Time-Independent Data Collection Protocol in Mobility-Assistant Wireless Sensor Networks with Duty Cycles

Abstract

Mobility-assistant sensor networks comprise mobile elements, and static sensors are established for the purpose of solving the serious problems such as overlapping or energy holes in wireless sensor networks (WSNs). In such systems, most of the energy is consumed when the radios are on, waiting for a mobile sink (MS) to arrive. Sleep/wake scheduling is an effective mechanism to prolong the lifetime of these energy-constrained wireless sensors. However, sleep/wake scheduling could result in substantial discovery delays because the sensor needs time to receive the beacon-ID signals when MS entered its communication range. In this paper, we first study on the MS discovery mechanism and the factors which affect the efficiency of data collection. Based on these results, we then provide a solution to the control problem of how to optimally adjust the system parameters of the sleep/wake scheduling protocol to maximize the network lifetime, subject to a constraint on the expected residual contact time. Our numerical results indicate that the proposed solution can balance the network consumption, especially in sparse sensor networks.

1. Introduction

Recently, wireless sensor networks (WSNs) are developed and used for information collection such as environmental monitoring [1, 2], automatic controlling [3, 4], and target tracking [5, 6]. In many data-centric applications, they often produce high-bandwidth sensor data that need to be collected under stringent delay constraints. There are multiple ways in which the sensor readings are transferred from the sensors to a central location. Usually, the readings are relayed to a stationary sink for processing using the ad-hoc multihop network formed by the sensor nodes. Though this is surely a feasible technique for data transfer, it creates a bottleneck in the network. This leads to a nonuniform depletion of network resources, and the nodes near the sink are the first to run out of batteries. If these nodes die, the network for all practical purposes will be disconnected. Periodically replacing the battery of the nodes for the large scale deployments is also infeasible.

In this paper, we exploit the mobility-assistant network to improve the data collection performance of WSNs. A mixture of networked mobile sink (MS) and static sensors reduces the cost but preserves the flexibility and advantageous capacities of a mobile system. In a hybrid sensor network, MS is generally equipped with more resources such as sensors, power, and computation, so forth. It can collect data from the sensor nodes and handle or merge the data directly. As a result, significant network energy saving can be achieved by reducing or completely avoiding numerous wireless communications and will prolong the lifetime of network.

The communication between the MS and sensor nodes takes place in two different phases. First, sensor nodes have to discover the presence of the MS in their communication range. Then, they can transfer collected data to the MS while satisfying certain reliability constraints, if required. Different from MS, sensor nodes have a limited energy budget, so that both discovery and data transfer should be energy efficient in order to prolong the network lifetime [3]. As the radio component is usually the major source of energy consumption, the overall activity of the radio should be minimized. To this end, a duty cycle approach can be used, so that sensors alternate sleep and active periods. However, the effects of the duty cycle have to be properly investigated: if sensor nodes are sleeping when the MS comes, they cannot detect it and transmit data, so that they are only wasting their energy.

In general, a low duty cycle provides better energy efficiency, it is also true if the contact time, which is the time when MS within the communication area of sensor, is large enough to allow the reliable transfer of a significant amount of data. However, when the contact time is limited, a very low duty cycle is not convenient as the energy saved during discovery is overcome by the decrease in the number of messages successfully transferred [7]. Hence, it is necessary to properly define the discovery parameters and the duty cycle to maximize the network lifetime.

The most efficient MS discovery method is the synchronous scheme which assumes the sensor nodes know exactly when the MS will enter the contact area and can thus wake-up at predefined times [8]. Obviously, such approaches require that the mobility of the MS is accurately known in advance. However, this assumption is rather strong, and the synchronization of MS and sensors is difficult to realize. In this paper, we develop an asynchronous and low-complexity solution to data gathering problem: a time-independent data collection protocol. We formulate the lifetime maximization problem: given a constraint on the expected residual contact time, how to maximize the network lifetime by controlling the wake-up rates but not concern the time when MS reached the sensors. We show how to use the solution to residual contact time maximization problem to construct an optimal solution to the lifetime-maximization problem for a specific definition of network lifetime.

The rest of the paper is organized as follows. Section 2 presents an overview of the relevant literature in the field. Section 3 introduces the system model and the related assumptions. Section 4 describes the MS discovery process in detail. In Section 5, we solve the lifetime-maximization problem using time-independent model. In Section 6, we provide simulation results that illustrate the performance of our proposed algorithm. Finally, Section 7 concludes the paper.

2. Related Works

Mobile nodes often used as data collectors are named as Data Mules or Data Ferries [4–6]. These nodes could be persons, cars, and animals, and so forth. In the GreenOrbs project [9], mobile user equipped communication device, like PDA, walks alone the trails to collect data from sensors which were deployed in Tianmu Mountain. Luo et al. [10] investigate the event collection problem in tough communication environment (e.g., underground coal mine) with the help of mobile sinks.

In order to reduce the transmission delay caused by slow-speed movement of MS, path selection problem are elaborately studied in these papers. In [11], authors studied path selection problem, assuming that each sensor buffers the sensing data and the data mule needs to collect it before the buffer overflows. Gandham et al. [12] used multiple mobile base stations to prolong the lifetime of the sensor networks. Xing et al. [13] presented path selection algorithms for rendezvous-based approach.

Synchronous schemas are used in some mobility-assistant discovery protocols. In [8], for instance, MEs are assumed to be on board of public transportation shuttles which visit sensor nodes according to a tight schedule. As an alternative, nodes can just define a networkwide active time and wake-up accordingly, so that they can contact the neighboring nodes which are available at that time. This kind of approach is adopted in ZebraNet [14], where nodes are synchronized through a Global Positioning System (GPS). Obviously, such approaches require strict synchronization or that the mobility of the nodes is accurate enough to obey schedules, and this limits the applicability of scheduled synchronous schemes to practical scenarios.

Asynchronous schemes define sleep/wake-up patterns such that nodes can communicate without explicitly agreeing on their activation instants [7, 15–17]. More specifically, the MS sends periodic discovery messages, while the static node cyclically wakes up and listens for advertisements for a short time. If it does not detect any discovery message, it can return to sleep; otherwise, it can start transferring data to the MS [18]. To ensure that the sensor can receive a discovery message independent of its sleep/wake-up schedule, the discovery parameters and the duty cycle have to be properly defined [19]. In both cases, it is analytically shown that using mobile elements leads to a network lifetime much longer than with a static sink. However, these papers only give the analysis of the mobility discovery and transfer protocol, they did not consider the network lifetime or other performance metric. Our approach also is an asynchronous scheme which does not concern when the MS enters the contact area, it can satisfy the transmission demand of application and maximize the network lifetime at the same time.

3. System Model

In this section, we will introduce the reference network scenario depicted in Figure 1, which is also used in [15, 16]. We consider a wireless sensor network with N nodes; let 𝒩 denote the set of all nodes in the network. One mobile sink moves along a linear path at a fixed vertical distance ( $D_y$ ) from a static node.

Figure 1

Reference scenario.

Data collection takes place only during a contact, that is, when the static node and the MS can reach each other. Furthermore, the area within the radio transmission range r of the static node is called contact area, while the overall time spent by the MS inside the contact area is called contact time and is referred to as $C_{\max \hspace{0.17em}}$ .

The overall data collection process can be split into three main phases. As MS arrivals are generally unpredictable, the static node initially performs a discovery phase for the timely detection of the MS. Indeed, the successful MS detection by the static sensor is not immediate but requires a certain amount of time, called discovery time, and denoted as d in Figure 1. Upon detecting the MS, the static node switches from the discovery state to the data transfer state and starts transmitting data to the MS. As a result of the discovery process, the static node cannot exploit the whole available contact time for data transfer. The portion of the contact time which can be actually used for subsequent data transfer is called residual contact time. After the end of the data transfer phase, the static node may switch to the discovery state again in order to detect the next MS passage.

To advertise its presence in the surrounding area, the MS periodically sends a beacon signal and an ID signal (carrying the receiver information) for time periods $t_B$ and $t_C$ , respectively, and then hears the medium for time period $t_A$ (see Figure 2). For ease of notation, we define the beacon period indicated by $t_I\triangleq t_C+t_B+t_A$ . If the MS does not hear any acknowledgment signal from the sensor i, it repeats this signaling procedure. When the sensor i wakes up and obtains the beacon signal, it keeps awake, waiting for the following ID signal to recognize the receiver. When node wakes up in the middle of an ID signal, it keeps awake, waiting for the next ID signal. If the sensor successfully recognizes itself the receiver of the MS, it then communicates with MS to receive the packet. In order to save energy during the discovery phase, the static node operates with a duty cycle, defined by the active time $t_{\mathrm{on}\hspace{0.17em}}$ and the sleep time $t_{\mathrm{off}\hspace{0.17em}}$ . Since nodes consume energy when awake, $t_{\mathrm{on}\hspace{0.17em}}$ should be as small as possible. However, if $t_{\mathrm{on}\hspace{0.17em}}$ is too small, a node that wakes up right after an ID signal could return to sleep before the following beacon signal. In order to avoid this case, we set $t_{\mathrm{on}\hspace{0.17em}}=t_A+{ϵ}_{\text{detect}}$ , where ${ϵ}_{\text{detect}}$ is a small amount of time required for a node to detect signal in the wireless medium. In the rest of the paper, we assume that ${ϵ}_{\text{detect}}$ is negligible compared to $t_A$ .

Figure 2

MS discovery model.

We make the following assumptions in this paper:

• (1)

the communication range of sensor node is a circular area with radius of r and the speed of MS is a constant of v;

(2)

the MS is power of energy and computing ability and with a large storage;

(3)

an arbitrary moving path is deterministic which connected all sensors that would transmit data to MS, and whole data of one sensor must transfer to MS in one contact;

(4)

to simplify the computation, we assume the moving path is linear, and the movement distance in one contact area is $2r$ , that is, $D_y=0$ and $C_{\max \hspace{0.17em}}=2r/v$ ;

(5)

the time instants that a node i wakes up follow a Poisson random process with rate ${\lambda }_i$ and the wake-up processes of different nodes are independent.

4. Analysis of MS Discovery Process

Although MS discovery by sensors with sleep/wake-up patterns is an asynchronous schema whose properties ensure that sensors are able to communicate without explicitly agreeing on their activation instants, the residual contact time is decided by the time MS enters the contact area. The residual contact time will be a maximum if the node's state is ON at that time, otherwise it will be shorten. On the other hand, the residual contact time is not a deterministic value for the MS moving alone different paths and the contact will be occurred at different time.

In detail, the time instant at which the MS transmits the first beacon-ID signal while in the contact area is denoted as $t_0$ . As beacon transmissions are periodic and start at t₀, the actual instants of subsequent beacon transmissions can be expressed as $t_n=t_0+n*t_I$ , with $n\in [1,N-1]$ , where $N=\lceil C_{\max \hspace{0.17em}}/t_I\rceil$ is the maximum number of beacon-ID signals the MS can send while in the contact area. Therefore, if the MS is discovered by means of the mth beacon, the discovery time is $d=d_0+m*t_I$ , and the corresponding residual contact time is $C_{\max \hspace{0.17em}}-d$ .

As shown in [15], the state of the static node at a given instant can be specified by its composite state $(s,l)$ where s denotes the radio state, that is, ON or OFF, and l represents the residual time, that is, the amount of time the node will remain the same state s. The initial state of the static node at the time $t=0$ is referred to as $(s_0,l_0)$ as shown in Figure 3. Let us denote by $s(t)$ and $l(t)$ the radio state and the residual time, respectively, at a generic time t. Because of the duty cycle, both $s(t)$ and $l(t)$ evolve in a deterministic way. In detail, the radio state of the static node is periodic, with period equal $t_{\text{ON}}+t_{\text{OFF}}$ . We focus now on the radio state $s(t_n)$ of the static node at the time MS enters the contact area. As $s(t)$ is periodic, it is sufficient to investigate the remainder of the ratio between the beacon-ID transmission times and the period of the duty cycle. By comparing this remainder against the initial residual state $s_0$ and the initial residual time $l_0$ , we can derive $s(t_n)$ . The number of the state changing from ON to OFF (or OFF to ON) is $\lfloor t_n/(t_{ON}+t_{\text{OFF}})\rfloor$ , and the remaining time is $\mathrm{\Delta }t=t_n\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{mod}\hspace{0.17em}(t_{ON}+t_{\text{OFF}})$ , the state of sensor is

$\begin{array}{cc}\hfill & {s\left(t_n\right)}_{s_0=\text{ON}}\hfill \\ \hfill & \hspace{1em}=\{\begin{array}{cc}\text{ON},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}0\le \Delta t<l_0,\hfill \\ \text{OFF},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{l}_0\le \Delta t<l_0+t_{\text{OFF}},\hfill \\ \text{ON},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{l}_0+t_{\text{OFF}}\le \Delta t<t_{\text{ON}}+t_{\text{OFF}},\hfill \end{array}\hfill \\ \hfill & {s\left(t_n\right)}_{s_0=\text{OFF}}\hfill \\ \hfill & \hspace{1em}=\{\begin{array}{cc}\text{OFF},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}0\le \Delta t<l_0,\hfill \\ \text{ON},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{l}_0\le \Delta t<l_0+t_{\text{ON}},\hfill \\ \text{OFF},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{l}_0+t_{\text{ON}}<\Delta t<t_{\text{ON}}+t_{\text{OFF}}.\hfill \end{array}\hfill \end{array}$

(1)

Figure 3

State changing of sensors.

Similarly, we can also derive the residual time $l(t_n)$ :

$\begin{array}{cc}\hfill & {l\left(t_n\right)}_{s_0=\text{ON}}\hfill \\ \hfill & \hspace{1em}=\{\begin{array}{cc}{l}_0-\Delta t,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}0\le \Delta t<l_0,\hfill \\ t_{\text{OFF}}+l_0-\Delta t,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{l}_0\le \Delta t<l_0+t_{\text{OFF}},\hfill \\ t_{\text{ON}}+t_{\text{OFF}}+l_0-\Delta t,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{l}_0+t_{\text{OFF}}\le \Delta t<t_{\text{ON}}+t_{\text{OFF}},\hfill \end{array}\hfill \\ \hfill & {l\left(t_n\right)}_{s_0=\text{OFF}}\hfill \\ \hfill & \hspace{1em}=\{\begin{array}{cc}{r}_0-\Delta t,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}0\le \Delta t<l_0,\hfill \\ t_{\text{ON}}+l_0-\Delta t,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{l}_0\le \Delta t<l_0+t_{\text{ON}},\hfill \\ t_{\text{ON}}+t_{\text{OFF}}+l_0-\Delta t,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{l}_0+t_{\text{ON}}\le \Delta t<t_{\text{ON}}+t_{\text{OFF}}.\hfill \end{array}\hfill \end{array}$

(2)

5. Time-independent Data Collection Protocol

5.1. Wake-Up Rates and Awake Probability

In this section, we present the time-independent data collection protocol to maximize the network lifetime. As we assumed, the sleep/wake schedule is determined by the wake-up rate ${\lambda }_i$ of the Poisson process with which each node i wakes up. Obviously, if ${\lambda }_i$ increases, the expected discovery delay will be reduced and the data communication time between MS and sensor will be extended. However, a larger wake-up rate leads to higher energy consumption and reduces network lifetime.

In the rest of the paper, it is more convenient to work with the notion of awake probability which is a function of ${\lambda }_i$ . Suppose that MS sends the first beacon signal at the initial time, as in Figure 2. If the sensor has not heard the first $(m-1)$ beacon and ID signals, then node transmits the mth beacon and ID signal in the time interval $[(t_C+t_B+t_A)(m-1),(t_C+t_B+t_A)(m-1)+t_C+t_B]$ . For the node i to hear the mth signals and to recognize the sender, it should wake-up during $[(t_C+t_B+t_A)(m-1)-t_C-t_A,(t_B+t_A)m-t_C-t_A]$ . Therefore, provided that MS is sending the mth signal, the probability that node i wakes up and hears this signal is

$p_i=1-e^{-{\lambda }_i\left(t_C+t_B+t_A\right)}.$

(3)

We call $p_i$ the awake probability of sensor i.

Note that there is a one-to-one mapping between the awake probability $p_i$ and the wake-up frequency ${\lambda }_i$ . Hence, the awake probability is also closely related to both delay and energy consumption. Let $\vec{p}=(p_i,i\in 𝒩)$ represent the global awake probability vector.

5.2. Performance Metrics

In this subsection, we define the performance metrics of the time-independent policy and the sleep/wake scheduling policy that we intend to optimize. We know, although the sleep-wake patterns and the data collection policy are applied in the operation phase of the network, their control parameters are optimized in the configuration phase.

5.2.1. Residual Contact Time

As mentioned above, the residual contact time is used for data communication after the MS has been discovered by sensor node. Upon receiving a beacon-ID from the MS, the static node enters the data transfer state. While, in this state, the static node remains always active to exploit the residual contact time as much as possible. On the other hand, the MS enters the data transfer phase as soon as it receives the first message sent by the static node, and stops beacon transmissions. Hence, the amount of data exchanged between MS and sensor is decided by the residual contact time, it must be maximized to transfer large mount of data. The maximum value of the residual contact time is $2r/v$ if the state of sensor is ON when MS enters the contact area, and the minimum value is 0 if the state is OFF before MS leaves the contact area.

For the definition of the residual contact time $c=C_{\max \hspace{0.17em}}-d$ , it is affected by the discovery time which is determined by the awake probability of the sensor node. We denote $C_i(p_i,v,r)$ as the expected residual contact time when the awake probability vector $p_i$ , the speed of MS, and the communication radius of sensor i are given.

Our objective is to maximize the residual contact time to satisfy the data transfer demand:

$\max C_i\left(p_i,v,r\right)\ge {\xi }_i,$

(4)

where ${\xi }_i$ is the minimum time to satisfy the data transfer demand. This problem is to find optimal sleep/wake scheduling policy to maximize the sensor's residual contact time.

5.2.2. Network Lifetime

We now introduce metric, the network lifetime, and the corresponding lifetime maximization problem (subject to residual contact time constraints). Let $Q_j$ denote the energy available to node j. We assume that node j consumes ${\mu }_j$ units of energy each time it wakes up. We define the expected lifetime of node j as $Q_j/{\mu }_j{\lambda }_j$ . Note that implicitly in this definition of lifetime we have chosen not to account for the energy consumption by data transmission. As mentioned in the introductory section, this is a reasonable approximation for event-driven sensor networks in which events occur very rarely because the energy consumption of the sensor nodes is dominated by the energy consumed during the sleep/wake scheduling.

By introducing the power consumption ratio $e_j={\mu }_j/Q_j$ , we can express the lifetime of node j as

$T_j\left(p_j\right)=\frac{1}{e_j{\lambda }_j}=\frac{t_C+t_B+t_A}{e_j\ln \left(1/\left(1-p_j\right)\right)}.$

(5)

Here, we have used the definition of the awake probability $p_j=1-e^{-{\lambda }_j(t_C+t_B+t_A)}$ from (3).

We define network lifetime as the shortest lifetime of all nodes. In other words, the network lifetime for a given awake probability vector $\vec{p}=(p_i,i\in 𝒩)$ is given by

$T\left(\vec{p}\right)=\underset{i\in \mathcal{N}}{\min }{T}_i\left(p\right),$

(6)

Based on the above performance metrics, we present the lifetime maximization problem as follows:

$\begin{array}{cc}\hfill \underset{\vec{p}}{\max }\hspace{0.17em}& T\left(\vec{p}\right)\hfill \\ \hfill \text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\hspace{0.17em}& C_i\left(p_i,v,r\right)\ge {\xi }_i,\hspace{1em}\forall i\in \mathcal{N},\hfill \\ \hfill & \vec{p}\in {\left(\mathrm{0,1}\right]}^N.\hfill \end{array}$

(P)

The objective of the above problem is to choose the optimal sleep/wake scheduling policies that maximize the network lifetime and also guarantee that the residual contact time of each node is not less than the minimum allowable data transfer time of this node.

5.3. Data Collection Protocol

We first derive the relationship between the expected residual contact time and awake probability.

Proposition 1.

For any sensor $i\in 𝒩$ , if the MS enters its contact area with a constant speed v, the expected residual contact time for a given awake probability vector $p_i$ is

$C_i\left(p_i,v,r\right)=\frac{2r}{v}-t_I\times \frac{{1-\left(1-p_i\right)}^{2r/v*t_I}}{p_i}.$

(7)

Proof.

The MS sends beacon-ID signals when it is within sensor's contact area. We define the probability $p_i,h$ , which denotes sensor i that received the hth beacon-ID signals is equal to the probability that i has not woke up for the past $h-1$ beacon-ID signaling iterations and it wakes up at hth beacon-ID signals, that is,

$p_{i,h}={\left(1-p_i\right)}^{h-1}\times p_i.$

(8)

We define the number of beacon-ID signals during the time MS within the contact area $n=2r/(v\times t_I)$ , so

$\begin{array}{cc}\hfill C_i\left(p_i,v,r\right)& ={\displaystyle \sum }_{h=1}^n{p}_{i,h}\times \left(\frac{2r}{v}-h\times t_I\right)\hfill \\ \hfill & ={\displaystyle \sum }_{h=1}^n{\left(1-p_i\right)}^{h-1}\times p_i\times \left(\frac{2r}{v}-h\times t_I\right)\hfill \\ \hfill & =p_i*\frac{2r}{v}*{\displaystyle \sum }_{h=1}^n{\left(1-p_i\right)}^{i-1}-p_i*\frac{2r}{v*n}\hfill \\ \hfill & \hspace{1em}*{\displaystyle \sum }_{h=1}^n{\left(1-p_i\right)}^{i-1}*i\hfill \\ \hfill & =p_i*\frac{2r}{v}*\frac{{1-\left(1-p_i\right)}^n}{p_i}-p_i\hfill \\ \hfill & \hspace{1em}*\frac{2r}{v*n}*\left(\frac{1-{\left(1-p_i\right)}^n}{p_i^2}-\frac{n*{\left(1-p_i\right)}^n}{p_i}\right)\hfill \\ \hfill & =\frac{2r}{v}-\frac{2r}{v*n}*\frac{1-{\left(1-p_i\right)}^n}{p_i}.\hfill \end{array}$

(9)

Hence, we can get the result when substituting n with $2r/(v\times t_I)$ .

From (5), the lifetime $T_i$ and the awake probability $p_i$ have a one-to-one mapping. Hence, we convert Problem (P) to the following equivalent problem that controls $\vec{T}=(T_1,T_2,\dots ,T_N)$ ,

$\begin{array}{cc}\hfill \max \underset{i\in \mathcal{N}}{\min }\hspace{0.17em}& T_i,\hfill \\ \hfill \text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\hspace{0.17em}& C_i\left(p_i,v,r\right)\ge {\xi }_i,\hspace{1em}\forall i\in \mathcal{N},\hfill \end{array}$

(P1)

$p_i=1-e^{-t_I/e^i{T}_i},\hspace{1em}\forall i\in \mathcal{N}.$

(10)

Proposition 2.

If ${\vec{T}}_{}^{*}=(T_1^{*},T_2^{*},\dots ,T_N^{*})$ is an optimal solution to Problem (P1), then so is $\vec{T}$ such that $\vec{T}=(T_i={\min \hspace{0.17em}}_k\hspace{0.17em}{T}_k^{*},i\in 𝒩)$ . In other words, according to the lifetime definition (6), it is no worse in terms of both the network lifetime and the residual contact time to let all nodes set their lifetime to the shortest lifetime.

Proof.

Since both solutions have the same objective value under our network lifetime definition in (6), it is sufficient to show that if ${\vec{T}}^{*}$ is in the feasible set, so is $\vec{T}$ . Let ${\vec{p}}^{*}$ and $\vec{p}$ be the awake probability vectors that correspond to ${\vec{T}}^{*}$ and $\vec{T}$ , respectively, by (10). Since $p_i$ monotonically decreases as $T_i$ increases, and $\vec{T}⪯{\vec{T}}^{*}$ , we have ${\vec{p}}^{*}⪯\vec{p}$ . (The symbol “⪯” denotes componentwise inequality, i.e., if $\vec{T}⪯{\vec{T}}^{*}$ , then $\vec{T}\le {\vec{T}}^{*}$ for all $i\in 𝒩$ .)

We prove the residual contact time from any node i is a nondecreasing function with respect to each component of $p_i$ . (The detailed proof is provided in the appendix). For a given $p_i$ , assume that node increases its awake probability to $p_i^{\prime }$ . Since the increased awake probability does not decrease the residual time of the node, we have

$C_i\left(p_i,v,r\right)\le C_i\left(p_i^{\prime },v,r\right).$

(11)

The inequality in (11) is due to the residual time optimality of for $p_i$ . Hence, the delay is nondecreasing with respect to each component of $\vec{p}$ . Since ${\vec{p}}^{*}⪯\vec{p}$ , we have $C_i(\vec{p},v,r)\ge C_i({\vec{p}}^{*},v,r)$ . Hence, if ${\vec{T}}^{*}$ satisfies problem (P1), so does $\vec{T}$ .

Using the above proposition, we can rewrite problem (P1) into the following problem with one-dimensional variable that corresponds to the network lifetime:

$\begin{array}{cc}\hfill \max \hspace{0.17em}& T,\hfill \\ \hfill \text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\hspace{0.17em}& C_i\left(p_i,v,r\right)\ge {\xi }^{*},\hspace{1em}\forall i\in \mathcal{N},\hfill \\ \hfill \underset{i\in \mathcal{N}}{\min }& p_i=1-e^{-t_I/e^{i}T},\hspace{1em}\forall i\in \mathcal{N},\hfill \end{array}$

(P2)

where ${\xi }^{*}=\max \hspace{0.17em}\hspace{0.17em}{\xi }_i$ , $i\in 𝒩$ .

Note that ${\min \hspace{0.17em}}_{i\in 𝒩}\hspace{0.17em}{C}_i(p_i,v,r)$ is nondecreasing with respect to each component of $p_i$ . (See the proof of Proposition 2). Since each component $p_i$ of is a decreasing function of $T,{\min \hspace{0.17em}}_{i\in 𝒩}\hspace{0.17em}{C}_i(p_i,v,r)$ is decreasing as increases T. Hence, we can develop an efficient binary search algorithm (see Algorithm 1 that follows) for computing the optimal value $T^{*}$ of such that ${\min \hspace{0.17em}}_{i\in 𝒩}\hspace{0.17em}{C}_i(p_i,v,r)={\xi }^{*}$ .

Algorithm 1

1: Initial Setup: The sink sets $T^{(1)}$ to a half of the maximum possible lifetime and sets $T_{\text{record}}\leftarrow 0$

2: for   $m=1$ to $m_{\max \hspace{0.17em}}$ do

3: Every node i computes $p_i^{(m)}=1-e^{-(t_I/(T^{(m)}{e}_i))}$ .

4: Node   $i$ sends their feedback of their transmission time $C_i$ to the sink.

5: The sink sets $C_{\min \hspace{0.17em}}\leftarrow {\min \hspace{0.17em}}_i\hspace{0.17em}{C}_i$   and

6: if $C_{\min \hspace{0.17em}}<{\xi }^{*}$ then

7:  $T^{(m+1)}\leftarrow T^{(m)}-(T^{(1)}/2^m)$ .

8: else

9:   $T^{(m+1)}\leftarrow T^{(m)}-(T^{(1)}/2^m)$ and $T_{\text{record}}\leftarrow T^{(m)}$ .

10:  end if

11: end for

12: return $T^{*}\leftarrow T_{\text{record}}$

After $m_{\max \hspace{0.17em}}$ iterations of the Binary Search Algorithm, the difference between the optimal lifetime $T^{*}$ and the algorithm output $T_{\text{record}}$ is smaller than $(T^{(1)}/2^{m_{\max \hspace{0.17em}}})$ . If we want to make this difference less than ε, the complexity of the Binary Search Algorithm is $O(\log \hspace{0.17em}\hspace{0.17em}(1/\epsilon )·N)$ .

6. Simulations and Experiments

In order to evaluate the performance of MS discovery and our time-independent data collection protocol, we test the contact time and network lifetime with NS2 simulator and physical experiments, respectively.

6.1. Residual Contact Ratio

In this section, we will use the analytical formulas derived in the previous sections to perform an analysis of the MS discovery process. To this end, we will consider the following performance metrics of residual contact ratio, which is defined as the average of the ratio between the residual contact time and the whole contact time:

$\eta =\mathbb{E}\left[\frac{C_i\left(p_i,v,r\right)}{c_{\max }}\right].$

(12)

In all simulations we performed 10 replicas, each consisting of 1000 passages. The obtained confidence intervals are always very low (below 1%) and are thus omitted. In the following, we will show both analytical and simulation results. However, unless stated otherwise, we will refer to the analytical results.

And the simulations are written in C++. The radio parameters are set according to the data sheet of the CC2420 radio on Mica2 motes [20]. Radio bandwidth is 40 Kbps, and transmission power is 4 dbm with the current consumption of 11.6 mA. The size of each packet is 30 bytes. To simulate the highly unreliable links of WSNs, we implemented a link layer model from USC [21]. Experimental data shows that the USC model can capture the highly probabilistic link characterization of Mica2 motes [21].

From formula (7), the effectiveness of the discovery strictly depends on the beacon period $t_I$ , the moving speed v and the awake probability of the sensor. Here, the parameter $t_I$ must be larger than or equal to the beacon duration $t_B$ (10 ms in our scenario). In addition, the discovery process is clearly influenced by these parameters.

Figures 4 and 5 show the residual contact ratio for three different beacon periods and several wake-up rates (mapping to awake probability), when the MS moves at 1 m/s and 8 m/s, respectively. To validate our analytical model we also performed some simulation experiments under the same conditions. The comparison between simulation and analytical results shows that our model is very accurate.

Figure 4

Residual contact ratio as a function of the beacon period for v =1 m/s.

Figure 5

Residual contact ratio as a function of the beacon period for v =8 m/s.

The results in Figure 4 show that the static node quickly discovers the MS when it moves slowly (i.e., at 1 m/s). As expected, for a fixed wake-up rate, the residual contact ratio decreases when $t_I$ increases. However, for a given beacon period, the residual contact ratio increases with the wake-up rate. In this scenario, most of the contact time can be effectively used for communication even when the wake-up rate is very low. The results are different, instead, when the speed of the MS is high (i.e., 8 m/s). From Figure 5, we can see that the residual contact ratio drops sharply when the wake-up interval $(1/\lambda )$ is from 10 to 10⁻¹, especially for large values of $t_I$ . Intuitively, this behavior can be explained as follows. For the same beacon period, a lower wake-up rate involves longer delays in the detection of the MS. When the MS moves fast, the time it remains in the contact area is lower (in this scenario the average contact time is about 20 s): hence, a late discovery results in a small amount of time left for data transfer.

6.2. Network Lifetime

We start our physical experiments by collecting data using the setup shown in Figure 6 where we placed an 11 × 11 grid on a 15 m × 15 m indoor environment. The sensor motes are also TelosB which uses the CC2420 chip. They are IEEE 802.15.4 compliant. We deployed 20 static motes in the random grids and each grid with one sensor. The control program on the TelosB motes was written in the nesC language then compiled and programmed onto the mote using TinyOS 2.x. The static sensors are randomly awake and sense the temperature.

Figure 6

(a) Experimental setup to collect data from the static sensor nodes with a mobile sink node moving on a uniform grid. (b) The mobile sink node named DataTruck designed by ourselves.

We use the DataTruck [22] as the mobile sink to download data from static sensors. DataTruck is a new sensor node platform designed to support mobility experiments in sensor networks. Although our design is driven by the research requirements of our group, extra effort was taken during the design phase to specify a feature set that is complimentary to existing platforms and can serve multiple aspects of research and education in sensor networks.

While DataTruck enters the contact area, it will send beacon-ID signals to static nodes and set CC2430 in receiving mode. Address resolution will be done while DataTruck receives sensing data correctly; otherwise, it sends a retransmission signal. When the DesNo in the received package is matched with the current DataTruck address, the package will be handled in the local node else it will be drop.

At first, we concern the discovery ratio while using different schemas. Discovery ratio is defined as the average of the ratio between the number of contacts correctly detected by the static sensor and the total number of contacts. We compare the performance of our protocol with other approaches: DIRL [17] and SORA [23], which are two heuristic-based reinforcement learning schemas. From Figure 7, we can see that when the mobility is low, almost all contacts are detected, independent from the adopted schemes, here we denoted our protocol as TIER. The situation is different, however, when the speed is high (i.e., 2 m/s). In this case there is a slight improvement of TIER over other schemas, since it obtains a discovery ratio always over 95%. The reason of this result is our protocol that will adjust the awake probability to satisfy the transmission demand in every round.

Figure 7

The discovery ratio of different schmas.

In Figure 8, we compare the network lifetime under the different value of speed, where x-axis represents different maximum residual contact time ${\xi }^{*}$ in our original Problem (P) and y-axis represents the maximum lifetime for each ${\xi }^{*}$ . Here, the communication radius is 100 m, and the maximum value of speed is 2 m/s, so the maximum residual contact time is 100 s. The beacon period $t_I$ is 10 ms.

Figure 8

The network lifetime subject to different residual contact time ${\xi }^{*}$ .

From Figure 8, we observe the network lifetime is reduced when increasing the speed of MS with the same residual contact time requests. This is because the time MS stay in the contact area is short if the MS has a large speed. Moreover, large speed may delay the MS detection, leading to lower residual contact times. In addition, they may also produce high contact miss ratios, so that the energy spent during discovery is simply wasted, as the sensor node cannot transmit any data.

7. Conclusion

In this paper, we develop a time-independent data collection scheme to reduce the MS discovery delay and to prolong the lifetime of wireless sensor networks employing asynchronous sleep/wake scheduling. Specifically, we study two optimization problems. First, when the wake-up rates of the sensor nodes are given, we develop an efficient and distributed algorithm to maximize the residual contact time for satisfying the data collection task. Second, using a specific definition of the network lifetime, we study the lifetime-maximization problem to optimally control the sleep/wake scheduling policy and discovery policy in order to maximize the network lifetime subject to a lower limit on the expected residual contact time. Our numerical results indicate that the proposed solution can balance the network consumption, especially in a sparse sensor networks. For future work, we plan to generalize our solution to take into account non-Poisson wake-up processes and other lifetime definitions.