CONNECT: Consociating opportunistic network neighbors for constructing a consistent and connected virtual backbone

Opportunistic networks have so far been seen mostly as delay tolerant in nature. As a result, real-time and soft real-time applications, which demand consistent and instant connectivity of the network, are usually considered intangible in opportunistic communication environments. In this paper we seek to reveal the inherent connected virtual backbone in an opportunistic network through the consociation of the neighbors in the network. This backbone can pave the way for designing an architecture for real-time social applications. The backbone may change in terms of time, location and crowd density. Experimenting on real world as well as synthetic human mobility traces and pause times, we first structure the pattern of human halt durations at popular places. Infusing this pattern, we then prove the existence of the intrinsic backbone in those networking environments, where people show regularity in their movements. Applying graph-theoretic concepts like Minimum Connected Dominating Set and Unit Node Weighted Steiner Tree we further optimize and ensure the robustness of the backbone. Simulation results show the effectiveness of our approach in exposing a newer dimension in the form of real time interaction prospects in opportunistic networks.