(57)【要約】  複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークにおいて各ノードが実行する時刻同期方法が提供される。その時刻同期方法は、１ビーコン周期毎に乱数を用いてスロット数を生成する生成ステップと、前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かを判定する判定ステップと、前記判定ステップでビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に自ノードの時刻情報を記載したビーコンを送信するステップとを有する。
2007052709.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークにおいて各ノードが実行する時刻同期方法であって、
１ビーコン周期毎に乱数を用いてスロット数を生成する生成ステップと、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かを判定する判定ステップと、
前記判定ステップでビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に自ノードの時刻情報を記載したビーコンを送信するステップと
を有することを特徴とする時刻同期方法。
【請求項２】
請求項１記載の時刻同期方法において、
前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、１ビーコン周期分だけ自ノードをアクティブモードとするステップを有することを特徴とする時刻同期方法。
【請求項３】
請求項１記載の時刻同期方法において、
前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、１ビーコン周期分だけ任意の確率で自ノードをアクティブモードまたはパワーセーブモードとするステップを有することを特徴とする時刻同期方法。
【請求項４】
請求項１記載の時刻同期方法において、
前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、１ビーコン周期分だけ前記スロット数に基づく確率で自ノードをアクティブモードまたはパワーセーブモードとするステップを有することを特徴とする時刻同期方法。
【請求項５】
請求項１乃至４のいずれか１項記載の時刻同期方法において、
ビーコン送信をキャンセルしたとき、自ノードの時刻が所定時刻である場合に、１ビーコン周期分だけ自ノードをアクティブモードとするステップを有することを特徴とする時刻同期方法。
【請求項６】
複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークのノードを構成する通信装置であって、
１ビーコン周期毎に乱数を用いてスロット数を生成するスロット数生成手段と、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かの判定を行う判定手段と、
前記判定手段でビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に前記通信装置の時刻情報を記載したビーコンを送信するビーコン送信制御手段と
を有することを特徴とする通信装置。
【請求項７】
請求項６記載の通信装置において、
ビーコン送信をキャンセルしたとき、前記通信装置の時刻が所定時刻である場合に、１ビーコン周期分だけ前記通信装置をアクティブモードとするアクティブモード設定手段を有することを特徴とする通信装置。
【請求項８】
請求項６または７記載の通信装置を有することを特徴とするノード。
【請求項９】
複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークのノードを構成するコンピュータを、
１ビーコン周期毎に乱数を用いてスロット数を生成するスロット数生成手段、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かの判定を行う判定手段、
前記判定手段でビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に前記コンピュータの時刻情報を記載したビーコンを送信するビーコン送信制御手段、
として機能させるためのプログラム。
【請求項１０】
請求項９記載のプログラムにおいて、
前記コンピュータを、ビーコン送信をキャンセルしたとき、前記コンピュータの時刻が所定時刻である場合に、１ビーコン周期分だけ前記コンピュータをアクティブモードとするアクティブモード設定手段として更に機能させることを特徴とするプログラム。
【請求項１１】
請求項９または１０に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時刻同期方法及びそれに用いる通信装置及びノードに関する。より詳細には、本発明は、複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して時刻同期を行うアドホックネットワークの時刻同期方法及びそれに用いる通信装置及びノードに関する。
【背景技術】
【０００２】
近年、アクセスポイントを必要とせず無線で接続できるパーソナルコンピュータ、ＰＤＡ、センサノード等のノード（端末ともいう）のみで構成されるアドホックネットワークの開発が進められている。【０００３】
ＩＥＥＥ８０２．１１プロトコル（非特許文献１参照）を用いたアドホックネットワークにおいては、各ノードはそれぞれの内部にもつ時刻をお互いにビーコンを送受信することにより更新していく。その結果、過渡状態の後に、全てのノードの時刻が一致して時刻同期が達成される。  
図１にアドホックネットワークの一例の構成図を示す。同図中、アドホックネットワークは複数のノードＡ〜Ｆから構成される。各ノードＡ〜Ｆは具体的にはパーソナルコンピュータ、ＰＤＡ、センサノード等の通信デバイスであり、各ノードは直接通信可能な半径Ｒ（通信範囲）のセルを有している。なお、半径Ｒはノード毎にある程度のバラツキを持っている。【０００４】
図１に示すようなアドホックネットワークを構成するノードのもつ時刻を制限された消費電力の下で自律分散的に同期させ維持するために、各ノードは以下に示す第１〜第３の機能を有している。【０００５】
第１の機能は、図２に示すように、一定周期（例えば１００ｍｓｅｃ）でアクティブモードとパワーセーブモードの２つのモードを繰り返す。図２において、アクティブモードに対応してコンテンションウィンドウが設定され、このコンテンションウィンドウはＷ＋１（Ｗは例えば３１）個のバックオフスロット（１バックオフスロットは例えば５０μｓｅｃ）に分割される。バックオフスロットは０からＷまでの整数値であるスロット数により特定される。【０００６】
第２の機能は、アクティブモードの期間中に他のノードと競合を行い、勝ち残ったノードが自ノードの時刻を記載したビーコンを周りに送信し、他のノードはビーコン送信を行わない。【０００７】
第３の機能は、条件１〜３が同時に満たされる時のみ、自ノードの時刻を受信したビーコンに記載されている時刻に更新することで時刻同期を行う。
（条件１）そのノードがその時アクティブモードの期間中である。
（条件２）到来するビーコンがコリジョンを生じない。
（条件３）受信したビーコンに記載されている時刻が、自ノードのもつ時刻より進んでいる（値が大きい）。  
従来のアドホックネットワークにおけるビーコン送信ノードの選定方法について図３Ａ、図３Ｂを用いて説明する。いま、ノードＡ、Ｂ、Ｃが互いに同一セル内に存在するものとする。図３Ａに示すように、ノードＡ、Ｂ、Ｃはそれぞれビーコン周期毎にランダムにスロット数（ビーコン送信予定時刻）を生成する。この場合、ノードＣが最小のスロット数（＝２）を与えられ、ノードＡのスロット数（＝６）、ノードＢのスロット数（＝９）を与えられたとする。【０００８】
このとき、図３Ｂに示すように、ノードＣは、このスロット数（＝２）に対応する時刻においてビーコン送信を行い、ノードＡ、Ｂはこれを受信する。ビーコンを受信したノードＡ、Ｂは各々のスロット数（＝６，９）に予定されているビーコン送信をキャンセルし、ビーコン送信を行わない。これにより、ビーコン送信ノードの選定はノード間による競合のみにより行われる。
【非特許文献１】ＩＥＥＥ  Ｓｔｄ．８０２．１１  Ｗｉｒｅｌｅｓｓ  ＬＡＮ  Ｍｅｄｉｕｍ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ（ＭＡＣ）  ａｎｄ  Ｐｈｙｓｉｃａｌ  Ｌａｙｅｒ（ＰＨＹ）  ｓｐｅｃｉｆｉｃａｔｉｏｎ，ｈｔｔｐ：／／ｓｔａｎｄａｒｄｓ．ｉｅｅｅ．ｏｒｇ／ｇｒｔｉｅｅｅ８０２／ｄｏｗｎｌｏａｄ／８０２．１１−１９９９．ｐｄｆ
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ビーコン送信において問題となるのは、あるノードに同じタイミングで複数のビーコンが到来するとコリジョン（衝突）を生じ、いずれのビーコンも受信されないことである。この場合、その時点で当該ノードの時刻は更新されない。【００１０】
したがって、このようなコリジョンが頻繁に生じると時刻同期完了までの過渡状態が長時間継続し、通常の通信を開始することの妨げとなる。最近の研究では以上の問題を現実的に想定される条件下で解析しており、その結果、同期完了までに要する時間はネットワークを構成するノード数のべき乗に比例して増加し、ノード数が数十程度のアドホックネットワークにおいてさえ、現在の通信レートでは同期完了までに数十秒以上の時間を要するケースが生じることが判明している。【００１１】
このことから、ＩＥＥＥ８０２．１１プロトコルによる大規模アドホックネットワークの構築において、現状のままではノード数が数百、数千ともなる大規模なネットワークの実現は時刻同期の点から困難であるという問題があった。【００１２】
本発明は、上記の点に鑑みなされたものであり、高い同期能力を得ることを可能とする時刻同期に係る技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題は、複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークにおいて各ノードが実行する時刻同期方法であって、
１ビーコン周期毎に乱数を用いてスロット数を生成する生成ステップと、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かを判定する判定ステップと、
前記判定ステップでビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に自ノードの時刻情報を記載したビーコンを送信するステップとを有することを特徴とする時刻同期方法により解決される。【００１４】
また、前記時刻同期方法において、前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、１ビーコン周期分だけ自ノードをアクティブモードとするステップを有することとしてもよい。また、前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、１ビーコン周期分だけ任意の確率で自ノードをアクティブモードまたはパワーセーブモードとするステップを有することとしてもよい。【００１５】
また、前記時刻同期方法において、前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、１ビーコン周期分だけ前記スロット数に基づく確率で自ノードをアクティブモードまたはパワーセーブモードとするステップを有することとしてもよく、ビーコン送信をキャンセルしたとき、自ノードの時刻が所定時刻である場合に、１ビーコン周期分だけ自ノードをアクティブモードとするステップを有することとしてもよい。【００１６】
また、上記の課題は、複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークのノードを構成する通信装置であって、
１ビーコン周期毎に乱数を用いてスロット数を生成するスロット数生成手段と、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かの判定を行う判定手段と、
前記判定手段でビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に前記通信装置の時刻情報を記載したビーコンを送信するビーコン送信制御手段とを有することを特徴とする通信装置によっても解決できる。【００１７】
また、本発明は、複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークのノードを構成するコンピュータを、
１ビーコン周期毎に乱数を用いてスロット数を生成するスロット数生成手段、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かの判定を行う判定手段、
前記判定手段でビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に前記コンピュータの時刻情報を記載したビーコンを送信するビーコン送信制御手段、として機能させるためのプログラムとして構成することもできる。
【発明の効果】
【００１８】
本発明によれば、無駄なビーコン送信を抑えコリジョンの発生頻度を低くでき、高い同期能力を得ることができる。
【図面の簡単な説明】
【００１９】
【図１】アドホックネットワークの一例の構成図である。
【図２】ビーコン周期を説明するための図である。
【図３Ａ】従来のアドホックネットワークにおけるビーコン送信ノードの選定方法を説明するための図である。
【図３Ｂ】従来のアドホックネットワークにおけるビーコン送信ノードの選定方法を説明するための図である。
【図４】本発明のアドホックネットワークを構成するノードの一実施形態のブロックである。
【図５】ビーコン送受信処理の第１実施形態のフローチャートである。
【図６Ａ】本発明のアドホックネットワークにおけるビーコン送信ノードの選定方法を説明するための図である。
【図６Ｂ】本発明のアドホックネットワークにおけるビーコン送信ノードの選定方法を説明するための図である。
【図７】ビーコン送受信処理の第２実施形態のフローチャートである。
【図８】ビーコン送受信処理の第３実施形態のフローチャートである。
【図９】ビーコン送受信処理の第４実施形態のフローチャートである。
【図１０】本発明のアドホックネットワークにおける時刻同期を説明するための図である。
【図１１】本発明のアドホックネットワークにおける時刻同期を説明するための図である。
【符号の説明】
【００２０】
１０  ハードディスク装置
１１  ＣＰＵ
１２  メモリ
１３  入力装置
１４  ディスプレイ装置
１５  ＰＣカードスロット
１６  バス
２０  無線ネットワークカード
２１  インタフェース部
２２  プロセッサ部
２３  ＭＡＣ処理部
２４  変復調部
２５  送受信部
２６  アンテナ
【発明を実施するための最良の形態】
【００２１】
以下、図面に基づいて本発明の実施形態について説明する。【００２２】
＜ノード装置の構成＞
図４は、本発明のアドホックネットワークを構成するノードの一実施形態のブロック図を示す。このノードはパーソナルコンピュータであり、ハードディスク装置１０にはＣＰＵ１１で実行する各種プログラムやデータ等が記憶される。ＣＰＵ１１はハードディスク装置１０から読み出されるプログラムを実行する際に、メモリ１２を作業領域として使用する。入力装置１３はキーボードやマウス等のポインティングデバイスである。ディスプレイ装置１４は表示を行う。上記のハードディスク装置１０からＰＣカードスロット１５までの各部はバス１６で相互に接続されている。ＰＣカードスロット１５には通信装置としての無線ネットワークカード２０が装着されてバス１６に接続される。【００２３】
無線ネットワークカード２０は、インタフェース部２１、プロセッサ部２２、ＭＡＣ処理部２３、変復調部２４、送受信部２５、及びアンテナ２６を有している。インタフェース部２１は、プロセッサ部２２とＭＡＣ（媒体アクセス制御）処理部２３をバス１６に接続する。【００２４】
プロセッサ部２２は、ＭＡＣ処理部２３を制御してＭＡＣ処理を実行させると共に、後述のビーコン送受信処理を実行する。このビーコン送受信処理を行うために、プロセッサ部２２は記憶部２２ａを内蔵している。【００２５】
なお、プロセッサ部２２と記憶部２２ａに代えて、ＣＰＵと、プログラムを格納したメモリとを有するコンピュータの構成を備えてもよい。この場合、メモリに格納されたプログラムをＣＰＵが実行することにより、プロセッサ部２２が実行する後述する処理と同様の処理が実行される。また、ノードを構成する端末等のコンピュータが、当該プログラムを実行することによりプロセッサ部２２が実行する処理と同様の処理を実行することとしてもよい。【００２６】
上記プログラムは、外部の記録媒体（可搬メモリ等）から上記メモリに格納するようにしてもよいし、ネットワークを介してダウンロードすることとしてもよい。なお、プロセッサ部２２と記憶部２２ａに代えて、ＣＰＵと、プログラムを格納したメモリとを備える場合、無線ネットワークカード２０自身をコンピュータと称することもできる。【００２７】
ＭＡＣ処理部２３は、ＩＥＥＥ８０２．１１で規定されるＭＡＣ（媒体アクセス制御）処理を実行する。変復調部２４はＩＥＥＥ８０２．１１で規定されるＤＳＳＢ（Ｄｉｒｅｃｔ  Ｓｅｑｕｅｎｃｅ  Ｓｐｒｅａｄ  Ｓｐｅｃｔｒｕｍ）やＣＣＫ（Ｃｏｍｐｌｅｍｅｎｔｚａｒｙ  Ｃｏｄｅ  Ｋｅｙｉｎｇ）やＯＦＤＭ（Ｏｒｔｈｏｇｏｎａｌ  Ｆｒｅｑｕｅｎｃｙ  Ｄｉｖｉｓｉｏｎ  Ｍｕ１ｔｉｐ１ｅｘｉｎｇ：直交周波数分割多重）変調方式による変復調を行う。送受信部２５はアンテナ２６を用いて送受信を行う。【００２８】
＜第１実施形態＞
図５は、アドホックネットワークを構成するノードに装着された無線ネットワークカード２０のプロセッサ部２２が実行するビーコン送受信処理の第１実施形態のフローチャートを示す。同図中、プロセッサ部２２は、１ビーコン周期毎に実行されるステップＳ１１で乱数等を用いて値が０〜３１のスロット数を生成し、ステップＳ１２で送受信を開始する。【００２９】
ステップＳ１３で、プロセッサ部２２は、ビーコンを送信する時刻までにノードがコリジョンの発生なく他のノードからビーコンを受信したか否かを判別する。ノードがビーコンを受信していない場合にはステップＳ１４に進んで、プロセッサ部２２は、ビーコン送信の足切り判定を行う。足切り判定では、ステップＳ１１で生成したスロット数が予め記憶部２２ａに設定された閾値（例えば１）未満であるか否かの判定が行われる。スロット数が閾値未満であれば足切りは回避され、スロット数が閾値以上である場合に足切りが行われる。【００３０】
ビーコン送信の足切りが回避された場合は、ステップＳ１５で、ノードは自ノードの時刻を記載したビーコンの送信を行い、ステップＳ１６で１ビーコン周期分だけアクティブモードを持続してステップＳ１１に進む。足切りが行なわれる場合は、ノードはステップＳ１７でビーコン送信をキャンセルし、ステップＳ１８で１ビーコン周期分だけアクティブモードを持続してステップＳ１１に進む。【００３１】
一方、ステップＳ１３で、ノードがビーコンを受信している場合にはステップＳ１９でビーコン送信をキャンセルし、ステップＳ２０で１ビーコン周期分だけパワーセーブモードとなり、その後アクティブモードに戻ってステップＳ１１に進む。【００３２】
本実施形態のアドホックネットワークにおけるビーコン送信ノードの選定方法について図６Ａ、図６Ｂを用いて説明する。図１に示すように、ノードＡ、Ｂ、Ｃが互いに同一セル内に存在するものとする。図６Ａに示すように、ノードＡ、Ｂ、Ｃはそれぞれビーコン周期毎にランダムにスロット数（ビーコン送信予定時刻）を生成する。この場合、ノードＣが最小のスロット数（＝２）を与えられ、ノードＡのスロット数（＝６）、ノードＢのスロット数（＝９）を与えられたとする。【００３３】
このとき、ノードＡ、Ｂ、Ｃ間における競合後、そのセルにおけるノードのうち最小のスロット数をもっているノードＣがビーコン送信ノードに選出される。つまり、ノードＡ、Ｂ、Ｃの中で、他からビーコンを受信する前に最も早くビーコン送信時刻になるのがノードＣである。【００３４】
このノードＣは、ビーコンを送信する前に、そのスロット数が閾値（例えば１）を越えているか否かをチェックする（図６Ｂ）。スロット数が閾値未満であれば（すなわち、スロット数＝０であれば）、予定通りビーコンを送信し、その後そのノードＣはアクティブモードを持続する。一方、スロット数が閾値以上であれば、そのノードＣがビーコンを送信することは取り止め、同時にそのノードＣは当初の予定通りアクティブモードを持続させる。上記の付加的操作を閾値によるビーコン送信の足切り（キャンセル）判定と呼んでいる。【００３５】
本実施形態では、ビーコン送信の足切りを行うことによってビーコン送信ノードに選出されるノード数を減少させることにより、コリジョンの発生頻度を低くすることができ、時刻同期が完了するまでの時間を短縮でき、高い同期能力を得ることができる。【００３６】
＜第２実施形態＞
第１実施形態では、足切り判定により当初予定していたビーコン送信を取り止めたノードは、その後、自動的にアクティブモードを持続する。しかし、足切りを受けるノード数が多くなると、それだけアクティブモードを持続するノード数も多くなってしまい、アドホックネットワーク全体のノードにおけるエネルギー消費が増大する。このため、ノードのエネルギー消費を抑える観点から工夫した第２、第３実施形態について説明する。【００３７】
図７は、アドホックネットワークを構成するノードに装着された無線ネットワークカード２０のプロセッサ部２２が実行するビーコン送受信処理の第２実施形態のフローチャートを示す。同図中、プロセッサ部２２は、１ビーコン周期毎に実行されるステップＳ３１で乱数等を用いて値が０〜３１のスロット数を生成し、ステップＳ３２で送受信を開始する。【００３８】
ステップＳ３３で、プロセッサ部２２は、ビーコンを送信する時刻までにノードがコリジョンの発生なく他のノードからビーコンを受信したか否かを判別する。ノードがビーコンを受信していない場合にはステップＳ３４に進んで、プロセッサ部２２は、ビーコン送信の足切り判定を行う。足切り判定では、ステップＳ３１で生成したスロット数が予め記憶部２２ａに設定された閾値（例えば１）未満であるか否かの判定が行われる。スロット数が閾値未満であれば足切りは回避され、スロット数が閾値以上である場合に足切りが行われる。【００３９】
ビーコン送信の足切りが回避された場合は、ステップＳ３５で、ノードは自ノードの時刻を記載したビーコンの送信を行い、ステップＳ３６で１ビーコン周期分だけアクティブモードを持続してステップＳ３１に進む。足切りが行なわれる場合は、ノードはステップＳ３７でビーコン送信をキャンセルし、ステップＳ３８で乱数を用いて所定の確率（例えば９０％）でアクティブモードを選択し、残りの確率（例えば１０％）でパワーセーブモードを選択し、１ビーコン周期分だけ選択したモードを持続し、その後アクティブモードに戻ってステップＳ３１に進む。【００４０】
一方、ステップＳ３３で、ノードがビーコンを受信している場合にはステップＳ３９でビーコン送信をキャンセルし、ステップＳ４０で１ビーコン周期分だけパワーセーブモードとなり、その後アクティブモードに戻ってステップＳ３１に進む。【００４１】
これによって、アドホックネットワーク全体のノードにおけるエネルギー消費の増大を低減することができる。【００４２】
＜第３実施形態＞
図８は、アドホックネットワークを構成するノードに装着された無線ネットワークカード２０のプロセッサ部２２が実行するビーコン送受信処理の第３実施形態のフローチャートを示す。同図中、プロセッサ部２２は、１ビーコン周期毎に実行されるステップＳ５１で乱数等を用いて値が０〜３１のスロット数を生成し、ステップＳ５２で送受信を開始する。【００４３】
ステップＳ５３で、プロセッサ部２２は、ビーコンを送信する時刻までにノードがコリジョンの発生なく他のノードからビーコンを受信したか否かを判別する。ノードがビーコンを受信していない場合にはステップＳ５４に進んで、プロセッサ部２２は、ビーコン送信の足切り判定を行う。足切り判定では、ステップＳ５１で生成したスロット数が予め記憶部２２ａに設定された閾値（例えば１）未満であるか否かの判定が行われる。スロット数が閾値未満であれば足切りは回避され、スロット数が閾値以上である場合に足切りが行われる。【００４４】
ビーコン送信の足切りが回避された場合は、ステップＳ５５で、ノードは自ノードの時刻を記載したビーコンの送信を行い、ステップＳ５６で１ビーコン周期分だけアクティブモードを持続してステップＳ５１に進む。足切りが行なわれる場合は、ノードはステップＳ５７でビーコン送信をキャンセルし、ステップＳ５８でスロット数が予め記憶部２２ａに設定された一定値（例えば３０）以下か否かを判別する。スロット数が一定値以下の場合は、ステップＳ５６に進んで１ビーコン周期分だけアクティブモードを持続してステップＳ５１に進む。スロット数が一定値を超える場合は、ステップＳ５９に進んで１ビーコン周期分だけパワーセーブモードとなり、その後アクティブモードに戻ってステップＳ５１に進む。【００４５】
一方、ステップＳ５３で、ノードがビーコンを受信している場合にはステップＳ６０でビーコン送信をキャンセルし、ステップＳ６１で１ビーコン周期分だけパワーセーブモードとなり、その後アクティブモードに戻ってステップＳ５１に進む。【００４６】
上記第２実施形態では足切り判定の結果に基づき送信キャンセルを行った場合に乱数を用いてアクティブモードかパワーセーブモードかを選択しているが、第３実施形態では元々乱数により発生したスロット数を利用してアクティブモードかパワーセーブモードかを選択しており、その効果は実質的に等価である。【００４７】
＜第４実施形態＞
図９は、アドホックネットワークを構成するノードに装着された無線ネットワークカード２０のプロセッサ部２２が実行するビーコン送受信処理の第４実施形態のフローチャートを示す。同図中、プロセッサ部２２は、１ビーコン周期毎に実行されるステップＳ７１で乱数等を用いて値が０〜３１のスロット数を生成し、ステップＳ７２で送受信を開始する。【００４８】
ステップＳ７３で、プロセッサ部２２は、ビーコンを送信する時刻までにノードがコリジョンの発生なく他のノードからビーコンを受信したか否かを判別する。ノードがビーコンを受信していない場合にはステップＳ７４に進んで、プロセッサ部２２は、ビーコン送信の足切り判定を行う。足切り判定では、ステップＳ７１で生成したスロット数が予め記憶部２２ａに設定された閾値（例えば１）未満であるか否かの判定が行われる。スロット数が閾値未満であれば足切りは回避され、スロット数が閾値以上である場合に足切りが行われる。【００４９】
ビーコン送信の足切りが回避された場合は、ステップＳ７５で、ノードは自ノードの時刻を記載したビーコンの送信を行い、ステップＳ７６で１ビーコン周期分だけアクティブモードを持続してステップＳ７１に進む。足切りが行なわれる場合は、ノードはステップＳ７７でビーコン送信をキャンセルしたのち、ステップＳ８０に進む。【００５０】
一方、ステップＳ７３でノードがビーコンを受信している場合にはステップＳ７９でビーコン送信をキャンセルしたのち、ステップＳ８０に進む。ステップＳ８０ではプロセッサ部２２は、ノードの時刻が予め記憶部２２ａに設定された所定時刻（例えば整数秒となる時刻）であるか否かを判別する。ノードの時刻が所定時刻である場合はステップＳ８１で１ビーコン周期分だけアクティブモードを持続してステップＳ７１に進む。ノードの時刻が所定時刻ではない場合はステップＳ８２で１ビーコン周期分だけパワーセーブモードとなり、その後アクティブモードに戻ってステップＳ７１に進む。【００５１】
これにより、各ノードは内部に保持する時刻が整数秒となる毎に１ビーコン周期分だけアクティブモードを持続することになり、この間にビーコン送信ノードから送信されたビーコンを受信して、一斉に時刻同期が行われる。【００５２】
なお、図７、図８の実施形態においても、図９におけるステップＳ８０〜Ｓ８２を追加しても良いことはもちろんである。【００５３】
図１０は、一辺が５Ｒの正方形の領域ＡＲ１に３６個のノードをランダムに固定配置した場合を想定している。なお、Ｒは通信範囲の半径に対応する正規化された距離である。各ノードは一様に通信範囲Ｒを持つものとする。ここで、初期において領域ＡＲ１内の各ノードは相互にビーコンを送受信し、全体の時刻同期が得られ１つのアドホックネットワーク（先のネットワーク）を構成しているものとする。【００５４】
そのとき、領域ＡＲ１の任意の位置に、他のネットワークに属しているノードＮＤ１が速やかに参入したものとする。ここで、このノードＮＤ１のもつ時刻は、先のネットワークを構成するノードの時刻より進んでおり（値が大きい）、かつ、そのビーコン周期におけるアクティブモードの位相は先のネットワークのビーコン周期におけるアクティブモードの位相に対し大略逆位相であったとする。【００５５】
ここで、参入したノードＮＤ１は、その通信範囲Ｒ内に存在するアクティブモードのノードの時刻を同期させる。その時刻同期の伝播は通信範囲Ｒ内でアクティブモードを持続している少数のノードを介して行われるので、ビーコン周期（１００ｍｓ）のオーダーのゆっくりとしたタイムスケールで行われる。【００５６】
従来のアドホックネットワークを用いた場合、第１段階で白抜きの矢印で示すような方向で領域ＡＲ１の境界に沿って時刻同期の伝搬が速やかに進行し、その後、第２段階で領域ＡＲ１の内側に残ったノードが長い時間をかけて徐々に時刻同期していくことが認められている。【００５７】
第１段階が生じる理由は、ランダムなスロット数生成で最小となったものが時刻伝播を担うノード（ビーコン送信ノード）として決定されるが、その際に領域ＡＲ１の境界付近では領域ＡＲ１外にノードがないので相対的なノードの密度が疎らとなり、境界付近のノードが比較的頻繁にビーコン送信ノードに選出されるためである。図１０では第２段階における進んだ時刻のノードを白丸で示し、遅れた時刻のノードを黒丸で示す。【００５８】
これに対し、本発明によると、第１段階の過程における時刻同期の伝搬は従来よりも速くなるが、それほど大きな差ではない。しかし、第２段階において従来とは異なる同期過程を示す。その特徴は領域ＡＲ１の中央部分のノードは、あまり同期が進展しない時点と、逆に急激に同期が進行する時点を繰り返すことである。その結果、全体の同期の終了に要する時間が従来に比べ、大幅に短縮される。その理由は以下のメカニズムから説明される。
（Ａ）領域ＡＲ１の境界部分のノードがビーコン送信の足切りを受けるために、領域ＡＲ１の中央部分のノードでビーコンのコリジョンの発生率は低くなる。
（Ｂ）足切りの効果が強く現れる場合がしばしば生じ、足切りの効果が強く現れたビーコン周期において領域ＡＲ１の境界部分のノードはほとんど全てが足切りを受ける場合が生じる。このとき、領域ＡＲ１の境界部分のノードから中央部分のノードにビーコンが到来せず、その時点では同期は進行しない。
（Ｃ）領域ＡＲ１の中央部分の未だ同期を達成していないノードにおいては、スロット生成時に足切りをクリアできず、全てのノードが足切りを受ける場合が時々生じる。
（Ｄ）上記（Ｃ）が生じた直後に、領域ＡＲ１の中央部分の同期を達成していないノードは全てアクティブモードになっているので、上記（Ａ）と同様に領域ＡＲ１の境界部分のノードからビーコンがコリジョンなく到来すると、領域ＡＲ１の中央部分の全てのノードが一気に同期を完了する。【００５９】
図１０は、ネットワークの空間的広がりを考慮した例であるが、図１１に示すように空間的に密集したノード配置の場合においても、同様のメカニズムによって大幅な時刻同期の時間短縮が認められる。【００６０】
図１１においては、領域ＡＲ２内に黒丸で示す複数のノードが存在し、領域ＡＲ３内に白丸で示す複数のノードが存在する。黒丸のノードが直接通信可能なセルＳＬ２と白丸のノードが直接通信可能なセルＳＬ３とは一部重なり、重なった部分に黒丸のノードＮＤ２が配置されている。また、白丸のノードは黒丸のノードより時刻が進んでおり、黒丸のノードと白丸のノードはビーコン周期におけるアクティブモードの位相が大略逆位相であったとする。【００６１】
この場合も、黒丸のノードＮＤ２がビーコン送信足切りまたはビーコン送信した後に１ビーコン周期分だけアクティブモードを持続するときに、白丸のノードからのビーコンを受信して速やかに時刻同期を行い、その後、同様にして、ノードＮＤ２からのビーコン送信により領域ＡＲ２内に黒丸のノードが順次時刻同期を行う。これによって、従来に比べ大幅な時刻同期の時間短縮がなされる。【００６２】
本発明の第１乃至第３実施形態における時刻同期の時間短縮は、上記（Ｃ）、（Ｄ）のメカニズムが大きく貢献している。上記（Ｃ）、（Ｄ）では、同期を達成していないノードが全てアクティブとなる状態が確率的に生起するが、第４実施形態では、同期を達成していないノードが全てアクティブとなる状態が所定時刻毎に一定周期で生じるため、さらに同期に要する時間を短縮することができる。【００６３】
消費エネルギーに関しては、同期が進行している過渡状態時の各ノードのパケット送信およびアクティブモードを持続するのに要する第１消費エネルギーと、同期が完了して定常状態にある時の各ノードのパケット送信およびアクティブモードを持続するのに要する第２消費エネルギーについて考える必要がある。【００６４】
本発明の第１実施形態においては、第１消費エネルギーは従来と比べ単位時間当たりの消費エネルギーが若干高くなる。ところが、過渡状態の継続時間は従来と比べかなり短くなるので、第１消費エネルギーの総計は結局、本発明の方が従来よりも下まわる。一方、第２消費エネルギーは、通信範囲Ｒが相当に小さい場合を除き、従来と本発明のそれには有意な差がみられない。したがって、全消費エネルギーにおいて、本発明は従来よりも省エネルギー性を持つことがわかる。また、これらの傾向は第２、第３実施形態を導入する場合により強められる。【００６５】
なお、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において種々の変更及び応用が可能である。【００６６】
本国際出願は２００５年１１月４日に出願された日本国特許出願第２００５−３２０５７３号に基づく優先権を主張するものであり、その全内容を本国際出願に援用する。
【図１】
2007052709.tif 000003
【図２】
2007052709.tif 000004
【図３Ａ】
2007052709.tif 000005
【図３Ｂ】
2007052709.tif 000006
【図４】
2007052709.tif 000007
【図５】
2007052709.tif 000008
【図６Ａ】
2007052709.tif 000009
【図６Ｂ】
2007052709.tif 000010
【図７】
2007052709.tif 000011
【図８】
2007052709.tif 000012
【図９】
2007052709.tif 000013
【図１０】
2007052709.tif 000014
【図１１】
2007052709.tif 000015
【国際調査報告】
2007052709.tif 000016
2007052709.tif 000017