Energy-Efficient Broadcast Scheduling Algorithm in Duty-Cycled Multihop Wireless Networks
Joint Authors
Chen, Quan
Wang, Tao
Cheng, Lianglun
Tao, Yongchao
Gao, Hong
Source
Wireless Communications and Mobile Computing
Issue
Vol. 2019, Issue 2019 (31 Dec. 2019), pp.1-14, 14 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2019-02-06
Country of Publication
Egypt
No. of Pages
14
Main Subjects
Information Technology and Computer Science
Abstract EN
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.
American Psychological Association (APA)
Chen, Quan& Wang, Tao& Cheng, Lianglun& Tao, Yongchao& Gao, Hong. 2019. Energy-Efficient Broadcast Scheduling Algorithm in Duty-Cycled Multihop Wireless Networks. Wireless Communications and Mobile Computing،Vol. 2019, no. 2019, pp.1-14.
https://search.emarefa.net/detail/BIM-1212158
Modern Language Association (MLA)
Chen, Quan…[et al.]. Energy-Efficient Broadcast Scheduling Algorithm in Duty-Cycled Multihop Wireless Networks. Wireless Communications and Mobile Computing No. 2019 (2019), pp.1-14.
https://search.emarefa.net/detail/BIM-1212158
American Medical Association (AMA)
Chen, Quan& Wang, Tao& Cheng, Lianglun& Tao, Yongchao& Gao, Hong. Energy-Efficient Broadcast Scheduling Algorithm in Duty-Cycled Multihop Wireless Networks. Wireless Communications and Mobile Computing. 2019. Vol. 2019, no. 2019, pp.1-14.
https://search.emarefa.net/detail/BIM-1212158
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1212158