Clustering In Mobile Ad Hoc Networks Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract - Clustering technology is an important research topic which has led to the development of new mobile ad hoc networks because clustering makes it possible to guarantee basic levels of system performance, such as throughput and delay, in the presence of both mobility and a large number of mobile terminals. A mobile Ad hoc networking is a self-configuring network of wireless devices connected by wireless links, which is rapidly deployable. Nodes generate user and application traffic and they carry out network control and routing functions. Random topologies lead to rapidly changing in connectivity and network partitions. This random nature along with bandwidth and power constraints together pose new problems in network control, scalability, especially in the design of higher level protocols such as routing, and Quality of Service requirements and soon. Clustering is the process of building hierarchies among nodes in the network. In this approach an ad hoc network is partitioned into group of nodes called as clusters. This paper presents a review of the different clustering algorithms and basis of which each of them takes the clustering decisions.

Keywords - Cluster Structure, Cluster Head Sections, Cluster Stability, Cluster Maintenance, Clustering Algorithms.

Ad Hoc Network

Wireless network

Wired internet








Home/Foreign Agent (HA/FA)

Mi - Mobile NodeCluster - The nodes in the network are randomly organized into partitions called clusters, and then the clusters are aggregated again into larger partitions called super clusters and so on. The nodes close to each other form a cluster. Each cluster elects a leading node called the cluster head which acts as a coordinator for the cluster. The nodes connected to more than one cluster are called gateway nodes and act as relays between clusters. Dividing a network into clusters helps maintain a relatively stable network topology. Clustering makes network more manageable. Cluster size is controlled through the radio transmission power.[26]

Cluster based algorithms are the most effective routing algorithms due to their scalability [1,2,16]. Clustering outperforms other routing algorithms in case of large networks. As all inter-cluster routing in such a scenario is through the cluster head, it is therefore more burdened than its members and tends to be a bottleneck in the system if not chosen appropriately. The objective of any clustering algorithm is to partition the network into several clusters which is the focus of current literature in this area.

MANET- a Mobile ad hoc network is also called as Mobile mesh network. MANET is an autonomous system or self-configuring network of mobile devices connected by wireless links - the union of which forms an arbitrary graph. The routers are free to move independently in any random direction and organize themselves arbitrarily. Thus, the strength of the network's wireless topology or connection may change rapidly in time or even disappear completely and unpredictably as it is very dynamic. Each node operates as an end system and a router for all other nodes in the network. Nodes can appear, disappear and re-appear as the time goes on and all the time the network connections should work between the nodes that are part of it. Such a network may operate in a standalone fashion, or may be connected to the larger Internet (external networks), no need for existing infrastructure. [18.22]

Fig. 1 Example of a Mobile Ad Hoc Network (MANET)

CHARACTERISTICS - Mobile Ad hoc Network (MANET) is a collection of independent mobile nodes that can communicate to each other via radio waves. The mobile nodes that are in radio range of each other can directly communicate, whereas others need the aid of intermediate nodes to route their packets. These networks are fully distributed, and can work at any place without the help of any infrastructure. This property makes these networks highly exible and robost.[22]

The characteristics of these networks are summarized as follows:

Communication via wireless means.

Nodes can perform the roles of both hosts and routers.

No centralized controller and infrastructure. Intrinsic mutual trust.

Dynamic network topology, frequent routing updates.

Autonomous, no infrastructure needed.

Can be set up anywhere.

Energy constraints.

Limited security.

Generally, the communication terminals have a mobility nature which makes the topology of the distributed networks time varying. The dynamical nature of the network topology increases the challenges of the design of ad hoc networks. Each radio terminal is usually powered by energy limited power source (as rechargeable batteries). The power consumption of each radio terminal could be divided generally into three parts -

Power consumption for data processing inside the Radio Terminal.

Power consumption to transmit its own information to the destination.

Power consumption is a critical issue in the design of the ad hoc networks.

The mobile devices usually have limited storage and low computational capabilities. They heavily depend on other hosts and resources for data access and information processing. A reliable network topology must be assured through efficient and secure routing protocols for Ad hoc networks. [18,22]



They provide access to information and services regardless of geographic position.

These networks can be set up at any place and time.

These networks work without any pre-existing infrastructure.


Limited resource.

Limited physical security.

Intrinsic mutual trust vulnerable to attacks than wired network.

Lack of authorization facilities.

Volatile network topology makes it hard to detect malicious nodes.

Security protocols for wired network cannot work for ad hoc networks.


Clustering Definition -

Clustering in mobile ad hoc network can be defined as the virtual partitioning of the dynamic nodes into various groups. These groups of the nodes are made with respect to their nearness to other nodes. Two nodes are said to be neighbor of each other when both of them lie within their transmission range and set up a bidirectional link between them. Depending on the diameter of the clusters there exist two kinds of cluster control architectures, known as one-hop clustering and multi-hop (d-hop) clustering.[21]

Fig. 2 Different ways to classify clustering schemes. [20]

Difference b/w one-hop clustering and multi-hop (d-hop) clustering -

One-hop clustering

Multi-hop (d-hop) clustering

In one-hop clustering every member node is at most 1-hop distance away from a central coordinator called as the clusterhead.

In multi hop clustering, the constraint of immediate neighborhood of members from the head is eliminated by allowing the nodes to be present at most d-hop distance away from each other to form a cluster.

The member nodes remain at most two hops distance away from each other within a logical cluster.

The member nodes remain at most d-hop distance away from each other to form a cluster.

Within each cell dedicated single channels are used for each direction of traffic.

Multiple channels are used for each direction of traffic

Clustering Structure -

Clustering Structure is a set of mobile nodes in a MANET. Inside each cluster the nodes are divided into different virtual groups and are allocated geographically adjacent into the same cluster according to some rules. The nodes with different behaviors for nodes included in a cluster are excluded from the cluster. [21]


(Ordinary node)




Fig. 3 Example of a Cluster formation in Mobile Ad Hoc Network (MANET)


Clusterhead -

It serves as a local coordinator for its cluster, performing inter-cluster transmission arrangement, data forwarding, and so on.

Clustergateway -

It is a non-clusterhead node with inter-cluster links, so that it can access neighboring clusters and forward information between clusters.

Clustermember -

It is usually called an ordinary node, which is a non-clusterhead node without any inter-cluster links (Clustergateway).

Clusters Formation -

A set of cluster cores in the form of star set scattered in the network such that:

Its internal node is the CH, and

Its leaves are nodes that choose the internal node as their broadcast neighbor.[23]

The ordinary nodes will be attached to their broadcast neighbor. The cluster diameter is at most equal to four. Every group of node is formed together and they are arranged in one Group. The main purpose of cluster formation is reducing the Transfer Rate and allocation of group in to subgroups and finally one leader will be selected. [17]

For the Selection of cluster group there are various methods used:

Find the nearby neighbors and joined the group.

Per group can have any number of nodes but mostly we assume 5 for maintenance.

Many groups can be made inside; cluster can also be made like tree structure also is made to reduce the level so reduce the traffic.

Cluster Naming -

Cluster naming is to correctly distribute the various nodes in order to describe the clusters. Each node belongs only to one cluster. For any node of the network declared as a clusterhead (CH), its field Zone ID number (ZID) takes the value of its Vertex ID number (VID). For the other nodes (Secondary cluster-heads (SCHs) and Ordinary nodes (ONs)), their field ZID takes a value equal to that of their broadcast neighbor. The attribution of the cluster identity is done in a hierarchical way: first of all, the CHs define the values of their field ZID that will be copied by their neighbors. This procedure will be reiterated on neighbors at two hops. Each cluster forms a tree. [17,23]

Role of cluster head in the cluster -

The node with the highest energy in the cluster is identified and selected as the Cluster-Head. [20]

Figure (a) - The neighboring relationship is first established according to a hop distance range.

Figure (b) - The clusters are organized using a dynamic transmission range adjustment protocol such that the number of the nodes in each cluster lies between a minimum and a maximum value.

Figure (c) - The node with the highest residual energy in each cluster is selected as the new CH.

Power consumption will then be averaged among the nodes in the cluster.

Cluster Maintenance -

Topological changes of an ad hoc network can be summarized in three various steps:

Lighting of the mobile node.

Stop of the mobile node.

Movement of the mobile node.

With regard to the broadcast neighbors, an automatic update is carried out each time that a broadcast neighbor modifies its field BN according to HELLO messages of its neighbors. The construction topology algorithm is a dynamic, distributed and fully self-organized algorithm.

The challenge here consists in defining the moment of the update of the CH and recalculating its information in the cluster, SCHs and if ONs will be automatically updated there is an update of the CH:

If there is a new node, the CH compares its average choice (AVRG.CH) with the new node one (AVRG'). If AVRG.CH<AVRG', the CH initializes its state, its ZID is empty.

If the average choice (AVRG) of a secondary clusterhead changes and became higher than the average choice (AVRG) of a clusterhead of the same cluster core, then the clusterhead initializes its state, it is removed from the cluster and then its ZID is empty.[23]


Several algorithms have been suggested for clustering and clusterhead selection. A number of clustering algorithms have been proposed, some are very simple and some with a view of optimally utilizing the critical parameters [3, 4, 5, 6, 7, 8, 9, 10, 12] of ad hoc networks. A review of the clustering and cluster head selection algorithms is being done in this paper.

The Lowest-Identifier (LID) -

This is the simplest clustering algorithm. In this algorithm every node in the network has a unique identifier (ID). This algorithm is also known as identifier-based clustering algorithm, chooses the node with the lowest ID as a cluster-head, the system performance is better than Highest-Degree in terms of throughput.

The Major drawbacks of this algorithm are its bias towards nodes with smaller ID's which may lead to the battery drainage of certain nodes, and it does not attempt to balance the load uniformly across all the nodes.

The algorithm takes following steps:

Every node broadcast its own ID periodically in Hello message.

All nodes receive hello messages from their neighboring nodes and match their IDs then the node having lowest ID is elected as cluster head.

The node, which can hear broadcast from two cluster head, is than becomes gateway node.[26]

In this algorithm there is no limit to the member nodes that a cluster can have. No network related parameter is given any consideration in selection of clusterhead, and hence the performance of such networks is of random and unpredictable nature. [3,13,24,25].

The Highest-Degree Algorithm -

This algorithm is also known as connectivity-based algorithm. This algorithm is based on the degree of nodes i.e. the number of its one-hop neighbors. Whenever the election procedure is needed, nodes broadcast its degree value or their Identifier (ID) which is assumed to be unique in the same network. According to the number of received IDs every node computes with the highest value of degree in its neighborhood is selected as the cluster-head and its neighbors join it as cluster members. The procedure is repeated with the remaining nodes until each node is assigned to a cluster. Any tie is broken by the lowest ID criterion.

Major drawbacks occur because this approach does not have any restriction on the upper bound on the number of nodes in a cluster, consequently the cluster head becomes highly overloaded leading to performance degradation. As the network degree of a node changes very frequently, the CHs are not likely to play their role as cluster-heads for very long. In addition, as the number of ordinary nodes in a cluster is increased, the throughput drops and system performance degrades.

These are two most popular criteria to partition mobile nodes. Both these algorithms do not provide any quantitative measure of cluster stability. [3,4,24,25]

The Distributed Clustering Algorithm (DCA) and Distributed and Mobility Adaptive Clustering Algorithm (DMAC) -

In this approach, the algorithm provides a generalized solution for clustering framework. Each node is assigned weights (a real number above zero) based on nodes' mobility-related parameters. The weights express how it is suitable a node is for the role of being a cluster-head. A node is chosen to be a cluster-head if its weight is higher than any of its neighbor's weight; otherwise, it joins a neighboring cluster-head. The smaller weight node id is chosen in case of a tie. The DCA makes an assumption that the network topology does not change during the execution of the algorithm. To verify the performance of the system, the nodes were assigned weights which varied linearly with their speeds but with negative slope. Results proved that the number of updates required is smaller than the Highest-Degree and Lowest-ID heuristics. Since node weights were varied in each simulation cycle, computing the cluster-heads becomes very expensive and there are no optimizations on the system parameters such as throughput and power control.

DCA is appropriate for networks that are quasi-static. DMAC is better suited to manage highly mobile networks. DMAC is a distributed algorithm in which clusterheads are selected using a weight-based criterion that depends on node mobility-related parameters. A Major drawback found in most clustering algorithms. A common assumption that is presented in most algorithms is that during the set up time nodes do not move while they are being grouped into clusters. Normally, clustering algorithms partition the network into clusters and only after this step has been accomplished, the non-mobility assumption is released. Afterwards the algorithm tries to maintain the cluster topology as nodes move. In real ad hoc situations this assumption cannot be made due to the constant mobility of nodes. Therefore one important feature of DMAC is that nodes can move, even during the clustering set up.

During the algorithm execution it is assumed that each node has a weight (a real number ≥ 0) and an ID (node's unique identifier) associated to it. The weight of a node represents node mobility parameters. During the execution of this algorithm, every node has knowledge of its ID, its weight as well as its neighbors ID and its neighbor's weight. DMAC is a message driven algorithm (except during the initial procedure). Two types of message are used: if a node joins a cluster it sends out a join message and if it becomes a cluster head it sends a CH message. A node chooses its own role (clusterhead or ordinary node) based on the knowledge it has of its current one hop neighbors. A node becomes a clusterhead if it has the highest weight among his one-hop neighbors; otherwise it joins a neighboring clusterhead.

DMAC executes five procedures at each node:

init routine

Link failure procedure

New link procedure

procedure depending upon the reception of a CH message

Procedure depending upon the reception of a Join message.

When a clusterhead receives a Join message from an ordinary node, it checks if the sending node is joining its own cluster or a different one. On the other hand, if an ordinary node receives a Join message from its clusterhead, it means that this clusterhead is giving up his role. Upon the reception of a CH message a node checks if it will affiliate or not to the sending clusterhead.

The adaptation feature of the clustering algorithm is made possible by letting each node react to the failure of a link with another node or to the presence of a new link. Upon link failure between a clusterhead and one of his node members, the membership of the node to the cluster is removed, and this node must determine his new role. A new link between two nodes means that a node has detected the presence of a new neighbor. In this case the node must determine if this new node has a larger weight than its own clusterhead in order to join it. If the node is a clusterhead itself then it will give up its role if the new clusterhead has a higher weight than his.

A major drawback presented by DMAC is that as node density increases, clusterheads may become overloaded. Proposes as a solution to this problem, to limit the number of node members of a cluster and to split existing clusters into several smaller clusters also mentions that it has been shown that DMAC can trigger undesirable global rippling effects. A solution to this problem is in a clusterhead change only where it takes place when two clusterheads become 1-hop neighbors.

Although DMAC provides a generalized framework for clustering nodes, it does not specify clearly weight metric method. [7]

The Weighted Clustering Algorithm (WCA) -

Although DMAC provides a generalized framework for clustering nodes, it does not specify clearly weight metric method. This is obtains from 1-hop clusters with one cluster-head. The election of the cluster-head is based on the weight of each node. It takes four factors into consideration and makes the selection of cluster-head and maintenance of cluster more reasonable. The four factors are node degree (number of neighbors), distance summation to all its neighboring nodes, mobility and remaining battery power. Although WCA has proved better performance than all the previous algorithms, it lacks a drawback in knowing the weights of all the nodes before starting the clustering process and in draining the CHs rapidly. As a result, the overhead induced by WCA is very high. However, how to normalize the factors is not addressed explicitly and the cumulative time of a node already serving as a clusterhead cannot accurately reflect the current level of battery power because a busy node may almost run out of power and it has never been a clusterhead.

The distributed clustering algorithm based on weight values. The weighted clustering algorithm (WCA) selects clusterheads by considering important aspects related to the efficient functioning of the system components. Therefore, in order to optimize battery usage, load balancing and MAC functionality a node is chosen to be a clusterhead according to the number of nodes it can handle, mobility, transmission power and battery power. To avoid communications overhead, this algorithm is not periodic and the clusterhead election procedure is only invoked based on node mobility and when the current dominant set is incapable to cover all the nodes. To ensure that clusterheads will not be over-loaded a predefined threshold is established in order to specify the number of nodes each clusterhead can ideally support. This parameter corresponds to δ. WCA selects the clusterheads according to the weight value of each node. The weight associated to a node v is defined as

Wv = w1∆v+ w2Dv+ w3Mv+ w4Pv

The node with the minimum weight is selected as a clusterhead. The weighting factors are chosen so that w1+ w2+ w3+ w4= 1. Mv is the measure of mobility. A node with less mobility is always a better choice for a clusterhead. Here mobility is taken by computing the running average speed of every node during a specified time T. ∆v is the degree difference that depicts the deviation of the actual degree of a node to the proposed ideal degree. ∆v is obtained by first calculating the number of neighbors of each node. The result of this calculation is defined as the degree of a node v, dv. To ensure load balancing the degree difference ∆v is calculated as |dv− δ| for every node v. The parameter Dv is defined as the sum of distances from a given node to all its neighbors and is used to depict energy consumption parameter since more power is needed for larger distance communications. The parameter Pv is the total time the node has served as a clusterhead. Pv is used to give a measure of how much battery power has been consumed. Power consumption in a clusterhead is higher than in an ordinary node as is has extra responsibilities. The total weight here is calculated such that it gives a deviation value from the ideal conditions hence the node with minimum weight is elected as cluster head. An attempt to optimize WCA by using entropy [10] has been made.

A clusterhead consumes more battery than an ordinary node because it has extra responsibilities. The clusterhead election algorithm finishes once all the nodes become either a clusterhead or a member of a clusterhead. The distance between members of a clusterhead, must be less or equal to the transmission range between them. No two clusterheads can be immediate neighbors. There has also been interesting work presented in which WCA is optimized by advanced computational methods such as genetic algorithms simulated annealing and particle swarm optimization. [8,15,25]

Optimization of WCA using Genetic Algorithm:

In [11], genetic algorithms have been used for enhancing the performance of clustering algorithms in mobile ad hoc networks. The clustering problem is mapped to individual chromosomes as input to the genetic algorithmic technique.

Optimization of WCA using Simulated Annealing:

In [12], simulated annealing algorithm has been applied to clustering algorithms used in ad hoc networks. Determining the optimal dominant set is a NP-hard problem. A good polynomial time approximation algorithm may be used to obtain a near optimal dominant set for cluster based topology.

This algorithm eventually finds the best solution without getting stuck in local minima by following the simulated annealing algorithm. Hence simulated annealing optimizes the performance of WCA such that each cluster head handles the maximum possible number of nodes in its cluster, resulting in minimum number of cluster heads and clusters. The simulation results show that fewer cluster heads are obtained by applying simulated annealing to WCA than the results of the original WCA. [24,25]

Weighted Distributed Clustering algorithm -

The New weighted distributed clustering algorithm called CBMD. It is the extended version of weighted clustering algorithm (CWA).


A novel weight function was introduced that can be used to select suitable and optimal clusterheads based on these parameters: connectivity (C), residual battery power (B), average mobility (M), and distance (D) and addressed explicitly for how to normalize these parameters.

Satisfying the load balancing between the clusters and reducing the number of clusters formed by specifying the maximum and minimum number of nodes that a clusterhead can ideally handle followed.

Each mobile node starts to measure its weight after n (small integer in order to minimize memory requirement) successive 'hello messages', where the result specifies the accurate value for the mobility and battery power.

The nodes with the largest local weights are elected as clusterheads.

As the nodes have various battery powers to start with, a more accurate metric would be to measure the power currently available at the node.

It was used to elect optimal clusterheads and divide optimal number of clusters without degrading the whole network performance, satisfying the load balancing between clusters, reducing the communication overhead and minimizing the explicit control messages caused by cluster maintenance, maximizing the stability of clustering to improve network life time.

Connectivity matric (C) - Neither nodes with the highest connectivity nor the lowest should be elected as clusterheads. The former will be congested and their battery power will drop rapidly and the latter will have a low cluster size and the advantages of clustering will be unable to be exploited. The problem can be solved by determining the number of nodes that can simultaneously be supported by a clusterhead.

Residual battery power metric (RBP)- Mobile nodes in a MANET usually depend on battery power supply; therefore prolonging a network's lifespan by reducing energy consumption is an attractive proposition and as CH as team leader and administrator carries extra responsibilities and performs more tasks compared with ordinary members it is likely to "die" early because of excessive energy consumption. These 'deaths', or 'dies', diminish the effectiveness of the network; a deficiency of mobile nodes due to energy depletion may cause network partition and communication interruption. Hence, it is vital to balance the energy consumption among nodes to avoid node failures, especially when the network density is comparatively sparse. Also, the battery power (set residual battery power of the node i as RBPi) can be resourcefully used within an optimum transmission range, i.e., nodes within close proximity will require less power to communicate with other nodes. But long-term service as a clusterhead can cause reduction in the battery power and hence RBPi of the current clusterhead is to be calculated periodically. The objective is to avoid this detriment where the total collapse of the current network topology may result and reduce the number of clusterhead elections and cluster formations. Finally, a node with high residual battery power RBPi can perform well as clusterhead for a longer duration.

Average mobility metric(M)- In most of the currently offered schemes addressing this property, the estimation of average node mobility M demands a GPS card with adequate precision to be mounted on every mobile node. An alternative method for measuring M which relaxes mobile nodes from such requirement. Node i measures its own average mobility Mi, used to calculate the weighted function value, in formula. This is achieved through contrasting the topology information it obtains during successive Hello messages (HMs). Mobile nodes maintain a short 'Neighborhood Record Table' (NRT); NRT rows comprise vectors representing the IDs of neighboring nodes, where each NRT row refers to different HM. Calculated Mi value actually represents the values recorded by i during the latest n HMs.

The distance between node and others within transmission range. It's better to elect a clusterhead with the nearest members. This might minimize node detachments and enhances clusters' stability.

The Connectivity, Energy & Mobility Driven Weighted Clustering Algorithm (CEMCA) -

To elect a cluster, the combination of particularly significant metrics is considered with attention focused on the extremes of the metrics rather than their existence or distribution per se. Characteristics such as the lowest node mobility, the highest node degree, the highest battery energy and the best transmission range are factored together. Total distribution of the algorithm throughout the network ensures every node having equal opportunity to assume the role of clusterhead. CEMCA is composed of two main stages. Following the election of the cluster head members are then grouped into a cluster. Election of clusterhead is based on calculated normalized values (normalized to 1) of mobility, degree and energy level for each node. Through broadcast to neighbors to compare node quality the best is selected for clusterhead. The selected clusterheads define their neighbors at two hops maximum to form their cluster membership and they store all member information just as all nodes record their clusterhead identifier. This information exchange permits the routing protocol to function both within a cluster and between the cluster groups.

Efficient Management Algorithm for Clustering (EMAC) -

EMAC [14] is another distributed clustering algorithm where the node weight is calculated using factors like the node degree, remaining battery power, transmission power, and node mobility for the cluster heads‟ election. The algorithm uses transmission range of node Pi instead of the sum of distance used in WCA in order to elect the node which can cover the largest range, thus, minimizing the number of clusters generated. In addition, the author argues that remaining battery power is a better measure than the cumulative time during which the node acts as a CH that is used in WCA, because it allows to extend the lifetime of nodes by relinquish the role as a CH in case of insufficient battery power. The algorithm also limits the number of nodes inside a cluster. By restricting the number of nodes catered by a cluster head helps in proper MAC functioning. The algorithm is based on the clusters‟ capacity and it uses the link lifetime instead of the node mobility for the maintenance procedure. The reason behind this is due to the fact that the node mobility metric does not affect the election of a CH as much as the link stability metric does.

EMAC implements different mechanisms for arrival of new nodes, cluster head nodes, member nodes, merging of clusters, reelection of cluster heads.

Entropy Based Clustering Algorithm -

In [11], the authors have used entropy as a measure of local and mutual information available to every node. Three node parameters: mobility, energy, and degree have been used for the selection of cluster head. The method first calculates the entropy for the three node parameters. These three entropies are hen combined through a simple linear model to find the total entropy of a node. The node with the lowest entropy is selected as a cluster head. The nodes gather information about their mutual mobility, energy, and degree through the exchange of Hello messages.


Major Drawbacks


Its bias towards nodes with smaller ID's which may lead to the battery drainage of certain nodes, and it does not attempt to balance the load uniformly across all the nodes.


This approach does not have any restriction on the upper bound on the number of nodes in a cluster, consequently the cluster head becomes highly overloaded leading to performance degradation. As the network degree of a node changes very frequently, the CHs are not likely to play their role as cluster-heads for very long. In addition, as the number of ordinary nodes in a cluster is increased, the throughput drops and system performance degrades.


Node density increases, clusterheads may become overloaded. Proposes as a solution to this problem, to limit the number of node members of a cluster and to split existing clusters into several smaller clusters also mentions that it has been shown that DMAC can trigger undesirable global rippling effects. A solution to this problem is found in where a clusterhead change only takes place when two clusterheads become 1-hop neighbors.


It lacks in knowing the weights of all the nodes before starting the clustering process and in draining the CHs rapidly. As a result, the overhead induced by WCA is very high.


The procedure consists of various steps as describe below:

Step 1: Initialization

x_range and y_range // x-axis and y-axis boundary.

max_distance= x_range * y_range // the maximum distance between two nodes.

The number of nodes (N).

max_disp // maximum displacement of one node.

Delta (Threshold for the cluster size).

Weights (w1, w2, w3, w4).

RUN_TIME //the time of simulation.

tx_range // transmission range.

Connection //the weighted connection matrix between all nodes.

Linkage //the linkage matrix, if linkage==1 then exist link between two nodes.

node_property//node property, 2=cluster head, 1=head neighbor, 0=homeless node


dv //the degree of every node.

Dv // the total distance from all its neighbors.

Mv // mobility.

Pv // power battery.

Step 2: Determine the specific location for each node in the network by using its uniform generation random.

grand ('unf',0,x_range); // generating random node location x.

grand ('unf',0,y_range); // generating random node location y.

Step 3: Compute the distance between any node and others lying in the same transmission range.

Step 4: Cluster-Head election Procedure:

dv = Sum(linkage) -1; // degree of every node

delta_v = abs (dv-delta); // computer the degree difference for each node.


For n=1 to N

If (dv = = 0) then Dv = max_distance;



Average speed for every node till current time T, This gives a measure of mobility and is denoted by Mv,


Where (Xt,Yt) and (Xt-1,Yt-1) are the coordinates of the node v at time t and (t-1) respectively.

Compute the remaining battery power Pv for every node.

The Combined weight Wv for each node v,

Wv= w1*delta_v + w2*Dv +w3*mv+w4*Pv.

Where w1, w2, w3 and w4 are the weighting factors and w1+w2+w3+w4=1

Taking the node with the smallest wv as the clusterhead. All the neighbors of the chosen clusterhead are no longer allowed to participate in the election. If the number of neighbors is larger than a predefined threshold we will take a predefined threshold only.

Repeat previous steps until there is no any node not selected yet as a member any cluster or as a clusterhead.

Step 5: update node positions: As all nodes move randomly after some unit of time. Using this formula to compute the velocity for each node.

V=grand (N,1,'unf',0,max_disp); //Determine the position

V=grand (N,1,'unf',0,2*PI); // Determine the direction

Step 6: Repeat this 3-5 steps until it reaches the maximum number of time.

Cluster starts when a Node boots up and broadcasts a cluster solicitation message to the neighbors.

If it does not get any reply from the neighboring within the maximum attempts, then it declares itself as a Cluster head.

If it receives a cluster advertisement, in response to its solicitation it examines the hop count value and if it is less than k then, it joins the cluster with the minimum hop count to the cluster head. However if the hop count advertised is k, then it declares itself as a cluster head.

Let's consider a scenario where a new node does not belong to any cluster and it need to join a cluster. [19]


A bit = 1

A bit = 0



Hop Count = 3

Hop Count = 2







Cluster Head



Cluster solicitation Message(Type,length,NodeID)

Cluster Advertisement Message(Type,length)

Cluster Acceptance Message (Type,length,Resevered,A,G,NodeID)

Step 1: As shown in figure i is a node doesn't belongs to any cluster and it wants to join a cluster. Therefore it broadcasts a cluster Solicitation message to its neighbors.

Step 2: k and j are the neighbors of the new node they receive solicitation message and send out a cluster advertisement message, which contains information such as cluster head ID and number of hops of that corresponding cluster.

Step 3: Each node maintains its approximate hop count. The hop count sent by node j to node i in the cluster advertisement which has the value 2 that is its own hop count incremented by one. Similarly the hop count value in the cluster advertisement sent from node k to node i is 3.

Step 4: Node i after receiving the cluster advertisement message,

If (hop count < k value) then

CH = Min (Hop count)

Send Acceptance message


Step 5: It sets the A bit to indicate acceptance of advertisement. If the hop count value is the same in two or more cluster advertisements then one of them can be selected randomly.

Step 6: When the new node i receives two or more cluster advertisements from nodes that belong to different clusters, it declares itself as a cluster gateway. It sets the G bit, in the cluster acceptance message.

Step 7: If the new node i does not receive any cluster advertisement after sending the cluster solicitation message multiple times or it receives all advertisements with maximum hop count, it declares itself as a cluster head.


It is observed that for all clustering algorithms the number of clusters decrease with increase in transmission range, as more nodes are within range of other nodes for longer periods of time. Therefore, less number of clusters, which are larger in size, are formed, and mobility causes lesser number of nodes which are at the border to move in and out of range of each other. This results in decrease in the number of clusterhead changes.

It can be concluded from the different algorithms that are considering the different attributes in the network such as node mobility, degree of clusterhead, distance between nodes, node battery power etc. result in selecting more stable clusterheads with lesser re-affiliations and increased network lifetime. For networks with highly mobile nodes, mobility should be the critical parameter and for network with high traffic energy could be a critical parameter for clusterhead selection. Highly mobile nodes lead to more volatile clusters and should not be used as critical nodes. It can be concluded that the importance to the different parameters should be according to the network environment. Soft computing techniques can be applied to achieve clustering using existing algorithms or new algorithms and these techniques can lead to improved results.