Connectivity of wireless sensor networks using directional antennae

In this thesis, we study fundamental issues on sensor networks employing directional antennae. The main question that motivates this work is how omnidirectional antennae can be replaced with directional antennae in such a way that the connectivity is maintained while the angle and range are minimum. This leads to the natural problem of finding the minimum radius to achieve connectivity for a given angle when each sensor has k ≥ 1 directional antennae. We prove that for any given angle a strongly connected network can be created with radius bounded by 2 · sin ( pk+1 ) times the optimal radius when k ≤ 5. We also prove a lower bound when 2 antennae are being used per sensor. A slightly different problem is to replace omnidirectional antennae of a given network with the minimum number of directional antennae while the minimum path between any two points in the resulting network (hop-stretch factor) increases independently of the size of the network. We give upper bounds on the number of directional antennae and hop-stretch factor for this problem provided we have an underlying two-edge connected geometric planar graph. This leads to the problem of constructing 2-edge connected geometric planar graphs with bounded edge length. Two approaches can be considered: i) Augmenting the connectivity of a given planar graph by adding new edges of bounded length. Using this approach, we give an upper bound on the number of new edges of bounded length to augment the connectivity of a given geometric planar graph into a 2-edge connected planar graph. We prove that determining the minimum number of new edges of bounded length to augment the connectivity is intractable. ii) Obtaining a 2-edge connected planar subgraph of a given Unit Disk Graph (UDG). We prove that deciding whether a UDG has a planar subgraph of degree two is intractable even for a scaling factor of 52 . On the opposite side, we prove that the square of any 2-edge connected UDG always has an underlying 2-edge connected geometric planar subgraph.