Analysis of minimum-energy path-preserving graphs for ad-hoc wireless networks

We consider ad-hoc wireless networks and the topology control problem defined as minimizing the amount of power needed to maintain connectivity. The issue boils down to selecting the optimum transmission power level at each node based on the position information of reachable nodes. Local decisions regarding the transmission power level induce a subgraph of the maximum powered graph G_max in which edges represent direct reachability at maximum power. We propose an analysis for constructing minimum-energy path-preserving subgraphs of G_max, i.e., ones minimizing the energy consumption between node pairs. We also propose an algorithm for constructing subgraph of G_max based on 1-hop neighbor information. By presenting experimental results we show the effectiveness of our proposed algorithm.