基于SDN 的自组织网络路由框架及构建方法

董芳，胡宇翔，李鸥

（1.信息工程大学，河南 郑州 450001；2.通信网信息传输与分发技术重点实验室，河北 石家庄 050081；3.国家数字交换系统工程技术研究中心，河南 郑州 450002）

1 引言

以传感网、物联网等泛在网络为典型表现形式的自组织网络既解决了无固定通信基础设施下移动通信联络的需求，又可作为现有固定通信基础设施的延伸来实现广域覆盖，是填补固定网络“空白”的首选方式，在工业监控、环境监测、医疗监护、智能家居、交通管理等诸多领域得到广泛应用。随着用户对网络体验的期望值越来越高，自组织网络已不仅局限于传统意义上的信息获取功能，更向着信息传输、处理，甚至服务定制等更高层次发展。然而，自组织网络鲜明的节点移动性特点，使时延、带宽、吞吐量等参数的变化不可预测，导致数据传输可靠性降低甚至失效，进而无从保证网络服务的有效性。另外，能量受限制约着自组织网络节点提供服务的多样化和复杂程度，成为阻碍自组织网络整体服务质量提升的主要因素。

为了解决以上问题，研究者尝试将最新的网络技术用于新型自组织网络的设计中，与软件定义网络（SDN,software defined networking）结合的自组织网络研究就是其中热点之一。SDN 起源于校园网，发展于互联网，其初衷是把当今互联网垂直紧耦合的体系结构解耦，以模块化结构开放网络核心功能，为打破现有网络“结构决定应用”的僵局[1]提供可行方案。目前，SDN 向无线网络扩展，较为成熟的研究成果集中于网络核心网层面（如5G 核心网等），但应对底层无线复杂环境仍显乏力。本文不回避无线接入的复杂性，在开放的控制平面内进行自由的网络功能创新，以显著增强自组织网络在功能路由、网络资源管理及规模化组网等方面的能力，其中定制化的路由设计是研究重点。

在自组织网络路由模型方面，面向Ad Hoc 灵活QoS 模型（FQMM,flexible quality of service model for mobile Ad Hoc network）是一种典型的无线移动自组织网络QoS 模型[2]。该模型以区分服务模型控制数据流，以集成服务模型对相似节点进行分类，能够根据网络流量及网络特性自适应地调节数据业务量，但该模型受限于节点计算与容量状况，只适用于小规模网络。无状态自组织网络QoS 服务模型（SWAN,stateless wireless Ad Hoc network）[3]采用分布式算法为数据业务提供QoS 保障。和FQMM 不同的是，该模型独立于路由协议，只需在源节点维护QoS 状态。然而，SWAN 仅为实时业务和尽力而为业务提供服务，尚不能满足除此之外的其他用户应用需求。在支持服务质量的路由协议方面，研究人员从不同的路由策略如多径传输、带宽预留、跨层联合、负载均衡等出发提出了大量路由协议，这些协议各具特点，考虑的参数也不尽相同，但大多是在原有尽力而为路由协议的基础上进行改进与拓展[4-5]，难于提升网络整体效能。在SDN 下的自组织网络功能革新方面，Gibb 等[6]提出了一种由外部特征提供商开发和部署的网络架构，该架构通过提供商之间的竞争促进网络功能创新。Mogul等[7]设计了一种控制平面，用于支持控制器上应用程序的组合，实现模块组合和优化，该工作与本文研究的网络分属不同类型，SDN 下的自组织网络可借鉴其思想。以上研究成果表明，自组织网络现有的路由设计存在诸多问题，引入SDN 实现自组织网络的路由定制优势明显，但同样面临着配置复杂等问题，目前鲜有明确思路与可行方案能够圆满解决以上问题。本文从基于SDN 的自组织网络全局系统出发，探讨SDN 下自组织网络设计的新思路和新方法，并重点关注基于SDN 的自组织网络路由设计框架及可行的构建方法。

SDN 下的网络功能组合是提高网络整体效能的主要方向之一[8]，其思想是将当前“僵化的”按层划分的网络功能重新抽象并分解为更细粒度的功能单元，然后按需组合为复合的功能集。在这一思想下，自组织网络设计发生了质的飞跃，即“网络结构主动适配上层应用”，如图1 所示。首先，网络功能实现模块化。在网络节点上，网络功能软件化为基本单元，节点整体功能则体现为根据服务实时重构的基本功能单元集。其次，路由序列化。在端到端系统中，路由软件化为满足服务约束的节点和链路有序序列，在功能层面上也就体现为能够承载网络服务的有序节点和链路序列，称为服务路径（SP,service path）[9]，服务路径上的相邻节点在功能层面上互为下一跳节点，但这样的相邻节点往往不是物理网络的相邻节点。由此，SDN 下的路由是由服务路径及其服务路径上相邻有序节点间普通节点构成的矢量路径，这里的难点在于获取服务路径上的有序节点和链路，而有序节点间的路由可由现有路由协议完成。本文聚焦于SDN 下基于服务路径的路由构建，明确SDN 下自组织网络控制系统架构，并以此架构全面分析SDN 自组织网络路由的本质特点和全新方式，提出一种基于服务特征的分层次路由方法，重点设计路由关键节点和关键链路的选择算法，以最优的方式将用户定制的服务嵌入基础物理网络中，这里最优方式是指能够让具体网络性能参数（如能耗、负载均衡、平均时延、网络效能等）达到一个最佳状态，从而构成业务数据传输的服务通道，为用户定制服务提供承载支撑。最后，依托OpenFlow1.3 与NS-3 实现原型系统，验证SDN 下自组织网络路由实现的优势。

2 基于SDN 的自组织网络控制系统架构

图1 服务路径与路由示意

基于SDN 的自组织网络相对成熟的应用场景是车载网（VANET,vehicular Ad Hoc network）[10]，如图2(a)所示。VANET 将网络节点分为无线接入点（车辆）、路边接入单元和SDN 控制器3 类。无线接入点在路边接入单元控制范围内，通过路边接入单元接受SDN 控制器控制；在路边接入单元覆盖不到的地方，无线接入点完全以自组织的方式工作。SDN 控制器经由路边接入单元至无线接入点的控制流承载于控制范围较广的LTE，无线接入点间的数据流则由高带宽的Wi-Fi 承载。本文将VANET的结构抽象并扩展（如图2(b)所示），作为基于SDN的自组织网络的基础控制架构。

如图2(b)所示的基于SDN 的自组织网络结构在集中式和分布式之间进行折中，是SDN 下自组织网络的新型部署架构，可以概括为“物理上分布，逻辑上集中”网络控制方式[11]。“物理上分布”指网络节点所处的网络分级地位不同，从边缘网络到核心网络依次为独立节点、接入控制器和全局控制器；“逻辑上集中”指不同级别的控制器运行相应级别的SDN 控制软件和应用配置，在同一级上拥有同样的控制能力和本地服务能力。全局控制器负责组建“流”的最高层分发系统，通过发布控制事件来同步各级控制器；接入控制器连接移动的独立节点并对其问询和管理。当独立节点进入或移出接入控制器控制范围时，接入控制器通过SDN 北向接口重新配置独立节点，同时接入控制器还可以通过SDN 东西向接口与相邻的活跃接入控制器建立连接。为了维护接入控制器面向独立节点的全局性和相对于全局控制器的本地化，接入控制器采用“发布/订阅”事件的方式完成状态更新。

3 基于SDN 的自组织网络分级路由建模

定制化路由是自组织网络长远发展的必然要求。SDN 的设计理念开放了网络控制平面，从而为面向服务定制的路由提供了基础网络条件。同时，SDN 并不是具体技术（如 OSPF（open shortest path first）等），所以完成面向服务定制的路由需要现实的方法。基于SDN 的自组织网络路由过程可以描述如下。首先，建立备选节点和链路集合。SDN 控制器将用户需求映射为具备用户服务特征的备选节点和链路的集合。其次，计算服务路径。SDN 控制器根据掌握的节点和链路状况（资源、网络效能等）视图，在备选节点和链路的集合中找出服务提供节点。以上提供服务的节点和链路是服务路径上的相邻节点，这些节点是定制化路由上必须存在的节点，本文将这些节点关键点和关键链路称为路由关键点和关键链路，由SDN 控制器下发至网络相应节点。最后，实现定制化路由。路由关键点和关键链路按照本地路由协议完成数据在源节点和目的节点上的传输。

图2 VANET 与基于SDN 的自组织网络控制架构示意

基于以上过程，从功能角度看，SDN 下的路由涵盖了服务路径，即服务路径上的节点和链路作为路由关键节点和关键链路是物理路由的组成部分；从实现角度看，SDN 下的路由仍是节点运行路由协议计算下一跳的过程，只是下一跳集合中除必须包含路由关键点和关键链路外，还可能存在其他中间节点。所以，SDN 下的路由并不是颠覆路由的本质含义，而是基于服务路径的路由实现方法扩展，这一扩展最重要环节在于找到路由关键节点和关键链路。当然，一般情况下，SDN 控制器能够掌握本控制域内节点状况，合理计算出定制路由。但由于自组织网络独立节点移动性、能量受限等不确定因素，不排除SDN 控制器对移动节点信息更新的滞后性，因此存在移动节点不能胜任路由关键节点和关键链路的个别异常情况。此时，由移动节点将自身状况主动上报SDN 服务器，请求重新计算服务路径和确定路由关键节点和关键链路，此时的服务路径不一定是最优的，但在路由上却是可实现的。

路由关键节点和关键链路在服务路径上是连续的，但在端到端的路由上却往往是离散的，受到自组织网络拓扑变化较快的制约，由SDN 控制器计算出路由上的所有节点是不切实际的；同时，服务路径已能够完全呈现用户需求，由SDN 控制器计算出路由关键节点和关键链路间的其他节点也是没有必要的。基于以上分析，SDN 下自组织网络的路由选择可以被建模成为一种带约束下的路由关键点和关键链路选择问题（RKNLSP,routing key node and link selected problem），这个问题的特殊性在于路由关键节点和关键链路的SDN 控制器集中式选择，以及以上节点和链路间分布式路由计算要并行实现。RKNLSP 优化目标为充分有效地利用网络的有限资源，为业务请求提供更优的服务。这里，路由关键点和路由关键链路间路由按网络常规路由协议配置。RKNLSP形式化描述如式(1)所示。其中，u是SDN 控制器计算的一种网络资源可行的配置，ξ是网络资源全部可行配置的集合；Nk和Lk分别表示备选路由关键节点和链路的集合，N表示网络全部节点的集合，PROTOCOL 表示网络可配置路由协议的集合；Demand(*)表示某业务要求关键节点或者链路能够提供的资源，Remain(*)表示关键节点或者链路剩余的资源，Capability(*)表示关键节点或者链路总的资源量。

网络架构是路由总体设计的主要依据，结合图2(b)所示的网络结构，基于SDN 的自组织网络路由规则也是分层次的，即为接入控制器主导的独立节点间路由和全局控制器主导的接入控制器间的路由。对网络业务特点和网络自身特点的分析是进行路由协议设计的前提，在接入控制器控制下由独立节点组成的接入层面，网络业务表现为数据的采集与回传，具有明显的方向性，自组织方式是实现多跳信息传递和网络控制的手段，能量集约化是路由设计的重要因素；在接入控制器和全局控制器组成的核心平面，网络业务表现为端到端的横向业务，具有显著的用户服务特征，如何保证服务有效性是路由设计的关键问题。所以，RKNLSP 又可分为面向服务的2 个子优化问题，即在网络接入层面的系统耗能最小化问题和在核心层面的网络效能最大化问题。

3.1 接入控制器域内路由能耗的建模

传统的自组织网络中，每个独立节点只掌握局部网络拓扑信息，优化的目标却是“多条传输路径的端到端总功耗”的全局目标，而完成全局目标则要依赖源节点及中继节点对相邻节点的探测，不断积累一跳外网络的拓扑信息。此时节点能耗由两部分组成：用于探测拓扑信息部分的和用于通信部分的，则节点能耗为。系统能耗优化模型为。假设节点i在ri范围内以按需方式发送邻居探测消息，收到包含目的节点位置信息的消息，如果节点的探测范围ri扩大，则增加，但由于可能选择到更优的路径，可能减少，找到合适的ri，就使系统整体能耗最小化[12]。这个问题可以采用整数规划的方法解决，但是复杂度偏高。

3.2 全局控制器域内系统服务效能的建模

作为支持自组织网络整体服务效能提升的一项关键技术，全局控制器域内的路由设计已不能仅考虑节点内简单的数据转发功能，伴随着接入层面接入控制器节点性能的提升，路由的构建不仅需要考虑节点转发能力，而且还要考虑节点的服务部署情况、网络的总体效能等因素。由于满足某一服务的节点和链路不唯一且提供服务的节点性能和链路代价不相同，路由计算将比现有网络路由多采用的距离矢量或链路状态算法更复杂。本文将全局控制器域内RKNLSP 抽象成为最优化问题，并建立与之相应的整数线性规划模型，如式(2)～式(8)所示，符号及其含义如表1 所示，旨在满足网络效能最大化目标的条件下找到最优的路由[13]。节点和链路服务特征如式(3)～式(4)所示。式(5)是节点服务能力约束。式(6)是节点间链路能力约束。式(7)～式(8)约束针对某一服务，全局控制器最终下发的路由策略中所包含路由关键点和链路的唯一性。

表1 式(2)～式(8)的符号及其含义

4 基于SDN 的自组织网络路由设计与求解

基于以上论述可以看到，SDN 下自组织网络路由问题从总体上看仍可归结为一类典型的整数线性规划（ILP,integer linear program）问题，通常情况下，这一类问题属于NP-hard 问题，求解时复杂度较高。当问题中变量数较少时，可以采用穷举算法遍历搜索空间的所有可行解，以确定最优解。但是，当模型中变量数增加时，问题求解的复杂度是呈指数增加的，难以再通过穷举遍历的方式进行求解。因此，快速且优质地获得模型解的关键在于约减变量数目。路由关键节点体现为2 种类型：一种是服务要求节点本身能够提供某种功能服务；另一种是服务路径要求两节点之间的某段功能链路。所以节点与链路约束可统一为约简为对节点的约束。另外，从工程角度而言，与获取网络全局信息相比，获取网络关键信息（节点和链路）的过程更具确定性、结果更具针对性，也可以进一步降低ILP 的求解复杂度。

4.1 基于节能的独立节点映射

SDN 下的自组织网络在接入层面，独立节点能量受限，节能成为此时服务特征的主要依据，伴随着独立节点的移动性，固化独立节点与接入控制器的信息交互行为是节能的关键。在接入控制器控制范围内，控制器管理多个与之直接相连的独立节点，并通过间接查询等方式管理其他非直连的独立节点。接入控制器可以将所有的转发规则一次性写入独立节点转发流表，从而使其在任何数据分组到达之前便知道所有可达地址。主动模式中，接入控制器主动将流表进行更新和推送，节点不能将失配的数据分组转发给接入控制器，因此不能发起一个新建的数据流业务。被动模式中，接入控制器不会主动地进行流表更新，只有接收到底层的独立节点发送来的请求时，才会向相应的独立节点下发流表更新信息。与传统的自组织网络由独立节点“探测式”节能路由设计不同，接入控制器是这一层面路由决策者，接入控制器对独立节点的“发布/订阅”式信息更新，使独立节点不确定的探测过程固化为有限次分阶段的信息交互行为。节点能耗和系统能耗如图3所示。

图3 网络接入层次节点能耗和系统能耗

从路由方面考虑的能量集约化有2 种思路：节能和能耗均衡。其中，节能即通过寻找节能的路由，减少路由建立和维护的控制开销或提高路由可靠性方法，降低传输一定量的数据所需要的能量；能量均衡即通过合理地从空间上调度能源，使网络中节点能量均衡消耗减少，从而延长网络寿命。首先，接入控制器掌握所控独立节点状态，由接入控制器以最小能耗路径（阶段1、阶段2 和阶段3）[12]来引导节点间路由；其次，当节点被选为业务中继节点时（阶段4），一定是经过接入控制器完成控制范围内能量均衡工作的结果；最后，接入控制器有持续的能量供给，实现能量均衡算法的复杂度和能量消耗都可不计入以移动节点生存性为目的路由开销。所以，系统能耗最小化即每个节点能耗和最小化，从而使系统能耗由整数规划问题约减为线性求和问题，大大降低了问题求解复杂度。假设节点收发损耗相同为Eelec（Eelec_sent=Eelec_receive=Eelec），交互信息长度相同为L（Lint=Lcon_cyc=Lcon_ini=Lchange=Lcom_charge=L），兼顾到节点移动性，接入控制器域内两节点的距离最大值D为控制器的控制范围，此时系统能耗存在最大值。另外，在接入层面上，选择合适的参数去抽象无线设备错综复杂，且某些参数因为实时性和复杂性无法被控制器动态配置，所以本层面路由关键点间的物理路由（即若干段点到点的物理链路）仍采用现有协议完成，如AODV（Ad Hoc on-demand distance vector routing）等。

综上所述，将本层面路由整体过程概括为算法1，具体步骤如下。

算法1基于节能的独立节点映射路由算法

1)SDN 控制器计算控制域内节点能耗，周期性更新网络能量视图；

2)若节点发出路由请求，转到步骤3)，否则转到步骤1)；

3)SDN 控制器以最小能耗路径引导路由，找到备选下一跳节点；

4)SDN 控制器通过能量均衡后确定下一跳节点；

5)重复步骤1)～步骤3)。

6)若找到最后一个路由关键点，转到步骤7)，否则，转到步骤3)；

7)SDN 控制器记录路由关键点并下发相应网络节点；

8)若网络节点没有异议，转到步骤9)，否则，网络节点上报自身状况给SDN 控制器，转到步骤2)；

9)路由关键点运行普通路由协议；

10)return；

4.2 基于服务能力矩阵的节点（网络核心侧节点）映射

SDN 下的自组织网络在核心层面，以用户为导向的服务有效性成为网络服务能力的关键，此时路由的构建就是通过服务能力矩阵计算满足服务需求服务路径，继而以网络效能最大化将服务路径上的节点映射为路由关键点集合。

4.2.1 效能函数

网络效能函数是以节点服务能力为变量的函数。服务能力与网络效用可能表现出相同的特性，即服务能力越大，效用越大，如节点能提供的带宽越大，效用就趋向增大；服务能力与网络效用也可能表现出相反的特性，即服务能力越大，效用越小，如节点耗能越大，效用就趋向减小。也就是说，一些服务能力越大，效能越优，另一些服务能力越小，效能越优，所以定义转化函数（如式(9)和式(10)所示）以取得基于所有能力变量的一致性优化结果[13]。

不失一般性，本文将节点具备的服务能力归一化为[0,1]。节点第k个服务能力矢量表示为中的最大值且为第j个元素的值，即。引入一个比值归一化矢量，则得到简记为r，转化函数可以分段如式(11)和式(12)定义，满足效能函数的归一化单调性要求。

为此，效能函数可以定义为f+和f-的仿射组合如式(13)所示，wk≥0(1≤k≤t)为仿射系数且=1。

4.2.2 服务能力矩阵与服务请求矩阵

基于网络图GS=(NS,LS)，Spe={p e|e=1,2,…,E}表示基本功能单元集合，那么节点Nn(Nn∈NS,1≤n≤N)对应的所有服务而产生的网络效能为

4.2.3 节点（网络核心侧节点）映射

基于服务能力矩阵和服务请求矩阵计算备选择矩阵Nsel=[si,r]N×E，该矩阵包含服务路径需求中所需的各类服务，计算过程通过矩阵乘法得到，如式(16)所示。

其中，设矩阵Nsel的各列向量为sr=(s1,r,…,sN,r)T(r=1,2,…,E)，因此选择矩阵可简化表示为Nsel=[s1,…,sE]。如果sr=0，表示没有节点能够满足服务路径需求；如果sr≠0且si,r≠0(si,r∈sr)，表示有网络节点ni能够作为服务路径需求的可选节点。

依据所得的选择矩阵Nsel，可选择出最优的网络节点用于服务路径需求的服务路径构建。对于服务路径需求的每一基本功能单元，选择节点ni中能提供基本功能单元pe，且具有最大网络效能的节点ni作为该基本功能单元的服务节点，该过程可以形式化表示为

4.2.4 基于节点（网络核心侧节点）映射的路由算法

综上所述，将基于节点映射的路由算法概括为算法2[15]，具体介绍如下。

算法2基于节点（网络核心侧节点）映射的路由算法

5 系统设计与验证

5.1 系统设计

综上，SDN 下的路由过程可概括为独立节点依照接入控制器给出的能耗优化路径，将服务请求经接入控制器上报至全局控制器，全局控制器接受服务请求后，开始启动路由构建。路由构建经过3 个过程：首先，全局控制器以网络效能最大化选择核心层路由关键节点；然后，接入控制器以能耗集约化选择接入层路由关键节点；最后，路由关键节点间路由构建。由于关键节点间路由采用现有的路由协议，对于这些协议研究的相关实验参数已经相当丰富，本文不再重点关注。以下实验以服务路径构建为主要参考依据。

为了证明本文算法的有效性，设计并搭建了如图4 所示的原型系统。基于SUMO（simulation of urban mobility）网络模型[16]，利用NS-3 模拟器在1 000 m×1 000 m 区域内布设5 个接入控制器，每个接入控制器最多控制30 个移动节点。该系统使用ONOS 作为SDN 控制器，使用OpenFlow 1.3 协议作为控制器与交换机之间的南向接口。ClickOS 是一种支持网络中间件服务的软件虚拟化服务实现平台，因此原型系统利用其作为基本功能单元的运行平台。接入控制器在原型系统中具备双重功能，既是面向全局服务器的SDN 交换机，也是面向独立节点的SDN 控制器。

图4 基于SDN 的自组织网络原型系统

5.2 实验验证

区别于传统的自组织网络路由，SDN 下的自组织网络路由是基于服务能力（本文主要指能耗和网络效能）分级实施的，这样的路由不仅要适应自组织网络移动性的特点，更要发挥SDN 集中控制与服务定制化的优势。所以，实验验证着力点在于：首先，接入层面评估各中路由方式下独立节点移动中的能耗优劣；其次，核心层面对比服务路径数目与网络效能的关系；最后，评估SDN 控制器主导下的自组织网络路由的总体效果。

5.2.1 接入级路由算法比较

节点移动性通常体现为节点移动速度；用户业务流特性在接入层面体现为节点并发业务速率。为比较节点移动速度对路由能耗的影响，采用随机路点模型[17]且业务流特性固定。基于图4系统的接入层面，在单个接入控制器控制范围内完成通信过程，每次通信的独立节点及其数据流由NS-3 服务器/客户端轮询流序列产生，在设定相同节点数量（总节点数为20 个，活动节点数为10 个）且工作在速率0.25 packet/s（低业务速率）、25 packet/s（高业务速率）的情况下，节点速度按每3 m/s 的步长从0 增加到15 m/s。

图5 每次配置参数的仿真持续时间5 min，共进行10 次仿真，取传输1 bit 分组的端到端能耗平均值。从整体趋势上分析，各路由方式在不同业务速率下能耗曲线平稳，表明各路由方式对节点移动的适应性较强。其中，SDN 方式能耗均小于其他路由方式，是由于接入控制器避免了不确定的探测过程且总能选择能耗最小的节点建立端到端路由。相对于图5(a)，图5(b)的能耗曲线整体上移，是由于业务速率提升后加大了发送电路能耗；在能耗曲线整体上移的趋势下，曲线间距离也增大，尤其是AODV 曲线上升更为明显，说明能耗受业务特征影响是现实存在的，需要在网络核心层面考虑业务特征因素。

图6 每次配置参数的仿真持续时间50 min，共进行3 次仿真，获取各节点剩余能量平均值。可以看出，节点剩余能量受业务特征影响，高业务速率下耗能稍高。SDN 方式下各节点平均能耗剩余柱状图较为规整，而其余路由方式节点平均能耗剩余柱状图呈锯齿状，说明SDN 方式下节点间能耗相对均衡，原因是接入控制器始终以负载均衡选择关键点。

5.2.2 核心层次网络效能评估

图5 传输1bit 分组的端到端平均能耗

图6 节点剩余能量

基于网络配置简便的目的，朴素的手动配置方式是构建路由的常用方法，其主要思路是同样的服务尽可能地让一个关键点提供，当一个节点的资源耗尽后，开始部署下一个节点，依次连续部署下去。本文依据式(14)和式(18)计算了每个关键点上资源占用率（ROR,resources occupied ratio）和网络效用值的情况，并且将本文RKNLSP 解决方法所得结果与基于手工配置方法所得结果进行比较。ROR 定义为提供基本功能单元时节点或链路上每一资源的已使用量()与该资源的总量()的平均比值。其中，k(k=1,2,…,K)是资源种类，i(i=1,2,…,NS+LS)是网络节点或链路的编号，NS和LS分别是网络中节点和链路的总数目，δ()=1表示节点或链i上有资源种类k，否则δ()=0。

如图7 所示，在路由数目分别为10 和104的条件下，本文RKNLSP 方法在不同服务路径长度下，网络节点的平均效用值分别约为0.69 和0.53，而相同条件下，手动方法的网络平均效用值约为0.42 和0.38。比较而言，本文所提出的RKNLSP解决方法的网络效能相比于手动配置方法整体提高约14%，但在路由数目相对较少的情况下，RKNLSP 解决方法优势并不明显。分析原因是本文RKNLSP 解决方法能够协同调配全网范围内的资源构建服务路径，使不同网络节点上的资源能够得到较为充分的利用。但当路由数目较少时，由于RKNLSP 解决方法产生一定的计算开销，所以网络平均效用值相差不多。另外，RKNLSP 解决方法资源平均占有率低于手动配置方法，意味着SDN 控制器参与下为同一基本功能单元所付出的资源量更少或者说节点间的资源占有量更均衡。当路由数目较少时，路由长度增加并不显著地增加资源占有率且2 种方法资源占有率相差也不大；当路由数目激增时，随着路由长度增加手动配置方法资源平均占有率较RKNLSP 方法增长迅速。这是因为RKNLSP 的自适应性只有在网络服务数量规模下才能显现。

5.2.3 网络整体性能效能评估

基于图4 原型系统建立一个独立节点间信息交换场景，源节点和目的节点之间的业务流量需要获得一定的可靠性支持。实际实验中，利用C#语言编写一个自动机来产生大量的服务能力参数，其中每一路由分配有1～5 个不同的基本功能单元数目。每次实验后，统计服务路径的构建时间（接入控制器计算时间与全局控制器计算时间之和）、OpenFlow配置时间和流量在用户和服务器之间的传输时延。重复统计多次得到平均值如图8 所示。

图7 不同路由数目条件下的网络平均效用与资源利用率示意

比较图8(a)和图8(b)中的结果可以看出，服务路径的构建时间、OpenFlow 配置时间和传输时延都伴随服务路径数目的增加而增长，并与服务路径的长度增长趋势一致。统计结果也显示服务路径构建时间在服务路径的构建中占有重要的比例，并且该比例值随网络中路由数目的增加而提高。其原因是：一方面，当路由数目增加时，控制器需要处理更多的请求，从而使路由建立时间延长；另一方面，由于路由关键点的负载增加，从而需要更多的时间来完成服务处理。

同时，文献[18]在互联网环境下设计了一种集中调控的分布式路径选择算法，其中集中调控等价于本文中SDN 控制器计算服务路径，分布式选择等价于路由关键点间的路由过程。图8(a)和图8(b)中的结果与文献[18]结果具有一致性，即服务响应时延（OpenFlow 配置时间与服务路径计算时间之和）相对于其他算法普遍降低。

图8 不同路由数目条件下的服务路径建立时间示意

6 结束语

当前，在SDN 技术的推动下，新型网络体系结构的设计成为未来网络的研究热点之一，与SDN结合的自组织网络研究方兴未艾。节点能量受限与移动性是自组织网络的显著特点，也是未来自组织网络路由设计的制约因素，且定制化服务的更高要求使自组织网络在路由层面尤其是功能路由设计上进展乏力。SDN 将网络传统的垂直紧耦合的体系结构解耦，重新构造模块化的网络功能结构。基于此SDN 下的自组织网络路由可以描述为逻辑上的服务路径和实现上的物理路由之叠加复合。首先，基于SDN 优势进一步分析了SDN 下自组织网络控制系统架构和全新的路由实现方式，建立了基于整数规划模的分级路由模型。其次，在接入控制器基于优化目标（最小能耗路径和能量均衡）引导路由的过程中固化了网络接入层面的信息交互流程，提出一种基于服务能力的分层次路由思想，重点设计了路由关键点和关键链路集中式选择问题的求解算法（称为RKNLSP 算法），该算法通过服务关键点的映射以最优的方式（节能和网络效能）将用户定制的服务嵌入基础物理网络中，为用户定制服务提供承载支撑。最后，在搭建的原型系统上验证了RKNLSP 算法能够实现的功能，同时在网络接入层次评估了SDN 下的RKNLSP 方式路由相对于自组网传统路由算法的性能，在网络核心层次和网络全局层面验证了相对于手动配置方式实现“按需配置”服务的网络效能整体优势。

然而，在网络实际运行中，核心层面的网络拓扑变化一般慢于网络流量的动态变化，服务路径构建的输入可由原始网络拓扑简化为离线计算的经验服务路径集合，当离线部署的服务路径产生的网络效能降低到一定门限后，再启动服务路径计算过程，从而降低算法实现复杂度。所以，作为对SDN下新型自组织网络的初步探讨，本文所提到路由思路、模型及算法仍值得进一步优化和完善。