A08: 動的な構造をもつネットワーク上の資源割当て問題の研究

Similar presentations


Presentation on theme: "A08: 動的な構造をもつネットワーク上の資源割当て問題の研究"— Presentation transcript:

1 A08: 動的な構造をもつネットワーク上の資源割当て問題の研究
藤田 聡  中野浩嗣  森本康彦 (広島大学)

2 研究組織 藤田 聡(広島大) 中野浩嗣(広島大) 森本康彦(広島大) ネットワーク上のサーバ配置問題 オンラインアルゴリズム
無線ネットワーク上のアルゴリズム 無線ネットワーク上の省電力ルーティング 森本康彦(広島大) センサーネットワーク上のデータマイニング

3 成果の概要 支配集合に基づく資源割当て問題 ルーティングにおける資源割当て サービスの安定性を保証するための要件
安定性をパラメータ化して必要なコストを評価 連結支配集合分割問題(→センサーネット) ルーティングにおける資源割当て 無線ネットワークにおけるチャネル割り当て ルーティング性能をいかにして保つか(ホップ数, QoS, 低電力) 輻輳制御(AIMD, Active Queue管理) マルチパスルーティング

4 【動的な構造をもつネットワークへの適用】
支配集合に基づく資源割当て問題 すべての頂点に対して均一なサービスを提供 支配集合がサーバ集合に対応 さまざまなバリエーションが存在 連結支配集合:センサーネットワークのバックボーン 支配集合分割:負荷分散、省電力化 r-configuration:ファイル配置問題 最大極小支配集合:用意すべきサーバ数の上限 【動的な構造をもつネットワークへの適用】 支配集合間の遷移可能性 (PDCAT’04, ISAAC’05) 欠陥を許した支配集合分割

5 支配集合間の遷移 支配集合の集合D’⊆D(G)は、D’中の任意の集合間で互いに遷移可能なとき、相互遷移可能であるという a b d c

6 主要な結果 (ISAAC’05) n頂点のグラフのクラスCnを考える
Cnに含まれる任意のグラフ上で相互遷移可能性を保証するような支配集合サイズの上界をg(n)とし、 相互遷移可能ではないグラフがCn中に存在するような支配集合サイズの下界をf(n)とする 木(tree)のクラスに対して g(n) = f(n)+1 = ceil((n-1)/2) ハミルトングラフのクラスに対して g(n) = f(n)+1 = ceil((n+1)/3)-1

7 支配数がceil((n-1)/2)になるグラフの例
木に関する証明の概要 十分性は、根の方向に向けて支配頂点を繰り返し遷移させていくことで証明できる 任意のグラフの支配数は葉に隣接している頂点数以上である 支配数がceil((n-1)/2)になるグラフの例

8 ハミルトングラフG ハミルトングラフG=(V,E)のハミルトン閉路Rを固定する
ring edge ハミルトングラフG=(V,E)のハミルトン閉路Rを固定する グラフGのサイズceil((n+1)/3)の支配集合S⊆V を考える Gからchord edgeを繰り返し除去しながら、SをRの支配集合に遷移させていく   Gがサイクルのとき、サイズceil((n+1)/3)の支配集合は相互遷移可能 chord edge 9 10 8 11 7 6 1 5 2 4 3 Graph G

9 Step 1: 冗長な辺の除去 規則1: もし除去によって支配集合であることが崩れなければ、そのchord edgeを除去
9 10 8 11 7 規則1をそれ以上適用できなくなるまで繰り返し適用 ⇒Gと同一の支配集合Sをもつ部分グラフG’ が得られる G’の任意のchord edgeでは、いっぽうの端点がSに属し、もういっぽうの端点はちょうどひとつのchord edgeと接続している 6 1 5 2 4 3 Graph G’

10 Step 2: 森への分割 Chord edgeで支配される頂点に接続するすべてのring edgeを除去 G”は森である
すべての葉はV-Sの要素であり、次数3以上の頂点はすべてSの要素である |S| ≧ ceil((n+1)/3)より、森の中には少なくともひとつの木Tが存在し、その木の中の支配集合数が頂点数の1/3を上回っている 9 10 8 T中の支配頂点をうまく遷移させて、Tに接続するchord edgeが取り除けるようにできる 同様の処理をすべてのchord edgeが 除去されるまで繰り返せばOK 11 7 6 1 5 2 4 3 Graph G”

11 欠陥のある支配集合分割 支配集合分割C ={C1,C2,…,Ck} 各頂点を支配する集合数をkからk-dに減らす
各Ciは支配集合 各頂点は、すべてのCiによって支配されている 各頂点を支配する集合数をkからk-dに減らす 点彩色で類似の概念はすでにある 動的な環境下で支配する集合数が一時的に減る状況をモデル化(⇒ディペンダビリティの尺度) パラメータdの値によって計算複雑度はどのように変化するか 動的な変化が起こった際にdを低く抑える方法は?

12 キュービックグラフの場合 d (許される欠陥の数) 1 2 3 4 5 k (分割のサイズ) P NP 6 7 8 9

13 ルーティングにおける資源割当て アドホックネットワーク QoSルーティング マルチパスルーティング 無線LANにおける通信機会割当て
ランキングアルゴリズム、チャネル割り当て QoSルーティング パス選択問題 (ICIS’05) 輻輳制御問題 (ICON’06, PDPTA’07) マルチパスルーティング 耐故障性、通信帯域の確保 (PDCS’06) 無線LANにおける通信機会割当て ビン詰め問題の一種 (PDCAT’06)

14 無線ネットワーク上でのランキング n個の無線端末がキーを1個ずつもつ 各キーのランク(何番目に小さい値か)を求める
32 41 85 57 29 各キーのランク(何番目に小さい値か)を求める ソーティングと本質的に同じ

15 通信チャネルが1つのときの 自明な時間最適アルゴリズム
32 各無線端末がキーを順にブロードキャスト 32 41 85 57 29 各端末は受信したキーと自分のキーを比較し,自分より小さいキーの個数をカウント 自分より小さいキーの個数+1がランクと一致 アルゴリズムは時間最適:自明な下界Ω(n)時間と一致 (各キーは少なくとも1回は送信される必要があるので) 欠点: 各端末はO(n)回の受信動作を行うので受信による消費電力が大きい

16 通信チャネルが1つのときの自明な 消費電力最適アルゴリズム
アイデア:並列ソーティングネットワークを無線ネットワークでシミュレート 32 41 85 57 29 比較交換器 並列ソーティングネットワークの既知の結果を用いる  O(n log n)個の比較交換器でソーティングが行える 比較交換を通信チャネル上で行うと  O(n log n)時間でソーティングが行える. 利点: 比較交換に関係ない無線端末は送受信を  行わなくてよいので,各無線端末が行う送受信  動作はO(log n)回 欠点: 時間最適でない.(下界はΩ(n)) 29 32 41 57 85 問題: O(n)時間,O(log n)送受信動作の時間最適,消費電力最適 ランキングアルゴリズムは作れるか?

17 マルチチャネルの場合 問題: O(n/k)時間,O(log n)送受信動作のランキングアルゴリズムは存在するか?
マルチチャネル無線ネットワークでの時間最適,消費電力最適なランキングを考える. 32 57 マルチチャネル:複数の通信チャネルを使って同時に通信が行える 32 41 85 57 29 k個の通信チャネルを用いる場合 計算時間の自明な下界: Ω(n/k) (各キーは少なくとも1回送信する必要があるので) 各送受信回数の下界: 通信チャネル数に関係なくΩ(log n) 問題: O(n/k)時間,O(log n)送受信動作のランキングアルゴリズムは存在するか? 決定的手法ではむずかしそう → 確率的手法を用いる

18 確率的ランキングアルゴリズム < < < < < < アイデア:ランダムサンプリング
1. 約n/log n個の無線端末をランダムに選ぶ 2. 選んだ無線端末だけでランキングし,ランキング結果から,約n/(log n)2個のキー を選ぶ.選んだキーをピボットとして用い,全ての無線端末をグループに分割. 各グループはほぼ等しく平均(log n)2個の端末をもつ. 3.グループ内でランキングし,全体のランキングを求める 1≦k≦n/log nのとき,少なくとも1-n-1の確率で,O(n/k)時間, O(log n)送受信回数で,ランキングを行うことができる. 結果

19 転置グラフ上の点素なパス 転置(transposition)グラフ:Cayleyグラフの一種 最大フローによる求解:
次元nのとき、次数がd=n(n-1)/2 star graphやpancake graphに比べて、選ぶべきパスの数が大きい(つまり難しい) 最大フローによる求解: 頂点数に関して多項式時間 次数に関して多項式時間のアルゴリズムを求めたい 提案手法の実行時間は、次数dに対してO(d2.5) マッチングに要する時間が支配的(Hopcroft-Karp) 得られるパスの長さは、 n≧7のとき、同じ目的頂点までの最短パスの長さよりも高々14長い

20 4-TG 長さ2のsuffixが同一である頂点をまとめる→vertical cluster
1234 4132 2134 1432 2314 1342 3214 3142 3124 3412 1324 4312 長さ2のsuffixが同一である頂点をまとめる→vertical cluster Vertical cluster全体の集合をTとする(|T| = 2|D|) 4231 4123 2431 1423 2341 1243 3241 2143 3421 2413 4321 4213

21 基本アイデア D中の頂点をT 中のvertical clusterに単射 TはDの2倍の要素をもつ
First Part (Length 1 or 2) D中の頂点をT 中のvertical clusterに単射 TはDの2倍の要素をもつ 異なるsuffixの数はn(n-1) 各パスに別々のvertical clusterを通過させることで互いに素なパスを実現 問題は、前後の部分をどううまく実現するか Horizontal clusterという考え方を用いる(class) Second Part Third Part 異なるvertical clusterは異なる長さ2のsuffixをもつため、頂点を共有しない

22 目的頂点のクラス替え すべての目的頂点が異なるクラスに属していれば、うまく接続できる
そうでない場合は、適切な中間頂点を入れて、クラスの変換を行う 中間頂点の集合をI (⊂ Vn)とする: 1) 集合Iの頂点は異なるクラスに属している 2) DとIはマッチング辺たちによって結ばれている(single hop) 3) DはソースからI中の各頂点を結ぶパス集合と互いに素 そのような頂点集合Iを構成できるか、 D中の多くの頂点が特定のクラスに集中しているか のいずれかが成立していることが証明できる (頂点集合の構成にマッチングを使う) Set I

23 検討課題 支配頂点の“自律分散的な”遷移 欠陥を許した支配集合間の遷移可能性
ランダムウォーク(交換)の解析 許される欠陥数のどのあたりでP→NPになるのか(Pの範囲が広がればうれしい) オンラインアルゴリズムとしての輻輳制御問題


Download ppt "A08: 動的な構造をもつネットワーク上の資源割当て問題の研究"

Similar presentations


Ads by Google