(57)【要約】【課題】アドホックネットワーク、センサネットワーク、メッシュネットワーク、マルチホップネットワークおよび他のネットワークのために用いることができるワイヤレスネットワーク内のノードにアドレスを割り当てるための方法を提供する。【解決手段】本方法は、ワイヤレスネットワーク内のノードにアドレスを割り当てる。アドレス空間は、ｎ次元格子として定義される。また、各格子の交点は、ワイヤレスネットワークの対応する取り得るノードの座標を有する。また、各座標の成分の数は、格子の次元数に等しく、座標は、対応する取り得るノードの論理アドレスを形成する。親ノードは、ワイヤレスネットワークに参加する子ノードに対して、子ノードアドレスの１つの成分が親ノードの対応する成分よりも１だけ大きくなるように、割り当てられていない論理アドレスを子ノードアドレスとして割り当てる。
2009505445.tif 000002
【特許請求の範囲】
【請求項１】
ワイヤレスネットワーク内のノードにアドレスを割り当てるための方法であって、
アドレス空間をｎ次元格子として定義するステップと、
親ノードから前記ワイヤレスネットワークに参加する子ノードに対して、子ノードアドレスの１つの成分が、前記親ノードの対応する成分よりも１だけ大きくなるように、割り当てられていない論理アドレスを前記子ノードアドレスとして割り当てるステップと、
を含み、
前記格子の交点のそれぞれは、前記ワイヤレスネットワークの対応する取り得るノードの座標を有し、前記座標の成分の数は、前記格子の次元数に等しく、前記座標は、前記対応する取り得るノードの論理アドレスを形成することを特徴とするワイヤレスネットワーク内のノードにアドレスを割り当てるための方法。
【請求項２】
前記各成分の取り得る値の範囲は、前記成分を表現するために用いられるビットの数によって決定されることを特徴とする請求項１に記載のワイヤレスネットワーク内のノードにアドレスを割り当てるための方法。
【請求項３】
前記格子は、平行六面体の形状を有することを特徴とする請求項１に記載のワイヤレスネットワーク内のノードにアドレスを割り当てるための方法。
【請求項４】
前記ネットワークのコーディネータノードの前記論理アドレスとして、前記格子の１つのコーナの座標を割り当てるステップをさらに含むことを特徴とする請求項１に記載のワイヤレスネットワーク内のノードにアドレスを割り当てるための方法。
【請求項５】
前記子ノードによって、アドレス要求メッセージを報知するステップと、
１つまたは複数の潜在的な親ノードによって、前記アドレス要求メッセージに応答するステップと、
前記子ノードにおいて、前記潜在的な親ノードのうちの１つを前記親ノードとして選択するステップと、
をさらに含むことを特徴とする請求項１に記載のワイヤレスネットワーク内のノードにアドレスを割り当てるための方法。
【請求項６】
前記親ノードを選択することは、前記応答するノードの信号強度に基づくことを特徴とする請求項１に記載のワイヤレスネットワーク内のノードにアドレスを割り当てるための方法。
【請求項７】
前記論理アドレスは、前記ノード間の経路を暗示することを特徴とする請求項１に記載のワイヤレスネットワーク内のノードにアドレスを割り当てるための方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはネットワークに関し、特に、ワイヤレスネットワーク内のノードにアドレスを割り当てることに関する。
【背景技術】
【０００２】
ワイヤレスネットワークの最新の進歩によって、ホームオートメーションおよび産業オートメーション、環境モニタリングおよび環境センシング、セキュリティおよび監視、人間追跡および商品追跡、並びに医療モニタリング等の応用形態が可能になった。
【０００３】
ワイヤレスネットワークでは、各ノードは、伝送範囲内にある他のノードと通信することができる。各ノードは、ノード間の通信を容易にするために固有の識別情報を有する。アドホックネットワーク内でアドレスを割り当てることは、ネットワークトポロジが不規則かつ自律分散的であることに起因した問題である。
【０００４】
ジグビーアライアンス（ＺｉｇＢｅｅ  Ａｌｌｉａｎｃｅ）によって用いられる方式のような、いくつかのアドレス割り当て方式は、アドレスの階層的な木を用いる。例えば、まず、ジグビーコーディネータ（ＺＣ）ノードは、割り当てられる全てのアドレスを管理している。その後、子ノードがネットワークに参加するときに、ＺＣノードで始まる親ノードは、このアドレス空間の一部を子ノードに割り当てる。
任意の親ノードに対する子ノードの数は、構成パラメータとして決定されるので、親ノードは、参加する子ノードに割り当てられるアドレス空間の領域を体系的に決定することができる。この方式は、報知メッセージを介した明白な経路の発見をすることなしに経路発見を促進する。
【０００５】
しかしながら、ジグビー方式の固定的な構造は、アドレスを浪費する恐れがあるか、または、いくつかの親ノードがこれから参加しようとしている子ノードにアドレスを割り当てるのを妨げる恐れさえある。さらに、ネットワーク内でアドレスの階層的な木が有することができるレベルの最大数には制限がある。さらに、１つのノードに障害があると、この木において下位のアドレスを有するノードにアクセスできなくなる恐れがある。これは、障害があるノードが、この木の根の近くに存在するときに深刻な問題である。
【０００６】
別のアドレス割り当て方式は、分散型の動的アドレス割り当てプロトコルを用いる（例えば、非特許文献１参照）。また、このプロトコルは、Ｒｉｃａｒｄ‐Ａｇｒａｗａｌａアルゴリズムを基にする排他制御過程に基づく（例えば、非特許文献２参照）。
すなわち、参加するノードは、イニシエータノードとして、隣接するノードを選択する。イニシエータノードは、１つのアドレスを選択し、メッセージを報知して、ネットワーク内の他の全てのノードに、選択されたアドレスを通知する。
その後、イニシエータノードは、ネットワーク内の他のノードからの応答を待つ。全てのノードからの応答が肯定応答、すなわち選択されたアドレスを他のどのノードも使用していないことを意味する応答である場合には、イニシエータノードは、このアドレスを参加するノードに割り当てる。そうでない場合には、イニシエータノードは別のアドレスを選択し、それ以降、同じように繰り返す。
【０００７】
しかしながら、このプロトコルはいくつかの問題を抱えている。すなわち、全てのノードが、割り当てられたアドレスについての情報を保持しなければならない。これは、小さなセンサノードにおいて限られた資源であるメモリを必要とする。
さらに、報知メッセージおよび他の管理メッセージは、帯域幅および電力といったネットワーク資源を消費する。さらに、イニシエータノードは、任意のアドレスを選択することができる。それゆえ、このアドレス割り当ては、必ずしも規則的または体系的なパターンには従わない。これにより、経路発見が困難になる。
【０００８】
また、別のアドレス割り当て方式は、逐次二分割アルゴリズム（ｂｉｎａｒｙ  ｓｐｌｉｔ  ａｌｇｏｒｉｔｈｍ）を用いる（例えば、非特許文献３参照）。
すなわち、各ノードは、利用可能なアドレスのブロックを保持する。あるノードがこのネットワークに参加しようとするとき、参加するノードは、隣接する構成ノードからのアドレスを要求する。この構成ノードは、アドレスのブロックを半分に分割し、自らのために半分を保有し、残りの半分を要求しているノードに与える。
どのノードも、アドレスのブロックを記録するためのアドレステーブルを保持している。また、各ノードは、周期的にそのアドレスブロックを報知し、他のノードが自らのアドレステーブルを更新できるようにする。また、アドレスは、他のノードから借りることもできる。
しかしながら、結果として、この方式も、アドレス割り当てが規則的または体系的なパターンに従わなくなる。
【０００９】
また、別の方式は、重複アドレス検出を実行する（例えば、非特許文献４参照）。
すなわち、参加するノードは、利用可能なアドレスの異なるグループから、自らのために２つのランダムなアドレスをそれぞれ選択する。一方のアドレスは、検証過程のための一時的なソースアドレスとして用いられる。また、他方のアドレスは、検証過程を待つ間に、最終的に割り当てられるアドレスとして予約される。
しかしながら、この方式も多数の報知メッセージを必要とし、アドレスがランダムに生成される。
【００１０】
【非特許文献１】Ｓ．Ｎｅｓａｒｇｉ，Ｒ．Ｐｒａｋａｓｈ，“ＭＡＮＥＴｃｏｎｆ：Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｏｆ  Ｈｏｓｔｓ  ｉｎ  ａ  Ｍｏｂｉｌｅ  Ａｄ  Ｈｏｃ  Ｎｅｔｗｏｒｋ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＥＥＥ  Ｉｎｆｏｃｏｍ，Ｊｕｎｅ  ２００２
【非特許文献２】Ｇ．Ｒｉｃａｒｄ，Ａ．Ｋ．Ａｇｒａｗａｌａ，“Ａｎ  ｏｐｔｉｍａｌ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｍｕｔｕａｌ  ｅｘｃｌｕｓｉｏｎ  ｉｎ  ｃｏｍｐｕｔｅｒ  ｎｅｔｗｏｒｋｓ”，Ｃｏｍｍ．ＡＣＭ，２４（１），１９８１，ｐ９‐１７
【非特許文献３】Ｍ．Ｍｏｈｓｉｎ，Ｒ．Ｐｒａｋａｓｈ，“ＩＰ  Ａｄｄｒｅｓｓ  Ａｓｓｉｇｎｍｅｎｔ  ｉｎ  ａ  Ｍｏｂｉｌｅ  Ａｄ  Ｈｏｃ  Ｎｅｔｗｏｒｋ”，ＩＥＥＥ  Ｍｉｌｉｔａｒｙ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｃｏｎｆｅｒｅｎｃｅ（ＭＩＬＣＯＭ  ２００２），Ｖｏｌ.２，Ｏｃｔｏｂｅｒ  ２００２，ｐ.８５６‐８６１
【非特許文献４】Ｃ．Ｅ．Ｐｅｒｋｉｎｓ，Ｊ．Ｔ．Ｍａｌｉｎｅｎ，Ｒ．Ｗａｋｉｋａｗａ，Ｅ．Ｍ．Ｂｅｌｄｉｎｇ‐Ｒｏｙｅｒ，Ｙ．Ｓｕｎ，“ＩＰ  Ａｄｄｒｅｓｓ  Ａｕｔｏｃｏｎｆｉｇｕｒａｔｉｏｎ  ｆｏｒ  Ａｄ  Ｈｏｃ  Ｎｅｔｗｏｒｋｓ”，ＩＥＴＦ  Ｉｎｔｅｒｎｅｔ  Ｄｒａｆｔ，ｄｒａｆｔ‐ｉｅｔｆ‐ｍａｎｅｔ‐ａｕｔｏｃｏｆ‐０１．ｔｘｔ，Ｎｏｖｅｍｂｅｒ  ２００１
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従来のアドレス割り当て方式には、上記のような問題点があった。
本発明は、上記のような問題点を解決することを課題とするものであって、その目的は、アドホックネットワーク、センサネットワーク、メッシュネットワーク、マルチホップネットワークおよび他のネットワークのために用いることができるワイヤレスネットワーク内のノードにアドレスを割り当てるための方法を提供することにある。
【課題を解決するための手段】
【００１２】
本発明に係るワイヤレスネットワーク内のノードにアドレスを割り当てるための方法は、アドレス空間をｎ次元格子として定義するステップと、親ノードからワイヤレスネットワークに参加する子ノードに対して、子ノードアドレスの１つの成分が、親ノードの対応する成分よりも１だけ大きくなるように、割り当てられていない論理アドレスを子ノードアドレスとして割り当てるステップと、を含み、格子の交点のそれぞれは、ワイヤレスネットワークの対応する取り得るノードの座標を有し、座標の成分の数は、格子の次元数に等しく、座標は、対応する取り得るノードの論理アドレスを形成するものである。
【発明の効果】
【００１３】
本発明に係るワイヤレスネットワーク内のノードにアドレスを割り当てるための方法によれば、メモリおよび報知要件のためのオーバーヘッドが小さい。また、ホップの最大数、または親子ノード関係の数に関する制限がない。この方法は、ノードの物理的な位置が一様に分布していないときに、アドレス空間の浪費を抑えることができる。
【発明を実施するための最良の形態】
【００１４】
実施の形態１．
図１は、本発明の実施の形態１によるワイヤレスネットワーク内のノードのｎ次元格子１００の一例を示す説明図である。ただしｎは２である。この格子の各交点は、デカルト座標、例えば（０，０）、（０，１）、・・・、（４，４）を有する。ノードの座標またはｎ個のタプルは、対応するノードの論理アドレスである。この座標は、格子の次元数に等しい数の成分を有する。例えば、２次元の場合、各論理アドレスは２つの成分を有する。
【００１５】
成分毎の値の範囲は、その成分に割り当てられるビットの数によって表される。例えば、最大アドレスが１６ビットによって示される場合、各成分には、０から２５５までの値を得るために８ビットが割り当てられる。また、８ビットの割り当ての代わりに、この割り当ては、６ビットおよび１０ビットにすることができ、他も同様である。
言い換えると、この格子は、立方体、直方体、またはさらに高次の平行六面体にすることができる。また、さらに大きな次元を用いることもでき、例えば、４次元の場合、ノードの座標は、（ｋ，ｌ，ｍ，ｎ）となる。
【００１６】
図１において、コーナノード１は、論理アドレス（０，０）を有するコーディネータノードとして用いることができる。点描されたノード２およびノード３は、アドレスを割り当てられている。網目模様のノード４は、アドレスを要求している。
ここで、アドレス割り当ては、任意のコーナノードにおいて開始することができることに留意されたい。
【００１７】
各アドレス成分に８ビットが割り当てられる場合には、４つのコーナアドレスは（０×０，０×０）、（０×０，０×ＦＦ）、（０×ＦＦ，０×０）および（０×ＦＦ，０×ＦＦ）となる。
ここで、便宜上、開始アドレスとして（０×０，０×０）が選択されているとする。
【００１８】
割り当てられていない論理アドレスは、最初に子ノードにアドレス要求メッセージを報知させることによって、ネットワークに参加する子ノードに割り当てられる。ジグビーネットワークでは、このメッセージとして、例えば「ビーコン要求」メッセージを用いる。伝送範囲内にある全ての潜在的な親ノードが、要求しているノードにビーコンフレームを送出することによって応答する。このフレームは、いくつかの付加情報に加えて、送信側の識別情報を含む。子ノードは、応答している潜在的な親ノードのうちの１つを親ノードとして選択する。この選択は、論理アドレス空間の密集性、または応答するノードの信号強度を考慮することができる。
【００１９】
その後、選択された親ノードは、以下のようにして参加する子ノードに子ノードアドレスを割り当てる。
すなわち、この子ノードアドレスの１つの成分の値は、親ノードの対応する成分よりも１だけ大きくされる。例えば、親ノードＮ１のアドレスが（０，０）である場合には、参加する子ノードＮ２のアドレスは、（０×１，０×０）、または（０×０，０×１）となる。
【００２０】
後の時点で同じアドレスを割り当てる可能性がある他のノードには、アドレス割り当てが通知される。例えば、図１では、ノード２およびノード３がいずれも、ノード４に対して同じアドレスを割り当てる可能性がある。ノード２が最初に割り当てる場合には、ノード３は、アドレス（１，１）がノード４に既に割り当てられていることを、ノード２によって通知される。
【００２１】
本発明の実施の形態１によれば、その割り当て順序は、例えば座標成分の所定の索引方式に従う。例えば、第１の成分が第２の成分の前にインクリメントされる。このように順序を付けることによって、アドレスを一様に分布させることができる。
【００２２】
ここで、選択されたアドレス割り当て順序は、任意の２つのノード間で取り得る経路選択を暗示することにも留意されたい。さらに、１つの特定のノードに対して１つの経路だけを有するようなジグビーの木構造の経路選択とは異なり、本発明のアドレス割り当て方法によれば、図２に示されるように、多数の経路（経路２１〜経路２３）を選択できるようになる。こうして、このネットワークは、全体として、ただ１つのノードの障害によって影響を及ぼされない。実際に、このネットワークは、特に格子の次元数が比較的高い場合には、多数のノードに障害がある場合であっても、機能し続けることができる。
【００２３】
本発明は、好ましい実施形態を例示しながら説明されてきたが、本発明の精神および範囲内で、種々の他の改変および変更を行うことができることは理解されたい。それゆえ、添付の特許請求の範囲の目的は、本発明の真の精神および範囲内に入るような、全ての変形および変更を網羅することである。
【産業上の利用の可能性】
【００２４】
ワイヤレス通信ネットワーク内のノードにアドレスを割り当てるためのさらに有用な方法を提供することができる。
【図面の簡単な説明】
【００２５】
【図１】本発明の実施の形態１によるデカルト座標空間内のノードの格子および対応するアドレスを示す説明図である。
【図２】多数の経路を示す格子の説明図である。
【符号の説明】
【００２６】
１〜４  ノード、２１〜２３  経路、１００  格子。
【図１】
2009505445.tif 000003
【図２】
2009505445.tif 000004
【国際調査報告】
2009505445.tif 000005
2009505445.tif 000006