### Abstract

The whitespace-discovery problem describes two parties, Alice and Bob, trying to discovery one another and establish communication over one of a given large segment of communication channels. Subsets of the channels are occupied in each of the local environments surrounding Alice and Bob, as well as in the global environment (Eve). In the absence of a common clock for the two parties, the goal is to devise time-invariant (stationary) strategies minimizing the discovery time. We model the problem as follows. There are N channels, each of which is open (unoccupied) with probability p _{1},p _{2},q independently for Alice, Bob and Eve respectively. Further assume that N ≫ 1/(p _{1} p _{2} q) to allow for sufficiently many open channels. Both Alice and Bob can detect which channels are locally open and every time-slot each of them chooses one such channel for an attempted discovery. One aims for strategies that, with high probability over the environments, guarantee a shortest possible expected discovery time depending only on the p _{i} 's and q. Here we provide a stationary strategy for Alice and Bob with a guaranteed expected discovery time of O(1/(p1p2q ^{2}|)) given that each party also has knowledge of p _{1},p _{2},q. When the parties are oblivious of these probabilities, analogous strategies incur a cost of a poly-log factor, i.e. Õ(1/(p1p2q ^{2}. Furthermore, this performance guarantee is essentially optimal as we show that any stationary strategies of Alice and Bob have an expected discovery time of at least Ω(1/(p1p2q^{2})).

Original language | English (US) |
---|---|

Title of host publication | Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings |

Pages | 713-722 |

Number of pages | 10 |

DOIs | |

State | Published - 2011 |

Event | 19th Annual European Symposium on Algorithms, ESA 2011 - Saarbrucken, Germany Duration: Sep 5 2011 → Sep 9 2011 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 6942 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 19th Annual European Symposium on Algorithms, ESA 2011 |
---|---|

Country | Germany |

City | Saarbrucken |

Period | 9/5/11 → 9/9/11 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Optimal discovery strategies in white space networks'. Together they form a unique fingerprint.

## Cite this

*Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings*(pp. 713-722). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6942 LNCS). https://doi.org/10.1007/978-3-642-23719-5_60