Virtual backbone construction and energy efficient routing in wireless ad hoc and sensor networks

在無綫传感器网络及 ad hoc 網絡中虛擬骨幹網的構造和能量高效的路由等問題

Student thesis: Doctoral Thesis

View graph of relations


  • Hongwei DU

Related Research Unit(s)


Awarding Institution
Award date2 Oct 2008


Ad hoc wireless networks and sensor networks have received significant attention in recent years due to their potential applications in battlefield, disaster relief operations, traffic surveillance, environment monitoring and so on. Virtual backbone construction and energy efficient routing are fundamental and major issues in ad hoc wireless networks and sensor networks. This thesis investigates these issues and presents their solutions. The major work of the thesis can be summarized below. First, recent research points out that the flooding mechanism for topology update or route request in existing ad hoc routing protocols greatly degrades the network capacity. If we restrict the broadcast of control packets within a small subset of hosts in the network, the protocol overhead can be substantially reduced. This motivates our research of constructing a virtual backbone by computing a connected dominating set (CDS) in unit-disk graphs. In this chapter, we propose two distributed algorithms to approximate a minimum CDS. Two distributed message/time efficient algorithms have been proposed. Their performance is verified by a complete theoretical analysis. Both of them achieve good performance compared with existing ones in the literature. Second, in ad hoc wireless networks, a connected dominating set can be used as a virtual backbone to improve the performance. Many constructions for approximating the minimum connected dominating set are based on the construction of a maximal independent set. The relation between the size mis(G) of a maximum independent set and the size cds(G) of a minimum connected dominating set in the same graph G plays an important role in establishing the performance ratio of those approximation algorithms. Previously, it is known that mis(G)≤4∙cds(G)+1 for all unit disk graphs G. we improve it by showing mis(G)≤3.8∙cds(G)+1.2. Third, the connected dominating set plays an important role in ad hoc wireless networking. Many constructions for approximating the minimum connected dominating set have been proposed in the literature. We propose a new one with Steiner tree, which produces an approximation solution within a factor of 6.8 from optimal. This approximation algorithm can also be implemented distributedly. Forth, we discuss the energy efficient multicast problem in ad hoc wireless networks. We assume that each node in the network has a set of discrete levels of transmission power and nodes are relatively static. The problem is, given a set of nodes in the Euclidean plane and a multicast request, to construct a multicast tree rooted at the source and including all destinations such that the total energy cost of the transmitting nodes in the tree is minimized. We first prove that this problem is NP-hard and unlikely has an approximation algorithm with a logarithmic performance ratio. We then propose two algorithms, one is based on the Steiner tree method and the other is based on the connected dominating set method. Both algorithms have guaranteed performance ratios and outperform the existing methods. Finally, we propose an algorithm that can construct a data aggregation tree with theoretically bounded energy cost under the latency constraint. Extensive simulations show that the proposed algorithm is very efficient in energy-saving under the latency constraint and has better performance than other existing algorithms.

    Research areas

  • Wireless communication systems, Sensor networks, Design and construction, Ad hoc networks (Computer networks)