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

Ou, S.; Yang, K.; Liotta, A.

Abstract

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.

Citation

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

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Fourth Annual IEEE International Conference on Pervasive Computing and Communications (PERCOM'06)
• Start Date: Mar 13, 2006
• End Date: Mar 17, 2006
• Online Publication Date: Mar 27, 2006
• Publication Date: 2006
• Deposit Date: Dec 3, 2019
• Publisher: Institute of Electrical and Electronics Engineers
• Volume: 2006
• Pages: 116-125
• Book Title: Fourth Annual IEEE International Conference on Pervasive Computing and Communications (PERCOM'06)
• ISBN: 0-7695-2518-0
• DOI: https://doi.org/10.1109/PERCOM.2006.7
• Keywords: graph theory, mobile computing, ubiquitous computing
• Public URL: http://researchrepository.napier.ac.uk/Output/1995932