Events — Colloquia & Seminars
Adversary Immune Communication Algorithms in Ad Hoc Networks
Speaker: Mirek Kutylowski, Wroclaw University of Technology, Poland
Date: Friday, October 1, 2004
Talk: 3:30 PM, 366 West Village H
Abstract
We consider self-organization algorithms for ad-hoc networks with a single, shared communication channel. In such networks, messages sent by different units at the same time collide and no message comes through. We even assume that collisions in the shared channel cannot be detected by the stations participating in the self-organization protocol (no-CD model).
We consider self-organization algorithms for ad-hoc networks with a single, shared communication channel. In such networks, messages sent by different units at the same time collide and no message comes through. We even assume that collisions in the shared channel cannot be detected by the stations participating in the self-organization protocol (no-CD model). Most of the algorithms constructed so far, disregard the fact that faults can occur in the radio channel, or even worse, an adversary can send messages aiming to cause collisions and in this way degrade functionality of the network. So we are interested in algorithms that work in the presence of an adversary, who knows the algorithm executed and may try to disturb its execution or to make it faulty. Usually, parallel algorithms have certain ``hot spots," where some crucial messages are exchanged. This gives opportunities for an adversary, who may attack only these hot spots. So, we have to reconsider design of self-organization algorithms of such networks. Ideally, such algorithms should be homogenous in the sense that there are no vulnerable points in the algorithm execution.
We present an initialization algorithm which assigns consecutive numbers to N participating units. Our algorithm has time complexity O(N) and energy cost O(sqrt(log(N))). It succeeds with probability 1-2^(Omega(sqrt(log(N)))) in presence of an adversary, who has energy cost Theta(log(N)).
Brief Biography
none provided