# An Energy Distance Aware Clustering Protocol with Dual Cluster Heads Using Niching Particle Swarm Optimization for Wireless Sensor Networks

Authors: Dexin Ma; Pengmin Xu
Journal: Journal of Control Science and Engineering
 (2015)

---

## Abstract

Energy efficient utilization is an important criteria and factor that affects the design of wireless sensor networks (WSNs). In this literature, we propose an energy distance aware clustering protocol with Dual Cluster Heads using Niching Particle Swarm Optimization (DCH-NPSO). The protocol selects two cluster heads in each cluster, the Master Cluster Head (MCH) and the Slave Cluster Head (SCH), and the selection needs to consider the network state information carefully and deliberately. Simulation results show that the protocol we proposed can balance the energy dissipation and extend the network lifetime effectively.


---

## Body

## 1. Introduction

The application of WSNs becomes more wide in recent years; there are a large number of typical applications, such as environment surveillance and exploration, target tracking, and volcano activity monitoring [1]. The energy of wireless sensor nodes is usually supplied by dry/lithium batteries, and, in some dangerous situations, the replacement or recharge of batteries is impossible. So, energy-efficient utilization is an important issue for WSNs, while clustering is as an energy-efficient technique and is often used to prolong the sensor network’s lifetime [2].There are several optimization problems in the whole information transmission process, WSN issues, such as clustering, localization, data fusion, and deployment that are often formulated as optimization problems [3]. Traditional mathematical optimization methods need tremendous computation efforts, and with the problem scale increase, the computation grows up exponentially. As to implement on tiny wireless sensor nodes, an optimization method that needs moderate and even minimal computation efforts yet generates better results is needed. Bioinspired optimization methods are computation efficient in contrast to traditional mathematical methods [4]; the authors [5] have demonstrated and compared the general mathematical formulation for this kind of problems. In this paper, we take advantage of bioinspired optimization to resolve clustering formation.Particle swarm optimization (PSO) is a bioinspired optimization, and it is simple, effective, and popular optimization method [6]. It has been used to address WSN issues such as clustering, deployment, localization, and date aggregation [3]. Niching is also inspired by nature [7]; different species must compete to survive by taking on different roles. Niching is a significant technique for multimodal optimization, and within the framework of PSO, some niching methods have been proposed and developed [8, 9].Several clustering protocols have been proposed for WSNs, LEACH [10] is a famous clustering protocol and selects nodes with a probability to act as cluster heads periodically. BCDCP [11] makes use of the base station to select clusters and routing path and perform randomized shift of cluster heads.Particle swarm optimization has been used to resolve WSN issues such as clustering, localization, deployment, and data fusion [3]. A protocol using PSO [12] aimed to minimize the intracluster distance and optimize the energy dissipation of the network. A clustering particle swarm optimization [13] has been presented for dynamic optimization and employed a hierarchical clustering method to locate multiple optima for dynamic optimization problems.In this literature, we propose an energy distance aware clustering protocol with Dual Cluster Heads using Niching Particle Swarm Optimization (DCH-NPSO). The protocol generates two cluster heads in each cluster using Niching PSO, a Master Cluster Head (MCH) and a Slave Cluster Head (SCH). The MCH receives and aggregates the data that have been collected from its member nodes and then sends it to the SCH; the SCH transmits the aggregated data to the sink directly. In our designed scheme, MCH does not communicate with the sink directly, that can balance the energy consumption. The simulation results show that the protocol can balance the network loads, minimize the energy consumptions, and prolong the network lifespan of WSNs.


## 2. System Model

### 2.1. Network Model

We assume a number ofN wireless sensor nodes distributed among an M×M squared field randomly. Sensed data are gathered in a periodical way, and we define each period as a round. Each round contains three phase, a set-up phase uses DCH-NPSO to part the network into clusters and selects MCH and SCH using Niching PSO, a steady phase when data collected and aggregated by the MCH, and a finish phase followed when data is transmitted to the BS (Base Station, also called sink node); the steady phase should be longer than other phases to minimize the energy dissipation. The MCH is used for data collection and data aggregation. The aggregated data are sent to the SCHs, and then the SCHs transmit it to the sink node directly and get some information through a piggyback manner to save more energy. The partial structure of the network in a round is as shown in Figure 1.Figure 1
DCH-NPSO partial network architecture.We make assumptions about the network model as follows.(i)
All nodes are equipped with small batteries, so each node has initial energy allocated and the energy is constrained.(ii)
A BS situates far away from the sensing field, and it has no energy constraints.(iii)
Each node has its location information. There are a number of existing works on localization in WSNs [14–16]. For example, we use the solution proposed in [16] to obtain the localization.(iv)
All nodes are equipped with power control units to adjust the transmit power according the distance.(v)
All nodes have no mobility.


### 2.2. Radio Model

The radio model we adopt is as used in [10]. In this model, the transmitter dissipates energy to drive the amplifier and the radio components, and the receiver dissipates energy to drive the radio components. The transmitter has power control ability to properly set the amplifier according to the distance and can be turned off to avoid receiving unintended sensing data, to minimize the energy consumption. The energy dissipation for transmit an l-bit packet over distance d is
(1)ETxl,d=Eelec(d)+Eampl,d=l×ETx+l×εfs×d2,d≤d0l×ETx+l×εmp×d4,d>d0,
where d0 is the threshold distance [17] and is given via d0=εfs/εmp. The energy dissipation that the receiver requires to receive an l-bit message is ERx(l)=l×Eelec. Eelec is the energy consumed per bit to run the receiver or the transmitter circuit, εfs and εmp depend on the transmitter amplifier model, the energy for data aggregation EDA is set to 5 nJ/bit/message [18].


## 2.1. Network Model

We assume a number ofN wireless sensor nodes distributed among an M×M squared field randomly. Sensed data are gathered in a periodical way, and we define each period as a round. Each round contains three phase, a set-up phase uses DCH-NPSO to part the network into clusters and selects MCH and SCH using Niching PSO, a steady phase when data collected and aggregated by the MCH, and a finish phase followed when data is transmitted to the BS (Base Station, also called sink node); the steady phase should be longer than other phases to minimize the energy dissipation. The MCH is used for data collection and data aggregation. The aggregated data are sent to the SCHs, and then the SCHs transmit it to the sink node directly and get some information through a piggyback manner to save more energy. The partial structure of the network in a round is as shown in Figure 1.Figure 1
DCH-NPSO partial network architecture.We make assumptions about the network model as follows.(i)
All nodes are equipped with small batteries, so each node has initial energy allocated and the energy is constrained.(ii)
A BS situates far away from the sensing field, and it has no energy constraints.(iii)
Each node has its location information. There are a number of existing works on localization in WSNs [14–16]. For example, we use the solution proposed in [16] to obtain the localization.(iv)
All nodes are equipped with power control units to adjust the transmit power according the distance.(v)
All nodes have no mobility.


## 2.2. Radio Model

The radio model we adopt is as used in [10]. In this model, the transmitter dissipates energy to drive the amplifier and the radio components, and the receiver dissipates energy to drive the radio components. The transmitter has power control ability to properly set the amplifier according to the distance and can be turned off to avoid receiving unintended sensing data, to minimize the energy consumption. The energy dissipation for transmit an l-bit packet over distance d is
(1)ETxl,d=Eelec(d)+Eampl,d=l×ETx+l×εfs×d2,d≤d0l×ETx+l×εmp×d4,d>d0,
where d0 is the threshold distance [17] and is given via d0=εfs/εmp. The energy dissipation that the receiver requires to receive an l-bit message is ERx(l)=l×Eelec. Eelec is the energy consumed per bit to run the receiver or the transmitter circuit, εfs and εmp depend on the transmitter amplifier model, the energy for data aggregation EDA is set to 5 nJ/bit/message [18].


## 3. DCH-NPSO Protocol

Our proposed protocol takes full advantage of Niching PSO for clustering, takes the network states information into account deliberately, and selects SCH to balance the energy dissipation to improve the energy efficiency.


### 3.1. Niching Particle Swarm Optimization

Particle swarm optimization is a bionic optimization that is inspired by nature such as bird flocking and fish school, and it was first put forward by Kennedy and Eberhart [19]. In a classic PSO, a number of m particles fly at a certain speed, respectively, in a D-dimension space, and each particle has a fitness value on the basis of the fitness function which is defined as related to the problems. The particles fly towards the position defined as personal best position and global best position (i.e., the best position refers to a position that gives the best fitness value). During each iteration, the particles’ velocity and position are updated based on the following equations, respectively:
(2)vidk+1=ωvidk+c1ξpidk-xidk+c2ηpgdk-xidk,(3)xidk+1=xidk+vidk+1,
where vid is particle i’s velocity in d dimension, k stands for the current iteration, xid is the particle i’s position in d dimension, ω is the inertia weight, deciding how the particle inherit present velocity, c1 and c2 are acceleration coefficient (or called learning factor) which are positive constants normally, ξ and η are stochastic numbers between 0 and 1, pid is the particle’s best position, and pgd is the global best position [20, 21].When the issue target is to find multiple global optima, niching methods are valuable and efficient. Niching PSO searched in parallel, so the chance of getting trapped into a local optimum is reduced [7, 9]. There has been a lot of existing work on niching methods [7–9]; in this paper, we use a ring topology niching method as [7], and each particle interacts with its immediate neighbors only.


### 3.2. The Fitness Function of NPSO

The fitness function is closely correlated with the features of the problem and determines the property of the optimal solution directly. So, the design of the fitness function is very important. Based on [3, 12], we consider the conditions that affect the system performance and define the fitness function deliberately and comprehensively. At first, we should take the residual energy of the sensor node into account, because if the node becomes the MCH, it dissipates more energy than the member nodes. Then, the distance between the MCH and its member nodes should be considered as the MCH takes charge of gathering data from its member nodes. At last, we should take the distance between the SCH and the BS into account as SCH sends the aggregated data to the BS directly. We define the fitness function f(i) of node i based on these considerations:
(4)fi=αf1i+βf2i+γf3i,f1i=∑i=1NEni∑k=1koptECHp,k,f2i=∑k=1kopt∑∀ni∈Cp,kdni,CHp,kCp,k,f3i=dCHp,k,BSkopt∑k=1koptdCHp,k,BS,0≤α,β,γ≤1,α+β+γ=1,
where ni is the sensor node i, E(ni) is the residual energy of sensor nodes i, CHp,k is the nodes that belong to cluster Ck of particle p, N is the number of node alive in the network, and kopt is the optimal number of clusters in the network [10, 12], so f1(i) takes the network’s energy efficiency into account and select the nodes that has more residual energy as cluster head. Cp,k is the number of nodes that belong to cluster Ck of particle p, d(ni,CHp,k) is the Euclidean distance between them, so f2(i) minimizes the intracluster distance between the CH and its member nodes, and f3(i) minimizes the distance between the CHs and the BS. The fitness function f(i) has the maximum of the residual energy and the minimum of the distance between the nodes among the cluster and the distance between the CH and the BS. So, based on the above fitness function, we choose the node that has the maximum fitness value as MCH and the suboptimal solution as SCH, that is the optimal selections during that round.


### 3.3. DCH-NPSO Setup

The proposed protocol runs in periodic way, and we use Niching PSO and the fitness function (4) to select the optimal set of CHs and their member nodes. The sensed data transmissions begin after the clusters have been selected; each MCH gathers and aggregates the data collected from its members. The aggregated data are sent to the SCH, and the SCH transmits the data to the BS directly. The flowchart of DCH-NPSO is shown in Figure 2.Figure 2
The flowchart of the DCH-NPSO protocol for cluster setup.The MCH sets up a TDMA schedule for its member nodes to avoid collection during data transmission, allowing the radio units to be turned off at all times except the transmission period for each member sensor. And we use a fixed spreading code and CSMA (Carrier Sense Multiple Access), a similar approach used in [22] during data transmission to minimize and balance the energy dissipation. Once the MCH finishes gathering data from its member sensors, the MCH performs data aggregation and sends the aggregated data to the SCH and then the SCH sends the aggregated data to the BS directly.


## 3.1. Niching Particle Swarm Optimization

Particle swarm optimization is a bionic optimization that is inspired by nature such as bird flocking and fish school, and it was first put forward by Kennedy and Eberhart [19]. In a classic PSO, a number of m particles fly at a certain speed, respectively, in a D-dimension space, and each particle has a fitness value on the basis of the fitness function which is defined as related to the problems. The particles fly towards the position defined as personal best position and global best position (i.e., the best position refers to a position that gives the best fitness value). During each iteration, the particles’ velocity and position are updated based on the following equations, respectively:
(2)vidk+1=ωvidk+c1ξpidk-xidk+c2ηpgdk-xidk,(3)xidk+1=xidk+vidk+1,
where vid is particle i’s velocity in d dimension, k stands for the current iteration, xid is the particle i’s position in d dimension, ω is the inertia weight, deciding how the particle inherit present velocity, c1 and c2 are acceleration coefficient (or called learning factor) which are positive constants normally, ξ and η are stochastic numbers between 0 and 1, pid is the particle’s best position, and pgd is the global best position [20, 21].When the issue target is to find multiple global optima, niching methods are valuable and efficient. Niching PSO searched in parallel, so the chance of getting trapped into a local optimum is reduced [7, 9]. There has been a lot of existing work on niching methods [7–9]; in this paper, we use a ring topology niching method as [7], and each particle interacts with its immediate neighbors only.


## 3.2. The Fitness Function of NPSO

The fitness function is closely correlated with the features of the problem and determines the property of the optimal solution directly. So, the design of the fitness function is very important. Based on [3, 12], we consider the conditions that affect the system performance and define the fitness function deliberately and comprehensively. At first, we should take the residual energy of the sensor node into account, because if the node becomes the MCH, it dissipates more energy than the member nodes. Then, the distance between the MCH and its member nodes should be considered as the MCH takes charge of gathering data from its member nodes. At last, we should take the distance between the SCH and the BS into account as SCH sends the aggregated data to the BS directly. We define the fitness function f(i) of node i based on these considerations:
(4)fi=αf1i+βf2i+γf3i,f1i=∑i=1NEni∑k=1koptECHp,k,f2i=∑k=1kopt∑∀ni∈Cp,kdni,CHp,kCp,k,f3i=dCHp,k,BSkopt∑k=1koptdCHp,k,BS,0≤α,β,γ≤1,α+β+γ=1,
where ni is the sensor node i, E(ni) is the residual energy of sensor nodes i, CHp,k is the nodes that belong to cluster Ck of particle p, N is the number of node alive in the network, and kopt is the optimal number of clusters in the network [10, 12], so f1(i) takes the network’s energy efficiency into account and select the nodes that has more residual energy as cluster head. Cp,k is the number of nodes that belong to cluster Ck of particle p, d(ni,CHp,k) is the Euclidean distance between them, so f2(i) minimizes the intracluster distance between the CH and its member nodes, and f3(i) minimizes the distance between the CHs and the BS. The fitness function f(i) has the maximum of the residual energy and the minimum of the distance between the nodes among the cluster and the distance between the CH and the BS. So, based on the above fitness function, we choose the node that has the maximum fitness value as MCH and the suboptimal solution as SCH, that is the optimal selections during that round.


## 3.3. DCH-NPSO Setup

The proposed protocol runs in periodic way, and we use Niching PSO and the fitness function (4) to select the optimal set of CHs and their member nodes. The sensed data transmissions begin after the clusters have been selected; each MCH gathers and aggregates the data collected from its members. The aggregated data are sent to the SCH, and the SCH transmits the data to the BS directly. The flowchart of DCH-NPSO is shown in Figure 2.Figure 2
The flowchart of the DCH-NPSO protocol for cluster setup.The MCH sets up a TDMA schedule for its member nodes to avoid collection during data transmission, allowing the radio units to be turned off at all times except the transmission period for each member sensor. And we use a fixed spreading code and CSMA (Carrier Sense Multiple Access), a similar approach used in [22] during data transmission to minimize and balance the energy dissipation. Once the MCH finishes gathering data from its member sensors, the MCH performs data aggregation and sends the aggregated data to the SCH and then the SCH sends the aggregated data to the BS directly.


## 4. Simulation

We perform the simulations to evaluate the proposed protocol’s performance. We assume that in a100m×100m-squared sensing area, 100 sensor nodes are distributed randomly, and the BS is situated at (50,175)m, the data message length is 75 bytes with 15-byte packet header. The simulation parameters are given in Table 1, in which the radio parameters are as described in Section 2 and particle swarm optimization is as described in Section 3, and we use ring topology as in [7] to form niching. The performances of our proposed protocol are compared with clustering protocol LEACH, LEACH-C [10], and PSO-C [12].Table 1
Simulation parameters for DCH-NPSO.
Parameter
Value
E
elec
50 nJ/bit
ε
f
s
10 pJ/bit/m2
ε
m
p
0.0013 pJ/bit/m4
E
DA
5 nJ/bit/message
c
1
2.5~0.5
c
2
0.5~2.5
ω
0.8~0.3We use the number of rounds to measure the number of nodes alive during the simulation; it as shown in Table2. We can see that, as for LEACH, the first node is “dead” (i.e., the node has consumed all its initial energy) in 725 rounds, LEACH-C in 843 rounds and PSO-C in 954 rounds, while DCH-PSO in 1134 rounds, and our proposed protocol prolongs the network lifetime about 410 rounds compared to LEACH. The reason is that LEACH and LEACH-C do not take the residual energy of sensor nodes into account and select cluster head randomly, although PSO-C can prolong the network lifetime compared to LEACH and LEACH-C; it still does not balance the energy consumption. Our protocol DCH-NPSO takes the residual energy into account and selects SCH in each cluster, which balances and minimizes the energy consumption.Table 2
Network lifespan comparison.
Protocol
First node dead
Half nodes dead
All nodes dead
LEACH
725
1053
1418
LEACH-C
843
1136
1580
PSO-C
954
1308
1636
DCH-NPSO
1134
1545
1788Figure3 shows the total data messages received at the BS, the plot clearly indicates the effectiveness of the proposed protocol that delivers more data messages than LEACH, LEACH-C, and PSO-C, because the proposed protocol takes advantage of higher energy sensors such as MCHs by considering the residual energy of the nodes and selects SCH to balance the energy dissipation. Thus, more data messages are transmitted to the BS. In contrast, LEACH does not consider the residual energy of a sensor node when choosing the MCH and may choose the MCH with insufficient energy to stay alive during the data transmission phase. Although PSO-C takes the node’s residual energy and the intracluster distance into consideration, it does not take actions to balance the energy consumption, while our protocol divides the network into clusters evenly, takes the nodes residual energy and the intracluster distance into account during the MCH selection, and selects SCH to balance the energy dissipation.Figure 3
The flowchart of the DCH-NPSO protocol for cluster setup.As can be seen from Figure3 and Table 2, the protocol we proposed can prolong the network lifetime and transmit more sensed data to the BS and thus improves the system robustness and enhances the system scalability. LEACH, LEACH-C, and PSO-C, on the other hand, either generate an uneven distribution of cluster heads throughout the network or do not balance the energy dissipation. Our protocol produces performs even clustering distribution and selects SCHs to balance the energy consumption.


## 5. Conclusion

In this literature, we have presented an energy distance aware clustering protocol with Dual Cluster Heads using Niching Particle Swarm Optimization (DCH-NPSO). We uses Niching PSO to select MCH and SCH in a cluster, taking the factors such as residual energy and the distance into account to balance and minimize the energy consumption. Results from the simulations show that the proposed protocol using Niching PSO prolongs the network lifetime and delivers more data to the BS compared to LEACH, LEACH-C, and PSO-C. Our future work includes the multihop routing among the network and explores rational parameters of Niching PSO to further improve the energy efficiency and the system performance.



---

*Source: 849281-2015-02-11.xml*