Please use this identifier to cite or link to this item:
Title: Distributed algorithms to form cluster based spanning trees in wireless sensor networks
Authors: Erciyeş, Kayhan
Özsoyeller, Deniz
Dağdeviren, Orhan
Keywords: Sensor networks
Spanning tree
Wireless sensor networks
Issue Date: 2008
Publisher: Springer Verlag
Source: Erciyeş, K., Özsoyeller, D., and Dağdeviren, O. (2008). Distributed algorithms to form cluster based spanning trees in wireless sensor networks. Lecture Notes in Computer Science, 5101 LNCS(PART 1), 519-528. doi:10.1007/978-3-540-69384-0_57
Abstract: We propose two algorithms to form spanning trees in sensor networks. The first algorithm forms hierarchical clusters of spanning trees with a given root, the sink. All of the nodes in the sensor network are then classified iteratively as subroot, intermediate or leaf nodes. At the end of this phase, the local spanning trees are formed, each having a unique subroot (clusterhead) node. The communication and data aggregation towards the sink by an ordinary node then is accomplished by sending data to the local subroot which routes data towards the sink. A modified version of the first algorithm is also provided which ensures that the obtained tree is a breadth-first search tree where a node can modify its parent to yield shorter distances to the root. Once the sub-spanning trees in the clusters are formed, a communication architecture such as a ring can be formed among the subroots. This hybrid architecture which provides co-existing spanning trees within clusters yields the necessary foundation for a two-level communication protocol in a sensor network as well as providing a structure for a higher level abstraction such as the γ synchronizer where communication between the clusters is performed using the ring similar to an α synchronizer and the intra cluster communication is accomplished using the sub-spanning trees as in the β synchronizers. We discuss the model along with the algorithms, compare them and comment on their performances.
Description: 8th International Conference on Computational Science, ICCS 2008; Krakow; Poland; 23 June 2008 through 25 June 2008
ISBN: 9783540693833
ISSN: 0302-9743
Appears in Collections:Computer Engineering / Bilgisayar Mühendisliği
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Files in This Item:
File Description SizeFormat 
2361.pdfConference Paper1.03 MBAdobe PDFThumbnail
Show full item record

CORE Recommender


checked on Oct 1, 2022

Page view(s)

checked on Oct 3, 2022


checked on Oct 3, 2022

Google ScholarTM



Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.