基于遺傳算法的Ｐｅｅｒ－ｔｏ－Ｐｅｅｒ路由算法Ｒ－ＧＡ

摘要：路由算法是制約PeertoPeer 系統(tǒng)整體性能的關(guān)鍵因素之一。目前大多數(shù)路由算法無法保證全局收斂，而鏈路延遲、費用、網(wǎng)絡(luò)帶寬等現(xiàn)實制約因素往往在選路時被忽略。針對上述問題，提出了基于遺傳算法的RGA路由算法。通過適度函數(shù)和遺傳因子，RGA可以快速地實現(xiàn)全局收斂。同時將鏈路的延遲、費用、帶寬等參數(shù)插入到適度函數(shù)中， 避免了盲目路由。仿真試驗的結(jié)果表明，RGA路由算法在大規(guī)模PeertoPeer系統(tǒng)中是高效和可擴展的。

關(guān)鍵詞： 路由； PeertoPeer； 遺傳算法； 適度函數(shù)

中圖法分類號：TP393；TP301．6文獻(xiàn)標(biāo)識碼：A

文章編號：1001－3695(2007)01－0316－02

在PeertoPeer(P2P) 系統(tǒng)中， 每個節(jié)點的路由表均記錄著直接鄰居節(jié)點的位置信息。目標(biāo)文件的定位通過節(jié)點間的消息轉(zhuǎn)發(fā)來實現(xiàn)。在大多數(shù)的P2P 系統(tǒng)中， 一個查詢從源節(jié)點到目標(biāo)節(jié)點平均需要花費O(logn)跳(n表示系統(tǒng)的節(jié)點總數(shù))。 在 Overlay 網(wǎng)絡(luò)中， 路由表中的直接鄰居在實際的物理網(wǎng)絡(luò)中可能相鄰甚遠(yuǎn)。

在文獻(xiàn)[1]中， 作者提出了相近度路由的概念。通過使用節(jié)點間端到端的最小延遲， PNS（Proximity Neighbor Selection）可以使用在Overlay網(wǎng)絡(luò)中。Ratnasamy等人為CAN提出了一種分布式圍欄算法（Distributed Binning Scheme），試圖讓Overlay拓?fù)浣Y(jié)構(gòu)與底層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)盡可能匹配[2]。該方法對規(guī)模固定的系統(tǒng)來說效果較好，但是如果系統(tǒng)規(guī)模處在動態(tài)變化之中，地標(biāo)節(jié)點的確定就變得很困難，而對地標(biāo)節(jié)點的依賴也會給系統(tǒng)帶來單點失效的可能。

在P2P系統(tǒng)中，不同的網(wǎng)絡(luò)連接方式下節(jié)點間的鏈路帶寬和費用也是不同的，如寬帶局域網(wǎng)、Cable Modem、無線網(wǎng)絡(luò)等。所以上述的因素在路由選擇中不能被忽略。 因此，

本文提出了一個基于遺傳算法（Genetic Algorithms，GA)的路由算法RGA， 它保證了所求解的全局收斂性。 節(jié)點間延遲，帶寬和費用等差異均被考慮在RGA算法中，這樣更加符合實際的P2P 系統(tǒng)。 

1P2P系統(tǒng)中的遺傳算法

遺傳算法的并行性[3]主要體現(xiàn)在兩個方面：①內(nèi)在并行性（Inherent Parallelism）。遺傳算法可以在P2P系統(tǒng)的各個節(jié)點上進(jìn)行獨立群體的演化計算，運行過程中可以不進(jìn)行任何通信。②內(nèi)含并行性（Implicit Parallelism）。由于遺傳算法采用群體的方式組織搜索，因此可以同時搜索解空間的多個區(qū)域。 

遺傳算法維持由許多個體組成的一個群體。在第t代，P(t)={X(t1)，X(t2)，…，X(tn)}。每個個體表述了問題的一個潛在解，通過對這些個體進(jìn)行合適的數(shù)據(jù)編碼來實現(xiàn)染色體的構(gòu)造，并對每個解X(ti)進(jìn)行評估。接下來， 合適的個體構(gòu)成一個新的群體(第t+1代)。 新群體的成員通過變異，交叉等遺傳算子的轉(zhuǎn)換又產(chǎn)生新的解。這樣經(jīng)過若干代的計算，程序?qū)諗浚藭r的最好個體就是近似最優(yōu)解。

通常對小規(guī)模的空間來說，我們可以用窮舉法（Try and Error）來求最優(yōu)解。但對像P2P這樣的大規(guī)?？臻g，專業(yè)的技巧是必需的。 

P2P路由問題[4] 可以抽象成一個節(jié)點間數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑問題，尤其是當(dāng)系統(tǒng)中存在多個副本時。較好的路徑是指低遲延，高帶寬和低費用的路由路徑。在遺傳算法中，每個個體均可以用圖來表示。從最初的群體開始，選出演化函數(shù)，演化程序開始執(zhí)行。變異算子用于改變單個圖；交叉算子用于將兩個圖合并成一個新圖；遺傳算子將優(yōu)秀的圖傳遞到下一代來保證合適的個體更加強壯。通過幾代的進(jìn)化，我們可以得到收斂的群體，最優(yōu)的個體將是我們的最優(yōu)解。因此，通過利用遺傳算法來解決P2P的路由問題， 整個系統(tǒng)的執(zhí)行效率將會得到改進(jìn)。

2基于遺傳算法的RGA路由算法

2．1編碼

可以使用一個大小為Nn×Nn采用二進(jìn)制編碼的一維數(shù)組作為P2P系統(tǒng)路由表的編碼方案，其中Nn表示系統(tǒng)中的節(jié)點數(shù)目。每個染色體所占用的空間為O(Nn×Nn)。

2．2適度函數(shù)

適度函數(shù)是繁殖的基礎(chǔ)，適度值高的個體將會有較多的機會來繁殖更多的后代[5]。相反，適度值低的個體將會逐步被淘汰。 

P2P路由算法的適度函數(shù)應(yīng)該遵從如下條件：

①路由總的代價應(yīng)該最低；②從源到目的只有一條合適路徑相連；③不存在的路徑應(yīng)該被避免。

RGA的適度函數(shù)表示如下： 

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) 表示路徑中的跳數(shù)。 a，b，c和d是歸一化參數(shù)。 

2．3算子 

（1）交叉Crossover。重組兩個被選擇的個體，使產(chǎn)生的后代有較好路徑。具體操作如下：兩個被選擇的個體在某個位置按照概率Pc被切割，第一染色體的第一部分和第二染色體的第二部分，第一染色體的第二部分和第二染色體的第一部分相互交叉的合并在一起。例如，由個體C1 和C2 通過交叉來產(chǎn)生新的個體C12和C22。

但產(chǎn)生的意義巨大。正是交叉和變異保證了 RGA路由算法的全局收斂性。 根據(jù)Kenneth DeJong[6]， 0.1%的變異概率就可以避免局部收斂。 

2．4RGA

我們提出的P2P 路由算法RGA 由如下五個主要步驟構(gòu)成：

（1）P2P路由問題的數(shù)字表述。編碼和解碼。

（2）產(chǎn)生一個初始群體。獲取路由表信息和設(shè)置染色體的初始狀態(tài)。

（3）選擇適度函數(shù)。 

（4）通過使用遺傳算子，得到一個新的群體并更新路由表。

（5）直到在要求代價范圍內(nèi)沒有可行路徑時，結(jié)束程序。 

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]路由算法在不同規(guī)模的P2P系統(tǒng)中作了仿真試驗。在Overlay網(wǎng)絡(luò)中，目標(biāo)文件的查詢是通過節(jié)點間的消息轉(zhuǎn)發(fā)來實現(xiàn)。數(shù)據(jù)延遲是判斷路由算法執(zhí)行效率的主要指標(biāo)。在兩套仿真系統(tǒng)中，我們產(chǎn)生相同的查詢請求。在仿真試驗中，節(jié)點數(shù)從100增加到700，延遲可以被RGA 和PGrid系統(tǒng)獨立地記錄下來。圖1 給出了實驗結(jié)果。對RGA而言，隨著節(jié)點數(shù)目的增加，延遲增加并不明顯；對PGrid而言，隨著節(jié)點數(shù)目的增加， 延遲快速地增大。這表明RGA 路由算法在大規(guī)模P2P系統(tǒng)中更加可行。

我們在節(jié)點數(shù)動態(tài)變化情況下對RGA算法收斂性進(jìn)行試驗觀察。在仿真試驗中， P2P系統(tǒng)的節(jié)點數(shù)在10~50的范圍內(nèi)動態(tài)變化，用于模擬在現(xiàn)實情況中節(jié)點自由加入和離開P2P系統(tǒng)。實驗結(jié)果如圖2所示。當(dāng)P2P系統(tǒng)中的節(jié)點增加時，RGA的平均進(jìn)化代數(shù)也將增加。這是因為隨著節(jié)點數(shù)的增加，染色體的編碼將會變長，搜索空間也將變大。

最后， 我們模擬了在2 500個節(jié)點的P2P系統(tǒng)中RGA 和PGrid路由算法的運行情況并對其運行時間進(jìn)行了記錄。從圖 3可以看出，隨著P2P規(guī)模的增大 RGA路由算法的運行時間并沒有明顯的增加，因此比PGrid算法具有更高的執(zhí)行效率。 

圖3在大規(guī)模P2P系統(tǒng)中RGA 和PGrid運行時間

4結(jié)論

綜上所述， RGA 路由算法在P2P系統(tǒng)中，尤其是當(dāng)系統(tǒng)規(guī)模較大時，表現(xiàn)出了較高的執(zhí)行效率。RGA考慮到了延遲、帶寬、傳輸代價等問題，因此更加適合實際系統(tǒng)的使用。然而適度函數(shù)和遺傳算子是制約RGA路由算法執(zhí)行效率的關(guān)鍵因素。所以如何構(gòu)建較好的適度函數(shù)和找到更加合適的遺傳算子是我們在后續(xù)工作中將繼續(xù)研究的課題。

參考文獻(xiàn)：

［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.

作者簡介：

王濤，博士研究生，主要研究方向為分布式文件系統(tǒng)、P2P計算；盧顯良，教授，博導(dǎo)，主要研究方向為計算機網(wǎng)絡(luò)、操作系統(tǒng)、信息安全。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文