一種無線mesh網(wǎng)絡(luò)下P2P-VoD系統(tǒng)的資源查詢算法

姜慧霖

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

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

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

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

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

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

圖2 跨層示意圖

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

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

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

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

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

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

2 流媒體資源的查詢算法

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

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

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

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

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

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

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

(7)結(jié)束。

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

4 結(jié)束語

本文設(shè)計(jì)一個(gè)在mesh網(wǎng)絡(luò)下P2P-VoD資源查詢算法，主要用來解決在無線網(wǎng)絡(luò)環(huán)境下使用Gossip協(xié)議進(jìn)行資源查詢所帶來的查詢效率低的問題。通過感知mesh路由器在物理空間中的位置，利用DHT算法將其組織成為一個(gè)Chord結(jié)構(gòu)，不僅縮短了對(duì)資源請(qǐng)求消息的響應(yīng)時(shí)間，而且減少數(shù)據(jù)的發(fā)送者和接收者之間的距離，提高數(shù)據(jù)的傳輸效率，減少數(shù)據(jù)傳輸?shù)牡却龝r(shí)延。下一步工作將提高流媒體數(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視頻點(diǎn)播技術(shù)的流媒體平臺(tái)設(shè)計(jì)與開發(fā)[J].計(jì)算機(jī)與現(xiàn)代化，2011(4):57-60.

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

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

[5] 夏敏，吳中海，楊雅輝，等.基于Darwin的集群流媒體服務(wù)器系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(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].計(jì)算機(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.