動的道路環境におけるローカルピアグループ（ＬＰＧ）ネットワーク用の適合プロトコル
動的な道路（可動性）環境においてローカルピアグループ（LPG）ネットワークのサイ
ズを決定するための方法およびシステムが提供される。一実施形態において、方法には、第１のノードと第２のノードとの間の往復時間を測定することと、測定往復時間を利用して、ローカルピアグループネットワークのサイズをルックアップテーブルから選択することと、が含まれる。別の実施形態において、方法には、往復時間が、ハートビート信号の時間間隔を超過する場合を決定することと、往復時間がハートビート信号の時間間隔を超過する場合に、ローカルピアグループネットワークのサイズを調整することと、が含まれる。
ズを決定するための方法およびシステムが提供される。一実施形態において、方法には、第１のノードと第２のノードとの間の往復時間を測定することと、測定往復時間を利用して、ローカルピアグループネットワークのサイズをルックアップテーブルから選択することと、が含まれる。別の実施形態において、方法には、往復時間が、ハートビート信号の時間間隔を超過する場合を決定することと、往復時間がハートビート信号の時間間隔を超過する場合に、ローカルピアグループネットワークのサイズを調整することと、が含まれる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に無線メッシュネットワークに関し、特に動的道路環境におけるメッシュネットワーク用の適合プロトコル（adaptation protocol）に関する。
【背景技術】
【０００２】
無線メッシュネットワークは、メッシュトポロジに組織された無線ノードで構成された通信ネットワークである。完全なメッシュトポロジにおいて、各ノードは、他のノードのそれぞれに直接接続される。部分的なメッシュトポロジにおいて、ノードは、他のノードの全てではなく、いくつかだけに接続される。単一ネットワークとして一緒に動作する無線ノードのカバレッジエリアは、時にはメッシュクラウドとして知られている。無線メッシュネットワークは、802.11, 802.16およびセルラー技術を含む様々な無線規格を介して実現することができる。
【０００３】
メッシュネットワークは、ノード間の多対多接続という利点を提供する。すなわち、通常、ノード間で情報を通信するための2つ以上の可能なルートが存在する。メッシュネッ
トワークはまた、これらの接続を動的に更新および最適化することができる。新しいノードが利用可能になると、それらは、メッシュネットワークに追加してもよい。ノードはまた、メッシュネットワークから除去してもよい。したがって、メッシュネットワークのトポロジは、動的である。
【０００４】
メッシュネットワークを形成するノードは、高い移動性を有してもよい。例えば、無線ノードは、絶えず位置を変更している自動車または別のタイプの動力車両の一部であってもよい。これらのノードは、メッシュネットワーク内で絶えず移動する（位置を変更する）。さらに、ノードがカバレッジエリア内へ移動したり、エリア外へ移動したりするのにしたがって、可動性メッシュネットワークのサイズおよびトポロジは、絶えず変化している。可動性メッシュネットワークのトポロジは、静止メッシュネットワークのトポロジよりもさらに頻繁に変化する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
したがって、非常に動的な可動性環境における無線メッシュネットワークのトポロジを定義するプロトコルの必要性が当該技術分野には存在する。
【課題を解決するための手段】
【０００６】
動的な道路（可動性）環境においてローカルピアグループ（LPG）ネットワークのサイ
ズを決定するための方法およびシステムが提供される。一実施形態において、方法には、第１のノードと第２のノードとの間の往復時間を測定することと、測定された往復時間を利用して、ローカルピアグループネットワークのサイズをルックアップテーブルから選択することと、が含まれる。別の実施形態において、方法には、往復時間がハートビート信号の時間間隔を超過する場合を決定することと、往復時間がハートビート信号の時間間隔を超過する場合に、ローカルピアグループネットワークのサイズを調整することと、が含まれる。
【０００７】
一実施形態において、システムには、第１のノードと第２のノードとの間の往復時間を測定し、かつ測定された往復時間を利用してローカルピアグループネットワークのサイズをルックアップテーブルから選択するように動作可能なプロセッサが含まれる。別の実施
形態において、プロセッサは、往復時間がハートビート信号の時間間隔を超過する場合を決定し、かつ往復時間がハートビート信号の時間間隔を超過する場合に、ローカルピアグループネットワークのサイズを調整するようにさらに動作可能である。
【０００８】
方法を具体化するコンピュータ可読媒体もまた開示される。
【図面の簡単な説明】
【０００９】
【図１】ローカルピアグループ（LPG）ネットワークの例である。
【図２】本発明の一実施形態によるTRモデルである。
【図３】LPGサイズを制御するための、測定された往復時間エントリを含むルックアップテーブルの例である。
【図４】LPGサイズを制御するための、測定された往復時間エントリおよび推定往復時間エントリを含むルックアップテーブルの例である。
【図５】LPGサイズを制御するためのルックアップテーブルの例である。
【図６】LPGサイズを１だけ低減するための方法の流れ図である。
【図７】LPGサイズを低減するための代替方法の流れ図である。
【図８】本発明から利益を得ることができるコンピューティング環境である。
【発明を実施するための形態】
【００１０】
非常に動的な道路（可動性）環境におけるローカルピアグループ（LPG）ネットワーク
の最適なサイズを決定するための方法およびシステムが提供される。動的な道路（可動性）環境は、街路およびハイウェイに沿った自動車の絶え間ない流れ、および自動車による移動方向を指す。LPGネットワークは、ネットワーク内における自動車間に無線通信を提
供する可動性メッシュネットワークを指す。ネットワーク内の自動車はまた、「ノード」として知られ、コンピュータネットワーク内のノードと同じ方法で機能する。本発明は、LPGネットワーク内のノードとして機能する無線送受信機を備えた自動車の文脈内で開示
される。しかしながら、本発明および一般概念が、どんなコンピュータネットワークも利することが可能であると理解される。
【００１１】
図1は、LPGネットワークにおけるトポロジの例である。トポロジは、互いにリンクされる無線送受信機をそれぞれが有するいくつかの自動車（ノード）を含んでLPGネットワー
クを形成する。無線送受信機は、各自動車内のより大きなコンピュータシステムの一部であってもよい。このコンピュータシステムは、時には「ダッシュボードコンピュータ」として知られている。ダッシュボードコンピュータは、メモリおよびプロセッサを含み、メモリ内に記憶されたソフトウェアによって指示されるような特定の機能を実行する。無線送受信機は、802.11準拠の送受信機であってもよく、自動車およびそれらのそれぞれのダッシュボードコンピュータが互いに通信できるようにする。
【００１２】
トポロジ内の1台の自動車102が、GH（「グループヘッダ」）とラベル付けされる。グループヘッダは、トポロジ内の「ヘッドノード」であり、他の全ての自動車（ノード）の位置が測定される起点となる出発点である。自動車114および116は、自動車（GH）102の1ホップ前方である。自動車104および106は、自動車（GH）102の1ホップ後方である。自動車108および110は、自動車（GH）102の2ホップ後方である。自動車112は、自動車（GH）102の3ホップ後方である。ホップは、グループヘッダ102に達するために必要とされるノード間の接続数として定義される。グループヘッダへの2つ以上の可能な経路が存在する場合
に、最小ホップカウントが、ノード間の相対的関係を定義するために用いられる。例えば、自動車106は、GH102と直接通信してもよく、または自動車106は、自動車104を介してGH102と通信してもよい。自動車106がGH102と直接通信する場合に、これらの2台の自動車間のホップカウントは、1である。自動車106が、自動車104を介してGH102と間接的に通信する場合に、これらの2台の自動車間のホップカウントは、2である。GH102に、1つまたは複
数の可能なホップカウントを有する自動車、例えば自動車106を提示された場合に、GH102は、最低ホップカウントに従って、その自動車の相対的位置を定義する。したがって、GH102と自動車106との間の相対的位置は、1のホップカウントによって定義される。
【００１３】
図2は、本発明の一実施形態によるTRモデルである。TRは、ノードが、GH102からのハートビートメッセージに応答するために必要な合計報告時間（total reporting time）である。THは、個々の自動車が、GH102からのハートビート（HB）メッセージを受信するため
に必要な時間量である。TMは、個々の自動車が、メッセージ応答（MR）をGH102に送信す
るために必要な時間量である。TRは、TH+TMに等しい。TRは、各自動車に特有である。一
般に、自動車とGH102との間のホップ数が増加するにつれて、TRの時間値もまた増加する
。
【００１４】
TRはまた、式1に従って次のように推定してもよい。
【数１】
上記の式において、hは、ホップカウントであり、Nは、ノード（自動車）数であり、d
は、ハートビート送信期間であり、d'は、メッセージ応答送信期間であり、pは、エラー
確率である。LHは、ホップごとの平均HB順方向待ち時間、すなわちHBメッセージが1ホッ
プ移動するための平均待ち時間である。無線チャンネルを用いるためのランダムなアクセス競合ゆえに、HBメッセージは、各ホップにおいて転送されるためのランダムな待ち時間を経験するが）、それは、式2によって与えられる。
【数２】
【００１５】
ハートビートは、GH102により生成される周期信号であり、他の自動車に送信（ブロー
ドキャスト）されて、これらの自動車がまだLPG内に存在するかどうかを決定するための
ものである。GH102は、一定間隔でハートビート信号を送信する。ハートビート信号を受
信した各自動車は、LPG全体を通してハートビート信号を再ブロードキャストする。例え
ば、図２に示すように、GH102は、ハートビート信号を自動車104にブロードキャストする。次に、自動車104は、ハートビート信号を自動車106に再ブロードキャストする。自動車は、GH102によってブロードキャストされるハートビート信号の範囲を超えて移動（ドラ
イブ）することや運転者が自動車のエンジンを切る（これはまた、ハートビート信号を受信する送受信機を切ることになる）ことによって、LPGから自動車自体を除く場合がある
。自動車は、GH102に対するそれらの相対的位置（ホップカウント）に基づいて、LPGに追加または除去され得る。GH102からハートビートメッセージを受信すると、自動車は、ハ
ートビートメッセージを確認したというメッセージでGH102に応答する。肯定応答（acknowledgement）は、応答する自動車がハートビート信号を受信したことをGH102に示す。
【００１６】
ハートビート信号は、「ホップカウント」フィールドを含むデータパケットである。ハ
ートビート信号が再送信されるたびに、ホップカウントフィールドは、1だけ増加される
。ハートビート信号の頻度が狭すぎる場合には、LPGサイズが頻繁に更新されすぎるので
、ハートビート信号に関連するオーバーヘッドは、限界値を超過する。したがって、システム資源を利用し過ぎない効率的な形で、ハートビート頻度およびLPGサイズを選択する
方法の必要性が存在する。
【００１７】
図3および4は、「ルックアップテーブル」をどのように作成できるかを共に示す。ルックアップテーブルを用いて、適切なLPGサイズを選択することができる。図3および図4に
示すルックアップテーブル内の各時間エントリは、秒単位で与えられている。図3は、以
下で示すように、観察された（測定された）メッセージ応答から作成された不完全なルックアップテーブルである。図4は、図3に基づいた推定ルックアップテーブルである。図4
内における欠落したルックアップテーブル時間エントリは、図3のルックアップテーブル
における測定された時間エントリを利用する「最小二乗」近似によって計算される。未知の値を計算するために「最小二乗」近似を使用することは、当該技術分野において周知であるが、しかし例示的な要約が、http://ceee.rice.edu/Books/LA/leastsq/index.htmlで見つけられよう。
【００１８】
ルックアップテーブル400内の推定時間エントリを用いて、適切なLPGサイズを選択することができる。一実施形態において、ルックアップテーブル400は、GH102内のシミュレータによって作成される。次の例は、QUALNET（商標）3.8シミュレータを用いて、ルックアップテーブル400を作成する。GH102は、1000ミリ秒（1秒）ごとにハートビート信号をブ
ロードキャストする。ハートビート信号は、約100メートルの予想範囲において６Mbpsの
データ速度で、802.11a規格に準拠してブロードキャストされる。自動車、例えば自動車104が、ブロードキャストから300ミリ秒内でハートビート信号を受信し、ノード識別子お
よびホップカウントを含むメッセージ応答（MR）で応答すると仮定される。通信チャネルが利用不能かまたはブロックされているために、自動車104が、GH102と通信できない場合があり得る。これらの場合に、自動車104は、バックオフ期間として10ミリ秒待ち、次に
、MRをGH102に通信しようと試みる。
【００１９】
ひとたびMRが、自動車104からGH102に通信されると、往復時間TRが、上記のように計算され、ルックアップテーブル400に格納するために用いられる。例えば、GH102は、ハートビート信号を自動車104にブロードキャストし、自動車104は、肯定応答、すなわちメッセージ応答をGH102に送信する。さらに、この例のために、自動車104が、GH102から1ホップ離れており、かつ往復時間が0.014秒であると仮定する。また、第2の自動車108が、GH102から2ホップ離れており、0.021秒の往復時間でメッセージ応答を返すと仮定する。第3の
自動車106は、1ホップだけ離れているが、しかし0.024秒の往復時間でメッセージ応答を
返す。これらの往復時間は、ルックアップテーブル300に格納するために用いられる。各
往復時間は、ルックアップテーブル300に加えられ、該当するホップ数に関連付けられる
。ホップ数が１から１０まで増加するにつれて、往復時間もまた増加する。同じホップ数によってGH102に接続される他の車両が異なる往復時間を有してもよい。例えば、自動車104および106は、両方ともGH102から１ホップ離れているが、しかし自動車104に関連する
往復時間は、自動車106に関連する往復時間より短い。ホップカウントに関連する往復時
間は、ルックアップテーブル300を横切って左から右へと、最小値から最大値まで増加す
る。
【００２０】
各欠落したテーブルエントリの推定値は、「最小二乗」近似法を利用して、ルックアップテーブル300における測定値から計算される。近似を使用することによって、ルックア
ップテーブル400における各エントリを完成することが可能になる。次に、ルックアップ
テーブル400を用いて、適切なLPGサイズを選択してもよい。
【００２１】
一実施形態において、LPGサイズは、100ミリ秒（0.1秒）の最大TR値に基づいて選択さ
れる。TR値は、自動車104とGH102との間で伝達されるデータが、「新鮮」で適切であることを保証する。新鮮さは、動的道路環境において重要である。なぜなら、GH102が、最新
のデータだけを利用することが望ましいからである。適切なLPGサイズは、0.1秒未満の時間値に関連付けられた、かつまた最大ホップカウント数によって制限されたLPGサイズを
選択することによって、ルックアップテーブル400から選択される。例えば、最大ホップ
カウント数が５に設定された場合に、選択されるLPGサイズは、４０である。４０が選択
されたLPGサイズであるのは、それが、0.1を超過しない最大値、すなわち0.097および最
大ホップカウント数を備えた、ルックアップテーブル400におけるエントリに対応するか
らである。自動車104がGH102から５ホップカウント内にあり、かつLPG内に40台以下の自
動車が存在する限り、自動車104とGH102との間で伝達されるデータは、0.1秒未満で受信
される。
【００２２】
ルックアップテーブル400から最適なLPGサイズを選択することの重要な利益は、LPGサ
イズを数学的に計算することに関連する計算オーバーヘッドの低減である。追加的な利益は、THがTRより大きいことを保証するLPGサイズを選択することから来る。すなわち、TR
がTHより大きい場合に、MRが受信される前に第2のハートビート信号がGH102によって送信される。第1のハートビート信号への応答として受信されるが、第2のハートビート信号が送信された後で受信されるMRは、無関係または不正確な情報をGH102に供給する可能性が
ある。したがって、GH102で受信されるMRが、その特定のハートビートサイクル中に送信
されたハートビート信号に応じていることが重要である。
【００２３】
一実施形態において、最適なLPGサイズは、閾値未満の最大の往復時間値に常に関連付
けられる。GH102が、動的道路環境を通って移動するにつれて、LPGのトポロジは、自動車がGH102との通信範囲内に入ったり出たりするにしたがって、絶えず変化する可能性があ
る。トポロジが頻繁に変化する場合に、ハートビート信号の頻度は増加される。すなわち、ハートビート信号間の時間間隔は、LPGの新鮮さを維持するために短縮される。トポロ
ジが変化しない場合、例えば、GH102および周囲の自動車が、赤信号で停止しているか、
または交通渋滞で立ち往生している場合には、ハートビート信号の頻度は低減される。すなわち、ハートビート信号間の時間間隔は延ばされる。
【００２４】
図5,6および7は、最適なLPGサイズを決定するための方法を集合的に開示する。図5は、最適なLPGサイズを決定するための方法の流れ図である。図6は、図5で示す方法によって
利用される適切なホップカウント値を決定するための方法の流れ図である。図7は、図5で示す方法によって利用される適切なホップカウント値を決定するための代替方法である。
【００２５】
方法は、往復時間の値が計算された場合に決定ステップ501で開始する。一実施形態に
おいて、往復時間は、式１に従って上記のように計算される。決定ステップ502において
、往復時間がハートビート時間間隔を超過するかどうかに関して決定がなされる。往復時間が、ハートビート間隔を超過しない場合に、方法はステップ508に進む。LPGネットワークの現在のサイズと同様に現在のホップカウント値が知られており、自動車ではダッシュボードコンピュータ内に記憶されている。ステップ508において、最大ホップカウント値
が、1だけ増加される。往復時間がハートビート間隔を超過する場合に、方法はステップ504に進む。
【００２６】
ステップ504において、ホップカウント値は、3つの方法の1つによって評価および低減
される。ステップ504でホップカウントを評価するために使用できる3つの方法の2つが、
図6および図7に示されている。第3の実施形態(図示せず)において、方法は、図4に示すものなどのルックアップテーブルを利用し、上記のように往復時間に基づいて適切なホップカウント値を選択する。
【００２７】
第1の実施形態において、ホップカウント値は、1の値だけ低減される。ステップ504で
行われるプロセスの拡大図である図6を参照すると、ステップ602において、ホップカウント値に関連するダウンサイジング要求が、ダッシュボードコンピュータによって受信される。決定ステップ604において、ホップカウント値が1に等しいかどうかに関して決定がなされる。ホップカウント値が1に等しい場合に、最小のホップカウント値に既に達してお
り、方法は終了する。ホップカウント値が1より大きい場合に、方法はステップ606に進む。ステップ606において、ホップカウント値は1だけ低減される。図5および6で一緒に示す方法は、適切なホップカウント値が選択されたかどうかを決定するために繰り返してもよい。
【００２８】
別の実施形態において、ホップカウント値は、新しいホップカウント値を決定するために、ある数で因数分解、すなわち除算される。ステップ504で行われるプロセスの拡大図
である図7を参照すると、ステップ702において、ホップカウント値に関連するダウンサイジング要求が、ダッシュボードコンピュータによって受信される。一実施形態において、ホップカウント値は、現在のホップカウント値と、ゼロなどの下限値との間の中間値として計算される。ステップ704において、下限値が、変数Lに記憶される。一実施形態において、下限値は、0に設定される。上限値、すなわち現在のホップカウント値（h）は、変数Rに記憶される。現在のホップカウント値（h）は、因数、例えば2で除算され、算出値は
、変数xに記憶される。例えば、現在のホップカウント値が10であり、因数値が2である場合に、10は2で除算され、5の値を算出する。値5は、変数xに記憶される。ステップ706に
おいて、往復時間は、変数xに記憶されたホップカウント値に基づいて再計算される。ス
テップ706で計算された往復時間は、ホップカウント値が低減されたので、ステップ501で計算された往復時間より短いはずである。
【００２９】
決定ステップ708において、往復時間が、閾値すなわちハートビート間隔より短いかど
うかに関して決定がなされる。往復時間が閾値より小さくない場合に、方法はステップ710に進む。ステップ710において、変数xに記憶された現在のホップカウント値はまた、変
数yに記憶される。xに記憶されたホップカウント値はまた、新しい上限値として変数Rに
再記憶される。次に、変数xに記憶されたホップカウント値は、再び因数分解される。一
実施形態において、新しいホップカウント値が、下限と上限との間の新しい中間値を提供する式x=[(R-L)/2]によって計算される。次に、方法は決定ステップ714に進み、そこでL<x<Rかどうかに関して決定がなされる。L<x<Rが真である場合に、方法はステップ716に進
み、ホップカウント値は、変数xに記憶された値に設定される。L<x<Rが偽である場合に、方法は、ステップ706にループバックする。
【００３０】
次の例は、図7に示す方法によって、10のホップカウント値を3のホップカウント値にどのように再設定可能かを示す。変数hに記憶されたホップカウント値はまた、変数Rに記憶される。Rは上限である。下限は、ゼロに設定され、変数Lに記憶される。新しいホップカウント値は、式x=[(R-L)/2]に従って、上限と下限との間の中間点の値として計算される
。現在の変数の値を代入した後で、式は、x=[(10-0)/2]=5として書き直してもよい。新しい往復時間は、5の最大ホップカウント値に基づいて計算される。しかしながら、この例
において、5のホップカウント値は、閾値すなわちハートビート時間間隔を超過する往復
時間に帰着する。現在のホップカウント値5は、再び因数分解される。現在のホップカウ
ント値5は、新しい上限になり、Lは、やはり下限である。上限と下限との間の新しい中間点が再計算される。現在の例において、上限（R）と下限（L）との間の中間点は、式x=[(R-L)/2]に従って計算される。現在の変数の値を代入した後で、式は、x=[(5-0)/2]=2.5として書き直してもよい。一実施形態において、非整数がホップカウントの値として計算された場合に、数は切り上げられる。したがって、2.5は、3に切り上げられる。次に、計算されたホップカウント値、例えば3が、下限および上限の範囲内であるかどうかに関して
決定がなされる。現在の例において、ホップカウント値3は、0の下限値より大きく、5の
上限値より小さい。新しいホップカウント値は、3に設定され、新しい往復時間を計算す
るために用いられる。
【００３１】
再び決定ステップ708を参照すると、往復時間が閾値より短い場合に、方法は、ステッ
プ712に進む。ステップ712において、変数x内の値は、最初に変数yに記憶される。変数x
が、元のホップカウント値の上限と下限との間における計算された中間値を記憶することを想起されたい。次に、変数xに記憶された値は、変数Lに記憶される。最後に、変数xの
値は、式x=L+[(R-L)/2]に従って再計算される。例として、ステップ704において、Lが0に等しく設定され、hが10に等しく設定され、Rがhに等しく設定され、ｘが、式x=[(R-L)/2]に従って計算されて、5に等しい値を有しているのが分かると仮定する。ステップ712において、y=5, L=5およびxが、x=L+[(R-L)/2]に従って再計算される。変数のそれぞれに対して周知の値を代入することによって、式x=5+[(10-5)/2］が提供され、この式は、結果x=7.5をもたらす。
【００３２】
次に、方法は、ステップ714に進む。再び、ステップ712からの例において計算された結果を用いて、L<x<Rが真であるかどうかに関して決定がなされる。ステップ712からL、xおよびR用の値を代入すると、真の結果、すなわちxを結果としてもたらす5<7.5<10は、下限と上限との間に位置する。一実施形態において、ホップカウント値は、7.5から8に切り上げられる。なぜなら、ホップカウント値は、整数でなければならないからである。次に、方法は、ステップ706にループバックし、往復時間は、xの値に基づいて計算される。
【００３３】
図8は、本発明から利益を得ることができるコンピューティング環境の例である。一実
施形態において、コンピューティング環境には、別の自動車104と無線で通信するGH102が含まれる。GH102および自動車104は、LPGネットワークを集合的に形成する。GH102内のダッシュボードコンピュータ802が、LPGネットワークのサイズ、およびGH102と自動車104との間の通信を制御する。自動車104が、GH102から受信される通信を受信し、かつそれらに応答できる類似のダッシュボードコンピュータ（図示せず）を有していると理解される。
【００３４】
ダッシュボードコンピュータ802には、プロセッサ（CPU）804、送受信機806、およびメモリ808が含まれる。コンピュータ802は、送受信機806およびメモリ808に結合され、かつ「HBサイクル制御」814および「認識コンポーネント」810など、メモリに記憶されたプログラムを実行する。送受信機806によって、GH102と自動車104との間の無線（RF）通信が
可能になる。一実施形態において、GH102は、802.11a規格を介して自動車104と通信する
。本発明が、任意の無線通信規格を使用可能であると理解される。電源、アンテナ、記憶装置および様々な支援回路など、ダッシュボードコンピュータ802内に通常見い出される
他のコンポーネントが存在するが図8には示されていないと理解される。
【００３５】
メモリ808には、ランダムアクセスメモリ、読み出し専用メモリ、リムーバブルディス
クメモリ、フラッシュメモリ、およびこれらのタイプのメモリの様々な組み合わせを含んでもよい。メモリ808は、時にはメインメモリと呼ばれ、キャッシュメモリとして部分的
に用いてもよい。メモリ808は、少なくとも「認識コンポーネント」810、LPGルックアッ
プテーブル812、および「HBサイクル制御」814を記憶する。認識コンポーネント810は、LPGネットワークのサイズを記憶し、かつLPGネットワーク内の全ての車両または自動車の
リストを維持する。認識コンポーネント810はまた、LPGネットワーク内の各自動車に関連する情報を維持してもよい。LPGルックアップテーブル814の例が、図4に提供されている
。LPGルックアップテーブル814によって、往復時間に基づいた最適なLPGネットワークサ
イズの選択が可能になる。
【００３６】
「HBサイクル制御」814は、GH102と自動車104との間の最大許容可能ホップカウント値
を制御する。「HBサイクル制御」814の機能は、図5,6および7に関連して上記で説明して
いる。一実施形態において、「HBサイクル制御」814は、往復時間がハートビート時間間
隔より短い場合に、ホップカウント値を増加する。別の実施形態において、「HBサイクル制御」814は、往復時間がハートビート時間間隔より長い場合に、ホップカウント値を低
減する。ホップカウント値を低減するための特定の方法が、図6および7に関連して説明されている。「HBサイクル制御」814はまた、図4に示すものなどのルックアップテーブルを利用することによって、最適なLPGネットワークサイズを選択してもよい。
【００３７】
本発明を、その好ましい実施形態に関連して特に図示し説明したが、形態および詳細における前述および他の変更が、本発明の趣旨および範囲から逸脱せずになし得ることを、当業者は理解されよう。したがって、本発明は、説明し図示した形態および詳細に正確には限定されず、添付の特許請求の範囲内に入るように意図されている。
【技術分野】
【０００１】
本発明は、一般に無線メッシュネットワークに関し、特に動的道路環境におけるメッシュネットワーク用の適合プロトコル（adaptation protocol）に関する。
【背景技術】
【０００２】
無線メッシュネットワークは、メッシュトポロジに組織された無線ノードで構成された通信ネットワークである。完全なメッシュトポロジにおいて、各ノードは、他のノードのそれぞれに直接接続される。部分的なメッシュトポロジにおいて、ノードは、他のノードの全てではなく、いくつかだけに接続される。単一ネットワークとして一緒に動作する無線ノードのカバレッジエリアは、時にはメッシュクラウドとして知られている。無線メッシュネットワークは、802.11, 802.16およびセルラー技術を含む様々な無線規格を介して実現することができる。
【０００３】
メッシュネットワークは、ノード間の多対多接続という利点を提供する。すなわち、通常、ノード間で情報を通信するための2つ以上の可能なルートが存在する。メッシュネッ
トワークはまた、これらの接続を動的に更新および最適化することができる。新しいノードが利用可能になると、それらは、メッシュネットワークに追加してもよい。ノードはまた、メッシュネットワークから除去してもよい。したがって、メッシュネットワークのトポロジは、動的である。
【０００４】
メッシュネットワークを形成するノードは、高い移動性を有してもよい。例えば、無線ノードは、絶えず位置を変更している自動車または別のタイプの動力車両の一部であってもよい。これらのノードは、メッシュネットワーク内で絶えず移動する（位置を変更する）。さらに、ノードがカバレッジエリア内へ移動したり、エリア外へ移動したりするのにしたがって、可動性メッシュネットワークのサイズおよびトポロジは、絶えず変化している。可動性メッシュネットワークのトポロジは、静止メッシュネットワークのトポロジよりもさらに頻繁に変化する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
したがって、非常に動的な可動性環境における無線メッシュネットワークのトポロジを定義するプロトコルの必要性が当該技術分野には存在する。
【課題を解決するための手段】
【０００６】
動的な道路（可動性）環境においてローカルピアグループ（LPG）ネットワークのサイ
ズを決定するための方法およびシステムが提供される。一実施形態において、方法には、第１のノードと第２のノードとの間の往復時間を測定することと、測定された往復時間を利用して、ローカルピアグループネットワークのサイズをルックアップテーブルから選択することと、が含まれる。別の実施形態において、方法には、往復時間がハートビート信号の時間間隔を超過する場合を決定することと、往復時間がハートビート信号の時間間隔を超過する場合に、ローカルピアグループネットワークのサイズを調整することと、が含まれる。
【０００７】
一実施形態において、システムには、第１のノードと第２のノードとの間の往復時間を測定し、かつ測定された往復時間を利用してローカルピアグループネットワークのサイズをルックアップテーブルから選択するように動作可能なプロセッサが含まれる。別の実施
形態において、プロセッサは、往復時間がハートビート信号の時間間隔を超過する場合を決定し、かつ往復時間がハートビート信号の時間間隔を超過する場合に、ローカルピアグループネットワークのサイズを調整するようにさらに動作可能である。
【０００８】
方法を具体化するコンピュータ可読媒体もまた開示される。
【図面の簡単な説明】
【０００９】
【図１】ローカルピアグループ（LPG）ネットワークの例である。
【図２】本発明の一実施形態によるTRモデルである。
【図３】LPGサイズを制御するための、測定された往復時間エントリを含むルックアップテーブルの例である。
【図４】LPGサイズを制御するための、測定された往復時間エントリおよび推定往復時間エントリを含むルックアップテーブルの例である。
【図５】LPGサイズを制御するためのルックアップテーブルの例である。
【図６】LPGサイズを１だけ低減するための方法の流れ図である。
【図７】LPGサイズを低減するための代替方法の流れ図である。
【図８】本発明から利益を得ることができるコンピューティング環境である。
【発明を実施するための形態】
【００１０】
非常に動的な道路（可動性）環境におけるローカルピアグループ（LPG）ネットワーク
の最適なサイズを決定するための方法およびシステムが提供される。動的な道路（可動性）環境は、街路およびハイウェイに沿った自動車の絶え間ない流れ、および自動車による移動方向を指す。LPGネットワークは、ネットワーク内における自動車間に無線通信を提
供する可動性メッシュネットワークを指す。ネットワーク内の自動車はまた、「ノード」として知られ、コンピュータネットワーク内のノードと同じ方法で機能する。本発明は、LPGネットワーク内のノードとして機能する無線送受信機を備えた自動車の文脈内で開示
される。しかしながら、本発明および一般概念が、どんなコンピュータネットワークも利することが可能であると理解される。
【００１１】
図1は、LPGネットワークにおけるトポロジの例である。トポロジは、互いにリンクされる無線送受信機をそれぞれが有するいくつかの自動車（ノード）を含んでLPGネットワー
クを形成する。無線送受信機は、各自動車内のより大きなコンピュータシステムの一部であってもよい。このコンピュータシステムは、時には「ダッシュボードコンピュータ」として知られている。ダッシュボードコンピュータは、メモリおよびプロセッサを含み、メモリ内に記憶されたソフトウェアによって指示されるような特定の機能を実行する。無線送受信機は、802.11準拠の送受信機であってもよく、自動車およびそれらのそれぞれのダッシュボードコンピュータが互いに通信できるようにする。
【００１２】
トポロジ内の1台の自動車102が、GH（「グループヘッダ」）とラベル付けされる。グループヘッダは、トポロジ内の「ヘッドノード」であり、他の全ての自動車（ノード）の位置が測定される起点となる出発点である。自動車114および116は、自動車（GH）102の1ホップ前方である。自動車104および106は、自動車（GH）102の1ホップ後方である。自動車108および110は、自動車（GH）102の2ホップ後方である。自動車112は、自動車（GH）102の3ホップ後方である。ホップは、グループヘッダ102に達するために必要とされるノード間の接続数として定義される。グループヘッダへの2つ以上の可能な経路が存在する場合
に、最小ホップカウントが、ノード間の相対的関係を定義するために用いられる。例えば、自動車106は、GH102と直接通信してもよく、または自動車106は、自動車104を介してGH102と通信してもよい。自動車106がGH102と直接通信する場合に、これらの2台の自動車間のホップカウントは、1である。自動車106が、自動車104を介してGH102と間接的に通信する場合に、これらの2台の自動車間のホップカウントは、2である。GH102に、1つまたは複
数の可能なホップカウントを有する自動車、例えば自動車106を提示された場合に、GH102は、最低ホップカウントに従って、その自動車の相対的位置を定義する。したがって、GH102と自動車106との間の相対的位置は、1のホップカウントによって定義される。
【００１３】
図2は、本発明の一実施形態によるTRモデルである。TRは、ノードが、GH102からのハートビートメッセージに応答するために必要な合計報告時間（total reporting time）である。THは、個々の自動車が、GH102からのハートビート（HB）メッセージを受信するため
に必要な時間量である。TMは、個々の自動車が、メッセージ応答（MR）をGH102に送信す
るために必要な時間量である。TRは、TH+TMに等しい。TRは、各自動車に特有である。一
般に、自動車とGH102との間のホップ数が増加するにつれて、TRの時間値もまた増加する
。
【００１４】
TRはまた、式1に従って次のように推定してもよい。
【数１】
上記の式において、hは、ホップカウントであり、Nは、ノード（自動車）数であり、d
は、ハートビート送信期間であり、d'は、メッセージ応答送信期間であり、pは、エラー
確率である。LHは、ホップごとの平均HB順方向待ち時間、すなわちHBメッセージが1ホッ
プ移動するための平均待ち時間である。無線チャンネルを用いるためのランダムなアクセス競合ゆえに、HBメッセージは、各ホップにおいて転送されるためのランダムな待ち時間を経験するが）、それは、式2によって与えられる。
【数２】
【００１５】
ハートビートは、GH102により生成される周期信号であり、他の自動車に送信（ブロー
ドキャスト）されて、これらの自動車がまだLPG内に存在するかどうかを決定するための
ものである。GH102は、一定間隔でハートビート信号を送信する。ハートビート信号を受
信した各自動車は、LPG全体を通してハートビート信号を再ブロードキャストする。例え
ば、図２に示すように、GH102は、ハートビート信号を自動車104にブロードキャストする。次に、自動車104は、ハートビート信号を自動車106に再ブロードキャストする。自動車は、GH102によってブロードキャストされるハートビート信号の範囲を超えて移動（ドラ
イブ）することや運転者が自動車のエンジンを切る（これはまた、ハートビート信号を受信する送受信機を切ることになる）ことによって、LPGから自動車自体を除く場合がある
。自動車は、GH102に対するそれらの相対的位置（ホップカウント）に基づいて、LPGに追加または除去され得る。GH102からハートビートメッセージを受信すると、自動車は、ハ
ートビートメッセージを確認したというメッセージでGH102に応答する。肯定応答（acknowledgement）は、応答する自動車がハートビート信号を受信したことをGH102に示す。
【００１６】
ハートビート信号は、「ホップカウント」フィールドを含むデータパケットである。ハ
ートビート信号が再送信されるたびに、ホップカウントフィールドは、1だけ増加される
。ハートビート信号の頻度が狭すぎる場合には、LPGサイズが頻繁に更新されすぎるので
、ハートビート信号に関連するオーバーヘッドは、限界値を超過する。したがって、システム資源を利用し過ぎない効率的な形で、ハートビート頻度およびLPGサイズを選択する
方法の必要性が存在する。
【００１７】
図3および4は、「ルックアップテーブル」をどのように作成できるかを共に示す。ルックアップテーブルを用いて、適切なLPGサイズを選択することができる。図3および図4に
示すルックアップテーブル内の各時間エントリは、秒単位で与えられている。図3は、以
下で示すように、観察された（測定された）メッセージ応答から作成された不完全なルックアップテーブルである。図4は、図3に基づいた推定ルックアップテーブルである。図4
内における欠落したルックアップテーブル時間エントリは、図3のルックアップテーブル
における測定された時間エントリを利用する「最小二乗」近似によって計算される。未知の値を計算するために「最小二乗」近似を使用することは、当該技術分野において周知であるが、しかし例示的な要約が、http://ceee.rice.edu/Books/LA/leastsq/index.htmlで見つけられよう。
【００１８】
ルックアップテーブル400内の推定時間エントリを用いて、適切なLPGサイズを選択することができる。一実施形態において、ルックアップテーブル400は、GH102内のシミュレータによって作成される。次の例は、QUALNET（商標）3.8シミュレータを用いて、ルックアップテーブル400を作成する。GH102は、1000ミリ秒（1秒）ごとにハートビート信号をブ
ロードキャストする。ハートビート信号は、約100メートルの予想範囲において６Mbpsの
データ速度で、802.11a規格に準拠してブロードキャストされる。自動車、例えば自動車104が、ブロードキャストから300ミリ秒内でハートビート信号を受信し、ノード識別子お
よびホップカウントを含むメッセージ応答（MR）で応答すると仮定される。通信チャネルが利用不能かまたはブロックされているために、自動車104が、GH102と通信できない場合があり得る。これらの場合に、自動車104は、バックオフ期間として10ミリ秒待ち、次に
、MRをGH102に通信しようと試みる。
【００１９】
ひとたびMRが、自動車104からGH102に通信されると、往復時間TRが、上記のように計算され、ルックアップテーブル400に格納するために用いられる。例えば、GH102は、ハートビート信号を自動車104にブロードキャストし、自動車104は、肯定応答、すなわちメッセージ応答をGH102に送信する。さらに、この例のために、自動車104が、GH102から1ホップ離れており、かつ往復時間が0.014秒であると仮定する。また、第2の自動車108が、GH102から2ホップ離れており、0.021秒の往復時間でメッセージ応答を返すと仮定する。第3の
自動車106は、1ホップだけ離れているが、しかし0.024秒の往復時間でメッセージ応答を
返す。これらの往復時間は、ルックアップテーブル300に格納するために用いられる。各
往復時間は、ルックアップテーブル300に加えられ、該当するホップ数に関連付けられる
。ホップ数が１から１０まで増加するにつれて、往復時間もまた増加する。同じホップ数によってGH102に接続される他の車両が異なる往復時間を有してもよい。例えば、自動車104および106は、両方ともGH102から１ホップ離れているが、しかし自動車104に関連する
往復時間は、自動車106に関連する往復時間より短い。ホップカウントに関連する往復時
間は、ルックアップテーブル300を横切って左から右へと、最小値から最大値まで増加す
る。
【００２０】
各欠落したテーブルエントリの推定値は、「最小二乗」近似法を利用して、ルックアップテーブル300における測定値から計算される。近似を使用することによって、ルックア
ップテーブル400における各エントリを完成することが可能になる。次に、ルックアップ
テーブル400を用いて、適切なLPGサイズを選択してもよい。
【００２１】
一実施形態において、LPGサイズは、100ミリ秒（0.1秒）の最大TR値に基づいて選択さ
れる。TR値は、自動車104とGH102との間で伝達されるデータが、「新鮮」で適切であることを保証する。新鮮さは、動的道路環境において重要である。なぜなら、GH102が、最新
のデータだけを利用することが望ましいからである。適切なLPGサイズは、0.1秒未満の時間値に関連付けられた、かつまた最大ホップカウント数によって制限されたLPGサイズを
選択することによって、ルックアップテーブル400から選択される。例えば、最大ホップ
カウント数が５に設定された場合に、選択されるLPGサイズは、４０である。４０が選択
されたLPGサイズであるのは、それが、0.1を超過しない最大値、すなわち0.097および最
大ホップカウント数を備えた、ルックアップテーブル400におけるエントリに対応するか
らである。自動車104がGH102から５ホップカウント内にあり、かつLPG内に40台以下の自
動車が存在する限り、自動車104とGH102との間で伝達されるデータは、0.1秒未満で受信
される。
【００２２】
ルックアップテーブル400から最適なLPGサイズを選択することの重要な利益は、LPGサ
イズを数学的に計算することに関連する計算オーバーヘッドの低減である。追加的な利益は、THがTRより大きいことを保証するLPGサイズを選択することから来る。すなわち、TR
がTHより大きい場合に、MRが受信される前に第2のハートビート信号がGH102によって送信される。第1のハートビート信号への応答として受信されるが、第2のハートビート信号が送信された後で受信されるMRは、無関係または不正確な情報をGH102に供給する可能性が
ある。したがって、GH102で受信されるMRが、その特定のハートビートサイクル中に送信
されたハートビート信号に応じていることが重要である。
【００２３】
一実施形態において、最適なLPGサイズは、閾値未満の最大の往復時間値に常に関連付
けられる。GH102が、動的道路環境を通って移動するにつれて、LPGのトポロジは、自動車がGH102との通信範囲内に入ったり出たりするにしたがって、絶えず変化する可能性があ
る。トポロジが頻繁に変化する場合に、ハートビート信号の頻度は増加される。すなわち、ハートビート信号間の時間間隔は、LPGの新鮮さを維持するために短縮される。トポロ
ジが変化しない場合、例えば、GH102および周囲の自動車が、赤信号で停止しているか、
または交通渋滞で立ち往生している場合には、ハートビート信号の頻度は低減される。すなわち、ハートビート信号間の時間間隔は延ばされる。
【００２４】
図5,6および7は、最適なLPGサイズを決定するための方法を集合的に開示する。図5は、最適なLPGサイズを決定するための方法の流れ図である。図6は、図5で示す方法によって
利用される適切なホップカウント値を決定するための方法の流れ図である。図7は、図5で示す方法によって利用される適切なホップカウント値を決定するための代替方法である。
【００２５】
方法は、往復時間の値が計算された場合に決定ステップ501で開始する。一実施形態に
おいて、往復時間は、式１に従って上記のように計算される。決定ステップ502において
、往復時間がハートビート時間間隔を超過するかどうかに関して決定がなされる。往復時間が、ハートビート間隔を超過しない場合に、方法はステップ508に進む。LPGネットワークの現在のサイズと同様に現在のホップカウント値が知られており、自動車ではダッシュボードコンピュータ内に記憶されている。ステップ508において、最大ホップカウント値
が、1だけ増加される。往復時間がハートビート間隔を超過する場合に、方法はステップ504に進む。
【００２６】
ステップ504において、ホップカウント値は、3つの方法の1つによって評価および低減
される。ステップ504でホップカウントを評価するために使用できる3つの方法の2つが、
図6および図7に示されている。第3の実施形態(図示せず)において、方法は、図4に示すものなどのルックアップテーブルを利用し、上記のように往復時間に基づいて適切なホップカウント値を選択する。
【００２７】
第1の実施形態において、ホップカウント値は、1の値だけ低減される。ステップ504で
行われるプロセスの拡大図である図6を参照すると、ステップ602において、ホップカウント値に関連するダウンサイジング要求が、ダッシュボードコンピュータによって受信される。決定ステップ604において、ホップカウント値が1に等しいかどうかに関して決定がなされる。ホップカウント値が1に等しい場合に、最小のホップカウント値に既に達してお
り、方法は終了する。ホップカウント値が1より大きい場合に、方法はステップ606に進む。ステップ606において、ホップカウント値は1だけ低減される。図5および6で一緒に示す方法は、適切なホップカウント値が選択されたかどうかを決定するために繰り返してもよい。
【００２８】
別の実施形態において、ホップカウント値は、新しいホップカウント値を決定するために、ある数で因数分解、すなわち除算される。ステップ504で行われるプロセスの拡大図
である図7を参照すると、ステップ702において、ホップカウント値に関連するダウンサイジング要求が、ダッシュボードコンピュータによって受信される。一実施形態において、ホップカウント値は、現在のホップカウント値と、ゼロなどの下限値との間の中間値として計算される。ステップ704において、下限値が、変数Lに記憶される。一実施形態において、下限値は、0に設定される。上限値、すなわち現在のホップカウント値（h）は、変数Rに記憶される。現在のホップカウント値（h）は、因数、例えば2で除算され、算出値は
、変数xに記憶される。例えば、現在のホップカウント値が10であり、因数値が2である場合に、10は2で除算され、5の値を算出する。値5は、変数xに記憶される。ステップ706に
おいて、往復時間は、変数xに記憶されたホップカウント値に基づいて再計算される。ス
テップ706で計算された往復時間は、ホップカウント値が低減されたので、ステップ501で計算された往復時間より短いはずである。
【００２９】
決定ステップ708において、往復時間が、閾値すなわちハートビート間隔より短いかど
うかに関して決定がなされる。往復時間が閾値より小さくない場合に、方法はステップ710に進む。ステップ710において、変数xに記憶された現在のホップカウント値はまた、変
数yに記憶される。xに記憶されたホップカウント値はまた、新しい上限値として変数Rに
再記憶される。次に、変数xに記憶されたホップカウント値は、再び因数分解される。一
実施形態において、新しいホップカウント値が、下限と上限との間の新しい中間値を提供する式x=[(R-L)/2]によって計算される。次に、方法は決定ステップ714に進み、そこでL<x<Rかどうかに関して決定がなされる。L<x<Rが真である場合に、方法はステップ716に進
み、ホップカウント値は、変数xに記憶された値に設定される。L<x<Rが偽である場合に、方法は、ステップ706にループバックする。
【００３０】
次の例は、図7に示す方法によって、10のホップカウント値を3のホップカウント値にどのように再設定可能かを示す。変数hに記憶されたホップカウント値はまた、変数Rに記憶される。Rは上限である。下限は、ゼロに設定され、変数Lに記憶される。新しいホップカウント値は、式x=[(R-L)/2]に従って、上限と下限との間の中間点の値として計算される
。現在の変数の値を代入した後で、式は、x=[(10-0)/2]=5として書き直してもよい。新しい往復時間は、5の最大ホップカウント値に基づいて計算される。しかしながら、この例
において、5のホップカウント値は、閾値すなわちハートビート時間間隔を超過する往復
時間に帰着する。現在のホップカウント値5は、再び因数分解される。現在のホップカウ
ント値5は、新しい上限になり、Lは、やはり下限である。上限と下限との間の新しい中間点が再計算される。現在の例において、上限（R）と下限（L）との間の中間点は、式x=[(R-L)/2]に従って計算される。現在の変数の値を代入した後で、式は、x=[(5-0)/2]=2.5として書き直してもよい。一実施形態において、非整数がホップカウントの値として計算された場合に、数は切り上げられる。したがって、2.5は、3に切り上げられる。次に、計算されたホップカウント値、例えば3が、下限および上限の範囲内であるかどうかに関して
決定がなされる。現在の例において、ホップカウント値3は、0の下限値より大きく、5の
上限値より小さい。新しいホップカウント値は、3に設定され、新しい往復時間を計算す
るために用いられる。
【００３１】
再び決定ステップ708を参照すると、往復時間が閾値より短い場合に、方法は、ステッ
プ712に進む。ステップ712において、変数x内の値は、最初に変数yに記憶される。変数x
が、元のホップカウント値の上限と下限との間における計算された中間値を記憶することを想起されたい。次に、変数xに記憶された値は、変数Lに記憶される。最後に、変数xの
値は、式x=L+[(R-L)/2]に従って再計算される。例として、ステップ704において、Lが0に等しく設定され、hが10に等しく設定され、Rがhに等しく設定され、ｘが、式x=[(R-L)/2]に従って計算されて、5に等しい値を有しているのが分かると仮定する。ステップ712において、y=5, L=5およびxが、x=L+[(R-L)/2]に従って再計算される。変数のそれぞれに対して周知の値を代入することによって、式x=5+[(10-5)/2］が提供され、この式は、結果x=7.5をもたらす。
【００３２】
次に、方法は、ステップ714に進む。再び、ステップ712からの例において計算された結果を用いて、L<x<Rが真であるかどうかに関して決定がなされる。ステップ712からL、xおよびR用の値を代入すると、真の結果、すなわちxを結果としてもたらす5<7.5<10は、下限と上限との間に位置する。一実施形態において、ホップカウント値は、7.5から8に切り上げられる。なぜなら、ホップカウント値は、整数でなければならないからである。次に、方法は、ステップ706にループバックし、往復時間は、xの値に基づいて計算される。
【００３３】
図8は、本発明から利益を得ることができるコンピューティング環境の例である。一実
施形態において、コンピューティング環境には、別の自動車104と無線で通信するGH102が含まれる。GH102および自動車104は、LPGネットワークを集合的に形成する。GH102内のダッシュボードコンピュータ802が、LPGネットワークのサイズ、およびGH102と自動車104との間の通信を制御する。自動車104が、GH102から受信される通信を受信し、かつそれらに応答できる類似のダッシュボードコンピュータ（図示せず）を有していると理解される。
【００３４】
ダッシュボードコンピュータ802には、プロセッサ（CPU）804、送受信機806、およびメモリ808が含まれる。コンピュータ802は、送受信機806およびメモリ808に結合され、かつ「HBサイクル制御」814および「認識コンポーネント」810など、メモリに記憶されたプログラムを実行する。送受信機806によって、GH102と自動車104との間の無線（RF）通信が
可能になる。一実施形態において、GH102は、802.11a規格を介して自動車104と通信する
。本発明が、任意の無線通信規格を使用可能であると理解される。電源、アンテナ、記憶装置および様々な支援回路など、ダッシュボードコンピュータ802内に通常見い出される
他のコンポーネントが存在するが図8には示されていないと理解される。
【００３５】
メモリ808には、ランダムアクセスメモリ、読み出し専用メモリ、リムーバブルディス
クメモリ、フラッシュメモリ、およびこれらのタイプのメモリの様々な組み合わせを含んでもよい。メモリ808は、時にはメインメモリと呼ばれ、キャッシュメモリとして部分的
に用いてもよい。メモリ808は、少なくとも「認識コンポーネント」810、LPGルックアッ
プテーブル812、および「HBサイクル制御」814を記憶する。認識コンポーネント810は、LPGネットワークのサイズを記憶し、かつLPGネットワーク内の全ての車両または自動車の
リストを維持する。認識コンポーネント810はまた、LPGネットワーク内の各自動車に関連する情報を維持してもよい。LPGルックアップテーブル814の例が、図4に提供されている
。LPGルックアップテーブル814によって、往復時間に基づいた最適なLPGネットワークサ
イズの選択が可能になる。
【００３６】
「HBサイクル制御」814は、GH102と自動車104との間の最大許容可能ホップカウント値
を制御する。「HBサイクル制御」814の機能は、図5,6および7に関連して上記で説明して
いる。一実施形態において、「HBサイクル制御」814は、往復時間がハートビート時間間
隔より短い場合に、ホップカウント値を増加する。別の実施形態において、「HBサイクル制御」814は、往復時間がハートビート時間間隔より長い場合に、ホップカウント値を低
減する。ホップカウント値を低減するための特定の方法が、図6および7に関連して説明されている。「HBサイクル制御」814はまた、図4に示すものなどのルックアップテーブルを利用することによって、最適なLPGネットワークサイズを選択してもよい。
【００３７】
本発明を、その好ましい実施形態に関連して特に図示し説明したが、形態および詳細における前述および他の変更が、本発明の趣旨および範囲から逸脱せずになし得ることを、当業者は理解されよう。したがって、本発明は、説明し図示した形態および詳細に正確には限定されず、添付の特許請求の範囲内に入るように意図されている。
【特許請求の範囲】
【請求項１】
ローカルピアグループネットワークのサイズを決定するためにコンピュータによって実行される方法であって、
第１のノードと第２のノードとの間の往復時間を測定することと、
前記測定された往復時間を利用して、前記ローカルピアグループネットワークの前記サイズをルックアップテーブルから選択することであって、前記コンピュータが、測定および利用の１つまたは複数のステップを実行することと、
を含む方法。
【請求項２】
前記第１のノードから前記第２のノードにハートビート信号を送信することと、
前記第２のノードにおいて前記ハートビート信号を受信することと、
前記ハートビート信号の受信に応答して、前記第２のノードから前記第１のノードにメッセージ応答を送信することであって、前記メッセージ応答が、ノード識別子およびホップカウント値を含むことと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記往復時間を前記ルックアップテーブルに格納することであって、前記往復時間が、前記ルックアップテーブルにおける前記ホップカウント値に関連付けられることと、
前記往復時間から１つまたは複数の追加往復時間を推定することと、
前記１つまたは複数の追加往復時間を用いて前記ルックアップテーブルを完成することと、
をさらに含む、請求項２に記載の方法。
【請求項４】
前記往復時間が、前記ハートビート信号の時間間隔を超過する場合に、前記ローカルピアグループネットワークの前記サイズを調整することをさらに含む、請求項１に記載の方法。
【請求項５】
前記ハートビート信号の前記時間間隔を超過する前記往復時間を利用することによって、前記ローカルピアグループネットワークの新しいサイズを前記ルックアップテーブルから選択することをさらに含む、請求項４に記載の方法。
【請求項６】
前記第１のノードと前記第２のノードとの間の最大許容可能ホップカウント値を低減することと、
前記往復時間が、前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記第１のノードと前記第２のノードとの間の前記最大許容可能ホップカウント値をさらに低減することと、
をさらに含む、請求項４に記載の方法。
【請求項７】
最大許容可能ホップカウント値を因数で除算して、前記第１のノードと前記第２のノードとの間の新しい最大許容可能ホップカウント値を確立することと、
前記往復時間が前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記新しい最大許容可能ホップカウント値を前記因数でさらに除算することと、
をさらに含む、請求項４に記載の方法。
【請求項８】
ローカルピアグループネットワークのサイズを決定するためのコンピュータプログラムプロダクトであって、
第１のノードおよび第２のノードとの間の往復時間を測定することと、
前記測定された往復時間を利用して、前記ローカルピアグループネットワークの前記サイズをルックアップテーブルから選択することであって、前記コンピュータが、測定および利用の１つまたは複数のステップを実行することと、
を含む方法を実行するための、プロセッサによって可読であり、かつ前記プロセッサによる実行のための命令を記憶する記憶媒体を含むコンピュータプログラムプロダクト。
【請求項９】
前記第１のノードから前記第２のノードにハートビート信号を送信することと、
前記第２のノードにおいて前記ハートビート信号を受信することと、
前記ハートビート信号の受信に応答して、前記第２のノードから前記第１のノードにメッセージ応答を送信することであって、前記メッセージ応答が、ノード識別子およびホップカウント値を含むことと、
をさらに含む、請求項８に記載のコンピュータプログラムプロダクト。
【請求項１０】
前記往復時間を前記ルックアップテーブルに格納することであって、前記往復時間が、前記ルックアップテーブルにおける前記ホップカウント値に関連付けられることと、
前記往復時間から１つまたは複数の追加往復時間を推定することと、
前記１つまたは複数の追加往復時間を用いて前記ルックアップテーブルを完成することと、
をさらに含む、請求項９に記載のコンピュータプログラムプロダクト。
【請求項１１】
前記往復時間が、前記ハートビート信号の時間間隔を超過する場合に、前記ローカルピアグループネットワークの前記サイズを調整することをさらに含む、請求項８に記載のコンピュータプログラムプロダクト。
【請求項１２】
前記ハートビート信号の前記時間間隔を超過する前記往復時間を利用することによって、前記ローカルピアグループネットワークの新しいサイズを前記ルックアップテーブルから選択することをさらに含む、請求項１１に記載のコンピュータプログラムプロダクト。
【請求項１３】
前記第１のノードと前記第２のノードとの間の最大許容可能ホップカウント値を低減することと、
前記往復時間が、前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記第１のノードと前記第２のノードとの間の前記最大許容可能ホップカウント値をさらに低減することと、
をさらに含む、請求項１１に記載のコンピュータプログラムプロダクト。
【請求項１４】
最大許容可能ホップカウント値を因数で除算して、前記第１のノードと前記第２のノードとの間の新しい最大許容可能ホップカウント値を確立することと、
前記往復時間が前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記新しい最大許容可能ホップカウント値を前記因数で除算することと、
をさらに含む、請求項１１に記載のコンピュータプログラムプロダクト。
【請求項１５】
ローカルピアグループネットワークのサイズを決定するためのシステムであって、
第１のノードと第２のノードとの間の往復時間を測定するように、かつ前記測定された前記往復時間を利用して前記ローカルピアグループネットワークの前記サイズをルックアップテーブルから選択するように動作可能なプロセッサを含むシステム。
【請求項１６】
前記プロセッサが、
前記第１のノードから前記第２のノードにハートビート信号を送信するように、
前記第２のノードにおいて前記ハートビート信号を受信するように、
前記ハートビート信号の受信に応じて、前記第２のノードから前記第１のノードにメッセージ応答を送信するように、
さらに動作可能であり、
前記メッセージ応答が、ノード識別子およびホップカウント値を含む、
請求項１５に記載のシステム。
【請求項１７】
前記プロセッサが、前記往復時間を前記ルックアップテーブルに格納するようにさらに動作可能であり、
前記往復時間が、前記ルックアップテーブルにおける前記ホップカウント値に関連付けられ、
前記往復時間から１つまたは複数の追加往復時間を推定し、
前記１つまたは複数の追加往復時間を用いて前記ルックアップテーブルを完成する、
請求項１６に記載のシステム。
【請求項１８】
前記プロセッサが、前記往復時間が前記ハートビート信号の時間間隔を超過する場合を決定し、かつ前記往復時間が前記ハートビート信号の前記時間間隔を超過する場合に、前記ローカルピアグループネットワークの前記サイズを調整するようにさらに動作可能である、請求項１５に記載のシステム。
【請求項１９】
前記プロセッサが、前記ハートビート信号の前記時間間隔を超過する前記往復時間を利用することによって、前記ローカルピアグループネットワークの新しいサイズを前記ルックアップテーブルから選択するようにさらに動作可能である、請求項１８に記載のシステム。
【請求項２０】
前記プロセッサが、
前記第１のノードと前記第２のノードとの間の最大許容可能ホップカウント値を低減するように、
前記第１のノードと前記第２のノードとの間の前記往復時間が、前記ハートビート信号の前記時間間隔を引き続き超過するかどうかを決定するように、
前記往復時間が、前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記第１のノードと前記第２のノードとの間の前記最大許容可能ホップカウント値をさらに低減するように、
さらに動作可能である、請求項１８に記載のシステム。
【請求項２１】
前記プロセッサが、
最大許容可能ホップカウント値を因数で除算して、前記第１のノードと前記第２のノードとの間の新しい最大許容可能ホップカウント値を確立するように、
前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を引き続き超過するかどうかを決定するように、
前記往復時間が前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記新しい最大許容可能ホップカウント値を前記因数でさらに除算するように、
さらに動作可能である、請求項１８に記載のシステム。
【請求項１】
ローカルピアグループネットワークのサイズを決定するためにコンピュータによって実行される方法であって、
第１のノードと第２のノードとの間の往復時間を測定することと、
前記測定された往復時間を利用して、前記ローカルピアグループネットワークの前記サイズをルックアップテーブルから選択することであって、前記コンピュータが、測定および利用の１つまたは複数のステップを実行することと、
を含む方法。
【請求項２】
前記第１のノードから前記第２のノードにハートビート信号を送信することと、
前記第２のノードにおいて前記ハートビート信号を受信することと、
前記ハートビート信号の受信に応答して、前記第２のノードから前記第１のノードにメッセージ応答を送信することであって、前記メッセージ応答が、ノード識別子およびホップカウント値を含むことと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記往復時間を前記ルックアップテーブルに格納することであって、前記往復時間が、前記ルックアップテーブルにおける前記ホップカウント値に関連付けられることと、
前記往復時間から１つまたは複数の追加往復時間を推定することと、
前記１つまたは複数の追加往復時間を用いて前記ルックアップテーブルを完成することと、
をさらに含む、請求項２に記載の方法。
【請求項４】
前記往復時間が、前記ハートビート信号の時間間隔を超過する場合に、前記ローカルピアグループネットワークの前記サイズを調整することをさらに含む、請求項１に記載の方法。
【請求項５】
前記ハートビート信号の前記時間間隔を超過する前記往復時間を利用することによって、前記ローカルピアグループネットワークの新しいサイズを前記ルックアップテーブルから選択することをさらに含む、請求項４に記載の方法。
【請求項６】
前記第１のノードと前記第２のノードとの間の最大許容可能ホップカウント値を低減することと、
前記往復時間が、前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記第１のノードと前記第２のノードとの間の前記最大許容可能ホップカウント値をさらに低減することと、
をさらに含む、請求項４に記載の方法。
【請求項７】
最大許容可能ホップカウント値を因数で除算して、前記第１のノードと前記第２のノードとの間の新しい最大許容可能ホップカウント値を確立することと、
前記往復時間が前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記新しい最大許容可能ホップカウント値を前記因数でさらに除算することと、
をさらに含む、請求項４に記載の方法。
【請求項８】
ローカルピアグループネットワークのサイズを決定するためのコンピュータプログラムプロダクトであって、
第１のノードおよび第２のノードとの間の往復時間を測定することと、
前記測定された往復時間を利用して、前記ローカルピアグループネットワークの前記サイズをルックアップテーブルから選択することであって、前記コンピュータが、測定および利用の１つまたは複数のステップを実行することと、
を含む方法を実行するための、プロセッサによって可読であり、かつ前記プロセッサによる実行のための命令を記憶する記憶媒体を含むコンピュータプログラムプロダクト。
【請求項９】
前記第１のノードから前記第２のノードにハートビート信号を送信することと、
前記第２のノードにおいて前記ハートビート信号を受信することと、
前記ハートビート信号の受信に応答して、前記第２のノードから前記第１のノードにメッセージ応答を送信することであって、前記メッセージ応答が、ノード識別子およびホップカウント値を含むことと、
をさらに含む、請求項８に記載のコンピュータプログラムプロダクト。
【請求項１０】
前記往復時間を前記ルックアップテーブルに格納することであって、前記往復時間が、前記ルックアップテーブルにおける前記ホップカウント値に関連付けられることと、
前記往復時間から１つまたは複数の追加往復時間を推定することと、
前記１つまたは複数の追加往復時間を用いて前記ルックアップテーブルを完成することと、
をさらに含む、請求項９に記載のコンピュータプログラムプロダクト。
【請求項１１】
前記往復時間が、前記ハートビート信号の時間間隔を超過する場合に、前記ローカルピアグループネットワークの前記サイズを調整することをさらに含む、請求項８に記載のコンピュータプログラムプロダクト。
【請求項１２】
前記ハートビート信号の前記時間間隔を超過する前記往復時間を利用することによって、前記ローカルピアグループネットワークの新しいサイズを前記ルックアップテーブルから選択することをさらに含む、請求項１１に記載のコンピュータプログラムプロダクト。
【請求項１３】
前記第１のノードと前記第２のノードとの間の最大許容可能ホップカウント値を低減することと、
前記往復時間が、前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記第１のノードと前記第２のノードとの間の前記最大許容可能ホップカウント値をさらに低減することと、
をさらに含む、請求項１１に記載のコンピュータプログラムプロダクト。
【請求項１４】
最大許容可能ホップカウント値を因数で除算して、前記第１のノードと前記第２のノードとの間の新しい最大許容可能ホップカウント値を確立することと、
前記往復時間が前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記新しい最大許容可能ホップカウント値を前記因数で除算することと、
をさらに含む、請求項１１に記載のコンピュータプログラムプロダクト。
【請求項１５】
ローカルピアグループネットワークのサイズを決定するためのシステムであって、
第１のノードと第２のノードとの間の往復時間を測定するように、かつ前記測定された前記往復時間を利用して前記ローカルピアグループネットワークの前記サイズをルックアップテーブルから選択するように動作可能なプロセッサを含むシステム。
【請求項１６】
前記プロセッサが、
前記第１のノードから前記第２のノードにハートビート信号を送信するように、
前記第２のノードにおいて前記ハートビート信号を受信するように、
前記ハートビート信号の受信に応じて、前記第２のノードから前記第１のノードにメッセージ応答を送信するように、
さらに動作可能であり、
前記メッセージ応答が、ノード識別子およびホップカウント値を含む、
請求項１５に記載のシステム。
【請求項１７】
前記プロセッサが、前記往復時間を前記ルックアップテーブルに格納するようにさらに動作可能であり、
前記往復時間が、前記ルックアップテーブルにおける前記ホップカウント値に関連付けられ、
前記往復時間から１つまたは複数の追加往復時間を推定し、
前記１つまたは複数の追加往復時間を用いて前記ルックアップテーブルを完成する、
請求項１６に記載のシステム。
【請求項１８】
前記プロセッサが、前記往復時間が前記ハートビート信号の時間間隔を超過する場合を決定し、かつ前記往復時間が前記ハートビート信号の前記時間間隔を超過する場合に、前記ローカルピアグループネットワークの前記サイズを調整するようにさらに動作可能である、請求項１５に記載のシステム。
【請求項１９】
前記プロセッサが、前記ハートビート信号の前記時間間隔を超過する前記往復時間を利用することによって、前記ローカルピアグループネットワークの新しいサイズを前記ルックアップテーブルから選択するようにさらに動作可能である、請求項１８に記載のシステム。
【請求項２０】
前記プロセッサが、
前記第１のノードと前記第２のノードとの間の最大許容可能ホップカウント値を低減するように、
前記第１のノードと前記第２のノードとの間の前記往復時間が、前記ハートビート信号の前記時間間隔を引き続き超過するかどうかを決定するように、
前記往復時間が、前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記第１のノードと前記第２のノードとの間の前記最大許容可能ホップカウント値をさらに低減するように、
さらに動作可能である、請求項１８に記載のシステム。
【請求項２１】
前記プロセッサが、
最大許容可能ホップカウント値を因数で除算して、前記第１のノードと前記第２のノードとの間の新しい最大許容可能ホップカウント値を確立するように、
前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を引き続き超過するかどうかを決定するように、
前記往復時間が前記ハートビート信号の前記時間間隔を引き続き超過する場合に、前記第１のノードと前記第２のノードとの間の前記往復時間が前記ハートビート信号の前記時間間隔を超過しなくなるまで、前記新しい最大許容可能ホップカウント値を前記因数でさらに除算するように、
さらに動作可能である、請求項１８に記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公表番号】特表２０１３−５１３３０５（Ｐ２０１３−５１３３０５Ａ）
【公表日】平成２５年４月１８日（２０１３．４．１８）
【国際特許分類】
【出願番号】特願２０１２−５４２１４４（Ｐ２０１２−５４２１４４）
【出願日】平成２２年１２月１日（２０１０．１２．１）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０５８４８５
【国際公開番号】ＷＯ２０１１／０６８８２４
【国際公開日】平成２３年６月９日（２０１１．６．９）
【出願人】（５０７３０２９００）トヨタ インフォテクノロジー センター，ユー．エス．エー．，インコーポレイテッド (10)
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【Ｆターム（参考）】
【公表日】平成２５年４月１８日（２０１３．４．１８）
【国際特許分類】
【出願日】平成２２年１２月１日（２０１０．１２．１）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０５８４８５
【国際公開番号】ＷＯ２０１１／０６８８２４
【国際公開日】平成２３年６月９日（２０１１．６．９）
【出願人】（５０７３０２９００）トヨタ インフォテクノロジー センター，ユー．エス．エー．，インコーポレイテッド (10)
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【Ｆターム（参考）】
[ Back to top ]