# A Constrained Coding-Aware Routing Scheme in Wireless Ad-Hoc Networks
## 1 Introduction  
Over the past few years, given the increased requirements of the network throughput and delay in wireless networks, network coding (NC), proposed by [PERSON] et al., has received much attention [1]. NC can achieve the upper limit of the maximum transmission flow. Compared with the traditional store-and-forward transmission method, NC allows for the intermediate nodes to mix some packets from different flows and broadcast the encoded packets to the receivers. Figure 1 illustrates a simple example of the NC idea, where Nodes A and B need to exchange some data via the intermediate Node R. The traditional store-and-forward method is shown in Figure 0(a). After the intermediate Node R receives the Packet P1 (P2) from Node A (B), it will transmit Packet P1 (P2) to Node B (A). The transmission counts are four times in this process, and it may not be the best choice. Now, considering the transmission with the NC idea in Figure 0(b), Node A (B) sends its respective Packet P1 (P2) to intermediate Node R. Then, Node R has a coding opportunity and can encode the two packets with an exclusive or (XOR) operation and broadcast the encoded Packet P1\(\oplus\)P2. Nodes A and B can recover the encoded packet by their own packet with a simple XOR operation again. The transmission counts are only three times in this NC-based transmission process, and the reduced transmissioncounts can save energy. NC is more useful for wireless networks because it can explore the broadcast nature of wireless links and reduce the negative characteristics (e.g., interference, channel fading, and energy constraints) [2; 3]. Moreover, the NC technology can be also widely applied to numerous aspects, such as distributed storage, cognitive radio, communication security, and P2P streaming system [4]. Not surprisingly, the NC technology and routing protocols can be combined. The first practical NC-based routing scheme, called COPE, was proposed by [PERSON] et al. [5]. They combined the routing protocol and network coding in a real network test-bed that can detect the coding opportunities and increase the network performance obviously [6]. However, the COPE-like schemes have some disadvantages: for example, their coding opportunities depend on certain topologies and limits in the two-hop region [7]. For more flexible detection of the coding opportunities, some researchers have combined the NC and opportunistic routing (OR) technologies, termed \"coding-aware routing (CAR)\". In the CAR scheme, the relay nodes can be aware of all the information of one-hop neighbors and flows and can then judge whether to encode according to the link quality or other information [8]. However, the traditional CAR scheme may induce more overhead, and the coding opportunities will concentrate on the part of flows [9]. Then, based on CAR, [PERSON] et al. proposed a distributed coding-aware routing (DCAR) scheme [10]. Because the candidate paths are diverse and have no fixed route in wireless multi-hop networks [11], the DCAR scheme introduced the primary coding conditions (PCC) to detect all possible coding opportunities in all candidate paths, which are more suitable for wireless multi-hop networks. The simulation results showed that the DACR scheme has much higher throughput than the original CAR and COPE-like schemes. Then, based on PCC, more DACR-type schemes emerged in large numbers [12; 13; 14; 15]. [PERSON] et al. proposed a free-ride-oriented routing metric to make PCC more implementable [12]. [PERSON] et al. improved the routing decision process to suit PCC and ensure a higher decoded ratio [14; 15]. [PERSON] et al. applied a consistency of encoding and overhearing (CEO) principle to the DCAR scheme to guarantee successful decoding of all encoded or re-encoded packets [16]. In addition, although the DCAR-type schemes have more coding opportunities and larger network throughput by PCC, they will cause imbalanced loads, for which the encoded and decoding nodes will coincide or be closed.