Graph-based optimal data caching in edge computing

In an edge computing environment, edge servers are deployed at base stations to offer highly accessible computing capacities and services to nearby users. Data caching is thus extremely important in edge computing environments to reduce service latency. The optimal data caching strategy in the edge computing environment will minimize the data caching cost while maximizing the reduction in service latency. In this paper, we formulate this edge data caching (EDC) problem as a constrained optimization problem (COP), prove that the EDC problem is NP -complete, propose an optimal approach named IPEDC to solve the EDC problem using the Integer Programming technique, and provide a heuristic algorithm named LGEDC to find near-optimal solutions. We have evaluated our approaches on a real-world data set and a synthesized data set. The results demonstrate that IPEDC and LGEDC significantly outperform two representative baseline approaches.