(57)【要約】  本発明は、少なくとも２つの通信装置を有する通信ネットワークにおける通信装置であって、装置間のコンタクトの任意のシーケンスについて、（ＬＤ（Ｌａｓｔ  Ｄｅｐａｒｔｕｒｅ），ＥＡ（Ｅａｒｌｉｅｓｔ  Ａｒｒｉｖａｌ））ペアのリストの形式によるパスをネットワーク装置の各（送信先，送信元）ペアについて格納する手段と、観察された以前のパスの履歴を用いて選択されたノードによって、データを他の装置に送信する手段とを有する通信装置に関する。本発明はまた、通信方法に関する。
2009538077.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つの通信装置を有する通信ネットワークにおける通信装置であって、
装置間のコンタクトの任意のシーケンスについて、（ＬＤ（Ｌａｓｔ  Ｄｅｐａｒｔｕｒｅ），ＥＡ（Ｅａｒｌｉｅｓｔ  Ａｒｒｉｖａｌ））ペアのリストの形式によるパスをネットワーク装置の各（送信先，送信元）ペアについて格納する手段と、
観察された以前のパスの履歴を用いて選択されたノードによって、データを他の装置に送信する手段と、
を有する通信装置。
【請求項２】
前記通信ネットワークは、パケット交換タイプであり、
当該通信装置は、
前記ネットワークの（送信元，送信先）ペアについて、各時点において生成された各パケットの最先の到着時間を提供する関数を生成する手段と、
（ＬＤ，ＥＡ）ペアのセットに基づき前記関数を表現する手段と、
を有する、請求項１記載の通信装置。
【請求項３】
前記ネットワークは、ＰＡＮ（Ｐｅｒｓｏｎａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）タイプネットワークである、請求項１又は２記載の通信装置。
【請求項４】
前記ネットワークは、無線アドホックタイプである、請求項１又は２記載の通信装置。
【請求項５】
前記ネットワークは、Ｂｌｕｅｔｏｏｔｈタイプである、請求項３記載の通信装置。
【請求項６】
前記ネットワークは、Ｗｉ−Ｆｉタイプである、請求項１又は２記載の通信装置。
【請求項７】
前記ネットワークの通信装置は、ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）アドレスにより識別される、請求項１乃至６何れか一項記載の通信装置。
【請求項８】
少なくとも２つの通信装置を有する通信ネットワークにおける通信方法であって、
装置間のコンタクトの任意のシーケンスについて、（ＬＤ（Ｌａｓｔ  Ｄｅｐａｒｔｕｒｅ），ＥＡ（Ｅａｒｌｉｅｓｔ  Ａｒｒｉｖａｌ））ペアのリストの形式によるパスをネットワーク装置の各（送信先，送信元）ペアについて格納するステップと、
観察された以前のパスの履歴を用いて選択されたノードによって、データを他の装置に送信するステップと、
を有する通信方法。
【請求項９】
前記通信ネットワークは、パケット交換タイプであり、
当該通信方法は、
前記ネットワークの（送信元，送信先）ペアについて、各時点において生成された各パケットの最先の到着時間を提供する関数を生成するステップと、
（ＬＤ，ＥＡ）ペアのセットに基づき前記関数を表現するステップと、
を有する、請求項８記載の通信方法。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
［発明の範囲］
本発明は、無線ネットワークの分野に関する。より詳細には、本発明は、通信装置と、異なる装置の間の通信方法とに関する。
【０００２】
［従来技術］
本発明は、アドホックワイヤレスタイプ又はＰＡＮ（Ｐｅｒｓｏｎａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、特にＢｌｕｅｔｏｏｔｈなどのネットワークの範囲内に属する。ネットワークは、モバイル端末がＭＡＣアドレスなどにより特定されるグラフのノード（ピーク）とされ、エッジが端末ペア間の接続又はコンタクトに対応し、パスが時間的に順序付けされたエッジのシーケンスとされるグラフとして示される。可能性のあるすべてのパスのうち、所与の時点に送信元からスタートして、可能となる最も早い到着日に送信先に到着する場合、それが最適とみなされる。各（送信元、送信先）ペアについて、到着関数は、各時点において生成されるパケットの最も早い到着時間を与える。“単純な（ｎａｉｖｅ）”解決策は、観察された遅延を各時点の値により表現することからなる。最適パスの計算アルゴリズムは、可能な新たなパスが検出される毎に、値のセットを更新することである。この解決策は、空間的及び処理的にコストがかかる。
【０００３】
科学論文“Ｓｈｏｒｔｅｓｔ−Ｐａｔｈ  ａｎｄ  Ｍｉｎｉｍｕｍ−Ｄｅｌａｙ  Ａｌｇｏｒｉｔｈｍｓ  ｉｎ  Ｎｅｔｗｏｒｋｓ  ｗｉｔｈ  Ｔｉｍｅ−Ｄｅｐｅｎｄｅｎｔ  Ｅｄｇｅ−Ｌｅｎｇｔｈ”（Ａ．Ｏｒｄａ  ａｎｄ  Ｒ．Ｒｏｍ）を通じて、従来技術では、エッジの遅延（又はウェート）がランダム関数に従って変換するネットワークにおける最短パスの問題を解く方法が知られている。本発明による方法は、それが同時にすべての送信元について最短パスを計算する点で異なっている。
【０００４】
また、科学論文“Ａｎ  ｅｆｆｉｃｉｅｎｔ  ｏｎ−ｌｉｎｅ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｔｈｅ  ｓｈｏｒｔｅｓｔ  ｍｏｂｉｌｅ  ｐａｔｈ  ｐｒｏｂｌｅｍ”（Ｓｙｒｏｔｉｕｋ）を通じて、従来技術では、モバイルグラフの形式により示されるネットワークにおける最短パスの問題を解くための方法が知られている。
［発明の概要］
何れか許容されるコンタクトシーケンス（時間的に順序付けされたパス）について、ＥＡ（Ｅａｒｌｉｅｓｔ  Ａｒｒｉｖａｌ）とＬＤ（Ｌａｓｔ  Ｄｅｐａｒｔｕｒｅ）とが定義される。本発明による方法は、時間グラフのエッジ又はコンタクトセットに対する帰納によって、すべての（送信元，送信先）ペアの到着関数を構成する。この関数は、（ＬＤ，ＥＡ）ペアのセットに基づき表現される。各（送信元，送信先）ペアについて、（ＬＤ，ＥＡ）ペアのリストによりすべての最適パスを表現することが可能である。
【０００５】
各時点における到着プロセス（到着関数）は、時間値ペアのシーケンスにより表現される。
【０００６】
本発明は、最適パスを迅速かつ効率的に抽出する方法を提案することによって、従来技術の問題点を解決するものである。
【０００７】
このため、本発明は、それの最も一般的に受け入れられている意味において、少なくとも２つの通信装置を有する通信ネットワークにおける通信装置であって、装置間のコンタクトの任意のシーケンスについて、（ＬＤ（Ｌａｓｔ  Ｄｅｐａｒｔｕｒｅ），ＥＡ（Ｅａｒｌｉｅｓｔ  Ａｒｒｉｖａｌ））ペアのリストの形式によるパスをネットワーク装置の各（送信先，送信元）ペアについて格納する手段と、観察された以前のパスの履歴を用いて選択されたノードによって、データを他の装置に送信する手段とを有する通信装置に関する。
【０００８】
好ましくは、前記通信ネットワークは、パケット交換タイプであり、当該通信装置は、前記ネットワークの（送信元，送信先）ペアについて、各時点において生成された各パケットの最先の到着時間を提供する関数を生成する手段と、（ＬＤ，ＥＡ）ペアのセットに基づき前記関数を表現する手段とを有する。
【０００９】
一変形によると、前記ネットワークは、ＰＡＮ（Ｐｅｒｓｏｎａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）タイプネットワークである。
【００１０】
一実施例によると、前記ネットワークは、無線アドホックタイプである。
【００１１】
一実施例によると、前記ネットワークは、Ｂｌｕｅｔｏｏｔｈタイプである。
【００１２】
他の実施例によると、前記ネットワークは、Ｗｉ−Ｆｉタイプである。
【００１３】
一変形によると、前記ネットワークの通信装置は、ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）アドレスにより識別される。
【００１４】
本発明はまた、少なくとも２つの通信装置を有する通信ネットワークにおける通信方法であって、装置間のコンタクトの任意のシーケンスについて、（ＬＤ（Ｌａｓｔ  Ｄｅｐａｒｔｕｒｅ），ＥＡ（Ｅａｒｌｉｅｓｔ  Ａｒｒｉｖａｌ））ペアのリストの形式によるパスをネットワーク装置の各（送信先，送信元）ペアについて格納するステップと、観察された以前のパスの履歴を用いて選択されたノードによって、データを他の装置に送信するステップとを有する通信方法に関する。
【００１５】
好ましくは、前記通信ネットワークは、パケット交換タイプであり、当該通信方法は、前記ネットワークの（送信元，送信先）ペアについて、各時点において生成された各パケットの最先の到着時間を提供する関数を生成するステップと、（ＬＤ，ＥＡ）ペアのセットに基づき前記関数を表現するステップとを有する。
［発明の実施例の詳細な説明］
本発明による方法は、大きなトレースに関する計算又はリアルタイムによる計算を実現するのに必要とされるメモリを低減する。
【００１６】
さらに、本発明による方法は、これら最適パスのうちの最もコンパクトな表現である（Ｎ個の最適パスについて２Ｎ個のナンバー）。さらに、それは、使用される符号変換が同時パスについて良好に適応化され、パス粒度に関する極めて高い不均一度（数秒に多数のパス、イベントのない長い期間）、の２つの状況に自動的に適応する。
【００１７】
本発明の結果は、モバイル端末の送信決定を行うのに利用可能である。
【００１８】
グラフトポロジーにおけるパスを構成するエッジシーケンスは、時間に関するパスがコンタクトシーケンスを用いて定義可能である場合、許容されると呼ばれる。すなわち、（ｅ１，ｅ２，．．．，ｅｎ）は、ｔｉｂｅｇ≦ｔｉ≦ｔｉｅｎｄとなるような非減少の時間シーケンス（ｔ１，．．．，ｔｎ）が存在する場合、許容される。ただし、ｅｉ＝（ｖｉ，ｖｉ−１，ｔｉｂｅｇ，ｔｉｅｎｄ）である。
【００１９】
帰納によって、等価な条件が
【数１】
2009538077.tif 000003
であるという事実を得る。
【００２０】
許容されるシーケンスは、シーケンスの最後のコンタクトが他方のシーケンスの最初のコンタクトである場合でさえ、常に連結可能であるとは限らない。これは、第１シーケンスの時間に関するパスが、第２シーケンスの時間に関するパスがすでに終わった後に到着する可能性があるという事実によるものである。
【００２１】
図３は、このケースの一例を示す。すなわち、シーケンス（ｅ１，ｅ２，ｅ３，ｅ４）は、それが時間に関して増加するシーケンス（３，５，５，５）に関連付けできるため、許容される。同様に、シーケンス（ｅ４，ｅ５）は、時間シーケンス（４，４）に関連付け可能である。しかしながら、（ｅ１，ｅ２，ｅ３，ｅ４，ｅ５）は、それが時間に関してパスを定義しないため、許容されない。この図３では、水平方向の各ライン上の垂直方向の第１の短いダッシュ記号は第１コンタクトを表し、水平方向の各ライン上の垂直方向の第２のダッシュ記号はコンタクトのエンドを表す。
【００２２】
任意の許容されるコンタクトシーケンスｅ＝（ｅ１，ｅ２，．．．，ｅｎ）について、ＥＡは、
【数２】
2009538077.tif 000004
と定義される。同様に、ＬＤは、
【数３】
2009538077.tif 000005
と定義される。
【００２３】
以下の事実が、簡単に得られる。それらは、上記定義が時間に関する大きなパスクラスの一般的な記述と、許容されるシーケンスの操作を可能にする。
（ｉ）ｅに係る時間に関するすべてのパスが、ＬＤ（ｅ）前に送信元を出発し、ＥＡ（ｅ）後に到着する。
（ｉｉ）時点ＬＤ（ｅ）に送信元を出発し、時点ＥＡ（ｅ）に到着するｅに係る時間に関するパスが存在する。
（ｉｉｉ）ｖｎ＝ｖ０’などのコンタクトの２つのシーケンス（ｅ），（ｅ’）は、ＥＡ（ｅ）≦ＬＤ（ｅ’）である場合かつその場合に限って、１つの許容されるシーケンス
【数４】
2009538077.tif 000006
に連結可能である。
【００２４】
提案（ｉｉｉ）は、上述された許容されるシーケンス（１）の特徴のシンプルかつ有用な構成である。
【００２５】
【数５】
2009538077.tif 000007
及び
【数６】
2009538077.tif 000008
であることを証明することは簡単である。
【００２６】
（ｉｉ）では、時点ＬＤ（ｅ）に送信元を出発し、時点ＥＡ（ｅ）に到着するパスは必ずしも同一である必要はない。例えば、ｔｂｅｇ＜ｔｅｎｄによる時間インターバル［ｔｂｅｇ；ｔｅｎｄ］において一意的なコンタクト（ａ−＞ｂ）により実現されるシーケンスｅを考える。このコンタクトを用いた時間に関するパスは、時点ｔｂｅｇにおけるａ−＞ｂから時点ｔｅｎｄにおける異なるパスに移行する。しかしながら、ＬＤ（ｅ）≦ＥＡ（ｅ）であるとき、マルチホップタイプパスの通常のケースと同様に、時点ＬＤ（ｅ）で出発し、時点ＥＡ（ｅ）で到着するパスが構成可能である。このシーケンスに係る時間に関するすべてのパスのうち、上記パスが、遅延に関して最も効率的であるため最適である。
【００２７】
時点ｔｄｅｐにおいてノードａを出発し、時点ｔａｒｒにおいてノードｂに到着した時間に関するパスは、出発／到着時間に関して厳密により良いパスが他に存在しない場合、最適であると呼ばれる。すなわち、後からスタートした他のパスは必ず後に到着し、より早く到着した他のパスは、必ず前にスタートしていなければならない。
【００２８】
【数７】
2009538077.tif 000009
ただし、ｔ’ｄｅｐ，ｔ’ａｒｒは、ａからｂに進む他のパスの出発時間と到着時間に対応する。
【００２９】
時間に関する所与のパスのサブセット内において、サブセットの他の何れのパスも上述された定義に従って厳密により良いものでない場合、当該サブセットについて最適であると呼ばれる。
【００３０】
例えば、コンタクトシーケンスｅに係るすべてのパスのサブセットを考慮することができる。このサブセットに対する最適なパスは、（ＥＡ（ｅ），ＬＤ（ｅ））となると特徴付けされる。ＬＤ（ｅ）≦ＥＡ（ｅ）である場合、上述されるように、時点ＥＡ（ｅ）において到着し、時点ＬＤ（ｅ）において出発したパスが構成可能である。それは最適であり、すべての最適パスは、ちょうど同じ時点で必ず出発及び到着する。
【００３１】
他方、ＥＡ（ｅ）＜ＬＤ（ｅ）である場合、これは、ｅの各コンタクトに係るすべてのインターバルが［ＥＡ（ｅ）；ＬＤ（ｅ）］上の交差を認識するという定義から得られる。その後、この共通するインターバルにおける選択された各時点ｔにおいて出発及び到着する最適なパスが構成可能である。これらは唯一のものである。
【００３２】
各送信元ａと送信先ｂについて、送信元により送信可能な時間の関数としてメッセージの最も早い到着を提供する到着関数が導入される。この関数は、一般に、
【数８】
2009538077.tif 000010
により定義される。ただし、πは、時間グラフにおいてａとｂとの間に引かれうる時間に関するすべてのパスを表す。慣例として、パスが存在しない場合、それは無限とされる。この定義では、最小値は、関数の値を変更することなく最適なパスしか含まないよう制限可能である。
【００３３】
所与のコンタクトシーケンスｅについて最適なパスの特徴は、明示的に知られ、ＥＡ（ｅ）、ＬＤ（ｅ）により提供される。到着関数の以下の式は、上述したものから導出できる。
【００３４】
【数９】
2009538077.tif 000011
ただし、最小値は、送信元から送信先に導くすべての許容されるコンタクトシーケンスｅからとられる。
【００３５】
すなわち、時間グラフにおいて直接構成され、許容されるコンタクトシーケンスに基づく到着関数のすべての値及び不連続性が記述可能である。さらに、この関数はこれらすべてのシーケンスに係るペア（ＥＡ，ＬＤ）にのみ依存する。
【００３６】
図２によって、到着関数とペアシーケンスによるそれの表現が示される。時間ｔがｘ軸に表現され、無限とすることが可能な到着関数の値がｙ軸に表される。このスキーマは、時間図と呼ばれる。スキーマは、左側でペアに係る座標による点を示し、中間で（２）における最小値によりとられる値を表し、右側で到着関数が示される。これら補完的ケースが示される。すなわち、ペア１及び３は、送信元と送信先との間の同時接続インターバルに対応し、ペア２は、コンタクトがある時間インターバルのみ続く同様のケースに対応し、ペア４は、データが送信元を出発し、送信前の中継の時点で留まる必要があるとき、同時接続に対応しない。同様のケースに実際に遭遇する。
【００３７】
与えられるアルゴリズムでは、到着関数は、関数として直接ではなく、それに係るペアシーケンス（ＬＤ，ＥＡ）を利用して常に示される。この表現によると、エンプティなコレクションは、パスが存在しない送信元・送信先ペアに自然と対応し、到着関数は常に無限の値の定数となる。
【００３８】
本発明による方法は、出発時点毎にすべての送信元・送信先ペアに対する時間グラフにおけるすべての最適パスのパフォーマンスを効率的に処理及び示す。これら最適なパスは、モバイルネットワークにおける日和見的コンタクトに基づき可能性のあるベストな送信選択に対応する。最適パスのみの考察は限定的過ぎる可能性があるため、同じ方法が特定クラス内のすべての最適パスの特定を可能にする。この最適性の概念はパラメータ化可能である。
【００３９】
本発明による方法は、時間グラフのエッジ又はコンタクトセットに対する帰納によって、すべての送信元・送信先ペアの到着関数を構成する。この関数は、ペアセット（ＬＤ，ＥＡ）に基づき表される。
【００４０】
２つのマークが、各送信元・送信先ペアに適用される。
・許容されるシーケンスに係る多数のペア（ＬＤ，ＥＡ）は、（２）により与えられる到着関数を特徴付けるのに必要とされない。この関数は、この送信元・送信先ペアについて不連続な箇所の数と最適なパスの個数とに等しい少数のペアにより完全に特徴付け可能である。
・ペアセットがリスト形式により構成される場合、すなわち、第１座標によりソートされる場合、当該リストは、他のコンタクトシーケンスの効果を取得する他のペア（ＬＤ，ＥＡ）を有するよう効率的にアップデートすることができる。
【００４１】
これらの技術に基づき、２つのアルゴリズムが開発された。
１）非限定サーチ
すべての最適パスの効果を取得するため、時間グラフにおけるコンタクトが次々に追加される。エンプティコレクションとエンプティコンタクトセットからスタートして、拡張されたサブグラフについて到着関数を表すコレクションが各ステージについて更新される。時間グラフにおけるコンタクトであるａ−＞ｂエッジが追加されるとき、係るペア（ＬＤ，ＥＡ）はまず、送信元ａと送信先ｂに対応するコレクションに含まれる。新たな最適パスにおいてこのエッジによって通過しうるすべてのパスを表すため、送信元ｓ及び送信先ａを有するすべてのコレクションと、送信元ｂ及びすべての送信先ｄを有するコレクションとが調べられる。これらのコレクションにおけるすべてのペア（ＬＤ，ＥＡ）を検討する必要はない。これらのうちの一部は、以前に与えられた連結ルールに従って許容されるシーケンスにおける新たなエッジにより完成されなくてもよく、他のものは新たな最適パスの定義をもたらすものでない。これらの処理（連結、最適性、依存の到着関数への包含）のすべてが、係るペア（ＬＤ，ＥＡ）の値に基づき決定可能である。これらすべてのコンタクトが含まれた後、特に各時点で観察される最適パスの遅延の特性を記述する最良の到着関数が取得される。
２）限定的なホップによるサーチ
このアルゴリズムでは、一意的な連結が、同一の固定されたリファレンスセットによるすべてのコンタクトの右に繰り返される。それはエンプティセットからスタートされ、これにより、第１の繰り返しはサイズ１の最適パスのすべての生成する（２つのターミナルの間の直接的な各コンタクトは実際に最適パスであるため）。次のステップでは、これらのパスのセットが新たなリファレンスセットとみなされ、変更することなく各コンタクトが再び当該セットと連結される。これらの結果は、少なくとも２つのサイズを有するすべての最適パスを取得するため結合される。このとき、メモリに第１パスセットを保存することは、以降のステージについて不要となる。
【００４２】
本発明によると、通信装置は、典型的には、プロセッサ、メモリ及び他の通信装置との通信手段を有するモバイル端末である。
【００４３】
本発明による分散方法は、各送信元から各送信先への最適遅延を与えるパスを事後的に計算する。
【００４４】
一実施例では、本方法は、現在までの最適遅延パスに関する情報の正確な計算である後方ルーティングと、送信決定を行うための過去の情報の抽出を担当する機構であるイベントログに基づく送信との２つの要素を有する。
・後方ルーティング
この部分では、自己に対するすべての送信元の過去の機会に関するネットワークの現在の状態が維持される。
【００４５】
各ネットワークノードは、後方ルーティングテーブルにおいて自己に対するすべての送信元ｓの直近の最適遅延パスを有する。このパスは、パケットがｓの直近の可能な時点に出発し、現在時点ｔより前にノードに到着することを可能にするものと同様に定義される。
【００４６】
すべてのテーブルは初期的にはエンプティである。２つのノードがコンタクトに到着すると、それらのテーブルの内容が、このコンタクトを表すようそれらの状態を更新するように交換される。これはまた、各ノードが他の送信元の存在を通知されることを可能にする。
【００４７】
ノードが特に他のノードによって興味を持たれていないとき、すべてのネットワーク送信元に関する情報を取得することは過剰であるかもしれない。しかしながら、ノード毎に選択を行うことは、送信元から当該送信先へのパスに対する影響を及ぼし、これはまた、データを交換するための中継として当該送信先を利用することを可能にするすべてのパスを排除することとなる。
【００４８】
２つのノードが互いに繰り返し遭遇するとき、冗長な入力の交換を回避することが可能である。
・履歴ベースフォワーディング
まず、一定の進展の状態における後方ルーティングテーブルから情報が抽出される。最適遅延パスの中継となったものに関する統計が収集可能である。
【００４９】
次に、この情報が、データパケットの送信を実行するため利用される。
【００５０】
図４は、７つのノードを有するシナリオを示す。５つのノードがこの期間中静的となる。それらは、２つのノードと３つのノードをそれぞれ含む２つのクラスタＡとＢに分散される。２つのノードは、異なる領域において動作する。２つのうちの１つが、特に複数の異なる時点に２つの静的なクラスタとのコンタクトに入る。
【００５１】
上述された後方ルーティングステージは、本例では以下のように動作する。
【００５２】
時点ｔ＝１において、後方ルーティングテーブルは、静的なノードしか有さず、モバイルノードはクラスタＢのすべてのノードからのパスを含む。
【００５３】
時点ｔ＝２において、中間のモバイルノードは、他方のクラスタとのコンタクトに入る。それは、クラスタＢのすべてのノードからクラスタＡのすべてのノードへの最適遅延パスによって遷移的に送信される。これは、クラスタＡのノードによりすぐに反映される。
【００５４】
時点ｔ＝３において、Ｂとコンタクトするモバイルノードは、当該クラスタからの出発時にそれらのすべてのパスを更新し、時点ｔ＝２におけるクラスタＡのすべてのノードからクラスタＢのノードへの新たなパスを生成する。さらに、左端のノードがクラスタＡのノードとのコンタクトに入る。それは、ｔ＝３に等しい出発時点のクラスタＡ全体のパスと出発時点ｔ＝１のクラスタＢのパスとを継承する。
【００５５】
時点ｔ＝４において、モバイルノードは、Ａにおいて第２コンタクトを繰り返す。それは、すべてのパスを更新し、左端のモバイルノードに対応する入力をまず取得する。
【００５６】
時点ｔ＝５において、各モバイルノードはまず、クラスタ、特にクラスタＢとのコンタクトに入る。このクラスタは、左端のモバイルノードから開始されるパスを有する。
【００５７】
この時点で、すべてのペア（送信元，送信先）について検出されたパスであるネットワークが接続される。
【００５８】
履歴に基づく特定の処理が、送信をより効率的なものにすることができる。
【００５９】
左端のモバイルノードのレベルで生成されたパケットがクラスタＢに送信される必要がある場合、時点ｔ＝３で実行されたコンタクトに基づき、クラスタＡにコピーを残すことが決定できる。なぜなら、それはＡを介しわたされる自らへのＢのパスをまず観察したためである。実際、同じルールに従って、クラスタＡのノードは、時点ｔ＝４の中間でモバイルノードにパケットを提供し、その後、時点ｔ＝５においてそれを送信先に提供する。
【００６０】
極めて迅速に、２つのクラスタのノードは、中間にあるモバイルノードが他方のクラスタへのパケットの送信に良好なオプションとなることを特定可能である。
・後方ルーティングテーブルフォーマット
各エントリについて、送信元（ＭＡＣアドレス又は他の一意的シグネチャにより特定される）と、当該送信元からの最後の出発として特定された時間との２つのフィールドが必要である。この情報は、更新された状態においてテーブルを維持するのに十分であるが、これは、各送信元とノードとの間の距離（又は最適パスの遅延）しか記述しないため、１以上の特定の中継の選択を不可にする。
【００６１】
他のフィールドが追加できる。それは、例えば、直近の送信機の身元、パスにおける各中継の完全なリスト、パスが記録された時間（当該パスにより使用される直近のコンタクトに対応する）及び当該パスに対するそれらの間の移行時間と使用された中継のリストなどを含みうる。
【００６２】
一例となるテーブルが、以下のテーブルに与えられる。
【００６３】
【表１】
2009538077.tif 000012
このテーブルは、初期的にはエンプティである。ｉとｊが一致するとき、それらはまず互いに関するエントリを初期化又は更新する。
【００６４】
【表２】
2009538077.tif 000013
第２に、それらは自らの現在の後方ルーティングテーブルを交換する。ノードが送信元ｓと最後の出発ｔ’について新たなエントリを受け取ると、当該ソースについてエントリがない場合には、それをテーブルに追加し、当該ソースのエントリがすでにある場合、直近の出発の時間を引くし、それを最も高い値により更新する。
【００６５】
エントリが初期化又は更新されると、使用されたパスに関する情報が受信されたものと連結される。
【００６６】
例えば、特定のエントリを送信しないことによって、交換されるエントリの個数を制限することが可能である。
【００６７】
本発明が実施例により上述された。当業者は、特許の範囲を離れることなく本発明の変形を生成可能であることを理解するであろう。
【図面の簡単な説明】
【００６８】
【図１】図１は、本発明による方法を示す。
【図２】図２は、所与の（送信元，送信先）ペアについて各時点での最適パスを示す時間図である。
【図３】図３は、連結不可である同一コンタクトを使用した時間に関するパスの一例を示す。
【図４】図４は、モバイルネットワークのシナリオ例を示す。
【図１】
2009538077.tif 000014
【図２】
2009538077.tif 000015
【図３】
2009538077.tif 000016
【図４】
2009538077.tif 000017
【手続補正書】
【提出日】平成20年11月26日(2008.11.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
少なくとも２つの通信装置を有する通信ネットワークにおける通信装置であって、
装置間のコンタクトの任意のシーケンスについて、（ＬＤ（Ｌａｓｔ  Ｄｅｐａｒｔｕｒｅ），ＥＡ（Ｅａｒｌｉｅｓｔ  Ａｒｒｉｖａｌ））ペアのリストの形式によるパスをネットワーク装置の各（送信先，送信元）ペアについて格納する手段と、
観察された以前のパスの履歴を用いて選択されたノードによって、データを他の装置に送信する手段と、
を有し、
ＥＡ及びＬＤは、通信装置間の接続期間に関する通信装置。
【請求項２】
前記通信ネットワークは、パケット交換タイプであり、
当該通信装置は、
前記ネットワークの（送信元，送信先）ペアについて、各時点において生成された各パケットの最先の到着時間を提供する関数を生成する手段と、
（ＬＤ，ＥＡ）ペアのセットに基づき前記関数を表現する手段と、
を有する、請求項１記載の通信装置。
【請求項３】
前記ネットワークは、ＰＡＮ（Ｐｅｒｓｏｎａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）タイプネットワークである、請求項１又は２記載の通信装置。
【請求項４】
前記ネットワークは、無線アドホックタイプである、請求項１又は２記載の通信装置。
【請求項５】
前記ネットワークは、Ｂｌｕｅｔｏｏｔｈタイプである、請求項３記載の通信装置。
【請求項６】
前記ネットワークは、Ｗｉ−Ｆｉタイプである、請求項１又は２記載の通信装置。
【請求項７】
前記ネットワークの通信装置は、ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）アドレスにより識別される、請求項１乃至６何れか一項記載の通信装置。
【請求項８】
少なくとも２つの通信装置を有する通信ネットワークにおける通信方法であって、
装置間のコンタクトの任意のシーケンスについて、（ＬＤ（Ｌａｓｔ  Ｄｅｐａｒｔｕｒｅ），ＥＡ（Ｅａｒｌｉｅｓｔ  Ａｒｒｉｖａｌ））ペアのリストの形式によるパスをネットワーク装置の各（送信先，送信元）ペアについて格納するステップと、
観察された以前のパスの履歴を用いて選択されたノードによって、データを他の装置に送信するステップと、
を有し、
ＥＡ及びＬＤは、通信装置間の接続期間に関する通信方法。
【請求項９】
前記通信ネットワークは、パケット交換タイプであり、
当該通信方法は、
前記ネットワークの（送信元，送信先）ペアについて、各時点において生成された各パケットの最先の到着時間を提供する関数を生成するステップと、
（ＬＤ，ＥＡ）ペアのセットに基づき前記関数を表現するステップと、
を有する、請求項８記載の通信方法。
【国際調査報告】
2009538077.tif 000018
2009538077.tif 000019
2009538077.tif 000020
2009538077.tif 000021