An Improved Energy Balanced Dissimilar Clustered Routing Architecture for Wireless Sensor Networks ()
Received 13 May 2016; accepted 20 May 2016; published 25 August 2016
1. Introduction
Wireless sensor networks are a collection of spatially distributed autonomous sensor nodes that form into networks with the objective of sensing a particular or multiple physical phenomena such as pressure, temperature, sound etc. within their range. Various applications of such a wsn network are environment monitoring, wildlife count, pollution control, health monitoring, military surveillance. Further every wsn consists of one or more base stations with the role of collecting data from individual sensor nodes and presents them to an external network for subsequent processing and action. Certain sensor nodes act as specialized nodes that perform data aggregation from nodes that are far away from base station. Typical operating modes of wsn nodes are sensing, collecting data, processing data and transmission. All operations require considerable amount of battery energy of the sensor nodes. Random organization of the wireless sensor network may lead to high consumption of energy by these operations, which may deplete the battery very quickly thereby shortening the lifetime of the wireless sensor network. As most of the wsn applications are deployed under remote conditions, it is virtually impossible to recharge the batteries of the sensor nodes once they are deployed into service.
This energy limitation led to the emergence of a new sensor network architecture based on clustering of wireless sensor nodes. Clustering is based on the technique of grouping certain number of neighboring sensor nodes. A specialized node of the cluster forms the cluster-head that assumes the role of collecting data from cluster members and forwarding them to other cluster-heads or to the base station itself. Selection of cluster-head itself is considered important for efficient energy consumption as cluster-heads need to have high amount of energy throughout the life-time of the network. When cluster-heads are low in energy, a re-election of cluster-head should be initiated in that a node with high energy becomes the new cluster-head. In the process of data aggregation, cluster-heads also performs data compression by eliminating any data redundancy caused due to sensing of localized data by cluster members.
In wsn, communication between neighbor nodes or between cluster-members and cluster-head or between cluster-head and base station can be either in single-hop or multiple-hop fashion. In single-hop communication, sensor nodes can reach base station within a single communication step, whereas in multiple-hop communication, a node requires multiple numbers of steps to reach the base station. In clustered architecture, when multi-hop communication is used, a cluster-member requires at least two hops to reach base station through a cluster-head. A two-hop communication is described in Figure 1.
In another clustered topology, nodes communicate with cluster-heads and cluster-heads far away from base station would send their collected data to nearby cluster-heads and they in turn communicate with cluster-heads nearer to base station and finally reach the base station. This kind of clustered architecture is depicted in Figure 2, where farthest nodes require more than 2 hops to reach base station.
At any stage of the network, every sensor node should be either in any one of the states such as transmit, receive, idle and sleep. Sensor nodes should be capable enough to wake from sleep state whenever it is required to transmit or receive data. This strategy considerably conserves a large amount of energy for the overall network.
![]()
Figure 1. One-hop communication pattern for clustered wireless sensor networks.
![]()
Figure 2. Multi-hop communication pattern for nodes through multi cluster-heads.
2. Related Work
Several works in designing protocols related to clustering in wsn with the objective of increasing the life time of the network were published in recent times. Leach [1] is a well known clustering protocol that aims at achieving energy efficiency. In this protocol, the wsn re-organizes itself over some interval of time according to the signal strength of the nodes. Accordingly cluster-head re-election is also initiated every time there is a depletion of energy for the current cluster-heads. In HEED protocol [2] , multi-hop technique is used between nodes and cluster-heads whereas cluster-heads communicate in a multi-hop fashion to reach the base station. In this approach, there can be a possibility of overloading of data at the cluster-heads nearer to base station as all farther cluster-heads would be forwarding its data through nearer cluster-heads. In such cases, the cluster-heads nearer to base station may die out soon leading to hot-spots. S. Lindsey and C. Raghavendra proposed PEGASIS [3] , another clustering technique, which improves the performance of Leach by allowing nodes to communicate only with their close neighboring nodes. In their view, every node will have an equal chance of becoming a cluster head based on its energy reserve. Even though the nodes use random locations, every node will have the capability to discover its new neighbor with lesser delay time. APTEEN [4] suggested by Manjeshwar A. and Agrawal D. P., uses threshold values to fire events that enable periodic data transmission from nodes to be collected by cluster-heads. During non-transmission periods, the nodes are allowed to sleep leading to considerable energy conservation by individual nodes. One of the drawbacks with this technique is that it requires a sleep- wake up algorithm which when not effectively utilized may end up in non-availability of nodes in effective transmission periods.
Unequal clustering algorithm [5] proposed by Soro S. & Heinzelman W.B., assumed comparatively smaller cluster sizes nearer to the base station as it diminishes the power requirement by the cluster-head to collect data from individual nodes. Similar observations were put forward by G. Chen, C. Li, M. Ye and J. Wu [6] in which most of the power is utilized in forwarding the data from farther cluster-heads to the base station. In another unequal clustering [7] , energy consumed is used as a parameter in constructing dynamic clusters. This requires frequent re-election of cluster-head that may become an overhead. Clustering can be further aided by deploying relay nodes [8] [9] along unreachable areas from where the cluster-heads gets the data. Placing large number of relay nodes can make the network congested.
A clustering algorithm proposed in [10] selects the cluster heads considering lower load, the smaller cluster radius, residual energy. As the cluster radius is low, more iteration thereby more computations are required in routing. The work in [11] takes into account of the residual energy of neighboring nodes in constructing the cluster. Liu Yang et al. [12] describe multi-hop data transmission between cluster-head and base station. Although this study leads to improved energy conservation, it may lead to faster draining of cluster-head nearer to base station. On a study in [13] [14] suggests that data transmission between cluster-head and base station consumes lesser energy when multi-hop mode of transmission is used. But this strategy has a drawback of cluster head being overloaded with tasks leading to early death. This may lead to hot-spots at those areas [15] . Li et al. [16] tried to avoid hot spots by considering the distance of cluster-head with base station. Algorithms by Wong Tong et al. [17] computed the position of nodes and their residual energy in balancing the load in cluster heads. Most of the authors concentrated on minimizing the energy consumption thereby compromising the packet delivery and delay. In our proposed work, we try to minimize energy consumption as well improve packet delivery rate and lessen delay.
3. Dynamic Unequal Clustered Routing (D-UCR) Architecture R
There have been a lot of architectures proposed for wireless sensor networks. In that clustered architecture is considered to be highly energy efficient. A variant of Leach [18] is one among the very popular clustering algorithm that uses an uniform pattern in forming cluster sizes. We have enumerated various clustering protocols that effectively reduce energy consumption in our previous work [19] . The architecture that is being presented in this work is expected to increase the life-time of the network by placing the nodes nominally throughout the network.
Usually wireless sensor network is considered to be an undirected graph G = (V; E), where V is the set of sensor nodes and E is the set of links that connect the nodes. In graph G, nodes u and v have an edge between them if and only if they are in each others’ transmission range. In this type of architecture there should be a head node for a collection of nodes. These nodes transmit their collected data to their respective head nodes. These head nodes pass on the required control information to their subordinate nodes downward and forward the collected data to other cluster-heads upwards until the data reaches the base station for further processing.
Cluster sizes [20] play an important role in increasing the life-time of the network. As the data-load of cluster-heads nearer to base station is enormously high, it is advisable to keep the cluster size as minimized as possible. Cluster sizes can be incrementally increased as its cluster-head moves farther away from base station. Hence distance between base station and node, more particularly head node decides upon the size of the cluster. In such scenario, the load is found to be evenly distributed throughout the sensor network. Even this architecture can pose certain trade-offs such as certain regions far away from base station may be densely populated with sensor nodes in that the cluster size may also be larger leading to higher load to the cluster-head. So our approach combines hop distances of nodes towards base-station as well as density of nodes in the so-formed clusters. The clusters formed based upon the distance metric should be re-aligned using the density of sensor nodes in certain regions.
3.1. Node Distance
The sink or base-station computes the distance of nodes in the entire network using the signal strength of individual nodes. This can be considered to be an iterative process that begins from the base-station. First the entire sensing region should be organized into different concentric circular regions. The algorithm to perform this process is mentioned below.
3.1.1. Formation of Circular Regions of the Sensing Area
・ Step-1: BS initiates the process by sending beacon signals to all the sensor nodes
・ Step-2: Only nodes at one hop distance to the BS responds by sending ACK and they form the nodes of the first innermost circular region from the BS.
・ Step-3: Outermost nodes all along the circumference in this circular region send beacon signals to its neighboring nodes.
・ Step-4: Nodes hearing this beacon and not part of any already formed circular region responds to the sender by sending ACK and these nodes form the next outer ring.
・ Step-5: Steps 2 to 4 are repeated until all the nodes in the sensing area are covered under k concentric circles. This ensures the outermost node in this wsn network can reach the BS in k-hops.
The base-station categorizes the nodes under different concentric circular regions using the distance of the nodes from itself through different circumferential nodes. The diagram shown in Figure 3 depicts the above algorithm. Further in order to form boundaries for the clusters, the base-station further subdivides the region using the following algorithm.
3.1.2. Defining Boundaries for Clusters in the Circular Regions Using Cluster Angle
・ Step-1: Starting with a reference plane, a cluster angle θ is used to divide the 360 degree region. θ is assumed
![]()
Figure 3. Distance computation that decides the concentric circular regions.
![]()
Figure 4. Subdivision of sensing area for uniform node distribution.
to be a divisor of 360.
・ Step-2: This division ensures that smaller regions form nearer to base station and larger regions are formed at farther distance from BS.
・ Step-3: Steps 1 and 2 are repeated using incremental values of θ until sensing region is sectored into a number of sub regions.
・ θ can be varied based upon the density of the nodes along the width of the sensing area shown by this angle.
・ If the density of nodes in that region is found to be high, then θ value is decreased and vice versa.
Figure 4 shows the diagrammatic representations of the above algorithm where the sensor nodes are sectored into different regions for uniform distribution of nodes.
In scenarios where, node distribution is non-uniform, certain regions may be densely populated with nodes that may pose high energy drain to the cluster head. To overcome this problem, it is proposed to vary or minimize the θ value in accordance with the density of nodes in such regions thereby reducing the size of clusters. Our proposed diagram for sensing region with reduced cluster sizes is shown in Figure 5.
3.2. Node Density
In scenarios where density of nodes in the network is non-uniform, forming the cluster sizes based on distance can lead to hot-spot problems. So it is important to compute the node density as clusters are formed dynamically. The work by Bulusu in [21] proposed a method to compute the network density as
(1)
![]()
Figure 5. Subdivision of sensing area for non-uniform node distribution.
where N is the number of nodes in unit area A and r is the radius of the transmission range. Along with distance of a node with neighboring nodes, we need to incorporate one-hop connectivity of the node with other neighbors should be considered. If the density of nodes in an area is high, obviously the connectivity will also be high. A threshold number of connectivity can be set for a node to have connections. As distance of node from base station increases, this threshold value can be increased as the coverage area for those clusters also increases.
4. System Model and Simulation Environment
In this simulation model, the sensing area is assumed to be a circular region centered towards the base station. Let d be the density of the sensor nodes uniformly distributed in the region. The transmission range of nodes may assume to be constant during the initial time. As clusters are constructed, future cluster-heads should be able to dynamically increase their range, in-order to reach their counterparts. Let tre be the total energy consumed by all nodes for transmission after an initial time t and let rce be the total energy consumed by all nodes for reception of data. A scheduled sleep time and wake up time for the nodes in the network efficiently utilizes the energy reserves of individual nodes. Mobility of the nodes is considered to be static during the start of the simulation. Even if mobility is imposed upon the nodes, they are allowed to move over a specified or computed radius. This mobility model allows nodes to be intact within their cluster for a long time. Boundary nodes of a cluster may need to leave their cluster and join other neighboring clusters if they have an outward mobility from base station.
4.1. Wireless Propagation Models
Two kinds of propagation models can be used in wireless simulation environments. They are Two-ray model and Free-space model. In the former case, the received power Pr at a distance d is predicted to be
(2)
where ht and hr are heights of transmit and receive antennas. When distance d is small, power efficiency is limited, whereas for longer distance it gives good result.
In free-space model, the received power can be computed as
(3)
where Pt is transmitted signal power and Gt and Gr are antenna gains of the transmitter and receiver respectively. L is the system loss and 
is the wavelength.
4.2. Energy Consumption Model
In wireless sensor networks, the total energy can be calculated for one-hop distance nodes and using this energy, total energy for multi-hop nodes in different rings of the network can be computed. Under this scenario, for one hop distance nodes, the energy required for transmission of bits of length n to a distance d is
(4)
(5)
where Eelec is the energy dissipated for a single bit of data in the transceiver. The terms 
and 
refer to the energy dissipation for a single bit of the transmitting amplifier. 
is the threshold distance for changing the amplification models. 
can be calculated to be
![]()
. (6)
Similarly, energy required for receiving bits of length n can be expressed as
![]()
. (7)
For multi-hop transmission, the number of hops can be incorporated into the above computation to find the total energy dissipation.
5. Performance Analysis
Simulation is performed in NS2 by comparing the proposed protocol Dynamic-Unequal Clustered Routing (D-UCR) with other clustering protocols such as Leach and Equal Clustered Routing (ECR) protocol. We iterated our simulation for different number of nodes and traffic conditions. On each comparison, we noted considerable conservation of energy by our proposed protocol leading to higher network life time. We tabulated them and visualized them in x-graph. Packet delivery rate and delay were also simulated to prove that they were not compromised when energy conservation is given importance. Under different density levels of nodes, the simulations were performed and values on energy, packet delivery rate and delay were noted for these three protocols.
5.1. Energy
Every node is initially assigned with an energy value and analyzed their energy consumption. We iterated our simulation for varying number of nodes to find any deviation in energy consumption. We averaged the energy consumed by all the nodes after routing data to the base station. Table 1 enumerates the energy consumed by the sensor network for Leach, ECR, D-UCR.
We plotted the energy consumed values by the three protocols in x-graph only to find that ECR is better than Leach and our proposal D-UCR is energy efficient than the other two. Figure 6 shows the x-graph representation of our findings on energy consumption by Leach and ECR. Points at red line show the average energy con-
![]()
Table 1. Average energy consumed in different protocols.
![]()
Figure 6. Energy consumption by nodes using Leach and ECR.
sumed by nodes in Leach, whereas green line depicts energy consumption by ECR. Compared to Leach, it can be found ECR conserves more energy.
Figure 7 depicts the comparison of Energy consumed in Leach and the proposed work in D-UCR. It is clearly visible as the density of nodes increase, the energy saved is larger in D-UCR than in Leach. Figure 8 presents the comparison of energy consumption by ECR and the proposed D-UCR protocols.
When the above three figures were co-related with each other, the proposed D-UCR protocol showed lower energy consumption.
5.2. Delivery Ratio
In this simulation, we analyzed the delivery of packets to the destinations. In the proposed work, we addressed the issue of unattended nodes by joining them to nearby clusters. Hence it is expected that packet dropping can be minimized. As with our findings, Table 2 depicts the delivery of packets under different scenarios of Leach, ECR and D-UCR.
When these values were plotted in x-graph we found that delivery ratio in ECR is high compared to Leach and our proposal D-UCR has even better delivery ratio than the other two. The graphical representations shown below demonstrate our findings on packet delivery.
In Figure 9 we can find that higher delivery of packets is achieved for ECR when density of nodes is low and even for higher density of nodes, ECR achieves better delivery ratio compared to Leach.
Figure 10 compares delivery ratio for Leach and proposed D-UCR protocols. It is noted as the node density increases, delivery ratio increases constantly for D-UCR.
The delivery of packets is compared for ECR and the proposed D-UCR in Figure 11. It is visible that delivery rate of D-UCR is better than ECR.
Higher the delivery rate, the performance of the protocol is better. Hence D-UCR performs better than other protocols.
5.3. Delay
When packet is being delivered with better energy consumption, it’s not advisable to allow any delay in deliver-
![]()
Figure 7. Energy consumption by nodes using Leach and D-UCR.
![]()
Figure 8. Energy consumption by nodes using ECR and D-UCR.
![]()
Table 2. Average delivery ratio for nodes using Leach, ECR, D-UCR.
![]()
Figure 9. Delivery ratio of packets using Leach and ECR.
![]()
Figure 10. Delivery ratio of packets using Leach and D-UCR.
![]()
Figure 11. Delivery ratio of packets using Leach, ECR and D-UCR.
![]()
Table 3. Average delay in transmission using Leach, ECR and D-UCR.
ing the packets. Delay is termed as the average time taken by a packet to reach a destination. We analyzed the effect of delay on the three protocols and came up with the following tabulation in Table 3.
The results when plotted in x-graph, as in Figure 12, ECR has minimal delay compared to Leach.
Figure 13 and Figure 14 show that D-UCR has considerably reduced delay compared to other two schemes.
The average time taken by packets to reach their destination is low for D-UCR. Hence with the above results, it is obvious that the proposed dynamic Unequal Clustered Routing is an efficient protocol in terms of energy conservation, delivery rate and minimized delay.
6. Conclusion and Future Work
This work concentrates on energy conservation in wsn using a dynamic unequal clustered routing protocol. Our protocol ensures increased network life-time without compromising packet delivery rate and delay. The architecture we proposed created unequal sizes of different clusters with varying density of nodes in the sensing region. Based upon the range of nodes, circular regions were formed and they enclose the nodes to be formed as clusters. Given a restricted mobility to the nodes, the density of the nodes changes dynamically. Accordingly cluster organization also gets re-aligned dynamically. Simulations results on energy, delivery rate and delay show that, with D-UCR, total energy requirement for the wsn network is found to minimize as compared with other protocols such as Leach and ECR. D-UCR achieves improved packet delivery rate and reduced network
![]()
Figure 12. Delay in packet transmission in Leach and ECR.
![]()
Figure 13. Delay in packet transmission in leach and D-UCR.
![]()
Figure 14. Delay in packet transmission in ECR and D-UCR.
delay compared to Leach and ECR. Overall, our D-UCR protocol considerably improves the life-time of the wsn network. Future work on this protocol can be done with unrestricted mobility to the nodes. This may induce heavy re-alignment of the nodes between clusters. Efficient mobility models for the nodes can be implemented. Energy consumption under this scenario can be analyzed.