A Study of fault-tolerant distributed approximation algorithms for MANET

MANET容错分布式逼近算法研究

• 批准号: 19700075
• 负责人: KAMEI Sayaka
• 金额: $ 2.43万
• 依托单位: Hiroshima University (2008-2009)Tottori University of Environmental Studies (2007)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2009
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19700075/
• 关键词: 分散アルゴリズム; 耐故障性; 自己安定; 近似アルゴリズム; MANET; 分散近似アルゴリズム; safe convergence; 自己安定性; safe converence; 最小連結支配集合; グループ相互排除

As distributed algorithms for MANET, we designed self-stabilizing distributed algorithms with safe convergence property. A self-stabilizing algorithm with safe convergence property quickly moves to a safe configuration regardless of the quality of solutions after the failure occurred. After that, it converges to the optimal solution without breaking the safety property. For distributed problems which can be modeled by NP-hard problems, we designed self-stabilizing distributed approximation algorithms with safe convergence property.

作为Manet的分布式算法，我们设计了具有安全收敛属性的自动化分布式算法。具有安全收敛属性的自动化算法都会迅速移动到安全配置，无论发生故障后解决方案的质量如何。之后，它在不破坏安全性能的情况下收敛到最佳解决方案。对于可以通过NP硬性问题建模的分布式问题，我们设计了具有安全收敛属性的分布式近似算法的自动化分布式近似算法。

项目成果

Randomized gathering of mobile robots with local-multiplicity detection

通过局部多重性检测随机聚集移动机器人

• 发表时间: 2009
• 作者: Sayaka Kamei;Hirotsugu Kakugawa;Hirotsugu Kakugawa;Sayaka Kamei;Sayaka Kamei;Taisuke Izumi
• 通讯作者: Taisuke Izumi

A Self-Stabilizing Distributed Approximation Algorithm for the Minimum Connected Dominating Set

• DOI: 10.1142/s0129054110007362
• 发表时间: 2007-03
• 期刊: 2007 IEEE International Parallel and Distributed Processing Symposium
• 作者: S. Kamei;H. Kakugawa

A Self-stabilizing Approximation Algorithm for the Minimum Weakly Connected Dominating Set with Safe Convergence

安全收敛的最小弱连通支配集的自稳定逼近算法

• 发表时间: 2007
• 期刊: Proc. of the First International Workshop on Reliability, Availability, and Security
• 作者: Takahiro Sawamura;et. al.;Sayaka Kamei and Hirotsugu Kakugawa
• 通讯作者: Sayaka Kamei and Hirotsugu Kakugawa

Randomized ganthering of mobile robots with local-multiplicity detection

具有局部多重性检测的移动机器人随机聚集

• 发表时间: 2009
• 作者: Sayaka Kamei;Hirotsugu Kakugawa;Hirotsugu Kakugawa;Sayaka Kamei;Sayaka Kamei;Taisuke Izumi;Hirotsugu Kakugawa;Taisuke Izumi
• 通讯作者: Taisuke Izumi

Timer-Based composition of fault-conntaining self-stabilizing protocols

基于定时器的含故障自稳定协议的组合

• 发表时间: 2010
• 期刊: Information Sciences 180
• 作者: Yukiko Yamauchi;Sayaka Kamei;Fukuhito Ooshita;Yoshiaki Katayama;Hirotsugu Kakugawa;Toshimitsu Masuzawa;Yukiko Yamauchi
• 通讯作者: Yukiko Yamauchi