无线Ad-Hoc网络中P2P文件搜索机制的研究

(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文件共享系统允许成员的低移动性，重新哈希运算后更完善的网络结构可抵消移动性造成的查询开销的增加。