Eryk Schiller
PhD, July 2010
Monday 12 July 2010
In this thesis, we investigate new aspects of addressing and routing in Spontaneous Wireless Mesh Networks (WMN). Spontaneous wireless mesh networks promise a completely different architecture of the future Internet in comparison with its current state, but there are still many problems that have to be solved prior to the WMNs deployment. For example, routing in small static networks is easy. However, most real wireless networks are dynamic; links may go up and down, nodes join or leave the network and WMN size may grow, which implies the problem of large routing tables. New kinds of spontaneous networks amplify this trend, they include thousands of nodes acting as routers. Several experimentations reported on scaling problems of topological routing protocols such as AODV, DSDV, DSR or OLSR. Classical routing algorithms should be replaced with suitable technologies that guarantee good scalability and offer robust connectivity. We have considered geographical routing algorithms, because they do not require complete knowledge of the global network topology to compute routes and thus they are much more scalable then topological algorithms. There are, however, many problems we need to solve. The most important one is that geographical algorithms suffer from poor performance. They can compute much longer paths than topological routing algorithms. In order to solve this problem, we first studied the behavior of the greedy geographical forwarding, the basic building block of geographical algorithms. Then, we designed two new routing protocols: Binary Waypoint Routing and Scalable Waypoint Routing. Our protocols do not require any additional overhead to discover the network topology, but instead they passively analyze the traffic to learn efficient routes. We gather pure geographical information that helps to forward packets. Our method of packet forwarding follows the topological properties of the network and in consequence improve the performance of geographical routing algorithms.