W-Grid: a Cross-Layer Infrastructure for Multi-Dimensional Indexing, Querying and Routing in Ad-Hoc and Sensor Networks

Large scale wireless ad-hoc networks of computers, sensors, PDAs etc. (i.e. nodes) are revolutionizing connectivity and leading to a paradigm shift from centralized systems to highly distributed and dynamic environments. A plethora of routing algorithms have been proposed for the network path discovery ranging from broadcasting/flooding-based approaches to those using global positioning systems (GPS). In this paper we propose a novel decentralized infrastructure that self-organizes wireless devices in an ad-hoc network, where each node has one or more virtual coordinates through which both message routing and data management occur without reliance on either flooding/broadcasting operations or GPS. The resulting ad-hoc network does not suffer from the dead-end problem, which happens in geographic-based routing when a node is unable to locate a neighbor closer to the destination than itself. The multi-dimensional data management capability will be described showing, as an example, how the location service reduces to a simple query, like for any other data type. Extensive performance analysis and experiments have been conducted and the results compared to GPSR, which is considered the most efficient routing solution not using broadcast operations. Our approach shows significant performance gains.