Optimal Monotone Forwarding Policies in Delay Tolerant Mobile Ad Hoc Networks

We study in this paper uid approximations for a class of monotone relay policies in delay tolerant ad-hoc networks. This class includes the epidemic routing and the two-hops routing protocols. We enhance the relay policies with a probabilistic forwarding feature where a message is forwarded to a relay with some probability p. We formulate an optimal control problem where a tradeo between delay and energy consumption is captured and optimized. We compute both the optimal static value of p as well as the optimal time de- pendent value of p. We show that the time dependent prob- lem is optimized by threshold type policies and we compute explicitly the value of the optimal threshold for some special cases of relay policies. forward a message to the destination is by epidemic routing in which any mobile that has the message keeps on relaying it to any other mobile that arrives within its transmission range and who does not have the message yet. This would minimize the delivery delay at a cost of inefficient use of network resources (in terms of memory used in the relaying mobiles and in terms of the energy used for ooding the

The need for more efficient use of network resources moti- vated the use of more economic forwarding such as the two hop routing protocols in which the source transmits copies of its message to all mobiles it encounters, but where the latter relay the message only if they come in contact with the destination. Furthermore, timers have been proposed to be associated with messages when stored at relay mobiles, so that after some threshold (possibly random) the message is discarded. The performance of the two hop forwarding protocol along with the e ect of the timers have been eval- uated in [1], the framework of which allows for optimization of the choice of the average timer duration. In this paper we analyze two alternative approaches for optimizing forwarding protocols. The rst approach consists of forwarding a message to another relay with some prob- ability p, where p can be optimized to meet some tradeo between delay and resource utilization. The second opti- mization approach we introduce is based on further allow- ing this probability p to vary in time. These two approaches are studied in this paper in conjunction with a wide class of monotone relaying schemes of which the epidemic routing and the two-hops routing are special cases (a precise de ni- tion of monotone relaying policies is postponed un

Free download research paper