多接口多信道WMN中基于干扰感知的多播路由算法

尹凤杰，杨小梅

(辽宁大学 信息学院，辽宁 沈阳 110036)

0 引言

无线Mesh网络(Wireless Mesh Network，WMN)具有组网灵活、易于部署、可靠性高等特点[1]，但由于同信道干扰的存在，网络容量受到了很大限制，尤其是在多播流量中较为严重.为了有效消除干扰，提高无线电资源的利用率，可以为无线Mesh网络中的路由器配备多个调谐到非重叠信道的无线电接口，这种网络就叫做多接口多信道无线Mesh状网络(Multi-Radio Multi-Channel Wireless Mesh Network，MRMC-WMN).许多研究表明，在无线Mesh网络中使用定向天线也可以有效减少干扰[2-5]，提升网络性能.因为与全向天线不同，定向天线几乎将所有辐射功率集中在主瓣方向上，只有那些位于发送节点主瓣内的节点才会干扰其他的发送节点[6-7]，这样就极大地减少了链路之间的同信道干扰，实现了更高的网络容量，获得了更好的网络性能.

近年来已有大量工作致力于将定向天线运用在无线自组网中的研究.文献[8]研究了使用定向天线对多接口无线Mesh网络信道分配的影响，提出的信道分配算法能够在大型拓扑中实现良好的网络性能.文献[9]提出了一种使用定向天线并考虑干扰的功率控制方案，且通过实验证明该方案提高了网络吞吐量，降低了能耗.文献[10]证明了MCMT(Minimum Cost Multicast Tree)是一个NP难题，并使用ILP(Integer Linear Programming)模型将其优化，提出了WCTB(Wireless Closest Terminal Branching)算法，利用WBA减少多播树中的传输次数，而且为了减小多播会话之间的干扰，还提出了MIMCR(Minimum Interference Minimum Cost Routing)算法.刘强等[11]针对使用全向天线进行数据传输时，会产生信号干扰严重和网络收敛较慢等问题，提出了一个基于定向天线的移动自组织网(MANETs)接入控制协议(DAND-MAC)，统一协调定向天线与全向天线同步工作，该协议在端到端延迟、吞吐量和时隙利用率等网络性能上有显著的提升.文献[12]提出了两种跨层算法：IRMT(Interference and Rate-aware Multicast Tree)算法和IRBT(Interference and Rate-aware Broadcast Tree)算法，减少带宽消耗.王松[13]提出了一种基于定向天线波束聚合旋转的分布式算法，该算法能快速构建一个网络，在满足节点度数限制的同时又使网络获得接近最优的吞吐量.文献[14]研究了使用定向天线的无线Mesh网络中的快速广播算法的设计问题，提出了基于传统的流言扩散机制的随机选择算法，以及基于贪婪策略的最大差异度优先算法.为了解决基于多波束切换的移动自组网邻居发现过程中的最优通信波束选择问题，李丽等[15]提出了一种改进的算法，在邻居发现过程中增加了接收信号质量评估机制，从而增强了网络的稳定性，提高了网络吞吐量.以上这些工作都在一定程度上改善了无线Mesh网络性能，但是对于影响网络性能的因素考虑得不够充分.为此，根据无线Mesh网络特性，本文综合运用定向天线技术、WBA和定向节点同信道干扰(Directional Node Co-Channel Interference，DNCI)判据，提出了干扰感知波束信道选择多播(Interference-aware Beam-channel Selection Multicast Routing，IBSMR)路由算法，使无线Mesh网络的整体性能获得了提升.

1 系统模型

1.1 定向天线模型

定向天线几乎将全部功率辐射到主瓣方向上，而向旁瓣方向辐射极少的功率.广泛使用的定向天线模型有两种：现实天线(Realistic Antenna)模型和理想天线(Ideal Antenna)模型.图1(a)为现实天线模型，天线的方向图由一个主瓣和多个旁瓣组成.图1(b)为理想天线模型，天线的方向图近似为波束宽为θ(0≤θ≤2π)的扇形.

为了方便，本文使用理想天线模型，假定每个发送节点的天线方向图仅由一个主瓣构成，主瓣方向即为该发送节点的功率辐射方向，旁瓣方向上的发射功率则为零.此外，本文假定每个接收节点都使用全向天线，可以接收从任意方向辐射过来的功率.在给定的传输功率下，理想天线的传输范围R(θ)通过公式(1)计算：

R(θ)=R0·(2π/θ)1/α

(1)

这里，α为定向天线的波束宽度，β是路径损失指数，R0则表示全向天线的传输范围.由公式可知，定向天线的主瓣传输范围与波束宽度和路径损失指数成反比，即，R(θ)会随着θ和α的增大而减小，反之亦然.

1.2 MRMC-WMN网络模型

用有向图G=(V，E)来表示多接口多信道无线Mesh网络，其中，V和E分别代表网络中的节点集和无线链路集.用(x，y)k表示节点x与y之间的无线链路，且节点x是发送节点，节点y位于节点x的主瓣内，两个节点之间使用信道k来传输数据.如图2所示的MRMC-WMN有向网络图，每个节点都配备了三个无线电接口，且都被调谐到三条不同的非重叠信道上，虚线箭头代表节点间的无线链路，链路旁的数字集合表示该链路的所有可用信道.由于使用了定向天线，相互连接的两个节点在两个方向上的可用信道允许不相同.例如，图中的节点m向节点a发送数据时，仅可使用信道1，而节点a向节点m发送数据时，既能使用信道1，也能使用信道2.为了更好地理解定向天线的方向性，图中仅仅画出了节点m的三条波束，并假定节点m被调谐到信道1、信道2和信道5上，并分别通过这些信道的波束覆盖了节点集{a，q}、{p，c}和{e}.

图2 使用定向天线的MRMC-WMN网络图

从图2可知，在使用定向天线的多接口多信道无线Mesh网络中，由于定向天线的波束只覆盖了部分节点，这就大大减少了节点之间的干扰.但也正是由于定向天线的使用，信道选择时极大地减小了WBA的影响，增加了网络的传输次数，造成严重的网络资源浪费.所以，我们需要折中考虑干扰和传输次数，使无线Mesh网络获得更好的性能提升.

1.3 干扰模型

在无线Mesh网络中，经常使用协议干扰模型(Protocol Interference Model)来计算多播发送节点之间的干扰，当一条链路的接收节点位于其他发送节点的干扰波束范围内，该链路就是被干扰链路.在多播通信中，干扰是由每个发送节点和所有树链路来确定的.如图3所示，有两棵多播树T1和T2，多播树T2中的发送节点s在信道5上的干扰范围为Ir，会干扰多播树T1上的运行在相同信道5上的链路(g，p)，因为链路(g，p)的接收节点p位于节点s的干扰范围内.这种情况下，当节点g在发送分组时，节点s就不能发送分组，必须等到节点g发送完毕节点s才能发送，这种不必要的等待导致了网络时延增加，性能下降.

图3 多播树无线链路间的干扰关系

2 问题及IBSMR算法描述

2.1 问题描述

对于给定的有向网络图G=(V，E)，用S(S∈V)表示多播源节点，R(R⊂V)表示多播接收节点.最小开销多播树(Minimum Cost Multicast Tree，MCMT)的目的是构建一棵以源节点S为根，覆盖R中所有接收节点的最小开销多播树.将多播树T在波束信道k上的传输节点的集合表示为V(T，k)，根据文献[11]中的定义，多播树T的开销由公式(2)计算：

Tree_cost(T)=∑k∈K|V(T，k)|

(2)

这里，K为网络中所有可用信道的集合.另外，通过扩展文献[11]中的定义，用定向节点同信道干扰(Directional Node Co-Channel Interference，DNCI)来量化多播树之间的干扰.那么，与发送节点x相关的多播树集Tset在波束信道k上的干扰可通过公式(3)计算：

DNCI(x，k，Tset)=∑T∈Tset|IL(x，k，T)|

(3)

这里，|IL(x，k，T)|表示多播树T中被运行在波束信道k上的节点x的传输所干扰的链路总数.通过DNCI(x，k，Tset)，就可以通过公式(4)计算出定向树同信道干扰(Directional Tree Co-Channel Interference，DTCI).

DTCI(T，Tset)=∑k∈K∑x∈V(T，k)DNCI(x，k，Tset)

(4)

通过以上阐述，我们的主要目标就是让使用定向天线的MRMC-WMN中每棵多播树的Tree_cost(T)和DTCI(T，Tset)最小，控制多播树传输数量的同时减小干扰，最终达到改善整个网络性能的目的.

2.2 IBSMR多播路由算法

本小节将详细阐述IBSMR多播路由算法，该算法启发式地解决了使用定向天线的多接口多信道无线Mesh网络中的最小干扰问题.在IBSMR多播树中，有三种类型的链路.第一种是树链路(Tree Link)，如果一条链路(x，y)k已经加入当前多播树T，那么该链路就是树链路，在这种链路上传输新的数据分组对于多播树来说不计算链路开销，因为当该链路加入多播树后，其链路开销就已经变为零.第二种是覆盖链路(Covered Link)，这些链路还没有包括在多播树T中，但已经被T中发送节点x的定向波束所覆盖，因此，这些链路的开销也为零，在这些链路上传输新的分组时也不计算其开销.第三种是未覆盖链路(Uncovered Link)，除树链路和覆盖链路之外的链路就是未覆盖链路，在这些链路上传输新的分组时需计算链路开销.对于每一个多播会话请求，IBSMR算法会逐步构建路由树，每一步都包括两个阶段.

第一阶段，首先在全向图上运行Dijkstra算法找到源节点S和所有目的节点R之间的最短路径，并用DP(S，R)表示这些最短路径的集合.然后通过公式(5)计算每条路径p(S，ri)∈DP(S，R)的开销，并根据公式(6)选择开销最小的一条路径添加到当前多播树T中.

cost(p(S，ri))=∑(x，y)∈p(S，ri)W(x，y)

(5)

psel(S，ri)=argminDP(S，R)cost(p(S，ri))

(6)

式中，W(x，y)表示链路(x，y)∈p(S，ri)的开销，路径p(S，ri)的开销即为其所有组成链路的开销之和.

第二阶段，在最小开销路径psel(S，ri)加入多播树后，开始为该路径的每条链路选择最佳波束信道，并更新链路开销和接收节点集.根据网络模型，两个节点之间的无线链路可以采用不同的信道，这里用k(x，y)avi表示链路(x，y)的所有可用信道集，在这些信道中选择一条作为该链路的传输信道.然而，IBSMR算法面临着一个挑战，那就是在所有可行的开销最低的路径中选择最佳路径，使该路径的波束所导致的干扰最小.所以，IBSMR算法使用公式(3)中的定向节点同信道干扰(Directional Node Co-Channel Interference，DNCI)作为判据，在所有可用波束信道中选择导致干扰最小的一条.

ksel=argmink(x，y)aviDNCI(x，y，Tset)

(7)

这里，ksel表示所选择的波束信道.波束信道选择后，被该波束所覆盖的所有链路的链路开销都被置为零.当路由树覆盖了所有接收节点时，IBSMR算法运行结束.其中，选择最佳波束信道的具体过程如下：

在为链路分配波束信道时，首先判断该链路的类型.若链路(x，y)是未覆盖链路，则计算其每条可用波束信道的DNCI判据，并选择导致干扰最小的一条波束信道k来传输数据，随后，发送节点x调谐到波束信道k上的天线的波束自动转到接收节点y的方向上，并且波束宽度恰好覆盖接收节点y；若链路(x，y)是已分配信道k的某条波束的覆盖链路，就为该链路选择信道k作为发送节点x的传输信道，接着发送节点x调谐到波束信道k上的天线的波束自动变宽直到覆盖接收节点y；若链路(x，y)是一条树链路，则不作任何操作.IBSMR算法描述如下：

输入：有向网络图G

多播源节点S

多播接收节点集R

输出：以S为根的多播树T

1.for 每一条链路(x，y)do

2. 将其链路开销设为1

3.whileR不为空时 do

4. 运行Dijkstra算法计算从源节点S到所有接收节点R的最短路径DP(S，R)

5. for每一条路径p(S，ri)∈DP(S，R)do

6. 计算其路径开销cost(p(S，ri))

7. end for

8. 选择最小开销的路径psel(S，ri)加入当前多播树

9. for 最小开销路径的psel(S，ri)的每一条链路(x，y)do

10. if(x，y)是一条未覆盖链路 then

11. (1)计算该链路所有可用波束信道的DNCI判据

12. (2)选择DNCI判据最小的信道k作为该链路的传输波束信道

13. (3)调节运行在信道k上的发送节点x的天线的方向和波束宽度以覆盖接收节点y

14. if(x，y)是一条覆盖链路(已被运行在信道k的波束所覆盖)then

15. (1)选择信道k作为该链路的传输波束信道

16. (2)运行在信道k上的发送节点x的天线波束变宽直到恰好覆盖接收节点y

17. if(x，y)是一条覆盖链路 then

18. 不作任何操作

19. end if

20. 更新链路开销(将所有被波束信道k所覆盖的链路的开销都置为0)

21. end for

22. 更新接收节点集

24.end while

3 仿真实验与结果分析

这部分将通过仿真实验综合评估IBSMR算法的性能，比较IBSMR算法与WCTB算法和MIMCR算法[4]的平均传输次数和归一化干扰.其中，归一化干扰是指网络实际干扰与最大干扰的比值.我们的多接口多信道无线Mesh网络测试平台由31个Mesh路由器组成，这些路由器随机分布在1 000 m×1 000 m的正方形区域中，并且每个路由器都配备三个无线电接口，这些接口被随机调谐到不同的非重叠信道上.我们假设全向天线的传输范围为300 m，定向天线的传输范围则通过公式(1)来计算.另外，每个节点的干扰范围是其传输范围的两倍，并假定路径损失指数α为4.实验中每个多播会话的源节点和目的节点都是随机选择的，实验所涉及的参数有|K|、N、r和q，其中|K|表示不重叠信道的总数，N表示网络中的节点数，r表示多播接收节点数，q表示多播会话请求数.图中的每个数据点都是50次单独运行结果的平均值.

图4的仿真结果显示了当α不同时IBSMR算法在平均传输次数和归一化干扰方面的性能.该实验设定|K|=6，N=31，r和q作为变量.由图4可知，随着α的增加，平均传输次数和归一化干扰也都随之增加.事实上，参数α的增加减小了每个波束的传输范围.

图4 不同α下的平均传输次数和归一化干扰

图5的仿真结果显示了在无线电接口数不同时，信道数目的变化对IBSMR算法性能的影响.该仿真设定N=45，r=0，q=30，|K|作为变量.比较图5(a)和图5(b)，可以看到，平均传输次数随着信道数的增加而增加，归一化干扰却随之增加而减小.开始时，由于可用信道数小于无线电接口数，平均传输次数随着可用信道数的增加而减少.当可用信道数大于无线电接口数时，WBA的影响减弱，所以传输次数增加.另一方面，随着可用信道数的增加，提高了网络的同步传输能力，并减小了归一化干扰.此外，从图5(a)和图5(b)可以看出，无线电接口越多，传输次数和归一化干扰越小.因此，为网络中的每个发送节点配备适当多的无线电接口，能够有效提升无线Mesh网络性能.

图5 不同接口数下的平均传输次数和归一化干扰

图6的仿真结果显示了传输次数和归一化干扰随多播接收节点数的变化关系.该实验设定|K|=6，N=31，q=30，r作为变量.图6(a)显示出IBSMR算法与WCTB算法和MIMCR算法的传输次数几乎相等.图6(b)显示出三种算法的归一化干扰都会随着多播接收节点的增加而增加，但IBSMR算法的干扰明显小很多.因为IBSMR算法在全向图上找到最短路径后，定向天线的波束自动地调节到目的接收节点的方向上，所以IBSMR算法在传输次数上保持WCTB算法和MIMCR算法性能界限的同时，极大地减少了多播树间的干扰.

图6 平均传输次数和归一化干扰随多播接收节点数的变化关系

图7的仿真结果显示了平均传输次数和归一化干扰随多播会话数的变化关系.该实验设定|K|=6，N=31，r=10，q从1变到30.图7(a)显示出IBSMR算法与WCTB算法和MIMCR算法在传输次数上性能相当.图7(b)显示出IBSMR算法在减少干扰方面比WCTB算法和MIMCR算法更加有效.在IBSMR算法中，每根天线的波束宽度和方向都是自适应地只覆盖目标接收节点，因此大大减少了传输节点的干扰区域.此外，在IBSMR算法中，源节点和接收节点之间选择的最小开销路径是干扰最小的路径，并在所有可用信道中选择导致最小干扰的信道作为传输信道.因此，IBSMR算法在降低干扰方面具有最佳性能.

图7 平均传输次数和归一化干扰随多播会话数的变化关系

4 结束语

本文研究了多接口多信道无线Mesh网络中的多播路由算法，综合运用定向天线技术、WBA和定向节点同信道干扰，提出了IBSMR多播路由算法.该算法在多播树构建期间，每一步都首先选择最小开销路径加入多播树，这就保证了最终所构建的多播树的树开销最小；在波束信道选择时，充分考虑了链路之间的同信道干扰，利用DNCI判据为每条链路都选择最佳波束信道来进行数据传输；定向天线的使用充分利用了WBA优势减少了传输次数，并且发送节点的波束只覆盖接收节点，大大地减少了干扰.仿真结果也表明，IBSMR算法在传输次数和干扰方面明显优于其他多播路由算法，能够更加有效地改善MRMC-WMN网络性能.