  This paper tackles the problem of transmitting a common content to a number
of cellular users by means of instantly decodable network coding (IDNC) with
the help of intermittently connected D2D links. Of particular interest are
broadcasting real-time applications such as video-on-demand, where common
contents may be partially received by cellular users due to packet erasures
over cellular links. Specifically, we investigate the problem of packet
completion time, defined as the number of transmission slots necessary to
deliver a common content to all users. Drawing on graph theory, we develop an
optimal packet completion time strategy by constructing a two-layer IDNC
conflict graph. The higher-layer graph permits us to determine all feasible
packet combinations that can be transmitted over the cellular link, while the
lower-layer graph enables us to find all feasible network coded packets and
identify the set of users that can generate and transmit these packets via
intermittently connected D2D links. By combining the higher-layer and the
lower-layer IDNC conflict graphs, we demonstrate that finding the optimal IDNC
packets to minimize the packet completion time problem is equivalent to finding
the maximum independent set of the two-layer IDNC conflict graph, which is
known to be an NP-hard problem. We design a scheme that invokes the
Bron-Kerbosch algorithm to find the optimal policy. To circumvent the high
computational complexity required to reach the global optimum, we establish a
polynomial-time solvable low-complexity heuristic to find an efficient
sub-optimal solution. The effectiveness of our proposed scheme is verified
through extensive numerical results which indicate substantial performance
improvement in comparison with existing methods.
