一种基于网络编码的组播共享树算法∗

梁建华，张振宇，杨文忠

(1.新疆大学软件学院，新疆乌鲁木齐830008;2.新疆大学信息科学与工程学院，新疆乌鲁木齐830046)

0 引言

无线传感器网络是由部署在监测区域内大量廉价的微型传感器节点通过无线通信形成一个多跳的相互协助工作的分布式自组织网络，节点所获得的信息通过中间节点整合发送给数据接收中心[1]．网络的生存时间是无线传感器网络的一个重要性能指标，因此降低网络消耗是关键性的性能需求．此外，无线带宽利用、均衡网络负载和服务质量等方面逐渐成为无线传感器网络研究的重点．

组播[2]是一种允许一个或者多个发送节点发送单一的数据包到多个接收节点的技术．由于发送节点不必向每一个接收节点发送数据，从而减少了数据的复制和传输，在能量节约、带宽利用方面提高了网络性能．组播路由根据具体的应用场景和不同的路由思想等可分3类：基于拓扑结构的组播路由[3−6]、基于空间地理位置的组播路由[7−9]和基于节能的组播路由[10−12]．基于拓扑结构的组播路由将网络中的节点根据不同的启发式算法，建立满足需求的steiner树和分层的树型结构．数据从源节点沿着组播树中的最短路径发送到网络中的其他节点．虽然根据组播树中的最优路径可以把信息快速准确的发送给网络中的节点，但是维护组播树和节点的状态需要消耗大量的能量．基于空间地理位置的组播路由算法中，网络中的每一个节点不必知道全局的拓扑结构，只要知道组播节点的位置和自己当前所在的位置，利用位置算法计算离组播区域更近的下一跳节点，虽然减少了路由的开销，但降低了网络带宽利用率，增加了网络传输时延．基于节能的组播路由协议节能效果较好，旨在考虑传感器节点的能量消耗，但较少考虑网络的吞吐量、带宽利用和可靠性．由于地理环境和屏蔽效应，链路的质量通常比较低，进而导致网络资源消耗过快和较低的吞吐量．

为了提高网络能耗效率、带宽利用率和可靠性，本文提出了一种基于网络编码的组播算法（MABNC），该算法在组播中建了两条冗余路径．利用网络编码，链路输入端将数据编码整合，从而在链路输出端得到多条数据流，提高了带宽利用率，有效减少了网络资源消耗和网络时延．

1 网络编码

网络编码[13]是一种融合编码和路由的信息交换技术，极大地提高网络的吞吐量和可靠性．在传统存储转发的路由方法基础上，通过允许对接收的多个数据包进行编码信息融合，增加单次传输的信息量，提高网络整体性能．

1.1 编码

源节点将数据包分为M1，M2···Mn块，线性网络编码将数据块赋予系数gi，在有限域里每个数据包乘以系数得到编码后的数据包，其中g=(gi···gn)是编码向量，X是数据矢量，编码向量和数据矢量必须与编码数据包发送到下一个节点．

1.2 解码

当目的节点完全接收到(g1,X1),···,(gm,Xm)以后，根据公式1只需要解码一组方程来恢复原始数据包M1,···,Mn．其过程是一个解逆矩阵．

其中，如果m≥n，编码向量g就是线性独立，因此目的节点根据线性无关可以恢复n个原始数据(M1,···,Mn)．由于有些组合线性也许不是线性无关，则条件是不够的．选择线性相关组合的概率取决于网络规模的大小．在Fragouli[14]的实验仿真展示了甚至是较小的场地线性相关组合的概率可以被忽略．因此一个节点收到足够的数据向量可以很容易完成解码恢复原来的数据包．

2 基于网络编码的组播共享树算法

2.1 冗余路径

基于树型结构的组播路由，其中目的节点到源节点只有一条传输路径．基于网络编码的共享树路由在组播中建了两条冗余路径，多个目的节点共享一个源节点．如图1所示，目标节点T1到源节点的两条不相交的路径（黑色的链接是T1的第一条道路，左边第二个路径是白色）．没有网络编码，两个目标节点不能同时得到信息流a和b．处在“瓶颈”链路的中间节点U3上应用网络编码，目标节点T1可以从源节点接收a和（a+b）信息流．同样，目标节点T2可以接收b和（a+b）信息流．节点T1和T2通过简单的模加法运算可以恢复原始数据a和b．

2.2 组播路径

组播路径的建立过程如图2所示．为便于解释，只取一个源节点的情况．开始只有一个源节点，没有目的节点，如图2（a）所示．如果一个目的节点要加入到组播，源节点将要建立两条不相交的路径，一条路径的带宽最大，一条路径的时延最小．如果一个目的节点加入到组播，那么这条路径成本和延迟是1/(1+λk)，其中λ是一个变量，k是不属于组播里的t节点的邻居节点数量．如图2（b）所示要求最短延迟，对于目标节点U10，到源节点有两条路径r1：S-U1-U5-U10和r2：S-U2-U6-U10．目的节点不仅可以与中间节点进行通信，还可以与其他目的节点进行通信．如图2（c）所示，U11则可以把U10当作中间节点，经过U10到源节点建立一条路径．当所有目的节点到源节点都建立了两条冗余路径，则组播路径建立完成．图2（d）展示了在建立组播路径时如何实现网络编码．由于目的节点到源节点有几条不同的路径，所以目的节点可以共享路径，称为瓶颈路径，例如（S,U1）和（U6，U10），并通过网络编码处理．

图1 网络编码冗余路径

图2 组播路径

2.3 基于网络编码的组播共享树算法

基于网络编码的组播共享树算法首先选取源节点作为树的根节点，建立组播路径到共享树里，然后从目的节点搜索组播路径添加到共享树．基于网络编码的组播共享树算法有多个节点为编码节点，其主要建立步骤：1）根据编码节点算法选取编码节点；2）把有编码节点的组播路径添加到共享树中；3）在组播路径之上建立源节点到目的节点的冗余路径，经过编码节点传输数据．

2.3.1 编码节点

如图3所示，s1和s2是源节点，d1，d2和d3是目标节点集合，其他节点是具有编码功能的中间节点．边上的值表示每条链路的代价，那么根据上面的算法Smin(A)=2，Smin(B)=3，Smin(C)=4，Smin(D)=3···，Smin(A)最小，因此选择A节点作为编码节点．A节点接收来至所有的源节点的数据并且编码．

2.3.2 共享组播树

根据编码节点的选择算法，基于网络编码的组播共享树的建立过程如下：

1）首先从源节点到中间节点建立组播路径，然后将目的节点加入到组播路径中；

2）利用编码节点选择策略在组播路径中选择编码节点；

3）在网络中计算编码节点到每个目的节点没有共享的路径数量，如果大于2，则反复用Dijkstra算法在部分网络或者整个网络中筛选出2条从编码节点到每个目的节点的最短非共享路径；

4）重复步骤2直到每个目的节点找到两条冗余路径，组成组播共享树；

5）平均分配数据到编码节点，再把编码数据传输到目的节点．

如图4所示：编码节点A作为源节点，A到其他中间节点可以获得最短路径，例如A-B，A-C，A-H，AB-D，A-C-F，A-H-I，A-D-E和A-C-F-G．然后通过Dijkstra算法获取各接收节点的非共享路径．节点D1的两条非共享路径是A-B-D-D1和A-B-E-D1，节点D2的两条非共享路径是A-B-D2和A-C-D2，节点D3的两条非共享路径是A-H-G-D3和A-C-F-D3，最后将这些路径添加到共享树．

图3 局部网络拓扑

图4 组播共享树

3 仿真结果分析

为验证算法的有效性，将MABNC算法与基于树组播算法（Multicast based tree）[6]进行了比较．仿真利用了NS平台，假设网络中有500个节点随机分布在一个100m*100m的矩形监测区域内，其中50个接收节点，汇聚节点位于网络的中心位置．节点通信半径R=20m，节点初始能量ε=200J，传输消息能耗为0.5J/KB，每个数据包大小为512byte．仿真时间为240s．仿真中信号碰撞、信号干扰等因素忽略不计．

3.1 平均能耗

根据文献[15]，在传感器网络中能耗体现在数据的传输．每隔10s采集一次数据，开始30s左右构建组播拓扑结构，节点平均能耗有所上升，随后的过程是数据的传输．如图5所示，仿真表明基于网络编码的组播共享树算法初始的能耗开销比基于树的组播算法能耗增加的速率快．然而，在数据传输时，利用网络编码机制有效减少了平均能量消耗．利用网络编码可以减少传输节点，让数据传输更加有效．

图5 节点平均能耗

图6 网络吞吐量

3.2 吞吐量

网络带宽的大小跟目标接收节点的数量有关，仿真中500个节点有50个接收节点，目标接收节点比率10%．图6表明基于网络编码的组播共享树的吞吐量接近组播树的两倍．有向组播网络采用线性网络编码即可达到最大组播速率[16]．网络中数据传输率的提高，在单位时间内网络吞吐量明显增大．与基于树的组播路由算法相比，基于网络编码的组播共享树算法可以达到良好的组播最大流．

3.3 传输时延

如图7所示，由于对比单位为毫秒，基于树的组播路由算法的传输时延比基于网络编码的组播较小，但随着实际的应用时间的延长，基于网络编码的组播共享树路由的优势会增大．由于传感器节点动态的变化，网络拓扑不稳定，路由需要维持和调整树的结构从而影响组播的性能．

4 结束语

针对无线传感器网络资源消耗过快和带宽利用率不足等问题，提出了一种基于网络编码的组播共享树路由算法，利用开销最小链路选择网络编码节点．该算法在组播中建立两条冗余路径，在此基础上在整个网络中，每个目的节点选择两条最优链路传输数据，提高了网络带宽利用率，均衡了链路消耗．实验仿真表明该算法可以提高网络吞吐量，减少了网络资源消耗和传输时延．

图7 网络传输时延

参考文献：

[1]Akyildiz IF,Su W,Sankarasubramaniam Y,et al.Wireless sensor networks:A urvey[J].Computer Networks,2002,38(4):393-422.

[2]田捷.组播路由算法研究[D].武汉:武汉理工大学,2005.

[3]The pvilojanapong N，Tobe Y，Sezaki K．An efficient multicast routing protocol for wireless sensor networks[J]．IEIC Technical Report，2005:419-422.

[4]Sheth A，Shucker B，Han R．VLM2:A very lightweight mobile multicast system for wireless sensor networks[C].IEEE Intl Conf on Wireless Communications and Networking，New Orleans，2003:1936-1941.

[5]Zhang W,Cao G,La Porta T.Dynamic proxy tree-based data dissemination schemes for wireless sensor networks[J].Wireless Networks,2007,13(5):583-595.

[6]Wang Fangfang，Tao Jun，Shao Birui．An energy-balanced multicast routing algorithm in wireless sensor networks[C].Proc of Ninth IEEE International Conference on Grid and Cloud Computing，Nanjing,2010:361-365.

[7]KoY B，Vatda N H．Geocasting in mobile ad hoc networks:Location-based multicast algorithms[C].Proc of the Second IEEE Workshop on Mobile Computer Systems and Applications，Washington:IEEE Computer Society，1999:101-110.

[8]Sanchez A，Ruiz M．Bandwidth-efficient geographic multicast routing protocol for wireless sensor networks[J].IEEE Sensors Journal，2007，7(5):627-636.

[9]Wu Shibo，Selcuk K.GMP:Distributed geographic multicast routing in wireless sensor networks[C].Proc of the 26th IEEE International Conference on Distributed Computing Systems，Lisboa:IEEE,2006:1-9.

[10]Chen C,He Z,Sun H,et al.A grid-based energy efficient routing protocol in Wireless Sensor Networks[C]//Wireless and Pervasive Computing(ISWPC),2013 International Symposium on.IEEE,2013:1-6.

[11]Mammu A S K,Sharma A,Hernandez-Jayo U,et al.A Novel Cluster-Based Energy Efficient Routing in Wireless Sensor Networks[C]//Advanced Information Networking and Applications(AINA),2013 IEEE 27th International Conference on.IEEE,2013:41-47.

[12]Minhas A A,Sattar D,Mustaq K,et al.Energy efficient multicast routing protocols for Wireless Sensor Networks[C]//Sustainable Technologies(WCST),2011 World Congress on.IEEE,2011:178-181.

[13]AHLSWEDE R，CAI N，LI S Y，et al．Network information f l ow[J]．IEEE Transactions on Information Theory，2000，46(4):1204-1216.

[14]Fragouli C,Le Boudec J Y,Widmer J.Network coding:an instant primer[J].ACM SIGCOMM Computer Communication Review,2006,36(1):63-68.

[15]Rex Min,Anantha Chandrakasan.A Framework for Energy-Scalable Communication in High-Density Wireless Networks[C].Proceedings of the 2002 International Symposium on Low Power Electronics and Design,2002:36-41.

[16]Li S Y R,Yeung R W,Cai N.Linear network coding[J].IEEE Trans on Informat ion Theory,2003,49(2):371-381.