Game Theory and Genetic Algorithm Based Approach for Self Positioning of Autonomous Nodes
Janusz Kusyk, Elkin Urrea, Cem Safak Sahin and M. Ümit Uyar
Dynamically changing topology, decentralized architecture, and unknown deployment terrain present difficulties for effective node distribution in mobile ad hoc networks (MANETs). Additional MANET concerns include a lack of centralized authority, scarce power resources, and conflicting individual interests, all of which promote selfish behavior. With reduced computational and communicational overhead, game theory (GT) and genetic algorithms (GAs) provide promising tools to improve area coverage of the self-spreading nodes.We present our node spreading potential game (NSPG) for MANET nodes to position themselves in an unknown geographical terrain with obstacles. NSPG is a distributed and scalable game participated by autonomous nodes. The decisions about node movements are based on localized data while the best next location to move is selected by a GA. Our approach requires only a limited synchronization among the closest neighbors of a player and does not demand a priori knowledge of environment.We prove NSPG’s properties and necessary conditions for its convergence to a stable state. Simulation results show that NSPG performs well with respect to network coverage, uniform node distribution, convergence speed, and adaptability to adverse terrain conditions with arbitrarily placed obstacles.
Keywords: MANETs, topology control, node spreading, game theory, genetic algorithm