Real-Time Cache-Aided Route Planning Based on Mobile Edge Computing

Route planning is considered as one of the fundamental technologies in the navigation system, which finds an optimal route between a pair of source and target locations. Navigation services are required to provide real-time responses to route planning queries to promote user experiences on the road under different situations, such as sudden detour, unpredictable traffic congestion and loss of GPS signals. However, most commercial navigation products search the optimal path at the remote central server which suffer from several inherent limitations. First, the communication between the access network and the remote central server has a large uncertain Internet-induced time delay. Second, the computational cost of retrieving an optimal path is increasing exponentially with the distance from the source location to the destination in a large-scale road network. To address the above issues, we propose a real-time Cache-Aided Route Planning System based on Mobile Edge Computing (CARPS-MEC), aiming to greatly shorten the communication and computation time of route planning queries by caching those frequently requested paths. Different from traditional cache based route planning algorithms which require an exact path matching from point to point, CARPSMEC makes a rough path matching from region to region. Thus, it only needs to process unmatched road segments on a MEC server which is closer to the end users. This will significantly reduce the transmission latency due to the uncertainty of the Internet. Experiment results demonstrate that CARPS-MEC can increase the cache hit ratio and reduce the response time greatly.