2. 吉林大学 通信工程学院, 长春 130012
提出了基于无线广播优势的负载感知多信道多播（W-LMCM）算法，以解决最大化服务用户数的多播路由与信道分配问题，将起始于同一节点的兄弟链路视为整体进行信道分配，充分利用无线广播优势节省带宽；提出最大信道号信道分配方法，避免随机信道分配带来的不利影响；在满足干扰范围内信道容量约束条件下，以最小化干扰为目标为链路分配信道，解决无干扰信道分配引起的服务用户数受限的问题.仿真结果表明，W-LMCM算法能有效提升多播吞吐量及网络服务能力.
2. College of Communication Engineering, Jilin University, Changchun 130012, China
Wireless broadcast advantage-based load-aware multi-channel multicast (W-LMCM) algorithm is proposed to solve the multicast routing and channel assignment problem with the goal of maximizing the number of served subscribers. W-LMCM regards links originating from the same node as a whole to fully exploit wireless broadcast advantage and save bandwidth; It uses maximal number channel selection strategy to avoid the adverse effect brought by random channel selection; While satisfying the channel capacity constraint within interference range, W-LMCM assigns channels for links with the goal of minimizing network interference, thus the problem that the number of subscribers served by interference-free channel assignment is limited can be solved. Network simulator simulation results show that W-LMCM can improve multicast throughput and network service capability efficiently.
无线Mesh网络(WMNs, wireless mesh networks)是构建下一代无线网络的关键组网技术之一，广泛应用于宽带家庭组网、社区及公司组网、公共Internet接入等[1].基础设施WMNs是目前WMNs普遍采用的网络架构[2]，其中Mesh客户端连接到基础设施骨干以获取Internet接入，基础设施骨干则为Mesh客户端提供各种资源和服务[3].
多播以广播的方式传递数据，是WMNs重要的数据传输方式.节点的一次数据发送可以使其传输范围内的所有节点都接收到相同的数据拷贝，而同时接收相同数据的节点之间不存在干扰，这称为无线广播优势(WBA, wireless broadcast advantage)[4].连接同一源节点与各接收节点的链路称为兄弟链路.为实现有效的多播数据传输，需要解决多播路由与信道分配问题，即需要建立合理的多播路由将源节点与所有多播接收端连接起来，并为路由上的链路分配合理的信道以达到通信目的.多播路由可以通过树形或格形拓扑来执行，其中树形拓扑由于实现代价较小而得到广泛采用[5]. WMNs流量的突发性易造成网络负载不均衡，继而引起网络拥塞[6].具有负载感知特性的路由及信道分配算法能更有效地均衡网络负载分布，提升网络性能.
Zeng等[7]提出了多信道多播(MCM, multi-channel multicast)算法，该算法以最小化中继节点数及源节点与多播接收端之间的跳数为目标来构建多播树，并为多播树中的链路分配部分重叠信道. Nguyen等[8]以最小化节点与一跳、两跳邻居间的信道间隔为目标选取信道，在一定程度上解决了MCM算法的隐藏信道问题. Jahanshahi等[9]以最小化多播树占用的网络资源和引入的干扰为目标构建多播路由与信道分配的二进制规划，通过求解规划得到最优的多播树构建及信道分配方案. Cheng等[10]使用智能算法解决多播路由与信道分配问题，目标是最小化网络干扰.以上多播算法在多播树构建和信道分配过程中均未考虑节点的负载状态，实际上负载重的节点应具有更高的信道分配优先权，从而保证网络在有限资源条件下能服务更多用户以获取利润. Yang等[11]提出基于负载的MCM(LMCM, load-based MCM)算法，该算法选取父节点数最少的子节点的父节点作为候选中继节点，从候选中继节点中选取负载最重的节点为中继节点来构建多播树，并使用深度优先搜索策略为多播树中的链路分配无干扰信道. LMCM算法为某链路随机选取的信道可能会影响后续链路的信道分配，制约网络性能；LMCM仅分配无干扰信道，有限的可用信道数会限制网络服务的用户数，造成资源的闲置浪费.石文孝等[12]为多个多播会话并存的WMNs提出了负载与干扰感知多播信道分配算法，该算法综合考虑流内、流间干扰及负载为链路分配干扰最小的信道.该算法仍继承了MCM随机信道分配的缺陷，且没有考虑信道的容量约束.
笔者研究多接口多信道WMNs中的多播路由与信道分配问题，在LMCM基础上提出基于WBA的负载感知多信道多播(W-LMCM, WBA-based LMCM)算法. W-LMCM算法将兄弟链路视为整体进行信道分配，充分利用WBA节省网络带宽；提出最大信道号信道分配方法，避免随机信道分配带来的不利影响；在满足干扰范围内信道容量约束条件下，以最小化干扰为目标为链路分配信道，解决无干扰信道分配服务用户数受限的问题.
1 W-LMCM算法W-LMCM算法是在LMCM算法基础上进行改进得到的. W-LMCM算法中节点的负载定义为以节点为根的子树上的总服务用户数. W-LMCM采用与LMCM相同的多播树构建方法：按照节点距离网关的跳数为节点分级；根据节点等级信息计算节点负载并选取中继节点来构建多播树，直到所有多播接收端均被覆盖，多播树构建完毕.这种多播树构建方法可以最小化中继节点数及源节点与多播接收端之间的跳数.
W-LMCM对LMCM的信道分配过程进行了改进，主要体现在以下两点.
1) 如图 1所示，为链路分配信道过程中，W-LMCM将兄弟链路视为整体进行干扰衡量，充分利用WBA.
|
图 1 干扰衡量说明 |
进行干扰衡量时，将起始于节点i的兄弟链路iu和iv视为兄弟链路组，将起始于节点j的兄弟链路jx和jy也视为兄弟链路组，兄弟链路需要被分配相同信道以充分利用WBA.由于多播数据传输没有重传和确认字符，通常使用接收端冲突避免协议干扰模型来判断链路间的干扰关系.这2个兄弟链路组之间的距离由式(1) 计算得出，通过距离与对应干扰范围的比较得出它们的干扰关系，如式(2) 所示.
| $ d\left( i, j \right)=\min \left( d\left( i, x \right), d\left( i, y \right), d\left( i, u \right), d\left( i, v \right) \right) $ | (1) |
| $ I\left( i, j \right)=\left\{ \begin{matrix} 1,&\text{if}\ d\left( i, j \right)\le R\left( \tau \right) \\ 0,&\text{else}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \end{matrix} \right. $ | (2) |
其中：d(i, x)为节点i与节点x之间的欧氏距离；R(τ)为信道间隔τ对应的干扰范围[13]，τ=|ch(i)-ch(j)|，ch(i)为分配给节点i的信道.
2) 为兄弟链路选取的是干扰最小的信道，而不是无干扰信道.干扰链路会竞争信道使用权，但是只要满足干扰范围内要求的数据传输速率不超过信道容量，多播请求是可以得到满足的.如果仅分配无干扰信道，则即使所有的正交信道和部分重叠信道均用于信道分配，有限的可用信道数仍会制约服务用户数，并造成网络资源的闲置浪费.
当有多条链路均满足干扰要求时，W-LMCM会从所有候选信道中选取信道号最大的并将其分配给兄弟链路组，如式(3) 所示.
| $ \begin{align} & {{c}_{\text{h}}}\left( i \right)=\max \left\{ c|c\in C\cap {{i}_{\text{f}}}\left( c \right)=\underset{\forall t\in C}{\mathop{\min }}\,{{i}_{\text{f}}}\left( t \right) \right\}, \\ & {{i}_{\text{f}}}\left( t \right)={{l}_{\text{o}}}\left( i \right)+\sum\limits_{j\in T\cap j\ne i}{{{l}_{\text{o}}}\left( j \right)}I\left( i,j \right) \\ \end{align} $ | (3) |
其中：if(t)是为起始于节点i的兄弟链路组分配信道t时，该兄弟链路组与网络中已分配信道链路产生的干扰；C为网络所有可用信道的集合；T为构建出多播树覆盖节点的集合；lo(i)为节点i的负载；I(i, j)为起始于节点i和节点j的兄弟链路组是否干扰的指示，如式(2) 所示.
最大信道号信道分配方法能避免随机信道分配带来的不利影响，为后续的信道分配预留出足够的空间.这种信道分配方法的优势可通过图 2来说明.
|
图 2 最大信道号信道分配方法优势 |
假设已经为链路e1分配了信道1，为链路e2分配信道时，可用信道集合为C1={5, 6, 7, 8, 9, 10, 11}，随机信道分配方法从C1中随机选取一条信道，如信道8.为链路e3分配信道时，为了保证不与链路e1相干扰，它们的信道间隔至少为4，则可用信道集合C2={5, 6, 7, 8, 9, 10, 11}；同理，为了保证不与链路e2干扰，可用信道集合C3={1, 2, 3, 4}.链路e3的可用信道集合C4=C2∩C3=∅，即无法为链路e3找到无干扰的可用信道.
同样条件下，最大信道号信道分配方法会从可用信道集合C′1={5, 6, 7, 8, 9, 10, 11}中选取最大信道号信道，即将信道11分配给链路e2.为链路e3分配信道时，为了保证不与链路e1相干扰，可用信道集合C′2={5, 6, 7, 8, 9, 10, 11}；同理，为了保证不与链路e2干扰，可用信道集合C′3={1, 2, 3, 4, 5, 6, 7}.链路e3的可用信道集合C′4=C′2∩C′3={5, 6, 7}，选取其中最大信道号信道，即将信道7分配给链路e3.
由以上分析可以看出，最大信道号信道分配方法能克服随机信道分配方法的缺陷，为更多的链路找到可用信道.
2 性能分析与评价利用网络仿真器将W-LMCM算法与以下多播算法进行了仿真性能比较，通过格形拓扑和随机拓扑下的仿真结果验证W-LMCM算法的性能.
1) t-LMCM算法：当有多条信道均满足无干扰要求时，从候选信道中选取最大信道号信道的改进LMCM算法.该算法能避免LMCM算法随机信道分配对网络性能的不利影响.
2) LMCM算法
性能评价是针对服务用户数、占用的网络接口数、网络干扰、多播吞吐量、平均丢包率和平均端到端时延6个指标进行的，其中服务用户数与网络干扰2个指标的定义具体如下，其余指标的定义与文献[13]相同.
1) 服务用户数：在满足干扰范围内信道容量的约束条件下，多播算法能服务用户数的最大值.网络能服务的用户数越多，则收益越大.
2) 网络干扰：位于彼此干扰范围内的多播树链路会竞争信道使用权，网络干扰衡量的是受这类干扰链路影响的总服务用户数.
2.1 仿真参数设置格形拓扑和随机拓扑2种网络场景下，网关节点均位于WMNs的中心位置.多播接收端是从除网关外的其他所有节点中随机选取的，每个多播接收端下的用户数随机取为1~5之间的整数.网关节点使用恒定比特速率(CBR, constant bit rate)发送数据，每个Mesh路由器配备2个网络接口，使用全向天线进行数据的发送和接收.具体的仿真参数设置如表 1所示.
|
表 1 仿真参数设置 |
源节点的发包速率设定为200 kbit/s，改变多播组中多播接收端的数目并观察格形拓扑下各多播算法的性能，仿真结果如图 3所示.
|
图 3 格形拓扑下各多播算法的性能比较 |
由图 3可以观察各多播算法随多播组规模扩大的性能变化趋势.各性能指标具体分析如下：
1) 服务用户数.服务用户数随多播组规模的扩大而增加.多播组中包含的多播接收端数目越多，需要服务的用户数越多，通过各多播算法得到服务的用户数也相应增加. LMCM服务的用户数最少，这主要是由信道分配的随机性引起的.为某链路随机分配的无干扰信道可能会导致无法为后续链路找到可用的无干扰信道，网络性能受到影响.
t-LMCM相对于LMCM性能提升的原因是它避免了信道分配随机性带来的不利影响. W-LMCM服务用户数随多播组规模的扩大呈线性增长，原因是W-LMCM充分利用了WBA，在满足干扰范围内信道容量约束条件下，为链路分配干扰最小的信道.这样可以为更多的多播树链路分配信道，得到服务的用户数也相应增加.
2) 占用的网络接口数.多播树中各节点消耗的网络接口数是固定的，中继节点消耗2个接口分别用于从上级节点接收数据和向下级节点转发数据.作为多播接收端的节点消耗1个接口用于从上级节点接收数据.为服务更多用户，网络通常需要建立更大的覆盖更多节点的多播树才能完成多播数据的传输，覆盖的节点越多则占用的网络接口数也就越多.
3) 网络干扰. LMCM和t-LMCM算法的网络干扰为0，因为它们只分配无干扰信道. W-LMCM是以最小化网络干扰为目标来为链路选取信道的，因此它以增加少量干扰为代价换取网络服务能力的提升.实际上，这些干扰链路会竞争信道使用权，但是只要满足干扰范围内的信道容量约束，多播数据传输仍可以快速准确的进行.
4) 平均丢包率和平均端到端时延.各多播算法的平均丢包率均为0，即它们都可以实现所有多播数据的正确传递，且数据包不需要在各中继节点的缓存队列中等待传输机会，端到端时延都很小且较恒定. W-LMCM算法的平均端到端时延略大.为覆盖更多的用户，W-LMCM需要建立更大的多播树，这样数据包传输的路径会略长，需要的传输时间也会略增加.
5) 多播吞吐量.各多播算法下被服务的用户均能成功接收所有传递来的多播数据包，且端到端时延接近，因此多播吞吐量基本上与服务用户数呈相同的变化趋势.
在30个节点组成的随机拓扑中重复上述仿真，得到各多播算法的性能仿真结果如图 4所示.
|
图 4 随机拓扑下各多播算法的性能比较 |
由图 4可以得出以下两点结论.
1) W-LMCM与t-LMCM算法的性能完全相同，原因是随机拓扑的节点分散分布特性使得多播树中各路径间的距离较大，W-LMCM与t-LMCM算法均能无干扰地服务所有用户，即它们建立了相同的多播树并实现了无干扰的多播数据传输. LMCM信道分配的随机性制约了网络的性能，无论是服务用户数还是多播吞吐量均低于W-LMCM和t-LMCM算法.
2) 随机拓扑下W-LMCM算法能达到最优性能.随机拓扑下，连接多播接收端与源节点的各路径上的链路均能被分配无干扰信道，所有传输可以并行进行而不会彼此干扰.这表明所提出的W-LMCM算法能够达到随机拓扑下的最优性能，即W-LMCM算法在格形和随机拓扑下都是适用的.
3 结束语笔者提出了W-LMCM算法，在满足干扰范围内信道容量约束条件下有效解决了最大化服务用户数的多播通信问题. W-LMCM算法能克服LMCM随机信道分配和无干扰信道分配带来的不利影响，显著提升了服务用户数及多播吞吐量等性能.
W-LMCM算法只为单个多播会话分配资源，没有从业务管理角度优化整体网络的资源使用.下一步的工作是研究多个多播会话及单播会话并存条件下的多播路由与信道分配问题，目标仍是最大化服务用户数.
| [1] | Avallone S, Banchs A. A channel assignment and routing algorithm for energy harvesting multiradio wireless mesh networks[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(5): 1463–1476. doi: 10.1109/JSAC.2016.2520238 |
| [2] | Ghannay S, Gammar S M, Filali F, et al. Multi-radio multi-channel routing metrics in IEEE 802. 11s based wireless mesh networks[J]. Annals of Telecommunications, 2012, 67(5-6): 215–226. doi: 10.1007/s12243-011-0253-z |
| [3] | Zhou Ping, Wang Xudong, Rao R. Asymptotic capacity of infrastructure wireless mesh networks[J]. IEEE Transactions on Mobile Computing, 2008, 7(8): 1011–1024. doi: 10.1109/TMC.2007.70778 |
| [4] | Zhao Xin, Guo Jun, Chou C T, et al. High-throughput reliable multicast in multi-hop wireless mesh networks[J]. IEEE Transactions on Mobile Computing, 2015, 14(4): 728–741. doi: 10.1109/TMC.2014.2333731 |
| [5] | Luo Junhai, Ye Danxia, Xue Liu, et al. A survey of multicast routing protocols for mobile Ad-Hoc networks[J]. IEEE Communications Surveys and Tutorials, 2009, 11(1): 78–91. doi: 10.1109/SURV.2009.090107 |
| [6] |
石文孝, 许银龙, 王继红, 等. 无线Mesh网络干扰与区域负载感知路由度量[J]. 北京邮电大学学报, 2014, 37(5): 41–44.
Shi Wenxiao, Xu Yinlong, Wang Jihong, et al. Interference and regional load aware routing metric for wireless mesh networks[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(5): 41–44. |
| [7] | Zeng Guokai, Wang Bo, Ding Yong, et al. Efficient multicast algorithms for multi-channel wireless mesh network[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(1): 86–99. doi: 10.1109/TPDS.2009.46 |
| [8] | Nguyen H L, Nguyen U T. Channel assignment for multicast in multi-channel multi-radio wireless mesh networks[J]. Wireless Communications and Mobile Computing, 2009, 9(4): 557–571. doi: 10.1002/wcm.v9:4 |
| [9] | Jahanshahi M, Dehghan M, Meybodi M R. A mathematical formulation for joint channel assignment and multicast routing in multi-channel multi-radio wireless mesh networks[J]. Journal of Network and Computer Applications, 2011, 34(6): 1869–1882. doi: 10.1016/j.jnca.2011.01.003 |
| [10] | Cheng Hui, Yang Shengxiang. Joint QoS multicast routing and channel assignment in multiradio multichannel wireless mesh networks using intelligent computational methods[J]. Applied Soft Computing Journal, 2011, 11(2): 1953–1964. doi: 10.1016/j.asoc.2010.06.011 |
| [11] | Yang Wenlin, Kao Chichou, Tung Chenghuang. Heuristic algorithms for constructing interference-free and delay-constrained multicast trees for wireless mesh networks[J]. KSⅡ Transactions on Internet and Information Systems, 2011, 5(2): 269–286. |
| [12] |
石文孝, 李蒸, 崔克强, 等. 一种无线Mesh网络负载与干扰感知多播信道分配算法[J]. 吉林大学学报(工学版), 2016, 46(5): 1644–1650.
Shi Wenxiao, Li Zheng, Cui Keqiang, et al. Load and interference-aware channel assignment algorithm for multicast in wireless mesh networks[J]. Journal of Jilin University (Engineering and Technology Edition), 2016, 46(5): 1644–1650. |
| [13] | Wang Jihong, Shi Wenxiao. Joint multicast routing and channel assignment for multi-radio multi-channel wireless mesh networks with hybrid traffic[J]. Journal of Network and Computer Applications, 2017, 80: 90–108. doi: 10.1016/j.jnca.2016.11.022 |