周 宇，楊 維

（北京交通大學(xué) 電子信息工程學(xué)院，北京100044）

0 引 言

現(xiàn)有的無(wú)線mesh網(wǎng)絡(luò)在盡可能提高系統(tǒng)吞吐量的同時(shí)，要保證傳輸?shù)膶?shí)時(shí)性和穩(wěn)定性，也就是降低系統(tǒng)時(shí)延［1－3］。

現(xiàn)階段研究無(wú)線mesh網(wǎng)絡(luò)的文獻(xiàn)中許多都是關(guān)于網(wǎng)絡(luò)構(gòu)建的，對(duì)mesh節(jié)點(diǎn)間數(shù)據(jù)分發(fā)機(jī)制的研究比較少。對(duì)于無(wú)線mesh網(wǎng)絡(luò)中的數(shù)據(jù)分發(fā)問(wèn)題，有學(xué)者提出了一些經(jīng)典數(shù)據(jù)分發(fā)的策略［4］。這些策略的主要思想分為3 種：第1種是通過(guò)組播樹的方式，以 “推”的方式主動(dòng)發(fā)送數(shù)據(jù)，但是由于一直在主動(dòng)發(fā)送數(shù)據(jù)，數(shù)據(jù)塊會(huì)重傳輸，造成網(wǎng)絡(luò)資源不合理利用，吞吐量下降；第2種是通過(guò) “拉”的方式，在某個(gè)節(jié)點(diǎn)需要數(shù)據(jù)的時(shí)候向相鄰節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)，這種方式主要的問(wèn)題是請(qǐng)求數(shù)據(jù)的時(shí)延會(huì)比較大；第3種是第1種和第2種的結(jié)合，可以在一定程度進(jìn)一步上降低控制信息開(kāi)銷和減少數(shù)據(jù)傳輸時(shí)延［5］，但是對(duì)算法要求較高，實(shí)際無(wú)線mesh網(wǎng)絡(luò)中不宜采用。本文主要是在第2種Mesh－Pull算法基礎(chǔ)上，綜合考慮了傳輸時(shí)延和吞吐量對(duì)于網(wǎng)絡(luò)性能的影響，提出一種改進(jìn)的BMesh－Pull算法，改善無(wú)線mesh網(wǎng)絡(luò)數(shù)據(jù)傳輸性能。

1 現(xiàn)有Mesh－Pull算法的問(wèn)題

Mesh－Pull算法核心就是調(diào)度節(jié)點(diǎn)在請(qǐng)求數(shù)據(jù)的時(shí)候給鄰居節(jié)點(diǎn)發(fā)送請(qǐng)求消息，鄰居節(jié)點(diǎn)收到請(qǐng)求信息之后再發(fā)送需要的數(shù)據(jù)塊給調(diào)度節(jié)點(diǎn)。Mesh－Pull這種分發(fā)方式不需要考慮整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)信息，但是存在的問(wèn)題是不一定當(dāng)前時(shí)刻傳輸?shù)臄?shù)據(jù)塊是用戶最需要的，而用戶最需要的數(shù)據(jù)塊卻有可能一直在緩存區(qū)等待傳輸，造成很大的傳輸時(shí)延。這樣的數(shù)據(jù)傳輸方式就會(huì)造成用戶觀看視頻時(shí)候的不流暢，影響用戶體驗(yàn)。同時(shí)，帶寬往往能決定網(wǎng)絡(luò)的容量和傳輸效率，帶寬衰減越小的網(wǎng)絡(luò)傳輸效率也會(huì)越大［6］。對(duì)于無(wú)線mesh網(wǎng)絡(luò)數(shù)據(jù)傳輸而言，要保證數(shù)據(jù)傳輸?shù)倪B續(xù)性，就需要嚴(yán)格控制噪聲引起的信號(hào)衰減［7，8］。

圖1建立了無(wú)線mesh網(wǎng)絡(luò)中的數(shù)據(jù)分發(fā)方式模型。其中給每個(gè)鄰居節(jié)點(diǎn)緩存的數(shù)據(jù)塊編號(hào)，不同的編號(hào)表示每個(gè)節(jié)點(diǎn)緩存含有不同的數(shù)據(jù)塊。在Mesh－Pull的算法中，調(diào)度節(jié)點(diǎn)i開(kāi)始發(fā)出數(shù)據(jù)請(qǐng)求信息，調(diào)度節(jié)點(diǎn)i就與相應(yīng)的鄰居節(jié)點(diǎn)交換可用數(shù)據(jù)的消息，同時(shí)查看該鄰居節(jié)點(diǎn)是否含有請(qǐng)求的數(shù)據(jù)塊，鄰居節(jié)點(diǎn)如果擁有該數(shù)據(jù)塊，就會(huì)告訴請(qǐng)求節(jié)點(diǎn)自己有該數(shù)據(jù)塊，這時(shí)請(qǐng)求節(jié)點(diǎn)就會(huì)從所有含請(qǐng)求數(shù)據(jù)塊的鄰居節(jié)點(diǎn)中選擇最合適的鄰居節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)，完成后再進(jìn)行下一輪數(shù)據(jù)請(qǐng)求。

圖1 Mesh－Pull的數(shù)據(jù)分發(fā)方式

從Mesh－Pull分發(fā)方式可以看出，每一次數(shù)據(jù)請(qǐng)求過(guò)程中，發(fā)送請(qǐng)求和響應(yīng)請(qǐng)求都需要等待一段時(shí)間，這樣就會(huì)造成網(wǎng)絡(luò)傳輸時(shí)延較大，吞吐量較低，影響網(wǎng)絡(luò)傳輸性能。

2 改進(jìn)的BMesh－Pull數(shù)據(jù)分發(fā)算法

改進(jìn)的BMesh－Pull算法是在Mesh－Pull算法的基礎(chǔ)上，綜合考慮了傳輸時(shí)延和吞吐量對(duì)于網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)挠绊?。其核心思想是在建模中通過(guò)優(yōu)先級(jí)調(diào)度算法先確立了需要傳輸?shù)臄?shù)據(jù)塊不同的優(yōu)先級(jí)。再利用帶寬和信噪比的關(guān)系為該數(shù)據(jù)塊分配合適的響應(yīng)鄰居節(jié)點(diǎn)。

圖2給出了改進(jìn)的BMesh－Pull數(shù)據(jù)分發(fā)算法的思想流程圖。無(wú)線Mesh節(jié)點(diǎn)i開(kāi)始第N 次數(shù)據(jù)請(qǐng)求，根據(jù)優(yōu)先級(jí)調(diào)度算法，確定最需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)塊a，完成數(shù)據(jù)塊優(yōu)先級(jí)的調(diào)度，再通過(guò)帶寬和信噪比估計(jì)為該數(shù)據(jù)塊a選擇最合適的鄰居節(jié)點(diǎn)j，完成數(shù)據(jù)分發(fā)的過(guò)程。

改進(jìn)的BMesh－Pull算法考慮了傳輸時(shí)延和網(wǎng)絡(luò)吞吐量的問(wèn)題，建立了最優(yōu)化選擇機(jī)制。

圖2 BMesh－Pull數(shù)據(jù)分發(fā)算法的思想流程

3 數(shù)據(jù)分發(fā)建模

如圖3所示給出了一個(gè)數(shù)據(jù)分發(fā)的滑動(dòng)窗口。在傳輸中，網(wǎng)絡(luò)將要傳輸?shù)臄?shù)據(jù)內(nèi)容分為許多個(gè)大小一樣的數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊都會(huì)有一個(gè)編號(hào)。其中數(shù)據(jù)塊c表示當(dāng)前播放時(shí)刻，數(shù)據(jù)塊d表示播放過(guò)錯(cuò)過(guò)了的數(shù)據(jù)，數(shù)據(jù)塊a表示已經(jīng)到達(dá)的數(shù)據(jù)，數(shù)據(jù)塊b表示缺失的需要傳輸?shù)臄?shù)據(jù)塊。從滑動(dòng)窗口的示意圖可以直觀看到數(shù)據(jù)塊的緊急程度。

圖3 滑動(dòng)窗口

數(shù)據(jù)分發(fā)建模前先定義了一些參數(shù)如表1所示，這些參數(shù)用于描述改進(jìn)的BMesh－Pull數(shù)據(jù)分發(fā)算法。

表1 BMesh－Pull算法用到的描述參數(shù)

改進(jìn)的數(shù)據(jù)分發(fā)算法的核心有兩個(gè)部分，首先通過(guò)優(yōu)先級(jí)調(diào)度算法選擇最需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)塊a，再通過(guò)帶寬和信噪比估計(jì)為數(shù)據(jù)塊a選擇最合適的鄰居節(jié)點(diǎn)j。

要確定節(jié)點(diǎn)i請(qǐng)求數(shù)據(jù)時(shí)最需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)塊a，分別要從數(shù)據(jù)塊的優(yōu)先級(jí)以及數(shù)據(jù)塊最少的提供者的數(shù)量這兩方面對(duì)每個(gè)需要傳輸?shù)臄?shù)據(jù)塊定義請(qǐng)求順序的優(yōu)先級(jí)［9］。在這里定義了一個(gè)優(yōu)先級(jí)算法的公式

其中，F(xiàn)ia表示數(shù)據(jù)塊a 對(duì)于節(jié)點(diǎn)i的優(yōu)先級(jí)大小。0≤β≤1，β越大表示更需要考慮數(shù)據(jù)提供者的數(shù)量，β越小表示更需要考慮迫切需要數(shù)據(jù)塊的程度。通過(guò)比較Fia的大小，就會(huì)得到一個(gè)需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)塊的優(yōu)先級(jí)順序，按照這個(gè)優(yōu)先級(jí)順序再對(duì)鄰居響應(yīng)節(jié)點(diǎn)發(fā)送請(qǐng)求信息。

要為數(shù)據(jù)塊a選擇最合適的鄰居節(jié)點(diǎn)j，分別從是帶寬和信噪比的影響兩個(gè)角度考慮。

（1）帶寬W 的考慮：核心思想是考慮所有含有數(shù)據(jù)塊a的鄰居節(jié)點(diǎn)n，把鄰居節(jié)點(diǎn)n在前p 個(gè)周期中發(fā)送給節(jié)點(diǎn)i的帶寬信息數(shù)據(jù)作為前p 個(gè)周期的帶寬估計(jì)，根據(jù)得到的信息選擇第p＋1 個(gè)周期時(shí)與節(jié)點(diǎn)i傳輸帶寬最大的鄰居節(jié)點(diǎn)n。

令BWi［n］［p＋1］來(lái)表示第p＋1周期時(shí)節(jié)點(diǎn)i選擇鄰居節(jié)點(diǎn)n 進(jìn)行數(shù)據(jù)傳輸時(shí)的帶寬估計(jì)。用下面的公式表示在第p＋1周期時(shí)節(jié)點(diǎn)i對(duì)其鄰居節(jié)點(diǎn)n 有效帶寬估計(jì)

（2）信噪比SNR 影響的考慮：信噪比越高往往可以使得信號(hào)的傳輸更為快速有效［10］。信噪比也是會(huì)影響網(wǎng)絡(luò)傳輸性能的重要因素。信噪比在網(wǎng)絡(luò)中往往是不確定的，建模的時(shí)候把節(jié)點(diǎn)之間的信噪比大小控制在一定的范圍之內(nèi)選擇隨機(jī)的值，這樣是比較符合實(shí)際的情況。

在這里定義了SNRMIN 表示信噪比SNR 的臨界值，SNRAVR ［ikn］表示鄰居節(jié)點(diǎn)n前m 個(gè)周期中與節(jié)點(diǎn)i 傳輸數(shù)據(jù)的信噪比平均值?；舅枷胧窃诘趍＋1個(gè)周期時(shí)考慮節(jié)點(diǎn)i的SNRAVR ［ikn］，把SNRAVR ［ikn］的值與SNRMIN 進(jìn)行比較來(lái)選擇最合適鄰居節(jié)點(diǎn)j。

判斷的方式是首先考慮傳輸帶寬最大的鄰居節(jié)點(diǎn)A，若SNRAVR ［ikA］的值大于SNRMIN 則選擇鄰居節(jié)點(diǎn)A作為最合適鄰居節(jié)點(diǎn)，若SNRAVR ［ikA］小于SNRMIN則繼續(xù)考慮傳輸帶寬第二大的鄰居節(jié)點(diǎn)B，接著以此類推從而直到選擇出滿足信噪比要求中傳輸帶寬最大的鄰居節(jié)點(diǎn)作為最合適鄰居節(jié)點(diǎn)j。

4 仿真實(shí)驗(yàn)和性能分析

采用了Matlab 軟件來(lái)進(jìn)行網(wǎng)絡(luò)仿真分析?？偣苍O(shè)定100個(gè)對(duì)等的節(jié)點(diǎn)來(lái)模擬無(wú)線mesh 網(wǎng)絡(luò)中的mesh 節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)其鄰居節(jié)點(diǎn)個(gè)數(shù)設(shè)為10 個(gè)。初始帶寬設(shè)定為10 MHz。初始信噪比范圍由Matlab中的隨機(jī)函數(shù)所產(chǎn)生，最小的值作為臨界值SNRMIN。

4.1 節(jié)點(diǎn)的吞吐量

通過(guò)設(shè)定上述的仿真環(huán)境，編寫仿真程序，圖4 中顯示了加入了最優(yōu)化選擇機(jī)制和沒(méi)有加入最優(yōu)化選擇機(jī)制兩種條件下，β節(jié)點(diǎn)平均吞吐量之間的關(guān)系。其中橫軸表示影響因子β，縱軸表示節(jié)點(diǎn)平均吞吐量 （kbps）。定義節(jié)點(diǎn)的吞吐量為在網(wǎng)絡(luò)中的單位時(shí)間里每個(gè)節(jié)點(diǎn)從其它節(jié)點(diǎn)獲得的數(shù)據(jù)量。加入最優(yōu)化選擇機(jī)制指的采用改進(jìn)的BMesh－Pull最優(yōu)化算法，沒(méi)有加入最優(yōu)選擇機(jī)制指的是采用現(xiàn)有的Mesh－Pull算法。

β是最優(yōu)化選擇的關(guān)鍵影響因子，在實(shí)驗(yàn)中分別選取了β＝0，0.4，0.6，0.9，1這幾個(gè)值，來(lái)綜合考慮β與吞吐量的關(guān)系。

圖4 節(jié)點(diǎn)平均吞吐量和β的關(guān)系

圖4中仿真結(jié)果可以看到，在加入最優(yōu)化選擇機(jī)制條件下，除了β＝0.4的時(shí)候，節(jié)點(diǎn)平均吞吐量對(duì)比沒(méi)有加入最優(yōu)選擇機(jī)制條件下降了5.3%，但是其余的情況下節(jié)點(diǎn)平均吞吐量對(duì)比沒(méi)有加入最優(yōu)選擇機(jī)制條件提高了5.2%－37.5%，說(shuō)明了加入最優(yōu)化選擇機(jī)制提高了節(jié)點(diǎn)平均吞吐量。同時(shí)，在β＝0.6時(shí)，節(jié)點(diǎn)平均吞吐量達(dá)到最大，說(shuō)明數(shù)據(jù)塊的緊急程度和數(shù)據(jù)塊的最少提供者數(shù)量這兩種因素都是影響節(jié)點(diǎn)平均吞吐量的關(guān)鍵性因素，缺了任何一部分都會(huì)對(duì)節(jié)點(diǎn)平均吞吐量有很大的影響，與理論分析的結(jié)果相對(duì)應(yīng)。

4.2 啟動(dòng)延時(shí)

無(wú)線Mesh網(wǎng)絡(luò)系統(tǒng)性能的一個(gè)重要指標(biāo)就是節(jié)點(diǎn)的啟動(dòng)延時(shí)，該指標(biāo)特別會(huì)影響流媒體傳輸效率，關(guān)系到用戶的切身體驗(yàn)。圖5所示了10到24號(hào)節(jié)點(diǎn)與啟動(dòng)時(shí)延的關(guān)系。其中橫軸表示節(jié)點(diǎn)編號(hào)的名稱，縱軸表示各節(jié)點(diǎn)從開(kāi)始請(qǐng)求數(shù)據(jù)時(shí)到傳輸完成的啟動(dòng)時(shí)延 （ms）。將節(jié)點(diǎn)啟動(dòng)時(shí)延定義為能夠使流媒體文件中最開(kāi)始數(shù)據(jù)塊正常傳輸所需要的時(shí)間。

圖5 相對(duì)應(yīng)節(jié)點(diǎn)與啟動(dòng)時(shí)延的關(guān)系

圖5仿真結(jié)果可以發(fā)現(xiàn)，在加入了最優(yōu)化選擇機(jī)制的條件下，選取的15個(gè)節(jié)點(diǎn)中有12個(gè)節(jié)點(diǎn)的啟動(dòng)延時(shí)相比沒(méi)有加入最優(yōu)選擇機(jī)制條件都有1ms－5ms上的降低，只有3個(gè)節(jié)點(diǎn)啟動(dòng)延遲相比沒(méi)有加入最優(yōu)選擇機(jī)制條件有所增加。這說(shuō)明了加入了最優(yōu)化選擇機(jī)制可以降低網(wǎng)絡(luò)的傳輸時(shí)延，這也是與理論分析的結(jié)果相對(duì)應(yīng)的。

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

本文重點(diǎn)研究了現(xiàn)有Mesh－Pull的流媒體數(shù)據(jù)分發(fā)策略所存在的時(shí)延高和吞吐量低的問(wèn)題，提出了一種改進(jìn)的BMesh－Pull數(shù)據(jù)分發(fā)優(yōu)化算法。該算法主要從吞吐量和傳輸時(shí)延這兩個(gè)角度出發(fā)，選擇了最符合無(wú)線mesh網(wǎng)絡(luò)傳輸性能要求的兩個(gè)節(jié)點(diǎn)完成數(shù)據(jù)傳輸過(guò)程，實(shí)現(xiàn)網(wǎng)絡(luò)傳輸性能的改善。通過(guò)Matlab仿真可以發(fā)現(xiàn)，改進(jìn)的BMesh－Pull數(shù)據(jù)分發(fā)算法是有效的。BMesh－Pull數(shù)據(jù)分發(fā)算法相比Mesh－Pull算法在節(jié)點(diǎn)平均吞吐量和節(jié)點(diǎn)啟動(dòng)延時(shí)兩個(gè)方面的傳輸性能都有了改進(jìn)。通過(guò)采用BMesh－Pull算法可以在保持Mesh－Pull算法基本優(yōu)勢(shì)的同時(shí)還能有效解決了時(shí)延和吞吐量問(wèn)題，使得BMesh－Pull算法相比Mesh－Pull算法時(shí)延降低了1ms－5ms，同時(shí)吞吐量有了5.2%－37.5%的提升。綜合可以表明，BMesh－Pull算法比Mesh－Pull分發(fā)算法在改善網(wǎng)絡(luò)時(shí)延和吞吐量方面更為優(yōu)越，可以實(shí)現(xiàn)提高網(wǎng)絡(luò)吞吐量和降低網(wǎng)絡(luò)數(shù)據(jù)傳輸時(shí)延的目的。

［1］SUN Zhixin，CHEN Yadang，REN Zhiguang.Data transmission strategy of P2Ppattern live video media streaming system［J］.Journal on Communications，2011，32 （6）：1－4 （in Chinese）.［孫知信，陳亞當(dāng)，任志廣.基于P2P流媒體直播系統(tǒng)的數(shù)據(jù)傳輸策略 ［J］.通信學(xué)報(bào)，2011，32 （6）：1－4.］

［2］LI Zhijie，F(xiàn)ANG Xuming.Method of cross－layer scheduling in wireless mesh networks［J］.Journal of the China Railway Society，2012，34 （10）：61－64 （in Chinese）. ［李志杰，方旭明.無(wú)線Mesh網(wǎng)絡(luò)中一種QoS保證的跨層調(diào)度方法 ［J］.鐵道學(xué)報(bào)，2012，34 （10）：61－64.］

［3］CHEN Lerui，KONG Jinsheng.Research on network routing optimisation based on improved genetic algorithm ［J］.Computer Applications and Software，2013，30 （4）：135－137（in Chinese）.［陳樂(lè)瑞，孔金生.基于改進(jìn)遺傳算法的網(wǎng)絡(luò)路由優(yōu)化研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2013，30 （4）：135－137.］

［4］SUN Shuang.Research on live scheduling algorithm in P2P media streaming based on Donet［D］.Qinghuangdao：Yanshan University，2010 （in Chinese）.［孫爽.基于Donet的P2P流媒體直播調(diào)度算法研究［D］.秦皇島：燕山大學(xué)，2010.］

［5］ZHANG Hong.Strategy of distributing streaming media data in P2Pnetwork ［J］.Heilongjiang Science and Technology Information，2013 （22）：149 （in Chinese）.［張弘.P2P網(wǎng)絡(luò)的流媒體數(shù)據(jù)分發(fā)策略淺析［J］.黑龍江科技信息，2013 （22）：149.］

［6］LIU Jiansheng，WEI Nanqing，YUE Guangxue，et al.Research on scheduling technologies of large－scale media streaming over peer－to－peer networks ［J］.Microelectronics ＆ Computer，2011，28 （8）：90－93 （in Chinese）.［劉建生，魏楠青，樂(lè)光學(xué)，等.P2P大規(guī)模流媒體調(diào)度技術(shù)研究 ［J］.微電子學(xué)與計(jì)算機(jī)，2011，28 （8）：90－93.］

［7］Zhang Baoxin，Mouftah HT.Destination－driven shortest path tree algorithms ［J］.Journal of High Speed Network，2006，15 （2）：123－130.

［8］LIU Tie，SHI Guomei，HUANG Qiuyuan，et al.An improved SNR estimation algorithm in OFDM ［J］.Microcomputer Applications，2013，2 （6）：29－32 （in Chinese）. ［劉鐵，時(shí)國(guó)美，黃秋元，等.一種改進(jìn)的OFDM 系統(tǒng)中信噪比估計(jì)算法 ［J］.網(wǎng)絡(luò)新媒體技術(shù)，2013，2 （6）：29－32.］

［9］BAO Rongzhen，CAI Ming.Graph coloring－based scheduling algorithm for P2P media streaming ［J］.Journal of Computer Applications，2011，31 （1）：190－193 （in Chinese）. ［鮑 榮真，蔡明.基于圖著色的P2P流媒體數(shù)據(jù)調(diào)度算法 ［J］.計(jì)算機(jī)應(yīng)用，2011，31 （1）：190－193.］

［10］FENG Jianchun.Design and implementation of hf digital receiver with high SNR ［D］.Wuhan：Wuhan University of Technology，2010 （in Chinese）.［馮建春.高信噪比短波數(shù)字接收機(jī)的設(shè)計(jì)與實(shí)現(xiàn) ［D］.武漢：武漢理工大學(xué)，2010.］

［11］CHEN Lerui，KONG Jinsheng.Research on network routing optimisation based on improved genetic algorithm ［J］.Computer Applications and Software，2013，30 （4）：135－137 （in Chinese）.［陳樂(lè)瑞，孔金生.基于改進(jìn)遺傳算法的網(wǎng)絡(luò)路由優(yōu)化研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2013，30 （4）：135－137.］