On Optimality of Routing Policies in Delay-Tolerant Mobile Social Networks

In Delay Tolerant Networks (DTN), contemporaneous end-to-end paths are rarely available. Routing in such networks is therefore one of the challenging issues. When the DTN is made of humans, human mobility characterizes the forwarding opportunities. To leverage the diversity of the strengths of social ties, a number of utility-based routing policies have been proposed. In this paper we first address theoretically the optimization problem of the routing policy in such a social DTN, under a multi-community network model, and we prove that the optimal policies have a per-community threshold structure, thereby generalizing the existing works for homogeneous mobility DTN. We then provide analysis of this result on a numerical example, and discuss the comparison of such optimal policies with the online utility-based policies of the literature.