以下、具体的な実施形態を参照しながら� ��本発明について説明する。当業者であれば� ��本発明の記載を基に、多様な異なる実施形� ��を採り得るであろうし、本発明は、説明の� ��めに図示された実施形態に限定されるもの� ��はない。

(第1の実施の形態)
 図1は、本発明の第1実施形態の通信ネット� �ークシステム101の概要を示すものである。� �1において、通信ネットワークシステム101は� ��ノードA、ノードB、ノードC、…、ノードW、 ノードX、ノードY、ノードZから構成されてい る。通信ネットワークシステム101は、DTN(Delay /Disruption Tolerant Network)や無線アドホックネ� �トワークのような、モバイルマルチホップ� �ネットワーク環境のものである。各ノードA~ Zでは、例えば無線を使って、転送データを� �ンドルと呼ばれる単位サイズに分割し、バ� �ドル単位で宛先ノードへの転送処理を行っ� �いる。各ノードA~Zの数や配置は任意であり� �また、各ノードA~Zは、移動することができ� �。

 図2は、各ノードA~Zの構成を示すものであ る。図2において、各ノードA~Zは、確率ルー� �ィングプロトコル部151と、ルーティングテ� �ブル152と、DTN転送部153と、TCP/IP転送部154と� �ら構成される。

 確率ルーティングプロトコル部151は、ル� ��ティングテーブル152のエントリを作成する� ��めに、隣接ノードと経路制御情報を交換し� ��経路を作成する機能を備える。

 確率ルーティングプロトコル部151は、配� ��確率計算部161と、配送確率データベース(DB) 162と、配送確率交換部163と、配送確率受付判 断部164と、経路計算部165とから構成される。

 配送確率計算部161は、宛先ノードへの配� ��確率を計算し、計算された配送確率を配送� ��率データベース162へ登録する機能を備える� ��配送確率の計算アルゴリズムの例としては� ��隣接する/しないに基づく計算方法(非特許� �献1)や、経路履歴に基づく計算方法(特許文� �1)などが挙げられる。なお、配送確率の計算 方法としては、これに限定されるものではな く、どのような計算方法を用いても良い。

 配送確率データベース162は、配送確率計� ��部161によって計算された配送確率をデータ� ��ースとして蓄積する機能を備える。配送確� ��データベース162は、後に説明するように、� ��ノードが計算した配送確率データベースと� ��他ノードから受信した配送確率データベー� ��とに分かれている。

 配送確率交換部163は、隣接ノードに対し� ��自ノードがもつ宛先ノードへの配送確率を� ��信する機能および隣接ノードから送信され� ��その隣接ノードがもつ宛先ノードへの配送� ��率を受信する機能を備える。この配送確率� ��情報は、SVメッセージとして送受される。� �発明の第1の実施形態では、このとき、宛先� ��ードへの配送確率と共に、その宛先ノード� ��対する次ホップノードが含められる。すな� ��ち、自ノードのもつ宛先ノードへの配送確� ��を送信する際は、配送確率データベース162� ��参照し、自ノードが計算した宛先ノードへ� ��配送確率を送信すると同時に、その宛先ノ� ��ドに対する次ホップノードを一緒に送信す� ��。また、隣接ノードからは、その隣接ノー� ��が計算した宛先ノードへの配送確率と同時� ��、その宛先ノードに対する次ホップノード� ��一緒に受信する。

 配送確率受付判断部164は、配送確率交換� ��163を介して隣接ノードから受信した配送確� ��を、隣接ノードから受信した宛先ノードへ� ��配送確率として配送確率データベース162に� ��録するかどうかを判断する機能を備える。� ��発明の第1の実施形態では、隣接ノードが計 算した宛先ノードへの配送確率と同時に、そ の宛先ノードに対する次ホップノードを一緒 に受信しており、配送確率受付判断部164は、 受信した次ホップノードと自ノードとが同一 であるかを調べ、次ホップノードと自ノード とが同一でない場合は、受信した配送確率を 配送確率データベース162に登録し、次ホップ ノードと自ノードとが同一である場合は、受 信した配送確率を配送確率データベース162に 登録しないようにしている。

 経路計算部165は、配送確率データベース1 62を参照して、各宛先ノードに対する次ホッ� ��ノードを決定し、ルーティングテーブル152� ��ルーティングエントリとして登録する。ル� ��ティングテーブル152には、各宛先ノードご� ��に、次ホップノードとその次ホップノード� ��対応するIPアドレスである次ホップIPアドレ スが登録される。

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

 なお、DTN転送部153は、ノードA2がDTN転送� �行う場合は必要な構成要素であるが、DTN転� �を行わない通常のTCP/IP転送のみを行うノー� �である場合は、必ずしも必要な構成要素で� �ない。

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

 上述のように、本発明の第1の実施形態の システムでは、各ノードA~Zは、宛先ノードへ の配送確率を計算し、隣接ノードに対して配 送確率を互いにSVメッセージとして交換して� ��る。このとき、各ノードA~Zが計算した宛先� ��ードへの配送確率を送信すると同時に、そ� ��宛先ノードに対する次ホップノードを一緒� ��送信している。そして、各ノードA~Zでは、� ��先ノードへの配送確率およびそのノードに� ��する次ホップノードを受信すると、次ホッ� ��ノードが自ノードと同一であるかどうかを� ��べ、次ホップノードと自ノードとが同一の� ��合には、配送確率データベース162に登録し� ��いようにしている。

 図3Aおよび図3Bは、配送確率データベース 162に登録される配送確率エントリの例を示す ものである。

 図3Aおよび図3Bを参照すると、配送確率デ ータベース162は、配送確率データベース(自� �ードが計算した配送確率)162a(図3A)と、配送� �率データベース(他ノードから受信した配送� ��率)162b(図3B)とに分かれている。

 ここで、ノードAの場合には、配送確率デ ータベース162aには、ノードAの配送確率計算� ��161が計算した配送確率が登録されている。� ��3Aを参照すると、ノードXに対する配送確率� ��「0.6」、ノードYに対する配送確率は「0.2」 、ノードZに対する配送確率は「0.3」である� �とが示されている。

 また、配送確率データベース162bには、ノ ードAが隣接ノード(ノードB、ノードC等)から� ��信した配送確率が登録されている。図3Bを� �照すると、宛先ノードに対する配送確率お� �びその配送確率を送信したノードおよびそ� �配送確率の有効期限が登録されている。例� �ば、ノードXに対しては2つのノードから配送 確率を受信しており、1つは配送確率が「0.4� �で、送信したノードはノードB、有効期限は� ��2008年8月18日17時10分49.500秒」であり、もう1� ��は配送確率が「0.1」で、送信したノードは� ��ードC、有効期限は「2008年8月18日17時11分10.0 00秒」であることがわかる。

 図2における経路計算部165は、図3Aおよび� ��3Bに示したような配送確率データベース162� �参照して、各宛先ノードに対する次ホップ� �ードを決定する。基本的には、配送確率デ� �タベース162中で、宛先ノードへの配送確率� �比較し、最も配送確率が大きいものを次ホ� �プノードとして決定する。

 例えば、自ノードが計算した配送確率デ� ��タベース162aおよび他ノードから受信した配 送確率データベース162bが図3Aおよび図3Bに示� ��ようなものであるとする。この場合、経路� ��算部165は、以下のようにして、各宛先ノー� ��に対する次ホップノードを決定し、図4に示 すように、ルーティングテーブル152に、ルー ティングエントリを登録する。

 まず、宛先ノードがノードXである場合、 図3Aの自ノードが計算した配送確率データベ� ��ス162aおよび図3Bの他ノードから受信した配� ��確率データベース162bを参照すると、配送確 率データベース162aに登録されているノードX� ��の配送確率は「0.6」、配送確率データベー� ��162bに登録されているノードXへの配送確率� �「0.4」と「0.1」である。したがって、配送� �率データベース162aに登録されている「0.6」� ��最も大きい配送確率である。このため、経� ��計算部165は、図4に示すように、その配送確 率を計算した自ノード(ノードA)を次ホップノ ードとしてルーティングテーブル152として登 録する。

 また、宛先ノードがノードYである場合、図 3Aの配送確率データベース162aに登録されてい るノードYへの配送確率は「0.2」、図3Bの配送 確率データベース162bに登録されているノー� �Yへの配送確率は「0.5」である。したがって� ��配送確率データベース162bに登録されている 「0.5」が最も大きい配送確率である。
 このため、経路計算部165は、図4に示すよう に、その配送確率を計算したノードであるノ ードCを次ホップノードとしてルーティング� �ーブル152に登録する。同様に、経路計算部16 5は、ノードZ,Wに対しては、それぞれ、図4に� ��すように、ノードA,ノードBを次ホップノー� ��としてルーティングテーブル152に登録する� ��

 図4は、ルーティングテーブル152に登録さ れるエントリの例を示すものである。

 例えば、ルーティングテーブル152がノー� ��Aのテーブルであるとすると、図4に示すよ� �に、ルーティングテーブル152には、各宛先� �ードごとに、次ホップノードとその次ホッ� �ノードに対応するIPアドレスである次ホップ IPアドレスが登録される。

 例えば、宛先ノードXおよび宛先ノードZ� �対しては、次ホップノードは自ノードであ� �ノードAで、次ホップIPアドレスは「10.0.0.1」 であることがわかる。また、宛先ノードYに� �しては、次ホップノードはノードCで、次ホ� ��プIPアドレスは「10.0.0.3」であり、ノードW� �対しては、次ホップノードはノードBで次ホ� ��プIPアドレスは「10.0.0.2」であることがわか る。宛先ノードがノードXまたはノードZであ� ��バンドルに対しては、そのバンドルを他の� ��接ノードへ転送せずに蓄積保持する。

 図5は、本発明の第1の実施形態の通信ネ� �トワークシステム101において、ノードAが配� ��確率を隣接ノードに送信する際の動作を示� ��フローチャートである。

 まず、ノードAにおいて、配送確率計算部 161で、配送確率を計算する(ステップS1)。そ� �て、配送確率計算部161は、既に同一宛先ノ� �ドに対する配送確率が配送確率データベー� �162に登録されているかどうかを調べ(ステッ� ��S2)、同一宛先ノードに対する配送確率が登� ��されている場合、配送確率データベース162� ��既存エントリにおける配送確率を更新し(ス テップS3)、同一宛先ノードに対する配送確率 が登録されていない場合は、配送確率を新規 登録する(ステップS4)。

 経路計算部165は、最大の配送確率を計算� ��たノードを、宛先ノードに対する次ホップ� ��ードとして設定する。ここで、最大の配送� ��率を計算したノードが自ノードであれば、� ��路計算部165は、自ノードを次ホップノード� ��して設定する(ステップS5)。配送確率交換部 163は、隣接ノードに配送確率と宛先ノードに 対するホップノードを含むSVメッセージをブ� ��ードキャストで送信する(ステップS6)。これ らの処理は、コンピュータのソフトウェアに より実現できる。

 図6は、本発明の第1の実施形態において� �ノードAが配送確率を隣接ノードから受信し� ��際の動作を示すフローチャートである。

 まず、ノードAにおいて、配送確率交換部 163が隣接ノードから配送確率のリストと宛先 ノードに対する次ホップノードを含むSVメッ� ��ージを受信する(ステップS101)。配送確率交� ��部263は受信した配送確率のリストを配送確� ��受付判断部164へ渡す。

 次に、配送確率受付判断部164は、ステッ� ��S101で受信した配送確率のそれぞれに対して 、その配送確率を配送確率データベース162へ 登録するかどうかの判断を行う。配送確率受 付判断部164は、配送確率と対になって送信さ れた次ホップノードを参照し、次ホップノー ドが自ノードと同一であるかを調べる(ステ� �プS102)。

 ステップS102において、次ホップノードが 自ノードと同一ではない場合、配送確率受付 判断部164は、既に同じノードから同一宛先ノ ードに対する配送確率が配送確率データベー ス162に登録されているかどうかを調べる(ス� �ップS103)。

 ステップS103において、既に同一のノード から同一宛先ノードに対する配送確率が登録 されている場合、配送確率受付判断部164は、 配送確率データベース162の既存エントリにお ける配送確率および次ホップノードを更新す る(ステップS104)。また、ステップS103におい� �、まだ同一のノードから同一宛先ノードに� �する配送確率が登録されていない場合は、� �送確率受付判断部164は、配送確率データベ� �ス162に受信した配送確率および次ホップノ� �ドを新規登録する(ステップS105)。

 ステップS102において、次ホップノードが 自ノードと同一である場合、配送確率受付判 断部164は、既に同じノードから同一宛先ノー ドに対する配送確率が登録されているかどう かを調べる(ステップS106)。

 ステップS106において、既に同一のノード から同一宛先ノードに対する配送確率が登録 されている場合、配送確率受付判断部164は、 配送確率データベース162の既存エントリを削 除する(ステップS107)。また、ステップS106に� �いて、まだ同一のノードから同一宛先ノー� �に対する配送確率が登録されていない場合� �、配送確率受付判断部164は、ステップS101で� ��信した配送確率を無視し(ステップS108)、終� ��する。

 ステップS104、S105、S107の後、これらのス� ��ップにより配送確率の更新/登録/削除が行� �れた結果、宛先ノードに対する最大の配送� �率は変化したかどうかを調べる(ステップS109 )。

 ステップS109において、変化があった場合 、経路計算部165は、最大の配送確率を計算し たノードを、宛先ノードに対する次ホップノ ードとして設定する。ここで、最大の配送確 率を計算したノードが自ノードであれば、経 路計算部165は、自ノードを次ホップノードと して設定する(ステップS110)。これらの処理は 、コンピュータのソフトウェアにより実現で きる。

 例えば、図7に示すように、ノードAとノ� �ドBとのメッセージの送受信を行ったとする� ��ここでは、ノードA、Bは、自ノードが計算� �た配送確率と同時に、そのノードに対する� �ホップノードを一緒に送信している。

 図4では、ノードBがSVメッセージ「P(Y)=0.5, N(Y)=A」を送信している(メッセージM1)。このSV メッセージM1中、「P(Y)=0.5」は、ノードYへの� ��送確率が「0.5」であることを示している。� ��た、「N(Y)=A」は、そのノード(ノードY)に対� ��る次ホップノードがノードAであることを示 している。このメッセージを受信したノード Aは、配送確率と対になって送信されている� �ホップノードがN(Y)=Aとなっており、自ノー� �と同一である判断する。よって、この配送� �率は、ノードAの配送確率データベース162に� ��登録されない。

 これに対して、ノードBが送信したその他 のSVメッセージ「P(X)=0.8,N(X)=B」(メッセージM2) 、「P(Z)=0.1,N(Z)=B」(メッセージM3)は、次ホッ� �ノードN(X),N(Z)がノードAではないため、ノー� ��Aの配送確率データベース162に登録される。

 上述のように、本発明の第1の実施形態で は、各ノードA~Zは、宛先ノードへの配送確率 を計算し、隣接ノードに対して配送確率を互 いに交換する際に、各ノードA~Zが計算した宛 先ノードへの配送確率を送信すると同時に、 その宛先ノードに対する次ホップノードを一 緒に送信している。そして、各ノードA~Zでは 、宛先ノードへの配送確率およびそのノード に対する次ホップノードを受信すると、次ホ ップノードが自ノードと同一であるかを調べ 、次ホップノードと自ノードとが同一の場合 には、配送確率データベース162に登録しない ようにしている。これにより、配送確率を隣 接ノードへ送信するためのメッセージをロス した場合でも、ルーティングループの発生が 防止できる。このことについて、図8に示す� �を参照しながら示す。

 図8を参照すると、互いに隣接しているノ ードAとノードBが示されている。ノードAとノ ードBはそれぞれ、定期的に、配送確率と次� �ップノードを含むSVメッセージを送信してい る。ここでは、宛先ノードXにバンドルを送� �場合について説明する。

 まず初期状態として、時刻T0において、� �ードAにおけるノードXへの配送確率は「0.7」 であると計算されており、また、他のノード から受信した配送確率はないものとする。し たがって、時刻T0においてノードAにおけるノ ードX宛てのバンドルを転送するための次ホ� �プは、自ノードであるノードAと設定される� ��

 また、同じ時刻T0において、ノードBでは� ��ノードXへの配送確率は「0.5」であると計算 されており、また、他のノードから受信した 配送確率はないものとする。したがって、時 刻T0においてノードBにおけるノードX宛ての� �ンドルを転送するための次ホップは、自ノ� �ドであるノードBと設定される。

 次に、時刻T1において、ノードAにおいてノ� ��ドXへの配送確率が再計算され、「0.7」から 「0.6」へ更新されるものとする。更新された 配送確率は、直ちにSVメッセージによってノ� ��ドBを含む隣接ノードへブロードキャストさ れる。ここで、配送確率P(X)と一緒にノードA� ��おけるノードXへの次ホップノードN(X)も送� �される。
すなわち、「P(X)=0.6,N(X)=A」がノードAから送� �される(メッセージM101)。

 ノードBは時刻T1において、ノードAからノ ードXへの更新された配送確率を含むメッセ� �ジM101受信すると、その配送確率を配送確率� ��ータベース162へ登録するかどうかを判断す� ��ため、対になって送信されたノードXへの次 ホップノードが自ノードと同一であるかを調 べる。調べた結果、N(X)=Aであり自ノード(ノ� �ドB)と同一ではないため、受信した配送確率 の値である「0.6」と、その配送確率を送信し たノードであるノードAを配送確率データベ� �ス162へ登録する。すなわち、図8では、「0.6( A)」と登録されている。同時に、ノードBが計 算した配送確率「0.5」と、ノードAから受信� �た配送確率「0.6」とを比較し、「0.6」の方� �大きいため、この配送確率を送信したノー� �であるノードAを、ノードXへの次ホップとし て設定する。実際には、ノードA以外の隣接� �ードから受信した配送確率も比較するが、� �の例では簡単のために、ノードBにはノードA だけから配送確率を受信しているものとして 説明する。

 次に、時刻T2において、ノードBにおいて� ��ードXへの配送確率が再計算され、「0.5」か ら「0.4」へ更新されるものとする。更新後、 計算した配送確率「0.4」と、受信した配送確 率「0.6」とを比較し、「0.6」の方が大きいた め、ノードXへの次ホップはノードAのままに� ��る。更新された配送確率は、ノードBから、 直ちにSVメッセージによってノードAを含む隣 接ノードへブロードキャストされる。ここで 、配送確率P(X)と一緒にノードBにおけるノー� ��Xへの次ホップノードN(X)も送信される。す� �わち、ノードBからは、「P(X)=0.4,N(X)=A」が送� ��される(メッセージM102)。

 ノードAは時刻T2において、ノードBからノ ードXへの更新された配送確率を含むメッセ� �ジM102を受信すると、その配送確率を配送確� ��データベース162へ登録するかどうかを判断� ��るため、対になって送信されたノードXへの 次ホップノードが自ノードと同一であるかを 調べる。調べた結果、「N(X)=A」であり自ノー ド(ノードA)と同一であるため、受信した配送 確率は配送確率データベース162へ登録しない と判断する。

 次に、時刻T3において、ノードAにおいて� ��ードXへの配送確率が再計算され、「0.6」か ら「0.2」へ更新されるものとする。そして、 ノードAは、時刻T1における動作と同様に、更 新された配送確率をSVメッセージによってブ� ��ードキャストする。すなわち、ノードAから は、「P(X)=0.2,N(X)=A」が送信される(メッセー� �M103)。しかしながら、ここで、ノードBは何� �かの原因により、このメッセージM103を受信� ��きなかったとする。

 時刻T3において、ノードAが送信したSVメ� �セージ(メッセージM103)をノードBが受信でき� ��かった場合、ノードBでは何も状態が変化し ないため、ノードXへの次ホップ設定はノー� �Aのままとなる。

 次に、時刻T4において、ノードBにおいて� ��ードXへの配送確率が再計算され、「0.4」か ら「0.3」へ更新されるものとする。更新され た配送確率は、ノードBから、直ちにSVメッセ ージによってノードAを含む隣接ノードへブ� �ードキャストされる。ここで、配送確率P(X)� ��一緒にノードBにおけるノードXへの次ホッ� �ノードN(X)も送信される。すなわち、ノードB からは、「P(X)=0.3,N(X)=A」が送信される(メッ� �ージM104)。

 ノードAは時刻T4において、ノードBからノ ードXへの更新された配送確率を含むメッセ� �ジM104を受信すると、その配送確率を配送確� ��データベース162へ登録するかどうかを判断� ��るため、対になって送信されたノードXへの 次ホップノードが自ノードと同一であるかを 調べる。調べた結果、「N(X)=A」であり自ノー ド(ノードA)と同一であるため、受信した配送 確率は配送確率データベース162へ登録しない と判断する。

 次に、時刻T5において、ノードAにおいて� ��ードXへの配送確率が再計算され、「0.2」か ら「0.1」へ更新されるものとする。そしてノ ードAは、更新された配送確率をSVメッセージ によってブロードキャストする。ここで、配 送確率P(X)と一緒にノードAにおけるノードXへ の次ホップノードN(X)も送信される。すなわ� �、「P(X)=0.1,N(X)=A」がノードAから送信される( メッセージM105)。時刻T5で送られたメッセー� �M105は正常にノードBが受信できたものとする 。

 ノードBは時刻T5において、ノードAからノ ードXへの更新された配送確率を含むSVメッセ ージ(メッセージM105)を受信すると、その配送 確率を配送確率データベース162へ登録するか どうかを判断するため、対になって送信され たノードXへの次ホップノードが自ノードと� �一であるかを調べる。調べた結果、「N(X)=A� �であり自ノード(B)と同一ではないため、受� �した配送確率の値である「0.1」と、その配� �確率を送信したノードであるAを配送確率デ� ��タベース162へ登録する。すなわち、図8では 0.1(A)と登録されている。同時に、ノードBが� �算した配送確率「0.3」と、受信した配送確� �「0.1」とを比較し、「0.3」の方が大きいた� �、自ノードであるノードBを、ノードXへの次 ホップとして設定する。

 以上の例は、時刻T0以降いずれの時間に� �いてもノードAとノードBとの間でルーティン グループ状態が発生していない。これは、受 信した配送確率を登録するかしないかの判断 を、一緒に受信した配送確率に対応する次ホ ップノードに基づいて行っているため、2ノ� �ド間のループが起こる可能性のあるノード� �次ホップノードとして設定する可能性をな� �しているからである。

 以上説明したように、本発明の第1の実施 形態によれば、配送確率を送信するノードは 、隣接ノードへ配送確率を送信する際に、一 緒に対応する宛先ノードに対する次ホップノ ードを送信し、配送確率を受信したノードは 、受信した次ホップノードが自ノードと同一 であるかを調べ、同一である場合は受信した 配送確率を登録しないことにより、対応する 宛先ノードへの次ホップノードとして該配送 確率を送信したノードが選択されないように している。このため、配送確率に基づくルー ティング方法において、2ノード間のルーテ� �ングループを防止することができる。

(第2の実施の形態)
 次に、本発明の第2の実施の形態について図 面を参照して詳細に説明する。前述の第1の� �施の形態では、2ノード間のルーティングル� ��プを防止するのに有効であったが、3ノード 以上のルーティングループは防止することが できなかった。これに対して、この実施形態 は、3ノード以上のルーティングループを防� �できるようにしている。

 本発明の第2の実施形態のシステムは、図 1に示した前述の第1の実施形態の通信ネット� ��ークシステム101と同様に、ノードA、ノード B、ノードC、…、ノードW、ノードX、ノードY� ��ノードZから構成されている。

 図9は、本発明の第2の実施形態のノードA~ Zの構成を示すものである。本発明の第2の実� ��形態においては、各ノードA~Zは、確率ルー� ��ィングプロトコル部251と、ルーティングテ� ��ブル252と、DTN転送部253と、TCP/IP転送部254と� ��ら構成される。

 確率ルーティングプロトコル部251は、配� ��確率計算部261と、配送確率データベース(DB) 262と、配送確率交換部263と、配送確率受付判 断部264と、経路計算部265と、MANETルーティン� ��プロトコル266とから構成される。

 DTN転送部253、TCP/IP転送部254の機能につい� ��は、前述の第1の実施形態におけるDTN転送部 153、TCP/IP転送部154と同様であるため、その説 明は省略する。また、確率ルーティングプロ トコル部251における、配送確率計算部261、配 送確率データベース(DB)262は、前述の第1の実� ��形態の確率ルーティングプロトコル部151に� ��ける、配送確率計算部161と、配送確率デー� ��ベース(DB)162と同様であるため、その説明は 省略する。

 配送確率交換部263は、第1の実施形態にお ける配送確率交換部163のもつ配送確率を送受 信する機能において、配送確率と共に、対応 するルーティングテーブル252における次ホッ プノード列を一緒に送信する。次ホップノー ド列とは、自ノードから宛先ノードまでの転 送経路における自ノードからnホップ目(n=整� �)までのノードを列挙したリストである。例� ��ば、ノードAからノードXまでの転送経路が� �ノードA,ノードB、ノードD、ノードE、ノード Xの順であり、ホップ数nが(n=2)である場合、� �ホップノード列は、ノードAから2ホップ目ま でのノードである、ノードB,ノードDとなる。

 図10は、配送確率交換部263によって送信� �れる配送確率および次ホップノード列のリ� �トの例を示すものである。

 図10を参照すると、ノードAとノードBとノ ードCが互いに隣接しており、ノードA、ノー� ��B、ノードCから配送確率および次ホップノ� �ド列のリストがブロードキャストされてい� �。この例では、ノードX,Y,Zへの配送確率P(X),P (Y),P(Z)と次ホップノード列N(X),N(Y),N(Z)とがそ� �ぞれ対になって送信されている。ここで、� �ホップノードが自ノードの場合は、2ホップ� ��のノードはないので、自ノードであるAだけ が自ノード列として入れられる。

 配送確率受付判断部264は、第1の実施形態 における配送確率受付判断部164と同様に、隣 接ノードから受信した配送確率を配送確率デ ータベース262における他ノードから受信した 配送確率として登録するかどうかを判断する 機能を備える。配送確率受付判断部264は、こ の判断基準として、配送確率交換部263が配送 確率と対で受信した次ホップノード列に自ノ ードが含まれる場合は登録しない、という基 準を用いる。

 配送確率を送受信する機能において、例� ��ば図10では、ノードBが配送確率「P(Y)=0.5」� �送信しているが(メッセージM201)、このメッ� �ージを受信したノードAは、その配送確率と� ��になって送信されている次ホップノード列� ��「N(Y)=A-F」となっており、自ノードが含ま� �ているため、その配送確率を配送確率デー� �ベース262へ登録しない。ノードBはまた、配� ��確率「P(Z)=0.1」を送信しているが(メッセー� ��M202)、このメッセージを受信したノードCは� ��その配送確率と対になって送信されている� ��ホップノード列が「N(Z)=ノードE-C」となっ� �おり、自ノード(ノードC)が含まれているた� �、その配送確率を配送確率データベース262� �登録しない。

 同様にして、ノードAが送信した配送確率 「P(Y)=0.2」(メッセージM203),P(Z)=0.3(メッセージ M204)はそれぞれノードC,ノードBにおいて配送� ��率データベース262へ登録されない。また、� ��ードCが送信した配送確率「P(X)=0.3」(メッセ ージM205)はノードAおよびノードBにおいて配� �確率データベースへ登録されない。

 MANETルーティングプロトコル266は、各宛� �ノードに対する次ホップノード列を計算し� �ルーティングテーブル252へ登録する。MANETル ーティングプロトコル266で動作するルーティ ングプロトコルの例として、OLSRが挙げられ� �。OLSRは、リンクステート型のルーティング� ��ロトコルであるため、次ホップノード列の� ��算を行うことが可能である。

 また、MANETルーティングプロトコル266に� �ってルーティングテーブル252に登録される� �ントリと、経路計算部265によって登録され� �エントリが競合する場合、エンド-エンド間� ��経路であるMANETルーティングプロトコル266� �よって登録されるエントリを優先するのが� �般的である。

 ルーティングテーブル252は、図4に示した ルーティングテーブル152と比べて、宛先ノー ドに対する次ホップではなく、次ホップノー ド列が登録され、宛先ノードに対する次ホッ プIPアドレスではなく、次ホップIPアドレス� �が登録される点が異なる。図11にルーティン グテーブル252に登録されるエントリの例を示 す。

 図11のルーティングテーブル252を参照す� �と、宛先ノードYに対しては、次ホップノー� ��列はノードC、ノードDの順であり、次ホッ� �IPアドレスは、「10.0.0.3」、「10.0.0.4」の順� �あることがわかる。同様にして、宛先Zに対� ��ては、次ホップノード列はノードB、ノード Eの順であり、次ホップIPアドレスは、「10.0.0 .2」、「10.0.0.5」の順であることがわかる。

 図12は、本発明の第2の実施形態において� ��ノードAが配送確率を隣接ノードに送信する 際の動作を示すフローチャートである。

 まず、ノードAにおいて、配送確率計算部 261で、配送確率を計算する(ステップS201)。そ して、配送確率計算部261は、既に同一宛先ノ ードに対する配送確率が配送確率データベー ス262に登録されているかどうかを調べ(ステ� �プS202)、同一宛先ノードに対する配送確率が 登録されている場合、配送確率データベース 262の既存エントリにおける配送確率を更新し (ステップS203)、同一宛先ノードに対する配送 確率が登録されていない場合は、配送確率を 新規登録する(ステップS204)。

 経路計算部265は、最大の配送確率を計算� ��たノードを、宛先ノードに対する次ホップ� ��ードとして設定する。ここで、最大の配送� ��率を計算したノードが自ノードであれば、� ��路計算部265は、自ノードを次ホップノード� ��して設定する(ステップS205)。配送確率交換� ��263は、隣接ノードに配送確率と宛先ノード� ��対する次ホップノード列を含むSVメッセー� �をブロードキャストで送信する(ステップS206 )。これらの処理は、コンピュータのソフト� �ェアにより実現できる。

 図13は、本発明の第2の実施の形態におい� ��ノードが配送確率を隣接ノードから受信し� ��際の動作を示すフローチャートである。

 まず、各ノードにおいて、配送確率交換� ��263が隣接ノードから配送確率のリストと宛� ��ノードに対する次ホップノード列を含むSV� �ッセージを受信する(ステップS301)。配送確� �交換部263は受信した配送確率のリストを配� �確率受付判断部264へ渡す。

 次に、配送確率受付判断部264は、ステッ� ��S301で受信した配送確率のそれぞれに対して 、その配送確率を配送確率データベース262へ 登録するかどうかの判断を行う。配送確率と 対になって送信された次ホップノード列を参 照し、その次ホップノード列に自ノードが含 まれるかどうかを調べる(ステップS302)。

 ステップS302において、次ホップノード列 に自ノードが含まれていない場合、既に同じ ノードから同一宛先ノードに対する配送確率 が配送確率データベース262に登録されている かどうかを調べる(ステップS303)。

 ステップS303において、既に同一のノード から同一宛先ノードに対する配送確率が登録 されている場合、配送確率受付判断部264は、 配送確率データベース262の既存エントリにお ける配送確率および次ホップノードを更新す る(ステップS304)。また、ステップS303におい� �、まだ同一のノードから同一宛先ノードに� �する配送確率が登録されていない場合は、� �送確率受付判断部264は、配送確率データベ� �ス262に受信した配送確率および次ホップノ� �ドを新規登録する(ステップS305)。

 ステップS302において、次ホップノード列 に自ノードが含まれている場合、既に同じノ ードから同一宛先ノードに対する配送確率が 登録されているかどうかを調べる(ステップS3 06)。

 ステップS306において、既に同一のノード から同一宛先ノードに対する配送確率が登録 されている場合、配送確率受付判断部264は、 配送確率データベース262の既存エントリを削 除する(ステップS307)。また、ステップS306に� �いて、まだ同一のノードから同一宛先ノー� �に対する配送確率が登録されていない場合� �、配送確率受付判断部264は、ステップS301で� ��信した配送確率を無視し(ステップS308)、終� ��する。

 ステップS304、S305、S307の後、これらのス� ��ップにより配送確率の更新/登録/削除が行� �れた結果、宛先ノードに対する最大の配送� �率は変化したかどうかを調べる(ステップS309 )。

 ステップS309において、変化があった場合 、経路計算部265は、最大の配送確率を計算し たノードを、宛先ノードに対する次ホップノ ードとして設定する。ここで、最大の配送確 率を計算したノードが自ノードであれば、経 路計算部265は、自ノードを次ホップノードと して設定する(ステップS310)。これらの処理は 、コンピュータのソフトウェアにより実現で きる。

 この実施形態では、配送確率交換部263が� ��配送確率を送信する際に、一緒に対応する� ��先ノードに対する次ホップノード列を送信� ��る。また配送確率を受信したノードは、配� ��確率受付判断部264が一緒に受信した次ホッ� ��ノード列に自ノードが含まれるかどうかを� ��べ、含まれている場合は受信した配送確率� ��配送確率データベース262に登録しないこと� ��より、経路計算部265によって対応する宛先� ��ードへの次ホップノードとしてその配送確� ��を送信したノードが選択されないようにす� ��。

 このようにすることにより、ループが起� ��る可能性のあるノードを次ホップノードと� ��て設定することがなくなる。

 前述の第1の実施の形態では、2ノード間� �ルーティングループを防止するのに有効で� �ったが、3ノード以上のルーティングループ� ��防止することができなかった。これに対し� ��、この実施形態では、3ノード以上のルーテ ィングループは防止することができる。

 具体的には、配送確率交換部263が送信す� ��次ホップノード列でnホップ目までのノード を送信する場合、(n+1)ノード間のループを防� ��することができ、nの値を変更することで任 意の数のノード間でのループを防止すること が可能になる。例えば、n=2として2ホップ目� �での次ホップノード列を送信する場合は、3� ��ード間までのループを防止することができ� ��。

 本発明の第2の実施形態によれば、配送確 率を送信するノードは、隣接ノードへ配送確 率を送信する際に、対応する宛先ノードに対 する次ホップノード列を送信し、配送確率を 受信したノードは、受信した次ホップノード 列に自ノードが含まれるかどうかを調べ、含 まれる場合は受信した配送確率を登録しない ことにより、対応する宛先ノードへの次ホッ プノードとして該配送確率を送信したノード が選択されないようにしているので、配送確 率に基づくルーティング方法において、任意 の数のノード間のルーティングループを防止 することができる。また、次ホップノード列 の送信において、何ホップ目までのノードを 送信するかを変更することによって、防止す る対象となるルーティングループのノード数 を調整することができる。

 本発明は、上述の実施形態に限定されず� ��本発明の主旨を逸脱しない範囲で、適宜修� ��や変更が可能である。