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

摘要

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