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 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[2]  
Banner R., 2008, P IEEE INFOCOM
[3]  
Burkhart M., 2004, Proc. of ACM MobiHoc
[4]   Approximation algorithms for directed Steiner problems [J].
Charikar, M ;
Chekuri, C ;
Cheung, TY ;
Dai, Z ;
Goel, A ;
Guha, S ;
Li, M .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 33 (01) :73-91
[5]  
Chlamtac Imrich., 2003, Ad Hoc Networks, V1, P13, DOI DOI 10.1016/S1570-8705(03)00013-1
[6]  
Damian M., 2008, P ACM MOBIHOC
[7]   AN APPLICATION OF SUBMODULAR FLOWS [J].
FRANK, A ;
TARDOS, E .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1989, 114 :329-348
[8]  
Hu Y., 2006, P IWCMC
[9]  
Jain K., 2003, P ACM MOBICOM
[10]   A real-time multicast routing algorithm for multimedia applications [J].
Jia, XH ;
Pissinou, N ;
Makki, K .
COMPUTER COMMUNICATIONS, 1997, 20 (12) :1098-1106
123