Simplifying wireless social caching via network coding

Mohammed Karmoose; Martina Cardone; Christina Fragouli

doi:10.1109/TCOMM.2018.2854786

Simplifying wireless social caching via network coding

Mohammed Karmoose, Martina Cardone, Christina Fragouli

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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 language	English (US)
Article number	8409444
Pages (from-to)	5512-5525
Number of pages	14
Journal	IEEE Transactions on Communications
Volume	66
Issue number	11
DOIs	https://doi.org/10.1109/TCOMM.2018.2854786
State	Published - 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: mkarmoose@ucla.edu; christina.fragouli@ucla.edu).

Publisher Copyright:
© 2018 IEEE.

Keywords

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

Access

10.1109/TCOMM.2018.2854786

OpenUrl availability

Full text

Cite this

@article{8987ef6e444d456f9f8878fecdcdf29e,

title = "Simplifying wireless social caching via network coding",

abstract = "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.",

keywords = "Social networks, network coding, polynomial-time heuristic, set-cover, wireless networks",

author = "Mohammed Karmoose and Martina Cardone and Christina Fragouli",

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: mkarmoose@ucla.edu; christina.fragouli@ucla.edu). Publisher Copyright: {\textcopyright} 2018 IEEE.",

year = "2018",

month = nov,

doi = "10.1109/TCOMM.2018.2854786",

language = "English (US)",

volume = "66",

pages = "5512--5525",

journal = "IEEE Transactions on Communications",

issn = "0090-6778",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "11",

}

TY - JOUR

T1 - Simplifying wireless social caching via network coding

AU - Karmoose, Mohammed

AU - Cardone, Martina

AU - Fragouli, Christina

N1 - 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: mkarmoose@ucla.edu; christina.fragouli@ucla.edu). Publisher Copyright: © 2018 IEEE.

PY - 2018/11

Y1 - 2018/11

N2 - 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.

AB - 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.

KW - Social networks

KW - network coding

KW - polynomial-time heuristic

KW - set-cover

KW - wireless networks

UR - http://www.scopus.com/inward/record.url?scp=85049809654&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049809654&partnerID=8YFLogxK

U2 - 10.1109/TCOMM.2018.2854786

DO - 10.1109/TCOMM.2018.2854786

M3 - Article

AN - SCOPUS:85049809654

SN - 0090-6778

VL - 66

SP - 5512

EP - 5525

JO - IEEE Transactions on Communications

JF - IEEE Transactions on Communications

IS - 11

M1 - 8409444

ER -

Simplifying wireless social caching via network coding

Abstract

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this