Optimality and complexity of opportunistic spectrum access: A truncated Markov decision process formulation

TitleOptimality and complexity of opportunistic spectrum access: A truncated Markov decision process formulation
Publication TypeJournal Article
Year of Publication2007
AuthorsDjonin, D. V., Q. Zhao, and V. Krishnamurthy
Journal2007 IEEE International Conference on Communications, Vols 1-14
Pagination5787–5792
ISSN1550-3607
Abstract

We consider opportunistic spectrum access (OSA) which allows secondary users to identify and exploit instantaneous spectrum opportunities resulting from the bursty traffic of primary users. Within the framework of Partially Observable Markov Decision Process (POMDP), we develop decentralized cognitive MAC protocols that allow secondary users to independently search for spectrum opportunities without a central coordinator or a dedicated communication channel. The focus of this paper is the tradeoff between optimality and complexity of obtaining OSA protocols. We first analyze the computational complexity of designing OSA protocols within the POMDP framework and demonstrate that the complexity grows exponentially with the horizon length (i.e, the spectrum access time of secondary users). By exploiting the underlying structure of the problem, we aim to develop a quantitative characterization of the fundamental tradeoff between optimality and complexity so that a systematic way of balancing these two can be obtained. Specifically, by exploiting the mixing time of the underlying Markov process of spectrum occupancy, we develop a truncated MDP formulation of OSA and reduce the computational complexity from growing exponentially to linearly with the horizon length. More importantly, this truncated MDP formulation provides a systematical way of trading off performance with complexity by choosing an appropriate truncation parameter.

a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949
Email:

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia