# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 1 Introduction
If the protocol is set by a high retransmission threshold, such as 29, in the CTPprotocol [15], without the consideration of delay requirement, thus the probability for successfully transmitting the first packet through the link \(S\to B\) can be significantly improved. However, this strategy may make the deadlines of both packets expire and consumes more system resource. If the maximum number of transmission trials is three for each node, in view of the summation of transmission trials, there are no more than nine. Then, the probability of the first packet passing the link \(S\to B\) is \(1-0.9^{3}=0.271\). However, if the retransmission thresholds of the three nodes are set to 6, 0 and 0, that is the maximum numbers of transmission trials are 7, 1 and 1, then the probability is \(1-0.9^{6}=0.927\). In terms of latency and reliability, there is a tradeoff in determining the retransmission threshold. Therefore, the retransmission threshold should be carefully chosen to achieve desirable QoS provisioning [9]. Figure 1: Impact of the retransmission threshold on the probability of packet delivery. From the example above, it is obvious that the retransmission threshold has significant impact on the delivery performance in terms of delay and reliability. Few studies focus on the optimization of the retransmission threshold [5; 14], and they have the following two major disadvantages. In the feedback control-based framework [5], a heuristic method for adjusting the transmission numbers is proposed, which does not provide the reliability guarantee. In our previous work [14], a greedy-based algorithm for finding optimal retransmission thresholds is proposed, which overlooks the impact of queue length on the forwarding quality. The aforementioned observation motivates us to investigate the problem of finding optimal retransmission thresholds in this paper. The problem is formalized as an integer optimization problem first. Then, a dynamic programming-based distributed algorithm for solving the problem is proposed. It can be run on a sensor node and enables the node to adaptively set the optimal retransmission threshold based on the link quality and the remaining time to deadline. Its time complexity is \(O\left(n\Delta\cdot\max_{1\leq i\leq n}\{u_{i}\}\right)\), where \(u_{i}\) is the given upper bound of the retransmission threshold of sensor node \(i\) in a given delivery path and \(n\) is the length of the delivery path. The complexity depends on delivery delay \(\Delta\). If \(\Delta\) is less than or equal to the polynomial, the complexity of the algorithm is polynomial. Otherwise, the algorithm is not efficient. In this case, a \((1+p_{min})\)-approximation algorithm is provided based on the linear programming. Furthermore, when the ranges of the upper and lower bounds of the retransmission thresholds are big enough, a Lagrange multiplier-based distributed \(O(1)\)-approximation algorithm with time complexity \(O(1)\) is developed. The main contributions of the paper are as follows. * The problem of finding optimal retransmission thresholds for each node along a delivery path is defined and is formalized as an integer optimization problem. * A Dynamic Programming-based Distributed Algorithm (DPDA) for solving the problem above is proposed; the correctness of the algorithm is proven; and its time and space complexity are analyzed, _i.e._, \(O\left(n\Delta\cdot\max_{1\leq i\leq n}\{u_{i}\}\right)\), and \(O\left(n\Delta\cdot\max_{1\leq i\leq n}\{u_{i}\}\right)\). * In case of the delivery delay \(\Delta\) being greater than the polynomial, a Linear Programming-based \((1+p_{min})\)-Approximation Algorithm (LPAA) is proposed. * Furthermore, in the case of the ranges of the upper and lower bounds of the retransmission thresholds being big enough, a Lagrange Multiplier-based Distributed Approximation Algorithm (LMDAA) with time complexity \(O(1)\) is proposed. * Simulation experiments are conducted to evaluate the proposed algorithms.