2019 · 14 citations · 17 references
ComputingComputer ScienceComputer NetworksFault ToleranceFault-tolerant ComputingFault-tolerant CommunicationReliable Distributed SystemsSensor NetworksWireless Sensor NetworksApproximation GuaranteesBroadcastBroadcast AlgorithmsGreedy ApproximationGreedy HeuristicsNode FailuresRandom GraphsReliable Broadcast
Broadcast is one of the fundamental primitives to enable large-scale networks such as sensor networks and IoT. There is a rich study on achieving reliable broadcast under various kind of failures. In this paper, we use the notion of trust to improve the performance of reliable broadcast. We focus on Certified Propagation Algorithm (CPA), one of the simple algorithms that does not rely on a cryptographic infrastructure and has a proven guarantee on resilience (number of node failures tolerated). Specifically, the paper has two main contributions: (i) A new algorithm Trust-CPA which integrates CPA with trusted nodes has been proposed and shown to increase the resilience from the original CPA, and (ii) A natural optimization problem related to Trust-CPA (i.e., finding the location to place trusted nodes to reduce the broadcast latency) has been proposed as well. We first show that it is NP-hard to find an exact answer and even NP-hard to find a good approximation. A greedy heuristic algorithm has been used and its efficacy has been examined using simulation. We show that our algorithm performs relatively well in geometric random graphs, an appropriate model for large- scale wireless sensor networks.
17
Design and deployment of industrial sensor networks
L. Krishnamurthy, Robert Adler, P. Buonadonna et al. · 2005 · 316 citations
Engineering, Industrial Engineering, Systems Engineering +17
Deploying sensor networks with guaranteed capacity and fault tolerance
Jonathan Bredin, Erik D. Demaine, MohammadTaghi Hajiaghayi et al. · 2005 · 202 citations
Broadcast in radio networks tolerating byzantine adversarial behavior
Chiu‐Yuen Koo · 2004 · 151 citations