Research Output
An adaptive multi-constraint partitioning algorithm for offloading in pervasive systems
  Offloading is a kind of mechanism utilized in pervasive systems to leverage the severity of resource constraints of mobile devices by migrating part of the classes of a pervasive service/application to some resource-rich nearby surrogates. A pervasive service application needs to be partitioned prior to offloading. Such partitioning algorithms play a critical role in a high-performance offloading system. This paper proposes an adaptive (k+1) partitioning algorithm that partitions a given application into 1 unoffloadable partition and k offloadable partitions. Furthermore, these partitions satisfy the multiple constraints imposed by either application users or mobile device resources. Underpinning the partitioning algorithm is a dynamic multi-cost graph that models the costs of an application in terms of its component classes (including CPU cost, memory cost and communication cost), and a Heavy-Edge and Light-Vertex Matching (HELVM) algorithm to coarsen the multi-cost graph. An offloading toolkit implementing the above algorithms has been developed, upon which the evaluations are carried out. The outcomes of the evaluation have indicated a higher level of performance of our algorithm in terms of its efficiency and cost-effectiveness.

  • Date:

    27 March 2006

  • Publication Status:


  • DOI:


  • Funders:

    Historic Funder (pre-Worktribe)


Ou, S., Yang, K., & Liotta, A. (2006). An adaptive multi-constraint partitioning algorithm for offloading in pervasive systems. In Fourth Annual IEEE International Conference on Pervasive Computing and Communications (PERCOM'06), (116-125).



graph theory, mobile computing, ubiquitous computing

Monthly Views:

Available Documents