Please use this identifier to cite or link to this item: https://hdl.handle.net/11147/2361
Title: Distributed algorithms to form cluster based spanning trees in wireless sensor networks
Authors: Erciyeş, Kayhan
Özsoyeller, Deniz
Dağdeviren, Orhan
Dağdeviren, Orhan
Izmir Institute of Technology. Computer Engineering
Keywords: Sensor networks
Clustering
Spanning tree
Synchronizers
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
URI: http://doi.org/10.1007/978-3-540-69384-0_57
http://hdl.handle.net/11147/2361
ISBN: 9783540693833
ISSN: 0302-9743
0302-9743
1611-3349
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
View/Open
Show full item record

CORE Recommender

Google ScholarTM

Check

Altmetric


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