An Energy Optimized Unequal Clustering Routing Protocol in Wireless Sensor Networks

Abstract

Energy conservation of sensors in wireless network is very important since the battery of a sensor node cannot be replaced. In this paper, we propose an energy efficient base station assisted routing protocol in wireless sensor network, named EOUCR, which uses the base station to control the overhead of sensor nodes and create clusters of sensors. Main idea of BSAH is based on the concept of UCR, which groups the nodes into clusters of unequal sizes. Cluster heads closer to the base station have smaller cluster sizes than those farther from the base station, thus they can reserve some energy for the inter-cluster data forwarding. EOUCR combines the benefit of several clustering schemes to maximize the lifetime of sensor nodes and introduces several new features to enhance the performance of sensors. We compare the performance of BSAH with HEED, BCDCP and UCR and the simulation results show that EOUCR achieves a good improvement on network lifetime.

1 Introduction

Recent advances in wireless technology and micro electro mechanical systems have brought the wireless sensor networks (WSNs) into several industrial, home and military applications. A WSN is composed of a large number of sensor nodes and a base station (BS). Sensor nodes sense their environment, collect sensed data and transmit it to the BS. However, they are limited in power, computational capacity and memory. It isn’t easy to find the route and reserve it, because the limited amount of energy and sudden change in the position of the nodes creates unpredictable changes [1–4].

In recent years clustering has emerged as a popular approach for organizing the network into a connected hierarchy. By using clustering, nodes are organized into small disjoint groups called clusters. Each cluster has a coordinator referred to as cluster head (CH) and a number of member nodes. Clustering results in a hierarchical network in which cluster head form the upper level and member nodes form the lower level. In contrast to flat architectures, clustering provides distinct advantages with respect to energy conservative by facilitating localized control and reducing the volume of inter-node communication. Moreover, the coordination provided by the cluster head allows sensor nodes to sleep for extended period thus allowing significant energy savings. Despite many advantages of clustering in wireless sensor network such as network scalability, localized route set up, bandwidth management, the fundamental objective centers around energy conservation [5, 6].

Cluster formation is a process whereby sensor nodes decide with which cluster head they should associate among multiple choices. After the cluster head are elected, the non-cluster head nodes are faced with the task of selecting a cluster head from a number of possible candidates based on the criteria of optimal energy use. For a sensor node, selecting the cluster head based on a single objective can lead to poor energy use because the nearest cluster head may be located at a greater distance from base station than the other cluster head. Thus for that particular node this may not be the best choice. In addition, factors like residual energy and transmission energy may also be of importance when making a decision [7].

Clustering provides an effective method for prolonging the lifetime of a wireless sensor network. Current clustering algorithms usually utilize two techniques; selecting cluster heads with more residual energy, and rotating cluster heads periodically to distribute the energy consumption among nodes in each cluster and extend the network lifetime. However, they rarely consider the hot spot problem in multi-hop sensor networks. When cluster heads cooperate with each other to forward their data to the base station, the cluster heads closer to the base station are burdened with heavier relay traffic and tend to die much faster, leaving areas of the network uncovered and causing network partitions. To mitigate the hot spot problem, G. Chen et al. propose an Unequal Cluster-based Routing (UCR) protocol. It groups the nodes into clusters of unequal sizes. Cluster heads closer to the base station have smaller cluster sizes than those farther from the base station, thus they can preserve some energy for the inter-cluster data forwarding [7, 8].

However, in UCR, the CHs close to the BS tend to use much more energy since they have to transmit the collected data to the BS. We re-organize the UCR structure to save the energy of CHs. In UCR several CHs send data to BS but in our scheme only one CH (Leader Node) sends the aggregated data to BS.

The rest of the paper is organized as follows. The whole paper is organized as follow: Sect. 2 discusses the related works on clustering methods, Sect. 3 discusses the system model, Sect. 4 describes the proposed clustering protocol, Sect. 5 shows the simulation results and Sect. 6 describes the conclusion of the work.

2 Related Works

Siva D. Muganathan et al. propose a centralized routing protocol called Base Station Controlled Dynamic Clustering Protocol (BCDCP) [6], which distributes the energy dissipation evenly among all sensor nodes to improve network lifetime and average energy savings. The method assumes that the properties of a given sensor network model are a fixed base station, sensor nodes with energy constraints, nodes equipped with power control capabilities, and stationary nodes. It operates in two major phases, i.e., the setup phase and data communication phase. BCDCP uses class based addressing which gives identifications to each node in a network (Fig. 1).

Fig. 1

The routing path of base station controlled dynamic clustering protocol (BCDCP)

In UCR [7, 8], at the network deployment stage, the base station broadcasts a beacon signal to all sensors at a fixed power level. Therefore each sensor node can compute the approximate distance to the base station based on the received signal strength. It not only helps nodes to select the proper power level to communicate with the base station, but also helps us to produce clusters of unequal sizes. Clusters closer to the base station have smaller cluster sizes, thus they will consume less energy during the intra-cluster data processing, and can conserve some more energy for the inter-cluster relay traffic (Fig. 2).

Fig. 2

An overview of the UCR protocol

3 System Model

In this paper we consider the sensor network consisting of N sensor nodes which is randomly deployed in a uniform pattern over a vast field to continuously monitor the environment. We denote ith sensor by s_i and corresponding sensor node set S = {s₁, s₂, …, s_N}, where |S| = N, where N is the number of sensor node.

3.1 The Network Model

The network model assumed the following:

• 1. The presence of a Base Station (i.e., data sink) located far from the sensing field. Sensors and the Base Station are stationary after deployment.

• 2. Sensors are homogeneous and have the same capability, and each node is assigned with a unique identifier (ID).

• 3. Sensors are capable of operating in an active node or sleeping mode.

• 4. Sensors are able to use power control to vary the amount of transmission power, which depends on the distance to the receiver.

3.2 The Energy Model

We use a simple model shown in [3, 5] for the radio energy dissipation as follows. The energy spent for transmission of an l-bit data to a distance d is:

$$ \begin{aligned} E_{T} x(l,d) = & E_{(Tx - elec)} (l) + E_{(Tx - amp)} (l,d) \\ = & l\, \times \,E_{elec} \, + \,l\, \times \,\varepsilon \, \times \,d^{\alpha } \\ = & \left\{ \begin{gathered} l\, \times \,E_{elec} \, + \,l\, \times \,\varepsilon_{fs} \, \times \,d^{2} ,\quad d < d_{0} \hfill \\ l\, \times \,E_{elec} \, + \,l\, \times \,\varepsilon_{mp} \, \times \,d^{4} ,\quad d \geq d_{0} \hfill \\ \end{gathered} \right. \\ \end{aligned} $$

(1)

The first value represents the energy consumption of radio dissipation, while the second represents the energy consumption for radio amplification. Depending on the distance between the transmitter and receiver, both the free space $\varepsilon_{fs}$ ($d^{2}$ power loss) and multi-path fading $\varepsilon_{mp}$ ($d^{4}$ power loss) channel model are used. It can be presented in a simple formula by using constant p and q as variables as follows:

$$ E_{TX} \left( {l,d} \right)\, = \,p\, + \,q\, \times \,d^{a} $$

(2)

Where α is the propagation exponent and basically dependent to the channel’s condition and cross over distance $d_{0} .$ The electronic energy, $E_{elec}$ depends on factor as digital coding, and modulation, whereas the amplifier energy, $\varepsilon_{fs} d^{2}$ and $\varepsilon_{mp} d^{4}$, depends on transmission distance and acceptable bit-error. The cross over distance $d_{0}$ can be obtained from:

$$ d_{0} \, = \,\sqrt {\varepsilon_{\text{fs}} /\varepsilon_{mp} } $$

(3)

When received data Cluster head performs data fusion on received data packets, it assumes that the sent information is highly correlated, thus the Cluster Head can always aggregate the data gathered from members into single length-fixed packet. The energy consumed by cluster Head to receive, $E_{Rx}$ and data fusion or aggregate data ($E_{DA}$) is derived in equation below. To receive this message the radio expends energy:

$$ E_{Rx} (l)\, = \,\left( l \right)E_{Rx - elec } \, = \,l \, \, \times \, \,E_{elec } \, = \,l \, \, \times \, \,E_{elec} \, + \,E_{DA} $$

(4)

4 Energy Optimized Unequal Clustering Routing

The operation of EUCR protocol consists of three phases:

• 1. Initialization Phase

• 2. Formation Phase

• 3. Transmission Phase

4.1 Initialization Phase

The main purpose of this phase is to gather information of the entire node in the field. After the sensor nodes are scattered, each node transmits its own information to the base station. Since transmitting to base station requires a substantial amount of energy, this phase is executed only once. Base station receives and gathers all information from each node in the field. Base station calculates the weight of each node.

If $Wi$ (weight of node i) is less than a threshold, it then will be a tentative Cluster Head. The weight value is described in the Eq. (5) below:

$$ Wi\, = \,w_{1} /RE \, \, + \,w_{2} \, \times \, \, d\, + \,w_{3} \, \times \,\varDelta s $$

(5)

$Wi$ is the weight of Node i; RE is the Residual Energy node i; d is the distance from node i to the BS; $\varDelta i$ is the degree difference of node i, ${\text{w}}_{ 1} ,$ ${\text{w}}_{ 2} ,$ ${\text{w}}_{ 3}$ are weight constants for each variable. Degree difference of node i is:

$$ \Updelta {\text{i}}\, = \,|{\text{N}}({\text{i}})\, - \,\delta | $$

(6)

N(i) is the number of neighbor node and δ is the ideal number of member nodes.Here we can see that a node with the large residual energy, small distance to the BS and the small degree difference have a small weight. The node with the smallest weight becomes the Leader Node which transmits the aggregated data to the BS.

4.2 Formation Phase

In this phase, the nodes within each cluster will be linked together to form a chain. All the nodes in a cluster will send data to their CHs (blue and green nodes) and one of the CHs is selected as a Leader Node (yellow color in Fig. 3) which sends the data to the base station. In order to select the best leader node, we consider the remaining energy of the cluster heads, the distance to the BS and the degree difference (i.e. number of member nodes).

Fig. 3

Selecting the leader node (yellow node)

Since the energy consumption of the Leader Node is quite large, we change the cluster structure for the Leader Node to have no member node. In this way the Leader node can save the energy required to manage the member nodes.

4.3 Transmission Phase

After the previous phases, the data collection and transmission phase begins. The CH farthest from the base station initiates the chain creation. CHs collaboratively relay their aggregated data to the Leader Node and the Leader finally transmits the data to the base station.

4.4 Maintenance

The maintenance is very important to manage the energy balancing of all the nodes since Leader Node and CHs consume more energy than others. As the time/round passes, the energy of those nodes decreases quickly. In our scheme, the CH or Leader which have less energy than a given threshold should give up their role and become the normal member nodes. We have to do the Initialization Phase, Formation Phase and the Transmission Phase again. This way, the remaining energy of each node can be saved and extend the life of those nodes.

5 Experimental Results

In this section, we present simulation studies for proposed EOUCR protocol. To assess the performance of EOUCR, we conduct simulations using NS2. The objective of this simulation study is to compare its performance with other clustering based routing protocols such as BCDCP, HEED and UCR. Calculation of energy dissipation in the simulation is based on Eq. (1). Parameters of the radio model were based on [2, 5–7]. All parameters used are listed in Table 1.

Table 1 Simulation parameters

We define the simulation round as a duration time in which all sensor nodes sending a 2000-bit packet to the base station. For each simulation scenario, the results are drawn by the average value of 10 runs. We compare the network lifetime of HEED, BCDCP, UCR and EOUCR. The simulation results are given in Fig. 4. We observed that our proposed EOUCR protocol performs better than HEED, BCDCP and UCR. BSAH clearly improves the network lifetime (both the time until the first node dies and the time until the last node dies). We conducted several experiments with different parameters and EOUCR shows better performance each time.

Fig. 4

Experimental results on the percent of nodes alive

6 Conclusion

In this paper, we presented EOUCR, a novel optimization of unequal cluster-based routing protocol in wireless sensor network. We exploited the capabilities of directional antenna and power control at the base station to assist routing and clustering. We argue that the node closest to base station should be the Leader Node which uses much more energy than the other cluster head nodes. We introduce new criteria to select a leader node and the rotation of the roles of the nodes.

Simulation results demonstrate that EOUCR achieved significant energy savings and enhances network lifetime compare to HEED, BCDCP and UCR. We show that EOUCR achieves better performance than other clustering based routing protocols.