# A Constrained Coding-Aware Routing Scheme in Wireless Ad-Hoc Networks
## 2 Related Work  
Concerning the routing protocols applied in wireless ad-hoc networks, the first attempt was the destination-sequenced distance-vector (DSDV) routing protocol, which was based on the Bellman-Ford algorithm [17]. By evaluating and utilizing the link state, [PERSON] et al. proposed an optimized link state routing (OLSR) protocol to find a route with a better link actively [18]. However, these routing protocols, which belong to a proactive work style, may induce more energy consumption. Some routing protocols focus on a reactive work style. [PERSON] proposed an ad-hoc on-demand distance vector (AODV) routing protocol with a lower network overhead and network utilization [19]. To adapt to the changes in the network topology, dynamic source routing (DSR) was proposed by [PERSON] [20]. Moreover, OR and CAR are also attributable to this type of routing [8]. CAR can apply to different wireless multi-hop networks [21], such as wireless mesh networks [22], wireless ad-hoc networks [23], and wireless sensor networks [24]. The CAR schemes are often classified into two categories. One is called intra-flow coding (IAC) routing, which can encode the original packets that belong to the same flow [25]. [PERSON] et al. proposed a constraint-aware IAC scheme to enhance reliability [26]. The other is inter-flow coding (IRC) routing, which can encode the original packets from different flows. The work in [27] combined the IAC and IRC methods to improve the robust performance of lossy wireless networks. However, the IAC method is more complicated than the IRC method because it will consume more time slots to send different data to different destinations. In this paper, we only focus on the IRC routing mechanisms. In these mechanisms, COPE [6] is the first IRC routing mechanism applied to practical wireless network protocols. COPE is also compatible with existing network protocols and algorithms. It has a better performance than traditional store-and-forward transmission methods using TCP and UDP. Many other derivatives have appeared. However, the COPE-like schemes have limitations such that the analyses are often in regular topologies, such as the Alice-Bob topology, X-topology, Y-topology, and star topology. Then, to make the CAR schemes no longer dependent on regular topologies, [PERSON] et al. [10] proposed a distributed solution, the DCAR scheme, to increase the ability of detecting the coding opportunities. Based on PCC, the coding opportunities can be carefully found in all possible routes. Compared to COPE, DCAR obtains better performance in terms of the network throughput and delay. Many researchers used the DCAR idea to design different routing schemes for a more complex wireless network. However, choosing when, where, and which packets to encode in wireless networks is an NP-hard problem [28]. Moreover, PCC may cause partial network congestion in a more complex wireless network, in which the decoding nodes are also the coding nodes or the decoding nodes are too close to the coding nodes. To avoid network congestion, some DCAR-type schemes using different metrics have been proposed. [PERSON] et al. proposed a free-ride-oriented routing metric (FORM), which can more accurately identify and utilize good coding opportunities [12]. To reduce the confusion of the coding opportunities, [PERSON] et al. revised the routing discovery procedures in the DCAR scheme by using the four steps of RREQ (route request), RREP (route reply), RCON (routing confirm), and RACK (routing acknowledge) [15]. To overcome network dynamics (e.g., high packet loss rate and node mobility), [PERSON] and [PERSON] proposed an NC-based evolutionary network formation to adapt to the topology change [29]. [PERSON] et al. proposed a load-balanced coding-aware routing metric that considered the load degree of each node, and the traffic of the scheme was evenly spread [30]. They also introduced a traffic-shaped CAR to increase the actual occurrences of network coding for wireless sensor networks [31].