战术网络拓扑构建研究范文

战术网络在复杂、恶劣环境下要求网络要具备动态拓扑变化和动态路由功能，以便支持移动用户进行多跳可靠的通信。在战术通信场景中，常用的通信模式是广播和多播消息，比如群组PTT(Push－To－Talk)、公告消息和态势感知信息等。连通支配集(connecteddominatingset，CDS)是一种在战术网络中被利用来构建虚拟骨干子网的有效方法。与簇结构类似，支配集中的节点在路由分发和中继转发中起着重要作用，意味着路由信息的维护在连通支配集中就可以完成。连通支配集在实现MANET的虚拟骨干网络方面有着很多优势［2］:在网络拓扑变化情况下路由过程得到简化、路由表的计算减少，同时分组中继只用在连通支配集内完成，而且可以避免在网络广播时可能产生的网络风暴。在战术网络环境中，很多CDS算法都已经被提出并应用于相关场景。利用冗余传输可以提高分组转发效率，比如多次传送分组或者在CDS中选择更多的中继节点来传输。前者是在很少的时间约束中获得可靠点对点数据传输，而后者则是采用多径策略以满足实时广播/多播业务的需求。考虑到在战术网络中实时广播/多播业务和节点移动导致拓扑变化的情况，利用Yang提出的UCDS(UnifyingConnectedDominatingSet)算法在战术网络环境中来提高分组转发效率，减少节点移动带来的拓扑变化影响。

1相关研究

在最近几年，关于CDS的观点、算法及实验大量涌现。在CDS算法构建拓扑中，CDS的大小、错误容忍度、能量节省和移动管理等方面都有很深入的研究。CDS算法的核心是寻找最小的连通支配集，这个已经被证明是一个NP完全问题，即对于给定问题域的输入规模，目前尚无足够的手段证明该问题能够被判定在多项式时间内求解。CDS算法目前的应用研究主要有:CDS能够创建一个虚拟骨干网络用来实现分组路由和控制。消息能够通过CDS中的虚拟骨干路径来选择从源节点发送到目的节点的最近路由，这种方式可以简称为基于支配集的路由或者基于虚拟骨干的路由。通过CDS来优化路由可以使得在路由信息更新时能够大大的减少信息开销。另外支配集在层级网络中的应用能够减少控制信令的开销。CDS能够提高多播/广播路由的效率。在多播/广播路由中存在一个比较严重的问题就是很多中继的节点不需要用来中继转发信息，即存在冗余节点。这样会导致目的节点收到很多重复的信息，这是广播风暴产生的问题。如果消息能够利用CDS来路由优化，那么绝大多数冗余节点的广播就可以消除。CDS能够改进功率控制，减少能量消耗。在无线网络中每个节点电池能量都是有限的。利用CDS可以确保更多的节点进入休眠模式，只保留中继转发消息的能力。另外CDS能够平衡网络管理的需求以便可以使得在节点中的能量能够相对平衡的消耗。此外，由支配集形成的虚拟骨干能够为多媒体业务在路由选择的时候提供链路信道的质量信息，或者可以当作数据库服务等［23］。

2算法描述

2．1概述UCDS是一个简单而有效的分布、启发式算法，通过其1跳的邻节点信息(比如邻居度数及节点ID)来确定CDS。在每个节点的链路层有一个分布式的状态机，用来定义该节点在拓扑结构的收敛中的作用。在UCDS中，一个图G的连通支配集(CDS)由一组连通节点组成。G图中每个节点要么是CDS的成员，要么就是与某个成员相距1跳。UCDS定义了一组连接节点，其连接不相交集中的支配节点。通过UCDS构建拓扑过程如图1所示:UCDS使用连接集(ConnectingSet，CS)和支配集(DominatingSet，DS)的规则来分别构建CS和DS，然后合并形成一个CDS。利用邻居度数及节点ID来对节点等级进行判定。具体有两个步骤:支配集构造和支配集连通。其中支配集连通中有三个规则:首先使用非CS规则，然后到CS规则，最后才用CS例外规则。

2．2符号说明i，j，k，l，m，n是指网络中的节点标识号;N是指网络中所有的节点标识号集合;DS是指节点i的邻居节点标识号集合;Nj是指节点j的邻居节点标识号集合;Nk是指节点k的邻居节点标识号集合;d是指节点的邻居度数，即节点的邻居节点个数;DS是指支配集;CS是指连通集;CS'是指候选连通集;DSNj是指节点j的DS邻居节点标识号集合;DSNk是指节点k的DS邻居节点标识号集合。

2．3支配集构造支配集构造算法过程如下:算法1:构造支配集(DS)//构建DS规则过程

2．4支配集连通支配集连通的构造算法过程如下:

3算法分析

UCDS算法分析主要包括两方面:一是算法本身性能分析;另一个是与其他相关研究的对比分析。

3．1性能分析UCDS性能分析主要包括计算复杂度和消息复杂度，Δ表示邻居度数。计算复杂度:在算法第一阶段，节点与邻居节点比较支配因子d及节点ID大小的计算复杂度为O(Δ)，主要是循环遍历所有节点对比所需要的计算开销;在算法第二阶段中，非CS规则的计算复杂度为O(Δ2)，CS例外规则的计算复杂度为O(Δ3)，CS规则的计算复杂度为O(Δ3)，主要是循环遍历节点i所有邻居节点的非相交和遍历循环候选CS成员对比支配因子d及节点ID大小所需要的计算开销，即外循环遍历、内循环遍历和非相交计算三个部分。算法的计算复杂度取决于最慢规则的计算复杂度，故UCDS算法的计算复杂度为O(Δ3)。消息复杂度:在整个算法过程中，每个节点均向邻居节点发送邻居列表消息，因此邻居列表信息的共享是其主要的信息开销，为O(Δ)。

3．2对比分析文献［24］提出了一种改进的Wu和Li规则［25］，其CDS的创建是通过采用扩展规则来对比邻居节点的邻居度数和电池能量等级来完成这个过程，具体是采用标记法来选择每个可能的DS和CS成员，然后再剔除无用的成员，而在UCDS中，首先通过DS规则选择准确的DS成员，然后利用CS的两个扩展规则把不是和无用的CS成员排除掉，最后才利用CS规则来选择准确的CS成员，其计算复杂度最高是O(Δ3)，低于文献［24］算法的计算复杂度。文献［26］也是一种改进的Wu和Li规则，其主要是提高在移动环境下利用开启和关闭节点来减少能量消耗的效率，在这个过程中，要利用不同的规则来处理开启和关闭之间的切换、移动管理、更新虚拟骨干，最后更新CDS。而在UCDS中，处理与该文献相同的情况时不再需要定制任何其他规则就能够实现，其实现比较简单。文献［27］描述了一种与UCDS的过程比较类似的算法，其标记阶段与DS规则类似，连接阶段与CS类似，但是其标记阶段的结果还没真正起作用。在该文献中，在标记阶段所构建的DS，其互相之间还不能连接，而UCDS在这个阶段即使用DS规则后所构建的DS已经能够用于寻找最短路由的应用了。在连接阶段，该文献增加了无用节点{5、9、14}，这些无用节点还要增加删减阶段才能去掉;与此相反的是，UCDS在该阶段用CS例外规则就可以排除所有的节点从而获得了最终CDS解{2、4、7、10、11、12}。文献［28］描述了一种使用混合因子(邻居度数和局域协作)的思想来构建CDS，其后扩展为邻居度数、局域协作和节点能量等级。该文献与前面改进的Wu和Li规则不一样的是，混合因子是在排除阶段使用，而改进的Wu和Li则在初始标记阶段就使用。这样会使得在初始阶段就失去使用混合因子来判断的机会，仅仅只是根据网络拓扑而没有考虑其他因子的影响。文献［29］在构建基于MPR(mul-tipointrelaying，多点中继)的CDS时，也只是仅仅使用剩余能量等级因子来决定覆盖的节点数量，而忽略了其他重要因子对CDS节点选择的影响。UCDS采取了灵活的可配置支配因子，在初始的DS规则阶段该方法对于前面的算法来说更为有效，其计算复杂度是，实际情况下，有可能在初始的DS规则阶段就能够选定了所有或者绝大部分的CDS成员，仅仅在DS规则不能满足全连通的要求时才使用计算复杂度更高的CS规则。因此UCDS不仅在求出CDS解的方面比文中所提到的算法更高效，而且在创建CDS时调整最佳的支配因子方面也比其他算法更灵活。文献［30］和［31］提出一种计算复杂度和时间复杂度比较低的算法，其中计算复杂度为O(N)，时间复杂度为O(N2)，但是这两种算法的计算效率是在花费更多的消息复杂度情况下获得，该算法需要的消息有局域邻居节点发现信息和其他拓扑变化时所产生一系列泛洪信息。文献［32］也是采用类似的算法，但在移动应用受到带宽限制，而且算法缺乏健壮性，很难得到推广。在文献［33］中所提出的算法过程与UCDS基本上一样，但是其是集中式，因此也很难在移动战术网络中得到应用。文献［34］对网络中存在两个支配集进行仿真，结果表明，相对于一个支配集来说，存在两个支配集所用到的CDS成员数量并没有增加很多。但是该算法的消息复杂度为，比UCDS的消息复杂度高。在战术网络中，由于有限的带宽，消息复杂度是一个非常重要的因素，消息复杂度越高，其收敛速度越慢。

4拓扑构建实例

基于UCDS算法实现拓扑构建过程实例分析如图3所示:通过图3的实例图展开如下分析:1．利用DS规则选择出DS。首先根据DS规则第一个条件:根据表1自选最大邻居度数，图中节点10确定是DS成员，然后根据DS规则第二个条件:根据表1推选最大邻居度数，图中节点6、7、8、9、11、13、16确定是DS成员，因此，最终的DS成员是6、7、8、9、10、11、13、16，如图3中黑色节点表示。2．利用非CS规则排除非CS成员节点。根据非CS规则，从剩余的节点中选择出非CS成员:5，在图3中用白色节点表示。3．利用CS规则选择出CS。根据CS规则从剩余的节点中选择成员:4和12，因为节点1、2、3、14、15都具有相交的DSN，比如节点1，其DSN(备注:节点中只存储2跳以内的节点信息)有两个{2、3、7}和{7、8、9}，存在相交的节点7，故排除节点1，同理2、3、14、15都是一样。故CS节点为{4、12}。4．利用CS例外规则去掉冗余的CS节点。根据CS例外规则，从上面分析后CS节点中去掉冗余CS成员:4，在图3中用白色节点表示。最后所得的CS成员为{12}。从上面4个规则执行后所得的DS和CS的并集就是UCDS，即{6、7、8、9、10、11、12、13、16}。

5应用分析

5．1路由优化在战术网络中，反应式路由比如AODV等用来发现源节点与目的节点之间的路由路径。通常路由发现过程都是广播一个路由请求分组(routere-quest，RREQ)给邻居节点，接收到该信息的节点继续转发RREQ分组，这个过程持续到RREQ分组到达目的节点为止，然后目的节点把路由中继消息(routereply，RREP)发送至源节点［35］－［36］。这种路由发现过程容易产生广播风暴。在路由发现过程中，可以结合UCDS算法来对路由路径进行优化，简化了路由过程，从而避免广播风暴的问题产生。对于战术网络中任意一对节点，其最短路径之间的中继节点都应包含在UCDS中。这样将分组转发任务限定于连通支配集内部，当CDS节点接收到一个RREQ分组时广播该数据包，非CDS节点则只用接收该分组而不用转发该分组。这样RREQ分组传输的数次会大大的减少，提高分组转发效率，从而避免了网络的拥塞。另外，在转发路由路径选择时，其所耗费的时间更加少。具体的路由优化实例如图4从图4可看出，利用UCDS算法时最多需要8次分组转发传送，而普通广播则至少需要13次才能够完成全网广播过程。

5．2节点移动自适应战术网络的拓扑因为节点的持续移动而不断变化。在战术网络中，UCDS算法支持低速率下节点移动自适应，具体从下面三个不同的移动实例，以图3作为图例进行说明。(1)非CDS节点离开网络如果一个非CDS节点离开网络，UCDS算法将会检查是否因为网络拓扑的改变而导致CDS节点成员改变。在图3中，除了节点3、4、5、14、15离开网络不会导致CDS成员发生改变之外，其他非CDS节点离开都会使得CDS成员发生改变，原因是由于节点4和5共同推举了DS节点11，故节点4和5离开网络均不会造成CDS成员改变;而节点3、14和15的离开导致了节点6、13和16变成了CS节点，故节点3、14和15离开网络不会造成CDS成员改变。根据UCDS算法中DS规则可知，非CDS节点1、2的离开都会造成CDS成员改变，具体原因是非CDS节点推荐其邻居节点作为DS节点，如果该节点离开网络，那么所推荐的DS节点将会失效，具体如表2所。(2)CDS节点离开网络如果一个CDS节点离开网络，UCDS算法将会检查是否因为网络拓扑的改变而导致CDS节点成员改变。如图3所示，节点10离开不会增加新的CDS成员，其他节点的离开都会增加新的CDS成员，而节点7的离开导致CDS成员增加比较多，节点8与9和12与13的离开后其CDS成员一样。具体情况如表3。(3)新节点加入网络新节点加入网络，获取邻居列表信息后，UCDS算法开始对新加入的节点进行分析。利用DS规则，新节点推举其邻居节点中邻居度数最大或者ID最大的节点(邻居度数相同情况下)作为新的DS节点加入到CDS，同时分析其它的DS节点，是否满足DS规则和CS规则，不满足的话则从CDS中剔除并加入到普通子集。具体如图5所示，节点17加入网络后，CDS变化为{2、6、7、8、9、10、11、12、13、16}。

6结语

在战术网络中，节点移动导致了网络拓扑的变化。以UCDS算法为基础，探讨了连通支配集在战术网络中的分布式构建虚拟骨干过程。通过与相关构建虚拟骨干算法进行对比分析，UCDS在计算度复杂度和消息复杂度上都有一定的优势，特别是消息复杂度，其所构建的虚拟骨干拓扑能够在战术网络环境中支持路由优化及低速率下节点移动自适应。下一步工作是在OSPF协议中使用UCDS节点作为中继节点，分析其执行效率，并能够使用在真实的战术网络环境中。

作者：唐龙 王峰 单位：武汉中原电子集团有限公司 总装备部