Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2012-02-21
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
Consider a time-slotted, single-hop, wireless sensor network (WSN) consisting of n correct devices and and t=f*n Byzantine devices where f>=0 is any constant; that is, the Byzantine devices may outnumber the correct ones. There exists a trusted sender Alice who wishes to deliver a message m over a single channel to the correct devices. There also exists a malicious user Carol who controls the t Byzantine devices and uses them to disrupt the communication channel. For a constant k>=2, the correct and Byzantine devices each possess a meager energy budget of O(n^{1/k}), Alice and Carol each possess a limited budget of \tilde{O}(n^{1/k}), and sending or listening in a slot incurs unit cost. This general setup captures the inherent challenges of guaranteeing communication despite scarce resources and attacks on the network. Given this Alice versus Carol scenario, we ask: Is communication of m feasible and, if so, at what cost? We develop a protocol which, for an arbitrarily small constant \epsilon>0, ensures that at least (1-\epsilon)n correct devices receive m with high probability. Furthermore, if Carol's devices expend T energy jamming the channel, then Alice and the correct devices each spend only \tilde{O}(T^{1/(k+1)}). In other words, delaying the transmission of m forces a jammer to rapidly deplete its energy supply and, consequently, cease attacks on the network.
Gilbert Seth
Young Maxwell
No associations
LandOfFree
Making Evildoers Pay: Resource-Competitive Broadcast in Sensor Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Making Evildoers Pay: Resource-Competitive Broadcast in Sensor Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Making Evildoers Pay: Resource-Competitive Broadcast in Sensor Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-423232