Efficient Scheduling Strategy for Data Collection in Delay-Tolerant Wireless Sensor Networks with a Mobile Sink

Abstract

Wireless sensor networks based on mobile sink (MS) can significantly alleviate the problem of network congestion and energy hole, but it results in large delay because of restriction of moving speed and lead to the loss of data due to the limited communication time. In this paper, a grid-based efficient scheduling and data gathering scheme (GES-DGS) is proposed for maximizing the amount of data collected and reducing energy consumption simultaneously within the delay of network tolerance. The main challenges of our scheme are how to optimize the trajectory and the sojourn times of MS and how to deliver the sensed data to MS in an energy-efficient way. To deal with the above problems, we first divide the monitoring field into multiple grids and construct the hop gradient of each grid. Second, we design a heuristic rendezvous point selection strategy to determine the trajectory of MS and devise a routing protocol based on hops and energy. With extensive simulation, we demonstrate that GES-DGS scheme not only significantly extends network lifespan compared with MS-based data gathering schemes, but also pro-actively adapts to the changes in delay in specific applications.

1 Introduction

The use of energy-efficient routing protocols in wireless sensor networks (WSNs) can reduce energy consumption to a certain extent, but it can not avoid the problem of network congestion and energy hole caused by the fixed position of sink. The introduction of mobile sink (MS) can solve the above problems, and greatly improve network lifespan. However, it result in large delay because of restriction of moving speed and lead to the loss of data due to the limited communication time. Taking the monitoring field of $L \times L$ ($L = 500\,\text{m})$ as an example, MS will takes more than 4 h, which is intolerable for many applications, to access 200 sensor nodes randomly deployed in the region even if it moves at a higher speed ($2\,\text{m}/\text{s})$. In addition, the length of MS’s patrolling path is restricted by battery endurance, the size of node’s buffer and the tolerable delay of application, etc., makes it impossible for MS to access every sensor node. To deal with the above problems, we propose a grid-based energy-efficient scheduling and data gathering scheme (GES-DGS), which joint consider the selection of rendezvous point (RP) and the routing from ordinary node to MS, for maximizing the amount of data collected and reducing energy consumption simultaneously within the delay of network tolerance.

The main contributions of our scheme can be summarized as follows:

• We first analysis the minimum virtual unit (MVU) of data acquisition, ensuring that all nodes in MVUs are within the communication radius of MS. Then, we propose a MVU-based partition method for division of WSNs and construct the hop gradient of each MVU.

• MVU is divided into multiple girds based on node’s sensing radius for ensuring full coverage of network monitoring, and only one sensor is kept in active state for reducing network traffic load.

• We design a virtual point-based adaptive patrol route algorithm (VP-APR), using proactive adjustment strategy based on node’s energy and location to adapts to the change of delay, to optimize the trajectory of MS.

• In order to reduce and balance energy consumption among nodes, we present a efficient routing protocol based on residual energy level of active node.

The performance of our scheme is evaluated through MATLAB simulations. Simulation results show that our scheme significantly extends network lifespan compared with existing MS-based data gathering schemes, and also achieve other better performance such as less energy consumption, less packet loss create, better throughput and better adaptability.

The rest of the article is organized as follows. In Sect. 2, we summarize the related work of MS-based data gathering schemes briefly. The problem statement is given in Sect. 3. In Sect. 4, we present and describe the details of our data gathering scheme GES-DGS. The simulation results are shown in Sect. 5. Finally, we give our peroration in Sect. 6.

2 Related Work

The issue of data gathering in WSNs has been solved by many researches from different methods. In this section, we give an overview of MS-based data gathering.

Chen et al. [1] proposed a grid-based reliable multi-hop routing protocol, optimizes the cluster head election process by combining individual ability and local cognition via a consultative mechanism based on cluster head’s lifespan expectancy, while considering data forwarding delay and reliable transmission of data. Xing et al. [2] presented a rendezvous-based approach in which a subset of nodes serves as the rendezvous points (RPs) that buffer data originated from source nodes and transfer to mobile elements (MEs) capable of carrying data automatically when they arrived. RPs enable MEs to collect a large volume of data every time without traveling long distance, which can achieve a desirable balance between network energy saving and data collection delay. Wen et al. [3] introduced an an energy-aware path construction (EAPC) algorithm, which selects an appropriate set of data collection points, constructs a data collection path, and collects data from the points burdened with data. EAPC accounts for the path cost from its current data collection point to the next point and the forwarding load of each sensor node. Yun et al. [4] have discussed about how to maximize the lifespan of the WSNs by using a mobile sink. Within a prescribed delay tolerance level, each node can store the data temporarily and transmit it when MS is at the most favorable location for achieving the longest WSNs lifespan. The framework proposed integrates energy-saving techniques, multipath routing, a mobile sink, delayed data delivery, and active region control, into a single optimization problem. Whether the proposal should be adopted in practice depends on the trade-off between the lifespan gain and the actual cost. Cayirpunar et al. [5] have considered the optimal mobility patterns of multiple mobile sinks for achieving the maximum WSNs lifespan. In this paper, three representative, i.e., grid, random, and spiral, are used for investigating the characteristics of the optimal mobility patterns and a novel mixed integer programming framework is proposed for characterizing network lifespan under different mobility patterns for multiple mobile BSs. Cheng et al. [6] proposed a timeliness traveling path planning (TTPP) algorithm which focus on how to plan a traveling path that meets the delay requirement of time-sensitive applications for data collection and reduces the amount of relay packets in the WSNs. Based on the least squares curve approach, the proposed TTPP algorithm can find the bestfitting curve for any given set of sensors by reducing the amount of relay packets in the WSNs.

3 Problem Statement

In this section, we introduce some terminologies, network model, energy model and then give our objectives.

Data gathering cycle (DGC): It is defined as the process that MS departs from $O_{s}$, moves inside ${\mathcal{A}}$ for collecting sensed data from nodes and back to $O_{s}$, forming a closed loop, which is also referred as a round.

Network lifespan $T_{sys}^{\alpha }$: It is defined as the period until the network fails to provide an acceptable monitoring effect, and parameter $\alpha$ represents acceptable level which depends on the specific application requirements. In this paper, the basic unit of $T_{sys}^{\alpha }$ is DGC.

3.1 Network Model

Assumed $N$ sensors are uniformly deployed in a monitoring field ${\mathcal{A}}$ of $L \times L m^{2}$ to collect data periodically and send sensed data to the mobile sink (MS). To simplify the network model, a few reasonable assumptions are adopted as follows:

• All sensor nodes are assumed to be static and have unique ID number, have the same data acquisition rate $k_{1}$ $bit/s$, have the same data transmission rate $k_{2}$ $bit/s$. The heterogeneity of nodes is shown as different limited initial energy. Besides, all sensor nodes have the same buffer size $B_{1}$ in packets.

• The data sensed is assumed to be not time-sensitive and they are stored in buffer of sensor nodes. Sensor nodes do not deliver their data to MS until it arrive at the given sojourns within a limited delay $T_{delay}$, where $T_{delay}$ is a variable that represents application delay.

• MS is located at starting point $O_{s}$ far away from ${\mathcal{A}}$ and has constant moving velocity $v$. MS has unlimited energy and large storage space.

• Intensive network is considered in this paper, all nodes can be connected by single hop or multi-hop. MS and sensors have the same restricted communication radius $R_{c}$, and all sensors have the same sensing radius $R_{s}$.

3.2 Delay Analysis

In a realistic application, it may not be able to deliver information to MS within direct radio range, thus local multihop routing is adopted in this paper. Compared with the multihop forwarding path in sink fixed network, the path length of local multihop routing is much shorter and the latency overhead of local multihop routing is much smaller. According to the definition of end-to-end delay which is composed of queuing delay $d_{Q}$, transmission delay $d_{T}$ and propagation delay $d_{P}$ [7], we just focus on $d_{T}$ but ignore $d_{Q}$ for its small value and $d_{P}$ due to the fact that electromagnetic waves propagate at the speed of light in the air. Since $d_{T}$ of one hop is related to the amount of data transmitted. Therefore, the more data forwarding, the greater the delay of data transmission.

3.3 Energy Model

Simple energy consumption model [8], which means all nodes use the same fixed transmit power and receive power, is adopted in this paper. We assume that $e_{t}$ and $e_{r}$ are the energy consumption of one hop required for sending and receiving per packet respectively. Besides, let $e_{idle}$ be the energy consumption required for storing data when node is kept in idle state, and the energy consumption in dormant state is negligible. Therefore, the energy consumption of data collection per round can be expressed as:

$$ E_{sys} = \sum\nolimits_{j = 1}^{{N_{g} }} {\sum\nolimits_{i = 1}^{{N_{j} }} {(e_{t} k_{t}^{i} + e_{r} k_{r}^{i} )} } $$

(1)

where $N_{g}$ is the amount of girds, $N_{j}$ is the amount of nodes in grid $j$, $k_{t}^{i}$ and $k_{r}^{i}$ denote the amount of packet sent and received by each node, respectively. The amount of data generated by node per round is calculated as follows:

$$ k_{self}^{i} = \left\{ {\begin{array}{*{20}c} {B_{1} } & {if\;k_{1} \times T_{delay} > B_{1} } \\ {k_{1} \times T_{delay} } & { if\;k_{1} \times T_{delay} \le B_{1} } \\ \end{array} } \right. $$

(2)

Where the relationship between $k_{t}^{i}$ and $k_{r}^{i}$ is $k_{t}^{i} = k_{r}^{i} + k_{self}^{i}$.

Due to the limitation of communication radius $R_{t}$, the energy consumption of data transmission is independent of transmission distance per hop but only related to hop count, and the total amount of data received in the network per DGC is calculated as follows:

$$ \sum\nolimits_{j = 1}^{{N_{g} }} {\sum\nolimits_{i = 1}^{{N_{j} }} {k_{r}^{i} = \sum\nolimits_{j = 1}^{{N_{g} }} {\sum\nolimits_{i = 1}^{{N_{j} }} {h_{{RP_{i} }}^{i} k_{self}^{i} } } } } $$

(3)

where $h_{{RP_{i} }}^{i}$ denotes the minimum hops from node $i$ to rendezvous point $RP_{i}$. Thus, the total energy consumption of data collection per DGC can be expressed as the sum of minimum hops,

$$ \begin{aligned} E_{sys} = \sum\nolimits_{j = 1}^{{N_{g} }} {\sum\nolimits_{i = 1}^{{N_{j} }} {(e_{t} k_{t}^{i} + e_{r} k_{r}^{i} )} } & = e_{t} \sum\nolimits_{j = 1}^{{N_{g} }} {\sum\nolimits_{i = 1}^{{N_{j} }} {(k_{r}^{i} \left( {1 + \alpha } \right) + k_{self}^{i} )} } \\ & = e_{t} \sum\nolimits_{j = 1}^{{N_{g} }} {\sum\nolimits_{i = 1}^{{N_{j} }} {(h_{{RP_{i} }}^{i} k_{self}^{i} \left( {1 + \alpha } \right) + k_{self}^{i} )} } \\ & = e_{t} k_{self}^{i} \sum\nolimits_{j = 1}^{{N_{g} }} {\sum\nolimits_{i = 1}^{{N_{j} }} {(h_{{RP_{i} }}^{i} \left( {1 + \alpha } \right) + 1)} } \\ \end{aligned} $$

(4)

where $\alpha^{{\prime }} = 1 + \alpha = 1 + \frac{{e_{r} }}{{e_{t} }}$. According to the above analysis, we can see that $h_{{RP_{i} }}^{i}$ depends on the distance between node $i$ and ${\text{rendezvous }}\,{\text{point}}\,RP_{i}$ that MS stays, thus it is crucial to optimize the trajectory of MS for reducing system energy consumption.

In particular, data fusion mechanism is not considered in this paper.

4 Grid-Based Energy-Efficient Scheduling and Data Gathering Scheme

In order to reduce and balance energy consumption, optimizing the patrolling route of MS as far as possible is worth considering within $T_{delay}$. In this section, we propose an efficient scheme GES-DGS, which can determine the location and different levels of virtual points, select corresponding level of virtual point and dynamically adjust trajectory of MS according to $T_{delay}$, and forward data sensed by nodes to MS using a simple and efficient routing algorithm.

4.1 Determination of Virtual Points

After randomly deployment of sensors in the monitoring field, they are divided into multiple virtual units. Assuming the coverage area of each node is a disk with a radius of $R_{c}$, then we can obtain the minimum virtual unit (MVU) of data acquisition, and the details are illustrated in Fig. 1. From Fig. 1, all nodes in MVU which consists of four sub-units ($S_{1} ,S_{2} ,S_{3} ,S_{4}$) can directly communicate with MS in the centre of disk and the size of MVU $l_{v}$ is $\sqrt 2 R_{c}$. In order to ensure monitoring performance and save network energy using redundant data elimination method, each sub-unit $S_{i}$ is divided into $m^{2}$ minimum cover units (MCU) using Algorithm 2 (PISA) in [1]. Assuming the value of $m$ is given ($m = 2$), then the size of each MCU $l_{g}$ is $\frac{\sqrt 2 }{4}R_{c}$. Next, monitoring field ${\mathcal{A}}$ is divided into multiple MVUs from centre to edge, and different levels of virtual points (VPs) will be marked to help optimize the trajectory of MS within a given delay $T_{delay}$. The number of levels $l_{e}$ depends on $L$ and $R_{c}$. Figure 2 shows the visualization of different levels of VPs $\left( {l_{e} = 4} \right)$.

Fig. 1.

Minimum virtual unit

Fig. 2.

VPs of different levels

4.2 Theoretical Analysis of Virtual Points

We can determine the amount of MVU according to the values of $L$ and $R_{c}$, and obtain the minimum amount of MCU that meets network monitoring performance, which means only one node in active in each MCU, according to the relationship between $R_{c}$ and $R_{s}$. Since the amount of active nodes is constant and same in each sub-unit, we can theoretically estimate the residence time at each VP and calculate the total moving distance traversed by MS.

Suppose that MS has enough receivers to accept all data delivered by all active nodes within one hop range simultaneously, all active nodes in the same sub-unit send data in time slot sequentially and communication interference between different sub-units and MS is not considered, thus we propose a residence time estimation algorithm (RTEA) to approximate calculate the data acquisition time $t_{level}^{i}$ and a moving distance estimation algorithm (MDEA) to approximate calculate the total moving distance $d_{level}^{i}$. The details of RTEA and MDEA are presented in Algorithms 1 and 2.

In algorithm RTEA, ideal concurrent transmission mechanism for corresponding MCUs in adjacent sub-units is adopted in this paper.

In algorithm MDEA, $VP_{i}^{in}$ and $VP_{i}^{out}$ are the two closest VP from point $O_{s}$. From algorithm MDEA, the total patrol distance of MS and walking time can be estimated approximately.

4.3 VP-APR: An VP-Based Adaptive Patrol Route for Mobile Sink

Considering the time-varying property of application delay $T_{delay}$, an VP-based adaptive patrol route algorithm (VP-APR) for MS is proposed for maximizing amount of data collected and reducing energy consumption per DGC simultaneously within the given period $T_{delay}$. Due to the high consistency of the Hilbert curve with our VP construction method proposed in this paper. In VP-APR, we first determine the level of VPs based on Algorithm 1 and determine which level of VP is selected as the reference point, which guides the movement of MS, according to Algorithm 2 and $T_{delay}$, then obtain the trajectory of MS efficiently. The details of algorithm VP-APR are presented in Algorithm 3.

In algorithm VP-APR, the level of VP $l_{vp}^{max}$ is first determined according to input parameters ($T_{delay}$, $L$, v, $l_{v}$), then MS traverses the regions in which $l_{vp}^{max} th$ VPs are located one by one in the form of hilbert curve. In essence, we convert the energy optimization problem in fixed-sink WSNs into the optimal-route minimum energy consumption problem in mobile sink-based WSNs. In algorithm VP-APR, VPs are just moving reference and MS actively adjust the actual rendezvous point (ARP) according to the priority of sub-unit. The priority of sub-unit is calculated as follows:

$$ P_{i}^{j} =\upgamma\left( {1 - \frac{{E_{max}^{i} - E_{res}^{j} }}{{E_{max}^{i} }}} \right) + \left( {1 - \gamma } \right)\left( {1 - \frac{{d_{vp}^{j} }}{{2^{\delta - 1} R_{c} }}} \right), if\,E_{res}^{j} > \overline{{E_{res} }} $$

(5)

Where $\delta = l_{vp}^{max}$, $i$ indicates serial number of region, $j$ is the serial number of sub-unit in region $i$, $E_{max}^{i}$ is the maximum initial energy in region $i$, $E_{res}^{j}$ is the residual energy of sub-unit $j$, $d_{vp}^{j}$ is the distance between centre of sub-unit $j$ and VP of region $i$, $\overline{{E_{res} }}$ is the minimum threshold value of sub-unit for computing priority. In (5), local energy factor and global hop factor inspired by (4) are considered. In algorithm VP-APR, the first DGC is completed by MS under the guidance of VPs, and then MS proactively changes ARPs for finding the optimal trajectory via self-adaptive behavior based on the priority of sub-unit.

4.4 Simple and Efficient Routing Method

In the early stage of network operation, MS starts data gathering tour and moves along $\psi_{vp}$ which is obtained by algorithm VP-APR. When MS arrives at any VP, it loiters and broadcasts ‘Hello’ message to active nodes (Atns) within the communication radius $R_{c}$. When Atns receive ‘Hello’ message, they will continue to spread ‘Hello’ message until all Atns in the same region are received. Due to the restricted communication radius and limited neighbor Atns for data forwarding, a simple and efficient routing method based on the ability of Atn is proposed for saving and balancing energy consumption. The ability of Atn-$i$ refers to residual representative energy (Rre) of sub-unit in which Atn is located and is calculated as follows:

$$ f_{Atn}^{Rre} \left( i \right) = \sum\nolimits_{j = 1}^{{N_{Atn - i}^{sur} }} {E_{res}^{j} } $$

(6)

where $f_{Atn}^{Rre} \left( i \right)$ denotes residual energy of sub-unit in which active node $i$ is located, $N_{Atn - i}^{sur}$ is the amount of surviving nodes in sub-unit that Atn-$i$ belongs to. From (6), MS proactively moves to neighbor Atn with the largest energy $f_{Atn}^{Rre} \left( i \right)$ for achieving dynamic balance of energy among surviving nodes in the same region, i.e., sub-unit with high density of nodes will be preferred as a relay region.

5 Performance Evaluation and Result Analysis

To evaluate performance of GES-DGS, extensive simulations with different evaluation criterias are conducted and the results of GES-DGS scheme with randow waypoint model (RW), shortest path method (SPM) in static WSNs are compared via simulations using MATLAB (version 2014b).

5.1 Experimental Setup

In the simulation, $4000$ sensor nodes are scattered randomly in the square monitoring area, $500\,\text{m} \times 500\,\text{m}$. Sensors continuously generate data at the speed of one packet per second and the size of packet is 500 bits, all nodes and MS have the same maximum communication radius $R_{c} = 50\,\text{m}$. The isomorphic network with initial energy $E_{init} = 1\,\rm{J}$ of all nodes, data transmission rate $k_{1} = 1\,\text{kb}/{\text{s}}$, the buffer size of node $B_{1} = 20\,\text{kbit}$, the value of $e_{t}$ and $e_{r}$ one hop per packet are $0.5\,{\upmu \text{J}}/\text{bit}$ and $0.4\,{\upmu \text{J}}/\text{bit}$ respectively.

In order to reduce the error, all simulation data are the mean of 30 random tests.

5.2 Network Lifespan

Efficient use of node energy is critical for extending network lifespan because of the constrained energy resource on the sensor nodes. We evaluated the NL performance of the three scheme as shown in Fig. 3. The value of $\alpha$ is defined as the period until first node fails to work according to the definition of NL. Figure 1 reveals that GES-DGS scheme extends about 3 times as long as that of SPM scheme and extends about 2 times as long as that of RW scheme. In general, the changes in network lifespan $T_{sys}^{\alpha }$ of GES-DGS and SPM are also stable than that of RWM scheme with the change in application delay $T_{sys}$.

Fig. 3.

Performance comparison: network lifespan

5.3 Effectiveness of Scheme

In Fig. 4, we present the measurement of effectiveness performance among SPM, RWM and GES-DGS. It can be found that SPM scheme and GES-DGS scheme obtain better monitoring performance than RWM scheme. Due to the fast speed of wireless communication, SPM scheme achieves good monitoring performance but drastically shortened NL as shown in Fig. 4. For RWM scheme, it can not guarantee the full coverage of the monitoring area due to the limited moving speed and $T_{sys}$, resulting in poor monitoring effectiveness than SPM scheme. However, RWM scheme achieves longer NL than SPM scheme for its larger moving distance and random walk feature, which effectively balances energy consumption among sensors. By contrast, we can observed that SPM scheme requires 5 times as much the amount of data acquisition as that of GES-DGS scheme to achieve the same monitoring performance. This is because GES-DGS scheme uses redundant data elimination method avoiding unnecessary consumption of node energy and significantly extended NL as shown in Fig. 3.

Fig. 4.

Performance comparison: scheme effectiveness

Combined with Figs. 3 and 4, we can conclude that GES-DGS scheme significantly extends network lifespan, drastically reduces energy consumption per DGC, and ensures network monitoring performance.

5.4 Energy Balance

The imbalance of node energy consumption is critical to the extension of network lifetime. Figure 5 illustrates that the variance in energy consumption of GES-DGS scheme decreases as the application delay increases and has better effect in energy balance that that of SPM scheme and RWM scheme. Besides, SPM has better stability of energy consumption per DGC than RWM scheme and GES-DGS scheme.

Fig. 5.

Performance comparison: energy balancing

6 Conclusion

To maximize the amount of data collected and reduce energy consumption within $T_{sys}$, we propose a GES-DGS scheme to guide MS patrolling in the monitoring field and collect data efficiently. Next, we intend to study the data acquisition problem of MS with limited energy.