Social groups open up the opportunity for a new form of caching. This paper investigates how a social group of users can jointly optimize bandwidth usage, by each caching network-coded parts of the data demand, and then opportunistically share these parts among themselves upon meeting. First, the problem is formulated as a linear program (LP) with exponential complexity in the number of users. Then, a heuristic algorithm is proposed, which is inspired by the bipartite set-cover problem and operates in polynomial time. For some scenarios, a worst-case performance guarantee of the heuristic with respect to the optimal LP solution is proved. Finally, the performance of the algorithm is assessed using real-world mobility traces synthesized using the SWIM model and from the MIT Reality Mining project data set. The proposed heuristic offers bandwidth savings up to 65% for a waiting time of 30 minutes and up to 28% performance gains with respect to the alternative solutions. These benefits make the algorithm a feasible candidate solution for bandwidth savings.
Bibliographical noteFunding Information:
Manuscript received November 22, 2017; revised March 28, 2018 and May 20, 2018; accepted June 30, 2018. Date of publication July 10, 2018; date of current version November 16, 2018. M. Karmoose was supported by NSF under Award #1423271. At UCLA M. Cardone was supported by NSF under Award #1314937 and #1514531. This paper was presented in part at the 2016 IEEE International Symposium on Information Theory . The associate editor coordinating the review of this paper and approving it for publication was D. Wu. (Corresponding author: Mohammed Karmoose.) M. Karmoose and C. Fragouli are with the Electrical and Computer Engineering Department, University of California at Los Angeles, Los Angeles, CA 90095 USA (e-mail: firstname.lastname@example.org; email@example.com).
- Social networks
- network coding
- polynomial-time heuristic
- wireless networks