# A Constrained Coding-Aware Routing Scheme in Wireless Ad-Hoc Networks
## 3 Routing Implementation
### Routing Determination  
#### 3.3.1 Routing and Coding Discovery Processes  
In the opportunity-routing mechanisms, which CAR belongs to, the routing and coding discovery processes are on-demand. In addition, the processes are often launched via the RREQ (route request) messages by the source nodes and replied via to the RREP (route reply) messages by the destination nodes in practice. Some researchers have extended the routing discovery method by using an extra handshake (routing confirm and routing acknowledge) to ensure the encoding success ratio and enhance the decoded success ratio. It works well, but is not efficient in a large-scale network [15]. Moreover, the routing and coding discovery processes were separately operated in the CAR mechanisms, which would cause more energy consumption [38]. In this paper, we adopted the traditional method, which only uses RREQ and RREP messages. Through the routing request and reply processes, we can also find the available paths for the data flow and detect the potential coding opportunities of the paths simultaneously, termed the \"routing + coding\" discovery process. To be suitable for the \"routing + coding\" discovery process, we modify the structure of the RREP message, which is shown in Figure 4. S_add and D_add denote the addresses of the source and destination nodes, respectively. Rt_path records the routing path that has been passed. Furthermore, Rt_info denotes the route information. Rt_info consists of the flow IDs (Flow_id), the number of flows (Flow_nm), and the relay node IDs (Re_id). Moreover, it includes neighbor information (e.g., the addresses of the neighbor nodes (Neig_id) and the overheard flows (Oh_flow)) to help judge the state of routes and detect the coding opportunities according to Definitions 1 and 2. Rate_f denotes the flow rate. The coding flows and coding opportunities are marked as Code_f and Code_o, respectively. The end of the RREP message is Link_qua, which denotes the link quality (i.e., packet loss probability). When a new flow arrives at the wireless network, the source node of the new flow activates the \"routing + coding\" discovery process using the RREQ and RREP messages. Moreover, the flowchart of routing discovery is summarized as shown in Figure 5.  
Figure 4: The format of the RREP message header. Then, we simply describe the function of the RREQ and RREP messages as follows:  
* RREQ (routing request message) The RREQ message is a simplified version of the RREP message, which contains the source and destination addresses, the relay node IDs, the overheard flows, the link qualities, and other pertinent information. To start with the \"routing + coding\" discovery process, the source node broadcasts the RREQ messages at the moment a new flow appears. When the RREQ message arrives at a relay node, the node will calculate the link quality (Link_qua) and determine to which node it should be forwarded. If the relay node has received some RREQ messages that have the same destination, it will compare the link qualities of those messages. Then, the relay node will temporarily store one RREQ message that has the best link quality and drop the others. After the destination node has received the RREQ messages from different relay nodes in a fixed period, it can sort all candidate transmission routes according to the information (e.g., link quality and transmission counts) in the RREQ messages and then choose the best route. * RREP (routing reply message) The RREP message should be transmitted to the source node through a candidate route. When the RREP message arrives at a node, the node will verify the information in the RREP message (i.e., S_add and D_add). If the node is not the destination, it adds the route information of the intersected flows, the overheard flows, and one-hop neighbors into the RREP message. The relay nodes will forward the RREP message to the source node through unicasting. Moreover, the link quality between the relay node and its next hop is recorded in the RREP message. Figure 5: The flowchart of routing discovery.