IMPLEMENTATION OF MDP OVER MOBILE AD HOC NETWORKS

We consider the location service in a mobile ad-hoc network (MANET), where each and every node needs to maintain its information about location by 1) often updating its positional information within its neighboring region, which is called neighborhood update (NU), and 2) frequently updating its location information to specific distributed location server in the network, which is called location server update (LSU). The tradeoff between the operation costs in location updates and the performance losses of the target application due to location errors imposes a crucial question for nodes to decide the optimal strategy to update their location information, where the optimality is in the sense of reducing the overall costs. In this paper, we develop a stochastic sequential decision framework to analyze this problem. Under a Markovian mobility model, the location update decision problem is modeled as a Markov Decision Process (MDP). We first investigate the monotonicity properties of optimal NU and LSU operations with respect to location inaccuracies under a general cost setting. From the discovered separation property of the problem structure and the monotonicity properties of optimal actions, we find that 1) there always exists a simple optimal threshold-based update rule for LSU operations; 2) for NU operations, an optimal threshold-based update rule exists in a low-mobility scenario. In the case that no advance knowledge of the MDP model is available, we also introduce a practical model-free learning approach to find a near-optimal solution for the issue.