(57)【要約】  無線メッシュネットワークで通信する方法、装置及びシステムは、最低のコストメトリックを有する発信元ノードと宛先ノードとの間のマルチホップパスを決定するために、Viterbiルーティングアルゴリズムを使用することを伴う。一例では、コストメトリックは、それぞれの潜在的なマルチホップパスのリンクで実現可能な伝送レートに反比例してもよい。無線通信を宛先ノードにルーティングする２つ以上の潜在的なマルチホップパスの次ホップのノードは、宛先ノードに通信することに関連する最低のコストメトリックを有するマルチホップパスに基づいて各ノードにより決定されてもよい。他の実施例及び変形例が詳細な説明で説明される。
2009520445.tif 000002
【特許請求の範囲】
【請求項１】
無線メッシュネットワークで通信する方法であって、
２つ以上の潜在的なマルチホップパスを通じて無線ノードと宛先との間で通信することに関連する最低のコストメトリックの合計を有する次ホップのノードを決定し、コストメトリックは、各潜在的なマルチホップパスでの各隣接無線ノード間のチャネル特性に基づき、
前記決定された次ホップのノードを特定するように、前記無線ノードでルーティングテーブルを更新することを有する方法。
【請求項２】
前記コストメトリックは、前記隣接無線ノード間の無線チャネルで可能な送信レートに比例する、請求項１に記載の方法。
【請求項３】
発信元ノードの方向に、存在する場合には各隣接無線ノードに前記最低のコストメトリックの合計の指標を送信することを更に有する、請求項１に記載の方法。
【請求項４】
前記ルーティングテーブルを更新することは、前記次ホップのノードを介して通信することに関連する前記最低のコストメトリックの合計を記録することを更に有する、請求項１に記載の方法。
【請求項５】
前記発信元ノードは、インフラストラクチャ型基地局を有し、
前記無線ノードは、固定無線メッシュポイントを有し、
前記宛先ノードは、移動局を有する、請求項３に記載の方法。
【請求項６】
前記無線メッシュネットワークは、ブロードバンド無線ネットワークを有する、請求項１に記載の方法。
【請求項７】
前記潜在的なマルチホップパスは、発信元と前記宛先との間のトレリスのノードの帯域に制限され、
非隣接ノードの間のパスは無視される、請求項１に記載の方法。
【請求項８】
無線通信を宛先ノードにルーティングするために少なくとも２つの潜在的なマルチホップパスのうち１つでノードからの次ホップのノードを決定するロジックを有する処理回路を有し、
前記次ホップのノードは、前記宛先ノードへの最大の潜在的な送信レートを有するマルチホップパスにあるように決定される無線装置。
【請求項９】
前記ロジックは、無線メッシュルーティングマネージャを有する、請求項８に記載の無線装置。
【請求項１０】
前記ロジックは、前記決定された次ホップのノードと、前記宛先ノードへの前記マルチホップパスを通じて通信することに関係するコストメトリックとを、前記宛先ノードに関連付けるように、前記無線装置のルーティングテーブルを更に更新する、請求項８に記載の無線装置。
【請求項１１】
前記処理回路は、前記宛先ノードからアップストリームで１つ以上の隣接無線ノードに前記コストメトリックの指標を送信するロジックを更に有する、請求項１０に記載の無線装置。
【請求項１２】
前記装置は、マクロ基地局又はマイクロ基地局のうち１つを有する、請求項８に記載の無線装置。
【請求項１３】
前記装置は、前記処理回路と通信する無線周波数（RF）インタフェースを更に有する、請求項８に記載の無線装置。
【請求項１４】
無線通信を宛先ノードにルーティングするために２つ以上の潜在的なマルチホップパスで次ホップのノードを決定するロジックを有する処理回路であり、前記次ホップのノードは、前記宛先ノードに通信することに関連する最低のコストメトリックを有するマルチホップパスにあるように決定される処理回路と、
前記処理回路に通信可能に結合された無線周波数（RF）インタフェースと、
前記RFインタフェースに結合され、多入力又は多出力通信のうち少なくとも１つを行う少なくとも２つのアンテナと
を有する無線システム。
【請求項１５】
前記ロジックは、前記次ホップのノードを決定するためにViterbiアルゴリズムを使用する、請求項１４に記載のシステム。
【請求項１６】
前記最低のコストメトリックは、前記２つ以上の潜在的なマルチホップパスでの各ノードの間で実現可能な送信レートに反比例する、請求項１４に記載のシステム。
【請求項１７】
前記ロジックは、前記決定された次ホップのノードと、前記宛先ノードへの前記マルチホップパスを通じて通信することに関係するコストメトリックとを、前記宛先ノードに関連付けるように、ルーティングテーブルを更に更新する、請求項１４に記載のシステム。
【請求項１８】
前記システムは、ブロードバンド無線基地局を有する、請求項１４に記載のシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
無線ネットワークの範囲を拡張するため及び／又はコストを低減するために、無線ネットワークで中継点としてのノードを使用することがますます魅力的になってきている。例えば、広い地域を通じて分散した基地局の配置を必要とする無線広域ネットワーク（WWAN：wireless  wide  area  network）又は無線メトロポリタンネットワーク（WMAN：wireless  metropolitan  network）では、基地局は、何らかの種類のバックホールを介してコアネットワークに及び／又は相互に接続される必要がある。従来のネットワークでは、典型的には、バックホールは、有線接続で構成されている。しかし、配置を容易にしてネットワークに関連するコストを低減するために、有線バックホールではなく、又は有線バックホールと何らかの組み合わせで、無線バックホールが次第に検討されている。
【０００２】
発信元と宛先との間で信号を中継するために無線基地局を使用するネットワークの種類は、口語的にメッシュネットワークと呼ばれる。メッシュネットワークでは、無線ネットワークノードは、通信がその宛先に到達するために進み得るパスの“メッシュ”を形成し得る。無線バックホールとしての無線メッシュネットワークの使用は、多くの関心の対象になってきており、無線メッシュネットワークを通じた送信の効率を増加させるための進行中の取り組みが存在する。
【発明を実施するための最良の形態】
【０００３】
本発明の実施例の態様、特徴及び利点は、添付図面を参照して本発明の以下の説明から明らかになる。添付図面において、同様の参照符号は同様の要素を示す。
【０００４】
以下の詳細な説明は、WMANに関して本発明の例示的な実施例を記載し得るが、本発明の実施例はこれに限定されず、他の種類の無線ネットワークにも適用可能であり、他の種類の無線ネットワークで同様の利点が実現され得る。本発明の実施例が適用可能なネットワークは、特に無線パーソナルエリアネットワーク（WPAN：wireless  personal  area  network）、無線ローカルエリアネットワーク（WLAN：wireless  local  area  network）、WWAN（セルラネットワーク等）、及び／又はこれらのネットワークの何らかの組み合わせを含む。更に、本発明の実施例は、直交周波数分割多重（OFDM：Orthogonal  Frequency  Division  Multiplexing）変調を利用した無線ネットワークを参照して説明され得る。しかし、本発明の実施例はこれに限定されず、例えば、適切に適用可能である場合には、他の変調方式及び／又は符号化方式を使用して実装され得る。
【０００５】
以下の本発明の実施例は、無線システムの送信機及び受信機を含み、様々な用途で使用され得る。特に本発明の範囲に含まれる無線システムは、ネットワークインタフェースカード（NIC：network  interface  card）、ネットワークアダプタ、移動局、基地局、アクセスポイント（AP：access  point）、ハイブリッド・コーディネータ（HC：hybrid  coordinator）、ゲートウェイ、ブリッジ、ハブ及びルータを含み、これらに限定されない。更に、本発明の範囲内の無線システムは、セルラ無線電話システム、衛星システム、パーソナル通信システム（PCS：personal  communication  system）、双方向無線システム及び双方向ページャ、並びに計算装置（パーソナルコンピュータ（PC）及び関連の周辺機器、携帯情報端末（PDA：personal  digital  assistant）、パーソナルコンピュータアクセサリ、並びに本質的に関連する可能性があり本発明の実施例が適切に適用され得る全ての既存の及び将来生じるシステムを含む）を含んでもよい。
【０００６】
図１を参照すると、様々な本発明の実施例による無線通信ネットワーク100は、無線（OTA：over-the-air）無線周波数（RF：radio  frequency）リンクを介して情報を送信及び／又は受信することができる装置を有する如何なるシステムでもよい。例えば、一実施例では、ネットワーク100は、１つ以上の固定装置又は移動装置（移動局120等）に及び／又はからメッセージを通信又は中継する複数の無線ノード101-110（及び他の指定されていないノード）を有してもよい。図１は、各ノード101-110が図示の多角形（polynomial）の中心にある例示的なトポロジを示していることがわかる。図示のパターンの各六角形は、一般的に、メッシュネットワーク100を形成するノードの領域で、各ノードの無線リンクサービスエリアの空間範囲又は“セル”範囲を表すことを目的とする。更なる非参照セル（白色の六角形）もまた、特定の例に関係しないノードを有する。
【０００７】
特定の実施例では、ネットワーク100の無線ノードは、無線プロトコル及び／又は１つ以上のIEEE（Institute  of  Electrical  and  Electronics  Engineers）の様々な802無線標準（例えば、WLANの802.11(a)、(b)、(g)及び／又は(n)標準、WPANの802.15標準、及び／又はWMANの802.16標準を含む）に準拠した技術を使用して通信する装置でもよい。しかし、本発明の実施例はこの点に限定されない。
【０００８】
アドホックネットワーク構成の既存の802.11媒体アクセス制御（MAC）仕様を使用して、ネットワーク100でのブロードキャスト動作は、ブロードキャストメッセージのユニキャスト転送又はブロードキャストメッセージのブロードキャスト転送により実行され得る。ユニキャスト転送では、ブロードキャストメッセージは、それぞれの隣接に個々にユニキャストされ、次に、メッセージが最終的に全てのノード又はメッシュポイントにブロードキャストされるまで複数のユニキャスト送信を行うことにより、それぞれの隣接がブロードキャストメッセージを全てのその隣接に転送する。ブロードキャスト転送では、ブロードキャストメッセージは、固有のブロードキャスト宛先アドレス（例えば、全て1を含むMACアドレス）を使用して全ての隣接にブロードキャストされ得る。このようなメッセージを受信するそれぞれの隣接ノードはまた、メッセージをブロードキャストし、全てのメッシュノードがブロードキャストメッセージを受信するまで続く。
【０００９】
しかし、これらの従来の方法の一方を使用すると、かなりの送信冗長度のオーバーヘッドが生じる。この理由は、実際には数個のメッシュノードが、例えば基地局101と移動局120との間でポイントAからポイントBへのメッセージを取得しさえすればよいときに、全てのメッシュノードがブロードキャストメッセージを送信するからである。この種類の冗長度は、高スループットのインフラストラクチャ（ブロードバンド無線アクセスの無線バックホール構成等）では許容できない。
【００１０】
従って、無線メッシュネットワークを通じた送信を特にルーティングする技術が望ましい。更に、効率及び／又は信頼性の増加を促すために、メッシュルーティング技術は、送信をルーティングするパスを選択する際にメッシュノード間のチャネル特性を考慮するべきである。これは、ノード間のチャネルが固定無線局の間のように比較的遅く変化する特性又はフェージング特性を有する場合に、最適になる。一例として、図１を参照すると、各ノードの間のリンクで様々な異なるレベルのチャネル品質が存在し得る。従って、発信元ノード（例えば、基地局101）と宛先ノード（例えば、移動局120）との間で送信をルーティングすることは、宛先に到達するために必要な最小数のホップ（ノード102、103及び104の間の黒の矢印で図示する）を考慮するだけでなく、発信元ノードと宛先ノードとの間のノードの格子（lattice）又はトレリス（trellis）でこれらのノードと隣接ノード105-110との間の潜在的なパスでの無線リンクの品質を考慮してもよい。
【００１１】
１つの非限定的な例示的な実装では、ネットワーク100の１つ以上のノード（例えば、ノード101）は、物理有線接続（例えば、電気又は光ファイバ接続）を介してコアネットワーク（インターネットプロトコル（IP：Internet  Protocol）ネットワーク等）に接続された無線トランシーバでもよい。この種類の局は、ここでは“マクロ”基地局（BS）と呼ばれる。更に、特定の実施例では、ネットワーク100の１つ以上のノード（例えば、ノード102-110）は、電気又は有線若しくは光ケーブルによりコアネットワークに接続されていないが、前述の無線バックホールを提供する無線トランシーバでもよい。典型的には、これらの無線トランシーバの送信電力及びアンテナの高さは、マクロBSのものより小さい。これらの種類の局は、場合によっては（サービスエリアのサイズに応じて）“マイクロ”又は“ピコ”基地局と呼ばれる固定無線中継ノードでもよい。しかし、本発明の実施例はこの点に限定されない。従って、無線メッシュネットワーク100の特定の実施例では、マイクロ基地局は、802.16及び／又は802.11プロトコルを使用して無線リンクを介して相互及び／又はマクロ基地局に接続性を提供してもよい。
【００１２】
（本発明の概念は上りリンクのシナリオと下りリンクのシナリオとの双方に適用され得るが）マクロ基地局101により開始されたパケットが移動局120にルーティングされる必要のある下りリンクのシナリオを検討する。この実施例では、唯一の中継ノードが、マルチホップ方法で所定の時間／周波数リソースでその隣接の中継ノードに送信することを仮定する。ルーティングパスの検索は、基地局101と宛先120との間のノード102-110の最初のトレリスに制限される。最適なルートが中継ノード102-110のこのトレリス内のマルチホップパスに存在し、非隣接ノード間のパスが無視され得ることを仮定する。非隣接セル間のパスロスは隣接セル間よりかなり高いため、このことは合理的な仮定である。
【００１３】
この簡略化は、重み付きグラフで最低コストのパスを見つける一般的なルーティング問題（これは複雑なDijkstraアルゴリズムを使用して解決可能である）を、Viterbiアルゴリズムで解決可能な簡単な階層化ネットワークルーティング問題に軽減する。開発者のAndrew  Viterbiの名前をとって命名されたViterbiアルゴリズムは、観測されたイベントの系列を生じる隠された状態の最も可能性の高い系列（Viterbiパスとして知られる）を見つける動的プログラムアルゴリズムである。Viterbiアルゴリズムは、長期に渡って、符号分割多重アクセス（CDMA：code  division  multiple  access）及び他の通信システムで使用される畳み込み符号をデコードする際に特定のアプリケーションで通信リンクの誤り訂正方式に使用されてきている。本発明の実施例は、無線ネットワークで通信をルーティングするためにViterbiアルゴリズムを利用する最初のものであると見られている。
【００１４】
前記のシナリオに関与するノード101-120の限られた帯域のトレリス図200が図２に示されている。最短パス（例えば、ノード102と103と104との間）が合計ホップ数を最小化するために好ましいが、このパスのリンクのいずれかがかなりのチャネル減衰（fade）を受ける場合、信頼性及び／又はエンドツーエンドのスループットを最大化するために、ホップ数を増加させ、隣接ノード105、106、107、108、109又は110のいずれかを含む代替パスを選択することが望ましいことがある。本発明の実施例のルーティング技術は、トレリス図200のノードの特定のパターンの選択に拘らず動作し得る点に留意すべきである。例えば、限られたパスのノード数は、設計者の判断で拡大又は減少されてもよい。何らかの所定の選択は、Viterbi型ルーティングアルゴリズムを使用して最適化され得る階層化ネットワークルーティング方式を生じる。
【００１５】
図３を参照すると、マルチホップ無線メッシュネットワークで送信をルーティングするViterbi型ルーティングアルゴリズム300は、発信元ノードと宛先ノードとの間で隣接ノードの限られた帯域を特定し305、最低の合計コストメトリックを有する、宛先に通信する次ホップのノードを決定すること315を有してもよい。グループの各ノードが、最低コストのパスで次の隣接ホップを特定するそのルーティングテーブルを更新すると315、発信元からのパケットは、選択されたノードのグループのルーティングテーブルに基づいて宛先にルーティングされてもよい。
【００１６】
隣接ノードの限られた帯域を特定すること305は、様々な方法で実行されてもよい。典型的には、マクロBSの地域サービスエリア内の全てのマクロ基地局及び／又は移動局が考慮される。移動局の位置に基づいて、マクロBSは、潜在的に使用する限られたノードの集合を決定し、ルート構成について考慮されることをノードの集合に通知し得る。
【００１７】
特定されたグループの各ノードは、存在する場合には自分と宛先との間の隣接ノードを使用して、様々な潜在的なマルチホップパスで通信する合計コストメトリックを決定してもよい310。例えば、各ノードは、隣接の周辺ノードを通じてマルチホップパスの何らかの組み合わせを介して自分と宛先との間のリンクで通信することに関連するコストメトリックを計算してもよい。コストメトリックを計算することは、所望の如何なる種類のメトリックで実行されてもよい。本発明の一実施例では、コストメトリックは、送信が特定のリンクで受ける可能性のある利用可能なレート又は時間に関係してもよいが、如何なる所望のメトリックが使用されてもよい。トレリスでの各リンクのチャネル品質は、基礎となるネットワーク技術に応じて、例えばフィードバック信号又はビーコンの受動走査に基づいて決定されてもよい。スループットレートは、トレリスでの他の隣接ノードへのリンク毎に各ノード（例えば、図１〜２の101-110）で評価されてもよい。
【００１８】
例えば、ホップnでの送信時間がtn秒であり、ホップnでの送信レートがRnビット／秒であるようなNホップのパスを検討する。送信メッセージがBビットの情報を有しており、T秒で複数のホップで送信される場合、エンドツーエンドのスループットRは、以下の式１を使用して計算され得る。
【００１９】
【数１】
2009520445.tif 000003
ただし、Rnは、瞬時受信信号対雑音比SNRnの関数として計算される。SNRnは、第nホップでのチャネル実現の認識に依存する。
【００２０】
固定中継ノード（例えば、図１のノード101-110）の静止した性質のため、固定無線ホップ間で受けるチャネルは、（移動局が関与する場合の最後のホップを除いて）遅いフェージングになり、各ノードは、自分の送信／受信チャネルをトラッキングすることができることが想定される。ルーティングアルゴリズムの目的は、Rを最大化する（又はTを最小化する）マルチホップパスを見つけることである。同様に、各リンクのコストをcn=1/Rnとして示すと、スループットを最大化するパスは、合計コストを最小化するパスである。
【００２１】
従って、図２に示すトレリスの各分岐は、例えば以下の式を使用して、コストメトリックを割り当てられてもよい。
【００２２】
【数２】
2009520445.tif 000004
この設定で、Viterbi型ルーティングアルゴリズムを使用して、最適なマルチホップルートが容易に決定され得る。
【００２３】
ノードが、限られたグループでの隣接ダウンストリームノードのそれぞれを使用してマルチホップパスに関連するリンクのコストを決定すると、ノードは、宛先への最低コスト（又は“最適”）のパスで次ホップのノードを特定するために、その内部ルーティングテーブルを更新してもよい315。特定の実施例では、最低コストのパスでこのノードと宛先との間で通信する合計コストメトリックはまた、ルーティングテーブルに記録されてもよい。この情報は、自動的に又は要求に応じて隣接ノードにアップストリームで渡されてもよく320、隣接ノードは、この処理を繰り返してもよい。特定されたグループのノードが更新されると、パケットは、発信元により送信され、各ノード内のルーティングテーブルに基づいて最適パスを通じてルーティングされてもよい325。
【００２４】
本発明の実施例のViterbi型ルーティングアルゴリズムは、ルート選択が分散方式で（すなわちノード毎に）実行されるという意味で、DSDV（destination-sequenced-distance-vector）ルーティングアルゴリズムの特別な場合である。これは、接続性及びリンクコストについてのグローバルな情報が各ノードで利用可能であることを仮定する集中型リンクステートアルゴリズム（Dijkstra等）と異なる。
【００２５】
前述のマクロセルのインフラストラクチャの階層化の性質のため、ルート選択アルゴリズムの分散した実装は、任意のアドホックネットワークのものよりかなり小さいオーバーヘッドを受ける。更に、固定ネットワークトポロジを備えたこの種類のインフラストラクチャネットワークでのルーティングは、ルート変更をタイムリーに更新し、ルーティングのループを回避することを確保する。（ルーティングのループを形成する主な原因は、場合によっては非同期の受信又はネットワークトポロジの予想しない変更に対して不正確になり得る情報に基づいて、ノードが次のホップを完全に分散した方法で選択する点にある。）
本発明の実施例の態様によれば、固定無線局の間の安定した移動性の低いリンクのため、ルーティング更新は起動が容易になり、複雑なパケット交換の必要がなくなる。これらは、期間又は起動された更新に関連する過度のオーバーヘッドを有するアドホックネットワークのDSDVの全ての改善点である。
【００２６】
以下は、階層化ネットワーク（例えば、図２のトレリス200により表されるような図１のネットワーク）でViterbi型ルーティングアルゴリズムを実装するために使用され得る擬似コードを表している。図２の各ノード101-120は、トランシーバ局（BS又はMS）を表す。図２に示す下りリンクのルーティング問題について、一実施例によるルーティングアルゴリズムは、後方から（例えば、ノード110で始まり基地局101に戻る）、分散して計算効率的に最低コスト（又は最適）のパスを計算する。アルゴリズムは、以下の繰り返し手順を使用してもよい。(i)各トレリス段階で、判定ノードは、宛先への最善（最低コスト）の“生き残り（surviving）”パスのみを保持し、そのノードと宛先との間の残りの潜在的なパスを無視又は除去する。(ii)判定ノードは、生き残りパスに基づいてそのコストメトリックを更新する。
【００２７】
（MS120から始まる）最低コストのパスは、以下の擬似コードを使用して計算されてもよい。
【００２８】
1.リンク毎にランダムなチャネルを生成し（図２の分岐の矢印は各リンクを表す）、前記の式(2)に従って分岐コストメトリックを計算する。
【００２９】
2.集合Φ(k)が最低コストでのノードkからMSへのノードの系列（ノードkの最適ルートと呼ばれる）を含むものとし、メトリックdkは、Φ(k)により指定されたルートに基づいてノードkからMSにデータを送信する合計コストを示す。
【００３０】
3.MSでのコストをゼロに初期化する。すなわち、dMS=0且つΦ(MS)=[]=空である。
【００３１】
4.全てのノードについて以下の手順を繰り返す。集合Ω(k)がノードk∈K（Kはトレリスの全てのノードの集合である）からデータを受信し得るノードの集合とする。Ω(k)の全てのノードが計算された最適なルートΦ(i)とコストメトリックdi,i∈Ω(k)とを有する場合、ノードkのコストメトリックを
【００３２】
【数３】
2009520445.tif 000005
として割り当てる。ただし、ck→iはノードkからノードi∈Ω(k)へのリンクの分岐メトリックである。Φ(k)をΦ[k  Φ(ibest)]として割り当てる。ただし、
【００３３】
【数４】
2009520445.tif 000006
である。
【００３４】
このように、移動局120で始まり、本発明の実施例によるルーティングアルゴリズムは、前述の手順に従って各ノードで順次にコストメトリックと最適ルートとを計算してもよい。マクロ基地局101で最低コストを生じる分岐（無線リンク）の集合（すなわち、前記の擬似コードでの集合Φ(Macro_BS)）は、最適なマルチホップパスとして選択され、宛先120にパケットを送信する320ために使用される。アルゴリズムが終了した後に、個々のノードは、最適パスを通じて移動局120宛のパケットを自己ルーティングしてもよい。パケットは、各ノードで格納されたルーティングテーブルを使用することにより、ネットワークのノード間で送信されてもよい。
【００３５】
一実施例では、各ノードは、例えば、全ての利用可能な宛先と、各宛先に関連するコストメトリック及び次のホップとを記載するルーティングテーブルを有してもよい。一例の実装では、各ノードは、それぞれ潜在的な次のホップのコストメトリックを要求することにより、階層化インフラストラクチャで潜在的な次ホップのノードの使用可能なスループットを推定してもよい。隣接ノードとチャネルで通信するために決定されたコストメトリック自体に加えて提供されたコストメトリックは、これまで宛先に通信する最適な次のホップ及び合計コストメトリックを有するノードのルーティングテーブルを更新するために使用されてもよい。
【００３６】
アルゴリズムの例が図４に示されている。ノード間の各分岐（リンク）は、三角で示される例示的なコストでラベル付けされており、ノード101-120（発信元=101及び宛先=120）がルーティングテーブルと共に示されている。この簡単な例でわかるように、最適なマルチホップパス（すなわち、最低コスト）は、ノードパス101→102→103→110→104→120であり、合計コストは9である（ノード101のルーティングテーブルに示される）。従って、最短パスは、発信元101と宛先120との間で４つのみのホップになるが、最低コスト及び／又は最も信頼性の高いパスは、５つのホップを有する（点線の矢印で示す）。２つ以上のマルチホップパスが同じ最低コストを有する場合、アルゴリズムは最低数のホップを有するパスを選択してもよい。或いは、２つ以上が同じホップ数を同様に有する場合、アルゴリズムは、使用する最適なパスをランダムに選択してもよい。
【００３７】
移動局120が、最適なルートがまだ確立されていないマクロ基地局101へのルート（すなわち、上りリンクルート）を希望する場合、一実施例では、移動局120は、ネットワークを通じてルート要求（RREQ：route  request）パケット又は同様のクエリ通信をブロードキャストしてもよい。RREQパケットを受信すると、マクロ基地局101は、そのロケーションコントローラ（LC：location  controller）を検索してもよい。ロケーションコントローラ（LC）は、マルチホップ通信に関与し得るノードのグループを決定するために、各移動局及び／又はマクロ基地局の位置及び周辺に関する情報を有してもよい。この情報は、ルート応答（RREP：route  reply）メッセージ又は同様の広告を使用して送信されてもよい。RREPが移動局120に伝達されると、ノードは、隣接ノードへの転送ポインタを設定し、下りリンクのシナリオについて図２の示すものと同様の階層化インフラストラクチャネットワークのトレリスを生成してもよい。
【００３８】
移動局120がRREPを受信すると、そのルーティングを更新するためにこの情報を使用してもよい。例えば、RREPが、小さいコストを有する大きいホップ数又は同じホップ数を有するルーティングパスを開示する場合、マクロ基地局101へのメッセージについてそのルーティング情報を更新し、送信に更新されたルートを使用し始めてもよい。
【００３９】
図５を参照すると、無線ネットワークで使用される装置500は、前述の１つ以上の処理で記載したように通信をルーティングするロジック（例えば、回路、プロセッサ及びソフトウェア、又はこれらの組み合わせ）を含む処理回路550を有してもよい。特定の実施例では、一般的に装置500は、無線周波数（RF：radio  frequency）インタフェース510と、ベースバンド及びMACプロセッサ部550とを有してもよい。
【００４０】
一例の実施例では、RFインタフェース510は、変調信号（例えばOFDM）を送信及び受信するように適合された如何なる構成要素又は構成要素の組み合わせでもよい。しかし、本発明の実施例は、何らかの特定の変調方式に限定されない。RFインタフェース510は、例えば、受信機512と、送信機514と、周波数合成器516とを有してもよい。インタフェース510はまた、必要に応じて、バイアス制御、水晶発振器及び／又は１つ以上のアンテナ518、519を有してもよい。更に、代替として又は更に、RFインタフェース510は、必要に応じて、外部電圧制御発振器（VCO：voltage-controlled  oscillator）、表面弾性波フィルタ、中間周波数（IF:：intermediate  frequency）フィルタ及び／又は無線周波数（RF）フィルタを使用してもよい。様々なRFインタフェースの設計及びこれらの動作は当該技術分野において既知であり、その構成の説明はここでは省略される。
【００４１】
ある実施例では、インタフェース510は、WPAN、WLAN、WMAN又はWWANについての１つ以上のIEEE標準に準拠したOTAリンクアクセスを提供するように構成されてもよい。しかし、実施例はこの点に限定されない。
【００４２】
処理部550は、受信／送信信号を処理するようにRFインタフェース510と通信／協調してもよく、一例のみとして、受信信号をデジタル化するアナログ・デジタル変換器552と、搬送波送信のために信号をアップコンバートするデジタル・アナログ変換器554と、各受信／送信信号の物理（PHY）リンクレイヤ処理のためのベースバンドフィルタ556とを有してもよい。処理部550はまた、MAC／データリンクレイヤ処理のための処理回路559を含んでもよく、処理回路559から構成されてもよい。
【００４３】
本発明の特定の実施例では、メッシュルーティングマネージャ558は、処理部550に含まれてもよく、前述のようにルーティングを決定し、メッシュノードのアドレス指定を制御するように機能してもよい。代替として又は更に、PHY回路556又はMACプロセッサ559は、これらの機能のうち特定のものの処理を共有してもよく、これらの処理を個々に実行してもよい。MAC及びPHY処理もまた、必要に応じて単一の回路に統合されてもよい。
【００４４】
装置500は、例えば、移動局、無線基地局若しくはAP、ハイブリッド・コーディネータ（HC：hybrid  coordinator）、無線ルータ及び／又は電子装置のネットワークアダプタでもよい。従って、装置500の前述の機能及び／又は特定の構成が、必要に応じて含まれてもよく、省略されてもよい。
【００４５】
装置500の実施例は、単一入力単一出力（SISO：single  input  single  output）アーキテクチャを使用して実装されてもよい。しかし、図５に示すように、特定の実装は、送信及び／又は受信用の複数のアンテナ（例えば、518、519）を有する多入力多出力（MIMO：multiple  input  multiple  output）、他入力単一出力（MISO：multiple  input  single  output）又は単一入力多出力（SIMO：single  input  multiple  output）アーキテクチャを使用してもよい。更に、本発明の実施例は、OTAリンクアクセスにマルチキャリア符号分割多重（MC:CDMA：multi-carrier  code  division  multiplexing）、マルチキャリア直接拡散符号分割多重（MC-DS-CDMA：multi-carrier  direct  sequence  code  division  multiplexing）を利用してもよく、本発明の実施例の機能に準拠した他の既存の又は将来生じる変調又は多重方式を利用してもよい。
【００４６】
装置500の構成要素及び機能は、別々の回路、特定用途向け集積回路（ASIC：application  specific  integrated  circuit）、論理ゲート及び／又は単一チップアーキテクチャの何らかの組み合わせを使用して実装されてもよい。更に、装置500の機能は、マクロコントローラ、プログラム可能ロジックアレイ及び／又はマイクロプロセッサ、又は必要に応じて前述の何らかの組み合わせ（併せて又は個別に“ロジック”と呼ばれる）を使用して実装されてもよい。
【００４７】
例示的な装置500は、多数の潜在的な実装の唯一の機能的に記述する例を表していることがわかる。従って、添付図面に記載したブロック機能の分割、省略又は包含は、これらの機能を実装するハードウェア構成要素、回路、ソフトウェア及び／又は要素が本発明の実施例で必ずしも分割、省略又は包含されることを推論するのではない。
【００４８】
物理的な可能性に反して、発明者は、ここに記載の方法は、(i)如何なる順序及び／又は如何なる組み合わせで実行されてもよく、(ii)各実施例の構成要素が如何なる方法で結合されてもよいことを想定する。
【００４９】
本発明の例示的な実施例について説明したが、本発明の範囲を逸脱することなく、多数の変更及び変形が可能である。従って、本発明の実施例は、前述の特定の開示により限定されず、特許請求の範囲及びその均等の範囲のみによって限定される。
【図面の簡単な説明】
【００５０】
【図１】本発明の様々な実施例による無線メッシュネットワークでの無線ノードの配置を示すブロック図
【図２】本発明の様々な実施例による無線メッシュネットワークでの無線ノードの配置を示すブロック図
【図３】本発明の１つ以上の実施例に従って無線メッシュネットワークを通じて送信をルーティングするViterbi型アルゴリズムを示すフローチャート
【図４】本発明の様々な実施例によるコストメトリック及びルーティング更新の例示的な計算を有する図２の構成を示すブロック図
【図５】本発明の様々な態様による例示的な無線装置を示すブロック図
【図１】
2009520445.tif 000007
【図２】
2009520445.tif 000008
【図３】
2009520445.tif 000009
【図４】
2009520445.tif 000010
【図５】
2009520445.tif 000011
【国際調査報告】
2009520445.tif 000012
2009520445.tif 000013
2009520445.tif 000014