International Journal of Engineering and Technical Research (IJETR)

ISSN: 2321-0869, Volume-2, Issue-11, November 2014

Energy Efficient Hierarchy Based Routing

Algorithms with Mobile Sink in Wireless Sensor
Networks: A Survey
Ajay Kumar Singh, Kanika Sharma
sensing, processing and communicating properties [1]. Many
Abstract In wireless sensor networks recent developments routing, power management and data dissemination protocols
have enabled the development of low power, low cost, have been specifically designed for wireless sensor networks
multifunctional sensor nodes that are small in size and where energy awareness is an essential design issue. The
communicate over the network. The main aim of the data
major components of the wireless sensor network include the
aggregation technique is to collect and aggregate data in an
energy efficient manner so that the network lifetime is enhanced.
sensing, processing, communication and power unit [2].
Sensor nodes are powered by limited capacities of batteries and Large quantities sensor nodes are typically deployed in
because of this limitation the energy consumption of sensor high-density manner, a wireless sensor network consists of
nodes must be controlled. One of the mechanisms used to high densely distributed nodes that support sensing, data
enhance the lifetime of the wireless sensor networks (WSNs) is processing and communication. Sensor nodes are logically
hierarchical routing. Hierarchical routing in the network linked by self organizing manner in short-hop point-to-point
provides better aggregation and scalability for the sensor masterslave pair arrangements. The typical wireless sensor
network with conserving energy of sensor nodes. In this paper network in a monitoring and data collection environment has
we present a survey on energy efficient hierarchical routing with
a number of components as depicted in Fig.1.
sink mobility to make the energy efficient and improved lifetime
of the network.

Index Terms cluster routing, Energy efficiency, mobile

sink, sensor node, wireless sensor networks.

I. INTRODUCTION
A wireless sensor network is composed of a large number of
sensor nodes which consist of sensing, data processing, power
unit and communication capabilities. In wireless sensor
network the sensor nodes distributed over a particular area to
cooperatively monitor physical or environmental conditions
such as temperature, pressure, humidity, sound, vibration,
motion and pollutants at different locations. Data are
collected from many sensor nodes by the base station which is Fig.1. Components of a sensor node.
the goal of the network. Data centric, self-organizing,
application specific and scalability are the main Sensing Unit- In this unit sensor node which physically reads
characteristics of the wireless sensor network. Another unique and collects data from its surroundings, there are two
feature of sensor network is the cooperation effort of sensor categories of sensor unit such as active and passive sensor.
nodes. Large numbers of sensor nodes are densely employed; The sensing units consist of sensor and analog to digital
neighbour nodes may be very close to each other. Hence converter, sensor reads and collects data from the
multi-hop communication in wireless sensor network is environment and analog to digital converter change the
expected to consume less power than the traditional single received analog input into digital signal for the processing
hop communication. Multi-hop communication can also unit.
effectively overcome some of the signal propagation effects
experienced in long distance wireless communication. Processing Unit- The processing unit is a small unit of sensor
which consist of processor and memory devices that are
Recent advancement in wireless communication the battery responsible for computation and storage of received data from
operated technologies have enabled the development of low the environment. Energy consumed in the processing unit can
power, small size and multifunction sensor nodes with be divided into switching and leakage energy. Energy is
consumed during switching when software instructions are
Manuscript received November 04, 2014. executed. Leakage energy is related with the nominal
Ajay Kumar Singh, Department of Electronics and Communication
consumption of energy when no computation is performed.
Engineering, National Institute of Technical Teachers Training and
Research (NITTTR), Chandigarh, India. The output of the processing unit is fed to the communication
Kanika Sharma, Department of Electronics and Communication unit for the transmission of received data from the sensing
Engineering, National Institute of Technical Teachers Training and unit.
Research (NITTTR), Chandigarh, India

69 www.erpublication.org
 Energy Efficient Hierarchy Based Routing Algorithms with Mobile Sink in Wireless Sensor Networks: A Survey

Communication Unit- Communication unit is the most data processing by sensor nodes reduces the energy of
demanding component of a sensor node. The transceiver unit individual node. To make the energy efficient routing
form a major part of the communication unit and are tasked between the source nodes and sink in a large sensor field the
with the transmission and reception of data. The more energy multiple mobile Sinks are used to improve the energy
is consumed in the transmission of data from sensor node to consumption and lifetime of the wireless sensor network. If
the base station as compared to the processing, computing and the sensor field area is large, clustering of sensor nodes is very
reception of data. Approximately energy consumed in useful to make the system energy efficient.
transmitting a single bit of data is equal to the energy spent in
processing of one thousand operations in typical sensor Depending on the applications and deployment area the sink
nodes. may follow different mobility patterns. The sink mobility
could be viewed in the perspective of sink and the sensors
Power Unit- This unit is required to maintain all sensing, deployment. The sinks perspective reflects the true motion
processing computational and communication operations pattern of the sink and the sensors perspective reflects the
from a few hours to several years depending on the estimate of sinks mobility through the limited knowledge of
applications. In this unit Primary and secondary batteries are the sensors. Sink mobility can be classified into three
used. The non-rechargeable batteries are Primary batteries categories are random, predictable and controllable mobility.
and rechargeable batteries are secondary batteries.
A sensor node has some application dependent additional
components such as location finding components, mobilizer III. OVERVIEW OF HIERARCHICAL ROUTING
and power generator. Sensors and analog to digital converters
are the parts of sensing unit. Analog to digital converter In hierarchical routing higher energy nodes are used to
convert the analog signals produced by the sensor nodes into process and send the message, while low energy nodes are
the digital signal. These digital signals are fed to the next unit used to detect the data in the network. The purpose of
(processing unit), the processing unit consists of a small hierarchical routing approach to decreases the load of
storage unit to store the data received by sensor nodes. A advertising the sinks location to the network by establishing a
transceiver unit is made up of two main sub units that are virtual hierarchy of nodes which imposes different dynamic
transmitter and receiver units. Power unit is the most roles on the sensors. The constructed hierarchy may be
important component of a sensor node. A mobilizer is used to composed of two or more tiers. The hierarchical approaches is
move the sensor node from one place to another to perform further classified as grid based, tree based, area based and
necessary tasks and a location finding system is used to find cluster based approach.
the location of the sensor node in the network.
(A) Grid-based Structure- In this approach grid structure
provides the higher level of the virtual hierarchy for the data
II. CONCEPT OF MOBILE SINK transmission in the network. The crossing-points of the grid
are constituted by the selected high-tier nodes in the network.
Mobile sink is a node which collects the data from the The number of shapes make up the grid i.e. squares,
sensor nodes and sends the collected data to the end user rectangles, triangles, hexagons etc. For this structure
through the internet or satellite communication system. Data geographic coordinates of the sensors are required, hence
gathering is a fundamental task of wireless sensor network. location-aware sensors are preferred in the structure.
Research has shown that sensors near the sink deplete their
battery power faster than those far apart due to their heavy (B) Tree-based Structure- In this approach tree based
overhead of forwarding messages. Non-uniform energy structure is virtual hierarchical, the sink advertisement is
consumption causes reduced lifetime of the network. Sink usually dissipated from the root towards the leaves.
mobility is used to reduce and balance energy expenditure
among sensor nodes. Sink mobility can effectively improve (C) Area-based Structure- In this approach the sensor nodes
network lifetime without bringing above mentioned negative are designated in a specific region as high-tier nodes. The
impacts on the network. The reason is evident as sinks move construction cost of this hierarchy is minimum. To solve the
the role of hot spot (i.e., heavily loaded nodes around sink) hotspot problem, large size of the area is specified to reduce
rotates among sensors, resulting in balanced energy the extra load on the high- tier sensor nodes in the network.
consumption. Sink should move toward data sources so as to
shorten path length and thus reduce energy consumption in (D) Cluster-based Structure- In this approach
wireless sensor network and enhance the lifetime of the clustering technique is used to partition the sensor network
WSNs. and employ the cluster head nodes as the high-tier nodes.
Clustering is a topology-aware mechanism which considers
If the sensor field is a small area only one mobile sink is the distribution of nodes in the network, with this approach an
used to collect the data from the sensor nodes. If the sensor efficient virtual hierarchy is achieved. The creation of clusters
field increases to a large area, there are large numbers of and assigning special tasks to cluster heads can greatly
source nodes to transmit the data to the single mobile sink. contribute to overall system scalability, energy efficiency and
The data transmitted from the end point of the sensor field to lifetime of the network. Hierarchical routing is an efficient
the mobile sink, Cooperative data processing being done. In routing to reduce the energy consumption of sensor nodes
this process the source nodes spent more energy to transmit within a cluster, performing data aggregation in order to
the data of other source nodes and itself also. Cooperative decrease the number of transmitted messages to the sink in the

70 www.erpublication.org
 International Journal of Engineering and Technical Research (IJETR)
ISSN: 2321-0869, Volume-2, Issue-11, November 2014

wireless sensor network. In this section, we describe the basic have to share the communication channel with the nodes
concept of clustering and components of a cluster in wireless in other clusters.
sensor networks. In studies where clustering technique were
primarily proposed for energy efficiency purposes [3] - [5].
IV. EXISTING HIERARCHICAL ROUTING
Basic Concept of Clustering: The basic concept of PROTOCOLS WITH MOBILE SINK IN WSNs
clustering play an important role to improve the network
performance. To fulfil the requirements such as lifetime Depending on the structure of the wireless sensor networks,
improvement, aggregation of data, quality of service and there are three main categories of the data collecting protocols
coverage, it is necessary to design an efficient network in WSNs. Flat-based routing, hierarchical routing and
layer routing protocol. There exist a number of routing location based routing [6]-[7]. A mobile sink routing
protocols in wireless sensor network such as Hierarchal algorithm mitigates the hotspot problem and improves the
routing protocols, Location based routing protocols and lifetime of the sensor network. There are various hierarchical
Flat routing protocols . Researchers and Engineers moved routing protocols with mobile sink in many contexts have
to routing protocols in recent years. been existed.

Components of a Cluster MSRP: It is a Mobile Sink based Routing Protocol for

prolonging the network lifetime in clustered wireless sensor
Cluster member: A cluster member is the most networks. In this protocol mobile sink moves in the clustered
important component of the wireless sensor network, network to collect the sensed data from the cluster heads
cluster member nodes are scattered in the sensor field to (CHs) within its vicinity. At a particular instant of time CHs in
detect events from the environment and perform local data the neighbourhood of the mobile sink forward their data to the
processing for the transmission of data to the base station. sink. The rest of the nodes in the network wait for their turn to
become mobile sink neighbourhood. In this way, during sink
Cluster Head: In each cluster one node is elected as movement all the nodes in the network forward their data to
cluster head (CH). Each cluster head is responsible for the mobile sink, when mobile sink comes in their
aggregating sensed data from its cluster member nodes neighbourhood during data gathering mobile sink also
that is sensor nodes and propagate it to the base station or maintains information about the residual energy of the CHs.
the next CH. The phenomenon of CH selection is Consequently, the hot spot problem is minimized as the
periodically divided in rounds. In each round new CH is immediate neighbour of the sink is high energy node and it
selected randomly or based on parameters like residual changes because of regular movement of the sink. It is a
energy of the sensor nodes, distance between sensor nodes balanced use of network energy and improves network
and base station, connected nodes and topology of the lifetime [8].
networks etc.
MECA: It is a Mobile-sink based Energy-efficient Clustering
Advantages of Clustering Algorithm. In this algorithm minimizing and balancing energy
Scalability: Among the nodes transmission numbers consumption for all sensor nodes. The network is divided into
are limited, the number of deployed sensor nodes in the several equal clusters and the intra-cluster routing exploits
network could be high, the density of sensor nodes can multi-hop routing to save energy of the sensor nodes. In this
range from few sensor nodes to few hundred nodes in a approach the mobile sink deployment helps to solve the
region. the number of nodes in a region of the network hotspot problem. The mobile sink moves around the edge of
indicate the density of the nodes. The deployment of the sensing field. Clustering technique and multi-hop intra
nodes in the region of network depends on the application cluster routing algorithm ensures less energy consumptions
in which the sensor nodes are deployed to sense the data. [9].

Data Aggregation: Data aggregation eradicates the GBEER: It is a Grid-Based Energy-Efficient Routing, it
duplication of data. In a large wireless sensor network constructs a single combined grid structure for all possible
there are often multiple nodes sensing similar information. sources. Location-awareness of sensor nodes is necessary to
In the clustering approach data aggregation allows to build the grid structure, data requests originated from the sink
make difference between sensed data and useful data. and data announcements originated from the source are
propagated through the grid structure. While data requests are
Energy Efficiency: The energy limitation of the propagated vertically data announcements are propagated
sensor nodes in the sensor network results in a limited horizontally along the grid to ensure that these packets
network lifetime for the nodes in the network. Clustering intersect at a crossing point. The location of the sink is send to
process help to prolong the network lifetime of the WSN. the source node, and data is delivered directly to the sink. This
routing is to eliminate the high overhead of constructing
Collision Reduction: In a large wireless sensor separate grids for each source by establishing and maintaining
network cluster heads work as a coordinator between a common grid structure [10].
sensor nodes and sink, number of nodes that access the
channel is limited. Cluster helps avoiding collisions EEMSRA: It is an Energy-Efficient Mobile Sink Routing
between the sensor inside the cluster, because they dont Algorithm. In this algorithm the number of hops, amount of
data in the transmission, the lifetime of sensor nodes can be

71 www.erpublication.org
 Energy Efficient Hierarchy Based Routing Algorithms with Mobile Sink in Wireless Sensor Networks: A Survey

prolonged and the communication is guaranteed. This by tree structure. MSDG is a distributed clustering data
algorithm uses cluster-based network structure to implement gathering protocol based on mobile sink [15].
the mobile sink routing protocol, and the sink movement
depends on the average energy in each cluster of the network. DHA- It is a Data Dissemination Protocol Based on Home
The mobile sink compares the average energy of the present Agent and Access Node. It is a progressive footprint chaining
cluster with the other clusters received from other mechanism to handle both sink position advertisement and
cluster-heads, if the average energy is more than any of the data dissemination. DHA selects home agents a data
received average energy from other cluster-heads, the mobile aggregation and dissemination point. The load on the home
sink will not move from its present position. Otherwise the agent is more and changing the home agent requires global
mobile sink will move to the cluster which has the maximum flooding in the network. The access node represents the
average energy in the network [11]. mobile sink to the home agent and home agent represents the
mobile sink to the sensor nodes, movement of the sink is
OAR: This is an Optimized Agent-based Routing protocol; it transparent to the sensor network. The home agent and the
provides efficient data delivery to the mobile sink and reduces access node are affected by the movement of the sink. When
the delay in data transmission. This algorithm minimizes sink moves it selects new access nodes which inform the home
signalling overhead and improve degraded route called agent of their new roles. The home agent is changed
triangular routing problem. All sensor nodes can transmit data occasionally to avoid hotspot problem and the location of the
to the sinks without delay or additional overhead, by new home agent is flooded across the sensor network. The
maintaining paths between all source nodes and sink pairs. source nodes are only need to know the location of the home
This feature enables OAR to cover a wide range of agent to disseminate the data in the network [16].
applications [12].
CMR: It is a Coordinate Magnetic Routing that constructs a
TTDD: It is a Two-Tier Data Dissemination protocol used in virtual rectangular grid in the network. Magnetic diffusion
in large scale wireless sensor networks. This protocol solves strategy is used to create a magnetic field over the nodes
the hierarchical routing problems in a sensor network with where the nodes knowing about the source nodes have
mobile sinks. Source node uses an algorithm to construct a positive polarity and nodes knowing the sinks position have
grid structure in the network for itself as a crossing node. The negative polarity. The sensor data are sent in the vertical
crossing node maintains events and source node information. direction and the sink position advertisements are sent in the
The cluster node sends flooding request message to neighbour horizontal direction along the grid. When a data packet is
nodes for searching the data. The data would be sent in received by a node with negative polarity it is the awareness
reverse direction. The cluster nodes can move and guarantee of the sinks position in the network [17].
data delivery correctly by agent policy, this algorithm is a
hierarchical routing algorithm which solves the nodes motion Ring Routing- It is a Ring Routing structure which is a closed
issues by agent policy. The algorithms have saved the energy loop of single-node width. Ring routing is considered to be an
cost and improve the lifetime of the wireless sensor network area-based approach. In this approach the sink advertises its
[13]. position to the ring by forwarding packets towards the
network centre via geographic routing. Hence the ring nodes
HCDD: This is a hierarchical Cluster-based Data maintain the fresh position of the sink at all the times. In this
Dissemination protocol. In this approach clustering is used to routing to mitigate the hotspots on the ring a local structure
determine the second-tier nodes. A combined hierarchical change mechanism is used. Ring Routing is an efficient
structure for all data sources is constructed. The cluster heads routing to mitigate the hotspot problem [18].
are responsible for propagation of data requests called
Routing Agents. The advantage of this routing algorithm is its SEAD: It is a Minimum-Energy Asynchronous
ability to operate without location information of sensor Dissemination protocol to mobile sinks in wireless sensor
nodes [14]. networks. In this protocol Steiner trees are used as the
high-tier structure with minimum cost. To make the sink
MSDG: This protocol is a Mobile Sink-based Data Gathering mobility transparent to the overlaying structure, this protocol
protocol. In mobile wireless sensor network model for high uses progressive chaining. For construction of the Steiner tree
efficient data gathering it adopts a joint strategy of sink and data dissemination the location-awareness of the sensor
mobility and routing based on the nodes which are divided nodes is required .This protocol establishes a more intelligent
into certain number of clusters. For data gathering when sink second-tier structure i.e. Steiner tree for efficient data
nodes move along the path the minimum energy consumption delivery in the network [19].
of the network is used. In this protocol sink approaches the
closest fixed nodes along the path as roots to build a routing On the basis of existing hierarchical routing algorithms with
tree, cluster-heads gather the data of all common nodes within mobile sink a comparison of hierarchical routing protocols
cluster and perform data aggregation. The aggregated data is with mobile sink in wireless sensor networks as shown in
sent to the sink in reverse direction by tree. This protocol is Fig.2
better than other data gathering protocols in terms of average
energy consumption and lifetime of the network. The sensing
data of each mobile node is aggregated and calculated by
cluster-head, and then reversely forwards to sink hop-by-hop

72 www.erpublication.org
 International Journal of Engineering and Technical Research (IJETR)
ISSN: 2321-0869, Volume-2, Issue-11, November 2014

Protocol Location Sink Hierarchical structure Data Multiple Protocol Hotspot

awareness mobility aggregation sink overhead mitigation
support
MSRP Yes Controlled Cluster Yes Yes Medium Medium
MECA Yes Controlled Cluster Yes No Medium Medium
GBEER Yes Random Rectangular Grid No Yes Medium Medium
EEMSRA Yes Controlled TDMA Cluster Yes No Medium High
OAR Yes Random Single Agent No Yes Low Low
TTDD Yes Random Rectangular Grid Yes Yes High High
HCDD No Random Max-Min D-Cluster No No High Low
MSDG Yes Random Square grid Yes No Medium Medium
DHA Yes Random Two Agent Yes No Low Low
CMR Yes Random Rectangular Grid No Yes Medium medium
Ring Yes Random Area No No Low High
Routing
SEAD Yes Random Stainer tree No Yes High High

Fig.2. Comparison of Hierarchical routing protocols in wireless sensor networks.

[9] Jin Wang, Yue Yin, Jeong-Uk Kim, Sungyoung Lee and Chin-Feng Lai,
An Mobile-sink Based Energy-efficient Clustering Algorithm for
V. CONCLUSION
Wireless Sensor Networks IEEE International Conference on
In wireless sensor networks routing is a leading area of Computer and Information Technology, pp.678-683, Oct. 2012.
research. In this paper we present a comprehensive survey of [10] K.Kweon, H. Ghim, J. Hong, and H. Yoon, Grid-based energy- efficient
hierarchical routing schemes in wireless sensor networks that routing from multiple sources to multiple mobile sinks in wireless
have been presented in the literature. They have the common sensor networks, in Wireless Pervasive Computing, 2009. ISWPC
2009. 4th Int. Symp. pp. 1 5, 2009.
objective to extend the lifetime of the sensor network. [11] Y. Xun-Xin and Z. Rui-Hua, An energy-efficient mobile sink routing
Hierarchical routing technique is most suitable for large scale algorithm for wireless sensor networks, in Wireless Communications,
WSNs and a useful technology management approach to Networking and Mobile Computing (WiCOM), 2011 7th Int. Conf. on,
reduce the communication overhead in sensor networks. In pp. 1 4, 2011.
[12] J.-W. Kim and D.-S. Eom, An agent-based routing algorithm with low
wireless sensor networks many hierarchical routing protocols overhead for mobile sinks in wireless sensor networks, in Advanced
have been reviewed. In this paper, the main concern of this Communication Technology, 2009. ICACT 2009. 11th Int. Conf. on,
survey is to examine the energy efficiency and network vol. 02, Feb. 2009, pp. 1156 1159.
lifetime enhancement of these routing protocols. [13] Haiyun Luo, Fan Ye, Jerry Cheng, TTDD: two-tier data dissemination in
large scale wireless sensor networks, Wireless Networks, vol.11,
pp161-175, 2005.
REFERENCES
[14] C.-J. Lin, P.-L. Chou, and C.-F. Chou, HCDD: Hierarchical cluster
based data dissemination in wireless sensor networks with mobile sink,
[1] Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal
in Proc. 2006 int. conf. on Wireless communications and mobile
Cayirci, "A Survey on Sensor Networks", IEEE Communications
computing. IWCMC 06, 2006, pp. 11891194.
Magazine, Vol. 40, No. 8, pp. 102-114, August 2002.
[15] Xu Jianbo, Guo Jian, Long Jing, Zhou Xinlian, Mobile Sink-based
[2] Kazem Sohraby, Daniel Minoli, Taieb, Znati Wireless SensorNetworks,
Data Gathering Protocol IEEE International Conference on
John Wiley & Sons Inc. publication, Canada, ISBN No.- 978-
Information Technology and Applications, vol. 2, pp.427-430, 16-18
0-471-74300-2, 2007.
Jul. 2010.
[3] W.R. Heinzelman. A. Chandrakasan. and H. Balakrishnan. An
[16] J. Lee, J. Kim, B. Jang, and E.-S. Lee, Data dissemination protocol
Application-specific Protocol Architecture for Wireless Microsensor
based on home agent and access node for mobile sink in mobile wireless
Networks. IEEE Transactions in Wireless Communications, vol. I, no.
sensor networks, in Convergence and Hybrid Information Technology,
4, pp. 660-670, 2002.
Springer Berlin / Heidelberg, 2011.
[4] V. Kawadia and P.R. Kumar. Power Control and Clustering in Ad Hoc
[17] S.-H. Chang, M. Merabti, and H. Mokhtar, Coordinate magnetic
Networks. in PIVC. of the 22nd IEEE INFOCOM, 2003.
routing for mobile sinks wireless sensor networks, in Advanced
[5] L. Bao and I.J. Garcia-Luna-Aceves. Topology Management in Ad Hoc
Information Networking and Applications Workshops, 2007, AINAW
Networks, in Proc. of the 4th ACM MobiHoc. 2003.
07. 21st Int. Conf. on, vol. 1, pp. 846 851, May 2007.
[6] Jamal N.Al-Karaki, Ahmad E.Kamal, Routing techniques in wireless
[18] C. Tunca, M. Y. Donmez, S. Isik, and C. Ersoy, Ring routing: An
sensor networks: a survey, IEEE International Conference on wireless
energy-efficient routing protocol for wireless sensor networks with a
communications, vol. 11, Issue.6, pp.6-28, Dec. 2004.
mobile sink, in Signal Processing and Communications Applications
[7] Can Tunca, Sinan Isik, M. Yunus Donmez, and Cem Ersoy, Distributed
Conf. (SIU), pp. 14 April 2012, .
Mobile Sink Routing for Wireless Sensor Networks: A Survey, IEEE
[19] H. S. Kim, T. F. Abdelzaher, and W. H. Kwon, Minimum-energy
Transactions in Communications Surveys and Tutorials, vol. 16, no. 2,
asynchronous dissemination to mobile sinks in wireless sensor
pp. 877-897, Oct. 2013.
networks, in Proc. of the 1st int. conf. on Embedded networked sensor
[8] B.Nazir, H. Hasbullah, Mobile Sink based Routing Protocol (MSRP)
systems, ser. ACM, pp. 193204, 2003 .
for Prolonging Network Lifetime in Clustered Wireless Sensor
Network, IEEE International conference on Computer Applications
and Industrial Electronics (ICCAIE), pp.624-629, 2010.

73 www.erpublication.org