基于能量梯度和APIT网格的GPSR路由算法

摘要

本发明涉及一种基于能量梯度和APIT网格的GPSR路由算法，其特征在于：汇聚节点在平面直角坐标系X轴和Y轴上的位置为（1000,1000）；无线传感器节点组包括300个无线传感器节点（后简称“节点”），分别用Node(

说明书

技术领域

    本发明涉及一种基于能量梯度和APIT网格的GPSR路由算法，属于无线传感器网络技术领域。

背景技术

GPSR协议作为一种基于地理位置的健壮的路由协议，GPSR协议省去了建立、维护和存储路由表的过程，并且数据传输时延小，在无线ad hoc和传感器网络中担任了重要的角色。在拓扑结构自由变化的ad hoc网络中，GPSR路由协议仅通过多个单跳的拓扑信息建立路由，利用平面周边转发法，改进了洪泛路由盲目性和开销大的缺陷。在一个随机配置的无线传感器网络（简称WSN）中，GPSR可通过边界转发策略有效地解决路由空洞问题。

然而在WSN的实际应用中，节点的生存能力往往决定了整个网络的生命周期，节点能耗越小，网络生命周期越长。在静态的网络拓扑结构中，一旦第一个数据包从汇聚节点通过一个长的路径到达目的节点，就造成热点路由问题，导致网络中能量消耗不均衡，缩短网络寿命。

GPSR路由协议使用贪婪算法建立路由，当某个节点需要向目的节点转发数据的时候，首先在自己的所有邻居节点中选择一个距目的节点欧氏距离最近的节点作为下一跳，然后将数据发送给该节点。该过程一直重复，直到数据到达目的节点。转发的过程中，如果出现路由空洞问题，则选择用右手法则通过边界进行数据转发，从而解决空洞问题。但是在路由建立过程中，如果建立的路径太长造成之后所有数据包一直沿这一条路径进行传输，形成热点路由。本文对WSN中热点路由问题进行研究，分析WSN中各节点路径能耗全网节点能量消耗，研究一种利用节点能量阈值来判断节点消耗，通过不断更新路径，改善热点路由问题。

发明内容

本发明的目的在于提供了一种基于能量梯度和APIT网格的GPSR路由算法，其改善热点路由造成的网络节点能耗不均的问题，通过预先设定节点能量阈值来减少全网节点死亡数，从而延长整个网络生命周期，提高数据传输效率。

本发明的技术方案是这样实现的：基于能量梯度和APIT网格的GPSR路由算法，包括汇聚节点，无线传感器节点组，其特征在于：汇聚节点在平面直角坐标系X轴和Y轴上的位置为（1000,1000）；无线传感器节点组2包括300个无线传感器节点（后简称“节点”），分别用Node(                                                )表示，=1,2,…,300。Node()随机分布在1000*1000的网络区域中，（）表示Node()在平面直角坐标系上的x轴和y轴坐标；无线传感器节点组中有N个节点分布在400*400的事件区域中,事件区域在平面直角坐标系上对应的x轴和y轴范围分别为0～400和0～400。无线传感器节点组2中的300个节点和汇聚节点1的通信半径均为250。

其具体的实现步骤如下：

1、对于无线传感器节点Node()，它的初始能量用表示，当前能量用表示，功率放大器的能耗用表示，自由空间消耗的能量用表示，发射电路消耗的能量用表示，=1,2,…,300。

2、汇聚节点将自己在平面直角坐标系下的x轴和y轴坐标发送给无线传感器节点组中的300个节点，无线传感器节点组2中300个节点记录汇聚节点1的x轴和y轴坐标。

3、对于事件区域中N个节点，用表示，=1,2,…N，（）表示节点Event()在平面直角坐标系上的x轴坐标和y轴坐标。根据公式

计算到汇聚节点1的距离表示,=1,2,…N。将()按照数值从小到大排序并形成所对应的点集队列Queue(l)，l=1,2,…,N。将Queue中Queue(1)作为目的节点，记该点为D，表示目的节点D在平面直角坐标系下的x轴坐标和y轴坐标。

4、将汇聚节点作为其到目的节点D的查询路径R的起点，记为节点R(1)，无线传感器网络中将非事件区域300-N个节点随机排列，构成非事件区域节点组，非事件区域节点组中的节点用Point表示，=1,2,…,300-N，（）表示非事件区域节点组Point。根据公式

计算Point到汇聚节点1的距离，z=1,2,…,300-N，设满足≤250的非事件区域节点组中的节点有M个，用Neighbor1 ()表示，=1,2,…,M，（）表示Neighbor1()在平面直角坐标系上的x轴和y轴坐标，根据公式

计算，=1,2,…,M，如果是最小数值，那么Neighbor1 ()作为查询路径R的第二个节点用R(2)表示，在平面直角坐标系上的x轴和y轴坐标为（）。

5、根据公式

计算Point到R(2)的距离，z=1,2,…,300-N，设满足≤250m的非事件区域节点组中的节点有L个，用Neighbor2()表示，=1,2,…,L，（）表示Neighbor2()在平面直角坐标系上的x轴和y轴坐标，根据公式

计算，=1,2,…,L，如果是中最小数值，那么Neighbor2()作为查询路径R的第三个节点R(3)。

6、重复步骤5，寻找查询路径R中的节点R (a)，，R()为目的节点D时，产寻结束，查询路径R长 ，共有个节点，依次为R (1),R (2),…,R()。

7、事件区域中除目的节点D外剩余N-1个节点，构成非目的节点组，非目的节点组中的节点用U_D表示，k=1,2,…,N-1,表示非目的节点组U_D，根据公式

计算，k=1,2,…,N-1。

    8、目的节点D将汇聚节点1沿查询路径R传来的数据洪泛传给非目的节点组U_D中的N-1个节点，根据公式

式中，的值为大于等于3000且小于等于4000的整数，计算目的节点D到非目的节点组中N-1个节点消耗的能量，用表示，k=1,2,…,N-1。根据公式

计算目的节点D当前剩余能量，用表示，式中=1,2,…N-1。

9、根据公式

式中，的值为大于等于3000且小于等于4000的整数，计算事件区域中N-1个节点每个节点到目的节点D的能量消耗，用表示，=1,2,…,N-1。根据公式

计算事件区域中N-1个节点中每个节点当前剩余能量，用表示，=1,2,…,N-1。

10、将查询路径R中个节点从后往前重新排列，构成反向路径R’，R’(1)= R(), R’(2)= R(),…, R’(b)= R()。目的节点D把收集到的数据沿反向路径R’传送到汇聚节点1，反向路径R’的起点R’(1)为事件区域中目的节点D，终点R’()是汇聚节点1，R’中的各节点在平面直角坐标系上的坐标用()表示，=1,2,…,。

11、根据公式

式中，s=1,2,…,-1，计算反向路径R’中每两个节点之间的距离，用表示，=1,2,…,-1。

12、根据公式

式中，的值为大于等于3000且小于等于4000的整数，计算反向查询路径R’中每个节点的能量消耗，用表示，=1,2,…,-1。根据公式

计算反向查询路径R’中每个节点当前剩余能量，用表示，=1,2,…,-1。

13、依次重复步骤10~12，直到至少出现以下两种情况中的一个：

(1)如果事件区域中的目的节点D当前剩余能量小于等于0，从Queue中选择Queue(l+1)代替原来的目的节点D，l=1,2,…,N-1。用节点Queue(l+1)的坐标代替原目的节点的坐标。

(2)对反向路径R’中的每个节点设定能量阈值0.2，如果反向路径R’中的某一个节点剩余能量小于等于0.2，该节点记为R’()(为1~-1中的一个值)。以节点R’()为顶点，节点R’()与节点R’()的连线为边，用[R’()R’()]表示。右手伸开，掌心向上，大拇指指向边[R’()R’()]的方向，从四指的方向上找到H个节点，用A()表示，=1,2,…,H。根据公式

式中，()表示节点R’()在平面坐标系上的x轴和y轴坐标，()表示节点组A()中每个节点在平面坐标系上的x轴和y轴坐标。计算节点组A()到节点R’()的距离，用表示，=1,2,…,H。选择中数值最小的节点，用a表示。将节点a更新顶点R’()，顶点R’()更新节点R’()，节点a与节点R’()的连线作为边更新边[R’()R’()]，用上面同样的方法找下一个点，依次找点并连线，直到找到的点连线围成一个多边形T，从节点R’()开始，顺时针遍历多边形T，遍历到的第一个节点作为新的节点代替反向路径上节点R’()，反向路径R’被更新。

14、重复步骤9~13，直到Queue中N个节点中每个节点的当前剩余能量(=1,2,…,N)小于等于0为止。

通过以上步骤可以建立查询路径R和反向路径R’，通过反向路径R’中每个节点的能量阈值更新路径，避免出现热点路由而引起的节点能耗不均匀问题。

       本发明的积极效果是在APIT定位的基础上，将其定位结果和网格扫描的长度用到GPSR路由建立的过程中，通过对节点能量预先设定阈值，从而避免了热点路由问题，有效地解决了节点能耗不均、部分节点过早死亡的问题，延长了节点寿命和整个无线传感器网络的生命周期。

附图说明

图1为本发明的示意图。

具体实施方式

下面结合附图和实施例对本发明做进一步的描述：如图1所示，基于能量梯度和APIT网格的GPSR路由算法，包括汇聚节点1，无线传感器节点组2，其特征在于：汇聚节点1在平面直角坐标系X轴和Y轴上的位置为（1000,1000）；无线传感器节点组2包括300个无线传感器节点（后简称“节点”），分别用Node()表示，=1,2,…,300。Node()随机分布在1000*1000的网络区域中，（）表示Node()在平面直角坐标系上的x轴和y轴坐标；无线传感器节点组2中有N个节点分布在400*400的事件区域中，事件区域在平面直角坐标系上对应的x轴和y轴范围分别为0～400和0～400。无线传感器节点组2中的300个节点和汇聚节点1的通信半径均为250。

其具体的实现步骤如下：

1、对于无线传感器节点Node()，它的初始能量用表示，当前能量用表示，功率放大器的能耗用表示，自由空间消耗的能量用表示，发射电路消耗的能量用表示，=1,2,…,300。

2、汇聚节点1将自己在平面直角坐标系下的x轴和y轴坐标发送给无线传感器节点组2中的300个节点，无线传感器节点组2中300个节点记录汇聚节点1的x轴和y轴坐标。

3、对于事件区域中N个节点，用表示，=1,2,…N，（）表示节点Event()在平面直角坐标系上的x轴坐标和y轴坐标。根据公式

计算到汇聚节点1的距离表示,=1,2,…N。将()按照数值从小到大排序并形成所对应的点集队列Queue(l)，l=1,2,…,N。将Queue中Queue(1)作为目的节点，记该点为D，表示目的节点D在平面直角坐标系下的x轴坐标和y轴坐标。

4、将汇聚节点1作为其到目的节点D的查询路径R的起点，记为节点R(1)，无线传感器网络中将非事件区域300-N个节点随机排列，构成非事件区域节点组，非事件区域节点组中的节点用Point表示，=1,2,…,300-N，()表示非事件区域节点组Point。根据公式

计算Point到汇聚节点1的距离，z=1,2,…,300-N，设满足≤250的非事件区域节点组中的节点有M个，用Neighbor1 ()表示，=1,2,…,M，（）表示Neighbor1()在平面直角坐标系上的x轴和y轴坐标，根据公式

计算，=1,2,…,M，如果是最小数值，那么Neighbor1 ()作为查询路径R的第二个节点用R(2)表示，在平面直角坐标系上的x轴和y轴坐标为（）。

5、根据公式

计算Point到R(2)的距离，z=1,2,…,300-N，设满足≤250m的非事件区域节点组中的节点有L个，用Neighbor2()表示，=1,2,…,L，（）表示Neighbor2()在平面直角坐标系上的x轴和y轴坐标，根据公式

计算，=1,2,…,L，如果是中最小数值，那么Neighbor2()作为查询路径R的第三个节点R(3)。

6、重复步骤5，寻找查询路径R中的节点R (a)，，R()为目的节点D时，产寻结束，查询路径R长 ，共有个节点，依次为R (1),R (2),…,R()。

7、事件区域中除目的节点D外剩余N-1个节点，构成非目的节点组，非目的节点组中的节点用U_D表示，k=1,2,…,N-1,表示非目的节点组U_D，根据公式

计算，k=1,2,…,N-1。

    8、目的节点D将汇聚节点1沿查询路径R传来的数据洪泛传给非目的节点组U_D中的N-1个节点，根据公式

式中，的值为大于等于3000且小于等于4000的整数，计算目的节点D到非目的节点组中N-1个节点消耗的能量，用表示，k=1,2,…,N-1。根据公式

计算目的节点D当前剩余能量，用表示，式中=1,2,…N-1。

9、根据公式

式中，的值为大于等于3000且小于等于4000的整数，计算事件区域中N-1个节点每个节点到目的节点D的能量消耗，用表示，=1,2,…,N-1。根据公式

计算事件区域中N-1个节点中每个节点当前剩余能量，用表示，=1,2,…,N-1。

10、将查询路径R中个节点从后往前重新排列，构成反向路径R’，R’(1)= R(), R’(2)= R(),…, R’(b)= R()。目的节点D把收集到的数据沿反向路径R’传送到汇聚节点1，反向路径R’的起点R’(1)为事件区域中目的节点D，终点R’()是汇聚节点1，R’中的各节点在平面直角坐标系上的坐标用()表示，=1,2,…,。

11、根据公式

式中，s=1,2,…,-1，计算反向路径R’中每两个节点之间的距离，用表示，=1,2,…,-1。

12、根据公式

式中，的值为大于等于3000且小于等于4000的整数，计算反向查询路径R’中每个节点的能量消耗，用表示，=1,2,…,-1。根据公式

计算反向查询路径R’中每个节点当前剩余能量，用表示，=1,2,…,-1。

13、依次重复步骤10~12，直到至少出现以下两种情况中的一个：

(1)如果事件区域中的目的节点D当前剩余能量小于等于0，从Queue中选择Queue(l+1)代替原来的目的节点D，l=1,2,…,N-1。用节点Queue(l+1)的坐标代替原目的节点的坐标。

(2)对反向路径R’中的每个节点设定能量阈值0.2，如果反向路径R’中的某一个节点剩余能量小于等于0.2，该节点记为R’()(为1~-1中的一个值)。以节点R’()为顶点，节点R’()与节点R’()的连线为边，用[R’()R’()]表示。右手伸开，掌心向上，大拇指指向边[R’()R’()]的方向，从四指的方向上找到H个节点，用A()表示，=1,2,…,H。根据公式

式中，()表示节点R’()在平面坐标系上的x轴和y轴坐标，()表示节点组A()中每个节点在平面坐标系上的x轴和y轴坐标。计算节点组A()到节点R’()的距离，用表示，=1,2,…,H。选择中数值最小的节点，用a表示。将节点a更新顶点R’()，顶点R’()更新节点R’()，节点a与节点R’()的连线作为边更新边[R’()R’()]，用上面同样的方法找下一个点，依次找点并连线，直到找到的点连线围成一个多边形T，从节点R’()开始，顺时针遍历多边形T，遍历到的第一个节点作为新的节点代替反向路径上节点R’()，反向路径R’被更新。

14、重复步骤9~13，直到Queue中N个节点中每个节点的当前剩余能量(=1,2,…,N)小于等于0为止。

通过以上步骤可以建立查询路径R和反向路径R’，通过反向路径R’中每个节点的能量阈值更新路径，避免出现热点路由而引起的节点能耗不均匀问题。