Computer Engineering / Bilgisayar Mühendisliği

Permanent URI for this collectionhttps://hdl.handle.net/11147/10

Browse

Filters

2008 - 20102

Settings

Language: search.filters.language.enSubject: search.filters.subject.Sensor networks

Search Results

Now showing 1 - 2 of 2
  • Article
    Citation - WoS: 13
    Citation - Scopus: 18
    Graph Matching-Based Distributed Clustering and Backbone Formation Algorithms for Sensor Networks
    (Oxford University Press, 2010) Dağdeviren, Orhan; Erciyeş, Kayhan
    Clustering is a widely used technique to manage the essential operations such as routing and data aggregation in wireless sensor networks (WSNs). We propose two new graph-theoretic distributed clustering algorithms for WSNs that use a weighted matching method for selecting strong links. To the best of our knowledge, our algorithms are the first attempts that use graph matching for clustering. The first algorithm is divided into rounds; extended weighted matching operation is executed by nodes in each round; thus the clusters are constructed synchronously. The second algorithm is the enhanced version of the first algorithm, which provides not only clustering but also backbone formation in an energy-efficient and asynchronous manner. We show the operation of the algorithms, analyze them, provide the simulation results in an ns2 environment. We compare our proposed algorithms with the other graph-theoretic clustering algorithms and show that our algorithms select strong communication links and create a controllable number of balanced clusters while providing low-energy consumptions. We also discuss possible applications that may use the structure provided by these algorithms and the extensions to the algorithms. © The Author 2009. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved.
  • Conference Object
    Citation - WoS: 13
    Citation - Scopus: 12
    Distributed Algorithms To Form Cluster Based Spanning Trees in Wireless Sensor Networks
    (Springer Verlag, 2008) Erciyeş, Kayhan; Özsoyeller, Deniz; Dağdeviren, Orhan
    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.