Back to Search
Start Over
Centralized and Distributed Delay-Bounded Scheduling Algorithms for Multicast in Duty-Cycled Wireless Sensor Networks
- Source :
- IEEE/ACM Transactions on Networking. 25:3573-3586
- Publication Year :
- 2017
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2017.
-
Abstract
- Multicast is an important way to diffuse data in duty-cycled wireless sensor networks (WSNs), where nodes can receive data only in active state. The communication delay can be extremely large if inappropriate schedules are adopted. Unfortunately, most previous methods do not consider controlling multicast delay energy-efficiently. This paper studies the minimum active time slot augmentation for delay-bounded multicast (MAADM) problem in duty-cycled WSNs. The MAADM problem is proved to be NP-hard even under the node-exclusive interference model. An optimal algorithm is proposed for the MAADM problem when $K=2$ and a heuristic latency bounding algorithm is proposed for source-to-all communications, where $K$ denotes the number of the destination nodes. When $K>2$ , two ( $K$ −1)-approximation algorithms are designed for the MAADM problem. In addition, a low computation-complexity distributed algorithm is proposed. To the best of our knowledge, this is the first work that develops a series of efficient centralized and distributed algorithms for the MAADM problem in duty-cycled WSNs. The theoretical analysis and experimental results verify that all the proposed algorithms have high performance in terms of delivery delay and energy consumption.
- Subjects :
- Schedule
Computer Networks and Communications
Computer science
computer.internet_protocol
Distributed computing
02 engineering and technology
Fair-share scheduling
Scheduling (computing)
0202 electrical engineering, electronic engineering, information engineering
Xcast
Electrical and Electronic Engineering
Pragmatic General Multicast
Protocol Independent Multicast
Multicast
business.industry
Approximation algorithm
020206 networking & telecommunications
Energy consumption
Computer Science Applications
Key distribution in wireless sensor networks
Source-specific multicast
Distributed algorithm
IP multicast
020201 artificial intelligence & image processing
Algorithm design
business
Wireless sensor network
computer
Software
Computer network
Subjects
Details
- ISSN :
- 15582566 and 10636692
- Volume :
- 25
- Database :
- OpenAIRE
- Journal :
- IEEE/ACM Transactions on Networking
- Accession number :
- edsair.doi...........f2a5131c45604ae9875bbfc696a39739