Network-Coded Macrocell Offloading in Femtocaching-Assisted Cellular Networks

Yousef N. Shnaiwer; Sameh Sorour; Parastoo Sadeghi; Neda Aboutorab; Tareq Y. Al-Naffouri

doi:10.1109/TVT.2017.2771416

Network-Coded Macrocell Offloading in Femtocaching-Assisted Cellular Networks

Yousef N. Shnaiwer^*, Sameh Sorour, Parastoo Sadeghi, Neda Aboutorab, Tareq Y. Al-Naffouri

^*Corresponding author for this work

Computer, Electrical and Mathematical Sciences and Engineering

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

10 Scopus citations

Abstract

Opportunistic network coding (ONC) has shown high potential in enhancing the quality-of-experience for the clients of cellular networks using their previously downloaded files. In this paper, we study the problem of offloading clients from the macrocell base station (MBS) with the help of femtocaches (FCs) and ONC. We formulate this MBS offloading problem as an optimization problem over an ONC graph, and prove that it is nondeterministic polynomial-time (NP)-hard. Thus, we propose an ONC-broadcast offloading scheme, which utilizes separate ONC graphs at the MBS and FCs in addition to uncoded broadcasting, to offload the clients from the MBS. We analyze the performance of the ONC-broadcast offloading scheme and show that it is asymptotically optimal using random graph theory. Since even this ONC-broadcast offloading scheme is still NP-hard to implement, we devise an efficient heuristic to simplify the implementation. We show that the proposed heuristic reduces the worst case complexity of implementing the ONC-broadcast offloading scheme from an exponential to a quadratic function of the total number of vertices in the FC ONC graph. Simulation results show that, despite its low complexity, the proposed heuristic achieves similar MBS offloading performance to the ONC-broadcast offloading scheme.

Original language	English (US)
Pages (from-to)	2644-2659
Number of pages	16
Journal	IEEE Transactions on Vehicular Technology
Volume	67
Issue number	3
DOIs	https://doi.org/10.1109/TVT.2017.2771416
State	Published - Mar 2018

Bibliographical note

Funding Information:
Manuscript received June 23, 2016; revised August 17, 2017; accepted October 25, 2017. Date of publication November 8, 2017; date of current version March 15, 2018. This publication is based upon work supported by the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research (OSR) under Award No. OSR-2016-KKI-2899. and in part by the Deanship of Scientific Research (DSR) at King Fahd University of Petroleum and Minerals (KFUPM), Dhahran, Saudi Arabia, through projects EE002355 and KAUST-002. The review of this paper was coordinated by Prof. N. Kato. (Corresponding author: Yousef N. Shnaiwer.) Y. Shnaiwer is with the Department of Electrical and Computer Engineering, King Fahd University of Petroleum and Minerals, Dhahran 30332, Saudi Arabia (e-mail: g201204420@kfupm.edu.sa).

Publisher Copyright:
© 1967-2012 IEEE.

Keywords

Femtocaching
conflict graph
macrocell offloading
opportunistic network coding (ONC)

ASJC Scopus subject areas

Aerospace Engineering
Applied Mathematics
Electrical and Electronic Engineering
Automotive Engineering

Access to Document

10.1109/TVT.2017.2771416

Cite this

@article{1734f5cf4f854d4f9da0b17d8dc8a0a3,

title = "Network-Coded Macrocell Offloading in Femtocaching-Assisted Cellular Networks",

abstract = "Opportunistic network coding (ONC) has shown high potential in enhancing the quality-of-experience for the clients of cellular networks using their previously downloaded files. In this paper, we study the problem of offloading clients from the macrocell base station (MBS) with the help of femtocaches (FCs) and ONC. We formulate this MBS offloading problem as an optimization problem over an ONC graph, and prove that it is nondeterministic polynomial-time (NP)-hard. Thus, we propose an ONC-broadcast offloading scheme, which utilizes separate ONC graphs at the MBS and FCs in addition to uncoded broadcasting, to offload the clients from the MBS. We analyze the performance of the ONC-broadcast offloading scheme and show that it is asymptotically optimal using random graph theory. Since even this ONC-broadcast offloading scheme is still NP-hard to implement, we devise an efficient heuristic to simplify the implementation. We show that the proposed heuristic reduces the worst case complexity of implementing the ONC-broadcast offloading scheme from an exponential to a quadratic function of the total number of vertices in the FC ONC graph. Simulation results show that, despite its low complexity, the proposed heuristic achieves similar MBS offloading performance to the ONC-broadcast offloading scheme.",

keywords = "Femtocaching, conflict graph, macrocell offloading, opportunistic network coding (ONC)",

author = "Shnaiwer, {Yousef N.} and Sameh Sorour and Parastoo Sadeghi and Neda Aboutorab and Al-Naffouri, {Tareq Y.}",

note = "Funding Information: Manuscript received June 23, 2016; revised August 17, 2017; accepted October 25, 2017. Date of publication November 8, 2017; date of current version March 15, 2018. This publication is based upon work supported by the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research (OSR) under Award No. OSR-2016-KKI-2899. and in part by the Deanship of Scientific Research (DSR) at King Fahd University of Petroleum and Minerals (KFUPM), Dhahran, Saudi Arabia, through projects EE002355 and KAUST-002. The review of this paper was coordinated by Prof. N. Kato. (Corresponding author: Yousef N. Shnaiwer.) Y. Shnaiwer is with the Department of Electrical and Computer Engineering, King Fahd University of Petroleum and Minerals, Dhahran 30332, Saudi Arabia (e-mail: g201204420@kfupm.edu.sa). Publisher Copyright: {\textcopyright} 1967-2012 IEEE.",

year = "2018",

month = mar,

doi = "10.1109/TVT.2017.2771416",

language = "English (US)",

volume = "67",

pages = "2644--2659",

journal = "IEEE Transactions on Vehicular Technology",

issn = "0018-9545",

publisher = "Institute of Electrical and Electronics Engineers",

number = "3",

}

TY - JOUR

T1 - Network-Coded Macrocell Offloading in Femtocaching-Assisted Cellular Networks

AU - Shnaiwer, Yousef N.

AU - Sorour, Sameh

AU - Sadeghi, Parastoo

AU - Aboutorab, Neda

AU - Al-Naffouri, Tareq Y.

N1 - Funding Information: Manuscript received June 23, 2016; revised August 17, 2017; accepted October 25, 2017. Date of publication November 8, 2017; date of current version March 15, 2018. This publication is based upon work supported by the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research (OSR) under Award No. OSR-2016-KKI-2899. and in part by the Deanship of Scientific Research (DSR) at King Fahd University of Petroleum and Minerals (KFUPM), Dhahran, Saudi Arabia, through projects EE002355 and KAUST-002. The review of this paper was coordinated by Prof. N. Kato. (Corresponding author: Yousef N. Shnaiwer.) Y. Shnaiwer is with the Department of Electrical and Computer Engineering, King Fahd University of Petroleum and Minerals, Dhahran 30332, Saudi Arabia (e-mail: g201204420@kfupm.edu.sa). Publisher Copyright: © 1967-2012 IEEE.

PY - 2018/3

Y1 - 2018/3

N2 - Opportunistic network coding (ONC) has shown high potential in enhancing the quality-of-experience for the clients of cellular networks using their previously downloaded files. In this paper, we study the problem of offloading clients from the macrocell base station (MBS) with the help of femtocaches (FCs) and ONC. We formulate this MBS offloading problem as an optimization problem over an ONC graph, and prove that it is nondeterministic polynomial-time (NP)-hard. Thus, we propose an ONC-broadcast offloading scheme, which utilizes separate ONC graphs at the MBS and FCs in addition to uncoded broadcasting, to offload the clients from the MBS. We analyze the performance of the ONC-broadcast offloading scheme and show that it is asymptotically optimal using random graph theory. Since even this ONC-broadcast offloading scheme is still NP-hard to implement, we devise an efficient heuristic to simplify the implementation. We show that the proposed heuristic reduces the worst case complexity of implementing the ONC-broadcast offloading scheme from an exponential to a quadratic function of the total number of vertices in the FC ONC graph. Simulation results show that, despite its low complexity, the proposed heuristic achieves similar MBS offloading performance to the ONC-broadcast offloading scheme.

AB - Opportunistic network coding (ONC) has shown high potential in enhancing the quality-of-experience for the clients of cellular networks using their previously downloaded files. In this paper, we study the problem of offloading clients from the macrocell base station (MBS) with the help of femtocaches (FCs) and ONC. We formulate this MBS offloading problem as an optimization problem over an ONC graph, and prove that it is nondeterministic polynomial-time (NP)-hard. Thus, we propose an ONC-broadcast offloading scheme, which utilizes separate ONC graphs at the MBS and FCs in addition to uncoded broadcasting, to offload the clients from the MBS. We analyze the performance of the ONC-broadcast offloading scheme and show that it is asymptotically optimal using random graph theory. Since even this ONC-broadcast offloading scheme is still NP-hard to implement, we devise an efficient heuristic to simplify the implementation. We show that the proposed heuristic reduces the worst case complexity of implementing the ONC-broadcast offloading scheme from an exponential to a quadratic function of the total number of vertices in the FC ONC graph. Simulation results show that, despite its low complexity, the proposed heuristic achieves similar MBS offloading performance to the ONC-broadcast offloading scheme.

KW - Femtocaching

KW - conflict graph

KW - macrocell offloading

KW - opportunistic network coding (ONC)

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

U2 - 10.1109/TVT.2017.2771416

DO - 10.1109/TVT.2017.2771416

M3 - Article

AN - SCOPUS:85033660725

SN - 0018-9545

VL - 67

SP - 2644

EP - 2659

JO - IEEE Transactions on Vehicular Technology

JF - IEEE Transactions on Vehicular Technology

IS - 3

ER -

Network-Coded Macrocell Offloading in Femtocaching-Assisted Cellular Networks

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this