Adaptive Clustering Algorithm for Wireless Sensor Networks

Abstract

In the context of Wireless Sensor Networks (WSN), the interactions of the sensors in order to provide service to a specific job is a significant issue. Services provided by WSNs include collecting data from the environment and aggregating them to address queries, or processing the collected data and using the result to adjust a number of environmental parameters such as temperature and moisture. In WSNs, a number of nodes may need to be used by the same job simultaneously and these nodes usually need to interact with one another. A number of studies have been conducted to minimize the overhead of such interactions and to optimize the energy and other resources utilized in the process. It is desirable in WSNs that enough resources be assigned to the jobs in such a way that the jobs can acquire their needed resources as fast as possible. The distances among the sensors that are assigned to carry out a specific job typically constitute an important factor in saving energy in the context of communications among this sensors. This thesis concerned introducing a clustering algorithm to enhance the efficiency of resource assignment by reducing the distances among the cooperating sensors. Furthermore, in the proposed algorithm, clusters are formed with different sizes in order to be able to assign just enough number of sensors to a requested job. The sizes of the clusters in the network were determined based on an input to the algorithm that contained the initial number of required clusters of each size. The algorithm forms clusters in such a way that the clusters' sizes are adapted to the input for the network for the purpose of serving the incoming jobs better. Upon providing a different input, the algorithm adaptively changes the network's clusters. In this thesis, a basic version of the clustering algorithm was developed. In the simulation results, several issues were recognized and resolved by revising/extending the initial version of the algorithm. In a second extension, the algorithm was complimented by attaching the isolated nodes (i.e., nodes not assigned to any cluster) to the clusters that did not obtain a sufficient number of nodes. The clustering algorithm was executed with a pseudo-randomly generated input. The results showed that the number of clusters with each size matched the requirements for the given input. The algorithm was also run with 100 different pseudo-randomly generated inputs and rectangular-grid networks of different sizes.