Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor Networks
Open Access
- 11 December 2015
- Vol. 15 (12) , 31224-31243
Abstract
Multicasting is a fundamental network service for one-to-many communications in wireless sensor networks. However, when the sensor nodes work in an asynchronous duty-cycled way, the sender may need to transmit the same message several times to one group of its neighboring nodes, which complicates the minimum energy multicasting problem. Thus, in this paper, we study the problem of minimum energy multicasting with adjusted power (the MEMAP problem) in the duty-cycled sensor networks, and we prove it to be NP-hard. To solve such a problem, the concept of an auxiliary graph is proposed to integrate the scheduling problem of the transmitting power and transmitting time slot and the constructing problem of the minimum multicast tree in MEMAP, and a greedy algorithm is proposed to construct such a graph. Based on the proposed auxiliary graph, an approximate scheduling and constructing algorithm with an approximation ratio of 4 l n K is proposed, where K is the number of destination nodes. Finally, the theoretical analysis and experimental results verify the efficiency of the proposed algorithm in terms of the energy cost and transmission redundancy.Keywords
Funding Information
- National Natural Science Foundation of China (61033015, 60933001)
- National Grand Fundamental Research 973 Program (2012CB316200)
This publication has 36 references indexed in Scilit:
- Spatial Reusability-Aware Routing in Multi-Hop Wireless NetworksIEEE Transactions on Computers, 2015
- A Biology-Based Algorithm to Minimal Exposure Problem of Wireless Sensor NetworksIEEE Transactions on Network and Service Management, 2014
- CDC: Compressive Data Collection for Wireless Sensor NetworksIEEE Transactions on Parallel and Distributed Systems, 2014
- Directional routing and scheduling for green vehicular delay tolerant networksWireless Networks, 2012
- Flooding-limited and multi-constrained QoS multicast routing based on the genetic algorithm for MANETsMathematical and Computer Modelling, 2011
- A 3.4713-approximation algorithm for the capacitated multicast tree routing problemTheoretical Computer Science, 2009
- Size-constrained tree partitioning: Approximating the multicast-tree routing problemTheoretical Computer Science, 2009
- Wireless sensor network surveyComputer Networks, 2008
- Minimum-Power Multicast Routing in Static Ad Hoc Wireless NetworksIEEE/ACM Transactions on Networking, 2004
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner TreesJournal of Algorithms, 1995