(57)【要約】  無線環境における無線ノード群間のデータ共有効率を最適化するシステムおよび方法が提供される。本技術は、データユニットを識別してそれにクラスを割り当てること、接続可能性種別を識別すること、該接続可能性種別および割り当てられたクラスに基づいて重要度因子を算出すること、該重要度因子を優先度因子にマッピングすること、該優先度因子に基づいてデータユニットの出力をスケジューリングすること、を含んでいる。スケジューラアルゴリズムを使用して、出力をスケジュールすることができる。無線ノード群のどのノードが所与の時間にデータユニットのコピーを持っているかに基づいて、クラスを割り当てることができる。仲裁プロセスを使用して、優先度因子を決定することができる。いくつのノードがデータを受信することになるかおよびノードがどれくらいのデータを必要とするかに基づいた重要度因子重み付けアルゴリズムを使用して、重要度因子を決定することができる。
2010511324.tif 000002
【特許請求の範囲】
【請求項１】
無線環境における無線ノード群間のデータ共有効率を最適化する方法であって、各ノード上で、
データユニットを識別するステップと、
前記データユニットにクラスを割り当てるステップと、
接続可能性種別を識別するステップと、
前記接続可能性種別および前記割り当てられたクラスに基づいて、重要度因子を算出するステップと、
前記重要度因子を優先度因子にマッピングするステップと、
前記優先度因子に基づいて、前記データユニットの出力をスケジューリングするステップと、
を含む方法。
【請求項２】
前記スケジューリングステップはスケジューラアルゴリズムを使用して実行される、請求項１に記載の方法。
【請求項３】
前記クラスを割り当てるステップは、前記無線ノード群のどの１つまたは２つ以上のノードが所与の時間に前記データユニットのコピーを持っているかに基づいている、請求項１に記載の方法。
【請求項４】
前記マッピングステップは、前記優先度因子を決定する仲裁プロセスを実行するステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記算出ステップは、前記データを受信するノード数および前記データを取得するノードの重要度に基づいた重要度因子重み付けアルゴリズムを用いて行われる、請求項１に記載の方法。
【請求項６】
前記データユニットは局所的に測定された値を有する請求項１に記載の方法。
【請求項７】
前記局所的に測定された値は、特定の無線ソースからのＳＮＲ、複数のノード間の無線リンクＳＮＲ、および所与の時間におけるＧＰＳ位置の少なくとも１つを含む、請求項６に記載の方法。
【請求項８】
前記接続可能性種別は、前記無線ノード群のトポロジーと、前記無線ノード群間の送信速度とを含む、請求項１に記載の方法。
【請求項９】
無線環境における無線ノード群間のデータ共有効率を最適化するシステムであって、
クラスを有するデータユニットと、
接続可能性種別と、
前記接続可能性種別および前記割り当てられたクラスに基づいて算出された重要度因子と、
を有し、
該重要度因子は優先度因子にマッピングされ、該データユニットは前記優先度因子に基づいて出力される、
システム。
【請求項１０】
前記データユニットは、スケジューラアルゴリズムを使用して出力されるようにスケジュールされる、請求項９に記載のシステム。
【請求項１１】
前記データユニットのコピーを持つ前記無線ノード群の１つまたは２つ以上のノードに基づいて、前記データユニットにクラスが割り当てられる、請求項９に記載のシステム。
【請求項１２】
前記優先度因子を決定する仲裁プロセスをさらに有する、請求項９に記載のシステム。
【請求項１３】
前記重要度因子の算出は、前記データを受信するノード数および前記データを取得するノードの重要度に基づいた重要度因子重み付けアルゴリズムを使用して行われる、請求項９に記載のシステム。
【請求項１４】
前記データユニットは局所的に測定されたデータ型をさらに有する、請求項９に記載のシステム。
【請求項１５】
前記局所的に測定されたデータ型は、特定の無線ソースからのＳＮＲ、複数のノード間の無線リンクＳＮＲ、および所与の時間におけるＧＰＳ位置の少なくとも１つを含む、請求項１４に記載のシステム。
【請求項１６】
前記接続可能性種別は、前記無線ノード群のトポロジーと、前記無線ノード群間の送信速度とを含む、請求項９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にアドホックネットワーキングに関し、より具体的には無線環境においてノード間でデータを配信することに関する。
【背景技術】
【０００２】
フェージングが大きく、ノイズが多い状況が一般的である厳しい無線環境においては、任意の２つのノード間でリンクが利用可能であるかどうかは不確実である。接続喪失が長時間続く可能性があることが予想できる。それにもかかわらず、このような厳しい環境内をあちこち移動するアドホックモバイルノードの一団は、この環境にある他のすべての無線ノードにデータを送信する必要がある。リンクが利用できるかどうかが不確実なので、送られたデータの大部分が、最初に送信されたときに他のすべてのノードに届くとは限らない。したがって、これらのデータは後で再送信する必要がある。
【０００３】
エピデミックアルゴリズム（ｅｐｉｄｅｍｉｃ  ａｌｇｏｒｉｔｈｍ）およびゴシップアルゴリズム（ｇｏｓｓｉｐ  ａｌｇｏｒｉｔｈｍ）のような既存の方法が、最初にどのノードでも受信されなかったデータを再送信するのに従来から使用されている。これらの手法では、各ノードは無作為に近隣ノードを選択し、どのデータが該近隣ノードから欠落しているかを調べて欠落データを送信する。しかしながら、とりわけ冗長データが送信されるので、これらの方法を用いた再送信は非効率的である。
【０００４】
非特許文献１において、Ｄｅｍｅｒｓらは、流行過程（ｅｐｉｄｅｍｉｃ  ｐｒｏｃｅｓｓ）の例として、アンチエントロピー（ａｎｔｉ−ｅｎｔｒｏｐｙ）およびｒｕｍｏｒ  ｍｏｎｇｅｒｉｎｇ（うわさまき散らし）について説明している（非特許文献１参照）。アンチエントロピーでは、各サイトは他のサイトを無作為に定期的に選択し、該サイトと情報を交換する。該交換は冗長なまたは反復的なデータ送信を伴うことがあるので、アンチエントロピー技術はデータの伝播にとって信頼できる技術ではあるが、極めて煩雑である。Ｒｕｍｏｒ  ｍｏｎｇｅｒｉｎｇでは、サイトは、他のサイトの１つに最新のうわさがあるかどうかを尋ねることによって、他のサイトと共有しようとする最新情報、すなわち「最新のうわさ」を受信する。該最新のうわさが１つのサイトと共有されている場合には他のサイトに尋ねることができる。最新情報がすべてのサイトに届かない場合もあるので、Ｒｕｍｏｒ  ｍｏｎｇｅｒｉｎｇも冗長なデータ送信を伴うことがあり、アンチエントロピーほど信頼性も高くない。
【０００５】
非特許文献２では、ネットワークの到達可能なメンバーの大半がグループにマルチキャストされたパケットを確実に受信するために、周期的な匿名のゴシップをバックグラウンドに実装することについて説明している（非特許文献２参照）。一連のゴシップでは、発信元ノードは自身のグループ内の他のノードを無作為に選択し、発信元のメッセージに関する、選択されたノード情報を送信する。選択されたノードにまだ発信元のメッセージがない場合、該２つのノードはメッセージを交換することができる。しかしながら、重複データまたは冗長データの送信が生じ得る。
【０００６】
前述の手法の問題点の中には、残りのノードが何を行っているかに関する情報の欠如だけでなく、ポイントツーポイントすなわちノードツーノード・ソリューションの利用もある。その結果、これらの手法は、複数のノードに同時に送信する、固有のブロードキャスト媒体である無線環境に対しては最適化されていない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国仮特許出願番号第６０／８６１，１６１号
【非特許文献】
【０００８】
【非特許文献１】Ｅｐｉｄｅｍｉｃ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｒｅｐｌｉｃａｔｅｄ  Ｄａｔａｂａｓｅ  Ｍａｎａｇｅｍｅｎｔ”ｉｎ  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｐｒｉｎｃｉｐｌｅｓ  ｏｆ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔｉｎｇ，１９８７
【非特許文献２】Ａｎｏｎｙｍｏｕｓ  Ｇｏｓｓｉｐ：Ｉｍｐｒｏｖｉｎｇ  Ｍｕｌｔｉｃａｓｔ  Ｒｅｌｉａｂｉｌｉｔｙ  ｉｎ  Ｍｏｂｉｌｅ  Ａｄ−Ｈｏｃ  Ｎｅｔｗｏｒｋｓ，”Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔｉｎｇ  Ｓｙｓｔｅｍｓ，２００１
【発明の概要】
【発明が解決しようとする課題】
【０００９】
アドホック無線ノードがメッシュネットワークで構成された厳しい無線環境において、一般的な用途は、各ノードが他のノードへのブロードキャストデータまたはマルチキャストデータを持っていることである。無線アドホックネットワークは本質的に信頼性が低いので、送信されたデータが意図した送信先に届かないことが非常に多く、したがってこのデータの送信は多くの場合複数回の再送信を必要とする。慎重なスケジューリングおよびプラニングがない状態では、この再送信は、データの冗長性、およびデータの緊急性に関する知識不足により、ネットワーク全体の観点から著しい非効率性を発生させる。
【課題を解決するための手段】
【００１０】
好都合に、本発明は、システム全体によって受信されるデータの総量の最適化を可能にする、効率的なデータ構造を提供する。本発明は、無線環境情報のみならず、ノードの状態、配信されるデータユニットの重要度に関する知識をも用いて、どのようにデータに優先度をつけ、スケジュールすべきかを最適化する。具体的には、本発明によるシステムおよび方法は、データユニットを識別すること、該データユニットに、誰がそのデータを最も必要とするかに一般的に基づいてクラスを割り当てること、ノードのトポロジーおよびノード間の送信速度を記述できる接続可能性種別を識別すること、該接続可能性種別およびクラスに基づいて重要度因子を算出すること、該重要度因子を優先度因子にマッピングすること、該優先度因子に基づいて上記データユニットの出力をスケジューリングすること、を含んでいる。一実施形態において、上記クラスは、どのノードが所与の時間にデータユニットのコピーを持っているかに基づいて割り当てられる。一実施形態において、重要度因子の算出は、データを受信するノード数および該データを取得する特定ノードの重要度に基づいたアルゴリズムを使用して行われる。
【図面の簡単な説明】
【００１１】
類似の参照番号が図面全体にわたって類似の部分を示す、本発明の非制限的な例示の実施形態として記載した図面を参照することにより、本発明を以下の発明を実施するための形態でさらに詳細に説明する。しかし、当然のことながら、本発明は図示した厳密な配置および手段に限定されるものではない。
【図１】本発明の優先度をつける部分の概略図である。
【図２】ノードにおける４つのアプリケーションマップのスナップショットである。
【図３】接続可能性行列（Ｃｏｎｎｅｃｔｉｖｉｔｙ  Ｍａｔｒｉｘ）および無線ホップ（Ｒａｄｉｏ  Ｈｏｐ）を示している。
【図４】近隣グループの種類（Ｔｙｐｅ  ｏｆ  Ｎｅｉｇｈｂｏｒｈｏｏｄ  Ｇｒｏｕｐ）を示している。
【図５】仲裁の距離メトリック（Ｄｉｓｔａｎｃｅ  Ｍｅｔｒｉｃ  ｆｏｒ  Ａｒｂｉｔｒａｔｉｏｎ）を示している。
【図６】２ホップノードへの重みの割り当て（Ａｓｓｉｇｎｍｅｎｔ  ｏｆ  Ｗｅｉｇｈｔ）を示している。
【図７】本発明の実施形態のフローチャートである。
【図８】戦略Iにおける利得点数である。
【図９】戦略ＩＩにおける利得点数である。
【発明を実施するための形態】
【００１２】
好都合に、本発明は厳しい無線環境における無線ノード群間のデータ共有効率を最適化するシステムおよび方法を提供する。本解決策により、データの最初のブロードキャスト中、すべてのノードによってうまく受信されなかったデータの効率的配信が可能となる。本システムおよび方法は、各ノードのデータ受信状態と、すべてのノードの接続可能性と、を含む動的な状況を考慮し、全体の性能が最適化されるように各データユニットに優先度を割り当てる。
【００１３】
ＡＣＥＲＴ（Ａｄａｐｔｉｖｅ  Ｃｏｇｎｉｔｉｏｎ  Ｅｎｈａｎｃｅｄ  Ｒａｄｉｏ  Ｔｅａｍ）環境のような接続が断続的である厳しい無線環境が、本発明が適用されうる環境の例を提供している。あちこち移動している４つの無線ノードが、すべての無線ノードまたはチームメンバーにデータを送ろうとする。目標は、各ノードがすべてのチームメンバーに局所的に生成されたすべてのデータを最短時間で送信することである。ＡＣＥＲＴ環境の可能性のあるシナリオは、配信されるのを待っているデータの量および受信されたデータの量が、ノードの接続可能性およびチャネルの容量に応じて、各ノードに対して著しく異なり得るシナリオを含んでいる。ブロードキャスト（またはマルチキャスト）環境に関するデータ配信の最適化は、「不均一」ブロードキャスティングと呼ばれている。チャネル容量が変化しているので、ＡＣＥＲＴ環境はさらに複雑度を増している。データソース、データシンク、およびチャネル容量におけるこの不均一性は、優先化データ構造および機構が全体的な性能を大幅に改善することができることを示唆している。本発明は、どのようにデータを編成し、優先度をつけ、伝播させて、動的なチャネル特性とマルチキャスト適合性とをより良く一致させ、それによりデータ配信を最適化すべきであるかを例証している。
【００１４】
図１は、本発明の実施形態における優先度情報算出の概略図を示し、図２は、ノードでの４つのアプリケーションマップのスナップショットである。各データオブジェクト１０は３つの部分、すなわちデータ状態１２、データユニット１４、およびメタデータ１６を持っている。データ状態１２とは、データユニット１４が、図２に示したノード２０に存在しているかどうかを示すデータの特性である。図２に示し、以下に詳細に説明するユーザダイジェスト２２は、データ状態１２に基づいて作成される。データユニット１４は、環境信号対雑音比（ＳＮＲ:Signal to Noise Ratio）の測定値、無線リンクＳＮＲ、時間、および全地球測位衛星（ＧＰＳ:Global Positioning Syaytem）によって決定される位置のような位置情報のようなデータ型またはデータのコンテンツ、または他のデータを運ぶ。メタデータ１６は優先化データであり、データオブジェクトがどのように処理されるかについての命令のような他の情報を運んでもよい。
【００１５】
ＡＣＥＲＴアプリケーションは、異なるデータ型のデータをマルチキャストする。異なる種類のデータは、別個のパケットに配置される（別個にパケット化される）か、または共に束ねられてもよい。これらのデータパケットがＡＣＥＲＴデータユニット１４である。全データは、図２に示す、アプリケーションデータマップすなわちアプリケーションマップ１８として知得される。データユニット１４は上記のデータ型のいずれを表していてもよい。１つのデータユニット１４が生成された場合、該データユニットは、通常ＳＮＲ測定値、または１つの時間および位置データのようなグリッド位置に関連づけられるので、これはアプリケーションデータマップ１８と呼ばれている。一般に、データユニット１４は特定の位置に関連づけられる必要はない。その代わりに、例えばデータユニット１４を時間に関連づけるか、または単にシーケンス番号に関連づけてもよい。
【００１６】
上述のように、図２は、ノードＤ  ２０における４つのアプリケーションマップ１８のスナップショットを示し、陰影付きのセルまたは小さな正方形は、局所的に生成されたデータまたは受信されたデータのいずれかであるデータユニット１４を表している。このスナップショットを使用して、１つのデータユニット１４をブロードキャストすることに対するＡＣＥＲＴシステムの利得を測定することができる。各ノード２０のアプリケーションマップ１８は、ユーザレベルの概要、またはユーザダイジェスト２２、すなわちノード２０に対する０および１の入力を持つテーブルとして表すことができる。０は特定のデータユニット１４の欠落を示し、１は該データユニットが存在していることを示している。ユーザダイジェスト２２は、他のすべてのノード２０に、定期的に例えば１０秒に１回ブロードキャストされる。ユーザダイジェストブロードキャストの頻度の最適値はシステムパラメータであり、システムの全体的なリソースに左右される。各ノード２０で、すべてのノードからのユーザダイジェスト２２のすべてを比較して、以下のように定義されるＳＷＦ（Ｓｉｇｎｉｆｉｃａｎｃｅ  Ｗｅｉｇｈｔｉｎｇ  Ｆａｃｔｏｒ：重要度重みづけ因子）のｗyと呼ばれるエンティティを作成する。
【００１７】
ｗyは次式（３．１）により与えられ、ノードｙが持っていないデータユニットの重要度の測定値である。
【００１８】
ｗy＝ｂ＋（１−ｆy）      （３．１）
ここで、ｂは０．５の固定バイアスである。
【００１９】
ｆyは、全取得データで割ったｙの受信データ（ｙによって生成されたデータを除く）の端数である。例として、ノードＣにより受信されたデータの端数ｆcは、次式で与えられる。
【００２０】
ｆc＝（ｄ＋ａ＋ｂ）／（Ｄ＋Ａ＋Ｂ）      （３．２）
ここで、分子の文字は生成データを表し、分母の文字は受信データを表している。この定義では、ｆyの範囲は、０から１までであり、対応するｗyの範囲は、１．５から０．５までである。
【００２１】
上述のように、ＡＣＥＲＴ環境の特徴は、データユニットの需要または重要度が、時間、状況、無線条件、およびＡＣＥＲＴ実行中のすべてのデータ配信の総計ステータス、のようなデータ型によって変化することである。この需要構造に最も良く適合させるために、ＤＤＰＤＳ（Ｄｅｍａｎｄ−Ｄｒｉｖｅｎ  Ｐｒｉｏｒｉｔｙ  Ｄａｔａ  Ｓｔｒｕｃｔｕｒｅ：需要駆動型優先化データ構造）と呼ばれる本発明の優先化データ構造が提供される。この構造は、どのＡＣＥＲＴチームのノード群が一定の時間間隔中そのデータユニットを持っているかによる、ＡＣＥＲＴノードでのすべてのデータユニット１４のクラスへの分類に基づいている。クラスはデータ配信クラス（Ｄａｔａ  Ｄｅｌｉｖｅｒｙ  Ｃｌａｓｓ）、または単にクラス２４と呼ばれる。クラス２４の総数は、該データユニット１４を持つすべてのノード群２０の組み合わせによって与えられる。テーブル１は、４ノードのＡＣＥＲＴシナリオのクラス２４の基本構造を説明している。
【００２２】
ＤＤＰＤＳのクラス２４のデータを編成することは、各データユニット１４に対する需要のレベルを明確に区別するものである。例として、クラス００１０  ２４はノード３  ２０のみが持つデータを指している。ノード３  ２０がこのデータユニット１４をブロードキャストしたときに、該ブロードキャストが成功した場合、他の３つのノード２０が該データを受信してそこから利得を得る、それによりＡＣＥＲＴシステムの総利得点数（ｔｏｔａｌ  ｂｅｎｅｆｉｔ  ｃｏｕｎｔ）は３データユニット分増加することになる。比較として、クラス１０１１  ２４については、ノード１、３、および４のすべてにデータユニット１４がある。ノード３  ２０がこのデータユニット１４をブロードキャストして、該ブロードキャストが成功した場合、ノード２  ２０のみがそれから利得を得て、総利得点数を１データユニット分上げることになる。クラス００１０  ２４と比較した場合、クラス１０１１  ２４からデータを送信することは、ＡＣＥＲＴの全体的な目標の観点からすると、より少ない値を提供することが予期される。
【００２３】
【表１】
2010511324.tif 000003
【００２４】
特定のデータユニット１４をブロードキャストする利得も、複数のノード２０の間の現在の通信チャネルにより決まる。一般に、複数のＡＣＥＲＴノード２０間の接続可能性は、ｉｊ番目の要素がノードｉとノードｊとの間の最小の無線ホップ数を示すｎｘｎ行列である、行列Ｈで記述することができる。図３に示すように、ノードｉおよびｊの無線出力が互いに到達できる場合には、該ノードｉ、ｊは１ホップで接続されている。ノード１と３が１ホップで接続され、ノード３と２も１ホップで接続されているが、ノード１と２が互いの無線範囲内にない場合、ノード１と２は、Ｈ行列の対応する２の入力に２ホップで接続されている（第１行、第２列）。一般に、ノードｘとノードｙは、それらの間の最短経路がｎ個の無線リンクを含んでいる場合、ｎホップで接続されている。
【００２５】
ＤＤＰＤＳの文脈に接続可能性種別または状態２６を組み込むために、隣接グループのコンセプトであるＧiが、ブロードキャスティング無線ノード２０について定義される。グループＧiは、ブロードキャスティングノードｉと、該ノードｉに１ホップで接続されたすべてのノードとから成る。図３の異なる無線ノード２０についての異なる種類の近隣グループを図４に示している。図４に示すように、各グループについて、４ノードのＡＣＥＲＴ環境に８種類の接続可能性がある。各グループの円で囲んだ接続可能性種別２６は、図３の無線ホップトポロジーに対応している。
【００２６】
接続可能性のトポロジーは、全ＡＣＥＲＴ目標に関して、配信データ（Ｄｅｌｉｖｅｒｙ  Ｄａｔａ）クラス２４の重要度に影響を及ぼすが、以下により詳細に説明する。
【００２７】
データの特定のクラス２４をブロードキャストする利得に関する接続可能性の影響を、異なるグループタイプの列およびクラス２４の行を持つテーブル２に示しており、クラス２４を近隣にあるグループタイプの反対に配置して描くことができる。テーブル２において、数値がテーブルの関連入力項目に配置されており、データユニット１４の特定のクラス２４がブロードキャストされた場合、各値または入力がＡＣＥＲＴシステムで受信されたデータユニット１４の総数となる。この入力は第１のレベルの優先度割り当てと考えることができ、より大きな数はより高い優先度を示唆している。
【００２８】
テーブル２において、ノードＩＤ、例えば−（Ｂ）が入力されたある入力項目がある。これは、データを送信するノードＡの代わりに、丸括弧内のノード（ノードＢ）がデータを送信することを示唆していることを示している。他のノードがデータを送信する理由は、データを持っているノードが２つ以上あるときには、重複を避けるために１つのノードのみがデータを送信すべきだからである。したがって、１つのノード２０だけがデータユニット１４を送信するように、仲裁プロセス（ａｒｂｉｔｒａｔｉｏｎ  ｐｒｏｃｅｓｓ）が複数のノード２０間で実行されうる。該仲裁プロセスは、以下に示したアルゴリズムの詳細によると、複数のピア間の近接性およびチャネル条件により決まる。一実施形態において、図５に示したような距離メトリックは、テーブル２の特定のノードを選ぶ基準を提供することができる。この実施形態では、より短い距離が選択されている。
【００２９】
【表２】
2010511324.tif 000004
【００３０】
ＤＤＰＤＳのデータのクラス２４の値を割り当てることに対する接続可能性および仲裁の効果を調査した。さらに、ＳＷＦの効果、すなわち２つのノード関する１つのデータの重要度の測定値、例えば数式３．１は、以下の数式に従って、ＤＤＰＤＳテーブル２の入力項目をＳＦ（Ｓｉｇｎｉｆｉｃａｎｃｅ  Ｆａｃｔｏｒ：重要度因子）２８と置き換えることにより、ＤＤＰＤＳに含めることがでる。
【００３１】
ノードｘに対するＳＦ＝
【数１】
2010511324.tif 000005
ここで、
クラス２４は２値（δ1δ2δ3δ4）として示され、例えば、００１０はクラス２である。ノードｙにデータがない場合δyは０、ノードｙにデータがある場合は１である。したがって、クラス２（００１０）は、ノード３にはデータがあり、ノード１、２、および４にはデータがないことを示している。
【００３２】
ｗyは、ノードｘにはデータがあるがノードｙにはないという、データユニット１４の重要度の測定値であり（上記の数式３．１を参照）、
ｐｘｙはノードｘとｙとの間のうまくいく通信の確率である。
【００３３】
この数式を用いて、Pxyを１と仮定すると、ＤＤＰＤＳテーブル３が得られる。
【００３４】
【表３】
2010511324.tif 000006
【００３５】
次に、ＳＦ  ２８は、あらかじめ定義されたマッピングまたは順位付けベースのマッピングのいずれかを介して、優先度クラス（Ｐｒｉｏｒｉｔｙ  ｃｌａｓｓ）にマッピングすることができる。
【００３６】
こうして、接続可能性トポロジーを考慮に入れながら重要度をクラス２４に割り当てる方法を説明する。１ホップ以上離れたノードを考慮しない、若しくは、２ホップ以上離れたノードに対して、０の重みが割り当てられることを想定する。これは、最初の焦点を、直接データ転送経路におき、Ａ→Ｂ→Ｃのような間接的転送は考慮しないためである。しかしながら、いくつかの非常に厳しい無線環境では、特定のノードは長期間互いの範囲内になくてもよい。そのような状況では、間接的経路を利用することが望ましい。
【００３７】
間接的経路を可能にするために、ＳＦ  ２８が重みを第２のホップノードに割り当てることを含むように増加される。これを図６に示す。このシナリオでは、ノード１  ２０は、ノード３  ２０およびノード４  ２０に直接接続され、ノード３  ２０経由でノード２  ２０に２ホップで接続されている。ノード２  ２０がデータを必要としているとき、すなわち多くのデータが欠けているとき、データユニット１４をノード３  ２０に送り、データユニット１４がノード２  ２０に転送されるように要求することは価値があるに違いない。このことは、ｗ2が大きい場合に発生する。第２のホップノードを実現するために、ノード１  ２０は、ノード３  ２０がデータユニット１４を最も高い優先度を持つノード２  ２０に直ちに送信することができるように、例えば、データをマークする必要がある。２ホップのネットワークに対する新しいＳＦ  ２８は、次式で与えられる。
【００３８】
ノードｘ（２ホップ）に対するＳＦ＝
【００３９】
【数２】
2010511324.tif 000007
ここで、ｔ2は２ホップノードに割り当てられ、α（１−δy）として定義される係数である。αの初期値は０．５〜１の間に割り当てることができる。αの詳細はここでは取り扱わない。
【００４０】
図６のトポロジーに対する１ホップおよび２ホップの優先度割り当てを比較した例は、以下のとおりである（ｗ2＝ｗ3＞ｗ4と仮定すると、αは０．５、ｗ4＞０．５ｗ2である）。表４において、優先度因子３０へのＳＦ  ２８のマッピングは、２ホップ接続の影響を説明するためにそのままの順位付け配置に基づいている。
【００４１】
【表４】
2010511324.tif 000008
【００４２】
優先度の算出は以下のように演算する。データユニット１４が作成され、ファイル名のような一意の識別子が割り当てられる。テーブル１に従ってクラスマッピングをデータユニット１４に割り当てるのに使用されるユーザダイジェスト２２が定期的に取得される。Ｈ−行列は、数式３．４を用いてＳＦ  ２８を算出するのに使用される表３の列に対応する接続可能性種別２６を識別する。次に、ＳＦ  ２８は、いくつかのあらかじめ定義されたマッピングまたはそのままの順位付け配置に従って、例えば１からｑまで優先度因子３０にマッピングされる。
【００４３】
図７は、図１および２に係る本発明の実施形態のフローチャートである。ステップＳ１で、データユニット１４がノード２０で作成され、ファイル名のような一意の識別子を割り当てられる。ステップ２で、アプリケーションマップ１８に基づいて、クラス２４がデータユニット１４に割り当てられる。ステップＳ３で、接続可能性種別２が表３または表４の列に対応する、上記のＨ−行列に従って識別される。ステップＳ４で、ＳＦ  ２８が接続可能性種別２６およびクラス２４に基づいて算出される。次に、ステップＳ５で、ＳＦ  ２８は、いくつかのあらかじめ定義されたマッピングまたはそのままの順位付け配置に従って優先度因子３０にマッピングされる。いったん優先度マッピングが作成されると、ステップＳ６で、スケジューラ（不図示）を使用して、ＦＩＦＯバッファのデータユニットの出力をスケジュールする。優先度待ち行列および／または重み付け優先度キューのようなスケジューラアルゴリズムが使用されてもよい。
［仲裁プロセス］
１つ以上のノード２０が同一クラス２４のデータを持っている場合、１つのノード２０だけがデータまたはデータユニット１４を送信するような仲裁プロセスがあることが望ましい。このセクションでは、該仲裁に使用可能なアルゴリズムを提供する。なお、仲裁プロセスは、ノードのネットワーク接続可能性の局所的視点に基づいて、各ノード２０に対し独立して実行されることに留意されたい。複数のノードは通信環境に関するデータを継続的に共有しているが、仲裁については、該複数のノードは明確なコミュニケーションは取らない、すなわち既に収集した情報を使用するのみである。仲裁アルゴリズムは以下のとおりである。
【００４４】
１．２つまたは３つ以上のノード２０がデータユニット１４を持っている場合、これらのノードから１ホップで接続されているノードの数を比較する。１ホップで接続された多くの数のノードを有するノードが勝つ。この規則はｎホップまで拡張することができる。
【００４５】
２．規則１が解決しない場合、すなわちノードが１ホップで（またはｎホップまで）接続された同数のノード持っている場合、１ホップで接続されたすべてのノードの距離の合計を算出し、より短い距離を持つノードが勝つ。
【００４６】
３．規則２が解決しない場合、ノードＩＤの順序を用いて、その結果最小または最低のＩＤが勝つ。
【００４７】
なお、これらの規則がほとんどの事例を解決するはずであることに留意されたい。しかしながら、ある種のシナリオでは、この規則では解決しない可能性もある。問題は、１つのノードが１つの方法で決定する一方、他のノードは、潜在的にデータの同期またはエラー状態により、異なる結論に達する可能性があるということである。しかしながら、これらの事例はまれであり、該事例が起こった場合でも、非最適決定による性能に不利な条件は重要ではない。
［例］
ＡＣＥＲＴ環境は、１ｍ2の「セル」に分割される、１００ｍ×１００ｍのグリッド内で定義することがでる。このＡＣＥＲＴの例では、４つのＡＣＥＲＴノードが、実行（run）で呼び出された３０分の間に、〜１．４ｍ／ｓの速さで指定された経路に移動する。この期間中、各ノードは、それ自身を配置すること、ＳＮＲマップと呼ばれる環境ＳＮＲ値を測定すること、チームの他のすべてのノードと通信する能力を推定すること、を含む多数の測定を実行しながら、グリッドの約２５％を横断する。すべての測定データは、実行期間内に、チームの他のすべてのノードに配信される必要がある。実行の終了時点で、測定データは、いくつかのあらかじめ定義されたメトリックに対し、その完全性が評価される。第１の実行の後、通信無線リンクの性能情報は保持できるが、ＳＮＲマップを含む他のすべての測定値は廃棄されることになっている。さらなる３０分の第２の実行が行われる。第２の実行の目的は、認識アルゴリズムがどの程度うまく機能するかをテストすることである。メトリックがより厳格であることを除いて、同一パラメータ群が第２の実行で測定される。
【００４８】
ＡＣＥＲＴアプリケーションの重要な特徴は、データは、３０分の実行中に、各ノードからすべての他のノードに配信される必要があるということである。評価メトリックは、実行中にすべてのノードに配信されたデータの量を評価するので、複数のＡＣＥＲＴノード間での通信中、各メッセージまたはパケットに関する遅延要求はない。各ノードは、グリッドを通過するときに新しいデータを生成する。
【００４９】
ＡＣＥＲＴの実装は、ＣＡＲＴ（Ｃｏｇｎｉｔｉｖｅ  Ａｄａｐｔｉｖｅ  Ｒａｄｉｏ  Ｔｅａｍ）と呼ばれている。該ＣＡＲＴの物理的環境は、以下の特性により特徴づけられている。
【００５０】
−固有の無線ブロードキャスト媒体。ユニキャストおよびマルチキャストは同一の共有媒体でサポートされる。初期の実装は８０２．１１ｂに基づいている、したがってユニキャストパケットは承認されるが一方、ブロードキャストパケットは承認されない。
【００５１】
−各ノードの正確な位置は、ＧＰＳおよびアンカーノードシステムによって取得される。位置情報はＡＣＥＲＴノード間で分配される。
【００５２】
−各ノードは、無線環境モデリングアプリケーション（Ｒａｄｉｏ  Ｅｎｖｉｒｏｎｍｅｎｔ  Ｍｏｄｅｌｉｎｇ  Ａｐｐｌｉｃａｔｉｏｎ）またはＲＥＭＡと呼ばれるアプリケーションを介して、自身を取り囲む無線環境について学ぶことができ、これらのアプリケーションは、最良の推定値およびすべてのＡＣＥＲＴノード間の通信能力の予測を提供する。各ノードは、該ノードのピアの移動経路および速度だけでなく、ノード自身の移動経路および速度についても学習することができる。該情報は知識の基礎を構成しており、この情報を使用して、どのデータを、どのように送信すべきの推薦を行う認識計画が考案される。
【００５３】
−ルーティングは、特殊なマルチキャストアプリケーションなので、段階１ではデータ配信機構に固有のものとして扱われる。したがって、アドホックルーティングアルゴリズムは使用されない。リアルタイム要件を持つアプリケーションのような他のアプリケーションが含まれている場合、将来の段階がアドホックルーティングを組み込んでいてもよい。
【００５４】
ＤＤＰＤＳを使用する定量的有利性の実証を以下に続けて説明する。この例は、ＡＣＥＲＴノードの１つ、すなわちノードＡでのデータ保存および送信に焦点を当てている。ノードＡにおいて、上記テーブル１のクラス１０００、１００１，．．．，１１１０、およびクラス８から１４までは、ＦＩＦＯバッファとしてモデル化することができる。ＡＣＥＲＴ環境では、接続可能性および結果的に生じたチャネル速度が不確実であるため、各ノードにおけるＦＩＦＯバッファは、送信されるのを待っているデータを各々持っていると予期される。
【００５５】
本発明の発見的な算出では、すべてのチャネル速度は時間間隔ごとに４つの単位であると仮定する。以下の２つの戦略が比較される。
【００５６】
戦略Ｉ：上で説明したエピデミックアルゴリズムおよび関連するゴシップ（Ｇｏｓｓｉｐ）手法に密接に関係があるとみなせるこの手法では、各ノードは、例えば、ノードＡがノードＣを選択するように無作為に他のノードを選ぶ。ノードＡは、ノードＣが持つ該ノードＡのデータが欠落している部分を決定し、欠落した部分を取得するためにノードＡとノードＣとの間でセッションを開始する。ゴシップ手法では、欠落データの交換はノードＡとノードＣとの間のユニキャストであるが、該モデルは拡張することができ、他のノードがデータを盗聴するのを可能にする。例えば、ノードＢが８０２．１１のブロードキャストによりノードＡとうわさ話（Gossip）をすることを考えてみよう。ノードＢはノードＡが持つ欠落データを見つけ出すので、ノードＢはノードＡから欠落データを取り出す。ノードＡがノードＢに送信するデータは、クラス１０００、１００１、１０１０、および１０１１に対応するデータと考えることができる。なお、この手法はクラスを明確に採用しているわけではないが、該クラスはここで以下の戦略ＩＩとの比較に使用されることに留意されたい。ノードＣおよびノードＤがノードＢと同時にうわさ話（Gossip）をするとき、該ノードＣおよびノードＤによって選択されたクラスを図８に示している。
【００５７】
各ノード（Ａ、Ｃ、Ｄ）はＢの欠落データを送信することしか気にかけないので、図８の陰影付きの円によって識別されるように、これらのノードからのブロードキャストデータの中には重複するものもある。この冗長性を考慮に入れると、総利得点数は、図８のすべてのクラスにおけるゼロの数を計数して、冗長なるがゆえに陰影が付けられた円内のゼロの数を差し引くことにより、算出することができる。総利得点数は１６ユニットである。
【００５８】
戦略ＩＩ（ＤＤＰＤＳ）：この手法では、各ノードは他のすべてのノードのユーザダイジェストを知っており、データ配信クラスに従ってデータを編成する。比較のために、本発明では、ノードＡ、Ｃ、およびＤの各々が４ユニットのデータを送信した場合の利得も算出する。戦略Iとの相違は、各ノードが単にデータを特定ノードに送信しないだけでなく、クラスが全体的な利得の増加を最大にするように選択されていることである。ＤＤＰＤＳは、仲裁システムも使用して、データの冗長性が最小限になることを確保する。
【００５９】
図９に示すようにクラスが選択されているとすると、利得の合計ユニットは、選択された陰影付きクラスのゼロの数の加重和を計数することにより算出でき、ここで該加重は、３０単位になる該特定のクラスに対して選ばれたデータユニットの数である。これは戦略Ｉより５０パーセント以上優れている。
【００６０】
上述のように、段階１のＡＣＥＲＴ環境では、各ノードは約１．４ｍ／ｓの速さで移動している。段階１に使用された８０２．１１の無線リンクは、数十メートルの範囲を持っている。１００ｍ×１００ｍのグリッドについては、接続トポロジーがほぼ数秒または数十秒程度で変化すると期待される。これは、優先度の更新比率に対するシステム要件と直接関連した、重要なシステムパラメータである。
【００６１】
本発明を特定の実施形態で説明したが、本発明は、そのような実施形態により限定されるものとして解釈されるべきではなく、むしろ以下の請求項に従って解釈されるべきであることが理解されるべきであろう。
【００６２】
（関連出願の相互参照）
本発明は、２００６年１１月２７日出願の米国仮特許出願番号第６０／８６１，１６１号の利益を主張し、その全内容および開示は参照によりここに組み込まれている。
（政府特許使用権）
本発明は、国防総省国防高等研究事業局（ＤＡＲＰＡ:Defense Advanced Research Projects Agency）によって与えられた契約ＮＢＣＨＣ０５０１６１の下に、米国政府支援によって行われた。米国政府は本発明において特定の権利を有している。
【図１】
2010511324.tif 000009
【図２】
2010511324.tif 000010
【図３】
2010511324.tif 000011
【図４】
2010511324.tif 000012
【図５】
2010511324.tif 000013
【図６】
2010511324.tif 000014
【図７】
2010511324.tif 000015
【図８】
2010511324.tif 000016
【図９】
2010511324.tif 000017
【国際調査報告】
2010511324.tif 000018