基于网络编码的传感网多径路由模型分析

赵 炜，唐振民，纪淑标，古 力，杨余旺

（南京理工大学 计算机学院，江苏 南京210094）

0 引 言

由于无线传感器网络 （WSN）节点多且网络具有不稳定性，传统的单径传输很难满足网络传输的要求。多径路由可在一次路由发现过程中找到多条路径［1－5］，从而减少路由发现的次数，同时利用多条链路的冗余特性，提高整个网络成功交付率，降低控制开销与端到端延迟。多径路由的稳定性和提资源利用率高的特点，使其更适合QoS路由要求。多路径可以分为两类：一类是不相交多径路由 （disjoint multipath routing，DMR），每条路径都不相交，每个节点只能在一条路径中出现；另一类是相交多径路由（braided multipath routing，BMR），一个节点可以在多条路径中出现。但在WSN中应用多径路由技术也面临一些新的挑战：一方面，由于多径路由技术采用并行方式传输数据报文，各路径的带宽、跳数以及节点处理能力的差异导致报文传输延时差别较大，在目的端会出现报文乱序现象；另一方面，WSN拓扑变化和链路差错引起的路径中断会导致某些路径拥塞，从而产生报文丢失现象。当网络规模较大时，采用传统的解决方案如报文重排序和报文重传机制将极大地增加网络传输代价，因此，多径路由应用在WSN中也有一定的局限性。

网络编码理论［6－9］论证了中间节点对信息的数学运算可以提高网络吞吐率，同时可以使网络容量逼近网络最大流。文献 ［10］研究网络编码在缠绕多径路由中应用，证明使用网络编码能够提高网络的稳定性和可靠性。文献 ［11－15］系统地讨论了网络编码技术在传感器网络中的理论研究和应用，采用了一系列的评价指标评估了网络编码技术与多径路由的性能。本文主要分析讨网络编码在不相交多路径和缠绕多路径两种网络环境中的性能，进一步讨论采用网络编码技术后的成功交付率和网络冗余度。通过计算仿真，发现相对于传统多径路由，采用该方法能够在一定的报文丢失范围内有效提升多径路由的容错能力，提高网络成功交付率，并降低网络冗余度。

1 基于网络编码的多径路由传感器网络模型

1.1 应用网络编码的不相交多路径传感器网络模型

本节采用经典的多径网络模型，网络拓扑如图1所示。N条不相交的路径分别记为第1到N条，其中每条路径除发送端，包含的节点个数记为ni，i＝1，2，…，N，接收端为第ni个节点。

图1 不相交多经路由网络拓扑

模型采用分包传输思想，应用随机线性编码方案作为编码方法。先是把数据包 （长度L）分成N个大小相等的数据包，然后对分割后的包再拆分成K个数据包，采用随机线性编码将K个包编码生成K′个数据包 （K′≥K）。编码后包长度为：L′＝L∕NK＋K，编码后包每次转发正确的概率为：p＝ （1－pb）L′，其中，pb为每字节传输误码率，根据随机网络编码理论，每次传输时接收端只要正确接收K个线性不相关数据包就可还原出正确的原始数据包，所以每次正确接收K个或者多于K个数据包的概率可以由式 （1）表示

每条路径需要发送ni次，计算出每条路径正确接收率为qi＝qni。成功交付率 （successful delivery ratio，SDR），指由发送端发送的数据包成功正确地到达接收端的概率，因此成功交付率可由式 （2）给出

每条路径转发数据包总量可以由式 （3）给出

标准化冗余度 （normalized redundancy，NR），指成功交付一个数据包所平均需要在网络中传递的数据包的总数。根据标准化冗余度的定义，可以得到该模型的标准化冗余度如下所示

1.2 应用网络编码的相交多路径传感器网络模型

建立基于簇的相交多路径路由模型［1］，网络拓扑如图2所示。网络中节点分为N个簇，分别记为第1到N簇。其中每个簇里面包含的节点个数记为ni，其中i＝1，2，…，N，接收端在第N个簇中。

图2 相交多经路由网络拓扑

应用随机线性编码方案作为编码方法，发送端把报文拆分成K个数据包，编码后生成的数据包个数K′（K′≥K），假定被编码成K′＝K＋2个数据包。ai，k表示第i个节点集合里的任意一个节点正确收到k个数据包的概率，其中1≤i≤N，0≤k≤K。对于第一簇中的节点，由于无线信道出错事件是相互独立的，于是其收到k个数据包的概率服从参数为K′和p的贝努利事件，故a1，k可以由式 （5）计算出来

由于中间节点会对收到的所有数据包重新进行编码，并且对编码后的数据包进行转发，所以，在任意簇中的节点向下一簇广播数据包时，数据包可能会有差错。每个数据包出错的事件是相互独立的，记m为当前节点将要向下一簇转发的数据包个数，传输多个数据包时有k个数据包正确地被下一簇中的节点接收的概率服从贝努利分布，把第i个簇中的节点从1到ni编号，用bi，j，k表示第i个簇中的任意一个节点正确接收到来自上一个簇中第j个节点恰好k个数据包的概率。在本模型中，为了降低网络冗余度，中间节点在转发的过程中，对于同一组的不同的数据包，最多只转发K个，于是对于i≥2，1≤j≤ni，1≤k≤K的情况，bi，j，k由式 （6）所示

这个模型中，并不区分每一簇中的任意两个节点，所以对于第i个簇来说，它从第i－1个簇中的任意一个节点收到k个数据包的概率实际上是相同的。而当i≥2时的ai，k便等于第i个簇中的任意节点从第i－1个簇中的每一个节点收到的数据包之总数为k的所有节点组合的概率之和。对于2≤i≤N，1≤j≤ni，0≤k≤K，ai，k由式 （7）所示

式 （5）与式 （7）计算了每一个节点正确收到数据包从0到K－1个的概率。只要编码系数的有穷域容量足够大，目的节点收到的数据包个数大于或者等于K，就可以解码出原始数据包。因此成功交付率即目的节点收到的数据包个数大于或者等于K个的概率，由式 （8）计算

源节点发送了K′个数据包给第1个节点集，而从第2个节点集开始，每一簇的节点也是采用广播的方式向下一簇节点传递数据包，并且每一个中间节点在正确收到K个或者多余K个数据包的情况下也仅仅是转发K个数据包。于是，整个系统中所传递过的数据包总数可以通过累加得到，所以该系统的标准化冗余度由式 （9）表示

2 性能分析比较

为了更好地比较两种模型性能，本文对图1、图2两种模型拓扑进行了统一，因此，不相交多径路由模型修改简化为基于簇的模型，拓扑图如图3所示，模型每条路径长度为N，路径跳数为ni，且n1＝n2＝…＝ni。

图3 简化后的不相交多路径网络拓扑

2.1 使用网络编码前后性能分析

根据式 （2）、式 （4）、式 （8）、式 （9）可以得出图4所示的使用网络编码前后性能比较图，图中分别给出不相交多径路由模型和相交多径路由模型的成功交付率与标准化冗余度随误码率变化曲线。分析计算所使用的参数为：簇数5、每簇节点个数2、传输数据512个字节、每组数据包个数3。

图4 使用网络编码前后性能比较

由图4可以看出，对于不相交多径路由，虽然使用网络编码会带来一定的冗余，但是成功交付率的提升幅度更大，因此标准化冗余度比未使用网络编码模型有大幅度降低；而对于相交多径路由，由于网络成功交付率在使用了网络编码后提升幅度较小，不能抵掉数据冗余度增加的幅度，因此使用网络编码后标准化冗余度略微变大。

通过上面分析计算，可以发现，网络编码技术在多径传感器网络中能获得较好的效果，在保证系统冗余度偏低的同时提高了网络了成功交付率。

2.2 两种基于网络编码技术多路径模型比较

在跳数分别为2、5、10、20、40、60时，两种模型成功交付率如图5所示，可以看出：基于网络编码的相交多径路由 （NC－BMR）受簇数影响较小，当跳数大于5时成功交付率基本不再发生变化；而基于网络编码的不相交多径路由 （NC－DMR）模型随跳数变化较大并且随着跳数增加而降低；当跳数较小时NC－DMR模型成功交付率要比NC－BMR络模型高，随着跳数增加，NC－DMR模型成功交付率逐渐下降，在跳数大于40后，成功交付率要比NCBMR模型低；跳数分别为10、20、40、60时，其变化基本与成功交付率一致。

当层数为5，簇中节点个数分别为2、3、5、8时，计算分析结果如图6所示，可以看出：随着节点增多，两种模型的成功交付率都随之提高，且BMR模型提高的幅度要比NC－DMR模型大。当节点较少时，相交网络编码模型成功交付率比不相交模型的低，随着节点个数变多，相交网络编码模型成功交付率逐渐超过不相交网络编码模型。

由图6可知，NC－BMR模型随着簇中节点个数的增加成功交付率很稳定，标准化冗余度逐渐变得稳定，但是误码率较低的时候标准化冗余度随着节点个数变大而变高，主要是因为节点增多后，路径增多，冗余增加；而NC－DMR模型由于采用了分包传输，虽然路径增多，但是每条路径上传输的数据减少，因此标准化冗余度随节点个数变化不大。

通过本节分析可以看出，两种基于网络编码的多路径传感器网络适用的网络不同：NC－DMR模型适用于网络规模较小的网络 （簇数较小，簇中的节点较少），而NC－BMR模型则适用于网络规模较大的网络，且对正确交付率和标准化冗余度的影响基本保持一致。

在实际应用中，可以根据网络规模来选择不同的模型，使得网络达到最优。只把网络的成功交付率作为选择路由的评判标准，便可以计算两种模型的正确交付率，选择成功交付率高的路由模型来组建网络。

3 仿真实验

为了验证理论分析的正确性，本文使用omnet＋＋仿真工具对使用网络编码后的不相交多路径传感器网络模型和相交多路径传感器网络模型进行了仿真实验。为了跟理论分析计算结果进行比较，仿真参数与2.1节中的参数一致，仿真结果如图7所示，从图7可以看出，仿真实验结果和理论计算结果基本吻合。在仿真的过程中数据包添加了数据包头，因此性能比理论略为降低。

4 结束语

本文将网络编码应用到传感器网络多径路由中，通过在源节点和中继节点使用随机网络编码，在接收节点进行解码，可以在部分报文丢失和顺序变化的情况下恢复出源数据包，使网络可靠性得到提高。通过仿真计算证明，使用网络编码后，多径路由的成功交付率和标准化冗余度都得到了很好的改善，提高了传感器网络的整体性能。通过对两种基于网络编码模型的性能比较，NC－DMR模型适用于网络规模较小的网络，而NC－BMR模型则适用于网络规模较大的网络。下一步工作计划是在移动传感器网络中，结合动态网络编码对多径路由协议进行更加深入的研究。

［1］Mahesh K，Marina，Samir R Das.Ad HoC on－demand multipath distance vector routing：research articles ［J］.Wireless Communications ＆ Mobile Computing，2006，6 （7）：969－988.

［2］Reddeppa Reddy L，Raghavan PS V.SMORT：Scalable multipath on－demand routing for mobile Ad HoC networks ［J］.Ad HoC Networks，2007，5 （2）：162－188.

［3］Ammar Zahary，Aladdin Ayesh.An analytical review for multipath routing in mobile Ad HoC networks ［J］.International Journal of Ad HoC and Ubiquitous Computing，2010，5 （2）：69－85.

［4］Eliana Stavrou，Andreas Pitsillides.A survey on secure multipath routing protocols in WSNs ［J］.Computer Networks the International Journal of Computer and Telecommunications Networking，2010，54 （13）：2215－2238.

［5］Mohammed Tarique，Kemal E Tepe，Sasan Adibi，et al.Review survey of multipath routing protocols for mobile Ad HoC networks ［J］.Journal of Network and Computer Applications，2009，32 （6）：1125－1143.

［6］WANG Chihchun.Pruning network coding traffic by network coding：a new class of max－flow algorithms ［J］.IEEE Transactions on Information Theory，2010，56 （4）：1909－1929.

［7］Parimal Parag，Chamberland Jean Francois.Queueing analysis of a butterfly network for comparing network coding to classical routing ［J］.IEEE Transactions on Information Theory，2010，56 （4）：1890－1908.

［8］Makesh Pravin Wilson，Krishna Narayanan，Henry D Pfister，et al.Joint physical layer coding and network coding for bidirectional relaying ［J］.IEEE Transactions on Information Theory，2010，56 （11）：5641－5654.

［9］Emina Soljanin，Piyush Gupta，Gerhard Kramer.Network coding for efficient network multicast ［J］.Bell Labs Technical Journal，2009，14 （3）：157－166.

［10］YANG Yuwang，ZHONG Chunshan，SUN Yamin，et al.Network coding based reliable disjoint and braided multipath routing for sensor networks ［J］.Journal of Network and Computer Applications，2010，33 （4）：422－432.

［11］GUO Zheng，WANG Bing，XIE Peng，et al.Efficient error recovery with network coding in underwater sensor networks［J］.Ad HoC Networks，2009，7 （4）：791－802.

［12］Fragouli C， Widmer J，LE Boudec J Y.Efficient broadcasting using network coding ［J］.IEEE／ACM Transactions on Networking，2008，16 （2）：450－463.

［13］YANG Yuwang，GU Li，JU Yutao，et al.Reliable braided multipath routing with network coding for underwater sensor networks［J］.China Ocean Engineering，2010，24 （3）：565－574.

［14］YU Jiming，LU Xianling，YANG Yuwang，et al.Overview of multipath routing protocols in wireless sensor networks［J］.Application Research of Computers，2007，24 （6）：1－3（in Chinese）.［于继明，卢先领，杨余旺，等.无线传感器网络多路径路由协议研究进展 ［J］.计算机应用研究，2007，24 （6）：1－3.］

［15］LU Liping，HUANG Fei，ZHANG Hong，et al.Energy analysis of network coding based multipath routing model for sensor networks ［J］.Journal of Nanjing University of Science and Technology，2010，34 （4）：436－440 （in Chinese）.［卢莉萍，黄飞，张宏，等.基于网络编码的传感器网络多径路由模型能量分析 ［J］.南京理工大学学报，2010，34 （4）：436－440.］