童立君

摘 要： 无线网络中的节点与路径故障会产生惩罚性网络成本，该成本是无线网络的一个重要性能指标，对此提出了一种基于关联规则引导遗传算法的高可靠性无线网络拓扑设计算法。首先，采用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，]网络中的节点与链接基于可靠性指数设置。……