基于兴趣梯度和能量梯度改进的GPSR路由算法

刘壮，冯欣，张昕，刘妍，张婧，张剑飞

（长春理工大学　计算机科学与技术学院，长春　130022）

基于兴趣梯度和能量梯度改进的GPSR路由算法

刘壮，冯欣，张昕，刘妍，张婧，张剑飞

（长春理工大学计算机科学与技术学院，长春130022）

针对贪婪周边无状态路由（GPSR）算法中能耗不均衡和高能耗问题，提出了一种基于兴趣梯度和能量梯度的改进的GPSR路由算法。首先，在查询消息沿路由路径的传输过程中，根据汇聚节点与事件区域节点发生数据内容的匹配程度，确立兴趣阈值和能量阈值；然后，当路由路径中的一些节点接近阈值，网络将运用右手法则和递归贪婪算法提前找出一条新的路由路径到目标区域，从而使节点负载相对均衡。仿真实验结果表明，改进的算法减少网络能耗和延长网络的生存周期。

GPSR；兴趣梯度，能量梯度；网络生存周期

无线传感器网络是由大量的廉价传感器节点组成，节点之间通过自组织的无线通信方式进行感知、采集和处理监测区域中被感知对象的信息，以多跳的方式将数据发送给终端用户［1］。无线传感器网络集成许多科学技术，如传感器技术、信息融合技术和信息处理技术，并且广泛应用在环境监测、军事研究、工业生产、医疗卫生、抢险救灾等领域［2］。无线传感器网络具有网络灵活性、可扩展性、易部署、流动性和廉价性等特点［3］。

在基于地理位置的路由协议中，每个节点都知道自身和它邻居节点的地理位置信息，当消息传输时，节点的位置信息通过数据包的方式利用贪婪算法传送给下一跳邻居节点［4］。如果中继节点无法找出比自身节点更近的目标节点的节点，将产生路由空洞。针对这个问题，Brad Karp等人［5］提出GPSR（贪婪周边无状态路由协议），该协议主要是通过邻居节点形成的平面网络利用周边无状态模型将数据包传输给目标节点。

GPSR协议避免了在节点中建立、维护和存储路由表，并且数据传输延迟小，然而GPSR也存在一些缺点。Nithyanandan L等人［6］提出一种基于能量选择的最佳路径算法，旨在改善GPSR中网络数据的不一致性，并且可以确保在不匀称的无线传感器网络中能量均衡的可行性。Shanmuga Raja B等人［7］也采纳能量最佳路径算法，用来确保节点之间信息的有效性和节能性，从而延长网络生存周期。刘宇等人［8］提出一种基于邻居节点的动态路由负载平衡的改进算法，可以解决由路由空洞造成的网络周期的减少的问题。重点研究节点能耗的不均衡分布问题并提出一种基于能量梯度的改进GPSR路由算法，通过提前设置的兴趣阈值和能量阀值调节传感器的工作状态，从而减少节点无效，延长网络的周期和提高数据传输效率。

1　相关工作

GPSR是一种经典的地理位置路由协议算法，广泛应用在Ad-hoc和无线传感器网络中，该算法包含两种形式的数据传输方法：贪婪转发和边界转发。

1.1贪婪转发

在GPSR中，源节点打包目标节点的位置信息，并将信息传输给已知位置的邻居节点，并且最佳的下一跳应该是最接近自身的邻居节点，根据这一原理，数据以多跳的方式传输到汇聚节点［9］。贪婪转发的具体过程如图1所示。小虚线圆圈代表节点x的通信半径，节点D代表汇聚节点，节点x将节点y作为下一跳传输节点，此时节点y是通过贪婪方法寻找的最接近节点D的节点，循环直到数据传送给节点D。

图1　贪婪转发（y是x最近D的邻居节点）

1.2边界转发

在贪婪转发中，如果节点不能找到离目标结点较近的下一个节点，为避免路由空洞产生，GPSR将运用周边无状态路由解决这一问题［10］。在此过程中，为描述网络拓扑结构，将构造平面图并确保图的任何两边不交叉。如图2所示，x比其邻居节点w和y更接近目标节点D，设置D为圆中心，D与x的距离作为圆的半径，可以看到，有两条路由路径到达节点D：（x→y→z→D）和（x→w→v→D），然而，根据贪婪算法，节点x不能传输数据到节点y 和w，从而形成路由空洞。

图2　贪婪转发失败

如果中继节点发现路由空洞，它可以利用右手法则找到一个新的路由路径。右手法则如图3所示，从节点y到节点x，下一条边连接顶点x和顶点y，方向从x到y，以逆时针旋转的方式选择另一条边，然后遍历封闭的多边形区域。在图2中，当节点x发现路由空洞时，将通过右手法则形成路由路径x→w→v→D→z→y→x，边界转发完成。

图3　右手法则

在GPSR算法中，传感器节点选择路由路径仅需知道自身、邻居节点和目标节点的地理位置，而不需要维持整个网络的拓扑图，从而减少了连接能耗。同时，采用贪婪算法可以减少路由路径跳数和缩短数据传输中路由路径步数，进而可以减少整个无线传感器网络中的能耗和提高路由路径质量的效率，并且延长网络的生存周期。

2　改进算法

2.1兴趣梯度和能耗梯度

在无线传感器网络应用中，传感器节点随机部署，节点能量有限，因此，减少能耗和延长网络生存周期成为关键问题。为解决这一问题，提出一种基于兴趣梯度和能量梯度改进的GPSR路由算法。

在改进算法中，当查询路径建立后，在数据传输的过程中，兴趣阈值Ithreshold根据汇聚节点与事件区域节点发生数据内容的匹配程度确定，匹配程度越高，说明未来在此路径上发生数据传递的概率越大，那么阈值设的越低，否则越高。能量阈值Ethreshold根据路由路径能量损耗数据包和传感器节点剩余能量确定，为固定值。每次数据传输时，路由路径上的每个传感器节点都将其剩余能量与 Ethreshold相比较，同时判断传递数据内容是否与Ithreshold相等，随着路由路径上能量的消耗，若某个节点的剩余能量Erest不大于Ethreshold，并且 Irest不小于 Ithreshold，算法将利用右手法则避开这个节点并重新修改当前路径，然后避开的节点仍在监测区域，它仅收集外界数据而不能传输其它传感器节点的数据，因此，传感器节点的负载周期将会延长并且网络中的能耗可以均匀分担。

图4改进GPSR算法

图4所示，在没有产生路由空洞时，贪婪路由路径是S→x→y→z→h→j→i→D，当节点y满足兴趣阈值与能量阈值的限定时，分别以D和y为中心画两个圆，圆的半径分别是节点D和节点y的通信半径之间的距离，利用右手法则和递归贪婪算法直到路由路径到达目标节点D，此时在重叠区域找到最佳的下一跳节点a。改进算法的新的路由路径为S→x→a→z→h→j→i→D，此外，若出现路由空洞，改进算法利用右手法则找出新的路由路径。

2.2能耗模型

模型采用Heinzalman提出的无线通信能耗模型［11］。无线传感器网络中n位数据传输能耗记为ETx，公式（1）所示。

式中，Eamp为信号放大器的放大系数，εfs为空闲空间能耗，Eelec为发射和接受电子线圈能耗，d为两个传感器节点请求数据传输的距离。

式中，R为通信半径，ERx为n位数据接受能耗。

3　仿真实验

3.1仿真实验环境及参数

仿真实验在Matlab R2011b环境下中运行，通过实验来比较改进算法和GPSR算法网络能耗和有效传感器节点数。

实验中监测区域为300m*300m，随机部署90个传感器节点，通信半径为75m，信标节点所占比例为30%，初始能量为0.5J，节点（300，300）是汇聚节点，左下方是事件区域。

3.2仿真实验结果分析

图5所示，路由路径首次建立，星状节点代表90个传感器节点，圆状节点代表汇聚节点。左下角黑色虚线包围的区域为事件区域，黑色实线代表路由路径。汇聚节点发送查询信息到事件区域，根据反方向的查询信息路径，建立路由路径。

图5　GPSR路由路径

在无线传感器网络中，网络中剩余能量是评价其性能的一个关键因素，因此，实验执行的目的就是比较两种算法中每轮中剩余能量。图6所示，横坐标代表轮数，纵坐标代表网络中所有节点剩余能量。虚线代表事件区域利用GPSR算法由于能量耗尽而失效之前每轮中网络中剩余能量，实线代表利用改进算法的剩余能量。从图6可以总结出，改进算法能降低网络能耗并且延长网络生存周期。

图6　剩余能量对照图

当事件区域内的节点由于能量耗尽而失效时，网络中有效传感器节点是评价路由算法的另一个重要因素。图7所示，横坐标代表实验轮数，纵坐标代表存活节点数量。虚线代表事件区域内所有传感器节点使用GPSR算法每轮的存活节点数，实线代表改使用进算法每轮存活节点数。从图7中可以得出，1100轮之前，GPSR算法和改进算法在事件区域内的传感器节点存活数量相当，1100轮之后，两算法相比，改进算法的节点存活数量明显优于原算法。所以使用改进算法中有效节点数明显多于使用GPSR算法。

图7　有效节点数量对比图

4　结论

为解决高能耗和GPSR算法中能量不均衡问题，提出了一种基于兴趣梯度和能量梯度改进的GPSR算法。GPSR是一种地理路由算法，改进后的路由算法设计查询信息传输和事件传输的传输机制，并利用右手法则和边界转发策略预测和避免了路由空洞。在新的算法中，通过查询发送消息和提前设置阈值建立兴趣梯度和能量梯度路径，然后，如果当前传感器节点能量接近阈值，根据右手法则及迭代贪婪算法重新建立路由路径。这种新的算法考虑到路由路径的能耗不均衡问题，并且为了避免一些节点由于能量过度消耗而造成失效，设计了动态更新路由路径机制。因此，能耗分布在整个网络中，可以降低了网络能耗。仿真实验结果表明，改进的算法能够延迟传感器节点的失效，降低网络能耗和延长网络生存周期。

［1］孙利民，李建中，陈渝.无线传感器网络［M］.北京：清华大学出版社，2005：3-4.

［2］胡智慧，刘智.基于LTE无线传感器在智能电网的应用研究［J］.长春理工大学学报：自然科学版，2014，37（2）：80-83.

［3］姚先连，胡贞，吕晓玲.无线传感器网络中卡尔曼滤波在移动目标跟踪中的研究［J］.长春理工大学学报：自然科学版，2011，34（3）：88-92.

［4］韩连胜，罗卫兵，李南翔.基于地理路由协议GPSR的研究与改进［J］.计算机工程与应用，2007，43（36）：160-162.

［5］Brad Karp，Kung H T.Greedy perimeter stateless routing for wireless networks［C］.The Sixth Annual International Conference on Mobile Computing and Networking，Boston，2000（8）：243-254.

［6］Nithyanandan L，Sivarajesh G，Dananjayan P.ModifiedGPSRprotocolforwirelesssensornetworks ［J］.International Journal of Computer and Electrical Engineering，2010，4（2）：324-328.

［7］Shanmuga Raja B，Prabakaran N，Sarma Dhulipala V R.Modified GPSR based optimal routing algorithm for reliable communication in WSNs［C］.International Conference on Devices&Communications，2011：1-5.

［8］刘宇，赵志军，沈强，等.能量感知的GPSR动态路由负载均衡［J］.计算机工程与应用，2011，47（6）：23-25.

［9］吴三斌，王小明，杨涛，等.改进的GPSR模型及其仿真分析［J］.计算机工程与应用，2011，47（8）：100-104.

［10］李道全，刘海燕，曹齐光，等.基于地理位置的路由算法—GPSR-AD［J］.计算机应用，2009，29（12）：3215-3232.

［11］Heinzelman W B，Candraksan A P，Balakrishnan H.An application specific protocol architecture for wireless microsensor network［J］.IEEE Transactions on Wireless Communications，2002（4）：660-670.

An Improved GPSR Routing Algorithm Based on Interest Gradient and Energy Gradient

LIU Zhuang，FENG Xin，ZHANG Xin，LIU Yan，ZHANG Jing，ZHANG Jianfei

（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

To solve the unbalanced and high energy consumption of greedy perimeter stateless routing（GPSR）algorithm，an improved routing algorithm based on interest gradient and energy gradient is proposed.First，during the transmission of query message along a routing path，an interest threshold and an energy threshold are established according to the matching degree of data content between sink node and the node in event area，and then if some nodes are approaching any thresholds，network uses right-hand rule and recursion greedy algorithm to find out a new routing path to target area，so nodes can get relatively balanced load among neighbor nodes.Simulation experiments show that the improved routing algorithm reduces the energy consumption of network and extends the lifecycle of network.

GPSR；interest gradient；energy gradient；lifecycle of network

TP393

A

1672-9870（2016）03-0132-04

2016-01-13

国家自然基金项目（NSCF61275080）

刘壮（1980-），男，讲师，E-mail：lz1227@live.cn

冯欣（1973-），男，副教授，E-mail：fengxin@cust.edu.cn