無(wú)線Ad-Hoc網(wǎng)絡(luò)中P2P文件搜索機(jī)制的研究

無(wú)線Ad-Hoc網(wǎng)絡(luò)中P2P文件搜索機(jī)制的研究

無(wú)線Ad-Hoc網(wǎng)絡(luò)因其構(gòu)建容易、支持用戶移動(dòng)性的特點(diǎn)，在無(wú)線通信領(lǐng)域中占有極其重要的地位并具有廣闊的應(yīng)用前景。無(wú)線通信技術(shù)、移動(dòng)技術(shù)的發(fā)展為無(wú)線Ad-Hoc網(wǎng)絡(luò)(WANET)提供了更廣泛的應(yīng)用空間。經(jīng)常使用文件共享的P2P網(wǎng)非常適合 WANET。然而，在現(xiàn)有的無(wú)線Ad-Hoc網(wǎng)絡(luò)中直接應(yīng)用P2P技術(shù)，會(huì)造成系統(tǒng)開(kāi)銷大量增加，傳輸效率及查詢成功率不高，從而影響整個(gè)網(wǎng)絡(luò)的性能。在無(wú)線Ad-Hoc網(wǎng)絡(luò)(WANET)中方便快捷地實(shí)現(xiàn)P2P數(shù)據(jù)共享與交換，改善文件搜索和下載機(jī)制成為廣泛關(guān)注的課題。
??? 這里提出一種將查詢功能和路由功能統(tǒng)一的跨層設(shè)計(jì)方案，利用分布式哈希表建立樹(shù)狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，使用P2P位置查找技術(shù)將文件位置信息分配在其間，每一網(wǎng)絡(luò)成員都存儲(chǔ)和保留系統(tǒng)資源的位置及路由信息，實(shí)現(xiàn)共享文件的定位查詢。在WANET中實(shí)現(xiàn)查詢和路由功能的統(tǒng)一，提高文件搜索和下載效率，定向查詢網(wǎng)絡(luò)資源，降低冗余開(kāi)銷。

2 系統(tǒng)概述
??? 這里WANET通過(guò)節(jié)點(diǎn)間的樹(shù)形邏輯結(jié)構(gòu)解決共享文件的定位查詢問(wèn)題，隨著網(wǎng)絡(luò)新節(jié)點(diǎn)的加入樹(shù)形拓?fù)浣Y(jié)構(gòu)增大。新節(jié)點(diǎn)只能通過(guò)某一個(gè)鄰居節(jié)點(diǎn)加入 WANET，每個(gè)WANET向外提供唯一的網(wǎng)絡(luò)ID，在同一ID的網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)只能擁有一個(gè)雙親節(jié)點(diǎn)。網(wǎng)絡(luò)有一個(gè)層次分明的樹(shù)狀拓?fù)浣Y(jié)構(gòu)，這種結(jié)構(gòu)有助于查找文件路徑(即從存放路徑的節(jié)點(diǎn)獲得到達(dá)文件存儲(chǔ)節(jié)點(diǎn)的路由)，以便從文件存儲(chǔ)節(jié)點(diǎn)下載文件。

??? 為了存儲(chǔ)和保留位置信息以及路由信息，系統(tǒng)使用全分布哈希表，關(guān)鍵詞是所要共享文件的文件名，值是共享文件的全球統(tǒng)一的位置信息(節(jié)點(diǎn)MAC地址和節(jié)點(diǎn)文件的全路徑)。用一維空間來(lái)存儲(chǔ)關(guān)鍵詞和哈希值對(duì)，通過(guò)統(tǒng)一的哈希函數(shù)將每個(gè)關(guān)鍵詞映射到哈希鏈上的對(duì)應(yīng)位置。統(tǒng)一的函數(shù)有助于節(jié)點(diǎn)之間信息分配的平衡， WANET中的每個(gè)節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)一段哈希鏈(與哈希表上的索引項(xiàng)對(duì)應(yīng))。如果某一節(jié)點(diǎn)負(fù)責(zé)哈希鏈段上包含某一文件哈希值，稱該節(jié)點(diǎn)為文件的路徑節(jié)點(diǎn) (Pnode)，存儲(chǔ)文件F的節(jié)點(diǎn)就稱為文件節(jié)點(diǎn)(Fnode)。因此Pnode存儲(chǔ)攜帶位置信息的索引，F(xiàn)node存儲(chǔ)實(shí)際文件。因此，訪問(wèn)一個(gè)文件的步驟如下：查詢節(jié)點(diǎn)(Qnode)哈希被搜索的文件名以確定哈希鏈上的值；訪問(wèn)Pnode(哈希值包含在Pnode負(fù)責(zé)的哈希鏈內(nèi))；從Pnode獲取被搜索文件的位置(即Fnode)并確定從Pnode小節(jié)點(diǎn)到Fnode的路由；從Qnode獲取到Qnode-Fnode的路由，訪問(wèn)Fnode，文件從 Fnode被下載。

3 樹(shù)形拓?fù)涞慕⒑凸?jié)點(diǎn)文件定位
??? 圖1d表示一個(gè)含有7個(gè)節(jié)點(diǎn)的WANET網(wǎng)絡(luò)，在該網(wǎng)絡(luò)中，假定節(jié)點(diǎn)A、B、C、D、E、F、G提供的共享文件分別為(α1α2)、(β1β2)、(γ1)、(δ1 δ2)、(σ1)、(ε1)、(η1η2)。

3．1 WANET網(wǎng)絡(luò)系統(tǒng)樹(shù)形拓?fù)涞慕?br>??? 假設(shè)網(wǎng)絡(luò)組建初期只有一個(gè)初始節(jié)點(diǎn)A，要建立一個(gè)如圖1d所示的7個(gè)節(jié)點(diǎn)的WANET文件共享網(wǎng)絡(luò)，樹(shù)形拓?fù)涞慕⑦^(guò)程如下：
??? (1)節(jié)點(diǎn)A對(duì)自己的兩個(gè)共享文件α1、α2哈希后將值映射到整段共享文件哈希鏈上，如圖2a所示。

??? (2)節(jié)點(diǎn)B(共享文件β1、β2)發(fā)現(xiàn)節(jié)點(diǎn)A并向節(jié)點(diǎn)A發(fā)起接入請(qǐng)求，即B要加入A組成的網(wǎng)絡(luò)。節(jié)點(diǎn)A收到B的接入請(qǐng)求后，將自己所負(fù)責(zé)的哈希鏈分成兩段并分配一半給B，文件α2因此落入節(jié)點(diǎn)B負(fù)責(zé)的一段哈希鏈，A將文件α2的位置索引送至B(文件雖然還存放在節(jié)點(diǎn)A，但A上α2的位置信息置空)。因此，A成為B的雙親節(jié)點(diǎn)。B存放著文件α2的位置信息[α2，A]。
??? (3)B向網(wǎng)絡(luò)插入其共享文件β1和β2，β1映射到B節(jié)點(diǎn)所負(fù)責(zé)的哈希鏈段，β2映射到A節(jié)點(diǎn)所負(fù)責(zé)哈希鏈段。則B節(jié)點(diǎn)存儲(chǔ)位置信息[β1，B]，A節(jié)點(diǎn)存儲(chǔ)位置信息[β2，B]，即B為文件β1的PnodeA為文件β2的Pnode,如圖2b所示。
??? (4)另一個(gè)新節(jié)點(diǎn)C(存儲(chǔ)文件γ1、γ2)發(fā)現(xiàn)節(jié)點(diǎn)B并對(duì)其發(fā)出接入請(qǐng)求，節(jié)點(diǎn)C從B接入網(wǎng)絡(luò)，B將自己的哈希鏈段分出一半給C。節(jié)點(diǎn)C上的文件γ1、 γ2哈希后映射到哈希鏈上，如圖2c。α2落入C所負(fù)責(zé)的哈希鏈段，B將α2的信息送至C，節(jié)點(diǎn)C不僅保留α2的位置信息，也保留從C到文件α2的路徑信息。C將B加到路徑上，同時(shí)保存[α2，BA]的索引項(xiàng)。表明文件α2存儲(chǔ)在節(jié)點(diǎn)A，并且從C到節(jié)點(diǎn)A的路徑是“C-B-A”。節(jié)點(diǎn)B成為C的雙親節(jié)點(diǎn)。
??? (5)C向網(wǎng)絡(luò)插入共享文件γ1、γ2，γ1映射到C負(fù)責(zé)的哈希鏈段，γ2映射到A負(fù)責(zé)的哈希鏈段。
??? (6)同理，節(jié)點(diǎn)E發(fā)現(xiàn)網(wǎng)絡(luò)并向節(jié)點(diǎn)B發(fā)出接入請(qǐng)求后，分擔(dān)了B負(fù)責(zé)的一半哈希鏈并插入文件σ1，B成為E的雙親節(jié)點(diǎn)；節(jié)點(diǎn)D(存儲(chǔ)文件δ1和δ2)發(fā)現(xiàn)網(wǎng)絡(luò)并從節(jié)點(diǎn)E接入后分擔(dān)了E一半的哈希鏈，節(jié)點(diǎn)F(存儲(chǔ)了文件η1和η2)發(fā)現(xiàn)網(wǎng)絡(luò)并從E接入，叉分擔(dān)E剩下部分一半的哈希鏈：最后節(jié)點(diǎn)G(存儲(chǔ)共享文件ε1)也從E加入網(wǎng)絡(luò)又分擔(dān)了 E剩下哈希鏈的一半。這樣，E成為節(jié)點(diǎn)D、G、F的雙親節(jié)點(diǎn)。各個(gè)節(jié)點(diǎn)在加入的過(guò)程中向網(wǎng)絡(luò)插入自己提供的共享文件，如圖2d~圖2g中所示，相應(yīng)的共享文件被插入到網(wǎng)絡(luò)中各節(jié)點(diǎn)所負(fù)責(zé)的哈希鏈上，在此過(guò)程中，相應(yīng)的節(jié)點(diǎn)也存儲(chǔ)了文件名及到達(dá)文件存儲(chǔ)節(jié)點(diǎn)的路由信息。
??? 該網(wǎng)絡(luò)結(jié)構(gòu)建立后，網(wǎng)絡(luò)中各共享文件的當(dāng)前位置和路由信息也被定位，搜索各共享文件的路由可從訪問(wèn)Pnode的請(qǐng)求消息中獲得，如圖2所示。網(wǎng)絡(luò)的樹(shù)形拓?fù)浣Y(jié)構(gòu)也同時(shí)建立，如圖1所示。
??? (7)恢復(fù)當(dāng)雙親節(jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)斷網(wǎng)時(shí)，雙親節(jié)點(diǎn)重新獲得子節(jié)點(diǎn)所負(fù)責(zé)的哈希鏈段?；蜃庸?jié)點(diǎn)與其雙親斷開(kāi)時(shí)，從子節(jié)點(diǎn)往下每個(gè)雙親與子節(jié)點(diǎn)哈希鏈重新分配。
??? (8)離開(kāi)當(dāng)一個(gè)節(jié)點(diǎn)要離開(kāi)WANET文件共享網(wǎng)絡(luò)時(shí)，要先刪除所有共享文件，再將其索引信息刪除，如E將自己的哈希鏈交付雙親B，同時(shí)將離網(wǎng)消息通知其雙親B和子節(jié)點(diǎn)D、G、F，則節(jié)點(diǎn)B將D、G、F加為子節(jié)點(diǎn)，節(jié)點(diǎn)D、G、F將B作為雙親節(jié)點(diǎn)。
??? 綜上所述，在圖1d中，假設(shè)節(jié)點(diǎn)D要查找文件η1，則D為查詢節(jié)點(diǎn)Qnode，文件η1存儲(chǔ)在F節(jié)點(diǎn)，則F節(jié)點(diǎn)就是文件節(jié)點(diǎn)Fnode，文件η1映射到哈希鏈上的H(η1)點(diǎn)，而H(η1)點(diǎn)正好落在節(jié)點(diǎn)C負(fù)責(zé)的哈希鏈上，所以，節(jié)點(diǎn)C就是路徑節(jié)點(diǎn)Pnode，它存儲(chǔ)著由Pnode(節(jié)點(diǎn)C)到Fnode (節(jié)點(diǎn)F)的路由信息。

4 WANET網(wǎng)絡(luò)中共享文件搜索和下載過(guò)程
??? 在圖1d中，假設(shè)D作為查詢節(jié)點(diǎn)搜索文件η2，D不知道η2的位置，甚至不知道這個(gè)文件是否存在，但由H(η2)的可以知道文件存儲(chǔ)在某個(gè)節(jié)點(diǎn)中。共享文件η2文件的搜索和下載過(guò)程如圖4所示。

??? (1)節(jié)點(diǎn)D對(duì)文件η2哈希，得到H(η2)，D發(fā)現(xiàn)H(η2)不在自己負(fù)責(zé)的哈希鏈內(nèi)，而D本身又沒(méi)有子節(jié)點(diǎn)，D就將查詢傳遞給其唯一的鄰居節(jié)點(diǎn)E(E這里也是D的雙親節(jié)點(diǎn))。
??? (2)節(jié)點(diǎn)E收到節(jié)點(diǎn)D查詢?chǔ)?的請(qǐng)求[η2，D]，但節(jié)點(diǎn)E的3個(gè)鄰居節(jié)點(diǎn)B、G和F都不包含文件η2的路由信息H(η2)，E就將查詢送至其雙親節(jié)點(diǎn)B。
??? (3)由于節(jié)點(diǎn)B所負(fù)責(zé)的哈希鏈也不包含H(η2)，但是因?yàn)楣?jié)點(diǎn)B知道它的一個(gè)子節(jié)點(diǎn)(這里指節(jié)點(diǎn)C)負(fù)責(zé)的哈希鏈上包含所請(qǐng)求的文件名的哈希值，按照H(η2)值和文件哈希鏈狀態(tài)，B將查詢向前傳送到節(jié)點(diǎn)C(否則節(jié)點(diǎn)B將查詢送給其雙親節(jié)點(diǎn)A)。
??? 節(jié)點(diǎn)B將查詢送到節(jié)點(diǎn)C后并不能保證能收到C的應(yīng)答。節(jié)點(diǎn)C除和節(jié)點(diǎn)B相連外可能還與其他節(jié)點(diǎn)相連，因此，確定節(jié)點(diǎn)所在的哈希鏈后，C可能將查詢送給它的一個(gè)子節(jié)點(diǎn)。但是無(wú)論節(jié)點(diǎn)C還是其子節(jié)點(diǎn)響應(yīng)查詢請(qǐng)求都對(duì)節(jié)點(diǎn)B無(wú)影響。節(jié)點(diǎn)B只知道將查詢送至節(jié)點(diǎn)C。在拓?fù)浣Y(jié)構(gòu)圖中，節(jié)點(diǎn)C沒(méi)有子節(jié)點(diǎn)并且擁有文件 η2的位置信息。從源節(jié)點(diǎn)發(fā)起查詢的路徑都被標(biāo)識(shí)為查詢。
??? (1)C節(jié)點(diǎn)收到查詢消息[η2，BED]，表示節(jié)點(diǎn)D經(jīng)節(jié)點(diǎn)E、B查詢文件η2，于是C對(duì)D產(chǎn)生查詢響應(yīng)消息ACK[η2，EBC](包含位置信息)，沿著路徑[η2，EBC]返回給節(jié)點(diǎn)D。
??? (2)從節(jié)點(diǎn)C獲得文件節(jié)點(diǎn)Fnode的路由信息FED沿查詢節(jié)點(diǎn)的路由回送節(jié)點(diǎn)D，節(jié)點(diǎn)C將響應(yīng)傳送給路徑上的下一個(gè)節(jié)點(diǎn)B。
??? (3)節(jié)點(diǎn)B查看響應(yīng)中的路由后，將消息送至路徑的下一個(gè)節(jié)點(diǎn)E。
??? (4)E查看路由后再將消息送至路徑中文件節(jié)點(diǎn)F(文件η2的存儲(chǔ)節(jié)點(diǎn))。
??? (5)節(jié)點(diǎn)D收到查詢響應(yīng)，響應(yīng)消息中包含文件η2的位置信息[η2，DEF]?，F(xiàn)在，節(jié)點(diǎn)D不僅知道了文件η2存在節(jié)點(diǎn)F中，也知道了兩個(gè)路徑從D到C (含η2文件位置信息)和從C到F(η2文件存儲(chǔ)節(jié)點(diǎn))。節(jié)點(diǎn)D將路徑鏈接成D-E-B-C-B-E-F，然后刪除不需要的路徑E-B-C-B，最后形成從D到η2的路徑D-E-F，即從查詢發(fā)起節(jié)點(diǎn)D到文件η2的存儲(chǔ)節(jié)點(diǎn)F的路徑，通過(guò)它能直接從節(jié)點(diǎn)F找到并下載文件η2。

5 與洪泛的比較系統(tǒng)的通信開(kāi)銷
??? WANET通常用于P2P文件共享，且一般采用洪泛查詢。假定洪泛模型無(wú)選擇轉(zhuǎn)發(fā)功能，因此，假定洪泛查詢一旦在網(wǎng)絡(luò)中啟動(dòng)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)都能收到查詢。該查詢產(chǎn)生的系統(tǒng)開(kāi)銷O=(n-1)m，其中m表示查詢次數(shù)，n表示節(jié)點(diǎn)數(shù)量。該WANET共享系統(tǒng)中P2P文件搜索和下載模型(圖4)組建網(wǎng)絡(luò)拓?fù)鋾r(shí)形成的樹(shù)形結(jié)構(gòu)使得即便所查文件不存在，也不會(huì)像洪泛一樣造成過(guò)多無(wú)用的查詢消息，該結(jié)構(gòu)幾乎能發(fā)現(xiàn)和訪問(wèn)網(wǎng)絡(luò)中的所有共享文件。

??? 所以。一旦網(wǎng)絡(luò)建立。系統(tǒng)開(kāi)銷與洪泛相比，單個(gè)查詢的成本效益明顯合算。
??? 另一方面，由于恢復(fù)操作和網(wǎng)絡(luò)接入操作產(chǎn)生的系統(tǒng)開(kāi)銷較大，當(dāng)每次斷網(wǎng)和網(wǎng)絡(luò)接入發(fā)生時(shí)，會(huì)帶來(lái)額外開(kāi)銷(在執(zhí)行恢復(fù)操作中斷開(kāi)的子節(jié)點(diǎn)變?yōu)楦?jié)點(diǎn)，哈希鏈在整個(gè)子網(wǎng)絡(luò)中重新分配；網(wǎng)絡(luò)接入時(shí)，每個(gè)接入的節(jié)點(diǎn)要對(duì)全網(wǎng)絡(luò)中的共享文件執(zhí)行插入請(qǐng)求，產(chǎn)生很大通信流量)，而洪泛不會(huì)帶來(lái)這樣的開(kāi)銷。

6 結(jié)論
??? 同樣大小的網(wǎng)絡(luò)中，在低移動(dòng)性、需要頻繁搜索文件的WANET上，提出方案的帶寬效率比洪泛高，文件搜索更有效。如果WANET網(wǎng)絡(luò)成員移動(dòng)頻繁且搜索文件不頻繁，則采用洪泛會(huì)更好。為避免洪泛和通過(guò)單播方式訪問(wèn)文件，我們盡量保持分布式位置信息的一致性。保持位置信息一致性的開(kāi)銷通過(guò)大量減少后續(xù)文件搜索的開(kāi)銷來(lái)補(bǔ)償。
??? 當(dāng)一個(gè)消息不存在時(shí)，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的每個(gè)文件都被洪泛就會(huì)導(dǎo)致?lián)砣?。WANET文件共享系統(tǒng)允許成員的低移動(dòng)性，重新哈希運(yùn)算后更完善的網(wǎng)絡(luò)結(jié)構(gòu)可抵消移動(dòng)性造成的查詢開(kāi)銷的增加。