一种基于散列邻域搜索网络编码的机会中继重传方法

2016-06-13邵鹏飞，赵燕伟，方朝曦

电信科学 2016年4期

邵鹏飞，赵燕伟，方朝曦

（1.浙江工业大学计算机科学与技术学院，浙江杭州 310023；2.浙江万里学院电子信息学院，浙江宁波 315100；3.浙江工业大学机械工程学院，浙江杭州 310023）

邵鹏飞1，2，赵燕伟3，方朝曦2

在无线多播网络中，传统的方法没有考虑某些接收节点与源节点及其他接收节点之间可能具有更好的链路质量。为此提出了一种基于散列邻域搜索网络编码的机会中继重传方法，该方法动态选择数据分组接收情况最好的且信道质量优于源节点的接收节点作为中继，并采用散列邻域搜索网络编码策略进行其他接收节点的丢失分组重传。仿真结果表明，相对于现有的其他网络编码重传方法，该方法能有效减少平均重传次数，提高重传效率，尤其当一些接收节点因受到干扰与源节点之间的信道质量变得很差时，该方法能取得很高的重传增益。

无线多播；网络编码；机会中继；重传

1 引言

随着通信技术的进步和发展及泛在物联网物与物之间的智能互联和大规模分布式计算［1，2］，越来越多的网络应用和服务渗透到日常生活中。在物联网基础架构中，除了物理基础设施外，基于通信网络收集和交换各种有用的信息才能充分发挥物联网的优势。无线通信系统是物联网中最重要的基础通信网络之一，使用越来越广泛。由于无线通信系统的传输可靠性较低，重传技术一直是该领域研究的重点［3，4］。

在无线多播网络中，基于传统的直接重传方式，比如ARQ 或 HARQ［5］等，源节点逐个重传各接收节点丢失的数据分组，传输效率低、能耗大。利用信道的广播特性，基于网络编码的广播重传已被证明能有效减少平均重传次数，提升传输性能［6-8］。该方式下，源节点根据各接收节点不同的数据分组丢失情况，对丢失分组进行调度和优化组合后编码重传，每一次重传能够同时让尽量多的接收节点恢复其丢失分组，从而减少总的重传次数。尽管相对于传统的直接重传方式，基于网络编码的重传技术大大提高了传输效率，降低了传输能耗，但是目前主要的研究都是假设信道相互独立且信道状态不变［9-11］，没有考虑无线链路状态的实时变化及这些变化对重传增益的影响，与实际网络情况仍有较大的差距。参考文献［12］虽然考虑了每个节点接收链路分组丢失率的不同，提出了基于机会网络编码的加权广播重传方法，将减少重传次数转化为基于加权的最大增益问题，但当源节点与某接收节点的信道质量变差时，重传性能将快速恶化。

在无线中继网络中，通过中继协作转发信息，可以有效利用信道并获得分集增益，提高传输可靠性。将机会中继协作传输技术应用于重传，利用质量较好的无线信道实现中继重传，能有效提升重传性能。但对中继协作通信的研究目前主要集中于单源 — 单中继 — 两目的［13］、两源 — 单中继 — 两目的［8，14］、两源 — 单中继 — 单目的［15］等中继通信系统，在单跳无线网络中很少提及。

为此，本文提出了一种适合单跳多播网络的基于散列邻域搜索网络编码的机会中继重传（hash neighborhood search network coding opportunistic relaying retransmission，HNS-NCORR）方法。该方法充分考虑节点之间的信道质量，动态选择数据分组接收情况最好的且信道质量优于源节点的接收节点作为中继，进行其他接收节点的丢失分组重传，重传方法基于散列邻域搜索网络编码策略。与现有的网络编码重传方法相比，这种结合机会中继的网络编码重传方法由于选择了信道质量更好的链路进行重传，提高了每一次重传的效率，从而能够提高整体的传输性能，尤其当个别接收节点由于受到干扰与源节点之间的信道质量变得非常差时，其作用将更加明显。

2 系统模型

如图 1 所示，本文基于通用的无线多播模型，一个源节点 S 和 N 个接收节点 Ri（N≥3，1≤i≤N）进行通信。假定系统采用时分多址技术，源节点和各接收节点之间的信道相互独立，信道环境变化缓慢，即数据重传时的信道增益变化可忽略不计，且反馈信道是可靠的，状态信息在反馈信道中不存在丢失。整个通信过程分为两个阶段：初始阶段和丢失分组重传阶段。在初始阶段，源节点向接收节点逐个广播 M 个原始数据分组 Qj（1≤j≤M），各接收节点Ri采用 ACK／NACK 同步反馈其丢失分组信息。当 S 发送完M 个数据分组后，能得到 N 个接收节点的接收状态信息。

图1 通用无线多播通信系统

在丢失分组重传阶段，根据节点间信道状态，动态选择数据分组接收情况最好的且信道质量优于源节点的接收节点作为中继，进行其他接收节点的丢失分组重传。若不存在这种情况，则直接采用散列邻域搜索网络编码重传方法［11］进行重传。

机会中继选择准则：中继节点到目的节点的链路质量由中继节点到多个目的节点的链路质量中较差的一路决定，而端到端的信道质量由源—中继和中继—目的信道中质量较差的一路决定，最佳中继节点拥有最好的端到端的信道质量。以链路分组丢失率作为衡量链路质量的指标，假设接收节点 Ri被选为最佳中继节点，PS，Ri为源节点到 Ri的分组丢失率，PRi，Rk为 Ri到其他接收节点的分组丢失率，PS，Rk为源节点到其他接收节点的分组丢失率，则 Ri需满足：

在具有3个接收节点无线多播网络中：

（1）若唯一存在符合式（1）的接收节点 Ri，则选择 Ri作为重传中继，并采用本文的 NCORR 方法；

（2）若同时存在符合式（1）的两个接收节点，则随机选择其一作为重传中继，转化为（1）进行处理。

在具有多个（超过 3 个）接收节点的无线多播网络中：

（1）若唯一存在符合式（1）的接收节点 Ri，则选择 Ri作为重传中继，并采用本文的 NCORR 方法；

（2）若同时存在符合式（1）的两个接收节点，则随机选择其一作为重传中继，转化为步骤（1）进行处理；

（3）若同时存在符合式（1）的 K（K＞2）个接收节点 Rj，则按与每个 Rj之间链路的信道质量按照就高原则进行区域划分，将重传划分为 K 个重传簇；在每个重传簇内选择Rj作为重传中继，转化为步骤（1）进行处理；若某个重传簇内节点数少于 3，则与邻近重传簇合并，合并后根据步骤（1）或（2）进行处理。

因此，在无线多播网络中，无论是只有 3 个接收节点还是具有更多接收节点，本文的重传处理思想是相同的，最终都转化为唯一存在符合式（1）的接收节点的情形进行处理。下文中，将以具有 3个接收节点的无线多播网络为例，阐述本文的方法。

3 HNS-NCORR 重传方法

本节将详细阐述提出的基于散列邻域搜索网络编码的机会中继重传方法。在单跳无线多播网络中，区别于其他重传方式，HNS-NCORR 动态选择具有比源节点信道质量更好的接收节点作为中继，进行其他接收节点的丢失分组重传，从而减少平均重传次数，提高重传效率。对丢失分组的调度、组合和编码采用散列邻域搜索网络编码策略。

3.1 机会中继策略

具有 3个接收节点的无线多播网络如图 2所示。

图2 具有3个接收节点的无线多播网络

假设：

由于 R1唯一符合式（1）条件，因此在重传阶段，R1将被选为重传中继，其重传方法如图 3所示。

情形 1 在初始阶段结束后，若 R1正确接收所有分组，R2和 R3存在分组丢失。此时，R1采用散列邻域搜索网络编码策略直接重传 R2和 R3丢失的数据分组，如图 3（a）所示。

情形 2 在初始阶段结束后，若 R1、R2和 R3都存在分组丢失，但 R1的接收情况最好且只有少量分组丢失。此时有两种处理方法。

方法（1）首先充分利用 R1成功接收的数据分组，R1将自己成功接收，而 R2和 R3没有正确接收的数据分组进行编码重传，直至两节点都正确接收；然后源节点编码重传剩余的3个节点都没有正确接收的分组。

方法（2）如图 3（b）所示，首先源节点广播重传 R1丢失的分组，让 R1正确接收所有数据分组，R2和 R3可同时接收这些重传分组来获取自己未正确接收的分组；然后选择 R1作为中继，编码重传 R2和 R3丢失的分组。在可解条件下［11］，在重传 R1丢失分组的过程中，可组合 R2、R3丢失的其他数据分组进行编码重传，进一步提高编码增益。由于当源节点S和个别接收节点的无线信道质量比较差时，方法（1）仍有可能需要源节点 S 直接重传该节点丢失的分组，导致重传性能快速下降，而方法（2）则不存在这种情况，因此本文将采用方法（2）处理情形 2。

图3 基于网络编码的机会中继重传方法

方法（3）对于其他情形，直接采用散列邻域搜索网络编码策略进行重传。

3.2 散列邻域搜索网络编码重传

相对于传统的网络编码重传策略［9，10］，散列邻域搜索网络编码重传策略［11］在对丢失分组的快速调度和优化组合、重传再丢失的优化处理等方面，有更好的考虑和设计，进一步提高了重传效率，其主要过程如下。

（1）发送节点基于接收状态表生成各接收节点丢失分组散列表（接收状态表表明发送节点有哪些数据分组未能被哪些接收节点正确接收）。

（2）发送节点基于散列邻域搜索快速选择符合满秩条件（可解条件下能从单个重传数据分组中恢复丢失分组的接收节点数达到最多）的丢失分组或丢失分组组合。

（3）发送节点对选出的丢失分组组合进行异或（XOR）编码，形成新的重传分组并发送出去。

（4）发送节点基于邻域关联搜索进一步挖掘编码机会，合并成多个关联的重传分组，经 XOR 编码后发送出去，并允许接收节点从多个重传分组中恢复丢失分组。

（5）各接收节点从收到的重传分组中解码出自己的丢失分组。

HNS-NCORR 对丢失分组的调度、组合、编码采用散列邻域搜索网络编码重传策略。在重传阶段，HNS-NCORR 在完成机会中继选择后，判断被选出的中继节点是否存在分组丢失。若中继节点存在分组丢失，则源节点首先重传中继节点的丢失分组，重传时最大化组合满足可解条件的其他接收节点的丢失分组，中继节点和其他接收节点接收该重传分组并解码出各自的丢失分组，然后同步反馈接收状态信息，源节点收到这些信息后更新自己的接收状态表，直至中继节点正确接收所有数据分组。若中继节点不存在分组丢失或经重传后中继节点已正确接收所有数据分组，则源节点将接收状态表信息发送给中继节点，中继节点收到该信息后生成自己的接收状态表（该表只包含其他接收节点的分组接收状态），并根据此表代替源节点重传其他接收节点丢失的分组，直至其他节点成功接收所有数据分组，然后反馈重传结束信息通知源节点进行下一组数据分组的传输。当其他接收节点从源节点和中继节点都收到某重传分组时，采用最大合并比解码。

由于无线传输的不可靠性，重传的分组仍会丢失。为了在重传的分组中不再出现已被所有节点成功接收的数据分组，在每次重传之前，HNS-NCORR 根据节点反馈的接收信息更新接收状态表（源节点重传则更新源节点的接收状态表，中继节点重传则更新中继节点的接收状态表）；然后根据新的接收状态表，在余下的丢失分组中通过散列邻域搜索和邻域关联搜索快速查找丢失分组组合，形成新的合并数据分组并编码重传。这种丢失分组更新机制由于调度组合时结合了最新的丢失分组信息，创造了更多的编码机会，可以有效提高重传效率。

3.3 HNS-NCORR 流程

如图 4 所示，HNS-NCORR 的工作流程分为两个阶段：在初始阶段，源节点连续发送 M个数据分组并判断接收状况，若这 M 个分组被所有节点成功接收，则发送之后的 M 个数据分组，否则进入重传阶段。在重传阶段，HNS-NCORR 首先根据分组接收情况和节点间链路状态选择机会中继；若找不到中继节点，源节点则采用散列邻域搜索网络编码策略重传所有节点的丢失分组；若找到中继节点，则判断该中继节点是否已成功接收M个分组；源节点优先重传中继节点的丢失分组，直至中继节点成功接收所有分组，然后中继节点代替源节点重传其他接收节点的丢失分组。由于中继节点具有更好的无线信道质量，因此能取得更好的传输增益。

图4 HNS-NCORR 工作流程

4 数学分析

在有 N（N≥3）个接收节点的多播网络中，假定 N 个接收节点的分组丢失率互不相关且服从伯努利分布［10-12］，令 pi表示接收节点 Ri（1≤i≤N）与源节点 S 之间的链路分组丢失率，pm=max｛p1，p2，… ，pN｝，其中，1≤m ≤N，令 λij为接收节点 Ri和 Rj之间的链路分组丢失率。当 M 足够大时，在初始阶段的 M 次初始传输后，各个接收节点分别有 Mpi个数据分组没有被正确接收，节点 Rm则是丢失分组最多的节点，丢失 Mpm个数据分组。在重传阶段，若各个接收节点每次正确接收都能获取 1个原始分组，则每个接收节点正确接收全部数据分组所需的重传次数为 Mpi／（1-pi）。由于pm最大，可以得到 Mpm／（1-pm）最大。

（1）当数据分组数 M 足够大时，采用基于网络编码的重传方法［9-12］，每个重传分组都可以看成链路分组丢失率最大的接收节点与其余 N-1 个节点丢失分组的编码组合，因此总的重传次数为 Mpm／（1-pm），由分组丢失率最大的节点决定。即 M 个数据分组的平均重传次数 TNC［10-13］可表示为：

（2）采用本文的 HNS-NCORR 方法，M 个数据分组的平均重传次数 THNS-NCORR可表示为：

代入 φ 和 w，并根据式（5）可得：

因此，当 ∀Pm、Pk、λkm满足式（7）时，HNS-NCORR 方法比其他基于网络编码的重传方法进一步减少了平均重传次数，获得了更高的传输效率。

HNS-NCORR 方法相对于其他网络编码重传方法的重传增益为：

代入式（3）和式（4），可得：

当 pm、pk、λkm满足式（7）时，HNS-NCORR 方法就能获得正重传增益。当 pm远大于 pk、λkm时，即一个或一个以上接收节点与源节点之间的无线链路质量因干扰变得很差时，系统将获得很大的重传增益。

5 仿真与分析

HNS-NCORR 方法首先根据链路状态检测机制计算源节点、各接收节点之间的链路分组丢失率，并根据链路分组丢失率进行机会中继选择，然后采用基于散列邻域搜索网络编码方法进行重传，重传分为两个阶段：首先源节点重传中继节点的丢失分组，然后中继节点代替源节点重传其他接收节点的丢失分组。参考文献［11］提出了改进的网络编码重传方法 IONCR，该方法在单跳无线多播网络中由源节点通过邻域关联搜索进行分组丢失组合和编码重传，并优先重传能让最多接收节点恢复其丢失分组的单个重传分组，在保持较低算法复杂度的情况下，相对于 ARQ 直接重传及其他网络编码重传方法［16，17］，IONCR 能取得更好的重传性能。为此，在相同的无线网络环境下，本文直接比较了 HNS-NCORR 算法与 IONCR 算法的重传性能，并以平均重传次数作为重传性能分析的评价指标。

仿真中，考虑实际应用环境，将分别考察两种系统模型：在系统 A 中，源节点与所有接收节点的无线链路质量都较好；在系统 B 中，存在一个或一个以上接收节点与源节点之间的无线信道由于受到干扰导致高链路分组丢失率。当接收节点数 N=4 时，系统 A、B 中源节点、各接收节点之间的信道参数如下（行参数为［S R1R2R3R4］＇，列参数为［S R1R2R3R4］）：

为了更好地进行性能比较，引入中间系统 C，系统 C与系统 B相近但节点受到的干扰较小。在系统 B中，接收节点 R4受到干扰，与源节点之间的链路分组丢失率达到0.8。在系统 C 中，接收节点 R4受到的干扰比系统 B 小，与源节点之间的链路分组丢失率为 0.6。在 3 个系统中，根据式（7）和式（1）确定 R1为最佳中继节点，与式（10）～式（12）节点之间的链路质量情况相符。

图5 比较了 N=4 时 3 个系统中 HNS-NCORR 和IONCR 的重传性能。从仿真结果可以看到，在 3 个系统中，HNS-NCORR 的平均重传次数都要少于 IONCR，而且当一个接收节点至源节点的链路质量变坏，出现高分组丢失率时，这种优势更加突出。在系统 A、C、B 中，根据式（9）计算可得 HNS-NCORR 相对于 IONCR 的重传增益分别约为10%、80%和 300%，与图 5 中仿真结果相符。这是因为HNS-NCORR 有效利用了信道质量最好的接收节点进行重传，当某个接收节点与源节点之间的信道变得很差而与机会中继节点之间的信道保持较好的情况下，将大大提高重传效率。

图5 N=4 时不同网络环境下（好、中、差）重传性能比较

假设 N=3 和 N=5 时，系统 A 和系统 B 的信道参数如下：

图6（a）和图 6（b）分别比较了较好无线网络环境和受干扰无线网络环境下，不同接收节点数时 HNS-NCORR 和IONCR 的重传性能。从仿真结果可以看出，无论在哪种网络环境下，HNS-NCORR 的重传性能都优于 IONCR。这是因为这些模型的参数都满足式（5）的条件，所以HNS-NCORR 的平均重传次数要少于 IONCR。当网络规模变大、接收节点数增加时，HNS-NCORR 能保持较稳定的重传性能，在较好的无线网络环境下，相对于 IONCR 有 10%左右的重传增益；在受干扰较差环境下，某接收节点与源节点之间出现高链路分组丢失率时，相对于 IONCR 有300%左右的重传增益。

图6 不同环境下不同接收节点数的重传性能比较

6 结束语

在单跳无线多播网络中，现有的网络编码重传方法普遍选用源节点进行丢失分组重传，对节点之间无线链路的质量及其动态变化考虑不足，本文提出了一种基于散列邻域搜索网络编码的机会中继重传方法 ——HNS-NCORR，并分析了该方法适用的条件。HNS-NCORR 方法充分考虑了无线链路质量及其状态的动态变化，利用网络中具有更高链路质量的接收节点代替源节点进行丢失分组重传，与现有的网络编码重传等方法相比，能减少链路中断率，获得更好的重传增益。仿真结果表明，HNS-NCORR 减少了平均重传次数，提高了重传效率，尤其当网络中一个或一个以上接收节点因受到干扰导致高链路分组丢失率时，该方法的效果更加明显。

［1］ STOJMENOVIC I.Machine-to-machinecommunicationswith in-network data aggregation， processing， and actuation for large-scale cyber-physical systems ［J］.IEEE Internet of Things Journal，2014，1（2）：122-128.

［2］ CHEN K C，LIEN S Y.Machine-to-machine communications：technologies and challenges ［J］.Ad Hoc Networks，2014 （18）：3-23.

［3］ QURESHI J，FOH C H，CAI J F.An efficient network coding based retransmission algorithm for wireless multicast［C］／IEEE 20th International Symposium on Personal，Indoor and Mobile Radio Communications，September 13-16，2009，Tokyo，Japan. New Jersey：IEEE Press，2009：691-695.

［4］ VIEN Q T， STEWART B G.An efficientcooperative retransmission for wireless regenerative relay networks［C］／2012 IEEE Global Communications Conference （GLOBECOM），December 3-7，2012，California，USA.New Jersey：IEEE Press，2012：4417-4422.

［5］ LEVORATO M，TOMASIN S，ZORZI M.Cooperative spatial multiplexing for ad hoc networks with hybrid ARQ：system design and performance analysis ［J］.IEEE Transactions on Communications，2008（9）：1545-1555.

［6］ HO T，MEDARD M，KOETTER R，et al.A random linear network coding approach to multicast ［J］.IEEE Transactions on Information Theory，2006，52（10）：4413-4430.

［7］TRAN T，NGUYEN T，BOSE B，et al.A hybrid network coding technique for single-hop wireless networks［J］.IEEE Journal on Selected Areas in Communications，2009，27（5）：685-698.

［8］ SONG Q，LI Y，HE Z Q，et al.On reliable multicast with network coding ARQ for relay cooperation cells ［C］／75th IEEE Vehicular Technology Conference （VTC Spring），May 6-9，2012，Yokohama，Japan.New Jersey：IEEE Press，2012：1-5.

［9］ SOROUR S， VALAEE S.An adaptive network coded retransmission scheme for single-hop wireless multicast broadcast services ［J］.IEEE／ACM Transactions on Networking，2010，19（3）：869-878.

［10］WANG Y S， ZHANG Q Y.Anapproachonwireless broadcasting retransmission using network coding ［C］／／8th International Conference on Wireless Communications，NetworkingandMobileComputing （WiCOM）， September 21-23，2012，Shanghai，China.New Jersey：IEEE Press，2012：1-4.

［11］邵鹏飞，赵燕伟，吴耀辉，等. 多播网络中基于机会网络编码改进的重传方法［J］. 电信科学，2015，31（4）：99-106. SHAO P F ，ZHAO Y W ，WU Y H ，et al.Animprovedretransmission approach based on opportunistic network coding in multicast networks［J］.Telecommunications Science，2015，31（4）：99-106.

［12］苟亮，张更新，孙伟，等. 无线网络中基于机会网络编码的加权广播重传［J］. 电子与信息学报，2014，36（3）：749-753. GOU L，ZHANG G X，SUN W，et al.Weighted broadcasting retransmission based on opportunistic network coding in wireless networks ［J］.Journal of Electronics&Information Technology，2014，36（3）：749-753.

［13］FAN P，ZHI C，WEI W，et al.Reliable relay assisted wireless multicast using network coding ［J］.IEEE Journal on Selected Areas in Communications，2009，27（5）：749-762.

［14］VIEN Q T，TRAN L N，HONG E K.Network coding-based retransmission for relay aided multisource multicast networks［J］. EURASIP Journal on Wireless Communications and Networking，2011（5）：1-10.

［15］方朝曦，李国胜，朱宇，等.一种基于联合网络编码和信道解码的高效率中继技术［J］. 电路与系统学报，2011，16（4）：120-124. FANG Z X，LI G S，ZHU Y，et al.A spectral efficient relaying scheme with joint network coding and channel decoding ［J］. Journal of Circuits and Systems，2011，16（4）：120-124.

［16］GOU L，ZHANG G X，SUN W，et al.WBRONC：efficient wireless broadcast retransmission based on opportunistic network coding［J］.Frequenz，2013，67（3／4）：117-125.

［17］卢冀，肖嵩，吴成柯. 一种基于机会式网络编码的高效广播重传方法［J］. 电子与信息学报，2011，33（4）：858-863. LU J，XIAO S，WU C K.A high efficiency retransmission approach based on opportunistic network coding ［J］.Journal of Electronics&Information Technology，2011，33（4）：858-863.

A hash-neighborhood-search-network-coding based opportunistic relay retransmission approach

SHAO Pengfei1，2，ZHAO Yanwei3，FANG Zhaoxi2
1.College of Computer Science&Technology，Zhejiang University of Technology，Hangzhou 310023，China 2.School of Electronic and Information Engineering，Zhejiang Wanli University，Ningbo 315100，China 3.College of Mechanical Engineering，Zhejiang University of Technology，Hangzhou 310023，China

In wireless multicast networks，it is rarely concerned that there may be certain receiving nodes which have better quality links both to the source node and to the other receiving nodes.A novel hash-neighborhoodsearch-network-coding based opportunistic relay retransmission approach was proposed.According to the packet reception status and channel quality，this novel approach dynamically selected the best suitable receiving node whose channel quality was better than the source node as a relay，then hash-neighborhood-search-network-coding strategy was used for the relay to retransmit other receiving nodes’ lost packets.Simulation results show that this novel approach can effectively reduce the number of retransmissions to improve the transmission efficiency with respect to the existing algorithms，especially when one or more of the receiving nodes are interfered and the quality of the channel between receiving nodes and source node continues to decline，this approach can achieve a high retransmission gain.

wireless multicast，network coding，opportunistic relaying，retransmission

s： The NationalNaturalScience Foundation of China （No.61379123，No.61401400）， Ningbo SocialDevelopment Foundation（No.2014C50006）

TN925

：A

10.11959／j.issn.1000-0801.2016090