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

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