CORE: A combinatorial game-theoretic framework for coexistence rendezvous in DSA networks

Rendezvous is a vital process for connection establishment and recovery in dynamic spectrum access (DSA) networks. Frequency hopping (FH) is an effective rendezvous method that does not rely on a predetermined control channel. Recently, quorum-based FH approaches have been proposed for enabling asynchronous rendezvous between two or more secondary users (SUs). In this paper, we consider two collocated secondary networks, each represented by a pair of SUs. Both networks try to rendezvous concurrently, each aiming at maximizing its rendezvous performance, as measured by the average time-to-rendezvous and the number of rendezvous opportunities. To study this form of coexistence rendezvous, we follow a non-cooperative combinatorial game-theoretic framework, which we refer to as CORE. In this framework, SUs have different preferences towards various available licensed channels. Assuming first that SUs are time-synchronized, we formulate the interactions between the two networks as a two-player symmetric combinatorial game. We show the existence and uniqueness of a finite-population evolutionary stable strategy for this game. Furthermore, we conjecture that the game attains a pure-strategy Nash equilibrium (NE) for a wide range of design parameters. We also show that when SU pairs have the same preference towards all available channels, our game is an exact potential game, and hence the sequential best-response update is guaranteed to converge to a pure-strategy NE. We then study the time-asynchronous rendezvous game when SU pairs have the same preference towards all available channels. In this case, the game is also shown to be an exact potential game.