面向无线多跳网络中网络编码感知路由的流量匹配方法

摘要

本发明公开了面向无线多跳网络中网络编码感知路由的流量匹配方法，步骤a.源节点S发起到目的节点D的路由请求，并依据网络编码感知路由原理，通过路由返回报文获取从源节点S到目的节点D且存在网络编码机会的路径PathSD；步骤b.源节点S向PathSD上的每跳节点发起成组虚拟队列计算请求；步骤c.PathSD上的每跳节点，基于成组虚拟队列计算结果，开始基于流量匹配机制的数据包发送。本发明的面向无线多跳网络中网络编码感知路由的流量匹配方法将成组虚拟队列机制和流量匹配机制应用于网络编码感知路由，提高网络编码数据包调度效率，增加网络中网络编码实际发生数目，提高路由传输效率，提高网络吞吐量，提高网络编码对数据传输的增益。

说明书

技术领域

本发明具体为一种无线多跳网络中面向网络编码感知路由的数据包传输调度方法， 主要适用于使用了网络编码感知路由的无线多跳网络中的数据包传输次序调度，属于无 线网络技术领域。

背景技术

无线多跳网络是一种由带有无线收发设备的节点，以自组织的方式构建的无线通信 系统。无线多跳网络中每个节点同时具有路由节点和终端节点功能，任意两个不在相互通信范围内的节点之间如要进行通信，需要其他节点的转发，数据才能最终到达目的节点。由于网络中每个节点功能与地位对等，没有中心化节点，也不需要任何网络基础设 施，无线多跳网络可以在极端环境下快速部署网络，且网络具有组网灵活、部署快速、 成本低廉、可扩展性强、抗毁性和健壮性强等优势。无线多跳网络被广泛应用于灾后应 急通信、战场通信、环境监测、智能家居等场景。因此无线多跳网络具有广阔的应用前 景。

典型的无线多跳网络有无线网状网络、无线传感器网络、无线自组织网络、车载自组织网络等。由于无线信道的开放特性，无线多跳网络中的数据传输容易受到无线干扰 等因素的影响，制约了无线多跳网络传输的吞吐量和能量效率的提升。如何为无线多跳 网络设计高吞吐量路由协议，实现无线多跳网络的高吞吐量、节能数据传输，是无线多 跳网络的一个重要研究方向。

传统网络中，节点以存储转发方式工作。节点对收到的数据包不进行任何操作。近年来出现的网络编码技术改变了这一工作方式，其允许节点对收到的数据包进行数学运算，这种数学运算被称为网络编码。网络编码中，未进行任何数学运算的数据包被称为 原始数据包。进行网络编码运算以后的数据包被称为编码数据包。

在无线网络环境下，采用网络编码后可以减少数据传输次数，节省节点能耗，提高网络吞吐量。此外，现有研究成果表明在100m的无线链路上传输1Kb的数据和CPU 执行3Mb的指令所消耗的能量相当。即引入网络编码所带来的计算能量开销，与其节 省数据传输次数所节约的能量相比可忽略。因此，网络编码技术适合于应用到无线多跳 网络中。

由于网络编码在减少数据传输次数和提高网络吞吐量方面的优势，研究人员针对无 线多跳网络已经提出了一些基于网络编码的路由技术。目前适用于无线多跳网络路由的 网络编码主要分为流内网络编码和流间网络编码。流内网络编码，是指参与编码的数据来自同一数据流。流间网络编码，是指参与编码的数据来自不同数据流。流间网络编码 实现通常采用异或运算。基于流间网络编码的路由技术，又称为网络编码感知路由。本 发明针对的就是使用流间网络编码的路由技术，即网络编码感知路由。

网络编码感知路由，通常在路由发现阶段，在路由中的每跳节点，依据多跳网络编码条 件判断该跳节点是否存在网络编码机会，即两条数据流在该节点是否可以进行网络编码。 但网络编码机会只是判断两条数据流在某个节点是否能够实施网络编码，并确保所有与 目的节点都能正确解码。但是，网络编码能否正常实施，还受到数据包传输调度算法的 影响。当前网络编码感知路由在数据链路层均采用顺序调度机制。顺序调度中，从队列中取出第1个数据包，并检查该数据包所属数据流的编码机会。如果所属数据流可以与 其他经过当前节点的数据流编码，那么将检查当前队列中是否有属于这些流的数据包。 如果这些流的数据包存在于队列中，那么第1个数据包将与队列中的可编码数据流的数 据包进行编码并广播出去。否则，第1个数据包将在不进行网络编码的情况下直接发送 出去。在第2种情况下，虽然网络编码机会存在，但网络编码无法发生，浪费了网络编 码机会，降低了网络编码增益。现有无线多跳网络的网络编码感知路由，其在数据链路 层调度数据包传输时，往往采用顺序调度的方法，即依据数据包到达顺序依次发送。但 与队列首个数据包存在编码机会的数据流的数据包可能在当时情况下尚未入队列，则将 发生存在编码机会但无法实施网络编码的问题。这一问题导致现有的网络编码感知路由， 虽然能够发现路由中的网络编码机会，但是某些网络编码机会不能确保网络编码的实际 实施，即部分数据包的网络编码无法实际实施，降低数据传输中网络编码实际发生的数 目，降低网络编码为网络传输带来的增益。图1(a)-图1(c)是网络节点传统顺序调 度基本原理图，图1(a)为线性拓扑中flow

发明内容

发明目的：本发明的目的主要是针对无线多跳网络，提出一种面向无线多跳网络中 网络编码感知路由的流量匹配方法。针对网络编码特点，提出面向编码数据流的成组虚拟队列机制，将原始数据包排队队列，按数据流虚拟为各个数据流的数据包队列，并对 存在编码机会的数据流的虚拟队列进行成组，并以成组后的虚拟队列作为基本的调度单 元。提出面向网络编码感知路由的流量匹配方法，将同组内存在编码机会的每条数据流 的虚拟队列进行匹配，确保网络编码机会能够发生，增加网络编码发生数目，减少数据 传输次数，减少节点传输的能耗，提高网络编码的增益。

技术方案：本发明面向无线多跳网络，提出一种面向无线多跳网络中网络编码感知 路由的流量匹配方法。相比于现有的无线多跳网络的网络编码感知路由及其使用的数据 包顺序调度传输机制，其特殊性和创新性在于，该方法引入了成组虚拟队列机制和流量匹配机制。成组虚拟队列机制，针对网络编码的特性，将节点的原始数据包排队队列， 对应每条数据流虚拟化一个虚拟队列，并将存在编码机会的数据流对应的虚拟队列组成 一个组，数据包传输时以成组的虚拟队列作为基本调度对象，提高数据包传输调度的针 对性和效率。流量匹配机制，针对同组的数据流存在编码机会的实情，匹配同组内每个 虚拟队列的数据包情况，确保存在编码机会的数据流能够在数据包传输之前，能够确实 实施网络编码，增加网络编码发生的数目，提高网络编码增益。因此本发明解决了现有 编码感知路由中，数据流确实存在编码机会，但因为使用数据包顺序调度，导致无法实 际发生网络编码，进而减少网络编码发生的实际数目，降低网络编码增益的问题。

本发明的一种面向无线多跳网络中网络编码感知路由的流量匹配机制，利用成组虚 拟队列机制提高数据包调度的针对性和准确性，利用流量匹配机制增加网络编码实际发 生数目以提高网络编码增益，具体包括以下步骤：

步骤a.源节点S发起到目的节点D的路由请求，并依据网络编码感知路由原理， 通过路由返回报文获取从源节点S到目的节点D且存在网络编码机会的路径Path

步骤b.源节点S向Path

步骤c.Path

进一步地，所述步骤b中的成组虚拟队列计算，其步骤如下：

步骤b1：假定当前节点为v，该节点的原始数据包排队队列为Queue

步骤b2：对于FlowSet

步骤b3：对于FlowSet

步骤b4：令FlowSet

步骤b5：如果FlowSet

步骤b6：cflowGroupRes＝cflowGroupRes∪{cflowGroup}，cvqueGroupRes＝cvqueGroupRes∪{cvqueGroup}，如果FlowSet

步骤b7：流经节点v的数据流依据存在网络编码机会的关系进行分组，假定共分为m组，结果为cflowGroupRes＝{cflowGroup

进一步地，所述步骤c中的流量匹配机制，其步骤如下：

步骤c1：节点v的成组虚拟队列的计算结果为cvqueGroupRes＝{cvqueGroup

步骤c2：对虚拟队列组cvqueGroup

步骤c3：对于cvqueGroupRes'中的第1个元素，虚拟队列组cvqueGroup'

步骤c4：对于cvqueGroupRes'中的第w个元素，虚拟队列组cvqueGroup'

步骤c5：计算cvqueGroupRes中的每个虚拟队列组的到达时间，并依据到达时间先后顺序排序，得到排序后的成组虚拟队列集合cvqueGroupRes'＝{cvqueGroup'

有益效果：

(1)针对网络编码的特性，提出成组虚拟队列机制，将节点的原始数据包排队队列， 对应每条数据流虚拟化一个虚拟队列，并将存在编码机会的数据流对应的虚拟队列组成 一个组，数据包传输时以成组的虚拟队列作为基本调度对象，提高数据包传输调度的针对性和效率；

(2)流量匹配机制，针对同组的数据流存在编码机会的实情，匹配同组内每个虚拟队列的数据包情况，确保存在编码机会的数据流能够在数据包传输之前，能够确实实施 网络编码，增加网络编码发生的数目，提高网络编码增益；

(3)该发明方法具有较好的可扩展性和自适应性，能够适合各种类型的无线多跳网络。

附图说明

图1(a)为线性拓扑中flow

图2是线性拓扑中在编码节点数据包传输顺序调度和数据流匹配调度比较示例图；

图3是数据流匹配机制下节点逻辑结构图；

图4是数据流流量匹配机制流程图；

图5(a)流量匹配机制示例网络；图5(b)为节点3的数据包括到达顺序；图5(c) 节点3使用顺序调度；图5(d)为节点3使用流量匹配机制。

具体实施方式

下面结合附图对本发明作进一步说明：

本发明的面向无线多跳网络中网络编码感知路由的流量匹配方法，针对每条数据流 分别设置虚拟队列，并将存在编码机会的数据流对应的虚拟队列成组，提高数据传输调度的针对性。提出流量匹配机制，调度数据包传输次序，让存在编码机会的数据流的数 据流量相匹配，增加实际的网络编码发生次数，提高网络编码增益，具体包括以下内容：

(1)成组虚拟队列机制：源节点在通过网络编码感知路由获取到目的节点的路由后，将对路由上的所有节点进行成组虚拟队列计算。路由上的每跳节点，对流经该节点 的每跳数据流对应生成一个虚拟队列，用于存储流经该节点且属于该数据流的数据包。 依据数据流间是否存在网络编码机会的关系，将存在网络编码机会的数据流分为一组， 对应的同组内的数据流的虚拟队列同样分为一组。同组内的虚拟队列，其对应的数据流 可以进行网络编码，则组内每个虚拟队列的队首数据包可以编码为一个数据包发送出去。 因此，虚拟队列成组后，数据传输调度以成组的虚拟队列为基本调度对象，提高数据传 输调度的效率。

(2)流量匹配机制：流量匹配机制的基本原理，是要让存在编码机会的数据流的数据包能够实际参与网络编码。节点在进行数据传输时，以成组的虚拟队列作为基本的调 度单位。对每个成组虚拟队列，选取队首数据包中到达时间最早的时间作为这个成组虚 拟队列的到达时间，然后对当前节点所有的成组虚拟队列依据到达时间先后顺序排序， 依此顺序检查各个成组虚拟队列的队列情况。如果当前成组虚拟队列的所有虚拟队列都 不为空，则将每个虚拟队列的队首数据包异或作为编码包发送出去，然后依次检查下一 个成组虚拟队列。如果当前成组虚拟队列有部分虚拟队列为空，则当前组内的所有数据 流不能都参与编码，为此设置一个计数器作为等待时间，等待虚拟队列为空的数据流的 数据到来。如果在等待的时间内，虚拟队列为空的数据流的数据未完全到达，为了避免 数据包延时过长，将所有非空虚拟队列的队首数据包异或后作为编码数据包发送出去。 重复以上过程，不断循环，从而实现数据流之间流量的匹配，增加网络编码发生的数量， 提高数据传输过程中的网络编码增益。

该面向无线多跳网络中网络编码感知路由的流量匹配方法，提出成组虚拟队列机制， 以成组虚拟队列为数据包传输调度基本单位，提高数据传输调度的针对性和效率，引入 流量匹配机制，以确保存在网络编码机会的节点，网络编码能够实际发生，增加网络编码发生的数目，提高网络编码增益，图3是数据流匹配机制下节点逻辑结构图。图4是 数据流匹配机制流程图，具体包括以下步骤：

步骤a.源节点S发起到目的节点D的路由请求，并依据网络编码感知路由原理， 通过路由返回报文获取从源节点S到目的节点D且存在网络编码机会的路径Path

步骤b.源节点S向Path

步骤c.Path

步骤b中的成组虚拟队列计算，其步骤如下：

步骤b1：假定当前节点为v，该节点的原始数据包排队队列为Queue

步骤b2：对于FlowSet

步骤b3：对于FlowSet

步骤b4：令FlowSet

步骤b5：如果FlowSet

步骤b6：cflowGroupRes＝cflowGroupRes∪{cflowGroup}，cvqueGroupRes＝cvqueGroupRes∪{cvqueGroup}，如果FlowSet

步骤b7：流经节点v的数据流依据存在网络编码机会的关系进行分组，假定共分为m组，结果为cflowGroupRes＝{cflowGroup

步骤c中的流量匹配机制，其步骤如下：

步骤c1：节点v的成组虚拟队列的计算结果为cvqueGroupRes＝{cvqueGroup

步骤c2：对虚拟队列组cvqueGroup

步骤c3：对于cvqueGroupRes'中的第1个元素，虚拟队列组cvqueGroup'

步骤c4：对于cvqueGroupRes'中的第w个元素，虚拟队列组cvqueGroup'

步骤c5：计算cvqueGroupRes中的每个虚拟队列组的到达时间，并依据到达时间先后 顺序排序，得到排序后的成组虚拟队列集合cvqueGroupRes'＝{cvqueGroup'

面向无线多跳网络中网络编码感知路由的流量匹配方法的流程图如图4所示，下面 进一步详细说明本发明的技术方案和方法流程。

(1)成组虚拟队列机制

源节点在通过网络编码感知路由获取到目的节点的路由后，将对路由上的所有节点 进行成组虚拟队列计算。路由上的每跳节点，对流经该节点的每跳数据流对应生成一个虚拟队列，用于存储流经该节点且属于该数据流的数据包。依据数据流间是否存在网络 编码机会的关系，将存在网络编码机会的数据流分为一组，对应的同组内的数据流的虚 拟队列同样分为一组。同组内的虚拟队列，其对应的数据流可以进行网络编码，则组内 每个虚拟队列的队首数据包可以编码为一个数据包发送出去。因此，虚拟队列成组后， 数据传输调度以成组的虚拟队列为基本调度对象，提高数据传输调度的效率。

(2)流量匹配机制

流量匹配机制的基本原理，是要让存在编码机会的数据流的数据包能够实际参与网 络编码。节点在进行数据传输时，以成组的虚拟队列作为基本的调度单位。对每个成组虚拟队列，选取队首数据包中到达时间最早的时间作为这个成组虚拟队列的到达时间， 然后对当前节点所有的成组虚拟队列依据到达时间先后顺序排序，依此顺序检查各个成 组虚拟队列的队列情况。

如果当前成组虚拟队列的所有虚拟队列都不为空，则将每个虚拟队列的队首数据包 异或作为编码包发送出去，然后依次检查下一个成组虚拟队列。如果当前成组虚拟队列有部分虚拟队列为空，则当前组内的所有数据流不能都参与编码，为此设置一个计数器 作为等待时间，等待虚拟队列为空的数据流的数据到来。如果在等待的时间内，虚拟队 列为空的数据流的数据未完全到达，为了避免数据包延时过长，将所有非空虚拟队列的 队首数据包异或后作为编码数据包发送出去。重复以上过程，不断循环，从而实现数据 流之间流量的匹配，增加网络编码发生的数量，提高数据传输过程中的网络编码增益。

为了直观地说明面向无线多跳网络中网络编码感知路由的流量匹配方法的工作原 理，图2给出了线性拓扑中在编码节点数据包传输顺序调度和数据流匹配调度比较示例图。图3是数据流匹配机制下节点逻辑结构图。图4是数据流流量匹配机制流程图。 图5(a)-图5(d)是流量匹配机制应用示例。下面以图5中的一个示例拓扑，说明面 向无线多跳网络中网络编码感知路由的流量匹配机制的工作步骤。

在图5(a)中，有3条数据流穿过节点3，根据基本编码结构，可以在节点3对flow 1和flow 2进行编码，另外，节点3的队列长度为5；图5(b)给出了数据包到达顺序； 图5(c)给出了节点3使用顺序调度方法，节点3的先入先出队列变化过程，需要7个 时隙，且只有2个编码包生成；图5(d)给出了节点3使用流量匹配机制，节点3的队 列变化情况。

使用流量匹配机制后，节点3由于有3条数据流flow1、flow2、flow3流经，分别为每条数据流虚拟化一个虚拟队列vq1、vq2、vq3。由于flow1和flow2可在节点3处编 码，则vq1和vq2组成虚拟队列组vqSet，并作为调度的基本单位。

在t0时刻，vq1中有P1、P2、P3，而vq2为空，则vqSet无法生成编码包，设等待 次数M＝3。而vq3非空，则将vq3队首数据包P1发送出去。

在t0+Δt时刻，vq1中有P1、P2、P3，而vq2为空，则vqSet无法生成编码包， M＝M-1＝2而vq3非空，则将vq3队首数据包P2送出去。

在t0+2Δt时刻，vq1中有P1、P2、P3，vq2中有P2，vq3中有P3，而且vqSet中 vq1队首数据包P1的到达时间比vq3中队首数据包P3到达时间早，则vqSet中vq1的 队首数据包P1和vq2的队首数据包P1可以编码后作为编码包发送出去。

在t0+3Δt时刻，vq1中有P2、P3，vq2中有P2、P3，vq3中有P3，而且vqSet中vq1队首数据包P2的到达时间比vq3中队首数据包P3到达时间早，则vqSet中vq1的 队首数据包P2和vq2的队首数据包P2可以编码后作为编码包发送出去。

在t0+4Δt时刻，vq1中有P3、P4，vq2中有P3，vq3中有P3、P4，而且vqSet中 vq1队首数据包P3的到达时间比vq3中队首数据包P3到达时间早，则vqSet中vq1的 队首数据包P3和vq2的队首数据包P3可以编码后作为编码包发送出去。

在t0+5Δt时刻，vq1中有P4，vq2中有P4，vq3中有P3、P4，而且vqSet中vq1 队首数据包P4的到达时间比vq3中队首数据包P3到达时间晚，则vqSet中vq3的队首 数据包P3发送出去。

在t0+6Δt时刻，vq1中有P4，vq2中有P4，vq3中有P4，而且vqSet中vq1队首 数据包P4的到达时间比vq3中队首数据包P4到达时间早，则vqSet中vq1的队首数据 包P4和vq2的队首数据包P4可以编码后作为编码包发送出去。

在t0+7Δt时刻，vq1和vq2均为空，vq3中有P4，则将vq3的队首数据包P4发送 出去。

至此，使用流量匹配后的节点3数据传输调度的数据传输任务结束，共发送4个编码数据包比顺序调度方式多了2个编码数据包，而且数据传输时间比顺序调度方式少了 2个Δt时间，提升了网络编码增益。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员 来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。