一种基于链路层的信道分配机制

一种基于链路层的信道分配机制

1非基础结构无线网络在过去10年中，关于支持多发送和多收集网络的技术研究变得越来越重要。提升网络容量最简单的办法就是使用频分复用技术,正如802.11标准就规定了相应硬件必须支持多信道通信,这样使得在同一个区域中能有多个网络同时传输。但是801.11标准中只考虑了提升基础架构(infrastructure)无线网络的网络流量,该标准规定不同的相邻的接入点(AP)使用不同的信道,从而使用户访问自己需要的接入点(AP)时不会受到其他接入点的干扰。但是非基础结构的无线网络并不能从中受益,802.11标准规定在同一个非基础结构无线网络(e.g.Ad-Hoc)中的节点只能使用同一个信道,甚至在某些节点相互之间都不在通信范围的情况下。而如果构建基于802.11标准的无线自组织网络必须利用非基础结构无线网络,所以引入一种合理的信道分配机制十分必要。本文在分析了国内外众多的基于802.11标准的信道分配方法的利弊之后提出的一种全新的基于链路层的信道分配机制。该机制包括了一个全新的可以提高网络容量的协议,一中新的优化同步技术,还有一种部分同步的技术。该方法独立于802.11标准,既不需要对硬件进行任何修改,也能应用到基于其他标准的无线自组织网络中,具有很高的实用价值。本文首先说明了设计该机制的背景和动机,然后探讨了具体的算法内容,最后通过仿真同现有方法进行了直接的对比以说明该机制的有效性。2“cts包”信号强制在本文中,由于篇幅限制把讨论的范围缩小到广为人知的IEEE802.11分布式协调(DCF)协议。从阐述该协议的有关细节开始。802.11推荐使用RTS和CTS机制来对介质访问进行控制。发送者如果期望发送一个包,必须首先确认传输介质空闲且大于传输帧空闲(DIFS),然后发送者广播一个RTS包并期待保留对介质的访问权。如果潜在接收者收到RTS包就会返回一个CTS包,但是这个CTS包会导致该接收者相邻的节点就会在这个时间段中不会尝试传输任何一个数据包。如果出现RTS失败或者冲突的情况,就会导致网络性能的大幅下降。更多细节请参考文献[8]。802.11标准把可用的频谱资源分配成了多个正交的信道。802.11b/g在2.4G的频段上拥有11个信道,其中三个是完全不相交的独立信道。而802.11a在5G的频段中拥有多达13个完全不相交的信道。数据包在这些独立信道中同时传输是完全不会相互干扰的。如果只使用单一信道传输数据大幅限制了无线网络的传输容量。如图1直观地显示了单一信道传输的缺陷。如果当节点3给节点4发送信息的时候在同一范围内的节点1与节点2及节点5和节点6均不能正常通信,虽然有足够的信道资源可以利用如图1。3频率筛选3.1仿真多跳环境本机制利用一种叫做优化同步的频率分集的办法。本机制的目的是制造一种节点间的共识,各个节点相互了解其他节点的跳频时间序列,然后允许任意节点在任意时间修改该时间序列。如果节点A要发送消息给节点B,而且A知道B的调频时间序列,A就能通过修正自己的调频时序列从而正常并快速地发送到B。但是在如果没有达成共识A并不知道B的调频时间序列,或者A掌握的关于吧B的时间序列已经过期,这种情况下在A了解B新的跳频时间序列以前消息发送就会延迟。设计本机制就是为了在各个节点间达成一种更好的公认,当节点间通信情况发生变化的频率(例如新建一个网络流时)小于跳频时间序列的更新频率时。因为跳频时间序列的更新只需要10微秒的时间,在达成时间序列共识后发送消息的性能将大幅增加。该办法在许多形式的无线网络方案均有效,并不局限于802.11协议。性能的具体提升,本文将在仿真部分用图表的形式具体表达。本机制的设计不光要考虑单跳的网络环境,而且多跳环境也是必须考虑的。本文提出一种部分同步的技术来适应多跳的环境。当节点B可以用一半的时间使用同节点A达成一致的跳频时间序列,然后用另一半的时间与节点C同步,这在当A要同C有效通信时是必要的。尽管这样的情况需要B不断地改变自己的跳频时间序列以不断地适应节点A和节点C,可以想象当有4个节点都要通过B中转的时候节点B的同步难度,本文将在下面的章节里具体讨论这样的情况。3.2无线局域网网络的3gs本文假设所有的节点都是使用IEEE802.11a,虽然本机制可以适用于所有的802.11系列,但是802.11a拥有13个完全独立的信道能更明显地显示该机制的优越性。本文还假设了无线网卡都具有信道切换的能力,半双工且只有单一信道发送能力。(大多数真实硬件能力与假设相同)3.3最大的调度控制策略本机制对每一个邻居节点维护一个FIFO队列。该队列保证了更高层协议的发送顺序,同时计算了邻居节点可到达性的优先顺序。最初,针对所有邻居等待发送的数据包都同等对待。当一个发送到特定邻居节点失败后开始修正邻居节点可到达性的优先性。由于本机制经常使用不同的信道,所以广播包在一个时间间隙里面只能发送到在物理通信范围内的节点,除了正好多个远距离节点同时工作在一个信道上的情况。这就会导致想DSR一样的依赖大量广播的路由算法性能的下降。本机制由于使用了时间间隙发送技术,所以要求完全同步的一些算法也不适用于本机制。虽然会造成上述的部分性能下降,但是本机制并不影响大多数算法的运行,而且就算基于一些不利的算法都能显著地提高网络总流量。如果一个节点给邻居节点发送一个RTS在某个信道上,但是邻居节点在该信道并不空闲,所以无法回应CTS,但是如果该RTS包在其他信道上发送,可能邻居节点就能良好地回应CTS,这样就导致了该发送推迟。为了解决该问题,一开始就保留这个数据包在包队列里,只有当所有对于某一个节点的包都失败的时候才丢弃该包。因为针对一个节点的所有包会通过各个信道发送,如果都不能发送就确实说明该节点无法通信,除此之外包都可以顺利地到达目的节点。以上说明的包的调度策略能简单地实现,在大多数情况下有良好的性能表现。只有一个潜在的缺陷,就是某节点故障后可能导致大量浪费的发送往该节点RTS包。特别是在多信道的情况下,已经超过了802.11建议的重发次数,但是经过仿真和计数表明这样的故障对网络造成的代价很小。3.4动态时间间隙的切换现在开始讨论本文的最主要部分信道调度问题。开始从描述产生信道调度所用到的数据结构开始。然后我们描述了节点应用自己的时间序列与其他节点通信的机制,最后介绍了节点间相互更新和改变时间序列的策略。时间序列必须获取一个给定节点的将来的调频计划,显然这样会导致这个时间序列相当冗长。不过,提出了一种紧凑的时间序列构建规则去更新所需调频序列,特别是当假设有序对N(Xi,Ai),Xi表示信道号取值在[0,12](分别表示使用802.11a中提供的0-12号不相交的信道),Ai表示我们设定的一个种子数在[1,12]的闭区间中任取的一个整数。有集合S包含了四个这样的有序对时。实验表明四个有序对就足以产生一个很好的结果。每一个节点都遍历在时间序列里的所有信道,在每一个新的时间间隙中切换到时间序列里对应的信道。然后节点依照刚才的种子数Ai,对每一个跳频时间序列增加一个新的时间间隙及对应的信道使用号。算法如下:然后不断重复该过程。引入了一个附加的时间间隙来避免出现逻辑分离。节点完成在全部4个时间间隙内对每一个信道的迭代算法以后,将切换到一个部分时间间隙,它的长度和时间间隙长度是由Xparity=a1决定的。在这个部分时间间隙里面将加入一种类似于奇偶校验的机制,在数据流尾部添加一些错误修正编码。包括验证的整个时间间隙信道分配循环大约需要530ms。在图2中,展示了一种在两个节点和三个可用信道中的可行的信道调度机制。节点A和节点B已经相互同步它们的调频时间序列,同时也添加了上面提到的附加的时间间隙用来修正错误。信道时间序列的每一个小格决定了每一个时间间隙所使用的信道号。每一次访问的信道都是通过本文已经描述过的基于种子的算法对信道时间序列进行更新。比如,A节点初始是由(信道,种子)=(1,2)开始的,当进入下一个时间小格,使用的信道就会由加入种子数然后除以3再取余(3代表3个可用信道),这样的话信道就会分配到(1+2)mod3=0。节点切换到下一个确定的调频时间序列只需要很短的时间,但是如果这个切换在节点正在发送或者接收数据包的时候就会被推迟,直到传输完毕ACK包收到之后切换。节点接收通过周期性地广播种子信息来相互了解其他节点的调频时间序列。使用802.11的LCFH的空余数据位置来嵌入需要的信息。节点同样通过和其他节点通信时产生的错误和失败来调整自己的调频时间序列。在任何时间,只要节点对未知时间序列的节点发送出的RTS没有收到回应,就会对针对该目标节点的跳频时间序列进行修改,直到了解确切的目标节点跳频时间序列为止。当一个节点更新了自己的调频时间序列,他必须通知其他节点知晓。这里使用上文描述过的附加时间间隙来传达该更改信息,同样使用802.11LCFH空余数据未知携带相关信息,所以该机制对性能影响很小。在动态调度信道时,该机制还存在一定的问题,比如使用这个简单的调度办法就是节点不断的检验这个包序列,以保证总是最大的概率发送最多的数据包。但是这个想法忽略了节点对接收包的兴趣和信道的拥挤。比如一个节点(B)忽略它对接收包的需求(见图3),A节点与B节点同步,B又与C同步,这样的话A就无法与B同步。这样B就只能发送自己需要发送的包而无法收到自己需要接收的包。4动态使用信道在讨论了本机制的优势和不足以后用仿真图直观地展示应用本机制的结果。使用的QualNet仿真软件,对比原始的802.11a协议和本机制的传输性能(802.11a拥有13个不相交的信道,