CHEFC: Cluster Head Election with Full Coverage in Wireless Sensor Networks

Mohammad Mehdi Shirmohammadi#1, Mostafa Chhardoli#2, Karim Faez *3 # Islamic Azad University hamedan branch

Hamedan,Iran 1,2{mmshirmohammadi,chhardoli}@gmail.com

* EE department of Amirkabir University of Technology Tehran,Iran

3kfaez@aut.ac.ir

Abstract— This article aims to deal with the purposeful election of the cluster head(Leader) in the Wireless Sensor Networks (WSNs). The basic protocol to choose the cluster head(CH) in such networks is LEACH (low-energy adaptive clustering hierarchy) which somehow will realize the election of CH in the network and needs no program for full coverage of the CH. This article by introducing a new protocol called CHEFC (Cluster Head Election Full Coverage) is able to tackle with the problem of CH vacancy in the different parts of the network. The function of this protocol is as follows: each sensor should usually have a CH in it vicinity, and unlike the previous protocol, there is no need for each sensor spends more energy to be connected with its own CH located in a farther distance. This protocol which acts on a distributed basis will lengthen the lifetime of the wireless sensor network as well as fully covering the CH in the network. In addition, after simulation and comparison based on LEACH protocol, it was clearly observed that CHEFC protocol has a higher conductivity which means the higher number of the CHs in each round of the network activity as compared with previous protocol Keywords— Cluster Head, Full Coverage, Election, Wireless Sensor Networks, Clustering.

I. INTRODUCTION The technology development in building small circuits has

led to using the wireless technology in most electronic equipments. It has also led to bringing more progress on the sensors that are smaller, less consumptive, and less costly. These small sensor nodes include three important features: the sensor, data processing, and wireless data transfer. These when applied side by side enjoy the potentiality of tackling with numerous senses in the work such as: recognition and collection of data and status control; from now on we call them a network.

A wireless sensor network includes numerous sensors to sense the event, whose data is processed in the main station of the network collectively. In such networks the failure of one node has no effect on sensing the events. Moreover, the location of the nodes in the network is not predetermined and they are assembled in a self-organized style.

WSNs that are used in a wide range of fields such as: military, health, environment, industry, agriculture, entertainment and research. [5] have attracted the attention of

so many researchers which has led to a little revolution in data transformation.

A WSN contains a great number of sensors which are connected together through radio frequencies (RF). The architecture of sensor networks is such that allows the sensors to be randomly (or indiscriminately) be distributed in an area and recognize, control and process the events and finally link them to a station called sink. [1]

The most important features in designing a sensor network are fault tolerance, scalability, manufacturing costs, hardware limitations, environment and energy consumption.

A. Clustering in WSNs Some protocols in WSNs use clustering with the aim of

load balancing, scalability, fault tolerance, connection increase, delay decrease and soon [4], is considered as architecture for WSN. The function of this architecture is on the following: the sensors are divided into some zones in which there is one CH and after any event's happening the sensors of that zone send their data to the CH and it is the CH which dispatches the data directly to the Sink.[2,9] (Fig 1)

Among the most important and basic features of WSNs, we can consider those which are self-organized in the environment while covering short distances and make connections through multi-step navigation. Also, these networks due to failures, energy limitations and memory and power of connectivity, enjoy a variant topology.[7]

Fig. 1 clustering in WSNs

Proceedings of the 2009 IEEE 9th Malaysia International Conference on Communications 15 -17 December 2009 Kuala Lumpur Malaysia

978-1-4244-5532-4/09/$26.00 ©2009 IEEE 780

In this article through introducing CHEFC, the election of CH with the aim of the homogeneous distribution of the CH in the network is carried out. This new method in addition to guarantying the existence of the CH in the neighborhood of the node can increase the network's lifetime. Furthermore, the number of CHs in each rounds of the network's activity is higher as compared with LEACH protocol which shows the higher conductivity and the increased accuracy in data collection through using the new protocol In part 2, this article will study the previous protocols as far as the election of CH is concerned; and in part 3, describes the new protocol. Then, in part 4 it aims to explain the issues related to simulation process which is followed by part 5 which is the conclusion.

II. RELATED WORK The LEACH protocol is on of the most famous hierarchical

protocols. In this protocol the time is divided into parts each called a round. Each round also consists of two phases. The first phase is called setup phase which in fact is the phase of node formation. The second phase is related to the normal function of the network and is called the Steady-State phase.

In the first phase, the CHs are elected based on a probability function. This election is as follows: each sensor node through producing a random figure and it’s comparison with a threshold limit decides to be a CH and during that round the node is chosen as the CH. This probability function is designed in such a way that within a specific number of rounds each sensor becomes a CH only once and thus the energy consumption is distributed over the whole network. After the set up phase of the round which, the CHs are elected, each CH announces its election to other nodes and each node chooses a suitable (close) CH for it self; and then it announces this decision to the related CH and thus the clusters are formed.

There fore, the LEACH protocol work based on clustering in which the clusters are formed randomly in an adaptive and self-organized way. By random we mean that a certain number of nodes randomly announce themselves as CH in each round. By adaptive, we mean that the nodes which undertake the role of the CH in the current rounds cannot be candidate to play that role in the next round until a certain time. And finally, by self-organized we mean that the nodes in the network form clusters without any help from any external agent or a certain node in the network.

In the second phase which consists of some time frames, each sensor sends its own data to the CH within its own time frame and the CH, after combining all the received data, will send the results to the main station, Fig 2 shows this time division.

Fig. 2 Time segmentation in LEACH protocol

The LEACH algorithm emphasizes the election of the CHs

randomly and through a fixed probability (it means all the

sensors have an equal probability to become a CH.) [2] In this algorithm the sensors are distributed randomly in a zone and there is always an assumption that the sensors are not mobile.

In LEACH protocol, there is no mechanism for locating the CH in the network. There fore, a major problem with LEACH protocol is that it is possible that there is no CH in some parts of the network while in other parts there are a few CHs side by side.[3](Fig 3)

Fig. 3 the simulation of a round of clusters distribution in LEACH protocol

In Fig 3, one round of simulation in LEACH protocol is

shown. As it is shown in zone B (the highlighted zone) there is no CH (black spot) and in a zones A (two tiny zones which are also highlighted), there are two CHs side by side. This is on of the major problem with LEACH protocol and this research tried to solve this problem in its own way.

The most important aim of LEACH is in collecting data and regarding the fact that it does not need a heavy navigation table it has lower overhead; therefore, it is one of the successful protocols of its own time, and it is considered as a basic protocol in clustering the WSNs.

This protocol function as follows: each sensor through generating a random number decides to be the CH or not. Concerning the random election of CHs, there is a probability that density of CHs in part of the network be high in some rounds of the networks activity; therefore, in other zones the sensor sees no CH in its neighborhood and they have to use more energy to be connected to the CH that is in the further distance.

Generally, there is no logical rule which has an effect on the nodes being elected as the CH; therefore, LEACH can make possible the election of the CH in the network just through its own way.[2] And this is referred to as the most important protocol in clustering due to its distributed function.

With regard to the relation 1 in this protocol, if a sensor is elected as CH, it cannot be the CH till 1/p in the next round. p is the probability of the sensors becoming the CH. In this protocol those sensors not elected to be CH will be a member of G (so that the CH can be elected among the G set in the next round). In the beginning of each round, every sensor which belongs to G set is elected independently using a random figure between [0,1]; if the random figure is lower

781

N

C

M L

than the threshold limit T(n), the sensor will be elected CH in the current round. Therefore, the threshold limit is computed by the relation:

(1)

Here the first part of the relation occurs when n Є G, and r will also defined the number of the current round (which begins from zero).

In this part since it was important for us how to choose the CH, therefore the set up phase of LEACH protocol was discussed and for more information about the function of this protocol, one can refer to source[2].

III. CHEFC PROTOCOL This new protocol can solve the problem of the heterogeneous distribution of CHs in the network. The problem is as follows: in election of CHs in LEACH protocol it was possible fore the CH nodes to be side by side or there be no CH in one zone at all; However, due to the randomly clustering the cluster area may be too large to consume large energy for the CH.[6]

This protocol has the same function as the LEACH protocol and it defers from LEACH only in the number of CHs and the way they are elected. Therefore, the new protocol still enjoys the distributed function and randomly elects the CH.

The advantage of CH election in CHEFC protocol is that its CH coverage expands all over the network, hence increasing the networks lifetime and improving the new protocols conductivity as compared with LEACH. Fig 4 shows the CHEFC protocol's function: 3 6 7 1 2 4

5

Fig. 4 The diagram of algorithm phases

At first, all sensors are in N position and all nodes are considered to be of ordinary type. Each node, at first, looks for a CH in its neighborhood; if there was a CH it will enter into M position as a member (are number 1), but if there was no CH in the neighborhood, it will be candidate for leadership based on a certain probability and enters into position C (are number 2). It is also possible in position N that it stays unchanged based on a certain probability and proceed with a new trend (are number 3). It means if it finds no CH in its neighborhood, it will be candidate for leadership based on a certain probability; otherwise, it will remain unchanged.

In position C the candidate node investigates its own neighbors and if there was another candidate among them it will go to position N again (are number 4), but if it sees no candidate for leadership among the neighbors it goes to position L and becomes a CH (are number 5).

Also, in position M and L if the energy of the CH is lower than the threshold limit (the amount of the leader's energy of the neighbors defines the threshold limit), it cannot remain the CH any more and it goes into position M (are number 6 and 7).

These two positions (movements) happen if one CH giving up the leadership (energy decrease) in phase 6 enters position N (ordinary sensor), so that it may face a new decision with regard to its neighbors. The sensor which was a member of a CH in position M and its CH has given up, should inter the N position to be a member of a new CH or be elected itself as a CH.

This trend to implement the protocol is carried out in several phases so that the full CH coverage in the network is realized. The important advantage of the algorithm is its distributed function in which if a CH gives up or loses life (i.e. at the end of its lifetime), the protocol in the some zone independently elects another node as its CH. The trend for implementing the project is feasible, as far as there is no node in position N, it means all the nodes should be the CH. After these phases were implemented entirely in the network, the change will occur in those points of the network where the CH wants the changing trend to occur in a distributed style only in that part of the network (the CH and its subset nodes) while having no effect no the other pars.

The function of this protocol can be explained in several phases providing each with an example. If the total number of the sensors is assumed to be one hundred, it will be possible to have fourteen sensors as candidates and eighty six as ordinary nodes in the first phase; then from among the fourteen sensors and the candidate nodes, those nodes will be the CHs which have no candidate in their neighborhood. It is possible to elect five as the CHs and the other nine sensors will see candidate sensors in their neighborhood and turn to be ordinary sensors again; then these phases are carried out for 95 remaining sensors and through implementing this trend of algorithm the CHs are gradually elected from among the ordinary sensors (with the aim of the full coverage of network with no spatial overlap between CHs while having no two CHs side by side).

In this article in order to provide the relation between the sensors a model similar to the one in reference 3 has been used.

Fig. 5 The radio model of energy

According to the radio model of energy consumption

introduced in Fig 5, to reach an acceptable rate of Signal-to-Noise (SNR), the allocated energy to send the message with

782

the length of L-bit in the distance of d is calculated through the relation:

(2)

Eelect is the consumed energy for each bit in the transmitter circuit or receiver circuit; Єmp and Єfs depend on the model boosting the transmitter circuit and d is the distance between the transmitter and receiver which in case of d=do we have do=√ (Єfs/ Єmp) ; to receive the L bit message the radio energy consumed is equal to relation 3 [3]: ERx=L.Eelec (3) The energy consummation by the CH during the round is also computed through the relation 4:

(4) K determines the number of clusters and EDA is the cost of processing (aggregate the data) of each bit to be reported to sink; and the dtoBS is the mean distance between the CH and sink. The energy consumed by the non-leader sensors is computed through the relation 5:

(5) and dtoCH is the mean of distance between the CH and the sensor.[3]

A. Performance measures Stability Period: is the time interval from the start of network operation until the death of the first sensor node. Instability Period: is the time interval from the death of the first node until the death of the last sensor node. We also refer to this period as “unstable region.” Network lifetime: is the time interval from the start of operation (of the sensor network) until the death of the last alive node. Number of CHs per round: This instantaneous measure reflects the number of nodes which would send information aggregated from their cluster members directly to the sink.(throughput) [3] The simulation of this protocol and its concluding results are explained in the next part.

IV. SIMULATION OF CHEFC To carry out this simulation, a clustered wireless sensor

network in a zone with the dimensions of 100×100 and the homogeneous distribution of 100 sensors (randomly) was simulated through using NS2.27 software. In this simulation the sink is located at the center, and the distance between the sensors and Sink is 70m at the most. The initial energy of all sensors is Eo=0.5 j.

TABLE I RADIO CHARACTERISTICS USED IN OUR SIMULATION

Operation Energy dissipated Transmitter/Receiver

ElectronicsEelec=50nJ/bit

Data Aggregation EDA=5Nj/bit/report Transmit Amplifier

0dtoBS<=d Єfs=10рJ/bit/m2

Transmit Amplifier 0dtoBS>=d

Єmp=0.0013рJ/bit/m4

The time period for the simulation was considered to be

suitable for 300 rounds of activity. Also, the consumed energy in the different simulation operations is computed based on the Table 1.

Fig. 6 the number of dead sensors in each round

The Fig 6 shows the number of the dead sensors (The

consumed energy); based on the figure, the first dead node in the LEACH protocol is in the round activity no. 114 and in the CHEFC protocol can be seen in round activity no. 146 which shows a 22% improvement of the stability period parameter.

Fig 7 shows the number of living sensors in each round as well as determining the 10% network lifetime parameter by CHEFC protocol.

Fig. 7 The number of living sensors in each round

Fig 8 also determines the number of cluster head sensors in

each round as it is seen in the figure. The average number of CHs is 23% and the mean of

leadership changes in each round is 6%; therefore, CHEFC

783

protocol has been able to improve the parameter. In the new protocol regarding the higher number of CHs in each round the accuracy of the collected data increases, it means the CHs are every where in the network and this shows the high rate of conductivity of the protocol. The interesting point about the capabilities of this protocol is that it can improve the lifetime of the network while increasing the number of CHs.

Fig. 8 the number of CHs in each round

This protocol is self configured and provide full cluster

head coverage for all node. Because If there is no cluster head in each node neighborhood, node compete for becoming cluster head.

V. CONCLUSIONS Finally, it was concluded that the use of clustering

architecture due to the number advantages it has, is among the suitable alternatives for wireless sensor networks; therefore, the election of CH for a cluster should follow a goal rather than being at random. This article could elect the CHs among the ordinary sensors in such a way that it could reach a full coverage of the WSN and solve the problem which the previous protocol was facing. The interesting point is that, this purposeful election led to the full coverage of the CH as well as increasing the network lifetime and its rate of conductivity.

REFERENCES [1] D. Chen and P. K. Varshney, "QoS Support in Wireless Sensor

Networks: A Survey", in Proc. of International Conference on Wireless Networks (ICWN '04), pp. 227-233, Las Vegas, Nev., USA, June 2004.

[2] W.R.Heinzelman, A.P.Chandrakasan and H.Balakrishnan , "An application-specific protocol architecture for wireless micro sensor networks" IEEE Transactions on Wireless Communications, 1(4):660-670,2002.

[3] Georgios Smaragdakis, Ibrahim Matta and Azer bestavros, "SEP: A Stable Election Protocol for clustered heterogeneous wireless sensor networks", Second International Workshop on Sensor and Actor Network Protocols and Applications (SANPA 2004),Boston MA, August 2004.

[4] A.A. Abbasi, M. Younis ,"A survey on clustering algorithms for wireless sensor networks," Computer Communications 30 (2007) 2826–2841.

[5] Carlos F. García-Hernández, "Wireless Sensor Networks and Applications: a Survey", IJCSNS International Journal of Computer Science and Network Security, VOL.7 No.3, March 2007.

[6] Yung-Fa Huang, Neng-Chung Wang, Ming-Che Chen," Performance of a Hierarchical Cluster-Based Wireless Sensor Network", IEEE International Conference on Sensor Networks, Ubiquitous, and

Trustworthy Computing, Volume , Issue , 11-13 June 2008 Page(s):349 – 354.

[7] Chor Ping Low, Can Fang, Jim Mee Ng, Yew Hock Ang, "Efficient Load-Balanced Clustering Algorithms for wireless sensor networks", Computer Communications 31 (2008) 750–759.

[8] Mohammad Mehdi Shirmohammadi, Karim Faez, Mostafa Chhardoli, "LELE: Leader Election with Load balancing Energy in Wireless Sensor Network", IEEE International Conference on Communications and Mobile Computing (CMC 2009), china, 2009.

[9] Yung-Fa Huang, Neng-Chung Wang, Ming-Che Chen, "Performance of a Hierarchical Cluster-Based Wireless Sensor Network", IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, 2008.

784