Erciyes K.Ozsoyeller D.Dagdeviren O.2023-06-162023-06-162008354069383197835406938330302-9743https://doi.org/10.1007/978-3-540-69384-0_57https://hdl.handle.net/20.500.14365/3391Hewlett-Packard Company;Intel Corporation;Qumak-Sekom S.A. and IBM;Microsoft Corporation;ATM S.A.8th International Conference on Computational Science, ICCS 2008 -- 23 June 2008 through 25 June 2008 -- Krakow -- 72693We 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. © 2008 Springer-Verlag Berlin Heidelberg.eninfo:eu-repo/semantics/openAccessClusteringSpanning treeSynchronizersWireless sensor networksAgglomerationAlgorithmsBoolean functionsCommunicationComputer architectureDetectorsNetwork architectureParallel algorithmsSensorsSynchronizationTrees (mathematics)Wireless sensor networksBreadth-first search (BFS)Cluster basedCo-existingCommunication architecturesCommunication protocolsComputational sciencesData aggregationDistributed algorithmsHeidelberg (CO)Hier archical clusteringHigher level abstractionHybrid architecturesInternational conferencesIntra cluster communicationsSpanning treesWireless sensorsSensor networksConference Object10.1007/978-3-540-69384-0_572-s2.0-47849094011