Optimizing Mobile Networks Connectivity and Routing Using Percolation Theory and Epidemic Algorithms

Abstract: Mobile Ad-hoc NETworks (MANETs) are complex systems presenting a phase transition phenomenon: an abrupt change in the behavior of the network around a critical value of a certain key parameter. The reliability and connectivity of MANETs depend on their size and on the efficiency of the routing protocol. In this paper we propose a new approach in MANETs modeling, combining percolation theory and epidemic algorithms. Using percolation theory we show the existence of a connectivity threshold (in a square lattice) needed to guarantee the communications in the network, in particular when the number of direct links are limited. Epidemic algorithms are used to provide a good propagation of information in the network wile minimizing the resources cost (energy, number of messages...).