進化的計算手法を用いた適応型経路制御アルゴリズムの構築

使用进化计算方法构建自适应路径控制算法

• 批准号: 09780225
• 负责人: 棟朝 雅晴
• 金额: $ 1.34万
• 依托单位: Hokkaido University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-09780225/
• 关键词: ルーティング; 遺伝的アルゴリズム

本研究では、複雑系、人工生命に関連して近年注目を集めている遺伝的アルゴリズムをインターネットにおける経路制御アルゴリズムへ応用することで、ネットワークの負荷変化に動的するアルゴリズムを構築する。現在一般に使用されているルーティングアルゴリズムでは、ネットワークの負荷状態や通信リンクの性能などを考慮せず、単純に通過したゲートウェイの数で表されるホップカウント距離を用いていた。そこで、ネットワークの負荷状態を考慮した適応型のルーティングアルゴリズムを少ない通信負荷で実現するため、遺伝的アルゴリズムにより必要な代替経路群を動的に生成するアルゴリズムを構築した。代替経路を効率的に生成するため、特別に設計された経路遺伝的操作(Path Genetic Operators)を提案した。提案するルーティングアルゴリズムにおいては、初期経路として、従来と同様のホップカウント距離に基づいた最短経路を使用し、ある一定回数以上使用される経路に関して、代替経路を動的に生成し、各代替経路の通信遅延に応じてパケットを分配する。通信遅延の観測に関しては、ルーティングテーブルに存在する各経路に関して、定期的に通信遅延の観測パケットを送出するが、ルーティングテーブルには頻繁に使用される少数の代替経路のみ存在するため、少ない通信負荷で効果的な観測が行われる。アルゴリズムの評価を行うため、離散事象シミュレータを構築し、その上でシミュレーション実験を行い、従来の代表的な手法であるRIP,SPFと比較した。その結果、今回提案した基本的なアルゴリズムにより、ネットワークの負荷が減少し、効果的に通信パケットが送出されていることが確かめられた。

This study focuses on the relationship between complex systems and artificial life in recent years, and constructs a new system for controlling the loss of life and load change. Now generally used in the field of communication, load status, performance, pure transmission, number of tables, distance, etc. The load status of the communication network is considered to be appropriate for the type of communication network. The communication network is constructed to reduce the communication load. Alternative Path Genetic Operators (Path Genetic Operators) The proposal is that the shortest circuit in the base distance should be used, and the shortest circuit should be used more than a certain number of times. The generation of alternative circuits should be generated, and the communication delay of each alternative circuit should be allocated. Communication delay measurement exists on all routes, and periodic communication delay measurement exists on all routes, and frequent use of communication delay measurement exists on a small number of alternative routes, and communication load measurement results are achieved. In addition to the above, the author also pointed out that there is a great deal of difference between the two. As a result of this, the basic requirements of the present proposal are to reduce the load on the server and to ensure that the communication is sent out.

项目成果

棟朝雅晴、高井昌彰、佐藤義治: "遺伝的アルゴリズムによる負荷分散機構を有する適応型ルーティング" 情報処理学会論文誌. 39・2. 219-227 (1998)

Masaharu Munetomo、Masaaki Takai、Yoshiharu Sato：“基于遗传算法的自适应路由”，日本信息处理学会会刊 39・2（1998 年）。