(57)【要約】【課題】通信経路の品質を高く維持するアドホックネットワークシステムを提供。【解決手段】アドホックネットワークシステムにおける通信経路を構成して中継機能を有するそれぞれの携帯端末装置の識別情報を記載する経路対応表２１１と、隣接する携帯端末装置と、該携帯端末装置との間の接続性を表す接続確率とを保持する周辺端末リスト２１２と、通信経路を構成する携帯端末装置の内、自端末から１ホップの携帯端末装置に２および３ホップ目で至る経路中のそれぞれの携帯端末装置の識別情報と該それぞれの携帯端末装置における接続確率の積とを該経路毎に保持する推奨保全経路リスト２１３と、を備える。周辺端末リスト２１２に含まれる携帯端末装置に関する接続確率が所定値以下となった場合に、推奨保全経路リスト２１３を参照して新たな通信経路を設定すると共に、この新たな通信経路に従って経路対応表２１１を書き換える。【選択図】図１
2007243575.tif 000002
【特許請求の範囲】
【請求項１】
アドホックネットワークシステムを構成するそれぞれの携帯端末装置が、隣接する携帯端末装置との間の接続性を表す接続確率を保持し、該接続確率の変化に基づいて通信経路の変更を行うことを特徴とするアドホックネットワークシステム。
【請求項２】
前記通信経路を構成して中継機能を有するそれぞれの携帯端末装置において、所定の携帯端末装置に関する前記接続確率が所定値以下となった場合に、前記所定の携帯端末装置の上流に位置する携帯端末装置に保持されている代用となる通信経路の情報に基づいて新たな通信経路を設定することを特徴とする請求項１記載のアドホックネットワークシステム。
【請求項３】
前記代用となる通信経路の情報は、該通信経路を構成するそれぞれの携帯端末装置に関する前記接続確率の積を含み、該積が最大となる前記通信経路を前記新たな通信経路に設定することを特徴とする請求項２記載のアドホックネットワークシステム。
【請求項４】
前記接続確率は、隣接リンクの受信信号強度、希望波信号電力対干渉波電力比、信号対雑音比、搬送波対干渉比、隣接チャネル干渉電力比、ビット誤り率、スループット、遅延時間、輻輳状態、媒体アクセス制御層における自動再送要求回数、自端末のバッテリー残量、自端末と隣接端末との距離のいずれか、またはこれらの組み合わせから算出されることを特徴とする請求項１〜３のいずれか一に記載のアドホックネットワークシステム。
【請求項５】
アドホックネットワークシステムを構成して中継機能を有する携帯端末装置であって、  隣接する携帯端末装置から該携帯端末装置との間の接続性を表す接続確率を受け取るリンク監視部と、
受け取った前記接続確率が所定値以下であるか否かを判断する切断予期部と、
前記接続確率が所定値以下となった場合に、保持されている代用となる通信経路の情報に基づいて新たな通信経路を設定する経路選択部と、
を備えることを特徴とする携帯端末装置。
【請求項６】
前記代用となる通信経路の情報は、該通信経路を構成するそれぞれの携帯端末装置に関する前記接続確率の積を含み、
前記経路選択部は、該積が最大となる前記通信経路を前記新たな通信経路として設定することを特徴とする請求項５記載の携帯端末装置。
【請求項７】
前記アドホックネットワークシステムの通信経路を構成するそれぞれの携帯端末装置の識別情報を記載する経路対応表と、
前記隣接する携帯端末装置と、前記携帯端末装置との間の接続性を表す接続確率とを保持する周辺端末リストと、
前記通信経路を構成する携帯端末装置の内、自端末から１ホップの携帯端末装置に２および３ホップ目で至る経路中のそれぞれの携帯端末装置の識別情報と該それぞれの携帯端末装置における前記接続確率の積とを該経路毎に保持する保全経路リストと、
を備え、
前記経路選択部は、前記保全経路リストを参照して前記新たな通信経路を設定し、
前記経路対応表は、前記新たな通信経路にしたがって書き換えられることを特徴とする請求項６記載の携帯端末装置。
【請求項８】
前記接続確率は、隣接リンクの受信信号強度、希望波信号電力対干渉波電力比、信号対雑音比、搬送波対干渉比、隣接チャネル干渉電力比、ビット誤り率、スループット、遅延時間、輻輳状態、媒体アクセス制御層における自動再送要求回数、自端末のバッテリー残量、自端末と隣接端末との距離のいずれか、またはこれらの組み合わせから算出されることを特徴とする請求項５〜７のいずれか一に記載の携帯端末装置。
【請求項９】
アドホックネットワークシステムを構成するそれぞれの携帯端末装置が、隣接する携帯端末装置との間の接続性を表す接続確率を保持し、該接続確率の変化に基づいて通信経路の変更を行うことを特徴とするアドホックネットワークシステムにおける経路修復方法。
【請求項１０】
前記通信経路を構成して中継機能を有するそれぞれの携帯端末装置において、所定の携帯端末装置に関する前記接続確率が所定値以下となった場合に、前記所定の携帯端末装置の上流に位置する携帯端末装置に保持されている代用となる通信経路の情報に基づいて新たな通信経路を設定することを特徴とする請求項９記載のアドホックネットワークシステムにおける経路修復方法。
【請求項１１】
前記代用となる通信経路の情報は、該通信経路を構成するそれぞれの携帯端末装置に関する前記接続確率の積を含み、該積が最大となる前記通信経路を前記新たな通信経路に設定することを特徴とする請求項１０記載のアドホックネットワークシステムにおける経路修復方法。
【請求項１２】
前記接続確率は、隣接リンクの受信信号強度、希望波信号電力対干渉波電力比、信号対雑音比、搬送波対干渉比、隣接チャネル干渉電力比、ビット誤り率、スループット、遅延時間、輻輳状態、媒体アクセス制御層における自動再送要求回数、自端末のバッテリー残量、自端末と隣接端末との距離のいずれか、またはこれらの組み合わせから算出されることを特徴とする請求項９〜１１のいずれか一に記載のアドホックネットワークシステムにおける経路修復方法。
【請求項１３】
アドホックネットワークシステムを構成して中継機能を有するそれぞれの携帯端末装置を構成するコンピュータに、
隣接する携帯端末装置から該携帯端末装置との間の接続性を表す接続確率を受け取る処理と、
受け取った前記接続確率が所定値以下であるか否かを判断する処理と、
前記接続確率が所定値以下となった場合に、保持されている代用となる通信経路の情報に基づいて新たな通信経路を設定する処理と、
を実行させるプログラム。
【請求項１４】
前記新たな通信経路を設定する処理において、前記代用となる通信経路の情報は、該通信経路を構成するそれぞれの携帯端末装置に関する前記接続確率の積を含み、該積が最大となる前記通信経路を前記新たな通信経路として設定することを特徴とする請求項１３記載のプログラム。
【請求項１５】
前記携帯端末装置は、
前記アドホックネットワークシステムの通信経路を構成するそれぞれの携帯端末装置の識別情報を記載する経路対応表と、
前記隣接する携帯端末装置と、前記携帯端末装置との間の接続性を表す接続確率とを保持する周辺端末リストと、
前記通信経路を構成する携帯端末装置の内、自端末から１ホップの携帯端末装置に２および３ホップ目で至る経路中のそれぞれの携帯端末装置の識別情報と該それぞれの携帯端末装置における前記接続確率の積とを該経路毎に保持する保全経路リストと、
を備え、
前記新たな通信経路を設定する処理において、前記保全経路リストを参照して前記新たな通信経路を設定し、
前記経路対応表を、前記新たな通信経路にしたがって書き換えることを特徴とする請求項１４記載のプログラム。
【請求項１６】
前記接続確率は、隣接リンクの受信信号強度、希望波信号電力対干渉波電力比、信号対雑音比、搬送波対干渉比、隣接チャネル干渉電力比、ビット誤り率、スループット、遅延時間、輻輳状態、媒体アクセス制御層における自動再送要求回数、自端末のバッテリー残量、自端末と隣接端末との距離のいずれか、またはこれらの組み合わせから算出されることを特徴とする請求項１３〜１５のいずれか一に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アドホックネットワークシステム、そのシステムにおける経路修復方法、移動端末装置およびプログラムに係り、特に、アドホックネットワークにおける通信経路の変更技術に係る。
【背景技術】
【０００２】
アドホックネットワークは、基地局、固定局やアクセスポイントを使わず、携帯電話などの端末間でホッピング（中継）することで、データ伝送を可能とするネットワークである。すべての端末によって自律的にネットワークが構築されるので、基地局等の設置が不要となり、柔軟性が高く、設置が容易なネットワーク構築が可能となる。そのため、災害地やイベント会場における一時的なネットワーク構築や、自動車などの移動機器の間でのネットワーク構築に適する。
【０００３】
ところで、このようなアドホックネットワークでは、各端末の位置が固定されていないために、端末移動等による通信路の切断が発生し、経路の再構築や、複数の経路の維持についての対応が必要となる。このため、ＤＳＲ(Dynamic Source Routing)やＡＯＤＶ(Ad hoc On-Demand Distance Vector routing)等の多くの手法が開発されている。
【０００４】
例えば、特許文献１には、既存の第１経路上で各無線リンクを監視し、いずれかの無線リンクで切断が予期されると第２経路の確立を開始するマルチホップ無線ネットワークの経路更新方法および無線端末が開示されている。それぞれの無線端末は、隣接リンクの切断を予期する指標として、各隣接リンクの受信信号強度、希望波信号電力対干渉波電力比、信号対雑音比、搬送波対干渉比、隣接チャネル干渉電力比、ビット誤り率、スループット、遅延時間、輻輳状態、媒体アクセス制御層における自動再送要求回数、および自端末のバッテリー残量のいずれか、または複数を検知する。そして、隣接リンクの切断を予期する指標を元に無線リンクで切断が予期されると、隣接端末と直接通信可能な１ホップ目の第１周囲端末のみならず、当該第１周囲端末と直接通信可能な２ホップ目の第２周囲端末をも仲介端末として機能させるようにしている。
【０００５】
【特許文献１】特開２００５−２２３６９７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
特許文献１においては、リンク切断の予測の指標が提示され、新たな経路を選択する際に１ホップ以上の場合も検索することが記載されている。しかしながら、リンク切断時に代替可能となる経路が複数存在する場合に、複数の経路の優劣を判定する基準が明示されていない。このため、代替経路として通信品質の劣った経路を設定する可能性があり、接続品質を低下させる虞がある。
【０００７】
そこで本発明は、代替経路における接続品質を高く維持するアドホックネットワークシステムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の１つのアスペクトに係るアドホックネットワークシステムは、アドホックネットワークシステムを構成するそれぞれの携帯端末装置が、隣接する携帯端末装置との間の接続性を示す接続確率を保持し、該接続確率の変化に基づいて通信経路の変更を行う。
【０００９】
第１の展開形態のアドホックネットワークシステムにおいて、通信経路を構成する中継となるそれぞれの携帯端末装置において、所定の携帯端末装置に関する接続確率が所定値以下となった場合に、所定の携帯端末装置の上流に位置する携帯端末装置に保存されている代用となる通信経路の情報に基づいて新たな通信経路を設定するようにしてもよい。
【００１０】
第２の展開形態のアドホックネットワークシステムにおいて、代用となる通信経路の情報は、該通信経路を構成するそれぞれの携帯端末装置に関する接続確率の積を含み、該積が最大となる通信経路を新たな通信経路に設定するようにしてもよい。
【００１１】
第３の展開形態のアドホックネットワークシステムにおいて、接続確率は、隣接リンクの受信信号強度、希望波信号電力対干渉波電力比、信号対雑音比、搬送波対干渉比、隣接チャネル干渉電力比、ビット誤り率、スループット、遅延時間、輻輳状態、媒体アクセス制御層における自動再送要求回数、自端末のバッテリー残量、自端末と隣接端末との距離のいずれか、またはこれらの組み合わせから算出されることが好ましい。
【００１２】
本発明の１つのアスペクトに係る携帯端末装置は、アドホックネットワークシステムを構成して中継機能を有する携帯端末装置であって、隣接する携帯端末装置から該携帯端末装置との間の接続性を表す接続確率を受け取るリンク監視部と、受け取った接続確率が所定値以下であるか否かを判断する切断予期部と、接続確率が所定値以下となった場合に、保持されている代用となる通信経路の情報に基づいて新たな通信経路を設定する経路選択部と、を備える。
【００１３】
第１の展開形態の携帯端末装置において、代用となる通信経路の情報は、該通信経路を構成するそれぞれの携帯端末装置に関する接続確率の積を含み、経路選択部は、該積が最大となる通信経路を新たな通信経路として設定するようにしてもよい。
【００１４】
第２の展開形態の携帯端末装置において、アドホックネットワークシステムの通信経路を構成するそれぞれの携帯端末装置の識別情報を記載する経路対応表と、隣接する携帯端末装置と、携帯端末装置との間の接続性を表す接続確率とを保持する周辺端末リストと、通信経路を構成する携帯端末装置の内、自端末から１ホップの携帯端末装置に２および３ホップ目で至る経路中のそれぞれの携帯端末装置の識別情報と該それぞれの携帯端末装置における接続確率の積とを該経路毎に保持する保全経路リストと、を備え、経路選択部は、保全経路リストを参照して新たな通信経路を設定し、経路対応表は、新たな通信経路にしたがって書き換えられるようにしてもよい。
【００１５】
本発明の１つのアスペクトに係るアドホックネットワークシステムにおける経路修復方法は、アドホックネットワークシステムを構成するそれぞれの携帯端末装置が、隣接する携帯端末装置との間の接続性を表す接続確率を保持し、該接続確率の変化に基づいて通信経路の変更を行う。
【００１６】
本発明の１つのアスペクトに係るプログラムは、アドホックネットワークシステムを構成して中継機能を有するそれぞれの携帯端末装置を構成するコンピュータに、隣接する携帯端末装置から該携帯端末装置との間の接続性を表す接続確率を受け取る処理と、受け取った接続確率が所定値以下であるか否かを判断する処理と、接続確率が所定値以下となった場合に、保持されている代用となる通信経路の情報に基づいて新たな通信経路を設定する処理と、を実行させる。
【発明の効果】
【００１７】
本発明によれば、選択可能な経路が複数存在する場合に接続性を表す接続確率に基づいて経路の選択を行うので、選択された通信経路の通信品質を高く維持することができる。
【発明を実施するための最良の形態】
【００１８】
図１は、本発明の実施形態に係る移動端末装置の構成を示すブロック図である。図１において、移動端末装置（以下、単に端末ともいう）１００は、隣接する移動端末装置１００ａ、１００ｂとの間で通信用データの中継およびリンクを構成するためのデータの交換を行う。移動端末装置１００は、送受信部２００、メッセージ判定部２０１、メッセージ生成部２０２、リンク監視部２０３、リンク切断予期部２０４、最適経路選択部２０５、対象端末通知部２０６、既経路対応部２０７、周辺端末探索部２０８、周辺端末リスト作成部２０９、推奨保全経路リスト作成部２１０、経路対応表２１１、周辺端末リスト２１２、推奨保全経路リスト２１３を備える。なお、ここでは、隣接する移動端末装置を便宜上２台として表しているが、リンクを構成する台数分存在するものとする。
【００１９】
送受信部２００は、隣接リンクを構成する移動端末装置１００ａ、１００ｂとの間で無線による信号の送受信を行う。
【００２０】
メッセージ判定部２０１は、移動端末装置１００ａ、１００ｂから送受信部２００を介して受信したリンク構成に関わるメッセージの内容を判定し、内容に応じて、既経路対応部２０７、周辺端末リスト作成部２０９、推奨保全経路リスト作成部２１０にメッセージを分配する。
【００２１】
メッセージ生成部２０２は、隣接する移動端末装置１００ａ、１００ｂに対して送出するリンク構成に関わるメッセージを生成し、送受信部２００に出力する。
【００２２】
リンク監視部２０３は、送受信部２００において受信した信号から、既存の通信経路上で隣接する端末（隣接端末）との間に確立されているそれぞれの隣接リンクの状態を監視する。隣接リンクとの状態は、隣接リンクの受信信号強度、希望波信号電力対干渉波電力比、信号対雑音比、搬送波対干渉比、隣接チャネル干渉電力比、ビット誤り率、スループット、遅延時間、輻輳状態、媒体アクセス制御層における自動再送要求回数、および自端末のバッテリー残量、自端末と隣接端末との距離等のいずれかの要因、またはこれらの組み合わせから算出される接続確率によって表す。接続確率は、０から１の間の値を取り、これらの要因に対して隣接端末との接続性が高まるほど、すなわち隣接リンクとの接続状態が良好なほど、１に近い値を取るものとする。また、隣接端末とリンクを構成できない場合には、接続確率は、０とする。
【００２３】
リンク切断予期部２０４は、リンク監視部２０３で監視する隣接リンクの状態に基づいて、隣接リンクが所定のリンク切断予期条件を満足するか否かを判別する。すなわち、リンク監視部２０３において検知されたリンク状態が所定のリンク切断予期条件を満足するか否かに基づいて、隣接リンクに切断の予兆があるか否かを判定する。例えば、接続確率が所定の値より下回った場合にリンク切断予期条件を満足しないと判断する。
【００２４】
最適経路選択部２０５は、リンク切断予期部２０４において隣接リンクに切断あるいは切断の予兆があると判断された場合に、推奨保全経路リスト作成部２１０の有する推奨保全経路リスト２１３から最適な経路、例えば最も接続確率の高い経路を選択し、経路情報として保持する。
【００２５】
対象端末通知部２０６は、最適経路選択部２０５で選択された最適な経路における対象となる隣接する端末に対して新たな経路として機能するためのメッセージを出力するようにメッセージ生成部２０２に通知する。
【００２６】
既経路対応部２０７は、通信経路の記載されたメッセージをメッセージ判定部２０１から受け取る。そして、現在自端末が通信経路状態にあることを認識し、１ホップ目の端末の接続状況を周辺端末リスト作成部２０９における周辺端末リストによって把握する。さらに、例えば１ホップ目の接続確率が所定の値を下回った場合には、推奨保全経路リスト２１３に従って、別の経路を使って、自端末から２ホップ目の経路を探索する。
【００２７】
周辺端末探索部２０８は、一定時間間隔で起動され周辺端末の状況を調べるために、周辺に存在する端末に対して応答を返すようにメッセージ発信をメッセージ生成部２０２に依頼する。
【００２８】
周辺端末リスト作成部２０９は、隣接する端末およびその接続確率の記載されたメッセージをメッセージ判定部２０１から受け取り、周辺端末リスト２１２を更新して保持する。また、新たに出現した隣接する端末およびその接続確率を周辺端末リスト２１２に追加する。さらに、周辺端末リスト２１２にあって、所定時間待っても応答の無かった隣接する端末を周辺端末リスト２１２から削除する。このようにして更新した周辺端末リスト２１２を、隣接する端末に送るようにメッセージ生成部２０２に依頼する。
【００２９】
推奨保全経路リスト作成部２１０は、隣接する端末における周辺端末リストの記載されたメッセージをメッセージ判定部２０１から受け取る。そして、宛先の無線端末と次ホップの無線端末との関係を示す経路情報が記録される経路対応表２１１を元に以下に説明する手順に従って推奨保全経路リスト２１３を更新して保存する。さらに、推奨保全経路リスト２１３の更新情報となるメッセージを、隣接する端末に送るようにメッセージ生成部２０２に依頼する。
【００３０】
以上の説明において、メッセージ判定部２０１、メッセージ生成部２０２、リンク監視部２０３、リンク切断予期部２０４、最適経路選択部２０５、対象端末通知部２０６、既経路対応部２０７、周辺端末探索部２０８、周辺端末リスト作成部２０９、推奨保全経路リスト作成部２１０の一部あるいは全部を、移動端末装置内に備えるコンピュータにプログラムを実行させて、実現するように構成してもよい。
【００３１】
図２（Ａ）は、周辺端末リスト２１２および推奨保全経路リスト２１３を説明するためのネットワーク構成を模式的に示す図である。図２（Ｂ）は、端末ｍｎ２が保持する周辺端末リスト２１２の例を示す図であり、図２（Ｃ）は、端末ｍｎ２が保持する推奨保全経路リスト２１３の例を示す図である。図２（Ｂ）において、端末ｍｎ２に対し下流に隣接する端末は、端末ｍｎ３、ｍｎ８、ｍｎ６、ｍｎ４であって、それぞれの端末との接続確率がＰ２３、Ｐ２８、Ｐ２６、Ｐ２４であることを示す。また、図２（Ｃ）において、経路１は、接続確率Ｐ２４で端末ｍｎ４に至る経路であり、経路２は、接続確率Ｐ２８＊Ｐ８４で、端末ｍｎ８を経由して端末ｍｎ４に至る経路であり、経路３は、接続確率Ｐ２６＊Ｐ６７＊Ｐ７４で、端末ｍｎ６、ｍｎ７を経由して端末ｍｎ４に至る経路であることを示す。
【００３２】
このような周辺端末リスト２１２および推奨保全経路リスト２１３をそれぞれの端末が保持し、現在の通信経路の下流に隣接する端末が消失した場合、すなわち、例えば隣接する端末との接続確率が所定の値以下になった場合に、推奨保全経路リスト２１３中の接続確率の最も高い経路を新たな通信経路として選択する。
【００３３】
次に、推奨保全経路リスト２１３の更新について説明する。図３は、推奨保全経路リストを更新する手順を表すフローチャートである。
【００３４】
ステップＳ１１において、メッセージ判定部２０１から出力されるメッセージを元に自端末の周辺端末リストを取得する。
【００３５】
ステップＳ１２において、メッセージ判定部２０１から出力されるメッセージを元に現在の通信路での１ホップ目の端末の周辺端末リストを取得する。
【００３６】
ステップＳ１３において、メッセージ判定部２０１から出力されるメッセージを元に現在の通信路での２ホップ目の端末の周辺端末リストを取得する。
【００３７】
ステップＳ１４において、現在の通信路での２ホップ目の端末がステップＳ１１で取得した周辺端末リストに含まれるか否かをチェックする。含まれていれば、ステップＳ１５において、推奨保全経路リスト２１３に経路と接続確率とを追加する。図２（Ｃ）の例では、経路１が相当する。
【００３８】
ステップＳ１６において、ステップＳ１１およびＳ１３で取得した周辺端末リストに共通の端末が存在するか否かをチェックする。共通の端末の候補が存在する場合には、ステップＳ１７において、推奨保全経路リストに経路情報を追加する。この時、自端末と候補端末との接続確率をＰ０Ａ、現通信路での２ホップ目の端末と候補端末との接続確率をＰ２Ａとし、接続確率Ｐ０Ａ２＝Ｐ０Ａ＊Ｐ２Ａを計算し、推奨保全経路リストに接続確率Ｐ０Ａ２を追加する。図２（Ｃ）の例では、経路２が相当する。
【００３９】
ステップＳ１８において、ステップＳ１２で取得した候補端末から、自端末、２ホップ目の候補端末およびステップＳ１６で求めた共通の候補端末を除く端末が存在するか否かをチェックする。存在しない場合にはステップＳ２２に進み、存在する場合には、ステップＳ１９に進む。
【００４０】
ステップＳ１９において、ステップＳ１８で選択された全ての候補端末の周辺端末リストを取得する。
【００４１】
ステップＳ２０において、ステップＳ１８で選択された候補端末と、その周辺端末リストとの組み合わせで自端末から２ホップ目の端末に繋がる端末が存在するか否かをチェックする。存在する場合には、ステップＳ２１において、推奨保全経路リストに経路情報を追加する。この時、自端末とステップＳ２０で見出した２ホップ目の端末に繋がる複数の候補端末と２ホップ目の端末間の接続確率を用意し、それらの積を接続確率として推奨保全経路リスト２１３に追加する。図２（Ｃ）の例では、経路３が相当する。
【００４２】
ステップＳ２２において、規定時間待って、ステップＳ１１に戻る。
【００４３】
以上のように本発明のアドホックネットワークでは、一度通信経路を確立した場合、その通信経路の端末それぞれに、その端末が消失した場合に備えて、上流の端末に代替となりうる別の経路情報を保存する。そして、通信経路に対して、各中継端末において、中継端末が消失した場合であっても、接続確率を元に既に保存されている代用経路を定めて代用経路を使うことで、すぐに新たな通信経路を確保することができる。また、代用経路の選択にあたり、消失予定の端末の近傍情報を使っているため、冗長な代用経路の探索を防ぐことができる。すなわち、中継経路が途絶えた場合、全く新しい経路を探さずに消失した経路だけをまず修正することで、新経路構築のための回復時間が短くて済む。またその修復経路の検出において消失端末に焦点をあてた接続確率を基にするアルゴリズムにより、冗長な経路検出を防ぐことができる。以下、実施例に即し、アドホックネットワークの経路修復方法について説明する。
【実施例１】
【００４４】
図４は、本発明の実施例に係る経路修復方法を説明するためのアドホックネットワークを模式的に示す図である。図４において、Ａ〜Ｎ、Ｑ〜Ｕ、Ｘ〜Ｚ、１０、１１は、上記で説明した移動端末装置を表す。図４に示すネットワークでは、移動端末装置１０から移動端末装置１１への通信を行うものとし、最初に存在する経路は、従来の適切な方法によって構築された経路とする。ここでは、経路２０（端末１０→端末Ｘ→端末Ｙ→端末Ｚ→端末Ｂ→端末Ｅ→端末Ｈ→端末Ｉ→端末Ｎ→端末１１）が選択されたとする。また、予備に複数の経路を選択しておく。例えば、経路２１（端末１０→端末Ｘ→端末Ｙ→端末Ｕ→端末Ａ→端末Ｄ→端末Ｇ→端末Ｍ→端末Ｌ→端末１１）、および経路２２（端末１０→端末Ｒ→端末Ｓ→端末Ｔ→端末Ｃ→端末Ｆ→端末Ｊ→端末Ｑ→端末１１）が予備として選択されたとする。
【００４５】
ここで、各端末ｎは、近傍情報、つまり、接続可能な周辺端末情報とこの周辺端末ｍに対する接続確率Ｐ（ｎ、ｍ）とを保持する。接続確率Ｐは、接続性を示すパラメータであって、端末における電池状況、移動状況、電波状況等によって計算される。０≦Ｐ（ｎ、ｍ）≦１とし、Ｐ（ｎ、ｍ）が大きいほど接続性が高いものとする。
【００４６】
複数の経路に対して、経路確率（それぞれの端末経路における端末の接続確率の積）が一番大きい経路を最適経路として選択しておく。経路２０が最適経路であるということは、経路確率＝Ｐ（１０，Ｘ）＊Ｐ（Ｘ，Ｙ）＊Ｐ（Ｙ，Ｚ）＊Ｐ（Ｚ，Ｂ）＊Ｐ（Ｂ，Ｅ）＊Ｐ（Ｅ，Ｈ）＊Ｐ（Ｈ，Ｉ）＊Ｐ（Ｉ，Ｎ）＊Ｐ（Ｎ，１１）が他の経路の経路確率と比較して一番大きいということである。
【００４７】
最適経路として選択された経路におけるそれぞれの端末において、その端末が消失した場合に、代替となる経路の別端末情報を、消失すると仮定した端末の上流の端末に保存する。図４の例で、Ｂ→Ｅ→Ｈの端末の経路について説明する。すなわち、中継となる端末Ｅが消失した場合に備え、端末Ｅを使用せずに端末Ｂから端末Ｈに向かう経路情報を上流の端末Ｂに保存しておく。これにより、端末Ｅが消失した場合、または消失しそうな場合に、両端端末の端末Ｂにその代用経路を先に提供し、切り替えを行うことで、経路が絶たれることを未然に防ぐようにする。さらに端末Ｅから遠くなく、複数の経路を保存することでより経路の保全化を図る。このため、以下のアルゴリズムに沿って代用経路を選定する。
【００４８】
（１）まず、中継端末抜きで接続可能か調査する。
先の例でいえば、Ｂ→Ｈが可能か否かを調査する。これは、端末Ｂの近傍情報、すなわち周辺端末リストにＨが含まれるかどうかで判断する。含まれていれば、端末Ｂに代用経路候補として、経路パターンと経路確率とを保存する。つまり、経路パターンＢ→Ｈに対して経路確率Ｐ（Ｂ，Ｈ）を保存する。図４の例では存在していない。
【００４９】
（２）次に中継端末を１つ含ませた経路を策定する。
これは端末Ｂの近傍情報と端末Ｈの近傍情報とを比較し、共通の中継端末を見出すことで決定する。共通の中継端末が見出されれば、端末Ｂに代用経路候補として、経路パターンと、その経路確率を保存する。図１の例では、共通の中継端末が２つ存在し、第１の経路パターンＢ→Ｄ→Ｈに対して経路確率Ｐ（Ｂ，Ｄ）＊Ｐ（Ｄ，Ｈ）を保存し、第２の経路パターンＢ→Ｋ→Ｈに対して経路確率Ｐ（Ｂ，Ｋ）＊Ｐ（Ｋ，Ｈ）を保存する。
【００５０】
（３）次に中継を２つ以上含ませた経路を選定する。
ここで、通常、両端から中継端末２つ以上の経路を選択するために、総当り法で行うと、近傍端末数をＮとした場合、比較数が２＊Ｎ＊Ｎと多くなり、余計に冗長な経路が選択される虞がある。このため、以下のようなアルゴリズムで探索を行う。
【００５１】
（４）中継端末の近傍端末についてのみ次の調査を行う。
（４−１）  中継端末（図４の例で端末Ｅ）の近傍端末（図４の例でＢ，Ｃ，Ｆ，Ｈ，Ｋ）から、経路となっている両端端末（図４の例でＢとＨ）と（２）で見つけた端末（図４の例でＫ）とを除いた端末（図４の例でＣとＦ）を抽出する。
【００５２】
（４−２）  （４−１）で抽出された端末に対する近傍端末情報を調べ、その中に両端端末（図４の例でＢかＨ）が発見できれば、（４−１）での端末に仮経路として保持する。図４の例だと、端末Ｃの近傍端末に対して、両端端末の端末Ｂを含んでいるため仮経路端末として保存する。同様に端末Ｆの近傍端末に対して、両端端末の端末Ｈを含んでいるため、仮経路端末として保存する。
【００５３】
（４−３）仮経路端末の近傍端末に対して、残りの両端端末か、別の仮経路端末が見つかれば、経路として保持し、経路パターンとして登録する。見つからなければ調査を中止する。図４の例では、端末Ｃの近傍端末として仮経路端末Ｆを得ることができるため、経路として保持される。経路パターンＢ→Ｃ→Ｆ→Ｈに対して確率Ｐ（Ｂ，Ｃ）＊Ｐ（Ｃ，Ｆ）＊Ｐ（Ｆ，Ｈ）を保持する。
【００５４】
（５）  （１）〜（４）で得られた代用経路を両端端末に推奨保全経路リストとして保存する。その場合、経路確率の高い順に順番をつける。例でいうと経路パターンＢ→Ｄ→Ｈおよび経路確率Ｐ（Ｂ，Ｄ）＊Ｐ（Ｄ，Ｈ）と、経路パターンＢ→Ｋ→Ｈおよび経路確率Ｐ（Ｂ，Ｋ）＊Ｐ（Ｋ，Ｈ）と、経路パターンＢ→Ｃ→Ｆ→Ｈおよび経路確率Ｐ（Ｂ，Ｃ）＊Ｐ（Ｃ，Ｆ）＊Ｐ（Ｆ，Ｈ）との、３つについて経路確率の大きさを比較し、大きいほうから順に代用経路として上流端末Ｂに保存しておく。
【００５５】
（６）端末Ｅが消失したり、端末Ｅを含む経路確率が著しく小さくなったりした場合には、上流の端末Ｂから端末Ｈへの経路に対して、代用経路の内で経路確率が一番高い経路パターンを選択して新規経路とする。
【００５６】
（７）  （６）において得られた新規経路と経路２１や経路２２のような予備経路とについて、それぞれの経路確率を比較し、経路確率の差分が所定の閾値を超えて予備経路が良くなった場合には、予備経路を選択するようにする。
【００５７】
以上のような経路修復方法によれば、中継経路が途絶えた場合に、全く新しい経路を探さずに消失した経路だけをまず修正するので、新経路構築の回復時間が短くて済む。また、修復経路の検出において消失する端末に焦点をあてた経路確率に基づくアルゴリズムにより、適切な経路検出が可能となる。
【図面の簡単な説明】
【００５８】
【図１】本発明の実施形態に係る移動端末装置の構成を示すブロック図である。
【図２】経路更新を行うためのネットワークとこのネットワークを構成する端末が保持する情報とを模式的に示す図である。
【図３】推奨保全経路リストを生成する手順を表すフローチャートである。
【図４】本発明の実施例に係る経路修復方法を説明するためのアドホックネットワークを模式的に示す図である。
【符号の説明】
【００５９】
１０、１１、１００、１００ａ、１００ｂ、ｍｎ１〜ｍｎ８、Ａ〜Ｎ、Ｑ〜Ｕ、Ｘ〜Ｚ  移動端末装置
２０、２１、２２  経路
２００  送受信部
２０１  メッセージ判定部
２０２  メッセージ生成部
２０３  リンク監視部
２０４  リンク切断予期部
２０５  最適経路選択部
２０６  対象端末通知部
２０７  既経路対応部
２０８  周辺端末探索部
２０９  周辺端末リスト作成部
２１０  推奨保全経路リスト作成部
２１１  経路対応表
２１２  周辺端末リスト
２１３  推奨保全経路リスト
【図１】
2007243575.tif 000003
【図２】
2007243575.tif 000004
【図３】
2007243575.tif 000005
【図４】
2007243575.tif 000006