(57)【要約】  本発明は、アドホックマルチ−ホップ通信ネットワークにおけるデータの質的ルーティンのための方法に関し、この方法は、決定可能な通信品質判定基準に基づき、前記ネットワークのソースノードとディスティネーションノードの間のリンクを通るデータの通過のための少なくとも一つの経路を決定することが可能であり、リンクは、データの通過の間、互いに干渉可能である。本発明によれば、経路の決定のため、フロー内干渉が考慮され、そして全体的ネットワークトポロジーを決定するステップおよび干渉リンクを決定するステップが行われ、後者のステップは対立グラフを決定することにより行われる。経路は完全制約を有する線形システムを解くことにより得られる。【選択図】  図１
2013513987.tif 000002
【特許請求の範囲】
【請求項１】
アドホックマルチホップ通信ネットワークにおけるデータの質的ルーティングのための方法であって、この方法は、決定可能な通信の品質判定基準に基づき、前記ネットワークのソースノードとディスティネーションノードの間のリンクを通るデータの通過のための少なくとも一つの経路を決定することが可能であり、所定の経路の品質判定基準の値は、前記ネットワークにおけるリンクの少なくとも一つの決定可能なメトリックに基づいて演算可能であり、リンクは、データの通過の間、互いに干渉可能である方法において、
経路の決定において、フロー内干渉が考慮され、そして満足すべきバンド幅の最小値Ｂである通信品質判定基準として、アドホックネットワークルーティングプロトコルは、ネットワークの全体的トポロジーを決定するために使用され、そしてパラメータＨ＞１とすると、干渉リンクは次のようにして決定され：
−ルーティングプロトコルが機能的であるとすると、ネットワークの各ノードは、全体的対立グラフを決定し、ここで、該対立グラフにおいて、各頂点は部分的な全体的トポロジーを示し、そしてこの全体的対立グラフの各縁部は部分的な全体的トポロジーの２つのリンクの間の対立関係を示し、すなわち、これらのリンクは、部分的な全体的トポロジーに従って、最大Ｈホップで分離され；
−全体的対立グラフを有する各ノードは、全体的対立グラフのクリークと呼ばれる、最大の完全部分グラフを決定し、そして前記ノードは、完全制約を有する線形システムを解くことにより、ネットワークにおける通過経路を決定する
ことを特徴とする方法。
【請求項２】
ネットワークにおける通過経路の決定は、以下の完全制約を有する以下の線形システムを解くことによって得られ：
2013513987.tif 000010
ここで、ｓがソースノードであり、ｔがディスティネーションノードであり、ｉ,ｊがネットワークノードの指標となる指数であり、Ｃｉｊがノードｉおよびｊの間のリンクの無負荷データレート容量であり、Ｂｉｊが存在するフローのためのノードｉおよびｊの間のリンクで使用される無負荷容量の比率であり、従って、１に対するＢｉｊの差は、前記リンク（ｉ，ｊ）における無負荷容量に対して残存する使用可能なフリーフローの比率に相当することを考慮すると、Ｋは、全体的対立グラフのクリークのセットであり、Ｅは、ノード間のリンクのセットである
ことを特徴とする請求項１に記載の方法。
【請求項３】
使用されるアドホックネットワークルーティングプロトコルが、ＯＬＳＲ、ＡＯＤＶ、ＤＳＲ、ＴＢＲＰＦ、またはＦＳＲであることを特徴とする請求項１または２に記載の方法。
【請求項４】
ネットワークの部分的な全体的トポロジーおよび対立グラフの決定のステップはノード内で別個に行われ、対立グラフはネットワークの部分的な全体的トポロジーの決定の後に決定されることを特徴とする請求項１、２または３に記載の方法。
【請求項５】
ネットワークが無線ネットワークであることを特徴とする請求項１〜４のいずれかに記載の方法。
【請求項６】
最大の完全部分グラフの決定のため、ボロン−ケルボッシュ（Bron-Kerbosch）の正確な方法またはアプローチ方法の中から選択された方法が使用されることを特徴とする請求項１〜５のいずれかに記載の方法。
【請求項７】
使用されるルーティングプロトコルがＯＬＳＲであり、そこで、各ＭＰＲ−Ｓに使用される無負荷容量の比率と共に無負荷容量の値が制御メッセージＴＣに導かれることを特徴とする請求項３に記載の方法。
【請求項８】
請求項１〜７のいずれかの方法を作動するために特別に構成されたアドホックマルチ−ホップ通信ネットワークノード管理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチホップネットワークにおけるサービスの予め定められた質による経路（ｐａｔｈ）の演算方法、およびネットワークノード管理設備に関するものである。本発明は、通信ネットワーク上のデータ変換の管理の分野において、特に無線（ｗｉｒｅｌｅｓｓ）アドホックネットワーク上の実時間マルチメディアアプリケーション、アドホックネットワーク上の音声、アドホックネットワーク上のビデオ会議に適用される。これは、このようなアプリケーションがウェブやファイル転送などの他の古典的なアプリケーションと共存することを可能にする。
【背景技術】
【０００２】
ルーティングは、ネットワークにおいて、ソースノードとディスティネーションノードの間の経路を見つけることにある。この経路は、ディスティネーションへ宛てられたデータパケットによりたどられる。経路は、一連のリンクである。リンクは、ネットワークの隣接する２つのノードを接続する物理的接続である。リンクにおけるメトリック(metrics)は、与えられた瞬時にリンクの状態に結びつける値である。経路におけるメトリックは、経路を作り上げる各リンクにおけるメトリックの組み合わせ（付加、乗算、最小、または他の関数）である。
【０００３】
アプリケーションは、サービスの質のレベルが十分な経路をたどるようにネットワーク上で変化させるパケットが必要であろう。ここで用いる“サービスの質”とは、ネットワークにおけるソースとディスティネーションの間のリンクを特徴付ける測定可能な値、例えば、伝達遅延、可能性がある最大データ率、パケット損失率等のセットである。
【０００４】
このために、サービスの質の満足するレベルを提供する経路の演算が必要である。したがって、アプリケーションがネットワークを介して互いに通信するとき、変換されるデータパケットは、そのオペレーションに必要なサービスの質のレベルを該アプリケーションに提供する経路をたどる。
【０００５】
従来、有線ネットワークにおいては、リンクにおけるメトリックは、しばしば他のリンクの状態とは独立しており、その見積もりは容易であった。これに対し、無線ネットワークにおいては、リンクの状態は、ずっと頻繁に他のリンクの状態に依存する。それは、リンクにおけるメトリックを無線ネットワークにおいて見積もることをより困難にしている。
【０００６】
一般に、１つまたはそれ以上のメトリックは、“サービスの質を伴った”ルーティングにおいて使用され、ここで、問題は、これらのメトリックのおのおののためのアプリケーションに必要な値を満たす経路が見つけ出されることである。
【０００７】
存在するルーティングアルゴリズムは、これらのメトリックに対する経路の使用の影響を無視する。それを通過することにより、パケットはリンクの状態を変更し、そして、従来の方法においては、この変更は、満足な結果をもたらすであろう経路の初期の演算において考慮されない。実際、サービスの質を伴う経路の演算のために存在するアプローチは、リンクにおけるメトリックが、それを通過するデータパケットのみにより変更されるであろうという推測に基づくものである。無線ネットワークにおける経験は、この推測が多くのケースにおいてふさわしくないものであることを示している。
【０００８】
特に、ルーティング方式は、特許文献１および特許文献２に開示されているが、それらは、ある限定に悩まされている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許出願公開２００６／２２７７２４号明細書
【特許文献２】米国特許出願公開２００２／０３６９８７号明細書
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本発明は、リンクのメトリックがまた、演算された経路を完全なものとする他のリンクに依存する故に、メトリックの見積もりが経路自体の演算とは切り離されないことを提供する。したがって、満足のいくレベルのサービスの質を提供する複数の経路の演算をするため、通過するパケットにより経路自体で発生する干渉が、考慮される。
【００１１】
本発明の実施の結果、演算された複数の経路は、それらが提供するサービスの質のレベルが十分であるので、それらを使用するアプリケーションの要求を十分に充足する。その結果、そのアプリケーションは適正に作動することができる。この十分なサービスの質を備えた経路を使用する可能性は、ネットワークにより提供される更なる資源を使用しない演算された経路を取得するアプリケーション間の通信を保障する。したがって、ネットワークの飽和は回避される。最後に、一般的な方法において、ネットワークにより提供される資源は、アプリケーションによってより良好に共有され、これによって、異なった要求を持つアプリケーションの共存を可能にする。
【００１２】
したがって、本発明は、アドホックマルチホップ通信ネットワークにおけるデータの質的ルーティングのための方法に関し、この方法は、決定可能な通信の品質判定基準に基づき、前記ネットワークのソースノードとディスティネーションノードの間のリンクを通るデータの通過のための少なくとも一つの経路を決定することを可能にし、与えられた経路の品質判定基準の値は、前記ネットワークにおけるリンクの少なくとも一つの決定可能なメトリックに基づいて演算可能であり、リンクは、データの通過の間、互いに干渉可能である。本発明によれば、経路の決定において、フロー内干渉が考慮され、そして満足すべきバンド幅の最小値Ｂである通信の品質判定基準として、アドホックネットワークルーティングプロトコルは、ネットワークの全体的トポロジーを決定するために使用され、そして与えられたパラメータＨ＞１，すなわち干渉リンクは次のようにして決定される：
−ネットワークの各ノードは、次のように規定される全体的対立グラフを決定し：この全体的対立グラフの各頂点は、部分的な全体的トポロジーにおけるリンクを示し、この全体的対立グラフの各縁は、部分的な全体的トポロジーの２つのリンクの間の対立関係を示し、すなわち、これらのリンクは、部分的な全体的トポロジーに従って、最大Ｈホップで分離され；
−全体的対立グラフを有する各ノードは、全体的対立グラフの“クリーク”と呼ばれる、最大の完全部分グラフ（full sub-graphs）を決定し、前記ノードは、特に以下の完全制約(integrality
constraints)を有する以下の線形システムを解くことにより、ネットワークにおける通過経路を決定する：
2013513987.tif 000003
ここで、ｓがソースノードであり、ｔがディスティネーションノードであり、ｉ,ｊがネットワークノードの指標となる指数であり、Ｃｉｊがノードｉおよびｊの間のリンクの無負荷データレート容量であり、Ｂｉｊが存在するフローのためのノードｉおよびｊの間のリンクで使用される無負荷容量の比率であり、従って、１に対するＢｉｊの差は、前記リンク（ｉ，ｊ）における無負荷容量に対して残存する使用可能なフリーフローの比率に相当することを考慮すると、Ｋは、全体的対立グラフのクリークのセットであり、Ｅは、ノード間のリンクのセットである。
【００１３】
本発明の種々の実施形態においては、個々に、あるいは、いかなる技術的に可能な組み合わせにおいて考慮される以下の手段が使用される：
−ネットワークの全体的トポロジーを決定するステップにおいて、ネットワークのフルローカルトポロジーが決定され、
−ネットワークの全体的トポロジーを決定するステップにおいて、ネットワークの部分的な全体的トポロジーが決定され、
−ネットワークの全体的トポロジーを決定するステップにおいて、後者が次のように決定され：
−ネットワークの各ノードが、一方で、“ワン−ホップ”（ｏｎｅ−ｈｏｐ）といわれる全ての直接のネイバー（ｎｅｉｂｏｕｒ）に相当する全てのノード、および、次いで“ツー−ホップ”（ｔｗｏ−ｈｏｐ）といわれる直接のネイバーの全ての直接のネイバー、および、他方で、それ自体とそのワン−ホップネイバーの間の全てのリンク、およびそのワン−ホップネイバーとそれら自体のワン−ホップネイバーの間の全てのリンクを備えるネットワークの全体ローカルトポロジーを決定し；前記トポロジーが、ツー−ホップ全体ローカルトポロジーと称され、
−各ノードは“ＭＰＲ”と称されるネイバーのサブ−セットを決定し、そのネイバーのサブ−セットは、それをすべてのそのツー−ホップネイバーに接続することを許容し、そしてＭＰＲとして決定されているリストのネイバー（単数、複数）をワン−ホップネイバーに周期的に伝達し、
−少なくとも一つのネイバーによりＭＰＲとして決定されている各ノードは、ＭＰＲとして選択されているリストのネイバー（単数、複数）をネットワーク上に周期的に送信し、前記リストは“ＭＰＲ−Ｓ”リストと呼ばれ、
−ＭＰＲ−Ｓリストを集約することにより、各ノードは、全てのノードと、ネットワークにおいて互いのノードに向けて少なくとも一つの経路を探し出すことを許容する複数のノードの間のリンクのセットを備えるネットワークの部分的な全体的トポロジーを再構成し、
−使用されるアドホックネットワークルーティングプロトコルは、ＯＬＳＲ、ＡＯＤＶ、ＤＳＲ、ＴＢＲＰＦ、またはＦＳＲであり、
−ネットワークの部分的な全体的トポロジーおよび対立グラフを決定するステップがノード内で別々に実行され、該対立グラフはネットワークの部分的な全体的トポロジーの決定の後に決定され、
−一つのノードに隣接した無負荷容量の各リンクは、隣接するリンクの間に存在する対立を効果的に考慮する方法により決定され、
−存在するリンクによって使用される無負荷容量の比率は、タイムユニットにより各リンクに送られてくるデータ量の集計に基づく方法により決定され、
−ネットワークは、無線ネットワークであり、
−最大の完全部分グラフの決定のため、the Bron-Kerbosch algorithm（１９７３）のような厳密アルゴリズムまたはアプローチ方法のいずれかが使用され、
−各ＭＰＲ−Ｓのために使用される無負荷容量の比率と同様の無負荷容量の値は、ＯＬＳＲプロトコルの制御メッセージＴＣに導入される。
【００１４】
本発明はまた、上記された方法にしたがって作動するように特別に構成されたアドホックマルチ−ホップ通信ネットワークノード管理システムに関する。
【００１５】
本発明は、限定されることなく、図面を参照しつつ、以下の実施形態及び実装により例示される。
【図面の簡単な説明】
【００１６】
【図１】スターティングノードａとディスティネーションノードｖの間のノードと２つの経路を有する典型的な無線通信ネットワークのダイアグラムである。
【図２】スターティングノードａとディスティネーションノードｆの間のノードと２つの経路を有する別の典型的な無線通信ネットワークのダイアグラムである。
【発明を実施するための形態】
【００１７】
典型的な実施形態を手段として、経路を構築するノードの間の異なったリンクの容量に基づく経路の容量の計算が示される。ノードは少なくとも受信・中継システムであり、この受信・中継システムは、それを通るフローを管理する演算手段を備えている。実際には、ノードは特に通信ネットワーク専用システム、あるいは、例えばマイクロコンピューターの通信ネットワークにおけるマイクロコンピューターなどの他の機能をさらに保障するシステムであってよい。ノードは、一つまたはいくつかの他のノードからデータを受信し、該データを一つまたはいくつかの他のノードに中継する。複数のノード間のリンクは、有線でよいが、好ましくは、無線、特に無線通信タイプのものが好ましい。アドホックネットワークにおいては、トポロジーが時間とともに変化してもよく、また、データ経路（複数）が時間とともに変化してもよい。経路の管理は、該管理に参画する各ノードにより、割り当てられた方法で行われる。
【００１８】
Ｘビット／秒のバンド幅を必要とするビデオストリームを始めることを欲するソースノードの場合を例にとって考えてみよう。存在するモデルで、経路の容量は、リンクにより提示された最小の容量であろう。さらに、複数のリンクは、相互に関連付けられ、そして並行して送信できない。その結果として、予期されるバンド幅を効果的に得るために、Ｘビット／秒のバンド幅のために見つけ出されるべき経路は、事実、相互関係を含む最小値がＸより多いか、またはそれと等しい経路であろう。
【００１９】
図２には、ソースからディスティネーション（ａからｖ）へ送信するために存在する二つの可能性における実施例が示されている。実線円はノードｈおよびｏのサービスエリアに描かれ、点線円は干渉エリアに描かれている。
【００２０】
ノードがリンク（例えば、ｏからｐ）上で伝わると、ｏおよびｐの干渉エリアにおける他のノードは送信することができない。したがって、このリンクにおける有効容量は、リンクにより使用されている容量に基づいており、このリンクの少なくとも一つの端部は、リンクの少なくとも一つの端部の干渉エリア内にある。拡大解釈すれば、経路の有効容量は、リンクにより使用されている容量に基づいており、このリンクの少なくとも一つの端部は、経路の少なくとも一つのリンクの少なくとも一つの端部の干渉エリア内にある。したがって、この現象を考慮に入れて満足する経路を探すのは、非常に複雑であり、かつ現存する解決手段はこの問題を無視している。
【００２１】
本発明によれば、少なくとも所定の有効容量を提供する経路が、複数のリンクの容量間の相互の関連性を考慮している間に、決定される。この目的で、ネットワーク管理演算機が、この経路決定ための演算アルゴリズムを実行する。この目的のため、ネットワークトポロジーは、例えば、ＯＬＳＲのようなプロアクティブ型（ｐｒｏａｃｔｉｖｅ）ルーティングプロトコルにより算出されて、決定され、そして要求されているバンド幅を満足する経路に復帰される。いくつかのステップが実行される：
−データフローの通過なしに互いに対して干渉するリンクのグループ分けを行い、次いで
−フロー内干渉を考慮して、様々な可能性の中で経路を選択する。
【００２２】
より正確には、ネットワークトポロジーは、アドホックネットワークのためのルーティングプロトコルを用いて決定される。存在するプロトコルの内、例えば、以下のように作動するＯＬＳＲ（”Optimized Link State Routing”）プロトコルが使用されても良い：
−ノードは、最近ノードがＨＥＬＬＯメッセージを受信した隣接ノードのリストを含むＨＥＬＬＯメッセージを定期的に交換し；
−受信したＨＥＬＬＯメッセージに含まれる情報を集約することにより、各ノードは、“ワン−ホップ”（ｏｎｅ−ｈｏｐ）といわれる全ての直接のネイバー、および“ツー−ホップ”といわれるネイバーのネイバー、およびそれ自身とワン−ホップネイバーとの間ならびにそのワン−ホップネイバーとそれら自身のワン−ホップネイバーとの間のすべてのリンクを含むネットワークのフルローカルトポロジーをメモリー中に再構成し；
−各ノードは、全てのツー−ホップネイバーを連繋することを可能にする“マルチポイント中継”のための“ＭＰＲ”といわれるネイバーのサブセットを選択し、そしてネイバーがＭＰＲとして選択されているＨＥＬＬＯメッセージでリポートし；
−少なくとも一つのネイバーによりＭＰＲとして選択された各ノードは、ＭＰＲとして選択され、“ＭＰＲ−セレクター”のための“ＭＰＲ−Ｓ”と称されるネイバーのリストを含むＴＣ（“トポロジーコントロール”）と称されるネットワークメッセージ上に周期的に送信し；
−ＴＣメッセージに含まれる情報を集約することにより、各ノードは、全てのノードと、各ノードに向けての一つの経路を探し出すことを許容するノードの間の十分なリンクを含むネットワークの部分的な全体的トポロジーをメモリー内で再構成する。
【００２３】
解決のパラメータは、ホップＨの数であり、この数を超えない値で、２つのリンクが同一容量リソース（バンド幅）をシェアしている。無線ネットワークにおいては、ノードが共通の無線媒体を使用するとき、複数のリンクが同時に全て使用されることはない。
【００２４】
したがって、共通のリソースのための対立においてリンクのセットを決定するという問題が生ずる。この目的で、各ノードは対立グラフを維持し：
−この対立グラフの各頂点は、部分的な全体的トポロジーを示し；
−この対立グラフの各縁部は、部分的な全体的トポロジーの２つのリンク間の対立関係を示す。
対立グラフのクリーク（最大の完全部分グラフ）は、共通の容量リソースために対立するリンクのセットを示す。
【００２５】
経路を決定するため、以下のような方法が実施される。ソースノードｓ、ディスティネーションノードｔおよび最小のバンド幅Ｂが満足の行くものであるとすると、実現可能な経路は、以下の完全制約を有する線形プログラムの解である：
2013513987.tif 000004
ここで、Ｋは対立グラフのクリークのセットであり、Ｃｉｊはリンク（ｉ，ｊ）の無負荷容量であり、Ｂｉｊは既に使用された無負荷容量の一部分である。
【００２６】
図１に戻って、これらの方法を適用するとき、ツー−ホップ干渉を考慮すると、下記のクリークのセットが得られる：
2013513987.tif 000005
【００２７】
経路（ａ，ｂ，ｃ，ｄ，ｅ，ｆ）における有効容量は、
2013513987.tif 000006
で、最大値Ｒ０を探し出すことによって得られる。
【００２８】
図１において、ノード間に示された数値は、残余／有効容量（すなわち、１−Ｂ．．）の値に相当する。不均衡の先のリストにおいて、Ｂ．．はそれらの値に置き換えられ、そして以下が得られる：
2013513987.tif 000007
これらの方程式を満足させる最大値Ｒ０は、したがって１／１２である。
【００２９】
同様に、（ａ，ｇ，ｈ，ｉ，ｊ，ｋ，ｆ）における有効容量は、
2013513987.tif 000008
で、最大値Ｒ１を探し出すことにより演算される。
Ｂ．．をそれらの値に置き換えることによって、以下が得られる：
2013513987.tif 000009
これらの方程式を満足する最大値Ｒ１は、したがって１／６である。
【００３０】
したがって、本発明の方法によれば、これら２つの経路の容量がそれぞれ１／１２および１／６と演算され得、したがって、第２経路が容量の観点からベストであるとして決定される。一方、現存する技術では、第１経路が容量の観点からベストのものとして選択されたであろう。
【００３１】
品質判定基準を満たす経路を決定するために行われる演算は、メトリックが用いられる。これらのメトリックは、ビット／秒における容量、ソースをディスティネーションから分離するホップの数値、またはソースからディスティネーションへのパケット伝達の遅延であってよい。これらのメトリックは、品質判定基準を規定するために互いの間で組み合わされてよく：
−（端部から端部までの遅延＜ｙ秒）および（容量＞Ｘビット／秒）の関係を満たしつつ、ホップ数の最短経路を見つけ出す。
【００３２】
本発明は、詳細な説明および特許請求の範囲により規定された範囲から逸脱することなく他の多くの可能性に従い適用されることが理解されよう。
【図１】
2013513987.tif 000011
【図２】
2013513987.tif 000012
【国際調査報告】
2013513987.tif 000013
2013513987.tif 000014
2013513987.tif 000015
2013513987.tif 000016
2013513987.tif 000017
2013513987.tif 000018