A Shortest-Path-Based Topology Control Algorithm in Wireless Multihop Networks

Yao Shen, Yunze Cai, and Xiaoming Xu
Appears in: 
CCR October 2007

In this paper, we present a shortest-path-based algorithm, called local shortest path (LSP), for topology control in wireless multihop networks. In this algorithm, each node locally computes the shortest paths connecting itself to nearby nodes based on some link weight function, and then it selects all the second nodes on the shortest paths as its logical neighbors in the final topology. Any energy model can be employed in LSP to design the link weight function whose value represents the power consumption required in the transmission along a link. We analytically prove that such a simple algorithm maintains network connectivity and guarantees that the minimal energy path between any two nodes is preserved in the final topology. Simulation results show that LSP can reduce the energy consumption, especially in heterogenous networks.

Public Review By: 
Konstantina Papagiannaki (INTEL Research Pittsburgh)

This paper proposes a new topology control algorithm for multihop wireless networks. The authors propose the use of shortest path algorithm for topology control, where the weight of each edge in the network reflects the energy consumption required for transmissions along that link. The topology is then constructed in a way that neighbors are those nodes that participate in the minimum cost paths of each node in the network. The advantage of the proposed algorithm is that it is very simple to implement, relies on local knowledge (energy required for transmission to neighbors), and that it does not rely on specific energy models, thus being able to incorporate heterogeneity in energy consumption across the network. Having studied the state of the art in the area of topology control in ad hoc networks, I find that this work is interesting in that it proposes a simple solution that does not require prior knowledge of the node coordinates and can guarantee the spanner property. The authors further prove analytically that the proposed simple algorithm maintains network connectivity. The simulations included offer enough evidence on the benefits of the proposed algorithm. An actual implementation would definitely make the claims even stronger. I would greatly encourage the authors to pursue such a future direction.