Fair and Efficient Caching Algorithms and Strategies for Peer Data Sharing in Pervasive Edge Computing Environments

摘要

Edge devices with sensing, storage, and communication resources (e.g., smartphones, tablets, connected vehicles, and IoT nodes) are increasingly penetrating our daily lives. Many novel applications can be created through sharing data among nearby peer edge devices. In such applications, caching data at some edge devices can greatly improve data availability, retrieval robustness, and delivery latency. In this paper, we study the unique problem of caching fairness in edge computing environments. Due to the heterogeneity of peer edge devices, load balance is a critical issue that affects the fairness in caching. We propose fairness metrics to characterize this issue and formulate the caching fairness problem as an integer linear programming problem, which is shown as the summation of multiple Connected Facility Location (ConFL) problems. We provide an approximation algorithm by 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 information and identify popular candidates as caching nodes. Finally, we update the fairness metric and apply it to algorithms for making continuous caching decisions over time. Our extensive evaluation results show that compared with existing caching algorithms for wireless networks, our proposed algorithms significantly improve the data caching fairness while keeping the contention induced latency comparable to the best existing algorithms.