Greedy Anti-Void Routing Protocol for Wireless Sensor Networks

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.