Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor Networks
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 th...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2015-12-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1424-8220/15/12/29860 |
| _version_ | 1811183989942124544 |
|---|---|
| author | Quan Chen Siyao Cheng Hong Gao Jianzhong Li Zhipeng Cai |
| author_facet | Quan Chen Siyao Cheng Hong Gao Jianzhong Li Zhipeng Cai |
| author_sort | Quan Chen |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-11T13:05:55Z |
| format | Article |
| id | doaj.art-4dbe27aa99484965b348fb4b1ef0bfae |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-04-11T13:05:55Z |
| publishDate | 2015-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-4dbe27aa99484965b348fb4b1ef0bfae2022-12-22T04:22:45ZengMDPI AGSensors1424-82202015-12-011512312243124310.3390/s151229860s151229860Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor NetworksQuan Chen0Siyao Cheng1Hong Gao2Jianzhong Li3Zhipeng Cai4School of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, ChinaSchool of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, ChinaSchool of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, ChinaSchool of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, ChinaDepartment of Computer Science, Georgia State University, Atlanta, GA 30303, USAMulticasting 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.http://www.mdpi.com/1424-8220/15/12/29860multicastingenergy optimizationpower awareSteiner treeduty cyclewireless sensor networks |
| spellingShingle | Quan Chen Siyao Cheng Hong Gao Jianzhong Li Zhipeng Cai Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor Networks Sensors multicasting energy optimization power aware Steiner tree duty cycle wireless sensor networks |
| title | Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor Networks |
| title_full | Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor Networks |
| title_fullStr | Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor Networks |
| title_full_unstemmed | Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor Networks |
| title_short | Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor Networks |
| title_sort | energy efficient algorithm for multicasting in duty cycled sensor networks |
| topic | multicasting energy optimization power aware Steiner tree duty cycle wireless sensor networks |
| url | http://www.mdpi.com/1424-8220/15/12/29860 |
| work_keys_str_mv | AT quanchen energyefficientalgorithmformulticastingindutycycledsensornetworks AT siyaocheng energyefficientalgorithmformulticastingindutycycledsensornetworks AT honggao energyefficientalgorithmformulticastingindutycycledsensornetworks AT jianzhongli energyefficientalgorithmformulticastingindutycycledsensornetworks AT zhipengcai energyefficientalgorithmformulticastingindutycycledsensornetworks |