Threshold policy for route and schedule discovery initiation in mobile ad hoc networks

Achieving optimal transmission throughput in multi-hop wireless networks is a fundamental but hard problem. The situation is aggravated when nodes are mobile. Further, multi-rate systems make the analysis of throughput more complicated. In mobile scenario, a link may break or be created as nodes are moving within communication range. `Route and schedule discovery´ which is to find the optimal route and transmission schedule is an important issue. Route and schedule discovery entails some cost; so one would not like to initiate discovery too often. On the other hand, not discovering reasonably often entails the risk of being stuck with a suboptimal route and/or schedule, which hurts end-to-end throughput. The implementation of the routing decision problem in one dimensional mobile ad hoc network as Markov decision process problem is already discussed in. A heuristic based on threshold policy was presented in the same paper without giving a way to find the threshold. In this paper, we suggest a rule for setting the threshold, given the parameters of the system. We also point out that our results remain valid in a slightly different mobility model; this model is a first step towards an `open´ network in which existing relay nodes can leave and/or new relay nodes can join the network.