IEEE
Proof
YANG et al.: FRIEND IS TREASURE 5
TABL E I
I
LLUSTRATION FOR SOCIAL RELATIONSHIP RANKING LIST
Fig. 3. Considering task priority with social contacts.
V. “ i TOP-K”: SOCIAL-RELATIONSHIP-BASED341
TASK OFFLOADING ALGORITHM342
In tackling the aforementioned challenges, we propose a343
social-relationship-based task offloading algorithm. We lever-344
age the concept of “Top-K,” where the first K users in the345
friend list are selected for task allocation. The “Top-K” friends346
bear more regular contact pattern than others, which will lead347
to more stable task allocations. The only negative effect of348
“Top-K” scheme is that when there are no users in the contact349
window, the “Top-K” scheme will lead to unbalanced allocation350
or longer delay. In this paper, we use an adaptive scheme,351
where the number of “K” is adaptive and scalable. Thus, we352
call our scheme “iTop-K,” which means a customized and353
adaptive method. The “iTop-K” algorithm slightly modifies the354
original “d-choice” scheme, where the random “d” candidates355
are replaced by the selected “friends” in “Top-K” discipline.356
A. Finding the “Top-K” Social Contacts357
We leverage the trace data from MobiClique application at358
ACM Sigcomm conference 2009 [2]. The trace data recorded359
traces of Bluetooth encounters, opportunistic messaging, and360
social profiles of 76 users. We pick up the records of user i (1 ≤361
i ≤ 76) and sort them in descending order such as in Table I. As362
a result, we get the “Top-K” friend list for each user i.363
We build a relationship table according to the encountering364
frequency similar to Fig. 3. Note that, for user Jimmy, who365
has the highest priority level, the number of contacts between366
Jimmy and Tom is 105 during the data collection period. To367
decrease the task execution time, we need to assign the tasks to368
close friends or familiar people.369
In a mobile social network, the mobility dominates the370
task allocation opportunity. Different from conventional task371
allocation, the availability of each mobile user is considered in372
a mobile network as the availability differs from one another.373
Pure balancing among users would lead to unfairness among374
users. The reason for this claim is when the availability of375
different users differs, e.g., some mobile users are frequently376
contacted, whereas others are not. If we still allocate tasks to377
each user equally, the task allocation might be not efficient.378
Fig. 4. Waiting for “Top-K” users with scalability.
First, the tasks assigned to inactive mobile users would lead 379
to larger task execution time. In contrast, the active mobile 380
users could be more efficient in task allocation. For efficient 381
offloading consideration, the active mobile users could bear 382
more tasks and make the network more efficient. Specifically, 383
since the availability among users differs, we should not simply 384
apply the load balancing scheme to the mobile crowdsourcing 385
network directly. 386
Thus, in our scheme, we pursuit another form of balancing, 387
i.e., users are allocating tasks according to the availability of 388
mobile users, which is subjected to the mobility patterns. More- 389
over, there should be a balanced allocation among users with 390
unequal availability. Thus, allocating more tasks to frequently 391
contacted user could effectively improve the network efficiency 392
because tasks assigned to these users could be effectively 393
executed, and the task execution results could be returned to 394
the task sender in a relatively short time. In contrast, for the 395
infrequently contacted users, when more tasks are assigned, the 396
time delay could be very long. Thus, the balancing scheme 397
should be tailored for mobility features. Moreover, in the 398
social domain, the mobility patterns could be leveraged for 399
task execution. Because in social network discipline, intimate 400
users would have a close relationship and would like to execute 401
the tasks with higher priority. This feature has been widely 402
explored and exploited in many studies [24], [38]. We make 403
further exploration on our trace data for spatial and temporal 404
correlation features. Such features could further support the 405
close relationship between frequently contacted users. Thus, in 406
our scheme, we fully consider the mobile and social features in 407
the load balancing scheme, where tasks are allocated according 408
to the mobility patterns and social relationships. 409
B. Waiting for K Friends With Scalability 410
We consider the task execution time when “Top-K” friends 411
are identified. As shown in Fig. 4, if there is no user in the 412
“Top-K” list in one contact window, assigning tasks to “non- 413
Top-K” users will not ensure the high contact frequency. More- 414
over, the task execution priority will not be guaranteed, which 415
will be discussed in Section V-C. As shown in Fig. 4, at the 416
given slot, e.g., slot i, if in the next slot i + 1, there is no user in 417
the “Top-K” list. Thus, the selection scope K
i
would be scaled 418
to 2K
i
. 419
Further, if in the next slot i + 2, there is still no “Top- 420
K” friends, the selection scope K
i+2
would be 2K
i+1
= 4K
i
. 421
Once there are users in the scalable “Top-K” list, the selection 422