# SAP: An IoT Application Module Placement Strategy Based on Simulated Annealing Algorithm in Edge-Cloud Computing

Authors: Juan Fang; Kai Li; Juntao Hu; Xiaobin Xu; Ziyi Teng; Wei Xiang
Journal: Journal of Sensors
 (2021)

---

## Abstract

The Internet of Things (IoT) is rapidly growing and provides the foundation for the development of smart cities, smart home, and health care. With more and more devices connecting to the Internet, huge amounts of data are produced, creating a great challenge for data processing. Traditional cloud computing has the problems of long delays. Edge computing is an extension of cloud computing, processing data at the edge of the network can reduce the long processing delay of cloud computing. Due to the limited computing resources of edge servers, resource management of edge servers has become a critical research problem. However, the structural characteristics of the subtask chain between each pair of sensors and actuators are not considered to address the task scheduling problem in most existing research. To reduce processing latency and energy consumption of the edge-cloud system, we propose a multilayer edge computing system. The application deployed in the system is based on directed digraph. To fully use the edge servers, we proposed an application module placement strategy using Simulated Annealing module Placement (SAP) algorithm. The modules in an application are bounded to each sensor. The SAP algorithm is designed to find a module placement scheme for each sensor and to generate a module chain including the mapping of the module and servers for each sensor. Thus, the edge servers can transmit the tuples in the network with the module chain. To evaluate the efficacy of our algorithm, we simulate the strategy in iFogSim. Results show the scheme is able to achieve significant reductions in latency and energy consumption.


---

## Body

## 1. Introduction

Smart devices (such as smart cameras, drones, and virtual reality terminals) are normally equipped with sensors and remote actuators and have the ability to sense the environment and actuate the remote signal [1]. Limited by the cost and size, terminal devices tend to be cheaper and smaller and have less computing resources. Cloud computing has scalable computing resources and can be a reasonable place for smart devices to offload their computational tasks to [2]. With the development of the Internet of Things (IoT), more and more terminal devices will be connected to the Internet [3]. There will be around 50 billion devices to be connected to the Internet by 2030, predicted by Cisco [4]. More devices connecting to the Internet mean more data will be produced and sent to the cloud. Applications in health care, smart home, or smart city need small latency to get real time response [5]. Due to the ultralong distance from the cloud data center to the edge of the network and huge amounts of data produced by the devices, cloud computing cannot always meet the real time requirement [6].As an emerging computing architecture, edge computing is proposed to make up the shortcoming of cloud computing. Edge computing extends cloud computing by deploying edge servers at the edge of the network and providing compution, storage, and network services between IoT devices and cloud data center [7]. Because edge servers are closer to the data producers, data can be processed with less communication latency, and IoT terminal devices can process data faster [1]. Thanks to its advantages, edge computing brings a broad prospect for real-time applications (e.g., health care, smart monitoring, and autopilot [8]).Although edge computing brings about many benefits, it also has shortcomings compared with cloud computing. Limited by the cost, servers deployed at the edge network cannot expand their resources like cloud computing [9]. Because of the limit of resources, edge servers might be overloaded with the increase of data produced and decrease the Quality of Service (QoS). Therefore, how to allocate the resource of edge servers and how to schedule the tasks of applications have become a hot topic in the area of edge computing.IoT applications can be divided into several modules to process different stages of it [10], and modules can be distributed at different servers. The data dependence of modules determines the data flow between modules. By allocating modules in the distributed edge servers and cloud data center, we can improve increase the QoS in terms of latency and energy consumption [11].To make full use of edge servers in the edge computing network and meet the real-time requirement of future IoT applications, we need to reduce the processing latency and avoid the wasting of edge computation resources. Based on these needs, the major contributions of this paper are summarized as follows:(1)
We propose a module chain to deal with the relationship between modules and sensors. In order to schedule modules of the same application, we classify the modules into the sensor and processing modules and connect the processing modules to form a module chain according to the dependencies of the modules. Therefore, the module placement problem becomes equivalent to finding resources for each module in the module chain(2)
In consideration of the limited computing resources of edge servers and the lack of bandwidth resources between the edge network and cloud computing center, a novel architecture that makes full use of edge resources is proposed. Edge servers in the same cluster communicate with each other through the Simple Network Management Protocol (SNMP). In this architecture, the cloud computing center processes computing tasks only when the edge servers are overloaded(3)
The performance of the application module placement strategy based on the Simulated Annealing Placement (SAP) algorithm is evaluated through experiments. The simulation results under various parameters are given, which show that the method can effectively reduce delay and energy consumptionThe rest of this paper is organized as follows. The related work is reviewed in Section2. Section 3 presents the application model and edge computing architecture. The policy we propose is detailed in Section 4. While in Section 5, we provide simulation results of our strategy. Concluding remarks alongside the future work are given in Section 6.


## 2. Related Work

With the real-time demand for applications in IoT, edge computing has become a hot topic. Edge computing or fog computing brings computing resources closer data producers and reduces latency to users. Many researchers have made contributions to this field [12–14].Gupta et al. [15] introduced a simulation platform iFogSim based on CloudSim with different computing models. It allows simulation and comparison of different resource management schemes in edge computing. The author describes two case studies and evaluates the impact of pure Cloud Application module placement and Edge Ward Module Placement (EWMP). The results show that the edge server is effective in the network.Facing limited edge resources and the demand of application timeliness, system delay and effective utilization of edge resources are the main research issues. The research content can be divided into two categories; the first is resource allocation problem, and the second is task scheduling problem. For the resource allocation problem, although the multilayer structure of edge computing can reduce the processing delay, it can also increase the power consumption and delay of transmission through the server in the network. The paper [16] mainly studies the dynamic task arrival and resource allocation problem with traffic prediction in edge computing system and describes it as a stochastic network optimization problem. The simulation results show that the power consumption is improved when the processing delay is stable.Existing researches focus on task scheduling from many aspects. Luiz et al. [17] discussed the impact of different scheduling strategies (such as FCFS, concurrency, and delay priority) on QoS when scheduling tasks in edge computing networks. The results show the advantages of the delay priority strategy, but they only consider the computing resources of edge servers. Rahbari et al. [18] proposed knapsack-based scheduling optimized by symbiotic biological search (SOS). This scheduling method was used to optimize the allocation of VM in the edge network, which improved the network energy consumption and reduced the network utilization, but the simulation lacked the comparison of delay.Intelligent algorithms have a wide range of applications, and most studies show that intelligent algorithm is effective in the application of task scheduling problem. Shudong et al. [19] proposed a task scheduling algorithm to reduce the processing time by using the improved firewall algorithm to ensure the overall load balance of edge devices in cloud edge computing system. This method considers the task characteristics and resources of the server. However, the author did not consider the energy consumption of the edge server. Songyuan and Jiwei [20] discussed the energy efficiency of the Internet of Things system and introduced resource management and task scheduling strategy through the establishment of the Markov Decision Process (MDP) to reduce task execution delay and equipment energy consumption. The method proposed by Mao et al. [21] jointly optimized the task offloading scheduling and transmission power allocation of an edge computing system with multiple independent tasks [22] aimed at multiuser, multiuser, multiuser. The unloading problem of heterogeneous edge server forms a multiobjective optimization problem from the time consumption and energy consumption resource utilization of the first level edge service and uses the improved Pareto optimization algorithm for collaborative optimization of end-to-end cloud.In order to improve (user Quality of Service) QoS and minimize delay and energy consumption, Jie et al. [23] captured a user centric view computing offload scheduling strategy to improve QoS. By describing the problem as a mixed integer nonlinear programming problem, they improve the delay and energy consumption. At the same time, [24] proposed a user centered joint optimization loading scheme, which minimizes the weighted cost of delay, energy consumption, and price to provide personalized services for users on the premise of meeting the personalized needs of users. In order to make full use of the computing power of the edge server and reduce the response delay of the application, the author proposed a delay aware application module management strategy for the edge environment in [25]. This strategy is aimed at ensuring the application will achieve QoS on the premise of meeting the service processing deadline. But they did not consider the energy consumption of edge servers and cloud data centers. In order to optimize the energy consumption of the system, Gholamreza et al. [26] proposed a task scheduling method based on Bayesian classification. By classifying tasks, virtual machines can be created according to the predicted requirements.In [27], the author pointed out that by using the limited application protocol (COAP) and Simple Network Management Protocol (SNMP), servers in the same area can form a cluster and communicate with each other directly with low delay. Based on this theory, Fang et al. [28] proposed an online task scheduling algorithm in edge computing. The algorithm makes some improvements in reducing delay and network usage. But they did not take energy consumption and scheduling time into account.As an effective method of resource allocation, Nam et al. [10] proposed a distributed data flow (DDF) application model of the Internet of Things, which divides an application into several distributed modules and places them on the distributed servers of the edge layer and cloud data center. The application model helps to promote the deployment of application logic by combining application constraints and device functions, thus providing a simple way to design IoT applications. By placing application modules in appropriate servers, edge computing systems can improve the quality of the experience. Redowan et al. [29] introduced a QoE aware application placement strategy. This strategy generates the priority of different applications by prioritizing the requests expected by different users and considering the current state of the edge server. Simulation results show that the method has the advantages of improving data processing time, network congestion, and resource affordability. The module placement method proposed by Dadmehr and Mohsen [30] considers the processing delay and energy consumption in edge computing. By using the classified regression tree algorithm and comparing the amount of computation with the communication power consumption, the simulation results show that the algorithm reduces the energy consumption and response time of the system.Thus, the placement strategy of application modules on the server is an effective method to optimize the resource allocation problem, while most studies do not consider the structural characteristics of edge computing to deal with the task scheduling problem in edge computing. In the next section, we will propose a module placement method based on simulated annealing algorithm, which aims to reduce energy consumption and processing delay.


## 3. System Model

### 3.1. Application Model

The application model we deploy in the edge computing system is based on the distributed data flow model (DDF) [10]. An application program is decomposed into a structure of multiple modules, which can be processed by multiple task processors according to the dependencies between the modules. Figure 1 shows a decomposed directed graph based on DDF applications.Figure 1
Decomposed directed graph based on DDF applications.Modules in a DDF represent different processers of an application which are distributed in the edge computing network. The direction of data flow shows the dependencies between the modules. Usemi to represent the ith processor of the program. The output of a module mi is the input of the next module of mi. mi and mj in the same program are transmitted through tuple-j, where j represents the input to tuple. The original data is produced by a sensor, and the result after the processing of several modules is sent to an actuator.Tuples between modules represent communication tasks between modules with dependency. Thus, the sensor is regarded as the beginning of an application, and the actuator is the end of it. An application (A) has modules (M), and data dependencies (D) can be written as follows:
(1)A=M,D,where A represents an application, M represents the modules of the application, and D donates the data dependence relationship of the modules.Modulemi has its required resource Reqi to process data, e.g., CPU, storage, and bandwidth. The policy we propose is based on these three attributes. Thus, Reqi can be represented by
(2)Reqi=<Mipsi,RAMi,Bwi>,where Mipsi denotes the computation requirement of module i, RAMi denotes the storage requirement of module i, and Bwi denotes the bandwidth requirement of module i. The tuples shown in Figure 2 have their own relationship and are generated by modules. Figure 2 shows the composition of a tuple: the data dependency between modules, the ID of the sensor, the ID of the gateway, the destination module name, and the module chain of the application that generated data from a sensor. SensorID, GatewayID, and the module chain will not vary with the tuple. The points in a module chain indicate the mapping relationship of modules and servers. For example, when a server receives a tuple, it will find server-i in the module chain that has the corresponding relationship with the destination module and send the tuple to server-i.Figure 2
The structure of a tuple.


### 3.2. Edge Computing Architecture

Edge computing deploys computation and storage resources between data producers and the cloud computing center. Since data is allowed to be computed at the edge of the network, edge computing reduces the frequency of data transmission between the cloud and edge servers. Figure3 shows the vertical architecture of edge computing. The first layer is the cloud data center which is connected to the edge servers through a proxy server. Edge servers are distributed at the edge of the network and have a shorter distance between the terminal. A proxy server normally routes data but does not process them.Figure 3
Edge-cloud computing architecture.The modules of an application are placed on the edge servers and cloud computing center according to a module placement strategy. An IoT device (like smart cameras and cell phones) has its sensor to produce data and an actuator to receive process results. Connected by the gateways (edge servers), the IoT devices can send their data to the edge computing network and receive the process result. The task that cannot be processed by an edge server will be sent to a higher-level server or will be eventually processed by the cloud computing center. Each serverSj with resources Resj (include CPU, storage, and bandwidth) can be represented by:
(3)Resj=<Cpuj,Ramj,Bwj.In an edge server, there might be multiple modules being processed at the same time. The CPU resources of modulemi (cpui`) are allocated as follows
(4)cpui`=cpuj×Mipsi∑mk∈MjMipsk,where Mj represents the modules placed on the edge server Sj that has data to process.


### 3.3. Timing Model

Assume the processing latency of modulemi is tpi, and the transmission delay of all modules is ttrans. Assume that there are m sensors in application A, and application A contains n modules. The average latency of application A from the sensor emitting data to the actuator receiving the result T can be represented by
(5)T=∑k=1m∑i=1ntpi+ttranskm.The processing latency can be calculated as follows(6)tpi=Mipsicpui`,(7)ttrans=Lj⟶k+diBwj,where Ln represents the communication latency between servers j and k. The size of transmitted data is donoted by di.It is reasonable that data processes in the cloud data center will take less time to process but also cause increased latency to transmit data between the edge servers and cloud. We aim to strike a balance between the edge servers and the cloud.


### 3.4. Energy Model

For an edge server, energy can be classified into dynamic energy and static energy. Static energy is due mainly to the cost of the server normally running and is affected by the time of server running. The dynamic energy includes two parts. That is,Ep represents the energy of the procedure of data processing, and Et represents the energy of the procedure of data transmission.Assume the CPU usage of the server in the time segment tp isθ, the server’s processing power and transmit power are Wp and Ws. The size of the transmited data is di. Ep and Et can be calculated as follows
(8)Ep=tp×θ×cpu×Wp,(9)Et=diBwj×Ws.Assume there arek edge servers in an area. The average energy E of the edge servers in an area of the third layer can be calculated as
(10)E=∑i=1kEsi+Epi+Etik.


### 3.5. Module Placement Problem Formulation

In light of limited computation resources available at edge computing servers, we consider the module placement problem, i.e., deciding which edge server application module should be deployed. We define the integer decision variablexi∈N that indicates module mi is placed on a certain edge server, where N represents a set of edge servers in the area. The variable of module placement is as follows: X=x1,x2,∙∙∙,xm. We propose to minimize the energy consumption E and the average latency T as shown in Sections C and D.Formally, the module placement problem can be formulated as follows:(11)minimizeXα×e−T+β×e−E,subjectto:a:∑i=1mRAMmi<Ramsj,xi=j,b:MaxBwmi≤Bwsj,xi=j,c:sj∈N,d:mi∈M.The objective function (11) is to minimize the energy cost and the completion latency. The first constraint (a) indicates that the sum of storage demand of modules placed on edge server-j is less than that of edge server-j. The second constraint (b) suggests that the maximum bandwidth among the modules placed on edge server-j is less than the bandwidth of edge server-j. N in (c) represents a set of servers in an edge computing network, while M in (d) represents the set of modules to be placed on servers.


### 3.6. Module Placement Strategy

In this article, we try to find a solution to placing application modules on edge servers and cloud computing servers using the simulated annealing technique. The method we propose tries to find an appropriate set including the module chain of each sensor in an area and then generate the module placement scheme with the set of module chain.


### 3.7. Application Module Analysis

Client modules are deployed at IoT devices by default, and the other modules need to find appropriate servers to be placed on. Firstly, we need to classify the modules of applications that need the data from terminal devices. The following modules can be connected as a chain base on the data dependencies of the modules. Modulemj which has a set of precursors Mp and a set of successors Ms in the module chain can be expressed as follows
(12)mJ=pD,sD,where pD=dij,i∈Mp is the set of data dependency rules between mj and mp. Similarly, sD=djk,k∈Ms is the set of data dependency rules between mj and Ms.As shown in Figure4, sensor S1−1 represents a sensor of an application, while mi represents the following modules of the client module.Figure 4
An example of module chain.The module placement problem is equivalent to finding a suitable server for module processing for the module in the chain, which can make full use of server resources and return the result to the client module with less delay.The servers in the edge computing servers can be divided by the level and the connection relationship into a device table. As shown in Table1, the network in Figure 3 is divided as follows.Table 1
Units for magnetic properties.
LocationLevel 3Level 2Level 1Area 14, 5, 6, 721Area 28, 9, 10, 1121


### 3.8. Improved Edge Computing Architecture

We also study the architecture of the edge server. In this part, we propose an improved edge-cloud computing architecture, which can make full use of the edge server resources in the application module placement problem.Figure5 shows the improved edge computing architecture we propose. Servers in the same area can form clusters and communicate with each other directly with low latency through the Constrained Application Protocol (CoAP) and the Simple Network Management Protocol (SMP) [21]. As shown in Figure 6, the edge servers in the third level have shorter distances between each other and can be regarded as an area. We connect the edge servers in an area and make the data transmitted through these edge servers. In this situation, more data can be processed at the edge of the network. The cloud computing center can process tasks, only if all the edge servers are fully used. Although the processing time will increase in the edge servers, the data transmission time will reduce notably.Figure 5
Improved edge-cloud computing architecture.Figure 6
The mapping relationship of modules of sensor and servers with the module chain.The application modules are placed at servers in the network. And the module chains tied to the sensors reflect the mapping relationship of the modules and servers. As shown in Figure6, modules of the sensor belonging to an application show how the servers to place each module, and the modules are placed at the corresponding servers.


### 3.9. Simulated Annealing Algorithm in Module Placement of Edge Computing

The simulated annealing algorithm is inspired by the phenomenon of solid annealing and usually used to find a good approximation for a global optimum. By choosing a worse solution with a certain probability to find the global optimal solution, the algorithm can be used to solve an NP-hard problem.The input parameters of our algorithm include the device table in the edge computing network and the module chains like Figure6. And the method is shown in Algorithm 1.Algorithm 1: Simulated annealing module placement strategy (SAP).
Input: sensors, edge servers table N, applications A, communication latency between edge servers Ln;Initialization:Set the start temperatureTemp, coolingrate, loop count, End temperature Tend;Start:Generate the initial module placementp_temp;WhileTemp>Tenddo:i=1;Whilei<loop count do:value_temp⟵Evalueate(p_temp);p_new⟵Algorithm2GenerateNewChain(A, p_temp, value_temp);value_new⟵Evalueate(p_new);∆E= value_new – value_temp;if∆E<0then:p_temp = p_new;else ifexp−E/Temp>randthen:p_temp = p_new;end ifi+1;end whileT←T×cooling rate;end whileOutput: module placement p_temp;Algorithm1 is executed according to the following steps:Step 1.
Set the initial temperature (Temp), loop count (C), and termination temperature of the algorithm and generate a random solution. The solution indicates the placement of the modules in the module chains. Figure 6 shows an example of the placement of the chain shown in Figure 1.Step 2.
Evaluate the solution; get the values ofk evaluation. This average latency T and energy consumption E are the optimization objectives in the proposed algorithm. Since the magnitudes of latency and energy consumption are quite different, we make them the same order of magnitude:
(13)VT=e−T,(14)VE=e−E.
The fitness function can be calculated by:(15)Vcurrent=α×VT+β×VE.
The values ofα and β represent the weights of latency and energy in the fitness function, respectively, where 0≤α≤1, 0≤β≤1, and α+β=1. We can change the values of α and β to adjust the optimization goal.
Save this value as the current evaluation valueVcurrent and save the latency of each module chain.Step 3.
Make random perturbation to the module chain that has the maximum latency in the solution. The method is shown in Algorithm2. In this step, the module has a higher possibility to be placed on a higher-level server. Then, we use (15) to calculate the evaluation value Vnew of the new solution.Algorithm 2: Generation method of the new module chain.
Input: applications A, module chains p_temp, Temp;Initialization: l =3;Start: find the worst latency value chain c in p_temp;for all module mi in c do:get a random serversjat the servers no lower than l;ifRamireq<Ramjallocated&&Bwireq<Bwjallocatedthen:placemi on server Sj;if the level of Sjlj`< l then:l = lj``end ifelse:placemi on serverSk at the higher level than Sj.l = lk`end ifend forOutput: placement of module chains on servers p_new;Step 4.
The simulated annealing algorithm can find the global optimal solution. While the new solution is better thanVcurrent, Vcurrent will be updated as Vnew. If Vnew is worse than Vcurrent, the algorithm will be updated as Vnew with the possibility γ. The value of γ will be calculated as follows:
(16)γ=exp−Vnew−VcurrentTemp.
The update ofVcurrent can be expressed as follows:
(17)Vcurrent=Vnewα+Vcurrent1−α,(18)α=1Vcurrent<Vnew∥PVcurremt≥Vnew,γ0Vcurremt≥Vnew.
The value ofα is determined by the values of Vcurrent andVnew, PVcurremt≥Vnew,γ. This means that when Vcurrent is greater thanVnew, it is received with the probability of γ, and the value of a is updated to 1.Step 5.
Repeat Steps3 and 4 until the loop count meets C.Step 6.
Drop the temperature. If the temperature meets the termination temperature, ends the algorithm. Otherwise, proceed with Step3. Assume q is the ratio of temperature dropped. The temperature Temp is reduced as follows:
(19)Temp=Temp×q.


## 3.1. Application Model

The application model we deploy in the edge computing system is based on the distributed data flow model (DDF) [10]. An application program is decomposed into a structure of multiple modules, which can be processed by multiple task processors according to the dependencies between the modules. Figure 1 shows a decomposed directed graph based on DDF applications.Figure 1
Decomposed directed graph based on DDF applications.Modules in a DDF represent different processers of an application which are distributed in the edge computing network. The direction of data flow shows the dependencies between the modules. Usemi to represent the ith processor of the program. The output of a module mi is the input of the next module of mi. mi and mj in the same program are transmitted through tuple-j, where j represents the input to tuple. The original data is produced by a sensor, and the result after the processing of several modules is sent to an actuator.Tuples between modules represent communication tasks between modules with dependency. Thus, the sensor is regarded as the beginning of an application, and the actuator is the end of it. An application (A) has modules (M), and data dependencies (D) can be written as follows:
(1)A=M,D,where A represents an application, M represents the modules of the application, and D donates the data dependence relationship of the modules.Modulemi has its required resource Reqi to process data, e.g., CPU, storage, and bandwidth. The policy we propose is based on these three attributes. Thus, Reqi can be represented by
(2)Reqi=<Mipsi,RAMi,Bwi>,where Mipsi denotes the computation requirement of module i, RAMi denotes the storage requirement of module i, and Bwi denotes the bandwidth requirement of module i. The tuples shown in Figure 2 have their own relationship and are generated by modules. Figure 2 shows the composition of a tuple: the data dependency between modules, the ID of the sensor, the ID of the gateway, the destination module name, and the module chain of the application that generated data from a sensor. SensorID, GatewayID, and the module chain will not vary with the tuple. The points in a module chain indicate the mapping relationship of modules and servers. For example, when a server receives a tuple, it will find server-i in the module chain that has the corresponding relationship with the destination module and send the tuple to server-i.Figure 2
The structure of a tuple.


## 3.2. Edge Computing Architecture

Edge computing deploys computation and storage resources between data producers and the cloud computing center. Since data is allowed to be computed at the edge of the network, edge computing reduces the frequency of data transmission between the cloud and edge servers. Figure3 shows the vertical architecture of edge computing. The first layer is the cloud data center which is connected to the edge servers through a proxy server. Edge servers are distributed at the edge of the network and have a shorter distance between the terminal. A proxy server normally routes data but does not process them.Figure 3
Edge-cloud computing architecture.The modules of an application are placed on the edge servers and cloud computing center according to a module placement strategy. An IoT device (like smart cameras and cell phones) has its sensor to produce data and an actuator to receive process results. Connected by the gateways (edge servers), the IoT devices can send their data to the edge computing network and receive the process result. The task that cannot be processed by an edge server will be sent to a higher-level server or will be eventually processed by the cloud computing center. Each serverSj with resources Resj (include CPU, storage, and bandwidth) can be represented by:
(3)Resj=<Cpuj,Ramj,Bwj.In an edge server, there might be multiple modules being processed at the same time. The CPU resources of modulemi (cpui`) are allocated as follows
(4)cpui`=cpuj×Mipsi∑mk∈MjMipsk,where Mj represents the modules placed on the edge server Sj that has data to process.


## 3.3. Timing Model

Assume the processing latency of modulemi is tpi, and the transmission delay of all modules is ttrans. Assume that there are m sensors in application A, and application A contains n modules. The average latency of application A from the sensor emitting data to the actuator receiving the result T can be represented by
(5)T=∑k=1m∑i=1ntpi+ttranskm.The processing latency can be calculated as follows(6)tpi=Mipsicpui`,(7)ttrans=Lj⟶k+diBwj,where Ln represents the communication latency between servers j and k. The size of transmitted data is donoted by di.It is reasonable that data processes in the cloud data center will take less time to process but also cause increased latency to transmit data between the edge servers and cloud. We aim to strike a balance between the edge servers and the cloud.


## 3.4. Energy Model

For an edge server, energy can be classified into dynamic energy and static energy. Static energy is due mainly to the cost of the server normally running and is affected by the time of server running. The dynamic energy includes two parts. That is,Ep represents the energy of the procedure of data processing, and Et represents the energy of the procedure of data transmission.Assume the CPU usage of the server in the time segment tp isθ, the server’s processing power and transmit power are Wp and Ws. The size of the transmited data is di. Ep and Et can be calculated as follows
(8)Ep=tp×θ×cpu×Wp,(9)Et=diBwj×Ws.Assume there arek edge servers in an area. The average energy E of the edge servers in an area of the third layer can be calculated as
(10)E=∑i=1kEsi+Epi+Etik.


## 3.5. Module Placement Problem Formulation

In light of limited computation resources available at edge computing servers, we consider the module placement problem, i.e., deciding which edge server application module should be deployed. We define the integer decision variablexi∈N that indicates module mi is placed on a certain edge server, where N represents a set of edge servers in the area. The variable of module placement is as follows: X=x1,x2,∙∙∙,xm. We propose to minimize the energy consumption E and the average latency T as shown in Sections C and D.Formally, the module placement problem can be formulated as follows:(11)minimizeXα×e−T+β×e−E,subjectto:a:∑i=1mRAMmi<Ramsj,xi=j,b:MaxBwmi≤Bwsj,xi=j,c:sj∈N,d:mi∈M.The objective function (11) is to minimize the energy cost and the completion latency. The first constraint (a) indicates that the sum of storage demand of modules placed on edge server-j is less than that of edge server-j. The second constraint (b) suggests that the maximum bandwidth among the modules placed on edge server-j is less than the bandwidth of edge server-j. N in (c) represents a set of servers in an edge computing network, while M in (d) represents the set of modules to be placed on servers.


## 3.6. Module Placement Strategy

In this article, we try to find a solution to placing application modules on edge servers and cloud computing servers using the simulated annealing technique. The method we propose tries to find an appropriate set including the module chain of each sensor in an area and then generate the module placement scheme with the set of module chain.


## 3.7. Application Module Analysis

Client modules are deployed at IoT devices by default, and the other modules need to find appropriate servers to be placed on. Firstly, we need to classify the modules of applications that need the data from terminal devices. The following modules can be connected as a chain base on the data dependencies of the modules. Modulemj which has a set of precursors Mp and a set of successors Ms in the module chain can be expressed as follows
(12)mJ=pD,sD,where pD=dij,i∈Mp is the set of data dependency rules between mj and mp. Similarly, sD=djk,k∈Ms is the set of data dependency rules between mj and Ms.As shown in Figure4, sensor S1−1 represents a sensor of an application, while mi represents the following modules of the client module.Figure 4
An example of module chain.The module placement problem is equivalent to finding a suitable server for module processing for the module in the chain, which can make full use of server resources and return the result to the client module with less delay.The servers in the edge computing servers can be divided by the level and the connection relationship into a device table. As shown in Table1, the network in Figure 3 is divided as follows.Table 1
Units for magnetic properties.
LocationLevel 3Level 2Level 1Area 14, 5, 6, 721Area 28, 9, 10, 1121


## 3.8. Improved Edge Computing Architecture

We also study the architecture of the edge server. In this part, we propose an improved edge-cloud computing architecture, which can make full use of the edge server resources in the application module placement problem.Figure5 shows the improved edge computing architecture we propose. Servers in the same area can form clusters and communicate with each other directly with low latency through the Constrained Application Protocol (CoAP) and the Simple Network Management Protocol (SMP) [21]. As shown in Figure 6, the edge servers in the third level have shorter distances between each other and can be regarded as an area. We connect the edge servers in an area and make the data transmitted through these edge servers. In this situation, more data can be processed at the edge of the network. The cloud computing center can process tasks, only if all the edge servers are fully used. Although the processing time will increase in the edge servers, the data transmission time will reduce notably.Figure 5
Improved edge-cloud computing architecture.Figure 6
The mapping relationship of modules of sensor and servers with the module chain.The application modules are placed at servers in the network. And the module chains tied to the sensors reflect the mapping relationship of the modules and servers. As shown in Figure6, modules of the sensor belonging to an application show how the servers to place each module, and the modules are placed at the corresponding servers.


## 3.9. Simulated Annealing Algorithm in Module Placement of Edge Computing

The simulated annealing algorithm is inspired by the phenomenon of solid annealing and usually used to find a good approximation for a global optimum. By choosing a worse solution with a certain probability to find the global optimal solution, the algorithm can be used to solve an NP-hard problem.The input parameters of our algorithm include the device table in the edge computing network and the module chains like Figure6. And the method is shown in Algorithm 1.Algorithm 1: Simulated annealing module placement strategy (SAP).
Input: sensors, edge servers table N, applications A, communication latency between edge servers Ln;Initialization:Set the start temperatureTemp, coolingrate, loop count, End temperature Tend;Start:Generate the initial module placementp_temp;WhileTemp>Tenddo:i=1;Whilei<loop count do:value_temp⟵Evalueate(p_temp);p_new⟵Algorithm2GenerateNewChain(A, p_temp, value_temp);value_new⟵Evalueate(p_new);∆E= value_new – value_temp;if∆E<0then:p_temp = p_new;else ifexp−E/Temp>randthen:p_temp = p_new;end ifi+1;end whileT←T×cooling rate;end whileOutput: module placement p_temp;Algorithm1 is executed according to the following steps:Step 1.
Set the initial temperature (Temp), loop count (C), and termination temperature of the algorithm and generate a random solution. The solution indicates the placement of the modules in the module chains. Figure 6 shows an example of the placement of the chain shown in Figure 1.Step 2.
Evaluate the solution; get the values ofk evaluation. This average latency T and energy consumption E are the optimization objectives in the proposed algorithm. Since the magnitudes of latency and energy consumption are quite different, we make them the same order of magnitude:
(13)VT=e−T,(14)VE=e−E.
The fitness function can be calculated by:(15)Vcurrent=α×VT+β×VE.
The values ofα and β represent the weights of latency and energy in the fitness function, respectively, where 0≤α≤1, 0≤β≤1, and α+β=1. We can change the values of α and β to adjust the optimization goal.
Save this value as the current evaluation valueVcurrent and save the latency of each module chain.Step 3.
Make random perturbation to the module chain that has the maximum latency in the solution. The method is shown in Algorithm2. In this step, the module has a higher possibility to be placed on a higher-level server. Then, we use (15) to calculate the evaluation value Vnew of the new solution.Algorithm 2: Generation method of the new module chain.
Input: applications A, module chains p_temp, Temp;Initialization: l =3;Start: find the worst latency value chain c in p_temp;for all module mi in c do:get a random serversjat the servers no lower than l;ifRamireq<Ramjallocated&&Bwireq<Bwjallocatedthen:placemi on server Sj;if the level of Sjlj`< l then:l = lj``end ifelse:placemi on serverSk at the higher level than Sj.l = lk`end ifend forOutput: placement of module chains on servers p_new;Step 4.
The simulated annealing algorithm can find the global optimal solution. While the new solution is better thanVcurrent, Vcurrent will be updated as Vnew. If Vnew is worse than Vcurrent, the algorithm will be updated as Vnew with the possibility γ. The value of γ will be calculated as follows:
(16)γ=exp−Vnew−VcurrentTemp.
The update ofVcurrent can be expressed as follows:
(17)Vcurrent=Vnewα+Vcurrent1−α,(18)α=1Vcurrent<Vnew∥PVcurremt≥Vnew,γ0Vcurremt≥Vnew.
The value ofα is determined by the values of Vcurrent andVnew, PVcurremt≥Vnew,γ. This means that when Vcurrent is greater thanVnew, it is received with the probability of γ, and the value of a is updated to 1.Step 5.
Repeat Steps3 and 4 until the loop count meets C.Step 6.
Drop the temperature. If the temperature meets the termination temperature, ends the algorithm. Otherwise, proceed with Step3. Assume q is the ratio of temperature dropped. The temperature Temp is reduced as follows:
(19)Temp=Temp×q.


## 4. Simulation and Result

### 4.1. Experimental Environment

This experiment uses iFogSim as the platform for simulating the edge computing environment, which is a toolkit for simulating different computing models based on CloudSim. The analysis of this paper was done on a computer with Intel Core i7 CPU and 8 GB of memory running Windows 10-64 bit.Figures7 and 8 show the applications we deployed in the edge computing network, where the numbers on an edge between two modules represent the computation and the amount of data to be sent. We deployed two kinds of applications to simulate the high computation and low computation applications. The MIPS of modules in the low computation application is within the range of 500-1500, while the MIPS of the modules in high computation application is within the range of 2000-3500. The RAM required of each module ranges from 1000 to 5000, and the bandwidth ranges from 200 to 1000 Hz.Figure 7
The application with high computation deployed in the network.Figure 8
The application with low computation deployed in the network.For server parameter settings, Different kinds of terminal devices are connected to the stochastic edge servers. The CPU capacity of each server in level 3 of the network is in the range of 2800-6000, and the RAM ranges from 5000 to 8000. The bandwidth of each server is in the range of 2000-5000 Hz. We set the CPU speed of to cloud computing center to be 44000; the RAAM is 40000, and the bandwidth is 10000 Hz. In level 3, the communication latency to each server in the same area is in the range of 10-30 ms. The uplink latency of the proxy servers to the cloud is 40 ms, whereas the upload latency of the servers to the proxy servers is 60 ms. We set 8 edge servers in an area, and the parameters of each server are listed in Table2.Table 2
Different numbers of two kinds of application.
CPURAMUp/down bandwidthStatic power/dynamic powerCloud server440004000010000/100001648/1332Proxy server250020001000/10000107.34/83.43Edge server2800-60003000-80005000/10000112.34-143.34/83.43Terminal device100015003000/300087.43/60.43To simulate different situations of edge computation, as shown in Table3, we set 5 different rates for the two types of applications.Table 3
Different numbers of two kinds of application.
Rate 1Rate 2Rate 3Rate 4Rate 5Number of low computation application1010101010Number of high computation application3691215We set the initial temperature of the algorithm to be 15000 and the cooling rate to be 0.9.


### 4.2. Simulation Results

In this section, we evaluate the performance of the proposed method using the iFogSim simulation environment. To prove the efficacy of our proposed module placement algorithm, we compare our algorithm with the following solutions in the literature.Edge-ward placement strategy (EWP): the strategy favors the deployment of application modules close to the edge of the network. Without consideration of the edge servers in an area, the strategy will try to find a server in the path between an IoT device and the cloud data center when the resource of the edge server is insufficient to host all operators of the application [17]Latency Aware Online scheduling strategy (LAO): an online task scheduling strategy of the edge computing system. With the connection of edge servers in an area, the tasks will be processed by the edge server. If the prediction delay is out of the preset delay, the edge server will send the task to the other edge servers in the area by polling. The tasks will be sent to the cloud if all the servers cannot complete the processing within the preset latency [28].EWP algorithm does not consider the case of edge server selection in the same region; LAO only chooses the server with delay as the goal. The SAP algorithm proposed in this paper firstly selects the servers in the same cluster when selecting the servers of tasks. If the computing resources of servers in the cluster cannot meet the requirements of task modules, it sends requests to the cloud server to minimize time and energy consumption.There are two different weights used in our algorithm. One of the weights is 0.7 and 0.3 forα and β, indicating that the primary optimization target of the algorithm is latency. The other weight is 0.3 and 0.7 for α and β, indicating that the primary optimization target of the algorithm is energy consumption.In our experiment, we observe the average latency of applications with different rates of low computation applications and high computation applications in an area. More high computation applications in an area indicate more computational and bandwidth resources required. The energy consumption of the edge servers and the cloud data center can reflect their utilization rate of them. The motivation of our algorithm is to make full use of the edge servers to reduce the high communication latency between the edge servers and the cloud data center with low energy consumption.


### 4.3. Latency Consumption

Figure9 shows the average latency of the applications deployed in the edge computing network. Because the resource required at Rate 1 is limited, all the strategies can process the tasks in the edge servers, and the difference is inconspicuous. With an increase in the number of high computation applications, the average latency increases gradually. It is evident that our algorithm always has low latency than EWP and LAO. Especially the configuration with latency as the main optimization objective, it achieves less average latency than the other comparative algorithms. This is because we connect the edge servers in one area so that more data can be processed at the edge of the network in lieu of the cloud data center. And the procedure to process data in LAO takes more time to schedule what data should be sent. Thanks to the reduction in communication latency and scheduling time, the algorithm we proposed can reduce the average latency by up to 65%.Figure 9
Average latency of the applications deployed in the edge computing network.


### 4.4. Energy Consumption

Figure10 plots the average energy consumption of the edge servers in the area. As can be observed from the figure, the weights 0.3 and 0.7 for α and β do not achieve the least latency but lower energy consumption compared to the other weights. Because LAO does not consider the different power levels of the edge servers, its energy consumption is higher than those of the other algorithms. In Rate 3 to Rate 5, the energy consumption tends to decrease, which means the edge servers in the area are overloaded and should offload more data to the cloud data center.Figure 10
Average energy consumption of servers in an area.Although the average energy consumption of SAP is higher than that of EWP, as shown in Figure11, the proposed method can significantly reduce the energy consumption of the cloud data center with an increase in the number of high computation applications. This is because the algorithm can make full use of the edge servers by considering the different power levels of the servers in the network.Figure 11
Energy consumption in the cloud data center.In comparison to the case of Rate 5, EWP sends too much data to the cloud data center and may congest the network. The cloud receives less data, which helps reduce its energy consumption.All the results above have shown that the proposed strategy is capable of reducing the dependence on the cloud and achieving shorter processing latency and lower energy consumption.


## 4.1. Experimental Environment

This experiment uses iFogSim as the platform for simulating the edge computing environment, which is a toolkit for simulating different computing models based on CloudSim. The analysis of this paper was done on a computer with Intel Core i7 CPU and 8 GB of memory running Windows 10-64 bit.Figures7 and 8 show the applications we deployed in the edge computing network, where the numbers on an edge between two modules represent the computation and the amount of data to be sent. We deployed two kinds of applications to simulate the high computation and low computation applications. The MIPS of modules in the low computation application is within the range of 500-1500, while the MIPS of the modules in high computation application is within the range of 2000-3500. The RAM required of each module ranges from 1000 to 5000, and the bandwidth ranges from 200 to 1000 Hz.Figure 7
The application with high computation deployed in the network.Figure 8
The application with low computation deployed in the network.For server parameter settings, Different kinds of terminal devices are connected to the stochastic edge servers. The CPU capacity of each server in level 3 of the network is in the range of 2800-6000, and the RAM ranges from 5000 to 8000. The bandwidth of each server is in the range of 2000-5000 Hz. We set the CPU speed of to cloud computing center to be 44000; the RAAM is 40000, and the bandwidth is 10000 Hz. In level 3, the communication latency to each server in the same area is in the range of 10-30 ms. The uplink latency of the proxy servers to the cloud is 40 ms, whereas the upload latency of the servers to the proxy servers is 60 ms. We set 8 edge servers in an area, and the parameters of each server are listed in Table2.Table 2
Different numbers of two kinds of application.
CPURAMUp/down bandwidthStatic power/dynamic powerCloud server440004000010000/100001648/1332Proxy server250020001000/10000107.34/83.43Edge server2800-60003000-80005000/10000112.34-143.34/83.43Terminal device100015003000/300087.43/60.43To simulate different situations of edge computation, as shown in Table3, we set 5 different rates for the two types of applications.Table 3
Different numbers of two kinds of application.
Rate 1Rate 2Rate 3Rate 4Rate 5Number of low computation application1010101010Number of high computation application3691215We set the initial temperature of the algorithm to be 15000 and the cooling rate to be 0.9.


## 4.2. Simulation Results

In this section, we evaluate the performance of the proposed method using the iFogSim simulation environment. To prove the efficacy of our proposed module placement algorithm, we compare our algorithm with the following solutions in the literature.Edge-ward placement strategy (EWP): the strategy favors the deployment of application modules close to the edge of the network. Without consideration of the edge servers in an area, the strategy will try to find a server in the path between an IoT device and the cloud data center when the resource of the edge server is insufficient to host all operators of the application [17]Latency Aware Online scheduling strategy (LAO): an online task scheduling strategy of the edge computing system. With the connection of edge servers in an area, the tasks will be processed by the edge server. If the prediction delay is out of the preset delay, the edge server will send the task to the other edge servers in the area by polling. The tasks will be sent to the cloud if all the servers cannot complete the processing within the preset latency [28].EWP algorithm does not consider the case of edge server selection in the same region; LAO only chooses the server with delay as the goal. The SAP algorithm proposed in this paper firstly selects the servers in the same cluster when selecting the servers of tasks. If the computing resources of servers in the cluster cannot meet the requirements of task modules, it sends requests to the cloud server to minimize time and energy consumption.There are two different weights used in our algorithm. One of the weights is 0.7 and 0.3 forα and β, indicating that the primary optimization target of the algorithm is latency. The other weight is 0.3 and 0.7 for α and β, indicating that the primary optimization target of the algorithm is energy consumption.In our experiment, we observe the average latency of applications with different rates of low computation applications and high computation applications in an area. More high computation applications in an area indicate more computational and bandwidth resources required. The energy consumption of the edge servers and the cloud data center can reflect their utilization rate of them. The motivation of our algorithm is to make full use of the edge servers to reduce the high communication latency between the edge servers and the cloud data center with low energy consumption.


## 4.3. Latency Consumption

Figure9 shows the average latency of the applications deployed in the edge computing network. Because the resource required at Rate 1 is limited, all the strategies can process the tasks in the edge servers, and the difference is inconspicuous. With an increase in the number of high computation applications, the average latency increases gradually. It is evident that our algorithm always has low latency than EWP and LAO. Especially the configuration with latency as the main optimization objective, it achieves less average latency than the other comparative algorithms. This is because we connect the edge servers in one area so that more data can be processed at the edge of the network in lieu of the cloud data center. And the procedure to process data in LAO takes more time to schedule what data should be sent. Thanks to the reduction in communication latency and scheduling time, the algorithm we proposed can reduce the average latency by up to 65%.Figure 9
Average latency of the applications deployed in the edge computing network.


## 4.4. Energy Consumption

Figure10 plots the average energy consumption of the edge servers in the area. As can be observed from the figure, the weights 0.3 and 0.7 for α and β do not achieve the least latency but lower energy consumption compared to the other weights. Because LAO does not consider the different power levels of the edge servers, its energy consumption is higher than those of the other algorithms. In Rate 3 to Rate 5, the energy consumption tends to decrease, which means the edge servers in the area are overloaded and should offload more data to the cloud data center.Figure 10
Average energy consumption of servers in an area.Although the average energy consumption of SAP is higher than that of EWP, as shown in Figure11, the proposed method can significantly reduce the energy consumption of the cloud data center with an increase in the number of high computation applications. This is because the algorithm can make full use of the edge servers by considering the different power levels of the servers in the network.Figure 11
Energy consumption in the cloud data center.In comparison to the case of Rate 5, EWP sends too much data to the cloud data center and may congest the network. The cloud receives less data, which helps reduce its energy consumption.All the results above have shown that the proposed strategy is capable of reducing the dependence on the cloud and achieving shorter processing latency and lower energy consumption.


## 5. Conclusions

As an extension of cloud computing, edge computing provides more possibilities to the IoT alongside AI and 5G. In this paper, we proposed a new edge computing architecture with the module chain bound to each sensor and a new module placement integrated with the simulated annealing algorithm. Simulation results were presented to demonstrate the advantages of our proposed method in terms of reducing latency and energy consumption.



---

*Source: 4758677-2021-10-07.xml*