“Friend is Treasure”: Exploring and Exploiting Mobile Social Contacts for Efficient Task Offloading
Authors:
- 6 August 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Vehicular Technology
- Vol. 65 (7) , 5485-5496
Abstract
In this paper, we investigate the task offloading issue in mobile social networks. Although the “d-choice” paradigm in “ball and bin” theory had shown the power of random choice in load balancing with a random walk model, its performance could be fairly poor where real-trace data sets are concerned. According to our preliminary evaluation results with “MobiClique,” the “d-choice” scheme could not achieve well-balanced allocations in a real-trace data set. Nevertheless, it would bring fundamental challenges to task reassignment in the following aspects: First of all, some of the friendships are relatively stable, which would lead to a more imbalanced task assignment, even if the “d-choice” scheme is applied for balancing. Second, some users would meet quite infrequently, which could inevitably lead to intolerable time delay and unfair task allocations. In tackling these difficulties, we revisit the real data sets for exploring the contact property among users. We find that the frequently met users could be leveraged for efficient task execution due to higher task priority. To this end, we propose the “ $i$ Top-K” algorithm, leveraging the basic concept, i.e., “your friends are more powerful than you,” which encourages mobile users to assign tasks among intimate friends instead of pure random assignment. With careful selections of “Top-K” friends, we achieve balanced load and guaranteed performance at the same time. Experimental studies verify our scheme and show the effectiveness with three typical data trace sets, including “MobiClique.” In this typical networking scenario, ours outperforms the conventional random choice scheme up to 15 $\times$ and the social relationship assignment without priority method up to 9 $\times$. Moreover, the “Top-K” scheme could be adaptive, even when no intimate friends are available. By scaling the “K” factor to larger values, our scheme outperforms random assignment and could be inspiringly close to the optimal solution. In summary, ours could effectively explore the social relationship and leverage it for efficient task assignment, which would further encourage more mobile users to work together under the rule of social contacts.
Keywords
Funding Information
- National Natural Science Foundation of China (61232018, 61272487, 61232016, U1405254, 61173136)
- NSF (ECCS-1247944)
- CMMI (1436786)
- PAPD
- CICAEET
This publication has 25 references indexed in Scilit:
- Achieving Efficient Cloud Search Services: Multi-Keyword Ranked Search over Encrypted Cloud Data Supporting Parallel ComputingIEICE Transactions on Communications, 2015
- Construction of Tree Network with Limited Delivery Latency in Homogeneous Wireless Sensor NetworksWireless Personal Communications, 2014
- A high-resolution human contact network for infectious disease transmissionProceedings of the National Academy of Sciences, 2010
- Ear-phone2010
- Common Sense Community: Scaffolding Mobile Sensing and Analysis for Novice Users2010
- PEIR, the personal environmental impact report, as a platform for participatory sensing systems research2009
- A measure of betweenness centrality based on random walksSocial Networks, 2005
- Random Walks on Complex NetworksPhysical Review Letters, 2004
- Queues, Priorities, and Social ProcessSocial Psychology, 1978
- The Problem of the Random WalkNature, 1905