Sage Journals: Discover world-class research

Abstract

In recent years, the big data emerged as a hot topic because of the rapid growth of the information and wireless communication technology. One of the significant sources of the big data is wireless sensor networks. Due to the power limitation of sensor nodes, energy-efficient big data collecting is a challenging task in wireless sensor networks. Being considered as an effective solution to address this challenge is to utilize sink’s mobility to assist data collecting. Although this method can reduce the volume of data transfer between sensor nodes and thus save energy consumption of nodes, the low speed of mobile sink hinders its use in data-intensive sensing applications with time constraint. In this article, we propose a four-phase mobility-assisted data collecting protocol consisting of network clustering, routes planning, routes combination, and data collecting. Two heuristic routes planning algorithms are presented to build a set of trajectories which satisfy the deadline constraint and have the minimum overall movement cost. Numeric results show that our approaches have better performance in terms of energy saving, latency, and movement cost.

Keywords

Big data wireless sensor network data collection protocol mobile sinks heuristic routes planning algorithm

Introduction

Due to the rapid development of various information acquisition and wireless communication technology, the volume of data grows in an explosive way every day all over the world. Recently, a report published by IBM¹ indicates that 90% of the data in the world was generated in the previous 2 years. Therefore, the concept of big data has emerged as a hot research area and is attracting much attention from government, industry, and academic. The big data exhibits three remarkable characteristics which are high volume, high velocity, and high variety.² The variety means that the data generated by a wide range of sources such as radio frequency identification (RFID), Global Positioning System (GPS), sensors is of highly varied structures. The velocity refers to the high speed of processing and analysis. The volume refers to a large amount of data needs to be gathered, stored, and analyzed. Although services like social network, cloud storage, and Internet application are generating much volume of the big data, wireless sensor networks (WSNs) will produce a large portion of the big data, the volume of data generated by sensors is expected to reach the order of petabytes. WSNs have been well suited for use with a variety of applications including environmental monitoring, biological detection, smart spaces, and battlefield surveillance. Collecting the large volume of sensed data generated in these applications is crucial because the sensed information plays an important role on various human activities.^3,4 In order to gather these data, a routing tree along which the sensors relay their data to the sink is constructed.^5–7 Wireless transmission consumes significant amount of power of sensor nodes only equipped with limited battery. Even though the volume of data generated by an individual sensor is not significant, each sensor needs a lot of energy to relay the data generated by surrounding sensors. Therefore, energy-efficient method to collect big data in high-density large-scale WSNs is necessary and crucial.

Many data collection approaches aimed to reduce energy consumption have been proposed for WSNs recently. For example, data aggregation is one of the most effective approaches to reduce the total communication cost.^8,9 However, in large-scale WSNs, the number of aggregated data is still significant and a huge volume of data is required to be transferred to the base station (BS); furthermore, the precision of aggregation should be traded off with energy saving. Another approach of energy-efficient data collection in WSNs is data prediction technique leveraging the spatial or temporal correlation between sensor data. The data compression technology is capable of reducing the volume of transmitted data. Although it is easy to be implemented, the data compression technology requires the nodes to be equipped with large storage and powerful computation. Recently, the mobile sink schemes have received great attention in literatures. In such schemes, ordinary sensor nodes are static and densely deployed in the sensing area. One or multiple data collectors, referred to as the sinks, are assumed to be capable of moving. As the sinks traveling around the sensing area, the sensors send their data to the sinks when the sinks appear in their proximity. In such way, significant network energy saving can be achieved by reducing the number of wireless transmissions. However, the primary disadvantage of this approach is the increased latency. For instance, the typical speed of several practical Mobile Sink systems is about $0.1 - 1 m / s$ . As a result, it takes hours for a mobile sink to travel a large sensing field, which cannot meet the delay requirements of many data-intensive applications.

In this article, we are concerned with the problem of energy-efficient method to collect big data in mobility-assisted WSNs with delay requirements. We propose a four-phase mobile data collecting protocol called mobility-assisted big data collecting protocol (MDCP). It consists of network clustering, route planning, route combination, and data collecting. In order to minimize the network energy consumption, the mobile sinks are required to visit all the source nodes along constraint routes. This problem is related to the vehicle routing and scheduling problem with time window (VRSPTW) which falls into the category of non-deterministic polynomial (NP)-hard problem. Even finding a feasible solution to the VRSPTW with fixed number of vehicles is NP-complete. Therefore, we propose two heuristic algorithms to solve the route planning problem. The first heuristic algorithm builds routes by adding a link to the partially formed routes between two end nodes based on a measure of cost savings. The second heuristic algorithm belongs to the class of sequential route building algorithm. After initializing the current route, the heuristic sequentially adds a new node to the current partial route guided by a cost metric accounting for both geographic and temporal closeness of nodes. If no feasible nodes could be added, a new route will be started from the BS. In large-scale sensor network, the heuristic algorithms will build a large number of distinct routes for mobile elements (MEs) in order to visit all sensors within given deadline. In order to trade off between energy saving and movement cost, we first divide the source nodes into clusters and all nodes within a single cluster are fully connected. The MEs only collect data from cluster head (CH). Figure 1 shows an example of sensor nodes distribution, nodes clustering, and two optimal tours for MEs. We analyze the impact of time constraint, network scale, and movement speed on energy consumption through extensive simulations. We also compare the performance of two heuristic algorithms with rendezvous-based data collection (RDC) protocol and traditional data collection method without using MEs (NET). Simulation results show that our algorithms outperform RDC and NET in terms of energy saving, movement cost, and deadline misses.

Figure 1.

Example for route combination.

The rest of this article is organized as follows. Section “Related works” reviews related work and compares different ME-based data collection approaches. Section “Introduction” introduces our assumptions and formulates the problem studied. The two heuristic algorithms are given in section “MDCP.” Simulation results of the proposed algorithm are discussed in section “Performance evaluation.” Finally, section “Conclusion and future work” draws the conclusion of this article.

Related works

Recent work has provided mobility-assisted method to WSN aiming at enhancing the connectivity of sparse ad hoc networks and reducing the energy consumption of WSN. Francesco and Das¹⁰ present a comprehensive literature survey on WSNs with MEs.

Many solutions available in the literature have addressed the design of a static trajectory for MEs. For instance, Luo and Hubaux¹¹ consider a single ME which collects data from a circular dense WSN. It is showed that the optimal path of MEs is the perimeter of the sensing field. However, the average network energy consumption is high as nodes must communicate with the mobile sinks through multi-hop routes. Several heuristics are proposed by Gu and colleagues^12,13 to schedule the movement of MEs such that the source nodes can be visited before buffer overflow. While this approach minimizes energy consumption by avoiding multi-hop wireless transmissions, it incurs high latency when collecting data from large sensing field due to slow speed of ME. Xing et al.¹⁴ present an RDC approach jointly considering the motion control of ME. Several mobility patterns are considered, depending on whether the ME can move freely or not.

Data mule scheduling (DMS) is presented in Sugihara and Gupta¹⁵ for sparse WSNs with only single-hop communications and then extended in Sugihara and Gupta¹⁶ for a hybrid multi-hop communication scheme. The network-assisted data collection (NADC) problem is considered in Rao and Biswas¹⁷ as an extension of network-assisted sink navigation (NAN). In this case, a hop-bound factor k can be specified, so that data can be forwarded up to k hops. Abdullah et al.¹⁸ present a connectivity-based data collection (CBDC) algorithm. The CBDC algorithm utilizes the connectivity between sensor nodes so as to determine the trajectory of the mobile sink while satisfying its path constraint and minimizing the number of multi-hop communications. We proposed a genetic algorithm to determine the optimal travel routes for mobile sinks; it is not suitable for big data collection in large-scale sensor networks.¹⁹

MDCP

In this section, we first outline the MDCP in large-scale WSNs. After that, we introduce the network clustering and two route planning algorithms in detail.

Overview of MDCP

In order to energy efficiently collect huge volume of data in large-scale WSNs, we propose an MDCP. We assume that the network consists of many static ordinary sensor nodes and several mobile sink nodes. The static sensors sample the measurements of surroundings periodically and store the sensed data locally. The mobile sink nodes can move around the network to collect sensor data from static sensor nodes. MDCP consists of four phases: clustering, route planning, route combination, and data collecting. Initially, the static sensor nodes in network are grouped into many clusters and then route planning algorithm generates optimal trajectories for mobile sinks. If the number of routes beyond the number limit of mobile sinks, route combination is exploited to reduce the number of routes. At last, mobile sinks move along their trajectories to collect data.

Network clustering

Network clustering is the first phase of MDCP. As the movement speed of mobile sink is relatively much lower than wireless transmission, it is impossible for mobile sink to visit all the static nodes within a given deadline. Therefore, network clustering phase of MDCP aims at dividing the network into clusters and deciding the data collection points (CHs). Sensors in the same cluster transfer their data to their CH. The CHs store the aggregated data in their buffer memory until mobile sinks approach them. The information is transferred to mobile sink by wireless communication.

We can exploit any of the existing clustering algorithms like low-energy adaptive clustering hierarchy (LEACH). Sensors are grouped into clusters based on their connectivity to each other. Every node can communicate with all the other nodes in the same cluster via one-hop communication. Let $G_{k}$ represent a set of nodes, such that $G_{k} = {i \in V | \forall j \in V, w_{ij} = 1 \land i \neq j}$ , $w_{ij} = 1$ if nodes i and j are one-hop connected, otherwise $w_{ij} = 0$ . $N_{k}$ denotes the number of sensors in cluster $G_{k}$ . The centroid point of each cluster is computed as the CH. The cluster members transmit their data to their CH. MEs collect data from CH nodes along specific route.

Route planning problem formulation

Since random walk cannot guarantee the deadline requirements for data collecting, route planning for mobile sink is necessary and important in MDCP. In this section, we formulate the problem of route planning for big data collection in mobility-assisted WSN. This problem involves the building of a set of optimal routes for mobile sinks, each route originates and terminates at the BS. Before we formally give the mathematical formulation of this problem, let us first state the assumptions and introduce the concepts that will be needed throughout this article.

We assume that sensor nodes are randomly and uniformly distributed in the sensing field. Each node periodically generates a chunk of data and must transfer the data to the BS before its deadline. The delivery deadline is often determined by the data freshness or the buffer size of sensors. Mobile sinks move along their specific routes and collect data from sensors on the routes. Each sensor needs to be visited by mobile sink exactly once and all nodes in network must be assigned to specific mobile sink. Sensor nodes and sinks are aware of their physical locations by GPS.

Definition 1

An undirected graph $G = (V, E)$ , where $V = {0, 1, 2, \dots, n}$ , is the set of vertices and $E = {(i, j) | i, j \in V}$ , is the set of unordered pair of distinct vertices, called edges.

Definition 2

$G = (V, E)$ be a graph, a path P is a sequence of vertices $i_{1}, i_{2}, \dots, i_{k}$ , such that $(i_{j}, i_{j + 1}) \in E$ , for all $1 \leq j \leq k - 1$ .

For convenience, let us define the following notions and variables:

$c_{ij}$ the cost associated with edge $(i, j)$ ;

$d_{ij}$ the Euclidean distance from node i to node j;

$t_{ij}$ the travel time from node i to node j;

$b_{i}$ the arrival time of ME at node i;

$l_{i}$ the latest visit time of node i;

$s_{i}$ the service time for node i;

L the time constraint for all routes;

R a sequence of $(i_{1}, i_{2}, \dots, i_{k})$ corresponding a route $(0, i_{1}, i_{2}, \dots, i_{k}, 0)$ ;

$L (R_{i})$ the travel time of route $R_{i}$ .

We now formally formulate our problem as follows.

Let G be a given undirected graph corresponding to the ME route planning problem. Vertex 0 corresponds to the BS and vertex i corresponds to node i for $1 \leq i \leq n$ . A solution S is a set of routes $S = {R_{1}, R_{2}, \dots, R_{m}}$ . The cost of route $R_{i} = (i_{1}, i_{2}, \dots, i_{k})$ is computed as follows

C (R_{i}) = c_{0, i_{1}} + \sum_{j = 2}^{k} c_{i_{j - 1}, ij} + c_{ik, 0}

(1)

Then, the route planning problem can be formulated as the following optimization problem

S = \arg min \sum_{R_{i \in S}} C (R_{i})

(2)

where $L (R_{i}) \leq L$ .

In order to minimize the network energy consumption, the mobile sinks are required to visit all the data collection nodes (CHs) along constraint routes. This problem is related to the VRSPTW which is NP-hard problem. Even finding a feasible solution to the VRSPTW with fixed number of vehicles is NP-complete. We propose two heuristic algorithms to solve the route planning problem in the following two sections.

Cost-saving algorithm

The first heuristic algorithm builds the optimal routes by a route combination procedure. This procedure begins with n distinct partial routes in which each sensor is visited by a dedicated ME. Then, two partial routes with common end node are combined by adding an edge between them. The combination is guided by a measure of cost saving given by the following formula

sa v_{ij} = d_{0 i} + d_{0 j} - d_{ij}, 1 \leq i, j \leq n, i \neq j

(3)

$sa v_{ij}$ is the cost savings in distance results from visit node i and j on one route as opposed to visiting them individually directly from the BS.

As shown in Figure 1, node 0 represents the BS, node 1 to node 4 is the ordinary static sensor node in network. The Saving Heuristic algorithm first constructs four initial routes from BS to each node S = {R₁, R₂, R₃, R₄}. After that, the algorithm computes $sa v_{12}$ , $sa v_{13}$ , $sa v_{14}$ , $sa v_{23}$ , $sa v_{24}$ , and $sa v_{34}$ and finds that $sa v_{12}$ has the largest value. Routes $R_{1}$ and $R_{2}$ are combined into $R_{12} (0120)$ ; S = {R₁₂, R₃, R₄}, continue this procedure, combine $R_{3}$ and $R_{4}$ into $R_{34}$ .

In order to guarantee the time constraint of each route, we must consider the route direction when we combine two partial routes. Two partial routes with end node i and j, respectively, have compatible directions if node i is the first node on one partial route and node j is the last node on another partial route or on the opposite. We only add link to the compatible partial routes.

Furthermore, we must check time constraint in the heuristic algorithm. Let us examine the necessary and sufficient conditions for time feasibility when inserting a node x between node $i_{p - 1}$ and $i_{p}$ , $1 \leq p \leq m$ , on a partial feasible route $(i_{0}, i_{1}, i_{2}, \dots, i_{m})$ , $i_{0} = i_{m} = 0$ . Let $b_{i_{p}}^{new}$ be the new visit time of node $i_{p}$ after inserting node x

b_{i_{p}} = b_{i_{p - 1}} + s_{p - 1}

(4)

b_{i_{p}}^{new} = b_{i_{x}} + s_{x}

(5)

We compute the difference between these two start times as follows

F_{i_{p}} = b_{i_{p}}^{new} - b_{i_{p}}

(6)

If $F_{i_{p}} > 0$ , some of the nodes $i_{r}, p \leq r \leq m$ could become infeasible. Therefore, we should examine all the nodes’ time feasibility on the partial route. The following lemma ensures that any node that does not permit the ME to return to the BS within time constraint will not be added to the partial route.

Lemma 1

The necessary and sufficient conditions for time feasibility when inserting a node x between node $i_{p - 1}$ and $i_{p}$ , $1 \leq p \leq m$ , on a partial feasible route $(i_{0}, i_{1}, i_{2}, \dots, i_{m})$ , $i_{0} = i_{m} = 0$ is

b_{i_{r}} + F_{i_{r}} \leq L, p \leq r \leq m, b_{x} \leq L

(7)

Here, L is the time constraint of all routes.

The saving heuristic is described in the following algorithm.

Algorithm 1: Saving heuristic

Input: (1) G = (V, E),

V = {0, 1, 2, \dots, n}

, (2) L be the maximum length of a Route

Output:

S = {R_{1}, R_{2}, \dots, R_{m}}

S = {R_{1}, R_{2}, \dots, R_{n}}, R_{i} = (0, i)

;

2: for i = 1 to n do

3: for j = 1 to n do

4: Compute

sa v_{ij}

;

5: Build a max-heap H on all

sa v_{ij}

;

6: repeat

7: Get the root

sa v_{ij}

of H;

8: if

R_{ki}

and

R_{jm}

are compatible then

9: Combine

R_{ki}

and

R_{jm}

;

10: if the new partial route

R_{ji}

satisfy the time constraint then

11: Delete

R_{ki}

and

R_{jm}

from S;

12: Insert

R_{jm}

into S;

13: Get the next node of H;

14: goto line 8

15: until no feasible route can be combined;

16: return S.

Nearest-neighbor algorithm

The nearest-neighbor heuristic starts every route by finding the unrouted node closest to the BS. At every subsequent iteration, the heuristic searches for the node closest to the last node added to the route. This search is performed among all nodes which can be added to the end of the partial route without violating the time constraint. If the search fails, a new route is started at any time, unless there are no more nodes to schedule.

The metric used in this method tries to account for both geographical and temporal closeness of nodes. Assume the last node on the current partial route is i and j denotes any unrouted node, $c_{ij}$ measures the direct distance between the two nodes $d_{ij}$ , the time difference between the completion of visit i and the visiting begin time of j, $T_{ij} = b_{j} - (b_{i} + s_{i})$ , and the urgency (time remaining until the ME’s last visit start) of moving to node j, $v_{ij} = l_{j} - (b_{i} + s_{i} + t_{ij})$ . Then, the cost is given by the following formula

\begin{array}{l} c_{i j} = β_{1} d_{i j} + β_{2} T_{i j} + β_{3} v_{i j}, β_{1} + β_{2} + β_{3} \\ = 1, β_{1}, β_{2}, β_{3} \geq 0 \end{array}

(8)

The nearest-neighbor heuristic is described in the following algorithm.

Algorithm 2: Nearest-neighbor heuristic

Input: (1) G = (V, E),

V = {0, 1, 2, \dots, n}

, (2) L, the maximum length of a Route

Output:

S = {R_{1}, R_{2}, \dots, R_{m}}

S = \emptyset

k = 0

V' = V

;

2: for all node i in

V'

3: Compute the cost

c_{0 i}

;

4: Add the least-cost node i to partial route

R_{k} = (0, i)

;

V' = V - {i}

;

6: repeat

7: for every unrouted node j in V′do

8: Search for the least-cost node

c_{ij}

;

R_{k} = (0, i, j)

;

10: if

L (R_{k}) < L

then

11: Update the partial route

R_{k} = (0, i, j)

;

12: else

S = S \cup R_{k}

, add this route into the result set;

13:

k = k + 1

;

14: goto line 4, start a new route

15: until

V' = \emptyset

;

16: return S.

Performance evaluation

In this section, we evaluate the performance of MDCP protocol.

Experimental setup

In this simulation, sensor nodes are randomly and uniformly deployed within 800 × 800 m² area. The BS is located at the top left corner of the region. The movement speed of mobile sink varies from 0.2 to 1 m/s. In this experiment, energy consumption is considered for data transmission and reception only; while during other time periods, sensor nodes are supposed to be in the sleep mode for which no energy consumption is assumed. A source generates and stores a data sample of 2 bytes every second. It sends all the accumulated data to the BS every 20 min (i.e. the deadline is 20 min). Thus, the route length L must not be longer than 1200 m.

We compare the performance of the proposed heuristic algorithm referred to as cost-save based algorithm (SAV) and nearest-neighbor based algorithm (NN), respectively, with RDC and NET algorithm. RDC⁹ is a rendezvous-based data collection protocol that facilitates reliable data transfers from the network to mobile sinks. NET represents the network collecting data through multi-hop transmission without any mobile sinks.

Scalability of sensor nodes

An important factor that should be considered while designing a sensor network is the scalability, which measures how efficient a WSN is for small and large numbers of sensor nodes. The scalability of our algorithm is evaluated by testing the algorithm at varying number of sensor nodes (from 200 to 1000 nodes). The simulation is repeated for MEs of different deadline constraints (i.e. L = 800, 1000, and 1200). We also compare the energy consumption of our heuristic algorithms with NET and RDC when varying the number of sensor nodes. The main difference between our algorithm and RDC is that we minimize the total cost (distance, time) of the MEs’ tours which is not considered in RDC. Therefore, we compare the ME cost for these two algorithms by varying the number of nodes. The results are shown in Figures 2 –4, respectively.

Figure 2.

The impact of number of nodes on energy consumption for different deadline constraints.

Figure 3.

The impact of number of nodes on energy consumption for different algorithms.

Figure 4.

The impact of number of nodes on ME’s cost for different algorithms.

When the number of sensor nodes increased, larger number of clusters is formulated. This, in turn, leads to increase in the number of multi-hop nodes and therefore the network energy consumption increased as shown in Figure 2. It is also clear from this figure that the increase in the ME path constraint leads to less energy consumption of sensor nodes. This is due to the reason that increasing the path constraint allowed the MEs to travel larger area of the sensor field and hence reduced the number of multi-hop sensor nodes.

Figure 3 shows that all algorithm yield larger energy consumption when increasing the number of nodes. The NET algorithm incurred the most energy consumption because the multi-hop transmissions increase a lot with the larger number of nodes. Since our algorithms first group all the sensor nodes into clusters, the number of multi-hop nodes increases slowly compared with RDC algorithm. Therefore, our algorithm has the least energy consumption. The nearest-neighbor heuristic consumes less energy than saving heuristic a little because NN considers the distance from BS.

From Figure 4 we can see that the movement cost (total distance) varies with the number of nodes. In order to cover more nodes, the MEs must travel a longer path which leads to the increase in ME’s cost. The goal of our algorithm is to minimize the total cost of mobile sink’s routes within deadline constraint and the genetic algorithm presented in this article can obtain a least-cost feasible solution. In contrast, RDC protocol did not take into consideration the cost of mobile sink.

Impact of movement speed

In this section, we evaluate the network energy consumption when the speed of mobile sinks varies from 0.1 to 2 m/s. Only radio transmission energy is counted in the simulations. Figure 5 shows that all algorithms yield lower energy consumption when the mobile sinks move faster except NET. This is because the mobile sinks are able to collect data on a longer tour within the deadline. NET collects data through multi-hop routing without using MEs. The results of this simulation show that our algorithms can effectively take advantage of speed increase of the mobile sink.

Figure 5.

The impact of movement speed on energy consumption for different algorithms.

Impact of number of mobile sink

In this section, we evaluate the performance in terms of energy consumption and percentage of deadline misses by varying the mobile sink number constraint. From Figure 6 we can see that the network energy consumption decreases when the maximum ME number increases. This is because the more the ME, the less the multi-hop transmissions. Figure 7 shows that the percentage of deadline misses decreases when the mobile sink number increases. This is because the more the mobile sink, the more the sensor nodes would be covered within deadline. The NET algorithm does not use any ME; therefore, the deadline misses would not be affected by the number of mobile sinks.

Figure 6.

The impact of maximum number of MEs on energy consumption for different deadline.

Figure 7.

The impact of maximum number of MEs on percentage of deadline misses for different algorithms.

Conclusion and future work

In this article, we study the challenging problem of energy-efficient big data collection in WSNs. Although the mobile sink approaches can significantly reduce energy consumption of sensor nodes and increase the network lifetime, they increase the delay of response. This makes the mobile sink schemes not suitable for real-time and emergency applications. To address this challenge, we propose a four-phase mobility-assisted data collecting protocol called MDCP. It first divides the network into connected clusters, and the mobile sinks only collect data from CH nodes. Then, it builds a set of optimal travel routes for mobile sinks by running two heuristic algorithms presented in this article. To meet the number limitation of mobile sinks, a route combination procedure is conducted in MDCP. Extensive simulation results show that MDCP can provide substantial energy saving and incur the least movement cost compared with traditional multi-hop transmission data collecting protocols and the existing mobility-assisted data collecting protocols.

In this article, we assume that sensor nodes have infinite storage memory and the same data generation rate. In future work, we will consider the more practical scenario that sensor nodes have buffer limitation and different buffer overflow rate.

Footnotes

Academic Editor: Donghyun Kim

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported, in part, by the National Science Foundation for Young Scholars of China (61100048, 61102105, and 81273649) and the Natural Science Foundation of Heilongjiang Province (F2016034).

References

IBM. Four vendor view on big data and big data analytic: IBM, January 2012, http://www-01.ibm.com/software/in/data/bigdata/

Chen

Mao

Liu

Big data: a survey. Mobile Netw Appl 2014; 19: 171–209.

Cheng

Cai

. Drawing dominant dataset from big sensory data in wireless sensor networks. In: The 34rd annual IEEE international conference on computer communications (INFOCOM, 2015), Kowloon, Hong Kong, 26 April–1 May 2015.

Cai

Cheng

. Approximate aggregation for tracking quantiles in wireless sensor networks. In: The 8th annual international conference on combinatorial optimization and applications (COCOA2014), Maui, HI, 19–21 December 2014.

Cai

Goebel

Lin

Size-constrained tree partitioning: a story on approximating the multicast k-tree routing problem. Theor Comput Sci 2011; 412(3): 240–245.

Cai

Chen

Lin

A 3.4713-approximation algorithm for the capacitated multicast tree routing problem. Theor Comput Sci 2009; 410(52): 415–424.

Cai

Chen

Lin

. An improved approximation algorithm for the capacitated multicast tree routing problem. In: Accepted by the 2nd annual international conference on combinatorial optimization and applications (COCOA2008), St. John’s, Newfoundland, Canada, 21–24 August 2008, pp.286–295. Berlin: Springer.

Cai

Cheng

. Approximate aggregation for tracking quantiles and range countings in wireless sensor networks. Theor Comput Sci 2015; 607(3): 381–390.

Cheng

Cai

Curve query processing in wireless sensor networks. IEEE T Veh Technol 2015; 64(11): 5198–5209.

10.

Francesco

Das

SK.

Data collection in wireless sensor networks with mobile elements: a survey. ACM T Sensor Network 2011; 8: 1–31.

11.

Luo

Hubaux

. Joint mobility and routing for lifetime elongation in wireless sensor networks. In: Proceedings of the 24th IEEE conference on computer communications (INFOCOM), Miami, FL, USA, 13–17 March 2005, pp.1735–1746. New York: IEEE.

12.

Bozdag

Brewer

. Data harvesting with mobile elements in wireless sensor networks. Comput Netw 2006; 50(17): 3449–3465.

13.

Somasundara

Ramamoorthy

Srivastava

MB.

Mobile element scheduling with dynamic deadlines. IEEE T Mobile Comput 2007; 6(4): 395–410.

14.

Xing

Wang

Jia

. Efficient rendezvous algorithms for mobility-enabled wireless sensor networks. IEEE T Mobile Comput 2012; 11: 47–60.

15.

Sugihara

Gupta

Optimizing energy-latency trade-off in sensor networks with controlled mobility. In: Proceedings of the 28th IEEE conference on computer communications (INFOCOM), Rio de Janeiro, Brazil, 19–25 April 2009, pp.2566–2570. New York: IEEE.

16.

Sugihara

Gupta

Optimal speed control of mobile node for data collection in sensor networks. IEEE T Mobile Comput 2010; 9(1): 127–139.

17.

Rao

Biswas

Network-assisted sink navigation for distributed data gathering: stability and delay-energy trade-offs. Comput Commun 2010; 33(2): 160–175.

18.

Abdullah

Khaled

Alasha’ary

. Connectivity-based data gathering with path-constrained mobile sink in wireless sensor networks. Wirel Sens Netw 2014; 6: 118–128.

19.

Yin

Zhu

. Mobile data gathering with time-constraints in wireless sensor networks. Wireless algorithms, systems, and applications. New York: Springer International Publishing, 2015.

Mobility-assisted big data collecting in wireless sensor networks

Abstract

Keywords

Introduction

Related works

MDCP

Overview of MDCP

Network clustering

Route planning problem formulation

Definition 1

Definition 2

Cost-saving algorithm

Lemma 1

Nearest-neighbor algorithm

Performance evaluation

Experimental setup

Scalability of sensor nodes

Impact of movement speed

Impact of number of mobile sink

Conclusion and future work

Footnotes

Declaration of conflicting interests

Funding

References