Loading...
|
Please use this identifier to cite or link to this item:
https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/34953
|
| Title: | Joint deployment, repairing and broadcasting algorithms for wireless sensor networks with obstacles |
| Other Titles: | 在無線感測網路中發展克服障礙物之網路佈建、修復以及廣播演算法 |
| Authors: | 張栩瑞;Chang, Hsu-ruey |
| Contributors: | 淡江大學資訊工程學系博士班
張志勇;Chang, Chih-yung |
| Keywords: | 無線感測網路;障礙物;網路佈建;網路修復;廣播;Wireless sensor networks;Obstacles;Deployment;Repairing;Broadcasting |
| Date: | 2007 |
| Issue Date: | 2010-01-11 05:49:12 (UTC+8) |
| Abstract: | 在Wireless sensor networks (WSNs)環境中，監控區域的感測覆蓋面積會影響回傳到sink的監控資料精確度，如何將sensors佈置於特定欲監測區域內，並維持高效率的監測效能是個重要的議題。在網路佈建議題方面，sensors必須以低成本、高覆蓋的方式佈建在特定的監控區域裡。傳統最簡單的方式是隨機將sensors佈建在監控區域中，然而以隨機佈建會造成sensor佈建不均的問題。有鑑於此，我們首先研發了有效率的克障機器人佈點（OFRD），藉由所提出之感測點佈建策略、蛇行狀移動機制及障礙物與邊界處理規則，使機器人能夠快速且花費最少的sensors數量佈點於監測區域，並有效地避開障礙物。在網路修復議題方面，由於sensor電量的限制，並且常被佈置於戶外去監控環境資訊，因此在執行一段時間後會因電量消耗殆盡，而導致無法正常運作，此時其所負責的區域若沒其他sensor感測的話，將會使網路出現空洞。因此，本論文提出了一有效率的網路修復演算法（TRR），藉由機器人在行走過程中留下其行走的軌跡，使WSN中的sensors皆能追蹤機器人的位置資訊，並能以較短路徑發送修復封包以通知機器人進行毀損修復，使機器人能以動態、快速、省電及有效率的方式往修復區移動。此外，Home演算法提供機器人在進行修復的過程中，以剩餘電量來安排較佳行走路徑，來達到回Home充電及補充新的sensors的目的，使WSNs的覆蓋範圍得以更有效地維護。除了網路佈建與修復議題外，本論文更探討了如何在已佈建的WSNs下進行廣播。傳統的方式是以封包泛流的方式，將需求封包由sink廣播給所有監控區域的sensor，雖然方法簡單，但會造成大量的封包碰撞與頻寬浪費，進而影響資料收集的精確度。有鑑於此，我們提出一個有效率克服障礙物的廣播演算法（OFZBP），藉由動態的座標系統，讓每個sensor知道自己與sink之間的相對位置，並透過適當的封包傳送排程協定，以減少代傳點的數目與克服未知的障礙物，進而節省sensor電量與網路頻寬耗費、以及提高封包到達率。實驗結果顯示了本論文所提出的克障礙物網路佈建、修復以及廣播演算法，能夠成功克服障礙物，並比現存的其他演算法有較佳的效能。
In wireless sensor networks(WSNs), coverage of the monitoring area represents the quality of service (QoS) related to the surveillance. Node deployment and failure recovery are the key issues in providing the WSN with full coverage. In the deployment issue, sensor nodes should be efficiently deployed in a predetermined region in a low cost and high coverage quality manner. Random deployment is the simplest way for deploying sensor nodes but may cause the unbalanced deployment and therefore increase the hardware cost and create coverage holes. This thesis initially presents an efficient obstacle-free robot deployment algorithm, called OFRD, which involves the design of node placement policy, snake-like movement policy, obstacle handling rules, and boundary rules. By applying the proposed OFRD, the robot rapidly deploys near-minimal number of sensor nodes to achieve full sensing coverage even though there exist unpredicted obstacles.
Another important issue for maintaining a high quality of surveillance service is the failure recovery. Since sensor nodes are battery powered and placed at the outdoor environment, they might be failure due to energy exhaustion or environmental influence, and hence result in the WSN coverage-loss. In literature, a number of study developed robot deployment algorithms that aim at achieving full coverage while the number of deployed sensor nodes can be minimized. After completing the deployment task, the robot still patrols the monitoring region for maintaining full coverage. However, the efficiency of existing repairing algorithms can be further improved in terms of time and energy consumption required for the robot to execute the repairing task. Moreover, existing repairing algorithms did not consider the existence of obstacles and the constraint of limited energy of the robot. This thesis presents novel tracking mechanism and robot repairing algorithm for maintaining the coverage quality of the given WSN. Without the support of location information, the tracking mechanism leaves robot’s footmark on those sensors that are nearby the failure region to learn better routes for sending repairing requests to the robot. Upon receiving several repairing request messages, the robot applies the proposed repairing algorithm to establish an optimal route that passes through all failure regions with minimal overhead in terms of the required time and power consumption. In addition, the proposed repairing algorithm also considers the remaining energy of the robot so that the robot can be back to home for recharging energy and overcome the unpredicted obstacles.
In addition to the network deployment and repairing issues, this thesis further considers the broadcasting issue for a given WSN that has been deployed by the robot. Broadcasting is an essential operation for sink node to deliver a request message to a region of sensor nodes. Blind flooding is the most simple way and can overcome obstacles but consumes power and bandwidth resources and raises the packet collision and contention problems. An efficient obstacle-free broadcasting protocol, namely OFZBP, is proposed by utilizing the location information of sensors to reduce the number of forwarding nodes and overcome the unpredictable obstacles. By applying the proposed OFZBP, each zone manager determines whether it would subsequently forward the request or not, according to the received zone ID of sink node and neighboring obstacle information. As a result, the proposed OFZBP reduces the packet collisions and increases the packet success rate in the broadcasting operation even through the existence of unpredictable obstacles.
Performance evaluation of the proposed obstacle-free deployment, repairing and broadcasting algorithms overcome the unpredicted obstacles and outperform the existing related work. |
| Appears in Collections: | [資訊工程學系暨研究所] 學位論文
|
All items in 機構典藏 are protected by copyright, with all rights reserved.
|
