Sage Journals: Discover world-class research

Abstract

In many surveillance sensor networks, sensors are scheduled to work in a duty-cycled mode (i.e., periodically switching between active states and sleeping states) in order to prolong the network lifetime. The duty-cycled mode saves sensors' energy but brings other issues. In surveillance applications (e.g., forest fire alarm or intruder detection), it is desired to report detected events to the sink node as soon as possible. However, the duty-cycled mode may increase the data delivery latency. In this paper, we study minimum-delay routing in duty-cycled surveillance sensor networks. As the minimum-delay routes are time dependent (i.e., they change with time) in duty-cycled sensor networks, routing becomes a challenging task. We propose a distributed routing algorithm to find the minimum-delay routes at any time from all nodes to the sink node. Further, all minimum-delay routes can be found in one execution of our routing algorithm. We further provide a distributed route maintenance algorithm for finding the minimum-delay routes when the network dynamically changes. We theoretically prove the correctness of the proposed algorithm, and extensive simulation results show that the performance of our algorithm outperforms other existing algorithms.

1. Introduction

Wireless sensor networks (WSNs) have been used in many surveillance applications such as traffic monitoring, forest fire detection, and target tracking. Typically, in surveillance system, sensors (or nodes) detect events and then report the events to the base station (or the sink node). To build long-term operating surveillance systems, sensors are expected to work for months or even years, but they only have limited battery energy. For example, the battery of a sensor can only last for a few days if running continuously. One viable technique is to schedule sensors switching between active mode and sleeping mode, while active sensors perform surveillance tasks. Energy-efficient scheduling algorithms [1–7] are proposed in the literature to prolong network lifetime, as well as to guarantee event detection. In these algorithms, sensors are scheduled to be active for a period of time and then to sleep for another period of time, which forms a duty-cycled WSN.

As pointed out by [8], the effectiveness of a surveillance system lies in two aspects: accurately detecting events and timely reporting the events. The second aspect is highly related to routing problem. Routing in WSNs has been extensively studied and many routing algorithms or protocols are proposed. The research on routing evolves from early flooding-based protocols to location-based routing protocols (with the help of localization methods [9, 10]) and to state-of-the-art gradient-based routing protocols [11]. Collection tree protocol (CTP) [12] and routing protocol for low-power and lossy networks (RPL) [13] are two well-known gradient-based routing protocols. CTP uses expected transmissions (ETX) as the gradient that indicates the expected number of transmissions needed for the packet to reach the sink node. Therefore, the major objective of CTP is to reduce energy consumption. RPL provides a framework in which multiple gradient metrics (e.g., energy and latency) can be combined to meet different application requirements. However, RPL does not provide solution for minimizing the packet delivery latency for the duty-cycled sensor networks.

In this paper, we focus on minimum-delay routing in duty-cycled surveillance sensor networks. In many surveillance applications (e.g., forest fire alarm or intruder detection), it is desired to report detected events to the sink node as soon as possible. Recently, several routing algorithms [14–17] have been proposed in the literature to minimize the packet delivery latency. The work in [15] studies minimum-delay routing problem for the network where each node works in low-duty-cycled and asynchronous modes; that is, each node works only one slot in a cycle, and it can independently select its working slots and cycle length. This network model, however, is not suited for surveillance systems as sensors have to cooperate to fulfil the surveillance tasks, and thus, they should work according to some scheduling algorithms. The most related work to ours is [16], which aims to find minimum-delay routes for a pair of nodes in a sensor-target surveillance system. The proposed algorithm, called optimal-PML, starts route discovery procedure by flooding route requests in the whole network. Although this method is valid in highly dynamic networks, it suffers from huge message cost as well as time cost (see Section 7).

The duty-cycled mode saves sensors' energy and prolongs network lifetime but also brings other issues. First, the duty-cycled mode may increase the data delivery latency because a node may have to wait for its next-hop node to wake up and receive its packets. Second, both the packet delivery latency and the next-hop node vary with time; that is, they are time dependent. We give a simple example to illustrate these facts.

Figure 1(a) shows the topology of a simple WSN, and Figure 1(b) gives the active or working period of each sensor determined by a given scheduling algorithm. The network lifetime is divided into cycles, and each cycle consists of 10 slots. Suppose that node B detects an event and wants to send a packet to sink node at the starting time of slot 8. It can send the packet to node D at slot 8 since node D is working at that time, and then, node D can forward the packet to node F at slot 9. Finally, the packet is sent to the sink node by node F at slot 10. The packet delivery latency is 3 slots as each transmission costs one slot. Now, consider that node B fails to transmit the packet at slot 8 and retransmits it at slot 9. At that time, node D goes to sleep and it will wake up at slot 5 in the next cycle, which means that node B has to wait 6 slots. Assume that node B wakes up and sends the packet to node D at slot 5 in the next cycle. When node D receives the packet, it also has to wait one slot (i.e., at slot 6), and then, sends the packet to node F at slot 7. The sink node will receive the packet from node F at slot 8, and the packet delivery latency is 10 slots. Figure 2 shows the minimum delay vectors from each node to the sink. It can be seen that the minimum packet delivery latency varies with time, and finding the minimum-delay routes for all nodes at any time becomes a challenging task in duty-cycled WSNs.

Figure 1

An example of a duty-cycled WSN: (a) network topology; (b) working slots of nodes in a cycle.

Figure 2

The minimum delays and next hops for the nodes in the duty-cycled network shown in Figure 1.

In this paper, we propose a distributed routing algorithm to find the minimum-delay routes at any time from all nodes to the sink node. Similar to the well-known Bellman-Ford algorithm, each node updates its routing table according to the routing information of its neighbors, and the routing table eventually converges to the optimal values including the minimum delay and corresponding next hop at any time. In addition, route discovery procedure is implemented in asynchronous mode, and all minimum-delay routes can be found in one execution of our routing algorithm. We further provide a distributed route maintenance algorithm for finding the minimum-delay routes when the network dynamically changes. We theoretically prove the correctness of the proposed algorithm and show that the execution of our algorithm will terminate in finite time, and at the end of execution, all routing tables converge to the optimal values. Extensive simulation results show that the performance of our algorithm outperforms other existing algorithms.

It is worth noting that in other research fields such as robotics fields, routing problem is also studied in [18], and in automatic control field, some problems other than routing are studied in [19, 20] when the network changes dynamically.

The rest of the paper is organized as follows. In the next section, we discuss related work. Section 3 gives the network model and problem formulation. Sections 4 and 5 present our routing algorithm and route maintenance algorithm, respectively. Some problems are discussed in Section 6. Performance evaluation is provided in Section 7, followed by conclusions in Section 8.

2. Related Work

To prolong network lifetime, sensors switch between active and sleeping modes, which forms a duty-cycled WSN. Recently, duty-cycled WSNs have attracted a lot of attention. The research efforts are on data collection [21], data forwarding [22], load balancing [23], and routing [14–17, 24]. In this section, we focus on routing problem and some related research efforts.

The work in [14] studies delivering data with a guaranteed communication delay bound, which is important for many surveillance applications. To achieve this goal, methods are devised from the temporal (time) and spatial (space) perspectives. Specifically, the temporal scheme decreases the communication delay by adding more working slots to sensors, and the spatial scheme addresses this issue by adding a minimum number of sinks. Hybrid spatiotemporal scheme is also presented to achieve balance between cost and energy efficiency. In this paper, we are also concerned about delivering data to the sink as soon as possible, but we consider a different problem: given a duty-cycled network which is determined by a surveillance scheduling algorithm, how to find the minimum-delay routes from each node to the sink at any time?

The minimum latency routing problem is studied in [15]. It is assumed that sensors work in low power listening (LPL) mode: each sensor periodically wakes up to listen to the wireless channel, checking whether a sensor wants to send packets to it. Further, the checking intervals of nodes can be different. A distributed routing algorithm is proposed to find the minimum latency routes from all nodes to the sink node. Note that LPL mode may not be suitable for surveillance sensor networks because it does not take surveillance task into account. Moreover, in [15], minimum latency routes from a node to the sink are found only for the time points when it wakes up. In other words, the minimum-delay route is undetermined if a node wants to send a packet at a time between two consecutive wake-up time points (e.g., retransmitting a packet or having more packets to be sent in the buffer). Since the checking interval may be long (e.g., 500 ms or 1000 ms), the packet delivery latency may increase a lot because the minimum latency route is time dependent.

The work in [16] investigates routing in intermittently connected sensor networks. It is assumed that each sensor has a working period and a sleeping period in a cycle according to application-driven scheduling schemes (e.g., target coverage scheduling). We adopt the same network model used in [16]. To find a minimum latency route from the source to the destination for a given time, a route request (RREQ) is sent by the source, and the nodes who receive the RREQ forward the RREQ to its neighbors. The first RREQ arriving at the destination will be acknowledged by the destination, and the path the RREQ goes through will be taken as the minimum latency route. Based on this route discovery process, two proactive algorithms are proposed, where one attempts to minimize the call number of route discovery process, and the other tries to reduce the time cost for finding minimum latency route. It can be seen that the route discovery process is like a flooding in the network. Moreover, the minimum latency routes found by it is only optimal for a specific time point. Since the minimum latency route from the source to the destination is time dependent, the route discovery process has to be invoked multiple times. Unlike [16], we target at developing a distributed routing algorithm to find the minimum-delay routes at any time from all nodes to the sink node. Further, all minimum-delay routes can be found in one execution of our routing algorithm.

3. Network Model and Problem Formulation

Consider a WSN whose topology is denoted by $G = (V, E)$ , with V being the set of nodes and $E = {(i, j) ∣ d (i, j) \leq r}$ being the set of wireless links, where $d (i, j)$ is the Euclidean distance between node i and node j, and r is the transmission radius of a node.

Assume that the network lifetime is divided into cycles and each cycle is further divided into several time slots. A given surveillance scheduling algorithm switches sensors between active and sleeping states. At any time slot, when a sensor node is in active mode, it can perform the surveillance tasks and communicate with other nodes. When a sensor node is in sleeping mode, it turns off its sensing device and radio transceiver. Here, we do not consider the case that the power of sensing device and radio transceiver can be separately controlled because sensors are usually tiny, cheap, and integrated devices. This assumption is also adopted in [1, 3, 5, 16, 17].

To simplify discussion, we assume that each cycle consists of T slots and each node i has one working period in each cycle, denoted by $[s_{i}, e_{i}]$ . Note that this assumption is not mandatory because our routing algorithm is applicable for the case that each node has multiple working periods in a cycle.

A node can receive packets at its working slots, while it can either send packets at its working slots, or wake up at its sleeping slots to send packets. The latter assumption ensures that a node can transmit its packets to its neighbors since they may work at its sleeping periods. The sink is assumed to be in receiving state all the time. These assumptions are the same as those in [16, 22].

Assume that a packet is sent only at the starting time of a slot, and receiving and acknowledging of the packet can be complemented in the slot. The link delays in duty-cycled WSN are time dependent. Suppose that node i wants to send a packet which is available at slot t to node j. There are two cases: (1) node j works at slot t; (2) node j does not work at slot t. For the first case, node i can transmit the packet without waiting, and the link delay is the transmission delay that is one slot. For the second case, node i has to wait for node j to wake up, say at slot $t^{'}$ , and the difference between these two slots (i.e., $t^{'} - t$ ) is referred to as waiting delay, denoted by $w_{i j} (t)$ . Besides waiting delay, there is one slot transmission delay, and thus, the link delay is $(t^{'} - t + 1)$ slots. In summary, the link delay is the sum of waiting delay and transmission delay.

Having link delays, we can calculate the node-to-sink delays as follows. Suppose that node i sends a packet at slot t along the route (or path) $i \to j \to k \to \dots \to s,$ where s denotes the sink node. The link delay from node i to node j is $w_{i j} (t) + 1$ . In other words, node j can forward the packet at slot $t_{j} = t + w_{i j} (t) + 1$ . Similarly, the link delay from node j to node k is $w_{j k} (t_{j}) + 1$ , and node k can forward the packet at slot $t_{k} = t_{j} + w_{j k} (t_{j}) + 1$ , and so on. Then, the delay from node i to sink s at slot t is defined to be the sum of all link delays along the route. It can be seen that the node-to-sink delays are time dependent because the link delays are time dependent.

Since there may be several routes with the same delay, to simplify discussion, the minimum delay route for node i at slot t is defined to be: (1) the route which has the minimal delay among all routes from node i to sink s; or (2) the route which has the minimal number of hops among the routes satisfying condition (1); or (3) the route whose sequence is the smallest in lexicographical order among the routes satisfying the above two conditions.

4. Routing in Duty-Cycled Networks

In this section, we present our distributed routing algorithm and prove its correctness.

4.1. Algorithm Description

To simplify discussion, we assume that each node i maintains a routing table that consists of two parts: $d e l a y_{i} [1 \dots T]$ and $n e x t h o p_{i} [1 \dots T]$ , where $d e l a y_{i} [t]$ denotes the minimum delay to the sink if node i sends a packet at slot t in a cycles, and $n e x t h o p_{i} [t]$ denotes the next hop when sending a packet at slot t.

Suppose that node j is a neighbor of node i, denoted by $j \in N b r_{i}$ , where $N b r_{i}$ denotes the set of neighbors of node i. If node i tries to send a packet at slot t to the sink through node j, it has to wait $w_{i j} (t)$ slots. If node j works at slot t, $w_{i j} (t) = 0$ ; otherwise, $w_{i j} (t) > 0$ . Besides waiting delay, it takes one slot for node i to transmit the packet to node j. Therefore, the earliest time for node j to forward the packet is at slot $(t + w_{i j} (t) + 1)$ , and the minimum delay from node j to the sink is $d e l a y_{j} [(t + w_{i j} (t) + 1) \mod T]$ , where mod denotes modulo operation (e.g., $t \mod T$ equals the remainder of division of t by T). Here, the modulo operation is used to compute the minimum delay because each node repeats its working periods from one cycle to another cycle, and thus, the minimum delay to the sink must be periodic (i.e., for each i and any t, $t \in [1 \dots T]$ , it follows that $d e l a y_{i} [t] = d e l a y_{i} [t + n T]$ , where n is a positive integer). Then, we have

\begin{array}{l} d e l a y_{i} [t] = \min_{j \in N b r_{i}} (w_{i j} (t) + 1 \\ + d e l a y_{j} [(t + w_{i j} (t) + 1) \mod T]), \end{array}

(1)

where

t \in [1 \dots T]

Based on (1), we design a minimum-delay routing algorithm (MDR) for duty-cycled WSNs. Similar to well-known Bellman-Ford algorithm, each node updates its routing table according to the routing information of neighbors, and it eventually converges to the optimal values including the minimum delay and corresponding next hop for each slot t in a cycle. In MDR, nodes exchange routing information by sending route message (RMSG). This procedure is implemented in asynchronous mode: once a node changes its routing table, it will inform all its neighbors of the new delays to the sink, and its neighbors update their routing tables accordingly. The routing algorithm will end up execution when there are no updates. The sketch of MDR is as follows.

Step 1.

Initialize the routing table of each node: for the sink s, $d e l a y_{s} [t] \leftarrow 0$ , $n e x t h o p_{s} [t] \leftarrow s$ ; for node i except the sink s, $d e l a y_{i} [t] \leftarrow \infty$ , $n e x t h o p_{i} [t] \leftarrow i$ .

Step 2.

Sink s sends a RMSG to each neighbor.

Step 3.

For each node i except sink s (a)

upon receiving a RMSG from its neighbor node j, it updates its routing table;

(b)

if there is routing update, sends a RMSG to each neighbor; otherwise, it ignores the received RMSG from node j.

Step 4.

MDR finishes when there are no RMSGs.

The route message (RMSG) is illustrated in Figure 3(a) and contains the following fields. (i)

Source: the ID of the sender.

(ii)

Destination: the ID of the receiver.

(iii)

Seq: the sequence number of this RMSG.

(iv)

Entry Num: the number of route entries in the payload of the RMSG.

(v)

Payload: contains variable number of time interval route entires (the format of which is shown in Figure 3(b) and will be explained later).

Figure 3

(a) The RMSG format; (b) a time interval route entry format.

The RMSG sent by node i contains source and destination IDs and a sequence number which is incremented by one with each transmitted RMSG. The minimum delay known so far is contained in the payload of RMSG. Instead of sending the whole delay vector $d e l a y_{i} [1 \dots T]$ , we only need to send delays associated with the working periods of node i because node i can receive packets from its neighbors only at its working slots. This reduces the length of RMSG especially when T is large and the duty cycle is low.

We further divide the working period of each node into two kinds of time intervals based on the following analysis. For node i, comparing $d e l a y_{i} [t]$ and $d e l a y_{i} [t + 1]$ will result in three cases: (1) $d e l a y_{i} [t] = d e l a y_{i} [t + 1]$ ; (2) $d e l a y_{i} [t] = d e l a y_{i} [t + 1] + 1$ ; and (3) $d e l a y_{i} [t + 1] > d e l a y_{i} [t] + 1$ .

The first case says that a packet sent by node i at slot $t + 1$ has the same delay as that sent at slot t. In other words, the packet sent by node i at slot $t + 1$ will arrive at the sink one slot later than the packet sent at slot t. For instance, in Figure 2(a), the minimum delays from node A to the sink at slot 6 and slot 7 are both 4 slots following the route $A \to B \to D \to F \to S i n k$ . It can be seen that there is no waiting delay at each hop.

The second case says that the minimum delay of a packet will decrease by one slot from slot t to $t + 1$ , which means that the earliest arrival time for the packet sent at slot t or slot $t + 1$ is the same. The second case happens when there are waiting delays at one or more hops of a route. For example, in Figure 2(b), the minimum delay from node B to the sink decreases by one from slot 1 to slot 6 following the route $B \to D \to F \to S i n k$ , and the earliest arrival time for a packet sent during the time interval $[1,6]$ is slot 8. In particular, in Figure 1, the packet sent by node B during $[1,4]$ has a waiting delay at $B \to D$ while the packet sent during $[5,6]$ has no waiting delay at $B \to D$ but has waiting delay at $D \to F$ . It can be seen that all the packets sent during $[1,6]$ want to arrive at node F at slot 7, and therefore, their arriving time at the sink is the same.

The transition from the first case to the second case may incur a sudden delay change, which is indicated by the third case. We still take node B in Figure 2(b) as an example. The minimum delay from node B to the sink at slot 8 is 3, while it suddenly changes to 10 at slot 9.

Based on the above analysis, we define two types of time intervals, that is, Type 0 and Type 1. A time interval $[t_{1}, t_{2}]$ of Type 0 for node i means that the minimum delays of the packet sent at a slot from $t_{1}$ to $t_{2}$ are the same (i.e., corresponding to the first case), while the time interval $[t_{1}^{'}, t_{2}^{'}]$ of Type 1 means that the minimum delays of the packet sent from $t_{1}^{'}$ to $t_{2}^{'}$ decrease by one (i.e., corresponding to the second case).

Now, we divide the working period $[s_{i}, e_{i}]$ of node i into time intervals of two types according to $d e l a y_{i} [1 \dots T]$ , and each time interval forms a route entry whose format is shown in Figure 3(b). A route entry of interval $[t_{1}, t_{2}]$ records the start slot ( $t_{1}$ ), end slot ( $t_{2}$ ), and the type (Type 0 or Type 1). In addition, the route entry contains two delay values Delay_1 and Delay_2, where Delay_1 denotes the delay if the packet is sent at the start slot $t_{1}$ , and Delay_2 denotes the delay if the packet is sent at the slot $t_{2} + 1$ . Delay_2 is necessary for a neighbor of node i, say node j, to compute the delay if the packet is sent to node i at the last slot (i.e., $t_{2}$ ) of the route entry (which equals $d e l a y_{i} [(t_{2} + 1) \mod T] + 1$ ). The details of adding time interval route entries to a RMSG are shown in Procedure 1.

Procedure 1: Add time interval route entries to a RMSG for node i.

Input: given a generated RMSG $m s g$ without payload,

routing table $d e l a y_{i} [1 \dots T]$ and $n e x t h o p_{i} [1 \dots T]$ ,

and working period $[s_{i}, e_{i}]$ .

Output: a RMSG containing time interval route entries

(1) generate a time interval route entry r

(2) $n u m \leftarrow 0$

(3) $k \leftarrow s_{i}$

(4) while $k \leq e_{i}$ do

(5) $t y p e \leftarrow 0$

(6) if $k + 1 \leq e_{i}$ and $d e l a y_{i} [k] = d e l a y_{i} [k + 1] + 1$ then

(7) $t y p e \leftarrow 1$

(8) for $l = k + 1$ to $e_{i}$ do

(9) if $type = 0$ and $d e l a y_{i} [l - 1] = d e l a y_{i} [l]$ then

(10) $l \leftarrow l + 1$

(11) else if $type = 1$ and $d e l a y_{i} [l - 1] = d e l a y_{i} [l] + 1$

then

(12) $l \leftarrow l + 1$

(13) else

(14) break

(15) ⊳ generate a route entry r for the time interval

$[k$ , $l - 1]$ , and catenate r to $m s g$

(16) $m s g \leftarrow m s g ∣ ∣ r (k$ , $l - 1$ , $t y p e$ , $d e l a y_{i} [k]$ , $d e l a y_{i} [l])$

(17) $n u m \leftarrow n u m + 1$

(18) $k \leftarrow l$

(19) $m s g . E n t r y N u m$ $\leftarrow n u m$

In MDR algorithm, before sending a RMSG, each node calls Procedure 1 so that time interval route entries are attached to the RMSG. For example, given the minimum delays shown in Figure 2, the RMSG sent by node F contains one route entry $(7,10,0, 1,1)$ (which follows the format shown in Figure 3(b)), while the RMSG sent by node A contains two route entries, $(4,5, 1,5, 4)$ and $(6,7, 0,4, 8)$ .

When node i receives a RMSG from node j, it will update its routing table as shown in Procedure 2. Suppose that the RMSG from node j has κ time interval route entries, that is, $r_{1}, \dots, r_{κ}$ , and they are sorted in increasing order by their starting slots. Node i computes the delay for the packet sent at slot t ( $t \in [1 \dots T]$ ) if using node j as the next hop, denoted by $d e l a y_{i}^{(j)} [t]$ . For a packet ready to be sent at slot t, node i should send it to node j as soon as possible. In other words, node i should send the packet at the working slot of node j which is closest to t. Following this rule, we can compute $d e l a y_{i}^{(j)} [t]$ for each slot t, $t \in [1 \dots T]$ . To be specific, the delay of a packet sent by node i at slot t in $[1, r_{1} . EndSlot]$ can be derived by route entry $r_{1}$ : for $t < r_{1} . StartSlot$ , there is a waiting delay $w = r_{1} . StartSlot - t$ if $r_{1} . StartSlot > t$ ; otherwise, $w = 0$ . In addition, since transmission of the packet costs one slot, the packet is ready to be forwarded by node j at slot $t + w + 1$ . So, we have $d e l a y_{i}^{(j)} [t] = w + 1 + d e l a y_{j} [t + w + 1]$ , where $d e l a y_{j} [t + w + 1]$ can be computed according to the values of Type, Delay_1, and Delay_2 in $r_{1}$ (lines 5–15). Similarly, we can compute delays during $[r_{1} . EndSlot + 1, r_{2} . EndSlot]$ based on $r_{2}$ , and so on. At last, packets sent during $[r_{κ} . EndSlot + 1, T]$ should be transmitted to node j at slot $r_{1} . StartSlot$ in the next cycle, and their delays can be derived according to $r_{1}$ (lines 17–22). After computing all delays, node i compares $d e l a y_{i} [t]$ with $d e l a y_{i}^{(j)} [t]$ . If $d e l a y_{i}^{(j)} [t] < d e l a y_{i} [t]$ , it means that it finds a better route to the sink for the packet sent at t, and thus, it updates $d e l a y_{i} [t]$ to $d e l a y_{i}^{(j)} [t]$ and $n e x t h o p_{i} [t]$ to j (lines 24–27).

Procedure 2: Update routing table for node i.

Input: given a received RMSG from node j which contains

κ time interval route entries that is, $r_{1}, \dots, r_{κ}$ , and

they are sorted in increasing order by their starting

slot.

Output: Updated $d e l a y_{i} [1 \dots T]$ and $n e x t h o p_{i} [1 \dots T]$

(1) ⊳ compute the minimum delay of each slot k if using

node j as the next hop

(2) $l \leftarrow 1$

(3) for each $α \leftarrow 1$ to κ do

(4) for $k \leftarrow l$ to $r_{α} . EndSlot$ do

(5) $w \leftarrow \max (r_{α} . StartSlot - k, 0)$

(6) if $r_{α} . Type = 0$ then

(7) if $k < r_{α} . EndSlot$ then

(8) $d e l a y_{i}^{(j)} [k] \leftarrow w + 1 + r_{α} . Delay_1$

(9) else if $k = r_{α} . EndSlot$ then

(10) $d e l a y_{i}^{(j)} [k] \leftarrow w + 1 + r_{α} . Delay_2$

(11) else if $r_{α} . Type = 1$ then

(12) if $k < r_{α} . EndSlot$ then

(13) $d e l a y_{i}^{(j)} [k] \leftarrow r_{α} . Delay_1 + r_{α} . StartSlot - k$

(14) else if $k = r_{α} . EndSlot$ then

(15) $d e l a y_{i}^{(j)} [k] \leftarrow w + 1 + r_{α} . Delay_2$

(16) $l \leftarrow r_{α} . EndSlot + 1$

(17) for $k \leftarrow r_{κ} . EndSlot + 1$ to T do

(18) $w \leftarrow T + r_{1} . StartSlot - k$

(19) if $r_{1} . Type = 0$ then

(20) $d e l a y_{i}^{(j)} [k] \leftarrow w + 1 + r_{1} . Delay_1$

(21) else if $r_{1} . Type = 1$ then

(22) $d e l a y_{i}^{(j)} [k] \leftarrow w + r_{1} . Delay_1$

(23) ⊳update routing table

(24) for $k \leftarrow 1$ to T do

(25) if $d e l a y_{i} [k] > d e l a y_{i}^{(j)} [k]$ then

(26) $d e l a y_{i} [k] \leftarrow d e l a y_{i}^{(j)} [k]$

(27) $n e x t h o p_{i} [k] \leftarrow j$

An Example. In Figure 1, assume the sink starts MDR algorithm at slot 1, and sends a RMSG with one route entry $(1,10,0, 0,0)$ to node E at slot 1, and to node F at slot 7, respectively. When node E receives this RMSG from the sink, it finds that its minimum delays to the sink are all one since it is one hop from the sink. Then, node E updates its routing table and sends a RMSG containing one route entry $(1,4, 0,1, 1)$ to node C at slot 2. Node C computes $d e l a y_{C}^{(E)} [t]$ as follows: for $t \in [1,4]$ , packet can be transmitted to node E without waiting delays, and the transmission delay is one, and therefore, $d e l a y_{C}^{(E)} [t] = 2$ , $t \in [1,4]$ ; for $t \in [5,10]$ , node C has to wait to the slot 1 in the next cycle when node E works, which incurs a waiting delay of $w = T + 1 - t$ . The packet will be transmitted to node E at slot 1 in the next cycle and then forwarded by node E at slot 2, and thus, $d e l a y_{C}^{(E)} [t] = w + 1 + d e l a y_{E} [2] = w + 2$ , $t \in [5,10]$ . In summary, node C obtains $d e l a y_{C}^{(E)} = (2,2, 2,2, 8,7, 6,5, 4,3)$ . Node C updates its routing table and generates a RMSG with two route entries $(2,4, 0,2, 8)$ and $(5,5, 0,8, 7)$ , and then, it sends this RMSG to node E at slot 3, to node A at slot 4, and to node D at slot 5, respectively. Node E will ignore this RMSG because it has converged to the minimum delays, while both node A and node D update their delays to $(4,3, 3,9, 8,9, 8,7, 6,5)$ as they receive the same RMSG from node C. Next, we focus on routing updates of node C and node D. At slot 7, node F receives RMSG from the sink and sets all delays to 1. Then, node F sends a RMSG with one route entry $(7,10,0, 1,1)$ to node D at slot 8. Node D obtains $d e l a y_{D}^{(F)} = (8,7, 6,5, 4,3, 2,2, 2,2)$ . By comparing $d e l a y_{D}^{(F)}$ with $d e l a y_{D} = (4,3, 3,9, 8,9, 8,7, 6,5)$ , node D updates its routing table as $d e l a y_{D} = (4,3, 3,5, 4,3, 2,2, 2,2)$ and $n e x t h o p_{D} = (C, C, C, F, F, F, F, F, F, F)$ , which in fact converges to minimum delays. When node C receives the RMSG from node D which contains two route entries $(5,7, 1,4, 2)$ and $(8,8, 0,2, 2)$ , it derives $d e l a y_{C}^{(D)} = (8,7, 6,5, 4,3, 3,3, 10,9)$ . Node C compares $d e l a y_{C}^{(D)}$ with $d e l a y_{C} = (2,2, 2,2, 8,7, 6,5, 4,3)$ and updates its routing table to $d e l a y_{C} = (2,2, 2,2, 4,3, 3,3, 4,3)$ and $n e x t h o p_{C} = (E, E, E, E, D, D, D, D, E, E)$ , which also converges to minimum delays.

4.2. Correctness

Proposition 1.

In a duty-cycled WSN with the cycle length of T slots, if each node, say i, has fixed one or more working periods in all cycles, then it follows that (a)

the minimum delay for the packet sent by node i at slot t is a periodic function with T ; that is, $d e l a y_{i} [t] = d e l a y_{i} [t + T]$ ;

(b)

to estimate the minimum delays for each slot t , $t \in [1 \dots T]$ , node i only needs to know the delays associated with its neighbors' working slots. It is sufficient for node i to exchange routing messages generated by Procedure 1 with its neighbors.

We have Proposition 1 part (a) because each node repeats its working mode from one cycle to another, and thus, the minimum delay from a node to the sink at slot t is a periodic function with cycle length T. In duty-cycled WSN, each node only receives packets at its working slots, which means that the transmission is receiver-based. So, to compute the minimum delay for the packet sent by node i at slot t, node i only needs the delays associated with its neighbors' working slots, which can be derived from the routing entries contained in the RMSGs sent by its neighbors. Therefore, we have Proposition 1 part (b).

Suppose that the topology of a wireless sensor network $G = (V, E)$ is connected and the RMSGs sent by a node can be correctly received by its neighbors in finite time. Then, we have the following Theorem.

Theorem 2.

Suppose that time is divided into cycles with the length of T slots and each node has fixed working periods in all cycles. Further, assume that the transmitted packet can be correctly received by the receiver in finite time, and there is no topological change during the execution of MDR algorithm. Then, the execution of MDR algorithm will terminate in finite time. At the end of execution, each node obtains the minimum delay to the sink and corresponding next hop for a packet which is ready to be sent at each slot of a cycle.

Proof.

Consider any node i at slot t, $t \in [1 \dots T]$ . Let $P = i \to j \to k \to \dots u \to v \to s$ be the minimum-delay route from node i to the sink s at slot t, and the time sequence when the packet is available to be sent is $(t_{i}, t_{j}, t_{k}, \dots, t_{u}, t_{v})$ , and $t_{i} = t$ . Then, path P must be a simple path which means that it does not contain any cycle; otherwise, we can find a route which has less delay than the route P by removing the cycle as all link delays are positive (at least one slot for transmission). Further, the route P has optimal substructure; that is, the sub-path from any intermediate node, say node k, to sink s is the minimum-delay route for node k at time $t_{k}$ , which can be easily proved by contradiction. Suppose, the subpath from node k to sink s (i.e., $k \to \dots u \to v \to s$ ) at time $t_{k}$ is not a minimum-delay route. Then, we can replace the sub-path in route P with the minimum-delay route from node k to sink s at time $t_{k}$ , and obtain a route which has less delay than P, which contradicts with the assumption that P is the minimum-delay route.

Next we show nodes in route P sequentially achieve their minimum latency in backward direction. Denote $d e l a y_{i}^{*} [t]$ the minimum packet delivery latency for node i at time t, and denote $d e l a y_{i} [t]$ the delay computed by MDR. Recall that we start routing algorithm from sink s. Since node v is one hop from sink s, its minimum delay for any time t in a cycle is one. Therefore, when node v receives RMSG from sink s, it updates its routing table, and it follows that $d e l a y_{v} [t_{v}] = d e l a y_{v} [t_{v} \mod T] = 1$ according to Proposition 1 (a). Moreover, since the packet is ready to be sent right after it has been received, therefore slot $(t_{v} - 1)$ must be a working slot of node v. After updating routing table, node v sends to each neighbor a RMSG which contains the information of $d e l a y_{v} [t_{v} \mod T]$ . When node u receives this RMSG, it will calculate the packet delivery latency at $t_{u}$ . Note that the link delay from node u to node v at time $t_{u}$ is fixed, which consists of waiting delay $w_{u v} (t_{u}) = t_{v} - t_{u} - 1$ and one transmission delay. So, we have $d e l a y_{u} [t_{u}] = w_{u v} (t_{u}) + 1 + d e l a y_{v} [t_{v}] = t_{v} - t_{u} + d e l a y_{v} [t_{v}] = t_{v} - t_{u} + d e l a y_{v}^{*} [t_{v}]$ . According to optimal substructure property, it follows that $d e l a y_{u} [t_{u}] = d e l a y_{u}^{*} [t_{u}] = d e l a y_{u}^{*} [t_{u} \mod T]$ . Node u updates its routing table and sends to its neighbors a RMSG which carries the information of $d e l a y_{u}^{*} [t_{u} \mod T]$ . Recall that route P is a simple path which means it has at most $| V | - 1$ hops in $G = (V, E)$ . Then, after no more than $| V |$ updates backward along the route P, $d e l a y_{i} [t]$ will eventually converge to $d e l a y_{i}^{*} [t]$ . Further, it will not decrease any more in the later updating processes as there is no negative cycle in the network. In summary, each node will obtain $d e l a y_{i}^{*} [t]$ for any $t \in [1 \dots T]$ in finite time.

5. Route Maintenance in Duty-Cycled Networks

The routes determined by MDR may not be optimal if the network dynamically changes (e.g., a node is added to the network, a node changes its working periods, or a node fails). Recomputing the minimum-delay routes is not a trivial task because (1) when a topological change happens, say a node failure, it is hard to know which nodes will be affected by this event as each node only has its next-hop information in its routing table; (2) even if node j tells node i that it has been affected by the event and node j is a next hop node of node i for some time slots, node i cannot make sure that it is also affected since the routes are time dependent; and (3) moreover, even if all minimum-delay routes of node i must go through node j who has been affected by the event, it is still possible that not all routes at all time slots will be affected.

For example, in Figure 1, suppose that node C fails, which affects node D since node C is its next hop (e.g., the minimum delay at slot 1 from node D to the sink will be 8 slots instead of 4 slots). Now, suppose that node D informs node B that it has been affected by the failure of node C. Node B finds that node D is the next hop for all time slots, thereby jumping to a conclusion that all routes are invalid. In fact, node B is not affected by the failure of node C at all. This is because all minimum-delay routes from node B to sink go through node D and then node F to the sink.

All the above issues are features of route maintenance in duty-cycled WSNs, which are different from traditional route maintenance. Moreover, like routing information protocol (RIP), MDR is a distributed distance-vector algorithm, and it also suffers from the well-known problems of counting-to-infinity and routing-table loops in route maintenance. The work in [25] studies this problem and provides four sufficient conditions for designing loop-free routing algorithms. Although the methods proposed in [25] cannot be directly applied to solve our problem, we are inspired by one of the four sufficient conditions, that is, distance increase condition (DIC), whereby designing MDR maintenance algorithm. DIC says if a node detects an increase in the distance of a neighbor, then it must maintain its current next hop. Otherwise, it can update its distance value and the next hop.

Note that different types of topological changes have different impacts on the delays. For example, when a node joins the network, then the minimum delays from nodes to sink can further decrease as the added node provides more options for routing. However, when a node fails, the minimum delays from nodes to sink may increase or remain unchanged. A more complex case is when a node changes its working periods. For this case, the minimum delays from nodes to sink may increase, decrease, or remain unchanged. So, the route maintenance algorithm should be able to handle all these cases.

We design a unified framework for route maintenance to handle all above cases. MDR maintenance algorithm consists of three phases and uses four maintenance messages, that is, INFORM, QUERY, REPLY, and UPDATE. These four maintenance messages have the same format with RMSG, as shown in Figure 3. The goal of the first phase is to identify all route entries that are affected by the topological change. After the first phase, the nodes who are affected by the topological change send queries to thier neighbors to obtain their routing tables. When a node receives all neighbors' routing tables, it updates its routing table and goes into the third phase. The last phase is similar to MDR procedure: if there are routing updates, send an update message to each neighbor; otherwise, ignore the received update message. Note that for the case of a node insertion, MDR maintenance algorithm goes directly to the last phase (according to DIC) since delays cannot increase, while the maintenance for other cases (e.g., a link failure, change of working period of a node, and a node failure) includes three phases.

Procedure 3 gives the main operations of MDR maintenance algorithm. We take a node failure as an example to describe the process. Suppose that node k fails, which is detected by its neighbor, node j. Node j checks if there are route entries which use node k as next hop. If there are some, node j sets the delays of these entries to infinity and sends an INFORM that carries the information of its current routing table to each neighbor.

Procedure 3: MDR maintenance for node i.

Upon receiving a INFORM from node j

If $n e x t h o p_{i} [t] \neq j$ for all t, $t \in [1 \dots T]$ then

return

$b_d e l a y_{i} [1 \dots T] \leftarrow d e l a y_{i} [1 \dots T]$

$b_n e x t h o p_{i} [1 \dots T] \leftarrow n e x t h o p_{i} [1 \dots T]$

for all t such that $n e x t h o p_{i} [t] = j$ do

$d e l a y_{i} [t] \leftarrow \infty$

call Procedure 2 to update route table

$f l a g \leftarrow 0$

for all t such that $n e x t h o p_{i} [t] = j$ do

If $d e l a y_{i} [t] = \infty$ and $b_d e l a y_{i} [t] \neq \infty$ then

$f l a g \leftarrow 1$

break

If $f l a g = 1$ then

send INFORMs to its neighbors

else

$d e l a y_{i} [1 \dots T] \leftarrow b_d e l a y_{i} [1 \dots T]$

$n e x t h o p_{i} [1 \dots T] \leftarrow b_n e x t h o p_{i} [1 \dots T]$

Upon receiving a QUERY from node j

send a REPLY to node j

Upon receiving a REPLY from node j

if all REPLYs of its neighbors have been received then

call Procedure 2 to update route table

If $d e l a y_{i} [t]$ decreases, $\forall t \in [1 \dots T]$ then

send UPDATEs to its neighbors

Upon receiving a UPDATE from node j

call Procedure 2 to update route table

If $d e l a y_{i} [t]$ decreases, $\forall t \in [1 \dots T]$ then

send UPDATEs to its neighbors

Suppose that node i receives the INFORM sent by node j, and it also checks whether node j is the next hop in its routing table. If node j is not the next hop for all time slots, node i simply drops the INFORM. Otherwise, node i backs up its routing table and temporarily sets the delays of the entries related to node j to infinity. Node i then calls Procedure 2 to update its routing table. After that, node i compares this routing table with the backup one. If there are some entries whose delays are not infinity in backup routing table but become infinity in newly computed routing table, then node i can be sure that these routing entries are affected by the node failure.

A node, say node i, who is affected by the failure of node k goes into the second phase when finishing the first phase. Node i sends a QUERY to each neighbor, and its neighbor responds with a REPLY. After receiving all REPLYs from its neighbors, node i updates its routing table based on the received routing information. If there exist route updates (i.e., delay decrease for some time slots), node i goes into the third phase and sends an UPDATE to each neighbor.

It can be seen that, in the first phase, the delay of a node at any slot is not allowed to decrease, and all affected routes will be identified, and their corresponding delay values are set to infinity. The rationale of MDR maintenance algorithm is to first increase the delays of the routes at any time slot, which satisfies DIC condition, and then, nodes start the converge process (i.e., decreasing delays), similar to that of MDR.

6. Discussion

(1)

In our network model, we assume that sensors' states (active or sleeping) are predefined by a given surveillance scheduling algorithm. In fact, jointly designing scheduling and routing algorithms is a better way to guarantee the effectiveness of a surveillance sensor network.

(2)

In a surveillance sensor network, sensors collaborate with each other to fulfill the surveillance tasks, which requires time synchronization among nodes. Furthermore, time synchronization is also needed to implement slotted transmissions. Fortunately, time synchronization protocols such as FTSP [26] can provide sufficient accuracy without much communication overhead.

(3)

Our routing algorithm is capable of finding minimum latency routes for all nodes at any time, but it cannot guarantee that the packet can be successfully transmitted along the minimum latency route because the wireless communication link is unreliable. Nevertheless, the minimum-delay routing tables will help a node make a decision about the time of retransmission. For example, if the minimum delays to the sink do not change or change smoothly in some period of time, the node can select a neighbor and/or a time slot when the estimated link quality is acceptable. In contrast, if the minimum delay will increase suddenly, the node may take a risk and transmit the packet even if the estimated link quality is low.

(4)

There is a tradeoff between routing optimality and maintenance cost in route maintenance. Obviously, it is not energy efficient for a node to start a route maintenance when it finds that the delays of its routes increase by a few slots due to a topological change (e.g., a link failure). For this case, the node can simply forward the packets along suboptimal routes. In real applications, to save energy, nodes perform route maintenance only when there is a big change of the routing tables.

7. Performance Evaluation

Extensive simulations are carried out over a customized C++ simulator to evaluate the performance of proposed algorithms. We design three sets of simulations. In the first set of simulation, we want to show that optimal-PML algorithm in [16] cannot be directly applied to solve many-to-one routing problem as running it for each node will incur large time cost as well as message cost. Small-scaled WSNs are randomly deployed in a 500 m × 500 m area. The cycle length $T = 50$ , and the duty cycle 𝒟 is 0.4. Each node randomly selects its working period with the length being $T \cdot 𝒟$ slots. Each statistic is collected in 100 simulation runs. Table 1 gives the time cost and message cost of optimal-PML and MDR for small-scaled networks. It can be seen that the time cost and message cost of MDR are dramatically less than those of optimal-PML. Specifically, the message cost of MDR is less than one percent of that of optimal-PML. The high cost of optimal-PML is mainly because it is a flood-based algorithm.

Table 1

Comparison between MDR and optimal-PML on time cost and message cost.

Number of nodes	Time cost (slots)		Message cost
Number of nodes	Optimal-PML	MDR	Optimal-PML	MDR
50	20040	331	48693	462
60	19496	387	90143	869
70	23342	440	157010	1312
80	25842	460	260940	2213
90	27406	492	373876	3103
100	31439	527	536780	4120

In the second set of simulation, we select two routing algorithms for comparison: one is shortest path (SP) routing algorithm which represents traditional routing algorithm and the other is fast time-dependent shortest path (FTSP) algorithm proposed in [15] (introduced in Section 2).

We first compare MDR with SP in terms of expected packet delivery latency. We consider a scenario where 500 sensors are randomly deployed in a 1000 m × 1000 m area. To simulate the effect of duty cycle on expected packet delivery latency, we set duty cycle 𝒟 to be 0.4, 0.2, and 0.1, respectively. The cycle length $T = 50$ , and each node randomly selects its working period with the length being $T \cdot 𝒟$ slots. For each generated duty-cycled WSN, we run MDR and SP, respectively. Then, nodes with different hops away from the sink are randomly selected. Assume that a node sends a packet at each slot with identical probability, and the expected minimum latency of a node is calculated by averaging minimum delays for all slots in a cycle. Each statistic is collected in 50 simulation runs.

Figure 4 compares the expected packet delivery latency of MDR and SP. It can be seen that MDR has an obvious advantage over SP as SP does not take the duty cycle into account. When duty cycle $𝒟 = 0.4$ , the expected packet delivery latency of MDR is less than one-half of that of SP. Moreover, the latency differences between SP and MDR increase with the number of hops. For instance, when node is more than 14 hops away from the sink node, the expected packet delivery latency of MDR is about one third of that of SP. As the duty cycle decreases (i.e., nodes decrease their working slots), the expected packet delivery latency of MDR and SP increases. Interestingly, it is observed that the latency of MDR for $𝒟 = 0.2$ is almost the same as that of SP for $𝒟 = 0.4$ , and the latency of MDR for $𝒟 = 0.1$ is much less than that of SP for $𝒟 = 0.2$ . This means, compared with traditional routing algorithms such as SP, MDR achieves a better performance while saving nodes' energy.

Figure 4

Comparison between MDR and SP on expected packet delivery latency.

We also compare MDR with FTSP algorithm. We modify FTSP algorithm so that it can be applied in our context. FTSP exchanges delay vectors between neighbor nodes, and it runs in rounds which is implemented by a β-synchronizer [27]. We set $𝒟 = 0.4$ , and the node density is the same as that in previous experiment. Figure 5 compares the time cost of MDR and FTSP. The time cost of MDR is much less than that of FTSP because MDR adopts an asynchronous mode which accelerates the process of converging to minimum delays, while FTSP updates nodes' minimum delays round by round, and a new round can start only when all nodes have finished the required procedure. Figure 6 shows the number of bytes sent per node, which also reflects the energy consumption in MDR and FTSP. It can be seen that a node in MDR sends much fewer bytes than that of FTSP. This is because MDR attempts to decrease the size of each route message by conveying the information of minimum delays through time interval entries, which makes MDR feasible in real applications as the packet size in WSNs is very small (e.g., the maximum payload length is 29 bytes in TinyOS 2.x).

Figure 5

Comparison between MDR and FTSP on time cost.

Figure 6

Comparison between MDR and FTSP on bytes sent per node.

In the last set of simulation, we perform MDR maintenance algorithm for four types of topological changes, that is, a node insertion, change of working period of a node, a link failure, and a node failure. The number of nodes is 500 and $𝒟 = 0.1$ . For each type of topological change, say a node failure, we randomly generate 1000 scenarios, and for each scenario, we randomly fail a node and run MDR maintenance algorithm. Figures 7 and 8 show the CDF of the time cost and the message cost of MDR maintenance algorithm, respectively. It can be seen from Figure 7 that quite a few link failures and node failures (over 70% and 30%, resp.) have no impact on the networks, while a node insertion and change of working period of a node often incur route maintenance. Among the four types of topological changes, the expected time cost of route maintenance, from low to high, is for a link failure, a node insertion, a node failure, and change of working period of a node. Generally, the message cost is proportional to the time cost, which is validated by Figure 8. All these simulation results will provide helpful guides for designing duty-cycled surveillance systems.

Figure 7

CDF of the time cost of MDR maintenance algorithm.

Figure 8

CDF of the message cost of MDR maintenance algorithm.

8. Conclusions

In this paper, we address the problem of routing in duty-cycled surveillance sensor networks. We propose a distributed routing algorithm which can find the minimum-delay routes from all nodes to sink in one execution. Extensive simulation results show that the performance of our algorithm outperforms other existing algorithms. We further provide a distributed route maintenance algorithm for finding the minimum-delay routes when the network dynamically changes. Our future work includes jointly designing scheduling and routing algorithms so as to improve the effectiveness of surveillance sensor networks.

Footnotes

Acknowledgments

This work is supported by the National Natural Science Foundation of China under Project 61172069, the Natural Science Basic Research Plan in Shaanxi Province of China (Program no. 2011JM8029), and 111 Project (no. B08038).

References

Cardei

Thai

M. T.

Energy-efficient target coverage in wireless sensor networks

Proceedings of the IEEE INFOCOM

March 2005

Liu

Cao

Distributed critical location coverage in wireless sensor networks with lifetime constraint

Proceedings of the IEEE INFOCOM

2012

Kasbekar

G. S.

Bejerano

Sarkar

Lifetime and coverage guarantees through distributed coordinate-free sensor activation

IEEE/ACM Transactions on Networking 2011 19 2 470 483

2-s2.0-79955475521

10.1109/TNET.2010.2077648

C. W.

K.-M.

W.-T.

Lin

C.-T.

Lin

C. Y.

Target coverage in wireless sensor networks

Proceedings of the 7th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN '11)

December 2011

408 412

2-s2.0-84856194556

10.1109/MSN.2011.78

Liu

Chu

Leung

Y.-W.

Jia

Wan

P.-J.

General maximal lifetime sensor-target surveillance problem and its solution

IEEE Transactions on Parallel and Distributed Systems 2011 22 10 1757 1765

2-s2.0-80052324615

10.1109/TPDS.2011.42

Zhao

Fundamental results on target coverage problem in wireless sensor networks

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '09)

December 2009

2-s2.0-77951600164

10.1109/GLOCOM.2009.5425300

Zhu

On guaranteed detectability for surveillance sensor networks

International Journal of Distributed Sensor Networks 2012 2012 15

10.1155/2012/852027

852027

Krishnamurthy

Luo

Yan

Stoleru

Zhou

Cao

Vicaire

Stankovic

J. A.

Abdelzaher

T. F.

Hui

Krogh

VigilNet: an integrated sensor network system for energy-efficient surveillance

ACM Transactions on Sensor Networks 2006 2 1 1 38

2-s2.0-33646523960

10.1145/1138127.1138128

Qin

A dynamic neural network approach for solving nonlinear inequalities defined on a graph and its application to distributed, routing-free, range-free localization of WSNs

Neurocomputing 2013 117 72 80

10.

Wang

Using Laplacian Eigenmap as heuristic information to solve nonlinear constraints defined on a graph and its application in distributed range-free localization of wireless sensor networks

Neural Processing Letters 2012 37 3 411 424

11.

Watteyne

Pister

K. S. J.

Wireless sensor networks technology overview

The Internet of Things: Connecting Objects to the Web 2013

Wiley

12.

Gnawali

Fonseca

Jamieson

Moss

Levis

Collection tree protocol

Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems (SenSys '09)

November 2009

2-s2.0-74549185267

10.1145/1644038.1644040

13.

RPL

IPv6 Routing Protocol for Low-Power and Lossy Networks

RFC 6550

14.

Lin

Spatiotemporal delay control for low-duty-cycle sensor networks

Proceedings of the IEEE Real-Time Systems Symposium

2009

15.

Lai

Ravindran

On distributed time-dependent shortest paths over duty-cycled wireless sensor networks

Proceedings of the IEEE INFOCOM

March 2010

2-s2.0-77953300083

10.1109/INFCOM.2010.5461987

16.

Liu

Song

Cao

Routing in intermittently connected sensor networks

Proceedings of the 16th IEEE International Conference on Network Protocols (ICNP '08)

October 2008

278 287

2-s2.0-67249165295

10.1109/ICNP.2008.4697046

17.

Nguyen

D. T.

Choi

M. T.

Choo

Design and analysis of a multi-candidate selection scheme for greedy routing in wireless sensor networks

Journal of Network and Computer Applications 2011 34 6 1805 1817

2-s2.0-80052729021

10.1016/j.jnca.2010.12.009

18.

Meng

M. Q. H.

Chen

SP-NN: a novel neural network approach for path planning

Proceedings of the IEEE International Conference on Robotics and Biomimetics

2007

19.

Olfati-Saber

Murray

R. M.

Consensus problems in networks of agents with switching topology and time-delays

IEEE Transactions on Automatic Control 2004 49 9 1520 1533

2-s2.0-4644244041

10.1109/TAC.2004.834113

20.

Olfati-Saber

Shamma

J. S.

Consensus filters for sensor networks and distributed sensor fusion

Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference (CDC-ECC '05)

December 2005

6698 6703

2-s2.0-33746234422

10.1109/CDC.2005.1583238

21.

Luo

Mao

Sun

Tang

Delay minimum data collection in the low-duty-cycle wireless sensor networks

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '12)

2012

22.

Dynamic switching-based data forwarding for low-duty-cycle wireless sensor networks

IEEE Transactions on Mobile Computing 2011 10 12 1741 1754

2-s2.0-80055010573

10.1109/TMC.2010.266

23.

Xiong

Wang

Liu

Multiple task scheduling for low-duty-cycled wireless sensor networks

Proceedings of the IEEE INFOCOM

April 2011

1323 1331

2-s2.0-79960880119

10.1109/INFCOM.2011.5934916

24.

Hao

Zhang

Mouftah

Routing protocols for duty cycled wireless sensor networks: a survey

IEEE Communications Magazine 2012 50 12 116 123

25.

Garcia-Lunes-Aceves

J. J.

Loop-free routing using diffusing computations

IEEE/ACM Transactions on Networking 1993 1 1 130 141

2-s2.0-0027542312

10.1109/90.222913

26.

Maroti

Kusy

Simon

Ledecai

The flooding time synchronization protocol

Proceedings of the SenSys

2004

27.

Orda

Rom

Distributed shortest-path protocols for time-dependent networks

Distributed Computing 1996 10 1 49 62

2-s2.0-0030196020

Routing in Duty-Cycled Surveillance Sensor Networks

Abstract

1. Introduction

2. Related Work

3. Network Model and Problem Formulation

4. Routing in Duty-Cycled Networks

4.1. Algorithm Description

Step 1.

Step 2.

Step 3.

Step 4.

Procedure 1: Add time interval route entries to a RMSG for node i.

Procedure 2: Update routing table for node i.

4.2. Correctness

Proposition 1.

Theorem 2.

Proof.

5. Route Maintenance in Duty-Cycled Networks

Procedure 3: MDR maintenance for node i.

6. Discussion

7. Performance Evaluation

8. Conclusions

Footnotes

Acknowledgments

References