本站小編為你精心準(zhǔn)備了高可靠性無(wú)線網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

摘要：

無(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ù)?/a>設(shè)計(jì)算法。首先，采用MonteCarlo模擬器將網(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ù)?；演化算法；收斂速?/p>

引言

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

1問題模型

本文使用一個(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ù)分配，從而最小化懲罰性成本。目標(biāo)函數(shù)是延遲與傳輸丟失的總成本，同時(shí)也表示了網(wǎng)絡(luò)的性能。式（2）是可靠指數(shù)分配的預(yù)算限制，可靠節(jié)點(diǎn)設(shè)置越多，成本越高，如式（3），式（4）所示。式（5），式（6）兩式表示節(jié)點(diǎn)與鏈接的可靠指數(shù)分配決定了網(wǎng)絡(luò)的傳輸延遲與丟失。7）例如：假設(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ò)可靠性度量

本文采用MonteCarlo模擬器[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ù)）。然后使用Apriori算法搜索網(wǎng)絡(luò)結(jié)構(gòu)編碼的關(guān)聯(lián)規(guī)則，算法的偽代碼如算法1所示。為了提取有意義的信息與規(guī)則，分別對(duì)兩種樣本（高、低性能樣本集）進(jìn)行分類處理，本文將高低性能樣本設(shè)為95%以上與5%以下。如圖1所示，將5%的最低性能分為L(zhǎng)⁃組，5%的最高性能分為H⁃組。pattern_code(i)=Rnum×(li-1)+ri（9）式中：Rnum表示可靠指數(shù)等級(jí)的數(shù)量，本文設(shè)為5；li表示鄰接編碼中對(duì)應(yīng)項(xiàng)的位置；ri表示分配給節(jié)點(diǎn)或鏈接的某個(gè)可靠指數(shù)的數(shù)量。圖2所示為一個(gè)簡(jiǎn)單的以圖表示網(wǎng)絡(luò)的示例，其中可靠指數(shù)分別設(shè)為0.85，0.9，0.95，0.99；ri分別設(shè)為2，3，4，5。根據(jù)式（8），將網(wǎng)絡(luò)編碼為（0.95，0.9，0.95，0.85，0.00，0.85），然后根據(jù)式（9），將該網(wǎng)絡(luò)重新編碼為（P4，P8，P14，P17，P21，P27）。

3.2基于關(guān)聯(lián)規(guī)則引導(dǎo)的遺傳算法

傳統(tǒng)遺傳算法的主要流程框圖如圖3所示。其中遺傳算法主要包含以下步驟：（1）染色體的編碼與表示；（2）遺傳操作的實(shí)現(xiàn)；（3）適應(yīng)度函數(shù)的實(shí)現(xiàn)。使用上文提取的關(guān)聯(lián)規(guī)則引導(dǎo)GA的變異與交叉操作。

3.2.1交叉操作

圖4所示為交叉操作的一個(gè)實(shí)例，圖4（a）~（d）是4種簡(jiǎn)單的網(wǎng)絡(luò)圖形式，圖4（e）為對(duì)應(yīng)的鄰接矩陣，圖4（f）表示對(duì)應(yīng)的GA染色體形式。本文使用式（8）（模式挖掘）的編碼算法生成染色體，每條染色體中按鏈接與節(jié)點(diǎn)的可靠指數(shù)順序排序。

3.2.2變異操作

本文使用MonteCarlo模擬器計(jì)算適應(yīng)度值，并使用Goldberg算法[]對(duì)適應(yīng)度值進(jìn)行擴(kuò)展處理，從而提高GA的效率?；贖⁃組與L⁃組間的關(guān)聯(lián)建立一個(gè)變異圖。將頻繁項(xiàng)的概率定義為可靠選擇的概率，對(duì)于無(wú)頻繁項(xiàng)的網(wǎng)絡(luò)，將各項(xiàng)概率設(shè)為相等。H⁃組的選擇概率為：H選項(xiàng)選擇率=100×[(support×信息影響率)2]（10）式中的信息影響率表示：模式挖掘獲得的先驗(yàn)知識(shí)對(duì)GA的影響程度。降低L⁃組變異的概率為：L項(xiàng)選擇率=100×[0.2(support×信息影響率)]（11）若L⁃組與H⁃組中包含同一個(gè)可靠指數(shù)的項(xiàng)，式（12）則賦予support值高的項(xiàng)更多的選擇機(jī)會(huì)；若support值相等，GA則不會(huì)改變選擇機(jī)會(huì)。圖5為一個(gè)實(shí)例，其中前4個(gè)染色體項(xiàng)使用相同的信息影響率。HL項(xiàng)選擇率=[(H項(xiàng)選擇率+L項(xiàng)選擇率)2]（12）如圖5所示，式（9）編碼的第一個(gè)項(xiàng)，P1~P5表示其5個(gè)可能變異樣本，使用式（10）~式（12）計(jì)算其中每個(gè)項(xiàng)目。最終，保持相應(yīng)列值的總和在一個(gè)機(jī)會(huì)矩陣中，將每個(gè)機(jī)會(huì)值均分獲得變異圖。

3.2.3適應(yīng)度值

樣本的模式與H⁃組中挖掘的模式接近，則被選擇的概率較高；而樣本模式與L⁃組中挖掘的模式接近，則被選擇的概率較低。由于模式的效果可能隨著網(wǎng)絡(luò)尺寸（n）的增加而降低，則通過增加一個(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，1000）。表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ì)問題，提出了一種基于模式挖掘引導(dǎo)遺傳算法的可靠拓?fù)湓O(shè)計(jì)方案。首先采用MonteCarlo模擬器將網(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.

作者：童立君 單位：南昌航空大學(xué)