一种多信道分配机制的研究

一种多信道分配机制的研究

在多段无线mesh网络中，段到端路径应充分利用所有可用的非重复通道，以某种方式实现空间复制率的最大化，并将同时发送的数据传输数据传输到网络区域的最大值。单频多通道多通道mac协议可以在一定程度上解决无线mesh网络的带宽问题。随着无线应用业务的快速发展和用户对高速率的要求，单个高频收发器的多通道mac协议需要频繁更换信道和网络同步。现在，80211硬件设备的转换时间从数百微秒到几分钟不等。频繁的信号变换可以被认为是有效路径的延长。转换期间，路径中的虚拟跳转数可以用来表示为虚拟跳转数。因此，与单个通道场景相比，多正交通道的使用可以显著提高1段的总吞吐量，但它需要增加端到端的延迟。随着无线射频收发器硬件成本的降低和相关技术的发展,在1个节点设备上装备多个射频收发器成为可能,多射频Mesh网络给MAC层协议的设计引进了新的自由度,打破了常规单射频无线设备的关键限制,有望成为未来无线网络实现中解决网络的可扩展性和适用性的关键组成部分.多信道MAC协议包括2方面的问题:接入控制和信道分配问题,其中需要重点研究的是信道分配的问题.Ramachandran等人提出了BFS-CA算法,该算法给所有路由器节点都设置1个相同的默认射频,网关充当了信道分配服务器的角色,信道分配服务器首先根据信道等级选择默认射频信道,然后根据多射频冲突图(multi-radioconflictgraph,MCG)多次执行信道分配算法完成信道分配.Raniwala和Chiueh将网络视为生成树拓扑结构,提出一种基于Hyacinth结构的信道分配算法D-HYA,信道分配通过邻居-射频绑定和射频-信道绑定2个阶段实现.Subramanian等人将信道分配问题转化为对冲突图的点着色问题.集中式的算法要求网络中有1个中心控制节点存在并用来协调网络中的信道分配问题,要求能获取网络全局拓扑和流量分布等信息,这将加重网络的负担,同时会降低网络的可扩展性和可靠性.为了克服集中式算法的缺点,研究者提出了多种分布式的信道分配算法,文献中提出的算法规定只有业务中继节点才会得到传输信道,避免了空闲节点占用大量的信道资源,但存在网络负载重的情况下性能大幅度下降的缺点.Shin等人提出按优先级进行信道分配,射频个数少的节点具有较高的信道分配优先级,算法在保证网络连通的情况下使用了尽可能多的信道,但是在移动的过程中节点需要遍历所有的信道后才可以确认邻居的存在,增加了节点加入网络的开销和时延.Jian等人提出了基于拓扑控制的信道分配算法.信道分配算法CA-OLSR融合在路由协议之内,算法的核心思想就是利用OLSR协议提供的路由控制信息来交换信道信息.Franklin等人提出了一种考虑当前信道分配状态的减小信道切换开销的信道切换算法DeSARA.Pediaditaki和Marina提出了LCAP算法,使用网络节点自学习的思想进行多射频无线Mesh网络中的信道分配,每个节点独立地使用保证节点连通性的概率自适应算法迭代的进行信道分配的学习.在多射频多信道网络中,由于信道分配将不同的邻居绑定到不同的信道上,制约了一些网络技术的可操作性.比如许多控制协议都依赖的广播操作,为保证消息到达网络中每个节点,必须在所有射频上都广播,这会增加传输的冲突概率及节点处理时间,进而增加广播时延和带宽消耗.另外,射频切换信道带来的时延对网络的影响也不可忽视,在切换过程中可能由于节点无法连接而造成隐藏终端问题.针对以上这些问题,本文在考虑节点接收负载的基础上,提出了一种基于混合式信道分配策略的多射频多信道MAC机制(multi-radiomulti-channelMAC,MRMC-MAC).该机制以节点的负载作为信道分配的优先级,考虑2跳范围内的邻居节点的接收负载来进行分布式的信道分配,有效地减少了节点的切换频率,通过使用固定广播信道的方式避免多射频广播,并且解决了多射频多信道环境下的隐藏终端问题.1广播信号的上传本算法基于混合的信道分配机制,有如下前提假设:1)多信道被分成N个正交信道,各信道带宽完全相同,其中1个作为广播控制信道作用,其余作为数据信道使用,广播信道可用来传输广播控制信息、信道预约以及虚拟载波侦听,数据信道进行数据的收发.2)各节点配备M个半双工射频收发器(M<N),其中1个射频收发器绑定到广播信道,用作广播信号的收发以及虚拟载波侦听;另一个射频收发器分配1个固定的信道,作为节点的主接收射频收发器,该固定信道作为节点的默认接收信道;其余所有射频收发器作为可切换射频使用.3)网络中各节点都有1个唯一的ID号,ID号通过对节点物理地址或者网络地址根据一定的算法规则变换得到.1.1广播及控制信息的产生信道分配方案采用混合信道分配机制,主要包括固定射频的信道分配以及动态射频信道的分配.在本多射频信道分配算法中,固定射频分为2个:1个工作在广播信道,用于广播及控制信息的收发;1个工作于节点的默认接收信道,作为节点的主接收射频使用.仅当节点的默认接收信道处于忙碌状态时节点才考虑使用其他数据信道接收数据.除了以上2个固定信道射频外其余所有的射频都作为动态射频使用,可以灵活切换到其他各个信道进行数据的收发.1.1.1加工网络的适应证理想情况下,在同一冲突域中的节点数目小于等于网络中可用正交信道数时,给各个节点分配不同的默认接收信道即可以保证节点可以无冲突地接收数据.而在实际情况下,这种理想情况往往不存在,即在同一冲突域中节点数目大于可用正交信道数时,就必然存在多个节点分享同一个默认接收信道的情况.为了更好地平衡各信道的负载,提升系统的吞吐能力,本算法在网络内部传输流量比较稳定的情况下,将节点的接收负载作为选择默认接收信道的依据.采用优先级选择———通告的方式为节点的主接收射频收发器分配默认接收信道.将节点的接收负载(接收负载指节点的数据接收量,采用统计的方式得出)作为优先级选择参数,节点的接收负载程度越大优先级越高.当接收负载程度相同时,以节点的ID作为优先级参数,ID值越大优先级越高.在默认接收信道分配算法中,各个节点维护两个数据结构:2跳邻居信息表(2-Hopneighborinformation,2_HNI),记录了2跳范围内邻居节点的ID号以及该邻居节点的接收负载值情况;信道使用表(channelusage,CU),记录了各信道被分配的情况.算法包括以下步骤:1)各节点初始化信道使用表.2)各节点与邻居节点通信建立起自己的2跳邻居集.3)各节点与其两跳邻居集内的节点交换ID号以及接收负载值,并填充自己的2跳邻居集信息表.4)各节点将自己的接收负载值与2跳邻居中尚未分配默认接收信道的节点的负载值相比较,在负载值相同的情况下,比较节点ID的大小,如果自己的负载值最大,则选择CU表中负载最小的信道作为自己的默认接收信道,并将选择结果(包括节点ID、接收负载以及选择的信道)发送给2跳邻居中尚未分配默认信道的节点.否则,进入步骤5).5)节点接收2跳邻居集中的节点发来的信道选择情况,并更新自己的CU表,直到所有优先级比自己大的2跳邻居节点都完成了信道分配,该节点再进行自身的默认接收信道的分配,方法同步骤4).将节点的接收负载作为分配默认接收信道的依据,保证了接收负载重的节点优先分配到了负载较小的信道,而接收负载程度较轻的节点间可以共享同一个默认接收信道,从而平衡了各个信道间的负载,减小了通信冲突发生的频率.1.1.2可切换主信道集分配算法除默认接收信道及广播信道外,其余所有信道都可作为节点的可切换信道(switchablechannel,SC)使用,即节点的动态射频可以切换到其中任意1个信道进行通信.当信道数目大于节点射频数目时,切换射频需要频繁的在各个信道之间进行切换,为减少节点射频的切换频率,降低通信延迟,将其中的k(M-2≤k<N-2)个可切换信道作为节点的可切换主信道集(mainswitchablechannelset,MSCS),简称为主信道集(mainchannelset,MCS),即空闲时动态射频停留的信道数.本算法中,我们仅考虑射频数小于信道数的情况.给节点分配可切换信道的主要目的是减少射频的切换次数,从而能降低通信时延.将节点发送数据时使用概率最大的信道作为节点的可切换信道,以最大程度上减少射频切换的次数.在初次进行分配时,以邻居节点的默认接收信道和接收负载情况作为该节点信道切换的依据,即邻居节点的接收负载越大,则节点切换到该邻居节点的默认接收信道的概率越大.初次分配完成后,网络运行过程中还需要根据射频的切换情况周期性地对可切换主信道集进行更新,以降低射频的切换次数.在分配可切换主信道集算法中,每个节点维护1个邻居节点默认接收信道-接收负载值对表(defaultreceivingchannel-receivedload,DRC-RL),节点通过与邻居节点交换默认接收信道和接收负载值来填充DRC-RL表.可切换主信道集分配算法如下:节点首先将主信道集(MCS)置空,接着将邻节点默认接收信道———接收负载值对表(DRC-RL)按接收负载值降序排列,然后依序将负载值高的邻居节点的默认接收信道放入主信道集中,且保证主信道集中的信道不重复且个数不大于k,另外节点本身的默认接收信道不在主信道集中.1.1.3节点可切换主信道更新在完成主信道集的分配后,信道分成了3类分别是2个固定信道、主信道集中的信道和剩余的其他信道,将主信道集中的信道称为主信道,非主信道集中的信道称为非主信道.随着通信的进行,节点射频停留各个信道进行通信的频率出现波动,一种可能的情况是,节点射频切换到非主信道进行通信的频率越来越大,而在主信道中通信的频率越来越小,从而导致节点射频的切换频率越来越大,此时就必须对节点的可切换主信道集进行更新,以降低射频的切换率.在本算法中,节点周期性的对其可切换主道集进行更新,每个节点维护1个信道使用次数表(其中不包括节点的默认接收信道以及广播信道),对各个信道的通信次数进行记数,当某个非主信道的使用次数大于某个主信道使用次数超过一个设定的阈值后,就进行主信道集的更新,使用次数多的非主信道替换使用次数少的主信道.更新完毕后,将信道使用次数表清零.并将结果告之其邻居节点.1.2共同的闲置信道在整个运行过程中,节点维护了3个数据结构:可用信道表(usablechannel,UC)、邻节点默认接收信道表以及邻节点主信道集表.源节点在与目的节点通信前,首先查看目的节点的默认接收信道是否在自己的可用信道表中,如果在,则说明当前目的节点的默认接收信道空闲,源节点与目的节点按常规RTS?CTS机制通信.如果目的节点的默认接收信道不在源节点的可用信道列表中,则说明当前不能使用目的节点的默认接收信道进行通信,源节点必须与目的节点协商一个共同的空闲信道来完成通信过程.源节点首先在控制信道给目的节点发送CNI(channelnegotiationinformation)帧,在该帧中携带经过重排序后的空闲信道表,其中空闲信道表按照主信道、默认接收信道、非主信道的顺序排序,从而保证目的节点在接收到CNI帧后,能够按照上面的顺序选择共同的空闲信道.按照这个顺序进行信道排序的原因如下:1)将主信道放在默认接收信道前,在选择了主信道为公共的空闲信道后,源节点可以继续用默认接收信道接收其他节点的通信请求;2)将非主信道放在最后面,减小将非主信道选为公共空间信道的可能,从而降低了源节点射频切换的次数.目的节点在控制信道上收到发给自己的CNI帧后,就对照自己的信道空闲表,依序在该CNI帧中携带的源节点空闲表中寻找共同的空闲信道,在寻找到第1个共同空闲信道后向源节点反馈CRI(channelresponseinformation)消息,告之协商的共同空闲信道.如果在规定的时间内接收到了目的节点反馈的CRI消息,源节点就以协商的信道作为通信的数据信道与目的节点进行协商通信.本算法同时支持广播数据通信,广播数据通信在广播控制信道进行,在广播数据通信过程中,正在进行的数据通信继续进行,不受影响,而在此期间新的数据协商过程将暂停,直到此轮广播通信的结束.2数据信道状态多信道隐藏终端问题主要是由于通信节点和干扰节点之间不知道对方的工作信道造成的,即节点不知道各个信道的工作状态.在单信道协议中,通常采用载波监听的方式来获取信道状态,以降低通信的碰撞概率,但是在多信道中,如果也采取这种方式,节点就必须频繁的在各个信道间切换,必然会增加网络延迟.因此,在MRMC-MAC协议中使用虚拟载波侦听机制来解决多信道中的隐终端问题.虚拟载波侦听是通过控制信息来得知信道的使用情况,是指每个节点在缓冲区中建立1个数据信道状态(channelstate,CS)表,在该表中记录当前被占用的数据信道号、信道占用的起始时间以及该信道占用的持续时间.节点通过读取数据信道状态表而获得当前数据信道的状态.源节点在与目的节点协商数据信道之前,先在控制信道上广播1个RTS帧,由上文可知,该帧包含了本次通信使用的信道号,以及通信持续时间,以此来通知与发送节点相邻的节点更新数据状态表.目的节点在反馈的CTS帧中也包含了通信使用的信道号以及占用的持续时间,以此来通知与接收节点相邻的节点更新数据信道状态表.对于处于空闲状态的节点,每次收到RTS帧或CTS帧后,就更新数据信道状态表.数据信道状态表如表1所示:节点根据信道占用的起始时刻及信道占用的持续时间判定某个信道的状态,并随时更新数据信道状态表以及空闲信道表,将空闲的信道从信道状态表中删除,添加到空闲信道表中.数据信道状态的具体判定方法为:若当前时刻为t,通过查找数据信道状态表得知:某一数据信道号为Chk的信道占用起始时刻为Stk,信道占用持续时间为Durak,则:当t-Stk<Durak时,该信道忙;当t-Stk>Durak时,该信道空闲.在MRMC-MAC协议中,节点首先进行默认接收信道分配以及可切换主信道集的分配,并设定主信道集的更新周期.在节点空闲状态时,节点的控制收发器(绑定在控制信道的射频收发器)一直监听控制信道并进行虚拟载波侦听,当在控制信道接收到RTS或CTS信号,提取其中的信道使用信息更新节点自身的数据信道状态表,根据信道状态表判定各个信道的使用情况,并随时更新可用信道表.3无线节点网络配置仿真使用NCTUns5.0仿真平台对MRMC-MAC进行性能仿真,分析信道数目及射频数目对网络吞吐量的影响,并与基于局部干扰最优的贪婪多信道分配算法进行比较.在NCTUns5.0中为每个节点配置多个基于802.11b以及802.11a标准的射频卡,其中802.11b拥有3个非重叠信道,802.11a拥有12个非重叠信道(实验中使用了其中的2个非重叠信道).在具体的实验过程中,多射频无线节点优先配置802.11b标准的射频卡,即仅当信道数目大于3的情况下,多射频节点才配置使用802.11a标准的射频卡.在仿真中,使用了节点均匀分布的网状拓扑结构,如图1所示.25个节点均匀分布在800m×800m的范围内,相邻节点间的距离为200m,节点的通信范围为250m.在本文的仿真中,外围4个顶角节点1,5,21,25同时持续向中间节点13发送数据,通过给网络配置不同的道数以及为无线节点配置不同的射频接口数来考察信道数目及射频接口数对网络性能的影响.同时在该特定的网络场景下,比较不同的信道分配算法对于网络吞吐量以及网络丢包率的影响.仿真参数如表2所示.MAC层的吞吐量是描述MAC协议性能的重要参数之一,表示网络传输效率,可以反映网络性能.下面就不同情况下MAC层的吞吐量来分析仿真结果.1多信道分配算法在每个仿真场景中,每个节点都已经配置1个绑定到默认广播信道的固定信道网卡,其他待分配网卡和信道的分配情况如下:(1)在网络中使用单个待分配信道,每个节点配置1个待分配信道的网卡,每个网卡上分配同1个信道;(2)在网络中使用多信道,每个节点配2个待分配信道网卡,在这些网卡上分配多个信道,待分配信道数为2;(3)在网络中使用多信道,每个节点配置2个待分配信道的网卡,在这些网卡上分配多个信道,信道数为3,使用本文提出MRMC-MAC协议中的多信道分配算法给各个网卡分配信道;(4)在网络中使用多信道,每个节点配置2个待分配信道的网卡,在这些网卡上分配多个信道,信道数为5,使用本文提出MRMC-MAC协议中的多信道分配算法给各个网卡分配信道.仿真结果如图2所示,图中CN为可分配的信道数目.从图2中可以看出,随着信道数的增加,MAC层吞吐量随之增大.相较于单信道网络,使用多信道网络性能有了很大的提高.因为在多信道网络中,使用不同信道的链路可以同时通信,因此相较于单信道网络而言,多信道网络可以增加网络的吞吐量.在实验结果中可以看出,分配信道数从2增加到3时吞吐量的增加明显降低.这是因为MAC层吞吐量并不是随着信道数目的增加而一直增加的,当信道数目增加到一定程度时,MAC层性能的提高幅度较小.2多信道分配算法仿真在考察射频卡数目对网络容量影响的实验中,我们将网络正交信道数目固定设置为5,另外,从实际应用的角度考虑,将网络场景分别设置为取1~4个待分配信道射频卡的情况(每个节点默认已经配置一个绑定到默认广播信道的射频卡).不考虑射频卡数目过大的情况,因为在实际的应用中,节点的射频卡数目比较是有限的.采用本文提出的多信道分配算法给各个网卡分配信道.仿真结果如图3所示,图中RN为待分配信道射频卡的数目.从图3中可以看出,随着射频卡数目的增加,MAC层吞吐量随之增加.当待分配信道的射频卡数目从1增加到2时,MAC层吞吐量有较大的提升,这是因为在多信道网络中节点配置多个射频卡,理论上可以实现节点的全双工通信,相较于传统的半双工节点来说,吞吐量将会加倍.但