Distribution of route requests using dominating-set neighbor elimination in an on-demand routing protocol

The use of dominating-set neighbor elimination as an integral part of the distribution of route requests using the ad hoc on-demand distance vector (AODV) protocol as an example of on-demand routing protocols is investigated. We use detailed simulations to show that simply applying dominant pruning (DP) to the distribution of route requests in AODV results in pruning too many route requests in the presence of mobility and cross-traffic. Accordingly, we introduce several heuristics to compensate the effects of DP and show that the resulting AODV with dominating set heuristics (AODV-DS) has comparable or better delivery ratio, network load, and packet latency than the conventional AODV. AODV-DS exhibits over 70% savings on RREQ traffic than conventional AODV, and in some situations, AODV-DS may have a lower control overhead using Hello packets than conventional AODV without Helios.