JP2004048478A

JP2004048478A - Ad hoc network routing method

Info

Publication number: JP2004048478A
Application number: JP2002204494A
Authority: JP
Inventors: Hidetoshi Yokota; 横田　英俊; Shingo Watanabe; 渡辺　伸吾; Toru Hasegawa; 長谷川　亨
Original assignee: KDDI Corp
Current assignee: KDDI Corp
Priority date: 2002-07-12
Filing date: 2002-07-12
Publication date: 2004-02-12
Anticipated expiration: 2022-07-12
Also published as: JP3888536B2

Abstract

【課題】アドホック網において、送信元ノードと宛先ノードとの間に最適パスを確立する。
【解決手段】複数の無線ノードが自立分散的に無線ネットワークを構築するアドホック網において、送信元ノードからブロードキャストされたパス接続要求メッセージに、当該パス接続要求メッセージが辿ったパスの通信能力に関する情報を登録する手順と、経路の異なる複数のパス接続要求メッセージを受信した宛先ノードが、各パス接続要求メッセージに登録された通信能力情報に基づいて一のパスを選択する手順と、宛先ノードが、前記選択した一のパスに対してパス接続応答メッセージをユニキャストする手順とを含む。
【選択図】　　　　図１An optimal path is established between a source node and a destination node in an ad hoc network.
In an ad hoc network in which a plurality of wireless nodes construct a wireless network autonomously and decentralized, information relating to the communication capability of a path followed by the path connection request message is included in a path connection request message broadcast from a source node. A step of registering, a step in which a destination node receiving a plurality of path connection request messages having different paths selects one path based on communication capability information registered in each path connection request message, and Unicasting a path connection response message for the selected one path.
[Selection diagram] Fig. 1

Description

【０００１】
【発明の属する技術分野】
本発明は、アドホック網のルーティング方法に係り、特に、送信元ノードと宛先ノードとの間に最適パスを確立するためのルーティング方法に関する。
【０００２】
【従来の技術】
無線通信技術を採用した移動ノードにおいて、既存のインターネットなどのインフラ網に接続することなく、ノード間で自立的にネットワークを構成して通信を行う形態のネットワーク、すなわちアドホック網が提案されている。
【０００３】
図９は、アドホック網の構成を示した図であり、丸印は移動ノードＮａ、Ｎｂ…Ｎｇを示し、その外周に記載した同心円は各移動ノードの無線カバレッジを示している。各移動ノードはルーティング機能を備え、宛先ノードまでの経路を作成してデータを配信する。
【０００４】
このような構成のアドホック網において、いずれかのノードでデータ送信要求が発生した時点で宛先までの経路を確立するルーティング方式（オンデマンド型のルーティング方式）では、宛先ノードまでの経路（パス）を確立するための制御メッセージを全てのノードがブロードキャスト（広報）することにより、このメッセージが宛先ノードまで伝搬される。
【０００５】
【発明が解決しようとする課題】
図１０において、ノードＮａからＮｄ宛にデータの送信要求が発生した場合、送信元ノードＮａから宛先ノードＮｄ宛にパス接続要求メッセージがブロードキャストされる。このメッセージは、例えばノードＮｂ、Ｎｃを中継してノードＮｄに至る第１パスと、ノードＮｅ、Ｎｆ、Ｎｇ、Ｎｃを中継して宛先ノードＮｄに至る第２パスとで伝達される。
【０００６】
このように複数のパスを経由してメッセージが宛先ノードＮｄへ届いた場合、宛先ノードでは、先に届いたメッセージのパスを選択してパス接続応答メッセージを送信元ノードに向けてユニキャスト（単一ノード宛）で転送する。これにより、送信ノードＮａと宛先ノードＮｄとの間にパスが確立されるので、これ以後は、当該パスを経由してデータ交換が行われる。しかしながら、到着順序の早いパス接続要求メッセージの辿ったパスが最適であるとは限らないため、上記した従来技術では、必ずしも最適パスが選択されるとは限らなかった。
【０００７】
さらに、図１１に示したように、送信元ノードＮａと宛先ノードＮｃとの間に既にパスが確立している状態で、ノードＮａがさらにノードＮｄに対してパス接続要求メッセージをブロードキャストしたような場合でも、宛先ノードＮｄでは最初に到着したパス接続要求メッセージに対して応答する可能性が高い。そして、図１１の例では、経由するノード数の少ないノードＮａ→Ｎｂ→Ｎｃ→Ｎｄ経由のメッセージが先に到着し、このパスが選択されるので、二つのパスが同一ノードＮｂ、Ｎｃを経由することになる。このため、複数のパスが同一ノードを経由することによるノードの過負荷や、トラヒックの集中によるデータスループットの劣化等が発生しやすいという技術課題があった。
【０００８】
本発明の目的は、上記した従来技術の課題を解決し、送信元ノードと宛先ノードとの間に常に最適パスを確立できるアドホック網のルーティング方法を提供することにある。
【０００９】
【課題を解決するための手段】
上記した目的を達成するために、本発明は、複数の無線ノードが自立分散的に無線ネットワークを構築するアドホック網において、送信元ノードが宛先ノードを指定してブロードキャストしたパス接続要求メッセージを他の無線ノードが連携して宛先ノードまで中継する手順と、各パス接続要求メッセージに、当該パス接続要求メッセージが辿ったパスの通信能力に関する情報を登録する手順と、経路の異なる複数のパス接続要求メッセージを受信した宛先ノードが、各パス接続要求メッセージに登録された前記通信能力情報に基づいて一のパスを選択する手順と、宛先ノードが、前記選択した一のパスに対してパス接続応答メッセージをユニキャストする手順とを含むことを特徴とする。
【００１０】
上記した特徴によれば、送信元および宛先が同一であって経路の異なる複数のパス接続要求メッセージを受信した宛先ノードは、各パス接続要求メッセージに登録されている通信能力情報に基づいて各パスを評価できるので、最適なパスを簡単に選択することができる。また、ネットワーク全体として見れば、複数のパスが確立される状況下でも、トラヒックが分散されて一部のノードへのパスの集中が防止されるので、ネットワークの利用効率が向上する。
【００１１】
【発明の実施の形態】
以下、図面を参照して本発明の好ましい実施の形態について詳細に説明する。図１は、本発明のルーティング方法の基本動作を説明するための図であり、無線移動ノードＮａ、Ｎｂ、Ｎｃ、Ｎｄ、Ｎｅ、Ｎｆ、Ｎｇがアドホック網を構成している。ここでは、ノードＮａが送信元ノード、ノードＮｄが宛先ノード、他のノードが中継ノードとして機能する場合を例にして説明する。
【００１２】
各ノードＮｉは自ノードのパス利用率Ｌｉを管理している。パス利用率Ｌｉは、各ノードＮｉにおいて利用可能なパスの本数Ｒｉと確立済みパスの本数ｒｉとの比であり、次式（１）で表される
Ｌｉ＝ｒｉ／Ｒｉ　…（１）
【００１３】
ここでは、ノードＮｂ、Ｎｃのパス利用率Ｌｂ、Ｌｃがいずれも「１」であり、他のノードＮｅ、Ｎｆ、Ｎｇのパス利用率Ｌｅ、Ｌｆ、Ｌｇがいずれも「０」であるものとして説明する。
【００１４】
送信元ノードＮａがノードＮｄを宛先としてブロードキャストしたパス接続要求メッセージは、初めにノードＮｂ、Ｎｅへ到達する。このパス接続要求メッセージには累積利用率Ｓ（初期値は「０」）が登録されている。累積利用率Ｓは、パスを構成する各ノードの利用率Ｌｉの積算値であり、複数のノードＮ１、Ｎ２…Ｎｎを経由して各ノードに到達した時点でのパス接続要求メッセージに登録された累積利用率Ｓｎは、次式（２）で表される。

【００１５】
ノードＮｂ、Ｎｅが受信した各パス接続要求メッセージに登録されている累積利用率Ｓ１、Ｓ２は、当該時点では「０」であり、ノードＮｂは累積利用率Ｓ１に自身のパス利用率Ｌｂ（＝１）を加算して当該累積利用率Ｓ１を「１」に更新する。ノードＮｅも累積利用率Ｓ２に自身のパス利用率Ｌｂ（＝０）を加算するが、当該累積利用率Ｓ２は「０」のままである。ノードＮｃは、ノードＮｂから受信したパス接続要求メッセージに登録されている累積利用率Ｓ１（＝１）に自ノードのパス利用率Ｌｃ（＝１）を加算して「２」に更新し、これを宛先ノードＮｄへ送信する。したがって、宛先ノードＮｄがノードＮｂ、Ｎｃ経由で受信したパス接続要求メッセージに登録された累積利用率Ｓ１は「２」となる。
【００１６】
同様に、ノードＮｆは、ノードＮｅから受信したパス接続要求メッセージＭ２に登録されている累積利用率Ｓ２（＝０）に自ノードのパス利用率Ｌｆ（＝０）を加算して「０」に更新し、これをノードＮｇへ送信する。ノードＮｇは、ノードＮｆから受信したパス接続要求メッセージに登録されている累積利用率Ｓ２（＝０）に自ノードのパス利用率Ｌｇ（＝０）を加算して「０」とし、これをノードＮｃへ送信する。ノードＮｃは、ノードＮｇから受信したパス接続要求メッセージに登録されている累積利用率Ｓ２（＝０）に自ノードのパス利用率Ｌｃ（＝１）を加算して「１」に更新し、これを宛先ノードＮｄへ送信する。したがって、宛先ノードＮｄがノードＮｅ、Ｎｆ、Ｎｇ、Ｎｃ経由で受信したパス接続要求メッセージに登録された累積利用率Ｓ２は「１」となる。
【００１７】
宛先ノードＮｄは各パスの累積利用率Ｓ１、Ｓ２を比較し、その値の小さいパスを選択してパス接続応答メッセージをユニキャストする。送信元ノードＮａがパス接続応答メッセージを受信すると、送信元ノードＮａと宛先ノードＮｄとの間にパスが確立される。
【００１８】
このように、本発明では宛先ノードが受信する各パス接続要求メッセージにパスの累積利用率Ｓが登録されており、宛先ノードは累積利用率Ｓの小さい経路を選択してパスを確立できるので、最適なパスを簡単に選択することができる。また、ネットワーク全体として見れば、複数のパスが確立される状況下でも、トラヒックが分散されて一部のノードへのパスの集中が防止されるので、ネットワークの利用効率が向上する。
【００１９】
次いで、図２，３，４のフローチャートを参照して、本実施形態における送信元ノード、中継ノードおよび宛先ノードの動作を詳細に説明する。なお、本実施形態でもノードＮａが送信元、ノードＮｄが宛先であるものとする。
【００２０】
図２は、送信ノードＮａの動作を示したフローチャートである。ステップＳ１０１において、上位層であるアプリケーション層からパケット送信要求を受信したノードＮａは送信元ノードとして振る舞い、ステップＳ１０２において、指定された宛先ノードＮｄまでのパスが既に確立されているか否かを判定する。パスが確立されていなければステップＳ１０３へ進み、試行回数Ｋに初期値として「１」がセットされる。ステップＳ１０４では、ノードＮｄを宛先とするパス接続要求メッセージがブロードキャストされる。
【００２１】
次いで、図３のフローチャートを参照して、前記パス接続要求メッセージを受信した各中継ノードおよび宛先ノードの動作を説明する。
【００２２】
ステップＳ２０１において、前記パス接続要求メッセージを受信したノードは、ステップＳ２０２において、その宛先が自ノードであるか否かを判定する。宛先が自ノード以外であれば中継ノードとして振る舞い、ステップＳ２０３において、指定された宛先までのパスが既に確立されているか否かを判定する。宛先までのパスが未だ確立されていなければ、ステップＳ２０４において、前記受信したパス接続要求メッセージが新規であるか否かが判定される。本実施形態では、パス接続要求メッセージに登録されている送信元ノードおよび宛先ノードの少なくとも一方が、これより先に受信したパス接続要求メッセージの送信元ノードおよび宛先ノードと異なっていれば、これを新規のメッセージと判断してステップＳ２０５へ進む。
【００２３】
ステップＳ２０５では、図５に示したように、当該メッセージを中継して自ノードへ転送してきた隣接ノードを、送信元へデータを送信する際の次ホップとして経路表へ登録する。すなわち、送信元ノードＮａがブロードキャストしたパス接続要求メッセージをノードＮｂから受信したノードＮｃは、ノードＮａを宛先とするパケットの次ポップとしてノードＮｂを登録する。ステップＳ２０６では、受信したパス接続要求メッセージに登録されている累積利用率Ｓを読み取る。ステップＳ２０７では、この累積利用率Ｓに自ノードのパス利用率Ｌを加算して更新する。ステップＳ２０８では、前記更新後の累積利用率Ｓが登録されたパス接続要求メッセージを再ブロードキャストする。
【００２４】
一方、前記ステップＳ２０２において、受信したパス接続要求メッセージの宛先が自ノードであれば宛先ノードとして振る舞い、ステップＳ２０９において、当該パス接続要求メッセージに登録されている累積利用率Ｓを記憶する。ステップＳ２１０では、他のパスを経由して到着する同一メッセージの受信に備えて所定時間だけ待機する。その間、他のパスを経由して同一メッセージが受信されるごとに、その累積利用率ＳがステップＳ２０９において全て記憶される。
【００２５】
所定の待機時間が経過するとステップＳ２１１へ進み、前記複数のパスの中から、前記累積利用率Ｓが最低のパスが最適パスとして選択される。ステップＳ２１２では、前記累積利用率Ｓが最低であったパス接続要求メッセージに対するパス接続応答メッセージがユニキャストされる。なお、このパス接続応答メッセージには、前記最低であった累積利用率Ｓが登録されている。
【００２６】
なお、図７に示したように、ノードＮｂ、Ｎｄ間に既にパスが確立されているときのノードＮｂがノードＮｄを宛先とするパス接続要求メッセージを受信すれば、前記ステップＳ２０３において、宛先までのパスが既に確立されていると判断してステップＳ２１２へ進む。前記ノードＮｂには当該パスの累積利用率Ｓが登録されており、ステップＳ２１２において、当該パスの累積利用率Ｓが登録されたパス接続応答メッセージを送信元ノードＮａへユニキャストする。
【００２７】
図４は、前記パス接続応答メッセージを受信した各中継ノードの動作を示したフローチャートである。
【００２８】
ステップＳ３０１においてパス接続応答メッセージを受信すると、ステップＳ３０２では、自ノードから送信元ノードＮａまでのパスが既に確立されているか否かが判定される。確立されてなければステップＳ３０５へ進む。これに対して、図８に示したように、ノードＮａ、Ｎｃ間に既にパスが確立されているときのノードＮｃが前記パス接続応答メッセージを受信すれば、ステップＳ３０３へ進む。
【００２９】
ステップＳ３０３では、当該パス接続応答メッセージに登録されている累積利用率Ｓ（ｎｅｗ）が読み取られ、ステップＳ３０４において、前記既に確立されているパスの累積利用率Ｓ（ｐｒｅ）と比較される。今回の累積利用率Ｓ（ｎｅｗ）が前記既に確立されているパスの累積利用率Ｓ（ｐｒｅ）よりも低ければ、ステップＳ３０５において、図６に示したように、当該パス接続応答メッセージを中継した隣接ノードを、宛先へパケットを送信する際の次ホップとして経路表に登録する。すなわち、宛先ノードＮｄからユニキャストされたパス接続応答メッセージをノードＮｃから受信したノードＮｂは、ノードＮｄを宛先とするパケットの次ポップとしてノードＮｃを登録する。なお、選択されなかったパスが経由する各ノードの経路表は一定時間後に削除される。
【００３０】
ステップＳ３０６では、受信したパス接続応答メッセージに登録されている累積利用率Ｓが読み取られて保持される。この累積利用率Ｓは、次のステップＳ３０４において前記「現在のパスの累積利用率Ｓ（ｐｒｅ）」として利用される。ステップＳ３０７では、前記パス接続応答メッセージが前記経路表に基づいて次ホップへ送信される。
【００３１】
次いで、前記図２のフローチャートへ戻り、前記パス接続応答メッセージを受信した送信元ノードＮａの動作を説明する。
【００３２】
送信元ノードは、ステップＳ１０５において、前記パス接続要求に応答して宛先ノードＮｄから自ノード宛にユニキャストされるパス接続応答メッセージの受信の有無を判定し、パス接続応答メッセージが受信されるまではステップＳ１０６へ進む。ステップＳ１０６では、前記パス接続要求メッセージを送出してからの経過時間が所定の再試行待ち時間を経過したか否かが判定され、経過するまではステップＳ１０５へ戻る。
【００３３】
その後、再試行待ち時間が経過し、これがステップＳ１０６で検知されると、ステップＳ１０７では、前記試行回数Ｋが再試行上限値Ｋｍａｘを超えたか否かが判定され、最初は超えていないと判定されるので、ステップＳ１０８において前記試行回数Ｋがカウントアップされ、その後、ステップＳ１０４へ戻って前記パス接続要求メッセージが改めてブロードキャストされる。
【００３４】
その後も、前記ステップＳ１０５においてパス接続応答メッセージの受信が検知されるまでは、再試行待ち時間が経過するごとにパス接続要求メッセージが再ブロードキャストされる。前記ステップＳ１０７において、試行回数Ｋが再試行上限値Ｋｍａｘに達したと判定されると、ステップＳ１０９においてパケットが破棄される。ステップＳ１１０では、パケットを破棄した旨のメッセージが上位層へ通知される。
【００３５】
一方、前記試行回数Ｋが再試行上限値Ｋｍａｘを超えるよりも前に前記パス接続応答メッセージが受信され、これがステップＳ１０５で検知されるとステップＳ１１１へ進む。ステップＳ１１１では、受信したパス接続応答メッセージに登録されているパスと同一のパスが既に確立されているか否かが判定される。確立済みであればステップＳ１１２へ進み、当該パス接続応答メッセージに登録されている累積利用率Ｓ（ｎｅｗ）が読み取られ、ステップＳ１１３において、前記既に確立されているパスの累積利用率Ｓ（ｐｒｅ）と比較される。
【００３６】
前記累積利用率Ｓ（ｐｒｅ）が累積利用率Ｓ（ｎｅｗ）よりも低ければステップＳ１１６へ進み、前記送信要求のあったパケットが前記確立済みのパスを利用して宛先へ送信される。また、累積利用率Ｓ（ｎｅｗ）が累積利用率Ｓ（ｐｒｅ）よりも低い場合や、前記ステップＳ１１１においてパスが未だ確立されていないと判定されるとステップＳ１１４へ進む。
【００３７】
ステップＳ１１４では、当該パス接続応答メッセージに登録されている経路情報を自ノードの経路表に書き込む。これにより、ノードＮａ、Ｎｄ間にパスが確立される。ステップＳ１１５では、同じく当該パス接続応答メッセージに登録されている累積利用率Ｓを保存する。この累積利用率Ｓは、自ノードが今後、前記ノードＮｄを宛先とする他のパス接続要求メッセージの中継ノードとして振る舞う際に、前記図４のステップＳ３０４で「現在のパスの累積利用率Ｓ（ｐｒｅ）」として利用される。ステップＳ１１６では、送信要求のあったパケットが前記確立されたパスを利用して宛先へ送信される。
【００３８】
【発明の効果】
本発明によれば、以下のような効果が達成される。
（１）送信元および宛先が同一であって経路の異なる複数のパス接続要求メッセージを受信した宛先ノードは、各パス接続要求メッセージに登録されている通信能力情報に基づいて各パスを評価できるので、最適なパスを簡単に選択することができる。
（２）複数のパスが確立される状況下でも、トラヒックが分散されて一部のノードへのパスの集中が防止されるので、ネットワークの利用効率が向上する。
【図面の簡単な説明】
【図１】本発明を適用したパス選択方法の基本動作を説明するための図である。
【図２】送信ノードがパス接続要求メッセージをブロードキャストする手順を示したフローチャートである。
【図３】パス接続要求メッセージを受信した中継ノードおよび宛先ノードの動作を示したフローチャートである。
【図４】パス接続応答メッセージを受信した各中継ノードの動作を示したフローチャートである。
【図５】パス接続要求メッセージに基づいて中継ノードが登録する経路情報の一例を示した図である。
【図６】パス接続応答メッセージに基づいて中継ノードが登録する経路情報の一例を示した図である。
【図７】パス接続要求メッセージで要求されたパスが既に確立されている状態を模式的に示した図である。
【図８】パス接続応答メッセージで要求されたパスが既に確立されている状態を模式的に示した図である。
【図９】アドホック網の構成を示した図である。
【図１０】従来のアドホック網におけるルーティング手順（その１）を示した図である。
【図１１】従来のアドホック網におけるルーティング手順（その２）を示した図である。
【符号の説明】
Ｎａ、Ｎｂ、Ｎｃ、Ｎｄ、Ｎｅ、Ｎｆ、Ｎｇ…無線ノード[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a routing method for an ad hoc network, and more particularly, to a routing method for establishing an optimal path between a source node and a destination node.
[0002]
[Prior art]
2. Description of the Related Art In a mobile node adopting a wireless communication technology, a network in which a node autonomously forms a network and communicates without connecting to an existing infrastructure network such as the Internet, that is, an ad hoc network has been proposed.
[0003]
FIG. 9 is a diagram showing a configuration of an ad hoc network, in which circles indicate mobile nodes Na, Nb,... Ng, and concentric circles described on the outer periphery indicate wireless coverage of each mobile node. Each mobile node has a routing function, creates a route to a destination node, and distributes data.
[0004]
In an ad hoc network having such a configuration, in a routing method (on-demand type routing method) that establishes a route to a destination when a data transmission request occurs at any node, a route (path) to the destination node is set. This message is propagated to the destination node by broadcasting a control message for establishment by all nodes.
[0005]
[Problems to be solved by the invention]
In FIG. 10, when a request to transmit data is issued from node Na to Nd, a path connection request message is broadcast from source node Na to destination node Nd. This message is transmitted, for example, via a first path that relays the nodes Nb and Nc to the node Nd and a second path that relays the nodes Ne, Nf, Ng, and Nc to the destination node Nd.
[0006]
When the message arrives at the destination node Nd via a plurality of paths as described above, the destination node selects the path of the message which has arrived earlier, and sends a path connection response message to the source node by unicast (single-cast). Transfer to one node). As a result, a path is established between the transmission node Na and the destination node Nd, and thereafter, data exchange is performed via the path. However, since the path followed by the path connection request message having the earliest arrival order is not always optimal, the conventional technique described above does not always select the optimal path.
[0007]
Further, as shown in FIG. 11, in a state where a path has already been established between the transmission source node Na and the destination node Nc, the node Na further broadcasts a path connection request message to the node Nd. Even in this case, there is a high possibility that the destination node Nd responds to the path connection request message that arrives first. Then, in the example of FIG. 11, a message via the nodes Na → Nb → Nc → Nd with a small number of passing nodes arrives first and this path is selected, so that two paths pass through the same nodes Nb and Nc. Will do. For this reason, there has been a technical problem that nodes are easily overloaded due to a plurality of paths passing through the same node, and data throughput is likely to be deteriorated due to traffic concentration.
[0008]
An object of the present invention is to solve the above-mentioned problems of the related art and to provide an ad hoc network routing method capable of always establishing an optimal path between a source node and a destination node.
[0009]
[Means for Solving the Problems]
In order to achieve the above object, the present invention provides an ad-hoc network in which a plurality of wireless nodes constructs a wireless network autonomously in a distributed manner, in which a source node specifies a destination node and broadcasts a path connection request message to another node. A procedure in which the wireless node cooperates to relay to the destination node, a procedure for registering, in each path connection request message, information on the communication capability of the path followed by the path connection request message, a plurality of path connection request messages having different routes The destination node having received the path connection request message, and selecting a path based on the communication capability information registered in each path connection request message, and the destination node transmits a path connection response message to the selected one path. And performing a unicast procedure.
[0010]
According to the above-described feature, the destination node that has received the plurality of path connection request messages having the same transmission source and destination and different paths, determines each path connection based on the communication capability information registered in each path connection request message. Can be evaluated, so that an optimal path can be easily selected. In addition, when viewed as a whole network, even under a situation where a plurality of paths are established, traffic is distributed and concentration of paths to some nodes is prevented, so that network use efficiency is improved.
[0011]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the drawings. FIG. 1 is a diagram for explaining a basic operation of the routing method according to the present invention, and wireless mobile nodes Na, Nb, Nc, Nd, Ne, Nf, and Ng constitute an ad hoc network. Here, a case will be described as an example where the node Na functions as a source node, the node Nd functions as a destination node, and another node functions as a relay node.
[0012]
Each node Ni manages its own path utilization rate Li. The path utilization ratio Li is a ratio between the number Ri of paths available at each node Ni and the number ri of established paths, and is represented by the following equation (1): Li = ri / Ri (1)
[0013]
Here, it is assumed that the path utilization rates Lb, Lc of the nodes Nb, Nc are all “1”, and the path utilization rates Le, Lf, Lg of the other nodes Ne, Nf, Ng are all “0”. explain.
[0014]
The path connection request message broadcasted by the transmission source node Na to the node Nd reaches the nodes Nb and Ne first. The cumulative utilization rate S (initial value is “0”) is registered in this path connection request message. The cumulative utilization ratio S is an integrated value of the utilization ratio Li of each node constituting the path, and is registered in the path connection request message at the time when each node reaches the node via a plurality of nodes N1, N2,. The cumulative utilization rate Sn is represented by the following equation (2).

[0015]
The cumulative utilization rates S1 and S2 registered in the respective path connection request messages received by the nodes Nb and Ne are “0” at this time, and the node Nb adds its own path utilization rate Lb (= 1) is added to update the cumulative utilization rate S1 to “1”. The node Ne also adds its own path utilization rate Lb (= 0) to the cumulative utilization rate S2, but the cumulative utilization rate S2 remains “0”. The node Nc adds the path utilization rate Lc (= 1) of its own node to the cumulative utilization rate S1 (= 1) registered in the path connection request message received from the node Nb, and updates it to “2”. To the destination node Nd. Therefore, the cumulative utilization rate S1 registered in the path connection request message received by the destination node Nd via the nodes Nb and Nc is “2”.
[0016]
Similarly, the node Nf adds the path utilization rate Lf (= 0) of its own node to the cumulative utilization rate S2 (= 0) registered in the path connection request message M2 received from the node Ne to “0”. Update and transmit this to node Ng. The node Ng adds the path utilization rate Lg (= 0) of its own node to the cumulative utilization rate S2 (= 0) registered in the path connection request message received from the node Nf, and sets the sum to "0". Nc. The node Nc adds the path utilization ratio Lc (= 1) of its own node to the accumulated utilization ratio S2 (= 0) registered in the path connection request message received from the node Ng, and updates the accumulated utilization ratio Sc to “1”. To the destination node Nd. Therefore, the cumulative utilization rate S2 registered in the path connection request message received by the destination node Nd via the nodes Ne, Nf, Ng, and Nc is “1”.
[0017]
The destination node Nd compares the cumulative utilization rates S1 and S2 of the paths, selects a path having a smaller value, and unicasts the path connection response message. When the source node Na receives the path connection response message, a path is established between the source node Na and the destination node Nd.
[0018]
As described above, according to the present invention, the cumulative utilization rate S of the path is registered in each path connection request message received by the destination node, and the destination node can select a route with a small cumulative utilization rate S and establish a path. The best path can be easily selected. In addition, when viewed as a whole network, even under a situation where a plurality of paths are established, traffic is distributed and concentration of paths to some nodes is prevented, so that network use efficiency is improved.
[0019]
Next, operations of the source node, the relay node, and the destination node in the present embodiment will be described in detail with reference to the flowcharts of FIGS. In this embodiment, it is assumed that the node Na is the transmission source and the node Nd is the destination.
[0020]
FIG. 2 is a flowchart showing the operation of the transmitting node Na. In step S101, the node Na that has received the packet transmission request from the upper layer, the application layer, acts as a transmission source node, and determines in step S102 whether a path to the designated destination node Nd has already been established. . If the path has not been established, the process proceeds to step S103, and the number of trials K is set to “1” as an initial value. In step S104, a path connection request message destined for the node Nd is broadcast.
[0021]
Next, the operation of each relay node and destination node that have received the path connection request message will be described with reference to the flowchart of FIG.
[0022]
In step S201, the node that has received the path connection request message determines in step S202 whether the destination is its own node. If the destination is other than the own node, it behaves as a relay node, and determines in step S203 whether a path to the designated destination has already been established. If the path to the destination has not been established, it is determined in step S204 whether the received path connection request message is new. In the present embodiment, if at least one of the source node and the destination node registered in the path connection request message is different from the source node and the destination node of the path connection request message received earlier, It is determined that the message is a new message, and the process proceeds to step S205.
[0023]
In step S205, as shown in FIG. 5, the adjacent node that relays the message and transfers the message to the own node is registered in the routing table as the next hop when transmitting data to the transmission source. That is, the node Nc that has received the path connection request message broadcasted by the transmission source node Na from the node Nb registers the node Nb as a next pop of the packet addressed to the node Na. In step S206, the cumulative utilization rate S registered in the received path connection request message is read. In step S207, the path utilization rate L of the own node is added to the cumulative utilization rate S and updated. In step S208, a path connection request message in which the updated cumulative usage rate S is registered is rebroadcast.
[0024]
On the other hand, in step S202, if the destination of the received path connection request message is the own node, the path connection request message acts as a destination node. In step S209, the accumulated utilization rate S registered in the path connection request message is stored. In step S210, the process waits for a predetermined time in preparation for reception of the same message arriving via another path. In the meantime, every time the same message is received via another path, the accumulated utilization rate S is all stored in step S209.
[0025]
When the predetermined standby time has elapsed, the process proceeds to step S211 and the path having the lowest cumulative utilization rate S is selected as the optimal path from the plurality of paths. In step S212, a path connection response message to the path connection request message having the lowest cumulative utilization rate S is unicast. The lowest cumulative utilization rate S is registered in this path connection response message.
[0026]
As shown in FIG. 7, if the node Nb receives a path connection request message destined for the node Nd when a path has already been established between the nodes Nb and Nd, in step S203 the destination is reached. It is determined that the path has already been established, and the process proceeds to step S212. In the node Nb, the cumulative utilization S of the path is registered, and in step S212, the path connection response message in which the cumulative utilization S of the path is registered is unicast to the transmission source node Na.
[0027]
FIG. 4 is a flowchart illustrating an operation of each relay node receiving the path connection response message.
[0028]
Upon receiving the path connection response message in step S301, in step S302, it is determined whether a path from the own node to the transmission source node Na has already been established. If not, the process proceeds to step S305. On the other hand, as shown in FIG. 8, if the node Nc receives the path connection response message when the path is already established between the nodes Na and Nc, the process proceeds to step S303.
[0029]
In step S303, the cumulative utilization rate S (new) registered in the path connection response message is read, and in step S304, it is compared with the cumulative utilization rate S (pre) of the already established path. If the current cumulative utilization rate S (new) is lower than the cumulative utilization rate S (pre) of the already established path, the path connection response message is relayed in step S305 as shown in FIG. The adjacent node is registered in the routing table as the next hop when transmitting the packet to the destination. That is, the node Nb that has received the unicast path connection response message from the destination node Nd from the node Nc registers the node Nc as the next pop of the packet destined for the node Nd. The route table of each node through which the unselected path passes is deleted after a predetermined time.
[0030]
In step S306, the accumulated utilization rate S registered in the received path connection response message is read and held. This cumulative utilization rate S is used as the “cumulative utilization rate S (pre) of the current path” in the next step S304. In step S307, the path connection response message is transmitted to the next hop based on the routing table.
[0031]
Next, returning to the flowchart of FIG. 2, the operation of the source node Na receiving the path connection response message will be described.
[0032]
In step S105, the transmission source node determines whether a path connection response message unicast from the destination node Nd to the own node has been received in response to the path connection request, and determines whether a path connection response message has been received. Goes to step S106. In step S106, it is determined whether or not the time elapsed since the transmission of the path connection request message has exceeded a predetermined retry waiting time, and the flow returns to step S105 until the time has elapsed.
[0033]
Thereafter, when the retry waiting time has elapsed and this is detected in step S106, it is determined in step S107 whether the number of trials K has exceeded a retry upper limit Kmax, and it is determined that the number of trials has not exceeded at first. Therefore, the number of trials K is counted up in step S108, and thereafter, the process returns to step S104, where the path connection request message is broadcast again.
[0034]
After that, until the reception of the path connection response message is detected in step S105, the path connection request message is rebroadcast every time the retry waiting time elapses. If it is determined in step S107 that the number of trials K has reached the retry upper limit value Kmax, the packet is discarded in step S109. In step S110, a message to the effect that the packet has been discarded is notified to the upper layer.
[0035]
On the other hand, the path connection response message is received before the number of trials K exceeds the retry upper limit Kmax, and if this is detected in step S105, the process proceeds to step S111. In step S111, it is determined whether the same path as the path registered in the received path connection response message has already been established. If the path has been established, the process proceeds to step S112, where the accumulated utilization rate S (new) registered in the path connection response message is read, and in step S113, the accumulated utilization rate S (pre) of the already established path is read. Is compared to
[0036]
If the cumulative usage rate S (pre) is lower than the cumulative usage rate S (new), the process proceeds to step S116, and the packet requested to be transmitted is transmitted to the destination using the established path. If the cumulative usage rate S (new) is lower than the cumulative usage rate S (pre), or if it is determined in step S111 that the path has not been established, the process proceeds to step S114.
[0037]
In step S114, the route information registered in the path connection response message is written in the route table of the own node. As a result, a path is established between the nodes Na and Nd. In step S115, the cumulative utilization rate S registered in the path connection response message is stored. This accumulated utilization rate S is determined by the current cumulative utilization rate S (in step S304 of FIG. 4) when the own node behaves as a relay node of another path connection request message addressed to the node Nd. pre)). In step S116, the packet requested to be transmitted is transmitted to the destination using the established path.
[0038]
【The invention's effect】
According to the present invention, the following effects are achieved.
(1) A destination node that has received a plurality of path connection request messages having the same transmission source and destination but different paths can evaluate each path based on communication capability information registered in each path connection request message. , You can easily select the best path.
(2) Even under a situation where a plurality of paths are established, traffic is distributed and concentration of paths to some nodes is prevented, so that network use efficiency is improved.
[Brief description of the drawings]
FIG. 1 is a diagram for explaining a basic operation of a path selection method to which the present invention is applied.
FIG. 2 is a flowchart showing a procedure in which a transmitting node broadcasts a path connection request message.
FIG. 3 is a flowchart illustrating operations of a relay node and a destination node that have received a path connection request message.
FIG. 4 is a flowchart illustrating an operation of each relay node that has received a path connection response message.
FIG. 5 is a diagram illustrating an example of route information registered by a relay node based on a path connection request message.
FIG. 6 is a diagram illustrating an example of route information registered by a relay node based on a path connection response message.
FIG. 7 is a diagram schematically illustrating a state where a path requested by a path connection request message has already been established;
FIG. 8 is a diagram schematically illustrating a state where a path requested by a path connection response message has already been established;
FIG. 9 is a diagram showing a configuration of an ad hoc network.
FIG. 10 is a diagram showing a routing procedure (part 1) in a conventional ad hoc network.
FIG. 11 is a diagram showing a routing procedure (part 2) in a conventional ad hoc network.
[Explanation of symbols]
Na, Nb, Nc, Nd, Ne, Nf, Ng ... wireless node

Claims

A plurality of wireless nodes autonomously build a wireless network in a distributed manner, a source node designates a destination node, broadcasts a path connection request message broadcast by another wireless node in cooperation with the destination node, and the destination node In an ad hoc network in which a path is established between the source node and the destination node by unicasting a path connection response message to the source node in response to the path connection request message,
A step of registering, in each path connection request message, information on the communication capability of the path followed by the path connection request message;
A procedure in which the destination node receiving the plurality of path connection request messages having different paths selects one path based on the communication capability information registered in each path connection request message,
The destination node unicasting a path connection response message for the selected one path.

The step of registering the communication capability information includes:
A procedure in which each node that relays the path connection request message updates the communication capability information registered in the path connection request message based on the communication capability of the own node;
2. The method according to claim 1, further comprising the step of: each of the relay nodes rebroadcasting the updated path connection request message of the communication capability information.

Each of the relay nodes,
When receiving a path connection response message relating to the same path as the already established path, the communication capability information registered in the path connection response message is compared with the communication capability information relating to the already established path. Instructions and
If the communication capability of the path registered in the path connection response message is superior to the communication capability of the already established path, the path connection response message is unicast, thereby establishing the path connection response message. 3. The method according to claim 2, further comprising: changing a path to a new path.

The source node is
When receiving a path connection response message for an already established path, a procedure for comparing communication capability information registered in the path connection response message with communication capability information for the already established path,
Changing the already established path to a new path if the communication ability of the path registered in the path connection response message is better than the communication ability of the already established path. 4. The routing method for an ad hoc network according to claim 1, wherein: