(57)【要約】【課題】無線基地局を寄り道スポットに選択して経路を検索すると経路長が無駄に長くなること。【解決手段】経路検索装置は、経路検索部と経路修正部と滞在時間付与部とを有する。経路検索部は、始点から１以上の無線基地局を経由して終点まで制限時間内に到達する１以上の経路を検索する。経路修正部は、検索された経路を、無線基地局直下と同等の通信品質を有し無線基地局の無線カバレッジエリア内に存在する地点を通過する、経路長のより短い経路に修正する。滞在時間付与部は、修正後の経路に沿って始点から終点まで移動するのに要する時間と制限時間との差を、修正後の経路上の通信品質が最大の地点での滞在時間として修正後の経路に付与する。【選択図】図１
2013140123.tif 000002
【特許請求の範囲】
【請求項１】
始点から１以上の無線基地局を経由して終点まで制限時間内に到達する１以上の経路を検索する経路検索部と、
前記検索された経路を、前記無線基地局直下と同等の通信品質を有し前記無線基地局の無線カバレッジエリア内に存在する地点を通過する、経路長のより短い経路に修正する経路修正部と、
前記修正後の経路に沿って前記始点から前記終点まで移動するのに要する時間と前記制限時間との差を、前記修正後の経路上の通信品質が最大の地点での滞在時間として前記修正後の経路に付与する滞在時間付与部と
を有する経路検索装置。
【請求項２】
前記経路修正部は、前記検索された経路のうち前記無線カバレッジエリア内を通過する経路部分を、前記無線カバレッジエリアに侵入する箇所と前記無線カバレッジエリアから退出する箇所との間の最短経路で置き換える
請求項１に記載の経路検索装置。
【請求項３】
前記経路修正部は、前記検索された経路を、前記無線カバレッジエリアに侵入する箇所と前記無線カバレッジエリアから退出する箇所との間の最短経路の中点を経由して前記始点から前記終点に至る最短経路に置き換える
請求項１に記載の経路検索装置。
【請求項４】
前記経路検索部は、前記始点または直前に経由する前記無線基地局を起点とし、前記起点および前記終点を焦点とし、周上の点から前記起点および前記終点までの距離の和が、前記起点から前記終点までの移動に許容される残り時間内に移動できる総距離に等しい第１の楕円を探索平面上に設定し、前記第１の楕円内の領域から次に経由する前記無線基地局を選択する
請求項１乃至３の何れかに記載の経路検索装置。
【請求項５】
前記経路検索部は、前記第１の楕円内の領域から選択する前記無線基地局が最後に経由する前記無線基地局以外のときは、前記第１の楕円内に存在する前記無線基地局であって、当該無線基地局および前記終点を焦点とし、周上の点から当該無線基地局および前記終点までの距離の和が、当該無線基地局から前記終点までの移動に許容される残り時間内で移動できる総距離に等しい第２の楕円の領域内に、当該無線基地局を除いて以降に経由する数以上の前記無線基地局が存在している前記無線基地局を選択候補とし、該選択候補のうちから次に経由する前記無線基地局を選択する
請求項４に記載の経路検索装置。
【請求項６】
前記経路検索部は、前記選択候補が複数存在する場合、前記第２の楕円の面積に占める、前記第２の楕円内に存在する前記無線基地局の無線カバレッジエリア毎に算出した通信品質量と前記第２の楕円内に含まれる無線カバレッジエリア面積との乗算値を累積した値の割合がより大きい前記選択候補を優先的に選択する
請求項５に記載の経路検索装置。
【請求項７】
前記滞在時間が付与された前記修正後の経路毎に総通信品質量を算出し、総通信品質量が最大の経路を最適経路として選択する最適経路選択部をさらに有する
請求項１乃至６の何れかに記載の経路検索装置。
【請求項８】
経路検索部と経路修正部と滞在時間付与部とを有する経路検索装置が実行する経路検索方法であって、
前記経路検索部が、始点から１以上の無線基地局を経由して終点まで制限時間内に到達する１以上の経路を検索し、
前記経路修正部が、前記検索された経路を、前記無線基地局直下と同等の通信品質を有し前記無線基地局の無線カバレッジエリア内に存在する地点を通過する、経路長のより短い経路に修正し、
前記滞在時間付与部が、前記修正後の経路に沿って前記始点から前記終点まで移動するのに要する時間と前記制限時間との差を、前記修正後の経路上の通信品質が最大の地点での滞在時間として前記修正後の経路に付与する
経路検索方法。
【請求項９】
コンピュータを、
始点から１以上の無線基地局を経由して終点まで制限時間内に到達する１以上の経路を検索する経路検索部と、
前記検索された経路を、前記無線基地局直下と同等の通信品質を有し前記無線基地局の無線カバレッジエリア内に存在する地点を通過する、経路長のより短い経路に修正する経路修正部と、
前記修正後の経路に沿って前記始点から前記終点まで移動するのに要する時間と前記制限時間との差を、前記修正後の経路上の通信品質が最大の地点での滞在時間として前記修正後の経路に付与する滞在時間付与部と
して機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路検索装置に関し、特に最短経路より通信品質が良い経路を検索する経路検索装置に関する。
【背景技術】
【０００２】
２地点間の移動に際しては、その最短経路を移動するのが一般に望ましいと考えられる。しかし、移動中に通信を行いたい利用者にとっては、一概にそうとは言えない。例えば携帯電話等の移動端末を所持する利用者が、始点ｓから終点ｇまで移動する場合を考える。このとき、最短経路上に無線カバレッジエリアが存在しなければ、移動中に一度も通信できないことになる。従って、移動端末利用者が、移動時間や移動距離が多少増大しても、無線カバレッジエリアを通る経路を利用したいと考えても不思議ではない。
【０００３】
このような状況の下、最短経路より通信品質が良く且つ制限時間内で移動できる経路を検索する技術が非特許文献１に記載されている。非特許文献１に記載の技術では、検索領域（例えば市街地）を重み付き有向グラフＧ＝（Ｖ，Ｅ，Ｃ，Ｐ）で表現する。ここで、Ｖは頂点（例えば交差点）、Ｅは辺（例えば道路）、Ｃは移動時間関数（例えば辺の移動に要する時間）、Ｐは通信品質関数（例えば各頂点での通信速度）である。そして、始点、終点、および制限時間が与えられた場合に、移動時間が制限時間以下になる経路のうち、次式で与えられる総転送量Ｐ（Ｔ）が最大となる経路を、分枝限定法により発見する。
【０００４】
Ｐ（Ｔ）＝ｔ・Ｐ（vi）＋Σj=1kＣ（ej）・Ｐ（ej）      …（１）
ここで、Ｃ（ej）・Ｐ（ej）は辺ｊを移動する間に得られる転送量であり、従ってΣj=1kＣ（ej）・Ｐ（ej）は移動中に得られる転送量の総和を示す。また、Ｐ（vi）は経路上の通信速度が最大の頂点での通信速度、ｔは制限時間から経路の移動時間を減じた残り時間である。すなわち、非特許文献１では、経路の移動時間が制限時間に満たない場合、その差ｔを、経路上の通信速度が最大の頂点での停止時間として割り当てる。この停止時間で得られる転送量の総和がｔ・Ｐ（vi）である。
【０００５】
他方、本発明に関連する他の技術として、特許文献１に記載の技術がある。特許文献１に記載の技術では、始点から終点までの経路検索において時間的余裕が存在する場合に、適当な寄り道スポット（レストランや博物館など）を選択し、その寄り道スポットを含む経路を利用者に提示する。また、次に立ち寄るスポットは、利用者の存在する地点から当該スポットに立ち寄った後に終点まで残り時間で到達できるエリア内から検索することで、検索対象エリアを絞り込んでいる。具体的には、残り時間と平均移動速度から残り時間内に移動できる総距離が計算でき、利用者の存在する地点から総距離内で寄り道した上で終点に辿り着ける範囲を求めると、平均移動速度が一定と仮定した場合に検索対象エリアは楕円形となる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−１３９５５３号公報
【非特許文献】
【０００７】
【非特許文献１】社団法人電子情報通信学会、進学技報、IEICE Technical Report RCS2009-269(2010-03)、p71-76、首藤裕一他、「無線モバイルユーザのための最適「寄り道」経路の特性」
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、非特許文献１に記載の技術は、全経路検索を行うアルゴリズムであるため基本的に計算量が多くなると共に、制限時間内では移動できない楕円領域外も検索するという無駄がある。これに対して特許文献１に記載の技術は、全経路検索でなく、然も制限時間内で移動できる楕円領域に検索範囲を絞っているため、少ない計算量で無駄の無い経路検索が可能である。しかし、特許文献１の技術を使用して、通信品質が良い経路を検索すると、経路長が無駄に長くなるという課題がある。以下、この課題について説明する。
【０００９】
特許文献１に記載の技術を用いて、通信品質の良い経路を検索する場合、無線基地局が寄り道スポットに相当する。このため、始点ｓと終点ｇと無線基地局ＢＳとが例えば図９に示すような位置関係にある場合、特許文献１に記載の技術では、始点ｓから無線基地局ＢＳを経由して終点ｇに至る経路Ｌ１が検索される。
【００１０】
一般に、無線基地局ＢＳの無線カバレッジエリア内では、無線基地局ＢＳに近いほど無線強度が強くなり通信品質が良くなる傾向がある。しかし、最大転送量に上限のある場合、或る距離より無線基地局に近づいても、それ以上は転送量が増大しない。すなわち、最大の通信品質が得られる場所はユークリッド平面状の点ではなく、ユークリッド平面状の面になる。今、図９の符号ＲＺで示す円のエリア内では無線基地局ＢＳ直下と同じ通信品質が得られているとする。また、迂回経路Ｌ１がエリアＲＺを横切る地点をｐ１、ｐ２とし、始点ｓから、ｐ１とｐ２とを経由して終点ｇに至る経路Ｌ２を考える。ユークリッド平面上の三角不等式より明らかなように、図９のｐ１から無線基地局ＢＳを経由してｐ２に行くよりも、ｐ１から直接にｐ２に行く方が距離が短くなり、その分、移動時間も短くなる。短縮できる時間をΔｔとすると、始点ｓから出発して経路Ｌ２上のｐ１からｐ２の間の任意の場所でΔｔだけ停止し、その後、経路Ｌ２に沿って終点ｇまで移動したときに得られる総転送量は、経路Ｌ１に沿って移動したときに得られる総転送量と等しい。すなわち、経路Ｌ２は、総転送量が経路Ｌ１と同じでありながら、より経路長が短くなる。通信品質が同じ複数の経路であれば、より経路長の短い方が望ましいと考える利用者は多いと考えられる。
【００１１】
本発明の目的は、上述したような課題、すなわち、無線基地局を寄り道スポットに選択して経路を検索すると経路長が無駄に長くなる、という課題を解決することにある。
【課題を解決するための手段】
【００１２】
本発明の一形態にかかる経路検索装置は、
始点から１以上の無線基地局を経由して終点まで制限時間内に到達する１以上の経路を検索する経路検索部と、
上記検索された経路を、上記無線基地局直下と同等の通信品質を有し上記無線基地局の無線カバレッジエリア内に存在する地点を通過する、経路長のより短い経路に修正する経路修正部と、
上記修正後の経路に沿って上記始点から上記終点まで移動するのに要する時間と上記制限時間との差を、上記修正後の経路上の通信品質が最大の地点での滞在時間として上記修正後の経路に付与する滞在時間付与部と
を有する。
【発明の効果】
【００１３】
本発明は上述したような構成を有するため、無線基地局を寄り道スポットに選択して検索した経路よりも経路長が短く、総通信品質は低下しない経路を求めることが可能となる。
【図面の簡単な説明】
【００１４】
【図１】本発明の第１の実施形態にかかる経路検索装置のブロック図である。
【図２】本発明の第１の実施形態にかかる経路検索装置の動作を示すフローチャートである。
【図３】本発明の第１の実施形態にかかる経路検索装置における経路検索部の動作説明図である。
【図４】始点から終点まで２つの無線基地局を経由して制限時間内に到達する経路を検索する過程を示す図である。
【図５】始点から終点まで１つの無線基地局を経由して到達する経路を例にして、より経路長の短い経路に修正する動作を説明する図である。
【図６】始点から終点まで１つの無線基地局を経由して到達する経路を例にして、より経路長の短い経路に修正する別の動作を説明する図である。
【図７】本発明の第２の実施形態にかかる経路検索装置のブロック図である。
【図８】本発明の第２の実施形態にかかる経路検索装置の動作を示すフローチャートである。
【図９】本発明が解決しようとする課題の説明図である。
【発明を実施するための形態】
【００１５】
次に本発明の実施の形態について図面を参照して詳細に説明する。
[第１の実施形態]
図１を参照すると、本発明の第１の実施形態にかかる経路検索装置１０は、ハードウェアとして、通信インターフェース部（以下、通信Ｉ／Ｆ部という）１１、操作入力部１２、画面表示部１３、記憶部１４、およびプロセッサ１５を有する。
【００１６】
通信Ｉ／Ｆ部１１は、専用のデータ通信回路からなり、図示しない通信回線を介して接続された各種装置との間でデータ通信を行う機能を有している。操作入力部１２は、キーボードやマウスなどの操作入力装置からなり、オペレータの操作を検出してプロセッサ１５に出力する機能を有している。画面表示部１３は、ＬＣＤやＰＤＰなどの画面表示装置からなり、プロセッサ１５からの指示に応じて、操作メニューや検索結果などの各種情報を画面表示する機能を有している。
【００１７】
記憶部１４は、ハードディスクやメモリなどの記憶装置からなり、プロセッサ１５での各種処理に必要な処理情報やプログラム１４Ｐを記憶する機能を有している。プログラム１４Ｐは、プロセッサ１５に読み込まれて実行されることにより各種処理部を実現するプログラムであり、通信Ｉ／Ｆ部１１などのデータ入出力機能を介して外部装置（図示せず）や記憶媒体（図示せず）から予め読み込まれて記憶部１４に保存される。記憶部１４で記憶される主な処理情報として、始点情報１４Ａ、終点情報１４Ｂ、制限時間１４Ｃ、移動速度１４Ｄ、経路数１４Ｅ、経由局数１４Ｆ、地図情報１４Ｇ、無線カバレッジ情報１４Ｈ、および検索結果１４Ｉがある。
【００１８】
始点情報１４Ａは、出発地点となる地点を特定する情報、例えば出発地の座標値である。終点情報１４Ｂは、目的地を特定する情報、例えば目的地の座標値である。制限時間１４Ｃは、出発地から目的地までの移動に許容される時間の上限値である。移動速度１４Ｄは、出発地から目的地までの移動速度の平均値である。経路数１４Ｅは、検索する経路の上限数である。経由局数１４Ｆは、経由する無線基地局の数である。
【００１９】
地図情報１４Ｇは、経路を検索する地域の地理的な情報である。地図情報１４Ｇは、非特許文献１に記載されるような重み付き有向グラフＧ＝（Ｖ，Ｅ，Ｃ，Ｐ）で表現されていてもよい。また地図情報１４Ｇは、カーナビゲーションシステムで使用されるような地図データベースであってもよい。
【００２０】
無線カバレッジ情報１４Ｈは、無線基地局の位置に関する情報とその無線カバレッジエリアの情報である。無線基地局の位置に関する情報は、例えば無線基地局の座標値である。無線カバレッジエリアの情報は、無線基地局直下の通信品質（例えば最大転送量）に関する情報及びそれと同等の通信品質が得られるエリアの地理的な情報とを有する。エリアの地理的な情報は、無線基地局を中心とする円の半径で近似されたものであっても良いし、エリアをより詳細に規定する座標情報であってもよい。
【００２１】
検索結果１４Ｉは、経路検索装置１０によって求められた経路の情報である。経路の情報は、始点から終点までの経路の地理的な情報を有する。また経路上で停止する場合には、停止する地点の地理的な情報と停止時間との情報を有する。
【００２２】
プロセッサ１５は、ＭＰＵなどのマイクロプロセッサとその周辺回路を有し、記憶部１４からプログラム１４Ｐを読み込んで実行することにより、上記ハードウェアとプログラム１４Ｐとを協働させて各種処理部を実現する機能を有している。プロセッサ１５で実現される主な処理部として、入力部１５Ａ、経路検索部１５Ｂ、経路修正部１５Ｃ、滞在時間付与部１５Ｄ、および出力部１５Ｅがある。
【００２３】
入力部１５Ａは、通信Ｉ／Ｆ部１１や操作入力部１２から検索要求を入力し、当該検索要求に含まれる始点情報１４Ａ、終点情報１４Ｂ、制限時間１４Ｃ、移動速度１４Ｄ、経路数１４Ｅ、および経由局数１４Ｆを、記憶部１４に記憶する機能を有する。
【００２４】
経路検索部１５Ｂは、記憶部１４から始点情報１４Ａ、終点情報１４Ｂ、制限時間１４Ｃ、移動速度１４Ｄ、経路数１４Ｅ、経由局数１４Ｆ、地図情報１４Ｇ、および無線カバレッジ情報１４Ｈを読み出し、始点情報１４Ａで与えられる始点から、経由局数１４Ｆで与えられる数の無線基地局を経由して、終点情報１４Ｂで与えられる終点まで、制限時間１４Ｃで与えらえる制限時間内に到達する経路を、経路数１４Ｅで与えられる数を上限として、地図情報１４Ｇ上から検索する機能を有する。
【００２５】
経路修正部１５Ｃは、経路検索部１５Ｂから検索された経路の情報を入力し、また記憶部１４から地図情報１４Ｇ等の必要な情報を読み出し、経路検索部１５Ｂによって検索された経路を、経由する無線基地局の無線カバレッジエリア内で無線基地局直下と同等の通信品質が得られる無線基地局以外の地点を経由する、より経路長の短い経路に修正する機能を有する。
【００２６】
滞在時間付与部１５Ｄは、経路修正部１５Ｃから修正後の経路の情報を入力し、また記憶部１４から移動速度１４Ｄや地図情報１４Ｇ等の必要な情報を読み出し、経路修正部１５Ｃによる修正後の経路に沿って始点から終点まで移動するのに要する時間と制限時間との差を残り時間として算出する機能を有する。また滞在時間付与部１５Ｄは、上記算出した残り時間を、修正後の経路上の通信品質が最大の地点での滞在時間として修正後の経路に付与する機能を有する。また滞在時間付与部１５Ｄは、上記滞在時間を付与した上記修正後の経路を、検索結果１４Ｉとして記憶部１４に記憶する機能を有する。
【００２７】
出力部１５Ｅは、記憶部１４から検索結果１４Ｉを読み出し、通信Ｉ／Ｆ部１１を通じて外部に出力し、或いは画面表示部１３に表示する機能を有する。
【００２８】
次に本実施形態の動作を説明する。
【００２９】
まず入力部１５Ａは、検索要求を通信Ｉ／Ｆ部１１や操作入力部１２から入力し、当該検索要求に含まれる始点情報１４Ａ、終点情報１４Ｂ、制限時間１４Ｃ、移動速度１４Ｄ、経路数１４Ｅ、および経由局数１４Ｆを記憶部１４に記憶する（図２のステップＳ１）。
【００３０】
次に経路検索部１５Ｂは、始点情報１４Ａで与えられる始点から、経由局数１４Ｆで与えられる数の無線基地局を経由して、終点情報１４Ｂで与えられる終点まで、制限時間１４Ｃで与えらえる制限時間内に到達する経路を、経路数１４Ｅで与えられる数を上限として、地図情報１４Ｇ上から検索する（ステップＳ２）。
【００３１】
次に経路修正部１５Ｃは、上記検索された経路を、経由する無線基地局の無線カバレッジエリア内で無線基地局直下と同等の通信品質が得られる無線基地局以外の地点を経由する、より経路長の短い経路に修正する（ステップＳ３）。
【００３２】
次に滞在時間付与部１５Ｄは、上記修正された経路に沿って始点から終点まで移動するのに要する時間と制限時間との差を、修正後の経路上の通信品質が最大の地点での滞在時間として修正後の経路に付与し、検索結果１４Ｉとして記憶部１４に記憶する（ステップＳ４）。
【００３３】
最後に出力部１５Ｅは、記憶部１４から検索結果１４Ｉを読み出し、通信Ｉ／Ｆ部１１を通じて外部に出力し、或いは画面表示部１３に表示する（ステップＳ５）。
【００３４】
次に、経路検索部１５Ｂの詳細な動作を図３を参照して説明する。図３は経路検索部１５Ｂの経路検索の動作説明図である。
【００３５】
（経由局数１４Ｆ＝１）
経路検索部１５Ｂは、経由局数１４Ｆが１の場合、図３の楕円Ｄ１を探索空間としての地図上に設定し、楕円Ｄ１内の領域から、経路数１４Ｅを上限数として、経由する無線基地局を選択する。ここで、楕円Ｄ１は、始点ｓおよび終点ｇを焦点とし、周上の点から始点ｓおよび終点ｇまでの距離の和が制限時間１４Ｃに移動できる総距離に等しい楕円である。総距離は、移動速度１４Ｄに制限時間１４Ｃを乗じることで求めることができる。
【００３６】
経路検索部１５Ｂは、楕円Ｄ１内に経路数１４Ｅを超える数の無線基地局ＢＳ１〜ＢＳｎ１が存在する場合、始点ｓおよび終点ｇからの距離の和がより短い無線基地局を優先的に選択する。或いは経路検索部１５Ｂは、通信品質のより良い無線基地局を優先的に選択する等、他の基準に従って無線基地局を選択してもよい。
【００３７】
経路検索部１５Ｂは、上記選択した無線基地局毎に、始点ｓから当該無線基地局までの最短経路と、当該無線基地局から終点ｇまでの最短経路とを地図上で検索し、それらの最短経路をつなぎあわせた経路を生成する。
【００３８】
（経由局数１４Ｆ≧２）
経路検索部１５Ｂは、経由局数１４Ｆが２以上の場合、まず図３の楕円Ｄ１を地図上に設定し、楕円Ｄ１内の領域から、２番目以降に経由する無線基地局を考慮して、最初に経由する無線基地局の候補を選択する。具体的には、最初に経由する無線基地局および終点ｇを焦点とし、周上の点から最初に経由する無線基地局および終点ｇまでの距離の和が、次式で与えられる残り時間内に移動できる総距離に等しい楕円の領域内に、焦点の一つとした無線基地局以外に残りの経由局数以上の無線基地局が存在している場合に限り、当該無線基地局を選択候補とする。
残り時間＝制限時間−始点ｓから当該無線基地局までの最短経路の移動時間  …（２）
【００３９】
図４は、始点ｓから終点ｇまで２つの無線基地局を経由して制限時間内に到達する経路を検索する過程を示している。この図４において、無線基地局ＢＳ１を最初の経由局として選択した場合、無線基地局ＢＳ１と終点ｇを焦点とし、周上の点から無線基地局ＢＳ１および終点ｇまでの距離の和が上記（２）式で与えられる残り時間内に移動できる総距離に等しい楕円がＤ２１とすると、この楕円Ｄ２１の領域内に無線基地局ＢＳ１以外に残りの経由局数である１以上の無線基地局ＢＳ２が存在するため、無線基地局ＢＳ１は選択候補となる。他方、無線基地局ＢＳ３を最初の経由局として選択した場合、無線基地局ＢＳ３と終点ｇを焦点とし、周上の点から無線基地局ＢＳ３および終点ｇまでの距離の和が上記（２）式で与えられる残り時間内に移動できる総距離に等しい楕円がＤ２３とすると、この楕円Ｄ２３の領域内には無線基地局ＢＳ３以外に残りの経由局数である１以上の無線基地局が存在しないため、無線基地局ＢＳ３は選択候補から除外される。
【００４０】
経路検索部１５Ｂは、上述のようにして求めた選択候補の中から最初に経由する無線基地局を選択する。選択候補が複数存在する場合、経路検索部１５Ｂは、上記楕円（Ｄ２１等）のスループット密度がより大きい無線基地局を優先的に選択する。ここで、楕円のスループット密度は、次式で与えられる。
スループット密度
＝（Σi=1n 転送速度ｉ×無線カバレッジエリア面積ｉ）／楕円面積    …（３）
ここで、ｉは楕円に含まれるｉ番目の無線カバレッジエリアを示す。
【００４１】
例えば図４の楕円Ｄ２１の場合、無線カバレッジエリアＲＺ１の転送速度に楕円Ｄ２１に含まれる無線カバレッジエリアＲＺ１の面積を乗じた値と、無線カバレッジエリアＲＺ２の転送速度に楕円Ｄ２１に含まれる無線カバレッジエリアＲＺ２の面積を乗じた値との総和を、楕円Ｄ２１の面積で割った値が、楕円Ｄ２１のスループット密度になる。
【００４２】
次に経路検索部１５Ｂは、楕円Ｄ１内の領域から上述のようにして選択した最初の経由局の次に経由する２番目の無線基地局を選択する。ここでは、無線基地局ＢＳ１が最初の経由局として選択されたものとして、２番目の無線基地局を選択する方法を説明する。
【００４３】
経路検索部１５Ｂは、上記楕円Ｄ２１、すなわち、無線基地局ＢＳ１と終点ｇを焦点とし、周上の点から無線基地局ＢＳ１および終点ｇまでの距離の和が上記（２）式で与えられる残り時間内に移動できる総距離に等しい楕円を地図上に設定し、楕円Ｄ２１内の領域から、２番目に経由する無線基地局を選択する。
【００４４】
経路検索部１５Ｂは、２番目の無線基地局が最後の経由局となる場合、即ち経由局数１４Ｆが２の場合、楕円Ｄ２１内の領域から、無線基地局ＢＳ１および終点ｇからの距離の和がより短い無線基地局を、経路数１４Ｅを超えない数だけ、優先的に選択する。或いは経路検索部１５Ｂは、通信品質のより良い無線基地局を優先的に選択する等、他の基準に従って無線基地局を選択してもよい。このような動作によって、例えば、経路数１４Ｅが２であれば、図３の楕円Ｄ２１内から２つの無線基地局ＢＳ１１、ＢＳ１２を選択する。また、楕円Ｄ２１内に存在する無線基地局の数が経路数１４Ｅに満たない場合は、楕円Ｄ２１内に存在する全ての無線基地局を選択する。そして、経路検索部１５Ｂは、２番目に経由するとして選択された無線基地局毎に、始点ｓから無線基地局ＢＳ１までの最短経路と、無線基地局ＢＳ１から２番目に経由する無線基地局までの最短距離と、２番目に経由する無線基地局から終点ｇまでの最短経路とを地図上で検索し、それらの最短経路をつなぎあわせた経路を生成する。
【００４５】
経路検索部１５Ｂは、２番目の経路局が最後の経由局でない場合、即ち経由局数１４Ｆが３以上の場合、１番目の無線基地局を選択した方法と同様の方法で、２番目の経由基地局を選択する。以下、最後に経由する無線基地局の一つ前の無線基地局まで、同様の方法で選択していく。そして、最後に経由する無線基地局を選択する場面に至ると、上述した最後の経由局を選択する場面と同様の方法で、経路数１４Ｅを超えない数だけ、最後に経由する無線基地局を選択する。例えば、経由局数１４Ｆが３で、経路数１４Ｅが２であれば、図３の楕円Ｄ３１から２つの無線基地局ＢＳ１１１、ＢＳ１１２を選択する。また、楕円Ｄ３１内に存在する無線基地局の数が経路数１４Ｅに満たない場合は、楕円Ｄ３１内に存在する全ての無線基地局を選択する。そして、経路検索部１５Ｂは、最後に経由するとして選択された無線基地局毎に、始点ｓから無線基地局ＢＳ１までの最短経路と、無線基地局ＢＳ１から２番目に経由する無線基地局までの最短距離と、…、最後に経由する無線基地局から終点ｇまでの最短経路とを地図上で検索し、それらの最短経路を経由順につなぎあわせた経路を生成する。
【００４６】
上記の方法は一例であり、始点から、経由局数１４Ｆで与えられる数の無線基地局を経由して、終点まで、制限時間内に到達する経路を、経路数１４Ｅで与えられる数を上限として、検索する方法は、上述した方法に限定されない。例えば、経由局数１４Ｆが２以上であって、最後に経由する無線基地局の選択数が経路数１４Ｅに満たない場合、始点ｓに近い側の経由局の選択場面に戻って新たな経由局の選択とその配下の経由局の選択を行うことで、経路数１４Ｅを満たす経路を検索するようにしてもよい。例えば、経由局数１４Ｆが２の場合、図３の無線基地局ＢＳ１を最初の経由局とするだけでは経路数が不足する場合、楕円Ｄ１から次に優先順位の高い無線基地局ＢＳ２を最初の経由局として新たに選択し、その無線基地局ＢＳ２と終点ｇとを焦点とし、周上の点から無線基地局ＢＳ２および終点ｇまでの距離の和が上記（２）式で与えられる残り時間内に移動できる総距離に等しい楕円を地図上に設定し、この楕円内の領域から、２番目に経由する無線基地局を選択するようにしてもよい。
【００４７】
次に、経路修正部１５Ｃの動作を詳細に説明する。
【００４８】
経路修正部１５Ｃは、先ず、経路検索部１５Ｂによって求められた経路が無線基地局の無線カバレッジエリアの外周と交わる地点を求める。経路が交わる地点は、無線カバレッジエリアが円形で且つ始点および終点を含まない場合、一つの無線カバレッジエリア当たり２つ存在する。次に経路修正部１５Ｃは、２つの交点が求められた無線カバレッジエリア毎に、経路と交わる２つの交点間の最短経路を検索する。次に経路修正部１５Ｃは、無線カバレッジエリア毎に、経路検索部１５Ｂによって求められた経路のうち、無線基地局を経由する交点間の経路を、上記交点間の最短経路で置き換える。こうして生成した経路を修正経路とする。
【００４９】
図５は、始点ｓから終点ｇまで１つの無線基地局ＢＳ１を経由して到達する経路Ｌ１１を修正する様子を示している。始点ｓから無線基地局ＢＳ１までの最短経路と、無線基地局ＢＳ１から終点ｇまでの最短経路とをつなげた経路Ｌ１１は、経路検索部１５Ｂによって検索された経路である。経路修正部１５Ｃは、経路Ｌ１１が無線基地局ＢＳ１の無線カバレッジエリアＲＺ１と交わる地点ｐ１１、ｐ１２を算出する。次に、経路修正部１５Ｃは、地点ｐ１１から地点ｐ１２までの最短経路を検索する。最後に、経路修正部１５Ｃは、元の経路Ｌ１１のうち、地点ｐ１１から無線基地局ＢＳ１を経由して地点ｐ１２まで至る経路部分を、地点ｐ１１から地点ｐ１２までの最短経路に置き換えた経路Ｌ１２を、修正経路として算出する。図５の例は、経路Ｌ１１が無線基地局ＢＳ１しか経由していないが、他の無線基地局を経由する場合、当該他の無線基地局の無線カバレッジエリアに対しても、無線基地局ＢＳ１の無線カバレッジエリアと同様な修正作業を行う。
【００５０】
経路修正部１５Ｃによる修正方法は、上述した方法に限定されず、他の方法を使用してもよい。例えば経路修正部１５Ｃは、経路検索部１５Ｂによって検索された経路を、無線カバレッジエリアに侵入する箇所と無線カバレッジエリアから退出する箇所との間の最短経路の中点を経由して、始点ｓから終点ｇに至る最短経路に置き換えるようにしても良い。図６はこの方法によって修正経路を求める様子を示しており、交点ｐ１１と交点ｐ１２との最短経路の中点を算出し、始点ｓから当該中点までの最短経路と、当該中点から終点ｇまでの最短経路とを求め、それらをつないだ経路を修正経路Ｌ２１としている。
【００５１】
なお、無線カバレッジエリアが円形で始点あるいは終点の一方を含む場合、経路が無線カバレッジエリアの外周と交わる交点は１つしか存在しない。このような場合、経路修正部１５Ｃは、当該１つの交点と始点あるいは終点との最短経路を修正経路として求めるようにしてもよい。また、無線カバレッジエリアが始点および終点の双方を含む場合、経路が無線カバレッジエリアの外周と交わる交点は存在しない。このような場合、経路修正部１５Ｃは、始点から終点までの最短経路を修正経路として求めるようにしてもよい。
【００５２】
次に、滞在時間付与部１５Ｄの詳細な動作を説明する。
【００５３】
滞在時間付与部１５Ｄは、まず、経路修正部１５Ｃによって算出された修正経路に沿って始点ｓから終点ｇまで移動するのに要する時間を算出する。移動時間は、修正経路の経路長を移動速度で除することで求めることができる。次に滞在時間付与部１５Ｄは、制限時間から移動時間を減算して残り時間を算出する。次に滞在時間付与部１５Ｄは、修正経路上の通信品質が最大の地点を求め、この求めた地点での滞在時間（停止時間）として上記算出した残り時間を付与する。例えば図５の場合、無線カバレッジエリアＲＺ１内では通信品質はすべて等しいので、地点ｐ１１から地点ｐ１２までの経路上の任意の地点を滞在地点とすることができる。滞在時間付与部１５Ｄは、滞在地点の情報と滞在時間とを修正経路に付与した内容を検索結果１４Ｉとして記憶部１４に記憶する。
【００５４】
このように本実施形態によれば、無線基地局を経由する経路を検索した後、その経路を、経由する無線基地局の無線カバレッジエリア内で無線基地局直下と同等の通信品質が得られる他の地点を経由する、より経路長の短い経路に修正し、この修正後の経路の移動時間と制限時間との差を修正後の経路上の通信品質が最大の地点での滞在時間として付与するようにしたため、無線基地局を経由する経路よりも経路長が短く、総通信品質が低下しない経路を求めることが可能となる。
【００５５】
[第２の実施形態]
図７を参照すると、本発明の第２の実施形態にかかる経路検索装置２０は、プロセッサ１５が最適経路選択部１５Ｆをさらに有する点で、図１に示した本発明の第１の実施形態にかかる経路検索装置１０と相違する。最適経路選択部１５Ｆは、経路検索部１５Ｂ等と同様にプログラム１４Ｐによって実現される。
【００５６】
最適経路選択部１５Ｆは、滞在時間付与部１５Ｄが記憶部１４に記憶した検索結果１４Ｉ、すなわち滞在時間が付与された修正後の経路の情報を読み出し、修正後の経路毎に、総通信品質量を算出し、総通信品質量が最大の修正後の経路を最適経路として検索結果１４Ｉに保存する機能を有する。修正後の経路の総通信品質量は、次式で与えられる。
【００５７】
総通信品質量
＝通信品質最大の地点での転送速度×滞在時間＋移動中に得られる転送量の総和
…（４）
【００５８】
次に本実施形態の動作を図８のフローチャートを参照して説明する。
【００５９】
まず入力部１５Ａは、検索要求を通信Ｉ／Ｆ部１１や操作入力部１２から入力し、当該検索要求に含まれる始点情報１４Ａ、終点情報１４Ｂ、制限時間１４Ｃ、移動速度１４Ｄ、経路数１４Ｅ、および経由局数１４Ｆを記憶部１４に記憶する（図８のステップＳ１１）。より最適な経路を検索するためには、数多くの経路を評価することが重要であるため、経路数１４Ｅは、無限大あるいは上限無しを指定しておくことが望ましい。また、経由局数１４Ｆは、経由局数の異なる経路を全て評価できるようにするために、可能な全ての経由局数、すなわち１、２、…、ｍ（ｍは予め設定された最大経由局数）を指定しておくことが望ましい。
【００６０】
次に経路検索部１５Ｂは、始点情報１４Ａで与えられる始点から、経由局数１４Ｆで与えられる数の無線基地局を経由して、終点情報１４Ｂで与えられる終点まで、制限時間１４Ｃで与えらえる制限時間内に到達する経路を、経路数１４Ｅで与えられる数を上限として、地図情報１４Ｇ上から検索する（ステップＳ１２）。経由局数１４Ｆとして、１、２、…、ｍが指定されている場合、経路検索部１５Ｂは、第１の実施形態で説明した経路局数＝１の動作、経路局数＝２の動作、…、経路局数＝ｍの動作を行う。
【００６１】
次に経路修正部１５Ｃは、上記検索された経路を、経由する無線基地局の無線カバレッジエリア内で無線基地局直下と同等の通信品質が得られる無線基地局以外の地点を経由する、より経路長の短い経路に修正する（ステップＳ１３）。
【００６２】
次に滞在時間付与部１５Ｄは、上記修正された経路に沿って始点から終点まで移動するのに要する時間と制限時間との差を、修正後の経路上の通信品質が最大の地点での滞在時間として修正後の経路に付与し、検索結果１４Ｉとして記憶部１４に記憶する（ステップＳ１４）。
【００６３】
次に最適経路選択部１５Ｆは、滞在時間が付与された修正後の経路毎に、総通信品質量を算出し、総通信品質量が最大の修正後の経路を最適経路として検索結果１４Ｉに保存する（ステップＳ１５）。
【００６４】
最後に出力部１５Ｅは、記憶部１４から検索結果１４Ｉ中の最適経路の情報を読み出し、通信Ｉ／Ｆ部１１を通じて外部に出力し、或いは画面表示部１３に表示する（ステップＳ１６）。
【００６５】
このように本実施形態によれば、無線基地局を経由する経路を検索した後、その経路を、経由する無線基地局の無線カバレッジエリア内で無線基地局直下と同等の通信品質が得られる他の地点を経由する、より経路長の短い経路に修正し、この修正後の経路の移動時間と制限時間との差を修正後の経路上の通信品質が最大の地点での滞在時間として付与するようにしたため、無線基地局を経由する経路よりも経路長が短く、総通信品質が低下しない経路を求めることが可能となる。
【００６６】
また本実施形態によれば、上記求めた経路のうちから総通信品質量が最大の修正後の経路を最適経路として選択することができる。
【００６７】
以上本発明を幾つかの実施形態を挙げて説明したが、本発明は以上の実施形態にのみ限定されず、その他各種の付加変更が可能である。
【００６８】
例えば、通信品質として転送量を用いたが、伝送誤り率、ＱＯＳ（Quality Of Service）、伝送遅延時間、総通信時間などを通信品質として用いてもよい。
【００６９】
また、移動速度１４Ｄ、経路数１４Ｅ、経由局数１４Ｆは、検索要求を通じて利用者から与えられるものとしたが、検索要求とは別に利用者から指定されてもよいし、或いはシステム固定のパラメータであってもよい。
【００７０】
また、無線カバレッジエリアの情報は、無線基地局直下と同等の通信品質が得られるエリアの地理的な情報だけでなく、それよりは通信品質が劣るエリアの地理的な情報が含まれていてもよい。また、経由する全ての無線基地局で無線基地局直下と同等の通信品質が得られるエリアを通過する必要は必ずしもなく、制限時間の関係で経路長をより短くする必要から、より通信品質の低いエリアを通過する無線基地局があってもよい。
【００７１】
また、経路検索装置は、携帯電話等の携帯端末に実装されていてもよいし、携帯端末からの検索要求をネットワーク経由で受信して処理するサーバ装置に実装されていてもよい。その際、経路検索部１５Ｂ、経路修正部１５Ｃ、滞在時間付与部１５Ｄ等は、物理的に同じコンピュータ上に存在する必要はかならずしもなく、複数のコンピュータに分散配置されていてもよい。
【符号の説明】
【００７２】
１０…経路検索装置
１１…通信Ｉ／Ｆ部
１２…操作入力部
１３…画面表示部
１４…記憶部
１５…プロセッサ
【図１】
2013140123.tif 000003
【図２】
2013140123.tif 000004
【図３】
2013140123.tif 000005
【図４】
2013140123.tif 000006
【図５】
2013140123.tif 000007
【図６】
2013140123.tif 000008
【図７】
2013140123.tif 000009
【図８】
2013140123.tif 000010
【図９】
2013140123.tif 000011