# An Energy-Efficient and Robust Multipath Routing Protocol for Cognitive Radio Ad Hoc Networks
## 4 Energy-Efficient and Robust Multipath Routing
### Route Discovery  
The process of route discovery allows the source to find the multiple routes between itself and the destination based on the routing metric. In the proposed ERMR, route discovery is a daunting twofold task that considers the residual node energy and the spectrum availability. In principle, it is based on the AOMDV routing algorithm. However, for adapting a cognitive radio environment, there are some modifications. When a node has data to transmit, it searches a valid routing path for the intended destination in its routing table. If no valid routing path is found, the node starts the route discovery process. In this process, a route request (RREQ) packet is broadcasted from the source to all its one-hop neighbors, forming multiple reverse paths at intermediate nodes. Every intermediate node that receives a RREQ packet checks if it is the intended destination; if not, it broadcasts the RREQ packet further. At the destination, a route reply (RREP) packet is unicasted towards the source along the reverse paths formed by RREQ forwarding. The multiple paths formed are loop-free and node-disjoint. That is, flood-based route discovery and regular route updates ensure loop freedom and path disjointedness. Figure 2 shows the basic structure of the RREQ packet. Because the route discovery is a hop-by-hop process, the regular update of RREQ fields is mandatory. Along with this, there is a routing table to be maintained at each participating node from source to destination. The routing table should hold the information represented in Figure 3 to ease the route discovery and subsequent selection. Figure 2: RREQ packet structure. S: Source; D: Destination; SN: Sequence Number; ACS: Available Channel Set; CAD: Channel Access Duration; CA: Channel Assigned; RE: Residual Energy; PC: Path Cost; HC: Hop Count; TO: Timeout. For every route discovery, the source broadcasts an RREQ packet via a common control channel (CCC). The RREQ packet exists only for the period defined by the TO field in Figure 2. When a neighboring node receives the RREQ packet, it first checks whether its battery energy exceeds the threshold value and whether there is any common vacant channel. Note that the communicating two nodes of transmitter and receiver not only should be within each other's transmission range but also must possess at least one common vacant licensed channel between them. If the two conditions are not met, the packet is dropped; otherwise, the intermediate node responds accordingly. In the response process, it first checks whether it is the destination being sought. If so, it replies with a unicast RREP packet; otherwise, it rebroadcasts the RREQ packet into its surroundings. Before it actually rebroadcasts the RREQ packet, the routing table is updated with information such as the last hop node, hop count for the reverse path, and channel assigned for that particular link. The channel assigned is the most stable channel available for that link. Likewise, the RREQ packet itself is also updated by appending node ID, available channel set, residual energy, most stable channel, path cost, and hop count (residual energy, channel stability, and hop count are increased by adding to their previous values). This process continues until the destination is reached, where the route decision and selection are made. To enable multiple paths between source and destination, the concept of sequence number is exploited, which facilitates unique identification for an RREQ packet. To ensure that the routes are disjointed, the redundant RREQ packets with the same sequence number as an RREQ packet that the node has already forwarded should be ignored. Figure 4 shows an example procedure of the route discovery process, where three disjoint routing paths can be found. As seen in the figure, the RREQ packet forwarding begins from source S and ends at destination D. Each of the nodes ensures that no RREQ packet is forwarded twice to avoid looping and maintain path disjointedness.