(57)【要約】【課題】  ＶＣアルゴリズムとＰＳＧアルゴリズムを併用する場合に適切な無線リソースの割当方法を提供する。【解決手段】  本発明の一態様に係る割当方法は、ＩＴＳ無線の路側機に無線リソースを割り当てる方法であって、ＶＣマップのセルに新設の路側機の位置情報のみが含まれる場合に、前記セルに割り当てられた無線リソースを当該新設の路側機に適用するＶＣ割当を行う第１ステップと、ＶＣマップのセルに新設の路側機の位置情報と他の路側機の位置情報が含まれる場合に、当該新設の路側機について、ＰＳＧアルゴリズムにより無線リソースを割り当てるＰＳＧ割当を行う第２ステップと、を含む。【選択図】      図１
2019198011.tif 000002
【特許請求の範囲】
【請求項１】
ＩＴＳ無線の路側機に無線リソースを割り当てる方法であって、
ＶＣマップのセルに新設の路側機の位置情報のみが含まれる場合に、前記セルに割り当てられた無線リソースを当該新設の路側機に適用するＶＣ割当を行う第１ステップと、
ＶＣマップのセルに新設の路側機の位置情報と他の路側機の位置情報が含まれる場合に、当該新設の路側機について、ＰＳＧアルゴリズムにより無線リソースを割り当てるＰＳＧ割当を行う第２ステップと、を含む無線リソース割当方法。
【請求項２】
前記第２ステップにおいて前記ＰＳＧ割当が行われた場合に、下記に定義するＰＳＧエリアを設定する第３ステップを、更に含む請求項１に記載の無線リソース割当方法。
ＰＳＧエリア：ＰＳＧ割当が行われた路側機を含むセルを中心として、所定の非干渉距離だけ縦横に離れた矩形領域に含まれる複数のセルよりなるエリア
【請求項３】
新設の路側機の位置情報が前記ＰＳＧエリアの内部である場合に、当該新設の路側機について前記ＰＳＧ割当を行う第４ステップを、更に含む請求項２に記載の無線リソース割当方法。
【請求項４】
新設の路側機の位置情報が前記ＰＳＧエリアの外部である場合に、当該新設の路側機について前記ＶＣ割当を行う第５ステップを、更に含む請求項３に記載の無線リソース割当方法。
【請求項５】
前記第４ステップにおいて前記ＰＳＧ割当が行われた場合に、当該ＰＳＧ割当が行われた路側機について更に前記ＰＳＧエリアを設定する第６ステップを、更に含む請求項３又は請求項４に記載の無線リソース割当方法。
【請求項６】
前記ＶＣマップのセルが、必要なリソース数が１６未満の所定数以下となるサイズに設定されている請求項１から請求項５のいずれか１項に記載の無線リソース割当方法。
【請求項７】
ＩＴＳ無線の路側機に無線リソースを割り当てる装置であって、
ＶＣアルゴリズムに基づいて作成されたＶＣマップを記憶する記憶部と、
新設の路側機の位置情報が前記ＶＣマップのセル内で唯一か否かにより、下記に定義するＶＣ割当及びＰＳＧ割当のいずれを当該新設の路側機に適用するかを決定する情報処理部と、を備える無線リソース割当装置。
ＶＣ割当：ＶＣマップのセルの無線リソースを新設の路側機に適用する処理
ＰＳＧ割当：ＰＳＧアルゴリズムにより新設の路側機に無線リソースを割り当てる処理
【請求項８】
ＩＴＳ無線の路側機に無線リソースを割り当てる装置として、コンピュータを機能させるためのコンピュータプログラムであって、
前記コンピュータに、
ＶＣマップのセルに新設の路側機の位置情報のみが含まれる場合に、前記セルに割り当てられた無線リソースを当該新設の路側機に適用するＶＣ割当を行う第１ステップと、
ＶＣマップのセルに新設の路側機の位置情報と他の路側機の位置情報が含まれる場合に、当該新設の路側機について、ＰＳＧアルゴリズムに基づいて無線リソースを割り当てるＰＳＧ割当を行う第２ステップと、を実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線リソース割当方法及び装置、並びにコンピュータプログラムに関する。
【背景技術】
【０００２】
車載機などの移動局との無線通信を行うために、多数の路側機が交差点近傍などに設置される。複数の路側機が同じ無線リソースを使用すると、電波の相互干渉が生じる。
このため、干渉ができるだけ生じないように、複数の路側機に無線リソースを割り当てることが望まれている。
【０００３】
非特許文献１及び２は、ＩＴＳ（Intelligent Transport Systems）無線の路側機に適した、無線リソースの割当手法のアルゴリズムが記載されている。
特許文献１には、県境などの境界に隣接する第１エリアに設置する第１路側機に、第１無線リソースの少なくとも一部を割り当て、境界から離れた第２エリアに設置する第２路側機に、第１無線リソースとは異なる第２無線リソースを割り当てる、無線リソースの割当方法が記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１７−３８２１４号公報
【非特許文献】
【０００５】
【非特許文献１】山口弘純  他、「密に設置されるＩＴＳ路側機群の運用シナリオに適した無線相互干渉調停アルゴリズム」、情報処理学会研究報告．ＩＴＳ，２０１４−ＩＴＳ−５９（２８），１−８，２０１４−１１−１３
【非特許文献２】山口弘純  他、「密な基地局群の無線相互干渉調停のための空間分割スケジューリング技術」、情報処理学会論文誌，Ｖｏｌ．５５，Ｎｏ．２，ｐｐ．８２６−８３７，２０１４
【発明の概要】
【発明が解決しようとする課題】
【０００６】
先行技術文献では、ＶＣアルゴリズムとＰＳＧアルゴリズムなどの複数種類のアルゴリズムを併用して、既設の路側機の無線リソースを変更せずに新設の路側機に無線リソースを順次割り当てる場合の適切な手法については想定されていない。
本発明は、かかる従来の問題点に鑑み、ＶＣアルゴリズムとＰＳＧアルゴリズムを併用する場合に適切な無線リソースの割当方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
（１）  本発明の一態様に係る割当方法は、ＩＴＳ無線の路側機に無線リソースを割り当てる方法であって、ＶＣマップのセルに新設の路側機の位置情報のみが含まれる場合に、前記セルに割り当てられた無線リソースを当該新設の路側機に適用するＶＣ割当を行う第１ステップと、ＶＣマップのセルに新設の路側機の位置情報と他の路側機の位置情報が含まれる場合に、当該新設の路側機について、ＰＳＧアルゴリズムにより無線リソースを割り当てるＰＳＧ割当を行う第２ステップと、を含む。
【０００８】
（７）  本発明の一態様に係る割当装置は、ＩＴＳ無線の路側機に無線リソースを割り当てる装置であって、ＶＣアルゴリズムに基づいて作成されたＶＣマップを記憶する記憶部と、新設の路側機の位置情報が前記ＶＣマップのセル内で唯一か否かにより、下記に定義するＶＣ割当及びＰＳＧ割当のいずれを当該新設の路側機に適用するかを決定する情報処理部と、を備える。
ＶＣ割当：ＶＣマップのセルの無線リソースを新設の路側機に適用する処理
ＰＳＧ割当：ＰＳＧアルゴリズムにより新設の路側機に無線リソースを割り当てる処理
【０００９】
（８）  本発明の一態様に係るコンピュータプログラムは、ＩＴＳ無線の路側機に無線リソースを割り当てる装置として、コンピュータを機能させるためのコンピュータプログラムであって、前記コンピュータに、ＶＣマップのセルに新設の路側機の位置情報のみが含まれる場合に、前記セルに割り当てられた無線リソースを当該新設の路側機に適用するＶＣ割当を行う第１ステップと、ＶＣマップのセルに新設の路側機の位置情報と他の路側機の位置情報が含まれる場合に、当該新設の路側機について、ＰＳＧアルゴリズムに基づいて無線リソースを割り当てるＰＳＧ割当を行う第２ステップと、を実行させる。
【発明の効果】
【００１０】
本発明によれば、ＶＣアルゴリズムとＰＳＧアルゴリズムを併用する場合に、無線リソースを適切に割り当てることができる。
【図面の簡単な説明】
【００１１】
【図１】無線リソース割当装置の構成例を示すブロック図である。
【図２】無線リソースの使用条件と路側機の設置条件の説明図である。
【図３】ＶＣマップ生成部の処理内容の一例を示す説明図である。
【図４】ＳＧアルゴリズムに基づく割当処理の一例を示す説明図である。
【図５】リソース割当部が実行する無線リソースの割当処理の一例を示すフローチャートである。
【図６】路側機の新設ごとのリソース割当の一例を示す説明図である。
【図７】路側機の新設ごとのリソース割当の一例を示す説明図である。
【図８】路側機の新設ごとのリソース割当の一例を示す説明図である。
【図９】路側機の新設ごとのリソース割当の一例を示す説明図である。
【図１０】路側機の新設ごとのリソース割当の別例を示す説明図である。
【図１１】路側機の新設ごとのリソース割当の別例を示す説明図である。
【発明を実施するための形態】
【００１２】
＜本発明の実施形態の概要＞  
以下、本発明の実施形態の概要を列記して説明する。
（１）  本実施形態の割当方法は、ＩＴＳ無線の路側機に無線リソースを割り当てる方法であって、ＶＣマップのセルに新設の路側機の位置情報のみが含まれる場合に、前記セルに割り当てられた無線リソースを当該新設の路側機に適用するＶＣ割当を行う第１ステップと、ＶＣマップのセルに新設の路側機の位置情報と他の路側機の位置情報が含まれる場合に、当該新設の路側機について、ＰＳＧアルゴリズムにより無線リソースを割り当てるＰＳＧ割当を行う第２ステップと、を含む。
【００１３】
本実施形態の割当方法によれば、ＶＣマップのセルに新設の路側機の位置情報のみが含まれる場合にＶＣ割当を行い（第１ステップ）、ＶＣマップのセルに新設の路側機の位置情報と他の路側機の位置情報が含まれる場合にＰＳＧ割当を行うので（第２ステップ）、新設の路側機に対するＶＣアルゴリズムとＰＳＧアルゴリズムを併用した無線リソースの割り当てを適切に行うことができる。
【００１４】
（２）  本実施形態の割当方法において、前記第２ステップにおいて前記ＰＳＧ割当が行われた場合に、下記に定義するＰＳＧエリアを設定する第３ステップを、更に含むことが好ましい。
ＰＳＧエリア：ＰＳＧ割当が行われた路側機を含むセルを中心として、所定の非干渉距離だけ縦横に離れた矩形領域に含まれる複数のセルよりなるエリア
【００１５】
このようにすれば、新設の路側機の位置情報が第３ステップで設定されたＰＳＧエリアの内部か外部かにより、以後の新設の路側機に適用する割当処理の種別を判定できるようになる。
【００１６】
（３）  具体的には、本実施形態の割当方法において、新設の路側機の位置情報が前記ＰＳＧエリアの内部である場合には、当該新設の路側機について前記ＰＳＧ割当を行う第４ステップを、更に実行すればよい。
その理由は、新設の路側機の位置情報がＰＳＧエリアの内部である場合は、ＰＳＧ割当が行われた既設の路側機との干渉関係を考慮する必要があるので、ＰＳＧアルゴリズムにより新設の路側機の無線リソースを割り当てるべきだからである。
【００１７】
（４）  また、本実施形態の割当方法において、新設の路側機の位置情報が前記ＰＳＧエリアの外部である場合には、当該新設の路側機について前記ＶＣ割当を行う第５ステップを、更に実行すればよい。
その理由は、新設の路側機の位置情報がＰＳＧエリアの外部である場合は、ＰＳＧ割当が行われた既設の路側機と非干渉関係にあるので、ＶＣエリアのセルに割り当てられた無線リソースをそのまま採用しても差し支えないからである。
【００１８】
（５）  本実施形態の割当方法において、前記第４ステップにおいて前記ＰＳＧ割当が行われた場合に、当該ＰＳＧ割当が行われた路側機について更に前記ＰＳＧエリアを設定する第６ステップを、更に含むことが好ましい。
このようにすれば、新設の路側機の位置情報が第６ステップで設定されたＰＳＧエリアの内部か外部かにより、以後の新設の路側機に適用する割当処理の種別を判定できるようになる。
【００１９】
（６）  本実施形態の割当方法において、前記ＶＣマップのセルが、必要なリソース数が１６未満の所定数（例えば図２の例では１２）以下となるサイズに設定されていることが好ましい。
このようにすれば、例えば重要交差点に設置する路側機用の空きスロットを確保できるようになる。このため、一般交差点に対する路側機の設置が先行しても、重要交差点に新設する路側機に無線リソースを割り当て易くなる。
【００２０】
（７）  本実施形態の割当装置は、上述の（１）〜（６）の割当方法を実行する無線リソース割当装置である。
従って、本実施形態の割当装置は、上述の（１）〜（６）の割当方法と同様の作用効果を奏する。
【００２１】
（８）  本実施形態のコンピュータプログラムは、上述の（７）の割当装置として、コンピュータを機能させるためのコンピュータプログラムである。
従って、本実施形態のコンピュータプログラムは、上述の（７）の割当装置と同様の作用効果を奏する。
【００２２】
＜本発明の実施形態の詳細＞  
以下、図面を参照して、本発明の実施形態の詳細を説明する。なお、以下に記載する実施形態の少なくとも一部を任意に組み合わせてもよい。
【００２３】
〔無線リソース割当装置の構成〕
図１は、本実施形態に係る無線リソース割当装置１の構成例を示すブロック図である。
図１に示すように、無線リソース割当装置１は、記憶部１１と情報処理部１２とを備える、ＯＳ（オペレーティングシステム）及び各種のアプリーションプログラムがインストールされたコンピュータ装置よりなる。図示省略しているが、割当装置１には、液晶ディスプレイなどの表示装置と、マウス及びキーボードなどの入力装置も含まれる。
【００２４】
記憶部１１は、ＨＤＤ（Hard Disk Drive）及びＳＳＤ（Solid State Drive）のうちの少なくとも１つの不揮発性メモリ（記憶媒体）と、ランダムアクセスメモリ等よりなる揮発性メモリ（記憶媒体）とを含む記憶装置である。
情報処理部１２は、記憶部１１の不揮発性メモリに格納されたコンピュータプログラム１３を揮発性メモリに読み出し、当該プログラム１３に従って情報処理を行うＣＰＵ（Central Processing Unit）を含む演算処理装置よりなる。
【００２５】
記憶部１１には、コンピュータプログラム１３の他に、地図情報１４とエリア情報１５が格納されている。
地図情報１４は、日本全国を網羅するデジタル地図データよりなる。デジタル地図データには、道路地図データ１８が含まれる。道路地図デー１８には、「交差点データ」と「リンクデータ」が含まれる。
【００２６】
「交差点データ」は、国内の交差点に付与された交差点ＩＤと、交差点の位置情報とを対応付けたデータである。「リンクデータ」は、国内の道路に対応して付与された特定リンクのリンクＩＤに対して、次の情報１）〜４）を対応付けたデータよりなる。
情報１）特定リンクの始点・終点・補間点の位置情報
情報２）特定リンクの始点に接続するリンクＩＤ
情報３）特定リンクの終点に接続するリンクＩＤ
情報４）特定リンクのリンクコスト
【００２７】
道路地図データ１８は、実際の道路線形と道路の走行方向に対応したネットワークを構成する。このため、道路地図データ１８は、交差点を表すノード間の道路区間を有向リンクｌ（小文字のエル）で繋いだネットワークになっている。
具体的には、道路地図データ１８は、交差点ごとにノードｎが設定され、各ノードｎ間が逆向きの一対の有向リンクｌで繋がった有向グラフよりなる。従って、一方通行の道路の場合は、一方向の有向リンクｌのみノードｎが接続される。
【００２８】
エリア情報１５には、ＶＣマップ１９が含まれる。ＶＣマップ１９は、日本全国を網羅するデジタル地図データを所定サイズのセルＣで区切ったメッシュデータよりなる。メッシュの粒度は任意であるが、本実施形態では、例えば５次メッシュを採用する。従って、セルＣの一辺は２５０ｍである。
【００２９】
ＶＣマップの各セルＣには、セルＣの識別情報（メッシュコード）と、セルＣ内に位置する路側機が使用可能なスロット番号（無線リソース）が割り当てられている。
図１の例では、左上隅から右側に向かって順に、「３」、「４」、「５」、「１」、「２」……のスロット番号が割り当てられている。各セルＣに対する無線リソースの割り当ては、ＶＣマップ生成部１６がＶＣ（Vector-based Cell Cover）アルゴリズムに基づいて実行するが、これについては後述する。
【００３０】
エリア情報１５には、ＰＳＧ（Prioritized Station-based Greedy）エリア２０が含まれる。ＰＳＧエリア２０は、リソース割当部１７がＶＣマップ１９に重畳的に設定するエリアである。
リソース割当部１７は、新設路側機についてＰＳＧアルゴリズムに基づくリソース割当を実行した場合に、新設路側機を含むセルＣを中心として、そのセルＣから所定の非干渉距離だけ縦横に離れた矩形領域に含まれる複数のセルＣを、ＰＳＧエリアに設定する。
【００３１】
情報処理部１２には、ＶＣマップ生成部１６及びリソース割当部１７が含まれる。これらは、情報処理部１２が記憶部１１からコンピュータプログラム１３を読み出して実行することによって達成される機能部である。
【００３２】
ＶＣマップ生成部１６は、地図情報１４からＶＣマップ１９を生成して記憶部１１に記憶させる。ＶＣマップ生成部１６が実行する生成処理の詳細については、後述する。
リソース割当部１７は、ユーザが入力した新設路側機の位置情報と、記憶部１１が記憶するエリア情報１５とに基づいて、新設路側機に割り当てる無線リソース（タイムスロット）を決定する。リソース割当部１７が実行する割当処理の詳細についても、後述する。
【００３３】
〔無線リソースの使用条件及び路側機の設置条件〕
図２は、無線リソースの使用条件と路側機の設置条件の説明図である。
図２に示すように、割当対象となる無線リソースは、１つの制御周期において時分割で並ぶ複数のタイムスロットＳＬ１〜ＳＬ１６よりなる。タイムスロットＳＬ１〜ＳＬ１６は、ＩＴＳ用路側機（基地局）の送信可能時間である。
【００３４】
複数のタイムスロットＳＬ１〜Ｓ１６は、所定時間（１００ｍｓ）の１つの制御周期に含まれており、制御周期は繰り返し生じる。１つの制御周期において、タイムスロットＳＬ１〜Ｓ１６の間の期間は、車載機などの移動局の無線通信に用いられる。
かかるタイムスロットＳＬ１〜ＳＬ１６は、７００ＭＨｚ帯高度道路交通システム（ＡＲＩＢ  ＳＴＤ−Ｔ１０９）に規定されている。
【００３５】
図２の道路地図（交差点ＮＷ）において、「Ａ」〜「Ｉ」の意味は次の通りである。
Ａ：重要交差点に設置される路側機（中央装置と専用回線で接続）
Ｂ〜Ｅ：一般交差点に設置される中継用の路側機（中央装置と非接続）
Ｆ〜Ｉ：一般交差点に設置される末端の路側機（中央装置と非接続）
【００３６】
図２に示すように、タイムスロットＳＬ１〜ＳＬ１６の使用条件は次の通りである。
スロットＳＬ１，ＳＬ２    ：路側機Ａの路車間通信用とする。
スロットＳＬ３〜ＳＬ１２  ：ＶＣ／ＰＳＧ割当用とする。
スロットＳＬ１３，ＳＬ１４：重要交差点で干渉した時の路路間通信用として開ける。
スロットＳＬ１５，ＳＬ１６：路側機Ａ〜Ｉの路路間通信用とする。
【００３７】
また、新設路側機の設置条件は、次の条件１及び２である。
条件１：ＶＣセル内に設置する路側機は１台とする。
条件２：重要交差点に対する路側機の設置間隔は、所定の干渉距離（例えば１１８０ｍ）以上とする。
【００３８】
〔ＶＣマップ生成部の処理内容〕
図３は、ＶＣマップ生成部１６の処理内容の一例を示す説明図である。
前述の通り、ＶＣマップ生成部１６は、ＶＣアルゴリズムに基づいて、上記の設置条件に適合するセルサイズを決定し、各セルＣに無線リソースを割り当てたＶＣマップ１９を生成する。以下、図３を参照しつつ、ＶＣアルゴリズムに基づくＶＣマップ１９の生成方法の概要を説明する。
【００３９】
ＶＣアルゴリズムには、次の工程１〜４が含まれる。
工程１：設置エリアの区画
工程１は、路側機の設置エリアを所定サイズのセルＣに区画する処理である。
図３Ａに示すように、路側機の設置エリアが、所定サイズのセルＣに区切られる。図３Ａでは、路側機の設置エリアが、格子状の道路Ｒを含む所定範囲のエリアで示され、路側機が設置される交差点が黒丸で示されている。セルＣの大きさは、予めタイムスロットの使用条件として設定した、ＶＣ／ＰＳＧ割当用スロット数（本実施形態では１２）を超えない区画数で干渉範囲を区画できるサイズとすることが好ましい。
【００４０】
２）工程２：非干渉セルの探索
工程２は、セルＣごとに非干渉となる他のセルＣを探索する処理である。
ＶＣアルゴリズムでは、路側機の実際の設置位置ではなく、セル単位で干渉関係が考慮される。具体的には、各セルＣについて、当該セルＣと干渉関係にある「干渉セル」と、非干渉関係にある「非干渉セル」が探索される。図３Ａにおいて、セルＣ１に対して、セルＣ２が干渉セルであり、セルＣ３が非干渉セルである。
【００４１】
３）工程３：無線リソースの割り当て及びリソース数の演算
工程３は、干渉セルに異なる無線リソース（タイムスロット）を規則的に割り当て、非干渉セル同士に同じ無線リソース（タイムスロット）を割り当てて、設置エリアにおいて必要となるリソース数を求める処理である。
図３Ｂでは、干渉関係のセルＣ１とセルＣ２に異なるタイムスロットが割り当てられ、非干渉関係のセルＣ１とセルＣ３に同じ無線リソースが割り当てられている。
【００４２】
４）工程４：セルサイズの特定
工程４は、セルサイズを種々に変更して工程１〜３の処理を繰り返し、設置エリアにおいて必要となるリソース数がＶＣ／ＰＳＧ割当用スロット数を超えない、かつ、最小となるセルサイズを特定する処理である。
図３Ｂでは、設置エリアを縦７×横９に区分するセルサイズとなっており、リソース数はスロット番号１〜５の５つとなっている。
【００４３】
ＶＣマップ生成部１６は、図３に示す設置エリアを日本全国を網羅するデジタル地図データの範囲に広げ、当該範囲に含まれる各セルＣに無線リソースを割り当てる。従って、ＶＣマップ１９の範囲は、日本全国を網羅する広域な範囲に及ぶ。
【００４４】
〔ＳＧ及びＰＳＧアルゴリズムによる割当処理〕
図４は、ＳＧ（Station-based Greedy）アルゴリズムに基づく割当処理の一例を示す説明図である。図４において、Ｒ１〜Ｒ２６は、各交差点に位置する路側機である。
まず、図４Ａに示すように、最も設置密度が高い路側機Ｒ１５を、対象路側機として選択し、無線リソース（ここでは、仮にタイムスロットＳＬ１１とする。）を割り当てる。対象路側機Ｒ１５は、タイムスロットＳＬ１１を割り当てた最初の路側機とする。
【００４５】
次に、対象路側機Ｒ１５と同じ無線リソースを割り当てる路側機を探索する。
具体的には、対象路側機Ｒ１５と他の路側機Ｒ１〜Ｒ１４，Ｒ１６〜Ｒ２６との間の干渉関係を計算し、対象路側機Ｒ１５が、与干渉源とならない第１非干渉路側機（対象路側機Ｒ１５から干渉を受けない路側機）を抽出する（図４Ａ参照）。
例えば、対象路側機Ｒ１５から路側機Ｒ９の通信エリアＥ内へ与えられる電波干渉が計算され、電波干渉が弱ければ、路側機Ｒ９は第１非干渉路側機として抽出される。
【００４６】
次に、干渉関係の計算結果に基づいて、図４Ａの第１非干渉路側機のうちで、対象路側機Ｒ１５への与干渉源とならない第２非干渉路側機（対象路側機Ｒ１５へ干渉を与えない路側機）を抽出する（図４Ｂ参照）。
例えば、第１非干渉路側機のうち、路側機Ｒ４や路側機Ｒ９が、対象路側機Ｒ１５の通信エリアＥ内へ与える電波干渉が計算され、電波干渉が強ければ、路側機Ｒ４や路側機Ｒ９は第２非干渉路側機としては抽出されない。
【００４７】
図４Ｂでは、路側機Ｒ１，Ｒ５，Ｒ６，Ｒ８，Ｒ２１，Ｒ２２，Ｒ２６が第２非干渉路側機として抽出されている。
第２非路側干渉路側機には、対象路側機Ｒ１５と同じ無線リソースが割り当てることができる。このうち、対象路側機Ｒ１５からの距離が最も短い、或いは、路側機の密度が最も高い路側機に、対象路側機Ｒ１５と同じ無線リソース（タイムスロットＳＬ１１）を割り当てる。
【００４８】
ここでは、例えば、路側機Ｒ２２に、対象路側機Ｒ１５と同じ無線リソース（タイムスロットＳＬ１１）を割り当てる。
続いて、第２非干渉路側機のうち、路側機Ｒ２２の次に、対象路側機Ｒ１５からの距離が最も短い、或いは、路側機の密度が最も高い路側機が、路側機Ｒ８である場合には、路側機Ｒ８が、路側機Ｒ１５に加えて路側機Ｒ２２とも相互干渉の関係に無ければ、路側機Ｒ８にも対象路側機Ｒ１５と同じ無線リソースを割り当てる。
【００４９】
一方、相互干渉の関係にあれば、路側機Ｒ１５や路側機Ｒ２２とは異なる無線リソースの割り当てを試みる。このとき、当該異なる無線リソース（例えば、タイムスロットＳＬ１２）を割り当てられた路側機が他になければ、路側機Ｒ１５と同様の処理を行う。
当該異なる無線リソースを割り当てられた路側機が他にあれば、路側機Ｒ１５がタイムスロットＳＬ１１の場合に行った処理と同様の処理を行う。
【００５０】
これを、タイムスロットＳＬ１１における複数の第２非干渉路側機について繰り返すことにより、対象路側機Ｒ１５と同じ無線リソース（タイムスロットＳＬ１１）を割り当てることができる路側機Ｒ６，Ｒ８，Ｒ２２，Ｒ２６を決定する（図４Ｃ参照）。
以上の処理が終了すると、対象路側機Ｒ１５の近傍の路側機（例えば、路側機Ｒ１０）を、次の対象路側機として、図４Ａ〜図４Ｃの処理を繰り返す。これにより、所定の相互干渉エリアに設置される路側機にどの無線リソースを割り当てられるかを決定する。
【００５１】
ＰＳＧアルゴリズムの割当処理は、上記のＳＧアルゴリズムの割当処理を、既設の路側機の無線リソースを変更しないとの加重条件の下で行われる処理である。
【００５２】
〔リソース割当部の処理内容〕
図５は、リソース割当部１７が実行する無線リソースの割当処理の一例を示すフローチャートである。
図５に示すように、リソース割当部１７は、ユーザによる新設路側機の位置情報の操作入力を契機として（ステップＳＴ１１でＹｅｓ）に、入力された路側機の位置情報がＰＳＧエリア２０内か否かを判定する（ステップＳＴ１２）。
【００５３】
上記の位置情報の操作入力は、例えば、ディスプレイに表示された道路地図の交差点の上にマウスポインタを移動し、当該交差点の上でマウスをクリックすることにより行うことができる。
ステップＳＴ１２の判定は、ポインタで指定された路側機の位置情報（座標値）を含むセルＣが、エリア情報１５のＰＳＧエリア２０として指定されているか否かによって行われる。
【００５４】
ステップＳＴ１２の判定結果が否定的である場合（位置情報がＰＳＧエリア２０の範囲外の場合）には、リソース割当部１７は、位置情報がＶＣマップ１９のセルＣ内で唯一の位置情報か否かを判定する（ステップＳＴ１３）。
なお、ＰＳＧエリア２０は、後述のＰＳＧ割当が実施された場合に作成されるので（ステップＳＴ１５，ＳＴ１６）、過去に一度もＰＳＧ割当が実施されていない場合には、ＰＳＧエリア２０は存在せず、ステップＳＴ１２の判定結果は必ず否定的となる。
【００５５】
ステップＳＴ１３の判定結果が肯定的である場合は、リソース割当部１７は、入力された新設路側機について、「ＶＣ割当」を実施する（ステップＳＴ１５）。
「ＶＣ割当」とは、ＶＣマップ１９のセルＣに割り当てられた無線リソースをそのまま新設路側機に適用する処理のことである。従って、位置情報を含むセルＣのスロット番号が「３」である場合は、新設路側機にタイムスロットＳＬ３が適用される。
【００５６】
ステップＳＴ１２の判定結果が肯定的である場合、及び、ステップＳＴ１３の判定結果が否定的である場合は、リソース割当部１７は、「ＰＳＧ割当」を実施する（ステップＳＴ１５）。
「ＰＳＧ割当」とは、新設路側機について、セルＣのスロット番号をそのまま適用するのではなく、前述のＰＳＧアルゴリズムに基づいて無線リソースを割り当てる処理のことである。
【００５７】
ＰＳＧ割当（ステップＳＴ１５）を実施した場合、リソース割当部１７は、ＰＳＧエリア２０を作成し、作成したＰＳＧエリア２０を記憶部１１のエリア情報１５に追加することにより、エリア情報１５を更新する（ステップＳＴ１６）。
例えば、リソース割当部１７は、新設路側機を含むセルＣを中心として、そのセルＣから所定の非干渉距離（例えば、１１８０ｍ）だけ縦横に離れた矩形領域に含まれる複数のセルＣを、ＰＳＧエリア２０に指定する。
【００５８】
〔路側機の新設ごとのリソース割当〕
図６〜図９は、路側機の新設ごとのリソース割当の一例を示す説明図である。
図６〜図９の画面１〜６は、無線リソース割当装置１のディスプレイに表示されるデジタル地図データの表示画面である。図６の画面１に含まれる直線は、デジタル地図データの「道路」を示し、直線の交点は「交差点」を示す。なお、図示の煩雑さを避けるため、画面２以降については道路の表示を省略している。
【００５９】
画面１〜６において、Ｒｊ（ｊ＝１〜７）は、「一般交差点」に対する設置が指定された路側機である。Ｒｊの添え字ｊは、ユーザが設置を指定した順番を表す。
画面１〜６において、「ＶＣ」は、路側機について「ＶＣ割当」（図５のステップＳＴ１４）が実施されたことを示す。「ＰＳＧ」は、路側機について「ＰＳＧ割当」（図５のステップＳＴ１５）が実施されたことを示す。
【００６０】
画面１〜６において、白抜きの四角形ドットは、現時点で既設の路側機を示し、黒塗りの四角形ドットは、ユーザが新たに設置を指定した新設の路側機を示す。
画面２〜６において、ＶＣマップ１９のセルＣ及びＰＳＧエリア２０Ａ，２０Ｂが表示されているが、セルＣ及びＰＳＧエリア２０Ａ，２０Ｂについては、必ずしもディスプレイに表示される必要はない。
【００６１】
図６の画面１は、路側機Ｒ１→路側機Ｒ２→路側機Ｒ３の順で路側機の設置が既に指定され、路側機Ｒ４の新設が指定された場合の表示画面である。ここでは、路側機Ｒ１〜Ｒ４の位置情報は、ＶＣマップ１９のセルＣ内で唯一であるとする。
この場合、リソース割当部１７は、路側機Ｒ１〜Ｒ４に対してＶＣ割当を実行する（図５のステップＳＴ１２〜ＳＴ１４）。従って、路側機Ｒ１〜Ｒ４については、ＶＣマップ１９のセルＣに割り当てられたタイムスロットが適用される。
【００６２】
図７の画面２は、４つの交差点への路側機Ｒ１〜Ｒ４（いずれもＶＣ割当）の設置が既に指定され、路側機Ｒ５の新設が指定された場合の表示画面である。ここでは、指定された路側機Ｒ５の位置情報は、既設の路側機Ｒ４の位置情報を含むセルＣ内であるとする。
この場合、リソース割当部１７は、新設の路側機Ｒ５に対してＰＳＧ割当を実行する（図５のステップＳＴ１２，ＳＴ１３，ＳＴ１５）。従って、路側機Ｒ５については、ＰＳＧ割当により決定したタイムスロットが適用される。
【００６３】
図７の画面３に示す通り、新設の路側機Ｒ５に対するＰＳＧ割当が行われると、リソース割当部１７は、路側機Ｒ５を含むセルＣを中心としたＰＳＧエリア２０Ａを設定する（図５のステップＳＴ１６）。
以後、ユーザが指定する新設路側機の位置情報がＰＳＧエリア２０Ａの内部か外部かにより、新設路側機に適用するリソース割当の種別をＰＳＧ割当とするかＶＣ割当とするかが決定される（図７のステップＳＴ１２）。
【００６４】
図８の画面４は、路側機Ｒ５の設置に伴ってＰＳＧエリア２０Ａが設定された後、ＰＳＧエリア２０Ａの外側に、路側機Ｒ６の新設が指定された場合の表示画面である。ここでは、路側機Ｒ６の位置情報は、ＶＣマップ１９のセルＣ内で唯一であるとする。
この場合、リソース割当部１７は、路側機Ｒ６に対してＶＣ割当を実行する（図５のステップＳＴ１２〜ＳＴ１４）。従って、路側機Ｒ６については、ＶＣマップ１９のセルＣに割り当てられたタイムスロットが適用される。
【００６５】
図８の画面５は、路側機Ｒ５の設置に伴ってＰＳＧエリア２０Ａが設定された後、ＰＳＧエリア２０Ａの内側に、路側機Ｒ７の新設が指定された場合の表示画面である。
この場合、リソース割当部１７は、路側機Ｒ７に対してＰＳＧ割当を実行する（図５のステップＳＴ１２，ＳＴ１５）。従って、路側機Ｒ７については、ＰＳＧ割当により決定したタイムスロットが適用される。
【００６６】
図９の画面６に示す通り、新設の路側機Ｒ７に対するＰＳＧ割当が行われると、リソース割当部１７は、路側機Ｒ７を含むセルＣを中心としたＰＳＧエリア２０Ｂを更に設定する（図５のステップＳＴ１６）。
以後、ユーザが指定する新設路側機の位置情報がＰＳＧエリア２０Ａ，２０Ｂの内部か外部かにより、新設路側機に適用するリソース割当の種別をＰＳＧ割当とするかＶＣ割当とするかが決定される（図７のステップＳＴ１２）。
【００６７】
〔第１の変形例：重要交差点に路側機を追加する場合〕
図１０は、路側機の新設ごとのリソース割当の別例を示す説明図である。
図１０の画面７及び８も、無線リソース割当装置１のディスプレイに表示されるデジタル地図データの表示画面であるが、道路の表示は省略している。
【００６８】
図１０の画面７及び８において、Ｒａ〜Ｒｃは、「重要交差点」に対する設置が指定された路側機である。Ｒａ〜Ｒｃの添え字ａ〜ｃは、ユーザが設置を指定した順番を表す。
ここでは、前述の通り、重要交差点に設置する路側機のためのタイムスロットＳＬ１，ＳＬ２，ＳＬ１３，ＳＬ１４が予め確保されているとする。従って、重要交差点に最初に設置が指定される路側機Ｒａについては、リソース割当部１７は、路側機Ｒａの位置情報がどのエリアであるかに関係なく、予め確保されたいずれかのタイムスロット（例えばスロットＳＬ１）を割り当てる。
【００６９】
図１０の画面７は、路側機Ｒａ→路側機Ｒｂ→路側機Ｒｃの順で重要交差点に対する路側機の設置が指定された場合の表示画面である。ここでは、２番目の路側機Ｒａの位置情報は、路側機Ｒａと相互に重要交差点干渉エリア２１の外部であり、３番目の路側機Ｒｃの位置情報は、路側機Ｒａの重要交差点干渉エリア２１の内部であるとする。
重要交差点干渉エリア２１は、路側機Ｒａを含むセルＣから所定の非干渉距離（例えば、１１８０ｍ）だけ縦横に離れた矩形領域に含まれる複数のセルＣよりなる。
【００７０】
リソース割当部１７は、２番目の路側機Ｒａについては、１番目の路側機Ｒａと相互に干渉関係にないので、１番目の路側機Ｒａと同じタイムスロット（例えばスロットＳＬ１）を割り当てる。
リソース割当部１７は、３番目の路側機Ｒｃについては、１番目の路側機Ｒａと干渉すするので、ＰＳＧ割当を実施する。
【００７１】
図１０の画面８に示す通り、新設の路側機Ｒｃに対するＰＳＧ割当が行われると、リソース割当部１７は、路側機Ｒｃを含むセルＣを中心としたＰＳＧエリア２０Ｃを更に設定する。
以後、ユーザが指定する新設路側機の位置情報がＰＳＧエリア２０Ａ〜２０Ｃの内部か外部かにより、新設路側機に適用するリソース割当の種別をＰＳＧ割当とするかＶＣ割当とするかが決定される（図７のステップＳＴ１２）。
【００７２】
〔第２の変形例：空きスロットなしの場合の再割当〕
図１１は、路側機の新設ごとのリソース割当の別例を示す説明図である。
図１１の画面９及び１０も、無線リソース割当装置１のディスプレイに表示されるデジタル地図データの表示画面であるが、道路の表示は省略している。
【００７３】
図１１の画面９及び１０において、Ｒ８は、「一般交差点」に対する新設が指定された路側機である。
ここでは、図１１の画面９に示す通り、路側機Ｒ８の位置情報が既設のＰＳＧエリア２０Ａ〜２０Ｃの内部にあり、かつ、路側機Ｒ８のＰＳＧ割当を行っても、一般交差点に設置する路側機Ｒ８のためのタイムスロットＳＬ３〜ＳＬ１２に空きがないものとする。
【００７４】
この場合、リソース割当部１７は、図１１の画面１０に示す通り、路側機Ｒ８に関する再割当エリア２２を設定する。再割当エリア２２は、路側機Ｒ８を含むセルＣから所定の非干渉距離（例えば、１１８０ｍ）だけ縦横に離れた矩形領域に含まれる複数のセルＣよりなる。
そして、リソース割当部１７は、再割当エリア２２に含まれるすべての路側機Ｒ４〜Ｒ８，Ｒａ，ＲｃについてＰＳＧ割当を実施して無線リソースの再割当を行う。
【００７５】
このようにすれば、既設の路側機Ｒ４〜Ｒ７，Ｒａ，Ｒｃに対するＰＳＧ割当により、路側機８のためのタイムスロットに空きが発生する場合があり、新設の路側機Ｒ８に対する無線リソースの割り当てが可能になり得る。
【００７６】
〔その他の変形例〕
上述の実施形態（変形例を含む。）は、すべての点で例示であって制限的なものではない。本発明の権利範囲は、特許請求の範囲に記載された構成と均等の範囲内でのすべての変更が含まれる。
【００７７】
例えば、上述の実施形態において、ＶＣマップ生成部１６は必ずしも無線リソース割当装置１に搭載される必要はなく、他のコンピュータ装置に存在してもよい。この場合、他のコンピュータ装置が生成したＶＣマップ１９を記憶部１１にインストールすればよい。
【符号の説明】
【００７８】
１  無線リソース割当装置
１１  記憶部
１２  情報処理部
１３  コンピュータプログラム
１４  地図情報
１５  エリア情報
１６  ＶＣマップ生成部
１７  リソース割当部
１８  道路地図データ
１９  ＶＣマップ
２０  ＰＳＧエリア
２０Ａ〜２０Ｃ  ＰＳＧエリア
２１  重要交差点干渉エリア
２２  再割当エリア
【図１】
2019198011.tif 000003
【図２】
2019198011.tif 000004
【図３】
2019198011.tif 000005
【図４】
2019198011.tif 000006
【図５】
2019198011.tif 000007
【図６】
2019198011.tif 000008
【図７】
2019198011.tif 000009
【図８】
2019198011.tif 000010
【図９】
2019198011.tif 000011
【図１０】
2019198011.tif 000012
【図１１】
2019198011.tif 000013