## 5 Reliable Data Forwarding Algorithm
### Feasibility Analysis  
To analyze the feasibility of the ARQ-\(\infty\) based scheme, energy-efficiency is evaluated with the expected number of transmissions required to reach a destination node. Other aspects of performance, such as latency, are not evaluated. The transmission count is compared against other common reliability schemes: multipath routing and traditional transport protocol. To simplify the evaluation, the analysis assumes static network topology and assumes that MAC layer acknowledgment for a data frame is always received. An analysis of transport protocols that utilize distributed caching is omitted as their performance depend on how well the data cache is distributed. In the worst case, data is cached near source node and the number of transmitted attempts is similar to the traditional transport protocol. In the best case, data is cached at the hop in which the transmission failed and the number of transmission attempts is similar to the ARQ-\(\infty\) scheme. In the ARQ-\(\infty\) scheme, the expected number of transmission attempts on a path consisting of \(L\) hops  
Figure 18: Routing layer end-to-end reliability scheme with intermediate node buffering. is  
\[T_{ARQ-\infty}=\sum_{i=0}^{L-1}a_{i}^{M}, \tag{5}\]  
where \(a_{i}^{M}\) is the number of transmissions on \(i\)th hop. It is calculated based on the link reliability \(r_{i}\) as  
\[a_{i}^{M}=1+\sum_{j=1}^{M}(j+1)\cdot(1-r_{i})^{j}\cdot r_{i}, \tag{6}\]  
where \(M\) is the limit for transmission attempts. For example, in IEEE 802.15.4 and IEEE 802.11, the default number of transmission attempts is 4 (3 retries). In ARQ-\(\infty\) scheme the number of attempts is not limited (\(M=\infty\)) and (6) can be rewritten as  
\[a_{i}^{\infty}=1-r_{i}+\frac{1}{r_{i}}. \tag{7}\]  
In multipath routing utilizing \(n\) alternative paths the expected number of transmission attempts is  
\[T_{mp}=\sum_{j=0}^{n-1}\sum_{i=0}^{L_{j}-1}a_{i}^{M}, \tag{8}\]  
where \(L_{j}\) is the path length of the \(j\)th path. The equation assumes that multiple paths do not converge, thus representing the simplest case of controlled multipath routing. The analysis with the transport protocol is slightly more complex as a packet drop on any link on the route causes retransmission at the source node. This analysis assumes that retransmission timers are optimal and do not trigger while packet is still being transmitted. Also, we do not consider batch transmissions, which would decrease overhead as several packets can be acknowledged with one reply packet. The expected number of transmissions on each hop depends on the position of the hop at the route. If transmission succeeds on a certain hop but fails at later hop, the packet must be retransmitted again. Therefore, we calculate the probability that the transmission succeeds in hops \(i..L-1\) as  
\[D_{i}=\prod_{j=i}^{L-1}1-(1-r_{j})^{M}, \tag{9}\]  
where \(r_{j}\) the packet error rate at \(j\)th link and \(M\) is the transmission limit. The total number of transmission attempts at \(i\)th hop is defined as  
\[A_{i}=a_{i}^{M}\cdot\Big{(}1+\sum_{j=1}^{\infty}(D_{i})^{j}\cdot(1-D_{i}) \Big{)}=a_{i}^{M}\cdot\Big{(}D_{i}+\frac{1}{1-D_{i}}\Big{)}. \tag{10}\]  
Finally, the expected number of transmissions to deliver packet from a source to the destination defined as  
\[T_{tp}=\sum_{i=0}^{L-1}A_{i}. \tag{11}\]  
In a transport protocol, the destination confirms the data packet with an acknowledgment. If the source does not receive the acknowledgment, a timer triggers and the packet is retransmitted. Thus, the total number of transmissions is modified with the expected number of times the acknowledgment needs to be send as  
\[T_{tpa}=T_{tp}\cdot\left(1+\sum_{i=1}^{\infty}(i+1)\cdot(1-D_{0})^{j}\cdot D_{0} \right)=1-D_{0}+\frac{1}{D_{0}}, \tag{12}\]  
where \(D_{0}\) is the probability that an acknowledgment is successfully delivered over the whole path and is calculated with (9). To analyze the performance of difference schemes, we consider a route consisting of 5 hops.