基于遺傳算法的Ｐｅｅｒ－ｔｏ－Ｐｅｅｒ路由算法Ｒ－ＧＡ
2007-01-01 00:00:00王濤盧顯良
計算機應用研究 2007年1期
摘要：路由算法是制約PeertoPeer 系統整體性能的關鍵因素之一。目前大多數路由算法無法保證全局收斂，而鏈路延遲、費用、網絡帶寬等現實制約因素往往在選路時被忽略。針對上述問題，提出了基于遺傳算法的RGA路由算法。通過適度函數和遺傳因子，RGA可以快速地實現全局收斂。同時將鏈路的延遲、費用、帶寬等參數插入到適度函數中， 避免了盲目路由。仿真試驗的結果表明，RGA路由算法在大規模PeertoPeer系統中是高效和可擴展的。
關鍵詞： 路由； PeertoPeer； 遺傳算法； 適度函數
中圖法分類號：TP393；TP301．6文獻標識碼：A
文章編號：1001－3695(2007)01－0316－02
在PeertoPeer(P2P) 系統中， 每個節點的路由表均記錄著直接鄰居節點的位置信息。目標文件的定位通過節點間的消息轉發來實現。在大多數的P2P 系統中， 一個查詢從源節點到目標節點平均需要花費O(logn)跳(n表示系統的節點總數)。 在 Overlay 網絡中， 路由表中的直接鄰居在實際的物理網絡中可能相鄰甚遠。
在文獻[1]中， 作者提出了相近度路由的概念。通過使用節點間端到端的最小延遲， PNS（Proximity Neighbor Selection）可以使用在Overlay網絡中。Ratnasamy等人為CAN提出了一種分布式圍欄算法（Distributed Binning Scheme），試圖讓Overlay拓撲結構與底層網絡拓撲結構盡可能匹配[2]。該方法對規模固定的系統來說效果較好，但是如果系統規模處在動態變化之中，地標節點的確定就變得很困難，而對地標節點的依賴也會給系統帶來單點失效的可能。
在P2P系統中，不同的網絡連接方式下節點間的鏈路帶寬和費用也是不同的，如寬帶局域網、Cable Modem、無線網絡等。所以上述的因素在路由選擇中不能被忽略。 因此，
本文提出了一個基于遺傳算法（Genetic Algorithms，GA)的路由算法RGA， 它保證了所求解的全局收斂性。 節點間延遲，帶寬和費用等差異均被考慮在RGA算法中，這樣更加符合實際的P2P 系統。
1P2P系統中的遺傳算法
遺傳算法的并行性[3]主要體現在兩個方面：①內在并行性（Inherent Parallelism）。遺傳算法可以在P2P系統的各個節點上進行獨立群體的演化計算，運行過程中可以不進行任何通信。②內含并行性（Implicit Parallelism）。由于遺傳算法采用群體的方式組織搜索，因此可以同時搜索解空間的多個區域。
遺傳算法維持由許多個體組成的一個群體。在第t代，P(t)={X(t1)，X(t2)，…，X(tn)}。每個個體表述了問題的一個潛在解，通過對這些個體進行合適的數據編碼來實現染色體的構造，并對每個解X(ti)進行評估。接下來， 合適的個體構成一個新的群體(第t+1代)。 新群體的成員通過變異，交叉等遺傳算子的轉換又產生新的解。這樣經過若干代的計算，程序將會收斂，此時的最好個體就是近似最優解。
通常對小規模的空間來說，我們可以用窮舉法（Try and Error）來求最優解。但對像P2P這樣的大規模空間，專業的技巧是必需的。
P2P路由問題[4] 可以抽象成一個節點間數據傳輸的最優路徑問題，尤其是當系統中存在多個副本時。較好的路徑是指低遲延，高帶寬和低費用的路由路徑。在遺傳算法中，每個個體均可以用圖來表示。從最初的群體開始，選出演化函數，演化程序開始執行。變異算子用于改變單個圖；交叉算子用于將兩個圖合并成一個新圖；遺傳算子將優秀的圖傳遞到下一代來保證合適的個體更加強壯。通過幾代的進化，我們可以得到收斂的群體，最優的個體將是我們的最優解。因此，通過利用遺傳算法來解決P2P的路由問題， 整個系統的執行效率將會得到改進。
2基于遺傳算法的RGA路由算法
2．1編碼
可以使用一個大小為Nn×Nn采用二進制編碼的一維數組作為P2P系統路由表的編碼方案，其中Nn表示系統中的節點數目。每個染色體所占用的空間為O(Nn×Nn)。
2．2適度函數
適度函數是繁殖的基礎，適度值高的個體將會有較多的機會來繁殖更多的后代[5]。相反，適度值低的個體將會逐步被淘汰。
P2P路由算法的適度函數應該遵從如下條件：
①路由總的代價應該最低；②從源到目的只有一條合適路徑相連；③不存在的路徑應該被避免。
RGA的適度函數表示如下：
Route_fit(x)=a×band(x)+b×cost(x)+c×latency(x)+d×hop(x)(1)
在式(1)中， band(x) 表示帶寬， cost(x) 表示路徑的費用， latency(x)表示鏈路延遲情況，hop(x) 表示路徑中的跳數。 a，b，c和d是歸一化參數。
2．3算子
（1）交叉Crossover。重組兩個被選擇的個體，使產生的后代有較好路徑。具體操作如下：兩個被選擇的個體在某個位置按照概率Pc被切割，第一染色體的第一部分和第二染色體的第二部分，第一染色體的第二部分和第二染色體的第一部分相互交叉的合并在一起。例如，由個體C1 和C2 通過交叉來產生新的個體C12和C22。
但產生的意義巨大。正是交叉和變異保證了 RGA路由算法的全局收斂性。 根據Kenneth DeJong[6]， 0.1%的變異概率就可以避免局部收斂。
2．4RGA
我們提出的P2P 路由算法RGA 由如下五個主要步驟構成：
（1）P2P路由問題的數字表述。編碼和解碼。
（2）產生一個初始群體。獲取路由表信息和設置染色體的初始狀態。
（3）選擇適度函數。
（4）通過使用遺傳算子，得到一個新的群體并更新路由表。
（5）直到在要求代價范圍內沒有可行路徑時，結束程序。
RGA的偽代碼如下：
begin
t:=0;
initialize P(t); //得到初始路由表
evaluate P(t); // 使用式（1）中的 Route_fit(x)
while (the termination condition is not reached) do
begin
t:=t+1;
select P(t) from P(t1);
recombine P(t);
evaluate P(t); //使用式（1）中的 Route_fit(x)
end
end
3試驗分析
我們將RGA路由算法和目前流行的 PGrid[7]路由算法在不同規模的P2P系統中作了仿真試驗。在Overlay網絡中，目標文件的查詢是通過節點間的消息轉發來實現。數據延遲是判斷路由算法執行效率的主要指標。在兩套仿真系統中，我們產生相同的查詢請求。在仿真試驗中，節點數從100增加到700，延遲可以被RGA 和PGrid系統獨立地記錄下來。圖1 給出了實驗結果。對RGA而言，隨著節點數目的增加，延遲增加并不明顯；對PGrid而言，隨著節點數目的增加， 延遲快速地增大。這表明RGA 路由算法在大規模P2P系統中更加可行。
我們在節點數動態變化情況下對RGA算法收斂性進行試驗觀察。在仿真試驗中， P2P系統的節點數在10~50的范圍內動態變化，用于模擬在現實情況中節點自由加入和離開P2P系統。實驗結果如圖2所示。當P2P系統中的節點增加時，RGA的平均進化代數也將增加。這是因為隨著節點數的增加，染色體的編碼將會變長，搜索空間也將變大。
最后， 我們模擬了在2 500個節點的P2P系統中RGA 和PGrid路由算法的運行情況并對其運行時間進行了記錄。從圖 3可以看出，隨著P2P規模的增大 RGA路由算法的運行時間并沒有明顯的增加，因此比PGrid算法具有更高的執行效率。
圖3在大規模P2P系統中RGA 和PGrid運行時間
4結論
綜上所述， RGA 路由算法在P2P系統中，尤其是當系統規模較大時，表現出了較高的執行效率。RGA考慮到了延遲、帶寬、傳輸代價等問題，因此更加適合實際系統的使用。然而適度函數和遺傳算子是制約RGA路由算法執行效率的關鍵因素。所以如何構建較好的適度函數和找到更加合適的遺傳算子是我們在后續工作中將繼續研究的課題。
參考文獻：
［1］H Zhang，A Goel，R Govindan. Incrementally Improving Lookup Latency in Distributed Hash Table Systems[J].ACM SIGMETRICS Perfor￣mance Evaluation Review，2003，31(1):114125.
［2］Yatin Chawathe， Sriram Ramabhadran， Sylvia Ratnasamy. A Case Study in Building Layered DHT Applications[C]. Proceedings of the 2005 Conference on Applications， Technologies， Architectures and Protocols for Computer Communications， Philadelphia: Pennsylvania，2005.97108.
［3］Whitley L D. Foundations of Genetic AlgorithmsⅡ[M]. Morgan Kaufmann Publisher，1993.
［4］Stoica I， Morris R， Karger D. A Scalable PeertoPeer Lookup Service for Internet Applications[J]. ACM SIGCOMM Computer Communication Review， 2001，31(4):149160.
［5］Ronald C Linton. Adapting Binary Fitness Functions in Genetic Algorithms[C]. Proceedings of the 42nd Annual Southeast Regional Conference. Huntsville:Alabama，20-04.391395.
［6］Dimitri C. Genetic Algorithms for Machine Learning[J]. ACM SIGART， 1998，9(2):3334.
［7］Karl Aberer. PGrid: A Selforganizing Access Structure for P2P Information Systems[J]. ACM SIGMOD，2003，32(3):2933.
作者簡介：
王濤，博士研究生，主要研究方向為分布式文件系統、P2P計算；盧顯良，教授，博導，主要研究方向為計算機網絡、操作系統、信息安全。
注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
