无线传感器网络改进的GAF算法研究

卢欣　朱正礼　朱红红

摘要：传感器节点能量有限一直以来都是无线传感器网络的关键所在。针对该问题对传统的GAF（geographic adaptive fidelity，GAF）算法进行了改进。改进的GAF算法引入了支持向量回归机（Support Vector Regression，SVR）来优化虚拟单元格的划分，同时将正方形网格改为圆形区域；另外，通过改变圆形区域的半径来加强相邻区域的连通性。结果显示，与传统的GAF算法相比，改进后的算法具有更大的优势，降低了节点能耗。

关键词： 支持向量回归机；GAF算法；虚拟单元格；节点能耗

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）05-0194-04

Abstract： The limited energy of sensor nodes had been the key of Wireless Sensor Networks.To solve the problem，traditional GAF algorithm was improved.Improved GAF algorithm introduced SVR to optimize virtual cells division and paints circular areas to replace the square grids.In addition，connectivity between adjacent areas were strengthened by changing the radius of the circular areas.Results showed that compared with the traditional GAF algorithm， the improved algorithm had a greater advantage， and reduced the energy consumption of nodes.

Key words： support vector regression；GAF algorithm；virtual cell；energy consumption of nodes

1 引言

无线传感器网络（Wireless Sensor Network， WSN）是由众多传感器节点以自组织和多跳方式组成的传感网络[1]。随着技术的进步，WSN广泛应用于军事、环境监测、城市交通和智能家居等领域。由于传感器节点的体积小，携带的能量是有限的，通常部署在复杂的无人值守的环境中，因此WSN面临的重要挑战是如何提高能量的利用率来延长整个网络的生存时间。

GAF算法[2]是一种拓扑控制算法，是由Xu等人针对无线传感器网络节点部署复杂且密集的这一特性提出来的[3]。该算法是基于单元格分簇的拓扑算法，不足之处在于它的簇首选择机制和节点能耗不均。在本文中，采用了支持向量回归机（Support Vector Regression，SVR）虚拟单元格的划分进行优化，并借助MATLAB工具对改进之后的算法进行了性能分析与实验仿真。

2 支持向量回归机

支持向量机（Support Vector Machine，SVM）主要用于研究分类和回归这两大问题，1995年Vapnik提出的一种新的通用学习方法[4]。在许多领域都得到了长足的发展， 例如非线性系统控制、人脸检测技术、计算机入侵检测、基因分类、函数回归估计、数据挖掘等等。本文主要采用SVM中的回归估计方法（即SVR），无线传感器网络中节点的分布满足某一函数，针对这一函数应用SVR寻找其属于支持向量（Support Vector，SV）的点，以该点作为圆心进行区域划分。

SVM方法首先是从解决分类问题发展起来的，把该方法推广到回归领域时，则提出了SVR。SVR仍然保持着分类问题中的稀疏性，即可以用少量SV来表示决策函数[5]。

3 GAF算法

3.1 传统的GAF算法

GAF算法[6]基于节点的位置信息，监测区域划分成方形的虚拟单元格，根据算法本身的簇首选择机制进行分簇。该算法主要有两个阶段的执行过程。

第一阶段，为保证相邻单元格中任意两个节点可以直接通信，根据传感器节点的位置信息和通信半径来划分虚拟单元格。在已知位置和通信半径的情况下，可以计算出该节点所在的单元格。

所有节点的初始状态的都是发现状态，每一个节点发送自己的位置信息来获得本单元格内其他节点的信息。每个节点设置一个定时器，一旦定时器超过T1，节点进入活动状态，同时发送消息声明成为簇头节点；若超时前收到本单元格内其他节点成为簇头的消息，则进入睡眠状态，说明该节点簇头竞争失败。当簇头节点处于活动状态，定时器时间设置为T2（即活动状态的时间）。一旦定时器超过T2，簇头节点就重新进入发现状态；在超过T2之前，簇头节点周期性地发送广播包，从而抑制其他发现状态的节点进入活跃状态。当节点进入睡眠状态，设置定时器时间为T3，在定时器超过T3之后进入发现状态。

3.2 改进的GAF算法

在GAF算法中，考虑WSN连通度的问题，对监测区域进行单元格划分，算法要使得相邻单元格内任意两个节点可以直接通信。因此单元格边长需要满足[r≤R5]。文献[7]提出另一种相邻区域的关系如图6，为保证每个单元格节点与周围相邻区域能直接通信。

3.3 基于SVR的GAF算法改进

GAF算法是WSN中较早采用让部分节点进入睡眠状态以节省能耗的分簇算法。它的优点在于采用了节点状态转换机制和按虚拟单元格划分簇。不过GAF算法也有它的不足之处，忽略了提供损失的节点，而且在实际应用中节点容易移动，可能从一个单元格移动到另一个单元格，这些移动的节点很可能是某个单元格内的簇头节点，这会导致有些单元格内没有簇首节点转发数据消息，从而导致网络中大量的丢包和重复发包，增加网络中不必要的能量消耗。为此，引入SVM技术中的SVR，对GAF算法进行预处理，当节点在ε-带范围之外则舍弃，减少能量消耗。SVR产生的支持向量作为虚拟单元格的圆心画圆形区域，当划分的圆形区域相交是就产生了重叠区域。重叠区域内的节点将属于两个或两个以上的单元格，这样势必会引起节点分区的矛盾和节点的能量消耗。为了避免这样的能量消耗和矛盾，将这些节点作为两个单元格中的中转节点。

算法流程如下：

（1）初始化：确定传感器节点个数n，随机产生每个节点的位置和初始能量；

（2）通过SVR，选取出属于支持向量的传感器节点；

（3）以支持向量节点为圆心，半径为r画圆形区域，每一个区域为一个整体；

（4）每个区域利用图5中节点状态转换选取簇首，非簇首节点加入相应的簇；

（5）节点成为簇首后，给单元格内其他节点发布声明消息，并进入活动状态；

（6）若T2超时，则返回（4）继续，直至节点全部死亡；

（7）网络稳定运行。

4 实验与分析

4.1 实验环境

在[x∈[-10，10]]，且[y]满足式（1-4）的监测区域中，随机分布100个传感器节点和一个基站节点（0，0）（基站位置不变）。高能量节点超出一般节点能量的百分比a为1，则监测区域内节点初始能量为[E0]的[（1+rand?a）]倍，其中[E0]为0.5J。传感器节点采集的数据的长度为4000bit，周期为5000轮。SVR模型中优先考虑线性回归函数，其中核参数k为0.05，惩罚参数C为100.0，精度参数ε为1。实验采用MATLAB7.0进行，将基于SVR的GAF算法（r不变）、基于SVR的GAF算法（r改变）与原始的GAF算法进行对比，主要对比死亡节点数和能量消耗这两方面。

4.2 实验结果

从图8和图9可以更明确地看出算法在相应轮数的死亡节点数。GAF算法在第2486轮附近出现第一个死亡节点，在第4842轮附近节点全部死亡；基于SVR的GAF改进（r不变）算法第一个死亡节点出现在第2525附近，节点全部死亡在第4900轮附近；基于SVR的GAF改进算法第一个死亡节点出现在第2490轮附近，最后一个死亡节点出现在第4955轮附近。基于SVR的GAF改进比传统的GAF算法以及基于SVR的GAF改进（r不变）算法的网络生命周期长，更能避免节点过早死亡。

5 结束语

本文在无线传感器网络中的GAF算法上引入SVR技术，对算法进行预处理，利用ε-带去除无效节点。以支持向量为圆心画圆形区域来划分单元格，通过改变半径来保持连通性。通过反复的实验验证，可以看出该算法能有效减少节点能耗，改善能量有限问题。这只是对GAF算法一方面的改进，该算法在实际应用中还有更多问题需要解决，比如节点分布范围很广的时候，如何减少外界因素对通信的干扰等，还有待进一步研究。

参考文献：

[1]陈林星. 无线传感器网络技术与应用[M]. 北京：电子工业出版社，2009：4-5.

[2]Xu Y，Heidemann J，Estrin D. Geography-informed energy conservation for ad hoc routing[C]. 7th Annual Int.l Conf on Mobile Computing and Networking. Rome，Italy： ACM Press， 2001：70-84.

[3]景博，张劼，孙勇. 智能网络传感器与无线传感器网络[M]. 北京：国防工业出版社，2011：109-110.

[4]邓乃扬，田英杰.数据挖掘中的新方法——支持向量机[M].北京：科学出版社，2004.

[5]朱红红，朱正礼，卢欣，侯迎坤.基于SVM的LEACH分簇算法优化[J]. 常州大学学报（自然科学版），2014：18-23.

[6]孙利民，李建中，等.无线传感器网络[M]. 北京：清华大学出版社，2005：97-98.

[7]梁青，李卓冉，韩昊澎，熊伟. 基于最优簇首数划分单元格的改进GAF算法[J]. 计算机应用研究，2014，30（12）：3622-3624.