Energy-Efficient Soft Real-Time Scheduling for Parameter Estimation in WSNs

Abstract

In wireless sensor networks (WSNs), homogeneous or heterogenous sensor nodes are deployed at a certain area to monitor our curious target. The sensor nodes report their observations to the base station (BS), and the BS should implement the parameter estimation with sensors' data. Best linear unbiased estimation (BLUE) is a common estimator in the parameter estimation. Due to the end-to-end packet delay, it takes some time for the BS to receive sufficient data for the estimation. In some soft real-time applications, we expect that the estimation can be completed before the deadline with a probability. The existing approaches usually guarantee the real-time constraint through reducing the number of hops during data transmission. However, this kind of approaches does not take full advantage of the soft real-time property. In this paper, we proposed an energy-efficient scheduling algorithm especially for the soft real-time estimations in WSNs. Through the proper assignment of sensors' state, we can achieve an energy-efficient estimation before the deadline with a probability. The simulation results demonstrate the efficiency of our algorithm.

1. Introduction

Wireless sensor networks (WSNs) are emerging technologies, which can be widely applied in medicine, military, surveillance, and aerospace fields. Several sensors collaborate to accomplish high-level tasks. A WSN typically consists of a Base Station (BS) and several homogeneous or heterogenous sensor nodes. The sensor nodes are responsible for sampling the analog signal and transmit their local data to the BS. The BS acquires data from sensor nodes and does some relevant applications.

The parameter estimation is an important task in WSNs. Because the sensors' observations are corrupted by the noise, the BS should estimate the real value with the corrupted observed data. An estimator which achieves an acceptable estimation Mean Square Error (MSE) should be designed at the BS. Best Linear Unbiased Estimation (BLUE) [1] is a popular estimator in parameter estimation. Due to the bandwidth constraint in WSNs, authors in [2] propose the Quasi-Best Linear Unbiased Estimation (Quasi-BLUE). The estimator is simple and can give unbiased estimation. The works [2–6] are examples that employ Quasi-BLUE as the estimator in WSNs.

Since sensors may be deployed in hostile or remote areas, sometimes, the batteries replacement is impossible. To a certain sensor network, there is an upper bound on the lifetime [7]. Therefore, energy saving is very important in the applications of WSNs. The communication is the primary source of energy consumption [8]. The data transmission from sensor nodes to the BS can be directly sensor-to-destination scheme or multihop routing scheme. Due to the transmission power is proportional to the αth power of the transmission distance [9, 10], multihop routing scheme is widely applied in WSNs. In order to save energy, not all the sensor nodes in the network need to send their observations to the BS. In [11], the authors proposed a new topology management scheme by switching the state of the sensors. The radios of nodes can be turned off in a so-called “monitoring” state and will be switched to the “transfer” state when required. The transfer state nodes report their observations to the BS and the monitoring state nodes will not send any packet to the BS. Many works employ the idea of [11] and schedule the state of sensor nodes to reduce energy consumption [12–15]. In this paper, an energy-efficient state scheduling scheme is designed especially for Quasi-BLUE in WSNs.

The BS should collect sufficient data from sensor nodes to implement the Quasi-BLUE. Because of the delay during data transmission, it takes some time for the BS to implement the Quasi-BLUE. The performance metric event detection delay (EDD) is used to describe the time when sufficient number of packets are delivered to the BS [16]. Because of stochastic behavior of end-to-end delay in WSNs, the previous works usually use a probabilistic model to describe the delay [17, 18]. The probability distribution of the end-to-end delay is researched in [17, 18]. That the EDD is less than a bound also satisfies a probability distribution. In some real-time applications, long EDD is not expected. However, the existing researches of Quasi-BLUE in WSNs do not consider the timing constraint. It calls for a scheme that can implement the real-time Quasi-BLUE. The real-time can be classified into hard real-time and soft real-time. In hard real-time, the system needs to finish a task before a hard deadline. The soft real-time, on the other hand, just requires the task be accomplished before the deadline with a probability. In this paper, we focus on the scheduling for the soft real-time estimation. Because the more number of hops during data transmission results in longer delay [19], the existing works usually reduce the number of hops during data transmission [20–24]. However, these approaches do not take advantage of property of soft real-time estimation. The soft timing constraint only requires a task to be finished before the deadline with a probability. In the Quasi-BLUE with an MSE constraint, more sensor nodes' data will increase the probability that the timing constraint is satisfied. Through turning some redundant nodes to transfer state, the soft timing constraint can still be guaranteed. In this paper, we add some redundant transfer state nodes to guarantee the soft timing constraint rather than reducing the number of hops during data transmission.

In this paper, we focus on soft real-time parameter estimation of WSNs. We employ Quasi-BLUE to implement the parameter estimation at the BS. The packets that carry the observations of sensors are transmitted the BS through multihop. The multihop path is the energy minimum path that can be obtained through Dijkstra's algorithm. We propose the MSE constraint function based nodes assignment (MBNA) algorithm to schedule the state of sensor nodes. MBNA schedules the state of sensor nodes to implement the soft real-time estimation with an MSE constraint. The contributions of this paper can be concluded as follows.

• (i)

We first consider the real-time for the Quasi-BLUE in WSNs.

(ii)

The probability that the EDD is less than the timing constraint is quite difficult to calculate. Our approach takes advantage of linear property of Quasi-BLUE and calculates the probability in a heuristic way.

(iii)

Our MBNA can achieve low energy consumption under MSE and soft timing constraints.

The paper is organized as follows. Section 2 provides some related works. In Section 3, we introduce the system model and give some assumptions in this paper. In Section 4, we show the possibility of energy reduction through adding redundant transfer state nodes. In Section 5, the energy-efficient scheduling algorithm for soft real-time estimation, MBNA, is introduced; the performance of MBNA is shown in Section 6. In Section 7, we conclude the paper.

2. Related Works

A lot of researches have been done on parameter estimation in WSNs. BLUE is a popular estimator for the parameter estimation [1, 25]. Luo makes some adjustments on BLUE, and proposes the Quasi-BLUE [2]. In Quasi-BLUE, the data is quantized to several bits, and the estimation is implemented with the quantized data. Although MSE through Quasi-BLUE increases compared to BLUE, Quasi-BLUE is quite suitable for the digital communication environment. In order to save energy, not all the sensor node will send their observations. Only part of sensors will report the observations to the BS according to the demand [11]. The estimation cannot be implemented until the BS receives sufficient data from sensor nodes, because the packet that is transmitted from source to the BS suffers an end-to-end delay. In some real-time applications, the estimation should be finished before a deadline. It requires sufficient data arrives at the BS before the deadline, and the packet delay should be considered.

Because of the randomness of wireless communication, the end-to-end packet delay shows the stochastic characterization. Many researches try to describe the delay through statistics method. In the studies in [26–28], the worst case end-to-end delay is analyzed. The low delay routing algorithms always guarantee the worst case of delay. But due to the large variance of end-to-end delay in WSNs, the worst case cannot accuratly describe the end-to-end delay. The works in [16–18, 29] employ a probability distribution to describe the delay. The delay distribution is built in [17, 18, 29], and the probabilistic description is quite suitable for the delay analysis. In this paper, we follow the probabilistic model of delay and implement our scheduling based on the results in [16–18, 29].

In order to guarantee the timing constraint, many works focus on designing the low delay routing algorithm [20–22, 24]. In WSNs, the delay during data transmission consists of the queueing delay, the transfer delay and the processing delay. Since more number of hops will increase the delay, the routing scheme decreases the delay by decreasing the number of hops. However, the energy consumption increases at the same time. The tradeoff between delay and energy is the major topic. But most low delay routing schemes do not take advantage of the probabilistic property of the delay. The approaches in [20–22, 24] are designed for the fixed delay bound and are not suitable for soft real-time scenario. The energy consumption sometimes can drop a lot while employing the soft timing constraint [30]. Through a proper scheduling scheme, heterogenous sensor nodes can cooperatively implement tasks under soft timing constraint. The works in [13, 15, 30] are examples that implement the optimization.

In this paper, we guarantee the soft timing constraint of Quasi-BLUE through adding redundant transfer state nodes. The BS just requires sufficient data from sensors in an area for the estimation but does not specify a certain sensor. So one sensors' data can be replaced by the other sensors. If there are enough transfer state nodes, the estimation can still be finished before the deadline with a high probability. The depth-first search method is suitable for the multilevel soft real-time scheduling problem [15, 30, 31]. However, the node state scheduling problem of Quasi-BLUE is a single-level scheduling problem, and there are multiple equivalent nodes in the same level. The approaches in [15, 30, 31] are not suitable for this kind of problem. The problem is also not easy to solve through breadth-first search because a huge number of node state combinations should be listed. Our MBNA algorithm, on the other hand, does not employ the traditional search method to implement the optimization. It exploits the properties of Quasi-BLUE in WSNs, and provides the energy-efficient scheduling in a heuristic way.

3. System Model

3.1. Network Model

In this paper, we assume the WSN consists of many sensor nodes and a BS. The sensors are uniformly distributed in the sensing area. The sensor node has two states: transfer state and monitoring state. In transfer state, sensors detect the environment and transmit the observed value to the BS. In monitoring state, sensors detect the environment but do not communicate with others. The mode of a sensor node can be switched according to the command from the BS. The transfer sensors will send their observations to the BS, and the BS implements the estimation with the observed data. The state of sensor nodes is determined by the BS. Based on some performance metrics, the BS comes up with the scheduling of sensor nodes and sends the scheduling command to the sensor nodes. The sensor nodes change their states according to the command.

The sensor nodes can communicate with each other in the network. In order to save energy, the packets will be transmitted to the BS through multihop. Some nodes will be selected as the intermediate nodes during multihop packet relay. Because the BS is usually powered by the external electric source, we do not care about the energy consumption of the BS. Therefore, the BS communicates with sensor nodes directly without any intermediate nodes. In the wireless communications, we assume that the quadrature amplitude modulation (QAM) is employed. The sensor node or the BS sends an L-bit message by using QAM with a constellation size ${\mathrm{2}}^L$ .

3.2. Quasi-BLUE

The sensors keep observing the curious parameters. The observation $z_k$ on the real-value x made by the kth sensor $s_k$ is corrupted by noise ${\theta }_k$ , which can be interpreted as

$$\begin{array}{cc}& z_k=x+{\theta }_k.\end{array}$$

(1)

If the variance ${\sigma }_k$ of the noise ${\theta }_k$ is known, the BLUE estimator [1] for the real-value x is

$$\begin{array}{cc}& \widehat{x}=\frac{{\sum }_{k=\mathrm{1}}^n\left(x_k/{\sigma }_k^{\mathrm{2}}\right)}{{\sum }_{k=\mathrm{1}}^n\left(\mathrm{1}/{\sigma }_k^{\mathrm{2}}\right)}.\end{array}$$

(2)

The MSE of BLUE estimator is

$$\begin{array}{cc}& E{\left(\widehat{x}-x\right)}^{\mathrm{2}}=\frac{\mathrm{1}}{{\sum }_{k=\mathrm{1}}^n\left(\mathrm{1}/{\sigma }_k^{\mathrm{2}}\right)}.\end{array}$$

(3)

The BLUE gives us a relatively accurate estimation, but it is impractical in a WSN system because of the bandwidth and energy limitation [2]. Therefore, the data is quantized to some bits at each sensor, and the estimations are implemented with the quantized data.

Suppose the value $z_k$ observed by sensor $s_k$ is bounded by $[-W,W]$ , and it is quantized to $L_k$ bits

$$\begin{array}{cc}& m_k\left(z_k,L_k\right)=\{\begin{array}{cc}-W+iM,\hfill & \left|z_k-iM\right|<\mathrm{0.5}M\hfill \\ -W+(i+\mathrm{1})M,\hfill & \mathrm{0.5}M\le \left|z_k-iM\right|<M,\hfill \end{array}\end{array}$$

(4)

where $\mathrm{0}\le i\le {\mathrm{2}}^{L_k}-\mathrm{2}$ , $M=\mathrm{2}W/{(\mathrm{2}}^{L_k}-\mathrm{1})$ .

We employ Quasi-BLUE to construct a linear estimator of x similar to BLUE estimator, and the estimator $\widehat{x}$ based on quantization is [5]

$$\begin{array}{cc}& \widehat{x}=\frac{{\sum }_{k=\mathrm{1}}^n\left(m_k/\left({\sigma }_k^{\mathrm{2}}+{\delta }_k^{\mathrm{2}}\right)\right)}{{\sum }_{k=\mathrm{1}}^n\left(\mathrm{1}/\left({\sigma }_k^{\mathrm{2}}+{\delta }_k^{\mathrm{2}}\right)\right)},\end{array}$$

(5)

where ${\delta }_k^{\mathrm{2}}=(W^{\mathrm{2}}/({\mathrm{2}}^{L_k}-\mathrm{1}{)}^{\mathrm{2}})$ , and the variance is

$$\begin{array}{cc}& D=E{\left(\widehat{x}-x\right)}^{\mathrm{2}}=\frac{{\sum }_{k=\mathrm{1}}^n\left(E{\left(m_k-x\right)}^{\mathrm{2}}/{\left({\sigma }_k^{\mathrm{2}}+{\delta }_k^{\mathrm{2}}\right)}^{\mathrm{2}}\right)}{{\sum }_{k=\mathrm{1}}^n{\left(\mathrm{1}/\left({\sigma }_k^{\mathrm{2}}+{\delta }_k^{\mathrm{2}}\right)\right)}^{\mathrm{2}}}.\end{array}$$

(6)

If we round the quantized value to the nearest endpoint of ${\mathrm{2}}^{L_k}$ intervals, the MSE is [2]

$$\begin{array}{cc}& D=\frac{\mathrm{1}}{{\sum }_{k=\mathrm{1}}^n\left(\mathrm{1}/\left({\sigma }_k^{\mathrm{2}}+{\delta }_k^{\mathrm{2}}\right)\right)}.\end{array}$$

(7)

From (7), it can be found that more sensors lead to more accurate estimation.

3.3. Energy Model

The energy consumption of a sensor node contains two main parts: (1) the communication energy and (2) the circuit energy. In long-range application, the data transmission consumes most of the energy in a WSN and the other energy can be neglected compared to the communication energy. Therefore, we only consider the communication energy in this paper.

When a sensor $s_k$ finishes detecting and quantization, an $L_k$ -bit length data will be transmitted to the BS. In a simplified model, the transmission energy can be described as a function of the data length and the transmission distance. The channel between two nodes experiences a pathloss proportional to $a=d^{\alpha }$ , where d is the transmission distance and $\alpha \ge \mathrm{2}$ is the pathloss exponent. If an $L_k$ -bit packet is transmitted with the distance of d, the energy consumption using QAM with a constellation size ${\mathrm{2}}^{L_k}$ is [9, 10]

$$\begin{array}{cc}& E=ca\left({\mathrm{2}}^{L_k}-\mathrm{1}\right),\end{array}$$

(8)

where E is the energy consumption and c is a constant during transmission. Equation (8) is the energy consumption to transmit $L_k$ -bit length data for one hop. The energy consumption to send a packet from source node to the BS is the summation of multihop energy consumption. We denote by $E_k$ the energy consumption which corresponds to the source node $s_k$ .

3.4. Probabilistic Delay

Within the communication range, a link can be built between two nodes. For two sensor nodes $s_i$ and $s_j$ , we denote $(i,j)$ the link between $s_i$ and $s_j$ . In a WSN, each link $(i,j)$ is associated with an end-to-end delay $T_{(i,j)}$ . $T_{(i,j)}$ is not stationary, and it will change during the system running. Because of the randomness in wireless communication, the end-to-end packet delay is usually described as a probabilistic model [16–18, 29]. If we know the probability density function (PDF) of $T_{(i,j)}$ , the delay of $(i,j)$ satisfies

$$\begin{array}{cc}& P(T_{(i,j)}<T)={\int }_{\mathrm{0}}^T‍p_{(i,j)}\left(t\right)dt,\end{array}$$

(9)

where $p_{(i,j)}$ is the PDF of $T_{(i,j)}$ . A packet is transmitted from the source node to the BS through a multihop path, and the packet will suffer the multihop end-to-end packet delay. We denote by $T_k$ the delay of the packets transmitted from the sensor node $s_k$ . The delay satisfies a probability distribution. We denote by $g_k$ the cumulative density functions (CDF) of $T_k$ .

The probability that the delay $T_k$ satisfies timing constraint is

$$\begin{array}{cc}& P(T_k<T_d)=g_k\left(T_d\right),\end{array}$$

(10)

where $T_d$ is the timing constraint.

4. Node State Scheduling for Soft Real-Time Estimation

4.1. Motivational Example

In the multihop transmission, increasing the number of hops will increase the delay. More hop means extra processing delay, queueing delay, and transmission delay. Transmitting the packets along a path with less number of hops is a method to guarantee the timing constraint [20–24]. We call this kind of approaches the delay sensitive energy aware (DSEA) routing scheme. Through the tradeoff between energy and delay, a path will be generated based on the timing constraint. However, this method has the two drawbacks.

• (1)

The energy minimum path planning with timing constraint is an NP-complete problem. The existing approaches can only provide the near-optimal solution.

(2)

In order to decrease the path delay, the path that satisfies the soft timing constraint has less number of hops, which will increase the communication energy.

In this paper, on the other hand, we try to guarantee the soft timing constraint through adding redundant nodes. In the estimation process, the BS only requires sufficient data but does not care for the source of the data. Transmitting redundant data is able to increase the $P(\text{EDD}<T_d)$ . Sometimes this approach is more energy-efficient compared to planning a new path. It can be illustrated in the following example. As shown in Figure 1, there is a sensor network that consists of three sensor nodes and one BS. The BS requires at least one piece of data from sensors in the area A. Either $s_i$ or $s_j$ is candidate to send observations to the BS. The energy consumption for transmitting the packet through each link is shown in Figure 1. In the energy minimum routing, both the two sensor nodes transmit their data to $s_k$ at first. Then $s_k$ relays the data to the BS.

Figure 1

A simple sensor network.

The delay of the two paths with the intermediate node $s_k$ is denoted by $T_i$ and $T_j$ . Assume the BS requires that the data from A within 50 ms with the probability 0.7. If $T_i$ and $T_j$ have the following probability

$$\begin{array}{cc}& P(T_i<\mathrm{50})=\mathrm{0.5},\\ P(T_j<\mathrm{50})=\mathrm{0.5},\end{array}$$

(11)

these two paths cannot guarantee soft timing constraint. The conventional approach is to generate a new path that satisfies the soft timing constraint. In this example, either $s_i$ or $s_j$ will transmit data directly to the BS. The direct data transmission will consume 6J energy per sensor. However, if both $s_i$ and $s_j$ transmit data to the BS through the energy minimum path, the probability that the BS receive the packet from $s_i$ or $s_j$ within 50 ms is

$$\begin{array}{cc}& P(T<\mathrm{50})=\mathrm{1}-P\left(T_i\ge \mathrm{5}\right)P\left(T_j\ge \mathrm{50}\right)=\mathrm{0.75}.\end{array}$$

(12)

The soft timing constraint is satisfied when redundant data is transmitted to the BS. The total energy consumption that both $s_i$ and $s_j$ transmit data to the BS along the energy minimum path is 4J. It can be found that adding redundant nodes can achieve low energy consumption while satisfies the soft timing constraint.

We should still note that the approach through adding redundant transfer state nodes may not perform better than DSEA routing. The performance is tightly related to the value of end-to-end packet delay. In the Section 6, we will discuss the problem in detail.

4.2. CDF of End-to-End Delay

For a source node, the energy minimum path to the BS can be obtained through Dijkstra's algorithm with energy metric. Each path is associated with an end-to-end delay distribution. Because each sensor node corresponds to a path, we can assume that the end-to-end packet delay distributions with the same source node are identical.

The packets are sent from source node to the BS through multihop relay. In the end-to-end delay analysis, the CDFs of multihop end-to-end delay are similar among the works in [17, 29]. Because there is a physical limit in how short a delay can be (shorter than that it is impossible that a message arrives at the other end), the end-to-end delay will be larger than a lower bound. The lower bound of delay is denoted by $T_{\min }$ in this paper. A packet may be lost during transmission. In this situation, the end-to-end packet delay can be thought as infinite. Based on the experimental results in [17, 29], the end-to-end delay approximately satisfies the negative exponential distribution in the range $[T_{\min },+\infty )$ . For the packets transmitted from the source node $s_k$ , the CDF of multihop end-to-end delay satisfies

$$\begin{array}{cc}& g_k\left(t\right)=\mathrm{1}-e^{-{\mu }_{k}t}+T_{\min }.\end{array}$$

(13)

The parameter ${\mu }_k$ can be estimated through moment estimation method. During the network system running, the BS can record the end-to-end delay with different source nodes. When a sensor node send a packet, the time information will be added to the packet. The BS calculate the end-to-end packet delay based on the time information. If the the delay of different packets from $s_k$ is $T_{\mathrm{1}},T_{\mathrm{2}},\dots ,T_n$ , the estimated ${\widehat{\mu }}_k$ through moment estimation is

$$\begin{array}{cc}& {\widehat{\lambda }}_k=\frac{\mathrm{1}}{{\sum }_{i=\mathrm{1}}^n{T}_i}-T_{\min }.\end{array}$$

(14)

The value of ${\widehat{\mu }}_k$ is always updated during the system running.

4.3. Guarantee Soft Timing Constraint with Redundant Nodes

Suppose the BS requires data from an area A to implement the estimation on a parameter. The MSE constraint for the estimation is $D_r$ . Multiple transfer state nodes will provide the observed data for the estimation. We will add several redundant transfer state nodes to guaranteed the soft timing constraint.

We denote on $S_A$ the set that contains all the sensor nodes in the area A. With the PDFs of different path delays and the timing constraint $T_d$ , we can calculate $P(T_k>T_d)$ of the sensor $s_k$ . If $P(T_k>T_d)=\mathrm{1}$ , it means the path can never satisfy the timing constraint. This kind of node will never be selected to send data to the BS. We delete this kind of node from $S_A$ . Then we randomly select several nodes from $S_A$ to guarantee the soft timing constraint. We denote by $S_r$ the transfer state sensor node set. The node $s_k\in S_r$ will transmit data to the BS. At first, we should choose several transfer state nodes to implement the BLUE while satisfying the MSE constraint. If the soft timing constraint is satisfied with the set $S_r$ , no redundant node are required. Otherwise, we should add some redundant nodes to $S_r$ . We define a subset $\Omega \subseteq S_r$ , and the sensors in Ω can provide the sufficient data for the estimation, that is,

$$\begin{array}{cc}& \frac{\mathrm{1}}{{\sum }_{s_k\in \Omega }^{}\left(\mathrm{1}/\left({\sigma }_k^{\mathrm{2}}+{\delta }_k^{\mathrm{2}}\right)\right)}\le D_r.\end{array}$$

(15)

If the data from the sensors in Ω can guarantee the soft timing constraint, we have

$$\begin{array}{cc}& \prod _{s_k\in \Omega }‍P(T_k<T_d)>\gamma .\end{array}$$

(16)

For the set $S_r$ , we can find more than one Ω that satisfies (15). Therefore, the probability $P(\text{EDD}<T_d)$ can be expressed as

$$\begin{array}{cc}& P(\text{EDD}<T_d)=\sum _{\Omega \subseteq S_r}‍\prod _{s_k\in \Omega }‍P(T_k<T_d).\end{array}$$

(17)

Through scheduling the state of sensor nodes, $P(\text{EDD}<T_d)$ can be controlled to a certain level and the soft timing constraint can be guaranteed.

4.4. Energy-Efficient Soft Real-Time Parameter Estimation

In the parameter estimation process, the BS should provide the accurate estimation with sensors' data. In this paper, we employ the MSE between the estimated value and the actual value to evaluate the accuracy of the estimation. In order to save energy, not all the sensor nodes need to send data to the BS. We just need some sensors' data to accomplish the estimation with a certain MSE constraint.

The BS collects sufficient data from different sensors, and implements the estimation. There is an event detection delay (EDD) for the WSNs [32]. The EDD is the time when sufficient number packets are delivered to the BS for the data fusion. In some real-time applications, the EDD should not be too large. A packet that is transmitted from source node to the BS corresponds to an end-to-end delay distribution [16, 17, 29]. In the network, the transfer state nodes send their packets to the BS, and the EDD is determined by the end-to-end delay distribution of each packet. In order to guarantee the soft timing constraint, the EDD should be less than a bound with a probability, that is,

$$\begin{array}{cc}& P(\text{EDD}<T_d)>\gamma ,\end{array}$$

(18)

where $T_d$ is the timing constraint.

The assignment of transfer state nodes will affect EDD. If the transfer state nodes are not enough, the Quasi-BLUE cannot be finished within the soft timing constraint. On the other hand, if we turn too many nodes to transfer state, the energy consumption will increase. We need to schedule the state of node to achieve low energy soft real-time estimation, that is,

$$\begin{array}{cc}& \hspace{0.17em}\min \sum _{s_k\in S_r}‍E_k,\\ \hspace{0.17em}\text{s}.\text{t}.\mathrm{\hspace{0.17em}\hspace{0.17em}}\hspace{0.17em}D\le D_r,\\ \hspace{0.17em}\hspace{1em}\hspace{0.17em}P(\text{EDD}<T_d)>\gamma ,\end{array}$$

(19)

where $S_r$ is the transfer state node set, $D_r$ is the MSE constraint, and $T_d$ is the timing constraint.

5. Redundant Nodes Assignment

$P(\text{EDD}<T_d)$ is the summation of all the probability of ${\prod }_{s_k\in \Omega }‍P(T_k<T_d)$ . Before calculating ${\prod }_{s_k\in \Omega }‍P(T_k<T_d)$ , we must list all the possible Ω. The process is time consuming. In this paper, we use a heuristic method to calculate $P(\text{EDD}<T_d)$ . We propose the MSE constraint function (MSECF) and calculate $P(\text{EDD}<T_d)$ through the MSECF. Then the transfer state node set can be determined based on $P(\text{EDD}<T_d)$ .

5.1. MSE Constraint Function

In Quasi-BLUE, more sensors' data results in small MSE. Under a certain MSE constraint, the BS has to wait for sufficient data to guarantee the MSE constraint. Thus, the timing constraint for Quasi-BLUE is not satisfied and can also be expressed as the estimation cannot be finished with the data that arrives before the deadline. Therefore, $P(\text{EDD}<T_d)$ is equivalent to the probability that the estimation cannot be finished before the deadline.

In this paper, we define the MSE constraint function (MSECF) $f(x)$ as

$$\begin{array}{cc}& f\left(x\right)=P(\frac{\mathrm{1}}{D_r}\ge x).\end{array}$$

(20)

The function means the probability that the reciprocal of MSE constraint is larger than x. Within the timing constraint, the MSE achieved is denoted by D. Then $f(\mathrm{1}/D)$ is the probability that the MSE constraint is not satisfied, and $P(\text{EDD}<T_d)=f(\mathrm{1}/D)$ .

If the MSE constraint is a static value, we have

$$\begin{array}{cc}& f\left(x\right)=\{\begin{array}{cc}\mathrm{1},\hfill & \hspace{0.17em}x\le \frac{\mathrm{1}}{D_r},\hfill \\ \mathrm{0},\hfill & \text{else}.\hfill \end{array}\end{array}$$

(21)

The function (21) can be plotted as shown in Figure 2.

Figure 2

The MSEPF with static $D_r$ .

The Quasi-BLUE is implemented with sensors' data, and there is an estimation MSE D. If $\mathrm{1}/D>\mathrm{1}/D_r$ , we have $f(\mathrm{1}/D)=\mathrm{0}$ . It means that the D can guarantee the MSE constraint with the probability 1.

In the Quasi-BLUE of WSNs, the MSE constraint is usually a certain value, and the MSECF can be formulated as (21). In order to guarantee the MSE constraint, we should determine a $S_r$ that satisfies

$$\begin{array}{cc}& \frac{\mathrm{1}}{D}=\sum _{s_k\in S_r}‍\frac{\mathrm{1}}{{\sigma }_k^{\mathrm{2}}+{\delta }_k^{\mathrm{2}}}>\frac{\mathrm{1}}{D_r}.\end{array}$$

(22)

When a packet from $s_k$ is transmitted to the BS, two possible events may happen.

• (i)

$G_k$ : the packet reaches the BS before the deadline.

(ii)

${\stackrel{-}{G}}_k$ : the packet does not reach the BS before the deadline.

We denote the probability that $G_k$ happens as $p_k$ and the probability ${\stackrel{-}{G}}_k$ happens as $q_k$ . With the CDF of end-to-end delay, $p_k$ and $q_k$ can be calculated.

$$\begin{array}{cc}& p_k=g_k\left(T_d\right),\\ q_k=\mathrm{1}-p_k,\end{array}$$

(23)

where $g_k$ is the CDF of end-to-end packet delay whose source node is $s_k$ .

The missing data will not be used while calculating $\mathrm{1}/D$ . Since the packet from each transfer state sensor node corresponds to probabilistic delay, there is a corresponding $p_k$ for the packet transmitted from $s_k\in S_r$ .

5.2. Probability for Satisfying MSE Constraint

At first, we assume that all the packets can reach the BS before the deadline, and original reciprocal MSE is

$$\begin{array}{cc}& {\frac{\mathrm{1}}{D}}^{\left(\mathrm{0}\right)}=\sum _{s_k\in S_r}‍\frac{\mathrm{1}}{{\sigma }_k^{\mathrm{2}}+{\delta }_k^{\mathrm{2}}}.\end{array}$$

(24)

If one packet transmitted from a transfer state node does not reach the BS before the deadline, it can be thought that the packet is missing. The BS has to implement the estimation without the data in that packet. Then the data will not make contribution to the estimation. If the missing packet is transmitted from $s_k$ , the contribution of $s_k$ should be subtracted from ${(\mathrm{1}/D)}^{(\mathrm{0})}$ . The achieved $\mathrm{1}/D$ without data from $s_k$ is ${(\mathrm{1}/D)}^{(\mathrm{0})}-\mathrm{1}/({\sigma }_k^{\mathrm{2}}+{\delta }^{\mathrm{2}})$ . The process is equivalent to add the MSE constraint by $\mathrm{1}/({\sigma }_k^{\mathrm{2}}+{\delta }^{\mathrm{2}})$ . Thus, the MSECF will be converted to

$$\begin{array}{cc}& f\left(x\right)=\{\begin{array}{cc}\mathrm{1},\hfill & x\le \frac{\mathrm{1}}{D_r}+\frac{\mathrm{1}}{{\sigma }_k^{\mathrm{2}}+{\delta }^{\mathrm{2}}},\hfill \\ \mathrm{0},\hfill & \text{else}.\hfill \end{array}\end{array}$$

(25)

The function (25) right shifts (21) for $\mathrm{1}/({\sigma }_k^{\mathrm{2}}+{\delta }^{\mathrm{2}})$ . Because the probability for ${\stackrel{-}{G}}_k$ is $q_k$ , the MSECF that considers possible data missing of $s_k$ is

$$\begin{array}{cc}& f\left(x\right)=p_k{f}^{\left(\mathrm{0}\right)}\left(x\right)+q_k{f}^{\left(\mathrm{0}\right)}(x-\frac{\mathrm{1}}{{\sigma }_k^{\mathrm{2}}+{\delta }^{\mathrm{2}}}),\end{array}$$

(26)

where $f^{(\mathrm{0})}(x)$ is the MSECF without considering the data missing. We introduce the operator “⊕”, and express (26) as

$$\begin{array}{cc}& f^{\left(\mathrm{1}\right)}\left(x\right)=f^{\left(\mathrm{0}\right)}\left(x\right)\oplus G_k.\end{array}$$

(27)

After one ⊕ operation, the MSECF is converted to Figure 3. $f^{(\mathrm{1})}(\mathrm{1}/D)$ is the probability that the estimation cannot be finished within timing constraint while considering the possibility of ${\stackrel{-}{G}}_k$ .

Figure 3

The MSEPF after one ⊕ operation.

Theorem 1.

Consider the following:

$$\begin{array}{cc}& f\left(x\right)\oplus G_i\oplus G_j=f\left(x\right)\oplus G_j\oplus G_i.\end{array}$$

(28)

Proof.

Consider the following:

$$\begin{array}{l}f\left(x\right)\oplus G_i\oplus G_j\\ \hspace{1em}\hspace{1em}=(p_{i}f\left(x\right)+q_{i}f(x-\frac{\mathrm{1}}{{\sigma }_i^{\mathrm{2}}+{\delta }_i^{\mathrm{2}}}))\oplus G_j\\ \hspace{1em}\hspace{1em}=p_j\left(p_{i}f\left(x\right)+q_{i}f\left(x-\frac{\mathrm{1}}{{\sigma }_i^{\mathrm{2}}+{\delta }_i^{\mathrm{2}}}\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+q_j(p_{i}f\left(x-\frac{\mathrm{1}}{{\sigma }_j^{\mathrm{2}}+{\delta }_j^{\mathrm{2}}}\right)\\ \hspace{0.17em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+q_{i}f\left(x-\frac{\mathrm{1}}{{\sigma }_i^{\mathrm{2}}+{\delta }_i^{\mathrm{2}}}-\frac{\mathrm{1}}{{\sigma }_j^{\mathrm{2}}+{\delta }_j^{\mathrm{2}}}\right))\\ \hspace{1em}\hspace{1em}=(p_{j}f\left(x\right)+q_{j}f(x-\frac{\mathrm{1}}{{\sigma }_j^{\mathrm{2}}+{\delta }_j^{\mathrm{2}}}))\oplus G_i\\ \hspace{1em}\hspace{1em}=f\left(x\right)\oplus G_j\oplus G_i.\end{array}$$

(29)

According to Theorem 1, the order of ⊕ operation will not affect the final MSECF. All the packets in $S_r$ may arrive at the BS after the deadline, so the above process should be applied to all sensors. After $n\hspace{0.17em}\oplus$ operation, the MSECF is converted to

$$\begin{array}{cc}& f^{\left(n\right)}\left(x\right)=f^{\left(\mathrm{0}\right)}\left(x\right)\oplus G_{\mathrm{1}}\oplus G_{\mathrm{2}}\oplus \cdots \oplus G_n.\end{array}$$

(30)

Hence,

$$\begin{array}{cc}& P(\text{EDD}<T_d)=f^{\left(n\right)}\left(\frac{\mathrm{1}}{D}\right).\end{array}$$

(31)

5.3. Nodes Assignment through MSECF

$P(\text{EDD}<T_d)$ can be calculated through MSECF. Based on the probability $P(\text{EDD}<T_d)$ , we propose the MSECF based nodes assignment (MBNA) algorithm to determine the transfer state nodes to implement the soft real-time BLUE. The detail steps of MBNA is shown in Algorithm 1. At first, an original $S_r$ is generated. The sensor nodes in $S_r$ can provide sufficient data for the Quasi-BLUE with the MSE constraint. The original $S_r$ does not have redundant nodes. So all data of sensors in $S_r$ should arrive before the deadline. Then we calculate the probability $P(\text{EDD}<T_d)$ through $f^{(n)}(\mathrm{1}/D)$ . If $f^{(n)}(\mathrm{1}/D)>\gamma$ , the estimation under the MSE constraint $D_r$ can be implemented with the soft timing constraint. Otherwise, we should add a redundant node to $S_r$ and check whether $f^{(n+\mathrm{1})}(\mathrm{1}/D)>\gamma$ . The process continues until we obtain a $f(x)$ that satisfies $f(\mathrm{1}/D)>\gamma$ .

Algorithm 1: MSECF Based Nodes Assignment (MBNA) Algorithm.

Require: observed value range $[-W,W]$ , quantization data

length L, timing constraint $T_d$ with probability γ, and

MSE constraint $D_r$ ;

Ensure: transfer state sensor set $S_r$ ;

(1) $\delta =W/\left({\mathrm{2}}^L-\mathrm{1}\right)$ ;

(2) calculate $p_k$ of every sensor node;

(3) $S_r=\mathrm{\varnothing }$ ;

(4) do

(5)  add a transfer state node to $S_r$ ;

(6)   $\mathrm{1}/D={\sum }_{s_k\in S_r}\mathrm{1}/\left({\sigma }_k^{\mathrm{2}}+{\delta }^{\mathrm{2}}\right)$ ;

(7) while   $\mathrm{1}/D<\mathrm{1}/D_r$ ;

(8) calculate $f(x)$ according to (21);

(9) for   $s_k\in S_r$

(10)   $f(x)=f(x)\oplus G_k$ ;

(11) end for

(12) while   $f\left(\mathrm{1}/D\right)\le \gamma$

(13)  add a transfer state node to $S_r$ ;

(14)  for   $s_k\in S_r$

(15)    $f(x)=f(x)\oplus G_k$ ;

(16)  end for

(17)   $\mathrm{1}/D={\sum }_{s_k\in S_r}\mathrm{1}/\left({\sigma }_k^{\mathrm{2}}+{\delta }^{\mathrm{2}}\right)$ ;

(18) end while

6. Simulation Results

In this section, we present the simulation results for the MBNA algorithms.

6.1. Simulation Setup

In the simulations, we randomly deploy 100 sensor nodes in a 1000 m × 1000 m area. We make the BS located at the (500,500). The two constants of the communication energy in (8) is set as $c=\mathrm{1}$ and $\alpha =\mathrm{2}$ . The maximum communication range of the sensor node is set as 500 m. The nodes can communicate with others within the communication range.

We assume that the sensors observe a parameter with the range of $[-\mathrm{16,16}]$ and the observations are quantized to 4-bit. The noise variance is assumed to be a stochastic value between $[1,4]$ . Each sensor corresponds to a noise variance. We schedule the states of the sensor nodes to implement Quasi-BLUE. The transfer state nodes will report their observations to the BS. At first, an original transfer state sensor set can be generated without considering the timing constraint. We randomly generate some transfer state nodes that are able to provide sufficient data for the Quasi-BLUE, and these nodes formulate the original transfer state sensor set. In soft real-time estimations, the EDD should be less than the timing constraint $T_d$ with a probability γ. The DSEA routing approaches usually reduce the number of hops to guarantee the timing constraint and construct a low delay path. The packets travel along the low delay path so that the EDD can be reduced. This kind of scheme guarantees the timing constraint by considering the worst case end-to-end delay. The MBNA, on the other hand, tries to guarantees the soft timing constraint through turning redundant nodes to the transfer state. The path of MBNA is still the energy minimum path. In this paper, we employ the approach in [19] to implement DSEA routing. We simulate the energy consumption for our MBNA and compare the results of MBNA with DSEA routing. Because the worst case of single hop delay is required for DSEA routing, we assume that the largest single hop delay is

$$\begin{array}{cc}& t=F^{-\mathrm{1}}\left(\mathrm{0.99}\right)+\text{rand},\end{array}$$

(32)

where $F(x)$ is the CDF of single hop delay, $F^{-\mathrm{1}}(x)$ is the inverse function of $F(x)$ , and $\text{rand}$ is a random value between 0 and 1. In (32), the single hop delay will be larger than $F^{-\mathrm{1}}(\mathrm{0.99})$ with the probability 0.99. While considering the variation of single hop delay, we add a random value $\text{rand}$ to $F^{-\mathrm{1}}(\mathrm{0.99})$ and approximate the worst case of single hop delay as (32).

6.2. Normal Distribution Single Hop Delay Case

Normal distribution single hop delay is a common assumption in the delay analysis in WSNs. In this subsection, we simulate the performance of MBNA with the normal distribution single hop delay. The single hop delay is assumed to satisfy the normal distribution with the PDF $(\mathrm{1}/\sqrt{\mathrm{2}\pi })e^{(t-\mathrm{15}{)}^{\mathrm{2}}/\mathrm{18}}$ . In the soft real-time parameter estimation in WSNs, three factors will affect the system's energy consumption: (1) timing constraint $T_d$ ; (2) MSE constraint $D_r$ ; (3) probability for satisfying timing constraint γ.

We investigate the performance of MBNA versus $T_d$ , $D_r$ , and γ. We make $\gamma =\mathrm{0.8}$ and the MSE constraint $D_r=\mathrm{0.3}$ and investigate the energy consumption versus $T_d$ . The simulation is repeated for 100 times and the result is shown in Figure 4.

Figure 4

Energy consumption versus timing constraint. $\gamma =\mathrm{0.8}$ and $D_r=\mathrm{0.3}$ .

The two curves in Figure 4 represent the average energy consumption required to implement the Quasi-BLUE. Short timing constraint means the low probability that the packet can reach the BS before the deadline. Therefore, when the timing constraint increases, the energy consumption decreases. Compared to DSEA routing, MBNA has lower energy consumption when the timing constraint is small. In Figure 4, DSEA routing achieves lower energy consumption than MBNA when $T_d>\mathrm{82}\hspace{0.17em}$ ms. The phenomenon is easy to understand. Because $T_d$ is large, the packets will travel along the energy minimum path through DSEA routing. Therefore, with the same source node, the multihop path is identical for both DSEA routing and MBNA. Because MBNA requires extra transfer state nodes to guarantee the soft timing constraint, MBNA may consume more energy for Quasi-BLUE when $T_d$ is large.

MBNA is designed for the soft timing constraint. We need the estimation to be implemented before the deadline with a probability γ. To verify that MBNA can guarantee the soft timing constraint, the number of successful estimations should be investigated. The successful estimation can be expressed as the MSE constraint is satisfied when the data arrives before the deadline. Figure 5 shows the number of successful estimations before deadline. We choose 11 different timing constraints from 50 ms to 100 ms and simulate the estimation process for 1000 times per timing constraint. We let $D_r=\mathrm{1}$ and $\gamma =\mathrm{0.8}$ during simulation. We record the number of successful estimations in the 100 times estimations. In Figure 5, the height of the bar represents the number of successful estimations. We can find that the number of successful estimation is larger than 800 for each timing constraint. It means that the Quasi-BLUE can be finished before the deadline with the probability that is larger than 0.8. The soft timing constraint can be guaranteed through MBNA.

Figure 5

Number of successful estimation before deadline. $\gamma =\mathrm{0.8}$ and $D_r=\mathrm{0.3}$ .

Then we investigate the MSE constraint's influence on the performance of MBNA. We make $\gamma =\mathrm{0.8}$ and the timing constraint $T_d=\mathrm{100}\hspace{0.17em}$ ms. γ and $T_d$ keep unchanged during simulation. The energy consumption with different MSE constraints is shown in Figure 6.

Figure 6

Energy consumption versus MSE constraint. $\gamma =\mathrm{0.8}$ and $T_d=\mathrm{100}\hspace{0.17em}$ ms.

The result in Figure 6 represents the average energy consumption with MBNA and DSEA routing. MBNA can achieve lower energy consumption when $D_r<\mathrm{4.6}$ . When $D_r\ge \mathrm{4.6}$ , MBNA and DSEA routing have the same energy consumption. The reason is that when the MSE constraint is large, the Quasi-BLUE can be finished with few sensors' data. According to (17), $P(\text{EDD}<T_d)$ will increase when the size of $S_r$ is small. When $D_r$ is large enough, DSEA routing does not need to reduce the number of hops and MBNA will not add redundant transfer state node.

The probability γ affects the number of redundant transfer state nodes. We make $T_d=\mathrm{100}\hspace{0.17em}$ ms and compare the results of MBNA with different γ. We choose three value of γ and simulate our MBNA with different γ. For each γ, the simulations is repeated for 100 times. We record the average energy consumption for the Quasi-BLUE. The simulation results is shown in Figure 7. γ represents the probability that the estimation should be finished before the deadline. If γ is small, MBNA will not add many redundant nodes to guarantee the timing constraint. As a result, the energy consumption will decrease as γ decreases.

Figure 7

Energy consumption versus γ for $T_d=\mathrm{100}\hspace{0.17em}$ ms.

6.3. Simulation for Different Single Hop Delay Distributions

The single hop delay distribution will affect the performance of DSEA routing. In DSEA routing, the worst case of single hop delay is used in the route planning. If the worst case is not far away from the common case, DSEA routing may achieve lower energy consumption than MBNA. The general hypothesis of single hop delay distribution are normal distribution, negative exponential distribution and uniform distribution. We make $D_r=\mathrm{1}$ , $\gamma =\mathrm{0.8}$ and simulate the performance of DSEA routing and MBNA under the three single hop delay distributions. The performances of DESA and MBNA with different single hop delay distributions are shown in Figures 8, 9 and 10. Figure 8 shows the energy consumption for normal distribution single hop delay, Figure 9 shows the energy consumption for negative exponential distribution single hop delay, and Figure 10 shows the energy consumption for uniform distribution single hop delay.

Figure 8

Energy consumption with normal distribution single hop delay.

Figure 9

Energy consumption with negative exponential distribution single hop delay.

Figure 10

Energy consumption with uniform distribution single hop delay.

In the normal distribution case, the single hop distribution is assume to satisfy the $N(\mathrm{15},{\beta }^{\mathrm{2}})$ , ${\beta }^{\mathrm{2}}$ is the variance of the distribution. In Figure 8, when $\beta =\mathrm{3,5},\mathrm{10}$ , MBNA achieves lower energy consumption than DSEA routing. When $\beta =\mathrm{1}$ , DSEA routing performs better than MBNA. In the negative exponential distribution case, the CDF single hop distribution is assumed to be $\mathrm{1}-e^{-\lambda t}$ . With different values of λ, the performances of DSEA routing and MBNA changes. When λ is small, MBNA shows great energy-efficiency over DSEA routing. When $\lambda =\mathrm{0.3}$ , MBNA and DSEA routing have similar energy consumption. In the uniform distribution case, we let the single hop delay vary in a range. In Figure 10, the single hop delay varies in $[10,15]$ , $[5,15]$ , and $[5,20]$ , respectively. In the uniform distribution case, we find that MBNA shows no advantage when the single hop delay varies in $[10,15]$ and $[5,15]$ . When the single hop delay varies in $[\mathrm{5,20}]$ , MBNA provides lower energy consumption.

The above results reflect the fact that DSEA routing guarantees the hard timing constraint. In DSEA routing, the packets travel along a path whose maximum end-to-end delay is less than the timing constraint. In general, the worst case will happen with a small probability, and DSEA routing over considers the end-to-end delay. Therefore, DSEA routing is not energy-efficient compared to MBNA. However, if the end-to-end packet delay varies in a small range, that is, the variance of delay distribution is small, the worst case of delay will not be far from the mean value of delay. In this case, the property of soft timing constraint is not notable, and DSEA routing may achieve lower energy consumption than MBNA. In the three single hop distribution cases, MBNA can reduce the energy consumption a lot when the variance is large. For the network traffic with large uncertainty, the single hop delay usually varies in a large range. And our MBNA can achieve lower energy consumption in this situation.

7. Conclusion

In this paper, we focused on the energy-efficient scheduling for soft real-time parameter estimation in WSNs. The estimator at the BS is Quasi-BLUE, which is a quite common estimator in WSNs. In order to save energy, not all the sensor nodes will send the data to the BS. Only part of sensor nodes will be at the transfer state so that the Quasi-BLUE can be implemented with an MSE constraint. In some real-time applications, we always expect the estimation can be finished before a deadline with a high probability. The EDD describes the time that the BS receives sufficient data from sensor nodes to implement the estimation. The traditional approaches usually try to reduce the number of hops to decrease the end-to-end packet delay, which will increase the communication energy. However, in the scenario of Quasi-BLUE, the BS just needs the data from an area instead of a unique sensor. A sensor node's data can be replaced by another sensors. Therefore, adding some redundant transfer state nodes will increase the probability that EDD is less than the timing constraint, that is, $P(\text{EDD}<T_d)>\gamma$ .

Because a packet from a sensor node corresponds to a delay distribution, the calculation of $P(\text{EDD}<T_d)>\gamma$ with packets from different sensor nodes is difficult. In this paper, we proposed the MSEPF and employ the MSEPF to calculate $P(\text{EDD}<T_d)>\gamma$ . The approach takes advantages of the linear property of Quasi-BLUE and it is easy to implement. Once $P(\text{EDD}<T_d)>\gamma$ is obtained, we proposed the MBNA algorithm to schedule the transfer state sensor nodes for the soft real-time Quasi-BLUE. We compared our MBNA with the existing DESA routing approaches in the soft real-time Quasi-BLUE. The simulation results show that MBNA is more energy-efficient while satisfying the soft timing constraint in the Quasi-BLUE.