无线传感器网络基于相交圆结构的改进GAF算法

梁 青，李卓冉，曹晓民，熊 伟

（1.西安邮电大学 电子工程学院，陕西 西安710061；2.空军工程大学 信息与导航学院，陕西 西安710077）

0 引 言

在无线传感器网络中，拓扑控制不仅仅是一项节能技术，还能够保证网络连通性和覆盖率，减少通信干扰，为路由协议和数据融合提供拓扑基础，有效保证网络的扩展性和可靠性，提高网络的整体性能［1－4］。因此，高效优化的拓扑控制机制是十分重要的，良好的拓扑控制算法可以降低节点能量消耗，延长网络生存时间［5，6］。GAF 算法是层次结构的拓扑控制机制中一种典型的自适应分簇算法，通过节点所处的地理位置来进行活动节点的选择。该算法的主要目标是选择少量的节点来维持网络连通度，减少网络总能量的消耗。GAF算法的执行过程包括两个阶段，第一个阶段是根据节点的地理位置进行虚拟单元格的划分，第二个阶段是在划分出的每个单元格中选择合适的簇头节点，也就是该单元格中的活动节点。文献 ［7］提出了一种新型的层次型拓扑结构生成算法，并通过设置节点度来形成最优的拓扑结构。文献 ［8］在蜂窝结构的基础上将区域划分为圆形，并将重叠区域作为中转区域。文献 ［9］中采用定期自动划分虚拟单元格的方法划分单元格，并在每个单元格中寻找最节约能耗的簇头位置。本文根据相关研究，提出了一种基于相交圆结构的改进GAF算法。

1 网络模型与能耗模型

1.1 网络模型

（1）监测区域内的所有节点均不可移动，节点的初始能量相同且能量有限。

（2）节点已知整个监测区域的位置信息和自身的位置信息。

（3）节点具有一定的计算能力和数据存储转发能力。

1.2 能耗模型

在无线传感器网络中，节点的能耗基本都用于数据通信。因此，本文采用的能耗模型只考虑节点收发数据时的能耗。假设网络中的节点传输l比特的数据，则其发送和接收数据的能耗分别为

2 虚拟单元格的划分

在GAF算法中，对监测区域进行单元格划分时只考虑到连通度的问题，GAF算法要求相邻两个单元格内的任意两个节点能够直接通信，如图1 （a）所示。文献 ［10］提出另一种相邻区域的关系，如图1 （b）所示，可保证每个单元格内的节点与周围相邻的8个区域能够直接通信。

图1 正方形结构模型

本文在图1 （b）的基础上提出一种相交圆结构模型，如图2所示。以每个正方形的中心为圆心，正方形的对角线长度为直径作外接圆。由图2可以看出，相交圆结构模型可以增大节点单跳范围内的覆盖面积，且可以增加一个单元格中的节点个数。

图2 相交圆结构模型

假设每个节点的通信半径为d，则传统GAF 算法中虚拟单元格的边长应满足

同样的，图1 （b）的正方形结构和图2的相交圆结构中的单元格边长为

因此，可以得到3种结构模型下节点单跳范围内的覆盖范围分别为

由式 （5）～式 （7）可知，在划分虚拟单元格时，相交圆结构模型下的节点单跳覆盖面积比图1 （b）的正方形结构增加了约21.4%，而与传统GAF算法相比较增加了约33.9%。

当单元格内节点个数增加时，网络生存期会相应的延长。因此，在网络中节点密度不变的情况下，增大每个单元格的面积，增加单元格内的节点个数，可以达到延长网络的生存期的目的。在二维监测区域中，每个单元格内保持网络连通所需要的最少节点数为M，网络的最短生存期为T，则每个单元格中平均节点数为

网络的生存期为

式中：X——一个大于1的常数且0＜qT。

假设N 个节点随机均匀分布在面积为S的监测区域中，则节点的平均密度为在图1 （b）结构中，每个单元格中的平均节点数为

而在相交圆结构中，每个单元格中的平均节点数为

比较式 （10），式 （11），由S3＞S2可推算出n3＞n2。因此，根据式 （8），式 （9）可知，相交圆结构中的X 值要大于图1 （b）结构中的X 值。从而在不考虑网络最短生存期的情况下，相交圆结构可以更好的延长网络生存期。

3 簇头节点及中转节点的选择

3.1 簇头节点的选择

在簇头选举阶段综合考虑单元格中每个节点的剩余能量、吞吐率和到基站的距离来进行合理的簇头选举，以达到均衡节点负载，减少节点能量消耗的目的。

在理想情况下，监测区域中每个节点的吞吐率应满足以下关系式

式中：A——监测区域面积，W ——传感器节点的最高传输速率，Δ——大于0的常数，L——节点到基站的距离，n——节点的个数，r为理想球状无线电发射模型的发射半径［11］。

设节点的剩余能量为E0，吞吐率为λ，到基站的距离为d0，定义如下簇头选择函数

式中：α、β、γ——大于零的影响因子，且α＋β＋γ ＝1，影响因子的大小取决于对网络性能的综合要求，d为节点的通信半径。在每个簇中选择函数f值最大的节点作为簇头。由式 （13）可以看出，节点的剩余能量和吞吐率越大且节点到基站的距离越近，节点成为簇头的概率就越大。

3.2 中转节点的选择

根据本文中提出的相交圆结构划分单元格，相邻单元格之间会产生重叠区域。通过无线信道的传输模型可知，数据包直线多跳传输的能量消耗要小于直线单跳传输的能量消耗［12］。基于这一点，可以在重叠区域中选择合适的节点作为相邻簇头间的中转节点，实现簇头间的多跳路由，进一步减少簇头节点的能量消耗。

同时考虑到重叠区域中节点的剩余能量E0和吞吐率λ，可以计算出重叠区域中节点的权值ω

式中：a，b——节点剩余能量和吞吐率的权值且a＋b＝1。在重叠区域中选择权值最大的节点作为中转节点。

4 仿真结果

本文中采用MATLAB仿真对改进的GAF算法进行性能分析，在节点的平均能量消耗和网络生存期等方面对3种结构模型下的GAF算法进行了比较。仿真过程中网络中的节点随机分布，每个节点的初始能量为0.5J，当节点的能量为零时，则定义节点为死亡节点。其它参数设置见表1。由于仿真时，传感器节点是随机部署的，故实验数据都是通过100次仿真后的平均值。

表1 仿真的参数设置

100次仿真实验过程中的其中一次随机节点分布图如图3所示。图中五角星形为监测区域中基站所在的位置，坐标 （100，100）。黑色圆点表示随机分布在监测区域中的400个节点。

图3 节点分布

在图3的基础上根据式 （4）所得出的虚拟单元格的划分条件进行虚拟单元格的划分，划分出的结果如图4所示。按照式 （4）进行计算得出每个虚拟单元格的边长为50m，从而整个监测区域可被划分为16个大小相同的单元格，即16个簇。

图4 虚拟单元格划分

根据本文所提出的相交圆结构模型进行单元格划分的划分图如图5所示。图5中绿色边界区域为监测区域的范围，从（0，0）到 （200，200）。每个圆形即为划分出一个簇，由图中可以看出，每个圆形之间都会有相应的重叠区域，且每个簇的面积都要明显大于图4中划分出的簇的面积。

图5 相交圆结构模型划分

图6所示为3种算法的网络生存期比较。由图中可以看出，在同一时刻，基于相交圆结构的改进GAF算法的存活节点比例要高于图1中所示的两种正方形结构的GAF算法。而两种正方形结构模型中，如图1 （b）的正方形结构模型的网络生存期要比图1 （a）的正方形结构模型的生存期长。这也就进一步说明了，当簇的面积增大时，可以延长网络的生存期。

图6 网络生存期比较

3种算法的节点平均能量消耗的比较如图7所示。在相同的实验环境中，改进算法的平均能量消耗最低。因此，基于相交圆结构的改进GAF 算法要优于正方形结构的GAF算法，这是由于相交圆结构增加了每个簇的面积，且利用中转节点使簇头间形成了多跳路由，从而减少了节点能耗，延长了网络生存期。

5 结束语

图7 节点平均能量消耗比较

根据传统GAF算法的基本思想，采用相交圆结构模型对监测区域进行划分，并在重叠区域中根据权值选择出中转节点。在簇头选择阶段，根据定义的簇头选择函数来进行簇头选择。改进算法有效的减少了节点能量消耗，延长了网络生存期。在改进GAF算法的基础上，如何使得网络生存期达到最大化［13］；在实际应用中如何保证算法的收敛速度，如何减少通信干扰还需要进行进一步的研究。

［1］LI Shancang，ZHANG Kewang.Wireless sensor network principle and application［M］.Beijing：China Machine Press，2008：120－123（in Chinese）.［李珊仓，张克旺.无线传感器网络原理与应用［M］.北京：机械工业出版社，2008：120－123.］

［2］LUO Xiaoyuan，YAN Yanlin，LI Shaobao.Topology control based on optimally rigid graph in wireless sensor network ［J］.Computer Networks，2013，57 （4）：1037－1047.

［3］LIU Zhixin，DAI Lili，MA Kai.Balance energy－efficient and real－time with reliable communication protocol for wireless sensor network ［J］.China Universities of Posts and Telecommunications，2013，20 （1）：37－46.

［4］JIANG Changjiang，SHI Weiren，TANG Xianlun，et al.Energybalanced unequal clustering routing protocol for wireless sensor networks［J］.Journal of Software，2012，23 （5）：1222－1232 （in Chinese）.［蒋畅江，石为人，唐贤伦，等.能量均衡的无线传感器网络非均匀分簇路由协议 ［J］.软件学报，2012，23 （5）：1222－1232.］

［5］JING Bo，ZHANG Jie，SUN Yong.Intelligent network sensors and wireless sensor networks［M］.Beijing：National Defence Industry Press，2011：103－104 （in Chinese）.［景博，张劼，孙勇.智能网络传感器与无线传感器网络 ［M］.北京：国防工业出版社，2011：103－104.］

［6］Halit Uster，Lin Hui.Integrated topology control and routing in wireless sensor networks for prolonged network lifetime［J］.Ad Hoc Networks，2011，9 （5）：835－851.

［7］WAN Chuanfei，DU Shangfeng.A hierarchical topology generation algorithm for wireless sensor networks［J］.Chinese Journal of Sensors and Actuators，2010，23 （3）：441－446（in Chinese）.［万传飞，杜尚丰.一种应用于无线传感器网络的层次型拓扑结构生成算法［J］.传感技术学报，2010，23 （3）：441－446.］

［8］YANG Zejun，WANG Yinglong，ZHAO Fumeng.An improved cluster algorithm based on intersecting circle structure［C］／／International Conference on Computer Supported Cooperative Work in Design.Wuhan：IEEE，2012：622－625.

［9］QI Xiaogang，QIU Chenxi.An improvement of GAF for lifetime elongation in wireless sensor networks［J］.Journal of Convergence Information Technology，2010，5 （7）：112－119.

［10］HU Changjun，YAO Shanhua.Clustering algorithm based on relay region for WSN ［J］.Computer Engineering and Applications，2012，48 （18）：104－109 （in Chinese）. ［胡长俊，姚善化.无线传感器网络基于中转区域的分簇算法 ［J］.计算机工程与应用，2012，48 （18）：104－109.］

［11］YU Chengbo，LI Hongbing，TAO Hongyan.Wireless sensor network practical tutorial［M］.Beijing：Tsinghua University Press，2012：80－81 （in Chinese）. ［余成波，李洪兵，陶红艳.无线传感器网络实用教程 ［M］.北京：清华大学出版社，2012：80－81.］

［12］LIU Shu，LIU Linfeng，TAO Jun.Improved GAF algorithm with hexagon－based virtual infrastructure ［J］.Computer Technology and Development，2009，19 （1）：39－42 （in Chinese）. ［刘曙，刘林峰，陶军.一种基于蜂窝结构的改进GAF算法 ［J］.计算机技术与发展，2009，19 （1）：39－42.］

［13］Ouadoudi Zytoune，Youssef Fakhri，Driss Aboutajdine.Lifetime maximization algorithm in wireless sensor network ［J］.International Journal of Ad Hoc and Ubiquitous Computing，2010，6 （3）：140－149.