Abstract | ||
---|---|---|
Broadcast is an essential operation for disseminating messages in multihop wireless networks. Unfortunately, the problem of Minimum Transmission Broadcast (MTB) in duty-cycled scenarios is not well studied. Existing works always have rigid assumption that each node is only active once per working cycle. Aiming at making the work more practical and general, MTB problem in duty-cycled network where each node is allowed to active multiple times in each working cycle (MTBDCA) is investigated in this paper. Firstly, the MTBDCA problem is proved to be NP-hard and unlikely to have an (1 - o(1))ln Delta-approximation algorithm, where Delta denotes the maximum node degree. A novel covering problem is proposed based on an auxiliary graph, which is constructed to integrating the transmitting time slots into the network. Then, a ln(Delta + 1)-approximation algorithm is proposed for MTBDCA. Finally, the theoretical analysis and experimental results verify the efficiency of the proposed algorithm. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1007/978-3-319-94268-1 | WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS (WASA 2018) |
Field | DocType | Volume |
Wireless network,Graph,Broadcasting,Computer science,Computer network,Dissemination | Conference | 10874 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
20 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Quan Chen | 1 | 51 | 7.05 |
Tianbai Le | 2 | 0 | 0.34 |
Lianglun Cheng | 3 | 51 | 29.51 |
Zhipeng Cai | 4 | 1928 | 132.81 |
Hong Gao | 5 | 1086 | 120.07 |