局所負荷に基づきエージェントのLoop-Free移動制約を適切に使い分けるAntNetの提案と評価

摘要

AntNet-FAに対して，エージェントが一度訪問したノードを再び訪問させない移動制約（以下Loop-Free）をもたせるアルゴリズムが提案されている．このアルゴリズムでは，ふくそうが起き，代替経路がある場合には，ふくそうしている経路を用いないように経路を円滑に切り換えることができる．しかし，このアルゴルリズムではScale-freeネットワークでトラヒックが定常状態において性能が劣化することが実験的に示されている．これは，移動制約により，必要以上にエージェントが生成され，ネットワーク全体の経路制御表から算出されるエントロピーが増加してしまうためと考えられる．エントロピーを増加させる作用は，ふくそう時には経路の切換を円滑に進める上で有用であるが，定常時においては，ランダムに経路制御を行ってしまうことにつながり，パケットの伝送時間を遅くする結果につながると考えられる．本論文では，AntNet-FAと，このLoop-Free移動制約をもつアルゴリズムと適時使い分けるアルゴリズムAntNet-CHTTを提案する．AntNet-CHTTでは，各ノードは通常はAntNet-FAと同じエージェントを生成するが，負荷が偏っている状態が一定時間続くと判断したとき，Loop-Free制約をもつエージェントを生成する．このときノードは同時に所要時間の履歴の消去も行う．このアルゴリズムにより，ネットワーク資源をより有効に活用することができる．本論文では，提案アルゴリズムと既存アルゴリズムの比較を計算機上で行い，既存のアルゴリズムよりも良好な結果が得られることを確認した．