(57)【要約】【課題】無線通信の干渉の発生が抑止され且つ通信路コストが小さい通信経路の選択を可能とすること。【解決手段】仮通信経路と無線通信の干渉を生じやすい通信路を干渉通信路として判断し、仮通信経路に対し、干渉通信路を除いた通信路を加えることにより構成される新たな通信経路を、経路候補として選択し、記経路候補に含まれる全ての通信路の通信路コストを加算することにより総通信路コストを算出し、経路候補の中から、総通信路コストの値が最も小さい経路候補を、新たな仮通信経路として選択し、仮通信経路が終点ノードを含む場合に、その仮通信経路を最終的な通信経路として選択する。【選択図】図７
2009212848.tif 000002
【特許請求の範囲】
【請求項１】
通信方式に応じた通信路を形成することによって一又は複数の通信方式を用いて他のノードと無線通信を行う複数のノードで構成される無線通信ネットワークにおいて、始点ノードから終点ノードに至る通信経路を選択する通信経路選択装置であって、
前記無線通信ネットワークのノード間に形成される各通信路について、その通信方式及びその通信路コストを対応付けて記憶する通信環境記憶部と、
前記通信環境記憶部に記憶される情報を参照することにより、始点ノードと他のノードとを結ぶ通信経路を仮通信経路として選択し、仮通信経路に含まれる全ての前記通信路の前記通信路コストを加算することにより総通信路コストを算出する通信路選択部と、
前記通信環境記憶部に記憶される情報を参照することにより、前記仮通信経路と無線通信の干渉を生じやすい通信路を干渉通信路として判断する干渉通信路判断部と、
通信路選択部によって選択されている仮通信経路が前記終点ノードを含む場合に、その仮通信経路を最終的な通信経路として選択する終了判断部と、
を備え、
前記通信路選択部は、前記仮通信経路に対し、前記干渉通信路を除いた通信路を加えることにより構成される新たな通信経路を、経路候補として選択し、
前記通信路選択部は、前記経路候補の中から、前記総通信路コストの値が最も小さい経路候補を、新たな仮通信経路として選択する
通信経路選択装置。
【請求項２】
前記通信路選択部は、仮通信経路の初期状態を、通信路を一つも含まない状態とし、
前記通信路選択部は、前記仮通信経路に対し一つの通信路を加えることによって構成される前記経路候補を選択する
請求項１に記載の通信経路選択装置。
【請求項３】
前記干渉通信路判断部は、仮通信経路に含まれる各通信路について、その通信路の両端のノードのうち仮通信経路において始点ノード側に位置するノードを選択し、このノードとの間に当該通信路と同じ通信方式に応じた通信路を有する他のノードを全て選択し、当該通信路と同じ通信方式に応じた通信路であってこれらの他のノードを一端に有する全ての通信路を、干渉通信路として判断する、請求項１又は２に記載の通信経路選択装置。
【請求項４】
前記干渉通信路判断部は、仮通信経路に含まれる各通信路について、その通信路の両端のノードを選択し、これらのノードとの間に当該通信路と同じ通信方式に応じた通信路を有する他のノードを全て選択し、当該通信路と同じ通信方式に応じた通信路であってこれらの他のノードを一端に有する全ての通信路を、干渉通信路として判断する、請求項１又は２に記載の通信経路選択装置。
【請求項５】
無線通信ネットワークのノード間に形成される各通信路について、その通信方式及びその通信路コストを対応付けて記憶する通信環境記憶部を備えるコンピュータに対し、通信方式に応じた通信路を形成することによって一又は複数の通信方式を用いて他のノードと無線通信を行う複数のノードで構成される無線通信ネットワークにおいて、始点ノードから終点ノードに至る通信経路を、前記始点ノードと他のノードとを結ぶ通信経路を仮通信経路として繰り返し選択することによって、選択する通信経路選択方法であって、
前記コンピュータが、前記仮通信経路と無線通信の干渉を生じやすい通信路を干渉通信路として判断するステップと、
前記コンピュータが、前記仮通信経路に対し、前記干渉通信路を除いた通信路を加えることにより構成される新たな通信経路を、経路候補として選択するステップと、
前記コンピュータが、前記経路候補に含まれる全ての前記通信路の前記通信路コストを加算することにより総通信路コストを算出するステップと、
前記コンピュータが、前記経路候補の中から、前記総通信路コストの値が最も小さい経路候補を、新たな仮通信経路として選択するステップと、
前記コンピュータが、仮通信経路が前記終点ノードを含む場合に、その仮通信経路を最終的な通信経路として選択するステップと、
を含む通信経路選択方法。
【請求項６】
無線通信ネットワークのノード間に形成される各通信路について、その通信方式及びその通信路コストを対応付けて記憶する通信環境記憶部を備えるコンピュータに対し、通信方式に応じた通信路を形成することによって一又は複数の通信方式を用いて他のノードと無線通信を行う複数のノードで構成される無線通信ネットワークにおいて、始点ノードから終点ノードに至る通信経路を、前記始点ノードと他のノードとを結ぶ通信経路を仮通信経路として繰り返し選択することによって、選択させるコンピュータプログラムであって、
前記仮通信経路と無線通信の干渉を生じやすい通信路を干渉通信路として判断するステップと、
前記仮通信経路に対し、前記干渉通信路を除いた通信路を加えることにより構成される新たな通信経路を、経路候補として選択するステップと、
前記経路候補に含まれる全ての前記通信路の前記通信路コストを加算することにより総通信路コストを算出するステップと、
前記経路候補の中から、前記総通信路コストの値が最も小さい経路候補を、新たな仮通信経路として選択するステップと、
仮通信経路が前記終点ノードを含む場合に、その仮通信経路を最終的な通信経路として選択するステップと、
を実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信経路選択装置、通信経路選択方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
従来、グラフ理論における最短経路問題を解く方法として、ダイクストラ法がある（非特許文献１参照）。ダイクストラ法は、任意の出発点（ソースノード）から、目的点（ディスティネーションノード）までの最小コスト経路を算出する方法である。
このような最短経路問題を解く方法は、ルーティングプロトコルに適用される。ルーティングプロトコルとは、ネットワークの経路情報（ルーティングテーブル）を、ルータ同士が交換する際に使用されるプロトコルである。上述したダイクストラ法が適用されるルーティングプロトコルとして、ＯＳＰＦ（Open Shortest Path First）がある（非特許文献２参照）。
【０００３】
また、メトリック（コスト）に加えて、実際の回線帯域幅などの情報を用いて最小コスト経路を決定するルーティングプロトコルとして、ＣＳＰＦ（Constrained Shortest Path First）がある（非特許文献３参照）。メトリックとは、ディスティネーションノードまでのルータのホップ数等を表す情報である。
さらに、ノード間に複数のパスがある場合に、２地点間に複数の等コストのパスを設けて、トラフィックを均等に分散させるルーティングプロトコルとして、ＥＣＭＰ（Equal Cost Multi Path）がある（非特許文献４参照）。
【０００４】
このように、ルーティングプロトコルとして、様々な方法が考案されてきた。
【非特許文献１】E.W.Dijkstra, ”A note on two problems in connexion with graphs”, Numerische Mathematik, １９５９年１２月, Volume 1, Number 1,ｐ．２６９−２７１
【非特許文献２】“IETF RFC 2328 OSPF Version 2”、［online］、１９９８年４月、［平成２０年２月２５日検索］、インターネット＜URL: http://www.ietf.org/rfc/rfc2328.txt＞
【非特許文献３】“OSPF extensions for flexible CSPF algorithm support draft-satish-ospf-cspf-support-00”、［online］、２００２年１０月、［平成２０年２月２５日検索］、インターネット＜URL: http://infonet.cse.kyutech.ac.jp/~ike/I-D/draft-satish-ospf-cspf-support-00.txt＞
【非特許文献４】“IETF RFC 4928 Avoiding Equal Cost Multipath Treatment in MPLS Networks”、［online］、２００７年６月、［平成２０年２月２５日検索］、インターネット＜URL: http://www.ietf.org/rfc/rfc4928.txt＞
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、隣接するノード間において、異なる無線帯域を用いた複数の無線方式による無線通信が実行可能である場合、このノード間には各無線方式に応じた複数のパスが存在する。このような状況において、隣接する複数のパスで、同じ無線帯域を用いた無線方式が適用された場合、無線リンク同士の干渉が生じるという問題があった。
【０００６】
図３６は、このような従来技術における問題点を示す図である。図３６では、無線通信方式として、第一無線方式と第二無線方式とが用いられる。図３６では、ノードＮ１とノードＮ２とを結ぶパスとして、Ｐ１（１−２）及びＰ２（１−２）がある。また、ノードＮ２とノードＮ３とを結ぶパスとして、Ｐ１（２−３）及びＰ２（２−３）がある。これら４つのパスのうち、実線で示される二つのパスＰ１（１−２）及びＰ１（２−３）は、第一無線方式による無線通信を示すパスである。これに対し、点線で示される二つのパスＰ２（１−２）及びＰ２（２−３）は、第二無線方式による無線通信を示すパスである。そして、各パスにおけるリンクコストは、Ｐ１（１−２）では３、Ｐ２（１−２）では１、Ｐ１（２−３）では６、Ｐ２（２−３）では２である。このリンクコストの合計値が最も少ない経路が、最短経路となる。
【０００７】
図３６において、ソースノードをノードＮ１、ディスティネーションノードをＮ３としてダイクストラ法を用いた最短経路探索を実行すると、Ｐ２（１−２）及びＰ２（２−３）のパスが取得される。しかしながら、Ｐ２（１−２）及びＰ２（２−３）は、いずれも同じ無線通信方式を用いた経路である。そして、Ｐ２（１−２）及びＰ２（２−３）は、ノードＮ２を挟んで隣接したパスである。そのため、このような経路を採用すると、無線リンクの干渉が生じてしまう。
【０００８】
このように、従来のダイクストラ法では、無線リンクの干渉が考慮されていなかった。そのため、従来のダイクストラ法では、無線リンクの干渉の有無に関わらずに、最短経路の探索が行われていた。従って、場合によっては図３６のように無線リンクの干渉が発生してしまうという問題があった。
そこで、本発明は、無線通信の干渉の発生が抑止され且つ通信路コストが小さい通信経路の選択を可能とする装置、方法及びコンピュータプログラムを提供することを目的としている。
【課題を解決するための手段】
【０００９】
本発明は、通信方式に応じた通信路を形成することによって一又は複数の通信方式を用いて他のノードと無線通信を行う複数のノードで構成される無線通信ネットワークにおいて、始点ノードから終点ノードに至る通信経路を選択する通信経路選択装置であって、通信環境記憶部、通信路選択部、干渉通信路判断部、及び終了判断部を備える。通信環境記憶部は、無線通信ネットワークのノード間に形成される各通信路について、その通信方式及びその通信路コストを対応付けて記憶する。通信路選択部は、通信環境記憶部に記憶される情報を参照することにより、始点ノードと他のノードとを結ぶ通信経路を仮通信経路として選択し、仮通信経路に含まれる全ての前記通信路の前記通信路コストを加算することにより総通信路コストを算出する。干渉通信路判断部は、通信環境記憶部に記憶される情報を参照することにより、仮通信経路と無線通信の干渉を生じやすい通信路を干渉通信路として判断する。終了判断部は、通信路選択部によって選択されている仮通信経路が終点ノードを含む場合に、その仮通信経路を最終的な通信経路として選択する。また、通信路選択部は、仮通信経路に対し、干渉通信路を除いた通信路を加えることにより構成される新たな通信経路を、経路候補として選択する。また、通信路選択部は、経路候補の中から、総通信路コストの値が最も小さい経路候補を、新たな仮通信経路として選択する。
【００１０】
本発明の通信経路選択装置において、通信路選択部は、仮通信経路の初期状態を、通信路を一つも含まない状態としても良い。この場合、通信路選択部は、仮通信経路に対し一つの通信路を加えることによって構成される経路候補を選択しても良い。
【００１１】
本発明の通信経路選択装置において、干渉通信路判断部は、仮通信経路に含まれる各通信路について、その通信路の両端のノードのうち仮通信経路において始点ノード側に位置するノードを選択し、このノードとの間に当該通信路と同じ通信方式に応じた通信路を有する他のノードを全て選択し、当該通信路と同じ通信方式に応じた通信路であってこれらの他のノードを一端に有する全ての通信路を、干渉通信路として判断しても良い。
【００１２】
本発明の通信経路選択装置において、干渉通信路判断部は、仮通信経路に含まれる各通信路について、その通信路の両端のノードを選択し、これらのノードとの間に当該通信路と同じ通信方式に応じた通信路を有する他のノードを全て選択し、当該通信路と同じ通信方式に応じた通信路であってこれらの他のノードを一端に有する全ての通信路を、干渉通信路として判断しても良い。
【００１３】
本発明は、コンピュータを、上述した通信経路選択装置として動作させるためのコンピュータプログラムとして特定されても良い。また、本発明は、上述した通信経路選択装置として機能するコンピュータが行う通信経路選択方法として特定されても良い。
【発明の効果】
【００１４】
本発明により、無線通信の干渉の発生が抑止され且つ通信路コストが小さい通信経路の選択を可能となる。
【発明を実施するための最良の形態】
【００１５】
〔第一実施形態〕
まず、通信経路選択装置の第一実施形態である通信経路選択装置１について説明する。通信経路選択装置１は、バスによって接続されたＣＰＵやＲＡＭや補助記憶装置等を備え、補助記憶装置に記憶されたプログラムをＣＰＵが読み出して実行することにより動作する。また、通信経路選択装置１は、専用ハードウェアを用いて構成されても良い。
図１は、通信経路選択装置１の機能ブロックの概略を示す図である。通信経路選択装置１は、受付部１１、終了判断部１２、通信路選択部１３、干渉通信路判断部１４、及び通信環境記憶部１５を含む。以下、通信経路選択装置１の各機能部について説明する。
【００１６】
受付部１１は、入力装置や通信を介して、ソースノード（始点ノード）及びディスティネーションノード（終点ノード）の組み合わせ（以下、「通信経路条件」という。）の入力を受け付ける。例えば、受付部１１は、それぞれのノードのノード識別情報の組み合わせを、通信経路条件として受け付ける。
受付部１１は、通信経路選択装置１の操作者が入力装置を操作することによって入力したソースノード及びディスティネーションノードそれぞれのノード識別情報を受け付ける。入力装置とは、ポインティングデバイス（マウスやタブレット等）であっても良いし、キーボードや各種ボタンや音声入力装置であっても良い。また、例えば、受付部１１は、通信可能に接続された他の情報処理装置から、ソースノード及びディスティネーションノードそれぞれのノード識別情報を受け付けても良い。受付部１１は、入力を受け付けたソースノードのノード識別情報を通信路選択部１３へ渡す。また、受付部１１は、入力を受け付けたディスティネーションノードのノード識別情報を終了判断部１２へ渡す。
【００１７】
終了判断部１２は、通信経路の選択処理の終了判定を行う。終了判断部１２は、通信経路選択部１３によって選択されている仮通信経路の到達ノードが、受付部１１によって受け付けられたディスティネーションノードと一致した場合に、選択処理を終了させると判断する。到達ノードとは、仮通信経路の二端のノードのうち、ソースノードではないノードを示す。また、仮通信経路については後述する。終了判断部１２は、通信路選択部１３から、選択されている仮通信経路の情報を受け取ることにより、この判断を行う。そして、終了判断部１２は、選択処理を終了させると判断した場合、その旨を通信路選択部１３に通知する。また、終了判断部１２は、ディスティネーションノードと一致した到達ノードを含む仮通信経路を、最終的な通信経路として通信路選択部１３に通知する。
【００１８】
通信路選択部１３は、受付部１１を介して入力されたソースノードを一端に有する複数の仮通信経路を選択する。仮通信経路とは、通信路選択部１３が通信経路探索を行うにあたって、一時的に選択する通信経路である。通信路選択部１３は、総通信路コストの少ない順に、仮通信経路を選択する。通信路選択部１３は、新たな仮通信経路を選択する度に、その情報を終了判断部１２及び干渉通信路判断部１４に渡す。通信路選択部１３が通信経路を選択する処理の詳細については後述する。
【００１９】
干渉通信路判断部１４は、通信路選択部１３によって選択されている各仮通信経路について、干渉が生じやすい通信路（以下、「干渉通信路」という。）を判断する。干渉通信路判断部１４は、判断結果に基づいて、干渉通信路を、係る仮通信経路と対応付けて通信路選択部１３に通知する。干渉通信路判断部１４が干渉通信路を判断する判断基準として、ＣＳＭＡ／ＣＡ（Carrier Sense Multiple Access/Collision Avoidance）の動作を応用した判断基準と、ＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳ（Request to Send／Clear to Send）の動作を応用した判断基準とがある。各判断基準については後述する。
【００２０】
通信環境記憶部１５は、通信経路選択装置１の処理対象となる通信環境（無線通信ネットワークの構成）を記憶する。通信環境は、１又は複数の無線通信インタフェースを備える複数のノードによって構成される。各ノードは、無線通信インタフェースを用いて、他のノードと無線通信を行う。各ノードは、自ノードが備えている任意の無線通信インタフェースを用いて通信を行うことが可能である。このようなノード間の無線通信により、ノード間の通信路が構成される。
【００２１】
各通信路は、両端のノードと、使用される無線通信インタフェースに実装されている通信方式と、によって表され、通信路コストを有する。通信方式とは、８０２．１１ａ、８０２．１１ｂ、８０２．１１ｇ、８０２．１１ｊ、８０２．１６などの無線通信プロトコルである。また、同じ無線通信プロトコルであっても、無線通信に使用される周波数帯（チャネル）が異なる場合には、それらは異なる通信方式である。従って、例えば８０２．１１ｂの１チャネルと、８０２．１１ｂの５チャネルとは、異なる通信方式である。通信路コストとは、帯域、ノード間のホップ数、無線帯域ごとに設定される優先度などに基づいて定義される。無線帯域ごとに設定される優先度とは、ユーザによって予め一意に設定可能な値である。この優先度は、ノイズに対する耐性の高低に基づいて予め定義される値であっても良いし、通信速度の速さに基づいて予め定義される値であっても良いし、通信範囲の広さに基づいて予め定義される値であっても良い。これらの情報を、通信環境記憶部１５は記憶する。
【００２２】
次に、通信路における干渉について説明する。図２は、通信環境の一例を示す図である。図２に示される通信環境は、三つのノードＮ１、Ｎ２、Ｎ３から構成される。各ノードは、第一無線通信方式を用いた通信路Ｐ１（実線）、第二無線通信方式を用いた通信路Ｐ２（破線）、第三無線通信方式を用いた通信路Ｐ３（長二点鎖線）によって通信を行う。第一無線通信方式、第二無線通信方式、第三無線通信方式は、それぞれ異なる通信方式である。
【００２３】
通信路における干渉は、近傍の通信路同士において同じ通信方式を用いた無線通信が行われた場合に生じやすい。例えば、隣り合う通信路（即ち、一の通信路の一端と、他の通信路の一端とが同じノードであるような二つの通信路）において、通信路の干渉が生じやすい。図２の場合、ノードＮ１とノードＮ２とを結ぶ通信路と、ノードＮ２とノードＮ３とを結ぶ通信路とは、隣り合う通信路であるため、同じ通信方式を用いた通信路を選択すると、干渉が発生しやすい。従って、干渉の発生を抑止するために、通信経路選択装置１は、図３に示されるように、それぞれ異なる通信方式を用いた通信路を選択する。
【００２４】
次に、干渉が発生しやすい通信路の判断基準について説明する。図４は、通信環境の一例を示す図である。図４に示される通信環境は、九つのノードＮ１〜Ｎ９から構成される。各ノードは、第一無線通信方式を用いた通信路（実線）、第二無線通信方式を用いた通信路（破線）、第三無線通信方式を用いた通信路（長二点鎖線）によって、通信範囲内に位置する他のノードと通信を行う。図４の大きな円は、通信範囲の例を示す。ノードＮ１は、通信範囲内に位置する他のノード、即ちノードＮ２及びノードＮ４と通信を行うことができる。他の各ノードも、ノードＮ１と同じ通信範囲を有する。従って、図４において実線、破線、長二点鎖線によって接続されているノード同士が通信を行うことができる。
【００２５】
図５は、ＣＳＭＡ／ＣＡの動作を応用した判断基準を示す図である。図５において、黒塗りの矢印は、既に選択された通信路を示す。図５において、白抜きの矢印は、ＣＳＭＡ／ＣＡの動作を応用した判断基準において、黒塗りの矢印によって示された通信路と干渉を生じやすいと判断される通信路を示す。なお、図５では、黒塗りの矢印によって表される通信路と白抜きの矢印によって表される通信路とは、同じ通信方式による通信路である。各矢印は、通信の方向を示す。このとき、矢印の根元は通信の送信側を示し、矢印の矢先は通信の受信側を示す。黒塗りの矢印の場合は、送信側はノードＮ１であり、受信側はノードＮ４である。
【００２６】
ＣＳＭＡ／ＣＡの動作を応用した判断基準では、まず、干渉通信路判断部１４は、既に選択された通信路の送信側のノード（図５ではノードＮ１）の通信範囲内に位置する各ノード（ノードＮ１、ノードＮ２、ノードＮ４を含む）を選択する。そして、干渉通信路判断部１４は、同じ通信方式を用いた通信路であって、選択された各ノードが送信側となる全ての通信路を、既に選択された通信路と干渉を生じやすい通信路であるとして判断する。
【００２７】
図６は、ＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳの動作を応用した判断基準を示す図である。図６において、黒塗りの矢印及び白抜きの矢印が示す内容は、図５と同じである。ＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳの動作を応用した判断基準では、まず、干渉通信路判断部１４は、既に選択された通信路の送信側のノード（図６ではノードＮ１）又は受信側のノード（図６ではノードＮ４）の通信範囲内に位置する各ノード（ノードＮ１、ノードＮ２、ノードＮ４、ノードＮ５、ノードＮ７）を選択する。そして、干渉通信路判断部１４は、同じ通信方式を用いた通信路であって、選択された各ノードが送信側となる全ての通信路を、既に選択された通信路と干渉を生じやすい通信路であるとして判断する。
【００２８】
次に、通信経路選択装置１の動作について説明する。図７は、通信経路選択装置１の動作例を示すフローチャートである。図８は、通信環境の一例を示す図である。また、図９〜１３は、干渉通信路判断部１４がＣＳＭＡ／ＣＡの動作を応用した判断基準に基づいて処理を行う場合の、通信経路選択処理の流れを示す図である。図９〜１３において、ＮＧの文字が付された通信路は、その仮通信経路において干渉が生じやすいため選択されない通信路である。また、図９〜図１３において、下線を付した数字は、そのノードに至る仮通信経路の総通信路コストを示す。以下、図７〜図１３を用いて、図８に示される通信環境における通信経路選択装置１の動作を説明する。なお、干渉通信路判断部１４がＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳの動作を応用した判断基準に基づいて処理を行う場合の、通信経路選択処理の流れについては後述する。
【００２９】
まず、図８の通信環境について説明する。図８に示される通信環境は、四つのノードＮ１〜Ｎ４から構成される。“Ｎ１”〜“Ｎ４”は、ノードＮ１〜ノードＮ４それぞれのノード識別情報である。各ノードは、第一無線通信方式を用いた通信路（実線）、第二無線通信方式を用いた通信路（破線）、第三無線通信方式を用いた通信路（長二点鎖線）によって、通信範囲内に位置する他のノードと通信を行う。ノードＮ１の通信範囲内には、ノードＮ２が位置する。ノードＮ２の通信範囲内には、ノードＮ１及びノードＮ３が位置する。ノードＮ３の通信範囲内には、ノードＮ２及びノードＮ４が位置する。ノードＮ４の通信範囲内には、ノードＮ３が位置する。図８において実線、破線、長二点鎖線によって接続されているノード同士が通信を行うことができる。また、図８において、各通信路の通信路コストは図中に「コスト：」として示される値である。
【００３０】
通信環境記憶部１５は、図８に示される通信環境を記憶している。受付部１１は、ソースノードの値として“Ｎ１”、ディスティネーションノードの値として“Ｎ４”の入力を受け付ける（図７のステップＳ０１）。受付部１１は、ソースノードの値を通信路選択部１３に渡す。また、受付部１１は、ディスティネーションノードの値を終了判断部１２に渡す。
【００３１】
通信路選択部１３は、仮通信経路と、各仮通信経路における総通信路コストを記憶する。通信路選択部１３は、複数の仮通信経路を記憶できる。通信路選択部１３は、ソースノードの値（“Ｎ１”）を受付部１１から受け取ると、このソースノードを仮通信経路として記憶する。また、通信路選択部１３は、総通信路コストを“０”とする（図７のステップＳ０２）。なお、以下の説明において、ある通信路を含む仮通信経路を、［“通信路”，“通信路”，・・・］として現す。また、ソースノードのみからなる仮通信経路を、［ソースノード］として表す。
【００３２】
次に、干渉通信路判断部１４は、仮通信経路毎に干渉通信路を判断する（図７のステップＳ０３）。干渉通信路判断部１４は、仮通信経路に含まれる各通信路について、ＣＳＭＡ／ＣＡの動作を応用した判断基準に基づき、干渉通信路を判断する。干渉通信路判断部１４は、仮通信経路に含まれる全ての通信路についてこの判断を行い、この判断によって得られた全ての通信路を、この仮通信経路の干渉通信路として判断する。干渉通信路判断部１４は、仮通信経路［ソースノード］については、仮通信経路に通信路が一つも含まれないため、干渉通信路は無いと判断する。
【００３３】
次に、通信路選択部１３は、各仮通信経路について、仮通信経路と、この仮通信経路に加えることのできる通信路との組み合わせ（以下、「経路候補」という。）を全て選択する（図７のステップＳ０４）。仮通信経路に加えることができる通信路（以下、「新通信路」という。）とは、仮通信経路の到達ノードを送信側とした通信路であって、干渉通信路として判断されていない通信路である。以下の説明において、経路候補を、〔“仮通信経路”，“新通信路”〕として表す。
【００３４】
通信路選択部１３は、新通信路として、ソースノードＮ１から伸びる三つの通信路を選択する。即ち、通信路選択部１３は、新通信路として、通信路Ｐ１（１−２）、通信路Ｐ２（１−２）、通信路Ｐ３（１−２）を選択する。そして、通信路選択部１３は、経路候補として、〔［ソースノード］，Ｐ１（１−２）〕、〔［ソースノード］，Ｐ２（１−２）〕、〔［ソースノード］，通信路Ｐ３（１−２）〕を選択する。
【００３５】
次に、通信路選択部１３は、各経路候補について、仮通信経路に対して新通信路を加えた場合の総通信路コストを算出する（図７のステップＳ０５）。通信路選択部１３は、仮通信経路の総通信路コストに、新通信路の通信路コストを加算することによって、新たな総通信路コストを算出する。図８の場合、通信路選択部１３は、各新通信路の通信路コストとして“１”、“２”、“３”を通信環境記憶部１５から読み出す。そして、通信路選択部１３は、現在の仮通信経路の総通信路コストに、各新通信路の通信路コストを加算し、各経路候補の総通信路コストとして、“１”、“２”、“３”を算出する。通信路選択部１３は、各経路候補と、その総通信路コストとを対応付けて記憶する。
【００３６】
次に、通信路選択部１３は、経路候補の中から、最も総通信路コストが小さい経路候補を選択する（図７のステップＳ０６）。通信路選択部１３は、総通信路コストが“１”となる経路候補〔［ソースノード］，Ｐ１（１−２）〕を選択する。そして、通信路選択部１３は、この経路候補の仮通信経路に新通信路を加えることにより、新たな仮通信経路として［Ｐ１（１−２）］を取得する（図７のステップＳ０７：図９参照）。このとき、通信路選択部１３は、新たな仮通信経路の総数進路コストも記憶する。この時点で、通信路選択部１３は、仮通信経路として、仮通信経路［ソースノード］と［Ｐ１（１−２）］とを記憶している。また、通信路選択部１３は、それぞれの総通信路コストとして、“０”と“１”を記憶している。
【００３７】
次に、終了判断部１２は、通信路選択部１３によって新たに選択された仮通信経路の到達ノードがディスティネーションノードであるか否か判断する（図７のステップＳ０８）。この場合、新たに選択された仮通信経路の到達ノードは、ノードＮ１であり、ディスティネーションノードではないため、終了判断部１２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。終了判断部１２が新たに選択された仮通信経路の到達ノードをディスティネーションであると判断するまで、通信経路選択装置１はステップＳ０３からステップＳ０８の処理を繰り返し実行する。
【００３８】
次に、干渉通信路判断部１４は、新たに選択された仮通信経路［Ｐ１（１−２）］について、干渉通信路を以下のように判断する（図７のステップＳ０３）。この仮通信経路に含まれる通信路はＰ１（１−２）のみであるため、干渉通信路判断部１４は、この通信路についてのみ判断を行う。この通信路は、送信側がノードＮ１であり、第一無線通信方式を用いた通信路である。そのため、干渉通信路判断部１４は、第一無線通信方式を用いた通信路であって、ノードＮ１の通信範囲内に位置するノード（ノードＮ２）を送信側とする通信路Ｐ１（２−３）を、干渉通信路と判断する。干渉通信路判断部１４は、干渉通信路を、仮通信経路と対応付けて記憶する。このように記憶することにより、その後の処理において、この仮通信経路にさらに新通信路が加えられた場合に、この仮通信経路に含まれる全ての通信路について干渉通信路の判断を行うことなく、干渉通信路を判断することが可能となる。即ち、干渉通路判断部１４は、その後の処理において、新たに加わった新通信路についてのみ、干渉通信路を判断すれば良い。干渉通信路判断部１４は、既に記憶している干渉通信路と、新たに判断した干渉通信路とを併せて、この仮通信経路における干渉通信路として判断する。
【００３９】
次に、通信路選択部１３は、各仮通信経路について、干渉通信路判断部１４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部１３は、〔［ソースノード］，Ｐ２（１−２）〕、〔［ソースノード］，Ｐ３（１−２）〕、〔［Ｐ１（１−２）］，Ｐ２（２−３）〕、〔［Ｐ１（１−２）］，Ｐ３（２−３）〕を、経路候補として選択する。そして、通信路選択部１３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。
【００４０】
このとき、通信路選択部１３は、既に総通信路コストが算出された経路候補については、計算を行わない。既に算出された総通信路コストを経路候補と対応付けて記憶しているためである。この場合、通信路選択部１３は、〔［ソースノード］，Ｐ２（１−２）〕と、〔［ソースノード］，Ｐ３（１−２）〕の総通信路コストは、既に記憶している。そのため、通信路選択部１３は、経路候補〔［Ｐ１（１−２）］，Ｐ２（２−３）〕及び経路候補〔［Ｐ１（１−２）］，Ｐ３（２−３）〕についての総通信路コストを算出する。
【００４１】
新通信路Ｐ２（２−３）及び新通信路Ｐ３（２−３）の通信路コストは、それぞれ“３”及び“５”である。通信路選択部１３は、経路候補の総通信路コストとして、仮通信経路［Ｐ１（１−２）］の総通信路コスト“１”と、各新通信路の通信路コストとを加算し、各経路候補の総通信路コスト“４”と“６”を算出する。このとき、通信路選択部１３は、この新たな総通信路コストを、各経路候補と対応付けて記憶する。
【００４２】
次に、通信路選択部１３は、全ての経路候補の中から、総通信路コストが最も小さい経路候補を選択する（図７のステップＳ０６）。この場合、最も小さい総通信路コストは、“２”である。そのため、通信路選択部１３は、この総通信路コストに対応する経路候補〔［ソースノード］，Ｐ２（１−２）〕を選択する。そして、通信路選択部１３は、この経路候補に基づき、新たな仮通信経路［Ｐ２（１−２）］を取得する（図７のステップＳ０７：図１０参照）。
【００４３】
次に、終了判断部１２は、新たな仮通信経路の到達ノードＮ２がディスティネーションノードであるか否か判断する。この場合、ノードＮ２はディスティネーションノードではないため、終了判断部１２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。
【００４４】
次に、干渉通信路判断部１４は、新たに選択された仮通信経路［Ｐ２（１−２）］について、干渉通信路を判断する（図７のステップＳ０３）。この場合、干渉通信路判断部１４は、Ｐ２（２−３）を干渉通信路として判断する。なお、ソースノードＮ１から通信路Ｐ１（１−２）を介してノードＮ２に至る仮通信経路［Ｐ１（１−２）］と、ソースノードＮ１から通信路Ｐ２（１−２）を介してノードＮ２に至る仮通信経路［Ｐ２（１−２）］とは、いずれもノードＮ１からノードＮ２に至る仮通信経路であるが、用いている通信路が異なるため、異なる仮通信経路である。そのため、それぞれの仮通信経路において、干渉が生じやすいと判断される通信路は異なる。
【００４５】
次に、通信路選択部１３は、各仮通信経路について、干渉通信路判断部１４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部１３は、〔［ソースノード］，Ｐ３（１−２）〕、〔［Ｐ１（１−２）］，Ｐ２（２−３）〕、〔［Ｐ１（１−２）］，Ｐ３（２−３）〕、〔［Ｐ２（１−２）］，Ｐ１（２−３）〕、〔［Ｐ２（１−２）］，Ｐ３（２−３）〕を経路候補として選択する。そして、通信路選択部１３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、それぞれ“３”、“４”、“６”、“３”、“７”となる。そのため、通信路選択部１３は、この中で最も小さい“３”に係る経路候補、〔［ソースノード］，Ｐ３（１−２）〕及び〔［Ｐ２（１−２）］，Ｐ１（２−３）〕を選択する（図７のステップＳ０６）。そして、通信路選択部１３は、この経路候補に基づき、新たな仮通信経路［Ｐ３（１−２）］及び［Ｐ２（１−２），Ｐ１（２−３）］を取得する（図７のステップＳ０７：図１１参照）。
【００４６】
次に、終了判断部１２は、新たな仮通信経路の到達ノードＮ２及びノードＮ３がディスティネーションノードであるか否か判断する。この場合、ノードＮ２及びノードＮ３はディスティネーションノードではないため、終了判断部１２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。
【００４７】
次に、干渉通信路判断部１４は、新たに選択された仮通信経路［Ｐ３（１−２）］及び［Ｐ２（１−２），Ｐ１（２−３）］それぞれについて、干渉通信路を判断する（図７のステップＳ０３）。この場合、仮通信経路［Ｐ３（１−２）］における干渉通信路としてＰ３（２−３）を、仮通信経路［Ｐ２（１−２），Ｐ１（２−３）］における干渉通信路としてＰ２（２−３）及びＰ１（３−４）を判断する。
【００４８】
次に、通信路選択部１３は、各仮通信経路について、干渉通信路判断部１４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部１３は、〔［Ｐ１（１−２）］，Ｐ２（２−３）〕、〔［Ｐ１（１−２）］，Ｐ３（２−３）〕、〔［Ｐ２（１−２）］，Ｐ３（２−３）〕、〔［Ｐ３（１−２）］，Ｐ１（２−３）〕、〔［Ｐ３（１−２）］，Ｐ２（２−３）〕、〔［Ｐ２（１−２），Ｐ１（２−３）］，Ｐ２（３−４）〕、〔［Ｐ２（１−２），Ｐ１（２−３）］，Ｐ３（３−４）〕を経路候補として選択する。そして、通信路選択部１３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、それぞれ“４”、“６”、“７”、“４”、“６”、“６”、“９”となる。そのため、通信路選択部１３は、この中で最も小さい“４”に係る経路候補、〔［Ｐ１（１−２）］，Ｐ２（２−３）〕及び〔［Ｐ３（１−２）］，Ｐ１（２−３）〕を選択する（図７のステップＳ０６）。そして、通信路選択部１３は、この経路候補に基づき、新たな仮通信経路［Ｐ１（１−２），Ｐ２（２−３）］及び［Ｐ３（１−２），Ｐ１（２−３）］を取得する（図７のステップＳ０７：図１２参照）。
【００４９】
次に、終了判断部１２は、新たな仮通信経路の到達ノードＮ３がディスティネーションノードであるか否か判断する。この場合、ノードＮ３はディスティネーションノードではないため、終了判断部１２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。
【００５０】
次に、干渉通信路判断部１４は、新たに選択された仮通信経路［Ｐ１（１−２），Ｐ２（２−３）］及び［Ｐ３（１−２），Ｐ１（２−３）］それぞれについて、干渉通信路を判断する（図７のステップＳ０３）。この場合、仮通信経路［Ｐ１（１−２），Ｐ２（２−３）］における干渉通信路としてＰ２（３−４）を、仮通信経路［Ｐ３（１−２），Ｐ１（２−３）］における干渉通信路としてＰ１（３−４）を判断する。
【００５１】
次に、通信路選択部１３は、各仮通信経路について、干渉通信路判断部１４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部１３は、〔［Ｐ１（１−２）］，Ｐ３（２−３）〕、〔［Ｐ２（１−２）］，Ｐ３（２−３）〕、〔［Ｐ３（１−２）］，Ｐ２（２−３）〕、〔［Ｐ１（１−２），Ｐ２（２−３）］，Ｐ１（３−４）〕、〔［Ｐ１（１−２），Ｐ２（２−３）］，Ｐ３（３−４）〕、〔［Ｐ２（１−２），Ｐ１（２−３）］，Ｐ２（３−４）〕、〔［Ｐ２（１−２），Ｐ１（２−３）］，Ｐ３（３−４）〕、〔［Ｐ３（１−２），Ｐ１（２−３）］，Ｐ２（３−４）〕、〔［Ｐ３（１−２），Ｐ１（２−３）］，Ｐ３（３−４）〕を経路候補として選択する。そして、通信路選択部１３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、それぞれ“６”、“７”、“６”、“５”、“１０”、“６”、“９”、“７”、“１０”となる。そのため、通信路選択部１３は、この中で最も小さい“５”に係る経路候補、〔［Ｐ１（１−２），Ｐ２（２−３）］，Ｐ１（３−４）〕を選択する（図７のステップＳ０６）。そして、通信路選択部１３は、この経路候補に基づき、新たな仮通信経路［Ｐ１（１−２），Ｐ２（２−３），Ｐ１（３−４）］を取得する（図７のステップＳ０７：図１３参照）。
【００５２】
次に、終了判断部１２は、新たな仮通信経路の到達ノードＮ４がディスティネーションノードであるか否か判断する。この場合、ノードＮ４はディスティネーションノードである。そのため、終了判断部１２は、通信経路の選択処理は終了すると判断する（図７のステップＳ０８−ＹＥＳ）。終了判断部１２は、通信経路の選択処理が終了することを通信路選択部１３へ通知する。そして、終了判断部１２は、［Ｐ１（１−２），Ｐ２（２−３），Ｐ１（３−４）］を最終的な通信経路として判断する。通信路選択部１３は、終了判断部１２から、通信経路の選択処理が終了することの通知を受けると、処理を終了する。
【００５３】
図１４〜１７は、干渉通信路判断部１４が、ＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳの動作を応用した判断基準に基づいて処理を行う場合の、通信経路選択処理の流れを示す図である。図１４〜１７における各表記は、図９〜１３のものと同じである。以下、図７及び図１４〜１７を用いて、干渉通信路判断部１４がＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳの動作を応用した判断基準に基づいて処理を行う場合の、図８に示される通信環境における通信経路選択装置１の動作を説明する。
【００５４】
図７のステップＳ０１及びステップＳ０２の処理は、干渉通信路判断部１４がＣＳＭＡ／ＣＡの動作を応用した判断基準に基づいて処理を行う場合と変わらないため、説明を省略する。また、通信路選択部１３が仮通信経路として［Ｐ１（１−２）］、［Ｐ３（１−２）］、及び［Ｐ２（１−２），Ｐ１（２−３）］を取得するまでの処理も、干渉通信路判断部１４がＣＳＭＡ／ＣＡの動作を応用した判断基準に基づいて処理を行う場合と変わらないため、説明を省略する。この後、ＣＳＭＡ／ＣＡのみの場合、干渉通信路判断部１４は、［Ｐ２（１−２），Ｐ１（２−３）］の干渉通信路として、Ｐ１（３−４）のみを選択する（図１１参照）。なお、この場合、干渉通信路判断部１４は、［Ｐ１（１−２）］の干渉通信路としてＰ１（３−４）を、［Ｐ３（１−２）］の干渉通信路としてＰ３（３−４）を、それぞれ選択する。
【００５５】
しかしながら、ＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳの動作を応用した判断基準の場合、干渉通信路判断部１４は仮通信経路［Ｐ２（１−２），Ｐ１（２−３）］について干渉通信路を以下のように判断する（図７のステップＳ０３：図１４参照）。この仮通信経路に含まれる通信路はＰ２（１−２）及びＰ１（２−３）であるため、干渉通信路判断部１４は、この二つの通信路について判断を行う。まず、干渉通信路判断部１４は、Ｐ２（１−２）について干渉通信路を判断する。この通信路は、送信側がノードＮ１であり、受信側がノードＮ２であり、第二無線通信方式を用いた通信路である。そのため、干渉通信路判断部１４は、同じ通信方式（第二無線通信方式）を用いた通信路であって、ノードＮ１の通信範囲内に位置するノード（ノードＮ１及びノードＮ２）を送信側とする通信路Ｐ２（２−３）を、干渉通信路と判断する。
【００５６】
さらに、干渉通信路判断部１４は、同じ通信方式（第二無線通信方式）を用いた通信路であって、ノードＮ２の通信範囲内に位置するノード（ノードＮ１、ノードＮ２、及びノードＮ３）を送信側とする通信路Ｐ２（３−４）を、干渉通信路と判断する。次に、干渉通信路判断部１４は、Ｐ１（２−３）について処理を行い、Ｐ１（３−４）を干渉通信路と判断する。
【００５７】
次に、通信路選択部１３は、各仮通信経路について、干渉通信路判断部１４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部１３は、〔［Ｐ１（１−２）］，Ｐ２（２−３）〕、〔［Ｐ１（１−２）］，Ｐ３（２−３）〕、〔［Ｐ２（１−２）］，Ｐ３（２−３）〕、〔［Ｐ３（１−２）］，Ｐ１（２−３）〕、〔［Ｐ３（１−２）］，Ｐ２（２−３）〕、〔［Ｐ２（１−２），Ｐ１（２−３）］，Ｐ３（３−４）〕を経路候補として選択する。そして、通信路選択部１３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、それぞれ“４”、“６”、“７”、“４”、“６”、“９”となる。そのため、通信路選択部１３は、この中で最も小さい“４”に係る経路候補、〔［Ｐ１（１−２）］，Ｐ２（２−３）〕及び〔［Ｐ３（１−２）］，Ｐ１（２−３）〕を選択する（図７のステップＳ０６）。そして、通信路選択部１３は、この経路候補に基づき、新たな仮通信経路［Ｐ１（１−２），Ｐ２（２−３）］及び［Ｐ３（１−２），Ｐ１（２−３）］を取得する（図７のステップＳ０７：図１５参照）。
【００５８】
次に、終了判断部１２は、新たな仮通信経路の到達ノードＮ３がディスティネーションノードであるか否か判断する。この場合、ノードＮ３はディスティネーションノードではないため、終了判断部１２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。
【００５９】
次に、干渉通信路判断部１４は、新たに選択された仮通信経路［Ｐ１（１−２），Ｐ２（２−３）］及び［Ｐ３（１−２），Ｐ１（２−３）］それぞれについて、干渉通信路を判断する（図７のステップＳ０３）。この場合、仮通信経路［Ｐ１（１−２），Ｐ２（２−３）］における干渉通信路としてＰ１（３−４）及びＰ２（３−４）を、仮通信経路［Ｐ３（１−２），Ｐ１（２−３）］における干渉通信路としてＰ１（３−４）及びＰ３（３−４）を判断する。
【００６０】
次に、通信路選択部１３は、各仮通信経路について、干渉通信路判断部１４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部１３は、〔［Ｐ１（１−２）］，Ｐ３（２−３）〕、〔［Ｐ２（１−２）］，Ｐ３（２−３）〕、〔［Ｐ３（１−２）］，Ｐ２（２−３）〕、〔［Ｐ１（１−２），Ｐ２（２−３）］，Ｐ３（３−４）〕、〔［Ｐ２（１−２），Ｐ１（２−３）］，Ｐ３（３−４）〕、〔［Ｐ３（１−２），Ｐ１（２−３）］，Ｐ２（３−４）〕を経路候補として選択する。そして、通信路選択部１３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、それぞれ“６”、“７”、“６”、“１０”、“９”、“７”となる。そのため、通信路選択部１３は、この中で最も小さい“６”に係る経路候補、〔［Ｐ１（１−２）］，Ｐ３（２−３）〕及び〔［Ｐ３（１−２）］，Ｐ２（２−３）〕を選択する（図７のステップＳ０６）。そして、通信路選択部１３は、この経路候補に基づき、新たな仮通信経路［Ｐ１（１−２），Ｐ３（２−３）］及び［Ｐ３（１−２），Ｐ２（２−３）］を取得する（図７のステップＳ０７：図１６参照）。
【００６１】
次に、終了判断部１２は、新たな仮通信経路の到達ノードＮ３がディスティネーションノードであるか否か判断する。この場合、ノードＮ３はディスティネーションノードではないため、終了判断部１２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。
【００６２】
次に、干渉通信路判断部１４は、新たに選択された仮通信経路［Ｐ１（１−２），Ｐ３（２−３）］及び［Ｐ３（１−２），Ｐ２（２−３）］それぞれについて、干渉通信路を判断する（図７のステップＳ０３）。この場合、仮通信経路［Ｐ１（１−２），Ｐ３（２−３）］における干渉通信路としてＰ１（３−４）及びＰ３（３−４）を、仮通信経路［Ｐ３（１−２），Ｐ２（２−３）］における干渉通信路としてＰ２（３−４）及びＰ３（３−４）を判断する。
【００６３】
次に、通信路選択部１３は、各仮通信経路について、干渉通信路判断部１４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部１３は、〔［Ｐ２（１−２）］，Ｐ３（２−３）〕、〔［Ｐ１（１−２），Ｐ２（２−３）］，Ｐ３（３−４）〕、〔［Ｐ１（１−２），Ｐ３（２−３）］，Ｐ２（３−４）〕、〔［Ｐ２（１−２），Ｐ１（２−３）］，Ｐ３（３−４）〕、〔［Ｐ３（１−２），Ｐ１（２−３）］，Ｐ２（３−４）〕、〔［Ｐ３（１−２），Ｐ２（２−３）］，Ｐ１（３−４）〕を経路候補として選択する。そして、通信路選択部１３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、それぞれ“７”、“１０”、“９”、“９”、“７”、“７”となる。そのため、通信路選択部１３は、この中で最も小さい“７”に係る経路候補、〔［Ｐ２（１−２）］，Ｐ３（２−３）〕、〔［Ｐ３（１−２），Ｐ１（２−３）］，Ｐ２（３−４）〕、及び〔［Ｐ３（１−２），Ｐ２（２−３）］，Ｐ１（３−４）〕を選択する（図７のステップＳ０６）。そして、通信路選択部１３は、この経路候補に基づき、新たな仮通信経路［Ｐ２（１−２），Ｐ３（２−３）］、［Ｐ３（１−２），Ｐ１（２−３），Ｐ２（３−４）］、及び［Ｐ３（１−２），Ｐ２（２−３），Ｐ１（３−４）］を取得する（図７のステップＳ０７：図１７参照）。
【００６４】
次に、終了判断部１２は、新たな仮通信経路の到達ノードＮ４がディスティネーションノードであるか否か判断する。この場合、ノードＮ４はディスティネーションノードである。そのため、終了判断部１２は、通信経路の選択処理は終了すると判断する（図７のステップＳ０８−ＹＥＳ）。終了判断部１２は、通信経路の選択処理が終了することを通信路選択部１３へ通知する。そして、終了判断部１２は、［Ｐ３（１−２），Ｐ１（２−３），Ｐ２（３−４）］及び［Ｐ３（１−２），Ｐ２（２−３），Ｐ１（３−４）］の二つを最終的な通信経路として判断する。通信路選択部１３は、終了判断部１２から、通信経路の選択処理が終了することの通知を受けると、処理を終了する。このように複数の通信経路が選択された場合、終了判断部１２は、複数の通信経路の中から一つの通信経路をさらに選択しても良い。この選択方法は、どのような方法が採用されても良い。例えば、終了判断部１２は、通信路の数が最も少ない通信経路を選択しても良いし、ランダムに一つの通信経路を選択しても良いし、最初に選択された通信経路を選択しても良い。
【００６５】
通信経路選択装置１は、仮通信経路の到達ノードから他のノードへの通信路を選択する際に、干渉が生じやすい通信路を選択の候補から除外して選択を行う。具体的には、干渉通信路判断部１４が、通信路について仮通信経路と干渉が生じやすいか否かを判断し、通信路選択部１３は干渉が生じやすいと判断されていない通信路を選択する。そのため、通信経路選択装置１は、無線通信の干渉が生じにくい通信経路を選択することを可能とする。
【００６６】
また、通信経路選択装置１は、ソースノードから伸びる各通信経路について、総通信路コストが小さいものから仮通信経路として選択する。そして、仮通信経路の到達ノードが初めてディスティネーションノードになった場合に、その仮通信経路を通信経路として選択する。そのため、通信経路選択装置１は、干渉が生じにくい通信経路であって、総通信路コストが小さい通信経路を選択することを可能とする。そして、このように選択された通信経路を用いて無線通信を行うことにより、リンク間の無線干渉を低減させることが可能となる。
【００６７】
また、通信経路選択装置１は、干渉通信路を判断する際に、ＣＳＭＡ／ＣＡの動作を応用した判断基準、又はＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳの動作を応用した判断基準、に基づいて判断を行う。この場合、通信経路選択装置１の干渉通信路判断部１４は、実際に（物理的に）ＣＳＭＡ／ＣＡやＲＴＳ／ＣＴＳを実行するわけではなく、ネットワークトポロジの情報に基づいて判断を行う。そのため、実際のその通信経路上にパケットを送信する際に、ＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳを使用しなくとも、隠れ端末を回避した経路構築が可能となるなど、ＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳを使用した場合と同等の効果を奏することが可能となる。
【００６８】
<変形例>
通信路選択部１３は、経路候補が無い場合には、仮通信経路の到達ノードがディスティネーションノードに達していないとしても、処理を終了しても良い。また、このような場合、通信路選択部１３は、干渉通路判断部１４の判断結果に関わらず、干渉通信路を新通信路として選択することによって処理を継続しても良い。
また、干渉通信路判断部１４が干渉通信路を判断する判断基準としては、上述した判断基準以外の方法が採用されても良い。
【００６９】
〔第二実施形態〕
次に、通信経路選択装置の第二実施形態である通信経路選択装置２について説明する。通信経路選択装置２は、バスによって接続されたＣＰＵやＲＡＭや補助記憶装置等を備え、補助記憶装置に記憶されたプログラムをＣＰＵが読み出して実行することにより動作する。また、通信経路選択装置２は、専用ハードウェアを用いて構成されても良い。
図１８は、通信経路選択装置２の機能ブロックの概略を示す図である。通信経路選択装置２は、受付部２１、終了判断部２２、通信路選択部２３、干渉通信路判断部２４、通信環境記憶部２５、及び通信経路記憶部２６を含む。以下、通信経路選択装置２の各機能部について説明する。
【００７０】
受付部２１は、受付部１１と同様に構成される。また、終了判断部２２は、終了判断部１２と同様に構成される。また、通信環境記憶部２５は、通信環境記憶部１５と同様に構成される。そのため、受付部２１、終了判断部２２、及び通信環境記憶部２５についての説明は省略する。
【００７１】
通信路選択部２３は、通信路選択部１３と同様の処理を行うことによって、最終的な通信経路を選択する。通信路選択部２３は、終了判断部２２から、通信経路の選択処理が終了することの通知を受けると、最終的な通信経路を通信経路記憶部２６に書き込む。
干渉通信路判断部２４は、干渉通信路を判断する際に、仮通信経路と干渉が生じやすい通信路のみでなく、通信経路記憶部２６に記憶されている通信経路との干渉が生じやすい通信路も、干渉通信路として判断する。
通信経路記憶部２６は、既に選択されている通信経路を記憶する。
【００７２】
次に、通信経路選択装置２の動作について説明する。図１９は、通信環境の一例を示す図である。また、図２０〜２９は、干渉通信路判断部２４がＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳの動作を応用した判断基準に基づいて処理を行う場合の、通信経路選択処理の流れを示す図である。図２０〜２９において、ＮＧの文字が付された通信路は、その仮通信経路において干渉が生じやすいため選択されない通信路である。また、図２０〜図２９において、下線を付した数字は、そのノードに至る仮通信経路の総通信路コストを示す。以下、図１９〜図２９を用いて、図１９に示される通信環境における通信経路選択装置２の動作を説明する。なお、通信経路選択装置２は、干渉通信路判断部２４の処理内容が干渉通信路判断部１４の処理内容と異なるものの、図７に示されるフローチャートと同じ流れで処理を行う。
【００７３】
まず、図１９の通信環境について説明する。図１９に示される通信環境は、六つのノードＮ１〜Ｎ６から構成される。“Ｎ１”〜“Ｎ６”は、ノードＮ１〜ノードＮ６それぞれのノード識別情報である。各ノードは、第一無線通信方式を用いた通信路（実線）、第二無線通信方式を用いた通信路（破線）、第三無線通信方式を用いた通信路（長二点鎖線）によって、通信範囲内に位置する他のノードと通信を行う。また、ノードＮ４とノードＮ５とは、第四無線通信方式を用いた通信路（長一点鎖線）による無線通信も行う。
【００７４】
ノードＮ１の通信範囲内には、ノードＮ２が位置する。ノードＮ２の通信範囲内には、ノードＮ１及びノードＮ３が位置する。ノードＮ３の通信範囲内には、ノードＮ２及びノードＮ４が位置する。ノードＮ４の通信範囲内には、ノードＮ３及びノードＮ５が位置する。ノードＮ５の通信範囲内には、ノードＮ４及びノードＮ６が位置する。ノードＮ６の通信範囲内には、ノードＮ５が位置する。
【００７５】
図１９において実線、破線、長二点鎖線、長一点鎖線によって接続されているノード同士が通信を行うことができる。また、図１９において、各通信路の通信路コストは図中に「コスト：」として示される値である。また、図１９の場合、二つの通信経路条件が受付部２１を介して入力される。第一の通信経路条件は、ソースノードがノードＮ１であり、ディスティネーションノードがノードＮ３である。第二の通信経路条件は、ソースノードがノードＮ３であり、ディスティネーションノードがＮ６である。
【００７６】
通信環境記憶部２５は、図１９に示される通信環境を記憶している。受付部２１は、ソースノードの値として“Ｎ１”、ディスティネーションノードの値として“Ｎ３”の入力を受け付ける（図７のステップＳ０１）。さらに、受付部２１は、ソースノードの値として“Ｎ３”、ディスティネーションノードの値として“Ｎ６”の入力を受け付ける。受付部２１は、ソースノードの値を通信路選択部２３に渡す。また、受付部２１は、ディスティネーションノードの値を終了判断部２２に渡す。
【００７７】
通信路選択部２３は、まずソースノードがノードＮ１である通信経路条件について処理を行う。なお、複数の通信経路条件が入力された場合にどのように動作するかについては、変形例に記載する。通信路選択部２３は、ソースノードの値（“Ｎ１”）を受付部２１から受け取ると、このソースノードを仮通信経路として記憶する。また、通信路選択部２３は、総通信路コストを“０”とする（図７のステップＳ０２）。
【００７８】
次に、干渉通信路判断部２４は、仮通信経路毎に干渉通信路を判断する（図７のステップＳ０３）。干渉通信路判断部２４は、仮通信経路に含まれる各通信路及び通信経路記憶部２６に記憶されている各通信経路に含まれる各通信路について、ＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳの動作を応用した判断基準に基づき、干渉通信路を判断する。干渉通信路判断部２４は、これらの全ての通信路について判断を行い、この判断によって得られた全ての通信路を、この仮通信経路の干渉通信路として判断する。なお、図１９の説明においては、この時点では通信経路記憶部２６は通信経路を記憶していない。そのため、干渉通信路判断部２４は、仮通信経路［ソースノード］について、干渉通信路は無いと判断する。
【００７９】
次に、通信路選択部２３は、各仮通信経路について、干渉通信路判断部２４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部２３は、〔［ソースノード］，Ｐ１（１−２）〕、〔［ソースノード］，Ｐ２（１−２）〕、〔［ソースノード］，Ｐ３（１−２）〕を選択する。そして、通信路選択部２３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、それぞれ“１”、“３”、“２”となる。そのため、通信路選択部２３は、この中で最も小さい“１”に係る経路候補、〔［ソースノード］，Ｐ１（１−２）〕を選択する（図７のステップＳ０６）。そして、通信路選択部２３は、この経路候補に基づき、新たな仮通信経路［Ｐ１（１−２）］を取得する（図７のステップＳ０７：図２０参照）。
【００８０】
次に、終了判断部２２は、新たな仮通信経路の到達ノードＮ２がディスティネーションノードであるか否か判断する。この場合、ノードＮ２はディスティネーションノードではないため、終了判断部２２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。
【００８１】
次に、干渉通信路判断部２４は、新たに選択された仮通信経路［Ｐ１（１−２）］について、干渉通信路を判断する（図７のステップＳ０３）。この場合、仮通信経路［Ｐ１（１−２）］における干渉通信路としてＰ１（２−３）を判断する。
【００８２】
次に、通信路選択部２３は、各仮通信経路について、干渉通信路判断部２４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部２３は、〔［ソースノード］，Ｐ２（１−２）〕、〔［ソースノード］，Ｐ３（１−２）〕、〔［Ｐ１（１−２）］，Ｐ２（２−３）〕、〔［Ｐ１（１−２）］，Ｐ３（２−３）〕を選択する。そして、通信路選択部２３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、それぞれ“３”、“２”、“４”、“６”となる。そのため、通信路選択部２３は、この中で最も小さい“２”に係る経路候補、〔［ソースノード］，Ｐ３（１−２）〕を選択する（図７のステップＳ０６）。そして、通信路選択部２３は、この経路候補に基づき、新たな仮通信経路［Ｐ３（１−２）］を取得する（図７のステップＳ０７：図２１参照）。
【００８３】
次に、終了判断部２２は、新たな仮通信経路の到達ノードＮ２がディスティネーションノードであるか否か判断する。この場合、ノードＮ２はディスティネーションノードではないため、終了判断部２２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。
【００８４】
次に、干渉通信路判断部２４は、新たに選択された仮通信経路［Ｐ３（１−２）］について、干渉通信路を判断する（図７のステップＳ０３）。この場合、仮通信経路［Ｐ３（１−２）］における干渉通信路としてＰ３（２−３）を判断する。
【００８５】
次に、通信路選択部２３は、各仮通信経路について、干渉通信路判断部２４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部２３は、〔［ソースノード］，Ｐ２（１−２）〕、〔［Ｐ１（１−２）］，Ｐ２（２−３）〕、〔［Ｐ１（１−２）］，Ｐ３（２−３）〕、〔［Ｐ３（１−２）］，Ｐ１（２−３）〕、〔［Ｐ３（１−２）］，Ｐ２（２−３）〕を選択する。そして、通信路選択部２３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、それぞれ“３”、“４”、“６”、“３”、“５”となる。そのため、通信路選択部２３は、この中で最も小さい“３”に係る経路候補、〔［ソースノード］，Ｐ２（１−２）〕及び〔［Ｐ３（１−２）］，Ｐ１（２−３）〕を選択する（図７のステップＳ０６）。そして、通信路選択部２３は、この経路候補に基づき、新たな仮通信経路［Ｐ２（１−２）］及び［Ｐ３（１−２），Ｐ１（２−３）］を取得する（図７のステップＳ０７：図２２及び図２３参照）。
【００８６】
次に、終了判断部２２は、新たな仮通信経路の到達ノードＮ２及びＮ３がディスティネーションノードであるか否か判断する。この場合、ノードＮ３はディスティネーションノードである。そのため、終了判断部２２は、通信経路の選択処理は終了すると判断する（図７のステップＳ０８−ＹＥＳ）。終了判断部２２は、通信経路の選択処理が終了することを通信路選択部２３へ通知する。そして、終了判断部２２は、［Ｐ３（１−２），Ｐ１（２−３）］を最終的な通信経路として判断する。通信路選択部２３は、終了判断部２２から、通信経路の選択処理が終了することの通知を受けると、この通信経路条件（第一の通信経路条件）についての処理を終了し、最終的な通信経路［Ｐ３（１−２），Ｐ１（２−３）］を通信経路記憶部２６に書き込む。そして、通信路選択部２３は、第二の通信経路条件についての処理を開始する。
【００８７】
通信路選択部２３は、第二の通信経路条件に基づき、ソースノードの値（“Ｎ３”）を仮通信経路として記憶する。また、通信路選択部２３は、総通信路コストを“０”とする（図７のステップＳ０２）。
【００８８】
次に、干渉通信路判断部２４は、仮通信経路毎に干渉通信路を判断する（図７のステップＳ０３）。干渉通信路判断部２４は、仮通信経路［ソースノード］には通信路が含まれていないため、干渉通信路はないと判断する。また、干渉通信路判断部２４は、通信経路記憶部２６から、既に選択された通信経路を読み出し、この通信経路について干渉通信路を判断する。この場合、干渉通信路判断部２４は、通信経路記憶部２６から［Ｐ３（１−２），Ｐ１（２−３）］という通信経路を読み出す。そして、干渉通信路として、Ｐ１（３−４）及びＰ３（３−４）を判断する（図２４参照）。
【００８９】
次に、通信路選択部２３は、各仮通信経路について、干渉通信路判断部２４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部２３は、〔［ソースノード］，Ｐ２（３−４）〕を選択する。そして、通信路選択部２３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、“２”となる。そのため、通信路選択部２３は、この中で最も小さい“２”に係る経路候補、〔［ソースノード］，Ｐ２（３−４）〕を選択する（図７のステップＳ０６）。そして、通信路選択部２３は、この経路候補に基づき、新たな仮通信経路［Ｐ２（３−４）］を取得する（図７のステップＳ０７：図２５参照）。
【００９０】
次に、終了判断部２２は、新たな仮通信経路の到達ノードＮ４がディスティネーションノードであるか否か判断する。この場合、ノードＮ４はディスティネーションノードではないため、終了判断部２２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。
【００９１】
次に、干渉通信路判断部２４は、新たに選択された仮通信経路［Ｐ２（３−４）］について、この仮通信経路及び通信経路記憶部２６に記憶されている通信経路に基づいて、干渉通信路を判断する（図７のステップＳ０３）。この場合、仮通信経路［Ｐ２（３−４）］における干渉通信路としてＰ１（４−５）及びＰ２（４−５）を判断する。
【００９２】
次に、通信路選択部２３は、各仮通信経路について、干渉通信路判断部２４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部２３は、〔［Ｐ２（３−４）］，Ｐ３（４−５）〕、〔［Ｐ２（３−４）］，Ｐ４（４−５）〕を選択する。そして、通信路選択部２３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、“７”、“９”となる。そのため、通信路選択部２３は、この中で最も小さい“７”に係る経路候補〔［Ｐ２（３−４）］，Ｐ３（４−５）〕を選択する（図７のステップＳ０６）。そして、通信路選択部２３は、この経路候補に基づき、新たな仮通信経路［Ｐ２（３−４），Ｐ３（４−５）］を取得する（図７のステップＳ０７：図２６参照）。
【００９３】
次に、終了判断部２２は、新たな仮通信経路の到達ノードＮ５がディスティネーションノードであるか否か判断する。この場合、ノードＮ５はディスティネーションノードではないため、終了判断部２２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。
【００９４】
次に、干渉通信路判断部２４は、新たに選択された仮通信経路［Ｐ２（３−４），Ｐ３（４−５）］について、この仮通信経路及び通信経路記憶部２６に記憶されている通信経路に基づいて、干渉通信路を判断する（図７のステップＳ０３）。この場合、仮通信経路［Ｐ２（３−４），Ｐ３（４−５）］における干渉通信路としてＰ２（５−６）及びＰ３（５−６）を判断する。
【００９５】
次に、通信路選択部２３は、各仮通信経路について、干渉通信路判断部２４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部２３は、〔［Ｐ２（３−４）］，Ｐ４（４−５）〕、〔［Ｐ２（３−４），Ｐ３（４−５）］，Ｐ１（５−６）〕を選択する。そして、通信路選択部２３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、“９”、“１０”となる。そのため、通信路選択部２３は、この中で最も小さい“９”に係る経路候補〔［Ｐ２（３−４）］，Ｐ４（４−５）〕を選択する（図７のステップＳ０６）。そして、通信路選択部２３は、この経路候補に基づき、新たな仮通信経路［Ｐ２（３−４），Ｐ４（４−５）］を取得する（図７のステップＳ０７：図２７参照）。
【００９６】
次に、終了判断部２２は、新たな仮通信経路の到達ノードＮ５がディスティネーションノードであるか否か判断する。この場合、ノードＮ５はディスティネーションノードではないため、終了判断部２２は、通信経路の選択処理はまだ終了しないと判断する（図７のステップＳ０８−ＮＯ）。
【００９７】
次に、干渉通信路判断部２４は、新たに選択された仮通信経路［Ｐ２（３−４），Ｐ４（４−５）］について、この仮通信経路及び通信経路記憶部２６に記憶されている通信経路に基づいて、干渉通信路を判断する（図７のステップＳ０３）。この場合、仮通信経路［Ｐ２（３−４），Ｐ４（４−５）］における干渉通信路としてＰ２（５−６）を判断する。
【００９８】
次に、通信路選択部２３は、各仮通信経路について、干渉通信路判断部２４の判断結果に基づき、全ての経路候補を選択する（図７のステップＳ０４）。この場合、通信路選択部２３は、〔［Ｐ２（３−４），Ｐ３（４−５）］，Ｐ１（５−６）〕、〔［Ｐ２（３−４），Ｐ４（４−５）］，Ｐ１（５−６）〕、〔［Ｐ２（３−４），Ｐ４（４−５）］，Ｐ３（５−６）〕を選択する。そして、通信路選択部２３は、全ての経路候補について、総通信路コストを算出する（図７のステップＳ０５）。この場合、各経路候補の総通信路コストは、“１０”、“１２”、“１５”となる。そのため、通信路選択部２３は、この中で最も小さい“１０”に係る経路候補〔［Ｐ２（３−４），Ｐ３（４−５）］，Ｐ１（５−６）〕を選択する（図７のステップＳ０６）。そして、通信路選択部２３は、この経路候補に基づき、新たな仮通信経路［Ｐ２（３−４），Ｐ３（４−５），Ｐ１（５−６）］を取得する（図７のステップＳ０７：図２８参照）。
【００９９】
次に、終了判断部２２は、新たな仮通信経路の到達ノードＮ６がディスティネーションノードであるか否か判断する。この場合、ノードＮ６はディスティネーションノードである。そのため、終了判断部２２は、通信経路の選択処理は終了すると判断する（図７のステップＳ０８−ＹＥＳ）。終了判断部２２は、通信経路の選択処理が終了することを通信路選択部２３へ通知する。そして、終了判断部２２は、［Ｐ２（３−４），Ｐ３（４−５），Ｐ１（５−６）］を最終的な通信経路として判断する（図２９参照）。通信路選択部２３は、終了判断部２２から、通信経路の選択処理が終了することの通知を受けると、この通信経路条件（第二の通信経路条件）についての処理を終了する。
【０１００】
通信経路選択装置２は、通信経路選択装置１と同様の作用及び効果を奏する。さらに、通信経路選択装置２は、仮通信経路の到達ノードから他のノードへの通信路を選択する際に、既に決定された他の通信経路による干渉が生じやすい通信路も、選択の候補から除外して選択を行う。具体的には、干渉通信路判断部２４が、通信路について仮通信経路及び既に決定された他の通信経路と干渉が生じやすいか否かを判断し、通信路選択部２３は干渉が生じやすいと判断されていない通信路を選択する。そのため、通信経路選択装置２は、他の通信経路からの無線通信の干渉が生じにくい通信経路を選択することを可能とする。
【０１０１】
<変形例>
通信経路選択装置２は、複数の通信経路条件が入力された場合、以下のように、それぞれの通信経路条件を同列に扱って処理を実行しても良い。
通信路選択部２３は、複数の通信経路条件それぞれのソースノードを、仮通信経路として取り扱う。そして、通信路選択部２３は、各ソースノードから伸びる経路候補を選択し、その中から最も総通信路コストの低いものを仮通信経路として選択する。そして、終了判断部２２は、選択された仮通信経路それぞれについて、各仮通信経路におけるソースノードに基づき、到達ノードがそのソースノードに対応するディスティネーションノードであるか否かを判断する。
【０１０２】
上述した処理について、図１９を例に説明する。通信路選択部２３は、まず仮通信経路として［ソースノードＮ１］、［ソースノードＮ３］を選択する。次に、通信路選択部２３は、経路候補として、〔［ソースノードＮ１］，Ｐ１（１−２）〕、〔［ソースノードＮ１］，Ｐ２（１−２）〕、〔［ソースノードＮ１］，Ｐ３（１−２）〕、〔［ソースノードＮ３］，Ｐ１（３−４）〕、〔［ソースノードＮ３］，Ｐ２（３−４）〕、〔［ソースノードＮ３］，Ｐ３（３−４）〕を選択する。それぞれの総通信路コストは、“１”、“３”、“２”、“１”、“２”、“３”である。従って、通信路選択部２３は、最も小さい“１”に係る経路候補を仮通信経路として選択する（図３０参照）。なお、図３０〜図３２において、（ａ）は第一の通信経路条件に基づく仮通信経路を示し、（ｂ）は第二の通信経路条件に基づく仮通信経路を示す。
【０１０３】
次の繰り返し処理においては、通信路選択部２３は、［Ｐ３（１−２）］及び［Ｐ２（３−４）］を、総通信路コストが“２”である仮通信経路として選択する（図３１参照）。そして、さらに次の繰り返し処理において、通信路選択部２３は、［Ｐ２（１−２）］、［Ｐ３（１−２），Ｐ１（２−３）］、［Ｐ３（３−４）］、［Ｐ２（３−４），Ｐ１（４−５）］を、総通信路コストが“３”である仮通信経路として選択する（図３２参照）。この時点で、終了判断部２２は、第一の通信経路条件に関しては、［Ｐ３（１−２），Ｐ１（２−３）］の到達ノードがディスティネーションノードであるため、選択処理が終了すると判断する。そして、通信路選択部２３は、［Ｐ３（１−２），Ｐ１（２−３）］を最終的な通信経路として、通信経路記憶部２６に書き込む。
【０１０４】
新たな通信経路が通信経路記憶部２６に書き込まれると、干渉通信路判断部２４は、書き込まれた通信経路に対し干渉を生じやすい通信路を判断する。この場合、干渉通信路判断部２４は、Ｐ１（３−４）、Ｐ３（３−４）、Ｐ１（４−５）の各通信路は、干渉通信路であると判断する。次に、通信路判断部２３は、現在までの処理で選択している仮通信経路のうち、この三つの通信路を含む全ての仮通信経路を削除する。その結果として［Ｐ２（３−４）］のみが残る。そして、通信路判断部２３は、この残った仮通信経路を用いて、さらに選択処理を進め、最終的に［Ｐ２（３−４），Ｐ３（４−５），Ｐ１（５−６）］を通信経路として選択する。
【０１０５】
このように構成されることにより、通信経路選択装置２は、複数の通信経路条件について並行して通信経路の選択処理を実行することが可能となる。また、通信経路選択装置２は、先に選択された通信経路によって生じる干渉通信路を除外して仮通信経路を選択するため、他の通信経路との干渉が生じにくい通信経路を選択することが可能となる。さらには、このように構成された通信経路選択装置２は、まだ選択処理が終了していない通信経路条件についても、既に選択された仮通信経路の中で、他の通信経路との干渉通信路と判断された通信路を含む仮通信経路のみについて削除を行い、残った仮通信経路を用いて処理を続行する。そのため、それまでに実行された選択処理の結果を有効に活用し、シーケンシャルにそれぞれの通信経路条件について処理を実行するよりも高速に全ての通信経路条件についての選択結果を得ることが可能となる。
【０１０６】
通信経路選択装置２は、終了判断部２２、通信路選択部２３、干渉通信路判断部２４をそれぞれ複数備えることによって、複数の通信経路条件に係る通信経路について、並列に選択処理を実行しても良い。この場合、通信経路選択装置２は、ある通信経路条件に係る通信経路の選択処理を実行している最中に、他の通信経路条件に係る最終的な通信経路が通信経路記憶部２６に書き込まれた場合、実行中の処理をリセットし、選択処理を最初から実行しなおしても良い。通信経路選択装置２がこのように動作することにより、複数の通信経路条件についての選択処理を並行して実行した場合に、並行して実行されている他の通信経路との干渉が生じにくい通信経路を選択することが可能となる。
【０１０７】
また、通信経路選択装置２は、複数の通信経路条件に係る通信経路について並列に選択処理を行なう場合、以下のように動作しても良い。ある通信経路条件に係る通信経路の選択処理を実行している最中に、他の通信経路条件に係る最終的な通信経路が通信経路記憶部２６に書き込まれた場合、実行中の処理について、以下の様に動作しても良い。
例えば、図１９において第一の通信経路条件（他の通信経路条件）に係る最終的な通信経路が通信経路記憶部２６に書き込まれた時点で、第二の通信経路条件に係る処理の途中経過が図３３に表される状態であるとする。干渉通信路判断部２４は、通信経路記憶部２６に新たな書き込みが発生した場合、この書き込まれた通信経路に含まれる通信路によって干渉が生じる干渉通信路を判断する。次に、通信路判断部２３は、実行中の第二の通信経路条件に係る処理に関して、干渉通信路判断部２４によって判断された干渉通信路を含む仮通信経路を全て削除する。図３４は、このような削除の例を示す図である。図３４において、Ｐ１（３−４）、Ｐ３（３−４）、Ｐ１（４−５）の各通信路は、干渉通信路であると判断される。そのため、通信路判断部２３は、仮通信経路のうち、この三つの通信路を含む全ての仮通信経路を削除する。その結果として［Ｐ２（３−４）］のみが残る。
【０１０８】
そして、通信経路選択装置２は、この残った仮通信経路を用いて、さらに選択処理を進め、最終的に［Ｐ２（３−４），Ｐ３（４−５），Ｐ１（５−６）］を通信経路として選択する（図３５参照）。
【０１０９】
このように構成されることにより、通信経路選択装置２は、複数の通信経路条件について並列に通信経路の選択処理を実行し、それぞれの通信経路を高速に選択することが可能となる。また、通信経路選択装置２は、先に選択された通信経路によって生じる干渉通信路を除外して仮通信経路を選択するため、他の通信経路との干渉が生じにくい通信経路を選択することが可能となる。さらには、このように構成された通信経路選択装置２は、並列に実行中の選択処理について、上述したようにそれまでの計算結果（それまでせんたくされた仮通信経路など）をリセットしない。通信経路選択装置２は、既に選択された仮通信経路の中で、他の通信経路との干渉通信路と判断された通信路を含む仮通信経路のみについて削除を行い、残った仮通信経路を用いて処理を続行する。そのため、計算結果をリセットする場合に比べて、最終的に同じ通信経路を取得できる上に、処理を高速に実行させることが可能となる。
【０１１０】
通信路選択部２３は、経路候補が無い場合には、仮通信経路の到達ノードがディスティネーションノードに達していないとしても、処理を終了しても良い。また、このような場合、通信路選択部２３は、干渉通路判断部２４の判断結果に関わらず、干渉通信路を新通信路として選択することによって処理を継続しても良い。例えば、通信路選択部２３は、同一の通信経路条件において選択されている仮通信経路による干渉通信路を、新通信路として選択しても良い。また、通信路選択部２３は、通信経路記憶部２６に記憶されている他の通信経路による干渉通信路を、新通信路として選択しても良い。また、通信路選択部２３は、経路候補が無い場合に、まずは通信経路記憶部２６に記憶されている他の通信経路による干渉通信路を、新通信路として選択し、それでも経路候補が無い場合には、同一の通信経路条件において選択されている仮通信経路による干渉通信路を、新通信路として選択するように構成されても良い。
【０１１１】
また、経路候補が無い場合には、干渉通信路判断部２４は、干渉通信路と判断する際の判断基準を緩和することにより、干渉通信路と判断される通信路を少なくするように動作しても良い。例えば、干渉通信路は、ＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳ（Request to Send／Clear to Send）の動作を応用した判断基準を用いている場合には、ＣＳＭＡ／ＣＡの動作を応用した判断基準を用いるようにすることによって、判断基準を緩和することができる。
【０１１２】
また、干渉通信路判断部１４が干渉通信路を判断する判断基準としては、上述した判断基準以外の方法が採用されても良い。
また、通信路選択部２３は、上述したように複数の通信経路条件に係る選択処理を並行して実行する場合に、所定の時間（例えば１秒、数秒、１分など）に受付部１１が受け付けた通信経路条件について、同時に処理を開始しても良い。
【０１１３】
受付部１１は、複数の通信経路条件を同時に受け付けても良い。受付部１１が複数の通信経路条件を同時に受け付けた場合、通信路選択部２３は、上述したようにこれらの複数の通信路条件について同時に選択処理を開始しても良い。また、受付部１１は、所定の条件（ソースノードの識別情報の値が小さい順、優先順位の高い順など）に従って、順に選択処理を行っても良い。
【０１１４】
〔適用例〕
上述した通信経路選択装置１及び通信経路選択装置２は、ネットワークの中継装置（ノード）に搭載されても良い。その場合、通信経路選択装置１及び通信経路選択装置２は、公知の方法を用いることによって、通信環境に係る情報を取得しても良い。以下、通信環境に係る情報を取得する方法について説明する。
各ノードは、近接する他のノードを発見しその状態を知るため、ビーコンを送信する。ノードは、このビーコンを受信することによって、近接する他のノードの存在を学習する。また、ビーコンによって、各ノードは、リンクが双方向であることを学習する。
【０１１５】
ノードは、自装置が備える全ての無線通信インタフェースを用いてビーコンを送信する。このとき、ノードは、自装置のノード識別情報と、ビーコンの送信に用いる無線通信インタフェースのインタフェース識別情報と、をビーコンに含める。また、ノードは、他のノードからビーコンを既に受信している場合は、このビーコンに含められていたノード識別情報（受信ノード識別情報）及びインタフェース識別情報（受信インタフェース識別情報）をさらにビーコンに含めて送信する。
【０１１６】
ビーコンを受信したノードは、受信されたビーコンに、自装置のノード識別情報が受信ノード識別情報として含まれている場合は、このビーコンを送信したノードと、このビーコンに含まれている受信インタフェース識別情報に対応する無線通信インタフェースを用いて双方向に通信が可能であると判断する。
【０１１７】
ノードは、ビーコンによって把握した、双方向に通信可能なノードのインタフェースの情報及び使用帯域などの通信路コスト情報を、トポロジ情報パケットとして、任意の集中管理ノードに対しブロードキャストする。この集中管理ノードは、各ノードからこのトポロジ情報パケットを受信する。そして、この集中管理ノードは、受信された各トポロジ情報パケットに含まれる情報に基づいて、通信環境に係る情報を作成し、通信環境記憶部１５に記憶する（集中管理方式）。この集中管理ノードの選択方法としては、予め設定されたノードが選択されても良いし、最も新しいノード（例えば新しいノードほどノード識別情報が大きな値となるように設計することにより、判断することができる）が選択されても良いし、他の公知の方法によって選択されても良い。
【０１１８】
ノードは、ビーコンによって把握した、双方向に通信可能なノードのインタフェースの情報及び使用帯域などの通信路コスト情報を、トポロジ情報パケットとして、ネットワーク全体にフラッディングすることによって、ノード同士で通信環境に係る情報を共有しても良い（分散管理方式）。この場合、各ノードは、他のノードからこのトポロジ情報パケットを受信する。そして、各ノードは、受信された各トポロジ情報パケットに含まれる情報に基づいて、通信環境に係る情報を作成し、通信環境記憶部１５に記憶する。
【０１１９】
なお、上述した実施形態における通信経路選択装置１又は通信経路選択装置２の一部、例えば、終了判断部１２、終了判断部２２、通信路選択部１３、通信路選択部２３、干渉通信路判断部１４、干渉通信路判断部２４の機能をコンピュータで実現するようにしても良い。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現しても良い。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時刻の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時刻プログラムを保持しているものも含んでも良い。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【０１２０】
【図１】通信経路選択装置の第一実施形態の機能ブロックの概略を示す図である。
【図２】通信環境の一例を示す図である。
【図３】干渉の発生を抑止するように選択された通信経路の一例を示す図である。
【図４】通信環境の一例を示す図である。
【図５】ＣＳＭＡ／ＣＡの動作を応用した干渉通信路の判断基準を示す図である。
【図６】ＣＳＭＡ／ＣＡ及びＲＴＳ／ＣＴＳの動作を応用した干渉通信路の判断基準を示す図である。
【図７】通信経路選択装置の動作例を示すフローチャートである。
【図８】通信環境の一例を示す図である。
【図９】通信経路選択処理の流れを示す図である。
【図１０】通信経路選択処理の流れを示す図である。
【図１１】通信経路選択処理の流れを示す図である。
【図１２】通信経路選択処理の流れを示す図である。
【図１３】通信経路選択処理の流れを示す図である。
【図１４】通信経路選択処理の流れを示す図である。
【図１５】通信経路選択処理の流れを示す図である。
【図１６】通信経路選択処理の流れを示す図である。
【図１７】通信経路選択処理の流れを示す図である。
【図１８】通信経路選択装置の第一実施形態の機能ブロックの概略を示す図である。
【図１９】通信環境の一例を示す図である。
【図２０】通信経路選択処理の流れを示す図である。
【図２１】通信経路選択処理の流れを示す図である。
【図２２】通信経路選択処理の流れを示す図である。
【図２３】第一の通信経路条件に基づいた選択結果を示す図である。
【図２４】通信経路選択処理の流れを示す図である。
【図２５】通信経路選択処理の流れを示す図である。
【図２６】通信経路選択処理の流れを示す図である。
【図２７】通信経路選択処理の流れを示す図である。
【図２８】通信経路選択処理の流れを示す図である。
【図２９】第一の通信経路条件及び第二の通信経路条件に基づいた選択結果を示す図である。
【図３０】変形例における通信経路選択処理の流れを示す図である。
【図３１】変形例における通信経路選択処理の流れを示す図である。
【図３２】変形例における通信経路選択処理の流れを示す図である。
【図３３】変形例における通信経路選択処理の流れを示す図である。
【図３４】変形例における通信経路選択処理の流れを示す図である。
【図３５】変形例における通信経路選択処理の流れを示す図である。
【図３６】従来技術における問題点を示す図である。
【符号の説明】
【０１２１】
１，２…通信経路選択装置，  １１，２１…受付部，  １２，２２…終了判断部，  １３，２３…通信路選択部，  １４，２４…干渉通信路判断部，  １５，２５…通信環境記憶部，  ２６…通信経路記憶部
【図１】
2009212848.tif 000003
【図２】
2009212848.tif 000004
【図３】
2009212848.tif 000005
【図４】
2009212848.tif 000006
【図５】
2009212848.tif 000007
【図６】
2009212848.tif 000008
【図７】
2009212848.tif 000009
【図８】
2009212848.tif 000010
【図９】
2009212848.tif 000011
【図１０】
2009212848.tif 000012
【図１１】
2009212848.tif 000013
【図１２】
2009212848.tif 000014
【図１３】
2009212848.tif 000015
【図１４】
2009212848.tif 000016
【図１５】
2009212848.tif 000017
【図１６】
2009212848.tif 000018
【図１７】
2009212848.tif 000019
【図１８】
2009212848.tif 000020
【図１９】
2009212848.tif 000021
【図２０】
2009212848.tif 000022
【図２１】
2009212848.tif 000023
【図２２】
2009212848.tif 000024
【図２３】
2009212848.tif 000025
【図２４】
2009212848.tif 000026
【図２５】
2009212848.tif 000027
【図２６】
2009212848.tif 000028
【図２７】
2009212848.tif 000029
【図２８】
2009212848.tif 000030
【図２９】
2009212848.tif 000031
【図３０】
2009212848.tif 000032
【図３１】
2009212848.tif 000033
【図３２】
2009212848.tif 000034
【図３３】
2009212848.tif 000035
【図３４】
2009212848.tif 000036
【図３５】
2009212848.tif 000037
【図３６】
2009212848.tif 000038