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.
Bibliographical noteFunding 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: email@example.com).
© 1967-2012 IEEE.
- conflict graph
- macrocell offloading
- opportunistic network coding (ONC)
ASJC Scopus subject areas
- Aerospace Engineering
- Applied Mathematics
- Electrical and Electronic Engineering
- Automotive Engineering