TY - GEN
T1 - Approximate Scheduling and Constructing Algorithms for Minimum-Energy Multicasting in Duty-Cycled Sensor Networks
AU - Chen, Quan
AU - Gao, Hong
AU - Cheng, Siyao
AU - Cai, Zhipeng
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2016/3/7
Y1 - 2016/3/7
N2 - 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.
AB - 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.
KW - duty-cycled
KW - minimum energy multicasting
KW - wireless sensor networks
UR - https://www.scopus.com/pages/publications/84978086970
U2 - 10.1109/IIKI.2015.42
DO - 10.1109/IIKI.2015.42
M3 - 会议稿件
AN - SCOPUS:84978086970
T3 - Proceedings - 2015 International Conference on Identification, Information, and Knowledge in the Internet of Things, IIKI 2015
SP - 163
EP - 168
BT - Proceedings - 2015 International Conference on Identification, Information, and Knowledge in the Internet of Things, IIKI 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 4th International Conference on Identification, Information, and Knowledge in the Internet of Things, IIKI 2015
Y2 - 22 October 2015 through 23 October 2015
ER -