An Optimal Application Partition Algorithm for Energy Efficient Computation Offloading

Abstract:

In order to alleviate the energy constraint in smartphones, computation offloading is regarded as an effective solution. In computation offloading, how to partition a given application is one of the key issues. On obtaining the best partition, due to the time complexity of partition algorithm, most researchers give up looking for a global optimal solution but to find local optimal. In this paper, a global optimal application partition algorithm is presented, the main strategy is scaling down the problem through merging the correlated nodes firstly, then using 0-1ILP to obtain the partition in order to make the mobile energy consumption achieve global optimal minimum, thus it has less time complexity than 0-1 ILP. Experimental results show that the proposed algorithm made the same global optimal partition results as 0-1 ILP, while it consumed less time and energy than 0-1 ILP.

• Periodical: Applied Mechanics and Materials (Volumes 687-691)
• Pages: 3516-3520
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.687-691.3516
• Online since: November 2014
• Authors: Wen Hao Fan*, Qian Deng, Bi Hua Tang, Fan Wu, Hong Guang Zhang
• Keywords: Application Partition, Computation Offloading, Energy Efficiency, Smartphone

References

[1] Kumar K, Liu J, Lu Y H, et al. A survey of computation offloading for mobile systems[J]. Mobile Networks and Applications, 2013, 18(1): 129-140.

DOI: 10.1007/s11036-012-0368-0

[2] Garey M R, Johnson D S. A Guide to the Theory of NP-Completeness[J]. San Francisco, (1979).

[3] Cuervo E, Balasubramanian A, Cho D, et al. MAUI: making smartphones last longer with code offload[C]/Proceedings of the 8th international conference on Mobile systems, applications, and services. ACM, 2010: 49-62.

DOI: 10.1145/1814433.1814441

[4] Gu X, Nahrstedt K, Messer A, et al. Adaptive offloading for pervasive computing[J]. Pervasive Computing, IEEE, 2004, 3(3): 66-73.

DOI: 10.1109/mprv.2004.1321031

[5] Ou S, Yang K, Zhang J. An effective offloading middleware for pervasive services on mobile devices[J]. Pervasive and Mobile Computing, 2007, 3(4): 362-385.

DOI: 10.1016/j.pmcj.2007.04.004

[6] Rhouma D, Romdhane L B. An efficient algorithm for community mining with overlap in social networks[J]. Expert Systems with Applications, 2014, 41(9): 4309-4321.

DOI: 10.1016/j.eswa.2014.01.002

[7] Watts D J, Strogatz S H. Collective dynamics of small-world, networks[J]. nature, 1998, 393(6684): 440-442.

DOI: 10.1038/30918

[8] Kwak J, Choi O, Chong S, et al. Dynamic Speed Scaling for Energy Minimization in Delay-Tolerant Smartphone Applications[R]. Technical Report, Jul. 2013. [Online]. Available: http: /netsys. kaist. ac. kr/publication/papers/Resources.

DOI: 10.1109/infocom.2014.6848173