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

信息网络调度的m平衡列及其扩展研究

• 批准号: 13780358
• 负责人: 三好 直人
• 金额: $ 1.02万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780358/
• 关键词: バランスの良い文字列; m-バランス列; ビリヤード列; ネットワーク・スケジューリング; 情報ネットワーク; 待ち行列; 確率モデル; 性能推定; パターン・サーチ法; スケジューリング; 定常特性

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

本研究的问题是通过排列多种类型的字符来创建一个无限长的字符串，并且当每个字符在字符串中出现给定的比例（出现率）时，如何满足这个要求，就是如何排列。以均衡的方式（尽可能均匀地）描述其特征，并将其应用于信息网络的调度和控制。为了完成这项任务，并作为相关主题，我们将在本财年开展以下培训。迄今为止，首席研究员的实验室提出了“m-平衡序列”的概念来解决上述问题，这给出了任何（半）无限序列的平衡指数，其中每个字符具有任意出现率（较小的一个）。 m的值越大，平衡性越好）另外，这个m平衡序列作为生成台球序列（biliard）的算法。该算法的问题在于，由N种字符组成的台球序列始终是（N-1）平衡序列，取决于出现率的集合，即使可能存在更平衡的序列，但也可能无法实现。这是因为生成的字符串的平衡为 对于这个问题，如果字符的出现率为 。利用当字符串为有理数时，生成的字符串成为周期字符串的事实，我们成功地为使用概率算法生成台球字符串的算法提供了良好的初始值，目前正在提交给一个算法。海外学术期刊。除上述之外，我们还对网络调度中重要的排队系统并行估计作为应用相关问题进行了研究。我们还对网络调度中重要的排队系统并行估计进行了研究。我们还进行了估计方法的研究。