标题： 即时解码网络编码的完成延迟最小化 显示英文标题

标题： Completion Delay Minimization for Instantly Decodable Network Codes

摘要： 本文中，我们研究了无线组播和广播场景下最小化即时解码网络编码（IDNC）完成延迟的问题。由于其诸多优点，如低解码延迟、低编码和解码复杂度以及简单的接收器需求，我们对该类网络编码感兴趣。 我们首先扩展了IDNC图，该图表示所有可行的IDNC编码机会，以在组播和广播场景中高效运行。 然后，我们将IDNC的最小完成延迟问题建模为随机最短路径（SSP）问题。 尽管使用SSP找到最优策略是不可行的，但我们利用这一公式来得出可以有效减少IDNC完成延迟的策略的理论指导原则。 基于这些指导原则，我们设计了一个最大权团选择算法，可以在多项式时间内有效地减少IDNC的完成延迟。 我们还设计了一个二次时间的启发式团选择算法，可以在实时应用中运行。 仿真结果显示，与随机和最大速率算法相比，我们提出的算法能够更有效地减少IDNC的完成延迟，并且在广播场景中几乎达到了所有网络编码的全局最优完成延迟性能。 显示英文摘要

摘要： In this paper, we consider the problem of minimizing the completion delay for instantly decodable network coding (IDNC), in wireless multicast and broadcast scenarios. We are interested in this class of network coding due to its numerous benefits, such as low decoding delay, low coding and decoding complexities and simple receiver requirements. We first extend the IDNC graph, which represents all feasible IDNC coding opportunities, to efficiently operate in both multicast and broadcast scenarios. We then formulate the minimum completion delay problem for IDNC as a stochastic shortest path (SSP) problem. Although finding the optimal policy using SSP is intractable, we use this formulation to draw the theoretical guidelines for the policies that can efficiently reduce the completion delay in IDNC. Based on these guidelines, we design a maximum weight clique selection algorithm, which can efficiently reduce the IDNC completion delay in polynomial time. We also design a quadratic time heuristic clique selection algorithm, which can operate in real-time applications. Simulation results show that our proposed algorithms efficiently reduce the IDNC completion delay compared to the random and maximum-rate algorithms, and almost achieve the global optimal completion delay performance over all network codes in broadcast scenarios.