A two-player coalition cooperative scheme for the bodyguard allocation problem

Abstract

This paper introduces the maximum uniform message distribution (MUMD) problem, which can be present in delay-tolerant communication networks, where the destination of the messages is not present in the network. This type of behavior arises in scenarios of natural disasters or social conflicts where a global communication network is not available. In these scenarios, the people inside the affected area might use their mobile devices to communicate in an opportunistic manner. During this communication, the devices can duplicate, exchange, and gather messages with the intention of afterward delivering them to the global communication network. A device successfully delivers all messages in its memory when it reaches the global communication network. We model the MUMD as a computational problem and analyze the effectiveness of the existing opportunistic routing algorithms to solve this problem. Furthermore, we design an algorithm for the MUMD and perform experimental simulations to analyze its performance. Our results show that the greater the number of copies of messages and the more uniformly distributed through the network they are, the higher the probability that deliveries will be successful.