WMN中的干扰避免部分重叠信道分配算法

杨 路，李玉洁，王诗言，肖皓月

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 引 言

网络容量的大小是决定无线mesh网络(wireless mesh network，WMN)[1]性能的关键因素，相邻信道并行传输的干扰是引起WMN容量锐减的主要原因[2]。多射频多信道(multi-radio multi-channel，MRMC)技术可以有效提升网络传输效率，增大网络容量。稀缺的频谱资源使得网络中共信道干扰增加，引发WMN容量下降等问题[3]。

文献[4-11]从不同角度验证了有效的信道分配对WMN整体性能的改善。但大多数算法的使用范围十分有限，文献[10,11]提出的两种干扰冲突图都不适用于部分重叠信道的分配方案。已有学者证明，合理设计部分重叠信道(partially overlapping channels，POC)分配方法可以有效提高频谱资源利用率和信道资源空间复用[12]。文献[13]考虑了更贴合实际网络的流量类型，充分利用部分重叠信道来设计端到端信道分配方案，有效改善了WMN网络的性能。

以上分析可得，信道分配算法可以合理地使用部分重叠信道来提高网络性能。因此，本文基于文献[13]，提出了一种有效干扰避免和负载均衡的部分重叠信道分配(load balance and interference-avoid partially overlapped channels assignment，LBIA-POCA)算法，旨在提高网络吞吐量，降低丢包率。

1 系统模型

1.1 网络模型

本文基于IEEE802.11b标准，将MRMC-WMN建模为一个无向图G(V,E)。 其中，V为节点集，代表mesh路由器、mesh网关和mesh客户端。E为链路集，表示mesh路由器之间的无线链路。mesh路由器配备k(k≥2) 个无线接口，客户端仅配备一个接口。可用部分重叠信道集C， 其可用信道个数为cn。

用F表示网络中流的集合，定义流fi的负载为li，pi为流fi的路径。从G(V,E) 中提取出加权流量子图Gf=(Vf,Ef)， 则链路l上的权重和load(l)

(1)

下面列出本文中的一些假设：

(1)所有mesh路由器都是静态的，以相同的传输功率工作，具有相同的传输范围，mesh客户端可以移动，但接入点不改变；

(2)mesh路由器的无线接口具有相同的配置、功能及发射功率；

(3)集中式信道分配由网关节点集中计算，进而发送给整个网络；

(4)使用AODV路由协议预先确定路由路径。

1.2 干扰模型

本文采用发送、接收端冲突避免协议干扰模[13]来建模。链路li=(ui,vi) 与lj=(ui,vi) 间的欧式距离d(li,lj) 定义为链路li的任意一个端点与链路lj的任意一个端点间的最短欧式距离，即

d(li,lj)=min(d(ui,uj),d(ui,vj),d(uj,vi),d(vi,vj))

(2)

对于部分重叠信道，由于两个不同信道的频谱重叠程度不同，干扰范围RI(τ) 与信道间隔τ有关。建立双径地面传播模型，通过发送节点的功率、天线增益等值推导得到同信道节点干扰范围RI(τ)

(3)

进一步可推导得到信道间隔为τ时对应的节点干扰范围值RI(τ)

RI(τ)=Ir(τ)×RI(0)

(4)

RI(τmin)

(5)

定义链路li的潜在干扰范围为IR(li)， 则IR(li) 可以表示为

IR(li)=D(ui,RI(0))∪D(vi,RI(0))

(6)

其中，D(ui,RI(0)) 为以点ui为圆心，以RI(0) 为半径的圆形区域，是节点ui的干扰范围；D(vi,RI(0)) 为节点vi的干扰范围。

(7)

1.3 链路重要因子

为了最大化网络公平性，将链路负载值作为衡量链路重要程度的一个指标。定义链路重要因子，记为S, 用以确定网络中链路的信道分配顺序，链路l的S值定义为

(8)

由式(1)定义可知，load(l) 为链路l上的负载值，定义链路l两端节点到网关节点的最小跳数为h(l)。 目前WMN的主要业务是提供Internet接入为用户获取网络服务。因此，越靠近网关的节点，其承受的网络压力越大。由S值的定义可以看出，链路重要因子与链路负载、链路端节点距网关的最小跳数有关。S值越大，链路的重要程度越高，因此按照S值降序排列顺序为链路进行信道分配。

2 信道分配算法

本文提出的LBIA-POCA算法主要由两个阶段组成，第一阶段为节点间通信接口分配，确定节点接口间的连接关系。第二阶段是无干扰信道分配阶段：根据网络干扰情况，对链路进行迭代信道分配，并使用静态链路调度来保证网络连接；最后，利用启发式算法优先为重要程度较高的链路分配无干扰时隙，对链路调度进行优化，以提高网络性能。

2.1 结点间通信接口分配

由于MRMC-WMN每个节点配有多个无线接口，因此在信道分配之前，确定结点间通信接口的连接关系是决定信道分配是否合理的关键因素。假设节点vi的度为d， 具有k个接口，与其通信的邻居节点集N={n1,n2,…,nn}。 每个邻居应该选择一个接口来传送数据包给节点vi， 并且最好应该将邻居节点均匀地关联到节点vi的k个接口，即每个接口上分配的负载是平衡的。而当邻居节点数大于节点接口数时，不能实现接口与邻居节点的一一匹配，为实现节点接口间的负载均衡，采用基于Huffman树的组合算法对邻居节点进行组合。定义节点vi与其邻居节点间的负载分别为r1,r2,…,rn， 确保具有所有可能组合的方差最小，即尽可能实现负载均衡。组合的邻居节点与节点vi的一个接口匹配，并在信道分配阶段整体考虑，分配相同信道。节点间通信接口分配见表1。

2.2 无干扰信道分配

本文采用集中式信道分配方式，集中服务器用于获取网络流的信息，并周期性更新信道分配。由于信道资源的有限性，无干扰传输的信道十分稀缺。为此，按照链路重要因子S(l) 对各链路进行降序排列，将所有链路分成M个无干扰链路集。相应地将每个数据帧的传输时间也划分为M个时隙，对应于M个无干扰链路集，每个时隙只有相应的无干扰链路集中的链路会被调度。定义一个三维矩阵MCT， 包含链路、时隙和信道分配信息

(9)

(10)

最后为重要程度较高的链路分配更多满足无干扰约束的时隙，根据链路重要因子S(l) 的顺序，依次优化链路调度。例如，对于链路lk， 若已为其分配时隙si， 则计算出链路lk与其余任意时隙sj(j≠i) 中各链路间是否存在干扰。若无则为链路lk增加改调度时隙，即可在时隙sj内调度该链路；若无，则不能在时隙si内调度链路lk。 无干扰信道分配算法流程见表2。

表2 无干扰信道分配算法伪代码

3 仿真与结果分析

3.1 仿真环境

本文的算法性能验证基于NS-3仿真平台进行。使用N×N方格网格拓扑，即，每个顶点部署有mesh路由器，每条边表示无线链路，网格步长设置为250 m，网关位于右下角。基于IEEE 802.11b标准，可用信道有11条，其中3条为正交信道。物理层的数据传输速率为2 Mbps。每个节点配置3个射频接口。对于每个接口，传输范围为250 m，载波侦听范围为550 m。使用的网络数据流为恒定比特率数据流(constant bit rate，CBR)，数据包大小固定为512 Byte，数据包发送速率为200 kbps。具体的网络参数设置见表3。

在仿真过程中，将实验结果与端到端负载感知部分重叠信道分配(ELIA)[14]、负载平衡链路层协议(LBLP)[15]以及仅使用正交信道的分配算法(LBIA-OCA)进行比较。

表3 仿真参数

分别验证网络并发流数量和网络大小对网络吞吐量、端到端时延和丢包率的影响。为了减少误差和随机结果的影响，对每个方案运行10次，运行结果取均值来保证一致性和再现性。

3.2 并发流数量对性能的影响

在5×5网格拓扑中，将并发流数量从4条递增到25条用以观察网络性能。随着流量增加，各种算法的网络吞吐量，平均端到端延迟和平均丢包率如图1～图3所示。

图1 不同并发流数量下的网络吞吐量

图2 不同并发流数量下的网络平均端到端时延

图3 不同并发流数量下的网络平均丢包率

图1为所有算法网络拓扑的平均吞吐量的比较图。由图1可得，随着网络中并发流数量逐渐增加，网络吞吐量呈现增长趋势。使用部分重叠信道分配的3种算法的性能明显优于基于正交信道分配的算法。当网络中的数据流数量为4和5时，网络中的负载较轻，4种方案的信道分配均可以得出较好的结果，网络吞吐量性能几乎相同。此时网络被划分为几个互不干扰的子网，并且正交信道足以实现非干扰数据传输。由于LBIA-OCA仅使用3个正交信道，因此当流量增加时，很可能为相邻链路分配相同的信道，由此产生的同信道干扰会阻止这些链路进行并行传输。适当地使用部分重叠信道可以减少相邻链路之间的干扰，并提高频谱效率以实现更多并行传输，因此可以改善网络性能。随着网络负载的增加，LBIA-POCA可以实现比LBLP和ELIA更高的网络吞吐量。例如，当网络中的数据流数量为7时，LBIA-POCA，LBLP和ELIA方案的网络吞吐量分别为3894.9 kbps、3221.4 kbps、2499.2 kbps。与ELIA相比，LBLP接口分配相对简单，而ELIA的接口分配可以根据节点的负载情况自适应调整，因此性能更好。LBLP没有考虑部分重叠信道的特性，因此干扰模型不适合LBIA-POCA。由于合理的邻居接口绑定和无时隙传输的时隙划分，LBIA-POCA实现了更好的网络性能。图2和 图3 分别显示了所有算法的平均端到端延迟和丢包率的比较图。由于本文提出的算法分时隙传输，因此平均端到端延迟性能改善程度较小。平均丢包率与吞吐量互补，网络丢包越多，吞吐量越低。

3.3 网格尺寸大小对性能的影响

在研究网格尺寸大小对性能的影响时，本文将网格大小从5×5逐渐增加到10×10，并在网络上同时施加一定量的CBR流，以观察网络大小对性能的影响。随着网格尺寸的增加，各种方案的网络吞吐量，平均端到端延迟和平均丢包率如图4～图6所示。

图4 不同网格大小下的网络吞吐量

图5 不同网格大小下的网络平均端到端时延

图6 不同网格大小下的网络平均丢包率

随着网络规模的增加，网络吞吐量不断提高，平均端到端延迟和丢包率有一定程度的下降。当网络拓扑很小时，正交信道分配方案网络的性能表现较差，主要是因为该方案无法为这些数据流分配不同的信道，数据包到达目标节点需要很长时间，从而对网络造成更严重的干扰。随着网络规模的扩大，网络吞吐量和平均端到端延迟性能得到了提升，原因是较大的网络允许更多的并行传输，为正交信道分配和部分重叠信道分配解决方案提供了更多空间来减少平均端到端延迟并提高网络吞吐量。与正交信道分配方案相比，部分重叠信道分配利用的可用信道资源，数据包可以更快地到达目标节点。

由图4～图6可见，LBIA-POCA算法的各项网络性能优于其它算法。当网络规模为9×9时，LBIA-POCA算法的网络吞吐量为4367.3 Kbps，相比LBLP、ELIA和LBIA-OCA分别提高了6.5%、12.2%和40.8%；LBIA-POCA算法的平均端到端时延为1.4 s，相比LBLP、ELIA和LBIA-OCA分别减少了15.6%、24.8%和44.9%；LBIA-POCA算法的平均丢包率为0.073，相比LBLP、ELIA和LBIA-OCA分别降低了37.8%、38.9%和62.9%。这是因为本文提出的算法能均衡网络负载同时避免网络干扰，更加合理地为承载网络流量的链路分配信道，避免了瓶颈链路带来的网络拥塞问题，获得更高的网络整体吞吐量。验证了LBIA-POCA算法在MRMC-WMN中信道分配的优越性。

4 结束语

针对WMN中存在的网络容量和干扰问题，本文提出了一种部分重叠信道分配算法，对具有混合流量的WMN实现有效的干扰避免和负载均衡。仿真结果表明本文提出的LBIA-POCA算法有效地避免了网络干扰，提高了网络吞吐量并降低了平均端到端延迟和丢包率。本方案是针对单播通信的WMN而设计的，而多播通信可以更有效地节省信道资源，下一步工作将研究如何解决多播通信的信道分配问题。