無線簇樹網下的GTS時隙調度算法*

葉雪梅， 朱云杰， 蔡艷寧， 范青剛， 李鵬遠

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

0 引 言

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

1 問題描述

1.1 簇樹網絡結構下的超幀調度機制

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

圖1 超幀結構圖

在CAP，設備使用帶時隙的CSMA/CA訪問機制。在CFP，協調器根據上一個超幀時期網絡中設備申請GTS同步時隙的情況，將其劃分成若干個GTS同步時隙。

1.2 簇間沖突與暴露節點

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

圖2 臨近簇間沖突

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

圖3 暴露節點問題

2 基于區分服務的GTS統籌調度算法

基于第1.2節中描述的問題，考慮由中心協調器節點Sink來匯集網絡的總體通信請求和協調時隙分配。將節點的通信請求細分為發送和接收2種類別，時隙分配時充分考慮節點之間的干擾和影響，盡可能地將互不影響的通信分配為并行狀態，從而提高信道的利用率。

2.1 形式定義

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

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

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

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

表1中各自段含義為：

表1 基于區分服務的GTS請求幀

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

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

2.2 調度算法

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

1)生成各節點沖突域CRi，簇內節點在CAP以廣播方式根據節點短地址尋找。

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

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

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

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

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

3 實例分析與仿真實驗

3.1 實例分析

以碼頭倉庫濕度測量網絡為應用背景，網絡規模為200個終端，父節點最多可連接的子節點數Cm=18，子節點中最多可以連接的路由節點個數Rm=5，網絡的最大深度Lm=4。中心協調器在網絡中部，網絡抽象圖如圖4所示。

圖4 倉庫濕度采集網絡抽象圖

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

圖5 幀的載荷

其沖突矩陣為

GTSR8R1R4N81N82N83N84N85N86N87N13N14N15N42100000000000000200000000000000300000000000000400000000000000500000000000000600000000000000700000000000000

Sink將第1，2時隙分配給R8節點，并對R4，R8的時隙分配表進行修改如下

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

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

稍后N11節點也發出了它的GRTS幀，載荷段如圖6。

圖6 載荷段

其沖突矩陣為

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

3.2 仿真實驗

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

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

圖7 網絡吞吐率

圖8 網絡平均時延

圖9 丟包率

4 結束語

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

參考文獻:

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

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

[3] 洪 榛，俞 立，張貴軍.無線傳感器網絡自適應分布式聚簇路由協議[J].自動化學報,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] 蔣 挺，趙成林,紫 蜂.技術及應用[M].北京:北京郵電大學出版社，2006:46-115.