# A Constrained Coding-Aware Routing Scheme in Wireless Ad-Hoc Networks
## 3 Routing Implementation
### Encoding and Decoding Implementation  
In this subsection, we discuss the issue of the encoding implementation involved in the constrained coding-aware routing scheme. To facilitate the analysis, we define a fixed duration \(T\). In this scheme, we used the time division duplex (TDD) technique to divide each timeslot \(T\) into two sub-timeslots \(T/2\). TDD is one of the duplexing methods and applied to the IEEE 802.11g standard, which is widely used in wireless ad-hoc networks. The duplexing methods allow receiving and sending at the same time. The primary benefit of TDD is that only one channel is needed. It saves spectrum space and cost. Moreover, it is possible to change the uplink and downlink capacity ratio dynamically according to the need. Moreover, TDD requires time synchronization at the network level. IEEE 802.11 standards specify a clock synchronization protocol (i.e., the network time protocol (NTP)), and the related content can be found in [43; 44]. In the first sub-timeslot, the relay nodes receive the original packets. Moreover, the encoded packets are generated by original packets and transmitted in the second sub-timeslot. As shown in Figure 7, in Timeslot 1, the node receives three original packets and transmits an encoded packet in different sub-timeslots. Because the coding nodes receive the original packets from different flows with different rates, the coding node needs an additional timeslot to await coding opportunities. We present a simple example with a one packet/timeslot flow rate, which is as shown in Figure 7. The coding opportunities are to encode three packets from Flows 1, 2, and 3, and the original packets are successfully encoded in Timeslot 1. In Timeslot 2, the packets from Flows 1 and 2 dissatisfy the preset coding opportunities. The coding node needs an extra timeslot (e.g., Timeslot 3) to wait for another packet from Flow 3 and temporarily puts the received packets into the packet pool. In addition, notice that the coding node does not spend too much time waiting for the slow rate flows. In addition, in this paper, we set the expiration time to two timeslots. For example, in the two timeslots 4-5, the coding node cannot encode the original packets, and the node should directly transmit the originals in Timeslot 6. This encoding implementation not only guarantees coding opportunities, but also reduces the network delay. Figure 6: An example of the output queue. Figure 7: An example of the encoding implementation. Let \(a_{j}[x]\) denote the packets from flow \(j\) in the output queue of coding node \(C_{m}\) at the end of the \(x^{\text{th}}\) timeslot. Then, \(a_{j}[x]\) can be determined as:  
\[a_{j}[x]=a_{j}[x-1]+b_{j}[x]-d_{j}[x], \tag{8}\]  
where \(a_{j}[x-1]\) denotes the packets awaiting delivery at the \(x-1^{\text{th}}\) timeslot and \(b_{j}[x]\) denotes the original packets from flow \(j\), which is also the input queue from flow \(j\). \(d_{j}[x]\) denotes the packets that can be encoded in the input queue at the end of the \(x^{\text{th}}\) timeslot. If \(t\) flows intersect in coding node \(C_{m}\), the encoded packets \(d_{m}[x]=\oplus d_{j}[x]\quad(1\leq j\leq t)\). We also denote the output queue of the coding node \(C_{m}\) as \(U_{m}[x]\) at the end of the \(x^{\text{th}}\) timeslot, which is given by:  
\[U_{m}[x]=\sum_{j=1}^{t}a_{j}[x]+d_{m}[x]. \tag{9}\]  
According to the previous analysis, we present an encoding algorithm as shown in Algorithm 1. When a coding node has no coding opportunity (i.e., code_o \(\
eq\) T), it will proceed to Step 2. If it has a coding opportunity (i.e., code_o \(=\) T), it will examine whether the arriving flows can be encoded according to the constrained coding conditions as Step 5 or 9. When the arriving flows are less than the required number (i.e., flow_n \(<\) code_f), no packets are placed in the output queue \(U_{m}[x]\) as Step 6, and the expire time of coding will be set to two timeslots as Step 7. Steps 9-17 show the detailed process of encoding the packets of different sizes.