基于机会主义路由的流间网络编码方法、设备及存储介质

摘要

本发明公开一种基于机会主义路由的流间网络编码方法、设备及存储介质。本发明中节点收到一个数据包时，读取数据包的候选集列表和相应的优先级参数，确定节点是否在候选集列表。然后节点在没有收到更高优先级节点的ACK帧时，根据优先级选择原则，将负责转发数据包。Mesh网络中的另外节点得到数据包发送机会时，检测编码条件，并在编码并准备转发。本发明引入流间网络编码后，能够有效减少无线Mesh网络中两个节点对于数据包的传输次数期望，从而提高网络转发成功率及网络的吞吐量。

说明书

技术领域

本发明涉及无线通信技术领域，尤其是涉及基于机会主义路由的流间网络编码方法、设备及存储介质。

背景技术

近年来，随着无线通信技术的高速发展，无线Mesh网络(Wireless MeshNetworks，WMNs)越来越多地受到学界、工业界以及市场的密切关注。相对于传统无线网络中“存储、转发”的数据传输方式，网络编码(Network Coding，NC)允许中间节点在转发数据包之前对数据包进行编码处理，将多个输入数据包混合生成一个新的编码数据包后再进行发送，使得网络中链路的容量能够达到理论上的最大值，因此具有提升网络吞吐量、保证网络可靠性和自适应性以及降低能耗、减少传输时延等显著优势。

不同于传统路由机制，在机会主义路由下，对于网络中的任一数据流，网络层为数据包的每一跳转发都选择一组潜在下一跳节点，而不是仅仅将链路质量最优的那一个节点作为下一跳。这些潜在下一跳节点被称为转发候选集(Forwarding Candidates)。转发候选集中的节点根据其到目的节点的距离被分配相应的优先级。当某个数据包通过无线广播信道传输的时候，转发候选集中收到该数据包的最高优先级节点将成为实际的下一跳节点，负责继续将该数据包向目的节点传输。可以知道，只要该数据包被转发候选集中任一节点正确接收，这次传输就能将该数据包有效地向目的节点传递一段距离。这样的传输方式极大地缓解了无线信道的不可靠性，降低了每个数据包在传输过程中的重传次数，因此显著提高了无线多跳网络传输性能。

值得注意的是，已有相关工作都没有设计合适的方式来确定转发候选集及候选集中节点的优先级这样一个关键问题，因此会造成网络节点转发成功率较低、吞吐量较小、延迟较高等问题。

发明内容

为了弥补现有技术的不足，本发明提供了一种基于机会主义路由的流间网络编码方法、设备及存储介质。

本发明的一方面提供了一种基于机会主义路由的流间网络编码方法，该方法包括以下步骤：

S1当Mesh网络中的节点R收到一个数据包P时，接收节点R读取数据包P的候选集列表F

如果接收节点R不在数据包P的候选集列表F

否则，根据节点R在候选集中的优先级，确定发送ACK帧的等待窗口大小W，并等待更高优先级节点发送的ACK帧。

S2如果接收节点R在等待窗口W内没有收到更高优先级节点的ACK帧，根据优先级选择原则，当前接收节点R将负责转发数据包P；

S3 Mesh网络中的节点S得到数据包发送机会时，节点S根据编码条件检查发送队列头部的数据包P

如果判断结果为否，节点S将直接发送非编码数据包P

否则，发送节点S继续判断是否已接收到了更高优先级节点发送的两个数据包P

如果是，节点S将这两个数据包P

否则，发送节点S对这两个数据包P

S4发送节点S提升编码数据包P

优选的，在S1中，所述优先级参数X

优选的，在S2中，如果P为非编码数据包，接收节点R将向数据包P的发送节点以及其它更低优先级节点发送ACK帧，并将数据包P向候选集转发；如果P为编码数据包，则接收节点R将P解码，为解码后的两个数据包分别发送ACK帧并分别转发。

优选的，在S3中，发送节点S对这两个数据包P

优选的，在S4中，在所述编码数据包P

本发明的另一方面提供了基于机会主义路由的流间网络编码设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其中，所述处理器执行所述程序时实现上述所述的基于机会主义路由的流间网络编码方法。

本发明的再一方面提供了一种计算机可读存储介质，所述存储介质存储有计算机程序，所述计算机程序用于执行上述所述的基于机会主义路由的流间网络编码方法。

本发明的有益效果：本发明引入流间网络编码后，能够有效减少无线Mesh网络中两个节点对于数据包的传输次数期望，从而提高网络转发成功率及网络的吞吐量。

附图说明

图1为各节点的缓存队列；

图2为各数据包的前一跳与候选集；

图3为本发明的设备结构图。

具体实施方式

为使本发明的目的、技术方案和优点更加清晰，下面将结合附图1对本发明作进一步描述。

本发明的方法主要包括以下步骤：

S1当网络中的节点R收到一个数据包P时(以下称R为接收节点)，接收节点R首先读取数据包P的候选集列表F

S2如果节点R在等待窗口W内没有收到更高优先级节点的ACK帧，根据优先级选择原则，当前接收节点R将负责转发数据包P。如果P为非编码数据包，节点R将向数据包P的发送节点以及其它更低优先级节点发送ACK帧，并将数据包P向候选集转发；如果P为编码数据包，则节点R将P解码后，为解码后的两个数据包P

S3网络中的节点S得到数据包发送机会时(以下称S为发送节点)，S首先根据编码条件检查发送队列头部的数据包P

S4发送节点S提升编码数据包P

进一步，确定步骤S1中候选集列表F

假设数据流中的所有数据包的传输相互独立，因此可以关注其中的一对数据包P

假设节点A和B的转发候选集均为中间节点的集合F，且中间节点的数量为N，并记节点A和节点B的转发候选集分别为

式中，

从节点A到B的传输需要经过候选节点集中某个节点的转发，因此式(1)中节点A到B的期望传输次数由两部分组成：一部分是节点A到A的转发候选集F

另一方面，在机会主义路由下，所有FA中的节点都有可能负责将数据包P

对于转发候选集中的节点j，记节点j将一个数据包传输到节点B期望传输次数为C

式(3)为一个基于条件概率的数学期望值的计算过程。首先，需要保证转发候选集中至少有一个节点收到了节点A发送的数据包，这一事件的概率为分母所表示的

综上分析，节点A传输一个数据包到节点B的期望传输次数C

同理，节点B传输一个数据包到节点A的期望传输次数C

下面计算引入流间网络编码后，节点A和B之间互相传递一个数据包能够进一步减少的期望传输次数。

假设编码机会出现在节点i，也就是说，节点i同时收到了节点A和节点B发送的数据包P

综合(4)、(5)和(6)，就可以得到引入流间网络编码后，节点A和B之间互相交换一对数据包所需的传输次数的期望X

X

记从A节点向B节点传输一个数据包所需的传输次数期望CETX为X

在一般情况下，如果源节点S和目的节点D的转发候选集不存在交集，与(4)式类似，S到D的期望传输次数X

为了进一步说明本发明，下面结合附图1详细介绍节点如何根据当前缓存队列以及队列中数据包的前一跳与候选集做出最合适的编码决定。如图1所示，节点C的当前发送队列中有三个数据包P、P

本发明的实施例可以应用在网络设备上,实施例可以通过软件实现，也可以通过硬件或者软硬件结合的方式实现。以软件实现为例，作为一个逻辑意义上的装置，是通过其所在设备的处理器将非易失性存储器中对应的计算机程序指令读取到内存中运行形成的，其中计算机程序用于执行上述步骤所确定的方法。从硬件层面而言，如图3所示，为本发明的基于机会主义路由的流间网络编码装置的硬件结构图，除了图3所示的处理器、网络接口、内存以及非易失性存储器之外，所述设备通常还可以包括其他硬件，以便在硬件层面进行的扩展。另一方面，本申请还提供了一种计算机可读存储介质，存储介质存储有计算机程序，计算机程序用于执行上述步骤所确定的基于机会主义路由的流间网络编码方法。

对于实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可。以上所描述的装置实施例仅仅是示意性的，本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。

本领域技术人员在考虑说明书及实践这里公开的发明后，将容易想到本申请的其它实施方案。本申请旨在涵盖本申请的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本申请的一般性原理并包括本申请未公开的本技术领域中的公知常识或惯用技术手段。说明书和实施例仅被视为示例性的。

还需要说明的是，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、商品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、商品或者设备所固有的要素。

以上所述仅为本申请的较佳实施例而已，并不用以限制本申请，凡在本申请的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本申请保护的范围之内。