沙　巖

[摘要]為了實(shí)現(xiàn)藍(lán)牙網(wǎng)絡(luò)在主從節(jié)點(diǎn)間建立兩種通信鏈路類型來支持同步通信量或者面向數(shù)據(jù)的異步通信量，提出藍(lán)牙網(wǎng)絡(luò)的媒介接入控制（MAC），在此基礎(chǔ)上，再提出一種優(yōu)化的支持QoS的差分調(diào)度算法。

[關(guān)鍵詞]藍(lán)牙 QoS 差分調(diào)度算法 媒介接入控制

中圖分類號：TP2文獻(xiàn)標(biāo)識碼：A文章編號：1671－7597（2009）0220030－02

一、藍(lán)牙網(wǎng)絡(luò)通信面臨的要求

目前，藍(lán)牙網(wǎng)絡(luò)的接入兼容性高低引起了業(yè)內(nèi)人士的注意，由于早期藍(lán)牙技術(shù)是針對單跳無線通信開發(fā)的，在一些移動設(shè)備上經(jīng)常會遇到延遲和阻塞等問題，為了使其適合在多跳移動網(wǎng)絡(luò)中使用，服務(wù)質(zhì)量(QoS，Quality of Service)技術(shù)被開發(fā)出來，可對藍(lán)牙協(xié)議本身進(jìn)行改進(jìn)，同時考慮將現(xiàn)有協(xié)議中的一些理想化的限制條件弱化，提高協(xié)議的適用性。藍(lán)牙協(xié)議標(biāo)準(zhǔn)中的現(xiàn)有協(xié)議規(guī)范大部分都限于靜態(tài)環(huán)境，沒有考慮節(jié)點(diǎn)的移動性，如何在節(jié)點(diǎn)移動、加入、撤出等情況下，保證散射網(wǎng)的有效性，當(dāng)節(jié)點(diǎn)移動速度比較大時，解決節(jié)點(diǎn)在不同接入點(diǎn)、基站之間的切換，保證業(yè)務(wù)流的服務(wù)質(zhì)量也就成為一個必須考慮的問題。本文針對藍(lán)牙媒介接入控制過程和輪詢方式的調(diào)度機(jī)制，改進(jìn)了Diff-KFP算法，通過優(yōu)化其參數(shù)來提高整個網(wǎng)絡(luò)的吞吐量以及QoS。

藍(lán)牙網(wǎng)絡(luò)中支持QoS保證所面臨的主要問題有以下四個方面。

1. 鏈路質(zhì)量預(yù)測困難：無線信號傳輸面臨著路徑損耗、多徑衰落和干擾等問題，由于節(jié)點(diǎn)的移動等因素的影響，周圍環(huán)境不斷變化導(dǎo)致預(yù)測鏈路質(zhì)量很困難。

2. 鏈路帶寬預(yù)測的困難：無限媒介的信道帶寬被周圍的節(jié)點(diǎn)共享，周圍節(jié)點(diǎn)的移動和這些節(jié)點(diǎn)業(yè)務(wù)量的變化是鏈路帶寬很難預(yù)測。

3. 分布式控制：由于信道使用權(quán)需要采用分布式獲得，這導(dǎo)致優(yōu)先級的保證和資源的預(yù)留都帶有一定的隨機(jī)性。

4. 網(wǎng)絡(luò)的動態(tài)性：分別是移動設(shè)備通常使用電池作為電源、節(jié)點(diǎn)的移動性、網(wǎng)絡(luò)業(yè)務(wù)流的動態(tài)與不可預(yù)測。

隨著藍(lán)牙技術(shù)的發(fā)展，QoS已經(jīng)成為通信系統(tǒng)必須支持的一項(xiàng)重要功能，已經(jīng)是藍(lán)牙網(wǎng)絡(luò)的發(fā)展瓶頸了。

二、現(xiàn)有的藍(lán)牙網(wǎng)絡(luò)通訊方案分析

截止目前，國際上提出的移動Ad-hoc網(wǎng)絡(luò)實(shí)現(xiàn)和解決方案為數(shù)不多，如美國MeshNetworks公司的解決方案，以及以色列Commil公司提出的藍(lán)牙Fixed to Mobile Convergence(FMC)方案。

MeshNetworks公司方案主要技術(shù)特點(diǎn)如下：

（1）支持網(wǎng)絡(luò)和客戶端組網(wǎng)（Meshing）：其Ad-hoc對等技術(shù)同時支持基礎(chǔ)設(shè)施的組網(wǎng)以及客戶端組網(wǎng)。使用Multi-Hopping TM路由技術(shù)可以將任何一個客戶設(shè)備轉(zhuǎn)變?yōu)橐粋€路由器或重復(fù)器，從而改善了網(wǎng)絡(luò)覆蓋范圍，增加網(wǎng)絡(luò)的吞吐量。

（2）支持端到端的IP：由于所有的路由都是在IP層之下，各種網(wǎng)絡(luò)設(shè)備無需更改。

（3）網(wǎng)狀結(jié)構(gòu)的頻譜復(fù)用和網(wǎng)絡(luò)吞吐量最大化：無論采用何種無線網(wǎng)絡(luò)技術(shù)，在網(wǎng)絡(luò)中所有節(jié)點(diǎn)都能彼此識別并間接或直接通信。避免了集中式結(jié)構(gòu)中的瓶頸問題。網(wǎng)絡(luò)中的節(jié)點(diǎn)通過彼此合作來充分利用頻譜資源，避免過度競爭。

在FMC方案中，做了兩個重要的應(yīng)用擴(kuò)展：

（1）網(wǎng)絡(luò)用戶終端類型的擴(kuò)展。將藍(lán)牙“三合一”手機(jī)應(yīng)用的終端設(shè)備擴(kuò)展為所有采用其CellarionTM技術(shù)所生產(chǎn)的移動設(shè)備，使得原來所局限于語音通信的應(yīng)用面擴(kuò)展到包括語音、數(shù)據(jù)通信在內(nèi)的應(yīng)用面。

（2）網(wǎng)絡(luò)覆蓋方式和范圍的擴(kuò)展。將一般的藍(lán)牙Piconet網(wǎng)絡(luò)擴(kuò)展為無縫覆蓋的藍(lán)牙蜂窩網(wǎng)絡(luò)，其網(wǎng)絡(luò)覆蓋范圍從一套房間、一層樓擴(kuò)展到一個智能化樓宇范圍的區(qū)域網(wǎng)，覆蓋范圍更廣，覆蓋方式更靈活，對于實(shí)現(xiàn)網(wǎng)絡(luò)的自動切換方式參考了現(xiàn)有的蜂窩網(wǎng)絡(luò)切換方式。

在上述藍(lán)牙網(wǎng)絡(luò)中，數(shù)據(jù)的傳輸是由主節(jié)點(diǎn)驅(qū)動的時分復(fù)用機(jī)制調(diào)度機(jī)制進(jìn)行的，并且時間片被分別分配給在一個皮克網(wǎng)內(nèi)的一個主節(jié)點(diǎn)和一個從節(jié)點(diǎn)。主節(jié)點(diǎn)能在偶數(shù)時間片內(nèi)發(fā)送給從節(jié)點(diǎn)數(shù)據(jù)包，而從節(jié)點(diǎn)只有在收到主節(jié)點(diǎn)數(shù)據(jù)包后才能在奇數(shù)時間片內(nèi)給主節(jié)點(diǎn)發(fā)送數(shù)據(jù)包。由于藍(lán)牙主要采用基于主節(jié)點(diǎn)時分復(fù)用的輪叫調(diào)度策略（RR），然而當(dāng)在輪詢序列中沒有等待傳輸?shù)臄?shù)據(jù)時，許多時間片被輪詢（Poll）或者空（Null）的數(shù)據(jù)包所占用而被浪費(fèi)。

為了克服這種鏈接浪費(fèi)問題，已經(jīng)提出了很多調(diào)度算法，如Low power mode-based policy,這個算法能相對地達(dá)到低能消耗和有效的時間片利用效果。但它并不適合動態(tài)通信量，而且還需要大量信號開銷。因此比較偏向應(yīng)用基于隊(duì)列狀態(tài)的優(yōu)先級策略，而K-Fainess Policy（KFP）則由于它的相對合理的性能顯得很突出。雖然它根據(jù)數(shù)據(jù)通信量的特點(diǎn)可以展示不同的性能，但它并沒考慮藍(lán)牙網(wǎng)絡(luò)的QoS。為了解決這個問題，Differentialted KFP（Diff-KFP算法）被提了出來。它能通過基于每對主從節(jié)點(diǎn)的隊(duì)列狀態(tài)，有區(qū)別地調(diào)度稀缺無線電資源，從而提高吞吐量。而且還能為單獨(dú)的節(jié)點(diǎn)對保證公平性，通過使用合適的參數(shù)把QoS要求反應(yīng)給調(diào)度機(jī)制。盡管Diff-KFP算法能提高吞吐量，但由于選擇了不合理的參數(shù)，現(xiàn)行通信還是可能被一個輪訓(xùn)間隔而打斷。這樣就引起吞吐量的下降。這里我們提供Diff-KFP算法的詳細(xì)內(nèi)容，并且優(yōu)化它的參數(shù)來提高整體性能，另外這個改進(jìn)了的Diff-KFP算法算法也能將QoS應(yīng)用到調(diào)度之中。

三、藍(lán)牙網(wǎng)絡(luò)的媒介接入控制（MAC）

藍(lán)牙網(wǎng)絡(luò)在主從節(jié)點(diǎn)間可建立兩種通信鏈路類型來支持同步通信量或者面向數(shù)據(jù)的異步通信量：同步面向連接鏈路（SCO）和異步無連接鏈路(ACL)。主節(jié)點(diǎn)通過在規(guī)則的間隔中保留時間片來維護(hù)SCO鏈路。由于每6個時間片就有兩個為SCO鏈路保留，剩下的時間片為ACL鏈路保留。

如圖1顯示了一個主節(jié)點(diǎn)調(diào)度數(shù)據(jù)傳輸。一個主節(jié)點(diǎn)在奇數(shù)時間片輪詢一個從節(jié)點(diǎn)，被輪詢的從節(jié)點(diǎn)在一個連續(xù)的奇數(shù)時間片內(nèi)傳輸數(shù)據(jù)包。然而藍(lán)牙技術(shù)通常采用輪叫調(diào)度策略（RR），許多時間片可能由于輪詢數(shù)據(jù)包或者空數(shù)據(jù)包的交換而被浪費(fèi)了。

盡管RR是最簡單的調(diào)度算法，并且在皮克網(wǎng)內(nèi)均勻地將數(shù)據(jù)傳輸機(jī)會分配給每對主從節(jié)點(diǎn)，但是鏈路浪費(fèi)可能會引起吞吐量的下降，而且輪叫調(diào)度策略(RR)也沒有考慮這些節(jié)點(diǎn)的優(yōu)先級。為了更有效的利用稀缺無線電資源，排隊(duì)狀態(tài)依靠數(shù)據(jù)包的調(diào)度策略?；诿繉?jié)點(diǎn)排隊(duì)狀態(tài)的KFP算法執(zhí)行對優(yōu)先級的輪詢。首先根據(jù)鏈路的利用來決定每對節(jié)點(diǎn)的類型，然后從所確定的類中分配合適的優(yōu)先級。具有較多流通量的這對節(jié)點(diǎn)具有較高的優(yōu)先級。在KFP中，優(yōu)先級低的節(jié)點(diǎn)將傳輸機(jī)會讓個優(yōu)先級高的節(jié)點(diǎn)。這樣KFP就能減少時間片的浪費(fèi)。而且，為了保障公平，KFP有個臨界參數(shù)K.每對節(jié)點(diǎn)在得到服務(wù)機(jī)會時它的計(jì)數(shù)器值加一，否則就減一。

計(jì)數(shù)器的值代表每對節(jié)點(diǎn)得到和退讓的服務(wù)機(jī)會的數(shù)量。計(jì)數(shù)器的值可以為負(fù)，通過與計(jì)數(shù)器最大最小值間的比較的K值能夠平衡服務(wù)機(jī)會的分配。這樣KFP可以控制吞吐量和公平性，然而如果數(shù)據(jù)流通量特點(diǎn)是靜態(tài)的，并且集中在特定節(jié)點(diǎn)對上，計(jì)數(shù)器最大值和最小值間的差異能很快達(dá)到臨界值K,服務(wù)機(jī)會就有可能被這對節(jié)點(diǎn)所壟斷，那么KFP與RR就很類似了。由于計(jì)數(shù)器值的最大和最小值間的差距在K的范圍內(nèi)并不減少，所以其他具有較低優(yōu)先級的節(jié)點(diǎn)對就不再讓出服務(wù)機(jī)會。因此只要提供服務(wù)的時間片數(shù)量增加，當(dāng)差距超過臨界值K時，KFP的性能就與RR類似。因此有最大計(jì)數(shù)器值的節(jié)點(diǎn)對與具有最小值的其他節(jié)點(diǎn)對影響了系統(tǒng)的整體性能。而且這個算法并沒有考慮到藍(lán)牙技術(shù)的QoS需求。

因此，需要有新的有效的調(diào)度方法來保留藍(lán)牙技術(shù)的優(yōu)點(diǎn)，諸如低成本，低電量，低復(fù)雜度。并且用合理的公平性、對吞吐量提高的有效調(diào)度來滿足QoS要求。

四、支持QoS的差分調(diào)度算法

早先的KFP算法依靠數(shù)據(jù)包的調(diào)度策略而采用一個排隊(duì)狀態(tài)。在這個方案中，由主從節(jié)點(diǎn)對的排隊(duì)狀態(tài)信息決定優(yōu)先級。例如當(dāng)一個SCO鏈路形成時，這個鏈路只允許四個連續(xù)的時間片給ACL鏈路，可以應(yīng)用一個或者三個時間片長度的數(shù)據(jù)包。如果主節(jié)點(diǎn)隊(duì)列線頭（HOL）數(shù)據(jù)包是一個三個時間片的包，而從節(jié)點(diǎn)隊(duì)列線頭數(shù)據(jù)包是一個時間片的包，那么這個鏈路利用率就是100%。因此調(diào)度分給這對最高等級并且優(yōu)先為其提供服務(wù)機(jī)會。如果一個主節(jié)點(diǎn)或者從節(jié)點(diǎn)隊(duì)列線頭數(shù)據(jù)包是一個三個時間片的數(shù)據(jù)包，而另一個則是空，那么鏈路利用率是75%。這種情況下，這對就得到第二等級。同樣地，如果一個主節(jié)點(diǎn)或者一個從節(jié)點(diǎn)隊(duì)列線頭數(shù)據(jù)包是一個時間片數(shù)據(jù)包而另外一個是空，那么這個鏈路利用率是50%。只要兩個時間片有一個被使用，那么這個節(jié)點(diǎn)對就成為第三等級。通過這個確定過程，每對的優(yōu)先級就能確定下來。

KEP的操作在圖2中顯示出來，這里countermaster，countermin，counteri和counterhighest分別代表在所有節(jié)點(diǎn)對中的最大計(jì)數(shù)值，最小計(jì)數(shù)值，第i節(jié)點(diǎn)對計(jì)數(shù)值和具有最高等級的節(jié)點(diǎn)對計(jì)數(shù)值。每對節(jié)點(diǎn)的計(jì)數(shù)器跟蹤記錄這對節(jié)點(diǎn)所接受過的過度或偏少的服務(wù)機(jī)會，這個值用來服務(wù)的控制。當(dāng)每對主從節(jié)點(diǎn)在RR內(nèi)被連續(xù)的訪問時，不管它是否在KFP中為最高等級，所被輪詢的節(jié)點(diǎn)對要么得到服務(wù)或者就放棄服務(wù)的機(jī)會。每對節(jié)點(diǎn)值在這對節(jié)點(diǎn)放棄服務(wù)機(jī)會或者搶占其他節(jié)點(diǎn)機(jī)會時，就會相應(yīng)的加一或者減一。只有在最大計(jì)數(shù)值和最小計(jì)數(shù)值間的差異不超過臨界值K時才允許服務(wù)機(jī)會的更替，例如在最大值時就會發(fā)生不公平性。如果沒有允許一對主從節(jié)點(diǎn)放棄服務(wù)機(jī)會，那么它就在預(yù)定時間片內(nèi)傳遞數(shù)據(jù)包。

我們所提出的支持QoS的差分調(diào)度算法，Diff-KFP算法在圖3中顯示出來。每對優(yōu)先級和計(jì)數(shù)值的決定過程跟KFP相類似。新算法在保證公平性的技術(shù)方面有三點(diǎn)與KFP不同。首先，如果不是在最大值與最小值之間而是在最大值與當(dāng)前對計(jì)數(shù)值間的差值小于K值，那么主節(jié)點(diǎn)就檢查。如果是這樣的話，主節(jié)點(diǎn)就根據(jù)節(jié)點(diǎn)對服務(wù)等級來決定這對節(jié)點(diǎn)是否放棄調(diào)度轉(zhuǎn)變。因此，這樣就能夠阻止具有最大計(jì)數(shù)值的節(jié)點(diǎn)對和具有最小的節(jié)點(diǎn)對對整個系統(tǒng)的性能的限制。第二，每個計(jì)數(shù)器減少的值，stepi對于每對節(jié)點(diǎn)反應(yīng)他的QoS要求是不同的，而在KFP中都是相同的。這樣，通過合適地選擇步長和更新Diff-KFP算法參數(shù)，我們能較好的控制性能。圖3中，stepi和stepmax分別代表第i對節(jié)點(diǎn)的步長和所有節(jié)點(diǎn)對中的步長最大值。最后，在圖4的流程圖中的右分支那里顯示出來了，通過（stepmax-stepi）增加計(jì)數(shù)值來克服超過K值的問題。

五、小結(jié)

中國電信、中國移動、中國聯(lián)通已在1月8日取得了國內(nèi)3G牌照，意味著移動通信終端將發(fā)生大的變革，在現(xiàn)有的PDA、筆記本、手機(jī)等移動終端所支持的藍(lán)牙協(xié)議上，還是面臨著網(wǎng)絡(luò)延遲和阻塞等問題。

參考文獻(xiàn)：

[1]蔡海慧，方旭名．藍(lán)牙自組網(wǎng)中的調(diào)度策略.電信快報(bào)，2003，(10)：30～34.

[2]馬忠建，方旭明，蔡?；?，傲丹．藍(lán)牙AdHoc網(wǎng)調(diào)度策略的設(shè)計(jì)與仿真.系統(tǒng)仿真學(xué)報(bào)，2006，18(9)：2546～2549，2608.