Sage Journals: Discover world-class research

Abstract

Wireless sensor networks with the mobile sink can help to prevent the hot-spot problem and improve the network lifetime. However, in practice, the trajectories of the sink can not ideally change due to the obstacle of the environment or the requirement of the application. The constraint on trajectory of the mobile sink causes the different connection time between the mobile sink and the sensor node, which might result in the imbalance depletion of energy. We propose here an efficient data gathering policy to jointly consider the constrained mobility of the sink and the different connection time at the sensor node. The policy increases the network lifetime in wireless sensor networks with path-constrained mobile sink by optimizing the assignment sensor node. In addition, we also propose the policy to cope with the overlapped connection time of the sink and sensor node due to the movement of the sink. The simulation results demonstrate the effectiveness of the proposed policy: by carefully considering the trajectory of the sink and effectively assigning the sensor node, the network lifetime is increased.

1. Introduction

As a promising technology for connecting smart object to create the new Internet of Things, wireless sensor networks (WSNs) have been widely deployed in many potential applications such as environmental monitoring, security, surveillance, plant automation, and control emergency response [1]. In these applications, the sensor nodes are responsible for monitoring environment, gathering the relevant data, and reporting to the center data node, referred to as sink. Although the sensor nodes have significant improvement in processing and computing, they are still powered by the limited battery. Furthermore, it is difficult to replace the battery of the sensor node due to the environmental disturbance. Thus, energy conservation to prolong the network lifetime is still the major issue in WSNs.

Network lifetime which is defined as the time until the first sensor's energy runs out is an important performance metric in WSNs [2, 3]. In traditional WSNs, all the sensor nodes are configured to forward collected data to the sink through multihop communication. One major drawback of this communication is that the node near the sink will be burdened by forwarding large amount of traffic from other nodes to the sink. The imbalanced traffic causes the early depletion of energy at the sensor node nearby sink. This problem is known as hot-spot problem in wireless communication, which might lead to the nonuniformly distributed energy among the sensor nodes [4].

To mitigate the hot-spot problem caused by the static sink [2], the mobile sink has been proposed as a solution to balance the energy consumption among the hot-spot nodes. Intuitively, as the sink traverses the networks, the hot-spot nodes will be distributively changed over the time, and thus the energy consumption around the sink spreads among the sensor nodes which helps to improve the network lifetime [5].

The deployment of the mobile sink can be classified into two cases based on the trajectory of the sinks: unconstrained trajectory and constrained trajectory. In the first case, the sinks have freedom to traverse around the network. The main objective here is how to optimize the movement of the mobile sink as in [2, 6]. However, in the most practical scenarios, the trajectory of mobile sink has been constrained or predetermined. These limitations occur due to (i) the obstacle of the environment such as road, wall, and river [7] and (ii) the operation of the application such as in urban area, where the sinks are typically installed on the public transport vehicle which follow the predetermined trajectory [8]. The main objective in this context is how to effectively route the data to mobile sink as it traverses the networks [9, 10]. In this paper, we aim at going further in this direction: we propose to optimize the network lifetime of WSNs with mobile sink whose trajectory is predetermined.

Maximizing the network lifetime requires balancing the traffic load among sensor nodes. In conventional way, the shortest path policy (SPP) is used to route the data from the sensor nodes to the sinks based on the hop distance information. However, since there is no mechanism to control the amount of traffic forwarded to the sink, this policy is unable to balance the energy consumption among the sensor nodes so as to prolong the network lifetime.

Besides, connection time between sensor node and sink is also an important metric to conserve energy. For a given amount of packets, transmitting packet at low data rate over long duration is more energy efficiency than transmitting packet at the high data rate over short duration [11]. Especially in WSNs with path-constrained mobile sink, the connection time between the sink and the sensor nodes is different which results in different transmission rate at the sensor node. Thus, we can also achieve significant network lifetime by carefully considering the connection time between the mobile sink and the sensor nodes.

In this paper, we propose the novel data gathering policy for mobile sink with predetermined trajectory. We consider both traffic load and connection time as metric for modeling the network lifetime. Our objective is to balance the depletion of the energy at the sensor node and, thereby, the network lifetime is improved. The major contributions of our paper are as follows: (i)

We formulate the network lifetime as the function of the transmission rate. The transmission rate is the ratio of traffic load to connection time between the sensor node and the mobile sink. We show that maximizing network lifetime is equivalent to balancing the transmission rate of sensor nodes (Section 3).

(ii)

We derive the distributed algorithm based on the duality theory and the subgradient method (Section 4).

(iii)

In addition, the communications between sensor nodes and mobile sink are able to overlap each other due to the movement of the mobile sink. Thus, we also propose the scheduling to further mitigate this collision (Section 5).

(iv)

We thoroughly evaluate the performance of this policy by simulations. Our algorithm results in better network lifetime and higher throughput than the existing benchmark algorithms. Furthermore, it can cope with high speed of the mobile sink (Section 7).

2. Related Works

In recent years, many methods on using mobile sink in WSNs have been proposed to improve the networks lifetime. They can be categorized into two groups based on the trajectory of mobile sink: (i) unconstrained trajectory, where the mobile sinks have freedom to travel all-around the networks, and (ii) constrained trajectory, where the mobile sinks are only allowed to travel on the predetermined trajectory such as road, line, and circular path.

2.1. Unconstrained Trajectory of Mobile Sink

The main objective of this group is to determine how the mobile sink goes to collect data. One of the common approaches is to visit all the sensor nodes to receive data directly. The movement of the mobile sink follows the traveling salesman algorithm [12]. However, since the number of sensor nodes increases, the problem becomes intractable. In order to overcome this challenge, the mobile sink only visits a subset of nodes designated as cluster-heads [2, 6]. The traveling salesman algorithm is used to determine the movement of the mobile sink among these cluster-heads. The sensors outside the transmission range of the mobile sink send data to their associated cluster-head via multihop transmission.

Other approaches of optimizing the movement of the mobile sink are in [13, 14]. In particular, the research in [13] proposed the realistic routing algorithm for mobile sink based on the sojourns time of the mobile sink at the cluster-head. The improvement of the networks lifetime is achieved by dynamically changing the epoch of the mobile sink at each cluster-head regarding the energy consumption of the sensor node. An extended version of this approach was introduced in [14]. In this work, the sojourn time at the cluster-head is determined by considering the load balancing and the distance constraint of the mobile sink.

In these works, the connection time between mobile sink and sensor node has been controlled to maximize the network lifetime. Furthermore, the mobile sink has freedom to travel among the cluster-heads. On the contrary, in our paper, this connection time is fixed due to the predetermined trajectory of the mobile sink and the sink does not stop for collecting data. Thus, they limit the applicability of these works to our scenarios.

2.2. Constrained Trajectory of Mobile Sink

The main objective of this group is to find the effective data gathering schemes to collect data from the sensor nodes. In [7, 15], the authors provide a closer look at the used mobile sink with constrained movement in WSNs. In particular, the work in [15] evaluates the network lifetime under different mobility patterns of the sinks. The evaluation results highlight the benefit of using mobile sink in order to prolong network lifetime as well as balance traffic load.

In [16], the scheduling problem in path-constrained mobile sink has been considered. Based on the movement of the sink, the scheduling policy determines a number of sensor nodes that are responsible for transmitting data by exploiting the trade-off between reliability and energy consumption. An extended version of this algorithm, where several sensor nodes with similar observation transmit data to the sink, was introduced in [17]. However, in these scenarios, all the sensor nodes communicate with the sink through one-hop communication, which is not applicable to our scenarios: only several sensor nodes can directly transmit to the sink.

As to the problem involved in gathering data from sensor nodes to mobile sink through multihop communication, various schemes like hop-based approach [18, 19], QoS-based approach [9, 20], and relay-based approach [21, 22] have been proposed. In these approaches, the sensor nodes are divided into two groups: (i) subsink nodes which can directly communicate with the mobile sinks and (ii) member nodes which can communicate with the sink via multihop transmission. The main objective here is to find an optimal assignment from the member node to the subsinks.

In the hop-based approach, each member sends data to the closest subsink in terms of hop count. Dijkstra's algorithm is applied to find the route from members to subsinks [18, 19]. Although this approach reduces the overall energy consumption of the networks, it might not guarantee the improvement of network lifetime.

The QoS-based approach utilizes the expected QoS to route the data to the sink. In [9], the author modified the shortest path algorithms to adapt to the delay constraint on the sensor data. In particular, in [20], the network lifetime is maximized under the total data collection of the subsink as a QoS constraint. However, the detailed solution of the problem has not been introduced in the paper. Similar approach has been introduced in [23] where the objective function is the minimization of the total hop distance from the member node to the subsink. These approaches can help to improve the overall throughput or delay of the networks. However, they require the centralized computation, which might result in the large amount of message overhead in networks.

The relay-based approach is similar to the hop-based approach since the member nodes forward data to the closest subsinks. The main difference here is the way mobile sinks collect data at the subsinks. In [21], the sink sends a query packet toward the subsinks. Then, it selects one neighbor sensor as its agent. The collected data is transmitted from the subsink to mobile sinks through relaying by its agent. A similar approach has been introduced in [22], where the set of the subsinks is adjusted based on the density of the networks. This approach can help to reduce the latency in collecting data. However, the agent node will suffer high traffic load which might result in low network lifetime.

Contrary to previous work, our paper focuses on finding optimal scheme for network lifetime maximization. We jointly consider the traffic load, the connection time between subsinks and mobile sink, and the hop distance information to make routing decision. All data from the member node will be buffered at the subsinks. Then, the subsinks forward data to the mobile sink when the mobile sink goes to the transmission range of the subsinks.

3. Problem Statement

3.1. Network Model

Consider the WSN with sensor nodes and mobile sink as shown in Figure 1. The sensor nodes are randomly deployed to keep monitoring the environment and periodically generating data packet. The mobile sink is installed on the vehicle and moves along a fixed trajectory to collect data from sensor nodes. According to the movement of the mobile sink, the network region is divided into two areas: single-hop area in which the sensor can directly transmit data to the sink and multihop area in which the sensor communicates with the mobile sink via multihop transmission. Similar to the work in [23, 24], the sensor nodes within single-hop area are called subsinks and the sensor nodes within multihop area are called members.

Figure 1

Wireless sensor networks with path-constrained mobile sink. The sinks are installed on the vehicle and move along the predetermined trajectory.

Let $S = \{s_{1}, s_{2}, \dots, s_{S}\}$ be the set of subsinks. $M = \{m_{1}, m_{2}, \dots, m_{M}\}$ is the set of members. Let $α_{i}$ be the generated data at each sensor i per round. $h_{i, j}$ is the closest hop distance between member $m_{i}$ and subsink $s_{j}$ .

In our model, each member node is associated with only one subsink. Let $x_{i, j}$ denote the binary assignment variable, which indicates the assignment of member $m_{i}$ to subsink $s_{j}$ : $\begin{matrix} x_{i, j} = \{\begin{cases} 1, & member m_{i} is assigned to subsink s_{j} \\ 0, & otherwise. \end{cases} \end{matrix}$ (1) A feasible assignment should assign one member to only one subsink: $\begin{matrix} \sum_{j \in S} x_{i, j} = 1, \end{matrix}$ (2) $\begin{matrix} x_{i, j} = \{0,1\} . \end{matrix}$ (3) In addition, some member nodes may be assigned to the long hop distance subsink. Assigning member node to far subsink while there are some nodes in nearby subsinks is in fact waste of resources (energy) in the network. To prevent this problem, we limit the hop distance from each member node to its subsink as not larger than H. We will incorporate the effect of this constraint H in simulation: $\begin{matrix} \sum_{j \in S} x_{i, j} h_{i, j} \leq H, \forall i \in M . \end{matrix}$ (4)

The mobile sink moves with a constant speed v. Let $t_{i}$ be the expected connection time of subsink i with mobile sink. This is the time when mobile sink enters (or leaves the transmission range of previous subsinks) the transmission range of subsink i as shown in Figure 2. We calculate $t_{i}$ by using the current distance from the subsink to the mobile sink ( $d_{i}$ ), the transmission range of the sensor node $s_{i}$ (d), the speed of the mobile sink M(v), and the angle between trajectory of the mobile sink and a line that connects mobile sink and subsink ( $θ_{i}$ ). According to Figure 2, the expected connection time of each subsink $s_{i}$ is given as $\begin{matrix} t_{i} = \frac{d \sin (θ_{i} + \arcsin ((d_{i} / d) \sin θ_{i}))}{v \sin θ_{i}} . \end{matrix}$ (5)

Figure 2

Expected connection time $t_{i}$ between mobile sink and subsink i.

The knowledge of hop distance information and connection time is assumed to be available to any sensor node in the system. Since the location of all sensor nodes is fixed and the trajectory of the mobile sink is predetermined, such information can be retrieved in advance.

3.2. Energy Model

All the sensors have limited power. Let $E_{i n t}$ be the initial energy at sensor nodes. At the sensor node, we assume that communications are the main source of energy consumption. According to [25, 26], the energy consumption for transmitting α bits over duration τ is given by $\begin{matrix} e_{t} = τ N (2^{α / τ} - 1), \end{matrix}$ (6) where N is noise power. Also, the energy for receiving α bits is given by $\begin{matrix} e_{r} = E_{c i r} α, \end{matrix}$ (7) where $E_{c i r}$ represents the energy consumption per bit by sensor's circuit.

Since the subsink also receives data from the member, the total energy consumption at each subsink i per round includes both transmission and reception data: $\begin{matrix} E_{j} = t_{j} (2^{r_{j} / t_{j}} - 1) + r_{j} E_{c i r}, \end{matrix}$ (8) where $r_{j} = \sum_{i \in M}^{} x_{i, j} α_{i} + α_{j}$ represents the total collected packets of subsink j per round. The following proposition confirms an interesting feature of the energy consumption in wireless networks: transmitting the same amount of data with low data rate over long duration consumes less energy than transmitting data with high data rate over short duration.

Proposition 1.

The energy consumption per round of each subsink j is monotonically increasing in $r_{j} / t_{j}$ , where $r_{j} = \sum_{i \in M}^{} x_{i, j} α_{i} + α_{j}$ .

Proof.

The proof is given in Appendix A.

3.3. Problem Statement

Since the subsinks are responsible for collecting packet from the member node and forwarding it to the mobile sink, they tend to consume energy more than the member nodes. Similar to the work in [23, 24] and references therein, we focus on the energy efficiency at the subsink by optimizing the member node assignment such that (i) each member is assigned only one subsink, (ii) the total hops from members to each subsink do not exceed H, and (iii) the network lifetime is maximized.

Given the initial energy $E_{i n t}$ , the lifetime of subsink j is $E_{i n t} / E_{j}$ . We propose here the max-min fairness assignment (MMFA) to maximize the networks lifetime of the network: $\begin{matrix} maximize \min_{j \in S} \frac{E_{i n t}}{E_{j}} \end{matrix}$ (9) subject to (2)–(4).

From (8), the objective function can be rewritten as $\begin{matrix} maximize \min_{j \in S} \frac{E_{i n t}}{t_{j} (2^{r_{j} / t_{j}} - 1) + r_{j} E_{c i r}} . \end{matrix}$ (10) From Proposition 1, since the denominator in (10) is monotonically increasing in $r_{j} / t_{j}$ , and $E_{i n t}$ is fixed, the MMFA problem becomes $\begin{matrix} minimize \max_{j \in S} \frac{1}{t_{j}} (\sum_{i \in M} x_{i, j} α_{i} + α_{j}) \end{matrix}$ (11) subject to (2)–(4).

Since $\sum_{i \in M}^{} x_{i, j} α_{i} + α_{j}$ is the total receiving packet per round at subsink j and $t_{j}$ is the transmission time of subsink j to mobile sink, the objective function in (11) can be interpreted as the transmission rate of subsink in single round. The MMFA becomes the min-max transmission rate problem, while satisfying the hop distance constraint.

MMFA is a nonconvex and NP-hard problem. We can get the optimal solution by using some global optimal methods such as branch and bound and brute-force search. However, in global methods, the computational complexity grows exponentially with increase of the network size. To overcome this challenge, we turn to the Lagrangian method. Even though this approach is suboptimal and can not guarantee the optimality, the assignment based on the Lagrangian method is low complexity, fast convergence, and distributed implementation.

4. Solution Approach via Lagrangian Method

In this section, we develop the distributed algorithms for solving MMFA. We first use the Lagrange multiplier for dualizing the coupled constraint. Then, we use the subgradient method to develop a distributed solution for MMFA.

4.1. Dualizing by Using Lagrangian Multiplier

Problem (11) does not lead to distributed computation. We transform it into epigraph form. The decision variables are the vector $x_{i, j}$ and the scalar η which is also the objective function $\begin{matrix} minimize η \end{matrix}$ (12) $\begin{matrix} s.t. \frac{1}{t_{j}} (\sum_{i \in M} x_{i, j} α_{i} + α_{j}) \leq η, \forall j \in S \\ (2), (3), (4), \end{matrix}$ (13) where η is introduced as an auxiliary variable. It is worth noting that constraints (4) and (13) are coupled among the members, which are obstacle to the distributed solution. To deal with this issue, we apply the Lagrangian relaxation to decouple these constraints. Let λ and μ be the Lagrange multipliers associated with constraints (4) and (13). The Lagrange function of (12) is given as $\begin{matrix} L (x, η, λ, μ) = η + \sum_{j \in S} λ_{j} (\frac{1}{t_{j}} (\sum_{i \in M} x_{i, j} α_{i} + α_{j}) - η) + \sum_{j \in S} μ_{j} (\sum_{i \in M} x_{i, j} h_{i, j} - H) . \end{matrix}$ (14) By rearranging and regrouping the terms based on the primal variables, we have $\begin{matrix} L (x, η, λ, μ) = η (1 - \sum_{j \in S} λ_{j}) + \sum_{j \in S} (\frac{λ_{j}}{t_{j}} α_{j} - H μ_{j}) + \sum_{j \in S} \sum_{i \in M} (\frac{λ_{j}}{t_{j}} α_{i} + μ_{j} h_{i, j}) x_{i, j} . \end{matrix}$ (15)

The Lagrange dual function $D (λ, μ)$ is the minimum value of the function $L (x, η, λ, μ)$ over primal variable $(x, η)$ : $\begin{matrix} D (λ, μ) = m i n L (x, η, λ, μ) \\ s.t. \sum_{j \in S} x_{i, j} = 1, \forall i \in M \\ x_{i, j} = \{0,1\}, \forall i \in M, \forall j \in S . \end{matrix}$ (16) The dual function can be rewritten as follows: $\begin{matrix} D (λ, μ) = \{\begin{cases} \min_{\begin{smallmatrix} \sum_{j \in S}^{} x_{i, j} = 1, \forall i \in M \\ x_{i, j} = \{0,1\}, \forall i \in M, \forall j \in S \end{smallmatrix}} \sum_{i \in M} \sum_{j \in S} (\frac{λ_{j}}{t_{j}} α_{i} + μ_{j} h_{i, j}) x_{i, j} + \sum_{j \in S} (\frac{λ_{j}}{t_{j}} α_{j} - H μ_{j}) & if \sum_{j \in S} λ_{j} = 1 \\ - \infty, & otherwise \end{cases} = \{\begin{cases} \sum_{i \in M} f_{i} (λ, μ) + \sum_{j \in S} (\frac{λ_{j}}{t_{j}} α_{j} - H μ_{j}), & if \sum_{j \in S} λ_{j} = 1 \\ - \infty, & otherwise, \end{cases} \end{matrix}$ (17) where $f_{i} (λ, μ)$ is the optimal solution of the following subproblem: $\begin{matrix} S_{1} : f_{i} (λ, μ) = \min \sum_{j \in S} (\frac{λ_{j}}{t_{j}} α_{i} + μ_{j} h_{i, j}) x_{i, j} \\ s.t. \sum_{j \in S} x_{i, j} = 1, \forall i \in M \\ x_{i, j} = \{0,1\}, \forall i \in M, \forall j \in S . \end{matrix}$ (18) The solution of the subproblem $S_{1}$ is depicted in Algorithm 1. We assign member i to subsink $j (x_{i, j} = 1)$ if $j = a r g m i n \{(λ_{j} / t_{j}) α_{i} + μ_{j} h_{i, j}\}$ . Otherwise, $x_{i, j}$ should be 0.

Algorithm 1: Solution for subproblem $S_{1}$ .

if $j = \arg \min \{{(λ}_{j} / t_{j}) α_{i} + μ_{j} h_{i, j}\}$ then

$x_{i, j}^{*} \Leftarrow 1$

else

$x_{i, j}^{*} \Leftarrow 0$

end if

Algorithm 1 can be implemented in distributed manner with local information. Since each member i only needs the knowledge of the dual variable from the subsink node $(λ, μ)$ , the value of $x_{i, j}^{*}$ can be calculated locally.

Now, we turn to the Lagrange dual problem corresponding to (12). The dual problem is to maximize the $D (λ, μ)$ with respect to $(λ, μ)$ : $\begin{matrix} Dual: max D (λ, μ) = \sum_{i \in M} f_{i} (λ, μ) + \sum_{j \in S} (\frac{λ_{j}}{t_{j}} α_{j} - H μ_{j}) \\ s.t. \sum_{j \in S} λ_{j} = 1 \\ λ_{j} > 0, μ_{j} > 0, \forall j \in S . \end{matrix}$ (19) In the following, we describe the subgradient projection method to solve the dual problem (19).

4.2. Subgradient Projection Method

The subgradient projection method is an iterative way to solve the Lagrange dual problem. We use the notation of $[p a r a m e t e r]^{(k)}$ to represent the specific value of $[p a r a m e t e r]$ at iteration k. The subgradient of the Lagrange function at iteration k is $\begin{matrix} \frac{\partial D}{\partial λ_{j}} = \frac{1}{t_{j}} (\sum_{i \in M} x_{i, j}^{* (k)} α_{i} + α_{j}), \forall i \in M, \forall j \in S, \\ \frac{\partial D}{\partial μ_{j}} = \sum_{i \in M} x_{i, j}^{* (k)} h_{i, j} - H, \forall i \in M, \forall j \in S . \end{matrix}$ (20)

The update of dual variables at each iteration is given as $\begin{matrix} λ_{j}^{(k + 1)} = Π_{j} [λ_{j}^{(k)} + s_{(k)} \frac{1}{t_{j}} (\sum_{i \in M} x_{i, j}^{* (k)} α_{i} + α_{j})], \\ μ_{j}^{(k + 1)} = {[μ_{j}^{(k)} + s_{(k)} \sum_{i \in M} x_{i, j}^{* (k)} h_{i, j} - H]}^{+}, \end{matrix}$ (21) where ${[x]}^{+} = \max \{x, 0\}$ and $Π_{j} [x]$ is the jth component of the Euclidean projection of x onto $\{λ \geq 0 | \sum_{j \in S}^{} λ_{j} = 1\}$ . $\{s_{(k)}\}$ is the stepsize that satisfies the nonsummable diminishing properties: $0 < s_{(k)} < 1$ ; $\sum_{k = 0}^{\infty} s_{(k)} = \infty$ ; and $\sum_{k = 0}^{\infty} s_{(k)}^{2} < \infty$ to ensure the convergence.

In the sequel, we combine various steps into our main algorithms to solve MMFA in distributed manner. Our algorithm is motivated by the approach in [27], but it is not exactly the same. The pseudocode for this algorithm is illustrated in Algorithm 2.

Algorithm 2: Distributed Fairness Assignment (DFA).

Step 1. Initialization.

(i) All member nodes set $x_{i, j}^{(0)} = 0$ for all $i \in M$ , $j \in S$ .

(ii) Every sub-sink node j generates and broadcasts the initial value $λ_{j}^{(0)}$ , $μ_{j}^{(0)}$ to member nodes.

(iii) Set $k = 1$ .

Step 2. At each member node i

(i) Receive $λ_{j}^{(0)}$ , $μ_{j}^{(0)}$ from the sub-sink.

(ii) Update the assignment variable $x_{i}^{(k)} = \{x_{i, j}^{(k)}\}$ by solving the sub-problem (18).

Let $j_{i}^{(k)}$ be the index of nonzero element of $x_{i}^{k}$

(iii) Transmit $x_{i, j}^{(k)}$ to sub-sink $j_{i}^{(k)}$ , if $x_{i, j}^{(k)} = 1$ .

Step 3. At each sub-sink node j

(i) Receive $x_{i, j}^{(k)}$ from the member node.

(ii) Update the dual variable for the next iteration:

$λ_{j}^{(k + 1)} = Π_{j} [λ_{j}^{(k)} + s_{(k)} \frac{1}{t_{j}} (\sum_{i \in M} x_{i, j}^{* (k)} α_{i} + α_{j})]$

$μ_{j}^{(k + 1)} = {[μ_{j}^{(k)} + s_{(k)} \sum_{i \in M} x_{i, j}^{* (k)} h_{i, j} - H]}^{+}$ .

(iii) Broadcast the new $λ_{j}^{(k + 1)}$ , $μ_{j}^{(k + 1)}$ to member nodes.

Step 4. Update iteration.

$k \leftarrow k + 1$ .

if $k < K$ then

Go to Step 2.

end if

Step 5. Return the assignment variable ${\{x_{i, j}^{* (k)} α_{i}\}}_{i \in S, j \in M}$ .

Implementation of MMFA. Implementation of the MMFA requires the message exchange between all subsinks and between subsinks and member nodes. By moving around all subsinks, the mobile sink can help to collect and broadcast such information to each subsink and member. The use of mobile sink to send such information can be found in literature [24, 28].

It is worth noting that the advantage of using Algorithm 2 to solve the MMFA problem is to eliminate the message exchange between member nodes. Since the number of the member nodes is large in comparison with the subsinks, Algorithm 2 can reduce the large amount of message exchange between sensor nodes. Furthermore, each node has to update its own objective function. It enables the partially distributed implementation of our proposed method with little coordinator from the mobile sink.

Optimality of MMFA. In general, we can use some global optimization methods such as exhausted search and branch and bound algorithms to achieve the optimal solution of the primal problem (12). However, solving these methods optimally becomes computationally intractable when the number of the computations exponentially increases with the increasing of the sensor nodes [29]. By using the Lagrangian method, Algorithm 2 can help to reduce the computations by decomposing the primal problem into subproblems which can be solved at each of the subsinks and member nodes.

However, since the original problem is not a convex problem, the MMFA does not always guarantee the optimal solution. There exists an optimal gap between the MMFA algorithms and the optimal algorithms based on global optimization methods. We will show that the solution of the MMFA is not too far from the optimal solution in simulation.

4.3. Convergence Analysis

In the sequel, we show the convergence of Algorithm 2 for MMFA problem. More specifically, we show that Algorithm 2 will converge to the optimal solution of (19) with a sufficient number of iterations.

Proposition 2.

Let $D^{*}$ denote the optimal value of the dual function $D (λ, μ)$ , and let $(λ^{*}, μ^{*})$ be the optimal variable of the dual problem (19). Let $D_{b e s t}^{(k)}$ be the maximum value of the dual objective function after k iterations; that is, $D_{b e s t}^{(k)} = \max_{i = 1 \dots k} D^{(i)}$ . Assume that ${‖(λ^{*}, μ^{*}) - (λ^{(1)}, μ^{(1)})‖}_{2}^{2}$ is bounded, that is, by $A > 0$ . Then, we have $\begin{matrix} \lim_{k \to \infty} D_{b e s t}^{(k)} = D^{*} . \end{matrix}$ (22) In addition, $D_{b e s t}^{(k)}$ also satisfies $\begin{matrix} D^{*} - D_{b e s t}^{(k)} \leq \frac{A + \sum_{i = 1}^{k} s_{(i)}^{2} (B + C)}{\sum_{i = 1}^{k} s_{(i)}}, \end{matrix}$ (23) where $B = \sqrt{{(\sum_{i \in M}^{} \max_{j} h_{i, j})}^{2} + (M - 1) H^{2}}$ . C is the maximum capacity of the links.

Proof.

The proof is in part borrowed from [30, 31] and is given in Appendix B.

The bound derived in Proposition 2 predicts the behavior of the convergence of Algorithm 2. The larger the value of H, the larger the value of B, and thereby, more iterations are required to obtain the optimal value. Similar to H, the number of member nodes M also influences directly the convergence speed of the algorithms.

5. Subsink Collision Avoidance (SCA)

Communications between subsink and mobile sink are able to overlap each other due to the movement of the mobile sink. We proposed here the greedy scheduling to avoid the transmission collision.

In this scheduling, we follow from the interesting property: if more nodes join forward data from the member node, the energy consumption and traffic load at the subsink are reduced. We would maximize the number of overlapped subsinks by scheduling the subsink which has the smallest transmission time among all overlapped subsinks. In this way, we can have more time left to schedule the others and thus more nodes become the subsinks.

Mobile sink calculates the expected connection time $t_{i}$ as in (5) with each subsink $i \in S$ and applies the following SCA strategy: (1)

Initially, let A be set of the scheduling subsinks and let A be empty.

(2)

If subsinks $i \in S$ with no overlapping transmission time exist, mobile sink adds them to scheduling set A and deletes i from S.

(3)

Else, while S is not empty,

(a)

choose a subsink $i \in S$ that has the smallest transmission time,

(b)

add i to A,

(c)

remove all subsinks from S which overlap transmission time with i.

(4)

Update the set of subsinks: $S \leftarrow A$ .

As a consequence, we schedule the subsink which has the transmission time as small as possible. By this way, more subsinks that participated in forwarding traffic impose a long network lifetime. This greedy algorithm comes from the interval scheduling problem [32] which can obtain the maximum nonoverlapping subsinks.

6. Data Gathering Scheme for Maximizing Network Lifetime

In this section, we develop the data gathering scheme incorporating the MMFA and the SCA schemes. The scheme includes three phases: subsink discovery phase, assignment phase, and data collection phase.

In the subsink discovery phase, the mobile sink calculates the connection time $t_{j}$ of each sensor node and executes the SCA to determine the set of subsinks. Then, it broadcasts the messages including the information about the list of subsinks to entire networks.

In the assignment phase, after receiving the list of subsinks, the member nodes apply the shortest path algorithm to build the route from themselves to all subsinks and broadcast this information to the subsink. By this way, the subsinks can have all hop distance information from themselves to all member nodes. The MMFA is executed to optimize the assignment from the member node to the subsink. Finally, the member nodes construct the route from themselves to the corresponding subsinks based on the optimal assignment.

In the data collection phase, at each round, all sensor nodes collect the data from the environment. The collected data is forwarded to the subsinks according to the routing table at the member node before the mobile sink goes into the communication range. The subsink transmits data to the mobile sink with transmission rate in (11).

7. Performance Evaluation

In this section, we evaluate the proposed assignment method (MMFA) in comparison with a few existing policies under different performance criteria. We model the network environment and provide the numerical result by using MATLAB simulator. We implement the following policies for comparison: (1)

The shortest path policy (SPP) from the hop-based approach which relies on the hop distance information to route data. Each member node will send its data to the closest subsink in terms of hop count. Dijkstra's algorithm is applied to find the route from the member node to the subsink [18].

(2)

The minimum total hop policy (MTHP) from the QoS-based approach which guarantees the amount of data collection at subsink. This policy has been introduced in [23]. It assigned the member node such that the total hops from members to subsinks are minimized. Since the data collection at each subsink is proportional to the number of member nodes, the QoS requirement is represented as the constraint on the number of member nodes assigned to each subsink, $M_{m i n}$ : $\begin{matrix} m i n \sum_{i \in M} \sum_{j \in S} x_{i, j} h_{i, j} \\ subject to \sum_{i \in M} x_{i, j} \geq M_{m i n}, \forall j \in S . \end{matrix}$ (24)

(3)

The max-min fairness assignment (MMFA) which is our proposed algorithms.

We measure the following metrics to evaluate the performance of these polices: (i)

Transmission rate of the subsinks is calculated as (11). It represents the convergence of our algorithms.

(ii)

Network lifetime is the total number of rounds of the mobile sink before first node runs out of its energy.

(iii)

Average throughput is the total collected packets by the mobile sink at each round.

(iv)

Energy balance index is the standard deviation of the energy consumption of sensor nodes. It measures the imbalance of the energy consumption under difference policies. The energy balance index is calculated as $\begin{matrix} J = \sqrt{\frac{\sum_{j \in S}^{} {(E_{j} - \bar{E})}^{2}}{|S|}}, \end{matrix}$ (25)

where $\bar{E}$ is the average energy consumption, $E_{j}$ is the energy consumption of subsink j, and $|S|$ is the number of subsinks.

7.1. Simulation Environment

7.1.1. Network Scenario

We consider random network topologies where all sensor nodes have been randomly placed in the square 60 × 60 m². Two nodes can communicate with each other if their distance is not longer than 10 m. The dotted line in Figure 3 shows the communication link of sensor nodes.

Figure 3

Mobility pattern is used in evaluation.

7.1.2. Mobility Model

We consider two mobility patterns of the sink which have been used in [15] (Figure 3). The arrow line shows the trajectories of the mobile sink.

7.1.3. Simulation Parameters

The simulation parameters are represented in Table 1.

Table 1

Network parameters used in simulation.

Parameters	Values
Number of sensor nodes	50 to 150 nodes
Transmission range of sensor	10 m
Mobile sink's speed (B)	8 to 20 m/s
Bandwidth (B)	20 kHz
Noise ( $N_{0}$ )	−15 dB
Energy consumption in circuit ( $E_{cir}$ )	42 mW
Energy budget at each sensor node ( $E_{int}$ )	100 J

7.2. Convergence of MMFA

We verify the convergence of the MMFA by investigating the transmission rate over 100 iterations. Behaviors of the transmission rate under different movements of the sink have been shown in Figure 4. As predicted in the analysis, our algorithm is stable and converged.

Figure 4

Convergence of the MMFA algorithms.

The convergence rate depends on the value of H: the larger the H values, the larger the number of iterations to obtain an optimal value. This result is predicted in Proposition 2. In addition, there is a trade-off between the convergence speed and the networks lifetime: the large value of H also imposes low transmission rate of the subsinks and, thereby, results in long networks lifetime.

7.3. Optimality of MMFA

Since the Lagrangian method can not always guarantee the optimal solution, in the following, we evaluate the optimal gap which is defined by the distance between the variables η in (12) obtained by branch and bound method and MMFA algorithms. The branch and bound method can obtain the optimal solution by using the enumeration technique. We define the percentage from the optimality metric as follows: $\begin{matrix} Percent from optimality = \frac{η_{o p t i m a l} - η_{M M F A}}{η_{o p t i m a l}} \times 100 %, \end{matrix}$ (26) where $η_{M M F A}$ is the value of η under our proposed policy. $η_{o p t i m a l}$ is the value of η by using branch and bound method [29].

We conduct the simulation under different sensor node and H. As shown in Figure 5, the MMFA performs close to the optimal policy when the number of sensors is less than 150 in the outer-boundary mobility pattern (and 200 in inner-boundary mobility pattern). More specifically, we are within 8% in outer-boundary mobility pattern and 10% in inner-boundary mobility pattern. However, when the number of sensors is large, the performance of MMFA is far away from the optimal policy. Such behavior is predicted because there is a trade-off between performance loss and complexity of the MMFA. These results indicate that the MMFA has comparative performance with the optimal policy when the number of sensors is not too large.

Figure 5

Percentage from optimal solution of MMFA under different hop distance constraint.

7.4. Impact of the Traffic Load

Now, we investigate the impact of the traffic load $α_{i}$ . We set the traffic load from 0.1 packets/s to 1 packet/s and measure the throughput and networks lifetime. The Pareto curves, which depict the trade-off between throughput and network lifetime under variant of the traffic load, are given in Figure 6. There are two interesting features from these results. First, we observe a trade-off between throughput and network lifetime: with the increasing of throughput, the network lifetime is decreased. This is because high throughput induces much energy consumption related to transmitting and receiving packet and thus the networks lifetime is reduced. Second, the MMFA can cope with high traffic load at the subsinks. Since it makes assignment based on the transmission rate of the node, the congestion at the subsink is mitigated. Hence, its performance is slightly better than the SPP and MTHP.

Figure 6

Average throughput and network lifetime under variant traffic load.

In addition, the energy balance index J is depicted in Figure 7. The higher value of J means that some sensor nodes' energy runs out sooner. Consistent with the result shown in Figure 6, Figure 7 confirms the advantages of MMFA policy: it can distribute energy to subsinks with more balance than the others do. The SPP policy assigns the member nodes to the closest subsink that might offer high energy consumption at the subsink which has small connection time. On the other hand, the MTHP can cause imbalance energy consumption at the member node by assigning long forwarding paths from the members to the subsinks.

Figure 7

Energy balance index under variant number of sensor nodes.

7.5. Impact of the Node Density

Since the network lifetime of these policies largely depends on the number of the subsinks and members in the network, we investigate the performance of these policies under different number of users. Figure 8 confirms the strong dependency with the density of networks. Obviously, the network lifetime increases with the increasing node density: more nodes join forward packet to mobile sink results in the less traffic load at the subsinks. However, when the number of sensors is significantly large, the network lifetime under these policies is almost the same.

Figure 8

Networks lifetime under variant sensor node.

7.6. Impact of the Velocity

We explore how these methods perform under various mobile sink speeds (Figure 9). The networks lifetime obviously decreases in rise of speed level. This trend can be explained as follows: the communication time between subsinks and sinks is decreased proportionally to the speed of the sink. Thereby, the higher the speed of the mobile sink, the higher the transmission rate required to transmit data at the subsinks. It results in reducing network lifetime.

Figure 9

Network lifetime under variant mobile sink speed.

However, in case of MMFA, the networks lifetime is less affected by the high speed since their assignment variables are kept updated as long as the connection time is feasible for selecting the subsinks. In Figure 9(a), the MMFA results in a slight decrement at the speed from 10 m/s to 20 m/s and is stable around 145 rounds. Similar result can be observed in Figure 9(b), where the network lifetime slightly decreases at the speed from 12 m/s to 20 m/s. Furthermore, MMFA outperforms others in high speed regime. Thus, it can cope with the high speed of the mobile sinks.

8. Conclusion

The mobile sink with constrained path has been widely considered in WSNs to improve the network lifetime. Due to the predetermined path, the connection time between sensor and the sinks is limited, which leads to the difference transmission rate of sensor. Thus, the energy consumption is not balanced among sensor nodes. To deal with this challenge, we proposed here to consider the transmission rate as the performance metric to improve network lifetime.

The results demonstrate the effectiveness of our algorithms: the network lifetime under our algorithm outperforms other benchmark algorithms. Besides, the algorithms can cope with the high speed of mobile sinks.

In the future, we plan to investigate experimentally the performance of such scenarios. We also aim at integrating controllable sinks and proposing a scheduling policy adapted to a collection of sinks with a predictable and controllable mobility.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This research was supported by the MSIP (Ministry of Science,ICT and Future Planning),Korea,under the Global IT Talent support program (R0618-15-1001) supervised by the IITP (Institute for Information and Communications Technology Promotion).

References

Borges

L. M.

Velez

F. J.

Lebres

A. S.

Survey on the characterization and classification of wireless sensor network applications

IEEE Communications Surveys and Tutorials 2014 16 4 1860 1890

10.1109/comst.2014.2320073

2-s2.0-84906859714

Zhao

ESWC: efficient scheduling for the mobile sink in wireless sensor networks with delay constraint

IEEE Transactions on Parallel and Distributed Systems 2013 24 7 1310 1320

10.1109/tpds.2012.210

2-s2.0-84878505783

Tunca

Isik

Donmez

M. Y.

Ersoy

Distributed mobile sink routing for wireless sensor networks: a survey

IEEE Communications Surveys and Tutorials 2014 16 2 877 897

10.1109/surv.2013.100113.00293

2-s2.0-84901199033

Liu

Jin

Cui

Chen

Deployment guidelines for achieving maximum lifetime and avoiding energy holes in sensor network

Information Sciences 2013 230 197 226

10.1016/j.ins.2012.12.037

2-s2.0-84874114967

Khan

M. I.

Gansterer

W. N.

Haring

Static vs. mobile sink: the influence of basic parameters on energy efficiency in wireless sensor networks

Computer Communications 2013 36 9 965 978

10.1016/j.comcom.2012.10.010

2-s2.0-84877694121

Salarian

Chin

K.-W.

Naghdy

An energy-efficient mobile-sink path selection strategy for wireless sensor networks

IEEE Transactions on Vehicular Technology 2014 63 5 2407 2419

10.1109/tvt.2013.2291811

2-s2.0-84902971132

Jeong

Y.-S.

Han

Y.-H.

Park

J. J.

Lee

MSNS: mobile sensor network simulator for area coverage and obstacle avoidance based on GML

Eurasip Journal on Wireless Communications and Networking 2012 2012, article 95

10.1186/1687-1499-2012-95

2-s2.0-84872858663

Konstantopoulos

Pantziou

Gavalas

Mpitziopoulos

Mamalis

A rendezvous-based approach enabling energy-efficient sensory data collection with mobile sinks

IEEE Transactions on Parallel and Distributed Systems 2012 23 5 809 817

10.1109/tpds.2011.237

2-s2.0-84859727925

Mamalis

B. G.

Prolonging network lifetime in wireless sensor networks with path-constrained mobile sink

International Journal of Advanced Computer Science & Applications 2014 5 10

10.14569/ijacsa.2014.051012

10.

Shi

Zhang

Mouftah

H. T.

DDRP: an efficient data-driven routing protocol for wireless sensor networks with mobile sinks

International Journal of Communication Systems 2013 26 10 1341 1355

10.1002/dac.2315

2-s2.0-84885618675

11.

Berry

Modiano

Zafer

Energy-efficient scheduling under delay constraints for wireless networks

Synthesis Lectures on Communication Networks 2012 5 2 1 96

12.

Nesamony

Vairamuthu

M. K.

Orlowska

M. E.

On optimal route of a calibrating mobile sink in a wireless sensor network

Proceedings of the 4th International Conference on Networked Sensing Systems (INSS '07)

June 2007

Braunschweig, Germany

IEEE

61 64

10.1109/inss.2007.4297389

2-s2.0-47149106841

13.

Yun

Xia

Behdani

Smith

J. C.

Distributed algorithm for lifetime maximization in a delay-tolerant wireless sensor network with a mobile sink

IEEE Transactions on Mobile Computing 2013 12 10 1920 1930

10.1109/TMC.2012.152

2-s2.0-84883149859

14.

Liang

Luo

Network lifetime maximization for time-sensitive data gathering in wireless sensor networks with a mobile sink

Wireless Communications and Mobile Computing 2013 13 14 1263 1280

10.1002/wcm.1179

2-s2.0-84884168644

15.

Vlajic

Stevanovic

Spanogiannopoulos

Strategies for improving performance of IEEE 802.15.4/ZigBee WSNs with path-constrained mobile sink(s)

Computer Communications 2011 34 6 743 757

10.1016/j.comcom.2010.09.012

2-s2.0-79952039741

16.

Song

Hatzinakos

Dense wireless sensor networks with mobile sinks

Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '05)

March 2005

Philadelphia, Pa, USA

IEEE

iii/677 iii/680

10.1109/ICASSP.2005.1415800

17.

Sharifkhani

Beaulieu

N. C.

A mobile-sink-based packet transmission scheduling algorithm for dense wireless sensor networks

IEEE Transactions on Vehicular Technology 2009 58 5 2509 2518

10.1109/tvt.2008.2010942

2-s2.0-66449103824

18.

Somasundara

A. A.

Kansal

Jea

D. D.

Estrin

Srivastava

M. B.

Controllably mobile infrastructure for low energy embedded networks

IEEE Transactions on Mobile Computing 2006 5 8 958 972

10.1109/TMC.2006.109

2-s2.0-33746336249

19.

Luo

Hubaux

J.-P.

Joint mobility and routing for lifetime elongation in wireless sensor networks

Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05)

March 2005

1735 1746

10.1109/INFCOM.2005.1498454

20.

Gao

Zhang

Song

Wang

Network lifetime and throughput maximization in wireless sensor networks with a path-constrained mobile sink

Proceedings of the International Conference on Communications and Mobile Computing (CMC '10)

April 2010

Shenzhen, China

IEEE

298 302

10.1109/cmc.2010.219

2-s2.0-77954008873

21.

H.-S.

Lee

Park

Kim

S.-H.

Virtual line-based data dissemination for mobile sink groups in wireless sensor networks

IEEE Communications Letters 2013 17 9 1864 1867

10.1109/LCOMM.2013.072913.131354

2-s2.0-84884815294

22.

Hamida

E. B.

Chelius

A line-based data dissemination protocol for wireless sensor networks with mobile sink

Proceedings of the IEEE International Conference on Communications (ICC '08)

May 2008

Beijing, China

2201 2205

10.1109/icc.2008.420

2-s2.0-51249087689

23.

Gao

Zhang

Das

S. K.

Efficient data collection in wireless sensor networks with path-constrained mobile sinks

IEEE Transactions on Mobile Computing 2011 10 4 592 608

10.1109/TMC.2010.193

2-s2.0-79951913744

24.

Waheed Khan

Abdullah

A. H.

Anisi

M. H.

Iqbal Bangash

A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks

Sensors 2014 14 2 2510 2548

10.3390/s140202510

2-s2.0-84893671245

25.

Berry

R. A.

Gallager

R. G.

Communication over fading channels with delay constraints

IEEE Transactions on Information Theory 2002 48 5 1135 1149

10.1109/18.995554

2-s2.0-0036566739

26.

Prabhakar

Uysal Biyikoglu

El Gamal

Energy-efficient transmission over a wireless link via lazy packet scheduling

Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '01)

April 2001

Anchorage, Alaska, USA

IEEE

386 394

10.1109/INFCOM.2001.916721

27.

Low

S. H.

Lapsley

D. E.

Optimization flow control. I: basic algorithm and convergence

IEEE/ACM Transactions on Networking 1999 7 6 861 874

10.1109/90.811451

2-s2.0-0033355765

28.

Aioffi

W. M.

Valle

C. A.

Mateus

G. R.

da Cunha

A. S.

Balancing message delivery latency and network lifetime through an integrated model for clustering and routing in wireless sensor networks

Computer Networks 2011 55 13 2803 2820

10.1016/j.comnet.2011.05.023

2-s2.0-79961022143

29.

Sierksma

Linear and Integer Programming: Theory and Practice 2001 2nd

CRC Press

30.

Boyd

S. P.

Vandenberghe

Convex Optimization 2004

Cambridge, UK

Cambridge University Press

10.1017/cbo9780511804441

31.

Lobel

Ozdaglar

Distributed subgradient methods for convex optimization over random networks

IEEE Transactions on Automatic Control 2011 56 6 1291 1306

10.1109/TAC.2010.2091295

2-s2.0-79958296696

32.

Kleinberg

Tardos

Algorithm Design 2006

Boston, Mass, USA

Pearson—Addison-Wesley

Network Lifetime Maximization in Wireless Sensor Networks with a Path-Constrained Mobile Sink

Abstract

1. Introduction

2. Related Works

2.1. Unconstrained Trajectory of Mobile Sink

2.2. Constrained Trajectory of Mobile Sink

3. Problem Statement

3.1. Network Model

3.2. Energy Model

Proposition 1.

Proof.

3.3. Problem Statement

4. Solution Approach via Lagrangian Method

4.1. Dualizing by Using Lagrangian Multiplier

Algorithm 1: Solution for subproblem S 1 .

4.2. Subgradient Projection Method

Algorithm 2: Distributed Fairness Assignment (DFA).

4.3. Convergence Analysis

Proposition 2.

Proof.

5. Subsink Collision Avoidance (SCA)

6. Data Gathering Scheme for Maximizing Network Lifetime

7. Performance Evaluation

7.1. Simulation Environment

7.1.1. Network Scenario

7.1.2. Mobility Model

7.1.3. Simulation Parameters

7.2. Convergence of MMFA

7.3. Optimality of MMFA

7.4. Impact of the Traffic Load

7.5. Impact of the Node Density

7.6. Impact of the Velocity

8. Conclusion

Footnotes

Conflict of Interests

Acknowledgment

References

Algorithm 1: Solution for subproblem $S_{1}$ .