高可靠性無線網絡拓撲設計范文

本站小編為你精心準備了高可靠性無線網絡拓撲設計參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

摘要：

無線網絡中的節點與路徑故障會產生懲罰性網絡成本，該成本是無線網絡的一個重要性能指標，對此提出了一種基于關聯規則引導遺傳算法的高可靠性無線網絡拓撲設計算法。首先，采用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.

作者：童立君 單位：南昌航空大學