# Mobility Aware Energy Efficient Clustering for MANET: A Bio-Inspired Approach with Particle Swarm Optimization

Authors: Naghma Khatoon; Amritanjali
Journal: Wireless Communications and Mobile Computing
 (2017)

---

## Abstract

Mobility awareness and energy efficiency are two indispensable optimization problems in mobile ad hoc networks (MANETs) where nodes move unpredictably in any direction with restricted battery life, resulting in frequent change in topology. These constraints are widely studied to increase the lifetime of such networks. This paper focuses on the problems of mobility as well as energy efficiency to develop a clustering algorithm inspired by multiagent stochastic parallel search technique of particle swarm optimization. The election of cluster heads takes care of mobility and remaining energy as well as the degree of connectivity for selecting nodes to serve as cluster heads for longer duration of time. The cluster formation is presented by taking multiobjective fitness function using particle swarm optimization. The proposed work is experimented extensively in the NS-2 network simulator and compared with the other existing algorithms. The results show the effectiveness of our proposed algorithm in terms of network lifetime, average number of clusters formed, average number of reclustering required, energy consumption, and packet delivery ratio.


---

## Body

## 1. Introduction

With the advancement of many nature inspired techniques for different optimization problems, researchers are motivated to develop solutions for two important optimization problems in MANET, that is, clustering and routing. There are various applications of bio-inspired computing and the need of all these algorithms is for optimization problems. Each possible solution in an optimization algorithm is derived in two ways, that is, deterministic and stochastic. All deterministic algorithms are generally covered by a certain mathematical formula and the search proceeds in only one direction; that is, these are unidirectional searches guided by certain rules. The stochastic algorithms are nontraditional algorithms to solve multimodal problems having many optima. Particle swarm optimization (PSO) is a robust stochastic optimization technique based on the movement and intelligence of swarms, that is, group (birds flocking or fish schooling) [1, 2]. In this paper, PSO has been used for optimizing the multiobjective problem of clustering in MANET.A mobile ad hoc network [3] is an autonomous system in which multiple hosts are connected with each other using multihop wireless links (Figure 1). This is a networking system that does not depend on a permanent backbone or fixed infrastructure and consists of devices on fly that are deployed for some specific applications. Such networks are most suitable in situations where infrastructure is not available or deployment of infrastructure is not cost effective like search and rescue operations, disaster recovery, military services, and communication between vehicles and roadside equipment as vehicular ad hoc networks (Figure 2). However, the management of such networks is difficult due to its self-configuring nature and absence of any central authority [4]. Furthermore, scalability is another issue which in last decades becomes one of the most focused on areas of communication research world. Clustering is an important approach which solves many problems of MANET and provides network scalability and increases its lifetime. Here nodes are divided into virtual groups called clusters with a cluster head (CH) in each cluster, which serves as a local coordinator for its cluster (Figure 3). Communication from source to destination is done via CHs and gateway nodes which are within the transmission range of more than one CH and, thus, conserve the energy of other nodes. Also cluster based MANETs improve network management as route setup is localized with clusters and so reduce the routing table of other nodes. However, CHs bear the extra work load of intracluster and intercluster transmission. This results in early depletion of energy and death of CHs which ultimately partition the network and degrade network lifetime. And also, as the mobility of nodes is the major cause of link failure, so, in a clustering scheme, particularly the situation when a selected CH is comparatively more mobile than other nodes, it will frequently dissolve a well formed cluster and require a new intercluster path setup from source to destination or in worst situation there is a need for reclustering. This recurrent link failure due to the movement of CHs accelerates the routing overheads and degrades the reliability of data transmission because in both situations there is an increase in control message overheads resulting in reducing the effectiveness and overall the network lifetime. Thus, designing an efficient clustering algorithm with minimum overhead becomes a good approach to increasing the network lifetime of the MANET.Figure 1
A mobile ad hoc network.Figure 2
MANET applications.Figure 3
An illustration of clusters in MANET.In this paper, we develop CH selection and cluster formation algorithms inspired from the natural social behavior as well as the dynamic movements with communication of insects and birds. The CH selection algorithm takes care of the selection of the most eligible nodes to act as CHs from the set of nodes which retain their connectivity with other nodes for longer duration of time. For this, we considered the direction of mobility of nodes along with the other selection parameters, that is, the degree of connectivity, the energy required to communicate with all the neighbors, and the level of energy depleted. The cluster formation algorithm defines a new fitness function based on the strength of CHs and the average distance of nodes to its corresponding CHs. For cluster formation, a bio-inspired PSO search technique is used which is a robust stochastic optimization technique based on the movement and intelligence of the swarm. It uses a number of agents called particles that constitute a swarm, moving around in the search space looking for the best solution. Each particle is nothing but a probable solution of a problem which adjusts its flying according to its own flying experience as well as the flying experience of other particles. Depending upon the fitness function derived for our proposed algorithm, a node gets affiliated to a CH from the set of CHs within its transmission range, which has the maximum fitness value, that is, a CH having maximum strength and minimum average distance with its neighbors. The main contributions of our proposed mobility aware energy efficient clustering based on particle swarm optimization (ME-PSO) are as given as follows:(i)
increasing the stability of clusters by taking care of node’s mobility as well as their direction of motion while deciding CHs;(ii)
deriving fitness function of particles on the basis of the strength of CHs as well as the average distance of cluster members with their respective CHs which increases the lifetime of both CHs and cluster members;(iii)
PSO based clustering which effectively balanced loads on CHs;(iv)
simulation results which show the efficacy of the proposed algorithm over other existing algorithms in terms of different performance parameters.The rest of the paper is organized as follows. A brief survey of related works on clustering algorithms is presented in Section2. In Section 3 we described the system model, including energy model, stability model, and an overview of PSO with some general terminologies used for our proposed algorithm. Section 4 gives description of the proposed algorithm. An explanatory example is given in Section 5. Section 6 presents the simulation results which show the effectiveness of the proposed algorithm. Finally, in Section 7, we conclude the paper and presented some directions for future work.


## 2. Related Works

We have reviewed several approaches of clustering and routing protocols developed for ad hoc networks [5–21]. Many approaches have been proposed to cope with the limitations of mobility and battery dependency of mobile nodes in MANETs. Bokhari et al. in their paper [5] presented a classification of clustering techniques as applied in MANETs that minimizes the energy consumption by nodes which is one of the major concerns for wireless ad hoc networks and overall improved the power consumption and battery usage. Although single metric CH selection algorithms are simple with less overhead, they are entirely dependent on the single parameter without taking into consideration the other eligibility qualifications of nodes to become a CH. Chatterjee et al. have proposed a novel weight based clustering algorithm (WCA) for MANETs [6]. They considered a combined weight of more than one parameter, that is, degree of connectivity, mobility, time till a node acts as a CH, and the sum of distances to a node’s neighbors for electing CHs. This algorithm is the basis for all weight based clustering approaches that consider many parameters for CH election. However, there are certain factors which reduce the efficiency of WCA like how, each time, execution of the setup phase on a node’s movement unnecessary dissolves a well formed cluster and lack of node’s stability. Choi and Woo [7] have presented a distributed weighted clustering algorithm (DWCA) for MANET which restrains configuration and reconfiguration of clusters and constraints on CHs in terms of power requirement. However, there are no parameters which define the stability of nodes while deciding CHs. In [8], a new enhanced version of the weighted clustering algorithm has been proposed called Enhancement on Weighted Clustering Algorithm (EWCA). The parameters used for the selection of CHs are transmission power, transmission range, mobility, and battery energy. Here, the average number of cluster formation instances is reduced by avoiding the dynamic change of CHs. EWCA takes care of load balancing and improves stability of clusters in MANET.Furthermore, with the proliferation of evolutionary and bio-inspired computing in different research areas, it becomes a good approach for optimized network partitioning and route establishment in wireless networks. Many deterministic and stochastic algorithms have been developed in recent years for such networks [22–35]. All the algorithms based on the gradient method are deterministic as they are hard computing based on a certain mathematical formula that cannot be changed. Stochastic algorithms are multimodal problem search in many directions inspired by biological creatures. Rajan et al. in their paper [22] have presented an overview of different bio-inspired population based metaheuristic algorithms for optimization problems in ad hoc networks. In [23], the authors have proposed a breadth-first search tree (BFS) based clustering algorithm for selection of minimal loaded CHs and affiliation of nodes to them. In [24], a Genetic Algorithm (GA) optimization technique has been developed which mimics the Darwinian theory of the survival of the fittest. In [25], the authors have developed a GA based load balanced clustering for wireless sensor networks (WSN) where the maximum loads on gateway nodes are minimized and nodes are affiliated to them forming load balanced clusters. Keerthipriya and Latha [26] have presented an adaptive cluster formation in MANET using particle swarm optimization (A-PSO). The authors have used different parameters for CH election which make stable clusters. However, the mobility of nodes is not handled with effectiveness. Also, PSO is used to find out efficient CHs with no focus on optimization in the clustering process. In [27], an energy efficient routing protocol for MANET has been developed based on the particle swarm optimization approach. Here the routing issue of MANET is formulated as an optimization problem and developed a new fitness function based on route length and route energy level. They used binary PSO (BPSO) for optimizing TORA routing protocol for MANET. In [28], the authors have developed an energy efficient clustering and routing algorithm where they considered both energy efficiency and load balancing while designing linear and nonlinear programming problems based on PSO. In [29], the authors have proposed clustering in MANET using comprehensive learning particle swarm optimization (CLPSO). In this, the parameters considered for CH selection are almost the same as that in WCA without taking the direction of motion of nodes in consideration when deciding the stability of CHs.In our proposed work we have developed a mobility aware energy efficient clustering for MANET based on the particle swarm optimization approach (ME-PSO). Here the main contribution of our work is to consider the direction of mobility of nodes while selecting a CH as well as its energy which are the two main challenges of the MANET. Also, we develop a new fitness function for cluster formation which is based on the strength of CHs and the average distance of non-cluster head members to its corresponding CHs. This fitness function ensures the affiliation of nodes to a CH having maximum strength with least deviation from stability and the nodes having least average distance with their respective CHs. This certainly increases the network lifetime as well as balancing loads on CHs.


## 3. System Model and Terminologies

We assume a MANET model consisting of mobile nodes deployed within a fixed area that move randomly in any direction. Once deployed, nodes are assigned with unique IDs. Each node becomes aware of its neighboring nodes by broadcasting its ID using the carrier-sense multiple access with collision avoidance (CSMA/CA) MAC layer protocol and receiving the same from the neighboring nodes. This process is called bootstrapping by which each node maintains its own neighbor information table. The transmission among them started over wireless links which are established only when nodes are within the transmission range of each other. We have used the following common terminologies to formulate our proposed work:(i)
LetN={n1,n2,…,nl} be the set of mobile nodes.(ii)
Ψ={ch1,ch2,…,chm} is the set of elected CHs such that l>m.(iii)
Trangecha is the transmission range of a CH cha.(iv)
W(ni) is the weight of a node ni.(v)
N(ni) is the cardinality of a node ni.(vi)
dist(ni,nj) is the Euclidean distance between nodes ni and nj.(vii)
S(cha) is the strength of a CH cha.


### 3.1. Energy Model

The energy model represents mobile node’s attribute in a wireless network. The energy consumption model used for our proposed algorithm is the basic energy model determined by the Class Energy Model in NS2 [36] used to assess node’s energy during simulation. The different attributes used are initialEnergy, rxPower, txPower, sleepPower, and idlePower representing the energy of a node in the beginning, energy consumed in receiving one packet, energy consumed in transmitting one packet, energy consumed in sleep state, and energy consumed in idle state, respectively. Energy consumption of a node ni at time interval Δt is given by(1)Econsni,Δt=Eresidualni,t0-Eresidualni,t1,where Eresidualni,t0 and Eresidualni,t1 represent residual energy of node ni at time t0 and time t1, respectively.


### 3.2. Stability Model

To select the most eligible nodes to act as CHs from an ordinary set of nodes, combined weights of different parameters are used. Mobility leads to more CH reelection as well as link updating which results in poor cluster stability. Thus, for making stable clusters, it is essential to consider the mobility of the nodes. The transmission range of a node (say)ni forms a circle with radius r consisting of (say) k nodes. Inside the circle, the neighboring nodes of ni can exist either closer to ni or far away, but within the transmission range of ni. Accordingly, we can divide the transmission zone of ni as trusted zone or risked zone [37]. The inner circle with radius α1r forms the trusted zone and the zone having width r(α2-α1) forms the risked zone as shown in Figure 4. The coefficients α1 and α2 are suitably selected based on the mobility of nodes in the network.Figure 4
Transmission range zones with direction of mobility.In order to decide how well suited a node is to behave as a CH, we take its relative mobility and distances with neighbors and the number of neighbors in its direct communication range. We calculate the relative mobility based on the received signal strength between two successive “HELLO” packets which is inversely proportional to the distance between the sender and the receiver. The relative mobility at nodeni with respect to node nj, MniRelnj, is calculated as(2)MniRelnj=10log10⁡RxPrnj→ninewRxPrnj→niold,where RxPrnj→ninew is the new and RxPrnj→niold is the old receiving power of the “HELLO” packet from node nj to node ni. In the case when RxPrnj→ninew<RxPrnj→niold, MniRelnj is negative; it means nj is moving away from ni as shown in Figure 4. When RxPrnj→ninew>RxPrnj→niold, MniRelnj is positive; that is, nj is coming closer to ni.For each neighboring node,nj, of node ni, we find its range indicator RIndnj,ni with respect to ni. On the basis of the distance between the nodes and its relative mobility, we categorize it as follows:(3)RIndnj,ni=0,ifα1r<dist⁡ni,nj≤α2r∧MniRelnj<01,if  distni,nj≤r∧MniRelnj>01+dist⁡ni,nj-α1rα2-α1r,if  distni,nj≤α1r∧MniRelnj<0.If a node is in risked zone and its mobility is negative, then it is moving away from the node which is calculating its weight to be selected as a CH. Such neighboring node is discarded as it will get away from the transmission range of the concerned node. If a node is anywhere within the transmission range and its relative mobility is also positive, it means that the node is coming closer to the node calculating its weight. In the third situation when a node is in trusted zone, but is moving away, then the priority of the node is reduced in the proportion of the distance as shown in (3). Finally, we calculate the stability deviation of node ni(STDni) as the summation of range indicators multiplied by the distance (distni,nj) and the whole divided by its cardinality of nodes (N(ni)) as given below (4)STDni=∑j=1kRIndnj,ni×distni,njNni.


### 3.3. Particle Swarm Optimization: An Overview

Particle swarm optimization is one of the recent multiagent stochastic parallel search techniques which apply the concept of social interaction to problem solving. It uses a number of particles (agents) that constitute a swarm (group) of predefined size,Np, moving around in the search space of say D dimension looking for the best solution. Each particle Pi,  1≤i≤Np, is nothing but a probable solution, having a fitness value which is evaluated by the fitness function to be optimized and have position Xi,d,  1≤d≤D, and velocity Vi,d is treated as a point in D-dimensional search space which adjusts its flying according to its own flying experience, called personal best (Pbesti), as well as the flying experience of other particles, that is, global best (Gbest). The different steps of PSO algorithm are given in Figure 5.Figure 5
Flowchart of particle swarm optimization.Each particle tries to modify its position using the following information and in each iteration updates its velocity and position using (5) and (6), respectively:(i)
The current position(ii)
The current velocity(iii)
The distance between the current position and Pbesti(iv)
The distance between the current position and Gbest.(5)Vi,dt+1=ω×Vi,dt+c1×rand1×Xpbesti,d-Xi,dt+c2×rand2×Xgbestd-Xi,dt,(6)Xi,dt+1=Xi,dt+Vi,dt.Here, ω is the inertial weight, c1, c2 are constants for acceleration factors, and rand1 and rand2 are random numbers between 0 and 1. The iteration goes on until some termination condition, that is, fixed number of iterations or adequate Gbest value, is obtained.


## 3.1. Energy Model

The energy model represents mobile node’s attribute in a wireless network. The energy consumption model used for our proposed algorithm is the basic energy model determined by the Class Energy Model in NS2 [36] used to assess node’s energy during simulation. The different attributes used are initialEnergy, rxPower, txPower, sleepPower, and idlePower representing the energy of a node in the beginning, energy consumed in receiving one packet, energy consumed in transmitting one packet, energy consumed in sleep state, and energy consumed in idle state, respectively. Energy consumption of a node ni at time interval Δt is given by(1)Econsni,Δt=Eresidualni,t0-Eresidualni,t1,where Eresidualni,t0 and Eresidualni,t1 represent residual energy of node ni at time t0 and time t1, respectively.


## 3.2. Stability Model

To select the most eligible nodes to act as CHs from an ordinary set of nodes, combined weights of different parameters are used. Mobility leads to more CH reelection as well as link updating which results in poor cluster stability. Thus, for making stable clusters, it is essential to consider the mobility of the nodes. The transmission range of a node (say)ni forms a circle with radius r consisting of (say) k nodes. Inside the circle, the neighboring nodes of ni can exist either closer to ni or far away, but within the transmission range of ni. Accordingly, we can divide the transmission zone of ni as trusted zone or risked zone [37]. The inner circle with radius α1r forms the trusted zone and the zone having width r(α2-α1) forms the risked zone as shown in Figure 4. The coefficients α1 and α2 are suitably selected based on the mobility of nodes in the network.Figure 4
Transmission range zones with direction of mobility.In order to decide how well suited a node is to behave as a CH, we take its relative mobility and distances with neighbors and the number of neighbors in its direct communication range. We calculate the relative mobility based on the received signal strength between two successive “HELLO” packets which is inversely proportional to the distance between the sender and the receiver. The relative mobility at nodeni with respect to node nj, MniRelnj, is calculated as(2)MniRelnj=10log10⁡RxPrnj→ninewRxPrnj→niold,where RxPrnj→ninew is the new and RxPrnj→niold is the old receiving power of the “HELLO” packet from node nj to node ni. In the case when RxPrnj→ninew<RxPrnj→niold, MniRelnj is negative; it means nj is moving away from ni as shown in Figure 4. When RxPrnj→ninew>RxPrnj→niold, MniRelnj is positive; that is, nj is coming closer to ni.For each neighboring node,nj, of node ni, we find its range indicator RIndnj,ni with respect to ni. On the basis of the distance between the nodes and its relative mobility, we categorize it as follows:(3)RIndnj,ni=0,ifα1r<dist⁡ni,nj≤α2r∧MniRelnj<01,if  distni,nj≤r∧MniRelnj>01+dist⁡ni,nj-α1rα2-α1r,if  distni,nj≤α1r∧MniRelnj<0.If a node is in risked zone and its mobility is negative, then it is moving away from the node which is calculating its weight to be selected as a CH. Such neighboring node is discarded as it will get away from the transmission range of the concerned node. If a node is anywhere within the transmission range and its relative mobility is also positive, it means that the node is coming closer to the node calculating its weight. In the third situation when a node is in trusted zone, but is moving away, then the priority of the node is reduced in the proportion of the distance as shown in (3). Finally, we calculate the stability deviation of node ni(STDni) as the summation of range indicators multiplied by the distance (distni,nj) and the whole divided by its cardinality of nodes (N(ni)) as given below (4)STDni=∑j=1kRIndnj,ni×distni,njNni.


## 3.3. Particle Swarm Optimization: An Overview

Particle swarm optimization is one of the recent multiagent stochastic parallel search techniques which apply the concept of social interaction to problem solving. It uses a number of particles (agents) that constitute a swarm (group) of predefined size,Np, moving around in the search space of say D dimension looking for the best solution. Each particle Pi,  1≤i≤Np, is nothing but a probable solution, having a fitness value which is evaluated by the fitness function to be optimized and have position Xi,d,  1≤d≤D, and velocity Vi,d is treated as a point in D-dimensional search space which adjusts its flying according to its own flying experience, called personal best (Pbesti), as well as the flying experience of other particles, that is, global best (Gbest). The different steps of PSO algorithm are given in Figure 5.Figure 5
Flowchart of particle swarm optimization.Each particle tries to modify its position using the following information and in each iteration updates its velocity and position using (5) and (6), respectively:(i)
The current position(ii)
The current velocity(iii)
The distance between the current position and Pbesti(iv)
The distance between the current position and Gbest.(5)Vi,dt+1=ω×Vi,dt+c1×rand1×Xpbesti,d-Xi,dt+c2×rand2×Xgbestd-Xi,dt,(6)Xi,dt+1=Xi,dt+Vi,dt.Here, ω is the inertial weight, c1, c2 are constants for acceleration factors, and rand1 and rand2 are random numbers between 0 and 1. The iteration goes on until some termination condition, that is, fixed number of iterations or adequate Gbest value, is obtained.


## 4. Proposed Algorithm

The main objective of the proposed method is to prolong the network lifetime of MANET by considering mobility as well as energy of mobile nodes which are two important challenging issues. For this we have implemented clustering approach with a bio-inspired particle swarm optimization technique for cluster formation. The network setup is performed in two phases of CH election and cluster formation. The details of these steps are given in the following subsections.


### 4.1. Cluster Head Election

In order to decide how much a node is capable of becoming a CH, it is a better choice to use its mobility, distances with all its neighbors, degree of connectivity, and the amount of energy depleted by it. The first three parameters are combined to form the formula of stability deviation as given in (4). In order to increase the lifetime of a CH, a node with less stability deviation and which depleted less energy is chosen to act as a CH.On the basis of stability deviation and energy depletion, the combined weight is calculated in (7). Here W1 and W2 are the weighing factors such that W1+W2=1, the values of which are selected depending on the network scenario. (7)Wni=W1×STDni+W2×EDni.A node which is less deviated from stability and depleted less energy is a good candidate to become a CH.Thus, a node with minimum weight among all its neighbors will declare itself as a CH and broadcast a CH advertisement message to all its neighboring nodes as given in Algorithm1.Algorithm 1:CH election algorithm.
Input: A set of nodes, N={n1,n2,…,nl}, weighing
factors w1 and w2.
Output: A set of elected CHs, Ψ={ch1,ch2,…,chm}.
Begin:
Step
1: for  i=1tol∀ni∈N  do
(1.1) each node ni broadcast and receive
“HELLO” message to and from all its one
hop neighbors.
(1.2) estimate the total number of one hop
neighbors.
(1.3) find STD(ni) and ED(ni).
(1.4) calculate weight, W(ni) using Equation (7)
and broadcast it to all its one-hop neighbors.
Step
2: set flag = 1
Step
3: while (flag==1∧ni is receiving W(nj)∀nj∈Trangeni) do
(3.1) if  W(nj)<W(ni)  then
(3.2) ni gives up the competition for CH election
(3.3) set flag = 0
end if
end while
Step
4: if (flag == 1) then
(4.1) ni declare itself as CH and broadcast CH
advertisement message with its ID and
weight, W(ni) to nj∀nj∈Trange(ni)
(4.2)elseni is an isolated node, so declare and
advertise itself as a CH after timeout.
end if
Stop.


### 4.2. PSO Based Cluster Formation

After the selection of CHs, we now present our proposed PSO based clustering in MANET. It consists of initialization of a swarm of particles, evaluation of fitness function and accordingly the velocity and position of particles are updated depending upon the range of search dimension. Hence, the position and velocity of the particles are governed by its present velocity, its self-progression factor, and the social interaction factor as shown in (5) and (6).


#### 4.2.1. Swarm Particle Initialization

Particles are initialized in a dimension equal to the number of nodes in MANET leaving the set of elected CHs; that is,Pi is a set for i=1,2,…,K, where K is the total number of non-cluster head nodes; that is, K=N-Ψ. A particle Pi of generation G is initialized with a randomly generated number in the range of 0 and 1; that is, 0<rand(0,1)≤1 and are independent for different components of particle Pi.


#### 4.2.2. Evaluation of Fitness Function

The performance of each particle is measured using a fitness function which is application dependent. For our proposed algorithm the fitness function is based upon two objectives, that is, to maximize the strength of CHs and simultaneously minimize the intracluster distance between nodes and their respective CHs described as follows.(a) Optimizing the Strength of CH. One of the main objective functions of our proposed PSO based clustering is to optimize the strength of CHs. This is one of the most important requirements in order to achieve stability of clusters in MANET. It should be noted that the mere selection of the most eligible nodes to act as CHs does not ensure the effectiveness of clustering in such networks where data transmission from source to destination is done via CHs. Unequal distribution of loads on CHs results in early depletion of energy of heavily loaded CHs. The death of a CH results in link failure which causes an overhead of control messages in either selection of new CH or reclustering. Hence, the clustering effectiveness should also depend upon how nodes are affiliated to a CH to form well-structured clusters. We, therefore, have considered the strength of CHs as the first optimizing parameter. It depends upon the residual energy of a CH and its stability deviation. A CH having comparatively high residual energy which is least deviated from stability is said to have good strength. Thus, our first objective is to maximize the minimum strength of a CH calculated as follows:(8)Scha=EresidualchaSTDcha,where Scha is the strength of a CH cha, Eresidualcha is the remaining battery energy, and STDcha is the stability deviation of cha calculated using (4) described above. Therefore,(9)Objective1:MaximizeS=min⁡Scha∣∀cha∈Ψ.Hence, the fitness function is directly proportional to the value of S.That is,(10)Fitness∝S.(b) Optimizing the Intracluster Distance between Nodes and Their Respective CHs. Our second objective of the PSO based clustering is to minimize the intracluster distance between nodes and their respective CHs. The attenuation of signal strength is one of the characteristics of wireless channel which is directly proportional to the distance between the transmitter and receiver. The generally used model of power attenuation is given by(11)PRecd=PTransdβ.Here, PRecd is the received signal amplitude from a sender at a distance of d from the receiver, PTrans is the strength of the transmitted signal, d is the distance between transmitter and receiver, and β is the path loss factor [38]. When the distance from the nodes to their respective CHs increases, they need to exhaust more energy to communicate with their CHs. As the rate of energy depletion increases such nodes die quickly, resulting in degradation of network lifetime. So, focus should be given to assigning a node to the nearest CH from the set of CHs within its transmission range so as to minimize the energy consumption for intracluster transmission. We therefore have considered our second objective to be minimizing the average distance between nodes and their respective CHs. The average distance is calculated as follows: (12)AvDist=∑i=1kdistni,chak∀ni∈Trangecha∧cha∈Ψ,where |k| is the cardinality of all nodes that belong to the transmission range of cha(Trangecha) and Ψ is the set of elected CHs.Therefore,(13)Fitness∝1AvDist,(14)Objective2:MinimizeAvDist.Combining (10) and (13), it means that (15)Fitness∝SAvDist.That is,(16)Fitness=K×SAvDist,where K is the proportionality constant, the value of which can be assumed to be 1.Therefore,(17)Fitness=SAvDist.Thus, the objective of the PSO based clustering is to maximize the fitness value given in (17). The more the fitness value of a particle is, the more the compact clusters with optimum CHs are created with the constraints that a node can be assigned to one and only one CH and it should be within the transmission range of the CH.This ultimately will increase the lifetime of the CHs and also the lifetime of non-cluster head members and so increases the overall network lifetime. Each particle periodically updates the Pbest and Gbest value after evaluating its fitness function.


#### 4.2.3. Update Velocity and Position of Particles

Particles, after evaluating their fitness function, calculate their velocity and position using (5) and (6), respectively. The velocity and position are updated after each iteration and the solution moves ahead towards the best possible result. The iteration continues and each time the particle’s current fitness value is compared with its personal best value. On achieving better fitness, the personal best, Pbesti, is replaced by the current value. Also, the global best, Gbest, is updated on getting the global best fitness. The update in velocity and position continues until a termination criteria is satisfied. We make the number of iterations as the termination criteria for the proposed work (Algorithm 2). After the completion of the clustering algorithm, nodes are assigned to their respective optimized CHs and are minimally distant away from their respective CHs achieving more compact and balanced clusters.Algorithm 2:PSO based cluster formation algorithm.
Input:  (1) A set of nodes  N={n1,n2,…,nl}. (2) a set of elected
CHs Ψ={ch1,ch2,…,chm}. (3) swarm size  Np.
Output:  An assignment A:n→Ψ with maximized objective function.
Begin:
Step
1: Initialize swarm particles Pi∀Pi∈Np∧1≤i≤Np
Step
2: fori=1toNp  do
(2.1) Find  Fitness(Pi) using Equation (17)
(2.2) set  Pbesti=Pi
end
Step
3: ifFitnessPbestj=max⁡{FitnessPbesti∀i:1≤i≤Np}
set Gbest = Pbestj
end if
Step
4:while  (Not Terminate) do
for  i=1  to  Np  do
(4.1) Each particle  Pi  update its velocity and position using
Equations (5) and (6) respectively.
(4.2) Find new  Fitness(Pi)  using Equation (17)
(4.3) if  Fitness(Pi)>Fitness(Pbesti)  then
(4.4) set  Pbesti=Pi
end
(4.5) if  Fitness(Pbesti)>Fitness(Gbest)  then
(4.6) set  Gbest=Pbesti
end
end
end
Step
5: Assign node  ni∀i∈N  to the CH  cha∀a∈Ψ  in its
transmission range with maximum fitness value i.e Gbest.
Stop.


## 4.1. Cluster Head Election

In order to decide how much a node is capable of becoming a CH, it is a better choice to use its mobility, distances with all its neighbors, degree of connectivity, and the amount of energy depleted by it. The first three parameters are combined to form the formula of stability deviation as given in (4). In order to increase the lifetime of a CH, a node with less stability deviation and which depleted less energy is chosen to act as a CH.On the basis of stability deviation and energy depletion, the combined weight is calculated in (7). Here W1 and W2 are the weighing factors such that W1+W2=1, the values of which are selected depending on the network scenario. (7)Wni=W1×STDni+W2×EDni.A node which is less deviated from stability and depleted less energy is a good candidate to become a CH.Thus, a node with minimum weight among all its neighbors will declare itself as a CH and broadcast a CH advertisement message to all its neighboring nodes as given in Algorithm1.Algorithm 1:CH election algorithm.
Input: A set of nodes, N={n1,n2,…,nl}, weighing
factors w1 and w2.
Output: A set of elected CHs, Ψ={ch1,ch2,…,chm}.
Begin:
Step
1: for  i=1tol∀ni∈N  do
(1.1) each node ni broadcast and receive
“HELLO” message to and from all its one
hop neighbors.
(1.2) estimate the total number of one hop
neighbors.
(1.3) find STD(ni) and ED(ni).
(1.4) calculate weight, W(ni) using Equation (7)
and broadcast it to all its one-hop neighbors.
Step
2: set flag = 1
Step
3: while (flag==1∧ni is receiving W(nj)∀nj∈Trangeni) do
(3.1) if  W(nj)<W(ni)  then
(3.2) ni gives up the competition for CH election
(3.3) set flag = 0
end if
end while
Step
4: if (flag == 1) then
(4.1) ni declare itself as CH and broadcast CH
advertisement message with its ID and
weight, W(ni) to nj∀nj∈Trange(ni)
(4.2)elseni is an isolated node, so declare and
advertise itself as a CH after timeout.
end if
Stop.


## 4.2. PSO Based Cluster Formation

After the selection of CHs, we now present our proposed PSO based clustering in MANET. It consists of initialization of a swarm of particles, evaluation of fitness function and accordingly the velocity and position of particles are updated depending upon the range of search dimension. Hence, the position and velocity of the particles are governed by its present velocity, its self-progression factor, and the social interaction factor as shown in (5) and (6).


### 4.2.1. Swarm Particle Initialization

Particles are initialized in a dimension equal to the number of nodes in MANET leaving the set of elected CHs; that is,Pi is a set for i=1,2,…,K, where K is the total number of non-cluster head nodes; that is, K=N-Ψ. A particle Pi of generation G is initialized with a randomly generated number in the range of 0 and 1; that is, 0<rand(0,1)≤1 and are independent for different components of particle Pi.


### 4.2.2. Evaluation of Fitness Function

The performance of each particle is measured using a fitness function which is application dependent. For our proposed algorithm the fitness function is based upon two objectives, that is, to maximize the strength of CHs and simultaneously minimize the intracluster distance between nodes and their respective CHs described as follows.(a) Optimizing the Strength of CH. One of the main objective functions of our proposed PSO based clustering is to optimize the strength of CHs. This is one of the most important requirements in order to achieve stability of clusters in MANET. It should be noted that the mere selection of the most eligible nodes to act as CHs does not ensure the effectiveness of clustering in such networks where data transmission from source to destination is done via CHs. Unequal distribution of loads on CHs results in early depletion of energy of heavily loaded CHs. The death of a CH results in link failure which causes an overhead of control messages in either selection of new CH or reclustering. Hence, the clustering effectiveness should also depend upon how nodes are affiliated to a CH to form well-structured clusters. We, therefore, have considered the strength of CHs as the first optimizing parameter. It depends upon the residual energy of a CH and its stability deviation. A CH having comparatively high residual energy which is least deviated from stability is said to have good strength. Thus, our first objective is to maximize the minimum strength of a CH calculated as follows:(8)Scha=EresidualchaSTDcha,where Scha is the strength of a CH cha, Eresidualcha is the remaining battery energy, and STDcha is the stability deviation of cha calculated using (4) described above. Therefore,(9)Objective1:MaximizeS=min⁡Scha∣∀cha∈Ψ.Hence, the fitness function is directly proportional to the value of S.That is,(10)Fitness∝S.(b) Optimizing the Intracluster Distance between Nodes and Their Respective CHs. Our second objective of the PSO based clustering is to minimize the intracluster distance between nodes and their respective CHs. The attenuation of signal strength is one of the characteristics of wireless channel which is directly proportional to the distance between the transmitter and receiver. The generally used model of power attenuation is given by(11)PRecd=PTransdβ.Here, PRecd is the received signal amplitude from a sender at a distance of d from the receiver, PTrans is the strength of the transmitted signal, d is the distance between transmitter and receiver, and β is the path loss factor [38]. When the distance from the nodes to their respective CHs increases, they need to exhaust more energy to communicate with their CHs. As the rate of energy depletion increases such nodes die quickly, resulting in degradation of network lifetime. So, focus should be given to assigning a node to the nearest CH from the set of CHs within its transmission range so as to minimize the energy consumption for intracluster transmission. We therefore have considered our second objective to be minimizing the average distance between nodes and their respective CHs. The average distance is calculated as follows: (12)AvDist=∑i=1kdistni,chak∀ni∈Trangecha∧cha∈Ψ,where |k| is the cardinality of all nodes that belong to the transmission range of cha(Trangecha) and Ψ is the set of elected CHs.Therefore,(13)Fitness∝1AvDist,(14)Objective2:MinimizeAvDist.Combining (10) and (13), it means that (15)Fitness∝SAvDist.That is,(16)Fitness=K×SAvDist,where K is the proportionality constant, the value of which can be assumed to be 1.Therefore,(17)Fitness=SAvDist.Thus, the objective of the PSO based clustering is to maximize the fitness value given in (17). The more the fitness value of a particle is, the more the compact clusters with optimum CHs are created with the constraints that a node can be assigned to one and only one CH and it should be within the transmission range of the CH.This ultimately will increase the lifetime of the CHs and also the lifetime of non-cluster head members and so increases the overall network lifetime. Each particle periodically updates the Pbest and Gbest value after evaluating its fitness function.


### 4.2.3. Update Velocity and Position of Particles

Particles, after evaluating their fitness function, calculate their velocity and position using (5) and (6), respectively. The velocity and position are updated after each iteration and the solution moves ahead towards the best possible result. The iteration continues and each time the particle’s current fitness value is compared with its personal best value. On achieving better fitness, the personal best, Pbesti, is replaced by the current value. Also, the global best, Gbest, is updated on getting the global best fitness. The update in velocity and position continues until a termination criteria is satisfied. We make the number of iterations as the termination criteria for the proposed work (Algorithm 2). After the completion of the clustering algorithm, nodes are assigned to their respective optimized CHs and are minimally distant away from their respective CHs achieving more compact and balanced clusters.Algorithm 2:PSO based cluster formation algorithm.
Input:  (1) A set of nodes  N={n1,n2,…,nl}. (2) a set of elected
CHs Ψ={ch1,ch2,…,chm}. (3) swarm size  Np.
Output:  An assignment A:n→Ψ with maximized objective function.
Begin:
Step
1: Initialize swarm particles Pi∀Pi∈Np∧1≤i≤Np
Step
2: fori=1toNp  do
(2.1) Find  Fitness(Pi) using Equation (17)
(2.2) set  Pbesti=Pi
end
Step
3: ifFitnessPbestj=max⁡{FitnessPbesti∀i:1≤i≤Np}
set Gbest = Pbestj
end if
Step
4:while  (Not Terminate) do
for  i=1  to  Np  do
(4.1) Each particle  Pi  update its velocity and position using
Equations (5) and (6) respectively.
(4.2) Find new  Fitness(Pi)  using Equation (17)
(4.3) if  Fitness(Pi)>Fitness(Pbesti)  then
(4.4) set  Pbesti=Pi
end
(4.5) if  Fitness(Pbesti)>Fitness(Gbest)  then
(4.6) set  Gbest=Pbesti
end
end
end
Step
5: Assign node  ni∀i∈N  to the CH  cha∀a∈Ψ  in its
transmission range with maximum fitness value i.e Gbest.
Stop.


## 4.2.1. Swarm Particle Initialization

Particles are initialized in a dimension equal to the number of nodes in MANET leaving the set of elected CHs; that is,Pi is a set for i=1,2,…,K, where K is the total number of non-cluster head nodes; that is, K=N-Ψ. A particle Pi of generation G is initialized with a randomly generated number in the range of 0 and 1; that is, 0<rand(0,1)≤1 and are independent for different components of particle Pi.


## 4.2.2. Evaluation of Fitness Function

The performance of each particle is measured using a fitness function which is application dependent. For our proposed algorithm the fitness function is based upon two objectives, that is, to maximize the strength of CHs and simultaneously minimize the intracluster distance between nodes and their respective CHs described as follows.(a) Optimizing the Strength of CH. One of the main objective functions of our proposed PSO based clustering is to optimize the strength of CHs. This is one of the most important requirements in order to achieve stability of clusters in MANET. It should be noted that the mere selection of the most eligible nodes to act as CHs does not ensure the effectiveness of clustering in such networks where data transmission from source to destination is done via CHs. Unequal distribution of loads on CHs results in early depletion of energy of heavily loaded CHs. The death of a CH results in link failure which causes an overhead of control messages in either selection of new CH or reclustering. Hence, the clustering effectiveness should also depend upon how nodes are affiliated to a CH to form well-structured clusters. We, therefore, have considered the strength of CHs as the first optimizing parameter. It depends upon the residual energy of a CH and its stability deviation. A CH having comparatively high residual energy which is least deviated from stability is said to have good strength. Thus, our first objective is to maximize the minimum strength of a CH calculated as follows:(8)Scha=EresidualchaSTDcha,where Scha is the strength of a CH cha, Eresidualcha is the remaining battery energy, and STDcha is the stability deviation of cha calculated using (4) described above. Therefore,(9)Objective1:MaximizeS=min⁡Scha∣∀cha∈Ψ.Hence, the fitness function is directly proportional to the value of S.That is,(10)Fitness∝S.(b) Optimizing the Intracluster Distance between Nodes and Their Respective CHs. Our second objective of the PSO based clustering is to minimize the intracluster distance between nodes and their respective CHs. The attenuation of signal strength is one of the characteristics of wireless channel which is directly proportional to the distance between the transmitter and receiver. The generally used model of power attenuation is given by(11)PRecd=PTransdβ.Here, PRecd is the received signal amplitude from a sender at a distance of d from the receiver, PTrans is the strength of the transmitted signal, d is the distance between transmitter and receiver, and β is the path loss factor [38]. When the distance from the nodes to their respective CHs increases, they need to exhaust more energy to communicate with their CHs. As the rate of energy depletion increases such nodes die quickly, resulting in degradation of network lifetime. So, focus should be given to assigning a node to the nearest CH from the set of CHs within its transmission range so as to minimize the energy consumption for intracluster transmission. We therefore have considered our second objective to be minimizing the average distance between nodes and their respective CHs. The average distance is calculated as follows: (12)AvDist=∑i=1kdistni,chak∀ni∈Trangecha∧cha∈Ψ,where |k| is the cardinality of all nodes that belong to the transmission range of cha(Trangecha) and Ψ is the set of elected CHs.Therefore,(13)Fitness∝1AvDist,(14)Objective2:MinimizeAvDist.Combining (10) and (13), it means that (15)Fitness∝SAvDist.That is,(16)Fitness=K×SAvDist,where K is the proportionality constant, the value of which can be assumed to be 1.Therefore,(17)Fitness=SAvDist.Thus, the objective of the PSO based clustering is to maximize the fitness value given in (17). The more the fitness value of a particle is, the more the compact clusters with optimum CHs are created with the constraints that a node can be assigned to one and only one CH and it should be within the transmission range of the CH.This ultimately will increase the lifetime of the CHs and also the lifetime of non-cluster head members and so increases the overall network lifetime. Each particle periodically updates the Pbest and Gbest value after evaluating its fitness function.


## 4.2.3. Update Velocity and Position of Particles

Particles, after evaluating their fitness function, calculate their velocity and position using (5) and (6), respectively. The velocity and position are updated after each iteration and the solution moves ahead towards the best possible result. The iteration continues and each time the particle’s current fitness value is compared with its personal best value. On achieving better fitness, the personal best, Pbesti, is replaced by the current value. Also, the global best, Gbest, is updated on getting the global best fitness. The update in velocity and position continues until a termination criteria is satisfied. We make the number of iterations as the termination criteria for the proposed work (Algorithm 2). After the completion of the clustering algorithm, nodes are assigned to their respective optimized CHs and are minimally distant away from their respective CHs achieving more compact and balanced clusters.Algorithm 2:PSO based cluster formation algorithm.
Input:  (1) A set of nodes  N={n1,n2,…,nl}. (2) a set of elected
CHs Ψ={ch1,ch2,…,chm}. (3) swarm size  Np.
Output:  An assignment A:n→Ψ with maximized objective function.
Begin:
Step
1: Initialize swarm particles Pi∀Pi∈Np∧1≤i≤Np
Step
2: fori=1toNp  do
(2.1) Find  Fitness(Pi) using Equation (17)
(2.2) set  Pbesti=Pi
end
Step
3: ifFitnessPbestj=max⁡{FitnessPbesti∀i:1≤i≤Np}
set Gbest = Pbestj
end if
Step
4:while  (Not Terminate) do
for  i=1  to  Np  do
(4.1) Each particle  Pi  update its velocity and position using
Equations (5) and (6) respectively.
(4.2) Find new  Fitness(Pi)  using Equation (17)
(4.3) if  Fitness(Pi)>Fitness(Pbesti)  then
(4.4) set  Pbesti=Pi
end
(4.5) if  Fitness(Pbesti)>Fitness(Gbest)  then
(4.6) set  Gbest=Pbesti
end
end
end
Step
5: Assign node  ni∀i∈N  to the CH  cha∀a∈Ψ  in its
transmission range with maximum fitness value i.e Gbest.
Stop.


## 5. Explanatory Example

After the selection of appropriate CHs and designing cost fitness function for swarm particles, the assignment of nodes to their respective CHs is based on the idea proposed by Kuila and Jana [28]. A component of particle Pi in the dth dimension (CPi,d) maps the assignment of nodes to a CH. For explanatory example, Figure 6 represents our network scenario consisting of 6 elected CHs and 14 non-cluster head nodes. The elements of the ith particle (CPi,d) are randomly initialized whose range is in between 0 and 1 as given in the 4th column of Table 1. The cardinality of the number of CHs which are in the direct communication range of each node (say r) is represented by |Gr| and given in column 3. The ceiling of the particle component value multiplied by |Gr| gives a number, that is, the CH with which the node will be affiliated. From Table 1, it is clear that node 1 is randomly affiliated with cluster head ch1, node 2 with ch2, and so on. The clusters formed after execution of the PSO based clustering are shown in Figure 7.Table 1
Nodes assignment to CHs.
Node # (ni)
Possible CHs (Gr)
G
r
C
P
i
,
d
G
r
×
C
P
i
,
d
Assigned CH
1
{
c
h
1
}
1
0.21
1
c
h
1
2
{
c
h
1
,
c
h
2
,
c
h
3
}
3
0.92
3
c
h
3
3
{
c
h
1
}
1
0.11
1
c
h
1
4
{
c
h
2
}
1
0.29
1
c
h
2
5
{
c
h
2
}
1
0.32
1
c
h
2
6
{
c
h
2
,
c
h
3
,
c
h
4
}
3
0.42
2
c
h
3
7
{
c
h
4
}
1
0.75
1
c
h
4
8
{
c
h
4
}
1
0.36
1
c
h
4
9
{
c
h
4
}
1
0.81
1
c
h
4
10
{
c
h
5
}
1
0.24
1
c
h
5
11
{
c
h
5
}
1
0.83
1
c
h
5
12
{
c
h
5
,
c
h
6
}
2
0.51
2
c
h
6
13
{
c
h
5
,
c
h
6
}
2
0.62
2
c
h
6
14
{
c
h
3
,
c
h
6
}
2
0.39
1
c
h
3Figure 6
Topology of the network with elected CHs.Figure 7
Cluster formation after execution of PSO based clustering.


## 6. Results and Discussions

In this section we describe the simulation results of the proposed work. To evaluate the performance, we have performed pervasive simulation experiments. We first implemented the already existing related clustering algorithms, that is, adaptive cluster formation in MANET using particle swarm optimization (A-PSO) and clustering in MANET using comprehensive learning particle swarm optimization (CLPSO), and then compared the performance of the proposed work with these algorithms. We have used NS2 network simulator [36] for execution of our simulation work. To assess our proposed algorithm, the number of nodes varies from 20 to 100. Nodes are deployed in the simulation area of 750m×750m. The transmission range of nodes varies from 10 m to 180 m and nodes are initialized with an initial energy of 80000 Nanojoule (NJ). We have summarized the simulation parameters setting in Table 2. The simulation results show the efficiency of the proposed ME-PSO over A-PSO and CLPSO in terms of packet delivery ratio (PDR), average end-to-end delay, average number of clusters formed and reclustering required, network lifetime, and energy consumed.Table 2
Simulation parameters.
Parameter
Value
Number of nodes
20–100
Simulation area
750
m
×
750
m
Simulation time
500 sec
Simulation iteration
100
Initial energy
80000 NJ
Packet size
512 bytes
Packet rate
35 packets/s
Transmission range of nodes
10 m–180 m
Routing protocol
AODV
Traffic type
Constant bit rate (CBR)
Movement model
Random-way point
Maximum speed
20 m/s
Radio propagation model
Two-ray groundFigure8 presents the packet delivery ratio for ME-PSO, A-PSO, and CLPSO with an increase in packet rate. This is an important performance metric which shows the successful number of packets received by a destination node. From the figure it can be noticed that for the proposed ME-PSO the PDR is comparatively higher than A-PSO and CLPSO. This is because in our proposed work we have taken stability deviation which is based on the mobility of nodes, their direction of motion, distances with neighbors, and the degree of connectivity as well as energy depletion for CH selection. These parameters certainly improved the lifetime of CHs. Thus, the path breakage due to the death or movement of CHs is reduced. This improved the intercluster multihop routing from source CH to destination CH shown in the form of improved PDR. Also, due to these factors, the average number of reclustering instances required for ME-PSO is reduced compared to A-PSO and CLPSO as illustrated in the graph shown in Figure 9.Figure 8
Packet delivery ratio versus packet rate.Figure 9
Average number of reclustering required versus number of nodes.Figure10 depicts the average end-to-end delay with varying packet rate. It can be observed from the figure that the proposed algorithm has a lower delay compared to A-PSO and CLPSO. This is due to the fact that in our work we focused on optimization of the strength of CHs which depends on the ratio of their residual energy to their stability deviation. Thus, depending on the strength of CHs, a node gets affiliated with the one in its transmission range having maximum strength. This ultimately balanced loads on CHs and reduced the rate of packet dropped and hence reduces the average end-to-end delay in packet transmission.Figure 10
Average end-to-end delay versus packet rate.Figure11 depicts the average number of clusters formed as the number of nodes increased. The graph shows that the number of clusters formed in our proposed ME-PSO is comparatively lesser than the related existing clustering algorithms of A-PSO and CLPSO. This is the result of using a fitness function which depends not only on the strength of CHs but also on the average distance of cluster members to its respective CHs and thus forming a more compact cluster with optimal load balance on CHs.Figure 11
Average number of clusters formed versus number of nodes.Figure12 shows the effectiveness of ME-PSO clustering algorithm coupled with AODV routing protocol compared with coupling the same with DSDV. As AODV is an on-demand routing protocol for MANET, the path setup is as and when needed from source CH to destination CH. This requires less overhead with no need of maintaining the routing table all the time as required by DSDV which is table-driven routing protocol for MANET. As shown in this graph, three nodes died due to the exhaust in energy when the proposed clustering algorithm is coupled with DSDV while on the other hand only one node died when the same coupled with AODV.Figure 12
Remaining battery energy per node.Finally Figure13 shows the effectiveness of the proposed algorithm in terms of the network lifetime. This is an important performance parameter defined in various ways by different researchers like the time till the death of the first CH or the last CH or the death of some percentage of CHs in the network. For our work, we have taken network lifetime as the time till the death of the first CH in the network. The result shown in the graph depicts the effectiveness of the proposed work as the maximization of the lifetime of CHs maximizes the overall network lifetime compared with the other related algorithms.Figure 13
Network lifetime versus number of nodes.Thus, we can say that the proposed ME-PSO clustering algorithm effectively forms stable clusters with well optimized intercluster as well as intracluster routing which is being taken care of by the parameter like stability deviation in the CH selection and the PSO based cluster formation mechanism. The simulation results proved its effectiveness over the existing related algorithms. Also, the time complexity of ME-PSO isO(nlog⁡m) in the worst situation where n is the number of non-cluster head nodes and m is the number of elected CHs. However, the time complexity is O(nlog⁡n) for A-PSO and O(mnlog⁡n) for CLPSO in the worst situation. The time complexity of the proposed algorithm is better than A-PSO and is far better than CLPSO. Hence, the proposed clustering algorithm shows the improvement over A-PSO and CLPSO.


## 7. Conclusion and Future Work

In this paper, we have presented a mobility aware energy efficient clustering for MANET based on a bio-inspired approach of particle swarm optimization. For this we considered the main challenges of MANET, that is, mobility and energy for the selection of most eligible nodes to act as CHs which coordinate their cluster members for longer duration of time. It selects a node which is less deviated from stability and depletes its less energy to serve as CH which improved its life time. For clustering, a multiobjective fitness function is developed based on the strength of CHs and the average distance of member nodes to its respective CHs. The strength of a CH is calculated as the ratio of its remaining battery energy to its stability deviation. The average distance from member nodes to their respective CHs ensures the optimized distance from cluster members to their corresponding CHs. The fitness function taking a combination of these two parameters certainly improved the lifetime of CHs as well as the member nodes because from the selection of CHs to cluster formation, most of the challenges of MANET are simultaneously considered which improved the overall network lifetime. In the future we further enhance the algorithm for optimizing intercluster multihop routing in MANET using PSO.



---

*Source: 1903190-2017-11-08.xml*