A Proximity Aware Extension of Skip Graph for World Wide Range Queries

摘要

The rapid development of crowd sensing and cloud computing makes it possible to build world wide Cyber Physical Systems (CPS). Range queriable P2P overlay technologies are considered as promising candidate for realizing some important functionalities of CPS, for example, retrieval based on the properties of sensors. It is difficult to build world wide systems with existing range queriable P2Ps efficiently as they cannot integrate physical Internet proximity in routing as DHTs can. In this report, we propose the hierarchical neighbor selection (HNS) mechanism for range queriable P2P overlays, which can integrate the hierarchy of physical Internet into overlay construction and routing to improve the performance. We also implement HNS based on Skip Graph, an efficient range queriable P2P technology. With extensive simulations, we show that HNS based Skip Graph (HSG) can improve the routing latency and locality significantly with little overhead.