一种联合机会网络编码的机会路由方法

摘要

本发明公开了一种联合机会网络编码的机会路由方法，其步骤：1.发送节点将数据编码打包后待发送；2.广播RTS帧，向发送节点邻居节点传输RTS帧；3.将该RTS帧通过CTS帧反馈其上游节点；4.上游发送节点计算各个下一跳节点的预期传输网络编码数据包次数（ECTX）；5.选择各个下一跳节点中ECTX值最小的下一跳节点作为中继节点；6.计算中继节点网络编码增益，选择编码增益最大的编码组合进行网络编码，该网络编码增益定义为记为：将编码数据包发送，转步骤3，选择中继节点；8.完成源节点至汇聚节点间数据链路的建立。该方法利用机会网络编码有效地将多个源节点数据编码融合，主动选择网络编码机会，提高无线传感器网络性能。

说明书

技术领域

本发明涉及的是一种联合机会网络编码的机会路由方法，主要是在传输过程中传感器节点利用网络编码的编码机会，通过定义最小编码数据包传输数作为机会路由转发传感器节点的选择度量，使得数据传输过程中尽可能多的进行网络编码，提高无线传感器网络的吞吐量。

技术背景

无线传感器网络中数据发送时，源节点需要其它节点的数据中继。路由协议是无线传感器网络中，不可缺少的部分，路由协议在满足业务的QoS需求的同时，还应增强路由的自适应性，减少寻路由的复杂性，降低路由开销，高效利用网络有限的资源。因此，在设计和分配无线传感器网络相关路由协议时，需要进行综合考虑各项因素。

网络编码是在每次传输中利用编码将数据融合，提高传输的信息量，减少传输次数。例如，Wu等在文献[1]、Fragouli等在文献[2]以及Ho等在文献[3]中分别设计和提出了网络编码应用于无线传感器网络方案。在文献[4]和文献[5]分别提出了机会网络编码，该机会网络编具体是：假设每个节点侦听到邻近节点传输的数据，利用侦听到的数据信息进行网络编码。当网络中出现瓶颈链路时，链路的发起节点根据收到的数据包的传输数量，尽可能多利用网络编码，提高瓶颈链路的利用率。这种节点根据数据传输的需要而采用网络编码的机制，使得网络编码在中继节点的机会减少。大量潜在的网络编码机会使得网络吞吐量的进一步提高变成可能。相较于基于网络编码机制的路由协议，以网络编码为目的的路由协议能更加有效地提高网络吞吐量、减少网络传输的开销。然而，现有的机会路由技术主要针对传统的有线网络和有固定基础设施的无线传感器网络，不能直接应用于能量和资源严重受限的无线传感器网络。为了应对无线传感器网络中可靠性差、无线信道丢包严重等问题，为此，本发明提出了一种联合机会网络编码的机会路由方法。

参考文献

[1].      Y. Wu, P.A. Chou, S.Y. Kung, ``Information exchange in wireless networks with network coding and physical layer broadcast,'' Microsoft Corporation, 2004, Redmond, WA, Technical Report.

[2].      C. Fragouli, D. Katabi, A. Markopoulou, M. Medard, H. Rahul, ``Wireless network coding: opportunities and challenges [C],'' Proc. of the IEEE Military Communications Conference MILCOM’07, Oct. 2007, pp:1-8.

[3].      T. Ho, J. Q. Jin, H. Viswanathan, ``On network coding and routing in dynamic wireless multicast networks [C],'' Proc. of the workshop on information theory and its applications, 2006, SanDiego(UCSD): University of California, pp:1-4.

[4].      S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, ``Xors in the air: practical wireless network coding [J],'' Computer Communication Review, 2006, vol.36, no.4, pp:243-254.

[5].      W. Chen, K. Letaief, Z. Cao, ``Opportunistic network coding for wireless networks [C],'' Proc. of IEEE International Conference on Communications ICC'07, June 2007, Glasgow, Scotland, United kingdom, pp:4634-4639。

发明内容

本发明的目的在于，提出了一种联合机会网络编码的机会路由方法。利用无线传输特性，主动选择网络编码机会，有效地提高网络的整体性能。

为达到上述目的，我们作如下研究：

定义无线传感器网络抽象成有向图，记为： 

，

其中，表示网络中传感器节点集合，表示传感器节点间的无线链路集合。

其中传感器节点集合由用于采集数据的传感器节点集合数据汇聚节点构成，具体如下：

                    (1)   和

                            (2)

式(1)、式(2)中，为传感器节点，，为汇聚节点，，Ns为源节点个数，Nt为汇聚节点个数。

为节点序号，为节点序号，为节点到节点的无线链路，和分别表示链路上的链路容量和数据流速率，其中，；

传感器节点，为汇聚节点集合，即接收传感器节点的所有汇聚节点集合。汇聚节点，为源节点的子集，其中，各元素节点的目的汇聚节点均为；

先前的机会路由中，路由选择的准则为最小跳数，例如，预期的传输计数(ETX)。链路传输概率为，则ETX表示为：，路由选择准则是：期望中继转发节点进行网络编码，将收到的数据进行编码组合，提高无线传感器网络的吞吐量。

定义编码传输数(ECTX)

定义编码传输数（the expected coded transmission ECTX）作为中继节点转发优先级，利用编码传输数作为路由选择的度量，利用网络编码技术既要解决数据流之间的冲突，又要提高无线传感器网络吞吐量，机会路由方法目标是选择提高网络端到端吞吐量的路径，在信源节点数据传输路由协议中， 编码传输数表达式为:

                         (3)    

式(3)中，为传感器节点，为发送数据至节点的节点集合，为接收节点发送数据的节点集合；

假设每个中继节点有一个用于数据缓冲的队列区，将不同源节点的数据存入数据缓冲的队列区，不同队列区存放不同源节点的数据。如图1所示，假设一个中继节点有h个缓冲，接收节点发送的数据；

传感器节点和传感器节点分别将采集的数据发送至汇聚节点，传感器节点和传感器节点将采集的数据发送至对应的汇聚节点为。则汇聚节点，其源节点集合为：， 对应于节点 。

以中继节点节点四种数据编码组合，如表1所示。

表1: 节点v中数据编码组合的各种组合

其中，定义为不同数据包编码后的网络编码增益，以表1为例，i=1，2，3，4。，网络编码解码在汇聚节点条件下，中继节点选择编码增益大的编码组合，定义中继节点网络编码增益，其表达式为：

     (4)

式(4)中，为不同数据包编码后的网络编码增益的最大值，  表示 到占用链路的状态， 表示链路被占用，表示链路未被占用， 表示到 的数据传输速率。

数据发送的源节点和中继节点发送节点以广播形式传递数据包，数据包发送的源节点和中继节点在开始时，广播RTS帧，向其相邻的节点要求配合数据传输，收到RTS帧的中继节点，计算选择编码后编码增益，并将该数据通过CTS帧告知其上游源节点和中继节点。

根据上述原理，本发明采用下述技术方案：

一种联合机会网络编码的机会路由方法，其特征在于：

步骤1：源节点采集视频数据，将数据编码打包发送至数据包发送节点；

步骤2：数据发送节点发送数据包前，广播RTS帧，向发送节点邻居节点传输RTS帧；

步骤3：邻居节点收到RTS帧，将该RTS帧通过CTS帧反馈其上游节点；

步骤4：上游发送节点计算各个下一跳节点的预期传输网络编码数据包次数（ECTX）；

步骤5：上游发送节点选择各个下一跳节点中ECTX值最小的下一跳节点作为中继节点；

步骤6：判断中继节点是否为汇聚节点，若为汇聚节点，则转步骤8，否则转步骤7；

步骤7：中继节点根据收到的数据包次数（ECTX），计算中继节点网络编码增益，为可能的数据编码组合种数，中继节点选择编码增益最大的编码组合进行网络编码，该网络编码增益定义为该中继节点处网络编码最大增益增加记为：，将编码数据包发送，跳转至步骤3，继续选择中继节点；

步骤8：数据发送至汇聚节点，完成源节点至汇聚节点间数据链路的建立。

上述步骤4所述的上游发送节点计算各个下一跳节点的预期传输网络编码数据包次数（ECTX），其编码传输数表达式为:

                                 (3)

 式(3)中，为传感器节点，为发送数据至节点的节点集合，为接收节点发送数据的节点集合；上述步骤7所述的计算中继节点网络编码增益，其表达式为：

     (4)

式(4)中，为不同数据包编码后的网络编码增益的最大值， 表示到占用链路的状态，表示链路被占用，表示链路未被占用，表示到的数据传输速率。

本发明中的联合机会网络编码的机会路由方法与现有技术相比较，具有的以下优点：该方法利用机会网络编码有效地将多个源节点数据编码融合，主动选择网络编码机会，使得有限的链路被合理有效使用，提高无线传感器网络的性能。通过仿真实验，对本发明提出的路由方式进行了性能分析，并与其他路由方法进行比较。性能分析与数值模拟的结果均说明采用本发明提出的路由方法，能够获得较好的网络性能。

附图说明

图1是中继节点、传感器节点、汇聚节点、的数据接收发送示意图。

图2是本发明的实施例中网络拓扑结构示意图。

图3是本发明的一种联合机会网络编码的机会路由方法的流程图。   

图4是不同路由机制下源节点端到端吞吐量比较图。

图5是丢包环境下采用三种不同路由方法中每个源节点端到端的吞吐量比较图。

图6是不同负载下采用三种不同路由方法中网络吞吐量比较图。

具体实施方式

下面结合附图和具体实施方式对本发明的实施例作进一步详细的描述。

假设一个无线传感器网络，其拓扑结构如图2所示，50米×50米范围内的网络由10个传感器节点和2个汇聚节点构成，对于汇聚节点的源节点集合为：，汇聚节点的源节点集合为：， 网络中的无线链路具有相同的有限链路带宽 1 Mbps 。

如图3所示，本发明的一种联合机会网络编码的机会路由方法，其具体步骤如下:

根据上述原理，本发明采用下述技术方案：

一种联合机会网络编码的机会路由方法，其特征在于：

步骤1：源节点采集视频数据，将数据编码打包发送至数据包发送节点；

步骤2：数据发送节点发送数据包前，广播RTS帧，向发送节点邻居节点传输RTS帧；

步骤3：邻居节点收到RTS帧，将该RTS帧通过CTS帧反馈其上游节点；

步骤4：上游发送节点计算各个下一跳节点的预期传输网络编码数据包次数（ECTX）；

步骤5：上游发送节点选择各个下一跳节点中ECTX值最小的下一跳节点作为中继节点；

步骤6：判断中继节点是否为汇聚节点，若为汇聚节点，则转步骤8，否则转步骤7；步骤7：中继节点根据收到的数据包次数（ECTX），计算中继节点网络编码增益，为可能的数据编码组合种数，中继节点选择编码增益最大的编码组合进行网络编码，该网络编码增益定义为该中继节点处网络编码最大增益增加记为：，将编码数据包发送，跳转至步骤3，继续选择中继节点；

步骤8：数据发送至汇聚节点，完成源节点至汇聚节点间数据链路的建立。

上述步骤4所述的上游发送节点计算各个下一跳节点的预期传输网络编码数据包次数（ECTX），其编码传输数表达式为：

                                  (3)

    式(3)中，为传感器节点，为发送数据至节点的节点集合，为接收节点发送数据的节点集合；上述步骤7所述的计算中继节点网络编码增益，其表达式为：

      (4)

式(4)中，为不同数据包编码后的网络编码增益的最大值， 表示到占用链路的状态，表示链路被占用，表示链路未被占用，表示到的数据传输速率。

下面给出使用本发明的方法的数值仿真实验，具体如下，首先，假设所有数据包均被正确接收，采用最短路径树算法路由（Shortest Path Tree SPT），每个源节点选择距汇聚节点最短路径传输数据，需要与其他数据竞争链路带宽。图4为不同路由机制下源节点到汇聚节点端到端吞吐量比较图。由于链路被和同时占用，因此节点和节点到汇聚节点的端到端吞吐量低。利用网络编码，节点能将节点和节点的数据编码融合，链路的带宽可以被两个节点共享。然而基于网络编码的路由机制（NC-based OR），只是在瓶颈链路，如链路，被动进行网络编码。在联合机会网络编码的机会路由方法（OR with ONC）下，数据发送节点则是主动选择编码机会、传输编码数据包少的节点请求转发。利用机会网络编码的机会路由，汇聚节点的接收吞吐量可以达到最小割上限。

为了评估算法在不可靠的无线传输环境中的传输性能，假设每条无线链路有一个随机正确接收概率，在[0,1]上服从均匀分布。图5为丢包环境下，选择不同路由方法每个源节点端到端吞吐量的比较图，本发明的方法与最短路径树算法和基于网络编码的路由方法相比较，从图6中可以看出，本发明的一种联合机会网络编码的机会路由方法下，源节点能获得更大的端到端吞吐量。

当源节点负载小时，网络编码的机会少，从图6可以看出，三种路由方法下网络吞吐量变化随着负载的增加，采用本发明的联合机会网络编码的机会路由方法可以获得更高的吞吐量；当负载大到一定程度后，因为多条数据传输路径相交叉使得网络编码的机会增加，联合机会网络编码的机会路由方式可以得到最高的网络吞吐量。