DISTRIBUTED COMPUTATION OFFLOADING METHOD BASED ON COMPUTATION-NETWORK COLLABORATION IN STOCHASTIC NETWORK

Abstract

A distributed computation offloading method based on computation-network collaboration in a stochastic network is provided. The distributed computation offloading method includes: building a device revenue maximization problem model and a MEC server revenue maximization problem model based on a local computing model and an edge cloud computing model; building composite sets of scenarios for dwell time and waiting latency based on a random movement of a user and burst computation demands; compensating for a game strategy by using a posteriori recourse action and building a game-based stochastic programming model between the device and the MEC server; transforming a multi-stage stochastic regularization problem for both the device and the MEC server into a DEP problem by constructing a scenario tree, and solving the DEP problem to obtain an optimal task strategy for the offloading from the MEC server and an optimal offering strategy of the MEC server to the device.

Claims

1. A distributed computation offloading method based on computation-network collaboration in a stochastic network, comprising: establishing a local computing model and an edge-cloud computing model based on differentiated service quality requirements, task processing costs, and the type of a device in a ultra-dense network UDN environment; establishing, based on the local computing model and the edge-cloud computing model, a device revenue maximization problem model by using a Lyapunov optimization theory and a minimum drift decreasing utility function at the device; establishing, based on the local computing model and the edge cloud computing model, a MEC server revenue maximization problem model by using a maximum value theory at a multi-access edge computing MEC server; respectively establishing, based on a random movement of a user and a burst computation requirement, a composite scenario set based on a dwell time period and a composite scenario set based on a waiting delay; performing compensation on a game strategy by performing a posteriori recourse action, and establishing a game-based stochastic programming model for the device and the MEC server; establishing a scenario tree to transform a multi-stage stochastic programming problem of the device and the MEC server to a DEP problem; solving an optimization problem of the device and an optimization problem of the MEC server based on a Lagrangian multiplier and a KKT condition to obtain an optimal task offloading strategy of the device to the MEC server and an optimal quotation strategy of the MEC server to the device; and in a case that both the optimal task offloading strategy of the device to the MEC server and the optimal quotation strategy of the MEC server to the device meet a Stackelberg equilibrium solution, offloading, by the device based on the optimal task offloading strategy, a task to the MEC server.

2. The distributed computation offloading method according to claim 1, wherein the establishing a device revenue maximization problem model comprises: $\underset{f_{i,L}\left(i\right),D_{i,k}\left(t\right)}{\max }{Y}_{b_i}\left(t\right)=V_i.Math.U_{b_i}\left[D_i\left(t\right)\right]+\underset{k\in \left\{L,M,S\right\}}{.Math.}{Q}_i\left(t\right).Math.D_{i,k}\left(t\right)-Q_i\left(t\right).Math.A_i\left(t\right),$ and constraints comprise: $T_{i,L}^{\mathrm{pt}}\left(t\right)\le {\tau }_i^d,$ $f_{i,L}^{\min }\le f_{i,L}\left(t\right)\le f_{i,L}^{\max },t\in T,$ $0\le D_i\left(t\right)\le Q_i\left(t\right),t\in T,\mathrm{and}$ $\stackrel{\_}{Q_i\left(t\right)}=\underset{T.fwdarw.+\infty }{\lim }\sup \frac{1}{T}\underset{t=0}{\overset{T-1}{.Math.}}E\left\{Q_i\left(t\right)\right\}\le +\infty ;$ where f.sub.i,L(t) represents a CPU clock frequency set of an i-th device, D.sub.i,k(t) represents an offloading task set in a time slot t, Y.sub.b.sub.i(t) represents a long-term revenue of the i-th device, V.sub.i represents a non-negative control parameter in the Lyapunov optimization theory, D.sub.i,k(t) represents an offloading task for an i-th mobile device, A.sub.i(t) represents a task arriving at the i-th mobile device in the time slot t, T represents a time slot index and T={0, 1, . . . }, U.sub.b.sub.i[D.sub.i(t)] represents a total revenue of the i-th device in the time slot t; k∈{L,M,S} represents a current task type, L represents a non-offloading task, M represents a task offloaded to a macro base station, S represents a task offloaded to a small base station; T.sub.i,L.sup.pt(t) represents a time period in which a local server processes an offloaded task, τ.sub.i.sup.d represents a maximum computation delay constraint of D.sub.i(t), f.sub.i,L.sup.min represents a minimum CPU clock frequency allocated for the i-th mobile device in the time slot t, f.sub.i,L(t) represents a CPU clock frequency allocated for the i-th mobile device in the time slot t, f.sub.i,L.sup.max represents a maximum CPU clock frequency allocated for the i-th mobile device in the time slot t, D.sub.i(t) represents a task processing decision at a beginning of the time slot t, Q.sub.i(t) represents a task queue backlog at the beginning of the time slot t, and (t) represents an average queue backlog.

3. The distributed computation offloading method according to claim 1, wherein in a case that a task is offloaded to a macro base station, the MEC server revenue maximization problem model is expressed as: $\text{?}{Y}_{s_M}\left(t\right)=u_M\left[p_M\left(t\right)\right]-\underset{\forall i}{.Math.}{e}_{i,M}\left[D_{i,M}\left(t\right),T_{i,M}^{\mathrm{wt}}\left(t\right)\right],$ $\text{?}\text{indicates text missing or illegible when filed}$ and constraints comprise:
p.sub.i,M(t)≥0,t∈T,
T.sub.i,M.sup.co(t)≤τ.sub.i.sup.d,t∈T, and
β.sub.l.sub.M.sup.min≤β.sub.i,l.sub.M(t)≤β.sub.l.sub.M.sup.max,t∈T; where p.sub.M(t) represents a pricing set of the macro base station in a time slot t, β.sub.i,l.sub.M represents a computing capacity set allocated to the macro base station, Y.sub.s.sub.M(t) represents a revenue of the macro base station, u.sub.M[p.sub.M(t)] represents a service utility of the macro base station, e.sub.i,M[D.sub.i,M(t),T.sub.i,M.sup.wt(t)] represents a task computing energy consumption of the macro base station, p.sub.i,M(t) represents a payment cost of an i-th device in the time slot t to the macro base station, T represents a time slot index and T={0, 1, . . . }, T.sub.i,M.sup.co(t) represents a total computation offloading time period of the macro base station in the time slot t, τ.sub.i.sup.d represents a maximum computation delay constraint of D.sub.i(t), β.sub.l.sub.M.sup.min represents a minimum frequency of each of CPU cores in the macro base station, β.sub.i,l.sub.M(t) represents a frequency of an i-th CPU core in the macro base station, and β.sub.l.sub.M.sup.max represents a maximum frequency of each of the CPU cores in the macro base station.

4. The distributed computation offloading method according to claim 1, wherein in a case that a task is offloaded to a small base station, the MEC server revenue maximization problem model is expressed as: $\underset{p_s\left(t\right),{\beta }_{{\mathrm{ij}}_s}}{\max }{Y}_{s_s}\left(t\right)=u_S\left[p_S\left(t\right)\right]-\underset{\forall i}{.Math.}{e}_{i,S}\left[D_{i,S}\left(t\right),T_{i,S}^{\mathrm{st}}\left(t\right),T_{i,S}^{\mathrm{wt}}\left(t\right)\right],$ and constraints comprise:
p.sub.i,S(t)≥0,t∈T,
T.sub.i,S.sup.co(t)≤τ.sub.i.sup.d,t∈T, and
β.sub.l.sub.S.sup.min≤β.sub.i,l.sub.S(t)≤β.sub.l.sub.S.sup.max,t∈T; where p.sub.S(t) represents a pricing set of the small base station in a time slot t, β.sub.i,l.sub.S represents a computing capacity set allocated to the small base station, Y.sub.s.sub.S(t) represents a revenue of the small base station, u.sub.S[p.sub.S(t)] represents a service utility of the small base station, e.sub.i,S[D.sub.i,S(t),T.sub.i,S.sup.st(t),T.sub.i,S.sup.wt(t)] represents a task computing energy consumption of the small base station, p.sub.i,S(t) represents a payment cost of an i-th device in the time slot t to the small base station, T represents a time slot index and T={0, 1, . . . }, T.sub.i,S.sup.co(t) represents a total computation offloading time period of the small base station in the time slot t, τ.sub.i.sup.d represents a maximum computation delay constraint of D.sub.i(t), β.sub.l.sub.S.sup.min represents a minimum frequency of each of CPU cores in the small base station, β.sub.i,l.sub.S(t) represents a frequency of an i-th CPU core in the small base station, and β.sub.l.sub.S.sup.max represents a maximum frequency of each of the CPU cores in the small base station.

5. The distributed computation offloading method according to claim 1, wherein the establishing a composite scenario set based on a dwell time period and a composite scenario set based on a waiting delay comprises: in a case that a possible dwell time period and a possible waiting time period of a mobile device in a small base station are known, obtaining, based on a Cartesian product, a composite scenario based on dwell time periods of all mobile devices and a composite scenario based on waiting delays of all the mobile devices, wherein a composite scenario set based on the dwell time periods of all the mobile devices is expressed as: ${\Omega }_S\left(t\right)={\Omega }_S^{\mathrm{st}}\left(t\right)\times {\Omega }_S^{\mathrm{wt}}\left(t\right),{\Omega }_S^{\mathrm{st}}\left(t\right)=\underset{i=1}{\overset{m}{.Math.}}{\Omega }_{i,S}^{\mathrm{st}}\left(t\right)={\Omega }_{1,S}^{\mathrm{st}}\left(t\right)\times .Math.\times {\Omega }_{m,S}^{\mathrm{st}}\left(t\right),\mathrm{and}{\Omega }_k^{\mathrm{wt}}\left(t\right)=\underset{i=1}{\overset{m}{.Math.}}{\Omega }_{i,k}^{\mathrm{wt}}\left(t\right)={\Omega }_{1,k}^{\mathrm{wt}}\left(t\right)\times .Math.\times {\Omega }_{m,k}^{\mathrm{wt}}\left(t\right);$ where m represents the number of the mobile devices, Ω.sub.i,S.sup.st(t) represent a composite scenario based on a dwell time period of an i-th mobile device, and Ω.sub.i,k.sup.wt(t) represents a composite scenario based on a waiting delay of the i-th mobile device.

6. The distributed computation offloading method according to claim 1, wherein compensation is performed on the game strategy by using the posteriori recourse action, that is, a two-stage optimal programming model is adopted, parameters are obtained based on the device revenue maximization problem model and the MEC server revenue maximization problem model in a first stage, compensation is performed on the parameters obtained in the first stage by using the posteriori recourse action in a second stage, and the device revenue maximization problem model after the compensation performed by using the posterior recourse action is expressed as: $\underset{f_{i,t}\left(t\right),D_{i,k}\left(t\right)}{\max }{Y}_{b_i}\left(t\right)=$ $V_i\{u_i\left[D_i\left(t\right)\right]-s_i\left[D_i\left(t\right)\right]-E_{{\Omega }_{i,S}^{\mathrm{st}}\left(t\right)}\left\{c_i\left(D_{i,t}\left(t\right),T_{i,S}^{\mathrm{st}}\left(t\right).Math.T_{i,S}^{\mathrm{st}}\left(t\right)\in {\Omega }_{i,S}^{\mathrm{st}}\left(t\right)\right)\right\}-$ $E_{{\Omega }_{i,S}^{\mathrm{st}}\left(t\right)}\left\{e_{i,L}\left(D_{i,t}\left(t\right),T_{i,S}^{\mathrm{st}}\left(t\right).Math.T_{i,S}^{\mathrm{st}}\left(t\right)\in {\Omega }_{i,S}^{\mathrm{st}}\left(t\right)\right)\right\}\}+$ $\underset{k\in \left\{L,M,S\right\}}{.Math.}{Q}_i\left(t\right)D_{i,k}\left(t\right)-Q_i\left(t\right)A_i\left(t\right),$ and constraints comprise: $T_{i,L}^{\mathrm{pt}}\left(t\right)\le {\tau }_i^d,f_{i,L}^{\min }\le f_{i,L}\left(t\right)\le f_{i,L}^{\max },t\in T,\theta \le D_i\left(t\right)\le Q_i\left(t\right),t\in T,\mathrm{and}\stackrel{\_}{Q_i\left(t\right)}=\underset{T.fwdarw.+\infty }{\lim }\sup \frac{1}{T}\underset{t=0}{\overset{T-1}{.Math.}}E\left\{Q_i\left(t\right)\right\}\le +\infty ;$ in a case that a task is offloaded to a small base station, the MEC server revenue maximization problem model after the compensation performed by using the posterior recourse action is expressed as: $\underset{p_s\left(t\right),{\beta }_{i,l_s}\left(t\right)}{\max }{Y}_{s_s}\left(t\right)=u_S\left[p_S\left(t\right)\right]-E_{{\Omega }_s\left(t\right)}\left[R\left({\beta }_{i,l_s}\left(t\right),{\Omega }_S\left(t\right)\right)\right],$ and constraints comprise:
p.sub.i,S(t)≥0,t∈T,
T.sub.i,S.sup.co(t)≤τ.sub.i.sup.d,t∈T, and
β.sub.l.sub.S.sup.min≤β.sub.i,l.sub.S(t)≤β.sub.l.sub.S.sup.max,t∈T; where f.sub.i,L(t) represents a CPU clock frequency set of an i-th device, D.sub.i,k(t) represents an offloading task set, Y.sub.b.sub.i(t) represents a long-term revenue of the i-th device, V.sub.i represents a non-negative control parameter in the Lyapunov optimization theory, u.sub.i[D.sub.i(t)] represents a utility of the i-th device, s.sub.i[D.sub.i(t)] represents a computation service cost of the i-th device, $E_{{\Omega }_{i,S}^{\mathrm{st}}\left(t\right)}\left\{c_i\left(D_{i,t}\left(t\right),T_{i,S}^{\mathrm{st}}\left(t\right).Math.T_{i,S}^{\mathrm{st}}\left(t\right)\in {\Omega }_{i,S}^{\mathrm{st}}\left(t\right)\right)\right\}$ represents an average communication cost in a composite scenario Ω.sub.i,S.sup.st(t), $E_{{\Omega }_{i,S}^{\mathrm{st}}\left(t\right)}\left\{e_{i,L}\left(D_{i,t}\left(t\right),T_{i,S}^{\mathrm{st}}\left(t\right).Math.T_{i,S}^{\mathrm{st}}\left(t\right)\in {\Omega }_{i,S}^{\mathrm{st}}\left(t\right)\right)\right\}$ represents an average energy consumption cost in the composite scenario Ω.sub.i,S.sup.st(t), D.sub.i,k(t) represents an offloading task for the i-th mobile device, A.sub.i(t) represents a task arriving at the i-th mobile device in a time slot t, T represents a time slot index and T={0, 1, . . . }, U.sub.b.sub.i[D.sub.i(t)] represents a total revenue of the i-th device in the time slot t, k∈{L,M,S} represents a current task offloading position, L indicates that a task is offloaded locally, M indicates that a task is offloaded to a macro base station, S indicates that a task is offloaded to a small base station, T.sub.i,L.sup.pt(t) represents a time period in which a local server processes an offloaded task, τ.sub.i.sup.d represents a maximum computation delay constraint of D.sub.i(t), f.sub.i,L.sup.min represents a minimum CPU clock frequency allocated for the i-th mobile device in the time slot t, f.sub.i,L(t) represents a CPU clock frequency allocated for the i-th mobile device in the time slot t, f.sub.i,L.sup.max represents a maximum CPU clock frequency allocated for the i-th mobile device in the time slot t, D.sub.i(t) represents a task processing decision at a beginning of the time slot t, Q.sub.i(t) represents a task queue backlog at the beginning of the time slot t, (t) represents an average queue backlog, Y.sub.s.sub.S(t) represents a revenue of a small base station, u.sub.S[p.sub.S(t)] represents a service utility of the small base station, E.sub.Ω.sub.S.sub.(t)[R(β.sub.i,l.sub.S(t),Ω.sub.S(t))] represents an average recourse in a composite scenario Ω.sub.i,S.sup.st(t), p.sub.i,M(t) represents a payment cost of the i-th device to the macro base station in the time slot t, T represents a time slot index and T={0, 1, . . . }, T.sub.i,M.sup.co(t) represents a total computation offloading time period of the macro base station in the time slot t, τ.sub.i.sup.d represents a maximum computation delay constraint of D.sub.i(t), β.sub.l.sub.M.sup.min represents a minimum frequency of each of CPU cores in the macro base station, β.sub.i,l.sub.M(t) represents a frequency of an i-th CPU core in the macro base station, and β.sub.l.sub.M.sup.max represents a maximum frequency of each of the CPU cores in the macro base station.

7. The distributed computation offloading method according to claim 6, wherein a recourse function R(β.sub.i,l.sub.S(t),Ω.sub.S(t)) is expressed as: $R\left({\nu }_{i,l_s}\left(t\right),{\Omega }_S\left(t\right)\right)=\underset{\forall i}{.Math.}{e}_{i,S}\left[D_{i,S}\left(t\right),T_{i,S}^{\mathrm{st}}\left({\omega }_S\left(t\right)\right),T_{i,S}^{\mathrm{wt}}\left({\omega }_S\left(t\right)\right)\right]$ where e.sub.i,S[D.sub.i,S(t),T.sub.i,S.sup.st(ω.sub.S(t)),T.sub.i,S.sup.wt(ω.sub.S(t))] represents an energy consumption cost of the small base station.

8. The distributed computation offloading method according to claim 6, wherein a task offloading process is divided into H sub-time slots, a distributed programming model with 2H stages is obtained, and the device revenue maximization problem model is expressed as: $\underset{f_{i,t}\left({\tau }_h\right),D_{i,k}\left({\tau }_h\right)}{\max }{Y}_{b_i}\left\{D_i\left({\tau }_1\right),.Math.,D_i\left({\tau }_H\right),f_{i,L}\left({\tau }_1\right),.Math.,f_{i,L}\left({\tau }_H\right)\right\}=$ $V_i\{u_i\left[D_i\left({\tau }_1\right)\right]-c_i\left[D_i\left({\tau }_1\right)\right]-e_{i,L}\left[D_i\left({\tau }_1\right)\right]-s_i\left[D_i\left({\tau }_1\right)\right]+$ $E_{{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_h\right).Math.{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_{k-1}\right)}\underset{h=2}{\overset{H}{.Math.}}\left\{u_i\left[D_i\left({\tau }_h\right)\right]-s_i\left[D_i\left({\tau }_h\right)\right]\right\}-$ $E_{{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_h\right).Math.{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_{h-1}\right)}\underset{h=2}{\overset{H}{.Math.}}{c}_i\left[D_i\left({\tau }_h\right),T_{i,S}^{\mathrm{st}}\left({\tau }_h\right)\right]-$ $E_{{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_h\right).Math.{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_{h-1}\right)}\underset{h=2}{\overset{H}{.Math.}}{e}_{i,L}\left[D_i\left({\tau }_h\right),T_{i,S}^{\mathrm{st}}\left({\tau }_h\right)\right]\}+$ $Q_i\left({\tau }_1\right)D_i\left({\tau }_1\right)+E_{{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_h\right).Math.{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_{h-1}\right)}\underset{h=2}{\overset{H}{.Math.}}{Q}_i\left({\tau }_h\right)D_i\left({\tau }_h\right)-$ $Q_i\left({\tau }_1\right)A_i\left({\tau }_1\right)-E_{{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_h\right).Math.{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_{h-1}\right)}\underset{h=2}{\overset{H}{.Math.}}{Q}_i\left({\tau }_h\right)A_i\left({\tau }_h\right),$ and constraints comprise: $f_{i,L}^{\min }\le f_{i,L}\left({\tau }_h\right)\le f_{i,L}^{\max },{\tau }_h\in H,\underset{h=1}{\overset{H}{.Math.}}{D}_i\left({\tau }_h\right)=D_i\left({\tau }_h\right),{\tau }_h\in H,\mathrm{and}0\le \underset{h=1}{\overset{H}{.Math.}}{D}_i\left({\tau }_h\right)\le Q_i\left({\tau }_h\right),{\tau }_h\in H;$ in the case that the task is offloaded to the small base station, the MEC server revenue maximization problem model is expressed as: $\underset{p_{i,s}\left({\tau }_h\right),{\beta }_{i,s}\left({\tau }_h\right)}{\max }{Y}_{s_s}\left\{p_{i,S}\left({\tau }_1\right),.Math.,p_{i,S}\left({\tau }_H\right),{\beta }_{i,S}\left({\tau }_1\right),.Math.,{\beta }_{i,S}\left({\tau }_H\right)\right\}=$ $u_S\left[p_S\left({\tau }_1\right)\right]-\underset{i=1}{\overset{m}{.Math.}}\left\{e_{i,S}\left[D_{i,S}\left({\tau }_1\right)\right]+p_{i,S}^f\left[D_{i,S}\left({\tau }_1\right)\right]\right\}+$ $E_{{\xi }_s\left({\tau }_h\right){.Math.}_{{\xi }_S\left({\tau }_{h-1}\right).Math.}}\underset{h=2}{\overset{H}{.Math.}}{H}_S\left[p_S\left({\tau }_h\right)\right]-$ $E_{{\xi }_S\left({\tau }_h\right){.Math.}_{{\xi }_s\left({\tau }_{h-1}\right).Math.}}\underset{i=1}{\overset{m}{.Math.}}\underset{h=2}{\overset{H}{.Math.}}{e}_{i,S}\left[D_{i,S}\left({\tau }_h\right),T_{i,S}^{\mathrm{st}}\left({\tau }_h\right),T_{i,S}^{\mathrm{wt}}\left({\tau }_h\right)\right],$ and constraints comprise: $p_{i,S}\left({\tau }_h\right)\ge 0,{\tau }_h\in H,E_{{\xi }_1}\left\{\underset{h=1}{\overset{H}{.Math.}}[T_{i,S}^{\mathrm{up}}\left({\tau }_h\right)+.Math.T_{i,S}^{\mathrm{wt}}\left({\tau }_h\right)+\underset{l_k\in L_k}{.Math.}\frac{D_i\left({\tau }_h\right){\gamma }_i}{{\beta }_{i,l_k}}\right\}\le {\tau }_i^d,\mathrm{and}{\beta }_{l_s}^{\min }\le {\beta }_{i,l_s}\left({\tau }_h\right)\le {\beta }_{l_s}^{\max },{\tau }_h\in H;$ where f.sub.i,L(τ.sub.h) represents a CPU clock frequency set of an i-th device in a sub-time slot τ.sub.h, D.sub.i,k(τ.sub.h) represents a offloading task set of an i-th mobile device in the sub-time slot τ.sub.h, u.sub.i[D.sub.i(τ.sub.1)] represents a utility of the i-th mobile device in a root node, c.sub.i[D.sub.i(τ.sub.1)] represents a communication cost of the i-th mobile device in the root node, e.sub.i,L[D.sub.i(τ.sub.1)] represents an energy consumption cost of the i-th mobile device in the root node, s.sub.i[D.sub.i(τ.sub.1)] represents a computation service cost of the i-th mobile device in the root node, T.sub.i,S.sup.st(τ.sub.h) represents a dwell time period of the i-th mobile device in the small base station in the sub-time slot τ.sub.h, D.sub.i(τ.sub.h) represents a processed task of the i-th mobile device in the sub-time slot τ.sub.h, f.sub.i,L(τ.sub.h) represent a local computation frequency of the i-th mobile device in the sub-time slot τ.sub.h; Q.sub.i(τ.sub.h) represents a task queue backlog in the sub-time slot τ.sub.h, ξ.sub.i,S.sup.st(τ.sub.h) represents a dwell time period in the sub-time slot τ.sub.h, and A.sub.i(τ.sub.1) represents a task arriving at the i-th mobile device in the root node.

9. The distributed computation offloading method according to claim 1, wherein the optimal strategy of the device is obtained based on the Lagrangian multiplier and the KKT condition by using the following equations: $f_{i,L}^{*}\left(t\right)=\left(\frac{{\rho }_i}{A_L.Math.\ln 2}-1\right)\frac{{\gamma }_i}{{\tau }_i^d},t\in T,\mathrm{and}{D}_{i,k}^{*}\left(t\right)=\frac{{\rho }_i}{A_k.Math.\ln 2}-1,k\in \left\{M,S\right\},t\in T;$ and the optimal quotation strategy of the MEC server to the device is obtained based on the Lagrangian multiplier and the KKT condition by using the following equation: $p_{i,k}^{*}\left(t\right)=2{\lambda }_k{k}_{l_k}\frac{D_{i,k}^{*}\left(t\right){\gamma }_i^2}{T_{i,k}^{\mathrm{pt}}}-\frac{D_{i,k}^{*}\left(t\right)}{{\Theta }_k};$ where, f.sub.i,L*(t) represents an optimal local computation frequency, ρ.sub.i represents a utility weight parameter of an i-th mobile user, A.sub.L represents a locally arriving task set, γ.sub.i represents a computation density in cycles/bit obtained by performing an offline measurement, τ.sub.i.sup.d represents a maximum computation delay constraint of D.sub.i(t), D.sub.i,k*(t) represents an optimal offloading strategy, p.sub.i,k*(t) represents an optimal quotation strategy of a base station, λ.sub.k represents a unit energy consumption, k.sub.l.sub.k represents an effective switching capacitance in the MEC server, D.sub.i,k*(t) represents an optimal offloading strategy, T.sub.i,k.sup.pt represents a processing time period for offloading a task, and ${\Theta }_k=\frac{\partial D_{i,k}^{*}\left(t\right)}{\partial p_{i,k}\left(t\right)},$ where k∈{M,S}, represents a first-order derivative of the optimal offloading strategy to a quotation.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0037] FIG. 1 shows a typical UDN environment supporting MEC;

[0038] FIG. 2 shows a flowchart of a distributed computing power and network collaboration method based on a ultra-dense network under multi-objective uncertainty according to the present disclosure;

[0039] FIG. 3 shows a task processing and time slot model according to the present disclosure;

[0040] FIG. 4 shows a scenario tree based on dwell time periods of an i-th mobile device according to the present disclosure;

[0041] FIG. 5 is a schematic diagram showing a recourse and compensation process according to the present disclosure;

[0042] FIG. 6 is a schematic diagram showing changes of a price with the number of iterations according to the present disclosure;

[0043] FIG. 7 is a schematic diagram showing changes of offloaded tasks with the number of iterations according to the present disclosure;

[0044] FIG. 8 is a schematic diagram showing changes of a calculation offloading performance with time (in which V is equal to 500 and represents a non-negative control parameter in a drift decreasing utility function) according to the present disclosure; and

[0045] FIG. 9 is a schematic diagram showing changes of a computation offloading performance with V according to the present disclosure.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0046] The technical solutions in the embodiments of the present disclosure will be clearly and completely described below in conjunction with the accompanying drawings in the embodiments of the present disclosure. It is apparent that the embodiments described are only a part of the embodiments of the present disclosure rather than all of the embodiments. Based on the embodiments of the present disclosure, all other embodiments obtained by those skilled in the art without creative efforts fall within the scope of protection of the present disclosure.

[0047] FIG. 2 shows a flowchart of a distributed computation offloading method based on computation-network collaboration in a stochastic network according to the present disclosure. The method includes the following steps:

[0048] establishing a local computing model and an edge-cloud computing model based on differentiated service quality requirements, task processing costs, and the type of a device in a UDN environment;

[0049] establishing, based on the local computing model and the edge-cloud computing model, a device revenue maximization problem model by using a Lyapunov optimization theory and a minimum drift decreasing utility function at the device;

[0050] establishing, based on the local computing model and the edge cloud computing model, a MEC server revenue maximization problem model by using a maximum value theory at an MEC server;

[0051] respectively establishing, based on a random movement of a user and a burst computation requirement, a composite scenario set based on a dwell time period and a composite scenario set based on a waiting delay;

[0052] performing compensation on a game strategy by using a posteriori recourse action, and establishing a game-based stochastic programming model for the device and the MEC server;

[0053] establishing a scenario tree to transform a multi-stage stochastic programming problem of the device and the MEC server to a DEP problem;

[0054] solving an optimization problem of the device and an optimization problem of the MEC server based on a Lagrangian multiplier and a KKT condition to obtain an optimal task offloading strategy of the device to the MEC server and an optimal quotation strategy of the MEC server to the device; and

[0055] in a case that both the optimal task offloading strategy of the device to the MEC server and the optimal quotation strategy of the MEC server to the device meet a Stackelberg equilibrium solution, offloading, by the device based on the optimal task offloading strategy, a task to the MEC server.

First Embodiment

[0056] In the embodiment, the process of establishing a local computing model and an edge-cloud computing model based on differentiated service quality requirements, task processing costs, and the type of a device in a UDN environment according to the present disclosure is described in detail.

[0057] In the embodiment, as shown in FIG. 1, a UDN system that supports MEC and operates in discrete time is considered. It is assumed that T={0, 1, . . . }, and τ∈T, where T represents a time slot index and τ represents a time length of each of time slots, the system includes a macro base station (MBS) and n small base stations (SBS), N=(1, . . . , n) and N represents a set of n SBSs, M represents the MBS, S∈N and S represents an S-th SBS, M=(1, . . . , m) and M represents m mobile devices (MDs), each of base stations is arranged with an MEC server where the MEC server has computing power and may provide computing power to MDs in a coverage region of the base station, each of the MDs may process tasks locally or offload a task to a MEC server of a base station, and each of the MDs may be connected to a MBS and a nearby SBS by using a dual connection in a 5G network or a CoMP technology.

[0058] It is assumed that MD.sub.i represents an i-th mobile device, a task requested to be processed by MD.sub.i may be represented by a quaternion Λ.sub.i(t)=(t),D.sub.i(t),τ.sub.i.sup.d,γ.sub.i, where Q.sub.i(t) represents a task queue backlog at a beginning of a time slot t and D.sub.i(t) represents a task processing decision at the beginning of the time slot t, τ.sub.i.sup.d represents a maximum computation delay constraint of D.sub.i(t), and γ.sub.i represents a computation density in cycles/bit that may be obtained by performing an offline measurements.

[0059] It is assumed that A.sub.i(t) represents a task arriving at MD.sub.i (i∈M) and A(t)={A.sub.1(t), . . . , A.sub.m(t)} represents a set of all MDs in the time slot t. Since the tasks arriving in one time slot are limited, 0≤A.sub.i(t)≤A.sub.i.sup.max, t∈T, where A.sub.i.sup.max represents a maximum number of arriving tasks. It is assumed that task arrival rates of all the MDs meet an independent and identical distribution. An update equation for the queue backlog of MD i may be expressed as:

(t+1=[(t)−D.sub.i(t)].sup.++A.sub.i(t),i∈M,i∈T

where [x].sup.+=max(x,0),

[00018]$D_i\left(t\right)=D_{i,L}\left(t\right)+\underset{k\in \left\{M,S\right\}}{.Math.}{D}_{i,k}\left(t\right),D_{i,L}\left(t\right)$

represents a task backlog processed locally, D.sub.i,M(t) represents a task backlog processed by the MBS, and D.sub.i,S(t) represent a task backlog processed by a SBS.

[0060] At a beginning of each of time slots, it is required for each of mobile devices to determine a task offloading strategy to determine the number of non-offloading tasks D.sub.i,L(t) and the number of offloading tasks D.sub.i,k(t), where k∈{M,S}. As shown in FIG. 3, an offloading process includes the following three stages.

[0061] In a first stage, each of the MDs uploads a computation task D.sub.i,k(t) to a BS through a wireless channel, where T.sub.i,k.sup.up(t) represents a task upload delay.

[0062] In a second stage, the task uploaded by each of the MDs waits in a server for a time period which is referred to as a waiting delay T.sub.i,k.sup.wt(t).

[0063] In a third stage, the offloaded task is to be processed by the server, and T.sub.i,k.sup.pt(t) represents a processing time period.

[0064] It is required to process the offloaded task in a constraint time length τ.sub.i.sup.d. In a case that the offloaded task is not processed in the constraint time length τ.sub.i.sup.d, it is determined that the task is failed to be processed.

[0065] Since a capacity of a battery of a mobile device is limited, in order to save energy in limited time, a MD may process a task at a CPU clock frequency determined based on a dynamic voltage and frequency scaling (DVFS) technology. It is assumed that

[00019]$D_{i,L}\left(t\right)=\underset{T_{i,L}^{\mathrm{pt}}\left(t\right)}{\int }\frac{f_{i,L}\left(t\right)}{{\gamma }_i}\mathrm{dt}$

represents a relationship between processed tasks and local computing resources, where T.sub.i,L.sup.pt(t)≤τ.sub.i.sup.d and represents a local execution time period, f.sub.i,L(t)(f.sub.i,L.sup.min≤f.sub.i,L(t)≤f.sub.i,L.sup.max) represents a CPU clock frequency (cycle/s) allocated in a time slot, f.sub.i,L.sup.min represents a minimum CPU clock frequency of MD i, and f.sub.i,L.sup.max represents a maximum CPU clock frequency of MD i.

[0066] For each of the MDs, it is assumed in the present disclosure that the energy of the device is mainly consumed by the operation of the CPU. Generally,

[00020]$E_{i,L}^{\mathrm{exe}}\left(t\right)=k_i\underset{T_{i,L}^{\mathrm{pt}}\left(t\right)}{\int }{\left(f_{i,L}\left(t\right)\right)}^2\mathrm{dt}$

represents energy consumption due to operation of a CPU is, where k.sub.i represents an effective energy factor, is related to a chip structure of the device and may be obtained by performing an offline measurements.

[0067] In the present disclosure, it is assumed that: (1) in a case that a MD is located both in a coverage region of a MBS and in coverage regions of SBSs, the MD may simultaneously communicate with the MBS and a nearby SBS in each of time slots, that is, the MD may offload a task to both the MBS and the nearby SBS; (2) due to random movements of the MDs and burst computation requirements, a dwell time periods T.sub.i,S.sup.st(t), i∈M of a MD in a SBS and waiting delays T.sub.i,k.sup.wt(t), k∈{M,S} of the MD in the different BSs are random and meet an independent identical distribution; and (3) in a case that a MD leaves a wireless coverage region of a SBS while the MD uploading a task to the SBS (where the uploaded task is represented by D.sub.i,S.sup.tr(t)), it is required to firstly upload remaining tasks (D.sub.i,S(t)−D.sub.i,S.sup.tr(t)) to the MBS, and then the MBS forwards the remaining tasks to another SBS via a wired optical network.

[0068] For a delay-sensitive application, an uploading delay of a task should be less than a constraint time length, that is, T.sub.i,k.sup.up(t)<τ.sub.i.sup.d. In a case that uploading delay of the task is not less than the constraint time length, it is certain that the task is to be executed unsuccessfully. Since calculation results are usually much smaller than inputted tasks of most applications, time cost for downloading calculation results from base stations is ignored in the present disclosure. Once a MD decides to offload a task to the MBS and a nearby SBS, the task uploading delay and communication energy cost are calculated as follows.

[0069] (1) Offloading a Task to a MEC Server of the MBS

[0070] For each of the MDs, it is required to transmit input bits of a task to the MBS through a wireless channel. It should be noted that an interference environment of the UDN becomes complex as the number of the users increases. Therefore, for a offloading decision, power interferences between devices should be considered. According to a Shannon-Hartley formula, an upload data rate is obtained by using the following equation:

[00021]$r_{i,M}\left(t\right)={\omega }_M{\log }_2\left(1+\frac{P_i\left(t\right)g_{i,M}\left(t\right)}{{\sigma }^2\left(t\right)+\underset{x\in M\backslash x=i}{.Math.}{P}_x{g}_{x,M}\left(t\right).Math.1\left(D_{x,M}\left(t\right)\right)}\right)$

[0071] where ω.sub.M represents a radio bandwidth, g.sub.i,M(t) represents a channel gain of the MBS, σ.sup.2(t) represents an average background noise power, P.sub.i(t) represents a communication power of a MD i in a time slot t, and 1(⋅) represents an indicator function.

[0072] Therefore, for the MBS, the task uploading delay is obtained by using the following equation:

[00022]$T_{i,M}^{\mathrm{up}}\left(t\right)=\frac{D_{i,M}\left(t\right)}{r_{i,M}\left(t\right)},i\in M,$

and

[0073] the communication energy consumption is obtained by using the following equation:

[00023]$E_{i,M}^{\mathrm{up}}\left(t\right)=P_i\left(t\right)\frac{D_{i,M}\left(t\right)}{r_{i,M}\left(t\right)},i\in M.$

[0074] (2) Offloading a Ask to a MEC Server of a SBS

[0075] In a case that a MD i offloads a task D.sub.i,S(t) to a MEC server of a SBS, an uploading data rate is obtained by using the following equation:

[00024]$r_{i,S}\left(t\right)={\omega }_S{\log }_2\left(1+\frac{P_i\left(t\right)g_{i,S}\left(t\right)}{{\sigma }^2\left(t\right)+\underset{x\in M\backslash x=i}{.Math.}{P}_x{g}_{x,S}\left(t\right).Math.1\left(D_{x,S}\left(t\right)\right)}\right)$

[0076] where ω.sub.S represents a wireless bandwidth, and g.sub.i,S(t) represents a channel gain of the SBS.

[0077] Generally, a wireless coverage region of a SBS is smaller than a wireless coverage region of a MBS. Based on the assumptions mentioned above, in a case that a MD leaves a wireless coverage region of a SBS while the MD uploading a task, the remaining tasks are firstly uploaded to the MBS and then are forwarded to another SBS. Therefore, an uploading delay of a SBS is obtained by using the following equation:

[00025]$T_{i,S}^{\mathrm{up}}\left(t\right)=\{\begin{array}{c}{T}_{i,S}^{\mathrm{st}}\left(t\right)+\widehat{T_{i,M}^{\mathrm{up}}}+T_{i,M}^f,\mathrm{if}{T}_{i,S}^{\mathrm{st}}\left(t\right)<\frac{D_{i,S}\left(t\right)}{r_{i,S}\left(t\right)}\\ \frac{D_{i,S}\left(t\right)}{r_{i,S}\left(t\right)},\mathrm{if}{T}_{i,S}^{\mathrm{st}}\left(t\right)\ge \frac{D_{i,S}\left(t\right)}{r_{i,S}\left(t\right)}\end{array}$

[0078] where T.sub.i,S.sup.st(t) represents a dwell time period of the MD i in the SBS,

[00026]$\widehat{T_{i,M}^{\mathrm{up}}}=\frac{D_{i,S}\left(t\right)-T_{i,S}^{\mathrm{st}}\left(t\right)r_{i,S}\left(t\right)}{r_{i,M}\left(t\right)}$

represents an uploading delay for the remaining tasks,

[00027]$T_{i,M}^f=\frac{D_{i,S}\left(t\right)-T_{i,S}^{\mathrm{st}}\left(t\right)r_{i,S}\left(t\right)}{c}.$

represents a forwarding time period of the remaining tasks, and c represents a data rate of an optical link.

[0079] Therefore, the communication energy consumption of the MD i uploading D.sub.i,S(t) to the SBS is obtained by using the following equation:

[00028]$E_{i,S}^{\mathrm{up}}\left(t\right)=\{\begin{array}{c}{P}_i\left(t\right)\left(T_{i,S}^{\mathrm{st}}\left(t\right)+T_{i,M}^{\mathrm{up}}\right),\mathrm{if}{T}_{i,S}^{\mathrm{st}}\left(t\right)<\frac{D_{i,S}\left(t\right)}{r_{i,S}\left(t\right)}\\ P_i\left(t\right)\frac{D_{i,S}\left(t\right)}{r_{i,S}\left(t\right)},\mathrm{if}{T}_{i,S}^{\mathrm{st}}\left(t\right)\ge \frac{D_{i,S}\left(t\right)}{r_{i,S}\left(t\right)}\end{array}.$

[0080] A total energy consumption of the MD i in the time slot t is obtained by using the following equation:

[00029]$E_{i,L}\left(t\right)=E_{i,L}^{\mathrm{exe}}\left(t\right)+\underset{k\in \left\{M,S\right\}}{.Math.}{E}_{i,k}^{\mathrm{up}}\left(t\right).$

[0081] A total computation offloading time period of the MBS/SBS is obtained by using the following equation:

T.sub.i,k.sup.co(t)=T.sub.i,k.sup.up(t)=T.sub.i,k.sup.wt(t)=T.sub.i,k.sup.pt(t),k∈{M,S}.

[0082] To ensure that offloaded tasks are processed timely, a total computation offloading time period T.sub.i,k.sup.co(t)(t) (including an uploading time period, a waiting delay and a processing time period) does not exceed a constrained time period in each of time slots (that is, T.sub.i,k.sup.co(t)≤τ.sub.i.sup.d).

[0083] It is assumed that the MEC server is arranged with a CPU having L.sub.k cores, a core set of a CPU is represented as L.sub.k=(1, . . . , L.sub.k), k∈{M,S}. A processing energy consumption of the MEC server for processing a task D.sub.i,k(t) is obtained by using the following equation:

[00030]$E_{i,k}\left(t\right)=\underset{l_k\in L_k}{.Math.}{k_{l_k}\left({\beta }_{i,L_k}\left(t\right)\right)}^2{T}_{i,k}^{\mathrm{pt}}\left(t\right),k\in \left\{M,S\right\}.$

where k.sub.l.sub.k represents an effective switching capacitance in the MEC server, β.sub.i,l.sub.k(t) (β.sub.i.sub.k.sup.min≤β.sub.i,l.sub.k(t)≤β.sub.i.sub.k.sup.max) represents a CPU clock frequency of a l.sub.k-th CPU core in the MEC server, β.sub.i.sub.k.sup.min represents a minimum CPU clock frequency of each of CPU cores, and β.sub.i.sub.k.sup.max represents a maximum CPU clock frequency of each of the CPU cores.

Second Embodiment

[0084] In the embodiment, resource cost to be consumed for processing a task is calculated based on the local computing model and the edge-cloud computing model established in the first embodiment.

[0085] Based on the local computing model and the edge-cloud computing model established in the first embodiment, it can be seen that the computation offload delay strongly relies on the communication delay, the waiting delay and the processing delay of the task. In order to ensure that an offloaded task is processed in the constrained time period τ.sub.i.sup.d, computation factors (including a computation waiting time period T.sub.i,k.sup.wt(t), a computation power f.sub.i,L and β.sub.i,l.sub.k(t)) and network factors (including a dwell time period T.sub.i,S.sup.st(t) and a communication time period T.sub.i,k.sup.up(t)) are required to be considered.

[0086] In order to evaluate a task processing performance, a task processing utility function and a task processing cost function are defined in the present disclosure. For each of the MDs, in order to evaluate a revenue for processing a task in each of the time slots, a logarithmic utility function is adopted in the present disclosure, which is widely used in the field of wireless communications and mobile computations. An utility of the MD i is obtained by using the following equation:

[00031]$u_i\left[D_i\left(t\right)\right]=\underset{k\in \left\{L,M,S\right\}}{.Math.}{\rho }_i\log \left[1+D\underset{i,\hat{k}}{}\left(t\right)\right],t\in T$

[0087] where ρ.sub.i is a utility weight parameter of MD i.

[0088] In a case that a transmission task of the MBS are expressed as:

[00032]$D_{i,M}^{\mathrm{tr}}\left(t\right)=\{\begin{array}{c}{D}_{i,M}\left(t\right)+D_{i,S}\left(t\right)-T_{i,S}^{\mathrm{st}}{r}_{i,S}\left(t\right),\mathrm{if}{T}_{i,S}^{\mathrm{st}}\left(t\right)<\frac{D_{i,S}\left(t\right)}{r_{i,S}\left(t\right)}\\ D_{i,M}\left(t\right),\mathrm{if}{T}_{i,S}^{\mathrm{st}}\left(t\right)\ge \frac{D_{i,S}\left(t\right)}{r_{i,S}\left(t\right)}\end{array},$

[0089] and a transmission task of a SBS is expressed as:

[00033]$D_{i,S}^{\mathrm{tr}}\left(t\right)=\{\begin{array}{c}{T}_{i,S}^{\mathrm{st}}{r}_{i,S}\left(t\right),\mathrm{if}{T}_{i,S}^{\mathrm{st}}\left(t\right)<\frac{D_{i,S}\left(t\right)}{r_{i,S}\left(t\right)}\\ D_{i,S}\left(t\right),\mathrm{if}{T}_{i,S}^{\mathrm{st}}\left(t\right)\ge \frac{D_{i,S}\left(t\right)}{r_{i,S}\left(t\right)}\end{array}$

[0090] communication cost of MD i is obtained by using the following equation:

c.sub.i[D.sub.i(t)]=θ.sub.iD.sub.i,M.sup.tr(t)+η.sub.iD.sub.i,S.sup.tr(t),t∈T

where θ.sub.i represents communication cost for a unit of bit of MD i in the MBS, and η.sub.i represents communication cost for a unit of bit of MD i in the SBS.

[0091] To simplify the analysis, it is assumed in the embodiment that a unit energy consumption cost is represented as

[00034]$\lambda \underset{\hat{k}}{}\ge 0,\hat{k}\in \left\{L,M,S\right\}.$

Therefore, the energy consumption cost is obtained by using the following equation:

[00035]$e\underset{i,\hat{k}}{}\left[D_i\left(t\right)\right]=\lambda \underset{\hat{k}}{}E\underset{i,\hat{k}}{}\left(t\right),t\in T.$

[0092] In order to improve the user's experience for the computation offload service, a cloud server provider has to consume costs. Apparently, offload services are not free, and an edge-cloud server usually requires compensations to share resources. It is assumed that p.sub.i,k(t), k∈{M,S} ($/bit) represents a unit payment cost of MD i for BS k in a time slot t, the compute service cost of MD i is obtained by using the following equation:

[00036]$s_i\left[D_i\left(t\right)\right]=\underset{k\in \left\{M,S\right\}}{.Math.}{p}_{i,k}\left(t\right)D_{i,k}\left(t\right),i\in M,$

[0093] and the service utility of the is obtained by using the following equation:

[00037]$u_k\left[p_k\left(t\right)\right]=\underset{\forall i\in M}{.Math.}{p}_{i,k}\left(t\right)D_{i,k}\left(t\right).Math.,k\in \left\{M,S\right\},$

[0094] where p.sub.k(t)[p.sub.1,k(t), . . . , p.sub.m,k(t)] represents a price strategy set of the MBS or a price strategy set of the SBS.

Third Embodiment

[0095] Based on the local computing model and the edge-cloud computing model established in the first embodiment and the resource cost to be consumed for offloading tasks obtained in the second embodiment, a device revenue maximization problem model and a MEC server revenue maximization problem model are established based on a Lyapunov optimization theory and a minimum drift decreasing utility function in the embodiment.

[0096] In the present disclosure, the task offloading and computation resource allocation problem is described as a deterministic optimization problem, and it is assumed that the dwell time period T.sub.i,S.sup.st(t) S∈N and the computation waiting time period T.sub.i,k.sup.wt(t), k∈{M,S} are known in advance.

[0097] In the present disclosure, it is assumed that mobile devices are always rational, and seek an optimal offloading decision to maximize the long-term revenue. For an optimal decision of each of the MDs/buyers, an offloaded task, communication cost, energy cost and payment cost should be considered. Based on the above analysis, an objective function of a MD/buyer i in a time slot t is expressed as:

U.sub.b.sub.i[D.sub.i(t)]=u.sub.i[D.sub.i(t)]−c.sub.i[D.sub.i(t),T.sub.i,S.sup.st(t)]−e.sub.i,L[D.sub.i(t),T.sub.i,S.sup.st(t)]−s.sub.i[D.sub.i(t)].

[0098] To ensure the computation performance in the long term evolution, for the MD/buyer i, the device revenue maximization problem model is expressed as:

[00038]$\begin{array}{c}P1-\mathrm{buyer}:\\ \underset{f_{i,L}\left(t\right),D_{i,k}\left(t\right)}{\max }\stackrel{\_}{U_{b_i}}=\underset{T.fwdarw.+\infty }{\lim }\frac{1}{T}E\underset{t=0}{\overset{T-1}{.Math.}}\left\{U_{b_i}\left[D_i\left(t\right)\right]\right\}\end{array}$$s.t.T_{i,L}^{\mathrm{pi}}\left(t\right)\le {\tau }_i^d,$$f_{i,L}^{\min }\le f_{i,L}\left(t\right)\le f_{i,L}^{\max },t\in T,$$0\le D_i\left(t\right)\le Q_i\left(t\right),t\in T,\mathrm{and}$$\stackrel{\_}{Q_i\left(t\right)}=\underset{T.fwdarw.+\infty }{\lim }\sup \frac{1}{T}\underset{t=0}{\overset{T-1}{.Math.}}E\left\{Q_i\left(t\right)\right\}\le +\infty .$

[0099] A Lyapunov function for a computation task queue of the MD i is represented as:

[00039]$L_i\left(Q_i\left(t\right)\right)=\frac{1}{2}{\left\{Q_i\left(t\right)\right\}}^2$

where L.sub.i((t))≥0. Thus, a conditional Lyapunov drift is expressed as:

Δ((t))=E{L.sub.i()−L.sub.i((t))|(t)}.

[0100] Based on an online optimal decision, an upper bound of a drift decreasing utility function is minimized, which is defined as: Δ((t))−V.sub.iE{U.sub.i[D.sub.i(t)]|(t)}, where V.sub.i≥0 is a non-negative control parameter. To obtain the upper bound of the drift decreasing utility function, based on control parameters V.sub.i≥0 and A.sub.i(t)∈[0, A.sub.i.sup.max] provided according to any possible decision, the following inequality may be obtained:

[00040]$\Delta \left(Q_i\left(t\right)\right)-V_{i}E\left\{U_i\left[D_i\left(t\right)\right].Math.Q_i\left(t\right)\right\}$$\le B_i+Q_i\left(t\right)A_i\left(t\right)-E\left\{Q_i\left(t\right)D_i\left(t\right).Math.Q_i\left(t\right)\right\}-V_{i}E\left\{U_i\left[D_i\left(t\right)\right].Math.Q_i\left(t\right)\right\}$$\mathrm{where}{B}_i=\frac{1}{2}\left\{{\left({D_i\left(t\right)}^{\max }\right)}^2+{\left({A_i\left(t\right)}^{\max }\right)}^2\right\}.$

[0101] The upper bound of the drift decreasing utility function may be obtained by minimizing the right-hand side (RHS) of the above inequality. Thus, the optimization problem P1-buyer may be transformed to:

[00041]$\begin{array}{c}P2-\mathrm{buyer}:\\ \underset{f_{i,L}\left(t\right),D_{i,k}\left(t\right)}{\max }{Y}_{b_i}\left(t\right)=V_i.Math.U_{b_i}\left[D_i\left(t\right)\right]+\underset{k\in \left\{L,M,S\right\}}{.Math.}{Q}_i\left(t\right).Math.D_{i,k}\left(t\right)-Q_i\left(t\right).Math.A_i\left(t\right)\end{array}$$s.t.T_{i,L}^{pt}\left(t\right)\le {\tau }_i^d,$$f_{i,L}^{\min }\le f_{i,L}\left(t\right)\le f_{i,L}^{\max },t\in T,$$0\le D_i\left(t\right)\le Q_i\left(t\right),t\in T,$$\stackrel{\_}{Q_i\left(t\right)}=\underset{T.fwdarw.+\infty }{\lim }\sup \frac{1}{T}\underset{t=0}{\overset{T-1}{.Math.}}E\left\{Q_i\left(t\right)\right\}\le +\infty .$

[0102] For each of BSs (base stations)/sellers, based on

[00042]$e\underset{i,\hat{k}}{}\left[D_i\left(t\right)\right]=\lambda \underset{\hat{k}}{}E\underset{i,\hat{k}}{}\left(t\right),t\in T,$$s_i\left[D_i\left(t\right)\right]=\underset{k\in \left\{M,S\right\}}{.Math.}{p}_{i,k}\left(t\right)D_{i,k}\left(t\right),i\in M\mathrm{and}$$u_k\left[p_k\left(t\right)\right]=\underset{\forall i\in M}{.Math.}{p}_{i,k}\left(t\right)D_{i,k}\left(t\right),k\in \left\{M,S\right\},$

revenues U.sub.s.sub.kk∈{M,S} of the MBS/SBS are respectively defined as:

[00043]$P1-\mathrm{seller}\left(\mathrm{MBS}\right):\underset{p_{i,M}\left(t\right),{\beta }_{i,t_M}\left(t\right)}{\max }\stackrel{\_}{U_{s_M}}=\underset{T.fwdarw.+\infty }{\lim }\frac{1}{T}E\left[\underset{t=0}{\overset{T-1}{.Math.}}\{u_M\left[p_M\left(t\right)\right]-\underset{\forall i}{.Math.}{e}_{i,M}\left[D_{i,M}\left(t\right),T_{i,M}^{wt}\left(t\right)\right]\right]$$\begin{array}{cc}s.t.& p_{i,M}\left(t\right)\ge 0,t\in T,\end{array}$$T_{i,M}^{co}\left(t\right)\le {\tau }_i^d,t\in T,$${\beta }_{l_M}^{\min }\le {\beta }_{i,l_M}\left(t\right)\le {\beta }_{l_M}^{\max },t\in T,$$P1-\mathrm{seller}\left(\mathrm{SBS}\right):\underset{p_{i,S}\left(t\right),{\beta }_{i,l_S}\left(t\right)}{\max }\stackrel{\_}{U_{s_S}}=\underset{T.fwdarw.+\infty }{\lim }\frac{1}{T}E\underset{t=0}{\overset{T-1}{.Math.}}\{u_S\left[p_S\left(t\right)\right]-\underset{\forall i}{.Math.}{e}_{i,S}\left[D_{i,S}\left(t\right),T_{i,S}^{st}\left(t\right),T_{i,S}^{wt}\left(t\right)\right]$$s.t.p_{i,S}\left(t\right)\ge 0,t\in T,$$T_{i,S}^{co}\left(t\right)\le {\tau }_i^d,t\in T,$${\beta }_{l_s}^{\min }\le {\beta }_{i,l_s}\left(t\right)\le {\beta }_{l_s}^{\max },t\in T$

[0103] The revenues of the MBS and the SBS are related to a pricing set p.sub.i,k(t), an allocated computational power β.sub.i,l.sub.k(k) and a computation waiting delay T.sub.i,k.sup.wt(t) in the time slot t. In order to ensure that the offloaded tasks are processed within the constrained time period, it is required for the SBS S to consider the waiting time period T.sub.i,S.sup.st(t) of MD i. Furthermore, based on a maximum theory, the problem P1-seller may be transformed to the following problem:

[00044]$P2-\mathrm{seller}\left(\mathrm{MBS}\right):\underset{p_M\left(t\right),{\beta }_{i,l_M}}{\max }{Y}_{s_M}\left(t\right)=u_M\left[p_M\left(t\right)\right]-\underset{\forall i}{.Math.}{e}_{i,M}\left[D_{i,M}\left(t\right),T_{i,M}^{\mathrm{wt}}\left(t\right)\right]$$\begin{array}{cc}s.t.& p_{i,M}\left(t\right)\ge 0,t\in T,\end{array}$$T_{i,M}^{co}\left(t\right)\le {\tau }_i^d,t\in T,$${\beta }_{l_M}^{\min }\le {\beta }_{i,l_M}\left(t\right)\le {\beta }_{l_M}^{\max },t\in T$$P2-\mathrm{seller}\left(\mathrm{SBS}\right):\underset{p_S\left(t\right),{\beta }_{i,l_S}}{\max }{Y}_{s_S}\left(t\right)=u_S\left[p_S\left(t\right)\right]-\underset{\forall i}{.Math.}{e}_{i,S}\left[D_{i,S}\left(t\right),T_{i,S}^{st}\left(t\right),T_{i,S}^{wt}\left(t\right)\right]$$\begin{array}{cc}s.t.& p_{i,S}\left(t\right)\ge 0,t\in T,\end{array}$$T_{i,S}^{co}\left(t\right)\le {\tau }_i^d,t\in T,$${\beta }_{l_s}^{\min }\le {\beta }_{i,l_s}\left(t\right)\le {\beta }_{l_s}^{\max },t\in T.$

[0104] Based on P2-seller, each of the sellers periodically announces a latest market prices p.sub.k(t) based on the user's requirement D.sub.i,k(t) and a current network state (such as the calculated waiting time period T.sub.i,k.sup.wt(t) and the calculated dwell time period T.sub.i,S.sup.st(t)) in the time slot t. With the changes of the requirement and the network state, the seller dynamically adjusts the pricing strategy until market equilibrium is reached, and the allocated computing power β.sub.i,l.sub.k(t) is adaptively adjusted.

Fourth Embodiment

[0105] In the third embodiment, it is assumed in the present disclosure that the dwell time period T.sub.i,S.sup.st(t) and the waiting delay T.sub.i,k.sup.wt(t),∈{M,S} are known. However, due to the random movements of the users and burst computation requirements, the dwell time period and the waiting delay are uncertain at a beginning of each of time slots. Decisions may be made by using average historical values of the dwell time period and the waiting delay or predicting the dwell time period and the waiting delay. However, in a real time-varying environment, it is difficult to perform high-precision predictions. Imprecise results affect computation performance and offloading success rate. For example, in a case that a predicted dwell time period and a predicted waiting delay are respectively greater than an actual dwell time period and an actual waiting delay, the computation offloading cost increases, or even the offloading process fails. Therefore, a two-stage stochastic programming method is performed according to the present disclosure to perform posteriori remedy to compensate for previous inaccurate predictions.

[0106] In order to deal with an uncertain dwell time period T.sub.i,S.sup.st(t) and an uncertain waiting delay T.sub.i,k.sup.wt(t), a scenario set having uncertain parameters is considered in the present disclosure. Ω.sub.i,S.sup.st(t) represents a scenario set based on possible dwell time periods of the MD i in a SBS, and Ω.sub.i,k.sup.wt(t) represents a scenario set based on possible waiting delays of the MD i in a BS k, k∈{M, S}. Based on a Cartesian product, a composite scenario Ω.sub.S.sup.st(t) based on dwell time periods of all MDs and a composite scenario Ω.sub.k.sup.wt(t) based on waiting delays of all MDs may be respectively expressed as:

[00045]${\Omega }_S^{\mathrm{st}}\left(t\right)=\underset{i=1}{\overset{m}{.Math.}}{\Omega }_{i,S}^{\mathrm{st}}\left(t\right)={\Omega }_{1,S}^{\mathrm{st}}\left(t\right)\times .Math.\times {\Omega }_{m,S}^{\mathrm{st}}\left(t\right),\mathrm{and}$${\Omega }_k^{\mathrm{wt}}\left(t\right)=\underset{i=1}{\overset{m}{.Math.}}{\Omega }_{i,k}^{\mathrm{wt}}\left(t\right)={\Omega }_{1,k}^{\mathrm{wt}}\left(t\right)\times .Math.\times {\Omega }_{m,k}^{\mathrm{wt}}\left(t\right).$

[0107] It is noted that based on U.sub.b.sub.i[D.sub.i(t)]=u.sub.i[D.sub.i(t)]−c.sub.i[D.sub.i(t),T.sub.i,S.sup.st(t)]−e.sub.i,L[D.sub.i(t),T.sub.i,S.sup.st(t)]−s.sub.i[D.sub.i(t)], a revenue of a MD is related to a scenario Ω.sub.i,S.sup.st(t) based on a dwell time period. Therefore, the revenue of the MBS is related to the composite scenario Ω.sub.M.sup.wt(t) and the revenues of the BSs are related to the composite scenario Ω.sub.S(Q)=Ω.sub.S.sup.st(t)×Ω.sub.S.sup.wt(t), where Ω.sub.S(t) represents a composite scenario based on composite time (that is, dwell time period and waiting delays in the SBSs). Hereafter, a game-based distributed two-stage stochastic programming model is analyzed in the present disclosure.

[0108] To simplify the analysis, analysis is performed based on the SBSs in the present disclosure. The analysis based on MBS may be easily derived from the analysis based on the SBSs.

[0109] In an uncertain and time-varying network environment, actual values of stochastic variables are obtained after performing processes, that is, the dwell time period T.sub.i,S.sup.st(t) and the waiting delay T.sub.i,k.sup.wt(t) are obtained after performing the game and uploading offloaded tasks to the cloud. However, after observing actual situations, compensation may be performed on the game strategy by performing a posterior recourse action. Based on the stochastic programming theory, a decision set includes the following two groups according to the present disclosure.

[0110] For a decision group in a first stage (game stage), it is required to adopt a strategy for offloading a task D.sub.i(t) and a strategy for announcing a price p.sub.i,S(t) before obtaining T.sub.i,S.sup.st(t) and T.sub.i,S.sup.wt(t) through the game. This stage is referred to as a first stage or a game stage.

[0111] For a decision group in a second stage (recourse stage), allocation of computing power β.sub.i,l.sub.S(t) may be performed after observing the realizations of T.sub.i,S.sup.st(t) and T.sub.i,S.sup.wt(t), which is referred to as a second stage decision. This stage is referred to as a second stage or a recourse stage.

[0112] T.sub.i,S.sup.st(t)∈Ω.sub.i,S.sup.st(t) represents a realization of a dwell time period in a time slot t, and ω.sub.S(t)=(T.sub.1,S.sup.st, . . . , T.sub.m,S.sup.st(t), Ω.sub.1,S.sup.qt, . . . , Ω.sub.m,S.sup.qt) represents a composite realization of the dwell time period in the time slot t. p[T.sub.i,S.sup.st(t)]∈[0,1] and p[ω.sub.S(t)]∈[0,1] represent probabilities. Based on the stochastic programming theory, an optimal problem of P2-buyer may be expressed as a two-stage stochastic programming problem:

[00046]$P3-\mathrm{buyer}\left(\mathrm{two}-\mathrm{stage}\right):\begin{array}{c}\underset{f_{i,L}\left(t\right),D_{i,k}\left(t\right)}{\max }{Y}_{b_i}\left(t\right)=V_i\{u_i\left[D_i\left(t\right)\right]-s_i\left[D_i\left(t\right)\right]\\ -E_{{\Omega }_{i,S}^{\mathrm{st}}\left(t\right)}\left\{c_i\left(D_{i,t}\left(t\right),T_{i,S}^{st}\left(t\right).Math.T_{i,S}^{st}\left(t\right)\in {\Omega }_{i,S}^{\mathrm{st}}\left(t\right)\right)\right\}\\ -E_{{\Omega }_{i,S}^{\mathrm{st}}\left(t\right)}\left\{e_{i,L}\left(D_{i,t}\left(t\right),T_{i,S}^{st}\left(t\right).Math.T_{i,S}^{st}\left(t\right)\in {\Omega }_{i,S}^{st}\left(t\right)\right)\right\}\}\\ +\underset{k\in \left\{L,M,S\right\}}{.Math.}{Q}_i\left(t\right)D_{i,k}\left(t\right)-Q_i\left(t\right)A_i\left(t\right)\end{array}$$s.t.T_{i,L}^{pt}\left(t\right)\le {\tau }_i^d,$$f_{i,L}^{\min }\le f_{i,L}\left(t\right)\le f_{i,L}^{\max },t\in T,$$0\le D_i\left(t\right)\le Q_i\left(t\right),t\in T,\mathrm{and}$$\stackrel{\_}{Q_i\left(t\right)}=\underset{T.fwdarw.+\infty }{\lim }\sup \frac{1}{T}\underset{t=0}{\overset{T-1}{.Math.}}E\left\{Q_i\left(t\right)\right\}\le +\infty .$

[0113] Similarly, an optimal problem of P2-seller(SBS) may be expressed as:

[00047]$\mathrm{P3}-\mathrm{seller}\left(\mathrm{two}-\mathrm{stage}\right):\underset{p_S\left(t\right),{\beta }_{i,l_S}\left(t\right)}{\max }{Y}_{s_S}\left(t\right)=u_S\left[p_S\left(t\right)\right]-E_{{\Omega }_S\left(t\right)}\left[R\left({\beta }_{i,l_S}\left(t\right),{\Omega }_S\left(t\right)\right)\right]$$s.t.p_{i,S}\left(t\right)\ge 0,t\in T,$$T_{i,S}^{co}\left(t\right)\le {\tau }_i^d,t\in T,\mathrm{and}$${\beta }_{l_s}^{\min }\le {\beta }_{i,l_s}\left(t\right)\le {\beta }_{l_s}^{\max },t\in T,$$\mathrm{where}R\left({\beta }_{i,l_s}\left(t\right),{\Omega }_S\left(t\right)\right)=\underset{\forall i}{.Math.}{e}_{i,S}\left[D_{i,S}\left(t\right),T_{i,S}^{\mathrm{st}}\left({\omega }_S\left(t\right)\right),T_{i,S}^{\mathrm{wt}}\left({\omega }_S\left(t\right)\right)\right],$$\mathrm{and}R\left({\beta }_{i,l_S}\left(t\right),{\Omega }_S\left(t\right)\right)$

represents a recourse function.

[0114] Expressions of an optimal problem for a macro base station may be derived by those skilled in the art based on the expressions for the small base stations, and not repeated in the embodiment.

Fifth Embodiment

[0115] As shown in FIG. 1, each of the MDs may move randomly between two or more SBSs. However, it is only required to perform a decision once in each of the time slots by using the game strategy based on two-stage stochastic programming, thus a sub-optimal solution may be obtained. Therefore, statistical features of T.sub.i,S.sup.st(t) and T.sub.i,S.sup.wt(t) may be accurately captured, and the offloading strategy, the pricing strategy and the computation power allocation strategy may be accurately defined, and the game strategy may be further developed by using multi-stage stochastic programming. In the multi-stage stochastic programming, a computation offloading process is divided into H sub-slices (H□{τ.sub.1, τ.sub.2, . . . , τ.sub.H}). In a sub-slice τ.sub.h, multi-stage stochastic programming is performed, and then the task offloading D.sub.i(τ.sub.h), τ.sub.h∈H, the price p.sub.i,S(τ.sub.H) and the computation power allocation β.sub.i,l.sub.S(t) are optimal. ξ.sub.i,S.sup.st(τ.sub.h) represents a possible dwell time period in the sub-slice τ.sub.h, and ξ.sub.S(τ.sub.h) represents possible composite time in the sub-slice τ.sub.h. The dwell time periods in all composite scenarios in all sub-time slots are expressed as:

[00048]${\xi }_{i,S}^{st}=\underset{h=1}{\stackrel{H}{.Math.}}{\xi }_{i,S}^{st}\left({\tau }_h\right)={\xi }_{i,S}^{st}\left({\tau }_1\right)\times .Math.\times {\xi }_{i,S}^{st}\left({\tau }_H\right),$

and
the composite time in all composite scenarios in all sub-time slots is expressed as:

[00049]${\xi }_S=\underset{h=1}{\overset{H}{.Math.}}{\xi }_S\left({\tau }_h\right)={\xi }_S\left({\tau }_1\right)\times .Math.\times {\xi }_S\left({\tau }_H\right).$

[0116] After dividing a task time period t of an offloading task into H sub-time slots, a distributed stochastic programming model having 2 H stages is obtained as follows.

[0117] A task offloading optimization problem of a MD/buyer i may be transformed to the following optimization problem of P3-buyer(multi-stage):

[00050]$P3-\mathrm{buyer}\left(\mathrm{multi}-\mathrm{stage}\right):$$\begin{array}{c}\underset{f_{i,L}\left({\tau }_h\right),D_{i,k}\left({\tau }_h\right)}{\max }{Y}_{b_i}\left\{D_i\left({\tau }_1\right),.Math.,D_i\left({\tau }_H\right),f_{i,L}\left({\tau }_1\right),.Math.,f_{i,L}\left({\tau }_H\right)\right\}\\ =V_i\{u_i\left[D_i\left({\tau }_1\right)\right]-c_i\left[D_i\left({\tau }_1\right)\right]-e_{i,L}\left[D_i\left({\tau }_1\right)\right]-s_i\left[D_i\left({\tau }_1\right)\right]\\ +E_{{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_h\right)|{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_{h-1}\right)}\underset{h=2}{\overset{H}{.Math.}}\left\{u_i\left[D_i\left({\tau }_h\right)\right]-s_i\left[D_i\left({\tau }_h\right)\right]\right\}\\ -E_{{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_h\right)|{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_{h-1}\right)}\underset{h=2}{\overset{H}{.Math.}}{c}_i\left[D_i\left({\tau }_h\right),T_{i,S}^{st}\left({\tau }_h\right)\right]\\ -E_{{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_h\right).Math.{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_{h-1}\right)}\underset{h=2}{\overset{H}{.Math.}}{e}_{i,L}\left[D_i\left({\tau }_h\right),T_{i,S}^{\mathrm{st}}\left({\tau }_h\right)\right]\}\\ +Q_i\left({\tau }_1\right)D_i\left({\tau }_1\right)+E_{{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_h\right).Math.{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_{h-1}\right)}\underset{h=2}{\overset{H}{.Math.}}{Q}_i\left({\tau }_h\right)D_i\left({\tau }_h\right)\\ -Q_i\left({\tau }_1\right)A_i\left({\tau }_1\right)-E_{{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_h\right)|{\xi }_{i,S}^{\mathrm{st}}\left({\tau }_{h-1}\right)}\underset{h=2}{\overset{H}{.Math.}}{Q}_i\left({\tau }_h\right)A_i\left({\tau }_h\right)\end{array}$$s.t.f_{i,L}^{\min }\le f_{i,L}\left({\tau }_h\right)\le f_{i,L}^{\max },{\tau }_h\in H,$$\underset{h=1}{\overset{H}{.Math.}}{D}_i\left({\tau }_h\right)=D_i\left({\tau }_h\right),{\tau }_h\in H,\mathrm{and}$$0\le \underset{h=1}{\overset{H}{.Math.}}{D}_i\left({\tau }_h\right)\le Q_i\left({\tau }_h\right),{\tau }_h\in H,$