メッシュネットワークにおける帯域割り当てモデルとスケジューリングに関する研究
M2010MM043 坪井 将行
指導教員：石崎 文雄

はじめに例えば，新しいノードをネットワークのどこに付加するかのように，どのようにネットワークの再構築を行うかが1.1 研究背景
QoS 保証の観点から重要である．なぜなら，ネットワー
近年，無線通信ネットワークの分野においてメッシュ クの再構築により TDMA のスケジューリングも変更しなネットワークに関する研究が盛んに行われている．メッ ければならず，再構築されたネットワークのトポロジー
シュネットワークは，無線通信機能に加えてルーティン が変更後のスケジュールのフレーム長に大きな影響を与グ機能を持つ多数のノードから構成され，ノード同士が えるからである．本研究では，フレーム長とノードの付マルチホップで相互に通信を行うことの出来る自己組織， 加，削除が生じる場合のネットワーク再構築方法との関
自己環境設定，自己管理の機能を持ったネットワークで 連についても論じる．
ある．メッシュネットワークは，ユビキタス社会における通信インフラストラクチャーとして大きな役割を果た 1.3 研究方法すことが期待されている．また，メッシュネットワーク研究方法について説明する．定式化を提案するために，は 1 つのノードが故障しても代替経路が確保しやすく有 簡単なネットワークトポロジーを作成してそのネットワー線のネットワークに比べて障害に強いという特徴があり， クトポロジーを参考にしながら新たな定式化を提案する．
この点においても注目されている．
さらに整数計画問題として提案した定式をプログラムに現在までメッシュネットワークに関する研究として，ノー おこし，整数計画ソルバー Gurobi Optimizer 4.5.0 を使
ドの電力消費の軽減やパケット送信の遅延の軽減などを 用して解析を行う．メッシュネットワークの最適なスケ目的とした研究が行われてきている [2, 3]．本研究では， ジューリングとその際のフレーム長について調査するた
メッシュネットワークにおける QoS(Quality of Service) めに，様々な環境で数値結果を得る．様々な条件下で得保証の問題に着目する．この問題のために，メッシュネッ られた数値結果を比較するために，数値結果を表にしてトワーク内のフローをいくつかの優先権クラスに分類し， 考察する．メッシュネットワークの自己組織化を調査す
クラスごとの適切な帯域割り当てとパケットスケジュー るために，既存のメッシュネットワークに対して新たなリングを行う手法を考える．問題を数理計画法として定 ノードを付加してネットワークの再構築を行う．新たな式化し，それを解くことにより，クラスごとの適切な帯 ノードを付加する時，メッシュネットワーク内の付加する域割り当てとパケットスケジューリングを決定する．様々 場所でフレーム長にどのように影響するか調査する．まな環境下での数値結果を得て，それらを精査することに た，メッシュネットワーク内のあるノードを削除するとより，提案手法と定式化の有効性について論じる．
きもノードを付加する時と同様に，再構築を行う際のフレーム長への影響を調査する．
1.2 研究目的

1

本研究では，メッシュネットワークとして IEEE802.16 2 モデル化・定式化
Mesh Mode のネットワークを想定する．特にネットワークのトポロジーとして，実用上重要と思われるツリー構造をしたメッシュネットワークを考える．本研究で考えるメッシュネットワークでは，MAC(Medium Access Control)として TDMA(Time Division Multiple Access) 方式が採用されているものとする．本研究では，このようなメッシュネットワークの TDMA 方式におけるノードの最適なスケジューリングとその際のフレーム長について調査する．TDMA においてフレーム長はノードのパケット遅延の上限を決定する非常に重要な要因であるので，フレーム長をいかに低く抑えるかが QoS 保証の観点から非常に図 1 ネットワークトポロジーにおけるツリー図重要なことである．また，メッシュネットワークの重要な機能として自己組織化があるが，このことは新たなノー本研究で使用する簡単なメッシュネットワークトポロ
ドがネットワークに付加されたとき，あるいはネットワージーについて説明し，定義する変数，定式化について説明
クに参加していたノードが削除された際に，ネットワーする．1 つの BS（Base Station）と 9 つの SS(Subscriber
クが自動的にネットワークを再構築することが必要になStations) を用意し，BS を根，SS を葉で構成する図 1 のることを意味する．ネットワークの再構築が行われる際，ようなクラス分けをしてツリー構造で考える．ノード 0 をBS，ノード 1 からノード 9 を SS とする．すべてのノードは必ずノード 0 である BS の葉であるため直接的又は間接的につながっている．間接的に繋がっているノードに移動する場合，段階的にノード間を隣接させることをホップするという．ノードはアクセスポイントで双方向性に無線でつながっていて全 2 重通信である．
2.1

変数の定義

本研究の定式化において使用する各変数の説明をする．
i はあるノードを意味し，ノード i を中心に以下の変数，定式を表現する．図 2 では図 1 のノード 3 をノード i として考える．
N はノードの個数を表す．図 2 では根であるノード 0
図 2 アクセスツリーとその概念を含む N = 9 つまり 10 個のノードの個数を示す．
P はノードのキャパシティを表す．キャパシティが大 2.2 定式化
きければ大きいほど複数のアップリンクトラフィックやダ前節で定義した変数をもとに定式化を行う．式は目的
ウンリンクトラフィックを同時に送受信することができ，関数を表す式 (1) と制約条件を表す式 (2)〜式 (10) の 10
小さければ小さいほど同時に送受信することができなく個の式を挙げる．その後各式の意味をそれぞれ説明する．
なる．
L はノード間のリンク数を表す．図 2 では L の値は 9n ∑K∑である．
min
Ck (xi,k + yi,k )(1)
Ck は定式化した数理計画問題のフレーム長さ K の最i=1 k=1小化を行うための変数で，Ck = (2L)k−1 × k! とする．
s.t.
Ni はノード i から見て子にあたるノードすべてを示す．
ただし孫，孫以下などの間接的な子のノードは含まず，1k−h(i)∑∑ホップで繋がっている．つまり隣接している子ノードを
dj ,xi,k = di +指す．図 2 では Ni はノード 6，7，8 にあたる．
k=1
j∈C(i)
C(i) はノード i から見た子以下すべてのノードを示す．
i = 1, · · · , N(2)
Ni は隣接した子ノードのみを指していたのに比べ，C(i)は隣接していない孫，孫以下にあたるノードも含む．図2 では C(i) はノード 6，7，8，9 にあたる．
K∑∑yi,k = d0i +d0j ,xi,k はノード i が親に情報を送るアップリンクトラフィッ
k=1j∈C(i)ク量を表し，情報を送っているときは xi,k = 1，送って
i = 1, · · · , N(3)
いないときは xi,k = 0 の決定変数である．図 2 ではノード i からノード 1 への上向きの矢印にあたる．
xN |Ni | はノード i がノード i の子から情報を受けるアッ∑∑i,kxi,k +yj,k + yi,k +xl,k ≤ P,プリンクトラフィック量を表す．xi,k と同様に 0 か 1 の値をとる決定変数である．図 2 ではノード 6，7，8 からノード i への上向きの矢印にあたる．
yi,k はノード i が親ノードから情報を受けるダウンリンクトラフィック量を表す．xi,k と同様に 0 か 1 の値をとる決定変数である．図 2 ではノード 1 からノード i への下向きの矢印にあたる．
|N |yj,ki はノード i からノード i の子らに情報を送るダウ
ンリンクトラフィック量を表す．xi,k と同様に 0 か 1 の値をとる決定変数である．図 2 ではノード i からノード 6，7，8 への下向きの矢印にあたる．
di はノード i の BS に要求されている情報量を表す．つまり各ノード i で発生した情報量である．
d0i は di とは逆にノード i が BS に要求している情報量を表す．BS からノード i へ届ける情報量である．
K はフレーム長を表す．
k はフレーム長 K の各スロット位置を表す．

j∈N (i)l=N (i)i = 0, · · · , Nk∑
t=1xi,t −|Ni |
k−1
∑∑(4)

≤ di ,xNi,tl

t=1 l=1

k = 1, · · · , K, i = 1, · · · , Nk∑∑
t=1 j∈N (i)yj,t ≤k−1∑(5)

yj,t ,t=1

i = 1, · · · , N(6)yi,k−1 = 0, k < h(i),i = 1, · · · , N, k = 1, · · · , K(7)

の時と k = m + 1 の時を比較して k = m + 1 の時よりもk = m の方が小さいことを証明する．
(0≤ xi,k ≤1) かつ (0≤ yi,k ≤1) のとき，xi,k = 0, k > K + 1 − h(i),i = 1, · · · , N, k = 1, · · · , K(8)n ∑K∑
i=1 k=1x0,k = 0, k = 1, · · · , K(9)Ck (xi,k + yi,k ) ≤m∑

2LCk

k=1= 2Lm∑

Ck

k=1y0,k = 0, k = 1, · · · , K(10)

ここで Ck = (2L)k−1 × k! を代入する．

mm∑∑∑n ∑K2L
Ck = 2L(2L)k−1 × k!
目的関数 (1) は i=1 k=1 Ck (xi,k + yi,k ) をフレーム
k=1k=1
長 K に注意して最小にする．
m≤m(2L)× m!
制約条件 (2) は BS からノード i とノード i の子 (図 2≤ Cm+1 = (2L)m (m + 1)!
ではノード 6，7，8) に対して要求している情報量の合計はノード i の親 (ノード 1) へのアップリンクトラフィック量と同じ値にならなければならない．また，トラフィック∑n ∑K量がスケジューリング中に収まるようなアップリンクト よって， i=1 k=1 Ck (xi,k + yi,k ) の最小値を求めればよいことがわかる．
ラフィック量を伝達しなければならない．
制約条件 (3) は式 (2) とトラフィックの向きは逆向きだ
3 実験
が式 (2) 同様，ノード i とノード i の子 (図 2 ではノード2 節で提案したネットワークトポロジー，定式化をもと6，7，8) の BS への要求している情報量の合計はノード iの親 (図 2 ではノード 1) からノード i へのダウンリンク に実験を行う．キャパシティP の値を変化させて，フレーム長 K との関係を調べる．その後，ネットワークにノートラフィック量はと等しくなければならない．
制約条件 (4) はノード i において親や子らへのアップリ ドを付加する場合とノードを削除する場合における実験ンクトラフィック量とダウンリンクトラフィック量の合計 を行い，再構築前とのスケジュールのフレーム長にどのはノード i のキャパシティP を超えることができない． ような影響をもたらすか調査する．パラメータは di = 1，
制約条件 (5) はノード i のアップリンクトラフィック量 d0i = 1 という環境下で実験を行う．
において，親から送信したトラフィック量から子から受信 3.1 キャパシティとフレーム長の関係したトラフィック量を引いた，つまりノード i で発生したノードのキャパシティとフレーム長の関係を調べるた
情報量は BS からノード i への要求量以下でなくてはなら
めに，キャパシティP の値を 1 から 1 ずつ増加させる．まない．
た各ノードのキャパシティは一律で変化させるものとす
制約条件 (6) はノード i の親からノード i へのダウンリ
る．表 1 に数値結果を示す．キャパシティの値を 1 から 2ンクトラフィック量はノード i から子らへのダウンリンクトラフィック量の合計以下でなくてはならない．
表 1 キャパシティとフレーム長の関係
制約条件 (7) はスロット k よりも，ノード i から BS へP
12 3 4 5 … 8のホップ数の方が大きい場合，ノード i の親からノード i
K
22
11
8 7 7 … 7へのダウンリンクトラフィック量は 0 でなくてはならない．
制約条件 (8) はスロット k が K + 1 − h(i) より大きい
とき，ノード i からのダウンリンクトラフィックは 0 でな に変化させるとフレーム長は約半分になったが，その後キャパシティの値を 3，4 と変化させてもフレーム長の変くてはならない．
制約条件 (9) はノード 0 すなわち BS は根であるため， 化は小さくなり，キャパシティの値を 4 から増加させてノード 0 からのアップリンクトラフィックは常に 0 でな もフレーム長に変化は見られなくなった．本研究のネットワークトポロジーでは，あるノードの子の数は 1〜3 個くてはならない．
制約条件 (10) はノード 0 すなわち BS は根であるため 程度であるが，1 つのノードに対して子の数が多いネット
制約式 (9) 同様，ノード 0 へのダウンリンクトラフィック ワークトポロジーになるほど，キャパシティの値が求められる．このネットワークトポロジーで P = 1 から P = 2も常に 0 でなくてはならない．に変更したときにフレーム長が大きく変化したため，以2.3 目的関数の最小化からスケジュールを得る証明
下の実験ではキャパシティP = 2 に設定して実験を行う．
2.2 節で定式化した数理計画問題の目的関数の最小化を3.2 ノードの付加示して，最小のスケジューリングを求める．変数 L はノーノードを新しく付加する実験について説明する．
ドのリンク数を表す．図 2 のモデルではノード間の繋がりを示す線は 9 本なので L = 9 である．スロットが k = m

図 4 に削除するノードを点線のノードとして示す．削除するノードは 1 つで各ノードを順に削除していきフレーム長にどのような影響があるか調査する．削除した際に，削除されたノードの子ノードは，削除されたノードの親ノードに直接再接続すると考える．ただしノードを付加する場合と同様に，ツリーの構造上同じになるものは一方の場合のみ考えるものとする．例えばノード 1 を削除する場合において，ノード 0 とノード 3 を接続すると考える．表 3 に数値結果を示す．ノードを付加したときと同
表 3 ノードの削除
削除するノード 1
25
K
9 11 11

図 3 付加するノードの位置を示す図
図 3 に付加するノード (ノード 10) の場所を点線のノードとして示す．ノードの付加する場所は各ノードの下に子ノードがある場合は，その子ノードに並列になるように付加する．ただし，ツリーの構造上同じになるものは片方の場合のみ考えるものとする．例えば，ノード 4 の子として付加する場合とノード 5 の子として付加する場合は同じ構造となる．数値結果を表 2 に示す．ノードをツ表 2 ノードの付加
0123411 13 11 13 117989

様にツリーの左側のノードを削除した時に限り，フレーム長が変化した．このことからネットワークにおける BSからのホップ数とフレーム長の関係が再確認できた．本研
究では削除したノードの子のノードを削除した親のノードに接続しているため，BS からの最大ホップ数に影響力が大きいノードを削除するとフレーム長が短くなると言える．

4

まとめ

本研究では，メッシュネットワークとして IEEE 802.16
Mesh Mode のネットワークを想定し，そのネットワークでの TDMA スケジューリング問題を考えた．TDMA スリー上の左側 (ノード 1 側) に付加する場合と右側 (ノー ケジューリング問題を整数計画問題として定式化し，そのド 2 側) に付加する場合で結果が異なる結果となった．こ 整数計画問題をソルバーを利用して解くことにより，フれはツリーの左側はネットワーク上の BS からのホップ数 レーム長を最小とする TDMA スケジューリングを得るこに影響を与えているため，フレーム長の値が大きくなっ とができた．数値結果から，フレーム長とキャパシティ，たと考えられる．逆に BS からのホップ数に影響を与え ノード数，情報要求量，ネットワークトポロジーとの関ていない左側にノードを付加する場合はフレーム長に変 係を調査した．
今後の課題として，ネットワークトポロジーについて化がないので，BS からのホップ数が多いネットワークにノードを増やすことにより複雑なネットワークトポロジーなればなるほど，フレーム長は大きくなると考えられる．
ホップ数の少ない，つまりツリーの深さが浅い構造のネッ で実験しフレーム長を調査する．また，複数のノードをトワークがフレーム長を短くすることができると言える． 付加，削除する場合の実験もする必要がある．さらに各トラフィックに対して優先度を与えていないので優先度3.3 ノードの削除に関してネットワークアルゴリズムを考え，新たな定式ノードを削除する実験について説明する．
化を加え実験する．
親のノード
K

613

813

913

参考文献
[1] J. Chen, C. Chi, Q. Guo, “A bandwidth allocation model with high concurrence rate IEEE802.16
mesh mode,” Proc. of Asia-Pacific Conference onCommunications (APCC 2005), 2005.
[2] G. Aggelou, Wireless mesh networking, McGrawHill, 2009.
[3] E. Hossain and K. K. Leung, Wireless mesh netoworks, Springer, 2008.

図 4 削除するノードを示す図