Geographic routing

From Wikipedia, the free encyclopedia

Geographic routing refers to a family of techniques to route data packets in a communication network. The main idea is that packets should be aware of their destination and messages will be routed hop-by-hop to nodes closer to the destination, until the message reaches its destination, which could be a point or a region in the case of geocasting. This implies that the hosts participating in the routing process should be aware of their geographic positions.

[edit] The Greedy algorithm and the Local Minima Problem

The most trivial idea is to use greedy routing, which consists of always passing a message which maximises the objective function. The objective function will typically be the remaining distance to the message's destination, however other metrics exist, such as the least deviation angle.

The main problem with the greedy approach is the fact that messages may get trapped in local minima nodes, which have no neighbours closer to the destination than themselves.