首页|Energy-Efficient Broadcast Scheduling Algorithm in Duty-Cycled Multihop Wireless Networks
Energy-Efficient Broadcast Scheduling Algorithm in Duty-Cycled Multihop Wireless Networks
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Wiley-Hindawi
Broadcasting is a fundamental function for disseminating messages in multihop wireless networks. Minimum-Transmission Broadcasting (MTB) problem aims to find a broadcast schedule with minimum number of transmissions. Previous works on MTB in duty-cycled networks exploit a rigid assumption that nodes have only active time slot per working cycle. In this paper, we investigated the MTB problem in duty-cycled networks where nodes are allowed arbitrary active time slots per working cycle (MTBDCA problem). Firstly, it is proved to be NP-hard and o(ln Δ)-inapproximable, where Δ is the maximum degree in the network. Secondly, an auxiliary graph is proposed to integrate nodes' active time slots into the network and a novel covering problem is proposed to exploit nodes' multiple active time slots for scheduling. Then, a ln(Δ + 1)-approximation algorithm is proposed for MTBDCA and a (ln(Δ + 1) + Δ)-approximation algorithm is proposed for all-to-all MTBDCA. Finally, extensive experimental results demonstrate the efficiency of the proposed algorithm.
Quan Chen、Tao Wang、Lianglun Cheng、Yongchao Tao、Hong Gao
展开 >
School of Computers, Guangdong University of Technology
Shenzhen Academy of Aerospace Technology
School of Computer Science and Technology, Harbin Institute of Technology
NSTL
Wiley-Hindawi
