Recently, network coding has been applied to the loss recovery of reliable multicast in wireless networks, where multiple lost packets are XOR-ed together as one packet and forwarded via single retransmission, resulting in a significant reduction of bandwidth consumption. In this paper, we first prove that maximizing the number of lost packets for XOR-ing, which is the key part of the available network coding-based reliable multicast schemes, is actually a complex NP-complete problem. To address this limitation, we then propose an efficient heuristic algorithm for finding an approximately optimal solution of this optimization problem. Furthermore, we show that the packet coding principle of maximizing the number of lost packets for XOR-ing sometimes cannot fully exploit the potential coding opportunities, and we then further propose new heuristic-based schemes with a new coding principle. Simulation results demonstrate that the heuristic-based schemes have very low computational complexity and can achieve almost the same transmission efficiency as the current coding-based high-complexity schemes. Furthermore, the heuristic-based schemes with the new coding principle not only have very low complexity, but also slightly outperform the current high-complexity ones.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Kaikai CHI, Xiaohong JIANG, Baoliu YE, Susumu HORIGUCHI, "Efficient Network Coding-Based Loss Recovery for Reliable Multicast in Wireless Networks" in IEICE TRANSACTIONS on Communications,
vol. E93-B, no. 4, pp. 971-981, April 2010, doi: 10.1587/transcom.E93.B.971.
Abstract: Recently, network coding has been applied to the loss recovery of reliable multicast in wireless networks, where multiple lost packets are XOR-ed together as one packet and forwarded via single retransmission, resulting in a significant reduction of bandwidth consumption. In this paper, we first prove that maximizing the number of lost packets for XOR-ing, which is the key part of the available network coding-based reliable multicast schemes, is actually a complex NP-complete problem. To address this limitation, we then propose an efficient heuristic algorithm for finding an approximately optimal solution of this optimization problem. Furthermore, we show that the packet coding principle of maximizing the number of lost packets for XOR-ing sometimes cannot fully exploit the potential coding opportunities, and we then further propose new heuristic-based schemes with a new coding principle. Simulation results demonstrate that the heuristic-based schemes have very low computational complexity and can achieve almost the same transmission efficiency as the current coding-based high-complexity schemes. Furthermore, the heuristic-based schemes with the new coding principle not only have very low complexity, but also slightly outperform the current high-complexity ones.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.E93.B.971/_p
Copy
@ARTICLE{e93-b_4_971,
author={Kaikai CHI, Xiaohong JIANG, Baoliu YE, Susumu HORIGUCHI, },
journal={IEICE TRANSACTIONS on Communications},
title={Efficient Network Coding-Based Loss Recovery for Reliable Multicast in Wireless Networks},
year={2010},
volume={E93-B},
number={4},
pages={971-981},
abstract={Recently, network coding has been applied to the loss recovery of reliable multicast in wireless networks, where multiple lost packets are XOR-ed together as one packet and forwarded via single retransmission, resulting in a significant reduction of bandwidth consumption. In this paper, we first prove that maximizing the number of lost packets for XOR-ing, which is the key part of the available network coding-based reliable multicast schemes, is actually a complex NP-complete problem. To address this limitation, we then propose an efficient heuristic algorithm for finding an approximately optimal solution of this optimization problem. Furthermore, we show that the packet coding principle of maximizing the number of lost packets for XOR-ing sometimes cannot fully exploit the potential coding opportunities, and we then further propose new heuristic-based schemes with a new coding principle. Simulation results demonstrate that the heuristic-based schemes have very low computational complexity and can achieve almost the same transmission efficiency as the current coding-based high-complexity schemes. Furthermore, the heuristic-based schemes with the new coding principle not only have very low complexity, but also slightly outperform the current high-complexity ones.},
keywords={},
doi={10.1587/transcom.E93.B.971},
ISSN={1745-1345},
month={April},}
Copy
TY - JOUR
TI - Efficient Network Coding-Based Loss Recovery for Reliable Multicast in Wireless Networks
T2 - IEICE TRANSACTIONS on Communications
SP - 971
EP - 981
AU - Kaikai CHI
AU - Xiaohong JIANG
AU - Baoliu YE
AU - Susumu HORIGUCHI
PY - 2010
DO - 10.1587/transcom.E93.B.971
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E93-B
IS - 4
JA - IEICE TRANSACTIONS on Communications
Y1 - April 2010
AB - Recently, network coding has been applied to the loss recovery of reliable multicast in wireless networks, where multiple lost packets are XOR-ed together as one packet and forwarded via single retransmission, resulting in a significant reduction of bandwidth consumption. In this paper, we first prove that maximizing the number of lost packets for XOR-ing, which is the key part of the available network coding-based reliable multicast schemes, is actually a complex NP-complete problem. To address this limitation, we then propose an efficient heuristic algorithm for finding an approximately optimal solution of this optimization problem. Furthermore, we show that the packet coding principle of maximizing the number of lost packets for XOR-ing sometimes cannot fully exploit the potential coding opportunities, and we then further propose new heuristic-based schemes with a new coding principle. Simulation results demonstrate that the heuristic-based schemes have very low computational complexity and can achieve almost the same transmission efficiency as the current coding-based high-complexity schemes. Furthermore, the heuristic-based schemes with the new coding principle not only have very low complexity, but also slightly outperform the current high-complexity ones.
ER -