M.Sc Thesis

M.Sc StudentShotland Ari
SubjectEfficient Route Discovery in Hybrid Networks
DepartmentDepartment of Computer Science
Supervisor PROF. Roy Friedman
Full Thesis textFull thesis text - English Version


Hybrid networks are formed by a combination of access points and mobile nodes such  that the mobile nodes can communicate both through the access points and using ad-hoc networking among themselves. This work deals with providing ecient routing between mobile devices in hybrid networks. Specifically, we assume the existence of a spanning  tree from each access point to all mobile devices within the transitive transmission range of the access point. We utilize this spanning tree to design a family of ecient point-to-  point routing protocols for communication between the mobile devices themselves. The protocols utilize the tree structure and have the following appealing properties:

1. The amount of eort to find a path between two nodes depends on its popularity.

2. The length of the routing path between any two nodes p and q monotonically

improves with its utilization. It is always between the length of the path that includes the common ancestor of both p and q in the tree and the shortest path from p to q in the real network. If the path is used often enough, it will eventually  converge to the shortest path (or very close to it).

3. The protocol avoids flooding the entire network.

In addition to introducing these intermediate protocols, our work also includes a detailed simulation study of several representative communication patterns, which compares our  approaches to DSR.