基于无线传感器网络的拓扑图自动布局法优化与实现

基于无线传感器网络的拓扑图自动布局方法优化与实现

基于无线传感器网络的拓扑图自动布局法

优化与实现

摘要：本文在扩展力学模型拓扑布局算法的基础上，完善了其平衡检测算法，通过加入防碰撞检测算法，保证节点不会超出画布范围；同时，引入拓扑居中算法优化其布局效果。并将优化后的布局算法应用于WSN拓扑结构可视化系统中，通过仿真测试以及在真实WSN环境下实验验证，优化后的算法能适用于WSN网络拓扑结构布局，尤其是对小规模WSN能布局出较高的可视化效果。 关键字：扩展力学模型;WSN;拓扑;可视化;优化

Optimization and implementation of automatic topology layout method based on wireless sensor

network

Abstract：This paper, which is based on the topology layout algorithm in extended mechanic model, made an improvement of its balance detection algorithm, adding anti-collision detection algorithm, to ensure that the nodes will not exceed the scope of the canvas; the method introduced a topological centering algorithm to optimize the layout effects, and applied the optimized algorithm to WSN topology visualization system. After the simulation tests and the experimental verification in a real WSN environment, the optimized algorithm is verified appropriate for the topology layout of WSN network, especially useful for miniature WSN networks.

Keywords: Extended mechanical model; WSN; Topology; Visualization;

Optimization

1

1 引 言

目前，随着无线传感器网络的快速发展，实现对WSN的有效管理成为又一重要研究内容。其中，能及时反映WSN网络特性的WSN拓扑成为整个网络管理的基础研究内容。通过清晰的拓扑结构图，管理者不仅可以直观地监测实时网络状态，而且还可以及时发现并解决相应的网络问题[1]。WSN拓扑结构可视化主要依托拓扑发现和拓扑自动布局两种关键技术。其中，拓扑发现主要是根据节点邻居信息来进行，该技术较为成熟，容易实施；拓扑自动布局技术则由于受到WSN动态拓扑特性以及网络复杂性的限制，使得其在WSN拓扑布局上应用较少[2]。因此，实现拓扑结构自动布局成为WSN拓扑结构可视化的重要突破点之一。

当前主要的自动布局方法有如下几种：（1）层次布局，该方法主要适用于有向连通图。该布局算法较复杂，实现难度高[3-4]。（2）环形布局，该方法主要以父节点为圆心，指定半径绘制子节点，并遍历递归实现整个拓扑布局[5]。该布局方法简单、容易实施，但多适用于树形拓扑布局，且布局效果一般。（3）混合拓扑布局，该方法采取分治策略，在同一个网络的不同局部采用不同的布局方法

[6-7]

。该布局方法多被用于大规模复杂网络布局，且该方法较复杂，有一定实施

难度。（4）力学模型布局，其通过力学平衡来实现拓扑布局。该方法复杂度较低，能达到一定质量的布局效果[8-10]。以上布局方法大多适用于特定网络的拓扑结构布局，且布局效果质量不高，而文献[11]中由吕亮、卢泽新等在力学模型基础上提出的基于扩展力学模型的布局算法，不仅继承了力学模型的优点，还解决了大多数拓扑布局算法中点线交叉的问题，能获得较好的布局效果，且该算法复杂度较低，能够适用于复杂的WSN。

然而，扩展力学模型布局算法更多地关注拓扑结构内的布局效果，对其在实际应用中的布局效果未进行深入研究，如算法在通过迭代方式动态计算节点坐标时，节点坐标可能超出画布范围，并影响实际布局效果等。本文在扩展力学模型的基础上，完善了其平衡检测算法，并引入碰撞算法以及拓扑居中算法优化了扩展力学模型下布局的WSN拓扑结构图，并对优化后的扩展力学模型布局算法进行了仿真以及实例验证。

2基于扩展力学模型的布局方法

在扩展力学模型布局算法中，将每个节点看作带相同电荷的质点。节点与节点之间存在电荷斥力，防止节点重合；将邻居节点之间存在的边看作是具有伸缩性的弹簧，防止了节点间相离过远；同时也定义节点与不相邻边之间存在斥力，以此防止节点与边相距太近甚至重合。

该算法的具体实现：首先，在画布布局区域内给各节点随机分配坐标；然后，根据扩展力学模型，对各节点进行受力分析；最后根据力学分析结果驱动节点沿合力方向移动，并不断迭代更新合力，直到各节点所受合力为零，即系统重新处于平衡态时，停止布局。在实际布局时，可假设系统小范围震荡作为系统达到平衡态的判断条件。

节点所受相应边的张力与该边长度成正比关系，当其长度小于定义原长时张力为0，根据胡可定律可得如下计算公式：

?k*S?ui,uj??C?bk?,S?ui,uj??C?bk??R?ui,uj,bk???,S?ui,uj??C?bk???0

(1)

式（1）中：R(ui,uj,bk)是节点ui 、uj受到边bk的张力；k为弹力系数，通常取k=1；S(ui,uj)为边bk的实际长度；C(bk)为定义的边初始长度，即原长。

节点与节点间的斥力是相互的，其与节点间的距离成反比，与节点所带电荷量成正比关系，其物理公式如下：

Q?ui,uj??g*G(ui)*G(uj)?S(ui,uj)2???H?,,S(ui,uj)?0S(ui,uj)?0

(2)

式（2）中：Q(ui,uj)为节点ui、uj间产生的排斥力；G(ui)、G(uj)分别为节点ui、uj所带电荷量，通常G(ui)=degree(ui),其中degree(ui)为节点ui度数；H为一个常量；g为斥力系数，g越大，布局越稀疏，通常取g=C(bk)2。

节点与不相邻边之间的斥力大小跟节点与该边的距离成反比关系，当且仅当节点在不相邻边上存在投影点时斥力存在。理想情况下，当节点与不相邻边重合时，其斥力为0，但考虑实际布局，可设定一定距离时其斥力为0。根据胡可定律可得其公式：

W?ui,bj??k*S?ui,bj??d,???,??0S?ui,uj??dS?ui,uj??d

(3)

式（3）中：W(ui ,bj)为节点ui受到不相邻边bj的斥力；k为胡可常数，通常取1；d为设定的最小距离，根据网络节点规模具体取值；S(ui, bj)为节点ui到边bj的垂直距离。

3 自动布局方法的优化设计

3.1 震荡检测算法

基于扩展力学模型的布局算法虽然给出了布局结束的判定条件，即当整个系统达到力平衡或者部分节点在小范围内震荡时布局结束，但并未给出实际的震荡检测算法。本文实现了如下的震荡检测算法，完善了扩展力学布局算法。震荡检

测算法具体描述如下，其中balanceFlag为判断节点小范围震荡标志，di、dmax分别为节点ui沿合力移动距离、最大移动距离。

Input：各节点ui坐标（xi,yi）及受力值F； Output: 平衡检测标准变量balanceFlag； Step1. 遍历各个节点ui，计算出每个节点

沿合力方向移动的距离di，并找出所有节点中的最大移动距离dmax；

Step2. 震荡检测，如果最大移动距离

dmax<约定最小震荡距离d,则节点小范围震荡，将震荡标志balanceFlag置1；

以上算法实现了网络节点震荡检测及震荡判断。同时，为了避免节点在约定节点最小震荡距离以外震荡，导致布局陷入死循环，本文还增加了一个最大布局迭代次数Imax变量作为布局结束的另一个辅助判断条件。

3.2 布局效果优化算法

扩展力学布局算法以节点和边为重点布局对象，在实际画布中进行布局拓扑时，未考虑节点在震荡过程中，其坐标位置可能偏离画布布局范围，以致影响整个WSN拓扑布局效果，或者在整个拓扑布局结束时，即使无节点偏离画布，但布局好的拓扑图任然可能整体偏向于画布的一侧，降低了拓扑图可视化效果。为此，本文增加了防止节点偏离画布范围的碰撞算法和优化布局结果的拓扑居中算法，其具体描述如下所示，其中w、h分别为画布的宽度、长度，xi 、yi分别为节点ui的横、纵坐标，xmin、xmax分别为最大、最小横坐标，ymin、ymax分别为最大、最小纵坐标。 碰撞算法：

Input：各节点ui坐标(xi,yi)；

Output: 各节点碰撞更新后的坐标（xi,yi）；

Step1. 遍历拓扑结构中每个节点ui,判断

节点的横坐标xi是否超出画布横

标xiw更新为靠近相应横向边界一向范围，若超出，则此节点横坐 定范围内的随机坐标；节点的横坐标yi是否超出画布的

Step2. 遍历拓扑结构中每个节点ui，判断

纵向范围h，若超出，则此节点纵坐标yi更新为靠近相应垂直边界一定范围内的随机坐标；

拓扑居中算法：

Input：各节点ui坐标(xi,yi);

Output: 各节点居中更新后的坐标（xi,yi）； Step1. 遍历拓扑结构中的每个节点ui，

找出最小横坐标xmin、最大横坐标xmax， 找出最小纵坐标ymin、最大纵坐标ymax；

Step2. 遍历拓扑结构中的每个节点ui，根据推导公

式居中更新节点坐标, xi = xi +(w-xmax-xmin)/2, yi = yi +(h -ymax-ymin)/2；

4拓扑图布局的实现

4.1 软件实现平台

本文在Qt平台上对优化后的扩展力学模型布局方法进行了具体实现。Qt是一个基于C++的GUI应用程序架构，其良好的跨平台特性以及优秀的signals/slots编程机制成为我们选择其作为算法实现平台的重要依据[12]。

4.2 软件的整体流程图

图1详细描述了WSN拓扑布局的程序流程：首先，获取拓扑结构中各节点的基本信息（包括本节点编号ID、本节点的邻居节点编号ID、节点类型），并构建邻接矩阵信息（即获取节点邻居关系；同时，初始化各节点其他变量（合力F、边张力P、节点斥力Q、边斥力W以及坐标值等）。然后，遍历一维节点数组U，给每个节点在画布范围内随机分配坐标(xi,yi)。接着，采用优化后的力学模型布局方法对WSN拓扑进行布局。其中，Imax为最大迭代次数，这里设置为2000；balanceFlag为系统平衡标志；dx、dy为节点沿合力F方向移动的距离；w、h分别为画布的长、宽。最后，使用QT提供的画图工具QPainter，根据布局后的WSN拓扑信息绘制出整个拓扑结构图。

本文在具体实现代码时，合力F、边张力P、节点斥力Q、边斥力W均以正交分解在X、Y轴上的分力来代替。

本文来源：https://www.bwwdw.com/article/pt3d.html