Wireless Sensor Network, 2011, 3, 54-60
doi:10.4236/wsn.2011.32006 Published Online February 2011 (http://www.SciRP.org/journal/wsn)
Copyright © 2011 SciRes. WSN
A Distributed Weighted Cluster Based Routing
Protocol for MANETs
Naveen Chauhan, Lalit Kumar Awasthi, Narottam Chand, Vivek Katiyar, Ankit Chugh
Department of C omput er Science & Enginee r i ng , National Institute of Technology,
Hamirpur, India
E-mail: naveen@nitham.ac.in, nar.chand@gmail.com, lalit@nitham.ac.in,
vivek.kat@gmail.com, ankit@nitham.ac.in
Received January 10, 2011; January 14, 2011; February 17, 2011
Abstract
Mobile ad-hoc networks (MANETs) are a form of wireless networks which do not require a base station for
providing network connectivity. Many MANETs’ characteristics that distinguish MANETs from other wire-
less networks also make routing a challenging task. Cluster based routing is a MANET routing schemes in
which various clusters of mobile nodes are formed with each cluster having its own clusterhead which is re-
sponsible for routing among clusters. In this paper we propose and implement a distributed weighted clus-
tering algorithm for MANETs. This approach is based on combined weight metric that takes into account
several system parameters like the node degree, transmission range, energy and mobility of the nodes. We
have evaluated the performance of the proposed scheme through simulation in various network situations.
Simulation results show that improved distributed weighted clustering algorithm (DWCAIMP) outperforms
the original distributed weighted clustering algorithm (DWCA).
Keywords: MANETs, Clustering, Routing, Wireless Communication, Distributed Clustering
1. Introduction
MANETs are a form of wireless networks which do not
require a base station for providing network con nectiv ity.
In this networking concept, mobile devices form a tem-
porary community without any planned installation, or
human intervention. Each node acts as a host and a router
at the same time. This means that each node participating
in a MANET commits itself to forward data packets from
a neighboring node to another until a final destination is
reached. Mobile ad-hoc networks have many characteris-
tics which distinguish them from other wireless networks.
These factors are: no fixed network infrastructure, dy-
namic network configuration, node mobility an d frequent
node failure, low battery power, etc., which make routing
in MANETs quite a challenging task. Various routing
protocols have been proposed for MANETs with varying
performance in different network con ditions [1].
Cluster based routing is one of the routing schemes for
MANETs in which various clusters of mobile nodes are
formed with each cluster having its own clusterhead
which is responsible for routing between clusters. Clus-
tering of nodes saves energy and communication band-
width in ad-hoc networks.
In this paper we discuss distributed weighted cluster-
ing algorithm (DWCA) [2]. This approach is based on
combined weight metric that takes into account several
system parameters like the ideal node degree, transmis-
sion range, energy and mobility of the nodes. Depending
on specific applications some of these parameters can be
used in the metric to determine the clusterhead . However
more clusterheads lead to extra number of hops for a
packet when it is to be routed from source to destination .
On the other hand we can choose to have minimum
number of clusterheads to maximize the resource utiliza-
tion. Various parameters and their respective weights can
be determined to arrive at an efficient weighted cluster
based routing scheme.
The rest of the paper is organised as follows. In Sec-
tion 2 we give background information of MANETs and
cluster based routing schemes. We have described pro-
posed algorithm in Section 3. Performance evaluation
and comparison bia simulation is presented in Section 4.
Finally, Section 5 concludes the paper and talks about
N. CHAUHAN ET AL.
Copyright © 2011 SciRes. WSN
55
future work.
2. Background and Related Work
2.1. Mobile Ad-Hoc Networks
Mobile ad-hoc networks (MANETs) are a form of wire-
less networks which do not require a base station for
providing network connectivity. It defines simple mecha-
nisms which enable mobile devices to form a temporary
community without any planned installation, or human
intervention. Each node acts as a host and a router at the
same time. This means that each node participating in a
MANET commits itself to forward data packets from a
neighboring node to another until a final destination is
reached. In other words, the survival of a MANET relies
on the cooperation between its participating members.
MANETs have many advantages like low cost, on the fly
deployment, etc [3].
2.2. Routing in MANETs
Routing is a very challenging task in mobile ad hoc net-
works due to their peculiar characteristics like dynamic
mobility, frequent disconnections, low bandwidth, low
battery power, etc. Hence traditional routing protocols
like RIP [4] cannot be used in mobile ad hoc networks.
Various routing protocol schemes have been proposed
for mobile ad hoc networks like table driven, source in-
itiated on demand etc. and protocols like AODV [1],
DSDV [5], DSR [6], ZRP [7], etc.
2.3. Cluster Based Routing
One of the major problems of routing schemes in MA-
NETs is the reduction of routing and other control in-
formation overheads required for an autonomous organ-
ization in the face of node mobility. Cluster based
routing scheme provides a solution to this problem by
organizing the nodes into clusters to reduce communica-
tion overhead. Thus a virtual network infrastructure is
created which resembles fixed network infrastructure.
This is crucial for scalability of media access protocols,
routing protocols and the security infrastructure besides
the advantage of reducing communication and control
overheads due to pre determined paths of communication
through clusterheads. One node from each cluster acts as
clusterhead. A clusterhead does all the resource alloca-
tion to all nodes belonging to its cluster e.g. CBRP [8].
Some of the major issues to be handled by a cluster
based routing protocol is the division of a dynamic mo-
bile network into clusters and determination of cluster-
heads for each cluster in the face of highly dynamic and
unstable nature of MANETs [9].
Various cluster based routing schemes have been pro-
posed in the literature. Some examples are:
1) Highest Degree Heuristic: The Highest Degree heu-
ristic uses the degree of a node as a metric for the selec-
tion of clusterheads. The degree of a node is the number
of neighbor nodes. The node with maximum degree is
chosen as a clusterhead. Any tie is broken by the node
identifiers. In this scheme, as the number of ordinary
nodes in a cluster is increased, the throughput drops and
system performance degrades [10].
2) Lowest ID Heuristic: The Lowest Identifier algo-
rithm chooses the node with the minimum identifier (ID)
as a clusterhead. The system performance is better than
Highest Degree heuristic in terms of throughput [10].
However, since this heuristic is biased to choose nodes
with smaller IDs as clusterheads, those nodes with
smaller IDs suffer from the battery drainage, resulting
short lifetime span of the system.
3) Distributed Clustering Algorithm: The Distributed
Clustering Algorithm is a modified version of the Lowest
Identifier algorithm. For each cluster, it chooses a node
with locally lowest ID among all the neighbour nodes as
a clusterhead. Every node can determine its cluster and
transmits only one message during the algorithm [11].
Since it uses nod e ID for the selection of clusterheads, it
inherits the drawbacks of the Lowest Identifier heuristic.
4) Weighted Clustering Algorithm (WCA): The WCA
is based on the use of a combined weight metric that
takes into account several system parameters like the
node-degr ee, distances with all its neighbors, node speed
and the time spent as a clusterhead. Each node obtains
the weight values of all other nodes and information of
other clusterheads in the system through rebroadcasting.
As a result, the overhead induced by WCA is very high.
If a node moves into a region that is not covered by any
clusterhead, then the cluster set-up procedure is invoked
throughout the whole system. This leads to overheads
[10,12].
5) Distributed Weighted Clustering Algorithm: This
algorithm is an enhanced version of WCA to achieve
distributed clustering set up and to extend lifetime span
of the system. This algorithm differs from WCA in
which it localizes configuration and reconfiguration of
clusters and poses restriction on the power requirement
on the clusterheads. This algorithm provides better per-
formance than WCA in terms of the number of reaffilia-
tions, end-to-en d throughput, o verheads during the initial
clustering set up phase, and the minimum lifespan of
nodes [13].
6) Distributed Score Based Clustering Algorithm: In
Distributed Scor e Based Clustering Algorithm (DSBCA)
various important parameters for cluster heads selection
N. CHAUHAN ET AL.
Copyright © 2011 SciRes. WSN
56
are considered. These parameters are battery remaining,
number of neighbors, number of members and stability
of node. Each node calculates its score by using a for-
mula that considers all the above parameters which is
used in selection of clusterhead . This algorithm performs
better than weighted clustering algorithm (WCA) and
distributed weighted clust e ring algorithm (DWCA) [2].
Some other cluster based routing schemes have been
given in [14-18].
3. Proposed Algorithm
In this section we present an improved distributed
weighted clustering algorithm (DWCAIMP). This algo-
rithm can be divided into three phases described as fol-
lows.
3.1. Cluster Formation
Initially each node is assigned a random ID value. It
broadcasts its ID value to its neighbours and builds its
neighbourhood table. Each node calculates its own
weight based on the following factors:
Node connectivity: The number of nodes that can
communicate directly with the given node i.e. that
are in its transmission range.
Battery Power: The power currently left in each
node. The energy is consumed by sending and re-
ceiving of messages.
Mobility: Running average of speed of each node.
If mobility is less, the node is more suitable to be-
come clusterhead.
Distance: Sum of distance of the node from all its
neighbours.
After finding its own weight, each node broadcasts its
weight to its neighbours. If it has maximum weight
among its neighbours, it sets the clhead variable to 1,
otherwise, the clhead variable is set to 0. The node with
maximum weight broadcasts clhead message to other
nodes. On receiving a clhead message, a node checks all
the nodes from which it receives clhead message. The
node with maximum weight becomes the clusterhead of
that node. A node sends a unicast message to the clus-
terheads.
3.2. Mobility
Then we assign a random value between 0 and 1 to each
node and a threshold value is taken. If the random value
assigned to the node is greater than threshold value, the
node becomes mobile, otherwise it remains stationary.
When a node moves from one position to other in the
random manner, its x and y parameters change. For ex-
ample, if a node is to move in east direction, its position
will change as
1; 0;xx yy

The direction and the duration the node moves in a
particular direction is random. On reaching new destina-
tion, it joins the nearest clusterhead .
3.3. Cluster Maintenance
Cluster maintenance is required when a node moves out
of the range of its clusterhead, if a new node is added or
the clusterhead fails. First case has been discussed earlier
in the mobility handling section. In case a new node is
added, it calculates its weight as discussed earlier. How-
ever, even if its weight is more than the clusterhead, it
does not immediately become the clusterhead and instead
chooses the current clu sterhead its clusterhead. Th is is to
reduce unnecessary overhead in selection of the cluster-
head each time a new node is added. In case the cluster-
head fails, the nodes attached to that clusterhead recal-
culate their weights and select new clusterhead with the
maximum weight.
3.4. The Algorithm
The algorithm is described as follows:
3.4.1. Weight Cal c ulation Al gori thm
1) Find connectivity c for each node which is the number
of neighbours of each node.
2) Find the energy remaining, e for each node.
3) Compute the mobility M for each node which is the
running average of the sp eed until the current time t.

22
11
1
1T
vtttt
t
MXXYY
T

1) Compute the sum of di st ances wit h all its nei ghbours,
d for each node.
2) Calculate the combined weight W as
123 4
WwcwewMwd

3.4.2. Clusterhead Selection Algorithm
1) Each node finds its neighbours and builds its neigh-
bourhood table.
2) Each node calculates its weight by calling the wei-
ght calculation algorithm given above.
3) Each node broadcasts its weight to its neighbours. If
it has maximum weight among its neighbours, it sets the
clhead variable to 1, otherwise, the clhead variable is set
to 0.
4) The node with maximum weight broadcasts clhead
message to other nodes.
N. CHAUHAN ET AL.
Copyright © 2011 SciRes. WSN
57
5) On receiving a clhead message a node checks all
the nodes from which it receives clhead message. The
node with maximum weight becomes the clusterhead of
that node.
6) Then we assign a random value between 0 and 1 to
each node and a threshold is taken.
7) If the random value assigned to the node is greater
than threshold value, then set mobile = 1, otherwise 0.
8) If for a node clhead = 1, then set mobile = 0.
9) If mobile = 1, set value of direction randomly. In-
crement or decrement the value of x and y depending
upon the direction to show mobility.
10) In case a new node is added, it calculates its
weight by calling weight calculation algorithm and re-
peats steps 3, 4 and 5.
11) In case clusterhead fails, the algorithm is repeated.
The flowchart for the above algorithm is given in
Figure 1.
4. Simulation and Performance Analysis
In this section we present the performance of the pro-
posed algorithm (DWCAIMP) obtained by simulation
using Omnet++. The measured performance of the pro-
posed algorithm was compared with that of DWCA.
The mobile network model assumed in this project
consists of random number of mobile nodes with each
node having fixed energy and random mobility. The
number of nodes can be determined initially. The trans-
mission range of each node can also be specified and
each node can pass messages to all the nodes in its
transmission range. The mobility has been provided by
assigning a random value to each node. If the value of
random number is greater than some specified value then
the node is mobile otherwise it is stationary. A mobile
node moves to some random direction for random inter-
val and then changes its direction to a new random loca-
tion. New nodes can also randomly be added to the net-
work. Further each node starts with some energy and its
energy decreases each time it passes a message. A node
fails if its whole energy has been consumed. A failed
node is represented as a black node. The network model
is shown in the Figure 2.
4.1. Number of Clusterheads Formed vs Number
of Nodes
Figure 3 depicts the average number of clusters formed
with respect to the total number of nodes in the MANET.
As the node density increases, our algorithm produces
constantly less clusters in comparison with the original
algorithm. As a result, our algorithm gives better per-
formance in terms of the number of clusters when the
Figure 1. Algorithm flowchart.
N. CHAUHAN ET AL.
Copyright © 2011 SciRes. WSN
58
Figure 2. Network model.
Figure 3. Number of clusterheads vs number of nodes.
node density and node mobility in the network are high.
4.2. Number of Control Messages vs Number of
Nodes
Figure 4 shows the overhead of packets generated per
node during the initial clustering set up phase. The over
head increased as the number of nodes increases. Each
node independently chose one of its neighbors with the
highest score to be its cluster head and thus the cluster
head selection was performed in a distributed manner
with most recently gathered information of current state
of the neighbors.
4.3. Number of Reaffiliations vs Number of
Nodes
Figure 5 describes the number of reaffilations that are
done when a node becomes mobile. The nodes become
mobile at a random value so this criteria is rather more
for self evaluation. The purpose of this factor is that the
reaffilations must not exceed the factor which increases
network overhead and fails the meaning of clustering
process.
4.4. Energy Left vs Number of Nodes
Figure 6 shows the total remaining energy in the net-
work. Initial energy is the total energy of all the nodes.
N. CHAUHAN ET AL.
Copyright © 2011 SciRes. WSN
59
Figure 4. Number of control messages vs number of nodes.
Figure 5. Number of reaffiliations vs number of nodes.
Figure 6. Remaining energy vs number of nodes.
As the messages are passed, the energy of a node de-
creases. Our protocol improves the original protocol in
the sense that it reduces the energy consumption. As the
number of nodes increases the number of messages in-
creases and thus the energy consumed also increases.
5. Conclusion and Future Work
In this paper we have proposed a distributed weighted
clustering algorithm by making some modifications and
improvements on existing algorith ms discussed in [2,13].
As demonstrated, our algorithm reduces the clusterhead
formation and control messages overhead thus improving
overall performance and reducing energy utilization.
Since energy utilization is the most important criteria in
cluster based routing schemes, our protocol provides
better results than existing distributed clustering algo-
rithm.
In the future, some new parameters can be added into
weight computation of nodes so as to give even better
performance. Also, in this algorithm, the clusterhead
selection is limited to single ho p neighbors. This protocol
can be extended to includ e multi-hop or k-hop neighb ors.
Since, the protocol has been tested on simulation envi-
ronment, it can be implemented in a real ad-hoc system
to evaluate its performance in real world scenarios.
6. References
[1] C. Perkins and S. Das, “Ad hoc On-Demand Distance
Vector (AODV) Routing,” Network Working Group, July
2003.
[2] S. Adabi, S. Jabbehdari, A. Rahmani and S. Adabi, “A
Novel Distributed Clustering Algorithm for Mobile Ad-
hoc Networks,” Journal of Computer Science, Vol. 4, No.
2, 2008, pp. 161-166. doi:10.3844/jcssp.2008.161.166
[3] F. Baker “An outsider’s view of MANET draft-baker
manet review,” Network Working Group, March 17,
2002.
[4] C. Hendrik, “Routing Information Protocol,” RFC 1058,
The Internet Society, June 1988.
[5] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destina-
tion-Sequenced Distance-Vector Routing (DSDV) for
Mobile Computers,” SIGCOMM’94 Proceedings of the
conference on Communications Architectures, Protocols
and Applications, Vol. 24, No. 4, 1994, pp. 234-244.
[6] D. B. Johnson, D. A. Maltz, Y. C. Hu, “The Dynamic
Source Routing Protocol for Mobile Ad Hoc Networks
(DSR),” Internet Draft, 16 April 2003.
[7] Z. J. Haas, M. R. Pearlman and P. Samar, “The Zone
Routing Protocol (ZRP) for Ad Hoc Networks,” Internet
Draft, July 2002
[8] M. Jiang, J. Li and Y. C. Tay, “Cluster Based Routing
Protocol (CBRP),” draft-ietf- manet-cbrp- spec-01.tx t, IETF,
Internet draft version 01, July 1999.
[9] L. Ramachandran, M. Kapoor, A. Sarkar and A. Ag-
gar-wal, “Clustering Algorithms for Wireless Ad Hoc
Networks,” In Proceeding: Workshop on Discrete Algo-
rithms and Methods for Mobile Computing and Commu-
N. CHAUHAN ET AL.
Copyright © 2011 SciRes. WSN
60
nications, Boston, 2000, pp. 54-63.
[10] M. Chatterjee, S. Das and D. Turgut, “WCA: A Weighted
Clustering Algorithm for Mobile Ad Hoc Networks,”
Journal of Cluster Computing (Special Issue on Mobile
Ad hoc Networks), Vol. 5, 2002, pp.193-204. doi:10.
1023/A:1013941929408
[11] S. Basagni, “Distributed Clustering for Ad Hoc Net-
works” In Proceedings: International Symposium on
Parallel Architectures, Algorithms, and Networks, 1999,
pp. 310-315.
[12] M. R. Brust, A. Andronache and S. Rothkugel, “WACA:
A Hierarchical Weighted Clustering Algorithm Opti-
mized for Mobile Hybrid Networks,” The Third Interna-
tional Conference on Wireless and Mobile Communica-
tions, Guadeloupe, 4-9 March, 2007. doi:10.1109/ICW
MC.2007.93
[13] W. Choi and M. Woo, “A Distributed Weighted Cluster-
ing Algorithm for Mobile Ad Hoc Networks,” Proceed-
ings of Advanced International Conference on Telecom-
munications and International Conference on Internet
and Web Applications and Services, 2006. doi:10.1109/
AICT-ICIW.2006.11
[14] M. E. Elhdhili, L. B. Azzouz and F. Kamoun, “Lowest
Weight: Reactive Clustering Algorithm for Adhoc Net-
works,” Personal Wireless Communications, Vol. 4217,
2006, pp. 135-146. doi:10.1007/11872153_12
[15] Y. Wang, H. R. Chen, X. Y. Yang and D. Y. Zhang,
“WACHM: Weight Based Adaptive Clustering for Large
Scale Heterogeneous MANET,” International Symposium
on Communications and Information Technologies, Syd-
ney, 2008, pp. i-liv.
[16] X. Niu, Z. Tao, G. Wu, C. Huang and Li Cui, “Hybrid
Cluster Routing: An Efficient Routing Protocol for Mo-
bile Ad Hoc Networks,” IEEE International Conference
on Communications, Vol. 8, 2006, pp. 3554-559.
[17] C. R. Lin a nd M. Gerla, “Ad aptive Clustering for Mobile
Wireless Networks,” IEEE Journal on Selected Areas in
Communication, Vol. 15, No. 7, 1997, pp. 1265-1275. doi:
10.1109/49.6229 10
[18] S. K. Dhurandherl and G. V. Singh, “Power Aware Clus-
tering Technique in Wireless Ad Hoc Networks,” Inter-
national Symposium on Ad Hoc and Ubiquitous Comput-
ing, 2006, pp. 75-80. doi:10.1109/ISAHUC.2006.4290
651