Simulator for Energy Efficient Clustering in Mobile Ad Hoc Networks

David C. Wyld, et al. (Eds): CCSEA, SEA, CLOUD, DKMP, CS & IT 05, pp. 191–198, 2012.
© CS & IT-CSCP 2012 DOI : 10.5121/csit.2012.2220
Simulator for Energy Efficient Clustering
in Mobile Ad Hoc Networks
Amit Kumar1
Dhirendra Srivastav2
and Suchismita Chinara3
Department of Computer Science and Engineering,
National Institute of Technology, Rourkela, Orissa, India.
1 Amitkcs036@gmail.com
2 Dheerendra.nitr@gmail.com
3 suchismita@nitrkl.ac.in
ABSTRACT
The research on various issues in Mobile ad hoc networks is getting popular because of its
challenging nature and all time connectivity to communicate. Network simulators provide the
platform to analyse and imitate the working of the nodes in the networks along with the traffic
and other entities. The current work proposes the design of a simulator for the mobile ad hoc
networks that provides a test bed for the energy efficient clustering in the dynamic network.
Node parameters like degree of connectivity and average transmission power are considered for
calculating the energy consumption of the mobile devices. Nodes that consume minimum energy
among their 1-hop neighbours are selected as the cluster heads.
KEYWORDS
Mobile ad hoc networks, Simulator, clustering, energy consumption.
1. INTRODUCTION
Mobile ad hoc networks support the communication among the nodes when they are on the fly.
Mobility of the nodes in and around the network causes frequent change in the network topology.
Thus the change in network topology that is associated with the link failures and creations
perturbs the routing stability. Along with that, the scarce in radio resources and bandwidth,
limited battery power and computing capability pose challenges in MANET scalability and
efficiency [1, 2]. In such scenario, the role of simulator to analyse the various paradigms of the
network plays a vital role. There exist some simulators for such a dynamic network like ns2,
OPNET, Qual Net, GloMo Sim, OMNeT++ etc. To understand the characteristics of a dynamic
network along with the node mobility patterns, the paper presents the design of a simulator for the
mobile ad hoc networks that forms clusters in the network.
In conventional cellular network the mobile nodes communicate directly with the fixed base
station reducing the wireless part of communication to a single hop problem. Thus the mapping of
cellular architecture into peer to peer network leads to the concept of clustering [6]. In such a
virtual cellular architecture (VCA) cluster heads are selected to play the role of base stations of
cellular network. The cluster head along with its one-hop members form the virtual cells retaining
the merits of cellular structure. The process of cluster formation deals with partitioning the
network into logical groups called clusters. The cluster head within each cluster that acts as the

192 Computer Science & Information Technology (CS & IT)
local coordinator for its member nodes also guarantees for faster communication [3]. The cluster
head in every cluster does the resource allocation to the cluster members and lies responsible for
inter-cluster communication.
Cluster heads being the communication hotspots tend to drain its battery power rapidly while
serving its member nodes [8]. Further, energy consumption is a key factor that hinders the deploy
ability of a real ad hoc and sensor network. It is due to the limited life time of the battery powered
devices that motivates intense research into energy efficient design of operating systems,
protocols and hardware devices. The rest of the paper is organized as follows. Section II
describes the work done in the related area. Section III describes the design of the proposed
simulator and the clustering algorithm for the selection of cluster heads. Section IV depicts the
simulation scenarios and the results associated with the algorithm for the cluster formation.
Finally section V concludes the paper.
2. RELATED WORK
Network simulators are used by researchers, developers and engineers to design various kinds of
networks, simulate and then analyze the effect of various parameters on the network performance.
A typical network simulator encompasses a wide range of networking technologies and can help
the users to build complex networks from basic building blocks such as a variety of nodes and
links. Simulation is a technique where a program models the behavior of a network either by
calculating the interaction between the different network entities like nodes, links and packets
using mathematical formulas, or actually capturing and playing back observations from a
production network. Most of the existing simulators are GUI driven. The network parameters
describe the state of the network like node placement and existing links and the events like data
transmissions and link failures etc.
The existing simulators provide the test bed to carry out the implementation of the network
protocols. The simulator GloMoSim is designed using the parallel discrete event simulation
capability provided by a parallel programming language Parsec that support protocols for purely
wireless networks. OMNeT++ is a component based, modular and open-architecture discrete
event simulation framework. Every simulator has its own pros and cons.
The concept of partitioning of the random dynamic network into logical clusters (also called as
the Linked Cluster Architecture LCA) was initially proposed by Baker and Ephremides [7].
The existing one-hop clustering algorithms emphasize either on minimizing number of cluster
heads [1, 2]) in the virtual back bone to reduce the routing delay or maximizing the cluster
stability by un-altering the head nodes [3,7].
A small variation to LCA was proposed by Ephremides, Wieselthier and Baker in [3] as a lowest
ID algorithm. In this algorithm a node having lowest ID among its neighbors is selected as the
head node. It retains its utility as a benchmark for producing reasonably stable cluster control
architecture as discussed by Gerla and Tsai in [1]. However, as node ID is the only deciding
factor for a node to be a cluster head, the lower ID nodes are biased to become the heads all the
time resulting in their faster energy drainage which may perturb the cluster stability .
A modified version of LCA was proposed by Parekh [2] that aims to reduce the number of
clusters in the network. If { }iN represents the set of neighbors of a particular node i , then the
degree of connectivity of i is represented as ii ND = , where iN is the cardinality of{ }iN . A
higher degree of connectivity ensures lower delay in communication through cluster heads. The

Computer Science & Information Technology (CS & IT) 193
mobility of nodes changes the degree of connectivity of the node very frequently which leads to
more number of cluster head reelections as well as link updations resulting poor cluster stability.
A mobility metric based version of lowest ID algorithm MOBIC was proposed by Basu, Khan
and Little [14]. The algorithm uses mobility based metric for calculation of weights of the nodes
by using the ratio of two consecutive signal strengths received by a node to know its relative
motion with respect to its neighbors. When two cluster heads accidentally come within their
transmission range, re-clustering is deferred for Cluster_Contention_Interval (CCI) period as per
the LCC [4] algorithm. Though MOBIC provides a better cluster stability, but the need to collect
relative speed information of a node from its neighbors degrades its performance.
The author in [4,9]) proposed a weight based distributed mobility adaptive algorithm DMAC that
removes the non-mobility assumption of the hosts during clustering setup and maintenance.
However, when two head nodes come within the transmission range of each other; the node with
the lower weight has to resign its role as head and is forced to become the member node of the
node with higher weight.
The combined metric clustering algorithms [5, 10, 12] use some node parameters like running
average, degree of connectivity or mean connectivity, transmission power, available battery
power or consumed battery power to find its suitability as a head. But obtaining so much of
information to compute the combined weight for every node in the network needs a longer frozen
period of motion before the cluster is actually formed. A large number of message exchanges take
place globally to yield the node with lowest weight.
The authors of [16] have proposed a topology adaptive clustering algorithm TACA. As the
network is activated, clusters are formed with the election of volunteer cluster heads. When any
of these volunteer head drains a threshold amount of its battery power then it selects a non-
volunteer head within its own cluster so that it can hand over the responsibilities to the newly
selected head locally. This avoids as much as possible to a global cluster head election procedure
that demands considerable computation and communication overhead.
3. PROPOSED SIMULATOR FOR CLUSTERING ALGORITHM
3.1. Basics of the Simulator
The mobile ad hoc network can be modelled as a unidirectional graph G = (V, L) where V is the
set of mobile nodes and L is the set of links that exist between the nodes. We assume that there
exists a bidirectional link Lij
between the nodes i and j when the distance between the nodes ijd
< ranget (transmission range) of the nodes. In the dynamic network the cardinality of the nodes V
remains constant, but the cardinality of links L changes due to the mobility of the nodes.

.
Figure 1: Simulator for dynamic network depicting the nodes in the network.
Figure 1 depicts the simulator where nodes are randomly deployed in a 100X100 simulation area.
Each node is identified with a unique identifier ID as shown in the figure. The nodes in the
network are allowed to move freely within the network area by following the Random Way Point
Mobility model (RWP) and satisfy the boundary conditions. In the RWP the nodes chooses a
random speed and random direction and moves towards the destination. After reaching the
destination it pauses for a while before selecting another set of speed and direction for the next
movement [RWP]. While moving in the network the nodes establish connectivity with the
neighbor nodes that are within their transmission range.
Figure 2: The simulator after the nodes probed their connectivity with the neighbours.
Figure 2 depicts the links established by the neighbor nodes in the network. The node without
having any links with other nodes is called as the isolated node. In the figure there exists an
isolated node. The links among the nodes may change as the nodes move from their position.

3.2. Selection of Cluster Heads in the Simulator
The proposed work is a modification to the work done by the authors of [16]. The energy efficient
clustering algorithm is a distributed algorithm. It considers the battery power consumed by a node
and its average transmission power utilised for serving its neighbors as the parameters to decide
its suitability for a cluster head. These two parameters are added with different weight factors to
find the weights of the individual nodes.
The steps for finding the cluster heads in the network are described below:
Step 1: Every node probes its neighbors by broadcasting hello packets and receiving
acknowledgements from others. Figure 2 represents the nodes after finding their connectivity in
the network.
Step 2: The nodes calculate the number of neighbors from which it receives the
acknowledgements. This number represents its degree of connectivity |Di| or the cardinality of the
node in graph theory terminology.
Step 3: Compute the average transmission power utilized by a node as:
avP =
iD
Dist∑ where
avP = Average Transmission Power.
Dist = Distance between the node and its one hop neighbors.
Step 4: Compute the weight of the node as
avPconsi
EnergyEW ** βα +=
Where α and β are the weight factors and
avPEnergy = Energy consumed due to the average transmission power utilised.
The algorithm indicates that a node having lowest weight W among its 1-hop neighbors consumes
minimum battery power and utilises minimum transmission power to serve the neighbors. So this
node is selected as the cluster head and its 1-hop uncovered neighbors (i.e. whose role is not yet
decided) become the cluster members of the selected head. The set of covered nodes are
exempted from taking part in subsequent selection procedure and this process is repeated till all
the nodes are assigned with their role either as a head or a member. The example of cluster setup
phase of the proposed algorithm is demonstrated with the help of Figure 3.

Figure 3: Cluster heads are identified in the simulator.
Figure 4 represents the simulator showing the degree of connectivity, average transmission power
and the energy consumed by every node in the network. This table gets updated with the
occurrence of changes in the network scenario.
Figure 4: Simulator depicting the connectivity, energy consumed by the nodes.
4. CONCLUSIONS
A network simulator is a software program that predicts the behaviour of a network without the
actual network being present. In simulators, the computer network is typically modelled with
devices, traffic etc and the performance is analysed. Typically, users can then customize the

simulator to fulfill their specific analysis needs. The proposed simulator is developed to
implement a distributed clustering algorithm for ad hoc networks. A node that consumes
minimum energy among its one-hop neighbors is selected as the cluster head. The heads get
changed as their weights change in the network. The change in the network scenario is reflected
in the table for ready reference.
REFERENCES
[1] M.Gerla and J.T.C.Tsai, “multicluster, mobile,multimedia radio network”, wireless networks,
1,3,pp.255-265,1995.
[2] A. K. Parekh, “Selecting routers in ad hoc wireless network”, Proceedings of the SBT/IEEE
international telecommunication symposium, August 1994.
[3] D.J.Baker, J.E.Wieselthier and A. Ephremides, “A design concept for reliable mobile radio networks
with frequency hoping signaling”, proceedings of IEEE, vol. 75, no.1, Jan. 1987.
[4] S.Basagni, “Distributed and mobility-adaptive clustering for multimedia support in multi-hop wireless
networks”, proceedings of vehicular technology conference, VTC, vol.2, pp. 889-893, 1999.
[5] S.Das, M.Chatterjee, 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, no. 2, 4, pp. 193-204,
2002.
[6] S. Basagni, I. Chlamtac, A. Farago, “A generalized clustering algorithm for peer-to-peer networks”,
Proceedings of Workshop on Algorithmic aspect of communication (satellite workshop of ICALP),
July 1997.
[7] D.J.Baker and A. Ephremides, “The architectural organization of a mobile radio network via a
distributed algorithm”, IEEE Transactions on Communications COM-29, pp. 1694-1701,
11(Nov.1981).
[8] J.H.Chang and L.Tassiulas, “Energy conserving routing in wireless ad hoc networks”, Proceedings of
INFOCOM 2000, Tel-Aviv, Israel, March 2000.
[9] S. Basagni,“Distributed clustering for ad hoc networks”, Proceedings of International Symposium on
Parallel Architectures, Algorithms and Networks, pp.310–315, June 1999.
[10] S.Das, M.Chatterjee, D.Turgut, “An on demand weighted clustering algorithm(WCA) for ad hoc
networks”, in proceedings of IEEE GLOBECOM 2000, pp.1697-1701, San Francisco, Nov. 2000.
[11] T. Ohta, S. Inoue, Y. Kakuda, “An adaptive clustering scheme for highly mobile ad hoc networks”, in
proceedings of sixth international symposium on autonomous decentralized systems(ISADS’03), April
2003.
[12] Wei-dong Yang and G-z Zhang, “A weight-Based Clustering Algorithm for mobile Ad Hoc
Network”, proceedings of Third International Conference on Wireless and Mobile Communication
(ICWMC’07), 2007.
[13] S. Basagni, M. Conti, S. Giordano and I. Stojmenovic, Mobile ad hoc networking, A John Wiley &
Sons Inc. publication, 2004.
[14] P. Basu, N. Khan and T.D.C. Little, “A mobility based metric for clustering in mobile ad hoc
networks”, Proceedings of IEEE ICDCS 2001 workshop on wireless networks and mobile computing,
Phoenix, AZ, 2001.

[15] R. Ghosh and S. Basagni, “ Limiting the impact of mobility on ad hoc clustering”, Proceedings of the
2nd ACM international workshop PE-WASUN ’05, Montreal, CA, pp. 197--204, 2005.
[16] Suchismita Chinara and Santanu Kumar Rath, “Taca: A Topology Adaptive Clustering Algorithm for
Mobile Ad Hoc Networks” , Proceedings of WORLDCOMP International Conference on Wireless
Networks (ICWN ’09), July 14th
-17th
, Las Vegas, USA, pp. 391-397, 2009.
Authors
Amit Kumar is persuing his B. Tech degree in Computer Science Engineering in the
National Institute of Technology Rourkela. The current work is a part of his thesis work
carried out in his final year.
Dhreendra Kumar is persuing his B. Tech degree in Computer Science Engineering in
the National Institute of Technology Rourkela. The current work is a part of his thesis
work carried out in his final year.
Suchismita Chinara is working as an Assistant Professor in the Department of
Computer Science Engineering at National Institute of Technology Rourkela. Her area
of interest includes wireless networks.

Simulator for Energy Efficient Clustering in Mobile Ad Hoc Networks

Recommended

More Related Content

What's hot (19)

Similar to Simulator for Energy Efficient Clustering in Mobile Ad Hoc Networks (20)

More from cscpconf (20)

Recently uploaded (20)

Simulator for Energy Efficient Clustering in Mobile Ad Hoc Networks