混合流媒體系統的資源搜索機制研究*

郭大鋼，卓明琴，張繼榮

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

1 引言

傳統的基于P2P（peer to peer，對等）網絡的流媒體系統中，資源的搜索方法是單一的基于結構化搜索或非結構化搜索，并未將這兩種模式進行優勢互補。事實上，針對不同的資源分布，兩種搜索模式體現出不同的特性：結構化搜索模式能準確命中資源，且具有相對確定的路由跳數和響應時間[1]，其缺點在于為了保持網絡邏輯拓撲而引入的動態維護開銷過大且過程較復雜，增大了網絡節點的處理負荷；非結構化搜索模式消除了對邏輯拓撲的依賴所帶來的維護開銷，并且對知名資源具有很好的搜索效率與質量[2]，但其對稀有資源的查找效率不高，且一般響應時間較長。本文研究的混合流媒體系統[3]綜合考慮了這兩種搜索模式的優勢，并進行了改進。根據搜索資源的知名度采取不同的搜索方法，即當搜索稀有資源時采用結構化搜索機制，當搜索熱門資源時則采用非結構化搜索機制，從而大大提高了搜索效率。為了更好地提高搜索命中率，還根據不同的資源知名度，采取不同的策略支持模糊查找。主流模糊查找大體分為2類，即多關鍵碼搜索（multi-keyword query，MKQ）和語義搜索。

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

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

2 混合流媒體系統結構及原理

2.1 混合流媒體系統結構

在混合流媒體系統中，將媒體分發網絡分為2層，分別為骨干網層和邊緣網層。在骨干網層次，采用CDN技術，通過在網絡邊緣合理布置代理緩存服務器（邊緣服務器），將視頻內容推送到靠近用戶端側；在邊緣網層次，以不同的代理緩存服務器為中心，組成多個自治的、相互獨立的P2P流媒體網絡，利用P2P技術進行流媒體的共享，具體系統結構如圖1所示。

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

2.2 系統工作原理

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

LP按照一定的詞條抽取規則對本節點共享的資源進行詞條抽取后，重定向到SP，并向SP傳送其共享資源的詞條，供SP進行本地資源的統計和更新。

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

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

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

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

2.3 主要節點的數據結構定義

2.3.1 SP中的主要數據結構和數據成員

SP中的主要數據結構和成員如下：鄰居SP表、本地資源表、本地節點的拓撲表、泛洪閾值、本地網絡規模、全局拓撲維護周期。

2.3.2 LP中的主要數據結構

在LP中，對傳統的Chord網絡節點路由表（finger table）進行改進，增加了逆向路由。雙向路由表（逆時針路由表，前繼節點，后繼節點，順時針路由表）見表1和表2，其中，i=log3N，N為網絡規模。其他主要數據結構介紹如下。

表1 順時針路由

表2 逆時針路由

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

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

3 改進的Chord搜索機制

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

3.1 節點加入（弱穩定算法）

假設LPi的節點ID為IDi，所屬的SP記為SPi，泛洪閾值為r，網絡規模為N。

當有節點LPi要加入網絡時，通過RRS鑒權后重定向到SPi，向SPi發送本節點資源詞條信息。SPi開始進行拓撲的弱穩定維護，即SPi向LPi發送它的后繼節點Si信息和實時的全局資源變化率η，則LPi及其相關節點進行如下操作：

LPi.successor=Si；

LPi.predecessor=Si.predecessor；

LPi.Predecessor=LPi

同時，LPi復制Si的路由表信息。經過上述弱穩定維護后，LPi成功加入邏輯拓撲環中，并保持了Chord環的完整性，而其他相關的節點暫時不更新自己的路由表。

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

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

3.2 查詢路由

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

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

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

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

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

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

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

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

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

3.3 節點退出

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

LPi.successor.predecessor=LPi.predecessor；

LPi.predecessor.successor=LPi.successor

其他相關節點暫時不更新路由表。

被動退出時，每個節點都會定時向其鄰居節點發送心跳檢測信息，若在規定的時間內未收到鄰居節點LPi的響應，則節點就認為LPi已退出網絡，檢測節點便向SPi發送LPi的退出消息，并刪除鄰居表中LPi的相關項。SPi據此在本地資源數據庫中刪除LPi的節點資源信息，并協助LPi的前繼節點和后繼節點完成連接，而其他的節點則暫時不更新路由表。

3.4 拓撲維護（強穩定算法）

由于網絡節點可以動態加入或退出，為了保持網絡的邏輯拓撲結構，SPi會周期性地進行本地的全局邏輯拓撲維護操作，即強穩定算法，假定其周期為T。

當到達全局拓撲維護周期T時，SPi會根據本地資源數據庫中的節點ID進行排序，生成新的全局拓撲信息，并向每個節點發送它所需要的雙向節點信息，節點會根據此信息更新自己的路由表。此外，每個節點將更新自己的鄰居表，檢測表中的所有鄰居是否全部在線，若通過檢測，在表中刪除已退出網絡的鄰居節點的表項，并為新鄰居添加相應的表項。

4 改進的泛洪搜索機制

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

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

4.1 節點加入

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

圖2 布魯曼濾波器報文結構

4.2 查詢路由

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

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

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

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

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

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

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

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

4.3 節點退出

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

5 算法仿真

實驗中，利用BRITE產生不同節點規模N的底層P2P網絡拓撲，所有節點的資源存放策略和熱門程度均服從Zipf分布。

5.1 改進的Chord搜索機制仿真

采用DHT搜索機制，主要考察節點搜索過程中節點維護的路由表長度、查詢消息轉發次數和搜索成功率。傳統的Chord算法的路由表長度為lbN，改進的Chord算法的路由表長度為2×log3N。在不同的網絡規模下，每個節點所需要維護的路由表長度如圖3所示，在不同的網絡規模下，節點分別利用傳統Chord算法和改進的Chord算法進行資源搜索時的查詢消息轉發，轉發次數對比如圖4所示。由圖3可知，改進的Chord算法的路由表比傳統的Chord算法的路由表長，但增長較緩慢。隨著網絡規模的增大，改進的Chord算法的路由表長度增長并不明顯，但是路由消息轉發次數卻明顯下降，如圖4所示。因此，改進的Chord算法在網絡規模較大時體現出明顯的優越性。

圖3 改進的Chord算法與傳統Chord算法路由表長度比較

圖4 改進的Chord算法與傳統Chord算法最大轉發次數比較

采用MKQ支持模糊查找后，改進的Chord算法的搜索成功率比較如圖5所示，由于引入了MKQ，改進的Chord算法只需在較小的轉發次數內便可達到較高的查找成功率，而傳統Chord算法則需要將近2倍的轉發次數才可達到相同的查找成功率。

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

5.2 改進的泛洪搜索機制仿真

采用BF_Flooding搜索方式，主要考察采用布魯曼濾波器報文結構查詢時，網絡中的冗余消息數量和搜索成功率。假設系統設定迭代最大深度為q，每個節點平均度數為d。在不同的迭代深度和鄰居度數下，查詢消息在網絡中的轉發流量如圖6、圖7所示。

由圖6、圖7可知，隨著網絡規模和節點度數的不斷增加，采用BF_Flooding算法在度數較大時，其查詢消息的轉發量少于傳統泛洪算法的一半，從而大大減小網絡和節點的負擔。

圖6 不同泛洪算法產生的轉發流量（q=3）比較

圖7 不同泛洪算法產生的轉發流量（q=6）比較

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

6 結束語

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

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

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

3 王煜坤.基于CDN和P2P技術的流媒體系統設計.現代計算機,2009(303):179～181

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

5 池靜.Bloom Filter的研究和應用.河北建筑科技學院學報,

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網絡信息搜索方法的應用研究.湘潭大學碩士學位論文,2011