ＡＤ ｈｏｃ網絡中的機會分組調度算法

摘要：無線多跳Ad hoc網絡中節點在業務發送過程中需要競爭共享信道，容易發生局部擁塞導致網絡性能下降，而且節點內部采用的先入先出(FIFO)隊列容易使隊頭阻塞，影響隊列中后續分組的發送。本文提出了一種機會分組調度算法CBOS，發送節點采用多播RTS的方式同時指向多個接收節點，可以支持可變長分組，提高了Ad hoc網絡的空間重用率，接收節點根據擁塞程度按照一定概率返回CTS，有利于節點網絡的擁塞控制。仿真結果表明，該算法提高了網絡端到端的飽和吞吐量和信道利用率，并提高了業務流之間的公平性。

關鍵詞：移動自組網；機會分組調度；擁塞控制；公平性

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)28-0113-04

Opportunistic Packet Scheduling Algorithms in AD Hoc Networks

HE Jun1，2，GUO Miao2

(1 Computer Science Technology Department，East China Normal University，Shanghai 200241，China;2.Urumqi Railway Transportation School，Urumqi 830011，China)

Abstract:The nodes in wireless multi-hop Ad hoc networks need to compete for communication channel when operations are sent out. During this process，the capability of network may descend due to part congestion. Furthermore，the \"First in First out\" queuing in node system leads to anterior barrage， which will effect the transmission of continued queuing. This paper proposes an opportunistic packet scheduling algorithm CBOS.The sender sends multicast RTS frame targeting serval receivers simultaneously and the receivers respond CTS according to a probability based on congestion level.It improves the spatial reuse ratio of Ad hoc networks and helps to the congestion control. As emulational result indicates，this scheduling algorithm improves end-end saturation throughput and using rate in network，and increases the fairness between operations.

Key words:Ad hoc networks;Opportunistic packet scheduling;congestion control;fairness

1 引言

在Ad hoc網絡中，如何充分利用有限的無線信道資源一直是人們重點研究的問題之一。MAC層空間復用技術主要研究MAC層包調度策略，本文主要研究基于包調度的MAC層的空間復用技術，在描述了Ad hoc網絡中隊頭阻塞(HOL)問題和擁塞問題之后，提出了一種基于擁塞的機會調度機制CBOS，改進了原有的RTS-CTS握手過程，同時可以防止由于鄰居節點移動到其傳輸范圍之外造成的隊頭阻塞問題。

2 問題描述

2.1 隊頭阻塞問題

在Ad hoc網絡中很容易出現隱藏終端和暴露終端問題[1]。圖1和2分別示出了隱藏接收端問題和暴露接收終端問題。圖1中，節點D內分別有向節點C和節點E送的分組。節點C為隱藏接收終端，如果節點D內的隊列頭部分組為發往C分組，那么D向C發送RTS幀之后，由于節點C是隱藏節點，不能發送任何信息，因此節點D將得不到節點C回應的CTS，D將超時重發RTS。圖2中，如果節點D要向暴露終端C發送分組，則來自節點D的RTS會與來自節點B數據分組在節點C處發生碰撞，導致節點C收不到來自節點D的RTS，節點收不到來自節點`C的CTS，就超時重發RTS。

■

圖1 隱藏接收終端引起的隊頭阻塞問題圖2 暴露接收終端引起的隊頭阻塞問題

圖3中，節點C處于節點A和節點B的通信范圍之內，因此在節點A與B通信期間，節點C被“凍結”而保持靜默。此時如果節點D向C發送RTS，將得不到節點C的CTS回應，因此節點D也將超時重發。

當節點處于以上幾種情況時，稱節點處于“阻塞狀態”，在Ad hoc網絡中經常發生，會造成無謂的重發，浪費無線資源。當出現緩沖隊列頭部數據阻塞時，并不代表頭部后面的其他分組也會阻塞。在出現阻塞時，如果節點D能選擇不同的節點(如節點E)發送或轉發數據，就可能會獲得成功，從而提高無線信道的空間利用率。這種因為隊列頭部分組阻塞導致網絡性能降低的現象與有線網絡中路由器或交換機內部隊列調度時的隊頭阻塞問題[2]類似，但是傳統的IEEE802.11協議不能解決隊頭阻塞問題。

2.2 擁塞問題

在多跳Ad hoc網絡中，由于在MAC層普遍存在流內競爭和流間競爭[3]，所以很容易導致擁塞[4-5]。擁塞會導致競爭惡化，嚴重影響網絡的整體性能。對于使用共享信道的Ad hoc網絡來說，如果在節點發生擁塞時繼續向其發送分組，那么分組將會被擁塞節點丟棄，有限的帶寬資源被浪費。

在Ad hoc網絡中，節點既是普通節點，又可以作為路由器，因此節點內部可能會有發往不同節點的分組。我們假設節點能夠同時向多個節點發送數據發送請求，那么最終選擇不擁塞的節點發送數據將有利于提高網絡的帶寬利用率。這樣就要求接收節點能夠進行接入控制，在達到一定的條件時可以拒絕發送節點的請求。

3 基于擁塞的機會分組調度算法

3.1 算法思路

Ad hoc網絡中的調度算法分為節點內部調度算法和全網調度算法，全網調度算法需要考慮網絡的拓撲結構及相關信息[6]，是一個很復雜的過程，本文僅考慮節點內部調度算法，而且只考慮節點內單播數據分組的調度。

在基于IEEE802.11的Ad hoc網絡中，發送節點為了選擇合適的下一跳節點進行分組轉發，需要根據鄰居節點的相關信息進行調度，這些信息可以包括信道質量、擁塞程度、信道利用率等。在RTS-CTS握手過程中可以獲取相關信息，但是一次只能獲取一個鄰居節點的信息，如果要獲取多個節點的信息就需要多次探測，這樣一方面增加了控制開銷，另一方面也使得探測的時間拉長，信息的時效性變差。為了能夠一次獲取多個節點的相關信息，我們采用了發送節點與接收節點互相配合的方式，使發送節點發送的RTS對多個下一跳節點有效，這些節點在正確解析RTS幀后根據自身的擁塞程度按照一定的概率返回CTS，如果第一個節點由于擁塞無法發送CTS，那么開始考慮下一個預備節點，依此類推。這種回復CTS的優先級順序在RTS幀中定義，滿足條件的優先級最高的節點將獲得信道的使用權。由此“機會”是指同時滿足能夠正確解析RTS和能夠回復CTS的擁塞條件。

為了在調度的時候保證一定的公平性，我們采用了簡單的輪詢調度算法確定包含在RTS幀中的目標下一跳節點的優先級順序。

3.2 算法過程

為了選擇合適的下一跳節點轉發DATA幀，我們改進了發送DATA幀之前的RTS-CTS握手過程，采用了多播RTS方式，使得多個節點能同時成為目標節點。圖4顯示了多播RTS(MRTS)的格式，其中{RA(l)，RA(2)……RA(N)}表示N個不同的目的節點，Duration(1)至Duration(n)分別表示根據N個目的節點各自對應的隊頭分組計算出的預留時間。

■

圖4 多播RTS格式(MRTS)

在此我們將節點擁塞程度分成三個等級：無擁塞、輕度擁塞和嚴重擁塞，采用節點的瞬時隊列長度L作為判斷擁塞的標準。設置兩個控制閾值Lmin和Lmax，當L≤Lmin時，判斷節點無擁塞；當L≥Lmax時，節點發生嚴重擁塞；而當Lmin＜L＜Lmax時，節點發生輕度擁塞。在獲取隊列擁塞程度之后，接收節點將按照一定的概率回應CTS幀，概率根據擁塞程度確定，如下：

■(1)

假設每個接收節點能夠成功接收分組的概率是相同的并且獨立，設為p，那么對于CBOS來說，接收節點都不擁塞時一次握手成功概率為P=1-(1-p)N，當p為50%時，對于N分別為2、3和4，P就能分別達到75%、87.5%和93.75%。握手成功概率高對于減小信令消耗時間有重要的作用。

CBOS的工作過程時序圖如圖5所示，其中發送節點向N個接收節點發送MRTS幀，最終由接收節點k返回CTS幀。節點A在發送節點的傳輸范圍內而不在接收節點k的傳輸范圍內，節點B在接收節點k的傳輸范圍內而不在發送節點的傳輸范圍內。

在這種握手過程中，接收節點在能夠正確解析RTS幀之后才按照概率回復CTS，因此如果節點處于阻塞狀態，導致無法回應，那么其他的節點仍有機會回復CTS，這樣就可以防止出現隊頭阻塞問題。

3.3 調度框架

圖6顯示了節點內部的調度算法框架，圖中MAC部分包含了上面所述的改進的RTS-CTS握手過程。在節點中為每個下一跳節點維護一個隊列，調度器負責根據調度信息調度這些隊列。調度信息收集模塊主要用于維護調度信息，這些信息包括隊列調度情況及MAC層反饋信息(哪個節點回復了CTS幀)等。

為了保證調度算法一定的公平性，我們使用了簡單的輪詢調度算法，為此我們定義了一種簡單的數據結構用以維護調度信息，如圖7所示，將所有的節點信息存為一個環形隊列，并設置一個頭指針。發送節點中調度算法的工作過程為：

1) 從頭指針開始依次向后選擇N個節點作為多播RTS的目標節點，優先級順序為離頭指針越近的節點優先級越高；

2) 根據收到CTS的時間判斷是哪個節點回復的CTS，并據此將頭指針移動到該節點之后；

3) 下一次調度按照新的頭指針位置繼續執行步驟1)。

可以看出，由于擁塞或其他原因導致高優先級的節點無法回復CTS時，調度算法將這些節點放到調度順序后面的位置，這樣可以給它們一定的時間擺脫這種狀態。這種簡單的輪詢調度算法可以保證基本的公平性。

4 仿真結果與分析

通過仿真研究CBOS機會調度算法的性能，使用的仿真工具是Glomosim[7]。物理層采用DSSS，無線鏈路帶寬為2Mbps。節點中隊列長度均設為50，隊列閾值Lmin為15，Lmax為40，多播RTS中的目標節點數量N取值4。仿真場景如圖8所示，有8個業務流，分別為0→5→9、2→5→9、1→6→10、2→6→10、3→7→11、2→7→l1、4→8→l2和2→8→12，業務類型選用CBR業務，分組大小為512Bytes。節點2的分組需要向路由節點5、6、7和8發送，而這些節點很可能發生擁塞。我們不考慮路由協議對調度算法的影響，因此各節點之間采用靜態路由，沒有路由協議開銷，仿真時間為60秒。

圖9顯示了不同網絡負載下兩種算法的端到端吞吐量，我們通過改變每個業務流速率來模擬不同的網絡負載。可以看出，使用CBOS調度算法網絡的端到端飽和吞吐量要比DCF協議的增長近20%，這主要是由于CBOS調度算法減少了由于分組被擁塞節點丟棄造成的無線帶寬浪費，提高了無線信道的利用率。

圖10顯示了節點2的4條業務流的公平性指數。從圖中可以看出，使用DCF協議時在網絡負載大時這幾條業務流的公平性很差，甚至出現餓死現象，原因是使用FIFO隊列時，由于隊列中的分組不能及時發送出去，導致大量分組被丟棄，而由于分組進入隊列的隨機性，使得到某一個節點的分組可能會被連續丟棄；而CBOS算法中由于采用了多個隊列循環調度，使得到每個下一跳節點的分組都有可能被調度，而且由于使用了多播RTS，增大了握手過程的一次成功率，減小了分組重傳次數，使得各個業務流的公平性得到很大提高。

■

圖9端到端吞吐量圖10 公平性指數

5 小結

Ad hoc網絡由于節點MAC層對共享信道的競爭，很容易導致局部節點擁塞，丟棄的分組無謂的浪費了有限帶寬資源，而且在節點內部使用的先入先出的隊列方式很容易產生隊頭阻塞問題。在Ad hoc網絡中，節點可能作為路由器需要向多個鄰居節點轉發分組，為了減小分組轉發后再被丟棄造成的帶寬浪費，提高無線帶寬的利用率，本文提出了基于擁塞的機會調度算法CBOS。該算法中改進了DCF協議的RTS-CTS握手過程，發送節點使用簡單的輪詢調度算法選擇多個下一跳節點作為目標節點發送多播RTS幀，這些節點在正確解碼RTS后檢查自己的擁塞狀態并據此按照一定的概率回復CTS幀。多播RTS方式還能夠防止由于目標節點無法回復CTS幀導致的隊頭阻塞問題，而按概率回復CTS的方式相當于在節點中加入了接入控制機制，有利于控制節點的擁塞。仿真結果顯示，CBOS調度算法提高了系統的端到端吞吐量和帶寬利用率，并提高了多個業務流間的公平性。CBOS機會調度算法還需要進一步的完善和研究，包括進一步的仿真研究、與功率控制的結合等等。

參考文獻：

[1] Tobagi F A，Kleinrock L.Packet switching in radio channels: Part Ⅱ-the hidden terminal problem in carrier sense multiple-access modes and the busy-tone solution.IEEE Transaction on Communications，1975，23(12):1417-1433.

[2] McKeown N.Scheduling algorithms for input-qucued cell switchs[D].Ph D Thesis， University of California at Berkeley，1995.

[3] Zhai H，Wang J，Fang Y.Distributed packet scheduling for multihop flows in Ad hoc networks[C]. Proceedings of IEEE WCNC’2004，March，2004:1081-1086.

[4] Chen L，Low S，Doyle J.Joint congestion control and media access control design for ad hoc wireless networks[J]. IEEE INFOCOM， 2005(3):2212-2222.

[5] Wang X，Kar K.Cross-layer rate control for end-to-end proportional fairness in wireless networks with random access[C].ACM Mobihoc，2005:157-168.

[6] Luo Haiyun，Lu Songwu，Bharghavan V.A New Model for Packet Scheduling in Multihop Wireless Networks. Proceedings of the Annual International Conference on Mobile Computing and Networking，MOBICOM， 2000:76-86.

[7] Takai M，Bajaj L，Ahuja R，Bagrodia R，Gerla M.GloMoSim: A Scalable Network Simulation Environment[R].Technical Report 990027，UCLA， Computer Science Department，1999.