Performance characterization and transmission schemes for instantly decodable network coding in wireless broadcast

Mingchao Yu*, Parastoo Sadeghi, Neda Aboutorab

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    11 Citations (Scopus)

    Abstract

    We consider broadcasting a block of packets to multiple wireless receivers under random packet erasures using instantly decodable network coding (IDNC). The sender first broadcasts each packet uncoded once, then generates coded packets according to receivers’ feedback about their missing packets. We focus on strict IDNC (S-IDNC), where each coded packet includes at most one missing packet of every receiver. But, we will also study its relation with generalized IDNC (G-IDNC), where this condition is relaxed. We characterize two fundamental performance limits of S-IDNC: (1) the number of transmissions to complete the broadcast, which measures throughput and (2) average packet decoding delay, which measures how fast each packet is decoded at each receiver on average. We derive a closed-form expression for the expected minimum number of transmissions in terms of the number of packets and receivers and the erasure probability. We prove that it is NP-hard to minimize the average packet decoding delay of S-IDNC. We also prove that the graph models of S- and G-IDNC share the same chromatic number. Next, we design efficient S-IDNC transmission schemes and coding algorithms with full/intermittent receiver feedback. We present simulation results to corroborate the developed theory and compare our schemes with existing ones.

    Original languageEnglish
    Article number94
    Pages (from-to)1-17
    Number of pages17
    JournalEurasip Journal on Advances in Signal Processing
    Volume2015
    Issue number1
    DOIs
    Publication statusPublished - 1 Dec 2015

    Fingerprint

    Dive into the research topics of 'Performance characterization and transmission schemes for instantly decodable network coding in wireless broadcast'. Together they form a unique fingerprint.

    Cite this