文献

J-GLOBAL ID：201202241468993575   整理番号：12A0479718

局所的プーリングとグラフ理論によるどん欲最大スケジューリングの性能解析

Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory

著者 (6件)： BIRAND Berk (Columbia Univ., NY, USA) ,  CHUDNOVSKY Maria (Columbia Univ., NY, USA) ,  RIES Bernard (Univ. Paris Dauphine, Paris, FRA) ,  SEYMOUR Paul (Princeton Univ., NJ, USA) ,  ZUSSMAN Gil (Columbia Univ., NY, USA) ,  ZWOLS Yori (McGill Univ., QC, CAN)
資料名： IEEE/ACM Transactions on Networking  (IEEE/ACM Transactions on Networking)
巻： 20  号： 1  ページ： 163-176  発行年： 2012年02月 
JST資料番号： W0507A  ISSN： 1063-6692  CODEN： IEANEP  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 無線ネットワークとスイッチをスケジューリングする単純なアルゴリズムとして,どん欲最大スケジューリング(GMS)などが提案されている。GMSは可能最大スループットの50%を達成するが,Dimakisらは最近局所的プーリング(LoP)条件下で100%スループットの達成を報告した。本論文は,グラフ理論の手法を利用して,一次干渉制約下においてLoPを充足するネットワークグラフの構造を求めた。次にGMSが100%スループットを達成しないグラフに注目し,二部ネットワークグラフ,すなわち入力待ち行列スイッチを考察し,k×nの二部グラフ(k≦7,nは任意)に対しGMSは少なくとも66%のスループットを達成することを示した。さらにσ%スループットを達成するσ-LoPグラフを考察し,任意に小さいσを伴うグラフの存在を示し,GMSの性能は非常に悪くなり得ることを示した。

シソーラス用語： 通信網 ,  無線伝送 ,  スイッチ回路 ,  *スケジューリング ,  性能分析 ,  計算機アルゴリズム ,  *スループット ,  *グラフ理論 ,  部分グラフ ,  待ち行列 ,  干渉雑音 ,  制約条件 ,  分散アルゴリズム ,  最大化問題 ,  計算機シミュレーション
準シソーラス用語： ネットワークグラフ ,  *無線ネットワーク ,  貪欲法 ,  二部グラフ

分類 (1件)： マイクロ波・ミリ波通信  (ND08020W)

タイトルに関連する用語 (3件)： グラフ理論 ,  スケジューリング ,  性能解析