Approximate Scheduling and Constructing Algorithms for Minimum-Energy Multicasting in Duty-Cycled Sensor Networks

Multicasting is a fundamental network service for the one-to-many communications in wireless sensor networks. However, when the sensor nodes work in a duty-cycled way, a sender may need to transmit the same message several times to get to one group of its neighboring nodes, which complicates the minimum energy multicasting problem. In this paper, we study the problem of minimum energy multicasting with adjusted power(MEMAP problem) in the duty-cycled sensor networks, and it was proved to be NP-hard. To solve such problem, an auxiliary graph was proposed for the MEMAP problem and a greedy strategy was exploited to construct such graph. Based on the proposed auxiliary graph, an scheduling and constructing algorithm with approximation ratio of 4lnK was proposed, where K is the number of destination nodes. Finally, the theoretical analysis and experimental results verify the high performance of the algorithm in terms of the energy cost.