Edge Server Placement For Vehicular Ad Hoc Networks in Metropolitans

Edge computing pushes computation and storage resources to the network edge which is close to end users, and thus is critical for latency-sensitive applications, e.g., intelligent Vehicular Ad Hoc Networks (VANETs). To enable these services, a set of edge servers need to be deployed to the roadsides. Such deployment should offer low-latency services to end users, while keeping a low deployment or maintenance cost, which is a non-trivial task. In this paper, we study the edge server placement problem in a metropolitan area. This problem is composed of two parts: to determine 1) the locations of the servers and 2) the coverage of each server, with multiple optimization objectives. First, we study the Shanghai Taxi Trace to gain insights into the traffic pattern of taxis, especially how vehicles move between different locations. Second, we build multi-objective optimization models to characterize the trade-off among three critical performance metrics, namely the initial deployment cost, the runtime cost (i.e., number of hand-offs between different servers), and the average delay of tasks. Due to the intractability of these NP-hard problems, we propose a heuristic multi-objective optimization method to decompose the global problem into a set of local problems with tractable scale. Numerical results verify that our heuristic strategy achieves a desirable balance among the three performance metrics, e.g., a 5% compromise of the delay can reduce up to 50% of the hand-offs for small local areas, and 10%+ for the entire global area, compared with the best existing algorithms.