Improvement and Simulation Analysis of GPSR

SUN Yulu,ZHANG Deyu,LV Yanhui

(Shenyang Ligong University,Shenyang 110159,China)

Wireless sensor networks (WSN,Wireless Sensor Networks) is made up of mounts of low-power-consumption,low-cost and tiny Sensor nodes,which are deployed in monitoring area.Nodes collect and process the information of the monitored object in the covered region through wireless radio communication,and transmit the information to the observer (Sink) at last.It can greatly reduce the routing control information in the network and improve network performance by using GPS positioning module which can obtain location information.When the location of the destination node is known,it can be carried in the packets.According to local and geographical topology information,the source node and each relay node can select a logical next hop to translate the packets to the final destination node.Based on the location information of the neighbor nodes,GPSR referred in literature[1]selects the closest neighbor node to the destination node as forwarding node.when the greedy algorithm failure,that is to say,there is “hole” appear in the network,GPSR algorithm establishes floor plan and forwards packets with boundary forwarding node to translate packets.But in GPSR algorithm,neighbors simply compare the distance to the destination node,which will bring single-path and hot spots issues.In addition,the boundary forwarding node will causes an increase in the number of hops and wastes energy as well.Therefore,many scholars have conducted the research and proposed improvement of GPSR.Literature[2]distributes the forward region many parts according to the residual energy of neighbor nodes,and uses probabilistic transmission mechanism to select the next hop in certain parts.The algorithm can effectively balance the load of the network,and improve network performance at the same time.However,there is redundancy among the parameters,and the formula is complex.Literature[3]proposed a dynamic load balancing capabilities routing algorithm,which introduces distance factor and energy factor.The algorithm proposed stochastic routing strategy and deterministic routing strategy,which are better solutions to hot spots and single path issues in GPSR.In order to solve the hole problem,GPSR algorithm uses the right-hand rule in the boundary forwarding node to forward packets.Literature[4]focuses on improving the boundary forwarding node in GPSR by reducing routing lines and jumps in GPSR.In the literature[5],nodes will notify the parent node once come across the hole.In this way,the source node predicts the hole when forward packets nest time.Literature[6]proposed AGAR algorithm,which utilizes inspired function to get location information for path optimization.Literature[7]proposed ellipse-around-the-hole algorithm,in which the node labels hollow points around after a hole is discovered,calculates the minimum ellipse that can cover the hole,and then sends packets along the elliptical boundary.Literature[8]calculates a closer node to the target by using two adjacent nodes,to forward packets.The algorithm,to a certain extent,reduces the potential probability of encountering the hole.Literature[9]argues that nodes can use landmark nodes to compare the number of hops to select optimum path.Literature[10]suggest that nodes can obtain the shortest path signpost lists by sending probing packets,and nodes can forward the next packets to the node in the list as intermediate.The algorithm can solve the hole problem automatically.

An improved algorithm GPSR-EA is proposed in this paper.Nodes firstly detect the energy to exclude nodes whose energy is less than the preset threshold to prevent the low power nodes from being the next hop.Then distance factor,energy factor and angle factor are introduced to choose the nest hop to forward packets.GPSR-EA can effectively balance the network energy consumption and extend the network life cycle.

1 ANALYSIS OF GPSR ALGORITHM

1.1 GPSR algorithm

GPSR algorithm is a geographic routing algorithm based on the greedy forwarding.In order to avoid routing failure caused by the communication hole in greedy forwarding and the overhead of routing due to the repeatedly request,GPSR generates a planar sub-graph according to the network topology and border along the hole graph to forward packets.GPSR algorithm has two patterns to forward packets:greedy forwarding mode and boundary forwarding node.The algorithm default uses greedy forwarding node to forward packets.When greedy forwarding node does not work,namely nodes meet communication holes,boundary forwarding node begin to run.Nodes will continue to run greedy forwarding node as its condition is met.Two modes switch repeatedly until the packet reaches the destination.

Figure 1 Greedy forwarding node

1.2 The shortage of GPSR

The mainly shortage of GPSR algorithm can be concluded as two points:

1)In GPSR algorithm,nodes simply select the nearest neighbor node to destination as the nest hop to translate packets.The node selected to forward packets won’t change until its energy runs out.Otherwise,other nodes which are not on the path have not been fully taken advantage of.Therefore,the hot spots and single path issues come across and come to be the mainly problem of GPSR algorithm.

2)When greedy node fails,nodes running GPSR algorithm turn into boundary forwarding node to tackle the hole problem,while using the right-hand rule to bypass holes.This node can increase the number of routing hops which accordingly add the end-to-end delay.In addition,the mode will cost a large amount of energy.

Mainly aimed at solving the hot spots and single path issues in GPSR algorithm,the improved algorithm GPSR-EA is proposed in this paper.

2 GPSR-EA ALGORITHM

2.1 Network model assumptions

1) Nodes don’t move after being deployed,and nodes are unavailable only when its energy runs out.

2) The topology structure will only dynamically change due to nodes’ failure.

3) Nodes can obtain their own location by using GPS positioning module,and the location of destination node is carried in packets,so that other nodes can obtain the location information of destination node once they receive the packets.

4) Nodes maintain a neighbor table,which includes the location information of neighbor nodes,the node residual energy information,etc.Nodes update the neighbor table regularly.

2.2 The flow chart of GPSR-EA algorithm

The process of nodes running GPSR-EA algorithm is shown in Figure 2.

2.3 Factors of routing rule

According to the above analysis,nodes running GPSR-EA algorithm choose the following three factors to be components of the priority of the rule.

1) The distance of the node to the neighbor nodes and the distance of neighbor nodes to the destination node.The nearer the distance to the destination node is,the less delay for nodes to deliver packets.

2) The residual energy of neighbor nodes.Nodes balance the energy consumption caused by forwarding packets to the nodes with larger residual energy as far as possible,and prolong the network life cycle in this way.

Figure 2 GPSR-EA algorithm flow chart

3) Node deflection Angle,namely node point of view of deviating from the destination node.The smaller Routing node deflection Angle is,the higher node′s energy efficiency is,with the better convergence.

2.4 Analysis of routing rule in GPSR-EA algorithm

Firstly,nodes collect the neighbor nodes in the forward area where nodes select from as the nest hop to forward packets.Secondly,nodes exclude the node whose energy is less than the preset threshold value to avoid them to participate data-forwarding.At last,nodes select the certain neighbor node based on the new routing rule in GPSR-EA algorithm to forward packets.Nodes calculate one priority of all the neighbor nodes in the forward area,and compare the value to select the node with the greatest priority as the nest hop.The priority consists of three parts:distance factor,energy factor and angle factor.The formula to calculate the priority is:

P=Ei/E+SD/(NiD+NiS)+cosα+r(x)

(1)

In the formula,Eirepresents the node residual energy,Erepresents the sum of nodes’ energy,Srepresents the source node,Drepresents the destination node,Nirepresents the forwarding node,αrepresents the deviation angles,andr(x) is a small random number,to ensure the value ofPis unique.

Figure 3 Show of the three factors

In order to avoid the loop,set the forward area.Distance of nodes to destination in forward area is nearer than the certain node which is running GPSR-EA algorithm.The forwarding area can be shown in the shaded area in the figure 3.

When nodes’ location is available,GPSR algorithm only refers to the distance of nodes to destination,ignoring the distance between the source node and the forwarding node,and blindly chooses the nearest node to destination as the nest hop.Therefore,to be more scientific and reasonable,GPSR-EA algorithm adds the distance between source node and the forwarding node as a factor in the priority.The distance factor is expressed asSD/ (NiD+NiS) in the formula.

To solve the hot spots and single path issues in GPSR algorithm,the energy factor is introduced.Nodes can gain its left energyEfrom battery power.Nodes should select the node with larger residual energy in the forward area as the forwarding node,so as to balance the nodes’ energy consumption in the network,and improve the network life cycle as well.So the energy factor is set to beEi/E.In wireless sensor networks,when the residual energy of nodes is lower than the preset threshold,nodes should be avoided as the forwarding nodes,while the remaining energy being used to capture and send their own information and accept the necessary control information.

Relative to the destination,the deviation angle alpha of each node is also different.The smaller the alpha is,the higher the node′s energy efficiency is.So the angle factor is introduced into the priority,using cosα to say.Cosα can be calculated by the formula as follows:

(2)

In addition,the distance factor is in the form of a ratio in the priority,so is the energy factor.As a result,the value of the priority calculated may be equal after the value of all the three factors being added together.Therefore,a random factorr(x),is introduced into the expression to avoid the equal value of priority.r(x) gets its random value from a very small range,and would not change the compared result.

3 ANALYSIS OF GPSR AND GPSR-EA

The NS2[11]simulator was originally developed by UC Berkeley of the University of UNIX system development based on network environment.It is an open-source and free software simulation platform which provides rich component library.The simulator is a discrete time scheduler,scheduling of network events in the event queue.It introduces two kinds of language C++ and OTcl to simulate networks while using TclCL mechanism to sharing data.

Based on NS2 environment,a large amount of simulation experiments have been done and the two algorithms are compared in the same scene.The initial energy is set 1000 mJ and nodes send hello packet every 2 seconds to establish and maintain the neighbor table.The scene parameters are as shown in the table 1.

Table 1 Scene parameters list

1)In wireless networks,the energy gap between nodes can reflect the performance of routing protocol balancing energy consumption ,energy of different nodes are selected to be compared in the two algorithm.The comparison and analysis of energy changes between nodes in the same scene are as shown in the figure 4.

In GPSR algorithm,nodes choose the neighbor node nearest the destination node as next hop according to the distance to the destination.For a particular node in the network,the next-hop node is fixed in a certain period of time.Nodes will not reselect other neighbor nodes unless the energy of the next hop node consumed over,so the nodes on the path in a network will be hot spots.As a result,the energy distribution of the entire network is uneven,and the energy of the nodes on the path decrease obviously more fast than those not on the path.On contrary,due to the introduction of energy factor in the improved GPSR-EA,nodes choose next hop according to the variation of the energy.Therefore,there is no too big gap between nodes in the energy consumption rate.

Figure 4 Energy changes of node 35 and 44 in the two algorithms

2)In the same scene,the network Maximize Lifetime[12](the time of the first node die in the network) were compared,and the experiment results are as follows:

As is shown in the figure 5,in GPSR algorithm,nodes begin to die earlier than in the improved GPSR-EA algorithm.What is more,the number of dead node is larger than the improved algorithm at any moment during the last period.The reason is,in GPSR algorithm,nodes will not choose other neighbor nodes,until the forwarding node runs out of energy.The nodes on the path will die soon as well.Instead,Nodes dynamically select next hop in improved GPSR-EA algorithm,and energy consumption of neighbor nodes is more balanced.Therefore,nodes begin to die later and there is less nodes dead in the network.After 150s,the cbr flow stops,and no new node dies any more.

Figure 5 Comparition of the deadtime in the network

3)In the same scene,the end-to-end delay[13](the time cost from the source node to the destination node) in the networks is shown as the figure 6.

Figure 6 End-to-end delay of the two algorithms

Can see from the figure above,the end to end delay between the two algorithms is also slightly different and the GPSR-EA algorithm’s delay is longer on the whole.However,the experimental results are accurate and reasonable.Based on GPSR algorithm,it is the nearest neighbor node to destination that is selected to forward packets.Hop count is the least,which caused the least delay.But,in the improved GPSR-EA,because of the introduction of new factors,nodes will not always choose the nearest neighbor node to destination as the next hop,which,as a result,will increase the end-to-end hop.At the same time,the delay is larger.

4 CONCLUSION

GPSR-EA algorithm introduces three factors,distance of neighbor nodes to destination,node′s residual energy and Point of view of neighbor nodes deviating from the destination,as a new routing rule to forward packets.Simulation results indicate that the algorithm can effectively balance the network energy consumption and prolong network to maximize survival time.But at the same time,due to the increase of the hop count,the end-to-end delay of the network is slightly increased,which is sacrifice for balancing the network energy consumption and prolonging the network lifetime.Overall,the improved GPSR-EA algorithm has better network performance and adaptability.

[1] Karp B,Kung H．GPSR,Greedy perimeter stateless routing for wireless networks[C].In Proceeding of the 6th Annual Int’l Conf.on Mobile Computing and Networking.Boston,USA,2000,49(3):243-254.

[2] WU Sanbin,WANG Xiaoming,YANG Tao.Improved GPSR model and simulation analysis[J].Computer Engineering and Applications,2011,47(8):100-104.

[3] LIU Yu,ZHAO Zhijun,SHEN Qiang.Energy-aware dynamic load balance routing of GPSR[J].Computer Engineering and Applications,2011,47(6):23-25.

[4] HAN Liansheng,LUO Weibing,LI Nan-xiang.Research and improvement of greedy geographical routing protocol[J].Computer Engineering and Applications,2007,43(36):160-162.

[5] WANG Guojun,WANG Tian,JIA Weijia.An location routing algorithm based on the travel inspiration in wireless senior networks[J].Journal of Sensior Technology,2007,20(2):382-386.

[6] JIANG Youfu,WU Weizhi.An heuristic ad hoc routing protocol based on geographic location[J].Computer Engineering,2008,34(1):137-139.

[7] LIANG Xiaoman,WANG Guojun,XIE Yongming.An ellipse around hole algorithm in wireless senior networks[J].Computer Engineering,2009,35(12):78-81.

[8] WANG Jianxin,ZHAO Xiangning,LIU Huiyu.An greedy routing algorithm based on geographic location while the information of two-hops neighbors is kown[J].Journal of Electronics,2008,36(10):1903-1909.

[9] Na J,Kim C.GLR.An Geographic Routing Scheme for Large Wireless Ad Hoc Net works[J].Computer Networks,2006,50(17):3434-3448.

[10]ZHANG Hengyang,WANG Ling,LIU Yunhui.An Adaptive hole processing algorithm with Iterative extraction and strip of sign[J].Journal of Software,2009,20(10):2744-2751.

[11]XU Leiming,PANG Bo,ZHAO Yao.NS and network simulation[M].Beijing:Tsinghua University press,2005.

[12]TANG Sulan.Research on Maximize Lifetime of Wireless Sensor Networks[J].Information Technology and Standardization,2009,15(7):1671-1679.

[13]HAN Yue,LIU Zengji,YAO Mingwu.Exponential Supermartingale for the Stochastic Analysis of End-to-End Delay[J].Computer Networks,2012,35(10):1016-1024.