Simplifying wireless social caching via network coding

Mohammed Karmoose, Martina Cardone, Christina Fragouli

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Article number8409444
Pages (from-to)5512-5525
Number of pages14
JournalIEEE Transactions on Communications
Issue number11
StatePublished - Nov 2018

Bibliographical note

Funding 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 [1]. 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:;

Publisher Copyright:
© 2018 IEEE.


  • Social networks
  • network coding
  • polynomial-time heuristic
  • set-cover
  • wireless networks


Dive into the research topics of 'Simplifying wireless social caching via network coding'. Together they form a unique fingerprint.

Cite this