Research Article
Assessing Standard and Inverted Skip Graphs Using Multi-Dimensional Range Queries and Mobile Nodes
@INPROCEEDINGS{10.1109/MOBIQ.2007.4450998, author={ Gregory J. Brault and Christopher J. Augeri and Barry E. Mullins and Christopher B. Mayer and Rusty O. Baldwin}, title={Assessing Standard and Inverted Skip Graphs Using Multi-Dimensional Range Queries and Mobile Nodes}, proceedings={4th International ICST Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services}, publisher={IEEE}, proceedings_a={MOBIQUITOUS}, year={2008}, month={2}, keywords={k-dimensional range query mobility skip graph}, doi={10.1109/MOBIQ.2007.4450998} }- Gregory J. Brault
Christopher J. Augeri
Barry E. Mullins
Christopher B. Mayer
Rusty O. Baldwin
Year: 2008
Assessing Standard and Inverted Skip Graphs Using Multi-Dimensional Range Queries and Mobile Nodes
MOBIQUITOUS
IEEE
DOI: 10.1109/MOBIQ.2007.4450998
Abstract
The skip graph, an application-layer data structure for routing and indexing, may be used in a sensor network to facilitate queries of the distributed k-dimensional data collected by the nodes, such as their geographic positions. Nodes in a standard skip graph sort keys in layered groups, where group membership is determined by random membership vectors. We propose a skip graph extension that inverts the key and membership vector roles, wherein group membership is based on deterministic z-ordering of k-dimensional data and sorting within groups is based on random keys. This extension retains the structure of a standard skip graph, and can be modified for use in 3D environments such as unmanned aerial vehicle swarms. Our results indicate this extension reduces the number of nodes contacted relative to the query precision, the volume of the multidimensional space, and the skip graph's height. We discuss our extension's performance relative to metrics at the application and network layers for static and mobile 2D networks.
