非常時における無線中継車配置のロバスト最適化

52
非常時における無線中継車配置のロバスト最適化
Robust Optimization of Emergency Locating Radio Relays
技 術 本 部
射 場 博 之＊1
高
名古屋誘導推進システム製作所
熊 野 信 太 郎＊2
勲＊3
見
綾 田 正 徳＊4
近年，情報通信技術の発達が著しいが，大規模災害時などの非常時には通信インフラの故障等も考えられ，このよう
な状況にも耐え得る強固な通信基盤の確立が必要不可欠である．本報では中継車を用いた無線通信を採り上げ，ある中
継車が故障等で使用不能になった場合でも通信経路が確保される中継車配置を算出する手法を紹介する．本問題は，最
も多くの通信経路を担当する中継車が使用不能になった場合の通信経路数が最大になるように，中継車配置を行う問題
として定式化される．高速アルゴリズムを開発することで計算時間を大幅に短縮し，実用的な時間内での最適化計算を
可能とした．
In emergent cases such as natural disasters, solid bases for communication are essential. We discuss radio
communication with relays and introduce a method for calculating the optimal location of relays, with which
communication paths are held even if any one unit is nonoperational. This can be formulated into a maximizing problem to
communication power such as the number of redundant paths or communication accuracy, when the most critical unit is
damaged. We developed a fast algorithm for formulation able to solve problems in practical time.
であり，非常時には有効な通信手段となり得る．このときの
1. は じ め に
中継車の配置は，地形による電波伝播の状況，地理条件によ
1995 年に発生した阪神・淡路大震災は，広域の都市災害
る中継車配置の容易性，分散しているすべての現場との通信
として社会に大きな打撃を与えた．行政やマスコミは震災発
可能性等を考慮して決定しなくてはならない．また同時に，
生直後，緊急の情報収集手段の確保に追われたが，このよう
どの中継車が使用不可能となっても通信経路が途絶しないロ
な大規模災害時においては災害への対策や社会への正確な情
バスト性が併せて求められる（図１）．人がこれらの条件を
報伝達といった観点から，迅速かつ正確な通信手段の確保が
すべて考慮して中継車配置を決定することは非常に困難であ
必要となる．大規模災害など非常時の情報収集においては，
るため，コンピュータを用いて短時間で最適配置を算出する
二次災害等によって通信障害，あるいは装置そのものの故障
技術の確立が必要である．
が発生することも考えられるため，このような事態を想定し
た，強固で確実な通信基盤を確立することが重要である．
非常時の基本的な通信方法として，災害等の現地と対策本
部の間を複数の中継車で結ぶ無線通信方式がある．これは通
信インフラの整備されていない発展途上国などでも運用可能
本報ではこの問題を非線型の離散型最適化問題として定式
化し，その計算例及び応用例を紹介する．
2. 中継車配置の課題
本問題では対策本部と複数の現場の間に中継車を複数配置
道路状況などのアクセス性
A
B
通信経路網の
ロバスト性
地形による電波到達性
距離による電波到達性
図１ 中継車配置の決定 中継車配置の際に考慮すべき項目を示す．
Decision on the location of relay vehicles
＊1
＊2
高砂研究所制御システム研究室
高砂研究所電子技術研究室
＊3
＊4
名古屋研究所所長室主幹 工博
誘導･電子機器技術部電子システム設計課
三菱重工技報 Vol. 39 No. 1（2002_1）
53
B
3
2
表１ 評価値の計算
B
An example of estimation
3
2
担当経路数
4
4
1
A
1
(b)
中継車１
３
２
中継車２
１
１
中継車３
１
１
中継車４
A
（a）ロバストでない経路
(a)
（b）ロバストな経路
１
１
最重要中継車
中継車１
中継車１
通信網全体の経路数
３
３
最重要中継車を用いない
場合の経路数
０
１
図２ 通信経路のロバスト性 ロバストな通信経路の例を示す．
Robustness of communication network
と定義する．
前章における課題（2）のロバスト性を考えない場合，評価
し，多段の中継により対策本部と現地で情報伝達を行う状況
関数 F
（X）の最大化を行うことで，課題（1），
（3）及び（4）を満
を扱う．本問題で考慮すべき課題として，次の４点が挙げら
たす中継車配置を求めることができる．これは，関数 G
（X）
れる．
の最大化を考えることで伝送品質の高い経路を多く含む配置
（1）対策本部とすべての現場との間で通信が可能であること．
が得られるためである．この際，対策本部と通信できない現
（2）通信経路網のロバスト性が確保されていること．
場が存在するような中継車配置は G
（X）の定義より評価値が
（3）各経路について十分な伝送品質が得られること．
０となり，選択されない．また，関数 H
（X）の最大化を考え
（4）中継車配置の容易性を考慮した適切な配置場所を選定す
ることにより中継車の配置容易性を考慮することになる．
ること．
（2）のロバスト性とは任意の中継車が使用不能となっても
代替の通信経路が確保されていることである．図２
（a）の例
これらに加えて課題
（2）
のロバスト性を反映するためには，
更に次の考え方を採用する．
中継車配置 X を決定すると，各中継車が担当する経路の伝
では，中継車１が使用不能となると AB 間の通信は途絶する．
送品質の総和を計算することができる．この値が最も大きい
一方（b）の例はどの中継車が使用不能となっても通信が可能
ものは，品質の高い経路を多数担当しているために，最も重
なロバストな経路となっている．以下では任意の１台の中継
要な中継車であると考えることができる．すべての中継車の
車が使用不能となった場合のロバスト性について扱うものと
中で，使用不能になったときに最も被害が大きくなるのは最
するが，２台以上の故障・破壊に対するロバスト性について
重要中継車であるため，中継車配置 X から最重要中継車を除
も同様の手法を応用することができる．
（3）
の伝送品質とは正
いたものを配置 X’
と表すものとし，これに対して評価値 （
F X’
）
常に通信される確率であり，中継車間の距離や地理条件から
の最大化
決まるものである．
なお，非常時には中継車は少ないほうが良いので，１台の
中継車が複数の通信経路を担当することも可能であるものと
する．
3. 中継車配置最適化問題の定式化
Maximize F
（X’
）
を考える．
配置 X から最重要中継車を除外することは，“最悪の事態”
を想定することである．最悪の事態を想定した上で評価関数
を最大化することは，残された機器を最大限有効に利用する
ことであり，最悪の事態での被害を最小化するものである．
3. 1 評価関数の定義
これにより，中継車の故障等に対してよりロバスト性の高い
前章の課題を踏まえ，
本問題の定式化を以下のように行う．
通信経路網を算出することが可能となる．図２の例で，全経
中継車の配置候補地は事前に選ばれているものとし，運用
路の伝送品質が１であり，各地点の配置容易性を考慮しない
時にはこの中から中継車の台数分の候補地に，実際に中継車
（β＝０）と仮定する．このとき（a），
（ b）のどちらのケース
を展開するものとする．中継車の展開状況を表すベクトル変
でも中継車１が最重要中継車となり，これ以外の中継車によ
数 X に対し，評価関数 F
（X）
を次のように定義する．
る評価値は（a）の場合が０，
（ b）の場合が１となる（表１）．
まず関数 G（X）を全通信経路の伝送品質の和と定義する．
ただし対策本部と通信ができない現場が存在する場合は，G
（X）は０をとるものとする．次に中継車配置候補地ごとに配
したがって上記の手法によって，ロバストな経路（b）がより
高い評価値を得ることが確認される．
3. 2 最適化計算手法
置容易性を表す数値を設定する．この数値は配置が容易であ
この定式化では，最重要中継車の選ばれ方が非線型である
るほど高い値をとるものとし，地理条件などによって定まる
ことと，配置位置の決定が離散的であることから，非線型の
ものとする．関数 H
（X）を実際の配置位置における配置容易
離散型最適化問題と分類される．この種の問題に対する効率
性の総和とし，適当な重み係数α，βを用いて，
的な汎用解法は存在せず，遺伝的アルゴリズム（GA）やシ
F
（X）
＝α G
（X）
＋β H
（X）
ミュレーティド・アニーリング（SA）等の反復解法を用い
三菱重工技報 Vol. 39 No. 1（2002_1）
特
集
54
現場１
現場２
現場３
現場１
中継車
現場２
現場３
中継車
最重要中継車
最重要中継車
現場４
現場４
対策本部
対策本部
図３ 最適化計算例 計算例に対する最適化計算結果を示
図４ 計算結果のロバスト性 計算例において，最重要中
す．
The result of optimization for the test problem
継車が使用不能となった場合の代替経路の例を示す．
The robustness of the example case
て解くことになる．これらの解法では，反復のたびに X を更
中継車
新して評価値を再計算する必要があり，問題規模が大きい場
合には計算アルゴリズムの高速化が要求される．
今回，評価値計算の高速性を図るためにこのアルゴリズム
にネットワーク理論における接続行列の概念を応用した．こ
観測車
れは各中継車間の通信可能性を行列で表し，また対策本部及
び各現場と中継車間の通信可能性をベクトルで表した上で，
これらの行列とベクトルの演算を行って通信経路数を計算す
るものである．これにより評価値計算を大幅に効率化するこ
中継車
対策本部
観測車
とができ，単純な数え上げ手法では１時間以上かかる規模の
問題を通常の PC で数分程度の計算時間で解くことができ
た．
4. 計 算 例
前章の定式化に基づく計算例を紹介する．正方形領域に１
ヶ所の対策本部と４ヶ所の現場がある場合の，中継車 10 台
中継車
図５ 応用例 中継車配置最適化技術の災害時無線中継システムへの
応用例を示す．
An example of application
を用いたロバストな最適配置を図３に示す．図中，点線は機
器間で通信可能であることを示す．また，通信経路の一例を
実線で示す．この場合の最重要中継車は四角で囲まれた中継
このような緊急時の運用では対策の有効性を高めるために
車である．図４に示すとおり，最重要中継車が使えなくなっ
も，本報で紹介したような高速な最適化手法が要求される．
た場合でも対策本部と各現場の通信経路が確保されており，
通信経路網のロバスト性が実現されていることが分かる．
5. 応 用 例
6. お わ り に
本手法によって，通信可能性や伝送品質などの中継車配置
に関わる種々の課題を考慮しつつ，通信経路のロバスト性を
今回開発した最適化手法の応用例としては，地震等の大規
実現することが可能となった．これにより，非常時であって
模災害時の無線情報収集システムなどが挙げられる（図５）．
も信頼性の高い通信網を構築する一つの方法が確立された．
災害時の情報収集手段として観測車両を災害現場に派遣し，
さらに最適化計算の高速化を達成したことにより，非常時に
中継車を用いて対策本部との通信を行う場合には，二次災害
おける迅速な意志決定も可能となる．
等に備えたロバストな通信経路網を確立することで，確実な
情報収集が可能となる．
今後は本技術を応用し，より信頼度の高い無線中継システ
ムの開発などに展開する．
三菱重工技報 Vol. 39 No. 1（2002_1）