同步无线Mesh网络带宽申请与分配策略的改进

王未名+焦蓉+刘经纬+吕仁健+韩仲华

摘 要： 数据通信具有突发性与带宽计算的不确定性，现有同步无线Mesh网络带宽申请与分配策略未对此问题进行充分考虑，在设计上存在带宽申请速度慢、带宽分配没有最大化、将数据时隙区分了上下行等不足，导致了QoS保障能力低与网络性能的下降。提出了带宽申请与分配策略的改进方案，包括结合各类数据业务类型的带宽申请条件的描述、检查数据发送队列的时间间隔描述、带宽分配最大化的描述、数据时隙不再区分上、下行的描述。理论分析表明，改进后的方案能够提供精确的QoS保障并提高网络性能。

关键词： 同步无线Mesh网络； 带宽申请； 带宽分配； 数据时隙； 带宽分配表

中图分类号： TN711?34； TP393.04 文献标识码： A 文章编号： 1004?373X（2014）16?0024?04

Improvement of bandwidth request and allocation for synchronized WMN

WANG Wei?ming1， JIAO Rong2， LIU Jing?wei2， [LU] Ren?jian2， 3， HAN Zhong?hua2

（1. China Electronics Technology Group Corporation， Beijing， 100846， China；2. North China Institute of Computing Technology，Beijing，100083，China；

3. School of Computer Science， Beijing University of Posts and Telecommunications， Beijing， 100876， China）

Abstract： Data communication has uncertainty features of suddenness and bandwidth calculation uncertainty. These factors have not been fully considered in existing bandwidth request and allocation strategy for synchronized WMN， so the slow bandwidth request， non?maximized bandwidth allocation and the division of upstream and downstream data time?slot are existed in the design， which cause the low QoS guarantee capability and network performance decline. An improved scheme for bandwidth request and allocation strategy is proposed， in which there are bandwidth request description for various data business types， the time interval description of the data transmission queue check， the maximized bandwidth allocation description and the mergence description of upstream and downstream data time?slot. Theoretical analysis shows that the fine QoS guarantee and the high performance can be realized in the improved solution.

Keywords： synchronized WMN； bandwidth request； bandwidth allocation； data time?slot； bandwidth allocation table

0 引 言

基于多方向天线阵列[1]的同步无线Mesh网络（Synchronized WMN）通过多根高增益定向天线在全向范围内完成了多扇区的高速扫描，使节点具备了单跳最大20 km通信距离的能力，而通过专有同步无线Mesh网络协议技术，使网络具备了多跳组网能力与高效数据传输能力，从而适用于宽带的机动组网应用领域。

同步无线Mesh网络的性能取决于硬件能力与与协议软件能力。硬件能力[2?4]包括多方向天线阵列硬件结构与底层无线数据收发信机，协议软件能力[5?7]包括软件平台基础性能与同步无线Mesh网络协议性能。同步无线Mesh网络协议性能主要与底层同步数据的收发性能与上层带宽申请与分配策略有关，合理的带宽申请与分配策略可以在恰当的时机产生带宽申请并在最短时间内给出带宽分配结果，并且可以保证其在大规模网络运行下的快速收敛性。

现有同步无线Mesh网络协议在带宽申请与分配策略上[8?10]仍存在以下不足，如进行改进，网络性能可有进一步提升：

（1） 带宽申请速度慢。现有策略为减少带宽申请的发生次数，更多地参考了带宽申请的历史发送数据量从而降低了触发带宽申请的阈值，其历史权重值为0.6，而周期检查数据发送队列待发送数据量的时间间隔为10 s，上述两种参数可以保证网络中各条链路在大部分时间内的带宽使用趋于稳定。然而，当节点产生了实时数据并且现有带宽不能满足时，现有策略不能较快地触发带宽申请，导致了数据通信的等待时间过长。

（2） 带宽分配没有最大化。现有的带宽分配策略为了降低未来新入网节点产生带宽申请的可能性，对可分配带宽进行了预留。然而，很多应用场合中的网络拓扑结构很少发生变化，发生网络重构或新节点加入网络的可能性很小，其网络的主要应用是保证带宽最大化。

（3） 将数据时隙区分了上下行。现有的带宽分配策略将数据时隙分成了上行数据时隙与下行数据时隙，保证了上下行数据分别拥有互不干扰的、稳定的带宽。但实际情况是：带宽分配策略实际难以准确估计数据传输所需要的带宽，当上行数据传输完毕而下行数据传输又需要更多的带宽时，所有上行时隙即被浪费。

产生上述问题的原因在于现有带宽申请与分配策略未考虑到数据通信的突发性、贪婪性与带宽计算的不准确性。本文将对上述问题进行解决，并提出同步无线Mesh网络带宽申请与分配策略的改进方案。

1 带宽申请与分配策略的改进

1.1 提高带宽申请速度

（1） 带宽申请的条件

不再参考带宽申请的历史发送数据量，而以当前节点数据业务类型与数据发送队列中的数据量的变化量决定是否进行带宽申请。这样有助于提高产生实时数据与大量突发数据时的带宽申请速度，而不必要的带宽申请则明显减少。

带宽申请不仅可以申请所需的数据时隙个数，也可以申请所需的数据时隙位置（数据时隙仅用于普通数据传输，并不用于链路维护等协议数据传输，因为协议数据传输是在不可分配的特殊时隙内完成）。将数据发送队列按数据业务类型分类：Ping数据、IP语音数据、FTP数据、视频数据，即每种数据业务各使用一个数据发送队列。各类数据的数据量、带宽申请情况如表1所示。

表1 各类数据的数据量、带宽申请情况

各类数据触发带宽申请的条件如表2所示。

（2） 检查数据发送队列的时间间隔

缩短检查数据发送队列待发送数据量的时间间隔。将该时间间隔改为一个带宽分配表所匹配的数据时隙长度（50个时隙长度），以此提高带宽申请的实时性。

1.2 带宽分配最大化

（1） 不进行带宽预留，而是将所有可分配的带宽都分配出去，以保证当前网络内的时隙使用效率最高。当网络拓扑结构改变或者有新节点加入网络中后，将产生带宽的重新分配，而重新分配后的带宽分配仍然是最大化分配。

表2 各类数据产生带宽申请的条件

（2） 带宽申请既可以申请增加数据时隙，也可以申请减少数据时隙。只有这样，才能把有限的带宽资源分配给最需要带宽的节点。

1.2.1 单跳网络情况

单跳网络情况比较简单，如图1所示。不论骨干1节点处于正在入网状态还是入网后状态，网关节点不按照骨干1节点的实际带宽申请量分配带宽，而是把自己所有带宽都分给骨干1节点。

图1 单跳网络情况

1.2.2 星状网络情况

星状网络情况如图2所示。网关节点根据骨干1与骨干2的带宽申请对需要带宽者进行最大化带宽分配。

（1） 骨干2节点正在入网。当网关节点收到骨干2节点发出的表示将要从网关节点处入网的入网请求包后，网关节点将按照骨干2节点的带宽申请量从分配给骨干1节点的带宽中回收相应带宽并分配给骨干2节点。回收带宽的数量与位置则按照骨干2节点的带宽申请策略。

图2 星状网络情况

（2） 骨干2节点入网后。骨干2节点入网后，如果网关节点与骨干1节点、网关节点与骨干2节点之间的普通数据通信均已结束，网关节点不必更新带宽分配表；否则，网关节点需要根据以下情况更新带宽分配表：

① 网关节点与骨干1节点之间有小数据量数据通信（如Ping数据），网关节点与骨干2节点之间无普通数据通信。此时，网关节点将所有带宽都重新分配给骨干1节点。

② 网关节点与骨干1节点、网关节点与骨干2节点之间都有小数据量数据通信（如Ping数据）。此时，网关节点将所有带宽平均分配给骨干1节点与骨干2节点，并保证各自占有的数据时隙位置较为均匀。

③ 网关节点与骨干1节点之间有大数据量数据通信（如视频数据与FTP数据），网关节点与骨干2节点之间有小数据量数据通信（如Ping数据）。此时，网关节点将所有带宽中的大部分带宽分配给骨干1节点，并保证各自占有的数据时隙位置较为均匀。

④ 网关节点与骨干1节点、网关节点与骨干2节点之间都有大数据量数据通信（如视频数据与FTP数据）。此时，网关节点将所有带宽平均分配给骨干1节点与骨干2节点，并保证各自占有的数据时隙位置较为均匀。

在以上情况中，如果网关节点与骨干1节点或者网关节点与骨干2节点之间的数据通信结束，数据通信结束的节点需要以带宽申请的方式（意为取消带宽申请）通知网关节点，网关节点便可以在其他节点有新的带宽申请时将分配给数据通信结束的节点的带宽回收并重新分配给需要带宽的节点。最后，如果骨干1节点或骨干2节点都进行带宽申请，但带宽申请总量超过可分配带宽总量时，网关节点将按比例为带宽节点分配带宽。此时，需要带宽节点不需再次发送同样的带宽申请，直至某个节点的数据发送队列中的数据量又有新的变化。

1.2.3 链状网络情况

链状网络情况如图3所示。网关节点为骨干1节点分配带宽，骨干1节点为骨干2节点分配带宽。

（1） 骨干2节点正在入网。当骨干1节点收到骨干2节点发出的表示将要从骨干1节点处入网的入网请求包后，骨干1节点将按照骨干2节点的带宽申请量向网关节点申请带宽（即取消一部分网关节点分配给自己的带宽）。当网关节点取消一部分分配给骨干1节点的带宽后，骨干1节点再将这些带宽分配给骨干2节点。

图3 链状网络情况

（2） 骨干2节点入网后。骨干2入网后，如果网关节点与骨干1节点、骨干1节点与骨干2节点之间的普通数据通信均已结束，网关节点与骨干1节点均不必更新带宽分配表；否则，网关节点与骨干1节点需要根据以下情况更新带宽分配表：

① 网关节点与骨干1节点之间有小数据量数据通信（如Ping数据），骨干1节点与骨干2节点之间无普通数据通信。此时，骨干1节点将回收骨干2节点的带宽并以带宽申请的方式通知网关节点，网关节点再将所有带宽重新分配给骨干1节点。

② 网关节点与骨干1节点、骨干1节点与骨干2节点之间都有小数据量数据通信（如Ping数据）。此时，骨干2节点将向骨干1节点发出带宽申请，骨干1节点收到该申请后将结合了自己的带宽申请的带宽申请发送给网关节点。网关节点将带宽分配表中相应位置的数据时隙分配给骨干1节点，骨干1节点获得自己的带宽后再将其他可分配带宽分配给骨干2节点。

③ 网关节点与骨干1节点间有大数据量通信（如视频数据与FTP数据），骨干1节点与骨干2节点之间有小数据量数据通信（如Ping数据）。该处理过程与②过程类似，不再赘述。网关节点与骨干1节点、骨干1节点与骨干2节点之间都有大数据量数据通信（如视频数据与FTP数据）。该处理过程与②、③过程类似，不再赘述。

在以上情况中，如果网关节点与骨干1节点或骨干1节点与骨干2节点之间的数据通信结束，数据通信结束的节点需要以带宽申请的方式（意为取消带宽申请）通知其上游节点，上游节点便可以在自己有新的带宽申请时重新分配带宽或者向更上游节点重新申请带宽。最后，如果骨干1节点或骨干2节点都进行带宽申请，但带宽申请总量超过可分配带宽总量时，各个上游节点将按比例为需要带宽的节点分配带宽。此时，需要带宽的节点不需再次发送同样的带宽申请，直至某个节点的数据发送队列中的数据量又有新的变化。

1.3 数据时隙不再区分上下行

节点申请的带宽实际是数据时隙，这些数据时隙由带宽申请者与带宽分配者共享，即这些数据时隙只表明其归属哪对节点，不表明数据传输的上下行方向。数据传输的上下行方向由带宽分配者在每个数据时隙的开始临时决定。带宽分配者在自己的发送下行数据的需求与带宽申请者发送上行数据的需求进行权衡，并依据双方的数据业务类型与实时性要求决定每个时隙的上下行方向。当某一方向的数据传输结束后，该方向的数据时隙将全部用于另外一个方向的数据传输。

2 策略改进前后的性能比较

现对带宽申请与分配策略改进前后的性能比较进行定性分析，具体见表3。

3 结 语

提出了带宽申请与分配策略的改进方案，包括结合各类数据业务类型的带宽申请条件的描述、检查数据发送队列的时间间隔的描述、带宽分配最大化的描述、数据时隙不再区分上下行的描述。理论分析表明，改进后的方案能够提供精确的QoS保障并提高网络性能。

参考文献

[1] 雷昕，郭琳，韩仲华，等.宽带无线Mesh网络中的多扇区天线阵列设计[J].中国电子科学研究院学报，2012（4）：178?181.

[2] 李佳，周杰.无线Mesh网络集中式信道分配算法设计[J].无线电工程，2009（12）：3235?3237.

[3] 刘贺，张陆勇，陈明刚，等.无线Mesh网络集中式信道分配算法设计[J].无线电工程，2011（5）：4?6.

[4] 苏家勇，许磊，周国.无线Mesh网络中的信道分配问题研究[J].无线电通信技术，2009，33（5）：4?6.

[5] 张克非，杨寿保，胡云，等.基于多QoS参数约束的无线Mesh网络路由机制研究[J].计算机应用研究，2009，26（3）：994?996.

[6] 邱振谋，姚国祥，官全龙，等.多信道无线Mesh网络的多播信道分配算法[J].计算机工程，2011，37（6）：107?109.

[7] 李鹤松，冷甦鹏.一种新型无线Mesh网络多信道MAC协议[J].计算机工程与应用，2011，47（26）：66?69.

[8] 谢桂芳，段盛，罗玉玲.无线Mesh网络信道分配研究[J].计算机工程与应用，2011，47（18）：85?87.

[9] 韩冬，鄢楚平，王志泉，等.基于NDIS的无线Mesh网络协议的研究和实现[J].计算机工程与设计，2011，32（3）：784?787.

[10] 何萍实，徐子平.无线Mesh网络中使用双收发器的多信道MAC协议研究[J].计算机应用研究，2010，27（1）：327?329.

图3 链状网络情况

（2） 骨干2节点入网后。骨干2入网后，如果网关节点与骨干1节点、骨干1节点与骨干2节点之间的普通数据通信均已结束，网关节点与骨干1节点均不必更新带宽分配表；否则，网关节点与骨干1节点需要根据以下情况更新带宽分配表：

① 网关节点与骨干1节点之间有小数据量数据通信（如Ping数据），骨干1节点与骨干2节点之间无普通数据通信。此时，骨干1节点将回收骨干2节点的带宽并以带宽申请的方式通知网关节点，网关节点再将所有带宽重新分配给骨干1节点。

② 网关节点与骨干1节点、骨干1节点与骨干2节点之间都有小数据量数据通信（如Ping数据）。此时，骨干2节点将向骨干1节点发出带宽申请，骨干1节点收到该申请后将结合了自己的带宽申请的带宽申请发送给网关节点。网关节点将带宽分配表中相应位置的数据时隙分配给骨干1节点，骨干1节点获得自己的带宽后再将其他可分配带宽分配给骨干2节点。

③ 网关节点与骨干1节点间有大数据量通信（如视频数据与FTP数据），骨干1节点与骨干2节点之间有小数据量数据通信（如Ping数据）。该处理过程与②过程类似，不再赘述。网关节点与骨干1节点、骨干1节点与骨干2节点之间都有大数据量数据通信（如视频数据与FTP数据）。该处理过程与②、③过程类似，不再赘述。

在以上情况中，如果网关节点与骨干1节点或骨干1节点与骨干2节点之间的数据通信结束，数据通信结束的节点需要以带宽申请的方式（意为取消带宽申请）通知其上游节点，上游节点便可以在自己有新的带宽申请时重新分配带宽或者向更上游节点重新申请带宽。最后，如果骨干1节点或骨干2节点都进行带宽申请，但带宽申请总量超过可分配带宽总量时，各个上游节点将按比例为需要带宽的节点分配带宽。此时，需要带宽的节点不需再次发送同样的带宽申请，直至某个节点的数据发送队列中的数据量又有新的变化。

1.3 数据时隙不再区分上下行

节点申请的带宽实际是数据时隙，这些数据时隙由带宽申请者与带宽分配者共享，即这些数据时隙只表明其归属哪对节点，不表明数据传输的上下行方向。数据传输的上下行方向由带宽分配者在每个数据时隙的开始临时决定。带宽分配者在自己的发送下行数据的需求与带宽申请者发送上行数据的需求进行权衡，并依据双方的数据业务类型与实时性要求决定每个时隙的上下行方向。当某一方向的数据传输结束后，该方向的数据时隙将全部用于另外一个方向的数据传输。

2 策略改进前后的性能比较

现对带宽申请与分配策略改进前后的性能比较进行定性分析，具体见表3。

3 结 语

提出了带宽申请与分配策略的改进方案，包括结合各类数据业务类型的带宽申请条件的描述、检查数据发送队列的时间间隔的描述、带宽分配最大化的描述、数据时隙不再区分上下行的描述。理论分析表明，改进后的方案能够提供精确的QoS保障并提高网络性能。

参考文献

[1] 雷昕，郭琳，韩仲华，等.宽带无线Mesh网络中的多扇区天线阵列设计[J].中国电子科学研究院学报，2012（4）：178?181.

[2] 李佳，周杰.无线Mesh网络集中式信道分配算法设计[J].无线电工程，2009（12）：3235?3237.

[3] 刘贺，张陆勇，陈明刚，等.无线Mesh网络集中式信道分配算法设计[J].无线电工程，2011（5）：4?6.

[4] 苏家勇，许磊，周国.无线Mesh网络中的信道分配问题研究[J].无线电通信技术，2009，33（5）：4?6.

[5] 张克非，杨寿保，胡云，等.基于多QoS参数约束的无线Mesh网络路由机制研究[J].计算机应用研究，2009，26（3）：994?996.

[6] 邱振谋，姚国祥，官全龙，等.多信道无线Mesh网络的多播信道分配算法[J].计算机工程，2011，37（6）：107?109.

[7] 李鹤松，冷甦鹏.一种新型无线Mesh网络多信道MAC协议[J].计算机工程与应用，2011，47（26）：66?69.

[8] 谢桂芳，段盛，罗玉玲.无线Mesh网络信道分配研究[J].计算机工程与应用，2011，47（18）：85?87.

[9] 韩冬，鄢楚平，王志泉，等.基于NDIS的无线Mesh网络协议的研究和实现[J].计算机工程与设计，2011，32（3）：784?787.

[10] 何萍实，徐子平.无线Mesh网络中使用双收发器的多信道MAC协议研究[J].计算机应用研究，2010，27（1）：327?329.

图3 链状网络情况

（2） 骨干2节点入网后。骨干2入网后，如果网关节点与骨干1节点、骨干1节点与骨干2节点之间的普通数据通信均已结束，网关节点与骨干1节点均不必更新带宽分配表；否则，网关节点与骨干1节点需要根据以下情况更新带宽分配表：

① 网关节点与骨干1节点之间有小数据量数据通信（如Ping数据），骨干1节点与骨干2节点之间无普通数据通信。此时，骨干1节点将回收骨干2节点的带宽并以带宽申请的方式通知网关节点，网关节点再将所有带宽重新分配给骨干1节点。

② 网关节点与骨干1节点、骨干1节点与骨干2节点之间都有小数据量数据通信（如Ping数据）。此时，骨干2节点将向骨干1节点发出带宽申请，骨干1节点收到该申请后将结合了自己的带宽申请的带宽申请发送给网关节点。网关节点将带宽分配表中相应位置的数据时隙分配给骨干1节点，骨干1节点获得自己的带宽后再将其他可分配带宽分配给骨干2节点。

③ 网关节点与骨干1节点间有大数据量通信（如视频数据与FTP数据），骨干1节点与骨干2节点之间有小数据量数据通信（如Ping数据）。该处理过程与②过程类似，不再赘述。网关节点与骨干1节点、骨干1节点与骨干2节点之间都有大数据量数据通信（如视频数据与FTP数据）。该处理过程与②、③过程类似，不再赘述。

在以上情况中，如果网关节点与骨干1节点或骨干1节点与骨干2节点之间的数据通信结束，数据通信结束的节点需要以带宽申请的方式（意为取消带宽申请）通知其上游节点，上游节点便可以在自己有新的带宽申请时重新分配带宽或者向更上游节点重新申请带宽。最后，如果骨干1节点或骨干2节点都进行带宽申请，但带宽申请总量超过可分配带宽总量时，各个上游节点将按比例为需要带宽的节点分配带宽。此时，需要带宽的节点不需再次发送同样的带宽申请，直至某个节点的数据发送队列中的数据量又有新的变化。

1.3 数据时隙不再区分上下行

节点申请的带宽实际是数据时隙，这些数据时隙由带宽申请者与带宽分配者共享，即这些数据时隙只表明其归属哪对节点，不表明数据传输的上下行方向。数据传输的上下行方向由带宽分配者在每个数据时隙的开始临时决定。带宽分配者在自己的发送下行数据的需求与带宽申请者发送上行数据的需求进行权衡，并依据双方的数据业务类型与实时性要求决定每个时隙的上下行方向。当某一方向的数据传输结束后，该方向的数据时隙将全部用于另外一个方向的数据传输。

2 策略改进前后的性能比较

现对带宽申请与分配策略改进前后的性能比较进行定性分析，具体见表3。

3 结 语

提出了带宽申请与分配策略的改进方案，包括结合各类数据业务类型的带宽申请条件的描述、检查数据发送队列的时间间隔的描述、带宽分配最大化的描述、数据时隙不再区分上下行的描述。理论分析表明，改进后的方案能够提供精确的QoS保障并提高网络性能。

参考文献

[1] 雷昕，郭琳，韩仲华，等.宽带无线Mesh网络中的多扇区天线阵列设计[J].中国电子科学研究院学报，2012（4）：178?181.

[2] 李佳，周杰.无线Mesh网络集中式信道分配算法设计[J].无线电工程，2009（12）：3235?3237.

[3] 刘贺，张陆勇，陈明刚，等.无线Mesh网络集中式信道分配算法设计[J].无线电工程，2011（5）：4?6.

[4] 苏家勇，许磊，周国.无线Mesh网络中的信道分配问题研究[J].无线电通信技术，2009，33（5）：4?6.

[5] 张克非，杨寿保，胡云，等.基于多QoS参数约束的无线Mesh网络路由机制研究[J].计算机应用研究，2009，26（3）：994?996.

[6] 邱振谋，姚国祥，官全龙，等.多信道无线Mesh网络的多播信道分配算法[J].计算机工程，2011，37（6）：107?109.

[7] 李鹤松，冷甦鹏.一种新型无线Mesh网络多信道MAC协议[J].计算机工程与应用，2011，47（26）：66?69.

[8] 谢桂芳，段盛，罗玉玲.无线Mesh网络信道分配研究[J].计算机工程与应用，2011，47（18）：85?87.

[9] 韩冬，鄢楚平，王志泉，等.基于NDIS的无线Mesh网络协议的研究和实现[J].计算机工程与设计，2011，32（3）：784?787.

[10] 何萍实，徐子平.无线Mesh网络中使用双收发器的多信道MAC协议研究[J].计算机应用研究，2010，27（1）：327?329.