標題: Greedy Routing with Anti-Void Traversal for Wireless Sensor Networks
作者: Liu, Wen-Jiunn
Feng, Kai-Ten
電信工程研究所
Institute of Communications Engineering
關鍵字: Greedy routing;void problem;unit disk graph;localized algorithm;wireless sensor network
公開日期: 1-七月-2009
摘要: The unreachability problem (i.e., the so-called void problem) that exists in the greedy routing algorithms has been studied for the wireless sensor networks. Some of the current research work cannot fully resolve the void problem, while there exist other schemes that can guarantee the delivery of packets with the excessive consumption of control overheads. In this paper, a greedy antivoid routing (GAR) protocol is proposed to solve the void problem with increased routing efficiency by exploiting the boundary finding technique for the unit disk graph (UDG). The proposed rolling-ball UDG boundary traversal (RUT) is employed to completely guarantee the delivery of packets from the source to the destination node under the UDG network. The boundary map (BM) and the indirect map searching (IMS) scheme are proposed as efficient algorithms for the realization of the RUT technique. Moreover, the hop count reduction (HCR) scheme is utilized as a short-cutting technique to reduce the routing hops by listening to the neighbor's traffic, while the intersection navigation (IN) mechanism is proposed to obtain the best rolling direction for boundary traversal with the adoption of shortest path criterion. In order to maintain the network requirement of the proposed RUT scheme under the non-UDG networks, the partial UDG construction (PUC) mechanism is proposed to transform the non-UDG into UDG setting for a portion of nodes that facilitate boundary traversal. These three schemes are incorporated within the GAR protocol to further enhance the routing performance with reduced communication overhead. The proofs of correctness for the GAR scheme are also given in this paper. Comparing with the existing localized routing algorithms, the simulation results show that the proposed GAR-based protocols can provide better routing efficiency.
URI: http://dx.doi.org/10.1109/TMC.2008.162
http://hdl.handle.net/11536/6996
ISSN: 1536-1233
DOI: 10.1109/TMC.2008.162
期刊: IEEE TRANSACTIONS ON MOBILE COMPUTING
Volume: 8
Issue: 7
起始頁: 910
結束頁: 922
顯示於類別:期刊論文


文件中的檔案:

  1. 000266033300004.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。