An adjustable structure for topology control in wireless ad hoc networks

In wireless ad hoc networks, the resources, such as energy, computation power, bandwidth and etc, available to each node are scare. Thus to improve the overall performance, the expenditures from the network operations should be balanced through the entire topology. One approach of solving such a problem is to keep the maximum node degree among all nodes as less as possible. However, a node having lower degree often prevents it from choosing better routes consuming less power between two ends. Therefore, a tradeoff is between the maximum node degree and the energy efficiency. In this paper we propose an adjustable structure, named r-neighborhood graph, to construct the topology of wireless ad hoc networks. The maximum node degree and energy efficiency of the topology can be adjusted through a parameter r, 0 ≤ r ≤ 1. Theoretic results show there must be some r´s such that the worst maximum node degree and the power stretch factor are bounded separately. The connectivity and planarity of the proposed structure are also guaranteed.