Count on me: Reliable broadcast and efficient routing in DTNs through social skeletons

This paper challenges the belief that reliable broadcasting and efficient routing primitives are not possible when DTNs are involved. Firstly, we present COM, a reliable broadcasting mechanism for hybrid networks where nodes can rarely use long-range and costly communication links (e.g. 3G) to complete missing opportunistic links. COM is based on the Social Skeleton, a compact and connected subgraph, computed in an efficient and distributed way, that best represents the strongest social links among nodes. COM exploits the Social Skeleton to guarantee reachability of 100% of nodes with the lowest number of long communications. Then we empirically prove that the Social Skeleton can be used to build routing mechanisms upon it. We deliver SR (Skeleton Routing), which involves at most 3 copies per message, and yields delivery rates up to 5.5 times higher than state-of-the-art forwarding protocols.