童立君

摘 要： 無(wú)線網(wǎng)絡(luò)中的節(jié)點(diǎn)與路徑故障會(huì)產(chǎn)生懲罰性網(wǎng)絡(luò)成本，該成本是無(wú)線網(wǎng)絡(luò)的一個(gè)重要性能指標(biāo)，對(duì)此提出了一種基于關(guān)聯(lián)規(guī)則引導(dǎo)遺傳算法的高可靠性無(wú)線網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)算法。首先，采用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)。仿真實(shí)驗(yàn)結(jié)果表明，對(duì)于多個(gè)網(wǎng)絡(luò)規(guī)模，該算法均可獲得較好的網(wǎng)絡(luò)性能與收斂速度，具有較好的實(shí)用性。

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

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

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

1 問(wèn)題模型

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

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

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

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

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

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

（3） 將節(jié)點(diǎn)?節(jié)點(diǎn)的會(huì)話稱為流量；

（4） 考慮兩個(gè)懲罰性成本：延遲成本與會(huì)話丟失成本；

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

3 本文算法

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

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

3.2.3 適應(yīng)度值

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

4 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

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

4.2 各算法的收斂速度比較

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

5 結(jié) 語(yǔ)

本文針對(duì)無(wú)線網(wǎng)絡(luò)的可靠性拓?fù)湓O(shè)計(jì)問(wèn)題，提出了一種基于模式挖掘引導(dǎo)遺傳算法的可靠拓?fù)湓O(shè)計(jì)方案。首先采用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ò)性能與收斂速度，具有較好的實(shí)用性。同時(shí)本文優(yōu)化算法具有普遍適用性，可以應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)、無(wú)線自組織網(wǎng)絡(luò)等。

參考文獻(xiàn)

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

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