Deadline Aware Retransmission Threshold Setting Protocol in Cyber-Physical Systems

Abstract

Many time-sensitive applications impose high requirement on real-time response. There exist many algorithms and routing protocols for efficient data packet delivery. However, previous works set the same retransmission threshold for all the relay nodes along a delivery path. The method decreases the probability of a packet being transmitted through the delivery path within given deadline. In this paper, we focus on finding the optimal retransmission thresholds for the relay nodes, such that the summation of the probability of a packet being transmitted to the next relay node or destination node within the specified deadline is maximized. A distributed greedy algorithm that can be run on sensor node is proposed, which enables the sensor node to adaptively set the optimal retransmission threshold. To avoid dropping the packet forwarded to the destination within given deadline with high probability, we develop a packet dropped protocol based on probabilistic delay bound. Experimental results show that the proposed protocols have better performance.

1. Introduction

Cyber-physical systems (CPS) integrate the computation and physical processes to monitor and control the continuous dynamics of physical world and engineered systems, which revolutionize the approaches for observing the physical world and the process of information access. As extremely critical component in CPS, wireless sensor networks (WSNs) have been envisioned to observe and cognize the complicated physical world at low cost [1, 2]. Deployments of large-scale WSNs have potential to shed light on a variety of monitoring purposes, such as environment monitoring, pollution levels monitoring, and progress of climate change. The discovery of useful knowledge from the massive sensed data is helpful for deeper scientific understanding of human-physical world interaction, which motivates researchers to explore complex and evolving relationships among the data. Plentiful research works have begun focusing on extracting useful knowledge from the Big Data perspective by using the large-scale sensed data.

Large-scale WSNs have been considered as one of the promising, high-value applications for CPS, whose enormous societal impact and economic benefit will be created by the discovery of useful knowledge from the sensed data. Many time-sensitive applications, such as intruder tracking, environment control, and structural health diagnosis impose high requirement on real-time response for decision making and future actions [3–6]. In these applications, deadline misses in data communication may bring about irreparable financial and environmental impacts. Therefore, achieving fast data delivery and response for the massive data generated in WSNs poses new research challenges.

Data delivery delay has been extensively studied in forwarding quality measurement [7–9], sensor network routing, and scheduling [10–13]. Most of the works focus on investigating the metrics to characterize the forwarding quality or minimizing average path delay. Moreover, existing works set the same retransmission threshold for all the sensor nodes along a delivery path. The method is short of taking the link quality and delay requirement into account, which decreases the probability of a packet being successfully transmitted through its delivery path within given deadline. In many cases, the retransmission threshold imposes a significant effect on the probability. To understand the impact of retransmission threshold on the probability of packet delivery before its deadline, we give an example, which is illustrated in Figure 1.

Figure 1

The impact of retransmission threshold on success probability of packet delivery.

The number at each link is the probability of a packet being successfully delivered to the next node through the link, denoted by $p_{\mathrm{s}\mathrm{u}\mathrm{c}}$ , which means that on average it takes $\mathrm{1}/p_{\mathrm{s}\mathrm{u}\mathrm{c}}$ transmission trials to successfully deliver a packet. We assume that one transmission takes $\mathrm{1}$ second and the deadline of delivering a packet from node S to node D is $\mathrm{9}$  s. To deliver the packet to node D before the deadline, the summation of transmission trials along the path must be no more than $\mathrm{9}$ , which is the result of dividing deadline $\mathrm{9}$  s by one transmission time 1 s. If the retransmission threshold for each link is $\mathrm{2}$ , then it is easily known that the probability of a packet passing the first link is 1 − 0.9 × 0.9 × 0.9 = 0.271. Therefore, the probability of a packet being successfully received by destination node D within its deadline is 0.271 × 1 × 1 = 0.271. However, if the retransmission thresholds for the first link is $\mathrm{6}$ and the others are $\mathrm{0}$ , then the probability is (1 − 0.9⁷) × 1 × 1 ≈ 0.522, which is almost twice as that of the method of setting the same retransmission threshold in advance. The approach of setting the same retransmission threshold did not take the link quality and deadline into account, which decreases the probability of a packet being successfully transmitted through its delivery path within given deadline.

To improve the reliability of packets delivery, the method of packets being transmitted along multiple paths is widely applied. Therefore, in this paper we focus on computing the optimal retransmission thresholds for the relay nodes along a delivery path, such that the summation of the probability of a packet being successfully delivered to the next relay node or destination node within the specified deadline is maximized. To find the optimal retransmission threshold, a distributed greedy algorithm that can be run on sensor node is proposed, which enables the sensor node to adaptively set the optimal retransmission threshold based on the link quality and the remaining time to deadline. Stringent retransmission threshold may make the packet forwarded to the destination within deadline with high probability be dropped. To overcome the shortcoming, we develop an $(\alpha ,\beta )$ -probabilistic delay bound based packet dropped protocol. The main contributions of the paper are as follows.

• (i)

The problem of finding optimal retransmission thresholds for the relay nodes along a delivery path is proposed. A formal description of the problem is given, and it can be formalized as an integer optimization problem.

(ii)

A distributed greedy algorithm for computing optimal retransmission threshold is proposed and the correctness of this algorithm is proved. The time complexity of the algorithm is $O(\Delta n)$ , and the memory complexity is $O(n)$ , where Δ is the given upper bound of the delivery delay and n is the length of the delivery path.

(iii)

To avoid dropping the packet forwarded to the destination within the given deadline with high probability, an $(\alpha ,\beta )$ -probabilistic delay bound based packet dropped protocol is developed.

(iv)

Simulation experiments are conducted to evaluate the proposed algorithm and protocol. Experimental results show that our algorithms have better performance in terms of deadline success ratio and real-time ratio.

The rest of this paper is organized as follows. The related works on real-time data delivery are surveyed in Section 2. In Section 3, the optimization problem is described first, and a greedy algorithm for computing optimal retransmission threshold is provided. Based on Chebyshev inequality, an $(\alpha ,\beta )$ -probabilistic delay bound based packet dropped protocol is proposed in Section 4. Experimental results are illustrated in Section 5, and Section 6 concludes this paper.

2. Related Works

Data delivery delay is extensively considered in routing metric. The metric of expected transmission count (ETX) was proposed in [14]. ETX measures the expected number of transmissions for successfully delivering a packet over the link, which works well in a homogeneous sigle-radio environment. Effective number of transmissions (ENT) [15] was proposed to enhance ETX by taking the variable link reliability into account. Expected transmission time (ETT) [16] and the path metric of weighted cumulative ETT were proposed for multichannel mesh networks. ETT can be considered as enhanced ETX by counting the hererogeneous channel rate and intraflow interference.

Data delivery delay has also attracted much attention in designing efficient routing protocol. There are three categories of routing protocols that favor the end-to-end delay performance guarantee in WSNs [17]: (I) tree-based routing; (II) optimal routing based on the knowledge of network topology; (III) geographic routing by the information of node position. To shorten the worst-case delay, [18] proposed tree-based routing protocol, which looks up the neighbor table for routing decisions. Tree-based protocol may lead to high energy consumption of the nodes near root of the tree. Generally, geographic routing protocols are not optimal, because they are merely based on one-hop decision [17]. SPEED protocol was proposed in [12], which estimates the forwarding delay. In SPEED protocol, the node of higher relay velocity is selected with higher probability. However, for high efficient energy utilization it is significant to integrate the information effectively.

Motivated by the tradeoff between the energy consumption and real-time routing performance, [19–21] investigated the optimal construction of virtual backbone and node placement. Aiming at enabling routing with probabilistic delay bounds in wireless sensing and control networks, multitimescale adaptation routing protocol was proposed in [22], which addresses the challenges of dynamic, uncertain link/path delays in real-time routing. To minimize the cost of packet delivery, [23, 24] developed approximation algorithms for the capacitated multicast routing problem.

There are plentiful research works that focus on the analysis of the end-to-end delay in wireless networks. In literature [25], the open queueing network theory was applied to model the WSNs and the analysis for the paths delay based on the model was provided. By mapping the scheduling of real-time periodic data flows in a wirelessHART network to real-time multiprocessor scheduling, the analysis of end-to-end delay was given in [26].

However, all the previous works set the same retransmission threshold for the sensor nodes in advance. The method of setting the same retransmission threshold for the sensor nodes along a delivery path is short of taking the link quality and delay requirement into account, which decreases the probability of a packet being successfully transmitted through its delivery path within given deadline. To the best of our knowledge, this paper first investigates the problem of finding optimal retransmission thresholds.

3. Greedy Algorithm for Computing Optimal Retransmission Threshold

The method of setting the same retransmission threshold for all sensor nodes has poor performance in real-time data delivery. In this section, we develop a greedy algorithm for computing the optimal retransmission thresholds for the relay nodes along a delivery path, such that the summation of the probability of a packet being successfully transmitted to the next relay node or destination node within the specified deadline is maximized.

3.1. Problem Description

Suppose that the end-to-end path is $P=j_{\mathrm{1}},j_{\mathrm{2}},\dots ,j_{n+\mathrm{1}}$ , where $j_{\mathrm{1}}$ and $j_{n+\mathrm{1}}$ are source and destination nodes. Let $p_i$ denote the probability of a transmission failure over the link from $j_i$ to $j_{i+\mathrm{1}}$ . Then $p_i$ is the probability that a MAC-layer transmission fails due to either collisions or bad channel quality when node $j_i$ forwards a data packet to node $j_{i+\mathrm{1}}$ . If $K_i$ is the retransmission threshold of node $j_i$ , then $\mathrm{1}-p_i^{K_i+\mathrm{1}}$ is the probability of a packet being successfully transmitted to node $j_{i+\mathrm{1}}$ by node $j_i$ . To improve the reliability of packet delivery, packets are transmitted along multiple paths. Therefore, we focus on maximizing the summation of the probability of a packet being successfully transmitted to the next relay node or destination node along the delivery path within the given deadline. Let Δ denote the end-to-end delay requirement. $L_i$ and $U_i$ are used to denote the given lower and upper bounds of retransmission threshold of node i. The problem of finding optimal retransmission thresholds for relay nodes can be formulated as the following integer optimization problem:

$$\begin{array}{ll}max\hfill & \sum _{i=1}^n\left(1-p_i^{K_i+1}\right)\hfill \\ \text{s}.\text{t}.\hfill & \sum _{i=1}^n\left(K_i+1\right)\le \Delta \hfill \\ \hfill & L_i\le K_i\le U_i,\hfill \\ \hfill & K_i\in Z,\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\},\hfill \\ \hfill & p_i\in (0,1),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{L}_i,U_i\in (0,+\infty ),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\}.\hfill \end{array}$$

(1)

Obviously, the value of objective function ${\sum }_{i=\mathrm{1}}^n‍(\mathrm{1}-p_i^{K_i+\mathrm{1}})$ is maximized if and only if the value of ${\sum }_{i=\mathrm{1}}^n‍p_i^{K_i+\mathrm{1}}$ achieves the minimum. For any $i\in \{\mathrm{1,2},\dots ,n\}$ , let $k_i=K_i+\mathrm{1},l_i=L_i+\mathrm{1}$ and $u_i=U_i+\mathrm{1}$ . Then the aforementioned optimization problem is equivalent to the following integer optimization problem:

$$\begin{array}{ll}min\hfill & \sum _{i=1}^n{p}_i^{k_i}\hfill \\ s.t.\hfill & \sum _{i=1}^n{k}_i\le \Delta \hfill \\ \hfill & l_i\le k_i\le u_i,\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{k}_i\in Z,\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\},\hfill \\ \hfill & p_i\in (0,1),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{l}_i,u_i\in (0,+\infty ),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\}.\hfill \end{array}$$

(2)

Then the problem of finding the optimal retransmission thresholds for each relay node along a delivery path can be defined as follows.

Input. $(1)$ The set of the transmission failure probabilities of the nodes along a delivery path, $\{p_{\mathrm{1}},\dots ,p_n\}$ .   $(2)$ The end-to-end delivery delay requirement Δ.

Output. Optimal retransmission thresholds $k_{\mathrm{1}}^{\prime },k_{\mathrm{2}}^{\prime },\dots ,k_n^{\prime }$ , which are optimal solutions for integer optimization problem (2).

Based on the above analysis, the key point is to design an efficient algorithm for finding the optimal solutions to integer optimization problem (2). In the following section, we prove that the optimization problem can be solved by a greedy algorithm. And the correctness of the algorithm is proved.

3.2. Correctness of Greedy Algorithm

Lemma 1.

For any $i\in \{\mathrm{1,2},\dots ,n\}$ , the following inequalities hold; if $\mathrm{0}<p_i<\mathrm{1}$ and $l_i<u_i$ ,

$$\begin{array}{cc}& p_i^{l_i+j}-p_i^{l_i+j-\mathrm{1}}<p_i^{l_i+j+\mathrm{1}}-p_i^{l_i+j}<\mathrm{0},\end{array}$$

(3)

where $j\in \{\mathrm{1,2},\dots ,u_i-l_i\}$ .

Proof.

Let $f_i(x)=p_i^x$ ; it is easily known that $f_i^{\prime \prime }(x)>\mathrm{0}$ .

Thus $f_i^{\prime }(x)$ is an increasing function with respect to x. According to the differential mean value theorem, the following equalities can be derived:

$$\begin{array}{cc}& f_i(l_i+j+\mathrm{1})-f_i(l_i+j)=f_i^{\prime }\left(\xi \right)·\mathrm{1}\\ f_i(l_i+j)-f_i(l_i+j-\mathrm{1})=f_i^{\prime }\left(\eta \right)·\mathrm{1},\end{array}$$

(4)

where $\xi \in \left(l_i+j,l_i+j+\mathrm{1}\right)$ and $\eta \in \left(l_i+j-\mathrm{1},l_i+j\right)$ . Since $f_i^{\prime }(x)$ is an increasing function, then $f_i^{\prime }(\eta )<f_i^{\prime }(\xi )$ . Then we can derive that $p_i^{l_i+j}-p_i^{l_i+j-\mathrm{1}}<p_i^{l_i+j+\mathrm{1}}-p_i^{l_i+j}$ . Due to the decreasing of $f_i(x)$ , we have $p_i^{l_i+j+\mathrm{1}}-p_i^{l_i+j}<\mathrm{0}$ . In conclusion, we know that $p_i^{l_i+j}-p_i^{l_i+j-\mathrm{1}}<p_i^{l_i+j+\mathrm{1}}-p_i^{l_i+j}<\mathrm{0}$ .

For any $i\in \{\mathrm{1,2},\dots ,n\},\hspace{0.17em}\hspace{0.17em}j\in Z^{+}$ , ${\lambda }_i(j)$ is defined as follows:

$$\begin{array}{cc}& {\lambda }_i\left(j\right)=\left\{\begin{array}{cc}{p}_i^j-p_i^{j-\mathrm{1}}\hfill & j\le u_i\hfill \\ \infty \hfill & j>u_i,\hfill \end{array}\right.\end{array}$$

(5)

where $l_i<u_i$ .

According to Lemma 1, for any $j\in [l_i,u_i-\mathrm{1}]$ , we have ${\lambda }_i(j+\mathrm{1})>{\lambda }_i(j)$ . And it can be known that $p_i^{l_i+j}=p_i^{l_i}+{\sum }_{k=l_i+\mathrm{1}}^{l_i+j}‍{\lambda }_i(k)$ . For $\forall i\in \{\mathrm{1,2},\dots ,n\}$ , we introduce the following sign function:

$$\begin{array}{cc}& {\chi }_i\left(x\right)=\left\{\begin{array}{cc}\mathrm{1}\hfill & x=i\hfill \\ \mathrm{0}\hfill & x\ne i.\hfill \end{array}\right.\end{array}$$

(6)

Lemma 2.

Let $h=\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{m}\mathrm{i}\mathrm{n}}_{i\in \{\mathrm{1,2},\dots ,n\}}\{{\lambda }_i(l_i+\mathrm{1})\}$ ; then $l_{\mathrm{1}}+{\chi }_{\mathrm{1}}(h),l_{\mathrm{2}}+{\chi }_{\mathrm{2}}(h),\dots ,l_n+{\chi }_n(h)$ are the optimal solution to the following integer optimization problem:

$$\begin{array}{ll}min\hfill & \sum _{i=1}^n{p}_i^{k_i}\hfill \\ \text{s}.\text{t}.\hfill & \sum _{i=1}^n{k}_i\le 1+\sum _{i=1}^n{l}_i\hfill \\ \hfill & l_i\le k_i\le u_i,\hfill \\ \hfill & k_i\in Z,\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\},\hfill \\ \hfill & p_i\in (0,1),\hspace{0.17em}\hspace{0.17em}{l}_i,u_i\in (0,+\infty ),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\}.\hfill \end{array}$$

(7)

Proof.

Based on the definition of ${\chi }_i(x)$ , it is easily verified that the solution $l_{\mathrm{1}}+{\chi }_{\mathrm{1}}(h),l_{\mathrm{2}}+{\chi }_{\mathrm{2}}(h),\dots ,l_n+{\chi }_n(h)$ satisfies all the constraints of optimization problem (7). For any $i\in \{\mathrm{1,2},\dots ,n\}$ , the objective function is decreasing with respect to $k_i$ . Then it is easily derived that the necessary condition of the objective function value achieving the minimal is that ${\sum }_{i=\mathrm{1}}^n‍k_i=\mathrm{1}+{\sum }_{i=\mathrm{1}}^n‍l_i$ . Suppose that $k_{\mathrm{1}}^{\ast },k_{\mathrm{2}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution to problem (7). According to the constraints, for any $i\in \{\mathrm{1,2},\dots ,n\}$ , we know that $k_i^{\ast }\ge l_i$ . Thus we can derive that there must exist $j\in \{\mathrm{1,2},\dots ,n\}$ , such that $k_i^{\ast }$ satisfies the following formula:

$$\begin{array}{cc}& k_i^{\ast }=\left\{\begin{array}{cc}{l}_i\hfill & i\ne j\hfill \\ l_i+\mathrm{1}\hfill & i=j.\hfill \end{array}\right.\end{array}$$

(8)

It can be easily known that ${\sum }_{i=\mathrm{1}}^n‍p_i^{l_i+{\chi }_i(h)}-{\sum }_{i=\mathrm{1}}^n‍p_i^{k_i^{\ast }}=p_h^{l_h+\mathrm{1}}+p_j^{l_j}-p_h^{l_h}-p_j^{l_j+\mathrm{1}}$    $=(p_h^{l_h+\mathrm{1}}-p_h^{l_h})-(p_j^{l_j+\mathrm{1}}-p_j^{l_j})={\lambda }_h(l_h+\mathrm{1})-{\lambda }_j(l_j+\mathrm{1})$ . Since ${\lambda }_h(l_h+\mathrm{1})={\mathrm{m}\mathrm{i}\mathrm{n}}_{i\in \{\mathrm{1,2},\dots ,n\}}\{{\lambda }_i(l_i+\mathrm{1})\}$ , then ${\sum }_{i=\mathrm{1}}^n‍p_i^{l_i+{\chi }_i(h)}-{\sum }_{i=\mathrm{1}}^n‍p_i^{k_i^{\ast }}\le \mathrm{0}$ . In conclusion, $l_{\mathrm{1}}+{\chi }_{\mathrm{1}}(h),l_{\mathrm{2}}+{\chi }_{\mathrm{2}}(h),\dots ,l_n+{\chi }_n(h)$ is the optimal solution to problem (7).

Lemma 3.

Let $h=\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{m}\mathrm{i}\mathrm{n}}_{i\in \{\mathrm{1,2},\dots ,n\}}\{{\lambda }_i(l_i+\mathrm{1})\}$ ; if $k_{\mathrm{1}}^{\ast },k_{\mathrm{2}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution to the following integer optimization problem, then $k_h^{\ast }\ge l_h+\mathrm{1}$ , where Λ is a given positive integer:

$$\begin{array}{ll}min\hfill & \sum _{i=1}^n{p}_i^{k_i}\hfill \\ \text{s}.\text{t}.\hfill & \sum _{i=1}^n{k}_i\le \Lambda +\sum _{i=1}^n{l}_i\hfill \\ \hfill & l_i\le k_i\le u_i,\hfill \\ \hfill & k_i\in Z,\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\},\hfill \\ \hfill & p_i\in (0,1),\hspace{0.17em}\hspace{0.17em}{l}_i,u_i\in (0,+\infty ),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\}.\hfill \end{array}$$

(9)

Proof.

The proof is by induction on Λ. According to Lemma 2, $k_h^{\ast }\ge l_h+\mathrm{1}$ holds, when $\Lambda =\mathrm{1}$ . Suppose that the proposition is true, when $\Lambda \le m-\mathrm{1}$ . In the following, we prove that when $\Lambda =m$ , $k_h^{\ast }\ge l_h+\mathrm{1}$ holds. And the proof is by contradiction.

Suppose that $k_{\mathrm{1}}^{\ast },k_{\mathrm{2}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution to problem (9), and $k_h^{\ast }<l_h+\mathrm{1}$ . According to the constraints, we know that $k_h^{\ast }=l_h$ . For any $i\in \{\mathrm{1,2},\dots ,n\}$ , the objective function is decreasing with respect to $k_i$ . Thus we can derive that ${\sum }_{i=\mathrm{1}}^n‍k_i^{\ast }=\Lambda +{\sum }_{i=\mathrm{1}}^n‍l_i$ . Then there must exist $r\in \{\mathrm{1,2},\dots ,n\}$ , such that $k_r^{\ast }\ge l_r+\mathrm{1}$ . We define $k_{\mathrm{1}}^{\prime },k_{\mathrm{2}}^{\prime },\dots ,k_n^{\prime }$ as follows:

$$\begin{array}{cc}& k_i^{\prime }=\left\{\begin{array}{cc}{k}_i^{\ast }\hfill & i\ne h,\hspace{0.17em}\hspace{0.17em}i\ne r\hfill \\ k_i^{\ast }+\mathrm{1}\hfill & i=h\hfill \\ k_i^{\ast }-\mathrm{1}\hfill & i=r.\hfill \end{array}\right.\end{array}$$

(10)

It is easily verified that the solution $k_{\mathrm{1}}^{\prime },k_{\mathrm{2}}^{\prime },\dots ,k_n^{\prime }$ satisfies all the constraints; then it is a feasible solution to optimization problem (9). We can derive that ${\sum }_{i=\mathrm{1}}^n‍p_i^{k_i^{\prime }}-{\sum }_{i=\mathrm{1}}^n‍p_i^{k_i^{\ast }}=p_h^{l_h+\mathrm{1}}+p_r^{k_r^{\ast }-\mathrm{1}}-p_h^{l_h}-p_r^{k_r^{\ast }}$    $=(p_h^{l_h+\mathrm{1}}-p_h^{l_h})-(p_j^{k_r^{\ast }}-p_j^{k_r^{\ast }-\mathrm{1}})={\lambda }_h(l_h+\mathrm{1})-{\lambda }_r(k_r^{\ast })$ . Since ${\lambda }_r(j)$ is an increasing function with respect to j, then ${\lambda }_r(k_r^{\ast })\ge {\lambda }_r(l_r+\mathrm{1})$ . Since ${\lambda }_h(l_h+\mathrm{1})={\mathrm{m}\mathrm{i}\mathrm{n}}_{i\in \{\mathrm{1,2},\dots ,n\}}\{{\lambda }_i(l_i+\mathrm{1})\}$ , then ${\lambda }_r(l_r+\mathrm{1})>{\lambda }_h(l_h+\mathrm{1})$ . Therefore, we have that ${\sum }_{i=\mathrm{1}}^n‍p_i^{k_i^{\prime }}-{\sum }_{i=\mathrm{1}}^n‍p_i^{k_i^{\ast }}<\mathrm{0}$ , which contradicts the fact that $k_{\mathrm{1}}^{\ast },k_{\mathrm{2}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution. In conclusion, it is proved that $k_h^{\ast }\ge l_h+\mathrm{1}$ .

Theorem 4.

If $k_{\mathrm{1}}^{\ast },k_{\mathrm{2}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution to integer optimization problem (9), then $k_{\mathrm{1}}^{\ast },k_{\mathrm{2}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution to the following integer optimization problem, where $h=\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}{\mathrm{m}\mathrm{i}\mathrm{n}}_{i\in \{\mathrm{1,2},\dots ,n\}}\{{\lambda }_i(l_i+\mathrm{1})\}$ :

$$\begin{array}{ll}min\hfill & \sum _{i=1}^n{p}_i^{k_i}\hfill \\ \text{s}.\text{t}.\hfill & \sum _{i=1}^n{k}_i\le \mathrm{\Lambda }-1+(l_h+1)+\sum _{i=1,i\ne h}^n{l}_i\hfill \\ \hfill & l_i\le k_i\le u_i,\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\}-\left\{h\right\}\hfill \\ \hfill & l_h+1\le k_h\le u_h,\hfill \\ \hfill & k_i\in Z,\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\},\hfill \\ \hfill & p_i\in (0,1),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{l}_i,u_i\in (0,+\infty ),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\}.\hfill \end{array}$$

(11)

Proof.

Based on Lemma 3, it can be verified that the solution $k_{\mathrm{1}}^{\ast },\dots ,k_n^{\ast }$ satisfies all the constraints of problem (11) and then it is a feasible solution to the problem. In the following, we prove that $k_{\mathrm{1}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution for problem (11) by contradiction.

Suppose that $k_{\mathrm{1}}^{\prime },k_{\mathrm{2}}^{\prime },\dots ,k_n^{\prime }$ is the optimal solution to problem (11), and ${\sum }_{i=\mathrm{1}}^n‍p_i^{k_i^{\prime }}<{\sum }_{i=\mathrm{1}}^n‍p_i^{k_i^{\ast }}$ . Due to $l_h+\mathrm{1}\le k_h^{\prime }\le u_h$ , we have $l_h\le k_h^{\prime }\le u_h$ . Then $k_{\mathrm{1}}^{\prime },k_{\mathrm{2}}^{\prime },\dots ,k_n^{\prime }$ is a feasible solution to integer optimization problem (9). It can be known that $k_{\mathrm{1}}^{\prime },k_{\mathrm{2}}^{\prime },\dots ,k_n^{\prime }$ is a better solution to problem (9), which contradicts the fact that $k_{\mathrm{1}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution. In conclusion, $k_{\mathrm{1}}^{\ast },k_{\mathrm{2}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution to problem (11).

Theorem 5.

Let $h_{\mathrm{1}}=\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{m}\mathrm{i}\mathrm{n}}_{i\in \{\mathrm{1,2},\dots ,n\}}\{{\lambda }_i(l_i+\mathrm{1})\}$ , for any $r\in \{\mathrm{2},\dots ,\Lambda \}$ , $h_r$ is defined as follows:

$$\begin{array}{cc}& h_r=\mathrm{a}\mathrm{r}\mathrm{g}\underset{i\in \{\mathrm{1,2},\dots ,n\}}{\mathrm{m}\mathrm{i}\mathrm{n}}\left\{\left\{{\lambda }_i\left(j\right)\right\}-{\displaystyle \bigcup }_{z=\mathrm{1}}^{r-\mathrm{1}}\left\{{\lambda }_{h_z}\left(l_{h_z}+{\displaystyle \sum }_{m=\mathrm{1}}^z‍{\chi }_{h_z}\left(h_m\right)\right)\right\}\right\},\end{array}$$

(12)

where $i\in \{\mathrm{1,2},\dots ,n\},j\in \{l_i+\mathrm{1},\dots ,u_i\}$ . Then $l_{\mathrm{1}}+{\sum }_{r=\mathrm{1}}^{\Lambda }‍{\chi }_{\mathrm{1}}(h_r),l_{\mathrm{2}}+{\sum }_{r=\mathrm{1}}^{\Lambda }‍{\chi }_{\mathrm{2}}(h_r),\dots ,l_n+{\sum }_{r=\mathrm{1}}^{\Lambda }‍{\chi }_n(h_r)$ is the optimal solution to integer optimization problem (9).

Proof.

The proof is by induction on Λ. According to Lemma 2, $l_{\mathrm{1}}+{\sum }_{r=\mathrm{1}}^{\Lambda }‍{\chi }_{\mathrm{1}}(h_r),l_{\mathrm{2}}+{\sum }_{r=\mathrm{1}}^{\Lambda }‍{\chi }_{\mathrm{2}}(h_r),\dots ,l_n+{\sum }_{r=\mathrm{1}}^{\Lambda }‍{\chi }_n(h_r)$ is the optimal solution to problem (9), when $\Lambda =\mathrm{1}$ . Suppose that when $\Lambda \le m-\mathrm{1}$ , the proposition holds. In the following, we prove that, when $\Lambda =m$ , the proposition is true.

Suppose that $k_{\mathrm{1}}^{\ast },k_{\mathrm{2}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution to problem (9), when $\Lambda =m$ . Let $h=\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}{\mathrm{m}\mathrm{i}\mathrm{n}}_{i\in \{\mathrm{1,2},\dots ,n\}}\{{\lambda }_i(l_i+\mathrm{1})\}$ . Based on Theorem 4, we know that $k_{\mathrm{1}}^{\ast },k_{\mathrm{2}}^{\ast },\dots ,k_n^{\ast }$ is the optimal solution to the following integer optimization problem:

$$\begin{array}{ll}min\hfill & \sum _{i=1}^n{p}_i^{k_i}\hfill \\ \text{s}.\text{t}.\hfill & \sum _{i=1}^n{k}_i\le m-1+(l_h+1)+\sum _{i=1,i\ne h}^n{l}_i\hfill \\ \hfill & l_i\le k_i\le u_i,\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\}-\left\{h\right\}\hfill \\ \hfill & l_h+1\le k_h\le u_h,\hfill \\ \hfill & k_i\in Z,\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\},\hfill \\ \hfill & p_i\in (0,1),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{l}_i,u_i\in (0,+\infty ),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i\in \{1,2,\dots ,n\}.\hfill \end{array}$$

(13)

Let $h_{\mathrm{1}}^{\prime }=\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}{\mathrm{m}\mathrm{i}\mathrm{n}}_{i\in \{\mathrm{1},\dots ,n\}}\left\{\left\{{\lambda }_i\left(j\right)\right\}-\left\{{\lambda }_h\left(l_h+\mathrm{1}\right)\right\}\right\}$ . For any $r\in \left\{\mathrm{2},\dots ,m-\mathrm{1}\right\}$ , $h_r^{\prime }$ is defined as follows:

$$\begin{array}{l}{h}_r^{\text{'}}=argmin\{\left\{{\lambda }_i(j)\right\}-\left\{{\lambda }_h(l_h+1)\right\}\phantom{-\underset{z=1}{\overset{r-1}{\cup }}\left\{{\lambda }_{h_z^{\text{'}}}\left(l_{h_z^{\text{'}}}+\sum _{m=1}^z\chi h_z^{\text{'}}\left(h_m^{\text{'}}\right)\right)\right\}\}}\hfill \\ -\underset{z=1}{\overset{r-1}{\cup }}\left\{{\lambda }_{h_z^{\text{'}}}\left(l_{h_z^{\text{'}}}+\sum _{m=1}^z\chi h_z^{\text{'}}\left(h_m^{\text{'}}\right)\right)\right\}\}\hfill \end{array}$$

(14)

By the induction hypothesis, $l_{\mathrm{1}}+{\sum }_{r=\mathrm{1}}^{m-\mathrm{1}}‍{\chi }_{\mathrm{1}}(h_r^{\prime }),\dots$ ,   $l_{h-\mathrm{1}}+{\sum }_{r=\mathrm{1}}^{m-\mathrm{1}}‍{\chi }_{h-\mathrm{1}}(h_r^{\prime })$ ,   $l_h+\mathrm{1}+{\sum }_{r=\mathrm{1}}^{m-\mathrm{1}}‍{\chi }_h(h_r^{\prime }),$   $l_{h+\mathrm{1}}+{\sum }_{r=\mathrm{1}}^{m-\mathrm{1}}‍{\chi }_{h+\mathrm{1}}(h_r^{\prime }),\dots ,$   $l_n+{\sum }_{r=\mathrm{1}}^{m-\mathrm{1}}‍{\chi }_n(h_r^{\prime })$ is the optimal solution to problem (13), and the value of the objective function achieves ${\sum }_{i=\mathrm{1}}^n‍p_i^{k_i^{\ast }}$ . Thus we can know that $l_{\mathrm{1}}+{\sum }_{r=\mathrm{1}}^{m-\mathrm{1}}‍{\chi }_{\mathrm{1}}(h_r^{\prime })+{\chi }_{\mathrm{1}}(h)$ ,  $l_{\mathrm{2}}+{\sum }_{r=\mathrm{1}}^{m-\mathrm{1}}‍{\chi }_{\mathrm{2}}(h_r^{\prime })+{\chi }_{\mathrm{2}}(h),\dots$ ,  $l_h+{\sum }_{r=\mathrm{1}}^{m-\mathrm{1}}‍{\chi }_h(h_r^{\prime })+{\chi }_h(h),\dots$ ,  $l_n+{\sum }_{r=\mathrm{1}}^{m-\mathrm{1}}‍{\chi }_n(h_r^{\prime })+{\chi }_n(h)$ is the optimal solution to problem (9), when $\Lambda =m$ .

Let $h_{\mathrm{1}}=\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}{\mathrm{m}\mathrm{i}\mathrm{n}}_{i\in \{\mathrm{1,2},\dots ,n\}}\{{\lambda }_i(l_i+\mathrm{1})\}$ , and, for any $r\in \{\mathrm{2},\dots ,m\}$ , $h_r$ is defined based on formula (12). It is easily known that for any $i\in \{\mathrm{1,2},\dots ,n\}$ , $l_i+{\sum }_{r=\mathrm{1}}^{m-\mathrm{1}}‍{\chi }_i(h_r^{\prime })+{\chi }_i(h)=l_i+{\sum }_{r=\mathrm{1}}^m‍{\chi }_i(h_r)$ . In conclusion, for a given positive integer Λ, $l_{\mathrm{1}}+{\sum }_{r=\mathrm{1}}^{\Lambda }‍{\chi }_{\mathrm{1}}(h_r),\dots ,l_n+{\sum }_{r=\mathrm{1}}^{\Lambda }‍{\chi }_n(h_r)$ is the optimal solution to problem (9).

3.3. Greedy Algorithm for Computing Optimal Retransmission Threshold

From Theorems 4 and 5, we know that integer optimization problem (9) exhibits the optimal substructure and greedy-choice properties, which are two key ingredients of the greedy approach. In this section, a greedy algorithm for computing the optimal retransmission threshold is proposed.

Suppose that the end-to-end path is $P=j_{\mathrm{1}},j_{\mathrm{2}},\dots ,j_{n+\mathrm{1}}$ , where $j_{\mathrm{1}}$ and $j_{n+\mathrm{1}}$ are source and destination nodes, respectively. Let $p_i$ denote the transmission failure probability over the link from $j_i$ to $j_{i+\mathrm{1}}$ . Suppose that rely node $j_i$ receives a data packet with delay requirement ${\Delta }^{\prime }$ . The greedy algorithm for computing optimal retransmission threshold runs at sensor node $j_i$ as follows. The retransmission thresholds for nodes $j_i,j_{i+\mathrm{1}},\dots ,j_n$ are initialized as $L_i,L_{i+\mathrm{1}},\dots ,L_n$ , respectively, where $L_h$ is the given lower bound of retransmission threshold of node $j_h$ . First, for each $h\in \{i,i+\mathrm{1},\dots ,n\}$ , compute $p_h^{L_h+\mathrm{2}}-p_h^{L_h+\mathrm{1}}$ . Then, the $L_h$ with the minimum value $p_h^{L_h+\mathrm{2}}-p_h^{L_h+\mathrm{1}}$ is incremented by one. The above procedures are repeated ${\Delta }^{\prime }-{\sum }_{h=i}^n‍\left(L_h+\mathrm{1}\right)$ times. The detail of the algorithm is described in Algorithm 1.

Algorithm 1: Greedy algorithm for computing optimal retransmission threshold.

Input: ${\mathrm{\Delta }}^{\prime }$ , $\{p_i,p_{i+\mathrm{1}},\dots ,p_n\},\{L_i,L_{i+\mathrm{1}},\dots ,L_n\},\{U_i,U_{i+\mathrm{1}},\dots ,U_n\}$

Output: optimal retransmission threshold of node i

(1) ${\mathrm{\Delta }}^{\prime }={\mathrm{\Delta }}^{\prime }-{\displaystyle \sum }_{h=i}^n\left(L_h+\mathrm{1}\right)$ ,

(2) for   $k=\mathrm{1}$ to ${\mathrm{\Delta }}^{\prime }$   do

(3)   $term=\mathrm{0}$ ;

(4)  for   $h=i$ to n  do

(5)   if   $L_h+\mathrm{1}\le U_h$   then

(6)     ${\lambda }_h=p_h^{L_h+\mathrm{2}}-p_h^{L_h+\mathrm{1}}$ ;

(7)   else

(8)     ${\lambda }_h=\mathrm{\infty }$ ;

(9)   if   ${\lambda }_h<term$   then

(10)     $term={\lambda }_h$ ;

(11)   $\kappa =\arg \{term\}$ ;

(12)    $L_{\kappa }=L_{\kappa }+\mathrm{1}$ ;

(13) return   $L_i$

For a given delay requirement Δ and a delivery path consisting of n sensor nodes, the cost for computing the optimal retransmission threshold is $O(n\Delta )$ , and the memory complexity is $O(n)$ .

4. $\mathbf{(}\alpha \mathbf{,}\beta \mathbf{)}$ -Probabilistic Delay Bound Based Packet Dropped Protocol

In previous section, we investigate the problem of finding the optimal retransmission thresholds for the relay nodes along a given end-to-end delivery path. Due to the uncertainty of wireless link, stringent retransmission threshold may make the packet forwarded to the destination within deadline with high probability be dropped. Since computing the probabilistic distribution of path delays is NP-hard [27], then we develop an $(\alpha ,\beta )$ -probabilistic delay bound based packet dropped protocol in this section.

The main idea of the proposed protocol is as follows. When a packet fails to be transmitted after a predefined number of retransmissions, if the upper bound of the probability of the delivery delay within the deadline is smaller than α, then the packet is dropped; if the upper bound of the probability of the delivery delay exceeding the deadline is smaller than β, then the packet is transmitted once again. In the following section, the probabilistic path delay bounds are derived.

4.1. Probabilistic Path Delay Bound

Given a path $P=j_{\mathrm{1}},j_{\mathrm{2}},\dots ,j_{n+\mathrm{1}}$ from source node $j_{\mathrm{1}}$ to destination node $j_{n+\mathrm{1}}$ , let $d_{j_i}$ denote the number of transmission trials when $j_i$ forwards the packet to node $j_{i+\mathrm{1}}$ . Then the end-to-end delivery delay over the path is $d_P={\sum }_{i=\mathrm{1}}^n‍d_{j_i}$ , where $d_{j_i}$ follows geometric distribution $G(\mathrm{1}-p_i)$ . Since per-packet transmission time is stable and uncorrelated [22], then we have that $E[d_p]={\sum }_{i=\mathrm{1}}^n‍(\mathrm{1}-p_i{)}^{-\mathrm{1}},\mathrm{V}\mathrm{a}\mathrm{r}[d_p]={\sum }_{i=\mathrm{1}}^n‍p_i(\mathrm{1}-p_i{)}^{-\mathrm{2}}$ .

Property 1.

Suppose that Δ is the delay requirement, let $\delta =\Delta -E[d_p]$ . If $\Delta <E[d_p]$ , then the following inequality holds:

$$\begin{array}{cc}& \mathrm{P}\mathrm{r}\left(d_p\le \Delta \right)\le \frac{\mathrm{V}\mathrm{a}\mathrm{r}\left[d_p\right]}{\mathrm{V}\mathrm{a}\mathrm{r}\left[d_p\right]+{\delta }^{\mathrm{2}}}.\end{array}$$

(15)

If $\Delta \ge E[d_p]$ , then the following inequality can be known:

$$\begin{array}{cc}& \mathrm{P}\mathrm{r}\left(d_p\ge \Delta \right)\le \frac{\mathrm{V}\mathrm{a}\mathrm{r}\left[d_p\right]}{\mathrm{V}\mathrm{a}\mathrm{r}\left[d_p\right]+{\delta }^{\mathrm{2}}}.\end{array}$$

(16)

Proof.

According to one-sided Chebyshev inequality, the following inequality holds, if $t<\mathrm{0}$ and $\mathrm{V}\mathrm{a}\mathrm{r}[x]$ is bounded:

$$\begin{array}{cc}& \mathrm{P}\mathrm{r}\left(x\le E\left(x\right)+t\right)\le \frac{\mathrm{V}\mathrm{a}\mathrm{r}\left[x\right]}{\mathrm{V}\mathrm{a}\mathrm{r}\left[x\right]+t^{\mathrm{2}}}.\end{array}$$

(17)

Similarly, the following inequality holds, if $t\ge \mathrm{0}$ and $\mathrm{V}\mathrm{a}\mathrm{r}[x]$ is bounded:

$$\begin{array}{cc}& \mathrm{P}\mathrm{r}\left(x\ge E\left(x\right)+t\right)\le \frac{\mathrm{V}\mathrm{a}\mathrm{r}\left[x\right]}{\mathrm{V}\mathrm{a}\mathrm{r}\left[x\right]+t^{\mathrm{2}}}.\end{array}$$

(18)

Thus formula (15) and (16) are easily obtained.

4.2. $\mathbf{(}\mathit{\alpha }\mathbf{,}\mathit{\beta }\mathbf{)}$ -Probabilistic Delay Bound Based Packet Dropped Protocol

Suppose that relay node $j_i$ fails to transmit a data packet to node $j_{i+\mathrm{1}}$ after a predefined number of retransmission trials, and the remaining time to the deadline is ${\Delta }^{\prime }$ . For given probability thresholds α and β, $(\alpha ,\beta )$ -probabilistic delay bound based packet dropped protocol implements at sensor node $j_i$ as follows.

Firstly, node $j_i$ computes the expectation and variance of the delivery delay over the path $j_{i+\mathrm{1}},j_{i+\mathrm{2}},\dots ,j_n$ , denoted by μ and σ, respectively. Let $\delta ={\Delta }^{\prime }-\mathrm{1}-\mu$ be the difference between ${\Delta }^{\prime }-\mathrm{1}$ and the expectation of the delivery delay.

Secondly, the node decides whether the packet will be dropped as follows.

Case 1 ( ${\Delta }^{\prime }-\mathrm{1}<\mu$ ).

If $\sigma /(\sigma +{\delta }^{\mathrm{2}})\le \alpha$ , then the packet is dropped; otherwise the packet is transmitted once again.

Case 2 ( ${\Delta }^{\prime }-\mathrm{1}\ge \mu$ ).

If $\sigma /(\sigma +{\delta }^{\mathrm{2}})\le \beta$ , then the packet is transmitted once again; otherwise the packet is dropped.

The detail of the protocol is described in Algorithm 2.

Algorithm 2: $(\alpha ,\beta )$ -Probabilistic delay bound based packet dropped protocol.

Input: $\alpha ,\beta ,{\mathrm{\Delta }}^{\prime }$ , $\{p_{i+\mathrm{1}},p_{i+\mathrm{2}},\dots ,p_n\}$ ,

Output: node $j_i$ retransmits the data packet or drops the data packet

(1) $\mu =\mathrm{0},\sigma =\mathrm{0}$ ;

(2) for   $k=i+\mathrm{1}$ to n  do

(3)   $\mu =\mu +(\mathrm{1}-p_k{)}^{-\mathrm{1}}$ ;

(4)   $\sigma =\sigma +p_k(\mathrm{1}-p_k{)}^{-\mathrm{2}}$ ;

(5) $\delta ={\mathrm{\Delta }}^{\prime }-\mathrm{1}-\mu$ ;

(6) if   ${\mathrm{\Delta }}^{\prime }-\mathrm{1}<\mu$   then

(7)  if   $\left(\sigma /\left(\sigma +{\delta }^{\mathrm{2}}\right)\right)\le \alpha$   then

(8)   The packet is dropped;

(9)  else

(10)   The packet is transmitted once again;

(11) else

(12)  if   $\left(\sigma /\left(\sigma +{\delta }^{\mathrm{2}}\right)\right)\le \beta$   then

(13)   The packet is transmitted once again;

(14)  else

(15)   The packet is dropped;

5. Performance Evaluation

In this section, a series of experiments have been conducted to evaluate the performance of the retransmission threshold setting protocol based on greedy algorithm for computing optimal retransmission threshold (GAORT) and probabilistic delay bound based packet dropped (PDBPD) protocol. The simulations are carried out by MATLAB.

$\mathrm{100}$ sensor nodes and the sink are randomly deployed into a region of size 200 m × 200 m (m for meters) and all the sensors have the same transmission radius 25 m. In each simulation, source node and destination node are randomly selected. Each simulation is repeated $\mathrm{100}$ times and the simulation result corresponds to the average value over $\mathrm{100}$ times. To understand the benefits of the GAORT based protocol, the comparison with General Method is conducted. The main idea of General Method is that we set the same retransmission threshold for all the sensor nodes along a delivery path. In the experimental simulation, Δ is the result of the deadline divided by once transmission time.

The first group of experiments is to investigate the deadline success ratio (DSR) of the GAORT based protocol. In this paper, deadline success ratio is the percentage of the packets delivered to the destination before given deadlines among all the packets. And DSR can be calculated as follows:

$$\begin{array}{l}\text{DSR}=(\#\hspace{0.17em}\text{of packets delivered to the destination}\hfill \\ \text{before given deadlines})\times {\left(\#\hspace{0.17em}\text{of all of the packets}\right)}^{-1}.\hfill \end{array}$$

(19)

Figure 2(a) shows the comparison of DSR between the GAORT based protocol and General Method, when the length of delivery path is $\mathrm{10}$ and the probability of transmission failure, $p_i$ , follows normal distribution $N(\mathrm{0.4,0.2})$ . The GAORT based protocol has better performance in terms of deadline success ratio. For example, when the deadline is 0.11 s, the DSRs of the GAORT based protocol and General Method are $\mathrm{82}\%$ and $\mathrm{69}\%$ , respectively. Figure 2(b) depicts the relationship between the DSRs and the deadlines, when the probability of transmission failure, $p_i$ , follows uniform distribution $U[\mathrm{0.4,0.9}]$ . Figure 2(c) demonstrates the comparison of DSRs under different lengths of delivery path. As expected, the GAORT based protocol can achieve a higher deadline success ratio, since delay requirement and link quality have been taken into account by our protocol. Experimental results show that the GAORT based protocol can optimize the probability of packet delivery within given deadline and the proposed protocol increases the number of retransmissions over the link of inferior quality.

Figure 2

Deadline success ratio of GAORT based protocol.

The second group of experiments is to investigate the real-time ratio (RTR) of the GAORT based protocol. Real-time ratio is the percentage of the packets delivered to the destination before given deadlines among the packets successfully delivered to the destination. And RTR can be calculated as follows:

$$\begin{array}{l}\text{RTR}=(\#\hspace{0.17em}\text{of packets delivered to the destination before}\hfill \\ \text{given deadlines})\hfill \\ \times \hspace{0.17em}{\left(\#\hspace{0.17em}\text{of packets delivered to the destination}\right)}^{-1}\hfill \end{array}$$

(20)

As shown in Figure 3(a), the GAORT based protocol can reach higher real-time ratio than that of General Method, when the length of delivery path is $\mathrm{10}$ and the probability of transmission failure, $p_i$ , follows normal distribution $N(\mathrm{0.4,0.2})$ . Figure 3(b) demonstrates the comparison of RTR, when the probability of transmission failure, $p_i$ , follows uniform distribution $U[\mathrm{0.4,0.9}]$ . Figure 3(c) shows that the GAORT based protocol has better performance in terms of RTR, when the length of delivery path is increased from $\mathrm{5}$ to $\mathrm{10}$ . For example, the RTR of the GAORT based protocol is more than $\mathrm{75}\%$ . Experimental results indicate that the protocol based on GAORT can reduce the number of retransmission for the packets, which are forwarded to the destination nodes before given deadlines with low probabilities. Therefore, the GAORT based protocol improves the real-time ratio and the energy efficiency.

Figure 3

Real-time ratio of GAORT based protocol.

The third group of experiments is to investigate the performance of PDBPD protocol. The comparisons between Normal Method and PDBPD protocol are carried out. The main idea of Normal Method is that a data packet is dropped after a predefined number of retransmissions, where the retransmission threshold is the result by implementing GAORT. As shown in Figures 4(a) and 4(b), PDBPD protocol achieves higher deadline success ratio than that of Normal Method, when the probability of transmission failure, $p_i$ , follows normal distribution $N[\mathrm{0.6,0.2}]$ . For example, the DSRs of PDBPD protocol and Normal Method are $\mathrm{80}\%$ and $\mathrm{73}\%$ , respectively, when the deadline is 0.12 s and the length of delivery path is $\mathrm{10}$ . Figure 4(c) demonstrates the comparison of DSRs, when the probability of transmission failure follows uniform distribution $U[\mathrm{0.3,0.6}]$ . Experimental results show that PDBPD protocol can avoid dropping the packets, which are forwarded to the destination before given deadlines with high probabilities.

Figure 4

Performance of $(\alpha ,\beta )$ -probabilistic delay bound based packet dropped protocol.

6. Conclusion

As one of the promising, high-value applications for CPS, deployments of large-scale WSNs have potential to shed light on a variety of monitoring purposes. Many time-sensitive applications impose high requirement on real-time response. There exist many algorithms and routing protocols for efficient data packet delivery. However, previous works set the same retransmission threshold for all the relay nodes along a delivery path. The method decreases the probability of a packet being transmitted through the delivery path within given deadline. In this paper, we focus on finding the optimal retransmission thresholds for the relay nodes, such that the summation of the probability of a packet being transmitted to the next relay node or destination node within the specified deadline is maximized. A distributed greedy algorithm that can be run on sensor node is proposed, which enables the sensor node to adaptively set the optimal retransmission threshold. To avoid dropping the packet forwarded to the destination within given deadline with high probability, we develop an $(\alpha ,\beta )$ -probabilistic delay bound based packet dropped protocol. Experimental results show that the proposed protocols have better performance.