# A Constrained Coding-Aware Routing Scheme in Wireless Ad-Hoc Networks
## 3 Routing Implementation
### Coding Conditions  
The coding conditions are essential components in coding-aware routing schemes to determine which nodes have coding opportunities. Then, we first review the primary coding conditions that can detect the coding opportunities on all paths. We will then introduce the constrained coding conditions and describe the difference between the primary and constrained coding conditions in both two-flow and multi-flow networks. Let \(z\) denote a node. \(N(z)\) denotes the set of each one-hop neighbor of node \(z\), and \(f\) denotes a flow path. If node \(z\) belongs to a flow path \(f\), \(z\in f\) is recorded. Let \(\text{For}(z,f)\) and \(\text{Bac}(z,f)\) denote the sets of the forward and backward nodes of a flow path \(f\), respectively. For example, as shown in Figure 1(a), For(R3, \(f_{1}\)) = {D1}, Bac(R3, \(f_{1}\)) = {R1, R2, S1}, For(R3,\(f_{2}\)) = {R4, R5, D2}, and Bac(R3, \(f_{2}\)) = {S2}. Moreover, when \(n\) flows \((f_{1},f_{2},\cdots,f_{n})\) intersect at node \(c\), the definitions of the primary coding conditions are specified as follows:  
**Definition 1**. : _Assuming that any two flows \(f_{a}\) and \(f_{b}\) pass in any intersection node \(c\), the necessary and sufficient conditions of coding opportunities are as follows:_  
1. _Existing node_ \(d_{1}\in\text{Bac}(c,f_{a})\)_, meanwhile_ \(d_{1}\in N(s_{2})\) _and_ \(s_{2}\in\text{For}(c,f_{b})\)_, or_ \(d_{1}\in\text{Bac}(c,f_{b})\)_._
2. _Existing node_ \(d_{2}\in\text{Bac}(c,f_{b})\)_, meanwhile_ \(d_{2}\in N(s_{1})\) _and_ \(s_{1}\in\text{For}(c,f_{a})\)_, or_ \(d_{2}\in\text{Bac}(c,f_{a})\)_._  
Given that existing backward nodes (i.e., \(d_{1}\in\text{Bac}(c,f_{a})\) and \(d_{2}\in\text{Bac}(c,f_{b})\)) must overhear or have the original packets in the primary coding conditions, this can ensure that the destinations have decoding opportunities and obtain their respective packets. Moreover, \(s_{1}\), \(s_{2}\) and \(d_{1}\), \(d_{2}\) can be arranged with any node along the backward and forward nodes of the flow instead of the source and destination nodes [12; 14; 15]. Moreover, the intermediate nodes need to decode the encoded packets at \begin{table}
\begin{tabular}{c c} \hline \hline
**Terms** & **Definition** \\ \hline Original packets & Nonencoded data packets \\ Encoded packets & The packets after the encoded operation \\ Encoded flows & The flows that incorporate the encoded packets \\ Coding nodes & The nodes that meet the coding conditions and perform the encoded function \\ Decoding nodes & The nodes that can decode the encoded packets \\ Output queue & A queue at each node to deposit the packets that need to be sent \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Definition of terms. the earliest possible moment to guarantee the decoding success ratio. For example, take the dotted box in Figure 1(a). Node R4 is the selected node, which can receive the encoded Packet P1\(\oplus\)P2 and overhear the original packets from Node R2. Thus, based on the primary coding conditions, Node R4 will decode the encoded Packet P1\(\oplus\)P2 and transmit the original Packet P2. However, Node R4 will be closed to the coding Node R3. The decoding and coding nodes will gather in the region. The network load will be congested and have an unbalanced distribution, especially in more complex networks. Then, we propose the constrained coding conditions to trade off the network load and coding opportunities. The definition of the constrained coding conditions is specified as follows:  
**Definition 2**. : _Assuming that any two flows \(f_{a}\) and \(f_{b}\) pass in any intersection node \(c\), the necessary and sufficient conditions of coding opportunities are as follows:_  
1. _Existing node_ \(d_{1}\in\text{Bac}(c,f_{a})\)_, meanwhile_ \(d_{1}\in\{N(s_{2})\cap\text{Bac}(c,f_{a})\}\) _and_ \(s_{2}\in\text{For}(c,f_{b})\)_, or_ \(d_{1}\in\text{Bac}(c,f_{b})\)_._
2.