TOP > 国内特許検索 > 時刻同期方法及びそれに用いる通信装置及びノード > 明細書

明細書 :時刻同期方法及びそれに用いる通信装置及びノード

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4982759号 (P4982759)
登録日 平成24年5月11日(2012.5.11)
発行日 平成24年7月25日(2012.7.25)
発明の名称または考案の名称 時刻同期方法及びそれに用いる通信装置及びノード
国際特許分類 H04W  56/00        (2009.01)
H04W  84/18        (2009.01)
H04L   7/00        (2006.01)
FI H04Q 7/00 462
H04Q 7/00 633
H04L 7/00 B
請求項の数または発明の数 11
全頁数 16
出願番号 特願2007-542784 (P2007-542784)
出願日 平成18年11月1日(2006.11.1)
国際出願番号 PCT/JP2006/321887
国際公開番号 WO2007/052709
国際公開日 平成19年5月10日(2007.5.10)
優先権出願番号 2005320573
優先日 平成17年11月4日(2005.11.4)
優先権主張国 日本国(JP)
審査請求日 平成21年9月3日(2009.9.3)
特許権者または実用新案権者 【識別番号】504133110
【氏名又は名称】国立大学法人電気通信大学
発明者または考案者 【氏名】田中 久陽
【氏名】太田 大輔
個別代理人の代理人 【識別番号】100070150、【弁理士】、【氏名又は名称】伊東 忠彦
審査官 【審査官】矢頭 尚之
参考文献・文献 特開2005-223593(JP,A)
特開2005-151476(JP,A)
調査した分野 H04W 56/00
H04L 7/00
H04W 84/18
特許請求の範囲 【請求項1】
複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークにおいて各ノードが実行する時刻同期方法であって、
1ビーコン周期毎に乱数を用いてスロット数を生成する生成ステップと、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かを判定する判定ステップと、
前記判定ステップでビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に自ノードの時刻情報を記載したビーコンを送信するステップと
を有することを特徴とする時刻同期方法。
【請求項2】
請求項1記載の時刻同期方法において、
前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、1ビーコン周期分だけ自ノードをアクティブモードとするステップを有することを特徴とする時刻同期方法。
【請求項3】
請求項1記載の時刻同期方法において、
前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、1ビーコン周期分だけ任意の確率で自ノードをアクティブモードまたはパワーセーブモードとするステップを有することを特徴とする時刻同期方法。
【請求項4】
請求項1記載の時刻同期方法において、
前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、1ビーコン周期分だけ前記スロット数に基づく確率で自ノードをアクティブモードまたはパワーセーブモードとするステップを有することを特徴とする時刻同期方法。
【請求項5】
請求項1乃至4のいずれか1項記載の時刻同期方法において、
ビーコン送信をキャンセルしたとき、自ノードの時刻が所定時刻である場合に、1ビーコン周期分だけ自ノードをアクティブモードとするステップを有することを特徴とする時刻同期方法。
【請求項6】
複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークのノードを構成する通信装置であって、
1ビーコン周期毎に乱数を用いてスロット数を生成するスロット数生成手段と、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かの判定を行う判定手段と、
前記判定手段でビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に前記通信装置の時刻情報を記載したビーコンを送信するビーコン送信制御手段と
を有することを特徴とする通信装置。
【請求項7】
請求項6記載の通信装置において、
ビーコン送信をキャンセルしたとき、前記通信装置の時刻が所定時刻である場合に、1ビーコン周期分だけ前記通信装置をアクティブモードとするアクティブモード設定手段を有することを特徴とする通信装置。
【請求項8】
請求項6または7記載の通信装置を有することを特徴とするノード。
【請求項9】
複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークのノードを構成するコンピュータを、
1ビーコン周期毎に乱数を用いてスロット数を生成するスロット数生成手段、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かの判定を行う判定手段、
前記判定手段でビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に前記コンピュータの時刻情報を記載したビーコンを送信するビーコン送信制御手段、
として機能させるためのプログラム。
【請求項10】
請求項9記載のプログラムにおいて、
前記コンピュータを、ビーコン送信をキャンセルしたとき、前記コンピュータの時刻が所定時刻である場合に、1ビーコン周期分だけ前記コンピュータをアクティブモードとするアクティブモード設定手段として更に機能させることを特徴とするプログラム。
【請求項11】
請求項9または10に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
発明の詳細な説明 【技術分野】
【0001】
本発明は、時刻同期方法及びそれに用いる通信装置及びノードに関する。より詳細には、本発明は、複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して時刻同期を行うアドホックネットワークの時刻同期方法及びそれに用いる通信装置及びノードに関する。
【背景技術】
【0002】
近年、アクセスポイントを必要とせず無線で接続できるパーソナルコンピュータ、PDA、センサノード等のノード(端末ともいう)のみで構成されるアドホックネットワークの開発が進められている。
【0003】
IEEE802.11プロトコル(非特許文献1参照)を用いたアドホックネットワークにおいては、各ノードはそれぞれの内部にもつ時刻をお互いにビーコンを送受信することにより更新していく。その結果、過渡状態の後に、全てのノードの時刻が一致して時刻同期が達成される。
図1にアドホックネットワークの一例の構成図を示す。同図中、アドホックネットワークは複数のノードA~Fから構成される。各ノードA~Fは具体的にはパーソナルコンピュータ、PDA、センサノード等の通信デバイスであり、各ノードは直接通信可能な半径R(通信範囲)のセルを有している。なお、半径Rはノード毎にある程度のバラツキを持っている。
【0004】
図1に示すようなアドホックネットワークを構成するノードのもつ時刻を制限された消費電力の下で自律分散的に同期させ維持するために、各ノードは以下に示す第1~第3の機能を有している。
【0005】
第1の機能は、図2に示すように、一定周期(例えば100msec)でアクティブモードとパワーセーブモードの2つのモードを繰り返す。図2において、アクティブモードに対応してコンテンションウィンドウが設定され、このコンテンションウィンドウはW+1(Wは例えば31)個のバックオフスロット(1バックオフスロットは例えば50μsec)に分割される。バックオフスロットは0からWまでの整数値であるスロット数により特定される。
【0006】
第2の機能は、アクティブモードの期間中に他のノードと競合を行い、勝ち残ったノードが自ノードの時刻を記載したビーコンを周りに送信し、他のノードはビーコン送信を行わない。
【0007】
第3の機能は、条件1~3が同時に満たされる時のみ、自ノードの時刻を受信したビーコンに記載されている時刻に更新することで時刻同期を行う。
(条件1)そのノードがその時アクティブモードの期間中である。
(条件2)到来するビーコンがコリジョンを生じない。
(条件3)受信したビーコンに記載されている時刻が、自ノードのもつ時刻より進んでいる(値が大きい)。
従来のアドホックネットワークにおけるビーコン送信ノードの選定方法について図3A、図3Bを用いて説明する。いま、ノードA、B、Cが互いに同一セル内に存在するものとする。図3Aに示すように、ノードA、B、Cはそれぞれビーコン周期毎にランダムにスロット数(ビーコン送信予定時刻)を生成する。この場合、ノードCが最小のスロット数(=2)を与えられ、ノードAのスロット数(=6)、ノードBのスロット数(=9)を与えられたとする。
【0008】
このとき、図3Bに示すように、ノードCは、このスロット数(=2)に対応する時刻においてビーコン送信を行い、ノードA、Bはこれを受信する。ビーコンを受信したノードA、Bは各々のスロット数(=6,9)に予定されているビーコン送信をキャンセルし、ビーコン送信を行わない。これにより、ビーコン送信ノードの選定はノード間による競合のみにより行われる。

【非特許文献1】IEEE Std.802.11 Wireless LAN Medium Access Control(MAC) and Physical Layer(PHY) specification,http://standards.ieee.org/grtieee802/download/802.11-1999.pdf
【発明の開示】
【発明が解決しようとする課題】
【0009】
ビーコン送信において問題となるのは、あるノードに同じタイミングで複数のビーコンが到来するとコリジョン(衝突)を生じ、いずれのビーコンも受信されないことである。この場合、その時点で当該ノードの時刻は更新されない。
【0010】
したがって、このようなコリジョンが頻繁に生じると時刻同期完了までの過渡状態が長時間継続し、通常の通信を開始することの妨げとなる。最近の研究では以上の問題を現実的に想定される条件下で解析しており、その結果、同期完了までに要する時間はネットワークを構成するノード数のべき乗に比例して増加し、ノード数が数十程度のアドホックネットワークにおいてさえ、現在の通信レートでは同期完了までに数十秒以上の時間を要するケースが生じることが判明している。
【0011】
このことから、IEEE802.11プロトコルによる大規模アドホックネットワークの構築において、現状のままではノード数が数百、数千ともなる大規模なネットワークの実現は時刻同期の点から困難であるという問題があった。
【0012】
本発明は、上記の点に鑑みなされたものであり、高い同期能力を得ることを可能とする時刻同期に係る技術を提供することを目的とする。
【課題を解決するための手段】
【0013】
上記の課題は、複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークにおいて各ノードが実行する時刻同期方法であって、
1ビーコン周期毎に乱数を用いてスロット数を生成する生成ステップと、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かを判定する判定ステップと、
前記判定ステップでビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に自ノードの時刻情報を記載したビーコンを送信するステップとを有することを特徴とする時刻同期方法により解決される。
【0014】
また、前記時刻同期方法において、前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、1ビーコン周期分だけ自ノードをアクティブモードとするステップを有することとしてもよい。また、前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、1ビーコン周期分だけ任意の確率で自ノードをアクティブモードまたはパワーセーブモードとするステップを有することとしてもよい。
【0015】
また、前記時刻同期方法において、前記判定ステップでの判定の結果に基づきビーコン送信をキャンセルした後、1ビーコン周期分だけ前記スロット数に基づく確率で自ノードをアクティブモードまたはパワーセーブモードとするステップを有することとしてもよく、ビーコン送信をキャンセルしたとき、自ノードの時刻が所定時刻である場合に、1ビーコン周期分だけ自ノードをアクティブモードとするステップを有することとしてもよい。
【0016】
また、上記の課題は、複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークのノードを構成する通信装置であって、
1ビーコン周期毎に乱数を用いてスロット数を生成するスロット数生成手段と、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かの判定を行う判定手段と、
前記判定手段でビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に前記通信装置の時刻情報を記載したビーコンを送信するビーコン送信制御手段とを有することを特徴とする通信装置によっても解決できる。
【0017】
また、本発明は、複数のノードが互いに無線接続されており、時刻情報を記載したビーコンをビーコン周期で送受信して各ノードの時刻同期を行うアドホックネットワークのノードを構成するコンピュータを、
1ビーコン周期毎に乱数を用いてスロット数を生成するスロット数生成手段、
前記スロット数に対応するビーコン送信時刻までに他ノードからのビーコンを受信していないとき、前記スロット数に基づいてビーコン送信をキャンセルするか否かの判定を行う判定手段、
前記判定手段でビーコン送信をキャンセルすると判定した場合にビーコン送信をキャンセルし、ビーコン送信をキャンセルしないと判定した場合に、前記ビーコン送信時刻に前記コンピュータの時刻情報を記載したビーコンを送信するビーコン送信制御手段、として機能させるためのプログラムとして構成することもできる。
【発明の効果】
【0018】
本発明によれば、無駄なビーコン送信を抑えコリジョンの発生頻度を低くでき、高い同期能力を得ることができる。
【図面の簡単な説明】
【0019】
【図1】アドホックネットワークの一例の構成図である。
【図2】ビーコン周期を説明するための図である。
【図3A】従来のアドホックネットワークにおけるビーコン送信ノードの選定方法を説明するための図である。
【図3B】従来のアドホックネットワークにおけるビーコン送信ノードの選定方法を説明するための図である。
【図4】本発明のアドホックネットワークを構成するノードの一実施形態のブロックである。
【図5】ビーコン送受信処理の第1実施形態のフローチャートである。
【図6A】本発明のアドホックネットワークにおけるビーコン送信ノードの選定方法を説明するための図である。
【図6B】本発明のアドホックネットワークにおけるビーコン送信ノードの選定方法を説明するための図である。
【図7】ビーコン送受信処理の第2実施形態のフローチャートである。
【図8】ビーコン送受信処理の第3実施形態のフローチャートである。
【図9】ビーコン送受信処理の第4実施形態のフローチャートである。
【図10】本発明のアドホックネットワークにおける時刻同期を説明するための図である。
【図11】本発明のアドホックネットワークにおける時刻同期を説明するための図である。
【符号の説明】
【0020】
10 ハードディスク装置
11 CPU
12 メモリ
13 入力装置
14 ディスプレイ装置
15 PCカードスロット
16 バス
20 無線ネットワークカード
21 インタフェース部
22 プロセッサ部
23 MAC処理部
24 変復調部
25 送受信部
26 アンテナ
【発明を実施するための最良の形態】
【0021】
以下、図面に基づいて本発明の実施形態について説明する。
【0022】
<ノード装置の構成>
図4は、本発明のアドホックネットワークを構成するノードの一実施形態のブロック図を示す。このノードはパーソナルコンピュータであり、ハードディスク装置10にはCPU11で実行する各種プログラムやデータ等が記憶される。CPU11はハードディスク装置10から読み出されるプログラムを実行する際に、メモリ12を作業領域として使用する。入力装置13はキーボードやマウス等のポインティングデバイスである。ディスプレイ装置14は表示を行う。上記のハードディスク装置10からPCカードスロット15までの各部はバス16で相互に接続されている。PCカードスロット15には通信装置としての無線ネットワークカード20が装着されてバス16に接続される。
【0023】
無線ネットワークカード20は、インタフェース部21、プロセッサ部22、MAC処理部23、変復調部24、送受信部25、及びアンテナ26を有している。インタフェース部21は、プロセッサ部22とMAC(媒体アクセス制御)処理部23をバス16に接続する。
【0024】
プロセッサ部22は、MAC処理部23を制御してMAC処理を実行させると共に、後述のビーコン送受信処理を実行する。このビーコン送受信処理を行うために、プロセッサ部22は記憶部22aを内蔵している。
【0025】
なお、プロセッサ部22と記憶部22aに代えて、CPUと、プログラムを格納したメモリとを有するコンピュータの構成を備えてもよい。この場合、メモリに格納されたプログラムをCPUが実行することにより、プロセッサ部22が実行する後述する処理と同様の処理が実行される。また、ノードを構成する端末等のコンピュータが、当該プログラムを実行することによりプロセッサ部22が実行する処理と同様の処理を実行することとしてもよい。
【0026】
上記プログラムは、外部の記録媒体(可搬メモリ等)から上記メモリに格納するようにしてもよいし、ネットワークを介してダウンロードすることとしてもよい。なお、プロセッサ部22と記憶部22aに代えて、CPUと、プログラムを格納したメモリとを備える場合、無線ネットワークカード20自身をコンピュータと称することもできる。
【0027】
MAC処理部23は、IEEE802.11で規定されるMAC(媒体アクセス制御)処理を実行する。変復調部24はIEEE802.11で規定されるDSSB(Direct Sequence Spread Spectrum)やCCK(Complementzary Code Keying)やOFDM(Orthogonal Frequency Division Mu1tip1exing:直交周波数分割多重)変調方式による変復調を行う。送受信部25はアンテナ26を用いて送受信を行う。
【0028】
<第1実施形態>
図5は、アドホックネットワークを構成するノードに装着された無線ネットワークカード20のプロセッサ部22が実行するビーコン送受信処理の第1実施形態のフローチャートを示す。同図中、プロセッサ部22は、1ビーコン周期毎に実行されるステップS11で乱数等を用いて値が0~31のスロット数を生成し、ステップS12で送受信を開始する。
【0029】
ステップS13で、プロセッサ部22は、ビーコンを送信する時刻までにノードがコリジョンの発生なく他のノードからビーコンを受信したか否かを判別する。ノードがビーコンを受信していない場合にはステップS14に進んで、プロセッサ部22は、ビーコン送信の足切り判定を行う。足切り判定では、ステップS11で生成したスロット数が予め記憶部22aに設定された閾値(例えば1)未満であるか否かの判定が行われる。スロット数が閾値未満であれば足切りは回避され、スロット数が閾値以上である場合に足切りが行われる。
【0030】
ビーコン送信の足切りが回避された場合は、ステップS15で、ノードは自ノードの時刻を記載したビーコンの送信を行い、ステップS16で1ビーコン周期分だけアクティブモードを持続してステップS11に進む。足切りが行なわれる場合は、ノードはステップS17でビーコン送信をキャンセルし、ステップS18で1ビーコン周期分だけアクティブモードを持続してステップS11に進む。
【0031】
一方、ステップS13で、ノードがビーコンを受信している場合にはステップS19でビーコン送信をキャンセルし、ステップS20で1ビーコン周期分だけパワーセーブモードとなり、その後アクティブモードに戻ってステップS11に進む。
【0032】
本実施形態のアドホックネットワークにおけるビーコン送信ノードの選定方法について図6A、図6Bを用いて説明する。図1に示すように、ノードA、B、Cが互いに同一セル内に存在するものとする。図6Aに示すように、ノードA、B、Cはそれぞれビーコン周期毎にランダムにスロット数(ビーコン送信予定時刻)を生成する。この場合、ノードCが最小のスロット数(=2)を与えられ、ノードAのスロット数(=6)、ノードBのスロット数(=9)を与えられたとする。
【0033】
このとき、ノードA、B、C間における競合後、そのセルにおけるノードのうち最小のスロット数をもっているノードCがビーコン送信ノードに選出される。つまり、ノードA、B、Cの中で、他からビーコンを受信する前に最も早くビーコン送信時刻になるのがノードCである。
【0034】
このノードCは、ビーコンを送信する前に、そのスロット数が閾値(例えば1)を越えているか否かをチェックする(図6B)。スロット数が閾値未満であれば(すなわち、スロット数=0であれば)、予定通りビーコンを送信し、その後そのノードCはアクティブモードを持続する。一方、スロット数が閾値以上であれば、そのノードCがビーコンを送信することは取り止め、同時にそのノードCは当初の予定通りアクティブモードを持続させる。上記の付加的操作を閾値によるビーコン送信の足切り(キャンセル)判定と呼んでいる。
【0035】
本実施形態では、ビーコン送信の足切りを行うことによってビーコン送信ノードに選出されるノード数を減少させることにより、コリジョンの発生頻度を低くすることができ、時刻同期が完了するまでの時間を短縮でき、高い同期能力を得ることができる。
【0036】
<第2実施形態>
第1実施形態では、足切り判定により当初予定していたビーコン送信を取り止めたノードは、その後、自動的にアクティブモードを持続する。しかし、足切りを受けるノード数が多くなると、それだけアクティブモードを持続するノード数も多くなってしまい、アドホックネットワーク全体のノードにおけるエネルギー消費が増大する。このため、ノードのエネルギー消費を抑える観点から工夫した第2、第3実施形態について説明する。
【0037】
図7は、アドホックネットワークを構成するノードに装着された無線ネットワークカード20のプロセッサ部22が実行するビーコン送受信処理の第2実施形態のフローチャートを示す。同図中、プロセッサ部22は、1ビーコン周期毎に実行されるステップS31で乱数等を用いて値が0~31のスロット数を生成し、ステップS32で送受信を開始する。
【0038】
ステップS33で、プロセッサ部22は、ビーコンを送信する時刻までにノードがコリジョンの発生なく他のノードからビーコンを受信したか否かを判別する。ノードがビーコンを受信していない場合にはステップS34に進んで、プロセッサ部22は、ビーコン送信の足切り判定を行う。足切り判定では、ステップS31で生成したスロット数が予め記憶部22aに設定された閾値(例えば1)未満であるか否かの判定が行われる。スロット数が閾値未満であれば足切りは回避され、スロット数が閾値以上である場合に足切りが行われる。
【0039】
ビーコン送信の足切りが回避された場合は、ステップS35で、ノードは自ノードの時刻を記載したビーコンの送信を行い、ステップS36で1ビーコン周期分だけアクティブモードを持続してステップS31に進む。足切りが行なわれる場合は、ノードはステップS37でビーコン送信をキャンセルし、ステップS38で乱数を用いて所定の確率(例えば90%)でアクティブモードを選択し、残りの確率(例えば10%)でパワーセーブモードを選択し、1ビーコン周期分だけ選択したモードを持続し、その後アクティブモードに戻ってステップS31に進む。
【0040】
一方、ステップS33で、ノードがビーコンを受信している場合にはステップS39でビーコン送信をキャンセルし、ステップS40で1ビーコン周期分だけパワーセーブモードとなり、その後アクティブモードに戻ってステップS31に進む。
【0041】
これによって、アドホックネットワーク全体のノードにおけるエネルギー消費の増大を低減することができる。
【0042】
<第3実施形態>
図8は、アドホックネットワークを構成するノードに装着された無線ネットワークカード20のプロセッサ部22が実行するビーコン送受信処理の第3実施形態のフローチャートを示す。同図中、プロセッサ部22は、1ビーコン周期毎に実行されるステップS51で乱数等を用いて値が0~31のスロット数を生成し、ステップS52で送受信を開始する。
【0043】
ステップS53で、プロセッサ部22は、ビーコンを送信する時刻までにノードがコリジョンの発生なく他のノードからビーコンを受信したか否かを判別する。ノードがビーコンを受信していない場合にはステップS54に進んで、プロセッサ部22は、ビーコン送信の足切り判定を行う。足切り判定では、ステップS51で生成したスロット数が予め記憶部22aに設定された閾値(例えば1)未満であるか否かの判定が行われる。スロット数が閾値未満であれば足切りは回避され、スロット数が閾値以上である場合に足切りが行われる。
【0044】
ビーコン送信の足切りが回避された場合は、ステップS55で、ノードは自ノードの時刻を記載したビーコンの送信を行い、ステップS56で1ビーコン周期分だけアクティブモードを持続してステップS51に進む。足切りが行なわれる場合は、ノードはステップS57でビーコン送信をキャンセルし、ステップS58でスロット数が予め記憶部22aに設定された一定値(例えば30)以下か否かを判別する。スロット数が一定値以下の場合は、ステップS56に進んで1ビーコン周期分だけアクティブモードを持続してステップS51に進む。スロット数が一定値を超える場合は、ステップS59に進んで1ビーコン周期分だけパワーセーブモードとなり、その後アクティブモードに戻ってステップS51に進む。
【0045】
一方、ステップS53で、ノードがビーコンを受信している場合にはステップS60でビーコン送信をキャンセルし、ステップS61で1ビーコン周期分だけパワーセーブモードとなり、その後アクティブモードに戻ってステップS51に進む。
【0046】
上記第2実施形態では足切り判定の結果に基づき送信キャンセルを行った場合に乱数を用いてアクティブモードかパワーセーブモードかを選択しているが、第3実施形態では元々乱数により発生したスロット数を利用してアクティブモードかパワーセーブモードかを選択しており、その効果は実質的に等価である。
【0047】
<第4実施形態>
図9は、アドホックネットワークを構成するノードに装着された無線ネットワークカード20のプロセッサ部22が実行するビーコン送受信処理の第4実施形態のフローチャートを示す。同図中、プロセッサ部22は、1ビーコン周期毎に実行されるステップS71で乱数等を用いて値が0~31のスロット数を生成し、ステップS72で送受信を開始する。
【0048】
ステップS73で、プロセッサ部22は、ビーコンを送信する時刻までにノードがコリジョンの発生なく他のノードからビーコンを受信したか否かを判別する。ノードがビーコンを受信していない場合にはステップS74に進んで、プロセッサ部22は、ビーコン送信の足切り判定を行う。足切り判定では、ステップS71で生成したスロット数が予め記憶部22aに設定された閾値(例えば1)未満であるか否かの判定が行われる。スロット数が閾値未満であれば足切りは回避され、スロット数が閾値以上である場合に足切りが行われる。
【0049】
ビーコン送信の足切りが回避された場合は、ステップS75で、ノードは自ノードの時刻を記載したビーコンの送信を行い、ステップS76で1ビーコン周期分だけアクティブモードを持続してステップS71に進む。足切りが行なわれる場合は、ノードはステップS77でビーコン送信をキャンセルしたのち、ステップS80に進む。
【0050】
一方、ステップS73でノードがビーコンを受信している場合にはステップS79でビーコン送信をキャンセルしたのち、ステップS80に進む。ステップS80ではプロセッサ部22は、ノードの時刻が予め記憶部22aに設定された所定時刻(例えば整数秒となる時刻)であるか否かを判別する。ノードの時刻が所定時刻である場合はステップS81で1ビーコン周期分だけアクティブモードを持続してステップS71に進む。ノードの時刻が所定時刻ではない場合はステップS82で1ビーコン周期分だけパワーセーブモードとなり、その後アクティブモードに戻ってステップS71に進む。
【0051】
これにより、各ノードは内部に保持する時刻が整数秒となる毎に1ビーコン周期分だけアクティブモードを持続することになり、この間にビーコン送信ノードから送信されたビーコンを受信して、一斉に時刻同期が行われる。
【0052】
なお、図7、図8の実施形態においても、図9におけるステップS80~S82を追加しても良いことはもちろんである。
【0053】
図10は、一辺が5Rの正方形の領域AR1に36個のノードをランダムに固定配置した場合を想定している。なお、Rは通信範囲の半径に対応する正規化された距離である。各ノードは一様に通信範囲Rを持つものとする。ここで、初期において領域AR1内の各ノードは相互にビーコンを送受信し、全体の時刻同期が得られ1つのアドホックネットワーク(先のネットワーク)を構成しているものとする。
【0054】
そのとき、領域AR1の任意の位置に、他のネットワークに属しているノードND1が速やかに参入したものとする。ここで、このノードND1のもつ時刻は、先のネットワークを構成するノードの時刻より進んでおり(値が大きい)、かつ、そのビーコン周期におけるアクティブモードの位相は先のネットワークのビーコン周期におけるアクティブモードの位相に対し大略逆位相であったとする。
【0055】
ここで、参入したノードND1は、その通信範囲R内に存在するアクティブモードのノードの時刻を同期させる。その時刻同期の伝播は通信範囲R内でアクティブモードを持続している少数のノードを介して行われるので、ビーコン周期(100ms)のオーダーのゆっくりとしたタイムスケールで行われる。
【0056】
従来のアドホックネットワークを用いた場合、第1段階で白抜きの矢印で示すような方向で領域AR1の境界に沿って時刻同期の伝搬が速やかに進行し、その後、第2段階で領域AR1の内側に残ったノードが長い時間をかけて徐々に時刻同期していくことが認められている。
【0057】
第1段階が生じる理由は、ランダムなスロット数生成で最小となったものが時刻伝播を担うノード(ビーコン送信ノード)として決定されるが、その際に領域AR1の境界付近では領域AR1外にノードがないので相対的なノードの密度が疎らとなり、境界付近のノードが比較的頻繁にビーコン送信ノードに選出されるためである。図10では第2段階における進んだ時刻のノードを白丸で示し、遅れた時刻のノードを黒丸で示す。
【0058】
これに対し、本発明によると、第1段階の過程における時刻同期の伝搬は従来よりも速くなるが、それほど大きな差ではない。しかし、第2段階において従来とは異なる同期過程を示す。その特徴は領域AR1の中央部分のノードは、あまり同期が進展しない時点と、逆に急激に同期が進行する時点を繰り返すことである。その結果、全体の同期の終了に要する時間が従来に比べ、大幅に短縮される。その理由は以下のメカニズムから説明される。
(A)領域AR1の境界部分のノードがビーコン送信の足切りを受けるために、領域AR1の中央部分のノードでビーコンのコリジョンの発生率は低くなる。
(B)足切りの効果が強く現れる場合がしばしば生じ、足切りの効果が強く現れたビーコン周期において領域AR1の境界部分のノードはほとんど全てが足切りを受ける場合が生じる。このとき、領域AR1の境界部分のノードから中央部分のノードにビーコンが到来せず、その時点では同期は進行しない。
(C)領域AR1の中央部分の未だ同期を達成していないノードにおいては、スロット生成時に足切りをクリアできず、全てのノードが足切りを受ける場合が時々生じる。
(D)上記(C)が生じた直後に、領域AR1の中央部分の同期を達成していないノードは全てアクティブモードになっているので、上記(A)と同様に領域AR1の境界部分のノードからビーコンがコリジョンなく到来すると、領域AR1の中央部分の全てのノードが一気に同期を完了する。
【0059】
図10は、ネットワークの空間的広がりを考慮した例であるが、図11に示すように空間的に密集したノード配置の場合においても、同様のメカニズムによって大幅な時刻同期の時間短縮が認められる。
【0060】
図11においては、領域AR2内に黒丸で示す複数のノードが存在し、領域AR3内に白丸で示す複数のノードが存在する。黒丸のノードが直接通信可能なセルSL2と白丸のノードが直接通信可能なセルSL3とは一部重なり、重なった部分に黒丸のノードND2が配置されている。また、白丸のノードは黒丸のノードより時刻が進んでおり、黒丸のノードと白丸のノードはビーコン周期におけるアクティブモードの位相が大略逆位相であったとする。
【0061】
この場合も、黒丸のノードND2がビーコン送信足切りまたはビーコン送信した後に1ビーコン周期分だけアクティブモードを持続するときに、白丸のノードからのビーコンを受信して速やかに時刻同期を行い、その後、同様にして、ノードND2からのビーコン送信により領域AR2内に黒丸のノードが順次時刻同期を行う。これによって、従来に比べ大幅な時刻同期の時間短縮がなされる。
【0062】
本発明の第1乃至第3実施形態における時刻同期の時間短縮は、上記(C)、(D)のメカニズムが大きく貢献している。上記(C)、(D)では、同期を達成していないノードが全てアクティブとなる状態が確率的に生起するが、第4実施形態では、同期を達成していないノードが全てアクティブとなる状態が所定時刻毎に一定周期で生じるため、さらに同期に要する時間を短縮することができる。
【0063】
消費エネルギーに関しては、同期が進行している過渡状態時の各ノードのパケット送信およびアクティブモードを持続するのに要する第1消費エネルギーと、同期が完了して定常状態にある時の各ノードのパケット送信およびアクティブモードを持続するのに要する第2消費エネルギーについて考える必要がある。
【0064】
本発明の第1実施形態においては、第1消費エネルギーは従来と比べ単位時間当たりの消費エネルギーが若干高くなる。ところが、過渡状態の継続時間は従来と比べかなり短くなるので、第1消費エネルギーの総計は結局、本発明の方が従来よりも下まわる。一方、第2消費エネルギーは、通信範囲Rが相当に小さい場合を除き、従来と本発明のそれには有意な差がみられない。したがって、全消費エネルギーにおいて、本発明は従来よりも省エネルギー性を持つことがわかる。また、これらの傾向は第2、第3実施形態を導入する場合により強められる。
【0065】
なお、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において種々の変更及び応用が可能である。
【0066】
本国際出願は2005年11月4日に出願された日本国特許出願第2005-320573号に基づく優先権を主張するものであり、その全内容を本国際出願に援用する。
図面
【図1】
0
【図2】
1
【図3A】
2
【図3B】
3
【図4】
4
【図5】
5
【図6A】
6
【図6B】
7
【図7】
8
【図8】
9
【図9】
10
【図10】
11
【図11】
12