无线网状网中的防干扰频道分配

1、无线网状网中的防干扰频道分配Krishna N. Ramachandran, Elizabeth M. Belding,Kevin C. Almeroth, Milind M. Buddhikot摘要通过安装无线网路由器使多频信号变为无同频信号来达到缓和无线网状网中的容量问题。 然而，频道分配变为了挑战因为无线网多了会导致同频干扰。 其结果相反会增加干扰影响性能。本文就多信道无线网状网络的干扰问题通过防干扰频道分配的方法提出了解决办法和方案。该解决方案通过合理的分配无线频道最大程度地减小了无线网之间的干扰。该方案利用了新的干扰估计技术手段并且付诸实施于无线中的每个路由器。 通过冲突图模型及多信

2、道冲突图的拓展来构造路由器之间的干扰模型。我们通过 IEEE802.11 协议实验平台来验证方案的可行性。 我们同时报告了大量实验模拟仿真的效果。 在多频取样上，我们解决方案对比于静态频道分配增加了百分之四十的取样。第一章 .引言典型的静态多跳无线网络， 又称无线网状网络， 其部署的路由器仅利用了 IEEE802.11 协议无线电广播。 IEEE802.11 无线广播是典型的单频道广播。因此，由于无线网的半双工特性，单信道网状无线网络通信的容量受到严重地衰减。幸运的是，IEEE802.11 物理层协议允许多个不重复频段的频道同时运行工作。例如， 2.4 兆赫兹带宽的频带内的 3 个不重复频段的

3、频道能够同时工作。 IEEE802.11a 协议最高允许 5.0 兆赫兹带宽的频带内划分为 12 个不重复频段的频道。通过在无线网中布置频率路由器和为不重复频道分配无线接收机来划分设置不同频段的频道， 这些路由器可以同时工作并且彼此之间的干扰能够最小化。 从而，能够提升无线网状网的能力。通过多个无线接收机对应多个路由器的策略， 使得无线电接收机的数量与正交频道的数量相等。 由于数量众多的不同频段的频道， 这个策略经济上代价过高。 而且，生产路由器的小型嵌入式系统仅仅能够提供数量有限的无线电接收机。 因此，在一个无线网状路由器上划分所有的不重复频段的频道仍然是不可行的。这样，为每个无线网状路由器

4、划分频道的问题变成了按无线电接收机划分频道的问题。简单的技术是用静态频道划分法。然而，静态划分对于基于 IEEE802.11b 标准的无线局域网会产生爆炸性的结果，可能导致网状网频道被重复划分。本文提及了频道划分的问题以及特别研究了无线网状网频道的动态划分。我们主要阐述了抗干扰频道划分算法和以及划分频道的方案，旨在改进无线网状网的容量来更有效的利用不重复频段的频道。 这个算法合理地为网状无线电接收机选择频道从而把无线网状网中的干扰以及不同无线网状之间的干扰降低到最小。 每个网状路由器利用新的干扰估计技术来检测邻近无线网产生的干扰的等级。 这个算法是对冲突图模型和多频冲突图模型的拓展， 从而构造

5、无线网状网中的多频路由器间干扰的模型。 多频冲突图被用来和频道分配的干扰估计相结合从而为无线电接收机分配频道。一个潜在的问题是动态频道分配会导致网络拓扑结构的改变。 拓扑结构的改变会导致次佳路由选择以及由于节点错误所引起的网络分隔。推荐的解决办法是授权每个网状路由器的无线电接收机在一个默认频道上工作。另外一个潜在的问题是当网状无线电接收机被重新配置不同频率时，频道分配会导致流干扰。为了防止流干扰，每个网状路由器间必须定向连接。这项技术重新定向直到频道分配成功。我们通过网路模拟器来仿真实验我们拟定解决方案的可行性。我们利用链路状态路由优化方法和加权累积预期传输来进行路由选择。我们通过多信道IEE

6、E802.11b 协议平台来验证解决方案的可行性。（一）研究贡献就我们掌握的知识，我们首先解决了受干扰的多重无线网中网状无线网的频道的静态分配。 拟定解决方案的首要目标是使用当前可用的无线电设备来实现。 我们的工作与几个推荐的解决方案不同之处在于需要专业的不可用的无线电设备或者网络知识。特别地，本文的贡献有如下几点:·通过静态，防干扰的频道分配算法将无线网状网和多重无线网间的干扰最小化。·利用多信道冲突图，冲突图模型的拓展来构造无线网状网中多频路由器间的干扰模型。·新的干扰估计计划，用路由器来估计他们邻近区域的干扰等级。·定向连接方案防止了频道分配时的流

7、破坏。·对于不同的干扰等级，通过标准根据经验主义测量方法来实验研究展现改进手段。（二）本文概述本文剩余章节组织如下：第二章讨论了频道分配对网络结构的影响。第三章我们明确表述了频道分配问题。第四章描述了我们的干扰估计技术和多频冲突图模型。第五章详细讲述了频道分配算法。第二章频道分配和网络拓扑结构在多频网状网络中，无线电接收机的频道分配能改变网络拓扑结构。图 1(a)是四节点拓扑结构，节点C 配有 3 无线电接收机，其余三个节点每个各有一个。每个连接线上标有其频道数量。图1（a）说明了所有无线电接收机都调成一个频道时的拓扑结构。图 1（b）说明乐频道分配后的网络拓扑结构的变化。网络拓扑结

8、构的变化有三个主要的缺点。首先，随之产生的节点错误很可能引起网络被隔断。结果，网络的部分不能通信，导致流破坏（通信中断）。这个现象在图 1（c）中可以看到。当节点连接错误时，这四个节点的网络被隔离成三个不多的部分。 这个网络的重新连接需要复杂的同步同时性计划付诸于每个网状路由器。图 1其次，拓扑结构的改变能够导致两个节点间次佳的路由选择，基于度量标准方面，如吞吐率，延迟，可靠性。再次通过图 1 来说明怎样发生这种情况。节点 A 能通过一条路径直接和节点 B 通信。频道分配后， A 点和 B 点只有通过二次路径（经过 C）才能相互通信，如图 1（b）。高跳数的路径选择不是我们所期望的有以下三个原

9、因：（ 1）更长的，频率多样化的路径相对于短路径经常会发生通信错误。（ 2）通信流量路径的路径数越多其干扰自然越厉害。 （3）更长的路径更有可能发生通信失败。 需要注释的是， 我们不能够肯定更长的路径会比短路径差，那是因为路径的选择肯定会遇到很多因素如交通路线，节点分布，无线电特性和地理环境等。因此，我们在这里强调：很难在实践中精确地预测频道分配的变化和网络拓扑结构变化能否产生适宜的结果。第三个网络拓扑结构变化的缺点是：可能影响当前的信息流。例如，让我们假设图 1（b）的 CD 连线被分配一个新的频道。这个频道分配必须精确地协调 ;另外，当线路上一个无线电接收机变换到这个新的频率而第二个无线电

10、接收机由于控制信息的丢失和延迟没有变换到这个频率时，会发生错误。因此，当频道分配的时候由节点 D 到网络其余部分的信息流会在变换频率时被损坏。 在实际中克服这些状况很难，因为无线电接收机的配置需要在频道分配期间网状路由器之间同时合作。因为这些由于网络拓扑结构变化产生的缺陷，我们提倡不改变网络拓扑结构。我们授权将所有网状网中的路由器将他们的无线电接收器的其中一个指定为无线电接入口。 这个指定的无线电接收器有着同样地物理层技术，是符合 802.11a协议或者 802.11b或者 802.11g，通过网状网调整为一个普通的频道。 这个指定的频道兼顾控制通信及数据通信。这个策略有几个好处。首先，它防止

11、了网络拓扑结构的变化因为所有路由器可以通过这个指定的无线电接收入口彼此连接和断开。 其次，它克服节点的失效变得简单了由于一个路由器能绕过一个失效的节点选择不同的路径通信。 另外，目前路由协议除了频率划分外有别的选择权，如果它比从频率特性划分上有更好地效果。 除此之外还有一个优势，信息流通过这个指定的无线电接收机可以重新传送直到频道分配完成，这样，就能防止频道分配时的信息流损坏。第三章 .问题陈述我们在本文中提及的频道分配算法是为无线网状网设计的。该网络中的路由器是固定的。然而，用户设备，如笔记本电脑，掌上电脑是移动的。诸如此类和路由器相连接的设备也同样起着作为无线接入点的功能。图 2 多信道无

12、线网状网络结构图 2 说明我们的多信道网状网络的模型。 在我们的模型中， 网状路由器被假象配有多个 IEEE802.11 协议的接收机，如 802.11a或者802.11b或者 802.11g。这些路由器不需要配有同样数量的无线接收机而且不要所有三种类型的接收机。 考虑到每个网状网络的接收机的数量，我们把路由器分为两类：（1）多信道网状路由器。（2）单信道网状路由器。我们授权每个网络中的多信道网状路由器及单信道网状路由器配有一台无线接收机， 称为默认接收机，它们都有相同的物理层，如 802.11b，并且都被调整为相同的频道，如第二章中所详述的。网络中至少有一个路由器被指定为网关。 这些网关与外

13、网是可连接的。为了把频道分配解释的简单明白，我们假设只存在一个网关。无线接入点提供了用户设备和路由器的可连接性。多数网状网络通信是从用户端到网关之间的通信，或者从网关到用户端。 这种通信方式是无线网状网中典型部署。 由于这种通信方式是与网关斜交的， 由信息流的路径可能会形成一个树状结构， 其中网关是树的根， 用户设备是叶子。信息流会在网关邻近的路由器上聚集。因此，为了改进整个网络的通信能力，最好在网关附近布置多信道网状路由器从而提升网状网络的区域的利用率。 为了改善网络的性能， 减少仪器的开支以及符合逻辑的约束，周密的网络布置很重要。图中点划线的地方代表了多信道网状路由器间调整为无重叠频道的部

14、分。在我们的例子中，使用了五个这样的频道。第六个频道用实线标注，是默认频道。与网关位置重叠的频道分配服务器，起着给接收机分配频道的作用。在分配频道时，频道分配服务器必须达到如下目标：·使网状路由器间的干扰最小化:实现需要三个次目标。首先，频道分配服务器必须满足两个路由器间存在一条线路的约束， 这两个路由器上的终端接收机必须被分配给一个普通频道。 其次，直接通信范围的线路必须被调整为不重叠频道。 另外，由于无线网状网中的树状通信图，频道分配的优先权应该首先给从网关起始的路线然后给网络边缘的路线。·使无线网状网之间的干扰最小化：为了达到这个目标，频道分配路由器必须定期检测网状网

15、络重叠造成的干扰的数量。 干扰等级由独立的网状路由器检测。 为了使频道受到来自外部接收机的干扰程度最小，频道分配路由器必须重置频道。陈述了信道分配算法的目标后， 我们接下来阐述干扰估计的细节及描述干扰建模技术。第四章干扰分析及建模本章节陈述了干扰分析的步骤。补充的细节部分在第五章中。本章也介绍多信道冲突图模型。（一）干扰分析干扰分析的目的是定期的检测每个网状路由器环境下干扰等级。然而，精确的测量方法是个挑战需要昂贵的硬件开支。取而代之的是， 用近似法，我们依靠每个频道的干扰接收机的数量作为干扰分析， 这些频道由路由器支持。 一个干扰接收机被定义为一个同时工作的接收机， 该接收机对路由器是可见的

16、而对网状网络来说是外置的。可见的接收机的数据包是按帧检查序列传送的因此会被无误的接收。我们假设频道分配路由器与网络内部的接收机的路由器通信。通信的内容由一些列网址和详尽的网络中的介质访问地址组成。分析步骤要注意的一点是： 这些接收机是在一个分析路由器的传感范围内但是不在接收范围内， 不会算在干扰分析内。 这是因为由无线接收机传送的数据包不能通过路由器帧检查序列的校验。 然而，传感接收机仍然会影响干扰到路由器。 我们的干扰分析技术不考虑接收机有两个原因。首先，最近研究表明现在的 IEEE802.11 介质访问在传感原理上实现的过度保守了并且干扰接收器经常受到不利的评价。因此，对于多个传感无线接收

17、机，也许并不像先前所理解的那样，接收机相邻就会引起性能不佳。 其次，就算我们真地把传感器无线接收机容纳进我们的干扰分析解决办法中， 也不可能决定能够使用这类标准硬件的接收机因为目前软件无法识别它们。 我们被建议用专门的软件来克服。这种软件可能在不久的将来会有并且投入市场。然而，仅有这些数量的干扰接收机的测量方法不充分因为并不能表明受干扰接收机影响的通信量。 例如，两个频道能有同样数量的干扰接收机但是其中一个频道相对于另一个可能被它的干扰接收机严重的占用。因此， 另外，每个网状路由器也可评估被干扰接收机占用的频道带宽。干扰评估步骤如下： 一个网状路由器通过每个支持的物理层规范设置一个接收机，从而

18、在每一段持续的短时间内从每个支持的频道上捕获数据包。路由器利用捕获的数据包来检测干扰接收机的数量和每秒频道利用率。干扰接收机的数量与网络外介质访问控制点的数量相同。受干扰机的影响的每个频道的利用率通过计算捕获的数据结构得到，其中包括数据包的大小和数据包传输的速度。频道利用率的计算应该同样考虑介质访问控制层的系统开销（在计算机网络的帧结构中，除了有用数据以外，还有很多控制信息，这些控制信息用来保证通信的完成。这些控制信息被称作系统开销。 ）在实施中，我们将数据捕获的持续时间设置为三秒。三秒的时间设置考虑到了每秒测量的平均变化量并且对于干扰分析的快速计算足够短暂。每个网状路由器衍生出两类频道等级排

19、列。第一类等级排列根据干扰接收机的增加数量。另外一类是根据增加的频道利用率。路由器然后通过单个级别的平均数来排列级别最终合并两类频道等级排列。最终的划分结果被送给频道分配服务器。图 3（ a）一个简单的网络拓扑结构G（ b）冲突图F（ c）多信道冲突图F（二）干扰模型冲突图广泛地被用来模拟蜂窝无线网络的干扰模型。一个网状网路的冲突图定义如下：图 G 具有节点类似于网络中的路由器，节点间的边线类似于无线线路。 一个冲突图 F，有与 G 图一致的节点并且节点间有连线，只要 F 图中的两个节点表示 G 中的线路，并且彼此干扰。作为冲突图的例子，图 3（a）展示了具有四个节点的网络拓扑结构图。图中的每

20、个节点标有节点名称和接收机的数量。 图 3（b）展示了这种冲突图。乍一看，网状网络线路的频道分配问题变成了冲突图顶点着色的问题。然而，顶点着色不能直接分配频道因为它没有说明解释其中的限制约束“一个路由器可分配的频道数量必须与它的接收机的数量相同”。举例来说明情况，我们假设图 3（b）冲突图中的四个顶点根据顶点着色法来给每个顶点分配三个不同的频道。 意思是每个顶点的两个接收机按照顶点的频率工作。这意味着这个网络中的节点C 在三个不同的频道上工作，这是不可能的因为它只有两台接收机。冲突图不能够直接构造具有多个无线接收机的路由器的模型。因此，我们扩展冲突图来构造多信道路由器的模型。在这个扩展的模型（

21、多信道冲突图） 中，我们像原始的冲突图那样通过接收机作为顶点而不是路由器作为顶点来描绘顶点间的边线。为了创建多信道冲突图F，我们首先在 G 中以每个接收机作为顶点而不是像G 中以路由器代表顶点。因此，在上诉的例子中，节点C 由 G中的两个顶点代替而不像 G 中只有一个顶点， G中两个顶点对应着两个接收机。G图中的边线是处于接收机间而G 图中的边线是路由器间连接的。 F图中的顶点代替 G图中的每条连线。图F中顶点间的连线的产生如同原始冲突图那样。 例如，图 3（c）展示了图 3（a）的多信道的干扰图。在图中，每个顶点都标记着用接收机代替顶点。例如，顶点（ A-1：C-2）代表了路由器 A 的第一

22、台接收机和路由器 C 的第二台接收机之间的连接。当用顶点着色法给多信道冲突图着色时，我们利用了一条重要的限制规定：在给多信道冲突图中所有顶点着色时，所用未着色的顶点包含了已着色且调整了位置的顶点的接收机。例如，对图3（c）中的顶点（ A-1 ：C-2）着色后，冲突图中所用包含 A-1 或者 C-2 的顶点都应该移开。这是为了保证无线网状网中每个接收机都只有一个频道。第五章频道分配算法（一）综述网状网络的频道分配问题与列表染色问题相似，列表染色定义如下：已知图 G=（V,E），对于 V 中的每个 v，一列有色的 L （v），能否构造固定的根据 G 染色的顶点染色法以至于每个顶点 v 都有 L（v

23、）中的一种颜色？这个列表染色问题已经解决了。 因此，我们依靠和其相近的算法来解决频道分配的问题。 我们的算法成为 “优先搜索频道分配法”，用优先搜索来为网状接收机分配频道。搜索从网关节点开始的连线。优先搜索的基本原理是直观的：通过优先搜索，从网关开始的线路具有频道分配的优先权然后至网络的边缘优先性递减。在用优先搜索频道分配法之前，频道分配服务器从网状路由器获取干扰评估。然后为默认接受机选择一个频道。 这个默认频道的选择可以将网络间的干扰最小化。 频道分配服务器为网中不是默认的接收机构建多信道冲突图。 我们用一个两跳干扰模型来构建多信道冲突图。在这个模型中，网中的两条线路是干扰的如果他们有一个普

24、通的路由器或者间隔一跳分开的。 Padhye etal建议用经验主义技术来防护网中受干扰的线路。 这个技术更精确因为其经验主义的特性， 但是需要很长时间完成。我们研究来改进该技术的速度。与此同时，我们在工作中利用两跳模型。构造好多信道冲突图之后，频道分配服务器利用优先搜索频道分配法为非默认接收机选择频道。一旦网状接收器的频道选择好，频道分配服务器会指示路由器设置它们的接收机变为新的频道。为了在本章更清楚地解释频道选择步骤，我们假设网状接收机被同时重置。我们会在第五章 D 节中说明上述假设，我们会陈述重置频道的特殊协议的细节部分。默认频道选择步骤会在优先选择频道分配法之后详述。频道分配服务器定期

25、地调用上述的频道选择步骤来改变网络中的干扰特性。本章以调用周期和其蕴含式的讨论结束。（二）默认频道选择频道分配服务器用频道序列c 来为整个网络 Rc 选择默认频道。R c 计算如下：nii1 Rank cRcn这里路由器的数量是 n， Rankic 是路由器 c 的频道序列。默认频道被选择为 R c 最小值的频道。标准时把受干扰最小的频道作为默认频道。这个默认频道可以使干扰最小化。（三） .非默认频道选择在这个阶段，频道分配服务器用所有相邻的路由器的信息来构建多信道冲突图。相邻的信息包括所有路由器接收机支持的频道的相邻识别，延迟，干扰估计。第五章C 中详述了路由器延迟的计算。频道分配服务器与多

26、信道冲突图中的每个顶点相关， 一个频道序列由单独频道序列的平均数衍生的。 这个平均数很重要因为多信道冲突图中的每个定点的频道分配应当考虑终端接收机的性能。对于多信道冲突图的所有顶点，频道分配服务器计算他们距离网关的长度。这个距离是两个接收机距离网关的平均距离。接收机的距离通过由始于网关的信标获得。一个信标是网关广告传送跳路由。每个信标包含了计跳数部分，传送时，每一跳都自然加一。路由器距离网关的长度是所有路由器接收的信标距离中最短的路径长度。路由器将这个距离通过周期心跳信息传送给频道分配服务器。算法：一旦计算好平均距离，频道分配服务器用优先搜索频道分配法来给网状接收机分配频道。 这个算法在算法 1 中总结。首先把所从有多信道冲突图的顶点变为一列（第 1 行）。通过优先搜索来访问所有的顶点并且分配频道。搜索的顶点从网关起始的线路开始（第3.4 行）。在第三行中， 在多信道冲突图的所有顶点来决定最小跳数的顶点。第四行中，所有距离与最小跳数距离相等的编入一列， Q。如果顶点相当于所有始于网关线路的顶点，他们的跳数为0.5。这些顶点通过增加延迟值来分类（第5 行）。分类是为了给予那些从最短跳数的路由器开始的线路更高地优先权。算法然后对每个Q 中的顶点运算并且永久的分配他们最高排列的频道，不与相邻的频道分配冲突。如果无冲突频道不可得到，则任意的选择一个频道永