Energy-Efficient Broadcast Scheduling Algorithm in Duty-Cycled Multihop Wireless Networks

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...

Full description

Saved in:
Bibliographic Details
Published in:Wireless communications and mobile computing 2019-01, Vol.2019 (2019), p.1-14
Main Authors: Tao, Yongchao, Cheng, Lianglun, Wang, Tao, Chen, Quan, Gao, Hong
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Broadcasting
Energy efficiency
Mathematical analysis
Nodes
Researchers
Schedules
Scheduling
Sensors
Sleep
Wireless networks
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1530-8669
1530-8677
DOI:10.1155/2019/5064109