# A Constrained Coding-Aware Routing Scheme in Wireless Ad-Hoc Networks
## 3 Routing Implementation
### Routing Coding Benefit
#### 3.4.1 Coding Benefit Function with Queue Length  
Data transmission with NC can reduce the transmission number and improve the performance in the multi-hop scenario [6]. Similar to ETX, we utilized the minimum expected transmission count to mainly measure the coding benefit. Before we introduce the coding benefit function, the symbols should be defined. Assume that \(k\) candidate routes exist and \(P_{l}(1\leq l\leq k)\) denotes the \(l^{\text{th}}\) candidate path. Let \(H(P_{l})\) be the hop number of the \(l^{\text{th}}\) candidate path. The minimum expected number among the set of all the candidate paths can be defined as follows:  
\[e_{\min}(P_{l})=\min_{1\leq l\leq k}H(P_{l}). \tag{1}\]  
We can see that the hop number of transmissions along the candidate paths is always larger than or equal to \(e_{\min}\). Moreover, the path cost \(M(P_{l})\) can be defined as:  
\[M(P_{l})=H(P_{l})-e_{\min}(P_{l}). \tag{2}\]  
Then, considering that two packets are coded as shown in Figure 1b, one transmission can be saved. Analogously, if \(n\) packets are encoded in a coding node, \(n-1\) transmissions can be saved due to the broadcast. While there are \(n_{m}\) packets in the coding node \(C_{m}\) on a candidate path, the benefit of the coding node \(C_{m}\) can be calculated as:  
\[\beta(C_{m})=n_{m}-1. \tag{3}\]  
As there are \(v\) coding nodes in the candidate path \(P_{l}\), we define \(D(P_{l})\) as the benefit of candidate path \(P_{l}\), which can be shown as follows:  
\[D(P_{l})=\sum_{m=1}^{v}\beta(C_{m}). \tag{4}\]  
According to (1), (2), and (4), to compute the actual number of transmissions in a multi-flow network on each path, we define the candidate path benefit \(\beta(P_{l})\) as follows:  
\[\beta(P_{l}) =D(P_{l})-M(P_{l})\] \[=\sum_{m=1}^{v}(n_{m}-1)-[H(P_{l})-e_{\min}(P_{l})]. \tag{5}\]  
We can see that \(\beta(P_{l})\) contains the benefit of decreased hop number \(D(P_{l})\) and path cost \(M(P_{l})\). Equation (5) indicates that we should choose the shorter path with more coding benefits. The larger the path benefit \(\beta(P_{l})\) is, the better the path. Moreover, the path benefit can be easily calculated when \(e_{\min}\) is selected and when the network is large. When multiple flows with different rates merge on a coding node, the coding node will be in a confused state, and the coding opportunity may be bad. Moreover, the state of the coding nodes is an important factor to determine the network delay [34; 35; 37]. Therefore, we need to consider the state of the coding nodes. It is important to note that the queue length is more feasible to calculate [10; 37]. For a realistic scenario with processes with different rates, each flow with different rates has different numbers of input queues in a time-slot. In this scheme, to resolve the multi-rate matching problem, instead of the accurate and complex measurement, we adopt an approximate method (i.e., using the queue length) to estimate the state of coding nodes. In the coding nodes, the output queue will be encoded and shortened by NC. For example, as shown in Figure 6, it is assumed that a coding node receives 4, 3, and 5 original packets from Flows 1, 2, and 3, respectively. In the traditional method, the total output queue length is 12. However, by the NC technology, the output queue length is shortened to six, and the length of encoded packets is three. Moreover, when the encoded packets are in the output queue, the coding nodes can transmit the unencoded at the same time, which is the free-rider phenomenon. In the output queue of coding nodes, more encoded and fewer original packets show that the coding opportunity is good. Therefore, we can obtain the proportion of the number of encoded packets in the output queue to measure the state of coding nodes. Assume that \(t\) flows intersect in the coding node \(C_{m}\). We define \(L(f_{j})\) as the length of input queue of flow \(j\quad(1\leq j\leq t)\).