著者

北條 真史 長尾 洋也 宮尾 武裕 首藤 一幸

出版者

一般社団法人情報処理学会

雑誌

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

巻号頁・発行日

vol.56, no.2, pp.439-447, 2015-02-15

---

センサが構成する無線メッシュネットワークなどにおいてメッセージ配送やデータ収集を行うためには,ノード群でオーバレイネットワークを構築することが有望である.地理的な近接性を考慮したルーティングや範囲問合せを行うためには,ノード位置に基づいたオーバレイネットワークの構築が必要となる.ノード位置をIDとして用いる場合,ルーティングの方式には,ノード位置すなわちIDに偏りがあっても経路長を短く抑えることが求められる.我々は,この要件を満たし,かつ,構造化オーバレイの設計手法である柔軟な経路表(FRT)の特長を備える構造化オーバレイを提案する.柔軟な経路表の特長とは,経路表サイズの動的な設定や高い拡張性を指す.提案手法は,既存手法の1つであるP2Pドロネーネットワークをトポロジとして採用し,ホップ数の推定に基づいて遠隔ノードとのショートカットリンクを形成することによって経路長を短く抑える.It is a promising way to construct an overlay network with sensor nodes for wireless mesh networks to perform message delivery and data collection from the nodes. It is necessary for an overlay to reflect nodes' locations to perform geometric routing and geometric search, for example node IDs on the overlay are nodes' location. Furthermore, a route on the overlay should be small, in other words, involve small number of hops even if the distribution of node locations and IDs are biased. A structured overlay presented in this paper fulfills the requirements and provides features of Flexible Routing Tables (FRT), a method for designing routing algorithms for structured overlays. Features of FRT are the dynamic routing table size and high extensibility. The proposed overlay adopts P2P Delaunay Network as its topology, and the method keeps route length short by forming shortcut links to distant nodes based on the estimated number of hops.