Coordination Minority Games in Delay Tolerant Networks

In this paper we introduce a novel framework for the distributed control of DTNs. The mechanism that we propose tackles a crucial aspect of such systems: in order to support message replication the devices acting as relays need to sacrifice part of their batteries. The aim is thus to provide a reward mechanism able to induce activation of relays in a coordinated fashion. The proposed scheme functions in non-cooperative fashion, and requires minimal message exchange to operate. In particular, relays choose among two strategies: either to participate to message relaying, or not to participate in order to save energy. The base for our mechanism design is to define the relays' utility function according to a minority game; in fact, relays compete to be in the population minority with respect to activation. By tuning the activation level, the system can hence control and optimize the DTN operating point in a distributed manner. To this respect, we characterize extensively the possible equilibria of this game. Finally, a stochastic learning algorithm is proposed which can provably drive the system to the equilibrium solution without requiring perfect state information at relay nodes. We provide extensive numerical results to validate the proposed scheme.