一种基于虚拟链路的多信道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