Joint Optimization of Latency and Energy Consumption for Mobile Edge Computing Based Proximity Detection in Road Networks

Tongyu Zhao,Yaqiong Liu,*,Guochu Shou,Xinwei Yao

1 School of Information and Communication Engineering,Beijing University of Posts and Telecommunications,Beijing 100876,China

2 Beijing Laboratory of Advanced Information Networks,Beijing Key Laboratory of Network System Architecture and Convergence,Beijing 100876,China

3 School of Computer Science and Technology,Zhejiang University of Technology,China

Abstract:In recent years,artifcial intelligence and automotive industry have developed rapidly,and autonomous driving has gradually become the focus of the industry.In road networks,the problem of proximity detection refers to detecting whether two moving objects are close to each other or not in real time.However,the battery life and computing capability of mobile devices are limited in the actual scene,which results in high latency and energy consumption.Therefore,it is a tough problem to determine the proximity relationship between mobile users with low latency and energy consumption.In this article,we aim at fnding a tradeoff between latency and energy consumption.We formalize the computation offoading problem base on mobile edge computing(MEC)into a constrained multiobjective optimization problem(CMOP)and utilize NSGA-II to solve it.The simulation results demonstrate that NSGA-II can fnd the Pareto set,which reduces the latency and energy consumption effectively.In addition,a large number of solutions provided by the Pareto set give us more choices of the offoading decision according to the actual situation.

Keywords:proximity detection;mobile edge computing;road networks;constrained multiobjective optimization

I.INTRODUCTION

In the criss-crossing road network,the moving speed of vehicles and pedestrians changes over time,forming a complex moving scene of the road network.In this complex mobile scene,how to determine the proximity relationship between users is known as the proximity detection.Proximity detection among mobile users plays a signifcant role in a dynamic road network,which helps ensure traffc safety and realize large-scale autonomous driving[1,2].

Most of the current proximity detection solutions[3–14]are based on geographic space distance(Euclidean distance or road network distance)and use traditional client-server(C/S)architecture or distributed peer-to-peer(P2P)architecture for detection.However,under the P2P architecture,mobile users communicate in pairs,resulting in a huge number of communication messages.Although each user can know which users are close to him/her,it cannot monitor the proximity status of all mobile users from a global perspective.In contrast,the traditional C/S architecture fails to make the best possible use of the restricted communication and computing resources,although it can detect the proximity relationship between users from a global perspective,so it is insuffcient in reducing the communication delay.Hence,these two architectures are not applicable to this scenario.

Compared with the above two architectures,Mobile Edge Computing(MEC)[15–17]has great effects on alleviating the mentioned problems.In the MEC architecture,edge servers have more powerful computing and storage capability.They are deployed at the edge of network,which are closer to users.The tasks are offoaded to the edge servers,which leads to a signifcant reduction in latency and energy consumption.Meanwhile,it brings a more comfortable user experience.

Observe the fact that,in road networks,vehicles need to pay attention to avoiding oncoming vehicles that collide with them in a short period of time,instead of avoiding parallel vehicles that are geographically close.Therefore,in many cases,considering time distance is more meaningful than geospatial distance for two users.Time distance means the least time required for two moving objects to approach[2].When the time distance between two users does not exceed the proximity thresholdTε,it can be determined that the two users are in proximity with each other.

However,in road networks,existing researches rarely refect the importance of time distance for proximity detection.Moreover,we need to pay attention to two key points when solving this problem,which include(i)the ability to constantly detect those users who are close to each other based on time distance,and(ii)the reduction of latency and energy consumption.The purpose is to ensure the precision and profciency of proximity detection.

Therefore,we exert time distance to evaluate whether two users are close and adopt pruning strategies to reduce latency and energy consumption.We consider latency and energy consumption at the same time and aim at fnding a tradeoff between latency and energy consumption.In this complex scene,we formalize the computation offoading problem based on MEC into a CMOP and use NSGA-II to fnd the Pareto set.A large number of solutions in the Pareto set provide more choices of the offoading decision for mobile users according to the actual situation,which is the biggest difference between our work and previous studies.

In this article,we adopt the MEC enhanced proximity detection architecture[2],and the latency and energy consumption of this problem is jointly optimized through the NSGA-II[18]to gain the Pareto optimal set.The main contributions of this article are summarized below.

·Based on the MEC enhanced proximity detection architecture,we propose a computation offoading scheme in dynamic road networks.

·The proximity detection problem is modeled as a CMOP with the objective of minimizing the average latency and energy consumption of this system simultaneously.

·We utilize NSGA-II to solve the CMOP and get the Pareto optimal solutions,which can meet actual requirements of different users.

·We propose the pruning strategy,which can reduce the latency and energy consumption signifcantly.

The rest of this article is structured as follows.Section II presents related work on proximity detection in Euclidean space and road network space.A computation offoading scheme based on the MEC enhanced proximity detection architecture is proposed in Section III.Section IV takes an overview of the system and formulates the optimization problem.Section V solves the CMOP using NSGA-II.In Section VI,we conduct simulation experiments and analyze the results.Finally,Section VII concludes this article.

II.RELATED WORK

In this section,we introduce the research status of proximity detection from two aspects: proximity detection in Euclidean space and proximity detection in road networks.

2.1 Proximity Detection in Euclidean Space

Most of the existing proximity detection research focus on the Euclidean space and perform proximity detection based on the Euclidean distance of two users.

References[3–8]are representatives of using the traditional C/S architecture for proximity detection in Euclidean space.Among them,Reference[3]introduces several location update methods and compares their effciency.Reference[4]proposes a simple and effcient location update policy.Reference[5]describes several position update methods,and proposes a proximity detection algorithm based on the navigation that considers the mobile target motion mode.Reference[6]describes a novel location update method that can produce less location update requests.References[7,8]propose algorithms to reduce the number of inquiry messages sent by the server to users to achieve effcient proximity detection.

The typical representatives of using the P2P architecture for proximity detection in Euclidean space are the Strips algorithm[9]and the Troy algorithm[10].The Strips algorithm requires each user to maintain a strip area for each of his friends.When the number of users is huge,it is necessary to maintain a large number of strip areas,producing a large number of communication and computing costs.The TROY algorithm takes into account the impact of communication distance between the users on power consumption of mobile intelligence terminals,aiming to reduce the power consumption caused by communication.However,the TROY algorithm does not reduce the number of communication messages between users,and in some cases the number of communication messages is even higher than existing algorithms.

Mobile users in Euclidean space can move in all direction,while users in the road network can only move along fxed roads.Due to the difference between the Euclidean space and the road network space,and the calculation of the road network distance is more complicated than the Euclidean distance,the proximity detection based on the Euclidean space is not suitable for the proximity detection in the road network space.

2.2 Proximity Detection in Road Networks

At present,a small number of studies pay attention to the proximity detection in road networks.

The work[11]proposes an update policy based on two regions,including proximity region and separation region.The key idea is to save two regions for each user,as long as the user does not reach the boundary of regions,there is no need to send update messages.The purpose is to reduce the user’s update cost,but ignore the cost of the server.Another work[12]proposes a method of reducing the user’s update cost and server’s inquiry cost based on the traditional C/S architecture and road network distance.Reference[13]defnes three proximity relationships of mobile users in road networks,but does not propose specifc solutions for proximity detection.The works above focus on static road networks.However,the road networks are time-aware rather than static in actual scenario.Few works focus on the time-aware road networks.Reference[14]uses graph embedding technology for proximity detection in time-dependent road networks,but it does not propose a method of reducing communication costs.

In summary,most of the current proximity detection solutions are based on geographic space distance(Euclidean distance or road network distance)and use traditional C/S architecture or P2P architecture for detection,which rarely refer to the importance of time distance to the proximity detection in road networks.Moreover,some researches only focus on user’s update cost or server’s inquiry cost,fail to resolve the contradiction between resource restriction and proximity detection performance,and ignore communication delay and calculation time.Therefore,it is still necessary to develop effcient proximity detection solutions in time-aware road networks to minimize the communication cost and computational cost.

In this article,we solve the problem of proximity detection in time-aware road networks and adopt time distance to judge whether the two mobile users are adjacent.Aiming at reducing the communication latency and energy consumption,we propose a computation offoading scheme for proximity detection based on the MEC.Aiming to reduce the calculation time,we propose the pruning strategy in dynamic road networks.

III.COMPUTATION OFFLOADING SCHEME FOR PROXIMITY DETECTION BASED ON MEC

In this section,we introduce the MEC enhanced proximity detection architecture and the computation offoading scheme based on it in details.

Figure 1 shows the MEC enhanced proximity detection architecture,which consists of the core network and multiple edge clouds.Multiple edge servers are distributed in edge clouds.The core network is distributed in network centre and equipped with central servers.The users only communicate with the corresponding edge server,not the central server.Each user exchanges information with the nearest edge server,reporting its location and velocity information.At the same time,the edge server also shares other users’information with it.Through communication,each mobile user receives the location and velocity information of other users in road networks.This avoids interfowing with the central server through the core network,so as to reduce latency and network burden.The architecture not only guarantees the regular communication mode between users and edge servers,and between edge servers and the central server,but also makes more reasonable use of bandwidth resources and effectively reduces the communication latency by taking advantage of the low latency characteristics of the MEC architecture.In contrast,under the traditional C/S architecture,the central server is responsible for calculating proximity relationship of all users in road networks which is too burdensome and timecomplex.In the new architecture based on MEC,each edge server is only in charge of the users communicating with it.In the meantime,each user can offoad part of tasks to the edge server,which reduces computation burden of users and the overall computing time.The central server is responsible for integrating the calculation results of each edge server and realizing global monitoring.

Figure 1.The MEC enhanced proximity detection architecture[2].

Figure 2.Schematic diagram of computation offloading under the proximity detection architecture based on MEC.

It is worth noting that most users can fnd all users close to them on edge servers.However,for the mobile user located in the boundary region of the corresponding edge server’s service area,perhaps part of users close to it are not distributed in the service area of this server,but located in the service area of other edge servers.Users located in the service area of other edge servers are easily overlooked.Therefore,for certifying the precision of proximity detection,each edge server reports these mobile users in the boundary region of the service area to the central server.Then,the central server uniformly performs proximity detection on these users and updates the detection results to the corresponding edge server.The central server does not directly communicate with users and the edge server still communicates with these users diametrically.That is to say,in the proximity detection architecture,proximity detection of most users is performed on each edge server,and only a small number of users need the central server to intervene.However,for most of the users whose proximity detection is directly performed by the edge server,or those that require the central server to intervene,they only exchange information with the edge server,in place of the central server.That ensures the low latency characteristics of the proximity detection architecture.

Figure 2 is the schematic diagram of computation offoading for proximity detection based on MEC.In road networks,there are a great number of users.Roads have two driving directions and we use solid lines to distinguish sub-roads in two directions on a road.We assume that all roads are either parallel to the X-axis or the Y-axis.We also assume that users have positioning devices and servers carry a map of the road network.We defne the speed of User 1 and User 2 asV1andV2,respectively.The time proximity threshold isTεandVmaxis the maximum speed of users.The service area of edge servers can be divided into two parts,non-border region and border region.

In the road network,if users are distributed in the non-border region of edge servers,they only need the corresponding edge server to take part in the detection process.For example,for User 1 in Figure 2,it is located in the non-border region of Edge Server 1.Edge Server 1 uses a selecting circle named the detection area of User 1 to select users which may be close to User 1,such as User 4.The center of circle is User 1,and the radius is(|V1|+|Vmax|)·Tε.The Edge Server 1 sends their information to User 1.Then,User 1 generates proximity detection computing tasks and offoads part of tasks to Edge Server 1 for computation.The remaining computing tasks are performed locally by User 1.After Edge Server 1 performs tasks completely,it sends the results to User 1.Finally,User 1 can know which users are close to him/her.

If users are located in the border region of edge servers,they need the corresponding edge server and the central server to participate in the process.First of all,edge servers need to send users’location and speed information within the detection area of User 2 to the Central Server.For example,for User 2 in Figure 2,it is located in the border region of Edge Server 1.The Central Server uses a selecting circle named the detection area of User 2 to select users,such as User 3 and User 5.The radius of this circle is(|V2|+|Vmax|)·Tεand the center is User 2.The Central Server sends their information to Edge server 1.After that,Edge server 1 transmits users’ location and speed information to User 2.Then,User 2 generates proximity detection tasks and simultaneously offoads part of tasks to Edge server 1,so as to reduce its own computing burden.The remaining tasks are performed locally by User 2.After Edge Server 1 performs tasks perfectly,it sends the results to User 2.Finally,User 2 can know which users are close to him/her.We can observe that User 3 is located in the service area of Edge Server 2 instead of Edge Server 1 and User 5 is located in the service area of Edge Server 1.The participation of the Central Server can ensure the accuracy of proximity detection of User 2 and avoid forgetting to consider users in the service area of other edge servers,such as User 3.

Figure 3.Schematic diagram of the special location of the dynamic road network.

IV.PROBLEM FORMULATION

In this section,to begin with,we present the system overview.Then,the communication model,local computing model,and edge computing model are introduced respectively.Moreover,the computing offoading problem in this complex scene is formulated into a CMOP.

4.1 System Overview

Figure 3 is the schematic diagram of the special location of the dynamic road network.We can see that there are many mobile users,several edge servers withras the serving radius and a central server in the road network.Mobile users are driving on the road at a constant speedV,communicating with the corresponding edge server in a wireless manner.Wired communication are setup between the central server and edge servers.The distance from the edge server to the inner boundary of the border region of its service area isr1.The border region is a circular ring,and the width of the ring is(|Vmax|+|Vmax|)·Tε.Since the traffc situation at the intersection is complicated and traffc accidents are prone to occur,we set a warning zone.The radius of the warning zone is(|Vmax|+|Vmax|)·Tεas well.For convenience,we call a mobile user who needs proximity detection as the target user.

LetAbe the total number of users andMbe the number of edge servers.Initially,the positions of all users are evenly distributed and the edge servers are located in the crossroads.We enumerate the set of edge servers bym={1,2,...,M}and the edge server is referred to asEm.LetUmbe the number of users in the service area ofEmandUm,jbe the jth(j ∈{1,2,...,Um})mobile user inEm’s service area.The computing capability of edge serverEmisFm.fm,j,pm,jdenote the computing capability,transmission power when offoading tasks ofUm,j,respectively.

The transmission time between the central server and edge servers is almost negligible[19]sincethey are connected through the wired communication.Compared to the data size of offoading tasks from users to the edge server,task execution results from the edge server to users is usually very small.Therefore,transmission time is shorter than the offoading time,and we also ignore it in this article[20].Moreover,we assume that the time for the central server to choose users can be ignored[21].

Therefore,in the whole computing offoading process,the energy consumption is only generated when tasks are executed locally and offoaded.The latency comprises transmission latency,local computing latency and MEC execution latency.On the basis of the above analysis,local computing,communication process,and edge server computing are modeled as follows.The primary notifcations used are listed in Table 1.

Table 1.Summary of key notations.

4.2 Communication Model

Let B be the total bandwidth and N be the number of channels with equal bandwidth.The communications between mobile users and edge servers adopt normally the orthogonal frequency through channels.Channel allocation is random and each user will be allocated a channel to communicate with the corresponding edge server.ForUm,j,part of tasks are offoaded to the corresponding edge server to reduce its own burden.According to the Shannon theorem,the uploading transmission rateRm,jcan be obtained as follows:

wheredm,jis the distance between mobile userUm,jand edge serverEm,pm,jis the transmission power of mobile userUm,j.σ2represents the background noise power,hrepresents the channel fading factor of the upload link,andεis the path loss factor.

The uploading transmission time iswhich can be obtained as follows:

whereDm,jis the total data size of tasks generated by mobile userUm,j.The edge serverEmuses a selecting circle to select users and sends their information to mobile userUm,j.The center of this circle is the target userUm,jand the radius is(|V m,j|+|Vmax|)·Tε.We defne that is the detection region of mobile userUm,j.We suppose that there areCm,jusers in the circle(excludingUm,jitself).Then the computing tasks can be divided intoCm,jsub-tasks.Denote the data size of a sub-task asDm,j,k,1≤k ≤Cm,j.Therefore,the total data size of tasks can be expressed as follows:

Assume that all users are driving in a straight line,regardless of turning situations.Consider that we have assumed that all roads are either parallel to the X-axis or the Y-axis.If the target user travels in the positive direction of the X-axis or the Y-axis,the speed is positive.Signifcantly,mobile users driving in the opposite direction on the same road will not be considered,as the target user does not need to perform proximity detection for these users.The reason is that although their geographical locations are very close,the two mobile users can not meet.In addition,the traffc situation near the intersection is complicated,and it is prone to collisions.If the target user is located in a circle with the edge serverEmas the center and(|Vmax|+|Vmax|)·Tεas the radius,we also need to consider oncoming vehicles on vertical roads.

We assume thatUl,iis in the detection region of the target userUm,j.The defnition of the network distance between two users at timetis the length of the shortest way between the two users along the roads[2],defned as the form ofD(Um,j,Ul,i).Suppose the coordinates ofUm,jandUl,iare(xm,j,ym,j)and(xl,i,yl,i),respectively.

We use the least time required by two users to meet each other to mean the time distance between two users at timet,defned asT(Um,j,Ul,i).Suppose the constant velocity ofUm,jandUl,iareVm,jandVl,i,respectively.

IfUl,iandUm,jare driving along the same road in the same direction,and the speed of the front carUm,jis lower than the speed of the rear carUl,i,then the time diatance can be expressed as follows:

IfUl,iandUm,jare driving along two perpendicular roads,then the time distance can be denoted as follows:

The value ofCm,jchanges over time.The system performs proximity detection every ΔTseconds.We take the pruning strategy into consideration to avoid repeated detection,and reduce latency and energy consumption.The pruning strategy is defned as follows.

Lemma 1.Pruning Strategy

1)If T(Um,j,Ul,i)-nΔT ＞Tε,then Um,j and Ul,i are not close within n detection time epochs.

2)If T(Um,j,Ul,i)+nΔT ＜Tε,then Um,j and Ul,i are close within n detection time epochs.

4.3 Local Computing Model

4.4 Edge Computing Model

whereFmis the computation capability of edge serverEm.In this article,we do not take the energy consumption of edge servers into consideration.

4.5 Problem Formulation

Finally,the joint optimization of latency and energy consumption for proximity detection is formulated as a CMOP which includes two objective functions,to minimize average energy consumptionEin Eq.(11)and average latencyTin Eq.(12).Some constraints are summarized as follows:

(i)PRm,jis the percentage of userUm,jperforming tasks locally,which needs to satisfy double-side constraints.

The optimization problemPcan be formulated as follows:

V.AN NSGA-II BASED SOLUTION

In all areas of the real world,multi-objective optimization is a familiar question.The functions of multiobjective optimization are mutually opposed,and it is impossible for each objective function to reach the best state at the same time.There are two most commonly used ways to solve such problems.

The frst way is to turn the multi-objective problem into one with only one single objective function,which is mainly based on the weighting idea.There are four main disadvantages: the selection of weighting coeffcients is subjective;multiple target units may be inconsistent,and it is not easy to compare them by forcing weighting together;the progress of the superiority of each goal in the optimization process is not operational;each goal restricts each other through decision variables,sometimes even contradictory goals,which makes the topological structure of the weighted objective function very complicated.

The second way is to obtain directly the Pareto set,which uses commonly the genetic algorithm[24].Because the Pareto set consists of a large number of optimal solutions,mobile users can make further decisions by own actual needs(which of energy consumption and latency is more important to users).In this way,the algorithms don’t need to rerun again even if users’demands change.By using the global search capability of genetic algorithm,we can maintain the diversity of individual solutions,instead of falling into the local optimal in the process.In fact,the genetic algorithm including NSGA-II and Multi-objective particle swarm optimization(MOPSO)has been proverbially utilized to settle this kind of problem[25–28].Therefore,in this article,we adopt NSGA-II to address the problemP.The NSGA-II algorithm is shown in Algorithm 1.

We now give the details of NSGA-II and use it to address the problemP.

1)Initialize the Four Main Parameters: the population sizeNP,the maximum number of iterationsG,the probability of crossoverCRand the probability of mutationPM.

Algorithm 1.NSGA-II.Input:The population size,NP.The probability of mutation,PM.The probability of crossover,CR.The maximum number of iterations,G.Output: Pareto optimal set.1: Generate an initial population.2: Compute multiple function values of each chromosome.3: Adopt the fast nondominated sorting method.4: Calculate the crowding distance.5: Sort the population based on Pareto ranks and crowding distance.6: Produce offspring population by selection,crossover,and mutation operations.7: Combine parent population and offspring population into new population.8: Compute multiple function values of each chromosome.9: Adopt the fast nondominated sorting method.10: Calculate the crowding distance.11: Create a new population based on elite selection strategy.12: If the number of iterations is equal to G,go back to Line 2.13: return Pareto optimal set.

2)Generate a Initial Population: The initial population consists ofNPchromosomes.Each chromosome represents all mobile users’ offoading decisions.In other words,the number of genes of each chromosome isA,which equals the number of users in the system.Each gene corresponds to one mobile user.The value of each gene is between 0 and 1,representing the percentage of tasks performed locally by the mobile user.

Moreover,we generate the population in three steps to maintain population diversity.First,we generate a chromosome in which all genes are 0.It means that all tasks are offoaded to the edge server for execution.Second,we produce a chromosome with all 1 genes.It means that all tasks are performed locally by the mobile user.Finally,the restNP-2 chromosomes are developed randomly.The initial population is shown in Figure 4.

Figure 4.Initial population.

3)Evaluate the Solutions: In this step,we evaluate each chromosome byEin Eq.(11)andTin Eq.(12).Among these,some chromosomes satisfy constraints in Eq.(16),and we call them feasible solutions.It is worth noting that there may be some chromosomes that don’t meet constraints in Eq.(16),and we call them infeasible solutions.

The value of constraint violation(CV)is generally used to describe the degree of constraint violation.For feasible solutions,the value ofCVis 0.For infeasible solutions,the value of constraint violation(CV)can be calculated as follows:

4)Fast Nondominated Sorting Approach: All chromosomes will be assigned Pareto ranks by stratifying the entire population.Individuals of the same Pareto rank are on the same level,as shown in Figure 5.The nondominated solutionxmeans that no other solutions dominate this solution in the population.Pareto front denotes the set of Pareto solutions.These nondominated solutions have the least confict of goals compared to other solutions and can be provided to decision makers with better choice space.Since the problemPis a constrained multi-objective optimization problem,we introduce the concept of Pareto Constraint-Dominance[28]frstly.

Figure 5.Schematic diagram of Pareto rank of solution space.

Definition 1.Pareto Constraint-Dominance: A solution x1constraint-dominates another solution x2if any of the conditions below is satisfied.

1)x1is a feasible solution and x2is an infeasible solution.

2)x1and x2are feasible solutions and x1≤x2.

3)x1and x2are infeasible solutions and CV(x1)≤CV(x2).

Fast nondominated sorting approach is a cyclic ftness grading process.First,fnd the nondominated solution set in the population,defne the individual Pareto rank as 1,and remove them from the entire population.Second,continue to look for the nondominated solution set from the remaining individuals,and defne their Pareto rank as 2.By analogy,the entire population is stratifed.We believe that the smaller the value of rank,the more powerful the solution.

5)Crowding Distance Calculation: The crowding distance(CD)is calculated to save the solutions with a lower degree of similarity.The obtained solutions are more evenly distributed in the target space,and the diversity of the solution space can be maintained.NSGA-II adopts a crowding strategy,which calculates the density of other individuals around a given individual in the same non-dominated front.To obtain the crowded distanceCDiof solutioni,we choose the two nearest solutionsi-1 andi+ 1 to form a rectangle.It is worth noting that solutionsi-1 andi+1 have the same front as solutionsi,as shown in Figure 5.Please note that,the boundary individuals of each non-dominated front are treated specially,and their crowded distances are all assigned the value of infnity.The formula is expressed as follows:

6)Tournament Selection:When the two individuals are not at the same non-dominated front,the individual is determined by judging the Pareto rank.When two individuals are at the same non-dominated front,the individual is judged based on the CD.The selection operation[18]is given as follows:

Theorem 1.Selection Operation

For any two solutions x1and x2,x1is superior to x2if any of the conditions below is satisfied.

1).

2).

Taking the Pareto rank and CD as a criterion,we select individuals from the population to make the parent population.(The parent population is to prepare for mutation and crossover operation in step 7).

7)Crossover and Mutation Operation: We adopt simulated binary crossover operator,which is suitable for encoding foating-point numbers.In this step,we randomly select two parentsx1andx2in the parent population and exchange their chromosomes with each other in a certain way to form two new offspringThe crossover operation is performed as follows:

wherenis the spread factor distribution index,anduis a uniform distribution random number in range[0,1).

After the crossover operation,the new individuals formed have a certain probability of genetic mutation.We select a chromosome to mutate randomly,and the probability of mutation determines whether to mutate.We adopt polynomial mutation in this step.

8)Generate New Population: The offspring population is generated after crossover and mutation operation in the previous step,which is evaluated by their objective function values and CV,as same as the way in the third step.We combine the parent population with the offspring population to construct an entire population.Then,we utilize the same way in step 4)and 5)to classify the entire population according to the Pareto rank and CD.According to elite selection strategy[18],we only select the bestNPindividuals from the entire population to creat a new parent population.

Theorem 2.Elite Selection Strategy

Generate a new parent population P1 from current population P according to the following rules.

1)According to the Pareto rank,population P are sorted from largest to smallest.We put the entire front of population P into new parent population P1,until a certain front of individuals cannot be put into new parent population P1 completely.

2)According to the CD,the individuals of this front are sorted from largest to smallest.They are placed in the new parent population P1 in turn,until the new parent population P1 is stuffed.

9)Judge the termination condition:If the number of iterations is equivlant toG,the frst front of population is exported,as the optimal solutions.If not,go back to Step 3).

The key procedure of NSGA-II is shown in Figure 6.

Figure 6.NSGA-II procedure.

VI.SIMULATION RESULTS

In this section,frst of all,the experimental environment is built.Then,we study the infuences of different parameters such as the time stamps,the number of mobile users,time proximity threshold,the number of iterations,so as to confrm the performance of NSGAII in solving the problemP.In addition,the effect of pruning strategy is also verifyed.

6.1 Experimental Setup

As shown in Figure 2,the central server is distributed in the network center,and the four edge servers are placed at the intersections of the roads.To begin with,the positions of all users are evenly distributed including the front and back directions of driving.Our assumptions are the number of mobile users is 480,the number of edge servers is 4,and the number of central server is 1.

Major simulation parameters are listed in Table 2.The four parameters used in NSGA-II are listed in Table 3.

Table 2.Simulation parameters.

Table 3.Parameters of NSGA-II.

6.2 Impacts of Time Stamps

Figure 7 shows the average latency and energy consumption optimized by NSGA-II with respect to the timet.Let the number of users be 480.The time threshold is 2s.

In Figure 7(a),during the 10 moments of movement,we can see that the Pareto front at each moment fuctuates.The number of users served by the edge server changes over time is the main reason for this fuctuation.In addition,considering the impact of pruning strategy,the number of users who need to be detected in the detection region of the target user may be different at each moment.Therefore,the Pareto front is different at each moment.

Additionally,it is manifest that the fuctuation range of the Pareto front gradually decreases and remains ba-sically unchanged after 8 seconds.From Figure 7(b)and Figure 7(c),we can get the same conclusions.

6.3 Impacts of the Quantity of Mobile Users

Figure 8 shows the average latency and energy consumption att=0 when the quantity of mobile users is 320,480,640,respectively.The time threshold is 2s.

With the increase of users,it can be observed that the range of Pareto optimal set becomes bigger,namely,the number of optimal solutions has also increased,which can be shown in Figure 8(a).The dimension of decision variables is equivlant to the number of users.The dimension of decision variables gets bigger,which is the principal reason.

In addition,we can fnd that the impact of the number of users on latency and energy consumption in Figure 8(b)and Figure 8(c).Obviously,the average latency and energy consumption increase with the increase of users.Logically speaking,the density of vehicles in the road network increases.The number of tasks requiring proximity detection and the total data size of tasks that need to be calculated has also increased for the target user.Therefore,the transmission latency,local execution latency,and MEC execution latency have become longer.

Observe that the energy consumption and the quantity of users is positively correlated.The reasons consist of two parts: 1)on the one hand,according to the model in Section IV,increasing the latency makes the energy consumption bigger simultaneously;2)on the other hand,the computation capability of the edge server is restricted.Some tasks have to be performed locally,when reaching the edge server’s storage capacityQd.Therefore,the energy consumption in performing tasks locally becomes higer.

6.4 Impacts of Time Proximity Threshold

Figure 9 shows the average latency and energy consumption att=0 when the time threshold is 2s,2.5s,3s,respectively.Let the number of mobile users be 480.

In Figure 9(a),all the while,observe that NSGA-II can fnd the Pareto set when time threshold varies.As the value of time threshold increases,the quantity of optimal solutions keeps increasing.

In Figure 9(b)and Figure 9(c),as the time proximity threshold increases,it can be seen that both the average latency and energy consumption increase,which can be shown in Figure 9(b)and Figure 9(c).Since the radius of the user’s mobile region is(|V|+|Vmax|)·Tε,the radius of the mobile region will become larger whenTεincreases,and the number of mobile users in the mobile region will also increase.Therefore,the number of tasks requiring proximity detection and the total data size of tasks generated by each mobile user will increase.The time proximity threshold have similar effects with the number of users.The effect of time proximity threshold is not very large compared with that of the quantity of users.

6.5 Impacts of the Number of Iterations

Figure 10 shows the average latency and energy consumption att=0 when the number of iterations is 10,50,100,150,respectively.Let the number of mobile users be 480.The time proximity threshold is 2s.

Figure 7.Impacts of time stamps.(a)Pareto front.(b)The latency with respect to different time stamps.(c)The energy consumption with respect to different time stamps.

Figure 8.Impacts of the quantity of mobile users.(a)Pareto front.(b)The latency with respect to different numbers of mobile users.(c)The energy consumption with respect to different numbers of mobile users.

Figure 9.Impacts of time proximity threshold.(a)Pareto front.(b)The latency with respect to different values of time proximity threshold.(c)The energy consumption with respect to different values of time proximity threshold.

Figure 10.Impacts of the number of iterations.(a)Pareto front.(b)The latency with respect to different number of iterations.(c)The energy consumption with respect to different number of iterations.

Figure 11.Impacts of pruning strategy.(a)Pareto front.(b)The latency with respect to use of pruning strategy.(c)The energy consumption with respect to use of pruning strategy.

In Figure 10(a),we can observe that both the average latency and energy consumption decrease slightly with the number of iterations.It is a remarkable fact that the Pareto set has a high coincidence degree after the number of iterations is identical to 100.When the number of iterations reaches a certain level,the infuence becomes very small.Therefore,we set the maximum number of iterations to be 100.As can be seen from Figure 10(b)and Figure 10(c),it can be noticed that the same conclusion can also be obtained.

6.6 Impacts of Pruning Strategy

Figure 11 shows the average latency and energy consumption at momentt= 1s when considering pruning strategies and no pruning strategies.The system performs proximity detection every one second.We take the pruning strategy into consideration to avoid repeated detection.The number of iterations is 100,the time proximity threshold is 2s and the number of users is 480.

In Figure 11(a),we can see that the average latency and energy consumption decrease drastically when considering pruning strategies.According to Figure 11(b)and Figure 11(c),the abscissa 0 represents considering no pruning strategies,and the abscissa 1 represents using pruning strategies.According to the pruning strategy,users that meet the requirements in the detection area of the target user do not need to be repeatedly detected.The target user can also judge whether the moving users are close at this moment.Therefore,for the target user,the number of users to be detected is greatly reduced and the total data size of tasks generated decreases at the same time.Therefore,the average latency and energy consumption of the system decrease.We can fnd that the pruning strategy plays a vital role in improving user experience.

VII.CONCLUSION

In this article,we investigated the joint latency and energy consumption optimization problem for proximity detection in road networks based on MEC.We built a communication model,an edge computing model and a local computing model in the system.Then,we formulated the joint optimization problem as a CMOP and solved it by NSGA-II algorithm.In addition,we adopted the pruning strategy based on time distance in dynamic road networks.Experimental results demonstrated that NSGA-II is able to fnd the Pareto optimal solutions,which can meet different requirements of users.

ACKNOWLEDGEMENT

This work is supported in part by the National Natural Science Foundation of China(Grant No.61901052),in part by the 111 project(Grant No.B17007),and in part by the Director Funds of Beijing Key Laboratory of Network System Architecture and Convergence(Grant No.2017BKL-NSACZJ-02).