一种基于网络编码的TDMA无线网络多路径数据传输方法

摘要

本发明公开了一种基于网络编码的TDMA无线网络多路径数据传输方法，属于通信技术领域。所述方法包括源节点初始化时建立网络编码系数有限域，对预发送数据的m个初始数据包进行线性随机网络编码，结合搜索路由获得多路径转发的最优路径和次优路径的邻居节点集与收到的ACK回复选择下一跳中继节点，每一中继节点对收到的编码数据包从网络编码系数有限域随机选择编码系数对所述编码数据包重新编码并发送给下一中继节点，直至目的节点收到大于等于m个系数向量线性无关的编码数据包并从中恢复出初始信息向量。本发明通过多路径路由策略与网络编码策略的结合，在提高网络吞吐量，增强数据传输可靠性的同时，缓解多条路径同时发送数据引起的网络拥塞的问题。

权利要求

1.一种基于网络编码的TDMA无线网络多路径数据传输方法，其特征在于，包括：S1，源节点对预发送数据的m个初始数据包进行线性随机网络编码，生成编码数据包组，其中第k个编码数据包为 其中：eik为从网络编码系数有限域中随机选择的编码系数，i为数据包序号，m为数据包个数；所述网络编码系数有限域在源节点初始化时建立；

S2，当前节点通过搜索路由获得多路径转发的最优路径和次优路径的邻居节点集；对所述邻居节点集中包含的所有邻居节点广播发送所述编码数据包并等待所述邻居节点的ACK回复；

S3，根据所述邻居节点的ACK回复确定下一跳中继节点，具体来说，如果节点ny为当前节点到达目的节点最优路径的下一跳，对于任一非节点ny的邻居节点n接收到了节点ny的ACK确认包，从确认包中获得节点ny的下一跳邻居节点集合，若邻居节点n到达目的节点的多路径中邻居节点集合与节点ny的下一跳邻居节点集合有重合，则邻居节点n为所述下一跳中继节点，从所述网络编码系数有限域中随机选择编码系数对所述编码数据包重新编码，更新所述编码数据包并广播给自己的下一跳邻居；如果节点ny为到达目的节点的非最优路径的下一跳，节点nz为最优路径的下一跳，则节点nz为所述下一跳中继节点，从所述网络编码系数有限域中随机选择编码系数对所述编码数据包重新编码，更新所述编码数据包并广播给自己的下一跳邻居；

S4，重复步骤S2和S3，直到目的节点收到大于等于m个系数向量线性无关的编码数据包；通过所述网络编码系数有限域从所述目的节点收到的大于等于m个系数向量线性无关的编码数据包中恢复出初始信息向量，获得所述m个初始数据包。

2.一种如权利要求1所述的基于网络编码的TDMA无线网络多路径数据传输方法，其特征在于，所述当前节点发送所述编码数据包的步骤包括：为每个出端口建立数据队列，所述数据队列用于存放所述预发送数据，为每个所述数据队列建立定时器；所述数据队列占满或者所述定时器到期时，对所述数据队列中的所述预发送数据进行所述线性随机网络编码，生成所述编码数据包，并将所述编码数据包发送到所述下一跳中继节点。

3.一种如权利要求2所述的基于网络编码的TDMA无线网络多路径数据传输方法，其特征在于，所述通过搜索路由获得多路径转发的最优路径和次优路径的邻居节点集的步骤包括：所述源节点首先根据报文目的IP地址搜索路由表，获得多路径的路由表项；根据所述路由表项判断所述最优路径和所述次优路径的出端口及邻居节点情况，若所述最优路径和所述次优路径的出端口一致，则所述预发送数据包进入同一所述出端口的数据队列等待网络编码；若出端口不一致，则分别进入所述最优路径的出端口与所述次优路径的出端口等待所述线性随机网络编码。

4.一种如权利要求1所述的基于网络编码的TDMA无线网络多路径数据传输方法，其特征在于，所述m个初始数据包分别为p1、......pm，转化为采用FIFO策略的缓冲区内存放的第一消息向量为P1、......Pm，通过从所述网络编码系数有限域中随机选择的编码系数中独立产生m个随机数组成m维向量Ek＝{e1k，e2k，...emk}作为第一消息向量的系数，对所述第一消k

息向量进行网络编码，获得第二消息向量P，其中，

5.一种如权利要求4所述的基于网络编码的TDMA无线网络多路径数据传输方法，其特

1 2 m

征在于，所述目的节点接收到不小于m份系数向量线性无关的数据P、P ......P ，就可以恢复出所述第一消息向量P1、......Pm，其中进而获得所述m个初始数

据包p1、......pm。

说明书

一种基于网络编码的TDMA无线网络多路径数据传输方法

技术领域

[0001] 本发明涉及通信技术领域，具体涉及一种基于网络编码的TDMA无线网络多路径数据传输方法。

背景技术

[0002] 数据传输是无线网络的基本功能，由于无线信道容易受周围环境、传输距离、移动性等多方面影响，使得传输误码率高、链路状态不稳定、拓扑结构动态变化，使得采用分布
式、自组织方式灵活组网的无线多跳网络与常规网络有较大区别，数据的可靠传输能力受
到严重限制。

[0003] 传统的无线网络基于“存储‑转发”采用逐跳重传确认机制提高数据传输可靠性。在通信链路质量比较差的情况下，频繁的重传导致信道带宽利用率低。

[0004] 多路径路由策略在网络层面被广泛应用以提高数据传输可靠性，但也会带来多条路径同时发送数据引起的网络拥塞问题，而且现有的多路径机制都在数据流出现之前预先
计算并确定了传输路径，没有考虑到数据包传输过程中存在的网络编码机会。

发明内容

[0005] 有鉴于此，本发明提供的一种基于网络编码的TDMA无线网络多路径数据传输方法，通过多路径路由策略与网络编码策略的结合，在提高网络吞吐量，增强数据传输可靠性
的同时，缓解多条路径同时发送数据引起的网络拥塞的问题。

[0006] 本发明提供了一种基于网络编码的TDMA无线网络多路径数据传输方法，该方法包括：

[0007] S1，源节点对预发送数据的m个初始数据包进行线性随机网络编码，生成编码数据包组，其中第k个编码数据包为 其中：eik为从网络编码系数有限域中随机选择的编
码系数，i为数据包序号，m为数据包个数；所述网络编码系数有限域在源节点初始化时建
立；

[0008] S2，当前节点通过搜索路由获得多路径转发的最优路径和次优路径的邻居节点集；对所述邻居节点集中包含的所有邻居节点广播发送所述编码数据包并等待所述邻居节
点的ACK回复；

[0009] S3，根据所述邻居节点的ACK回复确定下一跳中继节点，所述下一跳中继节点从所述网络编码系数有限域中随机选择编码系数对所述编码数据包重新编码，更新所述编码数
据包；

[0010] S4，重复步骤S2和S3，直到目的节点收到大于等于m个系数向量线性无关的编码数据包；通过所述网络编码系数有限域从所述目的节点收到的大于等于m个系数向量线性无
关的编码数据包中恢复出初始信息向量，获得所述m个初始数据包。

[0011] 作为本发明的进一步改进，所述当前节点发送所述编码数据包的步骤包括：为每个出端口建立数据队列，所述数据队列用于存放所述预发送数据，为每个所述数据队列建
立定时器；所述数据队列占满或者所述定时器到期时，对所述数据队列中的所述预发送数
据进行所述线性随机网络编码，生成所述编码数据包，并将所述编码数据包发送到所述下
一跳中继节点。

[0012] 作为本发明的进一步改进，所述通过搜索路由获得多路径转发的最优路径和次优路径的邻居节点集的步骤包括：所述源节点首先根据报文目的IP地址搜索路由表，获得多
路径的路由表项；根据所述路由表项判断所述最优路径和所述次优路径的出端口及邻居节
点情况，若所述最优路径和所述次优路径的出端口一致，则所述预发送数据包进入同一所
述出端口的数据队列等待网络编码；若出端口不一致，则分别进入所述最优路径的出端口
与所述次优路径的出端口等待所述线性随机网络编码。

[0013] 作为本发明的进一步改进，所述m个初始数据包分别为p1、......pm，转化为采用FIFO策略的缓冲区内存放的第一消息向量为P1、......Pm，通过从所述网络编码系数有限域
中随机选择的编码系数中独立产生m个随机数组成m维向量Ek＝{e1k，e2k，...emk}作为第一
k
消息向量的系数，对所述第一消息向量进行网络编码，获得第二消息向量P，其中，

[0014]

[0015] 作为本发明的进一步改进，所述目的节点接收到不小于m份系数向量线性无关的1 2 m
数据P、P、.....P，就可以恢复出所述第一消息向量P1、......Pm，其中

[0016]

[0017] 进而获得所述m个初始数据包p1、......pm。

[0018] 籍由上述技术方案，本发明提供的有益效果如下：

[0019] (1)面向数据流，采用流内网络编码，数据校验纠错能力较强。

[0020] (2)根据数据报文目的节点IP地址搜索路由表，获得多路径的路由表项，并判断最优路径和次优路径，通过放弃与最优路径和次优路径无关的节点，有效降低多条路径同时
发送数据引起的网络拥塞。

[0021] (3)无需在数据流出现之前预先计算并确定传输路径，数据传输灵活。

[0022] 上述说明仅是本发明技术方案的概述，为了能够更清楚了解本发明的技术手段，而可依照说明书的内容予以实施，并且为了让本发明的上述和其它目的、特征和优点能够
更明显易懂，以下特举本发明的具体实施方式。

附图说明

[0023] 通过阅读下文优选实施方式的详细描述，各种其他的优点和益处对于本领域普通技术人员将变得清楚明了。附图仅用于示出优选实施方式的目的，而并不认为是对本发明
的限制。而且在整个附图中，用相同的参考符号表示相同的部件。在附图中：

[0024] 图1为本发明实施例提供的一种基于网络编码的TDMA无线网络多路径数据传输方法中，源节点数据网络编码处理流程图；

[0025] 图2为本发明实施例提供的一种基于网络编码的TDMA无线网络多路径数据传输方法中，中继节点数据处理流程图；

[0026] 图3为本发明实施例提供的一种基于网络编码的TDMA无线网络多路径数据传输方法中，源节点采用线性随机网络编码生成数据的示意图；

[0027] 图4为本发明实施例提供的一种基于网络编码的TDMA无线网络多路径数据传输方法中，网络编码数据多路径转发的示意图。

具体实施方式

[0028] 下面将参照附图更详细地描述本公开的示例性实施例。虽然附图中显示了本公开的示例性实施例，然而应当理解，可以以各种形式实现本公开而不应被这里阐述的实施例
所限制。相反，提供这些实施例是为了能够更透彻地理解本公开，并且能够将本公开的范围
完整的传达给本领域的技术人员。

[0029] 首先，在对本发明实施例进行描述的过程中出现的部分名词或者术语适用于如下解释：

[0030] TDMA：时分多址Time division multiple access的缩写，是一种为实现共享传输介质(一般是无线电领域)或者网络的通信技术。它允许多个用户在不同的时间片(时隙)来
使用相同的频率。用户迅速的传输，一个接一个，每个用户使用他们自己的时间片。这允许
多用户共享同样的传输媒体(例如：无线电频率)。

[0031] 本发明要解决的核心技术问题为，在TDMA无线网络多路径数据传输中提升数据传输可靠性与降低网络拥塞之间的矛盾问题。

[0032] 针对上述技术问题，本发明提出一种基于网络编码的TDMA无线网络多路径数据传输方法，通过中间转发节点对信息编码，并传输编码后的信息，通过“存储‑编码‑转发”，提
升数据传输可靠性；通过在每个传输节点计算最优路径和次优路径，有效降低多条路径同
时发送数据引起的网络拥塞；解决数据传输可靠性与降低网络拥塞之间的矛盾问题。

[0033] 实施例1

[0034] S1，源节点对预发送数据的m个初始数据包进行线性随机网络编码，生成编码数据包组，其中第k个编码数据包为 其中：eik为从网络编码系数有限域中随机选择的编
码系数，i为数据包序号，m为数据包个数；所述网络编码系数有限域在源节点初始化时建
立；

[0035] 图3为本发明实施例提供的一种基于网络编码的TDMA无线网络多路径数据传输方法中，源节点采用线性随机网络编码生成数据的示意图。

[0036] 如图3所示，对于无线网络中任一通信节点s∈N在给定时间t内预发送m个数据包分别为p1、......pm至目的节点d∈N，即采用FIFO策略的缓冲区内存放的消息向量为
P1、......Pm，独立产生m个随机数组成m维向量E＝{e1，e2，...em}作为消息向量的系数，从而
1
获得一个新的消息向量P：

[0037]

[0038] 数据在转发过程中的中继节点f∈N若在给定时间t内收到多份不同的数据时，还可以再次编码，通过把不同的数据融合在一起，减少了对单份数据的依赖，进一步减少数据
相关性。

[0039] 其中第k个m维向量Ek＝{e1k，e2k...emk}，第k个消息向量Pk为：

[0040]

[0041] S2，当前节点通过搜索路由获得多路径转发的最优路径和次优路径的邻居节点集；对所述邻居节点集中包含的所有邻居节点广播发送所述编码数据包并等待所述邻居节
点的ACK回复；

[0042] 源节点src∈N在发送数据给目的节点dst∈N时，首先根据线性随机网络编码不断生成编码数据包，其中第k个编码包为 eik为从有限域中随机选择的编码系数；搜索
路由获得多路径转发的邻居节点neigh＝{n1、n2...nx}，其中x为邻居节点个数，并连续对这
些邻居节点广播发送编码数据，直到收到某个邻居节点ny的ACK确认包为止。图1为本发明
实施例提供的一种基于网络编码的TDMA无线网络多路径数据传输方法中，源节点数据网络
编码处理流程图，从图1中可以看出具体的步骤如下：

[0043] 步骤1：在源节点初始化过程中，建立网络编码系数有限域，根据多路径转发原则为每个路由端口建立数据队列，保存预发送的数据；同时为每个队列建立定时器，防止在队
列未满的情况下，超长甚至无限期等待下一个数据包的情况；

[0044] 步骤2：当接收到来自终端需要转发的数据时，源节点首先根据报文目的IP地址搜索路由表，获得多路径的路由表项，并判断最优路径和次优路径的出端口及邻居情况，若出
端口一致，则数据包进入同一端口队列等待网络编码，否则若出端口不一致，则进入不同的
端口队列等待网络编码。当出端口队列长度满员且定时器未到期的情况下，为数据进行网
络编码，并从出端口发送，并启动重传机制等待ACK回复；当定时器到期时，无论队列是否满
员，均对队列中已存在的数据进行网络编码，发送数据并等待ACK回复。

[0045] S3，根据所述邻居节点的ACK回复确定下一跳中继节点，所述下一跳中继节点从所述网络编码系数有限域中随机选择编码系数对所述编码数据包重新编码，更新所述编码数
据包；

[0046] 图2为本发明实施例提供的一种基于网络编码的TDMA无线网络多路径数据传输方法中，中继节点数据处理流程图；从图2中可以看出具体的步骤如下：

[0047] 如果ny为到达目的地dst最优路径的下一跳，对于任一邻居节点n∈neigh，且n≠ny，接收到了ny的ACK确认包，从确认包中获得ny的下一跳邻居节点集合，若n到达目的地dst
的多路径中邻居节点集合与ny的下一跳邻居节点集合有重合，即两者之间存在公共的邻居
节点到达目的地dst，则邻居n将自己接收到的编码数据包进行随机编码产生新的编码包，
并再把编码包广播给自己的下一跳邻居。如果ny为到达目的地dst的非最优路径的下一跳，
nz为最优路径的下一跳，则nz将自己接收到的编码数据包进行随机编码产生新的编码包，并
再把编码包广播给自己的下一跳邻居。

[0048] S4，重复步骤S2和S3，直到目的节点收到大于等于m个系数向量线性无关的编码数据包；通过所述网络编码系数有限域从所述目的节点收到的大于等于m个系数向量线性无
关的编码数据包中恢复出初始信息向量，获得所述m个初始数据包。

[0049] 图4为本发明实施例提供的一种基于网络编码的TDMA无线网络多路径数据传输方法中，网络编码数据多路径转发的示意图。

[0050] 从图4中可以看出，目的节点dst最终接收到经过中继节点转发的不小于m份系数1 2 m
向量线性无关的数据P、P、......P ，就可以恢复出初始信息向量P1、......Pm，获得初始的
m个数据包p1、......pm。具体恢复算法如下：

[0051]

[0052] 最后目的节点dst接收到不小于m份系数向量线性无关的数据，就可以恢复出初始数据，否则沿路径相反方向请求再次发送新的编码数据，要求其向量系数和已有数据线性
无关，若请求失败，则丢弃报文，并告知源节点。

[0053] 在此提供的算法和显示不与任何特定计算机、虚拟系统或者其它设备固有相关。各种通用系统也可以与基于在此的示教一起使用。根据上面的描述，构造这类系统所要求
的结构是显而易见的。此外，本发明也不针对任何特定编程语言。应当明白，可以利用各种
编程语言实现在此描述的本发明的内容，并且上面对特定语言所做的描述是为了披露本发
明的最佳实施方式。

[0054] 在此处所提供的说明书中，说明了大量具体细节。然而，能够理解，本发明的实施例可以在没有这些具体细节的情况下实践。在一些实例中，并未详细示出公知的方法、结构
和技术，以便不模糊对本说明书的理解。

[0055] 类似地，应当理解，为了精简本发明并帮助理解各个发明方面中的一个或多个，在上面对本发明的示例性实施例的描述中，本发明的各个特征有时被一起分组到单个实施
例、图、或者对其的描述中。然而，并不应将该公开的方法解释成反映如下意图：即所要求保
护的本发明要求比在每个权利要求中所明确记载的特征更多的特征。更确切地说，如下面
的权利要求书所反映的那样，发明方面在于少于前面公开的单个实施例的所有特征。因此，
遵循具体实施方式的权利要求书由此明确地并入该具体实施方式，其中每个权利要求本身
都作为本发明的单独实施例。

[0056] 此外，本领域的技术人员能够理解，尽管在此所述的一些实施例包括其它实施例中所包括的某些特征而不是其它特征，但是不同实施例的特征的组合意味着处于本发明的
范围之内并且形成不同的实施例。例如，在下面的权利要求书中，所要求保护的实施例的任
意之一都可以以任意的组合方式来使用。

[0057] 应该注意的是上述实施例对本发明进行说明而不是对本发明进行限制，并且本领域技术人员在不脱离所附权利要求的范围的情况下可设计出替换实施例。在权利要求中，
不应将位于括号之间的任何参考符号构造成对权利要求的限制。单词“包含”不排除存在未
列在权利要求中的元件或步骤。位于元件之前的单词“一”或“一个”不排除存在多个这样的
元件。本发明可以借助于包括有若干不同元件的硬件以及借助于适当编程的计算机来实
现。在列举了若干装置的单元权利要求中，这些装置中的若干个可以是通过同一个硬件项
来具体体现。单词第一、第二、以及第三等的使用不表示任何顺序。可将这些单词解释为名
称。