Joint Computation and Communication Scheduling to Enable Rich Mobile Applications

Increasing interest in sensor networking and ubiquitous computing has created a trend towards embedding more and more intelligence into our surroundings. This enables thin wireless clients to support powerful applications by using processing resources that are available around them. One of the major challenges is how to schedule both the embedded computing and wireless communication resources to support a broad set of client nodes. This scheduling has to take into account the constraints on the wireless capacity, as well as the resource limitations on the processing elements. We have developed a set of fast algorithms to perform this scheduling, based on an LP-approachand a greedy solution. These algorithms are able to perform the scheduling with a performance close to the optimal exhaustive solution, but with an execution time that is reduced by three or more orders of magnitude (from hours to seconds).