基于關(guān)聯(lián)規(guī)則引導遺傳算法的高可靠性無線網(wǎng)絡拓撲設計

童立君

摘 要： 無線網(wǎng)絡中的節(jié)點與路徑故障會產(chǎn)生懲罰性網(wǎng)絡成本，該成本是無線網(wǎng)絡的一個重要性能指標，對此提出了一種基于關(guān)聯(lián)規(guī)則引導遺傳算法的高可靠性無線網(wǎng)絡拓撲設計算法。首先，采用Monte Carlo模擬器將網(wǎng)絡模擬為圖結(jié)構(gòu)；然后，采用Apriori算法提取模擬器數(shù)據(jù)的關(guān)聯(lián)規(guī)則；最后，利用提取的關(guān)聯(lián)規(guī)則引導遺傳算法的變異與交叉操作，搜索最優(yōu)的網(wǎng)絡拓撲結(jié)構(gòu)。仿真實驗結(jié)果表明，對于多個網(wǎng)絡規(guī)模，該算法均可獲得較好的網(wǎng)絡性能與收斂速度，具有較好的實用性。

關(guān)鍵詞： 關(guān)聯(lián)規(guī)則； 遺傳算法； 無線網(wǎng)絡拓撲； 演化算法； 收斂速度

中圖分類號： 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 引 言

無線網(wǎng)絡中的大部分節(jié)點由能量可靠的電池供電，且往往分布于惡劣的環(huán)境之中，因此節(jié)點容易損壞，導致產(chǎn)生懲罰性成本，因此可靠性是無線網(wǎng)絡的一個重要性能指標[1]。已有的可靠性研究分為容錯性分析與容錯性設計兩種[2]。文獻[3?5]分別使用遺傳算法、模擬退火算法以及動態(tài)編碼算法提出了性能較好的可靠性網(wǎng)絡設計方案。上述算法中，遺傳算法的優(yōu)化效果較好，但其學習大量的樣本，計算效率較低。

本文首先對網(wǎng)絡樣本進行模式挖掘，然后使用挖掘的關(guān)聯(lián)規(guī)則引導遺傳算法進行變異與交叉等遺傳操作，并完成整個演化過程，提高了遺傳算法的收斂速度與優(yōu)化效果。

1 問題模型

本文使用一個無向圖[UG（N，A）]表示無線網(wǎng)絡，節(jié)點間的傳輸速度設為[t，]網(wǎng)絡中的節(jié)點與鏈接基于可靠性指數(shù)設置?？煽啃灾笖?shù)（在0～1之間）表示節(jié)點或鏈接無錯操作的概率。若某個鏈接失敗，數(shù)據(jù)流將被引導至另一個鏈接，從而導致了傳輸延遲；若所有可行路徑均失敗，則產(chǎn)生一個會話失敗。上述延遲與失敗定義為懲罰性延遲成本與丟失成本。無線網(wǎng)絡拓撲的設計則需要考慮選擇最優(yōu)拓撲以及對節(jié)點與鏈接的可靠性指數(shù)分配，從而最小化懲罰性成本。

例如：假設網(wǎng)絡有20個節(jié)點，將5個等級的可靠指數(shù)分配給節(jié)點與路徑，則共有6.73×10161個設計方案。因此，其計算復雜度較高，對于大型網(wǎng)絡不具備可行性。

2 網(wǎng)絡可靠性度量

本文采用Monte Carlo模擬器[6]，將網(wǎng)絡模擬為圖結(jié)構(gòu)，并將節(jié)點與鏈接的故障率設為獨立的隨機值。模擬器參數(shù)與環(huán)境的設置如下：

（1） 根據(jù)可靠性指數(shù)獨立且隨機地發(fā)生故障；

（2） 節(jié)點與鏈接的可靠性指數(shù)設為4個等級：0.99，0.95，0.9，0.85；

（3） 將節(jié)點?節(jié)點的會話稱為流量；

（4） 考慮兩個懲罰性成本：延遲成本與會話丟失成本；

（5） 網(wǎng)絡圖為無向圖結(jié)構(gòu)。

3 本文算法

3.1 對模擬器數(shù)據(jù)進行模式挖掘

首先，本文采用Apriori算法[7]提取模擬器數(shù)據(jù)的關(guān)聯(lián)規(guī)則。本文采用文獻[6]的圖結(jié)構(gòu)變換，該方案對網(wǎng)絡頂點排序組成鄰接矩陣[Xk，]然后將矩陣映射為一維向量（對角元素表示節(jié)點的可靠指數(shù)，其他元素則反映了鏈接的可靠指數(shù)）。

3.2.3 適應度值

樣本的模式與H?組中挖掘的模式接近，則被選擇的概率較高；而樣本模式與L?組中挖掘的模式接近，則被選擇的概率較低。由于模式的效果可能隨著網(wǎng)絡尺寸（n）的增加而降低，則通過增加一個乘數(shù)[（1n）]來計算。因此，包含優(yōu)秀模式樣本的適應度值將提高，如式（13）；反之，包含較弱模式的適應度值將隨著迭代而降低。[新適應度=舊適應度+support×信息影響率×（1n）]（13）[新適應度=舊適應度-support×信息影響率×（1n）] （14）

4 仿真實驗與結(jié)果分析

將本文遺傳算法與傳統(tǒng)GA以及模擬退火算法進行對比實驗，網(wǎng)絡節(jié)點數(shù)量分別設為（50，100，200，500，800，1 000）。表1所示為5個等級的可靠性指數(shù)對應的成本，本實驗的關(guān)聯(lián)規(guī)則基于1%最高、最低樣本的模式挖掘所得。

4.1 各算法的網(wǎng)絡性能優(yōu)化效果比較

將網(wǎng)絡的懲罰性成本作為無線網(wǎng)絡的性能指標。圖6所示為對比實驗的結(jié)果統(tǒng)計，模擬退火算法的性能最低，而傳統(tǒng)遺傳算法的性能優(yōu)于模擬退火算法，可以看出遺傳算法的全局優(yōu)化性能明顯優(yōu)于模擬退火算法。而本文基于關(guān)聯(lián)規(guī)則引導的遺傳算法獲得的結(jié)果則優(yōu)于基本遺傳算法，可以看出本文算法效果明顯。原因在于：本文對樣本進行模式挖掘，獲得了最優(yōu)與最弱樣本集，然后使用遺傳算法搜索最優(yōu)解，提高了對精英樣本的局部提煉效果，獲得了優(yōu)于傳統(tǒng)遺傳算法的性能。

4.2 各算法的收斂速度比較

圖7所示為三種算法收斂所需的代數(shù)統(tǒng)計，模擬退火算法的收斂速度最快，而基本遺傳算法的收斂速度最慢，原因在于：本文首先對樣本的精英子集與弱樣本子集進行模式挖掘，然后以挖掘的關(guān)聯(lián)規(guī)則引導遺傳算法演化，提高了演化的效率。雖然模擬退火算法的收斂速度最快，但其優(yōu)化效果較差。而本文算法在性能的優(yōu)化效果與收斂速度上均優(yōu)于傳統(tǒng)的遺傳算法。

5 結(jié) 語

本文針對無線網(wǎng)絡的可靠性拓撲設計問題，提出了一種基于模式挖掘引導遺傳算法的可靠拓撲設計方案。首先采用Monte Carlo模擬器將網(wǎng)絡模擬為圖結(jié)構(gòu)，然后采用Apriori算法提取模擬器數(shù)據(jù)的關(guān)聯(lián)規(guī)則，最終利用提取的關(guān)聯(lián)規(guī)則引導遺傳算法的變異與交叉操作，獲得了較好的網(wǎng)絡性能與收斂速度，具有較好的實用性。同時本文優(yōu)化算法具有普遍適用性，可以應用于無線傳感器網(wǎng)絡、無線自組織網(wǎng)絡等。

參考文獻

[1] 朱曉娟，陸陽，邱述威，等.無線傳感器網(wǎng)絡數(shù)據(jù)傳輸可靠性研究綜述[J].計算機科學，2013，40（9）：1?7.

[2] 李峰，趙海興，徐宗本.構(gòu)建一類新網(wǎng)絡簇的可靠性控制集[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.