(57)【要約】本発明は、分散型システムの各ノードでオフセット補正とクロックレート補正を同時に行うことによってリアルタイム用に意図された前記分散型システムの改良されたクロック同期アルゴリズムを提供する。これによって、高価な発振器を避けることが可能であり、同期を高速でかつ高精度で達成できる。
2004536538.tif 000002
【特許請求の範囲】
【請求項１】
リアルタイム処理用の分散型システムのノード（１）の同期方法において、
該分散型システムのノード（１）は、通信リンク（３）によって相互接続され、ノード（１）の各々は局所クロック（２）とメッセージが他のノードから何時受信されるタイミングを示す情報を含み、各ノード（１）は少なくとも全てのノード（１）のサブセットを構成し、局所クロック（２）同期させるために、
(a) 他のノード（１）からのメッセージを受信する受信工程、
(b) 前記サブセットに属する他の全てのノード（１）と自己の局所クロック（２）の間の１組の時間ずれを決める工程であって、時間ずれは、受信メッセージの予測受信時点と自己の局所クロック（２）との時間に基づいて観測された実際の受信時点との差を測定することによって決定する時間ずれ決定工程、
(c) 前記サブセットの他の各ノード（１）から受信した2つの連続したメッセージに基づいて、自己の局所クロック（２）と前記ノード（１）のサブセットに属する他の全てのノード（１）との間の１組のクロックレートのずれを決定するクロックレートずれ決定工程、
(d) 前記決定された一組の時間ずれに基づいてオフセット補正値を計算し、前記決定された一組のクロックレートずれに基づいてクロックレート補正値を計算する計算工程、および
(e) 前記オフセット補正値並びに前記クロックレート補正値に基づいて前記局所クロックを調整する調整工程
を含む工程を行うことを特徴とする前記同期方法。
【請求項２】
前記時間ずれ決定工程(b)は、第１組の時間ずれ及び第2組の時間ずれを決定し、
前記第クロックずれ決定工程(c)は、前記第1組の時間ずれ及び第2組の時間ずれに対応する時間ずれ間の差を計算することによって前記一組のクロックレートずれを決定することを特徴とする請求項１に記載の同期方法。
【請求項３】
前記計算工程(d)は、前記第2組の時間ずれに基づいてオフセット補正値を計算することを特徴とする請求項２に記載の同期方法。
【請求項４】
前記クロックずれ決定工程(c)は、予測された時間間隔と観測された時間間隔との間の差を測定することによってクロックレートずれを決定し、前記予測された時間間隔は、特定のノードにおいて連続して受信されたメッセージの予測された時点間の時間間隔であり、前記予測された時間間隔は、自己の局所クロック(2)の時間に基づいて観測されたメッセージの実際の受信時点間の時間間隔である、ことを特徴とする請求項１に記載の同期方法。
【請求項５】
前記クロックずれ決定工程(c)は、次の工程、すなわち
(c1)  自己の局所クロック(2)の時間に基づいて前記サブセット中の特定のノードに対して連続して受信されたメッセージの実際の受信時点間の時間間隔をカウントする工程と、
(c2)  特定のノード(1)に対するカウントされた時間間隔と、特定のノード(1)に対するメッセージの予測された受信時点に基づく予測時間間隔との間のクロックレート差を計算する工程
を実行することによって前記一組のクロックレートずれの各クロックレートずれを決定することを特徴とする請求項４記載の同期方法。
【請求項６】
前記分散型システムは、タイムトリガーシステムであることを特徴とする請求項1乃至５のいずれかに記載の同期方法。
【請求項７】
前記ノード(1)に含まれた前記情報は、前記分散型システムの各ノード(1)に対して、特定のノード(1)が前記通信リンク(3)上にメッセージを送ること可能な一定のタイムスロットを定義することを特徴とする請求項1乃至６のいずれかに記載の同期方法。
【請求項８】
前記ノード(1)に含まれた情報は、所定の時間間隔内での前記通信リンク(3)に対する各ノード(1)の一回のアクセスを定義することを特徴とする請求項1乃至７の何れかに記載の同期方法。
【請求項９】
前記分散型システムにおけるノード(1)の前記通信リンク(3)に対する同一の所定の一時的アクセスパターンを有する時間間隔が連続的に繰返されることを特徴とする請求項８に記載の同期方法。
【請求項１０】
各ノード(1)は、前記所定のアクセスパターンに従って前記通信リンク(3)に対してアクセスしたとき自己のメッセージを送信することを特徴とする請求項８又は９に記載の同期方法。
【請求項１１】
前記計算工程(d)は、前記一組の決定されたクロックレートずれ中の2つのクロックレートずれに基づいて前記クロックレート補正値を第1の所定のルールに従って計算することを特徴とする請求項1乃至１０の何れかに記載の同期方法。
【請求項１２】
前記第1の所定ルールは、互いに最大差を有する2つのクロックを選択することを特徴とする請求項１１に記載の同期方法。
【請求項１３】
前記第1の所定ルールは、第2の所定ルールに従ってクロックレートずれを排除する請求項１１又は１２に記載の同期方法。
【請求項１４】
前記計算工程(d)は、前の調整工程の間に適用されたクロックレート補正値を現在計算されたクロックレート補正値とともに増加させることによって前記クロックレート補正値を計算することを特徴とする請求項１乃至１０の何れかに記載の同期方法。
【請求項１５】
前記計算工程(d)によって与えられたクロックレート補正値を第3の所定ルールに従って変更する工程をさらに含むことを特徴とする請求項１乃至１４の何れかに記載の同期方法。
【請求項１６】
前記第3の所定ルールは、前記計算されたクロックレート補正値を幾分減少した量を有する値で置換することを特徴とする請求項１５に記載の同期方法。
【請求項１７】
(e) 前記オフセット補正値及び前記クロックレート補正値に基づいて前記局所クロック(2)を調整する調整工程(e)は、各々所定の時間間隔内での前記通信リンク(3)に対する各ノード(1)の一回のアクセスを定義する所定の数の時間間隔の後に、両補正値について実行されることを特徴とする請求項１乃至１６の何れかに記載の同期方法。
【請求項１８】
請求項１乃至１７に記載の同期方法を実行するように構成されたコード手段を備えたコンピュータプログラム。
【請求項１９】
リアルタイム処理用の分散型システムのノード（１）の同期方法において、
該分散型システムのノード（１）は、通信リンク（３）によって相互接続され、前記同期ユニットは、
局所クロック（２）、
受信メッセージの予測受信時点と自己の局所クロック（２）との時間に基づいて観測された実際の受信時点との差を測定することによって、自己の局所クロック（２）と他のノード（１）との間の１組の時間ずれを決定し、他の各ノード（１）から受信した2つの連続したメッセージに基づいて、自己の局所クロック（２）と他の全てのノード（１）との間の１組のクロックレートのずれを決定するずれ検出器、
前記決定された一組の時間ずれに基づいてオフセット補正値を計算し、前記決定されたクロックレートずれに基づいてクロックレート補正値を計算する補正値計算ユニット、
前記オフセット補正値並びに前記クロックレート補正値に基づいて前記局所クロックを調整する調整ユニット、
を備えたことを特徴とする前記同期ユニット。
【請求項２０】
前記ずれ検出器は第１組の時間ずれ及び第2組の時間ずれを決定し、前記第1組の時間ずれ及び第2組の時間ずれに対応する時間ずれ間の差を計算することによって前記一組のクロックレートずれを決定するように構成されていることを特徴とする請求項１９に記載の同期ユニット。
【請求項２１】
前記補正値計算ユニットは、前記第２組の時間ずれに基づいてオフセット補正値を計算することを特徴とする請求項２０に記載の同期ユニット。
【請求項２２】
前記ずれ検出器は、予測された時間間隔と観測された時間間隔との間の差を測定することによってクロックレートずれを決定し、前記予測された時間間隔は、特定のノードにおいて連続して受信されたメッセージの予測された時点間の時間間隔であり、前記予測された時間間隔は、自己の局所クロック(2)の時間に基づいて観測されたメッセージの実際の受信時点間の時間間隔である、ことを特徴とする請求項１９に記載の同期ユニット。
【請求項２３】
前記ずれ検出器は、自己の局所クロック(2)の時刻に基づいて特定のノードに対して連続して受信されたメッセージの実際の受信時点間の時間間隔をカウントするカウンタを備えたことを特徴とする請求項２２に記載の同期ユニット。
【請求項２４】
前記メモリは、前記分散型システムの各ノード(1)に対して、特定のノード(1)が前記通信リンク(3)上にメッセージを送ることを可能とする一定の一時的アクセスパターンを定義する情報を記憶することを特徴とする請求項１９乃至２３のいずれかに記載の同期方法。
【請求項２５】
前記ノード(1)に含まれた情報は、所定の時間間隔内での前記通信リンク(3)に対する各ノード(1)の一回のアクセスを定義することを特徴とする請求項１９乃至２４の何れかに記載の同期ユニット。
【請求項２６】
各ノード(1)は、前記所定のアクセスパターンに従って前記通信リンク(3)に対してアクセスしたとき自己のメッセージを送信する送信器をさらに備えたことを特徴とする請求項１９乃至２５に記載の同期ユニット。
【請求項２７】
前記局所クロックと他のクロックとの間に決定された時間ずれを記憶するずれメモリをさらに備えたことを特徴とする請求項１９乃至２６の何れかに記載の同期ユニット。
【請求項２８】
前記メモリは２組の時間ずれを記憶するように構成されていることを特徴とする請求項２７に記載の同期ユニット。
【請求項２９】
前記補正値計算ユニットによって与えられたクロックレート補正値を変更し、該変更したクロックレート補正値を前記調整ユニットに送るドリフト保護手段を更に備えたことを特徴とする請求項１９乃至２８に記載の同期ユニット。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リアルタイム処理用分散型システムの同期に関し、特に各ノードの局所リアルタイムクロックを有する該分散型システムのノードを同期させる方法および各ノードに含まれる同期ユニットに関する。
【背景技術】
【０００２】
分散型システムは、通信リンクによって接続されたいくつかのノードからなる。分散型リアルタイムシステムの各ノードは、自己の局所リアルタイムクロックを含む。これらのクロックの精度は、各局所クロックに含まれる水晶の精度を基礎としている。分散型システムによって制御されるリアルタイムの適用には、ノードの局所クロックの同期が必要である。同期時間は一般に「グローバルタイム」と呼ばれる。
【０００３】
分散型システムでは、グローバルタイムは、リアルタイムでの適用にとって重要な機能性である。リアルタイムタスクは例えば、異なったノードのタスクからのメッセージに依存することがある。このようなタスクを予定するには、単に局所的ではなく意味のある情報が必要である。しかし、異なったノードにクロックを含むシステムは、必ずしも全て同時間を示すものではない。通常、クロック間にはオフセットがあり、これらのクロックはしばしば、全く同一の周波数で動作するわけではない。また、この周波数は、一定であるわけではなく、例えば、温度に依存する。
【０００４】
ノード間の内部同期は、参照時間源に対する外的同期から区別される。自動化処理という従来の領域とは別に、分散型リアルタイムシステムが、自動車製造産業にますます利用されている。現在、自動車内の制御装置が、特に、自動車エンジンまたは自動送信を制御するためにCANバスシステムを用いて接続されている。複数のセンサ、アクチュエータ及び電子制御ユニットを組合せる制御システムの数は、かなり増加している。制御システム、センサ、アクチュエータおよびそれらに接続された電子制御ユニットを継続的に使用すると、現在の通信プロトコルによって解決されていない通信技術に対する需要が生じる。特に、自動的な“バイ−ワイヤ（by-wire）" システムを導入すると、信頼性が特に重要である、将来の車両内制御分野に対する別の要求が生じる。これには、安全が重要な制御分野に適しているクロック同期サービスが含まれる。
【０００５】
本発明は、FlexRayと名づけられた進化した自動通信システムに利用することを特に意図している。出願人は、エックス・バイ・バイヤ（x-by-wire）のような、車内の革新化された高速制御分野の基準を定義することを目的とするFlexRay技術を発展、実施するために作られた合弁企業の構成員である。
【０００６】
将来の自動分野では、決定論的でかつ耐故障性で、分散型制御システムを支援することが可能な高速バスシステムが必要となる。FlexRay通信システムは、最高10 Mbits の高速データ転送速度での同期非同期データ転送が可能である。この技術は、グローバル時間軸にたいする耐冗長性耐故障性クロック同期を支援する。
【０００７】
現在のバスシステムは、バスに対する処理アクセスの種類、すなわち時分割多重であるか、周波数多重であるかコード多重であるかによって区別される。リアルタイム制御システムの分野では、該システムを制御する方法について2つの基本的に異なった原理、すなわち、タイムトリガー(time triggered) 制御とイベントトリガー（event-triggered）制御システムがある。タイムトリガーシステムでは、すべてのアクティビティ(activity)は、先験的に知られた一定の時点で実行される。従って、タイムトリガーシステムの全てのノードは、近似的に同期したクロックを基礎とした、共通の認識時点がある。これに対して、イベントトリガーシステムでは、全てのアクティビティは、システムに対する外部のイベントに応答して実行される。両システムの主な違いは、決定論的な行動である。所定のルールに基づいたバスに対するシステム制御アクセスによって、各ノードがメッセージを送信する一定の期間内に該バスに対して排他的にアクセスすることが保証される。イベントトリガーシステムは、割り当てられた優先順位でアクセスを行うので、決定論的な行動を保証することができない。
【０００８】
分散型リアルタイムシステムは、耐故障性のクロック同期に依存する。このことは、ノードが所定のスケジュールに従ってその行動を実行する分散型アーキテクチャーに特にあてはまる。このようなタイムトリガーシステムは、主に、安全性が特に問題となる分野において用いられる。クロック同期は、タイムトリガーアーキテクチャーが正しく同期するためには、重要な要素である。
【０００９】
分散型リアルタイムシステムにおいては、局所クロックの同期のために用いられる離散したチャンネルを避けるために、メッセージの交換によって同期が実現し得る。この同期処理自身は、欠陥のあるクロックおよび喪失メッセージを許容しなければならない。
【００１０】
本発明は、機械的なバックアップ（back-up）なしに安全性が問題となる電子システム、すなわちステアリング、ブレーキングまたはサスペンション制御用のバイワイヤ（by-wire）システムを制御する装置に関連して用いられているタイムトリガーアーキテクチャーを意図している。
【００１１】
クロック同期は、所定のリアルタイム性を達成するための最も基本的なサービスである。
【００１２】
公知の耐故障性のリアルタイム通信システムは、タイムトリガープロトコル（TTP）、すなわち安全性が問題となる制御分野に特に適した通信プロトコルである。TTPの同期アルゴリズムは、他のノードに対するノードクロックの読み取りを与える特殊な同期メッセージを用いない。到来するメッセージの到着の遅延は、送信者クロックの値を評価するために用いられる。また、TTPは、選択されたノードからだけのタイミング情報を集める手段を与え、性能が劣っている発振器となると知られているクロック値を無視する。クロック同期とそれに対応する時間測定は、周期的に実行される。
【００１３】
タイムトリガーシステムの特徴は、すべてのシステムアクティビティが時間の進行によって開始されるということである。TTPプロトコルは、周期的に動作する。各ノードにはクロックと一定のスケジュールが与えられる。スケジュールは、一定のアクションが実行されるタイミング、特に、一定の種類のメッセージが特定のノードに送られるタイミングを決定する。
【００１４】
スケジュールは、所定のスロットの持続時間や送信側ノードの同一性のような全てのノードに共通な情報を含む。意図されたシステムビヘービア(system behavior)は全てのノードに既知であるから、重要な情報は、メッセージから間接的に得ることが可能である。
【００１５】
システムバスに対するアクセスは、スケジュールに事前にコンパイルされている時分割マルチアクセス（TDMA）スキーマによって決定される。各ノードは、バス上でメッセージを送ることが可能な自己の一定のスロットを含んでいる。全てのノードが当該バスに一回アクセスした完全サイクルは、TDMAラウンドと呼ばれる。TDMAラウンドが完結した後は、同一の一時的パターンが再び繰返される。
【００１６】
ノードのクロックは、現在のスロットで一致し、かつメッセージが到達するに適当なタイミングで当該バスを走査するに十分な程度に正確に同期しなければならない。欠陥のあるノードが順番を違えて通信するのを防止するために、バスインタフェースが、適当なタイミングでのみバスに対するアクセスを与える「バスガーディアン(bus guardian)」によって制御される。各ノードには、典型的には、個別のカウンタによって提供される物理クロックが供給される。このカウンタは、水晶発振器によって周期的にインクレメントされ、トリガされる。
【００１７】
このような発振器は、完全に固定した周波数で共振しないので、クロックはリアルタイムからドリフトする。他のノードクロックとの一致を保つために、あるノードの物理クロックの調整を繰返し計算することがクロック同期のタスクである。調整された物理クロックは、操作中にノードによって用いられるものである。
【００１８】
クロック調整の最も簡単なやり方は、リアルタイムからの現在のオフセットを単純にクロックに加算する「ワンステップ調整」である。しかし、このやり方は、一致性の問題が生じる可能性がある。
【００１９】
別のやり方では、クロックスピードを、クロックのずれを補償するために早くもしくは遅くなるように変化させるものである。クロックスピードは、オフセットが補償されるまで、早くもしくは遅くなる。正のオフセットは、より遅く「走行する」クロックによって補償され、反対のオフセットは、より早く走行するクロックによって補償されうる。しかし、クロックは変化し続けるので、引き続き調整する必要がある。
【００２０】
TTP（タイガプロトコル）システムでは、クロック同期アルゴリズムは、他のクロックの読取値の推定値を一緒に演算し、局所クロックに対する調整を推測する。各ノードは、いつ一定のメッセージが送られるかを前もって知っているから、メッセージがあるノードで受信されることが期待される時点と実際の到着時点との差異を送信者クロックと受信者クロックとのずれを計算するのに用いることが可能である。従って、何らの特別の同期メッセージもTTPでは必要ない。
【００２１】
TTPプロトコルでのクロック同期は、各TDMA（時分割マルチアクセス）ラウンドに対するできるだけ小さい極大のクロックずれでメッセージが到達するために、殆ど完全に一定の周波数で共振する水晶発振器を必要とする。
【発明の開示】
【発明が解決しようとする課題】
【００２２】
この先行技術から出発して、クロック同期をさらに向上させ、特に、水晶発振器に対するコストを減少させ、より小さな極大クロックずれを達成するのが本発明の問題である。
【課題を解決するための手段】
【００２３】
これは、ノードを同期させる方法に関する請求項１の特徴及び同期ユニットに関する請求項１９によって達成される。
【００２４】
オフセット補正値およびクロックレート（クロック周波数）補正値によってノードの局所ロックを調節することによって、高価な水晶発振器を用いることを避ける。
【００２５】
こうして、全てのクロックの内部クロック同期は、より早く、高精度で達成される。正確なレート補正は、増大するオフセットオーバタイムに対するクロックを保護し、付加的なオフセット補正は、ノードのクロック間の存在するオフセットを減少する。
【００２６】
本発明の好適実施例によれば、クロックレート補正は、あるノードと他のノードとの間の一組のクロックレートずれに基づいて計算される。
【００２７】
第1の好適実施例によれば、該一組のクロックレートずれは、あるノードと他のノードの局所クロック間で決定される2組の時間ずれから計算される。
【００２８】
第２の好適実施例によれば、該一組のクロックレートずれは、局所クロックを基礎とした特定のノードに対する受信メッセージの測定された時間間隔と予測された時間間隔との間の差に基づいている。
【００２９】
好適には、通信リンクに対する分散システムのノードの所定のアクセスパターンのサイクルを備えたTDMAにおいて本発明は用いられる。このようなタイムトリガーアーキテクチャーは、安全性が問題となる電子システムに関する同期方法を用いることが許される。
【００３０】
好適には、同期はTDMAシステムにおいて実行され、2つのTDMAラウンド（サイクル）は、補正値が計算され、クロックが補正される前にずれを測定するために用いられる。
【００３１】
補正値を計算するとき、特定のノードを考慮するのみで、耐故障性行動を増大可能であり、メモリ性を減少してもよい。
【００３２】
さらに好適な実施例によれば、計算されたクロックレート補正値の量は、該補正値を基礎としてクロックを調整する前に減少される。このような減少されたクロックレート補正値は、向上したクロック同期安定性を提供し、ノードのクラスタがドリフトするのを防止し、クラスタ全体を極端な周波数値からクラスタの全てのクロック周波数の平均値へシフトさせる。
【００３３】
本発明の他の好適な実施例は、種々の従属クレームとして提示される。
【発明の効果】
【００３４】
本発明は、分散型システムの各ノードでオフセット補正とクロックレート補正を同時に行うことによって、リアルタイム処理に対して意図された分散型システム用の改良されたクロック同期アルゴリズムを提供できる。従って、高価な発振器は、不要であり、同期を迅速にかつ高精度で達成可能である。
【発明を実施するための最良の形態】
【００３５】
図１は、複数のノードを備えた分散型システムの単純化された例を示す。水晶発振子２を備えた各ノードはクロックを供給される。メッセージを送るために、各ノードは、通信リンクに接続され、メッセージを送受信するためのバスにアクセスする。この通信リンクはさらに、任意の冗長通信チャンネルを備え、約10Mビット/secの総データレートを支持するように設計されている。
【００３６】
各ノードは、それ自身のクロックだけでなく、すべてのノードに共通な付加的情報を供給される。共通情報は、所定のスロットの間隔または送りノードの同一性のような通信構造に関する。意図されたシステム行動は、すべてのノードに既知であり、重要な情報は、受信されたメッセージから間接的に得ることが可能である。例えば、受信ノードは、予測された到着時間が経過した直後にメッセージが消失していることを判断可能であるから、明確な肯定応答（acknowledgement）は送る必要がない。
【００３７】
通信リンク（バス）３に対するアクセスは、時分割多重アクセス（TDMA）スキームによって決定される。全てのノードは、バス上にメッセージを送ることが許容されているアクセススキーム内に一定のスロットを有している。全てのノードがその間に一回アクセスしていた完全サイクルは、TDMAラウンドと呼ばれる。このような通信サイクルの例は、図２に示されている。図２に示された通信サイクルは、2つの部分、すなわちスタチック（静的）部とダイナミック（動的）部を有している。静的部では、各ノードが適時にバスにアクセスするにすぎない。これは、6個のタイムスロットの各々が全ノードのうちの特定のノードによってアクセスされ得る静的TDMAアクセス部に現れている。これに対して、動的部では、メッセージを送信するための衝突のないアクセス（collision free access）を与える所定のスキームに従って各ノードがバスにアクセスし得る。TDMAラウンドが完了したら、同じ一時的アクセスパターンが再び繰返される。
【００３８】
各通信ノードは、2つのバスガーディアン４とそれに対応するドライバ５を備え、図３に示されるように各ノードのバスに対するアクセスを制御する。通信ノード内の全てのユニットは、単一の電源に接続される。バスガーディアン４は、送信タイミングと送信用に許された期間を示す分散型システムの各ノード上の記憶情報に基づいて動作する。バスガーディアン４は、前記所定のタイミングでのみ許容されている通信リンクへのアクセスを制御する。ホスト６に最初に記憶された情報は転送され、動作中のバスガーディアンに記憶される。
【００３９】
図４は、通信リンク上で送信されるメッセージフォーマットの一例である。
メッセージフォーマットは、TDMAラウンドのスタティック部又はダイナミック部間に送信される全てのメッセージついて同一である。各メッセージはつぎのフィールドを有している。
ID: 識別子。１０ビット。レンジ１、、、、１０２３。スタティック部のスロット位置とダイナミック部でのメッセージの優先順位を定義する。各識別子は、システムにおいて一回だけ利用するのが望ましい。
MUX:マルチプレックスフィールド。１ビット。ノードが同一でIdが異なったメッセージを送信することを可能とする。
SYNC: 同期フィールド。１ビット。メッセージがクロック同期に用いられるかどうかを示す。
LEN:  長さフィールド。4ビット。用いられたデータバイトの数（0…12）を示す。
D00…D11: データバイト。0-12バイト。
CRC: 16ビット（又は15ビット）。周期的冗長度チェック。
【００４０】
クロック同期アルゴリズムは、他のノードクロックの時間の予測を集めることによって作動し、局所クロックの調整を予測する。各ノードは、一定のメッセージがいつ送られるか事前に知る。メッセージがノードによって受信されることが期待される時間と実際の到着時間との間の差異は、送り手のクロックと受け手のクロックのずれを計算するのに用いることが可能である。従って、特別の同期メッセージは必要なくなる。2つのTDMAラウンドにわたって行われる測定が図５に示されている。2つのノード（コントローラ）の時間が図５において太い線によって示されている（コントローラ１とコントローラ２）。図示されているように、両コントロータの時間は若干異なっており、タイムオフセット及び時間と共に増大する時間ずれで示される。
【００４１】
第１のサイクルにおいては、各ノードは、受信されたメッセージに基づいて自己の時間と他のノードの時間との間の時間差を決定する。その差は、各特定のノードのアクセスパターンにも依存する。同じ処理は、同一のアクセスパターンを有する連続したサイクル内で実行される。クロックレート（クロック周波数）が異なることにより、各ノードによって検出された時間ずれがさらに増大する。この付加的差は、両クロック間の周波数を評価し、計算された共通のタイムベースに基づいてクロックを調整するのに用いられる。
【００４２】
クロック補正処理によって達成可能な結果は、図６及び図７に示されている。図６において、個々のクロックレートは、オフセット定数を維持し、時間とともにノード間の増加するクロックオフセットを避けるために調整される。図７は、別の補正法、すなわち検出されたタイムオフセットを補正することを示している。このような調整では、サイクルの始には、両クロックを近づけるが、両クロックは、両サイクルの最後には、大きな差を再び示すことになる。
【００４３】
改良されたクロック調整法は、図８に示されている。各クロック調整のために、クロックは、クロックレート及びクロックオフセットに関して補正される。
【００４４】
コントローラ１およびコントローラ２のクロックは破線によって示されている。オフセット補正されたクロックは点線で示されている。付加的にクロックレートが補正されたクロックは太い線によって示されている。その結果、両クロックは、近接したままであり、クロックずれは、時間とともに増大しない。
【００４５】
補正値は、メモリに記憶された測定クロック差から計算される。図４に関して説明したように、時間差を測定するために用いられるノードは、特別のフラグによってマークされている。グローバルタイムの計算のために、各ノードは同一のアルゴリズムを適用する。簡単なやり方では、各ノードは、補正値に到達するように平均差を計算する。好適には、より複雑な方法が、耐故障性の標準的なアルゴリズム（FTA）が用いられる。このアルゴリズムは、検出された最大値及び最小値を捨て、補正値を計算するために最大差を有する残りの2つの値の平均値を計算する。
【００４６】
各ノードによって個々に実行されるクロック同期アルゴリズムは、2つの連続したスロット毎に、到来するメッセージの予期された到着タイミングと観測された到着タイミングとの間の差を決定するステップを実行する。
【００４７】
検出された差は、メモリに記憶され、第2のサイクル中の対応する差の値を検出した後で、補正値、すなわちレート補正値及びオフセット補正値が計算される。
【００４８】
図９に示されるように、クロック同期アルゴリズムは、2つの連続したサイクル毎に、三つのフェーズすなわち、測定フェーズ、計算フェーズおよび補正フェーズを含んでいる。
【００４９】
測定フェーズは、2つのサイクル、すなわちサイクル１およびサイクル２に分離される。各サイクルについて、同期ビットを備えた全ての有効なメッセージの時間値が測定され、第1のサイクルに割り当てられた第1のメモリ部及び第2のサイクルに割り当てられた第2のメモリ部にセーブされる。第1のサイクルの終末後に局所クロックに加えられる補正値は存在しない。
【００５０】
好適には、サイクル２およびサイクル３の間に実行される計算フェーズの間に、レート補正値及びオフセット補正値が計算される。レート補正では、第1、第2のメモリ部に記憶された測定値間の差が計算される。計算された差の値から、2つの値が、有効な同期メッセージの数kに基づいている所定のルールに応じて選択される。このような所定のルールおよび耐故障性のミットポイントアルゴリズム（FTA/FTM）は、"Information and Communication" vol.77, no.1, April 1998号のWelch, J.L., Lynch, N.A. "A New Fault-Tolerant Algorithm for Clock Synchoronization" の1-36頁に記載されている。その結果は、クロックレート補正を増分的に改良するために前のクロックレート補正値と組合される。
【００５１】
オフセット調整に対しては、有効な同期メッセージの数kに応じて、2つのノードが再び選択される。この選択は、上記レート補正の選択処理に対応し、再びWelch およびLynchによる上記文献が参照される。第2のメモリからの選択された差の値が加えられ、２分割される。
【００５２】
図９において、別々のノードについて計算した値がノード番号に従って挙げられている。第1欄には、第1サイクルでの測定結果が示されており、第2欄には、第2サイクルでの測定結果が示されている。第3欄は、第1サイクル及び第2サイクルでの測定ずれの間で計算された差が示されている。計算された補正値がこれらの値の上に示されており、図９の最上部に示された局所クロックに適用される。
【００５３】
補正フェーズはまた、2つの別々のステップ、すなわち、レート補正およびオフセット補正に分けられる。計算されたレート補正値を、次の2つのサイクル、すなわちサイクル３及びサイクル４に付加しクロック周波数を補正する。オフセット補正値は、つぎのサイクル、すなわちサイクル３の最初に付加されるだけである。さらなるオフセット補正値はサイクル４の最初には付加されない。
【００５４】
この同期処理は、2つの連続したサイクルに対して繰返され、サイクル番号は、サイクル（2n-1）とサイクル(2n)として一般化可能である。
【００５５】
新同期法を適用するための特定の２サイクルスキームが図１０に詳細に示されている。
【００５６】
補正値の計算のために用いられる耐故障性アルゴリズムに関しては、各ノードが同一のアルゴリズムを適用する限り、各既知の耐故障性アルゴリズムを用い得る。
【００５７】
各局所クロック周波数は、複数の異なった既知の手段の一つを適用することによって調整可能である。可能性の例は、印加された電圧に基づいて調整可能な周波数を有しているVCOや、分数率補正をするために単位時間当りのクロックチックの数を調整することによってクロックチックをカウンタ値への変換を制御する回路である。
【００５８】
本発明の好適実施例の一般化された同期アルゴリズムは次の通りである。
【００５９】
ラウンドk0: ノードjで全てのc(i,j,k,)を集合。同期メッセージは目印付け(tag)されている。c(i,j,k,)は、「マイクロチック（micro ticks）すなわち局所マイクロチック」単位の観測された時間と期待時間との間の差である。t(i,j,k,)は、スロットiの開始を期待するノードの物理時間、s(i,j,k,)は、スロットiの先頭でノードｊで観察された物理時間として、c(i,j,k,)は、次のように定義できる。
【００６０】
c(i,j,k,) = Int s(i,j,k,) - t(i,j,k,)[micro ticks]
・  ラウンド(k0+1):全ての目印付された同期メッセージに対してノードｊで全てのc(i,j,k0+1,)を集合。
・  ラウンド(k0+1)の最後で、スロットiに対するノードjでのオフセット入力は、
of(i,j,k0+1) = c(i,j,k0+1)
・  レート差は、
st(i,j,k0+1) = c(i,j,k0+1) - c(i,j,k0)
・  各新ラウンド（k0+2）に対して、新オフセット値o(j, k0+2)及び新レート補正値d(j, k0+2)を以下の式に従って一般化。
【００６１】
o(j,k0+2) = FT(of(i,j,k0+1))
d(j,k0+2) = FT(st(i,j,k0+1)) +d(j,k0)
・  次のサイクルの始めにクロックをo(j, k0+2)だけ調整。
・  ラウンド(k0 +2)及びラウンド(k0 +3)に対してd(j,k0+2)だけ連続的にクロック周波数を調整。
【００６２】
別の実施例によれば、一組のクロックレートずれ及び一組の時間ずれは、別々に決定される。クロックレートずれは、同一のノードからの2つの連続したメッセージに対する2つの時間間隔、すなわち観測された時間間隔および予測された時間間隔を比較することによって決定される。観測された時間間隔は、同じノードからの2つのメッセージの実際の到着時間の間で、好適には、マイクロチックの単位でカウンタによって測定される。予測された時間間隔は、既知でかつ各ノードで記憶されたメッセージの予測された受信タイミングから計算される。両時間間隔の間の差は、両ノード間のクロックレート差によるずれを示す。クロックレート補正値は、上記の方法で、計算されたクロックレートずれに基づいて計算される。
【００６３】
ひと組の時間ずれで、上記したオフセット補正値を計算するには十分である。本代替実施例では、好適には、オフセット補正値と一組の時間ずれが、２サイクル毎に一回だけ計算される。
【００６４】
本発明のアルゴリズムの特徴は、測定と間隔調整は重複することはなく、レート補正は、時間の誤りに影響されないことである。さらに、このアルゴリズムは、測定、計算および調整ステップを適切に適応するためには、サイクルカウントを必要とする。
【００６５】
メモリ性に関しては、全ての検出された差を記憶することが必要なわけではなく、適用された耐故障性のアルゴリズムに応じて関連のあるものだけで良い。
【００６６】
クロック同期に基づいて達成可能な極大オフセットの減少は、図１１乃至図１３から理解できる。図１１は、適用されたオフセット補正に対する極大クロックオフセットを示し、図１２は、適用されたレート補正に対する極大クロックオフセットを示している。図１２から理解できるように、同期が確立された後は、レート補正は、各サイクル毎に適用する必要はない。図１３は、かなり低い極大クロックオフセットで到達する本発明の利点を示している。同期が一旦確立された後では、補正は少ない頻度で行えば良い。
【００６７】
更なる好適実施例によれば、極端値までの総時間のドリフトは、さらに別の方策によって避けることが可能である。この目的のために、クロックレート補正値は、計算されたようには適用されず、計算された補正量は、所定量だけシフトされる。好適には、レート補正値は若干減少される。このクロックレート補正値のこの変化によって、クロック同期性が幾分減少することになる。これに対して、極端値への総時間の絶えざるドリフトは避けられ、全てのノードは、一定時間後には、同期されるべきクロックの平均値に近接する。
【００６８】
この目的のために、クロックレート補正値d(j,k0+2)は、補正値d(j,k0+2)＋/−x (xは減少量)によって置きかえられる。
【００６９】
さらに、ラウンド時間エラーはオフセット補正値を補正することによって、すなわちオフセット補正値o(j,k0+2)−yj(yjは正の値)を用いることによって補償可能である。
【００７０】
図１４および図１５は、クロック同期を確立する各サイクルに対する適用されたクロックレート補正値を示す。図１４においては、クロック値補正はなされていない。提示された例では、全てのノードは、一番上のノードの局所時間に同期する（上方ノードでは何ら一定の補正は行わないが、他のノードは、約−50または−80の補正を行う）。
【００７１】
図１５は、適用されたクロックレートを１マイクロチックだけ減少することによってクロックレート補正値を減少したときの結果を示す。グローバルタイムは、同期される全てのノードの平均値にシフトされ、補正を行うノードはなくなる。
【図面の簡単な説明】
【００７２】
【図１】単純化された態様の分散システムの一般的構造を示す図である。
【図２】典型的なアクセススキームの一例を示す図である。
【図３】通信システムに接続されたノードの単純化されたブロック図の一例を示す図である。
【図４】通信システム上で送信されるメッセージの構造の一例を示す図である。
【図５】測定されたクロックずれを示す図である。
【図６】クロックレート補正を示す図である。
【図７】オフセット補正を示す図である。
【図８】オフセット補正とクロックレート補正の組合せを示す図である。
【図９】本発明の好適実施例によるクロック同期の一例を示す図である。
【図１０】本発明の好適実施例による時間軸の測定フェーズと補正フェーズのシーケンスを示す図である。
【図１１】オフセット補正を用いるときに達成可能な極大クロックオフセットを示す図である。
【図１２】クロックレート補正を用いるときに達成可能なク極大クロックオフセットを示す図である。
【図１３】本発明によるクロック同期を用いるときの極大クロックオフセットを示す図である。
【図１４】クロックレート補正による減少のない必要な補正値の一例を示す図である。
【図１５】本発明の好適実施例によるクロックレート補正による減少のある図１４に対応する一例を示す図である。
【符号の説明】
【００７３】
１    ノード
２    局所クロック
３    通信リンク
４    バスガーディアン
５    ドライバ
６    メモリ
【図１】
2004536538.tif 000003
【図２】
2004536538.tif 000004
【図３】
2004536538.tif 000005
【図４】
2004536538.tif 000006
【図５】
2004536538.tif 000007
【図６】
2004536538.tif 000008
【図７】
2004536538.tif 000009
【図８】
2004536538.tif 000010
【図９】
2004536538.tif 000011
【図１０】
2004536538.tif 000012
【図１１】
2004536538.tif 000013
【図１２】
2004536538.tif 000014
【図１３】
2004536538.tif 000015
【図１４】
2004536538.tif 000016
【図１５】
2004536538.tif 000017
【国際公開パンフレット】
2004536538.tif 000018
2004536538.tif 000019
2004536538.tif 000020
2004536538.tif 000021
2004536538.tif 000022
2004536538.tif 000023
2004536538.tif 000024
2004536538.tif 000025
2004536538.tif 000026
2004536538.tif 000027
2004536538.tif 000028
2004536538.tif 000029
2004536538.tif 000030
2004536538.tif 000031
2004536538.tif 000032
2004536538.tif 000033
2004536538.tif 000034
2004536538.tif 000035
2004536538.tif 000036
2004536538.tif 000037
2004536538.tif 000038
2004536538.tif 000039
2004536538.tif 000040
2004536538.tif 000041
2004536538.tif 000042
2004536538.tif 000043
2004536538.tif 000044
2004536538.tif 000045
2004536538.tif 000046
2004536538.tif 000047
2004536538.tif 000048
2004536538.tif 000049
2004536538.tif 000050
2004536538.tif 000051
2004536538.tif 000052
2004536538.tif 000053
【国際調査報告】
2004536538.tif 000054
2004536538.tif 000055