一種基于虛擬鏈路的多信道M AC機制*

羅 娟,羅海波,李仁發

(湖南大學計算機與通信學院,湖南長沙 410018)

一種基于虛擬鏈路的多信道M AC機制*

羅 娟1?,羅海波1,李仁發1

(湖南大學計算機與通信學院,湖南長沙 410018)

在Zigbee協議體系基礎上,提出了一種基于虛擬鏈路的多信道媒質訪問機制VL-MAC,針對分簇的網絡結構,結合時分和頻分復用,簇內由簇頭進行時間調度,實現簇內無沖突通信,兩簇跳鄰簇范圍的各簇使用不同的信道,以避免簇間的干擾.簇間的數據傳輸在一個虛擬鏈路進行上,連整個網絡存在幾條互不重疊的虛擬鏈路,使用虛擬M IMO接收不同鏈路上的數據,避免Sink周圍數據量大造成的嚴重沖突.VL-MAC解決了隱終端問題.仿真實驗表明,VL-MAC減少了整個網絡的干擾,降低了傳輸時延,減少了能耗.

媒質接入控制;多信道分配;時分復用;虛擬M IMO

對于無線通信,在同一時間,同一空間,同一頻率下的兩個傳輸鏈路存在一定的沖突和干擾,為了避免這種干擾,可采用時分、頻分或碼分的方式.目前,常用的無線通信協議如802.11,802.15.4/Zigbee等,它們的MAC并沒有提供多信道的機制用于充分利用物理層的信道頻率資源[1-2].使用多信道的接入方式有利于減少沖突和干擾,提高網絡吞吐量、節省能量.

S-MAC[3]是一個能量有效的協議,使用基于競爭的隨機接入,但它不是一個多信道協議.CMAC[4]假設節點使用兩個發射器,一個用于數據傳輸,一個用于協調和管理.Mohamed Younis和Sam uel Bushra假設基站擁有多個發射器設計了ARCH多信道算法[5],但沒有考慮簇間通信的具體機制,且沒有解決隱藏終端問題(hidden terminal p roblem),在文獻[6]中,針對大數據量的數據采集傳感網絡,使用多基站的方式,提出了一種分布式的動態信道分配機制,以達到不同信道間的數據負載平衡,使整個網絡的吞吐量達到最大,此算法和CMAC,ARCH一樣,都不適合普遍存在的網絡中所有節點只有一個發射器的情況.MCM AC協議[2]使用簇內頻分和簇間時分的方式,簇頭必須頻繁的進行信道切換,浪費信道資源.此外,TFMAC[7]和SM RS-MAC[8]都基于單發射器設計了多信道算法,但前者不適合大規模網絡,后者局限于網絡中所有節點都是鄰居.

本文在每個節點配備單射頻的前提下,基于分簇的網絡結構,簇內節點分配傳輸時隙,相鄰簇使用不同的信道,通過適當選擇簇半徑,解決了隱終端問題,在簇頭和Sink節點之間,形成幾條“虛擬鏈路”用于簇間傳輸,這樣,有效地避免了干擾,減少了重發,增加了網絡吞吐量.

1 多信道MAC機制

本算法基于網絡的分簇管理,前提假設如下: 1)Sink節點(匯聚節點)單獨成簇.

2)越接近Sink節點的簇規模越小,越遠離Sink節點的簇規模越大.

3)所有簇的簇內節點都能跟其簇頭(CLH)直接通信,即一跳可達其簇頭.

4)網絡成簇后,每個簇都有一個唯一的從1開始并連續編號的ID號,Sink節點ID號總為1.

VL-MAC機制主要包括3個方面:信道分配、簇內通信和簇間通信.

1.1 信道分配機制

無線協議在物理層的信道數是有限的,802.15. 4在2.4G頻段共有16個信道可用,在網絡形成并成簇后,首先進行信道資源的分配,本文針對小規模和大規模網絡,分別提出了集中式和分布式分配算法.這兩種算法都基于簇的優先級進行,簇ID號越小,優先級越高.信道的分配過程只在Sink節點和簇頭之間進行,分配完畢后,由簇頭管理信道信息并在公共信道內廣播給簇內各節點.公共信道可選擇為網絡協調者(Coordinator)在網絡建立時所選擇的信道.

1.1.1 小規模網絡

在小規模網絡中,Sink節點維護3個數據結構:鄰簇矩陣表(A),可用信道列表(UC),不可用信道列表(UUC).網絡建立時,Coordinator獲得邏輯信道資源并進行信道掃描構成UC,UUC初始化為空,A的構造規則如下:

1)矩陣中下三角某個元素a jj=1表示:簇i跟簇j一簇跳相鄰(i＞j,j優先級必比i高).

2)矩陣中下三角某個元素ajj=2表示:簇i跟簇j二簇跳相鄰(i＞j,j優先級必比i高).

3)矩陣中對角線上的元素aii=m表示:簇i已選定信道m.初始化都為0(表示未選定).

4)其余元素都為0.

簇跳定義為兩個簇頭間的最小跳數.矩陣A為Nc維方陣(Nc為簇的數目),此矩陣為一個下三角矩陣,采用壓縮存儲方式.

Sink按優先級進行信道分配,即依次計算得到aii(i≤i≤Nc).信道分配的理想情況是2跳范圍內的節點使用不同的信道,而對于分簇管理的網絡,則應要求兩簇跳鄰簇范圍內各簇使用不同信道,考慮到在ZigBee網絡中,相鄰節點使用相鄰信道的情況下仍然存在干擾[9],本文使用的信道分配原則是:ⅰ)一跳鄰簇信道不鄰不重,ⅱ)二跳鄰簇信道不重.對于ID號為i的簇,只需查詢優先級比其高的1跳和2跳鄰簇的信道分配情況,即求aii時,只需掃描矩陣A的第i行,然后根據以上的分配原則進行選擇即可,偽代碼如下:

由以上分析得到,在分配時,需要對Nc維矩陣A的下三角進行掃描,時間復雜度為 O((Nc2-Nc)/2),當網絡規模小,Nc較小時,時間收斂性較好,但不適合大規模網絡.

1.1.2 大規模網絡

網絡規模較大時,采用分布式的信道分配算法,網絡中各簇頭保存其2簇跳范圍內鄰簇信息結構CIS(包括簇ID、簇跳數和信道選擇結果).信道的選擇過程仍然按優先級進行,簇ID號小的簇優先選擇.任意簇頭只有當2簇跳范圍內比自己優先級高的簇選擇完畢后才能開始自己的選擇,并在選擇后把選擇結果廣播給2簇跳內鄰簇,同時,任意簇頭在兩簇跳范圍內所有比自己優先級高的簇都進行選擇后,或者不存在比自己優先級高的簇時,立即開始進行選擇過程.

由算法的特點可知此算法具有一定并行性,且是收斂的,時間復雜度近似地正比于Nc,在選擇過程中,只需在2簇跳范圍內廣播選擇結果(由簇ID號和信道號組成的數據信息),通信開銷較小.

1.2 簇內通信

信道分配完畢后,各簇頭CH i在公共信道內通告信道選擇結果C i給其簇內節點,并切換到 Ci. VL-MAC對于簇內通信采用TDM方式進行.

對于簇頭CH i,通信過程可分為4個階段:

1)申請階段:接受和應答簇內節點提出的申請,并按照申請的通信數據量分配時隙.

2)接收數據階段:此階段簇內節點按照所分配的時隙依次進行數據傳輸,否則進入休眠狀態.

3)休眠階段:簇頭在簇內通信完畢且簇間通信到來前進行休眠,此段時間的長短取決于簇內節點通信量的大小以及簇間通信的長短.簇內節點在此階段休眠.

4)簇間通信階段:簇頭之間在虛擬鏈路上進行數據傳輸.

各階段時間的分配:

如圖1,其中階段1～階段4的時間分別為Ts1～Ts4.網絡中每個節點都維護兩個值:即每個時隙的時間長度和總時隙數Nslot.

其中:DL為應用中需要發送的數據長度,K為數據傳輸速率,例如DL為1 000 B,K為200 kbps,Tslot為1 000*8/200 kbps=40m s.

式中:C表征數據融合度,融合度越高,C越小,簇間通信所要求時隙數也會越小.Nm為網絡中簇內所允許的最大節點數.

圖1 時隙分配表示圖Fig.1 Slot assignment

Tslot×Nslot為一個時隙周期,決定了全網中除Sink節點外的所有節點進行一輪簇內通信和簇間通信的時間.

對于某個特定的簇,Ts1～Ts4的分配由各簇頭按照自己簇內節點的實際數目(Ns)分配完成.其中最重要的為Ts2,Ts4,下面給出其表達式.

H(H≥1)為本簇離Sink的簇跳數.

算法中需要實現時間同步,可以使用802.15. 4/ZigBee網絡中的信標偵,此外,可以選擇在時隙申請期之前進行時間的同步(大約幾個m s即可),這樣可以避免由于時間漂移造成的同步誤差,從而影響時隙調度,特別是各個時隙邊緣的通信沖突[10].

1.3 簇間通信

在整個網絡中,以Sink為中心,形成幾條公共信道鏈路(虛擬鏈路),每條鏈路選擇跟Sink直連的簇頭所在的簇使用的信道,如圖2所示,在簇間通信時,所有屬于此鏈路的簇頭都需要切換到此公共鏈路信道,由于跟Sink直連的簇頭必然工作在互不相鄰的信道,所以這些虛擬鏈路信道亦不重疊,即虛擬鏈路之間互不干擾,簇間數據可無沖突的傳輸到與Sink直連的簇頭上,這樣緩解了Sink附近數據量大造成的高沖突.相當于把與Sink直連的簇頭虛擬成Sink節點的接收器,稱之為虛擬M IMO機制.

在圖2中,共有3條虛擬鏈路,分別工作在第11信道,13信道和15信道.虛線部分表示兩簇是1跳相連的.本文已假設接近Sink的簇規模較少,根據2.2節分析,其簇內通信的開銷也較少,而簇間通信的窗口較大,有利于接收公共鏈路信道上的數據以及將數據在公共信道內將數據上傳給Sink,Sink直連各簇頭與Sink的通信由Sink節點統一調度,按時分復用的方式進行.在802.15.4/ZigBee中,跟Coordinator相連的節點可以通過申請GTS(受保證的時隙)分時的與其通信,這個過程較易在Zig-Bee網絡中實現.

圖2 簇間通信公共信道鏈路表示圖Fig.2 V irtual Link during inter-cluster communication

1.4 隱終端問題

如圖3所示,極限情況下,在一條鏈路上,簇C1,C2,C3依次相鄰,根據本文的信道分配原則,C2和C1,C3使用的信道不相鄰不重合,C1和C2使用的信道不重合,屬于C1的節點n1位于C1和C2的交界處,屬于C3的節點n2位于簇C2和簇C3的交界處,VL-MAC使用分簇的網絡結構,以簇為單位進行信道分配,所以VL-MAC中不存在隱終端問題的充分條件是:任意簇的簇內節點在其兩倍通信距離內不存在使用相同信道的簇,即節點的兩倍通信距離范圍不覆蓋使用相同信道的簇.顯然,節點n1和節點n2是最可能存在隱終端的兩類節點.

圖3 VL-MAC中隱終端問題示意圖Fig.3 H idden terminal p roblem

1)對于n1,當 x=1時,其兩倍通信距離范圍(即以2r為半徑的圓)不會超出C1和C2的范圍,則不存在隱終端.

2)對于n2,其兩倍通信距離范圍(以2x2r為半徑的圓)左側不能超出C1的左邊緣,則需要滿足條件:2r+2xr≥2x2r,即1＜x＜1.62.

綜合以上兩點可以看出,VL-MAC不存在隱終端問題的充要條件是:1＜x＜1.62.即簇半徑增長倍數要小于1.62.

2 仿真分析

本文使用離散事件驅動仿真器OMNET++來仿真VL-MAC的性能,比較時延、吞吐量,通過節點在一個時隙周期中的休眠期比例來表征能耗,并與S-MAC進行了比較.在仿真時,布撒了115個節點,由于不關心分簇的過程,所以我們初始化了一個符合要求的分簇網絡,最大簇內節點數為20.仿真時假設每個節點以概率P隨機產生0～2 000 B的數據請求,P越大,每單位時間傳輸的數據越多,網絡負載越重.仿真時的其他參數如下:數據傳輸速率200 kbps,每個時隙傳輸數據的長度為1 000 B,每個時隙的長度為40 ms,一個周期總時隙數為30,一個周期總時長為1.2 s.

從圖4可知,當P從0.1上升到1.0時,簇間平均時延的總趨勢上升,簇內平均時延(即從簇內節點發送時刻到簇頭開始將其上傳時刻的時間差)的總趨勢下降,這是因為網絡負載越大,簇內時隙越多,休眠期越短,時隙利用率提高,所以簇內時延減少,而由于網絡數據量的增加,簇間傳輸時延增加.在P接近1.0時,簇內時隙越來越不能滿足要求,簇內時延略有上升.

圖4 時延比較分析Fig.4 Mean packet latency

單個節點申請的數據包長度不同時的網絡吞吐量情況如圖5所示,當數據包長為100字節時,數據包較短,網絡負載較輕,隨著P的增加,吞吐量成比例增加.當數據包長為500字節和1 000字節時,隨著P增加,沖突加大,丟包率增加,數據重傳幾率加大,吞吐量上升較慢并最后趨于平緩.

圖5 吞吐量對比分析Fig.5 Throughput

節點休眠比例如圖6所示,從中可知VL-MAC較S-M AC有較大改善.V L-MAC的簇內節點的休眠比例是固定的,因為對于簇內節點,除了申請期和發送時隙外,其他時間均處于休眠狀態,而對于簇頭,隨著P的增加,休眠期比例下降,約從64%下降到40%.

圖6 節點休眠期比例Fig.6 Sleep period percentage

3 結 語

本文結合時分和頻分復用,在網絡分簇的基礎上,提出了一種多信道MAC機制,充分利用物理層的多信道頻率資源,提高網絡吞吐量,減少節點的能耗.利用本文提出的公共信道鏈路和虛擬M IMO機制,可降低Sink節點周圍的干擾和網絡負載,虛擬射頻通過各個不同的信道鏈路接收數據,然后在一個公共的信道匯聚給Sink節點.實驗結果表明, VL-MAC有較低的平均網絡時延,較高的網絡吞吐量,其節點休眠比例也反應出節點的能耗較低.下一步我們將使用成熟可靠的能耗模型來考察算法的能耗,分析Sink節點與虛擬M IMO的傳輸特性,具體化它們之間的通信機制.

[1] JA YA SP,AM ITABHA D,ANIL K G.Primary channel assignm ent based MAC(PCAM)-A m ulti-channelMAC p rotocol for multi-hop wireless netw ork s[C]//Wireless Communications and Netw orking Conferenc,IEEE,A tlanta,USA:2004: 1110-1115.

[2] XUN C,PENG H,QIU-SHENG H,et al.A mu lti-channel MAC p rotocol for w ireless sensor netw orks[C]//Computer and Information Technology,IEEE,Seoul,Korea:2006:224-224.

[3] YEW,HEIDM ANN J,ESTRIN D.M edium access con trol w ith coordinated,adaptive sleeping for wireless sensor netw orks[J].IEEE/ACM Transaction on Netw orking,2004,12 (3):493-506.

[4] KAUSHIK R C,NAGESH N,DAVE C,et al.CMAC-A multi-channel energy efficien t MAC for w ireless sensor netw orks[C]//W ireless Communicationsand Netwo rking Conferen ce,IEEE,Las Vegas,USA:2006:1172-1177.

[5] YOUNISM,BUSHRA S.Efficient distribu tedmedium access arbitration for multi-channel wireless sensor netw orks[C]// InternationalCon ference on Comm unication,IEEE,G lasgow, Scotlard,2007:3666-3671.

[6] H IEY K L,DAN H,TAREK A.A control theory app roach to throughpu t optim ization in mu lti-channel collection sensor netw ork s[C]//Information Processing in Sensor Netw orks, ACM,Canbridge,USA:2007:31-40.

[7] M ILICA D J,GORAN L D.TFM AC:M ulti-channel M AC protocol for w ireless sensor netw orks[C]//Telecommunications in Modern Satellite,Cable and Broadcasting Services, IEEE,Serbia:2007:23-26.

[8] TSUNG T W,KAE H K,CRA IG M,et al.Self-organize multi-channel random selectionm edium access controlp rotocol forw ireless sensor netw ork s[C]//Consumer Communications and Netw orking Conference,IEEE,Las Rogas,USA:2008: 569-570.

[9]OZLEM D I,STEFAN D,PIERRE J,etal.Multi-channel interference m easuremen ts for wireless sensor netw orks[C]// LocalCom puter Netw ork s,IEEE,Tampas,USA:2006:694-701.

[10]CH IH K L,V LADIM IR Z,PRASHANT K.Grid-based access scheduling for mobile data intensive sensor netw orks [C]//M obile Data Management,CCF,Beijing:2008:197-204.

Virtual Link Based M ulti-channelMAC Scheme

LUO Juan?1,LUO Hai-bo1,LIRen-fa1
(1.Co llege of Computer and Communication,H unan Univ,Changsha,H unan 410082,China)

M ulti-channelMAC can fully utilize the frequency resources of PHY layer,which can reduce interference and imp rove throughput Grounded on ZigBee p rotocol architecture.A virtual link based multi-channelMAC(VL-MAC)was proposed,aim ing at clustered network,V L-MAC combines TDMA with FDMA.In VL-MAC,Cluster-heads schedule time-slots achieve non-collision during intra-cluster communication.The clusters in two-cluster hops range use different channel to avoid inter-cluster interference.Inter-cluster communication between the cluster heads is based on virtual link(VL).There are several un-overlapped VLs.VirtualM IMO is also emp loyed to solve severe enorm ous data induced collision problem s.Furthermore,hidden terminal problem is also considered in our algorithm.Simulation results have shown that interference,latency and energy consum ption can be reduced in V L-MAC.

medium access control;m u lti-channel assignment;TDMA;virtual M IMO

TP393

A

1674-2974(2010)12-0077-05 *

2010-05-10

國家自然科學基金資助項目(60903019);高等學校博士點基金資助項目(200805321056);湖南省科技計劃重點資助項目(2009GK 2008);留學回國基金資助項目

羅 娟(1974-),女,湖南株洲人,湖南大學副教授,博士

?通訊聯系人,E-mail:juanluo@hnu.cn