Loading...
|
Please use this identifier to cite or link to this item:
https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/34925
|
| Title: | A decentralized temporal coverage maintenance protocol and obstacle-resist routing and localization algorithms in WSNs |
| Other Titles: | 無線感測網路之時間覆蓋維護技術、克障繞徑及定位演算法 |
| Authors: | 朱威誠;Ju, Wei-cheng |
| Contributors: | 淡江大學資訊工程學系資訊網路與通訊碩士班
張志勇;Chang, Chih-yung |
| Keywords: | 感測器;繞徑;覆蓋;障礙物;定位;sensor;routing;Coverage;obstacle;localization |
| Date: | 2008 |
| Issue Date: | 2010-01-11 05:47:13 (UTC+8) |
| Abstract: | 無線感測網路已廣泛應用於環境監控、軍事及醫療監控。根據其不同的應用與場景，在研究上急待解決的問題包括覆蓋、繞徑、定位等研究議題。位置資訊的利用在過去許多國內外的研究中一直被高度重視，位置資訊的取得與否，將影響演算法發展的難易度及效率。本論文以位置資訊的獲得程度將研究主題區分為兩大部份：(1) 在精確位置資訊的條件下，探討克障繞徑以及時間覆蓋的議題。(2) 在不精確的位置資訊的環境下，開發克障且電量平衡的繞徑協定。
在第一部份的研究主題上，本論文假設每個感測器均具有精準的位置資訊，並據此提出一新的繞徑演算法，稱為WRGP。其改善了環境中障礙物對Greedy Forwarding Routing所造成的不良影響。在運作之初，WRGP會先找出包圍障礙物四周的節點，我們稱這些節點為Border Node。隨後，位於障礙物凹洞區的節點便開始進行權重值更動的工作，利用權重值的更動，這些Border Nodes便能夠建立一禁閉區以防止封包進入凹洞區。最後，WRGP選出一些具有特殊地位的Border Nodes成為Effective Border Nodes，這些Effective Border Nodes主要用於建立一條自身至Sink的最佳封包傳送路徑。本論文所提出的WRGP不儘降低了網路初始化的通訊成本，也可利用Effective Border Nodes來導引封包至最佳的傳送路徑。此外，本論文亦提出一繞徑協定，稱為M-WRGP，以克服環境中具有多障礙物並提昇繞徑效能。
除了繞徑的議題外，我們提出了一稱為EBHMM的演算法以解決覆蓋問題。空間上的完全覆蓋其達成的條件必需要有足夠的移動式感測器以填補網路中的空洞。當網路中的感測器數量不足以填滿空洞時，移動式感測器以搬移空洞的方式將可達到時間上的覆蓋。但是若只有固定少數的感測器參與空洞搬移，則很容易造成網路節點電量不均的情況發生。在這個研究議題上，本論文以節點數不足的環境為假設場景，發展一電量平衡的空洞搬移技術，以達到時間上的完全覆蓋，並使網路生命期得以延長。
在第二個部份中，我們考慮感測節點具有不精確之位置資訊，在這種艱困的環境下，本論文的議題再度回到繞徑協定上。在傳統的繞徑協定中，尋找一條最短的傳送路徑以減少封包傳遞的時間為共同的目標。但是由於封包經常在此路徑上傳送，因此此路徑上的節點便較其他節點消耗更多的電量。另一方面，不精確的位置資訊以及障礙物的存在將導致某些繞徑協定效能降低。為解決此問題，本論文提出了一繞徑演算法，稱為JLR。JLR結合了電量平衡以及克障的功能，運作在不精確位置資訊的環境下。首先，JLR以裝載方向性天線的機器人進行定位。之後，感測器再建立緊鄰障礙物的禁閉區以防止封包進入凹洞區。
Wireless sensor networks (WSNs) have been widely applied on applications such as environment monitoring, military, and remote medical system. In the past few years, research issues including coverage, routing and localization have received much attention and required more efforts to improve the performance of existing work. The location information is a critical factor that it determines the difficulty of the algorithm design and significantly impacts their performance. Based on the different levels of obtained location information, the research issues proposed in this thesis can be categorized into two parts: (1) The issues of obstacle-resist routing protocol and temporal coverage with accurate location information; (2) The obstacle-resist and energy-balanced routing protocol with inaccurate location information.
In the first part, this thesis proposes a novel mechanism, called WRGP, which removes the impact of obstacles on the greedy forwarding routing. The proposed WRGP initially identifies the border nodes that surround the obstacle. The border nodes in the concave region of the obstacle then initiate the weight assigning process aiming at establishing a forbidden region to prevent the packets from entering the concave region. Finally the WRGP identifies some border nodes to act as the effective border nodes for constructing the optimal routes from themselves to the sink node. The proposed WRGP reduces the control overheads and guides the packets moving along the shortest path from the encountered effective border node to the sink node. In addition, the M-WRGP is further developed to cope with the multi-obstacle problem.
In addition to the routing issue, the coverage problem is one of the most important issues in WSNs and has been widely discussed in last decade. However, the spatial full-coverage only can be achieved when the surplus mobile sensors contribute a larger coverage area than the hole size. When there is no surplus mobile sensor to cover the hole, the mobile sensor moving the hole from one location to another can achieve the purpose of temporal full-coverage. However, if only some mobile sensors participate in the hole-movement task, the WSN will be energy-unbalanced. This thesis further considers a mobile WSN that contains holes but no redundant mobile sensor exists to heal the hole. To achieve the temporal full-coverage purpose, a distributed hole-movement mechanism is proposed aiming to balance the energy consumptions of mobile sensors.
The second part of this thesis focuses on the routing issue based on the network environment where each sensor has inaccurate location information. Constructing a best route is a common goal of existing researches on the routing issue. In a WSN, the best route is the shortest path that minimizes the end-to-end delay from source to destination. However, the sensor nodes that participate in the best route might consume more energy to deliver the packet than other sensor nodes. On the other hand, the inaccurate location information and the existence of obstacles can significantly drop the performances of existing routing protocols. This thesis proposes a novel algorithm, called JLR, which takes both the energy balancing and obstacle resistance issues into consideration under the network environment where all sensors have inaccurate location information. Initially, a robot localization approach based on the directional-antenna system is proposed to offer the inaccurate location information to each sensor node. Afterward, the sensor nodes that are nearby the obstacles cooperatively establish the forbidden regions to prevent the packet from entering the concave regions. Compared with the well known GPSR routing protocol, the JLR expects to improve the performance in terms of packet delivery ratio and network lifetime. |
| Appears in Collections: | [Graduate Institute & Department of Computer Science and Information Engineering] Thesis
|
All items in 機構典藏 are protected by copyright, with all rights reserved.
|
