A lot of self-stabilizing algorithms for computing dominating sets problem have been proposed in the literature due to many real-life applications. Most of the proposed algorithms either work for dominating sets with ...
详细信息
ISBN:
(纸本)9781467360852;9781467360845
A lot of self-stabilizing algorithms for computing dominating sets problem have been proposed in the literature due to many real-life applications. Most of the proposed algorithms either work for dominating sets with a uniform weight or find approximation solutions to weighted dominating sets. However, for non-uniform weighted dominating sets (WDS) problem, there is no self-stabilizing algorithm for the WDS. Furthermore, how to find the minimal weighted dominating set is a challenge. In this paper, we propose a self-stabilizing algorithm for the minimal weighted dominating set (MWDS) under a central daemon model when operating in any general network. We further prove that the worst case convergence time of the algorithm from any arbitrary initial state is O(n(2)) steps where n is the number of nodes in the network.
Wireless sensor network (WSNs) are composed of a large number of battery-powered wireless sensors, which acquire and monitor physical data from their surroundings through self-organization. The sensors are deployed ra...
详细信息
Wireless sensor network (WSNs) are composed of a large number of battery-powered wireless sensors, which acquire and monitor physical data from their surroundings through self-organization. The sensors are deployed randomly in a target area where maintenance and battery replacement are difficult or even impossible. To achieve better coverage and prolong network lifetime, networks typically adopt clustering protocols with hierarchical inter-cluster topology for network management and data acquisition in WSNs. However, typical solutions require cluster re-configuration due to early death of cluster heads (CHs) and cause energy inefficiency. This paper proposes a coverage- and energy-aware protocol with intra- and inter-cluster methods called CEMST that considers the sensor node density and coverage overlapping. In addition, to adapt network dynamics while improving energy efficiency, self-stabilizing algorithm and Boruvka algorithm are applied to construct the minimum spanning trees (MST) for antra- and inter-cluster routes, respectively. Simulation results indicate that CEMST produces the balanced clustering structures and provides better coverage and longer network lifetime than previous methods.
self-stabilizing protocols enable distributed systems to recover correct behavior starting from any arbitrary configuration. In particular, when processors communicate by message passing and the communication links ar...
详细信息
self-stabilizing protocols enable distributed systems to recover correct behavior starting from any arbitrary configuration. In particular, when processors communicate by message passing and the communication links are unbounded, fake messages may be placed in communication links by an adversary. When the number of such fake messages is unknown, self-stabilization may require huge resources: center dot generic solutions ( a.k.a. data link protocols) require unbounded resources, which makes them unrealistic to deploy, center dot specific solutions ( e.g. , census or tree construction) require O(n log n) or O(O log n) bits of memory per node, where n denotes the network size and O its maximum degree, which may prevent scalability. We investigate the possibility of resource-efficient self-stabilizing protocols in this context. Specifically, we present self-stabilizing protocols for (O + 1)-coloring and maximal independent set construction in any n-node graph, under the asynchronous message-passing model. The problems of (O + 1)-coloring and maximal independent set construction are widely regarded as benchmark problems for evaluating local algorithms. Our protocols offer many desirable features. They are deterministic, converge in O(kOn2 2 log n) message exchanges, where k is the (unknown) initial number of (possibly corrupted) messages in a communication link. They use messages of O (log log n + log O) bits with a memory of O (O log O + log log n) bits at each node. The resource consumption of our protocols is thus almost oblivious to the number of nodes, enabling scalability. Moreover, a striking property of our protocols is that the nodes do not need to know the number, or any bound on the number of messages initially present in each communication link of the initial (potentially corrupted) network configuration. This permits our protocols to handle any future network with unknown message capacity communication links. A key building block of our coloring and maximal
One of the main design challenges in Wireless Sensor Networks (WSN) is to prolong the system lifetime, while achieving acceptable quality of service for applications. In WSN, each sensor node is battery powered and it...
详细信息
One of the main design challenges in Wireless Sensor Networks (WSN) is to prolong the system lifetime, while achieving acceptable quality of service for applications. In WSN, each sensor node is battery powered and it is not convenient to recharge or replace the batteries in many cases, especially in remote and hostile environments. Due to the limited capabilities of sensor nodes, it is usually desirable that a WSN should be deployed with high density and thus redundancy can be exploited to increase the network's lifetime. In this paper, we introduce an efficient lifetime optimization and self-stabilizing algorithm to enhance the lifetime of wireless sensor networks especially when the reliabilities of sensor nodes are expected to decrease due to use and wear-out effects. Our algorithm seeks to build resiliency by maintaining a necessary set of working nodes and replacing failed ones when needed. We provide some theoretical and simulation results, that fully demonstrate the usefulness of the proposed algorithm. (C) 2013 Elsevier B.V. All rights reserved.
self-stabilization is an excellent approach for adding fault tolerance to a distributed multi-agent system. However, two properties of self-stabilization theory, closure and convergence, may not be satisfied if agents...
详细信息
ISBN:
(纸本)9781450384414
self-stabilization is an excellent approach for adding fault tolerance to a distributed multi-agent system. However, two properties of self-stabilization theory, closure and convergence, may not be satisfied if agents are selfish. To guarantee closure in the presence of selfish agents, we propose fault-containment as a method to constrain legitimate configurations of the self-stabilizing system to be Nash equilibria. To guarantee convergence, we introduce probabilistic self-stabilization to set the probabilities of rules such that agents' self-interests are satisfied. We also assume selfish agents as capable of performing unauthorized actions at any time, which threatens both properties, and present a stepwise solution to handle it. As a case study, we consider the problem of distributed clustering and propose self-stabilizing algorithms for forming clusters. Simulation results show that our algorithms react correctly to rule deviations and outperform comparable schemes in terms of fairness and stabilization time.
Wireless sensor network (WSNs) are composed of a large number of battery-powered wireless sensors, which acquire and monitor physical data from their surroundings through self-organization. Sensors are deployed random...
详细信息
ISBN:
(纸本)9781538671771
Wireless sensor network (WSNs) are composed of a large number of battery-powered wireless sensors, which acquire and monitor physical data from their surroundings through self-organization. Sensors are deployed randomly in a target area where maintenance and battery replacement are difficult or even impossible. To effectively save energy and prolong network lifetimes, networks typically adopt clustering protocols with hierarchical inter-cluster topologies for network management and data acquisition in WSNs. However, such solutions require cluster re-configuration due to early death of cluster heads (CHs) and energy inefficiency. This paper proposes a coverage- and energy-aware protocol with intra- and inter-cluster methods called CEMST based on newly defined parameters for sensor overlapping and node density functions. In addition, to adapt network dynamics while improving energy efficiency, a self-stabilizing algorithm is proposed with the Boruvka algorithm to respectively construct minimum spanning trees (MST) for intra- and inter-cluster routes. Simulation results indicate that CEMST yields more balanced clustering structures than previous efficient protocols, and provides longer network lifetime than those methods.
暂无评论