NDLI: Deterministic Blind Rendezvous in Cognitive Radio Networks

Content Provider	IEEE Xplore Digital Library
Author	Sixia Chen Russell, A. Samanta, A. Sundaram, R.
Copyright Year	2014
Description	Author affiliation: Dept. of Comput. Sci. & Eng., Univ. of Connecticut, Storrs, CT, USA (Sixia Chen; Russell, A.) \|\| Coll. of Comput. Sci., Northeastern Univ., Boston, MA, USA (Samanta, A.; Sundaram, R.)
Abstract	Blind rendezvous is a fundamental problem in cognitive radio networks. The problem involves a collection of agents (radios) that wish to discover each other (i.e., rendezvous) in the blind setting where there is no shared infrastructure and they initially have no knowledge of each other. Time is divided into discrete slots and spectrum is divided into discrete channels, [n] = 1, 2, ..., n. Each agent may access (or hop on) a single channel in a single time slot and two agents rendezvous when they hop on the same channel in the same time slot. The goal is to design deterministic channel hopping schedules for each agent so as to guarantee rendezvous between any pair of agents with access to overlapping sets of channels. The problem has three complicating considerations: first, the agents are asymmetric, i.e., each agent Ai only has access to a particular subset $S_{i}$ ⊂ [n] of the channels and different agents may have access to different subsets of channels (clearly, two agents can rendezvous only if their channel subsets overlap), second, the agents are synchronous, i.e., they do not possess a common sense of absolute time, so different agents may commence their channel schedules at different times (they do have a common sense of slot duration), lastly, agents are anonymous i.e., they do not possess an identity, and hence the schedule for Ai must depend only on $S_{i}.$ Whether guaranteed blind rendezvous in the asynchronous model was even achievable was an open problem. In a recent breakthrough, two independent sets of authors, Shin et al. (Communications Letters, 2010) and Lin et al. (INFOCOM, 2011), gave the first constructions guaranteeing asynchronous blind rendezvous in O $(n^{2})$ and O $(n^{3})$ time, respectively. We present a substantially improved and conceptually simpler construction guaranteeing that any two agents, $A_{i},$ $A_{j},$ will rendezvous in O $(\|S_{i}\|\|S_{j}\|$ log log n) time. Our results are the first that achieve nontrivial dependence on $\|S_{i}\|,$ the sizes of the sets of available channels. This allows us, for example, to save roughly a quadratic factor over the best previous results in the important case when channel subsets have constant size. We also achieve the best possible bound of O (1) rendezvous time for the symmetric situation, previous works could do no better than O (n). Using techniques from the probabilistic method and Ramsey theory we establish that our construction is nearly optimal: we show both an Ω $(\|S_{i}\|\|S_{j}\|)$ lower bound and an Ω(log log n) lower bound when $\|S_{i}\|,$ $\|S_{j}\|$ ≤ n/2.
File Size	282832
Page Count	10
Starting Page	358
Ending Page	367
File Format	PDF
ISSN	10636927
e-ISBN	9781479951697
DOI	10.1109/ICDCS.2014.44
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-06-30
Publisher Place	Spain
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Schedules Silicon Cognitive radio Color Computer science Educational institutions Communities channel hopping Deterministic blind rendezvous cognitive radio network Dynamic spectrum allocation
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Channel-Hopping-Based Communication Rendezvous in Cognitive Radio Networks

Channel-hopping-based communication rendezvous in cognitive radio networks

A Fast Blind Rendezvous Method by Alternate Hop-and-Wait Channel Hopping in Cognitive Radio Networks

Alternate hop-and-wait channel rendezvous method for cognitive radio networks

A Fast Rendezvous-Guarantee Channel Hopping Protocol for Cognitive Radio Networks

Channel selection using a multiple radio model

A channel-hopping scheme for continuous rendezvous and data delivery in cognitive radio network

Multiple Radios for Fast Rendezvous in Cognitive Radio Networks

A channel allocation strategy for multi-hop cognitive radio networks

Deterministic Blind Rendezvous in Cognitive Radio Networks

Similar Documents

Channel-Hopping-Based Communication Rendezvous in Cognitive Radio Networks

Channel-hopping-based communication rendezvous in cognitive radio networks

A Fast Blind Rendezvous Method by Alternate Hop-and-Wait Channel Hopping in Cognitive Radio Networks

Alternate hop-and-wait channel rendezvous method for cognitive radio networks

A Fast Rendezvous-Guarantee Channel Hopping Protocol for Cognitive Radio Networks

Channel selection using a multiple radio model

A channel-hopping scheme for continuous rendezvous and data delivery in cognitive radio network

Multiple Radios for Fast Rendezvous in Cognitive Radio Networks

A channel allocation strategy for multi-hop cognitive radio networks

Deterministic Blind Rendezvous in Cognitive Radio Networks