(57)【要約】  ネットワークの効率を改善する方法及び装置。発信元ノードは、データが宛先ノードに到着する伝搬遅延を決定する。これは、個別のタイムスロットの大きい部分が、宛先ノードによるデータ受信に使用されることを保証することによって、発信元ノードがデータを効率的に送信できるようにする。次に、宛先ノードは、自分が他のノードに接続されているかどうかを決定し、他の接続されたノードとの間の伝搬遅延を決定する。プロセスは、伝搬遅延が計算されていない他のノードへ自分が接続されていないことをノードが検出するまで継続する。こうして、ネットワーク上の各ノードは、各ノード間の伝搬遅延を知り、ノードはこの情報を利用して、ネットワークを介してデータを効率的に転送する。【選択図】  図３
2009520401.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介してデータを効率的に転送する方法であって、
発信元ノードから宛先ノードへメッセージを送信し、前記メッセージが送信のローカル時間（ｔ１）を示す第１のタイムスタンプを備えるステップと、
前記宛先ノードで前記メッセージを受信し、受信のローカル時間（ｔ２）を表示する第２のタイムスタンプで前記メッセージに押印するステップと、
前記宛先ノードから前記発信元ノードへ返答メッセージを送信し、前記返答メッセージが前記第１のタイムスタンプ、前記第２のタイムスタンプ、及び第３のタイムスタンプを備え、前記第３のタイムスタンプが前記返答メッセージの送信のローカル時間（ｔ３）を示すステップと、
前記発信元ノードで前記返答メッセージを受信するステップと、
前記発信元ノードで前記返答ノードの受信のローカル時間（ｔ４）を決定するステップと、
時間ｔ１、ｔ２、ｔ３、及びｔ４を使用して、前記発信元ノードと前記宛先ノードとの間の範囲又は伝搬遅延の少なくとも１つを計算するステップと
を備える方法。
【請求項２】
更に、前記発信元ノードから前記宛先ノードへ、前記範囲又は伝搬遅延の少なくとも１つを送信するステップを備える、請求項１に記載の方法。
【請求項３】
更に、前記範囲又は伝搬遅延の少なくとも１つに基づいて、前記発信元ノードからデータ・フレームを受信するフレーム・タイミングを前記宛先ノードで調整するステップを備える、請求項１に記載の方法。
【請求項４】
更に、前記宛先ノードにおける前記データ受信のために利用可能なタイムスロットを決定するステップと、
前記利用可能なタイムスロットよりも、前記発信元ノードと前記宛先ノードとの間の前記伝搬遅延にほぼ等しい時間量だけ早く、前記発信元ノードから前記宛先ノードへデータを送信するステップと
を備える、請求項１に記載の方法。
【請求項５】
更に、ネットワーク内の各ノードについて前記方法を反復するステップを備える、請求項１に記載の方法。
【請求項６】
更に、前記方法を反復し、前記時間ｔ１、ｔ２、ｔ３、及びｔ４を使用して、前記発信元ノードと前記宛先ノードとの間の前記範囲又は伝搬遅延の平均を取り、範囲決定結果の正確度を増進するステップを備える、請求項１に記載の方法。
【請求項７】
ノードのクロックを較正する方法であって、
標準８０２．１１時刻同期関数を使用して宛先ノードを発信元ノードで同期するステップと、
前記発信元ノードから前記宛先ノードへメッセージを送信し、前記メッセージが送信のローカル時間（ｔ１）を示す第１のタイムスタンプを備えるステップと、
前記宛先ノードで前記メッセージを受信し、受信のローカル時間（ｔ２）を表示する第２のタイムスタンプで前記メッセージに押印するステップと、
前記第１のタイムスタンプと前記第２のタイムスタンプとの間の差を計算するステップと、
前記計算された差を使用し、前記発信元ノードと前記宛先ノードとの間のクロック・ドリフトを補償することによって、前記宛先ノードのクロックを較正するステップと
を備える方法。
【請求項８】
ネットワークを介してデータを効率的に転送する装置であって、
発信元ノードから宛先ノードへメッセージを送信し、前記メッセージが送信のローカル時間（ｔ１）を示す第１のタイムスタンプを備える発信元ノードと、
前記メッセージを受信して、受信のローカル時間（ｔ２）を表示する第２のタイムスタンプで前記メッセージに押印し、次に宛先ノードから前記発信元ノードへ返答メッセージを送信する宛先ノードであって、前記返答メッセージが前記第１のタイムスタンプ、前記第２のタイムスタンプ、及び第３のタイムスタンプを備え、前記第３のタイムスタンプが前記返答メッセージの送信のローカル時間（ｔ３）を示す宛先ノードと、
前記発信元ノードで前記返答ノードについて受信のローカル時間（ｔ４）を決定し、前記時間ｔ１、ｔ２、ｔ３、及びｔ４を使用して、前記発信元ノードと前記宛先ノードとの間の範囲又は伝搬遅延の少なくとも１つを計算し、前記発信元ノードと前記宛先ノードとの間の前記範囲又は伝搬遅延の少なくとも１つを送信するための、前記発信元ノードに設けられたプロセッサと
を備える装置。
【請求項９】
前記宛先ノードが、更に、前記範囲又は伝搬遅延の少なくとも１つに基づいて、前記発信元ノードからデータ・フレームを受信するフレーム・タイミングを前記宛先ノードで調整する手段を備える、請求項８に記載の装置。
【請求項１０】
前記発信元ノードが、更に、
前記宛先ノードでデータを受信するため利用可能なタイムスロットを決定する手段と、
前記利用可能なタイムスロットよりも、前記発信元ノードと前記宛先ノードとの間の前記伝搬遅延にほぼ等しい時間量だけ早く、前記発信元ノードから前記宛先ノードへ前記データを送信する手段と
を備える、請求項８に記載の装置。
【請求項１１】
宛先ノードへメッセージを送信し、前記メッセージが送信のローカル時間（ｔ１）を示す第１のタイムスタンプを備える発信元ノードと、
前記メッセージを受信し、受信のローカル時間（ｔ２）を表示する第２のタイムスタンプで前記メッセージに押印する宛先ノードと、
前記第１のタイムスタンプと前記第２のタイムスタンプとの間の第１の差を計算するための、前記宛先ノードに設けられたプロセッサと
前記第１のタイムスタンプと前記第２のタイムスタンプとの間の少なくとも第２の差を計算するための、前記宛先ノードに設けられたプロセッサと、
を備える、ノードのクロックを較正する装置であって、
前記発信元ノードが、少なくとも第２のメッセージを前記宛先ノードへ送信し、前記少なくとも第２のメッセージが、送信のローカル時間（ｔ１）を示す第１のタイムスタンプを備え、
前記宛先ノードが、前記少なくとも第２のメッセージを受信し、受信のローカル時間（ｔ２）を表示する第２のタイムスタンプで前記少なくとも第２のメッセージに押印し、
前記第２の差を計算するための前記プロセッサが、前記第１の差と前記少なくとも第２の差との間の平均を計算し、
前記第２の差を計算するための前記プロセッサが、前記平均を使用して前記宛先ノードの前記クロックを較正する、装置。
【請求項１２】
更に、請求項７に記載の方法を少なくとも1回反復するステップと、
前記計算された差を平均するステップと、
前記計算された差の前記平均を使用し、前記発信元ノードと前記宛先ノードとの間のクロック・ドリフトを補償することによって、前記宛先ノードのクロックを較正するステップと
を備える、請求項７に記載の方法。
【請求項１３】
更に、請求項１に記載の方法を反復するステップと、
前記時間ｔ１、ｔ２、ｔ３、及びｔ４を使用して、前記発信元ノードと前記宛先ノードとの間の前記範囲又は伝搬遅延の少なくとも１つを平均するステップと、
前記範囲又は伝搬遅延の少なくとも１つの前記平均に基づいて、前記発信元ノードからデータ・フレームを受信するフレーム・タイミングを前記宛先ノードで調整するステップと
を備える、請求項１に記載の方法。
【請求項１４】
ノードの位置を決定する方法であって、
発信元ノードから宛先ノードへメッセージを送信し、前記メッセージが送信のローカル時間（ｔ１）を示す第１のタイムスタンプを備えるステップと、
前記宛先ノードで前記メッセージを受信し、受信のローカル時間（ｔ２）を表示する第２のタイムスタンプで前記メッセージに押印するステップと、
前記宛先ノードから前記発信元ノードへ返答メッセージを送信し、前記返答メッセージが前記第１のタイムスタンプ、前記第２のタイムスタンプ、及び第３のタイムスタンプを備え、前記第３のタイムスタンプが前記返答メッセージの送信のローカル時間（ｔ３）を示すステップと、
前記発信元ノードで前記返答メッセージを受信するステップと、
前記発信元ノードで前記返答ノードについて受信のローカル時間（ｔ４）を決定するステップと、
前記時間ｔ１、ｔ２、ｔ３、及びｔ４を使用して、前記発信元ノードと前記宛先ノードとの間の範囲を計算するステップと、
指向性アンテナを使用して、前記宛先ノードが突き止められる近似区域を決定するステップと、
前記発信元ノードからの前記範囲で突き止められた前記近似区域の中の前記宛先ノードの近似位置を決定するステップと
を備える方法。
【請求項１５】
前記指向性アンテナが複数の放射素子を備え、これらの放射素子の各々が放射パターンを形成し、前記近似区域が前記放射パターンの１つの中にある、請求項１４に記載の方法。
【請求項１６】
更に、複数の指向性アンテナを使用して、複数のノードへの複数の範囲を計算し、前記近似位置の正確度を改善するステップを備える、請求項１４に記載の方法。
【請求項１７】
前記指向性アンテナが全方向性であり、
複数の全方向性アンテナ及び三角測量計算を使用してノードの位置を計算するステップを備える、請求項１６に記載の方法。
【請求項１８】
ノードの位置を決定する装置であって、
発信元ノードから宛先ノードへメッセージを送信し、前記メッセージが送信のローカル時間（ｔ１）を示す第１のタイムスタンプを備える発信元ノードと、
前記メッセージを受信し、受信のローカル時間（ｔ２）を表示する第２のタイムスタンプでメッセージに押印し、次に宛先ノードから前記発信元ノードへ返答メッセージを送信する宛先ノードであり、前記返答メッセージが前記第１のタイムスタンプ、前記第２のタイムスタンプ、及び第３のタイムスタンプを備え、前記第３のタイムスタンプが前記返答メッセージの送信のローカル時間（ｔ３）を示す、宛先ノードと、
複数の放射パターンを作成するため前記発信元ノードに結合された指向性アンテナであり、各々の前記放射パターンがアンテナから一意の方向へ伸びる指向性アンテナと、
返答ノードの受信のローカル時間（ｔ４）を前記発信元ノードで決定し、前記時間ｔ１、ｔ２、ｔ３、及びｔ４を使用して、前記発信元ノードと前記宛先ノードとの間の範囲を計算し、前記宛先ノードから前記メッセージを受信するために使用される前記放射パターンを決定して、前記決定された放射パターンが方向を規定するための、前記発信元ノードに設けられたプロセッサと
を備える装置。
【請求項１９】
前記指向性アンテナが全方向性放射パターンを有する、請求項１８に記載の装置。
【発明の詳細な説明】
【発明の分野】
【０００１】
[0001]本発明の実施形態は、一般的には、ネットワークに関し、更に具体的には、ネットワークを介するデータの効率的転送、及びネットワークを監視及び管理する手法に関する。
【関連技術の説明】
【０００２】
[0002]通常のネットワークは、典型的にはハブ及びスポーク形状で配列されたノード及びルータを備える。ノードはデータをルータへ送信することによって他のノードと通信し、次にルータはデータを宛先ノードへ結合する。ノードはネットワーク上に存在する他の全ノードの存在に気付かないが、ルータはネットワーク上の全ノードの存在に気付いている。ルータはネットワーク上の全ノードの物理アドレスを記憶し、１つのノードから他のノードへの送信を容易にする。
【０００３】
[0003]アドホック・ネットワークは通常のネットワークとは異なる。なぜなら、ネットワーク内でデータを配布する中央切り替え点、即ち、ルータが存在しないからである。ノードはネットワーク上の他のノードの存在に気付いており、データは、相互接続されたノードを介してデータを渡すことによって、ネットワークを横切って送信される。
【０００４】
[0004]アドホック・ネットワークの１つの例はメッシュ・ネットワークである。メッシュ・ネットワーク上のノードは、個別のタイムスロットの間でのみデータを受信及び送信する。例えば、データを宛先ノードへ送信している発信元ノードは、宛先ノードでデータの聴取に指定された個別のタイムスロットの間にデータを送信する。タイムスロットは、データ部分及び伝搬遅延に割り振られた部分を備える長さを有するように設計される。こうして、伝搬遅延及び発信元と宛先ノードとの間の距離は、利用されないタイムスロット部分を引き起こし、データの送信は、可能な限り効率的とは言えない。
【０００５】
[0005]発信元と宛先との間の距離が知られていないネットワークでは、タイムスロットは最悪ケースの伝搬遅延を収容しなければならない。そのような送信の非効率を回避するためには、時刻同期されたノードを使用し、ノード間で送信時間情報を送ることによって、伝搬遅延が測定されてもよい。こうして、いずれのノードも、送信時間から現在の時間を減じることによって、伝搬遅延を計算することができる。次に、タイムスロットの長さが、計算された遅延に適合するようにカスタマイズされ、全体のタイムスロットがデータ送信に使用できるようにされる。しかしながら、そのような計算を容易にするため、ネットワークは、時間基準、例えば、全地球測位システム(ＧＰＳ)又は他の全世界時間基準に同期される。そのような同期は、ネットワークの開発及び展開にコストを追加する。
【０００６】
[0006]したがって、時分割多元接続ネットワークを介してデータを効率的に転送するための改善方法及び装置の必要性が存在する。
【発明の概要】
【０００７】
[0007]本発明は、ネットワークの効率を改善し、及び／又はネットワーク監視及び管理能力を提供する方法及び装置である。１つの実施形態において、発信元ノードは、データが宛先ノードに到着する伝搬遅延を決定する。これは、個別のタイムスロットの大きい部分が、宛先ノードによるデータ受信に使用されることを保証することによって、発信元ノードがデータを効率的に送信することを可能にする。次に、宛先ノードは、自分が他のノードに接続されているかどうかを決定し、他の接続されたノードとの間の伝搬遅延を決定する。プロセスは、伝搬遅延が計算されていない他のノードへ自分が接続されていないことをノードが検出するまで継続する。こうして、ネットワーク上の各ノードは、各ノード間の伝搬遅延を知り、ノードはこの情報を利用して、ネットワークを介してデータを効率的に転送し、及び／又はネットワークを監視及び管理する。
【０００８】
[0008]本発明の上記の特徴を詳細に理解できるように、実施形態を参照することによって、上記で短く要約された本発明の更に具体的な説明が得られてもよい。実施形態の幾つかが、添付の図面で図解される。しかしながら、注意すべきこととして、添付された図面は本発明の典型的な実施形態を図解するだけで、本発明の範囲を限定すると考えてはならない。なぜなら、本発明は他の同じように効果的な実施形態を承認するからである。
【詳細な説明】
【０００９】
[0015]図１は、接続されたノード１０２を備えるネットワーク１００の１つの実施形態の図形の描写である。ノード１０２は相互に接続され、複数の経路(ノード間の線によって示される)が、各々のノード１０２の間に存在する。本発明を利用して利益を得る例示的ネットワークは、２００２年４月１５日に出願された同一出願人による米国特許出願第１０／１２２，８８３号、及び２００２年４月１５日に出願された同一出願人による米国特許出願第１０／１２２，８８６で開示されるメッシュ・ネットワークである。これら双方の特許出願は、参照して本明細書に組み入れられる。当業者は、下記の開示から、有線及び無線の他のネットワーク接続形態が、本発明を使用することによって利益を見出すことを実感するであろう。
【００１０】
[0016]本発明は、ネットワーク１００の効率を改善する方法及び装置である。本発明の１つの実施形態において、発信元ノード１０２ｘ（ここでｘは整数）、例えば、ノード１０２１は、データが宛先ノード１０２ｙ（ここでｙは整数）、例えば、ノード１０２２に到着する伝搬遅延を決定する。これは、個別のタイムスロットの大きい部分が使用されて、データが宛先ノード１０２２へ送信されることを保証することによって、発信元ノード１０２１がデータを効率的に送信することを可能にする。次に、宛先ノード１０２２は、自分が他のノード１０２４、１０２５、１０２６へ接続されているかどうかを決定し、他の接続ノードとの間の伝搬遅延を決定する。プロセスは、伝搬遅延が計算されていない他のノード１０２ｘ，ｙへ自分が接続されていないことをノード１０２ｘ，ｙが検出するまで継続する。こうして、ネットワーク上の各ノード１０２ｘ，ｙは、それ自身と各隣接ノード間の伝搬遅延を知り、ノードはこの情報を使用し、ネットワークを介して効率的にデータを転送する。
【００１１】
[0017]図２は、ノード１０２のブロック図である。ノード１０２は、１つ又は複数の個々のコンピュータ、無線デバイス、パーソナル・ディジタル・アシスタント、デスクトップ・コンピュータ、ラップトップ・コンピュータ、サーバ、又はコンピュータ又は通信ネットワークへの接続から利益を得る他のディジタル・デバイスであってもよい。１つの具体的実施形態において、ノードの１つ、例えば、ノード１０２１は、ネットワーク１００をブロードバンド・バックボーンへ接続するゲートウェイである。そのようなものとして、ゲートウェイは、当面のネットワーク１００の外部位置へのネットワーク・データ・トラフィックの玄関となる。
【００１２】
[0018]ノード１０２は、ＣＰＵ２０２、サポート回路２０６、メモリ２０４、及びネットワーク・インタフェース２０８を含む。ＣＰＵ２０２は、１つ又は複数の容易に入手可能なマイクロプロセッサ又はマイクロコントローラを備えてもよい。サポート回路２０６は、ＣＰＵの動作をサポートするために使用される周知の回路であり、１つまたは複数のキャッシュ、電源、入力/出力回路、ネットワーク・インタフェース・カード、クロック回路、などを備えてもよい。メモリ２０４は、ランダム・アクセス・メモリ、読み出し専用メモリ、取り外し可能ディスク・メモリ、フラッシュ・メモリ、光メモリ、又はこれらの型のメモリの様々な組み合わせを備えてもよい。メモリ２０４は、時には、メイン・メモリと呼ばれ、一部分はキャッシュ・メモリ又はバッファ・メモリとして使用されてもよい。メモリ２０４は、様々な形態のソフトウェア及びファイル、例えば、オペレーティング・システム（ОＳ）２１０及び通信ソフトウェア２１２を記憶する。通信ソフトウェア２１２は、ＣＰＵ２０２によって実行され、下記で説明されるような本発明の動作を容易にする。オペレーティング・システム２１０は多数の周知のオペレーティング・システム、例えば、ＬＩＮＵＸ、ＷＩＮＤＯＷＳ、ＷＩＮＤＯＷＳ ＣＥ、ＳＭＡＲＴＰＨＯＮＥ、ＰＡＬＭ、などの１つであってもよい。
【００１３】
[0019]ネットワーク・インタフェース２０８は、ノード１０２をネットワーク１００へ接続する。ネットワーク・インタフェース２０８は、他のノードへの有線又は無線接続を容易にしてもよい。もしノード１０２がゲートウェイであれば、ネットワーク・インタフェース２０８は有線ブロードバンド・バックボーンへ結合する。追加的に、インタフェース２０８は、有線及び／又は無線接続を経由して、狭帯域幅通信路によりネットワークの他のノードへ結合する。
【００１４】
[0020]本発明の１つの実施形態において、通信ソフトウェア２１２は、時分割多元接続アーキテクチャ（ＴＤМＡ）を採用するネットワークの効率を増進するために使用される。本発明は、ネットワークのノードが共通の同期時間基準、例えば、ＧＰＳに頼らない非同期ネットワークで特別の使用を見出す。非同期ＴＤМＡ内ネットワークの中で、発信元ノード、例えば、ノード１０２１は、宛先ノード、例えば、ノード１０２２へ、割り振られたタイムスロットの間にデータを送信する。宛先ノード１０２２は、割り振られたタイムスロットの間に、データを受信又は聴取する。こうして、ネットワーク１００の効率は、発信元ノード１０２１によって増進され得る。発信元ノード１０２１は、宛先ノード１０２２がデータを受信するように設定されるとき、即ち、送信及び受信スロットが同期されてデータ・スループットを最大にすべきであるとき、送信されたデータがタイムスロットの始めで受信される確率を増加する。
【００１５】
[0021]宛先ノード１０２２がタイムスロットの始めでデータを受信するように発信元ノード１０２１がデータを送信する確率は、伝搬遅延によって影響される。周知されるように、伝搬遅延は、発信元ノード１０２１からの送信データの出発と、宛先ノード１０２２における送信データの到着との間のタイムラグである。
【００１６】
[0022]本発明の１つの実施形態において、各ノードによって実行される通信ソフトウェア２１２は、３方向ハンドシェイクを遂行することによって、発信元ノード１０２１と宛先ノード１０２２との間の伝搬遅延を測定する。一度決定されると、発信元ノード１０２１は伝搬遅延を宛先ノード１０２２へ送信する。宛先ノード１０２２は、伝搬遅延を使用して、宛先ノード１０２２が発信元ノード１０２１からの送信を聴取するタイムスロットを遅らせる。言い換えれば、遅延は、発信元ノードがデータを送信するように割り振られたタイムスロット上のデータを宛先ノードが聴取する前の時間量であり、宛先ノードでの受信に割り振られたタイムスロットの始めでデータが受信されることを保証する。
【００１７】
[0023]一度、発信元ノード１０２１及び宛先ノード１０２２が相互間の伝搬遅延に気付くと、各ノードはデータの送信を時間調節して、受信ノードがデータ受信に割り振られたタイムスロットの始めでデータを受信するようにする。このようにして、共通時間基準なしに２つのノード間の同期が達成される。
【００１８】
[0024]次に、宛先ノード１０２２は、ネットワーク１００上の隣接ノード１０２４、１０２５、１０２６に対し発信元ノード１０２２として行動する。ノードの通信ソフトウェア２１２は、宛先ノード１０２２と、接続されたノード１０２４、１０２５、１０２６との間の伝搬遅延を決定する。プロセスはネットワーク１００の至る所で再帰的に使用され、各ノード１０２がそれ自身と他の接続されたノード１０２との間の伝搬遅延に気付くようにされる。
【００１９】
[0025]その結果、タイミング情報がネットワーク１００を介して外部へ伝搬され、全てのノード１０２が共通時間基準を使用することなく隣接ノードと同期される。
【００２０】
[0026]図３は通信ソフトウェア２１２の動作の方法３００のフローチャートを描写し、図４は２つのノード１０２ｘ及び１０２ｙの間のデータ・フレームの送信及び受信の図形の図を描写する。本発明の動作を最良に理解するため、読者は図３及び図４を同時に観察すべきである。
【００２１】
[0027]図３の方法３００は、発信元ノード１０２ｘによって遂行される方法ステップ３０１と、宛先ノード１０２ｙによって遂行される方法ステップ３０３とに分割される。方法３００は、ステップ３０２で始まり、ステップ３０４へ進む。ステップ３０４において、発信元ノード１０２ｘはデータ・フレーム４０２の中で同期メッセージ４０８を送信する。メッセージ４０８は送信時間ｔ１を含む。送信は宛先ノード１０２ｙへ宛てられる。ノード１０２ｘからノード１０２ｙへデータ・フレーム４０２を送信するときの未知の伝搬遅延は、参照番号４０６によって表わされる。
【００２２】
[0028]ステップ３０６において、宛先ノードはフレーム４０２を受信する。ステップ３０８において、宛先ノード１０２ｙは、ネットワーク・インタフェース２０８によって提供された自分自身のタイムスタンプ４０９でメッセージに押印する。タイムスタンプ４０９は、宛先ノード１０２ｙがデータの完全なフレームを受信したローカル時間ｔ２を表示する。
【００２３】
[0029]１つの実施形態において、ノードで使用されるハードウェアは、ＩＥＥＥ８０２．１１ｘに準拠する。ここでｘはａ、ｂ、ｃ、ｄ、ｅ、ｆ、又はｇである。そのような準拠ハードウェアにおいて、時刻同期関数（ＴＳＦ）が使用され、ノードにおけるローカル時間に基づいてタイムスタンプを作成してもよい。ＴＳＦの通常の使用は、宛先ノード１０２ｙのクロックを発信元ノード１０２ｘのクロックと同期することである。本発明が機能するためには、発信元ノード１０２ｘと宛先ノード１０２ｙとの間のクロック同期を必要としない。しかしながら、ＴＳＦを使用して、宛先ノード１０２ｙのクロックを発信元ノード１０２ｘのクロックで同期する場合でも、本発明は依然として機能する。ＴＳＦの動作は、当業者によって周知である。
【００２４】
[0030]タイムスタンプ情報を備えるメッセージは、発信元ノード１０２ｘのクロックで宛先ノード１０２ｙのクロックを較正するためにも使用され得る。較正は発信元ノード１０２ｘによって遂行される。発信元ノード１０２ｘは、タイムスタンプ情報を備える複数のメッセージを宛先ノード１０２ｙへ送る。宛先ノード１０２ｙは、受信時間を示すローカル時間のタイムスタンプでメッセージに押印し、次に発信元ノード１０２ｘがメッセージを送信した時間と受信時間との間の差を計算する。方法は、発信元ノード１０２ｘによって送信された複数のメッセージの中の各メッセージについて反復される。宛先ノード１０２ｙは差を平均し、この平均を使用して自分のクロックを較正する。
【００２５】
[0031]ステップ３１０において、宛先ノード１０２ｙは送信時間ｔ３を含むタイムスタンプ４１０でメッセージに押印する。次に、ステップ３１２において、宛先ノードはデータ・フレーム４０４を発信元ノード１０２ｘへ送信する。データ・フレーム４０４はタイムスタンプ４０８、４０９、及び４１０を備える。これらのタイムスタンプは、データ・フレームの送信時間（ｔ１）、受信が完了した時間（ｔ２）、及びデータ・フレームの返却送信時間（ｔ３）を提供する。
【００２６】
[0032]ステップ３１４において、発信元ノード１０２ｘはデータ・フレーム４０４を受信し、ステップ３１６において、ノード１０２ｘはデータ・フレームの完全な受信のローカル時間ｔ４を決定する。ステップ３１８において、発信元ノード１０２ｘはメッセージ内のタイムスタンプ情報及び時間ｔ４に基づいて発信元ノード１０２ｘと宛先ノード１０２ｙとの間の範囲を計算する。発信元ノードは、送信時間（ｔ１）、受信時間（ｔ２からデータ・フレームの長さを差し引いたもの）、宛先ノードからの送信時間（ｔ３）、及び発信元ノードにおける受信時間（ｔ４からデータ・フレームの長さを差し引いたもの）を知る。これらの時間は、次のように伝搬遅延を引き出すために処理される。
【００２７】
[0033]  伝搬遅延＝（ｔ４-ｔ１-（ｔ３-ｔ２））／２
【００２８】
[0034]伝搬遅延の計算は、継続的に反復可能であり、時間の経過に従って計算された伝搬遅延の平均は、クロックの分解能を増進する。例えば、もし使用されるクロック分解能が１マイクロ秒であれば、１つの計算の正確度は、近似的に１マイクロ秒であるか１マイルの１／５である。メッセージが送信される時間を巧妙にランダム化することによって、メッセージはマイクロ秒クロックと相関しないようにされ、範囲の結果は、十中八九２つの値の間に入り、この２つの値のそれぞれの分布は真の値を示す。例えば、もし計算が８、８、８、７、８、８、７、８、８、８マイクロ秒の結果を生じるならば、真の値は近似的に７．２マイクロ秒である。これによって、クロック分解能を超える正確な結果を取得することができる。
【００２９】
[0035]実現されたアルゴリズムは、更に、フレームの送信に要する時間量（ｙ ｍｂｐｓでｘバイト）を考慮に入れる。なぜなら、本発明の１つの実施形態において、送信及び受信されたタイムスタンプは、フレーム開始及びフレーム終了に対応するからである。
【００３０】
[0036]下記のステップは任意である。即ち、これらのステップは、本発明が機能するためには必要でないが、追加の利益を提供する。ステップ３２０において、発信元ノード１０２ｘは範囲及び／又は伝搬遅延を宛先ノード１０２ｙへ送信する。ステップ３２２において、宛先ノード１０２ｙは範囲（又は遅延）を受信する。ステップ３２４において、宛先ノード３２４は発信元ノード１０２ｘからのデータを受信するフレーム・タイミングを設定し、データ・フレームが効率的に利用されるようにする。
【００３１】
[0037]ステップ３２６において、宛先ノード１０２は、それがネットワーク１００上の発信元ノード１０２ｘを除く他のノードに接続されているかを調べるためにテストする。もし質問の答えが肯定であれば、方法はステップ３０４へ進む。ステップ３０４において、宛先ノードは他の隣接ノードに対する発信元ノードとなる。もし質問の答えが否定であれば、方法はステップ３２０で終了する。
【００３２】
[0038]図５は、宛先ノード内のクロックを発信元ノード内のクロックで同期及び較正する方法を詳細に示すフローチャートを描写する。方法は、標準８０２．１１時刻同期関数を利用する。
【００３３】
[0039]方法５００はステップ５０２でスタートし、ステップ５０４へ進む。ステップ５０４において、発信元ノードは時刻同期関数メッセージを宛先ノードへ送信する。ステップ５０６において、宛先ノードは標準８０２．１１時刻同期関数に従って自分のクロックを発信元ノードへ同期する。ステップａ５０８において、発信元ノードと宛先ノードとの間の範囲が計算される。ステップ５１０において、発信元ノード及び宛先ノードのクロックは、２つのノード間の伝搬遅延に等しい量だけ非整列にされる。これは、発信元ノードから宛先ノードへ送信されたフレームが、適正な時間に受信されることを可能にする。
【００３４】
[0040]方法５００は、更に、発信元ノードと宛先ノード間のクロックを較正する方法を提供する。ステップ５１２において、発信元ノードは複数の一方向メッセージを宛先ノードへ送信し、宛先ノードでクロックを較正する。ステップ５１４において、発信元ノードと宛先ノード間のクロック速度差が宛先ノードで計算される。理想的には、発信元ノードのクロックは宛先ノードのクロックと同期されており、ノード間の伝搬時間によってずらされているので、宛先ノードにおける受信タイムスタンプは、発信元ノードからの送信タイムスタンプとマッチすべきである。発信元ノードと宛先ノード間のクロック・ドリフトは、ノード間のクロック速度差を計算し、この差を使用して宛先ノードのクロックを較正することによって、最小にされ得る。較正のステップは、宛先ノードが発信元ノードに同期される間に起こる。方法は、ステップ５１６で終了する。
【００３５】
[0041]図６は、ノード６０２、６０４、及び６０８上にそれぞれ置かれた指向性アンテナ６１６１〜６１６３(集約的に６１６)を使用することによって、ノード６０８の位置を決定するために使用できるノード配列を描写する。アンテナ６１６は複数の放射器を備え、これらの放射器は個別のメイン・ビームを形成し、これらのメイン・ビームは、各アンテナから放射状に伸びる実質的に円錐の放射パターンを有する。指向性アンテナ６１６は、円錐形区域６１０、６１２、及び６１４の中で信号を受信及び送信するように設計され、ノード６０８は各ノード６０２、６０４、及び６０６へ信号をブロードキャストし、各ノードの上に置かれた指向性アンテナ６１６によって信号が受信される。その結果、もしアンテナ６１６が６つの素子を有するならば、各素子はほぼ３０度の広さの放射パターンを形成する。
【００３６】
[0042]ノード６０８の近似位置は、第1のノード６０２及び第１の指向性アンテナ６１６１のみを使用して決定可能である。ノード６０８と第１のノード６０２間の距離は、上記で説明した範囲決定手法を使用して計算される。ノード６０８は１つのアンテナ素子を経由して（例えば、円錐６１４を経由して）ノード６０２と通信する。こうして、計算された範囲での円錐の中でノード６０８が突き止められなければならないことが知られる。ノード６０８の更に正確な位置は、円錐６１４によって描写された指向性アンテナ６１６１の焦点を狭くすることによって、例えば、より狭いビーム幅を有する更に多くの素子を追加することによって、決定され得る。
【００３７】
[0043]第２のノード６０４は、ノード６０８の一層正確な位置を確立するために使用可能である。第２のノード６０４も指向性アンテナ６１６２を有する。第２のノード６０４とノード６０８間の範囲が計算される。ノード６０８は、円錐６１０によって描写された区域の中で突き止められる。円錐６１０は、指向性アンテナ６１６２から外側へ放射し、円錐６１４によって描写された区域と交差する。第１のノード６０２及び第２のノード６０４からの計算された範囲の中の円錐６１０及び６１４の交差内の位置を見出すことによって、近似位置が決定され得る。
【００３８】
[0044]ノード６０８の一意の位置は、第３のノード６０６を使用することによって決定され得る。第３のノード６０６は指向性アンテナ６１６３を有する。ノード６０８は、円錐６１２によって描写される区域の中で突き止められる。円錐６１２は、指向性アンテナ６１６３から外側へ放射し、円錐６１０及び６１４によって描写された区域と交差する。三角測量法を使用し、ノード６０２、６０４、及び６０６の計算された範囲の中の円錐６１０、６１２、及び６１４の交差内の位置を見出すことによって、ノード６０８の一意の位置が決定され得る。
【００３９】
[0045]本発明の代替実施形態において、アンテナ６１６１〜６１６３は、全方向性アンテナであってもよく、上記のノード範囲決定方法を使用して生成された範囲決定情報は、ノード位置を決定するため通常の三角測量計算で使用可能である。
【００４０】
[0046]前述したことは、本発明の実施形態に向けられているが、本発明の基本的範囲から逸脱することなく他の更なる実施形態が考え出されてもよく、本発明の範囲は、次の特許請求の範囲によって決定される。
【図面の簡単な説明】
【００４１】
【図１】ネットワークの図形図である。
【図２】ネットワーク・ノードのブロック図である。
【図３】本発明を実現する方法を詳細に示すフローチャートである。
【図４】本発明を使用して範囲を決定する図形描写である。
【図５】本発明で実現され得るクロック較正方法を詳細に示すフローチャートである。
【図６】第４のノードの位置を決定するための、３つのノード間の三角測量の図形描写である。
【図１】
2009520401.tif 000003
【図２】
2009520401.tif 000004
【図３】
2009520401.tif 000005
【図４】
2009520401.tif 000006
【図５】
2009520401.tif 000007
【図６】
2009520401.tif 000008
【国際調査報告】
2009520401.tif 000009
2009520401.tif 000010