无线Mesh网络结构的拓扑控制策略

邓建良，王 景，胡松华，郭建丁

（重庆大学通信工程学院，重庆400044）

0 引言

拓扑控制机制从研究方向可归纳为节点功率控制和层次型拓扑结构组织两类。无线网络中的层次型拓扑结构由于具有通信量少、可扩展性强、能量利用效率高及适合大规模部署等特点，成为当前拓扑控制研究的重点。

提出一种新的网络架构并在此基础上研究一种虚拟的层次化拓扑控制策略，主要考虑相邻簇间的自身负载和相互转发负载的平衡，提高网络的公平性、提升链路可靠性以及提高路由算法的有效性。

1 问题说明

该文研究的前提是，无线Mesh网络的簇都分配了足够等量的信道资源，从而保障通信的公平性和链路的可靠性。在一定节点分布的情况下，节点不但自身通信产生负载，而且节点同时要转发产生负载。图1中，簇1和簇4仅仅只是簇内节点间通信和与内外簇间的通信。而簇2和簇3不仅要承担自身通信与簇间通信，还要转发簇间的通信。簇2和簇3的通信负载相对大很多，网络中处于中间转发位置的节点承担相对较多的负载，缺乏公平性。同时网络的容量和可靠性依赖于中间位置的簇。

图1 簇的通信状况

新的划分簇的方法主要从2个方面来分析:覆盖范围和容量。其次簇大小的划分也必须考虑信道资源的分配，尽量使其每个虚拟簇内的节点都满足信道匹配。必须要强调的是网络考虑覆盖范围，同时要达到公平性的网络基本要求。

根据新的网络架构—虚拟层次无线Mesh网络结构，提出一种拓扑控制策略，拓扑控制策略主要应用于簇间的控制。在极值情况下，其拓扑控制能量域为。在图2中，一个点代表一个簇。这是一个由7个簇组成的链型拓扑。在这种情形下，每个簇仅仅为相邻节点转发数据报和发送自身与其他节点的通信数据。簇1和簇7与其他簇的通信都经过其相邻簇转发，而其本身仅仅承担簇内部通信和与相邻簇的通信。n为网络某一侧中虚拟簇的数量;H（d）为虚拟节点ci与ci-1之间的链路容量;li为节点虚拟簇半径;R（li）为li内部流量负载其中RD是指每个用户内部平均流量，DM指节点密度虚拟簇2个簇间流量负载其中RZ是指每个用户内部平均流量，DM指节点密度;虚拟簇中所有的流量负载应该受到蜂窝饱和吞吐率的限制，即:R（li）≤Rb（k），其中，Rb（k）表示饱和吞吐率。根据文献[4]中的方法，对于用户数量k，IEEE 802.11 b WLAN的单元饱和吞吐量可以使用曲线拟合的方法获得，即则簇2转发的流量是簇3转发流量是簇4转发流量是在等半径的情况下，内部流量负载和虚拟簇间流量负载是相等的。所以簇2的转发流量为5R（lin），簇3转发流量为8R（lin），簇4的转发流量为9R（lin）.

图2 簇数目为7的链型拓扑和转发流量图

可以很明显看出簇的流量负载是不均衡的，网络的性能将受到中间簇的限制。所以该文提出一种新的簇划分方法，根据其总的流量来改变簇的覆盖范围，达到簇间流量和转发流量之和在每个簇中都是相等的。由此其簇的划分为图3所示。

图3 负载均衡簇的分配方式

将转发流量大簇缩小其覆盖范围，保障簇内部节点能够正常通信，从而保障通信的可靠性和公平性。它们覆盖半径之间关系是:

以2种簇拓扑进行研究，图4和图5分别是虚拟簇半径相等和虚拟簇半径逐渐增大的拓扑，为便于分析，用位于小区中心的虚拟节点表示每个小区，实际上节点可位于小区内任何位置。为了用连接图来表示这种虚拟层次网络结构的拓扑，邻居虚拟节点用一条边连接，均给出了对应的Mesh网络拓扑结构。

图4 虚拟簇半径相等的拓扑形式

图5 虚拟簇逐渐增大的拓扑形式

从组合图论的角度，可以知道簇半径相等和簇半径逐渐增大拓扑在等分带宽上是相同的，所考虑的是链路的等分带宽，但是，如果考虑信道资源分配，虚拟簇中节点有些链路不是活跃的;如果考虑链路的活跃性，则可以知道簇半径逐渐增大的拓扑在等分带宽性能上优于等半径拓扑，因为在理想情况下，簇半径逐渐增大的拓扑可以是信道资源分配和簇节点完全匹配。

2 算法规则

在图3中，由于簇的划分是对称的，考虑其中的上半部分，定义一些参数:n为网络某一侧中虚拟簇的数量;di为小区中心的虚拟节点ci于ci-1之间的距离;H（di）是虚拟节点ci与ci-1之间在间距为di情况下的链路容量;li为节点ci的蜂窝半径;R（li）为到达ci的流量负载，其中RD是指每个用户平均流量，DM指节点密度;δ（n）为代价函数，指部署一个虚拟簇所需代价;R（s）是指从其他虚拟簇接收到的流量与本簇转发出流量差值。

接下来，介绍2种虚拟簇划分策略:等半径虚拟簇的划分和半径逐渐增大的划分策略。2个虚拟中心节点的间距可以描述如下:di=li+li+1，i=1，2，…，n。虚拟簇中所有的流量负载应该受到蜂窝饱和吞吐率的限制，即:R（li）≤Rb（k），其中，Rb（k）表示饱和吞吐率。根据文献[3]中的方法，对于用户数量k，IEEE 802.11b WLAN的单元饱和吞吐量可以使用曲线拟合的方法获得，即:Rb（k）=b1eb3k+b2eb4k。故虚拟簇的总流量为

等半径情况下:

半径逐渐增大情况下:

在该网络中，虚拟簇的划分问题可以描述成一个混合整数非线性编程（MINLP）问题，其中决策变量包括n和l0，l1，…，ln。MINLP问题的目标是使虚拟簇的总体负载流量与划分簇的代价函数比值达到最大化。于是有目标函数:

对于等半径情况下有目标函数:

半径逐渐增大情况下有目标函数:

算法流程如图6所示。

定理1:任何满足簇的域内连通性和互通性的模型，必定具有拓扑连通性。

证明:∀u，u′∈V，假定u∈Vi，u′∈Vj，因拓扑具有簇的域内连通性和互通性，则u和u′之间一定存在一条路径（u，ci，…，ck，cm，…，cj，u′）。

定理2:当d满足时，拓扑内簇群必定满足域内连通性和簇间邻接可达性。

图6 算法流程

证明:由簇满足域内连通性则必有d≤dmax。假定簇Cj具有最大规模d，且d（k，m）=d，其中k，m∈Vj，因此可知簇Cj内其他节点必位于图所示区域akcm内，为满足簇间邻接可达性，若节点a与b可直接通信，必能保证相邻簇区域内任意2节点可直接通信，由图易得簇群必定满足域内连通性和簇间邻接可达性，证毕。

图7 簇规模与簇区域关系图

3 结束语

从拓扑控制出发，探讨一种能够增大网络容量且保证网络可靠性的拓扑结构。通过对随机拓扑和2种规则拓扑的网络容量和拓扑特征分析，表明了规则拓扑在无线Mesh网络应有的优良性能。该文提出的方案对现有无线Mesh网络结构改动较小，主要工作是在网络帧结构中添加虚拟分簇标志和组网拓扑方式等调整，易于工程实现。

[1]SANTI P.Silence is golden with high probability:Maintaining a connected backbone in wireless sensor networks[C]//1st European Workshopon WirelessSensor Network，2004，2（9）:9-20.

[2]XIONG Shu-ming，WANG Liang-Min，WU Ji-Ying.Energyefficient hierarchical topology control in wireless sensor networks using time slots[C]//Proceedings of the Seventh International Conference on Machine Learning and Cybernetics，Kunming，12-15 July 2008:33-39.

[3]徐俊明.组合网络理论[M].北京:科学技术出版社，2005.

[4]PERILLO M，ZHAO C，HEINZELMAN W.On the problem of unbalanced load distribution in wireless sensor networks[C]//Proceedings of the IEEE Global Telecommunications Conference Workshops.Piscataway，NJ，USA:IEEE，2004:74-79.

[5]CHEN J C.Measured performance of 5GHz 802.11a wireless LAN systems[S].White Paper of Atheros Communications，2001.8.

[6]GUPTA P，KUMAR P R.Thecapacityofwireless networks[J].IEEE Trans.Inform.Theory，2000，46（2）:388-404.

[7]TOUMPIS S，GOLDSMITH A J.Capacity regions for wireless ad hocnetworks[J].IEEE Transactions on Wireless Communications，2003，2（4）:736-748.

[8]SILVESTER J，KLEINROCK L.On the capacity of multichip slotted ALOHA networks with regular structure[J].IEEE Trans.Commun.，1983，31（8）:974-982.