# VANET Clustering Based Routing Protocol Suitable for Deserts
## 5 The Proposed Cluster-Based VANET Routing Protocol
### Routing between Clusters  
When the CH does not find the needed information in its internal storage, it requests the closest CHs for the destination information and waits for a routing response. If the waiting time exceeds the threshold \(t_{r}\) and the route response has not yet been received, re-request message (\(RREQ\)) is present. If the retransmission exceeds the maximum retransmission limit (\(r_{max}\)), the route search process is terminated. To reduce network congestion, not all of the neighboring CHs receiving \(RREQ\) will respond. Only those located on the route towards the destination having the ability to serve will participate in the routing process. As shown in Figure 8, only \(CH_{1}\) and \(CH_{2}\) participate in the routing process.  
Therefore, neighbor CHs, after having received the \(RREQ\) message, first determine if they are located on the route of the CH request; if not, the request is discarded. Otherwise, the procedure is as follows.  
1. A neighboring CH checks the request; if it is the first time received, then it continues the procedure; if not, then the request is discarded.
2. The neighboring CH checks whether the destination vehicle is in its cluster or not. If not, then apply Step 4.
3. The neighboring CH forwards a route request to the intended vehicle and waits for vehicle routing response \(RREP\); also, go to Step 5.
4. The CH adds its own \(msg\) to the (\(REEQ\)\(msg\)) message, and then forwards to the next hop neighbors' CH and waits for the route response.
5. If the waiting time exceeds \(t_{r}\), and it does not receive the route response, then retransmit the request and add one to request number; otherwise, go to Step 7.
6. If the number of retransmissions exceeds the limit \(r_{max}\), then end the route request process; alternatively, in accordance with the intended vehicle situation, directly apply Step 3 or Step 4.
7. If the CH receives more than one route response, then it chooses the vehicle with the fewest numbers of routing hops and the minimum distance to the destination and adds its own \(msg\) to the (\(REEP\)\(msg\)) message; then, it forwards this message to the previous hop CH vehicle at the same time, saving other routes as backups. If the routing request fails, probably due to the destination cluster, which is far away from the source cluster, and the routing communication request cannot be established through the VANET or through neighbor vehicles, the CH may establish a connection via satellite or mobile communication.  
Figure 8: Routing between clusters.  
In some situations and according to the CHE process, the CH may have no satellite or mobile equipment to communicate with the far away CHs; in this case, the CH searches for one of its cluster members, which is equipped with satellite or mobile communication, to forward the request to the neighboring CHs.
9. If still not be able to establish the connection and routing through satellite or mobile communication, then it sends the notification \(REER\) to the source vehicle, indicating routing failure. The flowchart of the procedure of routing between vehicles located in different clusters is shown in Figure 9.