(57)【要約】【課題】他のノードからより少ないトラフィックによって周辺ノード情報を得る。【解決手段】取得した周辺ノード情報に含まれる自身の位置や、周辺ノードの識別情報および地理情報を参考にして、各ノードＸ，Ａ，Ｂ，Ｃ，Ｄがネットワーク上でのルートを自律的に決定する。特に各ノードＸ，Ａ，Ｂ，Ｃ，Ｄは、周辺ノードを検索する際に、自ノードが知っている周辺ノード情報を送るか送らないかの判断を行なってから、必要に応じて周辺ノード情報を送る。これにより、より少ないトラフィックによって他のノードから周辺ノード情報を得ることができる。【選択図】　　図１
2004032559.tif 000002
【特許請求の範囲】
【請求項１】
ノード固有の識別情報とノードの位置や移動速度を特定する地理情報とからなる周辺ノード情報を、無線レンジ内にある周辺ノードと交換し、前記周辺ノード情報を得たら、この周辺ノード情報から情報元にパケットを送るアドホックネットワークのルーティング方法において、
前記各ノードは周辺ノードのそれぞれに対して、自ノードが知っている周辺ノード情報を送るか送らないかの判断を行なうことを特徴とするアドホックネットワークのルーティング方法。
【請求項２】
前記判断は、自ノードの無線レンジと、送る相手ノードの無線レンジと、この相手ノードの無線レンジ内にある周辺ノードの位置とを利用して行なわれることを特徴とする請求項１記載のアドホックネットワークのルーティング方法。
【請求項３】
前記自ノードが知っている周辺ノード情報を、自ノードの移動速度と、予め得ている周辺ノードの移動速度とを用いて補正することを特徴とする請求項１または２記載のアドホックネットワークのルーティング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数の移動体無線端末どうしが互いに通信を行なうアドホックネットワークにおいて、最適なルーティング（経路選択）を確立するためのアドホックネットワークのルーティング方法に関する。
【０００２】
【発明が解決しようとする課題】
無線通信において、固定した基地局を用いずに適宜マルチホップ伝送を行なうアドホックネットワークが注目されている。アドホックネットワークにおいては、移動体端末（以下、ノードという）が自由に移動して、ノード間のリンク状態の変化が頻繁に発生するために、ネットワークトポロジーの変化が激しい。そのため、こうしたトポロジー変化が激しいネットワークでは、ノード情報を把握するためのパケット送信によるプロトコルオーバーヘッド増加により、周辺ノードの状況を把握するのに時間がかかり、その間に各ノードが保持しているルーティング情報から頻繁に対象ノードが消失するなどの問題がある。
【０００３】
従来の技術として、インターネットにおけるルーティング手法をアドホックネットワークに応用した例では、Ｏｎ−Ｄｅｍａｎｄ型と呼ばれる例えばＩｎｔｅｒｎａｔｉｏｎａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｔａｓｋ　Ｆｏｒｃｅ　（ＩＥＴＦ）　Ｍｏｂｉｌｅ　Ａｄ　Ｈｏｃ　Ｎｅｔｗｏｒｋｉｎｇ　Ｗｏｒｋｉｎｇ　Ｇｒｏｕｐ，　ＩＮＴＥＲＮＥＴ　ＤＲＡＦＴの２００２年１月１９日に刊行された”Ａｄ　ｈｏｃ　Ｏｎ−Ｄｅｍａｎｄ　Ｄｉｓｔａｎｃｅ　Ｖｅｃｔｏｒ（ＡＯＤＶ）　Ｒｏｕｔｉｎｇ”や、２００２年２月２１日に刊行された”Ｔｈｅ　Ｄｙｎａｍｉｃ　Ｓｏｕｒｃｅ　Ｒｏｕｔｉｎｇ（ＤＳＲ）　Ｐｒｏｔｏｃｏｌ　ｆｏｒ　Ｍｏｂｉｌｅ　Ａｄ　Ｈｏｃ　Ｎｅｔｗｏｒｋｓ”に記載されたルーティングプロトコルや、Ｐｒｏ−Ａｃｔｉｖｅ型と呼ばれる”Ｆｉｓｈｅｙｅ　Ｓｔａｔｅ　Ｒｏｕｔｉｎｇ　Ｐｒｏｔｏｃｏｌ　（ＦＳＲ）　ｆｏｒ　Ａｄ　Ｈｏｃ　Ｎｅｔｗｏｒｋｓ”に記載されたルーティングプロトコルが知られている。
【０００４】
上記従来技術において、Ｏｎ−Ｄｅｍａｎｄ型のルーティングプロトコルは、通信の要求が発生してから経路探索を行なうもので、その手法をまとめると以下のようになる。
【０００５】
（１）全てのノードに送信を行なうフラッデイング（Ｆｌｏｏｄｉｎｇ）によって、周辺ノードのネットワークＩＤ（識別子）を把握する。
【０００６】
（２）最終通信対象となり得るノードまでのルーティングパスを、フラッデイングにより中間のノードを経由してパス確立の要求を伝える。目的のノードがその要求を受取ると、逆のパスを通って元のソースノードにルーティングパスを返す。
【０００７】
しかしながら、実際のアドホックネットワークはネットワークトポロジーが頻繁に変化することから、Ｏｎ−Ｄｅｍａｎｄ型のルーティングプロトコルでは、ルーティングパス上から消えたノードの削除情報を送るなどの工夫がなされている。また、上記Ｐｒｏ−Ａｃｔｉｖｅ型のルーティングプロトコルも、周辺ノードとルーティングテーブル（情報）を交換して行くことにより、周辺ノードのネットワークＩＤとリンク情報を得るようにしている。しかし、これらの従来技術に基づくルーティングプロトコルの手法では、ネットワークトポロジーが頻繁に変化する環境下で、次のような問題が発生する。
【０００８】
（１）周辺ノード情報の頻繁なリフレッシュが必要であり、ノード間の通信トラフィックが増加する。
【０００９】
（２）各ノードは周辺ノードからのルーティング情報を得てからでないと、目的のノード先にパケットを送ることができないので、パケットを送るまでにネットワークトポロジーが変化してしまう可能性がある。
【００１０】
そこで、ルーティングを行なうに際して、各ノードの位置や速度などの地理情報を利用したいわゆるＧｅｏｇｒａｐｈｉｃ　Ｒｏｕｔｉｎｇ（地理的ルーティング）が、従来の技術として知られている。このＧｅｏｇｒａｐｈｉｃ　Ｒｏｕｔｉｎｇでは、図６に示すような固有情報を各ノードが保有していると仮定した場合に、図７に示すような情報を、ルーティングのためのテーブル情報として得るようにしている。
【００１１】
各ノードは、位置検出手段で検出される自分の位置（例えば緯度や経度）と、周辺ノードのネットワークＩＤや位置などの地理情報から、自律的にルートを決定する。ここでいう自律的なルートの決定とは、あるノードへパケットを送るときに、送りたいノードになるべく近いノードへ、そのパケットを送って行くという手法である。この送信方法では、隣接ノード間で不必要なパス情報をやり取りすることなく、パケットを送ることが可能になる。
【００１２】
上記図６および図７において、符号１０１を付したＩＤは、ネットワークにおいて唯一の端末番号であって、これは例えばＭＡＣアドレスやＩＰアドレスなどのノード識別情報が記憶格納される。位置情報１０２はＧＰＳ（Ｇｌｏｂａｌ　Ｐｏｓｉｔｉｏｎｉｎｇ　Ｓｙｓｔｅｍ）などの位置検出手段によって各ノードが獲得できる情報で、この位置情報１０２には自ノードの位置を特定する経度データ１０３や緯度データ１０４などが含まれている。移動速度１０５は、自身のノードが実際にどのように動いているのかを示す情報、すなわち速度データ１０６や向きデータ１０７などを含んでいる。情報元のＩＤ１０８は、文字通り情報元のノードのＩＤを記憶格納するものである。Ｆｉｒｓｔ＿Ｆｌａｇと記されているフラグ１０９は、情報元のノードとのやり取りを初めて行なったか否かを判断するためのものである。拡張情報１１０は、ノードの無線レンジ幅や電池残量などのデータを含んでいる。
【００１３】
さらに更新した時刻１１１は、情報元のノードＩＤからルーティングテーブルを交換した時刻である。すなわち図８に示すように、情報元のノードＢからの情報を中間ノードＡが時刻ｔ（１）に受取り、さらにノードＣが時刻ｔ（２）に受取ったと仮定すると、ノードＢの情報をノードＣがノードＡから受け取った場合に、時刻ｔ（１）がノードＣにおける更新した時刻１１１として格納記憶される。また、ここでいう情報元のＩＤ１０８は、図８の場合において、ノードＡおよびノードＢのことであり、自身のノードＣがノード情報を受け取るのに関わった全てのノードＡ，ＢのＩＤを指す。
【００１４】
このようなＧｅｏｇｒａｐｈｉｃ　Ｒｏｕｔｉｎｇを用いれば、各ノードの自律的なパケットフォワーディング（転送）が達成できるため、上述のＯｎ−Ｄｅｍａｎｄ型あるいはＰｒｏ−Ａｃｔｉｖｅ型のルーティングプロトコルのような地理情報を用いない手法に比べて、ルーティングテーブルを交換するためのプロトコルパケット量を大幅に削減でき、伝送効率を上げることができる。しかし、こうしたＧｅｏｇｒａｐｈｉｃ　Ｒｏｕｔｉｎｇの手法では、周辺ノードを検索する際にやはりフラッデイング方式を使用しなければならず、重複するノードのＩＤや地理情報などが送られる。したがって、他のノードからのルーティング情報を得るに際して、トラフィックの増加を招くといった問題を生じていた。
【００１５】
そこで本発明は、他のノードからより少ないトラフィックによって周辺ノード情報を得ることができるアドホックネットワークのルーティング方法を提供することをその目的とする。
【００１６】
【課題を解決するための手段】
本発明の請求項１におけるアドホックネットワークのルーティング方法は、ノード固有の識別情報とノードの位置や移動速度を特定する地理情報とからなる周辺ノード情報を、無線レンジ内にある周辺ノードと交換し、前記周辺ノード情報を得たら、この周辺ノード情報から情報元にパケットを送るアドホックネットワークのルーティング方法において、前記各ノードは周辺ノードのそれぞれに対して、自ノードが知っている周辺ノード情報を送るか送らないかの判断を行なうものである。
【００１７】
この場合、取得した周辺ノード情報に含まれる自身の位置や、周辺ノードの識別情報および地理情報を参考にして、各ノードがネットワーク上でのルートを自律的に決定し、情報元にパケットをフォワーディングする。特に各ノードは、周辺ノードを検索する際に、自ノードが知っている周辺ノード情報を送るか送らないかの判断を行なってから、必要に応じて周辺ノード情報を送るようにしているので、従来のように無条件で送信を行なうフラッデイング方式に比べて、より少ないトラフィックによって他のノードからルーティングに関わる周辺ノード情報を得ることができる。
【００１８】
また、本発明の請求項２におけるアドホックネットワークのルーティング方法は、前記判断が自ノードの無線レンジと、送る相手ノードの無線レンジと、この相手ノードの無線レンジ内にある周辺ノードの位置とを利用して行なわれる。
【００１９】
このように、自ノードの無線レンジと、送る相手ノードの無線レンジと、この相手ノードの無線レンジ内にある周辺ノードの位置とを利用して、自ノードが知っている周辺ノード情報を送るか送らないかの判断を、各周辺ノード毎に行なうので、周辺ノード情報の送信を必要最小限に止めることができる。
【００２０】
本発明の請求項３におけるアドホックネットワークのルーティング方法は、前記自ノードが知っている周辺ノード情報を、自ノードの移動速度と、予め得ている周辺ノードの移動速度とを用いて補正するようにしている。
【００２１】
このようにすると、例えば周辺ノードと周期的に情報交換を行なう必要のない場合や、何等かの原因で周辺ノードと情報交換ができない場合であっても、自ノードの移動速度と、予め得ている周辺ノードの移動速度とを利用して、常に周辺ノードの確からしい位置を予測した周辺ノード情報を保持することができる。
【００２２】
【発明の実施形態】
以下、添付図面を参照しながら、本発明における好適な実施例を説明する。図１は、アドホックネットワークの全体構成を示したものである。同図において、ソースノードとしてのノードＸは、このノードＸの周囲に点線で示した無線レンジｘ内にある他のノード（例えばこの図１では、ノードＢ，Ｃ）と双方向の通信が可能であり、最終通信対象となるノードＡは、このノードａの周囲に点線で示した無線レンジＡ内にある他のノード（例えばこの図１では、ノードＤ）と双方向の通信が可能になっている。勿論、ここでは図示していないが、他のノードＢ，Ｃ，Ｄも自身が保有する送信手段により、一定の無線レンジｂ，ｃ，ｄ内での双方向通信が可能となっている。これらのノードＸ，Ａ，Ｂ，Ｃ，Ｄは、いずれも位置情報検出手段を備えた移動体端末で構成され、したがってノードＸとノードＡとの間のルーティングも時間の経過と共に刻々と変化する。
【００２３】
各ノードＸ，Ａ，Ｂ，Ｃ，Ｄは、前記図７における自身のノード情報を保有している。これは前述のように、少なくとも自身のノードを識別する固有の識別情報としてのＩＤ１０１と、位置検出手段によって得られる自身のノードの経度データ１０３や緯度データ１０４などを含んだ位置情報１０２と、自身のノードが実際にどのように動いているのかを示す速度データ１０６や向きデータ１０７などを含んだ移動速度１０５とを保有して構成される。また、このノード情報とは別に、ルーティングのためのテーブル情報（ルーティングテーブル情報）を、各ノードＸ，Ａ，Ｂ，Ｃ，Ｄは保有している。その詳細は、前記図８で示した通りである。因みに、図７に示すノード情報は、各ノードＸ，Ａ，Ｂ，Ｃ，Ｄで共通化すなわち標準化する必要があるが、それ以外の例えばルーティングテーブルなどは、どのように構築しても構わない。
【００２４】
次に、上記構成に基づく作用を図２〜図４の各フローチャートに基づき説明する。ここにあるフローチャートは、前述のノードＸがその無線レンジｘ内にある周辺ノードへＩＤ１０１や位置情報１０２などを含んだ地理情報を送るアルゴリズムを示したものである。但し、図３の表記記号において、ノードＡの無線レンジａ内にあるノードの集合を、図５の（１）に示すように、Ｎｏｄｅ（Ａ）と表わす。また、２つの無線レンジにまたがる領域にあるノードの集合は論理記号を用いる。例えば図５の（２）では、ノードＡの無線レンジａ内であって、かつノードＸの無線レンジｘ内に存在するノード群を次の数１のように表わす。
【００２５】
【数１】
2004032559.tif 000003
【００２６】
図２は、ノードＸが自律的に周辺ノードのルーティングテーブルを得るプロトコルの手順を示している。ステップＳ１において、ノードＸは無線レンジｘ内にある全ての周辺ノードＢ，Ｃに対して問合せを行ない、応答のあった周辺ノードＢ，Ｃに含まれる情報から、ノード情報を更新していない周辺ノードが存在するか否かを判断する。もし、更新していない周辺ノードが存在するならば、ステップＳ２に移行し、自ノードＸ自身のノード情報を周辺ノードＢ，Ｃ自身のノード情報と交換して、ステップＳ１の手順に戻る。
【００２７】
また、更新していない周辺ノードが存在しなければ、ステップＳ３の手順に進み、送るべきノード情報を判断していないノードが、周辺ノードＢ，Ｃのなかで存在するか否かを調べる（ステップＳ３）。もし、そのようなノードが存在する場合は、ステップＳ４に移行して、相手ノードＡと無線レンジｘ内のノードとの情報交換が初めてであるか否かを判断する。そして、相手ノードＡと無線レンジｘ内にあるノードとの情報交換が初めてではない場合は、次のステップＳ５において、収集した相手ノードＡの位置情報１０２からノードＡの無線レンジａを予測し、自ノードＸの無線レンジｘ内に存在する各ノードＢ，ＣのＩＤ１０１や位置情報１０２を送るべきかどうか判断する（ステップＳ６）。なお、ここでの判断処理の詳細は、図３のフローチャートにて後程説明する。そして、次のステップＳ７において、送る必要のある周辺ノード情報のみを相手ノードＡに送信し、ステップＳ３の手順に戻る。
【００２８】
一方、前記ステップＳ３の手順で、送るべき周辺ノード情報を判断していないノードが、周辺ノードＢ，Ｃの中に存在していない場合は、ステップＳ８に移行する。また、ステップＳ４の手順で、相手ノードＡと無線レンジｘ内のノードとの情報交換が初めてであれば、ステップＳ９において、ルーティングテーブルを一括で送るプロセスを行なった後で、同様にステップＳ８に移行する。このステップＳ８で、ノードＸが周辺ノードを全く知らない場合か、或いは自ノードＸの速さ（速度や向き）が変化する場合には、ステップＳ１の手順に戻るが、そうでなければステップＳ８の処理を続行する。すなわちノードＸが初めて通信を行なう場合か、さもなければ自ノードの速さが変化しない限り、ルーティングテーブルの更新は行なわれない。
【００２９】
この一連の手順が終了した後で、各ノードは周辺ノード情報を用いてパケットをフォワーディングする。この時のルーティング手法は、既存のＧｅｏｇｒａｐｈｉｃ　Ｒｏｕｔｉｎｇを利用するか、ノードのルーティングテーブルを受取った元のノードにフォワードするなどの方法で行なう。
【００３０】
次に、前記図２のステップＳ６において、自ノードＸが自身に保有する周辺ノード情報を送るか否かを自律的に判断する処理手順を、図３のフローチャートに基づき説明する。先ずステップＳ１１において、送るべきノード情報を判断しているノードが、ノードＡの無線レンジａ内に存在する場合は、そのノードに関する情報は送らないと判断し（ステップＳ１２）、後述するステップＳ２８にそのまま移行する。これに対して、判断しているノードが、ノードＡの無線レンジａ内に存在しなければ、ステップＳ１３に移行し、そのノードが無線レンジａに含まれず、かつ無線レンジｘ内に存在するものであるか否かを調べる。もしそうであれば、無線レンジａ内であって、かつ無線レンジｘ内に存在するノード群のリストを選び出す。但し、今回初めて通信したノードはリストから外す（ステップＳ１４）。
【００３１】
続くステップＳ１５では、前記ステップＳ１４で選び出したリストを参照して、無線レンジａに含まれず、かつ無線レンジｘ内に存在する各ノード毎に、自ノードＸと、無線レンジａ内であって、かつ無線レンジｘ内に存在するノード群との距離を、それぞれの位置情報１０２から算出し、自ノードＸの方が最短距離であるか否かを調べる。もし、自ノードＸの方が最短距離であれば、無線レンジａに含まれず、かつ無線レンジｘ内にある判断しているノードの情報を送ると判断する（ステップＳ１６）。これに対して、自ノードＸではなく、無線レンジａ内であって、かつ無線レンジｘ内に存在するいずれか一つのノードの方が、最短距離であった場合は、ステップＳ１７に移行して、無線レンジａに含まれず、かつ無線レンジｘ内にある判断しているノードの情報を送らないとして判断する。そして、まだ送るか否かの判断をしていない別のノードが、無線レンジａに含まれず、かつ無線レンジｘ内にあれば、ステップＳ１５に戻ってそれらの各ノード毎に同様の判断を繰り返し行なう（ステップＳ１８）。
【００３２】
さらに、前記ステップＳ１３において、送るべきノード情報を判断している判断しているノードが無線レンジａおよび無線レンジｘ内のいずれにも含まれない場合に、ステップＳ２１の手順に移行する。なお、このステップＳ２１移行の処理は、前記ステップＳ３０において、無線レンジａに含まれず、かつ無線レンジｘ内にある全てのノードについて、情報を送るか否かの判断を終了した後で行なわれる。
【００３３】
ステップＳ２１では、無線レンジａに含まれないか、あるいは無線レンジｘに含まれないノード群のリストを選び出す。そして次のステップＳ２２では、前記ステップＳ２１で選び出したリストを参照し無線レンジａおよび無線レンジｘ内のいずれにも含まれない各ノード毎に、無線レンジａに含まれないか、あるいは無線レンジｘに含まれないノード群との距離を、それぞれの位置情報１０２から算出し、無線レンジａ内にあるノードとの間で最短距離となっているか否かを調べる。但し、無線レンジａ内にあるノードの中で、今回初めて通信したノードは除外する。
【００３４】
そして、無線レンジａ内にあるノードとの間で最短距離となっていれば、判断しているノードの情報を送ると判断する（ステップＳ２３）。これに対して、無線レンジａ内にあるノードとの間で最短距離となっていなければ、判断しているノードの情報は送らないと判断する（ステップＳ２４）。そして、まだ送るか否かの判断をしていないノードが他に存在すれば、ステップＳ２２に戻ってそれらの各ノード毎に同様の判断を繰り返し行なう（ステップＳ２５）。
【００３５】
こうして最終的には、送るべきノード情報を判断しているノードの全てについて、周辺ノードの情報を送るか否かの判断を集計し（ステップＳ２８）、前記ステップＳ１６やステップＳ２３で送ると判断した周辺ノードの情報のみを、自ノードＸから相手ノードＡに送信する。
【００３６】
次に、前記図２に示すステップＳ９の手順、すなわちノードがその無線レンジ内で初めて通信するような場合に、あるノードから一括してルーティングテーブルを受取る手順を図４に基づき説明する。先ずステップＳ３１において、自ノードＸは、予め決められた条件である相手ノードＡの周辺（例えばｙメートル以内）の、所定時間（例えばｔ秒）以内におけるルーティングテーブルを持っているか否かを調べる。もしそのような条件のルーティングテーブルを持っていなければ、それはノードＡに対し必要のない情報と判断して、ノードＡにルーティングテーブル情報は送らない（ステップＳ３２）。これに対して、そのような条件のルーティングテーブルを持っていれば、その条件を満たすノードの中で、自ノードＸが最もノードＡに近い距離にあるか否かを、位置情報１０２に基づき調べる（ステップＳ３３）。仮に、自ノードＸがノードＡの周辺の最も近い位置にあるあれば、ステップＳ３４に移行して、全てのルーティングテーブル情報をノードＡに転送する。逆に、自ノードＸ以外で、ノードＡの周辺の最も近い位置にノードが存在すれば、ノードＡにルーティングテーブル情報は送らない（ステップＳ３５）。
【００３７】
このように、上記手順でルーティングテーブルを持っているか否かの判断は、現在利用しているルーティングテーブルだけでなく過去に利用していたルーティングテーブルも参照する。
【００３８】
また、周期的な情報交換がない場合や、何等かの障害などにより周辺ノードとの情報交換ができない場合には、自ノードＸの位置情報１０２や移動速度１０５、および予め得ている周辺ノードの位置情報１０２や移動速度１０５を利用して、図７に示すようなルーティングテーブルを補正する補正処理手段を、各ノードＸ，Ａ，Ｂ，Ｃ，Ｄは備えている。
【００３９】
例えば、あるノードが保有するルーティングテーブルの位置情報１０２や移動速度１０５において、時刻ｔで速さがＳｉであるノードの位置が（ｘｉ，ｙｉ）と記録されている場合、現在時刻が時刻ｔからΔｔだけ過ぎていたとすると、そのノードの現在時刻における推定位置は、（ｘｉ＋Ｓｉ・Δｔ・ｓｉｎθ，ｙｉ＋Ｓｉ・Δｔ・ｃｏｓθ）と補正できる。ここで、θは相対的な向きであり、例えば赤道に対するノードの向いている角度などを採用できる。さらにこの方法を拡張すると、各ノードが一定の時間（例えばｔ秒）以内における過去のルーティングテーブルを保持することにより、この過去のルーティングテーブルを合せて交換すれば、同様な計算方法で、過去の情報から現在の情報を推定する補正処理がより正確に行なえる。このように、過去のルーティングテーブルにおける移動速度１０５の情報を利用して、現在時刻におけるノードの位置を補正できる補正処理手段の方法を、各ノードが行なえるとすると、図２のステップＳ８に示すように、ノードが初めて通信を行なう場合か、あるいはノードの移動速度１０５（速さや向き）が変化したときにのみ、ルーティングテーブルの更新を行なえばよいので、さらに交換する情報量が減ることになり、すなわち迅速で効率の良いルーティングテーブルの更新を行なうことができる。
【００４０】
本実施例では、あるノードＡが周辺ノードと１回ルーティングテーブルを交換した場合に送られてくるノード情報の数Ｓを、従来の手法であるフラッディングで行った場合に、その量を大幅に削減できる。ここで、以下に示す各式で用いる変数を次のように定義する。
Ｎ：存在する全てのノード数。
ｎ（論理式）：論理式で表わせるエリア内に存在するノード数。例えば、次の数２に示す記号は、ノードＡの無線レンジａ内にあって、かつノードＸの無線レンジｘ内に存在するノード数である。
Ｎｏｄｅ（Ａ）：ノードＡの無線レンジ内ａに存在するノードの集合
Ｒ（Ａ）：ノードＡが保有しているルーティングテーブルにおけるノード情報の数
【００４１】
【数２】
2004032559.tif 000004
【００４２】
従来例におけるフラッデイングによる手法では、ノード情報の数Ｓが次の数３のようになる。
【００４３】
【数３】
2004032559.tif 000005
【００４４】
ここで、分散するノードが均一であるとすると、上記数３におけるノード情報の数Ｓは、次の数４のように近似できる。
【００４５】
【数４】
2004032559.tif 000006
【００４６】
一方、本実施例におけるノード情報の数Ｓは、上述したように冗長なノード情報を送らないので、次の数５のようになる。
【００４７】
【数５】
2004032559.tif 000007
【００４８】
上記数式の比較によれば、時間が経過した場合に送られてくるノード情報の数Ｓは、本実施例に比べてフラッデイングによる手法が、（ｎ（Ａ）−１）倍増加する。そのため、特に周辺ノードの数が増えるほど、本実施例におけるノード情報の数Ｓと、従来手法によるノード情報の数Ｓとの差が大きくなる。
【００４９】
具体的に、本発明では時間が十分に経過したと仮定すると、前記数５がＳ＝γに近似されるが、例えばγ＝４００ノード，ｎ（ｘ）＝１００ノードで、一度に送るパケット情報量が６４バイト（ＩＤ１０１が８バイト，位置情報１０２が２４バイト，速度が８バイト，向きが２４バイト）であるとする。この場合、１回の更新で一つのノードでは、従来のフラッデイング方式でＳ＝（１００−１）＊４００＊６４＝２．５３メガバイトとなり、本実施例における手法でＳ＝４００＊６４＝２５．６キロバイトとなる。すなわち、本実施例の手法は情報量が約０．０１倍に削減されることがわかる。
【００５０】
このように本実施例では、アドホックネットワークにおけるルーティングにおいて、通信パケット量を従来の方法に比較して少なくできるため、少ないコストで安定したルーティング情報を、端末である各ノードが確保できる。そのため、効率の良い通信が行なえるようになる。
【００５１】
また前述したように、ルーティングテーブルの位置情報を次の数６に示すように各ノードでダイナミックに変化させ、ノード自体の移動速度１０５（速さや向き）が変化したときに、そのルーティングテーブルを各ノード間でリフレッシュする。
【００５２】
【数６】
2004032559.tif 000008
【００５３】
但し、（ｘｉ，ｙｉ）は、ｉ番目のノードの位置情報１０２である。このようにすると、最新のトラフィックで常に各ノードが最新のルーティングテーブル情報を保有することができる。また、ノードの移動速度１０５に適した間隔でリフレッシュできる。
【００５４】
さらに、アドホックネットワークに新たに参入してくるノードには、近くのノードから一括してルーティングテーブルを送ることにより、無駄なトラフィックを削減する効果がある。
【００５５】
このように本実施例によれば、ノード固有の識別情報であるＩＤ１０１と、ノードの位置や移動速度を特定する地理情報（位置情報１０２，移動速度１０５）とからなる周辺ノード情報を、無線レンジ内にある周辺ノードと交換し、ノードに保有している得られた周辺ノード情報から情報元にパケットを送るアドホックネットワークのルーティング方法において、各ノード各ノードＸ，Ａ，Ｂ，Ｃ，Ｄは周辺ノードのそれぞれに対して、自ノードが知っている周辺ノード情報を送るか送らないかの判断を行なっている。
【００５６】
この場合、取得した周辺ノード情報に含まれる自身の位置や、周辺ノードの識別情報および地理情報を参考にして、各ノードＸ，Ａ，Ｂ，Ｃ，Ｄがネットワーク上でのルートを自律的に決定し、情報元にパケットをフォワーディングする。特に各ノードＸ，Ａ，Ｂ，Ｃ，Ｄは、周辺ノードを検索する際に、自ノードが知っている周辺ノード情報を送るか送らないかの判断を行なってから、必要のある場合にのみ周辺ノード情報を送るようにしている。そのため、従来のように無条件で送信を行なうフラッデイング方式に比べて、より少ないトラフィックによって他のノードからルーティングに関わる周辺ノード情報を得ることができる。
【００５７】
またその場合、自ノードが知っている周辺ノード情報を送るか送らないかの判断は、自ノードの無線レンジと、送る相手ノードの無線レンジと、この相手ノードの無線レンジ内にある周辺ノードの位置とを利用して行なうのが好ましい。すなわち、自ノードの無線レンジと、送る相手ノードの無線レンジと、この相手ノードの無線レンジ内にある周辺ノードの位置とを利用して、自ノードが知っている周辺ノード情報を送るか送らないかの判断を、各周辺ノード毎に行なえば、周辺ノード情報の送信を必要最小限に止めることができる。
【００５８】
さらに本実施例では、自ノードが知っている周辺ノード情報を、自ノードの移動速度と、予め得ている周辺ノードの移動速度とを用いて補正するようにしている。
【００５９】
このようにすると、例えば周辺ノードと周期的に情報交換を行なう必要のない場合や、何等かの原因で周辺ノードと情報交換ができない場合であっても、自ノードの移動速度と、予め得ている周辺ノードの移動速度とを利用して、常に周辺ノードの確からしい位置を予測した周辺ノード情報を保持することができる。
【００６０】
また、過去の自ノードや周辺ノードにおける移動速度１０５の情報を利用して、現在時刻におけるノードの位置を各ノードＸ，Ａ，Ｂ，Ｃ，Ｄで補正できるようにすれば、ノードが初めて通信を行なう場合か、あるいはノードの移動速度１０５が変化したときにのみ、周辺ノード情報の更新を行なえばよく、交換する情報量がさらに減って、迅速で効率の良い周辺ノード情報の更新を行なうことが可能になる。
【００６１】
なお、本発明は上記実施例に限定されることなく、本発明の範囲内で種々の変形実施が可能である。
【００６２】
【発明の効果】
本発明の請求項１におけるアドホックネットワークのルーティング方法によれば、他のノードからより少ないトラフィックによって周辺ノード情報を得ることができる。
【００６３】
本発明の請求項２におけるアドホックネットワークのルーティング方法によれば、周辺ノード情報の送信を必要最小限に止めることができる。
【００６４】
本発明の請求項３の構成によれば、常に周辺ノードの確からしい位置を予測した周辺ノード情報を保持することができる。
【図面の簡単な説明】
【図１】本発明の一実施例を示すアドホックネットワークの全体構成をあらわした概略説明図である。
【図２】同上あるノードが周辺ノードのルーティング情報を交換する際の手順を示したフローチャートである。
【図３】同上自身のノード中にある周辺ノード情報を送るか否かを自律的に判断する際の手順を示したフローチャートである。
【図４】同上新しいノードに対してルーティングテーブルを一括して送る手順を示したフローチャートである。
【図５】図３に記述される各論理記号をベン図で示した概略説明図である。
【図６】Ｇｅｏｇｒａｐｈｉｃ　Ｒｏｕｔｉｎｇを利用した各ノードの固有情報のフォーマット構成図である。
【図７】Ｇｅｏｇｒａｐｈｉｃ　Ｒｏｕｔｉｎｇを利用した各ノードが持つルーティングテーブルのフォーマット構成図である。
【図８】図７における「更新した時刻」を説明するための概略説明図である。
【符号の説明】
Ｘ，Ａ，Ｂ，Ｃ，Ｄ　ノード
【図１】
2004032559.tif 000009
【図２】
2004032559.tif 000010
【図３】
2004032559.tif 000011
【図４】
2004032559.tif 000012
【図５】
2004032559.tif 000013
【図６】
2004032559.tif 000014
【図７】
2004032559.tif 000015
【図８】
2004032559.tif 000016