Geometric routing over virtual coordinate systems: algorithms, protocols and applications

Advancements in hardware development have given rise to a novel paradigm of computing called ubiquitous computing. In ubiquitous computing, applications provide various services across heterogeneous hardware platforms, over standard protocols. These hardware can range from mobile devices to small devices with wireless communication capabilities, which can be embedded into appliances utilized in daily life. Wireless ad-hoc networks is an important ingredient in the deployment of ubiquitous computing applications. It acts as the communication backbone, which enables the flexible deployment of devices required by most of the ubiquitous applications. In general, wireless ad-hoc networks do not have a pre-defined topology, hence form a mesh network over wireless communication medium. Routing in wireless ad-hoc networks is a challenging task compared to fixed infrastructure networks. It has to deal with the dynamics of the network topology, due to the unpredictable wireless communication behavior. Geographic routing is a routing paradigm, especially proposed for wireless ad-hoc networks. In geometric routing, routing decisions are made based on the geometric position of the nodes. Initially geometric routing tries to forward a packet to the closest node towards the destination, namely greedy routing. If greedy routing fails, it explores the graph systematically to reach the destination, namely face routing. As routing is based on the geometric coordinates of the nodes, it avoids building and maintaining the routing tables as in classical routing protocols. Hence, it provides scalability and robustness in networks with dynamic topologies. Despite the ingenuity of seminal proposal in geometric routing, it has not thrive to become a standard for wireless ad-hoc networks. This is mainly due to the unrealistic assumptions of the algorithms. Also as geometric routing requires the nodes to be equipped with geometric coordinates, an auxiliary location service has to be in place. Such a service can be expensive and unrealistic in most of the wireless ad-hoc network deployments. In this thesis, geometric routing is investigated on virtual coordinate systems. In the first contribution of the thesis, an efficient coordinate system called virtual raw anchor coordinates (VRAC) has been investigated and geometric routing algorithms are formulated on it. Further more, it establishes results on the possibility of greedy routing with delivery guarantees on VRAC. Second contribution of the thesis is the proposal of greedy zone routing protocol considering the reliability and scalability aspects of large scale wireless ad-hoc networks. Greedy zone routing protocol design not only free of unrealistic assumptions but also based on simple techniques which can be applied in real network settings. In the third contribution, an application layer framework is presented over existing routing protocols for wireless ad-hoc networks. This framework is then applied to solve a smart building use case