PEECA: PSO-Based Energy Efficient Clustering Algorithm for Wireless Sensor Networks

New advancement in MEMS and wireless technologies allows the micro autonomous system comprised of small tiny devices known as sensors. These sensors can detect, compute and communicate via suitable sensor technology that gives birth to wireless sensor network [1-3]. Deployment ease and low cost sensors make wireless sensor network suitable for many applications like: health care, transportation, smart building, and environmental monitoring etc. Because of the limitations on the power, bandwidth and processing capability, efficient routing becomes a key issue in sensor network [2]. Routing methods in WSN are responsible for exploring and retaining energy efficient paths, to facilitate reliable and efficient communication [4,5]. The energy efficient routing protocols (EERP) are broadly categorized as: network structured, communication modelled, topology, and reliability based routing schemes [6,7]. The network structure based protocols can be broadly categorized as: flat structured and hierarchy based protocols. The communication model based protocols can be categorized as: negotiation or coherent/non-coherent or query based. Topology based schemes can be divided into location or mobile agent based. Reliable routing schemes can be categorized as: QoS or multipath based. Clustering is a process used to handle the energy usage effectively [8,9]. In this scheme, each and every group of sensors has a head node recognized as cluster head (CH) that perform data fusion and data forwarding toward the base station (BS) or sink node [10-12]. Numerous cluster based routing algorithms have been reported in text to extend the network life span. A clustered WSN is shown in Fig. 1. The LEACH is most popular routing protocol due to its simplicity and efficiency [13]. LEACH divides the complete network into a various clusters, and execution time of system is partitioned into several rounds. In every round, the member node contends to be CH in accordance with some specified criterion. However, this protocol does not guarantee that the preferred amount of CHs is selected in the network. Some enhancement on LEACH is reported in literature [14-16].

Fig.1. A Clustered WSN

In this work, we proposed an improved clustering algorithm to increase network lifetime. The main initiative in our new algorithm is CH election with consideration of residual energy. The rotating epoch for every node is dissimilar in accordance with owned primary and remaining energy. The nodes that have higher opening and remaining energy value will be more probable to turn into CH per round per iteration. CHs gathers data from the other sensor nodes in its particular clusters then perform data aggregation and forward that to BS. The key idea of proposed algorithm is the election of CH which can lessen the intra-cluster distance and optimize the network energy.

The rest of the paper is structured as. In section II, previous work on this topic is summarized. The proposed method is expressed in section III. Section IV illustrates the simulation results and analysis. At last, sectionV concludes the work.

• II.    Related Work

In this section, we focus on the similar work reported in the literature. Routing is a process of selecting best path in the network. So, routing protocols are liable for discovering and managing efficient routes in the network. Energy efficiency is an essential issue in WSN routing. Hence, development of energy efficient routing protocol becomes a hot research issue in sensor networks. The energy efficient routing protocols (EERP) can be broadly classified based on four parameters as follows: network structure, computation model, topology, reliability [17]. The taxonomy of EERP is shown in Fig. 2. Here, we focus on the hierarchical or cluster based routing protocols. Several hierarchical routing protocols for WSNs are given by various researchers. LEACH is an eminent protocol of this category

Fig.2. Taxonomy of Energy Efficient Routing Protocols in WSNs

LEACH is a hierarchical routing protocol that reduces the energy expenditure in the network. LEACH outperforms the classical routing algorithm since it uses adaptive clustering scheme. But when a CH dies in the LEACH that cluster is of no use since data gathered at CH will not reach the BS. LEACH suffers from the problem of CH rotation overhead in every round. LEACH elects the CH depend on the random number in the range (0,1]. If chosen number is fewer than threshold T(n) then node become CH for present round. Energy efficient hierarchical clustering algorithm (EEHCA) uses a novel process for CH election with the idea of backup CHs to get better efficiency of the network [18]. The distributed energy efficient clustering (DEEC) uses initial and remaining energy level of node for CH selection. It is developed for heterogeneous wireless sensor networks.

• III.    Proposed Work

In this section, we illustrate the system model and optimal clustering used in our protocol and also gives detailed description of proposed algorithm.

• A. System model

Here, we illustrate the network model and radio energy model used in proposed protocol.

• 1)    Network model

Let us consider a network model alike to that utilized in LEACH with the following characteristics:

• i.    Every node carry out sensing tasks sporadically and all the time send data to BS.

• ii.    A fixed BS can be placed inside or outside the network area.

• iii.    The entire nodes are fixed and energy restrained.

• iv.    Each and every node is capable of working in CH mode as well as in sensing manner.

• v.    Data fusion is utilized to lessen the overall data.

• 2)    Radio energy model

In this work, we employ radio energy model (REM) given in Fig. 3. In REM, transmitter depletes energy to operate radio as well as power amplifier, moreover the receiver uses up the energy to operate radio. The radios can carry out the power control and thus utilize minimum energy needed to get to the destined recipients. Because of attenuation, energy loss model is applied for small and long distances. Hence, to realize signal-to-noise ratio (SNR) in broadcasting l -bit packet over distance d , the energy dissipated by radio is specified as:

^ETX ( ¹ , d ) ^—

lE_dec + 8 fs d 2,

4 elec      mp , if d < d0 if d > d0

Wherever, E elec represents energy depleted per bit to operate the electronic circuitry, ε fs and ε mp depends on amp model, d denotes the distance among sender and receiver. The d₀ is the threshold transmission distance.

The threshold distance d₀ is given by:

Equating the equation (1) for d = d₀

IE, + 8 z d — IE, + 1sd^

elec       fs 0        elecmp d0

To obtain l- bit message, the radio uses

ERX (1) — 1.Ee1ec

Fig.3. Radio Energy Model

dE round dk

0 + 0 + l £f_s^d_toBs

dF. . round           2

dk      ^{l S fs}d^toBS

dd

( k ) + l e n dk        ^fs dk

l e _fs n ( m ² ) d

2n

dk

_V 2 n k ₎

(k-')

dE                 l e _fs n ( m ² )

round           2

lb fsdtoBs + dk              2n

1 I ^— ( k ) k ² ) dk^v ’

B. Optimal clustering

Let us consider a region A= m x m meter² over which n nodes are evenly dispersed. For ease, we suppose that BS is situated in middle of network area, and distance of every node to the BS or its CH is ≤ d₀ . The field is divided into k number of clusters. In transmission, every non head node forwards l -bit packet to CH inside its cluster. Therefore, energy consumed by non-CH node is expressed as:

Е _гн — /Е , +1s, d" (3)

non - CH elec fs toCH

Where, d toCH denotes average distance among member and head of cluster. Considering that nodes are evenly scattered, it can be revealed as:

dE round dk

1 e fs toBS

^{l e} fs n ^{( m 2)} 2nk²

Now putting the equation (6) equals to zero, we get the optimal no. of clusters as:

kopt

If distance of a considerable proportion of nodes to sink is larger than d₀ in that case optimal value of clusters is given as:

x max y max

max max dtoCH = f f ((x2 + y2) * p(x, y))dx dy = о о                             2nk

kopt

"

V

m dtoBS )

Wherever, p(x,y) represents the distribution of node.

The energy depleted in CH in a round is explained as:

E_CH = I n - 1 I Ek= + n lE_DA + lEdec + PA\_BS (4)

CH                 elec         DA      elec      fs toBS

V k )      k

Wherever, k denotes the amount of clusters, E DA denotes data processing rate of a bit reports to sink, d toBS represents the average distance among a cluster head and BS.

d oes = f ( x ² + y ² ) *1 = 0.765* m

The total energy exhausted in network in one round is given as:

E round    l ( ² n ^Eelec ⁺ n ^EDA ^{+ P} fs ( ^kdtoBS ⁺ nd toCH ) )     ⁽⁵⁾

Now differentiating equation (5) w.r.t. k dEund = — (2 nlEdec) + — (lnED,) + — (le,kd 2BS) +—l lefs nd2CH)

_{dk     dk}        elec     _dk      DA     _dk     fs toBS     _dk     fs toCH

The optimal probability of a node to turn out to be CH is computed as:

popt

popt kopt n

^{2 П П} b mP^ V V d toBS )

The optimal possibility of a node to turn into CH is extremely essential. If clusters are not created in best possible manner, the total energy usage for each round is raised exponentially.

• C.    Particle swarm optimization

The PSO is an optimization scheme, modeled behind the societal behavior of a flock of birds or fishes [19, 20]. In PSO, a swarm specifies the no. of possible solutions to complex problem, where every probable solution is known as a particle. The objective of PSO is to discover the particle location that outcomes the best assessment of a specified fitness function. During initialization phase of PSO, every particle set initial parameters in random fashion and is flown throughout the multidimensional search space. In every generation, every particle make use of the info about its earlier individual best position as well as global best position to maximize the possibility of moving in the direction of a better answer space that will results in improved fitness and update its candidate solutions in accordance with the following equations:

V id ( t ) = ® x V d ( t - 1 ) + Q X0 1 X ( P - X d ( t - 1 ) ) + C 2 X0 2 x ( P g_d - X d ( t - 1 ) ) (10)

Xd (t ) = X d (t -1)+Vd (t)       (11)

Where, V and X represents particle velocity and position, t is time, C₁, C₂ are learning coefficients, ω is the inertia weight. ϕ₁, ϕ₂ are the numbers generated randomly among 0 &1. P _d is particle’s best position individually and P_gd is particle’s best position globally.

• D.    Proposed algor thm

The general model of proposed energy efficient clustering algorithm is shown in Fig. 4. Starting with data collection it consists of the computation like figuring out the power of all sensor nodes and preliminary node clustering over the measurement space and the initialization. The initialization is for planning the position of every sensor in evaluation space and using PSO to get the initial position of the head of every cluster. Afterward regular operation mode is entered, it comprised of two phases those are subsequent.

Fig.4. Block Diagrams of Proposed Method

Like LEACH, our proposed algorithm has two phases adaptive clustering (set up phase) and data transfer (steady state phase). This is still running until the network becomes idle, either by the node deaths or by BS commands. During the adaptive clustering phase, BS broadcasts a message at a certain power containing its ID info. The BS decides the number and best possible size of clusters depending upon the network size and node density. The sink then sends control packet to every node informing about the protocol to be utilized. These control packets consists of all necessary info needed for steady state functioning of the procedure. In steady state phase, non head nodes gather data and forward to its CH. Similarly, each CH sends data to BS. After each round, a CH checks its remaining energy with respect to threshold rate for a CH transform. If so, it generate a signal and lets its members realize that CH is just going to alter. Thereafter, it behaves like a non-CH node. The CH rotation process continues till each node in a cluster gets a possibility to be a CH. Once the final node reached to be the threshold rate, the algorithms starts over and run the identical CH schedule.

popt

T ( s ) = ] ^{1 -} Pop*^x

r mod

if s e G

otherw se

Where p opt is the preferred fraction of CH among the entire nodes, r denotes the present round no., G represents the node’s group that have not been selected CHs in previous (1/ p_opt ) rounds, and s represent the present CH node.

Most of the energy efficient techniques in the literature minimizing the average wasted energy [21-24]. Hence, they take into effect only residual energy. The network life span depends both on the average exhausted energy and average transmission energy. The final aim is to maximize the network life span so one needs to balance the both.

We propose the new threshold function to improve the threshold function used by LEACH be as:

popt

T ( s ') = <

1 - P_opt x r mod ^ 1

popt

x E MMRE.      if s . _e g

^EAvg                  (13)

otherw se

Where E_MMRE , is the maximum of minimum residual energies, E_Avg is the average energy and s' is the present CH.

The average energy at r^th round is specified by:

Etvg ( Г) = ПЕ(J " R J          (14)

Where R is the life span of network, which assume that each node consume same quantity of energy in every round. Considering that the entire nodes dead at the identical time. Thus, R denotes whole rounds in which network is alive. The R is given as:

R =

total

E round

• IV.    Simulation Results

  The performance analysis of proposed algorithm is done with help of MATLAB 2015a. In the network, 100 nodes are organized in random fashion in 100m×100m area where BS is situated in the middle. The performance assessment of proposed work is done as per the certain parameters given as:

Energy dissipation: remaining energy with the nodes.

No. of alive nodes: quantity of nodes that have not so far exhausted their power.

No. of dead nodes: quantity of nodes that have used all of their power and are unable to perform any function.

Packet sent to BS: number of packet sends to BS.

No. of CHs: number of nodes that have chosen CHs over rounds.

The PEECA is evaluated with LEACH, DEEC, in term of dead and alive nodes over rounds, and energy expenditure. The total number of rounds used in experiment is 10,000. The simulation network parameters are summarized in Table 1. PSO specifications are revealed in Table 2.

Table 1. Network parameters

Parameter	Value
E 0	0.5 J
elec	5 nJ/bit
E TX =E RX	50 nJ/bit
ε fs	10 pJ/bits/m2
ε mp	0.0013 pJ/bits/m2
E DA	5 nJ
Packet size	500 bytes

Table 2. PSO Parameters

Parameter	Value
Particle size	50
Number of Iterations	30
ω	0.09
C 1 , C 2	2.0, 2.0
V max	4

Fig. 6 illustrates the no. of dead nodes per round demonstrating stability of the network.

Fig.6. Dead Nodes over Rounds

Fig. 7 illustrates the no. of alive nodes per round.

Fig.7. Number of Nodes Alives over Rounds

Fig. 8 shows the no. of packet sends to BS.

Fig. 5 shows the comparative analysis of remaining energy of the proposed algorithm with LEACH and DEEC and it is clear that proposed algorithm have better remaining energy as compared to LEACH and DEEC.

rounds

Fig.5. Remaining Energy over Rounds

Fig.8. Number of Packets Sent to BS

Fig. 9 shows the cluster head selection over rounds.

Fig.9. The Cluster Heads over Rounds

The proposed algorithm (PEECA) is more efficient in term of extending the network life time and number of packet received at BS is high as compared to LEACH and DEEC. Table 3 shows the efficiency of energy optimization that is attained using PEECA of variable clustering of wireless sensor networks assessment with different algorithms.

Table 3. Energy Ptimization of Different Schemes

Algorithm	Energy optimization
Proposed (PEECA)	90%
DEEC	79%
LEACH	68%

Security is also an important issue in clustering routing protocols in WSNs [25].

• V.    Conclusion

This paper illustrates a PSO based clustering algorithm (PEECA) for wireless sensor networks. We presented an optimized clustering algorithm where the key focus is to improve the CH election process. CHs are chosen in every cluster based on remaining node energy and average energy of network. As of the simulation results, it is clear that stability time of system is improved as compared to LEACH and DEEC. The existing node energy in our proposed algorithm is better as compared to the LEACH and DEEC. So, we state that the proposed algorithm has improved energy efficiency and useful in extending the network life span.

This work is carried out with the help of Human Resource Development Ministry under research grant for doctoral study.

• [1]    I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cyirci, “Wireless sensor networks: a survey,” Computer Networks , Vol. 38, No.4, pp. 393-422, 2002.

• [2]    K. Sohraby, D. Minoli, and T. Znati, Wireless Sensor Networks: Technology, Protocols, and Applications , John Wiley& Sons: USA, 2007.

• [3]    J. Yick, M. Biswanath, and D. Ghosal, “Wireless sensor network survey,” Computer Networks , Vol.52, No. 12, pp.2292-2330, 2008.

• [4]    P. Kumar, M. P. Singh, and U. S. Triar, “A review of routing protocols in wireless sensor network,” International Journal of Engineering Research & Technology , Vol. 1, No. 4, pp. 1–14, 2012.

• [5]    K. Sohrabi, J. Gao, V. Ailawadhi, and G. J. Pottie, “Protocols for self-organization of a wireless sensor network,” IEEE Personal Communications, Vol. 7, No. 5, pp. 16–27,2000.

• [6]    Banerjee S and Khuller S, “A clustering scheme for hierarchical control in multi-hop wireless networks,” in Proceedings of 20th Joint Conference of the IEEE Computer and Communications Societies , Anchorage, AK, USA, 2001.

• [7]    M. Younis, M. Youssef, and K. Arisha, “Energy-aware management in cluster-based sensor networks,” Computer Networks, Vol. 43, No. 5, pp. 649–668,2003.

• [8]    W. K. Lai, C. S. Fan, and Lin L Y, “Arranging cluster sizes and transmission ranges  for  wireless  sensor

  networks,” Information Sciences , Vol. 183, No. 1, pp. 117–131, 2012.

• [9]    A. A. Abbasi and M. Younis, “A survey on clustering algorithms for wireless sensor networks,” Computer Communications, Vol. 30, No.14-15, pp. 2826-2841, 2007.

• [10]    S. Naeimi, H. Ghafghazi, C. O. Chow, and H. Ishii, “A survey on the taxonomy of cluster-based routing protocols for homogeneous wireless sensor networks,” Sensors , Vol. 12, No. 6, pp. 7350–7409, 2012.

• [11]    X. Liu and J. Shi, “Clustering routing algorithms in wireless sensor networks:   an overview,” KSII

  Transactions on Internet and Information Systems , Vol. 6, No.7, pp.1735-1755, 2012.

• [12]    S. P. Singh and S. C. Sharma, “A survey on cluster based routing protocols for wireless sensor networks,” Procedia Computer Science , Vol. 45, pp.687-695, 2015.

• [13]    W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks,” in Proceedings of 33rd Hawaii International Conference on System Sciences , Hawaii, USA, pp. 1–10, 2000.

• [14]    W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “Application specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Networking , Vol. 1, No.4, pp.660-670, 2002.

• [15]    L. Qing, Q. Zhu, and M. Wang, “Design of distributed energy efficient clustering algorithm for heterogeneous wireless sensor network , ” Computer Communications , Vol. 29, pp.2230-2237, 2006.

• [16]    A. T. Nuray and S. M. Dharagma, “A New Energyefficient clustering-based protocol for heterogeneous wireless senor network,” Electrical and Electronics Systems , Vol. 4, No. 3, pp. 2-7, 2015.

• [17]    N. A. Pantazs, S. A. Nikolidakis, and D. D. Vergados, “Energy-efficient routing protocols in wireless senor network: a survey,” IEEE Communication Surveys and Tutorials, Vol. 15, No. 2, pp. 551-591, 2013.

• [18]    G. Xin, W. H. Yang, and D. D. Gang, “EEHCA: an energy efficient clustering algorithm for wireless Sensor network,” Information Technology Journal, Vol. 7, pp. 245-252, 2008.

• [19]    J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ , USA, pp. 1942-1948, 1995.

• [20]    R. V. Kulkarni and G. K. Venayagamoorthy, “Particle

  swarm optimization in wireless sensor Network: a brief survey,” IEEE Transactions on System, Man, and Cybernetics-Part C: Applications and Reviews , Vol.41, No.2, pp.262-267, 2011.

• [21]    S. Soro and W. B. Heinzelman, “Prolonging the lifetime of wireless sensor networks via unequal clustering,” in Proceedings of 19th IEEE International Parallel and Distributed Processing Symposium , Denver, Colorado, USA, 2005.

• [22]    D. C. Hoang, R. Kumar, and S. K. Panda, “Realisation of cluster based protocols using fuzzy C-mean algorithms for wireless sensor networks,” IET Wireless Sensor System , Vol. 3, No. 3, pp.163-171, 2013.

• [23]    D. Kumar, “Performance analysis of energy efficient clustering protocol for maximizing lifetime of wireless sensor networks,” IET Wireless Sensor System , Vol. 4, No.1, pp.9-16, 2014.

• [24]    V. C. Thang and N. V. Tao, “A Performance evaluation of improved IPVv6 routing protocol for wireless sensor networks,” International Journal of Intelligent Systems and Applications , Vol. 8, No.12, pp. 18-25, 2016.

• [25]    S. P. Singh and S. C. Sharma, “Secure clustering protocols in wireless sensor networks,” Journal of Wireless Sensor Network , Vol. 3, pp.1-10, 2016.

Professor S. C. Sharma received the M.Sc.

international journals/conferences and supervised more than 30 projects/dissertation of PG students. He has supervised 14 PhDs in the area of Computer Networking, Wireless Network, Computer Communication and continuing supervising Ph.D. students in the same area.

He has successfully completed several major research projects independently funded by various Govt. Agencies like AICTE, CSIR, MHRD, DST, and DRDO.