具有线性独立数据分组编码的可靠多播

摘要

调度常规数据分组以便在多播ARQ系统中从发送器传输到多个接收器。在联合调度和编码过程中，复合数据分组形成为常规数据分组的加权线性组合。基于来自接收器有关接收的数据分组的反馈信息，调整对应的编码权重，使得复合分组表示常规数据分组的新的线性独立编码，不同于在多播会话期间由选定的接收器集合中每个接收器以前接收的任何多播数据分组。另外，使用具有至少两个不同的非零编码权重的权重向量添加了更多的自由度，并且保证能够始终形成表示新线性独立编码的复合数据分组以便传输。在至少大部分传输实例中传送线性独立数据分组的能力将大大提高可靠多播的吞吐量性能，特别是在用户数量大时。

说明书

技术领域

本发明一般涉及多播通信系统，并且更具体地说，涉及用于多播 传输的调度分组和编码分组的新颖策略。

背景技术

一般而言，对于通信系统中，且具体而言，对于无线网络中改进 性能的需求在不断增长。多播是通过将相同信息有效地传送到多个用 户/接收器而提高吞吐量的一种方案。信道不可靠时，不可能可靠地将 数据输送到所有接收器。因此，通过不可靠信道的多播一般要求使用 前向纠错(FEC)技术或后向纠错技术，如自动重发请求(ARQ)。

所谓的喷泉编码是用于可靠多播的一种令人感兴趣的方案[1-2]。 喷泉编码是理想的低比率(rate-less)数据编码方案，一种FEC形式， 它产生新的奇偶信息，直至所有用户已将发送的数据文件解码。理想 的喷泉码近似值是所谓的Tornado码和LT码。其它喷泉码包括所谓 的Tornado码和联机码(Online codes)。在其中形成新奇偶信息的LT 码中(以及通常在大多数喷泉码中)，基本理念是基于随机选择编码 程度，即，根据预定义程度分布然后按位对分组进行异或处理(模2 加法)要一起编码的分组数量。虽然不是固有的喷泉编码的一部分， 但确认一般在接收器接收了能够实现编码的充足数量的奇偶分组时 发送，而不是在该时间之前。因此，对于FC文件，每个用户只需一 次确认。在需要接收比数据大致多ε数额冗余的删除信道中，FC的那 些近似值能够实现有效的多播。

ARQ是用于数据传输的一种有效差错控制策略，其中，接收器检 测消息中的传输差错，并自动请求从发送器重新传输。通常，从接收 器到发送器的反馈消息用于使发送器能够确定预期接收器正确收到 了哪些分组，哪些分组未正确收到。已正确收到的分组必须重新发送。

ARQ被提议用作在蜂窝无线通信系统中通过空中接口的通信的 标准，并且也能够在多跳系统中使用。一般情况下，信息在传输前被 分成称为协议数据单元(PDU)的更小分组。通过使用检错码将分组 编码，能够实现可靠的传递，使得接收器能够检测错误或丢失的分组， 并由此请求重新传输。数据序列完整性一般通过分组的按序编号和应 用某些传输规则而得以保证。

可有用的是在论述有关多播ARQ的细节前，先回顾基于单播的 ARQ的基本原理，记住单播ARQ的基本原理大部分转入多播ARQ。

在通常称为停止并等待ARQ的最简单形式的ARQ中，数据的发 送器存储每个发送的数据分组，并等待接收器通过确认消息(ACK) 的有关正确收到的数据分组的确认。收到ACK时，发送器丢弃存储 的分组并发送下一分组。该过程一般补充有计时器和否定确认消息 (NACK)的使用。发送实体使用在数据分组传输时启动的计时器， 如果在计时器计满前未收到ACK(或NACK)，则重新传送数据分组。 如果接收器检测到分组中的错误，则它能向发送器发送NACK。在接 收NACK时，发送器重新传送数据分组而不等待计时器计满。如果 ACK或NACK消息丢失，则计时器将最终计满，并且发送器将重新 传送数据分组。

从简单的停止并等待中，已形成了常规ARQ的更成熟的方案， 例如，提供更高吞吐量的回退N(Go-Back-N)和选择性拒绝(或选 择性重发)。

在ARQ发展的另一方面，以各种方式利用编码中的冗余以增强 通信性能(一般作为吞吐量度量)。这些方案称为混合ARQ方案。 编码和ARQ的组合，混合ARQ方案能够对例如衰退等无线电环境中 的变化提供一定的适应性。在混合1ARQ中，FEC与ARQ组合。在 混合2ARQ中，发送或多或少带有FEC编码的PDU，但附带有循环 冗余检验(CRC)以便在解码后检查误码的存在，并且如果请求重新 传输，则发送由FEC编码器、系统比特或两者的组合生成的奇偶校验 比特(也称为冗余比特)。

如果效率不是主要目标，则多个并行单播ARQ过程可用于确保 可靠的“多播”。在多播组大小即预期接收器的数量小时，这可以是常 见的方案。然而，对于更大的组，这是效率低的通信方式。因此，一 般情况下考虑更有效地将并行单播过程合并成单个所谓的多播ARQ 过程，其中，相同的信息传送到多个用户[3]。

参考文献[4]涉及性能优化以实现可靠的多个单播流。

参考文献[5-7]描述方案，其中，相同的数据多播到多个用户，并 且有效的重新传输通过将不同接收器否定确认(NACK)的若干分组 组合成单个块而能够实现。

传统多播ARQ有关的问题一般在于在用户数量大时性能极差。 实际上，注意到且易于认识到的是在用户的数量K趋于无限时，吞吐 量效率趋于零。

虽然喷泉编码减轻了传统多播ARQ中的性能问题，但其性能大 致为T＝p/(1+ε)，其中，T是吞吐量效率，ε取决于正在发送的数据量， 并且p是接收概率。在[2]中，大致指出1+ε超过1.06的概率1/10，在 所谓的Tornado Z码实现的10000次试验中不超过1.10。另外，指出 的是Tornado码在商业应用的解码低效率方面没有足够的紧界，并且 对于LT码的当前商业数字喷泉实现，几乎任何大小的源文件的解码 无效(decoding inefficiency)不超过1.05的概率小于10。

在喷泉编码中有几个缺陷。FC依赖通过过度供应冗余信息来在统 计上确保可解码性，并且不依赖确定性可解码性。首先，一般需要大 量的信息以获得小的ε值，并且在只传递少量数据分组时，性能一般 很差。将输送的数据解码的时间相当长，这是因为在能够保证可解码 性前，需要接收所有冗余。LT码是喷泉码的一种形式，也已知为具 有至少在一定程度上由象Tornado码等其它FC已遇到的坏的差错基 数行为。

虽然参考文献[5-7]中提议的方案代表了在具有确定性可解码性的 多播ARQ的正确方向中的步骤，但这些方案仍未提供最佳性能。此 方面的一个原因是传统的多播ARQ操作比需要的更静态，并且无法 识别和利用所有的自由度。

因此，可靠多播普遍需要一种甚至更具吞吐量效率的策略。

发明内容

本发明克服了先有技术装置的这些和其他缺陷。

本发明的一般目的是为可靠多播提供一种高吞吐量效率的策略。

本发明的目的是提供一种用于对数据分组进行调度和编码以便在 多播会话中从多播ARQ系统中发送器传输到至少两个接收器的方法 和装置。

还有一个目的是提供适用于在多播ARQ系统中使用的发送器。

一个特定的目的是提供一种使增强的吞吐量、降低的延迟和/或降 低的能耗能够实现的多播策略。

特别希望的是提供一种使编码的分组的确定性可解码性能够实现 的多播策略。

这些和其它目的由如随附专利权利要求定义的本发明实现。

本发明一般涉及数据分组的调度和编码以便在多播会话中从多播 ARQ系统中发送器传输到至少两个接收器的多播组。

本发明的基本构想是在多个调度实例的每个实例执行如下过程，

包括通过使用来自接收器、指示收到的数据分组的反馈信息，基于包 括一组编码权重的对应权重向量，形成作为常规数据分组的加权线性 组合的至少一个复合数据分组，以及将形成的复合数据分组传送到考 虑的多播组的接收器。在此过程中，基于反馈信息，为每个复合数据 分组调整权重向量的编码权重，使得复合分组表示常规线性组合，对 于至少一组所述接收器的每个接收器，该组合线性独立于考虑的多播 会话期间接收器以前收到的任何数据分组。

通过结合多个调度实例的每个实例执行此过程，将降低给定量的 多播信息的传递所需的传输次数。

在多播会话期间在至少大部分传输实例中传送新线性独立数据分 组(传送复合数据分组及可选地传送常规分组)的能力将大大提高可 靠多播的吞吐量性能，特别是在用户数量大时。

在理想的情况下，系统地传送多个常规和/或复合数据分组，而这 些分组线性独立于多播会话期间由一组接收器中包括的每个接收器 以前收到的任何数据分组(常规的或复合的)时，将足以只发送N个 此类数据分组来重新获得所有N个常规数据分组，从而获得了最大吞 吐量。

任何情况下，与常规多播ARQ相比，本发明需要从发送器发送 更少的数据分组到接收器以便确保正确接收传送的数据分组。

本发明因此能够实现提高的吞吐量效率以实现(完全)可靠多播， 并且也提供确定性的可解码重新传输方案。

例如，在喷泉编码中，为了将全部文件解码的而需要接收的子分 组的数量是个随机变量，即，未受到确定性限制。

本发明提供一种实现上述方案的系统及适于在多播ARQ系统中 使用的对应发送器。

本发明一般适用于在诸如无线通信系统等具有不可靠链路的通信 系统中的多播ARQ。例如，本发明可在具有与多个移动终端通信的基 站的典型蜂窝系统中得到有利的利用。

本发明可提供以下优点：

·可靠多播。

·增大(或甚至最大)的吞吐量。

·降低(或甚至最低)的等待时间。

·提高的能源/能量利用率。

·有关为实现可解码性而需要接收的分组数量的确定性范围。

在阅读本发明实施例的下面说明时，将理解本发明提供的其它优 点。

附图说明

通过结合附图，参照以下说明，可最好地理解本发明及其其它目 的和优点，其中：

图1示出完全可靠多播ARQ的吞吐量效率，K＝1，2，4，8，16， 32，64和128，随正确接收的概率而变化。

图2是示出多播ARQ系统概述的简单示例的示意框图。

图3是示出示范总体ARQ过程的示意流程图。

图4是根据本发明的优选示范实施例，用于对常规数据分组进行 调度并将其编码成复合数据分组的方法的示意流程图。

图5示出将两个常规数据分组编码成一个复合数据分组的可能实 施例。

图6是示出根据本发明的优选示范实施例，用于将数据分组从发 送器多播传输到多个用户的系统的示意框图。

图7是根据本发明的示范实施例的数据分组调度和编码的示意框 图。

具体实施方式

在所有附图中，相同的标号将用于相同或类似的要素。

在下文中，术语“常规数据分组”表示普通(非复合)数据分组(即， 只是完全普通的数据分组)，而复合数据分组是基于至少两个常规数 据分组。“多播数据分组”能够是常规数据分组或复合数据分组，并且 其最普通的意义中，此类数据分组可称为“一般数据分组”、“多播数据 分组”或“一般多播数据分组”。

传统多播ARQ有关的问题一般在于在接收器/用户数量K大时性 能极差。图1示出作为正确接收概率的函数的完全可靠多播ARQ的 吞吐量效率，K＝1，2，4，8，16，32，64和128。最左边曲线示出 K＝1的情况。正如能够看到的一样，性能随着节点数量K的增大而降 低，并且在节点数量接近无限大时接近零，但在正确接收的概率等于 1时的特殊理想情况下除外。

因此，普遍需要一种吞吐量效率更高的策略来实现可靠多播。

以多播ARQ系统的简要概述开始将有所益处。在与本发明配合 使用的ARQ通信系统中，如图2以示意图方式所示，发送器100一 般参与跟多个接收器200的多播通信会话。发送器100通常表示为发 送节点，如发射操作中的基站，并且接收器200-1到200-K通常表示 为接收节点，例如，通过在接收操作中的移动终端实现。应注意的是， 例如移动终端也能够充当发送节点，并且基站也能够充当接收节点。 在多播通信中，相同的信息集合通常发送到多播组的所有接收器部 分。多播组一般包括至少两个接收器，有时称为用户。对于在多播会 话中的多个数据分组的传输，这一般意味着每个单独的数据分组是预 期用于所有考虑的接收器的所谓多播数据分组。应注意的是，如果通 信预期针对例如小区或系统内的所有用户，这经常称为广播而不是多 播。因此，广播只是小区或类似区域中所有接收器接收数据的多播的 极端情况。

本发明可在具有与多个移动终端通信的基站的典型蜂窝系统中得 到有利地利用。通常，多种调度方案可在此类系统中利用以增强性能， 并且ARQ用于提高传输的可靠性。

本发明将在无线情形中描述，但同样也可在具有不可靠链路的其 它通信情形中使用。

本发明的基本构想在于在多个调度实例的每个实例执行如下过 程，包括通过使用来自接收器、指示收到的数据分组的反馈信息，基 于包括某个编码权重集合的对应权重向量，形成作为常规数据分组的 加权线性组合的至少一个复合数据分组，以及将形成的复合数据分组 传送到考虑的多播组的接收器。在此过程中，优选基于反馈信息，为 每个复合数据分组适应性地选择权重向量的编码权重，使得复合分组 表示常规数据分组的线性组合，该组合线性独立于在多播会话期间由 多播组的相关接收器集合中每个接收器以前收到的任何数据分组(常 规或复合)。

上述相关接收器集合一般包括至少两个接收器，并且可以是总体 多播组中接收器的子集或全集。

“以前接收的数据分组”一般指在接收器侧已正确解调和FEC解码 的多播数据分组(常规的或复合的)。

通过在多个(两个或更多个)调度实例的每个实例执行此过程， 并传送新线性独立数据分组(复合数据分组及可能的常规数据分组)， 将降低传递给定量多播信息的传送所需的传输次数，并且将提高可靠 多播的吞吐量性能。

正如技术人员将理解的一样，在编码权重的调整中要考虑的相关 接收器/用户集合将随着多播会话进展而变化，并且一个调度实例与下 一调度实例可不同。一旦接收器接收所有多播数据分组，此接收器便 将不再被考虑。通常，只有仍需要接收一个或多个多播数据分组的接 收器被考虑为多播组的相关集合。这意味着在整个多播会话期间，在 调度过程(即，权重调整)中考虑的相关接收器集合将逐渐变小，直 至所有接收器接收到所有多播信息。

本发明者认识到基于选定接收器集合中每个接收器以前接收的分 组集合来调整编码权重的重要性，而不是如在现有技术中一样，如果 除一个外所有接收器收到了所有分组，则选择为其应用静态的全然相 同(all-one)的代码向量的接收器子集。

正如后面将详细解释的一样，线性独立数据分组编码的构想能够 根据增大权重向量(包括编码权重)的矩阵的秩进行描述。更具体地 说，对于每个接收器，以前收到的多播数据分组(常规和/或复合数据 分组)能够描述为基于权重向量的矩阵的线性方程组。秩的增大对应 于在权重向量的矩阵中形成新线性独立行，这相当于多播数据分组的 新线性独立编码。

为更好地理解本发明，考虑一个说明性示例可能有所帮助。假设 有一个发送器，具有要传送给两个接收器/用户U₁和U₂的两个常规数 据分组。下面的表I示出根据本发明的示范实施例的可能的传输/重新 传输情形的示例。例如，编码集“001”意味着第一常规分组乘以编码权 重0，第二常规分组乘以编码权重0，以及第三常规分组乘以编码权 重1，有效地表示只传送第三常规分组。同样地，对于用户，“001”表 示此特定用户收到了第三常规数据分组，而对于用户，“X”表示该用 户未正确收到信息。

表I

表I的示例示出两个用户在接收三个分组。要注意的是，通常只 先接收常规分组和单个复合分组不足以实现所有常规数据分组的解 码。相反，示出的是发送器需要适应性地选择代码权重，并且在此特 定示例中，它在每个步骤执行此操作，使得如果所有相关用户将接收 复合分组，则每个用户的接收器特定矩阵的秩将为其增大。如本文所 述，权重的调整，而不是如现有技术文档[5-7]中所述调整单个复合分 组被发送到的用户集合，从根本上增强了性能。另外，参考文献[5-7] 未采用用户特定矩阵进行调度和编码。还要注意的是，参考文献[5-7] 中，发射方未以可使接收器能够并发使用多个复合分组进行解码的此 类方式发送分组。

在此示例中，也能够注意到，在一个用户已经接收充足数量的数 据分组、常规数据分组和复合数据分组，并且对应矩阵的秩已满时， 不再必需或甚至不再可能进一步增大该接收器的矩阵的秩。因此，在 确定为剩余非满秩矩阵接收器确保秩增大的适合的代码权重中，只考 虑非满秩矩阵。假设调整在第一调度实例的复合数据分组的编码权 重，使得对于第一接收器集合中的每个接收器，复合分组表示线性独 立于在多播会话期间接收器以前接收的任何数据分组的线性组合。在 以后的第二调度实例，因此可调整另一复合数据分组的编码权重，使 得对于更少的第二接收器集合的每个接收器，复合分组表示线性独立 于在多播会话期间接收器以前所接收的任何数据分组的线性组合。

在更现实的情形中，用户的数量和数据分组的数量必然将经常增 大，但以下简化示例用于示出本发明的关键特性。在实际应用中，用 户/接收器的数量K能够是从二到可能一百或更大的任何数字。

例如诸如分组A和分组B等两个常规数据分组的线性组合通常只 表示分组以相等加权组合，从而有效地使用相同的编码权重“1”。未在 线性组合中考虑的那些常规数据分组(如分组C和分组D)能够被视 为具有编码权重“0”。

在某些情况下，特别是在多播组包括三个或更多个用户时，选择 具有至少两个不同的非零编码权重的权重向量的可能性将增强(以及 在大多数情况下保证)形成表示常规数据分组的新线性独立编码的复 合数据分组的能力，该复合数据分组不同于在多播会话期间由作为选 定接收器集合一部分的每个相关接收器以前接收的任何数据分组(常 规数据分组或复合数据分组)。

假设有一个发送器，具有要传送到三个接收器/用户U₁、U₂和U₃的两个常规数据分组。下面的表II示出根据本发明的另一示范实施例 的可能传输/重新传输情形的示例。例如，编码集“01”表示第一常规分 组乘以编码权重0，第二常规分组乘以编码权重1，有效地表示只传 送第二常规分组。同样地，对于用户，“01”表示此特定用户接收了第 二常规数据分组，而对于用户，“x”表示该用户未正确接收信息。

表II

参照下面的表III，将描述仍有的传输情形的另一示例。在此特定 示例中，我们假设有一个发送器，具有要传送到三个接收器/用户U₁、 U₂和U₃的三个常规数据分组。

表III

要注意的是，在表II中，每个用户只接收可能是复合数据分组、 常规数据分组或两者的组合的两个不同的数据分组。也能够确认的 是，因为已确保在每次传输中保证每个用户接收常规数据分组的新线 性组合，所以，每个用户能确定两个常规数据分组。这同样适用于表 I和表III。

如上所述，适应性地选择具有至少两个不同非零编码权重的权重 向量的特殊可能性增强了始终形成常规数据分组的新线性独立编码 的复合数据分组的能力，该复合数据分组不同于在多播会话期间由所 有接收器的全部或其相关子集的每个接收器以前接收的任何数据分 组(常规数据分组或复合数据分组)。在某些情况下，特别是在用户 的数量大时，由于在多播会话期间在至少大部分传输实例中为每个接 收器传送新线性独立数据分组(常规和/或复合数据分组)的能力将大 大提高可靠多播的吞吐量性能，因此，这可能很重要。

通常，通过系统地传送多个多播或普通数据分组(常规和/或复合 数据分组)，而这些分组线性独立于多播会话期间该接收器集合以前 接收的任何多播数据分组(常规数据分组或复合数据分组)，则将足 以只发送N个此类数据分组以重新获得所有N个常规数据分组，从而 获得了最大吞吐量。然而，如果接收器接收只基于N个常规数据分组 的超过N个数据分组，则它将仍只可能重新获得N个常规数据分组。

与常规多播ARQ相比，本发明需要从发送器发送更少的多播数 据分组到接收器以便确保正确接收传送的数据分组。本发明提供了一 种可靠多播策略，具有关于为了实现可解码性而需要接收的分组数量 的确定性区间。

在本发明的示范实施例中，也可能在给定调度实例形成多个数据 分组，并在突发中传送多个复合分组。在此类调度实例中，多个复合 数据分组通常使用相同的反馈信息形成，使得这多个复合数据分组相 互相关(但它们每个仍线性独立于相关接收器集合的每个接收器以前 接收的分组及突发中以前传送的复合分组)。如果这在多个调度实例 系统地实行，则可能降低传递给定量多播信息所需的反馈信号。

为更好地理解本发明，现在将参照图3的示意流程图，简要地描 述示范总体ARQ过程。

在步骤S1中，一个或多个数据分组从发送操作中的一个或多个 节点发送到至少两个接收节点。每个单独的数据分组预期用于所有考 虑的接收节点，即，数据分组是“多播数据分组”。数据分组的传输可 根据传输技术并发或相继进行。在步骤S2中，接收节点存储已正确 接收(正确解调和FEC解码)的相应数据分组。在步骤S3中，接收 节点将有关它们接收的分组的信息反馈到发送节点。在步骤S4中， 在有利时发送节点通过使用从接收节点110、120接收的数据分组的 反馈知识，形成复合多播数据，或备选发送常规多播数据分组。复合 多播数据分组通常基于要(重新)传送的多个选定常规多播数据分组 形成。例如，复合多播分组中比特的数量可有利地小于联合编码的分 组部分的比特的数量之和。发送节点可形成多个不同的复合多播分组 以便传输，可能与常规多播数据分组的传输组合在一起，以优化吞吐 量效率。在步骤S5中，发送节点向所有接收节点传送复合多播数据 分组或选定的常规多播数据分组。在收到复合多播数据分组后，接收 节点在可能时将复合多播数据分组解码，提取相应接收节点以前未知 的相应多播数据。在解码和提取过程中，优选利用接收器以前FEC解 码的多播数据分组。

在此上下文中，本发明明确针对复合分组的形成(编码)和在每 个复合数据分组中使用(及如何使用)哪些常规数据分组的决定(调 度)。在某种意义上，复合数据分组的形成能够视为联合调度和编码 过程。如图4的示意流程图中所示，这主要涉及发送器侧。在步骤S11 中，发送器从接收器接收指示接收的数据分组的反馈信息。如上所述， 本发明的一个关键特性是如步骤S12和S13中所示，基于认真选定的 编码权重集合，形成作为常规数据分组的加权线性组合的至少一个复 合多播数据分组。在步骤S12中，基于有关以前接收的数据分组的反 馈信息，调整用于至少一个复合数据分组的编码权重，使得复合分组 表示常规数据分组的新编码，该新编码线性独立于在多播会话期间相 关接收器集合中每个接收器以前接收的任何数据分组。这意味着通过 反馈，响应每个接收器以前接收的分组，适应性地选择编码权重，以 确保常规数据分组的新线性独立编码。在步骤S13中，优选通过将常 规数据分组乘以对应的适合的编码权重，形成复合数据分组。在步骤 S14中，将形成的复合数据分组传送到接收器。如图3中的总体ARQ 流程所示，优选重复进行该过程，直至多播会话中的所有常规分组已 传递给多播组的所有相关用户。

可选的是通过重复如图4中虚线所示的步骤S12-S14，可在给定 调度实例形成和传送若干复合数据分组。这将在后面更详细描述。

从接收节点到发送节点的反馈可优选是确认(ACK)过程的一部 分。反馈消息一般情况下能够以各种方式组成，例如，根据使用的传 输协议、ARQ过程等。

正如后面将详细描述的一样，各种编码方法和格式可用于本发明。

应理解的是，借助于本发明，不存在阻止以在步骤S1(参见图3) 中传送复合数据分组开始的整个过程的可能。

也应注意的是，如果利用允许并发传输的传输技术，例如，正交 频分多址(OFDMA)，则传输能同时进行，即，并发但在非重叠的 OFDM子载波集上发送第一分组和第二分组。重新传输也能够并发进 行。

在解释本发明的更具数学性的方案中，每个接收器以前接收的多 播数据分组(常规和/或复合数据分组)能够描述为基于权重向量的矩 阵的线性方程组。对于以前接收的复合数据分组，表示权重向量的ω 将包括编码权重集合，而对于以前接收的常规数据分组，权重向量将 包括单个非零编码权重。在编码和调度实例，在形成新复合数据分组 以便传输到接收器时，构想是基于以前接收的数据分组的反馈，适应 性地选择常规数据分组的加权线性组合的编码权重，使得对于每个考 虑的接收器的线性方程组秩将增大。秩的增大对应于每个接收器特定 的权重向量矩阵中形成新线性独立行，这相当于多播数据分组的新线 性独立编码。

现在，由于每个用户已接收一个或多个多播数据分组(常规和/ 或复合数据分组)，可将此视为线性方程组，其中，传送的多播数据 分组已知，加权已知，并且接收器集合中的每个接收器要为其线性方 程组求解以便确定常规数据分组并对其解码。在发射器侧，目的是生 成(调度和编码)适当的方程组，并且在接收器侧，目标是为线性方 程组求解(解码)和提取常规数据分组。

如果每次传送新线性独立多播数据分组，使得对于每个接收的数 据分组(接收数据分组的每个用户)，秩将连续增大，或至少大部分 的次数中增大，则吞吐量效率将大大提高。在前一情况下，每次传送 新线性独立多播数据分组时，在仅仅接收到N个数据分组时能保证N 个常规数据分组的可解码性，这是因为权重向量的矩阵将包括N个线 性独立行，从中可重新获得所有N个常规数据分组。由于对于每个接 收的数据分组矩阵的秩会增大，因此，将足以确保所有用户已接收正 好N个数据分组以解码和重新获得所有N个常规数据分组。

另外，为确保对于所有考虑的接收器或其子集秩会增大，发明者 认识到有时使用只能假设值0和1的权重是不足的。有时，在相对于 要传递的常规分组的数量，接收节点的数量很大时，如上所述，使用 具有至少两个不同非零编码权重的权重向量将是有利的。

注意，虽然线性组合在原则上能够通过常规运算执行，促使进位 比特为复合分组生成，但优选使用确保复合分组长度大致与常规分组 长度相同的度量。因此，基于有限域的运算是优选的，并在下文中采 用。一个可能的运算类型是所谓的模运算，但本发明并不限于此。此 外，注意线性编码操作可在完整的数据分组上执行，或备选常规数据 分组被分成多个更可管理的子串，而相同的线性编码操作在这些子符 串上执行。

注意，在下文中，将假设我们通过任何类型的运算操作，该运算 提供与允许生成(调度和编码)和求解(解码)线性方程组的传统运 算相同的规则。因此，在不失一般性的情况下，方程将在下文中通过 传统运算符号写出。

首先，每个用户的先验信息，即以前接收的一般多播数据分组(常 规和/或复合数据分组)能够根据以下所示描述为线性方程组

其中，d_n是第n个常规分组的值，是用户k的第m_k个一般多 播数据分组的值，是用户k、常规分组n和用户k接收的一般多播 数据分组m_k的权重因子，M_k是用户k最后接收的数据分组，并且N 是要传递的常规分组的总数。注意，每个用户可接收不同数量的多播 数据分组，因此，在变量M_k上具有不同的标志k。

现在，为简化符号，我们以矩阵形式为用户k编写(1)：

C_k＝W_kD                        (2)

生成(编码)和求解(解码)线性方程组可如前面所示通过普通 运算、“模运算”或任何其它适合的运算执行。

权重可采用的值一般在数量方面受限。此外，本发明不具体 强制可为权重采用哪些值，那些值能够从象{0，...，3}的任意集合或诸如 {0，1，2，3，5，7，11，13}等甚至一些更具想象力的任何集合中选择。可采用 的值数量越多，引入的有助于查找可用于形成复合数据分组的代码向 量的自由度就越大。此外，涉及的分组数量越多，引入的有助于查找 可用于形成复合数据分组的代码向量的自由度就越大。

然而，用于代码向量的权重的符号集一般必须足够大，以得到充 足的自由度，允许所有考虑的用户获得N个线性独立方程。然而，符 号集不必非常大。模拟显示了对于K＝20个用户，N＝6个分组，在用 户的接收概率是独立的，并且每个接收概率在此处假设为p＝0.05的情 况下，符号集大小(或等同于基数b)只使用3个元素{0，1，2}(或等 同于基数b＝3)便已足够。

要得到基数b的最小值的构想(或等同于符号集中的元素最小数 量)，我们知道代码字的数量b^N必须大于在最坏的情况下，K个用户 中的每个用户接收N个不同的多播数据分组的数量。因此，条件是b^N＞N·K。虽然这不是理想估计，但它仍指示，b、N和K是互相关的。 通常也存在对接收概率p的依赖性，与高接收概率一样，存在若干用 户接收相同数据分组的高的可能性。

此外，注意可能在W_k中的行和代码向量或权重向量ω只包含单 个非零元素。这相当于只为一般多播数据分组发送单个常规分组。本 发明优选使用有限域的运算，该运算可使用比只是“0”和“1”更多的元 素。用户的数量大，并且要传递的常规数据分组的数量小时，这将保 证找到新的线性组合。

在系统化方案中，每次希望找到新线性组合时，核心操作如下：

另一个也引起秩增大的等效阐述如下所示：

如上所述，阐述此的另一方式是选择编码权重，使得每次发送常 规数据分组的新线性独立编码。

上述操作确保接收一般多播数据分组的任何用户将始终增大其 秩。用户收到N个多播数据分组时，方程组将具有N个线性独立行， 即，满秩。因此，用户可在只接收最小数量的一般多播数据分组时将 所有常规数据分组解码。由于一些用户可能要更长时间接收其N个多 播数据分组，因此，一些其它用户可接收其需要的N个多播数据分组， 然后接收冗余的并能够被丢弃的(或者未被接收的)一些随后的数据 分组。

找到适合的代码向量ω的一种可能方案是基于暂定代码向量ω的 迭代测试假设。例如，选择代码向量ω的元素可采用的值的符号集(即， 域)。假设有该符号集，将具有所有可能排列的列表排序，即，具有 b^N个候选代码向量的列表(其中，b是域中的元素的数量，并且N是 要传递的常规数据分组的数量)。从列表开始向末尾搜索(确切地说 直至所需项)，并且又将列表中的每个项分配为候选代码向量ω。对 于每个候选代码向量ω，测试是否允许用于具有非满秩权重矩阵的所 有用户，根据编码/调度算法的条件(即，秩增大或备选在零空间上ω 的非零向量投影(projection))。如果条件得以满足，则选择候选代 码向量为代码向量ω。

实际上，通过将值“1”加上以前的候选代码向量，可创建候选代码 向量，即，只是计数器。为能够实现权重的适合的值集合，例如，从 零至某一数字b-1，候选代码向量可使用基数b并为其计数，其中， 每个数将对应一个权重。

作为用于下一代码向量候选的以基数b向上计数的备选方案，可 转为搜索具有权重“1”的所有字或字集合，即，只有一个权重为非零， 并且随后搜索具有权重“2”的所有字或字的集组合，并以此类推。此处 的构想是保持有关非零权重元素的数量尽可能低以使编码和解码复 杂性降到最低。然而，根据本发明，对于至少一个代码向量，将至少 有两个非零编码权重。

作为备选，可能可直接从权重矩阵的零空间确定代码向量。对于 每个用户k，考虑权重矩阵W_k，并确定相关联零空间并将它表示为Ξ_k。 对于每个用户k，我们现在要生成代码向量ω，其属性是它具有到Ξ_k中至少一个向量的非零投影。我们知道，如果代码向量ω被选择为Ξ_k中的基之一，假设为第一零空间向量ξ_k，则将具有用于该用户的所需 非零投影。然而，我们要确保这对于所有或至少给定的用户子集都成 立。趋近此的一种方式是在Ξ_k中所有考虑的用户的第一零空间向量ξ_k上形成重叠(superposition)。然而，需要避免由于重叠的原因，任何 向量ξ_k被其它ξ_k消去。如果此操作未实现，则可变更重叠的权重，或 者选择一个或多个ξ_k作为不是其相应零空间Ξ_k中的第一个向量。因此， 此任务是找到代码向量ω，使得其中，“·”是标量积。

作为备选或补充，也可能可从优化的角度接近构想，因为在每个 实例有可选择的许多不同的候选代码向量ω。优化的目的应优选是确 保只需要少量的编码和解码操作，即，本质上使W_k尽可能稀疏。Ω 的此类优化标准根据但不限于以下所示是探试的：

在发送器侧，要保持复杂性尽可能低，例如，在确定秩时，此算 法的实现可使用以前计算轮(round)的结果和权重矩阵的处理版本。 例如，如果分组由用户k成功接收，则使用在最后轮W′_k上执行的高斯 消元的结果是新W_k。下一轮新W′_k的秩计算可基于前一轮高斯消元形 式的W′_k，并修正了暂定代码向量ω。

类似于发送器侧，接收器侧可使用以前多播数据分组接收的结果 和权重矩阵的处理版本。例如，可使用更早高斯消元的结果。

编码方法

适合本发明的编码示例优选是基于异或按位编码，这是由于其简 单性的原因。异或运算对应于如上所述的编码权重一。

可预想联合异或编码，然后识别哪些分组要联合在一起编码的许 多不同的方法。

参照图5的示例，给出了可能的代码帧格式的一个示例。在此示 例中，两个数据分组(A)1005和(B)1010联合编码以形成复合多 播数据分组1015。异或运算能够直接对有效负载进行，但需要提供用 于识别哪些单独的分组编码在一起的工具。在图5的示范编码方法中， 在复合分组报头1020中以信号表示相关联合编码分组(此处只示出 两个分组，但构想能轻松扩展到更多分组)的标识符(例如，报头或 来自单独分组报头的相关信息的子集)。标识符例如可包括发送器地 址、多播地址和每个编码分组的分组序号。除标识符外，复合分组报 头优选也以信号表示复合多播分组的格式，即，在复合多播分组中分 组放置的位置。例如，如果有两个分组，并且其中一个分组包含比另 一分组更少的比特，如图5所示，则通常也指示具有更少比特的分组 中包含的比特数量及更短分组的第一比特的位置。比特的数量不同 时，如图5中通过分组B 1010所示，利用填充1025。复合分组报头 1020的格式字段也能以信号指示两个分组B和C相继地串接(未示 出)，然后与例如第三分组A或更多分组一起编码。包括报头的整个 复合分组随后优选采用FEC编码。

在正确FEC解码和检测正确的CRC 1030后，示范复合分组报头 能够实现轻松标识哪些分组已一起编码。接收器随后可使用此信息从 解码的数据分组存储获取先验已知分组，然后提取其它分组。应注意 的是，复合分组报头也可包含其它信息。与如上所示分组格式版本不 同的另一分组格式版本(未示出)是在为多个分组的有效负载编码的 同时，在公共广播消息中以信号表示复合分组报头，即，一种带外信 令。仍有的又一编码方法(未示出)能涉及盲标识(blind identification) 方案，即，针对先验信息的数据库测试已编码消息(其中，分组的报 头和有效负载均在一起编码)的假设，并使用CRC检验来测试假设 测试的有效性。

本发明不限于在复合数据分组的编码中使用异或运算。异或运算 是在与带有元素{0，1}的域F(2)上的线性相加。如上所述，发明者认识 到在接收器的数量增大时，通过更多元素扩展域以允许每个接收器的 矩阵的秩可在每次传输增大，变得很重要。因此，域可扩展到3个元 素{0，1，2}、四个元素{0，1，2，3}，并以此类推。通常，在一般编码理论 中为人所熟知的是域需要具有p^m个元素才可很好地定义，其中，p是 质数，并且m是正整数。还为人所熟知的是相同大小的域是同构的， 表现在如果域包含不同的元素，假设{0，1，2}或{2，3，7}，是无关紧要的。 除相关联合编码分组的标识符(例如，报头或单独分组报头的相关信 息的子集)外，如上所述，在域比两个元素更大时使用的权重向量的 值也优选在复合分组报头1020中以信号表示。

适合在根据本发明的方法中使用的编码操作的又一示例是基于在 信号星座，即在FEC编码和调制后操作的模算子。下文中考虑了每信 号星座符号编码，并且可为多个连续的信号星座符号重复该过程。模 运算在此示例中在处理复数时对于实部和虚部均独立执行，并利用模 运算的定义和数学观察：

((A+B)mod L-B)mod L＝(A)mod L，

这指示实值信号B能够叠加在实值信号A上，并允许信号A不受 干扰的恢复(只要信号A不超过量化级L)，而幅度(及因此功率) 限于(非线性编码的)复合信号。

实际上，这能够如下使用。发送器具有一般采用不同值的符号S₁和S₂。例如，在16QAM中，S₁∈{-3，-1，1，3}+i·{-3，-1，1，3}。现在，由 于接收器知道数据序列D₂(n)，因此接收器也知道对应符号S₂(对于 每个S₁)。随后，对于实部(并且同样对于虚部)，在发射方处联合 和已编码信号为

该信号随后被接收和均衡化，即，补偿路径损耗(确保为接收的 信号和减去的信号使用相同的标度)和复相(确保相应的同相和正交 相位轴与减去的信号一致)，以产生接收的信号

$R^{\left(\mathrm{Re}\right)}=(S_1^{\left(\mathrm{Re}\right)}+S_2^{\left(\mathrm{Re}\right)})\mathrm{mod}L+N^{\left(\mathrm{Re}\right)},$

其中，N^(Re)是噪声(和干扰)项。随后，通过以下恢复所需的信 号：

${\hat{S}}_1^{\left(\mathrm{Re}\right)}=(\left(R^{\left(\mathrm{Re}\right)}\right)\mathrm{mod}L-S_2^{\left(\mathrm{Re}\right)})\mathrm{mod}L=(S_1^{\left(\mathrm{Re}\right)}+N^{\left(\mathrm{Re}\right)})\mathrm{mod}L$

编码也能借助于比上述只一维量化更高维点阵(lattice)，通过量 化实现。在此情况下，量化在向量而不是标量上操作。

通常，接收节点可不具有立即对复合多播数据分组完全解码并从 中提取自己的数据所需的全部信息，而要等待接收更多数据分组。如 果情况是如此，则接收节点可将复合多播数据分组部分解码，并存储 结果、剩余的复合多播数据分组以便在其它信息可用时做进一步处 理。通过根据当前代码矩阵计算简化的行阶梯形式，并为每个接收的 新数据分组(常规或复合)执行更新的简化行阶梯形式，可为每个接 收器执行此解码。备选，复合多播数据分组被存储而不尝试解码，直 至接收节点获取所有所需信息。有关将大部分复合多播数据分组解码 所需信息的信息例如包括在报头中。此外，此解码能通过简化的行阶 梯形式方案执行。每个接收器本质上关注对代码矩阵求逆(在它使用 的域内)，并将此乘以接收的数据分组。精确地说，如同对于编码操 作一样，此操作要为数据分组分成的比特的每个子串进行。

通过利用常规和复合数据分组，并且通过让发送节点(通过反馈 信息)和接收节点均利用此信息，可能降低从一节点将一定数据量传 送到另一节点所需的传输次数。这将增强累积吞吐量及单个用户(或 等同于节点)吞吐量。另外，端对端等待时间特征将得以改进。备选， 依赖于条件，降低的传输次数能够用于在具有发送器和多个接收器的 通信系统中提高能量和能源效率。

应理解，发送器可使用和利用有关接收的数据分组的所有可用反 馈信息。除上述反馈信息外，在形成复合数据分组时，诸如服务质量 (QoS)信息和数据分组特征等补充信息也可使用。

图6是示出根据本发明的优选示范实施例，用于数据分组从发送 器到多个用户的多播传输的系统的示意框图。

视所选实现而定，下面所述的模块和方块可视为通信系统中发送 节点和/或接收节点的功能部分，并且不必本身是物理上不同的对象。 连接因而能理解为功能部分之间的链路，并且不必是物理连接。

整个系统是基于通过或多或少易于出错的通信信道或链路，与多 个用户200-1到200-K通信的发送器100。

诸如发送节点100等发送器基本上包括数据缓冲器模块110、ACK 寄存器120、多播调度器130、多播分组编码器140及提供执行实际 多播传输所需功能的某一形式的传送部件。

发送器也可包括用于处理单播信息的部件(未示出)。

数据缓冲器模块110暂时保持数据分组以便随后的调度/编码和到 用户/接收器200的传输。

一般情况下，如上所述，发送节点100先发送一个或多个常规数 据分组。在接收器的反馈信息变得可用，并且复合多播分组能够形成 时，发送节点也可形成并发送一个或多个复合多播数据分组。

多播调度器130考虑哪些数据分组驻留在数据缓冲器模块110中， 并且也考虑在ACK寄存器120中存储的、来自不同接收节点的ACK 信息。

基本上，多播调度器130通过基于ACK寄存器120中的ACK反 馈，确定编码权重集合，从而执行对数据缓冲器模块110中可用的常 规数据分组的调度。多播调度器130通知多播数据分组编码器140， 该编码器基于选定的编码权重，形成作为常规数据分组的加权线性组 合的复合多播数据分组或对其编码。此所谓的联合调度和编码在图7 中示出。多播调度器130具有用于确定/调整权重使得因为需要或者在 需要时能够形成新线性独立编码的功能模块。如上所述，此编码在特 定实施例中可基于包括至少两个非零编码权重的编码权重集合(此权 重集合也称为编码向量)。

多播调度器130一般配置用于处理常规/惯用多播ARQ操作。

补充知识也可用于调度。补充信息可包括但不限于：满足QoS调 度方面的可能性的QoS要求及单独分组的状态，如其寿命时间值。

诸如接收节点200等接收器主要包括提供执行实际接收所需功能 的接收部件、具有反馈功能的多播数据分组解码器210及数据缓冲器 模块220。数据缓冲器模块通常配置用于存储尚未输送到k个接收单 元的数据分组。

在接收到复合分组时，接收器200的解码器210通常识别哪些分 组已在一起编码。使用在缓冲器模块220中存储的常规多播数据分组， 或复合多播数据分组，或两者，解码器尝试将复合多播分组解码以提 取各个常规数据分组。解码器210也配置用于发出反馈消息和处理反 馈消息，包括ARQ相关消息。

在接收器200成功接收多播数据分组(常规数据分组或复合数据 分组)后，它立即或稍迟向发送器100发送ACK消息以确认它收到 了分组。由于每个反馈分组的开销原因，延迟可能对于不占用资源和 浪费不必要的能量是有用的。更新优选经接收器的ARQ部件和发送 器的ARQ部件实现。

另外，注意如果随后转发数据，则接收器200也可充当发送器。 这对于发送器60同样成立，即，它也可充当其它数据的接收器。

上述实施例只是作为示例提供，并且应理解，本发明并不限于此。 保持本文公开和要求保护的基础原理的其它修改、更改和改进是在本 发明的范围内。

附录A

基于对每个用户的每个传送的多播数据分组的秩增大要求的算 法，构建了在每次迭代中增大一个步级的模拟器。

以下模拟最终结果表示用于在i.i.d分组删除信道中五个多播数据 分组要发送到的三个用户的权重矩阵，其中，接收概率p＝0.1，并且 权重向量使用的基数b＝3。注意，在那些矩阵建立时，在每个实例最 多单行被添加到那些矩阵，并且此处所示的那些矩阵表示前五个接收 的多播数据分组的情况。易于确认的是每个权重矩阵具有满秩，并且 能够为每个用户都重新获得编码的数据分组。

$W_1=\left(\begin{array}{ccccc}0& 0& 0& 0& 1\\ 0& 0& 0& 1& 0\\ 0& 1& 0& 0& 0\\ 0& 1& 1& 0& 0\\ 1& 0& 0& 0& 0\end{array}\right),$$W_2=\left(\begin{array}{ccccc}0& 0& 1& 0& 0\\ 0& 0& 1& 0& 1\\ 1& 1& 0& 0& 1\\ 1& 1& 0& 1& 0\\ 1& 2& 0& 0& 0\end{array}\right),$$W_3=\left(\begin{array}{ccccc}0& 0& 1& 1& 0\\ 0& 0& 1& 1& 1\\ 0& 0& 1& 2& 0\\ 1& 0& 0& 0& 0\\ 1& 1& 0& 0& 0\end{array}\right)$

使用其它数量的分组和其它数量的用户的进一步模拟从实验上确 认了如果选择的权重向量的基数b足够大，可满足测试的充足组合数 量，则满秩始终能够实现。

注意，对于所有K，在p≠1时，性能大致为T≈p，而与分组的数 量无关。本发明允许对完全可靠的多播实现最佳吞吐量效率，即，在 为无限数量的分组分析吞吐量效率时，T＝p。

发明的方案是确定性可解码，即，与喷泉编码(FC)不同，接收 恰好完全相同数量的编码的分组便足以重新获得相同量的常规数据 分组。因子1+ε确定的FC性能取决于发送的分组数量。FC要求大量 的分组，大约为1000个或更多才可提供低ε。提议的发明不存在此类 相关性。

参考文献

[1]J.W.Byers，M.Luby，M.Mitzenmacher，and A.Rege.A digital  fountain approach to reliable distribution of bulk data.In Proceedings of  ACM SIGCOMM，pages 56-67，1998.

[2]J.Byers，M.Luby，and M.Mitzenmacher，″A digital fountain  approach to asynchronous reliable multicast″，IEEE Journal on Selected  Areas in Communications，20(8)，Oct.2002.

[3]J.Sachs，M.Meyer，S.Wager，H.Huschke，M.W.Larsson，P. Larsson，″Method and devices for efficient data transmission link control  in mobile multicast communication systems″.US Patent Application  2006/0154603.

[4]P.Larsson，N.Johansson，″Multi-User ARQ″，In conference  proceedings of VTC2006s|Pring，Melbourne，7-10May，2006.

[5]Shen Yong，Lee Bu Sung，″XOR retransmission in multicast error  recovery″，(ICON 2000)，Proceedings，IEEE International Conference on  Networks，pages 336-340，2000.

[6]M.A.Jolfaei，S.C.Martin，J.Mattfeldt，″A new efficient selective  repeat protocol for point-to-multipoint communication″，1993.ICC 93. Geneva.Technical Program，Conference Record，IEEE International  Conference on Communications，Volume 2，23-26May 1993，pages：1113 -1117vol.2.

[7]M.A.Jolfaei，U.Quernheim，″Effective Block Recovery Schemes  for ARQ Retransmission Strategies″IEEE Int.Symposium on Personal， Indoor and Mobile Radio Communications，1994.Wireless Networks- Catching the Mobile Future.5th Volume 3，Issue，18-23 Sep 1994 Page(s)：781-785vol.3.