STORE: Simple Task Offloading and REassignment for Mobile Social Network

With the pervasive use of mobile devices and increasingly computational ability, more concrete and deeper collaborations among mobile users are becoming possible and needed. Appropriate task reassignment can effectively migrate tasks to more suitable devices for execution, improving processing efficiency and saving device energy. We investigate the task offloading in mobile social network, where mobile users reassign their tasks to others distributively when they are in communication ranges.However, most of the studies fail to consider load balancing requirement among mobile users. When tasks are unevenly distributed, the processing time as well as energy consumption will be extremely high on some specular devices, which will inevitably counterweight the benefits from incentive mechanism and task scheduling scheme. In this work, we propose STORE: a simple task offloading and reassignment scheme for mobile social network. The basic ideal is simple. We leverage the `ball and bins' theory for task assignment, where $d$ mobile users in contact range are investigated, and we select the least loaded one among them. It has been proved that, such simple case can effectively reduce the largest queueing length from $\theta(\frac{\log n}{\log\log n})$ to $\theta(\frac{\log\log n}{\log d})$. Inspired by this theoretical result, we develop a task reassignment policy where the tasks and device computation capabilities are diverse. Incorporating the weights into this problem, we make modifications on the number of $d$ candidates and reevaluate the queueing length. We find that, 2-choice is good enough for task balancing among users, even when energy level and computational capability are diverse. Simulation studies have shown that, STORE can effectively improve the balancing in typical network scenarios.