|
||||||
|
||||||
| Undergraduate Honours Projects | ||||||
|
Carleton University - School of Computer Science Undergraduate Honours Project Winter 2011 Empirical Study of Spanning Properties of Communication Graphs Induced by Directional Antennas Beibyt Azymbek 
ABSTRACT Let S be a set of points in the plane, whose unit disk graph is connected. This paper addresses the problem of finding orientations and a minimum radius for directional antennas of a fixed cone angle placed at the points of S, such that the induced communication graph G[S] is a hop t-spanner (meaning that G[S] is strongly connected, and contains a directed path with at most t edges between any pair of points within unit distance). We consider problem instances in which antenna angles are fixed at 120 and 90 degrees. We show that, in the case of angles, a radius of 5 suffices to establish a hop 5-spanner; in the case of angles, a radius of 7 suffices to establish a hop 6-spanner; and for any angle strictly less than , a radius of 2 is necessary to establish strong connectivity. Furthermore, this paper gives an empirical study of above research, through simulation of the discussed algorithm. |
||||||
|
