检索结果-内蒙古大学图书馆

self-stabilizing algorithms for minimal global powerful alliance sets in graphs

INFORMATION PROCESSING LETTERS 2013年第10-11期113卷 365-370页

作者： Yahiaoui, Said Belhoul, Yacine Haddad, Mohammed Kheddouci, Hamamache Univ Lyon 1 LIRIS CNRS UMR5205 F-69622 Villeurbanne France Univ A Mira Dept Informat Bejaia 06000 Algeria CERIST Algiers 16030 Algeria

We propose a self-stabilizing distributed algorithm for the minimal global powerful alliance set problem in an arbitrary graph. Then, we give self-stabilizing algorithms for some generalizations of the problem. Using an unfair distributed scheduler, the proposed algorithms converge in O (mn) moves starting from an arbitrary state. (C) 2013 Elsevier B.V. All rights reserved.

关键词： self-stabilizing algorithms Graph algorithms Global powerful alliance Distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing algorithms for efficient sets of graphs and trees

引用

INFORMATION PROCESSING LETTERS 2013年第19-21期113卷 771-776页

作者： Turau, Volker Hamburg Univ Technol Inst Telemat D-21073 Hamburg Germany

关键词： self-stabilizing algorithms Efficient domination Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed self-stabilizing MIS with Few States and Weak Communication 23

Distributed Self-Stabilizing MIS with Few States and Weak Co...

引用

42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Giakkoupis, George Ziccardi, Isabella Univ Rennes Inria CNRS IRISA Rennes France Bocconi Univ Milan Italy

ISBN: (纸本)9798400701214

We study a simple random process that computes a maximal independent set (MIS) on a general n-vertex graph. Each vertex has a binary state, black or white, where black indicates inclusion into the MIS. The vertex states are arbitrary initially, and are updated in parallel: In each round, every vertex whose state is "inconsistent" with its neighbors, i.e., it is black and has a black neighbor, or it is white and all neighbors are white, changes its state with probability 1/2. The process stabilizes with probability 1 on any graph, and the resulting set of black vertices is an MIS. We show that the expected stabilization time is O(log n) on certain graph families, such as cliques and graphs of bounded arboricity. Our main result is that the process stabilizes in poly(log n) rounds w.h.p. on G(n,p) random graphs, for 0 <= p <= poly(log n) . n(-1/2) or p >= 1/poly(log n). Further, we propose an extension of this process, with larger but still constant vertex state space, which stabilizes in poly(log n) rounds on G(n,p) w.h.p., for all 1 <= p <= 1. Both processes readily translate into distributed/parallel MIS algorithms, which are self-stabilizing, use constant space (and constant random bits per round), and assume restricted communication as in the beeping or the synchronous stone age models. To the best of our knowledge, no previously known MIS algorithm is self-stabilizing, uses constant space and constant randomness, and stabilizes in poly(log n) rounds on G(n,p) random graphs.

关键词： maximal independent set parallel/distributed algorithms self-stabilizing algorithms beeping model

来源：评论

学校读者我要写书评

暂无评论

ACapDS: An Energy-Efficient and Fault-Tolerant Distributed Capacitated Dominating Set Algorithm for Industrial IoT

引用

IEEE ACCESS 2024年 12卷 38816-38829页

作者： Arapoglu, Ozkan Cabuk, Umut Can Dagdeviren, Orhan Challenger, Moharram Ege Univ Int Comp Inst TR-35040 Izmir Turkiye San Diego State Univ Dept Elect & Comp Engn San Diego CA 92182 USA Ege Univ Dept Comp Engn TR-35040 Izmir Turkiye Univ Antwerp Dept Comp Sci B-2020 Antwerp Belgium Flanders Make Strateg Res Ctr B-3001 Leuven Belgium

Design and analysis of energy-efficient and fault-tolerant dominating set (DS) algorithms are vital tasks for Industrial Internet of Things (IIoT) scenarios, as operational efficiency is a key objective in most industries. Such algorithms must maintain topology control, clustering, routing, and data aggregation. An IIoT deployment is said to pose the self-stabilization property if it can always recover to a steady state in a bounded time without any interruption whenever it is started at an unstable state. self-stabilization is a fruitful principle for building fault-tolerant IIoT deployments. This paper proposes a novel distributed fault-tolerant capacitated DS (capDS) algorithm for IIoT systems. The algorithm is the first self-stabilizing capDS approach to the best of our knowledge. Proofs concerning the asynchronous behaviors of the algorithm, as well as the self-stabilization feature with regard to convergence and closure properties, are provided. R2C1 Besides, our theoretical analysis showed that the algorithm's approximation ratio is 6 for IIoT setups implemented as unit disk graphs. Measurements made using our testbed of 40 IRIS motes and the extensive TOSSIM simulations revealed that the proposed algorithm is up to 55% better in terms of coefficient of variation, requires up to 61% fewer moves, causes up to 13% less data traffic, and consumes up to 14% less energy when compared to a randomized approach and a minimum ID priority-based approach.

关键词： Industrial Internet of Things (IIoT) minimum capacitated dominating set distributed algorithms self-stabilizing algorithms fault tolerance

来源：评论

学校读者我要写书评

暂无评论

Distributed self-stabilizing Capacitated Maximal Independent Set Construction in Wireless Sensor Networks

引用

WIRELESS PERSONAL COMMUNICATIONS 2020年第4期114卷 3271-3293页

作者： Arapoglu, Ozkan Dagdeviren, Orhan Ege Univ Int Comp Inst Izmir Turkey

Wireless sensor networks (WSNs) are composed of a large number of wireless self-organized sensor nodes connected through a wireless decentralized distributed network without the aid of a predefined infrastructure. Fault-tolerance and power management are fundamental challenges in WSNs. A WSN is self-stabilizing if it can initially start at any state and obtain a legitimate state in a finite time without any external intervention. self-stabilization is an important method for providing fault-tolerance in WSNs. Maximal independent set (MIS) is an extensively used structure for many important applications such as clustering (Randhawa and Jain in Wirel Personal Commun 97(3):3355, 2017. 10.1007/s11277-017-4674-5) and routing (Attea et al. in Wirel Personal Commun 81(2):819, 2015. 10.1007/s11277-014-2159-3;Lipinski in Wirel Personal Commun 101(1):251, 2018. 10.1007/s11277-018-5686-5) in WSNs. The capacitated MIS (CapMIS) problem is an extension of MIS in that each node has a capacity that determines the number of nodes it may dominate. In this paper, we propose a distributed self-stabilizing capacitated maximal independent set algorithm (CapMIS) in order to reduce energy consumption and support load balancing in WSNs. To the best of our knowledge, this is the first algorithm in this manner. The algorithm is validated through theoretical analysis as well as testbed implementations and simulations.

关键词： Capacitated maximal independent set Wireless sensor networks Distributed algorithms self-stabilizing algorithms

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing Metric Graphs

引用

THEORY OF COMPUTING SYSTEMS 2019年第2期63卷 177-199页

作者： Gmyr, Robert Lefevre, Jonas Scheideler, Christian Paderborn Univ Dept Comp Sci Paderborn Germany Univ Paris Diderot Paris 7 IRIf Paris France

We present a self-stabilizing algorithm for overlay networks that for an arbitrary given metric specified via a distance oracle constructs the graph representing that metric. The graph representing a metric is the unique minimal undirected graph such that for any pair of nodes the length of a shortest path between the nodes corresponds to the distance between the nodes according to the metric. The algorithm works under both an asynchronous and a synchronous daemon. In the synchronous case, the algorithm stabilizes in time O(n), and after stabilization each node sends and receives only a constant number of messages per round.

关键词： Overlay networks self-stabilizing algorithms Metric graph

来源：评论

学校读者我要写书评

暂无评论

An energy-efficient, self-stabilizing and distributed algorithm for maximal independent set construction in wireless sensor networks

引用

COMPUTER STANDARDS & INTERFACES 2019年 62卷 32-42页

作者： Arapoglu, Ozkan Akram, Vahid Khalilpour Dagdeviren, Orhan Ege Univ Int Comp Inst Izmir Turkey

Maximal independent set (MIS) is a very important structure that provides data aggregation, topology control and routing for wireless sensor networks (WSNs). Energy-efficient and fault-tolerant construction of MIS on WSNs is one of the vital tasks. A distributed sensor network is self-stabilizing if it can initially start at any state and regain a legal state in a finite time without any external intervention. self-stabilization is a considerable method to provide fault tolerance in WSNs. This paper presents a distributed self-stabilizing MIS algorithm which is an improved version of Turau's algorithm under a fully distributed scheduler for WSNs. The proposed algorithm is theoretically analyzed and evaluated with its counterparts. The proposed algorithm is compared with the other studies through testbed experiments on IRIS nodes and simulations on TOSSIM environment. It is shown that the proposed algorithm outperforms other algorithms in terms of move count and energy consumption.

关键词： Wireless sensor networks Maximal independent set self-stabilizing algorithms Fully distributed scheduler Distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

An Asynchronous self-stabilizing Maximal Independent Set Algorithm In Wireless Sensor Networks Using Two-Hop Information

An Asynchronous Self-Stabilizing Maximal Independent Set Alg...

引用

International Symposium on Networks, Computers and Communications (ISNCC)

作者： Arapoglu, Ozkan Dagdeviren, Orhan Ege Univ Int Comp Inst Izmir Turkey

ISBN: (纸本)9781728112442

Maximal independent set (MIS) has significantly important in practical applications for wireless sensor networks (WSNs). A distributed self-stabilizing system can initially start at any illegal state and takes back a legal state as long as there is no external intervention. We propose a novel distributed self-stabilizing MIS algorithm using two-hop information. It stabilizes an unstable system at most n-1 moves under an unfair distributed scheduler where n is the number of nodes in the graph. We use the message passing model as the communication model where this model is very appropriate for WSNs. The communication consumes the most energy in WSNs. So, move count is at least as important as round count where reducing the move count prolongs the lifetime of the network. We analyzed theoretically and tested it on SimPy discrete event simulator on randomly generated connected simple undirected graphs to compare with its counterparts in terms of transmitted bit count and move count against various node degrees and node counts.

关键词： self-stabilizing algorithms maximal independent set graph algorithms wireless sensor networks asynchronous algorithms

来源：评论

学校读者我要写书评

暂无评论

FORGIVE & FORGET self-stabilizing Swarms in Spite of Byzantine Robots 7

FORGIVE & FORGET Self-Stabilizing Swarms in Spite of Byzanti...

引用

7th International Symposium on Computing and Networking (CANDAR)

作者： Ashkenazi, Yotam Dolev, Shlomi Kamei, Sayaka Ooshita, Fukuhito Wada, Koichi Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Hiroshima Univ Grad Sch Engn Dept Informat Engn Grad Hiroshima Japan Nara Inst Sci & Technol Grad Sch Sci & Technol Nara Japan Hosei Univ Fac Sci & Engn Dept Appl Informat Tokyo Japan

ISBN: (纸本)9781728152684

In this paper, we consider the case in which a swarm of robots collaborates in a mission, where a few of the robots behave maliciously. These malicious Byzantine robots may be temporally or constantly controlled by an adversary. The scope is synchronized full information robot operations, where a robot that does not follow the program/policy of the swarm is immediately identified and can be remembered as Byzantine. As robots may be suspected of being Byzantine due to benign temporal malfunctions, it is imperative to forgive and forget, otherwise, a robot cannot assume collaborative actions with any other robot in the swarm. Still, remembering for a while may facilitate a policy of surrounding, isolating and freezing the movement of the misbehaving robots, by several robots, allowing the rest to perform the swarm task with no intervention. We demonstrate the need to periodically forgive and forget to realize swarm several tasks including patrolling/cleaning in the presence of possible Byzantine robots. The policy for achieving the task consists of blocking the movement of the Byzantine robot(s) by some of the robots, while the rest patrol/clean the plane. We present and use self-stabilizing (non-two faced) Byzantine pulse and clock synchronizations that are of independent interest.

关键词： Byzantine robots self-stabilizing algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A fault-tolerant and distributed capacitated connected dominating set algorithm for wireless sensor networks

引用

COMPUTER STANDARDS & INTERFACES 2021年 77卷 103490-103490页

作者： Arapoglu, Ozkan Dagdeviren, Orhan Ege Univ Int Comp Inst Izmir Turkey

Energy efficiency is one of the major issues in wireless sensor networks (WSNs) that lack a fixed infrastructure and centralized control. In order to prolong the network lifetime, a connected dominating set (CDS) has been widely used as a virtual backbone in WSNs. The sensor nodes in WSNs are prone to failure due to a lack of battery, hardware damage, link failure, or environmental interference. Therefore, designing an energy-efficient and fault-tolerant CDS algorithm is quite vital in WSNs. A non-masking fault tolerance method denoted selfstabilizing tolerates any finite number of transient faults. In this paper, we propose a fault-tolerant distributed algorithm for a minimal capacitated CDS (CapCDS) construction in WSNs. To the best of our knowledge, this is (the first distributed self-stabilizing CapCDS algorithm. It makes an illegitimate system legitimate at most n2 3 + )2n moves by using an unfair distributed scheduler where n is the number of nodes. The performance of the algorithm is validated through extensive experimental testbeds and simulations.

关键词： Capacitated connected dominating set self-stabilizing algorithms Distributed algorithms Wireless sensor networks Fault tolerance

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：