(57)【要約】マルチホップ通信ネットワークにおけるコストの決定方法は、送信元と宛先ノード対の間のノードの少なくとも１つに対する複数の同時に可能性のある、あるいは有望な次のホップノードの決定ステップを含み、複数の同時に可能性のあるルート、あるいは経路を含むメッシュ状の経路が送信元と宛先ノードの間に規定される。このメッシュ状の構造は代表的に分散手法において決定され、コスト最適化プロセスから結果が得られる。コストの最適化は、例えば無線メディアに起因する確率的な変動を好ましくは考慮すべきである。
2007515906.tif 000002
【特許請求の範囲】
【請求項１】
マルチホップ通信ネットワークにおけるコスト決定方法であって、
ネットワークの送信元ノードから宛先ノードへの複数のノードの少なくとも１つに対し、同時に可能性のある複数の次ホップノードを決定するステップであって、前記同時に可能性のある複数のノードが共に所定のコスト関数を最適化し、及び
前記複数のノードの少なくとも１つについての最適コストを、前記所定のコスト関数の前記最適化された値に等しくなるように決定するステップ、
とを有することを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、前記複数のノードの少なくとも１つについての可能な次ホップノードの各々の個別コストに少なくとも部分的に基づいて、前記所定のコスト関数を最適にすることを特徴とする方法。
【請求項３】
請求項１又は２に記載の方法であって、前記複数のノードの少なくとも１つに起因するコストファクタに少なくとも部分的に基づいて、前記所定のコスト関数を最適にすることを特徴とする方法。
【請求項４】
請求項１から３のいずれかに記載の方法であって、前記送信元ノードから前記宛先ノードへの同時に可能性のあるルートのメッシュが提供されるまで、同時に可能性のある複数の次ホップノード及び関連する最適コストをノードごとに決定することを特徴とする方法。
【請求項５】
請求項１から４のいずれかに記載の方法であって、所定のコスト関数を共に最適化する前記同時に可能性のある複数の次ホップノードに加え、リンクパラメータを決定することを特徴とする方法。
【請求項６】
請求項１に記載の方法であって、
2007515906.tif 000020
による所定のコスト関数ｆＩの最適化に基づき、ノードｉに対する前記同時に可能性のある複数の次ホップノードを決定することを特徴とし、
上式でＳ”はノードｉの全ての可能な次ホップノードを表し、Ｓ”ｊはＳ”の前記ノードの全ての可能な組み合わせを表し、ＣｏｓｔＳ"ｊ（ｋ）は１つの特定の集合Ｓ”ｊのノードＳ”ｊ（ｋ）の個別のコストであり、△Ｃｏｓｔｉ、Ｓ"ｊ（ｋ）はノードｉからノードＳ”ｊ（ｋ）へ至るコストであり、Ｃｏｓｔｉ（ｏｐｔ）はノードｉの最適コストであり、Ｓ”ｊ（ｏｐｔ）は同時に可能性のある次ホップノードの前記集合である、方法。
【請求項７】
請求項６に記載の方法であって、
2007515906.tif 000021
による所定のコスト関数の最適化に基づきノードｉに対する前記同時に可能性のある複数の次ホップノードを決定することを特徴とし、
上式でｏは選択と設計目標に依存する任意の算術演算であり、Ｃｏｎｓｔｉはノードｉが前記コストに含むことができる項である方法。
【請求項８】
請求項７に記載の方法であって、
2007515906.tif 000022
による所定のコスト関数の最適化に基づきノードｉに対する前記同時に可能性のある複数の次ホップノードを決定することを特徴とし、
上式でＰａｒはｎ次元リンクパラメータ空間であり、ｎ＝１、２、．．．、Ｃｏｓｔｉ、Ｓ"ｊ（Ｐａｒ）はノードｉから前記Ｓ”ｊのノードへデータを送信する前記リンクパラメータ空間Ｐａｒ及びノードＳ”ｊの前記集合の関数としての前記コストを表し、Ｐａｒ（ｏｐｔ）はデータ転送のためのリンクパラメータの前記最適集合である方法。
【請求項９】
請求項７又は８に記載の方法であって、前記ネットワークのトポロジーの接続性及び／又は動的プロパティーに依存して前記項Ｃｏｎｓｔｉを選択することを特徴とする方法。
【請求項１０】
請求項７から９のいずれかに記載の方法であって、確率論的変数に依存して前記項Ｃｏｎｓｔｉを選択することを特徴とする、方法。
【請求項１１】
請求項７から１０のいずれかに記載の方法であって、干渉、ノードｉのバッテリー状態及び前記ノードｉの待ち行列状況の少なくとも１つに依存して前記項Ｃｏｎｓｔｉを選択することを特徴とする方法。
【請求項１２】
請求項１から１１のいずれかに記載の方法であって、ノードに関する前記コストを、遅延、干渉、ホップ数及び経路損失の少なくとも１つと関連させることを特徴とする方法。
【請求項１３】
通信ネットワークにおけるルーティングプロトコルのコスト最適化方法であって、所定のコスト関数を最適化し、それによって、送信元ノードから宛先ノードへの複数のノードの少なくとも１つに対する最適コスト及び同時に可能性のある複数の次ホップノードが決定されることを特徴とする方法。
【請求項１４】
マルチホップ通信ネットワークにおけるコスト決定システムであって、
前記ネットワークの送信元ノードから宛先ノードへの複数のノードの少なくとも１つに対して、同時に可能性のある複数の次ホップノードを決定する手段であって、前記ノードが共に所定のコスト関数を最適化し、及び
前記複数のノードの少なくとも１つについての最適コストを、前記所定のコスト関数の前記最適化された値に等しくなるように決定する手段、
とを有することを特徴とするシステム。
【請求項１５】
請求項１４に記載のシステムであって、前記決定手段が前記複数のノードの少なくとも１つについて可能な次ホップノードの各々の個別コストに少なくとも部分的に基づいて、前記所定のコスト関数を最適にするように適合されることを特徴とする、システム。
【請求項１６】
請求項１４及び１５に記載のシステムであって、前記送信元ノードから前記宛先ノードへの同時に可能性のあるルートのメッシュが提供されるまで、同時に可能性のある複数の次ホップノード及び関連する最適コストをノードごとに決定するように適合された手段を有することを特徴とするシステム。
【請求項１７】
請求項１４から１６のいずれかに記載のシステムであって、所定のコスト関数を共に最適化する前記同時に可能性のある複数の次ホップノードに加え、リンクパラメータを決定するように適合された手段を有することを特徴とするシステム。
【請求項１８】
請求項１４から１７のいずれかに記載のシステムであって、前記決定手段が、
2007515906.tif 000023
による所定のコスト関数ｆＩを最適化するように適合され
上式でＳ”はノードｉに対する全ての可能な次ホップノードを表し、Ｓ”ｊはＳ”の前記ノードの全ての可能な組み合わせを表し、ＣｏｓｔＳ"ｊ（ｋ）は１つの特定の集合Ｓ”ｊのノードＳ”ｊ（ｋ）の個別のコストであり、△Ｃｏｓｔｉ、Ｓ"ｊ（ｋ）はノードｉからノードＳ”ｊ（ｋ）へ至るコストであり、Ｃｏｓｔｉ（ｏｐｔ）はノードｉの最適コストであり、Ｓ”ｊ（ｏｐｔ）は同時に可能性のある次ホップノードの前記集合であるシステム。
【請求項１９】
マルチホップ通信ネットワークにおけるノードであって、
前記ノードに対し、同時に可能性のある複数の次ホップノードを決定する手段であって、前記同時に可能性のある次ホップノードが共に所定のコスト関数を最適化し、及び
前記ノードの最適コストを、前記所定のコスト関数の前記最適化された値に等しくするように決定する手段、
とを有することを特徴とするノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は全体としてマルチホップ通信ネットワークに関し、特にそのようなネットワークにおけるコスト決定方法に関する。
【背景技術】
【０００２】
ルーティングが無線通信ネットワークにおいて適用される場合、そのようなネットワークはしばしばマルチホップネットワークと表記される。マルチホップネットワークにおいて、互いに直接通信できない複数のノード又はステーションは、それらノード又はステーションのメッセージを送信元ノードから宛先ノードへ転送することが可能な、中間に位置する複数のノードの助けを借りることができる。伝統的には、マルチホップネットワークは、ノードの大半が移動体で、中心となってネットワークの調整を行なうインフラストラクチャが存在しない所謂アドホックネットワークを連想させる。しかし、ノードが固定されている場合及び／又は中心的な調整インフラストラクチャが存在する場合にも、マルチホップネットワークの考え方は適用することができる。そのようなシナリオの１つは、田園地域でのインターネットアクセスを対象とし、家屋の屋根上や電柱などに取り付けられた固定ノードを使用する。
【０００３】
所謂ベルマン・フォード（Ｂｅｌｌｍａｎ−Ｆｏｒｄ）及びその他の従来ルーティング技術は、通信ネットワークにおいて送信元ノードから宛先ノードへのマルチホップツリーあるいはルートを構築し、規定する。これはルーティングコスト情報をネットワーク経由により伝達し、コスト情報に基づいてルーティングテーブルを形成することにより行われる。このコスト情報は例えば、メッセージ遅延、累積電力消費、あるいはホップ数を含むことができる。システム内では、各ノードあるいはステーションは自身のルーティングテーブルを使用して独立した決定を行う。ベルマン・フォードに基づくルーティングは、結果として各送信元−宛先ノード対間に１つのルートをもたらす。しかしながら可動性によりトポロジーに変化があると、この１つのルートは時間の経過と共に異なるノードを通ることになる。
【０００４】
移動するノードの他にも、トポロジーが時間の経過と共に変化する理由が幾つか存在する。例えばトポロジーの変化は、電波を反射する移動物体や、通信メディアの変化に起因する変動など、ノードの移動がなくても生じることがある。これらのトポロジーの変化には、例えばチャネル変動、トラフィックパターンの変化、伝送パターンの変化及びリソース割り当ての変化が含まれる。
【０００５】
システム内の変化あるいは変動は、最適なルーティングがシステムのその時の状態に基づいて変わりうることを示す。換言すれば、時間経過に伴うシステムプロパティー又は特性の変動は、他の時間及び他の状態よりもうまく行なうことを可能にする機会を与えうる。変化するシステムプロパティーとしては、例えば経路品質、雑音、干渉干渉及びメッセージトラフィック負荷が含まれうる。ベルマン・フォードに基づくような従来ルーティング技術は、システム内のステーションあるいはノードがそれぞれ、関連する情報を格納しないので、このようなタイミングの良い機会を認識しない。
【０００６】
それとは対照的に、所謂オポチューンルーティング技術(opportune routing techniques)は、ネットワークの変動が提供するチャンスを活用する。特に無線ルーティングに関して述べれば、システム内のリンク品質が時間の経過と共に（例えばレイリーフェーディングにより）急速に変化すると、全体的なシステム性能は劣化する。しかしながらオポチューンルーティングは、変動がもたらすチャンスあるいはそのピークを使用することで、性能の低下を部分的に相殺する。オポチューンルーティングが使用された場合、各送信元−宛先ノード対についての決まったルートは存在しない。その代わり、データパケットは送信元ノードから宛先ノードに至る、幾らかランダムなルートに従う。従って、ベルマン・フォードのルーティングが使用される場合には、連続するパケットは同一ルートを経て送信されるが、オポチューンルーティングが使用される場合には、連続するパケットは全体的には同じ方向であるが、異なる経路上をルーティングされうる。しかしながら以下で理解されるように、オポチューンルーティングプロトコルもまた、ベルマン・フォードのような基礎的なルート／コスト決定プロトコルに基づいている。
【０００７】
送信元−宛先ノード対が互いに通信できるためには２つの機能が実装されねばならない、即ちルート決定（ルート維持を含む）機能及びパケット転送機能である。
【０００８】
第１に、ルート／コスト決定ステップにおいて、各送信元−宛先ノード対について、データパケットを送信するルートが決定されねばならない（各ノードについて、少なくとも次のホップが決定されることが必要である）。例外の１つはフラッディングで、ルートに関する知識を必要としない。決定されたルートはソースルーティングを除く全ての場合において関係するノードに知らされる必要がある。
【０００９】
第２に、パケット転送ステップにおいて、あるノードで受信されたパケットは、ルート決定ステップで決定されるルートに沿って次ノードに転送される必要がある。
【００１０】
［ルート／コストの決定］
ルートは従来、幾つかの最短経路条件基準に基づいて決定され、この基準は送信元と宛先ノード対の各々について、あるコストに関して単一の最短経路あるいはルートを与える。そのような方法の全体としての目標は一般的に以下のように述べられる：
リンクにより接続されるノードのネットワークが与えられ、各リンクが付随するコストを持つ場合に、２ノード間の経路コストを、経路に含まれるリンクのコストの合計として規定する。各ノード対に対して、最小コストの経路を見つける。
【００１１】
ベルマン・フォードアルゴリズムは有線ネットワーク（例えばインターネット）において中心的役割を果たしたが、また無線マルチホップシステムにおいても重要な機能を有している。そのアルゴリズムは分散され、かつ調整されないやり方での最短経路決定をもたらし、隣接ノード間で単に情報を交換するだけで有限時間内に収束することを保証する。「最短経路」に相当する用語として、経路がある特定のコスト測定基準(metric)に関して最小の経路であることを強調する、「最小コスト経路／ルート」を使用することができる。
【００１２】
ベルマン・フォードは最短経路アルゴリズムの良い例であるので、図１Ａを参照して簡明に記述する。しかし幾つかの定義がまず有益である。
【００１３】
Ｓはネットワークの全てのノードの集合であるとする。ｄは宛先ノードを表し、決定アルゴリズムはこの宛先ノードへのルートを決定する。ノードｉは対象対象ノード、即ちノードｄへの到達方法の決定を試みるノードである。次にＳ’ はノードｉが通信できる全てのノード、即ち所謂隣接ノードの集合を規定するものとする。集合Ｓ’内のノードは１からＪの範囲を取るｊにより指標付けされる。次いでＳ” はノードｉから見た最短経路をもたらす、集合Ｓ’ からのノードを含むささやかな集合(trivial set)である。最短経路はホップにより計算されるとの仮定の下に、１つのノードがＳ”に属するように指定される。最短経路はＬ１を経てＳ”のノードに至る。
【００１４】
宛先ノードｄへのパケットの最小経路あるいはルートの次ホップノードＳ”及び、宛先ノードに到達するコスト(即ちノードｉのコスト、Ｃｏｓｔｉｄ)を決定するために、アルゴリズムあるいは方法はＳ’内の複数のノードに到達するためのコストＣｏｓｔｉｊ及びＳ’内の各ノードからさらに宛先ノードｄへのコストＣｏｓｔｊｄを考慮しなければならない。
【００１５】
基本的ベルマン・フォードアルゴリズムは以下のように記述することができる：
最初に、
Ｃｏｓｔｉｄ＝∞及びＣｏｓｔｄｄ＝０
次いでコストを、
2007515906.tif 000003
により計算する。
【００１６】
これは次の２つの重要な出力をもたらす。
⇒Ｃｏｓｔｉｄ及びＳ”
従って分かることはパケットの転送先及びパケット転送コストであり、この情報は周囲のノードに分配されなければならない。
【００１７】
言葉で表現するアルゴリズム：宛先ノードｄは、宛先ノードｄへのコストが当初は無限大である全ての近隣ノードに（例えば０の）初期コストをブロードキャストすることにより最短経路の計算を開始する。次いで各ノードはそれぞれのコストを計算し、結果を隣接ノードに分配する。さらに多くのコスト情報が受信されると、新しい、さらに低い値のコストが計算され、分配される。ある有限時間が経過した後、全てのノードは達成可能な最低コストを手に入れている。同じコストの複数の経路が存在する場合、その1つが例えばランダムに選択される。
【００１８】
データが後にノードで受信されると、データは宛先アドレスに従い最低コスト経路を経て転送される。ここで重要な点は、どの時点においても、各宛先に対して最大で1つの次ホップノードが存在することである。
【００１９】
可能なコスト測定基準の例は：ホップ数、遅延、干渉干渉、電力消費、リンク容量などである。測定基準は加算される必要はなく、他の演算を使用しても良いことに注意されたい。さらに最小演算を最大演算に変えることができる。これら２つの点を含む1つの例は、最も信頼できるルートを、
2007515906.tif 000004
のように決定することである。
【００２０】
［パケット転送］
ベルマン・フォードアルゴリズムに基づく従前のパケット転送は、次ホップの選択選択肢が１つしかないという意味で、平凡なものである。
【００２１】
シスコのＩＧＰＲ[1]（特許文献１）、ランダム転送ルーティング[2]（特許文献２）、オポチューンルーティング[3,4]（特許文献３，４）、選択ダイバシティ転送[5]（非特許文献１）及びエニーキャスト[6]（非特許文献２）のような他の転送プロトコルは、ノードが受信パケットを幾つかの選択可能なノードの1つに送信することを許す。それ故転送プロセスは有望なノードの集合の中でなされる重大な選択を含む。ここでこれらの方式を転送決定に基づくルーティング、ＦＤＢＲと表す。これは最も適応的な形式のルーティングで、それぞれの転送時点で適応的な決定を行う。
【００２２】
ＩＧＰＲ[1]において、ノードはパケットを、ベルマン・フォードアルゴリズムによって決定される最小コストの最大ｖ倍のコストを有する任意のノードに転送する。
【００２３】
ランダム転送ルーティング[2]は、パケットがベルマン・フォードのコストあるいは位置のいずれかに基づいて、転送方向にあるランダムなノードに送信されることを意味する。
【００２４】
オポチューンルーティング  [3,4]は、ベルマン・フォードアルゴリズムを活用して、全体として正しい転送方向の観念(notion)を取得し、転送の選択に、例えばリンク品質及びノードの可用性に関する地域的かつ現行の知見を加える。
【００２５】
選択ダイバシティ転送（ＳＤＦ）[5]はルーティングの決定を、パケットが複数の中継ノード候補にマルチキャストされた後まで持ち越す。応答と通報されたノードの状態に基づいて、送信ステーションは成功裏に前のパケット送信を受信した候補ステーションあるいはノードから1つを選択し、通報する。次ホップノード決定アルゴリズムはＳＤＦ機構とは関係がない(orthogonal)が、例えばベルマン・フォードアルゴリズムに基づくことができる。
【００２６】
エニーキャスト[6]はデータ送信の前に試験送信を行い、それ故基本的ＳＤＦにほぼ同じの操作が体験される。さらにエニーキャストはＳＤＦの変形物に類似する。
【００２７】
この、幾らか複数経路指向のルーティング方式と、古典的な複数経路ルーティングの間に明確な相違があることに注意されたい。後者の場合、複数かつ平行なルートが送信元−宛先ノード対に対して規定され、転送の選択は送信元だけで行われる。即ち、分離複数経路ルーティングである。パケットが複数経路の1つに導かれると、その場合パケットはその選択されたルートに従う。そのため、転送の決定は古典的ベルマン・フォードの場合と同様に重大なものではない。
【００２８】
ルート決定及びパケット転送に加えて、任意選択の機能は、ネットワークに適切な接続性を提供することを目的としたトポロジー制御を組み込む。これは性能を高め、リソースを節約する。トポロジー制御は代表的に電力制御及びリンクアダプテーションを含む。
【００２９】
【特許文献１】ＷＯ９６／１９８８７号公報
【特許文献２】ＷＯ９８／５６１４０号公報
【特許文献３】ＵＳ２００２／００５１４２５号公報
【特許文献４】ＷＯ２００４／０９１１５５号公報
【非特許文献１】シー．エル．ヘドリック  ラットガース（Ｃ．Ｌ．Ｈｅｄｒｉｃｋ  Ｒｕｔｇｅｒｓ）「シスコ−ＩＧＰＲ入門」(“Cisco-An introduction to IGPR”)1991年8月22日、http://www.cisco.com/warp/public/103/5.html
【非特許文献２】アール．ネルソン、エル．クラインロック(R.Nelson、L.Kleinrock)「捕捉によるスロティッドALOHAマルチホップパケット無線ネットワークの空間容量」(“The spatial capacity of a slotted ALOHA multihop packet radio network with capture”)IEEE通信技術論文誌(Transactions on Communications)32巻、6号、684-694ページ、1984年
【非特許文献３】エス.ジェイン、ワイ.エル、エス.アール.ダス(S.Jain、Y.Lv、S.R.Das)「無線アドホックネットワークのリンク層における経路ダイバシティの活用」(“Exploiting Path Diversity in the Link Layer in Wireless AdHoc Networks”)技術報告、WINGS研究所、2003年7月
【００３０】
仔細に分析すれば所謂転送決定ベースのルーティング（ＦＤＢＲ）プロトコルに伴う問題の１つは、このプロトコルが、例えばベルマン・フォードのような、プロトコルの転送決定指向動作を反映しないルート／コスト決定機構に依存している点にあることが分かる。加えて、単純な(trivial)転送決定を用いる他の無線ルーティング方式もまた、ベルマン・フォードアルゴリズムより優れた代替方式を使用することができるであろう。
【００３１】
従って、本発明の目的は改良されたルート決定機構を提供することである。
【００３２】
本発明の別の目的は、転送決定指向動作を反映した、コストあるいはルート決定機構を提供することである。
【００３３】
本発明の更なる目的は、同報メディア（無線は本質的に同報メディアである）及び、無線が本質的にもたらす高速で変化するチャネル品質に合わせたコストあるいはルート決定機構を提供することである。
【００３４】
本発明の別の目的は、転送決定に基づくルーティングをサポートするようになされたコストあるいはルート決定機構を提供することである。
【００３５】
さらに本発明の別の目的は、ノードの各送信元−宛先対への接続方法を明らかにするのに向いたコストあるいはルート決定機構を提供することである。
【００３６】
本発明の別の目的は転送決定指向トポロジー制御の統合に向くコストあるいはルート決定方法を提供することである。
【００３７】
最後に、本発明の追加の目的はリンクの変更／障害に強く反応しないコストあるいはルート決定方法を提供することである。
【００３８】
特に、本発明は各送信元と宛先ノード対の間のノードの少なくとも１つに対し、複数の同時に可能性のある、あるいは有望な次ホップノードを決定するコスト決定方法を提供し、それによって送信元と宛先ノードの間の複数の同時に可能性のあるルートあるいは経路を含むメッシュ状の経路が規定される。通常、このメッシュ状の構造は分散的な方式で決定され、コスト最適化プロセスにより得られる。コスト最適化は例えば無線メディアに起因する確率論的変動を考慮することが好ましい。特に、ＦＤＢＲ方式に考慮が払われることができる。
【００３９】
本発明は、送信元と宛先ノードの間の少なくとも1つのノードに対して所定のコスト関数を共に最適化する同時に可能性のある複数の次ホップノードを決定するコスト最適化方法を提供し、それによって考慮するノードの最適コストを決定する。
【００４０】
本発明は上記の方法を可能にするシステム及びノードを提供する。
これら及びその他の目的は添付の特許請求範囲により達成される。
【００４１】
本発明による方法は以下の利点をもたらす：
−  ノード障害、変動するノード可用性及びノードの移動性の下におけるロバスト性の提供。
−  フェーディング及び干渉干渉により変動するチャネル品質の下におけるロバスト性の提供。
−  当然な要素(natural part)としての多様な態様の統合。
−  冗長経路の提供及び最も有利な接続性の存在する所へのトラフィックの好ましい転送の保証。
−  複数経路ルーティングのサポート。
【００４２】
本発明並びに、本発明の他の目的及び利点は、添付する図面と共に行われる以下の記述を参照することにより最も良く理解されるであろう。
【発明を実施するための最良の形態】
【００４３】
本発明は以下に無線マルチホップ通信ネットワークに関して記述される。しかしながら本発明は従来の有線ネットワークに等しく適用可能であると考えられる。
【００４４】
前述の通り、本発明による方法の実施形態は、基本的に、通信ネットワークにおける送信元と宛先ノードの間の少なくとも1つのノードに対して複数の同時に可能性のある、あるいは有望な次ホップノードを決定する。これはコスト最適化手順により好ましくは行われる。そうすることにより、メッシュ状の構造の同時に可能性のあるルートが送信元と宛先ノードの間で決定される。
【００４５】
さらに方法の考察が可能となる前に、図１Ｂを参照して幾つかの定義が提示される。
上述したベルマン・フォードアルゴリズムと同様に、Ｓはネットワークにおける全ノードの集合を規定する。サブ集合Ｓ’は、送信範囲及び受信範囲を結合した範囲内に含まれる全ノードの集合、あるいはノードｉの所謂隣接ノードの集合を規定する。例えば最大送信電力かつ干渉干渉のない場合のように、送信パラメータが最適化される状態において、データを規定された閾値より低い電力により送信できる能力として規定される接続性を双方向接続性とも呼ぶ。ノードｉはコストが決定されるノードであり、時に対象端末あるいはステーションとも呼ばれる。即ち、集合Ｓ’はノードｉの隣接ノードを含む。
【００４６】
集合Ｓ”はＳの累乗集合(power set)であり、即ちＳ”はＳ’のノードの全ての可能な組み合わせを含む。しかしながら空集合は考慮されない。種々の組み合わせはｊにより指標付けされ、Ｓ’がＮノードを含む場合、ｊ∈［１、２、３、．．．、２Ｎ−１］である。各集合Ｓｊ’はｋにより指標付けされる1又は複数のノードを含む。即ち、Ｓｊ（ｋ）’である。
【００４７】
図１ＢはＳ、Ｓ’及び、Ｓ”内の全Ｓ”ｊの１つを示す。Ｓ’は５つのノードを含むので、Ｓ”には３１の異なる集合が存在する。提示されるＳｊ”はたまたま最適集合Ｓ”（ｏｐｔ）であり、Ｓｊ（１）”、．．．、Ｓｊ（３）”と指標付けされる３つのノードを有する。Ｓ”（ｏｐｔ）は最適コストＣｏｓｔｉを同時に、あるいは共に提供するノードの集合である。
【００４８】
図２Ａは複数のノードを含むネットワークを示し、可能性のあるリンクがノード間の破線により示される。また、送信元ノードｓ、宛先ノードｄ、及び対象ノードである中間ノードｉが示される。
【００４９】
複数の同時に可能性のある次ホップノード、あるいは有望な次ホップノードの集合を決定するために、ノードｉのコスト関数ｆ１を好ましくは
2007515906.tif 000005
により最適化することが望ましく、上式でＯｐｔｉｍｉｚｅは選択と設計目標に依存する任意の最適化操作を表す。項ＣｏｓｔＳ"ｊ（ｋ）は1つの特定の集合Ｓ”ｊのノードＳ”ｊ（ｋ）の個別のコストを表し、△Ｃｏｓｔｉ、Ｓ"ｊ（ｋ）はノードｉからノードＳ”ｊ（ｋ）へ至るコストを表す。さらに関数はＳ”ｊの各ノードＳ”ｊ（ｋ）により与えられるコストを結合する。
【００５０】
そうすることにおいて、関数はまた随意にＭＡＣプロトコルにより使用される任意の優先規則を呼び出すことができる。優先規則は例えば、データがＳ”ｊの複数のノードにより正しく受信されれば、最小コストを持つノードが常に選択されるものでありうる。
【００５１】
そのような最適化を行い、トポロジーが考慮される随意の実施例の手法は以下の表現に従い、
2007515906.tif 000006
上式で、ｏの記号は選択と設計目標に依存する任意の算術演算を表す。コストの項Ｃｏｎｓｔｉはノードｉが総コストに含むことができる定数である。その目的はトポロジーの接続性と動的特性を多少管理することでありうる。定数はまたノードｉにおける干渉あるいは待ち行列の状況を反映することができる。
【００５２】
一般に無線通信の品質はいささか予想しがたいので、確率論的なモデリングが適している。従ってコストの決定はある程度最適化期待値を扱う。これはより下位層の性能最適化の慣例的扱い方に沿うので、実用的な手法である。
【００５３】
全ノードが最小あるいは最適コストを達成するまで、上記の方法がノード毎に繰り返される。これは全てのノードが複数の有望な次ホップノードを有することを意味するのではなく、あるノードはただ1つの次ホップノードのみを持つこともある。しかし前述のように、少なくとも1つのノードは自体に関連する複数の有望な次ホップノードを持つ。その際複数の同時に可能性のあるルートあるいは経路が図２Ｂに示すように提供される。
【００５４】
本発明による方法の上記の実施形態に対する随意の修正により、適切なリンクパラメータが決定される。これは次式により容易化される：
2007515906.tif 000007
上式で項Ｐａｒは連続及び離散両方のパラメータを含むｎ次元リンクパラメータ空間（ｎ＝１、２．．．）である。Ｃｏｓｔｉ、Ｓ"ｊ（Ｐａｒ）の項は、ノードｉから、集合Ｓ”ｊの任意もしくは所定数のノードへデータパケットを送信するコスト（あるいは労力）を表す。所定数は実際のシステムでは代表的には1ノードに設定される。さらにＣｏｓｔｉ、Ｓ"ｊ（Ｐａｒ）の項は、リンクパラメータ空間Ｐａｒ及び対象ノードの集合、即ちＳ”ｊの関数である。
【００５５】
「リンクパラメータ」は、変調、符号化及び拡散方式、送信電力、アンテナの重み及び周波数チャネルパラメータのような呼パラメータをまとめて表す用語である。それ故リンクパラメータはデータリンク層のＤＬＣ（Ｄａｔａ  Ｌｉｎｋ  Ｃｏｎｔｒｏｌ、データリンク制御）パラメータ及び基礎となる物理ＰＨＹ層パラメータを含む。ＤＬＣパラメータはＬＬＣ（Ｌｏｇｉｃａｌ  Ｌｉｎｋ  Ｃｏｎｔｒｏｌ、論理リンク制御）パラメータ及びＭＡＣ（Ｍｅｄｉｕｍ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ、メディアアクセス制御）パラメータの両方を含み、従ってリンクパラメータはＬＬＣ、ＭＡＣ及びＰＨＹパラメータから選択されることができる。
【００５６】
以上に説明した修正により、本発明による方法の実施形態はＣｏｓｔｉ、Ｓ”（ｏｐｔ）、Ｐａｒ（ｏｐｔ）、即ちノードｉから宛先ノードを見たコスト、データが転送されることができる、同時に可能性のある、あるいは有望な次ホップノードの集合、及びデータ転送の際に使用する最適リンクパラメータを出力する。
【００５７】
本発明による方法の実施形態がどのように動作するかについての例示を図３Ａに示す。この図で、ノードｉのコストはあるリンクパラメータＰａｒの関数であるとする。また、ノードｉからはそれぞれ付随するコストＣｏｓｔＡ及びＣｏｓｔＢを持つ２つのノードが見えるものとする。本発明による方法の実施形態により、これら２つのノードから３つの累乗集合、即ちＳ”１、Ｓ”２及びＳ”３が構築されうる。３つの集合の中で、ここではＳ”３が最適であり、即ちＳ”（ｏｐｔ）＝Ｓ”３である。換言すれば、Ｓ”３はノードｉについてのコストを最小化する。その際２つの同時に可能性のある、あるいは有望な次ホップノードがそのノードに対して決定される。
【００５８】
本発明による方法に関して提案される実施形態の別の例示的適用例は、転送手順に利用される場合、図３Ｂを参照して与えられる。
【００５９】
この例では、コスト測定基準は予期される最小遅延であるように経験的に選択される。これにより、転送の進行が最大になるので、実用的な測定基準であろう。
【００６０】
ノードｉの遅延は再送信回数及び送信確率ＰＴＸ（即ちスロット内の送信確率）によって決定される。ノードｉによる（再）送信回数￣ｔｉは、ノードｉとＳ”ｏｐｔのノードとの間のチャネル特性及び変調、自動再送要求（ＡＲＱ）及び符号化方式に依存する。
【００６１】
これを説明するために、選択的反復ＡＲＱ及び決定論的経路損失Ｌを考慮する。検出器特性はノードＳ”ｊ（ｋ）による受信の無条件確率βｋによって表される。βｋ＝ｆ（ＰＴＸ，modulation，ＦＥＣ，Ｎ０，Ｌｋ）であり、多くのパラメータの関数である。
【００６２】
2007515906.tif 000008
【００６３】
2007515906.tif 000009
上式で
2007515906.tif 000010
であり、
ノードｉの幾つかのスロットの遅延期待値は以下のようになる。
2007515906.tif 000011
【００６４】
追加の、実用的な規則では、Ｓ”ｏｐｔの幾つかのノードがデータを同時に受信するとすれば、最小コストのノードがまずデータ転送に選択される。そのような選択はＳＤＦ[5]において実施する場合に簡単であるが、例えばキュー長、ランダムあるいはラウンドロビンに基づく任意のその他の選択規則も可能である。
【００６５】
ここで選択の目的のため、Ｓ”ｏｐｔのノードは指標付けされ、コストＣｋは以下の特性を持つ。
Ｃ１≦Ｃ２．．．≦ＣＫ
【００６６】
上式でＫは集合の最後のノードの指標である。これらのコストは条件付受信確率γｋ、即ちいずれかのノードがデータを受信したことを条件とされる確立により重み付けされるべきである。即ち、
2007515906.tif 000012
【００６７】
次いで結合コスト関数ｆ１は以下の通りである。
2007515906.tif 000013
【００６８】
ここでの具体的な重み付けは、最小コストノードがデータを受信すればそのノードが選択され、受信しなければ次の最小コストノードが順次選択される、などの選択規則を反映すると想定されている。
【００６９】
解析的数学表現はさらに込み入るであろうが、同様の手法はフェーディングチャネルに採用されることができる。
【００７０】
解析的表現を使用するよりむしろ、シミュレーション手法を使用することができる。２つの場合が想定され、１つは事前にシミュレーションされた場合のルックアップテーブルを使用すること、もう１つは現行パラメータを入力としたリアルタイムシミュレーションを使用することである。後者はおそらくほとんど現実的ではないが、なお選択肢ではある。
【００７１】
［速度依存メッシュ測定基準］
種々の速度が通信に使用されることを仮定すれば、さらに別のメッシュ測定基準が想定されうる。経路損失はノード間で異なり、異なるノードは干渉により異なる影響を受け、送信ノードは種々の量の送信電力を用いるので、受信時の信号対干渉比もまた種々のノード大きく異なりうる。通信の基本的な性質は、ノードがパケットを受信することができる最大速度が信号対干渉比（あるいは、干渉がなければ、単に信号対雑音比）の関数であるということである。信号対干渉比が大きければ、それだけ速いデータ速度がサポートされうる。従ってノードが送信（受信にも）に種々の速度を使用することができるとの想定をベースに、メッシュ測定基準を考えることは関心の持てることである。種々の速度はパケットを種々の転送誤り訂正符号、種々の拡散率(spreading factor)、及び種々の変調アルファベット（例えば、４ＱＡＭと６４ＱＡＭの信号配置を比較されたい）による符号化により実現可能である。
【００７２】
次いで速度依存測定基準が形式化される。考慮されるシナリオは、送信はプローブを用いた送信の指示後に生じることとして、平均エンドツーエンド時間リソース利用を最小化することである。この状況はＭＤＦ[7]（非特許文献３）のようなマルチホップ転送方式において生じ、この方式ではまず複数のノードにショートプローブを送信し、各ユーザに使用可能な速度を示す複数の応答を受信し、その後選択されたユーザに送信されるパケットを選択する。ここで、フロー選択の態様、即ちＭＤＦの一部は無視される（送信はプローブにより指示されており、その他のノードは経験した干渉に従いその速度選択に適応しているので、送信を後段に遅らせる意味はない）。
【００７３】
次いで全近隣ノードの上位集合の集合であるＫノードの集合を考慮するノードｉについて考察する。その場合ノードは次のように順序付けされる（かつ数えられる）：
Ｃ’１≦Ｃ’２．．．≦Ｃ’Ｋ
上式でＣ’ｋ＝△Ｃｉｋ＋Ｃｋ、ｋ∈｛０、．．．、Ｋ｝であり、△Ｃｉｋはノードｉからノードｋへの平均コストであり、Ｃｋはノードｋにおける考慮される宛先へのコストである（実際これは全宛先に対してなされるが、ここでは１つの宛先のみが調べられる）。
【００７４】
次に速度依存性が以下の設定により導入される。
2007515906.tif 000014
上式でγｉｋはノードｉとノードｋの間の速度である。速度は種々の方法により決定される、あるいはこれまでの通信から評価されることができるが、より直接的には経路利得Ｇｉｋ、ノードｉによる使用が考えられる送信電力Ｐｉ（ＴＸ）、ノードｋにおける雑音及び干渉レベルの合計Ｗｋに関する知識から決定されることができる。例えばシャノン（Ｓｈａｎｎｏｎ）の制約が速度γｉｋ＝ｌｏｇ２（１＋ＧｉｋＰｉ（ＴＸ）／Ｗｋ）の決定に使用されることができる。
【００７５】
次いで結合されたメッシュコストｆ１は以下のように書くことができる。
2007515906.tif 000015
上式で条件付受信確率が使用され、即ち以下の通りである。
2007515906.tif 000016
【００７６】
次いでβｋはノードｋが受信に利用可能な無条件確率であり、その受信は上記のＭＤＦ[7]の試験プロセスにより試験される。ノードが受信に常に利用できない理由はノードが例えば送信モードあるいはスリープモードにあるため常に受信状態ではありえないからである。
【００７７】
時間リソース利用の最小化に関心があるので、機能ｆ１（ＣｏｓｔＳ'ｊ（ｋ）、△ＣｏｓｔｉＳ'ｊ（ｋ）│∀Ｓ” ｊ（ｋ）∈Ｓｊ”）は上位集合中可能な全ての集合に対して最小化される。
本発明による方法の実施形態の別の例示は以下に図４を参照して与えられる。
この非常に単純化された例では、各リンクは任意に設定される平均受信成功確率により特徴付けされる。
【００７８】
最初に、ある時刻Ｔ１において、２つのノード１及び２がコンタクトを確立し、ノード１がその初期コストＣ１をノード２に送信する。その結果、時刻Ｔ２において、ノード２のコストが以下により８に決定される。
2007515906.tif 000017
【００７９】
後の時刻Ｔ３において、第３のノード、ノード３がネットワークに加えられる。
時刻Ｔ４において、ノード３はノード１への接続が最低コスト、即ち６を提供することを以下の通り決定する。
2007515906.tif 000018
【００８０】
時刻Ｔ５において、ノード２はノード３の参加に気づき、そのコスト選択肢を評価する。ノード２がノード１及びノード３の両方にアタッチすると、以下により最低コストが６．６であると決定される。
2007515906.tif 000019
【００８１】
その際本発明による方法の実施形態によれば、以前に説明したベルマン・フォードの場合に得られるであろう単一のホップあるいは経路に代わって、２つの同時に可能性のある、あるいは有望な次ホップ、さもなくば同様に２つの同時に可能性のある経路、あるいはルートがノード２から提供される。
【００８２】
以前に示したように、ノードｉのコストの計算に使用されるコストは期待値であるが、ある確率密度関数（ＰＤＦ）によりモデル化される確率変数とも考えられる。入力がＰＤＦ値であれば、出力はＰＤＦ値であるのは理に適っている。しかしながら最適化は平均あるいは変化を演算しなければならない。
【００８３】
ノード集合の探索は非多項式（ＮＰ）完全問題であるので、これは開始するのが難しそうに見える。しかしながら（２Ｎ−１）の異なる集合はＮが小さければ問題ではない。マルチホップネットワークの黄金規則(golden rule)ではノードは約６つの隣接ノード、即ち予定される転送方向に凡そ３つの隣接ノードを有するはずである。これからコスト計算で考慮する凡そ７つの集合が得られる。
【００８４】
複雑さを削減する方法の第１の選択肢は、任意の（しかしおそらくはうまく推測される）集合Ｓ”ｊに対するＣｏｓｔｊより高いコストを持つ全てのノードを除外することである。これは、これらのノードは考慮したとしてもコストを改善しないであろうからである。
【００８５】
このことは図３Ａの上の２つの曲線を除く曲線を示す図５に例示される。ノードＡ及びＢによるコストはＣｏｓｔｉより低いが、第３のノードＣは、その開始コストがＣｏｓｔｉより高いので考慮されなくとも良いことが認められる。この方法は加算演算においてはコストが負とならないこと、また乗算演算ではコストは１を上回り増加することを仮定していることに注意されたい。
【００８６】
本発明による方法の複雑さを削減する随意の補足的方法は図６Ａ、図６Ｂ及び図７を参照して記述される。アルゴリズムの観点から、高いコストのノードを早く排除できるので、始めに最初の集合Ｓ”ｊにＳ’の最低コストのノードを考慮するのは理に適っている。
【００８７】
図６Ａに複数のノードを持つマルチホップネットワークが示され、それぞれのノードは付随する個別のコストを持つ。ノードｉが挿入され、図に示すように４つの隣接ノード１、２、３及び４を有する。
【００８８】
図７に本発明の複雑さを削減するアルゴリズムの実施形態のフローチャートが示される。この経験的アルゴリズムでは、隣接ノードへのコストは、最初のステップ（図示せず）においてＳ”の全てのノードに対してベルマン・フォードと同様の方法で計算される。最適コスト及び次ホップノードを選択するというよりむしろ、ノードはＳ２からＳ１０のステップにおいて計算されたコストによりソートされる。同じステップＳ２においてコストベクトルとノードベクトルが決定される。例えば図６Ａによれば、得られるコストベクトルとノードベクトルはそれぞれ｛Ｃｉ−４−ｄ、Ｃｉ−１−ｄ、Ｃｉ−３−ｄ、Ｃｉ−２−ｄ｝及び｛４、１、３、２｝であり、ここで例えばＣｉ−４−ｄはノードｉからノード４を経て宛先ノードｄへの経路の最適コストである。Ｃｉ−４−ｄはノードｉからノード４へのコストＣｉ−４及びノード４から宛先へのコストＣ４−ｄの関数である。
【００８９】
次いで調査される集合はＳ”１＝｛Ｃｉ−４−ｄ、｝、Ｓ”２＝｛Ｃｉ−４−ｄ、Ｃｉ−１−ｄ｝、Ｓ”３＝｛Ｃｉ−４−ｄ、Ｃｉ−１−ｄ、Ｃｉ−３−ｄ｝から、ノードｉの観点から以前に決定されたいずれのコストも超えない個別のコストを伴うノードを持つ最後の集合までである。
【００９０】
選別の複雑さは最大Ｏ（Ｎ２）であるが、分割攻略に基づくクイックソートのようなあるアルゴリズムは平均してＯ（Ｎｌｏｇ・（Ｎ））の複雑度を保証する。
コスト決定はＯ（Ｎ）の複雑度を持つが、使用不能なノードが排除されると、さらに低い平均複雑度を持つ。
【００９１】
アルゴリズムは全ての集合の組み合わせを調べるわけでなないので、経験的であることに注意されたい。しかしながらノードは最も有望な順序で配列される。
各ノードがそのそれぞれのコストと次ホップノードの集合を更新すると結果は図６Ｂのようになる。
【００９２】
図８に本発明によるマルチホップ通信ネットワークにおけるノード１０の実施形態の概要ブロック図が示される。ノード１０は無線トランシーバモジュール（ＲＸ／ＴＸモジュール）２０を含み、これは既知の様式の必要な受信及び送信機能を供給する。ノード１０はまた送信元と宛先ノードの間のルートを本発明により決定するように適応するルート決定手段３０を含む。代わってルート決定手段３０はコスト最適化手段３１、コスト決定手段３２及びルート最適化手段３３を含む。最後にノード１０はルート決定手段３０からの出力に基づくパケット転送手段４０を含む。
【００９３】
添付の特許請求の範囲により規定されるその範囲から逸脱することなく、種々の修正及び変更が本発明になされることができることは当業者により理解される。
【図面の簡単な説明】
【００９４】
【図１Ａ】マルチホップネットワークの概要図である。
【図１Ｂ】本発明によるマルチホップネットワークの実施形態の概要図である。
【図２Ａ】マルチホップネットワークの概要図である。
【図２Ｂ】本発明による方法の実施形態により決定されるルートを持つマルチホップネットワークの概要図である。
【図３Ａ】本発明による実施形態の例示図である。
【図３Ｂ】本発明による実施形態の別の例示図である。
【図４】本発明による方法の実施形態の進行を示す概要図である。
【図５】本発明による実施形態の別の例示図である。
【図６Ａ】本発明による単純化されたネットワークの実施例である。
【図６Ｂ】本発明による方法の実施形態が適用された後の図６Ａのネットワークを示す図である。
【図７】本発明による実施形態のフローダイアグラムである。
【図８】本発明によるシステムの実施形態のブロック図である。
【図１Ａ】
2007515906.tif 000024
【図１Ｂ】
2007515906.tif 000025
【図２Ａ】
2007515906.tif 000026
【図２Ｂ】
2007515906.tif 000027
【図３Ａ】
2007515906.tif 000028
【図３Ｂ】
2007515906.tif 000029
【図４】
2007515906.tif 000030
【図５】
2007515906.tif 000031
【図６Ａ】
2007515906.tif 000032
【図６Ｂ】
2007515906.tif 000033
【図７】
2007515906.tif 000034
【図８】
2007515906.tif 000035
【手続補正書】
【提出日】平成17年7月7日(2005.7.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
マルチホップ通信ネットワークにおけるコスト決定方法であって、
ネットワークの送信元ノードから宛先ノードへの複数のノードの少なくとも１つに対し、同時に可能性のある複数の次ホップノードを決定するステップであって、前記同時に可能性のある複数のノードが共に所定のコスト関数を最適化するとともに、前記同時に可能性のある複数の次ホップノードが前記複数のノードの少なくとも１つの隣接ノードの部分集合を形成し、及び
前記複数のノードの少なくとも１つについての最適コストを、前記所定のコスト関数の前記最適化された値に等しくなるように決定するステップ、
とを有することを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、前記複数のノードの少なくとも１つについての可能な次ホップノードの各々の個別コストに少なくとも部分的に基づいて、前記所定のコスト関数を最適にすることを特徴とする方法。
【請求項３】
請求項１又は２に記載の方法であって、前記複数のノードの少なくとも１つに起因するコストファクタに少なくとも部分的に基づいて、前記所定のコスト関数を最適にすることを特徴とする方法。
【請求項４】
請求項１から３のいずれかに記載の方法であって、前記送信元ノードから前記宛先ノードへの同時に可能性のあるルートのメッシュが提供されるまで、同時に可能性のある複数の次ホップノード及び関連する最適コストをノードごとに決定することを特徴とする方法。
【請求項５】
請求項１から４のいずれかに記載の方法であって、所定のコスト関数を共に最適化する前記同時に可能性のある複数の次ホップノードに加え、リンクパラメータを決定することを特徴とする方法。
【請求項６】
請求項１に記載の方法であって、
2007515906.tif 000036
による所定のコスト関数ｆＩの最適化に基づき、ノードｉに対する前記同時に可能性のある複数の次ホップノードを決定することを特徴とし、
上式でＳ”はノードｉの全ての可能な次ホップノードを表し、Ｓ”ｊはＳ”の前記ノードの全ての可能な組み合わせを表し、ＣｏｓｔＳ"ｊ（ｋ）は１つの特定の集合Ｓ”ｊのノードＳ”ｊ（ｋ）の個別のコストであり、△Ｃｏｓｔｉ、Ｓ"ｊ（ｋ）はノードｉからノードＳ”ｊ（ｋ）へ至るコストであり、Ｃｏｓｔｉ（ｏｐｔ）はノードｉの最適コストであり、Ｓ”ｊ（ｏｐｔ）は同時に可能性のある次ホップノードの前記集合である、方法。
【請求項７】
請求項６に記載の方法であって、
2007515906.tif 000037
による所定のコスト関数の最適化に基づきノードｉに対する前記同時に可能性のある複数の次ホップノードを決定することを特徴とし、
上式でｏは選択と設計目標に依存する任意の算術演算であり、Ｃｏｎｓｔｉはノードｉが前記コストに含むことができる項である方法。
【請求項８】
請求項７に記載の方法であって、
2007515906.tif 000038
による所定のコスト関数の最適化に基づきノードｉに対する前記同時に可能性のある複数の次ホップノードを決定することを特徴とし、
上式でＰａｒはｎ次元リンクパラメータ空間であり、ｎ＝１、２、．．．、Ｃｏｓｔｉ、Ｓ"ｊ（Ｐａｒ）はノードｉから前記Ｓ”ｊのノードへデータを送信する前記リンクパラメータ空間Ｐａｒ及びノードＳ”ｊの前記集合の関数としての前記コストを表し、Ｐａｒ（ｏｐｔ）はデータ転送のためのリンクパラメータの前記最適集合である方法。
【請求項９】
請求項７又は８に記載の方法であって、前記ネットワークのトポロジーの接続性及び／又は動的プロパティーに依存して前記項Ｃｏｎｓｔｉを選択することを特徴とする方法。
【請求項１０】
請求項７から９のいずれかに記載の方法であって、確率論的変数に依存して前記項Ｃｏｎｓｔｉを選択することを特徴とする、方法。
【請求項１１】
請求項７から１０のいずれかに記載の方法であって、干渉、ノードｉのバッテリー状態及び前記ノードｉの待ち行列状況の少なくとも１つに依存して前記項Ｃｏｎｓｔｉを選択することを特徴とする方法。
【請求項１２】
請求項１から１１のいずれかに記載の方法であって、ノードに関する前記コストを、遅延、干渉、ホップ数及び経路損失の少なくとも１つと関連させることを特徴とする方法。
【請求項１３】
通信ネットワークにおけるルーティングプロトコルのコスト最適化方法であって、所定のコスト関数を最適化し、それによって、送信元ノードから宛先ノードへの複数のノードの少なくとも１つに対する最適コスト及び同時に可能性のある複数の次ホップノードが決定されるとともに、前記同時に可能性のある複数の次ホップノードが前記複数のノードの少なくとも１つの隣接ノードの部分集合を形成することを特徴とする方法。
【請求項１４】
マルチホップ通信ネットワークにおけるコスト決定システムであって、
前記ネットワークの送信元ノードから宛先ノードへの複数のノードの少なくとも１つに対して、同時に可能性のある複数の次ホップノードを決定する手段であって、前記ノードが共に所定のコスト関数を最適化するとともに、前記同時に可能性のある複数の次ホップノードが前記複数のノードの少なくとも１つの隣接ノードの部分集合を形成し、及び
前記複数のノードの少なくとも１つについての最適コストを、前記所定のコスト関数の前記最適化された値に等しくなるように決定する手段、
とを有することを特徴とするシステム。
【請求項１５】
請求項１４に記載のシステムであって、前記決定手段が前記複数のノードの少なくとも１つについて可能な次ホップノードの各々の個別コストに少なくとも部分的に基づいて、前記所定のコスト関数を最適にするように適合されることを特徴とする、システム。
【請求項１６】
請求項１４及び１５に記載のシステムであって、前記送信元ノードから前記宛先ノードへの同時に可能性のあるルートのメッシュが提供されるまで、同時に可能性のある複数の次ホップノード及び関連する最適コストをノードごとに決定するように適合された手段を有することを特徴とするシステム。
【請求項１７】
請求項１４から１６のいずれかに記載のシステムであって、所定のコスト関数を共に最適化する前記同時に可能性のある複数の次ホップノードに加え、リンクパラメータを決定するように適合された手段を有することを特徴とするシステム。
【請求項１８】
請求項１４から１７のいずれかに記載のシステムであって、前記決定手段が、
2007515906.tif 000039
による所定のコスト関数ｆＩを最適化するように適合され
上式でＳ”はノードｉに対する全ての可能な次ホップノードを表し、Ｓ”ｊはＳ”の前記ノードの全ての可能な組み合わせを表し、ＣｏｓｔＳ"ｊ（ｋ）は１つの特定の集合Ｓ”ｊのノードＳ”ｊ（ｋ）の個別のコストであり、△Ｃｏｓｔｉ、Ｓ"ｊ（ｋ）はノードｉからノードＳ”ｊ（ｋ）へ至るコストであり、Ｃｏｓｔｉ（ｏｐｔ）はノードｉの最適コストであり、Ｓ”ｊ（ｏｐｔ）は同時に可能性のある次ホップノードの前記集合であるシステム。
【請求項１９】
マルチホップ通信ネットワークにおけるノードであって、
前記ノードに対し、同時に可能性のある複数の次ホップノードを決定する手段であって、前記同時に可能性のある次ホップノードが共に所定のコスト関数を最適化するとともに、前記同時に可能性のある複数の次ホップノードが前記複数のノードの少なくとも１つの隣接ノードの部分集合を形成し、及び
前記ノードの最適コストを、前記所定のコスト関数の前記最適化された値に等しくするように決定する手段、
とを有することを特徴とするノード。
【国際調査報告】
2007515906.tif 000040
2007515906.tif 000041
2007515906.tif 000042