title: Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor Networks.
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.
authors.affiliation: School of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, China. chenquan@hit.edu.cn.
authors.forename: Quan
authors.initials: Q
authors.lastname: Chen
authors.affiliation: School of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, China. csy@hit.edu.cn.
authors.forename: Siyao
authors.initials: S
authors.lastname: Cheng
authors.affiliation: School of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, China. honggao@hit.edu.cn.
authors.forename: Hong
authors.initials: H
authors.lastname: Gao
authors.affiliation: School of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, China. lijzh@hit.edu.cn.
authors.forename: Jianzhong
authors.initials: J
authors.lastname: Li
authors.affiliation: Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA. zcai@gsu.edu.
authors.forename: Zhipeng
authors.initials: Z
authors.lastname: Cai
keywords: Steiner tree; duty cycle; energy optimization; multicasting; power aware; wireless sensor networks