基于Ad Hoc无线传感网络的三维智能组网优化算法设计研究

金鑫，娄文忠，王辅辅

(北京理工大学 机电学院，北京100081)

0 引言

Ad Hoc 网络是一种不需任何固定基础设施支持便可实现互相通信的分布式自组织网络［1］，无中心、自组织、多跳路由、具有高度动态拓扑结构。因为具有分布性、动态性、自治性、移动性和异构性等特点，这种不同于蜂窝移动通信网和无线局域网的可自由组网的网络不仅适用于军事环境(战场)和灾难救助，在民用环境中(分布式计算和传感网络)也得到充分应用［2］。

每一个网络终端节点都带有一组无线收发的装置，使得终端具备路由器和主机两种功能，能通过自组织形成任意拓扑网络模型。但是，由于Ad Hoc 使用无线通信技术，具有无线通信系统信道质量低、带宽有限、节点通信距离有限等特点［3］。Ad Hoc 网络不能使用传统网络的通信方式，所以提出了很多针对性的路由算法。在Ad Hoc 网络的路由算法中，基于分群的算法是最有效的可伸缩算法。该算法的基本思想是把网络分为群，每个群有一个群首，群首节点负责群间信息的交换，这样既保证路由信息的准确性，又可以减少信息数量、提高网络效率［4］。目前最受关注的Ad Hoc 网络的路由算法有基于蚂蚁算法的分布式路由算法［5］和基于分簇的路由算法［6］。蚁群算法生成的网络结构中，所有节点地位平等、功能相同、鲁棒性较好，通信流量平均地分散到网络中，但是缺乏可扩展性、路由开销较大、能量消耗快。分簇算法将网络中的节点分成不同的簇，并分别对“簇首”和“簇员”节点指定不同的功能:1)减少参与路由计算的节点数量从而有效减少多余的洪泛;2)通过划分簇，将拓扑变化的影响限制在局部范围内，减少对路由协议带来的影响;3)成员节点的功能比较简单，无须维护复杂的路由信息，这大大减少了网络中路由控制信息的数量，减少了通信量［7］;4)分簇拓扑结构便于管理，有利于分布式算法的应用，具有较好的可扩展性，适合大规模网络［8］。

本文选取了分簇算法作为基础，在原有多种分簇路由算法基础上，根据实际需要首次提出了一种基于三维空间建立的新型分簇路由算法，优化了生成的拓扑结构，使得网络具有更好的动态性。

1 分簇路由算法

1.1 分簇路由结构

Ad Hoc 网络采用分布式控制结构，一般分为平面结构和分级结构。其中平面网络结构简单，对于小规模网络适用，平面网络拓扑图如图1所示。

图1 平面结构网络拓扑Fig.1 Planar structure of the network topology

分级网络采用分簇的方法，将网络节点分成若干簇群，每个簇群都由一个簇头和多个簇成员节点构成。簇头之间可继续进行分簇，形成更高一级的网络。簇头节点可通过预设获取或通过节点使用算法选举。簇头节点主要功能是实现簇结构的稳固、重组和通信，而簇成员只需维护、与簇头通信即可。

分级网络又可分为单频率分级和多频率分级两种［9］。如图2所示，单频率分级中，所有节点使用同一频率信号进行通信。为了簇头之间能正常通信，需要网关节点(同属两簇的节点)的支持。簇头和网关节点形成高一级的网络，成为虚拟骨干。

图2 单频率分级网络拓扑结构Fig.2 Single frequency hierarchical network topology

如图3所示，多频率分级网络不同网络级采用不同的频率进行通信。簇头节点有两个频率，以实现簇群内和簇群间的通信。其中:频率1 用于簇头与簇成员之间的通信，频率2 用于簇头之间的通信。

1.2 分簇算法描述

定义1 将Ad Hoc 网络抽象成无向连接图集G(V，E).其中:V 为网络中节点的集合;E 为网络中节点对的通信链路的边集合。eij=vivj(i，j=1，2，…)用来表示图集中存在一条从vi到vj的路径，即i 节点和j 节点是一对可互相通信的一跳邻居节点。

定义2 假定一个集合S⊂V 由一组网络节点构成。其中:S 为非空节点集。若v1∈S，∀v2∈S 满足v1和v2能互相通信，那么v1为簇头，S 为一个簇。若Si∩Sj=∅，i≠j，那么簇Si和簇Sj称为非交叠簇，反之为交叠簇。

图3 多频率分级网络拓扑结构Fig.3 Multi-frequency hierarchical network topology

定义3 对于具有簇头v1的簇S，如果簇内任意节点v2到簇头的距离最多为k 跳，那么该簇被称为k 跳有头簇［10］。

定义4 一个节点的一跳邻居节点的个数被称为该节点的度数dv.

本文的新型算法基于多频率分级网络进行设计，不具有网关节点，即建立满足度数需求的一跳有头非交叠簇。最终目标是构建一个覆盖所有网络节点，计算和通信开销少，网络拓扑稳定的分簇网络。

2 三维智能组网优化算法

2.1 算法设计思想

本文在研究了最小ID 算法、最大节点度算法和块合并算法3 种典型的分簇算法的基础上，提出了一种基于三维智能组网的新型分簇算法。

通过检测计算，选取相邻节点距离符合传输范围、邻节点与簇头节点距离之和大、存活的网络节点成为该网络中的簇头，提高网络稳定性、减小节点最大负载。该算法具有如下4 个特点:

1)簇头通过按需自适应进行选举产生，不是周期性产生。

2)算法的更新是按需的，而不是周期的，降低了网络维护的开销。

3)通过限制节点的信号传输范围，减少远距离节点之间的连接，使得邻节点与簇头节点距离小，节省节点能量，延长网络生存时间。

4)通过给定节点度数的要求选择适合的簇头节点，优化簇结构，减少网络负载，提高信息传输效率。

2.2 算法过程描述

应用本算法的网络节点上装载有GPS 定位和高度传感器，以获得网络节点相对于地球坐标系的局部三维坐标，执行算法获得最优簇头及簇结构。算法过程如下:

1)检测节点的能量Pvi，若Pvi≠0，节点存活;否则，节点死亡。

2)若节点存活，通过GPS 定位和高度传感器获得三维坐标，并对每个节点进行ID 定义.

3)根据普通节点的传输范围，确定能互相进行通信的一跳节点。记录下一跳网络节点间的距离，并建立距离表。

4)记录每个节点vi的所有邻居节点数，即节点vi的度数，用dvi表示。

5)记录节点vi和其所有邻节点，构成节点集N(v).

6)根据距离表计算节点vi到其所有一跳邻居节点的距离总和

7)计算节点vi的权值

式中:ω1和ω2为不同参数的权重，ω1+ω2=1.

8)根据需求定义最优度数，即最优簇成员数，用σ 表示。

9)选择具有最大Wvi的节点成为簇头节点，选择小于等于σ 个节点作为簇成员。所有已选择的簇头节点及簇内成员不再允许进入簇头选择。

10)删除被选取的节点后，重复权值判断，直至所有节点均成为簇头或簇成员。

11)判断簇成员数是否小于最小度数要求，如果不符合，将簇连接到距离近的簇形成新簇。

12)算法结束。

2.3 算法优点

相对于以往的各类分簇算法，该算法具有如下优点:

1)三维网络算法在二维算法基础上，增加了高度差，模型更接近真实情况。

2)通过实际检测定位减少了相对定位的计算，不仅运算量减少，精度也大大增加。

3)通过限制节点的传输范围，减少了远距离点的连接，删除了大量链路，使得距离表更简洁，数据量减少。

通过最优度数及最小度数的选取，在满足实际需求的基础上，使得簇群数量尽可能少，简化二级簇头网络。

3 仿真分析

根据上述算法，建立如下的模拟环境:实际需求仿真场景区域为700 m ×200 m ×1 m，随机生成24 个网络节点分布其中。节点的传输半径选取为为区域宽度。由于节点加入了GPS 定位和高度传感器，节点能够获知其在网络中的地理位置，网络拓扑结构容易得到。在模拟中通过传输半径来衡量节点是否能够进行通信，节点距离如果大于半径，视为不能通信连接，即在网络拓扑结构中两节点不存在连接边。取权重ω1=0.95，ω2=0.05.

通过数学软件Matlab 仿真建模，输出在未建立分簇算法时的三维及二维网络拓扑结构，以及分簇后的结构;通过对比，对算法进行评估。

3.1 生成网络

现有的网络拓扑随机生成器，很难生成比较理想的网络拓扑结构，本文通过Matlab 软件，在随机抛撒节点的时候使用K 均值聚类算法，使得生成的节点分布和真实情况类似。并根据传输半径要求，形成平面拓扑结构，如图4所示为三维网络拓扑结构，如图5所示为二维网络拓扑结构。

图4 三维网络拓扑结构Fig.4 Three-dimensional network topology

从图4、图5可看出，直接生成的网络拓扑结构复杂，节点间通信较为复杂，时延较高、维护费用高且稳定性不高。

通过新型三维分簇算法优化后，可得到分簇网络拓扑结构。如图6所示为三维网络分簇拓扑结构，如图7所示为二维网络分簇拓扑结构。

图5 二维网络拓扑结构Fig.5 Two-dimensional network topology

图6 三维网络分簇拓扑结构Fig.6 Three-dimensional network clustering topology

图7 二维网络分簇拓扑结构Fig.7 Two-dimensional network clustering topology

图6、图7中的网络被分成了4 簇，24 节点属于孤立簇头，于是被连接到20，使24 节点成为簇成员，簇4、簇9、簇18、簇20 分别在簇内形成一级网络，簇头4、簇9、簇18、簇20 形成二级网络，两级网络信号频率不同。可发现网络获得了极大的优化，拓扑结构变得简单，节点通信简化，时延减少，维护费用低，并且网络稳定。

3.2 簇头数

簇头数是评价一个分簇网络的重要指标，本算法通过控制最优度数，使得簇头数最小值为4，随机选取多次仿真数据观察，发现簇头数在4 ～5 之间波动，由于规定了最少簇成员数大于等于3，所以使得分簇结果良好，如图8所示为随机仿真的簇头数图。随着传输半径的增加，每个节点可与剩余所有点连接，所产生的簇数将恒等于4.

图8 随机簇头数图Fig.8 The figure of random cluster-head

3.3 分簇平衡度

另一个衡量分簇算法性能的指标就是分簇的平衡度。由于最优度数及最少簇成员数的限制，使得每个簇中的节点大致是等同的，簇的分布均匀、平衡度较好。这里选择用节点数目的标准差来作为衡量平衡度的标准。通过多次仿真实验得到平衡度的统计，如图9所示，标准差基本在0 ～2 之间波动，说明簇的平衡度良好、节点分布均匀。

图9 平衡度统计图Fig.9 Statistics figure of balance

4 结论

通过上述仿真可看出，网络拓扑结构经过新型的三维智能分簇组网算法优化后，远距离传输节点减少，参与路由计算的节点数量减少，网络复杂度明显降低，网络的分簇平衡度良好，分簇均匀，从而节省了节点的能量消耗，使得网络中节点的存活率延长，降低了网络重构的概率，同时提高了网络的抗毁能力。仿真结果验证了这种新型分簇算法可以较好地应用于Ad Hoc 网络等具有动态网络拓扑的网络中。

本文主要通过理论分析来研究新型的三维智能分簇组网算法，而在实际的工程应用中，限定节点间的传输距离、节点间存在障碍物等问题可能会对算法的实现造成一定的影响。在下一步工作中，将通过实物仿真来进行算法进一步的优化设计。

References)

［1］徐佳，李千目，王永利，等. 一种Ad Hoc 网络动态路径压缩技术［J］. 兵工学报，2010，31(6):811 -819.XU Jia，LI Qian-mu，WANG Yong-li，et al. A path compression technique based on dynamic model in Ad Hoc demand routing protocols［J］. Acta Armamentarii，2010，31(6):811 -819.(in Chinese)

［2］陈冬松，刘治国，王光兴. 移动Ad Hoc 网络管理中基于节点定位的簇生成算法［J］.兵工学报，2007，28(10):1200 -1204.CHEN Dong-song，LIU Zhi-guo，WANG Guang-xing. A clustering algorithm based on node location in the mobile Ad Hoc network management［J］. Acta Armamentarii，2007，28(10):1200 -1204.(in Chinese)

［3］金鑫，张尧学，王洪波.一种Ad Hoc 网络中动态自适应的路由更新算法［J］. 小型微型计算机系统，2005，26(12):2078 -2081.JIN Xin，ZHANG Yao-xue，WANG Hong-bo. Dynamically self-adaptive routing update algorithm for Ad Hoc networks［J］. Mini-Micro Systems，2005，26(12):2078 -2081.(in Chinese)

［4］赵春晓，王光兴. 无线网络中基于最高向量权独立集的分群算法［J］. 兵工学报，2004，25(5):591 -594.ZHAO Chun-xiao，WANG Guang-xing. A clustering algorithm based on highest vector-weighted independent set in wireless network［J］. Acta Armamentarii，2004，25(5):591 -594. (in Chinese)

［5］Zheng X Q，Guo W，Liu R T. An ant-based distributed routing algorithm for Ad-Hoc networks［C］∥International Conference on Communications，Circuits，and Systems. Chengdu:IEEE，2004:412 -417.

［6］Mario G，Taek J K，Pei G. New cluster formation method for efficient flooding in Ad Hoc networks［C］∥Proceedings of WCNC.Orlando，Florida:WCNC，2002.

［7］沈波，张世永，钟亦平. 无线传感器网络分簇路由协议［J］.软件学报，2006，17(7):1588 -1600.SHEN Bo，ZHANG Shi-yong，ZHONG Yi-ping. Cluster-based routing protocols for wireless sensor networks［J］. Journal of Software，2006，17(7):1588 -1600.(in Chinese)

［8］徐佳，李陟，李千目，等. Ad Hoc 网络中一种自适应分簇路由过渡协议［J］.通信学报，2008，29(3):54 -62.XU Jia，LI Zhi，LI Qian-mu，et al. Adaptive clustering routing transition protocol in Ad Hoc networks［J］. Journal of Communications，2008，29(3):54 -62.(in Chinese)

［9］王金龙，王呈贵. Ad Hoc 移动无线网络［M］.北京:国防工业出版社，2004.WANG Jin-long，WANG Cheng-gui. Ad Hoc mobile wireless networks［M］. Beijing:National Defense Industry Press，2004. (in Chinese)

［10］郑少仁，王海涛，赵志峰. Ad Hoc 网络技术［M］. 北京:人民邮电出版社，2005.ZHENG Shao-ren，WANG Hai-tao，ZHAO Zhi-feng. Ad Hoc network technology［M］. Beijing:Posts ＆ Telecom Press，2005.(in Chinese)