Improving Energy Efficient Clustering Method for Wireless Sensor Network

Published Online August 2013 in MECS

Wireless Sensor Networks (WSNs) can offer unique benefits and versatility with respect to low-power and low-cost rapid deployment for many applications which do not need human supervision. The nodes in WSNs are usually battery operated sensing devices with limited energy resources and replacing or replenishing the batteries is not usually an option. Thus energy efficiency is one of the most important issues and designing power-efficient protocols is critical for prolonging the lifetime. The latest developments in time critical, low cost, long battery life, and low data rate wireless applications have led to work on wireless sensor networks. These WSNs have been considered for work in certain applications with limited power, reliable data transfer, short communication range, and reasonably low cost such as industrial monitoring and control, home automation and security, and automotive sensing applications [1]. The WSNs consist of a set of sensors that communicate with each other to form a sensor field. These large numbers of nodes, which have the ability to communicate wirelessly, to perform limited computation, and to sense their surroundings, form the WSN [2].

The core operation of wireless sensor network is to collect and process data at the network nodes, and transmit the necessary data to the base station for further analysis and processing. In order to enhance the network life time by the period of a particular mission, many routing protocols have been devised. One of these is network clustering, in which network is partitioned into small clusters and each cluster is monitored and controlled by a node, called Cluster Head (CH). These cluster heads can communicate directly with the base station (BS). Other nodes send the data, sensed from the environment to these CHs. CHs first aggregate the data from the multiple sensor nodes and then finally send it directly to the BS. Hence the CH should be powerful, closer to the cluster-centroid, less vulnerable [3] and has to have low mobility. Heinzelman et al. proposed LEACH [4] a protocol based on network clustering. Each cluster has a cluster-head that aggregates all the data received from the near nodes and send them to the base station. The cluster-head are selected following a distributed algorithm for each round. Every transmission round the node elects itself to be a clusterhead. Once the clusters are formed, the cluster- head broadcasts in its cluster a data message containing its measurement assuming it the pertinent value. Only the nodes, having most significant data, send their messages towards the cluster-head. The [5] proposed an algorithm called IELP which is an improvement of the LEACH one. This algorithm permits to dominate the number of clusters heads to have at any transmission round, the optimal cluster-heads amount. That modifies the cluster-head selection algorithm to improve the partition of cluster. This algorithm assumes that all nodes receive the messages broadcasted by the nodes selected as cluster-heads. On one hand, if a node is not reachable by a cluster head it assumes that the number of clusters heads is insufficient, and elects them to be cluster head, and therefore the number of cluster-heads may be not dominated, on the other hand, this is not real with the large networks because the those messages cannot reach all the network. The major issues stemming from these studies are protocol design in regards to battery energy efficiency, localization scheme, synchronization, data aggregation and security technologies for wireless sensor networks. In particular, researchers have shown great interest in the routing protocols in the network layer, which considers self-organization capabilities, limited battery power, and data aggregation schemes. In this paper, we proposed an enhanced cluster reconfiguration algorithm for a routing protocol of wireless sensor networks based upon the LEACH routing protocol. The proposed algorithm extends the survival time of sensor networks by properly choosing cluster heads with consideration to node residual energy and count neighbor node.

• II.    Problem Formulation

  LEACH use a random method with a self-organizing clustering based protocol to evenly distribute energy loads between each sensor, coincidently electing CH with a probability. In this protocol, Cluster Head selection is done in setup phase (Heinzelman et al., 2000), by considering two factors. First, the desired percentage of nodes in the network and second the history of node that has served as cluster head. For selecting CHs, each sensor chooses a random number between 0 and 1 inclusive. If this is lower than the threshold for node n, T(n), the sensor node becomes a cluster head. The threshold T (n) is given by (1)

p

T ( n ) = J 1 - p ( r * mod—) ^p

if n€G otherwise

P represents a probability of electing as CH out of entire nodes, r means current round, and G is node group that is not elected as head in previous 1/P round.

Once the nodes have elected themselves to be cluster heads they broadcast an advertisement message. Each non cluster-head node decides its cluster for this round by choosing the cluster head that requires minimum communication energy, based on the received signal strength of the advertisement from each cluster head. After each node decides to which cluster it belongs, it informs the cluster head by transmitting a join request message (Join-REQ) back to the cluster head as depicted in Fig. 1.

Fig. 1: Time line operation of LEACH

The cluster head node sets up a TDMA schedule and transmits this schedule to all the nodes in its cluster, completing the setup phase, which is then followed by a steady-state operation. The steady-state operation is broken into frames, where nodes send their data to the cluster head at most once per frame during their allocated slot.

Although LEACH is able to increase the network lifetime, there are still a number of issues about the assumptions used in this protocol. LEACH assumes that all nodes can transmit with enough power to reach the BS if needed and that each node has computational power to support different MAC protocols. Therefore, it is not applicable to networks deployed in large regions. It also assumes that nodes always have data to send and nodes located close to each other have correlated data. It is not obvious how the number of predetermined Cluster Heads is going to be uniformly distributed throughout the network. Therefore, there is a possibility that the elected CHs will be concentrated in one part of the network. Hence, some nodes will not have any CHs in their vicinity.

This following approach presents a protocol to efficiently harness sensors energy which called the IELP. What is suggested to resolve this problem of LEACH is the IELP, where the energy of sensor node is used by leveraging energy as parameter in defining value of T (n) which based on the initial energy and number of neighbor of that nodes. This solution is more applicable compared to any solution which assumes that each node knows the total energy of the network and then adapts its election probability to become a cluster head according to its remaining energy [6]. Our approach is to assign a weight to the optimal probability p . This weight must be equal to the initial energy of each node divided by the initial energy of the normal node. Let us define as p the weighted election probability for normal nodes, and p the weighted election probability for the advanced nodes.

Virtually there are n x (1+α.m) nodes with energy equal to the initial energy of a normal node. In order to maintain the minimum energy consumption in each round within an epoch, the average number of cluster heads per round per epoch must be constant and equal to n X p . In the heterogeneous scenario the average number of cluster heads per round per epoch is equal to n x(1+α.m)x p . The weighed probabilities for normal and advanced nodes are, respectively:

last     rounds of the epoch, T(      ) is the threshold applied to a population of n.(1+m)(normal) nodes, is the initial energy and is the number of neighbor of the i-th node. This guarantees that each normal node will become a cluster head exactly once every rounds per epoch, and that the

Popt average number of cluster heads that are normal nodes per round per epoch is equal to n.(1+m)x     .

Similarly, for advanced nodes, we have:

T ( S ad, ) = ^

adv

1 - P , ( r * mod ¹  )

adv

P adv

* -г-

N i

"

nrm otherwise

where    is the set of advanced nodes that have not become cluster heads within the last      rounds of the epoch,T(     )is the threshold applied to a population of n .m (advanced) nodes,     is the initial energy and

= the number of neighbor of the i- th node. These guarantees that each advanced node will become a

1   1+ a.m cluster head exactly once every             round.

р nrm

р opt

1 + a. m

is the number of neighbor i sensor node. The number of nodes which receive power (R) that transmitted from sensor node i is known as neighbor node . The receive power (R) must be less than or equal to threshold level (T) i.e. (R

P

PdV. =         X (1 + a)1 + a. m

In Equation (1), we replace by the weighted probabilities to obtain the threshold that is used to elect the cluster head in each round. We define as T( ) the threshold for normal nodes, and T( ) the threshold for advanced nodes. Thus, for normal nodes, we have:

Fig. 2: Calculate neighbor node for each node

nrm

T (Snrm ) ^

1- ^Pnrm⁽r * mod^) nrm

Ni

if Snrm€G^'

otherwise

wherer is the current round, is the set of normal nodes that have not become cluster heads within the

III. Radio Model

Two conventional routing protocols in wireless network that we will discuss in this section are direct communication and minimum-transmission-energy

routing protocol (MTE). Recently, there is a significant amount of work in the area of building low-energy radios. We assume a simple model for the radio hardware energy dissipation where the transmitter dissipates energy to run the radio electronics and the power amplifier, and the receiver dissipates energy to run the radio electronics (this model is used in many works like [7, 8, 9]), as shown in Fig.3. For the experiments described here, both the free space ( power loss) and the multi path fading ( power loss) channel models were used, depending on the distance between the transmitter and the receiver [10]. If the distance is less than a threshold, the free space (fs) model is used; otherwise, the multi path (mp) model is used.

Transmitter

Receiver

Fig. 3: Radio energy dissipation model

Thus, to transmit a -bits message over a distance d, the radio expends (4):

EtX (l, d ) = Etx - elec (l) + Etx _ amp (l, d )       (4)

ETX(l,d)

l.Eelec

l.Eelec

+l .€fi d2 ifd < d

+l .€ _mp,d ⁴ ifd > d о

Where the threshold is (6):

^d о =

€

fs

\ € mp

The electronics energy (      ) depends on many factors such as the digital coding, the modulation, the

filtering, and the spreading of the signal, whereas the amplifier energy, or €mp. , depends on the distance to the receiver and the acceptable bit-error rate. To receive an l-bit message, the radio expends (6):

ErX (l) = ErX - elec (l) = l. Eelec (6)

It is also assumed that the radio channel is symmetric, which means the cost of transmitting a message from A to B is the same as the cost of transmitting a message from B to A. The electronics energy depends on factors such as the digital coding, modulation, filtering, and spreading of the signal, whereas the amplifier energy depends on the distance.

These parameters were used for the theoretical and simulation work described in this paper.

Table 1: Radio Model Communication Parameters

Description	Value
Energy consumed by the amplifier to transmit at a shorter distance,	10pJ /bit/m2
Energy consumed by the amplifier to transmit at a longer distance,	0.0013 pJ/bit ^
Energy consumed in the electronics circuit to transmit or receive the signal,	50nJ/bit
Energy consumed for beam forming, EDC	5„J/bit /signal
Sensor Deployment Area	100m x 100m
Number of Nodes	100
Data Message Size	500 bytes
Packet Header	25 bytes
BS Location	(50,50)m

• IV.    Simulation Result

• 4.1    Node Lifetime Simulation

In this section, we evaluate the performance of the new energy efficient protocol implemented with MATLAB. In our simulation environment, we assume that all nodes always have data to send and sensor devices are not with mobility, same initial energy, and capable of transmission range adjustment [11]. Furthermore, for correctness of simulation, initially base station provides address localization for each sensor. We compared their performance with LEACH and SEP[12]. The criteria for performance comparison we used are the sensor lifetime, the energy consumption and cluster formation.

In this case the stable region of the clustering hierarchy process using the characteristic parameters of heterogeneity, namely the fraction of advanced nodes (m) and the additional energy factor between advanced and normal nodes (α).

Fig. 4: Distributed node in network environment

Fig. 5 shows number of alive nodes using LEACH in the presence of heterogeneity m=0.1 and α =2 (100 nodes with energy 0.5J) is call SEP and propose of IELP protocol. The simulation results show in the table-3 the performance of IELP has an improvement of 39% over LEACH and 15% over SEP in the area of 100m*100m with parameter value( m=0.1 , α =2) and 43% over LEACH and 19% over SEP in the area of 100m*100m with parameter value( m=0.2 , α =1).

Fig. 5: The number of alive nodes vs. the number of round

Parameter value	Protocol	First Node Dies
m=0.1, α =2	IELP	1257
	SEP	1061
	LEACH	762
m=0.2, α =1	IELP	1350
	SEP	1092
	LEACH	762

Table 3: Improvement of IELP

Parameter value	Protocol	Improvement
m=0.1, α =2	SEP	15%
	LEACH	39%
m=0.2, α =1	SEP	19%
	LEACH	43%

In fig. 7 and fig. 8, X axis represents node death percentage (percentage of nodes with no power) and Y axis represents number of round.

Fig. 7: Node death percentage v.s. # of Rounds

100m x 100m, 100 nodes, m=0.2, a=l

Fig. 8: Node death percentage v.s. # of Rounds

• 4.2    Energy-time Simulation

Fig. 9 shows the energy consumption, where X-axis is the simulation time and Y-axis is the total energy consumed during simulation. Comparing the energy consumption in the entire number rounds, it can be seen that the reduction in energy of IELP is slower than the reduction in energy of SEP. It is known that SEP consumes all of the energy at 2230 rounds, but IELP is finished in about 4397 rounds

^ Energy ( n )Average Energy =---—-----------

Number of alive Node

Energy(n) = Remaining Energy at Node n .

Fig. 9: Energy vs the number of round

• V.    Conclusion