Using pre-deployment planning for maintaining network connectivity in MANET models

Abstract

Mobile Ad hoc Networks (MANET) allow communication with little or no network infrastructure. Assuming no infrastructure is available, user nodes are defined as service demanding and agent nodes as service providing, communicating via device-to-device connections when within range. This dissertation uses pre-planning, assignment and possible re-planning, in a stochastic environment, to improve network connectivity over the mission.

A mission's progression is discretized, where each time step can be modeled as a Steiner Tree Problem with Minimum Number of Steiner Points and Bounded Edge Length (STP-MSPBEL). To solve the static problem, a Reduction method was developed, derived from a Minimum Spanning Tree (MST) solution method yielding a set of connecting points, P. The Reduction method was verified and preformed as well as a mathematical model when comparing |P|. The Reduction method also performed as well as or (when possible) better than a solution method found in literature.

The dynamic deterministic environment problem considers successive static networks. A two stage solution approach is presented that first determines connecting points, Pt, at each time step using the Reduction per Time Interval (RTI) method and then assigns points in Pt to agent node tours with a genetic algorithm. In a majority of the runs this method performed as well as a mathematical model developed for validation and was better than a reactive approach.

The dynamic stochastic environment problem incorporated random deviations in user node movement. A MANET management method is presented that uses the pre-plan and assignment solution with the possibility of re-planning when the network has deviated beyond a given threshold. In comparison, using the MANET management method outperformed the reactive method in a majority of the runs.