Zheng Kai, Tong Libiao, Lu Wenjun

（New Star Research Institute of App lied Technologies, Hefei 230031, P. R. China）

Abstract:Routing algorithms based on geog raphical location is an important research sub ject in the Wireless Sensor Network（WSN）.They use location in formation to guide routing d iscovery and m aintenance as well as packet forward ing,thus enab ling the best routing to be selected,reducing energy consum p tion and op tim izing the whole network.Through three aspec ts involving the flood ing restriction schem e,the virtual area partition scheme and the best routing choice scheme,the im portance o f location information is seen in the routing algorithm.

T he Wireless Sensor Network（WSN）is an intelligentautonomous monitoring system where lots of m icro sensornodes w ith communication and computing capabilities are dep loyed in the unattended monitoring regions.In actual app lications,especiallym ilitary,itis often required to locate the sensornodes in order to ob tain the geog raphical location information ofamonitoring region.As a result,itis a naturalthing to consider location information in the design ofWSN routing algorithms.The routing algorithm based on location information has become an im portantsub jectin current WSN research and has attracted w idesp read attention.

The location information-based routing algorithm uses location information to guide routing d iscovery and maintenance as wellas data forwarding,enab ling d irec tional transm ission of the information and avoid ing information flooding in the entire network.Consequently,the control overhead of the algorithm is reduced,and routing is op tim ized.Moreover,w ith network topology based on nodes'location information,network managementbecomes sim p le and g lobalnetwork op tim ization can be easily achieved.

The researchers around the world have put forward several location information-based routing algorithm s for various app lication scenarios.Among other issues,how tomake fulluse of location information to achieve efficient routing is a focus.This paperanalyzes the app lication of location information in routing algorithms from three aspects:flooding restric tion,virtualarea partition,and op timalrouting choice.

1 Flooding Restriction

Trad itional flooding routing p rotocols have such advantages as simp licity and robustness［1］,many ofwhich have adop ted the flood ing routing idea.However,flooding routing is ap t to information redundancy and＂im p losion＂,b ringing unwanted resource consum p tion.To add ress this p rob lem,location information,such as distance and position,is used to guide and restrict the flood ing by defining the search region of flood ing routing,thus the orientation and effectiveness of routing search are g reatly imp roved.When no suitab le path is availab le in the restricted region,flood ing region would be adap tively ad justed,or traditional flood ing methodswould be used to continue routing search.Flooding restric tion comes into several form s,inc lud ing d istance-based,ang le-based,and rectang le-based.

1.1 Distance-Based Flooding Restriction

When the location ofa target region is uncertain,a sim p le d istance-based flood ing restriction region can be c reated:The routing search information is flooded to the nodes faraway from the sender.Onlywhen a node faraway from the sender receives the data packet,it forwards the packet.In this way,information redundancy is reduced.When the location ofa target region is certain,a requestzone can be created w ith the nodes nearer than the target region.The Location-Aided Routing（LAR）scheme fordeterm ining the requestzone adop ts this concep t［2］.

1.2 Angle-Based Flooding Restriction

In the ang le-based flood ing restriction mechanism,the restricted region is determ ined by an ang le.That is to say,only the intermediate nodes thatare in a certain ang le range can be used as relay nodes for routing flood ing.There are many ways to decide the restric tion ang le.Figure 1,Figure 2 and Figure 3 illustrate three of them.

In Figure 1,the ang le-restricted region is confined by the two rays:OM and OP［3］and the restriction ang le∠SOM is determ ined as follows:First,use the source node S and the destination node D as the centers and RSand Rd（supposing RS＞Rd）as the rad iuses respec tively to form two circ les;then d raw the two common tangents of the two circ les,whichmeetatpoint O;and finally,calculate the deg ree of the restriction ang le∠SOM.The sizes of RSand Rdare ad justab le,depend ing on specific app lications.

In Figure 2,the restriction ang le is variab le rather than fixed.Assume S is the source node,D is the destination node,and X is an intermed iate node.The routing requestpacket forwarded by X contains the restriction ang le∠DXM,which is calculated outw ith the follow ing formula:

▲Figure 1. Restriction region constructed with a fixed angle.

▲Figure 2. Restriction region constructed with variable angles.

▲Figure 3. Restriction region constructed with a predefined angle.

When nodes Jand K receive the data packet forwarded by X,they compute∠DXJ and∠DXK respectively,and com pare them w ith∠DXM.If the com puted ang le（e.g.∠DXK in this case）is g reater than∠DXM,the related node（K）d rops the packet;if the com puted ang le（e.g.∠DXJ in this case）is less than∠DXM,the node（J）continues to forward the data packetand updates the restric tion ang lew ith the computed one（∠DXJ here）.

In Figure 3,the routing request packetof the source node S inc ludes its own location information and a p redefined restriction ang le［4］.Afteran intermed iate node M receives the packet,ituses trigonometric formulae to compute its inc luded ang le（∠SMD）w ith the source node Sand the destination node D.If∠SMD is g reater than the p redefined restriction ang le,the node M continues to forward the packet,otherw ise,itd iscards the packet.The p redefined restriction ang le can be set based on actualapp lications.

1.3 Rectangle-Based Flooding Restriction

Rectang le-restric ted region is a rectang le flood ing region determ ined by certain policies.Figures 4 and 5 illustrate two ways of constructing such a rectang le.

In Figure 4,the restriction rectang le is construc ted using source node S and destination node D as two vertexes.To inc rease the success rate of routing request,the destination can be expanded into a circ le w ith a radius of R.The R should notexceed the communication rad ius of the destination node and its value can be ad justed according to the density of the nodes.Generally,in order to ensure the success rate of routing,the R is set to be a small value if the nodes are densely dep loyed,buta large value if the nodes are sparse.

In Figure 5,the rectang le restriction region is constructed［5］as follows:source node S and destination node D are the centerpoints of two sides（i.e. L1and L2）of the rectang le respectively,which are verticalto the line passing through S and D.The other two sides L3and L4are parallelw ith the line passing S and D.w is the leng th of L1and L2）,which sizes can be ad justed forac tualapp lications.

In add ition,the p rotocols which d ivide the entire region into g rids and flood queries w ithin each rectang le g rid,such as Two-TierData Dissem ination（TTDD）［6］,can be also regarded as a constructionmethod for restriction rec tang le.

2 Virtual Area Partition

▲Figure 5. Restriction rectangle constructed using source and destination nodes as side centers.

The virtualpartition scheme firstdivides the entiremonitoring region intomany sub-regions by location and then designs the routing accord ing to the location information of the sub-regions.This scheme is scalab le and suitab le for large-scale networks because itsolves the coord ination p rob lem using organizationalstructure design.The location information inc luded in each sub-region can help routing setup and enab le d irectionaltransm ission,thus avoid ing b lindness in information transm ission and reducing redundancy;and meanwhile,it facilitates information fusion and mobile node p rocessing,thus allow ing better real-time transm ission.Moreover,by allocating and scheduling the tasks among the nodes in a region,some nodes can be in sleep ing state,lead ing to energy saving and longer network lifetime.

Virtualarea partition can be realized inmany forms,inc lud ing regular geometricalpattern,virtualpolar coordinate system,and c lustering-based irregular partition.In p ractice,the entire network can be evenly d ivided into severalg rids,or d ivided into severalsub-regions unevenly based on node density,connectivity and network scale.A routing search can be done in two steps:Intra-region routing and inter-region routing.

2.1 Regular Partition

Regulargeometric patterns thatare used fornetwork partition inc lude rectang le,regularhexagon,triang le,diamond,circ le,and sector.The regularhexagonal pattern adop ts the cellmechanism in cellularnetworks butit is seldom used because itinvolves very comp licated com puting.The circ le partitionmethod determ ines a node's partition by comparing the partition rad iusw ith the distance from the node to the center,but the partitionsmay overlap at their boundaries.Reference［7］discusses triang le and d iamond partitionmethods,which d ivide the network into triang le or d iamond grids respectively.In Reference［8］,the network is d ivided into annulus sectorgrids.In p ractice,rectang le partitionmethod is used the mostbecause there is notany overlapped area,and its imp lementation is very simp le.

Among all rectang les,square g rid is themostcommon used inmany p rotocols,for instance,Geog raphical Adap tive Fidelity（GAF）［9］,TTDD,GRID and Grid-Clustering Routing Protocol（GROUP）［10］.Here we analyze several typ icalsquare grid-based routing p rotocols.

In GAF,the whole network area is d ivided into smallvirtualg rids based on the nodes'location information and communication ranges,ensuring thatany two nodes,which are in two ad jacent g rids respectively,can d irectly communicate w ith each other.Assume the communication range ofallnodes is R,and the side of the virtualgrid is r.To ensure communication between nodes in o g rids,it is required to satisfy Within a g rid,the topology control algorithm is adop ted to letsome nodes be in the sleep ing state,thus achieving energy conservation.Meanwhile,the states ofallnodes are controlled w ith a state transitionmechanism.The core concep tofGAF is to keep the network connective by letting the rep resentative node in each virtualg rid be always active.

In TTDD p rotocol,whenmultip le nodes detectan event,they selectone node as the source node to send the data.This source node itselfacts as one crossing point to constructa g rid.The construction p rocess is as follows:The source firstcalculates the locations of its fourneighboring dissem ination points and simp ly uses g reedy forward ing algorithm to requesta neighbornode that has the smallestd istance to any d issem ination point to be a forward ing node.The neighbornode continues the forward ing in a sim ilarway tillthe request times outor the edge of the network is reached.The forward ing node saves the eventas wellas the source node information,and w illbe a participant in future data transm ission.When a sink queries data,it floods the query among the dissem ination nodes and the flood ing stops until finally the query reaches the source.The queried data are then transm itted to the sink in a reverse d irection.

In GRID p rotocol,the entire network is d ivided intomany virtualg rids of the same size,and a path ismade up ofa g roup ofspecific virtualgrids.By certain

2.2 Virtual Polar Coordinate System

Virtualpolar coord inate system is a specialang le partitionmethod.The basic idea ofGraph Embedd ing（GEM）［11］for data-centric storage is to build a virtual polar coordinate system to align w ith the ac tualnetwork topology.The nodes in the network form a ringed tree whose root is a convergence node.Each node is denoted w ith the numberofhops to the rootof the tree and a virtualang le range,and the node-to-node routing is denoted w ith a ringed tree.The virtual polar coordinate system is created as follows:The rootnode assigns each child node an ang le range,e.g.［0,90］,which size is p roportionalto the size of that child node's sub tree.Each node then assigns each of its child nodes a subset of its ang le range.The p rocess continues recursively untilevery leafnode is assigned an ang le range.In thisway,a node can assign ang le ranges to its child nodes based on a uniform rule（e.g.c lockw ise）,enab ling the ang le ranges assigned to the nodes at the same level to increase or decrease p roportionally.

Thus the nodes thatare the same hops away from the root form a ring and the entire network becomes a ringed tree whose root is the convergence node.The basic routing p rocess of the virtualpolar coord inate system is:When a node sends a data packet,it forwards the packet to its parent if the destination'smeans,each g rid selects a node as the gateway,which is responsib le for forward ing alldata packets thatpass this grid and the routing is from one g rid to another.Reference［5］gives several methods ofdeterm ining grid side length.Simulations show thatonce the side length r meets the follow ing requirement:

（where R is the communication rad ius of the node）,the nodes in two d iagonalg rids can communicate w ith each otherw ithoutany obstac le.That is to say,a node can communicatew ith nodes in its eightneighborg rids.

In GROUP,the sink selects a seed node periodically and builds a virtualg rid structure of certain w id th based on the seed node.In each g rid,a node is selected as the c lusterhead,which is often near to the grid intersec tion.The nodes around the head belong to this c luster.ang le is notw ithin its ang le range.The parent,in turn,uses the samemethod to hand le the packet.The routing goes on in thismanneruntilthe packet reaches the node whose ang le is c loser to the destination ang le range.

2.3 Clustering-Based Irregular Partition

Location information also p lays an important role in the c lustered routing.The c lusters com ing from d ifferent c lustering algorithms are irregularand form virtualnetwork sub-regions.In a c luster,the c lusterhead is the basis for c luster construction.One im portant c riterion used in c lusterhead election algorithm s is location information of the c luster,inc luding the d istance ofa node to the c lusterhead,the distance of the c lusterhead to the BS and the ratio of d istance to energy consump tion.For exam p le,the Cluster-head Election using Fuzzy Logic（CEFL）［12］algorithm uses node centrality as a criterion for c lusterhead election.The centrality means how much a node app roaches the c luster center,which is calculated on the basis of the sum of the squared d istances of the node to othernodes in the c luster.After c lusterheads are elected,the nodes around the heads w ill selectively join the c lusters based on the distribution ofc lusterheads.In Energy EfficientClustering Scheme（EECS）［13］p rotocol,the distance from a node to the c lusterhead and the d istance from the c lusterhead to the BS are considered in the formula for computing the costat which the node decides to join a c luster.

3 Optimal Path Choice

In selec ting nodes formulti-hop forward ing,certain criteria are often followed to choose the op timalnode.The op timalpath choice scheme based on location information is supposed to use the location information such as ang le or d istance as a route selection criterion.In the follow ing chap ters,we d iscuss several typicalrouting algorithm s to exp lain the importance of location information in choosing the op timalpath.

3.1 GPSR

Greedy Perimeter Stateless Routing（GPSR）［14］is a typ icalp rotocolthatadop ts greedy forward ing algorithm.When a node is required to forward data packets,it firstselec ts the nearestneighboras the next-hop node,and then forwards the packets to the node.To add ress the local op tim ization p rob lem arisen from g reedy algorithm,that is,a satisfying next-hop node is notavailab le,GPSR suggests perimeter forward ing algorithm,which acts as a supp lement to greedy forwarding algorithm.This algorithm constructs a p lanargraph on the original network topology to solve the route hole p rob lem.That is to say,the route is recovered by routing to the destination around the edge of the g raph.The full GPSR p rotocolcombines g reedy forwarding algorithm w ith perimeter forwarding algorithm to achieve routing to destination node.In the network,g reedy forwarding is themain app roach for routing,butwhen satisfying next-hop nodes are notavailab le,the perimeter forward ing algorithm is used on the p lanargraph to choose the next-hop.

3.2 GEAR

Geog raphic and Energy Aware Routing（GEAR）［15］sets up a path from the source node to the target region bymeans of query.Taking advantage of the g reedy algorithm in GPSR,this p rotocoluses the nodes'location information aswellas the remaining energy levelto select the neighbornode w ith the leastoverall overhead（a combination of the distance to the destination and the remaining energy level）for forwarding and thus sets up a path to the target region for the query packet.After the query packet reaches the target region,recursive geog raphic forward ing or restricted flood ing can be used to dissem inate the packet.

In recursive geog raphic forward ing app roach,the node that first receives the query requestw ithin the target region sp lits the target region into several sub-regions and forwards the query request to the centers ofallsub-regions.Sim ilarly,the node nearest to the center ofa sub-region,upon receiving the query request,furthersp lits the sub-region into severalsmallerones and forwards the query request.This recursive sp litting and forward ing p rocedure is repeated untila node finds itself the only one inside the sub-region.After the forward ing p rocedures in all sub-regions finish,the entire recursive p rocedure term inates.This app roach is bettersuitab le for the app lications where the nodes are densely dep loyed.

3.3 TBF

Trajectory Bas ed Forward ing（TBF）［16］uses parameters to specify a trajec tory rather than routing node sequence in packetheaders.Each forward ing node,based on its trajectory parameterand its neighbors'locations,makes g reedy decision to find the nearestnode and selectitas the next-hop node.By specifying d ifferent trajectory parameters,multipath p ropagation or broadcastas wellas b roadcastor multi-cast in a specific region can be easily achieved.

3.4 SPAN

SPAN［17］is an energy-efficient coordination algorithm which elec ts some nodes as coordinators based on their locations.These elec ted coordinators form a backbone,specially responsib le formessage forwarding.The nodes that do not join the backbone w illgo to sleep periodically.Each node in the network can independently and periodically decide whether itshould sleep or wake up.

4 Conclusions

The routing algorithm s based on location information are an im portantsub jec tin the research of routing p rotocols.In the long term,these algorithm s should be further stud ied from the follow ing perspec tives:

（1）Combination w ith location technologies:Mostofexisting geog raphic routing p rotocols do not discuss the specificmethod to ob tain the location information ofa node,and their research is always carried outupon the assum p tion that the node's location information is known.In fact,the location technology is stillan importantand challenging sub jectin currentWSN research because the location p rocedure and p recision have great im pacton the design of routing p rotocols.With location algorithms being combined w ith and the im pactof location p recision on p rotocol performance being taken into account,the routing p rotocols can bemuchmore effective and app lication-specific.The Geog raphic Routing w ithout Location Information（GRWLI）［18］suggests a routing mechanism,where only a few nodes'p recise locations are used.The key of the algorithm is to use some beacon nodes to construc ta g lobal coordinate space as wellas the positions ofothernodes in the coord inate space.

（2）The im pactof topog raphy on routing algorithm s:In actualapp lications,WSNs are often affected by topographical factors,such as land form and surface feature.Some ofexisting routing algorithm s are based on a virtual 2-d imensionalgeog raphic space rather than actualenvironments.As a result,the actualgeog raphic environmentis also an issue to be add ressed in the research of routing p rotocols.

（3）Coverage control:Another issue thathas to be considered in the design of routing p rotocols is the node's connectivity and network coverage.Particularly,the coverage controlhas to be analyzed when sleeping mechanism is inc luded in the routing design.

（4）Security:Inmany app lications,especiallym ilitary,the security of routing p rotocolsmustbe considered.For exam p le,Reference［19］studies geog raphicallocation-based key d istribution.

（5）Routing p rotocols forunderwater,deep space and underg round WSNs.Related research should be done for these specialapp lication scenarios.