(57)【特許請求の範囲】
【請求項１】
第１通信局と第２通信局との間の無線通信を中継するための複数の中継局を最適に配置するための通信経路の最適化方法であって、
（ａ）  前記複数の中継局が配置されたときの前記第１通信局と前記第２通信局との間の伝送品質および通信経路数の少なくともいずれか一方を評価値として設定するステップと、
（ｂ）  前記設定された評価値を算出するステップと、
（ｃ）  前記算出された評価値に基づいて、前記複数の中継局の配置を最適化するステップと
を備え、
前記（ｂ）において、前記設定された評価値を算出する際には、前記複数の中継局のうちの最も重要なＮ（Ｎは１以上の整数）台の中継局を求め、前記最も重要なＮ台の中継局を通過しない通信経路についてのみの前記設定された評価値を算出する
通信経路の最適化方法。
【請求項２】
請求項１記載の通信経路の最適化方法において、
前記（ｂ）は、前記複数の中継局のそれぞれが使用される通信経路数を計算することを含み、前記通信経路数の計算は、前記複数の中継局、前記第１通信局および前記第２通信局間の通信可能性を表す行列を用いて行われる
通信経路の最適化方法。
【請求項３】
請求項１記載の通信経路の最適化方法において、
前記（ｂ）は、前記複数の中継局、前記第１通信局および前記第２通信局間の伝送品質を表す行列を用いて、前記第１通信局と前記第２通信局との間の伝送品質を計算することを含む
通信経路の最適化方法。
【請求項４】
請求項１から３のいずれか１項に記載の通信経路の最適化方法において、
前記（ｃ）における前記複数の中継局の配置の最適化は、発見的手法により行う
通信経路の最適化方法。
【請求項５】
請求項４記載の通信経路の最適化方法において、
前記発見的手法は、シミュレーティド・アニーリングである
通信経路の最適化方法。
【請求項６】
第１通信局と第２通信局との間の無線通信を中継するための複数の中継局を最適に配置するための通信経路の最適化方法であって、
（ｄ）  前記複数の中継局の配置に関する方針Ｘを生成するステップと、
（ｅ）  前記方針Ｘの前記複数の中継局のうち最重要中継局Ｊ（Ｘ）を求めるステップと、
（ｆ）  前記方針Ｘから前記最重要中継局Ｊ（Ｘ）を除いた場合の評価値Ｇ（Ｘ−Ｊ（Ｘ））を求めるステップと、
（ｇ）  前記評価値Ｇ（Ｘ−Ｊ（Ｘ））が最大となるＸ＝Ｘｏｐｔを求めるステップと、
（ｈ）  前記方針Ｘｏｐｔを出力するステップと
を備えた通信経路の最適化方法。
【請求項７】
第１通信局と第２通信局との間の無線通信を中継するための複数の中継局のそれぞれへの周波数割り当てを最適に行うための周波数割り当て決定方法であって、
（ｉ）  前記複数の中継局のそれぞれへの周波数割り当てに関する方針Ｘを生成するステップと、
（ｊ）  前記方針Ｘの前記複数の中継局のうち最重要中継局Ｊ（Ｘ）を求めるステップと、
（ｋ）  前記方針Ｘから前記最重要中継局Ｊ（Ｘ）を除いた場合の評価値Ｇ（Ｘ−Ｊ（Ｘ））を求めるステップと、
（ｌ）  前記評価値Ｇ（Ｘ−Ｊ（Ｘ））が最大となるＸ＝Ｘｏｐｔを求めるステップと、
（ｍ）  前記方針Ｘｏｐｔを出力するステップと
を備えた周波数割り当て決定方法。
【請求項８】
第１通信局と第２通信局との間の無線通信を中継するための複数の中継局を最適に配置するとともに前記複数の中継局のそれぞれへの周波数割り当てを最適に行うための通信経路の最適化方法であって、
（ｎ）  前記複数の中継局の配置と周波数割り当てに関する方針Ｘを生成するステップと、
（ｏ）  前記方針Ｘの前記複数の中継局のうち最重要中継局Ｊ（Ｘ）を求めるステップと、
（ｐ）  前記方針Ｘから前記最重要中継局Ｊ（Ｘ）を除いた場合の評価値Ｇ（Ｘ−Ｊ（Ｘ））を求めるステップと、
（ｑ）  前記評価値Ｇ（Ｘ−Ｊ（Ｘ））が最大となるＸ＝Ｘｏｐｔを求めるステップと、
（ｒ）  前記方針Ｘｏｐｔを出力するステップと
を備えた通信経路の最適化方法。
【請求項９】
請求項６または８に記載の通信経路の最適化方法において、
更に、
（ｓ）  前記方針Ｘｏｐｔに従って、前記複数の中継局を配置するステップと
を備えた通信経路の最適化方法。
【請求項１０】
請求項６、８及び９のいずれか１項に記載の通信経路の最適化方法において、
更に、
（ｔ）  前記方針Ｘを採用したときの前記複数の中継局の配置の容易性を示すＵ（Ｘ）を求めるステップと、
（ｕ）  前記評価値Ｇ（Ｘ−Ｊ（Ｘ））と前記Ｕ（Ｘ）の和を前記方針Ｘの評価値Ｆ（Ｘ）とするステップと、
（ｖ）  前記Ｆ（Ｘ）が最大となるＸ＝Ｘｏｐｔを求めるステップと
を備え、
前記（ｇ）、（ｑ）に代えて、前記（ｔ）、（ｕ）および（ｖ）を実行する
通信経路の最適化方法。
【請求項１１】
請求項６、及び８から１０のいずれか１項に記載の通信経路の最適化方法において、
更に、
（ａａ）  前記中継局をｈ台経由して、前記第１通信局と前記第２通信局を結ぶ経路の伝送品質の総和を示す第１の値を求めるステップと、
（ａｂ）  前記第１通信局から特定の前記中継局が経路として前記ｈ台目となるような経路全体での前記第１通信局から前記特定の前記中継局までの伝送品質を示す第２の値を求めるステップと、
（ａｃ）  前記第２通信局から前記特定の前記中継局が経路として前記ｈ台目となるような経路全体での前記第２通信局から前記特定の前記中継局までの伝送品質を示す第３の値を求めるステップと、
（ａｄ）  前記第２の値と前記第３の値に基づいて、前記特定の前記中継局を経由して前記第２通信局から前記第１通信局へ至る全ての経路での伝送品質の和を示す第４の値を求めるステップと、
（ａｅ）  前記第１の値に基づいて、前記第１通信局と前記第２通信局を結ぶ通信経路の伝送品質の総和を示す第５の値を求めるステップと
を備え、
前記最重要中継局Ｊ（Ｘ）は、前記第４の値および前記第５の値に基づいて求められる
通信経路の最適化方法。
【請求項１２】
第１通信局と第２通信局との間の無線通信を中継するための複数の中継局が最適に配置された通信経路の生成装置であって、
前記複数の中継局が配置されたときの前記第１通信局と前記第２通信局との間の伝送品質および通信経路数の少なくともいずれか一方を評価値として設定する評価値設定部と、
前記設定された評価値を算出する評価値算出部と、
前記算出された評価値に基づいて、前記複数の中継局の配置を最適化する最適化部と
を備え、
前記評価値算出部が前記設定された評価値を算出する際には、前記複数の中継局のうちの最も重要なＮ（Ｎは１以上の整数）台の中継局を求め、前記最も重要なＮ台の中継局を通過しない通信経路についてのみの前記設定された評価値を算出する
通信経路の生成装置。
【請求項１３】
請求項１から６、及び８から１１のいずれか１項に記載の通信経路の最適化方法の各ステップをコンピュータに実行させるための通信経路の最適化プログラム。
【請求項１４】
請求項７に記載の周波数割り当て決定方法において、
更に、
（ｔ）  前記方針Ｘを採用したときの前記複数の中継局の配置の容易性を示すＵ（Ｘ）を求めるステップと、
（ｕ）  前記評価値Ｇ（Ｘ−Ｊ（Ｘ））と前記Ｕ（Ｘ）の和を前記方針Ｘの評価値Ｆ（Ｘ）とするステップと、
（ｖ）  前記Ｆ（Ｘ）が最大となるＸ＝Ｘｏｐｔを求めるステップと
を備え、
前記（ｌ）に代えて、前記（ｔ）、（ｕ）および（ｖ）を実行する
周波数割り当て決定方法。
【請求項１５】
請求項１４に記載の周波数割り当て決定方法において、
更に、
（ａａ）  前記中継局をｈ台経由して、前記第１通信局と前記第２通信局を結ぶ経路の伝送品質の総和を示す第１の値を求めるステップと、
（ａｂ）  前記第１通信局から特定の前記中継局が経路として前記ｈ台目となるような経路全体での前記第１通信局から前記特定の前記中継局までの伝送品質を示す第２の値を求めるステップと、
（ａｃ）  前記第２通信局から前記特定の前記中継局が経路として前記ｈ台目となるような経路全体での前記第２通信局から前記特定の前記中継局までの伝送品質を示す第３の値を求めるステップと、
（ａｄ）  前記第２の値と前記第３の値に基づいて、前記特定の前記中継局を経由して前記第２通信局から前記第１通信局へ至る全ての経路での伝送品質の和を示す第４の値を求めるステップと、
（ａｅ）  前記第１の値に基づいて、前記第１通信局と前記第２通信局を結ぶ通信経路の伝送品質の総和を示す第５の値を求めるステップと
を備え、
前記最重要中継局Ｊ（Ｘ）は、前記第４の値および前記第５の値に基づいて求められる
通信経路の最適化方法。
【請求項１６】
請求項７、１４、及び１５のいずれか１項に記載の周波数割り当て決定方法の各ステップをコンピュータに実行させるための周波数割り当て決定プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信経路の最適化方法、通信経路の生成装置、および通信経路の最適化プログラムに関し、特に、災害無線中継車配置のためのロバスト最適化（Ｒｏｂｕｓｔ  Ｏｐｔｉｍｉｚａｔｉｏｎ  ｏｆ  Ｌｏｃａｔｉｎｇ  Ｍｏｂｉｌｅ  Ｒｅｌａｙ  Ｓｔａｔｉｏｎｓ  ｆｏｒ  Ｒａｄｉｏ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ）を実現可能な通信経路の最適化方法、通信経路の生成装置、および通信経路の最適化プログラムに関する。
【０００２】
【従来の技術】
１９９５年に発生した阪神大震災は、広域の都市災害として社会に大きな打撃を与えた。マルチメディア時代の入り口で遭遇したこの大災害では、多種多様で膨大な量の情報が発生し、その伝達において通常の電話に加え、携帯電話、ファックス、防災行政無線、アマチュア無線、衛星通信、さらにはインターネットやパソコン通信等の様々なメディアが活用された。
【０００３】
災害時に発生する多種多様の情報を処理するメディアの中で、行政が災害の状況を早期かつ正確に把握するための通信手段の確保は、災害への対策や社会への正確な情報伝達という観点で重要である。国や自治体では、こうした重要性を踏まえて、防災無線システムの高度化（郵政省）や防災用移動端末の開発（三重県）等に取り組んでいる。災害発生時の情報伝達においては、輻輳等による通信障害及び装置そのものの破壊や故障を想定して２重３重の通信系列を持つことが必要とされる。
【０００４】
災害発生時の基本的な通信方法として、災害現地に派遣した観測車と対策本部の間を複数の中継車で結び、防災無線帯域の周波数帯を活用した無線通信方式がある。これは通信インフラの発達した都市型災害でも、インフラの整備されていない地方や発展途上国での災害でも同様に活用可能であり、災害影響範囲の広域化にも対応可能な方法である。
【０００５】
観測車と対策本部との間を結ぶ中継車の配車は、地形による電波伝播の条件、地勢や幹線道路状態による配車の容易性、複数観測車の分散状態へ対応可能性等を考慮して決定しなくてはならない。また、特定の観測車との通信を行う際、送受信信号の混信や、情報が本来の経路以外で伝わることによる混信をさけるため、各中継車の送受信周波数を決定する必要がある。
【０００６】
【発明が解決しようとする課題】
災害現場ではいかなる障害や２次災害が発生するとも限らない。１台の中継車が使用不能になっても、通信経路が途絶しないロバスト性も合わせて求められる。災害発生直後には、２次災害の発生により中継車が破壊されたり、故障する場合や、配置候補地へのルートが不通となる場合等の可能性が高い。
【０００７】
このような実際問題に対処するためには、通信経路のロバスト性と伝送品質の保証を実現できることが望まれる。通信経路の最適化において、最も重要な中継器が使用不能になっても高い精度で通信が可能であるような配置および／または周波数割り付けが行われることが望まれる。
通信経路の最適化において、最も重要な中継器が使用不能になっても高い精度で通信が可能であるような配置および／または周波数割り付けを求めるに際して、計算の効率化が行われることが望まれる。
上記の問題をミニマックス型の意思決定問題として定式化し、汎用的な解法をベースとして解くことが望まれている。
【０００８】
なお、特開平６−３１５０２３号公報には、次の予備パス網設計方法が記載されている。その予備パス網設計方法は、伝送路へ複数収容される現用パスおよび予備パスのパス切替を行なうクロスコネクト装置と、故障伝送路の現用パスを救済するために接続可能な予備パスを探索し切替経路を決定する網管理装置とを有する通信網に対して、予備パス設置量の初期値を算出し、その後、削除を行なうことにより最適化を図る予備パス網設計方法において、伝送路が故障した場合の現用パスの救済に必要な量のパスを複数のルートへ割り付ける処理を各伝送路について行ない、それらを積み上げた値を予備パス設置量の初期値とすることを特徴としている。
【０００９】
本発明の目的は、通信経路のロバスト性と伝送品質の保証を実現できる、通信経路の最適化方法、通信経路の生成装置、および通信経路の最適化プログラムを提供することである。
本発明の他の目的は、通信経路の最適化において、最も重要な中継器が使用不能になっても高い精度で通信が可能であるような配置と周波数割り付けを行うことができる、通信経路の最適化方法、通信経路の生成装置、および通信経路の最適化プログラムを提供することである。
本発明の更に他の目的は、通信経路の最適化において、最も重要な中継器が使用不能になっても高い精度で通信が可能であるような配置と周波数割り付けを求めるに際して、計算の効率化を行うことのできる、通信経路の最適化方法、通信経路の生成装置、および通信経路の最適化プログラムを提供することである。
本発明の更に他の目的は、上記の問題をミニマックス型の意思決定問題として定式化し、汎用的な解法をベースとして解くことが可能な、通信経路の最適化方法、通信経路の生成装置、および通信経路の最適化プログラムを提供することである。
【００１０】
【課題を解決するための手段】
その課題を解決するための手段が、下記のように表現される。その表現中の請求項対応の技術的事項には、括弧（）つき、番号、記号等が添記されている。その番号、記号等は、請求項対応の技術的事項と実施の複数形態のうちの少なくとも一つの形態の技術的事項との一致・対応関係を明白にしているが、その請求項対応の技術的事項が実施の形態の技術的事項に限定されることを示されるためのものではない。
【００１１】
本発明の通信経路の最適化方法は、第１通信局（Ｓ）と第２通信局（Ｃ）との間の無線通信を中継するための複数の中継局（Ｒ）を最適に配置するための通信経路の最適化方法であって、（ａ）  前記複数の中継局（Ｒ）が配置されたときの前記第１通信局（Ｓ）と前記第２通信局（Ｃ）との間の伝送品質および通信経路数の少なくともいずれか一方を評価値として設定するステップと、（ｂ）  前記設定された評価値を算出するステップと、（ｃ）  前記算出された評価値に基づいて、前記複数の中継局（Ｒ）の配置を最適化するステップとを備え、前記（ｂ）において、前記設定された評価値を算出する際には、前記複数の中継局（Ｒ）のうちの最も重要なＮ（Ｎは１以上の整数）台の中継局（Ｒ）を求め、前記最も重要なＮ台の中継局（Ｒ）を通過しない通信経路についてのみの前記設定された評価値を算出する。
【００１２】
本発明の通信経路の最適化方法において、前記（ｂ）は、前記複数の中継局（Ｒ）のそれぞれが使用される通信経路数を計算することを含み、前記通信経路数の計算は、前記複数の中継局（Ｒ）、前記第１通信局（Ｓ）および前記第２通信局（Ｃ）間の通信可能性を表す行列を用いて行われる。
【００１３】
本発明の通信経路の最適化方法において、前記（ｂ）は、前記複数の中継局（Ｒ）、前記第１通信局（Ｓ）および前記第２通信局（Ｃ）間の伝送品質を表す行列を用いて、前記第１通信局（Ｓ）と前記第２通信局（Ｃ）との間の伝送品質を計算することを含む。
【００１４】
本発明の通信経路の最適化方法において、前記（ｃ）における前記複数の中継局（Ｒ）の配置の最適化は、発見的手法により行う。
【００１５】
本発明の通信経路の最適化方法において、前記発見的手法は、シミュレーティド・アニーリングである。
【００１６】
本発明の通信経路の最適化方法は、第１通信局（Ｓ）と第２通信局（Ｃ）との間の無線通信を中継するための複数の中継局（Ｒ）を最適に配置するための通信経路の最適化方法であって、（ｄ）  前記複数の中継局（Ｒ）の配置に関する方針Ｘを生成するステップと、（ｅ）  前記方針Ｘの前記複数の中継局（Ｒ）のうち最重要中継局Ｊ（Ｘ）を求めるステップと、（ｆ）  前記方針Ｘから前記最重要中継局Ｊ（Ｘ）を除いた場合の評価値Ｇ（Ｘ−Ｊ（Ｘ））を求めるステップと、（ｇ）  前記評価値Ｇ（Ｘ−Ｊ（Ｘ））が最大となるＸ＝Ｘｏｐｔを求めるステップと、（ｈ）  前記方針Ｘｏｐｔを出力するステップとを備えている。
【００１７】
本発明の通信経路の最適化方法は、第１通信局（Ｓ）と第２通信局（Ｃ）との間の無線通信を中継するための複数の中継局（Ｒ）のそれぞれへの周波数割り当てを最適に行うための通信経路の最適化方法であって、（ｉ）  前記複数の中継局（Ｒ）のそれぞれへの周波数割り当てに関する方針Ｘを生成するステップと、（ｊ）  前記方針Ｘの前記複数の中継局（Ｒ）のうち最重要中継局Ｊ（Ｘ）を求めるステップと、（ｋ）  前記方針Ｘから前記最重要中継局Ｊ（Ｘ）を除いた場合の評価値Ｇ（Ｘ−Ｊ（Ｘ））を求めるステップと、（ｌ）  前記評価値Ｇ（Ｘ−Ｊ（Ｘ））が最大となるＸ＝Ｘｏｐｔを求めるステップと、（ｍ）  前記方針Ｘｏｐｔを出力するステップとを備えている。
【００１８】
本発明の通信経路の最適化方法は、第１通信局（Ｓ）と第２通信局（Ｃ）との間の無線通信を中継するための複数の中継局（Ｒ）を最適に配置するとともに前記複数の中継局（Ｒ）のそれぞれへの周波数割り当てを最適に行うための通信経路の最適化方法であって、（ｎ）  前記複数の中継局（Ｒ）の配置と周波数割り当てに関する方針Ｘを生成するステップと、（ｏ）  前記方針Ｘの前記複数の中継局（Ｒ）のうち最重要中継局Ｊ（Ｘ）を求めるステップと、（ｐ）  前記方針Ｘから前記最重要中継局Ｊ（Ｘ）を除いた場合の評価値Ｇ（Ｘ−Ｊ（Ｘ））を求めるステップと、（ｑ）  前記評価値Ｇ（Ｘ−Ｊ（Ｘ））が最大となるＸ＝Ｘｏｐｔを求めるステップと、（ｒ）  前記方針Ｘｏｐｔを出力するステップとを備えている。
【００１９】
本発明の通信経路の最適化方法において、更に、（ｓ）  前記方針Ｘｏｐｔに従って、前記複数の中継局（Ｒ）を配置するステップとを備えている。
【００２０】
本発明の通信経路の最適化方法において、更に、（ｔ）  前記方針Ｘを採用したときの前記複数の中継局（Ｒ）の配置の容易性を示すＵ（Ｘ）を求めるステップと、（ｕ）  前記評価値Ｇ（Ｘ−Ｊ（Ｘ））と前記Ｕ（Ｘ）の和を前記方針Ｘの評価値Ｆ（Ｘ）とするステップと、（ｖ）  前記Ｆ（Ｘ）が最大となるＸ＝Ｘｏｐｔを求めるステップとを備え、前記（ｄ）、（ｌ）、（ｑ）に代えて、前記（ｔ）、（ｕ）および（ｖ）を実行する。
【００２１】
本発明の通信経路の最適化方法において、更に、（ａａ）  前記中継局（Ｒ）をｈ台経由して、前記第１通信局（Ｓ）と前記第２通信局（Ｃ）を結ぶ経路の伝送品質の総和を示す第１の値（Ｆｕｐｉ（ｈ））を求めるステップと、（ａｂ）前記第１通信局（Ｓ）から特定の前記中継局（Ｒｊ）が経路として前記ｈ台目となるような経路全体での前記第１通信局（Ｓ）から前記特定の前記中継局（Ｒｊ）までの伝送品質を示す第２の値（Ｇｕｐｉ（ｈ））を求めるステップと、（ａｃ）  前記第２通信局（Ｃ）から前記特定の前記中継局（Ｒｊ）が経路として前記ｈ台目となるような経路全体での前記第２通信局（Ｃ）から前記特定の前記中継局（Ｒｊ）までの伝送品質を示す第３の値（Ｇｄｎｉ（ｈ））を求めるステップと、（ａｄ）  前記第２の値（Ｇｕｐｉ（ｈ））と前記第３の値（Ｇｄｎｉ（ｈ））に基づいて、前記特定の前記中継局（Ｒｊ）を経由して前記第２通信局（Ｃ）から前記第１通信局（Ｓ）へ至る全ての経路での伝送品質の和を示す第４の値（Ｉ１（ｉ、ｊ））を求めるステップと、（ａｅ）  前記第１の値（Ｆｕｐｉ（ｈ））に基づいて、前記第１通信局（Ｓ）と前記第２通信局（Ｃ）を結ぶ通信経路の伝送品質の総和を示す第５の値（Ｉｓ（ｉ））を求めるステップとを備え、前記最重要中継局Ｊ（Ｘ）は、前記第４の値（Ｉ１（ｉ、ｊ））および前記第５の値（Ｉｓ（ｉ））に基づいて求められる。
【００２２】
本発明の通信経路の生成装置は、第１通信局（Ｓ）と第２通信局（Ｃ）との間の無線通信を中継するための複数の中継局（Ｒ）が最適に配置された通信経路の生成装置であって、前記複数の中継局（Ｒ）が配置されたときの前記第１通信局（Ｓ）と前記第２通信局（Ｃ）との間の伝送品質および通信経路数の少なくともいずれか一方を評価値として設定する評価値設定部と、前記設定された評価値を算出する評価値算出部と、前記算出された評価値に基づいて、前記複数の中継局（Ｒ）の配置を最適化する最適化部とを備え、前記評価値算出部が前記設定された評価値を算出する際には、前記複数の中継局（Ｒ）のうちの最も重要なＮ（Ｎは１以上の整数）台の中継局（Ｒ）を求め、前記最も重要なＮ台の中継局（Ｒ）を通過しない通信経路についてのみの前記設定された評価値を算出する。
【００２３】
本発明の通信経路の最適化プログラムは、本発明の通信経路の最適化方法の各ステップをコンピュータに実行させるための通信経路の最適化プログラムである。
【００２４】
本発明によれば、通信経路の最適化において、最も重要な中継器が使用不能になっても高い精度で通信が可能であるような配置および／または周波数割り付けを、自動的に計算することができる。
本発明によれば、通信経路のロバスト性と伝送品質の保証を実現できる。最も重要な中継器が使用不能になっても、高い伝送品質で通信経路が確保される。
【００２５】
【発明の実施の形態】
以下、添付図面を参照して、本発明の通信経路の最適化方法の一実施形態として、ロバストな通信経路最適化手法について説明する。
【００２６】
本実施形態では、災害発生時の迅速かつ正確な情報収集のために、広範囲に派遣した観測車からの情報を複数の中継車を介して対策本部まで伝送する無線通信システムにおける、中継車の配置問題を取り上げる。伝送品質の高い経路を確立するための中継車の配置と、混信を回避するための通信周波数の割り当てを最適に決定することに関するモデル化手法と解法について述べる。本実施例の特徴は、情報収集時に中継車が故障するという現実の問題を考慮して、どの１台が使用不能になっても、通信経路が確保でき、高い伝送品質と通信経路数を総合して伝送能力を最も低下させる中継車の故障の影響を最小にするミニマックス型の意思決定問題として定式化できる。これは、非線型整数計画問題となり、シミュレーティドアニーリングを基本として、行列演算による計算の効率化を組み込んだ解法を提案する。具体的な数値例でその有効性を検証した結果を示す。
【００２７】
複数の中継器を用いる通信経路の設定においては、混信の防止と、最も重要な中継器が使用不能になった場合でも通信可能性が保証されることが必要である。各中継器の送受信周波数と、中継器の配置の設定に際しては、中継器の設置候補となる地点間での伝送品質などを考慮し、ロバストな最適配置を計算によって求めることが必要となる。
【００２８】
このように、最も重要な中継器が使用不能になった場合でも通信経路が確保される中継器の配置と周波数割り当てを決定する問題としては、例えば、次の２つの例が考えられる。
【００２９】
（例１）
災害発生時の情報伝達においては、通信インフラが使用不能になる場合がある。災害現地に派遣した観測車両と対策本部の間を複数の中継車両で結び、防災無線帯域の周波数帯を使用して無線通信を行うことが考えられる。このとき、混信を避けるために送受信周波数を異なったものに設定する必要がある。また、二次災害等により中継車両が使用不能になる場合があるため、使用頻度の高い中継車両が使用不能になった場合でも、高い伝送品質で通信経路が確保されていることが必要となる。
【００３０】
（例２）
指揮統制システムにおいて、指揮統制装置とレーダ装置が複数の中継装置を介して通信を行う。このとき、混信を避けるために送受信周波数を異なったものに設定する必要がある。また、ある中継装置が故障または破壊された場合でも確実に通信を行うために、重要度の高い中継装置が使用不能になった場合でも、高い伝送品質で通信経路が確保されていることが必要となる。
【００３１】
本実施形態は、後述する説明で明らかとなるように、上記の（例１）および（例２）のいずれにも適用可能であるが、ここでは（例１）を想定して説明する。
【００３２】
本実施形態は、上記の問題に対し、「どの１台の中継器が使用不能になっても、通信経路が確保されるように周波数割り当ておよび中継器の配置を決定する」方法に関するものである。
【００３３】
まず、本実施形態のアイデアの概略を説明すると以下の▲１▼〜▲５▼の通りとなる。
▲１▼各中継器の周波数割り当てと配置の両方を、ＳＡ（シミュレーティド・アニーリング）などの発見的手法により最適化する。
▲２▼最適化においては、伝送品質または通信経路数を評価値とし、これらの最大化を考える。
▲３▼評価値を計算する際には最も重要な中継装置を求め、その中継装置を通過しない経路の伝送品質または通信経路数を評価値とする。
▲４▼上記の最適化計算の際に、各中継器が何本の通信経路に使われているかを計算する必要がある。このときに、各装置間の通信可能性を表す行列を用いて、この通信経路数を高速に計算する。
▲５▼各装置間の伝送品質を表す行列を用いて、伝送品質を計算する。
【００３４】
なお、以下の本実施形態では、▲１▼各中継器の周波数割り当てと配置の両方の最適化を、ＳＡ（シミュレーティド・アニーリング）などの発見的手法により行うとして説明するが、ＳＡに限定されず、例えば、ＧＡ（遺伝的アルゴリズム）、反復解法により行うことができる。
【００３５】
また、以下の本実施形態では、「どの１台の中継器が使用不能になっても、通信経路が確保されるように周波数割り当ておよび中継器の配置を決定する」方法として説明するが、「どの１台」に代えて、「どのＮ台」であってもよい。または、「周波数割り当て」および「中継器の配置」のいずれか一方を決定する方法であってもよい。
【００３６】
本実施形態では、災害発生時に複数の決められた観測地点に配置された観測車と対策本部及び、その間の伝送信号を中継する複数の中継車からなる無線通信システムにおいて、中継車の配置場所及び中継車の送受信周波数を決定する問題を取り扱う。その際に、配置した中継車のうち１台が使用不能となることを許容した問題、即ち単一故障でシステムの機能を喪失しないというロバスト性を保証する設計問題と捉える。これは、災害発生直後には２次災害の発生により中継車が破壊される場合や配置候補地へのルートが不通となる場合等の可能性が高いという、実際問題に対処するためである。
【００３７】
この問題は、任意の中継車の１台の故障に対して、通信経路を最大限確保するとともに、伝送品質を最大にすることである。このため、無線通信システムにおける観測車、中継車と本部との間の通信経路の設定に関し、通信の伝送能力を伝送品質と通信経路の冗長度の統合した形でモデル化し、無線通信システムの伝送上最も重要な中継車の故障が発生した条件下で伝送能力を最大化するミニマックス型の最適問題として定式化する。また、本実施形態は現実の通信で課題となる混信のない通信経路確立のための中継車での周波数決定も合わせて解決することが特徴である。非線型整数計画問題を解く必要があり、シミュレーティドアニーリングを基本として、行列演算による計算の高速化を組み込んだ解法を提案する。具体的な数値例でその有効性を検証した結果を示す。
【００３８】
最適配置問題は、ＯＲの分野で古くから研究されている。実務応用を狙ったものに限定しても、ボロノイ図による学校やポストの最適配置、被覆モデルによるネットワーク上の施設配置等がある。また、配置の意思決定に対して、競合相手を導入した競争立地モデルについては、ショッピングモールの小売吸引力を扱う問題や、ハブ空港配置をシュタッケルベルグ問題として扱った２段階最適化問題がある。
【００３９】
これらは、問題の理論的なアプローチのために、現実の課題での運用条件の本質的な部分を抽出して、理論的な厳密性と汎用性を持たせていることで価値が高い。
【００４０】
これに対し、本実施形態では、現実問題の直接的な解決に主眼を置き、災害時の通信経路確保という社会的ニーズの強い問題を取り上げ、課題の性質を忠実に定式化することを目指した。現実問題として考えざるを得ない「重要な設備の故障」をミニマックス型の課題として取り組み、設備設置の条件や考慮すべき評価基準も実運用を忠実に反映した。
【００４１】
以下、［１］では、問題を具体的に説明し、［２］で最適化問題として数学的に定式化し、［３］では、シミュレーティドアニーリング法を基本とする解法について説明する。［４］では、典型的なモデルに対して実行した結果により、解の性質や解探索時間についての評価を行う。
【００４２】
［１］  中継車配置の課題
［１．１］  中継車の配置
広域災害が発生し、公共の通信手段が輻輳や被害により使用不能となった状況を仮定する。災害発生の場合、被害状況を迅速かつ正確に把握するために観測車を派遣する。観測車は、被害状況が大局的に把握できるように広範囲に分散するように派遣される。大局的把握を行うための観測装置としては、他にハイテク気球やヘリコプター等もあるが、台風被害などの悪天候状況下では使用が限定される。車両は空からの観測に比べるとアクセス性や大局性では劣るものの、基本的な手段として有効である。
【００４３】
観測車には、本部からの指令を受け情報を送信するための通信機が搭載される。指令や情報は、音声の場合と画像等のデータの場合がある。災害における観測範囲としては、阪神大震災や有珠山噴火の１００〜２００ｋｍ２以上が対象となる。本部が県庁に置かれた場合、観測点から本部までの距離は直線距離で５０〜１００ｋｍ以上となる。一方、通常の実効放射電力レベル（１ｋＷ）で基地局のアンテナ高さが１００ｍとすると３０ｄｂの受信強度を得るには４０ｋｍ以下、１０ｄｂでも８５ｋｍ以下が条件となる（通信周波数１５０ＭＨｚの場合）。
【００４４】
従って、観測車と本部との間を中継する中継車が必要になる。現実的な出力と環境を考慮すると、観測車と中継車、中継車同士、中継車と本部の距離はそれぞれ３０ｋｍ以下となる。中継車の配置数は少ないほどよいので、１台の中継車が複数の観測車と本部との中継を担当することも可能とする。ただし、以下に説明するように、災害現場ではいかなる障害や２次災害が発生するとも限らない。１台の中継車が使用不能になっても、通信経路が途絶しないロバスト性も合わせて求められる。
以上のことから、災害の状況収集において以下を決定することが課題の一つである。
【００４５】
［課題１］
固定された複数位置の観測車と本部との間に中継車を複数配置し、多段の中継により観測車と本部の情報伝達を可能にするように、複数の中継車位置を決定する。配置に際しては、伝送品質や経路の冗長性、配置の容易性等を考えて適切な場所を選定する。
【００４６】
ここで、伝送品質とは、正常に通信される確率であり、経路の距離や地形条件から決められるものである。経路の冗長性とは、複数経路数であり、１台の中継車の故障に対しても通信を継続できる性質である。伝送品質と経路の冗長性を統合して伝送能力と呼ぶ。配置の容易性とは、各中継車の指定の配置場所への到着させやすさを意味し、地形、道路の混雑状況や道路幅等から決定されるものである。
【００４７】
観測車と対策本部を結ぶ中継車の配置の例を図１に示す。以降の議論の便宜上、本部側を上位側、観測車を下位側と呼ぶ。観測指令は上位側から下位側へのメッセージの流れになり、観測情報は下位側から上位側に流れる。
【００４８】
［１．２］  周波数の割付
通信の成立条件は、中継車同士が電波の届く距離にあるということに加えて、送信側の中継車の無線機と受信側の無線機の周波数が同じに設定してあることが必要である。
【００４９】
中継車には、上位側との連絡用、下位側との連絡用の２台の無線機を搭載する。１台の中継車が使用できる周波数は配置している間中固定である。データ通信の場合には、必要なデータを全て受信し蓄えてから送信することも可能であるため無線機は１台でもよい。しかし音声通信の場合には、蓄えを行うと人間にとって不自然な遅延が発生するために、受信しながら送信する必要がある。従って２台の無線機が必要になる。
【００５０】
受信しながら送信するため、送信と受信の周波数が同じであると１台の中継装置の中で混信が起きる。上位側用と下位側用とで異なる周波数を用いることが必要になる。
【００５１】
このため、使用する周波数の種類についても考察が必要となる。特定の観測車と本部との通信経路を確立する際に、本部→中継車Ｒ１→中継車Ｒ２→観測車，という場合を考える。本部の周波数をｆ１とし、中継車の周波数を（上位側、下位側）で表すことにする。最低の周波数種類で経路を確立するには、中継車Ｒ１，中継車Ｒ２，観測車の周波数をそれぞれ（ｆ１、ｆ２），（ｆ２、ｆ１），ｆ１とすればよい。中継車が多くなっても２種類の周波数を交互に使うことで経路の確率が可能と思われる。
【００５２】
しかし、現実にはこの方式では混信が発生する場合がある。
中継車Ｒ１，Ｒ２，Ｒ３，Ｒ４が（ｆ１、ｆ２），（ｆ２、ｆ１），（ｆ１、ｆ２），（ｆ２、ｆ１）という周波数で通信する場合を考える。この時、中継車Ｒ１からの出力が中継車Ｒ２に届くと同時に中継車Ｒ４にも届く可能性がある。Ｒ１からＲ２，Ｒ３を経由したメッセージとＲ４に直接届くメッセージとには若干の遅延関係があるため、これにより中継車Ｒ４において混信が発生する。Ｒ１やＲ４が本部，観測車であっても同様である。混信の例を図２に示す。
【００５３】
中継車導入の原則から考えると、中継車Ｒ１と中継車Ｒ４は十分離れていることが期待されるが、第１．１項で説明したように、中継機は１台で複数の観測車との中継を受け持つ場合があり、かつ伝送品質がなるべく高くなるように配置されるので、観測地点が多い場合や観測地点間の位置関係が複雑な場合には必ずしも中継車Ｒ１と中継車Ｒ４が離れていないことも考えられる。
【００５４】
従って一般には、２種類以上の周波数を用いて、各中継車の位置を決定する際に中継車に搭載する２台の無線機の周波数を混信が起きないように決定する必要がある。
【００５５】
次に、周波数の決定の際、本部から特定の観測車Ｓ１への経路が複数存在する方がより冗長的な配置であるが、複数の経路がある場合に経路間での混信をおこさない工夫について説明する。
【００５６】
図３に、複数経路が定義できる配置の例を示す。
通信は音声によるものとする。本部は、観測車との通信を行う前にこれから使う経路を定義するデータＤとして、経路として使用する中継車と観測車のＩＤ番号を並べたデータを送信することにより経路を１つに決定する。１例を以下に示す。
Ｄ＝（経路の定義；ｐａｔｈ＝（Ｒ１，Ｒ３，Ｒ５，Ｓ１））．
【００５７】
データを受信した中継車は、データの命令が経路の定義であることを認識し、データ内の経路を表すＩＤ番号を調べる。自分が経路に含まれていなければ、音声データを受信しても下位側への送信は行なわない。自分が経路に含まれていた場合には、送信周波数を用いて送信する。
【００５８】
経路を定義するデータを送信し直すことにより、異なる経路を使用することが可能である。
【００５９】
なお、複数の観測車との交信での混信については、以下の理由により考慮する必要がない。即ち、複数の相手と同時に交信することは、音声を使用する場合には無用である。１回のタイミングでは本部からある１つの観測車に対してのみ交信することとする。これにより、複数の観測車との通信による混信の問題もなくなる。
【００６０】
以上、混信を回避するための方針を図４にまとめる。
図４に示すように、１つの通信経路内での混信を回避するために、各中継車毎に送受信周波数を割り当てる。また、１つの観測車と本部との間の複数経路間の混信を回避するために、通信開始時に、これから使用する経路を１つに決めるデータを送信する。また、複数の観測車との間の経路間の混信を回避するために、本部と複数の観測車との同時交信は行なわない。
【００６１】
第２の課題は以下のようになる。
【００６２】
［課題２］
固定された複数の観測車と本部とを中継する複数の中継車を配置する際に、各中継車の使用する２種類の周波数と観測車の周波数とを決定する。決定に当たっては、経路の冗長度が高くなることと、決定される経路の伝送品質が高くなることを目的とする。
【００６３】
［２］  最適配置問題の定式化
［２．１］  最適性の定義
前節で説明した課題に対する最適化について説明する。最適化とは、指定された台数の中継車の位置と、中継車と観測車の周波数を以下の最適性に基づいて最大化することである。
【００６４】
［最適性］  任意の１台の中継装置が故障した場合にも、重要な観測車との通信経路数が多く、かつ経路の伝送品質が高くできること。最適性の評価指標は、冗長な経路数及び経路の伝送品質であり、これをまとめて伝送能力と呼ぶ。
【００６５】
［２．２］  中継車配置と周波数決定の記号表現
記号Ｓｉにより観測車を表し、Ｒｊにより中継車を表すものとする。中継車の配置場所は、事前に候補地として選定しておくＮ種類の場所に限定されるものとし、このうちのＭ箇所に実際に配置するものとする。観測車はＬ種類の場所に配置されているとする。本部はＣで表す。
【００６６】
中継車のｊ番目の配置場所はＰｒｊで表し、観測車のｉ番目の配置場所はＰｓｉで表す。本部の場所はＰｃで表す。
【００６７】
中継車、観測車の状態を表す変数を以下のように定義する。中継車の配置を表す変数ｒｊは、ｊ＝１，・・・，Ｎについてｊ番目の配置候補場所に実際に中継車を配置する場合には１、しない場合には０をとる。使用周波数は、ｊ番目の場所の中継車が上位側との通信に使う周波数をｆｕｐ（ｊ）、下位側との周波数をｆｄｎ（ｊ）とする。周波数は、Ｈ種類（Ｆ＝｛ｆ１，・・・，ｆＨ｝）の中から選択する。配置されない場所ｊ’での周波数はｆｕｐ（ｊ’）＝ｆｄｎ（ｊ’）＝０とする。これらを、
【数１】
0003905712.tif 000002
と表す。
【００６８】
観測車については、Ｌ種類の場所にすべて配置されているので、配置を表す変数は定義しない。使用周波数は、観測車Ｓｉについてｆｓ（ｉ）∈Ｆ（１≦ｉ≦Ｌ）とする。
【数２】
0003905712.tif 000003
本部の使用周波数はｆｃ（ｃ）＝ｆＨ（固定）とする。
【００６９】
また、決定すべき変数をまとめてＸで表し、方針と呼ぶ。方針Ｘは中継車の配置と周波数、観測車の周波数をまとめたものであり、
【数３】
0003905712.tif 000004
である。
【００７０】
方針Ｘを決めることにより、Ｃから各Ｓｉへの通信経路の集合が定まる。これをＲ（Ｘ；Ｓｉ）と表す。Ｒ（Ｘ；Ｓｉ）のｋ番目の経路をＥｋ（Ｘ；Ｓｉ）と表す。Ｅｋ（Ｘ；Ｓｉ）∈Ｒ（Ｘ；Ｓｉ）である。
【００７１】
方針Ｘを決める際の配置評価関数をＦ（Ｘ）と表す。ある１つの中継車をＪとし、方針Ｘで使用した中継車のうちＪが使用不能になることをＸ−Ｊと表す。Ｘ−Ｊは、ｒＪ＝０，ｆｕｐ（Ｊ）＝ｆｄｎ（Ｊ）＝０とすることに相当する。
【００７２】
Ｊ以外の中継車を用いて構成できる経路評価関数をＧ（Ｘ−Ｊ）と表現する。
方針Ｘで最も重要な中継車をＪ（Ｘ）とすると、方針Ｘの評価関数は、
Ｆ（Ｘ）＝Ｇ（Ｘ−Ｊ（Ｘ））＋Ｕ（Ｘ）
で表される。ここで、最も重要な中継車Ｊ（Ｘ）とは、中継車Ｊ（Ｘ）が使用不能となった時に経路評価関数Ｇ（Ｘ−Ｊ）が最小となる中継車である。また、Ｕ（Ｘ）は、Ｘで定まる場所へ中継車を配置する容易性であり、道路状況等から定まる。
【００７３】
第［１］節で説明したように、本実施形態での意思決定は、方針Ｘとして、最も重要な中継車Ｊ（Ｘ）が１台使用不能になった場合の配置評価関数Ｆ（Ｘ）＝Ｇ（Ｘ−Ｊ（Ｘ））＋Ｕ（Ｘ）を最大とするＸを求めることであり、これは以下のようにミニマックス型の課題として定式化できる。
【００７４】
［課題の定式化］Ｘｏｐｔｓ．ｔ．
Ｆ（Ｘｏｐｔ）＝ｍａｘＸＧ（Ｘ−Ｊ（Ｘ））＋Ｕ（Ｘ）となる方針Ｘｏｐｔを求める。ここで、Ｊ（Ｘ）はＧ（Ｘ−Ｊ（Ｘ））＝ｍｉｎＪＧ（Ｘ−Ｊ）を満たすものである。
【００７５】
評価関数に使われるＧ（Ｘ），Ｕ（Ｘ）の具体的な内容については次項で説明する。
表現した記号を図５、図６、図７にまとめる。
【００７６】
［２．３］  評価関数の定義
第２．２項で説明した評価関数の内容を具体的に示す。まず、評価関数に必要なパラメータを整理する。上位側中継車Ｒｊ１と下位側Ｒｊ２の間の伝送品質をａｊ１，ｊ２と表す。０≦ａｊ１，ｊ２≦１である。ただし、ａｊ１，ｊ２＞０の場合には必ずａｊ１，ｊ２＞θとする。θは伝送の最低品質を決めるしきい値であり、これ以下の伝送品質は全て０とおく。ａｊ１，ｊ２は、中継車ｒｊ１とｒｊ２の間の距離、遮る山や建物の有無等の地形条件で決まる係数であり、場所毎に設定しておく。ａｊ１，ｊ２がしきい値以下となる距離を通信限界距離という。
【００７７】
ただし、中継車の配置有無や周波数の整合による条件として、ｒｊ１・ｒｊ２＝０の場合にはａｊ１，ｊ２＝０とする。また、ｆｄｎ（ｊ１）≠ｆｕｐ（ｊ２）（Ｒｊ１がＲｊ２の上位側）の場合にもａｊ１，ｊ２＝０とする。
【００７８】
同様に、本部Ｃと中継車Ｒｊとの伝送品質ａｃ，ｊ，観測車Ｓｉと中継車Ｒｊとの伝送品質ａｊ，ｓｉも定義する。
【００７９】
方針Ｘに対する本部Ｃから観測車Ｓｉとのｋ番目の通信経路Ｅｋ（Ｘ；Ｓｉ）を
【数４】
0003905712.tif 000005
と表す。第（１）式に含まれる中継車ＲｊをＳｉへの通信経路に包含されるという。最後のＲｊＰｋにおいてＰｋとなっているのは、経路に含まれる中継車数Ｐは経路ｋ毎に異なるためである。
【００８０】
経路Ｅｋ（Ｘ；Ｓｉ）の伝送品質Ｔ（Ｅｋ（Ｘ；Ｓｉ））は、
【数５】
0003905712.tif 000006
である。
【００８１】
ＣからＳｉまでの経路の総数をＶ（Ｘ；Ｓｉ）とする。Ｖ（Ｘ；Ｓｉ）は、Ｔ（Ｅｋ（Ｘ；Ｓｉ））＞０となる経路の個数である。Ｔ（Ｅｋ（Ｘ；Ｓｉ））を、本部Ｃから観測車Ｓｉまでの経路総数Ｖ（Ｘ；Ｓｉ）分並べたベクトルを
【数６】
0003905712.tif 000007
と表す。
【００８２】
また、場所Ｐｒｊに配置する容易性をｂｊとする。方針Ｘを採用することによる配置の容易性Ｕ（Ｘ）は、
【数７】
0003905712.tif 000008
で与えられる。容易性ｂｊは、中継車が場所Ｐｒｊへ行くことの容易性であり、本部からのアクセスする際の道幅の広さや途中の道路の混雑状況等、配置を検討する際に収集できる情報から、人間が総合的にランクＡ，Ｂ，Ｃ程度に分類してＡは１０点、Ｂは７点、Ｃは３点のように設定する。事前の情報がなければ等しくＡランクとしておけばよい。
【００８３】
経路評価関数Ｇ（Ｘ）は、ｌｐノルム‖・‖ｐを用いて、
【数８】
0003905712.tif 000009
と定義する。ただし、方針Ｘにより全ての観測車との通信経路が確立できない場合には、経路評価関数Ｇ（Ｘ）の値は０とする。また、
【数９】
0003905712.tif 000010
である。これは、ｐ＝１の場合には、各成分の絶対値の和をとることに相当し、ｐ＝∞の場合には絶対値が最大の成分をとることに相当する。
【００８４】
即ち、（４）式は、配置と周波数の決定において、経路数と各観測車への経路の伝送品質に関する［最適性］の基準を表現した伝送能力を表し、ｐの値によって通信経路数と伝送品質のどちらをどれだけ重視するかを制御できる。
【００８５】
［２．４］  最重要中継車の定義
本実施形態の課題では、最重要中継車が使用不能になった場合の伝送能力を問題にする。最重要中継車とは、前節で述べたように経路評価関数Ｇ（Ｘ−Ｊ）が最小になる中継車Ｊである。
この定式化が、通常考えられる「経路全体の伝送能力」を最大にする定式化に比べ防災無線中継車の配置という課題において優れている点を図８および図９を参照して説明する。
図８（ａ）および（ｂ）は、中継車の位置が固定された２種類の周波数割り当てのパターンを示している。図９に示すように、ｐ＝１での「経路全体の伝送能力」を最大にする評価関数に従うと、図８（ａ）の方針の方が評価値が高くなる。しかし、この方針は、１台の中継車が使用不能になると通信経路がなくなる場合があるという意味でロバストでない。
一方、本実施形態の定式化に従うと、図８（ｂ）の方針の方が評価値が高くなる。図８（ｂ）の方針ではどの１台が使用不能になっても通信経路を確保したロバストな方針である。
【００８６】
［３］  最適化の解法
［３．１］  中継車配置と周波数決定の解探索の流れ
中継車配置と周波数の割り当ての標準的なステップは以下の（ステップ１）〜（ステップ６）のようになる。
【００８７】
［中継車配置と周波数割り当て］
（ステップ１）  方針Ｘを一つ決める。決め方は、方針Ｘの生成で詳述する（[方針Ｘの生成方法]）。
（ステップ２）  方針Ｘに対する配置の容易性Ｕ（Ｘ）を（３）式により求める。
（ステップ３）  方針Ｘの中からｍｉｎＪＧ（Ｘ−Ｊ）に基づき最重要中継車Ｊ（Ｘ）を求める（[最重要中継車選択]）。方針Ｘからその中継車Ｊ（Ｘ）を取り除く。残りをＸ−Ｊ（Ｘ）と表す。
【００８８】
（ステップ４）  （４）式に基づき、方針Ｘから中継車Ｊ（Ｘ）を除いた場合の評価値Ｇ（Ｘ−Ｊ（Ｘ））を求める（[経路評価関数計算]）。
（ステップ５）  評価値Ｇ（Ｘ−Ｊ（Ｘ））＋Ｕ（Ｘ）を方針Ｘの評価値Ｆ（Ｘ）とする。
【００８９】
（ステップ６）  Ｆ（Ｘ）が最大となるＸ＝Ｘｏｐｔが求まるまで、ステップ１から繰り返す。
【００９０】
ただし、（ステップ３）から（ステップ４）の処理は、方針Ｘを変更する繰り返しの中で何度も計算されるため、高速性が必要となる。本実施形態では、行列演算によりこの部分を高速化した。評価は第３．３節の[最重要中継車選択と経路評価関数計算]で説明する。
【００９１】
［３．２］  方針の生成方法
方針Ｘは、中継車の配置を表す離散的な変数｛ｒｊ｝と、周波数を表す離散的な変数｛ｆｕｐ（ｊ），ｆｄｎ（ｊ），ｆｓ（ｉ）｝から構成される。いずれの変数も数理解析的に生成する適切な方法がないため、組み合わせ問題を戦略的に計算する方法であるシミュレーティドアニーリングを採用する。方針の初期値Ｘｔ＝Ｔ０はランダムに生成し、以降の方針Ｘｔ＝Ｔ０＋１は、Ｘｔ＝Ｔ０から以下の（ステップ１）〜（ステップ６）のように生成する。
【００９２】
［方針Ｘの生成方法］
（ステップ１）  方針Ｘｔ＝Ｔ０でｒｊ＝１である中継車Ｒｊもしくは観測車Ｓｉの一つをランダムに選択する。
（ステップ２）  中継車Ｒｊを選択した場合には、変数ｒｊ，ｆｕｐ（ｊ），ｆｄｎ（ｊ）のうちどれか１つを、それぞれ確率Ｐｒ（ｒ），Ｐｒ（ｆｕｐ），Ｐｒ（ｆｄｎ）に従って選択する。ただし、Ｐｒ（ｒ）＋Ｐｒ（ｆｕｐ）＋Ｐｒ（ｆｄｎ）＝１である。観測車を選択した場合には、ｆｓ（ｉ）を確率１で選択する。
【００９３】
（ステップ３）  変数ｒｊを選択した場合には、Ｘｔ＝Ｔ０においてｒｊ’＝０であるｊ’をランダムに１つ選択し、ｒｊ＝０，ｒｊ’＝１と置き換える。さらに、ｆｕｐ（ｊ’）＝ｆｕｐ（ｊ），ｆｄｎ（ｊ’）＝ｆｄｎ（ｊ）とし、ｆｕｐ（ｊ）＝０，ｆｄｎ（ｊ）＝０とする。
【００９４】
（ステップ４）  ｆｕｐ（ｊ）を選択した場合には、ｆ∈｛ｆ２，…，ｆＨ｝の中からｆ＞ｆｄｎ（ｊ）を満たすようにランダムに選択し、ｆｕｐ（ｊ）＝ｆとする。
（ステップ５）  ｆｄｎ（ｊ）を選択した場合には、
ｆ∈｛ｆ１，ｆ２，…，ｆＨ−１｝の中から、ｆ＜ｆｕｐ（ｊ）を満たすようにランダムに選択し、ｆｄｎ（ｊ）＝ｆとする。
【００９５】
（ステップ６）  ｆｓ（ｉ）を選択した場合には、
ｆ∈｛ｆ１，ｆ２，…，ｆＨ−１｝の中からランダムに選択し、ｆｓ（ｉ）＝ｆとする。
【００９６】
ここで、解探索の効率化のために、中継車が使用する周波数は、ｆｕｐ（ｊ）＞ｆｄｎ（ｊ）となる条件を付加した。この条件は解空間を限定するが、経路にループが生じず、本部から観測車までの間に存在しうる中継車が最大Ｈ−１台になることで、解探索を効率化することができる。
【００９７】
［３．３］  伝送品質と経路数の計算方法
最適な方針Ｘの探索に際し、（４）式及び最重要中継車選択は、上記方針Ｘ生成の中で毎回評価されるため、高速に計算できる必要がある。
本実施形態では、（４）式がｐ＝１の場合を行列計算で表現し、行列計算の途中結果を利用してＪ（Ｘ）を求め、効率的にＧ（Ｘ−Ｊ（Ｘ））の計算が出来るように工夫した。以下、その手法について説明する。
本手法の正当性については、後述するとともにその計算の具体性を示す。
【００９８】
［準備］
【数１０】
0003905712.tif 000011
を、本部Ｃと各中継車との伝送品質を表すベクトルとする。（・）ｔは転置ベクトルを表す。
【００９９】
【数１１】
0003905712.tif 000012
を、観測車Ｓｉと各中継車との伝送品質を表すベクトルとする。
【０１００】
【数１２】
0003905712.tif 000013
を、上位側中継車Ｒｊ１と下位側中継車Ｒｊ２との伝送品質を表すＮ×Ｎ行列とし、隣接行列と呼ぶ。
【０１０１】
【数１３】
0003905712.tif 000014
をｑ番目の成分のみが１で他は０であるＮ次元列ベクトルとすると、
【数１４】
0003905712.tif 000015
は、中継車Ｒｑの上位側にありＲｑと直接通信可能な各中継車との伝送品質を表すベクトルである。また、
【数１５】
0003905712.tif 000016
は、中継車Ｒｑの下位側にありＲｑと直接通信可能な各中継車との伝送品質を表すベクトルである。
行列
【数１６】
0003905712.tif 000017
のｉ，ｊの成分は、ｈ台の中継車を経由して中継車Ｒｉから中継車Ｒｊに行く全経路の品質の総和である。
【０１０２】
［最重要中継車選択と経路評価関数計算］
（ステップ１）  観測車ｉ＝１，…，Ｌについて、以下のステップ２からステップ１１を繰り返す。
（ステップ２）
【数１７】
0003905712.tif 000018
を計算する。
【０１０３】
（ステップ３）
【数１８】
0003905712.tif 000019
を計算する。
【０１０４】
（ステップ４）  ステップ３と同様の計算により、
Ｆｕｐｉ（２），Ｇｕｐｉ（２），…，Ｆｕｐｉ（Ｈ−１），Ｇｕｐｉ（Ｈ−１）を順次計算する。
ここで、
【数１９】
0003905712.tif 000020
は、中継車をｈ台経由して、観測車Ｓｉと本部を結ぶ経路の伝送品質の総和である。また、
【数２０】
0003905712.tif 000021
の第ｊ成分は、観測車Ｓｉから中継車Ｒｊが経路としてちょうどｈ台目となるような経路全体での伝送品質（観測車Ｓｉから中継車Ｒｊまでの）の総和を表す。
【０１０５】
ここで、Ｇｕｐ、Ｇｄｎを考えるのは、中継車のうち最も重要なものを除く処理が必要であるためであり、中継車の１台が壊れるという前提がなければ、Ｆｕｐだけでよい。
【０１０６】
（ステップ５）  ΣＨ−１ｈ＝１Ｆｕｐｉ（ｈ），ΣＨ−１ｈ＝０Ｇｕｐｉ（ｈ）を計算する。ただし、
【数２１】
0003905712.tif 000022
とする。
【０１０７】
（ステップ６）
【数２２】
0003905712.tif 000023
を求める。
【０１０８】
（ステップ７）  Ｇｄｎ（２）＝Ｇｄｎ（１）・ＡＲを求める。
（ステップ８）  ステップ７と同様の計算により、Ｇｄｎ（２），Ｇｄｎ（３），…，Ｇｄｎ（Ｈ−１）を順次計算する。ここで、
【数２３】
0003905712.tif 000024
の第ｊ成分は、本部Ｃから中継車Ｒｊが経路としてちょうどｈ台目となるような経路全体での伝送品質（本部Ｃから中継車Ｒｊまでの）を表す。
【０１０９】
（ステップ９）  ΣＨｈ＝０Ｇｄｎ（ｈ）を計算する。ただし、
【数２４】
0003905712.tif 000025
とする。
【０１１０】
（ステップ１０）  １≦ｊ≦Ｎについて、ΣＨｈ＝０Ｇｕｐｉ（ｈ）とΣＨｈ＝０Ｇｄｎｉ（ｈ）の第ｊ成分同士を掛けたものをＩ１（ｉ，ｊ）とする。Ｉ１（ｉ，ｊ）は、中継車Ｒｊを経由して本部から観測車Ｓｉへ至る全ての経路での伝送品質の和を表す。
【０１１１】
（ステップ１１）  Ｉｓ（ｉ）＝ΣＨ−１ｈ＝１Ｆｕｐｉ（ｈ）を求める。Ｉｓ（ｉ）は、観測車Ｓｉと本部を結ぶ通信経路の品質の総和である。
【０１１２】
（ステップ１２）  全ての観測車ｉについてＩ１（ｉ，ｊ）が求まったら、Ｇ（Ｘ−ｊ）＝ΣＬｉ＝１（Ｉｓ（ｉ）−Ｉ１（ｉ，ｊ））を求める。ただし、あるｉについてＩｓ（ｉ）＝Ｉ１（ｉ，ｊ）となる場合には、Ｇ（Ｘ−ｊ）＝０とする。
【０１１３】
（ステップ１３）  全てのｊについて、Ｇ（Ｘ−ｊ）が最小となるｊをＪ（Ｘ）とし、Ｆ（Ｘ）＝Ｇ（Ｘ−Ｊ（Ｘ））＋Ｕ（Ｘ）とする。
【０１１４】
なお、本計算量は、中継車候補地数をＮ、観測車台数をＬとするとＯ（Ｎ２・Ｌ）のオーダーとなり、少ない計算量で計算することができる。
【０１１５】
［４］  計算結果
解法の能力を評価するために、図１０に示す基本条件で検証を行った。
なお、本実験では観測車が本部からほぼ等距離にあることから、観測車の周波数は全てｆ１に固定した。
【０１１６】
中継車の配置候補位置と初期配置、本部、観測車の配置例を図１１に示す。△が観測車位置、□が本部の位置を表す。○が中継車を置ける候補地であり●の部分が実際に中継車を配置した場所を示す。白抜きの文字は中継車番号であり、左右の数字は、上位側、下位側の周波数番号である。１辺の長さを１．０とする。中継車同士、中継車と本部や観測車を結ぶ点線は、周波数条件と通信限界距離条件を満たし通信可能であることを示す。初期状態では、本部と観測車を結ぶ経路は全く確立していない。
【０１１７】
通信限界距離を０．５２に設定し３０万回の繰り返し計算を行った。距離０．５２とは、図で示した格子点の１×４，２×３の格子範囲が通信可能になることに相当する距離であり、通信限界距離をこれ以下にすると経験上基本条件ではほとんど解が求まらないという限界ぎりぎりの値である。最重要中継車は図中四角で囲んだ。位置（１．０，０．２５）の観測車と本部を結ぶ複数の通信経路の中で、最も伝送品質の高い経路を図１２に太線で示す。図１２の中で、最重要中継車である中継車５（位置（０．３７５，０．３７５）の中継車）が使用不能になった場合の経路例を図１３に太線で示す。全ての観測車との通信経路が最低１本確保されており、ロバストな通信経路が確立できている。
【０１１８】
さらに３０万回繰り返し計算をした結果を図１３に示す。図１２と比較すると、図１２では本部との中継に４台の中継車を経由し、全５種類の周波数を用いて通信経路を求めているのに対し、図１４の結果では３台の中継車と４種類の周波数で経路を確立している。使用周波数の種類が少ないということは、中継車の数が同じ場合特定の周波数で通信できる中継車数の期待値が大きい。従って、通信経路数が多くなり、伝送能力の高い方針となっている。
【０１１９】
本部と観測車の位置関係を変えた場合の結果例を図１５に示す。ここでは、通信限界距離０．６で計算した。
本計算は、３０万回のシミュレティドアニーリングの繰り返しにおいて、PentiumII（200ＭＨｚ）クラスのＰＣを用いて約４分で計算を終了することができた。
【０１２０】
［５］  おわりに
広域の災害において、広範囲からの情報を迅速かつ正確に収集するための通信手段の確立は今後ますます重要になってくると思われる。その際、防災無線の周波数帯による無線通信の確立は、衛星通信やインターネット、携帯電話等の近年急激に発展してきているインフラを利用した方法に比べ基礎的ではあるものの、系列の多重化という観点から必要不可欠であり、安定かつ効率のよい利用方法を確立しておくべき分野である。
【０１２１】
本実施形態では、広域に分散した観測車と本部とを結合するために、送受信周波数を事前に決定した中継車を中間点に配置する問題を最適化した。最適化の観点は、災害時の使用ということを考慮して「最も重要な中継車両が使用不可になる」という想定でも通信経路が確立でき、伝送品質が最大となるように位置と周波数とを決定することである。この問題を、ミニマックス型の意思決定問題として定式化した。
【０１２２】
現実問題の中継車数と配置可能な候補地数を考慮すると、定式化した問題は大規模なロバスト最適化問題ととらえられる。これを汎用的な解法であるシミュレーティドアニーリング法をベースとして戦略的に解く方式を考えた。ミニマックス型は２段階意思決定になり、使用不可となる中継車を選択する部分は、計算の効率化のために行列演算による数理的な手法により高速化した。
典型的なデータにより解探索の効率を評価した。結果は納得のできる配置であり、災害時の短時間に人間が方針を決定する支援として計算機により自動計算できる有効性が確認できた。
【０１２３】
次に、本実施形態で用いた行列を用いた伝送精度の計算法について説明する。
【０１２４】
伝送経路最適化問題においては、最適化計算を行う際に伝送精度の計算が必要となる。本節では、行列とベクトルを用いて伝送精度を計算する方法について述べる。
【０１２５】
１．１  通信可能性の行列表示
中継車Ｒの台数をK台、観測車Ｓの台数をl台とする。
Ｒｉのｕｐ側とＲｊのｄｏｗｎ側の通信精度をａｉｊとおく。また、Ｒｉのｕｐ側と本部Ｃの通信精度をａｉ０とおき、ＲjとＳlの通信精度をａｋ＋１，ｊとおく。このとき、各装置間で通信不可能であれば、ａｉｊ＝０とおく。
行列ＡＲを
【数２５】
0003905712.tif 000026
で定めると、行列ＡＲは中継車Ｒ間の通信精度を表す行列となる。この行列はＡを以下「Ｒ−接続行列」と呼ぶ。
【０１２６】
ａｋ＋１，ｊをｊについて横に並べたベクトル
【数２６】
0003905712.tif 000027
は、Ｓｉと各中継車Ｒの通信精度を表すベクトルとなる。このベクトルｓｉを以下「Ｓｉの接続ベクトル」と呼ぶ。
【０１２７】
ａｉ，０をｉについて縦に並べたベクトル
【数２７】
0003905712.tif 000028
は、本部Ｃと各中継車Ｒ間の通信精度を表すベクトルとなる。このベクトルｃを以下「本部Ｃの接続ベクトル」と呼ぶ。
【０１２８】
Ｒ−接続行列Ａｒの第Ｋ行の下側に観測車Ｓの接続ベクトルをｉ＝１，２，…，ｌの順に挿入した行列を
Ａｓとおく：
【数２８】
0003905712.tif 000029
この行列Ａｓを以下「Ｓ−接続行列」と呼ぶ。
【０１２９】
Ｒ−接続行列ＡＲの第１列の左側に本部Ｃの接続ベクトルを挿入した行列をＡＣとおく：
【数２９】
0003905712.tif 000030
この行列ＡＣを以下「Ｃ−接続行列」と呼ぶ。
【０１３０】
なお、ａｉｊを各装置間の通信精度と定義したが、０−１変数を用いることによって通信の可／不可を表すことができる。この場合、得られる結果は通信精度ではなく伝送経路数となる。
【０１３１】
（例１）
図１６に示すようなネットワークの場合、接続ベクトルおよび接続行列は以下のようになる。
【数３０】
0003905712.tif 000031
【数３１】
0003905712.tif 000032
【数３２】
0003905712.tif 000033
【数３３】
0003905712.tif 000034
ただしこの例での通信精度は、通信可能ならば１，通信不可能ならば０とした。
【０１３２】
１．２  行列演算による伝送精度計算
第ｉ成分のみが１で残りの成分が０であるようなＫ次元横ベクトルを単位ベクトルｅｊと呼ぶ：
【数３４】
0003905712.tif 000035
【０１３３】
また、第ｊ成分のみが１で残りの成分が０であるようなＫ次元縦ベクトルを単位ベクトルｆｊと呼ぶ：
【数３５】
0003905712.tif 000036
【０１３４】
これらの単位ベクトルと接続行列の演算を考える。Ｃ−接続行列に単位ベクトルｅｉを左から掛けると以下の結果が得られる。
【数３６】
0003905712.tif 000037
【０１３５】
ａｉｊ（ｊ＝１，２，…，Ｋ）はＲｉのｕｐ側とＲｊのｌｏｗ側間の通信精度を表す。また、ａｉ０はＲｉのｕｐ側と本部Ｃ間の通信精度を表す。従って、ベクトルｅｉＡＣはＲｉのｕｐ側と通信可能な装置との通信精度を表すベクトルとなっている。
【０１３６】
次に一般のＫ次元横ベクトルｕ＝（ｕ１，ｕ２，…，ｕＫ）とＣ−接続行列の演算を考える。
【数３７】
0003905712.tif 000038
なので、
【数３８】
0003905712.tif 000039
となる。ｅｉＡＣはＲｉのｕｐ側で通信可能な装置との通信精度を表すベクトルであった。ベクトルｕの第ｉ成分ｕｉがＲｉへの通信精度の総和、すなわち
【数３９】
0003905712.tif 000040
をあらわすとき、ベクトルｕｉｅｉＡＣの第ｋ成分は
【数４０】
0003905712.tif 000041
となり、Ｒｉへ精度の総和がｕｉで送られてきた情報を、Ｒｋへ伝送するときの通信精度の総和を表す。また、ベクトルｕｉｅｉＡＣの第０成分はＲｉへ精度の総和がｕｉで送られてきた情報を本部Ｃへ伝送するときの通信精度の総和を表す。従ってベクトル
【数４１】
0003905712.tif 000042
は、各中継車Ｒへ精度の総和がｕで送られてきた情報を、次の中継装置（または本部Ｃ）へ伝えるときの通信精度の総和を表すベクトルとなっている。
【０１３７】
以上を踏まえ、次の二つの線型写像ｆｕｐ，ｇｕｐを定義する。
写像ｆｕｐは、横ベクトルｕ∈ＲＫに対して、ベクトルｕＡＣの第０成分が対応する写像とする。式（１０）および式（１１）より、
【数４２】
0003905712.tif 000043
と表される。
【０１３８】
次に写像ｇｕｐは、横ベクトルｕ∈ＲＫに対して、ベクトルｕＡＣの第０成分を削除したベクトルが対応する写像とする。式（１０）および式（１１）より、
【数４３】
0003905712.tif 000044
と表される。
【０１３９】
写像ｆｕｐは精度の総和がｕで伝わった情報が、一回中継されて本部Ｃへ伝送されるときの通信精度の総和を与える。一方、写像ｇｕｐは、精度の総和がｕで伝わった情報が、一回中継されて他の中継車Ｒへ伝送されるときの通信精度の総和を表すベクトルを与える。
【０１４０】
特にベクトルｕとして、Ｓｊの接続ベクトルｓｊをとると、ｆｕｐ（ｓｊ）はＳｊから１個の中継車Ｒを介して各中継車Ｒへ情報を伝送する際の通信精度ベクトルを表す。同様に、ｇｕｐ（ｓｊ）はＳｊから１個の中継車Ｒを介して各中継車Ｒへ情報を伝送する際の通信精度ベクトルを表す。
このことから、ｆｋｕｐ（ｓｊ）はＳｊからｋ個の中継車Ｒを介して本部Ｃへ情報を伝送する際の通信精度を表し、ｇｋｕｐ（ｓｊ）はＳｊからｋ個の中継車Ｒを介して各中継車Ｒへ情報を伝送する際の通信精度ベクトルを表す。ただし、ｆｋｕｐおよびｇｋｕｐは、それぞれ写像ｆｕｐ，ｇｕｐのｋ乗を表す。またｆ０ｕｐは、観測車Ｓから直接本部Ｃへつながる経路はないものと仮定するので恒等的に０とし、ｇ０ｕｐは恒等写像を表すものとする。
【０１４１】
例２
図１６の例１の場合、写像ｆｕｐ，ｇｕｐの計算をすると以下のようになる。
【数４４】
0003905712.tif 000045
【０１４２】
これより
【数４５】
0003905712.tif 000046
【数４６】
0003905712.tif 000047
【０１４３】
この例では０−１変数を用いているので、得られた数値は通信精度ではなく伝送経路数を表す。上記結果より、観測車Ｓから１個の中継車Ｒを介して本部Ｃに至る経路が１本、１個の中継車Ｒを介してＲ４に至る経路が２本存在することが計算された。これは図１７の内容と一致する。
【０１４４】
さらに、
【数４７】
0003905712.tif 000048
であるから、
【数４８】
0003905712.tif 000049
【数４９】
0003905712.tif 000050
となり、観測車Ｓから２個の中継車Ｒを介して本部Ｃに至る経路は２本あり、２個の中継車Ｒを介して観測車Ｓと通信可能な中継車Ｒは存在しないことが計算される。これについても図１７の内容と一致する。
【０１４５】
上記の例２からわかるとおり、
【数５０】
0003905712.tif 000051
は、ＳｊからＮ回以下の中継を介して本部Ｃに情報を伝送する際の通信精度の総和を表す。また
【数５１】
0003905712.tif 000052
の第ｉ成分はＳｊからＮ回以下の中継を介してＲｉに情報を伝送する際の通信精度の総和を表す。中継車Ｒの総数がＫ以下で、伝送経路にループがない場合には、中継回数はＫ回以下なので、Ｎ＝Ｋとすれば
【数５２】
0003905712.tif 000053
はＳｊから本部Ｃへ至る全ての経路についての精度の総和であり、
【数５３】
0003905712.tif 000054
の第ｉ成分は、ＳｊからＲｉに至る全ての経路についての通信精度の総和を表すことになる。
【０１４６】
次に、Ｓ−接続行列に（縦）単位ベクトルｆｊを掛ける演算について考える。
【数５４】
0003905712.tif 000055
ａｉｊは、各中継車ＲからＲｊのｌｏｗ側へ情報を伝達する際の通信精度を表す。
【０１４７】
また、一般のＫ次元縦ベクトルｖ＝ｔ（ｖ１，…，ｖＫ）とＡｓの積は、
【数５５】
0003905712.tif 000056
であることから次式のようになる。
【数５６】
0003905712.tif 000057
【０１４８】
ｖｊが中継車Ｒを通る通信経路の、Ｒｊ以降の通信精度の総和を表すとすれば、ベクトルｖｊＡＳｆｊの第ｉ成分はｖｊａｉｊとなり、ＲｉまたはＳｉからＲｊを介して通信する場合の、通信精度の総和を表すことになる。
【０１４９】
以上を踏まえ、２つの線形写像ｆｌｏｗおよびｇｌｏｗを次のように定める。写像ｆｌｏｗは、（縦）Ｋ次元ベクトルｖ∈ＲＫに対して、ベクトルＡＳｖの第Ｋ＋１〜Ｋ＋１成分を並べたベクトルを対応させる写像とする。式（２０）および式（２１）より、
【数５７】
0003905712.tif 000058
となる。また、写像ｇｌｏｗは、Ｋ次元ベクトルｖ∈ＲＫに対して、ベクトルＡＳｖの第１〜Ｋ成分を並べたベクトルを対応させる写像とする。式（２０）および式（２１）より、
【数５８】
0003905712.tif 000059
表される。
【０１５０】
写像ｆｌｏｗは、観測車Ｓから発信された情報が、精度ｖの１回の中継を経て他に伝送される場合の通信精度の総和を表す。また、写像ｇｌｏｗは、各中継車Ｒから発信された情報が、精度ｖの１回の中継を経て他に伝送される場合の通信精度の総和を表す。
【０１５１】
特にｖとして本部Ｃの接続ベクトルｃをとると、ｆｌｏｗ（ｃ）は本部Ｃから１個の中継車Ｒを介して観測車Ｓへ情報を伝送する際の通信精度を表す。同様に、ｇｌｏｗ（ｃ）本部Ｃから１個の中継車Ｒを介して各中継車Ｒへ情報を伝送する際の通信精度ベクトルを表す。
【０１５２】
このことから、ｆｋｌｏｗ（ｃ）は本部Ｃからｋ個の中継車Ｒを介して観測車Ｓへ情報を伝送する際の通信精度を表し、ｇｋｌｏｗ（ｃ）は本部Ｃからｋ個の中継車Ｒを介して各中継車Ｒへ情報を伝送する際の通信精度ベクトルを表す。ただし、ｆｋｌｏｗおよびｇｋｌｏｗは、それぞれ写像ｆｌｏｗ、ｇｌｏｗのｋ乗を表す。また、ｆ０ｌｏｗは、観測車Ｓから直接本部Ｃへつながる経路はないものと仮定するので恒等的に０とし、ｇ０ｌｏｗは恒等写像を表すものとする。
【０１５３】
例３
再び図１６例１の場合、写像ｆｌｏｗ、ｇｌｏｗの計算をすると以下のようになる。
【数５９】
0003905712.tif 000060
【０１５４】
これより
【数６０】
0003905712.tif 000061
【数６１】
0003905712.tif 000062
【０１５５】
この例では０−１変数を用いているので、得られた数値は通信精度ではなく伝送経路数を表す。上記結果より、本部Ｃから１個の中継車Ｒを介して観測車Ｓに至る経路が１本、１個の中継車Ｒを介してＲ１およびＲ２に至る経路がそれぞれ１本ずつ存在することが計算された。これは図１８の内容と一致する。
【０１５６】
さらに、
【数６２】
0003905712.tif 000063
であるから、
【数６３】
0003905712.tif 000064
【数６４】
0003905712.tif 000065
となり、本部Ｃから２個の中継車Ｒを介して観測車Ｓに至る経路は２本あり、２個の中継車Ｒを介して本部Ｃと通信可能な中継車Ｒは存在しないことが計算される。これについても図１８の内容と一致する。
【０１５７】
上記の例３からわかるとおり、
【数６５】
0003905712.tif 000066
の第ｉ成分は、本部ＣからＮ回以下の中継を介してＳｉに情報を伝送する際の通信精度の総和を表す。また
【数６６】
0003905712.tif 000067
の第ｉ成分は本部ＣからＮ回以下の中継を介してＲｉに情報を伝送する際の通信精度の総和を表す。中継車Ｒの総数がＫ以下で、伝送経路にループがない場合には、中継回数はＫ回以下なので、Ｎ＝Ｋとすれば
【数６７】
0003905712.tif 000068
の第ｉ成分は、本部ＣからＳｉへ至る全ての経路についての精度の総和であり、
【数６８】
0003905712.tif 000069
の第ｉ成分は、本部ＣからＲｉに至る全ての経路についての通信精度の総和を表すことになる。
【０１５８】
以上の例２、例３より、
【数６９】
0003905712.tif 000070
の第ｉ成分を
【数７０】
0003905712.tif 000071
の第ｉ成分を
【数７１】
0003905712.tif 000072
と書くとき、Ｒｉを通り、Ｓｊと本部Ｃと結ぶ全ての通信経路の通信精度の総和は
【数７２】
0003905712.tif 000073
で与えられる。なお、接続行列を０−１で設定すれば、式（３０）はＲｉを通り、Ｓｉと本部Ｃをつなぐ経路の総数を与えることに注意する。
【０１５９】
例４
図１６の例１の場合、各中継車Ｒを通る経路数の計算は以下のようになる。
例２より、
【数７３】
0003905712.tif 000074
【数７４】
0003905712.tif 000075
【数７５】
0003905712.tif 000076
【数７６】
0003905712.tif 000077
である。これより、中継車Ｒ１〜４を通る経路数ベクトルで書くと（１，１，１，２）となる。これは図１９の内容一致する。
【０１６０】
また、経路総数については、
【数７７】
0003905712.tif 000078
となり、これについても図１９の内容と一致する。
【０１６１】
次に、行列計算による伝送能力計算の具体例について説明する。
［最重要中継車選択と評価関数計算のアルゴリズム］について、図８（ｂ）の方針に基づき具体的に説明する。ただし、伝送品質を０．９＝ａ、０．８＝ｂ、０．７＝ｃと記号表現し、ａ×ｂをａｂと表す。また、中継車を配置していない候補地はないものとして除いてある。
【０１６２】
【数７８】
0003905712.tif 000079
【０１６３】
【数７９】
0003905712.tif 000080
【０１６４】
【数８０】
0003905712.tif 000081
【０１６５】
【数８１】
0003905712.tif 000082
【０１６６】
【数８２】
0003905712.tif 000083
【０１６７】
【数８３】
0003905712.tif 000084
【０１６８】
【数８４】
0003905712.tif 000085
【０１６９】
【数８５】
0003905712.tif 000086
【０１７０】
【数８６】
0003905712.tif 000087
【０１７１】
【数８７】
0003905712.tif 000088
【０１７２】
【発明の効果】
本発明のネットワークシステムによれば、サーバの負荷を上昇させることなく、ユーザが任意の時間にデータを取得することができる。
【図面の簡単な説明】
【図１】図１は、本発明の一実施形態の通信経路の最適化方法において、観測車と対策本部を結ぶ中継車の配置の例を示す模式図である。
【図２】図２は、本発明の一実施形態の通信経路の最適化方法において、回避されるべき混信が発生する例を示す図である。
【図３】図３は、本発明の一実施形態の通信経路の最適化方法において、複数の通信経路が定義できる例を示す図である。
【図４】図４は、本発明の一実施形態の通信経路の最適化方法において、混信内容とその回避法を示す図である。
【図５】図５は、本発明の一実施形態の通信経路の最適化方法において、表現する記号をまとめた第１の図である。
【図６】図６は、本発明の一実施形態の通信経路の最適化方法において、表現する記号をまとめた第２の図である。
【図７】図７は、本発明の一実施形態の通信経路の最適化方法において、表現する記号をまとめた第３の図である。
【図８】図８（ａ）は、本発明の一実施形態の通信経路の最適化方法において、中継車の位置が固定された周波数割り当ての第１の例を示し、図８（ｂ）は、本発明の一実施形態の通信経路の最適化方法において、中継車の位置が固定された周波数割り当ての第２の例を示している。
【図９】図９は、本発明の一実施形態の通信経路の最適化方法において、図８（ａ）、（ｂ）のケースにおける評価値とロバスト性を示す図である。
【図１０】図１０は、本発明の一実施形態の通信経路の最適化方法において、解法の能力を評価するための検証が行われたときの基本条件を示す図である。
【図１１】図１１は、本発明の一実施形態の通信経路の最適化方法において、検証が行われたときの中継車の配置候補位置と初期配置、本部、観測車の配置例を示す図である。
【図１２】図１２は、本発明の一実施形態の通信経路の最適化方法において、検証が行われたときの選択された観測車と本部を結ぶ最も伝送品質の高い経路を示す図である。
【図１３】図１３は、図１２において、最も重要な中継車が使用不要になった場合の経路例を示す図である。
【図１４】図１４は、本発明の一実施形態の通信経路の最適化方法において、検証の際の繰り返し計算数が多いときの結果例を示す図である。
【図１５】図１５は、本発明の一実施形態の通信経路の最適化方法において、検証の際の本部と観測車の位置関係を変えたときの結果例を示す図である。
【図１６】図１６は、本発明の一実施形態の通信経路の最適化方法において、通信可能性の行列表示を説明するためのネットワークの一例を示す図である。
【図１７】図１７は、本発明の一実施形態の通信経路の最適化方法において、行列演算による伝送精度計算を説明するためのネットワークの一例を示す図である。
【図１８】図１８は、本発明の一実施形態の通信経路の最適化方法において、行列演算による伝送精度計算を説明するためのネットワークの他の例を示す図である。
【図１９】図１９は、本発明の一実施形態の通信経路の最適化方法において、行列演算による伝送精度計算を説明するためのネットワークの更に他の例を示す図である。
【符号の説明】
Ｒ１  中継車
Ｒ２  中継車
Ｒ３  中継車
Ｒ４  中継車
Ｒ５  中継車
Ｒ６  中継車
Ｓ１  観測車
Ｓ２  観測車
Ｓ３  観測車
Ｓ４  観測車
Ｃ  対策本部
Ｊ  最重要中継機
【図１】
0003905712.tif 000089
【図２】
0003905712.tif 000090
【図３】
0003905712.tif 000091
【図４】
0003905712.tif 000092
【図５】
0003905712.tif 000093
【図６】
0003905712.tif 000094
【図７】
0003905712.tif 000095
【図８】
0003905712.tif 000096
【図９】
0003905712.tif 000097
【図１０】
0003905712.tif 000098
【図１１】
0003905712.tif 000099
【図１２】
0003905712.tif 000100
【図１３】
0003905712.tif 000101
【図１４】
0003905712.tif 000102
【図１５】
0003905712.tif 000103
【図１６】
0003905712.tif 000104
【図１７】
0003905712.tif 000105
【図１８】
0003905712.tif 000106
【図１９】
0003905712.tif 000107