# Enhanced Adaptive Cloudlet Placement Approach for Mobile Application on Spark

Authors: Yiwen Zhang; Kaibin Wang; Yuanyuan Zhou; Qiang He
Journal: Security and Communication Networks
 (2018)

---

## Abstract

The applications of mobile devices are increasingly becoming computationally intensive while the computing capability of the user’s mobile device is limited. Traditional approaches offload the tasks of mobile applications to the remote cloud. However, the rapid growth of mobile devices has made it a challenge for the remote cloud to provide computing and storage capacities with low communication delays due to the fact that the remote cloud is geographically far away from mobile devices. Reducing the completion time of applications in mobile devices through the technical expending mobile cloudlets which are moving collocated with Access Points (APs) is necessary. To address the above issues, this paper proposes EACP-CA (EnhancedAdaptiveCloudletsPlacement approach based onCoveringAlgorithm), an enhanced adaptive cloudlet placement approach for mobile applications in a given network area. We apply the CA (Covering Algorithm) to adaptively cluster the mobile devices based on their geographical locations, the aggregation regions of the mobile devices are identified, and the cloudlet destination locations are also confirmed according to the clustering centers. In addition, we can also obtain the traces between the original and destination locations of these mobile cloudlets. To increase the efficiency, we parallelize CA on Spark. Extensive experiments show that the proposed approach outperforms the existing approach in both effectiveness and efficiency.


---

## Body

## 1. Introduction

The rapid development of the mobile Internet and the Internet of Things has promoted the emergence of various new types of services, which has led to explosive growth in mobile communication traffic over the past few years. Mobile devices have gradually replaced personal computers as one of the main tool, which people can use in daily work, socialization, and entertainment. Simultaneously, the mobile applications are also increasingly becoming computationally intensive [1–3]. These vast amounts of mobile applications accordingly bring huge computing capacity, storage capacity requirements, and low latency requirements. The previous methods allow these mobile devices to directly access the remote cloud (e.g., Amazon) [4–6], deploying all services to the remote cloud which will not only lead to the great increase of the network load and cause a long delay in the network, but also put higher demands on bandwidth and delay performance of network. The remote cloud is far away from its users and the network delay incurred by processing the requirements can be very costly. These above situations are especially intolerable in real-time demand of applications where the rapid response time is vital for users who take the mobile devices.In order to cope with the long latency problem, recent works have proposed the cloudlets with strong computing and storage capacity, which are typically collocated at the AP in a network and can be accessed by users via wireless connection [3, 7, 8]. The critical advantage of the cloudlets is that the cloudlets can be deployed physical proximity close to users which can shorten the transmission latency and improve the user experience of using interactive applications.Although there is an increasing number of researches in mobile cloudlet offloading technology [9–11], fewer researches about how to place cloudlets in a given network region are conducted [3, 7, 12–14]. It is necessary to pay attention to how cloudlets should be placed in a given network since the suitable cloudlets placements contribute to enhancing the cloud service for dynamic context-aware mobile applications. The price of the cloudlets is so expensive that the number of the cloudlets is limited, so we should maximize the utilization of cloudlets by a suitable cloudlets placement. Some current researches pay attention to the cloudlets placement to alleviate the low utilities of cloudlets [3, 12–14], the cloudlets placement in their studies are fixed, but, in practice, users are constantly moving. Fixed-placed cloudlets cannot maintain efficiency in responding to the application requirements for the constant mobile devices. In order to explain this problem more vividly, we use Figure 1 to illustrate the issue. Figure 1 presents an example with many mobile devices and a cloudlet. In Figure 1(a), those mobile devices with GPS location are randomly distributed in the scenic spot and a cloudlet with AP being in positionA. Those mobile devices are constantly moving over time. And at time t′, the crowd moves close to positionB. If the cloudlet is still deployed at positionA, the coverage range of cloudlet is so small which leads to the low utility of the cloudlet. But if the cloudlet moves to positionB described in Figure 1(b), the scope of cloud coverage has increased significantly. Therefore, to improve the performance of the cloudlet service in the dynamic scenario, it is significant to propose an enhanced adaptive mobile cloudlets placement according to practical distributions of mobile devices.Figure 1
Motivation example of adaptive cloudlet placement.To address the above issue, this paper proposes EACP-CA (EnhancedAdaptiveCloudletsPlacement approach based onCoveringAlgorithm), a novel approach for cloudlets placement. Given a known mobile devices activity area, according to the characteristics of the data and being independent of the initial centers [8, 15], EACP-CA first employs CA with “blind” features to adaptively partition mobile devices into clusters based on the physical distance between their positions. Then we adjust the central positions obtained by CA through the obtained graph path. Next, we executeconfirmation of the center positions operation and get the desired cloudlets central positions according to the distribution of the mobile devices. We also need to obtain the pair of the original mobile cloudlet positions and the destination position of them. Finally, we conduct the enhanced adaptive cloudlets placement approach to finish the mobile cloudlets placement. To improve the efficiency, we parallelize CA on Spark.The major contributions of this paper are as follows:(1)
We employ the adaptive clustering algorithm CA to cluster the mobile devices in given regions. CA based on the quotient space theory has “blind” features without determining the number of clusters in advance; the algorithm can automatically identify the number of clusters based on the characteristics of the data and is independent of the initial centers. And we parallelize the CA on Spark to increase the efficiency of EACP-CA in processing big data.(2)
We implement the enhanced adaptive cloudlets placement and obtain the traces of mobile cloudlets any distribution of the mobile devices with changing over time.(3)
We conduct extensive experiments to comprehensively compare EACP-CA with existing k-means based approach.This paper is organized as follows. Section2 reviews the related work. Section 3 overviews the preliminary knowledge. Section 4 introduces enhanced adaptive cloudlet placement approach for mobile applications. Section 5 presents the experimental results and analysis, and Section 6 concludes this paper.


## 2. Related Work

Mobile cloud computing provides information technology service environment and cloud computing capabilities within the radio access network closest to the user's mobile devices, aiming to further reduce latency, enhance network operating efficiency, boost service distribution, and improve user experience, which can also increase the computing capacity of mobile devices by offloading the workload to clouds [1, 2, 9, 16–19]. Many kinds of researches have been conducted on mobile cloud computing [2, 16, 20–22], but most of them are about remote clouds which are physically far away from the uses and cloudlet offloading technology. The remote clouds lead to a long latency, which is negative for improving the user experience and the performance of cloud services [4, 5]. In view of the above issues, researchers present the cloudlets with computing and storage resource-rich which can deploy at APs in a network [3, 7]. The cloudlets are deployed physically close to the users and act as offloading destinations of the mobile user which can significantly short the response time for the users’ requirements and also can reduce the energy consumption of mobile devices.There are some studies investigated the cloudlets. To name a few, Jia et al. [3] study the cloudlet placement and mobile user allocation to the cloudlets at user dense region of the wireless metropolitan area network (WMAN) and assign mobile users to the placed cloudlets while balancing their workload. Xu et al. [12] focused the cloudlet placement problem in a large-scale WMAN consisting of many wireless APs, in which capacitated cloudlets need to find the best deployment locations within a given set of candidate locations in WMAN. The objective is to minimize the average access delay between the mobile users and the activated cloudlets serving the users. Ma et al. [13] propose a New Heuristic Algorithm (NHA) and a Particle Swarm Optimization (PSO) algorithm for the delaying problem. In the above approaches, cloudlets are fixed in the placement, which cannot maintain efficiency in response to the requirements of applications for frequently moving devices. There are some researchers proposed the movable cloudlets to enhance the performance of the cloud service with the mobile users. Xiang et al. [7] propose self-adaptive edge cloud placement based on the locations of mobile applications. The core idea of the method is to maximize the number of mobile devices that are covered by the known active area of the edge cloud. They use the k-means algorithm to conduct the clustering process. However, k-means clustering algorithm has some drawbacks that the number of clustersk cannot be easily determined, and the clustering results heavily rely on the initial centers of random selection. And the selection of the initial center has a significant impact on the final clustering result and is easily disturbed by outliers [15, 23, 24].In this paper, we propose EACP-CA, a novel approach for enhanced adaptive cloudlets placement. EACP-CA efficiently addresses the limitations and issues of most existing clustering approaches with a novel covering-based clustering technique. The CA algorithm we employed has “blind” features, without determining the number of clusters in advance, which can automatically identify the number of clusters based on the characteristics of the data and is independent of the initial centers. And EACP-CA can efficiently mitigate the issue of data scalability on Spark.


## 3. Preliminaries

In this section, we formally define the problem accurately to facilitate further introduction on enhanced adaptive cloudlet placement for mobile applications. Before conducting the introduction, we summarize the notions used throughout this paper in Table1 to simplify the discussion.Table 1
Mathematical notation.
Symbol Explanation A Denotes the set of points in mobile devices activity area,A=x,y∣0≤x≤W,0≤y≤H M D Denotes the set of mobile devices,D={d1,d2,…,dN} M D P Denotes the set of mobile devices positions d n Denotes thenth (1≤n≤N) mobile device in D d n p ( t ) Denotes the position of dn at time t,dnp(t)=(dnpt_x,dnpt_y), where dnpt_x and dnpt_y represents the latitude and longitude of the location L Denotes the set of the cloudlets,L=l1,l2,…,lN l m Denotes themth cloudlet C L Denotes the set of the central position of the cloudlets l m p ( t ) Denotes the central position oflm at time t,lmp(t)=(lmpt_x,lmpt_y) A P Denotes the set of the Aps,AP={ap1,ap2,…apm} r m Denotes the converage radius forlm d c _ l m p ( t ) Denotes the mobiles devices collection oflmp at timet,dc_lmp(t)=dnpt∣dismdpnpt,lmpt≤r,1≤≤N d i s m d p n , l m p ( t ) Denotes the Euclidean distance betweenmdpnp(t) and lmp(t), dismdpnp(t),lmp(t)=(mdpnpt_x-lmpt_x)2+(mdpnpt_y-lmpt_y)2 d c _ c p i Denotes the mobile devices collection ofcpi σ Denotes the density threshold for cloudlet placement judgment A N ( t ) Denotes the number of covered mobile devices by all cloudlets d c _ l m p ( t ′ ) Denotes the mobile device collection oflmp at time t′ V Denotes the available positions that cloudlets can only stay v u Denotes theuth available position that cloudlets can stay E Denotes the edges between adjacent position inV e u v Denotes the edge between two APsvu and vv W Denotes the weight of all cloudlet available positions G Denotes the paths graph inA, G={E,V,W} p ( x , y ) Denotes the coordinates of positionMost existing studies in mobile edge computing focus on the limited of computing capacity, storage, and energy savings of mobile devices by offloading high-complexity and computing-intensive tasks from mobile devices to remote clouds [2, 9, 10]. However, the approach of offloading computing tasks to the cloud computing center not only brings about a large amount of data transmission and increases the network load, but also increases the transmission delay, which has a certain impact on the delay-sensitive service and the user experience [15]. Therefore, to effectively solve the requirements of high bandwidth and low latency brought about by the rapid development of the mobile Internet and the Internet of Things, the mobile edge computing has received extensive attention from the academic community and the industry. The cloudlets play an important role in the mobile edge computing which can significantly enhance the performance of mobile devices and meet the mobile users’ response time requirements simultaneously, as shown in Figure 1. The mobile cloud framework consists of three main parts presented in Figure 2. Part 1 is mobile device clients, Part 2 is cloudlets, and Part 3 is the remote cloud. The mobile device clients can directly access the cloud service through the APs or can connect to the network through the wireless network. What is more, there is also a remote cloud which can be accessed from APs through the Internet. When the cloudlets cannot meet the request of the mobile devices, some computationally intensive tasks and data can be offloaded to the remote cloud for processing. Mobile devices can quickly access nearby cloudlets through APs to obtain cloud storage and cloud computing resources, so cloudlets can help reduce the access latency.Figure 2
The mobile cloud framework.Effectively dealing with the cloudlet placement problem in WMAN consisting of many APs can contribute to enhancing the cloud services for dynamic mobile computationally intensive applications and improve the user experience. In this paper, we apply a rectangle activity area to place the cloudlets. In addition, other shaped areas can also be split by multiple different size rectangles.


### 3.1. Cloudlet Placement Strategy

If cloudletlm with the central position p(x,y) is providing service to the users with the mobile devices at timet, the number of the mobile devices covered by lm at timet should meet the condition that dc_lmp(t)≥σ. Our goal is to find optimal cloudlet placement inA and maximize the total number of covered mobile devices which is calculated by the following objective function:(1)ANt=⋃m=1Mdc_lmptAssume cloudlet lm is placed at p(x,y) at time t, and, in the time range (t,t′], the mobile devices in A move randomly. The place position of cloudlet lm at timet may not suitable for distribution of mobile devices after moving at time t′. In order to maintain the cloudlets working efficiently, we should propose a cloudlet movement strategy as the move reference for the cloudlets.


### 3.2. Cloudlet Movement Strategy

After mobile devices have moved at timet′, if the cloudlet lm is still placed at the position p(x,y) at the timet, the mobile devices’ collection of position p(x,y) at time t′ is denoted as dc_lmp(t′), and another place position p′(x′,y′) for cloudlet lm at time t′ is obtained by adaptive cloudlet placement approach, and satisfying the cloudlet placement strategy is denoted as dc_lmp′t′. If meet the condition that dc_lmp′t′≥dc_lmpt′ is met, and there are no other cloudlets placing around p′ at time t′ within radiusr, cloudlet lm will move from p(x,y) to p′(x′,y′).


## 3.1. Cloudlet Placement Strategy

If cloudletlm with the central position p(x,y) is providing service to the users with the mobile devices at timet, the number of the mobile devices covered by lm at timet should meet the condition that dc_lmp(t)≥σ. Our goal is to find optimal cloudlet placement inA and maximize the total number of covered mobile devices which is calculated by the following objective function:(1)ANt=⋃m=1Mdc_lmptAssume cloudlet lm is placed at p(x,y) at time t, and, in the time range (t,t′], the mobile devices in A move randomly. The place position of cloudlet lm at timet may not suitable for distribution of mobile devices after moving at time t′. In order to maintain the cloudlets working efficiently, we should propose a cloudlet movement strategy as the move reference for the cloudlets.


## 3.2. Cloudlet Movement Strategy

After mobile devices have moved at timet′, if the cloudlet lm is still placed at the position p(x,y) at the timet, the mobile devices’ collection of position p(x,y) at time t′ is denoted as dc_lmp(t′), and another place position p′(x′,y′) for cloudlet lm at time t′ is obtained by adaptive cloudlet placement approach, and satisfying the cloudlet placement strategy is denoted as dc_lmp′t′. If meet the condition that dc_lmp′t′≥dc_lmpt′ is met, and there are no other cloudlets placing around p′ at time t′ within radiusr, cloudlet lm will move from p(x,y) to p′(x′,y′).


## 4. Enhanced Adaptive Cloudlet Placement Approach for Mobile Applications

The placement of the cloudlets has a significant impact on the resource utilization of the cloudlets. Inappropriate placement of cloudlets can cause the severe imbalance in the edge cloud load. Some cloudlets are overloaded, while others are underloaded or even idled and reducing the mobile users’ response time requirements.To obtain the proper cloudlet placement, now we introduce our main approach to the cloudlet placement. The enhanced adaptive cloudlet placement consists of three stages. Stage1 performs the parallel CA clustering algorithm to obtain the central positions of mobile devices gathering place. Stage 2 confirms the cloudlet locations. Stage 3 realizes the adaptive cloudlet placement. The three stages are discussed in detail as follows.Stage 1.
We observe that mobile devices-dense regions ofA areas are suitable to place the cloudlets, which means that cloudlets are situated close to a large number of devices and can reduce the average network latency between mobile devices and cloudlets. Therefore, we propose a clustering algorithm named CA to adaptive identify the central positions of device gathering place. Algorithm 1 presents the pseudocode for the CA algorithm and we use Table 2 to simply introduce these functions in Algorithm 1. The detailed description of these functions is in Section 3.3 in [23]. In order to better illustrate the effectiveness, we also discuss the time complexity of the CA.Table 2
Explanations of functions.
Functions Explanation get_center(Cu) Denotes a function has the function of obtaining the center of the data setCu. The specific acquisition process of the center of the circle is to calculate the data point closest to the center of gravity of the data set Cu. get_weight_radius(c,Cu) Denotes a function has the function of obtaining the weighted radius based on centerc and data set Cu. get_covering(c,r,Cu) Denotes a function has the function of obtaining the centroids of the current spheres continually according to the obtained center and radius and obtain new clusters until the number of clusters in the data points does not increase. get_centroid(Cform) Denotes a function has the function of obtaining the center of gravity of data setCu. Split Operation Denote a function has the function of combing the most similar pair of clusters into a new cluster. Merge Operation Denote a function has the function of splitting the clusters with more data points.Algorithm 1:CA (MDP).
Input: M D P Output: Results of parallel covering with granularity analysis–A set of clusters CP={CP1,CP2,…} Begin (1)center c = null (2)SetCu=MDP (3)do (4) center c←get_center(Cu) (5) radius r← get_weight_radius(c,Cu) (6) Covering Cform = get_covering(c,r,Cu) (7) c ← get_centroid(Cform) (8) r← get_weight_radius(c,Cu) (9) Covering Clast = get_covering(c,r,Cu) (10) whileClast.subtractByKey(Cform) > 0 (11) Cform←Clast (12) c ← get_centroid(Cform) (13) r← get_ radius_centroid(c,Cu) (14) Clast = get_covering(c,r,Cu) (15) end while (16) while(Cu≠∅) (17) Do Split Operation (18) Do Merge Operation (19) return CP=CP1,CP2,… End


### 4.1. Time Complexity Analysis of the Algorithm1

In Algorithm1, the computational complexity of line (5) isO(n) because datasetMDP contains a maximum ofn points. Similarly, the computational complexities of lines (5) and (6) are alsoO(n), and those of lines (7), (8), and (9) are alsoO(n) because the number of clusters is smaller thann. Lines (10)-(15) will be repeated until the data points in the cluster do not change. Lines (3)-(15) must also be repeated until all of the data points inMAP are covered, and the number of repetitionsnum_C is much smaller thann. In line (3), the radius of a cluster is the average distance between the center of the cluster and all of the data points that are not covered by any clusters. On average, each newly created cluster covers half of the uncovered data points, and the computational complexity isO(log⁡n). In line (17), the computational complexity isO(p) because there is a maximum ofp clusters after the initial covering process. Similarly, the computational complexity of line (18) isO(p) because there is a maximum of p clusters. The number of clusters is much smaller thann. Thus, the computational complexity of Algorithm 1 isO(n) ×O(log⁡n) +O(p) =O(nlog⁡n).Therefore, we obtain the central positions of mobile devices gathering place through the CA clustering algorithm.Considering the security and efficiency of path researching in adaptive cloudlet placement, the whole cloudlets can only place to APs [25]. Then we employ the path graphG to adjust the obtained central positions and generate moving traces of the mobile cloudlets. Algorithm 2 presents the pseudocode for the adjusting of the central positions obtained by CA.Algorithm 2:Center position adaptive identification (MDP, V).
Input: M D P, V Output: A set of mobile device central positions CCP Begin (1) centers ← CA(MD) (2)  CP←∅ (3) fori = 1 to k (4) do (5) Pos←dis(cpi,vj)vjargmin ( j=1 to U ) (6) add Pos to CCP (7) end for (8) return CCP EndStage 2.
We obtained several mobile device central positions after performing Stage1. Then we will conduct the confirmation operation to filter the undesired center positions. The confirmation of center positions operation is introduced as follows.


### 4.2. Confirmation of Center Positions Operation

Through Stage1, we get the mobile device central positions setCCP. For each center position cpi inCCP, the confirmation of center positions operation filters the mobile devices that the distances between cpi and each mobile device position are shorter than radiusr. And if cpi center position contains more than σ mobile devices, then add the cpi center position to the set of cloudlet central position denoted byCP. After the confirmation operation, we get the set of cloudlet central positionCP. We use the following formula for a brief explanation.(2)CP=cpi∣cpi∈CCPanddccpi≥σStage 3.
After the above confirmation operation, we get the desired mobile devices central positions. According to the distribution of the mobile devices inA, if each cloudlet moves to the center position which is surrounded by dense mobile devices, these cloudlets will achieve high utilities. Therefore we will propose a method to choose a suitable center position inCP as its destination position. Assuming we have already known the previous cloudlets, we describe the selection strategy for cloudlets location to introduce the selection of each cloudlet. For the subproblem of the cloudlet selection, a straightforward idea is to greedily select the cloudlet with the minimum distance. The center position selected by each cloudlet is according to the distance between cloudlet previous location and the mobile devices central positions.


### 4.3. Locations Selection Mechanism

Supposing that we already know the original positions and the destination positions of cloudlets, i.e., the central positions, the cloudlets denoted byL={l1,l2,…,lm} and the original positions denoted by OCL={ocl1,ocl2,…,oclm}, the destination positions of cloudlets are obtained by the above stages which are denoted by CP={cp1,cp2,…,cpm}. We compute all the distances betweencli andcpj, and get distance setOCP={ocp1,ocp2,…, ocpm∣ocpi=(cp1,…,cpp…,cpq,…,cpm) where 1≤p≤q≤m and dis(ocli,cpp)<dis(ocli,cpq)}. While not all cloudlets have selected a central position, we addocli to the intermediate seti_cj thatcpj is the nearest central position ofli inocpi, and then for eachi_cj that is not empty. If eachcpi corresponding toi_cj have not selected a cloudlet or a nearest cloudlet selectedcpi this time, we obtaincpi’ nearestlj ini_cu andcpi selectsoclj. If there are some existing cloudlets ini_cj are not selected, we delete thecpi fromocpa thatocla ini_cj is not selected. We repeat those operations until all cloudlets have selected a central position. In order to explain the locations select mechanism process visually, we use a specific example to explain which are presented in Figure 3.Figure 3
The example of locations selection mechanism.As we can see from Figure3, there are 4 cloudlets,l1,l2,l3,l4, 4 original cloudlet positions,ocl1,ocl2,ocl3,ocl4, and 4 central positions,cp1,cp2,cp3,cp4. Forocp1,ocp2,ocp3,and ocp4, we, respectively, get ocp1 = (cp1,cp2,cp4,cp3),ocp2= (cp4,cp1,cp2,cp3),ocp3= (cp2,cp1,cp3,cp4), andocp4= (cp4,cp3,cp1,cp2). Now, each of cloudlets does not select acp. For all cloudlets, we figure out thati_c=i_c1=ocl1,i_c2=ocl3,i_c4=ocl2,ocl4. Then we will deal with the un-emptyi_ci. For each cloudlet ini_c1,cp1 has not selected a cloudlet, we get thecp1’ nearest cloudletocl1 ini_c1 andcp1 selectsocl1. For each cloudlet ini_c2,cp2 has not choose a cloudlet, we obtain thecp2’ nearest cloudletocl3 ini_c2, andcp2 selectsocl3. For each cloudlet ini_c4,cp4 has not selected a cloudlet, we acquire thecp4’ nearest cloudletocl2 ini_c4 andcp4 choosesocl2,ocl4 ini_c4 is not selected. So we delete thecp4 inocp4, now theocp4= (cp3,cp1,cp2). We can find thatocl4 is still not selected acp, so we will repeat these operations. For each cloudlet inOCL which has not selected acp, we come to the updated i_c={i_c1=ocl1,i_c2=ocl3,i_c3=ocl4,i_c4=ocl2}. For each cloudlet ini_c1,cp1’ nearest cloudletocl1 choosescp1, we obtain thecp1’ nearest cloudletocl1 ini_c1 andcp1 selectsocl1. For each cloudlet ini_c2,cp2’ nearest cloudletocl3 choosescp2, we get thecp2’ nearest cloudletocl3 ini_c2 andcp2 selectsocl3. For each cloudlet ini_c3,cp3 has not choose acp, we acquire thecp3’ nearest cloudletocl4 ini_c3 andcp3 selectsocl4. For each cloudlet ini_c4,cp4’ nearest cloudletocl2 choosescp4, we get thecp4’ nearest cloudletocl2 ini_c2 andcp4 choosesocl2. So far, all the cloudlets have selected acp.After the selection, we will employ the enhanced adaptive cloudlet placement approach to obtain the moving trace of each cloudlet. As introduced above, the previous cloudlet locations and the destination positions of all cloudlets all belonged toV. Consequently, the problem of the generation of moving trace can transform to the shortest path problem. We use the Dijkstra algorithm for generation of moving trace and then the moving traces will be transmitted to corresponding cloudlet moving. The ultimate overall process of enhanced cloudlets placement is presented in Algorithm 3.Algorithm 3:Enhanced adaptive cloudlets placement (G).
Input: G Output: The moving trace of all cloudlets Begin (1) fort = 1 to tmax (2)do (3) CCP←Algorithm2(MDP, V) (4) CP←filteringCCP through Confirmation of center positions operation (5) (ocli∈OCL,ocliselectedcps)←Locations selection mechanism (6) fori = 1 to OCL (7) do (8) ifli have selected a cpthen (9) shortest trace trai from ocli to its selected cp←Dijkstra algorithm (G,li) (10) transmit trai as the moving description to li (11) end if (12) end for (13) end for End


## 4.1. Time Complexity Analysis of the Algorithm1

In Algorithm1, the computational complexity of line (5) isO(n) because datasetMDP contains a maximum ofn points. Similarly, the computational complexities of lines (5) and (6) are alsoO(n), and those of lines (7), (8), and (9) are alsoO(n) because the number of clusters is smaller thann. Lines (10)-(15) will be repeated until the data points in the cluster do not change. Lines (3)-(15) must also be repeated until all of the data points inMAP are covered, and the number of repetitionsnum_C is much smaller thann. In line (3), the radius of a cluster is the average distance between the center of the cluster and all of the data points that are not covered by any clusters. On average, each newly created cluster covers half of the uncovered data points, and the computational complexity isO(log⁡n). In line (17), the computational complexity isO(p) because there is a maximum ofp clusters after the initial covering process. Similarly, the computational complexity of line (18) isO(p) because there is a maximum of p clusters. The number of clusters is much smaller thann. Thus, the computational complexity of Algorithm 1 isO(n) ×O(log⁡n) +O(p) =O(nlog⁡n).Therefore, we obtain the central positions of mobile devices gathering place through the CA clustering algorithm.Considering the security and efficiency of path researching in adaptive cloudlet placement, the whole cloudlets can only place to APs [25]. Then we employ the path graphG to adjust the obtained central positions and generate moving traces of the mobile cloudlets. Algorithm 2 presents the pseudocode for the adjusting of the central positions obtained by CA.Algorithm 2:Center position adaptive identification (MDP, V).
Input: M D P, V Output: A set of mobile device central positions CCP Begin (1) centers ← CA(MD) (2)  CP←∅ (3) fori = 1 to k (4) do (5) Pos←dis(cpi,vj)vjargmin ( j=1 to U ) (6) add Pos to CCP (7) end for (8) return CCP EndStage 2.
We obtained several mobile device central positions after performing Stage1. Then we will conduct the confirmation operation to filter the undesired center positions. The confirmation of center positions operation is introduced as follows.


## 4.2. Confirmation of Center Positions Operation

Through Stage1, we get the mobile device central positions setCCP. For each center position cpi inCCP, the confirmation of center positions operation filters the mobile devices that the distances between cpi and each mobile device position are shorter than radiusr. And if cpi center position contains more than σ mobile devices, then add the cpi center position to the set of cloudlet central position denoted byCP. After the confirmation operation, we get the set of cloudlet central positionCP. We use the following formula for a brief explanation.(2)CP=cpi∣cpi∈CCPanddccpi≥σStage 3.
After the above confirmation operation, we get the desired mobile devices central positions. According to the distribution of the mobile devices inA, if each cloudlet moves to the center position which is surrounded by dense mobile devices, these cloudlets will achieve high utilities. Therefore we will propose a method to choose a suitable center position inCP as its destination position. Assuming we have already known the previous cloudlets, we describe the selection strategy for cloudlets location to introduce the selection of each cloudlet. For the subproblem of the cloudlet selection, a straightforward idea is to greedily select the cloudlet with the minimum distance. The center position selected by each cloudlet is according to the distance between cloudlet previous location and the mobile devices central positions.


## 4.3. Locations Selection Mechanism

Supposing that we already know the original positions and the destination positions of cloudlets, i.e., the central positions, the cloudlets denoted byL={l1,l2,…,lm} and the original positions denoted by OCL={ocl1,ocl2,…,oclm}, the destination positions of cloudlets are obtained by the above stages which are denoted by CP={cp1,cp2,…,cpm}. We compute all the distances betweencli andcpj, and get distance setOCP={ocp1,ocp2,…, ocpm∣ocpi=(cp1,…,cpp…,cpq,…,cpm) where 1≤p≤q≤m and dis(ocli,cpp)<dis(ocli,cpq)}. While not all cloudlets have selected a central position, we addocli to the intermediate seti_cj thatcpj is the nearest central position ofli inocpi, and then for eachi_cj that is not empty. If eachcpi corresponding toi_cj have not selected a cloudlet or a nearest cloudlet selectedcpi this time, we obtaincpi’ nearestlj ini_cu andcpi selectsoclj. If there are some existing cloudlets ini_cj are not selected, we delete thecpi fromocpa thatocla ini_cj is not selected. We repeat those operations until all cloudlets have selected a central position. In order to explain the locations select mechanism process visually, we use a specific example to explain which are presented in Figure 3.Figure 3
The example of locations selection mechanism.As we can see from Figure3, there are 4 cloudlets,l1,l2,l3,l4, 4 original cloudlet positions,ocl1,ocl2,ocl3,ocl4, and 4 central positions,cp1,cp2,cp3,cp4. Forocp1,ocp2,ocp3,and ocp4, we, respectively, get ocp1 = (cp1,cp2,cp4,cp3),ocp2= (cp4,cp1,cp2,cp3),ocp3= (cp2,cp1,cp3,cp4), andocp4= (cp4,cp3,cp1,cp2). Now, each of cloudlets does not select acp. For all cloudlets, we figure out thati_c=i_c1=ocl1,i_c2=ocl3,i_c4=ocl2,ocl4. Then we will deal with the un-emptyi_ci. For each cloudlet ini_c1,cp1 has not selected a cloudlet, we get thecp1’ nearest cloudletocl1 ini_c1 andcp1 selectsocl1. For each cloudlet ini_c2,cp2 has not choose a cloudlet, we obtain thecp2’ nearest cloudletocl3 ini_c2, andcp2 selectsocl3. For each cloudlet ini_c4,cp4 has not selected a cloudlet, we acquire thecp4’ nearest cloudletocl2 ini_c4 andcp4 choosesocl2,ocl4 ini_c4 is not selected. So we delete thecp4 inocp4, now theocp4= (cp3,cp1,cp2). We can find thatocl4 is still not selected acp, so we will repeat these operations. For each cloudlet inOCL which has not selected acp, we come to the updated i_c={i_c1=ocl1,i_c2=ocl3,i_c3=ocl4,i_c4=ocl2}. For each cloudlet ini_c1,cp1’ nearest cloudletocl1 choosescp1, we obtain thecp1’ nearest cloudletocl1 ini_c1 andcp1 selectsocl1. For each cloudlet ini_c2,cp2’ nearest cloudletocl3 choosescp2, we get thecp2’ nearest cloudletocl3 ini_c2 andcp2 selectsocl3. For each cloudlet ini_c3,cp3 has not choose acp, we acquire thecp3’ nearest cloudletocl4 ini_c3 andcp3 selectsocl4. For each cloudlet ini_c4,cp4’ nearest cloudletocl2 choosescp4, we get thecp4’ nearest cloudletocl2 ini_c2 andcp4 choosesocl2. So far, all the cloudlets have selected acp.After the selection, we will employ the enhanced adaptive cloudlet placement approach to obtain the moving trace of each cloudlet. As introduced above, the previous cloudlet locations and the destination positions of all cloudlets all belonged toV. Consequently, the problem of the generation of moving trace can transform to the shortest path problem. We use the Dijkstra algorithm for generation of moving trace and then the moving traces will be transmitted to corresponding cloudlet moving. The ultimate overall process of enhanced cloudlets placement is presented in Algorithm 3.Algorithm 3:Enhanced adaptive cloudlets placement (G).
Input: G Output: The moving trace of all cloudlets Begin (1) fort = 1 to tmax (2)do (3) CCP←Algorithm2(MDP, V) (4) CP←filteringCCP through Confirmation of center positions operation (5) (ocli∈OCL,ocliselectedcps)←Locations selection mechanism (6) fori = 1 to OCL (7) do (8) ifli have selected a cpthen (9) shortest trace trai from ocli to its selected cp←Dijkstra algorithm (G,li) (10) transmit trai as the moving description to li (11) end if (12) end for (13) end for End


## 5. Experience Evaluation

In this section, we present the performance evaluation of our proposed EACP-CA approach. And we also experimentally compare our proposed approach with k-means based approach.The Spark cluster used to implement CA is built on a cluster with three connected nodes. Master/Slave is ThinkCentre M8500t-N000 Intel(R) Core(TM) i7-4790 CPU 3.60GHZ, 4cores, 8CPUs, DDR3 1600MHz SDRAM; 1 disk on the master and 2 disks on the slave: 1TB, 7.2K RPM SATA Hard Drive.


### 5.1. Experimental Setup

The experiments are conducted on the randomly generated location datasets deferring to the Gaussian distribution which can better simulate real-world applications. The parameters of Gaussian distribution used for generating location datasets are illustrated in Table3, whereμ andσ represent mean and standard deviation, respectively. 200, 300, and 400 represent the number of mobile devices. We will also introduce the parameters used in our experiments. The shape of mobile device activity area A is set to square and the ranges of x-axis and y-axis of this area are both in [0m,180m]. The locations of mobile device are randomly generated and distributed in A. The numbers of the mobile devices are moderate values of N∈{200,300,400}. We set the density threshold σ for cloudlet placement judgment as 30, the coverage radius for cloudlet as 30m, and the time of period of experiments t as 30 minutes. We change the number of APs M from 1 to 7. This way, we comprehensively evaluate EACP-CA’s ability to handle datasets with different characteristics in various application scenarios.Table 3
The parameters of Gaussian distribution.
Devices 200(μ, σ) 300(μ, σ) 400(μ, σ) Fixed devices (30,25),(50,16),(110,18),(150,19) (30,25),(50,16),(110,18),(150,19) (30,25),(50,16),(110,18),(150,19) Moving devices oft0 (60,19),(80,13),(150,25),(140,30) (60,22),(65,20),(130,30),(140,22) (55,35),(40,40),(110,15),(130,30) Moving devices oft1 (55,28),(60,15),(150,25),(120,30) (60,22),(65,20),(130,30),(140,22) (55,35),(40,40),(110,40),(130,30) Moving devices oft2 (60,19),(80,15),(150,25),(150,30) (60,22),(65,20),(130,30),(140,22) (55,35),(40,40),(110,40),(130,30)


### 5.2. Performance Evaluation and Comparison

In this section, we will evaluate the performance of our proposed approach and compare it with k-means based approach through the number of movable cloudlets covered mobile devices.In order to intuitively display the distributions of mobile devices and cloudlets inA, we show three sequential record instances, i.e., t0, t1, and t2 in our experiments. The different times distributions of mobile devices and cloudlets are illustrated in Figure 4. Figure 4(a) describes the distributions at time t0. And at time t1, since the positions of the mobile devices are not changed significantly, there is no corresponding change in the locations of the mobile cloudlets, as we can see in Figure 4(b). But at time t2, the distribution of mobile devices has changed greatly and we can also find that the two cloudlets move to new locations illustrated in Figure 4(c).Figure 4
Distributions of mobile devices and cloudlets att0, t1, and t2.
(a)
t 0 (b)
t 1 (c)
t 2We investigate the performance of our approach and k-means based approach with different cloudlet numbers. We simulate to generate three datasets, which include 200, 300, and 400 mobile devices. The experimental results are shown in Figures5, 6, and 7 demonstrating that our approach outperforms k-means based approach. Figure 5 presents the results for the dataset with 200 mobile devices. Figure 5(a) shows the coverage value by all cloudlets through executing our EACP-CA approach and k-means based approach, while Figure 5(b) shows the average utilization value of each cloudlet inL. And the experimental results for datasets with 300 mobile devices and 400 mobile devices which are shown in Figures 6 and 7, respectively, are the same as the experimental results of dataset with 200 mobile devices. Figures 6(a) and 7(a) show the coverage value by all cloudlets through executing our EACP-CA approach and k-means based approach for the datasets with 300 mobile devices and 400 mobile devices, respectively, while Figures 6(b) and 7(b) show the average utilization value of each cloudlet inL.Figure 5
Comparison of performance with EACP-CA and k-means (number of mobile devicesN = 200).
(a)
Coverage value comparison (b)
Average utilization value comparisonFigure 6
Comparison of performance with EACP-CA and k-means (number of mobile devicesN = 300).
(a)
Coverage value comparison (b)
Average utilization value comparisonFigure 7
Comparison of performance with EACP-CA and k-means (number of mobile devicesN = 400).
(a)
Coverage value comparison (b)
Average utilization value comparisonThe experimental results illustrated in Figures5, 6, and 7 show that EACP-CA is better than k-means based approach because both the coverage value and average utilization of each cloudlet within different cloudlet numbers obtained by EACP-CA are higher than k-means based approach. The experimental results show that, with the rising number of cloudlets, the coverage value obtained by EACP-CA and k-means based approach also increases with the fixed number of mobile devices but becomes less significant. This is caused by the fixed number of mobile devices and the increased number of cloudlets, because, through performing the clustering algorithm, the dense mobile devices are covered by many cloudlets and the remained discrete mobile devices are also covered by another cloudlet which leads decreasing of the average utilization of each cloudlet. Therefore, we can find that the coverage value is impacted by the number of cloudlets while the number of mobile devices is fixed. With the growing number of cloudlets, the average utilization of each cloudlet is increasing at the beginning and then begins to decrease again. Simultaneously, we can also apply the average utilization value of cloudlets to select a suitable number of cloudlets. We can obtain the appropriate number of cloudlets when the average utilization value of cloudlets and the number of users covered become lager.


## 5.1. Experimental Setup

The experiments are conducted on the randomly generated location datasets deferring to the Gaussian distribution which can better simulate real-world applications. The parameters of Gaussian distribution used for generating location datasets are illustrated in Table3, whereμ andσ represent mean and standard deviation, respectively. 200, 300, and 400 represent the number of mobile devices. We will also introduce the parameters used in our experiments. The shape of mobile device activity area A is set to square and the ranges of x-axis and y-axis of this area are both in [0m,180m]. The locations of mobile device are randomly generated and distributed in A. The numbers of the mobile devices are moderate values of N∈{200,300,400}. We set the density threshold σ for cloudlet placement judgment as 30, the coverage radius for cloudlet as 30m, and the time of period of experiments t as 30 minutes. We change the number of APs M from 1 to 7. This way, we comprehensively evaluate EACP-CA’s ability to handle datasets with different characteristics in various application scenarios.Table 3
The parameters of Gaussian distribution.
Devices 200(μ, σ) 300(μ, σ) 400(μ, σ) Fixed devices (30,25),(50,16),(110,18),(150,19) (30,25),(50,16),(110,18),(150,19) (30,25),(50,16),(110,18),(150,19) Moving devices oft0 (60,19),(80,13),(150,25),(140,30) (60,22),(65,20),(130,30),(140,22) (55,35),(40,40),(110,15),(130,30) Moving devices oft1 (55,28),(60,15),(150,25),(120,30) (60,22),(65,20),(130,30),(140,22) (55,35),(40,40),(110,40),(130,30) Moving devices oft2 (60,19),(80,15),(150,25),(150,30) (60,22),(65,20),(130,30),(140,22) (55,35),(40,40),(110,40),(130,30)


## 5.2. Performance Evaluation and Comparison

In this section, we will evaluate the performance of our proposed approach and compare it with k-means based approach through the number of movable cloudlets covered mobile devices.In order to intuitively display the distributions of mobile devices and cloudlets inA, we show three sequential record instances, i.e., t0, t1, and t2 in our experiments. The different times distributions of mobile devices and cloudlets are illustrated in Figure 4. Figure 4(a) describes the distributions at time t0. And at time t1, since the positions of the mobile devices are not changed significantly, there is no corresponding change in the locations of the mobile cloudlets, as we can see in Figure 4(b). But at time t2, the distribution of mobile devices has changed greatly and we can also find that the two cloudlets move to new locations illustrated in Figure 4(c).Figure 4
Distributions of mobile devices and cloudlets att0, t1, and t2.
(a)
t 0 (b)
t 1 (c)
t 2We investigate the performance of our approach and k-means based approach with different cloudlet numbers. We simulate to generate three datasets, which include 200, 300, and 400 mobile devices. The experimental results are shown in Figures5, 6, and 7 demonstrating that our approach outperforms k-means based approach. Figure 5 presents the results for the dataset with 200 mobile devices. Figure 5(a) shows the coverage value by all cloudlets through executing our EACP-CA approach and k-means based approach, while Figure 5(b) shows the average utilization value of each cloudlet inL. And the experimental results for datasets with 300 mobile devices and 400 mobile devices which are shown in Figures 6 and 7, respectively, are the same as the experimental results of dataset with 200 mobile devices. Figures 6(a) and 7(a) show the coverage value by all cloudlets through executing our EACP-CA approach and k-means based approach for the datasets with 300 mobile devices and 400 mobile devices, respectively, while Figures 6(b) and 7(b) show the average utilization value of each cloudlet inL.Figure 5
Comparison of performance with EACP-CA and k-means (number of mobile devicesN = 200).
(a)
Coverage value comparison (b)
Average utilization value comparisonFigure 6
Comparison of performance with EACP-CA and k-means (number of mobile devicesN = 300).
(a)
Coverage value comparison (b)
Average utilization value comparisonFigure 7
Comparison of performance with EACP-CA and k-means (number of mobile devicesN = 400).
(a)
Coverage value comparison (b)
Average utilization value comparisonThe experimental results illustrated in Figures5, 6, and 7 show that EACP-CA is better than k-means based approach because both the coverage value and average utilization of each cloudlet within different cloudlet numbers obtained by EACP-CA are higher than k-means based approach. The experimental results show that, with the rising number of cloudlets, the coverage value obtained by EACP-CA and k-means based approach also increases with the fixed number of mobile devices but becomes less significant. This is caused by the fixed number of mobile devices and the increased number of cloudlets, because, through performing the clustering algorithm, the dense mobile devices are covered by many cloudlets and the remained discrete mobile devices are also covered by another cloudlet which leads decreasing of the average utilization of each cloudlet. Therefore, we can find that the coverage value is impacted by the number of cloudlets while the number of mobile devices is fixed. With the growing number of cloudlets, the average utilization of each cloudlet is increasing at the beginning and then begins to decrease again. Simultaneously, we can also apply the average utilization value of cloudlets to select a suitable number of cloudlets. We can obtain the appropriate number of cloudlets when the average utilization value of cloudlets and the number of users covered become lager.


## 6. Conclusion and Future Work

In this paper, we propose EACP-CA, a novel covering-based approach for enhanced adaptive cloudlets placement. Given a known mobile devices activity area, according to the characteristics of the data and being independent of the initial centers, EACP-CA first employs CA with “blind” features to adaptively partition mobile devices into clusters based on the physical distances between their positions at timet. Then we adjust the central positions obtained by clustering algorithm through the graph path. Next, we execute confirmation of the center positions operation and get the desired cloudlets central positions according to the distribution of the mobile devices. We also need to obtain the pair of the original mobile cloudlet positions and the positions. Finally, we conduct the enhanced adaptive cloudlets placement to finish the mobile cloudlets placement. We parallelize the portioning operation of EACP-CA on Spark to increase the efficiency of EACP-CA in processing big data. The results of the experiments on the simulated datasets demonstrate that EACP-CA significantly outperforms the k-means based approach, which also demonstrate that EACP-CA is more efficient in clustering and improving the utilities of mobile cloudlets.In our future work, we will enhance EACP-CA to solve big data and consider the assignment of mobile users to the placed cloudlets.



---

*Source: 1937670-2018-09-02.xml*