Lightweight Instantly Decodable Network Coding: Performance Analysis and Algorithm Design

We consider broadcasting a block of data packets to multiple users via instantly decodable network coding (IDNC) under the semi-online feedback transmission mode. In this paper, we first introduce a new class of IDNC schemes called lightweight IDNC, tailored for wireless broadcast with stringent computational load at the receiver end. Unlike traditional IDNC that may encode a larger number of original packets together, lightweight IDNC limits each coded packet to a combination of at most two original packets. Explicit lower bounds of the total completion delay as well as the decoding delay are respectively obtained for arbitrary lightweight IDNC schemes. We further investigate the number of transmission rounds as another performance metric, and explicitly characterize its distribution and expectation. The characterizations apply to arbitrary partition-based IDNC schemes, including the lightweight IDNC schemes considered in this paper. A new efficient algorithm is also proposed to construct lightweight IDNC schemes which grants the original packets with lower coding opportunity a higher priority to be encoded. Numerical analyses demonstrate that the lightweight IDNC schemes constructed by the new algorithm not only achieve lower completion and decoding delays in comparison with the ones constructed by the existing algorithm but also adhere closely to theoretical lower bounds, demonstrating their efficiency and practical utility.