(57)【特許請求の範囲】
【請求項１】
第１の送受信機器を第２の送受信機器に同期させるための装置であって、
前記第２の送受信機器からの同期信号（１４０）を受信および検出するようにされた受信機（１１０）と、
前記第２の送受信機器からの前記同期信号（１４０）と同期した同期信号（１４０）を同期期間後に送信する送信機（１３０）と、
処理装置（１２０）と
を具備し、該処理装置は、
所定の非リスニング時間（Ｔ，Ｔ＋Ｔrefr）後に時間についての所与の第１の関数（Φ（ｔ））に従って内部信号値（Φ）を増大させ、前記受信機（１１０）から検出信号（１５０）を受信したら第２の関数（ΔΦ（Φ））に従って前記信号値（Φ）を増大させ、
当該装置が受信期間（１６４）に関連する第１の制御状態（１７０）にあるときに前記内部信号値（Φ）を閾値（Φthreshold）と比較し、前記内部信号値が該閾値（Φthreshold）に等しくなったときに当該内部信号値（Φ）をリセットし、
前記内部信号値が前記閾値（Φthreshold）に等しくなったとき（１７２）に期間変数（ｎｅｘｔ）に基づいて前記受信期間（１６４）を繰り返す（１７４）かどうかを決定し、
前記受信期間（１６４）を繰り返す場合には、異なる非リスニング時間（Ｔrefr）を使用してまたは非リスニング時間なしに前記同期信号（１４０）を送信することなく、その繰り返された受信期間において前記内部信号値（Φ）を増大させ始めるようにされているものであるか、
または、
前記送信機（１３０）を制御して、前記内部信号値（Φ）が前記閾値（Φthreshold）に等しくなって（１７２）前記処理装置が前記送信期間へ移行することを決定したときに到達する状態である前記送信期間（１６２）に関連した第２の制御状態（１８０）において、前記送信機（１３０）が前記同期信号（１４０）を送信するようにし、
前記同期信号（１４０）の送信が終了（１８２）した後に始まる状態である前記送信期間（１６２）に関連した第３の制御状態（１９０）において、ゼロより大きくかつ前記送信期間（１６２）の継続時間（Ｔ）より短い受信機待機時間（ＴwaitRX，Ｔdec）の間だけ待機し、
前記期間変数（ｎｅｘｔ）に基づいて前記送信モード（１６２）を繰り返す（１９４）かどうかを決定し、
前記送信モード（１６２）を繰り返す場合には、前記送信機（１３０）を制御して、前記送信機（１３０）が、リスニング期間（１６４）を合間に挟むことなく、前記第２の制御状態（１８０）において前記同期信号（１４０）を送信するようにするようにされているものである、送受信機器を同期させるための装置。
【請求項２】
前記処理装置（１２０）は、前記受信機（１１０）を制御して、第４の制御状態（３２０）において、ゼロより大きくかつ受信期間（１６４）の継続時間（Ｔ）より短い所与の不応時間（Ｔrefr）の間、前記第２の送受信機器から前記同期信号（１４０）を受信および／または検出することができる状態に前記受信機（１１０）があるようにし、前記不応時間が経過したとき（３２２）に前記第１の制御状態（１７０）へ移行するようになっているものである、請求項１に記載の送受信機器を同期させるための装置。
【請求項３】
前記処理装置（１２０）は、前記送信機（１３０）を制御して、前記内部信号値（Φ）が前記閾値（Φthreshold）に等しくなったときに第１の制御状態（１７０）にある前記処理装置（１２０）が前記期間変数（ｎｅｘｔ）に基づいて前記送信期間（１６２）へ移行することを決定したときまたは前記第３の制御状態（１９０）にある前記処理装置（１２０）が前記送信期間（１６２）を繰り返すことを決定したときに到達する状態である前記送信期間（１６２）に関連した第５の制御状態（３１０）において、ゼロより大きく前記送信期間（１６２）の前記継続時間（Ｔ）より短い送信機待機時間（ＴwaitTX，Ｔwait）の間だけ、前記送信機（１３０）が待機するようにされているものである、請求項１または２に記載の送受信機器を同期させるための装置。
【請求項４】
前記送信期間（１６２）の前記継続時間（Ｔ）は前記受信期間（１６４）の継続時間（Ｔ）に等しい、請求項１乃至３のいずれかに記載の送受信機器を同期させるための装置。
【請求項５】
前記処理装置（１２０）は、
前記受信機（１１０）を制御して、前記処理装置（１２０）が前記受信期間（１６４）を繰り返すことを決めたときに、前記受信機（１１０）が前記同期信号（１４０）の進行中の受信を完了して前記同期信号を検出し、または前記同期信号の進行中の検出を完了するようにし、
再び前記第１の制御状態（１７０）にあるときにのみ前記内部信号値をインクリメントするように働くものである、請求項１乃至４のいずれかに記載の送受信機器を同期させるための装置。
【請求項６】
前記処理装置（１２０）は、前記受信機（１１０）を制御して、前記処理装置（１２０）が前記受信期間（１６４）から前記送信期間（１６２）へ移行する（１７６）ことを決めたときに、前記受信機（１１０）が前記同期信号の検出を開始しないようにする、または前記同期信号の進行中の検出を中止するように働くものである、請求項１乃至５のいずれかに記載の送受信機器を同期させるための装置。
【請求項７】
前記処理装置（１２０）は、第３の関数に基づいて前記期間変数（ｎｅｘｔ）を決定するように働くものである、請求項１乃至６のいずれかに記載の送受信機器を同期させるための装置。
【請求項８】
前記期間変数（ｎｅｘｔ）は第１の値（ＴX）または第２の値（ＲX）を有しており、
前記処理装置（１２０）は、
前記期間変数（ｎｅｘｔ）が前記第１の値（ＴX）を有する場合には、前記受信期間（１６４）から前記送信期間（１６２）へ移行し（１７６）、もしくは、前記送信期間（１６２）を繰り返す（１９４）ようにされているか、
または、
前記期間変数（ｎｅｘｔ）が前記第２の値（ＲX）を有する場合には、前記送信期間（１６２）から前記受信期間（１６４）へ移行し（１９６）、もしくは前記受信期間（１６４）を繰り返す（１７４）ようにされているものである、請求項１乃至７のいずれかに記載の送受信機器を同期させるための装置。
【請求項９】
前記処理装置（１２０）は前記期間変数（ｎｅｘｔ）を第３の関数に基づいて決定する働きをし、前記第３の関数は、直交系列の集合、好ましくはゴールド系列の集合からの疑似ランダム系列であり、第１の値（ＴX）と第２の値（ＲX）の系列を与えるものである、請求項８に記載の送受信機器を同期させるための装置。
【請求項１０】
前記処理装置（１２０）は、前記期間変数（ｎｅｘｔ）を第３の関数に基づいて決定する働きをし、前記第３の関数は、ランダム関数であって、確率過程に基づいて前記期間変数（ｎｅｘｔ）の前記第１の値（ＴX）および前記第２の値（ＲX）を決定する関数である、請求項８に記載の送受信機器を同期させるための装置。
【請求項１１】
前記処理装置（１２０）は、前記受信期間（１６４）の間に前記内部信号値（Φ）が前記第２の関数（ΔΦ（Φ））に基づいて増大したかどうかを追跡し、所定数の連続する受信期間の間に前記内部信号値（Φ）が増大したときには前記期間変数（ｎｅｘｔ）を前記第２の値（ＲX）に設定するようにされているものである、請求項８乃至１０のいずれかに記載の送受信機器を同期させるための装置。
【請求項１２】
前記内部信号値（Φ）が前記第２の関数（ΔΦ（Φ））に基づいて増大することなく前記所定数の連続する受信期間が経過した後に、前記期間変数（ｎｅｘｔ）の第１の値（ＴX）または第２の値（ＲX）がランダム関数に基づいて決定されるものである、請求項１１に記載の送受信機器を同期させるための装置。
【請求項１３】
前記受信機（１１０）は、通信プロトコルに基づくフレームの所定部分を受信し、前記フレームの前記所定部分（８４０）を前記同期信号（１４０）として検出する働きをするものである、請求項１乃至１２のいずれかに記載の送受信機器を同期させるための装置。
【請求項１４】
前記通信プロトコルはＷＬＡＮ（wireless local area network）プロトコルであり、前記フレームの前記所定部分（８４０）は前記フレームのプリアンブル（８１０）の一部分である、請求項１３に記載の送受信機器を同期させるための装置。
【請求項１５】
前記フレームは前記送信期間（１６２）の前記継続時間（Ｔ）に等しい所定の長さを有している、請求項１４に記載の送受信機器を同期させるための装置。
【請求項１６】
前記フレームはＥＲＰ・ＯＦＤＭ（Enhanced Rate PHY Orthogonal Frequency Division Multiplexing）版８０２．１１ＷＬＡＮ通信プロトコルに従って実現され、前記フレームと前記送信期間の前記継続時間は、各ＯＦＤＭシンボルが４μｓの継続時間を有するＯＦＤＭシンボルの数をＮDATAとし、前記プリアンブル（８１０）の継続時間を１６μｓとし、ヘッダ（８２０）の継続時間を４μｓとしたときに、次の式、
１６μｓ＋４μｓ＋ＮDATA・４μｓ＝Ｔ
に基づいて定義され、
前記プリアンブル（８１０）の継続時間８μｓを有する前半部分（８４０）は前記同期信号（１４０）として利用される、請求項１５に記載の送受信機器を同期させるための装置。
【請求項１７】
第１の送受信機器を同期させるための請求項１乃至１６のいずれかに記載された装置と、
前記同期信号（１４０）のタイミングに基づいてデータ送信またはデータ受信を制御するための制御装置と
を具備する送受信機器。
【請求項１８】
第１の送受信機器を第２の送受信機器に同期させるための方法であって、
所定の非リスニング時間（Ｔ，Ｔ＋Ｔrefr）後に、受信期間（１６４）に関連した第１の制御状態（１７０）において、時間上の所与の第１の関数（Φ（ｔ））に従って内部信号値（Φ）を増大させるステップと、
同期信号（１４０）を受信および検出するステップと、
前記第１の制御状態（１７０）にある間に前記同期信号（１４０）を検出したとき第２の関数（ΔΦ（Φ））に従って前記内部信号値（Φ）を増大させるステップと、
前記第１の制御状態（１７０）にある間に前記内部信号値（Φ）を所与の閾値（Φthreshold）と比較するステップと、
前記内部信号値（Φ）が前記閾値（Φthreshold）に等しくなったときに期間変数（ｎｅｘｔ）に基づいて前記受信期間（１６４）を繰り返す（１７４）かどうかを決定し、前記内部信号値（Φ）が前記閾値（Φthreshold）に等しくなったときに前記内部信号値（Φ）をリセットするステップと、
前記受信期間（１６４）を繰り返す場合には、異なる非リスニング時間（Ｔrefr）を使用してまたは非リスニング時間なしに前記同期信号（１４０）を送信することなく、繰り返された受信期間において前記内部信号値（Φ）を増大させ始めるステップと
を含むものであるか、または、
前記送信期間（１６２）に関連した第２の制御状態（１８０）において前記同期信号（１４０）を送信するステップと、
前記同期信号（１４０）の送信が終了（１８２）した後に始まる状態である前記送信期間（１６２）に関連した第３の制御状態（１９０）において、ゼロより大きくかつ前記送信期間（１６２）の継続時間（Ｔ）より短い受信機待機時間（ＴwaitRX，Ｔdec）の間だけ待機するステップと、
前記受信機待機時間が終わったときに前記期間変数（ｎｅｘｔ）に基づいて前記送信期間（１６２）を繰り返す（１９４）かどうかを決定するステップと、
前記送信期間（１６２）を繰り返す場合には、リスニング期間を合間に挟むことなく、繰り返された送信期間（１６２）において前記同期信号（１４０）の送信を実行するステップと
を含んでなる、送受信機器を同期させるための方法。
【請求項１９】
コンピュータ上で走らせたときに請求項１８に記載された方法を実行するためのプログラムコードを有するコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの同期、特に自己組織化ネットワークの同期の技術に関する。
【背景技術】
【０００２】
近年、日々、アイテムは無線能力を獲得し、他の電子機器との無線通信はますますユビキタスなものとなりつつある。この流れが、アドホック（ad hoc）およびピアツーピア（peer-to-peer）ネットワークの分野における研究を促進し、特に自己組織化ネットワークに対する関心をますます高めている。これらのシステムは制御が比較的難しいが、驚くべき利点をもたらす。その理由は、それらは明瞭なルールの集合によって支配され、多数のノードが何とかこれらのルールを何らかの態様で利用して新しい挙動を生み出すからである。これらの特性を利用するうまく設計された分散型アルゴリズムとは、フレキシブル、スケーラブル、ローバストであることが分かり、そしてトポロジーの変化にうまく適応するものとなる。
【０００３】
実際、自己組織化システムは広く見られる。２、３の例を挙げれば、ヒトの心筋細胞、蟻、小魚の群れなどがある。心臓ペースメーカのおかげで、心臓は周期的に脈動することが可能であり、身体運動に起因する急な酸素要求に対応することも可能である。蟻は局所的に集められた情報を集約することが可能で、それは食物を効率的に探して獲得するのに役立つ。小魚の群れは一体となって泳ぎ、外部の刺激に迅速に反応することが可能である。この習性は、小魚の群れを捕食者に対して一匹の大型魚のように見せ、彼らへの攻撃を抑止する効果を生む（非特許文献１参照）。
【０００４】
自己組織化システムの１つの興味深い実例は東南アジアの河川の川岸に観察される。明け方になると、ホタルが川岸に沿った木々に集まり、一斉に同期した点滅を始める。それはあたかも木全体が完全に同期して点滅しているように見える。同様に、ヒトの心拍は集中管理スキームには依存しないが、同期して周期的に脈動する心臓細胞に頼っている。同期収束の理論的なフレームワークはMirolloとStrogatzによって１９９０年に公表されている（非特許文献２参照）。これについては後でより詳しく説明される。このモデルはホタルが完全メッシュ状ネットワークを形成し、パルスでコミニュケーションし合うことを仮定している。
【０００５】
このような同期化を記述するための数学的なアプローチは“パルス結合発振器（pulse-coupled oscillators）”の概念に基づく。この術語は、時間的に周期的に発振し、各発振を完了するごとに相互作用するシステム指す。この相互作用は隣接する発振器によって感知されるパルスの形をとる。これらのシステムは、完全同期からパタン形成に至る範囲の異なる挙動を示すことが知られている。
【０００６】
次に、パルス結合発振器同士の間で時間的同期化がいかに成し遂げられるかについて説明する。まず最初に、これらの発振器に関連する数学的モデルについて説明する。次にどのように２つ以上のパルス結合発振器が同期して１つのものとしてパルス発振することができるかについて説明する。
【０００７】
明瞭な数学的モデルまたは数学的表現として、パルス結合発振器をその位相関数（phase function）Φ（ｔ）のみによって記述する。この関数は閾値Φthresholdに達するまで時間の経過とともに線形に時間的に変化する。閾値Φthresholdに達すると、発振器は発火（fire）し、その位相をリセットする。全く他の発振器と結合しなければ、それはＴに等しい周期で発火する。以下の記述では、この周期は位相関数周期（phase function period）Ｔまたは発振器周期（oscillator period）Ｔと呼ばれる。
【０００８】
この関数の時間的変化から、これらの発振器は積分発火（型）発振器（integrate-and-fire oscillators）とも呼ばれる。図１２Ａに単独の発振器の位相関数の時間発展を示す。
【０００９】
図１２Ｂは積分発火型発振器の第２の表現として分円図（pie chart）を示したものである。発振器は図１２Ｂにおいて円上を反時計回りに回ると考えることができる。円上の各ポジションはリスニング状態（Ｌｉｓｔｅｎ）における位相Φ（ｔ）を表し、円が完成した後に発火する。位相は内部時計と見なすこともできる。
【００１０】
このモデルは生物学的なパルス結合発振器の挙動を近似する。発火の瞬間は、ホタルの発光、ニューロンの電気パルスまたはノード（node）の同期信号（synchronization signal）の発信に相当する。次に、斯かる発振器がパルスを受け取ったときにそれらの位相関数を修正することによっていかに同期することが可能かについて見ることにする。
【００１１】
位相関数のみに基づいて２つの同種の発振器は２、３周期の間にそれらの発火時点を同期させることが可能である。これを遂行するため、発振器は別の積分発火型発振器からのパルスを受け取ったときに自己の位相を修正する。
【００１２】
図１３Ａに２つの発振器がこのスキームを利用してどのように同期することができるかを示す。時刻０では発振器は同期していない。それらの初期位相Φ1およびΦ2は０からΦthresholdまでの間にランダムに分布している。このとき、各発振器は時間の経過とともに位相をそれが閾値に到達するまで線形にインクリメント（increment）する。時刻ｔ1で発振器１は閾値に到達する。そこで発振器１はパルスを発火し自己の位相をリセットする。発振器（発振器１および発振器２）が結合しているときには、発振器２は自己の位相をインクリメントする。その際の増分はＰＲＣ（Phase Return Curve）Δ（Φ）で決まる。この関数については後述する。時刻ｔ2で発振器２が発火し、それに応えて発振器１は自己の位相を増大させる。発振器１の発火により発振器２が同じ時刻に発火するｔ5までこのスキームは継続される。この時点（ｔ5）で、両方の発振器は同期化される。時刻ｔ6＝ｔ5＋Ｔでは、発振器は両方とも同時に発火する。
【００１３】
図１３Ｂに、２つの積分発火型発振器がそれぞれ位相Φ1とΦ2を有するシナリオに対する分円図を示す。発振器は発火するとすぐにパルスを発信する。
【００１４】
最初は両方の発振器は独立または孤立している。それらの位相Φは時間の経過とともに線形にインクリメントする。互いに結合している場合、１つの発振器の発火を契機に他方の発振器はその位相を現時点の位相に依存するΔΦ（Φ）だけ次のように即座にインクリメントする。
Φ→Φ＋ΔΦ（Φ）
【００１５】
図１３Ｂに例示的な位相の増分（インクリメント）を符号１３１０、１３２０および１３３０で示す。位相増分１３３０は図１３Ａにおける時刻ｔ5の状況を示している。その状況では、第１の発振器が発火し（Φ1（ｔ5）＝Φthreshold）、その結果、第２の発振器は第１の発振器のパルスを受信すると同時にその位相（Φ2（ｔ5）＜Φthreshold）をインクリメントする。インクリメント実行後、第２の発振器の位相もΦthresholdに等しくなる。
【００１６】
非特許文献２に示されているように、この明瞭なタイプの相互作用は初期状態が何であれ結果的に同期化をもたらす。それを遂行するため、位相増分Δ（Φ）は関数ｆ（Φ）に基づいて選ばれる必要がある。ここでｆ（Φ）は発振器が同期するために下に凹形になっている必要がある。ここで、選ばれた関数は次のようなものである。
【数１】
0004418481.tif 000002
【００１７】
各発振器ごとに、関数ｆは振幅の役割を果たす。発振器がパルスを受け取ると、その発振器はε（＞０）だけその振幅を増大させる。これは位相増分Δ（Φ）に等しい。図１３Ｃは、ｂ＝３およびε＝０．１に対して、位相応答曲線ＰＲＣから位相増分Δ（Φ）がどのように得られるかを示している（いまの場合、Φthreshold＝１）。
【００１８】
図１３Ｄに、積分発火型発振器の挙動を記述する２つの関数の一例を示す。符号１３５０は位相Φ（ｔ）の積分または増加関数を示す。符号１３６０は線形位相応答曲線ΔΦ（Φ）を示す。この明瞭なモデルだけに基づいて、２つ以上の同種の発振器は２、３周期内に発火点を同期させることが可能である。
【００１９】
Δφは位相応答曲線（ＰＲＣ：Phase Response Curve）で決まり、ＰＲＣは非特許文献２にあるように以下のように線形になるように選ばれた。
【数２】
0004418481.tif 000003
上式においてｂは散逸因子（dissipation factor）、εは振幅の増分（インクリメント）である。両ファクタとも発振器同士の結合を決定する。閾値φthresholdは１に規格化される。
【００２０】
非特許文献２に示されたように、ネットワークが完全にメッシュ状である場合には、ｂ＞０かつε＞０に対してシステムは常に収束する、つまり全ての発振器は１つのものとして発火する。同期までの時間は積ｂ・εに反比例する。
【００２１】
このモデルは、前述したように、同期をもたらすパルス結合発振器の最も端的な数学的解釈を提示する。
【００２２】
無線環境では、パルスは、検出が困難なことから、通信にはほとんど考慮されない。この最初のフレームワークは継続時間が一定のパルスのバーストまたはシーケンスによる通信に適応するよう構成された（非特許文献３参照）。このスキームはタイムアドバンス同期（time advance synchronization）スキームと呼ばれ、後でより詳しく述べることにする。
【００２３】
ここまでは、同期スキームはノードが完全メッシュ状ネットワークを形成すると仮定しており、この仮定は無線ネットワークには当てはまる。しかしながら、一般に、この仮定は２つの理由から成り立たない。第１に、ノードが広いエリアにわたって拡散しているまたは伝送パワーが限られている場合、ノードはその伝送距離内にあるノード、つまり近隣ノード、とだけ通信することができる。第２に、ノード間のピアツーピア通信に対しては、完全メッシュ状ネットワークは高い干渉を暗示する。従ってそれはネットワーク容量を改善するために、より低い伝送パワーには望ましい。このためほとんどの場合、無線ネットワークのトポロジーは完全にはメッシュ化されない。
【００２４】
より現実的には、アドホック・ネットワークのトポロジーはメッシュ状と考える必要がある。斯かるネットワークにおける２つのデバイスは必ずしも伝送距離内にある必要はなく、近隣ノードを介して通信することができ、従ってマルチホップ・ネットワークを形成する。距離依存チャネルモデルが議論される場合、伝送範囲は半径ｒ0の円として単純化される。ノードはこの領域内に入るノードとのみ直接通信することができる。図１１Ａは５つのノードが正方形エリア内のそれらのそれぞれの伝送範囲内にランダムに分布している様子を示している。
【００２５】
図１１Ａようにノードの座標と到達可能エリアを単純に表しただけではネットワークの接続性を表現することは難しい。この目的のため、５つのノードから成る同一ネットワークの第２の表現（グラフ表現）を図１１Ｂに示す。実線は、２つのノードの間にリンクが存在し、通信が可能であることを示している。
【００２６】
次の記述において、完全メッシュ状ネットワークを議論するとき、分散型の時間的同期化がいかにして達成できるかをまとめる。時間的同期化は、全てのノードにわたって共通のスロット構造を定義するため、局所時間単位（local time unit）を揃えるものとして定義される。
【００２７】
以前の研究によれば、例えば同期ワード（ＴTx）の継続時間といった送信遅延時間と受信機が受信メッセージを処理するために必要とされる復号遅延時間（Ｔdec）とが、最初のホタル同期化スキームの達成可能な精度に影響を与えることが示された（非特許文献３参照）。この不都合な効果に対応するため、待機状態がノードの有限状態機械に付加された。タイムアドバンス同期（time advance synchronization）に基づく１つのノードを記述する状態機械を図１４Ａに示す。
【００２８】
この状態機械は、リスニング状態（ＬＩＳＴＥＮ）、待機状態（ＷＡＩＴ）、送信状態（ＴＲＡＮＳＭＩＴ）、不応状態（ＲＥＦＲ（REFRACTORY））の４つの状態から成る。リスニング状態（ＬＩＳＴＥＮ）の間、ノードは積分関数に従って位相Φをインクリメントし、リスニング時間Ｔlistenの間、他のノードのパルスをリスンする。パルスを受信すると、ノードは位相を位相応答曲線（ＰＲＣ）に従って増大（increase）させる。位相Φが閾値Φ＝Φthresholdに達するとすぐにノードは発火する、言い換えると、発火状態に達する。このイベント（発火）を契機にノードは自分の位相をゼロにリセットし、待機状態（ＷＡＩＴ）に移行し、その状態のまま待機状態に関連した待機時間ＴWAITの間だけ待機する。待機状態の間、ノードは他のノードをリスンすることもなく、それ自体がパルスを送信することもない。
【００２９】
待機時間が終わると（イベント：ＷＡＩＴ終了）、ノードは送信状態ＴＲＡＮＳＭＩＴに移行し、パルスまたは同期信号長ＴTXを有する同期信号の送信を開始する。同期信号を送信し終わった後（イベント：ＴＲＡＮＳＭＩＴ終了）、ノードは不応状態ＲＥＦＲへ移行する。ノードは、不応時間Ｔrefrの間、不応状態にとどまる。不応時間が終わった後（イベント：ＲＥＦＲ終了）、ノードはリスニング状態ＬＩＳＴＥＮに再び移行する。
【００３０】
図１４Ｂに時間ｔに対する位相Φ（ｔ）の変化の一例を示す。ノードは最初に他のノードの同期信号にリスン（listen）しき耳を立て、その位相をインクリメントする。位相が閾値に到達した後、ノードは発火（fire）し、同期信号を送信する（ＴX）前に待機時間だけ待機する。同期信号を送信した後、ノードは不応状態（refr）に移行し、その後、再びリスニング状態（listen）に移行する。図１４Ｂは伝搬遅延Ｔ0が無視できる場合のシナリオを示したものである。このとき待機時間Ｔwaitは次のように定義される。
Ｔwait＝Ｔ−（ＴTX＋Ｔdec）
上式においてＴdecは復号時間である。
【００３１】
同期信号を受信する別のノードは同期信号を完全に受信し終わった後に同期信号の復号を開始する。復号に要する時間は前記復号時間Ｔdecであって、第１のノードが発火した正確にＴ秒後に（１４１０）、その位相をインクリメントする。
【００３２】
図１４Ｃの上の部分に、送信機ＴXが、チャネル関数ｈ（ｔ）のチャネル（通信路）で信号ｘ（ｔ）を受信機ＲXへ送信する送信モデルの一例を示す。受信機ＲXが受信する信号ｙ（ｔ）は次のように書かれる。
ｙ（ｔ）＝ｈ（ｔ）＊ｘ（ｔ＋Ｔ0）
上式においてＴ0はチャネルによって引き起こされる伝搬遅延時間である。受信信号に適用される整合フィルタの出力は次のように表すことができる
Λ（ｔ）＝ｘ（−ｔ）＊ｙ（ｔ）
【００３３】
図１４Ｃの左下の部分に、経過時間に対する一連の状態を示す。送信状態ＴXから始まり、その状態が送信時間ＴTXの間だけ続き、その後、不応状態ＲＥＦＲ、リスニング状態ＬＩＳＴＥＮへと続く。図１４Ｃの右下の部分に、ノードが実際に送信を開始してから別のノードが位相をインクリメントするまでの間の全遅延時間Ｔtotを示す。これは伝搬遅延時間Ｔ0、同期信号長もしくは送信時間ＴTX、および復号時間Ｔdecを合わせた時間である。すでに言及した遅延時間を考慮に入れると、同期信号の受信に要する時間は次のようになる。
Ｔtot＝Ｔ0＋ＴTX＋Ｔdec
【００３４】
シミュレーションにおいて、タイムアドバンスシステムは完全なメッシュ環境においてうまく機能することが観察されている。メッシュ状ネットワークでは、特にノードが少数の近隣ノードしか持たない場合には、同期率は好ましいネットワーク環境では２０％低下し、難しいネットワーク環境では６０％も低下する。言い換えると、メッシュ状ネットワークにおける同期率は低すぎるため、ノードを同期させるための信頼性の高いソリューションを提供することはできない。
【非特許文献１】C. Prehofer and C. Bettstetter, "Self-organization in communication networks: Principles and design paradigms,"IEEE Communications Magazine, vol. 43, pp. 78-85, Jul. 2005
【非特許文献２】R. Mirollo and S. Strogatz, "Synchronization of pulse-coupled biological oscillators," SIAM j. APPL. MATH, vol.50, pp.1645-1662, Dec. 1990
【非特許文献３】A. Tyrrell, G. Auer, and C. Bettstetter, "Firefly synchronization in ad hoc networks," in Proc. of 3d MiNEMA workshop, Feb. 2006
【発明の開示】
【発明が解決しようとする課題】
【００３５】
そこで本発明の課題は、自己組織化メッシュ状ネットワークにおいて確実により多くのノードを同期させるための装置および方法を提供することにある。
【課題を解決するための手段】
【００３６】
上記課題は、第１の送受信機器を第２の送受信機器に同期させるための請求項１に記載された装置、請求項１７に記載された送受信機器、第１の送受信機器を第２の送受信機器に同期させるための請求項１８に記載された方法によって解決される。
【００３７】
本発明は、上記課題を解決するため、第１の送受信機器（transmit or receive device）を第２の送受信機器に同期させるための装置を提供する。本発明の装置は、
前記第２の送受信機器からの同期信号を受信および検出するようにされた受信機と、
同期期間後に前記第２の送受信機器からの同期信号と同期した前記同期信号を送信する送信機と、
処理装置とを具備する。前記処理装置は、
所定の非リスニング時間後に時間上の所与の第１の関数に従って内部信号値を増大させ、前記受信機から検出信号を受信したら第２の関数に従って前記信号値を増大させ、
当該装置が受信期間に関連する第１の制御状態にあるときに前記内部信号値を閾値と比較し、
前記内部信号値が前記閾値に等しくなったときに期間変数に基づいて前記受信期間を繰り返すかどうかを決定し、
前記受信期間を繰り返す場合には、前記同期信号を送信することなく前記内部信号値の増大が繰り返された受信期間において実行され、更に、異なる非リスニング時間を使用してまたは非リスニング時間なしに前記繰り返された受信期間において前記内部信号値を増大させ始めるようにされる、
または、
前記送信機を制御して前記送信機が、前記内部信号値が前記閾値に等しくなったときに前記処理装置が前記送信期間へ移行することを決定したときに到達する状態である前記送信期間に関連した第２の制御状態において、前記同期信号を送信するようにし、
前記同期信号の送信が終了した後に始まる状態である前記送信期間に関連した第３の制御状態において、ゼロより大きくかつ前記送信期間の継続時間より短い受信機待機時間の間だけ待機し、
前記期間変数に基づいて前記送信モードを繰り返すかどうかを決定し、
前記送信モードを繰り返す場合には、前記送信機を制御して前記送信機が、リスニング期間を合間に挟むことなく、前記第２の制御状態において前記同期信号を送信するようにするようにされる。
【００３８】
本発明は、上記課題を解決するため、送受信機器も提供する。本発明の送受信機器は、
第１の送受信機器を同期させるための装置と、
前記同期信号のタイミングに基づいてデータ送信またはデータ受信を制御するための制御装置とを具備する。
【００３９】
本発明は、上記課題を解決するため、第１の送受信機器を第２の送受信機器に同期させるための方法も提供する。本発明の方法は、
所定の非リスニング時間後に、受信期間に関連した第１の制御状態において、時間上の所与の第１の関数に従って内部信号値を増大させるステップと、
同期信号を受信および検出するステップと
前記第１の制御状態にいる間に前記同期信号を検出したら第２の関数に従って前記内部信号値を増大させるステップと、
前記第１の制御状態にいる間に前記内部信号値を所与の閾値と比較するステップと、
前記内部信号値が前記閾値に等しくなったときに期間変数に基づいて前記受信期間を繰り返すかどうかを決定し、前記受信期間を繰り返す場合には、前記同期信号を送信することなく、繰り返された受信期間において前記内部信号値の増大が実行されるとともに、異なる非リスニング時間を使用してまたは非リスニング時間なしに前記繰り返された受信期間において前記内部信号値のインクリメント（increment）または増大（increase）を開始するステップと
を含むものであるか、または、
前記送信期間に関連した第２の制御状態において前記同期信号を送信するステップと、
前記同期信号の送信が終了した後に始まる状態である前記送信期間に関連した第３の制御状態において、ゼロより大きくかつ前記送信期間の継続時間より短い受信機待機時間の間だけ待機するステップと、
前記受信機待機時間が終わったときに前記期間変数に基づいて前記送信期間を繰り返すかどうかを決定し、前記送信期間を繰り返す場合には、リスニング期間を合間に挟むことなく、繰り返された送信期間において前記同期信号の送信を実行するステップと
を含んでなる。
【００４０】
本発明は、ほとんど同時に発火する近隣ノードは互いに聞こえない（hear）ことから互いに同期し合わないという点の発見、および、所与のスキームに基づくノードが送信期間および／または受信期間を繰り返すことができるようにより大きな柔軟性を持ち込むことでメッシュ状ネットワークにおいても同期が回復できるという発見に基づく。
【００４１】
本発明の装置は、その一態様において、前記受信期間に関連する受信モード、または前記送信期間に関連する送信モードにある。このとき前記第１の制御状態は前記受信期間または受信モードに関連し、前記第２および第３の制御状態は前記送信モードまたは送信期間に関連する。固定された一連の制御状態を有しておりノードは常にリスニング状態から待機状態へ移行し、その後に送信状態へ移行し、そして常に送信後に不応状態に移行し、その後に再びリスニング状態に入る元々のタイムアドバンスシステム（time advance system）とは対照的に、ノードを同期させるための本発明の装置は、送信期間および／または受信期間の最後にそれが同じモードにとどまる（つまり同じ期間を繰り返す）べきか、またはその他のモードへ移行する（つまりその他の期間へ移行する）べきかどうかを決定する働きをする。この結果、近隣の装置またはノードがほとんど同時に送信する（このことがこれらの近隣の装置またはノードが同期し合うことを妨げる）いわゆる難聴スポット（deaf spots）は避けることが可能である。
【００４２】
期間を繰り返すべきかまたはその他の期間に移行すべきかどうかの判断は期間変数（period variable）に基づく。本発明の装置は、前記期間変数は２つの値のみをとり、その各値は前記２つの期間（受信期間と送信期間）のいずれか一方に関連するようにすることが可能である。好ましくは、前記期間変数の値は第３の関数に基づいて決定され、本発明の装置はその各態様において、近隣ノードの第３の関数とは異なる、異なる第３の関数上の前記期間変数の値を決定する働きをする。この結果、近隣ノードが送信期間および受信期間の同一の系列を示し、従って最悪の場合、互いの近隣ノードの同期信号を聞くことができない状態（難聴状態）のままになる（こうなるともはや同期できない）状況が避けられる。前記第３の関数は具体的な態様としてゴールド系列（Gold sequences）の集合の疑似ランダム系列（pseudo-random sequences）またはランダム系列（random sequences）から構成される。本発明の装置は、別の態様として、送信期間の最後に受信期間に移行し、そして同じく受信期間の最後に送信期間に移行し、言い換えると、元々のタイムアドバンス（time advance）ストラテジーから知られているように元々の送信／受信期間を実行し、当該装置が所定数の連続する受信期間またはむしろ送信／受信期間の間にその内部信号値を増大しなかった、すなわち、近隣ノードから同期信号を受信し復号し終わらなかった場合に、送信期間を合間に入れることなく受信期間のみを繰り返す働きをする。
【００４３】
本発明の装置は他の態様として上記の各実装を合せたものを利用しても動作可能である。例えば、本発明の装置は、最初に、当該装置が所定数の前記当初の送信／受信期間の間に同期信号を成功裏に受信し復号し終わったかどうかをチェックし、もし成功裏に終わらなかった場合には、疑似ランダム系列またはランダム系列を適用して送信期間または受信期間を繰り返すべき時を決定する働きをする。こうして、この場合も同じように近隣ノードの同じ挙動が避けられる。
【００４４】
本発明の装置は、更なる態様として、伝搬遅延がかなり大きなネットワークにおいてより高い安定度を獲得するため、前記受信期間に関連した第４の制御状態を含む。この状態の期間の間は当該装置は前記内部信号値をインクリメント（increment）させたりまたは増大（increse）させない。
【００４５】
本発明の他の態様の装置では、第５の制御状態は前記送信期間に関連する。この第５の制御状態があることで、フレームの中間部分（mid-amble）を同期に利用することが可能となる。
【００４６】
本発明の装置は、更なる態様として、例えばペイロードデータの送信を組織するために設計された通信プロトコルのデータパケットまたはデータフレームの所定の部分を同期信号として利用する働きをする。結果、本発明は既存の物理層実装において、例えば８０２．１１、８０２．１６などのＷＬＡＮ（wireless local area network）標準またはある特定の継続時間を持つフレームを使用する任意の他のプロトコルに従って利用することが可能である。
【発明の効果】
【００４７】
以上述べたことをまとめると、積分発火型発振器の当初の明瞭さは維持されると言うことができる。さらに、取得または同期段階および送信段階を区別する必要性は全くないのでノード間の同期はシームレスである。本発明の装置（または方法）はスキームがプリアンブル（pre-amble）、ミッドアンブル（mid-amble）、またはポストアンブル（post-amble）スキームに適応可能なことから非常にフレキシブルなスキームを与える。言い換えると、フレームの同期信号として利用される部分はフレームの最初の部分、中間の部分または最後の部分であることが可能である。ペイロードデータは装置が前記送信期間に関連する第３または第５の制御状態にあるときに送信することが可能である。第３および第５の制御状態は例えば、前記送信期間の間の同期信号の送信前または送信後の待機状態としての役割を果たす。このため、ＭＡＣ（medium access control）層に課される制約条件はより少なくて済む。
【００４８】
本発明の実施の最良の形態を以下の図面を参照して詳細に説明する。
【発明を実施するための最良の形態】
【００４９】
本発明の実施の最良の形態を詳細に説明する前に、以下使用される用語とそれらのそれぞれの関係を紹介する。本発明の装置はパルス結合発振器（pulse-coupled oscillator）または積分発火型発振器（integrate-and-fire oscillator）と称されることもある。特定の実施形態において、内部信号値は位相（phase）Φ、その閾値はΦthreshold、第１の関数は位相関数、積分関数またはインクリメント関数、第２の関数は位相応答曲線ΔΦ（Φ）と呼ばれることもある。特定の実施形態において、第１の制御状態はリスニング状態（listen state）、第２の制御状態は送信状態（transmitting state）、第３の制御状態は受信機待機状態（receiver wait state）、第４の制御状態は不応状態（refractory state）、そして第５の制御状態は送信機待機状態（transmitter waiting state）と呼ばれることもある。用語“ノード（node）”は本発明の装置の実施形態または一般的には本発明の送信もしくは受信機器を指すことがある。送信期間は送信タイムスロット（transmitting time slot）、それに対して受信期間は受信タイムスロット（receiving time slot）と呼ばれることもある。同期信号（synchronization signal）は、パルス、メッセージまたは同期バーストと呼ばれることもある。
【００５０】
図１Ａに、受信機１１０、処理装置（processing unit）１２０および送信機１３０で構成される本発明の実施の一形態である装置を例示する。第１の制御状態は受信期間または受信モードに関連し、第２および第３の制御状態は送信期間または送信モードに関連する。本発明の装置は同期信号の送信または受信のいずれか一方を行うだけで同期信号の送信と受信を同時に行ったりはしない。従って、本発明の装置は送信モードまたは受信モードのいずれかにあると言うことができる。処理装置１２０は受信機１１０および送信機１３０を制御して例えば１つの制御状態から別の制御状態へ移行させる働きをする。処理装置１２０は、第１制御状態にあるとき、内部信号値または位相を第１の関数または位相関数に従って増大させる。第１の制御状態にあるとき、受信機１１０は同期信号１４０を別の装置またはノードから受信し、受信および検出が成功裏に終わった後にその同期信号１４０を復号し（同期信号１４０の復号とも呼ばれる）、検出信号１５０を処理装置１２０に送信する準備が整う。同期信号の検出は、例えば、相関ピークが例えば検出信号１５０である相関検出器（correlation detector）または整合フィルタ（matched filter）によって実行することが可能である。また処理装置１２０は、第１の制御状態において検出信号１５０を受信する際に、例えば位相応答曲線もしくは結合関数（coupling function）といった第２関数に従って内部信号値を修正するよう構成されている。処理装置１２０は更に、内部信号値を所与の閾値（例えばΦthreshold）と比較するよう構成されており、内部信号値が閾値に等しくなるとすぐに第１の制御状態を終結する。この時点で、処理装置１２０は、期間変数に基づいて、リスニング期間を繰り返すべきかまたは送信期間へ移行すべきかいずれかを決定する。
【００５１】
内部信号値が閾値に等しくなるとすぐに、つまり発火するとすぐに、処理装置１２０はその内部信号値をリセットし、前記送信期間に移行すべきかまたは前記受信期間を繰り返すべきかいずれかを決定する。
【００５２】
処理装置１２０が受信期間を繰り返すと決めた場合、処理装置は再び内部信号値のインクリメントを開始する。処理装置１２０は更に、前回の受信期間の間にすでに受信を開始した同期信号の受信を継続してその同期信号を復号する、または前回の受信期間の間に受信を完了した同期信号の復号を開始する、または前回の受信期間で開始した進行中の復号を継続するよう構成されることも可能である。他の実施形態では、処理装置１２０は前回の受信期間において受信または復号を開始した同期信号の受信または復号を中止する働きをすることが可能である。内部信号が再び閾値に到達するとすぐに、処理装置１２０は再度、前記受信期間を繰り返すべきかまたは前記送信期間に移行すべきかいずれかを決定する。
【００５３】
処理装置１２０が送信期間に移行すると決めた場合、処理装置１２０は前回の受信期間（＝送信期間に移る前の受信期間）の間に開始した任意の受信または復号を中止する働きをすることができる。代わりの実施形態では、処理装置１２０は前回の受信期間の間に受信を完了した同期信号の復号を開始するまたは前回の受信期間の間に開始した進行中の復号を継続する働きをすることができる。後者の場合、処理装置１２０は送信期間の間に内部信号値を増大させずに、例えば第１またはリスニング状態に再び到達するまでその増大を遅らせる働きをすることができる。送信期間に移行するとき、処理装置１２０は生成信号（generation signal）１６０を送信機１３０に送信し、送信機は生成信号１６０を受信するとすぐに同期信号１４０を送信する。それと同時に処理装置１２０は受信機１１０を制御してそれが近隣ノードからの同期信号１４０の受信またはリスニングを停止するようにする働きをする。
【００５４】
送信機１３０が同期信号１４０を送信した後、処理装置１２０はそれ自体と送信機を第３の制御状態へ移行させて、その状態で受信機待機時間の間、待機する働きをする。受信機待機時間が終了した後、処理装置１２０は期間変数に基づいて送信期間を繰り返すべきかまたはリスニング状態へ移行すべきかいずれかを決定する働きをする。処理装置１２０が送信期間を繰り返すことを決めた場合、処理装置は再び生成信号１６０を送信機１３０へ送信し、送信機は再び同期信号１４０を送信する。処理装置１２０が受信期間へ移行することを決めた場合、処理装置１２０は受信機１１０を第１の制御状態へ再び移行させて第１の関数に従って内部信号値のインクリメントを開始し、および／または第２の関数に従って内部信号値の増大を開始する。
【００５５】
図１Ａに本発明の装置の１つの可能な実施形態を示す。本装置はもちろん、例えば、受信機１１０、処理装置１２０および送信機１３０が１つの単一のユニットに一体化されるように実現することが可能である。あるいは代わりに、同期信号の復号または検出は処理装置１２０で実行され、受信機１１０はペイロードデータと同期信号を例えば１フレームで受信するために使用され、処理装置はそのフレーム内の同期信号をリスンし、それを利用して送信もしくは受信機器またはノードをその近隣の機器またはノードと同期させることが可能である。
【００５６】
図１Ｂに、一般化されたタイムアドバンススケジューリング（generalized time advance scheduling）とも呼ばれる、本発明に基づく同期させるための装置の挙動を記述する状態機械を例示する。本状態機械は、第１の制御状態１７０またはリスニング状態ＬＩＳＴＥＮ、第２の制御状態１８０または送信状態ＴＲＡＮＳＭＩＴ、および第３の制御状態１９０または受信機待機状態ＷＡＩＴRXとから構成される。第１の制御状態１７０にあるとき、処理装置は内部信号値または位相Φをインクリメント（increment）し、受信機が別のノードから同期信号を受信および検出した場合には内部信号値を増大（increase）させる。図１Ｃに図１Ｂの状態機械に対応する分円図（pie chart）を例示する。
【００５７】
図１Ｃは分円図の中に第１の制御状態またはリスニング状態をそのリスニング状態に関連するリスニング時間Ｔlistenと共に示している。リスニング時間Ｔlistenは、内部信号値が、同期信号が検出されたことによる増大（increase）なしに、（インクリメントで）閾値に到達するまでに必要とされる時間である。それゆえ、リスニング時間Ｔlistenが終わるとすぐに装置は発火１７２する。期間変数（以下“ｎｅｘｔ”と呼ぶ）が受信期間１６４に関連する第１の値ＲXに等しくなった場合、つまりｎｅｘｔ＝ＲXかつΦ＝Φthreshold)の場合（１７４）、処理装置は受信期間を繰り返すことを決める、言い換えると、第１の制御状態１７０に入り直すことを決める。
【００５８】
期間変数ｎｅｘｔが送信期間１６２に関連する第２の値ＴXに等しくなった場合、つまりΦ＝Φthresholdかつｎｅｘｔ＝ＴXの場合（１７６）、処理装置は送信期間へ移行することを決める。また、図１Ｃには、可能性１７４および１７６の両者が示されている。
【００５９】
送信期間１６２に関連する第２の状態１８０に移行した後、送信機は同期信号長Ｔtransmitを有する同期信号の送信を開始する。同期信号の送信が終わった後、つまりＴtransmitが終了（transmit終了）した後１８２、装置は受信機待機状態１９０へ移行し、そこで受信機待機状態または第３の制御状態１９０に関連する受信機待機時間ＴwaitRXの間、待機する。受信機待機時間ＴwaitRXが終了（WAITRX終了）した後１９２、処理装置は送信期間１６２にとどまるべきかまたは受信期間１６４へ移行すべきかいずれかを決定する。期間変数ｎｅｘｔが第２の値ＴXに等しくなった場合、つまりWAITRX終了かつｎｅｘｔ＝ＴXの場合（１９４）、装置は第３の制御状態１９２から第２の制御状態１８０へ移行し、送信期間１６２にとどまる。
【００６０】
期間変数ｎｅｘｔが第１の値に等しい場合、つまりWAITRX終了かつｎｅｘｔ＝ＲXの場合（１９６）、装置は第３の制御状態１９０から第１の制御状態１７０へ、つまり受信期間１６４へ移行する。
【００６１】
イベントおよび／または決定１８２、１９２、１９４および１９６も図１Ｃに示されている。図１Ｃには、それぞれリスニング状態１７０、送信状態１８０、および受信機待機状態１９０に関連する時間Ｔlisten、ＴtransmitおよびＴwaitRXも示されている。
【００６２】
好ましい実施形態では、同期状態において、受信期間１６４の継続時間は送信期間１６２の継続時間に等しい。この場合、両方の期間は継続時間Ｔを有する。従って次式が成り立つ。
Ｔlisten＝Ｔ、
Ｔtransmit＋Ｔwait＝Ｔ
Ｔtransmitは以下ＴTxとも呼ばれる。
【００６３】
代わりに、本発明の装置では、受信期間の継続時間または送信期間の継続時間は期間Ｔの整数倍であることが可能である。この場合、互いにＴまたはＴの整数倍だけ隔たった３つ以上の瞬時グループが形成される可能性がある。
【００６４】
上述した実施形態では期間変数は唯２つの値ＴXおよびＲXしか採らない。代わりの実施形態では、期間変数は任意の値を採ることがある。その場合の処理装置の決定は例えば閾値に基づいて、この閾値より上の全ての値は受信期間に関連し、この閾値より下の全ての値は送信期間に関連するように取り決めることができる。
【００６５】
さらに、本発明の装置は、期間変数を例えば外部の発信源またはノードから受信する、または内部もしくは外部のイベントまたは例えば第３の関数に基づいて期間変数の値を決定する働きをすることができる。期間変数を決定するための好ましい実施形態のより詳しい議論については後述することにする。
【００６６】
次に、元々のタイムアドバンスストラテジーをメッシュ状ネットワークで利用したときに観察される問題について考察し、そして本発明のいくつかの実施形態について説明する。
【００６７】
図１４Ａに示したタイムアドバンススケジューリングに基づくノードを参照すると、各状態の継続時間を視覚化するため、Ｎ個のノードから成るシステムは分円図の円に沿ったマーカとして表すことが可能である。タイムアドバンススケジュールに基づく１発振器に対する自然な発振周期は２・Ｔに等しい。
【００６８】
それゆえ、分円図を丸一周したときの時間は２・Ｔに等しい。各状態のサイズは、Ｔwait、ＴTX、Ｔrefr、ＴRXに比例する。斯かる表現を図２Ａに示す。この図において、リスニング状態に関連するリスニング時間ＴRX＝０．８・Ｔ、待機状態に関連する待機時間Ｔwait＝０．７５・Ｔ、送信状態に関連する送信時間ＴTX＝０．２・Ｔ、不応状態に関連する不応時間Ｔrefr＝０．２５／Ｔに設定されている。
【００６９】
ＬＩＳＴＥＮの間、メッセージが受信され復号される場合、ゼロから閾値Φthresholdまで時間の経過とともに線形にインクリメントする位相関数は、現時点の位相値［３］に依存するオフセットだけインクリメントされる。
【００７０】
最初は同期化されていないＮ個のノードから成る斯かるシステムがある時間から正確にＴ秒後に発火する２つのグループを形成することがどのようにして可能となるかを理解するため、１つのノードＡの時間発展を詳しく調べる。ノードが交互に送信機と受信機を繰り返すとき、ノードＡは、いつそれが送信し、その後、いつそれが受信するかを最初に調べる。
【００７１】
図２ＡはノードＡが待機状態を脱した後に送信を開始するときのタイムアドバンスシステム（time advance system）に基づくシステムを表している。図２Ａには図１４Ａに基づく４つの制御状態としてＷＡＩＴ（待機状態）、ＴＲＡＮＳＭＩＴ（送信状態）、ＲＥＦＲ（不応状態）およびＬＩＳＴＥＮ（リスニング状態）が示されている。
【００７２】
この瞬間において、送信中の全てのノードはそれらの受信機（または受信機能）をオフにしており、ノードＡのメッセージの始めを受信することはできない。このグループはＲ１でラベルされる。リスニング状態にあるがＴTX＋Ｔdec内に発火するノードと待機中のノードもノードＡの同期メッセージを完全に受信し復号することはできない。この領域はＲ２でラベルされる。
【００７３】
従ってＲ３でラベルされた領域内にあるノードだけが送信された同期メッセージを完全に解釈することが可能である。領域Ｒ３内のノードはノードＡが送信を開始してからＴTX＋Ｔdec後にメッセージを受信し復号し終わることになる。この瞬間が図２Ｂに表されている。ノードＢはＲ３の部分にある。この瞬間において、ノードＢはその位相をΔΦ（ΦB）だけインクリメントし、それを契機にそれは即座に発火する。このときそのマーカはノードＡのマーカとは直径を挟んで正反対の位置にある。従ってこれら２つのノードは互いに正確にＴ秒の間隔を置いて発火する。言い換えると、これら２つのノードは同期している。
【００７４】
図２ＣはノードＡがその受信機をオンにするときのシステムを示している。ノードＡが受信を開始する際、そのとき送信されている最中だったメッセージを不応状態において失ってしまうことになる。それゆえ、ノードＡは領域Ｒ４内にその状態があるノードのメッセージは聞こえないことになる。
【００７５】
ノードＡは、それがリスニング状態にあるときにあるいは他の実施形態において不応状態またはリスニング状態にあるときに送信されている最中の任意のメッセージを受信することが可能である。
【００７６】
しかしながら、メッセージが発火のＴTX＋Ｔdec以下前に送信が開始される場合、そのメッセージは完全に受信・復号はなされない。この領域はＲ５でラベルされる。
【００７７】
従って、ノードＡは、状態が領域Ｒ６にある送信機からの同期メッセージを完全に受信し復号することが可能である。ノードＡは領域Ｒ６内の送信機からメッセージを受信すると、直径を挟んで反対側の状態に向かって状態を徐々にシフトさせる。
【００７８】
ノードＡの状態の時間的変化をまとめるため、ノードＡが発火しているときの重要な領域を図２Ｄに集めた。
【００７９】
図２Ｄは分円図に基づいてタイムアドバンスストラテジーによる受信機と送信機の分解を示している。
【００８０】
領域Ｒ３におけるノードはノードＡのメッセージが聞こえ、それらの状態をノードＡとは直径を挟んで反対側のポイントへ徐々にシフトする。逆に、領域Ｒ６内のノードのメッセージはノードＡによって聞かれ、ノードＡとは直径を挟んで反対側のポイントへ徐々にシフトする。タイムアドバンススキームによる同期は、２つのグループが分円図の直径を挟んで互いに反対側に形成され、それらの発火点がＴ秒の間隔をおいたときに完成する。
【００８１】
システムが同期化されると、全てのノードは安定平衡状態にある。というのは、１つのグループからのノードがその同期状態から少しでもずれると、直径を挟んで反対側にあるグループは新たな状態に加入するかまたは外れたノードを安定平衡状態に押し戻すかいずれを行うからである。
【００８２】
他方、ノードＡは、状態がＲ１またはＲ４内にあるノードから受信もしないし、そういうノードに影響も与えない。これらのノードが同期するためには、領域Ｒ３またはＲ６からの外部のノードがＲ１またはＲ４内のノードがそのメッセージを受信するときに１つのグループへ吸収する（merge）ことによって、Ｒ１またはＲ４内のノードを強制的に同期させる。全てのノードが領域Ｒ１またはＲ４内にあるシステムは決して成功裏に同期することはない。
【００８３】
言い換えると、それらは互いの同期信号に対して難聴である。それゆえ、領域Ｒ１およびＲ４は難聴領域または難聴スポットとも呼ばれる。
【００８４】
Ｎ個のノードから成るシステムが２・ＴTXの幅を持つこの難聴領域内にある初期状態を有する確率ｐdeafは次式に等しい。
【数３】
0004418481.tif 000004
【００８５】
同期確率ｐsyncは、同期率に影響を及ばす唯一の効果が難聴性（deafness）であることを考慮すると、この難聴確率ｐdeafから次のように直接得られる。
ｐsync＝１−ｐdeaf                （２）
【００８６】
メッシュ状ネットワークにおける難聴効果を検証するため、最悪ケースのトポロジーでタイムアドバンス同期スキームを調べることがより明瞭である。式（１）から分かるように、難聴確率は所与のノードの近隣ノード数が増大するのにともなって指数関数的に減少する。それゆえ難聴問題はノードが１個または２個の近隣ノードしか持たないときに最も高い確率で存在する。
【００８７】
図２Ｅに１個または２個の近隣ノードしか持たないＮ＝８のシステムに対する対応するトポロジーを示す。このトポロジーを以下、ＮＷ１と呼ぶことにする。
【００８８】
式（１）に基づいて、Ｎ＝４個のノードから成るラインネットワークに対する確率は、末端ノードがそれらの唯一の近隣ノードと難聴になる確率の総和として近似することができ、中央のノードが難聴になる確率は次式で与えられる。
【数４】
0004418481.tif 000005
【００８９】
８個のノードに対する表現は見つけることがとても難しく、そのため上式（３）が近似としての役割を果たす。この式の有効性を検証するため、ＴTXが０．１・Ｔから０．５・Ｔまで変化するときにタイムアドバンススキームがＮＷ１に適用される。シミュレーションの設定は以下の通りである。遅延時間がＴdec＝０．１・ＴおよびＴrefr＝ＴTX＋Ｔdecに固定される。各シミュレーションは８０・Ｔの間だけ実行し、この期間内に同期が実現しない場合には、同期は不成功と見なされる。各期間Ｔは１５００ステップに分割され、各ステップごとに各ノードの状態と相互作用が計算される。カップリング設定はｂ＝３およびε＝０．２に設定される。初期状態は全てのノードがランダムに分散した状態変数（分円図に沿ってランダムに分散するマーカ）を有するケースに対応し、図１４Ａの状態機械に従う。
【００９０】
図２Ｆと図２Ｇは、元々のタイムアドバンススキームをネットワークＮＷ１に適用したときの、各ＴXごとに１０００セットの初期状態に基づく同期結果をプロットした図である。図２ＦはＴTX／Ｔ（同期信号長ＴTXを期間Ｔで規格化したもの）に対する同期率（％）を示している。プロット１９２は同期率の理論値、プロット２９４は同期率のシミュレーション結果を示す。図２ＧはＴTX／Ｔ（同期信号長ＴTXを期間Ｔで規格化したもの）に対する、期間Ｔで規格化された同期に達するまでの平均時間を示している。
【００９１】
送信遅延時間の増大に伴う同期率の劣化は式（３）を支持している。低い同期率の主な理由はノード１とノード８の難聴から来ている。これらのノードは１つの近隣ノードしか持たない。このことはそれらが最初にノード２とノード７の難聴エリアにある確率がＴTX/Ｔに等しいことを暗に示している。
【００９２】
明らかに、送信継続時間が０．４・Ｔを超えるときの同期率は１５％を下回り、それは受け入れ可能ではない。このため元々のタイムアドバンス同期スキームは修正される必要がある。
【００９３】
難聴効果に対処することは送信遅延時間が大きなときにそれが同期を妨げる主原因であることから必要である。これは特にメッシュ状ネットワークにおいて顕著に現れる。同期を回復するため、タイムアドバンス同期スキームに従うノードの挙動は本発明によれば２つの別個のタイムスロットまたは期間に分かれる。このアプローチを、以下、一般化されたタイムアドバンス同期スキーム（generalized time advanced synchronization scheme）と呼ぶことにする。このスキームは元々のスキームにより多くの柔軟性を与え、高い同期率を回復するために利用される。
【００９４】
すでに述べたタイムアドバンス同期スキームの説明から、ノード間の難聴（deafness）は本質的に初期状態とリンクしている。これは変えることはできない。
【００９５】
この難聴に有利に働く別のファクタは、２つのグループが形成されるおかげでノードが改善された精度で同期することである。各グループは同期するための他のグループを必要とし、１つのグループは、それ自体のグループ内にあるノードは聞こえない。それゆえ、ノードがその近隣ノードの難聴領域内にある場合、同期に達することはできない。
【００９６】
２つのノードが互いに聞こえないという状況を解決するため、ノードの全期間２Ｔはそれぞれの継続時間がＴの２つの期間、つまりすでに導入した送信期間と受信期間、に分解される。図３Ａにこの分解の様子を示す。
【００９７】
図３Ａの左側に送信期間１６２と受信期間１６４に分解された分円図を示す。送信期間１６２は３つの状態から成る。１つ目の状態は図１４Ａに示されたタイムアドバンススケジュールから知られる待機状態ＷＡＩＴに相当する送信機待機状態（ＷＡＩＴTX）３１０、２つ目の状態は同期信号を送信するための送信状態（ＴＲＡＮＳＭＩＴ）１８０、そして３つ目の状態は受信機待機状態（ＷＡＩＴRX）１９０である。受信期間１６４は不応状態（ＲＥＦＲ）３２０とリスニング状態（ＬＩＳＴＥＮ）１７０から成る。
【００９８】
リスニング状態または第１の制御状態１７０、送信状態または第２の制御状態１８０、そして受信機待機状態または第３の制御状態１９０は、図１Ｂに示されたそれぞれの制御状態に対応する。以下、不応状態３２０は第４の制御状態とも呼ばれ、送信機待機状態３１０は第５の制御状態とも呼ばれる。
【００９９】
図３Ａの右側に、左側に示された５つの制御状態とそれらの関連する継続時間およびタスクを示す。Ｔwaitは送信機待機状態ＷＡＩＴTX３１０に関連する時間、ＴTXは送信状態ＴＲＡＮＳＭＩＴ１８０に関連する時間、Ｔrefrは不応状態ＲＥＦＲ３２０に関連する時間、そしてＴlistenはリスニング状態ＬＩＳＴＥＮ１７０に関連する時間である。
【０１００】
上記分解を明らかにするため、追加の状態ＷＡＩＴRXが加えられる。その継続時間は受信機が同期メッセージを復号するのに要する時間Ｔdecに等しい。復号遅延時間は最初は受信機が受信メッセージを処理するために必要とされる時間として定義されたため、Ｔdecはゼロには設定できない。待機状態はＷＡＩＴTXと改名され、送信機はこの状態にＴwaitの間だけとどまる。それゆえ、ノードの送信期間は３つの状態、ＷＡＩＴRX、ＴＲＡＮＳＭＩＴ、ＷＡＩＴTXに分解される。この期間の継続時間は次式のＴに等しい。
Ｔwait＋ＴTX＋Ｔdec＝Ｔ                      （４）
【０１０１】
データはＷＡＩＴRXとＷＡＩＴTXの間に送信することができる。ＴＲＡＮＳＭＩＴはいまは同期ワード（synchronization word）の送信に対応する。Ｔwaitは同期ワードがプリアンブルの場合にはゼロに設定できる。同期シーケンスが例えばＧＳＭ標準におけるようにバーストの中間に位置する場合、ＴwaitとＴdecは等しくあるべきである。ＷＡＩＴRXにおける時間は、受信機が同期メッセージを特定するのに十分な時間がもてるよう、ゼロに設定すべきではない。
【０１０２】
受信期間は継続時間Ｔを有し、それは２つの状態、すなわちＲＥＦＲとＬＩＳＴＥＮ、から成る。受信期間の最大継続時間（つまり位相の増大（increase）がない場合の継続時間）は、以下のＴに等しい。
Ｔrefr＋Ｔlisten＝Ｔ
【０１０３】
受信期間（Receiving Priod）１６４の開始において、ノードは、Ｔrefrに等しい時間の間、不応状態ＲＥＦＲ（refractory）にとどまる。不応状態にいる間に、ノードは、その受信機をオンに切り替える。その位相関数はインクリメントせず、かつ位相の増大（increase）は可能でない。これは伝搬遅延による不安定性を防止する。これについてはY.-W. Hong, B. Sirkeci, and A. Scaglione, "Swarming activities to distribute information in large sensor networks," in Proc. MILCOM Conference, Boston, MA, pp.682-687, Oct. 2003を参照されたい。ＬＩＳＴＥＮの間、位相関数は同期メッセージが受信されるときに調整される。
【０１０４】
タイムアドバンス同期スキームはこのように２つに分解されていることから、ＬＩＳＴＥＮの最後とＷＡＩＴRXの最後に、ノードはＲＥＦＲへ移行するかまたはＷＡＩＴTXへ移行するかいずれかを選択する。この選択は新しい変数“ｎｅｘｔ”に基づいて決定される。これらの移行をまとめた新しい状態機械を図３Ｂに示す。
【０１０５】
図３Ｂに元々のタイムアドバンス同期スキーム（original time advance synchronization scheme）の修正された状態機械、あるいは言い換えると、図３Ａに示した分解された分円図に対応する一般化されたタイムアドバンス同期スキーム（generalized time advanced synchronization scheme）の状態機械の１つの態様、を示す。この状態機械は送信期間（Transmitting Period）１６２と受信期間（Receiving Period）１６４を有する。送信期間１６２は３つの制御状態、つまり送信機待機状態（ＷＡＩＴTX）３１０、送信状態（ＴＲＡＮＳＭＩＴ）１８０、および受信機待機状態（ＷＡＩＴRX）１９０、から成る。
【０１０６】
ノードは送信機待機状態３１０において送信機待機時間ＴwaitTXの間だけ待機し、その後３１２（イベント：wait終了）、送信状態１８０に移行する。元々のタイムアドバンススケジューリングスキームによれば、送信機待機時間はＴwaitとも呼ばれる。送信状態ＴＲＡＮＳＭＩＴ１８０にあるときにノードは同期信号を送信し、その後１８２（イベント：transmit終了）、あるいは言い換えると同期信号長Ｔtransmitの後、受信機待機状態１９０に移行する。ノードは受信機待機時間ＴwaitRXの間だけ待機し、そのときに送信期間１６２を繰り返すべきかまたは受信期間１６２に移行すべきかいずれかを決定する。元々のタイムアドバンススキームによれば、受信機待機時間は復号時間Ｔdecとも呼ばれる。期間変数ｎｅｘｔがＴXに等しい場合（イベント：waitRX終了かつｎｅｘｔ＝ＴX）１９４、ノードは送信機待機状態３１０に移行することで送信期間１６２を繰り返す。ここで値ＴXは送信期間に関連する期間変数の値である。期間変数がＲX（ＲXは受信期間１６４に関連する期間変数の値である）に等しい場合（イベント：waitRX終了かつｎｅｘｔ＝ＲX）１９６、ノードは不応状態３２０に移行することで受信期間１６４に移行する。
【０１０７】
不応状態３２０に移行すると、この不応状態３２０に関連する不応時間Ｔreferの間だけノードはこの状態にとどまり、その後（イベント：refr終了）３２２、リスニング状態１７０に移行する。リスニング状態１７０に移行すると、ノードは、第１の関数（位相関数）に従ってその内部信号値または位相値のインクリメントを開始し（図３Ａの右側も参照）、ノードが近隣ノードからの同期信号を検出した場合には第２の関数（位相応答曲線）に従って内部信号値を増大（increase）させる。位相が閾値に等しくなると（Φ＝Φthreshold）、図３Ａの右側に見られるように、ノードは発火し、受信期間１６４を繰り返すべきかまたは送信期間１６２に移行すべきかいずれかを決定する。期間変数がＲｘに等しい場合（Φ＝Φthresholdかつｎｅｘｔ＝ＲX）１７４、ノードは不応状態３２０に移行することで受信期間１６４を繰り返す。期間変数がＴXに等しい場合（Φ＝Φthresholdかつｎｅｘｔ＝ＴX）１７６、ノードは送信機待機状態３１０へ移行することで送信期間１６２へ移行する。
【０１０８】
状態機械から、変数ｎｅｘｔは期間の最後にのみ、つまりノードがＷＡＩＴRXを脱するまたはノードがＬＩＳＴＥＮを脱するときに評価されることは明らかである。“ｎｅｘｔ”は、期間の最後に動的に決定することができるか、あるいは、ＲｎａｄＳｅｑでラベルされた所定の系列（シーケンス）で定義されることができる。この系列が［‘ＴX’，‘ＲX’，‘ＴX’，‘ＲX’，‘ＴX’，‘ＲX’，．．．］に等しい場合、スキームは元々のタイムアドバンススキームに等しい。
【０１０９】
非リスニング時間（non-listening time）は、装置またはノードがその間に近隣ノードの同期信号をリスニング（つまり受信および／または復号）しない時間として定義される。それゆえ、非リスニング時間は送信期間から成り、本発明の装置が不応状態においてもリスニングをしない実施形態では、斯かる不応状態または関連する不応時間Ｔrefrも含むことがある。
【０１１０】
この場合、非リスニング時間は例えばＴ＋Ｔrefrであることが可能で、受信期間を送信期間なく繰り返すときの異なる非リスニング時間はＴrefrにすぎない。
【０１１１】
提案したソリューションとタイムアドバンススキームを比較すると、提案したスキームは明瞭なままに、いくつかの利点が見て取れる。各ノードはリスニング状態にあるときにそれ自体の時間基準（time reference）を調整し（例えば、位相応答曲線に基づいて位相を増大（increase）させる）、パケットが送信される必要があるときにその時間基準を送信する（例えば、その現時点の基準タイミングに従って同期信号を送信する）。提案のスキームはフレキシブルであり、このことがその実装を非常に魅力的なものにする。元々のタイムアドバンススキームは、送信する必要のあるデータがなくとも、ノードに強制的に交互に受信と送信を行わせる。上述したスキームによれば、ノードは必ずしもこれに従う必要はなく、このためＭＡＣ層に課される制約条件は少なくて済む。
【０１１２】
次に、この系列を修正することで、メッシュ状ネットワークにおいて同期が回復されることを示す。またそのときいかにスキームがＩＥＥＥ８０２．１１標準に直接適用できるかを説明する。
【０１１３】
以下、疑似ランダム系列（pseudo-random sequence）実装とも呼ばれる実施形態についてより詳しく説明する。
【０１１４】
難聴問題を解決するため、近隣ノードは初期状態とは無関係に互いも聞こえるようにすべきである。そうするため、２つの近隣ノードのｎｅｘｔ系列は理想的には直交（orthogonal）すべきである。そうすれば、１つのノードが送信しているときは、他方のノードはリスニングしている可能性が高い。しかしながら、ノードは系列が直交性を保つために始めから同期される必要があることから、直交系列は現実的でない。より現実的な方策として、良好な相互相関特性を有する疑似ランダム系列が議論される。これはゴールド系列（Gold sequences）のケースである（D. Sarwate and M. Pursley, "Cross correlation properties of pseudorandom and related sequences," Proc. IEEE, vol. 68, pp. 593-619参照）。
【０１１５】
斯かる系列を一般化されたタイムアドバンスストラテジーで使用するとき、ノードＡは最初にゴールド系列の集合Ｇ（ｕ，ｖ）から系列ＲａｎｄＳｅｑAをランダムに選択し、それを利用して次の期間における自分の挙動を以下の条件に従って受信（Receiving）なのか送信（Transmitting）なのかいずれかを決定することになる。
・ＲａｎｄＳｅｑA（ｉA）＝０の場合、ｎｅｘｔ（ｉA）＝‘ＲX’
・ＲａｎｄＳｅｑA（ｉA）＝ｌの場合、ｎｅｘｔ（ｉA）＝‘ＴX’
ｉAは各タイムスロットの最後（ＬＩＳＴＥＮの最後またはＷＡＩＴRXの最後）にインクリメントされるカウンタである。
【０１１６】
ゴールド系列の特性のおかげで、２つのノードが同一のランダム系列を選択しない限り、ノードが互いに決して聞こえないというケースは避けられる。
【０１１７】
修正された同期スキームをそのオリジナル版と比較するため、提案スキームが前節と同じ制約条件でネットワークＮＷ１に適用される。遅延時間はＴdec＝０．１・ＴとＴrefr＝ＴTXに固定される。各シミュレーションは１５０．Ｔの間だけ実行され、この期間内に同期が実現されない場合は、同期は不成功と見なされる。各期間は１５００ステップに分解される。カプリング設定はｂ＝３とε＝０．２に設定される。
【０１１８】
ゴールド系列Ｇ（ｕ，ｖ）の集合は、ｍ＝１０、ａ＝７、ｔ（ｚ）＝ｚ-7＋ｚ-3、およびｋ＝３から成る設定に従って生成される。４００個未満の‘１’を有する系列は破棄され、系列は同一シンボルが連続する数Ｎconsecが多すぎないように修正された。Ｎconsecは５を限度とする。
【０１１９】
図４Ａおよび図４Ｂは各ＴTXごとに１０００セットの初期条件に基づく両方の同期スキームに対する同期結果をプロットした図である。
【０１２０】
図４Ａに同期信号長ＴTXを期間Ｔで規格化したもの（ＴTX／Ｔ）に対する同期率（％）を示す。プロット４１０は元々のタイムアドバンススキームに対するもの、プロット４２０はゴールド系列に基づいて期間変数‘ｎｅｘｔ’を決定する修正または一般化されたタイムアドバンススキームに対するものである。図４Ｂに同期信号長ＴTXを期間Ｔで規格化したもの（ＴTX／Ｔ）に対する同期までの平均時間（平均同期時間）を示す。プロット４３０は元々のタイムアドバンススキームに対するもの、プロット４４０はゴールド系列を利用して期間変数値を決定する一般化されたタイムアドバンススキームに対するものである。
【０１２１】
同期スキームの修正のおかげで、０．１・Ｔと０．５・Ｔの間で変化するＴTXに対して同期が回復された。同期までの平均時間は修正版タイムアドバンススキームでは特にＴTXの低い値に対しては相対的に大きい。
【０１２２】
次に、確率過程（random process）に基づいて期間変数を決定する代替的な実施形態（以下、ランダム送信形態と呼ぶ）についてより詳しく説明する。
【０１２３】
修正版タイムアドバンススキームのより直接的な適用例として、期間変数ｎｅｘｔを決定する系列ＲａｎｄＳｅｑは各ノードがランダムに生成することができ、Ｎconsecに対する制約もこの系列に適用される。
【０１２４】
このスキームは前節と同じ条件でＮＷ１に適用される。遅延時間はＴdec＝０．１・ＴとＴrefr＝０．４・Ｔに固定される。各シミュレーションは１５０．Ｔの間だけ実行され、この期間内に同期が実現されない場合は、同期は不成功と見なされる。各期間は１５００ステップに分解される。カプリング設定はｂ＝３とε＝０．２に設定される。
【０１２５】
図５Ａおよび図５Ｂは各ＴTXごとに１０００セットの初期条件に基づくランダム系列同期スキームに対する同期結果をプロットした図である。
【０１２６】
図５Ａに同期信号長ＴTXを期間Ｔで規格化したもの（ＴTX／Ｔ）に対する同期率（％）を示す。プロット４１０は元々のタイムアドバンススキームに対するもの、プロット４２０はゴールド系列を利用する一般化されたタイムアドバンススキームに対するもの、プロット５３０は各ノードによるランダム生成に基づく期間変数値を決定する一般化されたタイムアドバンススキームに対するものである。図５Ｂに同期信号長ＴTXを期間Ｔで規格化したもの（ＴTX／Ｔ）に対する同期までの平均時間を示す。プロット４３０は元々のタイムアドバンススキームに対するもの、プロット４４０はゴールド系列を利用する一般化されたタイムアドバンススキームに対するもの、プロット５５０はランダム送信に対する一般化されたタイムアドバンススキームに対するものである。
【０１２７】
結果は同期が常に得られることから非常に勇気付けられるものである。同期までの時間はゴールド系列が使用されるときよりもずっと低い。この結果は不応遅延時間が０．４・Ｔに固定されていることから来ている。しかしそれは以前はＴTXに設定されていた。それゆえ、Ｔrefrを一定値に設定することが好ましい。
【０１２８】
次に、ローカル同期（local synchrony）に基づいて期間変数を決定する別の実施形態（以下、ローカル同期形態と呼ぶ）についてより詳しく説明する。
【０１２９】
メッシュ状ネットワークでは、ノードはその近隣ノードとだけ直接通信することができ、それゆえ、全体のネットワークのうちのローカルな視野を持つに過ぎない。その意味において、ノードはそれがローカルに同期化されたかどうかを検出することだけができる。元々のタイムアドバンス同期スキームに従う場合、それは孤立したときまたは同期に到達した場合にはどのメッセージも位相調整を引き起こさないために２・Ｔごとに発火する。
【０１３０】
この情報（２Ｔごとに発火するということ）はｎｅｘｔ変数の値を決定するために使用することができる。ローカルな同期を待機するときは、ノードは、例えばしばらくの間は元々のタイムアドバンスストラテジーに従う。それがＮstable周期（Ｎstable・２・Ｔ秒）の間に定期的に発火すれば、それはローカルに同期化されたと見なすことができる。現実にそうなっているなら、２つのグループが形成されており、ノードは同期状態を乱すことなくグループを切り替えるために期間変数ｎｅｘｔを‘ＲX’に設定することができる。
【０１３１】
図６にローカルな同期を検出するときのｎｅｘｔの系列を示す。
【０１３２】
図６の実施形態において、ノードは元々のタイムアドバンススキームと同様にそれがローカルな同期６１０を宣言するまで、受信期間から送信期間へ、同じく送信期間から受信期間へ移行する。ノードがいる特定の実行状態および／または特定の期間に応じて、そのノードは図６に示すように受信期間または送信期間を繰り返すように構成することがきでる。
【０１３３】
全てのノードが同じ挙動を有する状況を避けるため、同期スキームにある程度のランダム性を加えることが可能である。端的には、ノードがローカルな同期を検出するときにそのノードは確率ｐswitchでグループを切り替える。代わりに、ランダム性はＭＡＣ層のランダムバックオフ（random backoff）を利用して加えることが可能である。つまり切替前にある数のタイムスロットを待機する。
【０１３４】
図７Ａと図７Ｂにこのスキームに対する１０００個の初期状態に基づくシミュレーション結果を示す。セッティングはＴdec＝０．１・Ｔ、Ｔrefr＝ＴTX、ｂ＝３、およびε＝０．７、Ｎstable＝４に設定される。
【０１３５】
図７Ａに同期信号長ＴTXを期間Ｔで規格化したもの（ＴTX／Ｔ）に対する同期率（％）を示す。プロット４１０は元々のタイムアドバンススキームに対するもの、プロット５３０はランダム送信を利用する一般化されたタイムアドバンススキームに対するもの、プロット７４０はローカルな同期を利用する一般化されたタイムアドバンススキームに対するものである。図７Ｂに同期信号長ＴTXを期間Ｔで規格化したもの（ＴTX／Ｔ）に対する同期までの平均時間を示す。プロット４３０は元々のタイムアドバンススキームに対するもの、プロット５５０はランダム送信を利用する一般化されたタイムアドバンススキームに対するもの、プロット７６０はローカルな同期を利用する一般化されたタイムアドバンススキームに対するものである。
【０１３６】
ＴTXの低い値に対しては、同期までの平均時間は提案したスキームではランダムスキームよりもずっと低い。これは勇気付けられる結果であり、グループを切り替える前に安定性を待つことがランダムであるよりも効果的であることを示しているように見える。
【０１３７】
一般化されたタイムアドバンス同期スキームはＩＥＥＥ８０２．１１標準の物理層に直接適用することが可能である。この標準はタイムスロット化したＭＡＣプロトコルは使用せず、代わりにＣＳＭＡ／ＣＡ（Carrier Sense Multiple Access/Collision Avoidance）ベースのプロトコルを使用する。ＥＲＰ（ERP=Extended Rate PHY）ＯＦＤＭ版８０２．１１標準で使用されるＯＦＤＭ（Orthogonal Frequency Division Multiplexing）バーストの周知フレーム構造を利用することで、一般化されたタイムアドバンススキームはＴwait、ＴTX、およびＴdecを適切に選ぶことによって直接構成することが可能である。
【０１３８】
８０２．１１ＥＲＰ・ＯＦＤＭフレームのフォーマットは信号検出と同期の目的に使用されるプリアンブル（preamble）を常に含む。このプリアンブルは同期スキームの同期ワード（synchronization word）として利用される。この同期ワードを受信するとき、フレームに含まれるデータとは無関係に、ノードはそれに応じてその位相をインクリメントする。
【０１３９】
前節で提案された異なるスキームから、ローカルな同期を待つことは最も効果的のように思われる。しかしながら、ランダム系列スキームはアドホック・ネットワークに最も自然に適合する。というのも、パケットが到達するとＭＡＣプロトコルはランダムに送受信するからである。この固有の特徴を同期スキームに組み合わせることで、ノードはシームレスに同期することになり、より効率的な通信が可能となる。
【０１４０】
図８の上側に、"Wireless LAB medium access control(MAC) and physical layer(PHY) specifications," 1999に記述された、８０２．１１標準で使用されるＥＲＰ・ＯＦＤＭバーストのフレーム構造を示す。また図８の下側に、対応する送信期間と受信期間の一例を示す。
【０１４１】
この図から分かるように、“プリアンブル（preamble）”は、全てのフレームに出現し、１６μｓのプリアンブル８１０と４μｓのヘッダ８２０から構成される。フレームに含まれるＯＦＤＭシンボル数は可変である。しかしながらタイムスロット化したプロトコルに対しては、固定されたタイムスロット継続時間を使用することが必要で、かつより効果的である。それゆえ、ＤＡＴＡ８３０内のＯＦＤＭシンボル数ＮDATAは、同期スキームを、タイムスロット化したＭＡＣプロトコルに適用するために固定される。各シンボルは４μｓの継続時間を有する。このためＤＡＴＡ８３０の継続時間はＮDATA・４μｓに等しい。それゆえ、フレームの全長は、継続時間Ｔの１送信期間に対応し、次式に等しい。
１６μｓ＋４μｓ＋ＮDATA・４μｓ＝Ｔ                （５）
【０１４２】
図８に示されたプリアンブルから、同期に使用される同期ワードはプリアンブル８１０の最初の部分８４０（この部分は信号検出と粗周波数オフセット推定に利用される）である必要があるだけある。この部分の継続時間は８μｓに等しい。この同期ワードが定義されるには、プリアンブルベースの同期スキームが必要である。それゆえ、一般化されたタイムアドバンスアルゴリズムに従うノードの送信期間は次のように設定される。Ｔwait＝０μｓ、ＴTX＝８μｓ（８４０）およびＴdec＝１２μｓ＋ＮDATA・４μｓ（８５０）。ＴＲＡＮＳＭＩＴの間にプリアンブル８４０の最初の部分が送信される。従って、４つの状態（リスニング状態１７０、送信状態１８０、受信機待機状態１９０および不応状態３２０）を有する状態モデル（state model）が使用される。受信機待機状態ＷＡＩＴRXの間に、ペイロードデータを含むフレームの残りの部分８５０が送信される。図９に１タイムスロットの間の送信機の挙動を示す。
【０１４３】
一般化されたタイムアドバンススキームでは、受信機は同期メッセージが送信されていることを宣言する前にプリアンブルまたはプリアンブルの一部のみを識別する必要がある。プリアンブルが受信されると受信機はそのＴdec秒後にその位相をインクリメントする。ここではＴdecは、同期メッセージを復号するために必要な時間に相当するのではなく、ＤＡＴＡの継続時間に相当する。それゆえ、必要な復号時間はＴdec＝ＮDATA・４μｓ以下であると想定される。
【０１４４】
これを遂行するのを理解する助けとして、図１０に３つのノードの挙動を例示する。最上部の１０１０は３つの連続した８０２．１１フレーム１００２、１００４、１００６を送信している。２番目の１０２０はすでに同期化しており、プリアンブルを識別してもその位相は調整しない。３番目の１０３０は送信機が送信を開始してからＴ秒後にその位相を徐々に調整する。
【０１４５】
元々のスキームと一般化されたスキームとの間の重要な違いは同期メッセージを受信するときのノードの挙動に関する。元々のタイムアドバンススキームでは、ノードが同期メッセージを完全に受信し復号し終わる前に発火した場合、そのノードはＷＡＩＴに移行し、部分的に受信したメッセージを破棄する。図１０から観察できるように、０とＴの間（フレーム１００２）に、未同期ノード１０３０は同期メッセージを完全に受信し終わる。しかしながら、それはその同期メッセージを復号している間に発火１０４０する。この瞬間に、そのノードは送信期間または受信期間のいずれかに入ることができる。例えば、それは受信期間に移行し、ｔ＝Ｔにおいて、すなわちメッセージが受信されてからＴdec後に、その位相を調整する。もしそれが送信期間に入っていた場合には、それはｔ＝Ｔにおいてその位相をインクリメントすることは可能ではなかった。この場合、２つの選択が可能である。受信メッセージを破棄するか、または受信期間に戻るときに位相をインクリメントする。以前示されたシミュレーション結果では、ＴＲＡＮＳＭＩＴに入るときに不完全なメッセージは破棄された。
【０１４６】
図１０から更に観察できるように、Ｔと２Ｔの間（フレーム１００４）で、未同期の１０３０は同期信号を完全に受信し終わる。しかしながら、それはその同期信号を受信中に発火１０６０する。この瞬間に、未同期ノードは送信期間または受信期間のいずれかに入ることができる。例えば図１０に示すように、それは再び受信期間に入り、ｔ＝２Ｔ（１０７０）、すなわち同期信号が受信されてからＴdec後に、その位相を調整する。ノード１０３０が送信期間に入っていた場合には、それはｔ＝２Ｔにおいてその位相をインクリメントすることは可能ではなかった。この場合、２つの選択が可能である。受信期間に戻るときに同期信号の失っている部分の受信を継続するか、またはより好ましくは、部分的に受信した同期信号を破棄する。
【０１４７】
それゆえ、ノードは、連続して繰り返される受信期間の中で近隣ノードの同期信号の受信もしくは復号を継続する働きをするか、または部分的に受信した同期信号および／または部分的に復号した同期信号を連続して繰り返される受信期間の中で破棄する働きをすることができる。
【０１４８】
ｔ＝２Ｔ（１０７０）において、未同期ノード１０３０はその位相を増大（increase）するだけでなく閾値にも到達する、すなわち発火する。その結果、ｔ＝２Ｔ（１０７０）の時点から、３つのノード１０１０、１２０および１０３０は全て同期する。
【０１４９】
前述したように、送信機１０１０がフレーム１００２と１００４でペイロードデータを最初は同期していない未同期ノード１０３０へではなく同期済みの同期ノード１０２０へ送信したいと考える場合、未同期ノード１０３０はそれでもなおフレーム１００２と１００４のプリアンブルの最初の部分８４０を使って送信機１０１０と同期する。
【０１５０】
送信機１０１０が最初は未同期のノード１０３０へペイロードデータをフレーム１００２で送信したいと考える場合、ノード１０３０は同期信号としてプリアンブルの最初の部分８４０を検出することが可能であるがペイロードデータＤＡＴＡを正確に受信することはできない。ノードがペイロードデータを成功裏に受信したことを確認応答するために追加的にＡＣＫ（acknowledge）ベースのプロトコルを利用する実施形態では、最初は未同期のノード１０３０は送信機１０１０へＡＣＫ信号を送信しない。ＡＣＫがなければ、送信機１０１０はフレーム１００４でペイロードデータを未同期ノード１０３０へ再送する。この場合も同様に、ノード１０３０はペイロードデータを正しく受信せず、ＡＣＫを送信しない。それゆえ、送信機１０１０は再びペイロードデータをノード１０３０へ今度はフレーム１００６で再送する。ノード１０３０はこのときは送信機１０１０と同期しているのでペイロードデータを正しく受信することが可能である。このため、同期位相とペイロード送信位相を区別する必要は一切ない。
【０１５１】
上述したことをまとめると、本発明は例えば分散型無線ネットワークのタイミング同期に関係した問題に対処する。上述した同期ストラテジーは自然界に観察される自発的な同期現象（例えば東南アジアにおいてホタルの大群が完全に同期して点滅する現象）に基づく。先の特許出願（EP 05015250.3）において、このモデルが無線ネットワークに適応するようにした。このモデルはタイムアドバンス同期（time advance synchronization）とも称され、完全メッシュ状ネットワークにおいて実現可能な精度を改善した。このタイムアドバンス同期スキームをメッシュ状ネットワークへ直接適用すると、ノードが少数の近隣ノードしか持たないときに同期が妨げられる。ノードは送信中は受信できないので、初期状態が原因で近隣ノードがほとんど同時に送信し、決して互いに同期しないことが起こりえる。本願の一般化されたタイムアドバンス同期スキームはノードにより多くのフレキシビリティを与えることでこの状況を避けることができる。原理は本質的に明瞭であって、多種多様な遅延に対してローバスト性を呈し、それゆえ、例えば分散型ＣＤＭＡ、ＯＦＤＭ、ＴＤＭＡ（time division multiple access）、時間的に構造化されたＦＤＭＡ（frequency division multiple access）またはＩＤＭＡ（interleave division multiple access）をベースとする無線ネットワークに対する同期プロトコルとして最適である。
【０１５２】
ノードは、送信中に受信することができない（難聴（deafness））ので、近隣ノードはお互いの同期信号を聞きたくても聞こえないという状況が起こり得る。一般化されたタイムアドバンス同期（time advance synchronization）スキームはこの状況をノードにより柔軟性を持たせることによって避ける。この原理は本質的に明瞭で、ＩＥＥＥ８０２．１１などの既存システムに組み入れることは比較的容易である。このため、同期位相とデータ送信位相を区別する必要性も一切ない。
【０１５３】
本発明の方法の一定の実施要件に応じて、本発明の方法はハードウェアまたはソフトウェアで実施が可能である。本発明の実施は、本発明の方法が実行されるようにプログラマブルなコンピュータシステムと協働することができるデジタル記憶媒体、特に電子的に可読な制御信号が保存された磁気ディスク、ＤＶＤまたはＣＤを使用して行うことができる。一般に、本発明は従ってコンピュータ上で走らせたときに本発明の方法を実行する働きをするプログラムコードが機械可読媒体に記憶されたコンピュータ・プログラム製品である。言い換えると、本発明の方法は、コンピュータ上で走らせたときに本発明の少なくとも１つの方法を実行するためのプログラムコードを有するコンピュータ・プログラムである。
【図面の簡単な説明】
【０１５４】
【図１Ａ】本発明の装置の例示的なブロック図である。
【図１Ｂ−１Ｃ】図１Ｂは、本発明の装置の状態を記述する状態機械を示す図である。図１Ｃは、図１Ｂの状態機械に基づく例示的な分円図である。
【図２Ａ】ノードＡが送信を開始するときのタイムアドバンスシステムの状態の例示的な分円図である。
【図２Ｂ】ノードＡの受信機が成功裏に同期信号を受信・復号し終わったときの例示的なタイムアドバンスシステムの状態を示す図である。
【図２Ｃ】ノードＡが受信機をオンにするときのタイムアドバンスシステムの状態の例示的な分円図である。
【図２Ｄ】タイムアドバンスストラテジーによる受信機と送信機の分解を示す例示的な分円図である。
【図２Ｅ】１つまたは２つの近隣ノードしか持たない８つのノードから成るある特定のネットワークトポロジーＮＷ１を示す図である。
【図２Ｆ】タイムアドバンス同期スキームを図２ＥのネットワークＮＷ１に直接適用したときの同期信号長に対する同期率をプロットした図である。
【図２Ｇ】タイムアドバンス同期スキームを図２ＥのネットワークＮＷ１に直接適用したときの同期信号長に対する同期までの平均時間（平均同期時間）をプロットした図である。
【図３Ａ】タイムアドバンススキームを構成する状態の送信期間と受信期間への分離とそれぞれの状態の継続時間を示す例示的な分円図である。
【図３Ｂ】本発明の実施の一形態によるタイムアドバンス同期スキームの例示的な修正された状態機械を示す図である。
【図４Ａ】ゴールド系列と組み合わせた一般化されたタイムアドバンス同期スキームを（図２ＥのネットワークＮＷ１へ）適用したときの同期率と、元々のタイムアドバンス同期スキームを適用したときの同期率を比較するための図である。
【図４Ｂ】ゴールド系列と組み合わせた一般化されたタイムアドバンス同期スキームを（図２ＥのネットワークＮＷ１へ）適用したときの同期までの平均時間と、元々のタイムアドバンス同期スキームを適用したときの同期までの平均時間を比較するための図である。
【図５Ａ】ゴールド系列と組み合わせた一般化されたタイムアドバンス同期スキームを適用したときの同期率と、ランダム送信と組み合あわせた一般化されたタイムアドバンス同期スキームを適用したときの同期率と、元々のタイムアドバンス同期スキームを適用したときの同期率を比較するための図である。
【図５Ｂ】ゴールド系列と組み合わせた一般化されたタイムアドバンス同期スキームを適用したときの同期までの平均時間と、ランダム送信と組み合あわせた一般化されたタイムアドバンス同期スキームを適用したときの同期までの平均時間と、元々のタイムアドバンス同期スキームを適用したときの同期までの平均時間を比較するための図である。
【図６】ローカル同期を検出するときの例示的な一連の期間変数値を示す図である。
【図７Ａ】ローカル同期検出と組み合わせた一般化されたタイムアドバンス同期スキームを適用したときの同期率と、ランダム送信と組み合わせた一般化されたタイムアドバンス同期スキームを適用したときの同期率と、元々のタイムアドバンス同期スキームを適用したときの同期率を比較するための図である。
【図７Ｂ】ローカル同期検出と組み合わせた一般化されたタイムアドバンス同期スキームを適用したときの同期までの平均時間と、ランダム送信と組み合わせた一般化されたタイムアドバンス同期スキームを適用したときの同期までの平均時間と、元々のタイムアドバンス同期スキームを適用したときの同期までの平均時間を比較するための図である。
【図８】８０２．１１フレーム構造と、送信期間および受信期間の例示的な割り当てを示す図である。
【図９】一般化されたタイムアドバンスストラテジーを８０２．１１フレームで使用する送信機の例示的な挙動を示す図である。
【図１０】フレーム構造と一般化されたタイムアドバンス同期スキームの組み合わせに対する３つのノードの例示的な同期化を示す図である。
【図１１Ａ】ノードのそれぞれの伝送距離を表現する図である。
【図１１Ｂ】近隣ノード間のそれぞれのリンクを表現する図である。
【図１２Ａ】積分発火型発振器の例示的な位相ダイアグラムを示す図である。
【図１２Ｂ】図１２Ａの積分発火型発振器の分円図である。
【図１３Ａ】２つの積分発火型発振器の同期化の過程を例示する図である。
【図１３Ｂ】分円表現に基づいて２つの積分発火型発振器の同期化の過程を例示する図である。
【図１３Ｃ】位相インクリメント（位相増分）が位相応答曲線からどのように得られるかを示す図である。
【図１３Ｄ】例示的な積分関数と例示的な位相応答曲線を示す図である。
【図１４Ａ】タイムアドバンスストラテジーを使用するノードの状態機械を示す図である。
【図１４Ｂ】図１４Ａに示した状態機械を使用するノードに対する位相を時間の関数としてプロットした図である。
【図１４Ｃ】伝搬遅延が伴う例示的なチャネルモデルを示す図である。
【符号の説明】
【０１５５】
１１０  受信機
１２０  処理装置
１３０  送信機
１４０  同期信号
１５０  検出信号
１６０  生成信号
１６２  送信期間
１６４  受信期間
１７０  リスニング状態（第１の制御状態）
１７２  発火点
１８０  送信状態（第２の制御状態）
１９０  受信機待機状態（第３の制御状態）
３１０  送信機待機状態（第５の制御状態）
３２０  不応状態（第４の制御状態）
【図１Ａ】
0004418481.tif 000006
【図１Ｂ−１Ｃ】
0004418481.tif 000007
【図２Ａ】
0004418481.tif 000008
【図２Ｂ】
0004418481.tif 000009
【図２Ｃ】
0004418481.tif 000010
【図２Ｄ】
0004418481.tif 000011
【図２Ｅ】
0004418481.tif 000012
【図２Ｆ】
0004418481.tif 000013
【図２Ｇ】
0004418481.tif 000014
【図３Ａ】
0004418481.tif 000015
【図３Ｂ】
0004418481.tif 000016
【図４Ａ】
0004418481.tif 000017
【図４Ｂ】
0004418481.tif 000018
【図５Ａ】
0004418481.tif 000019
【図５Ｂ】
0004418481.tif 000020
【図６】
0004418481.tif 000021
【図７Ａ】
0004418481.tif 000022
【図７Ｂ】
0004418481.tif 000023
【図８】
0004418481.tif 000024
【図９】
0004418481.tif 000025
【図１０】
0004418481.tif 000026
【図１１Ａ】
0004418481.tif 000027
【図１１Ｂ】
0004418481.tif 000028
【図１２Ａ】
0004418481.tif 000029
【図１２Ｂ】
0004418481.tif 000030
【図１３Ａ】
0004418481.tif 000031
【図１３Ｂ】
0004418481.tif 000032
【図１３Ｃ】
0004418481.tif 000033
【図１３Ｄ】
0004418481.tif 000034
【図１４Ａ】
0004418481.tif 000035
【図１４Ｂ】
0004418481.tif 000036
【図１４Ｃ】
0004418481.tif 000037