通信資源管理への人工進化モデルの適用とその大規模ネットワークにおける評価

人工进化模型在大规模网络通信资源管理及其评估中的应用

基本信息

批准号：
11780179
负责人：
棟朝雅晴
金额：
$ 1.41万
依托单位：
Hokkaido University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

项目摘要

本研究では、進化的計算手法、特に遺伝的アルゴリズムを用いた経路制御アルゴリズムに関して、大規模ネットワーク上での性能評価を行い、アルゴリズムの改良を行った。改良点としては、適応度を評価するために必要なネットワーク状態の観測法について、従来は評価パケットが到着するまでの時間を用いていたのに対し、改良したアルゴリズムでは各リンクの負荷状態を離散化した情報を収集することでより高速かつ効率的にネットワークの負荷状態を観測することができた。さらには代替経路を生成するために使用される遺伝的操作に関してもリンクの負荷状態を考慮した交叉および突然変異の手法を開発することでアルゴリズムの改良を行った。提案したアルゴリズムの評価を行うため、イベントシミュレーション手法に基づくネットワークシミュレータを開発し、大規模シミュレーションにより改良手法の有効性を確認した。本研究では、さらに、ネットワーク資源管理アルゴリズムとして分散型帯域幅割当アルゴリズムを開発した。特定の通信リンクや小規模ネットワークを対象とした場合、通信帯域割当などの資源管理は集中管理方式により比較的容易に行うことができるが、大規模ネットワーク上においては、必然的に不確実な情報を基にした分散管理を行わざるを得なくなり、単純な最適化問題としてとらえることはできない。このような状況において、遺伝的アルゴリズムを用いた分散型帯域幅割当アルゴリズムを構築し、その有効性をシミュレータによるシミュレーション実験と通して検証した。

在这项研究中，在大型网络上进行了绩效评估，以用于进化计算方法，尤其是使用遗传算法的路径控制算法，并改善了算法。作为改进，先前使用了评估适应性所需的网络状态观察方法，以便在评估数据包到来之前使用时间，而改进的算法使网络负载状态可以通过收集已在每个链接的负载状态下离散的信息来更快，更有效地观察到网络负载状态。此外，就用于产生替代途径的遗传操作而言，通过开发了考虑链接加载条件的交叉和突变技术来改善算法。为了评估所提出的算法，开发了基于事件模拟方法的网络模拟器，并通过大规模模拟确认了改进方法的有效性。在这项研究中，我们进一步开发了分布式带宽分配算法作为网络资源管理算法。当针对特定的通信链接或小型网络时，可以使用集中式管理方法相对容易地执行诸如通信带宽分配之类的资源管理，但是在大型网络上，基于不确定信息的分布式管理不可避免地被迫执行分布式管理，这不能被视为简单的优化问题。在这种情况下，构建了使用遗传算法的分布式带宽分配算法，并通过使用模拟器的模拟实验来验证其有效性。