Carriers Selection for Content Dissemination in Social Opportunistic Networks

Content dissemination in social opportunistic networks has attracted great interests in the field. Most of the researches in literature focused on the data forwarding and routing mechanisms in such network scenarios. There were few studies on the assignment of content originators. This paper is concerned about how to identify a small subset of users as content carriers through which the content can be disseminated more efficiently. The problem is modeled as a dominating set problem in bipartite graph, in which a minimum number of carriers are selected to cover all the venues with required probability, by using available location affinity information. The NP-complete property of the problem is pointed out, along with an exact exponential exhaustive algorithm. Then three polynomial heuristic algorithms are presented to solve the venue coverage problem. Among them, the adaptive metric-based algorithm chooses carriers based on dynamically calculated metric values. Several user-centric and expected contribution based metrics are discussed and examined. The submodular algorithm selects carriers greedily based on the estimation of marginal coverage gain from each user. The reduced-union algorithm asks each venue to select a candidate set separately based on its own individual affinity information. Then the candidate union set is reduced gradually by reasonable greedy method. Synthetized data and real trace experiment results show that the submodular algorithm can be applied in scenarios where coverage threshold is low and small number of carriers is required. In most cases we can rely on metric-based algorithm to solve the carriers selection problem. Among all the metrics, total affinity and proportional contribution perform more valuable than other metrics. Meanwhile, the adaptive operation in metric-based algorithm plays more important role than the metrics in seeking the most qualified carriers. When complete affinity information is not available, the reduced-union algorithm could provide a feasible and acceptable solution to find the coverage set in a scalable way. It is also found that in practical network scenarios, it is realistic to have a small fraction of users act as content carriers, so that all the venues could be covered by them with required probability. These findings would be essentially helpful to content dissemination in affinity context-aware social opportunistic networks.