An Efficient Distributed Algorithm for Constructing Spanning Trees in Wireless Sensor Networks

Sensors

Rosana Lachowski¹  Marcelo E. Pellenz¹  Manoel C. Penna¹  Edgard Jamhour¹ 

[1] PPGIa, Pontifical Catholic University of Parana – Parana, Curitiba 80215-901, Brazil; E-Mails:

关键词: wireless sensor networks;    distributed spanning tree algorithms;    routing;    shortest path trees;   

DOI  :  10.3390/s150101518

来源: mdpi

【 摘 要 】

Monitoring and data collection are the two main functions in wireless sensor networks (WSNs). Collected data are generally transmitted via multihop communication to a special node, called the sink. While in a typical WSN, nodes have a sink node as the final destination for the data traffic, in an ad hoc network, nodes need to communicate with each other. For this reason, routing protocols for ad hoc networks are inefficient for WSNs. Trees, on the other hand, are classic routing structures explicitly or implicitly used in WSNs. In this work, we implement and evaluate distributed algorithms for constructing routing trees in WSNs described in the literature. After identifying the drawbacks and advantages of these algorithms, we propose a new algorithm for constructing spanning trees in WSNs. The performance of the proposed algorithm and the quality of the constructed tree were evaluated in different network scenarios. The results showed that the proposed algorithm is a more efficient solution. Furthermore, the algorithm provides multiple routes to the sensor nodes to be used as mechanisms for fault tolerance and load balancing.

【 授权许可】

CC BY   
© 2015 by the authors; licensee MDPI, Basel, Switzerland.