2.1 Basic concepts
Edge computing sinks computing tasks into the vicinity of the wireless access network, i.e., the base station, and provides the services and computing functions required by mobile devices through the wireless access network. On the basis of the smart city, we establish a mobile computing model based on mobile edge computing. Each base station is defined as an edge node, which provides computing resources for nearby mobile devices. Suppose there are N edge nodes deployed is the edge computing environmental, denoted as E={e1,e2,...,eN}.
Let S={s1,s2,...,sM} be the set of mobile devices, where M is the amount of mobile services. Each mobile device in S generates workflows when task arrives, which schedules its computing tasks to different edge nodes to get sufficient computing resources. Ti={t1,t2,...,tQ} represents set of workflow tasks, where Q is the amount of it. The edge nodes in E provide computing resources for tasks in T; in other words, tasks are scheduled to different edge nodes for execution.
Definition 1 Dependencies among workflows.There are dependencies among some workflow tasks [30]; in order to express these relationships clearly, we use a direct acyclic graph G=(
T, D)
to model workflow operations, where D is the set of dependencies between workflow tasks. Each dependency is in the form of directed edge di, j=(
ti,
tj) (1<
i, j≤
Q),
which means only when the task ti is completed can the task tj begin. The dependencies of tasks in the workflow can be calculated by conditional probability [21].
2.2 Completion time analysis of workflow
All workflows constitute a directed acyclic graph. In order to reduce the processing time of workflow, we find critical paths to meet the deadlines of workflow tasks. In order to simplify the problem, we add two virtual tasks tstart and tlast at the beginning and end of the workflow to ensure the single entry and single output of tasks.
Definition 2 Parent tasks.Due to the dependencies among the tasks, a task ti (i={1,2,...,Q}) can start only when all its parent tasks are finished. We use the set P(ti) (i={1,2,...,Q}) to represents parent tasks of the ith task.
The earliest start time of each task in a workflow is obtained from the earliest start time of its parent task, and the start time of the task
t1 is regarded as zero. The earliest start time of the
ith (
i={1,2,...,
Q}) task is calculated by:
$$ {}ES({t_{i}}) = \left\{ {\begin{array}{*{20}{c}} {0,i = \text{start},}\\ {\max (ES({t_{j}}) + TD({t_{j}},{t_{i}}) + ED({t_{j}})),0 < i \le Q,{t_{j}} \in P({t_{i}}),} \end{array}} \right. $$
(1)
where TD(ti,tj) represents the transmission delay between the parent tasks and the task ti (i={1,2,...,Q}) itself, and TD(ti,tj) denotes the minimum execution delay of the parent tasks. The earliest start time of the task ti (i={1,2,...,Q}) means that all parent tasks before it is completed as early as possible.
Therefore, the earliest finish time of the task
ti (
i={1,2,...,
Q}) is calculated by:
$$ EF({t_{i}}) = ES({t_{i}}) + ED({t_{i}}). $$
(2)
Definition 3 Children tasks.The set C(ti) represents the subtasks, i.e., the children tasks of the task ti (i={1,2,...,Q}). The children tasks of the task ti (i={1,2,...,Q}) can start only when it is finished.
Let
LF(
ti) be the latest finish time of the task
ti (
i={1,2,...,
Q}), which is defined as:
$$ {}LF({t_{i}}) = \left\{{\begin{array}{*{20}{c}} {D,i = \text{last},}\\ {\min (LF({t_{j}}) - TD({t_{i}},{t_{j}}) - ED({t_{j}})),0 < i \le Q,{t_{j}} \in C({t_{i}}),} \end{array}} \right. $$
(3)
where D is the deadline of the whole workflow which is determined by the mobile users themselves. The latest finish time of the task ti (i={1,2,...,Q}) means the latest completion time without delaying the completion of subsequent children tasks and workflows.
Definition 4 Parent critical path.The parent critical path of a task ti (
i={1,2,...,
Q})
represents the critical parent task tj (
j={1,2,...,
Q})
of task ti and the parent critical path of tj if it exists [1].
The task sequence on the parent critical path of the task
ti (
i={1,2,...,
Q}) is
Si=(
p1,
p2,...,
pH) (
i={1,2,...,
Q}), where H is the amount of the tasks. The deadline of
Si is denoted as:
$$ DL({S_{i}}) = LF({p_{H}}) - ES({p_{1}}). $$
(4)
Each task needs to be completed before its deadline. Assume that the task
pj in
Si corresponds to the task
ti in
T, then the deadlines [
31] of each task on the parent critical path is calculated by:
$$ DL({p_{j}}) = \frac{{EF({p_{j}}) - ES({p_{1}})}}{{EF({P_{H}}) - ES({P_{1}})}} \times (LF({p_{H}}) - ES({p_{1}})), $$
(5)
$$ DL({t_{i}}) = DL({p_{j}}). $$
(6)
After determining the deadlines of each task on the parent critical path, the unallocated tasks on the parent critical path will be allocated with optimal edge nodes according to the scheduling strategies.
2.3 Energy consumption analysis of workflow scheduling
In our model, we also consider the energy consumption in workflow scheduling and strive to minimize it. Firstly, we use a variable
αi, k to represent the allocation status between the task
ti in
T and the edge node
ek in
E. If the task
ti is allocated to the edge node
ek,
αi, k=1; otherwise,
αi, k=0. Therefore, the energy consumption of workflow scheduling is denoted by:
$$ EC = \sum\limits_{i = 1}^{Q} {\sum\limits_{k = 1}^{N} {{\alpha_{i,k}} \cdot t{e_{i,k}} + \sum\limits_{i = 1}^{Q} {e{e_{i}}}} }, $$
(7)
where tei, k is the transmission energy consumption which is generated when the task ti is transferred to the edge node ek, and eei represents the execution energy consumption pf the task ti. The eei is determined by the size of the computing tasks.
2.4 Success rate analysis of workflow rescheduling
Finally, we will evaluate the success rate of workflow rescheduling. Assume that there are
A tasks needed to be rescheduled because of the uncertainties. The variable
βv (
v={1,2,...,
A}) denotes whether the task
tv is successfully completed or not.
$$ {\beta_{v}} = \left\{ {\begin{array}{*{20}{c}} {1,RC({t_{v}}) \le DL({t_{v}}),}\\ {0,\text{otherwise}.} \end{array}} \right. $$
(8)
where RT(ti) is the real completion time of the task ti in T. Whether the actual completion time of a task is prior to its limited deadline is the criterion to determine whether the task is rescheduled successfully.
Consequently, the success rate of workflow rescheduling is calculated by:
$$ SR = \frac{1}{A}\sum\limits_{v = 1}^{A} {{\beta_{v}}}. $$
(9)