JP4124196B2 - ネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラム - Google Patents

Description

本発明は、実世界に関するさまざまな情報の取得並びに流通を行なうネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムに係り、特に、センサと演算機能と無線通信機能を備えた無数のセンサ・ノードを比較的広範な領域に分散して配置させることにより構成されるネットワーク上で、各センサが取得したデータを収集するネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムに関する。

さらに詳しくは、本発明は、移動機能を備えた複数のセンサ・ノードが自律分散的に動作してアドホックなネットワーク・トポロジを形成するネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムに係り、特に、移動機能を備えた各センサ・ノードが位置情報を利用せずに自律分散的にネットワーク・トポロジを形成するネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムに関する。

複数の通信端末間を通信回線経由で接続することで、ネットワークが形成される。例えば、コンピュータ同士を接続したコンピュータ・ネットワーク上では、情報の共有、流通、配信など情報資源の利用が活性化される。最近では、インターネットやブロードバンド・ネットワークの発達により、情報通信の利便性は格段に向上してきている。さらにＰＤＡ（Ｐｅｒｓｏｎａｌ Ｄｉｇｉｔａｌ Ａｓｓｉｓｔａｎｃｅ）や携帯電話機などのインターネット接続可能なモバイル機器の普及により、どこでも利用可能で、グローバルな空間からのアクセスが許容されるユビキタス・ネットワーク若しくはユビキタス・コンピューティングが注目されている。

他方、時々刻々と変わる環境情報の取得や、広域にわたる情報の同時把握など、実世界上の情報の取得や流通に関しては、技術的な課題が残されていると言われている。このため、実世界に関するさまざまな情報を扱う「センサ・ネットワーク」に関する研究が進められている。

センサ・ネットワークは、センサと演算機能と無線通信機能を備えた無数のセンサ・ノードを比較的広範な領域に分散して配置させることにより構成される。そして、形成されたネットワーク上では、各センサが取得したデータを収集することができる。各センサ・ノードは基本的には自律分散的に動作し、センサ・ネットワークはアドホックな通信システムである。あるノードで得られた情報は、例えばマルチホップ転送により遠方のノードへ伝送される。したがって、同じノード数で通信エリアがより大きくなるようにネットワーク・トポロジを形成することができれば効率的である。

また、センサ・ノードが移動機能を備えることにより、複数のセンサ・ノードが自律分散的にネットワーク・トポロジを形成し、センシング情報をユーザに提供するような世界を構築することができる。例えば、カリフォルニア大学バークレー校のＣＯＴＳ−ＢＯＴＳ（例えば、非特許文献１を参照のこと）などは、車輪型のロボットと一体となってセンサ・ノードが構成されている。

既に述べたように、同じノード数で通信エリアがより大きくなるようにネットワーク・トポロジを形成することができれば効率的である。したがって、移動機能を備えた複数のセンサ・ノードが自律的に動作するセンサ・ネットワーク・システムでは、動的なネットワーク・トポロジの生成技術が重要な課題の１つとなる。

センサ・ネットワークを構築する場合、一般には、以下の手順に従って初期設定が行なわれる。

（１）ノードの設置
（２）ノード間での時刻同期
（３）各ノードの位置測定

ここでポイントとなるのは、センサ・ノードを設置した後に位置測定が行なわれるという点である。

ユビキタス・コンピューティングの分野では特殊なインフラストラクチャを必要とする位置測定技術があり、これらは“Ｒａｎｇｅ Ｂａｓｅｄ”と呼ばれる。これに対し、センサ・ネットワークで利用される位置測定技術は、これらとは相違し、“Ｒａｎｇｅ Ｆｒｅｅ”と呼ばれる。

Ｒａｎｇｅ Ｆｒｅｅの位置測定技術では、位置情報を知る一部のセンサ・ノードがランドマークとして作用することを想定し、そのランドマークからの距離を各ノードが測定する。例えば、ランドマークとなるノードは、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）のような位置検出装置を搭載している。また、その他のノードは、ホップ数や電波強度などを利用してランドマークまでの距離を算出し、さらに高く測量を利用して自らの位置を計算することができる。ここで、位置測定を行なう際には、ノードの設置が完了していることが前提となる、という点に留意されたい。

センサ・ネットワーク・システムでは、同じノード数で通信エリアがより大きくなるようにネットワーク・トポロジを形成することができれば効率的である。ここで言う「トポロジ」とは、マルチホップなどの通信手順によりすべてのノードが接続可能となる状態、すなわちシングル・コネクテッド・ネットワークを表している。

センサ・ノード間で接続性を保証しながらネットワーク・トポロジを構成する方法は、各センサ・ノードが移動しないことを想定した静的なトポロジ構成方法と、移動機能を備えているセンサ・ノードの移動を利用した動的なトポロジ構成方法に大別することができる。

前者の静的なトポロジ構成方法として、センサ・ノードを高密度にばら撒く方法や、人間が設置する方法などが挙げられる。

例えば、山や森など、人が簡単に入れない場所を環境測定する場合に、対象とするフィールドにセンサを散布し（安価で微小な数万個のセンサ・ノードを飛行機で上空からばら撒く）、各センサをネットワークのノードとして用い、センシング・データを取り扱う（図１４を参照のこと）。個々のノードでセンシングしたデータは、ノード同士で形成されたアドホック・ネットワークを介してマルチホップ伝送により抽出される。

この種の究極的なセンサ・ネットワークとして、カリフォルニア大学バークレー校から“ＳｍａｒｔＤｕｓｔ”が提案されている（例えば、非特許文献２を参照のこと）。ＳｍａｒｔＤｕｓｔに端を発する流れから、現在の多くのセンサ・ネットワークの研究では、センサ・ノードの密度が高い環境を想定している。ノード同士が十分に近接している環境では、ノード間の接続性は考慮しなくてもよいことになる。

しかしながら、実際に利用されているセンサ・ネットワークのアプリケーションの多くは、このような形態ではなく、ノードが低密度に散在するネットワークである。また、高密度にばら撒くという手法を実社会で実現するにはさまざまな制約が考えられる。例えば、ビルの中や家の中には上空からばら撒くことはできない。また、センサ・ノードを人為的にばら撒く場合には、偏りなく均一にばら撒くことは困難である。

また、現在の環境モニタリング型のセンサ・ネットワークの多くは、人間によってセンサ・ノードが設置されている。この場合、接続性を確認しながら設置しなければならず、作業負担が過大である。数個のセンサ・ノードならばこの手法は最適かもしれないが、センサ・ノードの総数が数百、数千あるいはそれ以上という規模になると人間が設置することは困難である。勿論、山や森など、人が簡単に入れない場所を対象フィールドとすることは現実的でない。また、トポロジの効率を上げるためには、フィールド全体のトポロジを把握しながら設置していかなくてはならず、これも困難な作業である。

なお、静的にトポロジを構成するセンサ・ネットワーク・システム若しくはデータ収集システムに関し、幾つかの特許出願がなされている（例えば、特許文献１並びに特許文献２を参照のこと）。

一方、各ノードが移動手段を備え、動的にネットワーク・トポロジを構成する方法は、ネットワークの分野においては未だあまり注目されていないが、ロボティクスの分野では幾つかの先行研究が散見される。

動的にネットワーク・トポロジを構成する技術の多くは、センシング領域と比較して無線電波領域が十分大きいことを想定しており、センシング領域の最適化を目指している。接続性は、遠隔操作するためには移動ノードのいわば命綱であるため、センシング領域と同様に接続領域も考慮したトポロジ形成方法が必要となる。例えば、環境情報などのセンシングでは、１００％の領域をセンシングするよりも、ある程度高域な範囲でのサンプルを取得したい場合がある。

また、密度の高いセンサ・ネットワークにおいて、接続性とセンシング領域を考慮しながら、どのノードをアクティブにするかといった研究がある（例えば、非特許文献３〜５を参照のこと）。これらの手法では、各ノードが自分の位置情報をあらかじめ知っていることを想定している。前述したように、センサ・ネットワークの位置測定技術の多くは、既にトポロジが生成された状態で利用されることを前提としているため相性がよくないと言える。さらに、このような位置情報を前提とした手法で、接続性のあるトポロジを作成することは非常に困難である。何故なら、実社会では、高い精度での位置情報を取得するには、ＧＰＳなどの高価なシステムが必要となるからである。また、無線電波の障害となる物体も多く、さらにこれらの仕組みは２次元空間での理想環境を想定しており、実際の３次元空間でのトポロジ作成はさらに困難となる。

以上を要言すれば、静的にトポロジを構成するセンサ・ネットワーク・システムでは、センサ・ノードの設置という観点から問題がある。一方、動的にトポロジを構成する場合、センサ・ノードが移動機能を備えることによりノードの設置の問題からは解放されるが、位置測定の工程において課題がある。各センサ・ノードがＧＰＳなどの位置情報の取得装置を搭載すればよいが、高価なシステムとなってしまう。そこで、本発明者らは、移動機能を備えた各センサ・ノードが位置情報を前提としないで動的にネットワーク・トポロジを構成する方法が好ましいと思料する次第である。

特開２００４−２６０５２６号公報 特開２００３−４４９７４号公報 http://www-bsac.eecs.berkeley.edu/projects/cotsbots/ http://www-bsac.eecs.berkeley.edu/~warneke/SmartDust/index.html Ｃ．−Ｆ．Ｈｕａｎｇ ａｎｄ Ｙ．−Ｃ．Ｔｓｅｎｇ．"Ｔｈｅ Ｃｏｖｅｒａｇｅ Ｐｒｏｂｌｅｍ ｉｎ ａ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋ．"（Ｉｎ Ｓｅｃｏｎｄ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ（ＷＳＮＡ），Ｓｅｐｔｅｍｂｅｒ ２００３） Ｓｈａｋｋｏｔｔａｒｉ Ｓ， Ｒ． Ｓｒｉｋａｎｔ， ａｎｄ Ｎ．Ｓｈｒｏｆｆ．"Ｕｎｒｅｌｉａｂｌｅ Ｓｅｎｓｏｒ Ｇｒｉｄｓ： Ｃｏｖｅｒａｇｅ， Ｃｏｎｎｅｃｔｉｖｉｔｙ ａｎｄ Ｄｉａｍｅｔｅｒ．"（Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｉｎｆｏｃｏｍ，ＭＡｒｃｈ ２００３） Ｘ．Ｗａｎｇ， Ｇ．Ｘｉｎｇ， Ｚ．Ｚｈａｎｇ， Ｃ．Ｌｕ， Ｒ．Ｐｌｅｓｓ， ａｎｄ Ｃ．Ｇｉｌｌ．"Ｉｎｔｅｇｒａｔｅｄ Ｃｏｖｅｒａｇｅ ａｎｄ Ｃｏｎｎｅｃｔｉｖｉｔｙ Ｃｏｎｆｉｇｕｒａｔｉｏｎ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ．"（Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｎｅｔｗｏｒｋｅｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ（ＳｅｎＳｙｓ，０３），Ｎｏｖｅｎｂｅｒ ２００３）

本発明の目的は、センサと演算機能と無線通信機能を備えた無数のセンサ・ノードを比較的広範な領域に分散して配置させることにより構成されるネットワーク上で、各センサが取得したデータを好適に収集することができる、優れたネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムを提供することにある。

本発明のさらなる目的は、移動機能を備えた複数のセンサ・ノードが自律分散的に動作してアドホックなネットワーク・トポロジを好適に形成することができる、優れたネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムを提供することにある。

本発明のさらなる目的は、移動機能を備えた各センサ・ノードが位置情報を利用せずに自律分散的にネットワーク・トポロジを形成することができる、優れたネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムを提供することにある。

本発明のさらなる目的は、移動機能を備えた各センサ・ノードが自律分散的に動作し、通信エリアがより大きくなるように効率的にネットワーク・トポロジを形成することができる、優れたネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムを提供することにある。

本発明は、上記課題を参酌してなされたものであり、その第１の側面は、無線通信機能と移動機能を備えた複数のノードの自律分散的な動作によりネットワーク・トポロジを構築するネットワーク・システムであって、各ノードは、移動機能を用いて移動しながら近隣ノードに関する接続情報を探索する第１及び第２の状態と、移動機能を用いた移動を停止した第３の状態を持っている。前記第１の状態では第１の条件に合致したことに応じて前記第３の状態に遷移するとともに、前記第２の状態では前記第１の条件とは異なる第２の条件に合致したことに応じて前記第３の状態に遷移するネットワーク・システムである。このようなネットワーク・システムでは、各ノードが前記第１及び第２の状態の間で動的に切り替わりながら、第３の状態へ遷移していくことでネットワーク・トポロジを形成していくことができる。

但し、ここで言う「システム」とは、複数の装置（又は特定の機能を実現する機能モジュール）が論理的に集合した物のことを言い、各装置や機能モジュールが単一の筐体内にあるか否かは特に問わない（以下、同様）。

本発明で言う前記第１の状態は、ノードが移動しながら、ネットワーク・トポロジを拡張する近隣ノードとの接続関係が得られる位置を探索するＥｘｐａｎｄ状態のことである。Ｅｘｐａｎｄ状態のノードは、１つのＳｔａｙ状態にある近隣ノードと接続可能となったときに、Ｓｔａｙ状態に遷移する。

また、前記第２の状態は、ノードが移動しながら、独立したネットワーク・トポロジ間を接続する近隣ノードとの接続関係が得られる位置を探索するＢｒｉｄｇｅ状態である。Ｂｒｉｄｇｅ状態のノードは、お互いに近隣ノードの関係ではなく且つ同一の近隣ノードを保有しない独立した関係にある２以上のノードと接続可能となったときに、Ｓｔａｙ状態に遷移する。

そして、前記第３の状態は、ノードが現在位置に停止し、最終的にネットワーク・トポロジの構成要素となったＳｔａｙ状態である、

ここで、ネットワーク・トポロジの初期時はすべてのノードはＥｘｐａｎｄ状態である。そして、ノード密度が所定値を上回ったときに所定の確率でＢｒｉｄｇｅ状態のノードを発生させるようにする。

Ｂｒｉｄｇｅ状態のノードはトポロジの作成を開始することが可能であるが、離れた場所でＢｒｉｄｇｅノードが何台も存在した場合には、途切れ途切れのネットワークが最終的にできてしまう可能性がある。そこで、ノード密度がある程度濃い場所でＢｒｉｄｇｅノードを発生する仕組みを導入することにより、１つのネットワークにすべてのノードが接続される確率を高めることができる。

Ｅｘｐａｎｄ状態とＢｒｉｄｇｅ状態間の状態遷移は可逆的に行なわれる。すなわち、各ノードは、自らの役割をトポロジの拡張とトポロジの接続の間で動的に切り替えるようになっている。そして、これらの状態の各ノードは、例えばランダム・ウォークにより移動しながら、マルチホップなどの通信手順によりすべてのノードが接続可能となる状態、すなわちシングル・コネクテッド・ネットワークを形成するために適当な位置を探索し、最終的にＳｔａｙ状態となる。

現在、実世界に関すさまざまな情報の収集を行なうために、センサ・ネットワーク・システムが開発されている。センサ・ネットワークは、センサと演算機能と無線通信機能を備えた無数のセンサ・ノードを比較的広範な領域に分散して配置させることにより構成される。

センサ・ネットワークにおけるトポロジの構成方法として、静的な構成方法と、各ノードの移動機能を利用した動的な構成方法が挙げられる。動的なトポロジ構成方法は、センサ・ノードの設置に関する問題を解消することができるが、位置測定の工程において課題がある。

これに対し、本発明を適用して構成されたセンサ・ネットワーク・システムの場合、位置情報を利用しない各センサ・ノードが、移動しながら電波到達距離内にいる近隣ノードとの情報交換を行ない、自らの役割をトポロジの拡張とトポロジの接続の間で動的に切り替えるようになっている。すなわち、移動機能を備えた各センサ・ノードの自律的な移動により、トポロジが拡張していくことになるので、位置情報を前提としないで動的にネットワーク・トポロジを構成することができる。

各状態のノードは、ネットワーク・トポロジを形成していく過程で、近隣ノードとの接続関係を認識する必要がある。そこで、各ノードは、自分の状態と、自分にとっての近隣ノードのリストを含んだ第１の信号すなわちＨＥＬＬＯメッセージを所定の周期毎に送信するようにしてもよい。このような場合、近隣ノードからのＨＥＬＬＯメッセージを受信処理することにより、接続可能な近隣ノードを認識し、あるいはノード密度を求めることができる。

このように、本発明に係るセンサ・ネットワーク・システムは、センサ・ノード間の接続性を保ちつつ、ネットワーク・トポロジの最大化を目指すものである。ところが、強い電波強度において２台のＥｘｐａｎｄ状態のノードがＳｔａｙ状態に遷移し、トポロジ領域の最大化という観点からは効率的でない状況や、逆に弱い電波強度においてノートがＳｔａｙ状態に遷移し、接続性が妥当でない状況など、ネットワーク・トポロジを形成するための基本的なメカニズムにおいて性能劣化が起こり得る。

これら２つの問題点を解決するために、本発明では電波強度を利用した改良方法を適用する。すなわち、各ノードは、無線通信機能部において適当な電波強度が得られる近隣ノードとの接続関係を得るようにする。具体的には、電波強度が所定値を超える近隣ノード、並びに電波強度が所定値を下回る近隣ノードは、いずれも電波強度が適当でないとして、これらとの接続関係を避けるようにする。

また、本発明の第２の側面は、センサと無線通信機能と移動機能を備えた無線通信装置がセンサ・ネットワークにおけるセンサ・ノードとして動作するための処理をコンピュータ・システム上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、
前記無線通信機能によって得られる近隣ノードに関する接続情報に基づいて、前記移動機能を用いて移動しながら近隣ノードに関する接続情報を探索する第１及び第２の状態の間で動的に切り替えるステップと、
前記第１の状態において、第１の条件に合致したことに応じて前記移動機能部を用いた移動を停止した第３の状態に遷移するステップと、
前記第２の状態において、前記第１の条件とは異なる第２の条件に合致したことに応じて前記第３の状態に遷移するステップと、
を具備することを特徴とするコンピュータ・プログラムである。

本発明の第２の側面に係るコンピュータ・プログラムは、コンピュータ・システム上で所定の処理を実現するようにコンピュータ可読形式で記述されたコンピュータ・プログラムを定義したものである。換言すれば、本発明の第２の側面に係るコンピュータ・プログラムをコンピュータ・システムにインストールすることによってコンピュータ・システム上では協働的作用が発揮され、センサ・ネットワークを構築するセンサ・ノードとして動作する。このようなセンサ・ノードを複数起動して無線ネットワークを構築することによって、本発明の第１の側面に係るセンサ・ネットワーク・システムと同様の作用効果を得ることができる。

本発明によれば、センサと演算機能と無線通信機能を備えた無数のセンサ・ノードを比較的広範な領域に分散して配置させることにより構成されるネットワーク上で、各センサが取得したデータを好適に収集することができる、優れたネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムを提供することができる。

また、本発明によれば、移動機能を備えた複数のセンサ・ノードが自律分散的に動作してアドホックなネットワーク・トポロジを好適に形成することができる、優れたネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムを提供することができる。

また、本発明によれば、移動機能を備えた各センサ・ノードが位置情報を利用せずに自律分散的にネットワーク・トポロジを形成することができる、優れたネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムを提供することができる。

また、本発明によれば、移動機能を備えた各センサ・ノードが自律分散的に動作することにより、通信エリアがより大きくなるように効率的にネットワーク・トポロジを形成することができる、優れたネットワーク・システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラムを提供することができる。

本発明に係るセンサ・ネットワーク・システムは、移動機能を備えた複数のセンサ・ノードにより構成されるが、同じノード数で通信エリアがより大きくなるようにネットワーク・トポロジを形成することができれば効率的であるということを考慮し、位置情報を利用しない各センサ・ノードは、移動しながら電波到達距離内にいる近隣ノードとの情報交換を行ない、自らの役割をトポロジの拡張とトポロジの接続の間で動的に切り替える。これによって、すなわち、移動機能を備えた各センサ・ノードの自律的な移動により、トポロジが拡張していくことになる。

本発明のさらに他の目的、特徴や利点は、後述する本発明の実施形態や添付する図面に基づくより詳細な説明によって明らかになるであろう。

以下、図面を参照しながら本発明の実施形態について詳解する。

本発明は、センサと演算機能と無線通信機能を備えた無数のセンサ・ノードを比較的広範な領域に分散して配置させることにより構成されるネットワーク上で、各センサが取得したデータを収集するセンサ・ネットワーク・システムに関するが、具体的には、移動機能を備えた各センサ・ノードが位置情報を前提としないで動的にネットワーク・トポロジを構成するものである。

図１には、本発明に係るセンサ・ネットワーク上において、センサ・ノードとして動作することができる装置の構成を模式的に示している。図示のセンサ・ノード１０は、センサ１１と、演算処理部１２と、無線通信機能部１３と、移動機能部１４を備えている。

センサ１１は、温度センサやその他各種の環境情報を採取するための計測機器で構成される。

演算処理部１２は、プロセッサやメモリで構成され、プロセッサが所定のプログラム・コードを実行することにより、当該装置全体の動作を統括的にコントロールするようになっている。

無線通信機能部１３は、ＩＥＥＥ８０２．１１やＢｌｕｅｔｏｏｔｈ通信、若しくはその他の任意の通信プロトコルに従って他のセンサ・ノードとの間で無線通信を行なう。本実施形態では、無線通信機能部１３は自律分散的な動作によりアドホックにネットワークを構築するが、勿論、特定のセンサ・ノードを制御局若しくはアクセス・ポイントに設定してネットワークを構築するという応用例も考えられる。また、移動機能部１４における移動作業を干渉しない範囲であれば、無線通信だけでなく有線通信を導入することも可能である。

移動機能部１４は、例えば車輪や可動脚などの機構により構成される。演算処理部１２に従って、移動機能部１４はランダム・ウォークなどの移動作業を実行する。なお、移動作業中における衝突回避や姿勢安定制御などの機能を備えていてもよいが、本発明の要旨には直接関連しないので、ここでは説明を省略する。

図２には、センサ・ノードにおける動作状態の遷移を示している。同図に示すように、各センサ・ノードには、“Ｅｘｐａｎｄ”、“Ｂｒｉｄｇｅ”、“Ｓｔａｙ”という３種類の状態が定義されている。位置情報を利用しない各センサ・ノードは、移動しながら電波到達距離内にいる近隣ノードとの情報交換を行ない、自らの役割をトポロジの拡張とトポロジの接続の間で動的に切り替える。これによって、すなわち、移動機能を備えた各センサ・ノードの自律的な移動により、トポロジが拡張していくことになる。

ＥｘｐａｎｄとＢｒｉｄｇｅ状態のノードは、ともに移動機能を用いて移動している状態である。移動の方法は特に限定されないが、本実施形態では移動方向を任意に決定するランダム・ウォークを行なうものとする。Ｅｘｐａｎｄ状態のノードは、コアとなるトポロジを拡張する役目を担っている。また、Ｂｒｉｄｇｅ状態のノードは、コアとなるトポロジを形成する役目を担っている。ノードが高密度で存在する領域では、例えば一定の割合でＥｘｐａｎｄ及びＢｒｉｄｇｅ状態のノードに振り分けられ、ノード間の協調的動作によりトポロジの拡張とトポロジの接続が行なわれる。

これに対し、Ｓｔａｙ状態のノードは、ネットワーク・トポロジの構成要素の一部となった状態であり、停止している。

すべてのノードは、Ｅｘｐａｎｄ状態で動作を開始する。そして、ノードが高密度で存在する領域では、例えば一定の割合でＥｘｐａｎｄ及びＢｒｉｄｇｅ状態のノードに振り分けられ、ノード間の協調的動作によりトポロジの拡張とトポロジの接続が行なわれる。そして、最終的には各ノードがＳｔａｙ状態に遷移していくことで、ネットワーク・トポロジが徐々に形成されていく。

また、各ノードは、ＨＥＬＬＯメッセージと呼ばれる一種の報知信号を送信することで、近隣ノードとの情報交換を行なう。例えば、ノードはラウンド・タイマを起動して、定期的にＨＥＬＬＯメッセージの交換を行なう。図３には、ＨＥＬＬＯメッセージの構成例を示している。図示の例では、ＨＥＬＬＯメッセージには、自ノードを識別するノードＩＤと、自分の現在の状態を表すＳｔａｔｅと、隣接する（ＨＥＬＬＯメッセージを受信することができる）ノードのノードＩＤのリストからなる近隣ノード情報が記載されている。各ノードは、ＨＥＬＬＯメッセージにより近隣のノードとの情報交換を行なうことができる。

各ノードは、近隣ノードから受信したＨＥＬＬＯメッセージに記載されている情報を利用して、自ノードの状態を遷移すべきか否かの判断を行なう。具体的には、各ノードは、ＨＥＬＬＯメッセージにより、現在自分が置かれている領域でのノードの密度を算出することができる。そして、ノードが高密度で存在する領域では、例えば一定の割合でＥｘｐａｎｄ及びＢｒｉｄｇｅ状態のノードに振り分けられ、ノード間の協調的動作によりトポロジの拡張とトポロジの接続が行なわれる。

Ｅｘｐａｎｄ状態のノードはトポロジを拡張する役目を担い、Ｂｒｉｄｇｅ状態のノードはトポロジを形成する役目を担う。そして、Ｅｘｐａｎｄ並びにＢｒｉｄｇｅの各状態のノードは、所定の事象が発生したことに応答して、Ｓｔａｙ状態へと遷移し、ランダム・ウォークを停止して、ネットワーク・トポロジに組み込まれていく。例えば、Ｅｘｐａｎｄ状態のノードは、近隣に存在する単一のＳｔａｙノードのみと接続されるようになったら、Ｓｔａｙに遷移し、トポロジの構成要素となる。また、Ｂｒｉｄｇｅ状態のノードは、お互いに近隣ノードの関係ではなく、さらに同一の近隣ノードを保有していない（若しくは、お互いに隠れ端末を持つ）近隣ノードとともにＳｔａｙ状態に遷移し、トポロジの構成要素となる。

このようにして、各ノードは自らの役割をトポロジの拡張とトポロジの接続の間で動的に切り替えていき、最終的にはすべてのノードがＳｔａｙ状態に遷移していくことで、ネットワーク・トポロジが形成される。

以下では、センサ・ノードにおける状態遷移について説明する。

ＥｘｐａｎｄからＳｔａｙへの状態遷移：
Ｅｘｐａｎｄ状態のノードは、Ｓｔａｙ状態のノードと接続し、トポロジを拡張する役目を担っている。Ｅｘｐａｎｄ状態からＳｔａｙ状態に遷移する条件は、近隣に存在する単一のＳｔａｙノードのみと接続されることである。具体的には、１ラウンド（すなわちＨＥＬＬＯメッセージを送信する周期）において１つのＳｔａｙ状態からＨＥＬＬＯメッセージを受信することである。

図４には、Ｅｘｐａｎｄ状態のノードがＳｔａｙ状態へ遷移する様子を図解している。図示の例では、あるＳｔａｙ状態のノードが、自ノードの接続可能範囲で、ラウンド毎にＨＥＬＬＯメッセージを送信している。一方、Ｅｘｐａｎｄ状態のノードは、ランダム・ウォークにより任意の方向へ移動しているが、この移動の過程でＳｔａｙ状態のノードの接続可能範囲に突入し、ＨＥＬＬＯメッセージを受信したとする。Ｅｘｐａｎｄ状態のノードは、このＨＥＬＬＯメッセージの内容を解析し、この近接ノードのノードＩＤ並びにＳｔａｙ状態であることを検出する。そして、１ラウンドでこのＳｔａｙノードのみからしかＨＥＬＬＯメッセージを受信しなかったならば、Ｅｘｐａｎｄ状態のノードは、ランダム・ウォークを停止してＳｔａｙ状態へ遷移し、自らもネットワーク・トポロジの構成要素となる。

Ｅｘｐａｎｄ状態からＳｔａｙ状態に遷移する際、ノードは一度移動を停止してＦｒｅｅｚｅメッセージを、ＨＥＬＬＯメッセージを送信してきたＳｔａｙ状態のノードに送信する。これに対し、Ｆｒｅｅｚｅメッセージを受け取ったＳｔａｙ状態のノードは、Ｆｒｅｅｚｅ−ＡＣＫメッセージを送信しなければならない。そして、Ｅｘｐａｎｄ状態のノードは、Ｆｒｅｅｚｅ−ＡＣＫメッセージを受け取った時点で、Ｓｔａｙ状態に遷移する。状態遷移時の動作手順の詳細については、後述に譲る。

ＢｒｉｄｇｅからＳｔａｙへの状態遷移：
Ｂｒｉｄｇｅ状態のノードは、２台以上の独立した関係のノードからＨＥＬＬＯメッセージを受信することによりＳｔａｙ状態に遷移する。

ここで言う「独立した関係のノード」とは、お互いに近隣ノードの関係ではなく、さらに同一の近隣ノードを保有していないことを示す。すなわち、他のノードを経由して２ホップ以内に接続されていないノードである。このようなノード間の接続関係の判断は、近隣ノードが送信するＨＥＬＬＯメッセージに含まれている近隣ノードのリストに基づいて判断することができる。

図５には、Ｂｒｉｄｇｅ状態のノードがＳｔａｙ状態へ遷移する様子を図解している。図示の例では、独立した関係となる２つのノードＡ及びＢ（各ノードＡ及びＢの状態は問わない）がそれぞれラウンド毎にＨＥＬＬＯメッセージを送信している。一方、Ｂｒｉｄｇｅ状態にあるノードＣは、ランダム・ウォークにより任意の方向へ移動しているが、この移動の過程で、独立した関係となる２つのノードＡ及びＢの双方から接続可能な範囲に突入し、両ノードＡ及びＢからＨＥＬＬＯメッセージを受信したとする。そして、Ｂｒｉｄｇｅ状態のノードＣは、これらのＨＥＬＬＯメッセージを解析し、各近接ノードＡ及びＢのノードＩＤ並びにそれぞれの近隣ノード・リストを取得して、これらがお互いに近接ノードの関係ではなく、さらに同一の近隣ノードを保有していないこと、すなわち独立した関係にあることを検出する。同図からも分かるように、独立した関係のノードＡ及びＢは、Ｂｒｉｄｇｅ状態のノードＣを架け橋とした隠れ端末の関係にある。そして、Ｂｒｉｄｇｅ状態のノードＣは、自らランダム・ウォークを停止し、これら独立した関係の近隣ノードＡ及びＢとともにＳｔａｙ状態へ遷移し、ネットワーク・トポロジの構成要素となる。

ノードの状態は問わず、独立した関係の２以上のノードからＨＥＬＬＯメッセージを受け取った場合、Ｂｒｉｄｇｅノードは、自ら停止するとともに、該当する各近隣ノードにＦｒｅｅｚｅメッセージを送信する。２台以上のノードからのＦｒｅｅｚｅ−ＡＣＫメッセージを受信した場合、Ｂｒｉｄｇｅ状態のノードはＳｔａｙ状態に遷移する。また、Ｓｔａｙ状態以外の状態のときに、Ｆｒｅｅｚｅメッセージを受信したノードはＳｔａｙ状態に遷移する。状態遷移時の動作手順の詳細については、後述に譲る。

ここで、Ｓｔａｙ以外の状態の各ノードは移動しているため、Ｆｒｅｅｚｅメッセージの送信に対しＦｒｅｅｚｅ−ＡＣＫメッセージが必ず戻ってくるとは限らない。１台のノードからしかＦｒｅｅｚｅ−ＡＣＫメッセージが戻ってこなければ（あるいは，いずれのノードからもＦｒｅｅｚｅ−ＡＣＫメッセージが戻ってこなければ）、図５右側に示すような２ホップの接続関係が得られていないことを意味している。そこで、Ｆｒｅｅｚｅ−ＡＣＫメッセージが戻ってこない場合には、Ｂｒｉｄｇｅノードは、続いてＦｒｅｅｚｅ−Ｃａｎｃｅｌメッセージを送信することにより、ＦｒｅｅｚｅメッセージでＳｔａｙ状態に遷移させてしまったノードの処理を取り消すとともに、自らは元のＢｒｉｄｇｅ状態に戻り、ランダム・ウォーク処理を継続する。また、Ｆｒｅｅｚｅ−Ｃａｎｃｅｌメッセージを受信したノードは、Ｓｔａｙ状態への遷移を取り消して、元の状態（Ｅｘｐａｎｄ又はＢｒｉｄｇｅ）に戻る。

ＥｘｐａｎｄとＢｒｉｄｇｅの相互状態遷移：
センサ・ネットワークの初期時には、すべてのノードはＥｘｐａｎｄ状態である。Ｅｘｐａｎｄ状態のノードはＳｔａｙ状態のノードが存在しないとＳｔａｙ状態に遷移しないため、永久に動き回ってしまう。このような状況を回避するため、ある条件によってＥｘｐａｎｄ状態からＢｒｉｄｇｅ状態への遷移と、その逆の遷移が起こるようにしている。

Ｂｒｉｄｇｅ状態のノードはトポロジの作成を開始することが可能である。このため、Ｂｒｉｄｇｅ状態のノードばかりでは、離れた場所でＢｒｉｄｇｅノードが何台も存在した場合には、途切れ途切れのネットワークが最終的にできてしまう可能性がある。そこで、本実施形態では、ノード密度がある程度濃い場所でＢｒｉｄｇｅノードを発生する仕組みを導入することにより、１つのネットワークにすべてのノードが接続される確率、すなわちシングル・コネクション・ネットワークが形成される確率を高めている。

具体的には、各ノードは、近隣ノードから受信したＨＥＬＬＯメッセージに記載されている情報を利用して、近隣ノードの数を計算する。そして、この数に対し加重平均をとった値すなわちノード密度を保持している。この値が一定値を上回る場合、すなわち連続してノード密度が高い場所を移動しているノードは、ある確率でＢｒｉｄｇｅ状態に遷移する。ノード密度を算出し、この計算結果に基づいてノードの状態をＥｘｐａｎｄ状態とＢｒｉｄｇｅ状態に動的に切り替えるための処理手順を、以下に擬似プログラム・コードの形式で示している。但し、ｎ（ｔ）は、ＨＥＬＬＯメッセージを送信するｔ回目のラウンドにおける近隣ノードの数である。また、ｄｅｎｓ（ｔ）は、ラウンドｔにおけるノード密度であり、直前のノード密度と現在の近隣ノード数に基づいて算出される。例えば、ｄｅｎｓ（ｔ）＝ βｄｅｎｓ（ｔ−１）＋（１−β）ｎ（ｔ）というノード密度の計算式が適用される（但し、０＜β＜１でありその推奨値は０．８である）。

ρ = random() // 0 <ρ< 1
if (dens(t) > K) && (ρ < 1/n(t) ) { // K: static value, recom. 4 Set state to "Bridge"
} else {
Set state to "Expand"
}

図６には、ノードがＨＥＬＬＯメッセージの送信と状態遷移を行なうための処理手順をフローチャートの形式で示している。但し、各ノードは、グローバル情報並びに近隣ノード毎の情報を管理するために、以下の変数を使用するものとする。

グローバル情報：
ｓｔａｔｅ //ノード状態
ｎｏｄｅ．ｎｅｉｇｈｂｏｒ［ｎ］ //近隣ノード・リスト
ｄｅｎｓ //平均近隣ノード数

近隣ノード毎の情報：
ｎｂｏｒ．ｓｔａｔｅ //ノード状態
ｎｂｏｒ．ｎｅｉｇｈｂｏｒ［ｎ］ //近隣ノード・リスト
ｎｂｏｒ．ｔｓｔａｍｐ //更新時刻

ラウンド・タイマが切れると（ステップＳ１）、まずＳＴＡＹ判定処理を行なう（ステップＳ２）。

ここで、センサ・ノードがＳＴＡＹ状態でなければ（ステップＳ３）、近隣ノードから受信したＨＥＬＬＯメッセージを集計して、現在のノード密度ｄｅｎｓ（ｔ）を求めるとともに（ステップＳ４）、乱数ρを生成する（ステップＳ５）。そして、ノード密度ｄｅｎｓ（ｔ）が所定値Ｋ以下の場合には（ステップＳ６）、当該センサ・ノードを初期時のＥｘｐａｎｄ状態のままとする（ステップＳ７）。

一方、ノード密度ｄｅｎｓ（ｔ）が所定値Ｋを上回るときには（ステップＳ６）、乱数ρを利用して得られる確率に基づいて、当該センサ・ノードをＥｘｐａｎｄ状態とＢｒｉｄｇｅ状態の間で動的に切り替える（ステップＳ８）。

そして、当該センサ・ノードの状態がＳｔａｙ状態のとき、あるいはステップＳ７又はＳ８により状態が決定された後、時間がラウンド・タイマ以上更新されていない近隣ノード・リストを消去する（ステップＳ９）。

次いで、自分のノードＩＤ、判定又は決定されたノード状態、並びに近隣ノード・リストを含んだＨＥＬＬＯメッセージを生成して送信バッファに一旦格納し（ステップＳ１０）、これをブロードキャスト送信する（ステップＳ１１）。

その後、ステップＳ１に復帰し、上記と同様の処理動作をラウンド・タイマが消滅する度に起動する。

図７には、図６中のステップＳ２において、Ｅｘｐａｎｄ状態のセンサ・ノードが状態判定を行なうための処理手順をフローチャートの形式で示している。既に述べたように、Ｅｘｐａｎｄ状態のセンサ・ノードは、１つのＳｔａｙ状態にある近隣ノードと接続可能となった条件下でＳｔａｙ状態に遷移する。

まず、近隣ノードから受信したＨＥＬＬＯメッセージを集計して、Ｓｔａｙ状態の近隣ノードの数を調べる（ステップＳ２１）。

ここで、Ｓｔａｙ状態にある近隣ノード数が１でない場合には（ステップＳ２２）、前処理に戻り（ステップＳ２８）、状態の変更を行なわない。

一方、Ｓｔａｙ状態にある近隣ノード数が１に等しい場合には（ステップＳ２２）、この近隣ノードに対し、Ｆｒｅｅｚｅメッセージを送信し（ステップＳ２３）、Ｆｒｅｅｚｅメッセージ・タイマを設定する（ステップＳ２４）。

ここで、Ｆｒｅｅｚｅメッセージ・タイマが消滅する前に、Ｆｒｅｅｚｅ−ＡＣＫメッセージを受信することができたならば（ステップＳ２５）、当該センサ・ノードの状態をＳｔａｙに設定する（ステップＳ２７）。

ところが、Ｆｒｅｅｚｅメッセージ・タイマが消滅するまでに、Ｆｒｅｅｚｅ−ＡＣＫメッセージを受信することができなかった場合には（ステップＳ２６）、前処理に戻り（ステップＳ２８）、状態の変更を行なわない。

また、図８には、図６中のステップＳ２において、Ｂｒｉｄｇｅ状態のセンサ・ノードが状態判定を行なうための処理手順をフローチャートの形式で示している。既に述べたように、Ｂｒｉｄｇｅ状態のセンサ・ノードは、お互いに近隣ノードの関係ではなく且つ同一の近隣ノードを保有しない独立した関係にある２以上のノードと接続可能となった条件下でＳｔａｙ状態に遷移する。

まず、同じノードを近隣ノード・リストに含まない近隣ノードの数、すなわち独立した関係にある近隣ノードの数を調べる（ステップＳ３１）。

ここで、独立した関係にある近隣ノードの数が２以上でない場合には、前処理に戻り（ステップＳ３９）、状態の変更を行なわない。

一方、独立した関係にある近隣ノードの数が２以上存在する場合には（ステップＳ３２）、これらの近隣ノードに対し、Ｆｒｅｅｚｅメッセージを送信し（ステップＳ３３）、Ｆｒｅｅｚｅメッセージ・タイマを設定する（ステップＳ３４）。

ここで、Ｆｒｅｅｚｅメッセージ・タイマが消滅する前に、Ｆｒｅｅｚｅメッセージを送ったすべての近隣ノードからＦｒｅｅｚｅ−ＡＣＫメッセージを受信することができたならば（ステップＳ３５）、当該センサ・ノードの状態をＳｔａｙに設定する（ステップＳ３７）。

ところが、Ｆｒｅｅｚｅメッセージ・タイマが消滅するまでに、Ｆｒｅｅｚｅメッセージを送信したすべての近隣ノードからＦｒｅｅｚｅ−ＡＣＫメッセージを受信することができなかった場合には（ステップＳ３６）、自らＳｔａｙ状態への遷移を取り消すとともに、Ｆｒｅｅｚｅ−Ｃａｎｃｅｌメッセージを再送信する（ステップＳ３８）。そして、前処理に戻り（ステップＳ３９）、状態の変更を行なわない。

図９には、ノードが近隣ノードからＨＥＬＬＯメッセージを受信したときの処理手順をフローチャートの形式で示している。

近隣ノードからのＨＥＬＬＯメッセージを受信すると（ステップＳ４１）、その内容を解析する。

そして、現在時刻を変数ｎｂｏｒ．ｔｓｔａｍｐに保存する（ステップＳ４２）。

次いで、当該ＨＥＬＬＯメッセージ内に記載されているノードＩＤを変数ｎｏｄｅ．ｎｅｉｇｈｂｏｒに保存する（ステップＳ４３）。

次いで、当該ＨＥＬＬＯメッセージ内に記載されている近隣ノード・リストを変数ｎｂｏｒ．ｎｅｉｇｈｂｏｒに保存する（ステップＳ４４）。

次いで、当該ＨＥＬＬＯメッセージ内に記載されているノード状態を変数ｎｂｏｒ．ｓｔａｔｅに保存する（ステップＳ４５）。

図１０には、Ｅｘｐａｎｄ及びＢｒｉｄｇｅ状態のノードが移動機能を用いてランダム・ウォークを行なうための処理手順をフローチャートの形式で示している。

センサ・ノードは、Ｅｘｐａｎｄ及びＢｒｉｄｇｅ状態では移動タイマを設定しており、これがタイムアウトすると（ステップＳ５１）、まず、移動方向をランダムに決定する（ステップＳ５２）。

そして、移動速度にランダム値を設定するとともに（ステップＳ５３）、移動タイマにランダム値を設定し（ステップＳ５４）、移動を開始する（ステップＳ５５）。

上述したように、本実施形態に係るセンサ・ネットワーク・システムでは、センサ・ノード間の接続性を保ちつつ、ネットワーク・トポロジの最大化を目指している。各ノードは、ネットワーク・トポロジを拡張する近隣ノードとの接続関係が得られる位置を探索するＥｘｐａｎｄ状態と、ノードが移動しながら独立したネットワーク・トポロジ間を接続する近隣ノードとの接続関係が得られる位置を探索するＢｒｉｄｇｅ状態とを可逆的に遷移する。そして、Ｅｘｐａｎｄ状態のノードは１つのＳｔａｙ状態にある近隣ノードと接続可能となったときにＳｔａｙ状態に遷移し、Ｂｒｉｄｇｅ状態のノードはお互いに近隣ノードの関係ではなく且つ同一の近隣ノードを保有しない独立した関係にある２以上のノードと接続可能となったときにＳｔａｙ状態に遷移する。

すなわち、各ノードは、自らの役割をトポロジの拡張とトポロジの接続の間で動的に切り替え、ランダム・ウォークにより移動しながら、マルチホップなどの通信手順によりすべてのノードが接続可能となる状態、すなわちシングル・コネクテッド・ネットワークを形成するために適当な位置を探索し、最終的にＳｔａｙ状態となる

ところが、このようなネットワーク・トポロジ形成の基本的なメカニズムにおいて、以下に示す２通りの性能劣化の状況が起こり得る。

例えば、図１１に示すように、２台のＥｘｐａｎｄ状態のノードがほぼ同じ方向に移動し、Ｓｔａｙ状態のノードと接続性がある場合、１つ目のＥｘｐａｎｄ状態のノードがＳｔａｙ状態のノードと接続するとすぐに２つ目のＥｘｐａｎｄ状態のノードが、Ｓｔａｙ状態に遷移したノードと接続してしまう。このため、２つのノードが近接してＳｔａｙ状態に遷移してしまう。このような状況は、トポロジ領域の最大化の観点からは、よい状況ではない。

また、図１２に示すように、２台のノードがＳｔａｙ状態に遷移する際に、電波到達距離ぎりぎりのところでＳｔａｙ状態に遷移する状況があり得る。無線電波は振動することがよく知られている。特に離れた距離の場合は、接続が途切れる可能性があるため、電波到達距離ぎりぎりでの接続はトポロジ構成においては避けることが妥当である。

これら２つの問題点を解決するために、本実施形態では電波強度を利用した改良方法を適用する。すなわち、各センサ・ノードは、無線通信機能部において適当な電波強度が得られる近隣ノードとの接続関係を得るようにする。具体的には、電波強度が所定値を超える近隣ノード、並びに電波強度が所定値を下回る近隣ノードとは、電波強度が適当ではないとして、接続関係を避けるようにする。

多くの無線通信デバイスでは、ピア・ツー・ピアノ通信においてお互いの電波強度を得ることが可能である。例えば、ＩＥＥＥ８０２．１１では、１００ミリ秒毎に送信するビーコン情報を用いて電波強度を知ることができる。

電波強度と距離の関係は、数理モデルとして提案されている（例えば、Ｐ．Ｂａｈｌ ａｎｄ Ｖ．Ｐａｄｍａｎａｂｈａｎ．“ＲＡＤＡＲ：Ａｎ Ｉｎ−Ｂｕｉｌｄｉｎｇ ＲＦ−Ｂａｓｅｄ Ｕｓｅｒ Ｌｏｃａｔｉｏｎ ａｎｄ Ｔｒａｃｋｉｎｇ Ｓｙｓｔｅｍ”（Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｉｎｆｏｃｏｍ，Ｍａｒｃｈ ２０００）を参照のこと）。本実施形態では、このモデルを利用して最適な電波強度での接続を実現する。

図１３には、電波強度と距離の関係からなる数理モデルに基づいて最適な電波強度を得る方法を図解している。図示の例では、最大電波強度の０．３〜０．５程度の電波強度が得られる近隣ノードを最適な接続関係（ＢＥＳＴ ｃｏｎｎｅｃｔｉｖｉｔｙ）が得るものとして扱うようにしている。例えば、Ｅｘｐａｎｄ状態のノードは、１つのＳｔａｙ状態にある近隣ノードとのみＢＥＳＴ ｃｏｎｎｅｃｔｉｖｉｔｙが得られるときに、Ｓｔａｙ状態に遷移する。また、Ｂｒｉｄｇｅ状態のノードは、お互いに近隣ノードの関係ではなく且つ同一の近隣ノードを保有しない独立した関係にある２台以上のノードとＢＥＳＴ ｃｏｎｎｅｃｔｉｖｉｔｙが得られるときに、Ｓｔａｙ状態に遷移する

一方、最大電波強度の０．５を超える電波強度（ｓｔｒｏｎｇ ｃｏｎｎｅｃｔｉｖｉｔｙ）が得られるときには、２つのノードが近接してＳｔａｙ状態に遷移してしまう可能性があるので、このようなノードとの接続関係は回避する。

また、最大電波強度の０．３を下回る電波強度（ｗｅａｋ ｃｏｎｎｅｃｔｉｖｉｔｙ）しか得られないときには、接続が途切れる可能性があるため、このようなノードとの接続関係は回避する。

以上、特定の実施形態を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施形態の修正や代用を成し得ることは自明である。

本明細書では、センサを備えた各通信ノードからなるセンサ・ネットワークを中心として説明してきたが本発明の要旨はこれに限定されるものではない。例えば、センサ情報を取り扱わない、移動手段付きの各通信ノードが自律的に動作するというアドホックなネットワーク・システムに対して本発明を適用することにより、トポロジ領域の拡大若しくは最適化を図ることができる。

また、本明細書では各センサ・ノードが自律分散的に動作するアドホックなネットワークを例に挙げて説明しているが、勿論、特定のセンサ・ノードを制御局若しくはアクセス・ポイントに設定してネットワークを構築するという応用例も考えられる。

要するに、例示という形態で本発明を開示してきたのであり、本明細書の記載内容を限定的に解釈するべきではない。本発明の要旨を判断するためには、特許請求の範囲を参酌すべきである。

図１は、本発明に係るセンサ・ネットワーク上において、センサ・ノードとして動作することができる装置の構成を模式的に示した図である。 図２は、センサ・ノードにおける動作状態の遷移を示した図である。 図３は、ＨＥＬＬＯメッセージの構成例を示した図である。 図４は、Ｅｘｐａｎｄ状態のノードがＳｔａｙ状態へ遷移する様子を示した図である。 図５は、Ｂｒｉｄｇｅ状態のノードがＳｔａｙ状態へ遷移する様子を示した図である。 図６は、ノードがＨＥＬＬＯメッセージの送信と状態遷移を行なうための処理手順を示したフローチャートである。 図７は、Ｅｘｐａｎｄ状態のセンサ・ノードが状態判定を行なうための処理手順を示したフローチャートである。 図８は、Ｂｒｉｄｇｅ状態のセンサ・ノードが状態判定を行なうための処理手順を示したフローチャートである。 図９は、ノードが近隣ノードからＨＥＬＬＯメッセージを受信したときの処理手順を示したフローチャートである。 図１０は、Ｅｘｐａｎｄ及びＢｒｉｄｇｅ状態のノードが移動機能を用いてランダム・ウォークを行なうための処理手順を示したフローチャートである。 図１１は、ネットワーク・トポロジの基本的なメカニズムにおいて、トポロジを拡大する性能の劣化が生じた状況を説明するための図である。 図１２は、ネットワーク・トポロジの基本的なメカニズムにおいて、トポロジを拡大する性能の劣化が生じた状況を説明するための図である。 図１３は、電波強度と距離の関係からなる数理モデルに基づいて最適な電波強度を得る方法を説明するための図である。 図１４は、安価で微小な数万個のセンサ・ノードを飛行機で上空からばら撒いてセンサ・ネットワークを形成する様子を示した図である。

符号の説明

１０…センサ・ノード
１１…センサ
１２…演算処理部
１３…無線通信機能部
１４…移動機能部

Claims (24)

1. 無線通信機能と移動機能を備えた複数のノードの自律分散的な動作によりネットワーク・トポロジを構築するネットワーク・システムであって、
   各ノードは、センサを備え、移動しながらネットワーク・トポロジを拡張する近隣ノードとの接続関係が得られる位置を探索するＥｘｐａｎｄ状態と、移動しながら独立したネットワーク・トポロジ間を接続する近隣ノードとの接続関係が得られる位置を探索するＢｒｉｄｇｅ状態と、現在位置に停止してネットワーク・トポロジの構成要素となるＳｔａｙ状態を持ち、前記Ｅｘｐａｎｄ状態では第１の条件に合致したことに応じて前記Ｓｔａｙ状態に遷移するとともに、前記Ｂｒｉｄｇｅ状態では前記第１の条件とは異なる第２の条件に合致したことに応じて前記Ｓｔａｙ状態に遷移し、
   各ノードが前記Ｅｘｐａｎｄ及びＢｒｉｄｇｅ状態の間で動的に切り替わりながら前記Ｓｔａｙ状態へ遷移していくことでネットワーク・トポロジを形成していく、
   ことを特徴とするネットワーク・システム。
2. Ｅｘｐａｎｄ状態のノードは、１つのＳｔａｙ状態にある近隣ノードと接続可能となった第１の条件下でＳｔａｙ状態に遷移する、
   ことを特徴とする請求項１に記載のネットワーク・システム。
3. Ｂｒｉｄｇｅ状態のノードは、お互いに近隣ノードの関係ではなく且つ同一の近隣ノードを保有しない独立した関係にある２以上のノードと接続可能となった第２の条件下でＳｔａｙ状態に遷移する、
   ことを特徴とする請求項１に記載のネットワーク・システム。
4. ネットワーク・トポロジの初期時ではすべてのノードはＥｘｐａｎｄ状態であり、
   ノード密度が所定値を上回ったときに所定の確率でＢｒｉｄｇｅ状態のノードを発生させる、
   ことを特徴とする請求項１に記載のネットワーク・システム。
5. 各ノードは、自分の状態と、自分にとっての近隣ノードのリストを含んだ第１の信号を所定のタイミングで送信し、近隣ノードからの第１の信号を受信処理することにより、接続可能な近隣ノードを認識し、又はノード密度を求める、
   ことを特徴とする請求項１に記載のネットワーク・システム。
6. Ｅｘｐａｎｄ状態のノードは、接続可能となったＳｔａｙ状態にある前記近隣ノードに対し第２の信号を送信するとともに、第３の信号を受信したことに応答して、Ｓｔａｙ状態に遷移する、
   ことを特徴とする請求項２に記載のネットワーク・システム。
7. Ｂｒｉｄｇｅ状態のノードは、独立した関係にある前記の各ノードに対し第２の信号を送信するとともに、第３の信号を受信したことに応答して、Ｓｔａｙ状態に遷移する、
   ことを特徴とする請求項３に記載のネットワーク・システム。
8. 第２の信号を送信したノードは、所定期間内に第３の信号を受信できなかったときに、Ｓｔａｙ状態への遷移を取り消すとともに、第４の信号を再度送信する、
   ことを特徴とする請求項６又は７のいずれかに記載のネットワーク・システム。
9. Ｓｔａｙ状態以外のときに第２の信号を受信したノードはＳｔａｙ状態に遷移し、第４の信号を受信したことによりＳｔａｙ状態への遷移を取り消す、
   ことを特徴とする請求項８に記載のネットワーク・システム。
10. 各ノードは、前記無線通信機能において適当な電波強度が得られる近隣ノードとの接続関係を得る、
    ことを特徴とする請求項１に記載のネットワーク・システム。
11. 各ノードは、前記無線通信機能において電波強度が所定値を超える近隣ノード、並びに電波強度が所定値を下回る近隣ノードは、電波強度が適当でないとして接続関係を避ける、
    ことを特徴とする請求項１０に記載のネットワーク・システム。
12. センサ・ネットワークにおけるセンサ・ノードとして動作する無線通信装置であって、
    現在位置での所望の情報を取得するセンサと、
    近隣のセンサ・ノードとの間で通信動作を行なう無線通信機能部と、
    当該装置の位置を移動させる移動機能部と、
    前記センサが取得したセンサ情報の処理、並びに前記の各機能部の動作を制御する制御部を備え、
    前記制御部は、前記無線通信機能部によって得られる近隣ノードに関する接続情報に基づいて、前記移動機能部を用いて移動しながらネットワーク・トポロジを拡張する近隣ノードとの接続関係が得られる位置を探索するＥｘｐａｎｄ状態及び移動しながら独立したネットワーク・トポロジ間を接続する近隣ノードとの接続関係が得られる位置を探索するＢｒｉｄｇｅ状態の間で動的に切り替え、前記Ｅｘｐａｎｄ状態では第１の条件に合致したことに応じて前記移動機能部を用いた移動を現在位置にて停止してネットワーク・トポロジの構成要素となるＳｔａｙ状態に遷移し、前記Ｂｒｉｄｇｅ状態では前記第１の条件とは異なる第２の条件に合致したことに応じて前記Ｓｔａｙ状態に遷移する、
    ことを特徴とする無線通信装置。
13. 前記制御部は、Ｅｘｐａｎｄ状態において、１つのＳｔａｙ状態にある近隣ノードと接続可能となった第１の条件下でＳｔａｙ状態に遷移させる、
    ことを特徴とする請求項１２に記載の無線通信装置。
14. 前記制御部は、Ｂｒｉｄｇｅ状態において、お互いに近隣ノードの関係ではなく且つ同一の近隣ノードを保有しない独立した関係にある２以上のノードと接続可能となった第２の条件下でＳｔａｙ状態に遷移させる、
    ことを特徴とする請求項１２に記載の無線通信装置。
15. 前記制御部は、初期時ではＥｘｐａｎｄ状態に設定し、前記無線通信機能部によって得られる近隣ノードに関する接続情報に基づいてノード密度が所定値を上回ったことが検知されたときに所定の確率でＢｒｉｄｇｅ状態に遷移させる、
    ことを特徴とする請求項１２に記載の無線通信装置。
16. 前記制御部は、
    現在の状態と、自分にとっての近隣ノードのリストを含んだ第１の信号を生成し、所定のタイミングで前記無線通信機能部から送信するとともに、
    前記無線通信機能部で受信された近隣ノードからの第１の信号を処理し、接続可能な近隣ノードを認識し又はノード密度を求める、
    ことを特徴とする請求項１２に記載の無線通信装置。
17. 前記制御部は、Ｅｘｐａｎｄ状態において、接続可能となったＳｔａｙ状態にある前記近隣ノードに対し第２の信号を送信するとともに、第３の信号を受信したことに応答して、Ｓｔａｙ状態に遷移させる、
    ことを特徴とする請求項１３に記載の無線通信装置。
18. 前記制御部は、Ｂｒｉｄｇｅ状態において、独立した関係にある前記の各ノードに対し第２の信号を送信するとともに、第３の信号を受信したことに応答して、Ｓｔａｙ状態に遷移する、
    ことを特徴とする請求項１４に記載の無線通信装置。
19. 前記制御部は、第２の信号を送信してから所定期間内に第３の信号を受信できなかったときに、Ｓｔａｙ状態への遷移を取り消すとともに、第４の信号を再度送信する、
    ことを特徴とする請求項１７又は１８のいずれかに記載の無線通信装置。
20. 前記制御部は、Ｓｔａｙ状態以外のときに、第２の信号を受信したことに応答してＳｔａｙ状態に遷移し、第４の信号を受信したことによりＳｔａｙ状態への遷移を取り消す、
    ことを特徴とする請求項１９に記載の無線通信装置。
21. 前記制御部は、前記無線通信機能部において適当な電波強度が得られる近隣ノードとの接続関係を得る、
    ことを特徴とする請求項１２に記載の無線通信装置。
22. 前記制御部は、前記無線通信機能部において電波強度が所定値を超える近隣ノード、並びに電波強度が所定値を下回る近隣ノードは、電波強度が適当でないとして接続関係を避ける、
    ことを特徴とする請求項２１に記載の無線通信装置。
23. センサと無線通信機能と移動機能を備えた無線通信装置がセンサ・ネットワークにおけるセンサ・ノードとして動作する無線通信方法であって、
    前記無線通信機能によって得られる近隣ノードに関する接続情報に基づいて、前記移動機能を用いて移動しながらネットワーク・トポロジを拡張する近隣ノードとの接続関係が得られる位置を探索するＥｘｐａｎｄ状態及び移動しながら独立したネットワーク・トポロジ間を接続する近隣ノードとの接続関係が得られる位置を探索するＢｒｉｄｇｅ状態の間で動的に切り替えるステップと、
    前記Ｅｘｐａｎｄ状態において、第１の条件に合致したことに応じて前記移動機能部を用いた移動を停止したＳｔａｙ状態に遷移するステップと、
    前記Ｂｒｉｄｇｅ状態において、前記第１の条件とは異なる第２の条件に合致したことに応じて前記Ｓｔａｙ状態に遷移するステップと、
    を具備することを特徴とする無線通信方法。
24. センサと無線通信機能と移動機能を備えた無線通信装置がセンサ・ネットワークにおけるセンサ・ノードとして動作するための処理をコンピュータ上で実行するようにコンピュータ可読形式で記述されたコンピュータ・プログラムであって、前記コンピュータに対して、
    前記無線通信機能によって得られる近隣ノードに関する接続情報に基づいて、前記移動機能を用いて移動しながらネットワーク・トポロジを拡張する近隣ノードとの接続関係が得られる位置を探索するＥｘｐａｎｄ状態及び移動しながら独立したネットワーク・トポロジ間を接続する近隣ノードとの接続関係が得られる位置を探索するＢｒｉｄｇｅ状態の間で動的に切り替えるステップと、
    前記Ｅｘｐａｎｄ状態において、第１の条件に合致したことに応じて前記移動機能部を用いた移動を停止したＳｔａｙ状態に遷移するステップと、
    前記Ｂｒｉｄｇ状態において、前記第１の条件とは異なる第２の条件に合致したことに応じて前記Ｓｔａｙ状態に遷移するステップと、
    を実行させることを特徴とするコンピュータ・プログラム。

Images