著者

斉藤裕樹 中村 陽一 戸辺 義人

出版者

情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.52, no.2, pp.334-346, 2011-02-15

---

センサネットワーク技術の発展,GNSS(Global Navigation Satellite System)機能を備えた小型デバイスの普及により,位置情報サービス(Location-based Service,LBS)の利用分野が拡大している.LBSでは実世界の膨大な情報を扱うため,分散環境上に実現される必要があるとともに,位置依存情報を管理するための枠組みが必要となる.本論文では,位置依存情報に適したオーバレイネットワークの構成手法GeoSkipを提案する.GeoSkipは,2次元の平面上のピア間を角度分割と隣接ピアへのリンクを行うことにより論理ネットワークを構成する.さらに,Skip Graphを2次元に拡張した階層構造を与えることにより,各ピアはより遠方のピアへのリンクを持つことができる.これらにより,2次元の情報を効率的に検索することができる特徴を有する.また,シミュレーションによる評価を行い,経路表の大きさと検索コストがO(log N)に抑えられることを確認した.Mobile devices equipped with Global Navigation Satellite System (GNSS) functionality and the advance of technology for sensor networks have enabled Location-Based Services (LBS). The location-based services deal with real-world information which is collected from mobile devices and sensors. Due to the large amount of collected data, we should manage such data in distributed architectures. This paper proposes a scalable overlay network architecture, called GeoSkip. GeoSkip extends one-dimensional Skip Graphs to two-dimensional content space in order to achieve efficient data processing for location-based contents. As a result, we are able to reduce cost to search for two-dimensional information to O(log N). The benefit of GeoSkip is validated by simulations.