説明

経路設計装置、及び、経路設計方法

【課題】 従来は無線通信装置間の相互中継によりネットワークの経路を設計する場合、ノードの位置が移動したり装置間の接続を無線により行うことにより、中継ノードの配置場所の設計が効率的に行えなかった。
【解決手段】 この発明の経路設計装置50は、フレームワーク処理部53と囲い込み処理部70との2段階の処理部によって、ノードの移動や無線でノード間を接続する場合であっても、効率的にサバイバブルネットワークの経路を設計する。フレームワーク処理部53は、斜向座標グラフを生成して、グラフ上の座標点にノードを配置する。囲い込み処理部70は、斜向座標グラフ上に配置したノードを多角形の周囲境界線で囲い込み、周囲境界線を移動させて囲い込む範囲を縮小し、さらに、縮退規則情報に従い仮想ノードを配置して、縮小した周囲境界線を縮退させる。縮退させた周囲境界線と仮想ノードの位置とノードの位置とから経路情報を生成して出力する。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、基地局等の固定設備を持たず、移動無線通信装置間の相互中継によりネットワークを構築するアドホックネットワークの設計において、障害発生、電波状況の変化等により、通信装置あるいは装置間リンクが使用できなくなった場合にも通信を維持するための冗長経路を設計する経路設計装置及び経路設計方法に関するものである。
【背景技術】
【0002】
固定の光通信ネットワークにおいて、サバイバビリティ(障害発生時にもサービスを提供する機能)を確保して障害発生時にもサービスを維持する方法として、特開2002−335192号公報の「作業回路から保護回路への高速保護切換を可能にする方法」があった。また、固定局無しで、移動無線通信装置でアドホックネットワークを構築する方法として、特開2003−324447号公報の「ブルートゥースオンデマンドルーティング及びネットワーク形成方法、並びにブルートゥースグループアドホックネットワークにおける通信方法」があった。しかし、アドホックネットワークのサバイバビリティを確保する方法はなかった。
【0003】
例えば、特開2002−335192号公報には、有線通信におけるサバイバルネットワークの設計方法が記載されている。この特開2002−335192号公報に記載された発明では、ネットワークを構成するノード(通信装置)やリンク(通信経路)が与えられた場合に、複数の独立経路(「独立経路」とは、発信ノードと宛先ノードとの間を中継するノードを他の通信経路で共有しないことを指す)を効率よく発見して、障害発生時には効率よく通信経路を切り替える。
【0004】
また、例えば、広域にわたって配置するノード間のコネクティビティ(接続性)を確保して通信を行なうために、航空機などの飛行体により中継を行なう方法がある。この方法の一例として「K. Chandrashekar, M. R. Dekhordi, J. S. Baras著「Providing full connectivity in large ad−hoc networks by dynamic placement of aerial platforms」IEEE MILCOM 2004,(2004年10月)」がある。
【0005】
また、同様の方法として、「P. Basu, J. Radi, V. Shurbanov著 「Coordinated flocking of UAVs for improved connectivity of mobile ground nodes」IEEE MILCOM 2004,(2004年10月)」がある。これらの方法は、ノード間のコネクティビティ(接続性)を確保し、ノード間を接続する経路が一個は存在するように経路設計を行なうが、障害時の冗長経路の提供はしなかった。
【特許文献1】特開2002−335192号公報
【特許文献2】特開2003−324447号公報
【非特許文献1】「K. Chandrashekar, M. R. Dekhordi, J. S. Baras著「Providing full connectivity in large ad−hoc networks by dynamic placement of aerial platforms」IEEE MILCOM 2004,(2004年10月)」
【非特許文献2】「P. Basu, J. Radi, V. Shurbanov著 「Coordinated flocking of UAVs for improved connectivity of mobile ground nodes」IEEE MILCOM 2004,(2004年10月)」
【発明の開示】
【発明が解決しようとする課題】
【0006】
ところが、基地局等の固定の通信設備を持たず、移動無線通信装置間の相互中継によりネットワークを構築するアドホックネットワークでは、ネットワークを構成するノードの位置が移動する。また、リンクは有線ケーブルではなく不安定な無線接続である。このため、従来の手法を適用することが困難である。また、発信ノードから宛先ノードまで直接電波が到達せず、間に中継ノードを設定する必要がある場合、例えばノードの位置が移動したり無線電波の届き方が一定でないなどの不定の事柄が多すぎて、従来の発明では、どこに中継ノードを設定し、どのように通信経路を設計すればよいのか等の解を、効率的に与えることができなかった。
【0007】
また、従来の航空機などの飛行体により中継を行なう方法による接続性(コネクティビティ)確保の方法は、地上ノード間の経路、飛行体ノード間の経路ともに、一本の経路(無線通信における経路)を確保するもので、これらに障害が発生した場合の冗長性はなかった。
【0008】
この発明は上記のような問題点を解決するためになされたもので、基地局等の固定の通信設備を持たず、移動無線通信装置間の相互中継によりネットワークを構築するアドホックネットワークにおいて、複数の独立経路を設計し、サバイバビリティを確保することを目的とする。
【0009】
また、この発明は上記のような問題点を解決するためになされたもので、広域にわたって配置するノード間のコネクティビティ(接続性)を確保して通信を行なうために、航空機などの飛行体により中継を行なう場合に、一個の通信経路を確保するだけでなく、複数の独立経路を設計し、サバイバビリティを確保することを目的とする。
【課題を解決するための手段】
【0010】
この発明に係る第1の無線通信装置と第2の無線通信装置との間のネットワーク経路を設計する経路設計装置は、上記第1の無線通信装置と上記第2の無線通信装置の通信可能範囲を示す通信範囲情報を記憶する通信範囲情報記憶部と、
上記第1の無線通信装置の位置を示す第1の位置情報と上記第2の無線通信装置の位置を示す第2の位置情報とを入力する位置情報入力部と、上記通信範囲情報記憶部が記憶する通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する斜向座標生成部と、上記位置情報入力部が入力した第1の位置情報と上記第2の位置情報とのそれぞれに対応する上記斜向座標生成部が生成した斜向座標グラフ上の第1の座標点と第2の座標点とを求めて、求めた上記第1の座標点と第2の座標点とを上記斜向座標グラフ上に配置するとともに、配置した第1の座標点と第2の座標点とを囲い込む周囲境界線を上記斜向座標グラフ上に生成する配置処理部と、上記配置処理部が斜向座標グラフ上に生成した周囲境界線を周囲境界線の内側に移動して上記第1の座標点と第2の座標点とを囲い込む範囲を縮小した縮小周囲境界線を上記斜向座標グラフ上に生成する周囲境界縮小部と、周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を記憶する縮退規則情報記憶部と、上記縮退規則情報記憶部が記憶する縮退規則情報に従い、上記周囲境界縮小部が上記斜向座標グラフ上に生成した縮小周囲境界線の内側に上記仮想通信装置を配置して配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記斜向座標グラフ上に生成する境界縮退部と、上記境界縮退部が上記斜向座標グラフ上に生成した縮退周囲境界線と、上記第1の座標点と上記第2の座標点と、上記境界縮退部が配置した仮想通信装置の斜向座標グラフ上の位置とから上記ネットワーク経路を設計して経路設計情報を生成して出力する経路設計部とを備えたことを特徴とする。
【発明の効果】
【0011】
この発明の経路設計装置は、斜向座標グラフによるネットワーク設計フレームワークを用いることにより、ノード(ネットワークを構成する通信装置)が移動し、リンク(通信経路)が定まっていない場合でも、ノードを接続する複数の通信経路、および発信ノードと宛先ノードとを中継する中継ノードの位置と設置台数を設計できるという効果がある。
【0012】
また、厳密に最適経路を求めるためには、全ノードの組み合わせを検証する膨大な処理を必要とするネットワーク設計であるが、縮退規則情報に設定した縮退規則を実行することにより、簡便に全ノード間を2本以上の経路で接続する経路を求めることができる。
【発明を実施するための最良の形態】
【0013】
実施の形態1.
この実施の形態1では、斜向座標グラフを用いたフレームワーク処理部と、縮退規則情報に従いネットワークモデルを設計する囲い込み処理部を備える経路設計装置と、経路設計装置が実行する経路設計方法の一例を説明する。
【0014】
図1(a)は、この発明のアドホックネットワークのモデルを示し、(b)はネットワーク設計方法の概要を示す図である。図1(a)において、ネットワーク構成を示すネットワークモデル10は、移動無線通信装置の発信ノード1Sと、移動無線通信装置の宛先ノード1Dとを与えられる。経路設計装置は与えられた図1(a)のネットワークモデル10から図1(b)の経路を設計する。図1(b)において、通信装置間は無線によって接続するリンク2によって接続され、ネットワーク内の二地点間を結ぶ経路3a,3b,3c,3dを設計する。ネットワークモデル10において、相互の接続関係に注目する場合は、移動無線通信装置をノードと呼び、ノード間の無線による接続をリンクと呼ぶ。ここで太線矢印で示すリンク2はノード間の個々の接続、経路3a,3b,3c,3dは破線矢印で示す経路を示す。図1(a)のネットワークモデル10において、発信ノード1Sから2つのそれぞれの宛先ノード1Dに向けてデータを伝送する場合を考える。なお、発信ノード1S、宛先ノード1Dとのそれぞれのノードの直接電波が到達する範囲を六角形方眼4で示す。
【0015】
発信ノード1Sからそれぞれの宛先ノード1Dまで直接電波が到達せず、間に中継ノード1Rを設定する必要がある場合、どこに中継ノード1Rを設定し、どのように経路を設計すればよいのか、決めるべき事柄が多すぎ、従来の方法では効率的な解を与えることができなかった。ここで、従来の「特開2002−335192号公報」に記載された発明を簡単に説明して、従来のネットワーク設計における問題点を考える。
【0016】
図2(a)〜(c)は、特開2002−335192等に示された、従来の有線通信経路の二重化により、サバイバビリティ(障害発生時にもサービスを提供する機能)を確保する方法を示す模式図である。図2において、ネットワーク構成を示すネットワークモデル10は、通信端末またはルータ等の通信装置であるノード1(特に発信ノードは発信ノード1Sとし、宛先ノードは宛先ノード1Dとする)と、通信装置間を接続する金属ケーブルまたは光ファイバ等のケーブルによるリンク2と、ネットワーク内の二地点間を結ぶ経路31,32,33とにより示される。ネットワークモデル10において、相互の接続関係に注目する場合は、通信装置をノードと呼び、ケーブルをリンクと呼ぶ。ここでリンク2はノード間の個々の接続を示す。経路31,32,33は、太線矢印の組で示す破線矢印で示した経路全体を指す。
【0017】
図2(a)のネットワークモデル10において、発信ノード1Sから宛先ノード1Dに向けてデータを伝送する場合を考える。発信ノード1Sから宛先ノード1Dに向けて、図2(b)では1本の経路31、図2(c)では2本の経路32と経路33とが設定されている。図2(b)のように経路が1本の場合は、経路31の有するノード1またはリンク2に障害が発生した場合、発信ノード1Sから宛先ノード1Dに向けた通信が不可となる。しかし、図2(b)のように、独立した経路が2本ある場合は、一方の経路32が切断されても、他方の経路33により通信が可能となる。ここで複数の経路が独立しているというのは、ノード1やリンク2を異なる経路によって共有していないことを指す。
【0018】
従来の有線通信のサバイバブルネットワーク設計方法は、図2(a)のようなノード1,1S,1Dやリンク2が与えられた場合、すなわち、ネットワークモデル10を構成するために必須の要素が既知である場合に、図2(c)のような複数の独立経路32,33を効率良く発見し、障害発生時には効率良く切り替えるためのものであった。
【0019】
ところが、基地局等の固定の通信設備を持たず、移動無線通信装置間の相互中継によりネットワークを構築するアドホックネットワークでは、図2のノード1やノード1S,1Dの位置が移動したり、リンク2が有線ケーブルではなく不安定な無線接続であるという理由で、従来の手法を適用することが困難である。図1に示したアドホックネットワークのモデルについて、図1(a)の発信ノード1Sから2個の宛先ノード1Dに向けてデータ通信を行う場合を考えると、発信ノード1Sから宛先ノード1Dまで直接電波が到達せず、間に中継ノード1Rを設定する必要がある場合、不定の事柄(ノードの移動や無線電波状態の変化等)が多すぎ、従来の方法では、どこに中継ノード1Rを設定し、どのように経路を設計すればよいのか等の解を効率的に与えることができなかった。
【0020】
そこでこの実施の形態1の経路設計装置では、図1(b)に示すように、経路を設計する補助のために六角形方眼4を設定し、そこで複数の経路3a,3b,3c,3dを設計する。図1(b)では、発信ノード1Sから2個の宛先ノード1Dまで、それぞれ2本の経路3a,3bと経路3c,3dを設定する。ここでは、経路設計の補助となる主に斜向座標グラフを生成するフレームワーク処理部と、ネットワーク設計における中継ノードの設定についての規則を示した縮退規則情報を実行してネットワークモデルの経路を設計する囲い込み処理部との2段階の処理部から構成する経路設計装置について、以下に説明する。
【0021】
図3は、この実施の形態の経路設計装置を構成する要素の一例を示すブロック図である。図3において、経路設計装置50は、ネットワークモデルを構成する発信ノードや宛先ノードのノード40から緯度情報と経度情報とを少なくも有する位置情報60を受信する位置情報入力部51を備える。また、主に斜向座標グラフを生成するフレームワーク処理部53と、ネットワーク設計における中継ノードの設定についての規則を示した縮退規則情報を実行してネットワークモデルの経路を設計する囲い込み処理部70とを備える。
【0022】
フレームワーク処理部53は、ノード40の通信可能範囲を距離で示す通信範囲情報を記憶する通信範囲情報記憶部55と、通信範囲情報記憶部55が記憶する通信範囲情報を1目盛りとする斜向座標グラフを生成する斜向座標生成部57と、位置情報60の斜向座標グラフ上の座標点を求めて斜向座標グラフ上にノード40を配置して、斜向座標グラフ上に配置したノード40に対応する座標点を取り囲む周囲境界線を斜向座標グラフ上に生成する配置処理部59とを、備える。
【0023】
また、囲い込み処理部70は、周囲境界線を周囲境界線の内側に移動させて周囲境界線が囲い込む範囲を縮小する縮小周囲境界線を、斜向座標グラフ上に生成する周囲境界縮小部73を備える。また、縮小周囲境界線の内側に仮想通信装置を配置させて、仮想通信装置上を通過する縮小周囲境界線を縮退させた縮退周囲境界線を生成する規則を示す縮退規則情報を記憶する縮退規則情報記憶部75と、縮退規則情報に従い、仮想通信装置を縮小周囲境界線の内側に配置して、仮想通信装置を通過するように縮小周囲境界線を縮退させて、縮退周囲境界線を斜向座標グラフ上に生成する境界縮退部77を備える。また、境界縮退部77が生成した縮退周囲境界線と、ノード40の座標点と、仮想通信装置の斜向座標グラフ上の位置とから中継ノードを配置するネットワークモデル上の位置を決定して、ネットワークモデルのネットワーク経路を設計して経路情報を生成して、経路情報を出力する経路設計部79を備えた。図3に示したノード40は、発信ノードと宛先ノードの2つであるが、ネットワークモデルの有するノードの数は2つ以上でもかまわない。
【0024】
図4は、通信範囲情報記憶部55が記憶する通信範囲情報の一例を示す図であえる。通信範囲情報はノード40の通信可能領域を例えば円で示した場合の半径の距離である。図4の通信範囲情報記憶部55が記憶する通信範囲情報は、1キロメートルである。
【0025】
図5は、実施の形態1における経路設計装置の外観を示す図である。図5において、経路設計装置50は、システムユニット200、CRT(Cathode Ray Tube)表示装置141、キーボード(K/B)142、マウス143、コンパクトディスク装置(CDD)186、プリンタ装置187、スキャナ装置188を備え、これらはケーブルで接続されている。さらに、経路設計装置50は、FAX機310、電話器320とケーブルで接続され、また、ローカルエリアネットワーク(LAN)505、ウェブサーバ500を介してインターネット501に接続され、無線通信のほかに有線による通信も可能である。
【0026】
図6は、実施の形態1における経路設計装置のハードウェア構成図である。図6において、経路設計装置50は、プログラムを実行するCPU(Central Processing Unit)137を備えている。CPU137は、バス138を介してROM139、RAM140、通信ボード144、CRT表示装置141、K/B142、マウス143、FDD(Flexible Disk Drive)145、磁気ディスク装置146、CDD186、プリンタ装置187、スキャナ装置188と接続されている。RAMは、揮発性メモリの一例である。ROM、FDD、CDD、磁気ディスク装置、光ディスク装置は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。通信ボード144は、FAX機310、電話器320、LAN505等に接続されている。例えば、通信ボード144、K/B142、FDD145などは、情報入力部の一例である。また、例えば、通信ボード144、スキャナ装置188、CRT表示装置141などは、出力部の一例である。
【0027】
ここで、通信ボードは、LAN505に限らず、直接、インターネット、或いはISDN等のWAN(ワイドエリアネットワーク)に接続されていても構わない。直接、インターネット、或いはISDN等のWANに接続されている場合、経路設計装置50は、インターネット、或いはISDN等のWANに接続され、ウェブサーバ500は不用となる。磁気ディスク装置146には、オペレーティングシステム(OS)147、ウィンドウシステム148、プログラム群149、ファイル群150が記憶されている。プログラム群は、CPU137、OS147、ウィンドウシステム148により実行される。
【0028】
上記プログラム群149には、以下に述べる実施の形態の説明において「〜部」として説明する機能を実行するプログラムが記憶されている。プログラムは、CPUにより読み出され実行される。ファイル群150には、以下に述べる実施の形態の説明において、「〜の判定結果」、「〜の計算結果」、「〜の処理結果」として説明するものが、「〜ファイル」として記憶されている。また、以下に述べる実施の形態の説明において説明するフローチャートの矢印の部分は主としてデータの入出力を示し、そのデータの入出力のためにデータは、磁気ディスク装置、FD(Flexible Disk)、光ディスク、CD(コンパクトディスク)、MD(ミニディスク)、DVD(Digital Versatile Disk)等のその他の記録媒体に記録される。あるいは、信号線やその他の伝送媒体により伝送される。
【0029】
また、以下に述べる実施の形態の説明において「〜部」として説明するものは、ROM139に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、ハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。
【0030】
また、以下に述べる実施の形態を実施するプログラムは、また、磁気ディスク装置、FD(Flexible Disk)、光ディスク、CD(コンパクトディスク)、MD(ミニディスク)、DVD(Digital Versatile Disk)等のその他の記録媒体による記録装置を用いて記憶されても構わない。
【0031】
図7は、実施の形態1のフレームワーク処理部による斜向座標グラフ上に通信装置の位置を配置する処理のフローチャート図である。図8は、実施の形態1の囲い込み処理部によるネットワークの経路設計情報を生成して出力する処理のフローチャート図である。図9は、斜向座標グラフの一例を示す図である。図9の斜向座標グラフは、三角メッシュに対応する斜向座標グラフの一例である。グラフのx軸、y軸の1目盛りは通信可能範囲(D)であり、図4に示したように通信可能範囲(D)は、1キロメートルであるものとする。
【0032】
図7、図8のフローチャートに従い経路設計装置の動作を説明する前に、まず、無線アドホックネットワーク設計の特徴を述べる。図1に示した無線アドホックネットワーク設計問題は、次の二点において図2の有線ネットワーク設計問題と異なる。
(1)位置依存性:ネットワークモデル10をノード1,1S,1Dとリンク2のモデルで表現する場合の基本的な仮定は、リンク2はゴムひもの様に伸び縮み自在でトポロジカルな自由度があるとすることであるが、無線ではこれは成り立たない。
(2)無線の同報性:有線通信では伝送はリンク2に沿って一次元でのみ行われるが、無線では三次元空間で行われる。
【0033】
上記したこれらの特性を生かしてサバイバブルアドホックネットワークを設計するために、まず、図2のノード1やノード1Sやノード1Dとリンク2の代わりに、ノード1と球によって表現する通信可能範囲5によるモデルを考える(図10)。図10は、ノードから電波の到達する通信可能範囲5を球で示す図である。発信元のノード1Sから宛先のノード1Dまで、各ノードの通信可能範囲5の範囲内に、順次、次ノードを設定することにより経路の設計を行う。例えば図10では、発信元のノード1Sを中心とする通信可能範囲5の球と、宛先のノード1Dを中心とする通信可能範囲5の球との間に通信不可能な空間が存在するため、この通信不可能な空間を通信可能な空間にして、発信元ノード1Sと宛先ノード1Dとの間の通信を可能にする。通信を可能にするため、中継ノード1をノード1Sとノード1Dとの間に配置させる。配置した中継ノード1の周りには、中継ノード1を中心とする通信可能範囲5の球ができる。
【0034】
ここで、検討を容易にするために、図10のモデルを単純化していく。まず、図10の通信可能範囲5の球を二次元の円に単純化する。次に、さらに円を多角形にして、通信可能範囲5の重複を避けるため半径を1/2に縮退させて考える(図11)。すなわち、半径を1/2に縮退させたものが、通信範囲情報記憶部55が記憶する通信可能範囲情報(1キロメートル)である。図11は、円を多角形、例えば六角形に置き換え、通信可能範囲5を1/2に縮退させてネットワークモデルを六角形方眼で示した図である。通信可能範囲5を1/2に縮退させた結果、我々の課題は、多角形方眼(図12)上の隣接する多角形をたどって発信元ノード1Sから宛先ノード1Dへの経路を求めることとなる。図12は多角形方眼の一例を示す図であり、(a)は六角形、(b)は四角形、(c)は三角形の方眼を示す。上記した説明では、球を円に単純化して、さらに円を六角形の多角形に置き換えることを説明した。しかし、円を多角形に置き換える場合、六角形以外に、四角形や三角形に置き換えてもかまわない。四角形に置き換えた場合、x軸とy軸とは直角に交わる。斜向座標座標グラフは、この直角に交わるグラフも含む。
【0035】
このように、円を多角形に置き換える場合、平面を隙間無く覆える多角形であれば、六角形ではなくても、四角形や三角形でもかまわない。ただし、六角形は電波伝搬を反映した円に近いので用いられることが多い。また、四角形は辺が直行しているので、取り扱いが楽である。それぞれの多角形の特徴を考慮して、設計者が六角形、四角形、三角形のいずれに置き換えるか決定できるものとする。
【0036】
このような平面グラフの問題は、グラフ理論において、通常、双対グラフを用いて解かれる。図13(a)、(b)、(c)に図12(a)、(b)、(c)のそれぞれの多角形方眼に対応する双対グラフメッシュを示す。我々の課題は、図13の双対メッシュグラフにおいて、点線で示すメッシュで接続された双対ノード1をたどって発信元ノード1Sから宛先ノード1Dへの経路を求めることとなる。ここで双対メッシュを定義する。双対メッシュとは、多角形方眼において、各マス目内にマス目を代表する点(双対の頂点)1個を設定し、隣接するマス目に対してマス目の境界線とただ1回交わるような線(双対の辺)で代表点を結んで得られるメッシュである。六角形方眼の双対メッシュは三角メッシュであり、四角形方眼の双対メッシュは四角メッシュ、三角形方眼の双対メッシュは六角メッシュとなる。
【0037】
この実施の形態では、図12(a)の六角形方眼、および対応する図13(a)の三角メッシュを使用する。問題の記述を容易にするために、図9に示す三角メッシュに対応する斜向座標7を用いて、ノードの位置を示す。
【0038】
次に、本発明の経路設計装置によるサバイバブルアドホックネットワーク設計方法である囲い込みアルゴリズムを実行する動作について説明する。我々のサバイバブルアドホックネットワーク設計問題は、発信元のノード1Sが付与されているとき、サバイバビリティの要求課題として、ネットワークモデル10内の各ノード間に、2本以上の独立経路を設計するとともに、経路内の最小コスト経路を求めるものとする。制約条件は、図9の斜向座標上の隣接する点(図9の「○」)で表されるノードをたどることである。全リンクコスト(図9の1目盛)を1として最小コスト経路を求める。図13(b)の場合は、x軸とy軸とは直角に交わる。斜向座標座標グラフは、この直角に交わるグラフも含む。
【0039】
上記したように経路設計装置は、フレームワーク処理と囲い込み処理との2段階の処理によってネットワークの通信経路を設計する。はじめに、図7のフローチャートに従い、フレームワーク処理の手順を説明する。図7において、経路設計装置50は、ネットワークモデル10の有する発信ノード40と宛先ノード40からそれぞれノードの位置を示す位置情報60を、位置情報入力部51により入力する(S1,位置情報入力工程)。位置情報60は、例えば緯度情報と経度情報とを有して、ノードの位置を表す。また、図3の例では、発信ノード40と宛先ノード40の2機のノードから位置情報を入力しているが、2機以上のノードから位置情報を入力してもかまわない。すなわち、ネットワークモデル10は、例えば、発信ノードを1機、宛先ノードを複数機有していてもかまわない。入力した位置情報60は、フレームワーク処理部53へ出力する。
【0040】
フレームワーク処理部53は、斜向座標生成部57によって、例えば図9に示す斜向座標グラフを生成する(S2,斜向座標生成工程)。このとき、斜向座標生成部57は、斜向座標グラフのx軸とy軸のそれぞれの1目盛を、通信範囲情報記憶部55が記憶する通信範囲情報の通信可能範囲(D)として生成する。ここで、斜向座標として三角形の双対メッシュを使用する理由は上記した通りである。
【0041】
次に、フレームワーク処理部53は、配置処理部59によって、S1で入力した発信ノード40の位置情報から斜向座標グラフの斜向座標7上の座標点を求めて、発信ノード40の位置を、求めた座標点に配置する。また、S1で入力した宛先ノード40の位置情報から斜向座標グラフの斜向座標7上の座標点を求めて、宛先ノード40の位置を、求めた座標点に配置する。求めた座標点が斜向座標グラフのメッシュで示した三角形の頂点でない場合は、求めた座標点を直近の頂点の座標点に近似させる。また、緯度情報と、経度情報とを所定の座標点に変換する処理は、例えば、発信元ノード40の緯度情報と、経度情報とを斜向グラフ上の座標(0,1)と仮定して宛先ノード40の緯度情報と、経度情報とを基準にして宛先ノード40との相対距離と角度とを求めて、相対距離と角度とから宛先ノード40の座標点を算出する。この時、x軸とy軸とのそれぞれの1目盛は、図4により1キロメートルとする。
【0042】
座標点の配置が終了したら、配置処理部59は、配置した座標点を囲い込む周囲境界線を、斜向座標7上に生成する(S3,配置処理工程)。ここまでのS1〜S3の処理がフレームワーク処理である。フレームワーク処理は、例えば磁気ディスク装置146のプログラム群149に記憶されたプログラムをフレームワーク処理部53が実行することによって実現する。また、通信範囲情報記憶部55は、磁気ディスク装置146のファイル群150に記憶されている。フレームワーク処理部53は、CPU137であり、CPU137は磁気ディスク装置146のプログラム群149からフレームワーク処理を行うプログラムを呼び出して、プログラムに従いS1〜S3のフレームワーク処理を行う。
【0043】
続いて、図8に従い、囲い込み処理の手順について説明する。なお、以下の囲い込みアルゴリズムは、囲い込み処理のアルゴリズムである。また、図7のS3の処理では、配置した座標点を囲い込む周囲境界線を斜向座標7上に生成する処理を、配置処理部59が行うものとして説明した。しかし、説明を容易にするため、囲い込み処理に含めるものとして以下に説明する。周囲境界線を生成する実際の処理は、フレームワーク処理内で行っても、囲い込み処理内で行っても、いずれでもかまわない。
【0044】
図14、図15に斜向座標グラフの斜向座標7上に囲い込み(Enclosure)アルゴリズムの実行状況の経過を説明する図を示す。なお、図14、図15において、「●」は発信元或いは宛先ノード、「◎」は仮想ノード、「○」は中継ノードをそれぞれ示す。
図14(a)−>ノードの和集合1W={宛先ノード1Dと発信ノード1Sの和集合}を求める。
図14(b)−>和集合1Wの六角形ゾーンの周囲境界線3Bによる初期囲い込み。6個の境界線を平行移動して範囲を縮小する。
図15(a)−>全ノードを包含する最小囲い込み範囲を決定して、決定した最小囲い込み範囲に基づいて周囲境界線3Bを縮小させて、縮小周囲境界線を生成。さらに範囲を縮小。
図15(b)−>予め定めた縮退規則情報に従い縮小周囲境界線をさらに縮退させて、六角形および付随三角形から構成される縮退周囲境界線を生成して、縮退境界範囲を決定する。図15(b)の「◎」は仮想ノード1Vである。
図15(c)−>縮退周囲境界線の内部にあるノードと境界閉路を2個の最短辺で接続。境界閉路は周囲境界線3Bによって示す。境界閉路および内部ノードが設計したネットワーク経路の解となる。図15(c)の「○」は、中継ノード1Rである。
【0045】
縮退規則情報に従う詳しい周囲境界線の縮退方法については、図16に示す。なお、縮退は周囲境界線の有する複数の辺それぞれについて行うものとする。
図16(a)−>周囲境界線3B上に2個以上のノード(図中ノードを「●」で示す)がある場合は、周囲境界線はシフト(縮退)しない。
図16(b)−>周囲境界線3B上にノードが1個のみある場合は、周囲境界線3Bは1単位(斜向座標の1目盛)シフト(縮退)し、周囲境界線上のノードはそのままで、シフト(縮退)された周囲境界線3B上に2個の仮想ノード1Vを設定する。
図16(c)−>ノードと周囲境界線3Bとの接続は2リンク以上必要で、1リンクではいけない(ここでの「リンク」とは、ノードと仮想ノードとの接続を指す)。
【0046】
図14、図15に示した経過で実行する囲い込み(Enclosure)処理の手順を図8のフローチャートに従い説明する。図8において、配置処理部59は、座標点の配置が終了したら、配置した発信元ノードの座標点と宛先ノードの座標点とを囲い込む周囲境界線を、斜向座標7上に生成する(S10,配置処理工程)。この処理は、図14(a)と図14(b)の初期囲い込みの処理に対応する。図14(a)に示すように、ここでは発信元ノードと宛先ノードとを合わせて3つ以上のノードをネットワークモデルが有するものとする。図14(b)のように、周囲境界線は例えば正六角形の形状をしている。
【0047】
次に、囲い込み処理部70の周囲境界縮小部73が、周囲境界線3Bの有する6つの各辺を周囲境界線の内側に平行移動させる(S11,周囲境界縮小工程)。各辺を移動させることによって、周囲境界線3Bが取り囲む範囲を縮小する。この処理は、図14(b)の境界線を平行移動して範囲を縮小する処理と、図15(a)の処理に対応する。
【0048】
次に、囲い込み処理部70の境界縮退部77が、縮退規則情報記憶部75に記憶された縮退規則情報に従い、平行移動して縮小した(縮小)周囲境界線3Bをさらに縮退させる(S12,境界縮退工程)。縮退規則情報記憶部75が記憶する縮退規則情報は、図16(a)〜(c)に示した内容で縮退を行わせるものであり、上記した図16の説明のように、
(1)周囲境界線3B上に2個以上のノード(図中ノードを「●」で示す)がある場合は、周囲境界線はシフト(縮退)しない。
(2)周囲境界線3B上にノードが1個のみある場合は、周囲境界線3Bは1単位(斜向座標の1目盛)シフト(縮退)し、周囲境界線上のノードはそのままで、シフト(縮退)された周囲境界線3B上に2個の仮想ノード1Vを設定する。
(3)ノードと周囲境界線3Bとの接続は2リンク以上必要で、1リンクではいけない(ここでの「リンク」とは、ノードと仮想ノードとの接続を指す)。
の規則で境界縮退部77に周囲境界線の縮退を行わせる。この処理は、図15(b)の処理に対応する。周囲境界縮小部73が縮小した周囲境界線を上記した縮退規則に従い縮退させる場合には、図15(b)のように仮想ノード1Vを配置する。また、仮想ノード1Vを配置する条件は、周囲境界線上にノードが1つのみある場合である。図15(b)の網がけした三角形に相当する部分が周囲境界線を縮退した部分であり、この三角形の頂点、或いは辺上の三角メッシュの頂点には仮想ノード1V(図中「◎」)が配置されている。
【0049】
次に、囲い込み処理部70の経路設計部79は、境界縮退部77が縮退した周囲境界線3B上にある仮想ノード1Vを中継ノード1Rに変更する。そして、周囲境界線上及び周囲境界線内部にあるノードと中継ノードとを接続してリンクを生成する。リンクの生成は、それぞれのノードに少なくとも2リンクを生成させる。そして、周囲境界線上のノードの位置情報と中継ノードの位置情報とリンクを示す情報とを経路情報80として出力する(S13,経路設計工程)。経路情報80の出力先は、例えば、発信ノードや宛先ノードや経路設計者の携帯する通信装置やプリンタ装置187やLAN505やCRT表示装置141やFAX機310等である。また、ノードの位置情報装置は、斜向座標グラフ上の座標点であっても、座標点を緯度情報と経度情報とに変換したものでもいずれでもかまわない。この処理は、図15(c)に対応する処理である。
【0050】
上記したS10〜S13の処理が、囲い込み処理である。このように、経路設計装置50は、経路設計処理をフレームワーク処理と囲い込み処理との2段階の処理で実現する。なお、ネットワークモデルの有する発信元ノードや宛先ノードが移動して位置が変更になった場合には、再度の経路設計が必要となり、図7、図8の手順を再実行して、経路情報を求める。
【0051】
次に、経路設計装置が設計した経路の妥当性を、周囲境界縮小と内部ノード接続の二段階について述べる。まず、周囲境界縮小について考える。我々の目的は予めネットワークモデルを構成する位置が分かっている複数のノードを2本以上の独立経路で接続することである。このため、各ノードは隣接ノードと少なくとも2個のリンクで接続されている必要がある。図15(c)の周囲境界線3B(周囲境界閉路)は、閉路上の各ノードに対して2リンク接続を与え、最適に近い。図14(a)に示したできるだけ多くのノードを2本以上のリンクで接続する閉路として、図15(c)と全く異なるものは考え難い。
【0052】
次に、内部ノードについて考える。図15(c)は網がけした三角形において明らかに冗長なリンクを有し、その一辺を削除することにより、コスト最小化を図ることが可能である。しかし、複雑さを増してその処理を行わなくても、最適に近い値は得られている。
【0053】
図17に経路設計装置50による経路設計の利用形態を示す。図17(a)は災害ネットワークであり、◎は、中継ノード1Rを示す。図17(b)は温度等のセンサーネットワークを示し、図中白抜きの○は、中継ノードを兼ねる宛先ノード1Dを示す。災害ネットワークは、1つの発信ノード1Sから2つの宛先ノード1Dへ、それぞれの宛先ノードに対して2つの経路3a,3bと3c,3dを設定し、経路途中に配置した中継ノード1Rを経路情報に含めて提示する場合等に使用することが可能である。
【0054】
また、センサーネットワークでは、情報を集中管理する発信元ノード1Sと発信元ノード1Sの通信可能範囲5と中継ノードを兼ねる宛先ノードを配置するネットワークモデルの領域を示す領域情報12が経路設計装置に与えられる。領域情報12は、例えば四角形の領域の4つの頂点それぞれの緯度情報と経度情報である。経路設計装置50は、領域情報12の有する4つの頂点それぞれの緯度情報と経度情報とを宛先ノードの位置情報と仮定して経路設計を行う。経路設計装置50は、図7、図8の処理を行い、経路情報として図17(b)の「◎」で示した中継ノードを兼ねる宛先ノードの位置情報を出力する。ネットワーク設計者は、出力された宛先ノードの位置情報に対応する場所に宛先ノードを配置させれば、所定の宛先ノードに障害が発生して使用不可能になるリンクとノードとが発生しても、他の中継ノードを兼ねる宛先ノードを経由する経路によって、ノード間の接続が確保される。
【0055】
以上のように、この実施の形態で説明した経路設計装置及び経路設計方法は、多角形グリッド、双対グラフメッシュ、斜向座標によるネットワーク設計フレームワークを用いることにより、ノードが移動し、リンクが定まっていない場合でも、ノードを接続する複数の経路、および中継ノードを設計できるという効果がある。また、厳密に最適経路を求めるためには、全ノードの組み合わせを検証する膨大な処理を必要とするネットワーク設計であるが、囲い込み処理部による囲い込み処理により、簡便に全ノード間を2本以上の経路で接続する経路を求めることができる。
【0056】
この実施の形態では、以下のことを特徴とする経路設計装置、経路設計方法の一例を説明した。
【0057】
アドホックネットワークでは、ノードが移動し無線リンクが不安定なため、不定の事柄が多すぎ、従来の有線通信の方法では、複数の独立経路の設計を効率的に行うことができなかった。しかし、この実施の形態の経路設計装置及び経路設計方法では、設計のためのフレームワークを用いることにより、可能となる。
【0058】
フレームワークは、多角形方眼、双対グラフメッシュ、斜向座標より構成される。
【0059】
フレームワークを用いたサバイバブルアドホックネットワーク設計方法として、囲い込みアルゴリズムを提案している。囲い込みアルゴリズムの特徴は、全ノード間に2本以上独立経路を設定するため、境界で囲い込み、これを狭めていき、できるだけ多くのノードを境界線上にのせ、内部に残ったノードは二本以上のリンクで境界線の枠と接続することである。
【0060】
実施の形態2.
この実施の形態では、通信範囲情報を電波の強度に対応させる経路設計装置、経路設計方法の一例を説明する。
【0061】
図18は、実施の形態2の経路設計装置を構成する要素の一例を示すブロック図である。図18において、位置情報入力部51は、位置情報を受信した際の電波の強度を測定する電波強度測定部91を備える。また、通信範囲情報記憶部55は、図19に示すように、通信可能範囲を電波強度に対応させて記憶する通信範囲情報を記憶する。また、斜向座標生成部57は、電波強度測定部91が測定した測定結果である電波レベルを入力して、電波レベルに対応する通信可能範囲を通信範囲情報記憶部55から取得して、取得した電波レベルに対応する通信可能範囲をx軸とy軸の1目盛とする斜向座標グラフを生成する。なお、位置情報入力部51は複数の位置情報を入力し、それぞれの位置情報は電波レベルが同じ場合と異なる場合とがある。電波レベルが異なる場合には、電波レベルに対応する通信可能範囲が異なる場合が考えられる。通信可能範囲が異なる場合には、例えば、通信可能範囲の平均値を算出して、平均値を斜向座標グラフの生成に使用する。経路設計装置50の他の要素は、上記実施の形態1の図3と同様であるものとする。
【0062】
経路設計方法の処理手順は、図7のS1とS2が実施の形態1と異なる。実施の形態2では、図7のS1の位置情報を受信した後、受信した位置情報の電波強度を電波強度測定部91が測定して、測定した電波レベルを斜向座標生成部57に出力する。また、S2では、斜向座標生成部57は、電波レベルに対応する通信可能範囲を通信範囲情報記憶部55から取得して、取得した電波レベルに対応する通信可能範囲をx軸とy軸の1目盛とする斜向座標グラフを生成する。S1、S2以外の処理は、上記実施の形態1の図7、図8と同様である。
【0063】
以上のように、通信可能範囲を電波レベルに対応させることにより、実際の通信環境に合ったネットワーク経路を設計することができる。
【0064】
実施の形態3.
この実施の形態では、通信範囲情報をノードの種類に対応させる経路設計装置、経路設計方法の一例を説明する。
【0065】
図20は、実施の形態3の経路設計装置を構成する要素の一例を示すブロック図である。図20において、位置情報入力部51は、位置情報を発信したノードの種類を識別するためのノード種類情報を有する位置情報61を受信する。また、通信範囲情報記憶部55は、図21に示すように、通信可能範囲をノードの種類に対応させて記憶する通信範囲情報を記憶する。また、斜向座標生成部57は、位置情報61の有するノード種類情報を入力して、ノード種類情報に対応する通信可能範囲を通信範囲情報記憶部55から取得して、取得したノード種類情報に対応する通信可能範囲をx軸とy軸の1目盛とする斜向座標グラフを生成する。なお、位置情報入力部51は種類の異なるノードから位置情報61を入力し、ノードの種類に対応する通信可能範囲は同じ場合と異なる場合とがある。通信可能範囲が異なる場合には、例えば、通信可能範囲の平均値を算出して、平均値を斜向座標グラフの生成に使用する。経路設計装置50の他の要素は、上記実施の形態1の図3と同様であるものとする。
【0066】
経路設計方法の処理手順は、図7のS1,S2が実施の形態1と異なる。実施の形態3では、図7のS1の位置情報61を受信した後、受信した位置情報61の有するノード種類情報を斜向座標生成部57に出力する。また、S2では、斜向座標生成部57は、ノード種類情報に対応する通信可能範囲を通信範囲情報記憶部55から取得して、取得した通信可能範囲をx軸とy軸の1目盛とする斜向座標グラフを生成する。S1、S2以外の処理は、上記実施の形態1の図7、図8と同様である。
【0067】
以上のように、通信可能範囲をノードの種類に対応させることにより、実際にネットワークモデルを構成する通信装置の仕様に合ったネットワーク経路を設計することができる。
【0068】
実施の形態4.
この実施の形態では、通信範囲情報を時刻に対応させる経路設計装置、経路設計方法の一例を説明する。
【0069】
図22は、実施の形態4の経路設計装置を構成する要素の一例を示すブロック図である。図22において、位置情報入力部51は、ネットワークモデルを構成する通信装置(ノード)が自己の位置情報を算出した際の時刻を示す時刻情報を位置情報に含めて発信した位置情報62を受信する。或いは、位置情報62に含まれる時刻情報は、例えば自己の位置を算出する際に使用する衛星から発信される測位信号に含まれる測位時刻情報でもかまわない。通信範囲情報記憶部55は、図23に示すように、通信可能範囲を時刻に対応させて記憶する通信範囲情報を記憶する。また、斜向座標生成部57は、位置情報62の有する時刻情報を入力して、時刻情報に対応する通信可能範囲を通信範囲情報記憶部55から取得して、取得した時刻情報に対応する通信可能範囲をx軸とy軸の1目盛とする斜向座標グラフを生成する。なお、位置情報入力部51は複数のノードから異なる時刻情報を有する位置情報62を入力し、時刻情報に対応する通信可能範囲は同じ場合と異なる場合とがある。通信可能範囲が異なる場合には、例えば、通信可能範囲の平均値を算出して、平均値を斜向座標グラフの生成に使用する。経路設計装置50の他の要素は、上記実施の形態1の図3と同様であるものとする。
【0070】
経路設計方法の処理手順は、図7のS1,S2が実施の形態1と異なる。実施の形態4では、図7のS1の位置情報62を受信した後、受信した位置情報62の有する時刻情報を斜向座標生成部57に出力する。また、S2では、斜向座標生成部57は、時刻情報に対応する通信可能範囲を通信範囲情報記憶部55から取得して、取得した通信可能範囲をx軸とy軸の1目盛とする斜向座標グラフを生成する。S1、S2以外の処理は、上記実施の形態1の図7、図8と同様である。
【0071】
以上のように、通信可能範囲を時刻に対応させることにより、ネットワークモデルの通信経路を設計する際の時刻における通信環境に合ったネットワーク経路を設計することができる。
【0072】
実施の形態5.
この実施の形態では、経路設計装置が通信経路の設計を行うだけでなく、自身もネットワークモデルを構成するノードである場合の経路設計装置、経路設計方法の一例を説明する。
【0073】
図24は、実施の形態4の経路設計装置を構成する要素の一例を示すブロック図である。図24において、経路設計装置50は、衛星群201を構成する静止衛星202やGPS衛星203や準天頂衛星204から発信された測位信号をアンテナ93を介して受信する測位受信部95を備える。また、測位受信部95が受信した測位信号から自己の位置を算出して自己位置情報を生成する位置算出部97を備える。アンテナ93,測位受信部95,位置算出部97とにより受信位置算出部94を構成する。フレームワーク処理部53は、位置情報入力部51から位置情報60を入力するとともに、位置算出部97から自己の位置情報を入力する。経路設計装置50の他の要素は、上記実施の形態1の図3と同様であるものとする。
【0074】
経路設計方法の処理手順は、図7のS1とS2との間に自己の位置を算出する処理を行う点が実施の形態1と異なる。実施の形態5では、図7のS1の位置情報を受信した後、アンテナ93を介して測位受信部95が測位信号を受信して、位置算出部97が受信した測位信号を用いて自己の位置情報を算出する処理を行う。また、S3で配置処理部59は、位置算出部97から自己の位置情報を入力して斜向座標グラフ上の座標点に変換し、自己の位置を斜向座標グラフ上に配置する。S1、S3以外の処理は、上記実施の形態1の図7、図8と同様である。また、通信可能範囲は、実施の形態2〜4にように、電波強度やノードの種類や時刻に対応させることも可能である。
【0075】
以上のように、経路設計装置は、ネットワークモデルを構成するノードを兼ねることが可能となる。
【0076】
実施の形態6.
この実施の形態では、2層構造のネットワークモデルを用いてアドホックネットワークの経路設計について一例を説明する。
図25は、実施の形態6のアドホックネットワークの2層構造のモデルを示す図である。図25に示すように、この実施の形態6のネットワークモデル10は、飛行体局1aからなるネットワーク層と、地上局1gからなるネットワーク層との2層構造である。飛行体局1aは、例えば航空機などの飛行体に搭載された無線通信端末装置であって、広域にわたって配置する地上局1g間のコネクティビティ(接続性)を確保して通信を行なうための中継を行なう。飛行体局1a間は、無線リンク2aによって接続される。地上局1gは、移動無線通信装置であって、地上局1g間は、無線リンク2gによって接続する。2地点間のそれぞれの地上局1gは、2つの地上局間経路3Hgによって接続する。2地点間のそれぞれの飛行体局1aは、2つの飛行体局間経路3Haによって接続する。飛行体局1aは、通信可能範囲5aLを有し、飛行体局1aの通信可能範囲を地上へ投射すると地上局1gからなるネットワーク層への投射5aRとなる。飛行体局1aは地上からの垂直高Hを有する。言い換えると、飛行体局1aからなるネットワーク層の面は、地上局1gからなるネットワーク層の面に対して、垂直方向にあって、地上局1gからなるネットワーク層の面とは、垂直高Hを有する。
ここで、符号の識別について説明する。ネットワークモデル10において、地上局に関するものは添え字g、飛行体局に関するものは添え字aを添えて表す。添え字gとaによるネットワーク層の区別は、本実施の形態6以降の実施の形態でも同様とする。また、地上局と飛行体局との相互の接続関係に注目する場合は、通信装置をノード、ノード間の個々の接続をリンクと呼ぶ。経路設計装置は、図25中の破線で示した地上局間経路3Hgと飛行体局間経路3Haとを合わせたネットワーク経路を設計する。図25のネットワークモデル10において、地上局1g間で通信を行なう場合、地上局1gが広域に渡って配置されており、地上ノードの相互通信のみでは通信経路を確保することが困難な場合(通信経路の確保が困難な理由としては、例えば、通信可能範囲が狭く、直近の地上ノードまで電波が届かない場合や、地上ノード間に高い山があり、電波が遮られて届かない場合などがある)、飛行体局1aで中継を行なうことにより、広域の通信経路を提供する。この際、一個の通信経路を確保するだけでなく、複数の独立経路を設計し、サバイバビリティを確保する。
【0077】
図26は、実施の形態6のネットワーク設計方法に使用する2層構造のネットワークモデルを示す図である。地上局のネットワークモデル10gは、複数の多角形、例えば複数の正六角形を隣接させて配置した地上レイヤメッシュ(多角形方眼)4gによって表す。飛行体局のネットワークモデル10aは、複数の多角形、例えば複数の正六角形を隣接させて配置した航空レイヤメッシュ(多角形方眼)4aによって表す。地上局1gは通信可能範囲Dg(第1の通信可能範囲)を有し、飛行体局1aは通信可能範囲Da(第2の通信可能範囲)を有する。通信可能範囲Dgと通信可能範囲Daとの関係は、通信可能範囲Dg<通信可能範囲Daであり、飛行体局の通信可能範囲が地上局の通信可能範囲よりも広い範囲をカバーすることによって、直接接続できない地上局間の経路を飛行体局を介して接続する。正六角形の中心点には地上局或いは飛行体局をそれぞれ配置するものとし、中心点から多角形の辺までの距離はそれぞれの通信可能範囲を1/2に縮退させた距離を有する。正六角形は、実施の形態1で説明したように、ノードから電波の到達する通信可能範囲を球で示し(図10)、次に、球を二次元の円に単純化して、さらに、円を正六角形に置き換えたものである(図11)。実施の形態1で説明したように、球を二次元の円に単純化する際に通信可能範囲の重複を避けるため、円の半径を通信可能範囲の1/2に縮退する。すなわち、隣接する地上局1gとの間は、通信可能範囲Dgであって、正六角形の中心点から正六角形の辺までの長さは通信可能範囲Dgを1/2に縮退した距離を有する。また、隣接する飛行体局1aとの間は、通信可能範囲Daであって、正六角形の中心点から正六角形の辺までの長さは通信可能範囲Daを1/2に縮退した距離を有する。次に、図26中のメッシュ状の点線について説明する。このメッシュ状の点線は、双対グラフを示している。この点線は、隣接する正六角形の中心点同士を正六角形の辺を通過する線で結んだものである。1つの中心点は他の複数の中心点と結ばれるため、線が多数生成されてメッシュ状になる。地上局の双対グラフメッシュ6gと飛行体局の双対グラフメッシュ6aは、このようにして生成する。
【0078】
これらの双対グラフメッシュは、図9の斜向座標7に対応する。地上局の双対グラフメッシュ6gと飛行体局の双対グラフメッシュ6aとは、それぞれ地上局と飛行体局とでは通信可能範囲が異なるため、メッシュの1マスの大きさが異なる。
【0079】
図27は、この実施の形態の経路設計装置を構成する要素の一例を示すブロック図である。図27は実施の形態1の図3と同様の符号を付した要素は同様の動作をする。図3の説明と重複する部分があるが、図27の各要素について説明する。
図27において、経路設計装置50は、地上局のネットワークモデル10gを構成する地上局であるノード40から緯度情報と経度情報とを少なくとも有する位置情報60を受信する位置情報入力部51を備える。また、主に第1のグラフと第2のグラフを生成するフレームワーク処理部53と、ネットワーク設計における中継ノードの設定についての規則を示した縮退規則情報を、地上局のネットワークと飛行体局のネットワークに対してそれぞれ実行して、地上局のネットワークモデルの経路と飛行体局のネットワークモデルの経路とをそれぞれ設計する囲い込み処理部70とを備える。また、地上局のネットワークモデルと、飛行体局のネットワークモデルとから、これらのモデルを融合して、地上局間の接続を部分的に飛行体局を介して接続するネットワーク経路情報を生成して出力する経路情報融合部78(第2の経路設計部)を備える。
【0080】
フレームワーク処理部53は、通信範囲情報記憶部55と、第1のグラフ生成部である地上レイヤ斜向座標生成部57gと、第1の配置処理部である地上レイヤ配置処理部59gと、エリア生成部であるマルチホップ隣接ノードエリア生成部581とエリア分類部であるエリア和集合生成部582とを備えるクラスタ生成部58と、第2のグラフ生成部である航空レイヤ斜向座標生成部57aと、第2の配置処理部である航空レイヤ配置処理部59aとを備える。
囲い込み処理部70は、周囲境界縮小部73と、縮退規則情報記憶部75と、境界縮退部77と、第1の経路設計部である経路設計部79とを備える。
【0081】
通信範囲情報記憶部55は、ノード40の通信可能範囲を距離で示したその距離を第1の通信範囲情報として記憶する。さらに、飛行体局の通信可能範囲を距離で示したその距離を第2の通信範囲情報として記憶する。
地上レイヤ斜向座標生成部57gは、第1の通信可能範囲を1目盛りとする地上レイヤ斜向座標グラフを生成する。
航空レイヤ斜向座標生成部57aは、第2の通信可能範囲を1目盛りとする地上レイヤ斜向座標グラフを生成する。
【0082】
地上レイヤ配置処理部59gは、位置情報60に基づき、複数のノード40に対応する各座標点を地上レイヤ斜向座標グラフ上に配置する。
クラスタ生成部58は、地上レイヤ斜向座標グラフ上に配置した複数のノード40に対応する各座標点を、後述する条件に従い複数のクラスタに分割する。
マルチホップ隣接ノードエリア生成部581は、各ノードのマルチホップ隣接エリアを生成し、エリア和集合生成部582は、マルチホップ隣接エリアの和集合を生成して、クラスタ毎に各クラスタに含まれる地上局を取り囲む周囲境界線を地上レイヤ斜向座標グラフ上に生成する。地上レイヤ斜向座標グラフ上に生成した複数の周囲境界線の情報は、地上レイヤ配置処理部59gに出力する。地上レイヤ斜向座標グラフ上に生成した複数の周囲境界線の情報と、地上レイヤ斜向座標グラフを示す情報(例えば、図9の斜向座標7を展開するための情報)とは、航空レイヤ配置処理部59aに出力する。
【0083】
航空レイヤ配置処理部59aは、クラスタ生成部58から地上レイヤ斜向座標グラフを示す情報(例えば、図9の斜向座標7を展開するための情報)と、地上レイヤ斜向座標グラフ上に生成した複数の周囲境界線との情報とを入力して、地上レイヤ斜向座標グラフ上の複数のクラスタのうち1つのクラスタの周囲境界線の範囲内に航空レイヤ斜向座標グラフの原点が配置されるように、地上レイヤ斜向座標グラフに対して航空レイヤ斜向座標グラフを配置する。また、航空レイヤ斜向座標グラフは、地上レイヤ斜向座標グラフに対して、図25に示した高さHを地上レイヤ斜向座標グラフの面から垂直方向に有するように航空レイヤ斜向座標グラフを配置する。そして、航空レイヤ斜向座標グラフ上に地上レイヤ斜向座標グラフ上の各クラスタの周囲境界線を投射して、クラスタ毎の投射した周囲境界線の範囲内に各クラスタに対応して飛行体局を配置する座標を決める。例えば、航空レイヤ斜向座標グラフ上には、図26のようにメッシュ状に配置された点線が交差する点がある。この点は正六角形の中心点であって、「頂点」と呼ぶ。航空レイヤ斜向座標グラフ上に投射したクラスタ毎の周囲境界線の範囲内に含まれる頂点を、各クラスタに対応する飛行体局を配置する座標点とする。また、各クラスタに対応する飛行体局を配置する座標点を取り囲む周囲境界線を航空レイヤ斜向座標グラフ上に生成し、囲い込み処理部70に渡す。
【0084】
囲い込み処理部70は、地上レイヤと航空レイヤで共通して使用する。周囲境界縮小部73は、地上レイヤ斜向座標グラフ上の周囲境界線を周囲境界線の内側に移動させて周囲境界線が囲い込む範囲を縮小する縮小周囲境界線を、地上レイヤ斜向座標グラフ上に生成する。また、周囲境界縮小部73は、航空レイヤ斜向座標グラフ上の周囲境界線を周囲境界線の内側に移動させて周囲境界線が囲い込む範囲を縮小する縮小周囲境界線を、航空レイヤ斜向座標グラフ上に生成する。
【0085】
縮退規則情報記憶部75は、航空レイヤ斜向座標グラフ上の縮小周囲境界線と、地上レイヤ斜向座標グラフ上の内側にそれぞれ仮想通信装置を配置させて、仮想通信装置上を通過する縮小周囲境界線を縮退させた縮退周囲境界線を生成する規則を示す縮退規則情報を記憶する。縮退規則情報は、航空レイヤ斜向座標グラフ用と地上レイヤ斜向座標グラフ用で共通であっても、異なっていてもかまわない。異なる場合には、航空レイヤ用であるのか地上レイヤ用であるのかを識別する識別情報を縮退規則情報に含める。
【0086】
境界縮退部77は、縮退規則情報記憶部75が記憶する縮退規則情報に従い、仮想通信装置を航空レイヤ斜向座標グラフ上の縮小周囲境界線の内側に配置して、航空レイヤ斜向座標グラフ上の縮小周囲境界線の内側に配置する仮想通信装置を通過するように縮小周囲境界線を縮退させて、縮退周囲境界線を航空レイヤ斜向座標グラフ上に生成する。また、縮退規則情報記憶部75が記憶する縮退規則情報に従い、仮想通信装置を地上レイヤ斜向座標グラフ上の縮小周囲境界線の内側に配置して、地上レイヤ斜向座標グラフ上の縮小周囲境界線の内側に配置する仮想通信装置を通過するように縮小周囲境界線を縮退させて、縮退周囲境界線を地上レイヤ斜向座標グラフ上に生成する。
【0087】
経路設計部79は、境界縮退部77が生成した地上レイヤ斜向座標グラフ上の縮退周囲境界線と、ノード40の座標点と、仮想通信装置の地上レイヤ斜向座標グラフ上の位置とから、中継ノードを配置する地上局のネットワークモデル上の位置を決定して、地上局のネットワークモデルのネットワーク経路を設計して地上局の経路情報を生成して出力する。また、経路設計部79は、境界縮退部77が生成した航空レイヤ斜向座標グラフ上の縮退周囲境界線と、飛行体局を配置する座標点と、仮想通信装置の航空レイヤ斜向座標グラフ上の位置とから、中継ノードを配置する飛行体局のネットワークモデル上の位置を決定して、飛行体局のネットワークモデルのネットワーク経路を設計して飛行体局の経路情報を生成して出力する。
【0088】
経路情報融合部78は、地上レイヤの経路情報と航空レイヤの経路情報とに基づいて、地上レイヤにおいて、地上局だけでは接続できないクラスタ間を飛行体局を介して接続するネットワーク経路情報を生成する。
【0089】
図28〜図32を用いて、図33の経路設計装置の処理の手順を示すフローチャートに従い、処理内容を説明する。
図28(a)は、地上レイヤ配置処理部が地上レイヤ斜向座標グラフ上に地上局を配置した例を示す図である。図28(b)は、クラスタ生成部が地上レイヤ斜向座標グラフ上の地上局を複数のクラスタに分類した例を示す図ある。
図29は、地上レイヤ斜向座標グラフに対して航空レイヤ斜向座標グラフを配置した例を示す図である。
図30は、地上レイヤ斜向座標グラフ上のクラスタ毎の周囲境界線を航空レイヤ斜向座標グラフ上に投射した例を示す図である。
図31(a)は、航空レイヤ斜向座標グラフ上にクラスタ毎に対応する飛行体局を配置した例を示す図である。図31(b)は、地上レイヤ斜向座標グラフ上の仮想ノードを配置した縮退周囲境界線の例を示す図である。
図32は、航空レイヤ斜向座標グラフ上の仮想ノードを配置した縮退周囲境界線の例を示す図である。
【0090】
図33において、地上局のネットワークモデル10gの有する複数のノード40からそれぞれノードの位置を示す位置情報60を、位置情報入力部51により入力する(S1,位置情報入力工程)。位置情報60は、緯度情報と経度情報とを有して、ノードの位置を表す。入力した位置情報60は、フレームワーク処理部53へ出力する。
【0091】
フレームワーク処理部53は、地上レイヤ斜向座標生成部57gによって、例えば図9に示す斜向座標グラフを生成する(S2g,地上レイヤ斜向座標生成工程)。
【0092】
ここで、斜向座標生成手順を説明する。この手順は、地上レイヤ斜向座標グラフを生成する手順と、航空レイヤ斜向座標グラフを生成する手順とで共通である。ただし、航空レイヤ斜向座標グラフを生成する場合、第1の通信範囲情報に代えて第2の通信範囲情報を使用する。
はじめに、多角形を正六角形とする。正六角形とする理由は、実施の形態1で説明したように、六角形は電波伝搬を反映した円に近いためである。正六角形の辺を共有させて正六角形を隣接させて複数配置する。このとき、それぞれの正六角形は、中心点から辺までの垂直線の長さを第1の通信範囲情報の1/2とする。このように複数の正六角形を隣接して配置した図が図12(a)である。次に、各正六角形の中心点同士を正六角形の辺を通過する線で結ぶ。正六角形の中心点を結んだ線を示した図が、図13(a)である。図13のように、中心点同士を結ぶ線は複数できる。この複数の線の中からx軸とする線と、y軸とする線とをそれぞれ選択して、選択したそれぞれの線をx軸、y軸とする斜向座標グラフを生成する。生成した斜向座標グラフの一例が図9の斜向座標7である。x軸は、ノードの位置情報のうち、経度情報を距離に変換した値示す。y軸は、ノードの位置情報のうち、緯度情報を距離に変換した値を示す。x軸、y軸のそれぞれの1目盛りは、第1の通信可能範囲であることが図11からわかる。図28〜図32の地上局のネットワークモデル10gは、地上レイヤ斜向座標グラフの一部を示したものであり、飛行体局のネットワークモデル10aは、航空レイヤ斜向座標グラフの一部を示したものである。
【0093】
次に、フレームワーク処理部53は、地上レイヤ配置処理部59gによって、S1で入力したノード40の位置情報から地上レイヤ斜向座標グラフ上の座標点を求めて、求めた座標点にノード40を配置する(S3g、地上レイヤ配置処理工程)。図28(a)の●の地上局1gがノード40である。求めた座標点が地上レイヤ斜向座標グラフ上の点線が交差する交点(頂点と呼ぶ)でない場合は、求めた座標点を直近の頂点の座標点に近似させる。
ここで、ノード40の位置情報から座標点を求める一例を説明する。図43は、位置情報から座標点を求める一例を説明する図である。経度1度分の距離は、極に近いほど短くなり、また、地球は真球ではく、表面は球面ではない等の種種の要素を考慮に入れると微妙な違いがあるが、経度1度分,緯度1度分のそれぞれ距離は約111kmであるとする。例えば図43に示すようにノードAの位置情報が(東経139度,北緯35度)、ノードBの位置情報が(東経140度,緯度36度)であるとする。これらの位置情報を図43の経緯度への展開430のように、ノードAの位置情報(東経139度,北緯35度)を原点とするグラフ431(x軸は経度、y軸は緯度を示す)に配置する。次に、この経緯度に展開したものを図43の直交座標への展開432のように、直交座標に展開する。このとき直交座標のx軸は東経方向を示し、1目盛りは11.1kmとし、y軸は緯度方向を示し、1目盛りは11.1kmとする。ノードAは原点であるため、座標は(0,0)となり、ノードBはノードAと緯度、経度ともに1度の差があるため、ノードBの座標は(10,10)となる。次に、直交座標に展開したものを、地上レイヤの斜向座標グラフに展開する。地上レイヤの斜向座標グラフは六角形を元にして生成したグラフであるため、x軸に対するy軸の傾きは60度である。このため、斜向座標への展開には三角関数を用いる。図43の直行座標でのノードAの座標は(0,0)、ノードBの座標は(10,10)であった。これらの座標を三角関数を用いて変換すると、図43の斜向座標への展開434に示すように、地上レイヤの斜向座標グラフ(グラフ435)上には、ノードAは原点であるためそのまま座標点は変わらずに(0,0)とし、ノードBの座標は、(10−10/√3,10×2/√3)、すなわち(10×(1−1/√3),20/√3)となる。これを小数で近似すると(4.2,11.6)となり、さらに、整数で近似すると(4,12)となる。
このとき、地上レイヤの斜向座標グラフのx軸は東経方向を示し、y軸は北緯方向から30度の方向を示す。このように、地上レイヤ配置処理部59gは、ノードの位置情報を地上レイヤの斜向座標グラフ上の座標点に変換して、地上レイヤの斜向座標グラフ上に配置する。
【0094】
図33へ戻る。図33のS3gでは、地上レイヤ配置処理部59gが、図28(a)のように8個の地上局のそれぞれの位置に対応する地上レイヤメッシュ7g上の座標点を求め、求めた地上局1gの座標点を●として地上レイヤメッシュ7g上に配置して、地上局のネットワークモデル10gを生成する。
【0095】
次に、S4gでは、クラスタ生成部58により、地上レイヤメッシュ7g上の8個の地上局1gを複数のクラスタに分けて、複数のクラスタ毎にクラスタに含まれる地上局を取り囲む周囲境界線を地上レイヤメッシュ7g上に生成する。
【0096】
図35、図36、図37を用いて、クラスタ生成部58の動作の一例を説明する。図35は、マルチホップについて説明する図である。図36(a)は、ホップ数を1とした場合の地上局それぞれのノード範囲(エリア)を示す図であり、図36(b)は、ホップ数を2とした場合の地上局それぞれのノード範囲(エリア)を示す図である。図37は、クラスタ生成部58によるクラスタ生成処理S4gを示す。
図37において、クラスタ生成部58のマルチホップ隣接ノードエリア生成部581は各地上局について、指定する最大ホップ数のマルチホップ隣接エリアを生成する(S20、マルチホップ隣接ノードエリア生成工程)。このマルチホップ隣接エリアとは、例えば図35の隣接ノード範囲1NB1,1NB2,1NB3を指す。隣接ノード範囲1NB1は、中央の地上局1Cから1目盛り(ホップ数1)の距離にある複数の1ホップ隣接ノードまでの範囲を示す。隣接ノード範囲1NB2は、地上局1Cから2目盛り(ホップ数2)の距離にある複数の2ホップ隣接ノードまでの範囲を示す。隣接ノード範囲1NB3は、地上局1Cから3目盛り(ホップ数3)の距離にある複数の3ホップ隣接ノードまでの範囲を示す。図36にマルチホップ隣接ノードエリア生成部581が各地上局毎に生成したマルチホップ隣接エリアを示す。図36(a)は、ホップ数を1とした場合の6個の地上局毎に生成した隣接ノード範囲を示す。図36(b)は、ホップ数を2とした場合の6個の地上局毎に生成した隣接ノード範囲を示す。図36(a)では、近隣のノードが他のノードの1ホップ隣接ノード範囲1NB1に含まれていない。これは、1ホップでは、各ノードが他のノードを含まず、それぞれ独立する。図36(b)では、各ノードの2ホップ隣接ノード範囲1NB2を示す。図36(b)では、近隣のノードが他のノードの2ホップ隣接ノード範囲1NB2に含まれている。これは、2ホップにすると複数のノードを含むクラスタが生成できることを示す。そこでクラスタ生成部58は、ホップ数を2として記憶する分類条件記憶部を備えるものとして、マルチホップ隣接ノードエリア生成部581が分類条件記憶部に記憶されたホップ数「2」に基づいて、地上局ごとの隣接ノード範囲を生成する。
【0097】
クラスタ生成部58のエリア和集合生成部582は、マルチホップ隣接ノードエリアのうち、他ノードを含むエリアの和集合をとり、出来た和集合を1つのクラスタとして、複数の地上局を複数のクラスタに分ける(S21、エリア和集合生成工程)。例えば、マルチホップ隣接ノードエリア生成部581がホップ数を2として隣接ノード範囲を生成すると、図36(b)の6個のノード1を含む隣接ノード範囲1NB2が生成される。クラスタ生成部58のエリア和集合生成部582は、他ノードを含むエリアの和集合として図36(b)の6個の隣接ノード範囲1NB2を隣接ノード範囲の和集合として生成する。生成し隣接ノード範囲の和集合の1つは、1つのクラスタに対応する。このようにして、クラスタ生成部85は、地上レイヤメッシュの斜向座標7上の複数のノード1をクラスタに分類する。
【0098】
クラスタ生成部58は、図28(a)の地上レイヤメッシュ7g上に配置した8個の地上局1gを、ホップ数1として(クラスタ生成部58は、ホップ数「1」を記憶する分類条件記憶部を備える)複数のクラスタに分類して、図28(b)のように、クラスタ21を2つ生成する。そして、2つのクラスタ21ごとに、クラスタに含まれる周囲境界線を、地上レイヤメッシュ7g上にそれぞれ生成する。クラスタ毎の周囲境界線の生成動作は、実施の形態1で説明した図8のS10及び図3の配置処理部59と同じである。クラスタ生成部58は、図29に示すようにクラスタ毎に地上レイヤの周囲境界線3Bgを、地上レイヤメッシュ7g上に生成する。
【0099】
次に、航空レイヤ配置処理部59aが、地上レイヤに対応して航空レイヤを配置して、配置した航空レイヤに各クラスタに対応した飛行体局を配置する(S3a,航空レイヤ配置処理工程)。まず航空レイヤ配置処理部59aは、クラスタ生成部85から、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局の座標点と、複数のクラスタを示すとともに各クラスタが含む地上局の情報と、複数の地上レイヤの周囲境界線を地上レイヤの斜向座標グラフ上に示す情報とを入力する。また、航空レイヤ配置処理部59aは、航空レイヤ斜向座標生成部57aから、航空レイヤ斜向座標グラフを展開することができる情報を入力する。そして、入力した複数のクラスタを示す情報から、1つのクラスタを選択する。このクラスタの選択は、例えば位置情報入力部51が地上局の位置情報を入力した際に一番電波が強い地上局を含むクラスタを選択する。あるいは、例えば部隊の隊員一人一人が地上局である通信端末装置を携帯しているような場合には、隊長が携帯している通信端末装置を含むクラスタを選択するようにしてもかまわない。この場合、隊長の通信端末装置の識別情報を予め経路設計装置50に記憶しておくとともに、位置情報と一緒に通信端末装置の識別情報を入力する。入力した通信端末装置の識別情報は、各クラスタが含む地上局の情報に含めて航空レイヤ配置処理部59aが受け取る。航空レイヤ配置処理部59aは、各クラスタが含む地上局の情報に含まれた通信端末装置の識別情報から、記憶した隊長の通信端末装置の識別情報と一致する通信端末装置を含むクラスタを選択する。
【0100】
航空レイヤ配置処理部59aは、このように選択した1つのクラスタの周囲境界線の取り囲む範囲内に、航空レイヤ斜向座標グラフの原点が配置されるように航空レイヤ斜向座標グラフの面を、地上レイヤ斜向座標グラフの面に対して垂直方向に高さHを有して平行に配置する。例えば、図29に示すように、選択した1つのクラスタの周囲境界線の取り囲む範囲内に含まれる1つの地上局100gの座標点と航空レイヤ斜向座標グラフの原点100aとを合わせる。このとき、地上レイヤメッシュ7g(地上レイヤ斜向座標グラフの面)に対して航空レイヤメッシュ7a(航空レイヤ斜向座標グラフの面)を平行に配置する。さらに、地上レイヤメッシュ7g(地上レイヤ斜向座標グラフの面)の垂直方向に高さHを有するように航空レイヤメッシュ7a(航空レイヤ斜向座標グラフの面)を配置する。この高さHは、例えば飛行体局である無線通信端末装置を搭載する航空機の地上からの高度であり、高度は飛行体局の通信可能範囲が示す距離を越えない距離である。
【0101】
次に、各クラスタに対応させて飛行体局を航空レイヤメッシュ7a上に配置する動作を、図29に示したネットワークモデル10を例に説明する。航空レイヤ配置処理部59aは、航空レイヤメッシュ7a上に図29の地上レイヤメッシュ7g上の右側にあるクラスタ21のクラスタの範囲を示す線、或いは、クラスタの周囲境界線を投射する。ここでは、図30に示すように、図29の右側のクラスタ21の地上レイヤの周囲境界線3Bgを投射する。図29の左側のクラスタについては、このクラスタに対する飛行体局を航空レイヤ斜向座標グラフの原点100aに配置したため、クラスタの範囲を示す線、或いは、クラスタの周囲境界線を投射する処理は行わない。航空レイヤ配置処理部59aは、投射した周囲境界線の取り囲む範囲内の頂点(頂点とは、メッシュを構成する線と線とが交差する点である。例えば、図30の航空レイヤメッシュ7aの点線の交差する点である。)を飛行体局を配置する座標点とする。図30では、座標点101aを飛行体局1aを配置する位置とする。座標点101aは、図30の地上レイヤメッシュ7gの右側にあるクラスタに対応する飛行体局を配置する座標点である。図31(a)に、地上レイヤメッシュ上の2つのクラスタ21にそれぞれ対応して、航空レイヤメッシュ7a上に配置する飛行体局1aの座標点を示す。航空レイヤ配置処理部59aは、航空レイヤメッシュ7a上の飛行体局を配置する2つの座標点を取り囲む周囲境界線を航空レイヤメッシュ7aに生成する。この周囲境界線を生成する処理は、実施の形態1で説明した図8のS10及び図3の配置処理部59と同じである。
【0102】
ここまで説明した図33のS2g〜S4g及びS2a、S3aの処理がフレームワーク処理部53によるフレームワーク処理である。フレームワーク処理は、例えば磁気ディスク装置146のプログラム群149に記憶されたプログラムをフレームワーク処理部53が実行することによって実現する。また、通信範囲情報記憶部55、分類条件記憶部は、磁気ディスク装置146のファイル群150に記憶されている。フレームワーク処理部53は、CPU137であり、CPU137は磁気ディスク装置146のプログラム群149からフレームワーク処理を行うプログラムを呼び出して、プログラムに従いS2g〜S4g及びS2a、S3aのフレームワーク処理を行う。
【0103】
続いて、経路設計装置50は、囲い込み処理部70による図33のS5g、S5aの囲い込み処理の手順について説明する。S5g、S5aの囲い込み処理の詳細な手順を図34に示す。図34に示したS10〜S13の処理内容は、実施の形態1で説明した図8のS10〜S13の処理内容と同様である。S10の周囲境界線を生成する処理は、S4gのクラスタ生成部58による地上レイヤメッシュ7gにクラスタごとの周囲境界線を生成する処理と、S3aの航空レイヤ配置処理部59aによる航空レイヤメッシュ7aに周囲境界線を生成する処理を指す。しかし、これらの周囲境界線を生成する処理は、囲い込み処理に含めてもかまわない。この場合、クラスタ生成部58と航空レイヤ配置処理部59aとは、フレームワーク処理部53と囲い込み処理部70とで共有する。また、地上レイヤメッシュ7g上と航空レイヤメッシュ7a上にそれぞれ生成した複数の周囲境界線を、それぞれのレイヤメッシュ別に周囲境界線を平行移動して範囲を縮小するS11の処理と、縮小した周囲境界線を縮退するS12の処理と、仮想ノードを中継ノードに変更して、中継ノードを含む経路設計情報とを生成する処理とは、地上局のネットワークモデルと飛行体局のネットワークモデルとで、別々に行う。言い換えると、周囲境界縮小部73は、地上局のネットワークモデルに関連する情報として、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局の座標点と、複数のクラスタを示すとともに各クラスタが含む地上局の情報と、複数の地上レイヤの周囲境界線を地上レイヤの斜向座標グラフ上に示す情報とを入力する。そして、これら入力した情報から地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局の座標点と、複数のクラスタを示すとともに各クラスタが含む地上局の情報と、地上レイヤの複数の周囲境界線を地上レイヤの斜向座標グラフ上に示す情報と、地上レイヤの複数の周囲境界線をそれぞれ縮小した複数の縮小周囲境界線とを出力する。さらに、周囲境界縮小部73は、飛行体局のネットワークモデルに関連する情報として、航空レイヤ斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局の座標点と、航空レイヤの周囲境界線を航空レイヤの斜向座標グラフ上に示す情報とを入力する。そして、これら入力した情報から航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局の座標点と、航空レイヤの周囲境界線を航空レイヤの斜向座標グラフ上に示す情報と、航空レイヤの周囲境界線を縮小した複数の縮小周囲境界線とを出力する。
【0104】
また、境界縮退部77は、地上ネットワークモデルに関連する情報として、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局の座標点と、複数のクラスタを示すとともに各クラスタが含む地上局の情報と、複数の地上レイヤの縮小周囲境界線を地上レイヤの斜向座標グラフ上に示す情報とを入力する。そして、これら入力した情報から地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局と仮想ノードの座標点と、複数のクラスタを示すとともに各クラスタが含む地上局の情報と、地上レイヤの複数の縮小周囲境界線をそれぞれ、縮退規則情報記憶部75に記憶した縮退規則情報に従い縮退した複数の縮退周囲境界線とを出力する。さらに、境界縮退部77は、飛行体局のネットワークモデルに関連する情報として、航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局の座標点と、航空レイヤの縮小周囲境界線を航空レイヤの斜向座標グラフ上に示す情報とを入力する。そして、これら入力した情報から航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局と仮想ノードの座標点と、航空レイヤの縮小周囲境界線をそれぞれ、縮退規則情報記憶部75に記憶した縮退規則情報に従い縮退した縮退周囲境界線とを出力する。縮退規則情報記憶部75が記憶する縮退規則情報は、1つの縮退規則情報を記憶して、境界縮退部77が地上ネットワークモデルと、航空ネットワークモデルとで、同じ縮退規則情報に従いそれぞれの縮小周囲境界線を縮退させる。または、地上局のネットワークモデルと、飛行体局のネットワークモデルとで、異なる縮退規則情報を記憶して、境界縮退部77が地上局のネットワークモデルと、飛行体局のネットワークモデルとで、それぞれ用の縮退規則情報に従い縮小周囲境界線を縮退させる。
【0105】
図31(b)は、地上局のネットワークモデル10gの地上レイヤメッシュ7g上と飛行体局のネットワークモデル10aの航空レイヤメッシュ7a上に縮退規則情報に従い仮想ノード1Vg、1Vaを配置した例を示す図である。図31(b)に示すように、仮想ノード1Vaを配置することによって、2つの飛行体局1a間は、2つのリンクで接続される。
【0106】
経路設計部79は、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局と仮想ノードの座標点と、複数のクラスタを示すとともに各クラスタが含む地上局と仮想局の情報と、地上レイヤの複数の縮小周囲境界線をそれぞれ、縮退規則情報記憶部75に記憶した縮退規則情報に従い縮退した複数の縮退周囲境界線とを入力する。そして、これらの入力した情報から、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局と中継ノードの座標点と、複数のクラスタを示すとともに各クラスタが含む地上局と中継局の情報と、地上レイヤの複数の縮退周囲境界線と、地上局と中継ノードとの間のリンクを示す情報とを出力する。さらに、経路設計部79は、航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局と仮想ノードの座標点と、航空レイヤの縮小周囲境界線をそれぞれ、縮退規則情報記憶部75に記憶した縮退規則情報に従い縮退した縮退周囲境界線とを入力する。そして、これらの入力した情報から、航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局と中継ノードの座標点と、航空レイヤの縮退周囲境界線と、飛行体局と中継ノードとの間のリンクを示す情報とを出力する。
【0107】
図31(b)を例にすると、経路設計部79は、地上レイヤメッシュ7gと航空レイヤメッシュ7aとをそれぞれ展開することができる情報と、地上レイヤメッシュ上の2つのクラスタを示す情報及び、それぞれのクラスタとそれぞれのクラスタが含む地上局1gの座標点と仮想ノード1Vgの座標点と縮退周囲境界線とを示す情報と、航空レイヤメッシュ上の飛行体局1aの座標点と仮想ノード1Vaの座標点と縮退周囲境界線とを示す情報とを出力する。
このように、囲い込み処理部70の各構成要素は、地上局のネットワークモデル用の処理と、飛行体局のネットワークモデル用の処理との2つの処理を行う。
【0108】
図33に戻る。図33のS6では、経路情報融合部78は、地上局のネットワークモデルに関する情報と、飛行体局のネットワークモデルに関する経路情報80Pとを入力する。例えば、地上局のネットワークモデルに関する情報として、地上レイヤの斜向座標グラフを展開することができる情報と、地上レイヤの斜向座標グラフ上に配置した複数の地上局と中継ノードの座標点と、複数のクラスタを示すとともに各クラスタが含む地上局と中継局の情報と、地上レイヤの複数の縮退周囲境界線と、地上局と中継ノードとの間のリンクを示す情報とを入力する。さらに、飛行体局のネットワークモデルに関する情報として、航空レイヤの斜向座標グラフを展開することができる情報と、航空レイヤの斜向座標グラフ上に配置した複数の飛行体局と中継ノードの座標点と、航空レイヤの縮退周囲境界線と、飛行体局と中継ノードとの間のリンクを示す情報とを入力する。そして、これらの入力した情報から、地上局のネットワークモデルの2つのクラスタの間を、飛行体局のネットワークモデルを介して接続する。飛行体局のネットワークモデルを介する接続とは、各クラスタ毎に、各クラスタに対応する飛行体局と、そのクラスタに含まれる地上局とをリンクして接続する。例えば図32のネットワークモデル10を例に、地上局のネットワークモデルと飛行体局のネットワークモデルとを、地上局のネットワークモデルの複数のクラスタ間を飛行体局のネットワークモデルを介して接続するネットワーク経路情報の生成について説明する。
【0109】
経路情報融合部78は、1つのクラスタとそのクラスタに対応する飛行体局との間を2つのリンクで接続する。2つのリンクとは1つの飛行体局を2つの地上局で接続して1つの地上局から飛行体局への経路を2経路とすることである。例えば経路情報融合部78は、図32の2つの飛行体局のそれぞれの飛行体局1a毎に、各飛行体局に対応するクラスタが含む複数の地上局の内、2つの地上局とのリンク2を生成する。2つの地上局とのリンクを接続することによって、一方の地上局が通信できなくなっても、他方の地上局とのリンクを使用して、地上局と飛行体局間との通信を行うことができる。複数の地上局のうち飛行体局と接続する地上局は、いずれの地上局を選択しても構わない。例えば、電波の強い地上局から順に優先して選択する。または、クラスタが部隊を構成するような場合には、部隊の隊長が携帯している通信端末装置と副隊長が携帯している通信端末装置とを、経路情報融合部78が優先して選択する。この場合、あらかじめ隊長と副隊長がそれぞれ携帯する通信端末装置の識別情報を経路設計装置50が記憶しておく。また、位置情報とともに、通信端末装置の識別情報を入力する。入力した通信端末装置の識別情報は、通信端末装置(地上局)の座標点を示す情報に対応させて、経路設計装置が備える記憶装置に記憶しておく。経路情報融合部78は、クラスタが含む複数の地上局の座標点から、座標点に対応する通信端末装置の識別情報を取得する。そして、取得した識別情報に基づいて、あらかじめ記憶しておいた隊長あるいは副隊長がそれぞれ携帯する通信端末装置の識別情報と一致することを確認して、一致することが確認できたら、確認できた2つの地上局を、飛行体局とリンクする地上局として選択する。
このように、地上レイヤと航空レイヤの2つの異なるレイヤそれぞれに配置した複数の局(ノード)をリンクする経路を生成することを融合という。
【0110】
融合を行った結果生成されるネットワーク経路情報(経路情報80T)は、例えば、図32の例では、地上レイヤメッシュ7g上の地上局1gの座標点と中継ノード1Rgの座標点、地上レイヤの周囲境界線3Bg、航空レイヤメッシュ7a上の飛行体局1aの座標点と中継ノード1Raの座標点、航空レイヤの周囲境界線3Ba、地上局と飛行体局とのリンク2とである。また、高さHもネットワーク経路情報(経路情報80T)に含める。
【0111】
この実施の形態の経路設計装置は、多角形グリッド、双対グラフメッシュ、斜向座標によるネットワーク設計フレームワークを複数階層構造で用いることにより、例えば人が携帯する無線通信端末装置(地上局)を配置する面を地上レイヤとし、飛行体が搭載する無線通信端末装置(飛行体局)を配置する面を航空レイヤとした場合、広域に渡って配置された地上局が移動し、リンクが定まっていない場合でも、飛行体局を経由して地上局を接続する複数の経路、および中継ノードを設計できるという効果がある。
また、厳密に最適経路を求めるためには、全ノードの組み合わせを検証する膨大な処理を必要とするネットワーク設計であるが、この発明の複数階層にわたる囲い込みアルゴリズムにより、簡便に広域に渡って配置された全ノード間を2本以上の経路で接続する経路を求めることができる。これにより、航空機などの飛行体により中継を行なって、広域にわたって配置するノード間の通信経路を設定する場合、一個の通信経路を確保するだけでなく、複数の独立経路を設計し、障害時の迂回経路を確保することができる。
【0112】
実施の形態7.
上記実施の形態6では、地上レイヤメッシュの面に対して航空レイヤメッシュの面を配置した際に、地上レイヤメッシュのクラスタを航空レイヤメッシュ上に投射すると、航空レイヤメッシュ上の頂点(点線で示した複数のメッシュの交差する交点)がクラスタの取り囲む範囲内に少なくとも1つ存在していた。しかし、航空レイヤメッシュ上の頂点(点線で示した複数のメッシュの交差する交点)がクラスタの取り囲む範囲内に存在していない場合がある。この場合には、頂点がクラスタの取り囲む範囲に内に存在するように航空レイヤメッシュの面を移動して、地上レイヤメッシュの面に対する航空レイヤメッシュの面の位置を調整をする。
【0113】
図38は、実施の形態7の航空レイヤメッシュ上に投射したクラスタの取り囲む範囲内に頂点が存在しない例を示す図である。図38のクラスタ21の中心点21cの方向に航空レイヤメッシュ7a上の頂点がずれるように航空レイヤメッシュ7aの面を移動して、頂点がクラスタの取り囲む範囲に内に存在するように航空レイヤメッシュの面の位置を調整する。
図39は、実施の形態7の経路設計装置の構成を示すブロック図である。航空レイヤ配置処理部59aが調整部591を備えることの他は、実施の形態6の図27の経路設計装置と同様の構成である。航空レイヤ配置処理部59aは、航空レイヤメッシュ上に投射したクラスタの取り囲む範囲内に頂点が存在しない場合に、調整部591によりクラスタ21の中心点21cの方向に航空レイヤメッシュ7a上の頂点がずれるように航空レイヤメッシュ7aの面移動する。
図40は、調整部591の動作手順を示すフローチャート図である。
図41は、調整部591の別の動作手順を示すフローチャート図である。
まず、図40のフローチャートに従い調整部591による航空レイヤメッシュの面を移動する手順を説明する。なお、図40及び図41に示した動作は、図33のS3aの航空レイヤ配置処理工程の中で、航空レイヤメッシュ上に投射した複数のクラスタの中に、クラスタの取り囲む範囲内に頂点が存在しないクラスタがある場合に行う。
【0114】
図40の調整部591の処理は、調整を行うときの基準に使用するクラスタの中心点に、その中心点に近い位置の航空レイヤメッシュ上の頂点(この頂点を他の頂点と区別するため「頂点A」と呼ぶ)を合わせる。図26に示すように、航空レイヤメッシュ7aの1マスの大きさ(1マスとは図26の飛行体局1aを中心点とする正六角形のことである)は、地上レイヤメッシュの1マス(1マスとは図26の地上局1gを中心点とする正六角形のことである)の複数分である。調整部591は、航空レイヤメッシュ1マスが含む複数のマス目の各中心点に頂点Aを順次移動させて、頂点Aの最適位置を探す。最適位置とは、地上レイヤメッシュ上の複数のクラスタを航空レイヤメッシュ上に投射した場合に、投射した各クラスタの取り囲む範囲内に、航空レイヤメッシュ上の頂点が含まれる場合の地上レイヤメッシュに対する航空レイヤメッシュの位置をさす。
【0115】
図40において、調整部591は、地上レイヤメッシュ上の複数のクラスタごとに、各クラスタの中心点21cを求める。この中心点21cは、クラスタ毎に、各クラスタが含む複数の地上局の座標点から求められる平均の座標点とする(SA0)。次に、クラスタ毎に求めた複数の中心点21cの中から1つの中心点21cを選択する。選択した中心点21cの座標点に一番近い位置にある航空レイヤメッシュ上の頂点を合わせて、航空レイヤメッシュの初期位相を設定する(SA1)。この頂点が頂点Aである。1つの中心点を選択する条件は、例えば、電波の一番強い地上局を含むクラスタの中心点を選択したり、クラスタの取り囲む範囲が一番大きいクラスタの中心点を選択するなどの条件をあらかじめ経路設計装置の記憶部に記憶させておき、記憶部に記憶した条件を調整部591が取得する。または、条件は設けず、ランダムに1つのクラスタの中心点を選択しても構わない。初期位相の設定を行った後、SA2では、クラスタ毎に、クラスタを航空レイヤメッシュに投射した場合の各クラスタの中心点21cと中心点21cに一番近い航空レイヤメッシュ7a上の頂点との距離を求める。クラスタ毎の求めた距離と中心点21cと頂点Aの座標とを対応させて、経路設計装置の記憶部に記憶する。続いて、SA3では、航空レイヤメッシュ7aの頂点Aを、選択したクラスタの取り囲む範囲内にある地上レイヤメッシュ7gの別のマスの中心点にずらす。上記したSA2とSA3の処理とを、選択したクラスタの取り囲む範囲内にある全てのマスの中心点に頂点Aを移動させるまで繰り返す(SA4)。SA2、SA3の処理の繰り返しが終了したら、SA2で記憶したクラスタ毎の求めた距離から全クラスタの平均の距離を、頂点Aの座標毎に求めて、求めた全クラスタの平均の距離のうち最小の平均距離を検索して、検索できた最小のクラスタ平均距離の頂点Aの座標を、SA1で選択したクラスタの中心点に合わせて、航空レイヤメッシュを地上レイヤメッシュに対して配置する。
【0116】
また、別の調整部591の処理手順を図41のフローチャートに従い説明する。図41の調整部591に処理では、航空レイヤメッシュ上に投射した複数のクラスタ毎に各クラスタの中心点からその中心点に一番近い位置にある頂点までの距離を求める(SA10)。そして、各クラスタ毎に求めた距離から、全クラスタ平均の距離を求め(SA11)、求めた全クラスタ平均の距離をSA10で使用した頂点の座標とともに、経路設計装置の記憶部の有するテーブルに記憶する(SA12)。各クラスタ毎に求めた距離と、全クラスタ平均の距離との差をクラスタ毎に求めて、差が一番大きいクラスタを選択する(SA13)。SA13で求めた差を所定の数、例えば10で割り、その商を調整部591の調整値とする(SA14)。商である調整値分の距離だけ、SA13で選択したクラスタの中心点へSA10の頂点を移動するように航空レイヤメッシュの面を地上レイヤメッシュの面に対してずらす(SA15)。SA15の後、複数のクラスタ毎に、各クラスタの中心点を求める(SA16)。複数のクラスタ毎に、求めたクラスタの中心点からその中心点に一番近い位置にある頂点までの距離を求める(SA17)。そして、各クラスタ毎に求めた距離から、全クラスタ平均の距離を求め各クラスタ毎に求めた距離から、全クラスタ平均の距離を求め、求めた全クラスタ平均の距離を、SA17で距離の計算に使用した頂点の座標点とともに経路設計装置の記憶部の有するテーブルに記憶する(SA18)。SA15からSA18の処理を、SA14の差を割った値の回数、例えば10回、繰り返す(SA19)。繰り返しが完了したら、記憶部の有するテーブルに記憶した全クラスタ平均の距離から、最も小さい値を検索して、検索できた値に対応する頂点の座標点にSA10の頂点を移動させて、航空レイヤメッシュを地上レイヤメッシュに対して配置する。なお、クラスタの中心点の求め方は、図40と同様である。
このようにして、調整部591は、地上レイヤメッシュに対する航空レイヤメッシュの位置を調整する。SA19及びSA14では「10」を使用したが、これに限らず、「10」よりも大きい値や小さい値を任意に設定して使用出来る。
【0117】
なお、調整部591を備えない場合であって、クラスタの取り囲む範囲内に航空レイヤメッシュの頂点が存在しない場合、航空レイヤメッシュのメッシュを構成する線上にクラスタ間を中継する飛行体局を配置して、さらに、その飛行体局を配置した座標点に近い航空レイヤメッシュの頂点に中継用のノードを配置して、クラスタの取り囲む範囲内に航空レイヤメッシュの頂点が存在しない場合の飛行体局によるクラスタの中継をサポートできる。ただしこの場合には、必要な飛行体局を搭載する飛行体を、調整部を備える場合よりも多くの数必要となるため、ネットワークの構築に費用がかかる。
【0118】
この実施の形態の経路設計装置は、調整部を備えたことにより、クラスタの取り囲む範囲内に航空レイヤメッシュ状の頂点が存在しないクラスタが存在しても、航空レイヤメッシュの面を地上レイヤメッシュの面に対して移動させて、クラスタの取り囲む範囲内に航空レイヤメッシュ状の頂点が存在するようにする。このため、各クラスタは飛行体局によって他のクラスタとのリンクの接続を確実行うことが可能となる効果がある。
【0119】
実施の形態8.
実施の形態6では、地上レイヤメッシュの面に対して垂直方向に高さHを有して、地上レイヤメッシュの面に平行に航空レイヤメッシュの面を配置した。この実施の形態7では、地上レイヤメッシュの面と同一平面状に航空レイヤメッシュの面を配置する例を説明する。
【0120】
図42は、この実施の形態の第1層目の地上レイヤメッシュ4gに対して、第1層目の地上レイヤメッシュ4gの面と同一平面上に第2層目の地上レイヤメッシュ40gを配置した例を示す図である。第2層目の地上レイヤメッシュ40gは、地上局の双対グラフメッシュ60g上にあって、地上局のネットワークモデル1000gを構成する。複数の双体グラフメッシュを図42のような配置にする運用例としては、部隊員が携帯する無線通信端末装置間の通信を、車両に搭載した無線通信端末装置により中継する場合がある。この運用例では、クラスタは大部隊を構成する複数の小部隊に相当し、広域に散らばって作業を行う小部隊のクラスタ間の通信を、車両に搭載した無線通信端末装置で中継するネットワーク経路情報を、実施の形態6の図27と同様の構成の経路設計装置により生成する。第1層目の地上レイヤメッシュには、部隊員が携帯する無線通信端末装置を地上局1gに配置して、第2層目の地上レイヤメッシュには、車両に搭載する無線通信端末装置を地上局102gに配置する。また、第1層目の地上レイヤメッシュの面に対して第2層目の地上レイヤメッシュの面を配置する場合、クラスタは第1層目の地上レイヤメッシュ上に配置され、第1層目の地上レイヤメッシュ上の複数のクラスタから1つのクラスタを選択する。そして、選択したクラスタが含む複数の部隊員がそれぞれ携帯する無線通信端末装置のうち1つの無線通信端末装置の位置を、第1層目の地上レイヤメッシュの面から第1層目の地上レイヤメッシュの面に対して水平に移動させた方向に第2層目の地上レイヤメッシュの原点を配置する。また、第1層目の経路情報と、第2層目の経路情報を融合する場合、第1層目の無線通信装置と第2層目の無線通信装置とは、実施の形態6のように高さHを有さない同一面上でのリンクを接続する。
【0121】
このように、実施の形態8では、第1層目のグラフと第2層目のグラフとを同一面上に配置するので、異なる通信可能範囲を有する無線通信端末装置ではあるが、「緯度,経度,高さ」の「高さ」が同じである無線通信端末装置を複数の層に分けて、層ごとの経路情報を生成して、層ごとの経路情報を融合して、通信可能範囲が狭い無線通信端末間のリンクを、通信可能範囲の広い無線通信端末装置で中継するためのネットワーク経路情報を生成できる効果がある。
【0122】
実施の形態9.
この実施の形態では、通信範囲情報を時刻に対応させる経路設計装置、経路設計方法の一例を説明する。
【0123】
位置情報入力部51は、ネットワークモデルを構成する通信装置(ノード)が自己の位置情報を算出した際の時刻を示す時刻情報を位置情報に含めて発信した位置情報を受信する。或いは、位置情報に含まれる時刻情報は、例えば自己の位置を算出する際に使用する衛星から発信される測位信号に含まれる測位時刻情報でもかまわない。通信範囲情報記憶部55は、第1の通信可能範囲を時刻に対応させて記憶する通信範囲情報を記憶する。また、地上レイヤ斜向座標生成部57gは、位置情報の有する時刻情報を入力して、時刻情報に対応する通信可能範囲を通信範囲情報記憶部55から取得して、取得した時刻情報に対応する通信可能範囲の斜向座標グラフを生成する。なお、位置情報入力部51は複数のノードから異なる時刻情報を有する位置情報を入力し、時刻情報に対応する通信可能範囲は同じ場合と異なる場合とがある。通信可能範囲が異なる場合には、例えば、通信可能範囲の平均値を算出して、平均値を斜向座標グラフの生成に使用する。経路設計装置50の他の要素は、上記実施の形態6と同様であるものとする。
【0124】
以上のように、第1の通信可能範囲を時刻に対応させることにより、ネットワークモデルの通信経路を設計する際の時刻における通信環境に合ったネットワーク経路を設計することができる。
【0125】
実施の形態10.
実施の形態6では、図26に示すように正六角形を使用して、第1及び第2のグラフを斜向座標グラフとして生成した。しかし、四角形を使用して、第1及び第2のグラフを生成しても構わない。この場合、第1及び第2のグラフは、y軸がx軸に対して直角になる。実施の形態1〜9の斜向座標グラフは、y軸がx軸に対して直角になるグラフを斜向座標グラフに含めるものとする。
【0126】
このように、実施の形態10では、第1及び第2のグラフは、六角形或いは四角形を使用して生成することができるので、経路設計者が六角形と四角形とのいずれか一方を選択して、ネットワーク経路情報を生成できる効果がある。
【0127】
実施の形態11.
実施の形態6では、地上レイヤと航空レイヤの2層のネットワークモデルを1つのネットワークモデルに融合する例を説明した。しかし、地上レイヤと航空レイヤの他に、水上レイヤであったり、衛星レイヤであっても、複数の層を構成すれば構わない。また、複数の層にそれぞれ配置される1つの局(ノード)は2つのリンクで接続して、一方のリンクに障害が発生した場合であっても、他方のリンクを使用することによって通信が可能になるネットワーク経路設計情報を生成する。図44は、2層によるネットワークモデルの経路を説明する図である。このように、従来では、2層のネットワークモデルであっても、航空レイヤでは、飛行体局間は1つのリンクで接続されているので、障害が発生すると通信が行えなくなるという問題がある。実施の形態6では、このような問題点を解決しているが、クラスタ間の通信を中継する中継用の無線通信端末装置を配置する層が、例えば、航空レイヤメッシュであったり、水上レイヤメッシュであったり、衛星レイヤメッシュであると、無線通信端末装置を搭載する機器のコストがかかる。このため、障害時の通信経路の確保よりも、コストを優先するような場合には、中継用の無線通信端末装置を配置する層では、無線通信端末装置間のリンクを1つにしても構わない。
【図面の簡単な説明】
【0128】
【図1】(a)は、この発明のアドホックネットワークのモデルを示し、(b)はネットワーク設計方法の概要を示す図である。
【図2】(a)〜(c)は、特開2002−335192等に示された、従来の有線通信経路の二重化により、サバイバビリティ(障害発生時にもサービスを提供する機能)を確保する方法を示す模式図である。
【図3】実施の形態1の経路設計装置を構成する要素の一例を示すブロック図である。
【図4】実施の形態1の通信範囲情報記憶部55が記憶する通信範囲情報の一例を示す図である。
【図5】実施の形態1における経路設計装置の外観を示す図である。
【図6】実施の形態1における経路設計装置のハードウェア構成図である。
【図7】実施の形態1のフレームワーク処理部による斜向座標グラフ上に通信装置の位置を配置する処理のフローチャート図である。
【図8】実施の形態1の囲い込み処理部によるネットワークの経路設計情報を生成して出力する処理のフローチャート図である。
【図9】斜向座標グラフの一例を示す図である。
【図10】ノードから電波の到達する通信可能範囲5を球で示す図である。
【図11】円を多角形、例えば六角形に置き換え、通信可能範囲5を1/2に縮退させてネットワークモデルを六角形方眼で示した図である。
【図12】多角形方眼の一例を示す図であり、(a)は六角形、(b)は四角形、(c)は三角形の方眼を示す。
【図13】図12(a)、(b)、(c)のそれぞれの多角形方眼に対応する双対グラフメッシュを示す図であり、(a)は三角メッシュ、(b)は四角メッシュ、(c)は六角メッシュの方眼を示す。
【図14】(a),(b)は囲い込み(Enclosure)アルゴリズムの実行状況の経過を説明する図である。
【図15】(a),(b)、(c)は囲い込み(Enclosure)アルゴリズムの実行状況の経過を説明する図である。
【図16】(a),(b)、(c)は縮退規則情報に従う詳しい周囲境界線の縮退方法を説明する図である。
【図17】(a),(b)は実施の形態1の経路設計装置50による経路設計の利用形態を示す図である。
【図18】実施の形態2の経路設計装置を構成する要素の一例を示すブロック図である。
【図19】実施の形態2の通信範囲情報記憶部55が記憶する通信範囲情報の一例を示す図である。
【図20】実施の形態3の経路設計装置を構成する要素の一例を示すブロック図である。
【図21】実施の形態3の通信範囲情報記憶部55が記憶する通信範囲情報の一例を示す図である。
【図22】実施の形態4の経路設計装置を構成する要素の一例を示すブロック図である。
【図23】実施の形態4の通信範囲情報記憶部55が記憶する通信範囲情報の一例を示す図である。
【図24】実施の形態5の経路設計装置を構成する要素の一例を示すブロック図である。
【図25】実施の形態6のアドホックネットワークの2層構造のモデルを示す図である。
【図26】実施の形態6のネットワーク設計方法に使用する2層構造のネットワークモデルを示す図である。
【図27】実施の形態6の経路設計装置を構成する要素の一例を示すブロック図である。
【図28】(a)は、実施の形態6の地上レイヤ配置処理部が地上レイヤ斜向座標グラフ上に地上局を配置した例を示す図である。(b)は、クラスタ生成部が地上レイヤ斜向座標グラフ上の地上局を複数のクラスタに分類して、クラスタ毎の周囲境界線を生成した例を示す図ある。
【図29】実施の形態6の地上レイヤ斜向座標グラフに対して航空レイヤ斜向座標グラフを配置した例を示す図である。
【図30】実施の形態6の地上レイヤ斜向座標グラフ上のクラスタ毎の周囲境界線を航空レイヤ斜向座標グラフ上に投射した例を示す図である。
【図31】(a)は、航空レイヤ斜向座標グラフ上にクラスタ毎に対応する飛行体局を配置した例を示す図である。(b)は、地上レイヤ斜向座標グラフ上の仮想ノードを配置した縮退周囲境界線の例を示す図である。
【図32】実施の形態6の航空レイヤ斜向座標グラフ上の仮想ノードを配置した縮退周囲境界線の例を示す図である。
【図33】実施の形態6の経路設計装置の処理の手順を示すフローチャート図である。
【図34】図33のS5g、S5aの囲い込み処理の詳細な手順を示すフローチャート図である。
【図35】実施の形態6のマルチホップについて説明する図である。
【図36】(a)は、ホップ数を1とした場合の地上局それぞれのノード範囲(エリア)を示す図である。(b)は、ホップ数を2とした場合の地上局それぞれのノード範囲(エリア)を示す図である。
【図37】実施の形態6のクラスタ生成部58によるクラスタ生成処理S4gを示すフローチャート図である。
【図38】実施の形態7の航空レイヤメッシュ上に投射したクラスタの取り囲む範囲内に頂点が存在しない例を示す図である。
【図39】実施の形態7の経路設計装置の構成を示すブロック図である。
【図40】実施の形態7の調整部591の動作手順を示すフローチャート図である。
【図41】実施の形態7の調整部591の別の動作手順を示すフローチャート図である。
【図42】この実施の形態8の第1層目の双体グラフメッシュ60gに対して、第1層目の双体グラフメッシュ60gの面と同一平面上に第2層目の双体グラフメッシュ60aを配置した例を示す図である。
【図43】実施の形態6のノードの位置情報から座標点を求める一例を説明する図である。
【図44】2層によるネットワークモデルの経路を説明する図である。
【符号の説明】
【0129】
1,1S,1D,40 ノード、1R,1Ra,1Rg 中継ノード、1a 飛行体局、1C,1g,100g 地上局、1NB1,1NB2,1NB3 隣接ノード範囲、1V,1Va,1Vg 仮想ノード、1W 和集合、2,2a,2g リンク、3a,3b,3c,3d,31,32,33 経路、3B 周囲境界線、3Ba 航空レイヤの周囲境界線、3Bg 地上レイヤの周囲境界線、3Ha 飛行体局間経路、3Hg 地上局間経路、4 六角形方眼、4a 航空レイヤメッシュ、4g,40g 地上レイヤメッシュ、5,5aL 通信可能範囲、5aR 地上局1gからなるネットワーク層への投射、6 双対グラフメッシュ、6a 飛行体局の双対グラフメッシュ、6g,60g 地上局の双対グラフメッシュ、7 斜向座標、7a 航空レイヤメッシュ、7g 地上レイヤメッシュ、10 ネットワークモデル、10a 飛行体局のネットワークモデル、10g,1000g 地上局のネットワークモデル、21 クラスタ、21c 中心点、50 経路設計装置、51 位置情報入力部、53 フレームワーク処理部、55 通信範囲情報記憶部、57 斜向座標生成部、57a 航空レイヤ斜向座標生成部、57g 地上レイヤ斜向座標生成部、59 配置処理部、59a 航空レイヤ配置処理部、59g 地上レイヤ配置処理部、60,61,62 位置情報、70 囲い込み処理部、73 周囲境界縮小部、75 縮退規則情報記憶部、77 境界縮退部、78 経路情報融合部、79 経路設計部、80,80P,80T 経路情報、91 電波強度測定部、93 アンテナ、94 受信位置算出部、95 測位受信部、97 位置算出部、100a 航空レイヤ斜向座標グラフの原点、101a 座標点、102g 地上局、137 CPU、138 バス、139 ROM、140 RAM、141 CRT表示装置、142 K/B、143 マウス、144 通信ボード、145 FDD、146 磁気ディスク装置、147 OS、148 ウィンドウシステム、149 プログラム群、150 ファイル群、186 CDD、187 プリンタ装置、188 スキャナ装置、200 システムユニット、201 衛星群、202 静止衛星、203 GPS衛星、204 準天頂衛星、310 FAX機、320 電話器、500 ウェブサーバ、501 インターネット、505 LAN、581 マルチホップ隣接ノードエリア生成部、582 エリア和集合生成部、591 調整部。

【特許請求の範囲】
【請求項1】
第1の無線通信装置と第2の無線通信装置との間のネットワーク経路を設計する経路設計装置において、
上記第1の無線通信装置と上記第2の無線通信装置の通信可能範囲を示す通信範囲情報を記憶する通信範囲情報記憶部と、
上記第1の無線通信装置の位置を示す第1の位置情報と上記第2の無線通信装置の位置を示す第2の位置情報とを入力する位置情報入力部と、
上記通信範囲情報記憶部が記憶する通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する斜向座標生成部と、
上記位置情報入力部が入力した第1の位置情報と上記第2の位置情報とのそれぞれに対応する上記斜向座標生成部が生成した斜向座標グラフ上の第1の座標点と第2の座標点とを求めて、求めた上記第1の座標点と第2の座標点とを上記斜向座標グラフ上に配置するとともに、配置した第1の座標点と第2の座標点とを囲い込む周囲境界線を上記斜向座標グラフ上に生成する配置処理部と、
上記配置処理部が斜向座標グラフ上に生成した周囲境界線を周囲境界線の内側に移動して上記第1の座標点と第2の座標点とを囲い込む範囲を縮小した縮小周囲境界線を上記斜向座標グラフ上に生成する周囲境界縮小部と、
周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を記憶する縮退規則情報記憶部と、
上記縮退規則情報記憶部が記憶する縮退規則情報に従い、上記周囲境界縮小部が上記斜向座標グラフ上に生成した縮小周囲境界線の内側に上記仮想通信装置を配置して配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記斜向座標グラフ上に生成する境界縮退部と、
上記境界縮退部が上記斜向座標グラフ上に生成した縮退周囲境界線と、上記第1の座標点と上記第2の座標点と、上記境界縮退部が配置した仮想通信装置の斜向座標グラフ上の位置とから上記ネットワーク経路を設計して経路設計情報を生成して出力する経路設計部と
を備えたことを特徴とする経路設計装置。
【請求項2】
自己と他の無線通信装置との間のネットワーク経路を設計する経路設計装置において、
自己と上記他の無線通信装置の通信可能範囲を示す通信範囲情報を記憶する通信範囲情報記憶部と、
測位信号情報を受信して自己の位置を示す第1の位置情報を算出する受信位置算出部と、
上記他の無線通信装置の位置を示す第2の位置情報を入力する位置情報入力部と、
上記通信範囲情報記憶部が記憶する通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する斜向座標生成部と、
上記受信位置算出部が算出した第1の位置情報と上記位置情報入力部が入力した第2の位置情報とのそれぞれに対応する上記斜向座標生成部が生成した斜向座標グラフ上の第1の座標点と第2の座標点とを求めて、求めた上記第1の座標点と第2の座標点とを上記斜向座標グラフ上に配置するとともに、配置した第1の座標点と第2の座標点とを囲い込む周囲境界線を上記斜向座標グラフ上に生成する配置処理部と、
上記配置処理部が斜向座標グラフ上に生成した周囲境界線を周囲境界線の内側に移動して、上記第1の座標点と第2の座標点とを囲い込む範囲を縮小した縮小周囲境界線を上記斜向座標グラフ上に生成する周囲境界縮小部と、
周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を記憶する縮退規則情報記憶部と、
上記縮退規則情報記憶部が記憶する縮退規則情報に従い、上記周囲境界縮小部が上記斜向座標グラフ上に生成した縮小周囲境界線の内側に上記仮想通信装置を配置して配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記斜向座標グラフ上に生成する境界縮退部と、
上記境界縮退部が上記斜向座標グラフ上に生成した縮退周囲境界線と、上記第1の座標点と上記第2の座標点と、上記境界縮退部が配置した仮想通信装置の斜向座標グラフ上の位置とから上記ネットワーク経路を設計して経路設計情報を生成して出力する経路設計部と
を備えたことを特徴とする経路設計装置。
【請求項3】
上記縮小周囲境界線は、複数の辺を有し、
上記周囲境界縮小部は、上記第1の座標点と第2の座標点との少なくともいずれか一方の座標点が上記縮小周囲境界線上に配置されるように上記縮小周囲境界線を生成し、
上記縮退規則情報記憶部は、上記縮退規則情報として、上記縮小周囲境界線の複数の辺のうち上記第1の座標点と第2の座標点とが配置されている辺については上記縮小周囲境界線を縮退しないことを示す情報と、上記縮小周囲境界線の複数の辺のうち上記第1の座標点と第2の座標点とのいずれか一方の座標点が配置されている辺については辺上の座標点の内側に2つの仮想通信装置を配置して、配置した2つの仮想通信装置と上記辺上の座標点とを結ぶ縮退周囲境界線を生成することを示す情報とを記憶することを特徴とする請求項1または2記載の経路設計装置。
【請求項4】
上記斜向座標グラフは、三角メッシュと四角メッシュと六角メッシュとのいずれかに対応する斜向座標のグラフであることを特徴とする請求項1または2記載の経路設計装置。
【請求項5】
上記第1の位置情報と第2の位置情報とはそれぞれ、所定の電波強度を有する電波信号であり、
上記位置情報入力部は、上記第1の位置情報と第2の位置情報の少なくともいずれか一方の電波信号の強度を測定する電波強度測定部を備え、
上記通信範囲情報記憶部は、上記通信範囲情報を電波強度に対応させて記憶し、
上記斜向座標生成部は、上記電波強度測定部が測定した電波信号の強度に対応する通信範囲情報を上記通信範囲情報記憶部から取得し、取得した通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する
ことを特徴とする請求項1記載の経路設計装置。
【請求項6】
上記第1の位置情報と第2の位置情報との少なくともいずれか一方は、位置情報を出力した無線通信装置の種類情報を有し、
上記通信範囲情報記憶部は、上記通信範囲情報を無線通信装置の種類情報に対応させて記憶し、
上記斜向座標生成部は、上記第1の位置情報と第2の位置情報との少なくともいずれか一方の位置情報の有する種類情報に対応する通信範囲情報を上記通信範囲情報記憶部から取得し、取得した通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する
ことを特徴とする請求項1記載の経路設計装置。
【請求項7】
上記第1の位置情報と第2の位置情報との少なくともいずれか一方は、時刻を示す時刻情報を有し、
上記通信範囲情報記憶部は、上記通信範囲情報を時刻情報に対応させて記憶し、
上記斜向座標生成部は、上記第1の位置情報と第2の位置情報との少なくともいずれか一方の位置情報の有する時刻情報に対応する通信範囲情報を上記通信範囲情報記憶部から取得し、取得した通信範囲情報の示す通信可能範囲を一目盛とする斜向座標グラフを生成する
ことを特徴とする請求項1記載の経路設計装置。
【請求項8】
第1の無線通信装置と第2の無線通信装置との間のネットワーク経路を設計する経路設計方法において、
上記第1の無線通信装置と上記第2の無線通信装置の通信可能範囲を示す通信範囲情報を通信範囲情報記憶部に記憶する通信範囲情報記憶工程と、
上記第1の無線通信装置の位置を示す第1の位置情報と上記第2の無線通信装置の位置を示す第2の位置情報とを入力する位置情報入力工程と、
上記通信範囲情報記憶工程により記憶された通信範囲情報を上記通信範囲情報記憶部から取り出し、取り出した通信可能範囲を一目盛とする斜向座標グラフを生成する斜向座標生成工程と、
上記位置情報入力工程により入力された第1の位置情報と上記第2の位置情報とのそれぞれに対応する上記斜向座標生成工程により生成された斜向座標グラフ上の第1の座標点と第2の座標点とを求めて、求めた上記第1の座標点と第2の座標点とを上記斜向座標グラフ上に配置するとともに、配置した第1の座標点と第2の座標点とを囲い込む周囲境界線を上記斜向座標グラフ上に生成する配置処理工程と、
上記配置処理工程により斜向座標グラフ上に生成された周囲境界線を周囲境界線の内側に移動して、上記第1の座標点と第2の座標点とを囲い込む範囲を縮小した縮小周囲境界線を上記斜向座標グラフ上に生成する周囲境界縮小工程と、
周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を縮退規則情報記憶部に記憶する縮退規則情報記憶工程と、
上記縮退規則情報記憶工程により記憶された縮退規則情報を上記縮退規則情報記憶部から取得し、取得した縮退規則情報に従い上記周囲境界縮小工程により上記斜向座標グラフ上に生成された縮小周囲境界線の内側に上記仮想通信装置を配置して配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記斜向座標グラフ上に生成する境界縮退工程と、
上記境界縮退工程により上記斜向座標グラフ上に生成された縮退周囲境界線と、上記第1の座標点と、上記第2の座標点と、上記境界縮退工程により配置された仮想通信装置の上記斜向座標グラフ上の位置とから上記ネットワーク経路を設計して経路設計情報を生成して出力する経路設計工程と
を有することを特徴とする経路設計方法。
【請求項9】
第1の通信可能範囲をそれぞれ有する複数の無線通信装置間の接続を上記第1の通信可能範囲とは異なる第2の通信可能範囲を有する1つ以上の無線通信装置を介して行うネットワーク経路を設定する経路設計装置において、
上記第1の無線可能範囲を示す第1の通信範囲情報と、上記第2の無線可能範囲を示す第2の通信範囲情報とを記憶する通信範囲情報記憶部と、
上記第1の通信可能範囲をそれぞれ有する複数の無線通信装置から、各無線通信装置の位置を示す緯度情報と経度情報とを有する位置情報を入力する位置情報入力部と、
上記通信範囲情報記憶部が記憶する第1の通信範囲情報の示す通信可能範囲を多角形で表し、多角形の辺を共有させて多角形を隣接させて複数配置し、配置した複数の多角形の中心点同士を上記共有する辺を通過する線で結んで、上記複数の多角形の中心点ごとに中心点を通過する上記線を複数生成して、上記複数の多角形の中心点うち1つの中心点をグラフの原点として選択するとともに、選択した原点を通過する複数の線のうちx軸とする線とy軸とする線とをそれぞれ選択して、x軸に経度を距離に変換した値を示し、y軸に緯度を距離に変換した値を示した第1のグラフを生成する第1のグラフ生成部と、
上記通信範囲情報記憶部が記憶する第2の通信範囲情報の示す通信可能範囲を多角形で表し、多角形の辺を共有させて多角形を隣接させて複数配置し、配置した複数の多角形の中心点同士を上記共有する辺を通過する線で結んで、上記複数の多角形の中心点ごとに中心点を通過する上記線を複数生成して、上記複数の多角形の中心点うち1つの中心点をグラフの原点として選択するとともに、選択した原点を通過する複数の線のうちx軸とする線とy軸とする線とをそれぞれ選択して、x軸に経度を距離に変換した値を示し、y軸に緯度を距離に変換した値を示した第2のグラフを生成する第2のグラフ生成部と、
上記位置情報入力部が入力した複数の無線通信装置の各無線通信装置の位置情報に基づいて複数の無線通信装置毎の経度情報を距離に変換した値と緯度情報を距離に変換した値とを求め、求めた複数の無線通信装置毎の値から複数の無線通信装置毎の上記第1のグラフ上の各座標点を求めて、求めた各座標点を上記第1のグラフ上に配置する第1の配置処理部と、
上記第1の配置処理部が配置した第1のグラフ上の複数の座標点を所定の条件に基づいて分類して複数の座標点を含むクラスタを複数生成して、生成した複数のクラスタに含まれる複数の座標点を囲い込む周囲境界線を上記第1のグラフ上に生成するクラスタ生成部と、
上記クラスタ生成部が第1のグラフ上に生成した周囲境界線と第1のグラフと、上記第2のグラフ生成部が生成した第2のグラフとを入力して、入力した第1のグラフ上の複数のクラスタのうち1つのクラスタを選択して、選択したクラスタの周囲境界線の取り囲む範囲内に第2のグラフ上の原点が配置されるように上記第1のグラフに対して第2のグラフを配置して、配置した第2のグラフ上に上記選択したクラスタ以外の他のクラスタの周囲境界線を投射して、投射した各クラスタ毎に周囲境界線の取り囲む範囲に近い上記第2のグラフ上の多角形の中心点を各クラスタ毎に対応させ、各クラスタ毎に対応させた多角形の中心点と上記原点の座標点とを各クラスタに対応する上記第2の通信可能範囲を有する無線通信装置を配置する座標点として、これらの座標点を囲い込む周囲境界線を上記第2のグラフ上に生成する第2の配置処理部と、
上記クラスタ生成部が第1のグラフ上に生成したクラスタ毎の周囲境界線を周囲境界線の内側に移動して周囲境界線が囲い込む範囲を縮小したクラスタ毎の縮小周囲境界線を生成するとともに、上記第2の配置処理部が第2のグラフ上に生成した周囲境界線を周囲境界線の内側に移動して周囲境界線が囲い込む範囲を縮小した第2のグラフ上の縮小周囲境界線を生成する周囲境界縮小部と、
クラスタ毎の縮小周囲境界線と第2のグラフ上の縮小周囲境界線とのそれぞれの縮小周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を記憶する縮退規則情報記憶部と、
上記縮退規則情報記憶部が記憶した縮退規則情報に従い、上記周囲境界縮小部が生成した第1のグラフ上のクラスタ毎の縮小周囲境界線の内側に仮想通信装置を配置して、配置した仮想通信装置を通過するようにクラスタ毎の縮小周囲境界線を縮退してクラスタ毎の縮退周囲境界線を上記第1のグラフ上に生成するとともに、上記縮退規則情報記憶部が記憶した縮退規則情報に従い、上記周囲境界縮小部が生成した第2のグラフ上の縮小周囲境界線の内側に仮想通信装置を配置して、配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記第2のグラフ上に生成する境界縮退部と、
上記境界縮退部が上記第1のグラフ上に生成したクラスタ毎の縮退周囲境界線と、各クラスタに含まれる複数の座標点と、上記境界縮退部が第1のグラフ上に配置した仮想通信装置の座標点とを有するクラスタ毎の経路設計情報を生成するとともに、上記境界縮退部が上記第2のグラフ上に生成した縮退周囲境界線と、上記第2の配置処理部が決定したクラスタ毎の第2の通信可能範囲を有する無線通信装置を配置する座標点と、上記境界縮退部が第2のグラフ上に配置した仮想通信装置の座標点とを有する第2の通信可能範囲を有する無線通信装置の経路設計情報を生成する第1の経路設計部と、
上記第1の経路設計部が生成したクラスタ毎の経路設計情報が有する各クラスタに含まれる複数の座標点のうち2つの座標点を選択して、選択した2つの座標点それぞれと、上記第1の経路設計部が生成した第2の通信可能範囲を有する無線通信装置の経路設計情報が有するクラスタ毎の第2の通信可能範囲を有する無線通信装置を配置する座標点とを接続する経路情報を、各クラスタ毎に生成して、生成した経路情報と、上記第1の経路設計部が生成したクラスタ毎の経路設計情報と、上記第1の経路設計部が生成した第2の通信可能範囲を有する無線通信装置の経路設計情報とに基づいて各クラスタ間を第2の通信可能範囲を有する無線通信装置を介して接続するネットワーク経路情報を生成して出力する第2の経路設計部と
を備えたことを特徴とする経路設計装置。
【請求項10】
上記第2の配置処理部は、上記第2のグラフの面を上記第1のグラフの面に対して垂直方向に所定の高さを有して平行に配置し、
上記第2の通信可能範囲を有する無線通信装置は、飛行体に搭載された通信局である
ことを特徴とする請求項9記載の経路設計装置。
【請求項11】
上記第2の配置処理部は、上記第1のグラフの面に対して上記第2のグラフの面を上記第2の通信可能範囲分の距離を有して同一平面上に配置し、
上記第2の通信可能範囲を有する無線通信装置は、地上局である
ことを特徴とする請求項9記載の経路設計装置。
【請求項12】
上記クラスタ生成部は、上記第1のグラフ上の複数の座標点を複数のクラスタに分類する条件として上記第1の通信可能範囲を1ホップとした場合のホップ数を記憶する分類条件記憶部と、
上記第1のグラフ上の複数の座標点毎に座標点を中心として中心から上記分類条件記憶部が記憶するホップ数の距離を有するエリアを上記第1のグラフ上に複数生成するエリア生成部と、
上記エリア生成部が生成した複数のエリアのうち隣接するエリアを同一のクラスタにして、上記第1の斜向グラフ上に生成した複数のエリアを複数のクラスタに分類するエリア分類部と
を備えることを特徴とする請求項9記載の経路設計装置。
【請求項13】
上記クラスタ毎の縮小周囲境界線と上記第2のグラフ上の縮小周囲境界線とはそれぞれ、複数の辺を有し、
上記周囲境界縮小部は、上記クラスタ毎の縮小周囲境界線を生成する場合は、クラスタ毎に各クラスタに含まれる複数の座標点のうち少なくとも1つの座標点が上記縮小周囲境界線上に配置されるように上記縮小周囲境界線を生成し、上記第2のグラフ上の縮小周囲境界線を生成する場合は、上記第2の通信可能範囲を有する無線通信装置を配置する複数の座標点のうち少なくとも1つの座標点が上記縮小周囲境界線上に配置されるように上記縮小周囲境界線を生成し、
上記縮退規則情報記憶部は、上記縮退規則情報として、上記縮小周囲境界線の複数の辺のうち上記第1の通信可能範囲を有する無線通信装置を配置する座標点が複数配置されている辺と、上記第2の通信可能範囲を有する無線通信装置を配置する座標点が複数配置されている辺については、上記縮小周囲境界線を縮退しないことを示す情報と、上記縮小周囲境界線の複数の辺のうち上記第1の通信可能範囲を有する無線通信装置を配置する座標点が1つ配置されている辺と、上記第2の通信可能範囲を有する無線通信装置を配置する座標点が1つ配置されている辺については、辺上の座標点の内側に2つの仮想通信装置を配置して、配置した2つの仮想通信装置と上記辺上の座標点とを結ぶ縮退周囲境界線を生成することを示す情報とを記憶することを特徴とする請求項9記載の経路設計装置。
【請求項14】
上記第1の通信範囲情報の示す通信可能範囲を表した多角形と、上記第2の通信範囲情報の示す通信可能範囲を表した多角形とは、六角形と四角形とのいずれかであることを特徴とする請求項9記載の経路設計装置。
【請求項15】
上記位置情報入力部が入力する各無線装置の位置情報のうち少なくとも1つの位置情報は、時刻を示す時刻情報を有し、
上記通信範囲情報記憶部は、上記第1の通信範囲情報を時刻情報に対応させて記憶し、
上記第1のグラフ生成部は、上記位置情報の有する時刻情報に対応する第1の通信範囲情報を上記通信範囲情報記憶部から取得し、取得した第1の通信範囲情報の示す通信可能範囲を一目盛とする第1のグラフを生成する
ことを特徴とする請求項9記載の経路設計装置。
【請求項16】
上記第2の配置処理部は、上記第2のグラフ上の複数の多角形の中心点ごとに各中心点を通過する複数の線が交差する点を頂点として、上記投射した周囲境界線の取り囲む範囲に上記第2のグラフ上の頂点が含まれないクラスタがある場合、上記投射したクラスタの周囲境界線の取り囲む範囲の中心点を求めて、求めた中心点に最も近い上記第2のグラフ上の多角形の中心点から上記投射したクラスタの周囲境界線の取り囲む範囲の中心点までの距離を、すべての投射したクラスタについて求め、求めた距離に基づいて全クラスタの平均を求め、求めた平均とクラスタ毎に求めた上記距離との差が一番大きいクラスタを選択して、選択したクラスタの周囲境界線の取り囲む範囲の中心点とその中心点に最も近い上記第2のグラフ上の多角形の中心点までの距離が上記平均に近くなるように上記第2のグラフの原点の上記第1のグラフに対する位置を移動して、選択したクラスタの周囲境界線の取り囲む範囲の中心点とその中心点に最も近い上記第2のグラフ上の多角形の中心点までの距離を調整する調整部を備える
ことを特徴とする請求項9記載の経路設計装置。
【請求項17】
第1の通信可能範囲をそれぞれ有する複数の無線通信装置間の接続を上記第1の通信可能範囲とは異なる第2の通信可能範囲を有する1つ以上の無線通信装置を介して行うネットワーク経路を設定する経路設計装置の経路設計方法において、
上記第1の無線可能範囲を示す第1の通信範囲情報と、上記第2の無線可能範囲を示す第2の通信範囲情報とを通信範囲情報記憶部に記憶する通信範囲情報記憶工程と、
上記第1の通信可能範囲をそれぞれ有する複数の無線通信装置から、各無線通信装置の位置を示す緯度情報と経度情報とを有する位置情報を入力する位置情報入力工程と、
上記通信範囲情報記憶工程により通信範囲情報記憶部に記憶した第1の通信範囲情報の示す通信可能範囲を多角形で表し、多角形の辺を共有させて多角形を隣接させて複数配置し、配置した複数の多角形の中心点同士を上記共有する辺を通過する線で結んで、上記複数の多角形の中心点ごとに中心点を通過する上記線を複数生成して、上記複数の多角形の中心点うち1つの中心点をグラフの原点として選択するとともに、選択した原点を通過する複数の線のうちx軸とする線とy軸とする線とをそれぞれ選択して、x軸に経度を距離に変換した値を示し、y軸に緯度を距離に変換した値を示した第1のグラフを生成する第1のグラフ生成工程と、
上記通信範囲情報記憶工程により通信範囲情報記憶部に記憶した第2の通信範囲情報の示す通信可能範囲を多角形で表し、多角形の辺を共有させて多角形を隣接させて複数配置し、配置した複数の多角形の中心点同士を上記共有する辺を通過する線で結んで、上記複数の多角形の中心点ごとに中心点を通過する上記線を複数生成して、上記複数の多角形の中心点うち1つの中心点をグラフの原点として選択するとともに、選択した原点を通過する複数の線のうちx軸とする線とy軸とする線とをそれぞれ選択して、x軸に経度を距離に変換した値を示し、y軸に緯度を距離に変換した値を示した第2のグラフを生成する第2のグラフ生成工程と、
上記位置情報入力工程により入力した複数の無線通信装置の各無線通信装置の位置情報に基づいて複数の無線通信装置毎の経度情報を距離に変換した値と緯度情報を距離に変換した値とを求め、求めた複数の無線通信装置毎の値から複数の無線通信装置毎の上記第1のグラフ上の各座標点を求めて、求めた各座標点を上記第1のグラフ上に配置する第1の配置処理工程と、
上記第1の配置処理工程により配置した第1のグラフ上の複数の座標点を所定の条件に基づいて分類して複数の座標点を含むクラスタを複数生成して、生成した複数のクラスタに含まれる複数の座標点を囲い込む周囲境界線を上記第1のグラフ上に生成するクラスタ生成工程と、
上記クラスタ生成工程により第1のグラフ上に生成した周囲境界線と第1のグラフと、上記第2のグラフ生成工程により生成した第2のグラフとを入力して、入力した第1のグラフ上の複数のクラスタのうち1つのクラスタを選択して、選択したクラスタの周囲境界線の取り囲む範囲内に第2のグラフ上の原点が配置されるように上記第1のグラフに対して第2のグラフを配置して、配置した第2のグラフ上に上記選択したクラスタ以外の他のクラスタの周囲境界線を投射して、投射した各クラスタ毎に周囲境界線の取り囲む範囲に近い上記第2のグラフ上の多角形の中心点を各クラスタ毎に対応させ、各クラスタ毎に対応させた多角形の中心点と上記原点の座標点とを各クラスタに対応する上記第2の通信可能範囲を有する無線通信装置を配置する座標点として、これらの座標点を囲い込む周囲境界線を上記第2のグラフ上に生成する第2の配置処理工程と、
上記クラスタ生成工程により第1のグラフ上に生成したクラスタ毎の周囲境界線を周囲境界線の内側に移動して周囲境界線が囲い込む範囲を縮小したクラスタ毎の縮小周囲境界線を生成するとともに、上記第2の配置処理工程により第2のグラフ上に生成した周囲境界線を周囲境界線の内側に移動して周囲境界線が囲い込む範囲を縮小した第2のグラフ上の縮小周囲境界線を生成する周囲境界縮小工程と、
クラスタ毎の縮小周囲境界線と第2のグラフ上の縮小周囲境界線とのそれぞれの縮小周囲境界線の内側に仮想通信装置を配置して周囲境界線を縮退させる縮退規則情報を縮退規則情報記憶部に記憶する縮退規則情報記憶工程と、
上記縮退規則情報記憶工程により縮退規則情報記憶部が記憶した縮退規則情報に従い、上記周囲境界縮小工程により生成した第1のグラフ上のクラスタ毎の縮小周囲境界線の内側に仮想通信装置を配置して、配置した仮想通信装置を通過するようにクラスタ毎の縮小周囲境界線を縮退してクラスタ毎の縮退周囲境界線を上記第1のグラフ上に生成するとともに、上記縮退規則情報記憶工程により縮退規則情報記憶部に記憶した縮退規則情報に従い、上記周囲境界縮小工程により生成した第2のグラフ上の縮小周囲境界線の内側に仮想通信装置を配置して、配置した仮想通信装置を通過するように縮小周囲境界線を縮退して縮退周囲境界線を上記第2のグラフ上に生成する境界縮退工程と、
上記境界縮退工程により上記第1のグラフ上に生成したクラスタ毎の縮退周囲境界線と、各クラスタに含まれる複数の座標点と、上記境界縮退工程により第1のグラフ上に配置した仮想通信装置の座標点とを有するクラスタ毎の経路設計情報を生成するとともに、上記境界縮退工程により上記第2のグラフ上に生成した縮退周囲境界線と、上記第2の配置処理工程により決定したクラスタ毎の第2の通信可能範囲を有する無線通信装置を配置する座標点と、上記境界縮退工程により第2のグラフ上に配置した仮想通信装置の座標点とを有する第2の通信可能範囲を有する無線通信装置の経路設計情報を生成する第1の経路設計工程と、
上記第1の経路設計工程により生成したクラスタ毎の経路設計情報が有する各クラスタに含まれる複数の座標点のうち2つの座標点を選択して、選択した2つの座標点それぞれと、上記第1の経路設計工程により生成した第2の通信可能範囲を有する無線通信装置の経路設計情報が有するクラスタ毎の第2の通信可能範囲を有する無線通信装置を配置する座標点とを接続する経路情報を、各クラスタ毎に生成して、生成した経路情報と、上記第1の経路設計工程により生成したクラスタ毎の経路設計情報と、上記第1の経路設計工程により生成した第2の通信可能範囲を有する無線通信装置の経路設計情報とに基づいて各クラスタ間を第2の通信可能範囲を有する無線通信装置を介して接続するネットワーク経路情報を生成して出力する第2の経路設計工程と
を有することを特徴とする経路設計方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate

【図34】
image rotate

【図35】
image rotate

【図36】
image rotate

【図37】
image rotate

【図38】
image rotate

【図39】
image rotate

【図40】
image rotate

【図41】
image rotate

【図42】
image rotate

【図43】
image rotate

【図44】
image rotate


【公開番号】特開2006−101497(P2006−101497A)
【公開日】平成18年4月13日(2006.4.13)
【国際特許分類】
【出願番号】特願2005−245965(P2005−245965)
【出願日】平成17年8月26日(2005.8.26)
【出願人】(000006013)三菱電機株式会社 (33,312)
【Fターム(参考)】