Adaptive Scheduling and Routing Scheme for Delay Guarantee in Wireless Sensor Networks

Abstract

In wireless sensor networks (WSNs), periodical sleeping scheme on sensor nodes is an effective way to save energy. However, it will hinder the capability of the network to provide real-time data reporting due to relay node being sleep. Motivated by this, we propose an adaptive scheduling and routing scheme for guaranteeing dynamic end-to-end delay requirement while minimizing the energy consumption. First of all, we utilize an optimal wake-up scheduling algorithm to achieve the initial wake-up schedules and routes and design an adaptive adjustment algorithm. When the end-to-end delay requirement of a region changes, our proposed adaptive adjustment algorithm can locally adjust the wake-up schedules or the routing tables of the nodes which are the nearest ones to the source node, so as to minimize energy consumption and the impact on other regions while guaranteeing the new end-to-end delay requirement of the region. Through experiments in a real wireless sensor network and extensive simulations, we can get that the proposed scheme can conserve at least 20% energy consumption comparing to other existing adjustment algorithms, and its performance approaches that of the optimal solution.

1. Introduction

Due to the vast potential applications, large-scale wireless sensor networks (WSNs) are widely used in environmental monitoring, battlefield detection, water level monitoring, and so on. Since sensor nodes are small devices with limited resources, in particular battery power (or energy), it is therefore crucial to reduce energy consumption of those nodes in order to achieve a longer network lifetime. Periodical sleeping scheme on sensor nodes is an effective way to save energy in the context of WSNs. However, due to the presence of sleep-awake scheduling, when a node needs to report data, it has to wait for its next-hop node to wake up. When the next-hop node is receiving data, it will encounter the same problem. As a result, end-to-end delay may uncontrollably increase, and hence the system may be unacceptable in many applications requiring real-time response.

Let us see an example of data reporting process in an industrial temperature monitoring system. At the beginning, the entire network has a same delay requirement. When we pay more attention to region A since its temperature exceeds a threshold, we may increase the data collecting and reporting frequency so as to get more detailed information there, and thus the delay requirement of this region A will be accordingly shortened. Such change on delay requirement can also be triggered by event detection. The node that detects the event or quickly reports is called trigger node. To meet the new end-to-end delay requirement of the region A, the optimal solution is to find some necessary adjustments near the trigger node while keeping other nodes unchanged. The adjustments include changes on route and sleep schedule. In most environmental monitoring WSNs, for prolonging the system lifetime, we usually set a long sleeping interval when the environment changes smoothly. Only when the sensing data is not in reasonable range or exceeds the pre-setting threshold, we shorten the sleep time in the event area and increase the reporting frequency, so as to reduce the end-to-end delay and hence ensure the rapid response of events. Wang et al. [1] proposed a dynamic duty cycle control approach that decomposed the end-to-end delay guarantee problem into a set of single-hop delay guarantee problems along the path of each data flow in a network. When the end-to-end delay requirement changed, the authors solved this problem by feedback. The problem they studied is similar to ours, but their solution needs recalculating all the single-hop delays and rescheduling all the nodes on the data flow path.

The algorithm proposed in [2] can provide the optimal wake-up scheduling algorithm for minimizing energy consumption and limiting the maximum end-to-end delay simultaneously. We use it to get the initial wake-up schedules and routes and name it as Initial Algorithm in this paper. The challenge is to find an adaptive scheduling and routing adjustment algorithm for guaranteeing dynamic end-to-end delay requirement while minimizing energy consumption and the impact on other regions, when the delay requirement of a region A changes. Towards this end, we do some exploratory research, which is named as Adaptive Adjustment Algorithm. The proposed adjustment algorithm merely modifies the route path and duty cycle of those nodes which transmit or relay the data from trigger node, so as to minimize the energy consumption of the additional data and minimize the impact on the other paths. The brief procedure is as follows: all relay nodes on the path from trigger node to the sink will be processed one by one. We first search all the nodes in the communication range of the current relay node and find whether there is an agent node that can meet the new end-to-end delay requirement. If there is such an agent node, the current relay node just needs to change its route to the agent node. If none of them meets the new delay requirement, we firstly use adaptive adjustment algorithm to change the duty cycle and increase the wake-up frequency of the current relay node, then find an agent node around the current relay node again. This procedure will be repeated on the path from the trigger node to the sink till finding a suitable agent node. In the adaptive adjustment algorithm, we calculate the new wake-up frequency based on the energy consumption of all nodes on the path, the energy consumption of the current relay node, and the new end-to-end delay requirement. If the new wake-up frequency exceeds an upper threshold, we let the node stop sleeping since frequently switching between sleep and working states shall bring more energy consumption [3]. We also prove that the adaptive adjustment algorithm can guarantee the optimal assignment of frequency to achieve the optimum distribution of energy. In general, a distributed algorithm is more flexible for WSNs than a centralized one [4]. So, we implement the algorithm in a distributed way. The contributions of the proposed scheme are summarized as follows.

• (i)

  It makes the nodes automatically adapt to the new delay requirements when events happen.

• (ii)

  It minimizes energy consumption and the impact on other paths while guaranteeing dynamic end-to-end delay requirement in a region.

• (iii)

  With the increasing scale of nodes, the energy consumption of the proposed algorithm is constantly close to the optimal algorithm.

• (iv)

  It has good stability for all kinds of tree-topology networks.

The rest of this paper is organized as follows. Section 2 surveys the related works from the literature. In Section 3, we give the problem description. The initial algorithm is summarized in Section 4. In Section 5, we detail the proposed scheduling and routing scheme and the adaptive adjustment algorithm. In Section 6, we describe detailed procedure in a real wireless sensor network. Section 7 illustrates simulation results for the proposed method and shows its performance. Section 8 concludes the paper.

2. Related Work

To shorten the end-to-end delay in WSNs, many literatures have focused on how to trade off between energy consumption and end-to-end delay caused by sleep. In S-MAC protocol [5], sensor nodes were divided into different virtual clusters. All the sensor nodes in a same virtual cluster adopted same sleep scheduling policy for energy saving. However, delay will increase with the increase of the number of transmission hops. In literatures [6–8], DMAC protocol and some improved DMAC protocols were proposed; these protocols greatly reduce delay while saving energy consumption. The shortcoming is that they cannot guarantee end-to-end delay due to retransmission incurred by data loss. Meanwhile, they were effective to unidirectional data flow while the reverse data flow will lead to greater delay. Q-MAC [9] can balance the tradeoff between energy consumption and the sleeping delay in query-based sensor networks by predicting nodes’ wake-up time using query commands. The authors of [10] presented and evaluated a packet scheduling policy and routing algorithm called RACE that inherently accounts for time constraints. However, both Q-MAC and the sleep scheduling in [10] only aimed to minimize but not guarantee the end-to-end delay. The authors of [11] proposed a methodology to provide a time-division cluster scheduling (TDCS) mechanism. The objective is to meet all end-to-end deadlines of a predefined set of time-bounded data flows while minimizing the energy consumption of the nodes by setting the TDCS period as long as possible. In literature [12], a solution was provided to the joint control problem of how to optimally control the system parameters of the sleep-wake scheduling protocol and the anycast packet-forwarding protocol to maximize the network lifetime, subject to a constraint on the expected end-to-end packet-delivery delay. The authors of [13] proposed a novel sleep scheduling method to reduce the delay of alarm broadcasting from any sensor node in WSNs. However, the sleep scheduling mentioned above was lack of flexibility when new tasks are added into the original schedule.

Other researchers worked on the delay guaranteed scheduling and routing strategies. In [14], the authors proposed delay guaranteed routing and MAC protocol (DGRAM) which was a TDMA-based protocol designed to provide deterministic delay guarantee in energy-efficient manner. Another tree-based delay guaranteed and energy efficient MAC protocol (TDGEE) was proposed in [15]. TDGEE was a cross-layered TDMA-based MAC protocol, which was energy efficient and delay guaranteed based on the tree topology. Unfortunately, both of them are TDMA-based and need carefully slot computation, so they may bring extra synchronization overheads. The authors of [2] proposed an algorithm for maximizing the lifetime of a sensor network while guaranteeing an upper bound on the end-to-end delay. It was mainly based on different wake-up frequency distributions of node in a network. However, the algorithm should take wake-up frequency distribution of all the nodes as a priori knowledge. Therefore, it cannot adapt to the case that the wake-up frequency of reporting sensor node has to change due to more precise observation requirement. Indeed, the aim of our study is how to quickly adjust the wake-up schedule or the routing table with minimum energy cost so as to satisfy the new delay requirement.

3. Problem Description

In many WSNs, sensor nodes collect information of the environment continuously, and then these data are transmitted to the sink through a chain of relay nodes. We call the sensor nodes as source nodes, which only collect the data instead of forwarding data for other nodes. When the source node periodically reports data, the reporting delay must be less than or equal to the reporting cycle. In WSNs, delay mainly consists of three parts: transmission delay, processing delay, and sleep delay. To maximize network lifetime, the sleep cycle is usually set as long as possible, for example, several seconds or above, so the transmission delay and the processing delay can be ignored. Hence, the upper boundary of the end-to-end delay depends on cumulative sleep delay. On the other hand, even if the data reporting cycle is less than the sleep cycle, the data cannot be sent because the node is in sleep state when reporting cycle arrives. Therefore, it is reasonable to set the sleep cycle equal to the reporting cycle. As a result, the upper boundary of the reporting end-to-end delay is the cumulative sleep delay, and its lower boundary is the reporting cycle of source node. So, we set the reporting cycle equal to the end-to-end delay in order to minimize the energy consumption while guaranteeing the end-to-end delay. Hence, we usually set the reporting cycle equal to the delay requirement in practice, and the two terms are used interchangeably in this paper.

When a WSN begins running, the entire network has same delay requirement; this is static scheduling phase, and initial schedule and route of each node should be calculated in order to minimize the energy while guaranteeing a fixed end-to-end delay. Due to the dynamic change of environment, the reporting cycle of a region needs change due to more precise observation requirement; this is dynamic scheduling phase. To meet new end-to-end delay requirement of the region, we can recalculate the schedule and route of each node according to the method in static scheduling phase. However, the solution will improve the energy consumption of the entire network because the wake-up frequency of each node rises, and this makes the network consume much more extra energy. In dynamic scheduling phase, we can consider two kinds of solutions. One solution is to adjust the wake-up frequency of each node along the original path from the source node to the sink node. Because the energy consumption of wake-up is greater than that of sending one packet [16], we hope to adjust the smallest number of nodes on the original routing path. Therefore, the main work of the paper is to find an optimal solution to make the minimal adjustment in order to maximize the reduction of the extra energy consumption.

The optimal solution is to make local adjustment on the original routing path; for example, as shown in Figure 1, source node $v_{\mathrm{1}}$ reports data to the sink node $v_{\mathrm{5}}$ along the routing path marked by thick line; when source node $v_{\mathrm{1}}$ has to shorten its reporting cycle from $T_{\mathrm{1}}$ to $T_{\mathrm{2}}$ , it searches in its communication set $W_{v_{\mathrm{1}}}$ and finds whether a relay node in set $W_{v_{\mathrm{1}}}$ satisfies the delay requirement or not. If $v_{\mathrm{1}}$ cannot find such a relay node, then it notifies $v_{\mathrm{2}}$ along the original routing path, and thus $v_{\mathrm{2}}$ searches in its communication set. If $v_{\mathrm{2}}$ cannot find a relay node, then it rises up its wake-up frequency and notifies $v_{\mathrm{3}}$ . If $v_{\mathrm{3}}$ finds out such a relay node $u_{\mathrm{1}}$ , it uses this relay node as the agent node to deliver its subsequent data along the routing path marked by dotted line. Otherwise, we rise up the frequency of $v_{\mathrm{3}}$ and continue the searching process at $v_{\mathrm{3}}$ 's next-hop node $v_{\mathrm{4}}$ in the original path. The searching process is performed from the source node to the sink until an appropriate agent node is found.

Figure 1

A sensor network (the routing paths to the sink node are marked by thick lines).

Subsequently, we briefly introduce Initial Algorithm [2] in static scheduling phase and propose an adaptive and distributed algorithm in dynamic scheduling phase.

4. Initial Algorithm

Because no node needs source node to forward data, the source nodes will not affect the end-to-end delays of other nodes. As a result, the authors of [2] modeled a network by simplifying the original tree topology into a corresponding T-tree that ignores all the source nodes. In the corresponding T-tree   $G=(V,E)$ , V is the set of all the relay nodes and E is the set of all the edges. Assume that the reporting cycle is $T_{\mathrm{1}}$ for all the source nodes in a network. After the corresponding T-tree G is created, we can use the Initial Algorithm to calculate the optimal wake-up frequency $f_v$ for each relay node v. The calculation method of node's wake-up frequency is given as Algorithm 1.

Algorithm 1.

Initial Scheduling and Routing Algorithm.

• (1)

Calculate frequency division in the T-tree. The function Calculate-Frequency-Division(v) receives a node v and returns the delay $D(v)$ on the subtree rooted at v as a function of the amount of energy $E(v)$ assigned to this subtree. From the sink node, they perform this function to get the subtree delay denoted by  $D(v)$ , the partition of energy assigned to node v denoted by $e(v)$ , the partition of the energy assigned to the subtree rooted at each child node v: $E(u_{\mathrm{1}}),\dots ,E(u_N)$ , and the coefficient $B_v$ according to $D(v)=\mathrm{1}/(B_{v}E(v))=\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{1}/(B_v(e(v)+{\sum }_{i=\mathrm{1}}^{n}E(u_i)))$ . After recursively calling this function for all its children $u_i$ , $i=\mathrm{1},\dots ,n$ , we finally obtain the frequency division for all the nodes in the T-tree.

(2)

Set $D(\text{sink})=T_{\mathrm{1}}$ and compute $E(\text{sink})$ using $E(v)=\mathrm{1}/(B_{v}D(v))$ .

(3)

Assign frequencies to each node in the T-tree. The function Assign-Frequencies( $v,E(v)$ ) calculates the node's wake-up frequency $f_v$ . From the sink node, they perform this function to get the wake-up frequency of current node. After recursively calling this function for all its children $u_i$ using $E(u_i)$ got in $\text{Step}\mathrm{\hspace{0.17em}\hspace{0.17em}}(1)$ , then we obtain the wake-up frequency for all the nodes in the T-tree.

This algorithm can guarantee that the delay on each path from the leaf to the sink is less than or equal to the end-to-end delay requirement. For example, there is a path $v_{\mathrm{1}}\to \cdots \to v_n$ . Let $d_{v_{\mathrm{1}}}$ denote the reporting delay from node $v_{\mathrm{1}}$ to the sink $v_n$ and $T_{\mathrm{1}}$ denotes the end-to-end delay requirement. Since $d_{v_{\mathrm{1}}}={\sum }_{v\in \{v_{\mathrm{1}},\dots ,v_N\}}‍(\mathrm{1}/f_v)$ and $d_{v_{\mathrm{1}}}\le T_{\mathrm{1}}$ , we can get ${\sum }_{v\in \{v_{\mathrm{1}},\dots ,v_N\}}(‍\mathrm{1}/f_v)\le T_{\mathrm{1}}$ .

Besides, this algorithm has the following characteristics.

• (i)

  The reporting delay on each path from the leaves to the root is equal, and those paths are fixed.

• (ii)

  The reporting cycle on each path from the leaves to the root is equal to the delay requirement.

• (iii)

  The reporting delay from a leaf to a relay node is inversely proportional to the energy consumption of the subtree rooted at the relay node.

Now, let us see the energy consumption according to the Initial Algorithm when the reporting cycle is $T_{\mathrm{1}}$ , The total energy consumption per second, denoted by E, is

$$\begin{array}{cc}& E=E_r+\frac{E_s}{T_{\mathrm{1}}},\end{array}$$

(1)

$$\begin{array}{cc}& E_r=\sum _{v\in V}‍f_v{c}_v,\end{array}$$

(2)

$$\begin{array}{cc}& E_s=c_{s}n.\end{array}$$

(3)

In the previous equations, $f_v$ is the wake-up frequency of relay node v calculated by the initial algorithm, $c_v$ denotes the average energy consumption of relay node v during the wake-up period, and hence $E_r$ denotes the average energy consumption of all the relay nodes per second; $c_s$ denotes the average energy consumption of one source node per collection, n is the number of source nodes in the network, and thus $E_s$ is the energy consumption of all the source nodes in the network with the reporting cycle $T_{\mathrm{1}}$ .

5. Adaptive Adjustment Algorithm

5.1. Problem Formulation

Using the Initial Algorithm, the entire network has same transmission delay which is equal to the tolerant delay. When there is an emergency or users want to quickly obtain data in a region, for example, the reporting cycle in the region A needs to be changed to $T_{\mathrm{2}}$ and $T_{\mathrm{2}}$ is less than $T_{\mathrm{1}}$ , as shown in Figure 1, the Initial Algorithm cannot perform local adjustment. Our purpose is to locally adjust some nodes’ reporting cycles and their routes to the sink with the minimum energy consumption while guaranteeing the new reporting cycle $T_{\mathrm{2}}$ .

Firstly, let us study the extra cost when the reporting cycle of some nodes becomes $T_{\mathrm{2}}$ . The energy consumption per second, $E^{\prime }$ , can be denoted as follows:

$$\begin{array}{cc}& E^{\prime }=E_r^{\prime }+\frac{E_s^{\prime }}{T_{\mathrm{2}}}+\frac{E_c}{t},\end{array}$$

(4)

$$\begin{array}{cc}& E_r^{\prime }=\sum _{v\in V}‍f_v^{\prime }{c}_v,\end{array}$$

(5)

$$\begin{array}{cc}& E_s^{\prime }=c_s{n}^{\prime }+c_s\frac{T_{\mathrm{2}}}{T_{\mathrm{1}}}\left(n-n^{\prime }\right),\end{array}$$

(6)

$$\begin{array}{cc}& E_c=e·\text{num}.\end{array}$$

(7)

In the previous equations, $f_v^{\prime }$ is the new wake-up frequency of relay node v, so $E_r^{\prime }$ denotes the new average energy consumption of all the relay nodes per second; t is the duration that the region A keeps its reporting cycle with $T_{\mathrm{2}}$ , and $n^{\prime }$ is the number of the source nodes in the region A, so $E_s^{\prime }/T_{\mathrm{2}}$ is the energy consumption per second of the sensor nodes in the region A; e represents the communication overhead per node due to adjusting the node wake-up frequency, and $\text{num}$ is the number of relay nodes which should adjust wake-up frequency; thus, $E_c$ is the communication overhead generated by adjusting the corresponding node's sleep schedule. Comparing (4) with (1), we can get that the extra cost when the delay requirement of some nodes changes from $T_{\mathrm{1}}$ to $T_{\mathrm{2}}$ , denoted by $E_a$ , is

$$\begin{array}{cc}& E_a=E^{\prime }-E=\left(E_r^{\prime }-E_r\right)+\left(\frac{E_s^{\prime }}{T_{\mathrm{2}}}-\frac{E_s}{T_{\mathrm{1}}}\right)+\frac{E_c}{t}.\end{array}$$

(8)

According to (3) and (6), the second part in (8) is

$$\begin{array}{l}\frac{E_s^{\prime }}{T_{\mathrm{2}}}-\frac{E_s}{T_{\mathrm{1}}}=\frac{c_s{n}^{\prime }}{T_{\mathrm{2}}}+\frac{c_s\left(n-n^{\prime }\right)}{T_{\mathrm{1}}}-\frac{c_{s}n}{T_{\mathrm{1}}}\\ =c_s{n}^{\prime }\left(\frac{\mathrm{1}}{T_{\mathrm{2}}}-\frac{\mathrm{1}}{T_{\mathrm{1}}}\right).\end{array}$$

(9)

Since $c_s$ , $n^{\prime }$ , $T_{\mathrm{1}}$ , and $T_{\mathrm{2}}$ are predefined constants, we set $E_s^{\prime }/T_{\mathrm{2}}-E_s/T_{\mathrm{1}}$ as a constant Q.

According to (2) and (5), we have $E_r^{\prime }-E_r={\sum }_{v\in V}‍(f_v^{\prime }-f_v)c_v$ . Let us divide all the relay nodes into two sets $V^{\prime }$ and ${\bar{V}}^{\prime }(V^{\prime }+\overline{V^{\prime }}=V)$ . $V^{\prime }$ consists of the necessary relay nodes which change report cycle to $T_{\mathrm{2}}$ . $\overline{V^{\prime }}$ consists of the rest relay nodes which keep report cycle at $T_{\mathrm{1}}$ . In order to minimize the impact on other paths, we set

$$\begin{array}{cc}& f_v^{\prime }=f_v\hspace{1em}\text{when}\mathrm{\hspace{0.17em}\hspace{0.17em}}v\in \overline{V^{\prime }},\\ f_v^{\prime }\ge f_v\hspace{1em}\text{when}\mathrm{\hspace{0.17em}\hspace{0.17em}}v\in V^{\prime }.\end{array}$$

(10)

As a result, we can obtain

$$\begin{array}{l}{E}_r^{\prime }-E_r=\sum _{v\in V}‍\left(f_v^{\prime }-f_v\right)c_v\\ =\sum _{v\in \left(V^{\prime }+\overline{V^{\prime }}\right)}‍\left(f_v^{\prime }-f_v\right)c_v\\ =\sum _{v\in V^{\prime }}‍\left(f_v^{\prime }-f_v\right)c_v.\end{array}$$

(11)

Bring the results of (7), (9), and (11) into (8) we have

$$\begin{array}{cc}& E_a=E^{\prime }-E=\sum _{v\in V^{\prime }}‍\left(f_v^{\prime }-f_v\right)c_v+Q+e·\frac{\text{num}}{t}\end{array}$$

(12)

or

$$\begin{array}{cc}& E^{\prime }=E+\sum _{v\in V^{\prime }}‍f_v^{\prime }{c}_v-\sum _{v\in V^{\prime }}‍f_v{c}_v+Q+e·\frac{\text{num}}{t}.\end{array}$$

(13)

Here, $E,f_v$ are calculated via the Initial Algorithm, $c_v,e$ depend on the device, and $Q,t$ are predefined. So, we can regard them as constants. Then, the objective of the problem is

$$\begin{array}{cc}& \min \left(\sum _{v\in V^{\prime }}‍f_v^{\prime }{c}_v+e·\frac{\text{num}}{t}\right)\end{array}$$

(14)

subject to: $f_v^{\prime }\ge f_v$ (for all $v\in V^{\prime }$ ) and $d_{v_{\mathrm{1}}}\le T_{\mathrm{2}}$ .

The adaptive adjustment problem is NP-hard, so we shall propose the heuristic algorithm to attain the suboptimal solution locally with limited computation. Before discussing the heuristic algorithm, we first study the lower boundary of the optimal solution and use it as the standard to verify the performance of the adjustment algorithms.

5.2. The Lower Boundary of Optimal Solution

According to the objective function (14), the ideal conditions are $f_v^{\prime }=f_v$ (for all $v\in V^{\prime }$ ) and $\text{num}=\mathrm{0}$ . When $\text{num}=\mathrm{0}$ , it means that no node needs to change its route or schedule, but this method may lead to $d_{v_{\mathrm{1}}}=T_{\mathrm{1}}\ge T_{\mathrm{2}}$ and against the constraint. Obviously, a feasible solution is to transmit the data through other paths. Ideally, we only need to adjust the routes without adjusting all wake-up frequencies. In this case, the extra energy is $Q+e*\text{num}/t$ , where $\text{num}$ is an indeterminate value for different topologies or different trigger regions. So we set $\text{num}=\mathrm{0}$ and regard it as the lower boundary of the optimal solution. In the heuristic algorithm, we will also only reallocate frequency on the reporting path and partially adjust the route to reduce overall cost, while keeping $\text{num}$ as a variable.

Therefore, the key challenge here is to select the minimum number of nodes to be adjusted and reassign wake-up frequency for them.

5.3. Optimal Assignment Theory

For presenting the adaptive adjustment algorithm, we first describe and prove an optimal assignment theory which is used in the algorithm.

Theorem 2.

${\sum }_{i=\mathrm{1}}^n‍\mathrm{1}/a_i=A$ , ${\sum }_{i=\mathrm{1}}^n‍b_i=B$ , ${\sum }_{i=\mathrm{1}}^n‍\sqrt{b_i}=C$ , $a_i,b_i$ are positive, and $n,A,B$ are constants. If and only if $a_i=C/(A\sqrt{b_i}$ ), then ${\sum }_{i=\mathrm{1}}^n‍a_i{b}_i$ will be minimum.

Proof.

We have

$$\begin{array}{l}A\sum _{i=\mathrm{1}}^n‍a_i{b}_i\\ \hspace{1em}\hspace{1em}=\sum _{i=\mathrm{1}}^n‍\frac{\mathrm{1}}{a_i}\times \sum _{i=\mathrm{1}}^n‍a_i{b}_i\\ \hspace{1em}\hspace{1em}=\sum _{i=\mathrm{1}}^n‍b_i+\sum _{i=\mathrm{1}}^n‍\frac{{\sum }_{j=\mathrm{1},j\ne i}^n{a}_i{b}_i}{a_i}\\ \hspace{1em}\hspace{1em}=B+\frac{a_{\mathrm{2}}{b}_{\mathrm{2}}+a_{\mathrm{3}}{b}_{\mathrm{3}}+\cdots +a_n{b}_n}{a_{\mathrm{1}}}\\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{a_{\mathrm{1}}{b}_{\mathrm{1}}+a_{\mathrm{3}}{b}_{\mathrm{3}}+\cdots +a_n{b}_n}{a_{\mathrm{2}}}+\cdots \\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{a_{\mathrm{1}}{b}_{\mathrm{1}}+\cdots +a_{k-\mathrm{1}}{b}_{k-\mathrm{1}}+a_{k+\mathrm{1}}{b}_{k+\mathrm{1}}+\cdots +a_n{b}_n}{a_k}+\cdots \\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{a_{\mathrm{1}}{b}_{\mathrm{1}}+a_{\mathrm{2}}{b}_{\mathrm{2}}+\cdots +a_{n-\mathrm{1}}{b}_{n-\mathrm{1}}}{a_n}\\ \hspace{1em}\hspace{1em}=B+\left(\frac{a_{\mathrm{2}}{b}_{\mathrm{2}}}{a_{\mathrm{1}}}+\frac{a_{\mathrm{1}}{b}_{\mathrm{1}}}{a_{\mathrm{2}}}\right)+\left(\frac{a_{\mathrm{3}}{b}_{\mathrm{3}}}{a_{\mathrm{1}}}+\frac{a_{\mathrm{1}}{b}_{\mathrm{1}}}{a_{\mathrm{3}}}\right)+\cdots \\ \hspace{1em}\hspace{1em}\hspace{1em}+\left(\frac{a_n{b}_n}{a_{\mathrm{1}}}+\frac{a_{\mathrm{1}}{b}_{\mathrm{1}}}{a_n}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\left(\frac{a_{\mathrm{3}}{b}_{\mathrm{3}}}{a_{\mathrm{2}}}+\frac{a_{\mathrm{2}}{b}_{\mathrm{2}}}{a_{\mathrm{3}}}\right)+\left(\frac{a_{\mathrm{4}}{b}_{\mathrm{4}}}{a_{\mathrm{2}}}+\frac{a_{\mathrm{2}}{b}_{\mathrm{2}}}{a_{\mathrm{4}}}\right)+\cdots \\ \hspace{1em}\hspace{1em}\hspace{1em}+\left(\frac{a_n{b}_n}{a_{\mathrm{2}}}+\frac{a_{\mathrm{2}}{b}_{\mathrm{2}}}{a_n}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\cdots +\left(\frac{a_{n-\mathrm{1}}{b}_{n-\mathrm{1}}}{a_{n-\mathrm{2}}}+\frac{a_{n-\mathrm{2}}{b}_{n-\mathrm{2}}}{a_{n-\mathrm{1}}}\right)+\left(\frac{a_n{b}_n}{a_{n-\mathrm{2}}}+\frac{a_{n-\mathrm{2}}{b}_{n-\mathrm{2}}}{a_n}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\left(\frac{a_n{b}_n}{a_{n-\mathrm{1}}}+\frac{a_{n-\mathrm{1}}{b}_{n-\mathrm{1}}}{a_n}\right)\\ \hspace{1em}\hspace{1em}=B+\sum _{i=\mathrm{1}}^{n-\mathrm{1}}‍\sum _{j=i+\mathrm{1}}^n‍\left(\frac{a_j{b}_j}{a_i}+\frac{a_i{b}_i}{a_j}\right).\end{array}$$

(15)

Since A and B are constants, ${\sum }_{i=\mathrm{1}}^n‍a_i{b}_i$ will be minimum when ${\sum }_{i=\mathrm{1}}^{n-\mathrm{1}}‍{\sum }_{j=i+\mathrm{1}}^n‍(a_j{b}_j/a_i+a_i{b}_i/a_j)$ is minimum. As $(a_j{b}_j/a_i+a_i{b}_i/a_j)>\mathrm{0}$ for any i and j, we get that if any one of $(a_j{b}_j/a_i+a_i{b}_i/a_j)>\mathrm{0}$ is not minimum, ${\sum }_{i=\mathrm{1}}^{n-\mathrm{1}}‍{\sum }_{j=i+\mathrm{1}}^n‍(a_j{b}_j/a_i+a_i{b}_i/a_j)$ will not be minimum. In other words, if ${\sum }_{i=\mathrm{1}}^{n-\mathrm{1}}‍{\sum }_{j=i+\mathrm{1}}^n‍(a_j{b}_j/a_i+a_i{b}_i/a_j)$ is minimum, each of $(a_j{b}_j/a_i+a_i{b}_i/a_j)$ should be minimum. By the binary average value inequality, $(a_j{b}_j/a_i+a_i{b}_i/a_j)$ is minimum when $(a_j{b}_j/a_i\hspace{0.17em}+\hspace{0.17em}{a}_i{b}_i/a_j)$ for any i and j. That is,

$$\begin{array}{cc}& a_{\mathrm{1}}\sqrt{b_{\mathrm{1}}}=a_{\mathrm{2}}\sqrt{b_{\mathrm{2}}}=\cdots =a_n\sqrt{b_n}.\end{array}$$

(16)

Substituting (16) into ${\sum }_{i=\mathrm{1}}^n‍\mathrm{1}/a_i=A$ , we have $A=\sqrt{b_1}/{(a}_1\sqrt{b_1})+\sqrt{b_2}/(a_1\sqrt{b_1})+\cdots +\sqrt{b_n}/(a_1\sqrt{b_1})=({\sum }_{i=\mathrm{1}}^n\sqrt{b_i})/(a_{\mathrm{1}}\sqrt{b_{\mathrm{1}}})=C/(a_1\sqrt{b_1})$ . Then, we get $a_{\mathrm{1}}=C/(A\sqrt{b_{\mathrm{1}\mathrm{\hspace{0.17em}\hspace{0.17em}}}})$ . Similarly, we can get $a_{\mathrm{2}}=C/(A\sqrt{b_{\mathrm{2}}}),\dots ,a_n=C/(A\sqrt{b_n})$ . So, we prove that ${\sum }_{i=\mathrm{1}}^n‍a_i{b}_i$ will be minimum when $a_n=C/(A\sqrt{b_n})$ . This finishes the proof.

5.4. Adaptive Adjustment Algorithm

Definition 3.

In a WSN, the communication set of node v denoted as $W_v$ is the set of nodes within the communication radius of node v.

Algorithm 4.

Adaptive Adjustment Algorithm.

• (1)

Search all the nodes in the communication set $W_{v_{\mathrm{1}}}$ of source node $v_{\mathrm{1}}$ . If we find a node v with the delay $d_v$ which is less than the required delay $d=T_{\mathrm{2}}-\mathrm{1}/f_{v_{\mathrm{1}}}$ , v is the agent node. Set v as the next-hop node of $v_{\mathrm{1}}$ and stop the process. If not, go to $\text{Step}\mathrm{\hspace{0.17em}\hspace{0.17em}}(2)$ .

(2)

Set the required delay $d=T_{\mathrm{2}}$ .

(3)

Calculate the new frequency of current node $v_i$ according to (17), that is, $f_{v_i}^{\prime }=C/{(T}_{\mathrm{2}}\sqrt{c_{v_{i\mathrm{\hspace{0.17em}\hspace{0.17em}}}}})$ . Compare it with the original frequency $f_{v_i}$ and the upper threshold of frequency $f_{\max }$ . if $f_{v_i}^{\prime }\ge f_{\max }$ , set $f_{v_i}=\infty$ which means the node is no longer sleep; If $f_{v_i}^{\prime }\le f_{v_i}$ , then keep $f_{v_i}$ as its old value; otherwise, change the frequency of current node $v_i$ to $f_{v_i}=f_{v_i}^{\prime }$ . Go to $\text{Step}\mathrm{\hspace{0.17em}\hspace{0.17em}}(4)$ .

(4)

Modify the required delay to  $d=d-\mathrm{1}/f_{v_i}$ . Then, search all the nodes in the communication set $W_{v_i}$ of node ${\mathrm{\hspace{0.17em}\hspace{0.17em}}v}_i$ . If we find a node v with the delay $d_v$ which is less than the required delay d, v is the agent node. Set v as the next-hop node of $v_i$ and stop the process. If not, go to $\text{Step}\mathrm{\hspace{0.17em}\hspace{0.17em}}(5)$ .

(5)

If the node is sink, the algorithm ends. Otherwise, send an adjustment message with parameters d and C to the next relay node on the reporting path.

(6)

When a relay node receives such an adjustment message, repeat $\text{Step}\mathrm{\hspace{0.17em}\hspace{0.17em}}(3)$ and $\text{Step}\mathrm{\hspace{0.17em}\hspace{0.17em}}(\mathrm{4})$   on the current node.

We use optimal assignment theory proved in Section 5.3 to determine the new frequencies of the relay nodes on the path. According to Theorem 2, we should know how many relay nodes need to adjust their frequencies. However, the number of nodes that should be adjusted will vary with the conditions (i.e. topology, delay requirement, and trigger node). Here, we study the worst case that all the relay nodes on the original path from $v_{\mathrm{1}}$ to the sink need to increase their frequencies. In the worst case, $\text{num}$ in the objective function ${\sum }_{v\in V^{\prime }}‍f_{v_{}}^{\prime }{c}_v+e·\text{num}/t$ is constant for the special source node $v_1$ . Therefore, the objective is to minimize ${\sum }_{v\in V^{\prime }}‍f_{v_{}}^{\prime }{c}_v$ . Using Theorem 2, we set $a_i$ as $f_{v_{}}^{\prime }$ and $b_i$ as $c_v$ . Since all the $c_v$ are constants, so both $A={\sum }_{i=\mathrm{1}}^n‍\mathrm{1}/a_i={\sum }_{v_i\in \{v_{\mathrm{1}},\dots ,v_N\}}‍\mathrm{1}/f_{v_i}^{\prime }=T_{\mathrm{2}}$ and $B={\sum }_{i=\mathrm{1}}^n‍b_i={\sum }_{v_i\in \{v_{\mathrm{1}},\dots ,v_N\}}‍c_{v_i}$ are constants too. As a result, the new frequency of each relay node on the original path from $v_{\mathrm{1}}$ to the sink is

$$\begin{array}{cc}& f_{v_i}^{\prime }=\frac{C}{T_{\mathrm{2}}\sqrt{c_{v_i}}},\hspace{1em}\left(\text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}}C=\sum _{v_i\in \left\{v_{\mathrm{1}},\dots ,v_N\right\}}‍\sqrt{c_{v_i}}\right).\end{array}$$

(17)

Hence, we get the optimal energy assignment theory as Corollary 5.

Corollary 5.

Let $T_{\mathrm{2}}$ be the new end-to-end delay requirement, $c_{v_i}$ the energy consumption per second of current relay node, and $C={\sum }_{v_i\in \{v_{\mathrm{1}},\dots ,v_N\}}\sqrt{c_{v_i}}$ . The nodes will achieve optimum distribution of energy by adjusting their frequencies according to $f_{v_i}^{\prime }=C/(T_{\mathrm{2}}\sqrt{c_{v_i}})$ .

According to Corollary 5, we summarize the adaptive adjustment algorithm as Algorithm 4.

6. Adaptive Scheduling and Routing Procedure

6.1. Initialization Procedure

In the initialization procedure, we design two types of messages: the upstream message “Info” and the downstream message “Notify.” Via “Info,” children nodes report their own control parameters including coefficient factor B to their parent nodes. Through “Notify,” parent node sends its own control parameters (including frequency f and delay d) to its children nodes. Figure 2 illustrates the workflow of the initialization procedure. In Figure 2, s is a sensor node, $R_n,R_{n-\mathrm{1}},\dots ,R_{\mathrm{2}}$ and $R_{\mathrm{1}}$ denote the router nodes on the path from source s to the sink node a, so $R_n$ is the leaf node in the routing tree (T-tree). Source s reports data to the sink a with cycle $T_{\mathrm{1}}$ . The workflow is described in Figure 2.

Figure 2

The workflow of the initialization procedure.

Step 1.

All the source nodes collect data according to a predefined cycle $T_{\mathrm{1}}$ .

Step 2.

$R_n$ sets the total energy of the tree rooted at it to 1, that is, $e(n)=\mathrm{1}$ , and calculates its coefficient factor $B_n=\mathrm{1}/c_n$ . Then, $R_n$ sends the coefficient $B_n$ to its directed parent node $R_{n-\mathrm{1}}$ .

Step 3.

The total energy of the tree rooted at $R_{n-\mathrm{1}}$ is set to “1.” When $R_{n-\mathrm{1}}$ receives the coefficient factors B of its children nodes, it calculates its own energy $e(n-l)$ , its coefficient factor $B_{n-\mathrm{1}}$ , and the assigned energy $E(u_i)$ of the subtrees rooted at its children nodes. Then, $R_{n-\mathrm{1}}$ sends the coefficient $B_{n-\mathrm{1}}$ to its directed parent node $R_{n-\mathrm{2}}$ . The above process is repeated until the sink node a receives the coefficient factor B of each child node.

Step 4.

Sink node a receives the coefficient factors B of its children nodes and calculates $e(a)$ , $B_a$ , and $E(u_i)$ . Then, the sink node calculates the actual energy consumption $E^{\prime }(a)$ of the whole network according to the predefined cycle $T_{\mathrm{1}}$ via $E^{\prime }(a)=\mathrm{1}/(B_a{T}_{\mathrm{1}})$ ; the actual energy consumption of sink node $e^{\prime }(a)=E^{\prime }(a)e(a)$ ; the actual energy assigned to the subtree rooted at each child node $E^{\prime }(u_i)=E^{\prime }(a)E(u_i)$ ; and its wake-up frequency $f_a=e^{\prime }(a)/c_a$ . Based on the wake-up frequency, sink node a computes the end-to-end delay requirement $d=\mathrm{1}/f_a$ and $C=\sqrt{c_a}$ . Finally, Sink node a sends the parameters $E^{\prime }(u_i)$ , C, d, and ${\mathrm{\hspace{0.17em}\hspace{0.17em}}f}_a$ to all of its children nodes.

Step 5.

$R_{n-\mathrm{1}}$ receives message from its parent node, same as Step 4, calculates its actual energy consumption $e^{\prime }(n-\mathrm{1})=E^{\prime }(n-\mathrm{1})e(e-\mathrm{1})$ and the actual energy assigned to the subtree rooted at its child node $E^{\prime }(u_i)=E^{\prime }(n-\mathrm{1})E(u_i)$ , then, accumulates the end-to-end delay $d=d+\mathrm{1}/f_{n-\mathrm{1}}$ and $C=C+\sqrt{c_{n-\mathrm{1}}}$ . Finally, $R_{n-\mathrm{1}}$ sends the parameters $E^{\prime }(u_i)$ , C, d, and $f_{\text{n}-\mathrm{1}}$ to all of its children nodes until the leaf node $R_n$ is reached.

Step 6.

$R_n$ calculates various parameters in the same manner and notifies its wake-up frequency $f_n$ to the source node s. As a result, all the nodes in the network work with a fixed wake-up frequency.

6.2. Adjustment Procedure

In the adjustment procedure, we design four types of messages. “Adjust” is an upstream message which tells its next-hop node to be adjusted, including necessary control parameters. When a node wants the delay information of agent candidate nodes in the communication range, it sends a “Search” message to those nodes. Then, those nodes will return “ACK” messages with their delays to the sink node.

Figure 3 shows an example of the adaptive adjustment procedure. In Figure 3, $R_n^{N_i}$ represents the ith neighbor node of the router $R_n$ . In an area of a wireless sensor network, when an event occurs, for example, temperature value collected by source node s exceeds a predefined threshold or the node received an adjustment command, then, s adjusts data reporting cycle to $T_{\mathrm{2}}$ . The adjustment procedure works as in Figure 3.

Figure 3

The workflow of the adaptive adjustment procedure.

Step 1.

Source node s initializes the required delay $d^{\prime }=T_{\mathrm{2}}$ and sends “Adjust” message with the parameters $d^{\prime }$ and $T_{\mathrm{2}}$ to its router node $R_n$ .

Step 2.

The router $R_n$ receives “Adjust” message with the parameters $d^{\prime }$ and ${\mathrm{\hspace{0.17em}\hspace{0.17em}}T}_{\mathrm{2}}$ and calculates a new wake-up frequency $f_n^{\prime }$ using (17), according to its reserved parameter C. If $f_n^{\prime }\ge f_{\max }$ , the node is no longer sleep. If $f_{\max }>f_n^{\prime }>f_n$ , then $R_n$ modifies its old wake-up frequency $f_n=f_n^{\prime }$ ; otherwise, $R_n$ maintains its old wake-up frequency. Then, $R_n$ notifies its wake-up frequency to all of its child nodes, updates the required delay $d_n^{\prime }=d^{\prime }-\mathrm{1}/f_n$ , and sends “Search” messages to all of its neighbor nodes $R_n^{N_i},\mathrm{\hspace{0.17em}\hspace{0.17em}}i=\mathrm{1},\dots ,m$ .

Step 3.

When the neighbor node $R_n^{N_i}$ receives the “Search” message, it responses an “ACK” message with its actual delay ${(d_n^{N_i})}^{\prime }$ to router $R_n$ .

Step 4.

$R_n$ receives all the actual delays ${(d_n^{N_i})}^{\prime },\mathrm{\hspace{0.17em}\hspace{0.17em}}i=\mathrm{1},\dots ,m$ compares them with $d_n^{\prime }$ , and calculates the minimal delay $\min ({(d_n^{N_i})}^{\prime },\mathrm{\hspace{0.17em}\hspace{0.17em}}i=\mathrm{1},\dots ,m;d_n^{\prime })$ . If the minimum is $d_n^{\prime }$ , then, $R_n$ sends “Adjust” message to its parent node $R_{n-\mathrm{1}}$ ; otherwise, $R_n$ adjusts the path to its neighbor node with the minimum actual delay, and the adjustment procedure ends.

Step 5.

When a router node $R_i\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,n-\mathrm{1})$ receives the “Adjust” message, it performs similar execution as node $R_n$ . If no router node on the original path can find an agent neighbor node to meet the delay requirement, sink node will receive the “Adjust” message.

Step 6.

When the sink node receives the “Adjust” message, it calculates a new wake-up frequency $f_a^{\prime }$ using (17). If $f_a^{\prime }>f_a$ , then the sink node modifies its old wake-up frequency $f_a=f_a^{\prime }$ ; else, the sink node maintains its old wake-up frequency. Then, the sink node notifies its wake-up frequency to all the children nodes. All the nodes continue to work in accordance with the adjusted wake-up frequency.

For example, in Figure 3, $R_n$ receives Adjust( $d^{\prime },T_{\mathrm{2}}$ ) and sends “Search” messages to all its neighbor nodes $R_n^{N_i},i=\mathrm{1},\dots ,m$ . After receiving the “ACK” message with the delay ${(d_{n-\mathrm{1}}^{N_i})}^{\prime }$ from the neighbor nodes ${\mathrm{\hspace{0.17em}\hspace{0.17em}}R}_n^{N_i}$ , ${\mathrm{\hspace{0.17em}\hspace{0.17em}}R}_n$ compares all the required delay and calculates the minimum. Due to $\min ({(d_n^{N_i})}^{\prime },i=\mathrm{1},\dots ,m;d_n^{\prime })={\mathrm{\hspace{0.17em}\hspace{0.17em}}d}_n^{\prime }$ , $R_n$ sends “Adjust” ( $d^{\prime },T_{\mathrm{2}}$ ) to its parent node $R_{n-\mathrm{1}}$ ; $R_{n-\mathrm{1}}$ receives adjustment command and then sends “Search” messages to all its neighbor nodes $R_{n-\mathrm{1}}^{N_i},i=\mathrm{1},\dots ,m$ . After receiving the “ACK” message with the delay ${(d_{n-\mathrm{1}}^{N_i})}^{\prime }$ from the neighbor nodes $R_{n-\mathrm{1}}^{N_i}$ , $R_{n-l\mathrm{\hspace{0.17em}\hspace{0.17em}}}$ computes   $\min ({(d_{n-\mathrm{1}}^{N_i})}^{\prime },i=\mathrm{1},\dots ,m;d_{n-\mathrm{1}}^{\prime })=d_{n-\mathrm{1}}^{\prime }$ . Now, since $\min ({(d_{n-\mathrm{1}}^{N_i})}^{\prime },i=\mathrm{1},\dots ,m;d_{n-\mathrm{1}}^{\prime })=d_{n-\mathrm{1}}^{\prime }$ , so, $R_{n-\mathrm{1}}$ adjusts its path. As a result, the data transmission path shown in Figure 2 adjusts to the transmission path shown in Figure 3.

7. Simulation and Analysis

We use a large number of simulation experiments to verify the performance of the adaptive scheduling and routing adjustment algorithm and study how various factors impact the algorithm performance.

7.1. Simulation Environment

We use C language to establish the simulation platform. In the simulation environment, there are N nodes in an area of $\mathrm{100}\hspace{0.17em}\text{m}\times \mathrm{100}\hspace{0.17em}\text{m}$ , both the tree topology of network and the region which needs to accelerate reporting are randomly generated. We randomly select a node as a trigger and adjust its end-to-end delay requirement of data reporting. Then, we study the effects of route adjusting and frequency adjusting in different algorithms. The communication radius of node varies between 25 m and 75 m. The original reporting cycle $T_{\mathrm{1}}$ is 20 s. For simplicity, $c_v$ is 20 mW for each relay node.

The proposed algorithm will be compared with the global adjustment algorithm, the lower boundary of optimal solution, and the local adjustment algorithm. The global adjustment algorithm will follow the smallest end-to-end delay of all regions as a global end-to-end delay to adjust the wake-up frequency. In the lower boundary of optimal solution, only the routes are adjusted, but all the wake-up frequencies are not adjusted, and it also neglects the additional communication overhead for routing modification.

In the local adjustment algorithm, all the wake-up frequencies of the nodes on the path increase to $T_{\mathrm{1}}/T_{\mathrm{2}}$ times of their original frequencies. We will, respectively, discuss the impacts of the network scale(N), new reporting cycle( $T_{\mathrm{2}}$ ), and communication radius on the performance of the adaptive adjustment algorithm.

7.2. Impact of Network Scale N

In this set of simulation, the communication radius is $\mathrm{30}\hspace{0.17em}\text{m}$ and the new reporting cycle $T_{\mathrm{2}}$ is $\mathrm{2}\hspace{0.17em}\text{s}$ . The network scale N increases from 100 to 835 in step of 15.

Figure 4 shows the relationship between the energy consumption and the network scale in the four algorithms. In Figure 4, the energy consumption of the global adjustment algorithm increases much faster with the increase of network scale compared with the other three algorithms. So, the global adjustment algorithm is unacceptable, while the energy of the other three algorithm is comparable. Next, we further study the relationship of the local algorithm, the proposed algorithm, and the lower boundary of optimal solution.

Figure 4

Energy of different node scale.

Figure 5(a) shows that the proposed algorithm and the lower boundary of optimal solution are similar in slope, but the local adjustment algorithm is larger than others. It demonstrates that the energy consumption of the proposed algorithm is the lowest growth. Meanwhile, from Figure 5(b) we can see that the ratio significantly decreases with the increase of network scale. This shows that the proposed algorithm is constantly close to the lower boundary of optimal solution with the increase of network scale.

Figure 5

Energy of different node scale.

Table 1 shows average energy consumption, maximum energy consumption gap, and ratio of them in the same node scale and different topologies. According to the data given in Table 1, the energy consumption gap of any topology is within $\mathrm{15}\%$ of the average when the network scale is larger than $\mathrm{400}$ . It goes to show that the proposed algorithm has good stability in different topologies for a large-scale network.

Table 1

Fluctuate energy of different network scales.

Node number	Average energy	Max gap	Max gap/average
$\mathrm{205}$	$\mathrm{997.5}$	$\mathrm{266.5}$	$\mathrm{0.267}$
$\mathrm{400}$	$\mathrm{1773.7}$	$\mathrm{248.2}$	$\mathrm{0.140}$
$\mathrm{610}$	$\mathrm{2600.9}$	$\mathrm{205}$	$\mathrm{0.145}$
$\mathrm{805}$	$\mathrm{3335.7}$	$\mathrm{445.7}$	$\mathrm{0.134}$

7.3. Impact of New Reporting Cycle $T_2$

The network scale N is $\mathrm{500}$ and the communication radius is $\mathrm{30}\hspace{0.17em}\text{m}$ . The new reporting cycle $T_{\mathrm{2}}$ decreases from $\mathrm{19.5}\hspace{0.17em}\text{s}$ to $\mathrm{0.5}\hspace{0.17em}\text{s}$ in step of $\mathrm{0.5}\hspace{0.17em}\text{s}$ . We run the simulation with 20 random topologies and the average energy consumptions for the three algorithms are shown in Figure 6. Since it is impossible that the adjustment of the boundary of optimal algorithm does not consume any energy when the gap between $T_{\mathrm{1}}$ and $T_{\mathrm{2}}$ is great, we ignore the result of the optimal algorithm when $T_{\mathrm{2}}$ is from $\mathrm{2}\hspace{0.17em}\text{s}$ to $\mathrm{0.5}\hspace{0.17em}\text{s}$ .

Figure 6

Energy consumption in different $T_{\mathrm{2}}$ .

Figure 6 shows that the energy consumption of the proposed algorithm is very close to the boundary of optimal algorithm when $T_{\mathrm{2}}$ changes from $\mathrm{19.5}\hspace{0.17em}\text{s}$ to $\mathrm{2}\hspace{0.17em}\text{s}$ and always less than that of the local adjustment algorithm. From $T_{\mathrm{2}}=\mathrm{10}\hspace{0.17em}\text{s}$ , the energy consumption gap between the proposed algorithm, and the local adjustment algorithm increases quickly. When $T_{\mathrm{2}}=\mathrm{2}\hspace{0.17em}\text{s}$ , the energy consumption of the proposed algorithm, the boundary of optimal algorithm and the local adjustment algorithm are $\mathrm{2206.6}\hspace{0.17em}\text{mW}$ , $\mathrm{1975.3}\hspace{0.17em}\text{mW}$ , and $\mathrm{2755.1}\hspace{0.17em}\text{mW}$ , respectively. That means the proposed algorithm can save $\mathrm{19.9}\%$ energy compared with the local adjustment algorithm and only cost $\mathrm{11.7}\%$ extra energy than the boundary of optimal algorithm. When $T_{\mathrm{2}}$ decreases to less than $\mathrm{2}\hspace{0.17em}\text{s}$ , the energy cost of the proposed algorithm is about half of the energy cost of the local adjustment algorithm.

7.4. Impact of Communication Radius

In this set of simulation, the network scale N is 500 and the new reporting cycle $T_{\mathrm{2}}$ is $\mathrm{2}\hspace{0.17em}\text{s}$ . The communication radius changes from $\mathrm{25}\hspace{0.17em}\text{m}$ to $\mathrm{75}\hspace{0.17em}\text{m}$ in step of $\mathrm{1}\hspace{0.17em}\text{m}$ . $c_v$ will change with different devices of different communication radiuses. The relationship is $c_v=\mathrm{20}(r/\mathrm{30}{)}^{\mathrm{2}}$ . We will, respectively, discuss the changes of the wake-up time and the extra energy in different communication radiuses.

Figures 7(a), 8(a), and 9(a) show the wake-up time in three topologies. In these three topologies, the wake-up times of both the local adjustment algorithm and the boundary of optimal algorithm keep constant and look like the upper and lower bounds of the proposed algorithm. That means that the proposed algorithm can significantly reduce the wake-up time through adaptive adjustment and therefore reduce the extra energy consumption.

Figure 7

Wake-up time and extra energy in topology 1.

Figure 8

Wake-up time and extra energy in topology 2.

Figure 9

Wake-up time and extra energy in topology 3.

The wake-up time of the proposed algorithm is ladder-like down and approaches the boundary of optimal algorithm when the communication radius increases from $\mathrm{25}\hspace{0.17em}\text{m}$ to $\mathrm{75}\hspace{0.17em}\text{m}$ . We analyze the phenomenon as follows. When the communication radius increases, there are four cases: $(1)$ the communication radius increases, but the communication set $W_v$ does not become larger. $(2)$ The communication radius increases and the communication set $W_v$ becomes larger, but the minimum delay of the communication set $W_v$ will not decrease. $(3)$ The communication radius increases, the communication set $W_v$ becomes larger, and the minimum delay of the communication set $W_v$ decreases, but the minimum delay still does not meet the end-to-end delay requirement. $(4)$ The communication radius increases, the communication set $W_v$ becomes larger, and the delay of one new node meets the end-to-end delay requirement. In cases $(1)$ , $(2)$ , and $(3)$ , even though the communication radius increases, the wake-up time will not change since no adjustment is needed through our adaptive adjustment algorithm. Only in case $(4)$ , the wake-up time decreases since we can find a proper agent node. Therefore, when the communication radius increases, the wake-up time keeps for a while and then jumps down when the communication radius satisfies the case $(4)$ .

Although the wake-up time of the proposed algorithm reduces with the increase of the communication radius, it does not mean the larger the communication radius is, the less the energy consumes. Figures 7(b), 8(b), and 9(b) show the extra energy consumption of the path in three topologies. We can see that with any kind of topology, the extra energy of the local adjustment algorithm and communication radius follows square rule. But the extra energy of the proposed algorithm and communication radius obeys a piecewise linear relationship. Meanwhile it hops down at some points. The reason of hopping down is same as above. The reason of the linear relationship is that the proposed algorithm uses the nearby nodes of the path as agent nodes so as to reduce extra energy. Comparing the proposed algorithm with the local adjustment algorithm, the lager the communication radius is, the bigger gap between them will be. In different networks, it is possible that nodes have different communication radiuses. Figures 7(b), 8(b), and 9(b) show that the extra energy when radius is $\mathrm{75}\hspace{0.17em}\text{m}$ is slightly larger than that of when radius is $\mathrm{25}\hspace{0.17em}\text{m}$ . So, the proposed algorithm has good adaptability and stability in different communication radiuses.

8. Conclusions

In this paper, the scheduling and routing strategies for end-to-end delay guarantee in WSNs have been studied. Firstly, we use the optimal wake-up frequency distribution algorithm proposed in [2] to initialize the wake-up schedule of nodes and guarantee the initial end-to-end delay. In the case that the end-to-end delay requirement of a region changes, we propose an adaptive adjustment algorithm to locally adjust the wake-up schedule or the routing table with the minimum energy cost while satisfying the new delay requirement. Then, we propose the detailed procedure in a real wireless sensor network. We simulate the algorithm over random sensor networks with different tree topologies and investigate the energy consumption of the network. The simulation results show that the adaptive adjustment algorithm can minimize energy consumption while guaranteeing the delay requirement. In the future work, we plan to take into account remaining energy of nodes when the frequency increases in order to balance the energy consumption of the entire network.