Energy efficient routing is one of the key design issues to prolong the lifetime of wireless sensor networks (WSNs) since sensor nodes can not be easily re-charged once they are deployed. During routing process, the routes with only few hops or with too many hops are not energy efficient. Hop-based routing algorithms can largely improve the energy efficiency of multi-hop routing in WSNs because they can determine the optimal hop number as well as the corresponding intermediate nodes during multi-hop routing process under medium or high density network. In this paper, we not only focus on studying the relationship between energy consumption and hop number from theoretical point of view but also provide a practical selection criterion of the sub-optimal hop number under practical sensor network so as to minimize the energy consumption. We extend the theoretical deduction of optimal hop number and propose our Hop-based Energy Aware Routing (HEAR) algorithm which is totally distributed and localized. Simulation results show that our HEAR algorithm can reduce the average energy consumption about 10 times compared to the direct transmission algorithm and 2 to 10 times than other algorithms like LEACH and HEED under various network topologies.

It is a fundamental problem to construct a virtual path layout minimizing the hop number as a function of the congestion for a communication network. It is known that we can construct a virtual path layout with asymptotically optimal hop number for a mesh of trees network, butterfly network, cube-connected-cycles network, de Bruijn network, shuffle-exchange network, and complete binary tree network. The paper shows a virtual path layout with minimum hop number for a complete binary tree network. A generalization to complete k-ary tree networks is also mentioned.