Automatic Decentralized Clustering for Wireless Sensor Networks
- PDF / 913,199 Bytes
- 12 Pages / 600 x 792 pts Page_size
- 88 Downloads / 280 Views
Automatic Decentralized Clustering for Wireless Sensor Networks Chih-Yu Wen Department of Electrical and Computer Engineering, University of Wisconsin-Madison, 1415 Engineering Drive, WI 53706-1691, USA Email: [email protected]
William A. Sethares Department of Electrical and Computer Engineering, University of Wisconsin-Madison, 1415 Engineering Drive, WI 53706-1691, USA Email: [email protected] Received 6 June 2004; Revised 28 March 2005 We propose a decentralized algorithm for organizing an ad hoc sensor network into clusters. Each sensor uses a random waiting timer and local criteria to determine whether to form a new cluster or to join a current cluster. The algorithm operates without a centralized controller, it operates asynchronously, and does not require that the location of the sensors be known a priori. Simplified models are used to estimate the number of clusters formed, and the energy requirements of the algorithm are investigated. The performance of the algorithm is described analytically and via simulation. Keywords and phrases: wireless sensor networks, clustering algorithm, random waiting timer.
1.
INTRODUCTION
Unlike wireless cellular systems with a robust infrastructure, sensors in an ad hoc network may be deployed without infrastructure, which requires them to be able to self-organize. Such sensor networks are self-configuring distributed systems and, for reliability, should also operate without centralized control. In addition, because of hardware restrictions such as limited power, direct transmission may not be established across the complete network. In order to share information between sensors which cannot communicate directly, communication may occur via intermediaries in a multihop fashion. Scalability and the need to conserve energy lead to the idea of organizing the sensors hierarchically, which can be accomplished by gathering collections of sensors into clusters. Clustering sensors are advantageous because they (i) conserve limited energy resources and improve energy efficiency, (ii) aggregate information from individual sensors and abstract the characteristics of network topology, (iii) provide scalability and robustness for the network. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
This paper proposes a decentralized algorithm for organizing an ad hoc sensor network into clusters. Each sensor operates independently, monitoring communication among others. Those sensors which have many neighbors that are not already part of a cluster are likely candidates for creating a new cluster by declaring themselves to be a new “clusterhead.” The clustering algorithm via waiting timer (CAWT) provides a protocol whereby this can be achieved and the process continues until all sensors are part of a cluster. Because of the difficulty of the analysis, simplified models are used to study and abstract its performance. A simple formu
Data Loading...
