電力用移動無線システムの最適盾臨
所 健一，松井 正一
州‖l…l…l‖＝‖＝＝‖‖＝‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖＝‖‖‖削＝l……ll削‖…】l…ll‖＝＝‖‖‖‖‖‖＝‖‖‖＝‖‖＝‖‖‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖＝‖‖附＝川‖‖‖‖‖‖＝‖‖………‖‖‖‖＝‖‖‖＝‖‖‖‖＝‖＝＝＝‖‖‖＝＝‖＝‖洲‖l＝＝‖‖‖＝＝‖‖‖＝冊されている。しかし，これらの手法を電力用移動無線

1． はじめにの周波数割当てに適用するには，計算時l湖や最適解へ

電力用移動無線システムは，電力会社が独自に構の収束性の面で問題があった．そこで，ここでは基地築。運用している移動無線システムであり，安定した局への最適な周波数割当てを求める手法として，貪欲

電力を供給するうえで非常に重要な役割を果たしていアルゴリズムと追イ云的アルゴリズム（GA：Geneticる．たとえば台風などの自然災害により電力の供給にAlgorithm）［2，3］の組合せによる新たな割当手法を障害が発生した場合，感電などの事故を未然に防ぎつ開発した。この手法を実際の割当問題に適用したとこ

つ，いち早く障害を授旧するには複数の作業班が連携ろ，利用周波数の帯域幅が最小となる割≡1iてが，非常して作業を進める必要があり，このためには電力用移に短い計算時問で求められ，周波数割当て作業の大幅動無線システムを用いた作業班の密接な連結が不可欠な効率化がノ実現された

本稿では次章において，必要チャネル数の算定方法なものとなっている．

この電力用移動無線システムのディジタル化を検討している電力会社において，近年の移動無線の急速な普及により，ますます貴重な資源となっている周波数を，いかに有効に利用するかが重要な課題となった．
そこで，周波数を有効に活用するために必要となる，について説明する．また，3章において周波数の最適別当手法について説明を行う。

2．必要チャネル数の算定
電力用移動無線システムのチャネル数の算定にアーランB式を用いるには，以下の点で問題がある．

各基地局で最低限必要となるチャネル数を明確に算定する方法と，利用周波数の帯域幅が最小となるように，⑳アーランB式の導出においては，呼の到着が話各基地局に対し最適に周波数を割り当てる方法の二つ中の呼故には依存せず，一定であること（無限呼について検討を行った．本稿ではこの二つの検討内容源）を仮定する．しかし，電力用移軌無線においについて報告する．て同一チャネルを共用する移動局数は数十であり，一般的な必要チャネル数の算定にはアーランB式

話中や通話待ちの移動局が増えれば，新たな呼の［1］が用いられることが多いが，これを電力用移動無到着は少なくなると考えるのが自然である線に通用するには2章で述べる問題がある．そこで，⑳電力用移動無線では他の移動局の通話を傍受でき移動無線の利用がピークとなる台風などによる障害のるので，他の移動局によりチャネルが利用されて復旧作業時を対象に，規定時間内に想定される障害箇いた場合，この移動局の通話終了を待ち，終了と所数の観点から，必要チャネル数を算定する方法を開同時に通話を開始することができる．したがって，発した．提案方法では復旧作業における作業班の作業

アーランB式のような即時式ではなく，チャネ状態の推移を閉鎖型待ち行列網でモデル化し，この待ル空きを待ち，チャネル空きと同時に通盲活を開始

ち行列網の解析から得られる復旧可能筒所数と通話待できるとした待時式で必要チャネル数を評佃する

ち時間から，必要となるチャネル数を算定する．のが適当である．

周波数の最適割当てに関しては，これまでにも数多⑳アーランB式では呼はすべて同一に扱われるが，くの研究が行われており，さまざまな割当手法が提案

電力用移動無線においては後述するように，通信

ところ けんいち，まつい しょういち（柵電力中央研究所〒201−8511狛日二■巾岩戸北2−11−1

2001年3月号

待ち時間に対する要求の異なる二つの通話が存在
し，それぞれを別クラスの呼と考え，クラスの違いによる優先処理を考慮した必要チャネル数の算© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（11）123

定が必要となる．

開閉器操作作業の中で行われる通話が，それぞれの作業時間内に一様に分布するものと仮定し，Ⅰ馨12に示す

そこで，新たな必要チャネル数の算定方法について検討を行った。

ように，修復作業が乃1回の部分作業から構成され，2．1復旧作業のモデル化

開閉器操作作業が裾2L！ヰ一の部分作業から構成されるも役旧作業は個々の作業班による，l馨Ilに示す一連ののと考える。ここで，裾1，裾2はそれぞれ，修復作業中，作業の繰り返しにより行われる。作業班は障害発生箇開閉器操作作業中に行われる過言封亘I数を表している。

所へと移動し，そこで障害筒所の修役を行う。修復作

2．1．2 チャネルの運用方式

業の完了後は開閉器を操作し，修復箇所への通電を再復1闘牛業時における移動無線のチャネルの運用を，開し，最終的な通電の確認後，次の障害発生筒所へと通信待ち時間に対する要求の厳しい開閉器操作作業に移動する。この修復作業と開閉器操作作業を安全かつ関する通話には，剃り込み優先権が与えられるものと円滑に進めるには，それぞれの作業の1ステップが終してモテリレ化する。つまり，チャネルは開閉器操作作了する毎に，移動無線を用いて監督者へ報一驚を行うと業に関する通話から優先して割り当てられるものとすともに，次の作業指示を受けることが必要となる。なる。また，すべてのチャネルが利月川二Ⅰであっても，修お，これらの復旧作業における通話のうち，修復作業復作業に関する通話がチャネルを利用していた場合にに関する通話については，ある程度の通信待ち時間がは，これを一時中断し，即座に開閉器操作作業に関す許容できるが，感電事故防止などの安全面に直接関わる通話を開始するものとする。

る開閉器操作に関わる通話については，通信待ち時間

2．2 復旧可能箇所敷からのチャネル数算定に対する要求が厳しいという特徴がある。

復旧作業における作業班の作業状態の推移をモテリレ

ここでは上述の役旧作業を以￣Fのようにモテル化し化した閉鎖型の待ち行列綱を解析することで，規定時たうえで，各基地局で必要となるチャネル数の算定を間内の矧［匝」■能筒所数と通信待ち時間を推定し，これ行った。

から必要チャネル数を算定した［4，5］。

2．1．1部分作業への分割

2．2．1閉鎖型待ち行列網によるモデル化

復旧作業中に行われる通話に着日し，修復作業と開l稟13の開銀型待ち行列網により，復旧作業における閉器操作作業を，それぞれ1回の通話をl哀切りとする作業班の作業状態の推移をモデル化する。この閉鎖型部分作業に分割する．分割にあたっては，修復作業と待ち行列細では作業班（客）が優先度クラスを変化させ∴− ニ …〒 ‡￣l享−・・二修復作業

開閉器操作作業

図2 部分作業のイメージ

図1復旧作業のフロー匝 優先度クラスlの客の流れ
確巨田虚＝凹正優尭度クラス2の客の流れ

図3 開銀型待ち行列網による復IL川三業フローのモデル化
瑠2侭（12）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

三オペレーションズ。リサーチながら，復旧作業における「移動」，「修役作業」，「開3．周波数の最適割当て閉器操作作業」，移動練繰を用いた「通話」をそれぞれモデル化したノードを巡回する．図3の待ち行列綱

各基地局の必要チャネル数が与えられた条件で，利で，ノード1，2，4は到着と同時にサービスが受けら用周波数の昔域幅が最小となる，各基地局への周波数れる，作業班の数と同数の窓［lを待った待ち行列であ割当てを求める手法について検討した．なお，この割り，ノード3は利用可能なチャネル数と同数の窓【］を当手法の詳細については，文献［6］を参照されたい．

持つ待ち行列である．ここでは修復作業を行っている

3．1定式化作業班に相当する客の優先度をクラス2，開閉器操作

電力用移動無線システムにおいて採用されている作業を行っている作業班に相当する客の優先度をクラFCA（FixedChannelAssignment）方式を採用した

ス1とし，ノード3におけるクラス1の客に対して，移動無線システムの周波数割当問題は，以下のように割り込み優先権を与える．

定式化される．なお，FCA方式とは，各基地局に対2．2．2 待ち行列網の解析してあらかじめチャネルを割り当てておき，その基地ここでは待ち行列網の定常状態の存在を仮定し，各局のエリア内で発生した通話要求に対しては，その基ノードの客数を状態とするマルコフ連鎖の平衡方程式

地局に割り当てられたチャネルの中から脚一つを選んでを解くことで，各ノードの平均客数を求めた［4，5］．

割り当てる方式である．

そして，この平均客数から，クラス1の客に割り込ま3．1．1前提条件れることによるクラス2の客の待ち時間の増加も考慮

以下のデータが与えられるものとする。

したうえで，クラス1，2の客それぞれのノード3で要求チャネル数：各基地局で必要となるチャネル数の平均待ち時間を計算し，が与えられるものとする．以降，基地局うで必要なチ

これより修復作業と開閉器ャネル数をγどと記述する．なお，一台の送信機には操作作業における通話の平均待ち時間を推定した．

また，この件ち行列網で客が網を循環する平均時間

最大二つのチャネルが割当て可能であり，基地局には（ノード1を出た客が，再びノ岬ド1に戻ってくるま

要求チャネル数に合わせた台数の送信機が設置されるでの平均時間）は，作業班が一障害箇所の復旧作業をつま−）基地局オには「γ才／21台の送信機が設置されるこ終了するのに要する平均時間に相当する．したがって，とになる．ここで「こrlは∬以上の最小の整数を表す。

規定時間をこの平均循環時間で除算し，これに作業班

基地局の干渉条件：すべての基地局の跳に対して，の総数を乗じることで，図4に示すように復旧作業に信号対干渉電力比（CIR）の低から，同一のチャネルあたる作業班全体で，規定時間に何筒所の復旧作業がが利用可能かどうかが与えられるとする．

完了できるかが推定できる．これより規定時間内に想3．1．2 目的関数定される障害箇所数の復旧が行え，通話待ち時間が規以下で定義する全基地局での使用周波数の帯域幅最定値以下となるチャネル数を見つけることで，必要チ小化と，干渉地域に位置する基地局での供用周波数のャネル数の算定が行える．

帯域幅最小化を目的に，基地局に周波数を割り当てる（図5）．なお，ここでは使用する周波数のうち，チャネル番号最大のものと，最小のものとの差を帯域幅と定義する

1．使用周波数帯城幅の最小化：全基地局で使用すチャネル番号

10

525
1580

20 作業班数

図4 復旧可能簡所数の推定結果
2001年3月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（13）125

る周波数の帯域幅を最小化する。5を全基地局の集合，る帯域幅の下界他となる。

舌を基地局イに割り当てられたチャネル番号最大の

1．すべての基地局を対象に，一つの局を1頂点と周波数とすると，maX出演が最小となるように周披

し，同一のチャネルを利用できない才甜司上を直接辺で数を割り当てる．

結んだグラフを作る（l衰Ⅰ6（b））。

2．各項点をγz・−1梱複製する。この時，他の頂点

2．干渉地域使用周波数帯城幅の最小化：他電力会社のこ基地局との干渉地域に位置する基地局で仮川するとの辺も同時に複製する（図6（C））。

周波数の帯域幅を最小化する。C⊂Sを干渉地域に設置される基地局の集合とすると，maX〜。誘が最小と3．同じ局に相当する頂点同」二を辺で結ぶ（†衰16（d））。

周波数を基地局に割り当てるには，このグラフGなるように周波数を割り当てる。
なお，一般的な周波数割当問題では，使用帯域幅ので直接辺で結ばれた頂点は契なる色を塗るという条件最小化のみをl］的としており，二つの帯域幅の最小化の下で，頂点を塗り分けるのに必安な色数のチャネルを目的とする点において，上記の問題は一般的な周波が最低限必要となる。そして，グラフCの頂点を塗り分けるには，最低でもこのグラフの最人クリークの数割当問題とは異なったものとなっている。

3．1．3 制約位数の色数が必要となるので，グラフGの最大クリ以下の三つの制約条件が満たされるように周波数をークの位数は，必要な′帯域幅のチャネル数の下界値と割り当てる．

なる。ただし，この故人クリークにより求まるのは，1．同岬チャネル割当条件：信号対干渉電力比

あくまで必要となる帯域帖の−卜界値である。グラフ（CIR）が許容値を越える基地局の組には，同一一の周Gの作成には，制約条件のうちのチャネル間隔条件波数を割り当てない。

は考慮していないため，実際にはこれ以上のチャネル2．同一局でのチャネル間隔条件：同一の基地局に割り当てるチャネルには，1チャネル以上の間隔を設数が必要となることもある。

なお，最大クリークを求めること自体NP完全な問題となるが，最大クリークを効率的に求める手法がける。
3．同岬送信機でのチャネル間隔条件：「計一の送信提案されており［7］，周波数割当てに関するグラフに機に割り当てられるチャネルは，間隔が7チャネル以ついては，これを用いることで比校的容易に最大クリ下となるようにする．

ークを求めることができる。

なお，一般的な周波数割当問題では上1記の制約のう

3．3 割当手法

ち，同一チャネル割当条件と，同一局でのチャネル間開発した割当手法では，貪欲アルゴリズムとGA隔条件は考慮されているが，同一送信機でのチャネルの組合せにより，二つの使用周波数の帯域帖が最小と間隔条件を考慮したものはない。

なる基地局への最適な周波数割当てを探索する。

3．2 必要帯域幅の下界値

3．3．1貪欲アルゴリズム

以下のようにして作ったグラフGの最大クリーク

使用する帯域幅がなるべく小さくなるように，送信の佳数は，基地局へ周波数を割り当てるのに必要とな（a）対象基地局機に周波数を割り当てる方法の一つに，割当て叶能な（b）グラフの作成（C）頂点の複製（d）辺の追加

図6 彩色問題としての定式化
瑠2圏（14）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ周波数のうち，チャネル番号最小のものから順次割当

クリークに含まれる基地局に設置される送信機，（2）干てを行っていく方法が考えられる．提案手法では，こ渉地域での最大クリークに含まれる基地闘こ設置されの貪欲アルゴリズムにより送信機に周波数を割り当てる送信機，（3）その他の送信機の順に周波数が割り当てることを基本に，GAにより最適な送信機への周波数られるよう，染色体の対立遺伝子の値を設定した．の割当順序を探索する．

（b）個体の適応度

3．3．2 GAによる最適割当順序の探索

個体の適応度をGAを用いて最適な割当順序を探索するのに，以下（ムー叩aX舌）十（長川叩aX舌）〜∈Jの設定を行った．

〜∈ぐで評価し，この他の大きな個体ほど優れた個体とする．

（a）染色体表現

ここでムは全局を対象としたグラフの最大クリーク

基地局に設置される送信機に1から乃までの番号を付けたうえで，チャネルを割り当てていく送信機の順序を染色体として表現する．ここで乃は管内全体で設置される送信機の総数を表し，一台の送信機には最大二つのチャネルが割当て可能であることから，乃＝∑ォ∈5「γ才／21と計算される．の位数を，美、は二l二渉地域の基地局のみを対象としたグラフの最大クリークの位数を表す．ここでム，差はそれぞれ，基地局全体と干渉地域とで最低限必要となるチャネル数となるので，適応度0の割当ては理論的に見て最適な割当てとなる．
（C）GAのパラメータ

この染色体表現でのg番目の遺伝子は，グー1番目までの遺伝子の情報に従った割当てが行われた時点で，次に周波数を割り当てる送信機が，未到当てリストの何番目の要素であるかを表している．未割当てリストとは，まだ周波数が割り当てられていない送信機の番号を列挙したものである．例としてチャネルを割り当てる送信機の総数が7の場合における，染色体（1，5，3，1，3，1，1）に対応する送信機甲割当順序を図7に示した．なお，図7の縦に並んだ数値列は，それぞれの割当て時における未到当てリストを表している．

また，最大クリークに属する基地局間では，同一の周波数を使用することはできず，これらの基地局は干渉条件が厳しい（割当てが難しい）局の集まりと考えることができる。そこで基地局全体を対象としたグラフと，干渉地域に位置する基地局のみを対象としたグラフの最大クリークをそれぞれ求め，（1）全体での最大ー仲代の個体数を200とし，この中からルーレット選択により180の個体を選び，これに突然変異率0．05の一様変異を加えた．そして，この新しく生成された180の個体と，元の200個体を合わせた中で，適応度の高い200個体を次仲代の個体として選択した．
交叉の遺伝的操作は加えなかった．そして，適応度0の個体が見つかるか，世代数が500に達するまで探索を続けた．なお，これらのパラメータの値は，実際に割当実験を行った結果から，探索効率が高い組合せを選択したものである．
3．4 問題への適用結果
実際の電力会社管l勺の基地局に対する榔皮数割当問
題に開発手法を適用した。開発手法を100恒†実行した
ところ，このうちの50［亘Ⅰで，全基地局と干渉地域での帯域幅が最大クリークの位数と一致する，理論的に最適な割当てが求まった．また，最適な割当てが求まらなかった50ケースについては，干渉地域での使用周波数の帯域幅は最小となったものの，全体での使用帯域幅のチャネル数が1だけ増えた．200個体を500未割当て送信機リスト

惟代まで進化させるのに要する計算時問は，Pentium

II333MHzのパ岬ソナルコンピュータで約260秒であるので，100「可の実行中50恒l理論的に最適な割当てが求まったこの計算では，平均的には520秒以下の計算で理論的に最適な基地局への周波数割当てを求めることができたことになる。

1 6 4 2 7 3 5
割当順序

4．むすび
本稿では電力用移動無線システムにおける二つの課

図7 染色体と送信機への割当順序

2001年3月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（15）127

題に対して検討を行った．第一に，各基地局で必要と［3］伊庭斉志：遺伝的アルゴリズムの基礎〜GAの謎を解なるチャネル数の算定方法について検討を行い，チャく〜，オ岬ム札東京，Sep．1994．

ネルの利用がピークとなる復旧作業時を対象に，規定［4］E，GelenbeandI．Mitrani，
OfComputerSystems

時間内に復旧可能な箇所数から必要チャネル数を算定する方法を開発した。第二に，利用周波数の帯域幅が最小となる，各基地局への最適な周波数割当てを求める手法について検討し，利用可能な周波数のうち，チャネル番号が最小となるものから割り当てていく貪欲

本譜訳「計算機システムの解析と設計」，オ【ム社，秋丸
春夫，橋田 温監訳

［5］D．P．Heyman and M．J．Sobel，，EIsevierSciencePublishers，

1990，H本譜訳「確率モデルハンドブック」，朝倉書店，伊探索する新たな割当手法を開発した。

里正夫，今野 活，刀根 薫監訳［6］所 健一，松井正一他，「GAによる移動無線基地局へ

参考文献［1］D．BertsekasandR．G．Gallager，

DataNetworks

Prentice−Hall，Inc．，1987，H本譜訳「データネットワーク」，オーム社，八星縫剛監訳の周波数割当ての最適化」，電気学会通信研究会資料，CMN−00d6，Jan．2000［7］R．CarraghanandR．M．Padalos，
ithm for the maximum clique problem［2］北野宏明（編）：遺伝的アルゴリズム，産業図書，東京，

Anexactalgor−，（砂e7t Res．

Lett．，VOl．9，nO．6，pP．375−382，Nov．1990．

Jun．1993．

周28（16）

Handbooksin

OperationsResearchandManagementScienceVol．2
STOCHASTICMODEL

アルゴリズムを基本に，GAにより最適な割当順序をAnalysisandSynthesis，Academic PressInc．，1980，fl© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ