Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 4, 2016 | Published
Journal Article Open

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

Abstract

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.

Additional Information

© 2015 Douik et al. Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License(http://creativecommons.org/licenses/by/4.0/), 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.

Attached Files

Published - s13634-015-0293-z.pdf

Files

s13634-015-0293-z.pdf
Files (711.0 kB)
Name Size Download all
md5:09e06beee03d698e74e8ceeb022c3c8c
711.0 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 17, 2023