A Balanced Clustering Algorithm for Non-uniformly Deployed Sensor Networks

Wireless sensor networks (WSNs) usually consist of small cheap sensors and they are extensively used for many applications including environment monitoring. In this paper, we focus on the problem that node density in a randomly deployed WSN differs region by region. In other words, sensor nodes are deployed non-uniformly over the network. Such a non-uniform topology makes clustering protocols less efficient. In this paper, we propose a new clustering algorithm for non-uniformly deployed sensor networks, which is called BCA (Balanced Clustering Algorithm). In BCA, each node determines the probability that the node itself becomes the cluster head (CH) by taking the node density, which is defined as the number of nodes within the node´s sensing range in this paper, into account. As a result, the coverage area of each cluster is almost equally distributed and unused redundant nodes are turned into sleep mode. Therefore, a large deviation of coverage areas of clusters in a network is remarkably decreased and the unnecessary duplication of sensing and transmission is also minimized. Because of the sleeping nodes not sending duplicated information over entire network, inefficient energy consumption is significantly reduced and thus the network lifetime is prolonged. According to the results of performance evaluation, the proposed BCA reduces energy consumption and increases the network lifetime as well as distributes the detection area of each cluster more uniformly than the existing protocols.