Efficient and resilient backbones for multihop wireless networks

Seungjoon Lee*, Bobby Bhattacharjee, Aravind Srinivasan, Samir Khuller

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


We consider the problem of finding "backbones" in multihop wireless networks. The backbone provides end-to-end connectivity, allowing nonbackbone nodes to save energy since they do not have to route nonlocal data or participate in the routing protocol. Ideally, such a backbone would be small, consist primarily of high capacity nodes, and remain connected even when nodes are mobile or fail. Unfortunately, it is often infeasible to construct a backbone that has all of these properties; e.g., a small optimal backbone is often too sparse to handle node failures or high mobility. We present a parameterized backbone construction algorithm that permits explicit trade-offs between backbone size, resilience to node movement and failure, energy consumption, and path lengths. We prove that our scheme can construct essentially best possible backbones (with respect to energy consumption and backbone size) when the network Is relatively static. We generalize our scheme to build more robust structures better suited to networks with higher mobility. We present a distributed protocol based upon our algorithm and show that this protocol builds and maintains a connected backbone in dynamic networks. Finally, we present detailed packet-level simulation results to evaluate and compare our scheme with existing energy-saving techniques. Our results show that, depending on the network environment, our scheme increases network lifetimes by 20 percent to 220 percent without adversely affecting delivery ratio or end-to-end latency.

Original languageEnglish (US)
Article number4497202
Pages (from-to)1349-1362
Number of pages14
JournalIEEE Transactions on Mobile Computing
Issue number11
StatePublished - Nov 2008


  • An algorithm/protocol design and analysis
  • Mobile computing
  • Network protocols

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Efficient and resilient backbones for multihop wireless networks'. Together they form a unique fingerprint.

Cite this