Energy Efficient Cluster Head Selection Algorithm Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In Wireless sensor networks, existing energy efficient routing algorithms assumed that the sensor nodes are stationary. Some of the applications in WSN must combine with both mobile sensor nodes and fixed sensor nodes in the same networks. When mobility is functioned there should be performance degradation. Because these nodes are equipped with a lesser amount of memory, restricted battery power, little computation capability, and small range of communication. So there is a need for energy efficient routing protocol to forward the incoming packet. In this paper, we propose Energy Efficient Cluster Head Selection Protocol in Mobile Wireless Sensor Network (EECHS-MWSN). The cluster-head nodes are selected from the residual energy, lowest mobility factor and density of the node. It is also used that the Gateway nodes are act as an intermediate node to transfer the data to the Base station. Simulation results show that the EECHS-MWSN protocol has more Energy consumption, network lifetime and throughput than the existing LEACH-Mobile protocol.

Keywords-Mobile Sensor Network, Mobility, Energy efficient, Throughput, density.


Wireless Sensor Network consists of a collection of mobile or static nodes which are able to communicate with each other for transferring data more efficiently and autonomously [1]. A lot of applications of mobile wireless sensor network can be found in different field such as habitat monitoring, wild life tracing, healthcare monitoring and search and rescue call for mobile sensor networks [2]. In Mobile wireless sensor network, one of the main constraints is limited battery power. So it reduced the lifetime and the quality of the network [1]. The researchers have considered many parameters for energy efficient cluster head (CH) selection protocols of Mobile WSN [7]. For example LEACH [8], LEACH-M [9] and LEACH-ME [10] etc are called energy efficient protocols. In these protocols, the data transmission phases are divided into rounds and in each round a random CH selection is performed. Our proposed protocol EECHS-MWSN gets better than LEACH-M [9] protocol by improving the Selection of the cluster-head nodes, considering residual energy, lowest mobility node and density of the node. And also the gateway nodes are used to transmit the data from cluster head to Base station. Simulation result shows that the proposed protocol has better performance than LEACH-M [9].The remaining of this paper is divided as follows. In section II gives a short overview of the routing techniques and developments made to reduce the energy consumption in Mobile WSN is given. In section III the approach used for the proposed energy model and its parameters are explained. In section IV the working of the simulated model has been explained and in section V concludes the work of this paper.

related work

This section briefly outlines the related works taken in the area of mobile sensor networks (MSN) which is LEACH [8] protocol improvements.

In LEACH [8], the nodes are organized themselves into local clusters. Each node has the same initial energy because of homogeneous networks. The operation is divided into rounds. In the set-up phase, the CH is selected from the organized clusters if a random number between 0 and 1 chosen by CH is less than threshold value. In the steady-state phase each non CH node sends data and the time slot allocated to CH .The CH aggregates the data and sends it to the BS. But the cluster formation is initiated in each round is not energy efficient and also it does not support mobility.

As a result, the work done by Do-Seong Kim and Yeong-Jee Chung propose LEACH-Mobile [9] (LEACH-M) routing protocol which applicable to Wireless mobile networks. The basic idea in LEACH-Mobile is to declare the membership of cluster as they move and to confirm whether a mobile sensor node is able to communicate with a specific cluster head. It transmits a message back to mobile sensor node from cluster head for data transmission within a timeslot allocated in TDMA schedule of a wireless sensor cluster. If the mobile sensor node does not receive the data transmission from cluster head within an allocated timeslot according to TDMA schedule, it sending join-request message at next TDMA time slot allocated. Then it decides the cluster to which it will belong for this moment by receiving cluster join-ack messages back from specific cluster heads. But in this protocol, transmission overhead is increased to send a message because of membership declaration.

To move forward this problem, Santhosh Kumar G et al. propose LEACH-Mobile-Enhanced [10] (LEACH-ME), the node with a lowest mobility factor is selected as a CH. Mobility factor is calculated based on the number of time that a node changes from one cluster to another. In steady state phase, if the non-CH node may not receive any request packet from CH node due to mobility then the CH node does not receive any acknowledgement form the non-CH nodes. If it is happened two consecutive timeslots, then CH assume that the node has moved and it deletes the timeslot of the node. However, LEACH-ME consumes much energy for determining mobility factor of the each node.

The effort taken by Samer A.B Awwad et al proposes cluster based Routing protocol for mobile Nodes in WSN [11] (CBR Mobile-WSN) to avoid the packet loss. The idea of this method is that, one of the cluster heads must be free to receive the packet from lost node that cannot receive data request message. The sensor node does not wait for two consecutive failure frames from cluster head to make decision but directly decided that the node has moved out of the cluster after one frame. Thus the data loss is reduced by sending its data to the new free cluster head and sends join acknowledgement message to the cluster heads.

The work done by Lutful Karim and Nidal Nasser propose Fault Tolerant Clustering Protocol for Mobile WSN [12] (FTCP-MWSN) that is not only energy efficient but also reliable. It does not require any extra timeslot for calculating the mobility of sensor node. So that it provide faster data delivery to BS. In the steady phase, CH assigns timeslots to the member nodes using TDMA scheme. If a node moves into a new cluster then it sends a Join-Request message to CH. Then the CH does not allocate the node a timeslot until any timeslot becomes free for moving a node out of this cluster.

system model

Assumptions of Network Model

For our proposed model, we adopt a few reasonable assumptions of the network model based on [3][4] as follows:

Sensor nodes are deployed densely and randomly in sensor field.

All the nodes of the sensor network are equipped with same amount of energy level in the beginning.

Each sensor node has a capability to transmit data to any other sensor node or directly to the base station using power control.

There is mobility in sensor nodes.

Gateway node is used to transmit data into Base station from Cluster Head node.

The radio channel is symmetric such that energy required for transmitting a message from node A to node B is the same as the energy required for transmitting a message from node B to node A.

Radio Energy Dissipation Model

The first order radio model used in LEACH-M and LEACH-ME is used for EECHS-MWSN, where radio dissipates Eelec = 50 nano Joule / bit to drive the transmitter and the transmit-amplifier dissipates εelec =100 pico Joule/ bit/m2 [16]. To save energy, when required the radio can be turned on or off. Also the radio spends the minimum energy required to reach the destination. The transmission cost of EECHS-MWSN is different from LEACH-ME because of there is no additional effort to calculate the remoteness at the ACTIVE slot. The equations used to calculate transmission costs and receiving costs for a k-bit message and a distance d are shown below.

1)Transmitting cost of LEACH-ME:

In active slots the k-active bits need to be sent twice, one for ID transmission and other for remoteness transmission. So there is an extra energy dissipated for ACTIVE slots.


ETx-cluster (k, d) = (N-1) * Eelec * k + εelec * k * ∑ di2



+ 2(N-1) * Eelec * K active + 2 * εelec * kactive * ∑ di2 (1)


2)Transmitting cost for EECHS-MSN:

ETx (k, d) = ETx-elec (k) + ETx-amp (k, d) (2)

= Eelec * k + εelec * k * d2 (3)

For N nodes in the cluster, the total transmission cost per TDMA cycle is:


ETX-cluster (k, d) = (N-1) * Eelec * k + εelec * k * ∑ di2 (4) i=1

Receiving cost will be same in LEACH-ME and EECHS-MWSN:

ERx (k) = ERX-elec (k) (5)

ERx (k) = Eelec (k) (6)

The radio channel is assumed to be symmetric for given signal to noise ratio.

Proposed Model

In this model, all the nodes are in the moving state except sink node and Gateway node. Because both sink and neighbor nodes are in mobile state then both nodes will consume large amount of energy that may lead to chances of early node death [6].Gateway node may be a Common gateway or Distributed gateway. Sink node takes a responsibility of data transformation and processing of the system. Our proposed work consists of two main phases in each round. They are Setup phase and Steady State phase. The followings are the brief responsibilities of each phase.

1) Setup Phase: During this phase, all the sensor nodes in the Mobile Wireless Sensor Networks are divided into smaller groups known as clusters. These groups are then involved in cluster head selection.

1.1 Cluster Formation Phase

Clusters are formed by the Base station (BS) in the basis of geographical locations of the sensors. During the first round, the base station first splits the network into two sub clusters, and proceeds further by splitting the sub clusters into smaller clusters. The base station repeats the cluster splitting process until the desired number of clusters is reached. When the splitting algorithm is completed, the base station will select a cluster head for each cluster. But nodes formed in the cluster are not an equal number in each of the cluster.

1.2 Cluster Head Selection phase

In this phase, Base station broadcasts a request message to all the nodes in the clusters using a non-persistent carrier-sense multiple access (CSMA) MAC protocol. After received the request message each node responds with current information messages which includes its basic information like node's ID, node category and also about the residual energy, Mobility factor and density of the node.

The remaining energy of the mobile node is considered by subtracting the total energy dissipated during the transmission from initial energy of the mobile node. Mobility is calculated based on the number of times a node changes from one cluster to another or on the basis of remoteness. Density of the node is calculated from ratio of Average distance from other nodes in same cluster and inter-node distance. These factors ensure that whether the node, to be selected as CH, belongs to a density popular area as well as the residual energy and mobility of the node within the cluster is on average.

After the selection of the CH node, it should inform their role to the other nodes in the networks. To do this, each Cluster head node broadcasts an advertisement message (ADV) using a non persistent CSMA MAC protocol to other nodes. This message is a small message containing the node's ID and a header that differentiate this message as an announcement message. After received the message from CH, each node transmits a join-request message (Join-REQ) back to the cluster head. This message is again a short message, consisting of the node's ID and the cluster head's ID.

If all nodes have the same initial energy then the CH is selected on a basis of random number i.e., between 0 and 1 and CH probability, which is similar to the LEACH protocol. The cluster head node sets up a TDMA schedule and transmits this schedule to the nodes in the cluster. This schedule ensures that there are no collisions among data messages. After the TDMA schedule is known by all nodes in the cluster, the set-up phase is complete and the steady-state phase (data transmission) can begin.

2) Steady State Phase: During the steady phase, cluster performs data gathering or routing. Steady state phase can be further divided into intra-cluster communication (forwarding to cluster head) and inter-cluster communication (forwarding to a sink node).

2.1 Intra-cluster Communication (Forwarding to CH)

In this phase, sensor node sends a sensed data to its CH. In the intra-cluster communication there exits two types of techniques: single hop or multi hop communication. In this protocol, multi hop communication is used. CH receives data from all senor nodes in its cluster in their assigned TDMA time slots. Then CH aggregates the data and sends it to nearby CH through the gateway node till reaches the BS.

2.2 Inter-cluster Communication (Forwarding to sink)

The data is forwarded by the CH node to the other zone CH node through the common gateway node or distributed gateway node using the best path routing technique called Inter cluster communication. Instead of choosing the entire available multipath, few of the best paths are selected on the basis of maximum remaining energy of the node. Finally, the CH which is near the BS can sends data directly to the BS. Cluster head nodes send the aggregated data into sink node i.e., base station through the Gateway nodes (Common GW and Distributed GW) is shown in the Fig 1.





CH4  

Common GW

Distributed GW

Cluster Head

Member Node

Figure 1: Data transmission from CH1 to BS through Gateway nodes.

simulation and results

In this paper, Energy efficient cluster head selection in Mobile wireless networks (EECHS-MWSN) is presented. A protocol for cluster formation, cluster head selection, intra-cluster communication and inter-cluster communication was proposed. This work is validated by using simulation and compared it with existing energy efficient protocol LEACH-M [9].The following subsections present mathematical analysis, simulation setup and simulation results.

Performance Analysis

In order to check the performance of the protocol in terms of its efficiency there are different metrics to be used. In this paper, we use Average energy consumption, Network lifetime and throughput for protocols evaluation.

The metrics that we selected for performances evaluation are as follow:

1) Average Energy Consumption:

The Average Energy Consumption is calculated as follows.

Average Energy Consumption [j] = Total Energy consumption / Total Number of received packets

2) Network lifetime:

This is the time interval from the start of operation of the sensor network until the death of the last alive node.

3) Throughput:

The ratio of total data received by a receiver from a sender for a time the last packet received by receiver measures in bit/sec and byte/sec. It can be expressed mathematically as follows. Throughput (bit/sec) = (Number of delivered packet * Packet size * 8) / Total duration of simulation

Simulation Setup

We use a 100m-100m region of 100 sensor nodes are scattered randomly in the sensor region. Ns2 simulator is used to implement the simulation [14]. The co-ordinate of BS is assumed to be at 90-170. Table I shows the network parameters and their respective values.

Simulation Parameters and their values



Network size

100 X 100 meter

Number of sensor nodes


Percentage of clusters Head

5 %

Percentage of Mobile sensor nodes

5 - 100 %

Base station position

90 X 170

Data Packet size

512 Bytes

Mobility model

Random way Point Model

Energy consumption for sending data packets

50 pJoule

Energy consumption in free space/air

0.01 pJoule

Initial node energy

2 Joule

Simulation Results

The performance of the EECHS-MWSN protocol is evaluated and compared with existing LEACH-M protocols in terms of Average Energy Consumption, Network life time and Throughput. Some significant results are as follows:

1) Average energy consumption per packet

Average energy consumption per packet is the measure of energy spent in forwarding a packet to the BS. It indicates the lifetime achieved by the protocols. In Figure 2, the number of nodes as x-axis and average energy per packet as y-axis is plotted. From the graph, it can be observed that the average energy consumption per packet using EECHS-MWSN is less than LEACH-M.

Fig 2: Number of Nodes Vs Average Energy Consumption of the network.

2) Network life time

Fig. 3: Number of Nodes Vs Lifetime of the network.

Figure 3 shows that the proposed protocol EECHS-MWSN gives the better Network lifetime when compared to LEACH-M and other clustering algorithms. This may due the following reasons. First, an alternating the role of Gateway node can balance energy consumption among cluster members. Second, EECHS-MWSN protocol considered residual energies of nodes, Mobility and density to elect the optimum cluster heads that can save more energy in nodes.

3) Throughput

It calculate from the total rate of data sent over the network, the rate of data sent from cluster heads to the base station as well as the rate of data sent from the nodes to their cluster heads.

In Figure 4 shows the graphical representation of Throughput with respect to number of nodes. Throughput is increasing when the network size is increased. From the graph, it can be observed that the throughput is increased using EECHS-MWSN than LEACH-M.

Fig 4: Number of Nodes Vs Throughput


This paper presents an improved description of LEACH-Mobile protocol called EECHS-MWSN which aims to reduce energy consumption in Mobile wireless sensor network and extend the lifetime of the network. This proposed protocol is improved the selection of the cluster-head nodes in a basis of the parameters like residual energy of the node, Mobility factor and density of the node. It is also used Gateway nodes as an intermediate node to transfer the data to the Base station. Simulation result shows that the proposed protocol gives better performance than LEACH-M in terms of Energy consumption, Network life time and Throughput. The new proposed scheme obviously has future scope for betterment of increasing network lifetime. In future, the plan is to extend the simulation by considering more challenging scenarios.