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

張龍妹，史浩山*，陸 偉

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

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

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

1 引言

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

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

2 DTFMM協議設計

2.1 網絡拓撲結構和假設條件

2.1.1 網絡拓撲結構

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

2.1.2 假設條件

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

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

圖1 分簇網絡拓撲和CH間的最小生成樹路徑

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

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

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

2.2 DTFMM協議設計

假設網絡已經部署好并形成了如圖1所示的分簇拓撲，那么DTFMM協議可以分三個階段描述，分別是分布式信道分配階段，簇內通信階段和簇間通信階段。

2.2.1 分布式信道分配算法

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

圖2 網絡中簇ID排序以及信道選擇結果

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

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

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

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

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

2.2.2 簇內通信階段

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

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

圖3 簇內通信階段各個簇的時間幀結構

2.2.3 簇間通信階段

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

3 性能評估

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

3.1 仿真環境

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

3.2 仿真結果

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

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

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

3.2.2 MAC 層的吞吐量

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

圖5 MAC層總的吞吐量

3.2.3 平均包延時

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

圖6 平均包延時性能對比

4 結論

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

［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，Fahmy 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.