开放科学(资源服务)标志码(OSID):

0 概述

互联网应用呈现多样化、精细化和快速化发展，同时网络管理的难度也越来越大。随着流量监测技术的不断提升，网络测量从流量数据中分析用户的行为特征^[1]，为网络管理提供依据。高清视频、虚拟现实等应用使网络带宽快速提升，直接导致网络流量难以复现，为攻击者隐藏恶意流量提供了便利。如果防护措施不规范，频发的网络安全事件严重威胁用户隐私和社会经济安全^[2]。网络测量是网络管理的基础，细粒度的流量统计特征可以准确反映潜在的网络问题，能够有效地指导异常检测工作。测量节点作为网络测量的环境要素^[3]，其主要采集流量的网络节点，如软件定义网络（Software Defined Network，SDN）中的OpenFlow交换机。测量节点选择方法用于决策整个网络中的测量节点，SDN控制器可以在线查询交换机上的流统计信息，然而查询哪些OpenFlow交换机获取了细粒度流信息成为研究热点^[4]。

SDN网络的控制平面和数据平面是解耦合的，控制器能够收集并管理网络的全局状态信息，包括测量节点选择需要的流传输路径。在一条流的传输路径上，任意一个OpenFlow交换机均记录了该流的统计信息^[5]。控制器每次选择流信息最多的OpenFlow交换机作为测量节点，直到获取当前网络中全部流信息^[6]。为避免攻击者通过流传输路径推断敏感信息，在注重隐私保护的SDN场景中，通常采取多路径技术^[7]防止机密信息泄露。如果获取的流传输路径不精确，那么SDN网络只能基于网络拓扑的中心性指标^[8]进行测量节点选择，此时精度越高的流量测量耗费的测量资源越多。单个中心性最高的测量节点对网络行为特征进行估计，大幅降低了测量资源的开销，但是部分流统计信息监测不准确，使得估计误差较大；选择全部网络节点对网络行为特征进行估计，不仅增加控制器轮询OpenFlow交换机的频率，而且相邻测量节点间的流统计存在较大重复的问题。因此，采用最少测量节点覆盖全部流信息是测量节点选择的趋势^[9-10]，以实现测量资源和准确性的平衡。

SDN中基于网络拓扑的测量节点选择问题，可以抽象成最小顶点覆盖模型，即寻找无向图顶点集的最小子集，使其包含图中任一条边的至少一个端点。文献[11]指出，最小顶点覆盖模型是NP-Hard的，不可能在小于1.360 6的复杂度因子内近似求解，研究人员分别采用分支界限法^[12]、贪心算法^[13]、元启发式算法^[14]和局部搜索算法^[15]对该抽象模型进行求解。然而这些算法均存在一定不足。分支界限法能够获取模型的最优解，但是其复杂度高使得算法在大规模无向图中的运行时间无法预估。贪心算法显著降低问题复杂度，但是局部的最优决策不一定能够达到全局最优，并且误差随图的规模逐渐增大。蚁群优化（Ant Colony Optimization，ACO）作为元启发式算法之一，具有正反馈、贪心启发两种机制和较优的鲁棒性，但存在收敛过早、搜索时间长等问题。属于局部搜索的邻域搜索算法（Neighborhood Search，NS）目标在于优化某个特定顶点而不是整个无向图，能够有效缩短搜索时间，但前提是问题的初始解较准确。

现有SDN测量节点选择方案对测量节点状态的考虑有所欠缺^[16-17]，对不同位置的OpenFlow交换机施加了不均匀的测量负载，最佳的测量结果可能导致不均匀的网络负载分布。在真实环境中的网络设备，同一时间运行着多个测量任务，处理性能和内存容量消耗较大，如果继续向其下发测量任务，该设备的测量负载维持在较高水平，可能会出现宕机现象^[18]。控制器利用OpenFlow消息查询OpenFlow交换机的计数器，需要综合考虑查询频率和测量精度。文献[19]指出，CPU吞吐量和三态内容寻址存储器（Ternary Content Addressable Memory，TCAM）容量是制约OpenFlow交换机性能的两大因素，在当前高带宽环境下尤为明显。因此，测量节点的负载因素应纳入SDN测量节点选择问题的范畴。

针对流路径信息获取受限的SDN场景，本文提出一种基于蚁群优化的网络测量节点选择算法。通过对ACO算法的概率状态转移规则和信息素更新规则进行优化，利用OpenFlow消息在线监控测量节点的负载，使用邻域搜索策略替换负载超过阈值的测量点，从而在保证准确性的前提下提高ACO算法的收敛度，缩短搜索时间。

1 相关工作

网络测量节点选择是网络管理工作的基础。随着网络技术的发展，研究人员提出各种智能选择算法，例如ACO算法，但都局限于特定场景。

对于抽象的最小顶点覆盖模型，ACO算法能够提高测量节点集合的准确性，但也存在局部最优、搜索时间长等问题，可以从概率状态转移和信息素更新2个规则进行优化。此外，较优的鲁棒性使得ACO算法可以结合其他算法的优势，弥补其自身不足^[20]。

针对概率状态转移规则，文献[21]使用轮盘赌的选择方式构造可行解，摒弃了传统ACO算法的α、β双参数方案，使得计算复杂度降至O（1），避免了局部最优现象的发生，然而降低信息素的重要程度可能导致算法收敛速度过慢。文献[22]在概率状态转移规则中引入故障排除因子，尽可能避免选择网络中的故障节点，以增加可行解搜索的多样性，从而提高算法的准确度。文献[23]提出现有概率状态转移规则容易导致局部最优解，需要设置平衡参数进行动态调整：初始时平衡参数值较大，蚂蚁倾向于选择信息素浓度高的节点；迭代数次后降低平衡参数的值，蚂蚁选择信息素浓度低的节点，从而避免局部最优；最后再次提高平衡参数的值，从而加快算法收敛过程。

针对信息素更新规则，文献[24]表明，部分异常节点可能影响全局最优解的质量，提出一种排除异常节点的信息素更新规则，以筛选迭代最优解中信息素异常的节点，后续迭代优先选择正常节点，从而将蚂蚁引导到新的搜索区域。文献[21]表明，当信息素挥发系数为常值时，算法对于信息素较低节点的搜索能力较低，因此提出一种信息素动态挥发机制，每次迭代后，挥发系数根据信息素浓度动态变化。文献[25]构建一种改进最大最小蚂蚁系统（Max-Min Ant System，MMAS），以避免结果陷入局部最优解，将顶点信息素初始为最大值，在蚁群搜索过程中，信息素被严格限制在最值范围内，每次迭代后仅更新迭代最优解或全局最优解中顶点的信息素。然而这些信息素更新规则无法兼顾算法的准确性和收敛性，在SDN测量节点选择问题的应用效果不佳。

现有SDN测量方案中均考虑了测量节点选择问题，利用有限测量资源实现较优的测量精度，但是尚未考虑测量节点的过载现象。文献[26]将控制器作为测量节点，考虑部署多个测量节点来测量网络参数的问题，分析变量特征后转换为0-1线性规划问题，并提出一种基于拉格朗日松弛的动态规划算法。该算法能够有效降低不同网络拓扑下的测量成本和运行时间。大多数SDN测量方案从OpenFlow交换机中采集流量信息，如果流路由信息获取不受限制，文献[5]提出5种查询策略，分别为流路径上最后、均匀随机、轮询、非均匀随机和负载最少的单个交换机，它们对网络设备施加不均匀的负载且难以扩展到大规模网络。文献[6]和文献[27]均采用贪心策略选择多个测量节点，其原理是第1轮迭代选择流数最多的一个节点，将第1个测量节点关联的流从流矩阵中删除，后续迭代重复选择点-删流过程，直到流矩阵不包含任何流时停止，以得到1个测量节点集合。然而在实际网络环境中流的数量通常较大，如10⁶条，使得持续统计并更新流矩阵的时间开销不可忽略。

在流路径信息获取受限的情况下，SDN网络测量节点选择问题只能依赖于网络的物理拓扑。文献[27]借助社交网络的中心性指标度量图节点的重要性，提出3种基于中心性的单个测量节点选择方案：介数中心性，接近中心性和度中心性。然而单点测量能够节约测量资源，但是测量准确度低。因此，该文献又提出一种基于扩展中心性的多测量节点选择算法。该算法基于介数中心性选择第1个测量节点，后续测量节点在其邻接点中按照最短路径重叠最少规则进行选择。

根据以上研究和分析，SDN网络下测量节点选择算法存在以下问题：1）隐私保护场景下流路径信息获取受限，基于流的测量节点选择方案失效；2）单个测量点采集的流统计信息不全面，导致测量精度较低；3）基于扩展中心性的多测量节点选择算法未考虑测量点的负载因素，实际测量效果较差。因此，本文在SDN网络中基于网络拓扑进行测量节点选择，改进ACO算法的概率状态转移规则和信息素更新规则，分别提高模型结果的准确性和收敛性，增加一种基于NS策略的过载处理机制局部调整满足条件的测量节点，在不破坏链路覆盖率的情况下，缩短过载处理时间。

2 SDN中基于蚁群优化的测量节点选择算法

基于蚁群优化的测量节点选择算法的参数信息如表 1所示。

2.1 SDN网络中测量节点选择方案

网络测量节点选择的SDN架构如图 1所示。基于蚁群优化的测量节点选择方案部署在SDN应用层，包括拓扑发现、节点搜索、负载监测和过载处理4个模块，同一模块流向其他模块的数据相同。

基于蚁群优化的测量节点选择方案的具体流程为：1）拓扑发现模块通过链路发现机制的REST-API获取模拟网络的所有交换机和链路，汇总成网络拓扑图；2）节点搜索模块利用改进ACO算法搜索graph的初始测量集；3）负载监测模块通过Packet-in消息触发机制和流表统计接口在线计算selects中节点的负载，若监测值超过阈值δ，该测量点被添加到过载测量集；4）过载处理模块利用NS策略将loads中满足覆盖条件的过载测量点从selects中删除，最终得到给定无向图的优化测量集updates。

2.2 ACO算法的规则改进

在无向图$ G=(V, E) $中，$ V $和$ E $分别表示顶点集和边集，覆盖$ E $中每条边的顶点集合是$ V $的子集，最小顶点覆盖$ M $要求该子集包含的顶点最少。假设其中过载顶点的邻接矩阵为$ \mathit{\boldsymbol{S}} $，附加负载的最小顶点覆盖要求使得$ M $包含最少数量的过载顶点。

ACO算法的规则改进是采用ACO-NS算法求解附加负载因素的最小顶点覆盖模型，首先ACO算法从图$ G $中搜索出最小顶点覆盖$ M $，然后NS算法结合邻接矩阵$ \mathit{\boldsymbol{S}} $得到最小状态顶点覆盖$ M\text{'} $，基于蚁群优化的网络测量节点选择算法流程如图 2所示。

对于ACO算法，本文主要改进概率状态转移过程中的候选集定义，对信息素更新过程的优化体现在局部增强和全局挥发2个子过程；而对NS算法优化主要分为构造筛选、替换和冗余检验3个操作，处理测量节点的过载现象。

2.2.1 概率状态转移优化

在概率状态转移过程中，候选集动态减小为空，每次根据概率选择一个顶点后，从候选集中删除点和度均为0的顶点。网络拓扑顶点的度通常服从以下分布^[28]：仅部分节点的度明显较大，多数节点的度在3附近。但是原始候选集更新策略还存在一定的不足：蚂蚁不断构造初始测量集，所选顶点的邻接点的度逐渐减小为1，在信息素和启发信息的作用下，它们得不到及时处理。仿真结果表明，假设无向图规模为n，度为1顶点的数量随着蚂蚁搜索次数增加而增加。区间$ \left(0, \frac{n}{8}\right) $内按正态曲线增大到$ \frac{n}{4} $，而区间$ \left(\frac{n}{8}, \frac{n}{2}\right) $内以线性关系降低到0。因此，未处理的度为1的顶点近似为$ \frac{3{n}^{2}+8n}{64} $，概率状态计算的时间复杂度和空间复杂度均为O（n²）。

蚂蚁每次选择一个顶点后，新候选集更新策略在原始候选集更新策略的基础上继续删除度为1的顶点。假设当前候选集用$ C $表示，则新候选集更新策略的数学描述如式（1）所示：

$ C={C}_{P}-s-{V}_{0}-{V}_{1} $

(1)

其中：$ {C}_{P} $为上次更新后的候选集；s为所选顶点；$ {V}_{0} $为度为0的顶点构成集合；集合$ {V}_{1} $包含所有度为1的顶点。

根据新候选集更新策略，ACO算法的概率状态转移规则进行了相应调整。候选集划分为优选集和计算集。优选集由度为1顶点的邻接点构成的集合，计算集是当前候选集中优选集的补集，必须保证优选集的优先级。在某次迭代中，如果蚂蚁先选择计算集的顶点，由于会删除关联的边，可能使优选集中顶点的度为0，导致优选集顶点被候选集更新策略删除。度为1的顶点与邻接点的边没有被selects覆盖，进而影响模型结果的准确性。优选集顶点的选择概率恒定为1，而计算集顶点的选择概率由信息素浓度和启发信息值计算得到。假设优选集、计算集分别为F和R，蚂蚁k选择顶点$ {v}_{i} $的概率为$ {p}_{i}^{k} $，则调整后的概率状态转移规则如式（2）所示：

$ {p}_{i}^{k}=\left\{\begin{array}{l}1, {v}_{i}\in F\\ \frac{{\tau }_{i}^{\alpha }{\eta }_{\mathrm{i}}}{\sum\limits_{j\in R}{\tau }_{j}^{\alpha }{\eta }_{\mathrm{i}}+1}, {v}_{i}\in R\end{array}\right. $

(2)

其中：$ {\tau }_{i} $为顶点的信息素浓度，初始值设为1，不构成顶点选择的元素，其值随蚁群的搜索逐渐增大；α为信息素指数，用于衡量信息素相对于启发信息的重要程度，指数较传统α、β双因子方案平均降低了3.63；O（n²）数量级的度为1顶点执行概率状态转移规则的计算开销较大；$ {\eta }_{i} $为顶点的启发信息值。邻接点被选择使得顶点的度减少一个单位，实际上是顶点动态变化的度，参数值的计算如式（3）所示：

$ {\eta }_{\mathrm{i}}=\left|{v}_{\mathrm{i}}\right| $

(3)

当计算集顶点和优选集顶点的选择概率相同时，蚂蚁极有可能选择计算集中的顶点，破坏规定的优先级。通过将概率状态转移规则的分母增加1，使得计算集的概率状态始终小于优选集，以确保模型结果的准确性。

2.2.2 信息素更新优化

信息素是自然界蚂蚁间交互的介质，蚂蚁经过节点或路径会释放一定浓度的信息素，但是信息素浓度随时间的增加不断降低。因此，信息素更新因素包括信息素增强和信息素挥发。由于信息素更新因素的触发时机不同，因此构成了不同的ACO算法，正反馈机制强弱也存在一定的差异。全局更新和局部更新是信息素策略的典型执行时机，局部更新指蚂蚁构造一个可行解结束后，全局更新则发生在蚁群搜索到迭代最优解。结合信息素更新因素和触发时机，本文提出一种信息素局部增强-全局挥发规则，增大可行解的信息素浓度，使得蚂蚁趋向于局部最优轨迹，以减少算法的迭代次数，从而有效解决蚁群搜索时间较长的问题。通过动态降低迭代解的信息素，并适当增加蚁群的搜索面，使得全局解与模型最优解的偏差逐渐减小。

信息素局部增强发生在蚂蚁构造出一个可行解，无论可行解是否最优，其相关节点的信息素均适当增加。节点$ {v}_{i} $在第$ t+1 $次迭代中信息素浓度如式（4）所示：

$ {\tau }_{i}(t+1)={\tau }_{i}\left(t\right)+Q $

(4)

信息素局部增强为充分建立ACO算法的正反馈机制，通过当前蚂蚁增强潜在最优节点的信息素，指导蚁群中的其他蚂蚁，以构造较优解。

每当蚁群迭代出一个局部解时，执行信息素全局挥发子策略。根据迭代解降低相关节点$ {v}_{j} $的信息素浓度，如式（5）所示：

$ {\tau }_{j}(t+1)=\left(1-\frac{\left|{V}_{c}^{\mathrm{V}\mathrm{C}}\right|}{\left|{V}_{g}^{\mathrm{V}\mathrm{C}}\right|}\rho \right){\tau }_{j}\left(t\right) $

(5)

其中：$ \left|{V}_{c}^{\mathrm{V}\mathrm{C}}\right| $和$ \left|{V}_{g}^{\mathrm{V}\mathrm{C}}\right| $分别为迭代最优解和全局最优解包含的测量节点数。在迭代最优解中，节点$ {v}_{j} $的信息素按$ \left|{V}_{c}^{\mathrm{V}\mathrm{C}}\right| $与$ \left|{V}_{g}^{\mathrm{V}\mathrm{C}}\right| $的比值进行挥发，比值越大说明迭代最优解偏离全局最优解的程度越高，挥发的信息素也就越多。信息素局部增强可能使算法陷入局部最优解，然而信息素全局挥发可以弥补这种不足，增大非局部最优解节点被搜索的可能性，以保证所提规则在提高模型收敛性时不影响其准确性。

2.3 测量点过载处理机制 2.3.1 OpenFlow交换机负载监测

测量点过载处理机制主要监测selects中测量点的负载，在实际SDN环境中，在线获取OpenFlow交换机的负载。在不同场景下，交换机负载的定义和监测方式有所不同，由于CPU吞吐量和TCAM容量是SDN交换机的两大性能瓶颈，OpenFlow交换机的负载$ {l}_{\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}} $如式（6）所示：

$ {l}_{\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}}=\frac{{T}_{\mathrm{C}\mathrm{P}\mathrm{U}}+{U}_{\mathrm{T}\mathrm{C}\mathrm{A}\mathrm{M}}}{2} $

(6)

其中：$ {T}_{\mathrm{C}\mathrm{P}\mathrm{U}} $和$ {U}_{\mathrm{T}\mathrm{C}\mathrm{A}\mathrm{M}} $分别为测量点的CPU吞吐率和TCAM使用率。因此，测量点负载监测分为统计CPU吞吐率和TCAM使用率。

在SDN交换机中，CPU主要用于处理各种OpenFlow消息，其中Packet-in消息参与多种报文处理机制。假设单个交换机单位时间内发送的Packet-in消息数量为$ \mathrm{i}\mathrm{n}\_\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t} $，根据SDN特性，该指标是有限的。CPU吞吐率计算的关键在于控制器统计单位时间内指定交换机发送的Packet-in消息数。控制器解析Packet-in消息，获取指定交换机对应的dpid标识，进而根据dpid对Packet-in消息进行累加。截止统计时间，控制器输出指定交换机的Packet-in消息数$ \mathrm{i}\mathrm{n}\_\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t} $。因此，CPU吞吐率由$ \mathrm{i}\mathrm{n}\_\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t} $与$ \mathrm{i}\mathrm{n}\_\mathrm{m}\mathrm{a}\mathrm{x} $比值计算得到，如式（7）所示：

$ {T}_{\mathrm{C}\mathrm{P}\mathrm{U}}=\frac{\mathrm{i}\mathrm{n}\_\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}}{\mathrm{i}\mathrm{n}\_\mathrm{m}\mathrm{a}\mathrm{x}} $

(7)

在OpenFlow交换机中，TCAM用于存储流表项，而流表项是交换节点处理数据包的依据。从成本和功耗两个方面考虑，TCAM存储器支持的流表项数量有限，假设最大流表项数为$ \mathrm{e}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{y}\_\mathrm{v}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{m}\mathrm{n} $。交换机当前使用的流表项数在一定程度上反映了其负载状态。

OpenFlow协议提供流表统计机制，包括TableStatsRequest和TableStatsReply消息。控制器向交换机发送不包含数据的TableStatsRequest消息，交换机回复TableStatsReply消息给控制器，TableStatsReply消息体结构如下：

/* Body of reply to OFPMP_TABLE request.*/

struct ofp_table_stats {

uint8_t table_id；/* Identifier of table.

Lower numbered tables are consulted first.*/

uint8_t pad [3]；/* Align to 32-bits.*/

uint32_t active_count；/* Number of active entries.*/

uint64_t lookup_count；

/* Number of packets looked up in table.*/

uint64_t lookup_count；

/* Number of packets looked up in table.*/

uint64_t matched_count；

/* Number of packets that hit table.*/

}；

OFP_ASSERT（sizeof（struct ofp_table_stats）== 24）；

active_count字段指示单个流表中活跃的流表项数，累加所有流表的active_count字段值，可以得到整个交换机当前占用流表项数$ \mathrm{e}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{y}\_\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t} $。

因此，TCAM使用率是当前占用流表项数与最大流表项数的比值，如式（8）所示：

$ {U}_{\mathrm{T}\mathrm{C}\mathrm{A}\mathrm{M}}=\frac{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{y}\_\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}}{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{y}\_\mathrm{v}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{m}\mathrm{n}} $

(8)

OpenFlow交换机在线获取测量节点的负载后，需要进一步判断该节点的状态是否异常。假设负载阈值δ=0.8，若式（6）计算的负载大于δ，该测量节点不适合下发测量任务，添加到loads后，等待过载处理模块筛选并替换。

2.3.2 基于NS的过载处理机制

测量点过载处理规则的相关假设是在短时间内网络拓扑不会发生大规模变化，并且负载主要发生在测量节点。随着网络测量持续运行，测量节点可能出现过载现象，需要重新执行ACO算法等。然而全局搜索算法将耗费大量资源，同时时间开销较大。NS策略在初始解的基础上执行添加、删除和交换等操作，以获取最优解。NS策略存在平衡测量资源和时间的可能，应用在最小顶点覆盖模型时，还可以兼顾链路覆盖率。

如果2个过载测量点由一条边连接，则定义这种边为过载边。过载节点可以集中替换的节点取决于过载边的统计结果，如果没有过载边，则替换整个过载节点集；否则不断筛选覆盖最多过载边的负载异常的测量节点，删除已覆盖过载边，直到删除完全，过载节点集中的剩余节点作为替换节点。

链路覆盖率维持的关键是NS策略的替换过程。基于网络拓扑图构造每个替换测量点的邻域，即所有邻接点构成的集合，若某个邻接点不在selects中，则将其添加到初始测量集。整个邻域遍历结束后，从初始测量集删除对应替换测量点。替换过程结束，selects还需要进一步处理。

冗余覆盖检验的目的在于降低模型结果的链路的冗余度。如果selects中每个测量点邻域被包含在更新的初始测量集中，说明该测量点与所有邻接点间的边被重复覆盖，直接将该测量点从初始测量集中删除，在不影响链路覆盖率的情况下，能够降低模型结果的冗余度，从而优化测量集。

测量点过载处理后的updates包含最少数量的过载测量点，算法1是邻域搜索策略的伪代码。

算法1  邻域搜索策略

输入  $ \mathrm{g}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{h} $，$ \mathrm{s}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{s} $，$ \mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}\mathrm{s} $

输出  $ \mathrm{u}\mathrm{p}\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d}\mathrm{s} $

1.假设基于过载边信息筛选出m个替换测量点。

2.初始化$ \mathrm{i}=1 $。

3.基于$ \mathrm{g}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{h} $构造替换测量点$ \mathrm{i} $的邻域。

4.遍历替换测量点$ \mathrm{i} $的邻域，若邻接点不属于初始测量集，则将其添加到$ \mathrm{s}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{s} $。

5.将替换测量点$ \mathrm{i} $从$ \mathrm{s}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{s} $中删除。

6.令$ \mathrm{i}=\mathrm{i}+1 $。

7.如果条件$ \mathrm{i} > \mathrm{m} $不成立，返回步骤3；否则停止循环。

8.更新的$ \mathrm{s}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{s} $进行冗余覆盖校验，原理优化测量集。

算法1的原理是1个双层循环结构（步骤2~7），外层循环控制当前访问的替换测量点，而内层循环遍历该替换测量点的邻域，除selects以外的邻接点被添加到初始测量集，遍历结束，再删除该替换测量点。假设n表示替换测量点的数目，根据分析可得，算法的时间复杂度是O（n²），由于需要记录每个替换测量点的邻接点信息，算法的空间复杂度也是O（n²）。

3 实验与分析

本节从实验设置、规则优化效果和仿真拓扑验证3个方面对SDN中基于蚁群优化的网络测量节点选择算法进行评估。

3.1 实验环境与基本参数

3.60 GHz、16 GB RAM的4核Windows 10主机作为硬件环境，SDN平台基于Ubuntu16.04系统搭建，使用开源控制器Ryu-4.32，拓扑仿真器采用Mininet-2.3.0d6，软件交换机为Open vSwitch-2.11.0，算法相关模块由Python语言实现。

算法输入的3种无向图参数信息如表 2所示，最小测量数是无向图可以部署测量节点的最少数量。

ACO算法的参数空间比较复杂，参数取值与算法的验证结果相关，通过参考文献或简单实验确定算法的参数，如表 3所示。其中：iterate表示算法最大迭代次数；verge表示算法的收敛条件，即模型解长度不再减少的连续迭代次数；符号|V|表示无向图的顶点数，算法中蚂蚁数量随无向图规模发生变化。

3.2 算法规则的优化效果 3.2.1 实验与数据对比

在算法执行过程中，平均测量数是指多个测量节点数的均值，命中频数是命中对应最小测量数的次数，两者决定算法的准确性。平均迭代次数是多次执行迭代次数的均值，与算法收敛性相关。

第1组对比实验用于验证新候选集定义对于ACO算法准确性的改进效果，在基本参数保持一致的条件下，本文采用新候选集定义和原始候选集定义的ACO算法在无向图karate、jazz和email中进行平均测量数、命中频数和平均迭代数对比，各执行10次，结果如表 4所示。

第2组对比实验用于验证信息素局部增强-全局挥发规则对ACO算法收敛性的优化效果，同理保持基本参数一致，本文采用信息素局部增强-全局挥发规则和MMAS更新规则的ACO算法分别在karate、jazz和email中执行10次，同样将第2组对比实验数据的结果统计到表 4。

从表 4可以看出，对比ACO算法中的典型策略，新候选集定义一定程度上提高了抽象模型的准确性，而信息素局部增强-全局挥发规则主要优化抽象模型的收敛性。过载处理机制执行的前提是无向图的初始测量集，为了保证实验环境相同，第3组对比实验采用改进ACO算法获取初始测量集。基本负载处理机制将负载作为概率状态转移规则的决策因素之一。第3组对比实验中过载节点随机产生，基本负载处理机制与测量点过载处理机制在3种无向图中各执行10次，主要用于验证过载处理机制对时间的优化效果。

图 3分别记录2种负载处理机制在无向图karate、jazz和email运行的测量节点数和运行时间。num_aco、num_ns分别表示基本负载处理和测量点过载处理机制的测量节点数；time_aco、time_ns分别为采用2种机制的运行时间，由于jazz和email图下两种负载处理机制的运行时间差别很大，因此图 3（b）和图 3（c）中time_ns指标非常接近于横坐标。

3.2.2 数据分析与结果

本文定义3种衡量算法的指标：准确性为命中频数的平均数；收敛性是收敛条件与平均迭代数的比值；单位时间开销是平均运行时间与无向图顶点数的比值。

对于表 4中的统计数据，尽管无向图规模不同，新候选集定义的平均测量数、平均迭代次数均小于或等于原始候选集定义，且命中频数较大，结果更接近无向图的最小测量数。相比MMAS更新策略，虽然信息素局部增强-全局挥发规则增加了平均测量数，但是大幅降低了平均迭代数，在无向图email中更为明显。从图 4可以看出，测量点过载处理机制与基本负载处理机制的测量节点数比较接近，但是测量点过载处理机制的运行时间具有2~3个数量级的优势，并且随着无向图顶点数增多而增大，其原因为将负载因素引入概率转移状态规则中，破坏信息素和启发信息的指导作用，增加了算法的运行时间。

因此，新候选集定义显著提高了ACO算法的准确性，信息素局部增强-全局挥发规则集中改进了收敛性，而测量点过载处理机制主要降低了算法的单位时间开销。若考虑3种规则在准确性、收敛性及单位时间开销的精确效果，ACO算法与ACO-NS算法的性能指标对比如表 5所示。

从表 5可以看出，相比ACO算法，ACO-NS算法的准确度和收敛度分别提高了56.7和28.2个百分点，且在单位时间开销方面降低了79.8个百分点。

3.3 SDN网络中不同测量节点选择方案

本节在SDN环境中使用Mininet工具模拟欧洲光纤网核心拓扑，如图 4所示。

为评估单个中心测量点、基于扩展中心性的多个测量点、ACO-NS算法和全部节点4种方案的覆盖率和冗余度，本文定义链路的覆盖率和冗余度。覆盖率是指所选测量点覆盖的链路占全部链路的比率，冗余度是指测量节点重复覆盖的链路数量。

仿真的欧洲光纤网核心拓扑包括16个节点、23条链路。假设单个中心测量点选择度最大的节点，即single={6}，扩展中心性方案的测量点集合extend={11，6，7，4，3，1}，ACO-NS算法的测量点集合aco_ns={6，4，2，8，10，14，16，12}，全部节点方案all包含该网络拓扑中所有节点。

不同方案的覆盖率和冗余度如图 5所示。single方案的覆盖率和冗余度都是最低的，但是网络测量更关注覆盖率，因此single方案应用效果最差。虽然aco_ns和all这2种方案的覆盖率均达到100%，但是all方案的冗余度过高，流量重复采集的概率较大。extend方案能够以较低的冗余度实现较高的覆盖率，但仍存在优化的空间，aco_ns方案的冗余度和覆盖率均优于extend方案。因此，ACO-NS算法在基于网络拓扑的SDN场景下选择测量节点的性能最佳。

4 结束语

本文提出一种基于蚁群优化的网络测量节点选择算法ACO-NS，利用CPU吞吐率和三态内容寻址存储器在线监测测量交换机的负载，为SDN环境中网络测量节点选择提供理论依据，通过优化概率状态转移规则和信息素更新规则，提高测量集的收敛度，同时仅对过载的测量交换机进行邻域搜索，有效缩短调整负载的时间。实验结果表明，相比ACO算法，ACO-NS算法的准确度提高了56.7个百分点，单位时间开销降低79.8个百分点，能够有效提高SDN控制器的工作效率，从而降低负载对网络测量结果的影响。后续将基于不同网络拓扑结构分析测量点选择与流长分布估计的关系，进一步优化算法设计。