《战术网络拓扑构建研究（精品推荐）.docx》由会员分享，可在线阅读，更多相关《战术网络拓扑构建研究（精品推荐）.docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、战术网络拓扑构建研究战术网络在复杂、恶劣环境下要求网络要具备动态拓扑变化和动态路由功能，以便支持移动用户进行多跳可靠的通信。在战术通信场景中，常用的通信形式是广播和多播消息，比方群组PTT(PushToTalk)、公告消息和态势感悟信息等。连通支配集(connecteddominatingset，CDS)是一种在战术网络中被利用来构建虚拟骨干子网的有效方法。与簇构造类似，支配集中的节点在路由分发和中继转发中起着重要作用，意味着路由信息的维护在连通支配集中就能够完成。连通支配集在实现MANET的虚拟骨干网络方面有着很多优势2:在网络拓扑变化情况下路由经过得到简化、路由表的计算减少，同时分组中继只
2、用在连通支配集内完成，而且能够避免在网络广播时可能产生的网络风暴。在战术网络环境中，很多CDS算法都已经被提出并应用于相关场景。利用冗余传输能够提高分组转发效率，比方屡次传送分组或者在CDS中选择更多的中继节点来传输。前者是在很少的时间约束中获得可靠点对点数据传输，而后者则是采用多径策略以知足实时广播/多播业务的需求。考虑到在战术网络中实时广播/多播业务和节点移动导致拓扑变化的情况，利用Yang提出的UCDS(UnifyingConnectedDominatingSet)算法在战术网络环境中来提高分组转发效率，减少节点移动带来的拓扑变化影响。1相关研究在近期几年，关于CDS的观点、算法及实验大
3、量涌现。在CDS算法构建拓扑中，CDS的大小、错误容忍度、能量节省和移动管理等方面都有很深化的研究。CDS算法的核心是寻找最小的连通支配集，这个已经被证实是一个NP完全问题，即对于给定问题域的输入规模，目前尚无足够的手段证实该问题能够被断定在多项式时间内求解。CDS算法目前的应用研究主要有:CDS能够创立一个虚拟骨干网络用来实现分组路由和控制。消息能够通过CDS中的虚拟骨干途径来选择从源节点发送到目的节点的近期路由，这种方式能够简称为基于支配集的路由或者基于虚拟骨干的路由。通过CDS来优化路由能够使得在路由信息更新时能够大大的减少信息开销。另外支配集在层级网络中的应用能够减少控制信令的开销。C
4、DS能够提高多播/广播路由的效率。在多播/广播路由中存在一个比拟严重的问题就是很多中继的节点不需要用来中继转发信息，即存在冗余节点。这样会导致目的节点收到很多重复的信息，这是广播风暴产生的问题。假如消息能够利用CDS来路由优化，那么绝大多数冗余节点的广播就能够消除。CDS能够改良功率控制，减少能量消耗。在无线网络中每个节点电池能量都是有限的。利用CDS能够确保更多的节点进入休眠形式，只保留中继转发消息的能力。另外CDS能够平衡网络管理的需求以便能够使得在节点中的能量能够相对平衡的消耗。此外，由支配集构成的虚拟骨干能够为多媒体业务在路由选择的时候提供链路信道的质量信息，或者能够当作数据库服务等2
5、3。2算法描绘21概述UCDS是一个简单而有效的分布、启发式算法，通过其1跳的邻节点信息(比方邻居度数及节点ID)来确定CDS。在每个节点的链路层有一个分布式的状态机，用来定义该节点在拓扑构造的收敛中的作用。在UCDS中，一个图G的连通支配集(CDS)由一组连通节点组成。G图中每个节点要么是CDS的成员，要么就是与某个成员相距1跳。UCDS定义了一组连接节点，其连接不相交集中的支配节点。通过UCDS构建拓扑经过如图1所示:UCDS使用连接集(ConnectingSet，CS)和支配集(DominatingSet，DS)的规则来分别构建CS和DS，然后合并构成一个CDS。利用邻居度数及节点ID来
6、对节点等级进行断定。详细有两个步骤:支配集构造和支配集连通。其中支配集连通中有三个规则:首先使用非CS规则，然后到CS规则，最后才用CS例外规则。22符号讲明i，j，k，l，m，n是指网络中的节点标识号;N是指网络中所有的节点标识号集合;DS是指节点i的邻居节点标识号集合;Nj是指节点j的邻居节点标识号集合;Nk是指节点k的邻居节点标识号集合;d是指节点的邻居度数，即节点的邻居节点个数;DS是指支配集;CS是指连通集;CS是指候选连通集;DSNj是指节点j的DS邻居节点标识号集合;DSNk是指节点k的DS邻居节点标识号集合。23支配集构造支配集构造算法经过如下:算法1:构造支配集(DS)/构建
7、DS规则经过24支配集连通支配集连通的构造算法经过如下:3算法分析UCDS算法分析主要包括两方面:一是算法本身性能分析;另一个是与其他相关研究的比照分析。31性能分析UCDS性能分析主要包括计算复杂度和消息复杂度，表示邻居度数。计算复杂度:在算法第一阶段，节点与邻居节点比拟支配因子d及节点ID大小的计算复杂度为O()，主要是循环遍历所有节点比照所需要的计算开销;在算法第二阶段中，非CS规则的计算复杂度为O(2)，CS例外规则的计算复杂度为O(3)，CS规则的计算复杂度为O(3)，主要是循环遍历节点i所有邻居节点的非相交和遍历循环候选CS成员比照支配因子d及节点ID大小所需要的计算开销，即外循环
8、遍历、内循环遍历和非相交计算三个部分。算法的计算复杂度取决于最慢规则的计算复杂度，故UCDS算法的计算复杂度为O(3)。消息复杂度:在整个算法经过中，每个节点均向邻居节点发送邻居列表消息，因而邻居列表信息的分享是其主要的信息开销，为O()。32比照分析文献24提出了一种改良的Wu和Li规则25，其CDS的创立是通过采用扩展规则来比照邻居节点的邻居度数和电池能量等级来完成这个经过，详细是采用标记法来选择每个可能的DS和CS成员，然后再剔除无用的成员，而在UCDS中，首先通过DS规则选择准确的DS成员，然后利用CS的两个扩展规则把不是和无用的CS成员排除掉，最后才利用CS规则来选择准确的CS成员，
9、其计算复杂度最高是O(3)，低于文献24算法的计算复杂度。文献26也是一种改良的Wu和Li规则，其主要是提高在移动环境下利用开启和关闭节点来减少能量消耗的效率，在这个经过中，要利用不同的规则来处理开启和关闭之间的切换、移动管理、更新虚拟骨干，最后更新CDS。而在UCDS中，处理与该文献一样的情况时不再需要定制任何其他规则就能够实现，其实现比拟简单。文献27描绘了一种与UCDS的经过比拟类似的算法，其标记阶段与DS规则类似，连接阶段与CS类似，但是其标记阶段的结果还没真正起作用。在该文献中，在标记阶段所构建的DS，其相互之间还不能连接，而UCDS在这个阶段即便用DS规则后所构建的DS已经能够用于
10、寻找最短路由的应用了。在连接阶段，该文献增加了无用节点5、9、14，这些无用节点还要增加删减阶段才能去掉;与此相反的是，UCDS在该阶段用CS例外规则就能够排除所有的节点进而获得了最终CDS解2、4、7、10、11、12。文献28描绘了一种使用混合因子(邻居度数和局域协作)的思想来构建CDS，其后扩展为邻居度数、局域协作和节点能量等级。该文献与前面改良的Wu和Li规则不一样的是，混合因子是在排除阶段使用，而改良的Wu和Li则在初始标记阶段就使用。这样会使得在初始阶段就失去使用混合因子来判定的时机，仅仅只是根据网络拓扑而没有考虑其他因子的影响。文献29在构建基于MP(mul-tipointrel
11、aying，多点中继)的CDS时，也只是仅仅使用剩余能量等级因子来决定覆盖的节点数量，而忽略了其他重要因子对CDS节点选择的影响。UCDS采取了灵敏的可配置支配因子，在初始的DS规则阶段该方法对于前面的算法来讲更为有效，其计算复杂度是，实际情况下，有可能在初始的DS规则阶段就能够选定了所有或者绝大部分的CDS成员，仅仅在DS规则不能知足全连通的要求时才使用计算复杂度更高的CS规则。因而UCDS不仅在求出CDS解的方面比文中所提到的算法更高效，而且在创立CDS时调整最佳的支配因子方面也比其他算法更灵敏。文献30和31提出一种计算复杂度和时间复杂度比拟低的算法，其中计算复杂度为O(N)，时间复杂度
12、为O(N2)，但是这两种算法的计算效率是在花费更多的消息复杂度情况下获得，该算法需要的消息有局域邻居节点发现信息和其他拓扑变化时所产生一系列泛洪信息。文献32也是采用类似的算法，但在移动应用遭到带宽限制，而且算法缺乏强健性，很难得到推广。在文献33中所提出的算法经过与UCDS基本上一样，但是其是集中式，因而也很难在移动战术网络中得到应用。文献34对网络中存在两个支配集进行仿真，结果表明，相对于一个支配集来讲，存在两个支配集所用到的CDS成员数量并没有增加很多。但是该算法的消息复杂度为，比UCDS的消息复杂度高。在战术网络中，由于有限的带宽，消息复杂度是一个非常重要的因素，消息复杂度越高，其收敛
13、速度越慢。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，由于节点
14、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应用分析51路由优化在战术网络中，反响式路由比方AODV等用来发现源节点与目的节点之间的路由途径。通常路由发现经过都是广播一个
15、路由请求分组(routere-quest，EQ)给邻居节点，接收到该信息的节点继续转发EQ分组，这个经过持续到EQ分组到达目的节点为止，然后目的节点把路由中继消息(routereply，EP)发送至源节点3536。这种路由发现经过容易产生广播风暴。在路由发现经过中，能够结合UCDS算法来对路由途径进行优化，简化了路由经过，进而避免广播风暴的问题产生。对于战术网络中任意一对节点，其最短途径之间的中继节点都应包含在UCDS中。这样将分组转发任务限定于连通支配集内部，当CDS节点接收到一个EQ分组时广播该数据包，非CDS节点则只用接收该分组而不用转发该分组。这样EQ分组传输的数次会大大的减少，提高分
16、组转发效率，进而避免了网络的拥塞。另外，在转发路由途径选择时，其所消耗的时间愈加少。详细的路由优化实例如图4从图4可看出，利用UCDS算法时最多需要8次分组转发传送，而普通广播则至少需要13次才能够完成全网广播经过。52节点移动自适应战术网络的拓扑由于节点的持续移动而不断变化。在战术网络中，UCDS算法支持低速率下节点移动自适应，详细从下面三个不同的移动实例，以图3作为图例进行讲明。(1)非CDS节点离开网络假如一个非CDS节点离开网络，UCDS算法将会检查能否由于网络拓扑的改变而导致CDS节点成员改变。在图3中，除了节点3、4、5、14、15离开网络不会导致CDS成员发生改变之外，其他非CD
17、S节点离开都会使得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离开不会增加新的CD
18、S成员，其他节点的离开都会增加新的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节点作为中继节点，分析其执行效率，并能够使用在真实的战术网络环境中。