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

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.