A study of fault-tolerant distributed approximation algorithms for dynamic wireless networks

动态无线网络容错分布式逼近算法研究

• 批准号: 22700074
• 负责人: KAMEI Sayaka
• 金额: $ 2.41万
• 依托单位: Hiroshima University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010-04-01 至 2014-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22700074/
• 关键词: 分散アルゴリズム; 耐故障性; 自己安定; 近似アルゴリズム; 安全収束性; 動的ネットワーク; 無線ネットワーク; 動的無線ネットワーク; 自己安定性; 分散近似アルゴリズム; safe convergence

As distributed algorithms for dynamic wireless networks, 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.

作为动态无线网络的分布式算法，我们设计了具有安全收敛特性的自稳定分布式算法。一个具有安全收敛特性的自稳定算法在故障发生后，无论解的质量如何，都能快速移动到安全配置。在此之后，它收敛到最优解，而不破坏安全性。对于可由NP难问题建模的分布式问题，我们设计了具有安全收敛性质的自稳定分布式逼近算法。

项目成果

Fast and Reliable Route Maintenance Protocols for WSN with Crash and Intermittent Failures

针对具有崩溃和间歇性故障的 WSN 的快速可靠的路由维护协议

• 发表时间: 2011
• 作者: Lean Yu;Wuyi Yue;and Shouyang Wang;河本満,井上雄二郎,河野清尊,浅野太;Sayaka Kamei
• 通讯作者: Sayaka Kamei

An Asynchronous Self-Stabilizing Approximation for the Minimum Connected Dominating Set with Safe Convergence in Unit Disk Graphs

单位圆盘图中安全收敛的最小连通支配集的异步自稳定逼近

• 发表时间: 2013
• 作者: 福島行信;菊本大志;陳文傑;横平徳美;打矢隆弘;Sayaka Kamei
• 通讯作者: Sayaka Kamei

Mobile agent rendezvous on a probabilistic edge evolving ring

概率边缘演化环上的移动代理会合

• 发表时间: 2012
• 作者: 大山 恵弘;河崎 雄大;Yukiko Yamauchi
• 通讯作者: Yukiko Yamauchi

Feasibility of Polynomial-time Randomized Gathering for Oblivious Mobile Robots

遗忘移动机器人多项式时间随机采集的可行性

• DOI: 10.1109/tpds.2012.212
• 发表时间: 2013
• 期刊: IEEE Transactions on Parallel and Distributed Systems
• 影响因子: 5.3
• 作者: Taisuke Izumi;Tomoko Izumi;Sayaka Kamei;Fukuhito Oosita
• 通讯作者: Fukuhito Oosita

Observations on non-silent self-stabilizing algorithms in sensor networks with probabilistically intermittent link failures

具有概率间歇性链路故障的传感器网络中非静默自稳定算法的观察

• 发表时间: 2011
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Hirotsugu Kakugawa;Yukiko Yamauchi;Sayaka Kamei;Toshimitsu Masuzawa
• 通讯作者: Toshimitsu Masuzawa