2020/06/20 by Juwendo Denis, Denis, Juwendo, Hülya Seferoğlu +1
Computer Science · #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI)
paper · pdf · doi:10.48550/arxiv.2006.11606
openalex publication_date 2020/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper tackles the problem of transmitting a common content to a number\nof cellular users by means of instantly decodable network coding (IDNC) with\nthe help of intermittently connected D2D links. Of particular interest are\nbroadcasting real-time applications such as video-on-demand, where common\ncontents may be partially received by cellular users due to packet erasures\nover cellular links. Specifically, we investigate the problem of packet\ncompletion time, defined as the number of transmission slots necessary to\ndeliver a common content to all users. Drawing on graph theory, we develop an\noptimal packet completion time strategy by constructing a two-layer IDNC\nconflict graph. The higher-layer graph permits us to determine all feasible\npacket combinations that can be transmitted over the cellular link, while the\nlower-layer graph enables us to find all feasible network coded packets and\nidentify the set of users that can generate and transmit these packets via\nintermittently connected D2D links. By combining the higher-layer and the\nlower-layer IDNC conflict graphs, we demonstrate that finding the optimal IDNC\npackets to minimize the packet completion time problem is equivalent to finding\nthe maximum independent set of the two-layer IDNC conflict graph, which is\nknown to be an NP-hard problem. We design a scheme that invokes the\nBron-Kerbosch algorithm to find the optimal policy. To circumvent the high\ncomputational complexity required to reach the global optimum, we establish a\npolynomial-time solvable low-complexity heuristic to find an efficient\nsub-optimal solution. The effectiveness of our proposed scheme is verified\nthrough extensive numerical results which indicate substantial performance\nimprovement in comparison with existing methods.\n