Centroid virtual coordinates - A novel near-shortest path routing paradigm

摘要

Geographic routing has received increasing attention in the context of Wireless Sensor Networks since it frees the network from the energy-demanding task of building and maintaining a structure. It requires however each node to know its position, which may be a prohibitive assumption for many applications. To this end, some prior work has focused on inferring a node's location from a set of location-aware anchor nodes.rnIn this work, we free ourselves from positioning techniques and anchor nodes altogether, and introduce and analyze the concept of virtual coordinates. These coordinates are chosen randomly when a node is switched on, and are updated each time the node relays a packet. As this process goes on, the virtual coordinates of the nodes converge to a near-optimal state. When using a greedy geographic approach on top of these coordinates, we show that the number of hops to reach the destination exceeds the shortest path by a few percent only. Moreover, our approach guarantees delivery even when nodes appear/disappear in the network, and under realistic transmission models.rnWe analytically prove the correctness of our protocol. Moreover, extensive simulations are used to show that our position-free solution outperforms existing geographic protocols - such as Greedy-Face-Greedy (GFG) or Greedy Perimeter Stateless Routing (GPSR) - in terms of energy-efficiency, path length and robustness.