Peer-to-peer overlay topology control for mobile ad hoc networks

The enormous popularity of peer-to-peer (P2P) applications and the increased use of mobile devices make running P2P applications on mobile ad hoc networks (MANETs) natural. However, simply applying existing P2P overlay techniques, which are designed for wired networks, to MANETs is undesirable clue to the differences between the two types of networks. In P2P systems, peers are often selfish rather than cooperative (which is expected of MANET nodes). In this paper, we study the construction of P2P overlays by selfish peers in the context of MANETs, and propose a computationally feasible game-theoretic heuristic algorithm. In our P2P-MANET creation game, peers seek to maintain as few neighbors as possible while minimizing their distances to all destinations, in an effort to reduce energy consumption and to improve response time. We find that Nash equilibria are difficult to find at best, and may not even exist in most cases. Our heuristic is fairly stable relative to the minimum cost algorithm, and when the degree-constraint is relaxed, it approximates the minimum cost. The lack of global knowledge of the overlay and underlying network at individual peers does not allow each peer to fully exploit such information for its own best interest, and actually may reduce the total cost network-wide. Crown Copyright (C) 2011 Published by Elsevier B.V. All rights reserved.