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

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

0 引 言

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

1 問(wèn)題描述

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

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

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

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

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

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

圖2 臨近簇間沖突

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

圖3 暴露節(jié)點(diǎn)問(wèn)題

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

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

2.1 形式定義

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

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

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

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

表1中各自段含義為：

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

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

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

2.2 調(diào)度算法

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

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

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

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

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

5)重新檢驗(yàn)各節(jié)點(diǎn)的沖突域，對(duì)于不滿足2.1中定理的各節(jié)點(diǎn)所分配的GTS全部收回，對(duì)于其請(qǐng)求重新運(yùn)行步驟(3)分配。

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

3 實(shí)例分析與仿真實(shí)驗(yàn)

3.1 實(shí)例分析

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

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

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

圖5 幀的載荷

其沖突矩陣為

GTSR8R1R4N81N82N83N84N85N86N87N13N14N15N42100000000000000200000000000000300000000000000400000000000000500000000000000600000000000000700000000000000

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

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

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

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

圖6 載荷段

其沖突矩陣為

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

3.2 仿真實(shí)驗(yàn)

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

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

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

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

圖9 丟包率

4 結(jié)束語(yǔ)

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

參考文獻(xiàn):

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

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

[3] 洪 榛，俞 立，張貴軍.無(wú)線傳感器網(wǎng)絡(luò)自適應(yīng)分布式聚簇路由協(xié)議[J].自動(dòng)化學(xué)報(bào),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.