梁活民 肖文俊 魏文紅

(1.華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東廣州510006;2.華南理工大學(xué)軟件學(xué)院，廣東廣州510006;3.華南理工大學(xué)電子與信息學(xué)院，廣東廣州510640)

對(duì)等覆蓋網(wǎng)絡(luò)已經(jīng)成為網(wǎng)絡(luò)應(yīng)用的重要基礎(chǔ)，而結(jié)構(gòu)化對(duì)等覆蓋網(wǎng)絡(luò)因其可擴(kuò)展性而得到了廣泛的應(yīng)用.結(jié)構(gòu)化對(duì)等覆蓋網(wǎng)絡(luò)通過(guò)分布式哈希表來(lái)計(jì)算被存儲(chǔ)對(duì)象的地址，將鍵值映射到網(wǎng)絡(luò)的節(jié)點(diǎn)，這種工作方式對(duì)于單個(gè)精確文件名的搜索效率非常高，但對(duì)于實(shí)際應(yīng)用中常見的不限定搜索形式的復(fù)雜搜索，結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)則缺乏支持，這使其可應(yīng)用的場(chǎng)合大大減少.這里所謂的復(fù)雜搜索是指不限定搜索形式和語(yǔ)法的搜索(多關(guān)鍵字搜索、前綴搜索、全文搜索等，或這些搜索形式的結(jié)合)，例如在Google上常用的支持并、或的多關(guān)鍵字查詢對(duì)于一般的結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)是非常困難的，對(duì)于更復(fù)雜的正則語(yǔ)言或SQL語(yǔ)言式的查詢更是無(wú)能為力.

以多關(guān)鍵字搜索為例，由于分布式哈希表(DHT)的機(jī)制只支持單關(guān)鍵字搜索，文獻(xiàn)［1］中試圖通過(guò)倒排表來(lái)解決這個(gè)問(wèn)題，但該方法存在索引過(guò)載、單點(diǎn)失效等缺點(diǎn)，而且倒排表可能會(huì)很大，在相關(guān)節(jié)點(diǎn)間傳輸用于交集運(yùn)算的倒排表的代價(jià)也非常高.文獻(xiàn)［2］中使用超立方體作為邏輯的關(guān)鍵字搜索層，這種方法在pin搜索［2］時(shí)效率較高，對(duì)于給定較少關(guān)鍵字的超集搜索效率卻很低，此外這種方法還需要預(yù)先知道整個(gè)關(guān)鍵字集合.所以對(duì)于復(fù)雜的搜索形式目前較合理的方法還是由本地節(jié)點(diǎn)進(jìn)行處理，這就需要將搜索請(qǐng)求高效地分發(fā)到相關(guān)節(jié)點(diǎn).

Cayley圖是對(duì)稱互連網(wǎng)絡(luò)的常用模型［3］，其對(duì)稱性和點(diǎn)傳遞性，使基于Cayley圖構(gòu)造的結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)具有路由算法簡(jiǎn)單、負(fù)載平衡、容錯(cuò)性能較好的特點(diǎn)，有很多結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)［4-5］都是基于Cayley圖構(gòu)造的，CayDHT［6］就是一種基于 Cayley圖的常數(shù)度結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)，具有較好的性質(zhì)，包括O(logN)的路由直徑、路由表項(xiàng)最大為6、較好的容錯(cuò)性能，此外還具有小世界網(wǎng)絡(luò)的部分特性.然而，和其它的結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)一樣，CayDHT對(duì)于不限定搜索形式的復(fù)雜搜索同樣缺乏支持.文中針對(duì)CayDHT拓?fù)涞奶攸c(diǎn)進(jìn)行了分析，在此基礎(chǔ)上提出了一種基于虛擬搜索樹的復(fù)雜搜索算法(VTCS)，在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為N時(shí)，算法具有O(logN)的時(shí)間復(fù)雜度.

1 相關(guān)工作

一般認(rèn)為非結(jié)構(gòu)化對(duì)等覆蓋網(wǎng)絡(luò)適于復(fù)雜搜索，而結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)更適于精確關(guān)鍵字搜索，文獻(xiàn)［7］中對(duì)結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)上的復(fù)雜搜索進(jìn)行了探討，認(rèn)為在結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)上進(jìn)行不限定形式的復(fù)雜搜索是可行的.

洪泛(Flooding)是非結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)常用的搜索方法，同樣可以應(yīng)用于結(jié)構(gòu)化覆蓋網(wǎng)絡(luò).搜索發(fā)起者將查詢發(fā)送給所有鄰居節(jié)點(diǎn)，節(jié)點(diǎn)在接收到查詢請(qǐng)求后返回相關(guān)的查詢信息，并將查詢請(qǐng)求繼續(xù)廣播給自己的鄰居節(jié)點(diǎn)，查詢通常在搜索請(qǐng)求的TTL(Time To Live)值變?yōu)?或者發(fā)現(xiàn)了滿足搜索條件的節(jié)點(diǎn)后終止.改進(jìn)的寬度優(yōu)先搜索(MBFS)［8］和洪泛類似，區(qū)別在于其每次不是將搜索信息廣播到所有鄰居節(jié)點(diǎn)，而是按比例隨機(jī)選擇一部分鄰居節(jié)點(diǎn)進(jìn)行廣播，該方法可以減少一定的廣播信息.而在隨機(jī)步行算法(Random-Walk)［9］中，搜索發(fā)起節(jié)點(diǎn)將搜索請(qǐng)求發(fā)送給自己的M個(gè)鄰居節(jié)點(diǎn)，而其他節(jié)點(diǎn)在收到搜索請(qǐng)求后，隨機(jī)將搜索請(qǐng)求發(fā)送給自己的某個(gè)鄰居節(jié)點(diǎn)，對(duì)于TTL值為K的搜索請(qǐng)求，共有M×K條消息在網(wǎng)絡(luò)上傳播.上述搜索算法非常簡(jiǎn)單，但很容易產(chǎn)生大量的冗余消息，給網(wǎng)絡(luò)帶來(lái)嚴(yán)重的性能問(wèn)題.

文獻(xiàn)［10］中提出了一個(gè)針對(duì) Chord［11］和 Pastry［12］的復(fù)雜搜索算法，稱為遞歸分區(qū)搜索(RPS).搜索發(fā)起節(jié)點(diǎn)根據(jù)路由表的特點(diǎn)將整個(gè)標(biāo)識(shí)符空間分為不相交的區(qū)間，然后將這些區(qū)間分配給路由表中的鄰居節(jié)點(diǎn)負(fù)責(zé)，每個(gè)節(jié)點(diǎn)依此類推將自己負(fù)責(zé)的區(qū)間繼續(xù)分割，然后交由自己的鄰居節(jié)點(diǎn)搜索.RPS算法以較高的概率可在O(logN)的時(shí)間復(fù)雜度內(nèi)遍歷整個(gè)網(wǎng)絡(luò)，但該算法依賴于網(wǎng)絡(luò)節(jié)點(diǎn)路由表中地址空間的劃分和節(jié)點(diǎn)分布的均勻度，并非適用于所有的結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)，而且在節(jié)點(diǎn)分布不均勻時(shí)性能不佳.

2 CayDHT的性質(zhì)

2.1 CayDHT的定義

CayDHT是基于Cayley圖和群半直積方法構(gòu)造的一個(gè)結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)，CayDHT的靜態(tài)拓?fù)涠x如下.

定義1 CayDHT的靜態(tài)拓?fù)溆?Cayley圖Cay(Z2wrZq，S)定義，其中 Z2為基本交換群，Zq(q≥4)為q階循環(huán)群為q階基本交換群的直積，S={sa，s-1a，sb，s-1b，sc，sd}，

CayDHT中的節(jié)點(diǎn)標(biāo)識(shí)符地址空間是一個(gè)二元組(c，r)，其中 c由字符“0”、“1”、“* ”組成，c∈為CayDHT根據(jù)覆蓋網(wǎng)絡(luò)大小選擇的初始化參數(shù).需要保存的資源ID也使用一致哈希函數(shù)映射到一個(gè)2元組，其中的組標(biāo)識(shí)符位長(zhǎng)度為一個(gè)選定的常數(shù)m，一般而言，m＞q，使得 q×2m足夠大，可以為所有需要保存的對(duì)象提供唯一的一個(gè)標(biāo)識(shí)符.

2.2 CayDHT 的拓?fù)湫再|(zhì)

根據(jù)基本拓?fù)涞亩x，任一節(jié)點(diǎn)均有6個(gè)鄰居節(jié)點(diǎn)，分別由該節(jié)點(diǎn)與S中的元素進(jìn)行圈積運(yùn)算得到.由(sa)q=(s-1a)q=(0q，0)，sa和 s-1a的階數(shù)為q，可知對(duì)于?α ∈G，有 α·=α.也就是說(shuō)，對(duì)于任意節(jié)點(diǎn)，通過(guò)與sa進(jìn)行運(yùn)算，可以構(gòu)成一個(gè)包含q個(gè)節(jié)點(diǎn)的環(huán).以q=4為例，從(x1x2x3x4，y)出發(fā)，可以得到(x1x2x3x4，y+1)、(x1x2x3x4，y+2)、(x1x2x3x4，y+3)、(x1x2x3x4，y)的環(huán).由于同一個(gè)環(huán)所有節(jié)點(diǎn)標(biāo)識(shí)符的前半部分是相同的，故文中使用節(jié)點(diǎn)標(biāo)識(shí)符的前半部分來(lái)標(biāo)識(shí)一個(gè)環(huán)，記為sa環(huán)x1x2x3x4.

定義2 ?α∈G，?β∈G，如果有 α·=β，則α和β是同屬于一個(gè)sa環(huán)的節(jié)點(diǎn).給定兩個(gè)環(huán)g0和g1，如果存在 u ∈g0，v∈g1，使得 u=v·sc，那么稱這兩個(gè)sa環(huán)相鄰.

若u與v同屬于一個(gè)sa環(huán)且v與t同屬于一個(gè)sa環(huán)，那么有 u·=v∧v·=t?u·=t，說(shuō)明u和t也處于同一個(gè)環(huán)內(nèi).此外，任意一個(gè)節(jié)點(diǎn)均屬于某個(gè)sa環(huán)，那么易得如下性質(zhì):

性質(zhì)1 G可分為q·2q/q=2q個(gè)點(diǎn)不交的sa環(huán).

根據(jù)sc的特點(diǎn)，對(duì)于任一環(huán)，而在同一個(gè)sa環(huán)中，0≤y＜q，易得性質(zhì)2.

性質(zhì)2 與一個(gè)sa環(huán)相鄰的sa環(huán)共有q個(gè)，且每個(gè)只和自己的環(huán)標(biāo)識(shí)符有一位的不同.

例如，與x1x2x3x4x5環(huán)相鄰的環(huán)為.給定任意兩個(gè)sa環(huán)x1x2…xq和x'1x'2…x'q，可以通過(guò)相鄰的邊傳遞消息:

3 基于虛擬搜索樹的復(fù)雜搜索

為了實(shí)現(xiàn)不限定搜索形式以及全文搜索等復(fù)雜搜索，搜索請(qǐng)求需要傳播到網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn).最簡(jiǎn)單的方法是根據(jù)洪泛的思想，首先在一個(gè)環(huán)內(nèi)傳播消息，然后傳播給所有與該環(huán)相鄰的環(huán)，最終所有的環(huán)都會(huì)收到該消息，但這種方法必然造成大量消息的冗余.

由Cayley圖的對(duì)稱性，可以根據(jù)CayDHT的結(jié)構(gòu)特性來(lái)獲取虛擬的分發(fā)樹.由性質(zhì)1可知，整個(gè)拓?fù)淇梢苑譃?q個(gè)不同的sa環(huán)，而根據(jù)性質(zhì)2可以知道每個(gè)sa環(huán)與哪些環(huán)相鄰.為了將搜索請(qǐng)求傳播到所有節(jié)點(diǎn)，根據(jù)CayDHT的上述特點(diǎn)可以得到一棵覆蓋全部環(huán)的虛擬分發(fā)樹.根據(jù)Cayley圖的對(duì)稱性，可以從任意的源節(jié)點(diǎn)出發(fā)來(lái)遍歷該分發(fā)樹.環(huán)內(nèi)的信息可以通過(guò)由sa生成的邊傳播.而相鄰的兩個(gè)環(huán)有一條由sc生成的邊，因此消息可以通過(guò)這條邊從這個(gè)環(huán)傳播到另一個(gè)環(huán).

為方便起見，首先將子樹節(jié)點(diǎn)標(biāo)識(shí)符定義為形如(i1，i2，i3，…，ik)，其中0 ＜i1＜i2＜i3＜… ＜ ik≤q，im表示 xim≠x'im.例如，若發(fā)起搜索的為 sa環(huán)x1x2x3x4，則sa環(huán)的子樹標(biāo)識(shí)符為(2，4)，文中將發(fā)起搜索的環(huán)分發(fā)樹標(biāo)識(shí)符記為(0).

文中使用如下的規(guī)則來(lái)構(gòu)造分發(fā)樹:分發(fā)樹標(biāo)識(shí)符為(i1，i2，i3，…，ik)的樹節(jié)點(diǎn)，將搜索請(qǐng)求傳播給q-ik個(gè)子樹，這些子樹的標(biāo)識(shí)符為(i1，i2，i3，…，ik，ik+1)，其中 ik＜ ik+1≤q.

根據(jù)性質(zhì)2，這些子樹都是父節(jié)點(diǎn)的鄰居，因此分發(fā)樹是可以構(gòu)造出來(lái)的.

給定任一個(gè)環(huán)，其標(biāo)識(shí)符必然形如(i1，i2，i3，…，ik)且0＜i1＜i2＜i3＜… ＜ik≤q，文中對(duì)標(biāo)識(shí)符的下標(biāo)做歸納法.當(dāng)j=1時(shí)，其標(biāo)識(shí)符為(i1)，由于0＜i1≤q，(i1)是根節(jié)點(diǎn)的子樹.當(dāng) j=2時(shí)，其標(biāo)識(shí)符為(i1，i2)，由于 0 ＜ i1＜ i2≤q，根據(jù)規(guī)則，(i1，i2)是(i1)的子樹.當(dāng) j=k-1 時(shí)，假設(shè)(i1，i2，i3，…，ik-1)是分發(fā)樹中的節(jié)點(diǎn)，由于ik-1＜ik，根據(jù)構(gòu)造規(guī)則，(i1，i2，i3，…，ik)必然是(i1，i2，i3，…，ik-1)的子樹，所以每個(gè)環(huán)都是分發(fā)樹的一個(gè)節(jié)點(diǎn).

圖1是在q=3的情況下x1x2x3作為搜索請(qǐng)求發(fā)起節(jié)點(diǎn)生成的虛擬分發(fā)樹.

圖1 以x1x2x3為根節(jié)點(diǎn)的虛擬搜索樹Fig.1 Spanning tree with root node x1x2x3

根據(jù)Cayley圖運(yùn)算和sc的特性，有，可以確定兩個(gè)環(huán)之間的連接點(diǎn)，所以在得到了環(huán)的分發(fā)樹后，可以非常直觀地得到所有節(jié)點(diǎn)的分發(fā)樹.

每個(gè)搜索請(qǐng)求報(bào)文除了包含搜索表達(dá)式外，還包含4個(gè)參數(shù):發(fā)起搜索請(qǐng)求的源節(jié)點(diǎn)標(biāo)識(shí)符、當(dāng)前環(huán)的源節(jié)點(diǎn)標(biāo)識(shí)符、上一跳節(jié)點(diǎn)的標(biāo)識(shí)符、TTL值.包含TTL值是由于網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)?？赡芎艽螅闹型ㄟ^(guò)TTL值來(lái)控制搜索的分發(fā)范圍.

發(fā)起搜索請(qǐng)求的節(jié)點(diǎn)將報(bào)文發(fā)送給同一個(gè)環(huán)內(nèi)的前后兩個(gè)節(jié)點(diǎn)和自己相鄰環(huán)的節(jié)點(diǎn).節(jié)點(diǎn)收到報(bào)文后，可能會(huì)向3個(gè)相鄰的節(jié)點(diǎn)傳播報(bào)文:同一個(gè)環(huán)內(nèi)的前后兩個(gè)節(jié)點(diǎn)，相鄰環(huán)的節(jié)點(diǎn).節(jié)點(diǎn)根據(jù)報(bào)文包含的參數(shù)來(lái)決定報(bào)文的傳遞:若報(bào)文的上一跳是同環(huán)節(jié)點(diǎn)，且上一跳的環(huán)內(nèi)地址比當(dāng)前節(jié)點(diǎn)的環(huán)內(nèi)地址值大，并且距離小于q/2，則下一跳地址填充為當(dāng)前節(jié)點(diǎn)與sa-1運(yùn)算得到的節(jié)點(diǎn)地址，也即當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，反之則為環(huán)內(nèi)的后一個(gè)節(jié)點(diǎn);若報(bào)文的上一跳與當(dāng)前節(jié)點(diǎn)為非同環(huán)節(jié)點(diǎn)，則將報(bào)文復(fù)制一份，分別傳遞給前后節(jié)點(diǎn).此外，若當(dāng)前節(jié)點(diǎn)的環(huán)內(nèi)地址比當(dāng)前環(huán)的源節(jié)點(diǎn)標(biāo)識(shí)符的環(huán)內(nèi)地址大，當(dāng)前節(jié)點(diǎn)復(fù)制一份報(bào)文并發(fā)送給相鄰環(huán)的節(jié)點(diǎn).

下面給出搜索樹的分發(fā)算法.其中msg.source為搜索報(bào)文的源節(jié)點(diǎn)，msg.localSource為報(bào)文在一個(gè)sa環(huán)內(nèi)傳播時(shí)的環(huán)內(nèi)地址，msg.previous為報(bào)文的上一跳節(jié)點(diǎn)地址，msg.ttl為報(bào)文的TTL值，this為當(dāng)前節(jié)點(diǎn)的地址.

從根節(jié)點(diǎn)到子樹(i1，i2，…，ik-1，ik)的路徑長(zhǎng)度可以按如下方法計(jì)算.從根節(jié)點(diǎn)到(i1)需要經(jīng)過(guò)i1-1條由sa生成的邊和1條由sc生成的邊，路徑長(zhǎng)度為i1，而對(duì)于非根節(jié)點(diǎn)，從(i1，i2，…，ik-1)到(i1，i2，…，ik-1，ik)需要經(jīng)過(guò)ik-ik-1條由sa生成的邊和1條由sc生成的邊，路徑長(zhǎng)度為ik-ik-1+1，因此從根節(jié)點(diǎn)到子樹(i1，i2，…，ik-1，ik)的路徑長(zhǎng)度是 i1+(i2-i1+1)+…+(ik-ik-1+1)=ik+k-1，以圖2為例，從(0)到(2)的路徑為.根據(jù)分發(fā)樹的構(gòu)造規(guī)則，處于樹葉位置的環(huán)標(biāo)識(shí)符最后分量都是q，k值最大也為q，因此，從根節(jié)點(diǎn)到任一葉環(huán)的最大路徑長(zhǎng)度為2q-1.考慮消息在環(huán)內(nèi)傳播需要的路徑長(zhǎng)度，可知從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑長(zhǎng)度不大于那么有性質(zhì)3.

性質(zhì)3 搜索樹的樹高為

由于節(jié)點(diǎn)總數(shù)為 N=q×2q，由5q/2＜5/2×log(q×2q)，那么該搜索樹的復(fù)雜度為O(logN).而由于Cayley圖的對(duì)稱性，搜索可以由任意節(jié)點(diǎn)發(fā)起，并且根據(jù)消息的參數(shù)和當(dāng)前節(jié)點(diǎn)的地址就可以知道虛擬分發(fā)樹中下一跳節(jié)點(diǎn)的地址，整個(gè)過(guò)程不需要維護(hù)實(shí)際分發(fā)樹的結(jié)構(gòu).

4 仿真和性能分析

在CayDHT的環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，比較了VTCS和Flooding、Random-Walk 3種方法的性能，如搜索時(shí)延、網(wǎng)絡(luò)負(fù)載和搜索覆蓋率等方面.在整個(gè)實(shí)驗(yàn)中，按照不同的節(jié)點(diǎn)規(guī)模生成隨機(jī)的節(jié)點(diǎn)標(biāo)識(shí)符，然后將節(jié)點(diǎn)加入到網(wǎng)絡(luò)中，在測(cè)試過(guò)程中假定節(jié)點(diǎn)穩(wěn)定，不存在退出和加入的情況.網(wǎng)絡(luò)節(jié)點(diǎn)間的時(shí)延隨機(jī)選定并服從5～10 ms之間的正態(tài)分布，節(jié)點(diǎn)每次只能發(fā)送一個(gè)數(shù)據(jù)包，發(fā)送數(shù)據(jù)包的間隔時(shí)延為0.2ms，網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模為2048.

在實(shí)驗(yàn)1中比較了 Flooding、Random-Walk和VTCS的搜索時(shí)延和網(wǎng)絡(luò)負(fù)載，其中搜索時(shí)延由發(fā)起搜索到搜索成功之間的時(shí)間差來(lái)衡量，而網(wǎng)絡(luò)負(fù)載由節(jié)點(diǎn)傳播的平均消息數(shù)來(lái)衡量.實(shí)驗(yàn)隨機(jī)選定5個(gè)節(jié)點(diǎn)標(biāo)記為含有待搜索資源.Random-Walk方法的初始鄰居數(shù)(Neigh)設(shè)定為20.在實(shí)驗(yàn)中每隔10ms就隨機(jī)選定一個(gè)節(jié)點(diǎn)發(fā)起搜索，實(shí)驗(yàn)共進(jìn)行10次并取平均值，結(jié)果如圖2所示.從圖2可以看到，以時(shí)延最小的Flooding為基準(zhǔn)，VTCS的時(shí)延比Flooding大17%，而 Random-Walk的時(shí)延幾乎是Flooding的4.6倍.網(wǎng)絡(luò)負(fù)載最小的是 VTCS，Random-Walk的網(wǎng)絡(luò)負(fù)載比VTCS大了近70%，負(fù)載最大的Flooding是 VTCS的7倍.結(jié)果表明，F(xiàn)looding雖然具有較小的搜索路徑長(zhǎng)度，但會(huì)產(chǎn)生很多冗余消息，因此網(wǎng)絡(luò)負(fù)載比較大，而Random-Walk在擴(kuò)散的每一跳增加搜索的節(jié)點(diǎn)數(shù)都是常數(shù)，使得其負(fù)載遠(yuǎn)比Flooding小，但卻需要更多的跳數(shù)才能搜索所需的資源，而VTCS在時(shí)延和負(fù)載上都較小.

圖2 搜索時(shí)延和網(wǎng)絡(luò)負(fù)載Fig.2 Lookup delay and network loads

實(shí)驗(yàn)2中比較了Flooding、Random-Walk和VTCS在不同參數(shù)下的搜索覆蓋率，其中搜索覆蓋率由搜索到的資源和資源總數(shù)的比率表示.本實(shí)驗(yàn)隨機(jī)選定10%的節(jié)點(diǎn)標(biāo)記為含有待搜索資源.實(shí)驗(yàn)通過(guò)對(duì)TTL值進(jìn)行調(diào)節(jié)，記錄搜索到的資源數(shù)占所有資源的比率，每個(gè)參數(shù)下的實(shí)驗(yàn)共進(jìn)行10次并取平均值，結(jié)果如圖3所示.圖3中F表示Flooding，R表示Rondom-Walk，V表示 VTCS，括號(hào)中的數(shù)值為 TTL值.從圖3可以看到，雖然Random Walk的網(wǎng)絡(luò)負(fù)載要比Flooding低，但為了實(shí)現(xiàn)較大的搜索覆蓋，Random Walk所需的TTL值遠(yuǎn)比其他兩種方法大，且跳數(shù)的增多顯然會(huì)導(dǎo)致時(shí)延的增大.而VTCS與Flooding的搜索覆蓋率相差無(wú)幾，在TTL為16時(shí)這兩者的搜索覆蓋率都大約為100%.考慮到Flooding的網(wǎng)絡(luò)負(fù)載遠(yuǎn)比VTCS要大，VTCS是一個(gè)較為合理的方案.

圖3 不同TTL下的搜索覆蓋率Fig.3 Search success rates with varous TTL

VTCS采用TTL值來(lái)限定搜索范圍，在實(shí)驗(yàn)3中對(duì)兩者的關(guān)系進(jìn)行了分析.顯然，發(fā)起搜索的節(jié)點(diǎn)設(shè)置的初始TTL值越大，可以搜索的范圍就越大，搜索到的節(jié)點(diǎn)也越多.根據(jù)性質(zhì)3，當(dāng)節(jié)點(diǎn)規(guī)模為2048時(shí)，VTCS生成的虛擬搜索樹高為20，那么設(shè)置TTL初始值為19就可以搜索完整個(gè)網(wǎng)絡(luò).圖4給出了TTL值與搜索范圍的關(guān)系，從圖中可以看到兩者的關(guān)系不是線性的，在TTL值小于10或大于15的時(shí)候曲線相當(dāng)平緩，節(jié)點(diǎn)總數(shù)變化不大.相對(duì)的，在TTL大于10時(shí)曲線突然變陡，意味著TTL值在這個(gè)范圍的細(xì)小增量會(huì)導(dǎo)致搜索節(jié)點(diǎn)的急劇增加，如TTL值為12比TTL值為11時(shí)的節(jié)點(diǎn)數(shù)增加約35%，F(xiàn)looding也存在同樣的問(wèn)題［9］.因此，通過(guò)TTL值來(lái)控制搜索范圍存在一定的缺陷.

圖4 不同TTL時(shí)節(jié)點(diǎn)搜索路徑長(zhǎng)度的分布情況Fig.4 Distrilution of path length with vanious TTL

5 結(jié)語(yǔ)

文中通過(guò)分析CayDHT拓?fù)涞奶攸c(diǎn)，提出了一種復(fù)雜搜索算法VTCS，不依賴于額外的樹結(jié)構(gòu)，根據(jù)消息附帶的參數(shù)就可以在O(logN)的時(shí)間復(fù)雜度內(nèi)通過(guò)虛擬的分發(fā)樹將搜索請(qǐng)求傳播到整個(gè)網(wǎng)絡(luò)上，與洪泛、隨機(jī)步行等方法相比具有一定的優(yōu)勢(shì).此外，雖然整個(gè)搜索算法的時(shí)間復(fù)雜度為O(logN)，但在網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模很大的情況下，搜索延遲及網(wǎng)絡(luò)負(fù)載仍然會(huì)比較大，因此通過(guò)控制搜索的節(jié)點(diǎn)范圍(分區(qū)搜索)是很重要的，而通過(guò)TTL參數(shù)來(lái)實(shí)現(xiàn)分區(qū)搜索還存在一定的缺陷，因此未來(lái)的工作需要尋找更好的方法來(lái)實(shí)現(xiàn)分區(qū)搜索，以減少搜索對(duì)網(wǎng)絡(luò)造成的影響.

［1］Reynolds P，Vahdat A.Efficient peer-to-peer keyword searching［C］∥Proceeding of the ACM/IFIP/USENIX 2003 International Conference on Middleware.Rio de Janeiro:Springer，2003:21-40.

［2］Joung Y，Yang L，F(xiàn)ang C，et al.Keyword search in dhtbased peer-to-peer networks［J］.IEEE Journal on Selected Areas in Communications，2007，25:46-61.

［3］Xiao W，Parhami B.Cayley graphs as models of deterministic small-world networks［J］.Information Processing Letters，2006，97(3):115-117.

［4］Qu C，Nejdl W，Kriesell M.Cayley DHTs-a group-theoretic framework for analyzing DHTs based on cayley graphs［C］∥Proceedings of the Second International Symposium on Parallel and Distributed Processing and Applications.Hong Kong:Springer，2004:914-925.

［5］魏文紅，肖文俊.一種具有小世界特征的結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)［J］.華南理工大學(xué)學(xué)報(bào):自然科學(xué)版，2009，37(10):66-72.Wei Wen-hong，Xiao Wen-jun.A Structured P2P overlay network with small-world characteristics［J］.Journal of South China University of Technology:Natural Science E-dition，2009，37(10):66-72.

［6］梁活民，肖文俊.一種具有小世界網(wǎng)絡(luò)特征的常數(shù)度結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33(9):1541-1547.Liang Huo-min，Xiao Wen-jun.A novel structured overlay network with constant degree and small-world features［J］.Chinese Journal of Computers，2010，33(9):1541-1547.

［7］Hautakorpi J，Schultz G.A feasibility study of an arbitrary search in structured peer-to-peer networks［C］∥Proceedings of the 19th International Conference on Computer Communications and Networks.Zurich:IEEE，2010:1-8.

［8］Kalogeraki V，Gunopulos D，Zeinalipour-Yazti D.A local search mechanism for peer-to-peer networks［C］∥Proceedings of the 11th International Conference on Information and Knowledge Management.McLean:ACM，2002:300-307.

［9］Lv Q，Cao P，Cohen E，et al.Search and replication in unstructured peer-to-peer networks［C］∥Proceedings of the 16th ACM International Conference on Supercomputing.New York:ACM，2002:84-95.

［10］Vishnevsky V，Safonov A，Yakimov M，et al.Scalable blind search and broadcasting over distributed Hash tables［J］.Computer Communications，2008，31(2):292-303.

［11］Stoica I，Morris R，Liben-Nowell D，et al.Chord:a scalable peer-to-peer lookup service for internet applications［J］.IEEE/ACM Transactions on Networking，2003，11(1):17-32.

［12］Rowstron A，Druschel P.Pastry:scalable，distributed object location and routing for large-scale peer-to-peer systems［C］∥Proceedings of IFIP/ACM International Conference on Distributed Systems Platforms.Heidelberg:Springer，2001:329-350.