Heuristic optimalization of geographic routing

OData support
Dr. Gulyás András
Department of Telecommunications and Media Informatics

The idea of using geographic routing in radio networks appeared in the 80’s. Nowadays geographic routing is widely used in ad-hoc and sensor networks. However, geographic routing can be used in other types of networks. Researches show that geographic routing is efficient in social networks, and it can also be used on a metric Internet topology.

Greedy forwarding is the basic forwarding method of geographic routing. It is based on a simple idea: we can try to reach a generally good path of the network by making locally optimal decisions. Simplicity is not the only positive feature of greedy forwarding. Greedy forwarding works in a completely distributed fashion, which is a requirement in large networks. No information is needed about the whole network, and there is no need to predefine the path. Instead, it is built up step by step, based on local decisions.

Although it is an effective concept, greedy forwarding has some problems to be solved. Namely, its largest problem is its computational complexity. This complexity comes from making locally optimal decisions. To make an optimal decision, every node has to examine all of its neighbors, which is expensive to do if the point has many neighbors. In this paper I show that by giving up finding the optimal decision, and making a locally good (but perhaps not the best) decision with heuristics, we can find a solution almost as good as greedy forwarding with much less computation. And less computation means faster forwarding.


Please sign in to download the files of this thesis.