User-aware partitioning algorithm for mobile cloud computing based on maximum graph cuts

Partitioning and offloading of mobile applications have been demonstrated as a promising approach that not only enhances the performance but also extends the battery life of Smart Mobile Devices (SMDs) effectively. Researchers have proposed four factors that affect the partitioning decision: device (hardware), application (software), developer and user. However, most existing research efforts focus on the first three factors and pay little attention to the influence of user preferences on the partitioning decision. Among these factors, user preference usually affects user experience most. Moreover, previous work which took into account the other factors cannot generate adaptive partitioning results. In this work, we propose a user-aware partitioning algorithm to offer a personalized and precise partitioning plan for better user experience. Based on machine learning methods, we first propose a user profile model for characterizing the preferences of different phone users. In addition, a novel cost evaluation model (called CMET model) is proposed to evaluate the comprehensive offloading costs in terms of CPU & memory utilization, time cost and energy consumption. Finally, we propose a Max-Cuts partitioning algorithm based on Branch-and-Bound search to obtain the optimal partitioning plan. Experimental results demonstrate that for different types of phone users, our partitioning algorithm could effectively improve corresponding performances that they concern about, and achieve the most satisfactory user experience compared with state-of-the-art approaches.