第 4 章 帯域保証チャネル割当方式
4.4 シミュレーションと考察
4.4.1 シミュレーション手順
4.3節より，端末への動的チャネル割当問題は，以下の最適化問題に帰着する ことができる．
m j
j m j m
x R
T max
( ) ( )max
)
1
( ) (
m i m D q
x
q
mM,
i1 , 2 ,
,
Nb
m j m
j
N
x
( )
jDi(m),
i1 , 2 ,
,
Nb
) min
( R
Rj m
jDi(m),
i1 , 2 ,
,
Nb
(4.7)
本問題は整数混合非線形最適化問題のため，線形時間内に全体最適解を導出 することは難しい．そこで，本シミュレーションにおいては，その解法として，
[14]と同じくグリーディ法を用いて，それぞれの基地局に属する端末毎に順次チ ャネル割当を行う．(4.6)式の拘束条件に関して，他の基地局のチャネルの割当状 態によっては干渉波の影響で Rj(m)が Rminよりも小さくなる可能性がある．そこ で(4.6)式を満たすことを考慮して，図4.4-1 に示すフローチャートに従ってシミ ュレーションを行う．
条件(4.6)を満たせ ない端末を呼損
No start
基地局における 最適な解の導出
解は存在 する？
条件 (4.6) の 干渉抑止制御
所望波の受信電力 が最低の端末を呼損
Yes
end 基地局 ループ ( 終わり )
基地局 ループ ( 始まり )
図4.4-1 提案方式のフローチャート
図4.4-1の通り，チャネル割当は基地局ループにより基地局毎に順次チャネル を割当てる．基地局ループの処理として，まず，既にチャネルを割当てた基地 局からの干渉波を考慮し，チャネル割当てを行っていない基地局からの干渉波 は受けていないと仮定した状況で各端末の各チャネルが(4.6)式を満たすかどう か判定を行う．(4.6)式を満たさない場合，その端末は呼損とする．
次に，その時点でループの対象である基地局に属する端末に関して，拘束条
件の(4.3)式と(4.4)式の下で，(4.5)式を最大化するような解を導出し，チャネル割
当の組み合わせを求める．その際，後に述べる干渉抑止制御のため，端末が必 要とするチャネル数に対して基地局が割当てることが可能なチャネル数が不足 している場合は(4.4)式を満たさず解が存在しない．この場合は，基地局の配下に ある端末の中で，システム全体のスループットに対する寄与が小さいと推測さ れる所望波の受信電力が最も小さい端末を呼損として扱う．その結果，その基 地局に属する端末が必要とするチャネル数の総和よりもその基地局が使用可能 なチャネル数が大きくなれば，解が導出可能となる．
基地局に所属している端末へのチャネル割当の組み合わせが決定した後，拘 束条件である(4.6)式を担保するために干渉波を抑止する制御を行う．すなわち，
この後の基地局ループのチャネル割当において(4.6)式を満たさなくなるような チャネルの割当を抑止する．図4.4-1の干渉抑止制御の具体的手順を記述したフ ローチャートを図4.4-2に示す．
U
j(m)を考慮した R
j(m)の導出
No start
U
j(m)の内，端末 j へ与 える干渉電力が最大 である基地局を U
j(m)から除外し P
j(m)に追加
Yes
end
R
j(m)=R
minか？
チャネル割り当 て対象の端末 ループ（終わり）
チャネル割り当 て対象の端末 ループ（始まり）
基地局セット U
j(m)の導出
P
j(m)に含まれる 基地局のチャネ ル割り当て抑止
図4.4-2 干渉抑止制御のフローチャート
干渉抑止制御は，直前の処理でチャネル割当対象となった端末に関するルー プ処理となる．今，基地局iに属しているチャネル割当対象端末jの処理を行っ ているとすると，ループの最初の処理として，この後チャネル割当を行う基地 局の中で端末 j に干渉波を送出する可能性がある基地局を求め，そのセットを Uj(m)とする．
( ) ( )
)
(
: ,
m0 ,
i mm u
j u u i D j D
U (4.8)
次に，端末jがUj(m)に含まれる全ての基地局から干渉波を受信すると仮定して Rj(m)を求める．
( ) 0
) 2
(
log 1
j m U u
uj m ij
j
N g Q
Q f g
R
(4.9)求めたRj(m)が(4.6)式を満たしているか判定し，(4.6)式を満たしていなかった場
合は Uj(m)に含まれる基地局のうち最も端末 j に与える干渉電力が大きい基地局 を Uj(m)から除外し，チャネル割当抑止対象の基地局セット Pj(m)に追加する．新 しく更新された Uj(m)を用いて(4.9)式からスループット Rj(m)を求めて再度(4.6)式 を満たしているか判定を行い，(4.6)式を満たしていなかった場合は同様に Pj(m)， Uj(m)の更新処理を行う．そして，求めたRj(m)が(4.6)式を満たしたときPj(m)に含ま れる基地局については，それらの基地局が対象となる基地局ループ時に，端末j に割当てられたチャネルと同じチャネルは使用不可とする．こうして基地局 i からチャネルを割当てた全ての端末について干渉抑止制御を行い，干渉抑止制 御のループ処理は終了となる．以上のように，図4.4-1，図4.4-2のフローチャー トに従って，チャネルの割当処理を行う．本アルゴリズムによって，干渉波の 有無に関わらず通信環境が悪いため Rmin が担保できない端末や，他端末に干渉 して Rmin を損なってしまう端末を呼損とすることで，通信を行う端末のチャネ ルのスループットがRminを担保可能となる．
xj(m)を要素にもつNm×Ncの行列をXとするとチャネルmを用いてシステム全 体で得られるスループットTmは次のように表される．
j
j m m m
j m
m
R x
T x
( )x
( ) m M
(4.10)ここで，xmはXのm番目のチャネルの列ベクトルを示す．これらを用いると図
4.4-1，図4.4-2のアルゴリズムは以下のようなプログラムとなる．
For i= 1:Nb
y= [0, 0, …, 0]T; z= [0, 0, …, 0]T; Tbef =O;
Taft =O;
For j= 1:Nm
For m= 1:Nc
For k = 1:Nm
If X(k,m) = 1 y(k) = 1;
Else y(k) = 0;
End If End For
If j ∈Di(m) then
If Rj(m)(y+ejNm)<Rmin then X(j,m) = 0;
End If
Tbef(j,m) =Tm(y);
y=y+ejNm; Taft(j,m) =Tm(y);
End If End For End For Ω=Taft–Tbef; X(j∈Di(m), 1:Nc)
←
) (
)
max (
arg
i m D
j m
j m jmx
x
s. t. 1) ( ) 1
) (
m i m D q
xq
2) m j
m
j N
x
( )ifxj(m)is already fixed to 0 3) xj(m) 0
% 基地局のループ
% 要素Nm個の零ベクトル
% 要素Nm個の零ベクトル
%OはNm×Ncの零行列
%OはNm×Ncの零行
% 端末のループ (a)
% チャネルのループ
% 既にチャネル割当済の場合
% チャネルループ終わり
% 端末ループ終わり
% 最適化問題の解をXに代入
If X(j∈Di(m), 1:Nc) doesn’t exist then X(jmin, 1:Nc) = 0;
go to (a);
End If
For j= 1:Nm
For m= 1:Nc
If j ∈Di(m)then If X(j,m) = 1 then
Pj(m)={ϕ};
Uj(m)={ϕ};
z= [0, 0, …, 0]T;
( ) ( )
)
( : , m 0, im
m u
j uu i D j D
U
z=X(1:Nm,m) + Nm
j m U u
eu
( )
If Rj(m)(z)<Rmin then Uj(m)=Uj(m)– {umax};
Pj(m)=Pj(m)+ {umax};
go to (b);
End If
X(k,m) = 0; ∀k∈Dp(m),
∀p∈Pj(m) End If
End If End For End For End For
%jminは基地局iに属する端末の中で 受信電力が最も弱い端末
% 端末ループ
% チャネルループ
% 要素Nm個の零ベクトル
% (b)
% umaxはUj(m)に属していて% 端末j への干渉電力が最も強い基地局
% チャネルループ終わり
% 端末ループ終わり
% 基地局ループ終わり
ここで，ejNmはNm個の要素を持ち，j番目の要素を1でそれ以外の要素を0とす る単位列ベクトルを示す．
基地局iに属する端末への最適なチャネル割当をするに当たり，基地局iに属 する各々の端末に各々のチャネルを仮に割当てると考えたときのシステムスル ープットの増加量Ω(=Taft – Tbef)を計算し，1)～3)の3つの拘束条件の下でシス テムスループットを最も増加させるような X の組み合わせを決定する．Ω の計 算では，計算している基地局iのループより前の基地局のループで既にチャネル を割当てることになっていたとき，そのxj(m)を1として計算する．また，Ωの計 算時には，各端末のチャネルが(4.6)式を満たすことが可能か計算し，不可能な場 合は当該の端末にそのチャネルは割当てない(X(j,m) = 0)．この(4.6)式に関わる判 定，及び，基地局iのループより前の基地局ループで実施された干渉抑止制御を 考慮するため，基地局iのチャネル割当時の拘束条件に3)を含んでいる．拘束条 件3)より使用可能なチャネル数が制限され，基地局iに属する全ての端末との通 信に必要なチャネル数が確保できない場合は解 X が存在せず，受信電力が最も 小さい端末を呼損とする．基地局iのチャネル割当実施後は，拘束条件(4.6)に関 わる干渉抑止制御を実施する．基地局iに属する端末への最適なチャネル割当は，
基地局IDが小さなものから順次行う．