同步無線Mesh網絡帶寬申請與分配策略的改進

王未名+焦蓉+劉經緯+呂仁健+韓仲華

摘 要： 數據通信具有突發性與帶寬計算的不確定性，現有同步無線Mesh網絡帶寬申請與分配策略未對此問題進行充分考慮，在設計上存在帶寬申請速度慢、帶寬分配沒有最大化、將數據時隙區分了上下行等不足，導致了QoS保障能力低與網絡性能的下降。提出了帶寬申請與分配策略的改進方案，包括結合各類數據業務類型的帶寬申請條件的描述、檢查數據發送隊列的時間間隔描述、帶寬分配最大化的描述、數據時隙不再區分上、下行的描述。理論分析表明，改進后的方案能夠提供精確的QoS保障并提高網絡性能。

關鍵詞： 同步無線Mesh網絡； 帶寬申請； 帶寬分配； 數據時隙； 帶寬分配表

中圖分類號： TN711?34； TP393.04 文獻標識碼： A 文章編號： 1004?373X（2014）16?0024?04

Improvement of bandwidth request and allocation for synchronized WMN

WANG Wei?ming1， JIAO Rong2， LIU Jing?wei2， [LU] Ren?jian2， 3， HAN Zhong?hua2

（1. China Electronics Technology Group Corporation， Beijing， 100846， China；2. North China Institute of Computing Technology，Beijing，100083，China；

3. School of Computer Science， Beijing University of Posts and Telecommunications， Beijing， 100876， China）

Abstract： Data communication has uncertainty features of suddenness and bandwidth calculation uncertainty. These factors have not been fully considered in existing bandwidth request and allocation strategy for synchronized WMN， so the slow bandwidth request， non?maximized bandwidth allocation and the division of upstream and downstream data time?slot are existed in the design， which cause the low QoS guarantee capability and network performance decline. An improved scheme for bandwidth request and allocation strategy is proposed， in which there are bandwidth request description for various data business types， the time interval description of the data transmission queue check， the maximized bandwidth allocation description and the mergence description of upstream and downstream data time?slot. Theoretical analysis shows that the fine QoS guarantee and the high performance can be realized in the improved solution.

Keywords： synchronized WMN； bandwidth request； bandwidth allocation； data time?slot； bandwidth allocation table

0 引 言

基于多方向天線陣列[1]的同步無線Mesh網絡（Synchronized WMN）通過多根高增益定向天線在全向范圍內完成了多扇區的高速掃描，使節點具備了單跳最大20 km通信距離的能力，而通過專有同步無線Mesh網絡協議技術，使網絡具備了多跳組網能力與高效數據傳輸能力，從而適用于寬帶的機動組網應用領域。

同步無線Mesh網絡的性能取決于硬件能力與與協議軟件能力。硬件能力[2?4]包括多方向天線陣列硬件結構與底層無線數據收發信機，協議軟件能力[5?7]包括軟件平臺基礎性能與同步無線Mesh網絡協議性能。同步無線Mesh網絡協議性能主要與底層同步數據的收發性能與上層帶寬申請與分配策略有關，合理的帶寬申請與分配策略可以在恰當的時機產生帶寬申請并在最短時間內給出帶寬分配結果，并且可以保證其在大規模網絡運行下的快速收斂性。

現有同步無線Mesh網絡協議在帶寬申請與分配策略上[8?10]仍存在以下不足，如進行改進，網絡性能可有進一步提升：

（1） 帶寬申請速度慢。現有策略為減少帶寬申請的發生次數，更多地參考了帶寬申請的歷史發送數據量從而降低了觸發帶寬申請的閾值，其歷史權重值為0.6，而周期檢查數據發送隊列待發送數據量的時間間隔為10 s，上述兩種參數可以保證網絡中各條鏈路在大部分時間內的帶寬使用趨于穩定。然而，當節點產生了實時數據并且現有帶寬不能滿足時，現有策略不能較快地觸發帶寬申請，導致了數據通信的等待時間過長。

（2） 帶寬分配沒有最大化。現有的帶寬分配策略為了降低未來新入網節點產生帶寬申請的可能性，對可分配帶寬進行了預留。然而，很多應用場合中的網絡拓撲結構很少發生變化，發生網絡重構或新節點加入網絡的可能性很小，其網絡的主要應用是保證帶寬最大化。

（3） 將數據時隙區分了上下行。現有的帶寬分配策略將數據時隙分成了上行數據時隙與下行數據時隙，保證了上下行數據分別擁有互不干擾的、穩定的帶寬。但實際情況是：帶寬分配策略實際難以準確估計數據傳輸所需要的帶寬，當上行數據傳輸完畢而下行數據傳輸又需要更多的帶寬時，所有上行時隙即被浪費。

產生上述問題的原因在于現有帶寬申請與分配策略未考慮到數據通信的突發性、貪婪性與帶寬計算的不準確性。本文將對上述問題進行解決，并提出同步無線Mesh網絡帶寬申請與分配策略的改進方案。

1 帶寬申請與分配策略的改進

1.1 提高帶寬申請速度

（1） 帶寬申請的條件

不再參考帶寬申請的歷史發送數據量，而以當前節點數據業務類型與數據發送隊列中的數據量的變化量決定是否進行帶寬申請。這樣有助于提高產生實時數據與大量突發數據時的帶寬申請速度，而不必要的帶寬申請則明顯減少。

帶寬申請不僅可以申請所需的數據時隙個數，也可以申請所需的數據時隙位置（數據時隙僅用于普通數據傳輸，并不用于鏈路維護等協議數據傳輸，因為協議數據傳輸是在不可分配的特殊時隙內完成）。將數據發送隊列按數據業務類型分類：Ping數據、IP語音數據、FTP數據、視頻數據，即每種數據業務各使用一個數據發送隊列。各類數據的數據量、帶寬申請情況如表1所示。

表1 各類數據的數據量、帶寬申請情況

各類數據觸發帶寬申請的條件如表2所示。

（2） 檢查數據發送隊列的時間間隔

縮短檢查數據發送隊列待發送數據量的時間間隔。將該時間間隔改為一個帶寬分配表所匹配的數據時隙長度（50個時隙長度），以此提高帶寬申請的實時性。

1.2 帶寬分配最大化

（1） 不進行帶寬預留，而是將所有可分配的帶寬都分配出去，以保證當前網絡內的時隙使用效率最高。當網絡拓撲結構改變或者有新節點加入網絡中后，將產生帶寬的重新分配，而重新分配后的帶寬分配仍然是最大化分配。

表2 各類數據產生帶寬申請的條件

（2） 帶寬申請既可以申請增加數據時隙，也可以申請減少數據時隙。只有這樣，才能把有限的帶寬資源分配給最需要帶寬的節點。

1.2.1 單跳網絡情況

單跳網絡情況比較簡單，如圖1所示。不論骨干1節點處于正在入網狀態還是入網后狀態，網關節點不按照骨干1節點的實際帶寬申請量分配帶寬，而是把自己所有帶寬都分給骨干1節點。

圖1 單跳網絡情況

1.2.2 星狀網絡情況

星狀網絡情況如圖2所示。網關節點根據骨干1與骨干2的帶寬申請對需要帶寬者進行最大化帶寬分配。

（1） 骨干2節點正在入網。當網關節點收到骨干2節點發出的表示將要從網關節點處入網的入網請求包后，網關節點將按照骨干2節點的帶寬申請量從分配給骨干1節點的帶寬中回收相應帶寬并分配給骨干2節點。回收帶寬的數量與位置則按照骨干2節點的帶寬申請策略。

圖2 星狀網絡情況

（2） 骨干2節點入網后。骨干2節點入網后，如果網關節點與骨干1節點、網關節點與骨干2節點之間的普通數據通信均已結束，網關節點不必更新帶寬分配表；否則，網關節點需要根據以下情況更新帶寬分配表：

① 網關節點與骨干1節點之間有小數據量數據通信（如Ping數據），網關節點與骨干2節點之間無普通數據通信。此時，網關節點將所有帶寬都重新分配給骨干1節點。

② 網關節點與骨干1節點、網關節點與骨干2節點之間都有小數據量數據通信（如Ping數據）。此時，網關節點將所有帶寬平均分配給骨干1節點與骨干2節點，并保證各自占有的數據時隙位置較為均勻。

③ 網關節點與骨干1節點之間有大數據量數據通信（如視頻數據與FTP數據），網關節點與骨干2節點之間有小數據量數據通信（如Ping數據）。此時，網關節點將所有帶寬中的大部分帶寬分配給骨干1節點，并保證各自占有的數據時隙位置較為均勻。

④ 網關節點與骨干1節點、網關節點與骨干2節點之間都有大數據量數據通信（如視頻數據與FTP數據）。此時，網關節點將所有帶寬平均分配給骨干1節點與骨干2節點，并保證各自占有的數據時隙位置較為均勻。

在以上情況中，如果網關節點與骨干1節點或者網關節點與骨干2節點之間的數據通信結束，數據通信結束的節點需要以帶寬申請的方式（意為取消帶寬申請）通知網關節點，網關節點便可以在其他節點有新的帶寬申請時將分配給數據通信結束的節點的帶寬回收并重新分配給需要帶寬的節點。最后，如果骨干1節點或骨干2節點都進行帶寬申請，但帶寬申請總量超過可分配帶寬總量時，網關節點將按比例為帶寬節點分配帶寬。此時，需要帶寬節點不需再次發送同樣的帶寬申請，直至某個節點的數據發送隊列中的數據量又有新的變化。

1.2.3 鏈狀網絡情況

鏈狀網絡情況如圖3所示。網關節點為骨干1節點分配帶寬，骨干1節點為骨干2節點分配帶寬。

（1） 骨干2節點正在入網。當骨干1節點收到骨干2節點發出的表示將要從骨干1節點處入網的入網請求包后，骨干1節點將按照骨干2節點的帶寬申請量向網關節點申請帶寬（即取消一部分網關節點分配給自己的帶寬）。當網關節點取消一部分分配給骨干1節點的帶寬后，骨干1節點再將這些帶寬分配給骨干2節點。

圖3 鏈狀網絡情況

（2） 骨干2節點入網后。骨干2入網后，如果網關節點與骨干1節點、骨干1節點與骨干2節點之間的普通數據通信均已結束，網關節點與骨干1節點均不必更新帶寬分配表；否則，網關節點與骨干1節點需要根據以下情況更新帶寬分配表：

① 網關節點與骨干1節點之間有小數據量數據通信（如Ping數據），骨干1節點與骨干2節點之間無普通數據通信。此時，骨干1節點將回收骨干2節點的帶寬并以帶寬申請的方式通知網關節點，網關節點再將所有帶寬重新分配給骨干1節點。

② 網關節點與骨干1節點、骨干1節點與骨干2節點之間都有小數據量數據通信（如Ping數據）。此時，骨干2節點將向骨干1節點發出帶寬申請，骨干1節點收到該申請后將結合了自己的帶寬申請的帶寬申請發送給網關節點。網關節點將帶寬分配表中相應位置的數據時隙分配給骨干1節點，骨干1節點獲得自己的帶寬后再將其他可分配帶寬分配給骨干2節點。

③ 網關節點與骨干1節點間有大數據量通信（如視頻數據與FTP數據），骨干1節點與骨干2節點之間有小數據量數據通信（如Ping數據）。該處理過程與②過程類似，不再贅述。網關節點與骨干1節點、骨干1節點與骨干2節點之間都有大數據量數據通信（如視頻數據與FTP數據）。該處理過程與②、③過程類似，不再贅述。

在以上情況中，如果網關節點與骨干1節點或骨干1節點與骨干2節點之間的數據通信結束，數據通信結束的節點需要以帶寬申請的方式（意為取消帶寬申請）通知其上游節點，上游節點便可以在自己有新的帶寬申請時重新分配帶寬或者向更上游節點重新申請帶寬。最后，如果骨干1節點或骨干2節點都進行帶寬申請，但帶寬申請總量超過可分配帶寬總量時，各個上游節點將按比例為需要帶寬的節點分配帶寬。此時，需要帶寬的節點不需再次發送同樣的帶寬申請，直至某個節點的數據發送隊列中的數據量又有新的變化。

1.3 數據時隙不再區分上下行

節點申請的帶寬實際是數據時隙，這些數據時隙由帶寬申請者與帶寬分配者共享，即這些數據時隙只表明其歸屬哪對節點，不表明數據傳輸的上下行方向。數據傳輸的上下行方向由帶寬分配者在每個數據時隙的開始臨時決定。帶寬分配者在自己的發送下行數據的需求與帶寬申請者發送上行數據的需求進行權衡，并依據雙方的數據業務類型與實時性要求決定每個時隙的上下行方向。當某一方向的數據傳輸結束后，該方向的數據時隙將全部用于另外一個方向的數據傳輸。

2 策略改進前后的性能比較

現對帶寬申請與分配策略改進前后的性能比較進行定性分析，具體見表3。

3 結 語

提出了帶寬申請與分配策略的改進方案，包括結合各類數據業務類型的帶寬申請條件的描述、檢查數據發送隊列的時間間隔的描述、帶寬分配最大化的描述、數據時隙不再區分上下行的描述。理論分析表明，改進后的方案能夠提供精確的QoS保障并提高網絡性能。

參考文獻

[1] 雷昕，郭琳，韓仲華，等.寬帶無線Mesh網絡中的多扇區天線陣列設計[J].中國電子科學研究院學報，2012（4）：178?181.

[2] 李佳，周杰.無線Mesh網絡集中式信道分配算法設計[J].無線電工程，2009（12）：3235?3237.

[3] 劉賀，張陸勇，陳明剛，等.無線Mesh網絡集中式信道分配算法設計[J].無線電工程，2011（5）：4?6.

[4] 蘇家勇，許磊，周國.無線Mesh網絡中的信道分配問題研究[J].無線電通信技術，2009，33（5）：4?6.

[5] 張克非，楊壽保，胡云，等.基于多QoS參數約束的無線Mesh網絡路由機制研究[J].計算機應用研究，2009，26（3）：994?996.

[6] 邱振謀，姚國祥，官全龍，等.多信道無線Mesh網絡的多播信道分配算法[J].計算機工程，2011，37（6）：107?109.

[7] 李鶴松，冷甦鵬.一種新型無線Mesh網絡多信道MAC協議[J].計算機工程與應用，2011，47（26）：66?69.

[8] 謝桂芳，段盛，羅玉玲.無線Mesh網絡信道分配研究[J].計算機工程與應用，2011，47（18）：85?87.

[9] 韓冬，鄢楚平，王志泉，等.基于NDIS的無線Mesh網絡協議的研究和實現[J].計算機工程與設計，2011，32（3）：784?787.

[10] 何萍實，徐子平.無線Mesh網絡中使用雙收發器的多信道MAC協議研究[J].計算機應用研究，2010，27（1）：327?329.

圖3 鏈狀網絡情況

（2） 骨干2節點入網后。骨干2入網后，如果網關節點與骨干1節點、骨干1節點與骨干2節點之間的普通數據通信均已結束，網關節點與骨干1節點均不必更新帶寬分配表；否則，網關節點與骨干1節點需要根據以下情況更新帶寬分配表：

① 網關節點與骨干1節點之間有小數據量數據通信（如Ping數據），骨干1節點與骨干2節點之間無普通數據通信。此時，骨干1節點將回收骨干2節點的帶寬并以帶寬申請的方式通知網關節點，網關節點再將所有帶寬重新分配給骨干1節點。

② 網關節點與骨干1節點、骨干1節點與骨干2節點之間都有小數據量數據通信（如Ping數據）。此時，骨干2節點將向骨干1節點發出帶寬申請，骨干1節點收到該申請后將結合了自己的帶寬申請的帶寬申請發送給網關節點。網關節點將帶寬分配表中相應位置的數據時隙分配給骨干1節點，骨干1節點獲得自己的帶寬后再將其他可分配帶寬分配給骨干2節點。

③ 網關節點與骨干1節點間有大數據量通信（如視頻數據與FTP數據），骨干1節點與骨干2節點之間有小數據量數據通信（如Ping數據）。該處理過程與②過程類似，不再贅述。網關節點與骨干1節點、骨干1節點與骨干2節點之間都有大數據量數據通信（如視頻數據與FTP數據）。該處理過程與②、③過程類似，不再贅述。

在以上情況中，如果網關節點與骨干1節點或骨干1節點與骨干2節點之間的數據通信結束，數據通信結束的節點需要以帶寬申請的方式（意為取消帶寬申請）通知其上游節點，上游節點便可以在自己有新的帶寬申請時重新分配帶寬或者向更上游節點重新申請帶寬。最后，如果骨干1節點或骨干2節點都進行帶寬申請，但帶寬申請總量超過可分配帶寬總量時，各個上游節點將按比例為需要帶寬的節點分配帶寬。此時，需要帶寬的節點不需再次發送同樣的帶寬申請，直至某個節點的數據發送隊列中的數據量又有新的變化。

1.3 數據時隙不再區分上下行

節點申請的帶寬實際是數據時隙，這些數據時隙由帶寬申請者與帶寬分配者共享，即這些數據時隙只表明其歸屬哪對節點，不表明數據傳輸的上下行方向。數據傳輸的上下行方向由帶寬分配者在每個數據時隙的開始臨時決定。帶寬分配者在自己的發送下行數據的需求與帶寬申請者發送上行數據的需求進行權衡，并依據雙方的數據業務類型與實時性要求決定每個時隙的上下行方向。當某一方向的數據傳輸結束后，該方向的數據時隙將全部用于另外一個方向的數據傳輸。

2 策略改進前后的性能比較

現對帶寬申請與分配策略改進前后的性能比較進行定性分析，具體見表3。

3 結 語

提出了帶寬申請與分配策略的改進方案，包括結合各類數據業務類型的帶寬申請條件的描述、檢查數據發送隊列的時間間隔的描述、帶寬分配最大化的描述、數據時隙不再區分上下行的描述。理論分析表明，改進后的方案能夠提供精確的QoS保障并提高網絡性能。

參考文獻

[1] 雷昕，郭琳，韓仲華，等.寬帶無線Mesh網絡中的多扇區天線陣列設計[J].中國電子科學研究院學報，2012（4）：178?181.

[2] 李佳，周杰.無線Mesh網絡集中式信道分配算法設計[J].無線電工程，2009（12）：3235?3237.

[3] 劉賀，張陸勇，陳明剛，等.無線Mesh網絡集中式信道分配算法設計[J].無線電工程，2011（5）：4?6.

[4] 蘇家勇，許磊，周國.無線Mesh網絡中的信道分配問題研究[J].無線電通信技術，2009，33（5）：4?6.

[5] 張克非，楊壽保，胡云，等.基于多QoS參數約束的無線Mesh網絡路由機制研究[J].計算機應用研究，2009，26（3）：994?996.

[6] 邱振謀，姚國祥，官全龍，等.多信道無線Mesh網絡的多播信道分配算法[J].計算機工程，2011，37（6）：107?109.

[7] 李鶴松，冷甦鵬.一種新型無線Mesh網絡多信道MAC協議[J].計算機工程與應用，2011，47（26）：66?69.

[8] 謝桂芳，段盛，羅玉玲.無線Mesh網絡信道分配研究[J].計算機工程與應用，2011，47（18）：85?87.

[9] 韓冬，鄢楚平，王志泉，等.基于NDIS的無線Mesh網絡協議的研究和實現[J].計算機工程與設計，2011，32（3）：784?787.

[10] 何萍實，徐子平.無線Mesh網絡中使用雙收發器的多信道MAC協議研究[J].計算機應用研究，2010，27（1）：327?329.

圖3 鏈狀網絡情況

（2） 骨干2節點入網后。骨干2入網后，如果網關節點與骨干1節點、骨干1節點與骨干2節點之間的普通數據通信均已結束，網關節點與骨干1節點均不必更新帶寬分配表；否則，網關節點與骨干1節點需要根據以下情況更新帶寬分配表：

① 網關節點與骨干1節點之間有小數據量數據通信（如Ping數據），骨干1節點與骨干2節點之間無普通數據通信。此時，骨干1節點將回收骨干2節點的帶寬并以帶寬申請的方式通知網關節點，網關節點再將所有帶寬重新分配給骨干1節點。

② 網關節點與骨干1節點、骨干1節點與骨干2節點之間都有小數據量數據通信（如Ping數據）。此時，骨干2節點將向骨干1節點發出帶寬申請，骨干1節點收到該申請后將結合了自己的帶寬申請的帶寬申請發送給網關節點。網關節點將帶寬分配表中相應位置的數據時隙分配給骨干1節點，骨干1節點獲得自己的帶寬后再將其他可分配帶寬分配給骨干2節點。

③ 網關節點與骨干1節點間有大數據量通信（如視頻數據與FTP數據），骨干1節點與骨干2節點之間有小數據量數據通信（如Ping數據）。該處理過程與②過程類似，不再贅述。網關節點與骨干1節點、骨干1節點與骨干2節點之間都有大數據量數據通信（如視頻數據與FTP數據）。該處理過程與②、③過程類似，不再贅述。

在以上情況中，如果網關節點與骨干1節點或骨干1節點與骨干2節點之間的數據通信結束，數據通信結束的節點需要以帶寬申請的方式（意為取消帶寬申請）通知其上游節點，上游節點便可以在自己有新的帶寬申請時重新分配帶寬或者向更上游節點重新申請帶寬。最后，如果骨干1節點或骨干2節點都進行帶寬申請，但帶寬申請總量超過可分配帶寬總量時，各個上游節點將按比例為需要帶寬的節點分配帶寬。此時，需要帶寬的節點不需再次發送同樣的帶寬申請，直至某個節點的數據發送隊列中的數據量又有新的變化。

1.3 數據時隙不再區分上下行

節點申請的帶寬實際是數據時隙，這些數據時隙由帶寬申請者與帶寬分配者共享，即這些數據時隙只表明其歸屬哪對節點，不表明數據傳輸的上下行方向。數據傳輸的上下行方向由帶寬分配者在每個數據時隙的開始臨時決定。帶寬分配者在自己的發送下行數據的需求與帶寬申請者發送上行數據的需求進行權衡，并依據雙方的數據業務類型與實時性要求決定每個時隙的上下行方向。當某一方向的數據傳輸結束后，該方向的數據時隙將全部用于另外一個方向的數據傳輸。

2 策略改進前后的性能比較

現對帶寬申請與分配策略改進前后的性能比較進行定性分析，具體見表3。

3 結 語

提出了帶寬申請與分配策略的改進方案，包括結合各類數據業務類型的帶寬申請條件的描述、檢查數據發送隊列的時間間隔的描述、帶寬分配最大化的描述、數據時隙不再區分上下行的描述。理論分析表明，改進后的方案能夠提供精確的QoS保障并提高網絡性能。

參考文獻

[1] 雷昕，郭琳，韓仲華，等.寬帶無線Mesh網絡中的多扇區天線陣列設計[J].中國電子科學研究院學報，2012（4）：178?181.

[2] 李佳，周杰.無線Mesh網絡集中式信道分配算法設計[J].無線電工程，2009（12）：3235?3237.

[3] 劉賀，張陸勇，陳明剛，等.無線Mesh網絡集中式信道分配算法設計[J].無線電工程，2011（5）：4?6.

[4] 蘇家勇，許磊，周國.無線Mesh網絡中的信道分配問題研究[J].無線電通信技術，2009，33（5）：4?6.

[5] 張克非，楊壽保，胡云，等.基于多QoS參數約束的無線Mesh網絡路由機制研究[J].計算機應用研究，2009，26（3）：994?996.

[6] 邱振謀，姚國祥，官全龍，等.多信道無線Mesh網絡的多播信道分配算法[J].計算機工程，2011，37（6）：107?109.

[7] 李鶴松，冷甦鵬.一種新型無線Mesh網絡多信道MAC協議[J].計算機工程與應用，2011，47（26）：66?69.

[8] 謝桂芳，段盛，羅玉玲.無線Mesh網絡信道分配研究[J].計算機工程與應用，2011，47（18）：85?87.

[9] 韓冬，鄢楚平，王志泉，等.基于NDIS的無線Mesh網絡協議的研究和實現[J].計算機工程與設計，2011，32（3）：784?787.

[10] 何萍實，徐子平.無線Mesh網絡中使用雙收發器的多信道MAC協議研究[J].計算機應用研究，2010，27（1）：327?329.