非線形最適化理論を援用する分散通信ネットワークの新規な制御則の開拓
代表研究者

田中 久陽

電気通信大学電気通信学部准教授

1 目的と成果の概要
現実的な分散通信ネットワークにおいて, トラフィックの輻輳（遅延）時には, 諸々の特性がベキ分布を示すことが多い. この性質に関する研究の多くは，シミュレーション解析, あるいは従来のトラフィックモデルによるラフな近似のレベルにとどまり, 本質的な理解がいまだ不足している．本研究は, この分散ネットワークにみられるベキ分布の存在を明確にし, これを推定する効率的アルゴリズムの開拓を行なった. その上で次のステップとして, このような輻輳のもとでも QoS 最適化を可能とする基礎理論の構築を目指してきた．この目標に向け, 具体的には次の相互に関連する 2 つの予備的成果が得られた.
(i) 与えられたネットワークトポロジと，その構成端末の（IEEE 802.11 プロトコルに基づく）通信の性質から，渋滞時のベキ分布の存在を明らかにし, ベキ分布の指数（ベキ指数）を求める枠組みの開拓. （2章）
(ii) 実際のベキ分布の生成過程では, 充分なデータ数が集まっていない段階でも, ベキ指数を求める必要がある. このためベキ分布の生成過程の簡略化モデルでの Tsallis エントロピーの示す挙動に注目し,ベキ指数を推定する有効なアルゴリズムの提案. （3 章）
これらにより, トラフィックの輻輳下でのベキ分布に対しある程度の特徴付けと準備が得られた. 以上が単年度内の主な成果であるが, 次の段階として, 上記(ii) で用いられたモデルを実際の（IEEE 802.11 等の）プロトコルの詳細に対応付けることが必要である. これが整備されれば, 通信の公平性（フェアネス）などの種々の目的関数を最適化する個々の端末の制御アルゴリズムを提案し, シミュレーションにより従来ネットワークの QoS と比較検討を行うところまで到達可能になると考えられる.

2 輻輳時前後のベキ分布の指数の変化
本章では, 802.11 のアドホックモードによる CSMA/CA を用いた小規模アドホックネットワークを対象に,ベキ分布の存在を明らかにするための枠組みを整備する．結果として, ベキ分析の存在が明らかとなり, 輻輳の前後でベキ指数の値に明らかな変化が生じることが確認された.
2-1 問題設定と結果の概要
アドホックネットワークとは, 基地局を介さず，端末同士が直接通信する自律分散無線ネットワークであり, 山間部，地下などの基地局が建てられない場合等の様々な場所でのネットワークの構築が容易となるメリットがある. IEEE802.11 は, アドホックネットワークを構築する際, 最も広く用いられる MAC プロトコルであるが, アドホックネットワークのように自律分散性をもたせる場合, これまでになかった問題が生じてきている. そのひとつとして, パケットの同時送信によるパケットの衝突, それによるトラフィックの輻輳が挙げられる.以下では, その具体例を, 最も広く用いられている CSMA/CA による衝突回避プロトコルのもとで検討する. まず各端末は送信を行う前に，周辺の通信の有無を確認（キャリアセンス）する．その際, ランダムなバックオフを使用し, その値を初期範囲（[0,CWmin]）から決定する（図 1(a)）．もしパケッ
トの衝突が発生した際は, バックオフの範囲を 2 倍にして再送信（CWmax に達した場合は維持）する（図 1(b)）．

1（公財）電気通信普及財団 研究調査助成報告書 No.31 2016

図 1(a)

図 1(b)

図 2 に示すように, この CSMA/CA のランダムなバックオフによって, ネットワーク内に短期間の通信の不公平性が発生する．短期間の通信の不公平性の原因は, 一つの端末が連続的に送信を行い帯域を占有することによるが, 特に図 2 の隠れ端末の存在するマルチホップネットワークの場合には, 端末 0→端末 2，逆に端末 2→端末 0 のいずれかの送信のみが連続して行われる．このネットワークに関しては, 先行研究として[1]があるものの, ベキ分布の特徴付けには至っていない．

図2

図3

短期間の通信の不公平性が発生すると,動画や音声のように即時性の必要なアプリの QoS を低下するため,（短期間の）フェアネスの保証は重要な課題の一つである．従来研究における 802.11 無線ネットワークのフェアネスの議論は, ネットワーク内の特定の端末に注目する傾向があり, 特に理論研究は小規模ネットワー
クの特定の端末にのみ注目したものがほとんどである[2]. 一方, ネットワーク全体のフェアネスに注目したものは, シミュレーションによる解析が少数存在しているのみである[3]. すなわち, ネットワーク全体としての通信のフェアネスを理論的に扱う手法が未開拓であるといえる.
以下では, 成果 (i)として, IEEE 802.11 プロトコルに基づく無線ネットワークの渋滞時のベキ分布の情報を正確に把握する枠組み・アルゴリズム構築の概要について述べる. この課題において, まず各端末に一定時間に到着するパケット数の分布を系統的に解析した. その方法として, 複雑ネットワークにおけるMeloni らによる Random Diffusion (RD) モデルの解析手法を応用した [4]. その結果, ベキ分布の存在そのものは示すことができたが, RD モデルの結果が示す, 輻輳時の前後でのベキ指数のクリアな転移が見られなかった. これは本研究の対象とする現実的なネットワークが, RD モデルの簡素化のための仮定を満たさないためと考えられる. そこで, 一定時間に到着するパケット数ではなく, 一定時間に注目するリンクを通過するパケットの「方向」の分布に注目した. その根拠は, この量がパケット同士が衝突しないというRD モデルの仮定と直接に対立しないことによる. また, 上記の通過するパケットの「方向」の分布は, 各端末の通信の公平性（フェアネス）指標にもなっており合理的である.
以上の準備のもとで, 2 パターンの小規模なネットワークに対し, 各端末に生じる送信パケット数と, 注目するリンク上を通過するパケットの方向の分布は, 輻輳の前後でクリアなベキ指数の変化を示すことが明らかとなった.
2-2 想定するネットワークと解析手法
以下で対象とするシングルネットワークとマルチホップネットワークの例をそれぞれ図 4, 5 に示す.

2（公財）電気通信普及財団 研究調査助成報告書 No.31 2016

図4

図5
これらのネットワークは最も簡単であるが, 自明ではない挙動を示すものである. 以下では, 各端末に到達するパケット数のゆらぎ, 及びネットワーク内の特定のリンクに注目した時のパケットの通過方向の分布が, 各端末に生じる送信パケット生成レートの値によりどのように決定されるかを系統的なネットワークシミュレーションにより解析する. 解析手法として, Randam Diffusion モデル[4]における枠組みを応用する. Randam Diffusion (RD) モデルとは, Meloni らによって提案された, 複雑ネットワーク上のパケット送信の確率モデルである. その際, 簡単化のために次の仮定(a), (b)がおかれている. (a)パケット同士の衝突が起こらない. (b)個々のパケットはランダムウォークに従いノード（端末）間を移動する.
その結果, 個々のパケットの到着タイミングはポアソン分布に従うことになる. 図 6 のように観測時間𝑇を一定長の time window で区切り, 各 time window 中に端末𝑖へと到達するパケットの に注目する.

図6

図7

3
（公財）電気通信普及財団 研究調査助成報告書 No.31 2016

Random Diffusion モデル[4]におけるシミュレーション解析の結果,の平均と のゆらぎの関係式はネットワーク構造と無関係に,の関係を満たすことが示されている.
さらに, 観測時間内のネットワーク全体に存在したパケット数定すると, その幅が 0 に近づくとが, ある幅で一様に分布していたと仮に漸近し, 逆に幅を（可能な限り）大きくするとに漸近することが解析的に導かれている.
2-3 シングルホップネットワークの場合の解析結果
以下では, この RD の枠組みを, アドホックネットワークにおけるベキ分析の特徴付けに応用する. まず,図４のシングルホップネットワークにおいて, 以下の設定でシミュレーションを行った.
３台の端末は互いに通信可能であり, 各端末には一定間隔で送信パケットが生成されるとする. このパケットは他の２台の端末へ順番に送信され, パケットの中継送信はないものとする. この際, 通信路容量から, パケット生成レート 68.4pkts/s でスループットが飽和することが分かっている.
まず RD モデル[4]の枠組みに従って, 端末に到達するパケット数のゆらぎを解析した. 方法としては各time window 中に図 4 の端末 0 に到達するパケット数 を測定しそのゆらぎを算出した.

その際, time window を 1s, 1 回の観測時間を 100s とし, 試行回数を 1000 回として, ゆらぎの平均値を求めた.
また同時に, time window（1s）毎にネットワーク全体に存在するパケット数𝑤を測定し, 観測時間にわたり𝑤の値の分布を求めた.
その結果, 図 8, 図 9 のように, 与えられたパケット生成レートによって, のゆらぎと𝑤の分布の形状が変化することが明らかとなった.

図8

図9

すなわち, パケット生成レートが低いときは, 𝑤は小さな値の周りに集中する分布となり, ゆらぎも小さな値となる. 逆にパケット生成レートが高くなるにつれ, 𝑤の分布は幅広くなり, ゆらぎも増加し, スループットの上限のところで一定値に飽和する.

4（公財）電気通信普及財団 研究調査助成報告書 No.31 2016

図 10

図 11

上記の𝑤の分布の形状の変化は, 図 9，10 の図中の色分けデータから明らかに, ある生成レートの値を境に急に現れる. 一方ゆらぎ の増加傾向（ベキ指数）は図 11 のデータが示すように, これもある生成レートの値を境に切り替わるように観測される. しかし, RD モデルから予想されるクリアなベキ指数の転移（図 7）は観測されていない. 考えられる理由として, ここで対象とするネットワークはパケット間のコリジョンが頻繁に生じ, RD モデルのコリジョンが生じないという仮定を破っていることが挙げられる. そこで, ゆらぎを観測する指標として到着パケット数以外のもので, パケットのコリジョンの影響を直接受けないものを検討した. 一つの候補として, 特定のリンクに注目し, リンク上のパケットの流れる「方向」の分布を指標とすることが合理的と考えられる. すなわち, ここで対象とするネットワークは対称的な構造なので, 通信がフェアに行われていれば, 注目するリンクを流れるパケットの向きはほぼ交互に分布することが予想される.
逆に, トラフィックのゆらぎが増大すれば, パケットの向きにもゆらぎが増大すると考えられる. ここで,リンク 0 を通過するパケットの向きにより, 1 次元座標系を±1 移動する仮想点を導入する. すなわち, 図のようにパケットが端末 0 → 端末 1 と移動したとき＋1 とカウントし, 端末 1 → 端末 0 と移動したとき －1 とカウントする.
ここで±1 移動する確率が, それぞれ同一の 1/2 である場合, これは単純ランダムウォークに他ならない.

図 12以下に, ゆらぎの測定方法を記載する. まず, 図 12 の端末 0 と 1 の間のリンクをリンク 0 とする. このリンク 0 上をパケットが 100 回通過する毎に, 上記で導入した仮想点の位置を測定し,のゆらぎを算出する. 但し, 通過パケット数が 10000 個となる時間を 1 個の観測時間とし, この観測回数を 1000 回として, ゆらぎの平均を求めた. また, 同時にリンク 0 上をパケットが 100 回通過する毎に，𝑤 を測定し, 𝑤の分布も求めた. 以上の測定の結果, 図 13,14,15,16 のように, 𝑤の分布とゆらぎの増加傾向, さらにベキ指数のクリアな転移が明らかとなった.
図 13 の図中の𝑤の分布の形状は, 先の図 8 のものと同様の傾向を示している. 一応, 図 13 における, ゆらぎの増加傾向は, （図 8 と比べ）きれいなベキ則を示し, RD モデルから予想されるベキ指数の転移もクリアである.

5（公財）電気通信普及財団 研究調査助成報告書 No.31 2016

図 14

図 13

その理由として, 図 8 の場合にはパケットコリジョンの影響が無視できなかったが, 図 13 の場合には, 直接影響が生じていないためと考えられている. また, 図 14, 15 内の𝑤の分布の形状の転移するパケット生成レートの値は, 同じ図中のベキ指数の転移点とほぼ一致しており, RD モデルの枠組みと整合していることが分かる.

図 16

図 15

また, 上記の送信パケットの方向の時間変化による仮想点の軌跡の詳細を表示したものが, 以下の図17,18,19,20 である.

図 17

図 18

6（公財）電気通信普及財団 研究調査助成報告書 No.31 2016

図 19
図 20
これらの結果から明らかに, パケット生成レートが高くなると同方向へ連続してパケットが移動する頻度が増え, 各端末の通信の公平性（フェアネス）が損なわれていることが分かる. 以上のトラフィックの輻輳
時に, ゆらぎの示すベキ分布そのものは避け得ないとしても, そのベキ指数を可能な限り小さく抑えるためのプロトコル上の工夫が必要である. このような工夫は予備的結果から, ある程度実行可能であることがわかったが, ここでは割愛する.
2-4 マルチホップネットワークの場合の解析結果
以上は図 4 の 3 端末からなるシグナルホップのネットワークを対象とした結果である. 以下では, 図 5 の4 端末からなるマルチホップネットワーク対象として結果を説明する.
このマルチホップネットワークのためのネットワークシミュレーションの設定は, 先行研究の[5]に従った. 対象となるネットワークの詳細は以下の通りである.
4 台の端末を一列に配置し, 端末 0,3 は互いに隠れ端末となるようにする. ここで, 端末 0,3 は一定間隔で送信パケットを生成し, 端末 0(3)での生成パケットは, それぞれ端末 1,2 を中継して端末 3(0)へ到達するように設定する. 図 4 のネットワークと同様に, 通信路容量より生成パケットレートが 1.8Mbps でスループット飽和することが分かっている.
以下では, まず, RD モデル[4]に従い, 端末に到達するパケット数のゆらぎを解析した. 方法として各time window 中に図 5 の端末 に到達するパケット数 を測定し，そのゆらぎを算出した.

その際, time window を 19.4ms, 1 回の観測時間を 1.94s とし, 試行回数を 1000 回として, ゆらぎの平均値を求めた.
また同時に,time window（19.4ms）毎にネットワーク全体に存在するパケット数全体に存在するパケット数 を測定し，観測１求めた. その結果，図 21, 22 の 2 となった.

図 21
図 22
これらの結果は, 図 4 のシングルホップネットワークの場合と, ほぼ同様の傾向を示している. しかし,先の図 8, 9 の結果と同じく RD モデルの予想(図 7)と異なり, ベキ指数の転移(図 8,9)はクリアでなかった.
そこで, 先の図に以下と同様の方法により, 特定のリンク上でのパケットの方向の分布に注目した. 注目するリンクを, 図 5 のリンク 0, リンク 1 とし, 得られた結果を, 図 23, 24, 25, 26 に示す.

7（公財）電気通信普及財団 研究調査助成報告書 No.31 2016

以上の結果から, 図 4 のシングルホップネットワークの場合と同じく, ベキ指数のクリアな転移が得られ,RD モデルの結果と整合することが確認された.
以上をまとめると、図 4, 5 のネットワーク構成のいずれにおいても次の性質が成り立つことが判明した.
(1)IEEE802.11 ベースのアドホックネットワークにおいて, ベキ分布を示す諸量はネットワーク全体に存在するパケット数の分布の形状の変化に伴い, ベキ指数を転移する．
(2)各端末のパケット生成レートを上昇させると，(バックオフのランダム性を反映し)リンク上のパケット移動方向が大きくゆらぎ, ある点を超えると各端末の通信のフェアネスを破る.
Random Diffusion モデルの解析方法を基に，端末に到達するパケット数のゆらぎと，リンクに注目した通信のフェアネスを示した．

3 Tsallis エントロピーから見たベキ分布生成過程一方, 成果 (ii)として, 渋滞時のベキ分布の指数（ベキ指数）を推定する新規な枠組み・アルゴリズム構
築について述べる. この課題においては, いきなり無線ネットワークに対してアプローチするのでなく,まず簡素なモデルから生成されるベキ分布を対象に基礎を構築する方針を採用した. その方法として, ベキ分布と密接に関係する Tsallis エントロピーを導入した. その結果, ベキ分布の生成過程での Tsallisエントロピーの示す挙動に注目することにより, ベキ指数を推定する有効なアルゴリズムの提案に至った.
このアルゴリズムは特許出願の予定であるため, ここでは内容の詳細を割愛する.
3-1 Tsallis エントロピーの定義と性質
まず Tsallis エントロピーの概要を以下で説明する.

を確率変数,を確率密度関数(PDF)とする.

こ の と き , Tsallis エ ン ト ロ ピ ー は 次 の 汎 関 数を示し,従来研究において,られている. この指数により与えられる. 但しは通常 1 より大きな値のパラメーターである.

を最大とする密度関数は,が十分大きい領域でに漸近することが知を とおけば, 前出のベキ指数 が Tsallis エントロピーと何らかの関係を持つことを想像するのは自然である.
一方で, 本研究の成果の一つとして, Tsallis エントロピーの最大化の問題を, 非線形な制約をもつ最適化問題と見ることが可能となった. その骨子は次の通りである.
本来は, 目的関数をを 2 つの制約条件およびのもとで最大化する問題である.
ところが, 非線形制約条件にラグランジェの未定定数を乗じることにより,約下で, 新たな目的関数の制を最大化する問題と等価になる. ここで, ヘ8（公財）電気通信普及財団 研究調査助成報告書 No.31 2016

（但し,ルダーの不等式：となり,のときのみ等号成立）を用いると,を最大とするは次を満たすことが分かる.

. このことより, Tsallis エントロピー最大化の問題が本質的にヘルダーの不等式の構造を反映していることが判明した.
3-2 解析結果
以上の結果より, 最大化する確率密度関数は, ヘルダーの不等式の上界から決まり, 唯一存在することが分かった. この密度関数は, 分布の裾野においてベキ分布を示すことは先に述べたとおりである. したがって, ベキ分布を生成するそのシステムは, 定常状態において Tsallis エントロピーを最大に（近いところに）している可能性がある. さらにいえば, 定常状態へ向かう過渡状態において, Tsallis エントロピーは時間とともに単調増加している可能性もある. この仮説と検証するために, 以下の数値実験を行った.
その際用いたモデルは以下の離散時間ランダム乗算系である. [7]
但し,は時刻 でのシステム変数,はそれぞれ, 乗法ノイズ, 加法ノイズであり, その分布関数が与えられているとする. このミニマルモデルにおいて, 例えば,として, それぞれが 2 章で議論したパケットの流れる向きに対応すると解釈することが可能である. （もちろん,の分布関数が, 現実のネットワークでどのように定まるかを議論する余地がある. ）以上のシステムにおいて, Tsallis エントロピーの時間発展を, 複数(10 点)の初期条件から, 長時間(ステップ)にわたり求める結果を図 23 に示す.

図 23
この結果の示すように, システムの時間経過にともない, Tsallis エントロピーは常に比較的短時間で急増し, その後一定値に漸近することが分かる.
実は, この性質は, ベキ分布の指数（ベキ指数）を推定するための有効なヒントとなる. その結果, ベキ指数の効率的推定アルゴリズムが得られるが, これは特許出願の予定であり, その内容は割愛する.

4 今後の課題と展望
以上の成果により, トラフィックの輻輳下でのベキ分布に対しある程度の特徴付けと準備が得られた.
これは単年度内の成果であるが, 次の段階として, 例えば上記(ii) で用いられたモデルを実際の（IEEE9（公財）電気通信普及財団 研究調査助成報告書 No.31 2016

802.11 等の）プロトコルの詳細に対応付けることが必要である. この対応付けが整備されれば, 通信の公平性（フェアネス）などの種々の目的関数を最適化する，個々の端末の制御アルゴリズムを提案し, シミュレーションにより従来ネットワークの QoS と比較検討を行うところまで到達可能になると考えられ, 今後の課題として残された.

【参考文献】[1] 眞田耕輔, 関屋大雄, 小室信喜, 阪田史郎, “IEEE 802.11 無線マルチホップネットワークにおける連成効果とその解析,”
信学技報, vol.111, no.8, NS2011-9, pp.49–54, Apr. 2011.
[2] J. Tang, Y. Cheng, and W. Zhuang, ``An Analytical Approach to Real-Time Misbehavior Detection
in IEEE 802.11 Based Wireless Networks,'‘ Proceedings of IEEE INFOCOM 2011, pp. 1638-1646,
2011.
[3] O. Dousse, P. Thiran, and M. Durvy, “On the fairness of large CSMA networks,” IEEE J. Sel.
Areas Commun., vol. 27, no. 7, pp. 1093–1104, Sep. 2009.
[4] S. Meloni, J. Gomez-Gardenes, V. Latora, and Y. Moreno, ``Scaling Breakdown in Flow
Fluctuations on Complex Networks,'' Phys. Rev. Lett. 100, 208701, 2008.
[5] 稲葉雅彦, 冨田佳宏, 松本真沙樹, 関屋大雄, 谷萩隆嗣, 阪田史郎, 柳生健吾, “無線マルチホップネ
ットワークにおける最大スループットに関する解析及び実験,”信学技報, vol.107, no.402, RCS2007-121,pp.55–60, Dec. 2007.
[6] Hisa-Aki Tanaka, Isao Nishikawa, Jürgen Kurths, Yifei Chen, and Istvan Z. Kiss,"Optimal Synchronization of Oscillatory Chemical Reactions with Complex Pulse, Square, andSmooth Waveforms Signals Maximizes Tsallis Entropy," Europhysics Letters, vol. 111, no. 5,50007, Sep. 2015[7] H. Takayasu, A. -H. Sato, and M. Takayasu, " Stable Infinite Variance Fluctuations in Randomly
Amplified Langevin Systems, " Phys. Rev. Lett. 79, 966〈発 表題

名Better Clock Synchronization From
Simultaneous Two Skew Estimations,Optimal Synchronization of Oscillatory
Chemical Reactions with Complex Pulse,
Square, and Smooth Waveforms Signals
Maximizes Tsallis Entropy,
非線形問題とヘルダーの不等式

Tsallis エントロピー最大化問題の新解法--制限された台を持つ一次元分布の場合と二次元分布の場合-Fundamental Limit of Synchronization in
Weakly Forced Nonlinear Oscillators,

Nonstandard Scaling Law of Fluctuationsin Globally Coupled Oscillator Systems ofFinite Size,

資料〉

掲載誌・学会名等

発表年月

Nonlinear Theory and Its
Applications (NOLTA) , IEICE,
vol.E 7-N, no. 4,
Europhysics Letters, vol. 111, no.
5, 500072016 年 1 月

電子情報通信学会 基礎・境界ソサ
イ エ テ ィ Fundamentals Review,
vol. 9, no. 3, pp. 219--228
電子情報通信学会 複雑コミュニ
ケーションサイエンス研究会(CCS)
国 際会議 Dynamics of Coupled
Oscillators: 40 years of theKuramoto
Model(Dresden,Germany)
国 際会議 Dynamics of CoupledOscillators: 40 years of theKuramoto
Model(Dresden,Germany)

2016 年 1 月

2015 年 9 月

2016 年 3 月

2015 年 7 月

2015 年 7 月

10（公財）電気通信普及財団 研究調査助成報告書 No.31 2016