A sociality-aware approach to computing backbone in mobile opportunistic networks

There are increasing interests on mobile opportunistic networks which have promising applications. Constructing a mobile backbone can effectively improve the packet delivery performance of a mobile opportunistic network by excluding poor relay nodes and reducing packet collisions. However, it is highly challenging to construct an effective mobile backbone because of the absence of the quantitative relationship between the network performance and the selection of backbone nodes, and expositive search space. We theoretically prove that the backbone construction problem is NP-Complete (NPC). By analyzing the real traces collected from around 100 users, we reveal that the nodes exhibit clear sociality. Motivated by this observation, we explicitly take such node sociality into account when computing the backbone for mobile opportunistic networks and we incrementally propose three algorithms for computing the mobile backbone. One of the algorithms is proved to achieve near-optimal solution under a specific model. Trace-driven simulations have been conducted and simulation results demonstrate that the sociality-aware algorithms can achieve low delivery delay and high delivery ratio.