姜慧霖

(商丘師范學(xué)院計算機與信息技術(shù)學(xué)院，河南 商丘 476000)

0 引言

隨著寬帶網(wǎng)的普及，流媒體作為互聯(lián)網(wǎng)中重要的數(shù)據(jù)業(yè)務(wù)而被廣泛應(yīng)用[1-7]。傳統(tǒng)中心化服務(wù)器/客戶端的系統(tǒng)模型受限于服務(wù)器帶寬資源，無法滿足大規(guī)模增長的用戶需求，從而限制了流媒體業(yè)務(wù)的大規(guī)模應(yīng)用[8]。P2P(Peer-to-Peer)技術(shù)很好地解決了上述問題[9]。網(wǎng)絡(luò)中節(jié)點之間相互共享本地存儲的流媒體資源能夠大大減少服務(wù)器端帶寬的壓力。無線移動網(wǎng)絡(luò)作為下一代網(wǎng)絡(luò)的發(fā)展趨勢之一，無線移動網(wǎng)絡(luò)的流媒體技術(shù)已經(jīng)得到了國內(nèi)外眾多學(xué)者的廣泛研究[10-12]。無線mesh網(wǎng)絡(luò)作為一種重要的無線移動網(wǎng)絡(luò)，提供了一個低成本的Internet接入方式，通過增加mesh路由器的方式擴大無線網(wǎng)絡(luò)的覆蓋范圍，多跳接入的方式使得mesh網(wǎng)絡(luò)具有良好的可擴展性[11-12]。根據(jù)mesh網(wǎng)絡(luò)的特性，這種快速便捷的接入Internet方式使得mesh能夠為移動或非移動設(shè)備提供多種服務(wù)。然而，在大多數(shù)P2P-VoD(Peer-to-Peer Video-on-Demand)系統(tǒng)中[6，11]，為了支持用戶的VCR操作，通常利用Gossip協(xié)議來查詢用戶所需要的資源?；贕ossip協(xié)議的資源查詢方法不僅效率低(增加用戶的播放等待延時)，而且會導(dǎo)致網(wǎng)絡(luò)中散布著大量的查詢消息，從而增加網(wǎng)絡(luò)的負(fù)載。例如，文獻(xiàn)[13]提出了一個在無線Ad Hoc網(wǎng)絡(luò)下基于P2P的資源共享系統(tǒng)。該系統(tǒng)通過維護(hù)覆蓋網(wǎng)絡(luò)中節(jié)點行為能夠提高資源共享效率。然而，通過交互消息維護(hù)移動節(jié)點，系統(tǒng)需要消耗大量的計算資源和帶寬資源，同時泛洪的資源查詢策略也加重了網(wǎng)絡(luò)的負(fù)擔(dān)。文獻(xiàn)[8]提出了一個mesh網(wǎng)絡(luò)下資源分享系統(tǒng)MESHCHORD(視頻資源是一種特殊的資源)，利用位置感知技術(shù)，將位置相近的mesh路由器組織成為一個Chord結(jié)構(gòu)。當(dāng)移動節(jié)點查詢所需要的資源時，通過Gossip協(xié)議散播查詢者的查詢消息，并利用跨層技術(shù)[8]，使每個移動節(jié)點在接收到查詢消息后將該消息從數(shù)據(jù)鏈路層直接傳遞至應(yīng)用層，從而判斷是否能夠為查詢者提供服務(wù)。雖然MESHCHORD提高了資源查詢效率并降低了網(wǎng)絡(luò)的負(fù)載，但它也無法很好地解決Gossip協(xié)議所帶來的查詢效率低以及網(wǎng)絡(luò)負(fù)載高的問題。

針對基于Gossip協(xié)議的資源查找算法中存在的不足，本文設(shè)計了一個mesh網(wǎng)絡(luò)下P2P-VoD系統(tǒng)的資源查找算法。受文獻(xiàn)[7]中資源分享系統(tǒng)結(jié)構(gòu)的啟發(fā)，本文所提出的算法也采用兩層結(jié)構(gòu)。如圖1所示，利用Chord協(xié)議[7]和每個mesh路由器之間的物理距離(物理空間中的歐氏距離)來計算 key值(mesh路由器的位置可由“位置感知”方法獲得，如文獻(xiàn)[7]中所述)，將mesh路由器組織成為一個Chord環(huán)[14]，并作為頂層邏輯結(jié)構(gòu)。環(huán)中每個元素的前驅(qū)與后繼均與當(dāng)前元素在物理空間中的距離最近;移動節(jié)點為底層結(jié)構(gòu)。利用跨層的思想，當(dāng)每個移動節(jié)點進(jìn)入到一個mesh路由器的覆蓋范圍內(nèi)時，該移動節(jié)點將自身所攜帶的資源信息發(fā)送給該mesh路由器，mesh路由器就能在本地構(gòu)建一個可利用的資源列表。當(dāng)移動節(jié)點需要查詢資源時，將查詢消息首先發(fā)送給mesh路由器，由mesh路由器為其查找距離最近且擁有資源的服務(wù)節(jié)點。

圖1 兩層的P2P-VoD系統(tǒng)

1 P2P-VoD系統(tǒng)設(shè)計

mesh網(wǎng)絡(luò)下P2P-VoD系統(tǒng)中通常包含移動節(jié)點、mesh路由器及流媒體服務(wù)器等元素。

(1)移動節(jié)點不僅能夠在物理空間中實現(xiàn)隨機的位移，而且還能夠通過一跳或多跳的方式接入并獲取流媒體資源。當(dāng)移動節(jié)點進(jìn)入到mesh路由器的覆蓋范圍內(nèi)，需要向mesh路由發(fā)送消息。如圖2所示，根據(jù)跨層思想，移動節(jié)點除了要向mesh路由器提供本身的節(jié)點信息外，還需要提供本地存儲的可利用的資源信息，也就是說，移動節(jié)點所傳送的消息中不僅包含了自身IP層的信息，也包含了應(yīng)用層的信息。每個移動節(jié)點Ni可以由一個三元組node=(IP，Res，MRIPL)表示，其中IP為移動節(jié)點的IP地址;Res為本地存儲的資源，MRIPL為mesh路由器IP列表，表示移動節(jié)點位于MRIPL中元素的覆蓋范圍內(nèi)。當(dāng)Ni離開mesh路由器的覆蓋范圍后，也需要向該路由器發(fā)送離開消息。因此，移動節(jié)點進(jìn)入或離開mesh路由器的通知消息emessage可被定義為一個二元組emessage=(flag，node)，其中flag為節(jié)點行為的標(biāo)志位，當(dāng)flag=0時，表明當(dāng)前移動節(jié)點進(jìn)入到mesh路由器覆蓋范圍，若flag=1，則表明當(dāng)前移動節(jié)點離開mesh路由器覆蓋范圍;node為節(jié)點信息三元組。

圖2 跨層示意圖

(2)mesh路由器主要負(fù)責(zé)管理覆蓋范圍內(nèi)的移動節(jié)點，并且接收來自于移動節(jié)點的請求消息，幫助移動節(jié)點查找請求的資源?？稍O(shè)MRS=(mr1，mr2，…，mrn)為一個非空有限集合，其中MRS為mesh路由器集合。每個mesh路由器mri都維護(hù)著一個三元組 mr=(IP，NL，chordT)，其中 IP 為 mesh路由器的IP地址;NL為在其覆蓋范圍內(nèi)的移動節(jié)點列表，NL=(node1，node2，…，nodem)。chordT=(MI1，MI2，…，MIk)為mesh路由器需要維護(hù)的Chord結(jié)構(gòu)信息，且，其中，IP 為 mesh路由器的IP地址;ResL為mesh路由器的資源列表，該列表通常由各個mesh路由器通過交互消息定時更新;key為mesh路由器的關(guān)鍵字，key的值由公式(1)得出:

其中DHT()為構(gòu)建Chord環(huán)的分布式哈希函數(shù)[10]，該函數(shù)能夠確保key在Chord環(huán)中的唯一性。dis為兩個路由器之間在物理空間中的歐氏距離，其值可由公式(2)得出:

MRS中所有元素均可根據(jù)兩個元素之間的物理距離來計算每個元素的key，并構(gòu)建成為一個Chord環(huán)。此處構(gòu)建一個基本的Chord環(huán)，具體的構(gòu)建過程不再贅述?；谖锢砜臻g的歐氏距離來構(gòu)建Chord環(huán)，主要是因為在無線網(wǎng)絡(luò)中，通信雙方的距離越近，在兩者之間的通信路徑上的中間節(jié)點越少，若兩者均在彼此的信號覆蓋范圍內(nèi)，那么兩者之間則無中間節(jié)點(即一跳到達(dá))，通信質(zhì)量及數(shù)據(jù)傳輸效率即為最優(yōu)。若存在多個資源擁有者，那么與請求者之間擁有距離最近的物理距離者為最優(yōu)服務(wù)源。移動節(jié)點的請求消息req由一個二元組表示，即req=(IP，res)，其中IP為請求節(jié)點的IP，res為請求節(jié)點所需要的資源。

mesh路由器盡可能地為請求節(jié)點查找與其距離最近的mesh路由器下的資源擁有者。mesh路由器的返回消息resp中包含了含有請求資源節(jié)點的IP地址列表，即 resp=(IP1，IP2，…，IPk)。因此，mesh 路由器利用構(gòu)建的Chord結(jié)構(gòu)實現(xiàn)通信雙方之間的物理距離最短，如圖3所示。

圖3 mesh網(wǎng)絡(luò)資源共享示意圖

(3)流媒體服務(wù)器主要負(fù)責(zé)為請求節(jié)點傳輸源數(shù)據(jù)。若在P2P網(wǎng)絡(luò)中沒有可利用的節(jié)點為資源請求者提供服務(wù)，則由服務(wù)器為該請求節(jié)點傳輸數(shù)據(jù)。則，video=(res1，res2，…，resm)，為一個非空有限集合，其中video為服務(wù)器中存儲的流媒體資源集合，包含了m個流媒體資源。

2 流媒體資源的查詢算法

下面將詳細(xì)描述資源查詢算法:

(1)當(dāng)節(jié)點nodei需要獲取資源resi時，根據(jù)三元組中存儲的當(dāng)前mesh路由器的IP地址向其發(fā)送請求消息reqi。

(2)mesh路由器mri收到reqi后，首先遍歷本地的資源列表NL。若NL中存在能夠滿足nodei請求的資源擁有者nodej，則將nodej加入到結(jié)果集合resultset中。遍歷結(jié)束后，將resultset中元素添加至返回消息resp中，并返回至nodei，執(zhí)行(6)。

(3)若mesh路由器無法從本地查找出能夠滿足nodei的資源，則遍歷chordT。遍歷的優(yōu)先級順序為根據(jù)key值由小到大遍歷。

(4)若chordT中包含了nodei所請求的資源，則mri將reqi轉(zhuǎn)發(fā)至擁有該資源的mesh路由器mrj，由mrj為nodei查找擁有資源的移動節(jié)點，并將查詢結(jié)果添加至resp中，并返回至nodei，執(zhí)行(6)。

(5)若chordT中未包含nodei所請求的資源，則將reqi轉(zhuǎn)發(fā)至chordT中 key值最大的元素 mrx，由mrx查找其余個mesh路由器。若查詢成功，則將查詢結(jié)果添加至resp中，返回nodei，執(zhí)行(6);否則，通知nodei查詢失敗，由nodei請求服務(wù)器提供資源，執(zhí)行(7)。

(6)nodei收到resp后，逐一向resp中元素發(fā)送連接請求，并準(zhǔn)備接收數(shù)據(jù)。

(7)結(jié)束。

3 實驗結(jié)果及分析

系統(tǒng)的仿真實驗在NS2下完成。移動節(jié)點數(shù)量為500，在x=2000，y=2000的區(qū)域中隨機移動，每個移動節(jié)點的無線信號覆蓋范圍為200單位距離，移動速度在0到20單位距離/秒隨機分配，節(jié)點的移動方向為隨機且停留時間為1秒，每個節(jié)點的帶寬設(shè)置為2Mbps。在仿真中，系統(tǒng)設(shè)定100個節(jié)點隨機請求不同資源;媒體服務(wù)器的數(shù)量為1;mesh路由器數(shù)量為9，信號覆蓋范圍為400單位距離;流媒體服務(wù)器中包含了20個資源，即m=20;mesh路由器與服務(wù)器的帶寬分別為6Mbps和11Mbps;每個數(shù)據(jù)流的速率為450kbps;系統(tǒng)定義的4種消息大小均為500字節(jié);仿真時間為300秒。本文從流媒體數(shù)據(jù)傳輸平均延時和丟包率以及資源查詢響應(yīng)時間3個方面與文獻(xiàn)[7]進(jìn)行了對比，并且設(shè)定兩個系統(tǒng)的仿真環(huán)境相同。

圖4 流媒體數(shù)據(jù)傳輸平均延時對比圖

圖5 流媒體數(shù)據(jù)傳輸平均丟包率對比圖

圖6 流媒體資源查詢平均響應(yīng)時間對比圖

如圖4所示，隨著請求節(jié)點的數(shù)量不斷增加，兩個算法的流媒體數(shù)據(jù)傳輸延時也在不斷增長。從曲線的高度及增長幅度來看，本文提出的mesh網(wǎng)絡(luò)下P2P-VoD資源查詢算法要明顯低于MESHCHORD。這是因為mesh路由器能夠為請求節(jié)點查找與其物理距離最近的資源擁有者，在數(shù)據(jù)傳輸過程中，數(shù)據(jù)所經(jīng)歷的中間節(jié)點數(shù)量(即數(shù)據(jù)被轉(zhuǎn)發(fā)的次數(shù))較低，從而數(shù)據(jù)傳輸延時也較低。MESHCHORD則通過Gossip協(xié)議泛洪查找資源，無法區(qū)分資源擁有者之間距離上遠(yuǎn)近。因此，MESHCHORD的曲線要高于本文所提出的算法。

如圖5所示，根據(jù)在數(shù)據(jù)傳輸過程中統(tǒng)計每10個節(jié)點請求資源的傳輸?shù)臄?shù)據(jù)總量及丟失的數(shù)據(jù)包個數(shù)之比。本文所提出的算法在平均丟包率上也要好于MESHCHORD。這也是因為mesh路由器能夠為請求節(jié)點查詢與請求者距離最近的服務(wù)節(jié)點，近的物理距離能夠減少數(shù)據(jù)在傳輸過程中的轉(zhuǎn)發(fā)次數(shù)，從而減少了丟包率。圖4與圖5的數(shù)據(jù)是一致的。

圖6顯示了統(tǒng)計每10個請求的查詢響應(yīng)時間的平均值。在本文所提出的算法中，最好情況為若當(dāng)前mesh路由器含有請求的資源時，則立刻返回至請求節(jié)點。最差情況為通過ChordT中key值最大元素查找全表的資源，請求被轉(zhuǎn)發(fā)3次。而MESHCHORD依賴于Gossip協(xié)議進(jìn)行泛洪查找，則查詢響應(yīng)時間無法被嚴(yán)格地限定。若資源與請求節(jié)點距離較遠(yuǎn)，那么泛洪消息需要經(jīng)過多個節(jié)點散播才能被資源擁有者發(fā)現(xiàn)。若資源在其周圍一跳范圍內(nèi)，則請求節(jié)點也可立刻獲得所需要的數(shù)據(jù)。然而，所需要的資源存在一跳范圍內(nèi)的概率較低，因此，泛洪方法在查詢效率上顯然低于本文所提出的方法。

4 結(jié)束語

本文設(shè)計一個在mesh網(wǎng)絡(luò)下P2P-VoD資源查詢算法，主要用來解決在無線網(wǎng)絡(luò)環(huán)境下使用Gossip協(xié)議進(jìn)行資源查詢所帶來的查詢效率低的問題。通過感知mesh路由器在物理空間中的位置，利用DHT算法將其組織成為一個Chord結(jié)構(gòu)，不僅縮短了對資源請求消息的響應(yīng)時間，而且減少數(shù)據(jù)的發(fā)送者和接收者之間的距離，提高數(shù)據(jù)的傳輸效率，減少數(shù)據(jù)傳輸?shù)牡却龝r延。下一步工作將提高流媒體數(shù)據(jù)在異構(gòu)網(wǎng)絡(luò)中的傳輸性能。

[1] Shen Z，Luo J，Zimmermann R，et al.Peer-to-peer media streaming insights and new developments[J].Proceedings of the IEEE，2011，99(12):2089-2109.

[2] 李海明，徐敬，黎燕飛.基于P2P視頻點播技術(shù)的流媒體平臺設(shè)計與開發(fā)[J].計算機與現(xiàn)代化，2011(4):57-60.

[3] 戴琦，夏青，顧春華，等.基于P2P的視頻點播系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機與現(xiàn)代化，2010(8):44-46.

[4] 袁雪萍，周芳，陳璐.基于Gossip協(xié)議的P2P流媒體算法優(yōu)化[J].計算機與現(xiàn)代化，2010(10):139-141.

[5] 夏敏，吳中海，楊雅輝，等.基于Darwin的集群流媒體服務(wù)器系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機與現(xiàn)代化，2009(5):19-22.

[6] Zhang X Y，Liu J C，Li B，et al.CoolStreaming/DONet:A data-driven overlay network for peer-to-peer live media streaming[C]//Proceedings of IEEE 24th Annual Joint Conference on Computer and Communications Societies.2005:2102-2111.

[7] Xu T Y，Chen J Z，Li W Z，et al.Supporting VCR-like operations in derivative tree-based P2P streaming systems[C]//Proc.of IEEE International Conference on Communications，2009.2009:1426-1430.

[8] Da Hora D N，Macedo D F，Oliveira L B，et al.Enhancing peer-to-peer content discovery techniques over mobile Ad Hoc networks[J].Computer Communications，2009，32(13-14):1445-1459.

[9] Oh H R，Wu D O，Song H.An effective mesh-pull-based P2P video streaming system using Fountain codes with variable symbol sizes[J].Computer Networks:The International Journal of Computer and Telecommunications Networking，2011，55(12):2746-2759.

[10] Tran D A，Minh Le，Hua K A.MobiVoD:A video-on-demand system design for mobile Ad Hoc networks[C]//2004 IEEE International Conference on Mobile Data Management.2004:212-223.

[11] Canali C，Renda M E，Santi P，et al.Enabling efficient peer-to-peer resource sharing in wireless mesh networks[J].IEEE Transactions on Mobile Computing，2010，9:333-347.

[12] 朱曉亮，王麗娜.無線Mesh網(wǎng)流媒體傳輸速率控制策略及模型[J].計算機應(yīng)用研究，2009，26(3):991-993，1009.

[13] Klemm A，Lindemann C，Waldhorst O P.A special-purpose peer-to-peer file sharing system for mobile Ad Hoc networks[C]//IEEE 58th Vehicular Technology Conference.2003，4:2758-2763.

[14] Stoica I，Morris R，Karger D，et al.Chord:A scalable peer-to-peer lookup service for Internet applications[C]//Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.2001:149-160.