4th International ICST Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services

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
Gregory J. Brault1,*, Christopher J. Augeri2,*, Barry E. Mullins2,*, Christopher B. Mayer2,*, Rusty O. Baldwin2,*
  • 1: Air Force Information Operations Center, Lackland AFB, TX USA
  • 2: Air Force Institute of Technology, Wright-Patterson AFB, OH USA
*Contact email: gregory.brault@lackland.af.mil, christopher.augeri@afit.edu, barry.mullins@afit.edu, christopher.mayer@afit.edu, rusty.baldwin@afit.edu

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.