Wireless networks as a class presents challenges that traditional wired networks do not have to overcome. Often, new algorithms have to be devised to solve fundamental networking problems like security and routing because traditional algorithms fare poorly within the constraints of wireless networks.
A sub-class of wireless networks, ad hoc wireless networks are networks that do not depend on a fixed infrastructure for their operation. Wireless nodes in such networks communicate directly with each other, often relying on other wireless nodes to relay messages. Basic networking functions like security and routing must be performed by the wireless nodes themselves, in addition to data generation and consumption.
In this dissertation, we exploit the unique properties of ad hoc wireless networks, such as broadcast communication and relation between physical location and network topology, to formulate algorithms that solve three basic networking problems – Location Verification, Neighbor Discovery and Geometric Routing – in ad hoc wireless networks.
Our location verification algorithm allows a wireless node to verify the location claims of another
wireless node. The algorithm can withstand byzantine or malicious nodes trying to fake its location using a variety of means including directional antennae and collusion with other nodes. Moreover, it does so without using any special hardware or complex cryptographic algorithms. We further extend our algorithm to include various realistic scenarios and discuss how this algorithm can be
used to implement a complete system.
The neighbor discovery algorithms is designed to withstand the Sybil attack which is considered intractable. Our algorithm exploits the network topology and broadcast communication model and uses appropriate external devices, or Universe Detectors, to solve this problem. We explore
the bounds of finding a solution to this problem and prove that the external devices used, are the weakest possible devices that can be employed.
Finally, we present a geometric routing technique – VOID – that can improve on the performance of traditional geometric routing algorithms by expanding the scope of their applicability, whilst guaranteeing message delivery.