TY - JOUR T1 - Efficient and Resilient Backbones for Multihop Wireless Networks JF - Mobile Computing, IEEE Transactions on Y1 - 2008 A1 - Lee,Seungjoon A1 - Bhattacharjee, Bobby A1 - Srinivasan, Aravind A1 - Khuller, Samir KW - algorithm;protocols;wireless KW - backbone KW - channels; KW - CONSTRUCTION KW - distributed KW - networks;parameterized KW - protocol;multihop KW - wireless AB - 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. VL - 7 SN - 1536-1233 CP - 11 M3 - 10.1109/TMC.2008.69 ER -