Utility-based Message Replication for Intermittently Connected Heterogeneous Networks

Communication networks (wired or wireless) have traditionally been assumed to be connected at least most of the time. However, emerging applications such as emergency response, special operations, smart environments, VANETs, etc. coupled with node heterogeneity and volatile links will likely change the typical conditions under which networks operate. In fact, in such scenarios, networks may be mostly disconnected. To cope with frequent, long-lived disconnections, opportunistic routing techniques have been proposed in which, at every hop, a node decides whether it should either forward and/or store-and-carry a message. As a result, a number of message replicas may be created and routed independently ("spraying"). Most opportunistic routing schemes to-date perform greedy replication handing over a copy of a message to the first nodes encountered. Yet, in a network with heterogeneous nodes, where some nodes may be much "better" relays than others, such greedy schemes may waste valuable message replicas (and thus energy, storage space, etc.) on "useless" relays. For this reason, we propose the idea of utility-based replication, where some fitness or utility function is maintained for all nodes in a distributed fashion, and a small budget of message replicas is allocated according to this utility only to the fittest nodes. We describe a number of variations using different utility functions, and show that an improvement of up to 5-6× in delay can be achieved over greedy algorithms.