基于關(guān)聯(lián)規(guī)則引導(dǎo)遺傳算法的高可靠性無線網(wǎng)絡(luò)拓?fù)湓O(shè)計

童立君

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

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

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

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

1 問題模型

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

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

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

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

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

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

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

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

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

3 本文算法

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

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

3.2.3 適應(yīng)度值

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

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

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

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

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

4.2 各算法的收斂速度比較

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

5 結(jié) 語

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

參考文獻(xiàn)

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

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