改进MOEA/ D算法的异构网络接入控制

刘艳君，牛丽平

(1.新乡学院 计算机与信息工程学院，河南 新乡 453003；2.河南师范大学 计算机与信息工程学院，河南 新乡 453007)

0 引 言

接入控制单元是无线异构网络的核心，当多模终端用户有业务需要接入网络时，会对当前网络的资源进行分析，并将其合理地分配到最适合的网络中，在保证用户接入体验的同时，充分利用整个网络资源[1-3]。目前，对异构网络的接入控制研究已经取得了一定的成果，文献[4]将NSGA-Ⅱ算法应用在异构网络多业务接入控制中，优化了用户的传输速率和网络负载均衡，但没有考虑网络阻塞的影响，所以始终无法让异构网络的资源得到充分利用；文献[5]利用高斯与戒上型组合隶属函数对多目标进行模糊处理，再转化为单目标问题后求出最优解，取得了不错的效果。由于在异构网络中的资源占用、阻塞率和负载均衡这3个方面相互冲突和制约，不能同时达到最优，属于多目标优化问题[6-8]。基于分解的多目标进化算法MOEA/D算法在解决多目标优化问题的优越性，关于MOEA/D算法的改进，学者们也提出了很多策略，如：文献[9]引入了惩罚机制建立了双层优化模型，利用改进的多目标优化算法求解出了惩罚期望后悔度的帕累托前沿，但该方法对惩罚系数的控制较难；文献[10]采用了动态惩罚参数的方法来调节候选解区域，避免边界个体的遗失问题，但在求解的过程中还会经常出现搜索区域不全面的问题；文献[11]通过在超平面生成初始权重向量的方式，不仅使解集的分布更加均匀，而且还降低了计算量，但仍有提升的空间。本文在MOEA/D的基础上，对其采取了进一步的改进策略，大幅提升了算法的性能，并将其应用在异构无线网络的接入控制中，分别对资源占用、阻塞率和负载均衡3个目标进行优化，能够更好地充分利用网络资源，解决异构网络的业务接入控制问题。

1 建立异构无线网络数学模型

异构网络的业务接入控制需要全局考虑不同网络和不同终端的各种因素，本文对正交频分复用(OFDM)技术的异构无线网络接入控制进行研究。假设在异构无线网络系统中，存在m个不同类型的网络，第j(1≤j≤m) 个网络的子载波数为Nj，每个子信道中有Fj个子载波，通过TRU的模型能够计算出第j个网络可用的TRU总数Tj表示如下

(1)

其中，TLj表示数据帧的长度；Sj和TSj分别表示OFDM的符号数量和符号周期。

若有n个业务等待接入网络，其中第i(1≤i≤n) 个业务接入第j个网络的状态表示为xij，接入成功xij=1，反之，未接入xij=0。实际上，本文最终求得的最优解形式是一个n×m的0/1矩阵X。

当业务i接入网络j时，设所需的TRU数为tij，首先将业务i优先分配到距离基站较近和发射功率较大的网络j，可以占用较少的网络资源，这样不仅可以降低整个网络的负载率，还能够保证更多的剩余网络资源[12,13]。业务占用最小网络资源的优化目标函数表示如下

(2)

为了避免网络资源的不合理配置，使系统中各网络的负载达到均衡，本文采用负载率方差对网络的负载分布情况进行描述，负载率方差越小，则说明网络负载越均衡，故将负载率方差作为最小优化目标函数，表达式描述如下

(3)

其中，η(j)为当业务i接入网络j后，已用TRU数占整个网络TRU总数的比，具体可描述为

(4)

其中，Bj表示业务i接入网络前已占用的TRU网络资源数量。

为了给用户提供更稳定和可靠的服务，提高业务接入网络的成功率，将最小阻塞率作为优化目标函数，表达式描述如下

(5)

另外，业务所需资源不应大于整个网络提供的资源总数。同时，每个业务实际上仅可以接入一个网络，所以可产生两个约束条件

(6)

(7)

通过上述分析可知，如果以业务占用最小的资源为优化目标，会优先接入距离较近的基站，从而出现不同网络负载不均衡的问题，持续接入业务后还会出现个别网络阻塞的现象，拒绝业务的接入，严重影响用户的体验。如果以网路负载平衡为最小优化目标，业务会优先接入已使用资源最少的网络，但可能会以消耗更多的TRU资源数为代价，从而影响整个网络的容量，当业务持续增加后，依然会提前出现网络阻塞的情况[14]。为此，本文将3个最小优化目标函数结合两个约束条件进行组合，转化成多目标优化模型，利用改进的MOEA/D算法进行求解，得到最优的业务接入控制方案。

2 MOEA/D算法及其改进策略

传统MOEA/D算法的思路是将多目标问题转化为多个单目标子问题进行求解，较其它常见智能算法在收敛性和复杂度方面均有了明显的改善，但是也仍然存在一些不足，如：给权重向量随机分配个体容易导致种群多样性和收敛性下降。另外，固定的邻域值不仅会使收敛速度放缓，而且还会影响算法的全局和局部搜索能力[15,16]。针对这两个方面的缺陷，给出改进策略。

2.1 权重向量与个体的匹配优化

在传统MOEA/D算法求解的初期，会为权重向量λ随机分配个体，而这种随机分配的方法可能会导致将某个权重向量临近的最优解分配给较远的权重向量，从而使该权重向量下的适应度变差，所以会出现该个体被其它个体替代的情况，进而使种群的多样性和收敛性下降。给权重向量λi随机分配个体的过程如图1所示。

图1 给权重向量随机分配个体过程

从图1中可看出，在随机分配的方式下，距离权重向量λ2较近的个体B可能会分配给λ3，而个体C则可能分配给λ2。然后，在随后的进化过程中，距离权重向量λ3更近的个体F会取代B，距离权重向量λ2更近的个体G会替代C，但实际上B的Pareto支配G，C的Pareto支配F，即B和C的Pareto要比F和G更优，故这种随机的分配方式会导致算法多样性和收敛性下降。同时，随着种群的不断进化，这个最优解还有被丢弃的可能，从而影响算法的收敛性精度。为此，本文提出了权重向量与个体匹配优化的方法，使权重向量选择最优解，计算权重向量和所有个体的偏差Δλ，表达式如下

(8)

(9)

其中，F′(X)=(f′1(X),f′2(X),…,f′i(X),…,f′m(X))。f′i(X) 则表示如下

(10)

综上所述，如果在多个权重向量选取同一个个体X的情况下，把该个体X匹配给ΔX最小的权重向量，通过权重向量与个体的匹配优化，可以形成两者的最佳对应关系，不仅维持了种群的多样性，而且还能利于获得均匀分布的Pareto最优解。

2.2 自适应邻域

在MOEA/D算法中使用权重向量间的欧式距离定义了个体间邻域，所以邻域值是固定的，但这样会影响到种群的进化。在进化的前期，应尽量用优良的个体对更多劣质的个体进行替换，需要较大的邻域加快算法的收敛速度，而到了进化的后期，需要适当减小邻域值，来维持种群的多样性和提升局部搜索能力。实际上，相邻个体间存在着共同的基因，通过这种内在关联能够促进种群的进化，使优良的基因得到保留。根据种群所处的进化阶段和分布情况，本文提出了一种自适应动态调节的邻域，具体描述如下

(11)

式中：t表示当前的迭代次数；tmax表示设置的最大迭代次数；μ为比例系数；β为比例调整参数；fav表示种群的平均适应度值；fmax则表示最大适应度值。

在进化的前期，由于迭代次数t值较小，邻域值T能够保持较大值，突出全局搜索能力；随着迭代次数t的增加，到了进化的后期，邻域值T逐渐减小，又突出了算法的局部搜索能力。另外，从适应度值的角度看，如果适应度值分布较均匀，那么个体间的差异就明显，种群表现出多样性，此时平均适应度值距离最大值较远，即arcsin(fav/fmax) 会更趋近于0，邻域T会被动态增大，就相应提升了算法收敛性。相反，如果适应度值分布较集中，个体间的差异就不大，即arcsin(fav/fmax) 会更趋近于1，邻域T就会被动态减小，来保持种群的多样性。

3 改进算法性能测试与对比

为了验证本文提出的改进算法的性能，利用通用的2目标测试函数ZDT1-ZDT4和3目标测试函数DTLZ1-DTLZ4进行仿真验证，并分别与标准MOEA/D算法、文献[10]中的MOEA/D-DPS和文献[11]中的MOAC/DE算法进行比较。通过反向世代距离[17,18](inverted generation distance，IGD)指标对不同算法运算得到结果进行比较和分析。IGD均值和标准差越小，对应算法的收敛性、分布性和稳定性就越优。

传统MOEA/D算法的参数：采用模拟二进制交叉，ηc=25，交叉率为1，邻域值T=15。本文提出的改进算法的参数：比例系数μ为0.5，比例调整参数β为45。设置种群大小为150，最大迭代次数tmax为300。在8个测试函数上分别运行50次，求得对应算法的IGD均值和标准差见表1。

从表1中的运行结果可看出：本文提出的改进算法在8个测试函数上求得的IGD均值均优于传统MOEA/D算法、MOEA/D-DPS算法、MOAC/DE算法，收敛性和分布性两个方面均得到了明显的提升。同时，也得到了最优的IGD标准差，也说明了改进算法具有更佳的稳定性，从而验证了改进策略的有效性和优越性。

表1 不同算法运行得到的IGD均值和标准差

4 仿真结果与分析

4.1 仿真环境参数设置

为了验证本文提出的改进算法在处理异构无线网络接入控制的效果，选择较为常见的无线网络TD-LTE、WiMax和LTE-FDD构成仿真网络模型。仿真网络模型如图2所示。

图2 仿真网络模型

实验运行的硬件平台配置为：Intel Core i7的CPU，主频率2.8 GHz；8 GB的内存，操作系统采用的是64位的Windows 7，在Matlab 2012a的环境中进行仿真，无线网络的参数见表2。

表2 3种无线网络的参数

4.2 仿真结果与对比分析

仿真环境搭建完毕后，预设100个业务，利用本文提出的改进算法求解异构网络接入控制的多目标优化问题。每当有新业务接入时，通过运算都能够得到一系列的最优解集，每个解均代表着一种接入方案。为了直观展示，当接入的业务数量为80个时，最优解集在目标空间的Pareto前沿分布如图3所示。

图3 本文改进算法求解得到的Pareto前沿分布(n=80)

从图3的结果可看出：每个点均代表着多目标优化问题的一个最优解，实际上是0/1矩阵，每个业务与接入网络的对应关系。每个解在占用TRU资源、阻塞率和负载均衡3个目标函数上表现出了不同的优势，从这些解中选择一个兼顾三者的折中方案，并将其应用到仿真环境中，对新接入异构网络的业务进行控制，并分别与文献[4]中的NSGA-Ⅱ算法、文献[5]中的MOC方法、文献[11]中的MOAC/DE算法得到的结果进行比较，记录接入业务数从50到100的控制过程，在不同算法下业务占用资源TRU总数和业务阻塞率的变化情况，得到的曲线如图4、图5所示。

图4 不同算法下业务占用TRU的变化情况

图5 不同算法下业务阻塞率的变化情况

从图4的结果可以看出：随着新业务的不断接入，业务占用TRU总数逐渐攀升，从整体上看，在相同接入业务数量的情况下，本文提出的改进算法占用的资源数均小于其它3种比较算法，使剩余的网络资源能够接入更多的业务，当接入业务数量达到85后，其它方法的网络资源陆续用尽，而在本文方法下当业务数达到95时，仍然有剩余网络资源可接入新业务。

从图5的结果可以看出：在文献[4]中NSGA-Ⅱ算法下，当新业务接入数量达到75个时，就开始出现了业务阻塞的现象，且随着新业务接入的增加阻塞率不断攀升，当接入第100个新业务时，阻塞率达到了18%；在文献[5]中MOC方法下，当新业务接入数量达到80个时，开始出现业务阻塞的现象，当接入第100个新业务时，阻塞率达到了14%；在文献[11]中MOAC/DE算法下，新业务接入数量达到85个时，开始出现业务阻塞的现象，当接入第100个新业务时，阻塞率达到了11%；在本文改进算法下，当新业务接入数量达到90个时，才开始出现业务阻塞的现象，而且当接入第100个新业务时，阻塞率仅为8%。

随着接入业务的增加，在4种不同算法下对3种网络负载进行归一化处理，得到结果如图6所示。其中，3条曲线越紧凑说明网络间的负载越均衡，纵轴的值越小，说明占用的资源越少。

从图6的仿真结果可看出：在新业务不断接入的过程中，3个网络的负载均逐渐攀升，但在本文改进算法下攀升的速度最慢(斜率最小)，说明算法有效控制了网络的总体资源占用率。在文献[4]中的NSGA-Ⅱ算法下，如图6(a)所示，当接入业务数量达到75时，由于LTE-FDD网络资源耗尽，已经开始满载，也正是此时开始出现网络阻塞现象；在文献[5]中的MOC方法下，如图6(b)所示，当接入业务数量达到80时，LTE-FDD也开始出现了满载和阻塞的情况；在文献[11]中的MOAC/DE算法下，如图6(c)所示，当接入业务数量达到85时，WiMax网络出现满载和阻塞情况；而在本文提出的改进算法下，如图6(d)所示，由于对资源占用和网络阻塞的有效控制，当接入业务数量达到90时，WiMax网络才出现了满载和阻塞情况。另外，从负载均衡的方面分析，文献[4]算法下，3种网络的归一化负载间距最大，在文献[5]和文献[11]算法下，归一化负载得到了明显改善，而本文提出的改进算法得到的3种网络的归一化负载曲线一致性最强，说明本文改进算法的求解精度更高、性能更强，在控制异构网络业务接入时，不仅占用最小的网络资源，还具有最小的阻塞率，也有更优的负载均衡控制能力。

图6 4种算法下的归一化负载情况

5 结束语

针对异构无线网络的业务接入问题，本文从资源占用率、阻塞率和负载均衡3个方面进行考虑建立了多目标优化数学模型，引入了复杂度较低的MOEA/D算法，并通过权重向量与个体的匹配进行优化，改善了种群的多样性和解的分布。同时，引入自适应邻域的策略，大大提升了算法的收敛速度和搜索能力。改进的MOEA/D算法在8个标准函数上进行测试，得到的IGD均值和标准差明显优于其它3种比较算法，验证了改进策略的有效性和优越性。将改进的MOEA/D算法应用在异构无线网络的接入控制中进行仿真实验，通过选取折中的解并与其它3种方法在资源占用、阻塞率和负载均衡进行比较，本文改进算法均得到了最优的结果，其中，本文方法在接入业务数为90个时，网络才开始出现阻塞的现象，而其它3种算法出现阻塞时对应的接入业务数分别为75、80和85，说明提出的改进算法能够对网络资源进行更为合理的分配，改善用户对业务接入的体验。