and PG level projects,mini projects and many more here ...

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 clustering.

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 [12]. 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.