次に、本発明の実施形態について図面を参� ��して説明する。
[第1の実施形態]
 まず、図1および図2を参照して、本発明の� �1の実施形態にかかるノードの基本構成につ� ��て説明する。

 このノード1は、ディレイトレラントネッ トワークを構成する情報通信端末からなり、 例えばディレイトレラントネットワークが図 2に示すような無線アドホックネットワーク� �場合、ノード1は携帯電話機などの無線端末� ��ら構成される。

 各ノード1は、単独で動作するものではな く、図2に示すような無線アドホックネット� �ークにおける1つのノードとして機能する。� ��2に示す無線アドホックネットワークにおけ るノード1A~1Dは、全てノード1と同一の機能を 含んでいる。これらノード1A~1Dを中心とした� ��線の円は、それぞれのノードからの電波が� ��く範囲を示しており、この円の内部に存在� ��るノードが隣接ノードとして認識される。� ��えば、ノード1Aの隣接ノードはノード1B~1Dと なる。

 図1に示すように、ノード1は、基本構成� �して、ルーティングプロトコル部11、ルーテ ィングテーブル12、およびDTN転送部13を含む� �これら基本構成は、一般的な情報通信端末� �備えるCPU、メモリ、各種インターフェース� �路などを含むハードウェアとプログラムや� �プリケーションからなるソフトウェアとが� �働して実現される。

 本実施形態は、ネットワーク内の各ノー� ��1において、ルーティングテーブル12内の宛� ��ノードへの現在および過去のエンド-エンド の経路の履歴に基づいて、ルーティングプロ トコル部11により宛先ノードへの配送確率を� ��算し、各ノード1における宛先ノードへの配 送確率の大小に基づいて、DTN転送部13により� ��送データを転送する際の次ホップノードを� ��定する。

 次に、図3を参照して、ノード1の詳細な構� �について説明する。
 図3において、ノード1は、主な機能部とし� �、ルーティングプロトコル部11、ルーティン グテーブル12、DTN転送部13、およびTCP/IP部14を 含む。これら機能部は、一般的な情報通信端 末が備えるCPU、メモリ、各種インターフェー ス回路などを含むハードウェアとプログラム やアプリケーションからなるソフトウェアと が協働して実現される。

 ルーティングプロトコル部11は、主な処理� �として、経路・確率情報交換部11A、配送確� �データベース11B、配送確率計算部11C、およ� �経路計算・設定部11Dを含む。
 経路・確率情報交換部11Aは、隣接ノードと� ��ード情報、リンク情報、配送確率情報など� ��交換し、交換した情報を基にルーティング� ��ントリを作成し、作成したルーティングエ� ��トリをルーティングテーブル12に更新する� �能を含んでいる。
 配送確率データベース11Bは、ネットワーク� ��の各ノードに対する配送確率の情報が格納� ��れているデータベースである。

 ここで、配送確率とは、各ノードがどれ� ��らいバンドルを宛先ノードまで配送できる� ��能性をもっているかを数値化したものであ� ��。例えば、あるノードにおいて、宛先ノー� ��に対して1.0の配送確率をもっているという� ��は、該ノードが宛先ノードへの直接の経路( 以降直接経路と呼ぶ)がある場合である。ま� �、あるノードにおいて、宛先ノードに対し� �0の配送確率をもっているというのは、該ノ� ��ドが宛先ノードのことを全く知らないなど� ��該ノードから宛先ノードまでバンドルを配� ��できる可能性がない、または不明であるこ� ��を表している。

 これに対して、あるノードにおいて、宛� ��ノードに対して0から1.0の間の配送確率をも っている場合は、該ノードが宛先ノードと直 接経路をもっていたことがあり、現在は直接 経路がない状態を表している。そして、配送 確率の大小は、最後に宛先ノードまでの直接 経路があった時刻からの経過時間、および、 該経路における宛先ノードまでのホップ数に 基づいて計算される。

 図4に示す配送確率データベース11Bの構成 例を参照すると、ネットワーク内の各ノード のIPアドレスおよび該ノードに対する配送確� ��が登録されており、例えば、IPアドレスが10 .0.0.2のノードに対しては、配送確率が1.0であ り、IPアドレスが10.0.0.17のノードに対しては� ��配送確率が0.5であることがわかる。

 配送確率計算部11Cは、ルーティングテーブ� ��12内に格納されている経路情報、すなわち� �該ノードから宛先ノードへの過去から現時� �、すなわち配送確率計算時までのエンド-エ� ��ドの経路の履歴に基づいて、各宛先ノード� ��の配送確率を計算し、配送確率データベー� ��11Bへ登録する機能を含んでいる。
 配送確率の計算は、配送確率データベース1 1Bの説明において述べたように、宛先ノード� ��での直接経路があるかどうか(直接経路があ る場合は1.0)、および、宛先ノードまでの直� �経路がない場合は、最後に宛先ノードまで� �直接経路があった時刻からの経過時間、お� �び該直接経路における宛先ノードまでのホ� �プ数に基づいて計算される。

 計算アルゴリズムの例として、ノードaに おいて、最後にノードbへの直接経路があっ� �時刻からの経過時間をt、該直接経路におけ� ��ノードaからノードbまでのホップ数をdとし� ��とき、ノードaにおけるノードbに対する配� �確率P(a,b)は、次の式(3)により計算する。

 P(a,b) = P(a,b)old×γ^t×r^(d-1)  …(3)
 ここで、P(a,b)oldは計算前のP(a,b)の値、γは� �間についての減衰定数、rはホップ数につい� ��の減衰定数である。この際、ホップ数では� ��く、リンクコストの総和であるメトリック� ��用いられてもよい。上記のt,d以外のパラメ� ��タが配送確率の計算に用いられてもよく、� ��えば、GPSによってノードの位置を取得する� ��とができる場合は、ノードaとノードbとの� �離が用いられる、などの方法が考えられる� �

 経路計算・設定部11Dは、経路・確率情報� ��換部11Aを介して他のノードから受信したネ� ��トワーク内のノード情報、リンク情報から� ��ネットワーク内の各ノードへの直接経路を� ��算し、計算された結果得られた経路エント� ��をルーティングテーブル12へ登録する機能� �含んでいる。

 経路計算・設定部11Dにおいて各ノードへ� ��直接経路を計算するためのプロトコルとし� ��は、例として、MANET(Mobile Ad-hoc NETwork)ルー� ��ィングプロトコルとして用いられている、O LSR(Optimized Link State Routing Protocol)やAODV(Ad Ho c On Demand Distance Vector Algorithm)が挙げられ� �。以下、本実施形態では、経路計算・設定� �11Dで用いられるプロトコルとして、AODVが用� ��られるものとして説明を行う。

 経路計算・設定部11Dは、従来のルーティ� ��グプロトコルのように、直接エンド-エンド で接続されているノードへの直接経路だけで はなく、確率的に宛先ノードまで配送可能な 途中の中継ノードまでの経路も、宛先ノード への確率的経路としてルーティングテーブル 12へ登録するという特徴を持つ。具体的には� ��現時点ではエンド-エンドで接続されていな いが、ある中継ノードまで転送すれば、該中 継ノードからは自ノードよりも高い確率で宛 先ノードまでDTN転送される場合、該中継ノー ドへの経路が宛先ノードへの確率的経路とし て登録される。

 確率的経路の設定においては、自ノード� ��ら直接経路のあるノードのうち、最も高い� ��先ノードまでの配送確率を持つノードを中� ��ノードとして選択する。ここで、自ノード� ��ら直接経路のある各ノードにおける宛先ノ� ��ドまでの配送確率を知る方法として、MANET� �ーティングプロトコルのメッセージを用い� �。詳細な動作については図7を参照して後述� ��る。

 ルーティングテーブル12は、ネットワーク� �の各ノードに対する直接経路および確率的� �路が登録されているテーブルである。
 図5に示したルーティングテーブル12の構成� ��を参照すると、宛先ノードごとに次ホップ� ��ードのIPアドレス、メトリックが登録され� �いる。ここで、メトリックとは、宛先ノー� �までの直接経路におけるリンクコストの総� �として定義される。各リンクのリンクコス� �が1の場合は、メトリックは宛先ノードまで� ��ホップ数と同一の値となる。

 この他に、タイプが登録されており、1お よび2のいずれかのタイプが登録されている� �ここで、タイプ1は、宛先ノードまで直接経� ��が存在する場合で、従来のIPルーティング� �ロトコルで登録されているエントリと同一� �ものである。

 タイプ1は、ルーティングテーブル12にお� ��る上から1番目のエントリの場合、宛先IPア� ��レスが10.0.0.2のノードへ到達するためには� �IPアドレスが10.0.0.2を持つ次ホップノードへ� ��送すればよいエントリであることを示して� ��る。この場合、宛先ノードが自ノードと隣� ��しているため、同一の次ホップノードとな� ��ている。また、宛先ノードまでのメトリッ� ��は1である。次に、2番目のエントリの場合� �、宛先IPアドレス10.0.0.7のノードへ到達する� ��めには、IPアドレスが10.0.0.3を持つ次ホップ ノードへ転送すればよいことを示している。 また、宛先ノードまでのメトリックは2であ� �。

 一方、タイプ2は、必ずしも宛先ノードま でエンド-エンドでつながっているとは限ら� �い場合に登録され、確率的に宛先ノードへ� �達できることを示すエントリ(確率的経路)で ある。タイプ2の経路エントリには、中継ノ� �ドのIPアドレス、配送確率が加えて登録され ている。ここで、中継ノードIPアドレスは、� ��先ノードまで転送したいバンドルを到達さ� ��られる確率(配送確率)が最も高いノードのIP アドレスで、中継ノードは、自ノードからタ イプ1の経路があるノードのなかから選択さ� �る。また、タイプ2の経路エントリの場合、� ��トリックは中継ノードまでのメトリックが� ��録されている。

 ルーティングテーブル12における上から3� ��目のエントリの場合、宛先IPアドレスが10.0. 0.16のノードに対しては、10.0.0.9のIPアドレス� ��持つ中継ノードが最も配送確率が高く、該� ��継ノードまでのメトリックは1、該中継ノー ドが持つ配送確率は0.6であるとわかる。また 、該中継ノードへ到達するために転送すべき 次ホップノードとして、IPアドレスが10.0.0.4� �隣接ノードへ転送する必要があることが示� �れている。

 DTN転送部13は、DTN転送を行う機能を含ん� �いる。具体的には、隣接ノードから受信し� �バンドルをデータとして再構成し、自ノー� �に一旦蓄積を行う。そして転送すべき次ホ� �プが見つかった時点で、該データをバンド� �に分割し、次ホップへ転送を行う。ここで� �転送すべき次ホップはルーティングテーブ� �12を参照することにより決定する。また、バ ンドルの送受信は、TCP/IP部14を介して送受信� ��行う。

 TCP/IP部14は、DTN転送部13が送受信するバン ドルをIPパケットとして他ノードと送受信す� ��機能を含んでいる。各バンドルは、直接IP� �ケットのペイロードとして埋め込まれるの� �はなく、TCP(Transmission Control Protocol)やUDP(User  Datagram Protocol)などのトランスポートプロト コルのデータグラムとしてIPパケット化され� ��隣接ノードと送受信が行われる。

[第1の実施形態の動作]
 次に、図6を参照して、本実施形態において 、ノード1における配送確率データベース11B� �更新する動作について詳細に説明する。

 まず、配送確率計算部11Cは、定期的に配送� ��率データベース11Bを参照し(ステップ101)、� �在データベース上に配送確率が登録されて� �る宛先IPアドレスを調べ、各宛先への直接経 路が存在するかどうかをルーティングテーブ ル12を参照してチェックする(ステップ102)。
 次に、配送確率計算部11Cは、該宛先ノード� ��対応する現在有効な直接経路を自ノードが� ��っているかをルーティングテーブル12を参� �して調べる(ステップ103)。

 ここで、有効な直接経路が存在した場合(ス テップ103:YES)、配送確率計算部11Cは、該宛先� ��ードに対応する配送確率を1.0に設定し(ステ ップ104)、配送確率データベース11Bにおける� �当エントリを新しい配送確率へと更新し(ス� ��ップ107)、一連の配送確率データベース更新 処理を終了する。
 一方、有効な直接経路が存在しなかった場� ��(ステップ103:NO)、配送確率計算部11Cは、新� �い配送確率を計算する(ステップ105)。この際 、配送確率の計算においては、配送確率計算 部11Cの説明において例として挙げられたアル ゴリズムが用いられてもよいし、他のアルゴ リズムが用いられてもよい。

 続いて、配送確率計算部11Cは、ステップ105� ��計算された新しい配送確率が、予め設定さ� ��たしきい値未満であるか検査する(ステップ 106)。ここで、新しい配送確率がしきい値未� �の場合(ステップ106:YES)、配送確率計算部11C� �、配送確率を更新せずに該当エントリを消� �し(ステップ108)、一連の処理を終了する。
 一方、新しい配送確率がしきい値未満でな� ��場合(ステップ106:NO)、ステップ107へ移行し� �、配送確率データベース11Bにおける該当エ� �トリを新しい配送確率へと更新し(ステップ1 07)、一連の配送確率データベース更新処理を 終了する。

 次に、図7を参照して、本実施形態におい て、ノード1がバンドルを送信する際の経路� �決動作について詳細に説明する。

 まず、DTN転送部13で転送すべきバンドル� �受信したり、自ノードがソースノードとな� �て送信すべきバンドルが存在する場合(ステ� ��プ201)、DTN転送部13は、ルーティングテーブ� ��12を参照して、該バンドルの宛先ノードのIP アドレスに対応する経路エントリがあるか検 索し(ステップ202)、対応するエントリが存在� ��るかどうか判定する(ステップ203)。

 ここで、対応するエントリが存在した場� ��(ステップ202:YES)、該エントリに登録されて� ��る次ホップノードのIPアドレスを解決し、� �ホップとして設定する(ステップ204)。この後 、設定された次ホップに対してバンドルを転 送し(ステップ211)、一連の経路解決処理を終� ��する。

 一方、ステップ203において、対応するエン� ��リが存在しなかった場合(ステップ203:NO)、DT N転送部13は、宛先ノードまでの経路を解決す るための経路要求メッセージを経路・確率情 報交換部11Aを介して送出する(ステップ205)。
 経路要求メッセージは、フラッディングに� ��りネットワーク内に同報送信され、該宛先� ��ード自身、該宛先ノードへの直接経路を有� ��るノード、該宛先ノードへの確率的経路を� ��するノードのいずれかが該経路要求メッセ� ��ジを受信すると、これらノードのルーティ� ��グプロトコル部11は、経路・確率情報交換� �21Aにより、自ノードから宛先ノードへの経� �に関する情報(例えば、宛先ノード自身であ� ��こと、該宛先ノードへの直接経路または確� ��的経路の有無やその配送確率)を含む経路応 答メッセージをソースノード(この場合ノー� �1)に対して応答する。

 ステップ205の後、経路・確率情報交換部11A� ��、経路応答メッセージを受信するまで一定� ��間待機する(ステップ206)。
 ここで、待機時間内に経路応答メッセージ� ��受信せずにタイムアウトした場合(ステップ 206:NO)、一旦バンドルを蓄積し(ステップ208)、 一定時間後にステップ202へ戻って処理を繰り 返し実行する。

 一方、待機時間内に経路応答メッセージ� ��受信した場合(ステップ206:YES)、DTN転送部13� �、当該経路応答メッセージが、該宛先ノー� �への確率的経路を有するノードによって応� �されたものであるか、それ以外のノードに� �って応答されたものであるかを判定する(ス� ��ップ207)。

 ここで、該経路応答メッセージが該宛先� ��ードへの確率的経路を有するノードによっ� ��応答されたものではない場合(ステップ207:YE S)、DTN転送部13は、メッセージに含まれる宛� �ノードまでのホップ数が最も少なくなる経� �に対応する経路応答メッセージを選択し、� �経路応答メッセージを自ノード(ノード1)へ� �送したノードを次ホップとして設定する(ス� ��ップ209)。この後、ステップ211へ移行して、 設定された次ホップに対してバンドルを転送 し、一連の経路解決処理を終了する。

 一方、ステップ207において、該経路応答� ��ッセージが、該宛先ノードへの確率的経路� ��有するノードによって応答されたものであ� ��場合(ステップ207:NO)、DTN転送部13は、その経 路応答メッセージに含まれる宛先ノードへの 配送確率が最も高い経路応答メッセージを応 答したノードを中継ノードとして選択し、該 経路応答メッセージを自ノードへ転送したノ ードを次ホップとして設定する(ステップ210)� ��この後、ステップ211へ移行して、設定され� ��次ホップに対してバンドルを転送し、一連� ��経路解決処理を終了する。

[第1の実施形態の効果]
 このように、本実施形態では、ディレイト� ��ラントネットワーク内の各ノードにおいて� ��当該ノードのルーティングテーブルに登録� ��れている当該ノードから宛先ノードへの過� ��から現在までのエンド-エンドの経路の履歴 に基づいて、当該ノードにおける宛先ノード への配送確率をルーティングプロトコル部に より計算し、ソースノードにより、各ノード で計算された個々のノードにおける宛先ノー ドへの配送確率に基づいて、当該ソースノー ドから宛先ノードへ転送データを転送する際 の次ホップノードをDTN転送部により選択して いる。
 これにより、自ノードと直接隣接すること� ��ない場合であっても、直接隣接したノード� ��先に存在する別のノードに対して、自ノー� ��からの配送確率に反映させることかできる� ��このため、宛先への到達率を大幅に向上さ� ��ることが可能となり、高い信頼性を有する� ��ィレイトレラントネットワークを実現する� ��とが可能となる。

 また、本実施形態では、宛先ノードへの� ��送確率は、MANETルーティングプロトコルの� �接経路を持つことによって1.0と設定される� �設定された配送確率は、該宛先ノードへの� �接経路がなくなった後も、経路がなくなっ� �からの経過時間と、該直接経路のホップ数� �によって逓減し、確率的経路として保持さ� �る。このようにMANETルーティングプロトコル が設定する直接経路と連動することで、宛先 ノードと直接隣接することがなくても、配送 確率を計算することができる。これにより、 宛先ノードが自ノードと直接隣接することが なく、2ホップ以上離れて存在している場合� �あっても、宛先ノードまでの配送確率を持� �ことができ、さらに、その配送確率を直接� �接していないノードへと伝えることが可能� �なる。

 さらに、本実施形態では、バンドルを転� ��する際に、ルーティングテーブル上にヒッ� ��するエントリがない場合、ルーティングプ� ��トコル部における経路・確率情報交換部が� ��MANETルーティングプロトコルの経路要求メ� �セージに対する応答メッセージを受け取る� �で、自ノードから直接経路のあるノードの� �ち、最も高い宛先ノードへの配送確率を持� �ノードを探すことができる。すなわち、自� �ードと隣接するノード以外のノードのなか� �らも、宛先ノードへの配送確率を持つノー� �を探索することができる。これにより、配� �確率を持つノードと隣接するノード以外の� �ードであっても、該配送確率を知ることが� �きる。

[第2の実施形態]
 次に、図8を参照して、本発明の第2の実施� �態にかかるノードについて説明する。
 図8を参照すると、本実施形態にかかるノー ド2は、第1の実施形態のノード1の構成に加え て、ルーティングプロトコル部21内に確率キ� ��ッシュ部21Eが追加された構成となっている� ��これら機能部は、一般的な情報通信端末が� ��えるCPU、メモリ、各種インターフェース回� ��などを含むハードウェアとプログラムやア� ��リケーションからなるソフトウェアとが協� ��して実現される。

 なお、経路・確率情報交換部21A、経路計� ��・設定部21D、ルーティングテーブル22、DTN� �送部23、TCP/IP部24は、ノード1における経路・ 確率情報交換部11A、経路計算・設定部11D、ル ーティングテーブル12、DTN転送部13、TCP/IP部14 と同等であるため、ここでの説明は省略する 。

 確率キャッシュ部21Eは、経路・確率情報交� ��部21Aを介して、経路応答メッセージにより� ��得した他のノードが持つ配送確率をキャッ� ��ュとして配送確率データベース21Bへ格納す� ��機能を含んでいる。
 配送確率データベース21Bは、第1の実施形態 におけるノード1の配送確率データベース11B� �機能に加え、確率キャッシュ部21Eによりキ� �ッシュとして設定された配送確率情報を格� �する機能を含む。キャッシュされた配送確� �も、通常に登録されている配送確率と同様� �他のノードからの経路要求メッセージに応� �する形で経路・確率情報交換部21Aから返送� �知することが可能である。

 図9に示す配送確率データベース21Bの構成 例を参照すると、各配送確率のエントリにお いて、該エントリがキャッシュした配送確率 であるかどうかを判別するキャッシュフラグ が設定されている。キャッシュフラグが0で� �る場合、該エントリはキャッシュした配送� �率ではないことを示し、1である場合、キャ� ��シュした配送確率であることを示す。さら� ��、キャッシュフラグが1の場合はライフタイ ムが設定され、該エントリの残り有効時間が 示されている。例えば、宛先IPアドレスが10.0 .0.31であるノードに対する配送確率は、キャ� ��シュしたエントリであり、配送確率が0.6、� ��イフタイムは10秒であることがわかる。

 配送確率計算部21Cは、第1の実施形態におけ るノード1の配送確率計算部11Cの機能に加え� �配送確率データベース21Bにおいて、キャッ� �ュフラグが1であるエントリに対しても配送� ��率を更新する機能を含んでいる。
 具体的には、ライフタイムを時間の経過と� ��もに更新していき、ライフタイムが0以下に なった時点で該エントリを消滅させる。また 、ライフタイムが0になる前においても配送� �率の更新を定期的に行う。例えば、キャッ� �ュ元のノードからのホップ数やキャッシュ� �た時刻からの経過時間に基づいて配送確率� �逓減させる方法などが考えられる。

[第2の実施形態の動作]
 次に、図10を参照して、本実施形態におい� �、ノード2における配送確率データベースを� ��新する動作について説明する。

 まず、配送確率計算部21Cは、定期的に配送� ��率データベース21Bを参照し(ステップ301)、� �ータベース上に登録されている各エントリ� �対し、該エントリのキャッシュフラグが0で� ��るかどうかをチェックする(ステップ302)。
 ここで、キャッシュフラグが0である場合(� �テップ302:YES)、配送確率計算部11Cは、前述し た図6のステップ102以降の処理を実行し(ステ� ��プ303)、一連の配送確率データベース更新処 理を終了する。

 一方、キャッシュフラグが1である場合(ス� �ップ302:NO)、配送確率計算部21Cは、当該エン� ��リのライフタイムを前回更新時刻からの経� ��時間に基づいて更新する(ステップ304)。
 次に、配送確率計算部21Cは、ステップ304の� ��果、ライフタイムが0以下になるかどうかを チェックする(ステップ305)。

 ここで、ライフタイムが0以下であった場合 (ステップ305:YES)、配送確率計算部21Cは、該エ ントリは無効なエントリとして消去し(ステ� �プ306)、一連の配送確率データベース更新処� ��を終了する。
 一方、ライフタイムが0より大きい場合、配 送確率計算部21Cは、前述した図6のステップ10 5以降の処理を実行し(ステップ307)、一連の配 送確率データベース更新処理を終了する。

[第2の実施形態の効果]
 このように、本実施形態では、確率キャッ� ��ュ部が経路・確率情報交換部を介して経路� ��答メッセージにより取得した他のノードが� ��つ配送確率をキャッシュとして配送確率デ� ��タベースへ格納する。そして、キャッシュ� ��れた配送確率も通常登録されている配送確� ��と同様に、他のノードからの経路要求メッ� ��ージに応答する形で通知することが可能で� ��る。こうすることにより、経路要求メッセ� ��ジの送信量を下げることや、経路要求メッ� ��ージを送信するノードが、宛先ノードへの� ��送確率を持つノードを発見するまでの時間� ��短縮する効果が期待できる。