Greedy Anti-Void Routing Protocol for Wireless Sensor Networks

Author

Liu, Wen-Jiunn ; Feng, Kai-Ten

Author_Institution

Nat. Chiao Tung Univ., Hsinchu

Volume

11

Issue

7

fYear

2007

fDate

7/1/2007 12:00:00 AM

Firstpage

562

Lastpage

564

Abstract

The unreachability problem (i.e. the so-called void problem) which exists in the greedy routing algorithms has been studied for the wireless sensor networks. However, most of the current research work can not fully resolve the problem (i.e. to ensure the delivery of packets) within their formulation. In this letter, the greedy anti-void routing (GAR) protocol is proposed, which solves the void problem 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. The proofs of correctness for the proposed GAR protocol are also given at the end of this letter.

Keywords

greedy algorithms; routing protocols; wireless sensor networks; boundary finding technique; greedy anti-void routing protocol; greedy routing; localized algorithm; rolling-ball boundary traversal; unit disk graph; unreachability problem; void problem; wireless sensor networks; Councils; Neodymium; Noise measurement; Routing protocols; Solids; Tin; Wireless communication; Wireless sensor networks;

fLanguage

English

Journal_Title

Communications Letters, IEEE

Publisher

ieee

ISSN

1089-7798

Type

jour

DOI

10.1109/LCOMM.2007.070311

Filename

4273761