On the Multichannel Rendezvous Problem: Fundamental Limits, Optimal Hopping Sequences, and Bounded Time-to-Rendezvous

• 成果类型: Article
• 署名作者: Chang, Cheng-Shang; Liao, Wanjiun; Lien, Ching-Min
• 署名单位: National Tsing Hua University; National Taiwan University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0680
• 发表日期: 2015
• 页码: 1-23
• 关键词: search; DESIGN; algorithm; scheme

摘要

One of the fundamental problems in a cognitive radio network, known as the multichannel rendezvous problem, is for two secondary users to find a common channel that is not blocked by primary users. The basic idea for solving such a problem in most works in the literature is for the two users to select their own channel hopping sequences and then rendezvous when they both hop to a common unblocked channel at the same time. In this paper, we focus on the fundamental limits of the multichannel rendezvous problem and formulate such a problem as a constrained optimization problem, where the selection of the random hopping sequences of the two secondary users must satisfy certain constraints. We derive various lower bounds for the expected (respectively, maximum) time-to-rendezvous under certain constraints. For some of these lower bounds, we are also able to construct optimal channel hopping sequences that achieve the lower bounds. Inspired by the constructions of quorum systems and relative difference sets, our constructions of the channel hopping sequences are based on the mathematical theories of finite projective planes, orthogonal Latin squares, and sawtooth sequences. The use of such theories in the constructions of channel hopping sequences appear to be new and better than other existing schemes in terms of minimizing the expected (respectively, maximum) time-to-rendezvous.