Title: A message complexity oriented design of distributed algorithm for long-lived multicasting in wireless sensor networks

Authors: Song Guo, Minyi Guo, Victor C.M. Leung

Addresses: School of Computer Science and Engineering, The University of Aizu, Aizu-Wakamatsu, Japan. ' Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China. ' Department of Electrical and Computer Engineering, The University of British Columbia, Vancouver, Canada

Abstract: We consider an optimisation problem in Wireless Sensor Networks (WSNs) that is to find a multicast tree rooted at the source node and including all the destination nodes such that the lifetime of the tree is maximised. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, we show that its high message complexity may prevent such contribution from being practically used in resource-constrained WSNs. In this paper, we proposed a new distributed sub-optimal algorithm that achieves a good balance on the algorithm-optimality and message complexity. In particular, we prove that it has a linear-message complexity. The trade-off between algorithm sub-optimality and message complexity is also studied by simulations.

Keywords: WSNs; wireless sensor networks; multicasting; distributed algorithms; communication complexity; energy efficiency; message complexity; wireless networks; simulation.

DOI: 10.1504/IJSNET.2009.029394

International Journal of Sensor Networks, 2009 Vol.6 No.3/4, pp.180 - 190

Available online: 29 Nov 2009 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article