Geographic routing (also called georouting or position-based routing) is a

routing Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone netw ...

principle that relies on

geographic position The geographic coordinate system (GCS) is a spherical or ellipsoidal coordinate system for measuring and communicating positions directly on the Earth as latitude and longitude. It is the simplest, oldest and most widely used of the various ...

information. It is mainly proposed for

wireless network A wireless network is a computer network that uses wireless data connections between network nodes. Wireless networking is a method by which homes, telecommunications networks and business installations avoid the costly process of introducing c ...

s and based on the idea that the source sends a message to the geographic location of the destination instead of using the

network address A network address is an identifier for a node or host on a telecommunications network. Network addresses are designed to be unique identifiers across the network, although some networks allow for local, private addresses, or locally administere ...

. In the area of

packet radio In digital radio, packet radio is the application of packet switching techniques to digital radio communications. Packet radio uses a packet switching protocol as opposed to circuit switching or message switching protocols to transmit digital dat ...

networks, the idea of using position information for routing was first proposed in the 1980s for interconnection networks. Geographic routing requires that each

node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines, ...

can determine its own location and that the source is aware of the location of the destination. With this information, a message can be routed to the destination without knowledge of the

network topology Network topology is the arrangement of the elements ( links, nodes, etc.) of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, including command and contro ...

or a prior route discovery.

Approaches

There are various approaches, such as single-path, multi-path and

flooding A flood is an overflow of water ( or rarely other fluids) that submerges land that is usually dry. In the sense of "flowing water", the word may also be applied to the inflow of the tide. Floods are an area of study of the discipline hydrolog ...

-based strategies (see for a survey). Most single-path strategies rely on two techniques: greedy forwarding and face routing. Greedy forwarding tries to bring the message closer to the destination in each step using only local information. Thus, each node forwards the message to the neighbor that is most suitable from a local point of view. The most suitable neighbor can be the one who minimizes the distance to the destination in each step (Greedy). Alternatively, one can consider another notion of progress, namely the projected distance on the source-destination-line (MFR, NFP), or the minimum angle between neighbor and destination (Compass Routing). Not all of these strategies are loop-free, i.e. a message can circulate among nodes in a certain constellation. It is known that the basic greedy strategy and MFR are loop free, while NFP and Compass Routing are not. Greedy forwarding can lead into a dead end, where there is no neighbor closer to the destination. Then, face routing helps to recover from that situation and find a path to another node, where greedy forwarding can be resumed. A recovery strategy such as face routing is necessary to assure that a message can be delivered to the destination. The combination of greedy forwarding and face routing was first proposed in 1999 under the name GFG (Greedy-Face-Greedy). It guarantees delivery in the so-called unit disk graph network model. Various variants, which were proposed later , also for non-unit disk graphs, are based on the principles of GFG . Face routing depends on a planar subgraph in general; however distributed planarization is difficult for real wireless sensor networks and does not scale well to 3D environments.

Greedy embedding

Although originally developed as a routing scheme that uses the physical positions of each node, geographic routing algorithms have also been applied to networks in which each node is associated with a point in a virtual space, unrelated to its physical position. The process of finding a set of virtual positions for the nodes of a network such that geographic routing using these positions is guaranteed to succeed is called

greedy embedding In distributed computing and geometric graph theory, greedy embedding is a process of assigning coordinates to the nodes of a telecommunications network in order to allow greedy geographic routing to be used to route messages within the network. Al ...

References

{{DEFAULTSORT:Geographic Routing Routing protocols Wireless networking Routing algorithms Geographic position

Approaches

Greedy embedding

See also

References