Efficient Virtual Backbone Construction with Routing Cost Constraint in Wireless Networks Using Directional Antennas

被引：10
作者：
Ding, Ling [1 ]
Wu, Weili [1 ]
Willson, James [1 ]
Du, Hongjie [1 ]
Lee, Wonjun [2 ]
机构：
[1] Univ Texas Dallas, Erik Jonsson Sch Engn & Comp Sci, Dept Comp Sci, Richardson, TX 75080 USA
[2] Korea Univ, Dept Comp Sci & Engn, Seoul, South Korea
来源：
IEEE TRANSACTIONS ON MOBILE COMPUTING | 2012年 / 11卷 / 07期
基金：
美国国家科学基金会;
关键词：
Directional antennas; connected dominating set; routing costs; wireless network; obstacle; general graph; NP-hard; virtual backbone; CONNECTED DOMINATING SETS; APPROXIMATION;
D O I：
10.1109/TMC.2011.129
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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 alpha Minimum rOuting Cost Directional VB (alpha-MOC-DVB). Besides the properties of regular VBs, alpha-MOC-DVB also has a special constraint-for any pair of nodes, there exists at least one path all intermediate directions on which must belong to alpha-MOC-DVB and the number of intermediate directions on the path is smaller than alpha times that on the shortest path. We prove that construction of a minimum alpha-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 alpha-MOC-DVB is much more efficient in the sense of VB size and routing costs compared to other VBs.
引用
收藏
页码：1102 / 1112
页数：11
相关论文
共 28 条
  • [1] [Anonymous], 1990, COMPUT INTRACTABILIT
  • [2] Barriere L., 2001, P ACM 5 INT WORKSH D
  • [3] Butenko S., 2001, P IEEE COOP CONTR OP
  • [4] Approximations for Steiner trees with minimum number of Steiner points
    Chen, DG
    Du, DZ
    Hu, XD
    Lin, GH
    Wang, LS
    Xue, GL
    [J]. JOURNAL OF GLOBAL OPTIMIZATION, 2000, 18 (01) : 17 - 33
  • [5] Deb B., 2003, P IEEE INT WORKSH SE
  • [6] Di W., 2006, P IEEE INT C COMM IC
  • [7] Ding L., 2008, P IEEE WIR COMM NETW
  • [8] Ding L., 2010, P IEEE 30 INT C DIST
  • [9] Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks
    Ding, Ling
    Wu, Weili
    Willson, James
    Du, Hongjie
    Lee, Wonjun
    Du, Ding-Zhu
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2011, 22 (10) : 1601 - 1609
  • [10] Du D.-Z., 2009, P ENC OPT
123