JP6485671B2 - マルチホップ異種無線ネットワークにおけるリソースアウェアマルチタスクルーティング - Google Patents

Description

本発明は、包括的には、無線ネットワークにおいてパケットをルーティングすることに関し、特に、異種のリソース及び能力を有するノードを備えるマルチホップ無線ネットワークにおいてパケットをルーティングすることに関する。

無線ネットワークは、当該ネットワークのノードのリソース及び能力に基づいて同種ネットワーク及び異種ネットワークに分類することができる。従来の無線センサーネットワーク等の同種ネットワークでは、全てのノードは、同じリソース及び能力を有する。他方、無線のモノのインターネット（ＩｏＴ）ネットワーク等の異種無線ネットワークでは、ノードは、異なるリソース及び能力を有する。幾つかのノードは、メモリ、記憶装置、プロセス電力、エネルギー供給、及び通信能力等のより多くのリソースを有する。他のノードは、限られたリソース及び能力を有する。その結果、ノードの中には、より多くの機能を実行することができるものもあれば、限られた機能しか実行することができないものもある。

従来の階層型ルーティング方法は、同種無線ネットワーク向けに設計され、ノードが異種であること及びアプリケーションの要件を考慮していない。例えば、特許文献１「methods and apparatus for hierarchical routing in communication networks」は、通信ネットワークにおけるクラスターの境界ノード対を接続する複数の制約付き加重パス（constrained weighted path）を求める。各制約付き加重パスは、それぞれの帯域幅及びそれぞれの重みを有する。制約付き加重パスの選択は、帯域幅閾値に基づいている。この特許文献１は、クラスターをどのように形成するのか及びクラスターを形成するのにどのようなメトリックが用いられるのかを検討していない。特許文献１は、選択されたノードが、他のクラスターとの接続を行うのに十分なリソースを有するか否かを考慮していない。したがって、同種ネットワークしか考慮されていない。

特許文献２「method and apparatus for hierarchical routing in multiprocessor mesh-based systems」は、メッシュシステムにおける階層型ルーティングの方法及び装置を記載している。この方法は、ノードのメッシュネットワークを複数の方形領域に分割し、これらの複数の方形領域のソース領域からデスティネーション領域への分割経路を求め、或る方形領域内のソースノードから同じ方形領域内のデスティネーションノードへの領域経路を提供する。この方法は、これらの分割経路及び領域経路を用いて、ソース領域内のソースノードからデスティネーション領域内のデスティネーションノードにパケットをルーティングすることも含むことができる。しかしながら、この方法も、同種ネットワーク向けに設計されており、ノードリソース、ルーティングメトリック、及び目的関数を考慮しておらず、到達可能性しか考慮していない。

低電力高損失ネットワーク用ＩＰｖ６ルーティングプロトコル（ＲＰＬ）は、インターネットエンジニアリングタスクフォース（ＩＥＴＦ）によって開発されたルーティングプロトコルである。ＲＰＬは、ネットワークのノードを、デスティネーション指向有向非巡回グラフ（ＤＯＤＡＧ）と呼ばれるツリー状のトポロジーに編成する。所定のメモリ閾値に基づいて、ＲＰＬは、４つの動作モード（ＭＯＰ）、すなわち、ＭＯＰ＝０、ＭＯＰ＝１、ＭＯＰ＝２及びＭＯＰ＝３を定義する。しかしながら、ＲＰＬは、ネットワーク内の全てのルーターノードが同じＭＯＰを有することができる、すなわち、全てのルーターノードがシンクノードのＭＯＰと同じＭＯＰを有することができることを要件とする。或るノードが、シンクノードのＭＯＰと異なるＭＯＰを有する場合、そのノードは、リーフノードとしてネットワークに参加することしかできず、したがって、ネットワークを拡張することができない。その結果、ＲＰＬは、物理的に接続されたネットワークを分割する可能性がある。加えて、ＲＰＬは、ネットワーク内では、単一の目的関数及び同じルーティングメトリックを要件とする。その結果、ＲＰＬも、同種ネットワーク向けに設計されている。

米国特許第８，７７３，９９２号明細書 米国特許出願公開第２００９／０２７４１５７号明細書

したがって、そのルーティング機能を、ノードの異なるリソース及び能力に基づいて適応させるリソースアウェアルーティング方法を提供することが望まれている。

本発明の幾つかの実施の形態は、マルチホップ異種無線ネットワークでは、異なるアプリケーション要件及びリソース要件に基づいてネットワークトポロジーを構築することができるという認識に基づいている。例えば、目的関数とルーティングメトリックとの適切なセットを選択して、トポロジーのマルチ階層及びマルチクラスターを構築するように、異種の目的関数及びルーティングメトリックがノードに提供されるべきである。

本発明の幾つかの実施の形態は、マルチホップ無線ネットワークでは、異なるリソースを有するノードは、当該ノードによって用いられるルーティングのタイプを規定する異なる動作モード（ＭＯＰ）を有することができるという認識に基づいている。例えば、ＭＯＰは、一方向ルーティングであるのか又は双方向ルーティングであるのか、テーブルルーティングであるのか又はソースルーティングであるのかを規定することができる。例えば、ノードは、当該ノードがもはやルーティングするリソースを有しないことを他のノードに知らせるべきである。

本発明の幾つかの実施の形態は、ノードが、パケットをバッファリングするのに用いられるバッファーセクションと、ネットワークトポロジーを作成及び維持するのに必要とされる情報を記憶するのに用いられるルーティングセクションとを含む異なるセクションにメモリを分割することができるという認識に基づいている。例えば、ルーティングセクションには、ネットワーク識別子、近傍情報及びルーティングテーブルエントリーが記憶される。

本発明の幾つかの実施の形態は、ノードが、配分ルーティングメモリと、必要ルーティングメモリと、サブネットワークサイズのサイズ及び近傍ノードのＭＯＰ変化等の検知されたネットワーク状態と、ノードの利用可能メモリ、ノードの処理電力、ノードの利用可能エネルギー量、及びノードの通信能力のうちの１つ又は組み合わせ等の利用可能リソースの変化とに応じて、そのＭＯＰを更新することができるという認識に基づいている。ＭＯＰの新たなセットが、異なるＭＯＰがネットワークにおけるノードの異なるルーティングタイプに対応することができるように定義され、ノードがより多くのルーティング機能を実行することができる場合、ＭＯＰはより昇格したものとなる。そのようにして、ノードは、そのＭＯＰをルーティングのタイプの表示として他のノードにシグナリングすることができる。例えば、ノードは、ＭＯＰを用いて、当該ノードがルーティングを行わないことを示すことができる。

本発明の幾つかの実施の形態では、ノードは、他のノードのＭＯＰによって示されるような当該他のノードのルーティングタイプと、異なるルーティング目的関数及び異なるルーティングメトリックとを考慮してそれらのルーティングを実行する。また、幾つかの実施の形態は、Ｋホップ近傍ノードの目的関数、ルーティングメトリック及びルーティングプリファレンスを容易にするために階層型ネットワークトポロジーを構築する。

したがって、本発明の幾つかの実施の形態は、異なるＭＯＰを有するノードを備える異種ネットワークを有するとともに、ノードの動作の変化に応じて少なくとも１つのノードのＭＯＰを変更することによって、ネットワークの状態の変化にルーティング方法を適応させる。

したがって、１つの実施の形態は、第１のシンクノードを有する第１のサブネットワークと第２のシンクノードを有する第２のサブネットワークとを含むサブネットワークのセットに分割されたマルチホップ異種無線ネットワークにおいてパケットをルーティングする方法であって、ノードが、前記第１のサブネットワークの少なくとも一部と、前記第２のサブネットワークの少なくとも一部とを形成する、方法を開示する。該方法のステップは、前記ノードのプロセッサを用いて実行される。

前記方法は、
前記ノードにおける配分ルーティングメモリ（ＡＲＭ）と、前記ノードの残りの予想ルーティング寿命（ＥＲＬ）との関数として前記ノードの利用可能ルーティングリソースを求めることと、
前記ノードによってサブネットワークに用いられるルーティングプロトコルと、前記サブネットワークにおける前記ノードの論理ロケーションと、前記ノードを通る前記サブネットワークにおけるデータトラフィックとの関数として、前記ノードの少なくとも１つの必要ルーティングリソースを求めることであって、該必要ルーティングリソースを該求めることは、前記第１のサブネットワークのための前記ノードの第１の必要ルーティングリソースを求めることと、前記第２のサブネットワークのための前記ノードの第２の必要ルーティングリソースを求めることと、を含み、前記第１の必要ルーティングリソースは、記第２の必要ルーティングリソースと異なることと、
前記利用可能ルーティングリソース及び前記第１の必要ルーティングリソースを用いて、前記第１のサブネットワークにおける前記ノードの前記ルーティングのタイプを指定する第１の動作モード（ＭＯＰ）を求めることと、
前記利用可能ルーティングリソース及び前記第２の必要ルーティングリソースを用いて、前記第２のサブネットワークにおける前記ノードの前記ルーティングのタイプを指定する第２のＭＯＰを求めることであって、前記第１のＭＯＰは該第２のＭＯＰと異なることと、
前記第１のＭＯＰに従って前記第１のサブネットワークにおいてパケットをルーティングするとともに、前記第２のＭＯＰに従って前記第２のサブネットワークにおいてパケットをルーティングすることと、
を含む。

別の実施の形態は、異なる計算リソース及びエネルギーリソースを有する複数のノードを備えるマルチホップ無線ネットワークであって、該ネットワークは、目的関数とルーティングメトリックとの固有の組み合わせを有する複数のサブネットワークに分割され、少なくとも１つのノードは、複数のサブネットワークに参加し、異なるサブネットワークの異なるタイプのルーティングを指定する異なる動作モード（ＭＯＰ）に従って動作する、ネットワークを開示する。

更に別の実施の形態は、
パケットを送受信する送受信機と、
前記パケット、経路エントリー、親子エントリー、Ｋホップ近傍ルーティングプリファレンスの少なくとも一部分を記憶するメモリと、
複数のサブネットワークの目的関数とルーティングメトリックとの組み合わせに基づいて前記サブネットワークに参加し、異なるサブネットワークの異なるタイプのルーティングを指定する異なる動作モード（ＭＯＰ）を求めるプロセッサと、
備える、異種無線ネットワークにおいてパケットをルーティングするノードを開示する。

物理的に接続されたネットワークの低電力高損失ネットワーク用ルーティングプロトコル（ＲＰＬ）の分割の一例を示す図である。 ネットワークトポロジー内の異なる位置にあるノードの異なるリソース要件の一例を示す図である。 ノードの電池の寿命に影響を与えるＲＰＬの一例を示す図である。 本発明の幾つかの実施形態によるマルチホップ異種無線ネットワークの概略図である。 本発明の幾つかの実施形態による図２Ａのネットワークの形成に関与しているノードの構造の概略図である。 本発明の幾つかの実施形態による、サブネットワークのセットに分割されたマルチホップ異種無線ネットワークにおいてパケットをルーティングする方法のブロック図である。 本発明の幾つかの実施形態によるルーティングテーブルエントリーの一例示のフォーマットを示す図である。 本発明の幾つかの実施形態によるソースルーティングエントリーのフォーマットを示す図である。 本発明の幾つかの実施形態によるＫホップ近傍エントリーのフォーマットを示す図である。 本発明の幾つかの実施形態による２ホップ近傍要求パケット及び応答パケットの送信の一例を示す図である。 本発明の幾つかの実施形態によるノードの動作モード（ＭＯＰ）を変更する方法のブロック図である。 本発明の幾つかの実施形態による、ソースノードからデスティネーションノードへの複数の中間中継ノードを介したルーティングパスの一例を示す図である。 本発明の幾つかの実施形態による、目的関数のセット及びルーティングメトリックのセットを用いて階層型デスティネーション指向有向非巡回グラフ（Ｈ−ＤＯＤＡＧ）を構築する方法のブロック図である。 本発明の幾つかの実施形態による、ルーティングメトリックの３つのセットを用いた階層型デスティネーション指向有向非巡回グラフ（Ｈ−ＤＯＤＡＧ）の一例を示す図である。 本発明の幾つかの実施形態による、ノードにＭＯＰを減少させることができる条件の概略図である。 本発明の幾つかの実施形態による、ノードにＭＯＰを増加させることができる条件の概略図である。 本発明の幾つかの実施形態による、データノードがタスクＩＤに基づいてシンクノードに上りパケットを送信する概略図である。 本発明の幾つかの実施形態による、データノードがキュー占有インデックス（ＱＯＩ）に基づいて上りパケットを転送する親を選択する概略図である。 本発明の幾つかの実施形態による、シンクノードがルーティングテーブル及びソースルーティングデータベースを用いて下りパケットをデスティネーションに送信する２つの方法の概略図である。 本発明の幾つかの実施形態による、記憶型ノードがルーティングテーブル及びソースルーティングデータベースを用いて下りパケットをデスティネーションに中継する２つの方法の概略図である。 本発明の幾つかの実施形態による、非記憶型ノードがソースルーティングパスを用いて下りパケットをデスティネーションに中継する概略図である。

無線のモノのインターネット（ＩｏＴ）ネットワーク等の異種無線ネットワークには、数万個のノードが存在する可能性がある。これらのノードは、異なるタスクを実行することが必要とされている。例えば、或るノードグループは、現場監視を行うことができ、別のノードグループは、ファクトリーオートメーションのデータを転送することができ、更に別のノードグループは、ビルセキュリティを監視する。異なるタスクは、異なる要件を有する。現場監視の場合、ノードは、通常、電池電源式である。これらのノードは、測定データをあまり高い頻度で送信しない。パケット損失は決定的に重要なものではない。ここでのルーティングの要件は、電池寿命を延長することである。ファクトリーオートメーションの場合、大量のデータ転送があり、データを確実に送達することが必要とされる。ここでの要件は、通信の信頼性である。ビルセキュリティの場合、多くのデータトラフィックはない。一方、何らかの疑わしいイベントの場合、情報が、コントロールセンターに直ちに送信される可能性がある。ここでの要件はレイテンシーである。

したがって、ネットワークトポロジーは、アプリケーションの要件に基づいて、ネットワークの異なる部分におけるその機能を適応させることが必要とされる。ネットワークトポロジーの特徴は、このトポロジーを作成するのに用いられるルーティングアルゴリズム、メトリック及び目的関数によって決まる。その結果、ルーティングアルゴリズムは、異種ネットワークの異なる部分には異なるルーティングメトリック及び目的関数を適用することができる。例えば、現場監視の場合、残余エネルギー（ＲＥ）等のエネルギー関連ルーティングメトリック及び最小エネルギーパス等の寿命関連目的関数が用いられるべきである。ファクトリーオートメーションの場合、予想送信カウント（ＥＴＸ）等の高スループットルーティングメトリック及び最高信頼性パス等の信頼性関連目的関数が用いられるべきである。セキュリティ監視の場合、ホップカウント（ＨＣ）等の遅延関連ルーティングメトリック及び最短パス等の低レイテンシー関連目的関数が用いられるべきである。異なるルーティングメトリック及び目的関数が、ネットワークトポロジーの異なる階層と、ネットワークトポロジーの同じ階層における異なるクラスターとにおいて適用されるように階層型ネットワークトポロジーを用いて、そのような要件を満たすことができる。

そのために、本発明の幾つかの実施形態は、マルチホップ異種無線ネットワークでは、異なるアプリケーション要件及びリソース要件に基づいてネットワークトポロジーを構築することができるという認識に基づいている。例えば、目的関数及びルーティングメトリックの適切なセットを選択して、トポロジーのマルチ階層及びマルチクラスターを構築するように、異種の目的関数及びルーティングメトリックがノードに提供されるべきである。

低電力高損失ネットワーク用ＩＰｖ６ルーティングプロトコル（ＲＰＬ）は、インターネットエンジニアリングタスクフォース（ＩＥＴＦ）によって開発されたルーティングプロトコルである。ＲＰＬは、ネットワークのノードを、デスティネーション指向有向非巡回グラフ（ＤＯＤＡＧ）と呼ばれるツリー状のトポロジーに編成する。所定のメモリ閾値に基づいて、ＲＰＬは、４つの動作モード（ＭＯＰ）、すなわち、ＭＯＰ＝０、ＭＯＰ＝１、ＭＯＰ＝２及びＭＯＰ＝３を定義する。ＭＯＰ＝０の場合、ＲＰＬは、データノードからシンクノードへの一方向ルーティング、すなわち、上りルーティングしかサポートしない。ＲＰＬは、シンクノードからデータノードへのルーティング、すなわち、下りルーティングをサポートしない。ＭＯＰ＝１の場合、ＲＰＬは、双方向ルーティングを可能にし、下りルーティングにソースルーティングを用いる。メモリを節約するために、ＭＯＰ＝１において動作するノードは、他のどのノードの経路エントリーも記憶しない。その結果、ＭＯＰ＝１は、非記憶型動作モードと呼ばれる。ＭＯＰ＝２の場合、ＲＰＬは、双方向ルーティングをサポートし、下りルーティングにルーティングテーブルを用いる。ＭＯＰ＝２において動作するノードは、そのサブＤＯＤＡＧ、すなわち、サブツリーにおけるノードの経路エントリーを記憶する。しかしながら、ＭＯＰ＝２の場合、下りマルチキャストはサポートされない。したがって、ＭＯＰ＝２は、マルチキャストサポートを有しない記憶型動作モードと呼ばれる。ＭＯＰ＝３の場合、ＲＰＬは、下りマルチキャストをサポートすることによってＭＯＰ＝２を強化する。したがって、ＭＯＰ＝３は、マルチキャストサポートを有する記憶型動作モードと呼ばれる。ＭＯＰ＝２及びＭＯＰ＝３は、ノードが経路エントリーを記憶するためにより大きなメモリ空間を有することを必要とする。

しかしながら、ＲＰＬは、ネットワークにおける全てのルーターノードが同じＭＯＰを有すること、すなわち、全てのルーターノードがシンクノードのＭＯＰと同じＭＯＰを有することができることを要件とする。そのために、本発明の幾つかの実施形態は、ノードがシンクノードのＭＯＰと異なるＭＯＰを有する場合に、そのノードは、リーフノードとしてネットワークに参加することしかができず、したがって、ネットワークを拡張することができないという認識に基づいている。

図１Ａは、そのような認識を実証する一例を示している。この例では、全てのノードは、リンク１１０を介して物理的に接続されている。シンクノードＳ、ノードＮ１及びノードＮ２は、ＭＯＰ＝１を有する。ノードＳ１及びＳ２は、ＭＯＰ＝２を有する。ノードＳ１は、シンクノードのＭＯＰと異なるＭＯＰを有するので、Ｓ１は、ＤＯＤＡＧトポロジー１２０にリーフノードとして参加することができる。したがって、Ｓ１は、ネットワークを拡張することができない。その結果ノードＳ２は隔離され、ネットワーク１２０に参加することができない。

本発明の幾つかの実施形態は、ネットワークトポロジーの位置が異なれば、その位置におけるノードのリソース要件は異なるということをＲＰＬは考慮していないという認識に基づいている。所定のメモリ閾値に基づくＭＯＰの決定は、同種ネットワークにおいても行うことができない。例えば、同じメモリを有する場合、シンクノードから離れているノードは、そのサブツリーにおける全ての経路エントリーを記憶することができる一方、シンクノードに近いノードは、そのサブツリーにおける全ての経路エントリーを記憶することができない。さらに、より小さなメモリを有するノードが全ての経路エントリーを記憶することができ、より大きなメモリを有するノードが経路エントリーを記憶することができない可能性さえある。

図１Ｂは、そのような認識を実証する一例を示している。この例では、経路エントリー１３０は２００バイトであり、ノードＳ１は１０００バイトのメモリを有し、ノードＳ２は５００バイトのメモリを有する。しかしながら、Ｓ２がノードＳ３の経路エントリーを記憶するには、２００バイトのメモリしか必要とされず、Ｓ１がノードＳ２〜Ｓ８の経路エントリーを記憶するには、１４００バイトのメモリが必要とされる。その結果、より大きなメモリを有するノードＳ１は、全ての経路エントリーを記憶することができない。

加えて、本発明の幾つかの実施形態は、ＲＰＬは、ネットワーク動作における電池エネルギー等の持続可能でないリソースの消費を考慮していないという認識に基づいている。図１Ｃは、そのような認識を実証する一例を示している。この例では、ノードＳ１は、ネットワーク始動時１４０に１００％の電池を有し、したがって、ＭＯＰ＝２で動作する。ノードＮ１〜Ｎ７は、それらのパケット１６０を、ノードＳ１を介してシンクノードＳに転送する。しかしながら、Ｓ１は電池電源式である。ネットワークが動作すると、Ｓ１は、そのエネルギーを費やして、そのサブツリーにおけるノードＮ１〜Ｎ７のデータパケットを中継する。現時点１５０において、Ｓ１は、５％の電池エネルギーしか有しておらず、そのため、Ｓ１は、それ自身のデータを送信することのみにそのエネルギーを用いるべきである。この場合、ノードＮ１〜Ｎ７は、それらのパケット１６０をＮ８及びＮ９を介して転送すべきである。この問題は、ノードＮ１〜Ｎ７がＳ１の電池レベルを知らず、それらのパケット１６０を、Ｓ１を介して転送し続けるということである。その結果、Ｓ１は、すぐにデッド（dead：電源が切れた）ノードになる。

したがって、本発明の種々の実施形態は、リソースアウェアマルチタスクルーティング方法を提供する。この方法は、混合動作モードが物理的に接続されたネットワークの分割を回避することを可能にし、そのルーティング機能をリソース要件に基づいて適応させ、ネットワーク動作におけるリソース使用量を考慮し、異種の目的関数及びルーティングメトリックがネットワークにおける複数のタスクの階層型ルーティングトポロジーを作成することを可能にするものである。

図２Ａは、本発明の幾つかの実施形態によるマルチホップ異種無線ネットワーク２００の概略図を示している。このネットワークは、異なるメモリリソース及びエネルギーリソース２０１を有する複数のノードを備える。このネットワークは、シンクノード２０５と、大きなメモリ及びグリッド電源を有するデータノード２１０と、大きなメモリ及び大きな電池電源を有するデータノード２２０と、大きなメモリ及び小さな電池電源を有するデータノード２３０と、小さなメモリ及びグリッド電源を有するデータノード２４０と、小さなメモリ及び大きな電池電源を有するデータノード２５０と、小さなメモリ及び小さな電池電源を有するデータノード２６０とを備える。全てのノードは、無線リンク２０８を介して通信する。リンクの方向は、ノードの物理的到達可能性を示している。幾つかのノードは、パケットをシンクノードに直接送信することができる。ノードのうちの幾つかは、いずれのシンクノードにもパケットを直接送信することができない。その代わりに、パケットは、まず、中間ノード又は中継ノードに送信され、次に、これらの中間ノード又は中継ノードが、これらのパケットをシンクノードに中継する。換言すれば、パケット送信は、マルチホップ形式で行われる。

本発明の幾つかの実施形態は、異なる計算リソース及びエネルギーリソースを有する複数のノードを備えるマルチホップ無線ネットワークは、目的関数とルーティングメトリックとの固有の組み合わせを有する複数のサブネットワークに分割することができるという認識に基づいている。その上、そのようなネットワークのノードは、複数のサブネットワークに参加することができ、異なるサブネットワークの異なるタイプのルーティングを指定する異なるＭＯＰに従って動作することができる。

図２Ｂは、図２Ａのネットワークの形成に関与することができるノード２７０の構造を概略的に示している。このノードは、データパケット及び制御パケット等のパケットを送受信する送受信機を備える。この送受信機は、受信機２７１及び送信機２７２のうちの一方又は組み合わせを備えることができる。このノードは、当該ノードにエネルギーを供給する電池２７４又は電力グリッド２７５等の電力源２７３と、プロセッサ２７６と、メモリ２７７とを備えることができる。このメモリは、ルーティングメモリセクション２７８とノードメモリセクション２７９とを含む２つのセクションに分割されている。

プロセッサ２７６は、複数のサブネットワークの目的関数とルーティングメトリックとの組み合わせに基づいてそれらのサブネットワークに参加し、異なるＭＯＰを求める。ルーティングメモリセクション２７８は、ノード２７０によって受信された中継パケットをバッファリングするルーティングバッファーメモリ２８０と、ノード２７０をルーター（すなわち、中継ノード）として用いるノードの経路エントリー（すなわち、ルーティングテーブルエントリー）及び親子（child-parent）エントリー（すなわち、ソースルーティングエントリー）等のルーティングトポロジー情報を記憶するルーティングトポロジーメモリ２９０とに更に分割される。ノードメモリ２７９は、ネットワークに参加するためにノード２７０によって用いられる。ネットワーク識別子及びノード２７０の識別子等のネットワーク情報は、ノードメモリ２７９に記憶される。ノードメモリ２７９は、このノード自身のパケットをバッファリングするのにも用いられる。

ネットワーク２００を形成するために、各ノード２７０は、幾つかの動作を実行し、幾つかの情報を記憶することができる。例えば、各ノードは、経路発見パケットを受信することができ、当該ノードのデータパケットをシンクノードに向けて送信するためにシンクノードＩＤ及び次ホップノードＩＤを記憶することができる。シンクノードＩＤ及び次ホップノードＩＤは、ノードメモリセクション２７９に記憶される。２６０等のノードは、他のノードのパケットを中継するだけの十分なメモリ及び電力供給を有していない場合があり、リーフノードとしてネットワークに参加することしかできない。２４０等のノードは、パケットを中継ルーティングするだけの十分な電力供給を有するが、そのサブツリーにおけるノードのルーティング情報を記憶するだけの十分なルーティングトポロジーメモリ２９０を有していない。２１０等のノードは、全てのルーティング機能を実行することができ、全てのルーティング情報を記憶することができる。

図２Ｃは、本発明の幾つかの実施形態による、第１のシンクノードを有する第１のサブネットワークと、第２のシンクノードを有する第２のサブネットワークとを含むサブネットワークのセットに分割されたマルチホップ異種無線ネットワークにおいてパケットをルーティングする方法のブロック図を示している。これらの実施形態では、１つのノードが、第１のサブネットワークの少なくとも一部と、第２のサブネットワークの少なくとも一部とを形成する。本方法のステップは、ノードのプロセッサ２７６を用いて実行される。

本方法は、ノードにおける配分ルーティングメモリ（ＡＲＭ）と、ノードの残りの予想ルーティング寿命（ＥＲＬ）との関数として、ノードの利用可能ルーティングリソース２８５を求める（２８４）。ＡＲＭは、ルーティングプロトコルを実行するためにノードによって配分されるメモリの一部分であり、ＥＲＬは、ノードがパケットをルーティングすることができる時間であり、この時間は、例えば、ノードの電池のタイプと、ノードが動作する状態とによって左右される可能性がある。特に、幾つかの実施形態では、利用可能ルーティングリソース２８５は、ノードのサブネットワークから独立しており、ノード自体のパラメーターに基づいて求められる。

本方法は、ノードによってサブネットワークに用いられるルーティングプロトコルと、サブネットワークにおけるノードの論理ロケーションと、ノードを通るサブネットワークにおけるデータトラフィックとの関数として、ノードの少なくとも１つの必要ルーティングリソースも求める（２８１）。特に、幾つかの実施形態では、必要ルーティングリソース２８５は、ノードが関与して形成されたサブネットワークに依存する。そのために、このノードは、異なる必要ルーティングリソースを求めることができる。例えば、この求めること２８１は、第１のサブネットワークのためのこのノードの第１の必要ルーティングリソース２８２を求めることと、第２のサブネットワークのためのこのノードの第２の必要ルーティングリソース２８３を求めることとを含む。第１の必要ルーティングリソース２８２は、第２の必要ルーティングリソース２８３と異なる可能性がある。例えば、ノードの論理ロケーションが、第２のネットワークの第２のシンクよりも第１のサブネットワークの第１のシンクに近い場合、ノードは、第２のサブネットワークよりも第１のサブネットワークのデータをより多く転送することが必要となる可能性がある。そのために、第１の必要ルーティングリソース２８２は、第２の必要ルーティングリソース２８３よりも大きい可能性がある。

本方法は、利用可能ルーティングリソース２８５及び第１の必要ルーティングリソース２８２を用いて、第１のサブネットワークにおけるノードのルーティングのタイプを指定する第１のＭＯＰを求める（２９１）とともに、利用可能ルーティングリソース２８５及び第２の必要ルーティングリソース２８３を用いて、第２のサブネットワークにおけるノードのルーティングのタイプを指定する第２のＭＯＰを求める（２９３）。第１の必要ルーティングリソースと第２の必要ルーティングリソースとの相違に起因して、第１のＭＯＰは第２のＭＯＰと異なる可能性がある。次に、本方法は、第１のＭＯＰに従って第１のサブネットワークにおいてパケットをルーティングするとともに、第２のＭＯＰに従って第２のサブネットワークにおいてパケットをルーティング（２９５）。

本発明の幾つかの実施形態は、マルチホップ異種無線ネットワークが、配分ルーティングバッファーメモリ２８０、配分ルーティングトポロジーメモリ２９０、電源２７３等のノードリソースと、サブツリーサイズ、必要ルーティングメモリ等の検知されたネットワーク状態とに基づいて階層型ルーティングを実現するための階層型ＲＰＬ（Ｈ−ＲＰＬ）ルーティングプロトコルを提供する。その結果、Ｈ−ＲＰＬルーティングプロトコルは、ネットワーク内のノードを階層型ＤＯＤＡＧ（Ｈ−ＤＯＤＡＧ）トポロジーに編成する。

Ｈ−ＤＯＤＡＧトポロジーにおけるシンクノードは、Ｈ−ＤＯＤＡＧルート（root）と呼ばれる。Ｈ−ＤＯＤＡＧは、３つのパラメーター、すなわち、Ｈ−ＲＰＬＩｎｓｔａｎｃｅＩＤ、Ｈ−ＤＯＤＡＧ ＩＤ及びＨ−ＤＯＤＡＧバージョン番号によって一意に特定される。Ｈ−ＤＯＤＡＧにおけるノードのランクは、Ｈ−ＤＯＤＡＧルートを基準とした他のノードに対するこのノードの個々の位置を規定する。Ｈ−ＲＰＬは、Ｈ−ＤＯＤＡＧ情報オブジェクト（Ｈ−ＤＩＯ）パケットを用いて、データノードからシンクノードへの上り経路を構築する。シンクノードからデータノードへの下り経路を作成するために、Ｈ−ＲＰＬは、Ｈ−ＤＯＤＡＧデスティネーションアドバタイズメントオブジェクト（Ｈ−ＤＡＯ）パケットを用いる。Ｈ−ＤＯＤＡＧ情報請求（Ｈ−ＤＩＳ）パケットは、Ｈ−ＤＩＯパケットをＨ−ＲＰＬノードに請求するのに用いられる。すなわち、新たな経路を発見するのに用いられる。

Ｈ−ＲＰＬと標準的なＲＰＬとの間の制御パケットの相違は、次のものを含む。すなわち、（１）Ｈ−ＤＩＯは、異種目的関数、すなわち、ネットワークの異なる部分において変化する目的関数のセットを搬送する；（２）Ｈ−ＤＩＯは、各目的関数に用いられるルーティングメトリックを指定する１対多マップのセットを搬送する；（３）Ｈ−ＤＩＯは、固定ＭＯＰではなく可変ＭＯＰを搬送する；（４）Ｈ−ＤＩＯは、サブＨ−ＤＯＤＡＧ ＩＤを搬送する；（５）ＭＯＰは、４つではなく５つの符号化を有する；（６）Ｈ−ＤＡＯは、対応するターゲットノードのＭＯＰを搬送する；及び（７）Ｈ−ＤＩＳは、好適な目的関数のセット及び好適なルーティングメトリックのセット並びに好適なＭＯＰを指定することができる。

新たな動作モード（ＭＯＰ）及びＭＯＰ符号化
Ｈ−ＤＯＤＡＧトポロジーでは、ノードは、ＭＯＰを用いて、それらのルーティングタイプをアナウンスする。ＲＰＬによって定義されたＭＯＰは、異種ネットワークの要件を満たしていない。したがって、ＲＰＬにおいて定義されたＭＯＰ＝０、ＭＯＰ＝１、ＭＯＰ＝２及びＭＯＰ＝３に加えて、本発明の実施形態は、Ｈ−ＤＯＤＡＧの新たなＭＯＰ、すなわち、ＭＯＰ＝−１を定義する。ＭＯＰ＝−１の場合、ノードは、そのリソースのうちの１つ又は組み合わせが重要であるので、もはやルーティングを実行することができないことをシグナリングする。代わりに、利用可能リソースは、そのノードがそれ自身のパケットを送信することのみ可能にすることができる。新たなＭＯＰ＝−１の導入に伴い、ＭＯＰは４ビットを要する。

Ｈ−ＤＯＤＡＧトポロジーでは、ＭＯＰ＝−１は、リーフＭＯＰと呼ばれ、ＭＯＰ＝０は、上りＭＯＰと呼ばれ、ＭＯＰ＝１は、非記憶型ＭＯＰと呼ばれ、ＭＯＰ＝２は、記憶型ＭＯＰと呼ばれ、ＭＯＰ＝３は、マルチキャスト記憶型ＭＯＰと呼ばれる。

Ｈ−ＤＯＤＡＧにおけるノードは、ルーティングのタイプを指定する異なるＭＯＰに従って動作する。リーフＭＯＰに従って動作するノードは、リーフノードとすることができ、したがって、ネットワーク接続を拡張することができない。すなわち、通常のＨ−ＤＩＯパケットを送信しない。上りＭＯＰに従って動作するノードは、下りパケットをルーティングしない。非記憶型ＭＯＰに従って動作するノードは、下りルーティング情報を記憶しない。記憶型ＭＯＰに従って動作するノードは、経路エントリー、ネットワークの少なくとも一部分の親子ペアを指定する親子エントリー、及びＫホップ近傍情報等の下りルーティング情報を記憶する。マルチキャスト記憶型ＭＯＰに従って動作するノードは、下りルーティング情報と、マルチキャストグループのメンバー等の下りマルチキャスト情報とを記憶する。

ＭＯＰ＝−１、０、１で動作するノードは、本明細書では、非記憶型ノードと呼ばれる。ＭＯＰ＝２、３で動作するノードは、本明細書では、記憶型ノードと呼ばれる。ＭＯＰ＝−１、０及び１の場合、ノードは、親情報をＨ−ＤＡＯに含めることによってＨ−ＤＡＯをシンクノードに送信する。このＨ−ＤＡＯは、非記憶型Ｈ−ＤＡＯ（Ｎ−Ｈ−ＤＡＯ）と呼ばれる。ＭＯＰ＝２及び３の場合、ノードは、親情報をＨ−ＤＡＯに含めずにＨ−ＤＡＯを親に送信する。このＨ−ＤＡＯは、記憶型Ｈ−ＤＡＯ（Ｓ−Ｈ−ＤＡＯ）と呼ばれる。

動作モード（ＭＯＰ）の決定及び変更
Ｈ−ＤＯＤＡＧトポロジーを構築するために、ネットワーク２００におけるノードは、適切なＭＯＰを求める必要がある。このために、本発明の幾つかの実施形態は、２つの新たなパラメーターを用いて、ＭＯＰを計算する。第１のパラメーターは、経路エントリー３１０、親子エントリー３２０、Ｋホップ近傍エントリー３３０を記憶するとともに、中継パケット等をバッファリングするのに必要とされる必要ルーティングメモリ（ＲＲＭ）である。ＲＲＭは、配分ルーティングメモリ（ＡＲＭ）２７８と異なる。ＲＲＭは、ＭＯＰを求める際に重要である。なぜならば、図１Ｂに示すように、同じＡＲＭを有する場合、より小さなサブツリーを有するノードは、経路エントリー及び親子エントリー等の全てのルーティング情報を記憶することができる一方、より大きなサブツリーを有するノードは、全てのルーティングデータを記憶することができないからである。第２のパラメーターは、ノードがルーティングを実行することができる時間を示す予想ルーティング寿命である。ルーティング寿命がクリティカルであるとき、ノードは、リーフノードとしてのみ動作することができる。ネットワーク２００では、ノードは、異なる電源及び異なる電池容量を有する。グリッド電源を有するノードは、無限のルーティング寿命を有するとみなされる。一方、電池電源を有するノードは、有限のルーティング寿命を有する。電池容量の変動に起因して、残りのエネルギーのパーセンテージ等の従来の測定値は意味をなさない。なぜならば、同じパーセンテージの残りのエネルギーを有する場合であっても、大きな電池容量を有するノードは、小さな電池容量を有するノードよりも長くルーティングを行うことができるからである。加えて、ノードは、ネットワーク２００において異なる役割を果たす場合がある。ルーターは、リーフノードよりも多くのエネルギーを消費する。同じ量の電池エネルギーを有する場合であっても、重い作業負荷のノードの寿命は、軽い作業負荷のノードの寿命よりも短い。したがって、従来の残余エネルギー測定値は、ノードの寿命を示さない場合がある。

Ｈ−ＤＯＤＡＧトポロジーに参加するために、ノードは、ノードが動作するのに必要とするメモリであるノードメモリ２７９を十分に有することができる。このノードメモリは、ノードがルーターとして付加的な役割を果たすのに必要とする付加的メモリであるルーティングメモリ２７８とは異なる。Ｈ−ＤＯＤＡＧトポロジーでは、必要とされるノードメモリ（ＲＮＭ）は、以下のように計算することができる。

ここで、
Parent ID：親ＩＤ
Parent MOP：ＭＯＰ
Default Lifetime：デフォルト寿命
Lifetime Unit：寿命単位
H-DOGAG Version Number：Ｈ−ＤＯＤＡＧバージョン番号
Sub H-DODAG ID：サブＨ−ＤＯＤＡＧ ＩＤ
Node MOP：ノードＭＯＰ
Node Buffer：ノードバッファー
である。
また、Ｎ_Ｐは親の数であり、親ＩＤ（Parent ID）は１６バイトであり、デフォルト寿命（Default Lifetime）は１バイトであり、寿命単位（Lifetime Unit：寿命ユニット）は２バイトであり、親ＭＯＰ（Parent MOP）は０．５バイトであり、Ｈ−ＲＰＬＩｎｓｔａｎｃｅＩＤは１バイトであり、Ｈ−ＤＯＤＡＧ ＩＤは１６バイトであり、Ｈ−ＤＯＤＡＧバージョン番号（H-DOGAG Version Number）は１バイトであり、サブＨ−ＤＯＤＡＧ ＩＤ（Sub H-DODAG ID）は１６バイトであり、ノードＭＯＰ（Node MOP）は０．５バイトであり、ノードバッファーサイズは、ノードのパケット生成レートに依存する。したがって、最小ＲＮＭ（ＲＮＭ^ｍｉｎ）は、少なくとも５４＋ｎｏｄｅ＿ｂｕｆｆｅｒ＿ｓｉｚｅ＋ｏｔｈｅｒ＿ｒｅｑｕｉｒｅｄ＿ｎｏｄｅ＿ｍｅｍｏｒｙバイトであり、これは１つの親のみのものである。

式（１）は、ＲＮＭ^ｍｉｎがノードに依存することを示している。ノードが、より多くの親を選択する場合又はより多くのパケットを生成する場合、ＲＮＭ^ｍｉｎはより大きくなる。そうでない場合、ＲＮＭ^ｍｉｎはより小さくなる。

必要ルーティングメモリ（ＲＲＭ）の計算
ＲＲＭを計算する手法は、全てのルーティングアルゴリズムについて同じである。しかしながら、計算されるＲＲＭは、特定のルーティングアルゴリズムに基づいて変化する。なぜならば、異なるルーティングアルゴリズムは、異なるルーティング情報を記憶するからである。本発明の実施形態は、Ｈ−ＲＰＬルーティングプロトコルのＲＲＭを計算する方法を提供する。Ｈ−ＲＰＬには、４つのタイプのルーター、すなわち、上りルーター、非記憶型ルーター、記憶型ルーター及びマルチキャスト記憶型ルーターが存在する。

Ｈ−ＤＯＤＡＧトポロジーにおけるノードが上りルーターであるためには、このノードは、通常のＨ−ＤＩＯパケットを送信する必要がある。したがって、ノードは、３つのトリクルタイマー構成パラメーター、すなわち、Ｈ−ＤＩＯ間隔最小値（interval minimum）（１バイト）、Ｈ−ＤＩＯ間隔倍増値（interval doublings）（１バイト）、及びＨ−ＤＩＯ冗長定数（１バイト）を保持する必要がある。加えて、ノードは、３つのトリクルタイマー変数、すなわち、現在の間隔サイズＩ（４バイト）、現在の間隔内の時刻Ｔ（４バイト）、及びカウンターＣ（１バイト）も保持する必要がある。加えて、上りルーターは、目的関数のセット及びルーティングメトリックのセット並びに目的関数とルーティングメトリックとの間の１対多マッピングも保持する必要がある。目的関数は、１バイトである目的コードポイント（ＯＣＰ）によって特定され、ルーティングメトリック（ＲＭ）は、少なくとも１バイトである。上りルーターは、親ランク（２バイト）、ノードランク（２バイト）、ＭａｘＲａｎｋＩｎｃｒｅａｓｅ（２バイト）、及びＭｉｎＨｏｐＲａｎｋＩｎｃｒｅａｓｅ（２バイト）も保持する必要がある。しかしながら、上りルーターは、下りパケットをルーティングせず、したがって、デスティネーションアドバタイズメントトリガーシーケンス番号（ＤＴＳＮ）を保持しない。その結果、上りルーターの必要ルーティングメモリ（ＲＲＭ_Ｕ）は、以下の式によって与えられる。

ここで、
H-DIO Interval Min：Ｈ−ＤＩＯ間隔最小値
H-DIO Interval Doublings：Ｈ−ＤＩＯ間隔倍増値
H-DIO Redundancy Constant：Ｈ−ＤＩＯ冗長定数
OCP to RMs Mappings：ＯＣＰ対ＲＭマッピング
Parent Rank：親ランク
Node Rank：ノードランク
Upward Routing Buffer：上りルーティングバッファー
である。
また、Ｎ_ＯＣＰは目的関数の数であり、Ｎ_ＲＭはルーティングメトリックの数である。したがって、上りルーターの最小ＲＲＭ（

）は、少なくとも２２＋ｕｐｗａｒｄ＿ｒｏｕｔｉｎｇ＿ｂｕｆｆｅｒ＿ｓｉｚｅ＋ｏｔｈｅｒ＿ｒｅｑｕｉｒｅｄ＿ｒｏｕｔｉｎｇ＿ｍｅｍｏｒｙバイトであり、これは１つの目的関数、１つのルーティングメトリック及び１つの親についてのものである。

非記憶型ルーターの場合、上りルーターによって必要とされるルーティングメモリに加えて、ＤＴＳＮ（１バイト）を保持することと、下りパケットをバッファリングすることとに、追加のルーティングメモリが必要とされる。したがって、非記憶型ルーターの必要ルーティングメモリ（ＲＲＭ_Ｎ）は、以下の式によって与えられる。

ここで、
Parenet DTSN：親ＤＴＳＮ
Downward Routing Buffer：下りルーティングバッファー
である。

非記憶型ルーターの最小ＲＲＭ（

）は、少なくとも２３＋ｕｐｗａｒｄ＿ｒｏｕｔｉｎｇ＿ｂｕｆｆｅｒ＿ｓｉｚｅ＋ｄｏｗｎｗａｒｄ＿ｒｏｕｔｉｎｇ＿ｂｕｆｆｅｒ＿ｓｉｚｅ＋ｏｔｈｅｒ＿ｒｅｑｕｉｒｅｄ＿ｒｏｕｔｉｎｇ＿ｍｅｍｏｒｙバイトであり、これは、１つの目的関数、１つのルーティングメトリック及び１つの親についてのものである。

ノードが記憶型ルーターであるためには、非記憶型ルーターによって必要とされるルーティングメモリに加えて、経路エントリー、親子エントリー及びＫホップ近傍情報を記憶するために、追加のルーティングメモリが必要とされる。ノードのＫホップ近傍は、このノードのＫホップ近傍内にあるノードとして定義される。記憶型ルーターは、その記憶型子によって送信又は転送されたＮ−ＤＡＯパケット及びＳ−Ｈ−ＤＡＯパケットの双方に含まれるデスティネーションの数をカウントすることによって、そのルーティングテーブルのサイズを計算する。記憶型ルーターは、その非記憶型子によって送信又は転送されたＮ−Ｈ−ＤＡＯパケットに含まれるデスティネーションの数をカウントすることによって、その親子データベースのサイズを計算する。記憶型ルーターは、Ｋホップ近傍要求パケットをブロードキャストするとともに、応答パケットに含まれるＫホップ近傍の数をカウントすることによってＫホップ近傍の数を計算する。記憶型ルーターは、そのプリファレンスに基づいてＫの値を求める。Ｋ＝１である場合、Ｋホップ近傍セットと近傍セットとは同じである。Ｋ＞１である場合、近傍セットは、Ｋホップ近傍セットのサブセットである。

図４は、記憶型ルーター（ＳＲ）４１０及び４２０が２ホップ近傍要求パケット４３０をブロードキャストし、２ホップ内の近傍が近傍応答パケット４４０を用いて応答する２ホップ近傍要求近傍応答プロセスの一例を示している。近傍要求パケット及び近傍応答パケットは、１ホップ近傍によって中継される。Ｎ１及びＮ２等の幾つかのノードは、１つの記憶型ルーター４１０からのみ２ホップ近傍要求４３０を受信する。一方、Ｎ８、Ｎ９及びＮ１１等の幾つかのノードは、記憶型ルーター４１０及び４２０の双方から２ホップ近傍要求４３０を受信する。この場合、これらのノードは、それらの第１のルーティングプリファレンス及び第２のルーティングプリファレンスを第１の記憶型ルーター及び第２の記憶型ルーターにそれぞれ送信することができる。ノードは、それらのプリファレンスに基づいて第１の記憶型ルーター及び第２の記憶型ルーターを選択する。例えば、ノードは、より小さなホップカウントを有する第１の記憶型ルーターと、より大きなホップカウントを有する第２の記憶型ルーターとを選択することができる。

記憶型ルーターが、そのルーティングテーブルにＮ_Ｒ個のエントリーと、その親子データベースにＮ_Ｃ個のエントリーと、Ｎ_Ｋ個のＫホップ近傍とを有すると仮定する。この記憶型ルーターのＲＲＭ（ＲＲＭ_Ｓ）は、以下の式によって与えられる。

ここで、
Route Entry：経路エントリー
Child-Parent Entry：親子エントリー
K-Hop Neighbor Entry：Ｋホップ近傍エントリー
である。
そして、経路エントリーのフォーマットは図３Ａに示され、ターゲットＩＤは１６バイトであり、次ホップＩＤは１６バイトであり、ＭＯＰは０．５バイトであり、パス寿命は１バイトである。したがって、経路エントリーの最小サイズは３３．５バイトである。親子エントリーのフォーマットは図３Ｂに示され、最小サイズは同じく３３．５バイトである。Ｋホップ近傍エントリーのフォーマットは、図３Ｃに示されている。近傍ＩＤは１６バイトであり、ルーティングプリファレンスは１バイトであり、ホップカウントは１バイトであり、タイムスタンプは４バイトである。Ｋホップ近傍エントリーの最小サイズは２２バイトである。記憶型ルーターであるためには、ノードは、少なくとも１つの親を有し、少なくとも１つの経路エントリー又は親子エントリーと、少なくとも２つのＫホップ近傍とを記憶する必要がある。したがって、記憶型ルーターの最小ルーティングメモリ（

）は、少なくとも１００．５＋ｕｐｗａｒｄ＿ｒｏｕｔｉｎｇ＿ｂｕｆｆｅｒ＿ｓｉｚｅ＋ｄｏｗｎｗａｒｄ＿ｒｏｕｔｉｎｇ＿ｂｕｆｆｅｒ＿ｓｉｚｅ＋ｏｔｈｅｒ＿ｒｅｑｕｉｒｅｄ＿ｒｏｕｔｉｎｇ＿ｍｅｍｏｒｙバイトである。

マルチキャスト記憶型ルーターが下りマルチキャストをサポートするために、必要ルーティングメモリＲＲＭ_Ｓに加えて、ノードは、マルチキャストグループのメンバーを記憶する等の、下りマルチキャストを動作させるのに必要とされる追加のマルチキャストメモリを必要とする。したがって、マルチキャストサポートを有する記憶型ルーターのＲＲＭ（ＲＲＭ_Ｍ）は、以下の式によって与えられる。

ここで、
Downward Multicast Memory：下りマルチキャストメモリ
である。

マルチキャストサポートを有する記憶型ルーターの最小ルーティングメモリ（

）は、少なくとも１００．５＋ｕｐｗａｒｄ＿ｒｏｕｔｉｎｇ＿ｂｕｆｆｅｒ＿ｓｉｚｅ＋ｄｏｗｎｗａｒｄ＿ｒｏｕｔｉｎｇ＿ｂｕｆｆｅｒ＿ｓｉｚｅ＋ｄｏｗｎｗａｒｄ＿ｍｕｌｔｉｃａｓｔ＿ｍｅｍｏｒｙ＋ｏｔｈｅｒ＿ｒｅｑｕｉｒｅｄ＿ｒｏｕｔｉｎｇ＿ｍｅｍｏｒｙバイトである。

式（２）から式（４）は、閾値

がノードに依存することを示している。例えば、ノードがより多くの親を選択する場合又はより大きなサブツリーを有する場合、これらの閾値はより大きくなる。また、双方向ルーティングには、一方向ルーティングよりも多くのメモリが必要とされる。

計算された閾値

と、配分ルーティングメモリ（ＡＲＭ）とを用いて、ノードは、そのＭＯＰを以下のように求めることができる。

このＭＯＰ計算方法は、ノードが商用電源式である場合又は予想ルーティング寿命が利用可能でない場合に用いることができる。

予想ルーティング寿命の計算
ノードは、ルーティングの際に、中継パケットの受信及び中継パケットの送信によってエネルギーを消費する。商用電源式ノードは、電力供給が無制限であり、したがって、無制限のルーティング寿命を有する。他方、電池電源式ノードは、電力供給が限られている。ノードの電池レベルが低いとき、ルーティング機能を停止することが望ましい。このように、電池ノードは、それ自身のパケットを送信するのに残りのエネルギーを用いることができる。この手法は、ネットワーク寿命を延ばし、デッドノードを回避する。予想ルーティング寿命（ＥＲＬ）を計算するために提供される方法は以下のとおりである。

商用電源式ノードについて、このノードが親を有する場合、すなわち、親集合（ＰＳ）のサイズが０よりも大きい場合、このノードは、無限のルーティング寿命を有するとみなされ、このノードが親を有しない場合、このノードはパケットをルーティングすることができない。その結果、このノードは、ルーティング寿命を有しないとみなされる。したがって、商用電源式ノードのＥＲＬは、以下のように規定される。

ここで、
Infinite Routing Lifetime：有限のルーティング寿命
である。

電池電源式ノードの予想ルーティング寿命を計算するために、Ｅ_ｉは、時刻ｔ_ｉ（ｉ＝０，１，２，…）における残余エネルギーであり、Ｅ_０は初期エネルギーであり、Ｐ_ＴＸは送信電力消費量であり、Ｐ_ＲＸは受信電力消費量であり、ＮＲ_ｉは時刻ｔ_ｉ−１から時刻ｔ_ｉまでに受信された中継パケットの数であり、ＮＴ_ｉは時刻ｔ_ｉ−１から時刻ｔ_ｉまでに送信された中継パケットの数であると仮定する。その場合、時刻ｔ_ｉにおける予想ルーティング寿命（ＥＲＬ_ｉ）は、以下のように推定される。

したがって、時刻ｔ_ｉにおける電池電源式ノードのＥＲＬは、以下のように規定される。

予想ルーティング時間の４つの閾値

を、

となるように規定する。ここで、

は、上りルーターに必要とされる最小ルーティング寿命であり、

は、非記憶型ルーターに必要とされる最小ルーティング寿命であり、

は、記憶型ルーターに必要とされる最小ルーティング寿命であり、

は、下りマルチキャストをサポートするために記憶型ルーターに必要とされる最小ルーティング寿命である。計算された予想ルーティング寿命（ＥＲＬ）に基づいて、ノードは、そのＭＯＰを以下のように求めることができる。

このＭＯＰ計算は、ノードが無制限のルーティングメモリを有するとともに、配分ルーティングメモリ又は必要ルーティングメモリが利用可能でないときに用いることができる。式（１０）は、電池電源式ノードがＥＲＬ＜ＥＲＬ_Ｕを有する場合に、このノードはパケットをもはやルーティングしないことを示している。代わりに、このノードは、自身のパケットを送信するのに残りのエネルギーを用いる。

式（６）と式（１０）とを組み合わせると、ネットワーク２００におけるノードのＭＯＰ計算は、以下のように規定される。

図５は、本発明の１つの実施形態による、ノードのＭＯＰを求める及び／又は変更する方法のブロック図を示している。ノードは、まず、ルーティングメモリ２７８を配分する（５００）。ルーティングメモリ５１０が配分されると、潜在的な記憶型ノード、すなわち、

以上の配分ルーティングメモリ（ＡＲＭ）５１０を有するノードは、Ｋホップ近傍要求パケットを送信する。次に、ノードは、Ｋホップ近傍応答パケットと、Ｈ−ＤＩＯ及びＨ−ＤＡＯ等の他のネットワークトポロジーパケットとの受信を開始する。受信されたパケットに基づいて、ノードは、式（２）、式（３）、式（４）又は式（５）を用いて必要ルーティングメモリ（ＲＲＭ）を求めることができ（５４０）、式（７）又は式（９）を用いて予想ルーティング寿命も求めることができる（５５０）。配分ルーティングメモリ（ＡＲＭ）と、必要ルーティングメモリ（ＲＲＭ）と、予想ルーティング寿命（ＥＲＬ）とに基づいて、ノードは、式（１１）を用いてそのＭＯＰを求めることができる（５６０）。新たなＭＯＰが計算されると、ノードは、この新たなＭＯＰ及び必要なトポロジーパケットを送信して（５７０）、そのルーティングタイプ及び更新された情報をその近傍に知らせる。次に、ノードは、戻ってパケットを受信し、ネットワーク状態と、必要な場合には変更されたＭＯＰとを監視する。

ネットワーク２００におけるノードは、配分ルーティングメモリと、必要ルーティングメモリと、予想ルーティング寿命とに基づいて計算された異なるＭＯＰを用いることによって、様々なルーティングタイプをシグナリングするので、幾つかの実施形態は、リソースアウェアマルチタスクルーティングを用いて、データノードからシンクへ及びシンクからデータノードへパケットをルーティングする。本発明の幾つかの実施形態は、Ｈ−ＲＰＬプロトコルをリソースアウェアマルチタスクルーティングに適応させる。

階層型ＤＯＤＡＧ（Ｈ−ＤＯＤＡＧ）の構築
ノードの親は、シンクノードに向かうパス上の当該ノードの直近後続ノードとして定義される。ノードの子は、シンクノードに向かうパス上の当該ノードの直近先行ノードとして定義される。図６は、中継ノード６５０が中継ノード６４０の親であり、中継ノード６４０が中継ノード６５０の子である、ソースノード６２０からデスティネーションノード６３０へのルーティングパス６１０の一例を示している。

本発明の幾つかの実施形態は、ノードが、そのルーティングを、それ自身のリソースと、他のノードのＭＯＰによって示されるような当該他のノードのリソースとを考慮して実行すべきであるとの認識に基づいている。加えて、幾つかの実施形態は、ノードが、それ自身のＭＯＰとその近傍のＭＯＰとを考慮してネットワーク階層に参加するという認識に基づいている。本発明の幾つかの実施形態は、ネットワーク階層が、目的関数のセット及びルーティングメトリックのセットに基づいて作成され、ノードが、それ自身のリソース及びその近傍のリソースを考慮して適切な目的関数及びルーティングメトリックを選択するという認識に基づいている。

図７は、本発明の１つの実施形態によるリソースアウェアマルチタスク階層型ＤＯＤＡＧ（Ｈ−ＤＯＤＡＧ）を作成するブロック図を示している。シンクノードは、Ｈ−ＤＩＯパケットをブロードキャストすることによってＨ−ＤＯＤＡＧ構築を開始する。標準的なＤＯＤＡＧ構築と異なり、シンクノードは、Ｈ−ＤＩＯに含められる目的関数（ＯＦ）のセット及びルーティングメトリック（ＲＭ）のセットを求める（７００）。シンクノードは、各目的関数に用いられるルーティングメトリックのセットを指定する。例えば、シンクノードは、２つの目的関数ＯＦ１及びＯＦ２と、３つのルーティングメトリックＲＭ１、ＲＭ２及びＲＭ３とを選択し、これらのＯＦ及びＲＭを２つのセット（ＯＦ１，ＲＭ１，ＲＭ２）及び（ＯＦ２，ＲＭ２，ＲＭ３）にグループ化する。その結果、ＲＭ１及びＲＭ２はそれぞれ、ＯＦ１の１次ルーティングメトリック及び２次ルーティングメトリックとなり、ＲＭ２及びＲＭ３はそれぞれ、ＯＦ２の１次ルーティングメトリック及び２次ルーティングメトリックとなる。指定されていない場合には、セット（ＯＦ１，ＲＭ１，ＲＭ２）が、Ｈ−ＤＯＤＡＧトポロジーの第１の階層を構築するのに用いられ、セット（ＯＦ２，ＲＭ２，ＲＭ３）が、Ｈ−ＤＯＤＡＧトポロジーの第２の階層を構築するのに用いられる。シンクノードは、ネットワーク全体の考慮に基づいてセット（ＯＦ１，ＲＭ１，ＲＭ２）を選択し、Ｋホップ近傍要求応答プロセスにおいて収集されたルーティングプリファレンス情報に基づいてセット（ＯＦ２，ＲＭ２，ＲＭ３）を選択する。Ｈ−ＤＯＤＡＧ ＩＤに加えて、シンクノードは、サブＨ−ＤＯＤＡＧ ＩＤも双方のセットとともにそのＩＰｖ６アドレスに含める。指定されていない場合には、シンクノードは、他の値を用いることができる場合であっても、ＭＯＰ＝２を設定する。シンクノードは、ルーティングテーブル７６０を作成し（７０５）、ソースルーティングデータベース（親子データベース）７７５を作成する（７１０）。これらのルーティングテーブル及びソースルーティングデータベースは、Ｈ−ＤＡＯパケットの受信及び処理において用いられる。次に、シンクノードは、２に設定されたＭＯＰを有するＨ−ＤＩＯパケットをブロードキャストする（７１５）。Ｈ−ＤＩＯパケットを送信した後、シンクノードは、次に、Ｈ−ＤＡＯパケットを受信し（７４０）、これらのＨ−ＤＡＯパケットを処理する（７４５）。記憶型子によって送信又は転送されたＮ−Ｈ−ＤＡＯパケット又はＳ−Ｈ−ＤＡＯパケット７５０について、シンクノードは、経路エントリーをルーティングテーブル７６０に加える（７５５）。非記憶型子によって送信又は転送されたＮ−Ｈ−ＤＡＯパケット７６５について、シンクノードは、親子エントリーをソースルーティングデータベース７７５に加える（７７０）。

シンクノードが、Ｈ−ＤＯＤＡＧの構築を開始すると、データノードは、Ｈ−ＤＩＯパケットを伝播して、ネットワークトポロジーを拡張する。データノードがＨ−ＤＩＯパケットを受信すると（７２０）、このノードは、パケットを処理し、受信されたＨ−ＤＩＯパケットに含まれる目的関数のセット、ルーティングメトリックのセット、目的関数とルーティングメトリックとの間の１対多マップのセット、及びＭＯＰ値を取得する。ノードは、Ｈ−ＤＯＤＡＧ ＩＤ及びサブＨ−ＤＯＤＡＧ ＩＤも取得する。データノードは、そのＭＯＰ値を求める（７２５）。記憶型ノードは、ルーティングテーブル７６０を作成し（７０５）、ソースルーティングデータベース７７５を作成する（７１０）。記憶型データノードは、ルーティングテーブル７６０及びソースルーティングデータベース７７５を用いて、そのＭＯＰを変更してもよい（７２５）。記憶型データノードは、近傍ルーティングプリファレンス７８０を用いて、目的関数のセット及びルーティングメトリックのセットを変更してもよい（７２５）。データノードのＭＯＰ＝−１である場合、このノードは、受信されたＨ−ＤＩＯに含まれる（ＯＦ，ＲＭ）の第２のセットを用いて親のセットを選択する。第２のセット（ＯＦ，ＲＭ）は、異なるノードからの異なるＨ−ＤＩＯでは異なる可能性がある。次に、ノードは、デフォルト親を選択し、そのＭＯＰを含むＮ−Ｈ−ＤＡＯ７６５を構築し、このＮ−Ｈ−ＤＡＯをデフォルト親に転送する（７３５）。ＭＯＰ＝−１を有するノードは、リードノードとすることができるので、このノードは、Ｈ−ＤＩＯパケットを送信しない。データノードのＭＯＰ＝０又は１である場合、このノードは、受信されたＨ−ＤＩＯに含まれる（ＯＦ，ＲＭ）の第２のセットを用いて親のセットを選択する。記憶型親が存在しない場合、ノードは、１つの非記憶型親をデフォルト親として選択し、このデフォルト親から受信された（ＯＦ，ＲＭ）の第２のセットを用いることによってそのランクを計算する。記憶型親が存在する場合、ノードは、１つの記憶型親をデフォルト親として選択し、このデフォルト親から受信された（ＯＦ，ＲＭ）の第２のセットを用いることによってそのランクを計算する。各ルーターが、選択された各親につき１つのＤＩＯパケットを送信する標準的なＲＰＬと異なり、ノードは、対応するサブＨ−ＤＯＤＡＧ ＩＤを記憶し、ノードのＭＯＰ及び受信された（ＯＦ，ＲＭ）のセットを含むＨ−ＤＩＯパケットを送信する（７３０）。最後に、ノードは、そのＭＯＰを含むＮ−Ｈ−ＤＡＯ７６５を構築し、このＮ−Ｈ−ＤＡＯをデフォルト親に転送する（７３５）。データノードのＭＯＰ＝２又は３である場合、ノードは、まず、受信されたＨ−ＤＩＯに含まれる（ＯＦ，ＲＭ）の第１のセットを用いて親のセットを選択する。そのような親が存在しない場合、すなわち、ノードが、非記憶型ノードからしかＨ−ＤＩＯを受信していなかった場合、このノードは、（ＯＦ，ＲＭ）の第２のセットを用いて親のセットを選択する。ノードが記憶型親を選択していた場合であっても、このノードは、それでもなお、（ＯＦ，ＲＭ）の第２のセットを用いることによって非記憶型親のセットをバックアップ親として選択することができる。ノードが、少なくとも１つの記憶型親を有する場合、このノードは、記憶型親をデフォルト親として選択する。この場合、ノードは、このデフォルト親から受信された（ＯＦ，ＲＭ）の第１のセットを用いてそのランクを計算する。選択された各親について、ノードは、Ｈ−ＤＩＯパケットにおいてＭＯＰ＝２又は３を設定することによってＨ−ＤＩＯパケットを送信する（７３０）。最も重要なこととして、ノードは、サブＨ−ＤＯＤＡＧ ＩＤをそのＩＰｖ６アドレスに置き換え、ノードは、Ｋホップ近傍のルーティングプリファレンスを示す、Ｋホップ近傍応答パケットから収集された情報を用いることによって、（ＯＦ，ＲＭ）の第２のセットを置き換えることができる（７２５）。ノードは、ルーティングテーブル７６０を作成し（７０５）、ソースルーティングデータベース７７５を作成する（７１０）。ノードは、１つのＳ−Ｈ−ＤＡＯ７５０パケットを記憶型Ｈ−ＤＡＯ親のそれぞれに送信し、いずれかの非記憶型親がＨ−ＤＡＯ親として選択されている場合には１つのＮ−Ｈ−ＤＡＯ７６５パケットを非記憶型親のうちの１つに転送する。記憶型親が選択されていない場合には、ノードは、デフォルト親から受信された（ＯＦ，ＲＭ）の第２のセットを用いることによってそのランクを計算する。次に、ノードは、ＭＯＰ＝１を設定することによってＨ−ＤＩＯパケットを送信する（７３０）。この場合、記憶型ノードは、非記憶型ノードとして動作し、ルーティングテーブル及びソースルーティングデータベースを作成しない。したがって、このノードは、代理非記憶型ノード（acting non-storing node）と呼ばれる。このＭＯＰの降格は、データパケットの輻輳を回避するためである。なぜならば、このノードは、非記憶型近傍によって囲まれており、このノードが記憶型ＭＯＰをアナウンスした場合、全ての近傍がそれらのパケットをこのノードに転送するが、このノードは、実際には、非記憶型デフォルト親を有し、この親は、より多くのパケットを記憶する大きなバッファーを有しないか又はより多くのパケットを中継するより多くの電力供給を有しないからである。このノードは、１つのＮ−Ｈ−ＤＡＯをデフォルト親に転送する（７３５）。

Ｈ−ＤＯＤＡＧ構築プロセス中、データノードは、Ｈ−ＤＩＯパケットを受信して処理することに加えて、シンクノードからデータノードへの下り経路を作成するのに用いられるＨ−ＤＡＯパケットも受信して処理する。リーフノードは、Ｈ−ＤＡＯパケットを受信すべきではない。非記憶型ノード及び代理非記憶型ノードは、Ｎ−Ｈ−ＤＡＯ７６５のみを受信すべきである（７４０）。これらのノードは、受信されたＮ−Ｈ−ＤＡＯパケットを処理せず、Ｎ−Ｈ−ＤＡＯパケットをそれらのデフォルト親に中継のみ行う。記憶型データノードは、記憶型子によって送信又は転送されたＮ−Ｈ−ＤＡＯ又はＳ−Ｈ−ＤＡＯ７５０パケットに含まれる各ターゲットの経路エントリーをルーティングテーブル７６０に加える（７５５）ことと、非記憶型子によって送信又は転送されたＮ−Ｈ−ＤＡＯ７６５パケットに含まれる各ターゲットの親子エントリーをソースルーティングデータベース７７５に加える（７７０）こととによって、受信されたＨ−ＤＡＯパケットを処理する（７４５）。シンクノードは、Ｈ−ＤＡＯパケットを用いて、ネットワークサイズ、すなわちＨ−ＤＯＤＡＧサイズを計算する。記憶型ノードは、Ｈ−ＤＡＯパケットを用いて、サブネットワークサイズ、すなわちサブＨ−ＤＯＤＡＧサイズを計算する。

代理非記憶型ノードは、データアグリゲーションを実行するより多くの処理電力と、複数の通信インターフェースとを有する場合に、それ自身のサブＤＯＤＡＧを作成することができる。

図８は、サブネットワークのセットに分割されたＨ−ＤＯＤＡＧトポロジーの一例を示している。シンクノードは、最大パケット送達レート及び高スループットメトリック予想送信カウント（ＥＴＸ）８５０を目的関数及びルーティングメトリックの１次セットとして指定し、最小パケット遅延及びホップカウントを目的関数及びルーティングメトリックの２次セットとして指定する。第１のサブネットワークＨ−ＤＯＤＡＧ８１０は、シンクノード、記憶型ノードＳ１〜Ｓ７によって形成される。ＥＴＸ８５０は、記憶型ノードＳ１〜Ｓ７によって高スループットを実現するために用いられる。ホップカウントメトリック８６０は、非記憶型ノードＮ１〜Ｎ７によって用いられる。第２のサブネットワークＨ−ＤＯＤＡＧ８２０は、記憶型ノードＳ２と、非記憶型ノードＮ１、Ｎ２、Ｎ３、Ｎ４及びＮ７とによって形成される。ここで、Ｓ２はサブＨ−ＤＯＤＡＧルートと呼ばれる。第２のサブネットワークＨ−ＤＯＤＡＧ８３０は、記憶型ノードＳ７と、非記憶型ノードＮ５、Ｎ６、Ｎ７と、代理非記憶型ノードＳ８とによって形成される。ここで、Ｓ７は、サブＨ−ＤＯＤＡＧルートである。ホップカウントメトリック８６０は、非記憶型ノードＮ５、Ｎ６、Ｎ７及び代理非記憶型ノードＳ８によって用いられる。この例では、非記憶型ノードＮ７は、２つの親Ｎ１及びＮ６を選択することによって２つのサブＨ−ＤＯＤＡＧ８２０及び８３０に参加する。第３のサブネットワークＨ−ＤＯＤＡＧ８４０は、代理非記憶型ノードＳ８と、非記憶型電池ノードＮ８、Ｎ９及びＮ１０とによって形成される。ここで、代理非記憶型ノードＳ８はサブＨ−ＤＯＤＡＧルートである。ノードＮ８、Ｎ９及びＮ１０のルーティングプリファレンスに基づいて、代理非記憶型ノードは、目的関数及びルーティングメトリックの第２のセット（最小パケット遅延、ホップカウント）を（最大ネットワーク寿命、残余エネルギーメトリック８７０）に置き換える。

種々のノードが、１つのサブネットワークに属することもできるし、複数のサブネットワークに属することもでき、前者は、例えばノードＮ４であり、後者は、例えばノードＮ７である。そのため、ノードＮ７は、パケットをサブネットワーク８３０のシンクＳ７及びサブネットワーク８２０のシンクＳ２にルーティングすることができる。

本発明の様々な実施形態によれば、Ｈ−ＤＯＤＡＧトポロジーにおけるデータノードは、複数の親を選択して、複数のサブＨ−ＤＯＤＡＧ、すなわちサブネットワークに接続する。サブＨ−ＤＯＤＡＧルートは、シンクノード又は記憶型ノードであり、当該サブＨ−ＤＯＤＡＧにおける全てのノードは、このシンクノード又は記憶型ノードへの経路を有する。ノードは、各親に対応するサブＨ−ＤＯＤＡＧルートＩＤを記憶する。

階層型ＤＯＤＡＧ（Ｈ−ＤＯＤＡＧ）の維持
リソース使用量及び検知されたネットワーク状態に基づいて、ネットワーク２００におけるノードは、そのＭＯＰを変更することができる。ノードは、リソースの障害又は不足に起因してネットワークから離脱することもできる。近傍ノードは、それらの機能を適応的に調整する必要がある。

図９Ａは、ノードにそのＭＯＰを減少させる（９００）ことができる変化を示している。これらの変化は、必要リソースの増加９１０、記憶型親ＭＯＰの減少９２０、記憶型親の利用不能９３０、及びノードリソースの減少９４０を含む。図９Ｂは、ノードにそのＭＯＰを増加させる（９５０）ことができる変化を示している。これらの変化は、必要リソースの減少９６０、非記憶型親ＭＯＰの増加９７０、リーフ近傍ＭＯＰの増加９８０、及びノードリソースの増加９９０を含む。

以下の段落では、Ｈ−ＲＰＬルーティングプロトコルにおけるＨ−ＤＯＤＡＧの維持を説明する。

非記憶型バックアップ親が到達不能になった場合、ノードは、ＤＩＳパケットを用いて新たな親を発見することができる。非記憶型デフォルト親が到達不能になった場合、ノードは、新たなデフォルト親を選択し、新たなランクを計算し、この変化を示すＨ−ＤＩＯパケットを送信する。ノードは、新たな親を発見することもできる。

記憶型バックアップ親が到達不能になった場合、ノードは、新たな親を発見することができる。記憶型デフォルト親が到達不能になった場合、ノードは、少なくとも１つのバックアップ記憶型親を有する場合に、バックアップ記憶型親をデフォルト親として選択する。次に、ノードは、新たなランクを計算し、そのＭＯＰを変更することなくＨ−ＤＩＯパケットを送信する。ノードがバックアップ記憶型親を有さず、かつ、ノードが非記憶型ノードである場合、ノードは、非記憶型親をデフォルト親として選択し、新たなランクを計算し、そのＭＯＰを変更することなくＨ−ＤＩＯパケットを送信する。一方、ノードがバックアップ記憶型親を有さず、かつ、ノードが記憶型ノードである場合、ノードは、そのＭＯＰを１に降格させて代理非記憶型ノードになり、非記憶型親をデフォルト親として選択し、新たなランクを計算し、新たなＭＯＰ＝１を有するＨ−ＤＩＯパケットを送信する。各場合において、ノードは、新たな親を発見することができる。

バックアップ記憶型親が、そのＭＯＰを−１に変更した場合、子ノードは、その親集合からこの親を除去し、必要な場合には新たな親を発見することができる。バックアップ記憶型親が、そのＭＯＰを０又は１に変更した場合、子ノードは、それに応じて親ＭＯＰを更新する。記憶型デフォルト親が、そのＭＯＰを−１に変更した場合、子ノードは、その親集合からこの親を除去することができる。ノードが、少なくとも１つのバックアップ記憶型親を有する場合、ノードは、バックアップ記憶型親をデフォルト親として選択し、新たなランクを計算し、そのＭＯＰを変更することなくＨ−ＤＩＯを送信する。ノードが、バックアップ記憶型バックアップ親を有しない場合、ノードは、非記憶型親をデフォルト親として選択し、新たなランクを計算する。ノードが非記憶型ノードである場合、ノードは、そのＭＯＰを変更することなくＨ−ＤＩＯを送信する。一方、ノードが記憶型ノードである場合、ノードは、そのＭＯＰを１に変更することができ、ＭＯＰ＝１を有するＨ−ＤＩＯを送信する。記憶型デフォルト親が、そのＭＯＰを０又は１に変更し、かつ、子ノードが、少なくとも１つのバックアップ記憶型親を有する場合、ノードは、バックアップ記憶型親をデフォルト親として選択し、新たなランクを計算し、そのＭＯＰを変更することなくＨ−ＤＩＯを送信する。記憶型デフォルト親が、ＭＯＰを０又は１に変更し、かつ、子ノードが、バックアップ記憶型親を有しない場合、ノードは、非記憶型親をデフォルト親として選択し、新たなランクを計算する。ノードが非記憶型ノードである場合、ノードは、そのＭＯＰを変更することなくＨ−ＤＩＯを送信する。一方、ノードが記憶型ノードである場合、ノードは、そのＭＯＰを１に変更することができ、ＭＯＰ＝１を有するＨ−ＤＩＯを送信する。

非記憶型バックアップ親が、そのＭＯＰを−１に変更した場合、子ノードは、その親集合からこの親を除去し、必要な場合には新たな親を発見することができる。非記憶型バックアップ親が、そのＭＯＰを２又は３に変更し、かつ、子ノードが、記憶型デフォルト親を有する場合、ノードは、デフォルト親を再選択することができる。ノードが非記憶型デフォルト親を有する場合、ノードは、この親をデフォルト親として選択し、新たなランクを計算する。ノードが非記憶型ノードである場合、ノードは、そのＭＯＰを変更することなくＨ−ＤＩＯパケットを送信する。一方、ノードが代理非記憶型ノードである場合、ノードは、２又は３に設定されたＭＯＰを有するＨ−ＤＩＯパケットを送信する。非記憶型デフォルト親が、そのＭＯＰを−１に変更した場合、子ノードは、その親集合からこの親を除去することができる。ノードは、非記憶型バックアップ親をデフォルト親として選択し、新たなランクを計算し、そのＭＯＰを変更することなくＨ−ＤＩＯを送信する。ノードは、必要な場合には、新たな親を発見することができる。非記憶型デフォルト親が、そのＭＯＰを２又は３に変更した場合、子ノードは、この親をデフォルト親として維持し、新たなランクを計算する。ノードが非記憶型ノードである場合、ノードは、そのＭＯＰを変更することなくＨ−ＤＩＯを送信する。ノードが代理非記憶型ノードである場合、ノードは、２又は３に設定されたＭＯＰを有するＨ−ＤＩＯパケットを送信する。

リーフノードが、そのＭＯＰを−１から０、１、２又は３に変更することが可能である。例えば、低電池ノードが、その電源を電池から電力グリッドに切り替える。近傍は、このＭＯＰ昇格を利用することができる。リーフノードが、そのＭＯＰを−１から０又は１に変更した場合、近傍は、このノードを非記憶型親として加えることができる。リーフノードが、そのＭＯＰを−１から２又は３に変更した場合、近傍は、このノードを記憶型親として加えることができる。最も重要なこととして、代理非記憶型ノードは、そのＭＯＰを記憶型ＭＯＰに戻すことができる。

ノードが、ＭＯＰを、リーフＭＯＰ又は非記憶型ＭＯＰから記憶型ＭＯＰに変更すると、このノードは、第１の階層ネットワークトポロジーに参加する。

ノードが、ＭＯＰを、記憶型ＭＯＰからリーフＭＯＰ又は非記憶型ＭＯＰに変更すると、このノードは、ルーティングテーブル及びソースルーティングデータベースを必要としない。ただし、このノードは、ルーティングテーブル及びソースルーティングデータベースを削除してもよいし、削除しなくてもよい。

Ｈ−ＲＰＬにおける上りデータパケット送達
目的関数及びルーティングメトリックは、Ｈ−ＤＯＤＡＧトポロジーにおける複数のルーティングパスの発見、すなわち、複数の親の選択において用いられる。親は、選択されると、或る期間の間、ネットワーク安定性を維持するために用いられる。クリティカルな疑問として、子はどの親にパケットを送信すべきか？という疑問がある。

従来のＲＰＬでは、データノードは、全ての上りパケットをそのデフォルト親に転送する。この手法は、バッファーオーバーフローに起因した深刻なデータパケットドロップと、デフォルト親が利用可能でないことに起因した深刻なパケット遅延とを引き起こす可能性がある。例えば、データノードが、電池ノードをデフォルト親として選択した場合、このデフォルト親は、場合によっては、電池エネルギーを節約するためにスリープする場合がある。この場合、デフォルト親はスリープ状態にあるので、子ノードがパケットをバッファリングしなければならない。これは、子ノードのバッファーオーバーフローを引き起こす可能性がある。別の例では、複数のデータノードが、同じノードをデフォルト親として選択する。したがって、これらの複数のノードは、全てのパケットを同じノードに送信し、これが、デフォルト親のバッファーオーバーフローを引き起こす可能性がある。

本発明の様々な実施形態によれば、データノードは、タスクＩＤに基づいて求められたサブＨ−ＤＯＤＡＧルートへの経路を有する親にデータパケットを転送し、データノードは、親のバッファー占有率に基づいて上りデータパケットを複数の親に分配する。この目標を達成する方法が提供される。

ネットワークトポロジーＨ−ＤＯＤＡＧを作成及び維持するのに用いられるルーティングメモリセクション２９０と異なり、ルーティングバッファーメモリセクション２８０は、ネットワーク動作中にデータパケットをバッファリングするのに用いられる。本発明の実施形態は、バッファー占有率指数（ＢＯＩ）を導入する。この指数は、バッファリングされた平均パケット数を、バッファーサイズ、すなわち、ルーティングバッファーメモリセクション２８０のサイズによって除算したものとして定義される。ＢＯＩを用いて、Ｈ−ＲＰＬプロトコルは、全てのパケットをデフォルト親に転送するのではなく、データパケットを親に分配する。

図１０Ａは、上りパケット送達のブロック図を示している。このブロック図では、ノードは、送信する上りデータパケット１００５を有する。Ｈ−ＲＰＬネットワークには、実行される複数のタスクが存在する。各データパケットは、タスクＩＤに関連付けられている。タスクＩＤに基づいて、ノードは、記録された目的関数及びルーティングメトリックを用いることによって、どのサブＨ−ＤＯＤＡＧルートがタスクに関係しているかを判断する（１０１０）。ノードは、ＳＲ１、ＳＲ２、…、ＳＲｍを含むｍ個のサブＨ−ＤＯＤＡＧルート１０２５に当該ノードを接続するｎ個の親を含む親集合１０２０を有すると仮定する。サブＨ−ＤＯＤＡＧルートが求められると、ノードは、図１０Ｂにおいて説明されるように、この決定されたサブＨ−ＤＯＤＡＧルートへの経路を有する好適な親Ｐａｒｅｎｔ−ｋを選択する（１０１５）。ノードは、サブＨ−ＤＯＤＡＧルートＩＤをパケットに含め、このパケットをＰａｒｅｎｔ−ｋに転送する（１０３０）。Ｐａｒｅｎｔ−ｋは、このパケットを受信すると、当該パケットからサブＨ−ＤＯＤＡＧルートＩＤを取得し（１０３５）、データノードが行うのと同様に好適な親を選択することによってパケットを中継する（１０４０）。このデータパケットは、最後にサブＨ−ＤＯＤＡＧルートＳＲｋに到達し（１０４５）、このサブＨ−ＤＯＤＡＧルートＳＲｋは、Ｈ−ＤＯＤＡＧトポロジーの第１の階層に従って、パケットをシンクノードに転送する（１０５０）。

図１０Ｂは、サブＨ−ＤＯＤＡＧルートへの経路を有する複数の親が存在する場合にデータパケットを転送する好適な親選択のブロック図を示している。このブロック図では、子ノードは、ｎ個の親を含む親集合１０２０を有する。各親は、そのＢＯＩを計算し、ＢＯＩを送信する（１０６０）。子ノードは、親からＢＯＩを受信し、受信されたＢＯＩに従って親をランキングする（１０７０）。高いＢＯＩを有する親ほど、低いランキングを取得し、低いＢＯＩを有する親ほど高いランキングを取得する。次に、子ノードは、ＢＯＩランキングに比例して上りパケットを親に分配する（１０８０）。最後に、子ノードは、親を選択して、上りデータパケットを転送する（１０９０）。

パケットを分配する利点として、以下のものがある。（１）ノードがパケットを複数の親に分配するので、負荷が均衡すること、（２）各親が子からパケットの一部分しか受信しないので、親のバッファーオーバーフローが低減されること、（３）子ノードはデフォルト親が利用可能になることのみを待機するのではなく、子ノードは全ての利用可能な親を利用するので、子のバッファーオーバーフローが低減されること、（４）バッファーオーバーフローに起因して廃棄されるパケットが少なくなるので、パケット送達レートが改善されること、及び（５）パケットの分配によってパケットバッファリング時間が減少するので、パケット遅延が低減されること。

親ノードは、そのＢＯＩをデータパケット等の他のパケットに含めて送信することができるか、又はそのＢＯＩを別のパケットとして送信する。ＢＯＩを計算する方法は以下のとおりである。

ＢＯＩを計算するために、ノードは、まず、所与の期間［ｔ_ｉ−１，ｔ_ｉ］においてバッファリングされた平均パケット数を計算する。時刻ｔにおいてバッファーにあるパケットの数をＮｏＰ（ｔ）とすると、バッファリングされている平均パケット数（ＡＮＰ）は、数学的に以下のように定義される。

期間［ｔ_ｉ−１，ｔ_ｉ］における測定値を用いて、ＡＮＰを推定することができる。期間［ｔ_ｉ−１，ｔ_ｉ］においてバッファーにプッシュされたパケットの数をＮｏＰ_ｉとし、期間［ｔ_ｉ−１，ｔ_ｉ］においてパケットがバッファリングされている平均時間量をＢＴ_ｉとすると、リトルの定理を用いて、ＡＮＰは、以下のように推定することができる。

また、ＢＯＩは、以下のように推定することができる。

ここで、Ｂ_Ｃは、バッファー容量、すなわち、ルーティングバッファーメモリセクション２８０のサイズを平均パケットサイズによって除算したものである。

本発明の様々な実施形態によれば、データノードは、ＭＯＰ＝−１をアナウンスしたノードにパケットを送信することができない。なぜならば、ＭＯＰ＝−１を有するノードは、リーフノードでしかあり得ないからである。

Ｈ−ＲＰＬにおける下りデータパケット送達
本発明の様々な実施形態によれば、ルート又は記憶型ノードは、下りパケットをデスティネーションに送信又は中継する２つの方法、すなわち、ソースルーティングを用いる方法又はルーティングテーブルを用いる方法を有する。ルート又は記憶型ルーターは、下りパケットを送信する複数の選択肢を有することが可能である。しかしながら、１つの実施形態は、ルーティングテーブルを用いて下りパケットを送信する。なぜならば、ルーティングテーブルはソースルーティングパスを必要とせず、パケットのサイズが小さくなるからである。パケットが小さくなることによって、より高い送達信頼性が得られる。非記憶型ノードは、ソースルーティングパスを用いて下りパケットを中継することしか行わない。

図１１Ａは、シンクノードが下りパケットを送信する（１１００）ブロック図を示している。シンクノードは、まず、デスティネーションノード１１９０がそのルーティングテーブル７６０に存在するか否かを確認する（１１１０）。存在する場合、シンクノードは、パケットを次ホップ記憶型ノードに転送する（１１２０）。存在しない場合、シンクノードは、そのソースルーティングデータベース７７５、すなわち親子データベースを用いることによって、シンクからデスティネーションノードへの完全なソースルーティングパスを作成する（１１３０）。次に、シンクノードは、パケットを次ホップ非記憶型ノードに転送する（１１４０）。パケットは、最終的には、デスティネーションノード１１９０に中継される。

図１１Ｂは、記憶型ノードが下りパケットを中継する（１１５０）ブロック図を示している。記憶型ノードも、まず、デスティネーションノード１１９０がそのルーティングテーブル７６０に存在するか否かを確認する（１１１０）。存在する場合、記憶型ノードは、パケットを次ホップ記憶型ノードに転送する（１１２０）。存在しない場合、記憶型ノードは、そのソースルーティングデータベース７７５、すなわち親子データベースを用いることによって、記憶型ノードからデスティネーションノードへの部分的なソースルーティングパスを作成する（１１６０）。次に、記憶型ノードは、パケットを次ホップ非記憶型ノードに転送する（１１４０）。パケットは、最終的には、デスティネーションノード１１９０に中継される。

図１１Ｃは、非記憶型ノードが下りパケットを中継する（１１７０）ブロック図を示している。非記憶型ノードは、受信されたソースルーティングパスにおいて次ホップ非記憶型ノードを見つける（１１８０）。次に、非記憶型ノードは、パケットを次ホップ非記憶型ノードに転送する（１１４０）。パケットは、最終的には、デスティネーションノード１１９０に中継される。

本発明の様々な実施形態によれば、シンクノード又は記憶型ノードは、ＭＯＰ＝−１又は０をアナウンスしたノードを介して下りパケットを転送することができない。なぜならば、ＭＯＰ＝−１を有するノードは、リーフノードでしかあり得ないからであり、ＭＯＰ＝０を有するノードは、下りルーティングをサポートしていないからである。シンクノード又は記憶型ノードは、ＭＯＰ＝−１又は０をアナウンスしたいずれかのノードを含むソースルーティングパスを作成することもできない。

本発明の上記で説明した実施形態は、多数の方法のうちの任意のもので実施することができる。例えば、実施形態は、ハードウェア、ソフトウェア又はそれらの組合せを用いて実施することができる。ソフトウェアで実施される場合、ソフトウェアコードは、単一のコンピューターに設けられるのか又は複数のコンピューター間に分散されるのかにかかわらず、任意の適したプロセッサ又はプロセッサの集合体において実行することができる。そのようなプロセッサは、１つ以上のプロセッサを集積回路部品に有する集積回路として実装することができる。ただし、プロセッサは、任意の適したフォーマットの回路類を用いて実装することができる。プロセッサは、当該技術分野において既知であるように、メモリ、送受信機及び入力／出力インターフェースに接続することができる。

本発明の方法、ネットワーク及びノードは、様々な種類の分野におけるマルチホップ無線ネットワークに利用可能である。

Claims (18)

1. 第１のシンクノードを有する第１のサブネットワークと第２のシンクノードを有する第２のサブネットワークとを含むサブネットワークのセットに分割されたマルチホップ異種無線ネットワークにおいてパケットをルーティングする方法であって、ノードが、前記第１のサブネットワークの少なくとも一部と、前記第２のサブネットワークの少なくとも一部とを形成し、該方法のステップは、前記ノードのプロセッサを用いて実行され、該方法は、
   前記ノードにおける配分ルーティングメモリ（ＡＲＭ）と、前記ノードの残りの予想ルーティング寿命（ＥＲＬ）との関数として、前記ノードの利用可能ルーティングリソースを求めることと、
   前記ノードによってサブネットワークに用いられるルーティングプロトコルと、前記サブネットワークにおける前記ノードの論理ロケーションと、前記ノードを通る前記サブネットワークにおけるデータトラフィックとの関数として、前記ノードの少なくとも１つの必要ルーティングリソースを求めることであって、前記第１のサブネットワークのための前記ノードの第１の必要ルーティングリソースを求めることと、前記第２のサブネットワークのための前記ノードの第２の必要ルーティングリソースを求めることと、を含み、前記第１の必要ルーティングリソースは、前記第２の必要ルーティングリソースと異なるものと、
   前記利用可能ルーティングリソース及び前記第１の必要ルーティングリソースを用いて、前記第１のサブネットワークにおける前記ノードの前記ルーティングのタイプを指定する第１の動作モード（ＭＯＰ）を求めることと、
   前記利用可能ルーティングリソース及び前記第２の必要ルーティングリソースを用いて、前記第２のサブネットワークにおける前記ノードの前記ルーティングのタイプを指定する第２のＭＯＰを求めることであって、前記第１のＭＯＰは該第２のＭＯＰと異なるものと、
   前記第１のＭＯＰに従って前記第１のサブネットワークにおいてパケットをルーティングするとともに、前記第２のＭＯＰに従って前記第２のサブネットワークにおいてパケットをルーティングすることと、
   を含む、方法。
2. 前記利用可能ルーティングリソース、前記第１の必要ルーティングリソース、及び前記第２の必要ルーティングリソースのうちの少なくとも１つの変化を検出することと、
   前記変化の検出に応答して、前記第１のＭＯＰ及び前記第２のＭＯＰのうちの一方又は組み合わせを更新することと、
   を更に含む、請求項１に記載の方法。
3. 前記第１のサブネットワーク及び前記第２のサブネットワーク内で送信される対応する制御パケットから、前記第１のサブネットワーク及び前記第２のサブネットワークにおける論理接続を求めること、
   を更に含む、請求項１に記載の方法。
4. 異なる目的関数及び異なるルーティングメトリックのうちの１つ又は組み合わせに従って、各サブネットワークが前記目的関数と前記ルーティングメトリックとの固有の組み合わせを有するように、前記ネットワークを前記サブネットワークに分割すること、
   を更に含む、請求項１に記載の方法。
5. 前記ネットワークの前記目的関数と前記ルーティングメトリックとの組み合わせのリストを、前記ネットワーク内で送信された制御パケットから取り出すことと、
   前記ノードの異なるタスクごとの各組み合わせの適合性を比較して、参加する１つ又は幾つかのサブネットワークを選択することと、
   前記選択されたサブネットワークに参加することと、
   を更に含む、請求項４に記載の方法。
6. 制御パケットのセットから前記ノードのネットワークパラメーターのセットを求めることを更に含み、前記ネットワークパラメーターのセットは、近傍ノードのＭＯＰと、前記第１のシンク又は前記第２のシンクまでの前記近傍ノードの相対距離を指定する前記近傍ノードのランクと、前記第１のサブネットワーク及び前記第２のサブネットワークのサイズと、前記第１のサブネットワーク及び前記第２のサブネットワークの目的関数のセット及びルーティングメトリックのセットと、Ｋホップ近傍ノードのルーティングプリファレンスのセットと、前記ノードの経路エントリーのセットと、前記ノードの親子エントリーのセットとのうちの１つ又は組み合わせを含む、請求項１に記載の方法。
7. 前記第１のＭＯＰ又は前記第２のＭＯＰは、リーフＭＯＰ、上りＭＯＰ、非記憶型ＭＯＰ、記憶型ＭＯＰ、又はマルチキャスト記憶型ＭＯＰであり、前記リーフＭＯＰに従って動作する前記ノードは、パケットをルーティングせず、前記上りＭＯＰに従って動作する前記ノードは、上りパケットのみをルーティングし、前記非記憶型ＭＯＰに従って動作する前記ノードは、経路エントリーを記憶することなく前記パケットをルーティングし、前記記憶型ＭＯＰに従って動作する前記ノードは、前記パケットをルーティングするとともに経路エントリーを記憶し、前記マルチキャスト記憶型ＭＯＰに従って動作する前記ノードは、前記パケットをルーティングするとともに経路エントリー及びマルチキャスト情報を記憶する、請求項１に記載の方法。
8. 前記ネットワークにおける前記ノードは、前記ノードのＭＯＰ、異種目的関数のセット及び異種ルーティングメトリックのセットに基づいて、階層型デスティネーション指向有向非巡回グラフ（Ｈ−ＤＯＤＡＧ）トポロジーに編成され、前記ノードの前記ＭＯＰ、前記目的関数及び前記ルーティングメトリックは、ネットワークの異なる部分では異なり、前記目的関数及び前記ルーティングメトリックは、目的関数と対応するルーティングメトリックとの間の１対多マップのセットにグループ化され、目的関数及びルーティングメトリックの第１のセットは、前記シンクノード及び記憶型ノードによってＨ−ＤＯＤＡＧトポロジーの第１の階層を作成するのに用いられ、目的関数及びルーティングメトリックの他のセットは、記憶型ノード、非記憶型ノード、上りノード及びリーフノードによってＨ−ＤＯＤＡＧトポロジーの他の階層を作成するのに用いられ、非記憶型ノード、上りノード及びリーフノードは、目的関数及びルーティングメトリックの第２のセットを用いてＨ−ＤＯＤＡＧトポロジーに参加する、請求項１に記載の方法。
9. 制御パケットは、Ｈ−ＤＯＤＡＧ情報オブジェクト（Ｈ−ＤＩＯ）パケットと、階層型デスティネーションアドバタイズメントオブジェクト（Ｈ−ＤＡＯ）パケットと、Ｈ−ＤＯＤＡＧ情報請求（Ｈ−ＤＩＳ）パケットとを含み、Ｈ−ＤＩＯパケットは、データノードから前記シンクノードへの上り経路を作成する情報と、前記Ｈ−ＤＩＯパケットを送信する前記ノードのＭＯＰとを含み、Ｈ−ＤＡＯパケットは、前記シンクノードから前記データノードへの下り経路を作成する情報と、デスティネーションノードのＭＯＰとを含み、Ｈ−ＤＡＯは、非記憶型Ｈ−ＤＡＯ（Ｎ−Ｈ−ＤＡＯ）と記憶型Ｈ−ＤＡＯ（Ｓ−Ｈ−ＤＡＯ）とを含み、Ｎ−Ｈ−ＤＡＯは、親子エントリーを含み、Ｓ−Ｈ−ＤＡＯは、ルーティングエントリーを生成する、請求項８に記載の方法。
10. 前記ノードは、該ノードの前記ＡＲＭ及び必要ルーティングメモリ（ＲＲＭ）に基づいて、以下の式に従ってＭＯＰを求め、
    

    

    ここで、
    

    

    は、正の閾値である、請求項７に記載の方法。
11. 前記ノードは、該ノードの予想ルーティング寿命（ＥＲＬ）に基づいて、以下の式に従ってＭＯＰを求め、
    

    

    ここで、
    

    

    は、正の閾値である、請求項７に記載の方法。
12. 前記ノードは、該ノードの前記ＡＲＭと、該ノードの必要ルーティングメモリ（ＲＲＭ）と、該ノードの予想ルーティング寿命（ＥＲＬ）との組み合わせに基づいて、以下の式に従ってＭＯＰを求め、
    

    

    ここで、
    

    

    は、正の閾値である、請求項７に記載の方法。
13. 異なる計算リソース及びエネルギーリソースを有する複数のノードを備えるマルチホップ無線ネットワークであって、該ネットワークは、目的関数とルーティングメトリックとの固有の組み合わせを有する複数のサブネットワークに分割され、少なくとも１つのノードが、複数のサブネットワークに参加し、異なるサブネットワークについて異なるタイプのルーティングを指定する異なる動作モード（ＭＯＰ）に従って動作し、
    前記ノードは、
    前記ノードにおける配分ルーティングメモリ（ＡＲＭ）と、前記ノードの残りの予想ルーティング寿命（ＥＲＬ）との関数として前記ノードの利用可能ルーティングリソースを求めることと、
    前記ノードによってサブネットワークに用いられるルーティングプロトコルと、前記サブネットワークにおける前記ノードの論理ロケーションと、前記ノードを通る前記サブネットワークにおけるデータトラフィックとの関数として、前記ノードの少なくとも１つの必要ルーティングリソースを求めることであって、第１のサブネットワークのための前記ノードの第１の必要ルーティングリソースを求めることと、第２のサブネットワークのための前記ノードの第２の必要ルーティングリソースを求めることと、を含み、前記第１の必要ルーティングリソースは、前記第２の必要ルーティングリソースと異なるものと、
    前記利用可能ルーティングリソース及び前記第１の必要ルーティングリソースを用いて、前記第１のサブネットワークにおける前記ノードの前記ルーティングのタイプを指定する第１の動作モード（ＭＯＰ）を求めることと、
    前記利用可能ルーティングリソース及び前記第２の必要ルーティングリソースを用いて、前記第２のサブネットワークにおける前記ノードの前記ルーティングのタイプを指定する第２のＭＯＰを求めることであって、前記第１のＭＯＰは該第２のＭＯＰと異なるものと、
    前記第１のＭＯＰに従って前記第１のサブネットワークにおいてパケットをルーティングするとともに、前記第２のＭＯＰに従って前記第２のサブネットワークにおいてパケットをルーティングすることと、
    を行うように構成されている、ネットワーク。
14. 前記ネットワークにおける前記ノードは、該ノードの動作のパラメーターの変更に応答して該ノードの前記ＭＯＰを変更する、請求項１３に記載のネットワーク。
15. 前記ＭＯＰは、リーフＭＯＰ、上りＭＯＰ、非記憶型ＭＯＰ、記憶型ＭＯＰ、又はマルチキャスト記憶型ＭＯＰであり、前記リーフＭＯＰに従って動作する前記ノードは、パケットをルーティングせず、前記上りＭＯＰに従って動作する前記ノードは、上りパケットのみをルーティングし、前記非記憶型ＭＯＰに従って動作する前記ノードは、経路エントリーを記憶することなく前記パケットをルーティングし、前記記憶型ＭＯＰに従って動作する前記ノードは、前記パケットをルーティングするとともに経路エントリーを記憶し、前記マルチキャスト記憶型ＭＯＰに従って動作する前記ノードは、前記パケットをルーティングするとともに経路エントリー及びマルチキャスト情報を記憶する、請求項１３に記載のネットワーク。
16. パケットを送受信する送受信機と、
    前記パケット、経路エントリー、親子エントリー、Ｋホップ近傍ルーティングプリファレンスの少なくとも一部分を記憶するメモリと、
    複数のサブネットワークの目的関数とルーティングメトリックとの組み合わせに基づいて前記サブネットワークに参加し、異なるサブネットワークの異なるタイプのルーティングを指定する異なる動作モード（ＭＯＰ）を求めるプロセッサと、
    を備える、異種無線ネットワークにおいてパケットをルーティングするノードであって、
    前記プロセッサは、
    前記ノードにおける配分ルーティングメモリ（ＡＲＭ）と、前記ノードの残りの予想ルーティング寿命（ＥＲＬ）との関数として前記ノードの利用可能ルーティングリソースを求めることと、
    前記ノードによってサブネットワークに用いられるルーティングプロトコルと、前記サブネットワークにおける前記ノードの論理ロケーションと、前記ノードを通る前記サブネットワークにおけるデータトラフィックとの関数として、前記ノードの少なくとも１つの必要ルーティングリソースを求めることであって、第１のサブネットワークのための前記ノードの第１の必要ルーティングリソースを求めることと、第２のサブネットワークのための前記ノードの第２の必要ルーティングリソースを求めることと、を含み、前記第１の必要ルーティングリソースは、前記第２の必要ルーティングリソースと異なるものと、
    前記利用可能ルーティングリソース及び前記第１の必要ルーティングリソースを用いて、前記第１のサブネットワークにおける前記ノードの前記ルーティングのタイプを指定する第１の動作モード（ＭＯＰ）を求めることと、
    前記利用可能ルーティングリソース及び前記第２の必要ルーティングリソースを用いて、前記第２のサブネットワークにおける前記ノードの前記ルーティングのタイプを指定する第２のＭＯＰを求めることであって、前記第１のＭＯＰは該第２のＭＯＰと異なるものと、
    前記第１のＭＯＰに従って前記第１のサブネットワークにおいてパケットをルーティングするとともに、前記第２のＭＯＰに従って前記第２のサブネットワークにおいてパケットをルーティングすることと、
    を行うように構成されている、ノード。
17. 前記プロセッサは、
    前記利用可能ルーティングリソース、前記第１の必要ルーティングリソース、及び前記第２の必要ルーティングリソースのうちの少なくとも１つの変化を検出することと、
    前記変化の検出に応答して、前記第１のＭＯＰ及び前記第２のＭＯＰのうちの一方又は組み合わせを更新することと、
    を行うように構成されている、請求項１６に記載のノード。
18. 前記ＭＯＰは、リーフＭＯＰ、上りＭＯＰ、非記憶型ＭＯＰ、記憶型ＭＯＰ、又はマルチキャスト記憶型ＭＯＰであり、前記リーフＭＯＰに従って動作する前記ノードは、パケットをルーティングせず、前記上りＭＯＰに従って動作する前記ノードは、上りパケットのみをルーティングし、前記非記憶型ＭＯＰに従って動作する前記ノードは、経路エントリーを記憶することなく前記パケットをルーティングし、前記記憶型ＭＯＰに従って動作する前記ノードは、前記パケットをルーティングするとともに経路エントリーを記憶し、前記マルチキャスト記憶型ＭＯＰに従って動作する前記ノードは、前記パケットをルーティングするとともに経路エントリー及びマルチキャスト情報を記憶する、請求項１６に記載のノード。

Images