無線通信端末および経路構築方法
【課題】通信経路を構築する場合に、経路探索パケットの伝送範囲を最適に絞り込むこと。
【解決手段】ノード１００は、通信経路探索パケットを受信した場合に、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されているか否かを判定する。ノード１００は、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されている場合には、通信経路探索パケットをブロードキャストする。これに対して、ノード１００は、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されていない場合には、通信経路端末パケットの探索範囲の値を減算する。そして、ノード１００は、減算した探索範囲の値が０以上の場合に、通信経路探索パケットをブロードキャストする。
【解決手段】ノード１００は、通信経路探索パケットを受信した場合に、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されているか否かを判定する。ノード１００は、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されている場合には、通信経路探索パケットをブロードキャストする。これに対して、ノード１００は、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されていない場合には、通信経路端末パケットの探索範囲の値を減算する。そして、ノード１００は、減算した探索範囲の値が０以上の場合に、通信経路探索パケットをブロードキャストする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線通信端末等に関する。
【背景技術】
【０００２】
近年、複数の無線通信端末が自律分散的に相互接続するアドホックネットワークの研究が進められている。アドホックネットワークには、例えば、スマートネットなどの固定形マルチホップネットワークが含まれる。以下では、無線通信端末をノードと表記する。アドホックネットワークでは、アクセスポイントは設定されず、各ノードが、隣接ノードから受信したパケットを通信経路に基づき他のノードに転送することで、パケットを目的地に送信する。
【０００３】
アドホックネットワークの各ノードは、ハローパケット（Hello Packet）を送受信することで、通信経路を構築することができる（例えば特許文献１参照）。ここで、ゲートウェイ（Ｇａｔｅｗａｙ：以下適宜「ＧＷ」と表す）から各ノードへの通信経路（下り方向）を構築するに際して、以下の前提条件１、２のもと経路構築を行うことを考えてみる。
【０００４】
前提条件１は、上り方向の通信経路が作成済みという条件である。上り方向は、ノードからＧＷに至る方向である。上り方向の通信経路が作成済みの場合には、目的地「ＧＷ」にパケットを送信するための転送先のノードが１つ以上通信経路に登録されている。なお、通信経路の作成は先の特許文献１に記載された技術を用いることができる。
【０００５】
前提条件２は、各ノードがＧＷに複数回パケットを送信していて、その上り方向の通信経路を利用して下り方向の通信を行うために、ＧＷの通信経路上の中継ノードには、下り方向の通信経路用のテーブルに目的地となるノード毎に転送先のノードが登録されているという条件である。ただし、ＧＷの通信経路の目的地のノードは、ＧＷにパケットを送信した送信元のノードとする。
【０００６】
上記前提条件１、２においては、経路候補数が限られ、また、ネットワークの変化に対する追随性が問題となる。そこで、送信要求が発生して後でルーティングテーブルを動的に作成するReactive方式を利用することが解決策として考えられる。Reactive方式では、送信要求が発生すると、宛て先を探すためのリクエストパケットを自己の近隣ノードに対して一斉送信（フラッディング）する。例えば、ＧＷは、通信経路に含まれるノードを目的地に設定した経路探索パケットを全方位にブロードキャストする。ＧＷは、該経路探索パケットを受信した目的地のノードからの応答を受信し、目的地のノードに至る複数の通信経路を作成する。このように、目的地のノードに至る複数の通信経路を有していると、ネットワークの変化により、ある通信経路が利用できなくなっても、他の通信経路を利用することで、目的地のノードにパケットを送信することができる。
【０００７】
なお、経路探索パケットを全方位にブロードキャストすると、ネットワーク全体にかかる負荷が大きくなるため、経路探索パケットのホップ数に制限をかけるという技術が存在する（例えば特許文献２参照）。探索要求パケットのホップ数に制限をかけることで、経路探索パケットの伝搬範囲が絞り込まれ、ネットワーク全体にかかる負荷を抑えることができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００９−２６７５３２号公報
【特許文献２】特開２００７−１８４８２７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上述した従来技術では、通信経路を構築する場合に、経路探索パケットの伝送範囲を最適に絞り込むことができないという問題があった。
【００１０】
たとえば、従来のReactive方式では、経路探索パケットがＧＷを中心に円状に広がっていくため、目的地のノードとは違う方向にも経路探索パケットが伝送されてしまう。また、目的地のノードに至る通信経路が迂回経路しか存在しない場合には、経路探索パケットの伝送範囲を超えてしまい、経路探索パケットが目的地のノードに届かず、目的地のノードに至る通信経路を構築することができない場合があった。
【００１１】
開示の技術は、上記に鑑みてなされたものであって、通信経路を構築する場合に、経路探索パケットの伝送範囲を最適に絞り込むことができる無線通信端末および経路構築方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
開示の無線通信端末は、判定部と送信制御部とを有する。判定部は、探索対象となる無線通信端末の情報と探索範囲を示す値とを有するパケットを受信した場合に、目的地の経路を含む通信経路テーブルを参照し、該通信経路テーブルの目的地に、探索対象となる無線通信端末が含まれているか否かを判定する。送信制御部は、判定部の判定結果に基づいて、通信経路テーブルの目的地に、探索対象となる無線通信端末が含まれている場合には、パケットを隣接する無線通信端末に送信する。一方、送信制御部は、通信経路テーブルの目的地に、探索対象となる無線通信端末が含まれていない場合には、探索範囲を示す値から所定値を減算し、該探索範囲を示す値が所定の閾値以上の場合には、パケットを隣接する無線通信端末に送信する。
【発明の効果】
【００１３】
開示の無線通信端末によれば、通信経路を構築する場合に、経路探索パケットの伝送範囲を最適に絞り込むことができるという効果を奏する。
【図面の簡単な説明】
【００１４】
【図１】図１は、アドホックネットワークの構成を示す図である。
【図２】図２は、ノードの構成を示す図である。
【図３】図３は、ハローパケットのデータ構造の一例を示す図である。
【図４】図４は、ワークテーブルのデータ構造の一例を示す図である。
【図５】図５は、通信経路テーブルのデータ構造の一例を示す図である。
【図６】図６は、経路構築パケットのデータ構造の一例を示す図である。
【図７】図７は、経路探索パケットのデータ構造の一例を示す図である。
【図８】図８は、ハローパケットによる経路構築の処理手順を示す図である。
【図９】図９は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（１）である。
【図１０】図１０は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（２）である。
【図１１】図１１は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（３）である。
【図１２】図１２は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（４）である。
【図１３】図１３は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（５）である。
【図１４】図１４は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（６）である。
【図１５】図１５は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（７）である。
【図１６】図１６は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（８）である。
【図１７】図１７は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（９）である。
【図１８】図１８は、経路構築パケットによる経路構築の処理を説明する図（１）である。
【図１９】図１９は、経路構築パケットによる経路構築の処理を説明する図（２）である。
【図２０】図２０は、経路構築パケットによる経路構築の処理を説明する図（３）である。
【図２１】図２１は、経路構築パケットによる経路構築の処理を説明する図（４）である。
【図２２】図２２は、経路探索パケットの転送処理を説明するための図（１）である。
【図２３】図２３は、経路探索パケットの転送処理を説明するための図（２）である。
【図２４】図２４は、経路探索パケットの転送処理を説明するための図（３）である。
【図２５】図２５は、経路探索パケットの転送処理を説明するための図（４）である。
【図２６】図２６は、経路探索パケットの転送処理を説明するための図（５）である。
【図２７】図２７は、経路探索パケットの転送処理を説明するための図（６）である。
【図２８】図２８は、経路探索パケットの転送処理を説明するための図（７）である。
【図２９】図２９は、経路探索パケットの転送処理を説明するための図（８）である。
【図３０】図３０は、ハローパケット受信処理の処理手順を示すフローチャートである。
【図３１】図３１は、ハローパケット送信処理の処理手順を示すフローチャートである。
【図３２】図３２は、経路構築パケットの送信処理の処理手順を示すフローチャートである。
【図３３】図３３は、経路構築パケットの受信処理の処理手順を示すフローチャートである。
【図３４】図３４は、経路探索パケットの処理手順を示すフローチャートである。
【図３５】図３５は、ノードを構成するコンピュータのハードウェア構成を示す図である。
【発明を実施するための形態】
【００１５】
以下に、本願の開示する無線通信端末および経路構築方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００１６】
本実施例にかかるアドホックネットワークの構成について説明する。図１は、アドホックネットワークの構成を示す図である。図１に示すように、このアドホックネットワークは、ノード１００ａ〜１００ｇ、１００ｘ〜１００ｚを有する。ノード１００ａ〜１００ｇ、１００ｘ〜１００ｚは、無線通信端末の一例である。また、ノード１００ｇは、ＧＷ（Gate Way）に対応する。
【００１７】
ノード１００ａ〜１００ｇ、１００ｘ〜１００ｚは、隣接のノードと無線により接続する。例えば、ノード１００ｇは、ノード１００ａ、１００ｂ、１００ｘに接続される。ノード１００ａは、ノード１００ｇ、１００ｃ、１００ｄに接続される。ノード１００ｂは、ノード１００ｇ、１００ｄ、１００ｅ、１００ｙに接続される。ノード１００ｃは、ノード１００ａ、１００ｄ、１００ｆに接続される。ノード１００ｄは、ノード１００ａ、１００ｂ、１００ｃ、１００ｅ、１００ｆに接続される。１００ｅは、ノード１００ｂ、１００ｄ、１００ｆに接続される。ノード１００ｆは、ノード１００ｃ、１００ｄ、１００ｅに接続される。ノード１００ｘは、ノード１００ｇ、１００ｂ、１００ｙに接続される。ノード１００ｙは、ノード１００ｂ、１００ｘ、１００ｚに接続される。ノード１００ｚは、ノード１００ｙに接続される。本実施例では、ノード１００ａ〜１００ｇ、１００ｘ〜１００ｙを総称する場合、ノード１００と表記する。
【００１８】
次に、本実施例にかかるノード１００の構成について説明する。図２は、ノードの構成を示す図である。図２に示すように、このノード１００は、無線通信部１１０、入力部１２０、表示部１３０、記憶部１４０、制御部１５０を有する。
【００１９】
無線通信部１１０は、隣接するノードとの間で無線によりデータ通信する装置である。例えば、無線通信部１１０は、無線リンクモジュールなどに対応する。制御部１５０は、この無線通信部１１０を介して、隣接するノードとの間でハローパケット等を送受信する。
【００２０】
入力部１２０は、各種の情報をノード１００に入力するための入力装置である。例えば、入力部１２０は、キーボード、マウス、タッチパネル等に対応する。表示部１２０は、各種の情報を表示する表示装置である。例えば、表示部１３０は、ディスプレイ、タッチパネル等に対応する。
【００２１】
記憶部１４０は、例えば、ワークテーブル１４０ａ、通信経路テーブル１４０ｂ、データ管理テーブル１４０ｃを記憶する。この記憶部１４０は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【００２２】
ワークテーブル１４０ａは、ハローパケットの情報を一時的に保持するテーブルである。ここで、ハローパケットのデータ構造の一例と、ワークテーブル１４０ａのデータ構造の一例について説明する。
【００２３】
図３は、ハローパケットのデータ構造の一例を示す図である。図３に示すように、ハローパケットは、ＧＳ、ＬＳ、Ｅを有する。このうち、ＧＳには、目的地のノードのアドレスが格納される。例えば、ＧＳには、ＧＷとなるノード１００ｇのアドレスが格納される。ＬＳには、ハローパケットを転送したノードのアドレスが格納される。Ｅには、例えば、ハローパケットのホップ数が格納される。
【００２４】
図４は、ワークテーブルのデータ構造の一例を示す図である。図４に示すように、このワークテーブル１４０ａは、ＧＤ、ＬＤ、Ｅを有する。ＧＤには、目的地のノードのアドレスが格納される。ＬＤには、転送先のアドレスが格納される。Ｅには、例えば、ハローパケットのホップ数が格納される。図３に示したハローパケットのＧＳ、ＬＳ、Ｅが、それぞれ、図４のワークテーブル１４０ａのＧＤ、ＬＤ、Ｅに格納される。
【００２５】
通信経路テーブル１４０ｂは、目的地となるノードにパケットを送信する場合に、どの隣接ノードにパケットを転送すればよいかを示すものである。図５は、通信経路テーブルのデータ構造の一例を示す図である。図５のＧＤ、ＬＤ、Ｅに関する説明は、上記図４のＧＤ、ＬＤ、Ｅに関する説明と同様である。図５に示すように、例えば、通信経路テーブル１４０ｂには、目的地のノード「ＧＤ」に対する複数の通信経路が記憶されている。この通信経路テーブル１４０ｂでは、ノード１００ｇにパケットを送信する場合には、ノード１００ａ〜１００ｅの何れかのノードにパケットを転送すればよいことを示している。図５では、説明の便宜上、ノードの名称を示しているが、ノードのアドレスが登録されてもよい。
【００２６】
データ管理テーブル１４０ｃは、パケットの送信履歴を記憶するテーブルである。このデータ管理テーブル１４０ｃは、後述の下り経路構築部１５０ｂにより利用される。
【００２７】
制御部１５０は、ハローパケット制御部１５０ａ、下り経路構築部１５０ｂ、経路探索パケット送信部１５０ｃ、経路探索パケット受信部１５０ｄを有する。制御部１５０は、ＡＳＩＣ（Application Specific Integrated Circuit）や、ＦＰＧＡ（Field Programmable Gate Array）などの集積装置に対応する。また、制御部１５０は、例えば、ＣＰＵやＭＰＵ（Micro Processing Unit）等の電子回路に対応する。
【００２８】
ハローパケット制御部１５０ａは、隣接のノードとハローパケットを送受信することで、通信経路テーブル１４０ｂに目的地「ＧＤ」、転送先「ＬＤ」、ホップ数「Ｅ」の関係を登録する処理部である。
【００２９】
ハローパケット制御部１５０ａが、ハローパケットを受信した場合の処理について説明する。ハローパケット制御部１５０ａは、ハローパケットのＧＳ、ＬＳの情報をワークテーブル１４０ａのＧＤ、ＬＤに格納する。また、ハローパケット制御部１５０ａは、ハローパケットのＥの値に１を加算したものを、ワークテーブル１４０ａのＥに格納する。そして、ハローパケット制御部１５０ａは、ワークテーブル１４０ａのレコードを通信経路テーブル１４０ｂに登録する。
【００３０】
ハローパケット制御部１５０ａが、ハローパケットを送信する場合の処理について説明する。例えば、ハローパケット制御部１５０ａは、クロックイベントが発生したことを契機にして、ハローパケットを生成する。
【００３１】
ハローパケット制御部１５０ａは、ハローパケットのＧＳに、通信経路テーブル１４０ｂのＧＳの情報を格納する。例えば、ハローパケット制御部１５０ａは、ゲートウェイに対応するノード１００ｇのアドレスをハローパケットのＧＳに格納してもよい。ハローパケット制御部１５０ａは、ハローパケットのＬＳに自ノード１００のアドレスを格納する。ハローパケット制御部１５０ａは、ハローパケットのＥに、通信経路テーブル１４０ｂのＥを格納する。
【００３２】
下り経路構築部１５０ｂは、上り方向の目的地のノードに対して、パケットを送信し、目的地に至る他のノードの下り経路構築部１５０ｂと協働して、下り方向の経路を構築する処理部である。下り方向の経路を構築することを目的として上り方向の目的地のノードに送信するパケットを、便宜上、経路構築パケットと表記する。
【００３３】
図６は、経路構築パケットのデータ構造の一例を示す図である。図６に示すように、この経路構築パケットは、ＧＤ、ＧＳ、ＬＳ、ＬＤ、Ｅ、ＦＩＤを有する。このうち、ＧＤは目的地を示すものであり、通信経路テーブル１４０ｂのＧＤの情報が格納される。ＧＳには、経路構築パケットの送信元のアドレスが格納される。ＬＳには、経路構築パケットの転送元のノードのアドレスが格納される。ＬＤには、経路構築パケットの転送先となる隣接ノードのアドレスが格納される。Ｅには、ホップ数が格納される。ＦＩＤには、経路構築パケットを一意に識別する値が格納される。下り経路構築部１５０ｂは、送信した経路構築パケットの情報を、送信履歴としてデータ管理テーブル１４０ｃに格納する。
【００３４】
経路探索パケット送信部１５０ｃは、ある目的地のノードに至る経路情報を増やすことを目的として、目的地のノードに経路探索パケットを送信する処理部である。図７は、経路探索パケットのデータ構造の一例を示す図である。図７に示すように、経路探索パケットは、ＧＳ、ＧＤ、探索範囲を有する。ＧＳには、経路検索パケットの送信元のノードのアドレスが格納される。ＧＤには、目的地のノードのアドレスが格納される。探索範囲には、経路探索パケットを転送するか否かを示す値が格納される。経路探索パケット送信部１５０ｃは、探索範囲に所定の数値を代入し、経路検索パケットをブロードキャストする。
【００３５】
経路探索パケット送信部１５０ｃは、経路探索パケットの目的地のノードから応答を受信しない場合には、探索範囲に代入する値を増やして、経路探索パケットを再送する。例えば、経路探索パケット送信部１５０ｃは、経路探索パケットをブロードキャストしてから、所定の時間が経過する間に応答を受信しない場合に、経路探索パケットを再送する。
【００３６】
経路探索パケット受信部１５０ｄは、経路探索パケットを受信した場合に、経路探索パケットの探索範囲に基づいて、経路探索パケットを送信する処理部である。経路探索パケット受信部１５０ｄは、判定部１５１と、送信制御部１５２を有する。
【００３７】
判定部１５１は、経路探索パケットのＧＤに格納されたノードが、通信経路テーブル１４０ｂのＧＤに含まれているか否かを判定し、判定結果を送信制御部１５２に出力する。
【００３８】
送信制御部１５２は、判定部１５１の判定結果に基づいて、経路探索パケットの送信制御を行う処理部である。
【００３９】
判定部１５１の判定結果に、経路探索パケットのＧＤに格納されたノードが、通信経路テーブル１４０ｂのＧＤに含まれている旨の情報が含まれている場合の送信制御部１５２の処理について説明する。この場合には、送信制御部１５２は、経路探索パケットの探索範囲の値をもとの初期値に戻し、経路探索パケットをブロードキャストする。
【００４０】
これに対して、判定部１５１の判定結果に、経路探索パケットのＧＤに格納されたノードが、通信経路テーブル１４０ｂのＧＤに含まれていない旨の情報が含まれている場合の送信制御部１５２の処理について説明する。この場合には、送信制御部１５２は、経路探索パケットの探索範囲の値から１を減算する。そして、送信制御部１５２は、減算した探索範囲の値が所定の閾値より大きい場合に、経路検索パケットをブロードキャストする。一方、送信制御部１５２は、減算した探索範囲の値が所定の閾値以下の場合には、経路検索パケットをブロードキャストする。例えば、探索範囲の値と比較される所定の閾値を０とする。
【００４１】
ところで、送信制御部１５２は、経路探索パケットのＧＤが、自ノードの場合には、経路探索パケットの送信元のノードに応答データを送信してもよい。
【００４２】
次に、アドホックネットワークのノード１００ａ〜１００ｇ、１００ｘ〜１００ｚがハローパケットを送受信して、通信経路テーブルを更新する処理について説明する。図８は、ハローパケットによる経路構築の処理手順を示す図である。また、図９〜図１７は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図である。
【００４３】
図８において、ノード１００ｇはハローパケットを、ノード１００ａ、１００ｂ、１００ｘに送信する（ステップＳ１０）。ノード１００ａは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ１１）。ノード１００ｂは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ１２）。ノード１００ｃは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ１３）。
【００４４】
図９において、ハローパケット１０は、ステップＳ１０において送信されるハローパケットである。通信経路テーブル１０ａ、１０ｂ、１０ｘは、それぞれ、ノード１００ａ、１００ｂ、１００ｘの通信経路テーブルである。ハローパケット１０のＧＤには「１００ｇ」、ＬＳには「１００ｇ」、Ｅには「０」が登録されている。
【００４５】
ノード１００ａは、ノード１００ｇからハローパケット１０を受信した場合に、通信経路テーブル１０ａのＧＤに「１００ｇ」、ＬＤに「１００ｇ」を登録する。また、ノード１００ａは、ハローパケット１０のＥの値に１を加算した値「１」を通信経路テーブル１０ａに格納する。ノード１００ｂは、通信経路テーブル１０ｂのＧＤに「１００ｇ」、ＬＤに「１００ｇ」を登録する。また、ノード１００ｂは、ハローパケット１０のＥの値に１を加算した値「１」を通信経路テーブル１０ｂに格納する。ノード１００ｘは、通信経路テーブル１０ｘのＧＤに「１００ｇ」、ＬＤに「１００ｇ」を登録する。また、ノード１００ｘは、ハローパケット１０のＥの値に１を加算した値「１」を通信経路テーブル１０ｘに格納する。
【００４６】
図８において、ノード１００ａは、ハローパケットをノード１００ｃ、１００ｄに送信する（ステップＳ２０）。ノード１００ｃは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ２１）。ノード１００ｄは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ２２）。
【００４７】
図１０において、ハローパケット２０は、ステップＳ２０において送信されるハローパケットである。通信経路テーブル１０ｃ、１０ｄは、それぞれ、ノード１００ｃ、１００ｄの通信経路テーブルである。ハローパケット２０のＧＤには「１００ｇ」、ＬＳには「１００ａ」、Ｅには「１」が登録されている。
【００４８】
ノード１００ｃは、ノード１００ａからハローパケット２０を受信した場合に、通信経路テーブル１０ｃのＧＤに「１００ｇ」、ＬＤに「１００ａ」を登録する。また、ノード１００ｃは、ハローパケット２０のＥの値に１を加算した値「２」を通信経路テーブル１０ｃに格納する。また、ノード１００ｄは、ノード１００ａからハローパケット２０を受信した場合に、通信経路テーブル１０ｄのＧＤに「１００ｇ」、ＬＤに「１００ａ」を登録する。また、ノード１００ｄは、ハローパケット２０のＥの値に１を加算した値「２」を通信経路テーブル１０ｄに格納する。
【００４９】
図８において、ノード１００ｂは、ハローパケットをノード１００ｄ、１００ｅ、１００ｙに送信する（ステップＳ３０）。ノード１００ｄは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ３１）。ノード１００ｅは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ３２）。ノード１００ｙは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ３３）。
【００５０】
図１１において、ハローパケット３０は、ステップＳ３０において送信されるハローパケットである。通信経路テーブル１０ｄ、１０ｅ、１０ｙは、それぞれ、ノード１００ｄ、１００ｅ、１００ｙの通信経路テーブルである。ハローパケット３０のＧＳには「１００ｇ」、ＬＳには「１００ｂ」、Ｅには「１」が登録されている。
【００５１】
ノード１００ｄは、ノード１００ｂからハローパケット３０を受信した場合に、通信経路テーブル１０ｄのＧＤに「１００ｇ」、ＬＤに「１００ｂ」を追加登録する。また、ノード１００ｄは、ハローパケット３０のＥの値に１を加算した値「２」を通信経路テーブル１０ｄに格納する。ノード１００ｅは、ノード１００ｂからハローパケット３０を受信した場合に、通信経路テーブル１０ｅのＧＤに「１００ｇ」、ＬＤに「１００ｂ」を格納する。また、ノード１００ｅは、ハローパケット３０のＥの値に１を加算した値「２」を通信経路テーブル１０ｅに格納する。ノード１００ｙは、ノード１００ｂからハローパケット３０を受信した場合に、通信経路テーブル１０ｙのＧＤに「１００ｇ」、ＬＤに「１００ｂ」を格納する。また、ノード１００ｙは、ハローパケット３０のＥの値に１を加算した値「２」を通信経路テーブル１０ｙに格納する。
【００５２】
図８において、ノード１００ｘは、ハローパケットをノード１００ｙに送信する（ステップＳ３５）。ノード１００ｙは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ３６）。
【００５３】
図１２において、ハローパケット３５は、ステップＳ３５において送信されるハローパケットである。通信経路テーブル１０ｙは、ノード１００ｙの通信経路テーブルである。ハローパケット３５のＧＳには「１００ｇ」、ＬＳには「１００ｘ」、Ｅには「１」が登録されている。
【００５４】
ノード１００ｙは、ノード１００ｘからハローパケット３５を受信した場合に、通信経路テーブル１０ｙのＧＤに「１００ｇ」、ＬＤに「１００ｘ」を追加登録する。また、ノード１００ｙは、ハローパケット３５のＥの値に１を加算した値「２」を通信経路テーブル１０ｙに格納する。
【００５５】
図８において、ノード１００ｃは、ハローパケットをノード１００ａ、１００ｄ、１００ｆに送信する（ステップＳ４０）。ノード１００ａは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ４１）。ノード１００ｄは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ４２）。ノード１００ｆは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ４３）。
【００５６】
図１３において、ハローパケット４０は、ステップＳ４０において送信されるハローパケットである。通信経路テーブル１０ａ、１０ｄ、１０ｆは、ノード１００ａ、１００ｄ、１００ｆの通信経路テーブルである。ハローパケット４０のＧＳには「１００ｇ」、ＬＳには「１００ｃ」、Ｅには「２」が登録されている。
【００５７】
ノード１００ａは、ノード１００ｃからハローパケット４０を受信した場合に、通信経路テーブル１０ａのＧＤに「１００ｇ」、ＬＤに「１００ｃ」を追加登録する。また、ノード１００ａは、ハローパケット４０のＥの値に１を加算した値「３」を通信経路テーブル１０ｙに格納する。ノード１００ｄは、ノード１００ｃからハローパケット４０を受信した場合に、通信経路テーブル１０ｄのＧＤに「１００ｇ」、ＬＤに「１００ｃ」を追加登録する。また、ノード１００ｄは、ハローパケット４０のＥの値に１を加算した値「３」を通信経路テーブル１０ｄに格納する。
【００５８】
ノード１００ｆは、ノード１００ｃからハローパケット４０を受信した場合に、通信経路テーブル１０ｆのＧＤに「１００ｇ」、ＬＤに「１００ｃ」を追加登録する。また、ノード１００ｆは、ハローパケット４０のＥの値に１を加算した値「３」を通信経路テーブル１０ｆに格納する。
【００５９】
図８において、ノード１００ｄは、ハローパケットをノード１００ａ、１００ｂ、１００ｃ、１００ｅ、１００ｆに送信する（ステップＳ５０）。ノード１００ａは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ５１）。ノード１００ｂは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ５２）。ノード１００ｃは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ５３）。ノード１００ｅは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ５４）。ノード１００ｆは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ５５）。
【００６０】
図１４において、ハローパケット５０は、ステップＳ５０において送信されるハローパケットである。通信経路テーブル１０ａ、１０ｂ、１０ｃ、１０ｅ、１０ｆは、ノード１００ａ、１００ｂ、１００ｃ、１００ｅ、１００ｆの通信経路テーブルである。ハローパケット５０のＧＳには「１００ｇ」、ＬＳには「１００ｄ」、Ｅには「２」が登録されている。
【００６１】
ノード１００ａは、ノード１００ｄからハローパケット５０を受信した場合に、通信経路テーブル１０ａのＧＤに「１００ｇ」、ＬＤに「１００ｄ」を追加登録する。また、ノード１００ａは、ハローパケット５０のＥの値に１を加算した値「３」を通信経路テーブル１０ａに格納する。ノード１００ｂは、ノード１００ｄからハローパケット５０を受信した場合に、通信経路テーブル１０ｂのＧＤに「１００ｇ」、ＬＤに「１００ｄ」を追加登録する。また、ノード１００ｂは、ハローパケット５０のＥの値に１を加算した値「３」を通信経路テーブル１０ｂに格納する。
【００６２】
ノード１００ｃは、ノード１００ｄからハローパケット５０を受信した場合に、通信経路テーブル１０ｃのＧＤに「１００ｇ」、ＬＤに「１００ｄ」を追加登録する。また、ノード１００ｃは、ハローパケット５０のＥの値に１を加算した値「３」を通信経路テーブル１０ｃに格納する。ノード１００ｅは、ノード１００ｄからハローパケット５０を受信した場合に、通信経路テーブル１０ｅのＧＤに「１００ｇ」、ＬＤに「１００ｄ」を追加登録する。また、ノード１００ｅは、ハローパケット５０のＥの値に１を加算した値「３」を通信経路テーブル１０ｅに格納する。ノード１００ｆは、ノード１００ｄからハローパケット５０を受信した場合に、通信経路テーブル１０ｆのＧＤに「１００ｇ」、ＬＤに「１００ｄ」を追加登録する。また、ノード１００ｆは、ハローパケット５０のＥの値に１を加算した値「３」を通信経路テーブル１０ｆに格納する。
【００６３】
図８において、ノード１００ｅは、ハローパケットをノード１００ｂ、１００ｄ、１００ｆに送信する（ステップＳ６０）。ノード１００ｂは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ６１）。ノード１００ｄは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ６２）。ノード１００ｆは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ６３）。
【００６４】
図１５において、ハローパケット６０は、ステップＳ６０において送信されるハローパケットである。通信経路テーブル１０ｂ、１０ｃ、１０ｆは、ノード１００ｂ、１００ｃ、１００ｆの通信経路テーブルである。ハローパケット６０のＧＳには「１００ｇ」、ＬＳには「１００ｅ」、Ｅには「３」が登録されている。
【００６５】
ノード１００ｂは、ハローパケット６０を受信した場合に、通信経路テーブル１０ｂのＧＤに「１００ｇ」、ＬＤに「１００ｅ」を追加登録する。また、ノード１００ｂは、ハローパケット６０のＥの値に１を加算した値「４」を通信経路テーブル１０ｂに格納する。ノード１００ｃは、ハローパケット６０を受信した場合に、通信経路テーブル１０ｃのＧＤに「１００ｇ」、ＬＤに「１００ｅ」を追加登録する。また、ノード１００ｃは、ハローパケット６０のＥの値に１を加算した値「４」を通信経路テーブル１０ｃに格納する。ノード１００ｆは、ハローパケット６０を受信した場合に、通信経路テーブル１０ｆのＧＤに「１００ｇ」、ＬＤに「１００ｅ」を追加登録する。また、ノード１００ｆは、ハローパケット６０のＥの値に１を加算した値「４」を通信経路テーブル１０ｆに格納する。
【００６６】
図８において、ノード１００ｙは、ハローパケットをノード１００ｂ、１００ｘ、１００ｚに送信する（ステップＳ７０）。ノード１００ｂは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ７１）。ノード１００ｘは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ７２）。ノード１００ｚは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ７３）。
【００６７】
図１６において、ハローパケット７０は、ステップＳ７０において送信されるハローパケットである。通信経路テーブル１０ｂ、１０ｘ、１０ｚは、ノード１００ｂ、１００ｘ、１００ｚの通信経路テーブルである。ハローパケット７０のＧＳには「１００ｇ」、ＬＳには「１００ｙ」、Ｅには「２」が登録されている。
【００６８】
ノード１００ｂは、ハローパケット７０を受信した場合に、通信経路テーブル１０ｂのＧＤに「１００ｇ」、ＬＤに「１００ｙ」を追加登録する。また、ノード１００ｂは、ハローパケット７０のＥの値に１を加算した値「３」を通信経路テーブル１０ｂに格納する。ノード１００ｘは、ハローパケット７０を受信した場合に、通信経路テーブル１０ｘのＧＤに「１００ｇ」、ＬＤに「１００ｙ」を追加登録する。また、ノード１００ｘは、ハローパケット７０のＥの値に１を加算した値「３」を通信経路テーブル１０ｘに格納する。ノード１００ｚは、ハローパケット７０を受信した場合に、通信経路テーブル１０ｚのＧＤに「１００ｇ」、ＬＤに「１００ｙ」を追加登録する。また、ノード１００ｚは、ハローパケット７０のＥの値に１を加算した値「３」を通信経路テーブル１０ｚに格納する。
【００６９】
図８において、ノード１００ｆは、ハローパケットをノード１００ｃ、１００ｄ、１００ｅに送信する（ステップＳ８０）。ノード１００ｃは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ８１）。ノード１００ｄは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ８２）。ノード１００ｅは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ８３）。
【００７０】
図１７において、ハローパケット８０は、ステップＳ８０において送信されるハローパケットである。通信経路テーブル１０ｃ、１０ｄ、１０ｅは、ノード１００ｃ、１００ｄ、１００ｅの通信経路テーブルである。ハローパケット８０のＧＳには「１００ｇ」、ＬＳには「１００ｆ」、Ｅには「３」が登録されている。
【００７１】
ノード１００ｃは、ハローパケット８０を受信した場合に、通信経路テーブル１０ｃのＧＤに「１００ｇ」、ＬＤに「１００ｆ」を追加登録する。また、ノード１００ｂは、ハローパケット８０のＥの値に１を加算した値「４」を通信経路テーブル１０ｃに格納する。ノード１００ｄは、ハローパケット８０を受信した場合に、通信経路テーブル１０ｄのＧＤに「１００ｇ」、ＬＤに「１００ｆ」を追加登録する。また、ノード１００ｄは、ハローパケット８０のＥの値に１を加算した値「４」を通信経路テーブル１０ｄに格納する。ノード１００ｅは、ハローパケット８０を受信した場合に、通信経路テーブル１０ｅのＧＤに「１００ｇ」、ＬＤに「１００ｆ」を追加登録する。また、ノード１００ｅは、ハローパケット８０のＥの値に１を加算した値「４」を通信経路テーブル１０ｅに格納する。
【００７２】
上記のように、各ノード１００ａ〜１００ｇ、１００ｘ〜１００ｚが図８に示すような処理を実行することで、図９〜図１７に示したように、各通信経路テーブルを更新する。なお、図９〜図１７に示した通信経路テーブルは、図２に示した通信経路テーブル１４０ｂに対応する。
【００７３】
次に、アドホックネットワークのノード１００ａ〜１００ｇ、１００ｘ〜１００ｚが経路構築パケットを送受信して、通信経路テーブルを更新する処理について説明する。図１８〜図２１は、経路構築パケットによる経路構築の処理を説明する図である。
【００７４】
まず、図１８に示すように、経路構築パケットがノード１００ｆから送信され、ノード１００ｄ、１００ａ、１００ｇの順に転送される場合について説明する。また、そのときの、経路構築パケットと各ノードの経路構築パケットの内容を図１９に示す。図１９において、１０ｆ、１０ｄ、１０ａ、１０ｇは、ノード１００ｆ、１００ｄ、１００ａ、１００ｇの通信経路テーブルである。
【００７５】
ノード１００ｆは、例えば、通信経路テーブル１０ｆの２段目を選択する。ノード１００ｆは、経路構築パケット８５ａのＧＤ、ＬＤに通信経路テーブル１０ｆのＧＤ「１００ｇ」、ＬＤ「１００ｄ」を格納する。また、ノード１００ｆは、経路構築パケット８５ａのＧＳ、ＬＳに、自ノードのアドレスを格納する。また、ノード１００ｆは、Ｅに「０」を格納し、ＦＩＤに経路構築パケット８５ａを識別する値「１」を登録する。
【００７６】
ノード１００ｆは、経路構築パケット８５ａをノード１００ｄに送信する。ノード１００ｄは、経路構築パケット８５ａのＧＳ、ＬＳを、通信経路テーブル１０ｄのＧＤ、ＬＤに登録する。また、ノード１００ｄは、経路構築パケット８５ａのＥに１を加算した値「１」を、通信経路テーブル１０ｄのＥに登録する（ステップＳ８５ａ）。
【００７７】
ノード１００ｄは、経路構築パケット８５ｂのＧＤ、ＧＳに経路構築パケット８５ａのＧＤ「１００ｇ」、ＧＳ「１００ｆ」を格納する。また、ノード１００ｄは、経路構築パケット８５ｂのＬＳに自ノードを格納する。ノード１００ｄは、経路構築パケット８５ｂのＬＤに転送先となる「ｌ００ａ」を格納する。また、ノード１００ｄは、先の経路構築パケット８５ａのＥに１を加算した値「１」を、経路構築パケット８５ｂのＥに格納する。また、ノード１００ｄは、ＦＩＤに値「１」を登録する。
【００７８】
ノード１００ｄは、経路構築パケット８５ｂをノード１００ａに送信する。ノード１００ａは、経路構築パケット８５ｂのＧＳ、ＬＳを、通信経路テーブル１０ａのＧＤ、ＬＤに登録する。また、ノード１００ａは、経路構築パケット８５ｂのＥに１を加算した値「２」を、通信経路テーブル１０ａのＥに登録する（ステップＳ８５ｂ）。
【００７９】
ノード１００ａは、経路構築パケット８５ｃのＧＤ、ＧＳに経路探索パケット８５ｂのＧＤ「１００ｇ」、ＧＳ「１００ｆ」を格納する。また、ノード１００ａは、経路構築パケット８５ｃのＬＳに自ノードを格納する。ノード１００ａは、経路構築パケット８５ｃのＬＤに転送先となる「ｌ００ｇ」を格納する。また、ノード１００ａは、先の経路構築パケット８５ａのＥに１を加算した値「２」を、経路構築パケット８５ｃのＥに格納する。
【００８０】
ノード１００ａは、経路構築パケット８５ｃをノード１００ｇに送信する。ノード１００ｇは、経路構築パケット８５ｃのＧＳ、ＬＳを、通信経路テーブル１０ｇのＧＤ、ＬＤに登録する。また、ノード１００ｇは、経路構築パケット８５ｃのＥに１を加算した値「３」を、通信経路テーブル１０ｇのＥに登録する（ステップＳ８５ｃ）。
【００８１】
このように、ステップＳ８５ａ〜８５ｃの処理を実行することにより、ノード１００ｇは、目的地「１００ｆ」に対する通信経路を得ることができる。
【００８２】
続いて、図２０に示すように、経路構築パケットがノード１００ｆから送信され、ノード１００ｅ、１００ｄ、１００ｂ、１００ｇの順に転送される場合について説明する。ただし、ノード１００ｅからノード１００ｂへの経路構築パケットの転送が失敗したために、経路構築パケットは、ノード１００ｄを経由して、ノード１００ｅからノード１００ｂに転送されるものとする。
【００８３】
図２１において、１０ｆ、１０ｅ、１０ｄ、１０ｂ、１０ｇは、ノード１００ｆ、１００ｅ、１００ｄ、１００ｂ、１００ｇの通信経路テーブルである。ノード１００ｆは、例えば、通信経路テーブル１０ｆの３段目を選択する。ノード１００ｆは、経路構築パケット８６ａのＧＤ、ＬＤに通信経路テーブル１０ｆのＧＤ「１００ｇ」、ＬＤ「１００ｅ」を格納する。また、ノード１００ｆは、経路構築パケット８６ａのＧＳ、ＬＳに、自ノードのアドレスを格納する。また、ノード１００ｆは、Ｅに０を格納し、ＦＩＤに経路構築パケット８５ａを識別する値「２」を登録する。
【００８４】
ノード１００ｆは、経路構築パケット８６ａをノード１００ｅに送信する。ノード１００ｅは、経路構築パケット８６ａのＧＳ、ＬＳを、通信経路テーブル１０ｅのＧＤ、ＬＤに登録する。また、ノード１００ｆは、経路構築パケット８６ａのＥに１を加算した値「１」を、通信経路テーブル１０ｅのＥに登録する（ステップＳ８６ａ）。
【００８５】
ノード１００ｅは、経路構築パケット８６ｂのＧＤ、ＧＳに経路構築パケット８６ａのＧＤ「１００ｇ」、ＧＳ「１００ｆ」を格納する。また、ノード１００ｅは、経路構築パケット８６ｂのＬＳに自ノードを格納する。ノード１００ｅは、経路構築パケット８６ｂのＬＤに転送先となる「ｌ００ｂ」を格納する。また、ノード１００ｅは、先の経路構築パケット８６ａのＥに１を加算した値「１」を、経路構築パケット８６ｂのＥに格納する。
【００８６】
ノード１００ｅは、経路構築パケット８６ｂをノード１００ｂに転送するが、転送に失敗する。このように、転送を失敗した場合には、通信経路を切り換える。例えば、ノード１００ｅは、経路構築パケット８６ｂのＬＤを「１００ｄ」に変更した経路構築パケット８６ｃを作成し、経路構築パケット８６ｃを、ノード１００ｄに送信する。
【００８７】
ノード１００ｄは、経路構築パケット８６ｃを受信し、経路構築パケット８６ｃのＧＳ、ＬＳを、通信経路テーブル１０ｄのＧＤ、ＬＤに登録する。また、ノード１００ｄは、経路構築パケット８６ｃのＥに１を加算した値「２」を、通信経路テーブル１０ｄのＥに登録する（ステップＳ８６ｂ）。
【００８８】
ノード１００ｄは、経路構築パケット８６ｄのＧＤ、ＧＳに経路探索パケット８６ｃのＧＤ「１００ｇ」、ＧＳ「１００ｆ」を格納する。また、ノード１００ｄは、経路構築パケット８６ｄのＬＳに自ノードを格納する。ノード１００ｄは、経路構築パケット８６ｃのＬＤに転送先となる「ｌ００ｂ」を格納する。また、ノード１００ｄは、先の経路構築パケット８６ｃのＥに１を加算した値「２」を、経路構築パケット８６ｄのＥに格納する。ノード１００ｄは、経路構築パケット８６ｄを、ノード１００ｂに送信する。
【００８９】
ノード１００ｂは、経路構築パケット８６ｄを受信し、経路構築パケット８６ｄのＧＳ、ＬＳを、通信経路テーブル１０ｂのＧＤ、ＬＤに登録する。また、ノード１００ｂは、経路構築パケット８６ｂのＥに１を加算した値「３」を、通信経路テーブル１０ｂのＥに登録する（ステップＳ８６ｃ）。
【００９０】
ノード１００ｂは、経路構築パケット８６ｅのＧＤ、ＧＳに経路探索パケット８６ｄのＧＤ「１００ｇ」、ＧＳ「１００ｆ」を格納する。また、ノード１００ｂは、経路構築パケット８６ｅのＬＳに自ノードを格納する。ノード１００ｂは、経路構築パケット８６ｅのＬＤに転送先となる「ｌ００ｇ」を格納する。また、ノード１００ｂは、先の経路構築パケット８６ｄのＥに１を加算した値「３」を、経路構築パケット８６ｅのＥに格納する。ノード１００ｂは、経路構築パケット８６ｅを、ノード１００ｇに送信する。
【００９１】
ノード１００ｇは、経路構築パケット８６ｅを受信し、経路構築パケット８６ｅのＧＳ、ＬＳを、通信経路テーブル１０ｇのＧＤ、ＬＤに登録する。また、ノード１００ｇは、経路構築パケット８６ｅのＥに１を加算した値「４」を、通信経路テーブル１０ｇのＥに登録する（ステップＳ８６ｄ）。
【００９２】
このように、ステップＳ８６ａ〜８６ｄの処理を実行することにより、ノード１００ｇは、目的地「１００ｆ」に対する新たな通信経理を得ることができる。
【００９３】
次に、アドホックネットワークのノード１００ａ〜１００ｇ、１００ｘ〜１００ｚが経路探索パケットを送信する処理について説明する。ただし、この経路探索パケットを送信する処理は、図８に示したハローパケットの送受信、図２０に示した経路構築パケットの送受信が行われた後に実行される。
【００９４】
次に、経路探索パケットの転送処理について説明する。図２２〜図２９は、経路探索パケットの転送処理を説明するための図である。ここでは一例として、ノード１００ｇが、経路探索パケットのＧＤにノード１００ｆのアドレスを格納して、経路探索パケットをブロードキャストする場合について説明する。図２２において、ノード１００ｇは、経路探索パケットをブロードキャストし、ノード１００ａ、１００ｂ、１００ｘは、経路探索パケットを受信する（ステップＳ９０）。
【００９５】
ステップＳ９１にて送信される経路探索パケットについて説明する。図２３に示すように、ノード１００ｇは、経路探索パケット９０のＧＳにノード１００ｇのアドレスを格納し、ＧＤにノード１００ｆのアドレスを格納する。また、ノード１００ｇは、経路探索パケット９０の探索範囲に初期値の１を設定し、経路探索パケット９０をブロードキャストする。
【００９６】
図２２において、ノード１００ａは、経路探索パケットをブロードキャストし、ノード１００ｃ、１００ｄは、経路探索パケットを受信する（ステップＳ９１）。
【００９７】
ステップＳ９１にて送信される経路探索パケットについて説明する。図２４に示すように、通信経路テーブル１０ａのＧＤにノード１００ｆのアドレスが含まれている。このため、ノード１００ａは、経路探索パケット９０の探索範囲を初期値の１に設定し、経路探索パケット９０をブロードキャストする。
【００９８】
図２２において、ノード１００ｂは、経路探索パケットをブロードキャストし、ノード１００ｄ、１００ｅ、１００ｙは、経路探索パケットを受信する（ステップＳ９２）。
【００９９】
ステップＳ９２にて送信される経路探索パケットについて説明する。図２５に示すように、通信経路テーブル１０ｂのＧＤにノード１００ｆのアドレスが含まれている。このため、ノード１００ｂは、経路探索パケット９０の探索範囲を初期値の１に設定し、経路探索パケット９０をブロードキャストする。
【０１００】
図２２において、ノード１００ｘは、経路探索パケットをブロードキャストし、ノード１００ｙは、経路探索パケットを受信する（ステップＳ９３）。
【０１０１】
ステップＳ９３にて送信される経路探索パケットについて説明する。図２６に示すように、通信経路テーブル１０ｘのＧＤにノード１００ｆのアドレスが含まれていない。このため、ノード１００ｘは、経路探索パケットの探索範囲を１減算する。探索範囲の値が０以上であるため、ノード１００ｘは、経路探索パケット９０をブロードキャストする。
【０１０２】
また、図２６に示すように、通信経路テーブル１０ｙのＧＤにノード１００ｆのアドレスが含まれていない。このため、ノード１００ｙは、経路検索パケットの探索範囲を１減算する。探索範囲の値が０未満となるため、ノード１００ｆは、経路検索パケット９０の転送を停止する。
【０１０３】
図２２において、ノード１００ｙは、ノード１００ｂから受信した経路探索パケットをブロードキャストし、ノード１００ｚは、経路探索パケットを受信する（ステップＳ９４）。
【０１０４】
ステップＳ９４にて送信される経路探索パケットについて説明する。図２７に示すように、通信経路テーブル１０ｙのＧＤにノード１００ｆのアドレスが含まれていない。このため、ノード１００ｙは、経路探索パケットの探索範囲を１減算する。探索範囲の値が０以上であるため、ノード１００ｙは、経路探索パケット９０をブロードキャストする。
【０１０５】
また、図２７に示すように、通信経路テーブル１０ｚのＧＤにノード１００ｆのアドレスが含まれていない。このため、ノード１００ｚは、経路探索パケットの探索範囲を１減算する。探索範囲の値が０未満となるため、ノード１００ｚは、経路探索パケットの転送を停止する。
【０１０６】
図２２において、ノード１００ｄは、ノード１００ａから受信した経路探索パケットをブロードキャストし、ノード１００ｃ、１００ｅ、１００ｆは、経路探索パケットを受信する（ステップＳ９５）。
【０１０７】
ステップＳ９５にて送信される経路探索パケットについて説明する。図２８に示すように、通信経路テーブル１０ｄのＧＤにノード１００ｆのアドレスが含まれている。このため、ノード１００ｄは、経路検索パケット９０の探索範囲を初期値の１に設定し、経路探索パケット９０をブロードキャストする。
【０１０８】
図２２において、ノード１００ｃは、ノード１００ｄから受信した経路探索パケットをブロードキャストし、ノード１００ｆは、経路探索パケットを受信する。また、ノード１００ｅは、ノード１００ｄから受信した経路探索パケットをブロードキャストし、ノード１００ｆは、経路探索パケットを受信する（ステップＳ９６）。
【０１０９】
ステップＳ９６にて送信される経路探索パケットについて説明する。図２９に示すように、通信経路テーブル１０ｅのＧＤにノード１００ｆのアドレスが含まれている。このため、ノード１００ｅは、経路検索パケット９０の探索範囲を初期値の１に設定し、経路探索パケット９０をブロードキャストする。
【０１１０】
また、図２９に示すように、通信経路テーブル１０ｃのＧＤにノード１００ｆのアドレスが含まれていない。このため、ノード１００ｃは、経路探索パケットの探索範囲を１減算する。探索範囲の値が０以上であるため、ノード１００ｃは、経路探索パケット９０をブロードキャストする。
【０１１１】
ステップＳ９６において、ノード１００ｆは、自ノード宛の経路検索パケットを受信する。この場合には、ノード１００ｆは、ノード１００ｇ宛の応答パケットを送信する。
【０１１２】
次に、ノード１００がハローパケットを受信した場合の処理手順について説明する。図３０は、ハローパケット受信処理の処理手順を示すフローチャートである。図３０に示す処理は、例えば、ハローパケットを受信したことを契機に実行される。図３０に示す処理は、ハローパケット制御部１５０ａの処理に対応する。
【０１１３】
図３０に示すように、ノード１００は、ハローパケットを受信していない場合には（ステップＳ１０１，Ｎｏ）、処理を終了する。一方、ノード１００は、ハローパケットを受信した場合には（ステップＳ１０１，Ｙｅｓ）、ハローパケットに情報が含まれるか否かを判定する（ステップＳ１０２）。
【０１１４】
ノード１００は、ハローパケットに情報が含まれない場合には（ステップＳ１０２，Ｎｏ）、処理を終了する。一方、ノード１００は、ハローパケットに情報が含まれている場合には（ステップＳ１０２，Ｙｅｓ）、ＧＳまたはＬＳが自アドレスであるか否かを判定する（ステップＳ１０３）。
【０１１５】
ノード１００は、ＧＳまたはＬＳが自アドレスの場合には（ステップＳ１０３，Ｙｅｓ）、処理を終了する。一方、ノード１００は、ＧＳまたはＬＳが自アドレスではない場合には（ステップＳ１０３，Ｎｏ）、ワークテーブル１４０ａにレコードを新規作成する（ステップＳ１０４）。
【０１１６】
ノード１００は、ワークテーブル１４０ａのＧＤにハローパケットのＧＳを設定し（ステップＳ１０５）、ワークテーブル１４０ａのＬＤにハローパケットのＬＳを設定する（ステップＳ１０６）。ノード１００は、ワークテーブル１４０ａのＥにハローパケットのＥに１を加算した値を設定する（ステップＳ１０７）。
【０１１７】
ノード１００は、通信経路テーブル１４０ｂに同一のＧＳおよびＬＤのレコードが存在しない場合には（ステップＳ１０８，Ｎｏ）、ワークテーブルに作成したレコードを通信経路テーブルに新規追加し（ステップＳ１１０）、処理を終了する。一方、ノード１００は、通信経路テーブル１４０ｂに同一のＧＳおよびＬＤのレコードが存在しない場合には（ステップＳ１０８，Ｎｏ）、ワークテーブル１４０ａに作成したレコードを通信経路テーブル１４０ｂに新規追加する（ステップＳ１１０）。一方、ノード１００は、通信経路テーブル１４０ｂに同一のＧＳおよびＬＤのレコードが存在する場合には（ステップＳ１０８，Ｙｅｓ）、上書きする（ステップＳ１０９）。
【０１１８】
次に、ノード１００がハローパケットを送信する場合の処理手順について説明する。図３１は、ハローパケット送信処理の処理手順を示すフローチャートである。図３１に示す処理は、例えば、クロックイベントが発生したことを契機として実行される。図３１に示す処理は、ハローパケット制御部１５０ａの処理に対応する。
【０１１９】
図３１に示すように、ノード１００は、クロックイベントが発生していない場合には（ステップＳ１５０，Ｎｏ）、処理を終了する。一方、ノード１００は、クロックイベントが発生した場合には（ステップＳ１５０，Ｙｅｓ）、通信経路テーブル１４０ｂに情報が存在するか否かを判定する（ステップＳ１５１）。
【０１２０】
ノード１００は、通信経路テーブルに情報が存在しない場合には（ステップＳ１５１，Ｎｏ）、処理を終了する。一方、ノード１００は、通信経路テーブルに情報が存在する場合には（ステップＳ１５１，Ｙｅｓ）、通信経路テーブル１４０ｂからＧＳがＧＷのアドレスとなるレコードを抽出する（ステップＳ１５２）。ＧＷをノード１００ｇとすると、ノード１００は、ＧＳがノード１００ｇのアドレスとなるレコードを抽出する。
【０１２１】
ノード１００は、ハローパケットのＧＳに通信経路テーブル１４０ｂのＧＤを設定し（ステップＳ１５３）、ハローパケットのＬＳに通信経路テーブル１４０ｂのＬＤを設定する（ステップＳ１５４）。
【０１２２】
ノード１００は、ハローパケットのＥに通信経路テーブルのＥを設定し（ステップＳ１５５）、ハローパケットを送信する（ステップＳ１５６）。
【０１２３】
次に、ノード１００が、下り経路を構築する場合の経路構築パケットの送信処理について説明する。図３２は、経路構築パケットの送信処理の処理手順を示すフローチャートである。図３２に示す処理は、例えば、クロックイベントが発生したことを契機にして実行される。図３２に示す処理は、下り経路構築部１５０ｂの処理に対応する。
【０１２４】
図３２に示すように、ノード１００は、通信経路テーブル１４０ｂに、所望のＧＤが存在しない場合には（ステップＳ２０１，Ｎｏ）、処理を終了する。一方、ノード１００は、所望のＧＤが存在する場合には（ステップＳ２０１，Ｙｅｓ）、データ管理テーブル１４０ｃに基づいて、通信経路テーブル１４０ｂに送信可能な転送先が存在するか否かを判定する（ステップＳ２０２）。
【０１２５】
ノード１００は、データ管理テーブル１４０ｃに基づいて、通信経路テーブル１４０ｂに送信可能な転送先が存在しない場合には（ステップＳ２０２，Ｎｏ）、処理を終了する。一方、ノード１００は、通信経路テーブル１４０ｂに送信可能な転送先が存在する場合には（ステップＳ２０２，Ｙｅｓ）、通信経路テーブル内の未送信の上位レコードを抽出する（ステップＳ２０３）。
【０１２６】
ノード１００は、自ノードがＧＳではない場合には（ステップＳ２０４，Ｎｏ）、レコードのＧＤを、経路構築パケットのＧＤに設定する（ステップＳ２０５）。ノード１００は、レコードのＧＳを、経路構築パケットのＧＳに設定し（ステップＳ２０６）、レコードのＥを経路構築パケットのＥに設定し（ステップＳ２０７）、ステップＳ２１１に移行する。
【０１２７】
一方、ノード１００は、自ノードがＧＳの場合には（ステップＳ２０４，Ｙｅｓ）、経路構築パケットのＧＤに目的地のノードのアドレスを設定する（ステップＳ２０８）。ノード１００は、経路構築パケットのＧＳに自ノードのアドレスを設定し（ステップＳ２０９）、経路構築パケットのＥに通信経路テーブル１４０ｂの上位Ｅを設定する（ステップＳ２１０）。
【０１２８】
ノード１００は、経路構築パケットのＬＤに通信経路テーブル１４０ｂの上位ＬＤを設定し（ステップＳ２１１）、経路構築パケットのＦＩＤにユニークな数値を設定する（ステップＳ２１２）。ノード１００は、経路構築パケットのＬＳに自ノードのアドレスを設定し（ステップＳ２１３）、経路構築パケットの内容をデータ管理テーブル１４０ｃに記録し（ステップＳ２１４）、経路構築パケットを送信する（ステップＳ２１５）。
【０１２９】
次に、ノード１００が、下り経路を構築する場合の経路構築パケットの受信処理について説明する。図３３は、経路構築パケットの受信処理の処理手順を示すフローチャートである。図３３に示す処理は、例えば、経路構築パケットを受信したことを契機にして実行される。図３３に示す処理は、下り経路構築部１５０ｂの処理に対応する。
【０１３０】
図３３に示すように、ノード１００は、経路構築パケットを受信していない場合には（ステップＳ２５０，Ｎｏ）、処理を終了する。一方、ノード１００は、経路構築パケットを受信した場合には（ステップＳ２５０，Ｙｅｓ）、ワークテーブル１４０ａにレコードを新規作成する（ステップＳ２５１）。
【０１３１】
ノード１００は、ワークテーブル１４０ａのＧＤに経路構築パケットのＧＳを設定し（ステップＳ２５２）、ワークテーブル１４０ａのＬＤに経路構築パケットのＬＳを設定する（ステップＳ２５３）。
【０１３２】
ノード１００は、ワークテーブル１４０ａのＥに、経路構築パケットのＥに１を加算した値を設定する（ステップ２５４）。ノード１００は、通信経路テーブル１４０ｂに同一のＧＳおよびＬＤのレコードが存在する場合には（ステップＳ２５５，Ｙｅｓ）、上書きする（ステップＳ２５６）。一方、ノード１００は、通信経路テーブル１４０ｂに同一のＧＳおよびＬＤのレコードが存在しない場合には（ステップＳ２５５，Ｎｏ）、ワークテーブル１４０ａに作成したレコードを通信経路テーブルに新規追加する（ステップＳ２５７）。
【０１３３】
次に、ノード１００が、経路探索パケットに対する処理について説明する。図３４は、経路探索パケットの処理手順を示すフローチャートである。図３４に示す処理は、例えば、経路探索要求を受け付けたことまたは、経路探索パケットを受信したことを契機に実行される。図３４に示す処理は、経路探索パケット送信部１５０ｃ、経路探索パケット受信部１５０ｄの処理に対応する。
【０１３４】
図３４に示すように、経路探索要求があった場合には（ステップＳ３０１，Ｙｅｓ）、経路探索パケットのＧＳに自ノードのアドレスを設定する（ステップＳ３０２）。ノード１００は、経路探索パケットのＧＤに目的ノードを設定する（ステップＳ３０３）。
【０１３５】
ノード１００は、経路探索パケットの探索範囲に、探索範囲の初期値を設定する（ステップＳ３０４）。例えば、ノード１００は、探索範囲の初期値として、１を設定する。ノード１００は、探索範囲が０以上の場合には（ステップＳ３０５，Ｙｅｓ）、経路探索パケットを送信する（ステップＳ３０６）。一方、ノード１００は、探索範囲が０未満の場合には（ステップＳ３０５，Ｎｏ）、処理を終了する。
【０１３６】
ところで、ノード１００は、経路探索要求がない場合には（ステップＳ３０１，Ｎｏ）、経路探索パケットの転送を行うと判定する（ステップＳ３０７）。ノード１００は、経路探索パケットのＧＤとＧＳをそのまま流用し（ステップＳ３０８）、通信経路テーブル１４０ｂ内にＧＤが存在する場合には（ステップＳ３０９，Ｙｅｓ）、ステップＳ３０４に移行する。
【０１３７】
一方、ノード１００は、通信経路テーブル１４０ｂ内にＧＤが存在しない場合には（ステップＳ３０９，Ｎｏ）、経路探索パケットの探索範囲に、既存の探索範囲値から１を減算した値を設定し（ステップＳ３１０）、ステップＳ３０５に移行する。
【０１３８】
次に、本実施例にかかるノード１００の効果について説明する。ノード１００は、通信経路探索パケットを受信した場合に、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されているか否かを判定する。ノード１００は、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されている場合には、通信経路探索パケットをブロードキャストする。これに対して、ノード１００は、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されていない場合には、通信経路端末パケットの探索範囲の値を減算する。そして、ノード１００は、減算した探索範囲の値が０以上の場合に、通信経路探索パケットをブロードキャストする。このため、通信経路探索パケットは、目的地以外の方向には転送されず、目的地の方向に転送される。したがって、ノード１００は、通信経路を構築する場合に、経路探索パケットの伝送範囲を最適に絞り込むことができる。
【０１３９】
また、ノード１００は、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されている場合には、通信経路探索パケットの探索範囲を初期値に設定し直す。このため、目的地のノードに至る通信経路が迂回経路しか存在しない場合でも、通信経路探索パケットを到達させることができる。
【０１４０】
また、ノード１００は、通信経路探索パケットを送信した後に、通信経路探索パケットの目的地のノードから応答を受信しない場合には、通信経路探索パケットの探索範囲を所定の値増やして、再送する。このため、通信経路探索パケットをより確実に目的地のノードに到達させることができる。
【０１４１】
ところで、ノード１００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、ノード１００の具体的形態は図示のものに限られず、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図２の各処理部１５０ａ〜１５０ｄの機能をまとめてもよい。
【０１４２】
上記実施例に示したノード１００の機能は、既知のＰＣ（Personal Computer）またはＰＤＡ（Personal Digital Assistants）などの情報処理装置に、ノードに対応する各機能を搭載することによって実現することもできる。図３５は、ノードを構成するコンピュータのハードウェア構成を示す図である。
【０１４３】
図３５に示すように、このコンピュータ３００は、各種演算処理を実行するＣＰＵ３０１と、ユーザからのデータの入力を受け付ける入力装置３０２と、ディスプレイ３０３とを有する。また、コンピュータ３００は、記憶媒体からプログラム等を読み取る読み取り装置３０４と、他の装置と接続するためのインターフェース装置３０５とを有する。また、コンピュータ３００は、他の装置と無線により接続する無線通信装置３０６と、各種情報を一時記憶するＲＡＭ３０７と、ハードディスク装置３０８とを有する。各装置３０１〜３０８は、バス３０９に接続される。
【０１４４】
ハードディスク装置３０８には、判定プログラム、送信制御プログラムなどの各種のプログラムが記憶される。
【０１４５】
ＣＰＵ３０１は、ハードディスク装置３０８に記憶された各プログラムを読み出して、ＲＡＭ３０７に展開し、各種の処理を行う。また、これらのプログラムは、コンピュータを図３の判定部１５１、送信制御部１５２として機能させることができる。
【０１４６】
なお、上記のプログラムは、必ずしもハードディスク装置３０８に格納されている必要はない。例えば、ＣＤ−ＲＯＭ等の記憶媒体に記憶されたプログラムを、コンピュータ３００が読み出して実行するようにしてもよい。また、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等に接続された記憶装置に、各プログラムを記憶させておいてもよい。この場合、コンピュータ３００がこれらから各プログラムを読み出して実行するようにしてもよい。
【符号の説明】
【０１４７】
１００ａ、１００ｂ、１００ｃ、１００ｄ、１００ｅ、１００ｆ、１００ｇ、１００ｘ、１００ｙ、１００ｚ ノード
１１０ 無線通信部
１２０ 入力部
１３０ 表示部
１４０ 記憶部
１５０ 制御部
【技術分野】
【０００１】
本発明は、無線通信端末等に関する。
【背景技術】
【０００２】
近年、複数の無線通信端末が自律分散的に相互接続するアドホックネットワークの研究が進められている。アドホックネットワークには、例えば、スマートネットなどの固定形マルチホップネットワークが含まれる。以下では、無線通信端末をノードと表記する。アドホックネットワークでは、アクセスポイントは設定されず、各ノードが、隣接ノードから受信したパケットを通信経路に基づき他のノードに転送することで、パケットを目的地に送信する。
【０００３】
アドホックネットワークの各ノードは、ハローパケット（Hello Packet）を送受信することで、通信経路を構築することができる（例えば特許文献１参照）。ここで、ゲートウェイ（Ｇａｔｅｗａｙ：以下適宜「ＧＷ」と表す）から各ノードへの通信経路（下り方向）を構築するに際して、以下の前提条件１、２のもと経路構築を行うことを考えてみる。
【０００４】
前提条件１は、上り方向の通信経路が作成済みという条件である。上り方向は、ノードからＧＷに至る方向である。上り方向の通信経路が作成済みの場合には、目的地「ＧＷ」にパケットを送信するための転送先のノードが１つ以上通信経路に登録されている。なお、通信経路の作成は先の特許文献１に記載された技術を用いることができる。
【０００５】
前提条件２は、各ノードがＧＷに複数回パケットを送信していて、その上り方向の通信経路を利用して下り方向の通信を行うために、ＧＷの通信経路上の中継ノードには、下り方向の通信経路用のテーブルに目的地となるノード毎に転送先のノードが登録されているという条件である。ただし、ＧＷの通信経路の目的地のノードは、ＧＷにパケットを送信した送信元のノードとする。
【０００６】
上記前提条件１、２においては、経路候補数が限られ、また、ネットワークの変化に対する追随性が問題となる。そこで、送信要求が発生して後でルーティングテーブルを動的に作成するReactive方式を利用することが解決策として考えられる。Reactive方式では、送信要求が発生すると、宛て先を探すためのリクエストパケットを自己の近隣ノードに対して一斉送信（フラッディング）する。例えば、ＧＷは、通信経路に含まれるノードを目的地に設定した経路探索パケットを全方位にブロードキャストする。ＧＷは、該経路探索パケットを受信した目的地のノードからの応答を受信し、目的地のノードに至る複数の通信経路を作成する。このように、目的地のノードに至る複数の通信経路を有していると、ネットワークの変化により、ある通信経路が利用できなくなっても、他の通信経路を利用することで、目的地のノードにパケットを送信することができる。
【０００７】
なお、経路探索パケットを全方位にブロードキャストすると、ネットワーク全体にかかる負荷が大きくなるため、経路探索パケットのホップ数に制限をかけるという技術が存在する（例えば特許文献２参照）。探索要求パケットのホップ数に制限をかけることで、経路探索パケットの伝搬範囲が絞り込まれ、ネットワーク全体にかかる負荷を抑えることができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００９−２６７５３２号公報
【特許文献２】特開２００７−１８４８２７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上述した従来技術では、通信経路を構築する場合に、経路探索パケットの伝送範囲を最適に絞り込むことができないという問題があった。
【００１０】
たとえば、従来のReactive方式では、経路探索パケットがＧＷを中心に円状に広がっていくため、目的地のノードとは違う方向にも経路探索パケットが伝送されてしまう。また、目的地のノードに至る通信経路が迂回経路しか存在しない場合には、経路探索パケットの伝送範囲を超えてしまい、経路探索パケットが目的地のノードに届かず、目的地のノードに至る通信経路を構築することができない場合があった。
【００１１】
開示の技術は、上記に鑑みてなされたものであって、通信経路を構築する場合に、経路探索パケットの伝送範囲を最適に絞り込むことができる無線通信端末および経路構築方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
開示の無線通信端末は、判定部と送信制御部とを有する。判定部は、探索対象となる無線通信端末の情報と探索範囲を示す値とを有するパケットを受信した場合に、目的地の経路を含む通信経路テーブルを参照し、該通信経路テーブルの目的地に、探索対象となる無線通信端末が含まれているか否かを判定する。送信制御部は、判定部の判定結果に基づいて、通信経路テーブルの目的地に、探索対象となる無線通信端末が含まれている場合には、パケットを隣接する無線通信端末に送信する。一方、送信制御部は、通信経路テーブルの目的地に、探索対象となる無線通信端末が含まれていない場合には、探索範囲を示す値から所定値を減算し、該探索範囲を示す値が所定の閾値以上の場合には、パケットを隣接する無線通信端末に送信する。
【発明の効果】
【００１３】
開示の無線通信端末によれば、通信経路を構築する場合に、経路探索パケットの伝送範囲を最適に絞り込むことができるという効果を奏する。
【図面の簡単な説明】
【００１４】
【図１】図１は、アドホックネットワークの構成を示す図である。
【図２】図２は、ノードの構成を示す図である。
【図３】図３は、ハローパケットのデータ構造の一例を示す図である。
【図４】図４は、ワークテーブルのデータ構造の一例を示す図である。
【図５】図５は、通信経路テーブルのデータ構造の一例を示す図である。
【図６】図６は、経路構築パケットのデータ構造の一例を示す図である。
【図７】図７は、経路探索パケットのデータ構造の一例を示す図である。
【図８】図８は、ハローパケットによる経路構築の処理手順を示す図である。
【図９】図９は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（１）である。
【図１０】図１０は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（２）である。
【図１１】図１１は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（３）である。
【図１２】図１２は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（４）である。
【図１３】図１３は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（５）である。
【図１４】図１４は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（６）である。
【図１５】図１５は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（７）である。
【図１６】図１６は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（８）である。
【図１７】図１７は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図（９）である。
【図１８】図１８は、経路構築パケットによる経路構築の処理を説明する図（１）である。
【図１９】図１９は、経路構築パケットによる経路構築の処理を説明する図（２）である。
【図２０】図２０は、経路構築パケットによる経路構築の処理を説明する図（３）である。
【図２１】図２１は、経路構築パケットによる経路構築の処理を説明する図（４）である。
【図２２】図２２は、経路探索パケットの転送処理を説明するための図（１）である。
【図２３】図２３は、経路探索パケットの転送処理を説明するための図（２）である。
【図２４】図２４は、経路探索パケットの転送処理を説明するための図（３）である。
【図２５】図２５は、経路探索パケットの転送処理を説明するための図（４）である。
【図２６】図２６は、経路探索パケットの転送処理を説明するための図（５）である。
【図２７】図２７は、経路探索パケットの転送処理を説明するための図（６）である。
【図２８】図２８は、経路探索パケットの転送処理を説明するための図（７）である。
【図２９】図２９は、経路探索パケットの転送処理を説明するための図（８）である。
【図３０】図３０は、ハローパケット受信処理の処理手順を示すフローチャートである。
【図３１】図３１は、ハローパケット送信処理の処理手順を示すフローチャートである。
【図３２】図３２は、経路構築パケットの送信処理の処理手順を示すフローチャートである。
【図３３】図３３は、経路構築パケットの受信処理の処理手順を示すフローチャートである。
【図３４】図３４は、経路探索パケットの処理手順を示すフローチャートである。
【図３５】図３５は、ノードを構成するコンピュータのハードウェア構成を示す図である。
【発明を実施するための形態】
【００１５】
以下に、本願の開示する無線通信端末および経路構築方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００１６】
本実施例にかかるアドホックネットワークの構成について説明する。図１は、アドホックネットワークの構成を示す図である。図１に示すように、このアドホックネットワークは、ノード１００ａ〜１００ｇ、１００ｘ〜１００ｚを有する。ノード１００ａ〜１００ｇ、１００ｘ〜１００ｚは、無線通信端末の一例である。また、ノード１００ｇは、ＧＷ（Gate Way）に対応する。
【００１７】
ノード１００ａ〜１００ｇ、１００ｘ〜１００ｚは、隣接のノードと無線により接続する。例えば、ノード１００ｇは、ノード１００ａ、１００ｂ、１００ｘに接続される。ノード１００ａは、ノード１００ｇ、１００ｃ、１００ｄに接続される。ノード１００ｂは、ノード１００ｇ、１００ｄ、１００ｅ、１００ｙに接続される。ノード１００ｃは、ノード１００ａ、１００ｄ、１００ｆに接続される。ノード１００ｄは、ノード１００ａ、１００ｂ、１００ｃ、１００ｅ、１００ｆに接続される。１００ｅは、ノード１００ｂ、１００ｄ、１００ｆに接続される。ノード１００ｆは、ノード１００ｃ、１００ｄ、１００ｅに接続される。ノード１００ｘは、ノード１００ｇ、１００ｂ、１００ｙに接続される。ノード１００ｙは、ノード１００ｂ、１００ｘ、１００ｚに接続される。ノード１００ｚは、ノード１００ｙに接続される。本実施例では、ノード１００ａ〜１００ｇ、１００ｘ〜１００ｙを総称する場合、ノード１００と表記する。
【００１８】
次に、本実施例にかかるノード１００の構成について説明する。図２は、ノードの構成を示す図である。図２に示すように、このノード１００は、無線通信部１１０、入力部１２０、表示部１３０、記憶部１４０、制御部１５０を有する。
【００１９】
無線通信部１１０は、隣接するノードとの間で無線によりデータ通信する装置である。例えば、無線通信部１１０は、無線リンクモジュールなどに対応する。制御部１５０は、この無線通信部１１０を介して、隣接するノードとの間でハローパケット等を送受信する。
【００２０】
入力部１２０は、各種の情報をノード１００に入力するための入力装置である。例えば、入力部１２０は、キーボード、マウス、タッチパネル等に対応する。表示部１２０は、各種の情報を表示する表示装置である。例えば、表示部１３０は、ディスプレイ、タッチパネル等に対応する。
【００２１】
記憶部１４０は、例えば、ワークテーブル１４０ａ、通信経路テーブル１４０ｂ、データ管理テーブル１４０ｃを記憶する。この記憶部１４０は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【００２２】
ワークテーブル１４０ａは、ハローパケットの情報を一時的に保持するテーブルである。ここで、ハローパケットのデータ構造の一例と、ワークテーブル１４０ａのデータ構造の一例について説明する。
【００２３】
図３は、ハローパケットのデータ構造の一例を示す図である。図３に示すように、ハローパケットは、ＧＳ、ＬＳ、Ｅを有する。このうち、ＧＳには、目的地のノードのアドレスが格納される。例えば、ＧＳには、ＧＷとなるノード１００ｇのアドレスが格納される。ＬＳには、ハローパケットを転送したノードのアドレスが格納される。Ｅには、例えば、ハローパケットのホップ数が格納される。
【００２４】
図４は、ワークテーブルのデータ構造の一例を示す図である。図４に示すように、このワークテーブル１４０ａは、ＧＤ、ＬＤ、Ｅを有する。ＧＤには、目的地のノードのアドレスが格納される。ＬＤには、転送先のアドレスが格納される。Ｅには、例えば、ハローパケットのホップ数が格納される。図３に示したハローパケットのＧＳ、ＬＳ、Ｅが、それぞれ、図４のワークテーブル１４０ａのＧＤ、ＬＤ、Ｅに格納される。
【００２５】
通信経路テーブル１４０ｂは、目的地となるノードにパケットを送信する場合に、どの隣接ノードにパケットを転送すればよいかを示すものである。図５は、通信経路テーブルのデータ構造の一例を示す図である。図５のＧＤ、ＬＤ、Ｅに関する説明は、上記図４のＧＤ、ＬＤ、Ｅに関する説明と同様である。図５に示すように、例えば、通信経路テーブル１４０ｂには、目的地のノード「ＧＤ」に対する複数の通信経路が記憶されている。この通信経路テーブル１４０ｂでは、ノード１００ｇにパケットを送信する場合には、ノード１００ａ〜１００ｅの何れかのノードにパケットを転送すればよいことを示している。図５では、説明の便宜上、ノードの名称を示しているが、ノードのアドレスが登録されてもよい。
【００２６】
データ管理テーブル１４０ｃは、パケットの送信履歴を記憶するテーブルである。このデータ管理テーブル１４０ｃは、後述の下り経路構築部１５０ｂにより利用される。
【００２７】
制御部１５０は、ハローパケット制御部１５０ａ、下り経路構築部１５０ｂ、経路探索パケット送信部１５０ｃ、経路探索パケット受信部１５０ｄを有する。制御部１５０は、ＡＳＩＣ（Application Specific Integrated Circuit）や、ＦＰＧＡ（Field Programmable Gate Array）などの集積装置に対応する。また、制御部１５０は、例えば、ＣＰＵやＭＰＵ（Micro Processing Unit）等の電子回路に対応する。
【００２８】
ハローパケット制御部１５０ａは、隣接のノードとハローパケットを送受信することで、通信経路テーブル１４０ｂに目的地「ＧＤ」、転送先「ＬＤ」、ホップ数「Ｅ」の関係を登録する処理部である。
【００２９】
ハローパケット制御部１５０ａが、ハローパケットを受信した場合の処理について説明する。ハローパケット制御部１５０ａは、ハローパケットのＧＳ、ＬＳの情報をワークテーブル１４０ａのＧＤ、ＬＤに格納する。また、ハローパケット制御部１５０ａは、ハローパケットのＥの値に１を加算したものを、ワークテーブル１４０ａのＥに格納する。そして、ハローパケット制御部１５０ａは、ワークテーブル１４０ａのレコードを通信経路テーブル１４０ｂに登録する。
【００３０】
ハローパケット制御部１５０ａが、ハローパケットを送信する場合の処理について説明する。例えば、ハローパケット制御部１５０ａは、クロックイベントが発生したことを契機にして、ハローパケットを生成する。
【００３１】
ハローパケット制御部１５０ａは、ハローパケットのＧＳに、通信経路テーブル１４０ｂのＧＳの情報を格納する。例えば、ハローパケット制御部１５０ａは、ゲートウェイに対応するノード１００ｇのアドレスをハローパケットのＧＳに格納してもよい。ハローパケット制御部１５０ａは、ハローパケットのＬＳに自ノード１００のアドレスを格納する。ハローパケット制御部１５０ａは、ハローパケットのＥに、通信経路テーブル１４０ｂのＥを格納する。
【００３２】
下り経路構築部１５０ｂは、上り方向の目的地のノードに対して、パケットを送信し、目的地に至る他のノードの下り経路構築部１５０ｂと協働して、下り方向の経路を構築する処理部である。下り方向の経路を構築することを目的として上り方向の目的地のノードに送信するパケットを、便宜上、経路構築パケットと表記する。
【００３３】
図６は、経路構築パケットのデータ構造の一例を示す図である。図６に示すように、この経路構築パケットは、ＧＤ、ＧＳ、ＬＳ、ＬＤ、Ｅ、ＦＩＤを有する。このうち、ＧＤは目的地を示すものであり、通信経路テーブル１４０ｂのＧＤの情報が格納される。ＧＳには、経路構築パケットの送信元のアドレスが格納される。ＬＳには、経路構築パケットの転送元のノードのアドレスが格納される。ＬＤには、経路構築パケットの転送先となる隣接ノードのアドレスが格納される。Ｅには、ホップ数が格納される。ＦＩＤには、経路構築パケットを一意に識別する値が格納される。下り経路構築部１５０ｂは、送信した経路構築パケットの情報を、送信履歴としてデータ管理テーブル１４０ｃに格納する。
【００３４】
経路探索パケット送信部１５０ｃは、ある目的地のノードに至る経路情報を増やすことを目的として、目的地のノードに経路探索パケットを送信する処理部である。図７は、経路探索パケットのデータ構造の一例を示す図である。図７に示すように、経路探索パケットは、ＧＳ、ＧＤ、探索範囲を有する。ＧＳには、経路検索パケットの送信元のノードのアドレスが格納される。ＧＤには、目的地のノードのアドレスが格納される。探索範囲には、経路探索パケットを転送するか否かを示す値が格納される。経路探索パケット送信部１５０ｃは、探索範囲に所定の数値を代入し、経路検索パケットをブロードキャストする。
【００３５】
経路探索パケット送信部１５０ｃは、経路探索パケットの目的地のノードから応答を受信しない場合には、探索範囲に代入する値を増やして、経路探索パケットを再送する。例えば、経路探索パケット送信部１５０ｃは、経路探索パケットをブロードキャストしてから、所定の時間が経過する間に応答を受信しない場合に、経路探索パケットを再送する。
【００３６】
経路探索パケット受信部１５０ｄは、経路探索パケットを受信した場合に、経路探索パケットの探索範囲に基づいて、経路探索パケットを送信する処理部である。経路探索パケット受信部１５０ｄは、判定部１５１と、送信制御部１５２を有する。
【００３７】
判定部１５１は、経路探索パケットのＧＤに格納されたノードが、通信経路テーブル１４０ｂのＧＤに含まれているか否かを判定し、判定結果を送信制御部１５２に出力する。
【００３８】
送信制御部１５２は、判定部１５１の判定結果に基づいて、経路探索パケットの送信制御を行う処理部である。
【００３９】
判定部１５１の判定結果に、経路探索パケットのＧＤに格納されたノードが、通信経路テーブル１４０ｂのＧＤに含まれている旨の情報が含まれている場合の送信制御部１５２の処理について説明する。この場合には、送信制御部１５２は、経路探索パケットの探索範囲の値をもとの初期値に戻し、経路探索パケットをブロードキャストする。
【００４０】
これに対して、判定部１５１の判定結果に、経路探索パケットのＧＤに格納されたノードが、通信経路テーブル１４０ｂのＧＤに含まれていない旨の情報が含まれている場合の送信制御部１５２の処理について説明する。この場合には、送信制御部１５２は、経路探索パケットの探索範囲の値から１を減算する。そして、送信制御部１５２は、減算した探索範囲の値が所定の閾値より大きい場合に、経路検索パケットをブロードキャストする。一方、送信制御部１５２は、減算した探索範囲の値が所定の閾値以下の場合には、経路検索パケットをブロードキャストする。例えば、探索範囲の値と比較される所定の閾値を０とする。
【００４１】
ところで、送信制御部１５２は、経路探索パケットのＧＤが、自ノードの場合には、経路探索パケットの送信元のノードに応答データを送信してもよい。
【００４２】
次に、アドホックネットワークのノード１００ａ〜１００ｇ、１００ｘ〜１００ｚがハローパケットを送受信して、通信経路テーブルを更新する処理について説明する。図８は、ハローパケットによる経路構築の処理手順を示す図である。また、図９〜図１７は、ハローパケットのデータ構造と各ノードの通信経路テーブルのデータ構造の一例を示す図である。
【００４３】
図８において、ノード１００ｇはハローパケットを、ノード１００ａ、１００ｂ、１００ｘに送信する（ステップＳ１０）。ノード１００ａは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ１１）。ノード１００ｂは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ１２）。ノード１００ｃは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ１３）。
【００４４】
図９において、ハローパケット１０は、ステップＳ１０において送信されるハローパケットである。通信経路テーブル１０ａ、１０ｂ、１０ｘは、それぞれ、ノード１００ａ、１００ｂ、１００ｘの通信経路テーブルである。ハローパケット１０のＧＤには「１００ｇ」、ＬＳには「１００ｇ」、Ｅには「０」が登録されている。
【００４５】
ノード１００ａは、ノード１００ｇからハローパケット１０を受信した場合に、通信経路テーブル１０ａのＧＤに「１００ｇ」、ＬＤに「１００ｇ」を登録する。また、ノード１００ａは、ハローパケット１０のＥの値に１を加算した値「１」を通信経路テーブル１０ａに格納する。ノード１００ｂは、通信経路テーブル１０ｂのＧＤに「１００ｇ」、ＬＤに「１００ｇ」を登録する。また、ノード１００ｂは、ハローパケット１０のＥの値に１を加算した値「１」を通信経路テーブル１０ｂに格納する。ノード１００ｘは、通信経路テーブル１０ｘのＧＤに「１００ｇ」、ＬＤに「１００ｇ」を登録する。また、ノード１００ｘは、ハローパケット１０のＥの値に１を加算した値「１」を通信経路テーブル１０ｘに格納する。
【００４６】
図８において、ノード１００ａは、ハローパケットをノード１００ｃ、１００ｄに送信する（ステップＳ２０）。ノード１００ｃは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ２１）。ノード１００ｄは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ２２）。
【００４７】
図１０において、ハローパケット２０は、ステップＳ２０において送信されるハローパケットである。通信経路テーブル１０ｃ、１０ｄは、それぞれ、ノード１００ｃ、１００ｄの通信経路テーブルである。ハローパケット２０のＧＤには「１００ｇ」、ＬＳには「１００ａ」、Ｅには「１」が登録されている。
【００４８】
ノード１００ｃは、ノード１００ａからハローパケット２０を受信した場合に、通信経路テーブル１０ｃのＧＤに「１００ｇ」、ＬＤに「１００ａ」を登録する。また、ノード１００ｃは、ハローパケット２０のＥの値に１を加算した値「２」を通信経路テーブル１０ｃに格納する。また、ノード１００ｄは、ノード１００ａからハローパケット２０を受信した場合に、通信経路テーブル１０ｄのＧＤに「１００ｇ」、ＬＤに「１００ａ」を登録する。また、ノード１００ｄは、ハローパケット２０のＥの値に１を加算した値「２」を通信経路テーブル１０ｄに格納する。
【００４９】
図８において、ノード１００ｂは、ハローパケットをノード１００ｄ、１００ｅ、１００ｙに送信する（ステップＳ３０）。ノード１００ｄは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ３１）。ノード１００ｅは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ３２）。ノード１００ｙは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ３３）。
【００５０】
図１１において、ハローパケット３０は、ステップＳ３０において送信されるハローパケットである。通信経路テーブル１０ｄ、１０ｅ、１０ｙは、それぞれ、ノード１００ｄ、１００ｅ、１００ｙの通信経路テーブルである。ハローパケット３０のＧＳには「１００ｇ」、ＬＳには「１００ｂ」、Ｅには「１」が登録されている。
【００５１】
ノード１００ｄは、ノード１００ｂからハローパケット３０を受信した場合に、通信経路テーブル１０ｄのＧＤに「１００ｇ」、ＬＤに「１００ｂ」を追加登録する。また、ノード１００ｄは、ハローパケット３０のＥの値に１を加算した値「２」を通信経路テーブル１０ｄに格納する。ノード１００ｅは、ノード１００ｂからハローパケット３０を受信した場合に、通信経路テーブル１０ｅのＧＤに「１００ｇ」、ＬＤに「１００ｂ」を格納する。また、ノード１００ｅは、ハローパケット３０のＥの値に１を加算した値「２」を通信経路テーブル１０ｅに格納する。ノード１００ｙは、ノード１００ｂからハローパケット３０を受信した場合に、通信経路テーブル１０ｙのＧＤに「１００ｇ」、ＬＤに「１００ｂ」を格納する。また、ノード１００ｙは、ハローパケット３０のＥの値に１を加算した値「２」を通信経路テーブル１０ｙに格納する。
【００５２】
図８において、ノード１００ｘは、ハローパケットをノード１００ｙに送信する（ステップＳ３５）。ノード１００ｙは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ３６）。
【００５３】
図１２において、ハローパケット３５は、ステップＳ３５において送信されるハローパケットである。通信経路テーブル１０ｙは、ノード１００ｙの通信経路テーブルである。ハローパケット３５のＧＳには「１００ｇ」、ＬＳには「１００ｘ」、Ｅには「１」が登録されている。
【００５４】
ノード１００ｙは、ノード１００ｘからハローパケット３５を受信した場合に、通信経路テーブル１０ｙのＧＤに「１００ｇ」、ＬＤに「１００ｘ」を追加登録する。また、ノード１００ｙは、ハローパケット３５のＥの値に１を加算した値「２」を通信経路テーブル１０ｙに格納する。
【００５５】
図８において、ノード１００ｃは、ハローパケットをノード１００ａ、１００ｄ、１００ｆに送信する（ステップＳ４０）。ノード１００ａは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ４１）。ノード１００ｄは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ４２）。ノード１００ｆは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ４３）。
【００５６】
図１３において、ハローパケット４０は、ステップＳ４０において送信されるハローパケットである。通信経路テーブル１０ａ、１０ｄ、１０ｆは、ノード１００ａ、１００ｄ、１００ｆの通信経路テーブルである。ハローパケット４０のＧＳには「１００ｇ」、ＬＳには「１００ｃ」、Ｅには「２」が登録されている。
【００５７】
ノード１００ａは、ノード１００ｃからハローパケット４０を受信した場合に、通信経路テーブル１０ａのＧＤに「１００ｇ」、ＬＤに「１００ｃ」を追加登録する。また、ノード１００ａは、ハローパケット４０のＥの値に１を加算した値「３」を通信経路テーブル１０ｙに格納する。ノード１００ｄは、ノード１００ｃからハローパケット４０を受信した場合に、通信経路テーブル１０ｄのＧＤに「１００ｇ」、ＬＤに「１００ｃ」を追加登録する。また、ノード１００ｄは、ハローパケット４０のＥの値に１を加算した値「３」を通信経路テーブル１０ｄに格納する。
【００５８】
ノード１００ｆは、ノード１００ｃからハローパケット４０を受信した場合に、通信経路テーブル１０ｆのＧＤに「１００ｇ」、ＬＤに「１００ｃ」を追加登録する。また、ノード１００ｆは、ハローパケット４０のＥの値に１を加算した値「３」を通信経路テーブル１０ｆに格納する。
【００５９】
図８において、ノード１００ｄは、ハローパケットをノード１００ａ、１００ｂ、１００ｃ、１００ｅ、１００ｆに送信する（ステップＳ５０）。ノード１００ａは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ５１）。ノード１００ｂは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ５２）。ノード１００ｃは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ５３）。ノード１００ｅは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ５４）。ノード１００ｆは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ５５）。
【００６０】
図１４において、ハローパケット５０は、ステップＳ５０において送信されるハローパケットである。通信経路テーブル１０ａ、１０ｂ、１０ｃ、１０ｅ、１０ｆは、ノード１００ａ、１００ｂ、１００ｃ、１００ｅ、１００ｆの通信経路テーブルである。ハローパケット５０のＧＳには「１００ｇ」、ＬＳには「１００ｄ」、Ｅには「２」が登録されている。
【００６１】
ノード１００ａは、ノード１００ｄからハローパケット５０を受信した場合に、通信経路テーブル１０ａのＧＤに「１００ｇ」、ＬＤに「１００ｄ」を追加登録する。また、ノード１００ａは、ハローパケット５０のＥの値に１を加算した値「３」を通信経路テーブル１０ａに格納する。ノード１００ｂは、ノード１００ｄからハローパケット５０を受信した場合に、通信経路テーブル１０ｂのＧＤに「１００ｇ」、ＬＤに「１００ｄ」を追加登録する。また、ノード１００ｂは、ハローパケット５０のＥの値に１を加算した値「３」を通信経路テーブル１０ｂに格納する。
【００６２】
ノード１００ｃは、ノード１００ｄからハローパケット５０を受信した場合に、通信経路テーブル１０ｃのＧＤに「１００ｇ」、ＬＤに「１００ｄ」を追加登録する。また、ノード１００ｃは、ハローパケット５０のＥの値に１を加算した値「３」を通信経路テーブル１０ｃに格納する。ノード１００ｅは、ノード１００ｄからハローパケット５０を受信した場合に、通信経路テーブル１０ｅのＧＤに「１００ｇ」、ＬＤに「１００ｄ」を追加登録する。また、ノード１００ｅは、ハローパケット５０のＥの値に１を加算した値「３」を通信経路テーブル１０ｅに格納する。ノード１００ｆは、ノード１００ｄからハローパケット５０を受信した場合に、通信経路テーブル１０ｆのＧＤに「１００ｇ」、ＬＤに「１００ｄ」を追加登録する。また、ノード１００ｆは、ハローパケット５０のＥの値に１を加算した値「３」を通信経路テーブル１０ｆに格納する。
【００６３】
図８において、ノード１００ｅは、ハローパケットをノード１００ｂ、１００ｄ、１００ｆに送信する（ステップＳ６０）。ノード１００ｂは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ６１）。ノード１００ｄは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ６２）。ノード１００ｆは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ６３）。
【００６４】
図１５において、ハローパケット６０は、ステップＳ６０において送信されるハローパケットである。通信経路テーブル１０ｂ、１０ｃ、１０ｆは、ノード１００ｂ、１００ｃ、１００ｆの通信経路テーブルである。ハローパケット６０のＧＳには「１００ｇ」、ＬＳには「１００ｅ」、Ｅには「３」が登録されている。
【００６５】
ノード１００ｂは、ハローパケット６０を受信した場合に、通信経路テーブル１０ｂのＧＤに「１００ｇ」、ＬＤに「１００ｅ」を追加登録する。また、ノード１００ｂは、ハローパケット６０のＥの値に１を加算した値「４」を通信経路テーブル１０ｂに格納する。ノード１００ｃは、ハローパケット６０を受信した場合に、通信経路テーブル１０ｃのＧＤに「１００ｇ」、ＬＤに「１００ｅ」を追加登録する。また、ノード１００ｃは、ハローパケット６０のＥの値に１を加算した値「４」を通信経路テーブル１０ｃに格納する。ノード１００ｆは、ハローパケット６０を受信した場合に、通信経路テーブル１０ｆのＧＤに「１００ｇ」、ＬＤに「１００ｅ」を追加登録する。また、ノード１００ｆは、ハローパケット６０のＥの値に１を加算した値「４」を通信経路テーブル１０ｆに格納する。
【００６６】
図８において、ノード１００ｙは、ハローパケットをノード１００ｂ、１００ｘ、１００ｚに送信する（ステップＳ７０）。ノード１００ｂは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ７１）。ノード１００ｘは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ７２）。ノード１００ｚは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ７３）。
【００６７】
図１６において、ハローパケット７０は、ステップＳ７０において送信されるハローパケットである。通信経路テーブル１０ｂ、１０ｘ、１０ｚは、ノード１００ｂ、１００ｘ、１００ｚの通信経路テーブルである。ハローパケット７０のＧＳには「１００ｇ」、ＬＳには「１００ｙ」、Ｅには「２」が登録されている。
【００６８】
ノード１００ｂは、ハローパケット７０を受信した場合に、通信経路テーブル１０ｂのＧＤに「１００ｇ」、ＬＤに「１００ｙ」を追加登録する。また、ノード１００ｂは、ハローパケット７０のＥの値に１を加算した値「３」を通信経路テーブル１０ｂに格納する。ノード１００ｘは、ハローパケット７０を受信した場合に、通信経路テーブル１０ｘのＧＤに「１００ｇ」、ＬＤに「１００ｙ」を追加登録する。また、ノード１００ｘは、ハローパケット７０のＥの値に１を加算した値「３」を通信経路テーブル１０ｘに格納する。ノード１００ｚは、ハローパケット７０を受信した場合に、通信経路テーブル１０ｚのＧＤに「１００ｇ」、ＬＤに「１００ｙ」を追加登録する。また、ノード１００ｚは、ハローパケット７０のＥの値に１を加算した値「３」を通信経路テーブル１０ｚに格納する。
【００６９】
図８において、ノード１００ｆは、ハローパケットをノード１００ｃ、１００ｄ、１００ｅに送信する（ステップＳ８０）。ノード１００ｃは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ８１）。ノード１００ｄは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ８２）。ノード１００ｅは、ハローパケットを受信し、通信経路テーブルを更新する（ステップＳ８３）。
【００７０】
図１７において、ハローパケット８０は、ステップＳ８０において送信されるハローパケットである。通信経路テーブル１０ｃ、１０ｄ、１０ｅは、ノード１００ｃ、１００ｄ、１００ｅの通信経路テーブルである。ハローパケット８０のＧＳには「１００ｇ」、ＬＳには「１００ｆ」、Ｅには「３」が登録されている。
【００７１】
ノード１００ｃは、ハローパケット８０を受信した場合に、通信経路テーブル１０ｃのＧＤに「１００ｇ」、ＬＤに「１００ｆ」を追加登録する。また、ノード１００ｂは、ハローパケット８０のＥの値に１を加算した値「４」を通信経路テーブル１０ｃに格納する。ノード１００ｄは、ハローパケット８０を受信した場合に、通信経路テーブル１０ｄのＧＤに「１００ｇ」、ＬＤに「１００ｆ」を追加登録する。また、ノード１００ｄは、ハローパケット８０のＥの値に１を加算した値「４」を通信経路テーブル１０ｄに格納する。ノード１００ｅは、ハローパケット８０を受信した場合に、通信経路テーブル１０ｅのＧＤに「１００ｇ」、ＬＤに「１００ｆ」を追加登録する。また、ノード１００ｅは、ハローパケット８０のＥの値に１を加算した値「４」を通信経路テーブル１０ｅに格納する。
【００７２】
上記のように、各ノード１００ａ〜１００ｇ、１００ｘ〜１００ｚが図８に示すような処理を実行することで、図９〜図１７に示したように、各通信経路テーブルを更新する。なお、図９〜図１７に示した通信経路テーブルは、図２に示した通信経路テーブル１４０ｂに対応する。
【００７３】
次に、アドホックネットワークのノード１００ａ〜１００ｇ、１００ｘ〜１００ｚが経路構築パケットを送受信して、通信経路テーブルを更新する処理について説明する。図１８〜図２１は、経路構築パケットによる経路構築の処理を説明する図である。
【００７４】
まず、図１８に示すように、経路構築パケットがノード１００ｆから送信され、ノード１００ｄ、１００ａ、１００ｇの順に転送される場合について説明する。また、そのときの、経路構築パケットと各ノードの経路構築パケットの内容を図１９に示す。図１９において、１０ｆ、１０ｄ、１０ａ、１０ｇは、ノード１００ｆ、１００ｄ、１００ａ、１００ｇの通信経路テーブルである。
【００７５】
ノード１００ｆは、例えば、通信経路テーブル１０ｆの２段目を選択する。ノード１００ｆは、経路構築パケット８５ａのＧＤ、ＬＤに通信経路テーブル１０ｆのＧＤ「１００ｇ」、ＬＤ「１００ｄ」を格納する。また、ノード１００ｆは、経路構築パケット８５ａのＧＳ、ＬＳに、自ノードのアドレスを格納する。また、ノード１００ｆは、Ｅに「０」を格納し、ＦＩＤに経路構築パケット８５ａを識別する値「１」を登録する。
【００７６】
ノード１００ｆは、経路構築パケット８５ａをノード１００ｄに送信する。ノード１００ｄは、経路構築パケット８５ａのＧＳ、ＬＳを、通信経路テーブル１０ｄのＧＤ、ＬＤに登録する。また、ノード１００ｄは、経路構築パケット８５ａのＥに１を加算した値「１」を、通信経路テーブル１０ｄのＥに登録する（ステップＳ８５ａ）。
【００７７】
ノード１００ｄは、経路構築パケット８５ｂのＧＤ、ＧＳに経路構築パケット８５ａのＧＤ「１００ｇ」、ＧＳ「１００ｆ」を格納する。また、ノード１００ｄは、経路構築パケット８５ｂのＬＳに自ノードを格納する。ノード１００ｄは、経路構築パケット８５ｂのＬＤに転送先となる「ｌ００ａ」を格納する。また、ノード１００ｄは、先の経路構築パケット８５ａのＥに１を加算した値「１」を、経路構築パケット８５ｂのＥに格納する。また、ノード１００ｄは、ＦＩＤに値「１」を登録する。
【００７８】
ノード１００ｄは、経路構築パケット８５ｂをノード１００ａに送信する。ノード１００ａは、経路構築パケット８５ｂのＧＳ、ＬＳを、通信経路テーブル１０ａのＧＤ、ＬＤに登録する。また、ノード１００ａは、経路構築パケット８５ｂのＥに１を加算した値「２」を、通信経路テーブル１０ａのＥに登録する（ステップＳ８５ｂ）。
【００７９】
ノード１００ａは、経路構築パケット８５ｃのＧＤ、ＧＳに経路探索パケット８５ｂのＧＤ「１００ｇ」、ＧＳ「１００ｆ」を格納する。また、ノード１００ａは、経路構築パケット８５ｃのＬＳに自ノードを格納する。ノード１００ａは、経路構築パケット８５ｃのＬＤに転送先となる「ｌ００ｇ」を格納する。また、ノード１００ａは、先の経路構築パケット８５ａのＥに１を加算した値「２」を、経路構築パケット８５ｃのＥに格納する。
【００８０】
ノード１００ａは、経路構築パケット８５ｃをノード１００ｇに送信する。ノード１００ｇは、経路構築パケット８５ｃのＧＳ、ＬＳを、通信経路テーブル１０ｇのＧＤ、ＬＤに登録する。また、ノード１００ｇは、経路構築パケット８５ｃのＥに１を加算した値「３」を、通信経路テーブル１０ｇのＥに登録する（ステップＳ８５ｃ）。
【００８１】
このように、ステップＳ８５ａ〜８５ｃの処理を実行することにより、ノード１００ｇは、目的地「１００ｆ」に対する通信経路を得ることができる。
【００８２】
続いて、図２０に示すように、経路構築パケットがノード１００ｆから送信され、ノード１００ｅ、１００ｄ、１００ｂ、１００ｇの順に転送される場合について説明する。ただし、ノード１００ｅからノード１００ｂへの経路構築パケットの転送が失敗したために、経路構築パケットは、ノード１００ｄを経由して、ノード１００ｅからノード１００ｂに転送されるものとする。
【００８３】
図２１において、１０ｆ、１０ｅ、１０ｄ、１０ｂ、１０ｇは、ノード１００ｆ、１００ｅ、１００ｄ、１００ｂ、１００ｇの通信経路テーブルである。ノード１００ｆは、例えば、通信経路テーブル１０ｆの３段目を選択する。ノード１００ｆは、経路構築パケット８６ａのＧＤ、ＬＤに通信経路テーブル１０ｆのＧＤ「１００ｇ」、ＬＤ「１００ｅ」を格納する。また、ノード１００ｆは、経路構築パケット８６ａのＧＳ、ＬＳに、自ノードのアドレスを格納する。また、ノード１００ｆは、Ｅに０を格納し、ＦＩＤに経路構築パケット８５ａを識別する値「２」を登録する。
【００８４】
ノード１００ｆは、経路構築パケット８６ａをノード１００ｅに送信する。ノード１００ｅは、経路構築パケット８６ａのＧＳ、ＬＳを、通信経路テーブル１０ｅのＧＤ、ＬＤに登録する。また、ノード１００ｆは、経路構築パケット８６ａのＥに１を加算した値「１」を、通信経路テーブル１０ｅのＥに登録する（ステップＳ８６ａ）。
【００８５】
ノード１００ｅは、経路構築パケット８６ｂのＧＤ、ＧＳに経路構築パケット８６ａのＧＤ「１００ｇ」、ＧＳ「１００ｆ」を格納する。また、ノード１００ｅは、経路構築パケット８６ｂのＬＳに自ノードを格納する。ノード１００ｅは、経路構築パケット８６ｂのＬＤに転送先となる「ｌ００ｂ」を格納する。また、ノード１００ｅは、先の経路構築パケット８６ａのＥに１を加算した値「１」を、経路構築パケット８６ｂのＥに格納する。
【００８６】
ノード１００ｅは、経路構築パケット８６ｂをノード１００ｂに転送するが、転送に失敗する。このように、転送を失敗した場合には、通信経路を切り換える。例えば、ノード１００ｅは、経路構築パケット８６ｂのＬＤを「１００ｄ」に変更した経路構築パケット８６ｃを作成し、経路構築パケット８６ｃを、ノード１００ｄに送信する。
【００８７】
ノード１００ｄは、経路構築パケット８６ｃを受信し、経路構築パケット８６ｃのＧＳ、ＬＳを、通信経路テーブル１０ｄのＧＤ、ＬＤに登録する。また、ノード１００ｄは、経路構築パケット８６ｃのＥに１を加算した値「２」を、通信経路テーブル１０ｄのＥに登録する（ステップＳ８６ｂ）。
【００８８】
ノード１００ｄは、経路構築パケット８６ｄのＧＤ、ＧＳに経路探索パケット８６ｃのＧＤ「１００ｇ」、ＧＳ「１００ｆ」を格納する。また、ノード１００ｄは、経路構築パケット８６ｄのＬＳに自ノードを格納する。ノード１００ｄは、経路構築パケット８６ｃのＬＤに転送先となる「ｌ００ｂ」を格納する。また、ノード１００ｄは、先の経路構築パケット８６ｃのＥに１を加算した値「２」を、経路構築パケット８６ｄのＥに格納する。ノード１００ｄは、経路構築パケット８６ｄを、ノード１００ｂに送信する。
【００８９】
ノード１００ｂは、経路構築パケット８６ｄを受信し、経路構築パケット８６ｄのＧＳ、ＬＳを、通信経路テーブル１０ｂのＧＤ、ＬＤに登録する。また、ノード１００ｂは、経路構築パケット８６ｂのＥに１を加算した値「３」を、通信経路テーブル１０ｂのＥに登録する（ステップＳ８６ｃ）。
【００９０】
ノード１００ｂは、経路構築パケット８６ｅのＧＤ、ＧＳに経路探索パケット８６ｄのＧＤ「１００ｇ」、ＧＳ「１００ｆ」を格納する。また、ノード１００ｂは、経路構築パケット８６ｅのＬＳに自ノードを格納する。ノード１００ｂは、経路構築パケット８６ｅのＬＤに転送先となる「ｌ００ｇ」を格納する。また、ノード１００ｂは、先の経路構築パケット８６ｄのＥに１を加算した値「３」を、経路構築パケット８６ｅのＥに格納する。ノード１００ｂは、経路構築パケット８６ｅを、ノード１００ｇに送信する。
【００９１】
ノード１００ｇは、経路構築パケット８６ｅを受信し、経路構築パケット８６ｅのＧＳ、ＬＳを、通信経路テーブル１０ｇのＧＤ、ＬＤに登録する。また、ノード１００ｇは、経路構築パケット８６ｅのＥに１を加算した値「４」を、通信経路テーブル１０ｇのＥに登録する（ステップＳ８６ｄ）。
【００９２】
このように、ステップＳ８６ａ〜８６ｄの処理を実行することにより、ノード１００ｇは、目的地「１００ｆ」に対する新たな通信経理を得ることができる。
【００９３】
次に、アドホックネットワークのノード１００ａ〜１００ｇ、１００ｘ〜１００ｚが経路探索パケットを送信する処理について説明する。ただし、この経路探索パケットを送信する処理は、図８に示したハローパケットの送受信、図２０に示した経路構築パケットの送受信が行われた後に実行される。
【００９４】
次に、経路探索パケットの転送処理について説明する。図２２〜図２９は、経路探索パケットの転送処理を説明するための図である。ここでは一例として、ノード１００ｇが、経路探索パケットのＧＤにノード１００ｆのアドレスを格納して、経路探索パケットをブロードキャストする場合について説明する。図２２において、ノード１００ｇは、経路探索パケットをブロードキャストし、ノード１００ａ、１００ｂ、１００ｘは、経路探索パケットを受信する（ステップＳ９０）。
【００９５】
ステップＳ９１にて送信される経路探索パケットについて説明する。図２３に示すように、ノード１００ｇは、経路探索パケット９０のＧＳにノード１００ｇのアドレスを格納し、ＧＤにノード１００ｆのアドレスを格納する。また、ノード１００ｇは、経路探索パケット９０の探索範囲に初期値の１を設定し、経路探索パケット９０をブロードキャストする。
【００９６】
図２２において、ノード１００ａは、経路探索パケットをブロードキャストし、ノード１００ｃ、１００ｄは、経路探索パケットを受信する（ステップＳ９１）。
【００９７】
ステップＳ９１にて送信される経路探索パケットについて説明する。図２４に示すように、通信経路テーブル１０ａのＧＤにノード１００ｆのアドレスが含まれている。このため、ノード１００ａは、経路探索パケット９０の探索範囲を初期値の１に設定し、経路探索パケット９０をブロードキャストする。
【００９８】
図２２において、ノード１００ｂは、経路探索パケットをブロードキャストし、ノード１００ｄ、１００ｅ、１００ｙは、経路探索パケットを受信する（ステップＳ９２）。
【００９９】
ステップＳ９２にて送信される経路探索パケットについて説明する。図２５に示すように、通信経路テーブル１０ｂのＧＤにノード１００ｆのアドレスが含まれている。このため、ノード１００ｂは、経路探索パケット９０の探索範囲を初期値の１に設定し、経路探索パケット９０をブロードキャストする。
【０１００】
図２２において、ノード１００ｘは、経路探索パケットをブロードキャストし、ノード１００ｙは、経路探索パケットを受信する（ステップＳ９３）。
【０１０１】
ステップＳ９３にて送信される経路探索パケットについて説明する。図２６に示すように、通信経路テーブル１０ｘのＧＤにノード１００ｆのアドレスが含まれていない。このため、ノード１００ｘは、経路探索パケットの探索範囲を１減算する。探索範囲の値が０以上であるため、ノード１００ｘは、経路探索パケット９０をブロードキャストする。
【０１０２】
また、図２６に示すように、通信経路テーブル１０ｙのＧＤにノード１００ｆのアドレスが含まれていない。このため、ノード１００ｙは、経路検索パケットの探索範囲を１減算する。探索範囲の値が０未満となるため、ノード１００ｆは、経路検索パケット９０の転送を停止する。
【０１０３】
図２２において、ノード１００ｙは、ノード１００ｂから受信した経路探索パケットをブロードキャストし、ノード１００ｚは、経路探索パケットを受信する（ステップＳ９４）。
【０１０４】
ステップＳ９４にて送信される経路探索パケットについて説明する。図２７に示すように、通信経路テーブル１０ｙのＧＤにノード１００ｆのアドレスが含まれていない。このため、ノード１００ｙは、経路探索パケットの探索範囲を１減算する。探索範囲の値が０以上であるため、ノード１００ｙは、経路探索パケット９０をブロードキャストする。
【０１０５】
また、図２７に示すように、通信経路テーブル１０ｚのＧＤにノード１００ｆのアドレスが含まれていない。このため、ノード１００ｚは、経路探索パケットの探索範囲を１減算する。探索範囲の値が０未満となるため、ノード１００ｚは、経路探索パケットの転送を停止する。
【０１０６】
図２２において、ノード１００ｄは、ノード１００ａから受信した経路探索パケットをブロードキャストし、ノード１００ｃ、１００ｅ、１００ｆは、経路探索パケットを受信する（ステップＳ９５）。
【０１０７】
ステップＳ９５にて送信される経路探索パケットについて説明する。図２８に示すように、通信経路テーブル１０ｄのＧＤにノード１００ｆのアドレスが含まれている。このため、ノード１００ｄは、経路検索パケット９０の探索範囲を初期値の１に設定し、経路探索パケット９０をブロードキャストする。
【０１０８】
図２２において、ノード１００ｃは、ノード１００ｄから受信した経路探索パケットをブロードキャストし、ノード１００ｆは、経路探索パケットを受信する。また、ノード１００ｅは、ノード１００ｄから受信した経路探索パケットをブロードキャストし、ノード１００ｆは、経路探索パケットを受信する（ステップＳ９６）。
【０１０９】
ステップＳ９６にて送信される経路探索パケットについて説明する。図２９に示すように、通信経路テーブル１０ｅのＧＤにノード１００ｆのアドレスが含まれている。このため、ノード１００ｅは、経路検索パケット９０の探索範囲を初期値の１に設定し、経路探索パケット９０をブロードキャストする。
【０１１０】
また、図２９に示すように、通信経路テーブル１０ｃのＧＤにノード１００ｆのアドレスが含まれていない。このため、ノード１００ｃは、経路探索パケットの探索範囲を１減算する。探索範囲の値が０以上であるため、ノード１００ｃは、経路探索パケット９０をブロードキャストする。
【０１１１】
ステップＳ９６において、ノード１００ｆは、自ノード宛の経路検索パケットを受信する。この場合には、ノード１００ｆは、ノード１００ｇ宛の応答パケットを送信する。
【０１１２】
次に、ノード１００がハローパケットを受信した場合の処理手順について説明する。図３０は、ハローパケット受信処理の処理手順を示すフローチャートである。図３０に示す処理は、例えば、ハローパケットを受信したことを契機に実行される。図３０に示す処理は、ハローパケット制御部１５０ａの処理に対応する。
【０１１３】
図３０に示すように、ノード１００は、ハローパケットを受信していない場合には（ステップＳ１０１，Ｎｏ）、処理を終了する。一方、ノード１００は、ハローパケットを受信した場合には（ステップＳ１０１，Ｙｅｓ）、ハローパケットに情報が含まれるか否かを判定する（ステップＳ１０２）。
【０１１４】
ノード１００は、ハローパケットに情報が含まれない場合には（ステップＳ１０２，Ｎｏ）、処理を終了する。一方、ノード１００は、ハローパケットに情報が含まれている場合には（ステップＳ１０２，Ｙｅｓ）、ＧＳまたはＬＳが自アドレスであるか否かを判定する（ステップＳ１０３）。
【０１１５】
ノード１００は、ＧＳまたはＬＳが自アドレスの場合には（ステップＳ１０３，Ｙｅｓ）、処理を終了する。一方、ノード１００は、ＧＳまたはＬＳが自アドレスではない場合には（ステップＳ１０３，Ｎｏ）、ワークテーブル１４０ａにレコードを新規作成する（ステップＳ１０４）。
【０１１６】
ノード１００は、ワークテーブル１４０ａのＧＤにハローパケットのＧＳを設定し（ステップＳ１０５）、ワークテーブル１４０ａのＬＤにハローパケットのＬＳを設定する（ステップＳ１０６）。ノード１００は、ワークテーブル１４０ａのＥにハローパケットのＥに１を加算した値を設定する（ステップＳ１０７）。
【０１１７】
ノード１００は、通信経路テーブル１４０ｂに同一のＧＳおよびＬＤのレコードが存在しない場合には（ステップＳ１０８，Ｎｏ）、ワークテーブルに作成したレコードを通信経路テーブルに新規追加し（ステップＳ１１０）、処理を終了する。一方、ノード１００は、通信経路テーブル１４０ｂに同一のＧＳおよびＬＤのレコードが存在しない場合には（ステップＳ１０８，Ｎｏ）、ワークテーブル１４０ａに作成したレコードを通信経路テーブル１４０ｂに新規追加する（ステップＳ１１０）。一方、ノード１００は、通信経路テーブル１４０ｂに同一のＧＳおよびＬＤのレコードが存在する場合には（ステップＳ１０８，Ｙｅｓ）、上書きする（ステップＳ１０９）。
【０１１８】
次に、ノード１００がハローパケットを送信する場合の処理手順について説明する。図３１は、ハローパケット送信処理の処理手順を示すフローチャートである。図３１に示す処理は、例えば、クロックイベントが発生したことを契機として実行される。図３１に示す処理は、ハローパケット制御部１５０ａの処理に対応する。
【０１１９】
図３１に示すように、ノード１００は、クロックイベントが発生していない場合には（ステップＳ１５０，Ｎｏ）、処理を終了する。一方、ノード１００は、クロックイベントが発生した場合には（ステップＳ１５０，Ｙｅｓ）、通信経路テーブル１４０ｂに情報が存在するか否かを判定する（ステップＳ１５１）。
【０１２０】
ノード１００は、通信経路テーブルに情報が存在しない場合には（ステップＳ１５１，Ｎｏ）、処理を終了する。一方、ノード１００は、通信経路テーブルに情報が存在する場合には（ステップＳ１５１，Ｙｅｓ）、通信経路テーブル１４０ｂからＧＳがＧＷのアドレスとなるレコードを抽出する（ステップＳ１５２）。ＧＷをノード１００ｇとすると、ノード１００は、ＧＳがノード１００ｇのアドレスとなるレコードを抽出する。
【０１２１】
ノード１００は、ハローパケットのＧＳに通信経路テーブル１４０ｂのＧＤを設定し（ステップＳ１５３）、ハローパケットのＬＳに通信経路テーブル１４０ｂのＬＤを設定する（ステップＳ１５４）。
【０１２２】
ノード１００は、ハローパケットのＥに通信経路テーブルのＥを設定し（ステップＳ１５５）、ハローパケットを送信する（ステップＳ１５６）。
【０１２３】
次に、ノード１００が、下り経路を構築する場合の経路構築パケットの送信処理について説明する。図３２は、経路構築パケットの送信処理の処理手順を示すフローチャートである。図３２に示す処理は、例えば、クロックイベントが発生したことを契機にして実行される。図３２に示す処理は、下り経路構築部１５０ｂの処理に対応する。
【０１２４】
図３２に示すように、ノード１００は、通信経路テーブル１４０ｂに、所望のＧＤが存在しない場合には（ステップＳ２０１，Ｎｏ）、処理を終了する。一方、ノード１００は、所望のＧＤが存在する場合には（ステップＳ２０１，Ｙｅｓ）、データ管理テーブル１４０ｃに基づいて、通信経路テーブル１４０ｂに送信可能な転送先が存在するか否かを判定する（ステップＳ２０２）。
【０１２５】
ノード１００は、データ管理テーブル１４０ｃに基づいて、通信経路テーブル１４０ｂに送信可能な転送先が存在しない場合には（ステップＳ２０２，Ｎｏ）、処理を終了する。一方、ノード１００は、通信経路テーブル１４０ｂに送信可能な転送先が存在する場合には（ステップＳ２０２，Ｙｅｓ）、通信経路テーブル内の未送信の上位レコードを抽出する（ステップＳ２０３）。
【０１２６】
ノード１００は、自ノードがＧＳではない場合には（ステップＳ２０４，Ｎｏ）、レコードのＧＤを、経路構築パケットのＧＤに設定する（ステップＳ２０５）。ノード１００は、レコードのＧＳを、経路構築パケットのＧＳに設定し（ステップＳ２０６）、レコードのＥを経路構築パケットのＥに設定し（ステップＳ２０７）、ステップＳ２１１に移行する。
【０１２７】
一方、ノード１００は、自ノードがＧＳの場合には（ステップＳ２０４，Ｙｅｓ）、経路構築パケットのＧＤに目的地のノードのアドレスを設定する（ステップＳ２０８）。ノード１００は、経路構築パケットのＧＳに自ノードのアドレスを設定し（ステップＳ２０９）、経路構築パケットのＥに通信経路テーブル１４０ｂの上位Ｅを設定する（ステップＳ２１０）。
【０１２８】
ノード１００は、経路構築パケットのＬＤに通信経路テーブル１４０ｂの上位ＬＤを設定し（ステップＳ２１１）、経路構築パケットのＦＩＤにユニークな数値を設定する（ステップＳ２１２）。ノード１００は、経路構築パケットのＬＳに自ノードのアドレスを設定し（ステップＳ２１３）、経路構築パケットの内容をデータ管理テーブル１４０ｃに記録し（ステップＳ２１４）、経路構築パケットを送信する（ステップＳ２１５）。
【０１２９】
次に、ノード１００が、下り経路を構築する場合の経路構築パケットの受信処理について説明する。図３３は、経路構築パケットの受信処理の処理手順を示すフローチャートである。図３３に示す処理は、例えば、経路構築パケットを受信したことを契機にして実行される。図３３に示す処理は、下り経路構築部１５０ｂの処理に対応する。
【０１３０】
図３３に示すように、ノード１００は、経路構築パケットを受信していない場合には（ステップＳ２５０，Ｎｏ）、処理を終了する。一方、ノード１００は、経路構築パケットを受信した場合には（ステップＳ２５０，Ｙｅｓ）、ワークテーブル１４０ａにレコードを新規作成する（ステップＳ２５１）。
【０１３１】
ノード１００は、ワークテーブル１４０ａのＧＤに経路構築パケットのＧＳを設定し（ステップＳ２５２）、ワークテーブル１４０ａのＬＤに経路構築パケットのＬＳを設定する（ステップＳ２５３）。
【０１３２】
ノード１００は、ワークテーブル１４０ａのＥに、経路構築パケットのＥに１を加算した値を設定する（ステップ２５４）。ノード１００は、通信経路テーブル１４０ｂに同一のＧＳおよびＬＤのレコードが存在する場合には（ステップＳ２５５，Ｙｅｓ）、上書きする（ステップＳ２５６）。一方、ノード１００は、通信経路テーブル１４０ｂに同一のＧＳおよびＬＤのレコードが存在しない場合には（ステップＳ２５５，Ｎｏ）、ワークテーブル１４０ａに作成したレコードを通信経路テーブルに新規追加する（ステップＳ２５７）。
【０１３３】
次に、ノード１００が、経路探索パケットに対する処理について説明する。図３４は、経路探索パケットの処理手順を示すフローチャートである。図３４に示す処理は、例えば、経路探索要求を受け付けたことまたは、経路探索パケットを受信したことを契機に実行される。図３４に示す処理は、経路探索パケット送信部１５０ｃ、経路探索パケット受信部１５０ｄの処理に対応する。
【０１３４】
図３４に示すように、経路探索要求があった場合には（ステップＳ３０１，Ｙｅｓ）、経路探索パケットのＧＳに自ノードのアドレスを設定する（ステップＳ３０２）。ノード１００は、経路探索パケットのＧＤに目的ノードを設定する（ステップＳ３０３）。
【０１３５】
ノード１００は、経路探索パケットの探索範囲に、探索範囲の初期値を設定する（ステップＳ３０４）。例えば、ノード１００は、探索範囲の初期値として、１を設定する。ノード１００は、探索範囲が０以上の場合には（ステップＳ３０５，Ｙｅｓ）、経路探索パケットを送信する（ステップＳ３０６）。一方、ノード１００は、探索範囲が０未満の場合には（ステップＳ３０５，Ｎｏ）、処理を終了する。
【０１３６】
ところで、ノード１００は、経路探索要求がない場合には（ステップＳ３０１，Ｎｏ）、経路探索パケットの転送を行うと判定する（ステップＳ３０７）。ノード１００は、経路探索パケットのＧＤとＧＳをそのまま流用し（ステップＳ３０８）、通信経路テーブル１４０ｂ内にＧＤが存在する場合には（ステップＳ３０９，Ｙｅｓ）、ステップＳ３０４に移行する。
【０１３７】
一方、ノード１００は、通信経路テーブル１４０ｂ内にＧＤが存在しない場合には（ステップＳ３０９，Ｎｏ）、経路探索パケットの探索範囲に、既存の探索範囲値から１を減算した値を設定し（ステップＳ３１０）、ステップＳ３０５に移行する。
【０１３８】
次に、本実施例にかかるノード１００の効果について説明する。ノード１００は、通信経路探索パケットを受信した場合に、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されているか否かを判定する。ノード１００は、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されている場合には、通信経路探索パケットをブロードキャストする。これに対して、ノード１００は、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されていない場合には、通信経路端末パケットの探索範囲の値を減算する。そして、ノード１００は、減算した探索範囲の値が０以上の場合に、通信経路探索パケットをブロードキャストする。このため、通信経路探索パケットは、目的地以外の方向には転送されず、目的地の方向に転送される。したがって、ノード１００は、通信経路を構築する場合に、経路探索パケットの伝送範囲を最適に絞り込むことができる。
【０１３９】
また、ノード１００は、通信経路探索パケットのＧＤに対応するノードのアドレスが、通信経路テーブル１４０ｂのＧＤに登録されている場合には、通信経路探索パケットの探索範囲を初期値に設定し直す。このため、目的地のノードに至る通信経路が迂回経路しか存在しない場合でも、通信経路探索パケットを到達させることができる。
【０１４０】
また、ノード１００は、通信経路探索パケットを送信した後に、通信経路探索パケットの目的地のノードから応答を受信しない場合には、通信経路探索パケットの探索範囲を所定の値増やして、再送する。このため、通信経路探索パケットをより確実に目的地のノードに到達させることができる。
【０１４１】
ところで、ノード１００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、ノード１００の具体的形態は図示のものに限られず、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図２の各処理部１５０ａ〜１５０ｄの機能をまとめてもよい。
【０１４２】
上記実施例に示したノード１００の機能は、既知のＰＣ（Personal Computer）またはＰＤＡ（Personal Digital Assistants）などの情報処理装置に、ノードに対応する各機能を搭載することによって実現することもできる。図３５は、ノードを構成するコンピュータのハードウェア構成を示す図である。
【０１４３】
図３５に示すように、このコンピュータ３００は、各種演算処理を実行するＣＰＵ３０１と、ユーザからのデータの入力を受け付ける入力装置３０２と、ディスプレイ３０３とを有する。また、コンピュータ３００は、記憶媒体からプログラム等を読み取る読み取り装置３０４と、他の装置と接続するためのインターフェース装置３０５とを有する。また、コンピュータ３００は、他の装置と無線により接続する無線通信装置３０６と、各種情報を一時記憶するＲＡＭ３０７と、ハードディスク装置３０８とを有する。各装置３０１〜３０８は、バス３０９に接続される。
【０１４４】
ハードディスク装置３０８には、判定プログラム、送信制御プログラムなどの各種のプログラムが記憶される。
【０１４５】
ＣＰＵ３０１は、ハードディスク装置３０８に記憶された各プログラムを読み出して、ＲＡＭ３０７に展開し、各種の処理を行う。また、これらのプログラムは、コンピュータを図３の判定部１５１、送信制御部１５２として機能させることができる。
【０１４６】
なお、上記のプログラムは、必ずしもハードディスク装置３０８に格納されている必要はない。例えば、ＣＤ−ＲＯＭ等の記憶媒体に記憶されたプログラムを、コンピュータ３００が読み出して実行するようにしてもよい。また、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等に接続された記憶装置に、各プログラムを記憶させておいてもよい。この場合、コンピュータ３００がこれらから各プログラムを読み出して実行するようにしてもよい。
【符号の説明】
【０１４７】
１００ａ、１００ｂ、１００ｃ、１００ｄ、１００ｅ、１００ｆ、１００ｇ、１００ｘ、１００ｙ、１００ｚ ノード
１１０ 無線通信部
１２０ 入力部
１３０ 表示部
１４０ 記憶部
１５０ 制御部
【特許請求の範囲】
【請求項１】
探索対象となる無線通信端末の情報と探索範囲を示す値とを有するパケットを受信した場合に、目的地の経路を含む通信経路テーブルを参照し、該通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれているか否かを判定する判定部と、
前記判定部の判定結果に基づいて、前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれている場合には、前記パケットを隣接する無線通信端末に送信し、
前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれていない場合には、前記探索範囲を示す値から所定値を減算し、該探索範囲を示す値が所定の閾値以上の場合には、前記パケットを隣接する無線通信端末に送信する送信制御部と
を有することを特徴とする無線通信端末。
【請求項２】
前記送信制御部は、前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれている場合には、前記パケットに含まれる探索範囲の値を初期値に設定し直し、該パケットを隣接する無線通信端末に送信することを特徴とする請求項１に記載の無線通信端末。
【請求項３】
コンピュータが実行する経路構築方法であって、
探索対象となる無線通信端末の情報と探索範囲を示す値とを有するパケットを受信した場合に、目的地の経路を含む通信経路テーブルを参照し、該通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれている場合には、前記パケットを隣接する無線通信端末に送信し、
前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれていない場合には、前記探索範囲を示す値から所定値を減算し、該探索範囲を示す値が所定の閾値以上の場合には、前記パケットを隣接する無線通信端末に送信することを特徴とする経路構築方法。
【請求項４】
前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれている場合には、前記パケットに含まれる探索範囲の値を初期値に設定し直し、該パケットを隣接する無線通信端末に送信することを特徴とする請求項３に記載の経路構築方法。
【請求項５】
第１の無線通信端末が、探索対象となる無線通信端末の情報と探索範囲を示す値とを有するパケットを送信し、
第２の無線通信端末が、前記パケットを受信した場合に、目的地の経路を含む通信経路テーブルを参照し、該通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれている場合には、前記パケットを隣接する無線通信端末に送信し、
前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれていない場合には、前記探索範囲を示す値から所定値を減算し、該探索範囲を示す値が所定の閾値以上の場合には、前記パケットを隣接する無線通信端末に送信することを特徴とする経路構築方法。
【請求項６】
前記第１の無線通信端末は、前記探索対象となる無線通信端末から前記パケットの応答を受信しない場合には、前記パケットの探索範囲の値に所定値を加算し、パケットを再送することを特徴とする請求項５に記載の経路構築方法。
【請求項１】
探索対象となる無線通信端末の情報と探索範囲を示す値とを有するパケットを受信した場合に、目的地の経路を含む通信経路テーブルを参照し、該通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれているか否かを判定する判定部と、
前記判定部の判定結果に基づいて、前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれている場合には、前記パケットを隣接する無線通信端末に送信し、
前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれていない場合には、前記探索範囲を示す値から所定値を減算し、該探索範囲を示す値が所定の閾値以上の場合には、前記パケットを隣接する無線通信端末に送信する送信制御部と
を有することを特徴とする無線通信端末。
【請求項２】
前記送信制御部は、前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれている場合には、前記パケットに含まれる探索範囲の値を初期値に設定し直し、該パケットを隣接する無線通信端末に送信することを特徴とする請求項１に記載の無線通信端末。
【請求項３】
コンピュータが実行する経路構築方法であって、
探索対象となる無線通信端末の情報と探索範囲を示す値とを有するパケットを受信した場合に、目的地の経路を含む通信経路テーブルを参照し、該通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれている場合には、前記パケットを隣接する無線通信端末に送信し、
前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれていない場合には、前記探索範囲を示す値から所定値を減算し、該探索範囲を示す値が所定の閾値以上の場合には、前記パケットを隣接する無線通信端末に送信することを特徴とする経路構築方法。
【請求項４】
前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれている場合には、前記パケットに含まれる探索範囲の値を初期値に設定し直し、該パケットを隣接する無線通信端末に送信することを特徴とする請求項３に記載の経路構築方法。
【請求項５】
第１の無線通信端末が、探索対象となる無線通信端末の情報と探索範囲を示す値とを有するパケットを送信し、
第２の無線通信端末が、前記パケットを受信した場合に、目的地の経路を含む通信経路テーブルを参照し、該通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれている場合には、前記パケットを隣接する無線通信端末に送信し、
前記通信経路テーブルの目的地に、前記探索対象となる無線通信端末が含まれていない場合には、前記探索範囲を示す値から所定値を減算し、該探索範囲を示す値が所定の閾値以上の場合には、前記パケットを隣接する無線通信端末に送信することを特徴とする経路構築方法。
【請求項６】
前記第１の無線通信端末は、前記探索対象となる無線通信端末から前記パケットの応答を受信しない場合には、前記パケットの探索範囲の値に所定値を加算し、パケットを再送することを特徴とする請求項５に記載の経路構築方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【公開番号】特開２０１２−２０５２９５（Ｐ２０１２−２０５２９５Ａ）
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【出願番号】特願２０１１−７１１６２（Ｐ２０１１−７１１６２）
【出願日】平成２３年３月２８日（２０１１．３．２８）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【出願日】平成２３年３月２８日（２０１１．３．２８）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]