(57)【特許請求の範囲】
【請求項１】
異なる計算リソースおよびエネルギーリソースを有する複数のノードを備えるマルチホップ無線異種ネットワークにおいて、各ノード内のプロセッサにより実行されるパケットをルーティングする方法であって、
前記マルチホップ無線異種ネットワークであるネットワーク内の前記各ノードにおいて、当該ノードの動作を変更する判断に用いられる一組のパラメーターを監視するステップであって、前記動作は、前記ルーティングのタイプを指定する動作モード（ＭＯＰ）に従って、前記ネットワーク内の各ノードにパケットをルーティングすることを含む、監視するステップと、
前記各ノードにおいて、前記動作の少なくとも１つのパラメーターの変化の検出に応答して、自身のノードの前記ＭＯＰを変更するステップと、
前記各ノードにおいて、前記自身のノードで変更された前記ＭＯＰについての情報を前記ネットワークにブロードキャストするステップと、
ブロードキャストされた前記情報を受信した前記各ノードにおいて、前記変更されたＭＯＰに従って前記パケットを前記ネットワーク内の各ノードにルーティングするステップと
を含み、該方法のステップは、前記ノードのプロセッサを用いて実行され、
前記ＭＯＰは、非記憶型ＭＯＰまたは記憶型ＭＯＰであり、
該非記憶型ＭＯＰに従って動作しているノードは、ルーティングテーブルを記憶せず、
該記憶型ＭＯＰに従って動作しているノードは、前記ルーティングテーブルと、前記ネットワークの少なくとも一部分の親子ペアを指定する親子テーブルとを記憶し、
前記ノードの前記ＭＯＰが前記記憶型ＭＯＰであり、前記ノードの親ノードのＭＯＰが前記非記憶型ＭＯＰである場合に、
前記記憶型ＭＯＰのノードにおいて、子孫ノードによって発信された制御パケットを受信するステップであって、該子孫ノードは、前記記憶型ＭＯＰのノードの直接の子でない、受信するステップと、
前記記憶型ＭＯＰのノードにおいて、前記制御パケットが前記子孫ノードの親子ペアを含まないか否かを検査するステップと、
前記記憶型ＭＯＰのノードにおいて、前記親子ペアが前記制御パケットにない場合、前記子孫ノードが前記記憶型ＭＯＰのノードの前記直接の子であることを指定する前記子孫ノードの前記親子ペアを前記制御パケット内に追加するステップと、
前記記憶型ＭＯＰのノードにおいて、前記制御パケットを前記記憶型ＭＯＰのノードの祖先に送信するステップと
をさらに含む、方法。
【請求項２】
前記一組のパラメーターは、前記ノードの利用可能なメモリ、前記ノードの処理能力、前記ノードの利用可能なエネルギー量、および前記ノードの通信能力のうちの１つまたは組み合わせを含む、請求項１に記載の方法。
【請求項３】
前記パケットは、制御パケットである、請求項１に記載の方法。
【請求項４】
前記パケットは、デスティネーション告知オブジェクト（ＤＡＯ）パケットを含み、前記ノードの前記ＭＯＰは、前記記憶型ＭＯＰであり、前記ノードは、該ノードの親ノードが記憶型ノードであることを示す識別情報を前記ＤＡＯ内に含める、請求項１に記載の方法。
【請求項５】
前記ノードの前記動作の前記一組のパラメーターの現在の値を求めるステップと、
前記一組のパラメーターを対応する一組の閾値と比較するステップと、
前記比較に基づいて前記ノードの前記ＭＯＰを決定するステップと
をさらに含む、請求項１に記載の方法。
【請求項６】
前記ノードの前記動作の前記一組のパラメーターの現在の値を求めるステップと、
前記一組のパラメーターの前記現在の値の加重結合としてリソースパラメーターを求めるステップと、
前記リソースパラメーターを閾値と比較して、前記ノードの前記ＭＯＰを生成するステップと
をさらに含む、請求項１に記載の方法。
【請求項７】
前記リソースパラメーターは、下式に従って求められ、
【数１】
0006461352.tif 000004
ここで、ＲＰは、リソースおよびネットワークの状態を組み合わせたパラメーターであり、ＡＭは、利用可能なランダムアクセスメモリ（ＲＡＭ）であり、ＭＣは、該ＲＡＭの容量であり、ＡＲは、利用可能な読み出し専用メモリ（ＲＯＭ）であり、ＲＣは、該ＲＯＭの容量であり、ＥＬは、前記ノードに利用可能なエネルギーレベルであり、ＭＥは、最大エネルギーレベルであり、ＳＳは、前記ノードの部分ＤＯＤＡＧのサイズであり、ＣＭ、ＣＲ、ＣＥおよびＣＮは、前記動作のパラメーターの重要度を重み付けする正の係数である、請求項６に記載の方法。
【請求項８】
前記ブロードキャストするステップは、
前記ノードの前記ＭＯＰを含むデスティネーション指向有向非巡回グラフ情報オブジェクト（ＤＩＯ）を生成するステップと、
前記ネットワークにおいて前記ＤＩＯをブロードキャストするステップと
を含む、請求項１に記載の方法。
【請求項９】
非記憶型ノードカウント（ＮＮＣ）を前記ＤＩＯに追加するステップ
をさらに含む、請求項８に記載の方法。
【請求項１０】
前記ネットワーク内のルートノードによって発信された前記ＤＩＯの一部分として前記ＮＮＣを受信するステップと、
前記ノードの前記ＭＯＰが非記憶型ＭＯＰである場合、前記ＮＮＣを１つだけ増加させるステップと
をさらに含む、請求項９に記載の方法。
【請求項１１】
前記ネットワーク内のルートノードによって発信されたデスティネーション指向有向非巡回グラフ情報オブジェクト（ＤＩＯ）の複数のコピーを受信するステップであって、該ＤＩＯの各コピーは、複数の近傍ノードのうちの１つから受信され、非記憶型ノードカウント（ＮＮＣ）を含む、受信するステップと、
より小さなＮＮＣを有する前記ＤＩＯを送信する前記近傍ノードのサブセットを前記ノードの親として選択するステップと
をさらに含む、請求項１０に記載の方法。
【請求項１２】
前記ノードの前記ＭＯＰは、前記記憶型ＭＯＰであり、前記方法は、
前記ノードの親のＭＯＰを受信するステップと、
前記親を指定することによってデスティネーション告知オブジェクト（ＤＡＯ）パケットを生成し、該ＤＡＯを祖先ノードに送信するステップと、
前記親の前記ＭＯＰが、前記記憶型ＭＯＰから前記非記憶型ＭＯＰに変更された場合には、子孫ノードが前記ノードの直接の子であることを示す親子ペアを有する制御パケットを送信するステップと、
前記親の前記ＭＯＰが、前記非記憶型ＭＯＰから前記記憶型ＭＯＰに変更された場合には、前記子孫ノードの前記親子ペアを前記制御パケットから除去し、該制御パケットを送信するステップと
をさらに含む、請求項１に記載の方法。
【請求項１３】
前記ノードの前記ＭＯＰは、前記非記憶型ＭＯＰであり、前記方法は、
前記ノードの親のＭＯＰを受信するステップと、
前記親を指定することなくデスティネーション告知オブジェクト（ＤＡＯ）パケットを生成し、該ＤＡＯを祖先ノードに送信するステップと
をさらに含む、請求項１に記載の方法。
【請求項１４】
異なる計算リソースおよびエネルギーリソースを有する複数のノードを備えるマルチホップ無線ネットワークであって、前記ノードは、ルーティングのタイプを指定する異なる動作モード（ＭＯＰ）に従って動作し、前記マルチホップ無線ネットワークであるネットワーク内の少なくとも１つのノードは、該ノードの動作を変更する判断に用いられるパラメーターの変化に応答して該ノードの前記ＭＯＰを変更し、
前記ＭＯＰは、非記憶型ＭＯＰまたは記憶型ＭＯＰであり、該非記憶型ＭＯＰに従って動作している前記ノードは、ルーティングテーブルを記憶せず、該記憶型ＭＯＰに従って動作している前記ノードは、前記ルーティングテーブルと、前記ネットワークの少なくとも一部分の親子ペアを指定する親子テーブルとを記憶し、
前記ノードの前記ＭＯＰが前記記憶型ＭＯＰであり、前記ノードの親ノードのＭＯＰが前記非記憶型ＭＯＰである場合に、
前記記憶型ＭＯＰのノードは、
前記記憶型ＭＯＰのノードの直接の子でない子孫ノードによって発信された制御パケットを受信し、
前記制御パケットが前記子孫ノードの親子ペアを含まないか否かを検査し、
前記親子ペアが前記制御パケットにない場合、前記子孫ノードが前記記憶型ＭＯＰのノードの前記直接の子であることを指定する前記子孫ノードの前記親子ペアを前記制御パケット内に追加し、
前記制御パケットを前記記憶型ＭＯＰのノードの祖先に送信する、
マルチホップ無線ネットワーク。
【請求項１５】
異種無線ネットワークにおいてパケットをルーティングするノードであって、
該ノードにエネルギーを供給する電池と、
パケットを送信および受信する送受信機と、
前記パケットの少なくとも一部分を記憶するメモリと、
電源装置の利用可能なエネルギー量および前記メモリの利用可能な部分のうちの一方のまたは組み合わせを監視し、前記利用可能なエネルギー量および前記メモリの前記利用可能な部分のうちの一方のまたは組み合わせに基づいて、前記パケットのルーティングのタイプを指定する該ノードの動作モード（ＭＯＰ）を決定するプロセッサと
を備え、
前記ＭＯＰは、非記憶型ＭＯＰまたは記憶型ＭＯＰであり、該非記憶型ＭＯＰに従って動作している前記ノードは、ルーティングテーブルを記憶せず、該記憶型ＭＯＰに従って動作している前記ノードは、前記ルーティングテーブルと、前記異種無線ネットワークであるネットワークの少なくとも一部分の親子ペアを指定する親子テーブルとを記憶し、
前記ノードの前記ＭＯＰが前記記憶型ＭＯＰであり、前記ノードの親ノードのＭＯＰが前記非記憶型ＭＯＰである場合に、
前記記憶型ＭＯＰのノードは、
前記記憶型ＭＯＰのノードの直接の子でない子孫ノードによって発信された制御パケットを受信し、
前記制御パケットが前記子孫ノードの親子ペアを含まないか否かを検査し、
前記親子ペアが前記制御パケットにない場合、前記子孫ノードが前記記憶型ＭＯＰのノードの前記直接の子であることを指定する前記子孫ノードの前記親子ペアを前記制御パケット内に追加し、
前記制御パケットを前記記憶型ＭＯＰのノードの祖先に送信する、
ノード。
【請求項１６】
前記プロセッサは、前記ＭＯＰの変更に応答して、前記ＭＯＰについての情報を前記ネットワークにブロードキャストするように前記送受信機に命令する、請求項１５に記載のノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、無線ネットワークにおいてパケットをルーティングすることに関し、特に、異種のリソースおよび能力を有するノードを含む無線ネットワークにおいてパケットをルーティングすることに関する。
【背景技術】
【０００２】
無線ネットワーク内のノードのリソースおよび能力に基づいて、無線ネットワークは、同種ネットワークまたは異種ネットワークとして分類することができる。従来の無線センサーネットワーク等の同種無線ネットワークでは、全てのノードが、同一のリソースおよび能力を有する。他方、無線マシンツーマシン（Ｍ２Ｍ）ネットワーク等の異種無線ネットワークでは、ノードは、異なるリソースおよび能力を有する。
【０００３】
異種無線ネットワークは、モノのインターネット（ＩＯＴ）、産業オートメーションおよびスマートグリッドを含む新興アプリケーションにおいて用いられる。異種無線ネットワーク内のいくつかのノードは、メモリ、記憶装置、プロセス電力、エネルギー供給、および通信能力等の十分なリソースを有する。他のノードは、制約されたリソースおよび能力を有する。その結果、異種ネットワーク内のノードの機能は変化する可能性がある。ノードの中には、多くの機能を実行することができるものもあれば、限られた機能しか実行することができないものもある。
【０００４】
ネットワークノードは物理デバイスを表す。物理デバイスは、一旦製造されると、そのリソースおよび能力を変更することは実際的でない可能性がある。この変更には、デバイス上で動作してそれらの機能を当該デバイスに適応させる技術が必要となる。ルーティングは、ネットワークトポロジーを構成するとともにネットワーク内でパケットを通信するネットワーキング技術のうちの１つである。同一のノードの集合を用いて、異なるルーティングアルゴリズムが、異なるように機能する異なるネットワークを形成することができる。いくつかのルーティングアルゴリズムは、効率的なネットワークを構成し、いくつかのルーティングアルゴリズムは、非効率的なネットワークを構成する。
【０００５】
同種無線ネットワーク向けに設計された従来のルーティング方法は、ノードが異種であることを考慮せず、限られたリソースを有するノードに適していない場合もあれば、より強力なノードのリソースを浪費する場合もある。例えば、ルーティング方法が、より強力なノードを採用するように設計および開発されている場合、このルーティング方法は、それよりも強力でないノードが用いることができず、これは、ノードの隔離をもたらす可能性がある。ルーティング方法が、平均的に強力なノードに基づいて設計および開発されている場合、それよりも強力なノード上のリソースは浪費され、それよりも強力でないノード上のリソースは、それらのノードがネットワークに参加することを妨げる場合もある。
【０００６】
例えば、アドホックオンデマンド距離ベクトル（ＡＯＤＶ）ルーティングは、ノードが十分なメモリを有すると仮定し、ノードが、受信したあらゆる経路要求および経路応答のルーティング情報を記憶することを必要とする。ノードは、順方向経路エントリーを記憶するとともに、逆方向ルーティング情報も記憶する。大規模ネットワークでは、ＡＯＤＶは、ノードが比較的大きなメモリ容量を有することを必要とする。このため、センサーノードは、ＡＯＤＶに基づくルーティングアルゴリズムを容易にサポートすることができない。
【０００７】
低電力高損失ネットワークのＩＰｖ６ルーティングプロトコル（ＲＰＬ）は、インターネットエンジニアリングタスクフォース（ＩＥＴＦ）によって近年開発されたルーティングプロトコルであり、標準規格ＲＦＣ６５５０として公開されている。ＲＰＬは、ノードのメモリ容量を考慮し、ルーティングメカニズムを４つの動作モード（ＭＯＰ）、すなわち、ＭＯＰ−０、ＭＯＰ−１、ＭＯＰ−２およびＭＯＰ−３に分類する。ＭＯＰ−０によると、ＲＰＬは、ノードからルートノードへの単方向ルーティング、すなわち、上りルーティングしかサポートしない。ＭＯＰ−１は、双方向ルーティングを可能にし、下りルーティングにソースルーティングを用いる。メモリ容量を削減するために、ＭＯＰ−１ノードは、他のいずれのノードのルーティング情報も記憶しない。その結果、ＭＯＰ−１は非記憶型モードと呼ばれる。ＭＯＰ−２は、双方向ルーティングをサポートし、下りルーティングにルーティングテーブルを用いる。ＭＯＰ−２ノードは、ノードの経路エントリーを部分木に記憶する。したがって、ＭＯＰ−２は記憶型モードと呼ばれる。しかしながら、ＭＯＰ−２によると、下りマルチキャストがサポートされない。ＭＯＰ−３は、下りマルチキャストをサポートする。したがって、ＭＯＰ−３も記憶型モードと呼ばれる。ＭＯＰ−２およびＭＯＰ−３は、ノードが、経路エントリーを記憶するより大きなメモリ容量を有することを必要とする。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、ＲＰＬは、ネットワーク内の全てのルーターノードについて１つのＭＯＰしか認めず、ルーターノードが異なるＭＯＰを有することを認めない。全てのルーターノードは、ルートノードと同じＭＯＰを有しなければならない。或るノードがルートノードのＭＯＰと異なるＭＯＰを有する場合、このノードは、リーフノードにしかなることができず、ネットワークを拡張することができない。
【０００９】
したがって、ノードの異なるリソースおよび能力に基づいて自らのルーティング機能を適応させるリソースアウェアルーティング方法を提供することが望ましい。
【課題を解決するための手段】
【００１０】
本発明のいくつかの実施の形態は、無線マルチホップネットワークでは、異なるリソースを有するノードが、ノードによって用いられるルーティングのタイプを定義する異なる動作モード（ＭＯＰ）を有することができるという認識に基づいている。例えば、ＭＯＰは、ノードが単方向ルーティングまたは双方向ルーティング、記憶型ルーティングまたは非記憶型ルーティングを用いることを規定することができる。
【００１１】
本発明のいくつかの実施の形態は、ノードが、ノードの利用可能なメモリ、ノードの処理能力、ノードの利用可能なエネルギー量、ノードの通信能力、および少なくとも１つの近傍ノードのＭＯＰのうちの１つまたは組み合わせ等の利用可能なリソースの変化に応答して自身のＭＯＰを更新することができるという認識に基づいている。異なるＭＯＰは異なるリソースに所定の方法で対応することができ、より多くのリソースがノードに利用可能であるとき、ＭＯＰの機能を増加させることができることがさらに認識されている。そのようにして、ノードは、自身のＭＯＰを利用可能なリソースの表示として他のノードにシグナリングすることができる。
【００１２】
本発明のいくつかの実施の形態では、ノードは、他のノードのＭＯＰによって示されるような当該他のノードのリソースを考慮してルーティングを実行する。また、いくつかの実施の形態は、仮想ペアレンティングまたは代行ペアレンティングの概念を用いて、異なるＭＯＰを有するノードのマージを容易にする。例えば、１つの実施の形態では、或るＭＯＰを有するノードは、当該ノードが、異なるＭＯＰの近傍の子ノードの親であることをネットワーク内の他のノードにシグナリングすることができる。このとき、実際には、この子ノードは親ノードからマルチホップ離れている。
【００１３】
本発明のいくつかの実施の形態は、異なるＭＯＰを有するノードを備える異種ネットワークを有し、ノードの動作のパラメーターの変化に応答して少なくとも１つのノードのＭＯＰを変更することによって、ネットワークの状態の変化にルーティング方法を適応させる。
【００１４】
したがって、本発明の１つの実施の形態は、異なる計算リソースおよびエネルギーリソースを有するノードを備えるマルチホップ無線異種ネットワークにおいてパケットをルーティングする方法であって、前記ネットワーク内のノードの動作の一組のパラメーターを監視することであって、前記動作は、前記ルーティングのタイプを指定する動作モード（ＭＯＰ）に従って、前記ネットワークの前記ノードにパケットをルーティングすることを含むことと、前記動作の少なくとも１つのパラメーターの変化の検出に応答して、前記ノードの前記ＭＯＰを変更することと、前記変更されたＭＯＰについての情報を前記ネットワークにブロードキャストすることと、前記変更されたＭＯＰに従って前記パケットを前記ノードにルーティングすることとを含み、該方法のステップは、前記ノードのプロセッサを用いて実行される、方法を開示する。
【００１５】
別の実施の形態は、異なる計算リソースおよびエネルギーリソースを有する複数のノードを備えるマルチホップ無線ネットワークであって、前記ノードは、ルーティングのタイプを指定する異なる動作モード（ＭＯＰ）に従って動作し、前記ネットワーク内の少なくとも１つのノードは、該ノードの動作のパラメーターの変化に応答して該ノードの前記ＭＯＰを変更する、マルチホップ無線ネットワークを開示する。
【００１６】
さらに別の実施の形態は、異種無線ネットワークにおいてパケットをルーティングするノードであって、該ノードにエネルギーを供給する電池と、パケットを送信および受信する送受信機と、前記パケットの少なくとも一部分を記憶するメモリと、電源装置の利用可能なエネルギー量および前記メモリの利用可能な部分のうちの一方のまたは組み合わせを監視し、前記利用可能なエネルギー量および前記メモリの前記利用可能な部分のうちの一方のまたは組み合わせに基づいて、前記パケットのルーティングのタイプを指定する該ノードの動作モード（ＭＯＰ）を決定するプロセッサとを備える、ノードを開示する。
【図面の簡単な説明】
【００１７】
【図１】本発明のいくつかの実施の形態による異種マルチホップ無線ネットワークの概略図である。
【図２Ａ】本発明のいくつかの実施の形態によるマルチホップ無線異種ネットワークにおいてパケットをルーティングする方法のブロック図である。
【図２Ｂ】本発明のいくつかの実施の形態による図１のネットワークを形成することに関与することができるノードの構造の概略図である。
【図３Ａ】本発明の１つの実施の形態によるノードのＭＯＰを決定および／または変更する方法のブロック図である。
【図３Ｂ】本発明の別の実施の形態によるノードのＭＯＰを決定および／または変更する方法のブロック図である。
【図４Ａ】本発明のいくつかの実施の形態の原理を用いたネットワークの一例の概略図である。
【図４Ｂ】本発明のいくつかの実施の形態によるネットワークを通じてリソースメトリックを伝播する方法のブロック図である。
【図４Ｃ】本発明のいくつかの実施の形態による、リソースメトリックを用いて経路を求める方法のブロック図である。
【図５】本発明の１つの実施の形態によるリソースアウェア経路発見の方法のブロック図である。
【図６】本発明のいくつかの実施の形態による制御パケットルーティングの一例である。
【図７Ａ】本発明のいくつかの実施の形態による代行親ノードを用いるネットワークの一例の概略図である。
【図７Ｂ】本発明のいくつかの実施の形態によるアクティブペアレンティングを定義する親子関係を指定する方法のブロック図である。
【図７Ｃ】本発明のいくつかの実施の形態によるアクティブな親に起因した図７Ａのネットワークの変換の一例の概略図である。
【図８Ａ】本発明のいくつかの実施の形態による異種無線ネットワークにおける経路の圧縮の概略図である。
【図８Ｂ】本発明のいくつかの実施の形態による異種無線ネットワークにおける経路の圧縮の概略図である。
【図９Ａ】本発明のいくつかの実施の形態による異種無線ネットワークにおけるランク割り当ておよび代行親を有するネットワークの一例の概略図である。
【図９Ｂ】本発明のいくつかの実施の形態による図９Ａにおけるネットワークから変換された圧縮ネットワークの一例の概略図である。
【図１０】本発明のいくつかの実施の形態による、下りパケットをデスティネーションに送信する３つの方法の概略図である。
【図１１】本発明のいくつかの実施の形態によるノードの適応的ＭＯＰ変更のブロック図である。
【発明を実施するための形態】
【００１８】
図１は、本発明のいくつかの実施の形態による異種マルチホップ無線ネットワーク１００の概略図を示している。このネットワークは、異なる計算リソースおよびエネルギーリソースを有する複数のノードを備える。いくつかのノードは、パケットを任意のルートに直接送信することができる一方、ノードのうちのいくつかは、パケットをいずれのルートにも直接送信することができない。その代わり、パケットは、まず、中間ノードまたは中継ノードに送信され、これらの中間ノードまたは中継ノードが、次に、パケットをルートに中継する。換言すれば、パケット送信は、マルチホップ形式で行われる。
【００１９】
ネットワーク１００内のノードは、ルーティングのタイプを指定する異なる動作モード（ＭＯＰ）に従って動作する。例えば、異なるノードのＭＯＰは、非記憶型ＭＯＰまたは記憶型ＭＯＰとすることができる。非記憶型ＭＯＰに従って動作しているノードは、本明細書では、非記憶型ノードとも呼ばれ、ルーティングテーブルを記憶せず、記憶型ＭＯＰに従って動作しているノードは、本明細書では記憶型ノードとも呼ばれ、ルーティングテーブルと、ネットワークの少なくとも一部分の親子ペアを指定する親子テーブルとを記憶する。
【００２０】
例えば、ネットワーク１００は、ルートノード（Ｒ）１０１、ＭＯＰ−０ノード（Ｍ０）１１０、ＭＯＰ−１ノード（Ｍ１）１２０、ＭＯＰ−２ノード（Ｍ２）１３０、およびＭＯＰ−３ノード（Ｍ３）１４０を備える。これらのノードおよびルートは、無線リンク１５０を用いて無線メッシュネットワークを形成する。リンクの方向は、物理ノード到達可能性を示している。
【００２１】
ネットワーク１００内の少なくとも１つのノードは、当該ノードの動作のパラメーターの変化に応答して、当該ノードのＭＯＰを変更する。そのようにして、ノードは、ネットワーク状態と、当該ノードに利用可能なリソースとに基づいて自身のルーティング機能を動的に調整することができる。
【００２２】
図２Ａは、本発明のいくつかの実施の形態による、異なる計算リソースおよびエネルギーリソースを有するノードを備えるマルチホップ無線異種ネットワークにおいてパケットをルーティングする方法のブロック図を示している。本方法は、ネットワーク内のノードの動作の一組のパラメーターを監視する（２１０）ことを含み、この動作は、ネットワークのノードにパケットを、そのノードのＭＯＰに従ってルーティングすることと、動作の少なくとも１つのパラメーターの変化２１５の検出に応答して、そのノードのＭＯＰを変更する（２２０）こととを含む。
【００２３】
いくつかの実施の形態では、本方法は、変更されたＭＯＰ２２５についての情報をネットワークにブロードキャストし（２３０）、変更されたＭＯＰ２２５に従ってネットワークのノードにパケットをルーティングする（２４０）。いくつかの実施の形態では、ノードの変更されたＭＯＰは、ノードに利用可能なリソースを示す。例えば、異なるＭＯＰは、所定の方法で異なるリソースに対応する。すなわち、ノードに利用可能なリソースがより多くなれば、ＭＯＰの機能もより多くなる。したがって、ブロードキャストする（２３０）ことによって、ネットワークの他のノードは、それらのルーティングを上記ノードのリソースに適応させることが可能になる。
【００２４】
図２Ｂは、図１のネットワークを形成することに関与することができるノード２０１の構造を概略的に示している。このノードは、データパケットおよび制御パケット等のパケットを送受信する送受信機を備える。この送受信機は、受信機２５５および送信機２５０のうちの一方または組み合わせを含むことができる。このノードは、当該ノードにエネルギーを供給する電池等の電源装置２６０と、送受信機によって受信または送信されたパケットの少なくとも一部分を記憶するメモリ２７０とを備えることができる。
【００２５】
ノードは、当該ノードの動作のパラメーターを監視し、当該ノードのＭＯＰを決定または変更するプロセッサ２８０も備える。例えば、一組のパラメーターは、ノードの利用可能なメモリ、ノードの処理能力、ノードの利用可能なエネルギー量、ノードの通信能力、および少なくとも１つの近傍ノードのＭＯＰのうちの１つまたは組み合わせを含むことができる。
【００２６】
例えば、プロセッサ２８０は、電源装置の利用可能なエネルギー量および／またはメモリの利用可能な部分を監視することができ、利用可能なエネルギー量および／またはメモリの利用可能な部分に基づいてノードのＭＯＰを決定することができる。プロセッサは、ＭＯＰの変更に応答して、ＭＯＰについての情報をネットワークにブロードキャストするように送受信機に命令することもできる。
【００２７】
いくつかの実施の形態は、４つの異なるタイプのＭＯＰ、すなわち、ＭＯＰ−０、ＭＯＰ−１、ＭＯＰ−２およびＭＯＰ−３を用いる。例えば、１０ＫＢ（１ＫＢ＝１０２４バイト）よりもはるかに少ないランダムアクセスメモリ（ＲＡＭ）および１００ＫＢよりもはるかに少ない読み出し専用メモリ（ＲＯＭ）を有するノードは、そのＭＯＰを０に設定する。このノードのクラスは、下りルーティングをサポートすることができない。約１０ＫＢのＲＡＭおよび約１００ＫＢのＲＯＭを有するノードは、そのＭＯＰを０または１に設定することを選ぶことができる。このノードのクラスは、非記憶型下りルーティングを行うことができる。約５０ＫＢのＲＡＭおよび約２５０ＫＢのＲＯＭを有するノードは、そのＭＯＰを０、１、または２に設定することを選ぶことができる。このノードのクラスは、記憶型下りルーティングを行うことができるが、下りマルチキャストをサポートしない場合がある。５０ＫＢよりもはるかに多くのＲＡＭおよび２５０ＫＢよりもはるかに多くのＲＯＭを有するノードは、そのＭＯＰを０、１、２、または３に設定することを選ぶことができる。このノードのクラスは、記憶型下りルーティングを行うことができ、下りマルチキャストをサポートする十分なメモリを有する。
【００２８】
ノードは、そのＭＯＰを決定する際にＲＡＭおよびＲＯＭ以外のリソースを考慮することができる。例えば、約１０％の電池エネルギーを有するノードは、ＲＡＭおよびＲＯＭにかかわらず、そのＭＯＰ＝０に設定する。約２０％の電池エネルギーを有するノードは、ＲＡＭおよびＲＯＭにかかわらず、そのＭＯＰを０または１に設定する。電池エネルギーが２０％よりも多い場合、ノードは、ＲＡＭおよびＲＯＭに基づいてそのＭＯＰを設定する。
【００２９】
ノードは、そのリソース使用量およびネットワーク状態に基づいてそのＭＯＰを動的に変更することができる。例えば、十分なＲＡＭおよびＲＯＭを有する電池式ノードは、そのＭＯＰを３に初期設定することができる。ネットワークの動作中、その電池レベルが低くなった場合、ノードは、デッドノードに起因したネットワークテアダウンを回避するために、そのＭＯＰをより低い値に変更することができる。別の例として、約５０ＫＢのＲＡＭおよび約２５０ＫＢのＲＯＭを有するノードは、ＭＯＰを２に初期設定する。ネットワークの動作中、ノードが、そのメモリが下りルーティングテーブルを記憶するのに十分でないおよび／またはその付近に十分なＭＯＰ−３ノードが存在することを検出した場合、ノードは、そのＭＯＰ値を下げることができる。
【００３０】
図３Ａは、本発明の１つの実施の形態によるノードのＭＯＰを決定および／または変更する方法のブロック図を示している。この実施の形態は、ノードの動作の一組のパラメーターの現在の値を求め（３１０）、この一組のパラメーターを対応する一組の閾値と比較する（３２０）。例えば、ノードが、利用可能なエネルギーおよび利用可能なメモリ等の２つのパラメーターのみを監視している場合、一組の閾値は、２つの異なる閾値、すなわち、メモリ用に１つの閾値と、エネルギー用にもう１つの閾値とを含むことができる。ノードは、いくつかの可能なタイプのＭＯＰのうちの１つを決定するための各監視パラメーターの複数の閾値を含むこともできる。
【００３１】
ノードは、この比較の結果に基づいてそのＭＯＰを決定する（３３０）。例えば、ノードは、少なくとも１つのパラメーターの変化が閾値と交差した場合、そのＭＯＰを変更することができる。例えば、ノードは、利用可能な最低位のリソースに対応するＭＯＰを選択することができる。
【００３２】
図３Ｂは、本発明の別の実施の形態によるノードのＭＯＰを決定および／または変更する方法のブロック図を示している。この実施の形態では、ノードは、一組のパラメーターの現在の値の加重結合としてリソースパラメーターを求め（３４０）、このリソースパラメーターを閾値と比較して（３５０）、ノードのＭＯＰを生成する。
【００３３】
例えば、リソースパラメーターは、以下の式に従って求めることができる。
【数１】
0006461352.tif 000002
ここで、ＲＰは、リソースおよびネットワークの状態を組み合わせたパラメーターであり、ＡＭは利用可能なＲＡＭであり、ＭＣはＲＡＭ容量であり、ＡＲは利用可能なＲＯＭであり、ＲＣはＲＯＭ容量であり、ＥＬはエネルギーレベルであり、ＭＥは最大エネルギーレベルであり、ＳＳは、このノード自体を含むノードの部分木のサイズを表し、ＣＭ、ＣＲ、ＣＥおよびＣＮは、それぞれＲＡＭ、ＲＯＭ、エネルギーおよびネットワーク状態の重要度を反映する正の係数である。式（１）に基づいて、ノードのＭＯＰを変更する当該ノード用の３つの閾値ＴＨ０、ＴＨ１およびＴＨ２を定義することができる。例えば、ノードのＲＰが減少してＴＨ０と交差した場合、ノードは、そのＭＯＰを１から０に変更する。ノードのＲＰが増加してＴＨ２と交差した場合、ノードは、そのＭＯＰを２から３に変更する。ＴＨ０、ＴＨ１およびＴＨ２の実際の値は、アプリケーション次第である。
【００３４】
ＲＰＬの概略
ネットワーク内のノードは、異なるＭＯＰを用いることによって様々なリソースをシグナリングするので、いくつかの実施の形態は、リソースアウェアルーティングを用いて、パケットをノードからルートにおよびルートからノードにルーティングする。本発明のいくつかの実施の形態は、ＲＰＬをリソースアウェアルーティングに適応させる。
【００３５】
ＲＰＬは、ネットワーク内のノードを有向非巡回グラフ（ＤＡＧ）として編成し、このＤＡＧを１つまたは複数のデスティネーション指向ＤＡＧ（ＤＯＤＡＧ）に分割する。ＤＡＧは、ＤＯＤＡＧが、ＤＯＤＡＧルートとも呼ばれる１つのみのデータシンクを有するように分割される。ＲＰＬは、異なるタイプのパケットを用いて、ノードからルートへの上り経路と、ルートからノードへの下り経路とを作成する。
【００３６】
ＤＯＤＡＧトポロジーと、ノードからルートへの上り経路とを構築するために、ＲＰＬは、ＤＯＤＡＧ情報オブジェクト（ＤＩＯ）パケットを用いる。このパケットは、ルートによって発信され、ネットワーク内の全てのノードに伝播する。ＤＩＯパケットは、ＤＯＤＡＧトポロジーを構築する情報を含む。例えば、ＤＯＤＡＧバージョンを識別するRPLInstanceID、DODAGIDおよびDODAGVersionNumberが同封され、ノードのランクは、ＤＯＤＡＧのルートに対する他のノードを基準とした相対的なノードの個々の位置を規定する。ＤＩＯパケットは、ネットワークのＭＯＰを示すＭＯＰフィールドも含む。ＭＯＰフィールドの値は、ルートによって設定され、他のノードがこれを変更することは認められない。ＤＩＯパケットを伝播させるために、ルートはＤＩＯパケットをブロードキャストする。ルートの付近のノードは、ＤＩＯパケットを受信し、ＤＯＤＡＧに参加することを決定すると、自身のランクを求め、更新されたＤＩＯパケットを自身の近傍ノードにブロードキャストする。あらゆるノードがＤＯＤＡＧに参加するまで、ＤＩＯパケットは、ＤＯＤＡＧトポロジーが波面のように構築されるよう全ての方向に伝播される。
【００３７】
ルートから他のノードへの下り経路を作成するために、ＲＰＬは、デスティネーション告知オブジェクト（ＤＡＯ）パケットを用いる。ＤＡＯパケットは上り方向に送信される。一方、ネットワークのＭＯＰに応じて、ＤＡＯパケットの内容およびデスティネーションは変化する。ＭＯＰ−０によると、ＲＰＬは、下りルーティングをサポートせず、したがって、ネットワーク内の全てのノードはＤＡＯパケットを送信しない。ＭＯＰ−１によると、全てのノードは、非記憶型ＤＡＯパケットを送信することしか認められない。ＭＯＰ−１では、ＤＡＯパケットのデスティネーションはルートである。したがって、ソースアドレスおよびデスティネーションアドレスは、グローバルＩＰｖ６アドレスである。非記憶型ＤＡＯパケットは、ルートまでホップごとに中継され、中間ノードは、受信されたＤＡＯパケットを処理せず、いずれの情報も記憶しない。ＭＯＰ−１で動作しているノードが非記憶型ＤＡＯパケットを構築するとき、このノードは自身の親を指定する。ルートは、この情報を用いて、ネットワーク内の各ノードの下り経路を作成する。ＭＯＰ−１で動作しているノードは、他のいずれのノードの下り経路情報も記憶しない。したがって、ＭＯＰ−１で動作しているノードは、非記憶型ノードと呼ばれる。
【００３８】
ＭＯＰ−２によると、全てのノードは、記憶型ＤＡＯパケットを送信することのみが認められる。非記憶型ＤＡＯと異なり、記憶型ＤＡＯパケットのデスティネーションは、ノードの親である。すなわち、記憶型ＤＡＯは、１つのホップにわたってのみ送信される。したがって、記憶型ＤＡＯパケットのソースアドレスおよびデスティネーションアドレスは、リンクローカルＩＰｖ６アドレスである。記憶型ＤＡＯでは、ノードは、自身の親を指定しない。なぜならば、記憶型ＤＡＯは、その親にしか送信されないからである。ＭＯＰ−２モードでは、ノードは、受信されたＤＡＯパケットを処理し、ＤＡＯパケットに含まれる各デスティネーションの経路エントリーを自身のルーティングテーブルに追加する。ＭＯＰ−２で動作しているノードは、新たな記憶型ＤＡＯパケットを生成して、自身の部分ＤＯＤＡＧ内のデスティネーションをルートに伝播することも担当する。下りルーティングは、その場合、中間ノードのルーティングテーブルを用いて中間ノードによって実現される。
【００３９】
ＭＯＰ−３によると、下りルーティングメカニズムは、ＭＯＰ−２のものと同じである。ＭＯＰ−２ノードまたはＭＯＰ−３ノードは、下り経路情報を記憶する。したがって、ＭＯＰ−２またはＭＯＰ−３で動作しているノードは、記憶型ノードとも呼ばれる。ＤＩＯをＲＰＬノードに要請する、すなわち、新たな経路を発見するのに、ＤＯＤＡＧ情報要請（ＤＩＳ）パケットが用いられる。
【００４０】
ＲＰＬは、ノードが、複数の親、すなわち複数の経路を有することを可能にする。親のうちの１つは好ましい親として選択され、他の親はバックアップ親として選択される。好ましい親は、上りパケット転送のためのデフォルトの次のホップとして用いられる。好ましい親が利用可能でない場合、バックアップ親を用いることができる。ＲＰＬは、ノードがランクを決定し親を選択するのを支援するための目的関数（ＯＦ）を用いる。
【００４１】
ＲＰＬは、ルーターの役割を行う全てのノードが、ルートと同じＭＯＰを有しなければならないことを必要とする。すなわち、ルートがそのＭＯＰを０に設定している場合、全てのルーターノードもそれらのＭＯＰを０に設定しなければならず、ルートがそのＭＯＰを１に設定している場合、全てのルーターノードもそれらのＭＯＰを１に設定しなければならず、ルートがそのＭＯＰを２に設定している場合、全てのルーターノードもそれらのＭＯＰを２に設定しなければならず、ルートがそのＭＯＰを３に設定している場合、全てのルーターノードもそれらのＭＯＰを３に設定しなければならない。
【００４２】
リソースアウェアルーティング
本発明のいくつかの実施の形態は、ノードが、他のノードのＭＯＰによって示されるような他のノードのリソースを考慮して、そのルーティングを実行すべきであるという認識に基づいている。加えて、いくつかの実施の形態は、加えてまたは代替的に、２つのノード間の経路を考慮したルーティングメトリックを用いて、リソースアウェアメトリックが、ノードの異種性を利用した経路全体の品質を考慮すべきであるという認識に基づいている。
【００４３】
図４Ａは、ＤＩＯパケット４２０が、２つの経路Ｒ１：Ｒ→Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｓ６およびＲ２：Ｒ→Ｓ１→Ｓ２→Ｓ３→Ｓ４→Ｓ５→Ｓ６に沿ってルートＲ  ４００からノードＳ６  ４１０に伝播するネットワークの一例を示している。ここで、Ｎ１〜Ｎ４は非記憶型ノードであり、Ｓ１〜Ｓ６は記憶型ノードである。従来のホップカウントルーティングメトリックによると、ノードＳ６は、経路Ｒ１をデフォルト経路として選択することになる。なぜならば、Ｒ１はＲ２よりも短いからである。一方、Ｒ１上の全ての中間ノードは非記憶型ノードであり、Ｒ２上の全ての中間ノードは記憶型ノードである。Ｒ１上でルートＲからノードＳ５に下りパケットを送信するには、ソースルーティングヘッダーＮ１→Ｎ２→Ｎ３→Ｎ４→Ｓ６をパケットに付加しなければならない。ＩＰｖ６ルーティングの場合、このソースルーティングヘッダーは、少なくとも８０バイトの長さである。他方、経路Ｒ２が用いられる場合、ソースルーティングヘッダーは必要とされない。すなわち、パケットオーバーヘッドは、少なくとも８０バイトだけ低減される。したがって、いくつかの実施の形態は、より多くの記憶型ノードを有する経路を用いる。
【００４４】
したがって、いくつかの実施の形態は、経路上の非記憶型ノードの数をカウントする経路の非記憶型ノードカウント（ＮＮＣ）等のパスレベルルーティングメトリックを用いる。経路発見の間、ルートは、ＮＮＣ＝０を設定する。非記憶型ノードは、ＮＮＣを１だけ増加させ、記憶型ノードは、ＮＮＣの値を変更しない。図４Ａでは、ＤＩＯがＲ１に沿ってＳ６に伝播したとき、ＮＮＣは４であり、ＤＩＯがＲ２に沿ってＳ６に伝播したとき、ＮＮＣは０である。したがって、Ｓ６は、Ｒ２がＲ１よりも好ましい経路であることを知る。
【００４５】
図４Ｂは、いくつかの実施の形態によるネットワークを通じてＮＮＣを伝播する方法のブロック図を示している。例えば、ノードは、当該ノードのＭＯＰを含むデスティネーション指向有向非巡回グラフ情報オブジェクト（ＤＩＯ）等の制御パケットを生成し（４３０）、このＤＩＯに非記憶型ノードカウント（ＮＮＣ）を追加することができる。加えてまたは代替的に、ノードは、ネットワーク内のルートノード等の別のノードによって発信されたＤＩＯの一部分としてＮＮＣを受信することができる（４４０）。ノードは、当該ノードのＭＯＰが非記憶型ＭＯＰである場合にＮＮＣを１つだけ増加させ（４５０）、ＤＩＯをネットワークにブロードキャストする（４６０）。ノードのＭＯＰが記憶型ＭＯＰである場合、ノードは、ＮＮＣを変更することなくＤＩＯをブロードキャストする。１つの実施の形態では、ノードが、異なるＮＮＣを有する複数のＤＩＯを受信した場合、最小のＮＮＣが再ブロードキャストされる。
【００４６】
図４Ｃは、本発明のいくつかの実施の形態による、ＮＮＣを用いて経路を決定する方法のブロック図を示している。例えば、ノードは、ネットワーク内のルートノードによって発信されたＤＩＯの複数のコピー４９０を受信する（４７０）。ＤＩＯの各コピーは、複数の近傍ノードのうちの１つから受信され、ルートからこの近傍ノードまでの各パス上の非記憶型ノードの数を反映したＮＮＣを含む。次に、ノードは、より小さなＮＮＣを有するＤＩＯを送信した近傍ノードのサブセットをこのノードの親として選択する。
【００４７】
本発明のいくつかの実施の形態は、ノードのリソースを利用してＤＯＤＡＧトポロジーを構築する。ＤＩＯパケットは、従来のルーティングメトリックおよびリソースアウェアメトリックＮＮＣの双方を搬送する。ＤＩＯパケットは、ルートによって発信される。ＤＩＯの伝播中、各ノードは、１つのデフォルトの親を選択するとともに、複数のバックアップの親が利用可能である場合にはこれらのバックアップの親を選択する。
【００４８】
図５は、本発明の１つの実施の形態によるリソースアウェアＤＯＤＡＧ構築および上り経路発見の方法のブロック図を示している。ノードがＤＩＯパケットを受信すると（５００）、このノードは、このＤＩＯが新たなＤＯＤＡＧのものであるのかまたは既存のＤＯＤＡＧのものであるのかを調べる（５０５）。ＤＩＯが新たなＤＯＤＡＧのものである場合、ノードは、このＤＯＤＡＧに参加するか否かを判定する（５１０）。ノードが新たなＤＯＤＡＧに参加しない場合、ＤＩＯパケットは廃棄される（５１５）。ノードがＤＯＤＡＧに参加する場合、ノードは、ＤＩＯを処理し、当該ノードのＭＯＰをそのリソースに基づいて設定する（５２０）。ＤＩＯにおいて搬送されたＮＮＣが０に等しい場合（５２５）、ノードは、ＤＩＯ送信者のＭＯＰを記録し、この送信者を自身のデフォルトの親として設定し、自身のランクを計算し（５３０）、ＤＡＯ送信をスケジューリングし（５３５）、自身のＭＯＰを有するＤＩＯを送信する（５４０）。ＮＮＣが０でない場合、ノードは、ＤＩＯ送信者のＭＯＰを記録し、このＤＩＯ送信者を親として選択するが（５４５）、ランクを計算しない。その代わり、ノードは、より好ましいＤＩＯを待機するためのタイマーを始動する（５５０）。
【００４９】
ＤＩＯが既存のＤＯＤＡＧのものである場合、ノードは、少なくとも１つの親を既に選択しており、ノードは、自身のランクが計算されているか否かを調べる（５５５）。ｙｅｓである場合、ノードは、自身のランクが、ＤＩＯにおいて搬送されたランクよりも大きいか否かを調べる（５５８）。ｎｏである場合、ＤＩＯは廃棄される（５１５）。ｙｅｓである場合、ノードは、十分な親が選択されているか否かを調べ（５６０）、ｎｏである場合、ノードは、ＤＩＯ送信者のＭＯＰを記録し、自身の親集合にこの送信者を追加し（５６５）、ｙｅｓである場合、ノードは、このＤＩＯがより良好な経路を含む場合には、親のうちの１つを交換することによって自身の親集合を更新し（５７０）、ノードは、ＤＩＯ送信者が自身の親集合に追加される場合、この送信者のＭＯＰも記録する。自身のランクが計算されておらず、受信されたＤＩＯがＮＮＣ＝０を搬送している場合（５７５）、ノードは、ＤＩＯ送信者のＭＯＰを記録し、この送信者をデフォルトの親として設定し（５８０）、ＤＩＯ待機タイマーをキャンセルし（５８５）、自身のランクを計算し、十分な親が選択されている場合には既存の親のうちの１つを交換することによって自身の親集合を更新し（５９０）、次に、ノードは、必要な場合には自身のＭＯＰを調整し（５９３）、ＤＡＯ送信をスケジューリングし（５３５）、自身のＭＯＰを有するＤＩＯをブロードキャストする（５４０）。ＤＩＯがＮＮＣ＞０を有する場合、ノードは、十分な親が選択されていない場合には自身の親集合にＤＩＯ送信者を追加し（５６５）、そうではなく十分な親が選択されている場合には自身の親集合を更新する（５７０）。ＤＩＯ待機タイマーが満了すると（５９５）、ノードは、親集合から１つの親をデフォルトの親として選択して、自身のランクを計算し（５９８）、必要な場合には自身のＭＯＰを調整し（５９３）、ＤＡＯ送信をスケジューリングし（５３５）、自身のＭＯＰを有するＤＩＯパケットを送信する（５４０）。
【００５０】
ノードの親の集合を更新するためには、或る経路が別の経路よりも良好であることを判断する基準を定義する必要がある。１つの実施の形態では、より小さなＮＮＣを有する経路は、他のメトリックが同様である場合に、それよりも大きなＮＮＣを有する経路よりも良好であるとみなされる。
【００５１】
ノードは、自身のリソースのみに基づいて自身のＭＯＰを初期設定する。ＤＩＯパケット伝播が継続するにつれて、ノードは、自身の近傍についてより多くの情報を受信する。より多くのリソースを有する近傍が存在する場合、１つの実施の形態では、ノードは、自身のＭＯＰをより低い値に変更する。
【００５２】
ＤＩＯパケットの送信前、ノードは自身のランクを計算する。以下の式は、リソースアウェアランク計算方法である。
【数２】
0006461352.tif 000003
ここで、ＲＤはデフォルトの親のランクであり、ＲＩは従来のルーティングメトリックおよび目的関数を用いることによって計算されるランク増加であり、ＣＮＮＣおよびＣＭＯＰは、それぞれ、デフォルト時のＮＮＣの重要度およびデフォルトの親のＭＯＰを反映する係数である。これらの係数は、ノードがより良好なデフォルト経路を発見した場合に、ノードがより小さなランクを有するように選択される。そうでない場合、ノードは、より大きなランクを有する。
【００５３】
ＤＡＯパケット構築
下り経路は、ＤＡＯパケットを用いて構築される。本発明のいくつかの実施の形態では、ノードは、自身のリソースだけでなく、自身の親のリソースにも応じて自身のＤＡＯパケットを構築する。ノードは、自身のＤＡＯパケットを次のように構築する。まず最初に、ＭＯＰ＝０を有するノードは、ＤＡＯパケットを構築せず、送信しない。なぜならば、そのようなノードは、下りルーティングをサポートするリソースを有しないからである。また、それらのノードは、ＭＯＰ＝０を有する親にＤＡＯパケットを送信しない。
【００５４】
非記憶型ＭＯＰおよび記憶型ＭＯＰを有するノードは、非記憶型親の非記憶型ＤＡＯパケットを構築する。記憶型ノードは、記憶型親の記憶型ＤＡＯパケットを構築する。非記憶型ノードは、記憶型親の記憶型ＤＡＯパケットまたは非記憶型ＤＡＯパケットのいずれも構築することができる。記憶型ＤＡＯを構築するために、親のリンクローカルアドレスがデスティネーションアドレスとして用いられ、ノードのグローバルアドレスがソースアドレスとして用いられる。１つの実施の形態では、記憶型ＤＡＯは、通信オーバーヘッドがより低いことに起因して非記憶型ＤＡＯよりも効率的であるので、非記憶型ノードは、記憶型親の記憶型ＤＡＯを構築する。非記憶型ＤＡＯは、ＲＰＬが行うのと同じように構築される。ルートが自身のＭＯＰ≠０を設定している場合、このルートは、非記憶型ノードまたは記憶型ノードのいずれとしてもみなすことができる。例えば、記憶型ノードは、このルートを記憶型ノードとみなし、非記憶型ノードは、このルートを非記憶型ノードとみなす。
【００５５】
図６は、本発明のいくつかの実施の形態によるＤＡＯパケット構築の一例を示している。ノードＮ１、Ｎ２、Ｎ３およびＮ４は非記憶型ノードである。ノードＳ１、Ｓ２およびＳ３は記憶型ノードである。ルートＲ  ６００は、ＤＩＯパケット６０５を下りリンク６１０に沿ってネットワーク内の全てのノードに伝播させる。上りリンク６１５は、ＤＡＯパケット送信を示している。ノードＳ３  ６２５は、Ｎ３  ６３０が非記憶型ノードであるので、親Ｎ３に送信される非記憶型ＤＡＯ（Ｎ−ＤＡＯ）６２０を構築する。Ｎ−ＤＡＯ６２０は、ルートに送信される。したがって、Ｎ３は、Ｓ３からＮ−ＤＡＯを受信すると、このＮ−ＤＡＯをＳ１  ６３５に単に転送し、Ｓ１は、次に、このＮ−ＤＡＯをＲに転送する。
【００５６】
逆に、Ｓ３は、Ｓ２が記憶型親であるので、Ｓ２  ６５０に送信される記憶型ＤＡＯ（Ｓ−ＤＡＯ）パケット６２３を構築する。Ｓ２がＳ−ＤＡＯを受信すると、Ｓ２は、Ｓ３の下り経路エントリーを追加し、Ｓ１に送信されるデスティネーションＳ３を含むＳ−ＤＡＯを構築し、Ｓ１は、Ｓ２と同じことを行う。最後に、Ｒは、デスティネーションＳ３を含むＳ−ＤＡＯを受信する。
【００５７】
リソースアウェア下りルーティングの代行ペアレンティング
異なるリソースを有するノードは、異なるＭＯＰを有する。異なるＭＯＰを有するノードは、異なるルーティング機能を実行する。異種ネットワークにおいて異なるＭＯＰを有するノードをサポートするために、より少ないリソースを有するノードにより多くの作業負荷を追加することは実際的でないので、余分な作業負荷が生じる。いくつかの実施の形態は、より多くのリソースを有するノードに余分な作業負荷をシフトする。
【００５８】
いくつかの実施の形態では、異なるＭＯＰを有するルーティングを実施するために、記憶型ノードのＤＡＯパケットの上り転送方法が、「アクティブな親」の注記の援助によって強化される。ノードの代行親は、このノードからルートへの経路上にある、次の２つの条件を満たす記憶型ノードである。経路上のこのノードとこの記憶型ノードとの間に非記憶型ノードがなく、かつ、この記憶型ノードの次のホップが非記憶型ノードである。したがって、いくつかの実施の形態では、或るノードは、子孫ノードのアクティブな親とすることができ、なお、この子孫ノードはこのノードの直接の子でない。
【００５９】
図７Ａは、ノードＲ  ７００がルートであり、Ｎ１  ７１０、Ｎ２  ７３０、Ｎ３  ７６０、およびＮ４  ７８０が非記憶型ノードであり、Ｓ１  ７２０、Ｓ２  ７４０、Ｓ３  ７５０、Ｓ４  ７７０、およびＳ５  ７９０が記憶型ノードである場合の代行親の一例を示している。経路Ｓ３→Ｓ２→Ｓ１→Ｎ１→Ｒ上では、Ｓ１はノードＳ３の代行親である。一方、Ｓ２は、Ｓ３の代行親とすることができない。なぜならば、ノードＳ２の次のホップは記憶型ノードＳ１であるからである。Ｎ３  ７６０が、経路Ｎ３→Ｓ３→Ｎ２→Ｓ１→Ｎ１→Ｒに沿って記憶型ＤＡＯをＳ３に送信すると仮定すると、Ｓ３は、ノードＮ３の代行親である。
【００６０】
代行親の重要な性質は、代行親が経路範囲しか有しないということである。すなわち、記憶型ノードは、１つの経路上で或るノードの代行親とすることができるが、別の経路上で同じノードの代行親でない場合がある。例えば、経路Ｓ３→Ｎ２→Ｓ１→Ｎ１→Ｒに沿って、Ｓ１は、Ｓ３の代行親とすることができない。なぜならば、Ｓ３とＳ１との間に非記憶型ノードＮ２が存在するからである。
【００６１】
ノードの代行親は、このノードの直接の親である可能性がある。例えば、経路Ｓ２→Ｓ１→Ｎ１→Ｒに沿って、Ｓ１は、ノードＳ２の代行親である。実際には、Ｓ１は、Ｓ２の直接の親でもある。
【００６２】
記憶型ノードは、ＤＡＯパケットを受信すると、代行親の役割を行う必要性を判断する。記憶型ノードは、自身の部分ＤＯＤＡＧ内のノードからＤＡＯパケットを受信する。ＤＡＯが、指定された親を有しないデスティネーションを含み、記憶型ノードが、それらのデスティネーションの非記憶型ＤＡＯを構築して、この非記憶型ＤＡＯを非記憶型親に送信することを意図している場合、記憶型ノードは、指定された親を有しないそれらのデスティネーションの親として自身を指定することによって代行親の役割を行う。
【００６３】
代行親は、ルートまたは記憶型ノードが下り経路を作成するメカニズムを提供する。したがって、代行親は、異なるＭＯＰを有するネットワークにおいて下りパケットを送信するメカニズムを提供する。
【００６４】
図７Ｂは、本発明のいくつかの実施の形態によるアクティブペアレンティングを定義する親子関係を指定する方法のブロック図を示している。本方法は、ノードのＭＯＰが記憶型ＭＯＰであり、このノードの親ノードのＭＯＰが非記憶型ＭＯＰである場合に、この記憶型ＭＯＰのノードによって実行される。
【００６５】
ノードは、子孫ノードによって発信された制御パケット、例えばＤＡＯを受信する（７０１）。この子孫ノードは、このノードの直接の子ではない。ノードは、制御パケットが子孫ノードの親子ペアを含むか否かを検査する（７０２）。親子ペアが制御パケットにない場合、ノードは、この子孫ノードがこのノードの直接の子であることを指定する子孫ノードの親子ペアを制御パケット内に追加し（７０３）、制御パケットをノードの祖先に送信する（７０４）。
【００６６】
代行親によって変換された圧縮ネットワーク
リソースアウェアルーティングによると、ルートまたは記憶型ノードは、ルーティングテーブルを用いることによっていくつかのノードの下りパケットを送信することができる。一方、ルートまたは記憶型ノードは、それ以外のノードの下り経路を作成することが必要な場合がある。
【００６７】
図７Ａの一例では、Ｓ６を介して下りパケットを送信するルートは、ノードＳ６が記憶型ノードであるので、ルーティングテーブルを用いることができる。一方、ルートが非記憶型ノードＮ１を介して下りパケットを送信する場合、ルートは、下り経路を作成する必要がある。下り経路を作成するために、ルートＲまたは記憶型ノードは、非記憶型ＤＡＯに収集された親子ペアを用いる。親のうちのいくつかは直接の親であるが、親のうちのいくつかは代行親である。代行親が存在する場合、ルートまたは記憶型ノードは、ネットワークトポロジーを実際のネットワークトポロジーと異なって捉える。換言すれば、ネットワーク内の代行親は、ネットワークまたはネットワークの一部分を圧縮ネットワークに変換する。
【００６８】
図７Ｃは、ルートＲの視点からの図７Ａの変換ネットワーク７９９を示している。ノードＳ１のアクティブな親の役割に起因して、Ｎ１を介した部分ネットワークは、実際の部分ネットワークとは異なって見える。したがって、代行親Ｓ１およびＳ３は、Ｎ１を介した部分ネットワークを圧縮ネットワークに変換する。この圧縮ネットワークは、元のネットワークよりも小さなネットワーク直径を有する。例えば、Ｎ１を介した部分ネットワークにおける最長経路は６ホップである。一方、圧縮ネットワーク７９９における最長経路は僅か４ホップである。圧縮ネットワークは、ルートまたは記憶型ノードによって下り経路を作成するのに用いることができる。
【００６９】
圧縮ネットワークから作成された圧縮経路
リソースアウェアルーティングによると、ルートまたは記憶型ノードは、いくつかのノードについてはホップ単位の下り経路を作成することができる。一方、ルートまたは記憶型ノードは、それ以外のノードについてはホップ単位の下り経路を構築することができない場合がある。
【００７０】
図８Ａおよび図８Ｂは、本発明のいくつかの実施の形態による異種無線ネットワークにおける経路の圧縮の概略図を示している。図８Ａの例では、ノードＳ２およびＳ３は記憶型ＤＡＯを生成し、Ｓ１はノードＳ２およびＳ３の代行親である。記憶型ＤＡＯはサイズがより小さいので、Ｎ２も記憶型ＤＡＯを生成し、Ｓ３に送信する。したがって、Ｓ１は、ノードＮ２の代行親でもある。
【００７１】
図８Ｂは、ルートＲの視点からの図８Ａのネットワークを示している。ルートは、圧縮ネットワークに基づいて下り経路を構築することができる。その結果、Ｓ３への下り経路は、Ｒ→Ｎ１→Ｓ１→Ｓ３  ８１０のように見え、Ｎ２への下り経路は、Ｒ→Ｎ１→Ｓ１→Ｎ２  ８２０のように見え、Ｓ４への下り経路は、Ｒ→Ｎ１→Ｓ１→Ｎ２→Ｓ４  ８３０のように見える。これらの経路は、ホップ単位の経路ではなく、実際には圧縮経路である。実際のＳ３へのホップ単位の下り経路は、Ｒ→Ｎ１→Ｓ１→Ｓ２→Ｓ３であり、実際のＮ２へのホップ単位の下り経路は、Ｒ→Ｎ１→Ｓ１→Ｓ２→Ｓ３→Ｎ２であり、実際のＳ４へのホップ単位の下り経路は、Ｒ→Ｎ１→Ｓ１→Ｓ２→Ｓ３→Ｎ２→Ｓ４である。
【００７２】
圧縮経路は、ルートまたは記憶型ノードからデスティネーションへの下り経路であり、圧縮経路は、収集された親子（または代行親）ペアを用いることによって構築される。圧縮経路は、ホップカウントの点でホップ単位の経路よりも短く、ソースルーティングヘッダーを短縮することによって通信オーバーヘッドを削減するので有利である。ルートまたは記憶型ルーターは、圧縮経路を用いて、デスティネーションに下りパケットをより効率的に送達することができる。
【００７３】
圧縮経路は、ホップ単位の経路ではない。したがって、圧縮経路上では、ノードは、次のホップと直接通信しない場合がある。例えば、圧縮経路Ｒ→Ｎ１→Ｓ１→Ｎ２→Ｓ４  ８３０上では、Ｓ１は、次のホップＮ２と直接通信しない場合がある。
【００７４】
圧縮経路Ｒ→Ｎ１→Ｓ１→Ｎ２→Ｓ４  ８３０を例として取り上げて、この圧縮経路を用いることによる下りパケット送達を示す。ルートＲは、Ｎ１→Ｓ１→Ｎ２→Ｓ４を含むソースルーティングヘッダーを、Ｓ４をデスティネーションとする下りパケットに付加し、このパケットをＮ１に転送する。Ｎ１は、非記憶型ノードであり、ソースルーティングヘッダーを用いることによってパケットをＳ１に転送する。Ｓ１がパケットを受信すると、ノードＳ１は、ソースルーティングヘッダーを調べ、デスティネーションがＳ４であることを確認する。このノードは、Ｓ４の自身のルーティングテーブルも調べ、Ｓ４への次のホップがＳ２であることを確認する。Ｓ２は記憶型ノードである。したがって、Ｓ１は、パケットからソースルーティングヘッダーを除去し、自身のルーティングテーブルを用いてパケットをＳ２に転送する。
【００７５】
Ｓ２がパケットを受信すると、ノードＳ２は、デスティネーションＳ４の自身のルーティングテーブルを調べ、次のホップがＳ３であることを知る。Ｓ３は記憶型ノードである。したがって、Ｓ２は、自身のルーティングテーブルを用いてパケットをＳ３に転送する。Ｓ３がパケットを受信すると、Ｓ３は、Ｓ４の自身のルーティングテーブルを調べ、次のホップがＮ２であると判断する。Ｎ２は非記憶型ノードである。したがって、Ｓ３は、Ｓ４への下り経路を作成する必要がある。Ｓ３は、自身の親子テーブルを調べ、経路Ｎ２→Ｓ４を含むソースルーティングヘッダーを構築する。Ｓ３は、パケットをＮ２に転送する。Ｎ２は、ソースルーティングヘッダーをパースし、パケットをデスティネーションＳ４に転送する。
【００７６】
リソースアウェアＤＡＯ処理および代行親に基づく転送
リソースアウェアルーティングによって、ノードは、自身のＭＯＰと、ＤＡＯが送信される親のＭＯＰとに基づいてＤＡＯタイプを決定することが可能になる。異なるＭＯＰを有するネットワークを実現するために、新たなＤＡＯ転送メカニズムが、いくつかの実施の形態によって提供される。
【００７７】
１つの実施の形態では、非記憶型ノードは、ＤＡＯを処理せず、ＤＡＯを自身のデフォルトの親に単に中継するだけである。逆に、ルートまたは記憶型ノードは、受信されたＤＡＯを異なって取り扱う。ルートまたは記憶型ノードは、直接の子を識別し、直接の子のＭＯＰを求める必要がある。ルートまたは記憶型ノードは、各直接の子のＭＯＰを記憶する。１つの実施の形態は、ＤＡＯフォーマットに対するいずれの変更も必要としない。その代わり、この実施の形態は、以下の原理に従って、直接の子および直接の子のＭＯＰを識別する。
【００７８】
ソースアドレスおよびデスティネーションアドレスの双方がリンクローカルアドレスである場合、ＤＡＯ送信者は直接の子であり、この直接の子は記憶型ノードである。ソースアドレスがグローバルアドレスであり、デスティネーションアドレスがリンクローカルアドレスである場合、ＤＡＯ送信者は直接の子であり、この直接の子は非記憶型ノードである。ソースアドレスおよびデスティネーションアドレスの双方がグローバルアドレスである場合、ルートまたは記憶型ノードは、ソースノードの親フィールドを調べる。ソースノードがルートまたは記憶型ノードを親として指定している場合、ソースノードは直接の子であり、この直接の子は非記憶型ノードである。そうでない場合、ソースノードは直接の子ではない。
【００７９】
例えば、１つの実施の形態では、ルートは、ＤＡＯに含まれる各デスティネーションの経路エントリーをルーティングテーブル内に追加することと、直接の子のＭＯＰを求めて記憶することとによって、記憶型ＤＡＯを処理する。ルートは、ＤＡＯに含まれる各デスティネーションの経路エントリーをルーティングテーブル内に追加し、非記憶型子から受信されたＤＡＯに含まれる各デスティネーションの親子（または代行親）ペアを記憶し、直接の子のＭＯＰを求めて記憶することよって、非記憶型ＤＡＯを処理する。
【００８０】
記憶型ノードは、記憶型ＤＡＯを次のように処理する。経路上の目的とする親が記憶型ノードである場合、ノードは、ＤＡＯに含まれる各デスティネーションの経路エントリーをルーティングテーブル内に追加し、直接の子のＭＯＰを求めて記憶し、記憶型ＤＡＯを構築し、この記憶型ＤＡＯを記憶型親に送信する。
【００８１】
経路上の目的とする親が非記憶型ノードである場合、ノードは、ＤＡＯに含まれる各デスティネーションの経路エントリーをルーティングテーブル内に追加し、直接の子のＭＯＰを求めて記憶し、代行親の役割を実行することによって非記憶型ＤＡＯを構築し、このＤＡＯを非記憶型親に転送する。ノードは、代行親の役割を実行することによって非記憶型ＤＡＯを構築することができる。例えば、ＩＰｖ６ヘッダーでは、デスティネーションアドレスは、ルートの一意のＩＰｖ６アドレスであり、ソースアドレスは、記憶型ノードの一意のＩＰｖ６アドレスである。デスティネーションノードが親を指定していない場合、記憶型ノードは、ノードがデスティネーションノードの親であることを指定する。
【００８２】
記憶型ノードは、ＤＡＯに含まれる各デスティネーションの経路エントリーをルーティングテーブル内に追加し、非記憶型子から受信された非記憶型ＤＡＯに含まれる各デスティネーションの親子（または代行親）ペアを記憶し、直接の子のＭＯＰを求めて記憶し、ＤＡＯを自身のデフォルトの親に中継することによって非記憶型ＤＡＯを処理する。
【００８３】
例えば、図７Ａでは、ノードＳ４は、非記憶型ＤＡＯをＮ３に送信し、Ｎ３は、このＤＡＯをＳ３に転送する。Ｓ３がＤＡＯを受信すると、Ｓ３は、非記憶型子Ｎ３から非記憶型ＤＡＯを受信しているので、ノードＳ３は、Ｓ４の経路エントリーおよびＳ４の親子エントリーを記憶する。Ｓ３は、次に、ＤＡＯをＳ２に転送する。一方、Ｓ２は、Ｓ４の経路エントリーのみを追加するが、Ｓ４の親子エントリーを追加しない。なぜならば、非記憶型ＤＡＯは、記憶型子（storing child）から受信されているからである。
【００８４】
いくつかの実施の形態では、ルートは、ネットワーク内の全てのノードについての２つのテーブル、すなわち、記憶型ＤＡＯを介して受信された全てのデスティネーションの下り経路エントリーを記憶するルーティングテーブルと、非記憶型ＤＡＯパケットを介して受信された全てのデスティネーションの子および親（または代行親）のペアを記憶する親子テーブルとを保持する。
【００８５】
加えてまたは代替的に、記憶型ノードは、全てのノードについての２つのテーブル、すなわち、記憶型ＤＡＯを介して受信された全てのデスティネーションの下り経路エントリーを記憶するルーティングテーブルと、非記憶型ＤＡＯパケットを介して受信された全てのデスティネーションの子および親（または代行親）のペアを記憶する親子テーブルとを自身の部分ＤＯＤＡＧに保持する。
【００８６】
ノードは、ルーティングテーブルおよび親子テーブルの双方にエントリーを有することができる。例えば、図４Ａにおいて、ノードＳ６がＮ４およびＳ５の双方をＤＡＯ親として選択した場合、Ｓ６は、非記憶型ＤＡＯをＮ４に送信し、記憶型ＤＡＯをＳ５に送信する。その結果、Ｓ６は、Ｓ６の親がＮ４であるというエントリーを用いてＲの親子テーブルに存在し、Ｓ６への次のホップがＳ１であるというエントリーを用いてＲのルーティングテーブルにも存在する。
【００８７】
圧縮ネットワークに基づくリソースアウェア下り経路構築
ルートまたは記憶型ノードは、下りパケットを送信する下り経路を構築することができる。下り経路は、ホップ単位の経路または圧縮経路とすることができる。
【００８８】
圧縮ネットワークに基づいて、ルートは、以下のように下り経路を構築する。
●初期化
○２つの集合を作成する
■開始集合（ＳＳ）＝｛ルートが非記憶型子から受信された非記憶型ＤＡＯから学習したネットワーク内の全てのノード｝
■終了集合（ＦＳ）＝｛Root｝
○経路＝（Root）を設定する。これは、ルートからの全ての下り経路の開始点である。
○Ref_Rank＝Root_Rank＋１を設定する
●下り経路構築
○Ref_Rankに等しいランクを有するノードがＳＳ内にあるか否かを調べる
■ない場合、Ref_Rankを１つだけ増加させ、動作を続ける
■ある場合、親子テーブルを用いることによってＦＳ内でこのノードの親を見つける
・親（または代行親）が見つかった場合、この親について作成された経路にこのノードを付加し、経路を記憶し、動作を続ける
・親が見つからなかった場合、これはエラーであり、動作を停止する
・このノードを求めてＦＳを探索した後、ランク＝Ref_Rankを有するＳＳ内の次のノードに移動する
■ランク＝Ref_Rankを有するＳＳ内の全てのノードを探索した後、これらのノードをＳＳからＦＳに移動させる
■Ref_Rankを１つだけ増加させ、動作を継続する
○ＳＳが空になったとき、プロセスは完了する
○プロセスが、エラーに起因して停止した場合、ルートは、増加されたＤＡＯトリガーシーケンス番号（ＤＴＳＮ）を有するＤＩＯを送信することによって、不明情報を有するノードをトリガーすることができる
【００８９】
記憶型ノードは、ルートが行うのと同様にして下り経路を構築する。唯一の相違は初期化であり、この初期化において、記憶型ノードは、ＳＳ＝｛記憶型ノードが非記憶型子から受信された非記憶型ＤＡＯから学習した自身の部分ＤＯＤＡＧ内の全てのノード｝、ＦＳ＝｛記憶型ノード｝およびRef_Rank＝記憶型ノードのランクに１を加えたものを設定する。
【００９０】
図９Ａは、図９Ｂにおける圧縮ネットワークに基づくルートによる下り経路構築の一例を示している。ルートＲは、以下のように下り経路を作成する。
●Ｒは、ＳＳ＝｛Ｎ１，Ｓ１，Ｎ２，Ｓ２，Ｓ３，Ｎ３，Ｓ４｝、ＦＳ＝｛Ｒ｝、Route＝（Ｒ）およびRef_Rank＝Root_Rank＋１＝２を設定する
●Ref_Rank＝２から開始する
○Ｎ１のランク＝２であり、Ｎ１の親はＲであり、Ｎ１の経路は（Ｒ→Ｎ１）であり、Ｎ１をＦＳに移動して、ＳＳ＝｛Ｓ１，Ｎ２，Ｓ２，Ｓ３，Ｎ３，Ｓ４｝およびＦＳ＝｛Ｒ，Ｎ１｝にする
●Ref_Rankを３に増加させる
○Ｓ１のランク＝３であり、Ｓ１の親はＮ１であり、Ｓ１の経路は（Ｒ→Ｎ１→Ｓ１）であり、Ｓ１をＦＳに移動して、ＳＳ＝｛Ｎ２，Ｓ２，Ｓ３，Ｎ３，Ｓ４｝およびＦＳ＝｛Ｒ，Ｎ１，Ｓ１｝にする
●Ref_Rankを４に増加させる
○Ｎ２のランク＝４であり、Ｎ２の親はＳ１であり、Ｎ２の経路は（Ｒ→Ｎ１→Ｓ１→Ｎ２）である；Ｓ２のランク＝４であり、Ｓ２の代行親はＳ１であり、Ｓ２の経路は（Ｒ→Ｎ１→Ｓ１→Ｓ２）である。Ｎ２およびＳ２をＦＳに移動して、ＳＳ＝｛Ｓ３，Ｎ３，Ｓ４｝およびＦＳ＝｛Ｒ，Ｎ１，Ｓ１，Ｎ２，Ｓ２｝にする。
●Ref_Rankを５に増加させる
○Ｓ３のランク＝５であり、Ｓ３の親はＮ２であり、Ｓ３の代行親はＳ１であり、Ｓ３の経路１は（Ｒ→Ｎ１→Ｓ１→Ｎ２→Ｓ３）であり、Ｓ３の経路２（圧縮）は（Ｒ→Ｎ１→Ｓ１→Ｓ３）である；Ｎ３のランク＝５であり、Ｎ３の代行親はＳ１であり、Ｎ３の経路（圧縮）は（Ｒ→Ｎ１→Ｓ１→Ｎ３）である。Ｓ３およびＮ３をＦＳに移動して、ＳＳ＝｛Ｓ４｝およびＦＳ＝｛Ｒ，Ｎ１，Ｓ１，Ｎ２，Ｓ２，Ｓ３，Ｎ３｝にする。
●Ref_Rankを６に増加させる
○Ｓ４のランク＝６であり、Ｓ４の親はＮ３であり、Ｓ４の経路（圧縮）は（Ｒ→Ｎ１→Ｓ１→Ｎ３→Ｓ４）であり、Ｓ４をＦＳに移動して、ＳＳ＝｛空｝およびＦＳ＝｛Ｒ，Ｎ１，Ｓ１，Ｎ２，Ｓ２，Ｓ３，Ｎ３，Ｓ４｝にする。
●Ref_Rankを７に増加させる
○ＳＳは空であり、プロセスは完了する
【００９１】
この例では、ノードＮ３は、記憶型ＤＡＯをＳ２に送信する。Ｎ３が非記憶型ＤＡＯをＳ２に送信する場合、Ｎ３およびＳ４の経路は、圧縮経路ではなく現実の経路である。
【００９２】
圧縮経路を用いたリソースアウェア下りパケット転送
本発明の様々な実施の形態によれば、ルートまたは記憶型ノードは、下りパケットをデスティネーションに転送する３つの方法を有する。すなわち、ソースルーティングを用いる方法、ルーティングテーブルを用いる方法、またはソースルーティングと、ルーティングテーブルおよび親子テーブルとの組み合わせを介した方法を有する。ルートまたは記憶型ルーターは、下りパケットを送信する複数の選択肢を有することが可能である。しかしながら、１つの実施の形態は、ルーティングテーブルを用いて下りパケットを送信する。なぜならば、ルーティングテーブルは、ソースルーティングヘッダーを必要とせず、パケットは、サイズがより小さいからである。パケットは、小さいほど、より高い送達信頼性を有する。
【００９３】
ルートまたは記憶型ノードは、経路上の次のホップが非記憶型ノードである場合、ソースルーティングヘッダーを下りパケットに付加する。ソースルーティングヘッダーは、ホップ単位の経路または圧縮経路とすることができる下り経路を含む。下りパケット中継中に、記憶型ノードは、ソースルーティングヘッダーを除去して、パケットをより小さくすることができる。
【００９４】
非記憶型ノードは、他のノードの下り経路情報を記憶しない。非記憶型ノードは、ソースルーティングヘッダーのみを用いて下りパケットを転送する。非記憶型ノードが、転送するための下りパケットを受信し、このパケットがソースルーティングヘッダーを含むとき、ノードは、ソースルーティングヘッダーに従うことによってパケットを次のホップに転送する。非記憶型ノードが、転送するための下りパケットを受信し、このパケットがソースルーティングヘッダーを含まないとき、ノードは、デスティネーションの到達可能性を調べる。デスティネーションが到達可能である場合、ノードは、パケットを転送する直接Ｐ２Ｐを用いる。デスティネーションが到達可能でない場合、ノードは、パケットをデフォルトの親に転送する。
【００９５】
記憶型ノードが、転送するための下りパケットを受信し、このパケットが、ソースルーティングヘッダーを含む場合、ノードは、デスティネーションが自身のルーティングテーブルにないときまたは次のホップが非記憶型ノードであるとき、ソースルーティングヘッダーを用いる。デスティネーションが自身のルーティングテーブルにあり、次のホップが記憶型ノードである場合、ノードは、ソースルーティングヘッダーをパケットから除去し、ルーティングテーブルを用いてこのパケットを転送する。なぜならば、ソースルーティングヘッダーを除去することによって、パケットはより小さくなるからである。記憶型ノードが、転送するための下りパケットを受信し、このパケットがソースルーティングヘッダーを含まないとき、ノードは、デスティネーションが自身のルーティングテーブルにあり、次のホップが記憶型ノードである場合に、ルーティングテーブルを介してパケットを次のホップに転送する。デスティネーションが自身のルーティングテーブルにあり、次のホップが非記憶型ノードである場合、ノードは、ソースヘッダーを付加し、パケットを次のホップに転送する。デスティネーションが自身のルーティングテーブルにない場合、ノードは、デスティネーションの到達可能性を調べる。デスティネーションが到達可能である場合、ノードは、パケットを転送する直接Ｐ２Ｐを用いる。デスティネーションが到達可能でない場合、ノードは、パケットを自身のデフォルトの親に転送する。
【００９６】
記憶型ノードが、転送するための下りパケットを受信し、このパケットが、ソースルーティングヘッダーを含むとき、ノードは、長い方のソースルーティングヘッダーを短い方のソースルーティングヘッダーと交換することができる。
【００９７】
図１０は、下りパケットをデスティネーションに送信する３つの方法の概略図を示している。ルートＲは、下りパケットをＮ４に送信するのにソースルーティングヘッダーを用いる（１０１０）。なぜならば、経路上の全てのノードは非記憶型ノードであるからである。ルートＲは、下りパケットをＳ４に送信するのにルーティングテーブルを用いる（１０２０）。なぜならば、経路上の全てのノードは記憶型ノードであるからである。ルートＲは、下りパケットをＳ７に送信するのに圧縮経路を用いる（１０３０）。なぜならば、経路上のノードは異なるＭＯＰを有するからである。パケットをＳ７に送信するために、Ｒは、圧縮経路Ｎ５→Ｓ５→Ｓ７を有するソースルーティングヘッダーを付加し、パケットをＮ５に転送する。Ｎ５は、非記憶型ノードであり、したがって、パケットをＳ５  １０００に転送する。Ｓ５はＳ７の代行親である。Ｓ５は、Ｓ７のルーティングテーブルエントリーを有し、次のホップは、記憶型ノードであるＳ６である。Ｓ５は、ソースルーティングヘッダーをパケットから除去し、このパケットをＳ６に転送する。Ｓ６は、次に、パケットをＳ７に転送する。Ｓ５からＳ７へは、パケットは、ルーティングテーブルを用いることによって中継される（１０４０）。
【００９８】
リソース使用量およびネットワーク状態に基づく適応的ＭＯＰ変更
いくつかの実施の形態では、ノードは、異種ネットワークの動作中に利用可能なリソースをシグナリングする。例えば、電池式ノードの電池レベルが低くなった場合、ノードは、エネルギーを節約するためにスリープすることができる。この場合、この電池式ノードが十分なメモリ空間および処理速度を有する場合であっても、他のノードのパケットを中継するのにこの電池式ノードを用いることは望ましくない。
【００９９】
本発明のいくつかの実施の形態は、異種ネットワーク内のノードが、ＭＯＰの変更を介して自身のリソース使用量をシグナリングすることを可能にする。ノードが自身のＭＯＰを減少させた場合、ブロードキャストされる変更されたＭＯＰは、そのノードが自身のリソースに注意を払っていることを示す。ノードが自身のＭＯＰを増加させた場合、ブロードキャストされる変更されたＭＯＰは、そのノードがより多くのリソースを取得していることを示す。したがって、１つの実施の形態では、ノードが自身のＭＯＰを変更したとき、このノードは、ＤＩＯを送信して、この変更をアナウンスする。
【０１００】
例えば、ＭＯＰ−０を有するノードが自身のＭＯＰを増加させたとき、このノードは、ＤＡＯ送信をスケジューリングする。このＤＡＯ送信に応答して、このノードの直接の子は、この親のＭＯＰを更新することができ、この親をＤＡＯ親集合内に追加することができる。また、近傍ノードは、このノードを自身の親集合内に追加することができる。
【０１０１】
非記憶型ノードが自身のＭＯＰを記憶型モードに変更したとき、このノードの直接の子は、この親のＭＯＰを更新することができる。また、記憶型子はＤＡＯをスケジューリングし、このスケジューリングにおいて、この記憶型子は、上り経路上の次のホップが現在記憶型ノードであるので、自身の代行親の役割を取り除く。
【０１０２】
記憶型ノードが自身のＭＯＰを非記憶型モードに変更したとき、この記憶型ノードの直接の子は、この親のＭＯＰを更新することができる。また、記憶型子は、非記憶型ＤＡＯをスケジューリングし、このスケジューリングにおいて、この記憶型子は、指定された親を有しない自身の部分ＤＯＤＡＧ内のノードの代行親の役割を取る。
【０１０３】
記憶型ノードまたは非記憶型ノードがＭＯＰを０に減少させたとき、このノードの直接の子は、この親のＭＯＰを更新し、この親をＤＡＯ親として有する直接の子は、ＤＡＯ親集合からこの親を除去し、この変更を反映するように新たなＤＡＯを生成する。
【０１０４】
図１１は、いくつかの実施の形態によるノードの適応的ＭＯＰ変更のブロック図を示している。このノードのＭＯＰは記憶型ＭＯＰである。ノードは、当該ノードの親のＭＯＰを受信し（１１１０）、ＭＯＰの変更のタイプを検査する（１１２０）。親のＭＯＰが記憶型ＭＯＰから非記憶型ＭＯＰに変更された場合、ノードは、子孫ノードがこのノードの直接の子であることを示す親子ペアを有する制御パケットを送信する（１１３０）。親のＭＯＰが非記憶型ＭＯＰから記憶型ＭＯＰに変更された場合、ノードは、子孫ノードの親子ペアを制御パケットから除去し（１１４０）、この制御パケットを送信する。
【０１０５】
本発明の上記の実施の形態は数多くの方法のいずれかにおいて実現することができる。例えば、それらの実施の形態は、ハードウェア、ソフトウェアまたはその組み合わせを用いて実現することができる。ソフトウェアにおいて実現されるとき、そのソフトウェアコードは、単一のコンピューター内に設けられるにしても、複数のコンピューター間に分散されるにしても、任意の適切なプロセッサ、またはプロセッサの集合体において実行することができる。そのようなプロセッサは集積回路として実現することができ、集積回路コンポーネント内に１つまたは複数のプロセッサが含まれる。しかしながら、プロセッサは、任意の適切な構成の回路を用いて実現することができる。そのプロセッサは、当該技術分野において既知であるように、メモリ、送受信機および入出力インターフェースに接続することができる。
【図１】
0006461352.tif 000005
【図２Ａ】
0006461352.tif 000006
【図２Ｂ】
0006461352.tif 000007
【図３Ａ】
0006461352.tif 000008
【図３Ｂ】
0006461352.tif 000009
【図４Ａ】
0006461352.tif 000010
【図４Ｂ】
0006461352.tif 000011
【図４Ｃ】
0006461352.tif 000012
【図５】
0006461352.tif 000013
【図６】
0006461352.tif 000014
【図７Ａ】
0006461352.tif 000015
【図７Ｂ】
0006461352.tif 000016
【図７Ｃ】
0006461352.tif 000017
【図８Ａ】
0006461352.tif 000018
【図８Ｂ】
0006461352.tif 000019
【図９Ａ】
0006461352.tif 000020
【図９Ｂ】
0006461352.tif 000021
【図１０】
0006461352.tif 000022
【図１１】
0006461352.tif 000023