(57)【要約】【課題】パス要求メッセージによる通信帯域の圧迫が生じにくいようにしたアドホック網のルーティング方法を提供する。【解決手段】アドホック網のルーティング方法において、送信元ノードからブロードキャストされたパス接続要求メッセージを中継するノードが、▲１▼パス接続要求メッセージの受信数を計数して、中継ノードの混雑具合を定量的に把握する手順（ステップＳ２０２）、▲２▼計数結果に基づいて、受信したパス接続要求メッセージの中継確率を設定する手順（ステップＳ２０２）、▲３▼受信した各パス接続要求メッセージの中継を、前記中継確率に基づいて選択的に禁止する手順（ステップＳ２０９）、を実行する。【選択図】　　　　図２
2004064678.tif 000002
【特許請求の範囲】
【請求項１】
複数の無線ノードが自律分散的に無線ネットワークを構築し、送信元ノードが宛先ノードを指定してブロードキャストしたパス接続要求メッセージを他の無線ノードが中継してブロードキャストし、前記宛先ノードが前記パス接続要求メッセージに応答してパス接続応答メッセージを前記送信元ノード宛にユニキャストするアドホック網のルーティング方法において、
前記パス接続要求メッセージを中継するノードが、
パス接続要求メッセージの受信数を計数する手順と、
前記計数結果に基づいて、前記受信したパス接続要求メッセージの中継確率を設定する手順と、
受信した各パス接続要求メッセージの中継を、前記中継確率に基づいて選択的に禁止する手順とを含むことを特徴とするアドホック網のルーティング方法。
【請求項２】
前記中継ノードは、単位時間当たりのパス接続要求メッセージの受信数が多いほど前記中継確率を低くすることを特徴とする請求項１に記載のアドホック網のルーティング方法。
【請求項３】
前記送信元ノードは、ブロードキャストしたパス接続要求メッセージに対してパス接続応答メッセージを受信できないときに、前記パス接続要求メッセージを強制モードでブロードキャストする手順を具備し、
前記中継ノードは、前記強制モードでブロードキャストされたパス接続要求メッセージを、前記中継確率にかかわらず中継することを特徴とする請求項１または２に記載のアドホック網のルーティング方法。
【請求項４】
前記送信元ノードは、ブロードキャストしたパス接続要求メッセージに対してパス接続応答メッセージを受信できないときに、前記パス接続要求メッセージを強制モードでブロードキャストする手順を具備し、
前記中継ノードは、前記強制モードでブロードキャストされたパス接続要求メッセージを受信すると、前記中継確立を増率することを特徴とする請求項１または２に記載のアドホック網のルーティング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、アドホック網のルーティング方法に係り、特に、送信元ノードが宛先ノードに向けてブロードキャストするパス接続要求メッセージによる帯域圧迫を最小限に抑えられるアドホック網のルーティング方法に関する。
【０００２】
【従来の技術】
無線通信技術を採用した移動ノードにおいて、既存のインターネットなどのインフラ網に接続することなく、ノード間で自律的にネットワークを構成して通信を行う形態のネットワーク、すなわちアドホック網が提案されている。
【０００３】
図１１は、アドホック網の構成例を示した図であり、丸印は移動ノードＮａ、Ｎｂ…Ｎｇを示し、その外周に記載した同心円は各移動ノードの無線カバレッジを示している。各移動ノードはルーティング機能を備え、宛先ノードまでの経路を作成してデータを配信する。
【０００４】
このような構成のアドホック網において、いずれかのノードでデータ送信要求が発生した時点で宛先までの経路を確立するオンデマンド型のルーティング方式では、初めに送信元ノードが宛先ノードまでの経路（パス）を確立するための制御メッセージとして、パス接続要求メッセージをブロードキャスト（広報）する。このパス接続要求メッセージは、これを受信した各中継ノードが再ブロードキャストを繰り返すことにより宛先ノードまで伝搬される。
【０００５】
【発明が解決しようとする課題】
上記した従来のパス確立方法では、各ノードはパス接続要求メッセージがループを形成することを防ぐ機能として、自ノードがブロードキャストしたパス接続要求メッセージを受信したときには、その再ブロードキャストを禁止する機能は備えているものの、新規に受信したメッセージは常に再ブロードキャストする。このため、図１２に矢印で示したように、ノード数が多い場合には、同じパス接続要求メッセージがネットワーク上を多数流れる可能性が高くなるので、これらのメッセージが通信帯域を圧迫してしまうという技術課題があった。
【０００６】
本発明の目的は、上記した従来技術の課題を解決し、パス接続要求メッセージによる通信帯域の圧迫が生じにくいようにしたアドホック網のルーティング方法を提供することにある。
【０００７】
【課題を解決するための手段】
上記した目的を達成するために、本発明は、複数の無線ノードが自律分散的に無線ネットワークを構築するアドホック網のルーティング方法において、送信元ノードからブロードキャストされたパス接続要求メッセージを中継するノードが、以下の手順を実行することを特徴とする。
（１）パス接続要求メッセージの受信数を計数する手順
（２）計数結果に基づいて、受信したパス接続要求メッセージの中継確率を設定する手順
（３）受信した各パス接続要求メッセージの中継を、前記中継確率に基づいて選択的に禁止する手順
【０００８】
上記した特徴を備えたことにより、本発明によれば、各中継ノードはパス接続要求メッセージの受信数を計数することにより無線ノードの混雑具合を定量的に把握することができる。そして、無線ノードの混雑度が高ければパス接続要求メッセージが重複して送受される可能性が高いので、各中継ノードは、受信したパス接続要求メッセージの一部について、その再ブロードキャストを禁止する。これにより、パス接続要求メッセージの機能を損なうことなく通信帯域の圧迫が抑制される。
【０００９】
【発明の実施の形態】
以下、図面を参照して本発明の好ましい実施の形態について詳細に説明する。ここでは、図１１に示したネットワーク構成において、ノードＮａが送信元ノード、ノードＮｄが宛先ノード、他のノードが中継ノードとして機能する場合を例にして説明する。
【００１０】
図１は、送信ノードＮａにおけるパス接続要求メッセージの送信動作を示したフローチャートである。ステップＳ１０１において、上位層であるアプリケーション層からパケット送信要求を受信したノードＮａは送信元ノードとして振る舞い、ステップＳ１０２において、指定された宛先ノードＮｄまでのパスが既に確立されているか否かを判定する。パスが確立されていなければステップＳ１０３へ進み、パス接続要求メッセージの送信回数としての試行回数Ｋに、初期値として「１」をセットする。ステップＳ１０４では、ノードＮｄを宛先とするパス接続要求メッセージをブロードキャストする。
【００１１】
ステップＳ１０５では、前記パス接続要求に応答して宛先ノードＮｄから自ノード宛にユニキャストされるパス接続応答メッセージの受信の有無を判定し、パス接続応答メッセージが受信されるまではステップＳ１０６へ進む。ステップＳ１０６では、前記パス接続要求メッセージを送出してからの経過時間が所定の再試行待ち時間を経過したか否かが判定され、経過するまではステップＳ１０５へ戻る。
【００１２】
その後、再試行待ち時間が経過し、これがステップＳ１０６で検知されると、ステップＳ１０７では、前記試行回数Ｋが再試行上限値Ｋｍａｘ１を超えたか否かが判定され、最初は超えていないと判定されるので、ステップＳ１１２において前記試行回数Ｋがカウントアップされ、その後、ステップＳ１０４へ戻って前記パス接続要求メッセージが改めてブロードキャストされる。
【００１３】
その後も、前記ステップＳ１０５においてパス接続応答メッセージの受信が検知されるまでは、再試行待ち時間が経過するごとにパス接続要求メッセージが再ブロードキャストされる。前記ステップＳ１０７において、試行回数Ｋが再試行上限値Ｋｍａｘ１に達したと判定されると、ステップＳ１０８では、前記試行回数Ｋが強制モード上限値Ｋｍａｘ２を超えたか否かが判定される。試行回数Ｋが強制モード上限値Ｋｍａｘ２を下回っていれば、ステップＳ１１１において動作モードを強制モードに変更した後、前記ステップＳ１１２へ進む。
【００１４】
これに対して、試行回数Ｋが強制モード上限値Ｋｍａｘ２を下回っていなければ、ステップＳ１０９においてパケットが破棄される。ステップＳ１１０では、パケットを破棄した旨のメッセージが上位層へ通知される。
【００１５】
次いで、図２のフローチャートを参照して、前記パス接続要求メッセージを受信した各中継ノードおよび宛先ノードの動作を説明する。
【００１６】
ステップＳ２０１において、前記パス接続要求メッセージを受信したノードは、ステップＳ２０２において、このパス接続要求メッセージを中継するか否かの判定材料となる中継確率を更新するための中継確率更新処理を実行する。
【００１７】
図３は、前記中継確率更新処理の動作を示したフローチャートであり、図４は、その動作を模式的に表現した図である。
【００１８】
ステップＳ４０１では、所定周期Δｔを繰り返しカウントするΔｔカウンタがタイムアウトしたか否かが判定される。タイムアウトしていなければステップＳ４０４へ進み、今回の所定周期Δｔ内に受信したパス接続要求メッセージの回数を代表する今回受信回数Ｎｊが「１」だけインクリメントされて更新される。これに対して、前記ステップＳ４０１において、Δｔカウンタがタイムアウトしていると判定されると、ステップＳ４０２において、前記今回受信回数Ｎｊが前回受信回数Ｎｊ−１として登録される。
【００１９】
ステップＳ４０３では、前記今回受信回数Ｎｊがリセットされる。ステップＳ４０４では、前記と同様に、今回受信回数Ｎｊが「１」だけインクリメントされて「１」に更新される。この結果、図４にも示したように、今回受信回数Ｎｊには今回の所定周期Δｔ内におけるパス接続要求メッセージの受信回数が登録される。同様に、前回受信回数Ｎｊ−１には前回の所定周期Δｔ内におけるパス接続要求メッセージの受信回数が登録される。
【００２０】
ステップＳ４０５では、次式（１）に基づいて、パス接続要求メッセージの平均受信回数ＡＶＥ（Ｎｊ）が算出される。なお、定数Ｇ（０＜Ｇ＜１）は、平均受信回数ＡＶＥ（Ｎｊ）に対して今回受信回数Ｎｊを前回受信回数Ｎｊ−１よりも強く反映させるための係数である。
ＡＶＥ（Ｎｊ）＝（１−Ｇ）×ＡＶＥ（Ｎｊ−１）＋Ｇ×Ｎｊ　…（１）
【００２１】
ステップＳ４０６では、前記平均受信回数ＡＶＥ（Ｎｊ）を所定の関数ｆに適用して、今回受信したパス接続要求メッセージの中継確率ｐ（ｊ）を求める。前記関数ｆ（ｊ）は、図５に示したような［０，１］の単純減少関数であり、例えば次式（２）で与えられる。
ｆ（ｘ）＝１／（ｘ＋１）　但し、ｘ≧０　…　（２）
【００２２】
図２に戻り、ステップＳ２０３では、前記メッセージの宛先が自ノードであるか否かを判定する。宛先が自ノード以外であれば中継ノードとして振る舞い、ステップＳ２０４において、指定された宛先までのパスが既に確立されているか否かを判定する。宛先までのパスが未だ確立されていなければ、ステップＳ２０５において、前記受信したパス接続要求メッセージが新規であるか否かを判定する。本実施形態では、パス接続要求メッセージに登録されている送信元ノードおよび宛先ノードの少なくとも一方が、これより先に受信したパス接続要求メッセージの送信元ノードおよび宛先ノードと異なっていれば、これを新規のメッセージと判断してステップＳ２０６へ進む。
【００２３】
ステップＳ２０６では、受信したパス接続要求メッセージを前記中継確率ｐ（ｊ）とは無関係に強制的に中継させる「強制モード」が指定されているか否かを判定する。強制モードが指定されていれば、ステップＳ２０７において、前記ステップＳ２０２で更新された中継確率ｐ（ｊ）が増率される。ステップＳ２０８では、図６に示したように、当該メッセージを中継して自ノードへ転送してきた隣接ノードを、送信元へデータを送信する際の次ホップとして経路表へ登録する。すなわち、送信元ノードＮａがブロードキャストしたパス接続要求メッセージをノードＮｂから受信したノードＮｃは、ノードＮａを宛先とするパケットの次ポップとしてノードＮｂを登録する。ステップＳ２１０では、パス接続要求メッセージを再ブロードキャストする。
【００２４】
一方、前記ステップＳ２０６において、「強制モード」ではないと判定されると、ステップＳ２０９へ進む。ステップＳ２０９では、前記更新された中継確率ｐ（ｊ）に基づいて、今回受信したメッセージを中継するか否かを判定する。本実施形態では、図７に示したように［０，１］の乱数Ｒを発生させ、この乱数Ｒが前記中継確率ｐ（ｊ）を下回れば、メッセージを中継するために前記ステップＳ２０８へ進み、乱数Ｒが中継確率ｐ（ｊ）を上回れば、中継を禁止すべく当該処理を終了する。
【００２５】
また、前記ステップＳ２０３において、受信したパス接続要求メッセージの宛先が自ノードであれば宛先ノードとして振る舞い、ステップＳ２１１において、受信したパス接続要求メッセージに対するパス接続応答メッセージを送信元ノードＮａ宛にユニキャストする。さらに、図８に示したように、ノードＮｂ、Ｎｄ間に既にパスが確立されているときのノードＮｂがノードＮｄを宛先とするパス接続要求メッセージを受信したときも、前記ステップＳ２０４において、宛先までのパスが既に確立されていると判断してステップＳ２１１へ進む。
【００２６】
図１３は、本実施形態におけるパス接続要求メッセージの中継状況を模式的に示した図であり、図１２の従来技術に較べて、パス接続要求メッセージの総数が減ぜられている。
【００２７】
図９は、前記宛先ノードＮｄから返信されたパス接続応答メッセージを受信した各中継ノードの動作を示したフローチャートである。
【００２８】
ステップＳ３０１においてパス接続応答メッセージを受信すると、ステップＳ３０２では、図１０に示したように、当該パス接続応答メッセージを中継した隣接ノードを、宛先へパケットを送信する際の次ホップとして経路表に登録する。すなわち、宛先ノードＮｄからユニキャストされたパス接続応答メッセージをノードＮｃから受信したノードＮｂは、ノードＮｄを宛先とするパケットの次ポップとしてノードＮｃを登録する。なお、選択されなかったパスが経由する各ノードの経路表は一定時間後に削除される。ステップＳ３０３では、前記パス接続応答メッセージが前記経路表に基づいて次ホップへ送信される。
【００２９】
次いで、前記図１のフローチャートへ戻り、前記パス接続応答メッセージを受信した送信元ノードの動作を説明する。
【００３０】
ステップＳ１０５においてパス接続応答メッセージを受信するとステップＳ１１３へ進み、当該パス接続応答メッセージに登録されている経路情報を自ノードの経路表に書き込む。これにより、ノードＮａ、Ｎｄ間にパスが確立される。ステップＳ１１４では、送信要求のあったパケットが前記確立されたパスを利用して宛先へ送信される。
【００３１】
【発明の効果】
本発明によれば、各中継ノードはパス接続要求メッセージの受信数を計数することにより無線ノードの混雑具合を定量的に把握することができる。そして、無線ノードの混雑度が高ければパス接続要求メッセージが重複して送受される可能性が高いので、各中継ノードは、受信したパス接続要求メッセージの一部について、その再ブロードキャストを禁止する。これにより、パス接続要求メッセージの機能を損なうことなく通信帯域の圧迫を抑制できる。
【図面の簡単な説明】
【図１】送信ノードがパス接続要求メッセージをブロードキャストする手順を示したフローチャートである。
【図２】パス接続要求メッセージを受信した中継ノードおよび宛先ノードの動作を示したフローチャートである。
【図３】中継確率更新処理の動作を示したフローチャートである。
【図４】中継確率更新処理の動作を模式的に示した図である。
【図５】関数ｆ（ｊ）の一例を示した図である。
【図６】パス接続要求メッセージに基づいて中継ノードが登録する経路情報の一例を示した図である。
【図７】中継確率ｐ（ｊ）に基づいてパス接続要求メッセージの中継の是非判定する方法を示した図である。
【図８】パス接続要求メッセージで要求されたパスが既に確立されている状態を模式的に示した図である。
【図９】パス接続応答メッセージを受信した各中継ノードの動作を示したフローチャートである。
【図１０】パス接続応答メッセージに基づいて中継ノードが登録する経路情報の一例を示した図である。
【図１１】アドホック網の構成例を示した図である。
【図１２】従来技術によるパス接続応答メッセージの中継状況を示した図である。
【図１３】本発明によるパス接続応答メッセージの中継状況を示した図である。
【符号の説明】Ｎａ、Ｎｂ、Ｎｃ、Ｎｄ、Ｎｅ、Ｎｆ、Ｎｇ…無線ノード
【図１】
2004064678.tif 000003
【図２】
2004064678.tif 000004
【図３】
2004064678.tif 000005
【図４】
2004064678.tif 000006
【図５】
2004064678.tif 000007
【図６】
2004064678.tif 000008
【図７】
2004064678.tif 000009
【図８】
2004064678.tif 000010
【図９】
2004064678.tif 000011
【図１０】
2004064678.tif 000012
【図１１】
2004064678.tif 000013
【図１２】
2004064678.tif 000014
【図１３】
2004064678.tif 000015