基于SDN的网络资源选择多目标优化算法

鲍楠，左加阔，胡晗，鲍煦

（1. 南京邮电大学物联网学院，江苏 南京 210023；2. 江苏大学计算机科学与通信工程学院，江苏 镇江 212013）

1 引言

在人类需求和产业发展的共同激励下，人们开始研究开发下一代无线通信网络。新的无线通信技术和应用，如认知无线电、设备到设备（D2D,device-to-device）、5G、物联网等，都成为现阶段各领域的研究热点。新的研究趋势表明下一阶段的无线网络结构在现有基础设施的基础上会发展成为多层、异构、密集的网络结构形式[1]。软件定义网络（SDN, software-defined network）就是这种新提出的网络形式，它通过将控制平台与数据平台分离，提供高效的控制体系结构[2]。在SDN环境中，用户访问、用户接入点、不同的无线接入技术、访问时间等数据，可以通过位于移动运营商或服务器上的SDN控制器（SDNC, SDN controller）获得[3]。这说明SDNC能够智能化和高效化地分配无线电资源[4]。然而多种无线接入技术共存和网络用户的增加可能会导致激烈的网络资源竞争，如何权衡各方利益，增加获取资源的机会，并有效利用网络资源成为需要进一步解决的问题。

传统的资源分配目标是网络总能耗或总容量的最优化[5-7]，或者偏重于用户与网络中一方的资源效用最优化[8-9]。SDN环境中的资源管理研究可以通过负载均衡调整网络资源分配[10]。文献[11]通过优化全网的信噪干扰寻找最优的信道分配，从而提高用户端信噪比，提高接入点的频谱效率。这类资源分配一般是通过降低干扰和通信冲突进行网络资源优化[12-13]。另外，一些群智能算法也被应用于基于 SDN的资源分配问题[14]，例如文献[15]结合遗传算法和粒子群算法得到最优功率分配并最小化系统中断概率。以上研究文献的优化方法和目的都不相同，却都是利用SDN结构获取网络资源状态并通过资源分配算法提高网络效用。但是这些网络模型都没有考虑多种有线或无线接入技术共存的情况，利用SDN统筹全网资源，在最优化全网效用的过程中可能导致较大的个体收益差异。为了体现个体利益在全网资源优化过程中的公平性，本文提出基于SDN的多目标优化资源选择算法。事实上在追求网络效用的过程中，用户与资源供给方之间、不同的资源供给方之间，互相冲突的优化目标会使其各自的资源使其用决策相互影响。同时考察这些决策并优化所有目标，研究SDN环境中资源分配的多目标优化问题，可以在追求多方利益的过程中寻找到权衡点，协调资源使用和用户需求的关系，将多网环境中牺牲个体利益追求全网效用的优化过程转变为追求个体利益并达到全网均衡的结果。

本文在 SDN结构中同时关注用户对资源需求的优化目标和资源供给方对资源使用的优化目标，研究基于 SDN资源选择的多目标优化问题。本文主要工作如下。

1）根据用户期望和预算，资源供给方的效用期望，分别建立用户资源请求优化模型和网络资源效用优化模型。

2）综合考虑用户申请资源的策略和资源供给方使用资源的策略，建立基于 SDN资源选择的多目标优化模型。

3）采用基于参考矢量的多目标优化算法对构建的模型进行求解，并与其他优化算法的结果进行仿真对比。实验结果表明，本文构建的模型可以均衡 SDN资源的多目标优化结果，且基于参考矢量的优化算法相比其他优化算法能够更快地收敛到分布更均匀的非劣解集。

2 优化目标

2.1 用户访问的最优策略

对于一个希望通过网络获得服务的用户来说，QoS（quality of service）始终是一个重要的考虑因素。不同于传统网络只提供单一资源服务，空闲远程无线单元、移动用户甚至虚拟中间商等现在都可以成为网络资源提供者。这意味着用户有更多的机会访问网络，因此，获得混合资源的成本被认为是另一个重要的参考指标。此时用户是否选择网络提供的服务不仅依赖于网络服务的质量，还取决于获取资源要付出的成本。从用户的角度来看，资源的效用需要最大化。用户总是选择提供更多资源并且花费成本更低的网络。用户最佳访问策略建模如下。

其中，xij表示用户所需的资源中来自资源供给方j的资源所占比例；Ri表示用户i需求的资源量占所有用户资源需求量的比例；pij表示用户获取资源的单价；Pi表示用户的总预算；eij表示用户获取资源消耗的单位能量；Ei表示用户i的总能量。

当pij、eij已知时，用户只需要决定从哪个资源供给方获取多少资源来最大化收益，或者说最小化资源请求成本。

2.2 资源供给方的最优策略

从小型资源供应商到传统网络服务提供商，最重视的都是共享闲置资源得到的回报。因此，资源供给方的最优选择策略很简单，即是否允许用户的访问，如何选择用户可以带来更多的回报。资源供给方希望获得更多回报的同时保留更多的可用资源，其优化选择策略模型如下。

其中，yij表示资源供给方j是否会选择用户i，yij=1表示“选择”，否则相反；表示上一轮资源选择后资源供给方j得到的回报。所有共享的资源不能超出资源供给方的资源储备。

3 多目标优化模型

大部分基于 SDN结构的资源管理研究中，都会分开讨论用户或供应商的最优策略，并且在SDN控制器中以全网总资源效用最优为优化目标来分配资源。在此过程中个体利益可能面临差异较大的实现程度，有些个体需求被超量满足，有些个体需求则被拒绝。这些个体需求之间的冲突情况，可以建模为多目标优化问题，求解多目标优化模型可以在 SDN控制器中完成，利用个体间优化目标的冲突性均衡全网资源分配。多目标优化问题可以用数学模型表示，如式（10）～式（12）所示。

其中，x表示M维决策矢量。矢量x中每一个元素都有上下限的约束，由此构成了决策矢量的决策空间。

在本文讨论的网络模型中，每个用户和每个资源供给方都有其各自的优化目标，这些优化目标由 S3模型中的优化目标函数fi（x）表示。用户的优化目标由 S1模型中的优化目标函数表示，决策矢量由S1模型中的决策矢量表示。资源供给方的优化目标由 S2模型中的优化目标函数表示，决策矢量由S2模型中的决策矢量表示。这些优化目标和决策矢量共同构成了基于 SDN的网络选择和资源配置多目标优化问题，用数学模型表示如下。

其中，z∈Rm，zi是每个目标函数fi（z）的决策矢量，每个决策矢量的元素个数为用户个数或资源供给者的个数，将所有决策矢量展开后，约束式（14）等价于约束式（11）。

4 基于参考矢量的SDN资源选择算法

求解多目标优化问题时，通常的解决方法是将多目标优化问题拆分为等价的多个单目标优化子问题，通过求解加权求和的一组单目标优化子问题或者联合求解单目标优化子问题，得到多目标优化问题的最优解[16-19]。因为优化目标之间互相制约，很难找到一个最优矢量z能满足所有最优化目标，但是不难找到一组非劣解，即可行解中不会出现比非劣解集更优的解。所以本文采用文献[20]的参考矢量算法来描述各个目标函数的折中变化过程，如算法1所示。

算法1基于参考矢量的SDN资源选择算法

1）初始化决策矢量集合P0和单位参考矢量集合V0；

2）当迭代次数小于最大迭代次数（即t＜tmax）时；

3）生成当前决策矢量集合Pt的子代矢量集合Qt；

4）将当前决策矢量集合与子代矢量集合Qt合并；

5）根据参考矢量多目标优化算法更新决策矢量集合Pt+1；

6）若有无效解，则对决策矢量进行约束惩罚，用修正解更新决策矢量集合；

7）进入下一轮迭代t=t+1；

8）当迭代次数等于最大迭代次数（即t=tmax）时，迭代结束。

4.1 初始化决策矢量和参考矢量

初始化决策矢量集合P0是一组随机个体的集合，个体数量等于初始化的参考矢量数量Nvector，其中，个体是由用户和资源供给方的策略矢量构成的，即满足式（14）～式（16）。初始化时，用户的策略矢量为每个用户选择不同资源供给方的资源量占用户需求资源量的百分比，取值区间为[0, 1]，定义为

其中，Nsupplier是资源供给方的数量。在每轮的迭代过程中，用户策略中的元素值在[0, 1]之间变化。

资源供给方的策略矢量为选择接受用户接入请求的概率，定义为

其中，Nuser是用户的数量；初始化时，yij=0或1，yij在每轮的迭代过程中会在取值区间[0, 1]中变化，表示资源供给方接受用户概率的变化。在基于SDN的网络环境中，为了保证空闲资源不会被浪费，资源供给方接受用户的总概率必须大于0。

参考矢量vk是一组在第一象限内均匀分布的单位矢量，根据规范单纯形设计法生成[20-22]，如式（21）所示。

4.2 产生子代决策矢量

在当前决策矢量集合中取2个最小适应值函数对应的决策矢量，采用经典的模拟二元交叉[23]和多项式变异的方法生成子代决策矢量[24]。

4.3 基于参考矢量的多目标优化算法

利用参考矢量将目标空间划分为多个子空间，在每个子空间中分别进行最优化资源选择，最终得到多目标优化的非劣解。具体的优化选择过程可以分为3个阶段。

第一阶段：适值函数转换

因为初始化的参考矢量位于第一象限，所以需要将优化目标的适值函数也转换到第一象限。定义适值函数为当前种群中的个体对应的目标函数值集合，可以表示为

转换后的适值函数为

第二阶段：拆分

根据参考矢量将适值函数矢量分区，每个区间内的适值函数矢量对应的决策矢量构成多个子集与相同参考矢量距离最近的适值函数矢量被分到同一个区间。空间中2个矢量的距离关系可以用夹角余弦关系来表示，矢量间的夹角余弦值越大，表示矢量之间越接近。矢量间的夹角余弦可以用式（24）计算。

其中，θt,k1,k2表示转换后的目标函数矢量与参考矢量vt,k2的夹角。

第三阶段：角度惩罚距离计算

在每一个参考矢量关联的子集合中寻找使角度惩罚距离最小的适值函数矢量，并生成新的决策矢量集合。角度惩罚距离可以由式（25）计算[20]。

其中，γvt,k2是参考矢量vt,k2与其他参考矢量之间最小的夹角值，N是适值函数数量，tmax是最大迭代次数，α是调节g（θt,k1,k2）变化速度的参数。

基于参考矢量多目标优化算法的具体过程如算法2所示。

算法2基于参考矢量多目标优化算法

1）当迭代次数小于最大迭代次数（即t＜tmax）时；

2）根据式（22）与式（23）进行适值函数转换；

3）根据式（24）寻找距离每个参考矢量最近的适值函数矢量，并对当前决策矢量集合进行拆分；

4）在每个子集合中根据式（25）与式（26）计算角度惩罚距离dt,k1,k2，找到的优秀个体It,k必须满足

5）新的决策矢量集合由步骤 4）中找到的优秀个体对应的决策矢量组成；

6）进入下一轮迭代t=t+1。

算法2将插入到算法1中的步骤5）。

4.4 处理不规范的非劣解

在对用户和资源供给方调节选择策略的过程中，有些搜索域内可能没有解，或者不适合有解，所以不是每个参考矢量关联的子集合中都至少有一个适值函数矢量。在这种情况下，随机选择一个适值函数矢量，作为新集合中的个体以维持集合的规模，甚至可以在当前迭代轮回中的目标函数适应值范围内，用随机生成新的参考矢量来代替无关联子集合的原参考矢量。

在迭代过程中还有可能出现超出单个目标函数约束的解，比如，用户选择网络资源后需要消耗的能量超出了能量约束门限，或者资源供给方接收用户的概率小于 0。本文设计一种个体约束惩罚算法对超出约束条件的解进行规范管理。S1～S3模型中的约束条件均可以用式（27）与式（28）表示。

其中，zik表示用户或资源供给方的选择策略，即S1模型和 S2 模型中的xij和yij；式（28）表示式（4）、式（5）与式（8）的等价约束条件。

个体约束惩罚算法的基本思想是：若新集合中的元素超出了上下边界值0或1，则新的元素值就取边界值0或1；若新的决策矢量不能满足式（28），则对决策矢量进行约束惩罚，使更新后的个体能够满足约束条件。具体流程如在算法3所示。

算法3个体约束惩罚算法

1）对新集合中的所有个体矢量进行检查

2）若个体元素超出了边界值，则新元素取边界值

3）若个体矢量不能满足式（28），则对其进行约束惩罚

4）更新决策矢量集合

算法3将插入到算法1中的步骤6）。

4.5 算法复杂度

不考虑生成初始集合和初始参考矢量的计算复杂度，根据文献[20]可知，每一轮迭代中最坏情况下算法1的计算复杂度为O（NNp2），其中，N是优化目标的数量，Np是集合大小。

5 资源选择算法性能仿真及结果分析

5.1 仿真场景

本节对基于参考矢量的 SDN资源选择算法进行Matlab仿真分析，假设共有8个用户和2个资源供给方加入SDN资源选择过程，即共有10个优化目标。同时也考察了基于遗传算法的全网效用目标优化算法和基于粒子群多目标优化算法[25]应用于本文网络模型的效果。在基于遗传算法的全网效用目标优化算法中，资源选择的目标是最小化所有参与者的优化目标之和；在基于粒子群多目标优化算法中的资源选择目标和所提算法相似。仿真参数如表1所示。

5.2 各个参与者的优化目标

图1～图3给出了各个优化目标函数值在3种算法的历次迭代过程中的变化情况。图中将各个优化目标的函数值连接起来是为了更好地显示目标函数值的分布情况。如图所示，3种算法中用户间的目标函数值优化结果差别并不明显，资源供给方之间的目标函数值优化结果差别也不大。所提算法和多目标粒子群算法的结果是一组向量集合，遗传算法的结果是一个目标和，把该目标和对应的各个优化目标的函数值也在图中标示出来。在本文所提算法中，因为参考矢量在多维空间中的均匀分布，导致得到的目标函数值分布也较为均匀，多目标粒子群算法得到的目标函数值分布较为集中。由此说明了在逼近优化结果的区间上，本文所提方法可以得到均匀分布性较好的结果，为混合资源分配提供更多选择。

表1 仿真参数

图1 基于参考矢量算法的各目标函数值

图2 基于粒子群算法的各目标函数值

图3 基于遗传算法的各目标函数值

图4比较了3种算法中用户1的目标函数值在每一轮迭代中的变化情况。比较结果说明，本文所提算法得到的结果在解空间分布上更加均匀，在迭代过程中较快地平稳收敛，基于粒子群算法的结果在迭代过程中振荡明显，且分布较为集中，而基于遗传算法的结果收敛效果不理想。因此，所提算法在求解结果的均匀分布性和收敛性方面表现较好。

图4 用户1的目标函数值变化情况

5.3 用户接入率

用户接入率主要体现用户每次选择资源供给方后成功接入网络资源的概率，其计算式如式（29）所示。

因为不能保证所有用户的需求都得到满足，所以图5～图7中不是所有用户的接入率都能达到1。由于网络资源的匹配是在基于SDN的网络环境下，因此可以通过集中调控避免单个优化目标的贪婪收益，有可用资源的资源供给方不能拒绝所有用户的接入请求，用户的接入率至少都大于0。虽然图5中的用户接入率不是最高的，但是大部分会较快集中在0.5附近，而图6和图7中的数值则比较分散。

图5 基于参考矢量算法的用户接入率

图6 基于粒子群算法的用户接入率

图7 基于遗传算法的用户接入率

5.4 资源请求的接受率

资源请求的接受率主要体现资源供给方接受一个用户接入网络资源的概率。为了保证不浪费可用网络资源，资源请求的接受率必须大于 0，计算式如式（30）所示。

从图8～图10可以看出，3种算法的资源请求的接受率都在0.5左右，差别不大。图9中基于粒子群算法的资源请求接受率稍微高一点，图8中基于参考矢量算法的资源请求接受率最快收敛到最优解区域，且2个资源供给方之间差异度较小。

图8 基于参考矢量算法的资源请求接受率

图9 基于粒子群算法的资源请求接受率

图10 基于遗传算法的资源请求接受率

5.5 资源匹配度

资源配置指标主要体现用户的 QoS需求和实际获取资源时得到的QoS之间的相似度，相似度高表明获取的资源能够贴近用户的QoS需求，从而体现基于 SDN的资源配置优势，即为用户定制贴合QoS需求的资源，而不会浪费宝贵的网络资源。资源匹配度MDi可用式（31）表示。

其中，Qask表示用户的QoS需求，Qget表示实际得到的QoS服务，Q={资源量，价格}。

本文研究 SDN环境中的资源选择多目标优化问题，主要是为了利用网络中空闲的资源来满足不同用户需求，期望实现如下目标：1）用户 QoS得到一定程度的满足；2）不浪费空闲网络资源；3）通过定制化的资源匹配将资源和需求有效地结合起来。考查资源选择匹配度可以分析出算法是否达到了期望目标。图11～图13显示出大部分用户的匹配度都逼近1，说明用户申请资源的各项期望指标（这里仅仿真了资源量和花费代价）与实际获取资源的各项指标都比较接近。其中，基于参考矢量的算法和基于粒子群的算法得到的资源匹配度要好于基于遗传算法的结果。从数据点的分布来看，基于参考矢量的算法数据更快地集中于一个小区间，并且匹配度都逼近 1，而基于粒子群算法的数据更多，且分布在一个较大的区间内。

图11 基于参考矢量算法的资源匹配度

6 结束语

本文通过考虑用户申请资源决策和网络提供资源决策的相互影响，首先建立了基于 SDN资源选择多目标优化模型，然后在此模型基础上提出了基于参考矢量的SDN资源选择优化算法，

图12 基于粒子群算法的资源匹配度

图13 基于遗传算法的资源匹配度

在仿真中进一步与基于遗传算法的全网效用目标优化算法和基于多目标粒子群优化的资源选择算法进行比较分析。仿真结果表明，所提算法与其他 2种算法相比，各个优化目标的性能指标值集中在一个较小的区间内，而且优化目标之间的差异性较小，优化目标值分布均匀，说明本文提出的算法收敛速度更快、非劣解的均匀分布性更好。基于SDN的网络资源选择多目标优化模型经过合适的算法设计，可以通过定制化的资源匹配方式，为用户选择资源、为网络分配用户，在不浪费网络空闲资源的前提下可以在一定程度上满足不同用户的QoS需求。