Fair Caching Algorithms for Peer Data Sharing in Pervasive Edge Computing Environments
Yaodong Huang, Xintong Song, Fan Ye, Yuanyuan Yang and Xiaoming Li
Stony Brook University, Peking University, Stony Brook University, Stony Brook University, Peking University

Edge devices (e.g., smartphones, tablets, connected vehicles, IoT nodes) with sensing, storage and communication resources are increasingly penetrating our environments. Many novel applications can be created when nearby peer edge devices share data. Caching can greatly improve the data availability, retrieval robustness and latency. In this paper, we study the unique issue of caching fairness in edge environment. Due to distinct ownership of peer devices, caching load balance is critical. We consider fairness metrics and formulate an integer linear programming problem, which is shown as summation of multiple Connected Facility Location (ConFL) problems. We propose an approximation algorithm leveraging an existing ConFL approximation algorithm, and prove that it preserves a 6.55 approximation ratio. We further develop a distributed algorithm where devices exchange data reachability and identify populate candidates as caching nodes. Extensive evaluation shows that compared with existing wireless network caching algorithms, our algorithms improves the 75-percentile fairness from 22.8% to 71.4%, while achieving contention thus latency similar as the best existing works.