支持网络编码的认知无线自组网拓扑控制算法

刘军，孙茜，王英梅，叶宁，沙明博

（1.东北大学 信息科学与工程学院，辽宁 沈阳 110819；2.北方交大计算所，北京 100029；3.奥维通信股份有限公司，辽宁 沈阳110179）

1 引言

Ad hoc网络[1]是由一组具有无线收发装置的移动终端组成的多跳临时性自治系统。该网络具有无中心和自组织性、节点功能不同、传输带宽受限、拓扑动态变化等特点。近年来，随着认知网络[2,3]的迅速发展，很多研究者将网络认知技术融入无线自组网中，使其可以根据条件变化和发生的事件（如端到端的业务量）按照推理和先验知识进行自适应，从而实现对拓扑结构的自管理、自优化、自监控、自修理、自保护和自治愈等。

随着无线通信技术的日益发展，认知无线自组网中的业务逐渐增多，有限的带宽成为限制其通信的主要因素。Ahlswede于2000年提出了网络编码技术[4]，其核心思想是节点将来自不同链路的数据分组进行编码组合，在实现路由功能的同时实现编码功能。网络编码技术[5,6]可以提高网络吞吐量，增加多播容量，节省节点能耗，增加网络安全性。因此，网络编码技术可以解决网络中带宽受限的问题，提高无线资源复用率。

由于网络编码是一种新兴的技术，目前绝大多数拓扑控制算法[7,8]都不能支持网络编码的应用。直到2007年，Chi等人针对有线网络提出一种支持网络编码的多播网络拓扑构建方案[9]。论文中将该问题作为非线性规划问题，证明其是NP问题，提出了2个启发式算法LDE(link deletion and exchange)和LAE(link addition and exchange)。在2011年，Li在其基础上，将该问题制定为特殊的K连通问题，利用遗传算法提出一种支持网络编码的拓扑设计方案[10]，但是，其优化目标较为简单，需要更加深入的研究。因此，构建支持网络编码的拓扑控制算法仍然具有广阔的研究空间。

2 支持网络编码的无线自组网拓扑控制算法

网络编码能够顺利进行的前提条件之一是网络拓扑结构存在冗余性，Ahlswede所用的著名蝶形网络很好地说明了这个问题。针对每个多播业务，若源节点到每个目的节点都存在K条边分离路径，那么采用网络编码技术可以实现多播传输的极限传输速率。如图1所示的2冗余网络（源节点到每个目的节点都存在2条边分离路径），s是源节点，t1、t2、t3是目的节点，a和b是要传输的数据分组，链路具有单位带宽。若源节点s对数据分组a和b进行网络编码后再传输，在链路s-u2、u2-t1、u2-t3上可以实现传输速率2bit/s。

基于以上思想，为采用网络编码技术解决无线自组网中带宽受限的问题，提出了支持网络编码的拓扑控制算法(TCBNC, topology control algorithm backing for network coding)。算法主要分为3个阶段：初始拓扑构建、拓扑优化和拓扑恢复。

图1 2冗余网络

2.1 初始拓扑构建

无线自组网中的通信类型多种多样，在拓扑构建过程中，需要在面向业务的框架下设计满足多业务需求的网络拓扑，适应其多元化的特点。针对网络中的单播业务，利用最短路径算法选择源节点到目的节点的最短路径，构建网络拓扑；针对网络中的多播业务，利用基于网络编码的最短路径算法选择源节点到每个目的节点的K（K值不同，最大传输速率不同）条边分离路径，构建K冗余网络。

针对无线自组网中的多播业务（假设都为单源多播业务），如图2所示，设K=2，源节点为s，目的节点集为D，其余为中间节点集M。基于网络编码的最短路径算法步骤如下。

图2 基于网络编码的最短路径算法

Step1在初始拓扑图G（如图2(a)）中，使用最短路径算法搜索源节点s到每个中间节点的最短路径，得到最短路拓扑图G′。如图2(b)所示，源节点到中间节点的最短路径分别为sm1、sm2、sm3、sm2m4、sm5。目的节点的输入链路为m1d1、m3d1、m4d1、m3d2、m4d2、m5d2、m4d3、m5d3。

定义1（最短路拓扑图）：在单源多播网络初始拓扑图G中，s为源节点，D为目的节点集，采用最短路径算法搜索源节点到每个中间节点的最短路径，再加上G中所有目的节点的输入链路构成的拓扑为最短路拓扑图G′。

Step 2计算最短路拓扑图G′中源节点s到每个目的节点di（di∈D，i=1,2,···,|D|）的边分离路径数及最小值m。在图2(b)中，计算得m=2。

定义2（边分离路径）：由目的节点的输入链路及输入链路另一端点到源节点的最短路径构成的彼此之间没有重合链路的路径。在图2(b)中，对于目的节点d1，边分离路径为sm1d1、sm3d1、sm2m4d1。

Step 3如果K≤m，转到Step4；否则，转到Step5。

Step 4在最短路拓扑图G′中，对每个目的节点重复采用最短路算法，搜索从源节点s到每个目的节点di的K条最短边分离路径，构建拓扑图G0，如图2(c)所示，可以找到源节点到每个目的节点的2条边分离路径，算法结束。

Step 5在最短路拓扑图G′中，对每个目的节点重复采用最短路算法，搜索从源节点s到每个目的节点di的m条最短边分离路径。

Step 6对于每个目的节点di，将Step5中搜索到的m条最短边分离路径中的链路在初始拓扑图G中删除得新初始拓扑图G′′，在G′′中重复使用以上算法，搜索源节点s到每个目的节点di的K-m条最短边分离路径，算法结束。

综上所述，利用不同的算法可以为不同的业务选择合适的路径或路径簇，构建初始拓扑图G0。不同路径或路径簇之间可能存在重合链路，增加了网络编码的应用机会。如果在重合链路的端节点采用网络编码技术，可以提高网络吞吐量。注意，算法中的“路径”可能代表时延、带宽、能耗等。

2.2 拓扑优化

在初始拓扑构建阶段，构建的拓扑结构具有很大的冗余性。因此，需要在保证网络编码应用的前提下，对拓扑结构进行优化，节省网络能量消耗。如图3(a)所示的拓扑图G0，K=2，网络中包括多播业务Q1（源节点s1，目的节点d11、d12、d13，边分离路径簇为s1m1d11、s1m3d11、s1m3d12、s1m2m4d12、s1m2m4d13、s1s3d21d13）、Q2（源节点s2，目的节点d21、d22，边分离路径簇为s2d21、s2s3d21、s2m2m4d22、s2s3d22）和单播业务 Q3（源节点s3、目的节点d3、最短路径为s3d3）。拓扑优化阶段的步骤如下。

图3 拓扑优化

1) 构建临时拓扑

在拓扑图G0中，选择效率指标最大的链路lmax。从 G0中删除链路lmax，获得临时拓扑图 GT，如图3(b)所示。

定义3 (效率指标)：链路上单位流量的能量消耗。

2) 探测临时拓扑图

①探测临时拓扑图GT中的多播业务是否满足K冗余。若满足，转到②；否则，说明链路lmax不能被删除，在剩余网络拓扑（不包括链路lmax）中重复1)。从图3(b)可以看出，GT满足2冗余条件。

②为链路lmax上的业务重新选择合适的路径，判断网络总能耗是否减小。若减小，将临时拓扑图 GT作为新初始拓扑图 G0；否则，说明链路lmax不能被删除，在剩余网络拓扑中重复1）。在图3中，链路lmax被删除后，其上的单播业务Q3可以选择新的路径s3d21d3，假设计算后，网络的总能耗减小，因此，将临时拓扑图GT作为新初始拓扑图G0。

上面的过程重复进行，直到拓扑图 G0中不存在能被删除的链路，算法结束。

2.3 拓扑恢复

Ad hoc网络中存在一些拓扑关键点，一旦网络认知到某个关键点发生故障或受到安全威胁，与关键点相连的链路会失效，网络很容易被分割成不连通的子网。为了保证网络可靠、安全运行，提出基于关键点失效的拓扑恢复算法，主要思想是采用与失效链路不在同一路径簇中且开销最小的链路恢复网络的连通性，以保证源节点到每个目的节点间的路径是边分离的，继续支持网络编码的应用。

定义4(关键点)：网络中某个节点失效可能导致网络被分割成多个部分，这样的节点称为网络拓扑关键点，如图4(a)所示，节点a是关键点。

以图 4为例说明基于关键点失效的拓扑恢复算法。

1) 收集局部网络拓扑信息

收集关键点a周围的两跳网络拓扑信息，将属于同一路径簇中的链路划为一组，得到3个不同的链路组L1、L2、L3，如图4(a)所示。

2) 恢复链路组的连通性

随机选取链路组L1，当关键点a失效时，路径b1ab6的连通性遭到破坏，将链路组L1中的链路开销置为无穷大，利用最短路径算法搜索节点b1到b6的新路径b1b4b3b6，添加到局部网络中，如图 4(b)所示。然后，探测此时L2中路径连通性是否遭到破坏，从图4(b)中看出，可以找到新路径b4b1b2b5，连通性不再受影响；否则，采用最短路径算法恢复连通性。对于剩余链路组重复使用以上算法。注意，链路组L3的连通性暂时不能恢复。

3) 恢复局部网络连通性

计算此时关键点a失效时局部网络中簇的个数N。若N不为1，添加能使簇个数减小的最小开销链路li（i=1，2，3，···），直到N=1，如图 4(c)中链路l1；否则，算法结束。网络进行拓扑恢复后如图4(c)所示。

2.4 算法支持网络编码的实例

以拓扑图3（b）中多播业务Q1为例，说明网络编码在拓扑结构中的具体体现。设源节点向目的节点发送信息a、b，目的节点d11的边分离路径簇为s1m1d11、s1m3d11，目的节点d12的边分离路径簇为s1m3d12、s1m2m4d12，这 2个路径簇构成了网络编码的典型应用环境——蝶形网络。在源节点处对a、b进行网络编码，将编码后的信息在重合链路s1m3、m3d11、m3d12上传输，在其他链路上传输a或b，可保证目的节点d11、d12成功解码出信息a、b。同样方法，可保证目的节点d13成功收到a、b。不论编码方法如何，构建的拓扑结构都能够支持网络编码的应用，并确保成功解码。

3 仿真分析

3.1 有效性

采用NS2网络模拟软件进行测试，设置网络中同时存在单播和多播业务，对比在TCBNC和基于多播树的拓扑控制算法(TCBMT，topology control algorithm based on multicast tree)的控制下，网络分组投递率、吞吐量、节点平均能耗随信宿节点数增加时的变化情况，仿真参数如表1所示。

图4 基于关键点失效的拓扑恢复算法

表1 仿真参数

定义5(网络吞吐量)：指一组特定数据在特定时间段经过特定路径所传输的信息量的实际测量值。

定义6(节点平均能耗)：指网络中每个节点在运行过程中所消耗的能量的平均值。在计算过程中，考虑了网络运行过程中影响节点能量的所有因素，其计算公式为

从图5～图7可以看出，TCBNC能够提高网络的分组投递率和网络吞吐量，降低网络的节点平均能耗。这是因为TCBNC能够构建出支持网络编码的拓扑结构，增加了节点进行网络编码的机会，因此提高了网络分组投递率和吞吐量，节省了节点平均能耗。随着网络中信宿节点数的增加，TCBNC控制的网络中更多的节点参与网络编码，增大编码机会的同时提高了解码成功概率，大量数据分组能够成功到达目的节点，网络的分组投递率几乎不变，吞吐量逐渐增大，节点平均能耗逐渐增大；而TCBMT控制的网络中由于数据分组的逐渐增多，网络阻塞、数据分组丢失和重传现象十分严重，网络性能逐渐下降。

图5 分组投递率随信宿节点数变化的对比

图6 网络吞吐量随信宿节点数变化的对比

图7 节点平均能耗随信宿节点数变化的对比

3.2 抗毁性

仿真环境与探测有效性时一致，信宿节点数设为10个。对比在TCBNC拓扑控制前后，网络性能指标随失效关键点数增加时的变化情况。

图8 分组投递率随失效关键点数变化的对比

从图8和图9可以看出，随着网络中失效关键点数的增加，支持网络编码的拓扑控制算法能够显著提高网络的分组投递率和吞吐量，改善网络的性能。一方面，TCBNC通过建立新链路，保证了网络的连通性，数据分组能够顺利到达目的节点；另一方面，修复后的网络拓扑结构能够继续支持网络编码的应用，减少了数据分组的传输次数，提高网络吞吐量。因此，TCBNC使网络性能得到了有效的恢复，增强了网络的抗毁性。

图9 网络吞吐量随失效关键点数变化的对比

4 复杂度分析

TCBNC的复杂度小于对比TCBMT的复杂度，主要体现在多播业务的拓扑构建过程中利用了最短路网络。图 10所示为初始网络拓扑图，源节点为s，目的节点为d，K=2，利用TCBMT搜索两条最短路径需要的计算次数为 2×(15+14+···+2)= 238；利用 TCBNC构建最短路网络的计算次数为14+13+···+2=104，如图 11 所示，在其基础上搜索一条最短路径的计算次数为 15，总计算次数为104+2×15=134，节约了 43.7%的计算量。并且，随着目的节点数、K值的增加，算法具有更低的复杂度。

图10 初始网络拓扑图

图11 最短路网络拓扑图

5 结束语

本文提出一种支持网络编码的认知无线自组网拓扑控制算法 TCBNC，针对不同的业务类型采用不同算法构建支持网络编码的初始拓扑图，然后通过逐个删除冗余链路进行拓扑优化，最后提出解决关键点失效问题的拓扑恢复算法。算法支持网络编码的应用，增强了通信的有效性和抗毁性。另外，算法复杂度不大，在节点移动或信道环境变化时仍能适用。在未来的工作中，将考虑链路失效的情况，重构支持网络编码的拓扑。

[1] DE MORAIS CORDEIRO C, GOSSAIN H, AGRAWAL D P.Multicast over wireless mobile ad hoc network： present and future directions[J].IEEE Communications Society, 2003, 17(1)： 52-59.

[2] RABBACHIN A, QUEK T Q S, HYUNDONG S.Cognitive network interference[J].IEEE Journal on Communications, 2011, 29(2)：480-493.

[3] WANG Z D, WANG H Q, FENG G S.Cognitive networks and its layered cognitive architecture[A].2010 Fifth International Conference on Internet Computing for Science and Engineering(ICICSE)[C].Heilongjiang, China, 2012.145-148.

[4] LI B C, NIU D.Random network coding in peer-to-peer petworks：from theory to practice[J].Proceedings of the IEEE, 2010, 99(3)：513-523.

[5] AHN M H, KIM Y Y.Network coding-based multicast scheduling for throughput enhancement in wireless ad hoc network[A].2011 International Conference on Information Networking[C].Barcelona, Spain,2011.188-193.

[6] 胡金秀.多播网络编码算法研究[D].西安： 西安电子科技大学,2010.HU J X.Study on Multicast Network Coding Algorithm[D].Xian： Xidian University, 2010.

[7] ZHANG T, YANG K, CHEN H H.Topology control for service-oriented wireless mesh networks[J].IEEE Wireless Communications, 2009, 16(4)： 64-71.

[8] YADU K K, KAKDE O G.Optimization based topology control for wireless ad hoc networks to meet QoS requirements[A].2010 29th IEEE Symposium on Reliable Distributed System[C].New Delhi, India, 2010.30-36.

[9] CHI K K, JIANG X H, HORIGUCHI S.Topology design of network-noding-based multicast networks[J].IEEE Transactions on Parallel and Distributed Systems, 2008, 19(5)： 627-640.

[10] LI J K, PAN Y.Network coding driented topology design based on parallel genetic algorithm[A].2011 Fourth International Joint Conference on Computational Sciences and Optimization[C].Yunnan, China,2011.838-841.