Cost Efficient Routing Strategies over Virtual Topologies for Wireless Sensor Networks

In this paper we focus on routing strategies for wireless sensor networks over hop count (HC) virtual coordinates. We consider the problem of optimally delivering data packets by means of multi-hop forwarding techniques where we assume that each node in the network, upon the execution of a proper distribution algorithm, can obtain a hop count number, i.e., the minimum number of transmissions needed to get to the sink (destination) node on the shortest path. We exploit HCs in place of commonly considered geographical coordinates as a valuable indication of the direction towards the sink. Within this framework, we present localized greedy routing schemes and compare them against globally optimal solutions, where the objective is to minimize a properly defined cost function. Further, we present novel routing algorithms where the statistical knowledge of the minimum costs of second order (two hops away) neighboring nodes is used as an aid to drive the forwarding process. These statistically enhanced schemes are found to outperform both hop count greedy approaches and geographical routing of up to one order of magnitude in terms of goodness of the selected path.