Title | ||
---|---|---|
Energy-Efficient Broadcast Scheduling Algorithm in Duty-Cycled Multihop Wireless Networks. |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1155/2019/5064109 | WIRELESS COMMUNICATIONS & MOBILE COMPUTING |
Field | DocType | Volume |
Approximation algorithm,Wireless network,Broadcasting,Computer science,Scheduling (computing),Efficient energy use,Computer network,Algorithm,Exploit,Dissemination,Degree (graph theory),Distributed computing | Journal | 2019 |
ISSN | Citations | PageRank |
1530-8669 | 1 | 0.35 |
References | Authors | |
15 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Quan Chen | 1 | 51 | 7.05 |
Tao Wang | 2 | 4 | 1.76 |
Lianglun Cheng | 3 | 51 | 29.51 |
Yongchao Tao | 4 | 1 | 0.35 |
Hong Gao | 5 | 1086 | 120.07 |