Interference and power constrained broadcast and multicast routing in wireless ad hoc networks using directional antennas

被引：8
作者：
Li, Zheng [1 ]
Li, Deying [1 ,2 ]
Liu, Ming [3 ]
机构：
[1] Renmin Univ China, Sch Informat, Beijing 100872, Peoples R China
[2] Renmin Univ China, Key Lab Data Engn & Knowledge Engn, MOE, Beijing 100872, Peoples R China
[3] Univ Elect Sci & Technol China, Sch Comp Sci & Engn, Chengdu 610054, Peoples R China
来源：
COMPUTER COMMUNICATIONS | 2010年 / 33卷 / 12期
关键词：
Wireless ad hoc network; Energy-efficient; Interference; Broadcast/multicast; Approximation algorithm; APPROXIMATION ALGORITHMS;
D O I：
10.1016/j.comcom.2010.02.005
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper, we address the interference and power constrained broadcast/multicast routing problem (D-IPCB/M) in wireless ad hoc networks using directional antenna as a starting point, which jointly considers low-interference and energy-efficiency issues. Then we study the delay-bounded interference and power constrained broadcast/multicast routing problem (DB-D-IPCB/M). An approximation algorithm and a heuristic algorithm with low time complexity are proposed for the D-IPCB/M and DB-D-IPCB/M problem, respectively. Finally, we explore and investigate the multi-constrained subgraph optimization (MCSO) problem. We prove its NP-hard and propose an approximation scheme with theoretical performance guarantee for this class of optimization problems. This is a general result originated from the study of D-IPCB/M and DB-D-IPCB/M problems, which can be applicable to solve different optimization problems such as the multi-constrained broadcast/multicast routing problems. Broadcast/multicast message by using the routing trees found by our algorithms tends to not only have less channel collisions but also save energy to extend network lifetime. The theoretical results are evaluated by simulation studies. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：1428 / 1439
页数：12
相关论文
共 25 条
[11]   Energy efficient multicast routing in ad hoc wireless networks [J].
Li, Deying ;
Liu, Qin ;
Hu, Xiaodong ;
Ha, Xiaohua .
COMPUTER COMMUNICATIONS, 2007, 30 (18) :3746-3756
[12]   Energy efficient broadcast routing in static ad hoc wireless networks [J].
Li, DY ;
Jia, XH ;
Liu, H .
IEEE TRANSACTIONS ON MOBILE COMPUTING, 2004, 3 (02) :144-151
[13]  
Li X., 2005, P IEEE SECON
[14]  
Li Z., 2009, P COCOA
[15]  
LI Z, 2009, P IEEE MASS
[16]   Approximate minimum-energy multicasting in wireless ad hoc networks [J].
Liang, WF .
IEEE TRANSACTIONS ON MOBILE COMPUTING, 2006, 5 (04) :377-387
[17]  
Ramanathan Ram., 2001, P 2 ACM INT S MOBILE, P95
[18]  
ROY S, 2006, P IEEE INFOCOM
[19]  
TANG J, 2005, P IEEE INFOCOM
[20]  
TANG J, 2005, P IEEE ICC
123