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

關(guān)鍵詞：移動自組網(wǎng)；機(jī)會分組調(diào)度；擁塞控制；公平性

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：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網(wǎng)絡(luò)中，如何充分利用有限的無線信道資源一直是人們重點(diǎn)研究的問題之一。MAC層空間復(fù)用技術(shù)主要研究MAC層包調(diào)度策略，本文主要研究基于包調(diào)度的MAC層的空間復(fù)用技術(shù)，在描述了Ad hoc網(wǎng)絡(luò)中隊(duì)頭阻塞(HOL)問題和擁塞問題之后，提出了一種基于擁塞的機(jī)會調(diào)度機(jī)制CBOS，改進(jìn)了原有的RTS-CTS握手過程，同時(shí)可以防止由于鄰居節(jié)點(diǎn)移動到其傳輸范圍之外造成的隊(duì)頭阻塞問題。

2 問題描述

2.1 隊(duì)頭阻塞問題

在Ad hoc網(wǎng)絡(luò)中很容易出現(xiàn)隱藏終端和暴露終端問題[1]。圖1和2分別示出了隱藏接收端問題和暴露接收終端問題。圖1中，節(jié)點(diǎn)D內(nèi)分別有向節(jié)點(diǎn)C和節(jié)點(diǎn)E送的分組。節(jié)點(diǎn)C為隱藏接收終端，如果節(jié)點(diǎn)D內(nèi)的隊(duì)列頭部分組為發(fā)往C分組，那么D向C發(fā)送RTS幀之后，由于節(jié)點(diǎn)C是隱藏節(jié)點(diǎn)，不能發(fā)送任何信息，因此節(jié)點(diǎn)D將得不到節(jié)點(diǎn)C回應(yīng)的CTS，D將超時(shí)重發(fā)RTS。圖2中，如果節(jié)點(diǎn)D要向暴露終端C發(fā)送分組，則來自節(jié)點(diǎn)D的RTS會與來自節(jié)點(diǎn)B數(shù)據(jù)分組在節(jié)點(diǎn)C處發(fā)生碰撞，導(dǎo)致節(jié)點(diǎn)C收不到來自節(jié)點(diǎn)D的RTS，節(jié)點(diǎn)收不到來自節(jié)點(diǎn)`C的CTS，就超時(shí)重發(fā)RTS。

■

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

圖3中，節(jié)點(diǎn)C處于節(jié)點(diǎn)A和節(jié)點(diǎn)B的通信范圍之內(nèi)，因此在節(jié)點(diǎn)A與B通信期間，節(jié)點(diǎn)C被“凍結(jié)”而保持靜默。此時(shí)如果節(jié)點(diǎn)D向C發(fā)送RTS，將得不到節(jié)點(diǎn)C的CTS回應(yīng)，因此節(jié)點(diǎn)D也將超時(shí)重發(fā)。

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

2.2 擁塞問題

在多跳Ad hoc網(wǎng)絡(luò)中，由于在MAC層普遍存在流內(nèi)競爭和流間競爭[3]，所以很容易導(dǎo)致?lián)砣鸞4-5]。擁塞會導(dǎo)致競爭惡化，嚴(yán)重影響網(wǎng)絡(luò)的整體性能。對于使用共享信道的Ad hoc網(wǎng)絡(luò)來說，如果在節(jié)點(diǎn)發(fā)生擁塞時(shí)繼續(xù)向其發(fā)送分組，那么分組將會被擁塞節(jié)點(diǎn)丟棄，有限的帶寬資源被浪費(fèi)。

在Ad hoc網(wǎng)絡(luò)中，節(jié)點(diǎn)既是普通節(jié)點(diǎn)，又可以作為路由器，因此節(jié)點(diǎn)內(nèi)部可能會有發(fā)往不同節(jié)點(diǎn)的分組。我們假設(shè)節(jié)點(diǎn)能夠同時(shí)向多個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)發(fā)送請求，那么最終選擇不擁塞的節(jié)點(diǎn)發(fā)送數(shù)據(jù)將有利于提高網(wǎng)絡(luò)的帶寬利用率。這樣就要求接收節(jié)點(diǎn)能夠進(jìn)行接入控制，在達(dá)到一定的條件時(shí)可以拒絕發(fā)送節(jié)點(diǎn)的請求。

3 基于擁塞的機(jī)會分組調(diào)度算法

3.1 算法思路

Ad hoc網(wǎng)絡(luò)中的調(diào)度算法分為節(jié)點(diǎn)內(nèi)部調(diào)度算法和全網(wǎng)調(diào)度算法，全網(wǎng)調(diào)度算法需要考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)及相關(guān)信息[6]，是一個(gè)很復(fù)雜的過程，本文僅考慮節(jié)點(diǎn)內(nèi)部調(diào)度算法，而且只考慮節(jié)點(diǎn)內(nèi)單播數(shù)據(jù)分組的調(diào)度。

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

為了在調(diào)度的時(shí)候保證一定的公平性，我們采用了簡單的輪詢調(diào)度算法確定包含在RTS幀中的目標(biāo)下一跳節(jié)點(diǎn)的優(yōu)先級順序。

3.2 算法過程

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

■

圖4 多播RTS格式(MRTS)

在此我們將節(jié)點(diǎn)擁塞程度分成三個(gè)等級：無擁塞、輕度擁塞和嚴(yán)重?fù)砣?，采用?jié)點(diǎn)的瞬時(shí)隊(duì)列長度L作為判斷擁塞的標(biāo)準(zhǔn)。設(shè)置兩個(gè)控制閾值Lmin和Lmax，當(dāng)L≤Lmin時(shí)，判斷節(jié)點(diǎn)無擁塞；當(dāng)L≥Lmax時(shí)，節(jié)點(diǎn)發(fā)生嚴(yán)重?fù)砣?；而?dāng)Lmin＜L＜Lmax時(shí)，節(jié)點(diǎn)發(fā)生輕度擁塞。在獲取隊(duì)列擁塞程度之后，接收節(jié)點(diǎn)將按照一定的概率回應(yīng)CTS幀，概率根據(jù)擁塞程度確定，如下：

■(1)

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

CBOS的工作過程時(shí)序圖如圖5所示，其中發(fā)送節(jié)點(diǎn)向N個(gè)接收節(jié)點(diǎn)發(fā)送MRTS幀，最終由接收節(jié)點(diǎn)k返回CTS幀。節(jié)點(diǎn)A在發(fā)送節(jié)點(diǎn)的傳輸范圍內(nèi)而不在接收節(jié)點(diǎn)k的傳輸范圍內(nèi)，節(jié)點(diǎn)B在接收節(jié)點(diǎn)k的傳輸范圍內(nèi)而不在發(fā)送節(jié)點(diǎn)的傳輸范圍內(nèi)。

在這種握手過程中，接收節(jié)點(diǎn)在能夠正確解析RTS幀之后才按照概率回復(fù)CTS，因此如果節(jié)點(diǎn)處于阻塞狀態(tài)，導(dǎo)致無法回應(yīng)，那么其他的節(jié)點(diǎn)仍有機(jī)會回復(fù)CTS，這樣就可以防止出現(xiàn)隊(duì)頭阻塞問題。

3.3 調(diào)度框架

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

為了保證調(diào)度算法一定的公平性，我們使用了簡單的輪詢調(diào)度算法，為此我們定義了一種簡單的數(shù)據(jù)結(jié)構(gòu)用以維護(hù)調(diào)度信息，如圖7所示，將所有的節(jié)點(diǎn)信息存為一個(gè)環(huán)形隊(duì)列，并設(shè)置一個(gè)頭指針。發(fā)送節(jié)點(diǎn)中調(diào)度算法的工作過程為：

1) 從頭指針開始依次向后選擇N個(gè)節(jié)點(diǎn)作為多播RTS的目標(biāo)節(jié)點(diǎn)，優(yōu)先級順序?yàn)殡x頭指針越近的節(jié)點(diǎn)優(yōu)先級越高；

2) 根據(jù)收到CTS的時(shí)間判斷是哪個(gè)節(jié)點(diǎn)回復(fù)的CTS，并據(jù)此將頭指針移動到該節(jié)點(diǎn)之后；

3) 下一次調(diào)度按照新的頭指針位置繼續(xù)執(zhí)行步驟1)。

可以看出，由于擁塞或其他原因?qū)е赂邇?yōu)先級的節(jié)點(diǎn)無法回復(fù)CTS時(shí)，調(diào)度算法將這些節(jié)點(diǎn)放到調(diào)度順序后面的位置，這樣可以給它們一定的時(shí)間擺脫這種狀態(tài)。這種簡單的輪詢調(diào)度算法可以保證基本的公平性。

4 仿真結(jié)果與分析

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

圖9顯示了不同網(wǎng)絡(luò)負(fù)載下兩種算法的端到端吞吐量，我們通過改變每個(gè)業(yè)務(wù)流速率來模擬不同的網(wǎng)絡(luò)負(fù)載?？梢钥闯?，使用CBOS調(diào)度算法網(wǎng)絡(luò)的端到端飽和吞吐量要比DCF協(xié)議的增長近20%，這主要是由于CBOS調(diào)度算法減少了由于分組被擁塞節(jié)點(diǎn)丟棄造成的無線帶寬浪費(fèi)，提高了無線信道的利用率。

圖10顯示了節(jié)點(diǎn)2的4條業(yè)務(wù)流的公平性指數(shù)。從圖中可以看出，使用DCF協(xié)議時(shí)在網(wǎng)絡(luò)負(fù)載大時(shí)這幾條業(yè)務(wù)流的公平性很差，甚至出現(xiàn)餓死現(xiàn)象，原因是使用FIFO隊(duì)列時(shí)，由于隊(duì)列中的分組不能及時(shí)發(fā)送出去，導(dǎo)致大量分組被丟棄，而由于分組進(jìn)入隊(duì)列的隨機(jī)性，使得到某一個(gè)節(jié)點(diǎn)的分組可能會被連續(xù)丟棄；而CBOS算法中由于采用了多個(gè)隊(duì)列循環(huán)調(diào)度，使得到每個(gè)下一跳節(jié)點(diǎn)的分組都有可能被調(diào)度，而且由于使用了多播RTS，增大了握手過程的一次成功率，減小了分組重傳次數(shù)，使得各個(gè)業(yè)務(wù)流的公平性得到很大提高。

■

圖9端到端吞吐量圖10 公平性指數(shù)

5 小結(jié)

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

參考文獻(xiàn)：

[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，F(xiàn)ang 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.