Research On Persistent Allocation Algorithm Based On Road Network In Cloud Computing Environment

With the development and maturity of ubiquitous computing technology,positioning technology,and wireless communication technology,resource assignment in mobile computing scenarios has become a new research hotspot,which is widely used in communication resource scheduling,emergency response,public resource planning and other fields.At present,in the mobile computing scenario of urban road networks,resource assignment is facing challenges such as large user terminal scale,high cost of assignment algorithm time,and high real-time requirements.In order to improve the overall efficiency of resource assignment.This thesis studies the continuous distribution problem based on the road networks in the cloud computing environment,and has achieved the following results:1.A heuristic algorithm for service resource assignment based on prediction of the location of moving objects in road networks is proposed to solve the problem of continuous service resource allocation based on limited service scope.The algorithm uses the client's motion characteristics with limited road networks at adjacent moments to predict the location of the client at the next moment,and then uses a heuristic algorithm to estimate the distribution relationship at the next moment based on the prediction result,and finally compares the forecast based on the actual data at the current moment.The estimated distribution relationship is adjusted to obtain the final distribution result.Experiments on real data sets show that the algorithm can quickly realize the effective assignment of service resources.2.A parallel algorithm for continuous service resource assignment based on limited service scope is proposed.The algorithm uses the Spark Streaming cloud computing framework to divide data according to spatial attributes.In the position prediction stage,the Map function is used to divide the client snapshots at adjacent moments,and the Reduce function is used to calculate the next moment position;the Map function is used to divide the bipartite graph in the estimated assignment relationship stage,and the Reduce function is used to resolve conflicts;in the assignment relationship adjustment stage The Map function distributes the current snapshot and estimated distribution results,and uses the Reduce function to modify the distribution relationship.Experiments on the cloud computing platform show that the parallel algorithm has a significant efficiency improvement for the single machine algorithm.3.An incremental update algorithm for K-selected service resource assignment in road networks is proposed to solve the problem of K-selected service resource assignment.The algorithm uses the Voronoi diagram to divide the road networks and builds an inverted index to speed up the neighborhood query on the server.Then use the neighbor relationship to evaluate the potential contribution value of the server,and then combine the results of the previous moment to filter the current server set to obtain a smaller candidate set.Finally,a heuristic algorithm is used to obtain the final Kselected assignment result.Experiments on real data sets show that the algorithm can quickly and effectively allocate service resources.4.A parallel algorithm of K-selected continuous service resource assignment is proposed.The algorithm uses the Spark Streaming cloud computing framework to divide the data according to the Voronoi divided road networks structure.In the stage of filtering the candidate set,the Map function is used to divide the Voronoi area of the server,the Reduce function is used to calculate the potential contribution value of each server,and then the filter function is used to filter the candidate set.In the precise calculation stage,the Map function is used to divide the assignment relationship,the Reduce function is used to allocate the clients that need to be re-allocated,and the assignment result is obtained iteratively.Experiments on the cloud computing platform show that the parallel algorithm has a significant efficiency improvement for the single machine algorithm.