張瑞琪， 降愛蓮

(太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

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

張瑞琪， 降愛蓮

(太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

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

調(diào)度延遲; 多信道; 時(shí)隙分配; 時(shí)分多址; 信道分配; 無線Mesh網(wǎng)絡(luò)

0 引 言

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

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

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

1 WMN中的延時(shí)問題

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

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

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

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

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

2.1 LFF信道分配

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

1)初始化次要爭(zhēng)用等級(jí)為0。

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

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

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

a.分配信道c給爭(zhēng)用等級(jí)最小的流；

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

c.更新次要爭(zhēng)用等級(jí)。

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

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

2.2 LFF時(shí)隙分配

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

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

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

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

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

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

b.如果以上時(shí)隙不存在，則T加1，且重新應(yīng)用該算法；

c.更新可用時(shí)隙列表。

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

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

3 性能評(píng)估

本文提出的算法的性能在Matlab 7.0中自己開發(fā)的模擬器進(jìn)行測(cè)試評(píng)估。模擬802.11標(biāo)準(zhǔn)的網(wǎng)狀網(wǎng)絡(luò)如圖2所示，其模擬器的參數(shù)如表1所示。

圖2 5×5網(wǎng)狀網(wǎng)絡(luò)Fig 2 5×5 mesh network

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

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

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

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

3.2 LFF時(shí)隙分配

通過使用LFF時(shí)隙分配算法與其他算法對(duì)比，如PETAR09。仿真模擬在擁有信道1和信道2的線性網(wǎng)絡(luò)拓?fù)渲型瓿傻?。?shù)據(jù)鏈從1到8的長(zhǎng)度各不相同，圖4表示了PETAR09延遲性能和LFF時(shí)隙分配在單雙信道中的延遲性能的對(duì)比。

通過使用LFF時(shí)隙分配算法與其他算法對(duì)比，如PETAR09。仿真模擬在擁有信道1和信道2的線性網(wǎng)絡(luò)拓?fù)渲型瓿傻?。?shù)據(jù)鏈的長(zhǎng)度各不相同，圖4表示了PETAR09延遲性能和LFF時(shí)隙分配算法在單雙信道中的延遲性能的對(duì)比。理想化的結(jié)果是所有的時(shí)隙全部有效使用。由于PETAR09算法被設(shè)計(jì)用于單信道的網(wǎng)絡(luò)中，所有它在單信道中的性能表現(xiàn)與LFF時(shí)隙分配算法的性能相同。當(dāng)LFF時(shí)隙分配算法在雙信道中使用時(shí)，與單信道性能相比，其最大延時(shí)降低了大約48 %。

圖4 LFF時(shí)隙分配算法性能測(cè)試Fig 4 Performance test of LFF time slot assignment algorithm

4 結(jié) 論

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

[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網(wǎng)QoS關(guān)鍵技術(shù)研究[D].長(zhǎng)沙:中南大學(xué),2010.

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

[6] 漆華妹,陳志剛,吳顯平.基于最小加代數(shù)理論求解無線Mesh網(wǎng)絡(luò)端到端延遲上界的方法[J].高技術(shù)通訊,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

山西省留學(xué)回國(guó)人員科研資助項(xiàng)目(2011—10); 山西省基礎(chǔ)研究資助項(xiàng)目(2013011019—7)

TP 393

A

1000—9787(2014)04—0158—03

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