Ad hoc網絡中基于帶寬的準入控制研究

胡桃英，程運安，官駿鳴

1.合肥工業大學計算機與信息學院，合肥 230009

2.合肥工大高科信息科技股份有限公司，合肥 230088

3.黃山學院信息工程學院，安徽黃山 245400

Ad hoc網絡中基于帶寬的準入控制研究

胡桃英1，程運安1，官駿鳴2，3

1.合肥工業大學計算機與信息學院，合肥 230009

2.合肥工大高科信息科技股份有限公司，合肥 230088

3.黃山學院信息工程學院，安徽黃山 245400

在決定無線自組織網服務質量的諸多參數中，可用帶寬是至關重要的參數。通過引用泊松分布流量產生器產生數據包的概率和發送數據包的概率，研究由于隱藏節點引起沖突的概率，消除由于節點發生碰撞對可用帶寬的消耗。通過分析與推導，建立IIAB算法模型，并將IIAB加載到AODV協議，利用RREQ/RREP對新的業務流進行準許接入和資源預留，在此基礎上，提出了新的基于IIAB-AODV協議的準入控制機制。通過NS2網絡仿真平臺模擬表明：提出的模型提高了估測可用帶寬的精度以及基于IIAB-AODV協議的準入控制機制更能夠保障和提高網絡的服務質量。

無線自組織網；可用帶寬估測；準入控制；按需平面距離矢量路由（AODV）協議；服務質量

無線自組織網是由一組帶有無線收發裝置的移動節點組成的一種無線移動通信網絡，它不依賴于固定的基礎設施，因此為無線自組織網提供QoS保障是一個具有挑戰性的難題，QoS保障最關鍵的一部分就是準入控制（Admission Control，AC）。AC的主要工作機制是負責對用戶的請求進行準許判決，決定是否允許系統為用戶提供相應請求服務的無線資源管理（Radio Resource Management，RRM）功能實體[1]。它能夠有效緩解網絡擁塞，保障和提高網絡服務質量。

本文提出一種準確估測多跳無線自組織網絡的可用帶寬的方法，并基于帶寬策略進行準入控制，從而進一步保障和提高網絡服務質量。可用帶寬是非常重要的網絡參數之一，它可以定義為在不降低網絡中其他業務流傳輸速率的情況下，鏈路所能提供的最大傳輸速率。傳統的有線網絡可用帶寬測量方法主要有兩類：一類是探測包間隔模型（PGM），如Spruce[2]、IGI[3]等；一類是基于探測包速率模型（PGM），如TOPP[4]、Pathchirp[5]等。然而由于無線網絡共享信道會導致節點之間競爭資源，同時在信道接入過程中，需要多次握手，用于帶寬測量的探測包將與網絡中傳輸業務的數據包相互碰撞，觸發重傳甚至導致數據包丟失等原因，導致用于估測有線網絡的可用帶寬方法無法用于無線網絡。另外，在研究測量無線網絡可用帶寬的方法時，需要綜合考慮各種因素對可用帶寬的消耗，例如：因節點同時發送數據時發生碰撞、隱藏節點的存在引起碰撞、碰撞后回避時間對帶寬的消耗以及收發節點忙閑同步等問題。顯然，相比于有線網絡，無線網絡可用帶寬的估測方法要復雜很多。目前，關于無線自組織網絡中多跳可用帶寬測量方法最為經典的是Cheikh Sarr和Claude Chaudet等提出的ABE算法[6]以及Haitao Zhao等提出的IAB算法[7]。本文提出的IIAB（Improved IAB）算法主要是對Haitao Zhao提出的IAB算法進行了改進，并將IIAB算法加載到AODV協議，實現了基于帶寬的接入控制技術。

1基本概念

1.1 傳輸距離和載波偵聽距離

這里分別用Rtx和Rcs表示傳輸距離和載波偵聽距離[8-9]。所謂傳輸距離Rtx是指在不存在其他無線節點干擾的情況下，一對無線節點能夠實現可靠通信的最遠距離，可以表示如下：

式中d0表示參考距離，P0表示在參考距離內接收到的信號強度，RXThresh為接收信號的閾值，α為路徑損耗因子，通常取α≥2。載波偵聽距離Rcs表示當一個節點在發送數據時，它能夠觸發其他節點進行載波偵聽監測的最遠距離，可以表示如下：

1.2 隱藏節點問題

為了研究方便，這里假設傳輸距離與載波偵聽距離相同。在圖1所示的簡單網絡拓撲結構中，兩個實線圓分別表示節點B和節點C的傳輸距離（載波偵聽距離），節點A位于節點B和節點C的傳輸距離之內，但是節點B和節點C不在彼此的傳輸距離之內。當節點B向節點A發送數據時，節點C無法偵聽到節點B在發送數據，因此節點C認為信道空閑。若此時節點C也向節點A發送數據，那么節點A處就會發生數據碰撞。因此這種由于存在隱藏節點引起的碰撞，稱為隱藏節點問題[10]。

圖1 隱藏節點網路拓撲圖

1.3 收發同步問題

對于A、B兩個節點連接的鏈路而言，由于存在雙方載波偵聽范圍不一致的現象，可能導致雙方節點的忙閑時間段不一致。如圖2（a）所示，此時節點A和節點B信道的忙閑時隙一致，假設鏈路容量為C且忙閑持續時間相等，則A、B雙方從自己對信道的偵聽情況就可以估算鏈路的剩余帶寬，可以簡單地視為C/2；另一種極端情況，如圖2（b）所示，A、B偵聽信道的忙閑時隙完全互補，即當節點A偵聽到信道空閑的時候，節點B偵聽到信道為繁忙狀態，反之亦然。由于A、B雙方對信道狀態的判斷完全相反，所以即使B節點空閑的時候可以接受數據，而此時節點卻因為信道忙無法發送數據，顯然它們之間的剩余帶寬為0。上述情況即為收發同步問題。

圖2 （a）收發雙方對信道感受同步

圖2 （b）收發雙方對信道感受異步

2 改進IAB算法（Improved IAB，IIAB）

2.1 IIAB算法相關背景

當前，常用的帶寬測量方法通常是考察在一段監測時間T內，節點探測的空閑時間Tidle，將兩者的比值作為節點的空閑率，因此可以得出節點觀測得到的系統可用帶寬值為：

其中C為鏈路容量，AB為可用帶寬值。但是，在無線網絡情況下評測鏈路可用帶寬不可忽視以下兩個問題：（1）節點發生碰撞以及碰撞后退避時間對帶寬的消耗；（2）由收發雙方節點不同步導致忙閑時間不一致現象所帶來的估測可用帶寬的偏差。

其中，Haitao Zhao在文獻[7]中提出的IAB算法主要是針對問題（2）而對ABE算法進行了改進。IAB算法中，作者對節點評測信道忙作了更為細致的劃分，定義節點發送或接收數據時為BUSY狀態，定義節點偵聽信道是否空閑時為SENSE BUSY狀態，其他情況為IDLE狀態。通過嚴格區分這三種狀態來判斷收發節點是否同步。結果發現，若收發節點不在彼此的傳輸范圍內，則收發雙方發生不同步，即一方處于IDLE狀態，而另一方處于SENSE BUSY狀態。在計算可用帶寬時，IAB算法消除了該情況下對帶寬的消耗。但是，針對問題（1），IAB算法沒有做出相應改進，這顯然會降低估計可用帶寬的精度。當前對沖突概率的估計主要采用實時監測和數學模型相結合的方式[11]，但是很多都是僅僅通過路由層的hello消息包丟失的情況來表示節點數據包發送的沖突概率。這樣，顯然考慮得不夠全面，這是因為：（1）引進hello消息會增加網絡負擔；（2）沖突概率與包尺寸有關，一般來說，包尺寸越大其沖突概率也隨之增大。因此，據此推斷出來的沖突概率顯然有失偏頗。本文引進了一種新的計算節點發送數據時產生碰撞概率的方法，以便達到改進IAB算法的目的。

2.2 IIAB的模型分析與推導過程

2.2.1 碰撞概率計算方法

以節點A為研究對象，導致其發送至B處的沖突原因可能是：（1）在其傳播范圍之內的節點，于同一時刻發送數據；（2）隱藏節點在特定時間段發送數據。然而，在低負荷的網絡情況下，二進制退避機制可以有效地緩解因情況（1）而產生的沖突，吞吐量也不會明顯下降。但是，隱藏節點導致的沖突在非飽和情況下可能會嚴重影響網絡性能。為了更好地研究由于隱藏節點所產生的沖突概率，本模型采用的是非飽和狀態下的網絡，即節點不是始終保持數據發送狀態。

本文對模型作了幾個前提假設：（1）節點數據包產生服從參數為λ的泊松分布，并且以μ的概率發送它們；（2）網絡中的節點按照均勻分布固定在節點C的載波偵聽范圍內；（3）節點的載波偵聽范圍和傳輸范圍相同。如圖3所示，節點A和B是兩個隱藏節點，兩個實線圓圈分別是A和B的載波偵聽范圍或傳輸范圍，虛線圓圈表示節點C的載波偵聽范圍，HA為節點A的隱藏節點區域，即處于節點A偵聽范圍之外但卻在節點C的偵聽范圍之內的所有節點的集合。

圖3 網絡拓撲示意圖

在推導過程之前，假設節點C的載波偵聽范圍內所有的節點以λi的概率產生數據幀，以μi的概率傳輸數據幀，其中λi和μi滿足以下關系式：

節點A向節點C發送數據時由于隱藏節點產生沖突可以分為兩種情況：（1）A傳輸數據時，HA已經處于忙狀態，即A的隱藏區域內有節點在傳輸數據；（2）A傳輸數據之后，HA由閑狀態轉為忙狀態，即A的隱藏區域內的節點偵聽到信道空閑開始發送數據。分別用Pb|txA和Pib，A表示這兩種情況發生的概率。當第一種情況發生時，節點A向節點C傳輸數據時肯定會發生沖突；否則，節點A不可能與A的隱藏區域內節點在同一時間段內向節點C發送數據而產生沖突，只有在節點A向節點C發送數據時，節點A的隱藏區域的節點開始向節點C發送數據，即在發生第二種情況時節點A向節點C發送數據會產生沖突。

因此，節點A傳輸數據發生沖突的概率可以表示為：

根據前面對Pb|txA的定義，顯然它可以用下面表達式表示：

由于本文假設節點的分布是按照均勻分布的，所以式（7）計算出來的節點A的沖突概率也可以表示為節點B的沖突概率，即Pc，B=Pc，A。

2.2.2 IIAB算法可用帶寬理論方法

在計算給定收發節點的一條鏈路中的可用帶寬值時，需要綜合考慮節點發生碰撞、退避時間以及收發同步問題對可用帶寬的消耗，在此引進兩個修正系數K和α。

其中m與上述n的值相同，也表示為競爭窗口到達最大值的次數，即Wmax=2mW，Wmax為競爭窗口的最大值，W為競爭窗口的初始值。

系數α是用來消除收發同步問題對可用帶寬的消耗，在IAB算法中，它是通過嚴格區分收發節點的BUSY狀態和SENSE BUSY狀態獲得的，為了簡單起見，本文直接引用其方法，即在觀測時間內記錄收發節點處于SENSE BUSY狀態的時長，并將該時長與觀測時間T的比值作為信道處于偵聽狀態的比率，再用該比值乘以收發雙方發生不同步的概率，那么同步系數可以表示為：

綜上所述，計算可用帶寬的公式可以進一步修正為：

3 基于IIAB的準入控制分析

基于IIAB策略的接入控制是對按需平面距離矢量路由協議（Ad hoc On-demand Distance Vector Routing，AODV）的擴展。通過比較新的業務流所需帶寬與網絡中的剩余帶寬來判斷是否接入該業務流，并且在接入新的業務流后，是否會對網絡中原有的業務流產生較小的干擾[12]。

3.1 內部業務流干擾

利用第3章計算出來的可用帶寬值只是網絡中每個節點的可用帶寬值，但是，由于無線網絡共享信道的特點，當一個流經過多跳時，會在各個節點受到內部業務流的干擾，所以僅僅通過比較節點的可用帶寬來判斷是否接入該業務流是不夠的。關于該問題，文獻[13]是將計算出來的可用帶寬值除以競爭數（多跳鏈路上某個節點載波偵聽范圍內的節點個數）。

為了簡單起見，本文采用的方法是文獻[14]的方法，即利用端到端的吞吐量與路徑跳數的關系，將計算出來的可用帶寬值除以min（H，4），用H表示從源節點到收到RREQ的節點i的節點個數，公式表示如下：

這樣，在接入控制時，只需要檢查下式是否成立即可。

其中RB表示請求接入的業務流需求帶寬。

3.2 準入控制分析

接入控制以IIAB和AODV協議為基礎，可以分為路由請求階段和資源預留階段。

當有新的業務流接入時，源節點就會產生和廣播RREQ，同時開啟定時器，若源節點在一定時間內收到RREP應答包，則準許該業務流的接入，否則，拒絕該業務流的接入。本文重新定義RREQ消息格式，包括業務流的源節點IP地址、目的節點IP地址、數據包大小、發送速率、業務流需求帶寬信息（Request Bandwidth，RB），如圖4所示。當中間節點收到RREQ時，通過判斷式（9）是否成立，若成立則繼續轉發RREQ，若不成立，則丟棄該請求包。當目的節點收到第一個RREQ時，目的節點產生RREP應答包，并且單播回送該應答包。在回送應答包RREQ的途中，路徑上每個節點根據RB的值為該業務流進行帶寬預留。一旦源節點在沒有超時的情況下收到RREP應答包，該業務流便可以發送數據，否則拒絕該業務流。

圖4 RREQ消息數據格式

4 仿真實現與結果分析

本文采用的仿真平臺是網絡仿真器NS2[15]，在NS2上比較了IIAB算法與IAB算法的性能以及實現了基于AODV協議和基于IIAB-AODV協議準入控制的性能比較與分析。

4.1 IIAB算法與IAB算法性能分析與比較

仿真場景如圖3所示：將節點c的坐標設置為（0，0），然后選擇節點c周圍的8個節點作為背景節點源-目節點對，共組成4對業務流傳輸數據，將節點c為研究對象，首先統計其真實可用帶寬，然后分別統計采用IIAB算法和IAB算法得到的可用帶寬值。流量產生器設置為Application/Traffic/Pareto，數據包大小為512 Byte。每個節點的載波偵聽半徑為550 m，物理帶寬為2 Mb/s，仿真時間為50 s。4對背景業務流流量如表1所示。

圖5顯示了采用IAB算法和IIAB算法與真實帶寬的比較。顯然，采用IAB算法高估了節點c可用帶寬，而利用IIAB算法估測的可用帶寬與真實可用帶寬值接近，進而提高了可用帶寬的精度。

圖5 節點c的可用帶寬

表1 背景業務流流量

4.2 基于AODV協議和基于IIAB-AODV協議準入控制性能比較與分析

首先在較簡單的環境下進行驗證。仿真參數設置如下：12個移動節點按照圖3分布在700 m×500 m的范圍內，它們的坐標為（0，0）、（250，125）、（250，375）、（500，0）、（0，250）、（0，500）、（500，250）、（750，125），其他14個節點按照圖3的網絡拓撲示意圖均勻地分布在其他三個象限。隨機選擇兩個節點作為源-目的節點對，共組成6對業務流傳輸數據，其他參數的設置與上述相同。6個業務流的詳細信息如表2所示。

表2 流量設置

圖6和圖7分別給出了基于AODV協議和IIABAODV協議各個業務流的吞吐量。結果表明，由于普通的AODV協議沒有考慮帶寬接入策略，盲目接入所有的業務流，會導致新的業務流接入網絡時對原有的業務流產生較大的干擾。例如，業務流1在5 s的時候開始接入，而在25 s之前吞吐量還是相對比較穩定，業務流2、3、4接入對其沒有產生影響。但是，在25 s的時候，由于業務流5開始接入，業務流1的吞吐量開始大幅下降并且波動幅度較大。同樣，業務流2、3、4的吞吐量也在25 s之后變得很不穩定。當把IIAB加載到AODV協議的時候，出現了圖7的結果，即只有業務流1、2、3、4、6可以接入網絡，業務流5由于不滿足接入條件而被拒絕接入，此時網絡中各個業務流吞吐量得到了很好的保證。

圖6 基于AODV協議各流的吞吐量

圖7 基于IIAB-AODV協議各流的吞吐量

接下來本文在相對一般的場景下進行了驗證。場景設置如下：50個節點均勻的分布在1 300 m×1 100 m范圍內，隨機選擇10對節點進行業務流的傳輸，每個業務流的流量產生器設置為Application/Traffic/Pareto。且10個業務流每隔10 s傳輸數據，仿真時間為120 s，數據包大小為1 024 Byte。其他參數與簡單環境下的參數相同。圖8和圖9顯示了采用基于AODV協議的準入控制和采用IIAB-AODV協議的準入控制的網絡吞吐量和延遲時間的對比。從結果可以看出，采用基于IIAB-AODV協議的準入控制，網絡的吞吐量和延遲都好于普通的AODV協議準入控制，從而有利地證明了基于帶寬策略的準入控制可以有效地保障和提高網絡服務質量。

圖8 網絡吞吐量變化圖

圖9 網絡延遲時間變化圖

5 結論

在充分研究IAB算法的基礎上，通過利用泊松分布流量產生器的產生數據包的概率和發送數據包的概率，計算隱藏終端引起的沖突概率，進而消除因收發同步問題對帶寬的消耗，提出了新的估測可用帶寬的方法IIAB，并將該方法應用到AODV協議，設計出新的準入控制機制。仿真表明：新的準入控制機制提高了網絡的穩定性以及吞吐量，降低了延遲時間，可以有效地保障和提高網絡服務質量。下一步工作是研究將IIAB算法應用到其他協議如DSR協議來提高網絡的性能。

[1]梁如冰，夏強.無線接入控制關鍵技術研究進展綜述[J].計算機測量與控制，2011，19（2）：246-249.

[2]Strauss J，Katabi D，Kaashoek F.A measurement study of available bandwidth estimation tools[C]//Proc ACM Internet Measurement Conference（IMC），2003：39-44.

[3]Hu Ningning，Steenkiste P.Evaluation and characterization of available bandwidth probing techniques[J].IEEE Journal on Selected Areas in Communications，2003，21（6）：879-894.

[4]Melander B，Bjorkman M，Gunningberg P.A new end to end probing and analysis method for estimating bandwidth bottlenecks[C]//Proc Global Internet Symposium，2000：415-420.

[5]Ribeiro V，Riedi R，Baraniuk R，et al.PathChirp：efficient availablebandwidthestimationfornetworkpaths[C]// Workshop on Passive and Active Measurement（PAM），2003.

[6]SarrC，ChaudetC.BandwidthestimationforIEEE 802.11-based ad hoc networks[J].IEEE Transactions on Mobile Computing，2008，7（10）：1228-1241.

[7]Zhao Haitao，Garcia-Palaciso E，Wei Jibo.Accurate available bandwidth estimation in IEEE802.11-based ad hoc networks[J].Computer Communications，2009，32：1050-1057.

[8]Zhai H，Wang J，Fang Y.A new dual-channel MAC protocolformultihopadhocnetworks[J].IEEETransactions on Wireless Communication，2006，5（11）：3224-3233.

[9]Li J，Blake C，Couto D S J D.Capacity of ad hoc wireless[C]//Proc ACM MobiCom，2001.

[10]宿景芳，武穆清，徐春秀.無線多跳Ad Hoc網絡最佳吞吐量分析[J].北京郵電大學學報，2011，34（3）：127-131.

[11]Jacquet P，Naimi A M，Rodolakis G.Asymptotic delay analysis for cross-layer delay-based routing in ad hoc networks[J].Advances in Multimedia，2007，4：1-11.

[12]劉春芳，張連芳.無線自組網絡QoS流的準入控制和流量控制[J].計算機工程與應用，2008，44（25）：88-91.

[13]Sanzgiri K，Chakeres I D，Belding-Royer E M.Determining intra-flow contention along multihop paths in wirelessnetworks[C]//1stInternationalConferenceon Broadband Networks，2004：611-620.

[14]Chen L，Heinzelman W.QoS-aware routing based on bandwidth estimation for mobile ad hoc networks[J]. IEEE Journal on Selected Areas in Communications，2005，23（3）.

[15]Yang Y，Kravets R.Throughput guarantees for multi-priority traffic in ad hoc networks[J].Ad Hoc Networks，2007，5（2）：228-253.

HU Taoying1,CHENG Yun’an1,GUAN Junming2，3

1.School of Computer&Information,Hefei University of Technology,Hefei 230009,China
2.GOCOM Information&Technology Co.,Ltd,Hefei 230088,China
3.School of Information Engineering,Huangshan University,Huangshan,Anhui 245400,China

Available bandwidth is an important parameter of wireless ad hoc networks for guaranteeing QoS.Many approaches for estimating the available bandwidth of wireless networks are presented by many scholars,but no mechanism has been standardized because of many factors affecting the available bandwidth of wireless networks.The proposed approach called IIAB eliminates the consumption for available bandwidth through calculating the probability of conflict caused by hidden nodes.It establishes the IIAB model and uses the result to analyze the admission control and proposes a new IIAB-AODV protocol eventually.Through the simulation results,it is demonstrated that the model proposed in this paper can improve the accuracy of the estimation of the available bandwidth and the IIAB-AODV protocol can guarantee and improve the quality of the service of the network effectively.

wireless ad hoc networks;available bandwidth estimation;admission control;Ad hoc On-demand Distance Vector routing（AODV）protocol;quality of service

A

TP393.0

10.3778/j.issn.1002-8331.1211-0168

HU Taoying,CHENG Yun’an,GUAN Junming.Admission control based on bandwidth policy for ad hoc networks. Computer Engineering and Applications,2014,50（21）：85-90.

安徽省博士后基金（財教[2012]593號）；安徽省科技攻關計劃（科計[2010]200號/11010201011）；安徽省高校優秀青年人才基金項目（No.2009SQRZ167）；安徽省高校省級自然科學研究項目（No.KJ2009B114）。

胡桃英（1987—），女，碩士研究生，主研方向為無線網絡準入控制；程運安（1968—），男，研究員，主研方向為計算機應用；官駿鳴（1979—），男，副教授，主研方向為無線自組織網MAC、網絡層協議研究。E-mail：695542201@qq.com

2012-11-14

2013-01-14

1002-8331（2014）21-0085-06

CNKI出版日期：2013-01-29,http://www.cnki.net/kcms/detail/11.2127.TP.20130129.1539.012.html