# A Constrained Coding-Aware Routing Scheme in Wireless Ad-Hoc Networks
## 3 Routing Implementation
### Coding Conditions
_Existing node_ \(d_{2}\in\text{Bac}(c,f_{b})\)_, meanwhile_ \(d_{2}\in\{N(s_{1})\cap\text{Bac}(c,f_{b})\}\) _and_ \(s_{1}\in\text{For}(c,f_{a})\)_, or_ \(d_{2}\in\text{Bac}(c,f_{a})\)_._  
In the constrained coding conditions, \(s_{1}\), \(s_{2}\) and \(d_{1}\), \(d_{2}\) are still the source and destination nodes. Moreover, the decoding nodes can be near the destination node. Then, the network hot-spots can be avoided. As shown in Figure 1(b), Node R5 is the decoding node and the neighbor node next to D2 and S1, which is away from the coding Node R3. In a multi-flow network, the primary coding conditions can also lead to the re-encoding phenomenon and decrease the decoding-success ratio. For example, three flows exist at a certain moment in Figure 3, (i.e., \(f_{1}\) (from Node S1 to Node D1), \(f_{2}\) (from Node S2 to Node D2), and \(f_{3}\) (from Node S3 to Node D3)). As shown in Figure 2(a), because the flows \(f_{1}\) and \(f_{3}\) satisfy the primary coding conditions, Node R1 will be selected as a coding node and broadcast the encoded Packet P1\(\oplus\)P3. Node R2 can receive the encoded Packet P1\(\oplus\)P3. To prevent subsequent no-decoding opportunities in the future, the encoded packet should be decoded as soon as possible. Thus, Node R2 decodes the encoded Packet P1\(\oplus\)P3 and generates the original Packet P1. However, flows \(f_{2}\) and \(f_{3}\) meet  
Figure 2: The routing decision with different coding conditions in a two-flow network. at Node R2, and Node R2 also has a coding opportunity to encode the original Packets P1 and P2. To this end, Node R2 transmits the encoded Packet P1\(\oplus\)P2. Node R2 contains both the coding and decoding opportunities. The burden of Node R2 will increase, and the network load will be unbalanced. Moreover, Node D2 only overhears the encoded packets P1\(\oplus\)P3, and it cannot decode the encoded Packet P1\(\oplus\)P2 received from Node R2. To avoid these phenomena, we can use the constrained coding conditions to judge the coding opportunities. As shown in Figure 2(b), similar to the primary coding conditions, Node R1 is also the coding node for flows \(f_{1}\) and \(f_{3}\). However, Node R2 continues to encode the received Packet P1\(\oplus\)P3 with the original Packet P2 and generates the encoded Packet P1\(\oplus\)P2\(\oplus\)P3. The decoding node is selected as Node R3 instead of Node R2, which can overhear the original packets P2 and P3. We can see that the decoding node is constrained in the neighbors of the source node to avoid the hot-spot problem. In addition, the destination Node D2 can successfully decode the received Packet P1\(\oplus\)P2\(\oplus\)P3 due to it being able to overhear the encoded Packet P1\(\oplus\)P3 from Node R1. We can see that the constrained coding conditions can avoid the re-encoding problem and ensure the decoded success probability. Moreover, compared with the constrained coding conditions, the primary coding conditions have a higher computational complexity. They often need to calculate each node of the forward and backward flows and loop twice. Then, we analyze the computational complexity in a two-flow network, which is a simple scene and similar to that of multi-flow networks. In a two-flow network, we define that the numbers of the forward nodes of the flows \(f_{1}\) and \(f_{2}\) are \(J_{1}\) and \(J_{2}\), respectively, and the numbers of the backward nodes of flows \(f_{1}\) and \(f_{2}\) are \(K_{1}\) and \(K_{2}\), respectively. The computational complexity is \(O(J_{1}K_{2}+J_{2}K_{1})=O(n^{2})\). However, the constrained coding conditions only need to calculate the number of neighbor nodes of the sources, and the sources are known. We assume that the number of neighbor nodes of Sources S1 and S2 are \(L_{1}\) and \(L_{2}\), respectively, and the computational complexity is \(O(L_{1}+L_{2})=O(n)\). Figure 3: The routing decision with different coding conditions in a multi-flow network.