高可靠性无线网络拓扑设计范文

摘要：

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

关键词：

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

引言

无线网络中的大部分节点由能量可靠的电池供电，且往往分布于恶劣的环境之中，因此节点容易损坏，导致产生惩罚性成本，因此可靠性是无线网络的一个重要性能指标[1]。已有的可靠性研究分为容错性分析与容错性设计两种[2]。文献[3⁃5]分别使用遗传算法、模拟退火算法以及动态编码算法提出了性能较好的可靠性网络设计方案。上述算法中，遗传算法的优化效果较好，但其学量的样本，计算效率较低。本文首先对网络样本进行模式挖掘，然后使用挖掘的关联规则引导遗传算法进行变异与交叉等遗传操作，并完成整个演化过程，提高了遗传算法的收敛速度与优化效果。

1问题模型

本文使用一个无向图UG(N,A)表示无线网络，节点间的传输速度设为t，网络中的节点与链接基于可靠性指数设置。可靠性指数（在0~1之间）表示节点或链接无错操作的概率。若某个链接失败，数据流将被引导至另一个链接，从而导致了传输延迟；若所有可行路径均失败，则产生一个会话失败。上述延迟与失败定义为惩罚性延迟成本与丢失成本。无线网络拓扑的设计则需要考虑选择最优拓扑以及对节点与链接的可靠性指数分配，从而最小化惩罚性成本。目标函数是延迟与传输丢失的总成本，同时也表示了网络的性能。式（2）是可靠指数分配的预算限制，可靠节点设置越多，成本越高，如式（3），式（4）所示。式（5），式（6）两式表示节点与链接的可靠指数分配决定了网络的传输延迟与丢失。7）例如：假设网络有20个节点，将5个等级的可靠指数分配给节点与路径，则共有6.73×10161个设计方案。因此，其计算复杂度较高，对于大型网络不具备可行性。

2网络可靠性度量

本文采用MonteCarlo模拟器[6]，将网络模拟为图结构，并将节点与链接的故障率设为独立的随机值。模拟器参数与环境的设置如下：（1）根据可靠性指数独立且随机地发生故障；（2）节点与链接的可靠性指数设为4个等级：0.99，0.95，0.9，0.85；（3）将节点⁃节点的会话称为流量；（4）考虑两个惩罚性成本：延迟成本与会话丢失成本；（5）网络图为无向图结构。

3本文算法

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

首先，本文采用Apriori算法[7]提取模拟器数据的关联规则。本文采用文献[6]的图结构变换，该方案对网络顶点排序组成邻接矩阵Xk，然后将矩阵映射为一维向量（对角元素表示节点的可靠指数，其他元素则反映了链接的可靠指数）。然后使用Apriori算法搜索网络结构编码的关联规则，算法的伪代码如算法1所示。为了提取有意义的信息与规则，分别对两种样本（高、低性能样本集）进行分类处理，本文将高低性能样本设为95%以上与5%以下。如图1所示，将5%的最低性能分为L⁃组，5%的最高性能分为H⁃组。pattern_code(i)=Rnum×(li-1)+ri（9）式中：Rnum表示可靠指数等级的数量，本文设为5；li表示邻接编码中对应项的位置；ri表示分配给节点或链接的某个可靠指数的数量。图2所示为一个简单的以图表示网络的示例，其中可靠指数分别设为0.85，0.9，0.95，0.99；ri分别设为2，3，4，5。根据式（8），将网络编码为（0.95，0.9，0.95，0.85，0.00，0.85），然后根据式（9），将该网络重新编码为（P4，P8，P14，P17，P21，P27）。

3.2基于关联规则引导的遗传算法

传统遗传算法的主要流程框图如图3所示。其中遗传算法主要包含以下步骤：（1）染色体的编码与表示；（2）遗传操作的实现；（3）适应度函数的实现。使用上文提取的关联规则引导GA的变异与交叉操作。

3.2.1交叉操作

图4所示为交叉操作的一个实例，图4（a）~（d）是4种简单的网络图形式，图4（e）为对应的邻接矩阵，图4（f）表示对应的GA染色体形式。本文使用式（8）（模式挖掘）的编码算法生成染色体，每条染色体中按链接与节点的可靠指数顺序排序。

3.2.2变异操作

本文使用MonteCarlo模拟器计算适应度值，并使用Goldberg算法[]对适应度值进行扩展处理，从而提高GA的效率。基于H⁃组与L⁃组间的关联建立一个变异图。将频繁项的概率定义为可靠选择的概率，对于无频繁项的网络，将各项概率设为相等。H⁃组的选择概率为：H选项选择率=100×[(support×信息影响率)2]（10）式中的信息影响率表示：模式挖掘获得的先验知识对GA的影响程度。降低L⁃组变异的概率为：L项选择率=100×[0.2(support×信息影响率)]（11）若L⁃组与H⁃组中包含同一个可靠指数的项，式（12）则赋予support值高的项更多的选择机会；若support值相等，GA则不会改变选择机会。图5为一个实例，其中前4个染色体项使用相同的信息影响率。HL项选择率=[(H项选择率+L项选择率)2]（12）如图5所示，式（9）编码的第一个项，P1~P5表示其5个可能变异样本，使用式（10）~式（12）计算其中每个项目。最终，保持相应列值的总和在一个机会矩阵中，将每个机会值均分获得变异图。

3.2.3适应度值

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

4仿真实验与结果分析

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

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

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

4.2各算法的收敛速度比较

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

5结语

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

参考文献

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

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

作者：童立君 单位：南昌航空大学