An Improved Approximation Algorithm for Minimum Multicast Time Problem in Wireless Sensor Networks

Author

Zhu, Jianming ; Chen, Xujing ; Hu, Xiaodong

Author_Institution

Inst. of Appl. Math., Chinese Acad. of Sci., Beijing

fYear

2006

fDate

14-17 Nov. 2006

Firstpage

1

Lastpage

4

Abstract

Given a network of processors and a source node, the minimum broadcast time problem is to find a scheme that broadcasts the message from the source to all other processors in the network in a minimum number of time steps assuming that at each time step a processor can send the message to at most one of its neighbors. This is a NP-hard problem and has been extensively studied in literature. In this paper we consider its general version, minimum multicast time problem whose goal is to multicast a message from the source to a set of destinations in a minimum number of time rounds. We focus on the problem in wireless sensor networks, which remains NP-hard and has a 41-approximation algorithm. In this paper, we propose a novel technique that reduces the performance ratio to 37

Keywords

approximation theory; broadcasting; message passing; multicast communication; wireless sensor networks; NP-hard problem; approximation algorithm; message broadcasting; minimum multicast time problem; wireless sensor network; Approximation algorithms; Broadcasting; Data processing; Delay; Mathematics; Mobile ad hoc networks; Multicast algorithms; NP-hard problem; Temperature sensors; Wireless sensor networks;

fLanguage

English

Publisher

ieee

Conference_Titel

TENCON 2006. 2006 IEEE Region 10 Conference

Conference_Location

Hong Kong

Print_ISBN

1-4244-0548-3

Electronic_ISBN

1-4244-0549-1

Type

conf

DOI

10.1109/TENCON.2006.344048

Filename

4142201