無線Ad-Hoc網絡中P2P文件搜索機制的研究

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

2 系統概述
??? 這里WANET通過節點間的樹形邏輯結構解決共享文件的定位查詢問題，隨著網絡新節點的加入樹形拓撲結構增大。新節點只能通過某一個鄰居節點加入 WANET，每個WANET向外提供唯一的網絡ID，在同一ID的網絡中，每個節點只能擁有一個雙親節點。網絡有一個層次分明的樹狀拓撲結構，這種結構有助于查找文件路徑(即從存放路徑的節點獲得到達文件存儲節點的路由)，以便從文件存儲節點下載文件。

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

3 樹形拓撲的建立和節點文件定位
??? 圖1d表示一個含有7個節點的WANET網絡，在該網絡中，假定節點A、B、C、D、E、F、G提供的共享文件分別為(α1α2)、(β1β2)、(γ1)、(δ1 δ2)、(σ1)、(ε1)、(η1η2)。

3．1 WANET網絡系統樹形拓撲的建立
??? 假設網絡組建初期只有一個初始節點A，要建立一個如圖1d所示的7個節點的WANET文件共享網絡，樹形拓撲的建立過程如下：
??? (1)節點A對自己的兩個共享文件α1、α2哈希后將值映射到整段共享文件哈希鏈上，如圖2a所示。

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

4 WANET網絡中共享文件搜索和下載過程
??? 在圖1d中，假設D作為查詢節點搜索文件η2，D不知道η2的位置，甚至不知道這個文件是否存在，但由H(η2)的可以知道文件存儲在某個節點中。共享文件η2文件的搜索和下載過程如圖4所示。

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

5 與洪泛的比較系統的通信開銷
??? WANET通常用于P2P文件共享，且一般采用洪泛查詢。假定洪泛模型無選擇轉發功能，因此，假定洪泛查詢一旦在網絡中啟動，網絡中所有節點都能收到查詢。該查詢產生的系統開銷O=(n-1)m，其中m表示查詢次數，n表示節點數量。該WANET共享系統中P2P文件搜索和下載模型(圖4)組建網絡拓撲時形成的樹形結構使得即便所查文件不存在，也不會像洪泛一樣造成過多無用的查詢消息，該結構幾乎能發現和訪問網絡中的所有共享文件。

??? 所以。一旦網絡建立。系統開銷與洪泛相比，單個查詢的成本效益明顯合算。
??? 另一方面，由于恢復操作和網絡接入操作產生的系統開銷較大，當每次斷網和網絡接入發生時，會帶來額外開銷(在執行恢復操作中斷開的子節點變為根節點，哈希鏈在整個子網絡中重新分配；網絡接入時，每個接入的節點要對全網絡中的共享文件執行插入請求，產生很大通信流量)，而洪泛不會帶來這樣的開銷。

6 結論
??? 同樣大小的網絡中，在低移動性、需要頻繁搜索文件的WANET上，提出方案的帶寬效率比洪泛高，文件搜索更有效。如果WANET網絡成員移動頻繁且搜索文件不頻繁，則采用洪泛會更好。為避免洪泛和通過單播方式訪問文件，我們盡量保持分布式位置信息的一致性。保持位置信息一致性的開銷通過大量減少后續文件搜索的開銷來補償。
??? 當一個消息不存在時，網絡中每個節點的每個文件都被洪泛就會導致擁塞。WANET文件共享系統允許成員的低移動性，重新哈希運算后更完善的網絡結構可抵消移動性造成的查詢開銷的增加。