Uniform Cluster formation Algorithm: Overview of clustering algorithm
Sensor networks are usually
composed of hundreds to a large indefinite number of sensor nodes, which appear
to be sprinkled randomly. In these networks, each node may be equipped with a
variety of sensors, such as acoustic, seismic, infrared, still/motion
video-camera, etc to capture interesting information in certain area and a
communication module to report it to the destination. Each node may have
sufficient processing power to make decision and it will be able to broadcast
this decision to the other nodes in the cluster. They typically utilize
intermittent wireless communication. Therefore, sensor networks should be
well-formed to relay information to destination.
Conventional algorithms that use centralized control and global properties of
the sensor network have inherent difficulties in the properties of scalability
and robustness, which are two important design goals for protocols in large-
scale sensor networks. Centralized, top-down algorithms often need to operate
with knowledge of the conditions and variables at every point of the network. In
a very large network, the network traffic and time delay induced by the
collection of this large amount of data may be undesirable.
Clustering has become very important in the operations of wireless sensor
networks. Performance of the wireless sensor networks and ad-hoc networks
completely depend on the formation of clusters of nodes.
Clustering is a fundamental mechanism to design scalable sensor network
protocols. The purpose of clustering is to divide the network by some disjoint
clusters. Through clustering, we can reduce routing table sizes, redundancy of
exchanged messages, energy consumption and extend a network’s lifetime.
In a highly efficient cluster formation with low overlap it is evident that the
broadcast is very efficient from the fact that the broadcast message is relayed
from the base station to cluster head, which further broadcast the messages to
their followers. The cluster formation having low overlap will experience a
small number of repeated broadcasts; thereby keeping the chances of possible
transmission collision to very low and significantly reducing the channel
traffic in the network.
The various applications that uses clustering are, to perform data aggregation
with reduced communication energy overhead, to facilitate queries on the sensor
network; formation of infrastructure for scalable routing; for efficient network
broadcast. For many applications single level clustering is sufficient and,
there may be other applications that may require multi-level hierarchical
A simple example is in data collection. In an unclustered network, if an query
of sensor nodes over the area is desired, the query needs to be sent to every
sensor nodes in that area, each of which then needs to individually respond to
the request of the station. But, in a clustered network, a query of sensors over
a given area is sent only to the relevant cluster head which will further query
its followers and forward single collective reply to the base station.
Let us assume that nodes are randomly dispersed in a field as shown in the
figure 5.1(a). At the end of clustering process, each node belongs to one
cluster exactly and be able to communicate with the cluster head directly via a
single hop . Each cluster consists of a single cluster head (cluster leader)
and a bunch of member nodes (cluster follower), all of which should be within
one communication radius of the cluster-head, thus causing the overall shape of
the cluster to be approximately a circle of one communication radius, centered
on the cluster-head. This is as illustrated in figure 5.1(b). The purpose of the
clustering algorithm is to form the smallest number of clusters that makes all
nodes of network to belong to one cluster.