JP6816625B2 - 回線設計方法及び装置 - Google Patents

Description

本発明は、回線設計を行う方法及び装置に関する。

例えば衛星通信において多元接続を実現するために、周波数分割多元接続（ＦＤＭＡ；Frequency-Division Multiple Access）の一方式である要求割当多元接続（ＤＡＭＡ；Demand Assigned Multiple Access）などが使用されている。ＦＤＭＡでは、通信周波数帯を複数の周波数帯域（回線）に分割して回線を各無線局に割り当てる。ＤＡＭＡでは、回線制御局に対して要求することにより、要求を行った無線局への回線の割り当てが行われる。
ところで衛星通信を実施する場合には、規定のＣ／Ｎｏ（キャリア対ノイズ比）を満たして受信することができるように、割り当てられた周波数ごとに事前に送信電力を決定する必要がある。この事前に送信電力を決定することを回線設計と呼ぶ。衛星通信においては、その通信波の信号の相互間で相互変調が発生することが知られており、相互変調の発生を考慮した回線設計方法あるいは回線設計アルゴリズムの開発が必要となっている。相互変調が発生する条件下においては、ある通信波の信号電力を大きくすると、そのことに関連して他の通信波における干渉が大きくなる。いずれかの通信波における干渉が大きくなればそれがさらに他の通信波における干渉の増大をもたらす。このようにして干渉の連鎖が発生するが、場合によっては干渉の連鎖が循環することがある。干渉の循環連鎖が発生したときには全体の整合を取るためには複雑な計算が必要となり、計算時間が多大なものとなる。場合によっては計算が終了しなくなることもある。相互変調による干渉の循環連鎖は、衛星通信の場合だけではなく、通信周波数帯内において異なる周波数を割り当てて複数の周波数配置を設定する場合に一般的に起こり得ることである。

衛星通信における回線設計に関連するものとして特許文献１は、他の無線回線からの干渉の影響を考慮した上で、同時に使用できる回線の数を求めることができる方法を開示している。特許文献２は、所定数の周波数帯域（回線）を通信周波数帯内に配置して各回線での干渉値を求め、次にいずれかの回線が存在しないのとして各回線での干渉値を求め、これらの結果からＤＡＭＡにより回線を割り当てるときの割り当て順を決めることを開示している。これらの技術は回線設計に関連はしているが、これらの技術だけでは事前に送信電力を決定する回線設計を行うことはできない。

特開２０１１−１１９９８２号公報 特開２０１４−２３９３２８号公報

回線設計では、回線間での相互変調による干渉の循環連鎖が生じると、全体の整合を取るために複雑な計算が必要となって計算時間が長くなり、場合によっては計算が終了しないこともある。
本発明の目的は、相互変調による干渉が起こり得る場合に、複雑な計算を不要として計算時間を短縮でき、計算が確実に終了する回線設計方法と、この回線設計方法を実行する回線設計装置とを提供することにある。

本発明の回線設計方法は、通信周波数帯内で異なる周波数を割り当てて複数の周波数配置を発生することと、複数の周波数配置において干渉を与える周波数配置と干渉を被る周波数配置との関係を有向グラフとして表現することと、有向グラフでの閉路の有無を判定し、閉路が存在する場合にはいずれかの周波数配置を削除して閉路を解消することと、閉路が解消した有向グラフを、各周波数配置をノードとする木構造として扱って、有向グラフの葉から根に向かう方向で干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算することと、を有する。
本発明の回線設計装置は、通信周波数帯内で異なる周波数を割り当てて複数の周波数配置を発生する周波数配置発生部と、周波数配置発生部が発生した複数の周波数配置において周波数配置間の相互変調に起因する干渉を与える周波数配置と干渉を被る周波数配置との関係である干渉関係を求めて干渉関係を有向グラフとして表現する干渉関係決定部と、有向グラフに閉路が存在するかどうかを判定し、閉路が存在する場合には、周波数配置発生部が発生した複数の周波数配置のうちのいずれかを削除して閉路を解消する閉路判定部と、閉路が解消された後の有向グラフを各周波数配置をノードとする木構造として扱って、木構造において葉から根に向かう方向で干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算する送信電力計算部と、を有する。

本発明によれば、相互変調による干渉が起こり得る場合であって、回線設計に複雑な計算を不必要とするとともに、回線設計の計算が確実に終了するようになる。

第１の実施形態の回線設計装置の構成を示すブロック図である。 図１に示す回線設計装置の動作を示すフローチャートである。 第２の実施形態の回線設計装置の構成を示すブロック図である。 図３に示す回線設計装置の動作を示すフローチャートである。 図３に示す回線設計装置を用いた回線設計の例を示す図である。

次に本発明の実施の形態について、図面を参照して説明する。
（第１の実施形態）
図１は第１の実施形態の回線設計装置の構成を示すブロック図である。この回線設計装置は、最も基本的な構成のものであって、周波数配置発生部２１、干渉関係決定部２２、閉路判定部２３及び送信電力計算部２４を備えている。周波数配置発生部２１は、通信周波数帯内で異なる周波数を割り当てて複数の周波数配置を発生する。干渉関係決定部２２は、周波数配置発生部２１が発生した複数の周波数配置において周波数配置間の相互変調に起因する干渉を与える周波数配置とその干渉を被る周波数配置との関係である干渉関係を求め、この干渉関係を有向グラフとして表現する。閉路判定部２３は、干渉関係を表す有向グラフに閉路（ループ）が存在するかどうかを判定し、閉路が存在する場合には、周波数配置発生部２１が発生した複数の周波数配置のうちのいずれかを削除して閉路を解消する。送信電力計算部２４は、閉路が解消された後の有向グラフを各周波数配置をノードとする木構造として扱って、木構造において葉から根に向かう方向で干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算する。送信電力計算部２４が計算する干渉は相互変調に起因する干渉であるので、その干渉量と、干渉の存在下で必要となる送信電力値とを算出するアルゴリズムは、当業者には広く知られたものである。

次に、図１に示した回線設計装置の動作について、図２のフローチャートを用いて説明する。まず、ステップ１０１において周波数配置発生部２１が、通信周波数帯内で異なる周波数を割り当てて複数の周波数配置を発生する。通信周波数帯において各周波数配置に対してどのように周波数を割り当てるかは任意のものとすることができる。例えば、通信周波数帯の周波数を所定の個数までランダムに選択して、それらの選択された周波数をそれぞれの周波数配置に対応させてもよい。あるいは、予め定めた規則に基づいて周波数をそれぞれの周波数配置に割り当てるようにしてもよい。発生させる周波数配置の数は、例えば、制御パラメータとして周波数配置発生部２１に予め入力しておくことができる。

ステップ１０１において周波数配置を発生させたら、次にステップ１０２において、干渉関係決定部２２が、これらの周波数配置間の相互変調に起因する干渉を与える周波数配置とこの干渉を被る周波数配置との関係すなわち干渉関係を有向グラフとして表現する。相互変調が発生する系の非線形性と周波数配置とが与えられたときにこれらから干渉が発生する周波数を求める方法は当業者には周知であり、干渉関係決定部２２は、この周知の方法に基づいて干渉関係を求めてその干渉関係を有向グラフとして表現する。このとき、有向グラフにおいて、周波数配置における干渉関係は、干渉を与える周波数配置から干渉を被る周波数配置に向かう矢印（すなわち有向枝）として表現することができる。当然のことながら、各周波数配置はそれぞれ有向グラフにおけるノードとして扱われる。ここでいう有向グラフは、矢印を用いて図解的に表されたものに限定されるものではなく、数学でのグラフ理論において有向グラフの表現として認められているすべてものが含まれる。例えば、集合間の写像に基づいて記述されるもの、例えば、関係式や関数式で表される関係で表されるものであってもよい。ここでは相互変調に起因する干渉を考えているので、ある周波数配置に対して干渉を及ぼす原因となる周波数配置は必ず２つ以上存在する。すなわち、図解表現での有向グラフにおいて、干渉を被っている周波数配置に対応するノードに対しては、そのノードに向かう矢印が２本以上存在する。実際には３つの異なる周波数配置からの干渉を考慮しなくてもよい場合がほとんどなので、干渉を被る１つの周波数配置に対し、その干渉を与える２つの周波数配置が存在すると考えてよい。

本実施形態において有向グラフは干渉関係における干渉の連鎖を示すものであり、有向グラフにおける閉路は、干渉の連鎖が循環することを表す。回線設計の演算の複雑さを排除し、また最適値を求めるためには、干渉の循環連鎖を解消する必要がある。そこで、ステップ１０３において、閉路判定部２３が、干渉関係を表す有向グラフに閉路（ループ）が存在するかどうかを判定する。有向グラフにおける閉路の判定方法としてはいくつかのものが知られているが、この中で、トポロジカルソートを用いる方法が、演算量が少ないなどの点で好ましい。閉路が存在しない場合には、ステップ１０５に移行する。閉路が存在する場合には、ステップ１０４において閉路判定部２３は、閉路を構成するいずれかのノードすなわち周波数配置を削除することによってその閉路を解消し、その後、処理はステップ１０５に移行する。閉路内のどの周波数配置を削除するかは適宜に定めることができる。周波数配置を削除することは、その周波数配置を使用せず、送信電力も定めないことを意味する。

グラフ理論によれば閉路が存在しないグラフは木構造であるから、閉路を削除された上述の有向グラフも木構造として扱うことができる。そこでステップ１０５では、送信電力計算部２４が、閉路が解消した有向グラフを各周波数配置をノードとする木構造として扱って、木構造において葉から根に向かう方向で干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算する。ここで木構造の葉の側から送信電力値を計算すなわち回線設計を行うのは、根側にあるノードは、葉側にあるノードでの回線設計結果の影響を受けるからである。葉側から根側に向けて、順次、回線設計を行い、最終的にすべてのノードすなわち周波数配置に対して回線設計を完了させる。以上説明したように本実施形態では、干渉の循環連鎖を防止して回線設計を実施する順番を定めることができるので、計算の複雑性を排除でき、計算時間の短縮を実現でき、計算の終了性を担保することができる。

（第１の実施形態の応用例）
上述した第１の実施形態において、通信周波数帯は、例えば、衛星通信のために割り当てられた周波数帯域であり、複数の周波数配置は、ＦＤＭＡにより衛星通信を実行する際に通信周波数帯内で使用される個々の周波数チャネルである。通信周波数帯内で複数の周波数配置を発生させる場合には、その通信周波数帯内で衛星通信の設定されるチャネルの数だけの周波数配置を発生させるようにすることができる。また、本実施形態は、衛星通信以外の用途において回線設計を行う際にも使用することができる。

（第２の実施形態）
第１の実施形態では、有向グラフにおける閉路を解消するときに周波数配置を削除するため、当初発生させた周波数配置よりも回線設計が行われた周波数配置の方が数が少なくなることがある。これは、例えばＦＤＭＡにおいて所定数の周波数チャネルを設けたいという要望には応えられないことになる。そこでこの第２の実施形態では、有向グラフにおける閉路の解消のために周波数配置を削除した場合であっても、回線設計が行われる周波数配置の数を減らさないようにする。図３は、第２の実施形態の回線設計装置の構成を示している。
図３に示される回線設計装置は、図１に示される回線設計装置に、さらに、閉路判定部２３が削除した周波数配置と同数の周波数配置を新たな周波数配置として追加する周波数配置追加部２５を設けたものである。本実施形態では、送信電力計算部２４は、周波数配置追加部２５が追加した新たな周波数配置も含めて送信電力値を計算する。

次に本実施形態の回線設計装置の動作について、図４及び図５を用いて説明する。図４は、図３に示す回線設計装置の動作を示すフローチャートであり、図５は、本実施形態での回線設計の例を示す図である。図５において丸付き数字は、周波数配置に対応するノードを示している。
まず、第１の実施形態で説明したステップ１０１〜１０３を実行する。ここではステップ１０１において、相互に異なる周波数であるという条件で、通信周波数帯内で６個の周波数配置１〜６（図５の（Ａ）で“［１］”〜“［６］”で示す周波数配置）を任意に発生させている。図５の（Ａ）において横軸は周波数である。ステップ１０２（図５における（Ｂ））において干渉関係を有向グラフとして表現すると、例えば、図５の（Ｃ）に示す有向グラフが得られる。この有向グラフでは、周波数配置４→周波数配置２→周波数配置３→周波数配置４という閉路が生じている。

ステップ１０３においては、閉路判定部２３が、干渉関係を表す有向グラフに閉路（ループ）が存在するかどうかを判定するが、本実施形態では、閉路がある場合には、ステップ１０６において、閉路判定部２３が、いずれか１つの周波数配置を削除して、その周波数配置に対応した閉路を解消する。有向グラフにおいて閉路が複数存在することがあり得るから、ステップ１０６の実行後は再びステップ１０３を実行し、さらなる閉路が存在するかを判定する。この処理は、図５において（Ｄ）〜（Ｆ）により示されており、有向グラフに含まれる閉路のすべてが解消されるまで繰り返される。例えば、図５の（Ｃ）に示すように有向グラフに閉路が存在する場合に、この閉路を解消を目的として周波数配置１を削除したとすると、図５の（Ｅ）に示すような有向グラフが得られる。図５の（Ｅ）の有向グラフは閉路を含んでいない。

ステップ１０３において閉路が存在しないと判定された場合には、処理はステップ１０７（図５においては（Ｇ））に移行する。ステップ１０７では、周波数配置追加部２５が、さきに閉路判定部２３が削除した周波数配置（図５の（Ｄ）〜（Ｆ）の処理で削除した周波数配置）と同数の周波数配置を、新たな周波数配置として、削除されなかった周波数配置に追加する。新たな周波数配置は、他の周波数配置に対して相互変調による干渉を与えるものであってはならない。そのような条件を満たす新たな周波数配置の周波数は、トライアンドエラーで決めてもよいし、他の周波数配置に対して干渉を発生し得る周波数を予め算出しておき、通信周波数帯内でそのような周波数を避けるようにして決めてもよい。図５に示す例では、既に周波数配置１を削除したが、周波数配置１の削除に対応して、図５の（Ｈ）に示すように、新たな周波数配置として周波数配置７が追加されている。

ステップ１０７の実行後、第１の実施形態でのステップ１０５と同様に、ステップ１０８（図５の（Ｉ））において、送信電力計算部２４が、ステップ１０７で追加した新たな周波数配置も含め、各周波数配置をノードとする木構造として有向グラフを扱って、木構造において葉から根に向かう方向で干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算する。図５の（Ｊ）は、干渉を葉から根に向かう方向で伝播させる計算の例を示している。その結果、図５の（Ｋ）に示すように、干渉の循環連鎖が解消された周波数配置とそれらの周波数配置ごとの送信電力が最終的に決定する。図５の（Ｌ）は、横軸を周波数とし、格子状のハッチング部の高さが送信電力を示すものとして、このようにして決定された周波数配置と送信電力の例を示している。ここでは、６個の周波数配置２〜７に対して送信電力が算出されており、これらの周波数配置２〜７に対する回線設計が行われたことになる。

上述した各実施形態の回線設計装置は、一例としてコンピュータによって構成することもできる。コンピュータとしては、一般的なパーソナルコンピュータあるいはワークステーションを用いることができる。コンピュータによって回線設計装置を構成する場合には、図２あるいは図４を用いて説明した処理をコンピュータに実行させるためのコンピュータプログラムをコンピュータに読み込ませて、そのコンピュータプログラムを実行させればよい。したがって本発明の範疇には、このようなコンピュータプログラムや、このコンピュータプログラムを格納した非一時的記録媒体も含まれる。

上記の実施形態の一部又は全部は、以下の付記のようにも記載され得るが、以下には限られるものではない。

［付記１］ 通信周波数帯内で異なる周波数を割り当てて複数の周波数配置を発生することと、
前記複数の周波数配置において周波数配置間の相互変調に起因する干渉を与える周波数配置と該干渉を被る周波数配置との関係を有向グラフとして表現することと、
前記有向グラフでの閉路の有無を判定し、前記閉路が存在する場合にはいずれかの周波数配置を削除して該閉路を解消することと、
前記閉路が解消した前記有向グラフを各周波数配置をノードとする木構造として扱って、前記木構造において葉から根に向かう方向で前記干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算することと、
を有する、回線設計方法。

［付記２］ 前記閉路を解消することを、前記有向グラフに含まれるすべての閉路が解消するまで繰り返す、付記１に記載の回線設計方法。

［付記３］ 前記閉路を解消するために削除した周波数配置と同数の周波数配置を新たな周波数配置として追加し、前記新たな周波数配置も含めて前記送信電力値を計算する、付記１または２に記載の回線設計方法。

［付記４］ 他の周波数配置に対して干渉を発生し得る周波数を避けて前記新たな周波数配置を追加する、付記３に記載の回線設計方法。

［付記５］ 前記有向グラフに対してトポロジカルソートを適用して前記閉路の有無を判定する、付記１乃至４のいずれか１項に記載の回線設計方法。

［付記６］ 前記複数の周波数配置は周波数分割多元接続において使用される周波数配置である、付記１乃至５のいずれか１項に記載の回線設計方法。

［付記７］ 通信周波数帯内で異なる周波数を割り当てて複数の周波数配置を発生する周波数配置発生部と、
前記周波数配置発生部が発生した複数の周波数配置において周波数配置間の相互変調に起因する干渉を与える周波数配置と該干渉を被る周波数配置との関係である干渉関係を求めて該干渉関係を有向グラフとして表現する干渉関係決定部と、
前記有向グラフに閉路が存在するかどうかを判定し、前記閉路が存在する場合には、前記周波数配置発生部が発生した複数の周波数配置のうちのいずれかを削除して前記閉路を解消する閉路判定部と、
前記閉路が解消された後の前記有向グラフを各周波数配置をノードとする木構造として扱って、前記木構造において葉から根に向かう方向で前記干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算する送信電力計算部と、
を有する、回線設計装置。

［付記８］ 前記閉路判定部は、前記閉路を解消することを、前記有向グラフに含まれるすべての閉路が解消するまで繰り返す、付記７に記載の回線設計装置。

［付記９］前記閉路判定部が削除した周波数配置と同数の周波数配置を新たな周波数配置として追加する周波数配置追加部をさらに有し、
前記送信電力計算部は、前記周波数配置追加部が追加した前記新たな周波数配置も含めて前記送信電力値を計算する、付記７または８に記載の回線設計装置。

［付記１０］ 前記周波数配置追加部は、他の周波数配置に対して干渉を発生し得る周波数を避けて前記新たな周波数配置を追加する、付記９に記載の回線設計装置。

［付記１１］ 前記閉路判定部は、前記有向グラフに対してトポロジカルソートを適用して前記閉路の有無を判定する、付記７乃至１０のいずれか１項に記載の回線設計装置。

［付記１２］ コンピュータに、
通信周波数帯内で異なる周波数を割り当てて複数の周波数配置を発生する処理と、
前記複数の周波数配置において周波数配置間の相互変調に起因する干渉を与える周波数配置と該干渉を被る周波数配置との関係を有向グラフとして扱う処理と、
前記有向グラフでの閉路の有無を判定し、前記閉路が存在する場合にはいずれかの周波数配置を削除して該閉路を解消する処理と、
前記閉路が解消した前記有向グラフを各周波数配置をノードとする木構造として扱って、前記木構造において葉から根に向かう方向で前記干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算する処理と、
を実行させるプログラム。

［付記１３］ 前記コンピュータに、前記閉路を解消する処理を、前記有向グラフに含まれるすべての閉路が解消するまで繰り返し実行させる、付記１２に記載のプログラム。

［付記１４］ 前記コンピュータに、
前記閉路を解消するために削除した周波数配置と同数の周波数配置を新たな周波数配置として追加する処理を実行させ、
前記計算する処理において、前記新たな周波数配置も含めて前記送信電力値を計算させる、付記１２または１３に記載のプログラム。

［付記１５］ 前記追加する処理において、前記コンピュータに、他の周波数配置に対して干渉を発生し得る周波数を避けて前記新たな周波数配置を追加させる、付記１４に記載のプログラム。

［付記１６］ 前記解消する処理において、前記コンピュータに、前記有向グラフに対してトポロジカルソートを適用して前記閉路の有無を判定させる、付記１２乃至１５のいずれか１項に記載のプログラム。

２１ 周波数配置発生部
２２ 干渉関係決定部
２３ 閉路判定部
２４ 送信電力計算部
２５ 周波数配置追加部
１０１〜１０８ ステップ

Claims (10)

1. 通信周波数帯内で異なる周波数を割り当てて複数の周波数配置を発生することと、
   前記複数の周波数配置において周波数配置間の相互変調に起因する干渉を与える周波数配置と該干渉を被る周波数配置との関係を有向グラフとして表現することと、
   前記有向グラフでの閉路の有無を判定し、前記閉路が存在する場合にはいずれかの周波数配置を削除して該閉路を解消することと、
   前記閉路が解消した前記有向グラフを各周波数配置をノードとする木構造として扱って、前記木構造において葉から根に向かう方向で前記干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算することと、
   を有する、回線設計方法。
2. 前記閉路を解消することを、前記有向グラフに含まれるすべての閉路が解消するまで繰り返す、請求項１に記載の回線設計方法。
3. 前記閉路を解消するために削除した周波数配置と同数の周波数配置を新たな周波数配置として追加し、前記新たな周波数配置も含めて前記送信電力値を計算する、請求項１または２に記載の回線設計方法。
4. 他の周波数配置に対して干渉を発生し得る周波数を避けて前記新たな周波数配置を追加する、請求項３に記載の回線設計方法。
5. 前記有向グラフに対してトポロジカルソートを適用して前記閉路の有無を判定する、請求項１乃至４のいずれか１項に記載の回線設計方法。
6. 通信周波数帯内で異なる周波数を割り当てて複数の周波数配置を発生する周波数配置発生部と、
   前記周波数配置発生部が発生した複数の周波数配置において周波数配置間の相互変調に起因する干渉を与える周波数配置と該干渉を被る周波数配置との関係である干渉関係を求めて該干渉関係を有向グラフとして表現する干渉関係決定部と、
   前記有向グラフに閉路が存在するかどうかを判定し、前記閉路が存在する場合には、前記周波数配置発生部が発生した複数の周波数配置のうちのいずれかを削除して前記閉路を解消する閉路判定部と、
   前記閉路が解消された後の前記有向グラフを各周波数配置をノードとする木構造として扱って、前記木構造において葉から根に向かう方向で前記干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算する送信電力計算部と、
   を有する、回線設計装置。
7. 前記閉路判定部は、前記閉路を解消することを、前記有向グラフに含まれるすべての閉路が解消するまで繰り返す、請求項６に記載の回線設計装置。
8. 前記閉路判定部が削除した周波数配置と同数の周波数配置を新たな周波数配置として追加する周波数配置追加部をさらに有し、
   前記送信電力計算部は、前記周波数配置追加部が追加した前記新たな周波数配置も含めて前記送信電力値を計算する、請求項６または７に記載の回線設計装置。
9. 前記周波数配置追加部は、他の周波数配置に対して干渉を発生し得る周波数を避けて前記新たな周波数配置を追加する、請求項８に記載の回線設計装置。
10. コンピュータに、
    通信周波数帯内で異なる周波数を割り当てて複数の周波数配置を発生する処理と、
    前記複数の周波数配置において周波数配置間の相互変調に起因する干渉を与える周波数配置と該干渉を被る周波数配置との関係を有向グラフとして扱う処理と、
    前記有向グラフでの閉路の有無を判定し、前記閉路が存在する場合にはいずれかの周波数配置を削除して該閉路を解消する処理と、
    前記閉路が解消した前記有向グラフを各周波数配置をノードとする木構造として扱って、前記木構造において葉から根に向かう方向で前記干渉を伝播させながら各ノードに対応する周波数配置に対する送信電力値を計算する処理と、
    を実行させるプログラム。

Images