In the Internet of Things (IoT) era, various nodes generate vast quantities of records, and data processing solutions consist of a number of activities/tasks that can be executed at the Edge of the network or on the Cloud. Their management at the Edge of the network may limit the time required to complete responses and return the final result/analytic to end users or applications. Also IoT nodes can perform a restricted amount of functionality over the contextual information gathered, owing to their restricted computational and resource capacities. Whether tasks are assigned to an Edge or a Cloud is based on a number of factors such as: tasks' constraints, the load of nodes, and energy capacity. We propose a greedy heuristic algorithm to allocate tasks between the available resources while minimizing the execution time. The allocation algorithm considers factors such as the deadline associated with each task, location, and budget constraint. We evaluate the proposed work using iFogSim considering two use case studies. The performance analysis shows that the proposed algorithm has minimized cost, execution time, control loop delay, networking, and Cloud energy consumption compared to the Cloud-only approach.
Cyber-Physical Systems (CPSs) are integrated systems that aim to
bring physical entities together with the all-present computing and
networking systems [
Many of these problems could be solved by using Cloud-Assisted
Things or Cloud of Things (CoT) technology as it provides
largescale and on-demand computing resources for managing, storing,
processing, and sharing IoT information and services [
There are certain challenges that need to be considered while making the allocation and scheduling decisions. The main challenges are given below.
To address these challenges while making the allocation, we propose a layered-based algorithm that identifies and minimizes the global bottleneck, i.e., minimizing the processing time and the cost as well as maximizing the utilization of resource computation at the Edge layer. The main contributions of this work are summarized as follows: • We consider a task placement approach based on cooperation between the Edge and Cloud that supports service decentralization, leveraging context-aware information such as location and available computing and storage capacities of Edge resources. The placement approach considers deadline constraints associated with each task as a way to emphasize utilizing Edge resources and a budget constraint at application level. This maximizes the utilization of Edge resources and minimizes latency, energy consumption, and cost. • We conduct a performance analysis with various case studies using iFogSim1 to reveal the efectiveness of the proposed approach in terms of maximizing the utilization of Fog devices while reducing latency, energy consumption, and network load. 2
SLA- AND CONTEXT-AWARE APPROACH FOR IOT ACTIVITY PLACEMENT ACROSS CLOUD AND EDGE In this approach, we consider IoT applications, which mostly consist of a set of activities, some of which requires high bandwidth and low computation. They can be performed on one of the resources at the Edge of the network, while if an activity requires more computation, then it can be ofloaded to the Cloud. In the case where there is more than one activity, selecting which one to deploy at the Edge or the Cloud level can be based on diferent criteria (e.g., cost, distance, location, processing time). Our aim is to provide a solution that distributes the workflow activities in such order that optimize both consumer requirements and utilizes computation capabilities at the Edge, meanwhile aiming to avoid any SLA violation. 2.1
Problem Definition and Modeling In IoT applications, task/activity placement is the problem of allocating tasks/activities to a set of processors (resources) that are distributed across layers (Edge and Cloud). The input to the task placement controller is an activity graph and a processor graph, and the output is a placement plan that maps each activity to a suitable processor/resource. Whether the resources are located at the Edge or the Cloud is based on each task/activity’s computation and communication requirements. 2.1.1 Multi-layer Computing Architecture for IoT. This section presents the proposed multi-layer architecture for IoT. It also describes the task placement information and the necessary concepts related to the proposed scheme. Figure 1 denotes the three main layers as described below: 1The iFogSim is an open source toolkit for modeling and simulating resource management approaches for IoT, Edge and Fog Computing https://github.com/Cloudslab/iFogSim • IoT devices: the layer consists of devices with sensing and actuating purposes. It also has internet connection capability for transferring the data to Edge or Cloud. • Edge Computing layer: this includes the upper layer of the IoT devices which provides lightweight computation. Resources in this layer are distributed to cover diferent regions. In other words, resources can be clustered by the region which covers the IoT devices within that region to connect and transfer data. • Cloud Layer: It is the centralized layer where heavy computation/storage processes can be delegated. 2.1.2 Task Graph: A task graph is represented by a directed acyclic graph (DAG), T G = (T , E) where the set of nodes T = {t1, t2, t3, ..., tn } represent n tasks. Between tasks, there is a set of edges belongs to E which represents the data dependency between nodes. For example, tasks t1 and t2 are connected by e1,2. In another word, between any ti and tj , there is ei, j belongs to E. Thus, we can define Edges and Tasks as follow:
∀(ti ∧ tj ∈ T ), ∃ ei, j = (ti , tj ) ∈ E
Consider T represents a task which is defined as T = {Tid , ReqPCapcty, deadline, region, level}. Tid represents the task Id, ReqPCapcty represents requested processing capacity, deadline represents the deadline constraint of a single task while reдion reveals the region/location where this task is preferable to be deployed. Finally level is used to denote how many hops this task is far from the starting point which in our case is sensing events.2
Each ei, j can be defined as ei, j = ( SrcI D, DisI D, dataTransfereRate, TupleProcessingReq, TupleLentgth) where SrcI D represent the source task id (ti node); DisI D represents the destination task id (tj node); dataTransfereRate expresses the data transfer rate between ti and tj , TupleProcessingReq represent the processing requirement of coming tuples, and TupleLength represents the total length of the tuple.
Each task has one or more predecessors unless it is a start task as well as successors (one or more) unless if it is a finish task (see Figure 2 which depicts the start and finish tasks). Any task starts only after 2Within the text, we used tasks, workflow activities and intermodules interchangeably for the same meaning. all its predecessor tasks have completed, so its earliest start time is equal to the maximum finish time of all of its predecessors. 2.1.3 Processor Graph. Consider the presented topology in Figure 3. A processor graph is represented by a DAG, PG = (P , D), where the set of nodes P = p1, p2, p3, ..., pn represents n processors, a processor belongs to P can be a Cloud or an Edge resource. Between processors, there is a link distance d that connects them, for example, processors p1 and p2 are connected by d1,2, so there is a set of links di, j between any pi and pj belongs to P and di, j belongs to D. We can define the distance links and processors as follows:
∀pi ∧ pj ∈ P , ∃ di, j = (pi , pj ) ∈ D p1 dev1 d 1,7
p7 GW1 p2 dev2
p9 d 7,9
Cloud Resource d 3,7 p3 dev3
GW2 dev4 dev5 dev6
Each processor pi can be defined as pi =(pCapctyi , upLnkLatencyi , pmLoadi ). pCapctyi is considered to hold processing capacity of pi , communication bandwidth is upLnkLatencyi and pmLoadi is the current PM load. 2.1.4 Objectives. The objective is to propose a placement mechanism which aims to maximize the utilization of Edge resource as well as minimizing the cost and latency of an IoT application. In this work, the main information considered for task/workflow activity placement is as follows: • Network Topology: available resources and their computation capabilities. • Location of initiated requests or consumed services. • Service Type: data storing and data filtering are services that require diferent computation/storage capabilities, therefore, approximate size of data (e.g. required Million Instructions Per Second (MIPS) required by an activity/task). • Level of activity: number of hops that separate a task/activity from its starting point, in our case from the IoT devices that generate the data. It is essential to denote the dependency between tasks that helps to avoid assigning a task to the resource on the level lower than their predecessor, as well as to allow parallel processing for tasks that are within the same level. • Quality of Service: knowing in advance the constraints on the ofered services plays a role in selecting the type and layer of resource. In our work we considered minimizing the end-to-end response time by considering the deadline constraint for each involved task/activity.
To express our objective in maximizing the utilization of Edge resources, Each Task ti can be deployed on RCloud or on REdдe , however, deploying ti on a Cloud resource or Edge resource is a binary variable. If ti is deployed on Cloud, then 1 is assigned to TiRCloud while 0 to TiREdдe and vice versa.
Each task is processed on either Edge or Cloud resources, thus, we try to maximize assigning tasks to Edge resources whenever it is appropriate which we represent mathematically as :
i=n Maximize Õ i=0
The processing time of a taski on a pj is calculated as given in equation 2.
α ptij fti (zi ) TEx ec (ti , pj′) =
+ upLnkLatencypj p′ j
Here, fti (zi ) represents computation requirement for task ti and zi represents data into task ti and α ptij represent number of current modules running concurrently with ti on node pj′.
To calculate the CPU requirement for upcoming data/tuples for task ti is given in equation 3 for each edge has ti as its distention(i.e DisID for edge e is ti ). Where DTR represents the data transfer rate of an edge e and TPR represents the required processing capacity for each transferred tuple by edge e.
edдee=y
Õ edдee=0
DT R × T PR ∀ edдe e has DisI D = ti (3)
The total cost of of running ti over node pj is sum of memory cost memCostT i , communication cost commCostT i , storage cost storдCostT i and node cost nodeCostT i as given in equation 4. Each of these costs are explained in equation 5 - 8 respectively. Cost (Ti ) = memCostT i + commCostT i + storдCostT i + nodeCostT i (4) memCostT i = fti (zi )memoryCostU nit
pi commCostT i = sizeDataIn ∗ commCostU nit storдCostT i = DataT oStore ∗ StoraдeCostU nit nodeCostT i = Ti Ex ec ∗ N odeCost (1) (2) (5) (6) (7) (8) 2.1.5 Proposed Algorithm. In the following section, we present the proposed algorithm for placing intermoduls among available resources with considering the following objectives and constraints:
Ofline Integer Programming Formulation. Here we aim to minimize the cost of deploying intermodules on available resources and and the end to end response time. For the ofline version of the intermodules placement problem, integer programming formulations are derived. These formulations are used to devise limits on the suggested approach. The main objective aims at minimizing the execution time while considering other constraints such as cost/budget constant. Table 1 summarizes the notations used in our formulation. Our main decision variables, denoted as xi j is defined as follows: subject to
i=n obj = Minimize Õ T imet aski
i=0 xi j ∈ 0, 1, ∀i = 0, 1, ..., n; ∀j = 0, 1, ..., m i=n Õ CostTi <= CostConstraint i=0
i=n i=n Õ TiREdдe > Õ TiRCloud i=0 i=0 Õ
ti j <= 1 i,l evel =l k=pr edecessor List Size
Õ k=0,i, j tk jtier <= ti jtier
(9) (10a) (10b) (10c) (10d) (10e)
Constraint 1 enforces the binary nature of xi j . Constraints 2 ensures that the cost of the deployment plan will not exceed the cost/budget limit. Constraints 3 ensures that number of assigned intermodules to Edge resources is greater than the number of assigned intermodules to Cloud resources. Constraint 4 ensures that no two intermodules from the same level are assigned to the same resource. Constraint 5, for all predecessors of a ti ti that has required processing capacity more than ti itself, constraint 5 ensures that no intermodule ti is assigned to a resource that is located in a tier lower than any of its predecessors.
In Algorithm 1, the Tasks and resources graphs are inputs. Line 6,7 and 8 are defining the associated level of each intermodules which calculated based on number of hops between the intermodule and the source of captured interesting event. Line 10 to 12 are to calculate the corresponding execution time of deploying ti on resource pj and then sort all resources based on their execution time. Starting with the least execution time do the constraints checking starting from Line 14 till 28: it check if pj resource has predecessors to check that no predecessor of an intermodule ti , is assigned to a resource that allocated in a layer higher than the current checked pj . If there is a resource pj , that has one of ti ’s predecessor deployed on OR there is no predecessor of ti are deployed on a resource with layer above the current pj , then do checking on the associated constraints with the interemodule ti by calling checkConstraintsConsistencyFunction (Line 21). If there is no resource pj Notations ti pj ei j li j bwi j zi j disi j di j picapacity
ei, j
pCapctyi upLnkLatencyi pLoadi
T imeConstraintti j T imeti j ti jtier predecessor ListSize
Meanings task/activity/intermodules i a resource with processor pj dependency edge between two tasks ti and tj Link between two resources Pi and Pj bandwidth of link li j data size transferred over edge dependency ei j distance between Pi and Pj Link delay of link li j between Pi and Pj Computation capacity of resources Pi Represents requested processing capacity Reflects how many hops this task is far from the starting point Edge between ti and tj task nodes Represent the source id Represents the destination id Expresses data transfer rate between ti and tj Represent processing requirement of the tuples Represents the length of tuples Holds processing capacity of pi in MIPS Up Link Latency of pi Current CPU load of pi Represents the length of tuples Task ti is running on Edge resource Task ti is running on Cloud resource Time constraint of runing ti Execution Time of running ti on resource pj Reflects the tier of resource pj that run ti predecessors of ti with ReqPCapcty less than ti ’s Sort resources based on their execution time of task ti in ascending order that matches the requirements and considered constraints then assign ti to Cloud resource. In checkConstraintsConsistencyFunction t checks that a resource pj can sustain the intermodule within its deadline constraint, not exceeding the budget and it is not running other tasks that have the same level as the coming intermodule and it is within the same region. If searching all resources within the same region does not satisfy the constraints, then check the other regions, if there is none then return false. If false is returned, then the task is assigned to Cloud resource if the cost constraint is not violated.
Algorithm 1: SLA aware algorithm for application modules placement cross layers 1 Input: TG=(T,E) ; PG=(P,D) 2 region =-1 3 found= false 4 Output: a mapped applications modules to available resources 5 Objectives: Minimize Cost and Minimize Application latency 6 foreach ti in TG do 7 define a deadline d constraint 8 assign a level value to ti foreach resource pj in PG do calculate T imeti j add(SortedResorces, pj ) end foreach resource pj in SortedResorces do if ti has a predecessor then foreach tk in predecessor list of ti do if tk is already assigned to a PG resource then
pl = the PG resource that tk is assigned to else if pl l evel is greater than pj l evel then
break call checkConstraintsConsistencyFunction if checkConstraintsConsistencyFunction then assign ti to pj update list of assigned modules of pj Found= true else end
continue end end end if not found then
Calculate the Cost of executing ti on Cloud as in Eq. 4 if TotalCost+=cost of executing ti on a Cloud resource is less than budget then update TotalCost assign ti to a cloud resource
Log The Cost exceeds the allowed Budget and break 2.2
Time Complexity Analysis We solved this problem as a context-aware approach, therefore, if the intermodule does not have predecessors, then in best case scenario, first search attempt returns a resource that matches the requirement for each intermodule, thus the time complexity is θ (n), where n represents number of intermodules. However, in worst case scenario when finding a resource that matches intermodules’ constraints and performing it for each intermodule ti , this requires checking all m resources in the resource list. Therefore, the time 9 10 11 12 else end
Go To line 4 Algorithm 2: Checking Budget Constraints Consistency after mapping tasks to resources 1 checkConstraintsConsistencyFunction 2 if region==-1 then 3 4 if ti r eдion == pj r eдion then if that pj does not have tasks from the same level of ti then
Calculate the Execution Time of ti on pj by applying Equation 2 if the requested CPU Less than available CPU then //Check if the resource can sustain the place module check if the time is less than or equal to the associated deadline with ti then
return true change the region value from -1 to another region not the same as region of ti return false complexity is θ (nm) where m represent number of IoT devices (e.g., mobile) in the available resources in PG. Cases where an intermodule ti has predecessors requires more time to avoid assigning an intermodule to a resource in a layer lower than its predecessors’s resource. Thus we perform a checking step that iterates all of an intermodule’s predecessors. As a result, in best case scenario, when an intermodules has only one predecessor and finds a resource that matches intermodules’ constraints from the first attempt, the time complexity is θ (n)θ (1) and considering only the upper bound means time complexity equals to θ (n). In worst case scenario, when an intermodule ti has k predecessors and finding a resource that matches intermodules’ constraints leads to checking all available m resources. In this case, time complexity can be calculated as θ (nmK ), so time complexity can be in worst case scenario: θ (nm)+θ (nmK ) , however, since k, which represents number of predecessors of an intermodule, is less than total number of intermodules n, therefore the Time complexity is θ (nm). 3
To evaluate our proposed algorithm we run it using the iFogSim
simulator. It simulates IoT applications where it can enable
application modules to be allocated and scheduled among Fog and
Cloud resources. There is a number of simulators for IoT,
however, we chose iFogSim due to the fact that it is built based on
CloudSim, which is popular among researchers for testing various
strategies/algorithms. Furthermore, iFogSim has been used by a
considerable number of published works such as [
For evaluation purpose, we consider the following use case scenario: 3.1.1 Remote Health Monitoring Service (RHMS) Case Study 1. Consider a Remote Health Monitoring Service (RHMS) where patients (elderly people, people with long term treatments,...) can subscribe to be monitored on a daily basis. Data is collected and filtered and if there is an interested pattern or event that match a threshold value, then data can be analysed on a small scale if it is related to a specific patient, however, in cases that require comparing coming data with historical data, or in cases that same events come from diferent subscribers such as fever signs, then the scenario can be considered as a large scale data analysis task that needs high computational power. Most interesting analysis results are then stored.
In this use case, the following workflow activities; data
collection, data filtering, small-scale real-time data analysis, large-scale
real-time data analysis, and storing data are considered as tasks
t1, t2, t3, t4, t5. There are sensors, attached to patients, hand-wrist,
camera video for some patients and mobile accelerometers to
capture activity patterns. They are connected to a smart phone as a
gateway which is then connected to WiFi gateway. The WiFi
gateway is connected to an Internet Service Provider, which in turn is
connected to a Cloud datacenter. Description of intermodule of this
case study is depicted in Table 2.
3.1.2 Intelligent Surveillance Case Study 2. Intelligent Surveillance
application comprises five main processing modules: Motion
Detector, Object Detector, Object Tracker, PTZ Control, and User
Interface. This case study is one of the case studies mentioned in
[
For the case study, we have considered a physical topology with diferent types of Fog devices. Table 3 and Table 4 present the configuration of the used topology. This configuration is the same for both case studies, except the number of Fog devices. Case study 1 consists of four areas and each area has four fog devices; Case study 2 consists of two areas and each area has four fog devices. 3.3.1 Analysis of Case Study1. We applied the proposed algorithm for Case Study 1 and compared the performance result with placing the intermodules on Cloud. Execution Time, Energy Consumption, Network Usage and Cost are the metrics that are Captured simulating the application and applying the proposed approach to place its intermodules using iFogSim. The following subsections compare the results of applying the proposed approach with applying the Cloud only approach when considering configurations listed in 2.
Execution Time. The overall execution time for Case Study 1 recorded less time when applying the proposed approach for task placement against the Cloud only approach. Figure 4.
Execution Time
Cloud 5640
Proposed 1345
Networking Usage. As can be noted in Figure 5, there is not much diference in network usage, however, the proposed approach reflects slightly more network usage at the Edge and this is probably because of allocating most intermodules to the Edge resources. s d n o c se llii M n i e m i T n o it u c e x E 200 180 s 160 e t liitrsgykaeenooKBUNw 11124086420000000
0 Cloud Proposed 6000 5000 4000 3000 2000 1000 0
Energy Consumption. In general, the Cloud-only approach as depicted in Figure 6 recorded a higher level of energy consumption on both Cloud and mobile layers compare with the proposed approach and on Edge layer, there is a slightly diference between both approaches which might have the same reason which is because the propose approach allocates more intermodules on Edge rather than Cloud.
Cloud Proposed
Cloud Cost. Figure 7 depicts the cost of implementing case study 1 when applying the Cloud-only approach, and our proposed approach. Cloud cost is higher with the cloud-only approach, while our approach is five times less costly than the Cloud-only approach because it only allocates "storing data" to the Cloud while the rest of deployed tasks are allocated to Edge resources.
se l u o j a g e M n i n o it p m u s n o C y g r e n E of time execution and the proposed approach has the least execution time.
s d n o c se liil M n i e m i T n o it u c e x E tsye B o il K n i e sga U rk o w t e N 3500 3000 2500 2000 1500 1000 500
0 1200 1000 800 600 400 200 Execution Time
Cloud 2528
Networking Usage. Networking usage is described for the three
tiers: IoT devices (mobiles), Edge resources (WiFi Gateways) and
Cloud. Edge-ward placement reflects the least network usage among
all proposed approaches for network usage on Edge and mobile
tiers. The proposed approach has recorded no network usage on
Cloud, but has recorded high level of network usage on the Edge tier.
This seems to be because of placing intermodules on diferent Edge
resources since it considered parallel processing for independent
tasks as well as following a greedy approach might afect the overall
optimality of resource allocation mechanism.
3.3.2 Analysis of Case Study2. We applied the proposed algorithm
for case study 2 and compared the performance result with placing
the intermodules on Cloud only as well as with the Edge-ward
placement algorithm proposed in [
Execution Time. Execution time of all three approaches: Cloudonly, Edge-ward placement and our proposed placement approaches are reflected in Figure 8. Edge-ward placement has the highest level
0 Network on Cloud Network on Edge Network on Mobile
Cloud 0.099 326.0964 6.3968
Edge-ward
0 16.4832 0.3232
Proposed
0 1038.61192 56.7716
Energy Consumption. Figure 10, shows the energy consumption for the three approaches; the Cloud-only approach demonstrates the highest value for energy consumption on the Cloud tier, however, on Edge and mobile/IoT devices all approaches reflect a similar level of energy consumption with a slightly low level for the proposed approach on mobile layer. ts o C d u o l C 16000 14000 12000 10000 8000 6000 4000 2000 0
Cloud Cost. Figure 11 shows the Cloud cost. Since the proposed approach placed all tasks on Edge, therefore Cloud cost is none while Edge-ward placement approach reflect lower cost than Cloud approach.
We have applied our heuristic algorithm to decentralize task placement in a cooperative way between Edge and Cloud resources. We have considered an RHMS as Case Study and compared it with the Cloud-only approach (an approach where tasks are placed only on the Cloud). The proposed approach demonstrates lower execution time, control loop, cost, network usage and energy consumption. Furthermore, we considered comparing our approach with a builtin use case in iFogSim. Thus we compared the results with the Edge-ward placement algorithm applied to Case Study 2. In general our proposed approach shows better results, as has been presented in the previous section.
Ref [
. 6 CONCLUSION AND FUTURE WORK Due to the limited computational and resource capabilities of IoT nodes, tasks can be allocated to Edge or Cloud resources taking into account a number of possibilities such as: task constraints, node load and computing capability. We suggested a heuristic algorithm for allocating tasks among the available resources. The allocation algorithm takes into account factors such as related time limits for each task, location, and budget constraints. We utilized iFogSim to evaluate the proposed approach for two use-case studies. The performance analysis demonstrates that the suggested algorithm has minimized costs, execution time, control loop delay, networking and cloud power usage compared to cloud-only and edge-ward positioning methods. For Future work, we will carry an evaluation of the proposed approach on real systems.