樊里略 蘇文莉，陳 佳

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

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

本文通過(guò)分析移動(dòng)P2P網(wǎng)絡(luò)的特點(diǎn)，提出一種移動(dòng)環(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é)點(diǎn)準(zhǔn)確的查詢到所需文件并能完整的下載．

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

1 M-P2PFS中的文件搜索過(guò)程

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

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

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

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

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

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

2 M-P2PFS中文件傳輸過(guò)程

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

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

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

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

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

(a) 節(jié)點(diǎn)1發(fā)起文件傳輸請(qǐng)求 (b) 節(jié)點(diǎn)4發(fā)生移動(dòng)時(shí)的文件傳輸圖2 文件傳輸機(jī)制示意圖

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

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

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

表1 模擬實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

參考文獻(xiàn)：

[1] 歐中洪, 宋美娜,戰(zhàn)曉蘇,等.移動(dòng)對(duì)等網(wǎng)絡(luò)關(guān)鍵技術(shù)[J].軟件學(xué)報(bào),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é)報(bào)，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.