(57)【要約】      （修正有）【課題】複数の無線ノードを備えるモバイル無線ネットワークにおいてルーティングするシステムを提供する。【解決手段】ローカル無線ノードは、複数の無線ノードについての重み付きネットワークグラフを管理するコントローラノードに対して、少なくとも１つの送信先ノードに関連するルート要求メッセージを送信し、送信先ノードまでの経路を受信し、受信した経路に基づいて、送信先ノードに対してパケットをルーティングする。システムは、送信元ノードから少なくとも１つの送信先ノードに関連するルート要求メッセージを受信し７２２、複数の無線ノードについての重み付きネットワークグラフに基づいて、送信元ノードと送信先ノードとの間の経路を計算し７２４、少なくとも送信先ノードに対して、計算された経路を送信する７２６。【選択図】図７Ｂ
2015139219.tif 000002
【特許請求の範囲】
【請求項１】
モバイル・アドホックネットワーク（ＭＡＮＥＴ）において、
複数の無線ノードについての重み付きネットワークグラフを管理するコントローラノードと、
複数のモバイルノードとを備え、各モバイルノードが、
コントローラノードに対して、少なくとも１つの送信先ノードに関連するルート要求メッセージを送信するように構成された要求送信機構と、
重み付きネットワークグラフに基づいて計算される経路をコントローラノードから受信するように構成された経路受信機構と、
受信した経路に基づいて、送信先ノードに対してパケットをルーティングするように構成されるルーティング機構とを備える、ＭＡＮＥＴ。
【請求項２】
経路を受信することが次ホップノードから送信先ノードまでの経路を含み、経路が、モバイルノードまでのルートを確立するために送信先ノードを介してコントローラノードによって送信された、請求項１のＭＡＮＥＴ。
【請求項３】
経路を受信することがコントローラノードから経路を受信することを含み、送信先ノードに対してパケットをルーティングすることが、受信した経路に基づいて、送信先ノードに対するソースルートを実行することを含む、請求項１のＭＡＮＥＴ。
【請求項４】
コントローラノードに対してルート要求メッセージを送信するときに、要求送信機構が、さらに、
モバイルノードがコントローラノードに対するアクセスを有するかどうかを判定し、
アクセスが存在しないことに応答して、コントローラノードに対するアクセスを有するピアネットワークノードに対して、送信先ノードに関連するルート要求メッセージを送信するように構成されている、請求項１のＭＡＮＥＴ。
【請求項５】
モバイルノードが、さらに、モバイルノードに関連する状態更新をコントローラノードに対して送信するように構成された更新送信部を備える、請求項１のＭＡＮＥＴ。
【請求項６】
状態更新がモバイルノードに関連する近隣メトリックを含み、近隣メトリックが、近隣ノード及び各近隣ノードについての接続メトリックのリストを含み、接続メトリックが、
チャネル信頼性、
残余帯域幅、及び、
キュー待ち時間
のうちの１つ以上を含む、請求項５のＭＡＮＥＴ。
【請求項７】
状態更新が、さらに、
ローカル無線ノードが加入されるマルチキャストグループのリスト、及び、
ローカル無線ノードによって記憶されたリソースオブジェクトの名称
のうちの１つ以上を含む、請求項５のＭＡＮＥＴ。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、モバイル・アドホックネットワーク（ＭＡＮＥＴ）に関する。より具体的には、本開示は、インテリジェント・バックボーン・インフラストラクチャに基づくソフトウェア・ディファインド・ＭＡＮＥＴに関する。
【背景技術】
【０００２】
典型的なアドホック通信システムは、大抵の場合、非集中且つ自立性のある方式で通信することができる独立したモバイルユーザを必要とする。例えば、モバイル・アドホックネットワーク（ＭＡＮＥＴ）は、２つの無線ノード間の経路を決定するためにピア・ツー・ピア通信プロトコルを使用する。ＭＡＮＥＴのいくつかの重要な特徴は、移動性及びノード組織についての基地局又はアクセスポイントのための要件を有しないという事実のためにルート変更に適応する能力を含む。
【０００３】
理論的には、ＭＡＮＥＴは、災害救援及び戦場行動、緊急捜索及び救助任務、並びに他の多くのモバイル及び分散アプリケーションをサポートするための理想的な通信インフラストラクチャを提供する。しかしながら、これらのアプリケーションは、今日のネットワークにおいては効果的にサポートされることができない。これは、主に、ネットワークがノードやアプリケーションの数が増加して発生した過剰なシグナリングのためにスケーリングしないためである。具体的には、ＭＡＮＥＴプロトコルは、ホップ・バイ・ホップで多くのノードに（例えばルーティング情報などの）計算を割り振る。ループや過剰なフラッディングを回避するためなど、プロトコルの正確且つ効率的な動作を保証するために、複雑な分散アルゴリズムが必要とされている。
【０００４】
一方、セルラーシステムは、通常はＭＡＮＥＴが近くの隣人に達成することができるよりもはるかに低いデータレートで広い地域にサービスを提供するために（ネットワークで結ばれた基地局のセットなどの）集中型リソースを使用する。しかしながら、分散システムに比べて、この集中型システムは、システムの集中型の性質のために、はるかに単純なルーティング及びプロトコル動作を可能とする。
【０００５】
集中型の性質はまた、オープンフロープロトコルに基づくものなどのソフトウェア・ディファインド・ネットワーキング（ＳＤＮ）にみることができる。ＳＤＮにおいて、「制御プレーン」及び「データプレーン」は分離され、少なくとも２つの制御ルータは、制御されたネットワーク要素における状態をインスタンス化するために使用される。ＳＤＮにより、ネットワークのトポロジは、ネットワーク規模の視野に応じて送信元から送信先までのルートを計算するコントローラノードにおいて仮想化され、ネットワークの各スイッチにおいて「フロー状態」をインスタンス化することができる。あいにく、現在のＳＤＮの実装は、ネットワークのフロー状態に基づいて経路を計算しており、それゆえに、ＭＡＮＥＴには適用することはできない。
【発明の概要】
【課題を解決するための手段】
【０００６】
１つの実施形態は、複数の無線ノードと、複数の無線ノードについての重み付きネットワークグラフを管理するコントローラノードとを含むモバイル無線ネットワークを提供する。動作中において、ローカル無線ノードは、コントローラノードに対して少なくとも１つの送信先ノードに関連するルート要求メッセージを送信し、送信先ノードまでの経路を受信し、受信した経路に基づいて送信先ノードに対してパケットをルーティングする。経路は、重み付きネットワークグラフに基づいて計算される。
【０００７】
本実施形態の変形例において、ローカル無線ノードは、次ホップノードから送信先ノードまでの経路を受信する。経路は、ローカル無線ノードまでのルートを確立するために送信先ノードを介してコントローラノードによって送信された。
【０００８】
本実施形態の変形例において、ローカル無線ノードは、コントローラノードから経路を受信し、受信した経路に基づいて、送信先ノードに対してソースルートを実行することによって送信先ノードに対してパケットをルーティングする。
【０００９】
本実施形態の変形例において、ローカル無線ノードは、ローカル無線ノードがコントローラノードに対するアクセスを有するかどうかを判定することにより、及び、アクセスが存在しないことに応答して、コントローラノードに対するアクセスを有するピア・ネットワークノードに対して送信先ノードに関連するルート要求メッセージを送信することにより、コントローラノードに対してルート要求メッセージを送信する。
【００１０】
本実施形態の変形において、ローカル無線ノードは、さらに、コントローラノードに対してローカル無線ノードに関連する状態更新を送信する。
【００１１】
さらなる変形例において、状態更新は、ローカル無線ノードに関連する近隣メトリックを含む。近隣メトリックは、近隣ノードのリストと、各近隣ノードについての接続メトリックとを含み、接続メトリックは、チャネル信頼性、残余帯域幅及びキュー待ち時間のうちの１つ以上を含む。
【００１２】
さらなる変形例において、状態更新は、さらに、ローカル無線ノードが加入されるマルチキャスト・グループ及びローカル無線ノードによって記憶されたリソースオブジェクトの名称のリストのうちの１つ以上を含む。
【００１３】
１つの実施形態は、複数の無線ノードを備えるモバイル無線ネットワークにおいてルーティングするためのシステムを提供する。動作中において、システムは、送信元ノードから少なくとも１つの送信先ノードに関連するルート要求メッセージを受信し、複数の無線ノードについての重み付きネットワークグラフに基づいて送信元ノードと送信先ノードとの間の経路を計算し、少なくとも送信先ノードに対して計算された経路を送信する。
【００１４】
本実施形態の変形例において、システムは、複数の無線ノードから受信した近隣メトリックに基づいて、重み付きネットワークグラフを計算する。
【００１５】
さらなる変形例において、システムは、近隣メトリックに基づいて、無線ネットワーク内の各リンクについてのコスト関数を計算することによって重み付きネットワークグラフを計算する。
【００１６】
本実施形態の変形例において、システムは、重み付きネットワークグラフに基づいて、マルチキャストグループについてのマルチキャストコアを選択し、マルチキャストグループ内の各ノードについてのマルチキャストコアに対する最良のルートを計算する。
【００１７】
本実施形態の変形例において、システムは、無線ネットワーク内のゲートウェイノードを選択し、ゲートウェイノードの送信をスケジューリングし、ゲートウェイノードが異なる無線チャネルで動作する第２の無線ネットワーク内のノードと通信するのを可能とする。ゲートウェイノードの送信をスケジューリングすることは、第２の無線ネットワークと通信するためにゲートウェイノードについての１つ以上の送信機会を予約することを含む。
【図面の簡単な説明】
【００１８】
【図１】図１は、本発明の実施形態にかかる例示的なソフトウェア・ディファインド・ＭＡＮＥＴ（ＳＤＭ）を図示する図を提示している。
【図２】図２は、本発明の実施形態にかかる、ノードからその近隣に対して送信された「ハロー」パケットの例示的なフレームフォーマットを図示する図を提示している。
【図３】図３は、本発明の実施形態にかかる、次ホップノードを更新するための例示的な擬似コードを提示している。
【図４】図４は、本発明の実施形態にかかる、バックボーンに対してモバイルノードによって送信された例示的な更新メッセージを図示する図を提示している。
【図５】図５は、本発明の実施形態にかかる、ユニキャストルーティング処理を図示する図を提示している。
【図６】図６は、本発明の実施形態にかかる例示的なマルチキャストシナリオを図示する図を提示している。
【図７Ａ】図７Ａは、本発明の実施形態にかかる、送信元モバイルノードによって実行される例示的なルーティング処理を図示するフローチャートを提示している。
【図７Ｂ】図７Ｂは、本発明の実施形態にかかる、バックボーンにおいてコントローラノードによって実行される例示的なルーティング処理を図示するフローチャートを提示している。
【図７Ｃ】図７Ｃは、本発明の実施形態にかかる、バックボーンによって実行される例示的なルート更新処理を図示するフローチャートを提示している。
【図８】図８は、本発明の実施形態にかかる例示的なサービス指向ルーティングシナリオを図示する図を提示している。
【図９】図９は、本発明の実施形態にかかる相互ＭＡＮＥＴ通信用の例示的なシナリオを図示する図を提示している。
【図１０】図１０は、本発明の実施形態にかかるコントローラノードの例示的なアーキテクチャを図示する図を提示している。
【図１１】図１１は、本発明の実施形態にかかる、ＭＡＮＥＴノードの例示的なアーキテクチャを図示する図を提示している。
【図１２】図１２は、本発明の実施形態にかかる、ソフトウェア・ディファインド・ＭＡＮＥＴ（ＳＤＭ）においてルーティングするための例示的なコンピュータシステムを図示している。
【発明を実施するための形態】
【００１９】
図において、同様の参照符号は、同じ図要素を指している。
【００２０】
以下の説明は、当業者が実施形態を作成及び使用するのを可能とするために提示され、特定の用途及びその要件の文脈で提供される。開示された実施形態に対する様々な変更例は、当業者にとって容易に明らかであり、本願明細書において定義された一般的原理は、本開示の精神及び範囲から逸脱することなく他の実施形態及び用途に適用することができる。それゆえに、本発明は、示された実施形態に限定されるものではなく、本願明細書に開示された原理及び特徴と一致する最も広い範囲を与えられるべきである。
【００２１】
本発明の実施形態は、現在既存のＭＡＮＥＴのスケーラビリティの問題を解決するソフトウェア・ディファインド・ＭＡＮＥＴのためのシステムを提供する。より具体的には、システムは、無線ネットワークの重み付きグラフを維持し、重み付きグラフの変化に基づいて、共有マルチキャストツリーを計算することができる集中型バックボーンサービスを含む。無線ネットワークは、例えば、各ワンホップの近隣者に対してリンク品質を報告するために、バックボーンサービスに対して状態更新を送信することができる多数のモバイルノードを含む。集中型バックボーンサービスは、状態更新に基づいて重み付きグラフを更新することができ、モバイルノードは、集中型バックボーンサービスから最適化されたルーティング経路を要求することができる。モバイルノードがバックボーンサービスまでの経路を有していない場合、このモバイルノードは、ピア・ツー・ピア・ルーティングを得るために、その接続されたピア・ノードに対してルーティング要求又は状態更新を送信することができる。
【００２２】
いくつかの実施形態において、無線ネットワーク内のルーティングは、インタレスト・ディファインド・メッシュ・エンクレーブに基づいて達成される。メッシュは、データ又はサービスの特定の部分に関連するユニキャスト及びマルチキャストフローについての接続されたＭＡＮＥＴの要素のセットを含む。バックボーンサービスは、送信先又はサービスにおけるインタレストの有無に基づいてメッシュを有効化又は無効化することができ、インタレスト（エンクレーブ）の各領域内のシグナリングオーバーヘッドのほとんどを制限する。ここで、用語「インタレスト」は、一般に、データ又はサービスの特定の部分についてのデータトラフィックを指す。また、情報集中型ネットワーキング（ＩＣＮ）の文脈のもとに、用語「インタレスト」又は「インタレストパケット」は、データの名称（又は名称接頭辞）を含むことにより、データの一部の要求を示すパケットを指す。データの消費者は、インタレストパケットを満たすために一致するコンテンツオブジェクトを提供することができる記憶装置（例えば、キャッシュサーバ）又はデータ製作者に向かってＩＣＮルータが伝播することができる、名称が付されたデータネットワークにわたってインタレストパケットを広めることができる。
【００２３】
いくつかの実施形態において、システムは、ＱｏＳ（サービス品質）を可能とするために、フロー固有のルーティングを使用することができる。例えば、バックボーンサービスは、チャネル信頼性、残余帯域幅及びキュー待ち時間などの無線ノードのセットによって報告された近隣情報を収集することができる。バックボーンサービスは、所定のフローについての送信先までの最適ルートを決定するために近隣情報を使用することができる。
【００２４】
バックボーンサービスはまた、２つ以上のＭＡＮＥＴにわたる通信を容易とすることができる。各ＭＡＮＥＴは、異なる周波数及び／又は所定の周波数についての異なる時間スロットを介してなど、異なるピア・ツー・ピア・チャネル上で動作する２つのＭＡＮＥＴ間のゲートウェイとして作用する１つ以上のノードを含むことができる。バックボーンサービスは、競合のないＭＡＮＥＴ間ルーティングを保証するために外部のＭＡＮＥＴにおけるタイムスロット又は通信時間を予約することができる。
【００２５】
今日の無線ネットワークにおいて使用されるプロトコルスタックは、本質的に、ピア・ツー・ピア・シグナリングに基づいており、制限された情報によって動作するように設計される。これらの既存のプロトコルにおいて、制御及びデータプレーンは、ユーザデータが広められる範囲内で大してコンテキストを考慮しておらず、各パケットは、そのヘッダにそれ自体のコンテキストを指定し、バックボーンは、サイズに対処するために使用される階層ネットワークアーキテクチャのコンテキストの範囲内のリンクレベルでのみ利用される。
【００２６】
ＳＤＮは、ピア・ツー・ピア・シグナリングを削減し、コントローラに対して更新された近隣情報を送信するのみのためのスイッチを設定することによってスイッチからのシグナリングを削減する、簡略化されたネットワーク動作を提供する。ＳＤＮはまた、例えば、様々な無線ノードからの近隣情報に基づいて、ネットワークの設定及び管理を簡略化するバックボーンサービスを提供する。しかしながら、現在のＳＤＮの実装は、サーバ室における有線ネットワークトポロジ動作に焦点をあてていることから、典型的なＳＤＮは、ＭＡＮＥＴが直面するスケーラビリティの問題に直接対処していない。ここで、コントローラは、全てのスイッチから１つのリンク離れており、シグナリングは、単にネットワーク層においてのみ実行される。換言すれば、典型的なＳＤＮの実装は、コンテンツ及びサービスの動的な配置を容易としない。
【００２７】
情報集中型ネットワーキング（ＩＣＮ）は、最近、多くの研究の注目を集めている。ＩＣＮの実装は、コンテンツオブジェクトが名称（例えば、階層又はフラット名称）を有する公開加入のスキームから構成され、ルーティングノードは、ローカルに将来の要求を処理するためにコンテンツオブジェクトをキャッシュすることができる。コンテンツの特定部分におけるインタレストを述べる各要求は、ルート要求と同様に拡散され、要求されたコンテンツのコピーを有する最も近いサイトが要求に応答する。ＩＣＮの実装は、アプリケーションに最も近いサイトからアプリケーションに対してコンテンツ及びサービスを提供することにより、アプリケーションのニーズに対してネットワークを動的に適応させることができる。
【００２８】
しかしながら、典型的なＩＣＮの実装における制限は、ネットワークが大規模な動的ネットワークに向けて拡張するのを可能としない。第１に、これらのＩＣＮの実装は、ネットワークピア間において過剰なシグナリングオーバーヘッドを発生し、各ルーティングノードにおいて望ましくない大きな計算オーバーヘッドを必要とするオブジェクト名に基づいてパケットをルーティングする。アプリケーションによって要求された情報オブジェクトの数がネットワークノードの数よりもはるかに大きくなるのにともない、シグナリング及び計算オーバーヘッドは増加する。第２に、ＩＣＮの実装は、要求されたコンテンツがローカルに記憶されているかどうかを判定するためのコンテンツ要求（例えば、インタレストパケット）を評価するために追加の計算オーバーヘッドを中継ノードに発生させるキャッシュノードとしてルーティングノードを利用する。
【００２９】
本発明のいくつかの実施形態は、サービスとしてネットワークバックボーンを使用するソフトウェア・ディファインド・ＭＡＮＥＴ（ＳＤＭ）を提供する。ＳＤＭは、予め定義されたクラスタ又は人為的なネットワーク境界を使用することなく、非常に大規模な動的ネットワークを実装するために、ＳＤＮ、ＩＣＮ及びユーティリティベースのクロスレイヤリングを統合する（ルーティング状態、チャネル状態及びＭＡＣ（メディア・アクセス・コントロール）状態の統合を含む）。
【００３０】
図１は、本発明の実施形態にかかる例示的なソフトウェア・ディファインド・ＭＡＮＥＴ（ＳＤＭ）を図示する図を提示している。ＳＤＭ１００は、バックボーンクラウド１０２（以下、バックボーン１０２と称される）と、モバイル・ネットワークノードのセットとを含むことができる。より具体的には、バックボーン１０２は、有線又は無線ネットワークを介して互いに通信するコントローラノード１０４などの１つ以上のコントローラノードを含むことができる。少なくともいくつかのモバイルノードは、無線ネットワークを介して、直接的に又はマルチホップ経路を介してバックボーン１０２と通信することができる。例えば、モバイルノード１０６は、ワンホップリンクを介してバックボーン１０２に対して結合されるのに対して、モバイルノード１０８は、ノード１０６を通る２ホップリンクを介してバックボーン１０２に対して結合される。また、いくつかのモバイルノードは、バックボーンクラウド１０２までの経路を検出できないことがある。例えば、モバイルノード１１０及び１１２は、大きな物理的障壁１２０がバックボーン１０２までの経路を有する任意のデバイスまでの通信チャネルを阻害するときにはバックボーン１０２までの経路を検出できないことがある。しかしながら、モバイルノード１１０及び１１２は、互いにネットワーク経路を検出してもよく、デフォルトのピア・ツー・ピア・ルーティング・プロトコルを介して互いに通信することができる。図１において、破線は、無線リンクを示している。
【００３１】
動作中において、バックボーン１０２までの経路を有するモバイルノードは、バックボーン１０２に対してローカル情報及びこの近隣の情報を定期的に報告するためにそれらの近隣の環境を監視することができる。モバイルノードによってバックボーン１０２に対して報告された近隣情報は、近隣メトリック（例えば、受信信号に基づく各ワンホップの近隣者に対するリンク品質）、ノードによって使用されたマルチキャストアドレスのセットを含む。ローカル情報は、ローカルノードについての地理的位置（例えば、全地球測位システム（ＧＰＳ）座標）及びローカルノードによってキャッシュされたコンテンツの変化を含むことができる。
【００３２】
近隣メトリックは、各近隣者についての接続メトリックとともにローカルノードによって検出された近隣ノードのリストを含むことができる。各近隣者についての接続メトリックは、ＭＡＣ（メディア・アクセス・コントロール）層におけるノードによって収集されることができる。いくつかの実施形態において、各近隣者についての接続メトリックは、これらに限定されるものではないが、チャネル識別子、チャネル信頼性メトリック、残余帯域幅メトリック及びキュー待ち時間を含む。チャネル信頼性メトリックは、信号対干渉雑音比（ＳＩＮＲ）によって又は成功したパケット配信率によって計算されることができる。
【００３３】
いくつかの実施形態において、ネットワークノードは、（「ハロー」パケットに添付されたシーケンス番号に基づいて決定される）近隣ノードによって送信された全体の「ハロー」パケットに対するローカルノードにおいて明確に受信した「ハロー」パケット（より詳細に後述する）の比率を計算することにより、その近隣ノードまでのリンクのチャネル信頼性を測定する。さらなる実施形態において、チャネル信頼性は、上りリンク及び下りリンク方向の双方について計算されたパケットの成功率に基づいて計算される。ネットワークノードは、上りリンクパケット成功率及び下りリンクパケット成功率の積を計算することによってチャネル信頼性メトリックを計算することができる。近隣ノードまでのリンクについての残余帯域幅メトリックは、リンクを介して利用可能な帯域幅の量から計算され、スケジューリングされたタイムスロットのセットにおいて利用可能な空きタイムスロットから計算される。ノードは、パケットが送信される前にそれらＭＡＣキューに費やす平均時間からキュー待ち時間を計算する。バックボーン１０２は、所定のフローについての送信先ノードへの最良のルートを決定するために、これらの近隣メトリックを使用する。
【００３４】
マルチキャストグループ情報は、ネットワークノードが所定の時点において加入している旨の（ＭＡＣ  ＩＤ内で表現されるような）マルチキャストグループを示す。バックボーン１０２は、先を見越したマルチキャストツリーを作成して維持するようにマルチキャスト情報を使用することができる。
【００３５】
ネットワーク１００にわたる各モバイルノードは、ネットワークノードによってキャッシュされたコンテンツ項目の変化をバックボーン１０２に通知するためにバックボーン１０２に対してコンテンツデルタ情報を送信することができる。バックボーン１０２に対してコンテンツデルタ情報を送信することは、バックボーン１０２が既にネットワークノードによってキャッシュされることを認識しているコンテンツオブジェクトの名称を省略することにより、冗長なシグナリングを回避する。ここで留意すべきは、バックボーンに対してコンテンツデルタを送信することがＩＣＮアーキテクチャにおける「公開」メッセージと同等であるということである。
【００３６】
モバイルノード１１０及び１１２などのバックボーンクラウド１０２までの経路を有しないモバイルノードは、バックボーン１０２に対してそれらのローカル又は近隣情報を報告又は更新しない。これらのノードは、ネットワークノードがそれらの情報をそれらの直接近隣ノードに対して報告又は更新するデフォルトのピア・ツー・ピア・ルーティング・プロトコルをあてにしている。
【００３７】
ここで留意すべきは、従来のＭＡＮＥＴにおいて、ルーティング動作（ユニキャスト又はマルチキャスト）が非効率的であり得てネットワークのスケーラビリティを制限するピア・ツー・ピアの方法で実行されるということである。対照的に、図１に示される例において、バックボーン１０２は、モバイルノードのセットに対して集中型バックボーンサービスを提供する。バックボーンサービスは、最適なユニキャストルートを生成してマルチキャストグループ毎に共有マルチキャストツリーを計算するためにバックボーン１０２に対して報告されたノード情報を使用することにより、（モバイルノードを含む）ＭＡＮＥＴからのほとんどのルーティングのオーバーヘッドを軽減する。
【００３８】
いくつかの実施形態において、バックボーン１０２は、ＭＡＮＥＴ１００のモバイルノードから得られたリンク信頼性、キュー遅延、スケジューリング遅延及び残余帯域情報を組み込んだコスト関数を使用してネットワーク１００の重み付きグラフを作成して管理する。バックボーンサービスは、バックボーン１０２が（モバイルノードが移動した又はその状態を変更したときなど）ＭＡＮＥＴ１００の変化を示す情報を受信するたびに重み付きグラフを動的に更新することができる。コスト関数は、データトラフィックについての中継として２つのＭＡＮＥＴノード間のリンクを使用することによって発生することがある待ち時間の推定値を捕捉する。コスト関数は、基礎となるＭＡＣプロトコルに応じて、様々な方法で計算されることができる。例えば、Ｗｉ−Ｆｉネットワークについて、コスト関数は、ＭＡＣ層上のネットワークの競合のために経験するチャネル輻輳及びバックオフを考慮する。スケジューリングベースのＭＡＣについて、コスト関数は、送信タイムスロットと欠落パケットのコストとの間のスケジューリング遅延を考慮する。いくつかの実施形態において、バックボーンサービスは、以下のようにコスト関数を計算する。
【数１】
2015139219.tif 000003
式（１）において、ｑｕｅｕｅＴｉｍｅは、マイクロ秒単位で測定された近隣者のチャネルについての平均キュー遅延であり、ｐａｃｋｅｔＴｉｍｅは、同様にマイクロ秒単位における、チャネル上で１２８バイトのパケットを送信するための時間である。いくつかの実施形態において、ｐａｃｋｅｔＴｉｍｅは、１マイクロ秒未満ではないと仮定される。Ｐｅｎａｌｔｙは、残余帯域幅が０に接近したときに発生したコストペナルティである（すなわち、ノードは、その利用可能なスケジューリングされた通信時間の高い割合を使用する）。要素１／ｒｅｌｉａｂｉｌｉｔｙは、成功したパケット受信についての多数の送信試行を必要とする信頼性のない近隣者を不利にするようにリンクの信頼性が低減するのにともない増加する。いくつかの実施形態において、バックボーンサービスは、バックボーンサービスがリンクにわたる各ＭＡＮＥＴノードによって報告された情報に基づいてリンクの２つの一方向信頼性を把握することを考えると、双方向のリンク信頼性を使用してコストを計算することができる。バックボーンサービスは、重み付きグラフを使用することができ、その重み付けされた値は、ＭＡＮＥＴ１００に対するリアルタイムの変化を考慮しながらオンデマンドのルーティングを実行するために、コスト関数を使用して動的に更新される。
【００３９】
従来のＭＡＮＥＴは、大抵の場合、点対点及び多対多の双方の通信をサポートするために並列でのユニキャスト及びマルチキャストプロトコルの実行をあてにし、それゆえに、帯域幅の利用が非効率的である。さらに、既存のオンデマンドのユニキャスト又はマルチキャストプロトコルは、大抵の場合、リンク状態の更新、距離の更新、ルート要求又はマルチキャストの更新が頻繁に殺到するネットワークをもたらす。これらの問題を解決するため、本発明の実施形態は、ユニキャスト及びマルチキャストルーティングを実装するために使用されることができるインタレストベースのルーティングプロトコルを使用する。より具体的には、このインタレストベースのプロトコルは、個々の送信先ノード及びグループにおけるインタレストの有無によって活性化及び不活性化されるメッシュを確立し、そのようなメッシュにおけるインタレスト（エンクレーブ）領域内のシグナリングオーバーヘッドのほとんどを制限する。インタレストベースのプロトコルにおいて確立されるルートには永久ループがないことが示され、このプロトコルは、従来のマルチキャスト及びユニキャストのルーティングプロトコルよりもスケーラブルである。
【００４０】
インタレストベースのルーティングプロトコルは、各アクティブなマルチキャストグループについて（すなわち、アクティブな送信元及び受信機を有する各グループについて）及び少なくとも１つのアクティブな送信元を有する各ユニキャスト送信先についてのルーティングメッシュを確立して維持する。所定のユニキャスト又はマルチキャスト送信先についてアクティブになる第１の送信元は、（ＭＲの広がりの範囲を定義する）水平閾値までＭＡＮＥＴにわたってピアモバイルデバイスに対してフラッディングされたメッシュ要求（ＭＲ）に含まれるその第１のデータパケットを送信する。送信元によって表現されるインタレストが単一のデータパケットを超えてまたがる場合、ＭＲの意図する受信機（複数可）は、アクティブな送信元及び送信先にまたがるルーティングメッシュを確立して維持する。送信先がユニキャストである場合には、送信先は、単一のノードとすることができ、又は、送信先がマルチキャストである場合には、ノードの動的なセットとすることができる。
【００４１】
マルチキャストフローについて、マルチキャストグループの受信機は、グループについてのコアを選択するためにメッシュアナウンスメント（ＭＡ）を使用して分散選択を実行する。選択されると、コアノードは、グループについてのＭＡを生成し続ける受信機のみである。いくつかの実施形態において、バックボーンサービスが利用可能である場合、バックボーンサービスは、（例えば、モバイルノードからの更新情報を受信することに応答して）各マルチキャストグループについての共有マルチキャストツリーを先を見越して計算し、マルチキャストグループのメンバーに対してこの情報を送信し、したがって、それらは、常にマルチキャストグループのセットアップを有する。いくつかの実施形態において、バックボーンサービスは、重み付きネットワークグラフ内のコアの中心性に基づいて各マルチキャストツリーについてのツリーコアを動的に選択する。そのような選択は、ユニキャスト送信先のためには必要ない。選択されたマルチキャストコア又はユニキャスト送信先は、それに関心がある少なくとも１つのアクティブな送信元が存在する限り、シーケンス番号を単調増加してＭＡを送信し続ける。フロー内で検出されたアクティブな送信元が存在しない場合、フローの送信先又はコアは、有限時間後にＭＡの生成を停止し、バックボーン及び関連するモバイルノードにフローのメッシュに対応するルーティング情報を削除させる。情報を必要とするネットワークのそれらの部分への制御トラフィックを制限するために、ルーティングプロトコルは、確立されたメッシュについてのエンクレーブ（又は関心領域）を定義する。ここで留意すべきは、そのようなエンクレーブの確立がバックボーン及びモバイルノードの双方をともなうということである。エンクレーブは、ネットワークの接続された要素であり、送信先、関心があるアクティブな送信元、及び、それらを接続するために必要な中継ノードを含むことができる全ての受信機にまたがる。
【００４２】
様々なＭＡＣプロトコルがＳＤＭにおいて使用可能である。いくつかの実施形態において、ＳＤＭ内のノードは、ＧＣＭＡ（地理分類多元接続）から導出されたＭＡＣプロトコルを使用して互いに通信する。他の可能なプロトコルは、情報を広げるためにコンテキスト・アウェア・パケットの切り替えをあてにするコンテキスト・アウェア・プロトコルエンジン（ＣＡＰＥ）を含むことができる。いくつかの実施形態において、バックボーンは、ノードの送信及び干渉範囲とともにノードの地理空間座標に基づく決定論的な分散アルゴリズムを使用して、無衝突送信スケジュールを定義するためにＧＣＭＡを実装することができる。これらのアルゴリズムは、隠れ端末が存在するときであっても、正確な送信スケジュールを導出するために、各ノードがそのすぐ近隣者の（各ノードについてのＧＰＳデータから得ることができる）地理空間座標のみを把握することを必要とする。ＧＣＭＡにおける送信フレームは、ノードの送信及び干渉範囲を考慮して、多重アクセス干渉を回避するために必要な最小数のタイムスロットから構成されている。
【００４３】
ＭＡＮＥＴ内において、近隣ノードは、共通チャネルを共有することができる。チャネルは、送信フレームのセットに分割され、各ノードは、その「ｘ’及びｙ’」地理的座標及びそのスロット番号値に基づいて、フレーム内のスロットにマッピングされる。モバイルノードは、１つ以上のデータパケットを送信するためにタイムスロットを使用することができる。いくつかの実施形態において、モバイルノードは、例えば、バックボーンまでの経路に沿った次ホップノードをみつけるために、次ホップノードのセットを検出する方法のように「ハロー」パケットを送信するためにタイムスロットを使用することができる。
【００４４】
図２は、本発明の実施形態にかかる、ノードからその近隣者に対して送信された例示的な「ハロー」パケット２００のフレームフォーマットを図示する図を提示している。「ハロー」パケット２００は、いくつかがＧＣＭＡスケジューリングのために使用可能であるフィールドのセットを含むことができる。例えば、「ハロー」パケット２００は、シーケンス番号（ＳｅｑＮｏ）フィールド２０２と、ノードＩＤフィールド２０４と、Ｘ座標（Ｘ−ｃｏｏｒｄ）フィールド２０６と、Ｙ座標（Ｙ−ｃｏｏｒｄ）フィールド２０８とを含むことができる。さらに、「ハロー」パケット２００は、バックボーンまでの経路に沿って次ホップノードをみつけるために使用可能であるフィールドのセットを含むことができる。これらのフィールドのセットは、例えば、バックボーンに接続されたツリーのルートを示すルートＩＤフィールド２１０と、ノードにおけるシーケンス番号を示すｂｂＳｅｑＮｏフィールド２１２と、ノードからルートノードまでのホップ数を示すｂｂＨｏｐフィールド２１４とを含むことができる。
【００４５】
動作中において、各ノードは、その近隣ノードに対して「ハロー」パケットを定期的に（例えば、全てのＨｅｌｌｏＩｎｔｅｒｖａｌ秒後に）送信し、その「ハロー」パケットにおいて各近隣者によって報告されたデータフィールドとともにワンホップ近隣者のリストを維持する。
【００４６】
ＧＣＭＡベースのスケジューリングに加えて、いくつかの実施形態において、シグナリングトラフィック、エラスティックデータフロー及びリアルタイムフローを処理するために優先度ベースのキューイングシステムが使用される。ノードがタイムスロットにわたって送信することが許可されると、ノードは、例えば、厳格な優先度スケジューラを使用してそのローカル送信キューからパケットを選択することにより、タイムスロット間にできるだけ多くのパケットを送信する。いくつかの実施形態において、ノードのキューは、ＦＩＦＯ（先入れ先出し）であり、優先度ベースアルゴリズムを使用して提供される。
【００４７】
いくつかの実施形態において、モバイルノードは、複数のキューを含むことができる。例えば、ゲートウェイノードは、それぞれが異なるフローに対応する２つ以上のチャネルについてのタイムスロットを有することができる。ノードが最高優先度を有する複数の空でないキューを有する場合、ノードは、ラウンドロビン方式で、これらのキューの間で繰り返すことができる。例えば、ネットワークレイヤ・シグナリングパケットは、データキューにおいて待機しているデータパケットが後続する最高優先度（Ｐｃｔｒ）を有することができる。データキューは、エラスティック又はリアルタイムとすることができ、リアルタイムキューは、ジッタ及び待ち時間がエラスティックキューにとって重要でないことを考えると、エラスティックキューに与えられた優先度（Ｐｅｌａｓｔｉｃ）よりも高い優先度（ＰＲＴ）が割り当てられる。モバイルノードは、「ハロー」パケットが送信された最後の時間からＨｅｌｌｏＩｎｔｅｒｖａｌ秒よりも少ない時間が経過した場合には、最低優先度（ＰＨｅｌｌｏ‐）を有する「ハロー」パケットを送信することができる。しかしながら、ＨｅｌｌｏＩｎｔｅｒｖａｌ秒を超えて経過している場合には、モバイルノードは、近隣情報をリフレッシュすることができる。したがって、モバイルノードは、「ハロー」パケットの優先度を
【数２】
2015139219.tif 000004
に設定する。全体的に、ノードに割り当てられたタイムスロット間において、トラフィックの優先度の関係は、以下のとおりである。
【数３】
2015139219.tif 000005
【００４８】
上述したように、モバイルノードは、バックボーンに向かって有効な次ホップノードをみつけるために「ハロー」パケットに含まれる情報を使用することができる。これは、モバイルノードがその次ホップノードを介してバックボーンに対して更新情報を送信するのを可能とする。図１に示される例において、モバイルノード１０８は、バックボーンに対する次ホップノードとしてモバイルノード１０６を特定することができる。その結果、モバイルノード１０８は、バックボーン１０２に対して更新を転送して状態情報を記憶するモバイルノード１０６に対してそのバックボーンの更新を送信することができる。
【００４９】
いくつかの実施形態において、モバイルノードは、バックボーンまでの次ホップノードをみつけるために、距離ベクトルルーティングアルゴリズムの簡略版を使用する。より具体的には、モバイルノードは、各近隣ノードの距離を決定するために、そのワンホップ近隣者のそれぞれから受信した（図２に示されるような）シーケンス番号及び「ハロー」パケットのルート値を使用することができる。このアルゴリズムは、ネットワークにおける各ノードからバックボーンまでのルートにおけるループの自由を保証する。図３は、本発明の実施形態にかかる、次ホップノードを更新するための例示的な擬似コードを提示している。具体的には、モバイルノードが新たな「ハロー」メッセージを受信した場合、ノードは、図３に示されるアルゴリズムを実行し、その次ホップノードＩＤを更新する。
【００５０】
ここで留意すべきは、モバイルノードがピア・ツー・ピア通信に使用されるチャネルとは異なるチャネルを使用してバックボーンと通信するということである。いくつかの実施形態において、２つのチャネルを区別するためにＴＤＭＡ方式が使用される。バックボーンまでの経路を有する各ノードは、バックボーンに対して定期的な更新を送信する。図４は、本発明の実施形態にかかる、バックボーンに対してモバイルノードによって送信された例示的な更新メッセージを図示する図を提示している。
【００５１】
図４において、バックボーン更新メッセージ４００は、３つのデータ・ブロック、近隣メトリック（Ｎｂｒ  Ｍｅｔｒｉｃｓ）ブロック４０２と、サブスクライブ・マルチキャスト（ＭＣ）・グループブロック４０４と、コンテンツデルタブロック４０６とを含む。近隣メトリックブロック４０２は、（Ｎｂｒ  ＩＤとしてリスト化された）近隣ノードと、各近傍ノードについての（チャネル信頼性、残余帯域幅及びキュー待ち時間を含む）接続メトリックとのリストを含む。サブスクライブ・ＭＣ・グループブロック４０４は、ノードが加入したマルチキャストグループのマルチキャストグループＩＤをリスト化する。コンテンツデルタブロック４０６は、ノードがそのローカルキャッシュに最近記憶したコンテンツオブジェクトの名称をリスト化する。バックボーンサービスは、所定のフローについての送信先までの最良のルートを決定してＱｏＳサポートを提供するために、バックボーン更新メッセージ４００からの情報を使用することができる。バックボーンサービスはまた、信頼性、遅延及び帯域幅などのリンク状態に関する最新情報に基づいて、ＱｏＳベースのルーティングを実行することができる。例えば、経路の計算中、モバイルノードのＱｏＳ要件を満たしていないリンクは、非アクティブであると考えられる。
【００５２】
さらに、バックボーンサービスがネットワーク内のモバイルノードまでのルートを決定して送信した後に更新された近隣メトリックを受信した場合、バックボーンサービスは、更新されたメトリックに基づいてデータフロー経路を変更するためにモバイルノードに対して反応性更新を生成して送信することができる。例えば、モバイルノードが新たな近隣者を検出すると、モバイルノードは、バックボーンサービスがその後に更新されたルートを計算するために使用するその新たな近隣メトリックによってバックボーンを更新する。マルチキャストトラフィックについて、バックボーンサービスはまた、コアベースのマルチキャストツリーを維持するためにモバイルノードに対して先を見越した更新を送信する。
【００５３】
ユニキャストトラフィックについて、ノードが送信先に対して送信するパケットを有する場合、それは、バックボーンに対してＲｏｕｔｅＲｅｑｕｅｓｔパケットを送信する。いくつかの実施形態において、ＲｏｕｔｅＲｅｑｕｅｓｔパケットは、送信先のアドレスを含む、又は、コンテンツの一部に対する「Ｉｎｔｅｒｅｓｔ」を含む。バックボーンは、重み付きネットワークグラフに基づいて経路をオンデマンドで計算し、ＲｏｕｔｅＲｅｐｌｙパケットにおいて送信先ノードに対して最小コストパスを送信する。ここで留意すべきは、送信先までのホップ数が最も少ない経路をみつける代わりに、バックボーンは、ホップ間のリンク品質に基づいて最適な経路を選択することができるということである。図１に示される例において、ノード１０６と１０８との間のリンク品質が（信号干渉や物理的障壁のために）満足のいくものでない場合、バックボーン・クラウド１０２は、リンク１１４を介して直接ノード１０６からノード１０８までのトラフィックをルーティングする代わりに、ノード１１６を介してノード１０６からノード１０８までのトラフィックをルーティングすることができる。いくつかの実施形態において、バックボーンサービスは、経路を計算するためにダイクストラのアルゴリズムを使用する。
【００５４】
ＲｏｕｔｅＲｅｐｌｙパケットを受信すると、送信先ノードは、ルートを確立するためにＭｅｓｈＲｅｐｌｙパケットを送信する。しかしながら、送信先ノードは、ネットワークを介してＭｅｓｈＲｅｐｌｙパケットをフラッディングしない。むしろ、送信先ノードは、送信元ノードまでのルートを確立するためにＲｏｕｔｅＲｅｐｌｙパケット内の経路を使用してソースルーティングを実行することができる。
【００５５】
図５は、本発明の実施形態にかかる、ユニキャストルーティング処理を図示する図を提示している。図５に示される例において、モバイルノード５０８がノード５１８からコンテンツオブジェクト又はサービスを受けようとする場合には、モバイルノード５０８は、矢印５３２によって示されるようにバックボーン５０２に対してＲｏｕｔｅＲｅｑｕｅｓｔパケットを送信することができ、モバイルノード５１８から送信されたコンテンツ更新に基づいて送信先ノードとしてモバイルノード５１８を特定し、モバイルノード５０８と５１８との間の経路（例えば、ノード５０８−ノード５０６−ノード５１８）を計算する。そして、バックボーン５０２は、矢印５３４によって示されるようにモバイルノード５１８に対してＲｏｕｔｅＲｅｐｌｙパケットを送信する。ＲｏｕｔｅＲｅｐｌｙパケットは、計算された経路を含む。
【００５６】
ＲｏｕｔｅＲｅｐｌｙパケットを受信すると、モバイルノード５１８は、経路５３６によって示されるようにルートを確立するために受信した経路を介してモバイルノード５０８に対して１つ以上のＭｅｓｈＲｅｐｌｙパケットを返送する。ルートが確立されると、送信元（モバイルノード５０８）は、確立されたルートを介して送信先ノード（モバイルノード５１８）に対してパケットを送信することができる。送信元ノードがバックボーンに対して直接的又は間接的に接続されない場合、送信元ノードは、メッシュを活性化して、バックボーンサービスからの指示なしにピア・ツー・ピアのルーティングを実行するために、その近隣者に対してＭｅｓｈＲｅｑｕｅｓｔパケットを送信することができる。図５に示される一例において、モバイルノード５１０は、バックボーン５０２に対してＲｏｕｔｅＲｅｑｕｅｓｔパケットを送信する代わりに、（矢印５３８によって示されるように）その近隣ノード５１２に対してＭｅｓｈＲｅｑｕｅｓｔパケットを送信することにより、送信先に対してパケットを送信するためにメッシュを確立することができる。
【００５７】
ルートが送信先に対して確立された場合であっても、バックボーンサービスは、チャネル又はネットワーク負荷の変化が送信先までのより最適なパスを生成する場合にはモバイルノードに対して不当なＲｏｕｔｅＲｅｐｌｙパケットを送信し続けることができる。図５に示される例において、モバイルノード５０８がノード５１８の近くに移動してその次ホップ近隣者になる場合、バックボーン５０２は、ノード５１８に対して不当なＲｏｕｔｅＲｅｐｌｙパケットを送信することができ、新たな最小コストのルート（ノード５１８からノード５０８）が現在利用可能である旨をノード５１８に通知する。いくつかの実施形態において、バックボーンサービスは、モバイルノードのローカル又は近隣情報の急激な又は一時的な変化が頻繁且つ不要なルート更新を引き起こすのを回避するために、加重移動平均としてメトリックの変化を計算することができる。このようにして、フローは、短時間のインスタンスだけ安定したままである一過性の最適ルートを無視して、（ルート応答のシーケンスから決定されるような）所定期間にわたって安定なままで新たな及び／又は他の最適なルートに適合させる。
【００５８】
マルチキャストトラフィックについて、バックボーンサービスは、アクティブなトラフィックフローなしでコアベースのツリーを維持するために、マルチキャストグループのメンバーに対して先を見越した更新を送信する。各マルチキャストグループについて、バックボーンサービスは、グループの中で最も中心的なノードを選択し、マルチキャストグループのコアとして、この中心ノードを指定する。いくつかの実施形態において、バックボーンサービスは、コアを選択するために中心性アルゴリズムを使用する。グループのコアは、例えば、グループメンバー間での移動性のために変更することができる。バックボーンサービスは、ＭｕｌｔｉｃａｓｔＲｏｕｔｅＲｅｐｌｙパケットを送信することにより、コアまでの最良のルートによって更新時においてマルチキャストグループに属する全てのノードを先を見越して更新することができる。モバイルノードは、順番に、マルチキャストツリーを先を見越して維持するために、ネットワークを介してＭｅｓｈＡｃｔｉｖａｔｉｏｎパケットを送信する。
【００５９】
グループ内のモバイルノードがマルチキャストトラフィックを生成する場合、ノードは、マルチキャストツリーに沿ってデータを転送することができる。モバイルノードがバックボーンに接続されていない場合には、モバイルノードは、ＭＡＮＥＴマルチキャストルーティング機構へとそれらのルーティングアルゴリズムを戻し、送信元ノードがその近隣ノードに対してＭｅｓｈＲｅｑｕｅｓｔパケットを送信する。
【００６０】
図６は、本発明の実施形態にかかる例示的なマルチキャストシナリオを図示する図を提示している。図６において、モバイルノード６０８、６１６及び６１８は、マルチキャストグループに属している。モバイルノード６１６は、バックボーン６０２によって計算されたグループのコアである。動作中において、バックボーン６０２は、マルチキャストグループのメンバー（例えば、モバイルノード６０８及び６１８）に対して、コア（例えば、ノード６１６）までの最小コストの経路を示すＭｕｌｔｉｃａｓｔＲｏｕｔｅＲｅｐｌｙパケットを送信する。ＭｕｌｔｉｃａｓｔＲｏｕｔｅＲｅｐｌｙパケットを受信すると、モバイルノード６０８及び６１８は、マルチキャストツリーを維持するために定期的にＭｅｓｈＡｃｔｉｖａｔｉｏｎパケットを送信する。図６から、モバイルノード６０６は、マルチキャストグループのメンバーではないものの、ノード６０６は、マルチキャストツリーのメンバーになることができ、ツリーの他のメンバーによって生成されたデータパケットを転送することができることがわかる。
【００６１】
図７Ａは、本発明の実施形態にかかる、送信元モバイルノードによって実行される例示的なルーティング処理を示すフローチャートを提示している。動作中において、モバイルネットワークノードは、ルーティング要求を生成する（動作７０２）。そして、ノード（又は送信元ノード）は、バックボーンに対する接続（シングルホップ又はマルチホップのいずれか）をみつけることができるかどうかを判定する（動作７０４）。いくつかの実施形態において、距離ベクトルルーティングアルゴリズムは、有効な次ホップノードをみつけるために使用される。ノードがバックボーンに対する接続を検出することができない場合、ノードは、その近隣ノードに対してメッシュ要求を送信する（動作７０６）。いくつかの実施形態において、メッシュ要求は、水平閾値までフラッディングされる。さらなる実施形態において、送信元ノードは、メッシュ要求に含まれる最初のデータパケットを送信することができる。対象とする受信機は、送信元ノード及び送信先ノードにわたるルーティングメッシュを確立する（動作７０８）。確立されたメッシュは、パケットの送信を可能とする（動作７１０）。一方、送信元ノードが有効な次ホップノードを特定することによってバックボーンに対する接続をみつけた場合には、ソースノードは、特定された次ホップノードを介してバックボーンに対してルート要求パケットを送信する（動作７１２）。送信先アドレス又は要求されたコンテンツの名称を特定することができる要求に基づいて、バックボーンは、送信先までの経路を計算する。いくつかの実施形態において、バックボーンは、送信先までの最小コストの経路をみつけるために、ネットワークの重み付きグラフを使用する。重み付きグラフは、（チャネル信頼性、残余帯域幅及びキュー待ち時間などの）各ノードについての近隣情報を含むことができる。
【００６２】
送信元ノードは、バックボーンから計算された経路を受信することができる（動作７１４）。いくつかの実施形態において、計算された経路は、ＲｏｕｔｅＲｅｐｌｙパケットに含まれている。そして、送信元ノードは、どのノードが計算された経路を含むＲｏｕｔｅＲｅｐｌｙパケットを送信するかを決定する（動作７１６）。経路がピア・ノードから受信された場合、送信元ノードは、ピア・ノードに対してパケットを返送する（動作７１８）。経路がバックボーンから受信された場合、送信元ノードは、送信先ノードに対してパケットをソースルートするための受信した経路を使用することによってパケットを送信する（動作７２０）。
【００６３】
図７Ｂは、本発明の実施形態にかかる、バックボーンにおけるコントローラノードによって実行される例示的なルーティング処理を図示するフローチャートを提示している。動作中において、コントローラノードは、送信元モバイルノードからルート要求メッセージを受信し（動作７２２）、送信元ノードと送信先ノードとの間の最適経路を計算する（動作７２４）。いくつかの実施形態において、最適経路は、重み付きネットワークグラフに基づいて計算された最小コスト経路である。その後、コントローラノードは、少なくとも送信先ノードに対して経路を送信する（動作７２６）。
【００６４】
図７Ｃは、本発明の実施形態にかかる、バックボーンによって実行される例示的なルートの更新処理を図示するフローチャートを提示している。動作中において、バックボーンは、モバイルノードから更新されたネットワーク情報を受信し（動作７３２）、更新されたネットワーク情報に基づいてネットワークグラフを更新する（動作７３４）。そして、バックボーンは、更新されたネットワークグラフに基づいて、送信元ノードと送信先ノードとの間で最適経路が変更されたか否かを判定する（動作７３６）。そうである場合、バックボーンは、送信元ノードと送信先ノードとの間の更新された最適経路を計算し（動作７３８）、少なくとも送信先ノードに対して更新された新たな経路を送信する（動作７４０）。
【００６５】
ここで留意すべきは、図７Ａ〜図７Ｃがユニキャストルーティングの例であるということである。送信元ノードがバックボーンサービスにアクセスできないときにルーティングがＭＡＮＥＴルーティングに後退する場合には、マルチキャストルーティングは、同様のものとすることができる。
【００６６】
ＩＣＮにおいて、ノードは、コンテンツ又はサービスの名称に基づいて、コンテンツの一部又はサービスの種類を要求することができる。「インタレスト」パケットを受信すると、コンテンツホルダは、次に、「インタレスト」パケットの経路を横断するコンテンツデータパケットを送信することができる。ＳＤＭはまた、同様のコンテンツベース又はサービス指向のルーティングを容易とすることができる。いくつかの実施形態において、ＳＤＭ内のノードは、コンテンツ又は計算サービスを含むことができる名称が付されたサービスを提供することができる。ＩＣＮの名称は、大抵の場合、場所に依存せず、コンテンツオブジェクト又はサービスなどのリソースオブジェクトを固有に識別する。データ転送デバイスは、リソースオブジェクトについてのネットワークアドレス又は物理的位置にかかわらず、リソースオブジェクトを提供するネットワークノードに向けてパケットを転送するために名称又は名称接頭辞を使用することができる。
【００６７】
いくつかの実施形態において、名称は、階層的構造化可変長識別子（ＨＳＶＬＩ）とすることができる。ＨＳＶＬＩは、様々な方法で構成されることができるいくつかの階層的要素に分割されることができる。例えば、個々の名称要素ｐａｒｃ、ｈｏｍｅ、ｃｃｎ及びｔｅｓｔ．ｔｘｔは、名称「／ｐａｒｃ／ｈｏｍｅ／ｃｃｎ／ｔｅｓｔ．ｔｘｔ」を形成するために、左指向の接頭辞を主とする方法で構造化されることができる。それゆえに、名称「／ｐａｒｃ／ｈｏｍｅ／ｃｃｎ」は、「／ｐａｒｃ／ｈｏｍｅ／ｃｃｎ／ｔｅｓｔ．ｔｘｔ」の「親」又は「接頭辞」とすることができる。追加の要素は、共同文書などのコンテンツ項目の異なるバージョンを区別するために使用可能である。
【００６８】
いくつかの実施形態において、名称は、コンテンツ／サービスオブジェクトのデータ（例えば、チェックサム値）及び／又はコンテンツ／サービスオブジェクトの名称の要素から導出されたハッシュ値などの非階層的識別子を含むことができる。名称はまた、フラットラベルとすることができる。以下では、「名称」は、階層的名称又は名称接頭辞、フラット名称、固定長名称、任意長名称又はラベル（例えば、マルチプロトコル・ラベル・スイッチング（ＭＰＬＳ）ラベル）などの名称−データネットワークにおけるデータの一部についての任意の名称を指すために使用される。
【００６９】
ＳＤＭにおいて、ネットワーク内の各ノードは、バックボーンによるサービス又はコンテンツ部分を登録する。いくつかの実施形態において、各ノードは、バックボーンに対してＢＢｕｐｄａｔｅ（バックボーン更新）パケットを定期的に送信する。ＢＢｕｐｄａｔｅパケットは、図４に示されたものと同様の形式を有することができる。いくつかの実施形態において、ノードは、冗長なシグナリングを回避するために、バックボーンサービスに対してノードにおいて利用可能なコンテンツ又はサービス名称の変化を送信する。いくつかの実施形態において、いくつかのノードには、所定のコンテンツ部分又はサービスが事前追加されることができ、バックボーンには、それらのコンテンツ部分又はサービスに関連する情報が事前追加されている。そのようなシナリオにおいて、ノードは、バックボーンによるそれらのコンテンツ又はサービス名称を再登録する必要はない。しかしながら、コンテンツ又はサービスがノードにおいて更新された場合には、ノードは、ＢＢｕｐｄａｔｅパケットを介してバックボーンに対して更新された情報を送信することができる。
【００７０】
ノードは、バックボーンに対してＣｏｎｔｅｎｔＲｅｑｕｅｓｔパケットを送信することにより、所定のコンテンツ部分又はサービスを要求することができる。ＣｏｎｔｅｎｔＲｅｑｕｅｓｔパケットを受信すると、バックボーンは、名称に基づいて、このようなコンテンツ部分又はサービスを提供することが可能なノードのグループを特定し、要求者までの最小コスト経路を有するグループ内のノードを選択する。いくつかの実施形態において、バックボーンは、要求者までの最低コストの経路を有するノードをみつけるためにダイクストラのアルゴリズムを実行する。その後、バックボーンは、パケットが選択されたノードまでの経路を含むように、要求者に対してＣｏｎｔｅｎｔＲｅｐｌｙパケットを発行することができる。ＣｏｎｔｅｎｔＲｅｐｌｙパケットを受信すると、要求者は、選択されたノードまでのルートを確立するために、ＣｏｎｔｅｎｔＲｅｐｌｙパケットにおいて示された経路に基づいて、選択されたノードに対してソースルートＭｅｓｈＲｅｐｌｙパケットを発行する。ルートが確立されると、選択されたノードは、要求者に対してサービス又はコンテンツを提供することができる。
【００７１】
図８は、本発明の実施形態にかかる例示的なサービス指向ルーティングシナリオを図示する図を提示している。図８において、モバイルノード８１８は、バックボーン８０２におけるコントローラノード（例えば、コントローラノード８０４）に対してそのような名称を示すＣｏｎｔｅｎｔＲｅｑｕｅｓｔパケットを送信することにより、サービス「ｐａｒｃ／ｈｏｍｅ／ｃｃｎ／ｆｏｏ」を要求している。その維持されたバックボーン更新レコードに基づいて、コントローラノード８０４は、モバイルノード８２２、８２４及び８０８を特定し、サービス「ｐａｒｃ／ｈｏｍｅ／ｃｃｎ／ｆｏｏ」を提供することができる。さらに、コントローラノード８０４は、そのようなサービスを提供するために最も近いノードとしてノード８０８を選択し、ノード８０８が要求されたサービスを提供することができるであろうことを示すＣｏｎｔｅｎｔＲｅｐｌｙパケットをモバイルノード８１８に対して送信する。そして、モバイルノード８１８は、ルートを確立するために、ノード８０６を介してノード８０８に対してソースルートＭｅｓｈＲｅｐｌｙパケットを送信する。ルートが確立されると、ノード８０８は、矢印８３２によって示されるように要求されたサービスを提供するか又は要求者ノード８１８に対して要求されたコンテンツを送信することができる。あるいは、サービスを提供するために最も近いノード８０８を選択した後、コントローラノード８０４は、選択されたノード８０８に対して、要求されたサービス及び要求者ノード８１８までの経路を示すＣｏｎｔｅｎｔＲｅｐｌｙパケットを直接送信することができる。それと引き換えに、選択されたノード８０８は、提供された経路に基づいて要求者ノード８１８とのルートを確立し、要求されたサービスを提供する。
【００７２】
バックボーンクラウドは、異なるピア・ツー・ピア・チャネル上で動作する複数のＭＡＮＥＴを制御することができ、相互ＭＡＮＥＴ通信は、ＭＡＮＥＴ毎に１つ以上のゲートウェイノードを活性化することによって達成されることができる。各ゲートウェイノードは、予約されたタイムスロット（ＴＤＭＡの場合）又は通信時間（Ｗｉ−Ｆｉの場合）において外部のＭＡＮＥＴと通信するように構成されることができる。
【００７３】
図９は、本発明の１つの実施形態にかかる相互ＭＡＮＥＴ通信についての例示的なシナリオを図示する図を提示している。図９において、バックボーンクラウド９０２は、ＭＡＮＥＴ９３２及びＭＡＮＥＴ９３４などの、異なるピア・ツー・ピア・チャネル上でそれぞれ動作する複数のＭＡＮＥＴを制御する。いくつかの実施形態において、バックボーンクラウドは、それらの地理的位置に基づいて、ノードのグループにピア・ツー・ピア・チャネルを割り当てることができる。グループ内のノードは、割り当てられたピア・ツー・ピア・チャネル上で互いに通信し、ＭＡＮＥＴを形成する。用語「チャネル」は、以下では、任意の通信チャネルを指す。伝送プロトコルに応じて、チャネルは、タイムスロット（ＴＤＭＡの場合）、周波数チャネル（ＦＤＭＡの場合）又は通信時間（Ｗｉ−Ｆｉの場合）とすることができる。各ノードは、ピア・ツー・ピア・チャネルとは異なるチャネル上でバックボーンに対して更新を送信することができる。
【００７４】
図９に示される例において、ＭＡＮＥＴ９３２は、モバイルノード９２２及び９２４を含み、ＭＡＮＥＴ９３４は、モバイルノード９０６、９０８、９１６及び９１８を含む。動作中において、バックボーン９０２は、ゲートウェイノードとして各ＭＡＮＥＴにおける少なくとも１つのノードを割り当てることができ、ゲートウェイノードが外部のＭＡＮＥＴに対してアウトバウンドトラフィックを中継するために外部のＭＡＮＥＴ内のノードと通信できるようにゲートウェイノードをスケジューリングする。
【００７５】
例えば、バックボーン９０２は、ゲートウェイノードとして動作するようにＭＡＮＥＴ９３２内のノード９２４をアクティブにすることができ、ノード９２４がＭＡＮＥＴ９３４に割り当てられたピア・ツー・ピア・チャネル上でＭＡＮＥＴ９３４におけるピア・ツー・ピア通信に参加するのを可能とするようにその送信をスケジューリングする。例えば、バックボーン９０２は、ノード９２４がそれらの予約されたタイムスロットにおいてＭＡＮＥＴ９３４内のノードと通信することができるのを確実にするために、ゲートウェイノード９２４上に所定のタイムスロットを予約することができる。その間、ＭＡＮＥＴ９３２においては、誰もそれらの予約されたタイムスロット上でノード９２４と通信しない。同様に、Ｗｉ−Ｆｉが使用される場合には、ゲートウェイノード９２４は、ノード９２４がＭＡＮＥＴ９３４内のノードとのピア・ツー・ピア通信に参加しながら現在スリープしているＭＡＮＥＴ９３２内のそのピア・ノード（ノード９２２）に示すことができる。
【００７６】
バックボーン９０２はまた、ＭＡＮＥＴ９３４についてのゲートウェイノードとしてモバイルノード９０６を活性化することができ、ノード９０６が所定の予約されたタイムスロット又は通信時間においてＭＡＮＥＴ９３２におけるピア・ツー・ピア通信に参加するのを可能とするように、その送信をスケジューリングする。ゲートウェイノードの確立は、異なるＭＡＮＥＴ内のノードが互いに通信するのを可能とする。さらに、相互ＭＡＮＥＴ通信についてのゲートウェイノードについてタイムスロット又は通信時間を排他的に予約することは、競合のない相互ＭＡＮＥＴルーティングを可能とするのみである。
【００７７】
図９に示される例において、（ＭＡＮＥＴ９３４内にある）ノード９１６が（ＭＡＮＥＴ９３２内にある）ノード９２２に対してパケットを送信したい場合には、バックボーン９０２に対してルート要求を送信する。最適経路を計算しながら、バックボーン９０２は、これらの２つのノードが２つの異なるＭＡＮＥＴに属している旨を通知するとともに、ノード９０６及び９２４がＭＡＮＥＴについてのゲートウェイノードである旨を通知する。そして、バックボーン９０２は、それに応じてネットワーク経路を計算する。計算された経路は、ノード９０６まで、ノード９２２までのノード９１６を含むことができる。したがって、ノード９１６は、相互ＭＡＮＥＴ通信について予約されたタイムスロット間にノード９２２に対してパケットを転送するゲートウェイノード９０６に対してパケットを送信する。あるいは、計算された経路は、ノード９２４まで、ノード９２２までのノード９１６を含むことができる。したがって、ノード９１６は、ＭＡＮＥＴ９３４によって通信するためにノード９２４について予約されたタイムスロット間に（そのようなデータリンクが利用可能である場合には）ゲートウェイノード９２４に対してパケットを送信することができる。そして、ゲートウェイノード９２４は、ピア・ノード９２２に対してパケットを転送する。
【００７８】
図１０は、本発明の実施形態にかかるコントローラノードの例示的なアーキテクチャを図示する図を提示している。コントローラノード１０００は、バックボーン更新受信機構１００２と、データベース１００４と、ネットワークグラフ生成部１００６と、ネットワークグラフ１００８と、ルート要求受信機構１０１０と、経路計算／マルチキャストコア選択部１０１２と、出力機構１０１４とを含む。
【００７９】
バックボーン更新受信機構１００２は、コントローラノード（又はバックボーンクラウド内の他のコントローラノード）に関連付けられているＭＡＮＥＴノードからのバックボーン更新の受信を担当する。いくつかの実施形態において、バックボーン更新は、各ノードにおいて保持された、近隣メトリック、ノードが加入したマルチキャストグループのリスト及びコンテンツデルタを含む。受信したバックボーン更新は、データベース１００４に記憶される。ネットワークグラフ生成部１００６は、受信した近隣メトリックに基づいて、重み付きネットワークグラフ１００８の生成を担当する。いくつかの実施形態において、ネットワークグラフ生成部１００６は、受信したバックボーン更新に基づいて、重み付きグラフを動的に更新する。
【００８０】
ルート要求受信機構１０１０は、関連するＭＡＮＥＴノードからのルート要求の受信を担当する。受信した要求は、その後、経路計算／マルチキャストコア選択部１０１２に対して送信される。ユニキャストトラフィックの場合、経路計算部１０１２は、重み付きグラフ１００８に基づいて、送信先までの最小コスト経路を計算する。ここで留意すべきは、ルート要求がコンテンツ又はサービスの一部についての名称を含む場合には、経路計算部１０１２は、データベース１００４に記憶された（モバイルノードによって報告されたコンテンツデルタ更新を含むことができる）情報及び重み付きグラフ１００８に基づいて、最も近いコンテンツキャッシュを最初に特定し、そのコンテンツキャッシュまでの最小コスト経路を計算する。マルチキャストトラフィックの場合、マルチキャストコア選択部１０１２は、重み付きグラフ１００８に基づいて、マルチキャストコアを選択し、マルチキャストグループ内の各ノードについてのコアまでの最良のルートを計算する。経路が計算されると、出力機構１０１４は、送信先ノード（ユニキャストトラフィックの場合）又はマルチキャストグループ内のノード（マルチキャストトラフィックの場合）に対して、計算された経路を送信する。
【００８１】
図１１は、本発明の実施形態にかかる、ＭＡＮＥＴノードの例示的なアーキテクチャを図示する図を提示している。ＭＡＮＥＴノード１１００は、次ホップファインダ１１０２と、バックボーン更新機構１１０４と、ピア・ツー・ピア更新機構１１０６と、経路要求送信機構１１０８と、経路受信機構１１１０と、パケット送信機構１１１２とを含む。
【００８２】
次ホップファインダ１１０２は、バックボーンまでの次ホップノードの発見を担当する。いくつかの実施形態において、距離ベクトルルーティングアルゴリズムは、バックボーンまでの次ホップノードをみつけるために、次ホップファインダ１１０２によって使用される。バックボーンまでの次ホップノードがみつかった場合、バックボーン更新機構１１０４は、その後にそのような更新をバックボーンに対して転送する特定された次ホップノードに対してバックボーン更新を送信する。それ以外の場合は、ピア・ツー・ピア更新機構１１０６は、他のワンホップ近隣者を有するＭＡＮＥＴノード１１００の各種状態を更新する。
【００８３】
ＭＡＮＥＴノード１１００が送信先に対してパケットを送信しようとする場合、経路要求送信機構１１０８は、バックボーンまでの次ホップノードが利用可能である場合、バックボーンに対してルート要求メッセージを送信する。それ以外の場合は、ルート要求は、所定ホライゾン内のピア・ノードに対してフラッディングされる。経路受信機構１１１０は、バックボーン又はバックボーンに届かないときには他のピア・ノードのいずれかからの経路情報の受信を担当する。パケット送信機構１１１２は、受信した経路に基づいて、送信先に向けてのパケットの送信を担当する。
【００８４】
図１２は、本発明の１つの実施形態にかかる、ソフトウェア・ディファインド・ＭＡＮＥＴ（ＳＤＭ）においてルーティングするための例示的なコンピュータシステムを図示している。１つの実施形態において、コンピュータ及び通信システム１２００は、プロセッサ１２０２と、メモリ１２０４と、記憶装置１２０６とを含む。記憶装置１２０６は、ＳＤＭルーティングアプリケーション１２０８とともに、アプリケーション１２１０及び１２１２などの他のアプリケーションを記憶する。動作中において、ＳＤＭルーティングアプリケーション１２０８は、記憶装置１２０６からメモリ１２０４にロードされた後、プロセッサ１２０２によって実行される。プログラムの実行時に、プロセッサ１２０２は、上述した機能を実行する。コンピュータ及び通信システム１２００は、任意のディスプレイ１２１４、キーボード１２１６及びポインティングデバイス１２１８に結合されている。
【００８５】
この詳細な説明に記載されたデータ構造及びコードは、典型的には、コンピュータシステムによって使用するためのコード及び／又はデータを記憶することができる任意の装置又は媒体とすることができるコンピュータ読み取り可能な記憶媒体に記憶される。コンピュータ読み取り可能な記憶媒体は、これらに限定されるものではないが、揮発性メモリ、不揮発性メモリ、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（ディジタル多用途ディスク若しくはディジタルビデオディスク）などの磁気及び光学記憶装置、又は、現在知られている若しくは後に開発されるコンピュータ読み取り可能な媒体を記憶することができる他の媒体を含む。
【００８６】
詳細な説明のセクションに記載された方法及びプロセスは、上述したようなコンピュータ読み取り可能な記憶媒体に記憶されることができるコード及び／又はデータとして具現化されることができる。コンピュータシステムがコンピュータ読み取り可能な記憶媒体に記憶されたコード及び／又はデータを読み出して実行した場合、コンピュータシステムは、データ構造及びコードとして具体化されてコンピュータ読み取り可能な記憶媒体に記憶された方法及びプロセスを実行する。
【００８７】
さらにまた、上述した方法及びプロセスは、ハードウェアモジュールに含めることができる。例えば、ハードウェアモジュールは、これらに限定されるものではないが、特定用途向け集積回路（ＡＳＩＣ）チップ、フィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ）、及び、現在知られている若しくは後に開発される他のプログラマブルロジックデバイスを含むことができる。ハードウェアモジュールが起動された場合、ハードウェアモジュールは、ハードウェアモジュール内に含まれる方法及びプロセスを実行する。
【００８８】
本発明の実施形態の上述した説明は、例示及び説明のみを目的として提示されている。それらは、網羅的であること又は開示された形態に本発明を限定することを意図するものではない。したがって、多くの変更例及び変形例が当業者には明らかであろう。さらに、上記開示は、本発明を限定するものではない。本発明の範囲は、添付された特許請求の範囲によって定義される。
【図１】
2015139219.tif 000006
【図２】
2015139219.tif 000007
【図３】
2015139219.tif 000008
【図４】
2015139219.tif 000009
【図５】
2015139219.tif 000010
【図６】
2015139219.tif 000011
【図７Ａ】
2015139219.tif 000012
【図７Ｂ】
2015139219.tif 000013
【図７Ｃ】
2015139219.tif 000014
【図８】
2015139219.tif 000015
【図９】
2015139219.tif 000016
【図１０】
2015139219.tif 000017
【図１１】
2015139219.tif 000018
【図１２】
2015139219.tif 000019