(57)【要約】【課題】  制御のためのオーバーヘッドが最小で、ルートコストに伴う最適のルートの探索を可能にするルーティング方法を提供する。【解決手段】  本発明に係るルーティング方法は、ルート探索のためにブロードキャストされる第１パケットを受信し、第１パケットのルートコストに基づいて、第１パケットがバックオフされる時間である第１バックオフ時間を算出する。そして、第１バックオフ時間内に第１パケットと重複する第２パケットを受信しないと、第１パケットを再ブロードキャストする。一方、第１バックオフ時間内に第２パケットを受信すれば、第２パケットのルートコストに基づいて、第２パケットがバックオフされる時間である第２バックオフ時間を算出し、第１および第２バックオフ時間の比較結果に応じて、第１および第２パケットのうち、何れかを再ブロードキャストする。【選択図】      図２Ａ
2005229624.tif 000002
【特許請求の範囲】
【請求項１】
ルート探索のためにブロードキャストされる第１パケットを受信するステップと、
前記第１パケットのルートコストに基づき、前記第１パケットがバックオフされる時間である第１バックオフ時間を算出するステップと、
前記第１バックオフ時間内に前記第１パケットと重複する第２パケットが受信されないと、前記第１パケットを再ブロードキャストするステップと、
前記第１バックオフ時間内に前記第２パケットが受信されれば、前記第２パケットのルートコストに基づき、前記第２パケットがバックオフされる時間である第２バックオフ時間を算出し、前記第１および第２バックオフ時間の比較結果に応じて、前記第１および第２パケットのうち、何れかを再ブロードキャストするステップと、
を含むことを特徴とするルーティング方法。
【請求項２】
前記ルートコストは、リンク品質、エネルギ効率、およびセキュリティ性のうち、少なくとも１つに基づいて算出されることを特徴とする、請求項１に記載のルーティング方法。
【請求項３】
前記第１および第２パケットは、ＲＲＥＱパケットであることを特徴とする、請求項１に記載のルーティング方法。
【請求項４】
前記第１および第２パケットのうち、何れかを再ブロードキャストするステップにおいて、
前記第２バックオフ時間が前記第１バックオフ時間より短い場合、前記第２パケットを予め設定された時間後に再ブロードキャストし、
前記第２バックオフ時間が前記第１バックオフ時間より長いか、または同じであれば、前記第１パケットを前記第１バックオフ時間後に再ブロードキャストすることを特徴とする請求項１に記載のルーティング方法。
【請求項５】
前記予め設定された時間は、
前記第１パケットの到着時間に前記第２バックオフ時間を加えた第３バックオフ時間が現在時刻より早ければ、前記第３バックオフ時間となり、
前記第３バックオフ時間が現在時刻より遅ければ、再ブロードキャストが可能な最も早い時刻になることを特徴とする請求項４に記載のルーティング方法。
【請求項６】
前記予め設定された時間は、前記第２パケットの到着時間に前記第２バックアップ時間を加えた時間であることを特徴とする請求項４に記載のルーティング方法。
【請求項７】
前記第１パケットが再ブロードキャストされた後に、前記第２パケットが受信されれば、前記第２パケットを廃棄するステップをさらに含むことを特徴とする請求項１に記載のルーティング方法。
【請求項８】
前記第１パケットが再ブロードキャストされた後、前記第２パケットを受信するステップと、
前記第２バックオフ時間が前記第１バックオフ時間より短ければ、前記第２パケットを再ブロードキャストし、前記第１バックオフ時間を前記第２バックオフ時間に更新するステップと、
前記第２バックオフ時間が前記第１バックオフ時間より長いか、または同じであれば、前記第２パケットを廃棄するステップと
をさらに含むことを特徴とする請求項１に記載のルーティング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はルーティング方法に関し、さらに詳細には、リンク品質などのルートコストに基づいて算出されるバックオフ時間を利用して最適のルートを探索するルーティング方法に関する。
【背景技術】
【０００２】
一般に、ＡＯＤＶ(Ad hoc On Demand Distance Vector)のようなオンデマンド・ルーティング方法を用いれば、アドホックタイプ(Ad hoc type)無線ネットワークにおいて効率的にルートを探索することが可能となる。ＡＯＤＶルーティング方法において、ソースノード(source node)がルートに対する有効な情報を持っていない状態でディスティネーションノード(destination node)にデータを送信しようとする場合、ディスティネーションノードまでの可能なルートを探索するために、ネットワーク全体にＲＲＥＱ(Route REQest)パケットをフラッディングする。この場合、ルート探索に伴うトラフィックを制限するために、各々の中間ノードは常に最初に受信したＲＲＥＱパケットだけを再ブロードキャストし、最初に受信したＲＲＥＱパケットに重複したＲＲＥＱパケットがその後に受信されれば、重複したＲＲＥＱパケットは廃棄される。このようなＡＯＤＶルーティング方法は、ホップカウント(hop-count)ベースのルーティングに適合し、最短ルートの探索を可能とする。
【０００３】
しかし、ホップカウント以外のルートコストを考慮した場合、最初に受信したＲＲＥＱパケットが最適ルート探索を保証する訳ではない。すなわち、無線ネットワークにおいて、ホップカウントだけがルートコストの最も重要な基準になる訳ではなく、リンク品質、エネルギ効率、セキュリティ性などが主要な要素として考慮されねばならない。また、ＡＯＤＶルーティング方法は、最短ルートではなく最適のルートが必要な場合のような、ルートコストを考慮したコストベースのルーティングには適していない。それは、中間ノードが最初に受信したＲＲＥＱパケットだけを中継する場合には、最適のルートの探索が無視される可能性があるからである。
【０００４】
例えば、図１のようなネットワーク構成において、ソースをノードＳ、そして目的地をノードＤと仮定すると、ノードＦは、ノードＳとノードＦとの間の最短ルートであるＳ-Ｂ-Ｆのルートを介して最初のＲＲＥＱパケットを受信する。しかし、ノードＢはノードＳの送信境界(transmission border)１０およびノードＦの送信境界２０上に存在するために、Ｓ-ＢおよびＢ-Ｆのリンク品質は極めて劣悪となる。この場合、Ｓ-Ｃ-Ｅ-Ｆのルートがより高いリンク品質を保障するが、このルートを介して送信されたＲＲＥＱパケットは、ノードＦで重複したＲＲＥＱパケットとなって廃棄される。したがって、ノードＳは、リンク品質の点から見て最適のルートであるＳ-Ｃ-Ｅ-Ｆ-Ｇ-Ｄのルートの存在が分からなくなる。
【０００５】
全ての中間ノードが重複したＲＲＥＱパケットの中継を許容するならば、最適ルートを探索できる可能性は高くなる。しかしながら、大部分の中間ノードが多様な時間に渡って同じＲＲＥＱパケットを再ブロードキャストすれば、制御に伴うオーバヘッドが増加してしまう。したがって、全ての中間ノードが重複したＲＲＥＱパケットを中継する方法を用いると、無線デバイスの貴重なリソースを枯渇し、正常的なデータトラフィックが妨害されてしまう。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、上記の問題を解決するためになされたものであって、その目的は、制御のためのオーバーヘッドが最小で、最適のルートの探索を可能にするルーティング方法を提供することである。
【課題を解決するための手段】
【０００７】
前記目的を達成するための本発明に係るルーティング方法は、ルート探索のためにブロードキャストされる第１パケットを受信するステップと、前記第１パケットのルートコストに基づき、前記第１パケットがバックオフされる時間である第１バックオフ時間を算出するステップと、前記第１バックオフ時間内に前記第１パケットと重複する第２パケットが受信されないと、前記第１パケットを再ブロードキャストするステップと、前記第１バックオフ時間内に前記第２パケットが受信されれば、前記第２パケットのルートコストに基づき、前記第２パケットがバックオフされる時間である第２バックオフ時間を算出し、前記第１および第２バックオフ時間の比較結果に応じて、前記第１および第２パケットのうち、何れかを再ブロードキャストするステップとを含む。
【０００８】
前記ルートコストは、リンク品質、エネルギ効率、およびセキュリティ性のうち、少なくとも１つに基づいて算出されることが好ましく、前記第１および第２パケットは、ＲＲＥＱパケットであることが可能である。
【０００９】
前記第１および第２パケットのうち、何れかを再ブロードキャストするステップにおいて、前記第２バックオフ時間が前記第１バックオフ時間より短い場合、前記第２パケットを予め設定された時間後に再ブロードキャストし、前記第２バックオフ時間が前記第１バックオフ時間より長いか、または同じであれば、前記第１パケットを前記第１バックオフ時間後に再ブロードキャストすることが好ましい。この時、前記予め設定された時間は、前記第１パケットの到着時間に前記第２バックアップ時間を加えた第３バックオフ時間が現在時刻より早ければ、前記第３バックオフ時間となり、前記第３バックオフ時間が現在時刻より遅ければ、再ブロードキャストが可能で、かつ最も早い時刻になることが可能である。また、前記予め設定された時間に、前記第２パケットの到着時間に前記第２バックアップ時間を加えた時間を使用することもできる。
【００１０】
好ましくは、前記第１パケットが再ブロードキャストされた後、前記第２パケットが受信されれば、前記第２パケットを廃棄するステップをさらに含む。また、前記第１パケットが再ブロードキャストされた後、前記第２パケットを受信するステップと、前記第２バックオフ時間が前記第１バックオフ時間より短ければ、前記第２パケットを再ブロードキャストし、前記第１バックオフ時間を前記第２バックオフ時間に更新するステップと、前記第２バックオフ時間が前記第１バックオフ時間より長いか、または同じであれば、前記第２パケットを廃棄するステップとをさらに含むことも可能である。
【発明の効果】
【００１１】
本発明によれば、ルートコストに伴う最適のルートを探索することができる。そして、各中間ノードが設定されたバックオフ時間にＲＲＥＱパケットを再ブロードキャストすることによって、ＲＲＥＱパケットの送信衝突を防止できるので、制御のためのオーバーヘッドを減少させることができるという効果を奏する。
【発明を実施するための最良の形態】
【００１２】
以下に、図面を参照して本発明の実施形態を詳細に説明する。
本発明の実施形態に係るルーティング方法は、基本的に中間ノードで最初に受信したＲＲＥＱパケットを常に再ブロードキャストすることではなく、最初に受信したＲＲＥＱパケットとこれに重複したＲＲＥＱパケットの中で、ルートコストの観点で最適のルートを通じて送信されたＲＲＥＱパケットを再ブロードキャストする方法を用いる。
【００１３】
図２Ａおよび図２Ｂは、本発明の１実施形態に係るルーティング方法を説明するためのフローチャートである。まず、図２Ａに示すように、ネットワークにリンクされたある中間ノードが最初のＲＲＥＱパケットを受信すると(Ｓ１００でＹｅｓ)、その中間ノードはＲＲＥＱパケットの到着時間であるＲＱ＿ｓｔａｒｔを記録する(Ｓ１０５)。そして、ＲＱ＿ｓｔａｒｔ記録後に、ＲＱ＿ｂａｃｋｏｆｆnowを算出する(Ｓ１１０)。ＲＱ＿ｂａｃｋｏｆｆnowは、ソースノードからＲＲＥＱパケットを受信した中間ノードまでのリンク品質、エネルギ効率およびセキュリティ性などのルートコストに応じて、中間ノードにより設定されるバックオフ時間である。この場合、ＲＱ＿ｂａｃｋｏｆｆnowは、ルートコストが大きいほど大きくなるように設定される。そして、ＲＱ＿ｂａｃｋｏｆｆnowは最初に受信したＲＲＥＱパケットのバックオフ時間を示す。ＲＱ＿ｂａｃｋｏｆｆnowが算出されれば、(ＲＱ＿ｓｔａｒｔ＋ＲＱ＿ｂａｃｋｏｆｆnow)後に終了するように、ＲＲＥＱパケットを受信した中間ノード内のタイマーを設定する(Ｓ１１５)。
【００１４】
次に、図２Ｂに示すように、タイマーが設定された後、終了される時までの時間の間に最初に受信された第１パケットと同じデータを持っている重複したＲＲＥＱパケットである第２パケットを受信しない限り(Ｓ１２０、Ｓ１２５)、タイマーが終了した(ＲＱ＿ｓｔａｒｔ＋ＲＱ＿ｂａｃｋｏｆｆnow)後に、最初に受信したＲＲＥＱパケットを再ブロードキャストする(Ｓ１３０)。
【００１５】
図３において、「ＣＡＳＥ  I」と表示された部分が、前記の場合を時間軸で示したものである。図３において、「最初のＲＲＥＱ」と表された矢印は、最初に受信したＲＲＥＱパケットの到着時間を示し、「ＲＲＥＱの再ブロードキャスト」と表された矢印は、最初に受信したＲＲＥＱパケットが再ブロードキャストされる時間を示している。図３に示すように、重複したＲＲＥＱパケットがＲＱ＿ｓｔａｒｔ＋ＲＱ＿ｂａｃｋｏｆｆnow時間内に受信されなければ、最初に受信したＲＲＥＱパケットが再ブロードキャストされる。
【００１６】
(ＲＱ＿ｓｔａｒｔ＋ＲＱ＿ｂａｃｋｏｆｆnow)後に終了するようにタイマーが設定された場合に、最初に受信したＲＲＥＱパケットに続いて重複したＲＲＥＱパケットである第２パケットが受信されれば、ＲＱ＿ｂａｃｋｏｆｆdupが算出される(Ｓ１５０)。ＲＱ＿ｂａｃｋｏｆｆdupは、上述したように、ルートコストによって算出される重複したＲＲＥＱパケットのバックオフ時間である。
そして、算出されたＲＱ＿ｂａｃｋｏｆｆdupと、ＲＱ＿ｂａｃｋｏｆｆnowが比較される。この比較の結果、ＲＱ＿ｂａｃｋｏｆｆdup≧ＲＱ＿ｂａｃｋｏｆｆnowの場合は、重複したＲＲＥＱパケットは廃棄され(Ｓ１５５、Ｓ１６０)、最初に設定されたタイマーが終了する時に最初に受信したＲＲＥＱパケットが再ブロードキャストされる(Ｓ１２５、Ｓ１３０)。
【００１７】
一方、ＲＱ＿ｂａｃｋｏｆｆdup＜ＲＱ＿ｂａｃｋｏｆｆnowの場合は、最初に受信したＲＲＥＱパケットを廃棄し(Ｓ１６５)、ＲＱ＿ｂａｃｋｏｆｆnowはＲＱ＿ｂａｃｋｏｆｆdupに更新される(Ｓ１７０)。そして、予め設定された設定オプションによって決められた時間に重複したＲＲＥＱパケットを再ブロードキャストする(Ｓ１７５)。この時の設定オプションは、次の２つの方法のうち、何れかを選択できる。
【００１８】
第１の方法は、(ＲＱ＿ｓｔａｒｔ+ＲＱ＿ｂａｃｋｏｆｆdup）と現在時刻(Ｃｕｒｒｅｎｔ  Ｔｉｍｅ）を比較して、(ＲＱ＿ｓｔａｒｔ+ＲＱ＿ｂａｃｋｏｆｆ)＞Ｃｕｒｒｅｎｔ  Ｔｉｍｅであれば、(ＲＱ＿ｓｔａｒｔ+ＲＱ＿ｂａｃｋｏｆｆdup)にタイマーを再設定した後、再設定されたタイマーが終了される時に重複したＲＲＥＱパケットを再ブロードキャストすることである。その他の場合には、重複したＲＲＥＱパケットを直ちに再ブロードキャストする。
【００１９】
第２の方法は、タイマーは(ＲＱ＿ＤＵＰ＿ｓｔａｒｔ+ＲＱ＿ｂａｃｋｏｆｆdup)に再設定され、再設定されたタイマーが終了すれば、重複したＲＲＥＱパケットを再ブロードキャストすることである。ここで、ＲＱ＿ＤＵＰ＿ｓｔａｒｔは重複したＲＲＥＱパケットの到着時間を示す。
【００２０】
図３において、「ＣＡＳＥ  ＩＩ」と表示された部分が、前記の場合を時間軸で示したものである。図３において、「重複ＲＲＥＱ」と表示された矢印は、重複したＲＲＥＱパケットが到着した時間を示し、上述した第１の方法が「Ｏｐｔｉｏｎ  １」に相当し、第２の方法が「Ｏｐｔｉｏｎ  ２」に相当する。
【００２１】
一方、最初に受信したＲＲＥＱパケットを再ブロードキャストした後、最初に受信したＲＲＥＱパケットに重複するＲＲＥＱパケットが受信される場合があるが、この場合は次の２つの方法のうち、何れかで処理することできる。
【００２２】
第１の方法は、重複したＲＲＥＱパケットを単に廃棄することである。
第２の方法は、算出されたＲＱ＿ｂａｃｋｏｆｆdupとＲＱ＿ｂａｃｋｏｆｆnowとを比較する。その結果、ＲＱ＿ｂａｃｋｏｆｆdup＜ＲＱ＿ｂａｃｋｏｆｆnowの場合は、重複したＲＲＥＱパケットが最初に受信されたＲＲＥＱパケットより低いルートコストあることを意味し、それゆえ重複したＲＲＥＱパケットを直ちに再ブロードキャストする。そして、ＲＱ＿ｂａｃｋｏｆｆnowをＲＱ＿ｂａｃｋｏｆｆdupに更新する。一方、ＲＱ＿ｂａｃｋｏｆｆdup≧ＲＱ＿ｂａｃｋｏｆｆnowの場合は、重複したＲＲＥＱパケットのルートコストが最初に受信されたＲＲＥＱパケットに比べてルートコストが高いことを意味し、それゆえ重複したＲＲＥＱパケットを廃棄する。
【００２３】
図４において、「ＣＡＳＥ  ＩＩＩ」は前記の場合、すなわち、「Ｏｐｔｉｏｎ  １」で、重複したＲＲＥＱパケットが廃棄され、「Ｏｐｔｉｏｎ  ２」で、ＲＱ＿ｂａｃｋｏｆｆdup＜ＲＱ＿ｂａｃｋｏｆｆnowの場合に、重複したＲＲＥＱパケットが直ちに再ブロードキャストされる場合を示している。
【００２４】
以上、本発明の実施形態に係るルーティング方法では、最初に受信したＲＲＥＱパケットを無条件に再ブロードキャストしないで、ルートコストの観点で最適のルートに沿って送信されたＲＲＥＱパケットを再ブロードキャストするため、ルートコストベースの最適なルート探索が可能となる。
なお、本発明は、上記の実施形態に限定されるものではなく、本発明の範囲および技術的趣旨から逸脱せずに様々な変更が可能なことは当業者には理解できるであろう。
【産業上の利用可能性】
【００２５】
本発明はルーティング方法に関し、さらに詳細には、リンク品質のようなルートコストに基づいて算出されるバックオフ時間を利用して、最適のルートを探索するためのルーティング方法に適用することができる。
【図面の簡単な説明】
【００２６】
【図１】従来のルーティング方法を説明のための図面である。
【図２Ａ】本発明の１実施形態に係るルーティング方法を説明するためのフローチャートである。
【図２Ｂ】本発明の１実施形態に係るルーティング方法を説明するためのフローチャートである。
【図３】本発明の１実施形態に係るルーティング方法を説明するための図面である。
【図４】本発明の１実施形態に係るルーティング方法を説明するための図面である。
【図１】
2005229624.tif 000003
【図２Ａ】
2005229624.tif 000004
【図２Ｂ】
2005229624.tif 000005
【図３】
2005229624.tif 000006
【図４】
2005229624.tif 000007