張瑞琪， 降愛蓮

(太原理工大學 計算機科學與技術學院，山西 太原 030024)

多信道時分多址MAC協(xié)議在WMN中的優(yōu)化應用*

張瑞琪， 降愛蓮

(太原理工大學 計算機科學與技術學院，山西 太原 030024)

隨著無線Mesh網絡(WMN)中跳數(shù)的增加，端到端的延時急劇增大，所以，在多跳WMN中很難做到服務質量(QoS)保證。針對以上問題，提出了一種新型多信道時分多址(TDMA)媒體訪問控制(McTMAC)的協(xié)議，可以有效地降低在多跳網絡中端到端的延時。通過測試評估結果顯示：McTMAC協(xié)議優(yōu)于現(xiàn)有的無線WMN協(xié)議，通過使用McTMAC協(xié)議端到端最大延時降低了60 %。

調度延遲; 多信道; 時隙分配; 時分多址; 信道分配; 無線Mesh網絡

0 引 言

無線Mesh網絡(WMN)作為一種新興的通信網絡，其網絡拓撲中包含多個通信節(jié)點。隨著它的發(fā)展應用，多跳通信鏈路的服務質量也開始受到關注。因為隨著跳數(shù)的增加，端到端的延時快速升高。為了解決這種延時升高問題，基于媒體控制(MAC)協(xié)議的時分多址(TDMA)技術被采用并作為標準?；赥DMA的WMN采用時隙分配算法來降低端到端的延時，所以，最優(yōu)化需要處理的問題就是降低最大延時，但現(xiàn)有優(yōu)化方式都是局限于使用單信道系統(tǒng)。

盡管在WMN中有多種信道分配算法，但是大部分都只是增強系統(tǒng)容量，如“distance-1”算法就是增加了系統(tǒng)的容量[1]。盡管這種算法能夠明顯地提高系統(tǒng)的容量，但是它卻沒有考慮到端到端的延時問題。文獻[2]中所提的算法是基于最大數(shù)據流的多頻射多信道WMN中選取最優(yōu)信道分配和集中鏈路分配。這些算法都能夠以最少的時隙數(shù)完成全部數(shù)據的傳送，但是最少的時隙數(shù)并不能保證降低多跳數(shù)據流端到端的延時[2]。文獻[3]中提到了集中式和分散式的最大調度算法在多頻射多信道WMN中的應用，文中考慮到了數(shù)據交換延時，但是它沒有考慮到在多跳連接鏈路中的傳輸順序，這是影響端到端延時的重要因素[3]。

本文提出在多信道鏈路中，使用一種基于TDMA的多信道網狀網絡，分別采用信道和時隙分配算法來實現(xiàn)降低端到端延時的目標。本文算法主要是基于長的數(shù)據流進行信道分配和時隙分配。

1 WMN中的延時問題

假設有多跳WMNG=(N,L)，其中,N為設備集合，L為連接設備的鏈路集合。存在于節(jié)點n和m的鏈路為l=(n,m)，其中,節(jié)點n和m包含在傳輸網絡中。假設l∈L，節(jié)點n通過多通道系統(tǒng)C向m發(fā)送數(shù)據包。此外，假設一個時間被分為固定連續(xù)的幀T的TDMA型系統(tǒng)，每個幀又被細分為一個時隙集合k。假定有流集合F和流f，規(guī)定F為節(jié)點集合R(f)={v1,v2,…,vn}，其中,vi為鏈路中的第i個節(jié)點。第一個節(jié)點v1為源節(jié)點，vn為接收節(jié)點。在圖1中，有一個數(shù)據流R(f1)={1,2,3,4}。節(jié)點1是源節(jié)點，節(jié)點4是目標節(jié)點，有3條通道，在每一幀中都有k=5的時隙。

圖1 無沖突信道中兩條數(shù)據流時隙分配Fig 1 Time-slot assignment of two data flows in conflict free channel

網絡中某個節(jié)點使用信道和時隙的組合(c,s)發(fā)送一個數(shù)據包，這兩個參數(shù)是確定聯(lián)機或是脫機的,因此，WMN就會有信道和時隙的分配問題。本文所關注是QoS，所以,目標是有效地降低數(shù)據流的延時[4]。其中重點是要找出一種最優(yōu)的方法來減小數(shù)據流的最大延時，因為這是一個NP完全問題。

2 長數(shù)據流優(yōu)先信道分配和長數(shù)據流優(yōu)先時隙分配

首先，向所有的鏈路分配信道,然后根據算法向信道分配時隙，算法的核心思想是給予長數(shù)據流更高的優(yōu)先級。采取這種長數(shù)據流優(yōu)先(longest flow first,LFF)的思想效果很明顯，因為在WMN中，隨著跳數(shù)的增加，端到端延時明顯增大，網絡吞吐量顯著下降[5]。

2.1 LFF信道分配

目前常用的算法采用在次要沖突鏈路中的爭議等級。在信道c中，鏈路l的爭議等級是鏈路中有干擾的鏈路的數(shù)目。例如:鏈路(1,2)在獨立的信道1和2之間的爭用等級有0和2。這些沖突鏈路是在干擾范圍內的一對鏈路。如果它們有公共節(jié)點，即為主要沖突鏈路；否則，即為次要的。鏈路(1,2)和(2,3)為主要的沖突鏈路，而鏈路(1,2)和(3,4)為次要沖突鏈路。在LFF的信道分配中，本文根據“distance-1”算法，并且進一步將數(shù)據流的長度考慮在內，利用爭用等級或次要沖突鏈路數(shù)目來分配信道的過程如下：

1)初始化次要爭用等級為0。

2)根據流長度降序排列數(shù)據流。

3)在數(shù)據流序列中選取最長的且沒有分配信道的流f。

4)對于未分配信道的流f的所有鏈路l：

a.分配信道c給爭用等級最小的流；

b.如果等級相等，且原鏈路的爭用等級是最小的，將信道分配給原始鏈路；否則，任意分配給一條爭用等級最小的鏈路;

c.更新次要爭用等級。

5)如果l是流f中的最后一條鏈路，跳至步驟(2)；否則，跳至步驟(3)。

如圖1中例子所示，有2條數(shù)據流R(f1)={1,2,3,4}和R(f2)={5,6}。假定有2條可用信道，由于流f1最長，LFF信道分配算法首先為它分配信道。對于鏈路(1,2),由于爭用等級的初始值為0，所以,它任意選取一條信道，假定分配信道1。然后，由于前一步的鏈路分配，算法同樣分配信道給鏈路(2,3)。那么，在信道1和2中鏈路(3,4)的爭用等級分別是1和0。需要注意的是,在計算次要沖突鏈路的數(shù)量時，鏈路(3,4)并沒有相同的節(jié)點，因此,LFF信道分配算法將鏈路(3,4)分配在信道2，其中,鏈路(3,4)是最低的爭用等級。流f1的鏈路分配完后，LLF信道分配算法為鏈路(5,6)上的流f2分配信道。因為在信道1和2上的爭用等級分別是2和1，所以分配信道2。

2.2 LFF時隙分配

在WMN的時隙分配中，提出了基于樹的拓撲結構，可以最大程度地減小端到端的延時[6]。然而，它卻被局限在單一的信道和單一的網關中。本文提出的LFF時隙分配算法將在多網關、多信道的網絡中應用。與信道分配算法相似，LFF時隙分配算法仍然采用的是長數(shù)據流。算法基本思想是分配長數(shù)據流的多個時隙，使得以前鏈路中的數(shù)據包可以被立即完成傳輸。例如：如果時隙1在優(yōu)先鏈路中被用于數(shù)據流1，分配時隙2或相近時隙2可以流程化傳輸。和LFF信道分配一樣，優(yōu)先給長數(shù)據流分配時隙。每個鏈路都有一個沒有在沖突鏈路中使用的時隙列表，列表中每一個時隙都可以被選取。時隙分配過程如下：

1)初始化可用時隙列表{1,2,3,…,T},其中,T為時隙個數(shù)。

2)根據流長度降序排列數(shù)據流。

3)在數(shù)據流序列中選取最長的且沒有分配信道的流f。

4)對于未分配信道的流f的所有鏈路l：

a.將其后最接近先前鏈路中時隙的可用時隙t分配;

b.如果以上時隙不存在，則T加1，且重新應用該算法；

c.更新可用時隙列表。

5)如果l是流f的最后一條鏈路，跳到步驟(2)；否則，跳到步驟(3)。

如圖1所示為LFF時隙分配的結果。其最長的流f1在鏈路(2,3)分配時隙2在先前鏈路(1,2)在時隙1傳送到達后立即傳輸。由于次要沖突鏈路(5,6)和(1,2)被分配了不同的信道，它們可以同時在時隙1安排傳輸。本文提出的算法是半靜態(tài)的，本文在給定的網絡假設了一組給定的數(shù)據流。信道和時隙的分配可以按需要變?yōu)楣潭ǖ拈g隔。此外，本算法與傳統(tǒng)算法不同，它采用的是網絡層中的數(shù)據流，而現(xiàn)在大部分信道分配算法都是工作在數(shù)據鏈路層。

3 性能評估

本文提出的算法的性能在Matlab 7.0中自己開發(fā)的模擬器進行測試評估。模擬802.11標準的網狀網絡如圖2所示，其模擬器的參數(shù)如表1所示。

圖2 5×5網狀網絡Fig 2 5×5 mesh network

參數(shù)數(shù)值速率2Mbps編解碼器G729A數(shù)據包大小864bits時隙大小432μs分組間隔24路由協(xié)議負載均衡、最小跳數(shù)

3.1 LFF信道分配算法與“distance-1”算法對比

假定有10個雙向噪聲信息通過一組節(jié)點(1,3,10,20,11,22,24,919,17)到網關節(jié)點25。最有效的數(shù)據通信就是當所有的時隙都沒有用于噪聲通信時，所有的節(jié)點都以2 Mbps的速度傳輸數(shù)據。如圖3顯示了兩信道分配算法在1～5個信道中端到端延時性能表現(xiàn)。當3個信道時，端到端最大延時降低了60 %，并且隨著信道數(shù)量增加，端到端延時性能變化較小，因為在網狀網絡中4個信道能夠滿足任意沖突中的信道分配。

圖3 LFF信道分配算法性能測試Fig 3 Performance test of LFF channel allocation algorithm

3.2 LFF時隙分配

通過使用LFF時隙分配算法與其他算法對比，如PETAR09。仿真模擬在擁有信道1和信道2的線性網絡拓撲中完成的。數(shù)據鏈從1到8的長度各不相同，圖4表示了PETAR09延遲性能和LFF時隙分配在單雙信道中的延遲性能的對比。

通過使用LFF時隙分配算法與其他算法對比，如PETAR09。仿真模擬在擁有信道1和信道2的線性網絡拓撲中完成的。數(shù)據鏈的長度各不相同，圖4表示了PETAR09延遲性能和LFF時隙分配算法在單雙信道中的延遲性能的對比。理想化的結果是所有的時隙全部有效使用。由于PETAR09算法被設計用于單信道的網絡中，所有它在單信道中的性能表現(xiàn)與LFF時隙分配算法的性能相同。當LFF時隙分配算法在雙信道中使用時，與單信道性能相比，其最大延時降低了大約48 %。

圖4 LFF時隙分配算法性能測試Fig 4 Performance test of LFF time slot assignment algorithm

4 結 論

本文分析了McTMAC協(xié)議在多跳WMN有效地處理了端到端延時。PETAR09算法的時隙分配與多信道時隙分配結合應用，增強了“distance-1”算法的信道分配性能。模擬結果顯示：本文的時隙算法得到的結果與PETAR09在單信道時隙分配應用結果相似，并且在多信道環(huán)境中優(yōu)于PETAR09算法。此外，模擬結果還表明：在某些情況下，使用LFF信道分配算法替代“distance-1”算法能夠明顯降低端到端最大延時。

[1] Aryafar E,Gurewitz O,Knightly E.Distance-1 constrained cha-nnel assignmentin single radio wireless mesh networks[C]∥IEEE INFOCOM,Orlando,USA:IEEE Communications Society,2008:762-770.

[2] Yu H,Mohapatra H,Liu X.Channel assignment and link scheduling in multi-radio multi-channel wireless mesh networks[J].Journal of Network and Computer Applications,2008,13(3):169-185.

[3] Yun M.Channel-assignment schedulingin wireless mesh networks considering switching overhead[C]∥IEEE ICC,Dresden,Germany:IEEE Communications Society,2009:1-6.

[4] 種紅波.無線Mesh網QoS關鍵技術研究[D].長沙:中南大學,2010.

[5] 王 震,常穎華.基于預測時延的無線Mesh網絡組播路由算法[J].傳感器與微系統(tǒng),2012,31(4):133-137.

[6] 漆華妹,陳志剛,吳顯平.基于最小加代數(shù)理論求解無線Mesh網絡端到端延遲上界的方法[J].高技術通訊,2010,33(20):233-238.

Optimization application of multi-channel TDMA MAC protocol in WMN*

ZHANG Rui-qi， JIANG Ai-lian

(College of Computer Science and Technology, Taiyuan University of Technology, Taiyuan 030024,China)

With the increasing number of hops,it is difficult to guarantee QoS over multihop wireless mesh networks(WMN) because end-to-end delay increases quickly.To solve the above issues,a novel multi-channel time-division multiple-access(TDMA) media access control(MAC),that is McTMAC protocol that can help to efficiently reduce end-to-end delay over multihop networks.Performance evaluation results demonstrate that McTMAC outperforms existing WMN protocols,the maximum-delay can be reduced by as much as 60 % by using McTMAC protocol.

scheduling delay; multi-channel; time-slot assignment; TDMA; channel assignment; WMN

2013—09—11

山西省留學回國人員科研資助項目(2011—10); 山西省基礎研究資助項目(2013011019—7)

TP 393

A

1000—9787(2014)04—0158—03

張瑞琪(1988-)，男，山西太原人，碩士研究生，主要從事無線傳感器網絡的研究。