基于关联规则引导遗传算法的高可靠性无线网络拓扑设计

童立君

摘 要： 无线网络中的节点与路径故障会产生惩罚性网络成本，该成本是无线网络的一个重要性能指标，对此提出了一种基于关联规则引导遗传算法的高可靠性无线网络拓扑设计算法。首先，采用Monte Carlo模拟器将网络模拟为图结构；然后，采用Apriori算法提取模拟器数据的关联规则；最后，利用提取的关联规则引导遗传算法的变异与交叉操作，搜索最优的网络拓扑结构。仿真实验结果表明，对于多个网络规模，该算法均可获得较好的网络性能与收敛速度，具有较好的实用性。

关键词： 关联规则； 遗传算法； 无线网络拓扑； 演化算法； 收敛速度

中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2016）07?0015?04

Abstract： The nodes and route failure in wireless network may result in the punitive network cost， which is an important performance index of the wireless network. A design algorithm of high reliability wireless network topology based on association rules guiding genetic algorithm is proposed to avoid the cost. The Monte Carlo simulator is used to simulate the network as the graph structure， and then Apriori algorithm is used to extract the association rules of the simulator data， finally the extracted association rules are used to guide the mutation and crossover operation of the genetic algorithm， and search the optimal network topology structure. The simulation experiment results show that the proposed algorithm can obtain perfect network performance and convergence rate for multi?network scale， and has good practicability.

Keywords： association rule； genetic algorithm； wireless network topology； evolutionary algorithm； convergence rate

0 引 言

无线网络中的大部分节点由能量可靠的电池供电，且往往分布于恶劣的环境之中，因此节点容易损坏，导致产生惩罚性成本，因此可靠性是无线网络的一个重要性能指标[1]。已有的可靠性研究分为容错性分析与容错性设计两种[2]。文献[3?5]分别使用遗传算法、模拟退火算法以及动态编码算法提出了性能较好的可靠性网络设计方案。上述算法中，遗传算法的优化效果较好，但其学习大量的样本，计算效率较低。

本文首先对网络样本进行模式挖掘，然后使用挖掘的关联规则引导遗传算法进行变异与交叉等遗传操作，并完成整个演化过程，提高了遗传算法的收敛速度与优化效果。

1 问题模型

本文使用一个无向图[UG（N，A）]表示无线网络，节点间的传输速度设为[t，]网络中的节点与链接基于可靠性指数设置。可靠性指数（在0～1之间）表示节点或链接无错操作的概率。若某个链接失败，数据流将被引导至另一个链接，从而导致了传输延迟；若所有可行路径均失败，则产生一个会话失败。上述延迟与失败定义为惩罚性延迟成本与丢失成本。无线网络拓扑的设计则需要考虑选择最优拓扑以及对节点与链接的可靠性指数分配，从而最小化惩罚性成本。

例如：假设网络有20个节点，将5个等级的可靠指数分配给节点与路径，则共有6.73×10161个设计方案。因此，其计算复杂度较高，对于大型网络不具备可行性。

2 网络可靠性度量

本文采用Monte Carlo模拟器[6]，将网络模拟为图结构，并将节点与链接的故障率设为独立的随机值。模拟器参数与环境的设置如下：

（1） 根据可靠性指数独立且随机地发生故障；

（2） 节点与链接的可靠性指数设为4个等级：0.99，0.95，0.9，0.85；

（3） 将节点?节点的会话称为流量；

（4） 考虑两个惩罚性成本：延迟成本与会话丢失成本；

（5） 网络图为无向图结构。

3 本文算法

3.1 对模拟器数据进行模式挖掘

首先，本文采用Apriori算法[7]提取模拟器数据的关联规则。本文采用文献[6]的图结构变换，该方案对网络顶点排序组成邻接矩阵[Xk，]然后将矩阵映射为一维向量（对角元素表示节点的可靠指数，其他元素则反映了链接的可靠指数）。

3.2.3 适应度值

样本的模式与H?组中挖掘的模式接近，则被选择的概率较高；而样本模式与L?组中挖掘的模式接近，则被选择的概率较低。由于模式的效果可能随着网络尺寸（n）的增加而降低，则通过增加一个乘数[（1n）]来计算。因此，包含优秀模式样本的适应度值将提高，如式（13）；反之，包含较弱模式的适应度值将随着迭代而降低。[新适应度=旧适应度+support×信息影响率×（1n）]（13）[新适应度=旧适应度-support×信息影响率×（1n）] （14）

4 仿真实验与结果分析

将本文遗传算法与传统GA以及模拟退火算法进行对比实验，网络节点数量分别设为（50，100，200，500，800，1 000）。表1所示为5个等级的可靠性指数对应的成本，本实验的关联规则基于1%最高、最低样本的模式挖掘所得。

4.1 各算法的网络性能优化效果比较

将网络的惩罚性成本作为无线网络的性能指标。图6所示为对比实验的结果统计，模拟退火算法的性能最低，而传统遗传算法的性能优于模拟退火算法，可以看出遗传算法的全局优化性能明显优于模拟退火算法。而本文基于关联规则引导的遗传算法获得的结果则优于基本遗传算法，可以看出本文算法效果明显。原因在于：本文对样本进行模式挖掘，获得了最优与最弱样本集，然后使用遗传算法搜索最优解，提高了对精英样本的局部提炼效果，获得了优于传统遗传算法的性能。

4.2 各算法的收敛速度比较

图7所示为三种算法收敛所需的代数统计，模拟退火算法的收敛速度最快，而基本遗传算法的收敛速度最慢，原因在于：本文首先对样本的精英子集与弱样本子集进行模式挖掘，然后以挖掘的关联规则引导遗传算法演化，提高了演化的效率。虽然模拟退火算法的收敛速度最快，但其优化效果较差。而本文算法在性能的优化效果与收敛速度上均优于传统的遗传算法。

5 结 语

本文针对无线网络的可靠性拓扑设计问题，提出了一种基于模式挖掘引导遗传算法的可靠拓扑设计方案。首先采用Monte Carlo模拟器将网络模拟为图结构，然后采用Apriori算法提取模拟器数据的关联规则，最终利用提取的关联规则引导遗传算法的变异与交叉操作，获得了较好的网络性能与收敛速度，具有较好的实用性。同时本文优化算法具有普遍适用性，可以应用于无线传感器网络、无线自组织网络等。

参考文献

[1] 朱晓娟，陆阳，邱述威，等.无线传感器网络数据传输可靠性研究综述[J].计算机科学，2013，40（9）：1?7.

[2] 李峰，赵海兴，徐宗本.构建一类新网络簇的可靠性控制集[J].计算机学报，2013，36（6）：1246?1253.

[3] RUI M M， PAVAN C， PINTO A N， et al. Genetic algorithm for the topological design of survivable optical transport networks [J]. Journal of optical communications and networking， 2011， 3（1）： 17?26.

[4] RODRIGUEZ D A， OTEIZA P P， BRIGNOLE N B. Simulated annealing optimization for hydrocarbon pipeline networks [J]. Industrial and engineering chemistry research， 2013， 52（25）： 8579?8588.

[5] ELSHQEIRAT B， SOH S， RAI S， et al. A dynamic programming algorithm for reliable network design [J]. IEEE transactions on reliability， 2014， 63（2）： 443?454.

[6] HUANG S M， WU Q， TSAI S C. A Monte Carlo method for estimating the extended all?terminal reliability [C]// Proceedings of the Fourth International Conference on Networking and Services. [S.l.]： IEEE， 2008： 122?127.

[7] HAN J， KAMBER M. Data mining： concepts and techniques， third edition [J]. Data mining concepts models methods and algorithms second edition， 2011， 29（S1）： 1?18.