The Forgiving Graph:A distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick "repairs," which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions,without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been - in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most - log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degreewould have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network. © Springer-Verlag 2012.

Selecting users in energy-efficient collaborative spectrum sensing

Cognitive radio network is defined as an intelligent wireless communication network that should be able to adaptively reconfigure its communication parameters to meet the demands of the transmission network or the user. In this context one possible way to utilize unused licensed spectrum without interfering with incumbent users is through spectrum sensing. Due to channel uncertainties, single cognitive (opportunistic) user cannot make a decision reliably and hence collaboration among multiple users is often required. Here collaboration among large number of users tends to increase power consumption and introduces large communication overheads. In this paper, the number of collaborating users is optimized in order to maximize the probability of detection for any given power budget in a cognitive radio network, while satisfying constraints on the false alarm probability. We show that for the maximum probability of detection, collaboration of only a subset of available opportunistic users is required. The robustness of our proposed spectrum sensing algorithm is also examined under flat Rayleigh fading and AWGN channel conditions.