(57)【要約】      （修正有）【課題】保証された最小の遅延量を有するルートを求めるルーティング方法。【解決手段】ネットワークにおいて、パケットを送信元ノードから中継ノードを介して宛先ノードに配信する最適ルートを求める。エッジによって接続されるノードのグラフは、ネットワーク内の可能なルートを表す。パケットが期限時間前に宛先に到着する確率が各エッジに割り当てられる。可能なルートから最小遅延ルートが選択され、当該最小遅延ルートを使用してパケットを配信する場合の到着時間が求められる。到着時間は期限時間と比較され、それに従って、最小遅延ルートが最適ルートとなるまで確率がスケーリングされる。【選択図】図３
2010130685.tif 000002
【特許請求の範囲】
【請求項１】
パケットを送信元ノードから中継ノードを介して宛先ノードに配信するための最適ルートを求める方法であって、
前記送信元ノードからの前記中継ノードを介する前記宛先ノードへの可能なルートを表すエッジによって接続されるノードのグラフを構築することであって、各エッジは２つのノード間のチャネルを表すこと、
前記パケットが前記宛先に期限時間前に到着する独立した確率を各エッジに割り当てること、
前記グラフ内の可能なルートから、最小遅延ルートを選択すること、
前記最小遅延ルートを使用して前記パケットを配信する場合の到着時間を求めること、
前記到着時間と前記期限時間及び所定の少量の時間εとを比較すること、
前記到着時間＞ｔ＋εの場合、前記確率をスケールダウンすると共に前記選択するステップから開始して繰り返すこと、
前記到着時間＜ｔ−εの場合、前記確率をスケールアップすると共に前記選択するステップから開始して繰り返すこと、及び、それ以外の場合、
前記最小遅延ルートを前記最適ルートとすること
を含む、方法。
【請求項２】
前記ノードはアドホック無線通信ネットワークにおける送受信機を表し、前記エッジは前記送受信機を接続するチャネルを表す、請求項１に記載の方法。
【請求項３】
前記確率は、ランダムに変化するチャネルに起因する、請求項１に記載の方法。
【請求項４】
前記確率は、前記チャネルの平均チャネル状態情報に基づく、請求項１に記載の方法。
【請求項５】
前記パケットが時間通りに到着する確率を最大にすることをさらに含む、請求項１に記載の方法。
【請求項６】
前記時間通りの到着の確率に対し畳み込みのない下界を提供することをさらに含み、前記最適ルートは前記下界を最大にする、請求項１に記載の方法。
【請求項７】
前記独立した確率の分布は、無限平均及び無限分散を有すると共に、準指数関数である、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、無線通信ネットワークにおいて、送信元から宛先への最小の遅延を有するルートを求めることに関し、より詳細には、無線アドホックネットワークにおいて、確率的遅延保証を有するルートに沿ってパケットをルーティングすることに関する。
【背景技術】
【０００２】
最適ルートを求めることは、多くの実際的な輸送、計画、及び通信の用途において頻繁に発生する問題である。本発明が特に対象とするのは、最適条件が遅延の観点から確定されるケースである。たとえば、輸送・配送システムでは、送信元から宛先まで多くの可能な代替ルートが存在する場合がある。パケットを、保証された最小の遅延量を有するルートに沿って送信元から宛先へ配信することが望ましい。
【０００３】
計画用途又は製造用途において、タスク又は組立てプロセスは、開始（ソース）から終了（目的）までに複数の選択可能な中間ステップを伴う場合がある。保証された遅延量でタスクを完了するか又は部分を組み立てることが望ましい。
【０００４】
通信用途において、データパケットを、最小の遅延量を有するルートに沿って送信元から宛先へ配信することが必要となる場合がある。物理的な長さの観点からの最短ルートが常に最速のルートであるとは限らない場合があるため、最小遅延は、より一般的な「最短」ルート問題と区別されることに留意されたい。
【０００５】
以下において、一例の用途として無線通信ネットワークが使用される。しかしながら、本発明を、上述したように他の多くのタイプのルーティング用途において機能させることができることが理解される。
【０００６】
独立基本サービスセット（ＩＢＳＳ）としても既知である無線アドホックネットワークは、ノード、たとえばユーザ端末、局、送受信機間の通信チャネルが無線であるネットワークである。ネットワークのトポロジ及びルーティングは任意であるためネットワークはアドホックであり、任意のノードが他のノードにパケットを転送することができる。ノードがデータパケットを転送するために使用するルートの決定は、ネットワーク接続性及びチャネル状態に基づいて動的に行われる。
【０００７】
無線アドホックネットワークは、ネットワークのノード間の信頼度の高い接続性を達成することができる。典型的には、すべてのノードが同様の構造及び機能を有する。ノードは通常電池式であり、パケットは、ノードを接続する無線チャネルを使用して、送信元ノードから１組の中間中継ノードを介して宛先ノードへ転送される。
【０００８】
構造化されていない無線アドホックネットワークは、インターネット及びセルラネットワークのような従来の構造化されたネットワークを上回る多数の利点を有する。無線アドホックネットワークは、基地局、無線バックボーン、及びパケットをルーティングするように特に設計されたルータのような固定のインフラストラクチャを必要としない。これによってコストを削減することができる。信号を様々な選択可能なルートを介して送信することができるため、信頼性が向上する。中間中継ノードがより信頼度の高いチャネルを介して信号を受信及び再送信することができるため、エネルギー消費を減少させることができる。伝送される全エネルギーが減少するため、ネットワーク寿命が増加し、干渉が減ると共に、スペクトル効率が改善される。アドホックネットワークは電池式送受信機の場合に特に有利である。
【０００９】
この理由によって、アドホックネットワークは、緊急対応、環境データ収集、ファクトリーオートメーション、セキュリティ、及び軍事の用途のために頻繁に使用される。
【００１０】
多くの用途において、アドホックネットワークはサービス品質（ＱｏＳ）の保証を提供しなくてはならない。ＱｏＳの１つの指標は、パケットを送信元ノードから宛先ノードへ送信する間に発生する遅延量である。たとえばアドホックセンサネットワークにおいて、１台の機械が過熱しているか又は他の様態で機能不良であることを示すパケットは、機械が機能を停止してより広範囲の損害を生じさせる前に、制御センターに配信されなくてはならない。
【００１１】
無線アドホックネットワークにおけるＱｏＳは、ノードの承認、ネットワークプロトコルの上位層からのパケットの到着統計、スケジューリングメカニズム及びマルチアクセスメカニズム、物理層伝送のプロパティ、並びにルーティングを含む、様々な要素によって影響を受ける。
【００１２】
これらのすべての変動に起因して、特に物理層における変動に起因して、パケットが期限より前に宛先に到着するという完全な保証を与えることは不可能である。すべてのチャネル実現の或る特定の百分率、たとえば９９％においてパケットが時間内に到着するということを保証することのみが可能である。この概念は、セルラネットワークの「故障確率」と性質が同様である。「故障確率」は、移動局が基地局と通信するのに十分な信号電力を受信しない確率を定義する。
【００１３】
これより、時間通りに到着する確率を「確率的保証」とする。送信元のランダムなパケット到着に起因する遅延の確率論的変動は、従来技術において広範に説明されてきたが、ランダムに変化するチャネルに起因する送信時間のランダムな変動はそうではない。
【００１４】
ルーティングは、無線アドホックネットワークにおけるＱｏＳにとって特に重要である。ルーティングは、送信元から宛先へパケットを転送するのに使用される中継ノードを決定する。典型的には、ルートは「発見」され、結果がルーティングテーブルに記憶される。特定のＱｏＳ制約、たとえば遅延を満たすルートは記憶され、このルートが「ブレーク」する、すなわち、ＱｏＳ制約が違反されるまで維持される。
【００１５】
ルート発見方法は、通常、フラッディング、ジオメトリ、又はステートフルとして分類することができる。フラッディング又は「ゴシッピング」によって、パケットは送信元からすべてのノード又はランダムに選択されたノードに送信される。この技法は、ノードがネットワークトポロジ又はチャネル状態情報（ＣＳＩ）を知っていることを一切必要としないが、多数のノードが関わるため、エネルギー効率が悪い。
【００１６】
ジオメトリベースのルーティングでは、最適ルートは、ノードの位置の知識に基づいて、集中型又は分散型で決定される。しかしながらノード間の距離は必ずしも伝播状態及び遅延状態を反映しない。したがって、ジオメトリベースの技法すなわち最短ルートベースの技法によって、遅延の観点から準最適なルートがもたらされる場合がある。
【００１７】
ステートフルルーティングでは、ルーティングは瞬時ＣＳＩに基づく。この分類では、最適ルートはノード間のすべての無線チャネルの瞬時ＣＳＩの全体知識又は分散知識から決定される。瞬時ＣＳＩに基づくルート発見は、多くの通信用途の場合に実際的ではない。無線チャネルの状態は、特にノードが可動である場合、連続的に変化する可能性がある。無線チャネルの典型的なコヒーレンス時間は約数ミリ秒である。その結果、ネットワーク全体にわたってＣＳＩを頻繁に更新することによって、許容不可能なオーバヘッドがもたらされる。
【００１８】
大規模ネットワークでは、すべての可能なノードに関するルーティング情報を通信することのオーバヘッドによって、ネットワークのスペクトル効率が減少し、電力が消費される。大規模ネットワークにおけるオンデマンドのルート発見も、ルート発見プロセスが多くの場合、許容される遅延よりも長い時間を要するため、実際的ではない。
【発明の概要】
【発明が解決しようとする課題】
【００１９】
したがって、上記の問題のうちのいかなるものも有せず、且つ保証された最小の遅延量を有するルートを求めることができるルーティング方法を提供することが所望されている。
【課題を解決するための手段】
【００２０】
本発明の実施の形態は、送信元から宛先への保証された最小の遅延量を有するルートを求める方法を提供する。より詳細には、本方法は、パケットを、当該パケットが宛先に所定の期限内に到着するように或るルートに沿って送信元から宛先へ送信することができるように、アドホック無線ネットワークにおいてルートを発見する。本方法を、他の多くの実際的なルーティング用途において機能させることができることが理解される。
【００２１】
本発明の実施の形態は、チャネル状態情報（ＣＳＩ）の平均のみを使用してルートを特定する。平均ＣＳＩは経時的に非常に低速に変化し、それによって、平均ＣＳＩを過度のオーバヘッドなしにネットワークを通じて通信することができる。本発明は、平均ＣＳＩを使用して、パケットが時間通りに到着する確率を求める。したがって、本発明は確率的遅延保証を可能にする。すなわち、本発明は、パケットが時間通りに到着する確率を最大にする。
【００２２】
本発明は、パケットが時間通りに到着する確率に対し畳み込みのない下界を提供し、この下界を最大にするルートを特定する。
【００２３】
本発明の背後にある着想は、或る種類の無限分散の準指数分布によって動機付けされている。これらの分布は、偏差制限及び畳み込み方式の使用を妨げる特性を有する。下界は、確率的最小遅延保証をもたらすルートを求める方法の基礎を成す。最小遅延方法は、従来の最短ルートルーティング方法よりも良好に働く。
【００２４】
本発明によるルーティングは、ＣＳＩの統計、たとえば平均ＣＳＩのみに基づく。そのようなルーティングは、確率的最小遅延保証を提供することができる。従来技術の発見的なルーティング方法と対照的に、本発明のルーティング方法は、時間通りの配信の確率の下界を最大にする。
【発明の効果】
【００２５】
本発明は、確率的遅延保証を用いてネットワークにおいてルーティングする方法を提供する。本発明は、フラッディングと、ネットワークにおける瞬時ＣＳＩに基づく最適ルーティングとの間の妥協点を提供する。フラッディングはＣＳＩの交換を必要としないが過度にエネルギー効率が悪く、ネットワークにおける瞬時ＣＳＩに基づく最適ルーティングは、ルート発見のための大きなオーバヘッド及びルーティングテーブルの維持管理を必要とする場合がある。
【００２６】
本発明の実施の形態は、パケットを送信元から宛先へ配信するのに使用されるチャネルの平均信頼度に従ってルーティングを行う。無線通信ネットワークでは、平均信頼度はＣＳＩに基づくことができる。ＣＳＩはごく稀にのみ、たとえばノードがネットワークに入るか若しくはネットワークを出るとき、又は選択されたルートがもはや時間通りの配信の保証を満たしていないことが検出されるときにのみ更新される。
【００２７】
この正確度が低減されたＣＳＩを用いてもなお、確率論的遅延保証を提供すること、すなわち、パケットが、最大にされた下界によって与えられるケースの百分率において時間通りに配信されることを確実にすることが可能である。
【００２８】
本発明者らは、遅延要件を最も多くの場合に満たすルートを特定する、新規の、さらに非常に効果的な方法を提供する。本方法は発見的ではなく、成功確率に対する下界に関する分析的証拠に基づく。本方法は、レイリーフェージングチャネルにおいて遅延保証を与えるルートを求める。
【００２９】
実際のところ、本方法は汎用的であり、多岐にわたる他の用途において使用することができる。何よりもまず、本方法はライス、仲上等のような任意のフェージング分布に対して有効である。実際のセンサネットワークにおいて様々なフェージング分布が発生し得るため、このように簡単に一般化可能であることは重要である。本方法は、ＣＳＩが真の平均ではなく、単に或る雑音混じりの推定値又は古い推定値である場合にも、信頼度測定の累積分布関数が知られている限り使用することができる。
【００３０】
本発明の実施例において、理想的に符号化されたシステムのチャネルごとの伝送遅延が使用されるが、ルーティング方法はこの仮定に依存しない。
【００３１】
さらに、ＱｏＳ要件を伝送遅延に制限する必要はない。たとえば付加的な、任意のＱｏＳ凸制約も本方法の基礎を成すことができる。エッジコストのＰＤＦが独立でなくてはならないという制限も取り除くことができる。
【００３２】
代替的な手法は、ノード間の接続のみを許可し、それによって、「接続された」ノードのいかなる対間の平均チャネル利得も要求される最小遅延を超えるようにする。サイズが知られているパケットは、特定の変調の場合に或る所定の低誤り確率で受信することができる。そして、同じ変調をすべてのホップに対して使用することができ、「時間」要件は「ホップ数」要件になる。１つの高速チャネルが別の低速チャネルの遅延を補償することができる本方法が遅延保証を満たすルートを決定することができる一方、「ホップ数」方法は失敗する多くの状況が存在する。
【図面の簡単な説明】
【００３３】
【図１】本発明の実施の形態による無線アドホックの図である。
【図２】本発明の実施の形態による無線アドホックの図である。
【図３】本発明の実施の形態によるネットワークのグラフである。
【図４Ａ】時間通りのイベントの確率に対する凸下界及び凸上界のグラフである。
【図４Ｂ】時間通りのイベントの確率に対する準凸下界及び準凸上界のグラフである。
【図５】本発明の一実施の形態によるルートを求める方法のフロー図である。
【発明を実施するための形態】
【００３４】
図１及び図２は、本発明の実施の形態による無線アドホックネットワーク１００及び２００を示す。ネットワーク１００は、送信元ノード１１１、すなわち送信元と、１組の中継ノード１２１〜１２４、すなわち中継と、宛先ノード１３１、すなわち宛先とを含むｋ個のノードを備える。ノードは、無線チャネル１１５によって接続されている。無線チャネル１１５は、本明細書において代替的にホップと呼ばれる。
【００３５】
本発明の実施の形態はまた、図２に示すように複数の中継「チャネル」を用いて使用することもできることを理解されたい。この場合、中継１２５は「中間」中継１２６のための「送信元」としての役割も果たす。この方式は追加のホップに拡張することができる。
【００３６】
一般性を損なうことなく、図３に示すように、図１及び図２のネットワークを全体的に、エッジＥ３０４によって接続されるＫ個のランダムに配置されたノード又は頂点Ｖ  ３０１〜３０３を有する確率論的グラフＧ３００、すなわちＧ（Ｖ，Ｅ）として表すことができる。通信ネットワークでは、ノードは送受信機又はセンサとすることができ、ノード間のエッジはチャネル１１５を表す。ノードは、送信元ノード３０１と、中継ノード３０２と、宛先ノード３０３とを含む。
【００３７】
製造用途又は計画用途において、ノードは開始及び終了を有するタスクを表すことができ、エッジはプロセスである。輸送用途では、ノードは出発場所、中間停留地、及び最終目的地であり、エッジは道路、空路、又は海路である。このように、本発明のネットワーク、ノード、エッジ、チャネル等の使用を一般化して、多岐にわたるルーティング用途に対して意味のあるものとする。
【００３８】
本発明では、ノード間のエッジにおける遅延３１０に注意を集中する。遅延は、チャネル状態で表されるように、ノードを接続するチャネルの信頼度に起因し得る。瞬時チャネル状態の測定は時間を要する可能性があるため、本発明では平均チャネル状態の測定を使用する。
【００３９】
通信ネットワークにおいて、信頼度の１つの測定は、チャネル状態情報（ＣＳＩ）に基づく。ＣＳＩはパケットを配信するのに使用することができるデータレートに直接影響を及ぼす。雑音が多いか又は信頼できないチャネルにおいて、パケットを、より低いデータレートで、より非常に長い誤り訂正符号を用いて、反復して再送信する必要がある場合がある。これは遅延を増大させる。他の用途の場合、信頼度及び遅延は、道路、交通量、又は天候状態に応じて決まり得る。製造において、信頼度はノード又はタスクに関連付けられる中間処理ステップに割り当てることができる。
【００４０】
本発明の通信ネットワークにおいて、ノードにおけるキューイング遅延は無視される。さらに、本発明では単一のパケットしか考察せず、（他の送信機及び受信機間の）他のパケットは直交チャネルで送信されると推定する。したがって、干渉は役割を果たさない。
【００４１】
ｉ番目のエッジ（チャネル）に沿う伝播減衰の逆数である電力利得はγｉである。電力利得の確率密度関数（ＰＤＦ）はｆ（γｉ）である。個々のチャネルの利得のＰＤＦは独立していると推定する。通信ネットワークに関して以下の説明をより明確にするために、チャネルはレイリーフェージングを受ける、すなわちγｉのＰＤＦは、
【００４２】
【数１】
2010130685.tif 000003
【００４３】
であると推定する。式中、γｉ上のバーは平均チャネル利得を示す。ネットワークにおける平均チャネル利得は非常に低速で変化すると共に、ネットワーク全体で利用可能であると推定する。パケットは理想的な物理層伝送によるマルチホップ中継によって、ネットワーク全体にわたって通信される。換言すると、各チャネルにおいて、伝送はチャネル容量で行われ、それによって、チャネルｉにおける、ソースエントロピーＨｔａｒｇｅｔを有するパケットの場合の伝送時間は以下となる。
【００４４】
【数２】
2010130685.tif 000004
【００４５】
チャネルはレイリーフェージングであるため、１つのチャネルにわたる伝送遅延のＰＤＦは以下である。
【００４６】
【数３】
2010130685.tif 000005
【００４７】
この分布は無限平均及び無限分散を有する。この分布は準指数関数でもある。確率論において、裾の重い分布とは、裾が指数的に制限されていない確率分布である。すなわち、この分布は指数分布よりも重い裾を有する。本発明の用途では、分布の右裾を対象とする。
【００４８】
主要な特性は、独立同一分布（ｉ．ｉ．ｄ．）準指数変数の和は、おそらく単一の変数によって支配されるということである。したがって、任意のサンプルが過度に大きな値を取り得る。準指数変数は、従来の確率推論方法に逆らう幾つかの他の特性を有すると共に、確率論的遅延保証を用いて最適ルーティングを求める場合に特殊な問題を生じさせる。本発明の方法の注目すべき特性は、本方法が、これらの極度に難しい分布の場合であっても機能するということである。
【００４９】
チャネル容量は複数の異なる方法によってほぼ達成することができる。瞬時ＣＳＩが送信ノードにおいて知られている場合、特定のＳＮＲに対して準（near）容量達成誤り訂正符号、たとえばターボ符号、又は低密度パリティチェック（ＬＤＰＣ）符号を使用することができる。ＣＳＩの知識は送信ノードにおいてローカルにありさえすればよい。瞬時ＣＳＩをネットワークにわたって知る必要は一切ない。瞬時ＣＳＩが知られていない場合、レートレス符号を使用することができる。
【００５０】
本発明の課題は、ルート遅延がもはや所定の時間閾値ｔを超えないすべてのチャネル状態の百分率を最大にするルートを特定することである。
【００５１】
複数のランダム変数を伴う事象の確率を、特に積分が実行不可能であるときに最適化する枠組みを説明する。積分が実行不可能であることによって、畳み込み又は積率を推論することが不可能になる。その結果、宛先にパケットが時間通りに到着する確率に対し、分布から独立した下界が生じる。
【００５２】
この下界を避ける統計的ルーティング方法を説明し、時間通りのパケット到着の確率に対し上界及び下界を与えると共に、本方法が下界を最大にすることを示す。
【００５３】
Ｘｉをランダム変数とし、ｘｉをＸｉの実現とする。１組のランダム変数Ｘ１，．．．，Ｘｎについて、Ｅ：ｘ１，．．．，ｘｎ→{０，１}を、対象となる事象を
【００５４】
【数４】
2010130685.tif 000006
【００５５】
の多面体として定義する不等式とする。本発明の用途では、事象は宛先におけるパケットの時間通りの配信であり、或る時間期限ｔ＞０について、Ｅ：Σｉｘｉ≦ｔとして表される。各事象Ｘｉは非負値の実数の連続したサブセットに対する非消滅のサポート（nonvanishing support）を有し、それによって事象Ｅは
【００５６】
【数５】
2010130685.tif 000007
【００５７】
において閉集合となると推定する。これらの状態は式（３）の分布の場合、及び他の多くの実際に関連する分布の場合に満たされる。
【００５８】
単位超立方体への非線形確率マップ
【００５９】
【数６】
2010130685.tif 000008
【００６０】
を考察する。これは確率ベクトル（Ｆ１（ｘ１），．．．，Ｆｎ（ｘｎ））に任意の実現（ｘ１，．．．，ｘｉ）を用いることによって定義され、ここで、Ｆｉ（ｘ）はＰｒ（Ｘｉ≦ｘｉ）として定義される。確率マップＰを事象多面体Ｅに適用することによって、境界Ｐ（∂Ｅ）が典型的な曲線状である超立体領域Ｐ（Ｅ）がもたらされる。確率マップＰの有意性は、確率が超立方体内で均一であるということである。したがって、領域Ｐ（Ｅ）の容積（content）（超体積）は、正確に事象Ｅの確率である。したがって、Ｐｒ（Ｅ）＝ｖｏｌ  Ｐ（Ｅ）と最適化する。ほとんどの分布において、この体積を与える積分を評価することができないため、事象の確率Ｐｒ（Ｅ）に対する、分布から独立した下界が探索される。
【００６１】
定義１
超立方体領域Ｐ（Ｅ）が凸集合である場合、Ｅは１組のランダム変数Ｘ１，Ｘ２，．．．，Ｘｎに関して凸事象である。
【００６２】
事象Ｅが
【００６３】
【数７】
2010130685.tif 000009
【００６４】
において凸である場合、領域Ｐ（Ｅ）は凸であり、ｔ≧０の場合の各累積分布関数（ＣＤＦ）Ｐｒ（Ｘｉ≦ｔ）は凹である。凹ＣＤＦは、ＰＤＦが非増加性であることを意味する。これは制限的過ぎる場合がある。凹ＣＤＦで開始するが、最終的に遥かに広いクラスの密度、すなわち非増加性の右裾を有する密度に関して界を展開する。
【００６５】
事象Ｅが凸事象であること、及び境界Ｐ（∂Ｅ）上の点の位置の知識のみで、多面体をＰ（Ｅ）内に密に適合させることによって界を構築する。
【００６６】
図４Ａ及び図４Ｂは、２つの可変事象Ｐｒ（Ｘ≦ｚ）及びＰｒ（Ｙ≦ｚ）の確率に対する、ダイヤモンド型の上界及び下界を視覚化する。曲線下面積は、事象ｖｏｌＡ≦ｖｏｌＥ＝Ｐｒ（Ｘ＋Ｙ≦ｔ）≦ｖｏｌＢとなる確率である。界が調整される事象は、図４Ａでは凸であり、図４Ｂでは準凸である。
【００６７】
各ＣＤＦは
【００６８】
【数８】
2010130685.tif 000010
【００６９】
に対しサポートを有し、それによって、境界が、原点と隣接する各超立方体頂点ｅ１，．．．，ｅｎと接触すると推定する。境界上で或る点ｐ∈Ｐ（∂Ｅ）を選択する。最初に、原点からの射線１＝（１，１，・・・，１）が境界とぶつかる点であるｐ＝ｐ１を選択する。
【００７０】
補助定理１：単純なダイヤモンド型多面体界
Ｐｒ（Ｅ）≧１／ｄ！（１＋ｑ√ｄ）であり、式中、ｄ≦ｎは、事象に関与しているランダム変数の数であり、ｑ＝ｐｄ１／２−１である。すべての証明は付録内にある。
【００７１】
ダイヤモンド型多面体は、点
【００７２】
【数９】
2010130685.tif 000011
【００７３】
にわたると共に、{ｅ１，．．．，ｅｎ}にわたる共有小単体（shared subsimplex）において結合される、２つの単体を含む。実際には、幾つかの変数について、Ｐｒ（Ｘｉ＞ｔ）＞０であるため、領域Ｐ（Ｅ）は超立方体の角ｅ１，ｅ２，．．．に到達しない場合がある。たとえば、特定のチャネルにおけるチャネル利得が低すぎる場合、この信号チャネルを介する送信は、既に許容される遅延時間を超えている。
【００７４】
ｍｉを、事象Ｅによって許容されるＸｉの最大の実現のＣＤＦ値であるｍａｘｘＰｒ（Ｘｉ≦ｘ｜Ｅ）として定義する。時間通りの配信の確率に対する下界は以下のように一般化される。
【００７５】
補助定理２：ダイヤモンド（多面体）界、凸分布
【００７６】
【数１０】
2010130685.tif 000012
【００７７】
式中、ｄ≦ｎは事象に関与しているランダム変数の数であり、ｚｉ＝ｍｉ−１である
【００７８】
【数１１】
2010130685.tif 000013
【００７９】
であり、任意のポイント
【００８０】
【数１２】
2010130685.tif 000014
【００８１】
である。証明に関しては付録を参照されたい。
【００８２】
多くのルーティング問題において、自然分布関数（natural distribution function）は凸事象をもたらさない。Ｐ（Ｅ）の凸の副体積を特定することによって、そのような事象まで下界を拡張する。
【００８３】
定理１：ダイヤモンド界、全体分布
確率Ｆｊの凹ベクトルの場合にｃｊ＝０とし、そうでない場合、以下となる。
【００８４】
【数１３】
2010130685.tif 000015
【００８５】
すなわち、ＸｊのＣＤＦが屈曲し且つ事象Ｅが可能である、最大サンプル値である。
【００８６】
事象Ｅが凸である場合、各確率関数ｆｉ（ｘ）＝Ｆｉ’（ｘ）は右裾において非増加性である。そして、
【００８７】
【数１４】
2010130685.tif 000016
【００８８】
であり、凸界は、ｍｉが、Ｘｊ＝ｃｊ，Ｘｋ＝ｃｋ，．．．であるときにＥを満たすＸｉの可能な最大値の確率に設定された状態を維持する。たとえば、事象Ｅ：Σｉｘｉ≦ｔ、すなわちパケットを時間通りに配信する場合、ｍｉ＝ｍａｘＰｒ（Ｘｉ＋（ｍａｘｘｊ≠ｉｃｊ）≦ｔ）である。証明は付録内にある。
【００８９】
ルーティング方法
グラフＧ＝（Ｖ，Ｅ）３００を使用する確率論的ルーティングにおいて、本発明は、組合わせの数の、可能なルートを有する。本発明者らは、各送信元−宛先ルート
【００９０】
【数１５】
2010130685.tif 000017
【００９１】
に関して、時間通りの到着の事象
【００９２】
【数１６】
2010130685.tif 000018
【００９３】
に関心を有する。
【００９４】
本発明の目的は、事象
【００９５】
【数１７】
2010130685.tif 000019
【００９６】
の確率を最大にするルート
【００９７】
【数１８】
2010130685.tif 000020
【００９８】
を求めることである。ほとんどの分布に関して、この問題はＮＰ困難であり、場合によっては近似可能でない。式（３）のＰＤＦの場合、単一のルート
【００９９】
【数１９】
2010130685.tif 000021
【０１００】
に関して、
【０１０１】
【数２０】
2010130685.tif 000022
【０１０２】
を数値的に近似することさえ困難であり得る。
【０１０３】
しかしながら、本発明は、上述したように遅延に対する下界を最大にするルートを求めることができる。そうするために、本発明では、ベクトル
【０１０４】
【数２１】
2010130685.tif 000023
【０１０５】
に沿って、すべての事象
【０１０６】
【数２２】
2010130685.tif 000024
【０１０７】
の和集合の境界上の点
【０１０８】
【数２３】
2010130685.tif 000025
【０１０９】
を検索する。ここで、ベクトルはエッジ確率の集まりである：
ベクトル
【０１１０】
【数２４】
2010130685.tif 000026
【０１１１】
に沿って二等分点
【０１１２】
【数２５】
2010130685.tif 000027
【０１１３】
を選択する。
各エッジのランダム変数Ｘｉについて、
【０１１４】
【数２６】
2010130685.tif 000028
【０１１５】
を満たす
【０１１６】
サンプル値
【０１１７】
【数２７】
2010130685.tif 000029
を求める。
【０１１８】
ｘ１，．．．，ｍ，．．．，ｘｎに関して、
【０１１９】
【数２８】
2010130685.tif 000030
【０１２０】
における最小遅延ルート
【０１２１】
【数２９】
2010130685.tif 000031
【０１２２】
を選択する。
Σｉｘｉ＞ｔ＋εである場合、ベクトルを二等分することによって確率を
【０１２３】
【数３０】
2010130685.tif 000032
【０１２４】
に近づけてスケールダウンすると共に、ステップ３から開始して繰り返す。
【０１２５】
Σｉｘｉ＜ｔ−εである場合、ベクトルを二等分することによって確率を
【０１２６】
【数３１】
2010130685.tif 000033
【０１２７】
から遠ざけてスケールアップすると共に、ステップ３から開始して繰り返す。
それ以外の場合、最小遅延ルートを最適ルートとする。
【０１２８】
概括的な方法
図５は、パケットを送信元ノードから中継ノードを介して宛先ノードへ期限時間までに配信する最適ルートを求める方法を示す。グラフ３００を構築する（５１０）。グラフにおいてノードは、１つの送信元、１つ又は複数の中継、及び１つの宛先を表す。ノードはエッジによって接続される。各エッジに、パケットが期限時間までに宛先に配信される独立した確率を割り当てる（５２０）。
【０１２９】
最小遅延ルートを選択する（５３０）。到着時間と期限時間及び所定の少量の時間εとを比較し（５４０）、到着時間＞ｔ＋ε  ５５０である場合、確率をスケールダウンし（５５５）、選択ステップから開始して繰り返し、到着時間＜ｔ−ε  ５６０である場合、確率をスケールアップし（５６５）、選択ステップから開始して繰り返し、それ以外の場合５７０、最小遅延ルートを最適ルートとする（５７５）。
【０１３０】
特定される遅延保証されたルートの特性
検索ベクトルが
【０１３１】
【数３２】
2010130685.tif 000034
【０１３２】
である場合、
【０１３３】
【数３３】
2010130685.tif 000035
【０１３４】
において選択されるルート
【０１３５】
【数３４】
2010130685.tif 000036
【０１３６】
は、以下の意味において、任意の単一のエッジの長さのランダムな再サンプリングを受けることができる（amenable）。
【０１３７】
命題１：
単一エッジの再サンプリングの下では、選択されたルートは、いかなる他のルートよりも時間通りに到着する事象Ｅを満たす可能性が高い。証明は付録内にある。
【０１３８】
２つ以上のエッジを再描画する場合、そのような保証は一切可能ではない。これは、Ｐｒ（Ｘｉ≦Ｘｉ）＝ｐ、且つＰｒ（Ｘｊ≦ｘｊ）＝ｐであってもなお、分布関数の非線形性に起因して、
Ｐｒ（Ｘｉ＋ｊ≦ｘｉ＋ｘｊ）＞＞ｐ
が可能であるためである。これは、いかなる他のルートよりも選択されたルートを所望する可能性が高い。
【０１３９】
定理２：
点
【０１４０】
【数３５】
2010130685.tif 000037
【０１４１】
において選択されたルートは、時間通りに到着する確率に対する凸下界を最大にする。証明に関しては付録を参照されたい。
【０１４２】
プロシージャは遅延分布の代理として分位点を使用し、本発明の「期限の下でのルーティング（routing-under-a-deadline）」タスクに関して最良の分位点の組を検索する。以下の説明によって、等確率の分位点（ｖ＝１）が何故最も有益であるのかに関する幾らかの洞察が与えられる。
【０１４３】
定義２：
点
【０１４４】
【数３６】
2010130685.tif 000038
【０１４５】
におけるルートＱ
【０１４６】
の事象影（event shadow）
【０１４７】
【数３７】
2010130685.tif 000039
【０１４８】
は、ｑｉ≧ｑｉであるすべての点の集合
【０１４９】
【数３８】
2010130685.tif 000040
【０１５０】
である。
【０１５１】
ルート
【０１５２】
【数３９】
2010130685.tif 000041
【０１５３】
に関して点
【０１５４】
【数４０】
2010130685.tif 000042
【０１５５】
において、且つ他のすべてのルートに関して点
【０１５６】
【数４１】
2010130685.tif 000043
【０１５７】
の影内においてダイヤモンド型の界自体が求められる。
【０１５８】
Ｑ’ｓの事象エンベロープ（event envelope）上の或る他の点
【０１５９】
【数４２】
2010130685.tif 000044
【０１６０】
において、しかし点
【０１６１】
【数４３】
2010130685.tif 000045
【０１６２】
の影の外側において、上記界が求められる場合、当該界は、或る他のルートＱを所望し得ることが可能である。この結果は、グラフサイズに伴い、より稀になる。
【０１６３】
最大にされた上界
ここで、凸事象の確率に対する上界の構築を説明する。観測
【０１６４】
【数４４】
2010130685.tif 000046
【０１６５】
から、単純な超長方形上界
【０１６６】
【数４５】
2010130685.tif 000047
【０１６７】
が生じる。この界は、カットスルーポイント
【０１６８】
【数４６】
2010130685.tif 000048
【０１６９】
を有する超長方形の遠方角を、点
【０１７０】
【数４７】
2010130685.tif 000049
【０１７１】
において、Ｐ（∂Ｅ）の導関数が張る接線空間に沿って除去することによって輪郭をはっきりさせることができる。
【０１７２】
本発明の方法によって選択されるルート
【０１７３】
【数４８】
2010130685.tif 000050
【０１７４】
は、この上界を最大にすることができる。任意の代替ルートＱ及び点
【０１７５】
【数４９】
2010130685.tif 000051
【０１７６】
の事象影内の点
【０１７７】
【数５０】
2010130685.tif 000052
【０１７８】
に関して、境界の切断超平面に関して２つの観測を行う：
点
【０１７９】
【数５１】
2010130685.tif 000053
【０１８０】
は、点
【０１８１】
【数５２】
2010130685.tif 000054
【０１８２】
よりも
【０１８３】
【数５３】
2010130685.tif 000055
【０１８４】
に近いため、
【０１８５】
【数５４】
2010130685.tif 000056
【０１８６】
を通過する超平面はより大きな体積を除去する。
ＣＤＦ値のうちの幾つかは、ＣＤＦの凹面によって、点
【０１８７】
【数５５】
2010130685.tif 000057
【０１８８】
において低減されているため、対応するＰＤＦ値が増大し、このため、点
【０１８９】
【数５６】
2010130685.tif 000058
【０１９０】
における
【０１９１】
【数５７】
2010130685.tif 000059
【０１９２】
の導関数は、値がより広範に拡散する。これによって、点
【０１９３】
【数５８】
2010130685.tif 000060
【０１９４】
におけるＰ（∂Ｅ）の接線空間は
【０１９５】
【数５９】
2010130685.tif 000061
【０１９６】
に対し、より直交的でなくなり、それによって除去される体積のサイズも増大する。
【０１９７】
付録
補助定理１の証明
Ｐ（Ｅ）は、凸であるため、
【０１９８】
【数６０】
2010130685.tif 000062
【０１９９】
の凸包を含む。この凸包は、
【０２００】
【数６１】
2010130685.tif 000063
【０２０１】
において標準単体に分裂し、
【０２０２】
【数６２】
2010130685.tif 000064
【０２０３】
において、射線
【０２０４】
【数６３】
2010130685.tif 000065
【０２０５】
に沿って「押しつぶされた」正単体に分裂する。射線はそれらの単体の共通ファセットを、ｄ−１／２において横断する。したがって、押しつぶされた単体は高さｑ＝ｐｄ１／２−１を有する。標準単体の容積は１／ｄ！である。共通ファセットは、エッジの長さ√２を有するｄ−１次元の正単体である。したがって、その容積は以下となる。
【０２０６】
【数６４】
2010130685.tif 000066
【０２０７】
これを高さｑまで錐体に拡張することによって、容積がｑ／ｄ倍増大する。容積の合計が結果を与える。
【０２０８】
注２：
事象Ｐ（Ｅ｜Ｘｋ＝０）を含む［０，１］ｎ−１に軸合わせされた部分空間を考察する。１がこの曲線にぶつかる点ｑｋを計算する場合、
【０２０９】
【数６５】
2010130685.tif 000067
【０２１０】
の凸包内の容積は、Ｐ（Ｅ）内であるが上記で与えられた界の外側に位置し、このため、この容積を界に追加して当該界を強化することができる。
【０２１１】
補助定理２の証明
ケイリー−メンガー行列式を使用すると、下側単体の容積は
【０２１２】
【数６６】
2010130685.tif 000068
【０２１３】
であり、共有単体の容積は
【０２１４】
【数６７】
2010130685.tif 000069
【０２１５】
である。ｑの場合の数式は、任意の
【０２１６】
【数６８】
2010130685.tif 000070
【０２１７】
に対する共有単体からの直交距離である。
【０２１８】
定理１の証明
Ｐ（Ｅ）を通る任意の２次元切片、及び軸ｅｉを考察する。ここでｅｉを垂直軸と見なす。Ｅは凸であるため、境界Ｐ（∂Ｅ）を通る切片によって生成される曲線は非増加性である。
【０２１９】
【数６９】
2010130685.tif 000071
【０２２０】
をこの曲線上に位置決めすることができる場合、
【０２２１】
【数７０】
2010130685.tif 000072
【０２２２】
であるため、曲線は分布の右裾によって生成される中心セグメントを有し、これは凸でなくてはならない。
【０２２３】
このセグメントをｅｉに投影する。構造上、ｍｉは投影の上端か又は上端より下に位置する。曲線セグメントは非増加性且つ凸であるため、（０，ｍｉ）から
【０２２４】
【数７１】
2010130685.tif 000073
【０２２５】
に描画される任意の直線は全体がＰ（Ｅ）内に位置する。したがって、頂点
【０２２６】
【数７２】
2010130685.tif 000074
【０２２７】
を有する任意の（上側）単体は、Ｐ（Ｅ）内に位置する。論理の対称性により、切片がｅｊも通過する場合、（０，ｍｉ）から（ｍｊ，０）までの直線もＰ（Ｅ）内にあり、下側単体がＰ（Ｅ）内にあることを意味する。
【０２２８】
命題１の証明
構造上、選択されるルートの任意のエッジに関して、Ｅ内に留まる確率ｐを有する。任意の他のルートに関して、新たな描画は実現されるルートの長さを必ず短くするため、Ｅに入る確率は＜ｐとなる。
【０２２９】
定理２の証明
任意の選択可能なルートＱは、当該ルートのエッジの長さの或る空でないサブセットｘｉ，ｘｊ，．．．，を低減し、それによって確率Ｐｒ（Ｘｉ≦Ｘｉ），Ｐｒ（Ｘｊ≦ｘｊ），．．．を低減することによってＥに入る。ｑをＱの実現されるエッジの長さの確率のベクトル（Ｐｒ（Ｘｉ≦Ｘｉ），Ｐｒ（Ｘｊ≦ｘｊ），．．．とすると共に、ベクトル
【０２３０】
【数７３】
2010130685.tif 000075
【０２３１】
に
【０２３２】
【数７４】
2010130685.tif 000076
【０２３３】
における対応する値を含ませる。ダイヤモンド界内では、正単体の容積はサンプルポイントの、単体間の共有ファセットまでの直交距離によって求められることを想起されたい。この距離は低減され、正単体がＰの場合よりもＱの場合に、より押しつぶされる一方で、界の他の全ての要素は保存される。
【０２３４】
本発明を特定の好ましい実施の形態を参照して説明してきたが、本発明の精神及び範囲内で様々な他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。
【図１】
2010130685.tif 000077
【図２】
2010130685.tif 000078
【図３】
2010130685.tif 000079
【図４Ａ】
2010130685.tif 000080
【図４Ｂ】
2010130685.tif 000081
【図５】
2010130685.tif 000082
【外国語明細書】
2010130685.tif 000083
2010130685.tif 000084
2010130685.tif 000085
2010130685.tif 000086
2010130685.tif 000087
2010130685.tif 000088
2010130685.tif 000089
2010130685.tif 000090
2010130685.tif 000091
2010130685.tif 000092
2010130685.tif 000093
2010130685.tif 000094
2010130685.tif 000095
2010130685.tif 000096
2010130685.tif 000097
2010130685.tif 000098
2010130685.tif 000099
2010130685.tif 000100
2010130685.tif 000101
2010130685.tif 000102
2010130685.tif 000103
2010130685.tif 000104
2010130685.tif 000105
2010130685.tif 000106
2010130685.tif 000107
2010130685.tif 000108
2010130685.tif 000109
2010130685.tif 000110
2010130685.tif 000111
2010130685.tif 000112
2010130685.tif 000113
2010130685.tif 000114
2010130685.tif 000115