Date Added: Feb 2011
This paper proposes a routing strategy for wireless sensor networks that is valid even when the sensor nodes are distributed non-uniformly. Energy efficiency is the most important consideration in wireless sensor networks; hence, global communication should be achieved by combinations of local messages. The authors first propose a new underlying graph called the almost Delaunay planar net, which can be calculated from information local to the sensor nodes. They statistically analyze the efficiency of existing routing strategies in the almost Delaunay planar net. They also propose a new routing strategy that always guarantees the reachability on planar graphs, including the almost Delaunay planar net.