大規模無線センサNWにおける自律分散／自己組織的最短スパニング・ツリー構築手法および最適シンクノード位置決定手法

摘要

The primary challenging problems for the wireless sensor networks are how to construct the shortest spanning tree and how to determine the optimal sink node position. To solve these two problems, we propose a novel algorithm that uses the polygonal affine shortening algorithm with flow aggregation. This algorithm enables a wireless sensor network that has movable sensor nodes and one movable sink node to self-organize the shortest spanning tree and self-determine the optimal sink node position in a fully distributed manner. We also show that our algorithm is faster than the existing shortest path algorithm in terms of computational complexity.%情報収集を目的とする大規模無線センサNWにおける課題として，自律分散的かつ自己組織的な，（1）シンクノードへの最短スパニング・ツリー形成と，（2）任意のセンサから最短時間かつ低遅延差で情報を収集するためのシンクノードの最適位置決定がある．本稿では，Polygonal affine shorteningを用いた手法を提案し，センサおよびシンクノードが移動可能な場合について，その有効性を簡易モデルでのシミュレーションを用いて示す．さらに，既存の複数の経路制御アルゴリズムと比較し，提案方式が計算量の意味で十分小さいことを示す．提案手法が計算量の意味において，既存の経路制御手法に比べて十分小さく（O(N~(1/2) log N)））スケーラビリティが高いことを示す．