Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks

被引：51

作者：

Ding, Ling ^{[1
]}

Wu, Weili ^{[1
]}

Willson, James ^{[1
]}

Du, Hongjie ^{[1
]}

Lee, Wonjun ^{[2
]}

Du, Ding-Zhu ^{[1
]}

机构：

[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 PARALLEL AND DISTRIBUTED SYSTEMS | 2011年 / 22卷 / 10期

基金：

美国国家科学基金会;

关键词：

Connected dominating set; routing path; wireless network; obstacle; general graph; NP-hard; topology control; CONNECTED DOMINATING SETS; UNIT DISK GRAPHS; CONSTRUCTION; APPROXIMATION;

D O I：

10.1109/TPDS.2011.30

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Topology control is one vital factor to a wireless network's efficiency. A Connected Dominating Set (CDS) can be a useful basis of a backbone topology construction. In this paper, a special CDS, named alpha Minimum rOuting Cost CDS (alpha-MOC-CDS), will be studied to improve the performance of CDS based broadcasting and routing. In this paper, we prove that construction of a minimum alpha MOC-CDS is NP-hard in a general graph and we propose a heuristic algorithm for construction of alpha-MOC-CDS.

引用

页码：1601 / 1609

页数：9

共 27 条

[1]

[Anonymous], 1979, COMPUTERS INTRACTABI

[2]

Bao L., 2003, Proc. of ACM MobiHoc

[3]

Barriere L., 2001, P ACM 5 INT WORKSH D

[4]

Burkhart M., 2004, Proc. of ACM MobiHoc

[5] Approximations for Steiner trees with minimum number of Steiner points [J].

Chen, DG ;

Du, DZ ;

Hu, XD ;

Lin, GH ;

Wang, LS ;

Xue, GL .

JOURNAL OF GLOBAL OPTIMIZATION, 2000, 18 (01) :17-33

[6]

CHENG X, 2003, NETWORKS, V42, P7

[7] Virtual backbone construction in multihop ad hoc wireless networks [J].

Cheng, XZ ;

Ding, M ;

Du, DH ;

Jia, XH .

WIRELESS COMMUNICATIONS & MOBILE COMPUTING, 2006, 6 (02) :183-190

[8] UNIT DISK GRAPHS [J].

CLARK, BN ;

COLBOURN, CJ ;

JOHNSON, DS .

DISCRETE MATHEMATICS, 1990, 86 (1-3) :165-177

[9]

Ding L., 2008, P IEEE WIR COMM NETW

[10]

Ding L., 2010, P IEEE 30 INT C DIST

← 1 2 3 →