一種基于文件路由表的移動P2P文件共享系統(tǒng)

樊里略 蘇文莉，陳 佳

(遵義師范學(xué)院計算機(jī)科學(xué)系，中國 遵義 563002)

近年來，大量用戶移動性應(yīng)用的需求和移動應(yīng)用環(huán)境的逐漸成熟，研究者開始關(guān)注具有更強(qiáng)分布性、更廣參與性和更具有對等自治特征的移動P2P網(wǎng)絡(luò)環(huán)境[1-5]．隨著移動設(shè)備的逐漸增多，P2P系統(tǒng)作為目前Internet的重要應(yīng)用，將在移動環(huán)境中得到更廣泛的應(yīng)用和發(fā)展．在有線Internet中，大多數(shù)P2P系統(tǒng)的操作都是依賴于節(jié)點間應(yīng)用層的連接，形成一個應(yīng)用層覆蓋網(wǎng)[6]，通常這些連接都是靜態(tài)的，只要系統(tǒng)中的兩個節(jié)點之間保持著連接即可．而在移動環(huán)境下保持靜態(tài)的覆蓋網(wǎng)連接是不可能的，覆蓋網(wǎng)拓?fù)洳荒芊从车讓右苿泳W(wǎng)絡(luò)拓?fù)洌M管覆蓋網(wǎng)拓?fù)涞墓?jié)點在系統(tǒng)中的駐留時間內(nèi)是靜態(tài)的，但是因為節(jié)點的移動性，拓?fù)涫穷l繁變化的[7]，這將會影響文件共享系統(tǒng)的性能．

本文通過分析移動P2P網(wǎng)絡(luò)的特點，提出一種移動環(huán)境下的P2P文件共享系統(tǒng)(Mobile P2P File Sharing System，M-P2PFS)．P2P文件共享系統(tǒng)需要高效準(zhǔn)確的文件搜索算法和穩(wěn)定的文件傳輸協(xié)議，因此本文基于應(yīng)用層覆蓋網(wǎng)應(yīng)用本地文件路由表進(jìn)行文件搜索和文件傳輸，以保障節(jié)點準(zhǔn)確的查詢到所需文件并能完整的下載．

通常P2P文件共享系統(tǒng)的關(guān)鍵技術(shù)主要有2個：一是傳輸查詢消息和搜索結(jié)果的文件搜索算法，另一個是下載匹配查詢消息的文件傳輸協(xié)議[8]．文件搜索一直是P2P系統(tǒng)研究的熱點之一，有線網(wǎng)絡(luò)中典型的P2P系統(tǒng)如Gnutella 0.4采用完全分布式的文件搜索策略[9]，文件查找采用泛洪機(jī)制，隨著查詢請求的增加，消息數(shù)量呈指數(shù)增長，網(wǎng)絡(luò)擁塞和帶寬浪費(fèi)嚴(yán)重，查詢效率也得不到保障．盡管如此，Gnutella還是得到了廣泛的應(yīng)用和發(fā)展，很多研究提出了許多改進(jìn)算法來減少洪泛算法的缺點，如Modified-BFS[10]算法在轉(zhuǎn)發(fā)查詢消息時不轉(zhuǎn)發(fā)給所有鄰居節(jié)點，而是隨機(jī)選擇k個鄰居節(jié)點進(jìn)行轉(zhuǎn)發(fā)，這樣來減小冗余信息．文獻(xiàn)[11]的一種搜索算法稱為Random Walk，查詢者隨機(jī)選取k個鄰居來轉(zhuǎn)發(fā)查詢消息，然后鄰居節(jié)點選取一個自己的鄰居依次繼續(xù)轉(zhuǎn)發(fā)，使用這種搜索算法，在搜索過程中產(chǎn)生的消息數(shù)量顯著減少．上述這些搜索算法都是基于參與節(jié)點能夠保持靜態(tài)連接的覆蓋層網(wǎng)絡(luò)．而與有線網(wǎng)絡(luò)不同，在移動環(huán)境中，由于節(jié)點的移動性和系統(tǒng)中節(jié)點隨時動態(tài)地加入和退出，系統(tǒng)覆蓋層網(wǎng)絡(luò)不能保持靜態(tài)的連接．因此，傳統(tǒng)有線網(wǎng)絡(luò)中的P2P搜索算法不能直接應(yīng)用于移動環(huán)境下．我們提出一種移動環(huán)境下P2P文件共享系統(tǒng)，應(yīng)用節(jié)點的本地文件路由表進(jìn)行文件搜索，完成文件傳輸，通過理論和實驗分析可知該系統(tǒng)能保障節(jié)點準(zhǔn)確的搜索到所需文件并能完整穩(wěn)定的下載．

1 M-P2PFS中的文件搜索過程

M-P2PFS系統(tǒng)中每個移動節(jié)點維護(hù)一個本地信息庫，由儲存在本地系統(tǒng)中的文件組成．M-P2PFS為在信息庫中的所有文件提供搜索功能．每個文件有一個獨(dú)一無二的文件標(biāo)示ID，另外每個節(jié)點維護(hù)一個文件路由表，用來為文件傳輸存儲可選的下一跳．節(jié)點在查詢處理過程中不斷更新文件路由表．

在文件搜索過程中，定義兩種類型的消息，一種類型是查詢消息用Query表示，包括查詢串，查詢串由一個或者多個關(guān)鍵字組成，另一種類型是響應(yīng)消息用Response表示，包括一個或多個匹配查詢的文件標(biāo)示ID．

由圖1可以直觀理解應(yīng)用文件路由表的搜索過程．假設(shè)有5個節(jié)點1，2，3，4，5，當(dāng)節(jié)點在彼此的無線傳輸范圍之內(nèi)時，就認(rèn)為節(jié)點之間可以相互建立連接．每個節(jié)點有一個本地信息庫和一個文件路由表．如圖1所示，每個節(jié)點邊上的上面的長方形表示本地信息庫，下面的表示文件路由表．

(a) 節(jié)點1發(fā)起查詢請求 (b) 節(jié)點2發(fā)送響應(yīng)消息 (c) 節(jié)點3,4,5發(fā)送響應(yīng)消息圖1 文件搜索過程示意圖

圖1(a)顯示節(jié)點1發(fā)起一個查詢請求消息Query，Query包含了文件a，b，c，d的關(guān)鍵字，也就是節(jié)點1發(fā)起查找文件a，b，c，d的請求．查詢消息Query的轉(zhuǎn)發(fā)借鑒移動Ad hoc網(wǎng)絡(luò)中的組播和廣播協(xié)議，通過鏈路層洪泛分布到整個系統(tǒng)．節(jié)點2在搜索本地信息庫后，發(fā)送一個包含了文件a和b標(biāo)示(這里就用a和b表示文件的標(biāo)識，文件c,d,e也一樣)的響應(yīng)消息給節(jié)點1方向的節(jié)點2的下一跳節(jié)點，這里即節(jié)點1，如圖1(b)，節(jié)點1在文件路由表中保存文件a和b的路由信息，即在文件路由表中節(jié)點2作為文件a和b的下一跳節(jié)點．另外節(jié)點4和節(jié)點5分別發(fā)送包含文件b,c,d和a,b,c標(biāo)示的響應(yīng)消息給節(jié)點1方向的下一跳節(jié)點即節(jié)點2和節(jié)點3，如圖1(c)所示．節(jié)點2接收到來自4和5的消息后，在轉(zhuǎn)發(fā)響應(yīng)消息之前，要對消息攜帶的文件標(biāo)示進(jìn)行檢查，文件c和d是節(jié)點2沒有的文件，則節(jié)點2在文件路由表中存儲文件c和d的路由信息．因為節(jié)點2之前已經(jīng)發(fā)送過帶有文件a和b標(biāo)識的響應(yīng)消息，則這里只轉(zhuǎn)發(fā)帶有文件c和d標(biāo)識的響應(yīng)消息．節(jié)點1收到響應(yīng)消息后，在文件路由表存儲文件c和d的下一跳路由信息，即文件c和d的下一跳路由節(jié)點是節(jié)點2如圖文件路由表所示c:2，d:2．節(jié)點3完成的工作同節(jié)點2類似，轉(zhuǎn)發(fā)帶有文件a,b,c標(biāo)識的響應(yīng)消息，因此節(jié)點1的文件路由表中文件a,b,c的下一跳節(jié)點又多了節(jié)點3可選．

從圖1(c)可以看出，節(jié)點2的文件路由表中不僅存儲了節(jié)點4作為文件c的下一跳路由節(jié)點，還存儲了節(jié)點5，在文件路由表中增加冗余并不會增加額外的傳輸開銷．在節(jié)點文件路由表中存儲文件冗余路由信息是為了在節(jié)點移動的情況下，保證接收方能穩(wěn)定地接收到完整文件，在文件傳輸過程中有詳細(xì)介紹．文件搜索過程結(jié)束后，節(jié)點1選擇匹配的文件下載．

2 M-P2PFS中文件傳輸過程

移動環(huán)境中，由于節(jié)點的移動，使得節(jié)點在下載文件過程中可能出現(xiàn)文件傳輸中斷等現(xiàn)象，導(dǎo)致節(jié)點不能下載到完整的文件．因此，接收方能夠在整個文件傳輸過程中保持對傳輸過程的完整控制是非常重要的．

本文提出一種文件分塊請求傳輸協(xié)議，其基本思想是：把要傳輸?shù)奈募指舫纱笮∠嗤膲K，文件接收節(jié)點沿著文件路由表提供的路由路徑發(fā)送一個數(shù)據(jù)塊請求消息，當(dāng)請求消息到達(dá)一個本地信息庫存有匹配文件的節(jié)點時，就返回帶有該請求數(shù)據(jù)塊的消息給文件接收者．文件接收者收到返回的數(shù)據(jù)塊后，繼續(xù)發(fā)送下一個文件數(shù)據(jù)塊請求，直到整個文件被完整下載．

我們通過圖2(a)來闡述文件傳輸機(jī)制．假設(shè)節(jié)點1要下載文件c．文件c的第一個文件數(shù)據(jù)塊的數(shù)據(jù)請求消息發(fā)送到存儲有文件c方向的下一跳節(jié)點，如節(jié)點1的文件路由表中所示，節(jié)點2和節(jié)點3．在有多個下一跳路由節(jié)點的情況下，根據(jù)節(jié)點之間的延遲來選擇，優(yōu)先選擇延遲較小的節(jié)點，這里優(yōu)先選擇節(jié)點2．(文件路由表中，文件的路由信息按延遲進(jìn)行排序如c:2,3，表示節(jié)點到文件c方向的下一跳節(jié)點2的延遲要比到節(jié)點3的延遲小)．節(jié)點2的本地信息庫沒有文件c，因此節(jié)點2根據(jù)本地文件路由表信息轉(zhuǎn)發(fā)數(shù)據(jù)請求信息給文件c方向最適合的下一跳節(jié)點，這里選擇節(jié)點4．節(jié)點4的本地信息庫存有文件c，沿著節(jié)點1方向返回帶有請求文件塊的消息給下一跳節(jié)點，再由節(jié)點2轉(zhuǎn)發(fā)給節(jié)點1．接下來節(jié)點1繼續(xù)發(fā)送下一個文件c的數(shù)據(jù)塊請求，直到整個文件被完整下載．

M-P2PFS中文件傳輸控制和數(shù)據(jù)傳輸都是在冗余路由中選擇最適合的路由，由于在文件傳輸過程中會存在節(jié)點移動，或者節(jié)點的加入退出等，因此，文件路由表中的路由信息可能發(fā)生變化，這就要求能提供一種高效的傳輸機(jī)制來解決路由失敗問題．

以圖2(b)為例，假設(shè)在文件c的傳輸過程中，由于節(jié)點4發(fā)生了移動，不在節(jié)點2的通信范圍之內(nèi)了，節(jié)點2和節(jié)點4的鏈接失敗．節(jié)點2一旦發(fā)現(xiàn)鏈路失敗，就在本地文件路由表中刪除節(jié)點4而發(fā)送文件塊的數(shù)據(jù)請求消息給現(xiàn)在更適合的文件c的下一跳節(jié)點即節(jié)點5．因此，節(jié)點2在本地解決了鏈路失敗問題，而沒有影響到其他節(jié)點，這顯然比通過發(fā)起全局路由發(fā)現(xiàn)來解決鏈路失敗要好．而在文件接收者1節(jié)點看來，并沒有感覺到文件傳輸過程中有鏈路失?。?/p>

(a) 節(jié)點1發(fā)起文件傳輸請求 (b) 節(jié)點4發(fā)生移動時的文件傳輸圖2 文件傳輸機(jī)制示意圖

3 系統(tǒng)性能分析

為了分析M-P2PFS系統(tǒng)的性能，我們用網(wǎng)絡(luò)模擬器NS-2[8]設(shè)計模擬實驗，同廣泛應(yīng)用的P2P文件共享系統(tǒng)Gnutella進(jìn)行比較，主要比較兩種系統(tǒng)中采用的搜索機(jī)制和文件傳輸機(jī)制的性能．

模擬實驗參數(shù)設(shè)置見表1．總共設(shè)置60個節(jié)點，其中移動節(jié)點40個，移動節(jié)點的傳輸范圍都設(shè)置為100 m，在一個900 m×900 m范圍內(nèi)，節(jié)點按Random waypoint移動模型進(jìn)行移動，移動速度在[0,1]m·s-1之間平均選擇．當(dāng)節(jié)點到達(dá)一個隨機(jī)選擇的目的時，停留60 s，然后繼續(xù)移動到下一個目的地．每個移動節(jié)點共享10個文件且節(jié)點每隔20 s發(fā)起一次查詢請求．為了評估文件傳輸效率，隨機(jī)選擇一個節(jié)點執(zhí)行100次不同文件的成功下載．

表1 模擬實驗參數(shù)設(shè)置

P2P文件共享系統(tǒng)中，最重要的一個性能是文件搜索準(zhǔn)確率，即對于一個查詢請求返回的響應(yīng)結(jié)果的質(zhì)量評估．這里用接收到的標(biāo)識唯一的文件數(shù)量同總共接收到的匹配查詢的文件總數(shù)的比值來表示查詢準(zhǔn)確率．圖3給出了文件搜索準(zhǔn)確率的比較，縱坐標(biāo)表示搜索準(zhǔn)確率，橫坐標(biāo)表示移動共享系統(tǒng)中節(jié)點的數(shù)量．

從圖3中可以看出，隨著節(jié)點的增加，兩種方法的文件搜索準(zhǔn)確率都在增加，這是由于節(jié)點的增加使得系統(tǒng)的連通率增加，節(jié)點直接彼此通信的幾率增加，因而文件搜索的準(zhǔn)確性自然也會隨之增加．但是在Gnutella中，節(jié)點增加到一定數(shù)量后出現(xiàn)了搜索準(zhǔn)確率下降的情況，在前文我們提到過Gnutella的覆蓋層網(wǎng)絡(luò)是靜態(tài)鏈接，沒有考慮實際物理網(wǎng)路中節(jié)點的移動性，而當(dāng)節(jié)點移動后，存在鏈路斷開等問題，必然會影響到文件搜索的效率．

為了分析在文件傳輸過程中，由于節(jié)點移動可能導(dǎo)致的文件發(fā)送者發(fā)生改變時對文件傳輸效率的影響，這里比較了文件傳輸成功率，即節(jié)點成功完整的下載到的文件數(shù)與發(fā)起的文件傳輸請求數(shù)之比．圖4給出了兩種系統(tǒng)中隨著系統(tǒng)中節(jié)點數(shù)量的增加，文件傳輸成功率的變化．

圖3 文件搜索效率比較 圖4 文件傳輸效率比較

從圖4中可以看出，系統(tǒng)中節(jié)點較少時，由于系統(tǒng)連通率不高，兩種系統(tǒng)的文件傳輸成功率都很低．隨著節(jié)點數(shù)量的增加，M-P2PFS系統(tǒng)能夠穩(wěn)定完整地完成40%以上的傳輸，則其能夠通過完成較多的文件傳輸為用戶提供更好的滿意度．

4 結(jié)語

本文在移動P2P文件共享系統(tǒng)中設(shè)計基于本地文件路由表的搜索機(jī)制和文件分塊傳輸協(xié)議，解決了由于節(jié)點的移動性導(dǎo)致的傳統(tǒng)有線網(wǎng)絡(luò)中覆蓋網(wǎng)靜態(tài)鏈接的不足，使得在有節(jié)點移動的情況下，文件傳輸能自

適應(yīng)調(diào)整，保證了文件下載的穩(wěn)定性和完整性．通過模擬實驗驗證了M-P2PFS系統(tǒng)具有較好的性能，能保證較高的文件搜索準(zhǔn)確率和文件傳輸成功率．在移動環(huán)境下的文件共享系統(tǒng)中，由于移動節(jié)點鏈路帶寬非常有限，因此文件搜索和傳輸都不能過多的占用帶寬資源，否則會造成網(wǎng)絡(luò)擁塞等，因此下一步我們將研究系統(tǒng)的帶寬消耗和移動環(huán)境下怎樣有效地利用有限的帶寬等網(wǎng)絡(luò)資源的課題．

參考文獻(xiàn)：

[1] 歐中洪, 宋美娜,戰(zhàn)曉蘇,等.移動對等網(wǎng)絡(luò)關(guān)鍵技術(shù)[J].軟件學(xué)報,2008,19(2):404-418.

[2] The washington times online. http://www.washshingtontimes.com/20040303-094741-3574r.htm.2004.

[3] 蔡俊亞.一種基于服務(wù)構(gòu)件模型的自適應(yīng)方法[J].湖南師范大學(xué)自然科學(xué)學(xué)報，2011，34(1)：48-51.

[4] MEIER R, CAHIIL V, NEDOS A,etal. Proximity-based service discovery in mobile ad hoc networks[J].Lecture Notes Computer Sci,2005,3545:1147-1149.

[5] ZHHN T, WINTER R, SCHILLER J. Simple, efficient peer-to-peer overlay clustering in mobile ad hoc networks:proc of the 12th IEEE Int’l Conf on Network Protocols, Washington DC, October 05-08[C]. Washington DC:IEEE Computer Society, 2004.

[6] WANG C, LI B. Peer-to-peer overlay networks: a survey[A].Technical Report, Department of Computer Science, HKUST, 2003.

[7] HUANG C M, HSU T H, HSU M F. Network-aware P2P file sharing over the wireless mobile networks[J]. Select Areas Commun, 2007, 25:204-210.

[8] SAROIU S, GUMMADI P K, GRIBBLE S D. A measurment study of peer-to-peer file sharing systems:proc of the multimedia computing and networking[C]. San Jose, SPIE, 2002.

[9] Gnutella[EB/OL]. http://www.gnutella.com,2001.

[10] KALOGERAKI V, GUNOPULOS D, ZEINALIPOUR-YAZTI D. A local search mechanism for peer-to-peer networks:proc of the 11th Int’l Conf on information and knowledge management[C]. New York: ACM Press, 2002.

[11] CHRISTOS G, MILENA M, AMIN S. Random walks in peer-to-peer networks: Algorithms and evaluation[J].Perform Evalu, 2006, 63(3):241-263.

[12] 徐雷鳴,龐 博,趙 耀.NS與網(wǎng)絡(luò)模擬[M].北京:人民郵電出版社,2003.