An Optimal Application Partition Algorithm for Energy Efficient Computation Offloading

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.