Efficient construction of network topology to conserve energy in wireless ad hoc networks

Wireless ad hoc networks are usually composed of battery constraint devices, which make energy conservation a vital concern of their design. Reducing energy consumption has been addressed through different aspects till now. Topology Control (TC) is a well-known approach which tries to assign transmission ranges of nodes to optimize their energy utilization while keeping some network propertied like connectivity. However, in current TC schemes, the transmission range of each node is mostly accounted as the exclusive estimator for its energy consumption, while ignoring the amount of data it sends or relays. In this paper, we redefine the problem of Topology Control regarding both transmission range and traffic load parameters. After proving the NP-hardness of the new problem, we mathematically formulate it as a mixed integer linear programming problem to find optimal solutions. Then, we introduce polynomial-time heuristic algorithms to practically solve the problem. During construction of network topology, we deliberately take into account the impact of the employed routing method on load of individual nodes. Finally, we show the advantages of our proposals through simulations. (C) 2007 Elsevier B.V. All rights reserved.