基于數(shù)據(jù)塊優(yōu)先級(jí)的無(wú)線多跳Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法

摘 要： 為了解決當(dāng)前無(wú)線多跳Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法大都使用Mesh?Pull分發(fā)策略，導(dǎo)致其傳輸性能較弱，以及較大的數(shù)據(jù)分發(fā)時(shí)延的不足，設(shè)計(jì)了基于數(shù)據(jù)塊優(yōu)先級(jí)的無(wú)線多跳Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法。首先，基于Mesh?Pull方法，考慮其吞吐量與時(shí)延的干擾作用，定義了最優(yōu)化擇取機(jī)制，并引入數(shù)據(jù)塊的優(yōu)先級(jí)，確定網(wǎng)絡(luò)中的待傳輸數(shù)據(jù)塊的請(qǐng)求排序，并通過(guò)評(píng)估Mesh網(wǎng)絡(luò)的帶寬和SNR值，尋找出最優(yōu)鄰居節(jié)點(diǎn)。實(shí)驗(yàn)數(shù)據(jù)顯示，與當(dāng)前Mesh?Pull數(shù)據(jù)分發(fā)算法相比，該算法具有更低的網(wǎng)絡(luò)時(shí)延與更高的吞吐量。

關(guān)鍵詞： Mesh網(wǎng)絡(luò)； 數(shù)據(jù)分發(fā)； 數(shù)據(jù)塊優(yōu)先級(jí)； 網(wǎng)絡(luò)延遲； 數(shù)據(jù)分發(fā)

中圖分類號(hào)： TN919.2?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）21?0040?04

Wireless multi?hop Mesh network data distribution algorithm

based on data block priority

DU Songjiang， ZHANG Jia

（Department of Information Engineering， Yangtze University College of Engineering Technology， Jingzhou 434020， China）

Abstract： The Mesh?Pull distribution scheme is mostly used to improve the wireless multi?hop Mesh network data distribution algorithm， which leads to the poor transmission performance， and insufficient distribution delay of massive data. The wireless multi?hop Mesh network data distribution algorithm based on data block priority was designed. On the basis of Mesh?Pull method， the optimal selection mechanism is defined by considering the interference effect of data throughput and time delay. The data block priority is introduced to determine the request sequence of the transmitting data block in network. The bandwidth and signal to noise ratio （SNR） of Mesh network are estimated to find out the optimal neighbor node. The simulation data shows that， in comparison with the Mesh?Pull data distribution algorithm， the improved algorithm has lower network delay and higher network throughput.

Keywords： Mesh network； data distribution； data block priority； network delay； data distribution

0 引 言

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的日益發(fā)展與完善，無(wú)線Mesh網(wǎng)絡(luò)也得到了廣泛應(yīng)用，與此同時(shí)，由于用戶響應(yīng)體驗(yàn)要求的提高，無(wú)線Mesh網(wǎng)絡(luò)面臨更大的挑戰(zhàn)與要求，尤其是數(shù)據(jù)分發(fā)能力，不但需要兼顧更高的吞吐量與傳輸穩(wěn)定性，而且更需要降低網(wǎng)絡(luò)數(shù)據(jù)傳輸時(shí)延[1?3]。

為了更好地?cái)U(kuò)展無(wú)線Mesh網(wǎng)絡(luò)的實(shí)用性，諸多學(xué)者提出了相應(yīng)的無(wú)線Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法。如班迪等人為了提高M(jìn)esh網(wǎng)絡(luò)的數(shù)據(jù)分發(fā)能力[4]，提出了改進(jìn)的數(shù)據(jù)傳遞策略，該技術(shù)在選擇錨點(diǎn)時(shí)，利用期望傳輸次數(shù)（Expected Transmission Count，ETX）作為通信鏈路的權(quán)值，以此降低整條數(shù)據(jù)傳遞路徑的ETX值，實(shí)驗(yàn)結(jié)果顯示其算法具有較高的數(shù)據(jù)吞吐量與理想的分發(fā)試驗(yàn)。Qiuling Yang等人為了解決無(wú)線頻道的干擾影響，提高數(shù)據(jù)分發(fā)能力，提出了基于TCP控制機(jī)制的無(wú)線Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)策略[5]，通過(guò)延遲分布，構(gòu)建網(wǎng)絡(luò)時(shí)延模型，精確實(shí)時(shí)控制數(shù)據(jù)傳輸時(shí)延，實(shí)驗(yàn)結(jié)果驗(yàn)證了其算法的優(yōu)異性。

然而，當(dāng)前無(wú)線Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法大都是側(cè)重于網(wǎng)絡(luò)構(gòu)建方面，且大都是基于Mesh?Pull，策略動(dòng)態(tài)性不強(qiáng)，當(dāng)傳輸數(shù)據(jù)塊并非是用戶理想數(shù)據(jù)時(shí)，會(huì)導(dǎo)致大量的數(shù)據(jù)排隊(duì)，造成巨大的網(wǎng)絡(luò)時(shí)延[6]。

對(duì)此，本文設(shè)計(jì)了基于數(shù)據(jù)塊優(yōu)先級(jí)的無(wú)線多條Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法。首先，基于Mesh?Pull法，兼顧其吞吐量與時(shí)延的干擾作用，定義了最優(yōu)化擇取機(jī)制，并引入數(shù)據(jù)塊的優(yōu)先級(jí)，確定網(wǎng)絡(luò)中的待傳輸數(shù)據(jù)塊的請(qǐng)求排序，并通過(guò)評(píng)估Mesh網(wǎng)絡(luò)的帶寬和SNR（Signal to Noise Ratio）值，尋找出最優(yōu)鄰居節(jié)點(diǎn)。最后測(cè)試了本文算法的網(wǎng)絡(luò)性能。

1 基于Mesh?Pull策略的數(shù)據(jù)分發(fā)技術(shù)

在當(dāng)前的Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法中，大都采用Mesh?Pull機(jī)制，該技術(shù)的核心思想為：Mesh網(wǎng)絡(luò)中的調(diào)度節(jié)點(diǎn)在請(qǐng)求數(shù)據(jù)過(guò)程中，將數(shù)據(jù)的排序請(qǐng)求傳播到其領(lǐng)域節(jié)點(diǎn)，當(dāng)接收到請(qǐng)求后，迅速向調(diào)度節(jié)點(diǎn)提供相應(yīng)的數(shù)據(jù)塊。雖然Mesh?Pull策略不需要考慮整個(gè)Mesh網(wǎng)絡(luò)中的節(jié)點(diǎn)，但是，當(dāng)網(wǎng)絡(luò)中的傳輸數(shù)據(jù)塊不是用戶最需要的，從而導(dǎo)致大量的節(jié)點(diǎn)數(shù)據(jù)處于等待狀態(tài)，產(chǎn)生較大的網(wǎng)絡(luò)時(shí)延。為了確保Mesh網(wǎng)絡(luò)的連續(xù)數(shù)據(jù)傳輸，需要將噪聲引起的信號(hào)衰減程度控制在一個(gè)合適的水平[6]。

圖[1]是Mesh?Pull策略的數(shù)據(jù)分發(fā)過(guò)程，可見該策略首先對(duì)各鄰居節(jié)點(diǎn)緩存的數(shù)據(jù)塊完成編號(hào)，以表征其數(shù)據(jù)塊數(shù)量。調(diào)度節(jié)點(diǎn)[i]廣播接收請(qǐng)求，則其將與鄰居節(jié)點(diǎn)貢獻(xiàn)可用資源。并在此基礎(chǔ)上查看請(qǐng)求的數(shù)據(jù)塊是不是存在于后者之中，若存在其中，后者將會(huì)把結(jié)果向前者告知，這種情況下，前者將從中選出最佳數(shù)據(jù)快，結(jié)束以后，重新開始數(shù)據(jù)請(qǐng)求[6?7]。

依據(jù)Mesh?Pull策略的工作原理可知，調(diào)度節(jié)點(diǎn)發(fā)出請(qǐng)求及響應(yīng)時(shí)，二者有可能處于等待狀態(tài)，從而增大了網(wǎng)絡(luò)傳輸時(shí)延，降低了數(shù)據(jù)吞吐量，嚴(yán)重影響了網(wǎng)絡(luò)性能。

2 本文Mesh數(shù)據(jù)分發(fā)算法

針對(duì)Mesh?Pull策略的不足，本文以網(wǎng)絡(luò)吞吐量與時(shí)延為目標(biāo)，提出了基于數(shù)據(jù)塊優(yōu)先級(jí)的無(wú)線多條Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法，其流程見圖2。通過(guò)先確定各個(gè)數(shù)據(jù)塊的優(yōu)先級(jí)確定最佳領(lǐng)域節(jié)點(diǎn)。調(diào)度節(jié)點(diǎn)[i]發(fā)出第[N]次請(qǐng)求，再依據(jù)其優(yōu)先級(jí)，確定其相應(yīng)的數(shù)據(jù)塊[a，]并引入信噪比與帶寬，確定出數(shù)據(jù)塊[a]的最優(yōu)領(lǐng)域節(jié)點(diǎn)。

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

在Mesh數(shù)據(jù)分發(fā)算法改進(jìn)的基礎(chǔ)上建立數(shù)據(jù)分發(fā)模型。分發(fā)算法的關(guān)鍵內(nèi)容體現(xiàn)在：首先需要確定改進(jìn)的分發(fā)算法中數(shù)據(jù)塊傳遞的優(yōu)先級(jí)別。這里假設(shè)節(jié)點(diǎn)名稱為[i，i]對(duì)網(wǎng)絡(luò)中傳送的數(shù)據(jù)發(fā)送請(qǐng)求，用[Fia]量化數(shù)據(jù)塊對(duì)于節(jié)點(diǎn)[i]的優(yōu)先級(jí)。[Fia]作為量化的優(yōu)先級(jí)大小，分別從數(shù)據(jù)塊提供數(shù)量和數(shù)據(jù)塊自身優(yōu)先級(jí)2個(gè)指標(biāo)入手，具體的表達(dá)式為：

[Fia=βD1+a∈NeighborView[i]BM[i][a]+（1+β）WTa-id]

式中：[β]是衡量數(shù)據(jù)塊提供數(shù)量的指標(biāo)，其值范圍大小為[0≤β≤1]，[β]的大小體現(xiàn)數(shù)據(jù)提供數(shù)量在優(yōu)先級(jí)量化過(guò)程中的權(quán)重，[β]越大體現(xiàn)該指標(biāo)在[Fia]中的權(quán)重越大；[D]代表與節(jié)點(diǎn)相關(guān)的鄰居點(diǎn)的個(gè)數(shù)。式中其他參數(shù)的意義如表1所示。

確定數(shù)據(jù)塊優(yōu)先級(jí)后，需要為數(shù)據(jù)塊確定最優(yōu)鄰居節(jié)點(diǎn)[j，]故需要完成鄰居節(jié)點(diǎn)的尋找工作，此過(guò)程依據(jù)信噪比估計(jì)和寬帶估計(jì)對(duì)最優(yōu)鄰居節(jié)點(diǎn)進(jìn)行評(píng)估。

在各節(jié)點(diǎn)之間信噪比估計(jì)過(guò)程中，根據(jù)實(shí)際網(wǎng)路信號(hào)傳遞過(guò)程，信號(hào)節(jié)點(diǎn)之間的信噪比對(duì)信號(hào)的傳遞過(guò)程具有較大的影響，而信噪比的不確定性造成在信號(hào)傳遞過(guò)程中兼顧信噪比的范圍，信噪比的峰值越大，則對(duì)應(yīng)的信號(hào)傳遞越流暢。在信噪比估計(jì)判斷最優(yōu)鄰居節(jié)點(diǎn)的過(guò)程中，定義兩個(gè)參數(shù)，分別是信噪比估計(jì)的極限最小值，這里用SNPMIN表示，另外一個(gè)參數(shù)為[SNRAVR[ikn]]，表示節(jié)點(diǎn)[i]與各個(gè)鄰居節(jié)點(diǎn)在一定周期內(nèi)信噪比的平均值，以[SNRAVR[ikn]]與SNPMIN的大小為判斷依據(jù)，即分別計(jì)算節(jié)點(diǎn)[i]與各個(gè)鄰居節(jié)點(diǎn)的均值，在均值大于極限最小值時(shí)，這里就認(rèn)為該節(jié)點(diǎn)為[i]的最優(yōu)鄰居節(jié)點(diǎn)[j。]如果不滿足以上的判斷依據(jù)，則系統(tǒng)一直處于鄰居節(jié)點(diǎn)的尋優(yōu)過(guò)程。

寬帶估計(jì)對(duì)最優(yōu)鄰居節(jié)點(diǎn)的影響，主要原理是兼顧全部包含[a]的鄰居節(jié)點(diǎn)[n，]將[n]在前[p]個(gè)周期中向[i]發(fā)送的帶寬數(shù)據(jù)當(dāng)做相應(yīng)的帶寬估計(jì)，在此基礎(chǔ)上按照所獲得信息確定第[p+1]個(gè)周期時(shí)與[i]傳輸帶寬最大的[n]。

用[BWi[n][p+1]]指代第[p+1]周期時(shí)[i]確定[n]傳輸時(shí)的帶寬估計(jì)。具體表示如下：

[BWi[n][p+1]=l=1pαlBWi[n][p+1-l]]

式中：[αl]屬于一個(gè)固定常值，用來(lái)指代第[l]個(gè)周期時(shí)帶寬的影響因子。為了能夠較為科學(xué)地開展帶寬估計(jì)工作，那么必須使[αl]符合以下條件：[l=1pαl=1，][α1≥α2≥…≥αp]。利用對(duì)比分析[BWi[n][p+1]]數(shù)值高低，獲得在第[p+1]周期時(shí)的[[n]max]。

根據(jù)以上數(shù)據(jù)分發(fā)算法的模型建立過(guò)程，數(shù)據(jù)傳輸包含大量的數(shù)據(jù)模塊，各個(gè)數(shù)據(jù)模塊之間存在數(shù)據(jù)優(yōu)先次序的不同，可理解為不同數(shù)據(jù)模塊所處的位置和功能隨時(shí)間的變化而變化，此時(shí)可用一個(gè)滑動(dòng)窗口形象地表示各個(gè)數(shù)據(jù)塊之間的關(guān)系，即優(yōu)先次序，如圖3所示。

4 仿真實(shí)驗(yàn)與結(jié)果分析

通過(guò)Matlab對(duì)本文構(gòu)建的數(shù)據(jù)分發(fā)算法模型進(jìn)行仿真實(shí)驗(yàn)，設(shè)定仿真基本參數(shù)，根據(jù)第三部分理論算法，設(shè)定信噪比的范圍由仿真軟件內(nèi)部函數(shù)提供，其中內(nèi)部函數(shù)的最小值作為信噪比最小值。寬帶估計(jì)值為12 Hz。為了能充分驗(yàn)證本文算法的有效性，這里對(duì)數(shù)據(jù)分發(fā)節(jié)點(diǎn)數(shù)目的選擇為120，每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)的鄰居節(jié)點(diǎn)個(gè)數(shù)為12。

4.1 吞吐量

所謂節(jié)點(diǎn)吞吐量，即單位時(shí)間里在網(wǎng)絡(luò)中各節(jié)點(diǎn)從其他節(jié)點(diǎn)得到的數(shù)據(jù)量。利用上文中的測(cè)試環(huán)境進(jìn)行相應(yīng)的編程，具體數(shù)據(jù)如圖4所示，在這里，橫坐標(biāo)用來(lái)指代[β（0<β<1），]是體現(xiàn)數(shù)據(jù)塊數(shù)量和數(shù)據(jù)塊優(yōu)先級(jí)在網(wǎng)絡(luò)信號(hào)傳遞過(guò)程中的優(yōu)先級(jí)權(quán)重判斷，這里對(duì)參數(shù)[β]取值為0.1，0.3，0.5，0.7，0.9，研究數(shù)據(jù)塊數(shù)據(jù)提供數(shù)量和數(shù)據(jù)塊自身優(yōu)先級(jí)對(duì)吞吐量的影響，而縱坐標(biāo)則是對(duì)應(yīng)的不同[β]參數(shù)下，對(duì)應(yīng)節(jié)點(diǎn)的平均吞吐量，圖4比較形象地展示了Mesh算法改進(jìn)前后節(jié)點(diǎn)的平均吞吐量。

根據(jù)圖4，改進(jìn)后的算法和未改進(jìn)的算法對(duì)應(yīng)的相同[β]參數(shù)下的節(jié)點(diǎn)吞吐量的值有高有低。在[β=0.7]的情形下，節(jié)點(diǎn)評(píng)價(jià)吞吐量的值達(dá)到最高，根據(jù)[β]參數(shù)的含義，[β]參數(shù)越大說(shuō)明數(shù)據(jù)供應(yīng)數(shù)量對(duì)吞吐量值影響大于數(shù)據(jù)塊緊急程度對(duì)吞吐量的影響。[β=0.7]吞吐量達(dá)到最大值，說(shuō)明數(shù)據(jù)供應(yīng)數(shù)量的大小對(duì)數(shù)據(jù)塊優(yōu)先級(jí)別起到關(guān)鍵影響作用。從圖4總體來(lái)說(shuō)，對(duì)于優(yōu)化的MePull_db算法，除去[β=0.5]時(shí)，節(jié)點(diǎn)的吞吐量小于未改進(jìn)Mesh?Pull算法外，其他參數(shù)下，改進(jìn)算法的平均吞吐量提高幅度處于5.3%～38.1%范圍內(nèi)，因此，通過(guò)對(duì)比數(shù)據(jù)能夠得知，MePull_db算法在很大程度上改善了吞吐量。

4.2 啟動(dòng)延遲

網(wǎng)絡(luò)信息傳遞過(guò)程中，網(wǎng)絡(luò)延遲較為常見。網(wǎng)絡(luò)延遲導(dǎo)致用戶在使用過(guò)程中產(chǎn)生較差的評(píng)價(jià)，故在對(duì)網(wǎng)絡(luò)評(píng)價(jià)效果方面，網(wǎng)絡(luò)延時(shí)較為直觀，也是比較重要的指標(biāo)。為了驗(yàn)證本文算法在網(wǎng)絡(luò)延遲方面的表現(xiàn)，這里選取20個(gè)節(jié)點(diǎn)對(duì)本文算法和未改進(jìn)的算法進(jìn)行檢測(cè)，如圖5所示，圖中分別表述了各個(gè)節(jié)點(diǎn)對(duì)應(yīng)的延遲時(shí)間，該延遲時(shí)間對(duì)應(yīng)的就是客戶等待時(shí)間，橫坐標(biāo)表示節(jié)點(diǎn)，縱坐標(biāo)是對(duì)應(yīng)的各節(jié)點(diǎn)的延遲，單位用ms表示，圖中兩條曲線分別代表改進(jìn)和未改進(jìn)算法對(duì)應(yīng)的啟動(dòng)延遲時(shí)間的長(zhǎng)短。

從圖5中可以看出，各個(gè)節(jié)點(diǎn)對(duì)應(yīng)的時(shí)延時(shí)間有所不同，改進(jìn)后的Mesh?Pull算法各節(jié)點(diǎn)的時(shí)間變化較大，未優(yōu)化的Mesh?Pull算法各節(jié)點(diǎn)的時(shí)延時(shí)間變化較為平穩(wěn)，平均維持在24 ms左右。雖然改進(jìn)后的算法各節(jié)點(diǎn)時(shí)延時(shí)間變化較大，但是普遍來(lái)說(shuō)，改進(jìn)后算法大部分節(jié)點(diǎn)的時(shí)延較未改進(jìn)的要低，平均時(shí)延時(shí)間維持在22 s左右，有的節(jié)點(diǎn)的時(shí)延時(shí)間減幅達(dá)到4 ms，驗(yàn)證了本文算法的有效性。

5 結(jié) 語(yǔ)

綜上所述，針對(duì)當(dāng)前Mesh?Pull算法在吞吐量相對(duì)較低與時(shí)延相對(duì)較高的不足，本文闡明了優(yōu)化的BMesh?Pull算法。從時(shí)延與吞吐量?jī)蓚€(gè)層面入手，確定最佳的兩個(gè)節(jié)點(diǎn)進(jìn)行信息傳輸，使得系統(tǒng)的傳輸性能有所提升。經(jīng)由Matlab仿真實(shí)驗(yàn)?zāi)軌虻弥?，本文提出的?yōu)化MePull_db方法具有相對(duì)較好的效果。與當(dāng)前的Mesh?Pull法比較，優(yōu)化方法的啟動(dòng)延時(shí)有所減少，同時(shí)其吞吐量同樣有所優(yōu)化。利用MePull_db法能夠充分發(fā)揮當(dāng)前Mesh?Pull法的優(yōu)點(diǎn)，在此基礎(chǔ)上，也可以明顯改善吞吐量與時(shí)延兩個(gè)方面的不足，對(duì)比來(lái)說(shuō)，前者的時(shí)延比后者縮減了2～4 ms；另一方面，前者的吞吐量大幅改善，改善幅度達(dá)到5.3%～38.1%。因此，本文提出的優(yōu)化MePull_db算法表現(xiàn)出相對(duì)突出的優(yōu)越性，能夠在增加系統(tǒng)吞吐量的基礎(chǔ)上有效縮減時(shí)延。

參考文獻(xiàn)

[1] 張旭，殷昌盛，熊輝，等.無(wú)線Mesh網(wǎng)絡(luò)中基于離散粒子群優(yōu)化的信道分配算法[J].現(xiàn)代電子技術(shù)，2013，36（8）：31?34.

[2] 王子凡，劉作學(xué)，代健美.基于干擾感知的多接口無(wú)線Mesh網(wǎng)絡(luò)信道分配算法[J].現(xiàn)代電子技術(shù)，2014，37（14）：24?27.

[3] 李茜，劉經(jīng)緯，呂仁健，等.同步無(wú)線Mesh網(wǎng)絡(luò)數(shù)據(jù)包連發(fā)技術(shù)研究[J].現(xiàn)代電子技術(shù)，2014，37（15）：49?54.

[4] 班迪.無(wú)線Mesh網(wǎng)絡(luò)的數(shù)據(jù)分發(fā)策略[D].杭州：浙江工業(yè)大學(xué)，2015.

[5] YANG Qiuling， JIN Zhigang， HUANG Xiangdang. Research on delay and packet loss control mechanism in wireless Mesh networks [J]. Journal of networks， 2014， 9（4）： 859?865.

[6] 周宇，楊維.改進(jìn)的無(wú)線多跳Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015，33（2）：1263?1266.

[7] ZHANG B X， MOUFTAH H T. Destination?driven shortest path tree algorithms [J]. Journal of high speed network， 2006， 15（2）： 123?130.

[8] 田浩，楊霖，李少謙.LTE上行鏈路中基于探測(cè)參考信號(hào)的信噪比估計(jì)[J].電子與信息學(xué)報(bào)，2014，36（2）：353?357.

[9] 程?hào)|升.連續(xù)數(shù)據(jù)保護(hù)系統(tǒng)中數(shù)據(jù)分塊策略研究[D].武漢：華中科技大學(xué)，2013.

[10] 高奧子，張晉豫.基于數(shù)據(jù)塊優(yōu)先級(jí)與負(fù)載性能自適應(yīng)P2P流媒體數(shù)據(jù)調(diào)度算法[J].計(jì)算機(jī)科學(xué)與技術(shù)匯刊（中英文版），2014，12（3）：102?108.