郭大鋼，卓明琴，張繼榮

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 順時(shí)針路由

表2 逆時(shí)針路由

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

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

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

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

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

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

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

LPi.successor=Si；

LPi.predecessor=Si.predecessor；

LPi.Predecessor=LPi

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

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

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

3.2 查詢(xún)路由

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

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

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

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

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

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

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

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

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

3.3 節(jié)點(diǎn)退出

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

LPi.successor.predecessor=LPi.predecessor；

LPi.predecessor.successor=LPi.successor

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

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

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

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

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

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

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

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

4.1 節(jié)點(diǎn)加入

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

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

4.2 查詢(xún)路由

查詢(xún)路由的具體流程如下。

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

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

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

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

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

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

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

4.3 節(jié)點(diǎn)退出

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

5 算法仿真

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

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

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

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

圖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)的泛洪搜索機(jī)制仿真

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

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

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

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

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

6 結(jié)束語(yǔ)

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

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

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

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

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

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

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