混合流媒體系統(tǒng)的資源搜索機制研究*

郭大鋼，卓明琴，張繼榮

（1.西安郵電學(xué)院郵電技術(shù)公司 西安710061；2.中興通訊股份有限公司南京研發(fā)中心 南京210012；3.西安郵電大學(xué)通信與信息工程學(xué)院 西安710121）

1 引言

傳統(tǒng)的基于P2P（peer to peer，對等）網(wǎng)絡(luò)的流媒體系統(tǒng)中，資源的搜索方法是單一的基于結(jié)構(gòu)化搜索或非結(jié)構(gòu)化搜索，并未將這兩種模式進(jìn)行優(yōu)勢互補。事實上，針對不同的資源分布，兩種搜索模式體現(xiàn)出不同的特性：結(jié)構(gòu)化搜索模式能準(zhǔn)確命中資源，且具有相對確定的路由跳數(shù)和響應(yīng)時間[1]，其缺點在于為了保持網(wǎng)絡(luò)邏輯拓?fù)涠氲膭討B(tài)維護(hù)開銷過大且過程較復(fù)雜，增大了網(wǎng)絡(luò)節(jié)點的處理負(fù)荷；非結(jié)構(gòu)化搜索模式消除了對邏輯拓?fù)涞囊蕾囁鶐淼木S護(hù)開銷，并且對知名資源具有很好的搜索效率與質(zhì)量[2]，但其對稀有資源的查找效率不高，且一般響應(yīng)時間較長。本文研究的混合流媒體系統(tǒng)[3]綜合考慮了這兩種搜索模式的優(yōu)勢，并進(jìn)行了改進(jìn)。根據(jù)搜索資源的知名度采取不同的搜索方法，即當(dāng)搜索稀有資源時采用結(jié)構(gòu)化搜索機制，當(dāng)搜索熱門資源時則采用非結(jié)構(gòu)化搜索機制，從而大大提高了搜索效率。為了更好地提高搜索命中率，還根據(jù)不同的資源知名度，采取不同的策略支持模糊查找。主流模糊查找大體分為2類，即多關(guān)鍵碼搜索（multi-keyword query，MKQ）和語義搜索。

在處理稀有資源時，使用結(jié)構(gòu)化搜索過程，結(jié)構(gòu)化P2P網(wǎng)絡(luò)中散列函數(shù)的隨機性和均勻分布性導(dǎo)致它不能很好地支持語義搜索，而稀有資源在網(wǎng)絡(luò)中的數(shù)量較少，采用MKQ所引入的分割發(fā)布對發(fā)布節(jié)點的存儲空間和網(wǎng)絡(luò)帶寬占用量很小，且實現(xiàn)方法簡單，因此在結(jié)構(gòu)化搜索部分，使用MKQ支持模糊查找。

在處理知名資源時，使用非結(jié)構(gòu)化搜索過程，由于資源詞條較為熱門，在網(wǎng)絡(luò)中的存儲量很大，采用MKQ將會大量占用發(fā)布節(jié)點的存儲空間和網(wǎng)絡(luò)帶寬，因此MKQ在此處不適用，而非結(jié)構(gòu)化P2P網(wǎng)絡(luò)能夠很好地支持語義搜索，研究發(fā)現(xiàn)，利用語義相關(guān)度可以較精確地在眾多相似資源詞條中找到與要求最接近的資源詞條，因此在非結(jié)構(gòu)化部分，采用語義相關(guān)度來支持模糊查找。

2 混合流媒體系統(tǒng)結(jié)構(gòu)及原理

2.1 混合流媒體系統(tǒng)結(jié)構(gòu)

在混合流媒體系統(tǒng)中，將媒體分發(fā)網(wǎng)絡(luò)分為2層，分別為骨干網(wǎng)層和邊緣網(wǎng)層。在骨干網(wǎng)層次，采用CDN技術(shù)，通過在網(wǎng)絡(luò)邊緣合理布置代理緩存服務(wù)器（邊緣服務(wù)器），將視頻內(nèi)容推送到靠近用戶端側(cè)；在邊緣網(wǎng)層次，以不同的代理緩存服務(wù)器為中心，組成多個自治的、相互獨立的P2P流媒體網(wǎng)絡(luò)，利用P2P技術(shù)進(jìn)行流媒體的共享，具體系統(tǒng)結(jié)構(gòu)如圖1所示。

系統(tǒng)的整體設(shè)計結(jié)合了互聯(lián)網(wǎng)的結(jié)構(gòu)特點，流媒體中心服務(wù)器（central server，CS）、請求路由服務(wù)器（request routing server，RRS）和分布在各自治系統(tǒng)的邊緣服務(wù)器（edge server，ES）通過骨干網(wǎng)互連組成流媒體CDN，各互聯(lián)網(wǎng)自治系統(tǒng)內(nèi)的邊緣服務(wù)器與客戶機組成與其他自治系統(tǒng)相互獨立的混合流媒體網(wǎng)絡(luò)。邊緣服務(wù)器是混合流媒體網(wǎng)絡(luò)中的超級節(jié)點（super peer，SP），客戶機是葉子節(jié)點（leaf peer，LP）。

2.2 系統(tǒng)工作原理

在上層應(yīng)用中，中心流媒體服務(wù)器負(fù)責(zé)在初始狀態(tài)發(fā)布流媒體資源。RRS負(fù)責(zé)對新加入的LP進(jìn)行身份鑒權(quán)，若鑒權(quán)成功，則根據(jù)LP的IP地址或端口號通過SHA-1算法為其分配一個全局唯一的ID，并向LP指定一個對它最合適的SP。RRS還負(fù)責(zé)在資源知名度更新過程中對CSP（chief super peer）進(jìn)行選擇。

LP按照一定的詞條抽取規(guī)則對本節(jié)點共享的資源進(jìn)行詞條抽取后，重定向到SP，并向SP傳送其共享資源的詞條，供SP進(jìn)行本地資源的統(tǒng)計和更新。

SP根據(jù)全局資源變化率η計算出資源在網(wǎng)絡(luò)中的實時數(shù)量，并與系統(tǒng)預(yù)設(shè)的泛洪閾值r進(jìn)行比較，將資源分別歸入稀有資源集和熱門資源集中。為了支持模糊查找，SP還需向LP發(fā)送實時的η值，LP根據(jù)η值判斷其存儲資源的流行度，并對其中的稀有資源進(jìn)行分割和發(fā)布，以支持MKQ；對于熱門資源，直接以二元組（詞條、節(jié)點IP地址）的形式存儲于本節(jié)點中。

在需要搜索某個流媒體資源時，LP會向SP發(fā)出搜索請求，SP根據(jù)LP輸入的關(guān)鍵碼Key判斷其在網(wǎng)絡(luò)中的流行度，即SP在稀有資源集和熱門資源集中查找含有Key的資源詞條，按照式（1）和式（2）計算兩個集中相關(guān)詞條與Key的平均語義相關(guān)度SRaver。

其中，n為相關(guān)詞條個數(shù)，pi、qj為Key和S相應(yīng)關(guān)鍵碼的隸屬度，p≥1，pi≥0，qj≤1，SR(Keyi,Sj)根據(jù)知網(wǎng)義原預(yù)先設(shè)定[4]。

通過計算，SP優(yōu)先選擇SRaver較大的集合作為候選集，若熱門資源集中相關(guān)詞條與Key的平均語義相關(guān)度大些，則SP選定熱門資源集為候選集，并告知LP采用改進(jìn)的泛洪機制和語義相關(guān)度匹配進(jìn)行模糊搜索，在搜索結(jié)束后，將結(jié)果按照一定的規(guī)則顯示給LP，若LP不滿意，則重新以DHT（distributed hash table）機制和MKQ結(jié)合進(jìn)行模糊搜索。若在全局搜索完成后仍然沒有滿意結(jié)果，SP會向上層CS請求該資源。

2.3 主要節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義

2.3.1 SP中的主要數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)成員

SP中的主要數(shù)據(jù)結(jié)構(gòu)和成員如下：鄰居SP表、本地資源表、本地節(jié)點的拓?fù)浔?、泛洪閾值、本地網(wǎng)絡(luò)規(guī)模、全局拓?fù)渚S護(hù)周期。

2.3.2 LP中的主要數(shù)據(jù)結(jié)構(gòu)

在LP中，對傳統(tǒng)的Chord網(wǎng)絡(luò)節(jié)點路由表（finger table）進(jìn)行改進(jìn)，增加了逆向路由。雙向路由表（逆時針路由表，前繼節(jié)點，后繼節(jié)點，順時針路由表）見表1和表2，其中，i=log3N，N為網(wǎng)絡(luò)規(guī)模。其他主要數(shù)據(jù)結(jié)構(gòu)介紹如下。

表1 順時針路由

表2 逆時針路由

·本節(jié)點資源表（資源詞條列表），鄰居表。由本地LP代為發(fā)布、存儲LP代為發(fā)布的資源及其源節(jié)點信息，此時LP被稱為發(fā)布節(jié)點Distr_ID。

·緩存表（cache table）：存儲之前網(wǎng)內(nèi)成功搜索的資源信息。由于在Distr_ID退出時，它代為發(fā)布的資源就會被轉(zhuǎn)存到它的后繼節(jié)點，因此在緩存表中將存儲它的若干個后繼節(jié)點，可以確保在其退出時，轉(zhuǎn)而訪問它的后繼節(jié)點，進(jìn)而找到資源的源節(jié)點S_ID。

3 改進(jìn)的Chord搜索機制

混合流媒體系統(tǒng)中的結(jié)構(gòu)化搜索（DHT機制）部分采用改進(jìn)的Chord搜索機制，節(jié)點路由表與以往的Chord網(wǎng)絡(luò)節(jié)點路由表不同：路由表節(jié)點間隔以3為基數(shù)；增加了逆向路由表，查找以雙向的方式進(jìn)行；增加了緩存表，若之前查找過相同的資源，便可以快速地再次定位；以MKQ的查找方法來支持DHT部分的模糊查找。

3.1 節(jié)點加入（弱穩(wěn)定算法）

假設(shè)LPi的節(jié)點ID為IDi，所屬的SP記為SPi，泛洪閾值為r，網(wǎng)絡(luò)規(guī)模為N。

當(dāng)有節(jié)點LPi要加入網(wǎng)絡(luò)時，通過RRS鑒權(quán)后重定向到SPi，向SPi發(fā)送本節(jié)點資源詞條信息。SPi開始進(jìn)行拓?fù)涞娜醴€(wěn)定維護(hù)，即SPi向LPi發(fā)送它的后繼節(jié)點Si信息和實時的全局資源變化率η，則LPi及其相關(guān)節(jié)點進(jìn)行如下操作：

LPi.successor=Si；

LPi.predecessor=Si.predecessor；

LPi.Predecessor=LPi

同時，LPi復(fù)制Si的路由表信息。經(jīng)過上述弱穩(wěn)定維護(hù)后，LPi成功加入邏輯拓?fù)洵h(huán)中，并保持了Chord環(huán)的完整性，而其他相關(guān)的節(jié)點暫時不更新自己的路由表。

之后，LPi根據(jù)η進(jìn)行資源發(fā)布：若資源為稀有資源，則將資源詞條以較小單位（如以單個漢字或字符為單位）通過SHA-1算法得到資源標(biāo)識SID，SID和節(jié)點標(biāo)識ID屬于同一個命名空間。LPi根據(jù)SID的值將資源發(fā)布到與SID最接近的ID節(jié)點上。例如，節(jié)點LPs中存有“創(chuàng)世紀(jì)”這一稀有電影資源，則LPs將“創(chuàng)世紀(jì)”的資源屬性按照抽取規(guī)則進(jìn)行抽取后得到資源詞條（如片名、主演、電影情節(jié)和關(guān)鍵字等），將詞條內(nèi)容進(jìn)行分割，如“創(chuàng)世紀(jì)”被分割成“創(chuàng)”、“世”、“紀(jì)”，并分別通過散列函數(shù)發(fā)布到相應(yīng)的節(jié)點IDn、IDk和IDm上，每個發(fā)布節(jié)點包含其所負(fù)責(zé)的關(guān)鍵碼和對應(yīng)的資源詞條以及相應(yīng)的節(jié)點信息。

此外，LPi還將通過探測鄰居節(jié)點與其距離來初始化自己的鄰居表。初始狀態(tài)下，節(jié)點的緩存表為空或保留上次在網(wǎng)內(nèi)的成功查找記錄。

3.2 查詢路由

當(dāng)LPi需要搜索某個流媒體資源時，例如搜索電影“創(chuàng)世紀(jì)”時，用戶只需輸入影片的若干個詞條關(guān)鍵碼便可進(jìn)行模糊查找，具體查找過程如下。

（1）LPi首先查詢本地緩存表，若之前LPi成功查詢過該資源，緩存表中會有相應(yīng)的記錄，LPi可以直接定位到資源發(fā)布節(jié)點Distr_ID，從而找到資源的源節(jié)點S_ID。

（2）若緩存表中無相關(guān)記錄，LPi向所屬SPi發(fā)送查詢請求，SPi通過分析得出候選集，若稀有資源集合中相關(guān)詞條與輸入請求碼字的平均語義相關(guān)度較大，則SPi指示LPi采用DHT搜索機制，即采用改進(jìn)的Chord機制和MKQ結(jié)合進(jìn)行模糊查找。

要論某一部蒙古史詩所產(chǎn)生的時代，就有必要先將它放到世界史詩的框架中加以比較分析，進(jìn)行綜合考量，然后再對其做出推斷。這樣做的理由是，蒙古史詩既然是世界史詩重要的組成部分，那么它就不應(yīng)該游離于世界史詩之外而孤立存在。

（3）若LPi被指示采用DHT機制搜索，它將輸入的關(guān)鍵字分割成單位關(guān)鍵碼并經(jīng)過SHA-1算法得到資源標(biāo)識，如LPi輸入 “世紀(jì)”時，將其分割為 “世”、“紀(jì)”，并調(diào)用SHA-1算法分別得到資源標(biāo)識SID0和SID1，LPi將按照SID0或SID1進(jìn)行搜索。

假設(shè)LPi以SID0開始搜索，首先判斷SID0與IDi+N/2的大小關(guān)系，若SID0小于IDi+N/2，則在順時針路由表中進(jìn)行查找，否則，在逆時針路由表中進(jìn)行查找；查找時首先查看LPi.successor（后繼節(jié)點）的ID，若SID0介于LPi與LPi.successor之間，則資源存儲在LPi.successor上，否則，在路由表中找到小于SID0但最接近它的節(jié)點IDj，將查詢請求轉(zhuǎn)發(fā)給IDj，IDj節(jié)點重復(fù)IDi節(jié)點的過程，經(jīng)過有限輪的轉(zhuǎn)發(fā)和查找，最終找到和SID0最接近的節(jié)點IDk，負(fù)責(zé)SID0的節(jié)點IDk將返回所有包含“世”字的資源列表，LPi在返回的結(jié)果中再根據(jù)關(guān)鍵碼“紀(jì)”搜索詞條中包含“紀(jì)”字的所有詞條，剔除不含“紀(jì)”字的資源詞條，如果還有其他的關(guān)鍵碼則繼續(xù)搜索。此過程可能找到精確的目標(biāo)文件，也可能只是一些符合條件的資源詞條的集合，用戶自己再進(jìn)行選擇。知道的關(guān)鍵碼越多，找到的詞條范圍越小，用戶越容易做選擇。

（4）通過選擇后，LPi將最終的結(jié)果集合{LPs,s≥1}按照匹配度進(jìn)行排序，并檢查LPn∈{LPs,s≥1}是否存在于自己的鄰居表中。若存在，則認(rèn)為LPn距離LPi最近，否則，LPi將計算與各個LPs的距離。LPi將優(yōu)先選擇與自身距離最近且資源匹配度較高的節(jié)點進(jìn)行連接。

（5）若LPi不滿意返回的結(jié)果，則LPi可激活以改進(jìn)的泛洪機制和語義相關(guān)度進(jìn)行模糊查找。當(dāng)搜索完成后，若仍沒有滿意結(jié)果，LPi將上報SP，由SP向上層CS請求資源。

（6）LPi搜索成功后，在緩存表中存儲此次資源搜索相關(guān)信息以備下次使用。緩存表采取LRU（最近最少使用）策略進(jìn)行維護(hù)更新。

3.3 節(jié)點退出

節(jié)點的退出分為主動退出和被動退出。主動退出時，節(jié)點LPi會向所屬的SPi報告自己的退出消息，SPi會在本地資源數(shù)據(jù)庫中刪除LPi所對應(yīng)的節(jié)點及資源信息。此外，LPi向自己的鄰居節(jié)點通知即將離開，鄰居節(jié)點據(jù)此刪除鄰居表中LPi的相關(guān)項，同時，LPi還將向自己的前繼節(jié)點和后繼節(jié)點通知自己即將退出，在LPi的協(xié)助下，進(jìn)行如下操作：

LPi.successor.predecessor=LPi.predecessor；

LPi.predecessor.successor=LPi.successor

其他相關(guān)節(jié)點暫時不更新路由表。

被動退出時，每個節(jié)點都會定時向其鄰居節(jié)點發(fā)送心跳檢測信息，若在規(guī)定的時間內(nèi)未收到鄰居節(jié)點LPi的響應(yīng)，則節(jié)點就認(rèn)為LPi已退出網(wǎng)絡(luò)，檢測節(jié)點便向SPi發(fā)送LPi的退出消息，并刪除鄰居表中LPi的相關(guān)項。SPi據(jù)此在本地資源數(shù)據(jù)庫中刪除LPi的節(jié)點資源信息，并協(xié)助LPi的前繼節(jié)點和后繼節(jié)點完成連接，而其他的節(jié)點則暫時不更新路由表。

3.4 拓?fù)渚S護(hù)（強穩(wěn)定算法）

由于網(wǎng)絡(luò)節(jié)點可以動態(tài)加入或退出，為了保持網(wǎng)絡(luò)的邏輯拓?fù)浣Y(jié)構(gòu)，SPi會周期性地進(jìn)行本地的全局邏輯拓?fù)渚S護(hù)操作，即強穩(wěn)定算法，假定其周期為T。

當(dāng)?shù)竭_(dá)全局拓?fù)渚S護(hù)周期T時，SPi會根據(jù)本地資源數(shù)據(jù)庫中的節(jié)點ID進(jìn)行排序，生成新的全局拓?fù)湫畔?，并向每個節(jié)點發(fā)送它所需要的雙向節(jié)點信息，節(jié)點會根據(jù)此信息更新自己的路由表。此外，每個節(jié)點將更新自己的鄰居表，檢測表中的所有鄰居是否全部在線，若通過檢測，在表中刪除已退出網(wǎng)絡(luò)的鄰居節(jié)點的表項，并為新鄰居添加相應(yīng)的表項。

4 改進(jìn)的泛洪搜索機制

采用改進(jìn)的泛洪搜索機制進(jìn)行泛洪查找，以布魯曼濾波器[5,6]這種隨機數(shù)據(jù)結(jié)構(gòu)進(jìn)行搜索消息的轉(zhuǎn)發(fā)，且與迭代泛洪[7]相結(jié)合，并在搜索過程中通過計算語義相關(guān)度支持資源的模糊查找。將這種基于布魯曼濾波器進(jìn)行的泛洪搜索機制記為BF_Flooding。

假設(shè)布魯曼濾波器共有m位，網(wǎng)絡(luò)規(guī)模為N，為實現(xiàn)布魯曼濾波器結(jié)構(gòu)采用k個散列函數(shù)，允許布魯曼濾波器產(chǎn)生假陽性錯誤的最大值為ε，最小值為f。為了實現(xiàn)f，則k=ln 2×(m/N)；而在散列函數(shù)的個數(shù)取到最優(yōu)時，要讓錯誤率不超過ε，則m≥N×lb e×lb（1/ε）；布魯曼濾波器分別通過添加和查詢操作判斷添加成員和成員是否存在于布魯曼濾波器中。

4.1 節(jié)點加入

節(jié)點LPi加入網(wǎng)絡(luò)的流程大體同第3.1節(jié)所述。此外，LPi會初始化自己的布魯曼濾波器，假設(shè)在初始時刻LPi未發(fā)出資源搜索請求且未收到來自其他節(jié)點的搜索請求，即LPi暫時不會轉(zhuǎn)發(fā)查詢消息，此時，將布魯曼濾波器初始化為全零，否則，將要轉(zhuǎn)發(fā)的目的鄰居節(jié)點加入布魯曼濾波器中。布魯曼濾波器的結(jié)構(gòu)如圖2所示。其中，style默認(rèn)為泛洪消息報文；ID表示報文發(fā)送者的全網(wǎng)ID；message是具體的消息內(nèi)容。

圖2 布魯曼濾波器報文結(jié)構(gòu)

4.2 查詢路由

查詢路由的具體流程如下。

（1）當(dāng)LPi需要查詢某個流媒體資源時，節(jié)點首先查詢本地緩存表，看是否存有該關(guān)鍵字的查詢記錄，若有，則可直接定位到資源的源節(jié)點。

（2）若緩存表中無相關(guān)記錄，LPi向SPi發(fā)出請求，SPi通過分析計算得出候選集，若熱門資源集合中相關(guān)詞條與輸入的請求碼字的平均語義相關(guān)度較大，則SPi指示LPi采用改進(jìn)的泛洪搜索機制，即通過BF_Flooding和語義相關(guān)度計算相結(jié)合進(jìn)行模糊查找。

（3）若LPi被指示采用改進(jìn)的泛洪查找機制，LPi將所要搜索的資源關(guān)鍵字信息、迭代深度和語義相關(guān)度門限φ附入布魯曼濾波器的message項中，將迭代策略設(shè)置為P={a,b,c}(a為第一輪迭代深度；b為第二輪迭代深度；c為最大迭代深度)。LPi按照一定的概率f（本文中取最壞情況f=1進(jìn)行試驗）選擇若干個鄰居節(jié)點作為查詢消息的目的轉(zhuǎn)發(fā)節(jié)點，并對這些節(jié)點進(jìn)行添加操作，將其加入布魯曼濾波器中，然后向這些目標(biāo)轉(zhuǎn)發(fā)節(jié)點以布魯曼濾波器的結(jié)構(gòu)發(fā)起TTL=a的查詢請求。

（4）收到查詢請求的節(jié)點LPj將布魯曼濾波器的message項中的資源關(guān)鍵字信息與本節(jié)點的資源列表進(jìn)行比較，找出相關(guān)項，并按照式（1）計算其與請求關(guān)鍵字的語義相關(guān)度λ，若λ≥φ，則將結(jié)果返回給LPi。LPj按照概率f選擇若干個鄰居節(jié)點作為本輪的目的轉(zhuǎn)發(fā)節(jié)點，繼而對這些目的轉(zhuǎn)發(fā)節(jié)點進(jìn)行查詢操作，判斷所選定的目的轉(zhuǎn)發(fā)節(jié)點是否存在于所接收到的布魯曼濾波器中（將此時收到的布魯曼濾波器記為receiver i，i為當(dāng)前的迭代深度），若不存在，則向這些目的轉(zhuǎn)發(fā)節(jié)點發(fā)送查詢消息，否則，不再向其發(fā)送查詢消息。之后收到查詢消息的節(jié)點都將重復(fù)LPj的操作，直到TTL=a時暫停搜索。此時，處在深度為a的節(jié)點成為下一輪泛洪的前繼節(jié)點，前繼節(jié)點保存receiver a消息，并等待一定的時間t接收LPi是否繼續(xù)搜索的指示。

（5）在完成深度為a的泛洪搜索后，將結(jié)果按語義相關(guān)度降序排列后返回給LPi，LPi對返回結(jié)果進(jìn)行處理。若滿意該結(jié)果，則搜索過程結(jié)束；否則，LPi將啟動下一輪的迭代，進(jìn)行深度為b的泛洪搜索。LPi向存在于布魯曼濾波器中的鄰居節(jié)點發(fā)送第二輪迭代的啟動消息renew，其TTL=b。深度在a以內(nèi)的節(jié)點只接收并轉(zhuǎn)發(fā)這個消息，并不處理。直到深度等于a的前繼節(jié)點收到renew后，丟棄renew并取出receiver a消息，開始進(jìn)行深度為(b-a)的迭代搜索，重復(fù)步驟（4）的過程，直到TTL=c時結(jié)束搜索。由于TTL=c為最大的迭代深度，泛洪搜索到此結(jié)束。

（6）若LPi不滿意返回的結(jié)果，則LPi可激活以改進(jìn)的Chord機制和MKQ結(jié)合進(jìn)行模糊查找。當(dāng)搜索完成后，仍沒有滿意結(jié)果時，LPi將上報SP，由SP向上層CS請求資源。

（7）同DHT搜索一樣，LPi在搜索成功后，將在緩存表中存儲此次資源搜索相關(guān)信息以備下次使用。緩存表采取LRU策略進(jìn)行維護(hù)更新。

4.3 節(jié)點退出

節(jié)點退出分為主動退出和被動退出，LPi的主動和被動退出流程大體同第3.4節(jié)所述，只是其鄰居節(jié)點在LPi退出后，還需將其布魯曼濾波器中的LPi信息刪除。

5 算法仿真

實驗中，利用BRITE產(chǎn)生不同節(jié)點規(guī)模N的底層P2P網(wǎng)絡(luò)拓?fù)?，所有?jié)點的資源存放策略和熱門程度均服從Zipf分布。

5.1 改進(jìn)的Chord搜索機制仿真

采用DHT搜索機制，主要考察節(jié)點搜索過程中節(jié)點維護(hù)的路由表長度、查詢消息轉(zhuǎn)發(fā)次數(shù)和搜索成功率。傳統(tǒng)的Chord算法的路由表長度為lbN，改進(jìn)的Chord算法的路由表長度為2×log3N。在不同的網(wǎng)絡(luò)規(guī)模下，每個節(jié)點所需要維護(hù)的路由表長度如圖3所示，在不同的網(wǎng)絡(luò)規(guī)模下，節(jié)點分別利用傳統(tǒng)Chord算法和改進(jìn)的Chord算法進(jìn)行資源搜索時的查詢消息轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)次數(shù)對比如圖4所示。由圖3可知，改進(jìn)的Chord算法的路由表比傳統(tǒng)的Chord算法的路由表長，但增長較緩慢。隨著網(wǎng)絡(luò)規(guī)模的增大，改進(jìn)的Chord算法的路由表長度增長并不明顯，但是路由消息轉(zhuǎn)發(fā)次數(shù)卻明顯下降，如圖4所示。因此，改進(jìn)的Chord算法在網(wǎng)絡(luò)規(guī)模較大時體現(xiàn)出明顯的優(yōu)越性。

圖3 改進(jìn)的Chord算法與傳統(tǒng)Chord算法路由表長度比較

圖4 改進(jìn)的Chord算法與傳統(tǒng)Chord算法最大轉(zhuǎn)發(fā)次數(shù)比較

采用MKQ支持模糊查找后，改進(jìn)的Chord算法的搜索成功率比較如圖5所示，由于引入了MKQ，改進(jìn)的Chord算法只需在較小的轉(zhuǎn)發(fā)次數(shù)內(nèi)便可達(dá)到較高的查找成功率，而傳統(tǒng)Chord算法則需要將近2倍的轉(zhuǎn)發(fā)次數(shù)才可達(dá)到相同的查找成功率。

圖5 不同Chord算法的搜索成功率

5.2 改進(jìn)的泛洪搜索機制仿真

采用BF_Flooding搜索方式，主要考察采用布魯曼濾波器報文結(jié)構(gòu)查詢時，網(wǎng)絡(luò)中的冗余消息數(shù)量和搜索成功率。假設(shè)系統(tǒng)設(shè)定迭代最大深度為q，每個節(jié)點平均度數(shù)為d。在不同的迭代深度和鄰居度數(shù)下，查詢消息在網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)流量如圖6、圖7所示。

由圖6、圖7可知，隨著網(wǎng)絡(luò)規(guī)模和節(jié)點度數(shù)的不斷增加，采用BF_Flooding算法在度數(shù)較大時，其查詢消息的轉(zhuǎn)發(fā)量少于傳統(tǒng)泛洪算法的一半，從而大大減小網(wǎng)絡(luò)和節(jié)點的負(fù)擔(dān)。

圖6 不同泛洪算法產(chǎn)生的轉(zhuǎn)發(fā)流量（q=3）比較

圖7 不同泛洪算法產(chǎn)生的轉(zhuǎn)發(fā)流量（q=6）比較

引入語義相關(guān)度匹配后的BF_Flooding算法與傳統(tǒng)泛洪算法的搜索成功率的比較如圖8所示。由圖8可知，BF_Flooding算法通過引入語義相關(guān)度來支持模糊查找，提高了查詢的命中率，其成功率穩(wěn)定在80%左右，而傳統(tǒng)泛洪算法遠(yuǎn)遠(yuǎn)低于該值。

6 結(jié)束語

本文主要討論了混合流媒體系統(tǒng)資源搜索機制，由于傳統(tǒng)的搜索機制較單一，沒有考慮到資源知名度對搜索算法的影響，本文采用改進(jìn)的Chord機制和BF_Flooding結(jié)合的混合搜索方式進(jìn)行資源查找，并且為了更好地提高搜索成功率，分別引入MKQ和語義相關(guān)度匹配來支持資源的模糊搜索。由仿真結(jié)果可知，與傳統(tǒng)的Chord搜索算法相比，改進(jìn)的Chord搜索算法在小幅度增加路由表長度的代價下明顯降低了查詢路由時延，并且通過與MKQ結(jié)合，大大提高了搜索成功率。BF_Flooding算法與傳統(tǒng)的泛洪算法相比，隨著迭代深度和節(jié)點度數(shù)的增加，明顯減少了查詢消息在網(wǎng)絡(luò)中的重復(fù)傳輸次數(shù)，大大降低了查詢消息在網(wǎng)絡(luò)中引起的冗余流量，通過引入語義相關(guān)度，支持了資源的模糊搜索，提高了資源搜索的質(zhì)量。

1 施曉秋.非集中式P2P系統(tǒng)中資源搜索與現(xiàn)存問題分析.計算機工程,2007,33(5):91～105

2 崔曉微，董雷剛.非結(jié)構(gòu)化P2P搜索方法分析與展望.大慶師范學(xué)院學(xué)報,2011,31(3):13～16

3 王煜坤.基于CDN和P2P技術(shù)的流媒體系統(tǒng)設(shè)計.現(xiàn)代計算機,2009(303):179～181

4 劉震，鄧蘇，黃宏斌.基于混合P2P網(wǎng)絡(luò)模型的語義檢索方法研究.計算機科學(xué),2009,36(12):60～64

5 池靜.Bloom Filter的研究和應(yīng)用.河北建筑科技學(xué)院學(xué)報,

2003 ,20(4):59～61

6 Bloom B.Space／time tradeoffs in hash coding with allowable errors.Communications of the ACM,1970，13(7):422～426

7 張譽騰.混合P2P網(wǎng)絡(luò)信息搜索方法的應(yīng)用研究.湘潭大學(xué)碩士學(xué)位論文,2011