  Computation offloading is indispensable for mobile edge computing (MEC). It
uses edge resources to enable intensive computations and save energy for
resource-constrained devices. Existing works generally impose strong
assumptions on radio channels and network queue sizes. However, practical MEC
systems are subject to various uncertainties rendering these assumptions
impractical. In this paper, we investigate the energy-efficient computation
offloading problem by relaxing those common assumptions and considering
intrinsic uncertainties in the network. Specifically, we minimize the
worst-case expected energy consumption of a local device when executing a
time-critical application modeled as a directed acyclic graph. We employ the
extreme value theory to bound the occurrence probability of uncertain events.
To solve the formulated problem, we develop an $\epsilon$-bounded approximation
algorithm based on column generation. The proposed algorithm can efficiently
identify a feasible solution that is less than (1+$\epsilon$) of the optimal
one. We implement the proposed scheme on an Android smartphone and conduct
extensive experiments using a real-world application. Experiment results
corroborate that it will lead to lower energy consumption for the client device
by considering the intrinsic uncertainties during computation offloading. The
proposed computation offloading scheme also significantly outperforms other
schemes in terms of energy saving.
