説明

マルチホップネットワークにおいて複数の経路を発見する方法および複数の経路を検索するノード

【課題】大規模マルチホップメッシュネットワークにおいてデータ送信元ノードから複数のデータ宛先ノードへの複数の経路を発見する方法を提供する。
【解決手段】ノードは、2回のネットワーク全体のパケットのフラッディングのみを含む初期発見段階において、2つの宛先への複数の経路を発見する。また1つの宛先で機能することもでき、通信オーバーヘッドが比例して増大するより多くの宛先を含むように拡張することができる。発見段階の完了後、ノードは、利用可能な経路のうちの任意のものを用いることにより、該ノード自体のデータまたは受信データを通信または転送することができる。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、包括的には、無線センサーネットワークにおけるパケットのルーティングに関し、特に、スマートメーターネットワークにおけるルーティングに関する。
【背景技術】
【0002】
無線ネットワーキング技術の急速な進歩により、リアルタイムモニタリング、信頼性およびより優れたリソース管理のために、電気、水およびガス等のユーティリティの分配ネットワークを含む無線マルチホップメッシュネットワークを展開することが、ますます実現可能になってきている。
【0003】
スマートグリッドの出現により、再生可能な発電源の分散ネットワークを展開し、その後、広い地理的地域にわたって円滑で、信頼性が高くかつ最適化されたエネルギー管理のための分配ネットワークを管理するという大きな難題への挑戦がなされている。グリッド全体の正常な動作に必要な極めて重要な構成要素は、種々の地理的地域におけるリソース消費に関するリアルタイムデータを収集することである。
【0004】
スマートメーターネットワークは、通常、家庭用スマートメーター内の一組のデータ送信元と、無線で、または電力線通信(PLC)システム等の有線ネットワークを介して接続された1つまたは複数のデータシンクとを有している。スマートメーターは、送信元データおよび近接する隣接ノードから受信したデータを中継する通信ルーターとして作用する。
【0005】
スマートメーターおよびデータシンクは、地理的位置に関して固定されている。従来の無線センサーネットワークおよびモバイルアドホックネットワークとは異なり、スマートメーターネットワークには2種類のデータフローしかない。スマートメーターは、1つまたは複数の指定されたデータシンクに周期的にデータを送信する。データシンクは、必要に応じて1つまたは複数のスマートメーターに制御データを送信することができる。データシンクを、いくつかのスマートメーターから複数ホップ離すことができる。したがって、これらのスマートメーターからのデータは、実際にデータシンクに到達するまでに複数ホップにわたって移動しなければならない。
【0006】
スマートメーターは、場合によっては、それ自体のデータと、その隣接するスマートメーターのうちのいくつかから受信したデータとを統合し、その後、その統合データを、スマートメーターまたはデータシンクとすることができる次ホップのノードに転送することができる。データシンクは、受信データを処理し、統合データをユーティリティ会社のオペレーションセンターに送信する、プロセッサおよび送受信機を有することができる。
【0007】
ルーティングは、スマートメーターネットワークにおける重要な機能のうちの1つである。データ通信が開始することができる前に、スマートメーターとデータシンクとの間の経路を発見しなければならない。リアルタイムスマートメーターネットワークにおけるルーティングは、より多くの課題を提供する。
【0008】
種々の要件に基づく無線センサーネットワークおよびモバイルアドホックネットワークに対して、アドホックオンデマンド距離ベクトルルーティング、ダイナミックソースルーティング、テンポラリオーダードルーティングおよび低電力で損失のあるネットワークに対するルーティング方法等、多数のルーティング方法が知られている。
【0009】
しかしながら、従来のルーティング方法は、スマートメーターネットワークに十分に適合していない。したがって、スマートメーターネットワークの要件を満足させるルーティング方法を開発することが望ましい。
【0010】
スマートメーターネットワークにおけるルーティング
最新のユーティリティ分配ネットワークでは、すべてのスマートメーターがそのデータを、ユーティリティプロバイダーのオペレーションセンターに定期的に送信するように期待されている。メーターは、非同期データトラフィックを生成することによって安全性事象およびセキュリティ事象等、異常事象に応答することもできる。そして、収集されたデータは、処理され、解析され、よりよい需要応答、リソース管理および危険な状況への対応のために利用される。
【0011】
データが、信頼性があり、かつ効率的な方法でデータシンクに通信されることが必須である。データパケットが損失するか、または過度に遅延することにより、リソースが無駄になり、またはさらに悪いことに、人間の生活および資産を危険にさらす可能性がある。したがって、スマートメーターネットワークは、スマートメーターネットワークの厳しい性能要件を満足させる、明確であり、効率的であり、かつ極めて信頼性の高いルーティング方法を展開しなければならない。
【0012】
スマートメーターネットワークにおけるルーティングの問題
無線センサーネットワークおよびモバイルアドホックネットワークに対する多数のルーティング方法が知られている。しかしながら、一般的な無線センサーネットワークおよびモバイルアドホックネットワークとの明確なアーキテクチャ上の相違に基づいて、スマートメーターネットワークには、非常に特異な要件がある。
【0013】
無線センサーネットワークにおけるピアツーピア通信とは対照的に、スマートメーターネットワークにはほんのわずかなデータシンクしかなく、ほとんどすべてのトラフィックがデータシンクポイントに向けられる。また、スマートメーターネットワークにおけるノードの数は、何千にも達する可能性がある。こうした大規模かつ高密度なネットワークでは、干渉が激しい可能性がある。車両等の移動体もまた、通信リンクに障害をもたらす可能性がある。データ送信間隔は、ほんの数分程度に短い可能性がある。制御データレイテンシは、数秒間である可能性がある。
【0014】
ピアツーピア通信では、通信ノードの各対は、一般に、ノード間の経路を発見する。多くのこうしたネットワークにおける経路発見は、ネットワーク全体のフラッディングを通じて行われる。大規模ネットワークでは、特に多くのノードがピアツーピア方式で通信している場合、経路発見のための通信オーバーヘッドは、膨大となる。こうした過度なオーバーヘッドは、大規模なスマートメーターネットワークでは回避されなければならない。また、メーターデータおよび制御データを宛先に確実に配信しなければならない。したがって、ノードは、シンクポイントへのプライマリルートに障害が発生した場合に使用される、すでに発見された多数の代替経路を有していなければならない。
【0015】
さらに、ノードは、複数のデータシンクへの経路を発見する必要がある場合がある。これらの複数の経路のすべてを、初期発見段階またはセットアップ段階中に最小の通信オーバーヘッドで発見しなければならない。障害が発生している経路を、ネットワーク全体のパケットのフラッディングをもたらすことなく、かつ通常の定期的なデータ通信を中断させることなく、修復しなければならない。
【0016】
無線アドホックネットワークに対して一般に用いられているルーティング方法のうちの1つは、アドホックオンデマンド距離ベクトル(AODV)ルーティングである。AODVには、必要な場合にのみ経路を発見すること、および障害が発生している経路を自動的に修復すること等の利点がある。しかしながら、AODVでは、制御メッセージが過度に伝送される。AODVルーティングアルゴリズムでは、送信元ノードと宛先ノードとの間の各経路発見により、1回のネットワーク全体のフラッディングがもたらされる。経路再発見には著しく時間がかかる。それは、シングルパスルーティング方法である。AODVは、ピアツーピアネットワークに適している。
【0017】
ダイナミックソースルーティング(DSR)は、無線アドホックネットワークに一般に使用されている別のルーティング方法である。DSRは、要求に応じて経路を形成するという点でAODVに類似している。しかしながら、DSRは、ルーティングテーブルに依存しない。むしろ、送信側/送信元ノードが、伝送されているパケットに宛先へのパスを含める。DSRは、移動度の低い小規模かつ静的なネットワークでは十分に実行する。しかしながら、移動度が増大すると、DSRの性能は、急速に劣化する。経路維持は、障害が発生した経路を修復しない。コネクションセットアップ遅延が大きくなる。データパケットに経路情報が含まれているため、著しいルーティングオーバーヘッドを伴う。
【0018】
無閉路有向グラフ(DAG)に基づく2つの既知のルーティング方法がある。1つは、テンポラリオーダードルーティングアルゴリズム(TORA)であり、TORAは、非階層ルーティング方法を用いて高度のスケーラビリティを達成しようとする。TORAは、宛先をルートとしたDAGを構成し維持する。TORAは、高さが高い方のノードから低い方のノードに流れるメッセージのみを許可することにより、ループのないマルチパスルーティングを達成する。TORAは、高密度ネットワークに優れている。しかしながら、TORAにおける制御メッセージオーバーヘッドは、さらに高くなる。ノードの数が増大するに従い、制御メッセージオーバーヘッドが大幅に増大する。また、TORAは、最短パス解決法を用いない。
【0019】
低電力で損失のあるネットワークに対するルーティング(RPL)は、DAGを用いる別のルーティング方法である。RPLは、インターネットエンジニアリングタスクフォース(IETF)によって開発中である。RPLは、大規模スマートグリッドネットワークに対して信頼性が高く、かつ低レイテンシのサポートを提供することを目指している。RPLでは、各ノードは、ランク特性を用いることによってDAG構造における該ノードの位置を維持する。しかしながら、RPLでは、多くの重要な問題が解決されないままになっている。ランク計算は、RPLに対して述べられていない。親の選択は、ゲートウェイからの制御メッセージの受信にのみ基づく。安定したリンクが存在しない場合、これによって配信障害が発生する可能性がある。RPLには、ブロードキャスト機構がない。RPLは、IPv6に密に関連し、それにより、非IPネットワークに適していないRPLがもたらされる可能性がある。
【0020】
モバイルアドホックネットワークへのよりよいアプローチ(BATMAN)もまた、無線アドホックネットワークに対するルーティング方法である。BATMANの非常に重要な点は、ネットワークを通る最適経路に関する知識の分散化である。いかなる単一ノードも、すべてのデータを有してはいない。定期的に、各ノードは、発信者メッセージをブロードキャストして、該ノードの隣接ノードに該ノードの存在に関して通知する。そして、隣接ノードは、この発信者メッセージをそれらの隣接ノードに中継する。あるノードへの最適進路を見つけるために、BATMANは、受信した発信者メッセージをカウントし、メッセージがいずれの隣接ノードを通って来たかを記録する。BATMANは、高度な安定性を呈している。しかしながら、BATMANは、収束時間が遅い。定期的な発信者メッセージは、特にスマートメーターネットワーク等の大規模ネットワークの場合、制御メッセージオーバーヘッドを増大させる。ハイブリッドマルチパスルーティングのためのアントエージェント(AntHocNet)は、無線アドホックネットワークのための適応ルーティング方法である。AntHocNetは、リアクティブ型経路設定をプロアクティブ型経路探索、維持および改善と組み合わせることによるハイブリッド方法である。AntHocNetは、複数のパスを発見し、連続して新たなパスを探索する。しかしながら、経路修復には複数のブロードキャストが必要であり、それによってネットワークがフラッディングする。定期的な隣接ノード制御メッセージが制御メッセージオーバーヘッドを増大させ、その結果、大規模ネットワークに信頼性問題およびレイテンシ問題がもたらされる。
【発明の概要】
【発明が解決しようとする課題】
【0021】
本発明の実施形態は、大規模マルチホップメッシュネットワークにおいてデータ送信元ノードから複数のデータ宛先ノードへの複数の経路を発見する方法を提供する。記憶容量および通信帯域幅が限られていることにより、経路発見および経路修復に対してノードに厳しい制限が課される。
【課題を解決するための手段】
【0022】
ネットワーク例では、ノードは、2回のネットワーク全体のパケットのフラッディングのみを含む初期発見段階において、2つの宛先への複数の経路を発見する。本方法は、また、1つの宛先でも機能することができる。本方法を、通信オーバーヘッドが比例して増大する、より多くの宛先を含むように拡張することができる。発見段階の完了後、ノードは、利用可能な経路のうちの任意のものを用いることによって、それら自体のデータまたは受信データを通信しまたは転送することができる。
【0023】
発見段階中、発見された経路は、コスト関数に基づいて列挙され、最適経路のみが保持される。それにより、経路に循環がないことが確実になる。本方法は、また、代替経路を用いることによって続行されている通常のデータ通信を中断させることなく、局所的な経路修復も容易にする。
【発明の効果】
【0024】
本発明は、明確であり、効率的であり、かつ極めて信頼性の高いルーティング方法を展開しなければならない非常に大規模なスマートメーターネットワークが、スマートメーターネットワークの厳しい性能要件を満たすために有利である。本方法は、送信元から宛先への代替経路を提供することにより、リンク障害およびノード障害に対して回復力がある。本方法は、大規模ネットワークの信頼性問題およびレイテンシ問題をもたらすオーバーヘッド制御メッセージを最小限にする。本方法は、また、経路内の循環も回避する。
【図面の簡単な説明】
【0025】
【図1】本発明の実施形態が動作するスマートメーターネットワークの概略図である。
【図2】図1のネットワークにおいて複数の経路を発見する方法の概略図である。
【図3】経路要求(RREQ)パケット例の概略図である。
【図4】経路応答(RREP)パケット例の概略図である。
【発明を実施するための形態】
【0026】
図1は、本発明の実施形態が動作する無線スマートメーターネットワーク100を示す。プライマリ宛先ノードD101およびバックアップ宛先ノードD102が、高速有線リンクまたは無線リンク103(実線)を介して、コアネットワーク120を介してオペレーションセンター110に接続している。
【0027】
通常のスマートメーターは、送信元ノードS121であり、それは、無線リンク124(破線)を用いて1つまたは複数のプライマリルート122および1つまたは複数のバックアップルート123によって宛先ノードに接続されている。宛先ノードを、ユーティリティ会社のオペレーションセンターに接続されたコンセントレーターノードとすることができる。
【0028】
本発明の実施の形態は、ネットワーク100における1つまたは複数の宛先ノードへの経路を、効率的かつ最適な方法で発見する方法を提供する。通信および記憶オーバーヘッドは、最小限にされ、大規模ネットワークのセットアップまたは回復のプロセス中の初期発見段階にのみ限定される。
【0029】
唯一ネットワーク全体のブロードキャストを使用する経路発見段階の最後において、ネットワークの送信元ノードのすべてが、両宛先ノードDへの複数の経路を発見している。
【0030】
図2は、図1のネットワークにおいて複数の経路を発見する方法の概略図を示す。送信元ノードS201は、経路要求パケットRREQ203をブロードキャストすることにより、宛先ノードD202への経路発見を開始する。経路発見を、定期的にまたは非定期的に実行することができる。
【0031】
図3に、RREQパケットのフォーマット例を示す。RREQパケットは、伝送ノードアドレス301、RREQ Id302、送信元アドレス303、宛先アドレス304、順方向コスト305、ホップカウント306および他のフィールド307〜308を含む。しかしながら、実際のRREQパケットは、展開に必要である場合または適切であると考えられる場合、より多くのフィールドを有することができる。このフォーマットは、この出願に対して重要であるフィールドのみを指定している。また、RREQパケット300における宛先ノードアドレスフィールド304は、1つの特定の宛先ノードのアドレスを指定することができるか、またはネットワークにおけるすべての宛先ノードを(たとえば、ブロードキャストアドレス0xFFFFを有することにより)指定することができる。代替的に、宛先アドレスフィールドは、ネットワークにおける宛先ノードの一部のアドレスのリストからなることができる。
【0032】
送信元ノードS201のすべての中間隣接ノード205が、RREQ203パケットを受信し、受信したRREQパケットにおける、宛先ノードD202に対する宛先ノードのアドレス304がその中間隣接ノード自体のアドレスに一致するか否かを検査する。アドレスが一致しない場合、受信ノードは、宛先ノードD202ではない。その場合、受信ノードは、中間ノード205として作用する。
【0033】
すべての中間ノード205が、ブロードキャストノードS201と受信ノード205(すなわち、中間ノード自体)との間のリンク204に対してリンクコストを加算することにより、RREQパケット203に関連する順方向コストを計算する。この順方向コストフィールド305は、ノードS201に戻る経路が実行可能であることを示す。
【0034】
リンクコストを、以下の要素の組のうちのいくつかまたはすべての組合せに基づいて適切な関数により計算することができる。すなわち、ホップカウント306、リンク品質、平均パケット廃棄率、バッファリング容量および予測される伝送遅延である。この組は、列挙した要素にのみ制限されない可能性がある。
【0035】
むしろ、この組に、他のいかなる関連性能パラメーターを含めることもできる。そして、ノードは、ローカルデータベースに関連する情報を記録する。情報は、RREQ Id302、RREQパケット203の発信ノードS201のアドレスである送信元ノードアドレス303、宛先ノードアドレス304、すなわちノードD202のアドレス、隣接ノード、すなわちRREQパケットを伝送したノードS201のアドレス301(伝送ノードアドレス)、および更新されたコストフィールドを含むことができる。
【0036】
ノードは、更新されたコストフィールド305を含むRREQパケット206を再ブロードキャストする。伝送ノード205のすべての中間隣接ノード207が、RREQパケット206を受信する。中間ノード207は、RREQパケット208が宛先ノードD202に達するまで、中間ノード205によって行なわれるものと同じ手続きに従う。
【0037】
中間ノード205および207は、隣接するノードから同じRREQパケット203の複数のコピーを受信することができる。すべての中間ノード207が、同じRREQ Idに対して受信するRREQパケットのすべてまたは事前に決められた限られた数(すなわちk≧1)のRREQパケットの情報を記録する。実際には、記録された情報は、発信ノードS201に戻るk個の最適経路を指定する。
【0038】
オーバーヘッドを低減するために、中間ノードは、受信する第1のRREQパケットと、同じRREQパケットの任意の後に受信したコピー、すなわち、前にブロードキャストしたRREQパケットより更新された順方向コストが低い、同じRREQ Idを有するRREQパケットとを再ブロードキャストする。
【0039】
宛先ノードD202は、その隣接するノード207からRREQパケット208を受信すると、RREPパケット250を構成し、ブロードキャストすることによって応答する。
【0040】
図4に、RREPパケットのフォーマット例を示す。RREPパケットは、伝送ノードアドレス401、RREP Id402、送信元アドレス403、宛先アドレス404、順方向コスト405、戻りコスト406、ホップカウント407および他のフィールド408〜409を含む。しかしながら、実際のRREPパケットは、展開に必要である場合または適切であると考えられる場合に、より多くのフィールドを有することができる。
【0041】
宛先ノードD202によって構成され、かつブロードキャストされるRREPパケット250は、更新された順方向コストおよびゼロ戻りコストの両方を含むことができる。RREPパケット250(または252)を受信するすべての中間ノード251(および253)は、受信リンクのコストを計算し、該コストを、受信したRREPパケットの戻りコストフィールド406に加算することによって、戻りコストフィールド406を更新する。RREQパケットと同様に、中間ノードは、同じRREPパケット250の2つ以上のコピーを受信することができる。
【0042】
すべての中間ノードは、同じRREP Idに対するすべてのRREPパケット、または事前に決められた数j(j≧1)のRREPパケットに対する関連情報を記録することができる。記録された情報は、実際には、宛先ノードD202へのj個の最適経路を指定する。すべての中間ノードが、受信したRREPパケットの順方向コストフィールド405の値を用いることにより、対応するRREQパケットに対する戻りコストフィールド406の格納された値を減算することによって、(その中間ノード自体から宛先ノードD202までの)各経路のコストを容易に計算することができる。
【0043】
中間ノードと同様に、宛先ノードS202は、その隣接するノードから同じRREQパケット203の複数のコピーを受信することができる。同様に、送信元ノードS201は、その隣接するノードから同じRREPパケット250の複数のコピーを受信することができる。これらのノードは、それぞれ受信したRREQパケットおよびRREPパケットのすべてまたはいくつかに対する関連情報を記録することができる。
【0044】
循環パスの防止
図2に示す方法では、循環パスを有する経路が発見される可能性がある。それは、循環に入るいずれのパケットもその循環から決して出ることができない可能性があるため、問題となる可能性がある。したがって、発見されている経路に循環が形成されるのを回避することが必須である。この問題は、すべてのノードが、宛先ノードへの複数の経路を発見しようとする場合に、さらに深刻になる。
【0045】
ノードは、RREQ/RREPパケットに追加の情報を含めることにより、これらの循環パスの形成を防止することができる。その情報を、受信ノードが、受信したRREQ/RREPパケットが破棄される必要があるか否かが判断されている間に利用することができる。目的は、宛先ノードへの発見されたすべての経路の集合体が論理ツリー構造を形成することを確実にすることである。
【0046】
すべての中間ノードが、侵害をもたらす可能性があるかまたは論理ツリー構造から脱落するRREPパケットを破棄する。それを達成するために、すべてのRREQパケットおよびRREPパケットは、それまで通過したノードのリストを含むことができる。すべてのノードが、RREQパケットまたはRREPパケットを伝送している間に、該ノードの一意のID(すなわち、該ノードのアドレス)をパケットの内部のリストに追加する。この情報は、受信ノードが、パケットの発信元への(受信されたパケットのリストによって指定される)経路を許容するべきか拒否するべきかを判断するために使用する。その条件により、宛先ノードへの交差しない経路がもたらされる。
【0047】
さらに、ノードは、リストのサイズが事前定義された閾値に達すると、RREQパケットまたはRREPパケットを廃棄することができる。それは、パケットサイズを制御するのに役立つだけでなく、むしろより重要なことには、発見されている過度に長い経路をフィルタリングによって除去する。それらの長い経路は、高性能ネットワークに対する厳しいレイテンシ制約のセットを満たすことができない可能性がある。
【0048】
しかしながら、経路が交差しないという条件は、ノードが複数の最適な経路を有する可能性を極度に制限することになるということは、注目に値する。利用可能な経路の数が減少することにより、ノードが破断した経路に対応する柔軟性が低減する。実際には、柔軟性と交差しない経路の程度との間にトレードオフがある。
【0049】
極端な場合、ノードは、受信したばかりのRREPパケットに指定されている宛先ノードへの経路を、この経路が前に発見された同じ宛先ノードへの既存の経路と交差する場合、拒否することができる。これにより、所与のノードから宛先ノードへのすべての経路が、強制的にそのノードと宛先ノードとの間の重ならないパスを形成する。
【0050】
したがって、経路の交差が許可される可能性がある。しかしながら、交差点は、(複数の経路の)交差するノードが破損した場合の代替経路として多くの選択肢があるように、(ホップの数に関して)安全な距離にあるべきである。

【特許請求の範囲】
【請求項1】
送信元ノードのセットと宛先ノードのセットとを含むマルチホップネットワークにおいて複数の経路を発見する方法であって、それにより、前記各送信元ノードが、前記宛先ノードのすべてに対する前記複数の経路を発見し、特定の宛先ノードへの前記発見された経路のうちの1つを用いて該送信元ノードからデータを伝送し、該方法は、
前記各送信元ノードにより、経路要求(RREQ)パケットをブロードキャストするステップであって、前記宛先ノードのセットに対する前記複数の経路の発見を開始し、前記RREQパケットは、ルーティング情報およびコストフィールドを含む、ブロードキャストするステップと、
前記送信元ノードの隣接する中間ノードにおいて、前記RREQパケットの1つまたは複数のコピーを受信するステップと、
前記隣接する中間ノードにおいて、前記ルーティング情報および前記コストフィールドを更新するステップと、
前記隣接する中間ノードにより、前記RREQパケットの前記1つまたは複数のコピーを受信することに応じて、前記RREQパケットの1つまたは複数のコピーが前記宛先ノードによって受信されるまで、前記RREQパケットの少なくとも1つのコピーを他の隣接する中間ノードにブロードキャストするステップと、
前記各宛先ノードにおいて、すべての受信されたRREQパケットに対して経路応答(RREP)パケットを構成するステップであって、該RREPパケットは、ルーティング情報およびコストフィールドを含む、ステップと、
前記各宛先ノードにより、前記隣接するノードに前記RREPパケットをブロードキャストするステップと、
前記宛先ノードの隣接する中間ノードにおいて、前記RREPパケットの1つまたは複数のコピーを受信するステップと、
前記隣接する中間ノードにおいて、前記ルーティング情報および前記コストフィールドを更新するステップと、
前記隣接する中間ノードにより、前記RREPパケットの前記1つまたは複数のコピーを受信することに応じて、該RREPパケットの該1つまたは複数のコピーが前記各送信元ノードによって受信され、それにより該各送信元が、前記RREPパケットのうちの1つにおける前記ルーティング情報および前記コストフィールドに基づいて、前記宛先ノードのうちの1つにデータを送信するための前記複数の経路のうちの1つを選択することができるようになるまで、他の隣接する中間ノードに前記RREPパケットの少なくとも1つのコピーをブロードキャストするステップと
を含む方法。
【請求項2】
前記ネットワークは、k+1以下の回数、前記RREQパケットおよび前記RREPパケットによってフラッディングされ、ここでkは、宛先ノードの数である請求項1に記載の方法。
【請求項3】
前記複数の経路は、定期的に発見される請求項1に記載の方法。
【請求項4】
前記複数の経路は、非定期的に発見される請求項1に記載の方法。
【請求項5】
前記各送信元ノードは、メーターノードであり、前記各宛先ノードは、ユーティリティプロバイダーのオペレーティングセンターに接続されたコンセントレーターノードである請求項1に記載の方法。
【請求項6】
前記ノードは、無線リンクによって接続される請求項1に記載の方法。
【請求項7】
前記複数の経路は、1つまたは複数のプライマリルートと1つまたは複数のバックアップルートとを含む請求項1に記載の方法。
【請求項8】
前記RREQパケットは、伝送ノードアドレス、RREQ Id、送信元アドレス、宛先アドレス、順方向コスト、ホップカウントを含み、前記RREPパケットは、前記伝送ノードアドレス、前記RREP Id、前記送信元アドレス、前記宛先アドレス、前記順方向コスト、戻りコストおよび前記ホップカウントを含む請求項1に記載の方法。
【請求項9】
前記順方向コストは、前記ホップカウント、リンク品質、平均パケット廃棄率、バッファリング容量および予測される伝送遅延の組合せに基づく請求項8に記載の方法。
【請求項10】
前記中間ノードは、同じRREQパケットの任意の後続する受信されたコピーを破棄することができる請求項1に記載の方法。
【請求項11】
前記宛先ノードへの前記経路の集合体により論理ツリー構造を形成するように、前記複数の経路から循環を除去するステップ
をさらに含む請求項1に記載の方法。
【請求項12】
別の経路と交差するいかなる経路も拒否するステップ
をさらに含む請求項1に記載の方法。
【請求項13】
前記コストは、順方向コストおよび逆方向コストを含み、前記順方向コストおよび前記逆方向コストの関数により特定の経路のコストが決まる請求項1に記載の方法。
【請求項14】
前記RREQパケットおよび前記RREPパケットが横断するすべてのノードのリストが前記各パケットに格納される請求項1に記載の方法。
【請求項15】
送信元ノードのセットとk個の宛先ノードのセットとを含むマルチホップネットワークにおいて複数の経路を発見する方法であって、
前記各送信元ノードにより、経路要求(RREQ)パケットをブロードキャストするステップであって、前記k個の宛先ノードのセットに対する前記複数の経路の発見を開始する、ブロードキャストするステップと、
前記k個の宛先ノードのセットの各々において前記RREQパケットの1つまたは複数のコピーを受信するステップと、
前記k個の宛先ノードのセットの各々によって、前記受信に応じて経路応答(RREQ)をブロードキャストするステップと、
前記各宛先ノードにおいて、前記RREPパケットの1つまたは複数のコピーを受信するステップであって、前記ネットワークは、k+1以下の回数、前記RREQパケットおよび前記RREPパケットでフラッディングされる、受信するステップと
を含む方法。
【請求項16】
前記各RREQパケットおよび前記各RREPパケットは、前記送信元ノードから前記k個の宛先ノードのセットのうちの1つまたは複数への1つまたは複数の経路と、該各経路に関連するコストとを含み、前記方法は、
前記コストに基づいて特定の宛先ノードにデータを伝送するために前記経路のうちの1つを選択するステップ
をさらに含む請求項15に記載の方法。
【請求項17】
所定の閾値より長い経路は拒否される請求項1に記載の方法。
【請求項18】
前記RREQパケットは、経路発見の目標として1つの宛先ノードを指定するか、または経路が同時に発見される宛先ノードのセットを指定する請求項1に記載の方法。
【請求項19】
すべてのデータ送信元ノードNは、該データ送信元ノードの利用可能な記憶容量および前記宛先ノードの重要性に基づいて、宛先ノードDへのRi1>0個の最適経路、宛先ノードDへのRi2>0個の最適経路等を維持するように、ローカルデータベースを維持することができ、前記Ri1およびRi2の値は、同じまたは異なる値とすることができる請求項1に記載の方法。
【請求項20】
前記ノードは、無線リンク、または電力線通信(PLC)システム等の他の任意の短距離通信技法によって接続される、請求項1に記載の方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate


【公開番号】特開2012−217164(P2012−217164A)
【公開日】平成24年11月8日(2012.11.8)
【国際特許分類】
【外国語出願】
【出願番号】特願2012−75857(P2012−75857)
【出願日】平成24年3月29日(2012.3.29)
【出願人】(597067574)ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】201 BROADWAY, CAMBRIDGE, MASSACHUSETTS 02139, U.S.A.
【Fターム(参考)】