情報ネットワークのスケジューリングのためのm-バランス列とその拡張に関する研究

点击翻译按钮获取中文摘要

本研究の課題は,複数種類の文字を並べて無限に長い文字列を構成する際に,各文字に対して列の中で現れる割合(出現率)が与えられているときに,それを満足しながら如何にバランス良く(なるべく均等に)文字を並べるかという問題への取り組み,ならびにその情報ネットワーク等のスケジューリングや制御への応用についてです.この課題の遂行,およびこれに関連するテーマとして,今年度は以下の研究を行いました.これまでに研究代表者の研究室では,上記の問題に対して「m-バランス列」という概念を提唱しています.これは,mに0以上の整数値を代入することによって,各文字が任意の出現率を持つ任意の(半)無限列に対してバランスの良さの指標を与える(mの値が小さい程バランスが良い)ものです.また,このm-バランス列を生成するアルゴリズムとして,ビリヤード列(billiard sequences)と呼ばれる文字列を生成するものを考え,N種の文字からなるビリヤード列は必ず(N-1)-バランス列になることを示しています.しかし,このアルゴリズムの問題点として,与えられた出現率の組によっては,よりバランスの良い列が存在するかもしれないにもかかわらず,それが実現されない場合がありました.これは,生成される文字列のバランスの良さが,アルゴリズムの初期値に大きく依存することに依ります.この問題に対して,文字の出現率が有理数であるときには,生成される文字列が周期列になることを利用し,確率的なアルゴリズムによって,ビリヤード列を生成するアルゴリズムに良い初期値を与えることに成功しました.尚,この研究成果は現在,海外の学術論文誌に投稿中です.上記に加えて,応用に関する課題として,ネットワークのスケジューリングにおいて重要な待ち行列システムの並列推定に関する研究も行いました.また,インターネットにおける性能や通信品質の推定法に関する研究も行っています.