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.

Spectrum efficient cooperative relaying based on outage-multiplexing tradeoff analysis.

Spectrum efficient multiple relay selection strategy for two-hop cooperative decode-and-forward relay networks is proposed for the case when the sum power among all relay nodes is limited. Based on the outage-multiplexing tradeoff (OMT), the number of active relay nodes is maximized so that the resulting sum-relay capacity is maximized while each relay outage capacity remains greater than or equal to a certain target level. Using asymptotic analysis, it is shown that for the proposed OMT relaying strategy the associated multiplexing and cooperative system diversity gains improve proportionally with the number of active relay nodes. It is also shown analytically that the proposed OMT relaying outperforms the conventional opportunistic single relaying in terms of the sum-relay capacity.

Mitigating Cross-Network Interference in Cognitive Spectrum Sharing with Opportunistic Relaying

We examine the impact of primary and secondary interference on opportunistic relaying in cognitive spectrum sharing networks. In particular, new closed-form exact and asymptotic expressions for the outage probability of cognitive opportunistic relaying are derived over Rayleigh and Nakagami-m fading channels. Our analysis presents revealing insights into the diversity and array gains, diversity-multiplexing tradeoff, impact of primary transceivers' positions, and the optimal position of relays. We highlight that cognitive opportunistic relaying achieves the full diversity gain which is a product of the number of relays and the minimum Nakagami-m fading parameter in the secondary network. Furthermore, we confirm that the diversity gain reduces to zero when the peak interference constraint in the secondary network is proportional to the interference power from the primary network.