改進的無線多跳mesh網絡數據分發算法

周 宇，楊 維

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

0 引 言

現有的無線mesh網絡在盡可能提高系統吞吐量的同時，要保證傳輸的實時性和穩定性，也就是降低系統時延［1－3］。

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

1 現有Mesh－Pull算法的問題

Mesh－Pull算法核心就是調度節點在請求數據的時候給鄰居節點發送請求消息，鄰居節點收到請求信息之后再發送需要的數據塊給調度節點。Mesh－Pull這種分發方式不需要考慮整個網絡中的節點信息，但是存在的問題是不一定當前時刻傳輸的數據塊是用戶最需要的，而用戶最需要的數據塊卻有可能一直在緩存區等待傳輸，造成很大的傳輸時延。這樣的數據傳輸方式就會造成用戶觀看視頻時候的不流暢，影響用戶體驗。同時，帶寬往往能決定網絡的容量和傳輸效率，帶寬衰減越小的網絡傳輸效率也會越大［6］。對于無線mesh網絡數據傳輸而言，要保證數據傳輸的連續性，就需要嚴格控制噪聲引起的信號衰減［7，8］。

圖1建立了無線mesh網絡中的數據分發方式模型。其中給每個鄰居節點緩存的數據塊編號，不同的編號表示每個節點緩存含有不同的數據塊。在Mesh－Pull的算法中，調度節點i開始發出數據請求信息，調度節點i就與相應的鄰居節點交換可用數據的消息，同時查看該鄰居節點是否含有請求的數據塊，鄰居節點如果擁有該數據塊，就會告訴請求節點自己有該數據塊，這時請求節點就會從所有含請求數據塊的鄰居節點中選擇最合適的鄰居節點請求數據，完成后再進行下一輪數據請求。

圖1 Mesh－Pull的數據分發方式

從Mesh－Pull分發方式可以看出，每一次數據請求過程中，發送請求和響應請求都需要等待一段時間，這樣就會造成網絡傳輸時延較大，吞吐量較低，影響網絡傳輸性能。

2 改進的BMesh－Pull數據分發算法

改進的BMesh－Pull算法是在Mesh－Pull算法的基礎上，綜合考慮了傳輸時延和吞吐量對于網絡數據傳輸的影響。其核心思想是在建模中通過優先級調度算法先確立了需要傳輸的數據塊不同的優先級。再利用帶寬和信噪比的關系為該數據塊分配合適的響應鄰居節點。

圖2給出了改進的BMesh－Pull數據分發算法的思想流程圖。無線Mesh節點i開始第N 次數據請求，根據優先級調度算法，確定最需要在網絡中傳輸的數據塊a，完成數據塊優先級的調度，再通過帶寬和信噪比估計為該數據塊a選擇最合適的鄰居節點j，完成數據分發的過程。

改進的BMesh－Pull算法考慮了傳輸時延和網絡吞吐量的問題，建立了最優化選擇機制。

圖2 BMesh－Pull數據分發算法的思想流程

3 數據分發建模

如圖3所示給出了一個數據分發的滑動窗口。在傳輸中，網絡將要傳輸的數據內容分為許多個大小一樣的數據塊，每個數據塊都會有一個編號。其中數據塊c表示當前播放時刻，數據塊d表示播放過錯過了的數據，數據塊a表示已經到達的數據，數據塊b表示缺失的需要傳輸的數據塊。從滑動窗口的示意圖可以直觀看到數據塊的緊急程度。

圖3 滑動窗口

數據分發建模前先定義了一些參數如表1所示，這些參數用于描述改進的BMesh－Pull數據分發算法。

表1 BMesh－Pull算法用到的描述參數

改進的數據分發算法的核心有兩個部分，首先通過優先級調度算法選擇最需要在網絡中傳輸的數據塊a，再通過帶寬和信噪比估計為數據塊a選擇最合適的鄰居節點j。

要確定節點i請求數據時最需要在網絡中傳輸的數據塊a，分別要從數據塊的優先級以及數據塊最少的提供者的數量這兩方面對每個需要傳輸的數據塊定義請求順序的優先級［9］。在這里定義了一個優先級算法的公式

其中，Fia表示數據塊a 對于節點i的優先級大小。0≤β≤1，β越大表示更需要考慮數據提供者的數量，β越小表示更需要考慮迫切需要數據塊的程度。通過比較Fia的大小，就會得到一個需要在網絡中傳輸的數據塊的優先級順序，按照這個優先級順序再對鄰居響應節點發送請求信息。

要為數據塊a選擇最合適的鄰居節點j，分別從是帶寬和信噪比的影響兩個角度考慮。

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

令BWi［n］［p＋1］來表示第p＋1周期時節點i選擇鄰居節點n 進行數據傳輸時的帶寬估計。用下面的公式表示在第p＋1周期時節點i對其鄰居節點n 有效帶寬估計

（2）信噪比SNR 影響的考慮：信噪比越高往往可以使得信號的傳輸更為快速有效［10］。信噪比也是會影響網絡傳輸性能的重要因素。信噪比在網絡中往往是不確定的，建模的時候把節點之間的信噪比大小控制在一定的范圍之內選擇隨機的值，這樣是比較符合實際的情況。

在這里定義了SNRMIN 表示信噪比SNR 的臨界值，SNRAVR ［ikn］表示鄰居節點n前m 個周期中與節點i 傳輸數據的信噪比平均值。基本思想是在第m＋1個周期時考慮節點i的SNRAVR ［ikn］，把SNRAVR ［ikn］的值與SNRMIN 進行比較來選擇最合適鄰居節點j。

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

4 仿真實驗和性能分析

采用了Matlab 軟件來進行網絡仿真分析。總共設定100個對等的節點來模擬無線mesh 網絡中的mesh 節點，每一個節點其鄰居節點個數設為10 個。初始帶寬設定為10 MHz。初始信噪比范圍由Matlab中的隨機函數所產生，最小的值作為臨界值SNRMIN。

4.1 節點的吞吐量

通過設定上述的仿真環境，編寫仿真程序，圖4 中顯示了加入了最優化選擇機制和沒有加入最優化選擇機制兩種條件下，β節點平均吞吐量之間的關系。其中橫軸表示影響因子β，縱軸表示節點平均吞吐量 （kbps）。定義節點的吞吐量為在網絡中的單位時間里每個節點從其它節點獲得的數據量。加入最優化選擇機制指的采用改進的BMesh－Pull最優化算法，沒有加入最優選擇機制指的是采用現有的Mesh－Pull算法。

β是最優化選擇的關鍵影響因子，在實驗中分別選取了β＝0，0.4，0.6，0.9，1這幾個值，來綜合考慮β與吞吐量的關系。

圖4 節點平均吞吐量和β的關系

圖4中仿真結果可以看到，在加入最優化選擇機制條件下，除了β＝0.4的時候，節點平均吞吐量對比沒有加入最優選擇機制條件下降了5.3%，但是其余的情況下節點平均吞吐量對比沒有加入最優選擇機制條件提高了5.2%－37.5%，說明了加入最優化選擇機制提高了節點平均吞吐量。同時，在β＝0.6時，節點平均吞吐量達到最大，說明數據塊的緊急程度和數據塊的最少提供者數量這兩種因素都是影響節點平均吞吐量的關鍵性因素，缺了任何一部分都會對節點平均吞吐量有很大的影響，與理論分析的結果相對應。

4.2 啟動延時

無線Mesh網絡系統性能的一個重要指標就是節點的啟動延時，該指標特別會影響流媒體傳輸效率，關系到用戶的切身體驗。圖5所示了10到24號節點與啟動時延的關系。其中橫軸表示節點編號的名稱，縱軸表示各節點從開始請求數據時到傳輸完成的啟動時延 （ms）。將節點啟動時延定義為能夠使流媒體文件中最開始數據塊正常傳輸所需要的時間。

圖5 相對應節點與啟動時延的關系

圖5仿真結果可以發現，在加入了最優化選擇機制的條件下，選取的15個節點中有12個節點的啟動延時相比沒有加入最優選擇機制條件都有1ms－5ms上的降低，只有3個節點啟動延遲相比沒有加入最優選擇機制條件有所增加。這說明了加入了最優化選擇機制可以降低網絡的傳輸時延，這也是與理論分析的結果相對應的。

5 結束語

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

［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）.［孫知信，陳亞當，任志廣.基于P2P流媒體直播系統的數據傳輸策略 ［J］.通信學報，2011，32 （6）：1－4.］

［2］LI Zhijie，FANG Xuming.Method of cross－layer scheduling in wireless mesh networks［J］.Journal of the China Railway Society，2012，34 （10）：61－64 （in Chinese）. ［李志杰，方旭明.無線Mesh網絡中一種QoS保證的跨層調度方法 ［J］.鐵道學報，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）.［陳樂瑞，孔金生.基于改進遺傳算法的網絡路由優化研究［J］.計算機應用與軟件，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流媒體直播調度算法研究［D］.秦皇島：燕山大學，2010.］

［5］ZHANG Hong.Strategy of distributing streaming media data in P2Pnetwork ［J］.Heilongjiang Science and Technology Information，2013 （22）：149 （in Chinese）.［張弘.P2P網絡的流媒體數據分發策略淺析［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）.［劉建生，魏楠青，樂光學，等.P2P大規模流媒體調度技術研究 ［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）. ［劉鐵，時國美，黃秋元，等.一種改進的OFDM 系統中信噪比估計算法 ［J］.網絡新媒體技術，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流媒體數據調度算法 ［J］.計算機應用，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）.［馮建春.高信噪比短波數字接收機的設計與實現 ［D］.武漢：武漢理工大學，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）.［陳樂瑞，孔金生.基于改進遺傳算法的網絡路由優化研究［J］.計算機應用與軟件，2013，30 （4）：135－137.］