基于數據塊優先級的無線多跳Mesh網絡數據分發算法

摘 要： 為了解決當前無線多跳Mesh網絡數據分發算法大都使用Mesh?Pull分發策略，導致其傳輸性能較弱，以及較大的數據分發時延的不足，設計了基于數據塊優先級的無線多跳Mesh網絡數據分發算法。首先，基于Mesh?Pull方法，考慮其吞吐量與時延的干擾作用，定義了最優化擇取機制，并引入數據塊的優先級，確定網絡中的待傳輸數據塊的請求排序，并通過評估Mesh網絡的帶寬和SNR值，尋找出最優鄰居節點。實驗數據顯示，與當前Mesh?Pull數據分發算法相比，該算法具有更低的網絡時延與更高的吞吐量。

關鍵詞： Mesh網絡； 數據分發； 數據塊優先級； 網絡延遲； 數據分發

中圖分類號： TN919.2?34 文獻標識碼： A 文章編號： 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 引 言

隨著計算機網絡技術的日益發展與完善，無線Mesh網絡也得到了廣泛應用，與此同時，由于用戶響應體驗要求的提高，無線Mesh網絡面臨更大的挑戰與要求，尤其是數據分發能力，不但需要兼顧更高的吞吐量與傳輸穩定性，而且更需要降低網絡數據傳輸時延[1?3]。

為了更好地擴展無線Mesh網絡的實用性，諸多學者提出了相應的無線Mesh網絡數據分發算法。如班迪等人為了提高Mesh網絡的數據分發能力[4]，提出了改進的數據傳遞策略，該技術在選擇錨點時，利用期望傳輸次數（Expected Transmission Count，ETX）作為通信鏈路的權值，以此降低整條數據傳遞路徑的ETX值，實驗結果顯示其算法具有較高的數據吞吐量與理想的分發試驗。Qiuling Yang等人為了解決無線頻道的干擾影響，提高數據分發能力，提出了基于TCP控制機制的無線Mesh網絡數據分發策略[5]，通過延遲分布，構建網絡時延模型，精確實時控制數據傳輸時延，實驗結果驗證了其算法的優異性。

然而，當前無線Mesh網絡數據分發算法大都是側重于網絡構建方面，且大都是基于Mesh?Pull，策略動態性不強，當傳輸數據塊并非是用戶理想數據時，會導致大量的數據排隊，造成巨大的網絡時延[6]。

對此，本文設計了基于數據塊優先級的無線多條Mesh網絡數據分發算法。首先，基于Mesh?Pull法，兼顧其吞吐量與時延的干擾作用，定義了最優化擇取機制，并引入數據塊的優先級，確定網絡中的待傳輸數據塊的請求排序，并通過評估Mesh網絡的帶寬和SNR（Signal to Noise Ratio）值，尋找出最優鄰居節點。最后測試了本文算法的網絡性能。

1 基于Mesh?Pull策略的數據分發技術

在當前的Mesh網絡數據分發算法中，大都采用Mesh?Pull機制，該技術的核心思想為：Mesh網絡中的調度節點在請求數據過程中，將數據的排序請求傳播到其領域節點，當接收到請求后，迅速向調度節點提供相應的數據塊。雖然Mesh?Pull策略不需要考慮整個Mesh網絡中的節點，但是，當網絡中的傳輸數據塊不是用戶最需要的，從而導致大量的節點數據處于等待狀態，產生較大的網絡時延。為了確保Mesh網絡的連續數據傳輸，需要將噪聲引起的信號衰減程度控制在一個合適的水平[6]。

圖[1]是Mesh?Pull策略的數據分發過程，可見該策略首先對各鄰居節點緩存的數據塊完成編號，以表征其數據塊數量。調度節點[i]廣播接收請求，則其將與鄰居節點貢獻可用資源。并在此基礎上查看請求的數據塊是不是存在于后者之中，若存在其中，后者將會把結果向前者告知，這種情況下，前者將從中選出最佳數據快，結束以后，重新開始數據請求[6?7]。

依據Mesh?Pull策略的工作原理可知，調度節點發出請求及響應時，二者有可能處于等待狀態，從而增大了網絡傳輸時延，降低了數據吞吐量，嚴重影響了網絡性能。

2 本文Mesh數據分發算法

針對Mesh?Pull策略的不足，本文以網絡吞吐量與時延為目標，提出了基于數據塊優先級的無線多條Mesh網絡數據分發算法，其流程見圖2。通過先確定各個數據塊的優先級確定最佳領域節點。調度節點[i]發出第[N]次請求，再依據其優先級，確定其相應的數據塊[a，]并引入信噪比與帶寬，確定出數據塊[a]的最優領域節點。

3 數據分發建模

在Mesh數據分發算法改進的基礎上建立數據分發模型。分發算法的關鍵內容體現在：首先需要確定改進的分發算法中數據塊傳遞的優先級別。這里假設節點名稱為[i，i]對網絡中傳送的數據發送請求，用[Fia]量化數據塊對于節點[i]的優先級。[Fia]作為量化的優先級大小，分別從數據塊提供數量和數據塊自身優先級2個指標入手，具體的表達式為：

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

式中：[β]是衡量數據塊提供數量的指標，其值范圍大小為[0≤β≤1]，[β]的大小體現數據提供數量在優先級量化過程中的權重，[β]越大體現該指標在[Fia]中的權重越大；[D]代表與節點相關的鄰居點的個數。式中其他參數的意義如表1所示。

確定數據塊優先級后，需要為數據塊確定最優鄰居節點[j，]故需要完成鄰居節點的尋找工作，此過程依據信噪比估計和寬帶估計對最優鄰居節點進行評估。

在各節點之間信噪比估計過程中，根據實際網路信號傳遞過程，信號節點之間的信噪比對信號的傳遞過程具有較大的影響，而信噪比的不確定性造成在信號傳遞過程中兼顧信噪比的范圍，信噪比的峰值越大，則對應的信號傳遞越流暢。在信噪比估計判斷最優鄰居節點的過程中，定義兩個參數，分別是信噪比估計的極限最小值，這里用SNPMIN表示，另外一個參數為[SNRAVR[ikn]]，表示節點[i]與各個鄰居節點在一定周期內信噪比的平均值，以[SNRAVR[ikn]]與SNPMIN的大小為判斷依據，即分別計算節點[i]與各個鄰居節點的均值，在均值大于極限最小值時，這里就認為該節點為[i]的最優鄰居節點[j。]如果不滿足以上的判斷依據，則系統一直處于鄰居節點的尋優過程。

寬帶估計對最優鄰居節點的影響，主要原理是兼顧全部包含[a]的鄰居節點[n，]將[n]在前[p]個周期中向[i]發送的帶寬數據當做相應的帶寬估計，在此基礎上按照所獲得信息確定第[p+1]個周期時與[i]傳輸帶寬最大的[n]。

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

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

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

根據以上數據分發算法的模型建立過程，數據傳輸包含大量的數據模塊，各個數據模塊之間存在數據優先次序的不同，可理解為不同數據模塊所處的位置和功能隨時間的變化而變化，此時可用一個滑動窗口形象地表示各個數據塊之間的關系，即優先次序，如圖3所示。

4 仿真實驗與結果分析

通過Matlab對本文構建的數據分發算法模型進行仿真實驗，設定仿真基本參數，根據第三部分理論算法，設定信噪比的范圍由仿真軟件內部函數提供，其中內部函數的最小值作為信噪比最小值。寬帶估計值為12 Hz。為了能充分驗證本文算法的有效性，這里對數據分發節點數目的選擇為120，每一個節點對應的鄰居節點個數為12。

4.1 吞吐量

所謂節點吞吐量，即單位時間里在網絡中各節點從其他節點得到的數據量。利用上文中的測試環境進行相應的編程，具體數據如圖4所示，在這里，橫坐標用來指代[β（0<β<1），]是體現數據塊數量和數據塊優先級在網絡信號傳遞過程中的優先級權重判斷，這里對參數[β]取值為0.1，0.3，0.5，0.7，0.9，研究數據塊數據提供數量和數據塊自身優先級對吞吐量的影響，而縱坐標則是對應的不同[β]參數下，對應節點的平均吞吐量，圖4比較形象地展示了Mesh算法改進前后節點的平均吞吐量。

根據圖4，改進后的算法和未改進的算法對應的相同[β]參數下的節點吞吐量的值有高有低。在[β=0.7]的情形下，節點評價吞吐量的值達到最高，根據[β]參數的含義，[β]參數越大說明數據供應數量對吞吐量值影響大于數據塊緊急程度對吞吐量的影響。[β=0.7]吞吐量達到最大值，說明數據供應數量的大小對數據塊優先級別起到關鍵影響作用。從圖4總體來說，對于優化的MePull_db算法，除去[β=0.5]時，節點的吞吐量小于未改進Mesh?Pull算法外，其他參數下，改進算法的平均吞吐量提高幅度處于5.3%～38.1%范圍內，因此，通過對比數據能夠得知，MePull_db算法在很大程度上改善了吞吐量。

4.2 啟動延遲

網絡信息傳遞過程中，網絡延遲較為常見。網絡延遲導致用戶在使用過程中產生較差的評價，故在對網絡評價效果方面，網絡延時較為直觀，也是比較重要的指標。為了驗證本文算法在網絡延遲方面的表現，這里選取20個節點對本文算法和未改進的算法進行檢測，如圖5所示，圖中分別表述了各個節點對應的延遲時間，該延遲時間對應的就是客戶等待時間，橫坐標表示節點，縱坐標是對應的各節點的延遲，單位用ms表示，圖中兩條曲線分別代表改進和未改進算法對應的啟動延遲時間的長短。

從圖5中可以看出，各個節點對應的時延時間有所不同，改進后的Mesh?Pull算法各節點的時間變化較大，未優化的Mesh?Pull算法各節點的時延時間變化較為平穩，平均維持在24 ms左右。雖然改進后的算法各節點時延時間變化較大，但是普遍來說，改進后算法大部分節點的時延較未改進的要低，平均時延時間維持在22 s左右，有的節點的時延時間減幅達到4 ms，驗證了本文算法的有效性。

5 結 語

綜上所述，針對當前Mesh?Pull算法在吞吐量相對較低與時延相對較高的不足，本文闡明了優化的BMesh?Pull算法。從時延與吞吐量兩個層面入手，確定最佳的兩個節點進行信息傳輸，使得系統的傳輸性能有所提升。經由Matlab仿真實驗能夠得知，本文提出的優化MePull_db方法具有相對較好的效果。與當前的Mesh?Pull法比較，優化方法的啟動延時有所減少，同時其吞吐量同樣有所優化。利用MePull_db法能夠充分發揮當前Mesh?Pull法的優點，在此基礎上，也可以明顯改善吞吐量與時延兩個方面的不足，對比來說，前者的時延比后者縮減了2～4 ms；另一方面，前者的吞吐量大幅改善，改善幅度達到5.3%～38.1%。因此，本文提出的優化MePull_db算法表現出相對突出的優越性，能夠在增加系統吞吐量的基礎上有效縮減時延。

參考文獻

[1] 張旭，殷昌盛，熊輝，等.無線Mesh網絡中基于離散粒子群優化的信道分配算法[J].現代電子技術，2013，36（8）：31?34.

[2] 王子凡，劉作學，代健美.基于干擾感知的多接口無線Mesh網絡信道分配算法[J].現代電子技術，2014，37（14）：24?27.

[3] 李茜，劉經緯，呂仁健，等.同步無線Mesh網絡數據包連發技術研究[J].現代電子技術，2014，37（15）：49?54.

[4] 班迪.無線Mesh網絡的數據分發策略[D].杭州：浙江工業大學，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] 周宇，楊維.改進的無線多跳Mesh網絡數據分發算法[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上行鏈路中基于探測參考信號的信噪比估計[J].電子與信息學報，2014，36（2）：353?357.

[9] 程東升.連續數據保護系統中數據分塊策略研究[D].武漢：華中科技大學，2013.

[10] 高奧子，張晉豫.基于數據塊優先級與負載性能自適應P2P流媒體數據調度算法[J].計算機科學與技術匯刊（中英文版），2014，12（3）：102?108.