(57)【要約】【課題】  従来は無線通信装置間の相互中継によりネットワークの経路を設計する場合、ノードの位置が移動したり装置間の接続を無線により行うことにより、中継ノードの配置場所の設計が効率的に行えなかった。【解決手段】  この発明の経路設計装置５０は、フレームワーク処理部５３と囲い込み処理部７０との２段階の処理部によって、ノードの移動や無線でノード間を接続する場合であっても、効率的にサバイバブルネットワークの経路を設計する。フレームワーク処理部５３は、斜向座標グラフを生成して、グラフ上の座標点にノードを配置する。囲い込み処理部７０は、斜向座標グラフ上に配置したノードを多角形の周囲境界線で囲い込み、周囲境界線を移動させて囲い込む範囲を縮小し、さらに、縮退規則情報に従い仮想ノードを配置して、縮小した周囲境界線を縮退させる。縮退させた周囲境界線と仮想ノードの位置とノードの位置とから経路情報を生成して出力する。【選択図】        図３
2006101497.tif 000002
【特許請求の範囲】
【請求項１】
第１の無線通信装置と第２の無線通信装置との間のネットワーク経路を設計する経路設計装置において、
上記第１の無線通信装置と上記第２の無線通信装置の通信可能範囲を示す通信範囲情報を記憶する通信範囲情報記憶部と、
上記第１の無線通信装置の位置を示す第１の位置情報と上記第２の無線通信装置の位置を示す第２の位置情報とを入力する位置情報入力部と、
上記通信範囲情報記憶部が記憶する通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する斜向座標生成部と、
上記位置情報入力部が入力した第１の位置情報と上記第２の位置情報とのそれぞれに対応する上記斜向座標生成部が生成した斜向座標グラフ上の第１の座標点と第２の座標点とを求めて、求めた上記第１の座標点と第２の座標点とを上記斜向座標グラフ上に配置するとともに、配置した第１の座標点と第２の座標点とを囲い込む周囲境界線を上記斜向座標グラフ上に生成する配置処理部と、
上記配置処理部が斜向座標グラフ上に生成した周囲境界線を周囲境界線の内側に移動して上記第１の座標点と第２の座標点とを囲い込む範囲を縮小した縮小周囲境界線を上記斜向座標グラフ上に生成する周囲境界縮小部と、
周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を記憶する縮退規則情報記憶部と、
上記縮退規則情報記憶部が記憶する縮退規則情報に従い、上記周囲境界縮小部が上記斜向座標グラフ上に生成した縮小周囲境界線の内側に上記仮想通信装置を配置して配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記斜向座標グラフ上に生成する境界縮退部と、
上記境界縮退部が上記斜向座標グラフ上に生成した縮退周囲境界線と、上記第１の座標点と上記第２の座標点と、上記境界縮退部が配置した仮想通信装置の斜向座標グラフ上の位置とから上記ネットワーク経路を設計して経路設計情報を生成して出力する経路設計部と
を備えたことを特徴とする経路設計装置。
【請求項２】
自己と他の無線通信装置との間のネットワーク経路を設計する経路設計装置において、
自己と上記他の無線通信装置の通信可能範囲を示す通信範囲情報を記憶する通信範囲情報記憶部と、
測位信号情報を受信して自己の位置を示す第１の位置情報を算出する受信位置算出部と、
上記他の無線通信装置の位置を示す第２の位置情報を入力する位置情報入力部と、
上記通信範囲情報記憶部が記憶する通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する斜向座標生成部と、
上記受信位置算出部が算出した第１の位置情報と上記位置情報入力部が入力した第２の位置情報とのそれぞれに対応する上記斜向座標生成部が生成した斜向座標グラフ上の第１の座標点と第２の座標点とを求めて、求めた上記第１の座標点と第２の座標点とを上記斜向座標グラフ上に配置するとともに、配置した第１の座標点と第２の座標点とを囲い込む周囲境界線を上記斜向座標グラフ上に生成する配置処理部と、
上記配置処理部が斜向座標グラフ上に生成した周囲境界線を周囲境界線の内側に移動して、上記第１の座標点と第２の座標点とを囲い込む範囲を縮小した縮小周囲境界線を上記斜向座標グラフ上に生成する周囲境界縮小部と、
周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を記憶する縮退規則情報記憶部と、
上記縮退規則情報記憶部が記憶する縮退規則情報に従い、上記周囲境界縮小部が上記斜向座標グラフ上に生成した縮小周囲境界線の内側に上記仮想通信装置を配置して配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記斜向座標グラフ上に生成する境界縮退部と、
上記境界縮退部が上記斜向座標グラフ上に生成した縮退周囲境界線と、上記第１の座標点と上記第２の座標点と、上記境界縮退部が配置した仮想通信装置の斜向座標グラフ上の位置とから上記ネットワーク経路を設計して経路設計情報を生成して出力する経路設計部と
を備えたことを特徴とする経路設計装置。
【請求項３】
上記縮小周囲境界線は、複数の辺を有し、
上記周囲境界縮小部は、上記第１の座標点と第２の座標点との少なくともいずれか一方の座標点が上記縮小周囲境界線上に配置されるように上記縮小周囲境界線を生成し、
上記縮退規則情報記憶部は、上記縮退規則情報として、上記縮小周囲境界線の複数の辺のうち上記第１の座標点と第２の座標点とが配置されている辺については上記縮小周囲境界線を縮退しないことを示す情報と、上記縮小周囲境界線の複数の辺のうち上記第１の座標点と第２の座標点とのいずれか一方の座標点が配置されている辺については辺上の座標点の内側に２つの仮想通信装置を配置して、配置した２つの仮想通信装置と上記辺上の座標点とを結ぶ縮退周囲境界線を生成することを示す情報とを記憶することを特徴とする請求項１または２記載の経路設計装置。
【請求項４】
上記斜向座標グラフは、三角メッシュと四角メッシュと六角メッシュとのいずれかに対応する斜向座標のグラフであることを特徴とする請求項１または２記載の経路設計装置。
【請求項５】
上記第１の位置情報と第２の位置情報とはそれぞれ、所定の電波強度を有する電波信号であり、
上記位置情報入力部は、上記第１の位置情報と第２の位置情報の少なくともいずれか一方の電波信号の強度を測定する電波強度測定部を備え、
上記通信範囲情報記憶部は、上記通信範囲情報を電波強度に対応させて記憶し、
上記斜向座標生成部は、上記電波強度測定部が測定した電波信号の強度に対応する通信範囲情報を上記通信範囲情報記憶部から取得し、取得した通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する
ことを特徴とする請求項１記載の経路設計装置。
【請求項６】
上記第１の位置情報と第２の位置情報との少なくともいずれか一方は、位置情報を出力した無線通信装置の種類情報を有し、
上記通信範囲情報記憶部は、上記通信範囲情報を無線通信装置の種類情報に対応させて記憶し、
上記斜向座標生成部は、上記第１の位置情報と第２の位置情報との少なくともいずれか一方の位置情報の有する種類情報に対応する通信範囲情報を上記通信範囲情報記憶部から取得し、取得した通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する
ことを特徴とする請求項１記載の経路設計装置。
【請求項７】
上記第１の位置情報と第２の位置情報との少なくともいずれか一方は、時刻を示す時刻情報を有し、
上記通信範囲情報記憶部は、上記通信範囲情報を時刻情報に対応させて記憶し、
上記斜向座標生成部は、上記第１の位置情報と第２の位置情報との少なくともいずれか一方の位置情報の有する時刻情報に対応する通信範囲情報を上記通信範囲情報記憶部から取得し、取得した通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する
ことを特徴とする請求項１記載の経路設計装置。
【請求項８】
第１の無線通信装置と第２の無線通信装置との間のネットワーク経路を設計する経路設計方法において、
上記第１の無線通信装置と上記第２の無線通信装置の通信可能範囲を示す通信範囲情報を通信範囲情報記憶部に記憶する通信範囲情報記憶工程と、
上記第１の無線通信装置の位置を示す第１の位置情報と上記第２の無線通信装置の位置を示す第２の位置情報とを入力する位置情報入力工程と、
上記通信範囲情報記憶工程により記憶された通信範囲情報を上記通信範囲情報記憶部から取り出し、取り出した通信可能範囲を一目盛とする斜向座標グラフを生成する斜向座標生成工程と、
上記位置情報入力工程により入力された第１の位置情報と上記第２の位置情報とのそれぞれに対応する上記斜向座標生成工程により生成された斜向座標グラフ上の第１の座標点と第２の座標点とを求めて、求めた上記第１の座標点と第２の座標点とを上記斜向座標グラフ上に配置するとともに、配置した第１の座標点と第２の座標点とを囲い込む周囲境界線を上記斜向座標グラフ上に生成する配置処理工程と、
上記配置処理工程により斜向座標グラフ上に生成された周囲境界線を周囲境界線の内側に移動して、上記第１の座標点と第２の座標点とを囲い込む範囲を縮小した縮小周囲境界線を上記斜向座標グラフ上に生成する周囲境界縮小工程と、
周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を縮退規則情報記憶部に記憶する縮退規則情報記憶工程と、
上記縮退規則情報記憶工程により記憶された縮退規則情報を上記縮退規則情報記憶部から取得し、取得した縮退規則情報に従い上記周囲境界縮小工程により上記斜向座標グラフ上に生成された縮小周囲境界線の内側に上記仮想通信装置を配置して配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記斜向座標グラフ上に生成する境界縮退工程と、
上記境界縮退工程により上記斜向座標グラフ上に生成された縮退周囲境界線と、上記第１の座標点と、上記第２の座標点と、上記境界縮退工程により配置された仮想通信装置の上記斜向座標グラフ上の位置とから上記ネットワーク経路を設計して経路設計情報を生成して出力する経路設計工程と
を有することを特徴とする経路設計方法。
【請求項９】
第１の通信可能範囲をそれぞれ有する複数の無線通信装置間の接続を上記第１の通信可能範囲とは異なる第２の通信可能範囲を有する１つ以上の無線通信装置を介して行うネットワーク経路を設定する経路設計装置において、
上記第１の無線可能範囲を示す第１の通信範囲情報と、上記第２の無線可能範囲を示す第２の通信範囲情報とを記憶する通信範囲情報記憶部と、
上記第１の通信可能範囲をそれぞれ有する複数の無線通信装置から、各無線通信装置の位置を示す緯度情報と経度情報とを有する位置情報を入力する位置情報入力部と、
上記通信範囲情報記憶部が記憶する第１の通信範囲情報の示す通信可能範囲を多角形で表し、多角形の辺を共有させて多角形を隣接させて複数配置し、配置した複数の多角形の中心点同士を上記共有する辺を通過する線で結んで、上記複数の多角形の中心点ごとに中心点を通過する上記線を複数生成して、上記複数の多角形の中心点うち１つの中心点をグラフの原点として選択するとともに、選択した原点を通過する複数の線のうちｘ軸とする線とｙ軸とする線とをそれぞれ選択して、ｘ軸に経度を距離に変換した値を示し、ｙ軸に緯度を距離に変換した値を示した第１のグラフを生成する第１のグラフ生成部と、
上記通信範囲情報記憶部が記憶する第２の通信範囲情報の示す通信可能範囲を多角形で表し、多角形の辺を共有させて多角形を隣接させて複数配置し、配置した複数の多角形の中心点同士を上記共有する辺を通過する線で結んで、上記複数の多角形の中心点ごとに中心点を通過する上記線を複数生成して、上記複数の多角形の中心点うち１つの中心点をグラフの原点として選択するとともに、選択した原点を通過する複数の線のうちｘ軸とする線とｙ軸とする線とをそれぞれ選択して、ｘ軸に経度を距離に変換した値を示し、ｙ軸に緯度を距離に変換した値を示した第２のグラフを生成する第２のグラフ生成部と、
上記位置情報入力部が入力した複数の無線通信装置の各無線通信装置の位置情報に基づいて複数の無線通信装置毎の経度情報を距離に変換した値と緯度情報を距離に変換した値とを求め、求めた複数の無線通信装置毎の値から複数の無線通信装置毎の上記第１のグラフ上の各座標点を求めて、求めた各座標点を上記第１のグラフ上に配置する第１の配置処理部と、
上記第１の配置処理部が配置した第１のグラフ上の複数の座標点を所定の条件に基づいて分類して複数の座標点を含むクラスタを複数生成して、生成した複数のクラスタに含まれる複数の座標点を囲い込む周囲境界線を上記第１のグラフ上に生成するクラスタ生成部と、
上記クラスタ生成部が第１のグラフ上に生成した周囲境界線と第１のグラフと、上記第２のグラフ生成部が生成した第２のグラフとを入力して、入力した第１のグラフ上の複数のクラスタのうち１つのクラスタを選択して、選択したクラスタの周囲境界線の取り囲む範囲内に第２のグラフ上の原点が配置されるように上記第１のグラフに対して第２のグラフを配置して、配置した第２のグラフ上に上記選択したクラスタ以外の他のクラスタの周囲境界線を投射して、投射した各クラスタ毎に周囲境界線の取り囲む範囲に近い上記第２のグラフ上の多角形の中心点を各クラスタ毎に対応させ、各クラスタ毎に対応させた多角形の中心点と上記原点の座標点とを各クラスタに対応する上記第２の通信可能範囲を有する無線通信装置を配置する座標点として、これらの座標点を囲い込む周囲境界線を上記第２のグラフ上に生成する第２の配置処理部と、
上記クラスタ生成部が第１のグラフ上に生成したクラスタ毎の周囲境界線を周囲境界線の内側に移動して周囲境界線が囲い込む範囲を縮小したクラスタ毎の縮小周囲境界線を生成するとともに、上記第２の配置処理部が第２のグラフ上に生成した周囲境界線を周囲境界線の内側に移動して周囲境界線が囲い込む範囲を縮小した第２のグラフ上の縮小周囲境界線を生成する周囲境界縮小部と、
クラスタ毎の縮小周囲境界線と第２のグラフ上の縮小周囲境界線とのそれぞれの縮小周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を記憶する縮退規則情報記憶部と、
上記縮退規則情報記憶部が記憶した縮退規則情報に従い、上記周囲境界縮小部が生成した第１のグラフ上のクラスタ毎の縮小周囲境界線の内側に仮想通信装置を配置して、配置した仮想通信装置を通過するようにクラスタ毎の縮小周囲境界線を縮退してクラスタ毎の縮退周囲境界線を上記第１のグラフ上に生成するとともに、上記縮退規則情報記憶部が記憶した縮退規則情報に従い、上記周囲境界縮小部が生成した第２のグラフ上の縮小周囲境界線の内側に仮想通信装置を配置して、配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記第２のグラフ上に生成する境界縮退部と、
上記境界縮退部が上記第１のグラフ上に生成したクラスタ毎の縮退周囲境界線と、各クラスタに含まれる複数の座標点と、上記境界縮退部が第１のグラフ上に配置した仮想通信装置の座標点とを有するクラスタ毎の経路設計情報を生成するとともに、上記境界縮退部が上記第２のグラフ上に生成した縮退周囲境界線と、上記第２の配置処理部が決定したクラスタ毎の第２の通信可能範囲を有する無線通信装置を配置する座標点と、上記境界縮退部が第２のグラフ上に配置した仮想通信装置の座標点とを有する第２の通信可能範囲を有する無線通信装置の経路設計情報を生成する第１の経路設計部と、
上記第１の経路設計部が生成したクラスタ毎の経路設計情報が有する各クラスタに含まれる複数の座標点のうち２つの座標点を選択して、選択した２つの座標点それぞれと、上記第１の経路設計部が生成した第２の通信可能範囲を有する無線通信装置の経路設計情報が有するクラスタ毎の第２の通信可能範囲を有する無線通信装置を配置する座標点とを接続する経路情報を、各クラスタ毎に生成して、生成した経路情報と、上記第１の経路設計部が生成したクラスタ毎の経路設計情報と、上記第１の経路設計部が生成した第２の通信可能範囲を有する無線通信装置の経路設計情報とに基づいて各クラスタ間を第２の通信可能範囲を有する無線通信装置を介して接続するネットワーク経路情報を生成して出力する第２の経路設計部と
を備えたことを特徴とする経路設計装置。
【請求項１０】
上記第２の配置処理部は、上記第２のグラフの面を上記第１のグラフの面に対して垂直方向に所定の高さを有して平行に配置し、
上記第２の通信可能範囲を有する無線通信装置は、飛行体に搭載された通信局である
ことを特徴とする請求項９記載の経路設計装置。
【請求項１１】
上記第２の配置処理部は、上記第１のグラフの面に対して上記第２のグラフの面を上記第２の通信可能範囲分の距離を有して同一平面上に配置し、
上記第２の通信可能範囲を有する無線通信装置は、地上局である
ことを特徴とする請求項９記載の経路設計装置。
【請求項１２】
上記クラスタ生成部は、上記第１のグラフ上の複数の座標点を複数のクラスタに分類する条件として上記第１の通信可能範囲を１ホップとした場合のホップ数を記憶する分類条件記憶部と、
上記第１のグラフ上の複数の座標点毎に座標点を中心として中心から上記分類条件記憶部が記憶するホップ数の距離を有するエリアを上記第１のグラフ上に複数生成するエリア生成部と、
上記エリア生成部が生成した複数のエリアのうち隣接するエリアを同一のクラスタにして、上記第１の斜向グラフ上に生成した複数のエリアを複数のクラスタに分類するエリア分類部と
を備えることを特徴とする請求項９記載の経路設計装置。
【請求項１３】
上記クラスタ毎の縮小周囲境界線と上記第２のグラフ上の縮小周囲境界線とはそれぞれ、複数の辺を有し、
上記周囲境界縮小部は、上記クラスタ毎の縮小周囲境界線を生成する場合は、クラスタ毎に各クラスタに含まれる複数の座標点のうち少なくとも１つの座標点が上記縮小周囲境界線上に配置されるように上記縮小周囲境界線を生成し、上記第２のグラフ上の縮小周囲境界線を生成する場合は、上記第２の通信可能範囲を有する無線通信装置を配置する複数の座標点のうち少なくとも１つの座標点が上記縮小周囲境界線上に配置されるように上記縮小周囲境界線を生成し、
上記縮退規則情報記憶部は、上記縮退規則情報として、上記縮小周囲境界線の複数の辺のうち上記第１の通信可能範囲を有する無線通信装置を配置する座標点が複数配置されている辺と、上記第２の通信可能範囲を有する無線通信装置を配置する座標点が複数配置されている辺については、上記縮小周囲境界線を縮退しないことを示す情報と、上記縮小周囲境界線の複数の辺のうち上記第１の通信可能範囲を有する無線通信装置を配置する座標点が１つ配置されている辺と、上記第２の通信可能範囲を有する無線通信装置を配置する座標点が１つ配置されている辺については、辺上の座標点の内側に２つの仮想通信装置を配置して、配置した２つの仮想通信装置と上記辺上の座標点とを結ぶ縮退周囲境界線を生成することを示す情報とを記憶することを特徴とする請求項９記載の経路設計装置。
【請求項１４】
上記第１の通信範囲情報の示す通信可能範囲を表した多角形と、上記第２の通信範囲情報の示す通信可能範囲を表した多角形とは、六角形と四角形とのいずれかであることを特徴とする請求項９記載の経路設計装置。
【請求項１５】
上記位置情報入力部が入力する各無線装置の位置情報のうち少なくとも１つの位置情報は、時刻を示す時刻情報を有し、
上記通信範囲情報記憶部は、上記第１の通信範囲情報を時刻情報に対応させて記憶し、
上記第１のグラフ生成部は、上記位置情報の有する時刻情報に対応する第１の通信範囲情報を上記通信範囲情報記憶部から取得し、取得した第１の通信範囲情報の示す通信可能範囲を一目盛とする第１のグラフを生成する
ことを特徴とする請求項９記載の経路設計装置。
【請求項１６】
上記第２の配置処理部は、上記第２のグラフ上の複数の多角形の中心点ごとに各中心点を通過する複数の線が交差する点を頂点として、上記投射した周囲境界線の取り囲む範囲に上記第２のグラフ上の頂点が含まれないクラスタがある場合、上記投射したクラスタの周囲境界線の取り囲む範囲の中心点を求めて、求めた中心点に最も近い上記第２のグラフ上の多角形の中心点から上記投射したクラスタの周囲境界線の取り囲む範囲の中心点までの距離を、すべての投射したクラスタについて求め、求めた距離に基づいて全クラスタの平均を求め、求めた平均とクラスタ毎に求めた上記距離との差が一番大きいクラスタを選択して、選択したクラスタの周囲境界線の取り囲む範囲の中心点とその中心点に最も近い上記第２のグラフ上の多角形の中心点までの距離が上記平均に近くなるように上記第２のグラフの原点の上記第１のグラフに対する位置を移動して、選択したクラスタの周囲境界線の取り囲む範囲の中心点とその中心点に最も近い上記第２のグラフ上の多角形の中心点までの距離を調整する調整部を備える
ことを特徴とする請求項９記載の経路設計装置。
【請求項１７】
第１の通信可能範囲をそれぞれ有する複数の無線通信装置間の接続を上記第１の通信可能範囲とは異なる第２の通信可能範囲を有する１つ以上の無線通信装置を介して行うネットワーク経路を設定する経路設計装置の経路設計方法において、
上記第１の無線可能範囲を示す第１の通信範囲情報と、上記第２の無線可能範囲を示す第２の通信範囲情報とを通信範囲情報記憶部に記憶する通信範囲情報記憶工程と、
上記第１の通信可能範囲をそれぞれ有する複数の無線通信装置から、各無線通信装置の位置を示す緯度情報と経度情報とを有する位置情報を入力する位置情報入力工程と、
上記通信範囲情報記憶工程により通信範囲情報記憶部に記憶した第１の通信範囲情報の示す通信可能範囲を多角形で表し、多角形の辺を共有させて多角形を隣接させて複数配置し、配置した複数の多角形の中心点同士を上記共有する辺を通過する線で結んで、上記複数の多角形の中心点ごとに中心点を通過する上記線を複数生成して、上記複数の多角形の中心点うち１つの中心点をグラフの原点として選択するとともに、選択した原点を通過する複数の線のうちｘ軸とする線とｙ軸とする線とをそれぞれ選択して、ｘ軸に経度を距離に変換した値を示し、ｙ軸に緯度を距離に変換した値を示した第１のグラフを生成する第１のグラフ生成工程と、
上記通信範囲情報記憶工程により通信範囲情報記憶部に記憶した第２の通信範囲情報の示す通信可能範囲を多角形で表し、多角形の辺を共有させて多角形を隣接させて複数配置し、配置した複数の多角形の中心点同士を上記共有する辺を通過する線で結んで、上記複数の多角形の中心点ごとに中心点を通過する上記線を複数生成して、上記複数の多角形の中心点うち１つの中心点をグラフの原点として選択するとともに、選択した原点を通過する複数の線のうちｘ軸とする線とｙ軸とする線とをそれぞれ選択して、ｘ軸に経度を距離に変換した値を示し、ｙ軸に緯度を距離に変換した値を示した第２のグラフを生成する第２のグラフ生成工程と、
上記位置情報入力工程により入力した複数の無線通信装置の各無線通信装置の位置情報に基づいて複数の無線通信装置毎の経度情報を距離に変換した値と緯度情報を距離に変換した値とを求め、求めた複数の無線通信装置毎の値から複数の無線通信装置毎の上記第１のグラフ上の各座標点を求めて、求めた各座標点を上記第１のグラフ上に配置する第１の配置処理工程と、
上記第１の配置処理工程により配置した第１のグラフ上の複数の座標点を所定の条件に基づいて分類して複数の座標点を含むクラスタを複数生成して、生成した複数のクラスタに含まれる複数の座標点を囲い込む周囲境界線を上記第１のグラフ上に生成するクラスタ生成工程と、
上記クラスタ生成工程により第１のグラフ上に生成した周囲境界線と第１のグラフと、上記第２のグラフ生成工程により生成した第２のグラフとを入力して、入力した第１のグラフ上の複数のクラスタのうち１つのクラスタを選択して、選択したクラスタの周囲境界線の取り囲む範囲内に第２のグラフ上の原点が配置されるように上記第１のグラフに対して第２のグラフを配置して、配置した第２のグラフ上に上記選択したクラスタ以外の他のクラスタの周囲境界線を投射して、投射した各クラスタ毎に周囲境界線の取り囲む範囲に近い上記第２のグラフ上の多角形の中心点を各クラスタ毎に対応させ、各クラスタ毎に対応させた多角形の中心点と上記原点の座標点とを各クラスタに対応する上記第２の通信可能範囲を有する無線通信装置を配置する座標点として、これらの座標点を囲い込む周囲境界線を上記第２のグラフ上に生成する第２の配置処理工程と、
上記クラスタ生成工程により第１のグラフ上に生成したクラスタ毎の周囲境界線を周囲境界線の内側に移動して周囲境界線が囲い込む範囲を縮小したクラスタ毎の縮小周囲境界線を生成するとともに、上記第２の配置処理工程により第２のグラフ上に生成した周囲境界線を周囲境界線の内側に移動して周囲境界線が囲い込む範囲を縮小した第２のグラフ上の縮小周囲境界線を生成する周囲境界縮小工程と、
クラスタ毎の縮小周囲境界線と第２のグラフ上の縮小周囲境界線とのそれぞれの縮小周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を縮退規則情報記憶部に記憶する縮退規則情報記憶工程と、
上記縮退規則情報記憶工程により縮退規則情報記憶部が記憶した縮退規則情報に従い、上記周囲境界縮小工程により生成した第１のグラフ上のクラスタ毎の縮小周囲境界線の内側に仮想通信装置を配置して、配置した仮想通信装置を通過するようにクラスタ毎の縮小周囲境界線を縮退してクラスタ毎の縮退周囲境界線を上記第１のグラフ上に生成するとともに、上記縮退規則情報記憶工程により縮退規則情報記憶部に記憶した縮退規則情報に従い、上記周囲境界縮小工程により生成した第２のグラフ上の縮小周囲境界線の内側に仮想通信装置を配置して、配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記第２のグラフ上に生成する境界縮退工程と、
上記境界縮退工程により上記第１のグラフ上に生成したクラスタ毎の縮退周囲境界線と、各クラスタに含まれる複数の座標点と、上記境界縮退工程により第１のグラフ上に配置した仮想通信装置の座標点とを有するクラスタ毎の経路設計情報を生成するとともに、上記境界縮退工程により上記第２のグラフ上に生成した縮退周囲境界線と、上記第２の配置処理工程により決定したクラスタ毎の第２の通信可能範囲を有する無線通信装置を配置する座標点と、上記境界縮退工程により第２のグラフ上に配置した仮想通信装置の座標点とを有する第２の通信可能範囲を有する無線通信装置の経路設計情報を生成する第１の経路設計工程と、
上記第１の経路設計工程により生成したクラスタ毎の経路設計情報が有する各クラスタに含まれる複数の座標点のうち２つの座標点を選択して、選択した２つの座標点それぞれと、上記第１の経路設計工程により生成した第２の通信可能範囲を有する無線通信装置の経路設計情報が有するクラスタ毎の第２の通信可能範囲を有する無線通信装置を配置する座標点とを接続する経路情報を、各クラスタ毎に生成して、生成した経路情報と、上記第１の経路設計工程により生成したクラスタ毎の経路設計情報と、上記第１の経路設計工程により生成した第２の通信可能範囲を有する無線通信装置の経路設計情報とに基づいて各クラスタ間を第２の通信可能範囲を有する無線通信装置を介して接続するネットワーク経路情報を生成して出力する第２の経路設計工程と
を有することを特徴とする経路設計方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、基地局等の固定設備を持たず、移動無線通信装置間の相互中継によりネットワークを構築するアドホックネットワークの設計において、障害発生、電波状況の変化等により、通信装置あるいは装置間リンクが使用できなくなった場合にも通信を維持するための冗長経路を設計する経路設計装置及び経路設計方法に関するものである。
【背景技術】
【０００２】
固定の光通信ネットワークにおいて、サバイバビリティ（障害発生時にもサービスを提供する機能）を確保して障害発生時にもサービスを維持する方法として、特開２００２−３３５１９２号公報の「作業回路から保護回路への高速保護切換を可能にする方法」があった。また、固定局無しで、移動無線通信装置でアドホックネットワークを構築する方法として、特開２００３−３２４４４７号公報の「ブルートゥースオンデマンドルーティング及びネットワーク形成方法、並びにブルートゥースグループアドホックネットワークにおける通信方法」があった。しかし、アドホックネットワークのサバイバビリティを確保する方法はなかった。
【０００３】
例えば、特開２００２−３３５１９２号公報には、有線通信におけるサバイバルネットワークの設計方法が記載されている。この特開２００２−３３５１９２号公報に記載された発明では、ネットワークを構成するノード（通信装置）やリンク（通信経路）が与えられた場合に、複数の独立経路（「独立経路」とは、発信ノードと宛先ノードとの間を中継するノードを他の通信経路で共有しないことを指す）を効率よく発見して、障害発生時には効率よく通信経路を切り替える。
【０００４】
また、例えば、広域にわたって配置するノード間のコネクティビティ（接続性）を確保して通信を行なうために、航空機などの飛行体により中継を行なう方法がある。この方法の一例として「Ｋ．  Ｃｈａｎｄｒａｓｈｅｋａｒ，  Ｍ．  Ｒ．  Ｄｅｋｈｏｒｄｉ，  Ｊ．  Ｓ．  Ｂａｒａｓ著「Ｐｒｏｖｉｄｉｎｇ  ｆｕｌｌ  ｃｏｎｎｅｃｔｉｖｉｔｙ  ｉｎ  ｌａｒｇｅ  ａｄ−ｈｏｃ  ｎｅｔｗｏｒｋｓ  ｂｙ  ｄｙｎａｍｉｃ  ｐｌａｃｅｍｅｎｔ  ｏｆ  ａｅｒｉａｌ  ｐｌａｔｆｏｒｍｓ」ＩＥＥＥ  ＭＩＬＣＯＭ  ２００４，（２００４年１０月）」がある。
【０００５】
また、同様の方法として、「Ｐ．  Ｂａｓｕ，  Ｊ．  Ｒａｄｉ，  Ｖ．  Ｓｈｕｒｂａｎｏｖ著  「Ｃｏｏｒｄｉｎａｔｅｄ  ｆｌｏｃｋｉｎｇ  ｏｆ  ＵＡＶｓ  ｆｏｒ  ｉｍｐｒｏｖｅｄ  ｃｏｎｎｅｃｔｉｖｉｔｙ  ｏｆ  ｍｏｂｉｌｅ  ｇｒｏｕｎｄ  ｎｏｄｅｓ」ＩＥＥＥ  ＭＩＬＣＯＭ  ２００４，（２００４年１０月）」がある。これらの方法は、ノード間のコネクティビティ（接続性）を確保し、ノード間を接続する経路が一個は存在するように経路設計を行なうが、障害時の冗長経路の提供はしなかった。
【特許文献１】特開２００２−３３５１９２号公報
【特許文献２】特開２００３−３２４４４７号公報
【非特許文献１】「Ｋ．  Ｃｈａｎｄｒａｓｈｅｋａｒ，  Ｍ．  Ｒ．  Ｄｅｋｈｏｒｄｉ，  Ｊ．  Ｓ．  Ｂａｒａｓ著「Ｐｒｏｖｉｄｉｎｇ  ｆｕｌｌ  ｃｏｎｎｅｃｔｉｖｉｔｙ  ｉｎ  ｌａｒｇｅ  ａｄ−ｈｏｃ  ｎｅｔｗｏｒｋｓ  ｂｙ  ｄｙｎａｍｉｃ  ｐｌａｃｅｍｅｎｔ  ｏｆ  ａｅｒｉａｌ  ｐｌａｔｆｏｒｍｓ」ＩＥＥＥ  ＭＩＬＣＯＭ  ２００４，（２００４年１０月）」
【非特許文献２】「Ｐ．  Ｂａｓｕ，  Ｊ．  Ｒａｄｉ，  Ｖ．  Ｓｈｕｒｂａｎｏｖ著  「Ｃｏｏｒｄｉｎａｔｅｄ  ｆｌｏｃｋｉｎｇ  ｏｆ  ＵＡＶｓ  ｆｏｒ  ｉｍｐｒｏｖｅｄ  ｃｏｎｎｅｃｔｉｖｉｔｙ  ｏｆ  ｍｏｂｉｌｅ  ｇｒｏｕｎｄ  ｎｏｄｅｓ」ＩＥＥＥ  ＭＩＬＣＯＭ  ２００４，（２００４年１０月）」
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところが、基地局等の固定の通信設備を持たず、移動無線通信装置間の相互中継によりネットワークを構築するアドホックネットワークでは、ネットワークを構成するノードの位置が移動する。また、リンクは有線ケーブルではなく不安定な無線接続である。このため、従来の手法を適用することが困難である。また、発信ノードから宛先ノードまで直接電波が到達せず、間に中継ノードを設定する必要がある場合、例えばノードの位置が移動したり無線電波の届き方が一定でないなどの不定の事柄が多すぎて、従来の発明では、どこに中継ノードを設定し、どのように通信経路を設計すればよいのか等の解を、効率的に与えることができなかった。
【０００７】
また、従来の航空機などの飛行体により中継を行なう方法による接続性（コネクティビティ）確保の方法は、地上ノード間の経路、飛行体ノード間の経路ともに、一本の経路（無線通信における経路）を確保するもので、これらに障害が発生した場合の冗長性はなかった。
【０００８】
この発明は上記のような問題点を解決するためになされたもので、基地局等の固定の通信設備を持たず、移動無線通信装置間の相互中継によりネットワークを構築するアドホックネットワークにおいて、複数の独立経路を設計し、サバイバビリティを確保することを目的とする。
【０００９】
また、この発明は上記のような問題点を解決するためになされたもので、広域にわたって配置するノード間のコネクティビティ（接続性）を確保して通信を行なうために、航空機などの飛行体により中継を行なう場合に、一個の通信経路を確保するだけでなく、複数の独立経路を設計し、サバイバビリティを確保することを目的とする。
【課題を解決するための手段】
【００１０】
この発明に係る第１の無線通信装置と第２の無線通信装置との間のネットワーク経路を設計する経路設計装置は、上記第１の無線通信装置と上記第２の無線通信装置の通信可能範囲を示す通信範囲情報を記憶する通信範囲情報記憶部と、
上記第１の無線通信装置の位置を示す第１の位置情報と上記第２の無線通信装置の位置を示す第２の位置情報とを入力する位置情報入力部と、上記通信範囲情報記憶部が記憶する通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する斜向座標生成部と、上記位置情報入力部が入力した第１の位置情報と上記第２の位置情報とのそれぞれに対応する上記斜向座標生成部が生成した斜向座標グラフ上の第１の座標点と第２の座標点とを求めて、求めた上記第１の座標点と第２の座標点とを上記斜向座標グラフ上に配置するとともに、配置した第１の座標点と第２の座標点とを囲い込む周囲境界線を上記斜向座標グラフ上に生成する配置処理部と、上記配置処理部が斜向座標グラフ上に生成した周囲境界線を周囲境界線の内側に移動して上記第１の座標点と第２の座標点とを囲い込む範囲を縮小した縮小周囲境界線を上記斜向座標グラフ上に生成する周囲境界縮小部と、周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を記憶する縮退規則情報記憶部と、上記縮退規則情報記憶部が記憶する縮退規則情報に従い、上記周囲境界縮小部が上記斜向座標グラフ上に生成した縮小周囲境界線の内側に上記仮想通信装置を配置して配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記斜向座標グラフ上に生成する境界縮退部と、上記境界縮退部が上記斜向座標グラフ上に生成した縮退周囲境界線と、上記第１の座標点と上記第２の座標点と、上記境界縮退部が配置した仮想通信装置の斜向座標グラフ上の位置とから上記ネットワーク経路を設計して経路設計情報を生成して出力する経路設計部とを備えたことを特徴とする。
【発明の効果】
【００１１】
この発明の経路設計装置は、斜向座標グラフによるネットワーク設計フレームワークを用いることにより、ノード（ネットワークを構成する通信装置）が移動し、リンク（通信経路）が定まっていない場合でも、ノードを接続する複数の通信経路、および発信ノードと宛先ノードとを中継する中継ノードの位置と設置台数を設計できるという効果がある。
【００１２】
また、厳密に最適経路を求めるためには、全ノードの組み合わせを検証する膨大な処理を必要とするネットワーク設計であるが、縮退規則情報に設定した縮退規則を実行することにより、簡便に全ノード間を２本以上の経路で接続する経路を求めることができる。
【発明を実施するための最良の形態】
【００１３】
実施の形態１．
この実施の形態１では、斜向座標グラフを用いたフレームワーク処理部と、縮退規則情報に従いネットワークモデルを設計する囲い込み処理部を備える経路設計装置と、経路設計装置が実行する経路設計方法の一例を説明する。
【００１４】
図１（ａ）は、この発明のアドホックネットワークのモデルを示し、（ｂ）はネットワーク設計方法の概要を示す図である。図１（ａ）において、ネットワーク構成を示すネットワークモデル１０は、移動無線通信装置の発信ノード１Ｓと、移動無線通信装置の宛先ノード１Ｄとを与えられる。経路設計装置は与えられた図１（ａ）のネットワークモデル１０から図１（ｂ）の経路を設計する。図１（ｂ）において、通信装置間は無線によって接続するリンク２によって接続され、ネットワーク内の二地点間を結ぶ経路３ａ，３ｂ，３ｃ，３ｄを設計する。ネットワークモデル１０において、相互の接続関係に注目する場合は、移動無線通信装置をノードと呼び、ノード間の無線による接続をリンクと呼ぶ。ここで太線矢印で示すリンク２はノード間の個々の接続、経路３ａ，３ｂ，３ｃ，３ｄは破線矢印で示す経路を示す。図１（ａ）のネットワークモデル１０において、発信ノード１Ｓから２つのそれぞれの宛先ノード１Ｄに向けてデータを伝送する場合を考える。なお、発信ノード１Ｓ、宛先ノード１Ｄとのそれぞれのノードの直接電波が到達する範囲を六角形方眼４で示す。
【００１５】
発信ノード１Ｓからそれぞれの宛先ノード１Ｄまで直接電波が到達せず、間に中継ノード１Ｒを設定する必要がある場合、どこに中継ノード１Ｒを設定し、どのように経路を設計すればよいのか、決めるべき事柄が多すぎ、従来の方法では効率的な解を与えることができなかった。ここで、従来の「特開２００２−３３５１９２号公報」に記載された発明を簡単に説明して、従来のネットワーク設計における問題点を考える。
【００１６】
図２（ａ）〜（ｃ）は、特開２００２−３３５１９２等に示された、従来の有線通信経路の二重化により、サバイバビリティ（障害発生時にもサービスを提供する機能）を確保する方法を示す模式図である。図２において、ネットワーク構成を示すネットワークモデル１０は、通信端末またはルータ等の通信装置であるノード１（特に発信ノードは発信ノード１Ｓとし、宛先ノードは宛先ノード１Ｄとする）と、通信装置間を接続する金属ケーブルまたは光ファイバ等のケーブルによるリンク２と、ネットワーク内の二地点間を結ぶ経路３１，３２，３３とにより示される。ネットワークモデル１０において、相互の接続関係に注目する場合は、通信装置をノードと呼び、ケーブルをリンクと呼ぶ。ここでリンク２はノード間の個々の接続を示す。経路３１，３２，３３は、太線矢印の組で示す破線矢印で示した経路全体を指す。
【００１７】
図２（ａ）のネットワークモデル１０において、発信ノード１Ｓから宛先ノード１Ｄに向けてデータを伝送する場合を考える。発信ノード１Ｓから宛先ノード１Ｄに向けて、図２（ｂ）では１本の経路３１、図２（ｃ）では２本の経路３２と経路３３とが設定されている。図２（ｂ）のように経路が１本の場合は、経路３１の有するノード１またはリンク２に障害が発生した場合、発信ノード１Ｓから宛先ノード１Ｄに向けた通信が不可となる。しかし、図２（ｂ）のように、独立した経路が２本ある場合は、一方の経路３２が切断されても、他方の経路３３により通信が可能となる。ここで複数の経路が独立しているというのは、ノード１やリンク２を異なる経路によって共有していないことを指す。
【００１８】
従来の有線通信のサバイバブルネットワーク設計方法は、図２（ａ）のようなノード１，１Ｓ，１Ｄやリンク２が与えられた場合、すなわち、ネットワークモデル１０を構成するために必須の要素が既知である場合に、図２（ｃ）のような複数の独立経路３２，３３を効率良く発見し、障害発生時には効率良く切り替えるためのものであった。
【００１９】
ところが、基地局等の固定の通信設備を持たず、移動無線通信装置間の相互中継によりネットワークを構築するアドホックネットワークでは、図２のノード１やノード１Ｓ，１Ｄの位置が移動したり、リンク２が有線ケーブルではなく不安定な無線接続であるという理由で、従来の手法を適用することが困難である。図１に示したアドホックネットワークのモデルについて、図１（ａ）の発信ノード１Ｓから２個の宛先ノード１Ｄに向けてデータ通信を行う場合を考えると、発信ノード１Ｓから宛先ノード１Ｄまで直接電波が到達せず、間に中継ノード１Ｒを設定する必要がある場合、不定の事柄（ノードの移動や無線電波状態の変化等）が多すぎ、従来の方法では、どこに中継ノード１Ｒを設定し、どのように経路を設計すればよいのか等の解を効率的に与えることができなかった。
【００２０】
そこでこの実施の形態１の経路設計装置では、図１（ｂ）に示すように、経路を設計する補助のために六角形方眼４を設定し、そこで複数の経路３ａ，３ｂ，３ｃ，３ｄを設計する。図１（ｂ）では、発信ノード１Ｓから２個の宛先ノード１Ｄまで、それぞれ２本の経路３ａ，３ｂと経路３ｃ，３ｄを設定する。ここでは、経路設計の補助となる主に斜向座標グラフを生成するフレームワーク処理部と、ネットワーク設計における中継ノードの設定についての規則を示した縮退規則情報を実行してネットワークモデルの経路を設計する囲い込み処理部との２段階の処理部から構成する経路設計装置について、以下に説明する。
【００２１】
図３は、この実施の形態の経路設計装置を構成する要素の一例を示すブロック図である。図３において、経路設計装置５０は、ネットワークモデルを構成する発信ノードや宛先ノードのノード４０から緯度情報と経度情報とを少なくも有する位置情報６０を受信する位置情報入力部５１を備える。また、主に斜向座標グラフを生成するフレームワーク処理部５３と、ネットワーク設計における中継ノードの設定についての規則を示した縮退規則情報を実行してネットワークモデルの経路を設計する囲い込み処理部７０とを備える。
【００２２】
フレームワーク処理部５３は、ノード４０の通信可能範囲を距離で示す通信範囲情報を記憶する通信範囲情報記憶部５５と、通信範囲情報記憶部５５が記憶する通信範囲情報を１目盛りとする斜向座標グラフを生成する斜向座標生成部５７と、位置情報６０の斜向座標グラフ上の座標点を求めて斜向座標グラフ上にノード４０を配置して、斜向座標グラフ上に配置したノード４０に対応する座標点を取り囲む周囲境界線を斜向座標グラフ上に生成する配置処理部５９とを、備える。
【００２３】
また、囲い込み処理部７０は、周囲境界線を周囲境界線の内側に移動させて周囲境界線が囲い込む範囲を縮小する縮小周囲境界線を、斜向座標グラフ上に生成する周囲境界縮小部７３を備える。また、縮小周囲境界線の内側に仮想通信装置を配置させて、仮想通信装置上を通過する縮小周囲境界線を縮退させた縮退周囲境界線を生成する規則を示す縮退規則情報を記憶する縮退規則情報記憶部７５と、縮退規則情報に従い、仮想通信装置を縮小周囲境界線の内側に配置して、仮想通信装置を通過するように縮小周囲境界線を縮退させて、縮退周囲境界線を斜向座標グラフ上に生成する境界縮退部７７を備える。また、境界縮退部７７が生成した縮退周囲境界線と、ノード４０の座標点と、仮想通信装置の斜向座標グラフ上の位置とから中継ノードを配置するネットワークモデル上の位置を決定して、ネットワークモデルのネットワーク経路を設計して経路情報を生成して、経路情報を出力する経路設計部７９を備えた。図３に示したノード４０は、発信ノードと宛先ノードの２つであるが、ネットワークモデルの有するノードの数は２つ以上でもかまわない。
【００２４】
図４は、通信範囲情報記憶部５５が記憶する通信範囲情報の一例を示す図であえる。通信範囲情報はノード４０の通信可能領域を例えば円で示した場合の半径の距離である。図４の通信範囲情報記憶部５５が記憶する通信範囲情報は、１キロメートルである。
【００２５】
図５は、実施の形態１における経路設計装置の外観を示す図である。図５において、経路設計装置５０は、システムユニット２００、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）表示装置１４１、キーボード（Ｋ／Ｂ）１４２、マウス１４３、コンパクトディスク装置（ＣＤＤ）１８６、プリンタ装置１８７、スキャナ装置１８８を備え、これらはケーブルで接続されている。さらに、経路設計装置５０は、ＦＡＸ機３１０、電話器３２０とケーブルで接続され、また、ローカルエリアネットワーク（ＬＡＮ）５０５、ウェブサーバ５００を介してインターネット５０１に接続され、無線通信のほかに有線による通信も可能である。
【００２６】
図６は、実施の形態１における経路設計装置のハードウェア構成図である。図６において、経路設計装置５０は、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１３７を備えている。ＣＰＵ１３７は、バス１３８を介してＲＯＭ１３９、ＲＡＭ１４０、通信ボード１４４、ＣＲＴ表示装置１４１、Ｋ／Ｂ１４２、マウス１４３、ＦＤＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）１４５、磁気ディスク装置１４６、ＣＤＤ１８６、プリンタ装置１８７、スキャナ装置１８８と接続されている。ＲＡＭは、揮発性メモリの一例である。ＲＯＭ、ＦＤＤ、ＣＤＤ、磁気ディスク装置、光ディスク装置は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。通信ボード１４４は、ＦＡＸ機３１０、電話器３２０、ＬＡＮ５０５等に接続されている。例えば、通信ボード１４４、Ｋ／Ｂ１４２、ＦＤＤ１４５などは、情報入力部の一例である。また、例えば、通信ボード１４４、スキャナ装置１８８、ＣＲＴ表示装置１４１などは、出力部の一例である。
【００２７】
ここで、通信ボードは、ＬＡＮ５０５に限らず、直接、インターネット、或いはＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）に接続されていても構わない。直接、インターネット、或いはＩＳＤＮ等のＷＡＮに接続されている場合、経路設計装置５０は、インターネット、或いはＩＳＤＮ等のＷＡＮに接続され、ウェブサーバ５００は不用となる。磁気ディスク装置１４６には、オペレーティングシステム（ＯＳ）１４７、ウィンドウシステム１４８、プログラム群１４９、ファイル群１５０が記憶されている。プログラム群は、ＣＰＵ１３７、ＯＳ１４７、ウィンドウシステム１４８により実行される。
【００２８】
上記プログラム群１４９には、以下に述べる実施の形態の説明において「〜部」として説明する機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵにより読み出され実行される。ファイル群１５０には、以下に述べる実施の形態の説明において、「〜の判定結果」、「〜の計算結果」、「〜の処理結果」として説明するものが、「〜ファイル」として記憶されている。また、以下に述べる実施の形態の説明において説明するフローチャートの矢印の部分は主としてデータの入出力を示し、そのデータの入出力のためにデータは、磁気ディスク装置、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）、光ディスク、ＣＤ（コンパクトディスク）、ＭＤ（ミニディスク）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のその他の記録媒体に記録される。あるいは、信号線やその他の伝送媒体により伝送される。
【００２９】
また、以下に述べる実施の形態の説明において「〜部」として説明するものは、ＲＯＭ１３９に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、ハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。
【００３０】
また、以下に述べる実施の形態を実施するプログラムは、また、磁気ディスク装置、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）、光ディスク、ＣＤ（コンパクトディスク）、ＭＤ（ミニディスク）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のその他の記録媒体による記録装置を用いて記憶されても構わない。
【００３１】
図７は、実施の形態１のフレームワーク処理部による斜向座標グラフ上に通信装置の位置を配置する処理のフローチャート図である。図８は、実施の形態１の囲い込み処理部によるネットワークの経路設計情報を生成して出力する処理のフローチャート図である。図９は、斜向座標グラフの一例を示す図である。図９の斜向座標グラフは、三角メッシュに対応する斜向座標グラフの一例である。グラフのｘ軸、ｙ軸の１目盛りは通信可能範囲（Ｄ）であり、図４に示したように通信可能範囲（Ｄ）は、１キロメートルであるものとする。
【００３２】
図７、図８のフローチャートに従い経路設計装置の動作を説明する前に、まず、無線アドホックネットワーク設計の特徴を述べる。図１に示した無線アドホックネットワーク設計問題は、次の二点において図２の有線ネットワーク設計問題と異なる。
（１）位置依存性：ネットワークモデル１０をノード１，１Ｓ，１Ｄとリンク２のモデルで表現する場合の基本的な仮定は、リンク２はゴムひもの様に伸び縮み自在でトポロジカルな自由度があるとすることであるが、無線ではこれは成り立たない。
（２）無線の同報性：有線通信では伝送はリンク２に沿って一次元でのみ行われるが、無線では三次元空間で行われる。
【００３３】
上記したこれらの特性を生かしてサバイバブルアドホックネットワークを設計するために、まず、図２のノード１やノード１Ｓやノード１Ｄとリンク２の代わりに、ノード１と球によって表現する通信可能範囲５によるモデルを考える（図１０）。図１０は、ノードから電波の到達する通信可能範囲５を球で示す図である。発信元のノード１Ｓから宛先のノード１Ｄまで、各ノードの通信可能範囲５の範囲内に、順次、次ノードを設定することにより経路の設計を行う。例えば図１０では、発信元のノード１Ｓを中心とする通信可能範囲５の球と、宛先のノード１Ｄを中心とする通信可能範囲５の球との間に通信不可能な空間が存在するため、この通信不可能な空間を通信可能な空間にして、発信元ノード１Ｓと宛先ノード１Ｄとの間の通信を可能にする。通信を可能にするため、中継ノード１をノード１Ｓとノード１Ｄとの間に配置させる。配置した中継ノード１の周りには、中継ノード１を中心とする通信可能範囲５の球ができる。
【００３４】
ここで、検討を容易にするために、図１０のモデルを単純化していく。まず、図１０の通信可能範囲５の球を二次元の円に単純化する。次に、さらに円を多角形にして、通信可能範囲５の重複を避けるため半径を１／２に縮退させて考える（図１１）。すなわち、半径を１／２に縮退させたものが、通信範囲情報記憶部５５が記憶する通信可能範囲情報（１キロメートル）である。図１１は、円を多角形、例えば六角形に置き換え、通信可能範囲５を１／２に縮退させてネットワークモデルを六角形方眼で示した図である。通信可能範囲５を１／２に縮退させた結果、我々の課題は、多角形方眼（図１２）上の隣接する多角形をたどって発信元ノード１Ｓから宛先ノード１Ｄへの経路を求めることとなる。図１２は多角形方眼の一例を示す図であり、（ａ）は六角形、（ｂ）は四角形、（ｃ）は三角形の方眼を示す。上記した説明では、球を円に単純化して、さらに円を六角形の多角形に置き換えることを説明した。しかし、円を多角形に置き換える場合、六角形以外に、四角形や三角形に置き換えてもかまわない。四角形に置き換えた場合、ｘ軸とｙ軸とは直角に交わる。斜向座標座標グラフは、この直角に交わるグラフも含む。
【００３５】
このように、円を多角形に置き換える場合、平面を隙間無く覆える多角形であれば、六角形ではなくても、四角形や三角形でもかまわない。ただし、六角形は電波伝搬を反映した円に近いので用いられることが多い。また、四角形は辺が直行しているので、取り扱いが楽である。それぞれの多角形の特徴を考慮して、設計者が六角形、四角形、三角形のいずれに置き換えるか決定できるものとする。
【００３６】
このような平面グラフの問題は、グラフ理論において、通常、双対グラフを用いて解かれる。図１３（ａ）、（ｂ）、（ｃ）に図１２（ａ）、（ｂ）、（ｃ）のそれぞれの多角形方眼に対応する双対グラフメッシュを示す。我々の課題は、図１３の双対メッシュグラフにおいて、点線で示すメッシュで接続された双対ノード１をたどって発信元ノード１Ｓから宛先ノード１Ｄへの経路を求めることとなる。ここで双対メッシュを定義する。双対メッシュとは、多角形方眼において、各マス目内にマス目を代表する点（双対の頂点）１個を設定し、隣接するマス目に対してマス目の境界線とただ１回交わるような線（双対の辺）で代表点を結んで得られるメッシュである。六角形方眼の双対メッシュは三角メッシュであり、四角形方眼の双対メッシュは四角メッシュ、三角形方眼の双対メッシュは六角メッシュとなる。
【００３７】
この実施の形態では、図１２（ａ）の六角形方眼、および対応する図１３（ａ）の三角メッシュを使用する。問題の記述を容易にするために、図９に示す三角メッシュに対応する斜向座標７を用いて、ノードの位置を示す。
【００３８】
次に、本発明の経路設計装置によるサバイバブルアドホックネットワーク設計方法である囲い込みアルゴリズムを実行する動作について説明する。我々のサバイバブルアドホックネットワーク設計問題は、発信元のノード１Ｓが付与されているとき、サバイバビリティの要求課題として、ネットワークモデル１０内の各ノード間に、２本以上の独立経路を設計するとともに、経路内の最小コスト経路を求めるものとする。制約条件は、図９の斜向座標上の隣接する点（図９の「○」）で表されるノードをたどることである。全リンクコスト（図９の１目盛）を１として最小コスト経路を求める。図１３（ｂ）の場合は、ｘ軸とｙ軸とは直角に交わる。斜向座標座標グラフは、この直角に交わるグラフも含む。
【００３９】
上記したように経路設計装置は、フレームワーク処理と囲い込み処理との２段階の処理によってネットワークの通信経路を設計する。はじめに、図７のフローチャートに従い、フレームワーク処理の手順を説明する。図７において、経路設計装置５０は、ネットワークモデル１０の有する発信ノード４０と宛先ノード４０からそれぞれノードの位置を示す位置情報６０を、位置情報入力部５１により入力する（Ｓ１，位置情報入力工程）。位置情報６０は、例えば緯度情報と経度情報とを有して、ノードの位置を表す。また、図３の例では、発信ノード４０と宛先ノード４０の２機のノードから位置情報を入力しているが、２機以上のノードから位置情報を入力してもかまわない。すなわち、ネットワークモデル１０は、例えば、発信ノードを１機、宛先ノードを複数機有していてもかまわない。入力した位置情報６０は、フレームワーク処理部５３へ出力する。
【００４０】
フレームワーク処理部５３は、斜向座標生成部５７によって、例えば図９に示す斜向座標グラフを生成する（Ｓ２，斜向座標生成工程）。このとき、斜向座標生成部５７は、斜向座標グラフのｘ軸とｙ軸のそれぞれの１目盛を、通信範囲情報記憶部５５が記憶する通信範囲情報の通信可能範囲（Ｄ）として生成する。ここで、斜向座標として三角形の双対メッシュを使用する理由は上記した通りである。
【００４１】
次に、フレームワーク処理部５３は、配置処理部５９によって、Ｓ１で入力した発信ノード４０の位置情報から斜向座標グラフの斜向座標７上の座標点を求めて、発信ノード４０の位置を、求めた座標点に配置する。また、Ｓ１で入力した宛先ノード４０の位置情報から斜向座標グラフの斜向座標７上の座標点を求めて、宛先ノード４０の位置を、求めた座標点に配置する。求めた座標点が斜向座標グラフのメッシュで示した三角形の頂点でない場合は、求めた座標点を直近の頂点の座標点に近似させる。また、緯度情報と、経度情報とを所定の座標点に変換する処理は、例えば、発信元ノード４０の緯度情報と、経度情報とを斜向グラフ上の座標（０，１）と仮定して宛先ノード４０の緯度情報と、経度情報とを基準にして宛先ノード４０との相対距離と角度とを求めて、相対距離と角度とから宛先ノード４０の座標点を算出する。この時、ｘ軸とｙ軸とのそれぞれの１目盛は、図４により１キロメートルとする。
【００４２】
座標点の配置が終了したら、配置処理部５９は、配置した座標点を囲い込む周囲境界線を、斜向座標７上に生成する（Ｓ３，配置処理工程）。ここまでのＳ１〜Ｓ３の処理がフレームワーク処理である。フレームワーク処理は、例えば磁気ディスク装置１４６のプログラム群１４９に記憶されたプログラムをフレームワーク処理部５３が実行することによって実現する。また、通信範囲情報記憶部５５は、磁気ディスク装置１４６のファイル群１５０に記憶されている。フレームワーク処理部５３は、ＣＰＵ１３７であり、ＣＰＵ１３７は磁気ディスク装置１４６のプログラム群１４９からフレームワーク処理を行うプログラムを呼び出して、プログラムに従いＳ１〜Ｓ３のフレームワーク処理を行う。
【００４３】
続いて、図８に従い、囲い込み処理の手順について説明する。なお、以下の囲い込みアルゴリズムは、囲い込み処理のアルゴリズムである。また、図７のＳ３の処理では、配置した座標点を囲い込む周囲境界線を斜向座標７上に生成する処理を、配置処理部５９が行うものとして説明した。しかし、説明を容易にするため、囲い込み処理に含めるものとして以下に説明する。周囲境界線を生成する実際の処理は、フレームワーク処理内で行っても、囲い込み処理内で行っても、いずれでもかまわない。
【００４４】
図１４、図１５に斜向座標グラフの斜向座標７上に囲い込み（Ｅｎｃｌｏｓｕｒｅ）アルゴリズムの実行状況の経過を説明する図を示す。なお、図１４、図１５において、「●」は発信元或いは宛先ノード、「◎」は仮想ノード、「○」は中継ノードをそれぞれ示す。
図１４（ａ）−＞ノードの和集合１Ｗ＝｛宛先ノード１Ｄと発信ノード１Ｓの和集合｝を求める。
図１４（ｂ）−＞和集合１Ｗの六角形ゾーンの周囲境界線３Ｂによる初期囲い込み。６個の境界線を平行移動して範囲を縮小する。
図１５（ａ）−＞全ノードを包含する最小囲い込み範囲を決定して、決定した最小囲い込み範囲に基づいて周囲境界線３Ｂを縮小させて、縮小周囲境界線を生成。さらに範囲を縮小。
図１５（ｂ）−＞予め定めた縮退規則情報に従い縮小周囲境界線をさらに縮退させて、六角形および付随三角形から構成される縮退周囲境界線を生成して、縮退境界範囲を決定する。図１５（ｂ）の「◎」は仮想ノード１Ｖである。
図１５（ｃ）−＞縮退周囲境界線の内部にあるノードと境界閉路を２個の最短辺で接続。境界閉路は周囲境界線３Ｂによって示す。境界閉路および内部ノードが設計したネットワーク経路の解となる。図１５（ｃ）の「○」は、中継ノード１Ｒである。
【００４５】
縮退規則情報に従う詳しい周囲境界線の縮退方法については、図１６に示す。なお、縮退は周囲境界線の有する複数の辺それぞれについて行うものとする。
図１６（ａ）−＞周囲境界線３Ｂ上に２個以上のノード（図中ノードを「●」で示す）がある場合は、周囲境界線はシフト（縮退）しない。
図１６（ｂ）−＞周囲境界線３Ｂ上にノードが１個のみある場合は、周囲境界線３Ｂは１単位（斜向座標の１目盛）シフト（縮退）し、周囲境界線上のノードはそのままで、シフト（縮退）された周囲境界線３Ｂ上に２個の仮想ノード１Ｖを設定する。
図１６（ｃ）−＞ノードと周囲境界線３Ｂとの接続は２リンク以上必要で、１リンクではいけない（ここでの「リンク」とは、ノードと仮想ノードとの接続を指す）。
【００４６】
図１４、図１５に示した経過で実行する囲い込み（Ｅｎｃｌｏｓｕｒｅ）処理の手順を図８のフローチャートに従い説明する。図８において、配置処理部５９は、座標点の配置が終了したら、配置した発信元ノードの座標点と宛先ノードの座標点とを囲い込む周囲境界線を、斜向座標７上に生成する（Ｓ１０，配置処理工程）。この処理は、図１４（ａ）と図１４（ｂ）の初期囲い込みの処理に対応する。図１４（ａ）に示すように、ここでは発信元ノードと宛先ノードとを合わせて３つ以上のノードをネットワークモデルが有するものとする。図１４（ｂ）のように、周囲境界線は例えば正六角形の形状をしている。
【００４７】
次に、囲い込み処理部７０の周囲境界縮小部７３が、周囲境界線３Ｂの有する６つの各辺を周囲境界線の内側に平行移動させる（Ｓ１１，周囲境界縮小工程）。各辺を移動させることによって、周囲境界線３Ｂが取り囲む範囲を縮小する。この処理は、図１４（ｂ）の境界線を平行移動して範囲を縮小する処理と、図１５（ａ）の処理に対応する。
【００４８】
次に、囲い込み処理部７０の境界縮退部７７が、縮退規則情報記憶部７５に記憶された縮退規則情報に従い、平行移動して縮小した（縮小）周囲境界線３Ｂをさらに縮退させる（Ｓ１２，境界縮退工程）。縮退規則情報記憶部７５が記憶する縮退規則情報は、図１６（ａ）〜（ｃ）に示した内容で縮退を行わせるものであり、上記した図１６の説明のように、
（１）周囲境界線３Ｂ上に２個以上のノード（図中ノードを「●」で示す）がある場合は、周囲境界線はシフト（縮退）しない。
（２）周囲境界線３Ｂ上にノードが１個のみある場合は、周囲境界線３Ｂは１単位（斜向座標の１目盛）シフト（縮退）し、周囲境界線上のノードはそのままで、シフト（縮退）された周囲境界線３Ｂ上に２個の仮想ノード１Ｖを設定する。
（３）ノードと周囲境界線３Ｂとの接続は２リンク以上必要で、１リンクではいけない（ここでの「リンク」とは、ノードと仮想ノードとの接続を指す）。
の規則で境界縮退部７７に周囲境界線の縮退を行わせる。この処理は、図１５（ｂ）の処理に対応する。周囲境界縮小部７３が縮小した周囲境界線を上記した縮退規則に従い縮退させる場合には、図１５（ｂ）のように仮想ノード１Ｖを配置する。また、仮想ノード１Ｖを配置する条件は、周囲境界線上にノードが１つのみある場合である。図１５（ｂ）の網がけした三角形に相当する部分が周囲境界線を縮退した部分であり、この三角形の頂点、或いは辺上の三角メッシュの頂点には仮想ノード１Ｖ（図中「◎」）が配置されている。
【００４９】
次に、囲い込み処理部７０の経路設計部７９は、境界縮退部７７が縮退した周囲境界線３Ｂ上にある仮想ノード１Ｖを中継ノード１Ｒに変更する。そして、周囲境界線上及び周囲境界線内部にあるノードと中継ノードとを接続してリンクを生成する。リンクの生成は、それぞれのノードに少なくとも２リンクを生成させる。そして、周囲境界線上のノードの位置情報と中継ノードの位置情報とリンクを示す情報とを経路情報８０として出力する（Ｓ１３，経路設計工程）。経路情報８０の出力先は、例えば、発信ノードや宛先ノードや経路設計者の携帯する通信装置やプリンタ装置１８７やＬＡＮ５０５やＣＲＴ表示装置１４１やＦＡＸ機３１０等である。また、ノードの位置情報装置は、斜向座標グラフ上の座標点であっても、座標点を緯度情報と経度情報とに変換したものでもいずれでもかまわない。この処理は、図１５（ｃ）に対応する処理である。
【００５０】
上記したＳ１０〜Ｓ１３の処理が、囲い込み処理である。このように、経路設計装置５０は、経路設計処理をフレームワーク処理と囲い込み処理との２段階の処理で実現する。なお、ネットワークモデルの有する発信元ノードや宛先ノードが移動して位置が変更になった場合には、再度の経路設計が必要となり、図７、図８の手順を再実行して、経路情報を求める。
【００５１】
次に、経路設計装置が設計した経路の妥当性を、周囲境界縮小と内部ノード接続の二段階について述べる。まず、周囲境界縮小について考える。我々の目的は予めネットワークモデルを構成する位置が分かっている複数のノードを２本以上の独立経路で接続することである。このため、各ノードは隣接ノードと少なくとも２個のリンクで接続されている必要がある。図１５（ｃ）の周囲境界線３Ｂ（周囲境界閉路）は、閉路上の各ノードに対して２リンク接続を与え、最適に近い。図１４（ａ）に示したできるだけ多くのノードを２本以上のリンクで接続する閉路として、図１５（ｃ）と全く異なるものは考え難い。
【００５２】
次に、内部ノードについて考える。図１５（ｃ）は網がけした三角形において明らかに冗長なリンクを有し、その一辺を削除することにより、コスト最小化を図ることが可能である。しかし、複雑さを増してその処理を行わなくても、最適に近い値は得られている。
【００５３】
図１７に経路設計装置５０による経路設計の利用形態を示す。図１７（ａ）は災害ネットワークであり、◎は、中継ノード１Ｒを示す。図１７（ｂ）は温度等のセンサーネットワークを示し、図中白抜きの○は、中継ノードを兼ねる宛先ノード１Ｄを示す。災害ネットワークは、１つの発信ノード１Ｓから２つの宛先ノード１Ｄへ、それぞれの宛先ノードに対して２つの経路３ａ，３ｂと３ｃ，３ｄを設定し、経路途中に配置した中継ノード１Ｒを経路情報に含めて提示する場合等に使用することが可能である。
【００５４】
また、センサーネットワークでは、情報を集中管理する発信元ノード１Ｓと発信元ノード１Ｓの通信可能範囲５と中継ノードを兼ねる宛先ノードを配置するネットワークモデルの領域を示す領域情報１２が経路設計装置に与えられる。領域情報１２は、例えば四角形の領域の４つの頂点それぞれの緯度情報と経度情報である。経路設計装置５０は、領域情報１２の有する４つの頂点それぞれの緯度情報と経度情報とを宛先ノードの位置情報と仮定して経路設計を行う。経路設計装置５０は、図７、図８の処理を行い、経路情報として図１７（ｂ）の「◎」で示した中継ノードを兼ねる宛先ノードの位置情報を出力する。ネットワーク設計者は、出力された宛先ノードの位置情報に対応する場所に宛先ノードを配置させれば、所定の宛先ノードに障害が発生して使用不可能になるリンクとノードとが発生しても、他の中継ノードを兼ねる宛先ノードを経由する経路によって、ノード間の接続が確保される。
【００５５】
以上のように、この実施の形態で説明した経路設計装置及び経路設計方法は、多角形グリッド、双対グラフメッシュ、斜向座標によるネットワーク設計フレームワークを用いることにより、ノードが移動し、リンクが定まっていない場合でも、ノードを接続する複数の経路、および中継ノードを設計できるという効果がある。また、厳密に最適経路を求めるためには、全ノードの組み合わせを検証する膨大な処理を必要とするネットワーク設計であるが、囲い込み処理部による囲い込み処理により、簡便に全ノード間を２本以上の経路で接続する経路を求めることができる。
【００５６】
この実施の形態では、以下のことを特徴とする経路設計装置、経路設計方法の一例を説明した。
【００５７】
アドホックネットワークでは、ノードが移動し無線リンクが不安定なため、不定の事柄が多すぎ、従来の有線通信の方法では、複数の独立経路の設計を効率的に行うことができなかった。しかし、この実施の形態の経路設計装置及び経路設計方法では、設計のためのフレームワークを用いることにより、可能となる。
【００５８】
フレームワークは、多角形方眼、双対グラフメッシュ、斜向座標より構成される。
【００５９】
フレームワークを用いたサバイバブルアドホックネットワーク設計方法として、囲い込みアルゴリズムを提案している。囲い込みアルゴリズムの特徴は、全ノード間に２本以上独立経路を設定するため、境界で囲い込み、これを狭めていき、できるだけ多くのノードを境界線上にのせ、内部に残ったノードは二本以上のリンクで境界線の枠と接続することである。
【００６０】
実施の形態２．
この実施の形態では、通信範囲情報を電波の強度に対応させる経路設計装置、経路設計方法の一例を説明する。
【００６１】
図１８は、実施の形態２の経路設計装置を構成する要素の一例を示すブロック図である。図１８において、位置情報入力部５１は、位置情報を受信した際の電波の強度を測定する電波強度測定部９１を備える。また、通信範囲情報記憶部５５は、図１９に示すように、通信可能範囲を電波強度に対応させて記憶する通信範囲情報を記憶する。また、斜向座標生成部５７は、電波強度測定部９１が測定した測定結果である電波レベルを入力して、電波レベルに対応する通信可能範囲を通信範囲情報記憶部５５から取得して、取得した電波レベルに対応する通信可能範囲をｘ軸とｙ軸の１目盛とする斜向座標グラフを生成する。なお、位置情報入力部５１は複数の位置情報を入力し、それぞれの位置情報は電波レベルが同じ場合と異なる場合とがある。電波レベルが異なる場合には、電波レベルに対応する通信可能範囲が異なる場合が考えられる。通信可能範囲が異なる場合には、例えば、通信可能範囲の平均値を算出して、平均値を斜向座標グラフの生成に使用する。経路設計装置５０の他の要素は、上記実施の形態１の図３と同様であるものとする。
【００６２】
経路設計方法の処理手順は、図７のＳ１とＳ２が実施の形態１と異なる。実施の形態２では、図７のＳ１の位置情報を受信した後、受信した位置情報の電波強度を電波強度測定部９１が測定して、測定した電波レベルを斜向座標生成部５７に出力する。また、Ｓ２では、斜向座標生成部５７は、電波レベルに対応する通信可能範囲を通信範囲情報記憶部５５から取得して、取得した電波レベルに対応する通信可能範囲をｘ軸とｙ軸の１目盛とする斜向座標グラフを生成する。Ｓ１、Ｓ２以外の処理は、上記実施の形態１の図７、図８と同様である。
【００６３】
以上のように、通信可能範囲を電波レベルに対応させることにより、実際の通信環境に合ったネットワーク経路を設計することができる。
【００６４】
実施の形態３．
この実施の形態では、通信範囲情報をノードの種類に対応させる経路設計装置、経路設計方法の一例を説明する。
【００６５】
図２０は、実施の形態３の経路設計装置を構成する要素の一例を示すブロック図である。図２０において、位置情報入力部５１は、位置情報を発信したノードの種類を識別するためのノード種類情報を有する位置情報６１を受信する。また、通信範囲情報記憶部５５は、図２１に示すように、通信可能範囲をノードの種類に対応させて記憶する通信範囲情報を記憶する。また、斜向座標生成部５７は、位置情報６１の有するノード種類情報を入力して、ノード種類情報に対応する通信可能範囲を通信範囲情報記憶部５５から取得して、取得したノード種類情報に対応する通信可能範囲をｘ軸とｙ軸の１目盛とする斜向座標グラフを生成する。なお、位置情報入力部５１は種類の異なるノードから位置情報６１を入力し、ノードの種類に対応する通信可能範囲は同じ場合と異なる場合とがある。通信可能範囲が異なる場合には、例えば、通信可能範囲の平均値を算出して、平均値を斜向座標グラフの生成に使用する。経路設計装置５０の他の要素は、上記実施の形態１の図３と同様であるものとする。
【００６６】
経路設計方法の処理手順は、図７のＳ１，Ｓ２が実施の形態１と異なる。実施の形態３では、図７のＳ１の位置情報６１を受信した後、受信した位置情報６１の有するノード種類情報を斜向座標生成部５７に出力する。また、Ｓ２では、斜向座標生成部５７は、ノード種類情報に対応する通信可能範囲を通信範囲情報記憶部５５から取得して、取得した通信可能範囲をｘ軸とｙ軸の１目盛とする斜向座標グラフを生成する。Ｓ１、Ｓ２以外の処理は、上記実施の形態１の図７、図８と同様である。
【００６７】
以上のように、通信可能範囲をノードの種類に対応させることにより、実際にネットワークモデルを構成する通信装置の仕様に合ったネットワーク経路を設計することができる。
【００６８】
実施の形態４．
この実施の形態では、通信範囲情報を時刻に対応させる経路設計装置、経路設計方法の一例を説明する。
【００６９】
図２２は、実施の形態４の経路設計装置を構成する要素の一例を示すブロック図である。図２２において、位置情報入力部５１は、ネットワークモデルを構成する通信装置（ノード）が自己の位置情報を算出した際の時刻を示す時刻情報を位置情報に含めて発信した位置情報６２を受信する。或いは、位置情報６２に含まれる時刻情報は、例えば自己の位置を算出する際に使用する衛星から発信される測位信号に含まれる測位時刻情報でもかまわない。通信範囲情報記憶部５５は、図２３に示すように、通信可能範囲を時刻に対応させて記憶する通信範囲情報を記憶する。また、斜向座標生成部５７は、位置情報６２の有する時刻情報を入力して、時刻情報に対応する通信可能範囲を通信範囲情報記憶部５５から取得して、取得した時刻情報に対応する通信可能範囲をｘ軸とｙ軸の１目盛とする斜向座標グラフを生成する。なお、位置情報入力部５１は複数のノードから異なる時刻情報を有する位置情報６２を入力し、時刻情報に対応する通信可能範囲は同じ場合と異なる場合とがある。通信可能範囲が異なる場合には、例えば、通信可能範囲の平均値を算出して、平均値を斜向座標グラフの生成に使用する。経路設計装置５０の他の要素は、上記実施の形態１の図３と同様であるものとする。
【００７０】
経路設計方法の処理手順は、図７のＳ１，Ｓ２が実施の形態１と異なる。実施の形態４では、図７のＳ１の位置情報６２を受信した後、受信した位置情報６２の有する時刻情報を斜向座標生成部５７に出力する。また、Ｓ２では、斜向座標生成部５７は、時刻情報に対応する通信可能範囲を通信範囲情報記憶部５５から取得して、取得した通信可能範囲をｘ軸とｙ軸の１目盛とする斜向座標グラフを生成する。Ｓ１、Ｓ２以外の処理は、上記実施の形態１の図７、図８と同様である。
【００７１】
以上のように、通信可能範囲を時刻に対応させることにより、ネットワークモデルの通信経路を設計する際の時刻における通信環境に合ったネットワーク経路を設計することができる。
【００７２】
実施の形態５．
この実施の形態では、経路設計装置が通信経路の設計を行うだけでなく、自身もネットワークモデルを構成するノードである場合の経路設計装置、経路設計方法の一例を説明する。
【００７３】
図２４は、実施の形態４の経路設計装置を構成する要素の一例を示すブロック図である。図２４において、経路設計装置５０は、衛星群２０１を構成する静止衛星２０２やＧＰＳ衛星２０３や準天頂衛星２０４から発信された測位信号をアンテナ９３を介して受信する測位受信部９５を備える。また、測位受信部９５が受信した測位信号から自己の位置を算出して自己位置情報を生成する位置算出部９７を備える。アンテナ９３，測位受信部９５，位置算出部９７とにより受信位置算出部９４を構成する。フレームワーク処理部５３は、位置情報入力部５１から位置情報６０を入力するとともに、位置算出部９７から自己の位置情報を入力する。経路設計装置５０の他の要素は、上記実施の形態１の図３と同様であるものとする。
【００７４】
経路設計方法の処理手順は、図７のＳ１とＳ２との間に自己の位置を算出する処理を行う点が実施の形態１と異なる。実施の形態５では、図７のＳ１の位置情報を受信した後、アンテナ９３を介して測位受信部９５が測位信号を受信して、位置算出部９７が受信した測位信号を用いて自己の位置情報を算出する処理を行う。また、Ｓ３で配置処理部５９は、位置算出部９７から自己の位置情報を入力して斜向座標グラフ上の座標点に変換し、自己の位置を斜向座標グラフ上に配置する。Ｓ１、Ｓ３以外の処理は、上記実施の形態１の図７、図８と同様である。また、通信可能範囲は、実施の形態２〜４にように、電波強度やノードの種類や時刻に対応させることも可能である。
【００７５】
以上のように、経路設計装置は、ネットワークモデルを構成するノードを兼ねることが可能となる。
【００７６】
実施の形態６．
この実施の形態では、２層構造のネットワークモデルを用いてアドホックネットワークの経路設計について一例を説明する。
図２５は、実施の形態６のアドホックネットワークの２層構造のモデルを示す図である。図２５に示すように、この実施の形態６のネットワークモデル１０は、飛行体局１ａからなるネットワーク層と、地上局１ｇからなるネットワーク層との２層構造である。飛行体局１ａは、例えば航空機などの飛行体に搭載された無線通信端末装置であって、広域にわたって配置する地上局１ｇ間のコネクティビティ（接続性）を確保して通信を行なうための中継を行なう。飛行体局１ａ間は、無線リンク２ａによって接続される。地上局１ｇは、移動無線通信装置であって、地上局１ｇ間は、無線リンク２ｇによって接続する。２地点間のそれぞれの地上局１ｇは、２つの地上局間経路３Ｈｇによって接続する。２地点間のそれぞれの飛行体局１ａは、２つの飛行体局間経路３Ｈａによって接続する。飛行体局１ａは、通信可能範囲５ａＬを有し、飛行体局１ａの通信可能範囲を地上へ投射すると地上局１ｇからなるネットワーク層への投射５ａＲとなる。飛行体局１ａは地上からの垂直高Ｈを有する。言い換えると、飛行体局１ａからなるネットワーク層の面は、地上局１ｇからなるネットワーク層の面に対して、垂直方向にあって、地上局１ｇからなるネットワーク層の面とは、垂直高Ｈを有する。
ここで、符号の識別について説明する。ネットワークモデル１０において、地上局に関するものは添え字ｇ、飛行体局に関するものは添え字ａを添えて表す。添え字ｇとａによるネットワーク層の区別は、本実施の形態６以降の実施の形態でも同様とする。また、地上局と飛行体局との相互の接続関係に注目する場合は、通信装置をノード、ノード間の個々の接続をリンクと呼ぶ。経路設計装置は、図２５中の破線で示した地上局間経路３Ｈｇと飛行体局間経路３Ｈａとを合わせたネットワーク経路を設計する。図２５のネットワークモデル１０において、地上局１ｇ間で通信を行なう場合、地上局１ｇが広域に渡って配置されており、地上ノードの相互通信のみでは通信経路を確保することが困難な場合（通信経路の確保が困難な理由としては、例えば、通信可能範囲が狭く、直近の地上ノードまで電波が届かない場合や、地上ノード間に高い山があり、電波が遮られて届かない場合などがある）、飛行体局１ａで中継を行なうことにより、広域の通信経路を提供する。この際、一個の通信経路を確保するだけでなく、複数の独立経路を設計し、サバイバビリティを確保する。
【００７７】
図２６は、実施の形態６のネットワーク設計方法に使用する２層構造のネットワークモデルを示す図である。地上局のネットワークモデル１０ｇは、複数の多角形、例えば複数の正六角形を隣接させて配置した地上レイヤメッシュ（多角形方眼）４ｇによって表す。飛行体局のネットワークモデル１０ａは、複数の多角形、例えば複数の正六角形を隣接させて配置した航空レイヤメッシュ（多角形方眼）４ａによって表す。地上局１ｇは通信可能範囲Ｄｇ（第１の通信可能範囲）を有し、飛行体局１ａは通信可能範囲Ｄａ（第２の通信可能範囲）を有する。通信可能範囲Ｄｇと通信可能範囲Ｄａとの関係は、通信可能範囲Ｄｇ＜通信可能範囲Ｄａであり、飛行体局の通信可能範囲が地上局の通信可能範囲よりも広い範囲をカバーすることによって、直接接続できない地上局間の経路を飛行体局を介して接続する。正六角形の中心点には地上局或いは飛行体局をそれぞれ配置するものとし、中心点から多角形の辺までの距離はそれぞれの通信可能範囲を１／２に縮退させた距離を有する。正六角形は、実施の形態１で説明したように、ノードから電波の到達する通信可能範囲を球で示し（図１０）、次に、球を二次元の円に単純化して、さらに、円を正六角形に置き換えたものである（図１１）。実施の形態１で説明したように、球を二次元の円に単純化する際に通信可能範囲の重複を避けるため、円の半径を通信可能範囲の１／２に縮退する。すなわち、隣接する地上局１ｇとの間は、通信可能範囲Ｄｇであって、正六角形の中心点から正六角形の辺までの長さは通信可能範囲Ｄｇを１／２に縮退した距離を有する。また、隣接する飛行体局１ａとの間は、通信可能範囲Ｄａであって、正六角形の中心点から正六角形の辺までの長さは通信可能範囲Ｄａを１／２に縮退した距離を有する。次に、図２６中のメッシュ状の点線について説明する。このメッシュ状の点線は、双対グラフを示している。この点線は、隣接する正六角形の中心点同士を正六角形の辺を通過する線で結んだものである。１つの中心点は他の複数の中心点と結ばれるため、線が多数生成されてメッシュ状になる。地上局の双対グラフメッシュ６ｇと飛行体局の双対グラフメッシュ６ａは、このようにして生成する。
【００７８】
これらの双対グラフメッシュは、図９の斜向座標７に対応する。地上局の双対グラフメッシュ６ｇと飛行体局の双対グラフメッシュ６ａとは、それぞれ地上局と飛行体局とでは通信可能範囲が異なるため、メッシュの１マスの大きさが異なる。
【００７９】
図２７は、この実施の形態の経路設計装置を構成する要素の一例を示すブロック図である。図２７は実施の形態１の図３と同様の符号を付した要素は同様の動作をする。図３の説明と重複する部分があるが、図２７の各要素について説明する。
図２７において、経路設計装置５０は、地上局のネットワークモデル１０ｇを構成する地上局であるノード４０から緯度情報と経度情報とを少なくとも有する位置情報６０を受信する位置情報入力部５１を備える。また、主に第１のグラフと第２のグラフを生成するフレームワーク処理部５３と、ネットワーク設計における中継ノードの設定についての規則を示した縮退規則情報を、地上局のネットワークと飛行体局のネットワークに対してそれぞれ実行して、地上局のネットワークモデルの経路と飛行体局のネットワークモデルの経路とをそれぞれ設計する囲い込み処理部７０とを備える。また、地上局のネットワークモデルと、飛行体局のネットワークモデルとから、これらのモデルを融合して、地上局間の接続を部分的に飛行体局を介して接続するネットワーク経路情報を生成して出力する経路情報融合部７８（第２の経路設計部）を備える。
【００８０】
フレームワーク処理部５３は、通信範囲情報記憶部５５と、第１のグラフ生成部である地上レイヤ斜向座標生成部５７ｇと、第１の配置処理部である地上レイヤ配置処理部５９ｇと、エリア生成部であるマルチホップ隣接ノードエリア生成部５８１とエリア分類部であるエリア和集合生成部５８２とを備えるクラスタ生成部５８と、第２のグラフ生成部である航空レイヤ斜向座標生成部５７ａと、第２の配置処理部である航空レイヤ配置処理部５９ａとを備える。
囲い込み処理部７０は、周囲境界縮小部７３と、縮退規則情報記憶部７５と、境界縮退部７７と、第１の経路設計部である経路設計部７９とを備える。
【００８１】
通信範囲情報記憶部５５は、ノード４０の通信可能範囲を距離で示したその距離を第１の通信範囲情報として記憶する。さらに、飛行体局の通信可能範囲を距離で示したその距離を第２の通信範囲情報として記憶する。
地上レイヤ斜向座標生成部５７ｇは、第１の通信可能範囲を１目盛りとする地上レイヤ斜向座標グラフを生成する。
航空レイヤ斜向座標生成部５７ａは、第２の通信可能範囲を１目盛りとする地上レイヤ斜向座標グラフを生成する。
【００８２】
地上レイヤ配置処理部５９ｇは、位置情報６０に基づき、複数のノード４０に対応する各座標点を地上レイヤ斜向座標グラフ上に配置する。
クラスタ生成部５８は、地上レイヤ斜向座標グラフ上に配置した複数のノード４０に対応する各座標点を、後述する条件に従い複数のクラスタに分割する。
マルチホップ隣接ノードエリア生成部５８１は、各ノードのマルチホップ隣接エリアを生成し、エリア和集合生成部５８２は、マルチホップ隣接エリアの和集合を生成して、クラスタ毎に各クラスタに含まれる地上局を取り囲む周囲境界線を地上レイヤ斜向座標グラフ上に生成する。地上レイヤ斜向座標グラフ上に生成した複数の周囲境界線の情報は、地上レイヤ配置処理部５９ｇに出力する。地上レイヤ斜向座標グラフ上に生成した複数の周囲境界線の情報と、地上レイヤ斜向座標グラフを示す情報（例えば、図９の斜向座標７を展開するための情報）とは、航空レイヤ配置処理部５９ａに出力する。
【００８３】
航空レイヤ配置処理部５９ａは、クラスタ生成部５８から地上レイヤ斜向座標グラフを示す情報（例えば、図９の斜向座標７を展開するための情報）と、地上レイヤ斜向座標グラフ上に生成した複数の周囲境界線との情報とを入力して、地上レイヤ斜向座標グラフ上の複数のクラスタのうち１つのクラスタの周囲境界線の範囲内に航空レイヤ斜向座標グラフの原点が配置されるように、地上レイヤ斜向座標グラフに対して航空レイヤ斜向座標グラフを配置する。また、航空レイヤ斜向座標グラフは、地上レイヤ斜向座標グラフに対して、図２５に示した高さＨを地上レイヤ斜向座標グラフの面から垂直方向に有するように航空レイヤ斜向座標グラフを配置する。そして、航空レイヤ斜向座標グラフ上に地上レイヤ斜向座標グラフ上の各クラスタの周囲境界線を投射して、クラスタ毎の投射した周囲境界線の範囲内に各クラスタに対応して飛行体局を配置する座標を決める。例えば、航空レイヤ斜向座標グラフ上には、図２６のようにメッシュ状に配置された点線が交差する点がある。この点は正六角形の中心点であって、「頂点」と呼ぶ。航空レイヤ斜向座標グラフ上に投射したクラスタ毎の周囲境界線の範囲内に含まれる頂点を、各クラスタに対応する飛行体局を配置する座標点とする。また、各クラスタに対応する飛行体局を配置する座標点を取り囲む周囲境界線を航空レイヤ斜向座標グラフ上に生成し、囲い込み処理部７０に渡す。
【００８４】
囲い込み処理部７０は、地上レイヤと航空レイヤで共通して使用する。周囲境界縮小部７３は、地上レイヤ斜向座標グラフ上の周囲境界線を周囲境界線の内側に移動させて周囲境界線が囲い込む範囲を縮小する縮小周囲境界線を、地上レイヤ斜向座標グラフ上に生成する。また、周囲境界縮小部７３は、航空レイヤ斜向座標グラフ上の周囲境界線を周囲境界線の内側に移動させて周囲境界線が囲い込む範囲を縮小する縮小周囲境界線を、航空レイヤ斜向座標グラフ上に生成する。
【００８５】
縮退規則情報記憶部７５は、航空レイヤ斜向座標グラフ上の縮小周囲境界線と、地上レイヤ斜向座標グラフ上の内側にそれぞれ仮想通信装置を配置させて、仮想通信装置上を通過する縮小周囲境界線を縮退させた縮退周囲境界線を生成する規則を示す縮退規則情報を記憶する。縮退規則情報は、航空レイヤ斜向座標グラフ用と地上レイヤ斜向座標グラフ用で共通であっても、異なっていてもかまわない。異なる場合には、航空レイヤ用であるのか地上レイヤ用であるのかを識別する識別情報を縮退規則情報に含める。
【００８６】
境界縮退部７７は、縮退規則情報記憶部７５が記憶する縮退規則情報に従い、仮想通信装置を航空レイヤ斜向座標グラフ上の縮小周囲境界線の内側に配置して、航空レイヤ斜向座標グラフ上の縮小周囲境界線の内側に配置する仮想通信装置を通過するように縮小周囲境界線を縮退させて、縮退周囲境界線を航空レイヤ斜向座標グラフ上に生成する。また、縮退規則情報記憶部７５が記憶する縮退規則情報に従い、仮想通信装置を地上レイヤ斜向座標グラフ上の縮小周囲境界線の内側に配置して、地上レイヤ斜向座標グラフ上の縮小周囲境界線の内側に配置する仮想通信装置を通過するように縮小周囲境界線を縮退させて、縮退周囲境界線を地上レイヤ斜向座標グラフ上に生成する。
【００８７】
経路設計部７９は、境界縮退部７７が生成した地上レイヤ斜向座標グラフ上の縮退周囲境界線と、ノード４０の座標点と、仮想通信装置の地上レイヤ斜向座標グラフ上の位置とから、中継ノードを配置する地上局のネットワークモデル上の位置を決定して、地上局のネットワークモデルのネットワーク経路を設計して地上局の経路情報を生成して出力する。また、経路設計部７９は、境界縮退部７７が生成した航空レイヤ斜向座標グラフ上の縮退周囲境界線と、飛行体局を配置する座標点と、仮想通信装置の航空レイヤ斜向座標グラフ上の位置とから、中継ノードを配置する飛行体局のネットワークモデル上の位置を決定して、飛行体局のネットワークモデルのネットワーク経路を設計して飛行体局の経路情報を生成して出力する。
【００８８】
経路情報融合部７８は、地上レイヤの経路情報と航空レイヤの経路情報とに基づいて、地上レイヤにおいて、地上局だけでは接続できないクラスタ間を飛行体局を介して接続するネットワーク経路情報を生成する。
【００８９】
図２８〜図３２を用いて、図３３の経路設計装置の処理の手順を示すフローチャートに従い、処理内容を説明する。
図２８（ａ）は、地上レイヤ配置処理部が地上レイヤ斜向座標グラフ上に地上局を配置した例を示す図である。図２８（ｂ）は、クラスタ生成部が地上レイヤ斜向座標グラフ上の地上局を複数のクラスタに分類した例を示す図ある。
図２９は、地上レイヤ斜向座標グラフに対して航空レイヤ斜向座標グラフを配置した例を示す図である。
図３０は、地上レイヤ斜向座標グラフ上のクラスタ毎の周囲境界線を航空レイヤ斜向座標グラフ上に投射した例を示す図である。
図３１（ａ）は、航空レイヤ斜向座標グラフ上にクラスタ毎に対応する飛行体局を配置した例を示す図である。図３１（ｂ）は、地上レイヤ斜向座標グラフ上の仮想ノードを配置した縮退周囲境界線の例を示す図である。
図３２は、航空レイヤ斜向座標グラフ上の仮想ノードを配置した縮退周囲境界線の例を示す図である。
【００９０】
図３３において、地上局のネットワークモデル１０ｇの有する複数のノード４０からそれぞれノードの位置を示す位置情報６０を、位置情報入力部５１により入力する（Ｓ１，位置情報入力工程）。位置情報６０は、緯度情報と経度情報とを有して、ノードの位置を表す。入力した位置情報６０は、フレームワーク処理部５３へ出力する。
【００９１】
フレームワーク処理部５３は、地上レイヤ斜向座標生成部５７ｇによって、例えば図９に示す斜向座標グラフを生成する（Ｓ２ｇ，地上レイヤ斜向座標生成工程）。
【００９２】
ここで、斜向座標生成手順を説明する。この手順は、地上レイヤ斜向座標グラフを生成する手順と、航空レイヤ斜向座標グラフを生成する手順とで共通である。ただし、航空レイヤ斜向座標グラフを生成する場合、第１の通信範囲情報に代えて第２の通信範囲情報を使用する。
はじめに、多角形を正六角形とする。正六角形とする理由は、実施の形態１で説明したように、六角形は電波伝搬を反映した円に近いためである。正六角形の辺を共有させて正六角形を隣接させて複数配置する。このとき、それぞれの正六角形は、中心点から辺までの垂直線の長さを第１の通信範囲情報の１／２とする。このように複数の正六角形を隣接して配置した図が図１２（ａ）である。次に、各正六角形の中心点同士を正六角形の辺を通過する線で結ぶ。正六角形の中心点を結んだ線を示した図が、図１３（ａ）である。図１３のように、中心点同士を結ぶ線は複数できる。この複数の線の中からｘ軸とする線と、ｙ軸とする線とをそれぞれ選択して、選択したそれぞれの線をｘ軸、ｙ軸とする斜向座標グラフを生成する。生成した斜向座標グラフの一例が図９の斜向座標７である。ｘ軸は、ノードの位置情報のうち、経度情報を距離に変換した値示す。ｙ軸は、ノードの位置情報のうち、緯度情報を距離に変換した値を示す。ｘ軸、ｙ軸のそれぞれの１目盛りは、第１の通信可能範囲であることが図１１からわかる。図２８〜図３２の地上局のネットワークモデル１０ｇは、地上レイヤ斜向座標グラフの一部を示したものであり、飛行体局のネットワークモデル１０ａは、航空レイヤ斜向座標グラフの一部を示したものである。
【００９３】
次に、フレームワーク処理部５３は、地上レイヤ配置処理部５９ｇによって、Ｓ１で入力したノード４０の位置情報から地上レイヤ斜向座標グラフ上の座標点を求めて、求めた座標点にノード４０を配置する（Ｓ３ｇ、地上レイヤ配置処理工程）。図２８（ａ）の●の地上局１ｇがノード４０である。求めた座標点が地上レイヤ斜向座標グラフ上の点線が交差する交点（頂点と呼ぶ）でない場合は、求めた座標点を直近の頂点の座標点に近似させる。
ここで、ノード４０の位置情報から座標点を求める一例を説明する。図４３は、位置情報から座標点を求める一例を説明する図である。経度１度分の距離は、極に近いほど短くなり、また、地球は真球ではく、表面は球面ではない等の種種の要素を考慮に入れると微妙な違いがあるが、経度１度分，緯度１度分のそれぞれ距離は約１１１ｋｍであるとする。例えば図４３に示すようにノードＡの位置情報が（東経１３９度，北緯３５度）、ノードＢの位置情報が（東経１４０度，緯度３６度）であるとする。これらの位置情報を図４３の経緯度への展開４３０のように、ノードＡの位置情報（東経１３９度，北緯３５度）を原点とするグラフ４３１（ｘ軸は経度、ｙ軸は緯度を示す）に配置する。次に、この経緯度に展開したものを図４３の直交座標への展開４３２のように、直交座標に展開する。このとき直交座標のｘ軸は東経方向を示し、１目盛りは１１．１ｋｍとし、ｙ軸は緯度方向を示し、１目盛りは１１．１ｋｍとする。ノードＡは原点であるため、座標は（０，０）となり、ノードＢはノードＡと緯度、経度ともに１度の差があるため、ノードＢの座標は（１０，１０）となる。次に、直交座標に展開したものを、地上レイヤの斜向座標グラフに展開する。地上レイヤの斜向座標グラフは六角形を元にして生成したグラフであるため、ｘ軸に対するｙ軸の傾きは６０度である。このため、斜向座標への展開には三角関数を用いる。図４３の直行座標でのノードＡの座標は（０，０）、ノードＢの座標は（１０，１０）であった。これらの座標を三角関数を用いて変換すると、図４３の斜向座標への展開４３４に示すように、地上レイヤの斜向座標グラフ（グラフ４３５）上には、ノードＡは原点であるためそのまま座標点は変わらずに（０，０）とし、ノードＢの座標は、（１０−１０／√３，１０×２／√３）、すなわち（１０×（１−１／√３），２０／√３）となる。これを小数で近似すると（４．２，１１．６）となり、さらに、整数で近似すると（４，１２）となる。
このとき、地上レイヤの斜向座標グラフのｘ軸は東経方向を示し、ｙ軸は北緯方向から３０度の方向を示す。このように、地上レイヤ配置処理部５９ｇは、ノードの位置情報を地上レイヤの斜向座標グラフ上の座標点に変換して、地上レイヤの斜向座標グラフ上に配置する。
【００９４】
図３３へ戻る。図３３のＳ３ｇでは、地上レイヤ配置処理部５９ｇが、図２８（ａ）のように８個の地上局のそれぞれの位置に対応する地上レイヤメッシュ７ｇ上の座標点を求め、求めた地上局１ｇの座標点を●として地上レイヤメッシュ７ｇ上に配置して、地上局のネットワークモデル１０ｇを生成する。
【００９５】
次に、Ｓ４ｇでは、クラスタ生成部５８により、地上レイヤメッシュ７ｇ上の８個の地上局１ｇを複数のクラスタに分けて、複数のクラスタ毎にクラスタに含まれる地上局を取り囲む周囲境界線を地上レイヤメッシュ７ｇ上に生成する。
【００９６】
図３５、図３６、図３７を用いて、クラスタ生成部５８の動作の一例を説明する。図３５は、マルチホップについて説明する図である。図３６（ａ）は、ホップ数を１とした場合の地上局それぞれのノード範囲（エリア）を示す図であり、図３６（ｂ）は、ホップ数を２とした場合の地上局それぞれのノード範囲（エリア）を示す図である。図３７は、クラスタ生成部５８によるクラスタ生成処理Ｓ４ｇを示す。
図３７において、クラスタ生成部５８のマルチホップ隣接ノードエリア生成部５８１は各地上局について、指定する最大ホップ数のマルチホップ隣接エリアを生成する（Ｓ２０、マルチホップ隣接ノードエリア生成工程）。このマルチホップ隣接エリアとは、例えば図３５の隣接ノード範囲１ＮＢ１，１ＮＢ２，１ＮＢ３を指す。隣接ノード範囲１ＮＢ１は、中央の地上局１Ｃから１目盛り（ホップ数１）の距離にある複数の１ホップ隣接ノードまでの範囲を示す。隣接ノード範囲１ＮＢ２は、地上局１Ｃから２目盛り（ホップ数２）の距離にある複数の２ホップ隣接ノードまでの範囲を示す。隣接ノード範囲１ＮＢ３は、地上局１Ｃから３目盛り（ホップ数３）の距離にある複数の３ホップ隣接ノードまでの範囲を示す。図３６にマルチホップ隣接ノードエリア生成部５８１が各地上局毎に生成したマルチホップ隣接エリアを示す。図３６（ａ）は、ホップ数を１とした場合の６個の地上局毎に生成した隣接ノード範囲を示す。図３６（ｂ）は、ホップ数を２とした場合の６個の地上局毎に生成した隣接ノード範囲を示す。図３６（ａ）では、近隣のノードが他のノードの１ホップ隣接ノード範囲１ＮＢ１に含まれていない。これは、１ホップでは、各ノードが他のノードを含まず、それぞれ独立する。図３６（ｂ）では、各ノードの２ホップ隣接ノード範囲１ＮＢ２を示す。図３６（ｂ）では、近隣のノードが他のノードの２ホップ隣接ノード範囲１ＮＢ２に含まれている。これは、２ホップにすると複数のノードを含むクラスタが生成できることを示す。そこでクラスタ生成部５８は、ホップ数を２として記憶する分類条件記憶部を備えるものとして、マルチホップ隣接ノードエリア生成部５８１が分類条件記憶部に記憶されたホップ数「２」に基づいて、地上局ごとの隣接ノード範囲を生成する。
【００９７】
クラスタ生成部５８のエリア和集合生成部５８２は、マルチホップ隣接ノードエリアのうち、他ノードを含むエリアの和集合をとり、出来た和集合を１つのクラスタとして、複数の地上局を複数のクラスタに分ける（Ｓ２１、エリア和集合生成工程）。例えば、マルチホップ隣接ノードエリア生成部５８１がホップ数を２として隣接ノード範囲を生成すると、図３６（ｂ）の６個のノード１を含む隣接ノード範囲１ＮＢ２が生成される。クラスタ生成部５８のエリア和集合生成部５８２は、他ノードを含むエリアの和集合として図３６（ｂ）の６個の隣接ノード範囲１ＮＢ２を隣接ノード範囲の和集合として生成する。生成し隣接ノード範囲の和集合の１つは、１つのクラスタに対応する。このようにして、クラスタ生成部８５は、地上レイヤメッシュの斜向座標７上の複数のノード１をクラスタに分類する。
【００９８】
クラスタ生成部５８は、図２８（ａ）の地上レイヤメッシュ７ｇ上に配置した８個の地上局１ｇを、ホップ数１として（クラスタ生成部５８は、ホップ数「１」を記憶する分類条件記憶部を備える）複数のクラスタに分類して、図２８（ｂ）のように、クラスタ２１を２つ生成する。そして、２つのクラスタ２１ごとに、クラスタに含まれる周囲境界線を、地上レイヤメッシュ７ｇ上にそれぞれ生成する。クラスタ毎の周囲境界線の生成動作は、実施の形態１で説明した図８のＳ１０及び図３の配置処理部５９と同じである。クラスタ生成部５８は、図２９に示すようにクラスタ毎に地上レイヤの周囲境界線３Ｂｇを、地上レイヤメッシュ７ｇ上に生成する。
【００９９】
次に、航空レイヤ配置処理部５９ａが、地上レイヤに対応して航空レイヤを配置して、配置した航空レイヤに各クラスタに対応した飛行体局を配置する（Ｓ３ａ，航空レイヤ配置処理工程）。まず航空レイヤ配置処理部５９ａは、クラスタ生成部８５から、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局の座標点と、複数のクラスタを示すとともに各クラスタが含む地上局の情報と、複数の地上レイヤの周囲境界線を地上レイヤの斜向座標グラフ上に示す情報とを入力する。また、航空レイヤ配置処理部５９ａは、航空レイヤ斜向座標生成部５７ａから、航空レイヤ斜向座標グラフを展開することができる情報を入力する。そして、入力した複数のクラスタを示す情報から、１つのクラスタを選択する。このクラスタの選択は、例えば位置情報入力部５１が地上局の位置情報を入力した際に一番電波が強い地上局を含むクラスタを選択する。あるいは、例えば部隊の隊員一人一人が地上局である通信端末装置を携帯しているような場合には、隊長が携帯している通信端末装置を含むクラスタを選択するようにしてもかまわない。この場合、隊長の通信端末装置の識別情報を予め経路設計装置５０に記憶しておくとともに、位置情報と一緒に通信端末装置の識別情報を入力する。入力した通信端末装置の識別情報は、各クラスタが含む地上局の情報に含めて航空レイヤ配置処理部５９ａが受け取る。航空レイヤ配置処理部５９ａは、各クラスタが含む地上局の情報に含まれた通信端末装置の識別情報から、記憶した隊長の通信端末装置の識別情報と一致する通信端末装置を含むクラスタを選択する。
【０１００】
航空レイヤ配置処理部５９ａは、このように選択した１つのクラスタの周囲境界線の取り囲む範囲内に、航空レイヤ斜向座標グラフの原点が配置されるように航空レイヤ斜向座標グラフの面を、地上レイヤ斜向座標グラフの面に対して垂直方向に高さＨを有して平行に配置する。例えば、図２９に示すように、選択した１つのクラスタの周囲境界線の取り囲む範囲内に含まれる１つの地上局１００ｇの座標点と航空レイヤ斜向座標グラフの原点１００ａとを合わせる。このとき、地上レイヤメッシュ７ｇ（地上レイヤ斜向座標グラフの面）に対して航空レイヤメッシュ７ａ（航空レイヤ斜向座標グラフの面）を平行に配置する。さらに、地上レイヤメッシュ７ｇ（地上レイヤ斜向座標グラフの面）の垂直方向に高さＨを有するように航空レイヤメッシュ７ａ（航空レイヤ斜向座標グラフの面）を配置する。この高さＨは、例えば飛行体局である無線通信端末装置を搭載する航空機の地上からの高度であり、高度は飛行体局の通信可能範囲が示す距離を越えない距離である。
【０１０１】
次に、各クラスタに対応させて飛行体局を航空レイヤメッシュ７ａ上に配置する動作を、図２９に示したネットワークモデル１０を例に説明する。航空レイヤ配置処理部５９ａは、航空レイヤメッシュ７ａ上に図２９の地上レイヤメッシュ７ｇ上の右側にあるクラスタ２１のクラスタの範囲を示す線、或いは、クラスタの周囲境界線を投射する。ここでは、図３０に示すように、図２９の右側のクラスタ２１の地上レイヤの周囲境界線３Ｂｇを投射する。図２９の左側のクラスタについては、このクラスタに対する飛行体局を航空レイヤ斜向座標グラフの原点１００ａに配置したため、クラスタの範囲を示す線、或いは、クラスタの周囲境界線を投射する処理は行わない。航空レイヤ配置処理部５９ａは、投射した周囲境界線の取り囲む範囲内の頂点（頂点とは、メッシュを構成する線と線とが交差する点である。例えば、図３０の航空レイヤメッシュ７ａの点線の交差する点である。）を飛行体局を配置する座標点とする。図３０では、座標点１０１ａを飛行体局１ａを配置する位置とする。座標点１０１ａは、図３０の地上レイヤメッシュ７ｇの右側にあるクラスタに対応する飛行体局を配置する座標点である。図３１（ａ）に、地上レイヤメッシュ上の２つのクラスタ２１にそれぞれ対応して、航空レイヤメッシュ７ａ上に配置する飛行体局１ａの座標点を示す。航空レイヤ配置処理部５９ａは、航空レイヤメッシュ７ａ上の飛行体局を配置する２つの座標点を取り囲む周囲境界線を航空レイヤメッシュ７ａに生成する。この周囲境界線を生成する処理は、実施の形態１で説明した図８のＳ１０及び図３の配置処理部５９と同じである。
【０１０２】
ここまで説明した図３３のＳ２ｇ〜Ｓ４ｇ及びＳ２ａ、Ｓ３ａの処理がフレームワーク処理部５３によるフレームワーク処理である。フレームワーク処理は、例えば磁気ディスク装置１４６のプログラム群１４９に記憶されたプログラムをフレームワーク処理部５３が実行することによって実現する。また、通信範囲情報記憶部５５、分類条件記憶部は、磁気ディスク装置１４６のファイル群１５０に記憶されている。フレームワーク処理部５３は、ＣＰＵ１３７であり、ＣＰＵ１３７は磁気ディスク装置１４６のプログラム群１４９からフレームワーク処理を行うプログラムを呼び出して、プログラムに従いＳ２ｇ〜Ｓ４ｇ及びＳ２ａ、Ｓ３ａのフレームワーク処理を行う。
【０１０３】
続いて、経路設計装置５０は、囲い込み処理部７０による図３３のＳ５ｇ、Ｓ５ａの囲い込み処理の手順について説明する。Ｓ５ｇ、Ｓ５ａの囲い込み処理の詳細な手順を図３４に示す。図３４に示したＳ１０〜Ｓ１３の処理内容は、実施の形態１で説明した図８のＳ１０〜Ｓ１３の処理内容と同様である。Ｓ１０の周囲境界線を生成する処理は、Ｓ４ｇのクラスタ生成部５８による地上レイヤメッシュ７ｇにクラスタごとの周囲境界線を生成する処理と、Ｓ３ａの航空レイヤ配置処理部５９ａによる航空レイヤメッシュ７ａに周囲境界線を生成する処理を指す。しかし、これらの周囲境界線を生成する処理は、囲い込み処理に含めてもかまわない。この場合、クラスタ生成部５８と航空レイヤ配置処理部５９ａとは、フレームワーク処理部５３と囲い込み処理部７０とで共有する。また、地上レイヤメッシュ７ｇ上と航空レイヤメッシュ７ａ上にそれぞれ生成した複数の周囲境界線を、それぞれのレイヤメッシュ別に周囲境界線を平行移動して範囲を縮小するＳ１１の処理と、縮小した周囲境界線を縮退するＳ１２の処理と、仮想ノードを中継ノードに変更して、中継ノードを含む経路設計情報とを生成する処理とは、地上局のネットワークモデルと飛行体局のネットワークモデルとで、別々に行う。言い換えると、周囲境界縮小部７３は、地上局のネットワークモデルに関連する情報として、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局の座標点と、複数のクラスタを示すとともに各クラスタが含む地上局の情報と、複数の地上レイヤの周囲境界線を地上レイヤの斜向座標グラフ上に示す情報とを入力する。そして、これら入力した情報から地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局の座標点と、複数のクラスタを示すとともに各クラスタが含む地上局の情報と、地上レイヤの複数の周囲境界線を地上レイヤの斜向座標グラフ上に示す情報と、地上レイヤの複数の周囲境界線をそれぞれ縮小した複数の縮小周囲境界線とを出力する。さらに、周囲境界縮小部７３は、飛行体局のネットワークモデルに関連する情報として、航空レイヤ斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局の座標点と、航空レイヤの周囲境界線を航空レイヤの斜向座標グラフ上に示す情報とを入力する。そして、これら入力した情報から航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局の座標点と、航空レイヤの周囲境界線を航空レイヤの斜向座標グラフ上に示す情報と、航空レイヤの周囲境界線を縮小した複数の縮小周囲境界線とを出力する。
【０１０４】
また、境界縮退部７７は、地上ネットワークモデルに関連する情報として、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局の座標点と、複数のクラスタを示すとともに各クラスタが含む地上局の情報と、複数の地上レイヤの縮小周囲境界線を地上レイヤの斜向座標グラフ上に示す情報とを入力する。そして、これら入力した情報から地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局と仮想ノードの座標点と、複数のクラスタを示すとともに各クラスタが含む地上局の情報と、地上レイヤの複数の縮小周囲境界線をそれぞれ、縮退規則情報記憶部７５に記憶した縮退規則情報に従い縮退した複数の縮退周囲境界線とを出力する。さらに、境界縮退部７７は、飛行体局のネットワークモデルに関連する情報として、航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局の座標点と、航空レイヤの縮小周囲境界線を航空レイヤの斜向座標グラフ上に示す情報とを入力する。そして、これら入力した情報から航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局と仮想ノードの座標点と、航空レイヤの縮小周囲境界線をそれぞれ、縮退規則情報記憶部７５に記憶した縮退規則情報に従い縮退した縮退周囲境界線とを出力する。縮退規則情報記憶部７５が記憶する縮退規則情報は、１つの縮退規則情報を記憶して、境界縮退部７７が地上ネットワークモデルと、航空ネットワークモデルとで、同じ縮退規則情報に従いそれぞれの縮小周囲境界線を縮退させる。または、地上局のネットワークモデルと、飛行体局のネットワークモデルとで、異なる縮退規則情報を記憶して、境界縮退部７７が地上局のネットワークモデルと、飛行体局のネットワークモデルとで、それぞれ用の縮退規則情報に従い縮小周囲境界線を縮退させる。
【０１０５】
図３１（ｂ）は、地上局のネットワークモデル１０ｇの地上レイヤメッシュ７ｇ上と飛行体局のネットワークモデル１０ａの航空レイヤメッシュ７ａ上に縮退規則情報に従い仮想ノード１Ｖｇ、１Ｖａを配置した例を示す図である。図３１（ｂ）に示すように、仮想ノード１Ｖａを配置することによって、２つの飛行体局１ａ間は、２つのリンクで接続される。
【０１０６】
経路設計部７９は、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局と仮想ノードの座標点と、複数のクラスタを示すとともに各クラスタが含む地上局と仮想局の情報と、地上レイヤの複数の縮小周囲境界線をそれぞれ、縮退規則情報記憶部７５に記憶した縮退規則情報に従い縮退した複数の縮退周囲境界線とを入力する。そして、これらの入力した情報から、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局と中継ノードの座標点と、複数のクラスタを示すとともに各クラスタが含む地上局と中継局の情報と、地上レイヤの複数の縮退周囲境界線と、地上局と中継ノードとの間のリンクを示す情報とを出力する。さらに、経路設計部７９は、航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局と仮想ノードの座標点と、航空レイヤの縮小周囲境界線をそれぞれ、縮退規則情報記憶部７５に記憶した縮退規則情報に従い縮退した縮退周囲境界線とを入力する。そして、これらの入力した情報から、航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局と中継ノードの座標点と、航空レイヤの縮退周囲境界線と、飛行体局と中継ノードとの間のリンクを示す情報とを出力する。
【０１０７】
図３１（ｂ）を例にすると、経路設計部７９は、地上レイヤメッシュ７ｇと航空レイヤメッシュ７ａとをそれぞれ展開することができる情報と、地上レイヤメッシュ上の２つのクラスタを示す情報及び、それぞれのクラスタとそれぞれのクラスタが含む地上局１ｇの座標点と仮想ノード１Ｖｇの座標点と縮退周囲境界線とを示す情報と、航空レイヤメッシュ上の飛行体局１ａの座標点と仮想ノード１Ｖａの座標点と縮退周囲境界線とを示す情報とを出力する。
このように、囲い込み処理部７０の各構成要素は、地上局のネットワークモデル用の処理と、飛行体局のネットワークモデル用の処理との２つの処理を行う。
【０１０８】
図３３に戻る。図３３のＳ６では、経路情報融合部７８は、地上局のネットワークモデルに関する情報と、飛行体局のネットワークモデルに関する経路情報８０Ｐとを入力する。例えば、地上局のネットワークモデルに関する情報として、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局と中継ノードの座標点と、複数のクラスタを示すとともに各クラスタが含む地上局と中継局の情報と、地上レイヤの複数の縮退周囲境界線と、地上局と中継ノードとの間のリンクを示す情報とを入力する。さらに、飛行体局のネットワークモデルに関する情報として、航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局と中継ノードの座標点と、航空レイヤの縮退周囲境界線と、飛行体局と中継ノードとの間のリンクを示す情報とを入力する。そして、これらの入力した情報から、地上局のネットワークモデルの２つのクラスタの間を、飛行体局のネットワークモデルを介して接続する。飛行体局のネットワークモデルを介する接続とは、各クラスタ毎に、各クラスタに対応する飛行体局と、そのクラスタに含まれる地上局とをリンクして接続する。例えば図３２のネットワークモデル１０を例に、地上局のネットワークモデルと飛行体局のネットワークモデルとを、地上局のネットワークモデルの複数のクラスタ間を飛行体局のネットワークモデルを介して接続するネットワーク経路情報の生成について説明する。
【０１０９】
経路情報融合部７８は、１つのクラスタとそのクラスタに対応する飛行体局との間を２つのリンクで接続する。２つのリンクとは１つの飛行体局を２つの地上局で接続して１つの地上局から飛行体局への経路を２経路とすることである。例えば経路情報融合部７８は、図３２の２つの飛行体局のそれぞれの飛行体局１ａ毎に、各飛行体局に対応するクラスタが含む複数の地上局の内、２つの地上局とのリンク２を生成する。２つの地上局とのリンクを接続することによって、一方の地上局が通信できなくなっても、他方の地上局とのリンクを使用して、地上局と飛行体局間との通信を行うことができる。複数の地上局のうち飛行体局と接続する地上局は、いずれの地上局を選択しても構わない。例えば、電波の強い地上局から順に優先して選択する。または、クラスタが部隊を構成するような場合には、部隊の隊長が携帯している通信端末装置と副隊長が携帯している通信端末装置とを、経路情報融合部７８が優先して選択する。この場合、あらかじめ隊長と副隊長がそれぞれ携帯する通信端末装置の識別情報を経路設計装置５０が記憶しておく。また、位置情報とともに、通信端末装置の識別情報を入力する。入力した通信端末装置の識別情報は、通信端末装置（地上局）の座標点を示す情報に対応させて、経路設計装置が備える記憶装置に記憶しておく。経路情報融合部７８は、クラスタが含む複数の地上局の座標点から、座標点に対応する通信端末装置の識別情報を取得する。そして、取得した識別情報に基づいて、あらかじめ記憶しておいた隊長あるいは副隊長がそれぞれ携帯する通信端末装置の識別情報と一致することを確認して、一致することが確認できたら、確認できた２つの地上局を、飛行体局とリンクする地上局として選択する。
このように、地上レイヤと航空レイヤの２つの異なるレイヤそれぞれに配置した複数の局（ノード）をリンクする経路を生成することを融合という。
【０１１０】
融合を行った結果生成されるネットワーク経路情報（経路情報８０Ｔ）は、例えば、図３２の例では、地上レイヤメッシュ７ｇ上の地上局１ｇの座標点と中継ノード１Ｒｇの座標点、地上レイヤの周囲境界線３Ｂｇ、航空レイヤメッシュ７ａ上の飛行体局１ａの座標点と中継ノード１Ｒａの座標点、航空レイヤの周囲境界線３Ｂａ、地上局と飛行体局とのリンク２とである。また、高さＨもネットワーク経路情報（経路情報８０Ｔ）に含める。
【０１１１】
この実施の形態の経路設計装置は、多角形グリッド、双対グラフメッシュ、斜向座標によるネットワーク設計フレームワークを複数階層構造で用いることにより、例えば人が携帯する無線通信端末装置（地上局）を配置する面を地上レイヤとし、飛行体が搭載する無線通信端末装置（飛行体局）を配置する面を航空レイヤとした場合、広域に渡って配置された地上局が移動し、リンクが定まっていない場合でも、飛行体局を経由して地上局を接続する複数の経路、および中継ノードを設計できるという効果がある。
また、厳密に最適経路を求めるためには、全ノードの組み合わせを検証する膨大な処理を必要とするネットワーク設計であるが、この発明の複数階層にわたる囲い込みアルゴリズムにより、簡便に広域に渡って配置された全ノード間を２本以上の経路で接続する経路を求めることができる。これにより、航空機などの飛行体により中継を行なって、広域にわたって配置するノード間の通信経路を設定する場合、一個の通信経路を確保するだけでなく、複数の独立経路を設計し、障害時の迂回経路を確保することができる。
【０１１２】
実施の形態７．
上記実施の形態６では、地上レイヤメッシュの面に対して航空レイヤメッシュの面を配置した際に、地上レイヤメッシュのクラスタを航空レイヤメッシュ上に投射すると、航空レイヤメッシュ上の頂点（点線で示した複数のメッシュの交差する交点）がクラスタの取り囲む範囲内に少なくとも１つ存在していた。しかし、航空レイヤメッシュ上の頂点（点線で示した複数のメッシュの交差する交点）がクラスタの取り囲む範囲内に存在していない場合がある。この場合には、頂点がクラスタの取り囲む範囲に内に存在するように航空レイヤメッシュの面を移動して、地上レイヤメッシュの面に対する航空レイヤメッシュの面の位置を調整をする。
【０１１３】
図３８は、実施の形態７の航空レイヤメッシュ上に投射したクラスタの取り囲む範囲内に頂点が存在しない例を示す図である。図３８のクラスタ２１の中心点２１ｃの方向に航空レイヤメッシュ７ａ上の頂点がずれるように航空レイヤメッシュ７ａの面を移動して、頂点がクラスタの取り囲む範囲に内に存在するように航空レイヤメッシュの面の位置を調整する。
図３９は、実施の形態７の経路設計装置の構成を示すブロック図である。航空レイヤ配置処理部５９ａが調整部５９１を備えることの他は、実施の形態６の図２７の経路設計装置と同様の構成である。航空レイヤ配置処理部５９ａは、航空レイヤメッシュ上に投射したクラスタの取り囲む範囲内に頂点が存在しない場合に、調整部５９１によりクラスタ２１の中心点２１ｃの方向に航空レイヤメッシュ７ａ上の頂点がずれるように航空レイヤメッシュ７ａの面移動する。
図４０は、調整部５９１の動作手順を示すフローチャート図である。
図４１は、調整部５９１の別の動作手順を示すフローチャート図である。
まず、図４０のフローチャートに従い調整部５９１による航空レイヤメッシュの面を移動する手順を説明する。なお、図４０及び図４１に示した動作は、図３３のＳ３ａの航空レイヤ配置処理工程の中で、航空レイヤメッシュ上に投射した複数のクラスタの中に、クラスタの取り囲む範囲内に頂点が存在しないクラスタがある場合に行う。
【０１１４】
図４０の調整部５９１の処理は、調整を行うときの基準に使用するクラスタの中心点に、その中心点に近い位置の航空レイヤメッシュ上の頂点（この頂点を他の頂点と区別するため「頂点Ａ」と呼ぶ）を合わせる。図２６に示すように、航空レイヤメッシュ７ａの１マスの大きさ（１マスとは図２６の飛行体局１ａを中心点とする正六角形のことである）は、地上レイヤメッシュの１マス（１マスとは図２６の地上局１ｇを中心点とする正六角形のことである）の複数分である。調整部５９１は、航空レイヤメッシュ１マスが含む複数のマス目の各中心点に頂点Ａを順次移動させて、頂点Ａの最適位置を探す。最適位置とは、地上レイヤメッシュ上の複数のクラスタを航空レイヤメッシュ上に投射した場合に、投射した各クラスタの取り囲む範囲内に、航空レイヤメッシュ上の頂点が含まれる場合の地上レイヤメッシュに対する航空レイヤメッシュの位置をさす。
【０１１５】
図４０において、調整部５９１は、地上レイヤメッシュ上の複数のクラスタごとに、各クラスタの中心点２１ｃを求める。この中心点２１ｃは、クラスタ毎に、各クラスタが含む複数の地上局の座標点から求められる平均の座標点とする（ＳＡ０）。次に、クラスタ毎に求めた複数の中心点２１ｃの中から１つの中心点２１ｃを選択する。選択した中心点２１ｃの座標点に一番近い位置にある航空レイヤメッシュ上の頂点を合わせて、航空レイヤメッシュの初期位相を設定する（ＳＡ１）。この頂点が頂点Ａである。１つの中心点を選択する条件は、例えば、電波の一番強い地上局を含むクラスタの中心点を選択したり、クラスタの取り囲む範囲が一番大きいクラスタの中心点を選択するなどの条件をあらかじめ経路設計装置の記憶部に記憶させておき、記憶部に記憶した条件を調整部５９１が取得する。または、条件は設けず、ランダムに１つのクラスタの中心点を選択しても構わない。初期位相の設定を行った後、ＳＡ２では、クラスタ毎に、クラスタを航空レイヤメッシュに投射した場合の各クラスタの中心点２１ｃと中心点２１ｃに一番近い航空レイヤメッシュ７ａ上の頂点との距離を求める。クラスタ毎の求めた距離と中心点２１ｃと頂点Ａの座標とを対応させて、経路設計装置の記憶部に記憶する。続いて、ＳＡ３では、航空レイヤメッシュ７ａの頂点Ａを、選択したクラスタの取り囲む範囲内にある地上レイヤメッシュ７ｇの別のマスの中心点にずらす。上記したＳＡ２とＳＡ３の処理とを、選択したクラスタの取り囲む範囲内にある全てのマスの中心点に頂点Ａを移動させるまで繰り返す（ＳＡ４）。ＳＡ２、ＳＡ３の処理の繰り返しが終了したら、ＳＡ２で記憶したクラスタ毎の求めた距離から全クラスタの平均の距離を、頂点Ａの座標毎に求めて、求めた全クラスタの平均の距離のうち最小の平均距離を検索して、検索できた最小のクラスタ平均距離の頂点Ａの座標を、ＳＡ１で選択したクラスタの中心点に合わせて、航空レイヤメッシュを地上レイヤメッシュに対して配置する。
【０１１６】
また、別の調整部５９１の処理手順を図４１のフローチャートに従い説明する。図４１の調整部５９１に処理では、航空レイヤメッシュ上に投射した複数のクラスタ毎に各クラスタの中心点からその中心点に一番近い位置にある頂点までの距離を求める（ＳＡ１０）。そして、各クラスタ毎に求めた距離から、全クラスタ平均の距離を求め（ＳＡ１１）、求めた全クラスタ平均の距離をＳＡ１０で使用した頂点の座標とともに、経路設計装置の記憶部の有するテーブルに記憶する（ＳＡ１２）。各クラスタ毎に求めた距離と、全クラスタ平均の距離との差をクラスタ毎に求めて、差が一番大きいクラスタを選択する（ＳＡ１３）。ＳＡ１３で求めた差を所定の数、例えば１０で割り、その商を調整部５９１の調整値とする（ＳＡ１４）。商である調整値分の距離だけ、ＳＡ１３で選択したクラスタの中心点へＳＡ１０の頂点を移動するように航空レイヤメッシュの面を地上レイヤメッシュの面に対してずらす（ＳＡ１５）。ＳＡ１５の後、複数のクラスタ毎に、各クラスタの中心点を求める（ＳＡ１６）。複数のクラスタ毎に、求めたクラスタの中心点からその中心点に一番近い位置にある頂点までの距離を求める（ＳＡ１７）。そして、各クラスタ毎に求めた距離から、全クラスタ平均の距離を求め各クラスタ毎に求めた距離から、全クラスタ平均の距離を求め、求めた全クラスタ平均の距離を、ＳＡ１７で距離の計算に使用した頂点の座標点とともに経路設計装置の記憶部の有するテーブルに記憶する（ＳＡ１８）。ＳＡ１５からＳＡ１８の処理を、ＳＡ１４の差を割った値の回数、例えば１０回、繰り返す（ＳＡ１９）。繰り返しが完了したら、記憶部の有するテーブルに記憶した全クラスタ平均の距離から、最も小さい値を検索して、検索できた値に対応する頂点の座標点にＳＡ１０の頂点を移動させて、航空レイヤメッシュを地上レイヤメッシュに対して配置する。なお、クラスタの中心点の求め方は、図４０と同様である。
このようにして、調整部５９１は、地上レイヤメッシュに対する航空レイヤメッシュの位置を調整する。ＳＡ１９及びＳＡ１４では「１０」を使用したが、これに限らず、「１０」よりも大きい値や小さい値を任意に設定して使用出来る。
【０１１７】
なお、調整部５９１を備えない場合であって、クラスタの取り囲む範囲内に航空レイヤメッシュの頂点が存在しない場合、航空レイヤメッシュのメッシュを構成する線上にクラスタ間を中継する飛行体局を配置して、さらに、その飛行体局を配置した座標点に近い航空レイヤメッシュの頂点に中継用のノードを配置して、クラスタの取り囲む範囲内に航空レイヤメッシュの頂点が存在しない場合の飛行体局によるクラスタの中継をサポートできる。ただしこの場合には、必要な飛行体局を搭載する飛行体を、調整部を備える場合よりも多くの数必要となるため、ネットワークの構築に費用がかかる。
【０１１８】
この実施の形態の経路設計装置は、調整部を備えたことにより、クラスタの取り囲む範囲内に航空レイヤメッシュ状の頂点が存在しないクラスタが存在しても、航空レイヤメッシュの面を地上レイヤメッシュの面に対して移動させて、クラスタの取り囲む範囲内に航空レイヤメッシュ状の頂点が存在するようにする。このため、各クラスタは飛行体局によって他のクラスタとのリンクの接続を確実行うことが可能となる効果がある。
【０１１９】
実施の形態８．
実施の形態６では、地上レイヤメッシュの面に対して垂直方向に高さＨを有して、地上レイヤメッシュの面に平行に航空レイヤメッシュの面を配置した。この実施の形態７では、地上レイヤメッシュの面と同一平面状に航空レイヤメッシュの面を配置する例を説明する。
【０１２０】
図４２は、この実施の形態の第１層目の地上レイヤメッシュ４ｇに対して、第１層目の地上レイヤメッシュ４ｇの面と同一平面上に第２層目の地上レイヤメッシュ４０ｇを配置した例を示す図である。第２層目の地上レイヤメッシュ４０ｇは、地上局の双対グラフメッシュ６０ｇ上にあって、地上局のネットワークモデル１０００ｇを構成する。複数の双体グラフメッシュを図４２のような配置にする運用例としては、部隊員が携帯する無線通信端末装置間の通信を、車両に搭載した無線通信端末装置により中継する場合がある。この運用例では、クラスタは大部隊を構成する複数の小部隊に相当し、広域に散らばって作業を行う小部隊のクラスタ間の通信を、車両に搭載した無線通信端末装置で中継するネットワーク経路情報を、実施の形態６の図２７と同様の構成の経路設計装置により生成する。第１層目の地上レイヤメッシュには、部隊員が携帯する無線通信端末装置を地上局１ｇに配置して、第２層目の地上レイヤメッシュには、車両に搭載する無線通信端末装置を地上局１０２ｇに配置する。また、第１層目の地上レイヤメッシュの面に対して第２層目の地上レイヤメッシュの面を配置する場合、クラスタは第１層目の地上レイヤメッシュ上に配置され、第１層目の地上レイヤメッシュ上の複数のクラスタから１つのクラスタを選択する。そして、選択したクラスタが含む複数の部隊員がそれぞれ携帯する無線通信端末装置のうち１つの無線通信端末装置の位置を、第１層目の地上レイヤメッシュの面から第１層目の地上レイヤメッシュの面に対して水平に移動させた方向に第２層目の地上レイヤメッシュの原点を配置する。また、第１層目の経路情報と、第２層目の経路情報を融合する場合、第１層目の無線通信装置と第２層目の無線通信装置とは、実施の形態６のように高さＨを有さない同一面上でのリンクを接続する。
【０１２１】
このように、実施の形態８では、第１層目のグラフと第２層目のグラフとを同一面上に配置するので、異なる通信可能範囲を有する無線通信端末装置ではあるが、「緯度，経度，高さ」の「高さ」が同じである無線通信端末装置を複数の層に分けて、層ごとの経路情報を生成して、層ごとの経路情報を融合して、通信可能範囲が狭い無線通信端末間のリンクを、通信可能範囲の広い無線通信端末装置で中継するためのネットワーク経路情報を生成できる効果がある。
【０１２２】
実施の形態９．
この実施の形態では、通信範囲情報を時刻に対応させる経路設計装置、経路設計方法の一例を説明する。
【０１２３】
位置情報入力部５１は、ネットワークモデルを構成する通信装置（ノード）が自己の位置情報を算出した際の時刻を示す時刻情報を位置情報に含めて発信した位置情報を受信する。或いは、位置情報に含まれる時刻情報は、例えば自己の位置を算出する際に使用する衛星から発信される測位信号に含まれる測位時刻情報でもかまわない。通信範囲情報記憶部５５は、第１の通信可能範囲を時刻に対応させて記憶する通信範囲情報を記憶する。また、地上レイヤ斜向座標生成部５７ｇは、位置情報の有する時刻情報を入力して、時刻情報に対応する通信可能範囲を通信範囲情報記憶部５５から取得して、取得した時刻情報に対応する通信可能範囲の斜向座標グラフを生成する。なお、位置情報入力部５１は複数のノードから異なる時刻情報を有する位置情報を入力し、時刻情報に対応する通信可能範囲は同じ場合と異なる場合とがある。通信可能範囲が異なる場合には、例えば、通信可能範囲の平均値を算出して、平均値を斜向座標グラフの生成に使用する。経路設計装置５０の他の要素は、上記実施の形態６と同様であるものとする。
【０１２４】
以上のように、第１の通信可能範囲を時刻に対応させることにより、ネットワークモデルの通信経路を設計する際の時刻における通信環境に合ったネットワーク経路を設計することができる。
【０１２５】
実施の形態１０．
実施の形態６では、図２６に示すように正六角形を使用して、第１及び第２のグラフを斜向座標グラフとして生成した。しかし、四角形を使用して、第１及び第２のグラフを生成しても構わない。この場合、第１及び第２のグラフは、ｙ軸がｘ軸に対して直角になる。実施の形態１〜９の斜向座標グラフは、ｙ軸がｘ軸に対して直角になるグラフを斜向座標グラフに含めるものとする。
【０１２６】
このように、実施の形態１０では、第１及び第２のグラフは、六角形或いは四角形を使用して生成することができるので、経路設計者が六角形と四角形とのいずれか一方を選択して、ネットワーク経路情報を生成できる効果がある。
【０１２７】
実施の形態１１．
実施の形態６では、地上レイヤと航空レイヤの２層のネットワークモデルを１つのネットワークモデルに融合する例を説明した。しかし、地上レイヤと航空レイヤの他に、水上レイヤであったり、衛星レイヤであっても、複数の層を構成すれば構わない。また、複数の層にそれぞれ配置される１つの局（ノード）は２つのリンクで接続して、一方のリンクに障害が発生した場合であっても、他方のリンクを使用することによって通信が可能になるネットワーク経路設計情報を生成する。図４４は、２層によるネットワークモデルの経路を説明する図である。このように、従来では、２層のネットワークモデルであっても、航空レイヤでは、飛行体局間は１つのリンクで接続されているので、障害が発生すると通信が行えなくなるという問題がある。実施の形態６では、このような問題点を解決しているが、クラスタ間の通信を中継する中継用の無線通信端末装置を配置する層が、例えば、航空レイヤメッシュであったり、水上レイヤメッシュであったり、衛星レイヤメッシュであると、無線通信端末装置を搭載する機器のコストがかかる。このため、障害時の通信経路の確保よりも、コストを優先するような場合には、中継用の無線通信端末装置を配置する層では、無線通信端末装置間のリンクを１つにしても構わない。
【図面の簡単な説明】
【０１２８】
【図１】（ａ）は、この発明のアドホックネットワークのモデルを示し、（ｂ）はネットワーク設計方法の概要を示す図である。
【図２】（ａ）〜（ｃ）は、特開２００２−３３５１９２等に示された、従来の有線通信経路の二重化により、サバイバビリティ（障害発生時にもサービスを提供する機能）を確保する方法を示す模式図である。
【図３】実施の形態１の経路設計装置を構成する要素の一例を示すブロック図である。
【図４】実施の形態１の通信範囲情報記憶部５５が記憶する通信範囲情報の一例を示す図である。
【図５】実施の形態１における経路設計装置の外観を示す図である。
【図６】実施の形態１における経路設計装置のハードウェア構成図である。
【図７】実施の形態１のフレームワーク処理部による斜向座標グラフ上に通信装置の位置を配置する処理のフローチャート図である。
【図８】実施の形態１の囲い込み処理部によるネットワークの経路設計情報を生成して出力する処理のフローチャート図である。
【図９】斜向座標グラフの一例を示す図である。
【図１０】ノードから電波の到達する通信可能範囲５を球で示す図である。
【図１１】円を多角形、例えば六角形に置き換え、通信可能範囲５を１／２に縮退させてネットワークモデルを六角形方眼で示した図である。
【図１２】多角形方眼の一例を示す図であり、（ａ）は六角形、（ｂ）は四角形、（ｃ）は三角形の方眼を示す。
【図１３】図１２（ａ）、（ｂ）、（ｃ）のそれぞれの多角形方眼に対応する双対グラフメッシュを示す図であり、（ａ）は三角メッシュ、（ｂ）は四角メッシュ、（ｃ）は六角メッシュの方眼を示す。
【図１４】（ａ），（ｂ）は囲い込み（Ｅｎｃｌｏｓｕｒｅ）アルゴリズムの実行状況の経過を説明する図である。
【図１５】（ａ），（ｂ）、（ｃ）は囲い込み（Ｅｎｃｌｏｓｕｒｅ）アルゴリズムの実行状況の経過を説明する図である。
【図１６】（ａ），（ｂ）、（ｃ）は縮退規則情報に従う詳しい周囲境界線の縮退方法を説明する図である。
【図１７】（ａ），（ｂ）は実施の形態１の経路設計装置５０による経路設計の利用形態を示す図である。
【図１８】実施の形態２の経路設計装置を構成する要素の一例を示すブロック図である。
【図１９】実施の形態２の通信範囲情報記憶部５５が記憶する通信範囲情報の一例を示す図である。
【図２０】実施の形態３の経路設計装置を構成する要素の一例を示すブロック図である。
【図２１】実施の形態３の通信範囲情報記憶部５５が記憶する通信範囲情報の一例を示す図である。
【図２２】実施の形態４の経路設計装置を構成する要素の一例を示すブロック図である。
【図２３】実施の形態４の通信範囲情報記憶部５５が記憶する通信範囲情報の一例を示す図である。
【図２４】実施の形態５の経路設計装置を構成する要素の一例を示すブロック図である。
【図２５】実施の形態６のアドホックネットワークの２層構造のモデルを示す図である。
【図２６】実施の形態６のネットワーク設計方法に使用する２層構造のネットワークモデルを示す図である。
【図２７】実施の形態６の経路設計装置を構成する要素の一例を示すブロック図である。
【図２８】（ａ）は、実施の形態６の地上レイヤ配置処理部が地上レイヤ斜向座標グラフ上に地上局を配置した例を示す図である。（ｂ）は、クラスタ生成部が地上レイヤ斜向座標グラフ上の地上局を複数のクラスタに分類して、クラスタ毎の周囲境界線を生成した例を示す図ある。
【図２９】実施の形態６の地上レイヤ斜向座標グラフに対して航空レイヤ斜向座標グラフを配置した例を示す図である。
【図３０】実施の形態６の地上レイヤ斜向座標グラフ上のクラスタ毎の周囲境界線を航空レイヤ斜向座標グラフ上に投射した例を示す図である。
【図３１】（ａ）は、航空レイヤ斜向座標グラフ上にクラスタ毎に対応する飛行体局を配置した例を示す図である。（ｂ）は、地上レイヤ斜向座標グラフ上の仮想ノードを配置した縮退周囲境界線の例を示す図である。
【図３２】実施の形態６の航空レイヤ斜向座標グラフ上の仮想ノードを配置した縮退周囲境界線の例を示す図である。
【図３３】実施の形態６の経路設計装置の処理の手順を示すフローチャート図である。
【図３４】図３３のＳ５ｇ、Ｓ５ａの囲い込み処理の詳細な手順を示すフローチャート図である。
【図３５】実施の形態６のマルチホップについて説明する図である。
【図３６】（ａ）は、ホップ数を１とした場合の地上局それぞれのノード範囲（エリア）を示す図である。（ｂ）は、ホップ数を２とした場合の地上局それぞれのノード範囲（エリア）を示す図である。
【図３７】実施の形態６のクラスタ生成部５８によるクラスタ生成処理Ｓ４ｇを示すフローチャート図である。
【図３８】実施の形態７の航空レイヤメッシュ上に投射したクラスタの取り囲む範囲内に頂点が存在しない例を示す図である。
【図３９】実施の形態７の経路設計装置の構成を示すブロック図である。
【図４０】実施の形態７の調整部５９１の動作手順を示すフローチャート図である。
【図４１】実施の形態７の調整部５９１の別の動作手順を示すフローチャート図である。
【図４２】この実施の形態８の第１層目の双体グラフメッシュ６０ｇに対して、第１層目の双体グラフメッシュ６０ｇの面と同一平面上に第２層目の双体グラフメッシュ６０ａを配置した例を示す図である。
【図４３】実施の形態６のノードの位置情報から座標点を求める一例を説明する図である。
【図４４】２層によるネットワークモデルの経路を説明する図である。
【符号の説明】
【０１２９】
１，１Ｓ，１Ｄ，４０  ノード、１Ｒ，１Ｒａ，１Ｒｇ  中継ノード、１ａ  飛行体局、１Ｃ，１ｇ，１００ｇ  地上局、１ＮＢ１，１ＮＢ２，１ＮＢ３  隣接ノード範囲、１Ｖ，１Ｖａ，１Ｖｇ  仮想ノード、１Ｗ  和集合、２，２ａ，２ｇ  リンク、３ａ，３ｂ，３ｃ，３ｄ，３１，３２，３３  経路、３Ｂ  周囲境界線、３Ｂａ  航空レイヤの周囲境界線、３Ｂｇ  地上レイヤの周囲境界線、３Ｈａ  飛行体局間経路、３Ｈｇ  地上局間経路、４  六角形方眼、４ａ  航空レイヤメッシュ、４ｇ，４０ｇ  地上レイヤメッシュ、５，５ａＬ  通信可能範囲、５ａＲ  地上局１ｇからなるネットワーク層への投射、６  双対グラフメッシュ、６ａ  飛行体局の双対グラフメッシュ、６ｇ，６０ｇ  地上局の双対グラフメッシュ、７  斜向座標、７ａ  航空レイヤメッシュ、７ｇ  地上レイヤメッシュ、１０  ネットワークモデル、１０ａ  飛行体局のネットワークモデル、１０ｇ，１０００ｇ  地上局のネットワークモデル、２１  クラスタ、２１ｃ  中心点、５０  経路設計装置、５１  位置情報入力部、５３  フレームワーク処理部、５５  通信範囲情報記憶部、５７  斜向座標生成部、５７ａ  航空レイヤ斜向座標生成部、５７ｇ  地上レイヤ斜向座標生成部、５９  配置処理部、５９ａ  航空レイヤ配置処理部、５９ｇ  地上レイヤ配置処理部、６０，６１，６２  位置情報、７０  囲い込み処理部、７３  周囲境界縮小部、７５  縮退規則情報記憶部、７７  境界縮退部、７８  経路情報融合部、７９  経路設計部、８０，８０Ｐ，８０Ｔ  経路情報、９１  電波強度測定部、９３  アンテナ、９４  受信位置算出部、９５  測位受信部、９７  位置算出部、１００ａ  航空レイヤ斜向座標グラフの原点、１０１ａ  座標点、１０２ｇ  地上局、１３７  ＣＰＵ、１３８  バス、１３９  ＲＯＭ、１４０  ＲＡＭ、１４１  ＣＲＴ表示装置、１４２  Ｋ／Ｂ、１４３  マウス、１４４  通信ボード、１４５  ＦＤＤ、１４６  磁気ディスク装置、１４７  ＯＳ、１４８  ウィンドウシステム、１４９  プログラム群、１５０  ファイル群、１８６  ＣＤＤ、１８７  プリンタ装置、１８８  スキャナ装置、２００  システムユニット、２０１  衛星群、２０２  静止衛星、２０３  ＧＰＳ衛星、２０４  準天頂衛星、３１０  ＦＡＸ機、３２０  電話器、５００  ウェブサーバ、５０１  インターネット、５０５  ＬＡＮ、５８１  マルチホップ隣接ノードエリア生成部、５８２  エリア和集合生成部、５９１  調整部。
【図１】
2006101497.tif 000003
【図２】
2006101497.tif 000004
【図３】
2006101497.tif 000005
【図４】
2006101497.tif 000006
【図５】
2006101497.tif 000007
【図６】
2006101497.tif 000008
【図７】
2006101497.tif 000009
【図８】
2006101497.tif 000010
【図９】
2006101497.tif 000011
【図１０】
2006101497.tif 000012
【図１１】
2006101497.tif 000013
【図１２】
2006101497.tif 000014
【図１３】
2006101497.tif 000015
【図１４】
2006101497.tif 000016
【図１５】
2006101497.tif 000017
【図１６】
2006101497.tif 000018
【図１７】
2006101497.tif 000019
【図１８】
2006101497.tif 000020
【図１９】
2006101497.tif 000021
【図２０】
2006101497.tif 000022
【図２１】
2006101497.tif 000023
【図２２】
2006101497.tif 000024
【図２３】
2006101497.tif 000025
【図２４】
2006101497.tif 000026
【図２５】
2006101497.tif 000027
【図２６】
2006101497.tif 000028
【図２７】
2006101497.tif 000029
【図２８】
2006101497.tif 000030
【図２９】
2006101497.tif 000031
【図３０】
2006101497.tif 000032
【図３１】
2006101497.tif 000033
【図３２】
2006101497.tif 000034
【図３３】
2006101497.tif 000035
【図３４】
2006101497.tif 000036
【図３５】
2006101497.tif 000037
【図３６】
2006101497.tif 000038
【図３７】
2006101497.tif 000039
【図３８】
2006101497.tif 000040
【図３９】
2006101497.tif 000041
【図４０】
2006101497.tif 000042
【図４１】
2006101497.tif 000043
【図４２】
2006101497.tif 000044
【図４３】
2006101497.tif 000045
【図４４】
2006101497.tif 000046