マルチホップ型移動通信網の中継局配置問題

概要

論文の詳細を見る
マルチホップ方式において移動局は中継機能を持ち基地局から電波が届かないエリアに存在する移動局と基地局, または移動局と移動局との通信をおこなう. (以後基地局, 移動局は区別せずにノードと呼ぶ.)それは基地局が十分に設置されていない地域, 災害時に基地局が崩壊してしまったような地域に通信手段として使われる. このような通信網においてネットワーク構造が非連結になると, あるノード間の通信が不可能となる. この場合, ネットワーク上に適当に中継局(以後リピータと呼ぶ)を配置しネットワーク構造を連結にしなければならない. 本報告書では, このような問題を扱う. R^2は2次元ユークリッド平面をあらわす. ノードnとはR^2上の点で, ノードの集合はNと表す. またリピータsはR^2上の点で, リピータの集合はSと書く. 2つのノード間の最大通信可能距離をγとする. 2つのノードn_1, n_2が通信可能(連結)であるというのは, n_1からn_2までのN∪S上のある点列{p_1(=n_1),...,p_k(=n_2)}が存在し, すべての1<__-i<,kに対し, d(pi,p^<i+i+1)<__-rであることである. だだしd(p^i,p^<i+1>)はp^i,p^<i+1>間のユークリッド距離とする. このときリピータ配置問題は以下のように定義される. 入力:ノード集合N, 最大通信可能距離r. 問:すべてのノード間が通信可能になるような最小のリピータ集合は? マルチホップ型通信ネットワークにおいてはチャネルのスケジューリング問題が主であり, このような問題は著者等が知る限りでは議論されていない. 一方この問題が解けるならば最小のリピータで通信網を連結にできるので, これは重要な問題といえる. まずは単純な貧欲算法を用いて連結にし, さらにリピークを移動し余分なものを減らす2段階のアルゴリズムを提案する.
社団法人電子情報通信学会の論文
1997-03-06

マルチホップ型移動通信網の中継局配置問題

スポンサーリンク

概要

著者

関連論文

スポンサーリンク