(57)【特許請求の範囲】
【請求項１】
ネットワークにおける一組のノードを発見する方法であって、
処理すべきノードのグループにおけるノードの中でノードを選択するステップと、
選択されているノードについて発見手順を実行するように指示するステップであって、前記発見手順が、
前記ネットワークの共有伝送媒体上で、現在選択されているノードから近傍発見要求をブロードキャストするステップ、ならびに
前記共有伝送媒体上で、近傍ノードによって送信された返答を前記現在選択されているノードにおいて受信し、前記近傍ノードを前記処理すべきノードのグループに追加するステップ
を含む、前記指示するステップと、
前記グループ中の任意のノードについて前記発見手順を実行しても当該グループが変化しなくなるまで、前記処理すべきノードのグループにおける他のノードについて選択する前記ステップおよび指示する前記ステップを繰り返すステップと、
選択されているノードについてリンク探索手順を実行するように指示するステップであって、前記リンク探索手順が、
現在選択されているノードから、その後のリンク品質の測定のために、１つまたは複数のリンク探索メッセージを近傍ノードに送信するステップ
を含み、
前記リンク探索手順の実行が前記発見手順と組み合わされ、その結果、選択されているノードについて前記発見手順を実行するときに受信された前記返答のうちの少なくとも１つが、前記現在選択されているノードと近傍ノードとの間のリンク品質の測定に関するデータを含む、
前記指示するステップと
を含む、前記方法。
【請求項２】
他のノードについて選択する前記ステップおよび指示する前記ステップを繰り返すステップが、現在選択されているノードについての前記発見手順の間に、少なくとも１つの返答を受信するステップの後で、トリガされる、請求項１に記載の方法。
【請求項３】
前記指示するステップが、ソース・ルーティング・メカニズムを介して、前記選択されているノードについて前記発見手順を実行するように指示するステップを含む、請求項１又は２に記載の方法。
【請求項４】
前記ソース・ルーティング・メカニズムが、ソース・ノードから最初に実行される、請求項３に記載の方法。
【請求項５】
選択されているノードについての前記リンク探索手順が、少なくとも前記選択されているノードについての前記発見手順が完了した後で、実行される、請求項１に記載の方法。
【請求項６】
前記１つまたは複数のリンク探索メッセージを送信するステップが、前記近傍発見要求をブロードキャストするステップの前に実行される、請求項１に記載の方法。
【請求項７】
選択されているノードについて発見手順を実行するときに受信された前記返答が、近傍ノードによってユニキャストされたものである、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
選択されているノードについて発見手順を実行するときに受信された前記返答が、ＣＳＭＡプロトコルを使用して近傍ノードによってユニキャストされたものであり、それにより、前記返答のそれぞれが、前記共有媒体上で他のトラフィックがない中で送信されたものである、請求項７に記載の方法。
【請求項９】
選択されているノードについて発見手順を実行するときに受信された前記返答が、限定された時間の間のみ、前記選択されているノードにおいて考慮される、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
前記近傍発見要求をブロードキャストする前記ステップが繰り返される、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
前記近傍発見要求が、近傍ノードが返答すべきか否かについての情報を含む、請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
前記ソース・ノードが基地局である、請求項４に記載の方法。
【請求項１３】
前記ノードがセンサ・ノードである、請求項１〜１２のいずれか一項に記載の方法。
【請求項１４】
一組のノードを含むネットワークを使用する方法であって、
請求項１〜１３のいずれか一項に記載の方法に従って、前記一組のノードの中のノードを発見するステップと、
時分割多重化を使用して、発見されたノードに通信させるステップと
を含む、前記方法。
【請求項１５】
コンピュータ化されたネットワークのノードに、請求項１〜１３のいずれか一項に記載の方法の各ステップのそれぞれを実行させるための命令を含む、コンピュータ可読媒体に常駐するコンピュータ・プログラム。
【請求項１６】
ノードを含むコンピュータ化されたネットワークであって、前記ノードのそれぞれが、メモリに動作可能に相互接続された少なくとも１つのプロセッサを備え、それにより、請求項１〜１３のいずれか一項に記載の方法のステップのそれぞれを実行するように構成された、前記コンピュータ化されたネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広くは、ネットワークにおける一組のノードの発見を可能にするためのコンピュータ化された方法およびシステムに関し、詳細には、集中型ワイヤレス・センサ・ネットワーク・アーキテクチャのためのトポロジ発見手順に関する。
【背景技術】
【０００２】
多対一通信は、たとえば、環境モニタリングまたはデータ収集の分野におけるセンサ・ネットワーク・アプリケーションなどの、ネットワーク・アプリケーションの一般的な要件である。センサ・ノード（ＳＮ）は、本質的に基地局（ＢＳ）と情報をやり取りし、センサ・ノード同士ではめったに情報をやり取りすることがない。ＳＮは、周期的なデータ・サンプルを発生させ、場合により、メッセージを転送するために他のＳＮを使用して、データ・サンプルをさらなる処理のためにＢＳに送信する。
【０００３】
ＳＮと比較して、ＢＳは、一般に、より強力な処理ユニット、ならびにプログラムおよびデータのためのより多くのメモリもまた備えている。集中型ネットワーク・アーキテクチャは、ＢＳにおいて利用可能なリソースを活用して複雑なルーティング機能を実施し、したがって、センサ・ノードを可能な限り単純に保つことができるので、そのような環境に最も適している。
【０００４】
必要なルーティング情報の計算を可能にするために、ＢＳは、ネットワークの完全なトポロジ、すなわち、配置されているすべてのＳＮ、およびそれらのノード間のワイヤレス・リンクの品質を知る必要がある。
【０００５】
どちらかといえば静的なネットワーク・トポロジの場合には、トポロジ情報を用いてＢＳを手動で構成することができるが、この方法は、ワイヤレスＳＮの数が多いときには、エラーを起こしやすく、実用的でなくなる。
【０００６】
ほとんどのセンサ・ネットワークは、分散型アーキテクチャを有し、そこでは、センサ・ノードが、隣接するノードと情報をやり取りすることによって、ローカル・トポロジ・データベースを構築する。そのような分散型アーキテクチャでは、「グローバルな」トポロジを知る必要がない。
【０００７】
いわゆるＰＥＤＡＭＡＣＳアーキテクチャ［１］は、その動作に自動トポロジ発見を要求する集中型センサ・ネットワーク・アーキテクチャである。ＰＥＤＡＭＡＣＳのトポロジ発見は、２つのフェーズ、すなわち、トポロジ学習フェーズと、トポロジ収集フェーズとを含む。ＢＳは、ネットワークにおけるすべてのノードが受信することを前提とした調整メッセージをブロードキャストすることによって、学習フェーズを開始する。調整メッセージに続いて、ＢＳは、ＳＮによって再ブロードキャストされる木構成メッセージをネットワークにフラッドする。ノードは、そのネイバから受信する木構成メッセージを使用して、そのローカル・トポロジ情報（すなわち、その隣接するノードおよびそれらのノードへのリンクの品質）を構築し、ＢＳにメッセージを送りたい場合に使用することになるノード（その親ノード）を選択する。
【０００８】
トポロジ学習フェーズの後、ＢＳは、やはり調整メッセージをブロードキャストすることによってトポロジ収集フェーズを開始し、調整メッセージは、ネットワークにおけるすべてのノードが受信することを再び前提とする。ノードが第２の調整メッセージを受信するとき、ノードは、前のフェーズで収集したローカル・トポロジを、ＢＳへのその後の転送のために、その親に伝送する。
【０００９】
両方のフェーズにおいて、ノードは、互いの間にはなお調整を有さず、キャリア検知多重アクセス（ＣＳＭＡ）を使用して、考え得る伝送衝突に対処する。
【００１０】
ＴＳＭＰ［２］は、別の集中型センサ・ネットワーク・アーキテクチャである。これは、ＴＤＭＡベースであり、周期的なネイバ発見プロセスのためのタイムスロットを確保する。このタイムスロットの間、ノードは、リンク探索の目的のために、発見メッセージをランダムにやり取りする。結果は、周期的なヘルスレポートを用いて報告される。
【００１１】
Chandraら［３］は、ハイブリッド・ワイヤレス・ネットワークにおける適応性のあるトポロジ発見を開示し、ここでのネットワーク発見手順は、ＰＥＤＡＭＡＣＳのそれに近い。すなわち、手順は、ネットワークの中に、発見メッセージをフラッドすること（ブロードキャストすること）からなる。興味深いことに、ブロードキャストされたメッセージの受信は、肯定応答が受信されるまで、送信元にメッセージを再伝送させることによって確認される。このソリューションは、伝送されるメッセージの総数、およびそれによるブロードキャスト・ニーズの集中を増大させる。
【００１２】
上で引用した以下の参考文献は、したがって、本発明についての背景技術の一部である。
[1] S.C. Ergen, P. Varaija, “PEDAMACS: Power Efficient and Delay AwareMedium Access Protocol for Sensor Networks”, IEEE Trans on Mobile Computing, vol. 5, no 7, July 2006、
[2] K. Pister, L. Doherty, “TSMP: Time Synchronized Mesh Protocol”, Proc IASTED Int. Symposium DistributedSensor Networks (DSN 2008), Nov 16-18 2008, Orlando, Florida, USA、および
[3] R.Chandra, C. Fetzer, K. Hogstedt; “Adaptive Topology Discovery in HybridWireless Networks”; Informatics’02。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】S.C. Ergen,P. Varaija, “PEDAMACS: Power Efficient and Delay Aware Medium Access Protocol for Sensor Networks”, IEEE Trans on Mobile Computing, vol. 5,no 7, July 2006
【非特許文献２】K. Pister,L. Doherty, “TSMP: Time Synchronized Mesh Protocol”,Proc IASTED Int. Symposium Distributed Sensor Networks (DSN 2008), Nov 16-182008, Orlando, Florida, USA
【非特許文献３】R.Chandra,C. Fetzer, K. Hogstedt; “Adaptive Topology Discovery in Hybrid Wireless Networks”; Informatics ’02
【発明の概要】
【発明が解決しようとする課題】
【００１４】
【課題を解決するための手段】
【００１５】
第１の態様によれば、本発明は、ネットワークにおける一組のノードを発見する方法として具体化され、方法は、
−  処理すべきノードのグループにおけるノードの中でノードを選択するステップと、
−  選択されているノードについて発見手順を実装するように指示するステップであって、前記手順が、
−  ネットワークの共有伝送媒体上で、現在選択されているノードからネイバ発見要求をブロードキャストするステップ、ならびに
−  共有伝送媒体上で、ネイバ・ノードによって送信された返答を現在選択されているノードにおいて受信するステップ、および前記ネイバ・ノードを処理すべきノードのグループに追加するステップ
を含む、指示するステップと、
−  一組のすべてのノードが発見されるまで、処理すべきノードのグループにおける他のノードについて選択するステップおよび指示するステップを繰り返すステップと
を含む。
【００１６】
他の実施形態において、前記方法は、以下の特徴のうちの１つまたは複数を含むことができる。
−  他のノードについて選択するステップおよび指示するステップを繰り返すステップが、現在選択されているノードについての発見手順の間に、少なくとも１つの返答を受信するステップの後で、および好ましくは、いくつかの返答を受信するステップの後で、トリガされる、
−  指示するステップが、ソース・ルーティング・メカニズムを介して、選択されているノードについて発見手順を実装するように指示するステップを含む、
−  ソース・ルーティング・メカニズムが、基地局などのソース・ノードから最初に実装される、
−  方法が、選択されているノードについてリンク探索手順を実装するように指示するステップをさらに含み、前記リンク探索手順が、現在選択されているノードから、その後のリンク品質の測定のために、１つまたは複数のリンク探索メッセージをネイバ・ノードに送信するステップを含み、送信するステップが、好ましくは、前記１つまたは複数のリンク探索メッセージを共有伝送媒体上でブロードキャストするステップを含む、
−  選択されているノードについてのリンク探索手順が、少なくとも前記選択されているノードについての発見手順が完了した後で、および好ましくは、一組のノードのすべてのノードが発見された後で、実装される、
−  リンク探索手順の実装が発見手順と組み合わされ、その結果、選択されているノードについて発見手順を実装するときに受信された返答のうちの少なくとも１つが、現在選択されているノードとネイバ・ノードとの間のリンク品質の測定に関するデータを含む、
−  前記１つまたは複数のリンク探索メッセージを送信するステップが、前記ネイバ発見要求をブロードキャストするステップの前に実行される、
−  選択されているノードについて発見手順を実装するときに受信された返答が、ネイバ・ノードによってユニキャストされたものである、
−  選択されているノードについて発見手順を実装するときに受信された返答が、ＣＳＭＡの類のプロトコルを使用してネイバ・ノードによってユニキャストされたものであり、それにより、前記返答のそれぞれが、共有媒体上で他のトラフィックがない中で送信されたものである、
−  選択されているノードについて発見手順を実装するときに受信された返答が、限定された時間の間のみ、前記選択されているノードにおいて考慮される、および
−  ネイバ発見要求をブロードキャストするステップが繰り返され、好ましくは、ネイバ発見要求が、ネイバ・ノードが返答すべきか否かについての情報を含む。
【００１７】
別の態様によれば、本発明は、一組のノードを含むネットワークを使用する方法として具体化され、方法は、前述したうちのいずれか１つの方法に従って、前記一組のノードの中のノードを発見するステップと、時分割多重化を使用して、発見されたノードに通信させるステップとを含む。
【００１８】
さらに別の態様によれば、本発明は、コンピュータ可読媒体に常駐するコンピュータ・プログラムとして具体化され、コンピュータ・プログラムは、コンピュータ化されたネットワークのノードに、本発明の実施形態に従った方法のステップのそれぞれを実装させるための命令を含む。
【００１９】
最後の態様によれば、本発明は、ノード、好ましくは、センサ・ノードを含むコンピュータ化されたネットワークとして具体化され、ノードのそれぞれが、メモリに動作可能に相互接続された少なくとも１つのプロセッサを備え、それにより、コンピュータ化されたネットワークが、本発明の実施形態に従った方法のステップのそれぞれを実装するように構成されている。
【００２０】
次に、本発明を具体化するネットワーク、方法、およびコンピュータ・プログラムの機能が、非限定的な例として、添付の図面を参照して説明される。
【図面の簡単な説明】
【００２１】
【図１】実施形態によるネットワーク発見手順の異なるステップにおけるネットワークノードを概略的に示す図である。
【図２】実施形態によるネットワーク発見手順の異なるステップにおけるネットワークノードを概略的に示す図である。
【図３】本発明の実施形態による方法のステップを実装するために好適な、コンピュータ化されたユニット（たとえば、基地局またはセンサ・ノード）の例を概略的に示す図である。
【図４】実施形態による、リンク探索手順と組み合わされたネットワーク発見手順の高レベルなステップを示す流れ図である。
【図５】発見手順がリンク探索手順の前に実施される代替実施形態において実装されるときの、典型的な高レベルなステップの別の流れ図である。
【図６】図５のステップのうちのいくつかを、実施形態に関与するときの詳細なサブステップに分解する図である。
【図７】図５のステップのうちのいくつかを、実施形態に関与するときの詳細なサブステップに分解する図である。
【図８】図５のステップのうちのいくつかを、実施形態に関与するときの詳細なサブステップに分解する図である。
【図９】図５のステップのうちのいくつかを、実施形態に関与するときの詳細なサブステップに分解する図である。
【図１０】図５のステップのうちのいくつかを、実施形態に関与するときの詳細なサブステップに分解する図である。
【発明を実施するための形態】
【００２２】
最初に、本発明の実施形態による方法の一般的な態様を、その高レベルな変形形態と共に論じる（セクション１）。次に、セクション２で、より具体的な実施形態を説明する。
【００２３】
１．本発明の一般的な態様
図１〜図１０を参照すると、本方法は、通信するために共有伝送媒体１（たとえばワイヤレス）を使用するノード２０、３０を含むコンピュータ化されたネットワーク１６５において実装される。好ましくは、ネットワークは、以下の例により論じるように、ワイヤレス・センサ・ネットワークである。
【００２４】
通常、集中型ネットワーク・アーキテクチャは、以下で基地局（ＢＳ）と呼ばれるソース・ノード１０を中心とすることを前提とする。そのような環境は、ＢＳにおいて利用可能なリソースを活用して、ノードの機能をできる限り単純に保ちながら、ルーティング機能などの重要なタスクを実施する。
【００２５】
以下では、ノードの自動発見を可能にする反復手順を説明する。図１および図２に示すように、参照番号２０は、「現在」選択されているノードを示し、参照番号３０は、ネイバ・ノードを示す。現在選択されているノードは、以下で論じることになる反復手順を通して変化する。ノード間の二方向リンクの品質は、同時に、または続けて調べられる。
【００２６】
そのような手順は、ソース・ノードから数ホップ離れたノードを発見することを可能にし、さらに、短い、決定的なランタイムを可能にする。さらに、動作間のノードによって保有される必要のある状態情報は、わずかであるか、または全くない。
【００２７】
１．１．方法の一般的な実施形態
以下のステップが、モニタリング・エンティティ、たとえば、ＢＳの観点から見て、実装される（図１、図２、図４、および図５に重点を置く）。
−  ステップＳ１１：ノード２０が、最初に、「処理すべき」としてタグ付けされたノードの中で選択され、これは、ネットワーク発見（ＮＤ）手順の実装が、前記ノードについて実施される必要があることを意味する。「処理すべき」としてタグ付けされたノードのグループ（たとえば、リスト）は、通常、ＢＳにおいて保有されている。最初の反復において、ＢＳは、「処理すべき」ノードとして、それ自身を選択する。
−  ステップ１２：選択されているノード２０が、ＮＤ手順を実装するように指示される。ＮＤ手順は以下を含む。
○ステップＳ２２：共有伝送媒体１上で、ＮＤ要求を（すなわち、現在選択されているノード２０から）ブロードキャストするステップ、および
○ステップＳ２３：ＮＤ要求に応答して（ステップＳ３４を参照されたい）、共有伝送媒体上でネイバ・ノード３０によって送信された返答を（すなわち、現在選択されているノード２０において）受信するステップ。返答するノードは、それにより、潜在的な処理されるべきノードとして識別される。それに応じて、返答するノードは、たとえば、現在選択されているノード２０またはＢＳによって、「処理すべき」ノードのグループに追加される。明らかに、前記ノードが既に処理されている場合は、それらはグループに追加される（または保持される）必要はない。たとえば、ノード２０は、返答したすべてのノードをＢＳに報告し、ＢＳは、どのノードがなお処理される必要があるかを決定する。手順は、ノードを複数回識別する結果になるものと思われるため、ＢＳは、好ましくは、複製のないグループを保有する。
−  最終的なステップＳ１４：上のステップは、該当するすべてのノードが発見されるまで、すなわち、グループ中の任意のノードについて再度ＮＤ手順を実装してもグループが変化しなくなるまで、「処理すべき」としてタグ付けされた他のノード３０について繰り返される。
【００２８】
上で述べたように、発見手順は、一回に１つのノードにおいて実装され、すなわち、少なくともブロードキャストするステップは、一回に１つのノードにおいてのみ行われる。したがって、衝突の危険性が低くなる。
【００２９】
１．２．高レベルな変形形態
反復は、通常、基地局より制御される。新たなＮＤ手順を実装するための別の候補ノードを選択する前に、ＢＳは、上で説明したように、現在選択されているノードが（少なくとも）ブロードキャストするステップを完了するのを待つ。現在選択されているノードは、たとえば、ブロードキャストの重なり合いを回避するためなどに、早ければ、ブロードキャストするステップが完了次第、ＢＳに報告することができる。
【００３０】
次に、（好ましくない）実装形態では、ＮＤ手順の他のステップが重なり合うように選ばれてもよく、たとえば、ｎ番目に発見されたノード（ノードｎ）は、ノードｎ＋２からの返答を受信し、このときノードｎ＋１はＮＤ要求をブロードキャストするように既に指示されている。そのような変形形態は、ＮＤ手順を加速することができる。
【００３１】
にもかかわらず、好ましくは、新しいＮＤ手順は、現在選択されているノード２０がネイバ・ノードからの返答を受信した後にトリガされて、共有伝送媒体の使用をさらに最小限にする。したがって、新しいＮＤは、通常、現在選択されているノードからの報告（ネイバ・ノードからの少なくとも１つの返答の受信を証明する報告）を受信次第、開始される。理解されるように、（すべての返答が受信されることを前提とする）ＮＤ手順の完了次第、現在のノードから送信される１つのみの報告につながる特定の手順が好ましい。
【００３２】
どのようにノードに到達するかは、好ましくは、ソース・ルーティング・メカニズムにより達成される。ソース・ルーティングは、それ自体既知である。このメカニズムを本コンテキストに適用することにより、ＢＳが所与のノードにＮＤコマンドを送信することを可能にする。所与のノードについてのソース・ルート情報は、前記所与のノードを以前に検出したノードのソース・ルート情報に基づいて、段階的に構築される。たとえば、ノードＡがＢＳそれ自体によって検出されたネイバである場合、ＢＳからノードＡへのソース・ルートは、「ＢＳ−Ａ」と記されてよく、さらにノードＢがＡのネイバである場合、ＢＳからＢへのソース・ルートは、「ＢＳ−Ａ−Ｂ」であってよく、以下同様である。結果としてのソース・ルートは、要求を送信するためにＢＳによって使用されるだけでなく、ＢＳに（リバース・ソース・ルートを使用することによって）報告するためにノードによってもまた使用される。ソース・ルーティング・メカニズムにより、ＢＳおよびノードは、フラッドする/ブロードキャストするメカニズムを必要とせずに、互いにメッセージを直接やり取りすることができる。また、ＢＳは、ノードに、ＮＤ手順を１つずつ実装するように指示するので、衝突が防止される。したがって、ノードは、その返答をＢＳに送信するときに、ＣＳＭＡを使用する必要がない。
【００３３】
上で説明した反復手順と一緒に使用して、ソース・ルーティング・メカニズムは、間接的であれ、離れたノードに到達することを可能にして、その結果、直接のブロードキャスト距離（シングルホップ）を超えたノードにさえ、到達することができる。したがって、本方法は、地理的に拡大されたネットワークに適用され、ＢＳによってブロードキャストされたメッセージがネットワークにおけるすべてのノードによって直接受信され得ることは、重要ではない。
【００３４】
次に、リンク探索（ＬＰ）手順が、好ましくは、ＮＤ手順に加えて実施されることになる。ＬＰ手順は、ＮＤ手順の間に識別されたノード間のリンク品質を評価することを狙いとする。ＬＰ手順は、その他の点ではＮＤ手順と類似しており、それは、通常、ＢＳより制御される反復プロセスである。
【００３５】
図４に示すように、ＬＰ手順を、ＮＤ手順と絡み合わせることができる。にもかかわらず、いくつかのスケジュールの可能性、すなわち、いつＬＰ手順を開始するかを企図することができる。たとえば、少なくとも現在のノード２０についてのＮＤ手順が完了した後で、前記現在のノードにおいて、ＬＰ手順を実装することができる。好ましい変形形態では、図５に示すように、すべてのノードが発見されてから、ＬＰ手順を開始する。この最後のシナリオは、より決定的である。（より短い）ＮＤ手順を完了するために必要な時間は、容易に決定され、絡み合わせたＬＰ手順によって乱されることがない。
【００３６】
ＬＰ手順を開始するために、ＢＳは、現在選択されているノード２０に、ＬＰ手順を実装するように指示する（図４、ステップＳ１２または図５、ステップＳ１６）。ＬＰ手順は、したがって通常、ステップＳ２１で、その後のリンク品質の測定（ステップＳ３１）のために、１つまたは複数のＬＰメッセージを、選択されているノード２０に隣接するノード３０に「送信すること」によって開始される。
【００３７】
そこでは、２つの変形形態を企図することができ、すなわち、「送信すること」は、リンク方法またはブロードキャスト方法を指すことができる。
【００３８】
−  リンク方法
この方法では、すべての該当するリンクが個々に探索される。ＢＳは、（発見されたノードのリスト外の）所与のノード２０に、所与のネイバｎ（すなわち、ノード３０の中の１つのノード）からのリンクを探索するための要求を送信する。この要求を受信すると、ノード２０は、ノードｎに、それに対するいくつかのメッセージを送信するよう求める。ノード２０は、ノードｎによってバースト送信されたメッセージをリスンし、エラーなしで受信できたメッセージの数をカウントし、受信した信号強度インジケータ（ＲＳＳＩ、すなわち、受信した無線信号に存在する電力の測定）または他のインジケータあるいはその両方を測定するなどし、結果をＢＳに報告して返す。ノード２０についてのリンク探索手順は、ＢＳが、すべてのノードにすべての隣り合うリンクを探索するよう求めたとき、終了する。
【００３９】
−  ブロードキャスト方法
このアプローチでは、ＢＳによって送信されたリンク探索要求を受信すると、選択されているノード２０が、いくつかのメッセージをブロードキャストする。ブロードキャストを受信することができるネイバ・ノード３０は、エラーなしで受信できたメッセージの数をカウントし、結果としてのＲＳＳＩを測定するなどする。
【００４０】
次に、どのように結果をＢＳに転送することができるかについて、少なくとも２つのオプションが存在する。すなわち、
○ノード２０が、各ネイバ３０に個別に尋ね、結果を基地局に送信する、または
○基地局が、隣接するノードに直接結果を要求する。
別のオプションは、図４を参照して、後述することにする。
【００４１】
ＮＤ手順におけるのとまさに同じように、共有伝送媒体１上でＬＰメッセージをブロードキャストすることは、一回に１つのノード（ノード２０）が選択されるので、効果的なアプローチのままである。たとえば、Ｎ個のノードを備えるネットワークについて、ブロードキャスト方法は、Ｏ（Ｎ）個の測定のみを必要とし、一方リンク方法は、Ｏ（Ｎ２）個の測定を必要とする。したがって、ブロードキャスト方法のランタイムの方が著しく短い。リンク方法およびブロードキャスト方法の両方において、ノードは同時に伝送していないので、したがって、ＣＳＭＡの類のアプローチは必要とされないことにも留意されたい。
【００４２】
次に、ステップＳ３４で、ＮＤ手順またはＬＰ手順あるいはその両方を実装するときにネイバ・ノードによって送信される返答が、効率化のために、好ましくは、ユニキャストされる。返答メッセージの受信の成功は、たとえば、８０２．１５．４ＭＡＣ層のリンク肯定応答メカニズムを使用して、肯定応答されてよい。
【００４３】
複数のノードが同時に返答することがあるので、ここで、返答するノードは、ＣＳＭＡの類のプロトコルを使用して、考え得る衝突に対処することができ、それにより、それ自体知られているように、返答は、共有媒体１の上で他のトラフィックがない中で送信される。これは、図７を参照して、さらに論じることにする。
【００４４】
また、現在選択されているノード２０において受信される返答は、好ましくは、限定された時間の間（タイマＴＢがあらかじめトリガされる）のみ考慮されて、手順をより決定的なものにする。通常、ＮＤ要求をブロードキャストするステップは、数回繰り返され、ＮＤ要求は、ネイバ・ノードが返答すべきか否かについての情報を含んでいる。
−  たとえば時間制限のために、前のラウンド内でその返答を伝送することに成功しなかった、または
−  前のラウンドに気付かなかった
ノードのみが、最初のラウンドに対するのと同じ手順を使用して、新しい要求に答える。これにより、答えるノードの数を減らし、したがって、返答に成功するためのその機会を増やすことになる。全体の手順は、決定的なままである。
【００４５】
ノード密度に応じて、そのネイバをすべて発見するために、ノードによってさまざまな発見ラウンドが必要とされることがある。実装形態のオプションとして、発見手順は、一定の数のラウンドの後に、または、最後のラウンドの間に応答するノードの数が特定の値よりも小さい場合に、終了してよい。
【００４６】
２．特定の実施形態
図４および図５の実施形態は、ＮＤ手順対ＬＰ手順の順序において、本質的に異なっている。図４では、両方の手順は絡み合っており、一方、図５では、ＬＰ手順をトリガする前に、ＮＤ手順は完了している。最初に、図５の実施形態について詳細に論じる。
【００４７】
２．１  連続的なＮＤ手順およびＬＰ手順
以下では、ネットワーク発見を可能にするための方法およびシステムの特定の実施形態を、図５〜図１０を参照して説明する。ここで、図５からわかるように、ＬＰ手順（ステップＳ１５〜Ｓ１７）は、すべてのノードが発見されてから、現在のノード２０において実装される。このシナリオは、（より短い）ＮＤ手順を完了するために必要な時間が容易に決定され、（より長い）ＬＰ手順によって乱されることがないので、図４のシナリオよりも「決定的」である。より詳細には、ＬＰ手順は、本質的に決定的な継続時間を有し、一方、ＮＤは有さない（すなわち、開始において、いくつのノードが存在するかが既知ではない）。利点は、通常、短いＮＤのコアステップＳ２２〜Ｓ２３を、継続時間に関して実質的な重要性なしに、（必要であれば）すべての既知のノードが見つかるまで繰り返す（Ｓ２４）ことができることである。これに対して、より長いＬＰ手順は、一回のみ実行される。
【００４８】
通常、ＢＳ１０は、まだ処理されていないノードの中で現在のノード２０を選択し（ステップＳ１１）、ステップＳ１２で、選択されているノード２０にＮＤ手順を最初に開始するように指示する。手短に言えば、ＢＳは、たとえば、ソース・ルーティングを使用して、コマンドＮＤ−ＣＭＤをノード２０に送信する。ＮＤ２０は、媒体１にＮＤ要求をブロードキャストすることによって反応する。ステップＳ３１で、ＮＤ要求を受信すると、ネイバ・ノード３０は要求を処理し（ステップＳ３３）、適切な応答ＮＤ−ＲＥＳＰを返答し（ステップＳ３４）、それにより、それ自身をノード２０に対して識別する。ステップＳ２３で、ノード２０において応答が受信され、ノード２０はそれに応じて、ステップＳ２５で、リバース・ソース・ルーティングを使用してＢＳに報告する。
【００４９】
上のステップは、次に図６（現在選択されているノード２０において実施されるステップを説明する）、および図７（ネイバ・ノードに関連する）を参照して説明する、いくつかのサブステップにさらに分解することができる。
【００５０】
図６を参照すると、以下のスキームを実装することができる。
−  ステップＳ２２０：ノード２０はリスンしている（ノード２０は、ＢＳによって選択されたことにまだ気付いていない）、
−  ステップＳ２２１：ノード２０は、ＢＳからＮＤコマンド（ＮＤ−ＣＭＤ）を受信し、
−  ステップＳ２２２：ノード２０は、カウンタＢＣをゼロに、ならびに返答するノードの組Ｎを初期化し、
−  ステップＳ２２３：ノード２０は、ＮＤ要求をブロードキャストし、
−  ステップＳ２２４：タイマＴＢを開始し、
−  ステップＳ２２５：ノード２０は、リスニング・モードに戻って、考え得る応答を待つ。
【００５１】
理解できるように、上のステップ２２１〜２２５は、単に、図５のステップＳ２２に対応している。より一般的には、ＮＤコマンドを受信するステップ、およびＮＤ要求をブロードキャストするステップから、より一般的に構成される、任意の好適なスキームを企図することができる。
【００５２】
同様に、図５のステップＳ２３は、以下のステップに分解されてよい。図６を参照されたい。
−  ステップＳ２３１：ネイバ・ノード３０の中の特定のノードｎから、ノード２０において応答ＮＤ−ＲＥＳＰが受信されると、
−  ステップＳ２３２：ノード２０は、返答ノードｎに従って組Ｎを更新し（ノードｎについての好適な識別子がＮに追加される）、
−  ステップＳ２３３：ノード２０は、リスニング・モードに戻って、さらなる応答を待ち、
−  ステップＳ２３４：一方で、以前に設定されたタイマＴＢが満了した場合、
−  ステップＳ２３５：ノード２０はＢＣをインクリメントし、
−  ステップＳ２３６：最大カウンタ値に到達しているかどうかをチェックする。到達していない場合、ステップＳ２２３で、ＮＤ＿ＲＥＱが再ブロードキャストされることになる。図５のステップＳ２４に示すように、ノード２０は、それに応じて、ＮＤ＿ＲＥＱを数回再伝送する。したがって、選択されているノード２０についてＮＤ手順を実装するときに受信された返答は、限定された時間の間のみ考慮される。最大カウンタ値に到達している場合、ステップＳ２５で、ノード２０は、レポート（ＮＤ＿ＲＥＰＯＲＴ）を準備してＢＳに送信する。ノード２０は最終的に、リスニング・モードに戻る。
【００５３】
その間に、以下のスキームを、ネイバ・ノード３０において実装することができる。ネイバ・ノード３０の中の特定のノード（たとえばノードｎ）を考えることにする。
−  ステップＳ３３０：ノードはリスンしている、
−  ステップＳ３３（図５でも同様）が、以下に分解される。
○ステップＳ３３１：ＮＤ＿ＲＥＱがノード２０から受信される。述べたように、ＮＤ要求は、ネイバ・ノードが返答すべきか否かについての情報を含む。通常、前記情報は、既に返答しているノードの識別子（ＩＤ）からなる。
○ステップＳ３３２：ノードｎは、それに応じて、それ自身のＩＤを、ＮＤ要求が含むかどうかをチェックする。含む場合、ステップ３４０で、ノード３０はリスニング・モードに戻る。含まない場合、ノードｎは、ステップＳ３４で、ＮＤ応答を送信することによって返答することになる（図５も参照されたい）。先に述べたように、この応答は、通常、ＣＳＭＡの類のプロトコルを使用してユニキャストされ、すなわち、応答は、他のトラフィックのない中で送信される。
−  ステップＳ３４：それに応じて、応答手順は、以下に分解されてよい。
○ステップＳ３４１：タイマが開始され、
○ステップＳ３４２：ノードｎは、媒体（たとえば無線チャネル）が空いているかどうかをチェックし、
○ステップＳ３４３：空いていない場合、ノードｎは、ランダム・バックオフを開始し、
○ステップＳ３４４：ノードは、ランダム・バックオフが満了するのを待ち、
○ステップＳ３４５：バックオフが満了すると、ノードｎは、ステップＳ３４２に戻って、媒体が空いているかどうかをチェックし、
○ステップＳ３４６：一方で、ステップＳ３４１で設定されたタイマが満了した場合、
○ステップＳ３４７：次いでノードｎは、バックオフを停止して、ステップＳ３４０のリスニング・モードに戻り、
○ステップＳ３４８：次に、ステップＳ３４２でチェックしたときに媒体が空いている場合、ノードｎは、要求するノード２０に応答をユニキャストするように進むことができ、
○ステップＳ３４９：ステップＳ３４１で設定されたタイマはしたがって停止され、ノードｎは、ステップ３４０のリスニング・モードに戻る。
【００５４】
ノード２０から受信したレポートＮＤ＿ＲＥＰＯＲＴに基づいて、ＢＳは、次にどのノード３０をなお処理すべきかを決定することができる（ステップＳ１３）。ＮＤ手順は、それに応じて、すべてのノードが発見されるまで、ステップＳ１４で再び反復される。
【００５５】
次に、ＮＤ手順が完了すると、ＢＳ１０は、応答した一組のノードに気付いて、ＬＰ手順を開始することができる。さらに、ＢＳは、各ノードについてそのネイバのリストおよびソース・ルートを含む、ノードのリストを有し、これが、前記各ノードにメッセージを送信するために使用されてよい。その情報に基づいて、ＢＳは、リスト上のすべての個別のノードに、リンク探索手順を実施するように要求し、その詳細は以下で説明する。リストのすべてのノードがリンク探索手順を実施すると、リンク探索手順は終了し、結果が基地局に転送される。リンク品質が次いで、収集された統計に基づいて、ＢＳにおいて蓄積される。
【００５６】
ＬＰ手順を実装するために、ＢＳは、最初にノード（再び参照番号２０によって示される）を選択し（図５、ステップＳ１５）、選択されているノード２０に、ＬＰ手順をローカルに開始するように指示することになる。すなわち、ステップＳ１６で、ＢＳは、コマンドＬＰ＿ＣＭＤをノード２０に送信する。
【００５７】
広くは、選択されているノード２０が、１つまたは複数のリンク探索メッセージＬＰ＿ＭＳＧ（図５、ステップＳ２１）をブロードキャストすることによって反応する。より詳細には、および図８に示すように、ノード２０は以下のステップを実施する。
−  ステップＳ２１０：ノード２０は、ネットワークをリスンし、
−  ステップＳ２１１：基地局から送信されたＬＰコマンドを受信し、
−  ステップＳ２１２：次いで、リンク探索メッセージＬＰ＿ＭＳＧをＭ回ブロードキャストし、
−  ステップＳ２１３：それに応じてＢＳに肯定応答し（ステップＳ２１にも示す通り、送信されるＬＰ＿ＡＣＫ）、リスニング・モードに戻る。ＢＳは、他のノード２０を続けることができる（ステップＳ１７）（およびステップＳ１５、Ｓ１６などを再反復する）。
【００５８】
それに応じて、（ネイバ・ノード３０の中の）ネイバ・ノードｎは、図９に従って進むことができ、すなわち、
−  ステップＳ３１０：ノードｎはリスンしている、
−  ステップＳ３１１：ＬＰメッセージＬＰ＿ＭＳＧがノード２０から受信され、
−  ステップＳ３１２：ノードｎは、対応するリンク探索メッセージ・トレインのＩＤ（ＬＰ＿ＩＤ）をチェックする、すなわち、受信したばかりのメッセージＬＰ＿ＭＳＧが属するメッセージ・トレインについて、リンク品質測定が既に実行されているかどうかをチェックする。加えて、ＬＰ＿ＭＳＧは、送信するノードのＩＤを含む。
−  ステップＳ３１３：リンク探索メッセージ・トレインのＩＤが新しい場合、ノードｎは、実行している現在のＬＱＭプロセスを削除し、
−  ステップＳ３１４：新しいＬＱＭプロセスを開始し、
−  ステップＳ３１５：ＬＰメッセージ・トレインのＩＤが新しくない場合（ＬＱＭプロセスは、そのＬＰメッセージ・トレインについて既に実行されていることを意味する）、ノードｎは、実行している現在のＬＱＭプロセスを更新するように指示する。
【００５９】
ＬＱＭプロセスの結果は、任意のノードによって要求されてよい。好ましくは、図５に示すように、ＢＳがＬＱＭ結果を収集することになる。それに応じて、ステップＳ１８で、ＢＳからコマンドが送信され、ステップＳ３５で、ノードｎにおいて受信され、そこでのその後の処理（ステップＳ１９）のために、ステップＳ３６で、結果（ＬＱＭ＿ＲＳＰ）が要求ノードに再び送信し戻される。ノードｎ受信ノードの観点から、これがどのように管理されるかが、図１０において、別のやり方で簡単に概説される。最初に、ステップＳ３５０で、ノードｎはリスンしている。次いで、ステップＳ３５で、（任意のノード２０によって、またはＢＳによって送信された）ＬＱＭ＿ＲＥＱが受信される。次いで、ステップＳ３６で、該当するＬＱＭプロセスの結果が、対応する応答ＬＱＭ＿ＲＳＰの中に入れられ、要求ノードに送信されてよい。
【００６０】
最後に、すべてのＬＱＭ結果が既知になると、たとえば、ＴＤＭＡ（図示せず）を使用して、適切な通信を開始することができる。
【００６１】
２．２  組み合わされたＮＤ手順およびＬＰ手順
以下では、ネットワーク発見を可能にする実施形態を、図４を参照してより具体的に説明する。上で述べたように、ＬＰ手順およびＮＤ手順は今、絡み合っている。理解されるように、ＬＰ手順およびＮＤ手順を組み合わせるステップは、いくつかのステップを省くことを可能にし、いくつかの場合においてより効率的になることがある。
【００６２】
より正確には、および図４に示すように、ＬＰ手順はＮＤと組み合わされ、その結果、ＮＤ要求に応答して（現在選択されている）ノード２０において受信された返答が、現在のノード２０と返答するノードｎとの間のリンク品質の測定に関するデータを含む（ステップＳ２３）。言い換えれば、その場合、ＮＤ要求が到着するとき、リンク品質測定（ＬＱＭ）に関するデータが利用可能になるように、ＮＤに先立ってＬＰが開始される。そのような結果は、したがって、ＮＤ要求に応答して追加されてよく、その結果、ＮＤ応答およびＬＱＭ結果が合わせて収集される。
【００６３】
より具体的には、その場合、ＢＳ１０が、通常、選択されているノード２０に、ＬＰ手順およびＮＤ手順の両方を開始するように指示することになる。図４を参照されたい。すなわち、ＢＳは、たとえば、ソース・ルーティングを使用して、ＬＰ／ＮＤ＿ＣＭＤと呼ばれる専用コマンドをノード２０に送信する。変形形態では、ＢＳは、最初に、ＬＰ＿ＣＭＤを送信し、後に、ノード２０の肯定応答時に、ＮＤ−ＣＭＤを送信する。
【００６４】
次に、選択されているノード２０は、前記１つまたは複数のリンク探索メッセージＬＰ＿ＭＳＧを送信することによって、たとえば、前記メッセージをブロードキャストすることによって、反応する。選択されているノード２０はさらに、必要であれば、ＬＰ＿ＣＭＤの受信を肯定応答することができる。
【００６５】
受信すると、ステップＳ３１で、ネイバ３０の中の所与のネイバ・ノードｎは、ＬＱＭに進み、結果を後の使用のために記憶する。他のネイバ・ノードは、実際には、ブロードキャストするノード２０、またはＢＳによって後で選択される他のノードに対して、本質的に同じやり方で進むことになる。
【００６６】
その後（たとえば、タイマの満了後、またはＢＳからの指示のとき）、ノード２０がＮＤ要求（ＮＤ＿ＲＥＱ、ステップＳ２２）をブロードキャストするとき、ステップＳ３３で、同じネイバ・ノードｎがＮＤ要求を処理し、ステップＳ３４で、ＬＱＭの結果を付加して、対応する応答（ＮＤ＿ＲＥＳＰ）を送信することによって返答することができる。したがって、ネイバ・ノード３０の合わさった応答は、ＮＤ要求に対する応答、および該当するリンクについてのＬＱＭ結果の両方を含むものになると思われ、それにより、１つの再伝送ステップが省かれる。
【００６７】
ステップＳ２３で、現在のノード２０において合わさった応答が受信される。ＮＤ要求をブロードキャストするステップは、通常は繰り返されて（ステップＳ２４）、すべてのネイバによる確かな受信を保証する。
【００６８】
次に、ステップＳ２５で、現在のノード２０は、どのノードが返答し、それにより識別されたかを、ＢＳにおけるその後の処理のために、ＢＳ１０に報告することができる。加えて、ＬＱＭ結果がＢＳに渡される。
【００６９】
ＢＳは、それに応じて、どの新しいノードがなお「処理される」必要があるか、すなわち、ＬＰ／ＮＤ手順を実装するとこれまでに識別されていないさらに別のノードにつながる可能性のある新しいノードを決定する。
【００７０】
ステップＳ１４で、ＢＳは、それに応じて、すべてのノードが処理されるまで、すべてのノードを通して反復する。最終的に、すべてのノードが識別され、ＬＱＭ結果が既知になると、たとえば、時分割多重アクセス（ＴＤＭＡ、図示せず）などの時間多重化スキームを使用して、ノード間で適切な通信を実装することができる。ノードが互いについて既知でない限りは、時間多重化が関与することはなかった。
【００７１】
次に、考え得る変形形態として、ＮＤおよびＬＰのブロードキャストするステップ（ステップＳ２１およびＳ２２）を合併することを企図することができる。すなわち、リンク探索メッセージが、ネイバ発見要求として働くことができ、ステップＳ２１およびＳ２２が、１つの同じステップとなり得る。しかし、ＬＰ手順は、通常、どちらかというと多数のメッセージをブロードキャストし、一方で、ＮＤ手順は、数回、たとえば１〜３回、再ブロードキャストされる１つのメッセージのみを送信することを必要とするので、それは全体の手順の継続時間を伸ばすことになるものと思われる。
【００７２】
３．ノードの説明
好ましくは、センサ・ノードが考えられる。センサ・ノード（またはモート（mote））は、知覚情報を集め、いくつかの（限定された）処理を実施し、ネットワークにおける他の接続されたノードと通信するように構成されている。上で述べたように、ＢＳは、通常、より複雑なタスクを実施するように構成されている。ＢＳは、より多くの計算的能力およびメモリ能力を有するスーパーノードとしてみなされてよい。すべての場合において、ノードおよびＢＳは、それぞれ、図３に示すような、コンピュータ化されたユニットとしてみなされてよい。
【００７３】
知られているとおり、センサ・ノードの主要なコンポーネントは、通常、以下である。
○プロセッサ・コア、
○メモリ、
○プログラム、および
○プログラマブル入力／出力周辺装置、たとえば、タイマ、イベントカウンタなど、
を含む、マイクロコントローラ。
【００７４】
マイクロコントローラは、データを処理し（単純なタスクを実施し）、一般には以下の、ノードにおける他のコンポーネントを制御する。
−  ネットワークと対話するためのトランシーバ（またはより一般的にはネットワーク・インターフェース）、
−  外部メモリまたはストレージ、
−  電源、および
−  入力コントローラを通してインターフェースされた１つまたは複数のセンサ。
【００７５】
ノードおよびＢＳは、上で説明した本発明の態様を実装するために設計されている。その点に関して、本明細書で説明する方法は、多くが非対話式で、自動化されていることが理解されるであろう。例示的な実施形態において、本明細書で説明する方法は、対話式の、部分的に対話式の、または非対話式のシステムにおいて実装されてよい。本明細書で説明する方法は、ソフトウェア（たとえば、ファームウェア）、ハードウェア、またはそれらの組み合わせにおいて実装されてよい。例示的な実施形態において、本明細書で説明する方法は、実行可能なプログラムとしてのソフトウェアにおいて実装され、プログラムは、特殊なデジタル・コンピュータ（ノードおよびＢＳ）によって実行される。より一般的には、本発明の実施形態は、パーソナル・コンピュータ、ワークステーションなどの、汎用デジタルコンピュータを使用して実装されてよい。
【００７６】
図３に示すシステム１００は、コンピュータ化されたユニット１０１、たとえば、センサ・ノードまたはＢＳの役割を果たすことができる汎用コンピュータを概略的に表す。例示的な実施形態において、ハードウェア・アーキテクチャの観点から、図３に示すように、ユニット１０１は、プロセッサ１０５、メモリ・コントローラ１１５に結合されたメモリ１１０、および、ローカルな入力／出力コントローラ１３５を介して通信可能に結合された１つもしくは複数の入力または出力（Ｉ／Ｏ）あるいはその両方のデバイス、１４０、１４５、１５０、１５５（または周辺装置）を含む。入力／出力コントローラ１３５は、限定はしないが、当技術分野で知られるような、１つもしくは複数のバス、または他のワイヤ接続もしくはワイヤレス接続であってよい。入力／出力コントローラ１３５は、簡略化のために省略してある、コントローラ、バッファ（キャッシュ）、ドライバ、リピータ、および受信機などの追加の要素を有して、通信を可能にすることができる。さらに、ローカル・インターフェースが、アドレス接続部、制御接続部、またはデータ接続部あるいはそのすべてを含んで、上述したコンポーネントの中での適切な通信を可能にすることができる。
【００７７】
プロセッサ１０５は、ソフトウェア、とりわけメモリ１１０に記憶されたソフトウェアを実行するためのハードウェア・デバイスである。プロセッサ１０５は、任意のカスタム・メイドまたは市販のプロセッサ、中央処理装置（ＣＰＵ）、ユニット１０１に関連付けられたいくつかのプロセッサの中の補助プロセッサ、（マイクロチップもしくはチップセットの形態の）半導体ベースのマイクロプロセッサ、または、ソフトウェア命令を実行するための一般的な任意のデバイスであってよい。
【００７８】
メモリ１１０は、揮発性メモリ要素（たとえば、ランダム・アクセス・メモリ）および不揮発性メモリ要素のうちの任意の１つ、またはそれらの組み合わせを含むことができる。さらに、メモリ１１０は、電子的な、磁気的な、光学的なストレージ媒体または他のタイプのストレージ媒体あるいはそれらのすべてを組み込むことができる。メモリ１１０は、さまざまなコンポーネントが互いからリモートに位置するものの、プロセッサ１０５によってアクセス可能である、分散型アーキテクチャを有することができることに留意されたい。
【００７９】
メモリ１１０の中のソフトウェアは、１つまたは複数の別個のプログラムを含むことができ、そのそれぞれが、論理機能を実装するための実行可能な命令の順序付けられたリストを含む。図３の例において、メモリ１１０の中のソフトウェアは、例示的な実施形態による本明細書で説明する方法、および好適なオペレーティング・システム（ＯＳ）１１１を含む。ＯＳ１１１は、本質的に、本明細書で説明するような方法（たとえば、図４〜図１０）などの他のコンピュータ・プログラムの実行を制御し、スケジューリング、入力出力制御、ファイルおよびデータ管理、メモリ管理、ならびに通信制御および関連サービスを提供する。
【００８０】
本明細書で説明する方法は、ソース・プログラム、実行可能なプログラム（オブジェクト・コード）、スクリプト、または実施すべき一組の命令を含む任意の他のエンティティの形式であってよい。ソース・プログラム形式のとき、プログラムは、ＯＳ１１１と関係して適切に動作するために、メモリ１１０内に含まれても、含まれなくてもよいコンパイラ、アセンブラ、インタプリタなどを介して翻訳される必要がある。さらに、方法は、データのクラスおよびメソッドを有するオブジェクト指向プログラミング言語として、または、ルーチン、サブルーチン、または関数あるいはそれらのすべてを有する手続き型プログラミング言語として書かれてよい。
【００８１】
場合により、（とりわけＢＳのために、必要であれば）従来のキーボード１５０およびマウス１５５は、入力／出力コントローラ１３５に結合されてもよい。他のＩ／Ｏデバイス１４０〜１５５は、（特にノードの場合における）センサ、すなわち、温度または圧力（モニタされるべき物理的データ）のような物理的条件の変化に対する測定可能な応答を生成するハードウェア・デバイスを含むことができる。通常、センサによって生成されるアナログ信号は、アナログ・デジタル変換器によってデジタル化され、さらなる処理のためにコントローラ１３５に送信される。センサ・ノードは、理想的には、小さく、エネルギー消費が低く、自律型で無人で動作する。ワイヤレス・センサ・ノードは、通常は小さな電子デバイスであるため、好ましくは、たとえば、０．５〜２アンペア時および１．２〜３．７ボルト未満の、限定された電源を備えている。
【００８２】
加えて、Ｉ／Ｏデバイス１４０〜１５５は、入力部および出力部の両方と通信するデバイスをさらに含むことができる。システム１００は、ディスプレイ１３０に結合されたディスプレイ・コントローラ１２５をさらに含むことができる。例示的な実施形態において、システム１００は、ネットワーク１６５に結合するためのネットワーク・インターフェースまたはトランシーバ１６０をさらに含むことができる。
【００８３】
ネットワーク１６５は、ユニット１０１と外部システム（ノード／ＢＳ）との間で、データを送受信する。述べたように、ネットワーク１６５は、好ましくは、たとえばワイヤレス・プロトコルおよび技術を使用する、ワイヤレス方式で実装される。本実施形態は、好ましくは、低電力ネットワーク、たとえば、ＩＥＥＥ８０２．１５．４に焦点を置く。しかしながら、他のプロトコルおよび技術を使用する他の実施形態が企図されてもよい。そのような多くの技術が存在し（たとえば、固定ワイヤレス・ネットワーク、ワイヤレス・ローカル・エリア・ネットワーク（ＬＡＮ）、ワイヤレス・ワイド・エリア・ネットワーク（ＷＡＮ）など）、それら自体が知られており、ここでさらに説明する必要はない。ネットワーク１６５はまた、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、インターネット・ネットワークなどのパケット交換ネットワーク、または他のタイプのネットワーク環境などであってよい。
【００８４】
ユニット１０１が、ＰＣ、ワークステーション、インテリジェント・デバイスなどである場合、メモリ１１０の中のソフトウェアは、基本入出力システム（ＢＩＯＳ）（簡略化のために省略されている）をさらに含むことができる。ＢＩＯＳは、ユニット１０１が起動したときに実行され得るように、ＲＯＭに記憶されている。
【００８５】
ユニット１０１が動作しているとき、プロセッサ１０５は、メモリ１１０内に記憶されたソフトウェアを実行し、メモリ１１０へのおよびメモリ１１０からのデータを通信し、ソフトウェアに従ってユニット１０１の動作を全体的に制御するように構成されている。本明細書で説明する方法およびＯＳ１１１は、全体として、または部分的に、プロセッサ１０５によって読み込まれ、通常はプロセッサ１０５内にバッファされ、次いで実行される。
【００８６】
本明細書で説明するシステムおよび方法がソフトウェアにおいて実装されるとき、方法は、任意のコンピュータに関連したシステムまたは方法による使用のために、またはそれらに関係して、ストレージ１２０などの任意のコンピュータ可読媒体に記憶されてよい。
【００８７】
当業者によって理解されるように、本発明の態様は、システム、方法、またはコンピュータ・プログラム製品として具体化されてよい。したがって、本発明の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、またはソフトウェア態様およびハードウェア態様を組み合わせる実施形態の形を取ることができる。さらに、本発明の態様は、コンピュータ可読プログラム・コードがそこで具体化される１つまたは複数のコンピュータ可読媒体において具体化される、コンピュータ・プログラム製品の形を取ることができる。
【００８８】
１つまたは複数のコンピュータ可読媒体の任意の組み合わせが利用されてもよい。コンピュータ可読媒体は、コンピュータ可読信号媒体、またはコンピュータ可読ストレージ媒体であってよい。コンピュータ可読ストレージ媒体は、たとえば、限定はしないが、電子的な、磁気的な、光学的な、電磁気的な、赤外線の、または半導体のシステム、装置、またはデバイス、あるいは上記の任意の好適な組み合わせであってよい。コンピュータ可読ストレージ媒体のより具体的な例（非包括的なリスト）には、１つまたは複数のワイヤを有する電気的接続、ハードディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能なプログラマブル読み出し専用メモリ（ＥＰＲＯＭまたはフラッシュメモリ）、光ファイバ、ポータブル・コンパクト・ディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）、光学ストレージデバイス、磁気ストレージデバイス、または、上記の任意の好適な組み合わせを含むであろう。この文書のコンテキストにおいて、コンピュータ可読ストレージ媒体は、命令実行システム、装置、もしくはデバイスによる使用のための、またはそれらに関係したプログラムを、収容する、または記憶することができる任意の有形な媒体であってよい。
【００８９】
コンピュータ可読信号媒体は、たとえば、ベースバンドにおいて、または搬送波の一部として、コンピュータ可読プログラム・コードをその中に組み入れられた、伝搬されたデータ信号を含むことができる。そのような伝搬された信号は、限定はしないが、電磁気的、光学的、またはそれらの任意の好適な組み合わせなどを含む、さまざまな形のうちのいずれかを取ることができる。コンピュータ可読信号媒体は、コンピュータ可読ストレージ媒体ではなく、また命令実行システム、装置、もしくはデバイスによる使用のための、またはそれらに関係したプログラムを、通信する、伝搬する、もしくは移送することができる、任意のコンピュータ可読媒体であってよい。
【００９０】
コンピュータ可読媒体上で具体化されたプログラム・コードは、限定はしないが、ワイヤレス、ワイヤ線、光ファイバ・ケーブル、ＲＦなど、または上記の任意の好適な組み合わせを含む、任意の適切な媒体を使用して、伝送されてよい。
【００９１】
本発明の態様についての動作を実行するためのコンピュータ・プログラム・コードは、１つまたは複数のプログラミング言語の任意の組み合わせで書かれてよく、プログラム言語には、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語などの従来の手続き型プログラミング言語、または同様のプログラミング言語が含まれる。プログラム・コードは、完全にユニット１０１（ノードまたはＢＳ）上で、一部をユニット１０１上で、一部をユニット１０１および別のユニット１０１上で、同様かどうかにかかわらず、実行することができる。プログラム・コードは、一部をユーザのコンピュータ上および一部をリモート・コンピュータ上で、または完全にリモート・コンピュータもしくはサーバ上で、実行することができる。
【００９２】
本発明の態様が、本発明の実施形態による方法、装置（システム）、およびコンピュータ・プログラム製品の流れ図またはブロック図あるいはその両方を参照して、上で説明された。流れ図またはブロック図あるいはその両方の各ブロックは、コンピュータ・プログラム命令によって実装されてよいことが理解されるであろう。これらのコンピュータ・プログラム命令は、汎用コンピュータ、特殊用途コンピュータ、または他のプログラマブル・データ処理装置のプロセッサに提供されて、マシンを生成することができ、その結果、コンピュータまたは他のプログラマブル・データ処理装置のプロセッサを介して実行される命令が、流れ図またはブロック図あるいはその両方の１つもしくは複数のブロックにおいて指定された機能／作用を実装するための手段を作成する。
【００９３】
コンピュータ・プログラム命令はまた、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイス上にロードされて、コンピュータ、他のプログラマブル装置、または他のデバイス上で一連の動作ステップを実施させて、コンピュータ実装プロセスを生成し、その結果、コンピュータまたは他のプログラマブル装置上で実行される命令が、流れ図またはブロック図あるいはその両方の１つもしくは複数のブロックにおいて指定された機能／作用を実装するためのプロセスを提供することができる。
【００９４】
図面における流れ図およびブロック図は、本発明のさまざまな実施形態に従ったシステム、方法、およびコンピュータ・プログラム製品の考え得る実装形態のアーキテクチャ、機能性、および動作を図示している。この点において、流れ図またはブロック図の各ブロックは、指定された論理機能を実装するための１つまたは複数の実行可能な命令を含むモジュール、セグメント、またはコードの一部を表すことができる。いくつかの代替実装形態においては、ブロックに記された機能が、図面に記された順序を外れて行われてもよいことにもまた留意されたい。たとえば、関与する機能性およびアルゴリズムの最適化に応じて、連続して示される２つのブロックは、実際には、実質的に同時に実行されてもよく、またはブロックは時に逆の順序で実行されてもよい。ブロック図または流れ図あるいはその両方の各ブロック、およびブロック図または流れ図あるいはその両方のブロックの組み合わせは、指定された機能もしくは作用を実施する特殊用途ハードウェア・ベースのシステムによって、または特殊用途ハードウェアとコンピュータ命令との組み合わせによって実装されてよいこともまた留意されたい。
【００９５】
本発明を、特定の実施形態を参照して説明してきたが、当業者は、本発明の範囲から逸脱せずに、さまざまな変更形態が行われ、均等形態が代用されてもよいことを理解するであろう。加えて、その範囲から逸脱せずに、特定の状況を本発明の教示に適応させるように、多くの修正形態が行われてもよい。したがって、本発明は、開示された特定の実施形態に限定されることは意図されず、本発明は、添付の特許請求の範囲内に入るすべての実施形態を含むことになることが意図される。たとえば、ＣＳＭＡプロトコルに対する多くの修正形態、たとえば、搬送波感知多重アクセス衝突検出方式（ＣＳＭＡ／ＣＤ）、または搬送波感知多重アクセス衝突回避方式（ＣＳＭＡ／ＣＡ）などが、実施形態において、要求するノードに応答をユニキャストするために使用されてもよい。いくつかの場所では、アプリケーションに応じて、適切な場合には、ユニキャストするプロセスをブロードキャストするプロセスに、およびそれらを相互に置き換えることができる。たとえば、返答するネイバ・ノードを処理すべきノードのグループに追加するステップ（ステップＳ１３）などのいくつかの典型的なＢＳのタスクが、ノードに委ねられてもよい。
【図１】
0006029120.tif 000002
【図２】
0006029120.tif 000003
【図３】
0006029120.tif 000004
【図４】
0006029120.tif 000005
【図５】
0006029120.tif 000006
【図６】
0006029120.tif 000007
【図７】
0006029120.tif 000008
【図８】
0006029120.tif 000009
【図９】
0006029120.tif 000010
【図１０】
0006029120.tif 000011