(57)【要約】【課題】中継端末間の双方向通信を可能とする中継経路の探索を行い、経路断時にもデータパケットの送信を継続することを可能にする。【解決手段】送信元端末が宛先端末を指定して経路探索パケットをブロードキャストするステップと、それを受信した各無線端末がさらなるブロードキャストにより宛先端末まで中継するとともに、経路探索パケットを送信した無線端末のＩＤを近接端末リストに登録するステップと、経路探索パケットを受信した宛先端末が、近接端末リストの情報を含んだ探索応答パケットを生成してブロードキャストするステップと、それを受信した各無線端末が、それの近接情報部に自端末のＩＤが含まれていると判断した場合にそれをブロードキャストするステップと、それを受信した送信元端末が、それの情報に基づいて、宛先端末毎に、宛先端末までの中継経路を表す経路情報テーブルを更新するステップとを含む。【選択図】図１
2007181056.tif 000002
【特許請求の範囲】
【請求項１】
複数の無線端末がマルチホップ通信により情報伝達する通信網において経路を選択するための経路選択方法であって、
送信元端末が宛先端末を指定して経路探索パケットをブロードキャストするステップと、
前記経路探索パケットを受信した各無線端末がさらなるブロードキャストにより宛先端末まで中継するステップと、
前記経路探索パケットを受信したときに、各無線端末が、当該経路探索パケットを送信した無線端末のＩＤを近接端末リストに登録するステップと、
前記経路探索パケットを受信した前記宛先端末が、近接端末リストの情報を含んだ探索応答パケットを生成してブロードキャストするステップと、
前記探索応答パケットを受信した各無線端末が、当該探索応答パケットの近接情報部に自端末のＩＤが含まれているかを判断し、含まれている場合に前記探索応答パケットをブロードキャストするステップと、
前記探索応答パケットを受信した送信元端末が、当該探索応答パケットの情報に基づいて、宛先端末毎に、宛先端末までの中継経路を表す経路情報テーブルを更新するステップと
を含むことを特徴とする経路選択方法。
【請求項２】
前記各無線端末が受信した前記探索応答パケットをブロードキャストするステップは、
当該探索応答パケットの中継可能な残り回数を格納するＴＴＬを参照して、転送可能であるかを判断し、ＴＴＬが０であれば探索応答パケットを破棄するステップと、
当該探索応答パケットのシーケンス番号を参照して、既に受信済みの探索応答パケットであるかを判断し、未受信であれば、当該探索応答パケットの近接情報部を自端末の近接端末リストで更新し、当該探索応答パケットが中継されてきた経路を示す中継情報部に自端末のＩＤを追加したコピーパケットをプロードキャストするステップと、
当該探索応答パケットの中継情報部を参照して自端末のＩＤが含まれていないことから未だ自端末を経由していない探索応答パケットであると判断するステップと、
自端末を経由していない場合に前記経路情報テーブルを更新するステップと
を含むことを特徴とする請求項１に記載の経路選択方法。
【請求項３】
前記経路情報テーブルを更新するステップは、
受信した前記探索応答パケットの宛先端末とブロードキャストにより中継された回数を示すホップ数とを参照し、前記経路情報テーブルの当該宛先端末の既登録されている複数の中継経路と比較し、ホップ数が既登録の中継経路より少なければ、当該パケットの中継経路を経路情報テーブルにホップ数順にソートし直して登録し、最大登録数を超えた場合はソート最下位を破棄するステップ
を含むことを特徴とする請求項２に記載の経路選択方法。
【請求項４】
前記各無線端末は、前記経路情報テーブルの中継経路を参照して、宛先端末までの中継経路を含んだデータパケットを送信するステップと、
前記データパケットを受信した無線端末が当該データパケットの中継情報部を参照して次に送信する無線端末を認識し送信するステップと、
当該データパケットを送信したときに、ある無線端末と別の無線端末との間で通信不能に至った場合、通信不能の無線端末を使用しない中継経路を自端末の前記経路情報テーブルから検索し、該当する中継経路があるときに、その中継経路に置き換えて当該データパケットを更新し、新たな中継経路を使用してデータパケットを送信するステップと
を含むことを特徴とする請求項１ないし３のいずれか１項に記載の経路選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は経路選択方法に関し、特に、マルチホップ通信網の経路選択方法に関する。
【背景技術】
【０００２】
マルチホップ型の無線通信網（以下、マルチホップ通信網と称する）とは、複数の無線端末が、ある特定の領域（半径数百メートル程度）に散在しているときに、任意の無線端末間で通信を直接行うことが可能で、直接電波が到達しない無線端末間においては、その間に位置する無線端末が中継をすることで通信経路を確立し通信を可能にする通信網のことである。
【０００３】
図１３に従来のマルチホップ通信網での経路選択の概要を示す。
送信元端末となる無線端末Ｎｓは、自端末の固有識別情報であるＩＤと、宛先端末となる無線端末Ｎｔの固有識別情報であるＩＤと、シーケンス番号を格納したＲＲＥＱ（Ｒｏｕｔｅ  Ｒｅｑｕｅｓｔ）パケットとを電波到達範囲内の無線端末にブロードキャストする。ＲＲＥＱパケットを受信した各無線端末は、自端末のＩＤをパケットの中継経路情報に追加して、電波到達範囲内の無線端末にさらにブロードキャストする。こうして無線端末Ｎｔに到達するまで、ブロードキャストを繰り返してパケットを中継する。この際、ＲＲＥＱパケットを受信した端末は、既受信のシーケンス番号であれば、そのＲＲＥＱパケットを破棄する。
【０００４】
ＲＲＥＱパケットを受信した無線端末Ｎｔは、自端末のＩＤと、ＲＲＥＱパケットの送信元である無線端末ＮｓのＩＤと、シーケンス番号及び中継経路情報を格納したＲＲＥＰ（Ｒｏｕｔｅ  Ｒｅｐｌｙ）パケットを、中継経路情報から知り得る次ホップの無線端末にユニキャストする。ＲＲＥＰパケットを受信した無線端末もまた中継経路情報から次ホップの無線端末を知り、次ホップの無線端末にユニキャストする。こうして無線端末Ｎｓまで、ＲＲＥＱパケットの中継経路を逆にたどってＲＲＥＰパケットを中継しながら送信する。
【０００５】
ＲＲＥＰパケットを受信することにより、無線端末Ｎｓは、無線端末Ｎｔまでの最短中継回数となるような単一の中継経路を確立する。無線端末Ｎｓは、上位層プロトコルからのデータに、自端末のＩＤ、無線端末ＮｔのＩＤ、確立した中継経路の情報、を付与したデータパケットを中継経路の次ホップの無線端末に送信する。各無線端末は、データパケットの中継経路情報を参照しながら無線端末Ｎｔまで、データパケットを送信していく。
【０００６】
ここで、使用中の経路に異常が発生してデータパケットの送達が不能になった場合、異常を検出した無線端末が経路エラーパケットを生成し、それを送信元端末までデータパケットの中継経路を逆にたどって中継送信していくことで通知する。経路エラーパケットを受信した送信元端末は、経路探索を開始して新たな中継経路を構築する。
【０００７】
このようなマルチホップ通信網の通信経路制御プロトコルのひとつとして、ＤＳＲ（Ｄｙｎａｍｉｃ  Ｓｏｕｒｃｅ  Ｒｏｕｔｉｎｇ）が開示されている（例えば、非特許文献１参照。）。
【０００８】
【非特許文献１】David B. Johnson “Routing in Ad Hoc Networks of Mobile Hosts”, Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, Dec. 1994
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上述のような従来のマルチホップ通信網では以下のような問題点があった。
個々の無線端末の無線装置が異なる場合や、環境により通信が片方向のみ可能な場合が存在し、このような状態では、宛先端末までＲＲＥＱパケットを中継することができても、逆方向の経路でＲＲＥＰパケットを送信する途中で通信不能となり送信元端末に到達しないことがある。従って、宛先端末が、ホップ数のみ或いは受信順のみを選択基準として、唯一のＲＲＥＰパケットを送信する従来例の方法では、中継経路を確立することができないという問題点があった。
【００１０】
また、従来例では、データパケットの送信において異常が発生した場合、経路エラーパケットにて送信元端末へ通知するが、経路の異常発生場所が宛先端末の近傍になるほど、経路エラーパケットが送信元端末へ到達するまでのステップが増加し、送信元端末からのデータパケットの再送に時間を要するという問題点があった。
【００１１】
この発明は、かかる問題点を解決するためになされたものであり、中継端末間の双方向通信を可能とする中継経路の探索を行い、経路断時にも送信元端末まで遡って再送することや経路の再構築をすることなく、データパケットの送信を継続することが可能なマルチホップ通信網の経路選択方法を提供することを目的としている。
【課題を解決するための手段】
【００１２】
この発明は、複数の無線端末がマルチホップ通信により情報伝達する通信網において経路を選択するための経路選択方法であって、送信元端末が宛先端末を指定して経路探索パケットをブロードキャストするステップと、前記経路探索パケットを受信した各無線端末がさらなるブロードキャストにより宛先端末まで中継するステップと、前記経路探索パケットを受信したときに、各無線端末が、当該経路探索パケットを送信した無線端末のＩＤを近接端末リストに登録するステップと、前記経路探索パケットを受信した前記宛先端末が、近接端末リストの情報を含んだ探索応答パケットを生成してブロードキャストするステップと、前記探索応答パケットを受信した各無線端末が、当該探索応答パケットの近接情報部に自端末のＩＤが含まれているかを判断し、含まれている場合に前記探索応答パケットをブロードキャストするステップと、前記探索応答パケットを受信した送信元端末が、当該探索応答パケットの情報に基づいて、宛先端末毎に、宛先端末までの中継経路を表す経路情報テーブルを更新するステップとを含むことを特徴とする経路選択方法である。
【発明の効果】
【００１３】
この発明は、複数の無線端末がマルチホップ通信により情報伝達する通信網において経路を選択するための経路選択方法であって、送信元端末が宛先端末を指定して経路探索パケットをブロードキャストするステップと、前記経路探索パケットを受信した各無線端末がさらなるブロードキャストにより宛先端末まで中継するステップと、前記経路探索パケットを受信したときに、各無線端末が、当該経路探索パケットを送信した無線端末のＩＤを近接端末リストに登録するステップと、前記経路探索パケットを受信した前記宛先端末が、近接端末リストの情報を含んだ探索応答パケットを生成してブロードキャストするステップと、前記探索応答パケットを受信した各無線端末が、当該探索応答パケットの近接情報部に自端末のＩＤが含まれているかを判断し、含まれている場合に前記探索応答パケットをブロードキャストするステップと、前記探索応答パケットを受信した送信元端末が、当該探索応答パケットの情報に基づいて、宛先端末毎に、宛先端末までの中継経路を表す経路情報テーブルを更新するステップとを含むことを特徴とする経路選択方法であるので、中継端末間の双方向通信を可能とする中継経路の探索を行い、経路断時にも送信元端末まで遡って再送することや経路の再構築をすることなく、データパケットの送信を継続することが可能である。
【発明を実施するための最良の形態】
【００１４】
実施の形態１．
図１はこの発明の実施の形態１であるマルチホップ通信網の各無線端末の配置構成を示す構成図である。この実施の形態１の無線通信網は、図１に示すように、複数の無線端末Ｎａ〜Ｎｇを備え、それぞれはある特定の領域に散在しており、当該領域内で同一周波数を使用して双方向の無線通信を行う。各無線端末は各々を識別するための重複しない唯一のＩＤがそれぞれ割り当てられている。また、各無線端末は、電波到達範囲にある送受信が可能な端末のＩＤの列挙からなる近接端末リストのデータをメモリに記憶している。
【００１５】
図１の例においては、Ａｄは無線端末Ｎｄの電波到達範囲であって、無線端末Ｎｂ、Ｎｃ、Ｎｆの３つが電波到達範囲Ａｄ内に存在して、無線端末Ｎｄからの通信を直接受信することが可能であり、無線端末Ｎａ、Ｎｅ、Ｎｇは電波到達範囲Ａｄ外に存在して無線端末Ｎｄからの通信を直接受信することが不可能である状態を想定している。
【００１６】
また、Ａｅは無線端末Ｎｅの電波到達範囲であって、無線端末Ｎｃ、Ｎｄ、Ｎｆ、Ｎｇの４つが電波到達範囲Ａｅ内に存在して無線端末Ｎｅからの通信を直接受信することが可能であり、無線端末Ｎａ、Ｎｂは電波到達範囲Ａｅ外に存在して無線端末Ｎｅからの通信を直接受信することが不可能である状態を想定している。また、図示はしていないが無線端末Ｎａ、Ｎｂ、Ｎｃ、Ｎｆ及びＮｇはそれぞれの電波到達範囲を有しており、無線端末Ｎａの電波到達範囲内に無線端末Ｎｂ、Ｎｃが存在し、無線端末Ｎｂの電波到達範囲内に無線端末Ｎａ、Ｎｃ、Ｎｄが存在し、無線端末Ｎｃの電波到達範囲内に無線端末Ｎａ、Ｎｂ、Ｎｄ、Ｎｅが存在し、無線端末Ｎｆの電波到達範囲内に無線端末Ｎｄ、Ｎｅ、Ｎｇが存在し、無線端末Ｎｇの電波到達範囲内に無線端末Ｎｅ、Ｎｆが存在するものとしている。
【００１７】
各無線端末は自身を送信元端末とし任意の無線端末を宛先端末としたデータパケット送信を行い、電波到達範囲内に存在しない場合はその間に位置する無線端末を中堅端末としてマルチホップによるデータパケット送信を行う。ここでは、無線端末Ｎａが送信元端末、Ｎｇが宛先端末、その他の端末が中継端末として機能する場合を例にして説明する。
【００１８】
図２は経路情報テーブルＨの構成例である。各無線端末は、図２に示すような経路情報テーブルＨを無線装置のメモリ上に持ち、宛先端末となる無線端末毎のＩＤ、及び、中継経路を保持する。中継経路は、宛先端末までのホップ数、及び、中継端末の各ＩＤから成る。格納できる宛先端末の最大数Ｈｍ、及び、宛先端末毎に保持できる中継経路の最大数Ｈｎは、各無線装置の性能に応じて任意である。
【００１９】
図３は経路探索パケットのフォーマット例である。図３において、経路探索パケットＥ１は、経路探索パケットであることを表すパケット種別ｅ１、送信元端末のＩＤを表す送信元端末ＩＤｅ２、宛先端末のＩＤを表す宛先端末ＩＤｅ３、パケットの同一性を識別するための一連の番号を表すシーケンス番号ｅ４、パケットの中継可能な残り回数を表すＴＴＬｅ５（ＴＴＬ：Time  To  Live）、及び、パケットを送信した無線端末のＩＤを表す中継端末ＩＤｅ６で構成される。
【００２０】
図４は探索応答パケットのフォーマット例である。図４において、探索応答パケットＥ２は、探索応答パケットであることを表すパケット種別ｅ１、経路探索パケットの送信元端末のＩＤを表す送信元端末ＩＤｅ２、経路探索パケットの宛先端末のＩＤを表す宛先ＩＤｅ３、対象の経路探索パケットを識別するためのシーケンス番号ｅ４、パケットの中継可能な残り回数を表すＴＴＬｅ５、近接する無線端末を表す近接情報部ｅ６、及び、中継経路を表す中継情報部ｅ７で構成される。
【００２１】
近接情報部ｅ６は、以降に格納されている近接端末ＩＤの数を示す近接端末数ｅ６−１、探索応答パケットを中継した無線端末がパケット受信可能な無線端末の列挙である近接端末ＩＤ１ｅ６−２，ＩＤ２ｅ６−２，・・・からなる。中継情報部ｅ７は、以降に格納されている中継端末ＩＤの数を示すホップ数ｅ７−１、探索応答パケットが辿ってきた無線端末の列挙である中継端末ＩＤ１ｅ７−２，ＩＤ２ｅ７−３，・・・からなる。
【００２２】
図５はデータパケットのフォーマット例である。図５において、データパケットＥ３は、データパケットであることを示すパケット種別ｅ１、送信元端末のＩＤを表す送信元端末ＩＤｅ２、宛先端末のＩＤを表す宛先端末ＩＤｅ３、中継経路を表す中継情報部ｅ４、及び、上位層プロトコルからのデータを格納するデータ部ｅ５から構成される。
【００２３】
中継情報部ｅ４は、以降に格納されている中継端末ＩＤの数を示すホップ数ｅ４−１、次に送信する中継端末ＩＤを表す中継数ｅ４−２、及び、中継経路の無線端末の列挙を示す中継端末ＩＤ１ｅ４−３，ＩＤ２ｅ４−４，・・・からなる。
【００２４】
図６は、本発明の実施の形態１における経路探索パケットの中継送信を表したものである。送信元端末である無線端末Ｎａは、送信元端末ＩＤ及び中継端末ＩＤに自端末のＩＤ、宛先端末ＩＤに無線端末ＮｇのＩＤ、シーケンス番号に同一性識別のための重複しない唯一な番号、及び、ＴＴＬにシステムで予め取り決めた値を格納した経路探索パケットＱａをブロードキャストする。
【００２５】
図９は、各無線端末が図３に示した経路探索パケットを受信したときの動作を示したフローチャートである。まず、無線端末Ｎｂは、ステップＳ１において、経路探索パケットＱａを受信した場合、ステップＳ２において、経路探索パケットＱａのシーケンス番号ｅ４から新規の経路探索であるか否かを判定し、新規の経路探索であることを認識した場合は、ステップＳ３において受信した経路探索パケットＱａの送信元の無線端末を全て列挙する近接端末リストＬをクリアする。ステップＳ４において、宛先端末ＩＤｅ３が自端末か否かを判定し、自端末ではないと判定した場合には、ステップＳ５において、ＴＴＬ（符号ｅ５）が０より大きいか否かを判定し、ＴＴＬが０より大きいことで中継対象と判断する。経路探索パケットＱａの内容から、ステップ６において、ＴＴＬを１減算し、ステップＳ７において、中継端末ＩＤに自端末のＩＤを格納した経路探索パケットＱｂを生成し、ステップＳ８において経路探索パケットＱｂをブロードキャストする。また、ステップＳ９において経路探索パケットＱａの中継端末ＩＤである無線端末ＮａのＩＤを近接端末リストＬに登録する。同様にして、無線端末Ｎｃは経路端末パケットＱｃを生成してブロードキャストし、無線端末ＮａのＩＤを近接端末リストＬに登録する。
【００２６】
経路探索パケットＱａの受信後に経路探索パケットＱｃを受信する無線端末Ｎｂは、図９において、ステップＳ２において、シーケンス番号からすでに受信済みの経路探索パケットであることを認識した場合は、パケットの送信を行わず、ステップＳ９において経路探索パケットＱｃの中継端末ＩＤである無線端末ＮｃのＩＤを近接端末リストＬに登録する。同様に、無線端末Ｎｃは、経路探索パケットＱｂの受信によるパケットの送信は行わず、近接端末リストＬに無線端末ＮｂのＩＤを登録する。
【００２７】
以下同様にして、宛先端末に到達するかＴＴＬが０になるまで経路探索パケットの中継送信が行われる。中継毎にＴＴＬを減ずることによりパケットの中継が無限に行われることを防止する。これにより無線端末Ｎｂ〜Ｎｇは個々の経路探索パケットの受信によりそれぞれの電波到達範囲内にある無線端末のＩＤを近接端末リストに登録する。
【００２８】
ここで図６に示すように、無線端末Ｎｄは経路探索パケットＱｃの受信により経路探索パケットＱｄを送信し、無線端末Ｎｅは経路探索パケットＱｃの受信により経路探索パケットＱｅを送信し、無線端末Ｎｆは経路探索パケットＱｄの受信により経路探索パケットＱｆを送信したものとし、無線端末Ｎｇは経路探索パケットＮｅを最初に受信するものとする。図９において、ステップＳ１において経路探索パケットＱｅを受信した無線端末Ｎｇは、ステップＳ２においてシーケンス番号から新規の経路探索であることを認識し、ステップＳ３において近接端末リストをクリアする。ステップＳ４において経路探索パケットＮｅの宛先端末ＩＤが自端末を示していることから、ステップＳ１０において後続する同シーケンス番号の経路探索パケットの受信のため、システムで予め定めた送信タイマＴの期間待機する。
【００２９】
図７は、本発明の実施の形態１における図４に示した探索応答パケットの中継送信を表したものである。宛先端末である無線端末Ｎｇは送信タイマＴの満了により、送信元端末ＩＤに経路探索パケットのＩＤ、宛先端末ＩＤに自端末のＩＤ、シーケンス番号に経路探索パケットのシーケンス番号、ＴＴＬにシステムで予め取り決めた値、近接端末数に２、近接端末ＩＤに近接端末リストに登録されている無線端末Ｎｅ、ＮｆのＩＤの２個、及び、ホップ数に０を格納した経路探索パケットＰｇをブロードキャストする。経路探索パケットＰｇにはホップ数０により中継端末ＩＤは無い。
【００３０】
図１０は、各無線端末が探索応答パケットを受信したときの動作を示したフローチャートである。ステップＳ１１において、無線端末Ｎｅは探索応答パケットＰｇを受信した場合、ステップＳ１２において、先の経路探索パケットのシーケンス番号と一致するか確認し、一致した場合には、ステップＳ１３において、送信元が自端末でないことを確認する。自端末でなかった場合には、ステップＳ１４において、ＴＴＬが０より大きいか否かを判定し、０より大きいと判定することで中継可能であると認識され、ステップＳ１５において、近接情報部の近接端末ＩＤに自端末のＩＤが含まれていることで相互に送受信が可能であると判断する。ステップＳ１６において、新規に受信した探索応答パケットであるか否かを判定し、新規の応答受信であると判断したことから中継対象と判断し、探索応答パケットＰｇの内容から、ステップＳ１７において、ＴＴＬを１だけ減算し、ステップＳ１８において、近接端末数に３、近接端末ＩＤを近接端末リストに登録されている無線端末Ｎｃ、ＮｆのＩＤの２個に変更し、ステップＳ１９において、ホップ数を１加算、中継端末ＩＤに自端末のＩＤを追加した探索応答パケットＰｅを生成し、ステップＳ２０において、探索応答パケットＰｅをブロードキャストする。
【００３１】
また、自端末が保持している内容より新規性があることから、探索応答パケットの中継情報が利用可能であれば、自端末の経路情報テーブルを更新する。すなわち、ステップＳ２１において探索応答パケットの宛先端末に該当するＩＤが、経路情報テーブルの宛先端末ＩＤに登録されているか、または、登録に空きがあるかを判定し、そうであれば、折り返しで受信したものを除くため、ステップＳ２２において、中継情報部の中継端末ＩＤに自端末のＩＤが含まれているか否かを判定し、含まれていなければ、ステップＳ２３において新規の探索応答パケットであるか否かを判定し、新規の応答受信であれば、ステップＳ２４において経路探索テーブルの当該宛先端末の情報を一旦クリアし、ステップＳ２５において、経路情報テーブルの当該宛先端末の登録経路に空きがあるか、または、探索応答パケットのホップ数が既登録経路のホップ数未満かを判定する。この場合は、先のステップＳ２４においてクリアしたため空きがあるので、ステップＳ２６において探索応答パケットＰｇの中継経路情報からホップ数１、中継端末ＩＤ無しを登録する。同様にして、無線端末Ｎｆは、探索応答パケットＰｆを生成してブロードキャストし、宛先端末Ｎｇ、ホップ数１、中継端末ＩＤ無しの中継経路を経路情報テーブルに登録する。
【００３２】
探索応答パケットＰｇの受信後に探索応答パケットＰｆを受信する無線端末Ｎｅは、図１０において、ステップＳ１６において既に受信済みの探索応答パケットであることを認識しパケットの送信は行わず経路情報テーブルヘの登録を行い、ステップＳ２３において新規の受信ではないので経路情報テーブルのクリアを行わず、ステップＳ２５において探索応答パケットのホップ数が既登録の中継経路のホップ数未満であるか登録に空きがあれば、ステップＳ２６においてホップ数２、中継端末ＩＤに無線端末ＮｆのＩＤの中継経路を追加し、ホップ数順で中継経路をソートして登録し、登録数Ｈｎを越える中継経路は破棄する。
【００３３】
ここで、図７に示すように無線端末Ｎｄにて、探索応答パケットＰｅを探索応答パケットＰｆより先に受信したとする。
図１０において、無線端末Ｎｄは探索応答パケットＰｅの受信により、ステップＳ１５において近接情報部の近接端末ＩＤに自端末のＩＤに含まれていないことから、探索応答パケットＰｅを破棄する。
続いて、無線端末Ｎｄは探索応答パケットＰｆの受信により、ステップＳ１５において近接情報部の近接端末ＩＤに自端末のＩＤが含まれており、先の探索応答パケットＰｅを破棄していることからステップＳ１６において新規のパケット受信と判断する。これにより、探索応答パケットＰｆの内容からＴＴＬを１減算、ホップ数を１加算、中継端末ＩＤに自端末のＩＤを追加し、近接端末数に４、近接端末ＩＤに近接端末リストに登録されている無線端末Ｎｂ、Ｎｃ、Ｎｅ、ＮｆのＩＤの４ヶに変更した探索応答パケットＰｄをブロードキャストし、宛先端末Ｎｇ、ホップ数２、中継端末ＩＤに無線端末Ｎｆの中継経路を経路情報テーブルに登録する。
【００３４】
以下同様にして、送信元端末に到達するかＴＴＬが０になるまで探索応答パケットの中継送信が行われる。中継毎にＴＴＬを減ずることによりパケットの中継が無限に行われることを防止する。
図１０において、無線端末Ｎａは、ステップＳ１１において探索応答パケットの受信により、ステップＳ１２において経路探索パケットとシーケンス番号の一致を確認し、ステップＳ１３において送信元が自端末であることから経路の登録を行う。ステップＳ２３において、最初に探索応答パケットを受信したと判断した際には、ステップＳ２４において経路情報テーブルの対象となる宛先端末の中継経路の登録を一旦クリアする。ステップＳ２５において、探索応答パケット中のホップ数が既登録の中継経路のホップ数未満であるか、あるいは、登録に空きがあるか判断し、それであれば、ステップＳ２６において探索応答パケットのホップ数、中継端末ＩＤを経路情報テーブルに追加し、ホップ数順で中継経路をソートして登録し、登録数Ｈｎを越える中継経路は破棄する。
【００３５】
以上の方法により、経路探索の発信元である無線端末、及び、中継経路上にある無線端末が、それぞれ相互に送受信できる複数の中継経路を得ることができる。
【００３６】
図８は図５に示したデータパケットの中継送信を表したものである。
経路探索により無線端末Ｎｇへの中継経路を確立している無線端末Ｎａは、送信元端末ＩＤに自端末のＩＤ、宛先端末ＩＤに無線端末ＮｇのＩＤ、中継数に０、経路情報テーブルに登録されている中継経路からホップ数に２、同じく中継端末ＩＤに無線端末Ｎｃ、ＮｅのＩＤの２ヶ、及び、上位層プロトコルからのデータをデータ部に格納したデータパケットＤａを無線端末Ｎｃヘユニキャストする。
【００３７】
図１１は、各無線端末が図５に示したデータパケットを受信したときの動作を示したフローチャートである。図１１において、無線端末ＮｃはステップＳ２７においてデータパケットＤａを受信した場合、ステップＳ２８において宛先端末ＩＤが自端末でないことから中継対象とする。データパケットＤａの内容から、ステップＳ２９において中継数を１加算したデータパケットＤｃを生成する。ステップＳ３０において中継数＋１で示される中継端末ＩＤである無線端末ＮｅヘデータパケットＤｃをユニキャストし、ステップＳ３１において送信成功により中継を終了する。
同様にして、無線端末Ｎｅは受信したデータパケットＤｃを中継情報部から次が宛先端末であることを識別し、中継数を１加算したデータパケットＤｅを無線端末Ｎｇにユニキャストする。
無線端末ＮｇはステップＳ２７においてデータパケットＤｅを受信した場合、ステップＳ２８において宛先端末ＩＤが自端末であることからデータパケットＤｅに格納されているデータ部を取り出して上位層プロトコルヘ通知する。
以上により、データパケットの中継送信を行う。
【００３８】
この発明の実施の形態１のように、無線端末Ｎａ乃至Ｎｇがパケットを中継送信することで相互の電波到達範囲内にない無線端末間での通信機能を実現する。
【００３９】
以上のように、本実施の形態１によれば、マルチホップ通信網の通信経路の探索において、各無線端末が自端末が受信可能な他の無線端末からの通信を通知しながら通信経路を構築していくことで、送信元端末から宛先端末まで、中継に関わる各無線端末間が相互に送受信できる経路を一回の探索で確立することができる。これにより、無線装置の種類が混在するなど、それぞれの無線端末の電波到達距離が均一でないマルチホップ通信網においても各無線端末間にＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）のようなコネクション方式の通信プロトコルを使用してのデータ伝送ができる。また、宛先端末から送信元端末への応答をブロードキャストにより中継することで、送信元端末から宛先端末までの中継経路を複数確立することができる。
【００４０】
また、経路探索を行った無線端末に限らず、中継経路上の無線端末が情報を更新することにより、個々の無線端末が経路探索を行う必要が無くなり、通信網の負荷軽減の効果がある。
【００４１】
実施の形態２．
図１２は本発明の実施の形態２であるデータパケットの中継を表したものである。図１２では本発明の実施の形態１で示した無線端末Ｎａから無線端末Ｎｇへの経路探索が完了した後、無線端末Ｎｅが電波状態の変化や無線装置の故障等の発生により通信不可になった場合を想定する。ここで、無線端末Ｎａの経路情報テーブルには無線端末Ｎｇへの中継経路として、ホップ数が３、中継端末ＩＤが順にＮｃ、Ｎｅが登録されており、無線端末Ｎｃの経路情報テーブルには無線端末Ｎｇへの中継経路として、ホップ数２、中継端末ＩＤが無線端末Ｎｅという経路と、ホップ数３、中継端末ＩＤが順にＮｄ、Ｎｆという経路との２経路が登録されているものとする。
【００４２】
無線端末Ｎａは、送信元端末ＩＤに自端末のＩＤ、宛先端末ＩＤに無線端末ＮｇのＩＤ、中継数に０、経路情報テーブルに登録されている中継経路からホップ数に２、同じく中継端末ＩＤに無線端末Ｎｃ、ＮｅのＩＤの２ヶ、及び、上位層プロトコルからのデータをデータ部に格納したデータパケットＤａ１を無線端末Ｎｃヘユニキャストする。
【００４３】
図１１において、無線端末ＮｃはデータパケットＤａ１の受信により、本発明の実施の形態１と同様にデータパケットＤｃ１を生成する。ステップＳ３０において無線端末ＮｅヘデータパケットＤｃ１をユニキャストするが、ステップＳ３０において通信不可であるため送信に失敗する。これによりステップＳ３２においてデータパケットＤｃ１の宛先端末である無線端末Ｎｇの中継経路が経路情報テーブルに登録されているかを検索し、ステップＳ３３においてホップ数３、中継端末ＩＤが順にＮｄ、Ｎｆの中継経路を得る。ステップＳ３４においてデータパケットＤｃ１の中継情報部のホップ数及び中継端末ＩＤを、ステップＳ３３にて得た中継端末ＩＤに置き換え、中継数を０としたデータパケットＤｃ２を、新たな中継情報部での次の中継端末である無線端末Ｎｄにユニキャストする。
【００４４】
データパケットＤｃ２の新たな中継経路に従い、無線端末Ｎｄは無線端末Ｎｆへ、無線端末Ｎｆは無線端末Ｎｇへ、データパケットをユニキャストし、宛先端末までデータパケットの中継を行う。
【００４５】
以上により、中継経路上の端末へ送信できなかった場合に代替の中継経路を使用してデータパケットの中継を行う。
【００４６】
ここで、無線端末ＮｃがデータパケットＤｃ２の送信に、ステップＳ３５において失敗した場合、ステップＳ３６において該当中継経路を経路情報テーブルの最下位にしてソートすることで再利用を制限する。
【００４７】
この発明の実施の形態２のように、中継経路上の無線端末がパケットの送信に失敗した場合、先だって行われている経路探索により保持している複数の中継経路から、代替中継経路を選択してパケットの中継を継続する機能を実現する。
【００４８】
以上のように、本実施の形態においても、上記の実施の形態１と同様の効果が得られるとともに、さらに、本実施の形態においては、予め中継経路上の無線端末が複数の異なる中継経路を保持していることにより、パケットの送信に失敗した場合に、送信元端末にまで戻って再度経路探索やパケット再送を行うことなく、代替経路を使用してパケットの送信を継続することができる。各無線端末が据え付け型であるなどで通信網トポロジーがほとんど変化がない場合に有効であり、これにより、通信異常が発生した場合の遅延を少なくしたデータ伝送に効果がある。
【図面の簡単な説明】
【００４９】
【図１】本発明の実施の形態１における複数の無線端末によるマルチホップ通信網の構成を示す構成図である。
【図２】本発明の実施の形態１における経路情報テーブルを示す説明図である。
【図３】本発明の実施の形態１における経路探索パケットを示す説明図である。
【図４】本発明の実施の形態１における探索応答パケットを示す説明図である。
【図５】本発明の実施の形態１におけるデータパケットを示す説明図である。
【図６】本発明の実施の形態１における経路探索パケットの中継を示す説明図である。
【図７】本発明の実施の形態１における探索応答パケットの中継を示す説明図である。
【図８】本発明の実施の形態１におけるデータパケットの中継を示す説明図である。
【図９】本発明の実施の形態１における経路探索パケットの受信処理を示すフローチャートである。
【図１０】本発明の実施の形態１における探索応答パケットの受信処理を示すフローチャートである。
【図１１】本発明の実施の形態１におけるデータパケットの受信処理を示すフローチャートである。
【図１２】本発明の実施の形態２におけるデータパケットの中継を示す説明図である。
【図１３】従来のマルチホップ通信網の経路探索を示す説明図である。
【符号の説明】
【００５０】
Ａｄ，Ａｅ  電波到達範囲、Ｎａ，Ｎｂ，Ｎｃ，Ｎｄ，Ｎｅ，Ｎｆ，Ｎｇ  無線端末、Ｎｒ１，Ｎｒ２，Ｎｒ３，Ｎｒ４，Ｎｒ５  無線端末、Ｎｓ  無線端末（送信元端末）、Ｎｔ  無線端末（宛先端末）。
【図１】
2007181056.tif 000003
【図２】
2007181056.tif 000004
【図３】
2007181056.tif 000005
【図４】
2007181056.tif 000006
【図５】
2007181056.tif 000007
【図６】
2007181056.tif 000008
【図７】
2007181056.tif 000009
【図８】
2007181056.tif 000010
【図９】
2007181056.tif 000011
【図１０】
2007181056.tif 000012
【図１１】
2007181056.tif 000013
【図１２】
2007181056.tif 000014
【図１３】
2007181056.tif 000015