(57)【要約】無線ネットワークにおけるノードのクロックの同期化を確立し、維持するためのシステムおよび方法（２００）であり、このシステムおよび方法は無線ネットワークにおける選択された準ノードとクライアントノードとの間の一連のメッセージ交換および制御アルゴリズムを使用してクロックシフトおよび伝搬遅延を計算（２１４）し、これら値を使ってクライアントノードのクロックを基準ノードのクロックに同期化（２１６）する。
2005536919.tif 000002
【特許請求の範囲】
【請求項１】
アドホック無線ネットワーク内の複数のノードのうちの少なくとも２つのノードの間のクロック同期を制御するための方法であって、
前記複数のノードから基準ノードを選択し、該基準ノードに第１の通信を送るように、前記複数のノードのうちのクライアントノードを制御する工程を備え、該クライアントノードがクライアントクロックを有し、前記基準ノードが基準クロックを有し前記第１の通信を受信し、これに応答して第１の回答を前記クライアントノードに送るよう、前記基準ノードを制御する工程と、
前記第１の回答を受信し、これに応答して第２および第３の通信を前記基準ノードに送るよう、前記クライアントノードを制御する工程と、
前記第２および第３の通信を受信し、これに応答して前記クライアントノードと前記基準ノードとの間に存在する第１のクロックシフトおよび伝搬値を計算し、第２の回答において前記値を前記クライアントノードに送るように前記基準ノードを制御する工程とを備えた、クロック同期化を制御するための方法。
【請求項２】
請求項１に記載の方法において、ネットワークの接続性に基づき、前記基準ノードを選択するように前記クライアントノードを制御する工程を更に含む、方法。
【請求項３】
請求項１に記載の方法において、前記第１の通信がクロック同期化のためのリクエストを含む、方法。
【請求項４】
請求項３に記載の方法において、前記第１の通信が更にクライアントクロックおよび基準クロック情報を有するＣＬＯＣＫＳＹＮＣメッセージを備え、該ＣＬＯＣＫＳＹＮＣメッセージが前記クライアントノードと前記基準ノードとの間のクロック同期化セッションをリクエストする、方法。
【請求項５】
請求項１に記載の方法において、前記第１の回答が第１の基準クロック値を有するＣＬＯＣＫＴＩＭＥメッセージを含む、方法。
【請求項６】
請求項５に記載の方法において、前記第１の基準クロック値が前記基準ノードから前記クライアントノードへの前記第１の回答の送信時の基準クロック値を含む、方法。
【請求項７】
請求項６に記載の方法において、前記基準クロック値が更に３２ビットの値を含む、方法。
【請求項８】
請求項１に記載の方法において、前記第２の通信が第１のクライアントクロック値を有するＣＬＯＣＫＲＥＰＬ１メッセージを含み、前記第３の通信が第２のクライアントクロック値を有するＣＬＯＣＫＲＥＰＬ２メッセージを含む、方法。
【請求項９】
請求項８に記載の方法において、前記第１のクライアントクロック値が前記クライアントノードによる前記基準ノードからの前記第１の回答の受信時におけるクライアントクロック値を含む、方法。
【請求項１０】
請求項８に記載の方法において、前記第２のクライアントクロック値が前記クライアントノードから前記基準ノードへの前記第２の通信の送信時のクライアントクロック値を含む、方法。
【請求項１１】
請求項１に記載の方法において、前記第１のクロックシフトおよび伝搬値を使って、前記クライアントクロックと前記基準クロックとを同期化するように前記クライアントノードを制御する工程を更に含む、方法。
【請求項１２】
請求項１に記載の方法において、第２クロックシフトおよび伝搬値を計算し、これに応答して前記クライアントクロックのクロックドリフトを決定するように前記クライアントノードおよび前記基準ノードのうちの少なくとも１つを制御する工程と、
前記決定されたクロックドリフトおよびドリフト制御アルゴリズムを使って前記クライアントクロックの前記クロックドリフトを補正するように、前記クライアントノードおよび前記基準ノードのうちの少なくとも１つを更に制御する工程とを備えた、方法。
【請求項１３】
請求項１２に記載の方法において、前記ドリフト制御アルゴリズムがアドホック無線ネットワークにおける１つのノードでのクロックドリフト補正を制御するための命令のコンピュータで読み取り可能な媒体を含み、
本方法が、ドリフト補正値を発生し、該ドリフト補正値を使って前記クライアントクロックの前記クロックドリフトを補正するように、前記クライアントノードおよび前記基準ノードのうちの少なくとも１つを制御するようになっている第１の組の命令を含む、方法。
【請求項１４】
請求項１に記載の方法において、前記第１クロックシフトおよび伝搬値を計算し、該第１クロックシフトおよび伝搬値を前記クライアントノードと交換するように前記基準ノードを制御する前記工程が、
前記基準ノードを初期化するようになっている第１の基準ノードタスクと、
前記クライアントノードとの間でクロック同期化メッセージを交換することを前記基準ノードに命令するようになっている第２の基準ノードタスクと、
前記第１クロックシフトおよび伝搬値を計算し、前記値を前記クライアントノードに送ることを前記基準ノードに指示するようになっている第３の基準ノードタスクのうちの少なくとも１つを備えた、基準のノードタスクを使用する、方法。
【請求項１５】
請求項１に記載の方法において、前記第１クロックシフトおよび伝搬値を計算し、該第１クロックシフトおよび伝搬値を前記クライアントノードと交換するように前記基準ノードを制御する前記工程が、
前記クライアントノードを初期化するようになっている第１のクライアントノードタスクと、
前記クライアントノードとの間でクロック同期化メッセージを交換することを前記クライアントノードに命令するようになっている第２のクライアントノードタスクと、
前記同期化メッセージを使用し、前記クライアントクロックを補正することを前記クライアントノード指示するようになっている第３のクライアントノードタスクのうちの少なくとも１つを備えた、基準のノードタスクを使用する、方法。
【請求項１６】
アドホック無線ネットワーク内の複数のノードのうちの少なくとも２つのノードの間のクロック同期化を制御するための方法であって、
前記複数のノードのうちのクライアントノードと基準ノードとの間でクロック同期化メッセージの交換を制御する工程と、
前記クロック同期化メッセージの交換に応答し、前記クライアントノードと基準ノードとの間に存在する第１のクロックシフトおよび伝搬値を計算し、前記値を前記クライアントノードに提供するように前記基準ノードを制御する工程と、
前記値およびドリフト制御アルゴリズムのうちの少なくとも１つを使って前記クライアントノードにおけるクライアントクロックと前記基準ノードにおける基準クロックとを同期化するように、前記クライアントノードを制御する工程とを備えた、方法。
【請求項１７】
請求項１６に記載の方法において、ネットワークの接続性に基づき、クロック同期化メッセージを交換するために前記基準ノードを選択するように前記クライアントノードを制御する工程を更に含む、方法。
【請求項１８】
請求項１６に記載の方法において、前記クロック同期化メッセージ交換を制御する前記工程が、
前記基準ノードを初期化するようになっており、更に前記クライアントノードとクロック同期化メッセージを交換することを前記基準ノードに指示するようになっている一組の基準ノードタスクと、
前記クライアントノードを初期化するようになっており、更に前記基準ノードとクロック同期化メッセージを交換することを前記クライアントノードに指示するようになっている一組のクライアントノードタスクのうちの少なくとも１つを含むノードタスクを使用する、方法。
【請求項１９】
請求項１６に記載の方法において、前記ドリフト制御アルゴリズムがアドホック無線ネットワークにおける１つのノードでのクロックドリフト補正を制御するための命令のコンピュータで読み取り可能な媒体を含み、
本方法が、ドリフト補正値を発生し、該ドリフト補正値を使って前記クライアントクロックの前記クロックドリフトを補正するために、前記クライアントノードおよび前記基準ノードのうちの少なくとも１つを制御するようになっている第１の組の命令を含む、方法。
【請求項２０】
アドホック無線ネットワークにおける複数のノードのうちの少なくとも２つのノードの間のクロック同期を制御するための命令をコンピュータで読み取り可能な媒体であって、
前記複数のノードから基準ノードを選択し、該基準ノードに第１の通信を送るために、前記複数のノードのうちのクライアントノードを制御するようになっている第１の組の命令を備え、前記クライアントノードがクライアントクロックを有し、前記基準ノードが基準クロックを有し、
前記第１の通信を受信し、これに応答して第１の回答を前記クライアントノードに送るために、前記クライアントノードを制御するようになっている第２の組の命令を備え、
前記第１の組の命令が更に前記第１の回答を受信し、これに応答し第２および第３の通信を前記基準ノードへ送るために前記クライアントノードを制御するようになっており、
前記第２の組の命令が更に前記第２および第３の通信を受信し、これに応答し、前記クライアントノードと前記基準ノードとの間に存在する第１のクロックシフトおよび伝搬値を計算し、第２の回答において前記値を前記クライアントノードに送るために前記基準ノードを制御するようになっている、少なくとも２つのノードの間のクロック同期を制御するための命令をコンピュータで読み取り可能な媒体。
【請求項２１】
請求項２０に記載の命令をコンピュータで読み取り可能な媒体において、前記第１の組の命令が更にネットワークの接続性に基づき、前記基準ノードを選択するように前記クライアントノードを制御するようになっている、媒体。
。
【請求項２２】
請求項２０に記載の命令をコンピュータで読み取り可能な媒体において、前記第１の通信がクロック同期化のためのリクエストを含む、媒体。
【請求項２３】
請求項２２に記載の命令をコンピュータで読み取り可能な媒体において、前記第１の通信が更にクライアントクロックおよび基準クロック情報を有するＣＬＯＣＫＳＹＮＣメッセージを備え、該ＣＬＯＣＫＳＹＮＣメッセージが前記クライアントノードと前記基準ノードとの間のクロック同期化セッションをリクエストする、媒体。
【請求項２４】
請求項２０に記載の命令をコンピュータで読み取り可能な媒体において、前記第１の回答が第１の基準クロック値を有するＣＬＯＣＫＴＩＭＥメッセージを含む、媒体。
【請求項２５】
請求項２４に記載の命令をコンピュータで読み取り可能な媒体において、前記第１の基準クロック値が前記基準ノードから前記クライアントノードへの前記第１の回答の送信時の基準クロック値を含む、媒体。
【請求項２６】
請求項２５に記載の命令をコンピュータで読み取り可能な媒体において、前記基準クロック値が更に３２ビットの値を含む、媒体。
【請求項２７】
請求項２０に記載の命令をコンピュータで読み取り可能な媒体において、前記第２の通信が第１のクライアントクロック値を有するＣＬＯＣＫＲＥＰＬ１メッセージを含み、前記第３の通信が第２のクライアントクロック値を有するＣＬＯＣＫＲＥＰＬ２メッセージを含む、媒体。
【請求項２８】
請求項２７に記載の命令をコンピュータで読み取り可能な媒体において、前記第１のクライアントクロック値が前記クライアントノードによる前記基準ノードからの前記第１の回答の受信時におけるクライアントクロック値を含む、媒体。
【請求項２９】
請求項２７に記載の命令をコンピュータで読み取り可能な媒体において、前記第２のクライアントクロック値が前記クライアントノードから前記基準ノードへの前記第２の通信の送信時のクライアントクロック値を含む、媒体。
【請求項３０】
請求項２０に記載の命令をコンピュータで読み取り可能な媒体において、前記第１の組の命令が更に前記第１のクロックシフトおよび伝搬値を使って、前記クライアントクロックと前記基準クロックとを同期化するために前記クライアントノードを制御するようになっている、媒体。
【請求項３１】
請求項２０に記載の命令をコンピュータで読み取り可能な媒体において、前記第１の組の命令が更に第２クロックシフトおよび伝搬値を計算し、これに応答して前記クライアントクロックのクロックドリフトを決定するために前記クライアントノードおよび前記基準ノードのうちの少なくとも１つを制御するようになっており、
前記第１の組の命令が更に前記決定されたクロックドリフトおよびドリフト制御アルゴリズムを使って前記クライアントクロックの前記クロックドリフトを補正するために、前記クライアントノードおよび前記基準ノードのうちの少なくとも１つを更に制御するようになっている、媒体。
【請求項３２】
請求項３１に記載の命令のコンピュータで読み取り可能な媒体において、前記アルゴリズムがドリフト補正値を発生し、前記ドリフト補正値を使って前記クライアントクロックの前記クロックドリフトを補正するために、前記クライアントノードおよび前記基準ノードのうちの少なくとも１つを制御するようになっている第３の組の命令を含む、媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（発明の背景）
（発明の分野）
本発明は無線ネットワークにおけるノードのクロックを同期化するためのシステムおよび方法に関する。より詳細には、本発明は無線ネットワーク内の選択された基準ノードとクライアントノードとの間のクロックシフト、クロックドリフトおよび伝搬遅延時間を計算するためのシステムおよび方法に関する。計算されたシフト、ドリフトおよび伝搬遅延値は基準ノードのクロックとクライアントノードのクライアントとを正確にクロック同期化し、更にこれらノード間の距離を計算するのに使用される。
【背景技術】
【０００２】
（関連技術の説明）
近年、従来のインフラストラクチャの範囲を超える多数の移動デバイスが通信できる必要性の問題を解決するために、アドホックネットワークとして知られるあるタイプの移動通信ネットワークが開発された。このタイプのネットワークでは、各ユーザターミナル（以下、「移動ノード」と称す）はネットワーク内の他の移動ノードに対し、移動リピータまたは移動ルータとして作動できるので、基地局の固定インフラストラクチャが不要となる。従って、発信源の移動ノードから宛て先移動ノードへ送られるデータパケットは、一般に宛て先ノードに達する前に多数の中間ノードを通過するようにルーティングされる。
【０００３】
従来のアドホックネットワーク内で行われているのと同じように、複数の移動ノードが互いに通信できるようにする外に、更に移動ノードが固定されたネットワークにアクセスしたり、他のタイプのユーザターミナル、例えば公衆交換電話ネットワーク（ＰＳＴＮ）およびインターネットのようなターミナルと通信できるようにする、より高度なアドホックネットワークも開発中である。これら高度なタイプのアドホックネットワークの詳細は「ＰＳＴＮおよびセルラネットワークとインターフェースされるアドホックなピアツーピア移動無線アクセスシステム」を発明の名称とし、２００１年６月２９日に出願された米国特許出願第09/897,790号、「別個の保留チャンネルを有する共用パラレルデータチャンネルへコーディネートチャンネルアクセスするアドホックなピアツーピア無線ネットワークのための時分割プロトコル」を発明の名称とし、２００１年３月２２日に出願された米国特許出願第09/815,157号および「アドホックな、ピアツーピアの移動無線アクセスシステムのための優先順序に従ったルーティング」を発明の名称とし、２００１年３月２２日に出願された米国特許出願第09/815,164号に記載されており、本明細書ではこれら米国特許出願の全内容を参考例として援用する。
【０００４】
有線または無線の、かかるネットワークの目的は、あるノードから別のノードへデータを送信することである。無線ネットワークでは、この情報はノード間のあるシーケンスのメッセージとして転送される。しかし、実際に情報を含むデータメッセージを送信する前に参加ノード間である種の制御メッセージ、すなわち「オーバヘッド情報」が交換される。これによってデータ転送中に同じチャンネル内で別の活動（例えば送信）が行われず、更に双方のコレスポンデントが同じ周波数に同調し、一方のコレスポンデントがすぐに送信でき、他方のコレスポンデントがすぐに受信できる状態となることが保証される。データ転送が完了した後に、受信者が受信されたデータの質を確認するメッセージで応答する。これによって、データの送信機は次のデータ転送の特性を調節でき、すなわちデータが正しく受信されなかった場合でも、異なる送信特性で最後の転送を繰り返すことが可能となる。
【０００５】
特にデータパケットが少なく、送信が頻繁に行われるときに、これら無線ネットワークにおいて交換されるオーバヘッド情報量は極めて大きくなり、ネットワークの容量に悪影響を与える。しかし、タイムスロット技術を使ってアクティビティのプランニングを実行することにより、オーバヘッド交換量を実質的に低減できる。好ましくないことに、かかるプランニングはネットワーク内の移動ノードの間のある程度のクロック同期化を必要とするが、このことは品質の低いクロックを含むシステムでは困難なことである。
【０００６】
頻繁な送信を行ったり、またはデータの極めて大きいパケットを送信する場合、送信の準備のためのオーバヘッドは重要ではない。しかし、特に送信されるデータが小さいパケットで構成され、これらパケットが頻繁に送信されるときには、オーバヘッド送信は負担となる。音声データパケットは、この小さくかつ頻繁なデータパケット送信の良好な一例である。ボイスパケットは一般に１２８バイトデータ未満であり、毎秒約３０回で繰り返される。小さく、かつ頻繁な送信であたえられるデータストリームに関連するオーバヘッド情報の量は、種々のプランニング方法を使って少なくすることができる。これら方法は、かかる高レベルのオーバヘッド送信を使用することなく、１つの周波数で１回の送信を行い、同じ時間に各コレスポンデントが同じ周波数に同調することを保証するのに必要なすべての情報を両当事者に与えることができる。
【０００７】
効率的なデータ転送をプランニングするための１つの方法は、送信時間を複数のタイムフレーム（ＴＦ）に分割することであり、各タイムフレームは更に複数のタイムスロット（ＴＳ）に分割される。かかる時間分割により時間フレームレベルで頻繁に送信をプランニングすることが可能となる。ＴＳの利用はあるＴＦから別のＴＦでは変化しないので、送信をする前にオーバヘッド情報は１回しか交換されず、しかもオーバヘッド情報は送信期間中、更に送信の再ルーティングが必要となるまでアクティブなままである。しかし、ＴＦおよびＴＳを使用する方法を実現するには、まず参加ノードのクロックを同期化しなければならない。
【０００８】
クロックの同期化は、有線または無線ネットワークにおける１つ以上のノードにおけるクロック調節を扱う方法を説明するのに使用されることが多い。これら調節は変換関数を使ってリモート時間ベースに一致させるようにローカル時間ベースを変換したり、または基準目的のためにリモート時間ベースに関する情報を単に受信することを含むことができる。例えばノード間に存在する基本変換関数を決定するために、ノード間のタイミング情報を交換することができる。かかるメッセージ交換については、「通信ネットワークのための連続変換関数を使用するブロック同期化システムおよび方法」を発明の名称とし、ジャン・マルク・ベルナード氏に対し２０００年１２月５日に発行された米国特許第6,157,957号に記載されている。この米国特許の全内容を本明細書では参考例として援用する。ベルナード特許に開示された方法は、多数のメッセージ交換をヒストリデータレジスタに収集し、記憶することに関するものであり、このレジスタはローカルクロック値をマスタ時間ベースに変換するための変換関数を計算するために使用できる。しかし、ベルナード特許は通信トラヒックから生じるネットワークキューから生じる交換遅延時間の非対称性を考慮していない。更に移動ノードアプリケーションでは変換関数を発生するためのヒストリデータレジスタの広範な処理は限られており、移動ノードのアプリケーションは低スピードのＣＰＵで一般に制御されており、浮動小数点演算を実行する能力が欠如していることが多い。「分散計算ユニットを有するシステムのための共通時間ベースを発生するための方法」を発明の名称として１９９５年３月２８日にクラウス・タルスキー氏に発行された米国特許第5,402,394号には、ローカル時間ベースを調節することなく、他のノードにおける時間ベースを計算するための別の方法が記載されている。本明細書ではこの米国特許の全内容を参考例として援用する。
【０００９】
同期化のためにノード間で実際にメッセージ交換することは、ノードネットワークのコンフィギュレーションに依存することが多い。１つのコンフィギュレーションである、閉ループ通信リングはメッセージおよび関連するデータがリング内の元のノードに戻るまで、リングの各ノードにメッセージを通過させ得る。かかる方法はリングネットワーク内の条件を満たすことができるが、リングノードが２つのノードからしか構成されない、最も簡単なコンフィギュレーションでは、メッセージの交換は過剰となり得る。「分散コンピュータノード内のクロックを同期化するためのシステムおよび方法」を発明の名称とし、１９９９年５月２５日にジョン・Ｒ・ドウサー氏に発行された米国特許第5,907,685号および「複数のノード間のＩＳＯ／ＯＳＩ通信モデルのＭＡＣ層における時間基準値を発生するためのシステム」を発明の名称とし、１９９５年１月３１日にブラン氏らに発行された米国特許第5,386,542号には、通信リング内での同期化交換の更なる詳細が記載されている。これら米国特許の全内容を本明細書では参考例として援用する。
【００１０】
リモートクロックに対応するようにローカルクロックを調節するために交換を使用する場合、いくつかのメッセージ交換変数、例えばメッセージ伝搬時間を検討しなければならない。更にアドホック無線ネットワークにおける移動ノード間のクロック同期化は、クロックシフトおよびクロックドリフトを含む別の問題を生じさせる。例えば無線ネットワークにおけるノードＡおよびＢを検討すると、所定の時間Ｔにおいて各ノードＡおよびＢ上のクロックレジスタは値ｔＡおよびｔＢを示す。これら２つの値の差、すなわちｔＡ−ｔＢは２つのノード間のクロックシフトである。双方のクロックが同じ値を示すようにするには両クロックの補正値としてクロックシフト値を加えなければならない。下記の式（１）からノードＡにおけるクロック値に適用すべき補正値としてΔＡＢが示され、ノードＢにおけるクロック値に適用すべき補正値としてΔＢＡが示される。
【００１１】
【数１】
2005536919.tif 000003
【００１２】
ここでｔＢは時間ｔにおけるノードＢのクロック値であり、ｔＡは時間ｔにおけるノードＡのクロック値である。
【００１３】
その他のクロック調節を行わない場合、ある時間後、レジスタＡとＢとはそれぞれ値ｔ’Ａおよびｔ’Ｂを示し、ここで各レジスタに対するクロックシフトは再び式（１）を使って決定できる。
【００１４】
【数２】
2005536919.tif 000004
【００１５】
ここでｔ’Ｂは時間ｔ’におけるノードＢのクロック値であり、ｔ’Ａは時間ｔ’におけるノードＡのクロック値である。
【００１６】
ΔＡＢとΔ’ＡＢとが同じでないことを観察することは、異常なことではない。ΔＡＢとΔ’ＡＢとの間の変動は双方のノードＡおよびＢが異なる周波数で作動する発振器によって駆動されるクロックを有し得るということに一部起因している。特に各ノードは異なるユニットで同じ時間（ｔ’−ｔ）を測定する。周波数が変化する結果、１つのクロックで測定される時間が長くなったり短くなったりし、第２クロックで同じ時間が測定される（すなわちノードＡのクロックは同じ時間をノードＢのクロックと異なるように測定する）。更に測定値が時間に対する標準値の実際の時間と同じになることはない（すなわちいずれのクロックも時間を正しく測定しない）。
【００１７】
発生する別の問題は、「クロックドリフト」の問題である。時間ｔから時間ｔ’までの間のクロックシフト値の変動値はクロックのクロックドリフトであり、次の式（２）を使って決定できる。
【００１８】
【数３】
2005536919.tif 000005
【００１９】
ここで、ΔＡＢは時間ｔにおけるノードＡとＢとの間のシフト値であり、Δ’ＡＢは時間ｔ’におけるノードＡとＢとの間のシフト値である。変数ｔＡおよびｔＢはそれぞれ時間ｔにおけるノードＡおよびＢのクロックレジスタ値であり、最後に、変数ｔ’Ａおよびｔ’Ｂはそれぞれ時間ｔ’におけるノードＡおよびＢのクロックレジスタ値である。
式（２）におけるクロックシフト間の関係は、次の式（３）に示されている。
【００２０】
【数４】
2005536919.tif 000006
【００２１】
上記のように、変動は異なる周波数で作動する発振器によって駆動されるクロックをノードＡおよびＢの双方が有し得るという事実に一部起因している。クロックのドリフトを生じさせる周波数の差は、通常ｐｐｍの大きさで測定される。所定のシステムのハードウェア回路基板内で発振器を制御する水晶発振子は、±１ｐｐｍよりも良好な精度レベルを有し得るが、このことは１秒の時間内で２つの回路基板上のクロック値は２μｓより短い時間だけ、すなわち約１７分で２ｍｓよりも短い時間だけドリフト（クロックドリフト）し得ることを意味する。かかるクロックドリフトはより大きくなり得るが、水晶発振子で制御される発振器は比較的長時間にわたって一定の周波数を一般に維持するので、大きさにかかわらず、ドリフトをほとんど一定のままに維持できる。しかし、温度変化またはシールドされていない基板での周辺容量効果からクロックドリフト値のゆっくりとした変動がある程度生じる。
【００２２】
これまでのクロック同期化の説明はノードのクロック間の周波数差、すなわちスキューから生じる問題について認識している。１つの解決方法は電圧制御発振器として機能するローカルクロックを制御するように、ループフィルタによって処理される位相補正条件を設定することである。しかし、この解決方法は例外的に安定な局部発振器およびループフィルタを有するローカルクロックを実現するノードに限定されている。クロック制御における電圧制御発振器の更なる細部は「インターネットの時間同期化：ネットワーク時間プロトコル」と題する、デビッド・Ｌ・ミルズ氏による論文に記載されており、本明細書ではこの論文の全内容を参考例として援用する。
【発明の開示】
【発明が解決しようとする課題】
【００２３】
移動ノードのクロック同期化におけるこれらの問題を仮定した場合、ノードのクロックの高速同期化を行い、ダイナミックなドリフト補正をすると共に、長期間にわたる同期化を維持するためのシステムおよび方法が求められている。
【００２４】
（発明の概要）
本発明の目的はアドホック無線ネットワークにおけるノード間のクロックシフトおよびクロックドリフトを計算するためのシステムおよび方法を提供することにある。
【００２５】
本発明の別の目的は、クロックシフトおよびクロックドリフトの計算された値を使ってアドホック無線値とワークにおけるノードクロックを同期化するためのシステムおよび方法を提供することにある。
【課題を解決するための手段】
【００２６】
これらおよびその他の目的は、選択された基準ノードとクライアントノードとの間で多数の同期化メッセージを交換し、これらメッセージからクロックシフト、クロックドリフトおよび伝搬遅延値を決定し、次にこれら値を使ってクライアントノードのクロックを基準ノードクロックに同期化し、移動ノードロケーションを計算するためのシステムおよび方法によって実質的に達成される。
【００２７】
添付図面と関連させて次の詳細な説明を読めば、本発明の上記およびそれ以外の目的、利点および新規な特徴についてより容易に理解できよう。
【実施例】
【００２８】
（好ましい実施例の詳細な説明）
図１は本発明の一実施例を示すアドホックはパケット交換無線通信ネットワーク１００の一例を示すブロック図である。より詳細には、ネットワーク１００には複数の移動無線ユーザターミナル１０２−１〜１０２−ｎ（一般にノードまたは移動ノード１０２と称す）と、複数のアクセスポイント１０６−１、１０６−２、....１０６−ｎ（一般にノードまたはアクセスポイント１０６と称す）を有する固定ネットワーク１０４とを備え、ノード１０２が固定されたネットワーク１０４にアクセスできるようになっている。固定ネットワーク１０４は、例えばコアローカルアクセスネットワーク（ＬＡＮ）と、複数のサーバおよびゲートウェイルータとを備え、ノード１０２が他のネットワーク、例えば他のアドホックネットワーク、公衆交換電話ネットワーク（ＰＳＴＮ）およびインターネットにアクセスできるようになっている。ネットワーク１００は更に複数の固定されたルータ１０７−１〜１０７−ｎ（一般にノードまたは固定ルータ１０７と称す）を備え、他のノード１０２、１０６または１０７との間でデータパケットをルーティングできるようにしている。
【００２９】
当業者であれば理解できるように、ノード１０２、１０６および１０７は本明細書で参考例として援用する、マイヤー氏に付与された米国特許第5,943,322号およびこれまで引用した米国特許出願第09/897,790号、同第09/815,157号および同第09/815,164号に記載されているように、ノード間で送られるデータパケットのためのルータとして作動する１つ以上の他のノード１０２、１０６または１０７を介して、または直接互いに通信できる。より詳細には、図２に示されるように、各ノード１０２、１０６および１０７はアンテナ１１０に結合されたトランシーバ１０８を備え、このトランシーバは総称としてモデムと称すことができ、コントローラ１１２の制御によりノード１０２、１０６または１０７との間でパケット化されたデータ信号のような信号を送受信できる。このパケット化されたデータ信号は、例えば音声、データまたはマルチメディア情報を含むことができる。
【００３０】
各ノード１０２、１０６および１０７は特に自己およびネットワーク１００内の他のノード１０２、１０６または１０７に関係するルーティング情報を記憶できるメモリ１１４、例えばランダムアクセスメモリ（ＲＡＭ）を含む。これらノード１０２、１０６および１０７は、例えば新しいノード１０２がネットワーク１００に入ったとき、またはネットワーク１００内の現在のノード１０２が移動したときに、一斉送信機構を介して周期的にルーティング情報（ルーティング広告またはルーティングテーブル情報と称される）を互いに交換する。
【００３１】
更に、図２に示されるように、所定のノード、特に移動ノード１０２は多数のデバイス、例えばノートコンピュータターミナル、移動電話ユニット、移動データユニットまたはその他の適当なデバイスから構成できるホスト１１６を含むことができる。各ノード１０２、１０６および１０７はインターネットプロトコル（ＩＰ）およびアドレスリゾリューションプロトコル（ＡＲＰ）を実行するための適当なハードウェアおよびソフトウェアも含むことができる。これらプロトコルの目的は当業者であれば容易に理解できよう。送信制御プロトコル（ＴＣＰ）およびユーザデータグラムプロトコル（ＵＤＰ）を実行するための適当なハードウェアおよびソフトウェアも含むことができる。更に、各ノードは到着時間（ＴＯＡ）の計算を実行するための適当なハードウェアおよびソフトウェアも含むことができる。
【００３２】
背景技術の章に記載したように、データパケットが小さく、送信が頻繁に行われると、無線ネットワーク内で交換されるオーバヘッド情報の量が極めて大きくなり、ネットワークの容量に悪影響を与える。更に、オーバヘッド情報の交換を低減する方法はネットワークのノード間の正確なクロック同期化を必要とすることが多い。例えばオーバヘッドの交換を低減するための時間フレーム（ＴＦ）およびタイムスロット（ＴＳ）方法を実施するには、参加中のノードのクロックを同期化しなければならない。例えば図２ではこれらクロックはコントローラ１１２の一部でもよいし、または完全に別個のクロックユニットでもよい。後述する本発明の実施例は水晶振動子によって駆動される発振器により制御されるクロックを含む、かかるすべてのノードのクロックを同期化し、長期間にわたってクロックの同期を維持する。
【００３３】
本発明の一実施例に係わる、無線ネットワークにおける２つ以上のノードクロックの同期化は、まず基準として１つのクロックを選択しなければならず、次に、残りの各ノードクロックを必要なときにこの基準ノードクロックに同期化できる。図１のネットワーク１００のような移動ノードのネットワークでは、クロック基準を提供するのに１つの特定のノード１０２、１０６または１０７が選択される。例えば説明のためにノード１０６−２を基準ノードとして選択し、１０６−２のクロックにノード１０２−４を同期化すべき場合、図３に示されるようにノード１０６−２と１０２−４との間でメッセージ交換が開始される。
【００３４】
図３の実施例では、無線ネットワーク内にノード１０６−２（ノードＡ）およびノード１０２−４（ノードＢ）が設けられ、これらノードは通信のためにクロックの同期化を必要とするように示されている。ノードＡを基準ノードとして選択する場合、まずノードＡを基準としてノードＢのシフトΔＢＡおよびクロックドリフトδＢＡを決定しなければならない。次の説明では、上の数字をイベント番号とする。例えばｔ２Ｂは第２の事象が生じたときのノードＢにおけるクロックの表示値である、等々である。
【００３５】
クロックシフトΔＢＡおよびクロックドリフトδＢＡを決定するために、図３のノードＡはクロック同期化方法をスタートするためにノードＢにメッセージ１１８を送信し、メッセージが送信されたときの時間ｔ１Ａを記録する。この瞬間に局Ｂにおけるクロックは次の式（４）に示されるように、時間ｔ１Ａにクロックシフトを加えた値に等しい時間ｔ１Ｂを示す。
【００３６】
【数５】
2005536919.tif 000007
【００３７】
ノードＢでは時間ｔ２ＢにてノードＡからのメッセージ１１８が受信される。この時間ｔ２Ｂは次の式（５）に示されるようにｔ１Ｂ＋（ノードＡとＢとの間のメッセージ伝搬時間）に等しい。
【００３８】
【数６】
2005536919.tif 000008
【００３９】
ここでｐＡＢはノードＡからノードＢへの信号伝搬時間である。
【００４０】
時間ｔ３Ｂにて、局ＢはノードＡからメッセージ１１８を受信したときのノードＢにおけるクロックの値（すなわちｔ２Ｂ）を含むメッセージ１２０により、ノードＡが送ったメッセージ１１８に応答する。ノードＢからのメッセージ１２０は時間ｔ４ＢにてノードＡによって受信され、この時間ｔ４Ｂは新しい値と共に式（５）を使用するように示される時間ｔ３Ｂ＋（ノードＡとＢとの間のクロックシフトおよびメッセージ伝搬時間）に等しい。
【００４１】
【数７】
2005536919.tif 000009
【００４２】
端的に述べれば、ノードＢからノードＡに前のメッセージ１２０が送信されたときの時間ｔ３Ｂを含む更に別のメッセージ１２２をノードＢはノードＡに送信する。
【００４３】
両方向の伝搬時間が同じであると仮定した場合に、ノードＡが直接知った時間ｔ１Ａおよびｔ４Ａの値、およびノードＢから受信されたメッセージよりノードＡが間接的に知った時間ｔ２Ｂおよびｔ３Ｂから、ノードＡは、式（６）を使ってノードＡとＢとの間に存在する伝搬時間ｐＡＢおよびクロックシフトΔＢＡの値を計算できる。
【００４４】
【数８】
2005536919.tif 000010
【００４５】
式（６）において、伝搬時間およびクロックシフトを計算した後に、ノードＡはメッセージ１２４内でノードＢに対し、ｐＡＢおよびΔＡＢの値を送信する。次にノードＢはノードＡからのｐＡＢおよびΔＡＢの値を使用してノードＢのクロックとノードＡのクロックとを同期化する。
【００４６】
時間ｔ１Ａおよびｔ４ＡにおけるサーバまたはノードＡにおけるクロックの表示値は、３２ビットの値である。送信時間をセーブするために、時間ｔ２Ｂおよびｔ３ＢにおけるクライアントすなわちノードＢにおけるクロックの表示値が、８ビット値としてメッセージ内で送信される。すべての値は正であるが、いずれかの値に対して「ラップアラウンド」が生じ得る。事象が制御不能となったときに、時間の「ラップアラウンド」が識別される。事象の正常なシーケンスは、式（６）を基準にｔ１Ａ＜ｔ４Ａかつｔ２Ｂ＜ｔ３Ｂとなる。これら値がシーケンスから外れると、時間のラップアラウンド補正（２３２または２８）を適用しなければならない。
【００４７】
数秒後、時間ｔ’において、ノードＡとＢとの間で図３に示されるメッセージ交換が繰り返され、ノードＢで適用するのに必要な新しい伝搬時間および新しいクロックシフトを計算するのに、第２のシリーズの値が使用される。
【００４８】
【数９】
2005536919.tif 000011
【００４９】
ノードＡとＢのクロック周波数が互いに大きくは異なっていない場合、式（７）で決定される新しく計算されるクロックシフトΔ’ＢＡは０となるはずである。クロックドリフトが生じていることを示すように０でない場合、再びノードＢのクロックとノードＡのクロックとを同期化し、後により詳細に説明するように、付録に示されるドリフト制御アルゴリズムを使ってクロックドリフトを保証するために、新しいクロックシフトΔ’ＢＡを使用できる。
【００５０】
アプリケーションに基づき、クロックシフトの補正の周波数を変えてもよい。同期化方法中に０の補正値が発生する場合、次のクロック制御セッションまでの時間インターバルを９００秒まで２倍にできる。第１セッションと第２セッションとの間のインターバルは任意の値とすることができるが、１秒未満の値は実用的ではない。
【００５１】
本明細書に記載された本発明の実施例では、ノードＢのクロックは±１μｓの精度を有すると見なす。更にノードＡからノードＢまでの伝搬時間はノードＢからノードＡまでの伝搬時間に等しいと見なす。ｐＡＢ＝ｐＢＡを維持するには、ノードＡとＢとの間の距離が図３の同期化プロセス中に３００ｍより長く変化してはならない。１００ｍｓより短い時間でノードＡとノードＢとの間のメッセージ交換が完了するので、ＡまたはＢのいずれかが３０００ｍ／ｓよりも速いスピード、すなわち音速の約９倍で移動する場合にしかｐＡＢ≠ｐＢＡとならない。したがって、両方向に信号の伝搬時間が同じでない場合でも、ノードＢの代表的なクロックはノードの移動に起因して生じる誤差を測定できない。
【００５２】
上記のようにノードＡとＢのクロック周波数が互いに大きくは異なっていない場合、新しく計算されるクロックシフトΔ’ＢＡは０となるはずである。０ではない場合（このことはクロックドリフトが生じていることを示す）、ノードＢのクロックとノードＡのクロックとを再び同期化し、ドリフト制御アルゴリズムを使ってクロックドリフトの補償をするのに、新しいクロックシフトΔＢＡを使用する。タイマがインタラプトされると、クロックドリフト補正が起動され、後述するドリフト制御アルゴリズムを実行するドリフト調節機能が立ち上げられる。特にドリフト調節機能を立ち上げるのに、クライアントにおける周期的タイマインタラプトが使用され、予想精度に応じ、この機能は１００ｍｓから５秒の間の一定インターバルで起動できる。２ｐｐｍの相対的クロック精度では、５００ｍｓ以下の起動インターバルは２ミリ秒を超えないサーバとクライアントクロックとの間の誤差レベルを維持する。５秒の起動インターバルの結果、１２マイクロ秒のような大きいサーバとクライアントクロックとの間で補正されないシフトが生じる。
【００５３】
次のように、クロックドリフトを補正するのに付録のコード例に具現化されるドリフト制御アルゴリズムを使用できる。このアルゴリズムは最後のシフト補正値をドリフト制御アルゴリズムへ送るためにグローバル変数「Ｇ＿ＣｌｏｃｋＳｈｉｆｔ」を使用する。クロック同期化セッションの終了時に計算されたクロックシフトの値を含む、変数Ｇ＿ＣｌｏｃｋＳｈｉｆｔにはクロックシフトの絶対値が記憶され、次にクロックサーバによって計算され、クライアントへ送られる。このアルゴリズムはクライアントでクロック調節を実行し、ドリフト評価および補正のためにこのクロックシフト変数を使用する。ここで、ドリフトは分数である。ドリフトの小数部分を無視しても、短時間の効果はないが、長期ではある程度重要となり得る。
【００５４】
ドリフト制御アルゴリズムはドリフト値に近似する２つの整数の除算をシミュレートするものである。ドリフト値はあらかじめ判っていないので、アルゴリズムはクロックシフトであるＧ＿ＣｌｏｃｋＳｈｉｆｔ変数の値にしたがって２つの整数の値の連続調節を実行する。調節ごとに近似値はドリフトの正確な値に近似する。
【００５５】
クライアント局が新しいクロックサーバに接続されるたびに、アルゴリズムの「ｄｒｉｆｔ＿Ｉｎｉｔ」関数がコールされ、この関数がローカルおよびグローバル変数の初期値を設定する。最初のクロック同期化セッションをスタートする直前にこの関数をコールしなければならない。
【００５６】
アルゴリズムの「ドリフト＿ＩＳＲ」関数はインタラプトサービスルーチン（ＩＳＲ）であり、一定時間のインターバルで起動される。図４にはこのＩＳＲのより詳細な説明が示されている。このインタラプトを制御するのにＴＤＭＡクロックを使用する場合、インタラプト間の同じ数のチックを維持するためにＴＤＭＡクロックを調節する度にインタラプトに関連するレジスタを調節しなければならない。図４では、ドリフト制御のためのＩＳＲの例を示すフローチャート２００が示されている。
【００５７】
チャート２００の左側にはターミナル起動時に実行される初期化手順２０２が示されている。この手順２０２はブロック２０４ですべての変数を０に設定する。チャート２００の右側にはクロックドリフト制御手順２０６が示されている。最初の２つのブロック２０８および２１０は補助的な重要性しか有していない。クロック同期化セッションが実行される間、変数「Ｇ＿ＣｌｏｃｋＳｅｓｓｉｏｎ」の値は１となる。ＩＳＲの最初のブロック２０８はクロックセッションが進行中にドリフト補正が実行されないことを保証するものである。Ｇ＿ＣｌｏｃｋＳｅｓｓｉｏｎが進行中である場合、このことはブロック２０８で検出され、この手順はブロック２２０で出る。かかる補正はクロックセッションの終了時に計算されたクロックシフトを無効にし得る。Ｇ＿ＣｌｏｃｋＳｅｓｓｉｏｎが進行中でない場合、この手順はブロック２１０に進む。
【００５８】
ブロック２１０は「ｒｅｍｏｔｅＣｌｏｃｋ」変数に記憶されている数字の大きさをチェックする。この値がブロック２１０で検出されたように過度に大きい場合、すべてのローカル変数をブロック２１８で２で除算し、この手順はブロック２１４へ進む。ＩＳＲの起動を繰り返す間、これら変数はインクリメントされ、代数的なオーバフローを生じさせ得る。値が過度に大きくなければ、この手順はブロック２１２に進む。
【００５９】
０による除算を防止するために、ブロック２１２はブロック２１０と同じ変数の値をチェックする。ｒｅｍｏｔｅＣｌｏｃｋ変数が０でなければ、次の補正値を変数「ｃｏｒｒ」として計算し、「ｃｏｒｒｅｃｔｉｏｎＣｏｎｔｒｏｌ」は値としてブロック２２０の除算の残りをとる。ｒｅｍｏｔｅＣｌｏｃｋが０である場合、この手順はブロック２１４に進み、ここでｒｅｍｏｔｅＣｌｏｃｋは１だけ増加され、「ｄｒｉｆｔＣｏｎｔｒｏｌ」がｃｏｒｒとクロックセッションの終了時に計算されたシフト補正値との間の総和として計算される。Ｇ＿ＣｌｏｃｋＳｈｉｆｔは０にセットされる。その理由は、この値が既に使用されているからである。更にｄｒｉｆｔＣｏｎｔｒｏｌの絶対値と共にｃｏｒｒｅｃｔｉｏｎＣｏｎｔｒｏｌが増加される。
【００６０】
最後のステップとして、ハードウェアクロックのレジスタ、例えばこの場合のＴＤＭＡクロックがブロック２１６におけるｃｏｒｒ変数の値にしたがって補正される。このＩＳＲでは２つのローカル変数ｃｏｒｒｅｃｔｉｏｎＣｏｎｔｒｏｌとｒｅｍｏｔｅＣｌｏｃｋはスタティックである。各変数はスタティック変数として、あるＩＳＲの起動から次の起動まで、その値を保存する。その他の２つの変数、すなわちＧ＿ＣｌｏｃｋＳｅｓｓｉｏｎおよびＧ＿ＣｌｏｃｋＳｈｉｆｔはグローバルであり、それらの値はクロックセッションを制御する関数によって設定される。
【００６１】
上記実施例は双方のノードＡおよびＢにおいて別個のタスク実行プログラムを使って達成される。特に、例えばネットワークサーバとすることができる基準ノードＡは「クロックサーバ」タスク（本明細書では基準タスクとしても知られる）として記載されやすいタスク機能を実行し、一方、基準ノードに同期化される任意のノード１０２とすることができるノードＢは「クロッククライアント」タスク（本明細書ではクライアントタスクとしても知られる）として記載されるタスク機能を実行する。
【００６２】
図１のアドホックネットワーク環境１００では、一般にＩＡＰノード１０６またはアイソレートされたネットワークのルートノードはクロックサーバタスクを行うだけに限定されており、クロッククライアントタスクを実行するのに決して選択されることはない。すなわち、一般に本発明の実施例ではＩＡＰまたはルートノードは基準ノードとしてしか選択できない。ネットワーク１００の他のノード１０２および１０７は各々が基準クロックに同期化でき、各々が他のノードに対するクロック基準を提供できるとき、双方のタスクを実行するのに選択できる。従って同じノードで多くのサーバタスクを同時に実行できるが、１つのクライアントタスクだけを実行してもよい。サーバタスクの数はクロックの同期化を求める隣接ノードの数に等しくなる。１つのノードで実行される各サーバタスクは隣接する１つのノードにしかクロックデータを提供しない。
【００６３】
前に図３で説明したように、同期化のためにノードＡとＢとの間で交換されるメッセージは次の信号を含む。
【００６４】
ＣＬＯＣＫＳＹＮＣ−リクエストするノードによりタイムアウトでサーバに送られる、クロック同期化セッションをスタートさせるためのリクエストである。
【００６５】
ＣＬＯＣＫＴＩＭＥ−サーバによるリクエストノードに対する回答である、３２ビット値としてサーバ時間を含むＣＬＯＣＫＳＹＮＣメッセージである。
【００６６】
ＣＬＯＣＫＲＥＰＬ１−リクエストノードによるサーバへの第１の回答であり、サーバからのＣＬＯＣＫＴＩＭＥメッセージがリクエストノードによって受信されたときのｔ２Ｂ時間を含むＣＬＯＣＫＴＩＭＥメッセージである。
【００６７】
ＣＬＯＣＫＲＥＰＬ２−リクエストノードによるサーバへの第２の回答であり、リクエストノードからＣＬＯＣＫＲＥＰＬ１メッセージが送信されたときのｔ３Ｂ時間を含むＣＬＯＣＫＴＩＭＥメッセージである。
【００６８】
ＣＬＯＣＫＤＡＴＡ−同期化セッションを終了させるサーバによるリクエストノードへの回答であり、リクエストノードのクロックとサーバのクロックとを同期化するためにリクエストノードが必要としたクロックシフトおよび伝搬時間の値を含む。
【００６９】
メッセージ１１８に先立つ第１ＣＬＯＣＫＳＹＮＣメッセージをノードＢからノードＡへ送ることができる（このメッセージは説明されているが、図示されていない）。このメッセージは同期化セッションを求めるリクエストノードＢまたはクライアントによって発行されるリクエストである。このリクエストはクロッククライアントの識別情報およびクロックサーバ識別情報を含む。
【００７０】
図３のＣＬＯＣＫＴＩＭＥメッセージ１１８はクロック同期化セッションをスタートさせるよう、サーバによって送られる。このメッセージはクロックサーバ識別、ＴＤＭＡレジスタ（３２ビット）、ホップ番号、接続性（切断または接続）およびネットワークのタイプ（アイソレートまたはランド）を含む。本明細書に記載する実施例では、サーバの接続性とはサーバとネットワークの間の接続を示す。切断されたサーバはネットワークへの接続部を有しないので、隣接するノードへの接続部も有していない。ネットワークのタイプはサーバを接続するネットワークのタイプを指定する。アイソレートされたネットワークはランド接続を有することはなく、この場合、１つ以上のＩＡＰを介してネットワークによってしか接続を達成できない。
【００７１】
図３のＣＬＯＣＫＲＥＰＬ１メッセージ１２０はＣＬＯＣＫＴＩＭＥメッセージ１１８に対する最初の回答である。このメッセージ１２０の内容はクロックサーバの識別、クロッククライアントの識別およびＣＬＯＣＫＴＩＭＥメッセージ１１８が受信されたときのクロックの表示ｔ２Ｂを含む。図３のＣＬＯＣＫＲＥＰＬ２メッセージ１２２はＣＬＯＣＫＴＩＭＥメッセージ１１８に対する第２の回答であり、サーバ識別、クロッククライアント識別およびＣＬＯＣＫＲＥＰＬ１メッセージ１２０が送信されたときのクロックの表示ｔ３Ｂを含む。
【００７２】
ノードＡおよびＢのモデムが所定の時間にメッセージの送信をスタートさせる能力を有する本発明の別の実施例では、メッセージＣＬＯＣＫＲＥＰＬ１とＣＬＯＣＫＲＥＰＬ２の双方は１つのメッセージＣＬＯＣＫＲＥＰＬに縮小できる。この場合、メッセージが送信されたときの時間、すなわちｔ３Ｂを計算し、メッセージを送信する前にメッセージに含ませることができる。
【００７３】
ＣＬＯＣＫＤＡＴＡメッセージ１２４はクロックサーバ識別、クロッククライアント識別、クライアントクロックのシフトおよびサーバとクライアントの間の伝搬時間を含む。
【００７４】
図３ではこの場合における基準ノード１２６またはサーバノードＡはクロックサーバタスク内に交換メッセージを組み込み、これによってクライアントノードのクロックの同期化が達成される。このようにすることにより、サーバは各クライアントノードに対する一連の作動ステートを通過し、これにより図５に示されるように同期化が生じる。図５ではサーバは任意の時間に２つ以上の隣接ノードにサービスを提供できるので、図５では同期化をリクエストする各隣接ノードに別個のサーバステートサイクルが関連している。
【００７５】
図５の第１のステートまたは「Ｓｔａｒｔ」ステート１３０は、基準ノードにおけるクロックサーバタスクが初期化される。テーブルに新しい隣接ノードが追加されると、追加ノードに関連するクロックサーバタスクがそのサーバで「Ｓｔａｒｔ」ステート１３０へ設定される。ノードの初期化が完了すると、ステートは「Ｓｔａｒｔ」から「Ｉｄｌｅ」１３０へ変化する。
【００７６】
図５の「Ｉｄｌｅ］ステート１３２にあるとき、クロックサーバタスクはＣＬＯＣＫＳＹＮＣまたはＣＬＯＣＫＲＥＰＬ１メッセージを待つ。最初にいずれかが生じる。上記のように、ＣＬＯＣＫＳＹＮＣメッセージはリクエスト中のノードによりサーバに送られるクロック同期化セッションをスタートさせるためのリクエストである。ＣＬＯＣＫＲＥＰＬ１メッセージはリクエストノードによるサーバＣＬＯＣＫＴＩＭＥメッセージに対する第１の回答であり、サーバからのＣＬＯＣＫＴＩＭＥメッセージがリクエストノードによって受信されたときの時間ｔ２Ｂを含む。
【００７７】
図５における１３４において、サーバによってＣＬＯＣＫＳＹＮＣメッセージが受信されると、サーバタスクは１３６においてＣＬＯＣＫＴＩＭＥメッセージを送信することをモデムに指示し、１３８で「Ｗａｉｔ  ＴｘＣ」ステートとなる。このステートではタスクは１５４でＴｘＣを発生する同期シーケンスの完了を待つ。前のメッセージの送信時間は１５２でｔ１Ａとしてセーブされ、タスクは１４０にて「Ｗａｉｔ  Ｒｅｐｌ１」となる。
【００７８】
図５における１４２にて、サーバによりＣＬＯＣＫＲＥＰＬ１メッセージが受信されると、サーバタスクは１４４にて時間ｔ４Ａおよびｔ２Ｂをセーブすることをサーバに指示し、１４６で「Ｗａｉｔ  Ｒｅｐｌ２」ステートとなる。１４８においてＣＬＯＣＫＲＥＰＬ２メッセージが受信されると、クロックの表示ｔ３Ｂが利用できるようになり、サーバは隣接クロックのシフトを計算できる。このクロックシフトは１５０においてＣＬＯＣＫＤＡＴＡメッセージと共にクライアントへ送り戻される。
【００７９】
次のクロック同期化をリクエストしなければならない時間までの時間が５秒未満である隣接ノードは、ＣＬＯＣＫＴＩＭＥメッセージを受信した後に５ｍｓ以内にこのＣＬＯＣＫＴＩＭＥメッセージに回答しなければならない。クロックサーバがコレスポンデントからのメッセージを待っているステートにあるとき、クロックサーバは時間内にメッセージを受信しない場合、「Ｉｄｌｅ」ステートに戻る。
【００８０】
図３では、この場合、クライアントノードＢのように働くリクエスト中のノード１２８は、クロックサーバタスクとメッセージを交換する。このようにする際にクライアントは図６に示されるような一連の作動ステートを通過し、これらステートにノードが関連している。タスクは図６内の１５６における「Ｓｔａｒｔ」からクライアントにおける「ｔｉｍｅ  ｏｕｔ」変数を１秒に初期化し、更に１５８で変数Ｇ＿ＣｌｏｃｋＳｈｉｆｔを０に初期化する。クロックセッションの終了時にＧ＿ＣｌｏｃｋＳｈｉｆｔ変数が計算され、この変数はクロック補正値を含む。クロックドリフトを補正するＩＳＲ中にクロックに対してこの補正値自身が適用される。
【００８１】
図６の１６０において「Ｉｄｌｅ」ステートにあるとき、クライアントタスクは１６８におけるタイムアウトインタラプトまたは１６２におけるＣＬＯＣＫＴＩＭＥメッセージの受信のいずれかを待つ。タスクはメッセージがクロックサーバからのものである場合にしかＣＬＯＣＫＴＩＭＥメッセージに回答せず、次のタイムアウトインタラプトまでの時間は５秒未満である。
【００８２】
図６内のクライアントにおけるタイムアウトインタラプト１６８において、タスクはクロック同期化セッションをスタートさせ、１７０においてサーバにＣＬＯＣＫＳＹＮＣメッセージを送り、１７２において「ＷａｉｔＣＬＯＣＫＴＩＭＥ」ステートに入るためのリクエストを送信することをクライアントノードのモデムに指示する。「ＷａｉｔＣＬＯＣＫＴＩＭＥ」ステートにおいて、タスクは数マイクロ秒（３２ビット）でサーバにおける時間を含む、サーバからのＣＬＯＣＫＴＩＭＥメッセージを予想する。
【００８３】
図６内の１７４における最初の時間の間にＣＬＯＣＫＴＩＭＥメッセージを受信すると、クライアントは１７６において自己のクロックレジスタにサーバクロックをコピーするホース（ｈｏａｒｓｅ）クロック補正を実行し、１７８においてＣＬＯＣＫＲＥＰＬ１により回答する。これによってクライアントがＣＬＯＣＫＴＩＭＥメッセージを受信する最初の時間、すなわちｔ２ＢがＣＬＯＣＫＴＩＭＥメッセージにおけるクロック値と同じ値となることが保証される。このホース補正を実行することにより、システムは精度を失うことなくクロックレジスタの最後の８ビットだけを交換できるようになる。ＣＬＯＣＫＴＩＭＥメッセージの連続受信はクライアントの内容として、かかるホース補正を必要とせず、サーバクロックは数ユニットしか異なっていない値を示さなければならない。
【００８４】
図６において、１６２の「Ｉｄｌｅ」ステート中にクライアントによりＣＬＯＣＫＴＩＭＥメッセージが受信された場合、１７８においてサーバにＣＬＯＣＫＲＥＰＬ１の回答メッセージが送信される前に、１９０にて５ｍｓまでのランダム遅延が適用される。ＣＬＯＣＫＲＥＰＬ１メッセージの送信時間を読み出した後で、１８０にてサーバにＣＬＯＣＫＲＥＰＬ２回答メッセージが送信される。所定時間にメッセージの送信をスタートできるモデム（すなわちクロックが特定の値を示すまで送信をホールドできる能力を含むモデム）を備えたシステムでは、単一のメッセージＣＬＯＣＫＲＥＰＬを使用できる。この場合、メッセージはすべての情報を含む。クロッククライアントタスクはサーバからのＣＬＯＣＫＤＡＴＡメッセージを待つ間、クロッククライアントタスクが１８２にて「ＷａｉｔＣＬＯＣＫＤＡＴＡ」ステートになる。
【００８５】
図６における１８４において、サーバから受信されるＣＬＯＣＫＤＡＴＡメッセージはクロックシフト補正値を含む。この補正値はメッセージから検索され、１８６にてＧ＿ＣｌｏｃｋＳｈｉｆｔ変数に記憶される。この値はローカルクロックのシフトおよびドリフトを補正するために、図４に示されたＩＳＲの実行中に使用される。クロックシフトが０または１ユニットだけである場合、タスクは１８８において、次のクロックセッションのためのタイムアウトを実際の値の２倍にセットする。この手順によってシステムはクロックシフトが、あるセッションから次のセッションに実質的に変化しない場合、連続するクロックセッションの間で時間を指数関数的に増加できる。このことは、クロックシフトの小さい値が一般にドリフト補正アルゴリズムが正しいパラメータを有しているとの正確な表示であるという事実に一致しており、これらパラメータを頻繁に調節する必要はない。
【００８６】
ノードクロックを駆動する水晶発振器の「ジッタ」に起因してクロックチックを喪失させない値まで、上記のように２つのクロック同期化セッションの間の時間を長くすることができる。ほとんどの発振器に対しては、かかるインターバルは約２０〜３０分である。クロックシフトの大きさが２〜４単位の間にある場合、セッション間の時間インターバルは変化しない。クロックシフトが４単位よりも大きい場合、次のクロックセッションまでの時間インターバルは前のインターバルの半分まで短縮されるが、１秒よりも短くされることはない。
【００８７】
上記サーバは接続されたネットワークおよびアイソレートされたネットワークの双方で作動でき、ネットワークコンフィギュレーションに基づき、基準目的のためにクライアントによって選択される。接続されたネットワークはランドサービスへの接続を提供し、一般に１つ以上のアクティブなＩＡＰを含む。しかし、アイソレートされたネットワークはＩＡＰ接続を有しない。この場合、ネットワークのメンバはランドサービスにアクセスしないが、ネットワーク内のサービスを提供できる。クライアントノードによるサーバの選択はこのことを考慮している。
【００８８】
本明細書に記載した本発明の一実施例に係わる同期化手順をスタートする際に、図１内のネットワーク１００の第１クライアント、すなわちノード１０２は、このノードがアイソレートされていると見なし、ノードの通信「ホップ」番号を０に設定する。当業者であれば理解できるように、「ホップ」とはアドホック無線ネットワークにおいてあるノードから別のノードにホッピングすることにより、発信源から宛て先へデータパケットをルーティングする通信ルーティングを意味する。隣接ノード、例えばルーチンのルーティング広告（ＲＡ）からのメッセージを受信した後に、クライアントは受信した最上のホップ番号を識別し、自己のホップ番号を受信した最小のホップ番号に１を加えた値に設定する。クライアントの自己のホップ番号未満のホップ番号を有するすべての隣接ノードからクライアントは最強の受信信号を有する隣接局をクロックサーバまたは基準ノードとして選択する。最も信頼できるクロックサーバを選択するために、適応型送信プロトコル（ＡＴＰ）のために利用できる５秒の予測を使用できる。
【００８９】
クライアントが実際に接続ネットワーク内にある場合、少なくとも１つの隣接ノードがＩＡＰへのかかる接続を有している場合に、自己のホップ番号を設定しながら、クライアントはＩＡＰに接続されていないすべての隣接ノードを無視する。クライアントの自己のホップ番号未満のホップ番号を有するＩＡＰに接続されたすべての隣接ノードから、クライアントは最強の受信信号を有する接続隣接ノードをそのクロックサーバとして選択する。
【００９０】
前に述べたように、隣接ノードのいずれもランドサービスへの接続部を有していない場合、ネットワークはアイソレートされている。クライアントがアイソレートされたネットワーク内に位置する場合、ネットワークのルートノードがネットワーク全体に対するクロック基準を提供する。アイソレートされたネットワークに接続されているクライアントは最小のホップ番号を有し、最大の信号を有する隣接ノードをそのクロックサーバとして選択する。２つのアイソレートされたクロックが相互に通信を開始すると、最初に話し出した一方のクライアントがネットワークのルートとして選択され、クロック基準を提供する。
【００９１】
従って、サーバが選択された時点で、サーバはクライアントに達するのに最小の数のホップを必要とし、最良の信号を提供できる。移動環境ではこれら特性はクライアント、サーバまたはネットワークのいずれかの移動に起因して、時間に対して変化する。次にこのことによってクライアントが常にサーバのステータスをモニタし、別のサーバが最適な選択対象となった場合にサーバを変えなければならない。クライアントは前のサーバが隣接ノードのテーブルから削除され、クロック同期化のために２つの連続するリクエストに回答せず、ネットワークから切り離されるか、またはサーバのホップ番号が局のホップ番号以上となる場合にしか別のサーバを探してはならない。サーバが失われるか、またはサーバを変える動作中、下記のドリフト補正のためのそのときのアルゴリズムは前に計算されたデータを使用しながら、アクティブなままである。
【００９２】
更に無限ループに入るクロックサーバを探すのを防止するためにクロッククライアントはクロックサーバを求めながらそのホップ番号を増加してはならない。クライアントが実際のホップ番号よりも小さいホップ番号を有する隣接ノードを探すことができない場合、クライアントは自らを「アイソレートされている」と広告し、少なくとも１回の広告サイクルの間、クロックサーバを探すことを控えなければならない。かかる控えの後でクライアントはクロックサービスを提供できる隣接ノードのサーチを再度１回スタートできる。
【００９３】
図７、８および１０には上記実施例の応用の結果が示されている。図７はドリフト補正アルゴリズムが５秒ごとに１回実行されるときの２.１５ｐｐｍの相対的ドリフトを有する２つのクロックに対する予想誤差のグラフを示す。プロットは秒ごとの開始時に測定された約９時間の間の２つのクロックの間の誤差の変動を示す。最初の５回の５秒を除き、図７のクロック誤差は±１５μ秒内の変動である。図７におけるライン１９２が左の垂直スケールに関連しており、クロックセッション間のインターバルを秒で示している。セッション間のインターバルはセッション間で３秒の初期値を有し、２つの連続するセッションの間で２０００秒まで急激に増加する。
【００９４】
同様に、図８は２.１５ｐｐｍのクロックドリフトを有する一対のクロックにおいて、ドリフトが５００ｍｓごとに補正されたときのシフト誤差のグラフを示す。図７と比較すると、誤差はより小さいが、セッション間のインターバルは２０００秒に向かってより急速に収束している。従って、上記本発明の実施例を使用した場合、クロックシフトを良好に制御する結果、クロック同期化セッションの数はより少数となる。
【００９５】
サーバおよびクライアントノードに対するドリフト値を近似することにより、本発明の実施例のテストを行うことができる。連続するドリフト近似値δｎは次の式（８）で計算される。
【００９６】
【数１０】
2005536919.tif 000012
【００９７】
ここで、δｎの数列はｎ→∽のときにδｎ→δとなる性質を有する。
【００９８】
ドリフト近似値δｎを計算するために、クロック同期化セッションおよびドリフト制御アルゴリズムから生じたＴＤＭＡレジスタに対してなされたすべてのΔｉ補正値が補正を行った時間ｔｉと共に収集される。個々の値を収集する必要はないが、これら値の総和は必要である。
【００９９】
式（８）によりδｎのすべての値を計算し、プロットする。式（８）ではｔ０は最初のクロック補正を行ったときの時間であるが、式（８）では時間５０で計算した最初の補正値Δ０は使用しない。式（８）では、ｉ＝０からではなく、ｉ＝１の場合から総和をスタートする。図９にはδｎ値のこの結果得られる曲線が示されている。図９のかなり右側部分にはδｎの最も正確な値が１９６として示されている。発振器が温度変化またはその他の原因によるドリフト変動を有する場合、ライン１９８は水平ではなく、振動を示す。
【０１００】
本明細書に説明した本発明の実施例により、ドリフトがどれだけ大きくなったとしても、ほとんど一定のドリフトを有するクロックを使用して高速のクロック同期化およびダイナミックなドリフト補正が可能となる。本実施例は音声パケット当たり少なくとも１.４ｍｓだけ、すなわち３５％音声データ転送のオーバヘッド量を削減するはずである。例えば±１ｐｐｍドリフトによって影響を受ける２つのクロックを、±３μｓ未満離れた状態の同期化を維持するには、本実施例は毎秒内部クロックのドリフトを補正するために各々６０ビットを有する５つのメッセージから成る、３５分ごとの交換を必要とする。無線トラヒックのオーバヘッドは２０００秒ごとに２ｍｓ、すなわち０.０００１％となる一方、この動作をサポートするための１６ＭＨｚのＣＰＵに対する超過負荷は約０.０００２％である。
【０１０１】
以上で、本発明の数例の実施例しか詳細に説明しなかったが、当業者であれば本発明の新規な要旨および利点から実質的に逸脱することなく、実施例において多数の変形が可能であることが容易に理解できよう。従って、特許請求の範囲に記載されているように、本発明の範囲内にはかかるすべての変形例が含まれるものである。
【０１０２】
2005536919.tif 000013
【図面の簡単な説明】
【０１０３】
【図１】本発明の実施例を使用する、複数のノードを含むアドホック無線通信ネットワークの一例のブロック図である。
【図２】図１に示されるような無線ノードの一例のブロック図である。
【図３】本発明の一実施例に係わるクロック同期化メッセージ交換の一例を示すブロック図である。
【図４】本発明の一実施例に係わるクロックドリフト制御のためのインタラプトサービスルーチン（ＩＳＲ）の一例を示すフローチャートである。
【図５】本発明の一実施例に係わるクロック同期化中に生じるサーバのステートの一例を示すフローチャートである。
【図６】本発明の一実施例に係わるクロック同期化中に生じるクライアントのステートの一例を示すフローチャートである。
【図７】本発明の一実施例に係わる５秒ごとのドリフト制御を使用したときのシフト誤差の一例を示すグラフである。
【図８】本発明の一実施例に係わる０.５秒ごとのドリフト制御を使用したときのシフト誤差の一例を示すグラフである。
【図９】本発明の一実施例に係わるドリフト推定の一例を示すグラフである。
【図１】
2005536919.tif 000014
【図２】
2005536919.tif 000015
【図３】
2005536919.tif 000016
【図４】
2005536919.tif 000017
【図５】
2005536919.tif 000018
【図６】
2005536919.tif 000019
【図７】
2005536919.tif 000020
【図８】
2005536919.tif 000021
【図９】
2005536919.tif 000022
【手続補正書】
【提出日】平成16年8月25日(2004.8.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１４
【補正方法】変更
【補正の内容】
【請求項１４】
請求項１に記載の方法において、前記第１の通信を受信するように前記基準ノードを制御する前記工程が、
前記基準ノードを初期化する工程を含み、前記クライアントノードに対する前記第１の回答がクロック同期化メッセージを含む、方法。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１５
【補正方法】変更
【補正の内容】
【請求項１５】
請求項１に記載の方法において、基準ノードを選択するように前記クライアントノードを制御する前記工程が、前記クライアントノードを初期化することを含み、
前記クライアントに対する前記第１の回答がクロック同期化メッセージを含み、
本方法が、前記基準ノードから送られた前記値を使って前記クライアントクロックを補正するように、前記クライアントノードを制御する工程を更に含む、方法。
【国際調査報告】
2005536919.tif 000023
2005536919.tif 000024