Task Allocation Methods for Mobile Computing

Project Investigators

1. Bhaskar Krishnamachari - Dept. of Electrical Engineering, University of Southern California (Principal Investigator)
2. Fan Bai - General Motors Research (Co-Principal Investigator)

Student Participants

1. Yi-Hsuan Kao
2. Suvil Doera

As more embedded devices are connected, lots of resource on the network, in the form of cloud computing, become accessible. These devices, either suffering from stringent battery usage, like mobile devices, or limited processing power, like sensors, are not capable to run computation-intensive tasks locally. Taking advantage of the remote resource, more sophisticated applications, requiring heavy loads of data processing and computation, can be realized in timely fashion and acceptable performance. Thus, computation offloading — sending computation-intensive tasks to more resourceful severs, is becoming a potential approach to save resources on local devices and to shorten the processing time.

However, implementing offloading invokes extra communication cost due to the application and profiling data that must be exchanged with remote servers. The additional communication affects both energy consumption and latency. As an example shown in Fig. 1, offloading a task saves mobile battery and expedites the execution, but the system must pay extra prices in the form of increased data communication cost, task scheduling cost, etc. Hence, finding an optimal decision relies on globally identifying tasks that are worth offloading. That is, to carefully determine the optimal offloading decision that balances the system’s benefits and costs.

In general, we are concerned in this domain with a task assignment problem over multiple devices, subject to constraints. Furthermore, task dependency must be taken into account in formulations involving latency as a metric. We formulate a deterministic optimization problem, which we show that it is NP-hard, and propose a FPTAS algorithm (Fully Polynomial Time Approximation Scheme) to solve it. On ther other hand, we also propose an on-line learning algorithm that adapts to dynamic environment. Furthermore, we develope an Android platform that allows flexible implementations between mobile phone and remote server (see our demo of "YelpScraper"). Interesting future works includes testbed implementations and solving more sophisticated optimization problems.

1. Yi-Hsuan Kao, Bhaskar Krishnamachari, Moo-Ryong Ra, Fan Bai, “Hermes: Latency Optimal Task Assignment for Resource-constrained Mobile Computing“, International Conference on Computer Communication (INFOCOM), 2015.
2. Yi-Hsuan Kao, Bhaskar Krishnamachari, “Optimizing Mobile Computational Offloading with Delay Constraints“, IEEE Global Communications Conference (GLOBECOM), 2014.

1. Wireless updates open new avenues for autos (Michael Wayland)

1. Flexible Implementation of "YelpScraper" on Android Platform (Suvil Deora)