DTFMM:一種適應于WMSNs的多信道MAC協(xié)議*

張龍妹，史浩山*，陸 偉

(1.西北工業(yè)大學電子信息學院，西安710072;2.西北工業(yè)大學計算機學院，西安710072)

無線多媒體傳感器網(wǎng)絡(luò)(WMSNs)在傳統(tǒng)的無線傳感器網(wǎng)絡(luò)(WSNs)基礎(chǔ)上增加了語音，圖像，視頻等多媒體信息的獲取和處理，強大的信息感知功能使其在國防、工業(yè)、農(nóng)業(yè)、機械、建筑、醫(yī)療等等領(lǐng)域都具有極大的應用前景［1－2］。與傳統(tǒng)的WSNs不同的是，WMSNs通常要求更高的帶寬，需要更大的網(wǎng)絡(luò)吞吐量來將大數(shù)據(jù)量的多媒體信息快速可靠地傳送到基站(BS)［3］。但是，現(xiàn)有的商業(yè)傳感器節(jié)點如MICAz［4］提供的250 kbit/s數(shù)據(jù)率不能有效地支持多媒體流量。當前的無線傳感器網(wǎng)絡(luò)硬件設(shè)備，如MICAz和Telos使用CC2420無線收發(fā)器，提供了對多個頻率信道通信的支持。而目前流行的無線網(wǎng)絡(luò)協(xié)議，如802.11、ZigBee等，雖然在物理層提供了多個可用的頻率信道，而MAC層并沒有提供多信道的機制來充分利用物理層的信道資源，致使很多性能優(yōu)良的單信道的MAC協(xié)議在多信道環(huán)境中發(fā)揮不出其優(yōu)勢。因此，設(shè)計多信道的MAC協(xié)議，允許多對節(jié)點在不同信道同時通信，可以增加網(wǎng)絡(luò)吞吐量并減少節(jié)點等待接入信道的時間，對帶寬和實時性要求較高的多媒體應用具有重要意義。

本文深入研究了目前移動Ad Hoc網(wǎng)絡(luò)和WSNs中幾種典型的多信道MAC協(xié)議，在此基礎(chǔ)上，提出了一種輕量級的能量有效的多信道MAC協(xié)議——DTFMM協(xié)議。該協(xié)議基于分簇的網(wǎng)絡(luò)拓撲，有效地結(jié)合了頻分和時分機制的特點。仿真結(jié)果表明，本文提出的方法可分級性好，通過合理的頻分和時分復用避免了節(jié)點間的訪問沖突，減小了時延，能夠最大化網(wǎng)絡(luò)的吞吐量，滿足WMSNs的大數(shù)據(jù)速率和高QoS要求。

1 引言

目前，針對 Ad Hoc網(wǎng)絡(luò)和 WSNs的多信道MAC協(xié)議的研究大體上可以分為兩大類:基于競爭的多信道協(xié)議［5－7］和基于調(diào)度的多信道 MAC協(xié)議［8－9］。DCA［5］協(xié)議要求每個節(jié)點有兩個收發(fā)器，指定一個專門的信道用于傳遞控制消息，其余信道用于數(shù)據(jù)通信。該協(xié)議中有一個收發(fā)器始終偵聽控制信道，有效地避免了多信道環(huán)境的隱藏終端問題，然而，每個節(jié)點兩個收發(fā)器加大了硬件成本。另外，當信道數(shù)很少時，一個信道用作控制信道造成了很大的浪費;當信道數(shù)很多時，基于包的信道協(xié)商又會使控制信道成為瓶頸，使數(shù)據(jù)信道的利用率不高。MMAC［6］協(xié)議基于 IEEE 802.11 的節(jié)能模式，每個節(jié)點只配備一個半雙工無線收發(fā)器，通過周期性地傳輸信標將時間分成了固定大小的信標間隔，在每個信標間隔開始處的ATIM窗口階段，所有節(jié)點都偵聽一個公共信道來協(xié)商信道分配，ATIM窗口之后的剩余數(shù)據(jù)窗口里，各個節(jié)點切換到協(xié)商好的信道交換控制消息進行通信。受可用信道數(shù)的限制，相同的信道還是會分配給多個節(jié)點，為解決這個問題，MMAC協(xié)議在數(shù)據(jù)窗口仍然需要采用802.11 DCF的RTS/CTS握手機制來競爭占用信道，這將引入可觀的控制開銷并帶來進一步的時延。另外，該協(xié)議需要全網(wǎng)嚴格的時間同步，這從網(wǎng)絡(luò)成本上來說是個不小的開銷。MMSN［7］是第一個專門針對無線傳感器網(wǎng)絡(luò)特點而設(shè)計的多信道MAC協(xié)議，每個節(jié)點配置一個收發(fā)器，該協(xié)議為每個節(jié)點指定一個信道用于接收數(shù)據(jù)并廣播給鄰居節(jié)點，因此每個節(jié)點都知道要給鄰居節(jié)點傳輸包時所使用的頻率。該協(xié)議在信道數(shù)足夠多的情況下取得了較高的吞吐量，信道數(shù)不足時會有多個節(jié)點分配到同一個信道導致沖突，從而降低了信道的利用率。Xun等在文獻［8］中基于分簇的網(wǎng)絡(luò)結(jié)構(gòu)，提出了一種簇內(nèi)頻分，簇間時分的多信道MAC協(xié)議。該協(xié)議采用基于簇首協(xié)調(diào)的機制增加了節(jié)點的總的休眠時間，但是簇首頻繁地切換信道要消耗更多的能量。COMMAC［9］協(xié)議是專門針對WMSNs的基于調(diào)度的多信道MAC協(xié)議。該協(xié)議也是基于分簇的網(wǎng)絡(luò)拓撲，但要求簇首裝配有N個半雙工收發(fā)器，由簇首調(diào)度簇內(nèi)成員的頻率和時隙的分配。該協(xié)議只解決了簇內(nèi)節(jié)點的通信而沒有考慮全網(wǎng)的信道分配問題，另外每個簇首裝配N個收發(fā)器大大增加了硬件成本，而更一般的情況是傳感器節(jié)點只有一個半雙工收發(fā)器。

以上所列出的都是當前有代表性的多信道MAC協(xié)議，它們都有自身的特點同時也有一定的局限性。本文提出的DTFMM協(xié)議只要求每個節(jié)點配備單個收發(fā)器，較以前的多信道MAC協(xié)議更適合于實際的多媒體傳感器網(wǎng)絡(luò)。簇首間分布式局部協(xié)調(diào)的信道分配和重用策略能保證各個簇同時無干擾的通信。簇首協(xié)調(diào)的簇內(nèi)TDMA機制避免了節(jié)點間的信道訪問沖突，增加了系統(tǒng)中節(jié)點總的休眠時間，提高了網(wǎng)絡(luò)的能效。

2 DTFMM協(xié)議設(shè)計

2.1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)和假設(shè)條件

2.1.1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)

一組同構(gòu)的多媒體傳感器節(jié)點隨機散布在監(jiān)測區(qū)域中，節(jié)點之間采用一種類似于HEED［10］的分布式的隨機分簇算法形成一些不相交的簇。一小部分傳感器節(jié)點充當簇首(CH)的功能，負責簇的組織管理和簇內(nèi)訪問的調(diào)度安排，其余的大部分節(jié)點則負責從周圍環(huán)境中獲取有用信息并傳輸給相應的CH。簇首之間通過最小生成樹路由［11］，將收集到的信息通過多跳方式轉(zhuǎn)發(fā)給基站(BS)。分簇的過程要保證每個節(jié)點只能加入一個簇，即簇之間沒有重疊，為了防止簇首能量很快耗盡，節(jié)點可以輪流充當簇首。圖1給出了一種通用的分簇網(wǎng)絡(luò)拓撲結(jié)構(gòu)，箭頭代表了各簇首到BS的最小生成樹路徑。

2.1.2 假設(shè)條件

(1)有N個不重疊的可用信道，所有信道具有相同的帶寬。

(2)所有多媒體傳感器節(jié)點是同構(gòu)的，即具有相同的能量和處理能力。每個傳感器節(jié)點裝有一個半雙工收發(fā)器。

圖1 分簇網(wǎng)絡(luò)拓撲和CH間的最小生成樹路徑

(3)BS具有充足的能量供應和處理能力，并裝配有N個半雙工收發(fā)器。BS位于監(jiān)控區(qū)域的中心，其通信范圍可覆蓋整個監(jiān)測區(qū)域。

(4)每個節(jié)點只能加入一個簇，且能跟其CH直接通信。當選為CH的節(jié)點將發(fā)射功率調(diào)整為普通節(jié)點的1.5倍，以保證CH之間的連接度，即所有CH都可以通過一跳或多跳路由將收集到的數(shù)據(jù)傳輸?shù)紹S。

(5)網(wǎng)絡(luò)成簇后，每個簇都有一個唯一的從0開始并連續(xù)編號的簇ID號。BS的簇ID號為0。

2.2 DTFMM協(xié)議設(shè)計

假設(shè)網(wǎng)絡(luò)已經(jīng)部署好并形成了如圖1所示的分簇拓撲，那么DTFMM協(xié)議可以分三個階段描述，分別是分布式信道分配階段，簇內(nèi)通信階段和簇間通信階段。

2.2.1 分布式信道分配算法

在網(wǎng)絡(luò)形成并分簇后，每個CH都知道自己的ID以及相鄰簇的ID。每個節(jié)點維護一個相鄰簇的信息列表NL(包括簇ID號以及信道選擇結(jié)果)。信道分配順序基于簇的優(yōu)先級進行，ID號小的簇優(yōu)先選擇信道。任意CH在開始信道選擇時，先檢查自己的NL，只有當NL中比自己優(yōu)先級高的簇選擇完畢后才能開始自己的選擇。簇首選定信道后，在公共信道廣播選擇結(jié)果，收到廣播信息的鄰居CH及時更新其NL，而本簇內(nèi)的成員節(jié)點則將收發(fā)器調(diào)到簇首所選的信道。當最低優(yōu)先級的CH選擇信道后，信道分配過程結(jié)束。公共信道可由網(wǎng)絡(luò)協(xié)調(diào)者(如BS)在網(wǎng)絡(luò)建立時選擇。圖2給出了圖1所示的分簇網(wǎng)絡(luò)的簇ID排序和一種可能的信道選擇結(jié)果，為了簡化，簇內(nèi)成員節(jié)點未畫出。本算法中簇ID編號以從內(nèi)到外擴散方式排序，圖中箭頭表示最小生成樹路徑，虛線表示簇首之間一跳可達。

圖2 網(wǎng)絡(luò)中簇ID排序以及信道選擇結(jié)果

圖2中信道分配從CH1開始，選擇信道1并向ID號為2，5，7，8的鄰簇廣播，只有 CH2在其 NL中具有最高優(yōu)先級，于是選擇信道4并廣播，其鄰居CH3，CH9更新各自的 NL，CH3選擇信道 6，然后CH4選擇信道3，CH5選擇信道5。這一輪結(jié)束后，ID號為6，7，8，10，12的簇都在各自的 NL中處于最高優(yōu)先級，可以同時進行信道選擇，但要遵守信道選擇的原則，即相鄰簇使用不同的且不相鄰的信道。按照這種方式，圖2中23個簇僅使用6個信道就可以實現(xiàn)各簇內(nèi)同時且無干擾的通信。

該信道分配算法具有以下幾個特點:

(1)用于信道分配的消息開銷很小，且消息開銷與總的簇數(shù)N成線性關(guān)系。

(2)任意簇首只要在其NL中具有最小的ID就可以開始信道選擇，使得該算法具有一定的并行性。

(3)信道選擇保證能在最多N次循環(huán)后結(jié)束，N是分簇的總數(shù)。

2.2.2 簇內(nèi)通信階段

網(wǎng)絡(luò)中節(jié)點分簇并形成路由樹后，每個簇首與BS共享簇信息，BS知道各個簇的ID及其簇內(nèi)的節(jié)點數(shù)。信道選擇結(jié)束后，各簇首將收發(fā)器調(diào)到選定的信道上。BS在每個信道內(nèi)廣播簇內(nèi)通信所需的最大時隙數(shù)，以滿足節(jié)點數(shù)最多的簇的通信需求。簇內(nèi)通信階段的幀長由最多節(jié)點數(shù)的簇決定，具有很少節(jié)點的簇頭可以休眠很長時間直到簇間通信階段開始。

在簇內(nèi)通信階段，簇首收集簇內(nèi)成員節(jié)點的報告數(shù)據(jù)，為了防止多個節(jié)點同時向簇首發(fā)送數(shù)據(jù)造成沖突，簇內(nèi)采用TDMA方式進行信道訪問。簇內(nèi)通信階段每個簇的時間幀結(jié)構(gòu)如圖3所示，由同步信標，傳輸請求，調(diào)度階段以及數(shù)據(jù)傳輸階段組成。首先由簇首在本簇的信道內(nèi)廣播同步信標，對各成員節(jié)點進行時間同步，然后有數(shù)據(jù)發(fā)送的節(jié)點以CSMA方式向簇首發(fā)送請求消息，消息中包括自身的節(jié)點ID號和要傳輸?shù)臄?shù)據(jù)大小。簇首收到這些請求信息后根據(jù)一定的優(yōu)先原則進行調(diào)度，并在調(diào)度階段將時隙分配情況在信道中廣播。各成員節(jié)點在各自的時隙到來時進行數(shù)據(jù)傳輸，并在傳輸結(jié)束后關(guān)掉收發(fā)器休眠，直到下一輪簇內(nèi)通信開始時醒來。所有成員節(jié)點的數(shù)據(jù)傳輸結(jié)束時，簇首關(guān)掉無線電進入睡眠模式，直到簇間通信階段到來。

圖3 簇內(nèi)通信階段各個簇的時間幀結(jié)構(gòu)

2.2.3 簇間通信階段

收集了簇內(nèi)所有成員節(jié)點的數(shù)據(jù)后，簇首和簇首之間通過多跳路由將數(shù)據(jù)發(fā)送給BS，進入簇間通信階段。假設(shè)網(wǎng)絡(luò)在分簇過程結(jié)束后，采用文獻［11］中的算法，形成了圖1中箭頭所指示的路由樹，該樹以BS為樹根，有多個獨立、不相交的路徑，且路徑的最大深度是受限的。簇內(nèi)通信結(jié)束后，各簇首駐留在自己的信道上，簇首間要進行通信，首先必須切換到同一個信道。因此，簇間通信仍然先要解決信道分配問題，以保證各條路徑同時無干擾的傳輸。這里采用一種簡單有效地信道分配算法，各條獨立的路徑采用該路徑上距離BS最近的簇首使用的信道。因為前面的信道分配已經(jīng)保證了相鄰簇采用不同的且不相鄰的信道，因此，這種基于路徑的信道分配策略仍然是無干擾的。同一條路徑上的簇首仍然采用TDMA的方式訪問信道，時隙的選擇按照深度優(yōu)先的順序。因此，簇間通信的最大延遲與簇間路由樹的最大深度成正比。

3 性能評估

我們在GloMoSim［12］仿真平臺下實現(xiàn)了DTFMM協(xié)議，并從算法的收斂性、網(wǎng)絡(luò)的吞吐量、平均包延遲等方面考察協(xié)議的性能。為了便于對比和分析，我們還實現(xiàn)了MMSN的平均信道分配算法。

3.1 仿真環(huán)境

一定數(shù)目的傳感器節(jié)點隨機散布在400 m×400 m的區(qū)域，BS位于部署區(qū)域的中心。傳感器節(jié)點的通信范圍為50 m，最大可達100 m。BS的通信范圍能覆蓋整個部署區(qū)域?？捎玫男诺罃?shù)設(shè)為8，每個信道帶寬都是250 kbit/s。簇內(nèi)最大節(jié)點數(shù)為20，路由樹的最大深度設(shè)為6。假設(shè)每個傳感器節(jié)點以概率P(0＜P≤1)隨機產(chǎn)生0～500 byte的數(shù)據(jù)請求，P越大，則表示每單位時間需要傳輸?shù)臄?shù)據(jù)越多，網(wǎng)絡(luò)負載則越重。在以下每組實驗中，傳感器節(jié)點數(shù)目從100到600之間變化，對每一種數(shù)目的節(jié)點部署，用不同的隨機種子多次運行分簇算法，以形成不同的分簇網(wǎng)絡(luò)拓撲，圖中每個實驗值都是取20次運行結(jié)果的平均值。

3.2 仿真結(jié)果

3.2.1 分布式信道分配算法的收斂性

信道分配算法的收斂性用全部簇首完成信道選擇所用的循環(huán)次數(shù)來度量。圖4給出了信道選擇的平均循環(huán)次數(shù)和節(jié)點總數(shù)及總簇數(shù)之間的關(guān)系。從圖4中可以看出，隨著傳感器節(jié)點數(shù)從100增加到600，網(wǎng)絡(luò)中的分簇總數(shù)從22增加到45，而信道分配算法的平均循環(huán)次數(shù)只從100個節(jié)點時的5次增加到600個節(jié)點時的8次。該結(jié)果表明，盡管網(wǎng)絡(luò)規(guī)模增長很快，但是信道選擇過程仍然在很少的有限次循環(huán)后結(jié)束，并沒有隨網(wǎng)絡(luò)規(guī)模的增加線性增加，這是因為算法本身具有一定的并行性，同時也說明該算法對大規(guī)模的網(wǎng)絡(luò)也有很好的收斂性和可分級性。

圖4 分布式信道分配算法的收斂性

3.2.2 MAC 層的吞吐量

這里的吞吐量指的是單位時間內(nèi)MAC層成功傳遞的總的數(shù)據(jù)量。圖5中給出了DTFMM和MMSN兩種協(xié)議隨著網(wǎng)絡(luò)中節(jié)點數(shù)增加時的吞吐量變化情況。從圖5中可以看出，當網(wǎng)絡(luò)中節(jié)點數(shù)目小于200時，網(wǎng)絡(luò)中的負載較輕，這兩種協(xié)議的MAC層吞吐量大致相當。隨著節(jié)點數(shù)的增多，DTFMM的吞吐量隨著節(jié)點數(shù)增多幾乎呈線性增長，而MMSN協(xié)議的吞吐量增加緩慢，甚至在節(jié)點數(shù)超過500后吞吐量呈下降趨勢。這是因為我們提出的DTFMM協(xié)議中信道分配算法是無沖突的，最大限度了重用了網(wǎng)絡(luò)中可用的頻率資源，即使節(jié)點數(shù)增多也不會造成節(jié)點的訪問沖突，因此吞吐量隨著網(wǎng)絡(luò)中的節(jié)點數(shù)增加而幾乎線性增加。而MMSN中采用平均信道分配算法，當網(wǎng)絡(luò)中節(jié)點數(shù)目繼續(xù)增多時，信道數(shù)目遠遠不夠，就會造成信道的競爭和數(shù)據(jù)訪問的沖突，且這種沖突隨著節(jié)點數(shù)目增多而逐漸加劇，頻繁的數(shù)據(jù)碰撞造成了網(wǎng)絡(luò)吞吐量的下降。

圖5 MAC層總的吞吐量

3.2.3 平均包延時

圖6給出了DTFMM和MMSN兩種協(xié)議隨著網(wǎng)絡(luò)中節(jié)點數(shù)增加的包延遲性能對比。在節(jié)點數(shù)為100時，網(wǎng)絡(luò)中的負載較輕，MMSN協(xié)議的延遲要略小于DTFMM，因為DTFMM協(xié)議幀內(nèi)采用TDMA的方式，節(jié)點只有在自己的時隙才可以發(fā)送數(shù)據(jù)，帶來了一定的延時。然而，隨著節(jié)點數(shù)增多，節(jié)點間的信道競爭加劇，MMSN協(xié)議中信道沖突的概率越來越大，碰撞和重傳帶來了較大的延時。而DTFMM協(xié)議中節(jié)點傳輸始終是無沖突的，隨著簇內(nèi)節(jié)點數(shù)增加，簇內(nèi)通信的時隙數(shù)也因此增加，造成時延稍有增大，但受簇內(nèi)最大節(jié)點數(shù)的限制(這里設(shè)為20)，包延時不會過大。

圖6 平均包延時性能對比

4 結(jié)論

本文針對無線多媒體傳感器網(wǎng)絡(luò)提出了一種新穎的無沖突的多信道MAC協(xié)議。該協(xié)議基于分簇的網(wǎng)絡(luò)結(jié)構(gòu)，采用FDMA和TDMA的混合機制來最大限度地重用頻率資源，提高網(wǎng)絡(luò)吞吐量和時延特性。仿真結(jié)果表明即使在傳感器節(jié)點密度很高的情況下，分布式信道分配算法也可以在少量的循環(huán)后收斂，因此算法具有很好的可分級性。下一步將優(yōu)化設(shè)計幀間通信中信道和時隙的分配算法，使得各路徑分支中也可用多信道并行傳輸，進一步降低數(shù)據(jù)收集的時延。

［1］Akyildiz I F.A Survey on Wireless Multimedia Sensor Networks［J］.Computer Networks，2007，51:921－960.

［2］Sharif A.Wireless Multimedia Sensor Network Technology:A Survey［C］//7th IEEE International Conference on Industrial Informatics，INDIN 2009，June，2009:606－613.

［3］Charfi Y.Challenging Issues in Visual Sensor Networks［J］.IEEE Wireless Communications，2009，16:44－49.

［4］XBOW MICA2 Mote Specifications［EB/OL］＜ http://www.xbow.com/＞.

［5］Wl Shih－Lin.A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks［C］//Proceedings of International Symposium on Parallel Architectures，Algorithms and Networks，I-SPAN 2000，2000:232－237.

［6］So J，Vaidya N.Multi-Channel Mac for Ad Hoc Networks:Handling Multi-Channel Hidden Terminals Using a Single Transceiver［C］//Proceedings of the 5th ACM International Symposium on Mobile ad Hoc Networking and Computing，MobiHoc′04，2004:222－233.

［7］Zhou G.MMSN:Multi-Frequency Media Access Control for Wireless Sensor Networks［C］//Proceedings of 25th IEEE International Conference on Computer Communications，INFOCOM′06，2006:1－13.

［8］Xun C.A Multi-Channel MAC Protocol for Wireless Sensor Networks［C］//.The Sixth IEEE International Conference on Computer and Information Technology，CIT′06，Sept，2006:224－224.

［9］Cheng L.A Cluster Based On-Demand Multi-Channel MAC Protocol for Wireless Multimedia Sensor Networks［C］//IEEE International Conference on Communications，ICC′08，May 2008:2371－2376.

［10］Younis O，F(xiàn)ahmy S.HEED:a Hybrid，Energy-Efficient，Distributed Clustering Approach for Ad Hoc Sensor Networks［J］.IEEE Transactions on Mobile Computing，2004，3:366－379，

［11］Li－Jen M.A Parallel Algorithm for the Degree-Constrained Minimum Spanning Tree Problem Using Nearest-Neighbor Chains［C］//Proceedings of Fourth International Symposium on Parallel Architectures，Algorithms，and Networks，I-SPAN′99，1999:184－189.

［12］Zeng X.GloMoSim:a Library for Parallel Simulation of Large-Scale Wireless Networks［C］//Proceedings of Twelfth Workshop on Parallel and Distributed Simulation，PADS 98，1998:154－161.