A Caltech Library Service

Instantly decodable network coding for real-time device-to-device communications

Douik, Ahmed and Sorour, Sameh and Al-Naffouri, Tareq Y. and Alouini, Mohamed-Slim (2016) Instantly decodable network coding for real-time device-to-device communications. EURASIP Journal on Advances in Signal Processing, 2016 (1). Art. No. 1. ISSN 1110-8657.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


This paper studies the delay reduction problem for instantly decodable network coding (IDNC)-based device-to-device (D2D) communication-enabled networks. Unlike conventional point-to-multipoint (PMP) systems in which the wireless base station has the sufficient computation abilities, D2D networks rely on battery-powered operations of the devices. Therefore, a particular emphasis on the computation complexity needs to be addressed in the design of delay reduction algorithms for D2D networks. While most of the existing literature on IDNC directly extend the delay reduction PMP schemes, known to be NP-hard, to the D2D setting, this paper proposes to investigate and minimize the complexity of such algorithms for battery-powered devices. With delay minimization problems in IDNC-based systems being equivalent to a maximum weight clique problems in the IDNC graph, the presented algorithms, in this paper, can be applied to different delay aspects. This paper introduces and focuses on the reduction of the maximum value of the decoding delay as it represents the most general solution. The complexity of the solution is reduced by first proposing efficient methods for the construction, the update, and the dimension reduction of the IDNC graph. The paper, further, shows that, under particular scenarios, the problem boils down to a maximum clique problem. Due to the complexity of discovering such maximum clique, the paper presents a fast selection algorithm. Simulation results illustrate the performance of the proposed schemes and suggest that the proposed fast selection algorithm provides appreciable complexity gain as compared to the optimal selection one, with a negligible degradation in performance. In addition, they indicate that the running time of the proposed solution is close to the random selection algorithm.

Item Type:Article
Related URLs:
URLURL TypeDescription
Douik, Ahmed0000-0001-7791-9443
Sorour, Sameh0000-0002-3936-7833
Al-Naffouri, Tareq Y.0000-0001-6955-4720
Alouini, Mohamed-Slim0000-0003-4827-1793
Additional Information:© 2015 Douik et al. Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License(, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. Received: 1 June 2015 Accepted: 1 December 2015. First online: 04 January 2016. A part of this paper [28] is published in proc. of IEEE Vehicular Technology Conference (VTC-Fall’ 2014), Vancouver, BC, Canada.
Subject Keywords:Device-to-device communications Instantly decodable network coding Maximum weight clique
Issue or Number:1
Record Number:CaltechAUTHORS:20160128-103712754
Persistent URL:
Official Citation:Instantly decodable network coding for real-time device-to-device communications Ahmed Douik, Sameh Sorour, Tareq Y. Al-Naffouri and Mohamed-Slim Alouini EURASIP Journal on Advances in Signal Processing 2016, 2016:1 doi:10.1186/s13634-015-0293-z
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:64039
Deposited By: Ruth Sustaita
Deposited On:28 Jan 2016 23:17
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page