Communications and Network, 2013, 5, 625-630
http://dx.doi.org/10.4236/cn.2013.53B2112 Published Online September 2013 (http://www.scirp.org/journal/cn)
Employing Orphan Nodes to Avoid Energy Holes in
Wireless Sensor Networks
Sepideh Zareei1, Elham Babaee1, Rosli Salleh1, Saeed Moghadam2
1Faculty of Computer Science and Information Technology, University of Malaya, Kuala Lumpur, Malaysia
2Faculty of Electrical, IT, and Computer Sciences, Qazvin Islamic Azad University, Qazvin, Iran
Received May 2013
ABSTRACT
When energy consumption by wireless sensor nodes gets off balance, partitions in the network appear because several
of the nodes stop functioning. The respective network’s lifetime also diminishes. This problem is commonly known as
the “hot spot” or “energy hole” phenomenon. To resolve this issue, a Multi-Hop Decentralized Cluster-Based Routing
(MDCR) protocol is proposed. This algorithm uses orphan nodes as intermediate nodes to form inter-cluster multi-hop
routing and balance the energy consumption among sensor nodes. Simulation experiments have shown that MDCR is
significantly better at prolonging networ k lifetime compared to the Adaptive Decentralized Re-Clustering Protocol.
Keywords: Wireless Sensor Networks; Clustering; Energy Efficiency; Orphan Nodes
1. Introduction
A wireless sensor network (WSN) consists of a large
number of distributed sensor nodes. The capability to
interact directly with physical phenomena have led to the
deployment of a vast number of applications for WSNs
including surveillance, machine failure diagnosis and
chemical/biological detection [1,2].
Clustering approach involves grouping nodes into
clusters; every cluster has a cluster head (CH) that acts as
the cluster coordinator, while the remaining nodes are
called cluster members (CM) [3]. In order to achieve
equilibrium in the energy consumption between members,
the role of CH is rotated throughout the CMs. Another
issue that remains to be addressed is the variation in
energy dissipation caused by the distance to the base sta-
tions. CHs which are further away from the base station
use more energy in inter-cluster single-hop routing be-
cause the energy load is higher in long-range communi-
cation compared to closer CHs. On the other hand, in
inter-cluster multi-hop routing, CHs near the base station
are used as intermediate nodes for transmitting data to
the base station. Therefore, these nodes forward more data
and rapidly dissipate their energy. The disparity in ener-
gy consumption by nodes results in an energy hole near
the base station. Hence, designing an energy-efficient
routing protocol, which also maintains the energy bal-
ance in the network, is the researchers’ primary concern.
In this paper, Multi-Hop Decentralized Cluster-Based
Routing is proposed, which is an extension of the Adap-
tive Decentralized Re-Clustering protocol. Rather than em-
ploying CHs to form inter-cluster multi-hop routing,
MDCR makes use of orphan nodes as intermediate nodes
for multi-hop routing. By using this method, CHs located
close to the base station preserve their energy for coor-
dinating their cluster. Thus, energy consumption can be
balanced among CHs. In addition, MDCR addresses the
problem of inefficient clustering in ADRP by selecting
future CHs located near the cluster’s center.
The paper is arranged as follows. The related works in
this area are covered in Section 2, the network model is
presented in Section 3, while Section 4 deals with the
orphan node problem and the solutions proposed to solve
it. Section 5 explains in detail the Multi-Hop Decentra-
lized Cluster-Based Routing protocol. Simulation results
along with an analysis are described in Section 6 and the
conclusions are presented in the final Section 7.
2. Related Work
LEACH [4] is a distributed single-hop clustering algo-
rithm, in which every sensor node decides to be a CH or
not, based on the following equation:
1
1*( mod)
()
0 otherwise
knG
kr
Pn k
∈

−
=



(1)

S. ZAREEI ET AL.
626
where
k
is the predetermined percentage of CHs (e.g.
0.05k=
),
r
is the current round, and
G
is the set of
nodes which have not been cluster-head in the last
1k
rounds. Subsequently, each CH broadcasts an advertise-
ment message and every regular node selects an appro-
priate CH for the current round. In the steady state phase,
CHs gather data from other nodes, then aggregate and
transmit it to the base station. LEACH needs every node
to communicate with the base station through single-hop
routing - something not feasible in most sensor networks.
In addition, the selected CHs can be placed in th e vicin ity
of network edges, causing the expenditure of much more
energy by other nodes to send information to these CHs.
To overcome this dilemma, the researchers have pro-
posed LEACH-M [5] and LEACH-C [4], which are ex-
tensions of LEACH. LEACH-M f or ms mul t i -hop routing
and LEA C H-C centrally con trols the bas e station in order
to form CHs.
One of the algorithms which significantly outperforms
LEACH is PEGASIS [6]. In PEGASIS, one node is se-
lected from a chain of sensor nodes to be the leader node,
which in turn transmits data to the base station after re-
ceiving transmissions for other nodes in the chain. The
overhead caused by the dynamic formation of clusters in
LEACH is reduced by PEGASIS. However, this accom-
plishment is countered by the lengthy delay introduced
by the single chain for the distant node.
BCDCP [7] is a centralized cluster-based routing pro-
tocol. To select a CH in BCDCP, the base station forms a
set of nodes with energy levels above the network’s av-
erage energy value. Subsequently, this protocol groups
the remaining nodes in one of the CHs, after which the
algorithm forms clusters via an iterative process until the
desired number of clusters is achieved. Making use of
CHs near the base station as intermediate nodes to form
inter-cluster multi-hop routing in this protocol, leads to
unbalanced energy consumption. In addition, communi-
cating with the base station in each round results in high
energy consumption and overhead.
To address this problem, Bejabar and Awan proposed
an ADRP algorithm [8]. Rather than communicating with
the base station at the end of each round for selecting
CHs, ADRP selects some nodes as future CHs for each
cluster. Hence, at the end of each cycle, the role of the
CH is switched to one of the future CHs without com-
municating with the base station. Although utilizing this
method results in a significant decrease in energy used,
inter-cluster single-hop routing and inefficient clustering
in ADRP leads to un-even energy consumption, as well
as energy holes in the network.
Still, none of the mentioned algorithms handles energy
holes in the network, but Soro and Heinzelman have
proposed an algorithm that does [9]. Their unequal algo-
rithm divides network fields in cirques. Same-size clus-
ters will be in the same cirque and there are various cir-
ques of different cluster sizes. To ensure energy dissipa-
tion remains balanced, the CH is selected from a group of
high-energy nodes to control network operations. In this
algorithm, the CHs’ positions must first be calculated to
ensure that high-energy nodes are available to become
CHs. EADUC [10] is an energy-aware protocol that uses
unequally distributed clustering in heterogeneous mul-
ti-hop wireless sensor networks. CHs are selected based
on the ratio of the node’s residual energy and the average
residual energy of neighbouring nodes. The irregular com-
petition ranges are used as a basis to create uneven clus-
ter sizes. CHs nearer to the base station will form smaller
clusters as a way of p reservin g energy for routing between
clusters. This algorithm suffers from extensive overhead
caused by dynamic clustering.
A distributed unequal clustering algorithm called EEUC
[11] elects CHs based on the nodes’ residual energy.
Every node will become a potential CH with a probabili-
ty of T. The uneven competition ranges are used by these
tentative CHs for cluster formation of uneven sizes. As
such, smaller clusters are closer to the base station (BS)
than those further away from it. This way, a CH close to
the BS is able to conserve energy for data forwarding
between clusters. Even energy consumption between CHs
is thus achieved. As T affects the quality of the generated
CHs, som e cas es o f T wi ll ha ve “i sola te p oint s” i n EEUC.
3. Network Model and Assumptions
Since MDCR is an extension of ADRP, the same net-
work model and assumptions as for ADRP have been
used to develop this protocol. The assumptions are as
follows:
1) The base station is far from the sensing field.
2) All the sensor nodes have a unique identifier (ID).
3) All of the sensor nodes are facilitated by power
control.
4) Each sensor node is able to send information to any
other node or to the base station.
5) There are no mobile nodes in the network.
6) Each sensor node can obtain location information
via GPS.
The energy model has been adopted from [4], while
the total cost of energy comes from Equations (2) and (3)
where the transmitter and receiver transfer
r
bit data
messages over distance
r
respectively.
(,) ()
TTx amp
E krEErk= +
, (2)
()
R Rx
Er Ek=
. (3)
In Equation (2),
(,)
T
E kr
reflects the cost of total
energy in the transmitter while
()
R
Er
in Equation (3),
shows the receiver’s energy consumption. Parameters
Tx
E
and
Rx
E
in Equations (2) and (3) indicate the per-bit

S. ZAREEI ET AL.
627
energy consumption for transmission and reception, re-
spectively. The transmit amplifier requires energy to main-
tain an acceptable signal-to-noise ratio, ensuring reliable
data transfer—shown as
()
amp
Er
. Finally, the energy for
data agg re ga t ion is de not ed by
DA
E
.
4. The Orphan Nodes Problem
Nearly all cluster-based routing protocols have orphan
nodes. An orphan node is a node which does not belong
to any cluster. A node may become orphaned for one of
several reasons. For example, orphan nodes might be out
of the CHs’ communication range, and do not receive the
advertised messages by CHs to join a cluster. Orphan
nodes are of no use in the network for at least one round.
Some solutions have been proposed in literature to make
use of orphan nodes within the network. Firstly, it is
possible to allow them to sleep in the current round so
they do not consume energy; if in this situation, however,
there happens to be some area in the sensing field which
is not covered by any nodes in the respective round,
network performance could be affected. Secondly, a
protocol can be added, which lets the cluster member
bring the orphan nodes into their clusters or allows them
to communicate directly with the base station [12]. How-
ever, this method might increase the overall network’s
energy utilization. MDCR is able to deal with orphan
nodes by using them as intermediate nodes to transmit
data from CHs to the base station and form inter-cluster
mul ti -hop routing. In this case, CHs close to the base
station are able to preserve their energy for coordinating
their clusters and energy consumption can balance out
among CHs.
5. MDCR Operation
The whole MDCR operation is divided into rounds, each
of which consists of initial and cycle phases just like
ADRP. The initial phase is further divided into three stag-
es: the partition stage, selection stage, and the multi-hop
routing formation stage. The cycle phases are divided
into the transmission and re-cluster stages. Figure 1 illu-
strates the MDCR procedure.
5.1. Initial Phase
Partition stage: Each sensor node transmits its energy
level and location information to the base station. Global
Positioning System (GPS) can be used to obtain the sen-
sor nodes’ location. During the initial stage, this system
is triggered and when all the information needed has been
obtained, the base station selects the CHs. If a sensor
node’s energy level is above average in the network, it
can be elected as a CH. In addition, the MDCR places
CHs into the centre of the clusters to distribute energy
among the nodes. Once CHs have been selected, each of
them broadcasts an Adv-Msg to inform the other nodes
that it has been elected as the CH for the current cycle.
Non-cluster heads pick the closest CH to them and send a
Join-Msg. Sensor nod es that do not belong to any partic-
ular cluster will transmit an Orphan-Msg to the base sta-
tion. In this case, the base s tation can identify orphan nodes
and use them to form inter-cluster multi-hop routing.
Selection Stage: A CH has several responsibilities in
the network. Therefore, the role of the CH should be ro-
tated among the cluster’s sensor nodes in order to distri-
bute the energy load in the network.
During the selection stage, the base station elects the
next heads. The nodes elected to be future CHs are called
the next heads. MDCR reiterates the steps below to select
the next he ads:
1) The following equation is used by the base station
to calculate the average energy of each cluster:
1
1()
m
ji
i
T Et
m
=
=
∑
. (4)
where
m
is the number of sensor nodes in cluster
j
and
()
i
Et
is the node’s curren t ener gy level.
2) Whichever sensor node’s energy level is above j T
—the threshold of cluster
j
—that is the one selected as a
next-head candidate for the current round (Equation (5)).
() ,
ij j
E tTiCNH≥∈
, (5)
where
j
CNH
is the set of next-head candidate nodes for
the current round in cluster
j
.
3) Once the
j
CNH
set is formed, the base station
computes the distance between each member of
j
CNH
and
j
CH
(CH of clu ster
j
), and selects the nodes nearest
to
j
CH
. These nodes form a new set called
j
NH
(next
heads of cluster
j
). In this case, the nodes near the center
of each cluster become CHs during MDCR operation; so,
CMs consume the same amount of energy to transmit
their sense d data to CH and intra -cluster energy consu mp-
tion is bal a nc ed.
Figure 1. MDCR procedure.

S. ZAREEI ET AL.
628
Four diverse types of sensor nodes are created at the
end of the selection stage, as shown in Figure 2:
1) CHs which are responsible for gathering data, ag-
gregating and transmitting it to the base station;
2) Next heads with the role of regular sensor nodes un-
til the beginning of the re-cluster stage, one of which will
be elected by the sensor nodes as a new CH for the com-
ing cycle to switch to;
3) Regular sensor nodes that collect data from the sur-
rounding environment to transmit to their CH;
4) Orphan nodes which do not belong to any cluster
and might be used as intermediate nodes to form inter-
cluster multi-hop routing.
Multi-hop Routing Formation Stage: In this stage, base
station assigns an orphan node to the CH and the set of
the next heads which can form the shortest multi -h op
routing path. After forming mult i -hop routing, the base
station sends a message to each sensor node. This mes-
sage consists of CH and the next heads ID so that each
sensor node is able to recognize the next head and switch
to it at the end of each cycle.
5.2. Cycle Phase
Transmission Stage: Scheduling and data transmission
are the two main activities in this stage. The regular nod e
must be able to send its sensed data to the CH once a
cluster has been formed. As such, the TDMA schedule is
employed by MDCR. In TDMA, ti me is split into differ-
ent slots which match the number of CMs. CH assigns
unique time slots to its members, in which the CH rece-
ives data sensed by its sensor node members. During data
transmission activity, CMs send data to their respective
CHs which will aggregate and tra nsmit to the base station
using inter-cluster multi-hop routing.
Re-cluster Stage: Again, in the multi-hop routing for-
mation stage, each member in its respective cluster rece-
ives a message containing the cluster-head and next heads
Figure 2. Node transition during MDCR operation.
ID from the base station. Therefore, the sensor nodes are
not required to communicate with the base station for
switching to the next head. At this point, the members of
each cluster elect the first member of
j
NH
set as CH
for the incoming cycle and switch to it. Once all sensor
nodes have switched to the next heads, this stage is ful-
filled and the transmission stage begins . The initial phase
starts in case a next head is not accessible.
6. Performance Evaluation
We analyse the performance of MDCR in this section.
The OMNET++ simulator [13] was used to simulate
MDCR performance and compare it to the Adaptive De-
centralized Re-cluster Protocol (ADRP), using the me-
trics shown be low.
1) Network Lifetime: Network lifetime is defined by
two metrics, namely a) first node dies and b) half of the
nodes die due to battery depletion.
2) Total Energy Consumption: This test shows the
energy used on the nodes in the network at certain time
intervals, allowing us to see the protocol’s energy con-
sumption during operation.
3) Energy Consumption of CHs: This test shows the
energy consumed by CHs at certain time intervals, allow-
ing for the comparison of CHs’ energy consumption in
ADRP and MDCR. Simulation parameters are listed in
Table 1.
Simulation Results
As pointed out in the previous section, two metrics are
applied for estimating network lifetime: first, time until
the first node dies and second, time until half of the nodes
die due to battery depletion.
Figure 3 illustrates the time until the first node of the
network dies over the number of cycles (a cycle is de-
fined as the time it takes f or the role of the CH to switch
to the next head). With MDCR, all nodes are still alive
for 88986 cycles; this number for ADRP is 80576. There-
fore, if network lifetime is defined as the time until the
Table 1. Simulation parameters.
Meaning of parameter Parameter value Unit
Network scale 1000 m × 1000 m m2
Number of nodes 100
Base station Location 500 m × 50 m m2
Initial energy 9.98 J
Data packet size 1000 bit
Tx Rx
EE=
50
nJ bit
amp
E
100
2
//pJ bit m
DA
E
5
nJ bit

S. ZAREEI ET AL.
629
first network node dies, MDCR exceeds the ADRP net-
work lifetime by 10.4%. The reason for this improve-
ment is the solution offered by MDCR for addressing
inefficient clustering in ADRP. ADRP selects next heads
without considering their location . Thus, it is possible for
sensor nodes located at the edge of a cluster to get se-
lected as next heads, and CMs consume high-energy loads
to transmit information to them when they become CHs.
By employing the proposed solution explained in Section
5, sensor nodes with sufficient energy and that are near-
est to the cluster center are voted as next heads. So,
members of the cluster consume approximately the same
amount of energy to transmit information to the CHs,
thus prolonging node lifetime and subsequently, network
lifetime.
Figure 4 shows the time it takes for half of the nodes
in the network to die over the number of cycles. From
this figure, it can be seen that it takes 94816 cycles for
half of the MDCR nodes to fail due to battery depletion,
while this number for ADRP is 86442. Similar to the
previous metric, MDCR outperforms ADRP by 9.7%.
Figure 3. Time un til first node dies.
Figures 3 and 4 illustrate that MDCR performs better
than ADRP in increasing the network lifetime of all me-
trics and gains about 10% longer lifetime than ADRP.
Figure 5 illustrates the total energy consumption of
the protocols over the number of cycles. Clearly, MDCR
outperforms ADRP by 10.07%. Using orphan nodes as
intermediate nodes to form inter-cluster multi-hop routing
is responsible for this improvement. ADRP applies in-
ter-cluster single-hop routing which results in high ener-
gy consumption by CHs located far from the base station.
Therefore, applying inter-cluster multi-hop routing by
MDCR leads to a lack of balance in energy consumption
among CHs and as a result, a decrease in total energy
dissipation in the network. In addition, inefficient clus-
tering in ADRP brings about high energy consumption of
the sensor nodes located far from the CHs. To address
this weakness pertaining to ADRP, the total MDCR ener-
gy consumption is decreased.
The final test comprises evaluating the energy dissipa-
Figure 4. Time un til half of the nodes die.
Figure 5. Total energy consumption.

S. ZAREEI ET AL.
630
tion of CHs. Figure 6 illustrates the energy used up by
CHs until half of the nodes die due to battery depletion.
Obviously, the energy dissipation of CHs in MDCR is
lower than that in ADRP. This improvement was achieved
by using orphan nodes to apply inter-cluster multi-hop
routing in MDCR. With this method, CHs located far
from the base station consume less energy to transmit
their information to the base station, while the closer
ones are able to preserve some energy to coordinate their
clusters.
7. Conclusions
In this paper, a Multi-Hop Decentralized Cluster-Based
Routing protocol was proposed, which is an extension of
ADRP. This algorithm utilizes orphan nodes in order to
form inter-cluster multi-hop routing and tackle the ener-
gy-hole problem in the network. In addition, the sensor
nodes’ location is considered as a metric for selecting
next heads, something that would solve the problem of
inefficient clustering in ADRP.
Simulation results indicate that compared to ADRP,
the performance of the proposed protocol is superior in
terms of network lifetime, total energy consumption, and
energy consumed by CHs.
Figure 6. Energy consumption of cluster-heads.
REFERENCES
[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E.
Cayirci, “A Survey on Sensor Networks,” IEEE Commu-
nications Magazine, Vol. 40, No. 8, 2002, pp. 102-114.
http://dx.doi.org/10.1109/MCOM.2002.1024422
[2] K. Akkaya and M. Younisc, “A Survey on Routing Pro-
tocols for Wireless Sensor Networks,” Ad Hoc Networks,
Vol. 3, No. 3, 2005, pp. 325-349.
http://dx.doi.org/10.1016/j.adhoc.2003.09.010
[3] N. Aslam, W. Phillips, W. Robertson and S. Sivakumar,
“A Multi-Criterion Optimization Technique for Energy
Efficient Cluster Formation in Wireless Sensor Networks,”
Information Fusion, Vol. 12, No. 3, 2011, pp. 202-212.
http://dx.doi.org/10.1016/j.inffus.2009.12.005
[4] W. B. Heinzelman, A. P. Chandrakasan and H. Balakri-
shnan, “An Application-specific Protocol Architecture for
Wireless Microsensor Networks, ” IEEE Transactions on
Wireless Communications, Vol. 1, No. 4, 2002, pp. 660-
670. http://dx.doi.org/10.1109/TWC.2002.804190
[5] Y. Li, X. H. Zhang and Y. Z. Li, “Algorithm of Cluster
Head Multi-Hops Based on LEACH,” Computer Engi-
neering and Design, Vol. 28, No. 17, 2008, pp. 4158-
4160.
[6] S. Lindsey and C. Raghavendra, “PEGASIS: Power-Ef-
ficient Gathering in Sensor Information Systems,” Pro-
ceeding of the International Conference of the IEEE Aer-
ospace, Big Sky, 9-16 March 2002, pp. 1125-1130.
http://dx.doi.org/ 10.1109/AERO.2002.1035242
[7] S. D. Muruganathan, D. C. F. Ma, R. I. Bhasin and A. O.
Fapojuwo, “A Centralized Energy-efficient Routing Pro-
tocol for Wireless Sensor Networks,” IEEE Communica-
tions Magazine, Vol. 43, No. 3, 2005, pp. 8-13.
http://dx.doi.org/ 10.1109/MCOM.2005.1404592
[8] F. Bajaber and I. Awan, “Adaptive Decentralized Re-
Clustering Protocol for Wireless Sensor Networks,”
Journal of Computer and System Sciences, Vol. 77, No. 2,
2011, pp. 282-292.
http://dx.doi.org/10.1016/j.jcss.2010.01.007
[9] S. Soro and W. B. Heinzelman, “Prolonging the Li fetime
of Wireless Sensor Networks via Unequal Clustering,”
Proceedings of the 19th International Conferences of the
IEEE IPDPS, Colorado, 4-8 April 2005, pp. 236-243.
http://dx.doi.org/10.1109/IPDPS.2005.365
[10] J. Yu, Y. Qi, G. Wang, Q. Guo and X. Gu, “An Ener-
gy-aware Distributed Unequal Clustering Protocol for
Wireless Sensor Networks,” International Journal of
Distributed Sensor Networks, Vol. 2011, 2011, Article ID:
202145. http://dx.doi.org/10.1155/2011/202145
[11] C. F. Li, M. Ye, G. H. Chen and J. Wu, “An Energy-
Efficient Unequal Clustering Mechanism for Wireless
Sensor Networks,” Proceedings of the International Con-
ference of the IEEE on Mobile Adhoc and Sensor Systems,
Washington, 7 November 2005, pp. 1-8.
http://dx.doi.org/10.1109/MAHSS.2005.1542849
[12] L. B. Oliveira, et al., “SecLEACH on the Security of
Clustered Sensor Networks,” Signal Processing, Vol. 87,
No. 12, 2007, pp. 2882-2895.
http://dx.doi.org/10.1016/j.sigpro.2007.05.016
[13] A. Verga, “OMNeT++ Discrete Event Simulation System
Version 4.2 User Manual,” 2011.
http://www.omnetpp.org/doc/omnetpp/Manual.pdf