Keywords

1 Introduction

Wireless sensor networks are composed of lots of low-cost, dime-size, multifunctional sensor nodes in a self-organized manner [1]. Due to advantages of cheapness, easy implementation, reliability and small footprint, WSNs have been widely applied into different kinds of applications, such as environmental monitoring and protection, medical care, mine safety, home automation and forest fire detection [2–4]. However, the battery capacity of sensor devices is limited and batteries cannot be replaced in most typical deployment scenarios. Therefore, energy efficiency is always a challenge for WSNs [5].

In a static sink scenario, sensor nodes in the vicinity of the sink suffer from a large number of data forwarding tasks towards the sink, which makes these nodes consume more battery power than other nodes. These nodes are easy to become hotspots [5]. For this purpose, sink mobility is proposed to alleviate hotspot problem, which helps achieving uniform energy consumption to extend the network lifetime by shifting the hotspots. Mobile sinks also implicitly provide load-balancing by distributing extra workload over other nodes. During the WSN operation, isolated sensor islands may be formed due to non-uniform node distribution or hotspot effect. Mobile sinks can link the isolated sensor islands to improve the network connectivity by accessing the portions of the network one by one to receive data, which might not be realized in a static sink case.

Mobile sinks although bring lots of advantages to WSNs, a series of new problems also comes with them. Exploring mobile sinks, how to maintain the fresh routes towards mobile sinks is a core problem [6]. Unlike static sink scenarios, the network topology becomes dynamic as the sink moves. Frequent location updates will cause frequent unpredictable topology changes. Flooding the location update packets of mobile sinks within the network is the simplest approach, whereas this method will introduce a high communication head.

The usage of the hierarchical architecture significantly decreases the advertisement overhead of the sink’s position [7]. Only a limited set of nodes which is high-tier nodes in the hierarchical architecture need to keep track of the latest location of mobile sinks. Other regular nodes complete data delivery by retrieve high-tier nodes to get the sink’s position. It is obvious that high-tier nodes cause a higher communication overhead than low-tier nodes, which makes the hierarchical structure collapse early. So in order to keep the network running smoothly, a high-tier structure maintenance mechanism is necessary to distribute extra communication overhead over a set of regular nodes [8].

For these problems, in this paper, we propose Grid Routing, an energy-efficient mobile sink routing protocol, suitable for time-sensitive applications. We highlight some key features and the contributions of Grid Routing as follows:

  • Grid Routing is a hierarchical mobile sink routing protocol targeted for periodic data reporting in a large-scale networks.

  • Grid Routing uses a routes dynamic adjustment scheme to maintain the fresh routes towards the mobile sink with minimal communication cost. Sensory data from source nodes can be easily forwarded to destination nodes.

  • A simple high-tier structure maintenance mechanism is adopted to prevent the high-tier nodes from dying quickly. Grid Routing enables the high-tier nodes to switch roles with regular nodes when their energy level is below a certain energy threshold.

The rest of this paper is organized as follows: Section 2 gives a brief introduction of routing protocols employing different hierarchical structures. Section 3 gives the system model, including network characteristics and energy model. In Sect. 4, the methodology of Grid Routing is described in detail. We shows how to construct a grid structure and how data is delivered among sources and sinks. Section 5 shows simulation environment and further analyzes simulation results. Finally, we conclude this paper in Sect. 6.

2 Related Work

2.1 Virtual Infrastructure-Based Routing Protocols=

There have been many hierarchical approaches to the problem of routing in WSNs with mobile sinks [9]. Overlaying a virtual infrastructure over the physical network significantly decreases the advertisement overhead of the sink’s position. The high-tier nodes keep track of the latest location of mobile sinks, which means that only a limited set of nodes are employed to communicate with the sink. Low-tier nodes get the sink’s position by querying the high-tier nodes. A successful hierarchy can enable the latest location of mobile sinks to be easily forwarded to the hierarchical structure and regular nodes to acquire the sink’s position from the virtual high-tier infrastructure. In the remainder of this section, we explore several hierarchical mobile sink routing protocols and analyze their respective relative merits.

A distributed load balanced clustering and dual data uploading (LBC-DDU) is a cluster-based hierarchical routing protocol [10], which is proposed for sensors to self-organize themselves into clusters and realize dual data uploading by imposing multi-user multi-input and multi-output (MU-MIMO) technique. The network is partitioned into separate clusters with two cluster-heads of each cluster. LBC-DDU employs a mobile car to access each polling points selected in each cluster to collect data within a tolerable delay. It is clear that LBC-DDU is not suitable for time-sensitive applications. If the mobile car does not reach each polling points on time, data packets will be dropped after a certain period of time.

Cluster-based structure is the most popular hierarchical structure but not the only one. Two-Tier Data Dissemination (TTDD) is a virtual grid-based hierarchical routing protocol [11]. Every source node establishes a virtual grid-based network structure when existing sensory data and itself becomes a crossing point of this grid. Mobile sinks flood a query within a local grid. The request packet will be forwarded to the source node and generated sensory data will be sent to the mobile sink along the opposite direction of the originating path. Although TTDD limits flooding overhead within a local grid, grid construction cost for every source node is immense.

Obviously, TTDD is not suitable for the network where events occur frequently. In order to overcome TTDD’s shortcoming of grid construction, a Grid-Based Energy-Efficient Routing (GBEER) from multiple sources to multiple mobile sinks is presented [12], which constructs only one grid structure for all the source nodes using global location information. Data request packets are sent from the sink along the horizontal direction while the source node sends data announcement packets along the vertical direction, ensuring that there must be a header to receive both two data packets. Data request packets will be forwarded to the source node along the reverse of the path taken by data announcement packets. Although GBEER significantly decreases grid construction cost and enables high overhead to be limited in a separate cell, headers which process data request and announcement are easy to become hotspots and deplete their energy quicker than other nodes.

Similar to GBEER and TTDD, a virtual Grid-Based Dynamic Routes Adjustment (VGDRA) scheme is put forward [6], aiming to reduce the routes reconstruction cost to extend the network lifetime. VGDRA adopts four communication rules to dynamically readjusting routes, facilitating the sink’s location update within the virtual high-tier infrastructure. Moreover, high-tier nodes can easily spread extra load to other nodes of every cell via a cell-header rotation mechanism. Even though dynamic routes adjustment scheme is a good solution for the problem of the sink’s position update, VGDRA has no good performance in a non-uniform network.

Area-based approaches are also adopted to the problem of the sink’s position advertisement in a hierarchical mobile sink routing protocol. LBDD [13] and Railroad [14] are typical area-based routing protocols.

Line-Based Data Dissemination (LBDD) protocol defines a vertical virtual line, where in-line nodes belong to high-tier nodes. Source nodes forward the data to the nearest in-line nodes while generating some new data. The sink sends a query to the line and in-line nodes share this query until the destination node is reached. The data is then directly forwarded to the sink. However, LBDD suffers from the hotspot problem. Especially for large-scale networks, the line has to be wide enough to alleviate the hotspot problem since sharing queries on the line will introduce a high communication overhead.

Railroad constructs a virtual rail structure, which is a closed loop of a strip of nodes. When a source node generates data, it sends an event notification message to the nearest rail node. This rail node constructs a new station and floods this notification message in the station. The sink sends a query to the nearest rail node and share this query in two directions until this query reaches the station. The station node receiving the query informs the source node of the sink’s position. The source node forwards sensory data directly to the sink. However, Railroad may introduce a high data delivery delay due to a much longer structure travelled by the query and a long distance between the rail node and the source node.

Grid Routing establishes a virtual grid structure that imposes dynamic routes adjustment scheme to easily deliver the latest location of mobile sinks to cell-headers (high-tier nodes) with minimal communication overhead. On the other hand, Grid Routing improves the grid maintenance mechanism to enable the cell-headers to distribute more reasonably, which helps decreasing the overall energy consumption of every cell.

2.2 Energy-Aware Transmission Range Adjusting

As we know, a node with a large communication range will have amounts of neighbors. This means this node will suffer from a large number of data forwarding tasks. If a sensor node keeps the same transmission range of a “healthy” node all the time during the WSN operation, it will run out of its battery resource quickly.

Wang proposed an energy-aware transmission range adjusting scheme to adjust the communication range of sensor nodes based on their current residual energy [15]. Assuming that the total battery capacity of a “healthy” sensor node is B and its transmission range is r, the battery capacity of sensor nodes can be divided into three types. As shown in Fig. 1, a sensor node will adjust its communication range according to the current residual energy.

Fig. 1.
figure 1

The energy-aware transmission range adjusting mechanism

Full size image

3 System Model

Grid Routing establishes a virtual grid-based network structure which divides the network into the optional number of cells of the same size. The optional number of cells is calculated based on the total number of sensor nodes in the sensor field. The mobile sink moves around the clockwise\counterclockwise around the sensor field to collect data from the network.

3.1 Network Characteristics

We make some assumptions about network characteristics before introducing our Grid Routing protocol.

  • Sensor nodes shows non-uniform distribution.

  • All sensor nodes have the same limited initial energy level, whereas the battery of the mobile sink is rechargeable, where it has no resource constraints.

  • Each sensor node can adjust its communication range referring to the energy-aware transmission range adjusting mechanism described in Related Work.

  • There is no communication obstacle between any two nodes.

3.2 Energy Model

Grid Routing adopts the first order radio energy model as energy consumption model [13]. When a sensor node transmits l-bit length data packet at distance d, energy consumed by the sender node can be got by the following Eq. 1.

$$ E_{Tx} (l,d) = \left\{ {\begin{array}{*{20}l} {lE_{elec} + l\varepsilon_{fs} d^{2} ,\;d < d_{0} } \hfill \\ {lE_{elec} + l\varepsilon_{mp} d^{4} ,\;d \ge d_{0} } \hfill \\ \end{array} } \right. $$
(1)

where \( l \) is the length of data packets, \( E_{elec}^{{}} \) is energy consumption to transmit or receive one-bit length data, \( \varepsilon_{fs} \) and \( \varepsilon_{mp} \) are energy required for the transmitter amplifier according to different transmission ranges. \( d_{0} \) is a constant, which can be calculated by \( \sqrt {{{\varepsilon_{fs} } \mathord{\left/ {\vphantom {{\varepsilon_{fs} } {\varepsilon_{mp} }}} \right. \kern-0pt} {\varepsilon_{mp} }}} \).

When a sensor node receives l-bit length data, energy consumption can be easily calculated:

$$ E_{Rx} (l,d) = lE_{elec} $$
(2)

4 Grid Routing

In this section, the methodology of Grid Routing is described in detail, which divides the network into cells of equal size on the basic of the total number of sensor nodes in the sensor field. Utilizing this grid construction approach, only a limited set of nodes need to keep track of the latest location of mobile sinks, thereby decreasing the communication cost of this process. The hierarchy can be kept during the WSN operation by reelecting cell-headers in every cell. Adjacent cell-headers communicate with each other via gateway nodes.

4.1 Grid Construction

Initially, the network is partitioned into several uniform-size cells. The number of cells is determined by the total number of sensor nodes. If a large number of nodes are divided into a small amount of cells, cell-headers will run out of their batteries quickly and cell-header reelection process will be performed frequently. If a small number of sensor nodes are divided into excessive cells, too many high-tier nodes will lead to a high communication overhead while updating the sink’s position.

To determine the optional number of high-tier nodes, we refer to the heuristics used in LEACH [16], which considers 5 % of the total number of sensor nodes. Considering load-balancing and uniform energy dissipation, Eq. 3 is adopted to divide the sensor field with N sensor nodes into K cells of equal size, where K is a square number.

$$ K = \left\{ {\begin{array}{*{20}l} 4 \hfill & {N \times 0.05 \le 6;} \hfill \\ 9 \hfill & {6 < N \times 0.05 \le 12;} \hfill \\ {16} \hfill & {12 < N \times 0.05 \le 20;} \hfill \\ \vdots \hfill & {\quad \quad \quad \;\; \vdots } \hfill \\ \end{array} } \right. $$
(3)

The virtual grid structure will not change once constructed successfully. Sensor nodes put themselves into their respective cells based on network partitioning results from the mobile sink. Initially, nodes closest to the mod-point of their respective cell will be determined as the cell-header. Only those nodes whose distance to the mid-point of cells is below a certain distance threshold will be qualified to be a cell-header candidate. Elected cell-headers informed their member nodes and adjacent cell-headers of their roles.

As shown in Fig. 2, the mobile sink is first placed at Cell 1 while the network is initially partitioned into 16 cells. The mobile sink moves counterclockwise around the sensor field to collect data.

Fig. 2.
figure 2

The backbone of virtual grid structure

Full size image

4.2 The Sink’s Position Update Mechanism

As the mobile sink changes its position, the topology becomes dynamic and routes towards the mobile sink should be reset. Flooding the update packets of mobile sinks within the network is the most efficient way, however, the significant communication overhead will cause a short network lifetime.

In this paper, Grid Routing adopts a dynamic routes adjustment scheme to facilitate the sink’s location update, which maintains the fresh routes towards the mobile sink. A propagation rule is performed while updating routes towards the mobile sink. The specific process is as follows:

  • Rule 1: The mobile sink sends a location update packet to its immediate cell. Then nodes upon receiving this packet will forward it to their cell-header. If the current cell-header (CH) is the originating cell-header (OCH), which communicates directly with the mobile sink, the current CH informs the mobile sink to transmit data directly. Otherwise, rule 2 will be executed.

  • Rule 2: The current CH becomes OCH, and forwards this location update packet to its immediate downstream cell-header. The next downstream cell-header upon receiving the update packet checks whether its next-hop is the sender node. If not, this cell-header set its next-hop as the sender node, and continues to relay this update packet to its downstream cell-header. If the downstream cell-header is NULL, the update packet is discarded.

  • Rule 3: The current OCH also shares the sink’s position update to the previous OCH. The previous OCH upon receiving the update packet adjusts its route by setting the current OCH as its next-hop towards the mobile sink.

As illustrated in Fig. 3(a), a mobile sink starting from Cell 2 moves a small distance and still sojourns at Cell 2, routes towards the mobile sink remain the same according to rule 1. However, if the mobile sink moves out to the current cell, routes towards the mobile sink will change. In Fig. 3(b), the mobile sink moves from Cell 2 to Cell 3, blue arrows represent adjusted data delivery routes.

Fig. 3.
figure 3

Dynamic routes adjustment scheme

Full size image

4.3 Grid Maintenance

To ensure a long network lifetime, the grid structure should be kept during the WSN operation. Hence, a grid maintenance mechanism is necessary in Grid Routing. Reelecting cell-headers to replace current cell-headers in every cell is a good way to extend the hierarchy lifetime.

We define a certain energy threshold to trigger cell-header reelection process. When the current residual battery energy of a cell-header is below this threshold, a cell-header reelection process occurs among nodes whose distance to the mid-point of cells is below a distance threshold. Since sensor nodes remain non-uniform distribution, the node density in local regions is different, leading to non-uniform energy consumption in every cell. We adopt the number of neighbor nodes to represent the node density and take it into consideration when reelecting a new cell-header. It is clear that the overall energy consumption in a cell will be decreased if the node with more neighbor nodes becomes the cell-header, since more nodes have less hops towards the cell-header.

In the reelection process, the node with a higher residual energy level and more neighbor nodes are more likely to be a new cell-header compared to other candidates. If no node meets the requirement in the search zone, the searching scope will be slightly expanded or the energy level is decreased progressively. In order to protect the grid structure, cell-headers will share information of new cell-headers with their respective member nodes and adjacent cell-headers in their neighborhood.

5 Performance Evaluation

5.1 Simulation Environment

We use Matlab R2012b to evaluate the performance of our proposed Grid Routing protocol. 300 sensor nodes are randomly deployed in a rectangular region of 200 × 200 m2. As shown in Fig. 2, the mobile sink is placed at Cell 1 and then moves counterclockwise around the sensor field to collect data at a constant speed. According to Eq. 3, the sensor field is divided into 16 cells. Specific simulation parameters are listed in Table 1.

Table 1. Simulation parameters
Full size table

5.2 Results Analysis

Compared with VGDRA [6], we adopt energy-aware transmission range adjusting scheme to adaptively change the communication range of a sensor node to avoid a long distance communication in our proposed Grid Routing protocol. Furthermore, we improve the cell-header reelection process to achieve uniform energy dissipation in every cell. Therefore, in a given period of time, Grid Routing can save more energy theoretically. We define one time of data reporting as one round. It is clear that Grid Routing, which can achieve uniform energy dissipation in the local region, has a longer network lifetime and also has higher residual energy level in the same rounds than VGDRA.

In our experiments, we estimated the network lifetime in terms of the number of rounds of the mobile sink around the sensor field till all nodes die due to energy depletion. Figure 4 presents the network lifetime of Grid Routing and VGDRA with different rounds. In VGDRA, sensor nodes suffer from more energy dissipation due to non-uniform node distribution. On the basic of the cell-header role rotation process, more nodes experience a long distance data delivery to forward data to the cell-header if the cell-header locates at a place with low node density. However, in our Grid Routing, we put local node density into consideration when reelecting cell-headers, which enables cell-header to distribute more reasonably. As described in Fig. 5, Grid Routing consumes less energy than VGDRA in the same rounds.

Fig. 4.
figure 4

Network lifetime comparison

Full size image
Fig. 5.
figure 5

Energy consumption comparison

Full size image

6 Conclusions and Future Work

In this paper, we proposed an energy-efficient hierarchical mobile sink routing protocol, called Grid Routing, which enable a mobile sink to move counterclockwise around the sensor field to collect data. Grid Routing maintains the fresh routes towards the mobile sink with minimal communication cost and imposes the cell-header reelection process to get uniform energy consumption in local region. Simulation results of Grid Routing show good performance compared to existing work.

In the future, we hope to analyze the performance of Grid Routing at different sink’s speeds and different moving paths. And we will work on constructing a grid structure with cells in different sizes to get uniform energy consumption in the whole sensor field.