Delay-Driven Routing for Low-Duty-Cycle Sensor Networks

Abstract

Duty-cycled operation has been introduced as an efficient way to preserve nodes energy and prolong network lifetime for wireless sensor networks. However, such networks are often logically disconnected since there is a limited number of active nodes within a period of time. Traditional routing algorithms, which have been designed for always-awake wireless networks, suffer excessive waiting time incurred by asynchronous schedule of nodes and cannot be applied to these time-dependent sensor networks. In this work, we study the optimization of delivery delay for low-duty-cycle sensor networks. Specially, we theoretically analyze the sleep latency in low-duty-cycle networks and present a new routing metric, which takes both lossy link and asynchronous schedule of nodes into consideration. Based on the metric, we propose delay-driven routing algorithms to find optimal forwarder in order to reduce delivery delay for source-to-sink communication. We compare our design against state-of-the-art routing algorithms derived in wireless networks through large-scale simulations and testbed experiments, which show that our algorithms can achieve a significant reduction in delivery delay.

1. Introduction

Wireless sensor network (WSN) is supposed to be a potential solution for many surveillance applications deployed in unmanned or hostile environment, such as habitat and ecological monitoring [1–4], disaster and scientific exploration [5, 6]. Many of these applications are designed for long-term existence, which requires battery-powered sensor to survive several months even years. However, it is too expensive even infeasible to replace or replenish energy-depleted nodes in large scale. To reduce the gap between application requirements and limited energy supply, duty-cycled operation is introduced as an economical way to preserve energy [1], with which sensor nodes wake up briefly and then sleep for a long period of time. Consequently, large amount of energy consumed in idle state, which is a state that transceiver of node keeps on listening to surrounding channel in order to be ready for possible incoming packets, can be greatly reduced.

However, it is impossible to maintain an always-awake communication backbone in such duty-cycled networks. Firstly, most of power management protocols [7, 8] are proposed to conserve energy, where the minimum number of sensor nodes are scheduled to be active at certain time. Secondly, nodes are often asynchronously scheduled in order to meet the requirement of coverage or connectivity [9, 10]. In other words, the connectivity of network is often related to the spatial-temporal distribution of sensor nodes. Thus, the existing routing schemes are impractical as they are designed based on the assumption that nodes are always awake, and they can overhear channels and receive packets from neighboring nodes. Consequently, sleep latency [8] instead of energy-efficiency is most significant for low-duty-cycle sensor networks.

In this paper, we attempt to study the optimization of delivery delay from the perspective of routing mechanism, which can be applied to randomly scheduled network topology with asynchronously duty-cycled nodes. We first introduce expected sleep latency (ESL) as a routing metric for source-to-sink communication in such time-dependable networks. In particular, we theoretically analyze the sleep latency for both single-hop and multihop data forwarding under unreliable link quality and then present the new metric for delay optimization in low-duty-cycle sensor networks. Based on the metric, we propose local-optimized routing and global-coordinated routing algorithm to reduce sleep latency for source-to-sink communication. To validate our design, extensive simulations and testbed experiments are conducted.

The rest of the paper is organized as follows. Section 2 introduces the related work. Section 3 presents network model and assumptions. In Section 4, we propose the new metric and routing algorithms. Simulation and testbed results are discussed in Sections 5 and 6, respectively. Section 7 concludes the paper.

2. Related Work

Different routing algorithms have been proposed to optimize network performances in wireless networks. In geographic routing [11], data packets are often forwarded via farthest neighboring node to minimize hop distance between source and destination. To handle lossy link in sensor networks, Zamalloa and Seada investigate distance-hop tradeoff for geographic routing and show that the product of packet reception rate and distance traversed to the destination is an optimal value to decide data forwarding path [12]. De Couto et al. introduce expected transmission count (ETX) as a metric to find high-throughput path in multihop wireless communication [13]. However, all these schemes are designed for the purpose of optimizing network performances in always-awake networks.

On the other hand, many power management approaches have been proposed to schedule nodes in order to conserve energy for low-duty-cycle networks. Though these schemes are generally application-dependent, they can be classified into coordinated duty-cycling or random duty-cycling. The prior is often designed to meet specific requirements of application [7, 8]. For example, Cao et al. present both sleep scheduling scheme and streamlined forwarding technique towards the detection of rare events in sensor networks [8]. With randomly wake-up schedule, sink-to-node communication delay is bounded with active-slots augmentation in duty-cycled sensor networks [14]. Gu et al. also argue that delivery delay could be reduced if more sink nodes are introduced into network [15]. Keshavarzian et al. firstly introduce multiparent forwarding mechanism to optimize delay [16]. More recently, Gu and He extend such multiparents forwarding technique to duty-cycled sensor networks [17]. The rationale behind is that a forwarding set consisting of multiple potential candidates rather than single node is selected to relay data packets at each hop, by which waiting time can be reduced in case of transmission failure. Our work is focused on routing strategy for delay optimization in low-duty-cycle sensor network, which is complementary or orthogonal to these works.

Some other works are also focused on schedule or data forwarding problem to trade off delivery delay and energy efficiency [18–24]. Both Su et al. [18] and Lai and Ravindran [19] study the minimum-latency routing problem in time-dependent sensor networks. However, their works are based on the assumption of perfect link and reliable transmission. An opportunistic routing scheme (ORW) [20] is proposed to balance delay and energy consumption, where low-power-listening technique is used. Similar to our work, a metric referred to as EDC is proposed for opportunistic routing in duty-cycled sensor network [21]. Instead of delay optimization, EDC is presented for the purpose of energy-efficiency improvement.

3. Model and Assumptions

In this section, we describe the notation of sleep latency and network model for low-duty-cycle sensor networks.

3.1. Delay Model

In duty-cycled sensor networks, all nodes decide and share their own working schedules, which are usually asynchronous among neighboring nodes in order to reduce information redundancy [8]. Guided by such working schedule, a sensor node is either in an active state or a dormant state at a given slot. For effective communication, a node has to transmit a packet when its receiver is in the active state. In this case, the connectivity among nodes becomes time-dependent since their neighboring nodes consistently switch between active and dormant states. Formally, we can denote the duty-cycled network at a given time t as a time-dependent graph, $G (t) = (V, E (t))$ , where V is the nodes set of whole network and $E (t)$ is the set of directed edges at time t. A directed edge $e_{i j} (t)$ belongs to $E (t)$ if and only if nodes $i, j$ are within each other's communication range, and the receiver is in the active state so that it can receive packets from the sender [17].

Note that sensor nodes often have periodical schedule for sensing purposes in realistic applications [8]. Without loss of generality, suppose the duration of working period to be T, we can divide it into a sequence of time slots with equal length τ, during which sensor node is in either active or dormant. Consequently, the working schedule for node i, $Γ_{i}$ can be uniquely represented as a list of active slots, that is, $Γ_{i} = {t_{1}^{i}, t_{2}^{i}, \dots, t_{K}^{i}}$ , where K is the number of active slots within whole period.

We define sleep latency, $s_{i j} (t)$ , as the waiting time from the moment (t) that the sender i has a packet being ready to the moment that the receiver j is in the receiving state. To elaborate, we give a sample topology shown in Figure 1(a) where nodes A, B, and C wake up and sense periodically according to the schedule depicted in brackets given whole period $T = 10$ . Figure 1(b) illustrates the communication diagram between node A and nodes B, C. For example, the sender A is ready to send packet at 3 but has to buffer it for a period of time until the receiver B wakes up at slot 7. Thus, the sleep latency between node A and node B is $s_{AB} (3) = 7 - 3 = 4$ since the packet is actually received by node B at slot 7. Consequently, the sleep latency of whole forwarding path from A to D through B is $s_{AD} (3) = 5$ if all links are assumed to be reliable. However, the sleep latency from node A to node D via node C could be different since node A has to wait for the chance of transmission in C's next period. In fact, the delay from node A to node D through C is $s_{AD}^{'} (3) = 15$ .

Figure 1

Duty-cycled sensor network.

Note that sleep latency in low-duty-cycle sensor network is usually far more larger than other delivery delay, such as processing, transmission, or propagation delay in traditional sensor networks, which are normally in the order of milliseconds. In this paper, we suppose that sleep latency and delivery delay are equivalent notions in low-duty-cycle sensor networks.

3.2. Network and Traffic Model

Different from traffic model in wireless ad hoc networks, data collection is the main communication model for sensor networks, where data packets converge from many source nodes to a few sink nodes. To assure loop-free data forwarding, we assume a traffic model shown in Figure 2 where data packets always flow from lower level (with larger hop count) to the sink through those nodes in higher level. In particular, we can formulate a forwarding set (FS) for each node, which consists of neighbors with less hop count to the sink. Thus, routing module will only select next hop from the forwarding set. As the example shown in Figure 2, the forwarding set of node A, ${FS}_{A} = {B_{1}, B_{2}, B_{3}}$ is actually the subset of neighboring table.

Figure 2

Traffic model.

3.3. Assumptions

Suppose that the source node has data packets to be sent to the sink node periodically; we make following assumptions.

(1)

The discussion of work scheduling in the sensor network would be irrelevant if there were not some synchronizing mechanisms [25]. We assume that the network is locally synchronized so that a node knows when it can send packet with the information of neighbors’ working schedules.

(2)

It is reasonable to assume that there is low data traffic in low-duty-cycle sensor nodes since the sleep period of nodes is relatively long. Consequently, the delay such as queueing latency due to transmission interference or network congestion can be trivial.

(3)

We assume the existence of wireless transmission failure. The probability of a successful transmission through a wireless communication link is quantified by link qualities, which can be measured by probe-based approaches in [13, 26] or through low-cost piggybacking on normal data traffic. Our design does not depend on the specified link model. For simplicity, a realistic channel model derived in [27] is utilized for the simulations. The model considers several environmental and radio parameters, such as path-loss exponent, log-normal shadowing variance, the modulation, and encoding schemes of the radio.

4. Main Design

The main goal of our design is to find optimal forwarder for each node so that the delivery delay from source to the sink node could be reduced.

4.1. Expected Sleep Latency

In this section, we present a new metric for routing decision in low-duty-cycle sensor networks. For simplicity, we first consider single wake-up schedule, where each node wakes up only once within the whole period (T).

Assuming that the working time of nodes A, B is $t_{A}$ , $t_{B}$ , respectively, shown in Figure 3, the ESL from node A to node B can be represented as the following if the link is reliable (i.e., $q = 1$ ):

\begin{matrix} S_{1} = {\begin{cases} t_{B} - t_{A}, & t_{B} \geq t_{A} \\ t_{B} - t_{A} + T, & t_{B} < t_{A} . \end{cases} \end{matrix}

(1)

Figure 3

Sleep latency over single hop.

However, wireless link is notoriously unreliable in extremely dynamic environments. Thus, the estimation of sleep latency should take transmission failure into consideration. In case of failure, the sender has to wait for whole working period to get the next chance of retransmission. The sleep latency of the $k th$ transmission, $S (k)$ , can be calculated as the following formula:

\begin{matrix} S (k) = S_{1} + (k - 1) T, (k \geq 1) . \end{matrix}

(2)

Note that the $k th$ transmission happens only when the first ( $k - 1$ ) times of transmission fail. On the other hand, small probability event may happen when the total N attempts fail, where N is the maximum number of allowable retransmissions for each hop. In this case, the packet would be dropped by the sender. Given the link quality, q, the conditional probability of the $k th$ transmission, $PR (k)$ , can be represented as follows:

\begin{matrix} PR (k) = \frac{{(1 - q)}^{k - 1} q}{1 - {(1 - q)}^{N}} . \end{matrix}

(3)

As a system parameter, N can be configured to trade off delivery ratio and energy cost. With a larger value of N, we can achieve a higher delivery ratio at the cost of more energy. In particular, we can confine N with a parameter δ which denotes the expected delivery ratio of one-hop transmission. With given δ, N should satisfy the following constraint:

\begin{matrix} \sum_{k = 1}^{N - 1} ‍ PR (k) \leq δ \leq \sum_{k = 1}^{N} ‍ PR (k) . \end{matrix}

(4)

Thus, the $ESL$ , for a packet to be successfully delivered can be calculated as

\begin{matrix} ESL = \sum_{k = 1}^{N} ‍ {S (k) PR (k)} . \end{matrix}

(5)

For candidates with multiple wake-up slots, the average waiting time of retransmission decreases since there is no necessary to wait for the whole period. Assuming that neighboring node j has n wake-up slots, that is, $Γ_{j} = {t_{1}, t_{2}, \dots, t_{n}}$ , the sleep latency of $k th$ transmission, $S (k)$ , can be approximated with

\begin{matrix} S (k) = {\begin{cases} | t_{m} - t_{0} | + \frac{T k}{n}, & m \neq 0, \\ | t_{n} - t_{0} | + T (\frac{k}{n} - 1), & m = 0 . \end{cases} \end{matrix}

(6)

Here, m is the reminder of k divided by n ( $1 \leq k \leq N$ ). Specially, if wake-up slots of forwarding candidate follow even-distribution, the average waiting time of data transmission is approximated to $T / n$ .

At last, suppose that source node ( $v_{s}$ ) send packets to the sink ( $v_{t}$ ) over L-hops path, $R^{s, t} = {v_{0}, v_{1}, \dots, v_{L}}$ , where $s = 0, t = L$ , and the expected end-to-end delay (EED) can be calculated as follows:

\begin{matrix} EED = \sum_{i = 1}^{L} ‍ ESL (i, i + 1) . \end{matrix}

(7)

Obviously, the E2E delay is also dependent on the length of routing path (L).

4.2. A Walkthrough for Expected Sleep Latency

In traditional always-awake networks, a sender can send its packets to next hop once data packets are ready to be sent. Ignoring network congestion and transmission collision, the E2E delay is proportional to the length of routing path. In this case, the shortest path routing is efficient for delay minimization. ETX has been proposed as a metric to find high throughput path in lossy wireless networks [13]. On the other hand, DESS is designed to reduce delivery delay by prioritizing the neighbor with earliest wake-up time [22].

We demonstrate the weakness of these existing routing algorithms by an example as shown in Figure 4, where node A is an always-awake node. Suppose that the wake-up time of its candidates $B_{1}$ , $B_{2}$ , and $B_{3}$ is 100, 50, and 25 and link qualities are 1, 0.8, and 0.4, respectively, we calculate the ESL according to the above metric for different routing policies. According to ETX, node A will select node $B_{1}$ (with the best link quality) to forward, and then sleep latency is 100. For DESS algorithm, node A intends to select node $B_{3}$ which has minimum waiting time among $B_{1}$ , $B_{2}$ , $B_{3}$ ; the delay value of first transmission is 25. Once failed (with a high probability of 60%), the delivery delay could be longer since node A needs to wait for a whole period ( $T = 100$ ) to obtain the chance of retransmission. Suppose that infinite retransmissions could be performed; the ESL values of successful delivery through three candidates $B_{1}$ , $B_{2}$ , and $B_{3}$ are 100, 75, and 175, respectively. In order to minimize delivery delay, data forwarding via neighbor $B_{2}$ might be the best choice in this example.

Figure 4

Example of routing strategies.

4.3. Delay-Driven Routing Algorithms

Based on the metric, we propose (i) a local-optimized routing algorithm by which each node select next hop to reduce one-hop sleep latency (referred to as ESL); (ii) a global-coordinated routing algorithm which can minimize the ESL from current sender to the sink node (referred to as MSL).

In ESL, we utilize the proposed metric in a way as the example explained in Section 4.2. As shown in Algorithm 1, the sender firstly evaluates the ESL value for each candidate according to Equation (5) and then selects neighbors with minimized ESL as the optimal forwarder [line 3–9]. Instead of building whole optimal forwarding path, the ESL algorithm is completely localized and distributed.

Algorithm 1: ESL algorithm at node i.

Input: Forwarding Set, $F S (i)$

Output: the optimal forwarder, $O p t F w d e r$

(1) $\min E S L \leftarrow \infty$

(2) $O p t F w d e r \leftarrow - 1$

(3) for $j \leftarrow 1$ to n do

(4) calculate $E S L$ from node i to candidate

$B_{j}$ , ( $B_{j} \in F S (i)$ ) using (5);

(5) if ESL $(i, j) < \min E S L$ then

(6) $\min E S L \leftarrow E S L (i, j)$

(7) $O p t F w d e r \leftarrow B_{j}$

(8) end if

(9) end for

(10) return $O p t F w d e r$

In MSL, we propose routing algorithm to find optimal path with minimized end-to-end delay from each node to the sink. The expected E2E delay from node i at level h to the sink, denoted by ${EED}_{i} (h)$ , is the ESL for the packets sent by node i and received by the sink node over multihop path. Formally, we can evaluate the minimized EED in a recursive way:

\begin{matrix} {EED}_{i} (h) = \min_{j \in FS (i)} ({EED}_{j} (h - 1) + ESL (i, j)) . \end{matrix}

(8)

Note that the above calculation of E2E delay can be started from the sink and then propagated towards the rest of network. For sink node, its ESL is zero since no further data forwarding is necessary once the packet arrives at the sink node. The routing algorithm for each node except the sink node is shown in Algorithm 2. Similar to Dijkstra's algorithm (but use sink as destination), the algorithm begins with the broadcasting of EED value by sink node. At first, each node sets its minimized EED to ∞ [line 1]. After receiving the broadcasted values from neighbors, each node starts to compute minimized EEDs based on Equation (8). With multiple iterations, the process converges at a node until it receives no more information from all neighbors [see line 2–12]. Finally, the sender selects potential candidate with minimized EED as its next hop.

Algorithm 2: MSL algorithm at node i.

Input: Forwarding Set, $F S (i)$

Input: Minimized EED from candidate $B_{j}$ at level $h - 1$ to

the sink, $E E D_{j} (h - 1)$

Output: the optimal forwarder, $O p t F w d e r$

(1) $\min E E D_{i} (h) \leftarrow \infty$

(2) $O p t F w d e r \leftarrow - 1$

(3) for $j \leftarrow 1$ to n do

(4) calculate ESL from node i to candidate

$B_{j} (B_{j} \in F S)$ using (5);

(5) if $E E D_{j} (h - 1) \neq \infty$ then

(6) $d \leftarrow (E E D_{j} (h - 1) + E S L (i, j))$

(7) end if

(8) if $d < \min E E D_{i} (h)$ then

(9) $\min E E D_{i} (h) \leftarrow d$

(10) $O p t F w d e r \leftarrow B_{j}$

(11) end if

(12) end for

(13) Broadcast the minimized value, $\min E E D_{i} (h)$ ;

(14) return $O p t F w d e r$

In fact, we can build a spanning tree with minimized E2E sleep latency, with which each source can forward data packets via its parent to minimize delivery delay.

5. Extensive Simulation

In this section, we evaluate and compare performance of proposed routing algorithms with extensive simulations.

5.1. Baseline of Routing Algorithms

To verify the effectiveness of our design, we compare the proposed algorithms with the state-of-the-art derived in wireless networks.

(i)

Geographic-based routing algorithm [12] (termed PRRxD): the product of the packet reception ratio (PRR) and the distance traversed towards destination (D) is selected as the optimal forwarding metric in order to improve energy efficiency.

(ii)

ETX-based routing algorithm [13] (termed ETX): the ETX can be represented as the reciprocal of link quality. Note that multiple neighbors may have the same link quality in dense networks, and the farthest one among them is selected.

(iii)

DESS-based algorithm [22] (termed DESS): original DESS is proposed based on perfect channel model. To deliver packets successfully, we assume that retransmissions can be performed via the wake-up earliest candidates. If one or more neighbors wake up at the same time, the one with better link quality is chosen.

5.2. Simulation Setup and Performance Metrics

Without specification, 400 nodes are randomly deployed in a $200 m \times 200 m$ network, where the source and sink node are located in the opposite of sensor area. The link qualities between node pairs are set according to channel model proposed in [27], where radio parameters strictly follow Chipcon CC2420 hardware specification [28]. Each experiment is repeated 10 times with different random seeds, node deployments, and working schedules. Simulation results are obtained with the average value of 100 source-to-sink data transmissions.

In the simulation, we measure delivery delay as period of time from a message being sent out by the source until it reaches the sink node. Since energy consumed by data reception for most wireless transmitter is close to that of idle state [28], energy cost is evaluated by the number of transmissions. For all experiments, the expected delivery ratio of one-hop (δ) is set to 0.8.

5.3. Performance Comparison

5.3.1. Different Network Sizes

We evaluate the performance of all algorithms in different network sizes. For side length from 100 to 300, the number of nodes is set from 100 to 900 in order to keep the same network density.

Figure 5(a) shows that the E2E delay increases as the size length of network. In particular, MSL reduces delay by a factor of 6 times compared with ETX. Even for DESS, our algorithm can obtain a factor of 2 times delay reduction. Note that ESL is suboptimal in delivery delay but still can obtain a large delay gain compared with other algorithms. For example, the delivery delay of ESL is 50% less than that of DESS when the size length is 150. Energy cost, quantified by number of transmissions, is plotted in Figure 5(b). Since PRRxD is proposed to optimize energy efficiency, it has the lowest energy consumption among all algorithms. Based on the global optimization, MSL is also energy efficient compared with ETX and DESS. On the contrary, ESL consume a little more energy because the average length of routing path is longer compared with other algorithms.

Figure 5

Network length.

5.3.2. Different Network Densities

To evaluate the performance in different network densities, 200~800 nodes are randomly deployed on a $200 m \times 200 m$ field. Figure 6(a) shows that the EEDs in all algorithms decrease as network density. Again, both MSL and ESL can reduce delivery delay compared with other algorithms. Figure 6(b) shows that DESS and ESL consume more energy and the change of network densities has little impact on them. The energy efficiency of ETX is monotonously increasing since the average link quality can be improved with more neighbors. For MSL and PRRxD, there is a turning point near 600 nodes, from which the energy dissipation keeps unchanged. In other words, more neighbors has no influence on the energy consumption.

Figure 6

Network density.

5.3.3. Different Duty Cycles

We change working period of nodes (T) from 100 to 500 and obtain the corresponding duty-cycle from 1% to 0.2%. Figure 7(a) demonstrates that delivery delay is monotonously decreasing with duty cycles for all algorithms. For example, the E2E delay for ESL decreases from 890 to 128, while the duty cycle increases from 0.2% to 1%. On the other hand, the number of transmissions keeps stable for all algorithms as shown in Figure 7(b). Note that duty-cycled operation saves energy consumed by idle listening instead of data transmission. The number of transmissions for PRRxD and MSL is smaller than that of other algorithms. According to our investigation, both of them prefer to send packets along reliable routing path.

Figure 7

Duty cycles.

5.3.4. Impact of Link Quality

In this section, we investigate the impact of link quality on the network performance. To set the given link qualities, we first used CC2420 radio specification and delay model derived in [27] to build the neighbor table for each sensor node and then generated the pairwise link quality according to the simulation settings.

Figure 8 shows that both E2E delay and energy consumption decreases as the average link quality. It is because the waiting time of retransmissions is reduced when the average link quality increases. In particular, the average delivery delay for DESS, ESL, and MSL is converging to the same point when the link quality approximates to perfection. In this case, all of them tend to select the earliest wake-up neighbors as the optimal forwarder. On the other hand, MSL instead of PRRxD has the lowest energy cost since the prior tends to select short path with better link quality. The energy consumption for ETX, DESS, and ESL is very similar if we take the path length and link quality into consideration. At last, Figure 8(c) shows that the delivery ratio from source nodes to the sink node for all schemes increases when the average link quality grows. Also, MSL has the best delivery ratio among them.

Figure 8

Impact of link quality.

5.4. Investigations

To investigate the rationale behind our design, we recorded average number of hops and delivery delay per hop taken along the routing path in Tables 1 and 2, respectively.

Table 1

Investigation of path length.

Side length	Average path length
Side length	PRRxD	ESL	ETX	DESS	MSL
100	5.8	9.7	9.7	9.3	6.7
150	8.2	15.8	14.1	13	9.6
200	10.8	22.5	17.3	16.1	12.7
250	13.4	26	23.4	21.6	14.6
300	16.22	31.3	25.9	27.2	18.2

Table 2

Investigation of delay per hop.

Working period (T)	Average delay per hop
Working period (T)	PRRxD	ESL	ETX	DESS	MSL
100	55	10	48	19	10
200	108	22	94	54	22
300	142	23	145	56	30
400	208	35	189	97	42
500	255	45	245	116	50

Table 1 shows that PRRxD and MSL have shorter routing path than the other algorithms. For example, the average path length for PRRxD and MSL is 5.8 and 6.7, while the side length of network is 100. On the other hand, it takes more than 9 hops for other algorithms to deliver the packets. In particular, ESL has the longest forwarding path and consumes more energy.

As shown in Table 2, both MSL and ESL can minimize the average sleep latency per hop. For example, the sleep latencies per hop for them are both 10 when the working period is 100, while the value is as large as 55 for PRRxD. Consequently, ESL and MSL outperform other algorithms in delivery delay. Taking both the length and single-hop delay into consideration, MSL can provide the best delivery performance for low-duty-cycle sensor networks.

6. Testbed Implementation

In this section, we implement ETX, DESS, and ESL on the TinyOS/Mote platform with micaZ nodes. The modules of algorithm include initialization, link quality measurement, working schedule sharing, metric evaluation, and data forwarding module.

6.1. Implementation

6.1.1. Initialization

At the boot-up phase, each node keeps awake and begins to exchange control messages in order to discover its neighbors. Next, initiated by the sink node which broadcasts beacon packets with hops-count equaling zero, nodes which receive such packets select the minimum hop count and add one as their own hop count and then broadcast packets to neighbors except the sender. This phase works similarly to breadth-first search algorithm until convergence is achieved.

6.1.2. Link Quality Measurement

Each node needs to know link quality with its neighboring nodes in order to calculate metrics. To measure link quality, each node sends a number of packets to each of its neighbors and utilizes acknowledge from MAC layer to evaluate the pairwise link quality. To reduce communication overhead, the four-bit link estimator can be used for such low-power sensor networks [13].

6.1.3. Working Schedule Sharing

Each node sets up its working schedule individually and then share with its neighbors. In our implementation, we randomly generate working schedules on a base station and then broadcast them by sink node.

6.1.4. Metric Evaluation

Evaluation component is the kernel of our design, where each individual node executes the given algorithm with different metric. For MSL algorithm, Algorithm 2 is performed, while the node receives updated information from its neighboring nodes. For other local algorithms, such as ESL, only neighbor information is needed for the evaluation of routing metric. After this process, each node can find the optimal forwarder via which the packet can be delivered to the sink.

6.1.5. Data Forwarding

Data forwarding component can be used by all routing protocols. When the source node has packets ready to send, it can forward them via the selected candidate. If failure happens, the node attempts to transmit again until the delivery succeeds or the packet is discarded when the maximum allowable number of retransmissions has been performed.

6.2. Performance Validation

In the experiments, 30 micaZ nodes are uniformly deployed along with the walkway in our office building. We adjust the transmission power of these nodes so that they form a maximum 7-hop network. At the startup, each node performs initialization, measures link quality, and receives working schedule. Next, they find the optimal forwarder with given routing algorithm. To minimize the effect of temporal link quality, the farthest nodes (7-hop away from the sink node) send 100 packets to the sink with different algorithms in turn during the data forwarding phase.

Figure 9(a) reports the E2E delay for all three algorithms. In the experiment, the working period of nodes is set to 100τ; that is, the node operates at 1% duty cycle. Each time slot is set to $20$ ms, and then the whole working period takes up 2 s. From the figure, we can see that more than 65% of packets can be delivered within three working periods for ESL, while the ratios for ETX and DESS are 52% and 49%, respectively. This is because ESL algorithm selects the optimal forwarder to reduce the ESL.

Figure 9

Performance comparison.

Figure 9(b) plots cumulative distribution of the number of transmissions from the source nodes to the sink, which shows that our algorithm takes a little more energy cost than ETX but less than DESS. For example, with 9 transmissions, our algorithm can deliver 93% of packets, while ETX can achieve 95% of packet transmissions. As we discussed, both ESL and DESS send packets via certain bad links. However, we found that the length of longest path for DESS is 14, while the length for ESL is 11, which verifies that ESL can make a better tradeoff between link quality and delay gain.

7. Conclusion and Future Work

This paper studies the routing algorithms for the optimization of delivery delay in low-duty-cycle sensor networks. We present a new routing metric, which takes both link quality and working schedule of sensor nodes into consideration. Based on the metric, delay-driven routing algorithms are proposed to reduce source-to-sink delivery delay. Both testbed experiments and large-scale simulations show that our algorithm can optimize sleep latency compared with other routing algorithms.

In future work, we will focus on the following aspects. First, we are aware that more experimental results from extensive testbed systems deployed in different scenarios are needed to further verify our design. Second, instead of single-parent forwarding delivery, we plan to compare our design with multiparent forwarding scheme proposed in [17]. Third, we also want to explore the performance of delay-driven routing algorithms in energy-harvesting sensor network [29], in which the energy supply is highly dynamic and environment-dependent. At last, we plan to study the impact of transmission power on the sleep latency in low-duty-cycle sensor networks.

Footnotes

Acknowledgments

The author would like to thank the anonymous reviewers for their helpful suggestions that improved this work. This work was supported by the Fundamental Research Funds for the Central Universities of China under Grant no. 21610318 and in part by NSFC under Grant no. 61070165.

References

Cerpa

Elson

Estrin

Girod

Hamilton

Zhao

Habitat monitoring: application driver for wireless communications technology

ACM SIGCOMM Computer Communication Review 2001 31 2, supplement 20 41

10.1145/844193.844196

2-s2.0-0034819265

Vicaire

Cao

Yan

Zhou

Luo

Stoleru

Stankovic

J. A.

Abdelzaher

T. F.

Achieving long-term surveillance in VigilNet

ACM Transactions on Sensor Networks 2009 5 1, article 9 39

2-s2.0-60449117536

10.1145/1464420.1464429

Liu

Zhao

Tang

Dai

Canopy closure estimates with GreenOrbs: sustainable sensing in the forest

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

November 2009

99 112

2-s2.0-74549201690

10.1145/1644038.1644049

Dyo

Ellwood

S. A.

MacDonald

D. W.

Markham

Mascolo

Pásztor

Scellato

Trigoni

Wohlers

Yousef

Evolution and sustainability of a wildlife monitoring sensor network

Proceedings of the 8th ACM International Conference on Embedded Networked Sensor Systems (SenSys ′10)

November 2010

127 140

2-s2.0-78650901972

10.1145/1869983.1869997

Werner-Allen

Lorincz

Welsh

Marcillo

Johnson

Ruiz

Lees

Welsh

Deploying a wireless sensor network on an active volcano

IEEE Internet Computing 2006 10 2 18 25

2-s2.0-33645115901

10.1109/MIC.2006.26

Ramanathan

Schoellhammer

Kohler

Whitehouse

Harmon

Estrin

Suelo: human-assisted sensing for exploratory soil monitoring studies

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

November 2009

197 210

2-s2.0-74549182228

10.1145/1644038.1644058

Chen

Sun

Coverage and connectivity in duty-cycled wireless sensor network for event monitoring

IEEE Transactions on Parallel and Distributed Systems 2012 23 3 475 482

2-s2.0-84855720973

10.1109/TPDS.2011.191

Cao

Abdelzaher

Stankovic

Towards optimal sleep scheduling in sensor networks for rare-event detection

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN ′05)

April 2005

20 27

2-s2.0-33744944530

Hsin

C. F.

Liu

Randomly duty-cycled wireless sensor networks: dynamics of coverage

IEEE Transactions on Wireless Communications 2006 5 11 3182 3192

2-s2.0-33846231048

10.1109/TWC.2006.04861

10.

Paruchuri

Basavaraju

Durresi

Kannan

Iyengar

S. S.

Random asynchronous wakeup protocol for sensor networks

Proceedings of the 1st International Conference on Broadband Networks (BroadNets ′04)

October 2004

710 717

2-s2.0-19544389635

10.1109/BROADNETS.2004.71

11.

Karp

Kung

H. T.

GPSR: greedy perimeter stateless routing for wireless networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM ′00)

August 2000

ACM

243 254

2-s2.0-0034547115

12.

Zamalloa

M. Z.

Seada

Krishnamachari

Helmy

Efficient geographic routing over lossy links in wireless sensor networks

ACM Transactions on Sensor Networks 2008 4 3, article 12

2-s2.0-44849102999

10.1145/1362542.1362543

13.

de Couto

D. S. J.

Aguayo

Bicket

Morris

A high-throughput path metric for multi-hop wireless routing

Wireless Networks 2005 11 4 419 434

2-s2.0-23044444929

10.1007/s11276-005-1766-z

14.

Bounding communication delay in energy harvesting sensor networks

Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS ′10)

June 2010

Genoa, Italy

837 847

2-s2.0-77955883748

10.1109/ICDCS.2010.41

15.

Lin

Spatiotemporal delay control for low-duty-cycle sensor networks

Proceedings of the 30th IEEE Real-Time Systems Symposium (RTSS ′09)

December 2009

Washington, DC, USA

127 137

2-s2.0-77649285524

10.1109/RTSS.2009.12

16.

Keshavarzian

Lee

Venkatraman

Wakeup scheduling in wireless sensor networks

Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′06)

May 2006

322 333

2-s2.0-33748034055

17.

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

18.

Liu

Song

Cao

Routing in intermittently connected sensor networks

Proceedings of the IEEE International Conference on Network Protocols (ICNP ′08)

October 2008

Orlando, Fla, USA

278 287

2-s2.0-67249165295

10.1109/ICNP.2008.4697046

19.

Lai

Ravindran

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

Proceedings of the IEEE INFOCOM 2010

March 2010

San Diego, Calif, USA

1 9

2-s2.0-77953300083

10.1109/INFCOM.2010.5461987

20.

Landsiedel

Ghadimi

Duquennoy

Johansson

Low power, low delay: opportunistic routing meets duty cycling

Proceedings of the 11th ACM/IEEE Conference on Information Processing in Sensing Networks (IPSN ′12)

April 2012

185 196

2-s2.0-84860513866

10.1145/2185677.2185731

21.

Ghadimi

Landsiedel

Soldati

Johansson

A metric for opportunistic routing in duty cycled wireless sensor networks

Proceedings of the 9th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks(SECON ′12)

June 2012

Seoul, Republic of Korea

335 343

22.

Sadagopan

Krishnamachari

Goel

Delay efficient sleep scheduling in wireless sensor networks

Proceedings of the IEEE INFOCOM 2005

March 2005

2470 2481

2-s2.0-25644435716

23.

Yang

Vaidya

N. H.

A wakeup scheme for sensor networks: achieving balance between energy saving and end-to-end delay

Proceedings of the RTAS 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS ′04)

May 2004

19 26

2-s2.0-7744236816

24.

Krishnamachari

Prasanna

V. K.

Energy-latency tradeoffs for data gathering in wireless sensor networks

Proceedings of the 23rd AnnualJoint Conference of the IEEE Computer and Communications Societies (INFOCOM ′04)

March 2004

244 255

2-s2.0-8344239614

25.

Sundararaman

Buy

Kshemkalyani

A. D.

Clock synchronization for wireless sensor networks: a survey

Ad Hoc Networks 2005 3 3 281 323

2-s2.0-13944269967

10.1016/j.adhoc.2005.01.002

26.

Woo

Tong

Culler

Taming the underlying challenges of reliable multihop routing in sensor networks

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys ′03)

November 2003

14 27

2-s2.0-18844378578

27.

Zuniga

Krishnamachari

Analyzing the transitional region in low power wireless links

Proceedings of the 1st Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (IEEE SECON ′04)

October 2004

517 526

2-s2.0-20344378689

28.

Chipcon CC2420 Data Sheet, http://www.ti.com/

29.

Kansal

Hsu

Zahedi

Srivastava

M. B.

Power management in energy harvesting sensor networks

ACM Transaction on Embedded Computing Systems 2007 6 4, article 32

10.1145/1274858.1274870