# Optimizing Retransmission Threshold in Wireless Sensor Networks
## 3 Problem Description
### Problem Definition  
Suppose that the end-to-end path is \(P=j_{1}\), \(j_{2},\ldots,\)\(j_{n+1}\), where \(j_{1}\) and \(j_{n+1}\) are source and destination nodes and other \(j_{i}\)'s are relay nodes. There exist the following four attributes for each link \(j_{i}\to j_{i+1}\). * transmission time \(t\): This means that once transmission costs time, including encoding and wireless communication. Usually each sensor node takes the same time for once transmission. * transmission failure probability \(p_{i}\): \(p_{i}\) denotes the transmission failure probability over the link \(j_{i}\to j_{i+1}\). It means that \(p_{i}\) is the probability of a transmission failure due to either collisions or bad channel quality when node \(j_{i}\) forwards a packet to node \(j_{i+1}\). * retransmission threshold \(K_{i}\): This means that the maximum number of retransmission trials is \(K_{i}\). It is obvious that the maximum number of transmission retries is \(K_{i}+1\), and thus, the packet will be eventually dropped by the sender after the \(K_{i}+1\) transmission retries. It can be known that \(1-p_{i}^{K_{i}+1}\) is the probability of a packet being successfully delivered to node \(j_{i+1}\). * retransmission threshold \(A_{i}\): Each hop delay consists of the transmission delay over the wireless link and the queuing delay in the buffer [9]. \(A_{i}\) denotes the number of the packets queued at node \(j_{i}\), which means that there exist \(A_{i}+1\) packets to be forwarded [6]. We define the metric of a given retransmission threshold as the probability of a packet being successfully delivered through the link. Existing works exploit multipath routing to guarantee both reliability and deliver delay in WSNs [13, 27, 28]. Similarly to [5, 9], we aggregate the measure over a path based on the metric and aim at maximizing the summation of the probability of the packet delivered to the next relay node along the given path within the deadline. The path-metric estimates the given path forwarding quality, and it considers both transmission reliability and delay constraint. The end-to-end delay over a path is the summation of the delays of all of the hops along the path. Let \(\delta\) denote the delay constraint. Then, the problem of finding the optimal retransmission thresholds for each node can be formulated as the following integer optimization problem, where \(L_{i}\) and \(U_{i}\) are the given lower and upper bounds of the retransmission threshold of node \(i\). \[ \begin{split}\max\sum_{i=1}^{n}\left(1-p_{i}^{K_{i}+1}\right)\\ s.t.\sum_{i=1}^{n}\left(A_{i}+1\right)(K_{i}+1)t\leq\delta\\ L_{i}\leq K_{i}\leq U_{i},K_{i}\in Z,i\in\{1,2,...,n\}\end{split}  \tag{1}\]  
Each hop delay consists of the transmission delay and the queuing delay in the buffer; thus, the maximum delay latency for each hop is \((A_{i}+1)(K_{i}+1)t\). The first inequality constraint means that the deliver delay of the last packet served at source node \(j_{1}\) is no more than the deadline constraint \(\delta\). The second inequalities mean that the retransmission thresholds should be bounded in a given interval. For the convenience of formalization and analysis, let \(\Delta\) denote \(\delta/t\). For any \(i\in\{1,2,...,n\}\), let \(a_{i}=A_{i}+1,k_{i}=K_{i}+1,l_{i}=L_{i}+1\) and \(u_{i}=U_{i}+1\); then, the problem above is equivalent to the following integer optimization problem.