一种基于分簇的无线传感器网络GPSR 协议*

沈丹丹，王立华，王 宇，王振洲

(1.上海海洋大学 信息学院，上海201306;2.中国水产科学研究院 渔业工程研究所，北京100141)

0 引 言

无线传感器网络(wireless sensor networks，WSNs)［1］是由大量微小的传感器节点组成的一种多跳无线网络，通过无线方式通信，网络设置灵活，设备位置可以随时更改，还可以跟互联网进行有线或无线方式的连接。WSNs 广泛应用于军事、智能交通、环境监控、医疗卫生等多个领域。由于WSNs 节点本身电池能量有限，在恶劣环境下，电池不易更换，当电池能量耗尽时，节点就会死亡，当网络中死亡节点过多就会导致网络瘫痪，因此，控制节点能量损耗成为延长网络的生存周期主要难题［2］。

GPSR［3］(greedy perimeter stateless routing)协议建立在传统贪婪转发算法之上，其优点是只依赖直接邻节点进行路由选择，避免在节点中建立、维护、存储路由表，几乎处于无状态;数据传输时延小;健壮性好。在一定程度上GPSR协议可节省节点的能量。而缺点是当网络中Sink 点和源节点在两个区域时，由于通信量不平衡导致部分节点失效，严重影响WSNs 生存时间。

为了延长网络生存周期，提出了一种基于分簇的WSNs GPSR 协议。通过仿真结果表明:该协议不仅能延长网络生存周期，还能提高数据传输成功率。

1 GPSR 协议简介

GPSR 是一种基于传统贪婪转发方案的路由协议。为了避免传统贪婪转发方案中通信空洞造成的路由寻径失败和由此产生的重复路由请求带来的额外开销，GPSR 利用传感节点对位置信息的可知性，在路由过程遭遇通信空洞而失效时，根据网络原始拓扑生成一个平面子图并沿子图中空洞的周界进行分组转发［4］。

2 WSNs 模型与算法改进

2.1 基于位置的WSNs 模型

针对本文提出的改进算法，提出以下假设条件:

1)每个节点初始能量相同ei(0);

2)每个节点担任簇头期间耗费的能量均等;

3)所有节点随机分布，并且传感器射频发射功率恒定。

本文节点的地理信息位置由GPS 获得，设节点Li={Li=(xi，yi)}，设Li表示节点i 的生存时间，ei(0)为传感器初始能量，T 表示整个网络从起始状态的能量到第一个节点是失效的时间，则有T=min(T1，T2，….TN)。

根据能量模型［5］

式中 Eelec为发送电路和接收电路每发送或接收单位比特所消耗的能量;εfs为自由空间传播模型下功率放大所需要的耗能系数;εmp为多路径衰减传播模型下功率放大所需要的耗能系数;d0为门限距离。

由式(1)可看出，传感器节点数据传输时，尽可能选择距离较短的路由，减少节点耗能，延长整个WSNs 的生存周期。

2.2 改进GPSR 协议算法

2.2.1 簇的建立阶段

WSNs 会被分成多个大小不同的簇，每个簇中包括一个簇头节点和多个普通节点，根据文献［6］可知，最优簇头数为

式中 εfs为自由空间传播模型下功率放大所需耗能系数;εmp为多路径衰减传播模型下功率放大所需要的耗能系数;dtoBs为簇头到基站的距离。

簇头节点不仅要负责接收、融合、传输簇内节点的数据而且还要负责转发其他簇头节点传输的数据，所以，选择剩余能量较少的传感器节点作为簇头节点，那么，该传感器节点会因为耗能过快而失效，这样，这个WSNs 的数据传输将会遭到破坏而失效［7～9］。因此，簇头节点的选择应该考虑传感器节点的剩余能量。

2.2.2 簇头的选举优化

节点随机产生一个［0，1］间的随机数，如果这个数小于阈值T(n)，则广播自己是簇头的消息。在每轮循环中，如果节点已经被当选为簇头，则设置T(n)为0，这样，该节点不会被再次被选为簇头。未被当选为簇头的节点被选中的概率T(n)

T(n)=0，其他情况下

式中 p 为簇头占所有节点的百分比，即节点当选簇头的概率;R 为目前循环进行的轮数;G 为最近1/p 轮中还未当选过簇头的节点集合。

WSNs 中所有节点等概率地担任簇首，保持网络内节点能量的均衡消耗，延长了整个网络生命周期。考虑到能量问题，将T(n)优化为

式中 En_current为节点的当前能量;En为节点的初始能量。

2.2.3 改进贪婪算法建立路由

在传统GPSR 协议中，源节点S 向目的节点D 发送数据包，数据包中标示了源节点和目的节点的位置信息。当目的节点D 不在源节点S 邻节点列表中时，则需要转发节点进行数据转发。在GPSR 协议中使用贪婪转发来获取下一跳［10］。

源节点S 向目的节点D 发送数据包，具体改进步骤如下:

1)源节点S 首先选择其通信半径内与簇头节点距离最近的一跳邻节点A，若该节点是簇头节点，则路由过程结束，簇头节点直接将数据包发送至下一个簇的簇头。

2)若A 不是簇头节点，那么，源节点选择覆盖半径内与簇头节点距离最近的节点A'传输数据。

3)A'同样选择其通信覆盖半径范围内与簇头节点距离最近的节点传输数据。

4)重复步骤(2)，(3)，直到数据传送至簇头节点。

5)重复步骤(2)，(3)，(4)，直到数据传送至目的节点D。

改进的路由协议执行的流程图如图1。

图1 改进路由协议算法流程图Fig 1 Algorithm flow chart of improved routing protocol

3 仿真与结果分析

3.1 仿真环境

在100 m×100 m 的正方形区域内，随机分布100 个传感器节点，这些节点初始能量相同且为0.5 J。本次仿真采用Matlab 2010b 进行模拟仿真，仿真环境参数设置如表1所示。

其中，Eelec为发送电路和接收电路每发送或接收单位比特所消耗的能量;εfs为自由空间传播模型下功率放大所需耗能系数;εmp为多路径衰减传播模型下功率放大所需要的耗能系数。

表1 仿真参数设置Tab 1 Simulation parameters settings

3.2 仿真结果分析

1)网络生存节点数

如图2 所示，由于GPSR 协议存在局部最小化问题，当局部最小化问题突出时，节点能量损耗严重，导致节点失效，网络生存下的节点数越来越少。而本文算法采用分簇算法避免了局部最小化问题，因此，节约了节点能量，延长了节点生存时间，使得生存的节点数增加。

图2 网络生存节点数对比图Fig 2 Comparison diagram of number of network alive nodes

2)网络节点能量消耗

如图3 所示，GPSR 协议存在局部最小化问题，当局部最小化问题不突出时，节点之间的数据传递不会有太多影响，不会出现大量的能量损失。但当出现局部最小化问题时，能量损耗速度快，节点消失较多。而本文算法不存在局部最小化问题，因此，能较好节省节点能量，延长节点生存时间，即延长网络的周期。

3)数据包转发成功数

如图4 所示，GPSR 协议数据传输成功率低，本文算法不存在局部最小化问题，在簇形成以后，就不必再消耗能量分簇。因此，网络节点能量稳定，均衡消耗，数据传输率高。

图3 网络节点能量消耗对比图Fig 3 Energy consumption comparison of network nodes

图4 数据包转发成功数对比图Fig 4 Comparison diagram of number of packets successful transmission

4 结束语

为了延长网络生存周期，本文提出一种基于分簇的WSNs GPSR 协议。该算法基于分簇思想提出基于每个邻节点与簇头节点距离的比较来建立路由，因此，不存在局部最小化问题，大大减少了算法的复杂度。由于WSNs 节点能源有限，考虑到节省能量来延长网络生存周期，但却是以增加数据传输时延为代价的。仿真对比结果表明:本文改进协议能有效均衡能耗，延长网络生存周期。

［1］ 任丰原，黄海宁，林 闯.无线传感器网络［J］.软件学报，2003，14(7):1282－1291.

［2］ Kail A，Kanatas A G，Efthymoglou G P.A cooperative beam forming solution for eliminating multi－hop communications in wireless sensor［J］.IEEE Journal on Selected Areas in Communications，2010，28(7):1055－1062.

［3］ 唐国明，谢 羿，唐九阳，等.一种基于左、右手法则的GPSR分区边界转发路由协议［J］.计算机应用研究，2011，28(3):1099－1101.

［4］ 张 威，施伟斌.无线传感器网络GPSR 路由协议研究［J］.电子测量技术，2010(9):118－121.

［5］ 李成法，陈贵海，叶 懋，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007(1):27－36.

［6］ 赵菊敏，张子辰，李灯熬，等.一种无线传感器网络链式传输分簇路由协议［J］.传感器与微系统，2014，33(3):135－138，142.

［7］ 钟 智，樊晓平，罗大庸，等.一种基于网格的无线传感器网络分簇路由协议［J］.传感器与微系统，2011，30(12):18－20，24.

［8］ 侯贵升，吴晓蓓，黄 成，等.无线传感器网络中一种基于标号的贪婪转发算法［J］.传感器与微系统，2012，31(9):123－125，128.

［9］ 杨海迎.基于非均匀分簇的无线传感器网络路由协议设计与研究［J］.现代计算机:专业版，2014(7):3－6.

［10］徐跃州，张 欣，张 涛，等.基于贪婪－改进果蝇算法的无线传感器网络路由协议［J］.传感器与微系统，2015，34(5):134－136，139.