On-demand beaconing: Periodic and adaptive policies for effective routing in diverse mobile topologies

Locally aware routing protocols base their next-hop selection on information about their immediate neighborhood, gathered by means of a beaconing mechanism. In general, beacons may be proactively broadcasted from nodes to their neighbors (‘receiver-initiated’ beaconing) or may be solicited by the node carrying the routed message (‘on-demand’ beaconing). On-demand beaconing is of growing importance, mainly in more dynamic and sparse environments (e.g., delay tolerant networks), and is addressed in this paper.A generic analysis is provided for the case of periodically issued beacons, linking the beacon period to the trade-off between the quality of neighborhood perception (determining the routing effectiveness) and the required amount of signaling (related to energy expenditure at the nodes). The analysis leads to upper and lower bounds for the length of the beacon period, expressed in terms of mobility characteristics.The paper also investigates policies where the inter-beacon intervals vary adapting to the environment, an approach most beneficial when routing is based on metrics bearing some relevance to time. This is the case with the MAD routing protocol, which incorporates the notion of ‘retaining time’, an estimate of the time that the carrying node will retain the message. It is shown that linking the beacon intervals to the each time applicable retaining time leads to an effective and efficient beacon policy.The paper provides simulation-based evaluation results, validating the beacon period bounds and demonstrating that, for the case of MAD, adaptive beaconing is capable of providing even better performance.