葉雪梅， 朱云杰， 蔡艷寧， 范青剛， 李鵬遠(yuǎn)

(1.西安高科技研究所 計算機(jī)教研室，陜西 西安 721006；2.西安高科技研究所 401教研室，陜西 西安 721006)

0 引 言

隨著微電子技術(shù)、計算機(jī)技術(shù)、通信技術(shù)的迅猛發(fā)展，無線傳感器網(wǎng)絡(luò)的性能和穩(wěn)定性快速提升，其應(yīng)用領(lǐng)域已經(jīng)從環(huán)境監(jiān)測、微控制等開始向低速率的即時通信方向發(fā)展。針對簇樹結(jié)構(gòu)下的各類路由優(yōu)化算法進(jìn)行研究的文章很多[1～3]，對網(wǎng)絡(luò)的組建、路由的發(fā)現(xiàn)、生存能耗等問題進(jìn)行了研究；然而對于網(wǎng)絡(luò)的速率，各級設(shè)備的交互沖突和多跳延時問題，MAC協(xié)議的性能同樣是一個決定性因素。Zig Bee技術(shù)所采用的IEEE 802.15.4[4]協(xié)議的MAC層規(guī)范是比較公認(rèn)的適合在對等無線傳感器網(wǎng)絡(luò)中應(yīng)用的協(xié)議之一。但仍存在多跳延時過大、鄰近簇沖突、暴露節(jié)點、信道利用率低等問題，且未給出具體的信標(biāo)幀或各級設(shè)備超幀分配的調(diào)度算法，因此，針對分配算法衍生了一系列研究。文獻(xiàn)[5]提出了一種基于整數(shù)線性規(guī)劃的時分簇調(diào)度方法來避免IEEE 802.15.4中超幀沖突，但其方法過于復(fù)雜。文獻(xiàn)[6]提出了一種通道預(yù)留機(jī)制，是把信標(biāo)幀中的GTS信息和預(yù)留地址信息單獨作為一個命令幀發(fā)送,雖然節(jié)省了很多能量,但該命令幀的發(fā)送時隙不好確定。文獻(xiàn)[7]設(shè)計了一個動態(tài)GTS請求幀，在一個超幀中動態(tài)GTS可以不止一次地分配給同一個節(jié)點，這樣做的弊端是很可能被一個節(jié)點占據(jù)所有GTS資源。本文將基于IEEE 802.15.4標(biāo)準(zhǔn)，來研究簇樹網(wǎng)絡(luò)中的非競爭時段(contention free period，CFP)的通信沖突問題，并提出一種解決方法，以保證簇樹網(wǎng)絡(luò)中實時通信的暢通運行。

1 問題描述

1.1 簇樹網(wǎng)絡(luò)結(jié)構(gòu)下的超幀調(diào)度機(jī)制

IEEE 802.15.4規(guī)范主要針對低速無線個域網(wǎng)(low-rate wireless personal area network，LR-WPAN )制定，它規(guī)定了物理層和介質(zhì)訪問控制子層與固定、便攜式及移動設(shè)備之間的低數(shù)據(jù)率無線連接的規(guī)范[8]。在IEEE 802.15.4中使用以超幀為周期組織通信。每個超幀都以信標(biāo)(beacon)幀為開始，并將通信時間劃為活躍和不活躍2個部分，活躍時期又劃分為3個階段：信標(biāo)發(fā)送時段、競爭訪問時段(contention access period，CAP)和CFP。如圖1所示，為一個超幀結(jié)構(gòu)。

圖1 超幀結(jié)構(gòu)圖

在CAP，設(shè)備使用帶時隙的CSMA/CA訪問機(jī)制。在CFP，協(xié)調(diào)器根據(jù)上一個超幀時期網(wǎng)絡(luò)中設(shè)備申請GTS同步時隙的情況，將其劃分成若干個GTS同步時隙。

1.2 簇間沖突與暴露節(jié)點

1)臨近簇間沖突問題：圖2中，路由器R1和R2是各自簇的簇首，通過超幀組織簇內(nèi)通信，R1簇中設(shè)備M1和R2簇中設(shè)備M2由于位置相鄰會產(chǎn)生通信干擾。如果M1和M2在各自超幀通信的GTS中有時間上的重疊，就會產(chǎn)生臨近簇間的沖突，從而無法通信。

圖2 臨近簇間沖突

2)暴露節(jié)點問題：由于采用的是統(tǒng)一調(diào)度機(jī)制，所以不存在隱藏節(jié)點問題。當(dāng)有一個節(jié)點要發(fā)送數(shù)據(jù)給鄰居節(jié)點，但因為其它鄰居節(jié)點正在發(fā)送數(shù)據(jù)，而影響了它的發(fā)送。如圖3，路由節(jié)點S1和S2，S1和R1，S2和R2都處在彼此的通信半徑內(nèi)；R1和R2不在彼此通信范圍內(nèi)。當(dāng)S1傳送數(shù)據(jù)給R1時，S2卻不能傳送數(shù)據(jù)給R2。因為此時S2檢測到正有節(jié)點在占用信道而放棄對信道的爭用，事實上，S2可以傳送數(shù)據(jù)給R2，因為R2并不在S1的通信范圍內(nèi)，S1則稱為S2的暴露節(jié)點。同理，當(dāng)S1正在接收R1的信息，而S2試圖接收R2的信息時則請求不被允許，而實際上若R1和R2的覆蓋半徑并不相交時，S2的請求是可以被允許的。

圖3 暴露節(jié)點問題

2 基于區(qū)分服務(wù)的GTS統(tǒng)籌調(diào)度算法

基于第1.2節(jié)中描述的問題，考慮由中心協(xié)調(diào)器節(jié)點Sink來匯集網(wǎng)絡(luò)的總體通信請求和協(xié)調(diào)時隙分配。將節(jié)點的通信請求細(xì)分為發(fā)送和接收2種類別，時隙分配時充分考慮節(jié)點之間的干擾和影響，盡可能地將互不影響的通信分配為并行狀態(tài)，從而提高信道的利用率。

2.1 形式定義

定義1 沖突域CRi：在MAC協(xié)議中各節(jié)點之間只進(jìn)行直接數(shù)據(jù)傳遞，所以，信道征用的沖突問題只在相鄰節(jié)點之間發(fā)生，把節(jié)點Ri的CFP時段的信道沖突域CRi定義為，CRi={R/與Ri之間小于一跳范圍的節(jié)點}。ai為節(jié)點Ri的狀態(tài)值

定義2 時隙分配表Ti:Ri的GTS分配表Ti定義為k(CAP包含時隙數(shù))維列向量Ti=[a1,a2,…,ak]T。

定義3 沖突矩陣C:節(jié)點的沖突矩陣C=Ti×CRi完整地描述了其與周邊節(jié)點的信道共用情況，其大小與CFP包含的時隙數(shù)，節(jié)點的信號覆蓋范圍直接相關(guān)

定義4 區(qū)分服務(wù)的GTS請求幀(GTS-request to server,GRTS)：將算法的計算依據(jù)和控制信息整合成GRTS幀，如表1所示。

表1中各自段含義為：

表1 基于區(qū)分服務(wù)的GTS請求幀

服務(wù)類別(Server Style,SS)域,把數(shù)據(jù)分為實時數(shù)據(jù)流(RT)和盡力交付數(shù)據(jù)流(BE)。GTS個數(shù)和目的節(jié)點域成對使用，表示預(yù)請求通話的目的節(jié)點和時長。沖突域CRi為Ri節(jié)點的沖突域。編號為幀的防重復(fù)編號從1～255循環(huán)使用。

判定定理：Ri是無線網(wǎng)絡(luò)中的任一路由節(jié)點，當(dāng)其沖突域滿足如下公式時，網(wǎng)絡(luò)通信沖突不存在且可避免暴露節(jié)點問題

2.2 調(diào)度算法

基于以上思想本文提出一種基于區(qū)分服務(wù)的GTS統(tǒng)籌調(diào)度算法(a macroscopical GTS scheduling algorithm based on differentiated services)。算法的具體步驟如下：

1)生成各節(jié)點沖突域CRi，簇內(nèi)節(jié)點在CAP以廣播方式根據(jù)節(jié)點短地址尋找。

2)生成GRTS幀并發(fā)往Sink，依據(jù)采集數(shù)據(jù)和通信量的大小，計算所需時隙數(shù)，取定服務(wù)優(yōu)先級對幀編號。

3)協(xié)調(diào)器節(jié)點對最先到達(dá)的節(jié)點請求進(jìn)行分配，依據(jù)其沖突域CRi內(nèi)各節(jié)點的分配表Ti生成沖突矩陣，尋找滿足定理條件的包含連續(xù)k(k大于等于申請結(jié)點申請的時隙數(shù))個GTS的CFP，按最小號優(yōu)先原則從前到后進(jìn)行分配，改寫其Ti值,若無可分配資源則不分配。

4)重復(fù)步驟(3)，直到所有請求都被滿足。

5)重新檢驗各節(jié)點的沖突域，對于不滿足2.1中定理的各節(jié)點所分配的GTS全部收回，對于其請求重新運行步驟(3)分配。

6)GTS分配方案通知各節(jié)點。

3 實例分析與仿真實驗

3.1 實例分析

以碼頭倉庫濕度測量網(wǎng)絡(luò)為應(yīng)用背景，網(wǎng)絡(luò)規(guī)模為200個終端，父節(jié)點最多可連接的子節(jié)點數(shù)Cm=18，子節(jié)點中最多可以連接的路由節(jié)點個數(shù)Rm=5，網(wǎng)絡(luò)的最大深度Lm=4。中心協(xié)調(diào)器在網(wǎng)絡(luò)中部，網(wǎng)絡(luò)抽象圖如圖4所示。

圖4 倉庫濕度采集網(wǎng)絡(luò)抽象圖

R8節(jié)點請求給R4發(fā)送信息，需要2個GTS，若其GRTS幀為Sink收到的第一個請求幀，載荷部分如圖5所示。

圖5 幀的載荷

其沖突矩陣為

GTSR8R1R4N81N82N83N84N85N86N87N13N14N15N42100000000000000200000000000000300000000000000400000000000000500000000000000600000000000000700000000000000

Sink將第1，2時隙分配給R8節(jié)點，并對R4，R8的時隙分配表進(jìn)行修改如下

TR8={1，1，0，0，0，0，0},

TR4={-1，-1，0，0，0，0，0}.

稍后N11節(jié)點也發(fā)出了它的GRTS幀，載荷段如圖6。

圖6 載荷段

其沖突矩陣為

GTSN11R1N01N12N15N65N6611001-1 102001-1 0013100-1 0104000-1 0-1 -1 5-1 -1 00010600000117-1 001000

3.2 仿真實驗

本文采用NS2網(wǎng)絡(luò)仿真軟件，網(wǎng)絡(luò)拓?fù)錇閳D4所示。競爭窗口值采用NS2默認(rèn)值。物理層采用TwoRayGround模型，節(jié)點接收距離RXThreshold為120 m。載波頻率為2.4 GHz，發(fā)送功率為100 mW，天線高度為15 cm，增益為1。仿真采用恒定比特率CBR業(yè)務(wù)流模擬實時數(shù)據(jù)業(yè)務(wù)，數(shù)據(jù)包大小為512 byte。路由層采用了AODV協(xié)議。MAC層分別使用了文獻(xiàn)[7]中的動態(tài)GTS請求算法簡稱為DGS和本文的算法簡稱為MGS(macroscopical GTS scheduling)。通過仿真比較2種情況下的網(wǎng)絡(luò)性能。圖7～圖9給出了網(wǎng)絡(luò)吞吐率、丟包率、發(fā)送時延隨發(fā)送速率變化的比較情況。

由圖7仿真結(jié)果可以看出:開始時由于通信量少，所以,沖突的發(fā)生和信道征用問題不是很尖銳，網(wǎng)絡(luò)的性能差別不大。但隨著網(wǎng)絡(luò)負(fù)荷的增大，發(fā)送速率的提高，信道的征用問題、時隙的競爭問題開始明顯起來，本文提出的算法在發(fā)送速率達(dá)到300 kB/s以前吞吐率近似呈線性增加，而DGS算法則受發(fā)送速率影響較大，網(wǎng)絡(luò)的吞吐量隨發(fā)送速率上升較緩。由圖8可以看出：本文算法在200 kB/s的發(fā)送速率下，傳播時延較穩(wěn)定，而DGS算法則存在較大的波動性，從圖中可以看到其出現(xiàn)了幾次明顯的抖動，傳播時延不穩(wěn)定。由圖9可見，2種算法的丟包率相差無幾，可見改變時隙的分配算法對網(wǎng)絡(luò)的丟包率影響不大。

圖7 網(wǎng)絡(luò)吞吐率

圖8 網(wǎng)絡(luò)平均時延

圖9 丟包率

4 結(jié)束語

統(tǒng)籌調(diào)度機(jī)制相比于競爭機(jī)制，在節(jié)點密集，網(wǎng)絡(luò)負(fù)荷大的情況下能發(fā)揮出更好的優(yōu)勢。本文針對無線簇樹網(wǎng)絡(luò)中的通信沖突和暴露節(jié)點問題展開研究，提出了一種分析理論和判定準(zhǔn)則，并在此基礎(chǔ)上給出了一種基于區(qū)分服務(wù)的GTS統(tǒng)籌調(diào)度算法。從仿真結(jié)果來看，算法能夠充分利用信道，合理分配時隙，避免不必要的通信沖突，在不影響丟包率的前提下提高網(wǎng)絡(luò)吞吐率、縮短穩(wěn)定網(wǎng)絡(luò)時延，體現(xiàn)出了明顯優(yōu)勢，同時映證了判定準(zhǔn)則的正確性。但算法在應(yīng)用范圍上還具有局限性，其帶寬開銷、時間開銷隨網(wǎng)絡(luò)的規(guī)模成幾何級數(shù)增加，所以，不適用于大規(guī)模無線網(wǎng)絡(luò)。算法在GTS的資源利用問題上沒有加以考慮，分配時隙時，采用最小號優(yōu)先原則，對于連續(xù)的大GTS時段申請，缺乏保障；同時算法對全網(wǎng)的時間同步要求也比較苛刻，這一點也沒能考慮。

參考文獻(xiàn):

[1] 李小青，李 暉，楊 凱.一種基于D-S證據(jù)理論的Ad Hoc網(wǎng)絡(luò)安全路由協(xié)議[J].計算機(jī)研究與發(fā)展,2011，48(8)：1406-1413.

[2] 鐘 智，樊曉平，羅大庸，等.一種基于網(wǎng)格的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].傳感器與微系統(tǒng),2012,30(12)：18-20.

[3] 洪 榛，俞 立，張貴軍.無線傳感器網(wǎng)絡(luò)自適應(yīng)分布式聚簇路由協(xié)議[J].自動化學(xué)報,2011,37(10)：1197-1205.

[4] IEEE Std 802.15.4TM.IEEE standard for information technology-telecommunications and information exchange between systems-local and metropolitan area networks-specific requirements-part 15.4:Wireless medium aceess control(MAC)and physical layer(PHY)specifications for low-rate wireless personal area networks(LR-WPANs)[S].NewYork:IEEE Press.2003.

[5] Jurcik Peter．Real-time communication over cluster-tree wireless sensor networks[R]．Report，Porto:IPP-HURRAY ，2010．

[6] Cheng Liang,Bourgeois A G.Efficient channel reservation for multicasting GTS allocation and pending addresses in IEEE 802.15.4[C]∥Proc of the 3rd Int’l Conf on Wireless and Mobile Communications,2007:46-46.

[7] Song Jun keun, Ryoo Jeong Dong,Kim Sang Cheol, et al. A dynamic GTS allocation algorithm in IEEE 802.15.4 for QoS gua-ranteed real-time applications[C]∥Proc of IEEE Int’l Symp on Consumer Electronics,2007:1-6.

[8] 蔣 挺，趙成林,紫 蜂.技術(shù)及應(yīng)用[M].北京:北京郵電大學(xué)出版社，2006:46-115.