(57)【要約】【課題】アドホック網において、送信元ノードと宛先ノードとの間に最適パスを確立する。【解決手段】複数の無線ノードが自立分散的に無線ネットワークを構築するアドホック網において、送信元ノードからブロードキャストされたパス接続要求メッセージに、当該パス接続要求メッセージが辿ったパスの通信能力に関する情報を登録する手順と、経路の異なる複数のパス接続要求メッセージを受信した宛先ノードが、各パス接続要求メッセージに登録された通信能力情報に基づいて一のパスを選択する手順と、宛先ノードが、前記選択した一のパスに対してパス接続応答メッセージをユニキャストする手順とを含む。【選択図】　　　　図１
2004048478.tif 000002
【特許請求の範囲】
【請求項１】
複数の無線ノードが自立分散的に無線ネットワークを構築し、送信元ノードが宛先ノードを指定してブロードキャストしたパス接続要求メッセージを他の無線ノードが連携して宛先ノードまで中継し、前記宛先ノードが、前記パス接続要求メッセージに応答してパス接続応答メッセージを前記送信元ノード宛にユニキャストすることにより、前記送信元ノードと宛先ノードとの間にパスが確立されるアドホック網において、
各パス接続要求メッセージに、当該パス接続要求メッセージが辿ったパスの通信能力に関する情報を登録する手順と、
経路の異なる複数のパス接続要求メッセージを受信した宛先ノードが、各パス接続要求メッセージに登録された前記通信能力情報に基づいて一のパスを選択する手順と、
前記宛先ノードが、前記選択した一のパスに対してパス接続応答メッセージをユニキャストする手順とを含むことを特徴とするアドホック網のルーティング方法。
【請求項２】
前記通信能力情報を登録する手順は、
パス接続要求メッセージを中継する各ノードが、当該パス接続要求メッセージに既登録の通信能力情報を自ノードの通信能力に基づいて更新する手順と、
前記各中継ノードが、前記通信能力情報の更新されたパス接続要求メッセージを再ブロードキャストする手順とを含むことを特徴とする請求項１に記載のアドホック網のルーティング方法。
【請求項３】
前記各中継ノードが、
既に確立されているパスと同一のパスに関するパス接続応答メッセージを受信したときに、当該パス接続応答メッセージに登録されている通信能力情報を、前記既に確立されているパスに関する通信能力情報と比較する手順と、
前記パス接続応答メッセージに登録されているパスの通信能力が前記既に確立されているパスの通信能力よりも優れていると、前記パス接続応答メッセージをユニキャストすることにより、前記既に確立されているパスを新たなパスに変更する手順とを含むことを特徴とする請求項２に記載のアドホック網のルーティング方法。
【請求項４】
前記送信元ノードが、
既に確立されているパスに関するパス接続応答メッセージを受信したときに、当該パス接続応答メッセージに登録されている通信能力情報を、前記既に確立されているパスに関する通信能力情報と比較する手順と、
前記パス接続応答メッセージに登録されているパスの通信能力が前記既に確立されているパスの通信能力よりも優れていると、前記既に確立されているパスを新たなパスに変更する手順とを含むことを特徴とする請求項１ないし３のいずれかに記載のアドホック網のルーティング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、アドホック網のルーティング方法に係り、特に、送信元ノードと宛先ノードとの間に最適パスを確立するためのルーティング方法に関する。
【０００２】
【従来の技術】
無線通信技術を採用した移動ノードにおいて、既存のインターネットなどのインフラ網に接続することなく、ノード間で自立的にネットワークを構成して通信を行う形態のネットワーク、すなわちアドホック網が提案されている。
【０００３】
図９は、アドホック網の構成を示した図であり、丸印は移動ノードＮａ、Ｎｂ…Ｎｇを示し、その外周に記載した同心円は各移動ノードの無線カバレッジを示している。各移動ノードはルーティング機能を備え、宛先ノードまでの経路を作成してデータを配信する。
【０００４】
このような構成のアドホック網において、いずれかのノードでデータ送信要求が発生した時点で宛先までの経路を確立するルーティング方式（オンデマンド型のルーティング方式）では、宛先ノードまでの経路（パス）を確立するための制御メッセージを全てのノードがブロードキャスト（広報）することにより、このメッセージが宛先ノードまで伝搬される。
【０００５】
【発明が解決しようとする課題】
図１０において、ノードＮａからＮｄ宛にデータの送信要求が発生した場合、送信元ノードＮａから宛先ノードＮｄ宛にパス接続要求メッセージがブロードキャストされる。このメッセージは、例えばノードＮｂ、Ｎｃを中継してノードＮｄに至る第１パスと、ノードＮｅ、Ｎｆ、Ｎｇ、Ｎｃを中継して宛先ノードＮｄに至る第２パスとで伝達される。
【０００６】
このように複数のパスを経由してメッセージが宛先ノードＮｄへ届いた場合、宛先ノードでは、先に届いたメッセージのパスを選択してパス接続応答メッセージを送信元ノードに向けてユニキャスト（単一ノード宛）で転送する。これにより、送信ノードＮａと宛先ノードＮｄとの間にパスが確立されるので、これ以後は、当該パスを経由してデータ交換が行われる。しかしながら、到着順序の早いパス接続要求メッセージの辿ったパスが最適であるとは限らないため、上記した従来技術では、必ずしも最適パスが選択されるとは限らなかった。
【０００７】
さらに、図１１に示したように、送信元ノードＮａと宛先ノードＮｃとの間に既にパスが確立している状態で、ノードＮａがさらにノードＮｄに対してパス接続要求メッセージをブロードキャストしたような場合でも、宛先ノードＮｄでは最初に到着したパス接続要求メッセージに対して応答する可能性が高い。そして、図１１の例では、経由するノード数の少ないノードＮａ→Ｎｂ→Ｎｃ→Ｎｄ経由のメッセージが先に到着し、このパスが選択されるので、二つのパスが同一ノードＮｂ、Ｎｃを経由することになる。このため、複数のパスが同一ノードを経由することによるノードの過負荷や、トラヒックの集中によるデータスループットの劣化等が発生しやすいという技術課題があった。
【０００８】
本発明の目的は、上記した従来技術の課題を解決し、送信元ノードと宛先ノードとの間に常に最適パスを確立できるアドホック網のルーティング方法を提供することにある。
【０００９】
【課題を解決するための手段】
上記した目的を達成するために、本発明は、複数の無線ノードが自立分散的に無線ネットワークを構築するアドホック網において、送信元ノードが宛先ノードを指定してブロードキャストしたパス接続要求メッセージを他の無線ノードが連携して宛先ノードまで中継する手順と、各パス接続要求メッセージに、当該パス接続要求メッセージが辿ったパスの通信能力に関する情報を登録する手順と、経路の異なる複数のパス接続要求メッセージを受信した宛先ノードが、各パス接続要求メッセージに登録された前記通信能力情報に基づいて一のパスを選択する手順と、宛先ノードが、前記選択した一のパスに対してパス接続応答メッセージをユニキャストする手順とを含むことを特徴とする。
【００１０】
上記した特徴によれば、送信元および宛先が同一であって経路の異なる複数のパス接続要求メッセージを受信した宛先ノードは、各パス接続要求メッセージに登録されている通信能力情報に基づいて各パスを評価できるので、最適なパスを簡単に選択することができる。また、ネットワーク全体として見れば、複数のパスが確立される状況下でも、トラヒックが分散されて一部のノードへのパスの集中が防止されるので、ネットワークの利用効率が向上する。
【００１１】
【発明の実施の形態】
以下、図面を参照して本発明の好ましい実施の形態について詳細に説明する。図１は、本発明のルーティング方法の基本動作を説明するための図であり、無線移動ノードＮａ、Ｎｂ、Ｎｃ、Ｎｄ、Ｎｅ、Ｎｆ、Ｎｇがアドホック網を構成している。ここでは、ノードＮａが送信元ノード、ノードＮｄが宛先ノード、他のノードが中継ノードとして機能する場合を例にして説明する。
【００１２】
各ノードＮｉは自ノードのパス利用率Ｌｉを管理している。パス利用率Ｌｉは、各ノードＮｉにおいて利用可能なパスの本数Ｒｉと確立済みパスの本数ｒｉとの比であり、次式（１）で表される
Ｌｉ＝ｒｉ／Ｒｉ　…（１）
【００１３】
ここでは、ノードＮｂ、Ｎｃのパス利用率Ｌｂ、Ｌｃがいずれも「１」であり、他のノードＮｅ、Ｎｆ、Ｎｇのパス利用率Ｌｅ、Ｌｆ、Ｌｇがいずれも「０」であるものとして説明する。
【００１４】
送信元ノードＮａがノードＮｄを宛先としてブロードキャストしたパス接続要求メッセージは、初めにノードＮｂ、Ｎｅへ到達する。このパス接続要求メッセージには累積利用率Ｓ（初期値は「０」）が登録されている。累積利用率Ｓは、パスを構成する各ノードの利用率Ｌｉの積算値であり、複数のノードＮ１、Ｎ２…Ｎｎを経由して各ノードに到達した時点でのパス接続要求メッセージに登録された累積利用率Ｓｎは、次式（２）で表される。
2004048478.tif 000003
【００１５】
ノードＮｂ、Ｎｅが受信した各パス接続要求メッセージに登録されている累積利用率Ｓ１、Ｓ２は、当該時点では「０」であり、ノードＮｂは累積利用率Ｓ１に自身のパス利用率Ｌｂ（＝１）を加算して当該累積利用率Ｓ１を「１」に更新する。ノードＮｅも累積利用率Ｓ２に自身のパス利用率Ｌｂ（＝０）を加算するが、当該累積利用率Ｓ２は「０」のままである。ノードＮｃは、ノードＮｂから受信したパス接続要求メッセージに登録されている累積利用率Ｓ１（＝１）に自ノードのパス利用率Ｌｃ（＝１）を加算して「２」に更新し、これを宛先ノードＮｄへ送信する。したがって、宛先ノードＮｄがノードＮｂ、Ｎｃ経由で受信したパス接続要求メッセージに登録された累積利用率Ｓ１は「２」となる。
【００１６】
同様に、ノードＮｆは、ノードＮｅから受信したパス接続要求メッセージＭ２に登録されている累積利用率Ｓ２（＝０）に自ノードのパス利用率Ｌｆ（＝０）を加算して「０」に更新し、これをノードＮｇへ送信する。ノードＮｇは、ノードＮｆから受信したパス接続要求メッセージに登録されている累積利用率Ｓ２（＝０）に自ノードのパス利用率Ｌｇ（＝０）を加算して「０」とし、これをノードＮｃへ送信する。ノードＮｃは、ノードＮｇから受信したパス接続要求メッセージに登録されている累積利用率Ｓ２（＝０）に自ノードのパス利用率Ｌｃ（＝１）を加算して「１」に更新し、これを宛先ノードＮｄへ送信する。したがって、宛先ノードＮｄがノードＮｅ、Ｎｆ、Ｎｇ、Ｎｃ経由で受信したパス接続要求メッセージに登録された累積利用率Ｓ２は「１」となる。
【００１７】
宛先ノードＮｄは各パスの累積利用率Ｓ１、Ｓ２を比較し、その値の小さいパスを選択してパス接続応答メッセージをユニキャストする。送信元ノードＮａがパス接続応答メッセージを受信すると、送信元ノードＮａと宛先ノードＮｄとの間にパスが確立される。
【００１８】
このように、本発明では宛先ノードが受信する各パス接続要求メッセージにパスの累積利用率Ｓが登録されており、宛先ノードは累積利用率Ｓの小さい経路を選択してパスを確立できるので、最適なパスを簡単に選択することができる。また、ネットワーク全体として見れば、複数のパスが確立される状況下でも、トラヒックが分散されて一部のノードへのパスの集中が防止されるので、ネットワークの利用効率が向上する。
【００１９】
次いで、図２，３，４のフローチャートを参照して、本実施形態における送信元ノード、中継ノードおよび宛先ノードの動作を詳細に説明する。なお、本実施形態でもノードＮａが送信元、ノードＮｄが宛先であるものとする。
【００２０】
図２は、送信ノードＮａの動作を示したフローチャートである。ステップＳ１０１において、上位層であるアプリケーション層からパケット送信要求を受信したノードＮａは送信元ノードとして振る舞い、ステップＳ１０２において、指定された宛先ノードＮｄまでのパスが既に確立されているか否かを判定する。パスが確立されていなければステップＳ１０３へ進み、試行回数Ｋに初期値として「１」がセットされる。ステップＳ１０４では、ノードＮｄを宛先とするパス接続要求メッセージがブロードキャストされる。
【００２１】
次いで、図３のフローチャートを参照して、前記パス接続要求メッセージを受信した各中継ノードおよび宛先ノードの動作を説明する。
【００２２】
ステップＳ２０１において、前記パス接続要求メッセージを受信したノードは、ステップＳ２０２において、その宛先が自ノードであるか否かを判定する。宛先が自ノード以外であれば中継ノードとして振る舞い、ステップＳ２０３において、指定された宛先までのパスが既に確立されているか否かを判定する。宛先までのパスが未だ確立されていなければ、ステップＳ２０４において、前記受信したパス接続要求メッセージが新規であるか否かが判定される。本実施形態では、パス接続要求メッセージに登録されている送信元ノードおよび宛先ノードの少なくとも一方が、これより先に受信したパス接続要求メッセージの送信元ノードおよび宛先ノードと異なっていれば、これを新規のメッセージと判断してステップＳ２０５へ進む。
【００２３】
ステップＳ２０５では、図５に示したように、当該メッセージを中継して自ノードへ転送してきた隣接ノードを、送信元へデータを送信する際の次ホップとして経路表へ登録する。すなわち、送信元ノードＮａがブロードキャストしたパス接続要求メッセージをノードＮｂから受信したノードＮｃは、ノードＮａを宛先とするパケットの次ポップとしてノードＮｂを登録する。ステップＳ２０６では、受信したパス接続要求メッセージに登録されている累積利用率Ｓを読み取る。ステップＳ２０７では、この累積利用率Ｓに自ノードのパス利用率Ｌを加算して更新する。ステップＳ２０８では、前記更新後の累積利用率Ｓが登録されたパス接続要求メッセージを再ブロードキャストする。
【００２４】
一方、前記ステップＳ２０２において、受信したパス接続要求メッセージの宛先が自ノードであれば宛先ノードとして振る舞い、ステップＳ２０９において、当該パス接続要求メッセージに登録されている累積利用率Ｓを記憶する。ステップＳ２１０では、他のパスを経由して到着する同一メッセージの受信に備えて所定時間だけ待機する。その間、他のパスを経由して同一メッセージが受信されるごとに、その累積利用率ＳがステップＳ２０９において全て記憶される。
【００２５】
所定の待機時間が経過するとステップＳ２１１へ進み、前記複数のパスの中から、前記累積利用率Ｓが最低のパスが最適パスとして選択される。ステップＳ２１２では、前記累積利用率Ｓが最低であったパス接続要求メッセージに対するパス接続応答メッセージがユニキャストされる。なお、このパス接続応答メッセージには、前記最低であった累積利用率Ｓが登録されている。
【００２６】
なお、図７に示したように、ノードＮｂ、Ｎｄ間に既にパスが確立されているときのノードＮｂがノードＮｄを宛先とするパス接続要求メッセージを受信すれば、前記ステップＳ２０３において、宛先までのパスが既に確立されていると判断してステップＳ２１２へ進む。前記ノードＮｂには当該パスの累積利用率Ｓが登録されており、ステップＳ２１２において、当該パスの累積利用率Ｓが登録されたパス接続応答メッセージを送信元ノードＮａへユニキャストする。
【００２７】
図４は、前記パス接続応答メッセージを受信した各中継ノードの動作を示したフローチャートである。
【００２８】
ステップＳ３０１においてパス接続応答メッセージを受信すると、ステップＳ３０２では、自ノードから送信元ノードＮａまでのパスが既に確立されているか否かが判定される。確立されてなければステップＳ３０５へ進む。これに対して、図８に示したように、ノードＮａ、Ｎｃ間に既にパスが確立されているときのノードＮｃが前記パス接続応答メッセージを受信すれば、ステップＳ３０３へ進む。
【００２９】
ステップＳ３０３では、当該パス接続応答メッセージに登録されている累積利用率Ｓ（ｎｅｗ）が読み取られ、ステップＳ３０４において、前記既に確立されているパスの累積利用率Ｓ（ｐｒｅ）と比較される。今回の累積利用率Ｓ（ｎｅｗ）が前記既に確立されているパスの累積利用率Ｓ（ｐｒｅ）よりも低ければ、ステップＳ３０５において、図６に示したように、当該パス接続応答メッセージを中継した隣接ノードを、宛先へパケットを送信する際の次ホップとして経路表に登録する。すなわち、宛先ノードＮｄからユニキャストされたパス接続応答メッセージをノードＮｃから受信したノードＮｂは、ノードＮｄを宛先とするパケットの次ポップとしてノードＮｃを登録する。なお、選択されなかったパスが経由する各ノードの経路表は一定時間後に削除される。
【００３０】
ステップＳ３０６では、受信したパス接続応答メッセージに登録されている累積利用率Ｓが読み取られて保持される。この累積利用率Ｓは、次のステップＳ３０４において前記「現在のパスの累積利用率Ｓ（ｐｒｅ）」として利用される。ステップＳ３０７では、前記パス接続応答メッセージが前記経路表に基づいて次ホップへ送信される。
【００３１】
次いで、前記図２のフローチャートへ戻り、前記パス接続応答メッセージを受信した送信元ノードＮａの動作を説明する。
【００３２】
送信元ノードは、ステップＳ１０５において、前記パス接続要求に応答して宛先ノードＮｄから自ノード宛にユニキャストされるパス接続応答メッセージの受信の有無を判定し、パス接続応答メッセージが受信されるまではステップＳ１０６へ進む。ステップＳ１０６では、前記パス接続要求メッセージを送出してからの経過時間が所定の再試行待ち時間を経過したか否かが判定され、経過するまではステップＳ１０５へ戻る。
【００３３】
その後、再試行待ち時間が経過し、これがステップＳ１０６で検知されると、ステップＳ１０７では、前記試行回数Ｋが再試行上限値Ｋｍａｘを超えたか否かが判定され、最初は超えていないと判定されるので、ステップＳ１０８において前記試行回数Ｋがカウントアップされ、その後、ステップＳ１０４へ戻って前記パス接続要求メッセージが改めてブロードキャストされる。
【００３４】
その後も、前記ステップＳ１０５においてパス接続応答メッセージの受信が検知されるまでは、再試行待ち時間が経過するごとにパス接続要求メッセージが再ブロードキャストされる。前記ステップＳ１０７において、試行回数Ｋが再試行上限値Ｋｍａｘに達したと判定されると、ステップＳ１０９においてパケットが破棄される。ステップＳ１１０では、パケットを破棄した旨のメッセージが上位層へ通知される。
【００３５】
一方、前記試行回数Ｋが再試行上限値Ｋｍａｘを超えるよりも前に前記パス接続応答メッセージが受信され、これがステップＳ１０５で検知されるとステップＳ１１１へ進む。ステップＳ１１１では、受信したパス接続応答メッセージに登録されているパスと同一のパスが既に確立されているか否かが判定される。確立済みであればステップＳ１１２へ進み、当該パス接続応答メッセージに登録されている累積利用率Ｓ（ｎｅｗ）が読み取られ、ステップＳ１１３において、前記既に確立されているパスの累積利用率Ｓ（ｐｒｅ）と比較される。
【００３６】
前記累積利用率Ｓ（ｐｒｅ）が累積利用率Ｓ（ｎｅｗ）よりも低ければステップＳ１１６へ進み、前記送信要求のあったパケットが前記確立済みのパスを利用して宛先へ送信される。また、累積利用率Ｓ（ｎｅｗ）が累積利用率Ｓ（ｐｒｅ）よりも低い場合や、前記ステップＳ１１１においてパスが未だ確立されていないと判定されるとステップＳ１１４へ進む。
【００３７】
ステップＳ１１４では、当該パス接続応答メッセージに登録されている経路情報を自ノードの経路表に書き込む。これにより、ノードＮａ、Ｎｄ間にパスが確立される。ステップＳ１１５では、同じく当該パス接続応答メッセージに登録されている累積利用率Ｓを保存する。この累積利用率Ｓは、自ノードが今後、前記ノードＮｄを宛先とする他のパス接続要求メッセージの中継ノードとして振る舞う際に、前記図４のステップＳ３０４で「現在のパスの累積利用率Ｓ（ｐｒｅ）」として利用される。ステップＳ１１６では、送信要求のあったパケットが前記確立されたパスを利用して宛先へ送信される。
【００３８】
【発明の効果】
本発明によれば、以下のような効果が達成される。
（１）送信元および宛先が同一であって経路の異なる複数のパス接続要求メッセージを受信した宛先ノードは、各パス接続要求メッセージに登録されている通信能力情報に基づいて各パスを評価できるので、最適なパスを簡単に選択することができる。
（２）複数のパスが確立される状況下でも、トラヒックが分散されて一部のノードへのパスの集中が防止されるので、ネットワークの利用効率が向上する。
【図面の簡単な説明】
【図１】本発明を適用したパス選択方法の基本動作を説明するための図である。
【図２】送信ノードがパス接続要求メッセージをブロードキャストする手順を示したフローチャートである。
【図３】パス接続要求メッセージを受信した中継ノードおよび宛先ノードの動作を示したフローチャートである。
【図４】パス接続応答メッセージを受信した各中継ノードの動作を示したフローチャートである。
【図５】パス接続要求メッセージに基づいて中継ノードが登録する経路情報の一例を示した図である。
【図６】パス接続応答メッセージに基づいて中継ノードが登録する経路情報の一例を示した図である。
【図７】パス接続要求メッセージで要求されたパスが既に確立されている状態を模式的に示した図である。
【図８】パス接続応答メッセージで要求されたパスが既に確立されている状態を模式的に示した図である。
【図９】アドホック網の構成を示した図である。
【図１０】従来のアドホック網におけるルーティング手順（その１）を示した図である。
【図１１】従来のアドホック網におけるルーティング手順（その２）を示した図である。
【符号の説明】
Ｎａ、Ｎｂ、Ｎｃ、Ｎｄ、Ｎｅ、Ｎｆ、Ｎｇ…無線ノード
【図１】
2004048478.tif 000004
【図２】
2004048478.tif 000005
【図３】
2004048478.tif 000006
【図４】
2004048478.tif 000007
【図５】
2004048478.tif 000008
【図６】
2004048478.tif 000009
【図７】
2004048478.tif 000010
【図８】
2004048478.tif 000011
【図９】
2004048478.tif 000012
【図１０】
2004048478.tif 000013
【図１１】
2004048478.tif 000014