Sage Journals: Discover world-class research

Abstract

Wireless sensor networks are composed of low-energy, small-size, and low-range unattended sensor nodes. Recently, it has been observed that by periodically turning on and off the sensing and communication capabilities of sensor nodes, we can significantly reduce the active time and thus prolong network lifetime. However, this duty cycling may result in high network latency, routing overhead, and neighbor discovery delays due to asynchronous sleep and wake-up scheduling. These limitations call for a countermeasure for duty-cycled wireless sensor networks which should minimize routing information, routing traffic load, and energy consumption. In this article, we propose a lightweight non-increasing delivery-latency interval routing referred as LNDIR. This scheme can discover minimum latency routes at each non-increasing delivery-latency interval instead of each time slot. Simulation experiments demonstrated the validity of this novel approach in minimizing routing information stored at each sensor. Furthermore, this novel routing can also guarantee the minimum delivery latency from each source to the sink. Performance improvements of up to 12-fold and 11-fold are observed in terms of routing traffic load reduction and energy efficiency, respectively, as compared to existing schemes.

Keywords

Routing information sleep latency non-increasing delivery-latency interval duty cycle wireless sensor networks

Introduction

Wireless sensor networks (WSNs) are composed of a large number of unattended sensor nodes. Generally, WSNs are deployed in hostile, hazardous, and inaccessible environments, for example, health, military, home,¹ target tracking,² water monitoring,³ and surveillance.⁴ Sensor nodes are often powered by batteries that may not be recharged. Moreover, many sensor network applications are meant to last for a long time. An efficient solution to meet this end is to densely deploy sensor nodes and scheduling to sleep and wake-up duty cycling.^5–10 This helps sensor nodes to reduce communication overhead and sensing duty cycles.

The scheduling scheme significantly decreases the number of active nodes, thereby prolonging network lifetime. However, decreasing the number of active nodes may cause the network to be intermittently connected. In sensor networks with such a scheduling mechanism, traditional routing protocols, for example, shortest path routing, may not be able to find routes with low latency. That is a mandatory requirement in many delay sensitive applications, such as, military surveillance, security monitoring, and forest alarms.

The problem of finding optimal routes in terms of delivery, latency, and energy consumption in duty-cycled WSNs has sparked interest as seen in the literature.^11–20 However, most of the previous work focused on finding optimal routes at each time slot in a duty cycle, eventually resulting in high routing overhead, especially when the number of time slots is huge. This motivates us to present a new scheme to overcome these challenges.

In this article, we employ the concept of non-increasing delivery-latency interval (NDI), a non-extendable time interval of a node in which delivery latency decreases steadily or remains the same. Furthermore, we propose an NDI-based routing scheme that finds minimum latency routes from sensors to the sink at each NDI instead of at each time slot, therefore guaranteeing minimum delivery-latency routes. This scheme is lightweight due to small routing tables on sensor nodes, reduced traffic overheads, decreased delays, and energy efficiency. The main contributions of our work are as follows:

Minimizing the routing information (i.e. routing table size) stored at each sensor and thus reducing the storage cost.

Significantly reducing the routing traffic load which could support in increasing network quality of service (QoS).

Conserving a large amount of energy per node on routing process to extend network lifetime.

The remainder of this article is organized as follows: “Related work” discusses the related literature review. “Network model and problem formulation” presents a network model, assumptions, and definitions. “Proposed NDI-based routing scheme” describes the proposed scheme. Section “Performance evaluation” gives the simulation environment and results. Finally, conclusions and future directions are outlined at the end of this article.

Related work

Sleep and wake-up scheduling has been exploited to conserve energy⁶ which can prolong network lifetime.²¹ The scheduling scheme significantly decreases the number of active nodes for a given time unit, thereby prolonging network lifetime. The decrease in the number of active nodes may cause the network to be intermittently connected. In such a network, traditional routing protocols may not be able to find minimum latency routes. The problem of finding optimal routes in terms of delivery latency and energy consumption in duty-cycled WSNs has been studied.^{11–20,22,23,24} The majority of works find optimal routes at each time slot in a duty cycle. That results in high routing overhead, especially when the number of time slots is large. This motivates the need for new scheme to overcome these limitations.

Beraldi et al.¹¹ addressed the lowest latency path problem, that is, the characteristics of a path with minimum delay that connects a source node to the sink under random duty cycling nodes. Furthermore, they proposed a forwarding protocol based on biased random walks. The sensor nodes just require local information about neighbors and their next active period to make forwarding decisions. This technique is called lukewarm potato forwarding. Their analytical model and simulation experiments showed that it is possible to reduce path latency without significantly increasing the number of transmissions for message delivery to the destination. Specifically, deviating from the shortest path requires additional transmissions, and hence, higher energy consumption. This shows that reducing latency at the cost of an increased number of transactions is not an energy-efficient solution.

Gu and He¹² presented the concept of dynamic switching-based reliable forwarding (DSRF) that optimizes: (1) expected data delivery ratio, (2) expected communication delay, or (3) expected energy consumption for low-duty-cycled WSNs. DSRF was designed for networks with possibly unreliable communication links and predetermined node communication schedules. It focuses on energy and delay reduction by reducing the number of transmissions. This work presents a wake-up scheduling algorithm with a low computational cost. However, it does not reduce the routing table size and guarantee minimum latency paths.

Gu et al.¹³ presented three different approaches to provide a real-time guarantee of communication delay. First, they presented a method for increasing the duty cycle at an individual node. Second, they described a scheme of placement of the sink nodes. Third, they proposed a hybrid approach that showed better balance between cost and efficiency on bounding communication delay. The proposed scheme is global optimal in terms of minimizing the energy consumption for bounding pairwise end-to-end delay. However, this scheme does not reduce routing table size and energy consumption.

Research work¹⁵ addressed the important problem of minimizing average communication latency for the active flows while providing energy efficiency in WSNs. The authors formulated a joint scheduling and routing problem aimed at finding the schedules and routes for current active flows with minimum average latency. By constructing a novel delay graph, the problem can be solved optimally by employing the $M$ node-disjoint paths algorithm under the frequency-division multiple access (FDMA) channel model. They further presented extensions of the algorithm¹⁶ to cater to dynamic traffic and topology changes in WSNs. Although schemes successfully saved energy and delay, it does not guarantee minimum delay paths and reduced routing table size.

Sun and Xu¹⁷ is another closely related work. It proposed and evaluated a delay-aware routing scheme for low-duty-cycled sensor networks. The proposed algorithm organizes the network into a layered structure. The sensor, with packets ready to be sent, dynamically determines a forwarder from multiple potential next-hop sensors in terms of timeliness. This delay-aware scheme is limited since it cannot minimize routing table size and guarantee minimum latency routing from multiple sources to a single sink. It can be found that these related works address the target problem partially while a solution dealing with the aforementioned limitation is required.

Galzarano et al.²⁵ investigated the influence of the number of deployed nodes on such major network performance metrics as energy consumption, delay, and traffic congestion. In contrast to the commonly used network density, they introduced node concentration and evaluated performance of one of the most popular protocols, ad hoc on-demand distance vector routing (AODV), with respect to this new parameter. Moreover, authors proposed an improvement of AODV, which is based on a node concentration-driving gossiping approach.

Network model and problem formulation

Network model and assumptions

A sensor network is composed of static, homogeneous, and randomly deployed sensor nodes. Each sensor consists of a limited and fixed amount of energy and range. Sensor network lifetime is divided into rounds of equal duration $(T_{r})$ . As shown in Figure 1, in a round, a node $A$ has a working period $(T_{w})$ starting at $S^{A}$ and ending at $E^{A}$ . A sleeping period is inactive time. Each round is divided into time slots. A time slot is an atomic period for sleeping/working scheduling. When a node is in the working period, it can sense the vicinity in order to receive/transmit. Otherwise, it turns off all functions except a timer to wake-up. A node can wake-up to transmit a packet at any time. A node can transmit or receive only one packet in one time slot.

Figure 1.

Time round structure where $T_{w}$ denotes the working period; $T_{r}$ denotes the round; $S^{A}$ is the starting time of the working period of node $A$ ; and $E^{A}$ is the ending time of the working period of node $A$ .

This work makes the following assumptions:

A simplex bidirectional communication is assumed, that is, node $A$ is capable of transmitting to another node $B$ and node $B$ can receive from node $A$ .

The network time is locally synchronized so that a node knows when it should send a packet to its neighbor given a working schedule.^12–17 Time synchronization of local clocks can be achieved using an energy-efficient time synchronization protocol (ETSP).²⁶

Thus, for communications between sensors, we assume that the network has a disk communication model with a given communication range.^9–11

For the sake of simplicity, we assume there is only one sink in the network.^12–14 All the source nodes report sensing data toward the sink.

Each node has its own working schedule by which the node knows when to wake up and work. We do not consider the case where nodes invite their neighbors to wake up out of their working schedule.^12–17

Sensor nodes know the working schedules of their one-hop neighbors.²⁷ This can be achieved using a setup phase in which all nodes are awake and every node broadcasts its working schedule to its one-hop neighbors.

Problem formulation

Table 1 shows the minimum latency routing table of node $A$ with the destination node $S$ in Figure 2. As the number of time slots in the working interval (or period alternatively) of a node increases, the size of the routing table becomes large. Consequently, each sensor needs more memory to store its routing table and there is more routing traffic load in the network and more energy consumed in the routing process. Our target is to minimize the routing information stored at each sensor and significantly reduce the routing traffic load and energy consumed in the routing process, while guaranteeing the minimum delivery latency from each sensor to the sink.

Table 1.

Minimum latency routing table for node $A$ .

Time slot	Delivery latency	Next hop
17	3	$B$
18	3	$B$
19	3	$B$
20	4	$B$
1	3	$B$
2	3	$B$
3	3	$B$
4	3	$B$

Figure 2.

An example for the proposed scheme; dark gray and white rectangles denote working and sleeping periods, respectively.

Basic definitions and lemmas

Before presenting definitions and lemmas, we summarize the notation used in this article in Table 2. The basic definitions, examples, and lemmas help in understanding the proposed method. We use these properties later in driving the three algorithms used in our approach.

Table 2.

Descriptions of notation.

Notation	Description
$R^{A}$	One of the routes from node $A$ to the sink node $S$
$R^{A, B}$	The route from node $A$ via a next-hop node $B$ to the sink node $S$
$N^{A}$	Set of one-hop neighbors of node $A$
$S^{A}$	Start time of the working period of node $A$
$E^{A}$	End time of the working period of node $A$
$T_{w}$	Length of the working period of a node
$T_{r}$	Round duration
$T (s, len)$	An interval of len time slots starting from $s$
$LD L^{A \to B} (t)$	Link delivery latency of the link $A \to B$ at time $t$
$D L^{A} (t)$	Delivery latency from $A$ to $S$ at time $t$
$D L^{A, B} (t)$	Delivery latency from $A$ to $S$ via a next-hop node $B$ at time $t$
$NLD I^{A \to B}$	Non-increasing link delivery-latency interval of the link $A \to B$
$s_{i}^{A \to B}$	Start time of the $i th$ $NLD I^{A \to B}$
$e_{i}^{A \to B}$	End time of the $i th$ $NLD I^{A \to B}$
$ND I^{A, B}$	Non-increasing delivery-latency interval of routes from node $A$ to $S$ via $B$
$s_{i}^{A, B}$	Start time of the $i th$ $ND I^{A, B}$
$e_{i}^{A, B}$	End time of the $i th$ $ND I^{A, B}$
$ND I^{A}$	Non-increasing delivery-latency interval of routes from node $A$ to $S$
$s_{i}^{A}$	Start time of the $i th$ $ND I^{A}$
$e_{i}^{A}$	End time of the $i th$ $ND I^{A}$
AT	Anchor time is start time of an NDI
ATS	Set of anchor times of neighbors
$R T^{A}$	Routing table of node $A$
$R T^{A, B}$	Routing table of node $A$ with a next-hop node $B$
$RA P^{A}$	Route advertising packet of node $A$

Note 1

$E^{A} = (S^{A} + T_{w} - 1) \mod T_{r}$ .

Definition 1

$T (s, len)$ : an interval of len time slots starting from $s$

T (s, len) = {\begin{matrix} [s, s + len - 1], if s + len - 1 \leq T_{r} \\ [s, T_{r}] \cup [1, (s + len - 1) \mod T_{r}], if s + len - 1 > T_{r} \end{matrix}

Example 1

As shown in Figure 2, we have $T (17, 3) = [17, 19]$ and $T (17, 6) = [17, 20] \cup [1, 2]$ .

Definition 2

If node $X$ is a neighbor node of node Y, we have a link from node $X$ to node Y, denoted by $X \to Y$ .

Definition 3

The interval from time $t$ when a packet is available for sending by node $X$ to the time when the packet is successfully sent out to a neighboring, node Y, is called the delivery latency of the link $X \to Y$ at time $t$ , $LD L^{X \to Y} (t)$

LD L^{X \to Y} (t) = {\begin{matrix} 1, & if t \in T (S^{Y}, T_{w}) \\ S^{Y} - t + 1, & if t \notin T (S^{Y}, T_{w}) and t < S^{Y} \\ S^{Y} + T_{r} - t + 1, & if t \notin T (S^{Y}, T_{w}) and t > E^{Y} \end{matrix}

Example 2

As shown in Figure 2, $LD L^{A \to B} (18) = 1$ , $LD L^{A \to B} (4) = 15 - 4 + 1 = 12$ , and $LD L^{A \to E} (17) = 3 + 20 - 17 + 1 = 7$ .

Note 2

The minimum delivery latency of a link $A \to B$ is 1 time slot.

Definition 4

Delivery latency of node $X$ at time $t$ , $D L^{X} (t)$ , is the minimum latency over all the routes from node $X$ to the sink node $S$ . Note that $D L^{S} (t) = 0$ .

Property 1

$D L^{X} (t) = \min_{Y \in N^{X}} {LD L^{X \to Y} (t) + D L^{Y} (t + LD L^{X \to Y} (t))}$ .

Note 3

Let $R^{X}$ be the shortest route from node $X$ to the sink node $S$ and $l$ be the number of links (hops) of $R^{X}$ . Then, the minimum delivery latency of $R^{X}$ is $l$ time slots.

Definition 5

$D L^{X, Y} (t)$ is the minimum latency of all the routes, which contain link $X \to Y$ , from node $X$ to the sink node $S$ at time $t$ .

Definition 6

Given a link $X \to Y$ . A non-increasing link delivery-latency interval, $NLD I^{\to Y}$ , is a non-extendable interval of time in which $LD L^{X \to Y}$ decreases steadily or equals to 1, also see example in Figure 3(a) for link $A \to B$ .

Figure 3.

An illustration of basic definitions and lemma 1: (a) an illustration of NLDI, (b) NLDI^A^→ B, (c) NLDI^A^→ E, (d), (e) link A → B contains one NLDI, (f) link A → B contains two NLDI, (g) NDI^A,B, (h) NDI^A,E, and (i) NDI^A.

Formally, $T (s, len)$ , an interval inside the working period of node $X$ , is called an $NLD I^{X \to Y}$ if the following conditions hold:

For any $t \in T (s, len)$ , $LD L^{X \to Y} (t) = \max {LD L^{X \to Y} (s) - dif (s, t), 1}$ , where

$dif (s, t) = {\begin{matrix} t - s, & if t \geq s \\ t + T_{r} - s, & if t < s \end{matrix}$

$LD L^{X \to Y} (s) \neq LD L^{X \to Y} (s - 1) - 1$ , $LD L^{X \to Y} (s) \neq LD L^{X \to Y} (s - 1)$ .

$LD L^{X \to Y} (e + 1) \neq LD L^{X \to Y} (e) - 1$ , $LD L^{X \to Y} (e) \neq LD L^{X \to Y} (e + 1)$ , where $e = (s + len - 1) \mod T_{r}$ .

Condition (1) infers that link delivery latency decreases steadily or equals to 1; (2) and (3) mean $T (s, len)$ cannot be extended to the left or to the right, respectively.

Example 3

As shown in Figure 3(b) and (c), $A \to B$ has two $NLD I^{A \to B}$ : $T (17, 6)$ and $T (3, 2)$ ; $A \to E$ has one $NLD I^{A \to E}$ : $T (17, 8)$ .

Lemma 1

Given a link $X \to Y$ . The working period, $T (S^{X}, T_{w})$ , of node $X$ contains two $NLD I^{X \to Y}$ if $E^{Y}$ belongs to this interval. Otherwise, $T (S^{X}, T_{w})$ contains one $NLD I^{X \to Y}$ .

Case 1

Assume $E^{Y} \notin T (S^{X}, T_{w})$ .

Without loss of generality, we can assume $S^{X} = 1$ . There are two possible cases shown in Figure 3(d) and (e). As shown in Figure 3(d) (note nodes A and B cannot communicate), for $S^{X} \leq t < E^{X}$ we have the following:

$LD L^{X \to Y} (t) = S^{Y} - t + 1$ .

$LD L^{X \to Y} (t + 1) = S^{Y} - (t + 1) + 1 = (T_{r} + S^{Y} - t + 1) - 1 = LD L^{X \to Y} (t) - 1$ .

Based on the definition of an $NLD I^{X \to Y}$ , $T (S^{X}, T_{w})$ is a valid $NLD I^{X \to Y}$ . The proof is similar for the case in Figure 3(e).

Case 2

Assume $E^{Y} \in T (S^{X}, T_{w})$ . This is equivalent to

{\begin{matrix} S^{X} \leq E^{Y} < E^{X}, if S^{X} \leq E^{X} \\ 1 \leq E^{Y} < E^{X} or S^{X} \leq E^{Y} \leq T_{r}, if S^{X} > E^{X} \end{matrix}

Without loss of generality, we can assume $S^{Y} = 1$ . One possible case is shown in Figure 3(f). We have

LD L^{X \to Y} (E^{Y}) = 1

(1)

\begin{matrix} LD L^{X \to Y} (E^{Y} + 1) & = (T_{r} + S^{Y}) - (E^{Y} + 1) + 1 \\ = T_{r} + S^{Y} - E^{Y} \\ = T_{r} - (E^{Y} - S^{Y}) \\ = T_{r} - (T_{w} - 1) \\ = T_{r} - T_{w} + 1 \end{matrix}

(2)

Since $E^{Y} < E^{X}$ (assumption) and $T_{w}$ is the same for every node, $T_{w} \leq T_{r} - 1$ . Thus, equation (2) is equivalent to

LD L^{X \to Y} (E^{Y} + 1) = T_{r} - T_{w} + 1 \geq 2

(3)

Let’s consider the interval $T (S^{X}, E^{Y} - S^{X} + 1)$ . For $S^{X} \leq t \leq E^{Y}$ , $LD L^{X \to Y} (t) = 1$ . Since $S^{X}$ is the start of the working time of node $X$ , we cannot extend this interval to the left. From (1) and (3), we also cannot extend this interval to the right. Therefore, (a) $T (S^{X}, E^{Y} - S^{X} + 1)$ is a valid $NLD I^{X \to Y}$ . From equations (1) and (3), we cannot extend $T (E^{B} + 1, E^{A} - E^{B})$ to the left. Since $E^{A}$ is the end of the working time of node $A$ , we cannot extend $T (E^{B} + 1, E^{A} - E^{B})$ to the right. Therefore, (b) $T (E^{B} + 1, E^{A} - E^{B})$ is a valid $NLD I^{A \to B}$ .

From (a) and (b), $T (S^{A}, T_{w})$ contains two $NLD I^{A \to B}$ : $T (S^{A}, E^{B} - S^{A} + 1)$ and $T (E^{B} + 1, E^{A} - E^{B})$ . Lemma 1 is proved.

Definition 7

Assume node $X$ forwards a packet to the sink node $S$ via a next-hop node Y. A non-increasing delivery-latency period, $ND I^{X, Y}$ , is a non-extendable interval of time inside the working interval of node $X$ in which $D L^{X, Y} (t) (t \in ND I^{X, Y})$ decreases steadily or is equal to the minimum latency of this interval.

Formally, $T (s_{i}^{X, Y}, len)$ , an interval inside the working interval of node $X$ , is called an $ND I^{X, Y}$ if the following conditions hold:

For $t \in T (s_{i}^{X, Y}, len)$ , $D L^{X, Y} (t) = \max {D L^{X, Y} (s_{i}^{X, Y}) - dif (s_{i}^{X, Y}, t), l_{i}^{X, Y}}$ , where $dif (s_{i}^{X, Y}, t)$ is defined in definition 6 and $l_{i}^{X, Y}$ is the minimum delivery latency of $T (s_{i}^{X, Y}, len)$ .

$D L^{X, Y} (s_{i}^{X, Y}) \neq D L^{X, Y} (s_{i}^{X, Y} - 1) - 1$ , $D L^{X, Y} (s_{i}^{X, Y}) \neq D L^{X, Y} (s_{i}^{X, Y} - 1)$ .

$D L^{X, Y} (e + 1) \neq D L^{X, Y} (e) - 1$ , $D L^{X, Y} (e) \neq D L^{X, Y} (e + 1)$ .

where $e = (s_{i}^{X, Y} + len - 1) \mod T_{r}$ .

Condition (1) means link delivery latency decreases steadily or is equal to the minimum latency of this interval ( $l_{i}^{X, Y}$ ); (2) and (3) mean $T (s_{i}^{X, Y}, len)$ cannot be extended to the left or to the right, respectively.

Example 5

As shown in Figure 3(g) and (h), $A \to B \to \dots \to S$ route has three $ND I^{A, B}$ : $T (17, 3)$ , $T (20, 3)$ , and $T (3, 2)$ ; $A \to E \to \dots \to S$ has one $ND I^{A, E}$ : $T (17, 8)$ .

Definition 8

An NDI of node $X$ , denoted by $ND I^{X}$ , is a non-extendable interval of time inside the working interval of node $X$ in which $D L^{X} (t) (t \in ND I^{X})$ decreases steadily or equals to the minimum latency of this interval.

Example 6

As shown in Table 1 and Figure 3(i), $A \to \dots \to S$ route has two $ND I^{A}$ : $T (17, 3)$ and $T (20, 5)$ .

Lemma 2

Assume node A forwards a packet to the sink node S via node B. An $NLD I^{X \to Y}$ contains $(n + 1) ND I^{X, Y}$ if there are $n$ different end times of $ND I^{Y}$ belonging to this interval.

n = 0: there does not exist any $e_{i}^{Y}$ belonging to an $NLD I^{X \to Y}$ .

There are three possible cases shown in Figure 4(a)–(c). Since the cases in Figure 4(a) and (b) are very similar and the case in Figure 4(b) is more general, we will focus on the case in Figure 4(b). As shown in Figure 4(b) (refer to Figure 3(e)), $T (S^{X}, T_{w})$ contains one $NLD I^{X \to Y}$ : $T (s_{1}^{X \to A}, T_{w})$ (refer to lemma 1). We have

\begin{array}{l} ∄ e_{i}^{Y} \in T (s_{1}^{X \to Y}, T_{w}) \Leftrightarrow e_{1}^{Y} \geq E^{X} + 1 \\ \Leftrightarrow T (S^{Y}, E^{X} - S^{Y} + 2) \in 1 N D I^{Y} \end{array}

For any $t \in T (S^{X}, S^{Y} - S^{X} + 1)$ , $D L^{X, Y} (t) = LD L^{X \to Y} (t) + D L^{Y} (S^{Y} + 1)$ . Since $LD L^{X \to Y} (t)$ decreases steadily from $S^{Y} - S^{X} + 1$ to 1 when $t$ increases from $S^{X}$ to $S^{Y}$ , $D L^{X, Y} (t)$ decreases steadily from $(S^{Y} - S^{X} + 1) + D L^{B} (S^{Y} + 1)$ to $1 + D L^{Y} (S^{Y} + 1)$ .

For any $t \in T (S^{Y} + 1, E^{X} - S^{Y})$ , $D L^{X, Y} (t) = 1 + D L^{Y} (t + 1)$ . Since $(S^{Y}, E^{X} - S^{Y} + 2) \in one ND I^{Y}$ (assumption), $D L^{Y} (t + 1)$ decreases steadily or is equal to the minimum latency of this interval of node $Y (l_{i}^{Y})$ when $t$ increases from $S^{Y} + 1$ to $E^{X}$ . That is, $D L^{X, Y} (t)$ decreases steadily or is equal to $l_{i}^{Y} + 1$ .

$D L^{X, Y} (S^{Y}) = 1 + D L^{Y} (S^{Y} + 1)$ and $D L^{X, Y} (S^{Y} + 1) = 1 + D L^{Y} (S^{Y} + 2)$ . Since $D L^{Y} (S^{Y} + 1) = D L^{Y} (S^{Y} + 2)$ or $D L^{Y} (S^{Y} + 1) = D L^{Y} (S^{Y} + 2) + 1$ , $D L^{X, Y} (S^{Y}) = D L^{X, Y} (S^{Y} + 1)$ or $D L^{X, Y} (S^{Y}) = D L^{X, Y} (S^{Y} + 1) + 1$ .

From (1), (2), and (3), $T (S_{1}^{X \to Y}, T_{w})$ contains one $ND I^{X, Y}$ . As shown in Figure 4(c) (refer to Figure 3(f)), $T (S^{X}, T_{w})$ contains two $NLD I^{X \to Y}$ : $T (s_{1}^{X \to Y}, E^{Y} - S^{X} + 1)$ and $T (s_{2}^{X \to Y}, E^{X} - E^{Y})$ (refer to lemma 1). There does not exist any $e_{i}^{Y}$ belonging to an $NLD I^{X \to Y} \Leftrightarrow e_{last}^{Y} \leq S^{X}$ . The proof is similar to the above case.

Figure 4.

An illustration of basic definitions and lemma 2: (a) one NLDI^A → B contains one NDI^A,B, (b) one NLDI^A → B contains one NDI^A,B (general), (c) one NLDI^A → B contains one NDI^A,B, (d) working schedules, (e) LDL^A → B, (f) DL^B, one NLDI^A → B contains two NDI^A,B, (g) one NLDI^A → B contains two NDI^A,B, (h) one NLDI^A → B contains (k + 1) NDI^A,B, and (i) property of combined ATS.

n = 1: there is one $e_{i}^{Y}$ belonging to an $NLD I^{X \to Y}$ . There are two possible cases shown in Figure 4(d)–(g).

From lemma 1, $T (S^{X}, T_{w})$ in Figure 4(d)–(f) contains two $NLD I^{X \to Y}$ : $T (s_{1}^{X \to Y}, E^{Y} - S^{X} + 1)$ and $T (s_{2}^{X \to Y}, E^{X} - E^{Y})$ . There is no case that $\exists e_{i}^{Y} \in T (s_{2}^{X \to Y}, E^{X} - E^{Y})$ since $T (s_{2}^{X \to Y}, E^{X} - E^{Y})$ is outside the working interval of node Y. It is only possible that $\exists e_{i}^{Y} \in T (s_{1}^{X \to Y}, E^{Y} - S^{X} + 1)$ . Therefore, assume that $e_{1}^{Y} \in T (s_{1}^{X \to Y}, E^{Y} - S^{X} + 1)$ , we have to prove that $T (s_{1}^{X \to Y}, E^{Y} - S^{X} + 1)$ contains two $ND I^{X, Y}$ . We have

For $s_{1}^{X \to Y} \leq t < e_{1}^{Y}$ , $D L^{X, Y} (t) = 1 + D L^{Y} (t + 1)$ . Since $D L^{Y} (t + 1)$ decreases steadily or is equal to $l_{1}^{Y}$ , $D L^{X, Y} (t)$ decreases steadily or is equal to $l_{1}^{Y} + 1$ .

For $e_{1}^{Y} \leq t \leq E^{Y}$ , $D L^{X, Y} (t) = 1 + D L^{Y} (t + 1)$ . Since $D L^{Y} (t + 1)$ decreases steadily or is equal to $l_{2}^{Y}$ , $D L^{X, Y} (t)$ decreases steadily or is equal to $l_{2}^{Y} + 1$ .

$D L^{X, Y} (e_{1}^{Y} - 1) = 1 + D L^{Y} (e_{1}^{Y})$ and $D L^{X, Y} (e_{1}^{Y}) = 1 + D L^{Y} (s_{2}^{Y})$ . Since $D L^{Y} (e_{1}^{Y}) \neq D L^{Y} (s_{2}^{Y})$ and $D L^{Y} (e_{1}^{Y}) \neq D L^{Y} (s_{2}^{Y}) + 1$ , $D L^{X, Y} (e_{1}^{Y} - 1) \neq D L^{X, Y} (e_{1}^{Y})$ and $D L^{X, Y} (e_{1}^{Y} - 1) \neq D L^{X, Y} (e_{1}^{Y}) + 1$

From (1), (2), and (3), $T (s_{1}^{X \to Y}, E^{Y} - S^{X} + 1)$ contains two $ND I^{X, Y}$ : $T (s_{1}^{X \to Y}, e_{1}^{Y} - S^{X})$ and $T (e_{1}^{X}, E^{Y} - e_{1}^{Y} + 1)$ . As shown in Figure 4(g) (refer to Figure 3(e)), $T (S^{X}, T_{w})$ contains one $NLD I^{X \to Y}$ : $T (s_{1}^{X \to Y}, T_{w})$ (refer to lemma 1). We have $\exists e_{i}^{Y} \in T ({s^{X \to Y}}_{1}, T_{w}) \Leftrightarrow \exists e_{i}^{Y} \leq E^{X}$ .

The proof is similar to the above case.

n = k: assume lemma 2 holds with $n = k$ , then we have to prove lemma 2 holds with $n = k + 1$ .

Lemma 2 holds with $n = k$ , that is, there are $k$ end times of $k$ $ND I^{B}$ belonging to $T (s_{1}^{X \to Y}, E^{Y} - S^{A} + 1)$ and $T (s_{1}^{X \to Y}, E^{Y} - S^{X} + 1)$ contains $(k + 1) ND I^{X, Y}$ , as shown in Figure 4(h). Assume $e_{k + 1}^{Y} \in T (e_{k}^{Y}, E^{Y} - e_{k}^{Y} + 1)$ . Then, we will prove $T (s_{1}^{X \to Y}, E^{Y} - S^{X} + 1)$ contains $(k + 2) ND I^{X, Y}$ .

Let’s consider the interval $T (e_{k}^{Y}, E^{Y} - e_{k}^{Y} + 1)$ . We have $e_{k + 1}^{Y} \in T (e_{k}^{Y}, E^{Y} - e_{k}^{Y} + 1)$ . Using the same proof as in case $n = 1$ , we have $T (e_{k}^{Y}, E^{Y} - e_{k}^{Y} + 1)$ contains two $ND I^{X, Y}$ : $T (e_{k}^{Y}, e_{k + 1}^{Y} - e_{k}^{Y})$ and $T (e_{k + 1}^{Y}, E^{Y} - e_{k + 1}^{Y} + 1)$ . Thus, $T (s_{1}^{X \to Y}, E^{Y} - S^{X} + 1)$ contains $(k + 2) ND I^{X, Y}$ . Lemma 2 is proved.

Definition 9

The start time of an $NDI$ is called an anchor time, $AT$ .

Property 2

Let $R^{X, Y}$ and $R^{X, Z}$ be two of the routes from node $X$ to node $S$ ; $AT S^{X, Y}$ and $AT S^{X, Z}$ be the set of all anchor times of $R^{X, Y}$ and $R^{X, Z}$ , respectively; and $AT S^{X} = {s_{1}^{X}, s_{2}^{X}, \dots, s_{n}^{X}}$ be the combined time-ordered set of $AT S^{X, Y}$ and $AT S^{X, Z}$ (Refer Figure 4(i) for illustration). For any $s_{k}^{X} \in AT S^{X}$ , $[s_{k}^{X}, s_{k + 1}^{X} - 1]$ completely belongs to an $ND I^{X, Y}$ and an $ND I^{X, Z}$ .

Figure 5 shows the routing table formats representing routing information.

Figure 5.

Routing table (a: time-slot-based routing and b: NDI-based routing scheme), format of an RAP (c), and routing record table (d: time-slot-based and e: NDI-based routing).

Simple RT’s format of the time-slot-based routing scheme: to determine the minimum latency routes from each sensor to the sink, the $RT$ of a sensor needs to contain the information as in Figure 5(a).

Simple RT’s format of the NDI-based routing scheme: as mentioned in definition 7, we need the delivery latencies at the starting and ending times of each NDI to calculate the delivery latency at any time slot inside this NDI. Therefore, in order to find the minimum latency routes from each sensor to the sink, the $RT$ of a sensor needs to contain the information as in Figure 5(b).

RAP’s format of the time-slot-based and NDI-based routing schemes: $RAP$ of a sensor needs to contain the information as in Figure 5(c). The routing information field contains the list of routing records. The format of a routing record of the time-slot-based routing scheme is as in Figure 5(d). The format of a routing record of the NDI-based routing scheme is as in Figure 5(e).

Proposed NDI-based routing scheme

The proposed routing scheme has a small footprint in terms of size of routing tables, amount of energy required by the routing process, traffic load, and creation of minimum latency routes. The lemmas and related properties derived in the previous section are used to formulate the three algorithms used in our scheme.

Overview

The proposed scheme finds minimum latency routes from sensors to the sink at each interval of time instead of at each time slot. Obviously, to minimize the number of intervals to be stored at each sensor, we have to maximize the length of an interval, but we have to guarantee obtaining the minimum latency routes from each sensor to the sink. In this article, we introduce the concept of a NDI: a non-extendable interval of time inside the working interval of a node in which delivery latency decreases steadily or remains the same (refer to definition 7). Using NDI, we can easily obtain the above goal. Therefore, the purpose of the proposed NDI-based routing scheme is to find the list of NDIs and corresponding minimum latency routes to the sink at each sensor.

Algorithm description

Our proposed scheme uses an initialization phase, in which all sensors are awake, to build the $RT$ at every sensor in a distributed manner. The algorithm is similar to the distributed Bellman–Ford algorithm, but it uses only the sink as a destination. The initialization phase starts with the sink node broadcasting its $RAP$ to its one-hop neighbors ( $RAP$ of sink has only 1 record with a 0 delivery latency). When a node receives $RAP$ , it uses algorithm 1 to process the $RAP$ . When no $RAP$ is transmitted in the network, the algorithm stops.

Algorithm 1

Processing $RAP$ at node $A$ : as shown in Figure 6, node $A$ first uses algorithm 2 to build the $R T^{A, B}$ based on the information of the $RA P^{B}$ (line 1) using algorithm 2. If the current $R T^{A}$ is empty, node $A$ uses the $R T^{A, B}$ as its $RT$ (lines 2–3). Otherwise, it builds the combined $ATS$ based on the $AT S^{A}$ of $R T^{A}$ and $AT S^{A, B}$ of $R T^{A, B}$ (lines 5–7). Then, it uses algorithm 3 to update the current $R T^{A}$ at each anchor time (lines 8–10) by employing algorithm 3. If the $R T^{A}$ is updated (line 12), it first optimizes the $R T^{A}$ (line 13). Then, it builds the $RA P^{A}$ and broadcasts the $RA P^{A}$ to its one-hop neighbors. The purpose of the Optimize function is to merge consecutive NDIs into a single one if the merged NDI satisfies the characteristics of an NDI. This helps to minimize the number of NDIs stored at sensors.

Figure 6.

Pseudocode of the RAP-processing algorithm.

Algorithm 2

Building $R T^{A, B}$ from $RA P^{B}$ : as shown in Figure 7, since the $R T^{A, B}$ has no record at the beginning of the algorithm, the $AT S^{A, B}$ is empty (line 1). The starting time $(S^{A})$ of the working interval of node $A$ is the first anchor time to be inserted to the $AT S^{A, B}$ (line 2). If the ending time $(E^{B})$ of the working interval of node $B$ belongs to the working interval of node $A$ , the next time slot of $E^{B}$ is inserted to the $AT S^{A, B}$ (lines 3–5) as illustrated in lemma 1. For each ending time $(e_{i}^{B})$ of each NDI in the $RA P^{B}$ , if $e_{i}^{B}$ belongs to the working interval of node $A$ , $e_{i}^{B}$ is inserted to the $AT S^{A, B}$ (lines 6–10) in accordance to lemma 2. Finally, the delivery latency at each anchor time in the $AT S^{A, B}$ from node $A$ to the sink node is updated accumulatively (lines 11–13).

Figure 7.

Pseudocode of the RT-building algorithm.

Algorithm 3

Updating $R T^{A}$ at an interval: as shown in Figure 8, node $A$ first calculates the ending time $(e_{i}^{A})$ of the current interval (lines 1–5). If the delivery latency at the starting time $(s_{i}^{A})$ of the current $R T^{A}$ is greater than that of the $R T^{A, B}$ (line 6), node $A$ first updates the record at $s_{i}^{A}$ of the current $R T^{A}$ with that of the $R T^{A, B}$ (line 7). Then, if the delivery latency at $e_{i}^{A}$ of the current $R T^{A}$ is less than that of the $R T^{A, B}$ , one new anchor time is created and one new record with the current route in $R T^{A}$ is inserted to $R T^{A}$ (lines 8–11; refer to Figure 9(a) to understand the lines from 6 to 11). Otherwise, if the delivery latency at $s_{i}^{A}$ of the current $R T^{A}$ is equal to that of the $R T^{A, B}$ and if the delivery latency at $e_{i}^{A}$ of the current $R T^{A}$ is greater than that of the $R T^{A, B}$ , one new anchor time is created and one new record with the current route in $R T^{A, B}$ is inserted to $R T^{A}$ (line 12–16; refer to Figure 9(b) to understand the lines from 12 to 16). Otherwise, if the delivery latency at $e_{i}^{A}$ of the current $R T^{A}$ is greater than that of the $R T^{A, B}$ , one new anchor time is created and one new record with the current route in $R T^{A, B}$ is inserted to $R T^{A}$ (lines 17–21; refer to Figure 9(c) to understand the lines from 17 to 21).

Figure 8.

Pseudocode of the RT-updating algorithm.

Figure 9.

An illustration for algorithm 3: (a) lines 6–11, (b) lines 12–16, and (c) lines 17–21.

Algorithm walk-through

We use the example in Figure 2 to illustrate the walk-through of the proposed NDI-based routing scheme. For the sake of simplicity, we describe the routing process in four steps: (1) $S \to F \to E \to A$ , (2) $S \to D \to B$ , (3) $S \to C \to B$ , and (4) $B \to A \to E$ . First, the sink node $S$ initializes its $RA P^{S}$ as in Table 3 (row one; represented by S in column one) and then broadcasts the $RA P^{S}$ to its one-hop neighbors. $S \to F \to E \to A$ : node $F$ receives the $RA P^{S}$ from node $S$ . It uses algorithm 2 to build the $R T^{F, S}$ as in Table 4 (row one or $F$ , $S$ ). Since the current $R T^{F}$ is empty, node $F$ uses the $R T^{F, S}$ as its $RT$ . It then builds an updated $RA P^{F}$ as in Table 3 ( $F$ ) and broadcasts to its one-hop neighbors.

Table 3.

Routing advertisement packets summary of node X.

$X = RA P^{X}$	Anchor time	Starting DL	Ending DL
$S$	1	0	0
$F$	1	1	1
$E$	3	2	2
	9	14	13
$D$	2	1	1
$C$	13	1	1
$B$	15	2	2
	1	3	2
$A$	17	3	3
	20	4	3

DL: delivery latency.

Table 4.

Routing table summary of $X$ with next-hope Y.

$X, Y = R T^{X, Y}$	AT	Starting DL	Ending DL
F, S	1	1	1
E, F	3	2	2
	9	14	13
A, E	17	9	3
D, S	2	1	1
B, D	15	9	2
C, S	13	1	1
B, C	15	2	2
	1	14	13
A, B	17	3	3
	20	4	3
	3	15	14
E, A	3	4	4
	5	16	11

AT: anchor time; DL: delivery latency.

Node $E$ receives the $RA P^{F}$ from node $F$ . Node $E$ uses algorithm 2 to build the $R T^{E, F}$ : the first anchor time is the starting time of the working interval of node $E (S^{E} = 3)$ ; Since $E^{F} = 8 \in T (3, 8)$ , $E^{F} + 1 = 9$ is inserted to $AT S^{A, B}$ ; $D L^{E, F} (3) = LD L^{E \to F} (3) + D L^{F} (3 + LD L^{E \to F} (3)) = 1 + D L^{F} (3 + 1) = 1 + 1 = 2$ ; $D L^{E, F} (8) = 1 + D L^{F} (8 + 1) = 1 + 1 = 2$ ; $D L^{E, F} (9) = 13 + D L^{F} ([9 + 13] % 20) = 13 + 1 = 14$ ; and $D L^{E, F} (10) = 12 + D L^{F} ([10 + 12] % 20) = 12 + 1 = 13$ . Table 5 ( $E$ , $F$ ) shows the resulted $R T^{E, F}$ . Since the current $R T^{E}$ is empty, node $E$ uses the $R T^{E, F}$ as its $RT$ . Then, it builds the $RA P^{E}$ as in Table 4 ( $E$ ) and broadcasts to its one-hop neighbors.

Table 5.

Routing table summary of node $X$ .

$X = R T^{X}$	AT	Starting DL	Ending DL	Next hop
$B$	15	2	2	$C$
	1	3	2	$D$
$A$	17	3	3	$B$
	20	4	3	$B$
	3	3	3	$E$
$E$	3	2	2	$F$
	5	2	2	$F$
	9	12	11	$A$
$E$ final	3	2	2	$F$
	9	12	11	$A$

AT: anchor time; DL: delivery latency.

Node $A$ receives the $RA P^{E}$ from node $E$ . Similarly, it uses algorithm 2 to build the $R T^{A, E}$ : there is only one anchor time $S^{A} = 17$ ; $D L^{A, E} (17) = 7 + D L^{E} ([17 + 7] % 20) = 7 + 2 = 9$ ; and $D L^{A, E} (4) = 1 + D L^{E} (4 + 1) = 1 + 2 = 3$ . Table 4 ( $A$ , $E$ ) shows the resulting $R T^{A, E}$ . Since the current $R T^{A}$ is empty, node $A$ uses the $R T^{A, E}$ as its $RT$ .

$S \to D \to B$ : node $D$ receives the $RA P^{S}$ from node $S$ . It uses algorithm 2 to build the $R T^{D, S}$ as in Table 4 ( $D$ , $S$ ). Since the current $R T^{D}$ is empty, node $D$ uses the $R T^{D, S}$ as its $RT$ . It then builds the $RA P^{D}$ as in Table 3 (D) and broadcasts to its one-hop neighbors. Node $B$ receives the $RA P^{D}$ from node $D$ . Similarly, it uses algorithm 2 to build the $R T^{B, D}$ as in Table 4 ( $B$ , $D$ ). Since the current $R T^{B}$ is empty, node $B$ uses the $R T^{B, D}$ as its $RT$ .

$S \to C \to B$ : node $C$ receives the $RA P^{S}$ from node $S$ . It uses algorithm 2 to build the $R T^{C, S}$ as in Table 4 ( $C$ , $S$ ). Since the current $R T^{C}$ is empty, node $C$ uses the $R T^{C, S}$ as its RT. It then builds the $RA P^{C}$ as in Table 3 (C) and broadcasts to its one-hop neighbors. Node $B$ receives the $RA P^{C}$ from node $C$ . Similarly, it uses algorithm 2 to build the $R T^{B, C}$ as in Table 4 ( $B$ , $C$ ). Node $B$ then uses algorithm 3 to update the current $R T^{B}$ with the $R T^{B, C}$ : there are two anchor times 15 and 1, and Table 6 shows the comparison between $R T^{B}$ and $R T^{B, C}$ . Let’s consider the first anchor time 15: $D L^{B} (15) = 9 > D L^{B, C} (15) = 2$ , which satisfies line 6 of algorithm 3, thus line 7 is applied; $D L^{B} (20) = 4 > D L^{B, C} (20) = 2$ , which does not satisfy line 8 of algorithm 3. The procedure is similar for the second anchor time 1. Table 5 (B) shows the updated $R T^{B}$ . Node $B$ then builds the $RA P^{B}$ as in table and broadcasts to its one-hop neighbors.

Table 6.

Final routing summary after comparison.

$X$	Anchor time	Starting DL	Ending DL
$B$ & B, C	15	9	2
	20	4	2
	1	3	14
	2	2	13
$A$ & A, B	17	9	3
	19	7	3
	20	6	4
	2	4	3
	3	3	15
	4	3	14
$E$ & E, A	3	2	4
	4	2	4
	5	2	16
	8	2	13
	9	14	12
	10	13	11

DL: delivery latency.

$B \to A \to E$ : node $A$ receives the $RA P^{B}$ from node $B$ . Similarly, it uses algorithm 2 to build the $R T^{A, B}$ as in Table 4 ( $A$ , $B$ ). Then, it uses algorithm 3 to update the current $R T^{A}$ with $R T^{A, B}$ : there are three anchor times: 17, 20, and 3; and Table 6 ( $A$ & A, B) shows the comparison. Table 5 (A) shows the updated $R T^{A}$ . Node $A$ then builds the $RA P^{A}$ and broadcasts to its one-hop neighbors. Since the second record and third record can be merged into one when removing the next-hop field, there are two records in the $RA P^{A}$ , as shown in Table 4 (A).

Node $E$ receives the $RA P^{A}$ from node $A$ and builds the $R T^{E, A}$ as in Table 4 ( $E$ , $A$ ). Table 6 ( $E$ & E, A) shows the comparison of the current $R T^{E}$ with $R T^{E, A}$ : there are three anchor times 3, 5, and 9. Table 5 (E) shows the updated $R T^{E}$ . After being optimized, the final $R T^{E}$ is created. To this point, every node in the network has its minimum latency routing table. Therefore, no more RAP needs to be sent and the algorithm stops. In the main phase, each sensor follows its predefined working schedule and uses its RT to forward data packets to the sink. For example, assume node $A$ has a packet to send to the sink at time 1. It checks its routing RT (refer to Table 5 (A)) and finds out that $1 \in T (20, 3)$ , that is, time 1 belongs to the second NDI of node $A$ . The delivery latency at time 1 is $D L^{A} (1) = 4 - (1 + 20 - 20) = 3$ and the next hop is node $B$ .

Thus, node $A$ forwards the data packet to node $B$ . The data packet arrives at node $B$ at time 1 and is available to be sent at time 2. Node $B$ checks its RT refer to Table 5 (B) and finds out that $2 \in T (1, 2)$ and the next hop is node $D$ . Node $B$ then forwards the data packet to node $D$ . The data packet arrives at node $D$ at time 2 and is available to be sent at time 3. Node $D$ check its RT (refer to Table 4 ( $D$ , $S$ )) and the next hop is sink node $S$ . The data packet finally arrives at the sink node at time 3.

Performance evaluation

In this simulation study, we employ a custom built simulator in Java to evaluate the performance of the proposed scheme, NDI-based routing, under different network sizes, duty cycles, node densities, and lengths of time round. We compare the proposed scheme with the time-slot-based routing scheme.²³ The time-slot-based routing scheme is implemented exactly the same as the proposed NDI-based routing scheme, but finds the minimum latency routes from sensors to the sink at each time slot. We used the following three metrics to evaluate the performance:

The size of routing tables. The average number of bytes stored at each sensor for the routing purpose.

Routing traffic load. The amount of traffic transmitted during the routing process.

Energy consumption per node. The average amount of energy consumed by each sensor to obtain the minimum latency routing table.

Note that the proposed NDI-based routing scheme guarantees obtaining the minimum latency routes from sensors to the sink, and the performance of the NDI-based routing scheme is exactly the same as the flooding scheme. Therefore, we do not show the performance result in terms of delivery latency.

Simulation environment

Sensor nodes are randomly deployed and each node randomly selects the starting time of its working interval. The working interval $(T_{w})$ is set to 90 time slots. For the sizes of the physical (PHY) Header and the media access control (MAC) Header, we use the same values as in the literature.^10,28Table 7 summarizes the simulation experiment parameters used in the performance evaluation. Each of the three performance measurements are carried out across the following four variable settings:

Different network sizes. The number of nodes increases from 200 to 1000 and the deployed area increases proportionally from $230 m \times 230 m$ to $510 m \times 510 m$ .

Different duty cycles. The node duty cycle increases from 10% to 50%.

Different node densities. The node density increases from 6 to 12.

Different lengths of time round. The time round increases from 100 to 500.

Table 7.

Simulation parameters.

Parameter	Value
IEEE 802.15.4 PHY Header	6 bytes
IEEE 802.15.4 MAC Header	11 bytes
RT record of NDI-based routing	8 bytes
RT record of time-slot-based routing	6 bytes
RAP record of NDI-based routing	6 bytes
RAP record of time-slot-based routing	4 bytes
Radio transmission range	30 m
Output power	6 dBm
Voltage	3 V
Data transmission rate	19.2 kbps

PHY: physical; MAC: media access control; NDI: non-increasing delivery-latency interval.

For each setting of network sizes, duty cycles, node densities, and lengths of time round, a simulation is run 100 times and we average them to get the mean value with 95% confidence.

Simulation experiments results

In this section, performance measure of the proposed scheme is compared with existing schemes.

The size of routing tables

As mentioned in the previous sections, the proposed NDI-based routing scheme minimizes the routing information stored at each sensor. As shown in Figure 10, the NDI-based routing scheme significantly improves the performance of the time-slot-based routing scheme in terms of the routing table’s size. Note that in the case of the NDI-based routing scheme, we obtained the mean (Mean of max NDI-based routing) and the maximum (Max of max NDI-based routing) of the maximum routing table’s size of sensor node in each run.

Figure 10.

The size of routing tables: (a) network size, (b) duty cycle, (c) node density, and (d) length of time round.

For example, as shown in Figure 10(d), when the $T_{r} = 500$ , routing table sizes of NDI-based, max of max NDI-based, and time-slot-based routing are 23.78, 112, and 900 bytes, respectively. That is, the NDI-based routing improves the performance of the time-slot-based routing is 36.85-fold on average and is 8.04-fold in the worst case.

Routing traffic load

Since the proposed NDI-based routing scheme minimizes the size of a routing table, it significantly reduces the routing traffic load in the network, as shown in Figure 11. For example, as shown in Figure 11(a), when the number of nodes is 1000, the traffic load of NDI-based and time-slot-based routing are 5326.88 and 64,896.31 kilobytes, respectively. That is, the NDI-based routing improves the performance of the time-slot-based routing is 12.18-fold.

Figure 11.

Routing traffic load: (a) network size, (b) duty cycle, (c) node density, and (d) length of time round.

Energy consumption per node

Due to the reduction of the routing traffic load, the proposed NDI-based routing scheme helps sensors conserve a large amount of energy consumed in the routing process, as shown in Figure 12. For example, as shown in Figure 12(c), when node density is 12 neighbors/transmission range, the energy consumption per node of NDI-based and time-slot-based routing are 187.21 and 2099.11 mJ, respectively. It means NDI-based routing improves the time-slot-based performance is 11.21-fold.

Figure 12.

Energy consumption per node: (a) network size, (b) duty cycle, (c) node density, and (d) length of time round.

Conclusion

Finding routes with low delivery latency in sleep- and awake-scheduled WSNs is a mandatory requirement in many critical applications. The majority of recent schemes find the optimal routes at each time slot, thereby resulting in very high routing overhead. In this article, we proposed the concept of an NDI and proposed the NDI-based routing scheme that finds minimum latency routes from sensors to the sink at each NDI instead of each time slot.

Analysis and simulation results showed that the proposed NDI-based routing scheme minimizes the routing information stored at each sensor and significantly improves the performance of the time-slot-based routing scheme in terms of routing traffic load and energy consumption. Furthermore, it also guarantees the minimum delivery-latency routes from the sensors to the sink. In this work, we assume the network has a disk communication model with a given communication range. We will consider the lossy environment in our future work. Furthermore, we will consider the multiple-sink-based network scenario to test our proposed scheme.

Future work

In this article, we have presented our NDI-based routing scheme and validated it using extensive modeling, simulation experiments, and significant performance improvements. Several additional WSN aspects and scenarios in our approach can lead to interesting future work. One direction can be hardware implementation as a next logical step. Another way forward is to consider addition and/or eviction of the sensor nodes. Considering the cost of time synchronization in terms of exchanged messages would also be an important aspect to consider. One more challenging issue for future research is to adopt the proposed idea for a scenario with a random wake-up interval. Last but not least, a multiple-sink-based WSN scenario is also an interesting future extension of our proposed method. Moreover, we intend to investigate the possibility of an extension of the proposed scheme for using in an Internet of things (IoT) scenario, such as Smart Cities, where a WSN can be considered as a building block for an area sensor network.²⁹

Footnotes

Handling Editor: Zhong Shen

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported, in part, by Korean government, under G-ITRC (IITP-2018-2015-0-00742), ICT R&D (B0101-15-1366, IITP), Priority Research Centers (NRF-2010-0020210), and Basic Science Research Program (NRF-2016R1D1A1B03934615).

References

Akyildiz

Sankarasubramaniam

et al . A survey on sensor networks. IEEE Commun Mag 2002; 40: 102–114.

Gui

Mohapatra

Power conservation and quality of surveillance in target tracking sensor networks. In: Proceedings of the 10th annual international conference on mobile computing and networking, Philadelphia, PA, 26 September–1 October 2004, pp.129–143. New York: ACM.

Kim

Schmid

Charbiwala

et al . NAWMS: nonintrusive autonomous water monitoring system. In: Proceedings of the 6th ACM conference on embedded network sensor system, Raleigh, NC, 5–7 November 2008, pp.309–322. New York: ACM.

Yan

Stankovic

. Differentiated surveillance for sensor networks. In: Proceedings of the 1st international conference on embedded networked sensor system, Los Angeles, CA, 5–7 November 2003, 2nd ed., pp.51–62. New York: ACM.

Chen

Cao

et al . Optimizing energy efficiency for minimum latency broadcast in low-duty-cycle sensor networks. ACM Trans Sensor Network 2015; 11(4): 57.

Feeney

Nilsson

Investigating the energy consumption of a wireless network interface in an ad hoc networking environment. In: Proceedings of the IEEE INFOCOM twentieth annual joint conference of the IEEE computer and communications societies, Anchorage, AK, 22–26 April 2001, pp.1548–1557. New York: IEEE.

Kasbekar

Bejerano

Sarkar

Lifetime and coverage guarantees through distributed coordinate-free sensor activation. In: Proceedings of the15th annual international conference on mobile computing and networking, Beijing, China, 20–25 September 2009, pp.169–180. New York: ACM.

Alkhdour

Baroudi

Shakshuki

et al . An optimal cross-layer scheduling for periodic WSN applications. Procedia Comput Sci19: 88–97.

Xing

Wang

Zhang

et al . Integrated coverage and connectivity configuration for energy conservation in sensor networks. ACM T Sensor Network 2005; 1(1): 36–72.

10.

Wang

Liu

Duty-cycle-aware broadcast in wireless sensor networks. In: Proceedings of the IEEE INFOCOM, Rio de Janeiro, Brazil, 19–25 April 2009, pp.468–476. New York: IEEE.

11.

Beraldi

Baldoni

Prakash

A biased random walk routing protocol for wireless sensor networks: the lukewarm potato protocol. IEEE T Mobile Comput 2010; 9(11): 1649–1661.

12.

Dynamic switching-based data forwarding for low-duty-cycle wireless sensor networks. IEEE T Mobile Comput 2011; 10(12): 1741–1754.

13.

Lin

et al . Spatiotemporal delay control for low-duty-cycle sensor networks. In: Proceedings of the IEEE real-time systems symposium, Washington, DC, 1–4 December 2009, pp.127–137. New York: IEEE.

14.

Lai

Paschalidis

IC.

Optimally balancing energy consumption versus latency in sensor network routing. ACM T Sensor Netw 2008; 4(4): 2111–2128.

15.

Sadagopan

Krishnamachari

et al . Delay efficient sleep scheduling in wireless sensor networks. In: Proceedings of the IEEE INFOCOM 24th annual joint conference of the IEEE computer and communications societies, Miami, FL, 13–17 March 2005, pp.2470–2481. New York: IEEE.

16.

Krishnamachari

Minimum latency joint scheduling and routing in wireless sensor networks. Ad Hoc Netw 2007; 5(6): 832–843.

17.

Sun

Delay-aware routing in low duty-cycle wireless sensor networks. In: Proceedings of the WiCOM, Chengdu, China, 23–15 September 2010, pp.1–4. New York: IEEE.

18.

Fan

Minimum delay query in low-duty-cycle sensor networks. Int J Future Gener Commun Netw 2016; 9(6): 351–362.

19.

Wang

Guo

Optimized energy-latency cooperative transmission in duty-cycled wireless sensor networks. In: Proceedings of the IEEE international conference on ICMA, Takamatsu, Japan, 4–7 August 2013, pp.185–190. New York: IEEE.

20.

Han

Dong

Guo

et al . Cross-layer optimized routing in wireless sensor networks with duty cycle and energy harvesting. Wire Commun Mob Comput 2014; 15(16): 1957–1981.

21.

Wan

Shen

. Maximal lifetime scheduling for roadside sensor networks with survivability k. IEEE T Veh Technol 2015; 64(11): 5300–5313.

22.

Dousse

Mannersalo

Thiran

Latency of wireless sensor networks with uncoordinated power saving mechanisms. In: Proceedings of the 5th ACM international symposium on mobile ad hoc networking and computing, Tokyo, Japan, 24–26 May 2004, pp.109–120. New York: ACM.

23.

Keshavarzian

Lee

Venkatraman

Wakeup scheduling in wireless sensor networks. In: Proceedings of the 7th ACM international symposium on mobile ad hoc networking and computing, Florence, 22–25 May 2006, pp.322–333. New York: ACM.

24.

Lai

Paschalidis

. Sensor network minimal energy routing with latency guarantees. In: Proceedings of the 8th ACM international symposium on mobile ad hoc networking and computing, Montreal, QC, Canada, 9–14 September, pp.199–208. New York: ACM.

25.

Galzarano

Savaglio

Liotta

et al . Gossiping-based AODV for wireless sensor networks. In: Proceedings of the IEEE international conference on systems, man, and cybernetics, Manchester, 13–16 October 2013, pp.26–31. New York: IEEE.

26.

Shahzad

Ali

Gohar

. ETSP: an energy-efficient time synchronization protocol for wireless sensor networks. In: Proceedings of the 22nd international conference IEEE AINA, Okinawa, Japan, 25–28 March 2008, pp.971–976. New York: IEEE.

27.

Guo

et al . Opportunistic flooding in low-duty-cycle wireless sensor networks with unreliable links. IEEE T Comput 2014; 63: 2787–2802.

28.

IEEE 802.15.4-2003. Part 15.4: wireless medium access control and physical layer specifications for low-rate wireless personal area networks.

29.

Molina

Palau

Fortino

et al . Empowering smart cities through interoperable sensor network enablers. In: Proceedings of the IEEE international conference on systems, man, and cybernetics, San Diego, CA, 5–8 October 2014, pp.7–12. New York: IEEE.

LNDIR: A lightweight non-increasing delivery-latency interval-based routing for duty-cycled sensor networks

Abstract

Keywords

Introduction

Related work

Network model and problem formulation

Network model and assumptions

Problem formulation

Basic definitions and lemmas

Note 1

Definition 1

Example 1

Definition 2

Definition 3

Example 2

Note 2

Definition 4

Property 1

Note 3

Definition 5

Definition 6

Example 3

Lemma 1

Case 1

Case 2

Definition 7

Example 5

Definition 8

Example 6

Lemma 2

Definition 9

Property 2

Proposed NDI-based routing scheme

Overview

Algorithm description

Algorithm 1

Algorithm 2

Algorithm 3

Algorithm walk-through

Performance evaluation

Simulation environment

Simulation experiments results

The size of routing tables

Routing traffic load

Energy consumption per node

Conclusion

Future work

Footnotes

Declaration of conflicting interests

Funding

References