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
Name | Size | Download all |
---|---|---|
md5:09e06beee03d698e74e8ceeb022c3c8c
|
711.0 kB | Preview Download |
Additional details
- Eprint ID
- 64039
- Resolver ID
- CaltechAUTHORS:20160128-103712754
- Created
-
2016-01-28Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field