# A Mobility-Aware and Sociality-Associate Computation Offloading Strategy for IoT

Authors: Yanfei Lu; Zengzi Chen; Qinghe Gao; Tao Jing; Jin Qian
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Mobile edge computing, a promising paradigm, brings services closer to a user by leveraging the available resources in an edge network. The crux of MEC is to reasonably allocate resources to satisfy the computing requirements of each node in the network. In this paper, we investigate the service migration problem of the offloading scheme in a power-constrained network consisting of multiple mobile users and fixed edge servers. We propose an affinity propagation-based clustering-assisted offloading scheme by taking into account the users’ mobility prediction and sociality association between mobile users and edge servers. The clustering results provide the candidate edge servers, which greatly reduces the complexity of observing all edge servers and decreases the rate of service migration. Besides, the available resource of candidate edge servers and the channel conditions are considered to optimize the offloading scheme to guarantee the quality of service. Numerical simulation results demonstrate that our offloading strategy can enhance the data processing capability of power-constrained networks and reach computing load balance.


---

## Body

## 1. Introduction

The arrival and evolution of the 5G delivers a transformative solution to an ultimate high-quality end-user experience. Such a high-speed, high-capacity, low-latency 5G network can well meet the demands of increasing data-intensive applications in the current Internet of Things (IoT) and Artificial Intelligence (AI) era. The numerous applications require high-speed internet connectivity and high computation power, which is not possible in a mobile device with limited memory and storage capacity [1–3]. In such situations, it is feasible to transfer resource-intensive tasks to external platforms like cloud, grid, and edge servers. This process is known as task offloading, which decides when and how a task should be offloaded to external platforms to execute.During the development of 5G, the mobile edge computing (MEC) technique has been playing an important role [4, 5]. Massive smart edge devices in various IoT systems hide huge distributed computing capabilities [6, 7]. The reasonable utilization of distributed capability can reduce the amount and frequency of information transferring to a distant centralized cloud server, which can greatly decrease transfer latency and omit the cloud server processing latency. Although existing research can reduce the delay in some scenarios, many severe problems remain to be solved. Especially, how to migrate services as mobile users move is a critical problem. If users move far away from the MEC server that is responding to their request, this could result in significant quality of service (QoS) and quality of experience (QoE) degradation and service interruption due to long transmission latency of the offloaded task [8]. To ensure the continuity of service, services need to be migrated to nearby MEC servers that can cover the user’s current location when it moved out of previous service coverage.The migration of user-generated data in edge networks is involved in transmission costs, the mobility of users, transmission resources, etc. Thus, an efficient edge server selection algorithm is needed to select the optimal target edge server. In general, two factors should be taken into account: users’ trajectory and QoS utility. On the one hand, existing research works rarely explore users’ trajectory data and the prediction of their movement and adopt a random mobility model instead [9]. However, users’ mobility pattern (e.g. direction and velocity) has a significant influence on the construction of the candidate edge server set and the users’ trajectory data can be used to predict users’ movement. On the other hand, existing literatures pay less attention on the effect of QoS utility (network latency, energy consumption, and cost) on the selection of edge servers in service migration and, therefore, hardly select the edge server with the highest QoS utility [10–13]. Without considering users’ trajectory data and QoS utility, the accuracy of edge server selection and the efficiency of service migration decrease. To develop a QoS-aware algorithm to improve edge server selection, we should overcome the problems such as how to integrate user’s trajectory data and QoS utility into the server selection algorithm.In this paper, we investigate an offloading scheme by considering users’ trajectory data, sociality associations, and QoS parameters. First, we employ a Kalman filtering algorithm to do mobility prediction of users’ trajectory; then, we compute the sociality association between mobile users and edge servers by using the history connection relationship. By using the mobility prediction and the social association results as input parameters of an affinity propagation algorithm, we propose a mobility-aware and sociality-associate clustering algorithm (MASACA), where MEC servers are divided into candidate sets associated with different users. Moreover, we devise a QoS utility function for each MEC server based on their available computation resource and the channel links’ quality, which is used to determine the appropriate MEC server for a user to offload task. The main contributions of this paper are summarized as follows:(1)
A mobility model of mobile users is considered, which is combined with a Kalman filter to make prediction about the location of users(2)
The sociality association is taken into account, which guarantees the continuity of service(3)
Clustering has been shown to achieve efficient and reliable management and reduce data congestion. We construct an AP-based algorithm to obtain stable clusters considering the trajectory data and the sociality association of mobile usersThe paper is organized as follows: Section2 gives a review of related works in the literature. Section 3 presents the system model and problem formulation. Section 4 gives the details of AP-MASACA. The QoS utility function encompassing outage probability and average coverage is derived in Section 5. Section 6 presents the performance of the proposed scheme by comparing with existing offloading schemes. And a summary is provided in Section 7.


## 2. Related Works

In order to optimize the delay and energy consumption of mobile devices, a computational offload strategy is adopted in mobile edge computing [14]. Mobility is one key challenging topic in MEC systems, which has effects on decisions in several domains such as caching, connected vehicles, and especially computation offloading [15]. However, the mobility of mobile users and the limited coverage of edge servers can result in significant network performance degradation, dramatic drop in QoS, and even interruption of ongoing edge services [16]. Usually, the types of UE mobility can be categorized as random mobility, short-term predictable mobility, and fully known mobility, depending on whether the future location of the UE is known. Because of the limited resources of servers, the mobility of users, and the low latency requirements of service requests, computing offloading and service migrations are expected to occur in MEC systems regularly. The authors in [17] proposed a glimpse mobility prediction model based on the seq2seq model, which provides useful coarse-grain mobility information for Mobility-Aware Deep Reinforcement Learning training. However, the traditional offloading approaches (e.g., auction-based and game-theory approaches) cannot adjust the strategy according to changing environment when dealing with the mobility problem, in order to keep the system performance for a long time, an online user-centric mobility management scheme is proposed in [18] to maximize the edge computation performance while keeping the energy consumption of user’s communication low by using Lyapunov optimization and multiarmed bandit theories. These proposed methods overcome the challenges of mobility in MEC, making contribution in reducing service delays or energy consumption of devices. However, by nature, minimizing the smart devices’ energy consumption and tasks’ execution time does not always coincide and may conflict in IoT.Beside delay and energy consumption, the MEC system performance can be further improved by utilizing the recent developments of social networks [13, 19] and energy harvesting methods. Social IoT (SIoT) has been proposed as a promising way to create and maintain the collaborative relations among smart SIoT devices. The idea of SIoT is to build social collaborative networking for smart IoTs to achieve locally distributed data processing according to the rules set by owners [20]. The collaboration between SIoT and MEC is crucial to minimize network communications and computation, where the SIoT collaboration can locally process user requests and further reduce the communications and computation in MEC networks. Nevertheless, the load sharing among SIoT devices, MEC, and remote servers brings about new challenges for the communication and computation trade-off, cross-layer design in SIoT, and forwarding and aggregation trade-off [14, 21]. To solve this issue, Wang et al. in [22] formulated a new optimization problem SIoT Collaborative Group and Device Selection Problem (SCGDSP) and propose Optimal Collaborative Group Selection (OCGS) for a fundamental SCGDSP to find the intrinsic properties of collaborative group construction under the deployment of SIoTs in a grid street map to reduce the running time and transmission delay. However, one of the main challenges of social attribute is the selfish nature of the user, and some users only response what they are interested in and do not care about other people’s needs. The authors in [23] proposed a physical-social-based cooperative cache framework to maximizing the social group utility and meet the data request of users. By considering the diversity of users, the authors of [24, 25] combined MEC with the mobile crowdsensing approach and proposed a social-based method to optimize the share of contents among users by exploiting their mobility and sociality, which improved the performance of a content-sharing scenario.There is no common definition of social strength in current researches about SIoT. Jung et al. [26] proposed a model named social strength prediction model, which infers social connections among smart objects and predicts the strength of the connections using the cousage data of the objects by two major components: (1) entropy-based and (2) distance-based social strength computations. These two components capture different properties of cousages of objects, namely, the diversity and spatiotemporal features, which are all essential factors that contribute to the values of social strength. Wang et al. [27] put forward a method to measure the social strength generally by the available storage capacity and betweenness centrality. In this paper, we propose a definition that utilizes the information entropy to calculate social strength.


## 3. System Model and Problem Formulation

In this section, we give the system model and computation model of the task offloading and then formulate the offloading problem. For the sake of clarity, we summarize the notations in Table1.Table 1
Summary of notations.
NotationsMeaningsUThe set of mobile usersSThe set of edge serversAiThe task set of mobile userUihi,jThe channel fading coefficient betweenUi and Sjdi,jThe distance betweenUi and SjN0The power of additive white Gaussian noise (AWGN)Ri,jThe channel rate betweenUi and SjAini,kThe input size of taskak for UiAouti,kThe size of computation results taskak for UiAcomi,kThe number of CPU clock cycles required byak of UiflociThe computation capability ofUiFsevjThe computation capability ofSjfsevi,j,kThe actual CPU frequency ofSj for the task ak of UiTloci,kThe time delay forUi locally executing the task akTini,j,kThe time delay forUi transmitting the task ak to SiTouti,j,kThe time delay forSi sending computation results of the task ak to UiTseci,j,kThe time delay forUi offloading task ak to Sj without service migrationTmigi,kThe time delay for migrating computing results of the taskak of Ui between two edge serversTsev,mi,j,j′,kThe time delay forUi offloading task ak to Sj with service migrationTsumi,kThe time delay for completing the taskak for UiTsumThe total time delay for completing all tasks of all usersplociThe average power when the CPU ofUi is workingpi,0The average powerUi is idlepi,RThe average powerUi is receiving computation resultspi,jThe transmission power ofUi for transmitting tasks to SjEloci,kThe energy consumption atUi for locally executing akEsevi,j,kThe energy consumption atUi for offloading ak to Sj without migrationEsev,mi,j,j′,kThe energy consumption atUi for offloading ak to Sj with migrationEsumiThe energy consumption atUi for completing its all tasksλi,j,k1 ifUi transmits ak to Sj, and otherwise 0μi,j,j′,k1 ifSj transmits computing results for ak of Ui to Sj′, and otherwise 0Sev¯The average service ratio


### 3.1. System Model

We consider a multiuser MEC model as shown in Figure1 with a set of mobile users (MUs) denoted as U=U1,U2,⋯,Ui,⋯,N and a set of edge servers as S=S1,S2,⋯,Sj,⋯,SM. According to physical positions of each user, they are clustered into different service cells surrounding edge servers. Assume that each MU has K computation tasks. Denote Ai=a1,a2,⋯,ak,⋯,aK as the task set of Ui, where each ak is independent and decomposable. For each task, a mobile user can proceed it locally or offload it to corresponding edge server within its service cell.Figure 1
System model: service cells are clustered by mobile edge computing servers and mobile users.However, the service cell for an MU may change due to the MU’s mobility. To guarantee seamless services, service migration is necessary. Specifically, as shown in Figure2, U2 initially belonged to the service cell surrounding S1 and now is within the service cell surrounding S2. If it offloaded computing tasks to S1 before moving out the initial cell and the computation results did not return to U2 before it enters into the current cell, computation results need to be migrated from S1 to S2, then returned to U2.Figure 2
Mobility-aware MEC network.Thus, there are three computation offloading models: local execution, offloading without service migration, and offloading with service migration. In following sections, we will investigate how to select from these three computation offloading models to minimize the time delay for completing all tasks of all mobile users under the guarantee of successful offloading.


### 3.2. Computation Offloading Model

DefineAini,k as the input size of task ak for Ui, Aouti,k the size of computation results returned to Ui for ak, and Acomi,k the total number of CPU clock cycles required to complete task ak.


#### 3.2.1. Local Computing Model

Letfloci denote the computation capability of Ui, which is dependent on the intrinsic nature of the MU, i.e., CPU cycles per second. The time Tloci,k for locally processing the request of task ak at Ui is expressed as
(1)Tloci,k=Acomi,kfloci.Assume that the energy consumption per second when the CPU is working isploci. Then, the energy consumption Eloci,k of local executing the task ak for Ui can be given as
(2)Eloci,k=plociTloci,k.


#### 3.2.2. Offloading without Service Migration

Three phases are needed to offload computation task to an edge server without service migration: (i) an MUUi transmits task request to an edge server Sj; (ii) edge server Sj executes computing task; and (iii) edge server Sj sends computing results to Ui.Assume that the wireless channel bandwidth betweenUi and Sj is Wi,j. Let pi,j represent the transmission power of Ui for transmitting tasks to Sj. The transmission rate Ri,j between Ui and Sj can be calculated by
(3)Ri,j=Wilog21+pi,jhi,j2di,jθN0,where hi,j represents the transmission channel fading coefficient, di,j is the distance from Ui to Sj, θ is the standard path loss propagation exponent, and N0 denotes the power of additive white Gaussian noise (AWGN). Then, the transmission phase Tini,j,k from Ui to Sj for the task ak can be given as
(4)Tini,j,k=Aini,kRi,j.The computing capability of an edge server is denoted asFsevj. Let fsevi,j,k denote the actual CPU frequency when edge server Sj executes the task ak received from Ui, where 0≤fsevi,j,k≤Fsevj. Then, the time Tcomi,j,k for edge server Sj processing the request of task ak from Ui can be calculated as
(5)Tcomi,j,k=Acomi,kfsevi,j,k.After completing the computation task, edge serverSj needs to send back the computation results to Ui. The time delay for this transmission phase is expressed as
(6)Touti,j,k=Aouti,kRi,j.Then, the total time delay for offloading taskak to an edge server Sj without service migration can be computed as
(7)Tseci,j,k=Tini,j,k+Tcomi,j,k+Touti,j,k.Assume the energy consumption per second forUi during the idle duration and the receiving phase are denoted as pi,0 and pi,R, respectively. In total, the energy consumption at Ui for executing the task ak on MEC sever Sj without service migration can be formulated as
(8)Esevi,j,k=pi,jTini,j,k+pi,0Tcomi,j,k+pi,RTouti,j,k.


#### 3.2.3. Offloading with Service Migration

IfUi moves from a cell surrounding Sj to current cell surrounding Sj′ before Sj completes the computing task ak, one more migration phase is needed to transmit computation results from edge server Sj to current edge server Sj′. The time delay of this migration phase is determined by the transmission rate Rs between these two edge servers as follows:
(9)Tmigi,k=Aouti,kRs,where Rs is a fixed value because of optical fiber communications between edge servers. Then, Sj′ forwards the computation results to Ui. Similar to (6), the transmission time can be given as
(10)Touti,j′,k=Aouti,kRi,j′,where the transmission rate Ri,j′ can be calculated in a similar way with (3). Thus, the total time delay Tsev,mi,j,j′,k for offloading with service migration can be calculated as
(11)Tsev,mi,j,j′,k=Tini,j,k+Tcomi,j,k+Tmigi,k+Touti,j′,k.Likewise as (8), the energy consumption at Ui for executing the task ak by offloading with service migration can be calculated as
(12)Esev,mi,j,j′,k=pi,jTini,j,k+pi,0Tcomi,j,k+Tmigj,j′+pi,RTouti,j′,k.


### 3.3. Problem Formulation

For convenience, we define a binary variableλi,j,k to equal to 1 if ak of Ui is offloaded to Sj and otherwise equal to 0. When ak of Ui is offloaded to Sj, we define μi,j,j′,k to be 1 if service migration from Sj to Sj′ is necessary and otherwise equal to 0. Thus, the time delay for completing the task ak for Ui can be expressed as
(13)Tsumi,k=Tloci,k∗1−∑jλi,j,k+Tsevi,j,kλi,j,k1−∑j′μi,j,j′,k+Tsev,mi,j,j′,kλi,j,k∑j′μi,j,j′,k.The total time delayTsum for completing all tasks of all users can be given by
(14)Tsum=∑i=1N∑k=1KTsumi,k.In summary, the problem of minimizing the total time delay by optimizing the transmission power matrixP=p1,⋯,pi,⋯,pN∈ℝM×N, the offloading matrix Λ∈ℝM×N×K, and the migration matrix Γ∈ℝM×N×K can be formulated as follows:
(15)P1:minP,Λ,ΓTsums.t.C1:0≤fsevi,j,k≤FsevjC2:0≤pi,j≤pmaxiC3:λi,j,k∈0,1,∀i,j,kC4:μi,j,j′,k∈0,1,∀i,j,j′,kC5:∑jλi,j,k≤1,∀i,kC6:∑j′,j′≠jμi,j,j′,k≤1,∀i,kC7:Esumi≤Emaxi,∀i,where
(16)Esumi=∑kKEloci,k∗1−∑jλi,j,k+Esevi,j,kλi,j,k1−∑j′μi,j,j′,k+Esev,mi,j,j′,kλi,j,k∑j′μi,j,j′,k.ConstraintC1 is the computing capacity limitation of edge server, and constraint C2 is the power limitation with pmaxi being the maximum tolerable transmission power at Ui. Constraints C3 and C4 indicate that λi,j,k and μi,j,j′,k are binary variables. Constraint C5 gives the requirement that each task that can be totally offloaded to an edge server or be executed locally as a whole. Constraint C6 ensures the service migration occurs between one-hop edge servers. The constraint C7 is the energy constraint at Ui with Emaxi being the maximum available energy of Ui.Due to the integer constraints C3-C6, P1 is a mixed integer programming problem and NP-hard. In order to reduce the complexity of solving this NP-hard problem, in the following sections, we propose a mobility-aware and sociality-associate affinity propagation clustering algorithm, and then design an offloading scheme based on the clustering results.


## 3.1. System Model

We consider a multiuser MEC model as shown in Figure1 with a set of mobile users (MUs) denoted as U=U1,U2,⋯,Ui,⋯,N and a set of edge servers as S=S1,S2,⋯,Sj,⋯,SM. According to physical positions of each user, they are clustered into different service cells surrounding edge servers. Assume that each MU has K computation tasks. Denote Ai=a1,a2,⋯,ak,⋯,aK as the task set of Ui, where each ak is independent and decomposable. For each task, a mobile user can proceed it locally or offload it to corresponding edge server within its service cell.Figure 1
System model: service cells are clustered by mobile edge computing servers and mobile users.However, the service cell for an MU may change due to the MU’s mobility. To guarantee seamless services, service migration is necessary. Specifically, as shown in Figure2, U2 initially belonged to the service cell surrounding S1 and now is within the service cell surrounding S2. If it offloaded computing tasks to S1 before moving out the initial cell and the computation results did not return to U2 before it enters into the current cell, computation results need to be migrated from S1 to S2, then returned to U2.Figure 2
Mobility-aware MEC network.Thus, there are three computation offloading models: local execution, offloading without service migration, and offloading with service migration. In following sections, we will investigate how to select from these three computation offloading models to minimize the time delay for completing all tasks of all mobile users under the guarantee of successful offloading.


## 3.2. Computation Offloading Model

DefineAini,k as the input size of task ak for Ui, Aouti,k the size of computation results returned to Ui for ak, and Acomi,k the total number of CPU clock cycles required to complete task ak.


### 3.2.1. Local Computing Model

Letfloci denote the computation capability of Ui, which is dependent on the intrinsic nature of the MU, i.e., CPU cycles per second. The time Tloci,k for locally processing the request of task ak at Ui is expressed as
(1)Tloci,k=Acomi,kfloci.Assume that the energy consumption per second when the CPU is working isploci. Then, the energy consumption Eloci,k of local executing the task ak for Ui can be given as
(2)Eloci,k=plociTloci,k.


### 3.2.2. Offloading without Service Migration

Three phases are needed to offload computation task to an edge server without service migration: (i) an MUUi transmits task request to an edge server Sj; (ii) edge server Sj executes computing task; and (iii) edge server Sj sends computing results to Ui.Assume that the wireless channel bandwidth betweenUi and Sj is Wi,j. Let pi,j represent the transmission power of Ui for transmitting tasks to Sj. The transmission rate Ri,j between Ui and Sj can be calculated by
(3)Ri,j=Wilog21+pi,jhi,j2di,jθN0,where hi,j represents the transmission channel fading coefficient, di,j is the distance from Ui to Sj, θ is the standard path loss propagation exponent, and N0 denotes the power of additive white Gaussian noise (AWGN). Then, the transmission phase Tini,j,k from Ui to Sj for the task ak can be given as
(4)Tini,j,k=Aini,kRi,j.The computing capability of an edge server is denoted asFsevj. Let fsevi,j,k denote the actual CPU frequency when edge server Sj executes the task ak received from Ui, where 0≤fsevi,j,k≤Fsevj. Then, the time Tcomi,j,k for edge server Sj processing the request of task ak from Ui can be calculated as
(5)Tcomi,j,k=Acomi,kfsevi,j,k.After completing the computation task, edge serverSj needs to send back the computation results to Ui. The time delay for this transmission phase is expressed as
(6)Touti,j,k=Aouti,kRi,j.Then, the total time delay for offloading taskak to an edge server Sj without service migration can be computed as
(7)Tseci,j,k=Tini,j,k+Tcomi,j,k+Touti,j,k.Assume the energy consumption per second forUi during the idle duration and the receiving phase are denoted as pi,0 and pi,R, respectively. In total, the energy consumption at Ui for executing the task ak on MEC sever Sj without service migration can be formulated as
(8)Esevi,j,k=pi,jTini,j,k+pi,0Tcomi,j,k+pi,RTouti,j,k.


### 3.2.3. Offloading with Service Migration

IfUi moves from a cell surrounding Sj to current cell surrounding Sj′ before Sj completes the computing task ak, one more migration phase is needed to transmit computation results from edge server Sj to current edge server Sj′. The time delay of this migration phase is determined by the transmission rate Rs between these two edge servers as follows:
(9)Tmigi,k=Aouti,kRs,where Rs is a fixed value because of optical fiber communications between edge servers. Then, Sj′ forwards the computation results to Ui. Similar to (6), the transmission time can be given as
(10)Touti,j′,k=Aouti,kRi,j′,where the transmission rate Ri,j′ can be calculated in a similar way with (3). Thus, the total time delay Tsev,mi,j,j′,k for offloading with service migration can be calculated as
(11)Tsev,mi,j,j′,k=Tini,j,k+Tcomi,j,k+Tmigi,k+Touti,j′,k.Likewise as (8), the energy consumption at Ui for executing the task ak by offloading with service migration can be calculated as
(12)Esev,mi,j,j′,k=pi,jTini,j,k+pi,0Tcomi,j,k+Tmigj,j′+pi,RTouti,j′,k.


## 3.2.1. Local Computing Model

Letfloci denote the computation capability of Ui, which is dependent on the intrinsic nature of the MU, i.e., CPU cycles per second. The time Tloci,k for locally processing the request of task ak at Ui is expressed as
(1)Tloci,k=Acomi,kfloci.Assume that the energy consumption per second when the CPU is working isploci. Then, the energy consumption Eloci,k of local executing the task ak for Ui can be given as
(2)Eloci,k=plociTloci,k.


## 3.2.2. Offloading without Service Migration

Three phases are needed to offload computation task to an edge server without service migration: (i) an MUUi transmits task request to an edge server Sj; (ii) edge server Sj executes computing task; and (iii) edge server Sj sends computing results to Ui.Assume that the wireless channel bandwidth betweenUi and Sj is Wi,j. Let pi,j represent the transmission power of Ui for transmitting tasks to Sj. The transmission rate Ri,j between Ui and Sj can be calculated by
(3)Ri,j=Wilog21+pi,jhi,j2di,jθN0,where hi,j represents the transmission channel fading coefficient, di,j is the distance from Ui to Sj, θ is the standard path loss propagation exponent, and N0 denotes the power of additive white Gaussian noise (AWGN). Then, the transmission phase Tini,j,k from Ui to Sj for the task ak can be given as
(4)Tini,j,k=Aini,kRi,j.The computing capability of an edge server is denoted asFsevj. Let fsevi,j,k denote the actual CPU frequency when edge server Sj executes the task ak received from Ui, where 0≤fsevi,j,k≤Fsevj. Then, the time Tcomi,j,k for edge server Sj processing the request of task ak from Ui can be calculated as
(5)Tcomi,j,k=Acomi,kfsevi,j,k.After completing the computation task, edge serverSj needs to send back the computation results to Ui. The time delay for this transmission phase is expressed as
(6)Touti,j,k=Aouti,kRi,j.Then, the total time delay for offloading taskak to an edge server Sj without service migration can be computed as
(7)Tseci,j,k=Tini,j,k+Tcomi,j,k+Touti,j,k.Assume the energy consumption per second forUi during the idle duration and the receiving phase are denoted as pi,0 and pi,R, respectively. In total, the energy consumption at Ui for executing the task ak on MEC sever Sj without service migration can be formulated as
(8)Esevi,j,k=pi,jTini,j,k+pi,0Tcomi,j,k+pi,RTouti,j,k.


## 3.2.3. Offloading with Service Migration

IfUi moves from a cell surrounding Sj to current cell surrounding Sj′ before Sj completes the computing task ak, one more migration phase is needed to transmit computation results from edge server Sj to current edge server Sj′. The time delay of this migration phase is determined by the transmission rate Rs between these two edge servers as follows:
(9)Tmigi,k=Aouti,kRs,where Rs is a fixed value because of optical fiber communications between edge servers. Then, Sj′ forwards the computation results to Ui. Similar to (6), the transmission time can be given as
(10)Touti,j′,k=Aouti,kRi,j′,where the transmission rate Ri,j′ can be calculated in a similar way with (3). Thus, the total time delay Tsev,mi,j,j′,k for offloading with service migration can be calculated as
(11)Tsev,mi,j,j′,k=Tini,j,k+Tcomi,j,k+Tmigi,k+Touti,j′,k.Likewise as (8), the energy consumption at Ui for executing the task ak by offloading with service migration can be calculated as
(12)Esev,mi,j,j′,k=pi,jTini,j,k+pi,0Tcomi,j,k+Tmigj,j′+pi,RTouti,j′,k.


## 3.3. Problem Formulation

For convenience, we define a binary variableλi,j,k to equal to 1 if ak of Ui is offloaded to Sj and otherwise equal to 0. When ak of Ui is offloaded to Sj, we define μi,j,j′,k to be 1 if service migration from Sj to Sj′ is necessary and otherwise equal to 0. Thus, the time delay for completing the task ak for Ui can be expressed as
(13)Tsumi,k=Tloci,k∗1−∑jλi,j,k+Tsevi,j,kλi,j,k1−∑j′μi,j,j′,k+Tsev,mi,j,j′,kλi,j,k∑j′μi,j,j′,k.The total time delayTsum for completing all tasks of all users can be given by
(14)Tsum=∑i=1N∑k=1KTsumi,k.In summary, the problem of minimizing the total time delay by optimizing the transmission power matrixP=p1,⋯,pi,⋯,pN∈ℝM×N, the offloading matrix Λ∈ℝM×N×K, and the migration matrix Γ∈ℝM×N×K can be formulated as follows:
(15)P1:minP,Λ,ΓTsums.t.C1:0≤fsevi,j,k≤FsevjC2:0≤pi,j≤pmaxiC3:λi,j,k∈0,1,∀i,j,kC4:μi,j,j′,k∈0,1,∀i,j,j′,kC5:∑jλi,j,k≤1,∀i,kC6:∑j′,j′≠jμi,j,j′,k≤1,∀i,kC7:Esumi≤Emaxi,∀i,where
(16)Esumi=∑kKEloci,k∗1−∑jλi,j,k+Esevi,j,kλi,j,k1−∑j′μi,j,j′,k+Esev,mi,j,j′,kλi,j,k∑j′μi,j,j′,k.ConstraintC1 is the computing capacity limitation of edge server, and constraint C2 is the power limitation with pmaxi being the maximum tolerable transmission power at Ui. Constraints C3 and C4 indicate that λi,j,k and μi,j,j′,k are binary variables. Constraint C5 gives the requirement that each task that can be totally offloaded to an edge server or be executed locally as a whole. Constraint C6 ensures the service migration occurs between one-hop edge servers. The constraint C7 is the energy constraint at Ui with Emaxi being the maximum available energy of Ui.Due to the integer constraints C3-C6, P1 is a mixed integer programming problem and NP-hard. In order to reduce the complexity of solving this NP-hard problem, in the following sections, we propose a mobility-aware and sociality-associate affinity propagation clustering algorithm, and then design an offloading scheme based on the clustering results.


## 4. Mobility-Aware and Sociality-Associate Clustering Algorithm (MASACA)

As shown in Figure3, a MU may meet different edge servers during its movement towards its destination. One of method to decrease the complexity of solving P1 is cutting down the number of candidate edge servers. In this section, we propose an affinity propagation- (AP-) based clustering by utilizing mobility prediction and sociality association results.Figure 3
Mobile node wants to get optimized offloading strategies during the movement.The MU can determine to randomly offload its tasks to an adjacent edge server at the moment the tasks arrive. In this case, service migration may occur due to the movement of MU. When the server completes the computing tasks, the MU may have moved to a remote position and the connection with this server may be lost, leading to the recalculation of tasks and bringing additional overhead. To avoid much service migration and decrease the lost rate of computation results, we use Kalman filtering method to make trajectory prediction. According to the prediction results, the mobile user can select the best timing to offload its tasks to a better edge server.


### 4.1. Mobility Prediction

The movement of the mobile user is considered as a traditional dynamic system satisfying the following state equation at timet=aT:
(17)sa=Asa−1+Bua−1+ωa,where sa is the state vector and equals px,py,vx,vya representing the user’s real-time position px,pya and its velocity vx,vya in a two-dimensional space; A is the transition matrix; ua−1 is the input signal from previous time, namely, the moving velocity of the user; B is the input matrix; ωa is a deterministic process noise and is usually assumed as a Gaussian noise with ω~N0,Q; and Q is called the process noise covariance matrix. The observation model is denoted as
(18)za=Hsa+ya,where za is the observation vector, H is the observation matrix, and ya is the observation noise and also seen as a Gaussian noise with y~N0,R. R is called the observation noise covariance matrix. Note that ωa and ya describe deviations such as collision, slippage, and friction that caused by objective conditions. Thus, in practice, the process noise covariance Q and the observation matrix R might change within each time step and are assumed to be temporally and spatially independent with each other.According to above analyses, lets^a denote the estimate value of sa when the measurement value of za is obtained. The dynamic estimation process includes two steps:
(i)
The time update phase follows the next equations as(19)s^a−=As^a−1+Bu^a,a≥1,Ga−=AGa−1A∗+Q,where ·− is the prediction value of a variable and ·∗ and ·−1 represent the transpose matrix and inverse matrix, respectively. G is the error covariance matrix(ii)
The measurement update phase is as follows:(20)Ka=Ga−H∗HPa−H∗+R−1,s^a=s^a−+Kaza−Hs^a−,Ga=I−KaHGa−,where matrix K is the Kalman filtering gain and I represents unit matrixThus, the Kalman filtering prediction algorithm starts with an initial predicted states0− and a certain error covariance G0−=Π0 then executes the time update and measurement update by iterations until satisfying a certain termination condition. Finally, we can get the predicted trajectory of each mobile user, including the position and the velocity information at each time slot.


### 4.2. Sociality Association

In this subsection, we consider the influence of sociality association on choosing appropriate edge servers for offloading tasks. Since there is an acquaintance effect, we mainly take the history connections into account. And we use the Renyi entropy to describe the selection preference. A higher entropy represents higher uncertainty on a specific selection. Specifically, the Renyi entropy is denoted as(21)HαiP=11−αlog∑j=1Mpi,jα,where α is a general parameter in Renyi entropy. Different values of α represent different entropy; for example, when α=1, it is the Shannon entropy as limα⟶1HαP=∑j=1Mlog1/pi,j. And pi,j is the probability of Ui communicates with Sj. A smaller value of HαiP means a higher possibility that Ui will offload its tasks to the server jm with the maximum value of jm=argjmaxpi,j,∀j∈1,2,⋯,M.LetV represent the set of social association matrix between edge servers and mobile users. Vi,j,a=<i,j,ta> represents that Ui communicates with Sj during t=aT. For example, Vi,·,·=<t3>,<t1,t15>,0,⋯,<t10,t12,t19> is the association vector for Ui, demonstrating that Ui has connected with S1 at t3, S2 at t1 and t15, and SM at t10,t12,t19 and never connected with S3. The set of request user i was proposed for edge server j. Let wi,j denote the communication frequency between Ui and Sj, e.g., wi,1=1,wi,2=2,wi,3=0,⋯,wi,M=3. Define Ωi=∑jwi,j representing the total number of Ui communicate with all edge servers. Thus, the probability pi,j is calculated as
(22)pi,j=wi,jΩi,forUi∈U,Sj∈S.Similarly,V·,j,· can be easily obtained, denoting the social association between Sj and all users and qj,i can be also calculated as
(23)qj,i=w′j,iΩ′j,forUi∈U,Sj∈S.


### 4.3. AP Clustering

To accelerate the determination on connection with appropriate edge servers, we propose mobility-aware and sociality-associate clustering algorithm. Without the need of giving the number of clusters, the affinity propagation- (AP-) based clustering is employed . For the sake of striking the balance between accuracy and complexity, the update window is set asL slots.


#### 4.3.1. Similarity Definition

The AP algorithm takes similarity,si,j, as a measure describing the resemblance between nodes. si,j≥si,j′ when node Ui has higher similarity with Sj than with Sj′. In the mobility model, the similarity is probable to be higher when two nodes have closer distance between them. Thus, we define the similarity as the reciprocal of the average distance between nodes with future L slots according to the mobility prediction results.
(24)di,j=∑t=aTt=a+L−1T∣p^x,p^yti−px,pytj∣L,di,i′=∑t=aTt=a+L−1T∣p^x,p^yti−p^x,p^yti′∣L,dj,j′=∑t=aTt=a+L−1T∣px,pytj−px,pytj′∣L.Thus, we have(25)si,j=1di,j,si,i′=1di,i′,sj,j′=1dj,j′.The smaller the distance is, the bigger the similarity and then, the higher the possibility thatUi and Sj belong to a same cluster. Assume the distance between any two different nodes is larger than 1; thus, the maximum value of similarity is set 1 such that si,i=sj,j=1. Note that i,i′ refer to the subscripts of mobile users and j,j′ are the subscripts of edge servers.


#### 4.3.2. AP-Based Clustering Mobility-Aware and Sociality-Associate Clustering Algorithm

During the clustering, we generally use subscriptsn,m to denote all nodes in the system. After similarity measures, there are other two important messages transferred between nodes [28, 29]: (i) responsibility, rn,m, is sent from node n to candidate exemplar node m, indicating how well the node m is suitable as the exemplar of node n; (ii) availability, an,m, is sent from candidate exemplar node m to node n, reflecting how appropriate it would be for the node n choose node m as its exemplar. The initial values are given according to the social association, i.e., for the case of n=i and m=j; calculate ri,j=qj,i and ai,j=pi,j; otherwise, the initial value is an,m=0, e.g., ai,i=ai,i′=aj,j′=aj,j=0.The update formulas for responsibility and availability are stated as(26)rn,m⟵sn,m−maxm′≠man,m′+sn,m′,(27)an,mn≠m⟵min0,rm,m+∑∀n′∉n,mmax0,rn′,m,(28)am,m⟵∑n′≠mmax0,rn′,m.In order to avoid numerical oscillations, the AP algorithm introduces a convergence coefficientλ when updating information. Each piece of information is set to λ times its previous iteration updating value plus 1−λ times the current information updating value. Among that, the attenuation coefficient λ is a number between 0 and 1, while in our simulation λ=0.5 is used.
(29)rt+1n,m⟵1−λrt+1n,m+λrtn,m,(30)at+1n,m⟵1−λat+1n,m+λatn,m.Availabilities and responsibilities are combined to select exemplar. The maximum value ofan,m+rn,m identifies the exemplar. Upon convergence, each node’s cluster head CH is defined by
(31)CH=argmaxmrn,m+an,mA detailed AP-based clustering algorithm is shown in Algorithm1.Algorithm 1: AP-based mobility-aware and sociality-associate clustering algorithm (AP-MASACA).
Input:•The user setU and edge servers set S;•The positions of edge serverspx,pyj;•History connection relationshipV between Ui and Sj;Output:•F: the partition of all nodes into clusters;•CH: the set of cluster centers;1: function KALMANFILTERINGU.2:  Initializes0 and P0;3:  for Eacha∈1,L−1 do4:   Time Update according to (19);5:   Measurement Update according to (20);6:  end for7:  Output mobility prediction results:8:si=s1,s2,⋯,sL−1i.9: end function10: function PROBABILITYCOMPUTATIONV11:  Build matrixVi,·,· and V·,j,·;12:  Calculatewi,j, Ωi, then compute pi,j according to (22);13:  Calculatew′j,i, Ω′j, then compute qj,i according to (23);14:  Outputpi,j and qj,i,∀Ui∈U,Sj∈S.15: end16: function APCLUSTERINGpx,pyj,si,pi,j,qj,i17:  Calculate the distancesdn,m based on (24);18:  Calculate the similaritiessn,m based on (25);19:  Initializean,m to be zero;20:  Initializern,m according to the type of nodes;21:  Update the responsibilityrn,m based on (26);22:  Update the availabilityan,m based on (27);23:CH=CH∣CH=argmmaxan,m+rn,m;24:  CalculateFCHn=m∣CHm=CHn;25:F=FCHn∣CHn∈CH;26:  OutputCH and F27: end function


## 4.1. Mobility Prediction

The movement of the mobile user is considered as a traditional dynamic system satisfying the following state equation at timet=aT:
(17)sa=Asa−1+Bua−1+ωa,where sa is the state vector and equals px,py,vx,vya representing the user’s real-time position px,pya and its velocity vx,vya in a two-dimensional space; A is the transition matrix; ua−1 is the input signal from previous time, namely, the moving velocity of the user; B is the input matrix; ωa is a deterministic process noise and is usually assumed as a Gaussian noise with ω~N0,Q; and Q is called the process noise covariance matrix. The observation model is denoted as
(18)za=Hsa+ya,where za is the observation vector, H is the observation matrix, and ya is the observation noise and also seen as a Gaussian noise with y~N0,R. R is called the observation noise covariance matrix. Note that ωa and ya describe deviations such as collision, slippage, and friction that caused by objective conditions. Thus, in practice, the process noise covariance Q and the observation matrix R might change within each time step and are assumed to be temporally and spatially independent with each other.According to above analyses, lets^a denote the estimate value of sa when the measurement value of za is obtained. The dynamic estimation process includes two steps:
(i)
The time update phase follows the next equations as(19)s^a−=As^a−1+Bu^a,a≥1,Ga−=AGa−1A∗+Q,where ·− is the prediction value of a variable and ·∗ and ·−1 represent the transpose matrix and inverse matrix, respectively. G is the error covariance matrix(ii)
The measurement update phase is as follows:(20)Ka=Ga−H∗HPa−H∗+R−1,s^a=s^a−+Kaza−Hs^a−,Ga=I−KaHGa−,where matrix K is the Kalman filtering gain and I represents unit matrixThus, the Kalman filtering prediction algorithm starts with an initial predicted states0− and a certain error covariance G0−=Π0 then executes the time update and measurement update by iterations until satisfying a certain termination condition. Finally, we can get the predicted trajectory of each mobile user, including the position and the velocity information at each time slot.


## 4.2. Sociality Association

In this subsection, we consider the influence of sociality association on choosing appropriate edge servers for offloading tasks. Since there is an acquaintance effect, we mainly take the history connections into account. And we use the Renyi entropy to describe the selection preference. A higher entropy represents higher uncertainty on a specific selection. Specifically, the Renyi entropy is denoted as(21)HαiP=11−αlog∑j=1Mpi,jα,where α is a general parameter in Renyi entropy. Different values of α represent different entropy; for example, when α=1, it is the Shannon entropy as limα⟶1HαP=∑j=1Mlog1/pi,j. And pi,j is the probability of Ui communicates with Sj. A smaller value of HαiP means a higher possibility that Ui will offload its tasks to the server jm with the maximum value of jm=argjmaxpi,j,∀j∈1,2,⋯,M.LetV represent the set of social association matrix between edge servers and mobile users. Vi,j,a=<i,j,ta> represents that Ui communicates with Sj during t=aT. For example, Vi,·,·=<t3>,<t1,t15>,0,⋯,<t10,t12,t19> is the association vector for Ui, demonstrating that Ui has connected with S1 at t3, S2 at t1 and t15, and SM at t10,t12,t19 and never connected with S3. The set of request user i was proposed for edge server j. Let wi,j denote the communication frequency between Ui and Sj, e.g., wi,1=1,wi,2=2,wi,3=0,⋯,wi,M=3. Define Ωi=∑jwi,j representing the total number of Ui communicate with all edge servers. Thus, the probability pi,j is calculated as
(22)pi,j=wi,jΩi,forUi∈U,Sj∈S.Similarly,V·,j,· can be easily obtained, denoting the social association between Sj and all users and qj,i can be also calculated as
(23)qj,i=w′j,iΩ′j,forUi∈U,Sj∈S.


## 4.3. AP Clustering

To accelerate the determination on connection with appropriate edge servers, we propose mobility-aware and sociality-associate clustering algorithm. Without the need of giving the number of clusters, the affinity propagation- (AP-) based clustering is employed . For the sake of striking the balance between accuracy and complexity, the update window is set asL slots.


### 4.3.1. Similarity Definition

The AP algorithm takes similarity,si,j, as a measure describing the resemblance between nodes. si,j≥si,j′ when node Ui has higher similarity with Sj than with Sj′. In the mobility model, the similarity is probable to be higher when two nodes have closer distance between them. Thus, we define the similarity as the reciprocal of the average distance between nodes with future L slots according to the mobility prediction results.
(24)di,j=∑t=aTt=a+L−1T∣p^x,p^yti−px,pytj∣L,di,i′=∑t=aTt=a+L−1T∣p^x,p^yti−p^x,p^yti′∣L,dj,j′=∑t=aTt=a+L−1T∣px,pytj−px,pytj′∣L.Thus, we have(25)si,j=1di,j,si,i′=1di,i′,sj,j′=1dj,j′.The smaller the distance is, the bigger the similarity and then, the higher the possibility thatUi and Sj belong to a same cluster. Assume the distance between any two different nodes is larger than 1; thus, the maximum value of similarity is set 1 such that si,i=sj,j=1. Note that i,i′ refer to the subscripts of mobile users and j,j′ are the subscripts of edge servers.


### 4.3.2. AP-Based Clustering Mobility-Aware and Sociality-Associate Clustering Algorithm

During the clustering, we generally use subscriptsn,m to denote all nodes in the system. After similarity measures, there are other two important messages transferred between nodes [28, 29]: (i) responsibility, rn,m, is sent from node n to candidate exemplar node m, indicating how well the node m is suitable as the exemplar of node n; (ii) availability, an,m, is sent from candidate exemplar node m to node n, reflecting how appropriate it would be for the node n choose node m as its exemplar. The initial values are given according to the social association, i.e., for the case of n=i and m=j; calculate ri,j=qj,i and ai,j=pi,j; otherwise, the initial value is an,m=0, e.g., ai,i=ai,i′=aj,j′=aj,j=0.The update formulas for responsibility and availability are stated as(26)rn,m⟵sn,m−maxm′≠man,m′+sn,m′,(27)an,mn≠m⟵min0,rm,m+∑∀n′∉n,mmax0,rn′,m,(28)am,m⟵∑n′≠mmax0,rn′,m.In order to avoid numerical oscillations, the AP algorithm introduces a convergence coefficientλ when updating information. Each piece of information is set to λ times its previous iteration updating value plus 1−λ times the current information updating value. Among that, the attenuation coefficient λ is a number between 0 and 1, while in our simulation λ=0.5 is used.
(29)rt+1n,m⟵1−λrt+1n,m+λrtn,m,(30)at+1n,m⟵1−λat+1n,m+λatn,m.Availabilities and responsibilities are combined to select exemplar. The maximum value ofan,m+rn,m identifies the exemplar. Upon convergence, each node’s cluster head CH is defined by
(31)CH=argmaxmrn,m+an,mA detailed AP-based clustering algorithm is shown in Algorithm1.Algorithm 1: AP-based mobility-aware and sociality-associate clustering algorithm (AP-MASACA).
Input:•The user setU and edge servers set S;•The positions of edge serverspx,pyj;•History connection relationshipV between Ui and Sj;Output:•F: the partition of all nodes into clusters;•CH: the set of cluster centers;1: function KALMANFILTERINGU.2:  Initializes0 and P0;3:  for Eacha∈1,L−1 do4:   Time Update according to (19);5:   Measurement Update according to (20);6:  end for7:  Output mobility prediction results:8:si=s1,s2,⋯,sL−1i.9: end function10: function PROBABILITYCOMPUTATIONV11:  Build matrixVi,·,· and V·,j,·;12:  Calculatewi,j, Ωi, then compute pi,j according to (22);13:  Calculatew′j,i, Ω′j, then compute qj,i according to (23);14:  Outputpi,j and qj,i,∀Ui∈U,Sj∈S.15: end16: function APCLUSTERINGpx,pyj,si,pi,j,qj,i17:  Calculate the distancesdn,m based on (24);18:  Calculate the similaritiessn,m based on (25);19:  Initializean,m to be zero;20:  Initializern,m according to the type of nodes;21:  Update the responsibilityrn,m based on (26);22:  Update the availabilityan,m based on (27);23:CH=CH∣CH=argmmaxan,m+rn,m;24:  CalculateFCHn=m∣CHm=CHn;25:F=FCHn∣CHn∈CH;26:  OutputCH and F27: end function


## 4.3.1. Similarity Definition

The AP algorithm takes similarity,si,j, as a measure describing the resemblance between nodes. si,j≥si,j′ when node Ui has higher similarity with Sj than with Sj′. In the mobility model, the similarity is probable to be higher when two nodes have closer distance between them. Thus, we define the similarity as the reciprocal of the average distance between nodes with future L slots according to the mobility prediction results.
(24)di,j=∑t=aTt=a+L−1T∣p^x,p^yti−px,pytj∣L,di,i′=∑t=aTt=a+L−1T∣p^x,p^yti−p^x,p^yti′∣L,dj,j′=∑t=aTt=a+L−1T∣px,pytj−px,pytj′∣L.Thus, we have(25)si,j=1di,j,si,i′=1di,i′,sj,j′=1dj,j′.The smaller the distance is, the bigger the similarity and then, the higher the possibility thatUi and Sj belong to a same cluster. Assume the distance between any two different nodes is larger than 1; thus, the maximum value of similarity is set 1 such that si,i=sj,j=1. Note that i,i′ refer to the subscripts of mobile users and j,j′ are the subscripts of edge servers.


## 4.3.2. AP-Based Clustering Mobility-Aware and Sociality-Associate Clustering Algorithm

During the clustering, we generally use subscriptsn,m to denote all nodes in the system. After similarity measures, there are other two important messages transferred between nodes [28, 29]: (i) responsibility, rn,m, is sent from node n to candidate exemplar node m, indicating how well the node m is suitable as the exemplar of node n; (ii) availability, an,m, is sent from candidate exemplar node m to node n, reflecting how appropriate it would be for the node n choose node m as its exemplar. The initial values are given according to the social association, i.e., for the case of n=i and m=j; calculate ri,j=qj,i and ai,j=pi,j; otherwise, the initial value is an,m=0, e.g., ai,i=ai,i′=aj,j′=aj,j=0.The update formulas for responsibility and availability are stated as(26)rn,m⟵sn,m−maxm′≠man,m′+sn,m′,(27)an,mn≠m⟵min0,rm,m+∑∀n′∉n,mmax0,rn′,m,(28)am,m⟵∑n′≠mmax0,rn′,m.In order to avoid numerical oscillations, the AP algorithm introduces a convergence coefficientλ when updating information. Each piece of information is set to λ times its previous iteration updating value plus 1−λ times the current information updating value. Among that, the attenuation coefficient λ is a number between 0 and 1, while in our simulation λ=0.5 is used.
(29)rt+1n,m⟵1−λrt+1n,m+λrtn,m,(30)at+1n,m⟵1−λat+1n,m+λatn,m.Availabilities and responsibilities are combined to select exemplar. The maximum value ofan,m+rn,m identifies the exemplar. Upon convergence, each node’s cluster head CH is defined by
(31)CH=argmaxmrn,m+an,mA detailed AP-based clustering algorithm is shown in Algorithm1.Algorithm 1: AP-based mobility-aware and sociality-associate clustering algorithm (AP-MASACA).
Input:•The user setU and edge servers set S;•The positions of edge serverspx,pyj;•History connection relationshipV between Ui and Sj;Output:•F: the partition of all nodes into clusters;•CH: the set of cluster centers;1: function KALMANFILTERINGU.2:  Initializes0 and P0;3:  for Eacha∈1,L−1 do4:   Time Update according to (19);5:   Measurement Update according to (20);6:  end for7:  Output mobility prediction results:8:si=s1,s2,⋯,sL−1i.9: end function10: function PROBABILITYCOMPUTATIONV11:  Build matrixVi,·,· and V·,j,·;12:  Calculatewi,j, Ωi, then compute pi,j according to (22);13:  Calculatew′j,i, Ω′j, then compute qj,i according to (23);14:  Outputpi,j and qj,i,∀Ui∈U,Sj∈S.15: end16: function APCLUSTERINGpx,pyj,si,pi,j,qj,i17:  Calculate the distancesdn,m based on (24);18:  Calculate the similaritiessn,m based on (25);19:  Initializean,m to be zero;20:  Initializern,m according to the type of nodes;21:  Update the responsibilityrn,m based on (26);22:  Update the availabilityan,m based on (27);23:CH=CH∣CH=argmmaxan,m+rn,m;24:  CalculateFCHn=m∣CHm=CHn;25:F=FCHn∣CHn∈CH;26:  OutputCH and F27: end function


## 5. QoS-Aware Offloading Scheme

According to the AP clustering results, each MU has a high probability to offload its tasks to the edge servers within a same cluster. During designing the clustering algorithm, we have considered the influence of history connections and the mobility prediction. To realize the objective given inP1, we take two more factors into account, encompassing the service ratio and the channel conditions between MU and edge servers.Although it is overloaded to make edge servers execute all of computation tasks, edge servers are expected to serve as many mobile users as possible. In addition in most cases, users prefer to communicate with edge servers with more available resources rather than the ones that are trapped in resource competition. So as the available resource of edge servers decreases, their corresponding social strength may be affected to decrease. To visually evaluate the quality of computation offloading based on the AP-MASACA, we defined a QoS parameter average service ratio, which follows(32)Sevi=nsevind,i=1,2,⋯,k,(33)Sev¯=∑Sevik,where Sevi represents the service ratio of i-th edge server, nsevi represents the actual number of mobile devices attaching the i-th edge server (assuming that every mobile user has only one device), and nd represents the actual number of mobile devices served by any edge server.By applying MASACA strategies, the system cost of computation offloading could be decreased. When signal propagates through wireless channels, it undergoes deleterious effects mainly characterized by path loss, multipath fading, and shadowing, while the computation links between mobile users and edge servers could be interrupted. The SINR outage probability is an important channel quality measure of communication links operating over composite fading/shadowing channels, which is defined as the probability that the received SNRγ drops below a certain threshold γth for a certain average SNR γ¯ [30]:
(34)Poutγ¯,rth=Eθγth−γ.Note thatPoutγ¯,rth requires the SNR distribution. Considering that the SNR could be affected by the distance of links, SNR γd could be obtained following
(35)PRxd=PTx−Ld+W,(36)γd=PRxd−N0,where PTx represents the transmission power, Ld represents the path loss, and W represents the shadowing gain factor. And N0 represents the noise power of additive white Gaussian noise (AWGN) in a wireless communication environment.Furthermore, according to the composite lognormal/gamma PDF introduced by [31], we could get the final expression about outage probability as follows:
(37)fσσ=12πζαexp−lnσ−μ22ζ2,(38)Poutd=121+erfγ−PRx−Ld−N02σ2.We define the connection ratio to visually describe the performance for maintaining the sustainability of connections with edge servers in different cases:(39)Pcond=1−Poutd.


## 6. Experiments and Result Analysis

In this section, we conduct simulation experiments to verify the efficiency of our proposed offloading scheme by comparing with an existing method employed in [32, 33] where mobile users randomly offload computation tasks to edge servers they have searched.In our simulation, MEC servers are uniformly distributed within an area with side length of 200 m. The simulation settings are listed in Table2. Under different numbers of MEC servers N and different moving speed of mobile users v, we conduct experiments to show the performance in terms of the time delay, the service ratio, and the connection ratio. The results are averaged over 1000 independent runs.Table 2
Parameter settings.
ParametersValuesThe initial state vector in Kalman filters00,0,0,vTThe number of tasks to be executed10,50The processing capacity of MEC servers10The transmission powerPTx−10 (dBm)The standard deviation of shadowingσ8 (dB)The desired SNRγth10 (dB)The AWGNN0−95 (dBm)Figure4 shows the influence of the number of mobile users on the average time delay. We can see that the average offloading time delay increases with the expansion of mobile users’ scale for each method. This is an intuitive result because the computation capability of MEC servers is limited and more users need to wait for a specific period before being serviced. For the same number of mobile users, our proposed scheme obtains a lower average delay, outperforming the original random offloading method. This demonstrates the effectiveness of our proposed scheme.Figure 4
The average offloading time delay.Figure5 shows that the number of mobile users serviced by edge servers will increase with the expansion of mobile users’ scales. Compared with the case that mobile users offload computation tasks randomly, we can see the improvements that applying AP-MASACA could bring more chances for mobile users to be served. At the same time, it can be seen that the system performance was not greatly stable as the number of mobile users increases, which means that there may be available resources of some edge servers not fully utilized and the offloading strategy can be further optimized.Figure 5
The service ratio with different user scales.Figure6 shows the connection ratio under different velocities in the single-user scenario. We can see that the connection ratio of each method declines with the increase of the number of computation tasks. This is because the competition for resources becomes more intense with the increase of task amount. Meanwhile, the decline rate of our proposed scheme is slower than that of the original random case. For the same number of computation tasks, our proposed scheme has a higher connection ratio than the original random method. This demonstrates our proposed scheme can improve the sustainability of connections between MU and MEC servers. Moreover, it is obvious that the larger the number of MEC server, N, is, the higher the connection ratio. By comparing the results shown in Figures 6(a) and 6(b), we can know that the connection ratio decreases with the increasing speed. This is because the distance between the MU and the selected MEC servers changes faster with the increasing speed.Figure 6
The connection ratiovs. number of tasks in single user scenario.
(a)
v=20 km/h(b)
v=60 km/hFigure7 shows the connection ratio of multiuser scenario. As the number of MEC servers increases, the system performance is getting better. And it shows that the performance in the multiuser scenario is better than that in the single-user scenario. Figure 6 shows the connection ratio of multiuser when the moving speed is 80 km/h. From the simulation results, it has been shown that the connection ratio is improved by applying the proposed method especially when mobile users move at a high speed.Figure 7
The connection ratiovs. number of tasks in multiuser scenario.
(a)
v=60 km/h(b)
v=80 km/h


## 7. Conclusion

In this paper, we design a task offloading strategy by considering the mobility, the sociality, and QoS factors. First, we employ the Kalman filtering algorithm to do mobility prediction of mobile users’ trajectory; then, we compute the sociality association parameter between mobile users and edge servers based on the history connection relationship. By applying the mobility prediction results and the social association parameter as input parameters of affinity propagation algorithm, we propose the mobility-aware and sociality-associate clustering algorithm (MASACA). By applying the clustering results as candidate edge server set, we devise QoS utility function of a given edge server based on the available service ratio and the quality of channel link. At last, based on the designed QoS utility function, we select the candidate edge server with the highest QoS utility as the target edge server to offload tasks. Numerical simulation results demonstrate that our offloading strategy can enhance the data processing capability of power-constrained networks and cut down the computation delay.



---

*Source: 9919541-2021-06-28.xml*