An adaptive multi-constraint partitioning algorithm for offloading in pervasive systems

S. Ou, K. Yang, A. Liotta

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

74 Citations (Scopus)


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
Original languageEnglish
Title of host publicationProceedings of the 4th IEEE International Conference on Pervasive Computing and Communications (PerCom 2006) March 13-17, 2006, Pisa, Italy, March 13-17, 2006
Place of PublicationBrussels
PublisherIEEE Computer Society
ISBN (Print)0-7695-2518-0
Publication statusPublished - 2006


Dive into the research topics of 'An adaptive multi-constraint partitioning algorithm for offloading in pervasive systems'. Together they form a unique fingerprint.

Cite this