Efficient virtual backbone construction with routing cost constraint in wireless networks using directional antennas

Ling Ding, Weili Wu, James Willson, Hongjie Du, Wonjun Lee

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


Directional antennas can divide the transmission range into several sectors. Thus, through switching off sectors in unnecessary directions in wireless networks, we can save bandwidth and energy consumption. In this paper, we will study a directional virtual backbone (VB) in the network where directional antennas are used. When constructing a VB, we will take routing and broadcasting into account since they are two common operations in wireless networks. Hence, we will study a VB with guaranteed routing costs, named α Minimum rOuting Cost Directional VB (α-MOC-DVB). Besides the properties of regular VBs, α-MOC-DVB also has a special constraintfor any pair of nodes, there exists at least one path all intermediate directions on which must belong to α-MOC-DVB and the number of intermediate directions on the path is smaller than α times that on the shortest path. We prove that construction of a minimum α-MOC-DVB is an NP-hard problem in a general directed graph. A heuristic algorithm is proposed and theoretical analysis is also discussed in the paper. Extensive simulations demonstrate that our α-MOC-DVB is much more efficient in the sense of VB size and routing costs compared to other VBs.

Original languageEnglish
Article number6202811
Pages (from-to)1102-1112
Number of pages11
JournalIEEE Transactions on Mobile Computing
Issue number7
Publication statusPublished - 2012 Jul

Bibliographical note

Funding Information:
The research in this paper was supported by the US National Science Foundation (NSF) under grants CNS0831579 and CCF0728851. It was also supported in part by the NSF under grants CNS1016320 and CCF0829993 and was jointly sponsored by MEST, Korea under WCU (R33-2008-10044-0) and MKE, Korea under ITRC NIRA-2010-(C1090-1021-0008).


  • Directional antennas
  • NP-hard
  • connected dominating set
  • general graph
  • obstacle
  • routing costs
  • virtual backbone
  • wireless network

ASJC Scopus subject areas

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


Dive into the research topics of 'Efficient virtual backbone construction with routing cost constraint in wireless networks using directional antennas'. Together they form a unique fingerprint.

Cite this