基于喷泉码和网络编码的机会路由协议数据分发方法

摘要

一种基于喷泉码和网络编码的机会路由协议数据分发方法，具体步骤包括：(1)在TinyOS系统下，将所有网络节点编号，建立路由信息；(2)将数据分段并编号，计算每个节点的接收阈值；(3)源节点采用喷泉码对数据进行预编码，维护一个控制网络中数据包数量的发送窗口；(4)中间节点对同一段的数据包采用网络编码，使用机会路由方法发送编码数据；(5)信宿节点对数据进行网络解码，对网络解码后的数据段进行喷泉码解码。本发明实现了网络编码和机会路由的结合，增加单次传输的信息量，减少数据包的传输和重传次数，具有可靠数据传输、提高网络效率和节省传感器节点能量消耗的优点。

说明书

技术领域

本发明属于通信技术领域，更进一步涉及一种无线传感器网络中应用喷泉码与网络编码和机会路由协议进行数据分发的方法。该方法应用喷泉码和网络编码对数据进行编码，使用改进的机会路由协议进行数据传输，接收端对收到的数据进行网络解码恢复原始的数据信息，可应用于对无线传感器网络的数据分发。

背景技术

目前，在网络编码为代表的网络通信技术领域中，广泛使用网络编码技术与机会路由技术相结合的方法，达到可靠数据传输和提高网络效率的目的。

Chachulski等人在“Chachulski S，Jennings M，Katti S，Katabi D.Trading structure for randomness in wireless opportunistic routing.In：Proc.of the ACM SIGCOMM 2007.New York：ACM Press，2007.169-180.”提出了一种随机机会路由方法MORE(MAC-independent opportunistic routing and encoding protocol)，该方法将流内随机网络编码(intra-flow random network coding)和机会路由相结合，并利用网络编码来降低重复分组发生的概率。实践证明，这种随机机会路由方法虽然可以提高分组成功投递率，但由于随机机会路由方法是以全网链路状态为基础的，采用“确认等待”策略，不能解决大规模网络中大量网络冗余包的问题，所以路由开销很大，不适合用于无线传感器网络。

Yan Y等人在“Yan Y，Zhang BX，Zheng J，Ma J.CORE：A coding-aware opportunistic routing mechanism for wireless mesh networks.IEEE Wireless Communications，2010，17(3)：96-103.”提出了一种编码感知的机会路由方法CORE(coding-aware opportunistic routing mechanism)，该方法将局部流间网络编码(localized inter-flow network coding)和机会路由相结合，在确定备选转发节点优先级时，以编码机会的大小为依据，使得分组总是尽量转发到编码机会多的节点上去，创造了更多的编码机会，提高了网络吞吐量。CORE虽然提高了多流无线网络的吞吐率，但在执行过程中需要节点保存两跳邻居缓存队列内的分组信息，存储开销较大。

Yan Y等人在“Yan Y，Zhang BX，Hussein M，Ma J.Mechanism for maximizing area-centric coding gains for wireless multi-hop networks.In：Proc.of the IEEE ICC 2009.Washington：IEEE Computer Society Press，2009.”中提出了一种基于编码增益的机会路由方案PACE(probabilistic area-centric network coding mechanism)，该方法是一种网络编码和机会路由的有效结合，节点每次传输都着眼于提升节点附近区域中多个节点的联合编码增益，同时使用编码感知的MAC层传输调度来保证编码机会的实现。但是，PACE也要求网络中每个节点保存两跳邻居信息。

湖南大学申请的专利“基于网络编码的无线传感器网络数据分发方法”(专利申请号：201010295107.5，公布号CN 101951556A)，公开了一种基于网络编码的无线传感器网络数据分发方法。该方法的思路是源节点将要发送的数据包先进行编码后再发送，所有其它节点收到足够的已编码数据包后进行再编码并按相应转发机制进行广播，当节点收到足够的编码包后解码出原始的数据包。该方法的不足之处在于，编码方式采用有比率码，在遇到突发事件的时候不能实时的改变码率，可能导致网络拥塞甚至数据丢失。

发明内容

本发明的目的在于克服现有技术的不足，提出一种基于喷泉码和网络编码的机会路由协议数据分发方法。该方法可以根据网络环境的要求而实时改变码率，可在建立无线传感器网络的telosb传感器节点的失效或传输链路不稳定的情况时，防止数据丢失。

本发明实现的思路是源节点对数据进行喷泉码预编码，中间节点对接收到的数据进行网络编码，并使用机会路由协议发送编码数据，实现了网络编码和机会路由的结合，增加了单次传输的信息量，减少了数据包的传输和重传次数，达到可靠数据传输、提高网络效率和节省传感器节点能量消耗的目的。

本发明的具体步骤如下：

(1)网络初始化

1a)设置telosb节点

将所有telosb节点按照从1开始递增的顺序设置不重复的ID编号；在已设置ID编号的telosb节点中，将主动发送数据的节点指定为源节点，将需要获取数据的节点指定为信宿节点，其余节点指定为中间节点；

1b)建立路由信息

用户根据应用环境布置所有的telosb节点，打开所有telosb节点电源开关；

源节点和信宿节点将控制包按照从1到N的顺序设置为不重复的编号，以洪泛的方式，根据网络中节点的数量广播控制包；

网络中的telosb节点维护一个存储上游节点ID的列表和一个存储下游节点ID的列表，从源节点发出的控制包中取出转发当前控制包的节点ID字段，用来更新上游节点列表，从信宿节点发出的控制包中取出转发当前控制包的节点ID字段，用来更新下游节点列表。

(2)数据初始化

2a)分段处理

用户将需要发送的数据分段，对每段设置一个与其它段不同的标识，段标识按照从0开始递增的顺序编号；

2b)计算中间节点的接收阈值

每个中间节点按照下式分别计算接收阈值T_a：

$T_a=\underset{u_a\in U\left(a\right)}{\max }\left({\Sigma }_{u_c\in U\left(c\right)}{E}_{u_c}{p}_{u_{c}c}\right)\frac{{\Sigma }_{u_a\in U\left(a\right)}{P}_{u_{a}a}}{{\Sigma }_{u_c\in U\left(c\right)}{p}_{u_{c}c}}$

其中，T_a是节点a的接收阈值；U(a)为节点a的上游邻居节点集合，u_a是U(a)集合中的任一节点；c节点是与a节点拥有相同的上游邻居节点，并且是该上游节点的所有下游节点中收包率最高的节点，U(c)为节点c的上游节点集合，u_c是U(c)集合中的任一节点；为节点u_c向节点c发送的数据包个数的期望；为节点u_c向节点c发送数据的概率；为节点u_a向节点a发送数据的概率。

(3)源节点预编码

3a)源节点采用喷泉码对需要发送的数据进行预编码，持续向网络发送编码后的数据，直到收到所有下游邻居节点发送的确认消息后，转入下一段数据的发送；

3b)源节点维护一个发送窗口，源节点收到信宿节点的某数据段的确认消息后，发送窗口平移到与确认消息对应的数据段之后。

(4)中间节点网络编码

4a)中间节点持续接收数据包，直到数据包数量达到该节点的接收阈值，向上游邻居节点发送确认消息，通知上游节点转入下一批数据的发送；

4b)对接收到的同一段数据包进行网络编码，将该编码包以概率p广播；

4c)接收下游邻居节点的当前数据段确认消息，收到所有下游邻居节点的确认消息后，转入下一个数据段的发送。

(5)信宿节点解码

5a)信宿节点收到一个数据包后，检查它对应的数据段是否已经解码，若是就丢弃；若否，则将这个数据包存入数据段的缓存中，并检查这个数据段缓存中线性无关的数据包数是否已经达到网络解码矩阵的秩，若是，则对该数据段进行网络解码；

5b)信宿节点对网络解码后的数据段进行喷泉码解码；

5c)信宿节点对一个数据段的数据解码成功后，向上游节点发送这个数据段的确认消息，并且检测之前的数据段是否也都解码成功了，若是，则向源节点发送一个与数据段对应的确认消息。

本发明与现有的技术相比具有以下优点：

1.本发明通过对数据进行网络编码，使用机会路由协议发送编码数据，增加单次传输的信息量，减少数据包的传输次数和重传次数，与现有技术相比，节省了传感器节点的能量损耗，提高了网络效率。

2.本发明采用喷泉码进行网络编码，喷泉码属于无比率码，因此该方法可以根据网络环境的要求而实时改变码率，克服了现有技术中有比率码必须考虑网络最大丢包率的缺点，在传感器节点失效或传输链路不稳定的情况下，性能提升尤为显著。

3.本发明将喷泉码和网络编码相结合，喷泉码的解码阶段的输入是网络解码后的数据，与现有技术单一编码的方法相比，本发明可以显著提高数据包的解码成功率。

4.本发明在中间节点接收到属于一个数据段的足够多的数据包后，通知上游节点转入下一段数据的发送，即允许多个数据段同时在网络中传输，避免了现有技术采用“确认等待”策略时信源节点持续等待确认消息的情况，尤其在网络规模大、传播时延大的情况下，可以显著减少网络中的数据冗余包，提高数据传输的效率。

附图说明

图1为本发明的流程图；

图2为本发明实施例进行数据分发的单源二信宿网络拓扑示意图；

图3为本发明无线传感网局部网络拓扑示意图；

图4为本发明仿真实验的局部网络拓扑图；

图5为本发明效果仿真图，其中图5(a)为本发明与洪泛方法、无网络编码机会路由方法的网络数据传输效率仿真图；图5(b)为本发明与洪泛方法、无网络编码机会路由方法的网络数据传输时延仿真图。

具体实施方式

下面结合附图对本发明做进一步的描述。

参照图1，本发明的具体实施步骤如下：

步骤1，网络初始化。

1a)设置telosb节点

在TinyOS系统下，将所有telosb节点按照从1开始递增的顺序设置不重复的ID编号；在已设置ID编号的telosb节点中，将主动发送数据的节点指定为源节点，如图2中的1号节点；将需要获取数据的节点指定为信宿节点，如图2中的6、7号节点，其余节点指定为中间节点，如图2中的2～5号节点；

1b)建立路由信息

根据用户需要放置所有的telosb节点，打开所有telosb节点；

源节点和信宿节点将控制包按照从1到N的顺序设置为不重复的编号，以洪泛的方式，根据网络中节点的数量广播控制包；控制包消息包括控制包编号packetID、转发当前控制包的节点nodeID、从源节点或者信宿节点到当前节点控制包经历的跳数Hop，Hop初始化为0；

每个节点存储一个数组Hops[N]，数组中的成员全都初始化为0；同时维护一个上游邻居节点列表和一个下游邻居节点列表。Hops[i]记录的是控制包号为i(1≤i≤N)的控制包第一次到达当前节点所经历的跳数。

节点收到控制包后，检查packetID；

如果是第一次收到该packetID的控制包，则将控制包的Hop字段赋值给Hops[packetID]；然后检查上游节点列表或者下游节点列表中是否存在nodeID，如果不存在，则在上游节点列表或者下游节点列表中增加值为nodeID的新元素；最后，当前节点将自身ID赋值给控制包中的nodeID字段，并将控制包中Hop加1，转发控制包；

如果不是第一次收到该packetID的控制包，检查上游节点列表或者下游节点列表中是否存在nodeID，如果不存在，检查控制包中的Hop是否大于Hops[packetID]，如果不是，则在上游节点列表或者下游节点列表中增加值为nodeID的新元素；

在图2中，以4号节点为例，它的上游节点列表包括2、3，下游节点包括5。

步骤2，数据初始化

2a)分段处理

用户将需要发送的数据分段，每段包含k个数据，k取2的整数次幂，不足k个数据的部分单独作为一段；对每段设置一个与其它段不同的标识，段标识按照从1开始递增的顺序编号；

2b)计算中间节点的接收阈值

在附图3的网络拓扑图中，a、b、c、d、e、f是telosb节点。我们欲计算节点a的接收阈值T_a，先计算出节点a对应于所有上游节点的接收阈值T_ab、T_ac、T_ad，在其中取最大值作为节点a的接收阈值：

$T_a=\underset{b\in U\left(a\right)}{\max }{T}_{\mathrm{ab}}$

节点c是节点b所有下游邻居节点中收包率最高的节点，以节点c为参照来计算节点a对应于节点b的接收阈值T_ab，那么：

$T_{\mathrm{ab}}=\left({\Sigma }_{u_c\in U\left(c\right)}{E}_{u_c}{p}_{u_{c}c}\right)\frac{{\Sigma }_{u_a\in U\left(a\right)}{P}_{u_{a}a}}{{\Sigma }_{u_c\in U\left(c\right)}{p}_{u_{c}c}}$

其中，T_ab是节点a对于上游节点b的接收阈值，U(c)为节点c的上游节点集合，u_c是U(c)集合中的任一节点；U(a)为节点a的上游节点集合，u_a是U(a)集合中的任一节点；为节点u_c向节点c发送的数据包个数的期望；为节点u_c向节点c发送数据的概率；为节点u_a向节点a发送数据的概率。

步骤3，源节点预编码

3a)源节点采用LT(Luby Transform)编码方式的喷泉码对需要发送的数据进行预编码，持续向网络发送编码后的数据，直到收到所有下游邻居节点发送的确认消息后，转入下一段数据的发送，确认消息包括下游邻居节点自身的编号和确认消息对应的数据段编号；

3b)源节点维护一个发送窗口来控制进入网络进行传输的数据段的个数。发送窗口的大小用w表示，即允许最多w个数据段进入网络进行传输。若窗口内最小的数据段段号为l，则发送窗口为[l，l+1，l+2，...，l+w-1]。源节点收到信宿节点发出的数据段l+j的确认消息，表示数据段l+j及其之前的段都已经接收成功，源节点将发送窗口向前平移到[l+j+1，l+j+2，...，l+j+w]。

步骤4，中间节点网络编码

4a)中间节点持续接收数据包，直到数据包数量达到该节点的接收阈值，向上游邻居节点发送确认消息，通知上游节点转入下一批数据的发送；

4b)对接收到的同一段数据包进行网络编码，产生的编码包由数据包与编码向量进行有限域运算得到的：

$p_j^{\prime }=\underset{i=1}{\overset{T}{\Sigma }}{\alpha }_{\mathrm{ji}}{p}_i$

其中，p′_j为编码包，T是中间节点接收阈值，α_ji是从伽罗华域GF(2⁸)中随机选取的编码系数，p_i是中间节点接收到的同一段数据包。将该编码包以概率p广播，p在0.6～0.8之间选取；

4c)接收下游邻居节点的当前数据段确认消息，收到所有下游邻居节点的确认消息后，转入下一个数据段的发送。

步骤5，信宿节点解码

5a)信宿节点收到一个数据包后，检查它对应的数据段是否已经解码，若是就丢弃；若否，就将这个数据包存入数据段的缓存中，并检查这个数据段缓存中线性无关的数据包数是否已经达到网络解码矩阵的秩，若是，就对该数据段进行网络解码；

5b)信宿节点对网络解码后的数据段进行喷泉码解码；

5c)信宿节点对一个数据段的数据解码成功后，向上游节点发送这个数据段的确认消息，并且检测之前的数据段是否也都解码成功了，若是，就向源节点发送一个与数据段对应的确认消息。

本发明的效果可以通过下述仿真实验得到验证：

本发明图5(a)和(b)的仿真环境是：TinyOS-2.1.0，nesC-1.3.0，jdk-1.5.0_16。采用TinyOS系统自带的meyer_heavy.txt作为噪声轨迹的输入。

仿真内容

本发明的仿真实验设置一个节点数为100，任一节点的通信范围内节点数大致为8的随机网络拓扑，如图4所示的网络拓扑局部示意图。0节点为汇聚节点，其通信范围内共有7个节点，以节点10为例，它的通信范围内共有8个节点。设定节点99为信宿节点，则从节点99到节点0的最短路径的跳数为8～12个。

TOSSIM中的仿真实验通过运行python脚本文件来进行。在实验脚本中，通过注入分组的方式给汇聚节点发送命令数据包，控制整个实验的进程，获取仿真数据。

在图4所示的给定随机网络拓扑中进行实验，递增地设置源节点的原始包数量，对网络总发包数和平均时延进行测量。将本发明的方法与泛洪方法、无网络编码的机会路由方法进行比较。得到的仿真结果如图5所示，其中图5(a)为本发明与洪泛方法、无网络编码机会路由方法的网络数据传输效率仿真图；图5(b)为本发明与洪泛方法、无网络编码机会路由方法的网络数据传输时延仿真图。

仿真结果分析

从图5(a)中可以看出，本发明的方法中网络总的发包数仍与源节点的发包数基本呈正比关系，但本发明的方法比无网络编码的机会路由方法更优，这是因为加入网络编码后各转发节点转发的是经过编码的数据包而不是原始包，且各转发节点转发的编码包很少重复，所以降低了转发的冗余度，提高了传输效率。从图5(b)中可以看出，本发明的方法与无网络编码的机会路由方法的平均时延随源节点发包数增加时的变化趋势基本一致，这是因为它们使用了相同的局部拓扑信息获取算法和路由机制，额外的时间开销会在发包数增加的时候平均增益递减。同时可以看到本发明的方法比无网络编码的机会路由方法的平均时延略大，这是由于本发明方法中每次数据发送都要进行编码发送，且中间节点和信宿节点都要进行回复确认，在提高了传输效率的同时增大了时延。但相对加入网络编码带来的传输效率提升而言，时延的略微增大是可以忍受的。