一种面向软件定义移动自组网的拓扑发现方法

所属分类：电子论文阅读次时间：2019-11-09 15:13

本文摘要：摘要:移动自组网在传统的分布式组网方式下难以满足复杂的业务需求对网络QoS及安全性的高要求，基于SDN的移动自组网架构(SD-MANET)的提出为解决该问题提供了有效的解决思路。在SD-MANET中，拓扑发现是控制器进行流量调度与安全性控制的前提。本文提出一种面

高端学术服务项目

　　摘要:移动自组网在传统的分布式组网方式下难以满足复杂的业务需求对网络QoS及安全性的高要求，基于SDN的移动自组网架构(SD-MANET)的提出为解决该问题提供了有效的解决思路。在SD-MANET中，拓扑发现是控制器进行流量调度与安全性控制的前提。

　　本文提出一种面向SD-MANET的拓扑发现方法，其主要思想是:利用连通支配集算法生成骨干网络，由骨干节点将局部拓扑信息通过上行通路上报给SDN控制器，控制器根据收集到的邻接信息计算出全网拓扑。本文方法通过限制向控制器上报局部拓扑信息的节点数量来降低拓扑信息收集过程中产生的额外开销。仿真结果表明，该方法能够准确地生成并维护网络拓扑，且具有较小的控制开销。

　　关键词:移动自组网,软件定义网络,拓扑发现,骨干网

计算机仿真

　　0引言

　　移动自组网(MobileAdHocNetworks，MANET)因其独立性、灵活性和适应性被广泛应用于战术通信、传感网、社交网络以及灾难恢复等场景[1]。近年来，越来越复杂的业务需求对MANET的安全性及QoS保证提出了更高的要求[2]。传统MANET采用分布式组网方式，难以在源节点和目的节点之间根据网络资源信息(端到端延迟、带宽、丢包率)选择最佳路由[3]，在提高安全性及QoS保证上遇到了瓶颈。软件定义网络技术(SoftwareDefinedNetwork，SDN)将网络的控制平面和转发平面解耦合，采用集中式控制替代原有的分布式控制[4]。

　　基于SDN的移动自组网网络架构SD-MANET[5]为上述问题提供了新的解决思路。控制器通过南向接口协议与网络设备进行通信，OpenFlow是目前主流的南向接口协议。区别于传统MANET的分布式组网方式，一般来说，SD-MANET中由控制器负责收集拓扑信息并进行全网拓扑学习，进而基于学习到的全网拓扑实现网络流量调度和安全性控制[6]。拓扑发现是控制器管理整个SD-MANET的基础。

　　从技术角度而言，将LLDP(LinkLayerDiscoveryProtocol)、OSPF(OpenShortestPathFirst)或者IS-IS应用到OpenFlow中都可以用来进行网络拓扑检测[7]，但是它们并不适于SD-MANET，主要原因有:1)一般应用在SDN交换机较少的有线网络中，其协议报文及响应机制对于无线窄带网络环境来说，带宽开销过大[8]。2)SD-MANET中因节点移动、信道干扰、电量消耗等因素导致的拓扑变化与有线网络拓扑变化相比频繁且复杂得多，现有技术没有针对性的解决方案[9]。

　　目前，在SD-MANET领域，不同的网络架构采用的拓扑发现方法也不尽相同。文献[10]提出了一种基于SDN的战术移动自组网网络架构，由多个控制器分级对网络进行协同管理，控制器可以部署在指挥中心、便携无线基础设施或者移动设备上，通过应用层协议将节点本地拓扑信息发送至控制器。例如，网络节点通过运行分布式组网协议OLSR可以得到全网拓扑[11]。

　　理论上来说，控制节点可以利用SNMP等应用层协议进行拓扑信息的收集和更新。但是，该过程依赖于转发层面的中继广播，控制开销较大，且获取相关的设备信息及资源信息还需要进行复杂的跨层协议设计和报文扩展，开发成本很高。文献[12]提出了一种适用于无线传感器网络的开源软件定义网络解决方案SDN-WISE，实现了基于状态的OpenFlow流表处理机制，能够降低传感节点与控制器之间的信息传递代价。

　　文献[13]基于SDN-WISE提出了拓扑发现协议FTDP，协议基于模糊理论综合考虑节点的邻居数、剩余能量以及工作负载对拓扑发现及路由决策模块进行了优化，但计算量大，对拓扑变化的适应性较差。文献[14]提出一种将异构战术网与SDN相结合的架构SDBN，通过异构子网内固定的网关节点向控制器上报子网拓扑。

　　在文献[15]提出的网络模型SD-TAODV中，控制器周期性地向邻居节点广播拓扑请求报文，报文在节点间逐层向外扩散，报文每到达一个节点，就将当前节点加入到所携带的拓扑列表中，并将报文返回给控制器。该方法通用性较强，但报文处理复杂，控制开销很大。本文提出一种新的拓扑发现方法。该方法基于连通支配集的思想减少网络中直接与控制器交互邻接信息的节点数量，从而减少拓扑发现过程中的带宽开销，且在理论上具备一定的通用性。实验表明，本文方法具有较小的控制开销，且能够及时感知拓扑变化。

　　1拓扑发现方法的基本思想

　　在SD-MANET中，选择网络中某个节点来部署控制器，这个节点作为网络中的控制节点(CN)与其他转发节点一样具有移动性。拓扑发现需要考虑以下2个问题:1)不同于有线网络中有专门的转发设备(交换机或路由器)来协调各终端设备间的通信，SD-MANET中的每个节点既是终端节点，又是转发节点。如果网络中的每个转发节点都向CN上报本地的局部拓扑，产生的控制信息必然会带来大量的带宽开销，CN会收到大量的冗余信息。因此，应该选取尽可能少的节点负责上报局部拓扑信息。2)节点移动性将导致CN与转发节点间的通信是不稳定的，故节点需要及时更新并维护到CN的上行通路，以减少局部拓扑信息上报过程中的报文丢失。

　　针对上述2个问题，本文提出:从所有节点中选取一部分通信能力强、稳定性高的节点集合构成一个骨干网，骨干节点通过到CN的上行通路向CN上报本地的局部拓扑信息。整个拓扑发现过程主要包括2个阶段:骨干网的构造和拓扑信息的收集与维护。拓扑发现过程如下:1)在SD-MANET中构造一个骨干网。2)各骨干节点获取并维护到CN的上行通路。3)各骨干节点将本地邻居信息上报给CN。4)CN分析并处理收集到的拓扑信息，生成全网拓扑。

　　2骨干网的构造

　　上文提到需要选取一部分节点集合来构造骨干网。这部分节点集合应当具备以下特性:特性1集合中各节点的通信范围能够覆盖到网络中的所有节点。特性2集合中的节点个数应当尽可能地小。特性3集合中的节点应当具有较高的通信带宽，以保证较高的数据处理能力。为了得到满足条件的节点集合，本文将SD-MANET抽象为一个无向图模型，节点、各节点间的通信链路分别被抽象为图中的点和边。

　　2.1连通支配集算法

　　求任意图的最小连通支配集是NP-难问题[16]，因此，目前在实际应用中，通常用近似解来代替最优解。(n表示节点数量;Δ表示最大邻居数)。文献[17]提出的基于多点中继(MultipointRelays，MPR)计算连通支配集的算法MPR-CDS允许节点根据其被选为MPR的次数和选择其作为MPR的节点(MPRSelector)个数或者其他业务条件约束来调节自身意愿度(willingness)。与其他算法相比，该算法能够保证选出的骨干节点与普通节点之间的链路双向对称。

　　本文使用该算法来生成骨干网络，网络运行过程中可通过调节某目标节点的willingness对骨干网进行管理。该算法的核心思想是采用贪心算法为每个节点v根据其二跳邻居信息N2(v)从一跳邻居信息N1(v)中选择一组中继节点MPR，网络中所有的MPR节点可以构成一个连通支配集，然后执行CDS强化规则减小这个基于局部信息计算出的CDS规模[18]。2条规则如下，对于节点v，若满足以下规则中的任意一条，便将其加入CDS。

　　3拓扑信息的收集与维护

　　3.1上行通路的计算策略

　　骨干网构造完成之后，所有的骨干节点需要及时建立并维护到CN的上行通路。已知对于任一个普通节点，它至少是一个骨干节点的一跳邻居，故本文旨在构造一棵以CN为根节点的生成树，这棵树上，所有骨干节点均为CN的子孙，每个骨干节点到其父节点的链路即为到CN的上行通路。每个节点维护一张DV表(Distance-VectorTable)，用于存储节点到CN的可达信息。表项中，next_hop表示本节点到CN的下一跳，cost表示经过当前下一跳到达CN的链路代价，SN是表示当前可达信息新旧程度的序列号[22]。

　　节点周期性地发送控制链路消息CL_MSG，该消息类似于HELLO消息，即只在一跳范围内广播，不能被转发，报文字段主要有该节点到CN的链路代价cost和序列号SN。节点之间通过交互CL_MSG消息来更新并维护DV表。每个节点在到达下一个CL_MSG广播周期或者DV表发生变化时执行DV表更新过程DV_Updating，该过程的具体描述如下:Step1节点生成一条CL_MSG，并广播。

　　Step2收到CL_MSG的邻居Ni判断自身是否为骨干节点。Step2.1若是，执行Step3。Step2.2否则，丢弃该消息。Step3判断CL_MSG→SN是否大于本地当前DV表中已经存在的最大SN。Step3.1若大于，执行Step4。Step3.2若等于，但cost(Ni，CL_MSG→Src)+CL_MSG→cost的值比对应表项中的cost更小，执行Step4。Step3.3否则，丢弃该消息。Step4新建或更新DV表中到CN的表项，执行Step1。

　　上文中Cost(i，j)表示i和j这一对直连邻居之间的链路代价，通过查找节点i的邻居表即可得到。初始情况下，CN的DV表中仅存在一个条目，其他节点的DV表为空。DV_Updating过程从CN生成CL_MSG(CN)并向外广播开始起作用。在DV_Updating过程中，SN的初始化及周期性偶数递增的操作只能由CN来完成，SN从0开始。

　　值得注意的是，CL_MSG消息从CN自顶向下传播的是SN为偶数的链路信息，当骨干节点检测到链路故障时，将SN加1置为奇数沿着上行通路自下而上进行传播，以通告链路故障。DV表中的每一条可达信息都包含一个SN，如果收到了来自不同节点的CL_MSG消息，选择SN较大的那条对DV表进行更新。这一消息处理机制能够保证DV表中的可达信息都是最新的。

　　4性能仿真与分析

　　本文主要使用OPNET18.6.1仿真软件和OpenDayLight控制器对本文方法进行可行性验证与性能分析。

　　4.1仿真实验环境

　　仿真平台由实物环境和OPNET仿真环境2个部分构成。其中，OPNET通过SITL接口与OpenDayLight通信，OpenDayLight通过OpenFlow协议与OPNET中的SDN交换机通信。各节点以packet-in和packet-out消息的形式向控制器传送拓扑信息。在OpenDayLight中添加Topology-Generator模块，负责根据收集得到的局部拓扑信息生成并更新全网拓扑。

　　由于目前OPNET中的SDN交换机模型仅支持有线链路通信，为了使其适应无线环境，本文对SDN有线交换机模型做了修改。物理层使用无线收发信机代替有线收发信机，使之支持无线收发;MAC层采用TDMA技术实现信道复用;通过OPNET将SDN交换节点的属性由固定节点修改为移动节点，使之具备移动性，并在其节点模型中新增MPR-CDS模块，用于构造骨干网。

　　对OPNET18.6.1的通用仿真参数进行设定:信道传输速率设定为11Mbps，传输层使用UDP协议，MAC层使用IEEE802.11b协议，仿真场景中的节点随机分布于20km×20km的矩形区域中，每组仿真实验的结果取20次运行的均值。

　　4.2实验结果分析

　　4.2.1MPR-CDS算法性能

　　通过修改节点传输半径来调节节点平均邻居数。分别对节点平均邻居数N为5、10、15、20时的场景执行节点编址规则优化后的MPR-CDS算法，并统计不同网络规模下选出的骨干节点个数占比。该算法可以有效减少网络中上报局部拓扑信息的节点数量，仿真结果与原算法基本一致。相同网络规模下，随着节点传输半径的增加，算法计算得出的连通支配集节点个数随之减少;当节点传输半径保持不变时，连通支配集的节点个数随着网络节点数的增大而增大。

　　5结束语

　　本文分析了在SD-MANET中进行拓扑发现需要解决的问题，提出了一种适用于SD-MANET的拓扑发现方法。通过分析常用的最小连通支配集近似算法及影响骨干网通信能力的主要因素，对于MPR-CDS算法的节点编址规则进行了优化，在一定程度上提高了生成的骨干网络的通信能力;并提出了在骨干网与控制节点之间建立有效的上行通路的策略。

　　本文使用OpenDayLight控制器以及OPNET仿真软件进行了仿真测试。实验结果表明，本文方法具有较小的控制开销，且能够及时响应拓扑变化并更新全网拓扑。但本文方法还存在一定的局限性，如:骨干节点选择冗余、较大网络规模(大于100节点)的动态场景下对网络变化的适应周期过长等，故仍然需要对CDS算法及报文设计进行优化，并采用适当的故障上报机制来解决拓扑响应时间长的问题。笔者将在后续工作中进一步对当前方法进行改进。

　　计算机技术论文投稿刊物：《计算机仿真杂志》(ComputerSimulation)杂志创刊于1984年，由中国航天科工集团公司主管,由航天科工集团十七所主办。本刊组织的栏目有：仿真技术综述、军事领域仿真、人工智能与系统分析、航空、航天领域仿真、化工领域仿真、汽车仿真、分布交互式实时仿真、仿真应用与研究、过程的建模与验证、仿真培训系统、虚拟仿真、仿真方法与算法等20多个栏目。