Distributed Multicast Tree Construction in Wireless Sensor Networks
Authors:
- 31 October 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 63 (1) , 280-296
Abstract
Multicast tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multica modeled as the Steiner tree problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length multi wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple algorithm, which we call toward source tree (TST), to build multicast trees in WSNs. We show three metrics of TST algorithm, i.e., running and energy efficiency. We prove that its running time is O(√(n log n)), the best among all existing solutions to our best knowledge. We prove that TST tree length is in the same order as Steiner tree, which give a theoretical upper bound and use simulations to show the ratio be only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of message complexity and the number of forwarding prove that they are both order-optimal. We give an efficient way to construct multicast tree in support of transmission of voluminous data.Keywords
Funding Information
- NSF China (61532012, 61325012, 61271219, 61521062, 61428205, 61602303, 91438115)
- China Postdoctoral Science Foundation
This publication has 31 references indexed in Scilit:
- Throughput-optimal broadcast on directed acyclic graphs2015
- Multicast for 6LoWPAN Wireless Sensor NetworksIEEE Sensors Journal, 2015
- A Low Cost, Highly Scalable Wireless Sensor Network Solution to Achieve Smart LED Light Control for Green BuildingsIEEE Sensors Journal, 2014
- GEographic Multicast (GEM) for Dense Wireless Networks: Protocol Design and Performance AnalysisIEEE/ACM Transactions on Networking, 2013
- SmartLoc2013
- Low Power Wireless Sensor Network for Building MonitoringIEEE Sensors Journal, 2012
- IP is dead, long live IP for wireless sensor networks2008
- Hierarchical geographic multicast routing for wireless sensor networksWireless Networks, 2008
- Energy optimal control for time-varying wireless networksIEEE Transactions on Information Theory, 2006
- A framework for routing and congestion control for multicast information flowsIEEE Transactions on Information Theory, 2002