Low complexity and provably efficient algorithm for joint inter and intrasession network coding in wireless networks

Abdallah Khreishah, Issa Khalil, Jie Wu

    Research output: Contribution to journalArticlepeer-review

    10 Citations (Scopus)


    The performance of wireless networks can be enhanced by performing network coding on the intermediate relay nodes. To enhance the throughput of large wireless networks, we can decompose them into a superposition of simple relay networks called two-hop relay networks. Previously, the capacity region of two-hop relay networks with multiple unicast sessions and limited feedback was characterized where packet erasure channels are used. A near-optimal coding scheme that exploits the broadcast nature and the diversity of the wireless links was proposed. However, the complexity of the scheme is exponential in terms of the number of sessions, as it requires the knowledge of the packets that are received by any subset of the receivers. In this paper, we provide a polynomial time coding scheme and characterize its performance using linear equations. The coding scheme uses random network coding to carefully mix intra and intersession network coding and makes a linear, not exponential, number of decisions. For two-hop relay networks with two sessions, we provide an optimal coding scheme that does not require the knowledge of the channel conditions. We also provide a linear programming formulation that uses our two-hop relay network results as a building block in large lossy multihop networks.

    Original languageEnglish
    Article number6244791
    Pages (from-to)2015-2024
    Number of pages10
    JournalIEEE Transactions on Parallel and Distributed Systems
    Issue number10
    Publication statusPublished - 2013


    • Network coding
    • capacity
    • fairness
    • lossy wireless networks
    • two-hop relay networks

    ASJC Scopus subject areas

    • Signal Processing
    • Hardware and Architecture
    • Computational Theory and Mathematics


    Dive into the research topics of 'Low complexity and provably efficient algorithm for joint inter and intrasession network coding in wireless networks'. Together they form a unique fingerprint.

    Cite this