当前位置:首页 >> >>

Analysis and design of cognitive radio networks and distributed radio resource management a


Analysis and Design of Cognitive Radio Networks and Distributed Radio Resource Management Algorithms
James O’Daniell Neel Dissertation submitted to the Faculty of the Virginia Polytechnic Institute and State University in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Electrical Engineering Approved:

Jeffrey H. Reed (Chairman) Luiz A. DaSilva Allen B. MacKenzie

R. Michael Buehrer Robert P. Gilles

September 6, 2006 Blacksburg, VA

Keywords: Cognitive Radio, Software Radio, Game Theory, Potential Games, Interference Reducing Networks, Distributed Radio Resource Management, Power Control, Dynamic Frequency Selection, 802.11, 802.22, Sensor Networks

Copyright ? 2006 James O’Daniell Neel

Analysis and Design of Cognitive Radio Networks and Distributed Radio Resource Management Algorithms
James O’Daniell Neel (Abstract) Cognitive radio is frequently touted as a platform for implementing dynamic distributed radio resource management algorithms. In the envisioned scenarios, radios react to measurements of the network state and change their operation according to some goal driven algorithm. Ideally this flexibility and reactivity yields tremendous gains in performance. However, when the adaptations of the radios also change the network state, an interactive decision process is spawned and once desirable algorithms can lead to catastrophic failures when deployed in a network. This document presents techniques for modeling and analyzing the interactions of cognitive radio for the purpose of improving the design of cognitive radio and distributed radio resource management algorithms with particular interest towards characterizing the algorithms’ steady-state, convergence, and stability properties. This is accomplished by combining traditional engineering and nonlinear programming analysis techniques with techniques from game to create a powerful model based approach that permits rapid characterization of a cognitive radio algorithm’s properties. Insights gleaned from these models are used to establish novel design guidelines for cognitive radio design and powerful low-complexity cognitive radio algorithms. This research led to the creation of a new model of cognitive radio network behavior, an extensive number of new results related to the convergence, stability, and identification of potential and supermodular games, numerous design guidelines, and several novel algorithms related to power control, dynamic frequency selection, interference avo idance, and network formation. It is believed that by applying the analysis techniques and the design guidelines presented in this document, any wireless engineer will be able to quickly develop cognitive radio and distributed radio resource management algorithms that will significantly improve spectral efficiency and network and device performance while removing the need for significant post-deployment site management.

ii

Table of Contents
Chapter 1: Cognitive Radio ................................................................................................ 1 1.1 Basic Cognitive Radio Concepts ........................................................................ 3 1.1.1 Defining “Cognitive Radio”........................................................................ 4 1.1.2 Related Terms ............................................................................................. 8 1.2 Cognitive Radio Implementation and Standardization..................................... 12 1.2.1 Radios........................................................................................................ 15 1.2.2 Cognitive Standards .................................................................................. 20 1.2.3 Institutional Initiatives .............................................................................. 23 1.3 Cognitive Radio Applications ........................................................................... 28 1.3.1 Improving spectrum utilization and efficiency......................................... 29 1.3.2 Improving Link Reliability ....................................................................... 33 1.3.3 Less Expensive Radios.............................................................................. 34 1.3.4 Advanced network topologies................................................................... 36 1.3.5 Collaborative Techniques ......................................................................... 37 1.3.6 SDR techniques enhanced by cognitive radio .......................................... 42 1.3.7 Automated Radio Resource Management ................................................. 44 1.4 Key Issues to Wide-Scale Deployment of Cognitive Radios ........................... 45 1.4.1 Regulatory Issues ...................................................................................... 46 1.4.2 Knowledge Representation....................................................................... 47 1.4.3 Improved Sensing Capabilities ................................................................. 48 1.4.4 Software Radio Issues ............................................................................... 49 1.4.5 Interactive Cognitive Radios..................................................................... 50 1.5 Problem Statement and Research Contributions and Document Organization 54 1.5.1 Problem Statement .................................................................................... 55 1.5.2 Research Contributions ............................................................................. 57 1.5.3 Document Organization............................................................................ 57 1.6 References ......................................................................................................... 60 Chapter 2: Modeling ......................................................................................................... 65 and Problem Formalization............................................................................................... 65 2.1 A General Model of Cognitive Radio Interactions ....................................... 65 2.2 Analysis Objectives....................................................................................... 73 2.3 Summary....................................................................................................... 77 2.4 References ..................................................................................................... 78 3.1 A Dynamical Systems Approach...................................................................... 79 3.1.1 Fixed Points and Solutions to Cognitive Radio Networks........................ 81 3.1.2 Establishing Optimality ............................................................................ 83 3.1.3 Convergence and Stability ........................................................................ 84 3.2 Contraction Mappings and the General Convergence Theorem.................................................................................................. 87 3.2.1 Contraction Mappings............................................................................... 88 3.2.2 Analysis Insights....................................................................................... 89 3.2.3 Pseudo-Contractions ................................................................................. 89 3.2.4 General Convergence Theorem ................................................................ 90 3.3 Markov Models ................................................................................................. 94

iii

3.3.1 Markov Model Analysis Insights .............................................................. 95 3.3.2 Ergodic Markov Chains ............................................................................ 96 3.3.3 Absorbing Markov Chains ...................................................................... 100 3.4 Summary......................................................................................................... 105 3.5 References ....................................................................................................... 107 Chapter 4: Game Theory................................................................................................. 109 4.1 Basic Elements of Game Theory .................................................................... 111 4.1.1 Basic Modeling Elements of a Game...................................................... 112 4.1.2 Mapping the Cognition Cycle to a Game ............................................... 117 4.2 Basic Game Models ........................................................................................ 119 4.2.1 Normal Form Games............................................................................... 119 4.2.2 Repeated Games...................................................................................... 121 4.3 Steady States ................................................................................................... 127 4.3.1 Nash Equilibrium .................................................................................... 128 4.3.2 Mixed Strategy Equilibria ....................................................................... 140 4.3.3 Enforceable Equilibria in Repeated Games ............................................ 142 4.4 Desirability...................................................................................................... 147 4.5 Convergence.................................................................................................... 153 4.5.1 Classes of Decision Dynamics ................................................................ 153 4.5.2 Stage Game Properties............................................................................ 156 4.5.3 Convergence Properties .......................................................................... 162 4.5.4 Convergence Summary and Conclusions ............................................... 169 4.6 Impact of Noise ............................................................................................... 172 4.6.1 Noise and Nash Equilibria ...................................................................... 173 4.6.2 Noise and Decision Processes................................................................. 174 4.6.3 Noise and Enforceable Equilibria ........................................................... 178 4.7 Analysis Summary and Design Implications .................................................. 182 4.7.1 Analysis Summary.................................................................................. 183 4.7.2 Design Implications ................................................................................ 185 4.8 References ....................................................................................................... 188 Chapter 5: Potential Games............................................................................................. 191 5.1 Potential Games .............................................................................................. 193 5.1.1 Potential Game Definitions ..................................................................... 193 5.1.2 Relationships between Potential Game Classes...................................... 199 5.2 Identification Techniques................................................................................ 200 5.2.1 Exact Potential Game Identification....................................................... 201 5.2.2 Ordinal Potential Game Identification.................................................... 211 5.3 Special Properties of Potential Games............................................................ 215 5.3.1 FIP and Potential Games......................................................................... 216 5.3.2 Approximate Finite Improvement Property (AFIP) ............................... 218 5.3.3 Improvement Path Implications of Equivalence Properties.................... 221 5.3.4 Continuity Properties of Potential Games............................................... 223 5.3.5 Net Improvement Properties of Exact Potential Games ......................... 225 5.3.6 Linear Space of Exact Potential Games .................................................. 227 5.4 Steady States of Potential Games ................................................................... 231 5.5 Optimality ....................................................................................................... 234

iv

5.6 Convergence of Potential Games .................................................................... 236 5.6.1 Decision Rule Classes ............................................................................. 236 5.6.2 Convergence in Finite Games................................................................. 237 5.6.3 Convergence in Infinite Games............................................................... 238 5.6.4 Convergence Rate (*).............................................................................. 247 5.7 Impact of Noise and Stability.......................................................................... 247 5.7.1 Operational State Characterization ......................................................... 247 5.7.2 Lyapunov Stability of Potential Games .................................................. 248 5.8 Analysis Summary and Design Implications .................................................. 254 5.8.1 Analysis Summary.................................................................................. 254 5.8.2 Design Implications ................................................................................ 257 5.8.3 Applications ............................................................................................ 259 5.9 References ....................................................................................................... 264 Chapter 6: Interference Reducing Networks................................................................... 267 6.1 Modeling and Terminology ............................................................................ 268 6.2 Related Work .................................................................................................. 269 6.3 IRN Properties................................................................................................. 272 6.3.1 IRN Steady State Properties.................................................................... 272 6.3.2 IRN Convergence and Stability Properties ............................................. 273 6.4 IRNs that Leverage External Information....................................................... 276 6.4.1 Globally Altruistic IRNs ......................................................................... 276 6.4.2 Locally Altruistic IRNs........................................................................... 277 6.5 IRN Protocols with Internally Generated Observations ................................ 278 6.5.1 Networks of Isolated Clusters................................................................. 280 6.5.2 Close Proximity Networks ...................................................................... 281 6.5.3 Controlled Observation Processes .......................................................... 284 6.6 Stabilizing IRNs.............................................................................................. 286 6.7 Legacy Devices and IRNs............................................................................... 288 6.8 IRN Summary and Conclusions ...................................................................... 291 6.9 References ....................................................................................................... 292 Chapter 7: Dynamic Frequency Selection ...................................................................... 295 7.1 Background ..................................................................................................... 297 7.1.1 Modeling DFS Algorithms ..................................................................... 297 7.1.2 Related Work .......................................................................................... 297 7.1.3 Interference Reducing Networks ............................................................ 300 7.2 An IRN DFS Algorithm.................................................................................. 301 7.2.1 Algorithm Details.................................................................................... 302 7.2.2 An 802.11h Application.......................................................................... 303 7.3 Algorithm under Non-Ideal Conditions .......................................................... 305 7.3.1 Policy Variations..................................................................................... 305 7.3.2 Asynchronous Timing............................................................................. 306 7.3.3 Private Frequency Preferences................................................................ 308 7.3.4 Effect of Estimations ............................................................................... 310 7.3.5 TPC and DFS .......................................................................................... 314 7.4 Summary and Conclusions ............................................................................. 316 7.4.1 Algorithm Summary ............................................................................... 316

v

7.4.2 How Game Theory Aided the Design..................................................... 317 7.4.3 Further Extensions .................................................................................. 318 7.5 References ....................................................................................................... 319 Chapter 8: Applications of Weak FIP ............................................................................. 321 8.1 Supermodular Games ...................................................................................... 322 8.1.1 Model Identification................................................................................ 322 8.1.2 Steady-states............................................................................................ 322 8.1.3 Desirability.............................................................................................. 323 8.1.4 Convergence............................................................................................ 323 8.1.5 Stability (*) ............................................................................................. 324 8.2 Ad-hoc Power Control .................................................................................... 325 8.2.1 Stage Game Model.................................................................................. 325 8.2.2 Analysis................................................................................................... 326 8.2.3 Validation................................................................................................ 328 8.3 Sensor Network Formation (*) ....................................................................... 329 8.3.1 Model...................................................................................................... 330 8.3.2 Steady-states............................................................................................ 331 8.3.3 Convergence............................................................................................ 332 8.4 Conclusions ..................................................................................................... 337 8.4.1 Analysis Summary.................................................................................. 337 8.4.2 Design Implications ................................................................................ 338 8.5 References ....................................................................................................... 339 Chapter 9: Conclusions ................................................................................................... 340 9.1 Modeling and Analysis Summary................................................................... 343 9.2 Design Summary............................................................................................. 348 9.3 Research Contributions ................................................................................... 350 9.3.1 Publications ............................................................................................. 350 9.3.2 External Citations .................................................................................... 352 9.4 Future Work .................................................................................................... 354 9.4.1 Research Topics ...................................................................................... 354 9.4.2 Planned Publications ............................................................................... 356

vi

List of Figures
Figure 1.1: Cognition cycle. Reproduced from Figure 4-2 [Mitola_00] .......................... 14 Figure 1.2: CR1 Natural Language Architecture from Figure 8-3 in [Mitola_00]........... 15 Figure 1.3: DARPA XG High- Level Architecture from [IEEE 1900.1] .......................... 16 Figure 1.4: Biologically Inspired Cognitive Radio Architecture from Figure 3.4 in [Rieser_04]................................................................................................................ 17 Figure 1.5: Updated Biologically Inspired Cognitive Radio Architecture [Le_06] ......... 18 Figure 1.6: CORTEKS Components and Interface........................................................... 19 Figure 1.7: Adapt4’s XG1 Cognitive Radio. Image from http://www.adapt4.com/......... 20 Figure 1.8: Cognitive Radio Applications ........................................................................ 28 Figure 1.9: Spectrum availability by band. Adapted from Figure 1 in [McHenry_05]. ... 30 Figure 1.10: Matlab capture of channel measurements from Germany [Jondral_04] ...... 31 Figure 1.11: Conceptual example of opportunistic spectrum utilization.......................... 32 Figure 1.12 Path and associated signal quality for a cognitive radio................................ 33 Figure 1.13: Opportunistic spectrum utilization in the presence of device with significant signal degradation. .................................................................................................... 35 Figure 1.14: Star and Ad-hoc Topologies ......................................................................... 36 Figure 1.15: Conceptual operation of 802.16j Modified from Fig 1 in IEEE 802.16mmr05/032........................................................................................................................ 38 Figure 1.16: Distributed Antenna Array Possibilities ....................................................... 40 Figure 1.17: An example of ad- hoc beam forming that would have negative effects on network performance. ............................................................................................... 43 Figure 1.18: The interactive cognitive radio model. Reproduced from Figure 15-1 in [Neel_06a]................................................................................................................. 51 Figure 1.19: A network of adaptive radios that has fallen into an infinite adaptation recursion. ................................................................................................................... 52 Figure 1.20: Initial network state. ..................................................................................... 53 Figure 1.21: Final network state. ...................................................................................... 53 Figure 1.22: A three radio interaction diagram with three steady states (NE1 , NE2 , and NE3) and adaptation paths. ....................................................................................... 54 Figure 2.1: The interactive cognitive radio problem. [Neel06] ........................................ 66 Figure 2.2: A three radio interaction diagram with three steady states (NE1 , NE2 , and NE3) and adaptation paths. ....................................................................................... 74 Figure 3.1: A function with three fixed points (circled). For functions on a one dimensional sets, the points at which the function intersect the line f (x ) = x (dashed) are fixed points.......................................................................................................... 82 Figure 3.2: f (x , y) = xy, x , y > 0 – A function that is pseudo-concave, but not concave. .. 84 Figure 3.3: Paths (formed by recursive application of d t with direction indicated by arrows) fo r a system that is Lyapunov stable but not attractive. .............................. 86 Figure 3.4: Paths for a fixed point that is attractive but not Lyapunov stable. ................. 86 Figure 3.5: A sequence of contracting sets, L ? A ( t 2 ) ? A ( t 1 ) ? A ( t 0 ) . ...................... 88 Figure 3.6 Digraph Representation of (3.12) .................................................................... 99 Figure 3.7: Digraph of DFS Example ............................................................................. 104 Figure 4.1: Cognition Cycle and Game Components. Modified from Figure 4.2.2 in [Mitola_00] ............................................................................................................. 118 vii

Figure 4.2: Matrix Form Representation of Paper-Rock-Scissors .................................. 120 Figure 4.3: Frequency domain representation of waveforms in the Cognitive Radios’ Dilemma [Neel_06]................................................................................................. 121 Figure 4.4: The Cognitive Radios’ Dilemma in Matrix Form [Neel_06] ....................... 121 Figure 4.6: A Repeated Game of Paper-Rock-Scissors [Neel_06] ................................. 124 Figure 4.7: A Repeated Two Player Cognitive Radio Game [Neel_06]......................... 127 Figure 4.8: Prisoners’ Dilemma Matrix Form Representation ....................................... 130 Figure 4.9: Abstract Representation of the Prisoners' Dilemma Game Matrix .............. 130 Figure 4.10: The Cognitive Radios’ Dilemma. This game has a unique NE at (w, W). . 131 Figure 4.11: A Channel Selection Game ........................................................................ 132 Figure 4.12: A Channel Construction Game ................................................................... 133 Figure 4.13 Visualization of Kakutani’s Fixed Point Theorem in Two Dimensions. .... 135 Figure 4.14: A function that is quasi-concave but neither concave nor pseudo-concave. From Figure 15.3-15 in [Neel_06a] ........................................................................ 136 Figure 4.16: General Shape of Utility Function Given in (4.5). ..................................... 138 Figure 4.17: Cognitive Radios’ Dilemma ....................................................................... 143 Figure 4.18 Improvement in Utilities from Enforcing a non-NE Equilibrium. .............. 145 Figure 4.19: A Game Where Players Would Desire to Enforce Different Equilibria .... 147 Figure 4.20: The Cognitive Radios’ Dilemma has Three Pareto Optimal Action Vectors. ................................................................................................................................. 148 Figure 4.21 Prisoners’ Dilemma Game Matrix for Improvement Path Analysis ........... 158 Figure 4.22: A game with weak FIP. (Taken from Figure 2 in [Neel_04a]) The game has an improvement cycle (shown in the arrow) and a NE (circled). ........................... 159 Figure 4.23: A Coordination Game which Can Fail to Converge for the Random Better Response of [Friedman_01] for Synchronous Timings. ......................................... 166 Figure 4.24 A Game with an NE, but not Weak FIP, FIP, or IESDS. ............................ 170 Figure 4.25 Percentage of Runs where a Cascade of Punishments Occurred due to Imperfect Signaling [Srivastava_06a]..................................................................... 181 Figure 5.1: A Game with FIP but no Ordinal Potential [Monderer_96]......................... 198 Figure 5.2: Generalized Ordinal Potential Function for Game in Figure 5.1 ................. 198 Figure 5.3: Potential Game Venn Diagram. Adapted from Fig.1 in [Voorneveld_00] .. 200 Figure 5.4 Relaxed Coordination Game ......................................................................... 202 Figure 5.5 Prisoners' Dilemma Game Matrix ................................................................. 207 Figure 5.6: Coordination-Dummy Game Representation of a Prisoners' Dilemma ....... 207 Figure 5.7: BSI Representation of Prisoners’ Dilemma. ................................................ 208 Figure 5.8: A Generalized Ordinal Potential Game. ....................................................... 213 Figure 5.9: An Ordinal Potential Game. ......................................................................... 213 Figure 5.10 Exact Potential Game Γ ............................................................................... 226 Figure 5.11 Exact Potential Games................................................................................. 229 Figure 5.12 Exact Potential Functions ............................................................................ 229 Figure 5.13: Ordinal Potential Games ............................................................................ 229 Figure 5.14: Ordinal Potential Functions ........................................................................ 229 Figure 5.15: A Game Formed by Additive Combination of Ordinal Potential Games. . 230 Figure 5.16: Coordination Game With Synchronous Play ............................................. 237 Figure 5.17: Radio Distribution...................................................................................... 246 Figure 5.18: Network Behavior Under Best Response Decision Rules.......................... 246

viii

Figure 5.19: Network Behavior Under Averaged Best Response Decision Rules ......... 246 Figure 5.20: Network Behavior Under Intelligent Random Better Response Decision Rules........................................................................................................................ 246 Figure 5.21: Network Behavior Under Random Better Response Decision Rules ........ 246 Figure 5.22: Network Behavior Under ε -Better Response Decision Rules .................... 246 Figure 5.23: Network Behavior Under Best Response Decision Rules.......................... 253 Figure 5.24: Network Behavior Under Averaged Best Response Decision Rules ......... 253 Figure 5.25: Network Behavior Under Intelligent Random Better Response Decision Rules........................................................................................................................ 253 Figure 5.26: Network Behavior Under Random Better Response Decision Rules ........ 253 Figure 5.27: Network Behavior Under ε -Better Response Decision Rules .................... 253 Figure 5.28: SINR levels under Best Response Adaptations of Signature Sequences from Figure 2 in [Menon_04]. ......................................................................................... 263 Figure 6.1: Impact of Asynchronous Decision Timings ................................................. 275 Figure 6.2: Simulation of seven code adapting cognitive radios operating in an isolated cluster. [Neel_06a].................................................................................................. 281 Figure 6.3: Simulation of a close proximity network. .................................................... 284 Figure 6.4: Simulation of a close proximity network. .................................................... 284 Figure 6.5 30 randomly distributed DFS nodes adapting to interference measured at the transmitter. .............................................................................................................. 286 Figure 6.6 Simulation of system in Figure 6.5 with different initial frequencies. .......... 286 Figure 6.7 Simulation of system in Figure 6.5 where interference estimates are corrupted by noise. .................................................................................................................. 287 Figure 6.8 Simulation of system in Figure 6.5 where interference estimates are corrupted by noise, but threshold adaptations are employed. ................................................. 287 Figure 6.9: Code adaptation in a noisy ad-hoc network. ................................................ 288 Figure 6.10: Code adaptation in a noisy ad-hoc network where adaptations only occur if interference decreases interference by at least τ. .................................................... 288 Figure 6.11: Noisy simulation of system in Figure 6.5 where five devices are incapable of adapting. .................................................................................................................. 290 Figure 6.12: Noisy simulation of system in Figure 6.5 where five devices are incapable of adapting, and the rest implement a threshold adaptation. ....................................... 290 Figure 7.1: Frequency Assignment Algorithm in [Steenstrup_05]................................. 298 Figure 7.2: Steady-state Channels Selected for a Random Distribution of Access Nodes with Random Initial Channels in the 5.47-5.725 GHz Band. ................................. 304 Figure 7.3: Instantaneous Statistics for Network in Figure 7.2. ..................................... 305 Figure 7.4: Instantaneous Statistics with Policy Variations ............................................ 306 Figure 7.5: Impact of Asynchronous Decision Timings ................................................. 308 Figure 7.6: Algorithm with Private Frequency Preferences ........................................... 310 Figure 7.7: Algorithm with Stochastic Estimations. ....................................................... 312 Figure 7.8: Algorithm with Stochastic Estimations and a small adaptation threshold (-85 dBm)........................................................................................................................ 313 Figure 7.9: Algorithm with TPC Applied to RTS/CTS. ................................................. 316 Figure 8.1: Simulation scenario for ad-hoc power control example............................... 328 Figure 8.2: Noiseless simulation. .................................................................................... 329 Figure 8.3: Noisy simulation. .......................................................................................... 329

ix

List of Tables
Table 1.1: Cognitive Radio Definition Matrix.................................................................... 7 Table 1.1: Levels of cognitive radio functionality. Adapted from Table 4-1 [Mitola_00]. ................................................................................................................................... 13 Table 1.2: Major Novel Contributions Made as Part of this Work................................... 59 Table 2.1: Parameters for Example Model ....................................................................... 73 Table 2.2: Symbol Summary ............................................................................................ 77 Table 3.1: Presented Models ........................................................................................... 105 Table 3.2 Steady-State Properties by Model................................................................... 106 Table 3.3 Convergence Properties by Model.................................................................. 106 Table 3.4 Stability Properties by Model ......................................................................... 107 Table 4.1 Relationships Between Game Elements ......................................................... 113 Table 4.2: Related Modeling Elements in a Game and a Cognitive Radio Network ..... 118 Table 4.3 Considered Classes of Dynamics.................................................................... 154 Table 4.4 Improvement Paths for Game Presented in Figure 4.21 ................................. 159 Table 4.5 Transition Matrix for Random Timing ........................................................... 163 Table 4.6 Transition Matrix for Asynchronous Timing.................................................. 164 Table 4.7 Expected Convergence Times to (H,H,H) for Different Initial States for Random Timing................................................................................................. 164 Table 4.8 Expected Convergence Times to (H,H,H) for Different Initial States for Asynchronous Timing ....................................................................................... 164 Table 4.9: The Markov Transition Matrix for the Game in Figure 4.23 with Synchronous Timings and Decision Rule of Definition 4.13 ....................................................... 167 Table 4.10: The Markov Transition Matrix for the Game in Figure 4.23 with Synchronous Timings and Decision Rule of Definition 4.13. ................................ 168 Table 4.11: Convergence Criteria ................................................................................... 170 Table 4.12: Link Gain Matrix ......................................................................................... 176 Table 4.13 Noiseless Observations ................................................................................. 176 Table 4.14 Transition Matrix for Better Response, Trembling Hand, ρ=0.1, and Random Timing ...................................................................................................... 177 Table 4.15: Transition Matrix for Best Response and Random Timing with Observations Corrupted by N(0,1) Gaussian Noise ..................................................................... 178 Table 4.16: Steady State Distributions for a Standard Deviation of 1 ............................ 178 Table 4.17: Steady State Distributions Different Standard Deviations .......................... 178 Table 5.1: Unilateral Deviation Relationships for Γ and V............................................. 194 Table 5.2: Unilateral Deviation relationships for Γ and V .............................................. 196 Table 5.3: Unilateral Deviation relationships for Γ and V .............................................. 197 Table 5.4: Improvement Paths for Game in Figure 5.1 .................................................. 198 Table 5.5 Common Exact Potential Game Forms .......................................................... 206 Table 5.6: Guaranteed Convergence Conditions for Finite Potential Games ................. 238 Table 5.7: Guaranteed Convergence Conditions for Infinite Potential Games with FIP 239 Table 5.8: Convergence Criteria for Potential Games .................................................... 256 Table 5.9: Utility Functions in [Hicks_04a] ................................................................... 264 Table 7.1: Other Conditions Guaranteed to Converge to a Low Interference State ....... 318 Table 9.1: Presented Models ........................................................................................... 344

x

Table 9.2 Steady-State Properties by Model................................................................... 345 Table 9.3: Convergence Properties by Model................................................................. 346 Table 9.4: Stability Properties by Model ........................................................................ 347 Table 9.5: Major Novel Contributions Made as Part of this Work................................. 350

xi

List of Examples
Example 2.1: Example: Modeling a Cognitive Radio Algorithm ...................... 71 Example 3.1: Markov Model of Cognitive Radio Adaptations .......................... 98 Example 3.2: DFS as an Absorbing Markov chain ............................................ 103 Example 4.1: Modeling a Game of Paper Rocks Scissors .............................. 120 Example 4.2: The Cognitive Radios’ Dilemma ................................................... 121 Example 4.3: Paper-Rock-Scissors Repeated Game ....................................... 123 Example 4.4: Mobile Assisted Power Control .................................................... 125 Example 4.5: FM-AM-Spread Spectrum Repeated Game ................................ 127 Example 4.6: Prisoners’ Dilemma .......................................................................... 129 Example 4.7: Identifying the NE of Cognitive Radios’ Dilemma ................... 130 Example 4.8 Existence of a NE in a Power Control Game .............................. 137 Example 4.9: Cournot Oligopoly and Bandwidth Selection ........................... 138 Example 4.10: Paper-Rock-Scissors in Mixed Strategies ............................... 141 Example 4.11 Punishment and Power Control................................................... 144 Example 4.12: SINR maximizing power control ................................................. 149 Example 4.13: Improvement Paths in the Prisoners’ Dilemma ..................... 158 Example 4.14 A Game with Weak FIP ................................................................... 159 Example 4.15 Friedman’s Generic Two-Player Quasi-Concave Game ........ 161 Example 4.16 Convergence of SINR Maximizing Power Control .................. 163 Example 4.17: Noisy DFS Decision Processes.................................................. 176 Example 5.1: A 2x2 Exact Potential Game .......................................................... 194 Example 5.2: A 2x2 Weighted Potential Game ................................................... 195 Example 5.3: A 2x2 Ordinal Potential Game ....................................................... 197 Example 5.4: Coordination-Dummy Game .......................................................... 202 Example 5.5: A Bilateral Symmetric Interaction (BSI) ...................................... 206 Example 5.6: Distributed Channel Assignment ................................................. 210 Example 5.7: Ordinal Potential Games and ........................................................ 213 Example 5.8: Zeno’s Game ...................................................................................... 218 Example 5.9: Identifying An Ordinal Potential Game ....................................... 223 Example 5.10: An Ordinal Potential Game without a Continuous Potential Function [Voorneveld_97b]............................................................................. 225 Example 5.11: Example Calculation of Net Improvement ............................... 226 Example 5.12: Linear Combination of Exact Potential Games ...................... 229 Example 5.13: Linear Combination of Ordinal Potential Games ................... 229 Example 5.14: Target SINR Power Control (*) .................................................... 230 Example 5.15: Convergence of a Power Control Potential Game ................. 244 Example 5.16: Stability of a Power Control Potential Game .......................... 251

xii

Acknowledgements
Throughout my academic career my mother, Dee Neel, had been the most dedicated editor imaginable. In grade school, she would stay up with me through the night to proof read and catch the typos and grammatical mistakes which littered my early writing. Fortunately, her efforts ensured that those mistakes became less frequent over time. Years later when I needed a thorough review of my Master’s Thesis and my first two textbook chapters, she patiently read every word I wrote even though she lacked the technical background to understand the material. Because of its importance to my career and the time required to closely proof read this document, I knew that she would again be my ideal copy editor. Unfortunately, she succumbed to cancer on March 25 of this year before the bulk of this dissertation was written. While this document would benefit from her watchful eye, it still reflects her 29 years of patient instruction and editing. Throughout this time my wife, Preethi, my father, Dr. James B. Neel, and my brother, David, have been a source of love, support, and encouragement. This document also reflects my interactions with the thriving cognitive radio research community at Virginia Tech. My advisor, Dr. Jeffrey Reed, has been instrumental to the framing, emphasis, scope, and direction of this research. Much of my success can be attributed to the numerous doors he opened for me and his guidance over the last seven years. It is doubtful that I would have made it beyond my first year in grad school with any other advisor when I placed too little emphasis on my class work. Yet, he believed in me and pushed me and now I have accomplished far more than I would have thought possible seven years ago. I have also been quite fortunate to have a committee so actively involved in my research. In a rare event for PhD research, particularly in light of the size of the field, two committee members – Dr. Allen MacKenzie and Dr. Luiz DaSilva – wrote their dissertations on closely related topic of game theory and communication networks and have been an invaluable resource to this research. It was actually a presentation by Dr. MacKenzie at Globecom in 2001 that convinced me that the analysis of cognitive radio

xiii

and adaptive software radio networks would be a feasible undertaking. Dr. Robert Gilles was the source of my initial training in game theory and my initial introduction to potential games – the topic and application of which served as a significant fraction of my research. Though lacking an engineering background, Dr. Gilles has been an enthusiastic partner in this research and an invaluable aid in the refinement of theory. A co-author and the presenter of my first paper on game theory and cognitive radio, Dr. R. Michael Buehrer’s insistence that I justify the significance and novelty of this research led to numerous insights into what game theory contributed to the design of cognitive radio networks. Additionally, numerous others at Virginia Tech have contributed to this research. Samir Ginde, James Hicks, Rekha Menon, Ramakant Komali, and Vivek Srivastava have all served as collaborators and colleagues who could discuss the intricacies of this research. Through numerous conversations, Dr. Charles Bostian, David Maldonado, Tom Rondeau, Bin Le, Joseph Gaeddert, Kyouwoong Kim, Youping Zhao, Juan Suris, Lizdabel Morales, and Ryan Thomas have provided insights into the operation and implementation of cognitive radio. Outside of Virginia Tech, this research has been enhanced by conversations with Dr. Bruce Fette of General Dynamics, Dr. Joe Mitola of Mitre, and engineers at G eneral Dynamics, Lockheed-Martin ATL, and SBC Technologies. Of course much less of this research would have been accomplished without the stable funding source provided by an NSF IGERT Fellowship administered by Dr. Scott Midkiff under NSF grant # 9983463. Travel funding was provided by the Office of Naval Research grant # N000140310629 and the initial research was sponsored by Motorola under a University Partnership in Research Grant and the Affiliates of MPRG. I would also like to thank the faculty and staff of MPRG for their help, Dr Annamalai Annamalai for participating in my qualifying exam, and the members of VT-ACO for their friendship and intellectual stimulation.

xiv

Chapter 1: Cognitive Radio
“Cogito, ergo sum. [I think, therefore I am]” – René Descartes Aided by advances in processors, RF technology, and software, software radio technology has rapidly progressed since the coining of the term “software radio” by Joe Mitola in 1991 [Mitola_00]. Software radio (SDR) currently forms the core of the US military’s multi-billion-dollar-a-year Joint Tactical Radio System (JTRS) which has resulted in SDRs being fielded by Gene ral Dynamics (DMR [GDDS]), Thales (JEM [Thales]), and Harris (RF-300M-HH [Harris]), to name a few. Beyond the military, commercial standards are beginning to be preferably implemented in software (802.16 [Picochip]) and commercial base stations are being implemented as software radios (Vanu [Vanu]). The reality of software radio and the support for moving a single radio through multiple standards has led the Institute of Electrical and Electronics Engineers (IEEE) to begin standardizing vertical handoffs between networks employing different standards (802.21 [802.21]). However, the numerous envisioned applications for SDR – multiband multimode radio, porting waveforms across platforms, over-the-air updates – are accompanied by the numerous envisioned problems – viruses or worms that render the radio unusable, unforeseen software/hardware combinations that turn radios into jammers, and cell phones that crash to reveal a “blue screen of death.” Accordingly, SDR research and development has focused as much on overcoming the problems created by SDR as it has the opportunities and realization of SDR. Now consider a radio that autonomously detects and exploits empty spectrum to increase your file transfer rate. Suppose this same radio could remember the locations where your calls tend to drop and arrange for your call to be serviced by a different carrier for those locations. These are some of the ideas motivating the development of cognitive radio 1 . In effect, a cognitive radio is a software radio whose control processes leverage situational knowledge and intelligent processing to work towards achieving some goal related to the
1

This term, too, was coined by Mitola in 1999 [Mitola_99].

1

needs of the user, application, and/or network. Arising from a logical evolution of the control processes of a software radio, cognitive radio presents the possibility of numerous revolutionary applications. Opportunistic spectrum utilization can find available spectrum in a crowded network, leading to 10- fold gains in capacity [Marshall_05a]. By learning their environment, cognitive radio s can dramatically improve link reliability and help networks autonomously improve coverage and capacity. True radio interoperability can be achieved when radios learn to autonomously negotiate services and protocols. Smart collaborative signaling techniques promise significant range extension and data-rate increases. Advanced network topologies can dramatically extend coverage and increase bandwidth. The global roaming of radios can be dramatically simplified when a radio is responsible for autonomously detecting the location specific operating requirements. Autonomous determination of bandwidth requirements and spectrum availability will greatly enhance the opportunities for rapid reallocation of spectrum resources. Finally, smart spectrum use can overcome the deficiencies of inexpensive analog components allowing lower-priced radios to be fielded [Marshall_05a]. But what’s to say that cognitive radios will not act maliciously – opportunistic spectrum use into spectrum bullying? Given the infinite number of environments that a radio will encounter and a design that how can we hope to verify that the radio will behave as intended? How can we be certain that radios will be able to even recognize the opportunities they are presented? What if the interaction of several seemingly benign algorithms yield disastrous network behavior – something that seems all too possible once selfish radios are competing for spectrum? This work concentrates on this last problem – the interaction of cognitive radios in distributed radio resource management settings – by developing techniques for modeling and analyzing cognitive radio algorithms to determine steady-states, convergence, and stability and by developing frameworks for designing cognitive radio algorithms that yield good performance for the radio and for the network. Beyond cognitive radio, the

2

techniques developed and presented in this work can also be extended to the modeling, analysis, and design of distributed and automated radio resource management. Serving as a foundation on which to build the subsequent models, analysis techniques and development frameworks, this chapter focuses on the concept, implementation, and applications of cognitive radio and is organized as follows. Section 1.1 formally defines cognitive radio and differentiates cognitive radio from some closely related terms. Section 1.2 discusses high- level implementation aspects of cognitive critical to understanding the analysis of interactive cognitive radio. Section 1.3 discusses some of the frequently discussed applications of cognitive radio and some limited current deployments of cognitive radio. Section 1.4 presents some of the major technical hurdles that must be cleared for widespread deployment of cognitive radio. Section 1.5 briefly overviews the objectives and original contributions of this work. Section 1.6 presents work related to the big-picture objectives of this work and outlines the material to be presented over the remainder of the text.

1.1 Basic Cognitive Radio Concepts
While the cognitive radio community has had significant success popularizing the concept of cognitive radio and developing prototypes, applications, and critical components, the community has had a surprisingly difficult time agreeing upon exactly what is and is not a cognitive radio beyond. Perhaps echoing the sentiment of former Supreme Court Justice Potter Stewart, many members of the cognitive radio community believe that “they know it when they see it,” even if a precise definition is ineffable. Some have succeeded in formulating a definition of cognitive radio but have found their definitions at significant variance with others’ definitions. While these definitions are likely to converge over time from either an international consensus (the goal of IEEE 1900.1 group) or from a de facto definition taken from the first cognitive radio to dominate the market, this dissertation must plunge ahead with some formalization of cognitive radio and related concepts to formally analyze their interactions. To that end, the remainder of this introductory section presents a definition of cognitive radio that is hopefully suitably encompassing and discriminating for other researchers to use and reasonably well- justified by its preceding discussion. To enhance 3

the offered definition’s usefulness, terms frequently discussed in relation to cognitive radio are subsequently defined and differentiated from cognitive radio.

1.1.1 Defining “Cognitive Radio”
Tautologically, a cognitive radio could be defined as “A radio that is cognitive,” or paraphrasing Descartes, “ Cogitat, ergo est cognitive radio.”2 In the absence of a Turing test for radios, applying this definition is nontrivial and implies a level of functionality that many researchers consider excessive. Indeed, while many researchers and public officials agree that upgrading a software radio’s control processes will add significant value to software radio, there is currently some disagreement over how much “cognition” is needed which results in disagreement over the precise definition of a cognitive radio. The following provides some of the more prominently offered definitions of cognitive radio. In the 1999 paper that first coined the term “cognitive radio”, Joseph Mitola III defines a cognitive radio as [Mitola_99]: “A radio that employs model based reasoning to achieve a specified level of competence in radio-related domains.” However, in his recent popularly cited paper that surveyed the state of cognitive radio, Simon Haykin defines a cognitive radio as [Haykin_05]: “An intelligent wireless communication system that is aware of its surrounding environment (i.e., outside world), and uses the methodology of understanding-by-building to learn from the environment and adapt its internal states to statistical variations in the incoming RF stimuli by making corresponding changes in certain operating parameters (e.g., transmit-power, carrierfrequency, and modulation strategy) in real-time, with two primary objectives in mind: ? ? highly reliable communications whenever and wherever needed; efficient utilization of the radio spectrum.

2

It thinks, therefore it’s a cognitive radio.

4

Coming from a background where regulations focus on the operation of transmitters, the FCC has defined a cognitive radio as [FCC_05]: “A radio that can change its transmitter parameters based on interaction with the environment in which it operates.” Meanwhile, the other primary spectrum regulatory body in the US, the NTIA [NTIA_05], adopted the following definition of cognitive radio that focuses on some of the applications of cognitive radio: “A radio or system that senses its operational electromagnetic environment and can dynamically and autonomously adjust its radio operating parameters to modify system operation, such as maximize throughput, mitigate interference, facilitate interoperability, and access secondary markets.” The international spectrum regulatory community in the context of the ITU Wp8A working document is currently working towards a definition of cognitive radio that focuses on capabilities as follows: “A radio or system that senses and is aware of its
operational environment and can dynamically and autonomously adjust its radio operating parameters accordingly.”

While aiding the FCC in its efforts to define cognitive radio, IEEE USA offered the following definition [IEEEUSA_03]: “A radio frequency transmitter/receiver that is designed to intelligently detect whether a particular segment of the radio spectrum is currently in use, and to jump into (and out of, as necessary) the temporarily-unused spectrum very rapidly, without interfering with the transmissions of other authorized users.” The broader IEEE tasked the IEEE 1900.1 group to define cognitive radio which has the following working definition [IEEE 1900.1]: “A type of radio that can sense and autonomously reason about its environment and adapt accordingly. This radio could employ knowledge representation, automated reasoning and machine learning mechanisms in establishing, conducting, or terminating communication or networking functions with other radios. Cognitive radios can be trained to dynamically and autonomously adjust its operating parameters.”

5

Likewise, the SDR Forum participated in the FCC’s efforts to define cognitive radio and has established two groups focused on cognitive radio. The Cognitive Radio Working Group focused on identifying enabling technologies uses the following definition: “A radio that has, in some sense, (1) awareness of changes in its environment and (2) in response to these changes adapts its operating characteristics in some way to improve its performance or to minimize a loss in performance.” However, the SDR Forum Special Interest Group for Cognitive Radio, which is developing cognitive radio applications, uses the following definition: “An adaptive, multi-dimensionally aware, autonomous radio (system) that learns from its experiences to reason, plan, and decide future actions to meet user needs.” Finally, the author of this text participates in the Virginia Tech Cognitive Radio Working Group which has adopted the following capability- focused definition of cognitive radio [VT CRWG]: “An adaptive radio that is capable of the following: a) awareness of its environment and its own capabilities, b) goal driven autonomous operation, c) understanding or learning how its actions impact its goal, d) recalling and correlating past actions, environments, and performance.” While it appears to be unlikely that there will be a harmonization of these definitions in the near future, an examination of the salient functionalities of these definitions, as summarized in Table 1.1, reveals some commonalities among these definitions. First, all of these definitions assume that cognition will be implemented as a control process, presumably as part of a software defined radio. Second, all of the definitions at least imply some capability of autonomous operation. Finally, the following are some general capabilities found in all of the definitions: 1. Observation – whether directly or indirectly, the radio is capable of acquiring information about its operating environment. 2. Adaptibility – the radio is capable of changing its waveform.

6

3. Intelligence – the radio is capable of applying information towards a purposeful goal. Table 1.1: Cognitive Radio Definition Matrix. No interference

Adapts (Intelligently)

Can sense Environment

“Aware” Environment

Learn the Environment

Autonomous

Goal Driven

“Aware” Capabilities

Transmitter

Negotiate Waveforms

Receiver

Definer FCC Haykin IEEE 1900.1 IEEE USA ITU-R Mitola NTIA SDRF CRWG SDRF SIG VT CRWG

? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

Note that this definition of intelligence 3 implies that even those definitions that do not explicitly mention a goal (or provide a specific goal such as performance) still implicitly require the existence of some goal for intelligent adaptation. By using only these common features of all these definition we arrive at the definition of cognitive radio given in Definition 1.1. Definition 1.1 : Cognitive Radio (*) 4 A cognitive radio is a radio whose control processes permit the radio to leverage situational knowledge and intelligent processing to autonomously adapt towards some goal.

3

Intelligence as defined by [American Heritage_00] as “The capacity to acquire and apply knowledge, especially toward a purposeful goal.” The definition for intelligence as applied to cognitive radio differs only in that the acquisition of knowledge has been subsumed into the observation process. 4 The asterik denotes that this definition is original to the author. Throughout this document when chapters present both original and prior work by others, original definitions and theorems are noted by an asterik.

7

Throughout the remainder of this text Definition 1.1 will be what is meant when the phrase “cognitive radio” is used. When different capabilities (sometimes more, sometimes less, sometimes more specific) are required, we will make use of different terms defined in the following section.

1.1.2 Related Terms
As part of our discussion of cognitive radio, we will find it useful to rigorously define some related terms. Specifically we will find it useful to make use of the terms software defined radios, policy based radios, procedural radios, and ontological radios. The logical authority for a definition of software defined radio, the Software Defined Radio Forum defines a software defined radio (SDR) as shown in Definition 1.2 [SDR Forum_05]. Definition 1.2 : Software Defined Radios (SDRs ) “Radios that provide software control of a variety of modulation techniques, wide-band or narrow-band operation, communications security functions (such as hopping), and waveform requirements of current and evolving standards over a broad frequency range. The frequency bands covered may still be constrained at the front-end, however, requiring a switch in the antenna system.” While others5 consider Definition 1.2 to be that of a “software controlled radio, ” this text will utilize the definition of SDR provided by the SDR Forum and will refer to radios whose functionality is primarily realized in software as “software implemented radios.” While a radio could be implemented via software or hardware and controlled via software, the emphasis on software control is important to the cognitive radio concept as software control permits rapid adaptation of the radio’s operation – perhaps as short as the time required to readdress a program address counter – and provides a logical mechanism on which to implement a cognitive radio’s “ control processes [that] permit the radio to leverage situational knowledge and intelligent processing to autonomously adapt towards achieving some goal.” It should be pointed out that while many treat that cognitive radio as an SDR with enhanced control processes (as was done in the introduction to this chapter), some researchers correctly emphasize that a cognitive radio
5

Here, the term “others” includes this author.

8

need not be implemented on an SDR as the control processes could be implemented in hardware and indeed have implemented a hardware cognitive radio [Rondeau_04]. However, such “hardware controlled cognitive radios” appear likely to share the fate of Babbage’s Analytical Engine due to the far greater flexibility and ease of programming provided by SDR cognitive radios. Although the definition of the term waveform is a frequent point of discussion at conferences due to variances in usage, we have used the term repeatedly throughout the preceding and hope its usage has been clear from context up to this point. However, as we just wrote “waveform requirements” as part of a formal definition, completeness dictates we formally define waveform. Definition 1.3 : Waveform (*) A protocol that specifies the shape of an electromagnetic signal intended for transmission by a radio. Implicit to Definition 1.3 is the fact that a waveform is not solely defined by its physical layer algorithms. If specified as part of the protocol, then link layer, network layer, transport layer, and application layer algorithms will all influence the shape of the electromagnetic signal. However, not all waveforms specify algorithms at all layers. For example the FM broadcast radio waveform is a purely physical layer standard. In general, the only influence of signal shape that is excluded from the term “waveform” is the information bits being carried by the signal. Because cognitive radios and SDRs could conceivably be configured (or autonomously configure themselves) to implement almost any waveform, spectrum regulators need some mechanism to ensure that cognitive and software defined radios have a limited impact on licensed systems. To provide this mechanism, many researchers have proposed the use of policy radios. The IEEE 1900.1 group currently defines a policy radio as given in Definition 1.4 [IEEE 1900.1]. Definition 1.4 : Policy Radio “A radio that is governed by a set of rules for choosing between different waveforms. The definition and implementation of these rules can be: ? during the manufacturing process ? during configuration of a device by the user;

9

? during over-the-air provisioning; and/or ? by over-the-air control.” Particularly for cognitive radios, it is convenient to refer to the set of set of rules as the radio’s policy and a policy radio that is also a cognitive radio as a cognitive policy radio. In practice, a policy might specify a spectral mask which defines a set of maximum transmission powers for a number of different frequency bands that are specific to a particular location. Then as the policy-based radio is moved around the world, the policybased cognitive radio would be responsible for inferring and applying the policy that applies to its particular location, perhaps via GPS, a radio environment map [Zhao_06], or from a primary spectrum holder. Because of the needs of spectrum regulators and primary spectrum holders, it is expected that all cognitive radios will eventually be cognitive policy radios. In fact, the incorporation of policy into cognitive radio has been a major focus of DARPA’s xG program [Marshall_06]. Especially a ssuming the use of an SDR platform, the actual implementation of the cognitive and policy-related processes permits significant variation. The more traditional approach implements the control processes in a procedural language, such as C, where the adaptations spawned from specific observations can be traced to a specific pre-coded function. Such a cognitive radio is termed a procedural cognitive radio which is more formally defined as given in Definition 1.5. [Neel_06] Definition 1.5 : Procedural Cognitive Radio (*) A cognitive radio whose adaptations are determined by hard coded algorithms and informed by observations. Most implemented cognitive radio prototypes exhibit a significant degree of hard coding in their adaptation algorithms and are thus procedural cognitive radios. This includes Adapt4’s xG1 cognitive radio [Adapt4_06] which implements a dynamic frequency selection algorithm to adapt around legacy systems and CWT’s cognitive radio [Rondeau_04] which utilizes a genetic algorithm
6

to generate adaptations from

6

A genetic algorithm is a search algorithm from optimization theory which generates sequences of candidate solutions by using an algorithm based on the gene theory of evolution. As such the algorithm exhibits both randomness (e.g., “mutations” and random “chromosome” cross-overs to generate “children”)

10

observations. Due to its significant parameterization, the CWT radio is significantly more flexible than the Adapt4 radio and is significantly less hard-coded, but it remains a procedural cognitive radio. Also the CWT radio illustrates that though procedural, the adaptations of a procedural radio may be nondeterministic. Thus when possible we will distinguish between deterministic and nondeterministic procedural cognitive radios. However, a s discussed in the text related to Fig 6 in the April 1900.1 draft, many researchers do not believe that a radio whose adaptations are determined by hard coded algorithms constitutes a cognitive radio. This is primarily because these researchers utilize a definition of cognitive radio which emphasizes a different implementation approach that utilizes a form of artificial intelligence. To provide this intelligence in a radio, [Mitola_00] proposes model-based reasoning using the Radio Knowledge Representation Language (RKRL) and [Baclawski_05] and [Kokar_06] propose ontological reasoning for cognitive radio applications. As defined by the IEEE 1900.1, an ontology is “the representation of terms in a vocabulary and their inter-relationships.” As such, RKRL would satisfy the IEEE 1900.1 definition of an ontology, thus these two different approaches could be said to be of the same “genus” (a cognitive radio that employs ontologies) if not the same “species” of ontology. The primary difference between the two approaches being the former’s usage of a vocabulary restricted to radio information while the latter uses the Web Ontology Language (OWL) to extend the radio’s knowledge base beyond radio-specific information. In the context of cognitive radio, ontologies are intended to permit a reasoning engine to make inferences about the radio’s operating environment and what actions would be in the cognitive radio’s interest. Such an ontological approach has been employed by the DARPA xG program to demonstrate the feasibility of multiple cognitive radios implementing dynamic freque ncy selection (DFS). For the purposes of this t ext, we consider cognitive radios that adapt based on the decisions of a reasoning engine and

and determinism (e.g., picking “surviving populations” based on their “fitness” which for cognitive radios is expressed in terms of the goal of the cognitive radio). More information on genetic algorithms and CWT’s genetic algorithm cognitive radio is available in [Reiser04].

11

incorporate ontologies to be ontological cognitive radios which we formally define in Definition 1.6. [Neel_06] Definition 1.6 : Ontological Cognitive Radio (*) A cognitive radio whose adaptations are determined by some reasoning engine which is guided by its ontological knowledge base (which is informed by observations). Though this distinction is blurred for nondeterministic procedural cognitive radios, e.g., the biologically inspired cognitive radio [Rondeau_04], an ontological cognitive radio could conceptually perform both much better and much worse than a procedural cognitive radio. Whereas for a procedural cognitive radio we typically know what action the radio will take when a known collection of observations are input to the radio, the same can not be said for an ontological cognitive radio as it truly has a mind of its own (the reasoning engine). Instead, for an ontological cognitive radio we only know that the radio will take an action the radio believes (or the engine calculates) furthers the radio’s goal. While this imprecision appears to be a significant hurdle to analyzing the interactions of cognitive radios, we introduce techniques for analyzing these radios beginning in Chapter 4.

1.2 Cognitive Radio Implementation and Standardization
The differences in the definitions for cognitive radio can be largely attributed to differences in the expectations of the functionality that a cognitive radio will exhibit. In his dissertation [ Mitola_00], Joseph Mitola III considers the nine levels of increasing cognitive radio functionality shown in Table 1.1, ranging from a software radio to a complex self-aware radio.

12

Table 1.1: Levels of cognitive radio functionality. Adapted from Table 4-1 [Mitola_00].

Level
0 1 2 3 4 5 6 7 8

Capability
Pre-programmed Goal Driven Context Awareness Radio Aware Capable of Planning Conducts Negotiations Learns Environment Adapts Plans Adapts Protocols A software radio

Comments
Chooses Waveform According to Goal. Requires Environment Awareness. Knowledge of What the User is Trying to Do Knowledge of Radio and Network Components, Environment Models Analyze Situation (Level 2& 3) to Determine Goals (QoS, power), Follows Prescribed Plans Settle on a Plan with Another Radio Autonomously Determines Structure of Environment Generates New Goals Proposes and Negotiates New Protocols

As a reference for how a cognitive radio could achieve these levels of functionality, [Mitola_00] introduces the cognition cycle, shown in Figure 1.1, as a “top- level control loop for cognitive radio.” In the cognition cycle, a radio receives information about its operating environment (Outside world) through direct observation or through signaling. This information is then evaluated (Orient) to determine its importance. Based on this valuation, the radio determines its alternatives (Plan) and chooses an alternative (Decide ) in a way that presumably would improve the valuation. Assuming a waveform change was deemed necessary, the radio then implements the alternative (Act) by adjusting its resources and performing the appropriate signaling. These changes are then reflected in the interference profile presented by the cognitive radio in the Outside world. As part of this process, the radio uses these observations and decisions to improve the operation of the radio (Learn), perhaps by creating new modeling states, generating new alternatives, or creating new valuations.

13

Figure 1.1: Cognition cycle. Reproduced from Figure 4-2 [Mitola_00] As the learning process can be quite cycle intensive and is not necessary for many of the envisioned applications and as artificial intelligence is not yet ripe for deployment, many researchers have assumed lower levels of functionality in their cognitive radio. For instance, in his remarks at the 2005 MPRG Technical Symposium, Bruce Fette, Chief Scientist at General Dynamics Decision Systems, noted that many members of the defense community refer to the cognition cycle as the “OODA” loop – emphasizing only the observation, orientation, decision, and action portions cognition cycles. Even the source of the most expansive interpretation of cognitive radio [Mitola_00] suggests that learning would occur during sleep or “prayer” (insight gained from external entities) epochs and that during wake epochs the cognitive radio would primarily operate as an OODA loop augmented by some light planning capabilities. Whether implemented as an ontological cognitive radio or as a procedural cognitive radio, all cognitive radios are likely to make use of a goal driven OODA loop for its adaptations. This assumption of an explicit or implicit OODA loop is reflected in the modeling introduced in Chapter 2.

14

1.2.1 Radios
The following sections briefly describe some initial cognitive radio implementations and their relationship to the levels of cognitive radio functionality and our classification of cognitive radios. The first two radios discussed – CR1 and DARPA’s xG architecture – are examples of ontological reasoning radios. The next two radios – a biologically inspired cognitive radio and CORTEKs – are examples of nondeterministic procedural radios. The last cognitive radio presented – XG1 – is an example of a deterministic procedural radio.

1.2.1.1 CR1
CR1 or Cognitive Radio 1 is the cognitive radio architecture developed by Mitola as part of his dissertation [Mitola_00]. CR1 utilizes case-based and natural language reasoning guided by an OODA loop and an ontological description of the radio’s capabilities (Radio K nowledge Representation Language) to determine the adaptations of the radio.

Figure 1.2: CR1 Natural Language Architecture from Figure 8-3 in [Mitola_00]

1.2.1.2 xG
Though hesitant to call its work cognitive radio, DARPA’s xG program is pursuing an implementation of cognitive radios that incorporate ontological reasoning into the decision process. A general architecture for their radio is shown in Figure 1.3 where 15

software control is exerted over the radio platform (making the platform an SDR). Note that their radio actually includes two different reasoning engines – one dedicated to policy and one dedicated to waveforms (strategy).

Sensing Loop Message Flow RF Info Acquisition
Develop Options

Policy Reasoner
Process Request
Accredited Policy

RF Resource Request

Radio Platform
RF Transmit Plan

System Strategy Reasoner
Select s Opportunitie

ine Determ ities tun l Oppor iona
ddit or A ints o N a Yes/ Constr

Policy Engine
Device Functionality & External Environment Interface Planning, Problem Solving, DecisionMaking, Learning Domain Knowledge Usage Conformance Verification

Figure 1.3: DARPA XG High- Level Architecture from [IEEE 1900.1]

1.2.1.3 Biologically Inspired Cognitive Radio
The biologically inspired cognitive radio was the dissertation topic of Christian Rieser [Rieser_04]. Leveraging earlier work on channel sounding, this cognitive radio uses channel measurements to build a hidden Markov model (HMM) of its environment. This HMM is then used by a genetic algorithm to internally predict the performance of different combinations of waveform components for the observed channel conditions.

16

Figure 1.4: Biologically Inspired Cognitive Radio Architecture from Figure 3.4 in [Rieser_04] Originally intended for use on a Proxim hardware radio, the architecture has since been updated (see Figure 1.5) for use on a software radio. This updated architecture now includes support for policy, classification of signals via neural nets, and user driven inputs. Further, this cognitive engine is intended to be with portable across hardware platforms [Scaparoth_06] and as such the engine has been applied to a GNU7 radio and to a radio built using Fujitsu test equipment, and will be applied this year to the Innovative Wireless Techno logies (IWT) Unified Radio Architecture (URA).

7

GNU is a recursive acronym which stands for “GNU is Not Unix”

17

Figure 1.5: Updated Biologically Inspired Cognitive Radio Architecture [Le_06]

1.2.1.4 CORTEKS
The CORTEKS radio is another procedural cognitive radio implemented at Virginia Tech using a PC that leverages Virginia Tech’s OSSIE SCA implementation and the following test equipment from Tektronix ? ? ? Arbitrary Waveform Generator AWG430 – used to create a multi- mode transmitter Logic Analyzer – used for signal characterization (identifying bit patterns, protocols, etc.) Real Time Spectrum Analyzer (RSA3408A) – used to perform signal demodulation. Governed by software defined policy, the CORTEKS radio acts as a secondary spectrum user and adapts its frequency and modulation to maximize goodput while avoiding interference with primary users. To help determine the presence of primary spectrum users, the CORTEKS radio employs neural nets for signal classification.

18

GPIB

GPIB

Arbitrary Waveform Generator AWG430
Multi-mode transmitter GPIB

Real Time Spectrum Analyzer (RSA3408A)
Receiver & spectrum sensor

Personal Computer
MPRG’s OSSIE (Open Source SCA Implementation Embedded) platform CoRTekS Software Application (Rudimentary Neural Network based Cognitive Engine)

Arbitrary Waveform Generator AWG710B
Signal upconverter

Policy (4 ch.)
Transmit spectral power mask Modulation schemes

Image Display
Transmitted Image Received Image

Packet History Display
Bit error Rate Spectral Efficiency

Waveform
Center Freq. Symbol Rate Mod. Type Transmit Power

Spectrum Display
Available Spectrum Detected Interference Current CR spectrum usage

Figure 1.6: CORTEKS Components and Interface

1.2.1.5 Adapt4 XG1
Adapt4 has developed and is currently fielding a cognitive radio called XG1 depicted in Figure 1.7. Intended to operate as secondary spectrum devices, their radio uses a proprietary algorithm known as Automatic Spectrum Adaptation Protocol (ASAP). According to [Adapt4_technology] this algorithm incorporates dynamic frequency selection, frequency hopping, and transmission power control with the intent of avoiding (when possible) and minimizing interference to primary spectrum users.

19

Figure 1.7: Adapt4’s XG1 Cognitive Radio. Image from http://www.adapt4.com/

1.2.2

Cognitive Standards

As highlighted in Section 3, many currently envisioned cognitive radio applications represent “low-hanging- fruit” that could be implemented by incorporating knowledge about the environment and the device into a software radio’s control process. Thus it should not be surprising to see that some efforts are already underway to develop cognitive radios with some

1.2.2.1

Policy Radio Deployments

Policy based radios are the logical result of software radio and global mobility. Because of varying historical local needs, different regions of the world implement different sets of regulations. While there has been some movement towards spectrum harmonization, e.g., the push to harmonize the 5 GHz access for unlicensed 802.11, it seems unlikely that all spectral regulations around the world will be harmonized in the near future. Accordingly, as a radio moves around the world, it requires some mechanism for determining which set of regulations it is operating under. In addition to global phones which are in some sense policy-based radios, though not cognitive policy-based radios, WLAN standards 802.11e and 802.11j can be seen as establishing a protocol that necessitates the use of a policy based radio when operating in the 5GHz band. A more generalized policy-based radio suitable for cognitive radio is being developed by DARPA under the xG program. As noted in [Berlemann_05], an XML based policy description language has been developed which is loosely based on concepts from game

20

theory. As noted in [Marshall_05b], these declarative policy languages have had significant success with Dynamic Frequency Selection algorithms.

1.2.2.2

Emerging Cognitive Radio Standards and Deployments

The IEEE 802 community is currently developing two standards the directly relate to cognitive radio – 802.22 and 802.11h. Additionally, 802.11k is developing techniques for incorporating radio resource management information into WLAN operation – in effect incorporating knowledge about the environment and the radios.

1.2.2.2.1.1

802.22

There are three applications typically discussed for coexistence with initial trial deployments of cognitive radios: television, microwave point-to-point links, and land mobile radio. Each of these applications has been shown to dramatically underutilize spectrum on average. However, only television signals have the advantage of incumbent signals that are easy to detect (as opposed to a microwave point-to-point links) and not involved in life-critical applications (as would be the case for many land mobile radio systems). Throughout its history, the UHF bands were under-allocated as regulators underestimated the cost-effectiveness of establishing new TV towers in these bands. It was not until the advent of cable TV that smaller TV stations were capable of cost-effective operation. Now with the introduction of HDTV technology, regulators in the US plan to force a nation-wide switch to this more efficient modulation by 2009 [Rast_05] accompanied by a completion of a de-allocation from analog TV of 108 MHz of high quality spectrum. With these bands in mind, the 802.22 working group is pursuing the development of a waveform intended to provide high bandwidth access in rural areas using cognitive radio techniques. In a report presented at DySPAN [Cordeiro_05], it is stated that the 802.22 standard intends to achieve spectral efficiencies of up to 3 bits/sec/Hz corresponding to peak download rates at coverage edge at 1.5 Mbps. Simultaneously, the 802.22 system hopes to achieve up to 100 km in coverage.

21

While the PHY and MAC are still under development, the MAC will provide the cognitive capabilities as it manages access to the physical medium, responsible for quickly vacating a channel as needed. The standard under development has specified the following thresholds for vacating a channel for the following signals: ? ? ? Digital TV: -116 dBm over a 6 MHz channel Analog TV: -94 dBm at the peak of the NTSC (National Television System Committee) picture carrier Wireless microphone: -107 dBm in a 200 kHz bandwidth.

Thus these radios will be required to both detect and classify signals in its environment. To help minimize the interference induced to these signals, the 802.22 protocol is currently considering using spectrum usage tables that will be updated both automatically and by the system operator. To limit the impact when the systems fail to detect the incumbent systems, the standard also places traditional maximum transmission power limits and out-of-band emission limits. While a promising approach, it is difficult to estimate how wide-scale a deployment 802.22 will enjoy as WiMAX was first to market with deployments in Korea (WiBro) and planned deployment s in the US [Segan_06] and will be able to provide the same target service: high data rates to rural users.

1.2.2.2.1.2

802.11h

Unlike 802.22, 802.11h is not formulated as a cognitive radio standard. However, the World Wireless Research Forum [WWRF_04] has noted that a key portion of the 802.11h protocol – dynamic frequency selection – has been termed a “cognitive function”. tasks. ? Observation – 5.4.4.1 in [802.11h] requires WLANs to estimate channel characteristics such as path loss and link margin and 5.4.4.2 further requires the radios estimate channel characteristics such as path loss and link margin. To see why an 802.11h WLAN might be considered a cognitive radio, consider that the 802.11h protocol requires that a WLAN be capable of the following

22

?

Orientation – Based on these observations, the WLAN has to determine if it is operating in the presence of a radar installation, in a bad channel, in band with satellites, or in the presence of other WLANs.

?

Decision – Based on the situation that the WLAN is encountering, the WLAN has to decide to change its frequency of operation ( Dynamic Frequency Selection), adjust the transmit power (Transmit Power Control), or both.

?

Action – The WLAN has to then implement this decision.

Reviewing most of the definitions from before, only learning or “recalling and correlating past actions, environments and performance” is not required as part of the standard. However, if we move beyond the requirements of the standard to expected implementations, it seems reasonable that many vendors will include and leverage some memory of past observations (useful for detecting intermittent transmitters) which implies that both cognitive radio definitions will be satisfied.

1.2.3

Institutional Initiatives

Beyond these initial deployments, several entities have started publicly acknowledged initiatives into cognitive radio including DARPA, the SDR Forum, IEEE, and the FCC.

1.2.3.1 DARPA
DARPA sees cognitive radio as a key enabling technology to their vision of advanced networking by allowing less individually capable radios to perform complex operations needed make better use of spectrum and support high data rate applications. Currently, DARPA is exploring many different aspects of cognitive radio as part of the xG program and other ongoing programs. Unfortunately, many of the results of the DARPA programs are not currently in the public domain. However, Preston Marshall, program manager for DARPA’s cognitive radio initiatives has promised that contracting organizations will be required to disclose most of their results online in the near future. In the interim, Marshall highlighted many of DARPA’s plans and results in a presentation at DySPAN [Marshall_05a] and during a panel session at the SDR Forum [Marshall_05b]. In the area signal classification and detection, DARPA has developed a sensor capable of processing 5 GHz/second frequency capable of sub-noise- floor signal detection (20 dB

23

below) by exploiting cyclostationarity properties. DARPA has contracted with Rockwell to miniaturize this sensor. Believing that procedural approach would result in too much code and too many detailed policies, DARPA has developed a declarative policy language that is independent of the implementation platform. Already successfully demonstrating small networks of Dynamic Frequency Selection networks, DARPA hopes to extend their policy work to construct a “provable framework” that supports policy enforcement and optimization (current focus is just on making the technology work, the Wireless Networking After Next program is intended to include optimization as a goal). Another demonstration of radios from Lockheed-Martin, Shared Spectrum, and Raytheon with the target of 90% connectivity and 90% chance of finding available spectrum found that 15 times more radios could be fielded using the xG approach. By August 2007, DARPA plans to have field trialed systems of interacting and collaborating 25 xG nodes. DARPA also believes that advanced network topologies will be a key application of cognitive radios and is starting the CBMANET program to explore advanced networking topologies based on the xG radio. To help support these new dynamic topologies and the proposed optimization routines Marshall believes there may need to be new layers inserted into the protocol stack for topology an optimizatio n because of the intelligence required in those operations. The most notable anticipated activity from DARPA is the launching of the Wireless Adaptable Node Network (WANN) project this September.WANN hopes to demonstrate reduced device cost (targeting ~$500/node) via intelligent adaptation and greater node density. Additionally, the WANN program is hoping to achieve significant gains in throughput and network scalability through the incorporation of intelligence in the radios.

1.2.3.2 SDR Forum
The SDR Forum chartered two groups in 2004 to explore cognitive radio issues: the Cognitive Radio Working Group and the Cognitive Radio Special Interest Group. The working group is tasked with standardizing a definition of cognitive radio and identifying 24

the enabling technologies for cognitive radio. The special interest group is tasked with identifying attractive commercial applications of cognitive radio for which the working group should identify the enabling technologies. At the 2005 SDR Forum Technical Conference, significant emphasis was given to cognitive radio with two paper sessions, one panel session, a tutorial, and a keynote talk dedicated to the subject of cognitive radio. Then in April 2006, the SDR Forum held a Cognitive Radio Workshop in San Francisco.

1.2.3.3 IEEE
The IEEE has expressed significant interest in cognitive radio. As a body, IEEE submitted the proposed definition to the FCC noted in Section 2. To allow for more focused development, the IEEE has started the IEEE 1900 group to study the issue of cognitive radio. Currently, the 1900 group has three subgroups with the following focuses: ? ? ? ? 1900.1 - Standardize definitions and terminology related to cognitive radio 1900.2 – Standardizing a process for testing and verifying the operation of cognitive radios. 1900.3 – Standardizing approaches for qualifying software modules. 1900.a – Regulatory certification of cognitive radios.

The IEEE Communications Society held its first Dynamic Spectrum Access Networks (DySPAN) in November 2005 with a primary focus on how cognitive radio, including the following: ? ? ? ? technologies needed to implement cognitive radio ranging from sensing, analysis of interactions, and advanced networking technologies appropriate regulatory approaches for cognitive radio potential market opportunities for cognitive radio trial implementations of cognitive radio systems.

25

The IEEE is playing an expanding role in the development of cognitive radio forming the 1900.4 workgroup (joining the 1900.1, 1900.2, and 1900.3 groups described in the December 2005 report) to support standardization of radio regulatory compliance, sponsoring CrownCom2006 – a cognitive radio focused conference – and two special issue journals on cognitive radio, and the 802.22 group which merged its final two proposals in March implying that the standard could be agreed upon within the next year.

1.2.3.4 FCC
On May 19, 2003, the FCC convened a workshop to examine the impact that cognitive radio could have on spectrum utilization and to study the practical regulatory issues that cognitive radio would raise. After a series of public interactions, the FCC adopted the transmitter-centric definition of cognitive radio listed in Section 2 and appears interested in adjusting its regulations in a way that will accommodate the deployment of cognitive radio in unlicensed bands and possibly in a portion of the new bands being opened up by the upcoming UHF reallocation with possible later extensions to the public safety and ISM bands. Since then, the Federal Communications Commission (FCC) has also taken steps to increase the opportunities for cognitive radio deployment by expanding the unlicensed 5 GHz and requiring that devices operating in those bands support both Dynamic Frequency Selection (DFS) and Transmit Power Control (TPC) – characteristics of 802.11h which was characterized in the December 2005 report as indicative of minimal cognitive radios. In light of the expanded introduction of cognitive radios, the FCC issued proposed rules for compliance testing DFS radios in April [FCC_06a] with comments due on May 15. The results of this process were compiled into a document released on June 30, 2006 that provides a standard for testing DFS and TPC compliance with regard to radar avoidance and minimizing interference with satellites [FCC_06b]. It is expected that these actions will enhance the opportunities for cognitive radio deployments.

26

1.2.3.5 Other Institutions
Several other institutions are also currently pursuing cognitive radio research including E2 R, Virginia Tech, Winlab, and BWRC. E2 R is a European initiative into supporting End-to-End Reconfigurability with numerous participating European universities and companies. E2 R is focused primarily focused on incorporating dynamically radio resource management schemes into existing cellular structures to achieve advanced end- user services with efficient utilization of spectrum, equipment and radio resources on multi-standard platforms. Virginia Tech currently has several significant cognitive radio initiatives. Two different cognitive radio testbeds that leverage test equipment to effect powerful yet easy to implement software radios are under development with a focus on both public safety and commercial interests. These two projects are exploring techniques for enhancing detection and classification capabilities, learning algorithms, knowledge representation and the effect of interaction of cognitive radios. Work is being performed exploring techniques to exploit collaborative radio to improve network performance. Other projects are exploring techniques for analyzing the interactions of cognitive radios, developing environmental awareness maps, and MAC protocols that can trans. Virginia Tech also maintains a publicly accessible cognitive radio wiki as part of its cognitive radio special interest group at http://support.mprg.org/dokuwiki/doku.php?id=cognitive_radio. Additionally, Virginia Tech is organizing the MANIAC (M obile Ad Hoc Networking Interoperability And Cooperation) challenge wherein researchers from numerous universities will independently design cognitive radios which will then be brought together to “compete” to see which cognitive radio algorithms yield desirable network behavior. A similar competitive cooperative contest is in the planning for DySPAN 2007 though details are unclear at this point. Winlab at Rutgers University is developing a cognitive radio testbed for disaster response using commercially available components. BWRC is currently developing a cognitive

27

radio for sensing and opportunistically using the spectrum. Additionally, BRWC is researching techniques for improving spectrum sensing algorithms.

1.3 Cognitive Radio Applications
Applications are often included in the definition of cognitive radio because of the compelling and unique applications afforded by cognitive radio. Additionally, there are many existing SDR techniques that cognitive radio is expected to enhance. This section reviews the following frequently advocated applications of cognitive radio some of which will be used as inspiration for example analyses later in this document: ? ? ? ? ? ? Improving spectrum utilization & efficiency Improving link reliability Less expensive radios Advanced network topologies Enhancing SDR techniques Automated radio resource management.
Spectrum Trading Cheaper Radios? Automated Interoperability

Opportunistic Spectrum Utilization

Improved Link Reliability

Advanced Networking Intelligent Beamforming

Collaborative Techniques
First Hop Second Hop

Source Cluster

Relay cluster

Destination Cluster Destination Cluster

Figure 1.8: Cognitive Radio Applications

28

1.3.1 Improving spectrum utilization and efficiency
Wireless technologies and wireless devices have proliferated over past decade dramatically increasing the demand for electromagnetic spectrum. Because of the current approach to spectrum access, spectrum supply h as not kept up with spectrum demand leading to the appearance of scarcity in the electromagnetic spectrum. However, research performed by various entities such as the FCC indicates that this assumption is far from reality; there is available spectrum since most of the spectrum allocated sits underutilized. In a recently completed NSF funded study of allocated spectrum utilization, researchers at Kansas University found an average U.S. spectrum occupancy of 5.2% with a maximum occupancy of 13.2% in New York City. Figure 1.9 shows the specific measurements by band as averaged over the following six locations: 1. Riverbend Park, Great Falls, VA, 2. Tysons Corner, VA, 3. NSF Roof, Arlington, VA, 4. New York City, NY, 5. NRAO, Greenbank, WV, 6. SSC Roof, Vienna, VA [McHenry_05]. So while the dramatically increasing demand for spectrum has fostered a perception that spectrum is scarce, the reality is that spectrum is abundant but poorly utilized.

29

Figure 1.9: Spectrum availability by band. Adapted from Figure 1 in [McHenry_05]. This underutilization is the result of a number of different factors including overly conservative allocation of guard bands; a migration from spectrally inefficient analog waveforms to more efficient digital waveforms, and the natural gaps in utilization that occur throughout the day due to variations in demand. As an example of variations in demand, Figure 1.10 shows a Matlab d epiction of spectrum measurements made in Germany at Karlsrhue in a more heavily used band. As the figure illustrates there is significant variation in spectrum underutilization in time and frequency, and though not depicted, there is also significant variation in terms of location.

30

Figure 1.10: Matlab capture of channel measurements from Germany [Jondral_04] To improve spectrum utilization, opportunistic spectrum utilization has been proposed wherein devices occupy spectrum that has been left vacant. An illustrative example of opportunistic spectrum utilization is shown in Figure 1.11. In the left half of the figure, a pair of transmitted carrier signals is present in the lower frequency bands while a random access system and a TDMA system are operating in the upper bands. After observing the spectrum holes - points in time and frequency where spectrum is underutilized – opportunistic devices could fill in these holes to support concurrent services as illustrated in the diagram on the right.

31

Figure 1.11: Conceptual example of opportunistic spectrum utilization According to the xG program manager [Marshall_05a], cognitive radios that employ opportunistic spectrum utilization have been shown to provide a 10-fold gain in capacity by implementing dynamic frequency selection algorithms. Of course, opportunistic use of spectrum presents significant challenges to the technical and regulatory communities. From a technical perspective, the devices must be able to autonomously resolve conflicts over spectrum access and when operating opportunistically should be able to avoid interfering with incumbent signals. While avoiding introducing interference to a signal that is continuously present, it is more difficult with regularly structured, but intermittent signals such as a TDMA signal, and impossible to guarantee with a random access signal. To some extent this implies that the control processes of cognitive radios will n eed to be able to operate over multiple time scales as is proposed in [Moessner_05]. Since there is a technical problem, there is also a regulatory problem. Current spectrum licensees are generally only amenable to opportunistic spectrum access when they can be assured that their signals will not be degraded. Figuring out how to achieve the 10- fold gain in capacity while limiting the impact of existing services is currently a topic of much debate in the regulatory community.

32

1.3.2 Improving Link Reliability
After improving spectrum utilization, the second most commonly discussed application of cognitive radio is improving link reliability. Many adaptive radios currently improve link reliability by adapting transmission power levels, modulations or error correctio n. However, a cognitive radio that is capable of remembering and learning from its past experiences can go beyond these simple adaptations as can be shown via the following simple example. Figure 1.12 illustrates a path that a mobile subscriber might follow on his daily commute through a particular area of a city where signal quality usually drops to an unacceptable level (shown in red) due to a coverage gap. Perhaps the first time or perhaps after several occurrences, the cognitive radio would become aware of this problem. Then via some geo- locational capability or by learning the expected time of day when this occurs, the radio could anticipate the coverage gap and signal to the base station the need to alter the signal characteristics as the user approaches the coverage gap.

Signal Quality

Good

Transitional

Poor

Figure 1.12 Path and associated signal quality for a cognitive radio.

33

The same concept of detecting coverage gaps could also be employed at the base station where the base station would learn to correlate particular areas of its coverage area with a gap and then could adjust its operation (perhaps via beam forming) to eliminate the gap. Without including a cognitive base station, cognitive mobiles could share such information among themselves so that the mobiles may learn to improve their link performance without first experiencing the coverage gap. This, however, highlights another key challenge to realizing cognitive radios – how to represent the knowledge a cognitive radio needs to operate in a machine- usable and machine-to- machine translatable way.

1.3.3 Less Expensive Radios
While adding complexity to a radio’s control processes would appear at first glance to necessarily increase cost, the inclusion of a cognitive control process may significantly decrease device cost when cognition is enabled. To resolve this apparent paradox of adding features but reducing cost, it is important to note that many of the proposed applications of cognitive radios represent “low- hanging fruit” that can be implemented via low complexity control processes. Further, these cognitive processes would be implemented in a software defined control process for which additional computations are relatively insignificant, especially when compared to the cost of improving the performance of analog components. Adding a couple hundred software cycles per second is virtually costless; improving the performance of a RF front end by 3 dB can be a very expensive undertaking. As noted in the preceding, the inclusion of opportunistic spectrum utilization permits significant gains in terms of capacity. Instead of only improving capacity, some of the spectrum gain could be “given” to accommodating lower performance analog components in the transmitter which generally result in signal energy outside of the intended band. These lower performance transmitter analog components can be included in the cognitive radios or among “dumb” radios. For example consider the spectrum utilization diagram shown below in Figure 1.13 where the signal from one device exhibits significant spurious components and the 34

remaining cognitive devices are capable of observing this signal and adapting around these spurs. In this particular example, there would be no degradation in total informational throughout bandwidth when compared with the example considered in Figure 1.11 as all opportunistic devices are still capable of finding spectrum holes to transmit in. However, any degradation in terms of out-of-band energy necessarily decreases the available bandwidth for opportunistic spectrum utilization so some tradeoff has to be made.

Figure 1.13: Opportunistic spectrum utilization in the presence of device with significant signal degradation. If the lower performance analog components are present only at the receiver, then there is no direct effect on the observable spectrum. However, cognitive radio processes similar to those assumed necessary for ensuring link reliability can be applied to overcome the limitations of poorly performing analog front ends. For example, adaptive beam forming

35

or nulling can provide additional SINR or opportunistic spectrum utilization routines could seek “deeper” spectrum holes to overcome low-Q anti-aliasing filters. Whether included in transmitter or the receiver, cognitive radio facilitates the use of lower cost analog components. Of course, these gains can be supplemented by software radio techniques such as dithering data converter inputs and predistortion for power amplifiers.

1.3.4 Advanced network topologies
Under a MANET operational scenario, the access points or base stations do not have to maintain direct connections to the more distant regions of their clusters or cells. Instead, each base station only needs to be able to reach a handful of the closest subscribers while the devices farther from the base station gain access by communicating through a sequence of intermediate devices to reach the base station. As illustrated in Figure 1.14, in a MANET the average propagation distance for each link is much shorter than would be the case for a star topology with the same number of base stations. The shorter propagation lengths means that greater effective spectral reuse factors can be achieved which some have said would lead to a gain of up to 30 dB in system capacity [Fette_05].

Figure 1.14: Star and Ad-hoc Topologies

36

While the deployment and advantages of MANETs do not inherently require the use of cognitive radio, cognitive radio can be seen as an enabling technology. For a MANET to successfully operate two criteria should be satisfied. First, a high node density should be present to permit the use of lower power links. In general, the denser the network of devices is, the greater the theoretical capacity of the MANET. Second, the devices must be capable of supporting the dynamic routing and link maintenance routines required ensure network connectivity. As described previously in this document, cognitive radios can be used to significantly increase the usable bandwidth and decrease device cost which in turn implies that many more devices can be expected to be fielded in the future, thus implying greater device density. For the second criterion, the environmental and device awareness implicit to a cognitive radio facilitate implementation of the algorithms needed to support the MANET routing and link maintenance algorithms.

1.3.5 Collaborative Techniques
A collaborative radio is a radio that leverages the services of other radios to further its goals or the goals of the networks. As introduced in the previous section, collaborative radio can be viewed as an application of cognitive radio. However, a collaborative radio could be implemented without a full implementation of cognitive radio. For instance, many collaborative applications require only trivial learning processes. Nonetheless cognitive radio can be viewed as an enabler of collaborative radio in that cognitive processes simplifies the identification of potential collaborators and intelligent observation processes facilitates the inclusion of distributed sensing – a characteristic of many collaborative radio applications. One of the more freque ntly discussed ways in which radios can collaborate is by implementing relay channels. In a relay channel, a radio serves as an intermediate node in the path between the client device and the access node. In general, this relaying process can be implemented at the relay node by amplifying and forwarding the received signal or by decoding and forwarding the signal. In the former case, radio complexity is relatively low as the signal does not have to be received; in the latter, radio complexity is 37

generally much higher as the relay has to completely receive the transmitted signal. However, the added complexity incurred by a decode-and-forward approach is generally accompanied by improved performance (low latency waveforms being the most noticeable exception) so there exists a tradeoff between the two approaches. The concept of using relay radios is currently the focus of the 802.16j workgroup which considers three types of relays: fixed relays, nomadic relays, and mobile relays. As illustrated in Figure 1.15, the relay radios in 802.16j are intended to extend the coverage of 802.16 networks where the relay nodes are intended as an extension of the 802.16 infrastructure.
Fixed Relays

Nomadic Relay

Mobile Relay

Figure 1.15: Conceptual operation of 802.16j Modified from Fig 1 in IEEE 802.16mmr05/032 While the relays in 802.16j are dedicated infrastructure installations, the existence of mobile relays (intended to support mass transportation) implies that the relaying concept should be extendable to subscriber units. While relaying with subscriber units implies that performance may be more difficult to guarantee, it should be possible to improve overall network performance and coverage with less deployment costs by judicious choice of relay nodes. However, wisely choosing which subscriber units should act as relay nodes implies some knowledge of the state of the network and the traffic and 38

mobility characteristics of other subscriber units in the area. For a traditional radio, this knowledge would be difficult to come by, but if the subscribers were cognitive radios then presumably the radios would be gathering and processing the relevant information as part of the normal processing.

1.3.5.1 Distributed Antenna Arrays
Of course there will be situations where a group of subscribers is out of range of an access node and no subscriber device will be positioned well enough to serve as a relay node. However, if the subscriber devices collaborate, their effective range can be dramatically increased, perhaps far enough to reach an access point. In this form of collaboration, several radios collaborate to realize an antenna array thereby leveraging the processing gains of an antenna array without each subscriber unit needing to have its own antenna array. Because of the likely spacing of devices, it seems unlikely that beamforming will be a readily used application for a collaborative array of radios, but diversity applications should be usable. For instance, two different diversitybased collaborative antenna applications are illustrated in Figure 1.16. In a simple diversity scheme a number of radios can coordinate to transmit or receiver the same signal thereby realizing a transmit or receive diversity algorithm. With some additional coordination, those same collaborating radios could implement a MIMO, MISO, or SIMO algorithm depending on the operational context.

39

Cooperative MIMO
First Hop Second Hop

Source Cluster

Relay cluster

Destination Destination ClusterCluster

Transmit Diversity

destination source

Figure 1.16: Distributed Antenna Array Possibilities Particularly for the distributed MIMO/MISO/SIMO schemes and to a lesser extent the collaborative transmit and receive algorithms, good timing and localization information will be of significant aid to the performance of these algorithms. Again, the normal processes of cognitive radio may be able to provide the information necessary or perhaps this information could be collaboratively collected into some environmental map.

1.3.5.2 Distributed Mapping
Assuming radios are aware of their location and capable of making observations, it should be possible for radios to collaborate to build maps of their environment. One such map could be the radio environment map discussed in [Zhao_06] which can help inform cognitive radio adaptations. Maps targeted to the service providers and subscribers instead of the radios themselves could also be built via radio collaboration. For instance, by collecting signal strength measurements and feeding this information back to the infrastructure, a network’s coverage map can be built. With this continually

40

updated coverage map, service providers can quickly identify coverage holes and take steps to rectify the problems. Assuming the network infrastructure is implemented using cognitive radio technology, these coverage holes could be automatically filled, significantly decreasing the chances of a subscriber experiencing a dropped call and improving subscriber perception of service. As another example, suppose the mobiles are continuously returning their location information to the network’s base stations. By integrating this information, the network can get an accurate picture of its subscriber density by location. While a subscriber density map will be useful for network planning, it also implies a unique subscriber service – real time traffic maps and real time traffic updates. Specifically, when higher subscriber densities are located on roads, this should be indicative of higher density automobile traffic – information which other drivers may be willing to pay so as to avoid traffic jams. Thus by simply collecting location information from each of its subscribers, a service provider can provide a novel service of real time traffic updates.

1.3.5.3 Enhanced Security
Certain radios will tend to be used in close proximity with other radios. For instance, the various Bluetooth devices in an automobile will typically be operated with the mobile (or mobiles) of its owners onboard. By learning and recognizing the MAC addresses of the mobiles of an automobile’s owners, the automobile should be able to flag situations that are inconsistent with normal operation, fo r instance if the car was in operation and a different mobile than the owners’ mobiles was on board. In and of itself, this situation will not be sufficient to know that the automobile has been stolen, but it should be enough to make the situation a scenario worth further examination. Conceptually, this could be viewed as similar to the process wherein credit card companies flag purchases that do not fall into normal patterns. Similarly, this sort of information could be incorporated into an enhanced authentication system where contextual information gleaned from other authorized radios can provide degrees of authentication assuredness.

41

1.3.5.4 Collaborative Sensing
For many emerging wireless standards, such as 802.22, it will be important for radios to be able to detect and classify signals in its environment to ensure proper network behavior. Introductory statistics courses teach that an increasing number of independent (and unbiased) observations reduce the variance of estimated parameters. Thus the decisions as to if a signal is present and what kind of signal is present (for example is a TV broadcast present or more generally is the incumbent user transmitting) could be improved by incorporating more observations from other devices. Beyond 802.22 applications, c ollaborative sensing should be able to help mitigate the hidden node problem endemic to most standards. In fact, collaborative radio itself holds the potential for numerous applications, including relay channels, distributed antenna arrays, improved localization algorithms, and collaborative mapping. However, many of these algorithms lack agreed upon models and algorithms. Without some unified approach, collaborative radios will likely go the way of networking and lack a sound theoretical basis. Lacking this theoretical basis, it will be important to construct prototypes and demonstration system before implementation or standardization can occur.

1.3.6 SDR techniques enhanced by cognitive radio
Similar to how cognitive radio will hasten the wide scale deployment of MANETs without being a requisite technology, several other techniques that require a software radio can be significantly enhanced by the use of cognitive radio. These SDR techniques include antenna array algorithms, spectrum trading, and interoperability. Smart antenna technology is a traditionally discussed advantage of software radio. However, network performance can be greatly improved by adding environmental awareness to smart antenna algorithms. For example consider the beamforming example shown in Figure 1.17 where two links are present – one between the gray nodes and one between the white nodes. When the bottom left node chooses to implement transmit beamforming, a significant gain in performance for the gray nodes’ link can be expected.

42

However, from a network perspective, this choice is not desirable as the benefit accrued by the beamforming link will not be as great as the added interference that the intermediate white node will experience. However, if the gray nodes are cognizant that one of the white nodes is operating within the potential beam, then the gray nodes could choose a different adaptation that would not impact the white nodes, perhaps via a combination of spatial and frequency multiplexing.

Figure 1.17: An example of ad- hoc beam forming that would have negative effects on network performance. Spectrum trading has long been discussed as a potential benefit of the frequency agility of software radio. In spectrum trading, different spectrum owners purchase and sell spectrum to varying service providers in response to changes in market demand. In theory – the practice of spectrum trading is in its infancy having recently received limited approval in the UK and Guatemala [Hatfield_05] and FCC approval in the US for trading among public safety users – spectrum trading facilitates the allocation of spectrum in the most efficient manner in terms of demand. Fundamentally, the only technology required to support spectrum trading is software radio. With software radio, subscriber nodes can be instructed to change their band of operation following any spectrum trade. However, this implies spectrum trading at the service provider level which implies a process that requires weeks to months to complete. However, if each subscriber unit is capable of determining its own bandwidth 43

requirements, is aware of its environment and the availability of spectrum, and is capable of negotiating with service providers for bandwidth, then spectrum trading transactions could be conducted on the order of milliseconds for significantly smaller pieces of spectrum. Similarly cognitive base stations operated by service providers could quickly and dynamically shift spectral resources between providers to adjust to variations in spectral demand, significantly reducing the probability of a dropped or blocked call. Interoperability is another frequently touted benefit of the reconfigurability of software radios. Assuming perfect reconfigurability, a software radio can be readily reprogrammed to communicate using any waveform necessary to communicate with another radio, whether the second radio is a software radio or a legacy radio. One commonly discussed technique for supporting interoperability among different legacy systems is to utilize one radio as a gateway device and automatically retransmit messages using the waveforms that each legacy device understands. Elided in this discussion are the control processes that translate device reconfigurability into interoperability. With a software radio acting as the gateway, it is necessary for a network administrator to set up the connections between disparate legacy devices as the gateway node may have no idea of what devices are present or what connections need the services of the gateway. If a cognitive radio serves as the gateway, the cognitive radio can assume responsibility for these tasks in an automated fashion.

1.3.7 Automated Radio Resource Management
After a wireless network is deployed, wireless engineers typically spend a few weeks tuning the radio parameters to get the most out of a network. Channels allocations between sectors, call drop thresholds, power levels, timers, antenna patterns and many more parameters are all adjusted to improve network performance based on postdeployment measurements. With the increasing number of wireless networks and the movement from centralized service providers to home and office wireless LANs, the need to optimize wireless networks will become an increasingly important but will be impractical to be performed at home or in rapidly deployed networks. For instance, Virginia Tech spent months carefully planning and checking up on the deployment of its 44

wireless LAN in order to maximize coverage with an acceptable capacity level – an unacceptable amount of time in a disaster response scenario. Because of its capacity to observe and learn how to improve its performance, cognitive radio networks could take over the task of post-deployment tuning and automatically update the radio parameters to best suit the needs of the particular deployment. Such an application would have a significant impact on rapidly deployed networks where emphasis, in home WLANs (which are rarely tuned), and in fixed commercial infrastructure where cognitive radio should be able to reduce the demand for postdeployment engineering.

1.4 Key Issues to Wide-Scale Deployment of Cognitive Radios
Of course there are always significant challenges accommodating revolutionary changes. First, unleashing the revolutionary changes of cognitive radio demands the development of new regulatory ideas – traditionally a glacial process. Second, programming intelligence has always been a difficult undertaking, and for the first time intelligence needs to be included in the radio. Third, many cognitive radio applications assume advanced capabilities to detect and classify signals and identify unused spectrum in a timely manner – capabilities that still need improvement. Fourth, to the extent that cognitive radio is an evolved software radio, cognitive radio will also benefit from enhanced control over the hardware, increased processing power, smaller form factors, and improved software verification techniques. Finally, autonomous adaptations of cognitive radios lead to complex interactive decision processes that make performance guarantees and network planning difficult. Before deploying cognitive radios in a wide-scale manner, there are a number of issues that should be addressed. These include being able to predict how the interactions of cognitive radios influence network performance, addressing regulatory issues, improving environmental observational capabilities, and a number of SDR issues that are exacerbated by cognitive radio.

45

1.4.1 Regulatory Issues
Partially caused by the present uncertainty in predicting the effect of interacting cognitive radios and partially caused by ideological differences, how to regulate cognitive radios has emerged as a significant point of disagreement, dividing the policy community into two camps: property-rights and commons. While both camps agree that the traditional command and control model wherein spectrum is licensed for a particular application is less desirable and on the way out, there is little agreement between the two models how cognitive radios will be governed in the future. Under the commons model (also called the unlicensed model), a pure opportunistic usage approach would be adopted wherein a cognitive radio could make use of any available spectrum that it observed. Under the property rights model (also called the exclusive-use model), entities would “own” their spectrum instead of licensing it, thus entitling them to implement different waveforms as well as subdivide their spectrum for resale to secondary spectrum users for a variety of applications inc luding opportunistic spectrum use. Property-rights proponents claim that the commons model will lead to a tragedy of the commons. A tragedy of the commons is a situation that can occur with a publicly- held finite resource where each person assigns receives a positive benefit from using more of the resource leading to overuse of the resource to the point of catastrophic results. Commons proponents are quick to point out that spectrum is an infinitely renewable resource so we will never run out and thus cannot experience a tragedy of the commons. However, property rights proponents respond that per unit time, spectrum is indeed finite and many apparently boundless resources have been overused when regulated with a commons approach. Commons advocates claim that a property-rights model may limit the development of technology and could lead to a tragedy of the anti-commons wherein a small number of entities secure the rights to spectrum and exclude others from using the spectrum thus increasing the value of their spectrum and leading to underutilization of the spectrum.

46

However, property-rights advocates note that spectrum presumably would not be used any worse than it is now and anti-trust laws exist for handling such an anti-commons situation. While the property-rights approach appears to have the better theoretical argument and while many incumbent service providers have explicitly stated their opposition to the commons model [Lynch_05], it is difficult to argue with the success of 802.11 which was deployed under a commons regulatory scheme in the ISM bands. While there are significant differences between the two camps, as noted in the remarks of Andy Mudar [Mudar_05], both communities have expressed interest in a simple regulation that could ensure proper and predictable operation of cognitive radios. However, no such regulation has yet to be identified.

1.4.2 Knowledge Representation
The capability to intelligently reason about the environment implies the existence of some language that captures the knowledge that the radio has about the environment. The need for such a language formed a significant portion of the discussion in the dissertation that proposed cognitive radio. Specifically, [ Mitola_00] proposed the use of a Radio Knowledge Representation Language (RKRL) to describe the knowledge a radio may have about its own capabilities and its environment. Similarly the xG program has developed an XML-based language for representing in a declarative manner the policies that govern a cognitive radio’s actions [Be rlemann_05]. In remarks at a cognitive radio panel discussion at the 2005 SDR Forum, Preston Marshall noted that this declarative language approach had shown significant success with Dynamic Frequency Selection (DFS) algorithms. However, at that same panel concern was expressed over how to validate an debug a radio whose operation is determined by a declarative language, such as Prolog, as opposed to a traditional procedural language, such as C. OWL – Web-based Ontology Language – has also been proposed as a language for representing radio knowledge in a declarative manner, but

47

primarily for the purpose of supporting knowledge queries between radios [Baclawski_05]. Taking an entirely different though potentially complementary route, [Mohammed_05] has shown that significant amounts of information related to cellular channels can be collected and represented using a hidden Markov models (HMM). Further, these HMMs can be used to gain context and environmental awareness by correlating HMMs generated from run-time observations with At this point, it is uncertain how these languages will interoperate and if the combination will provide a sufficient basis for implementing the reasoning capabilities needed for cognitive radio. Once these knowledge representation languages have crystalized, additional work is expected to be performed in the area of artificial intelligence (AI), e.g., inference machines, which will further enhance the capabilities and advantages of cognitive radio. Fortunately, however, cognitive radio does not require fully operation AI for any of the applications discussed in Section 1.3.

1.4.3 Improved Sensing Capabilities
To properly respond to changes in its environment, cognitive radios will need to be able to detect and classify the signals in its environment. If deployed in an opportunistic manner, it will be important for the cognitive radios to differentiate between primary spectrum licensees whose signals must be protected from interference and from other opportunistic signals for which less complicated measures are required. Additionally, there may be a variety of different primary signals in the same band, each of which can handle a different level of interference. For example in the UHF bands in the US which have been suggested for initial cognitive radio deployments, there are currently three primary signals that must be protected - analog TV, digital TV, and wireless microphones – with the possibility of many more in the future. Somewhat repeating the process when spread spectrum moved from the military sphere to the commercial market, many of the needed technologies already exist, but are not publicly known. However, public researchers are now actively exploring the issue of 48

signal detection and classification with initial promising results from combinations of algorithms that exploit cyclostationarity properties to extract signal information and neural networks to make sense of the information [Fehske_05]. Even with the best sensing capabilities, there exists the possibility of failing to find the operating primary devices due to hidden node problems. To help combat this, a variety of solutions have been proposed [Brown_05] including maintaining spectrum usage tables, network assisted detection, and placing beacons on the primary license devices. Of these approaches, network assistance (wherein cognitive radios share their observations in the network) and spectrum usage tables (updateable by primary and secondary service providers) appear to be the most promising approaches. The IEEE 802.22 standardization committee is currently considering requiring the maintenance of spectrum usage tables as a part of its standard [Cordeiro_05].

1.4.4 Software Radio Issues
As cognitive radio is just an evolution of the software radio control processes, all software radio issues will also be issues for cognitive radio. This includes improving frequency flexibility and agility, enhancing data converter technologies and careful software architecting. Frequency flexibility and agility is critical to successful implementation of opportunistic spectrum utilization. While MEMS controlled RF devices should soon be able to provide both high performance and rapid RF reconfiguration, an intermediate solution may be available now using FETs to implement the same switches that would be used with MEMS. [Oh_04] has proposed the use of FETs to implement reconfigurable antennas and [Domalapally_04] has proposed the use of FETs to implement reconfigurable oscillators and anti-aliasing filters. Using FET-controlled RF, cheap reconfigurable RF can be achieved now with a clear upgrade path to MEMS. To sense available spectrum and other signals in the environment, wider bandwidth ADCs will be needed. Advances in data converter technologies appear to have accelerated recently [Le_05] so this may not be a significant limitation. Likewise 49

improved processors will greatly aid the development of the intelligent routines needed the advanced topology routines, learning, and environmental models. This too appears to be on a promising path with multiple core solutions being adopted by Intel and taken to the logical extreme by PicoChip whose picoArray contains hundreds of ARM processors. However, one of the more important unsolved issues facing cognitive radio is operational validation. As is the case for software radio, validating software is an NP-complete problem, i.e., for complete certainty in operation, every possible combination of inputs must be tried. For a cognitive radio expected to operate in many different environments with millions of possible adaptations, this could be a very lengthy process. While a number of different entities have recognized the importance of developing techniques for validating cognitive radio designs and implementations, e.g., testing for acceptable interference is the topic of IEEE 1900.2 and software module qualification is the subject of IEEE 1900.3, no generalizable techniques have yet been developed.

1.4.5 Interactive Cognitive Radios
While even minimally cognitive radios hold great promise, there is some concern that cognitive radios may negatively impact network performance. While how a cognitive radio can negatively impact network performance may not be immediately apparent from cognition cycle shown in Figure 1.1, a more realistic diagram of the processes of a cognitive radio in a network is shown in Figure 1.18 where cognitive radios react to both “dumb” and cognitive radios. Specifically, many cognitive radios will be reacting to an outside world whose state is jointly determined by the adaptations of several cognitive radios, making any network of two or more cognitive radios an interactive decision process.

50

Figure 1.18: The interactive cognitive radio model. Reproduced from Figure 15-1 in [Neel_06a]. While we intuitively understand the reaction of a cognitive radio to a collection of “dumb” radios, the interaction of a collection or cognitive radios is less clear as each cognitive radio waveform adaptation changes the state of the outside world for all the other radios. The actions of a collection of cognitive radios would then appear as a recursive interactive decision process as adaptation spawns adaptation after adaptation, perhaps infinitely as implied by Figure 1.19. Such an infinite process of adaptations makes performance guarantees difficult to make and networks nearly impossible to plan in a traditional sense. Further, while some authors have proposed having the receiver dynamically determine the adaptations of the transmitter; it seems more reasonable that any adaptations will be performed at least with the knowledge of the receiver, if not actually directed by the receiver. So an infinite recursion of adaptations may imply poor utilization of spectrum as bandwidth is consumed to signal these adaptations.

51

Figure 1.19: A network of adaptive radios that has fallen into an infinite adaptation recursion. Even when these adaptations do not continue infinitely, the final state of the network might be quite undesirable. For instance, consider a single cluster DS-SS network with a centralized receiver where all nodes other than the centralized receiver are adjusting their transmitted power levels in an attempt to maximize their signal-to- interference-plus-noise ratio (SINR) as measured at the receiver. The initial state in terms of transmit power levels (blue) and SINR (green) for this network are shown in Figure 1.20. Following this implied adaptation scheme, the final state for this network is shown in Figure 1.21 where all terminals are transmitting at their maximum power levels. Clearly this is an undesirable outcome as (1) capacity is greatly diminished due to near- far problems (unless the nodes are all at the same radius from the receiver) and counter to a goal of MANET operation, (2) the resulting SINRs are unfairly distributed (the closest node will have a far superior SINR to the furthest node), and (3) battery life would be greatly shortened.

52

Figure 1.20: Initial network state.

Figure 1.21: Final network state.

Abstracting the problem of interactive cognitive radios, consider a network of three radios where repeated adaptations define out paths in the action space (the combined set of all possible choices of waveforms by the three cognitive radios). Sometimes these paths terminate in a stable point; under different conditions the paths may enter an infinite loop. There may also be points in the action space which are fixed points of the decision update rule but are unstable as any small perturbation in initial conditions drive the network away from the point. Each of these concepts is illustrated in the example interaction diagram shown in Figure 1.22 where paths are shown by the arrows and fixed points are labeled as “NE” in reference to “Nash equilibrium” – a concept introduced in Chapter 4.

53

Figure 1.22: A three radio interaction diagram with three steady states (NE1 , NE2 , and NE3) and adaptation paths. This conceptual interaction diagram illustrates the four different analysis questions that we would like to answer when considering a network of interactive cognitive radios. ? ? ? ? What is the expected behavior of the network? Does this behavior yield desirable performance? What conditions must be satisfied to ensure that adaptations converge to this behavior? Is the network stable? To answer these questions, several researchers [Neel_06a] [MacKenzie_01] have proposed the use of game theory to analyze the interactions of autonomous adapting wireless devices.

1.5 Problem Statement and Research Contributions and Document Organization
This section refines the problem addressed by this work, describes the contributions made as part of this work

54

1.5.1 Problem Statement
This research addresses the issue presented in Section 1.4.5 – how can we ensure that cognitive radio algorithms will behave well in a network? Tackling this issue requires us to handle three inter-related issues. ? ? ? How do we model an interactive cognitive radio network? How do we ana lyze an interactive cognitive radio network? How do we design an interactive cognitive radio network?

1.5.1.1 Modeling
Modeling a cognitive radio network is a non-trivial task as cognitive radios can be implemented as either procedural or ontological radios and both implementation classes may be present in a single network. Thus to accurately model a cognitive radio network, we need models that simultaneously capture the adaptations and interactions of ontological and procedural (both deterministic and non-deterministic) radios. Further this model should be amenable to a wide variety of possible networking architectures, decision timings, waveform adaptations (possibly governed by policies), and operating environments. Of course, our models should also facilitate our analysis and design efforts.

1.5.1.2 Analysis
When analyzing a cognitive radio network, the interactions of a cognitive radio network can be viewed as creating a recursion of adaptations that modify the network state. As highlighted in Section 1.4.5, we wish to be able to analyze the recursions of cognitive radio algorithms to answer the following questions. ? ? ? ? Will the recursion have a fixed point (steady state) and can we identify the steadystate (or steady-states) so we can anticipate performance? Will that performance be desirable? What conditions will be necessary to ensure convergence? Will the steady-states be stable or will the inherent variations of the wireless medium make the system unpredictable?

55

While we could attempt to address these issues via simulation and experimentation, this will be a very time consuming task even for limited systems considering limited scenarios. For example, in [Ginde_03], a desktop simulation of a modeled GPRS network that incorporated power and rate adaptations required days to fully simulate all possible combinations of powers and rates for a system with just seven subscriber units in a fixed position. Expanding this simulation to account for more units, different positions or even mobility would have required months of simulation time. Instead, we would prefer to be able answer our questions in just minutes by mathematically analyzing the structure and characteristics of the interactions of cognitive radios algorithms. As such, the goal of this research is to present a methodology suitable for quickly analyzing many cognitive radio networks with interactive and recursive decision processes with a particular focus on the kinds of cognitive radio algorithms that are deployed today – transmit power control and adaptive interference avoidance. Further, rather than effectively reinventing the wheel for each new network and algorithm, if our analysis can follow a model-based approach analytical effort can be more efficiently spent on establishing results for generalizable models and model identification criteria.

1.5.1.3 Design
If we are only able to model and analyze the interactions of cognitive radio networks, that would be a useful result in and of itself. However, the design of cognitive radio networks would remain a hit-or- miss affair as we would not know how a network would perform until we analyze it. We would prefer to be able to leverage our insights from modeling and analyzing cognitive radio algorithms to formulate algorithm design rules that result in behavior that converges to stable desirable steady-states.

56

1.5.2 Research Contributions
This research presents an application- independent model of cognitive radio interactions which we can refine to application specific models dependent on the algorithms being studied. Addressing the analysis issues required the development of new models, new analysis results for contraction mappings, new applications of analysis techniques to cognitive radio algorithms, and the development of design frameworks. Techniques for analyzing procedural radios for determining steady-states, desirability, and stability are introduced based on dynamical systems, contraction mappings, and Markov chains. A game theoretic approach is proposed for the analysis of ontological radios and this is shown to be applicable to procedural radios as well. This research also refines two attractive game models – potential games and supermodular games – so they become suitable candidates for analysis of cognitive radio algorithms which required significant work developing the theoretical convergence and stability implications of these models as well as novel identification criteria. These approaches are applied to dynamic frequency selection (DFS) and transmit power control (TPC) algorithms – the two algorithms most commonly discussed for use in cognitive radios. An additional study of a self-configuring sensor network is also presented. These modeling and analysis results are leveraged to develop new algorithm design rules for cognitive radio ne tworks. These rules are shown to yield cognitive radio networks that are low complexity, scalable, convergent to optimal performance, and suitable for implementation in either procedural or ontological radios.

1.5.3 Document Organization
The remainder of this document is organized as follows. Chapter 2: Presents a model developed as part of this work suitable for modeling cognitive radio interactions. This model can be applied to all known cognitive radio algorithms and implementations and is amenable to a wide variety of analysis techniques. This model is used in all subsequent chapters.

57

Chapter 3:

Discusses techniques for analyzing procedural cognitive radios. The chapter addresses dynamical systems theory, contraction mappings, and Markov chain theory. Techniques for establishing steady-states, optimality, convergence, and stability are presented.

Chapter 4:

Describes how game theory can be used to model procedural and ontological cognitive radios. Normal form games and repeated games are covered. General game theoretic techniques for establishing steady-states, optimality, convergence, and stability are presented including the concepts of Nash equilibria (NE), Pareto optimality, and the Finite Improvement Property.

Chapter 5:

Presents the theory of potential games which are particularly well suited as a design framework for ontological radios. The chapter shows how potential games simplify NE identification, introduces techniques for guaranteeing optimal performance, and exhibit broad convergence and stability conditions. Several novel game theoretic results are introduced.

Chapter 6:

Leveraging potential game theory, proposes a novel framework for designing cognitive radio algorithms – the Interference Reducing Networks (IRN) framework. This framework is shown to result in behavior that minimizes sum network interference and is shown to be implementable with either procedural or ontological cognitive radios.

Chapter 7:

Focuses on a particular realization of the IRN framework for Dynamic Frequency Selection (DFS) intended for implementation on procedural or ontological cognitive radios. This algorithm is a low complexity highly scalable algorithm that only requires local observations, yet reduces the interference of all cognitive radios in the network.

58

Chapter 8:

As part of a process of introducing examples of a key game theory concept (weak FIP, this chapter presents the theory of supermodular games which are particularly well suited as a design framework for procedural radios. A commonly encountered class of ad-hoc power control algorithms is shown to be a supermodular game, and a sensor network algorithm is proposed and shown to have weak FIP.

Chapter 9:

Based on the modeling and analysis covered in the preceding chapters, this chapter draws conclusions on the design and implementation of cognitive radio networks and summarizes the results of this dissertation.

Original research contributions are made in every chapter in this dissertation. Sometimes an entire chapter is an original contribution. Other chapters present theory which needed refining for application to cognitive radios. For chapters where original and previous related work are interspersed, original definitions and theorems are marked by an asterisk. Table 1.2 lists major original contributions to the modeling, analysis, and design of cognitive radio interactions made as part of this work. Papers and awards resulting from this research are listed in Chapter 9. Chapter Chapter 1 Chapter 2 Chapter 3 Table 1.2: Major Novel Contributions Made as Part of this Work Research Contributions Definition of procedural and ontological cognitive radios. Definition of waveform General model of cognitive radio interactions Application of dynamical systems to the analysis of procedural radios Stability of standard interference function (SIF) Application of SIF to ad-hoc networks Application of game theory to cognitive radios General game model of cognitive radio networks Novel random better response algorithm with broader convergence conditions Convergence analysis for basic game theoretic properties under different decision timings Ergodic Markov chain model of noisy cognitive radio networks Necessary condition for convergence of myopic rational cognitive radios Application of potential games to wireless network design Multilateral Symmetric Interference Games Identification of ordinal potential games via better response 59

Chapter 4

Chapter 5

Chapter 6

Chapter 7 Chapter 8

transformations Convergence of round-robin/random better response algorithms for potential games with infinite action spaces Convergence of asynchronous better response algorithms for finite action spaces Stability of potential games for discrete time adaptations Interference Reducing Network (IRN) design framework Global altruism algorithm Local altruism algorithm Bilateral Symmetric Interference identification condition General algorithm for implementing an IRN in an isolated cluster Close proximity algorithm Impact of legacy devices Novel Dynamic Frequency Selection algorithm for ad-hoc networks and its performance under non- ideal circumstances Condition for uniqueness and stability of supermodular games A convergence proof of typical ad-hoc TPC algorithms Novel sensor network formation algorithm

1.6 References
[802.11h] Std 802.11h?-2003 Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment 5: Spectrum and Transmit Power Management Extensions in the 5 GHz band in Europe. IEEE New York, New York, October 2003. [802.21] 802.21 Working Group Web Page http://www.ieee802.org/21/ [Adapt4_06] Adapt4 Press Release, Jan http://www.adapt4.com/news/articles/xg1-receives-certification.php 12, 2006,

[Adapt4_Technology] Adapt4 technology webpage: http://www.adapt4.com/adapt4technology.php [American Heritage_00] The American Heritage ? Dictionary of the English Language, Fourth Edition, Houghton Mifflin Company, 2000. [Baclawski_05] K. Baclawski, D. Brady, and M. Kokar, “Achieving Dynamic Interoperability of Communication at the Data Link Layer through Ontology Based Reasoning”, 2005 SDR Forum Technical Conference, Nov. 14-17 Orange County CA, 2005. [Berlemann_05] L. Berlemann, S. Mangold, B. Walke, “Policy-based Reasoning for Spectrum Sharing in Cognitive Radio Networks,” IEEE DySPAN2005, Nov 8-11, 2005 Baltimore, MD. [Brown_05] T. Brown, “An Analysis of Unlicensed Device Operation in Licensed Broadcast Service Bands,” IEEE DySPAN2005, Nov 8-11, 2005 Baltimore, MD.

60

[Cordeiro_05] C. Cordeiro, L. Challapali, D. Birru, S. Shankar, “IEEE 802.22: The First Worldwide Wireless Standard based on Cognitive Radios,” IEEE DySPAN2005, Nov 811, 2005 Baltimore, MD. [Domalapally_04] D. Domalapally, J. Wang, Y. Zhang, “Reconfigurable Oscillator and Filter,” 2004 SDR Forum Technical Conference, Phoenix AZ. [Fehske_05] A. Fehske, J. Gaeddert, J. Reed, “A New Approach to Signal Classification using Spectral Correlation and Neural Networks,” IEEE DySPAN2005, Nov 8-11, 2005 Baltimore, MD. [Fette_05] B. Fette, “Introduction to Cognitive Radio,” SDR Forum Technical Conference 2005, Nov. 14-17, Orange County, CA. [FCC_05] ET Docket No. 03-108, March 11, 2005. [FCC_06a] “Office of Engineering and Technology Seeks Additional Comment on Petitions for Reconsideration for Unlicensed National Infrastructure Devices,” ET Docket No. 03-122, April 26, 2006. [FCC_06b] “Revision of Parts 2 and 15 of the Commission’s Rules to Permit Unlicensed National Information Infrastructure (U-NII) devices in the 5 GHz band,” ET Docket No. 03-122, June 30, 2006. [GDDS] AN/USC – 61(C) Software Defined Radio (SDR) System Brochure. Available online: http://www.gdc4s.com/documents/D-DMR-5-0704.pdf [Harris] RF-300M-HH brochure http://www.rfcomm.harris.com/jtrs/RF-300M-HH.pdf [Hatfield_05] D. Hatfield, “Spectrum Regulation 101,” DySPAN, Baltimore, MD, Nov. 8-11, 2005. [Haykin_05] S. Haykin, “Cognitive Radio: Brain- Empowered Wireless Communications,” IEEE Journal on Selected Areas in Communications, vol. 23, No 2, Feb. 2005. [IEEEUSA_03] “Improving Spectrum Usage through Cognitve Radio Technology,” IEEE USA Position, Nov 13, 2003, Available online: http://www.ieeeusa.org/policy/positions/cognitiveradio.asp [IEEE 1900.1] Draft Document, “Standard Definitions and Concepts for Spectrum Management and Advanced Radio System Technologies,” June 2, 2006. [Jondral_04] F. Jondral, “SPECTRUM POOLING - An Efficient Strategy for Radio Resource Sharing,” Blacksburg (VA), June 8, 2004. [Kokar_06] M. Kokar, D. Brady, K. Baclawski, “Roles of Ontologies in Cognitive Radios” in Cognitive Radio Technology, B. Fette, ed., Elsevier, 2006. [Le_05] B. Le, T. Rondeau, J. Reed, C. Bostian, “Past, Present, and Future of ADCs,” IEEE Signal Processing Magazine, to be published, November, 2005. [Le_06] B. Le, “Recognition and Adaptation in PHY laye r,” SDR Forum Workshop on Cognitive Radio, San Francisco, April 10, 2006.

61

[Lynch_05] R. Lynch, Keynote Address, IEEE DySPAN2005, Nov 8-11, 2005 Baltimore, MD. [MacKenzie_01] A. MacKenzie and S. Wicker, “Game theory and the design of Selfconfiguring, adaptive wireless networks” IEEE Communications Magazine, vol. 39, pp. 126-131, Nov. 2001. [Marshall_05a] P. Marshall, “Current R&D Investments in Dynamic Spectrum Technology,” DySPAN, Baltimore, MD, Nov. 8-11, 2005. [Marshall_05b] Remarks of Preston Marshall during Cognitive Radio Panel Session. 2005 SDR Forum Technical Conference, Nov 14-17, Orange County CA. [Marshall_06] P. Marshall, “Policy Languages, and Specifically, How Can We Standardize the Basis for Extensible Cognitive Radio Tools?” SDR Forum Workshop on Cognitive Radio, April 10, 2006. [McHenry_05] M. McHenry , “NSF Spectrum Occupancy Measurements Project Summary”, Aug. 15, 2005. Available online: http://www.sharedspectrum.com/?section=nsf_measurements [Mitola_99] J. Mitola, III, “Cognitive Radio for Flexible Multimedia Communications”, Mobile Multimedia Communications, 1999. (MoMuC '99) 1999 IEEE International Workshop on, pp. 3 –10, 1999. [Mitola_00] J. Mitola III, “Cognitive Radio: An Integrated Agent Architecture for Software Defined Radio,” PhD Dissertation Royal Institute of Technology, Stockholm, Sweden, May 2000. [Moessner_05] K. Moessner, G. Dimitrakopoulos, P. Demestichas, J. Luo,O. Sallent, C. Kloeck, “Dynamic Radio Resource Allocation Strategies and Time Scales,” SDR Forum Technical Confe rence 2005, Nov. 14-17, Orange County, CA, 2005. [Mohammed_05] M. Mohammed, “” Preliminary PhD Examination Report, Blacksburg, VA, Oct. 2005 [MPRG Demo] CoTeKs: Cognitive Policy-based Radio Demonstration at SDR Forum 2005 Technical Conference, November 2005, Orange County, CA. [Mudar_05] Comments of A. Mudar while presenting C. Ianculescu, A. Mudar, “Cognitive Radio and Dynamic Spectrum Sharing”, 2005 SDR Forum Technical Conference, Nov 14-17 Orange County, CA, 2005. [Neel, 1] J. Neel, J. Reed, R. Gilles, “Game Models for Cognitive Radio Analysis,” SDR Forum 2004 Technical Conference, Nov 2004, Phoenix, AZ. [Neel, 2] J. Neel, “Potential Games,” MPRG Technical Report, May 2005. Available Online: www.mprg.org/people/gametheory/publications.shtml [Neel, 3] J. Neel, R. Menon, A. MacKenzie, J. Reed, "Using Game Theory to Aid the Design of Physical Layer Cognitive Radio Algorithms," Conference on Economics, Technology and Policy of Unlicensed Spectrum, May 16-17 2005, Lansing, Michigan. [Neel, 4] J. Neel, J. Reed, and R. Gilles, “Convergence of Cognitive Radio Networks,” WCNC2004, March 25, 2004. 62

[Neel_06a] J. Neel. J. Reed, A. MacKenzie, Cognitive Radio Network Performance Analysis in Cognitive Radio Technology, B. Fette, ed., Elsevier 2006. [Neel, 6] J. Neel, “Game theory can be used to analyze cognitive radio” EE Times, Aug. 29, 2005. [Neel, 7] J. Neel, J. Reed, R. Gilles, “The Role of Game Theory in the Analysis of Software Radio Networks,” SDR Forum Technical Conference November, 2002. [Neel_06b] J. Neel, J. Reed, “Game theory implications for cognitive radio design,” SDR Forum Workshop on Cognitive Radio, San Francisco, April 10, 2006. [NTIA_05] Comments of the National Telecommunications and Information Administration on FCC ET Docket No. 03-108: “Facilitating Opportunities for Flexible, Efficient, And Reliable Spectrum Use Employing Cognitive Radio Technologies,” February 15, 2005. [Oh_04] S. Oh, J. Aberle, “Reconfigurable Antennas as an Enabling Technology for SDR”, 2004 SDR Forum Technical Conference, Phoenix AZ. [PicoChip] IEEE802.16 "WiMAX" Software Reference Designs. Available online: http://www.picochip.com/solutions/wimax [Rast_05] R. Rast, “The Dawn of Digital TV”, IEEE Spectrum, Oct 2005. Available online: http://www.spectrum.ieee.org/oct05/1911 [Rieser_04], C. Rieser, “Biologically Inspired Cognitive Radio Engine Model Utilizing Distributed Genetic Algorithms for Secure and Robust Wireless Communications and Networking,” PhD Dissertation, Virginia Tech, August 2004. [Rondeau_04] T. Rondeau, B. Le, C. Rieser, C. Bostian, “Cognitive Radios with Genetic Algorithms: Intelligent Control of Software Defined Radios”, SDR Forum 2004 Technical Conference, November 2004. [Segan_06] S. Segan, “Sprint Nextel Goes To The WiMax,” PC Magazine, August 8, 2006. Available online: http://abcnews.go.com/Technology/ZDM/story?id=2288147 [SDR Forum_05] “SDR Forum Yearbook 2005,” SDR Forum Technical Conference 2005, Nov 14-17, 2005 Orange County, CA. [Thales] JTRS Enhanced MBITR https://secure.thalescomminc.com/cart2/jemDesc.asp (JEM) webpage:

[Vanu_06] Vanu April 5, 2006 Press Release. Available online: http://vanu.com/news/prs/Vanu%20CTIA%20anywave%20demo%20CTIA%204-0506.pdf [VT CRWG] “Cognitive Radio Definition,” Virginia Tech Cognitive Radio Work Group Wiki. Availabile Online: http://support.mprg.org/dokuwiki/doku.php?id=cognitive_radio:definition [Winlab] Network Centric Cognitive Radio Platform. http://www.winlab.rutgers.edu/pub/docs/focus/Cognitive-Hw.html Homesite:

[WWRF_04] “Cognitive Radio, Spectrum and Radio Resource Management”, Wireless World Research Forum, Working Group 6 White Paper, December 2004. 63

[Zhang_04] H. Zhang and H. Dai, “On the Capacity of Distributed MIMO Systems,” 2004 Conference on Information Sciences and Systems, Princeton University, March 1719, 2004. [Zhao_06] Y. Zhao, B. Le, J. Reed, “ Infrastructure Support – The Radio Environment MAP,” in Cognitive Radio Technology, B. Fette, ed., Elsevier 2006.

64

Chapter 2: Modeling and Problem Formalization
“If we can really understand the problem, the answer will come out of it, because the answer is not separate from the problem.” - Jiddu Krishnamurti Before proceeding to develop solution techniques for cognitive radios interactions, we must first define what we wish to solve. This chapter presents a general model of the interactions of cognitive radios applicable to both procedural and ontological radios and refines the aspects of their behavior that we wish to be able to analyze.

2.1 A General Model of Cognitive Radio Interactions
Consider the interactive cognitive radio problem previously illustrated in Figure 1.18 and repeated in Figure 2.1. In this interaction problem, each radio reacts to observations of the outside world by choosing some adaptation (or waveform) that the radio believes will help bring it closer to its goal, whatever that goal may be. At any given point in time, the observation a cognitive radio makes will be a function of the passive operating environment of the network (the channel conditions and interference environment that would be observed if no cognitive radios were operating in the environment) and the decision processes of the cognitive radios – decision processes that may be implemented via procedures or via a reasoning engine. Regardless of the implementation of the decision process, by definition, the cognitive radios are guided in their adaptations by some goal.

65

Figure 2.1: The interactive cognitive radio problem. [Neel06] While application specific variables and models are introduced as needed later in this document, the following presents a collection of symbols and conventions that captures the general features of cognitive radio interaction and can be fashioned into a usable model of cognitive radio interactions. ? N – The (finite) set of cognitive radios in the network where n is the number of elements in N, N . ? ? i, j – Particular devices in N. Aj – The set of actions available to radio j . While these sets are quite limited for many radios, they include all available adaptations to the radio. As the adaptations can include a number of independent types of adaptations, e.g., power le vels, modulations, channel and source coding schemes, encryption algorithms, MAC algorithms, center frequencies, bandwidths, and routing algorithms, Aj will generally be a multidimensional set.

66

To simplify matters, we assume we are analyzing adaptations only over a short time interval so the Aj will not be a function of time, i.e., the radios are not learning new actions while they are adapting. This is consistent with the earlier discussion that cognitive radios’ learning processes are expected to be performed during sleep or prayer processes [Mitola_00]. However, if we consider time scales that spanned these sleep or prayer processes, Aj could be expected to grow as radio j learns new waveforms. ? A – The action space, i.e., set of all possible combinations of actions by the radios in the network. Throughout, we assume that A is formed by the Cartesian product of each radio’s action sets, i.e., A = A1 × A2 × L× An . For some algorithms, it is convenient to think of A as a vector space with orthogonal bases A1 through An . ? a – A particular combination of actions where each radio in N has implemented a particular action (waveform), i.e., a point in A or an action vector. Radio j ’s contribution to a is written as aj, and the choice of actions by all cognitive radios other than j is written as a-j. ? O – The set of all possible observed outcomes of the outside world as determined by the choice of actions available to each cognitive radio and the passive operating environment. ? oj – An observation made by or supplied to radio j . For instance, an SINR measurement. ? o – A vector of observed outcomes where all radios have observed an outcome. For instance, o may represent a vector of SINR measurements with each measurement associated with a particular cognitive radio. Frequently, we refer to this as an outcome. ? dj – The decision rule which describes how radio j updates its decisions based on observations. Strictly, dj is a function that relates actions to outcomes, i.e., d j : o j → A j . However, while the observed outcome may only be statistically rela ted to the action vector, we will assume for the purposes of analysis that the relationship between actions and observed

67

outcomes is known and treat each decision rule as a function that relates action vectors to actions, i.e., d j : A → Aj .

For procedural cognitive radios, the decision rule may be explicitly given; for ontological cognitive radios, we may have to make broad generalizations such as the implemented decision rule selects a locally optimal action or the radio behaves selfishly. A more formal treatment of decision rules for ontological radios is presented in Chapter 4. However, throughout this report, we assume that each radio’s decision rule is guided by its goal or utility function. ? uj(a) – The utility function which describes how much value radio j assigns to action vector a. Throughout this report we assume these values or utilities are described using real numbers, i.e., u j : A → ? . In general, the utility function expresses some goal that the radio is working towards whether explicitly (ontological cognitive radio) or implicitly (procedural cognitive radio). Again, a practical implementation of a cognitive radio’s goal would associate numbers with the radio’s observed outcomes, oj, and not the action vector as other radios’ actions will not generally be directly observable. However, for purposes of analysis we assume that the analyst knows the relation between actions and observed outcomes so that the analyst can express the utility function in terms of the action vector. Therefore, for analysis purposes, these utility functions capture the actions of the cognitive radios and the passive operating environment. Although elided in the introduction to this section, the exact times at which radios make their decisions can significantly influence the behavior of a network. In military circles, there is much effort placed on getting inside the enemy’s decision loop because of the potential advantages gained by the quicker decision maker. Or in a more mundane circumstance, anyone who has met someone head on in a hallway and proceeded to repeatedly block each others’ attempts to pass knows the effects that there is a significant difference between synchronous and asynchronous decision timings. To capture the

68

cognitive radio equivalent of these conditions, our model requires addition of the following symbols and conventions. ? Tj – The times at which radio j can update its decision (a radio may have a time allocated for updating, but choose not to update its decision). Unless stated
1 m otherwise, we assume that each Tj is infinite, i.e., T j = {t 0 j , t j , K, t j , K} . As we are

ultimately modeling interactive software processes, we always assume that Tj is a discrete set. ? T – The set of all times where decision updates can occur, i.e., T = T1 U T2 ULU Tn , where t ∈ T denotes a particular updating time. For convenience, we treat t k as the k th element of T arranged chronologically. Further, when appropriate, we also use the notation d t to denote the network decision rule at time t where in general d t captures the adaptations of the subset of radios that update their decisions at time t , i.e., d t = × dk , M ? N . While it is also possible that a
k ∈M

radio bases its decisions on past observations and predictions about the future state of the network, this text assumes that d tj is only a function of cognitive radio j ’s most recent observation. Additionally, we make use of the following terms in describing the timing of the decision update process: synchronous decision processes, round-robin decision processes, random decision processes, and asynchronous decision processes. Definition 2.1 : Synchronous decision process If ?t ∈ T , d t = × d k , then we say that the network has a synchronous decision process
k∈N

and write a

t k+ 1

= d tk a tk .

( )

Definition 2.2 : Round-robin decision process m m If t1m < t2m < t 3 < L < tn < t1m+1 , then we say that the network is updating its decisions in round-robin order.

69

Definition 2.3 : Random decision process If ?t ∈ T d t = rand {d k } , then we say that the network is updating its decisions in
k∈ N

random order Definition 2.4 : Asynchronous set decision process If ?t ∈ T d t = rand {d k } , then we say that the network is updating its decisions in N
k∈ 2

random order For asynchronously updating networks, there may be some points in time where tim = t k j (the mth update of radio i occurs at the same time as the k th update of radio j ) is satisfied for two or more radios. As we will see in subsequent sections, these different decision update timings – synchronous, round robin, random, and asynchronous – can have a significant impact on the analysis of our cognitive radio network. Systems with synchronous timings are most frequently encountered in centralized systems and thus will be rarely encountered in an interactive cognitive radio decision process as an interactive decision process implies some degree of distributed decision timings. A round-robin scheme can occur in centralized systems with distributed decision making with scheduling (as might occur in a hybrid ARQ scheme). Without a synchronizing agent and assuming an arbitrary fineness in the time scale, every distributed cognitive radio algorithm will be a randomly decision process. Ho wever, because real- world observations necessitate processing data collected over noninfinitesimal intervals and because of signal propagation delays, a system with random timings will behave more like an asynchronous system. Summarizing this discussion, the basic model of cognitive radio interaction consists of a collection of a collection of cognitive radios, N, an action space A, a utility function for each cognitive radio j ∈ N which is a function of the actions of each radio and the passive operating environment, a decision rule for each cognitive radio, and a set of times at which these decisions occur. This can be compactly represented as the 5-tuple shown in (2.1).

70

N , A, {u j } ,{d j } , T

(2.1)

The following chapters illustrate how this model can be applied to networks of procedural and ontological radios. For procedural radios, we place increased modeling emphasis on the decision rules; for ontological radios, we place increased emphasis on the radios’ goals. If we ignore the mapping from actions to outcomes, our model is implementation independent, though not particularly useful for analysis. With the mapping from actions to outcomes in place, our m odel is implementation specific – useful for analysis, though difficult to generalize.

Example 2.1: Example: Modeling a Cognitive Radio Algorithm Consider two cognitive radios, {1,2}, with actions (waveforms) {ω1a ,ω1b } and {ω2a , ω 2b } , respectively, that are communicating with a common receiver which reports to each cognitive radio that radio’s signal-to-interference ratio (SIR). In this scenario, there are four different possible elements in A, which form the set

{(ω

1a

,ω 2a , ω1a ,ω2b ,

)(

)



1b

, ω2a , ω1b , ω 2b

)(

)} . However, there are an infinite number of possible observations due

to the infinite number of passive operating environments. In this case, the passive operating environment is defined by the gains from each cognitive radio to the common receiver, g1 and g2 . We’ll consider the interference that one waveform induces on the other to be given by the absolute value of the correlation of their signal space representations, ρ ( ωj , ω? j ) where ωj is the waveform chosen by radio

j ∈ {1, 2} and ω ? j is the waveform chosen by the other radio. In such a system, the
observed outcome for each radio j is given by the SIR equation given in (2.2) where j ∈ {1, 2} , γ j is the observed SIR for radio j , g j is the link budget gain of radio j to the common receiver, and g ? j is the gain of the other radio to the common receiver.

71

oj =γ j =

g ? j ρ ( ωj , ω? j )

gj

(2.2)

A reasonable goal or a utility function for a cognitive radio operating in this system would be to maximize (2.2) so that the greater the SIR the radio achieves, the higher the value the radio assigns to the outcome. Note that this goal incorporates both the relevant information from the passive operating environment (in this case, the link gains), the potential actions that could be taken by the radios, and the interactive nature of those actions. Particularly as each radio only has two waveforms to choose from, it seems reasonable to assume that whether procedurally or ontologically each radio implements a locally optimal decision rule or more formally as given in (2.3).

gj d j ( a ) = argmax ω j ∈{ ω j a ,ω j b } g ? j ρ ( ω j , ω? j )

(2.3)

Finally, by controlling when observations are returned to the cognitive radios, the common receiver could conceivably enforce any decision timing scheme. However, this example will assume that adaptations occur in a round robin fashion with one adaptation permitted each half second, e.g.., T1 = n sec and T2 = n + 0.5 sec where n ∈ ? . Based on this discussion, these various modeling parameters can be compactly summarized as shown in Table 2.1.

72

Table 2.1: Parameters for Example Model General Model Symbols N (cognitive radio set) A (action space) {uj} (utility functions) {dj} (decision rules) Tj (decision timings) Modeled System Parameters {1,2}

{(ω

1a

,ω 2a , ω1a ,ω2b , ω1b , ω2a , ω1b , ω 2b

)(

)(

)(

)}

u j ( a) =

g ? j ρ ( ωj , ω? j )

gj

d j ( a ) = argmax u j ( a ) ω j∈{wj a ,ω jb } T2 – 0.5s = T1 = N

2.2 Analysis Objectives
By using these modeling parameters and considering another example of cognitive radio interaction, we can begin to formalize our analysis objectives. Consider a network of three radios where each radio, j ∈ {1,2,3} , can choose actions from a convex action set, Aj, according to its decision update rule dj. Starting at any initial action vector, the repeated application of the decision update rules trace out paths in the action space. Definition 2.5 : Path A path is a sequence of action vectors, {atk } formed by the recursion a tk+1 = d tk ( a tk ) . Note that even if the same network decision rule and the same passive operating environment are used, different paths result from different initial points, a0 . Conceptually, a path may terminate in a stable point, but under different conditions a path may enter an infinite loop. There may also be points in the action space that are fixed points of the decision update rule but are unstable so that any small perturbation in initial conditions drives the network away from the point. Each of these concepts is illustrated in the example interaction diagram shown in Figure 2.2 where paths are shown by the arrows and fixed points are labeled as “NE” for reasons that will become clear in Chapter 4.

73

Figure 2.2: A three radio interaction diagram with three steady states (NE1 , NE2 , and NE3) and adaptation paths. This conceptual interaction diagram illustrates the four different analysis questions we identified in Chapter 1 that we would like to answer when analyzing the interactions of a network of cognitive radios. 1. What is the expected behavior of the network? 2. Does this behavior yield desirable performance? 3. What conditions must be satisfied to ensure that adaptations converge to this behavior? 4. Is the network stable? The following formalizes the analysis objectives underlying each of these questions and previews some of the techniques introduced later in this text.

2.2.1

Establishing Expected Behavior

As is the case for many systems, the analysis in this report assumes that expected behavior of a cognitive radio network is equivalent to its steady-state behavior. Accordingly, establishing expected behavior is concerned with addressing the following issues: 74

? ?

Existence – Does the system have a steady state? Identification – What are the specific steady states for the system?

In general, we will consider an action vector, a* ∈A, to be a steady state for a network if it is a fixed point of the decision rule, a condition that is expressed more formally in Definition 2.6. Definition 2.6 : Steady state An action vector a* is a steady state for the cognitive radio network N , A, {u j } ,{d j } , T if there is some t * ∈T such that for all t ≥ t * , d t ( a* ) = a * .

Subsequent chapters will introduce a number of different techniques for demonstrating that a steady state exists and for identifying the steady states of the network. These include showing that the network decision rule is a variant of a contraction mapping, that the network can be modeled as an absorbing Markov chain, and that the network obeys certain game theoretic properties. 1

2.2.2

Desirability of Expected Behavior

Of course, determining a cognitive radio network’s steady states tells us nothing about whether or not we should implement the algorithm under study. We also need to address whether or not those steady states are “good” steady states of “bad” steady states and if there are other action vectors that would be preferable from a network designer’s perspective. Again, there are two specific issues that we would like to address: ? ? Desirability – How “good” are the steady states of the algorithm? Optimality – Does an optimal action vector exist and how close do the steady states come to achieving optimal performance? There are many different ways of identifying whether or not an action vector is a “good” steady state, but we will make the assumption that the network designer has some objective function, J : A → ? that he/she wishes to maximize or minimize (perhaps total system goodput or spectrum utilization). Assuming we wish to maximize J, we’ll treat
1

Contraction mapping and absorbing Markov chain are defined in Chapter 3. The associated game theoretic techniques are defined in Chapters 4 and following.

75

action vector a2 as more desirable than a1 if J ( a 2 ) > J ( a1 ) . To determine if an optimal action vector exists and if our steady states are indeed optimal, subsequent chapters will introduce gradient techniques and Pareto optimality criteria.

2.2.3

Convergence Conditions

Even if we demonstrate that a cognitive radio network has desirable steady states, it is important to identify the conditions (decision rules, passive operating environments, initial conditions) under which paths converge, a concept formalized in Definition 2.7. Definition 2.7 : Convergence Given path {atk } , we say that the path converges to some action vector a* ∈A if for every

ε > 0 , there is a t * ∈ T such that t ≥ t * implies a t , a * < ε .
In other words, path {atk } converges to a* if for every arbitrarily small region around a* that we might define, there is a time after which {atk } remains “trapped” in that region. For convergence, this research addresses the following issues: ? Rate – Given converges? ? Sensitivity – How do changes in the value of a0 , slight variations in d t (perhaps asynchronous instead of round-robin timings) or changes in the passive operating environment impact the paths and the network’s steady states? Frequently when assessing convergence this text considers a time-independent decision rule, d, coupled with varying timings for implementing decision rule. For example, this text considers time-independent decision rules corresponding to locally optimal decisions, directional improvement, and randomly selected better responses coupled with synchronous, asynchronous, random, or round robin decision timings. This approach allows us to establish the sensitivity of the decis ion rules to timing variations more precisely.

*

{a } and
tk

ε > 0 , what is the value of t * such that the path

76

2.2.4

Network Stability

Implicitly, the preceding analysis objectives assume the radios have perfect knowledge of their operating environment and behave deterministically. However, wireless networks are stochastic, not deterministic. Accordingly, the cognitive radios’ observations will not be the deterministic functions and instead will be estimates of their operating environment. Because these are only estimates, the radios will frequently make adaptations that appear to be mistakes to the analyst. While this research assumes the radios’ estimates and errors are unbiased, there is the concern of stability as small perturbations could potentially lead to undesirable behavior. Because of this concern, this research addresses the following analytical issues with respect to a network decision rule’s steady state(s): ? ? Lyapunov stability – After a small perturbation, will stay the system within a bounded region about the steady state? Attractivity – After a small perturbation, will the network converge back to the steady state?

2.3 Summary
This chapter has presented a generalized model of cognitive radio interactions and identified important analysis objectives. This model is defined by the tuple
N , A, {ui } ,{di } ,T

where the associated symbols are summarized in Table 2.2.

Subsequent chapters provide application-specific refinements of this model and introduce techniques for determining steady states, desirability of those steady states, convergence criteria, and stability. Table 2.2: Symbol Summary Symbol N Aj a-j O dj T Meaning Set of cognitive radios Adaptations for j Adaptation vector excluding aj Set of outcomes Decision rule for j Adaptation times ?j ∈N Symbol i, j aj uj Oj Tj t Meaning Particular cognitive radios Adaptation chosen by j Goal of j Outcome observed by j Times when j adapts An element of T

77

In general we will seek to design cognitive radio algorithms such that all of their steadystates maximize the design objective for the particular application, are converged to and are stable under the broadest possible conditions, and require a minimal amount of signaling overhead and device resources to realize the algorithm. While this seems to be an impossible order to fill, by leveraging the analysis insights of the subsequent chapters, Chapters 6, 7, and 8 present several algorithms that meet all of these objectives.

2.4 References
[Mitola_00] J. Mitola III, “Cognitive Radio: An Integrated Agent Architecture for Software Defined Radio,” Ph.D. Dissertation Royal Institute of Technology, Stockholm, Sweden, May 2000. [Neel_06] J. Neel. J. Reed, A. MacKenzie, “Cognitive Radio Network Performance Analysis” in Cognitive Radio Technology, B. Fette, ed., Elsevier August 11, 2006.

78

Chapter 3: Tools for Analyzing the Interactions of Procedural Radios 1
“Before thinking outside the box, one should know what’s in the box. The box tends to have a lot of good ideas – that’s how they came to be in the box.” In this chapter we consider the problem of analyzing the interactions procedural radios based on the model presented in Chapter 2. In general, we can study the interactions of procedural radios via a reduced model that excludes their goals, namely the tuple N , A,{d j } , T . As this chapter shows, many traditional analysis techniques from engineering can be applied to the analysis of procedural radios, including dynamical systems theory, optimization theory, parallel processing (contraction mappings), and Markov chain theory. Before cognitive radio, before SDR, these techniques were being applied to the analysis of wireless algorithms. And as we show in this chapter, they are still useful for the analysis of procedural cognitive radios. Further, when we turn to the analysis of ontological radios in subsequent chapters many of the concepts presented in this chapter resurface. The remainder of this chapter is organized as follows. Section 3.1 considers dynamical systems and describes how the evolution function can be used to determine steady-states, optimality, convergence, and stability. Section 3.2 presents variants on contraction mappings, including the standard interference function and pseudo-contractions, and describes how they can be used to determine steady-states, optimality, convergence, and stability. Section 3.3 presents Markov chain theory which can be used to determine steady-states, optimality, convergence, and stability for non-deterministic procedural radios.

3.1 A Dynamical Systems Approach
Dynamical systems theory is concerned with analyzing the behavior of dynamical systems and designing mechanisms so the systems act in a desirable manner. Typical

1

This chapter is based on a section in J. Neel. J. Reed, A. MacKenzie, "Cognitive Radio Network Performance Analysis" in Cognitive Radio Technology, B. Fette, ed., Elsevier, July 28 2006.

79

analysis goals of dynamical systems theory are similar to the ones that we set out in Chapter 2: determining the expected behavior, convergence, and stability of the system. Formally, a dynamical system is a system whose change in state is determined by a function of the current state and time. In other words, a dynamical system is any system of the form given by (3.1) which describes the change in the state of a system as a function of the system state, a, and time, t . Implicitly the system is assumed to be at state a(0) at time t =0.

& = g (a , t ) a
When (3.1)

(3.1)

& = g ( a ) , the system is said to be is not directly dependent on t , i.e., a

autonomous. For our purposes, it makes sense to treat synchronous systems as autonomous, but for random and asynchronous systems, it is difficult to eliminate the time dependency. The first goal of a dynamical systems analyst is to solve (3.1) to yield the evolution function that describes the state of the system as a function of time. This typically involves solving an ordinary differential equation – a task that we would preferably not undertake without knowing that a solution exists. Given a dynamical systems model, we can be assured that such a solution exists by the Picard-Lindel?f theorem [Walker_80]. Theorem 3.1 : Picard-Lindel?f Theorem Given an open set D ? A× T and g as in (3.1), if g is continuous on D and locally Lipschitz with respect to a for every a ∈ D , then there is a unique solution, d t , to the dynamical system for every a (0) while d t remains in D. Note that Theorem 3.1 requires that g is not only continuous, but also locally Lipschitz – a term we define in Definition 3.1. Note that any function that is Lipschitz continuous is also continuous.

80

Definition 3.1 : Lipschitz continuity A function, d t : A × T → A, A ? ?n 2 is said to be Lipschitz continuous 3 at ( a, t ) if there

exists a K < ∞ such that d t (a 1, t ) ? d t (a 2, t ) ≤ K a1 ? a 2 for all a1 , a 2 ∈ A ; dt would be locally Lipschitz continuous if this condition were only satisfied for some open set D ? A× T . Similarly the function d is Lipschitz continuous if it is Lipschitz continuous for all ( a, t ) ∈ A × T . In general, the solution to (3.1) will take the form of the decision update rule, d t , which we assumed existed as part of our model. So this section primarily serves the purpose of connecting our model to the model traditionally assumed in dynamical systems. However, Theorem 3.1 foreshadows the importance of fixed point theorems to the steady-states of procedural radio networks.

3.1.1 Fixed Points and Solutions to Cognitive Radio Networks
A solution for the evolution function d t may imply a system that is changing states over time, perhaps bounded within a certain region or wandering over the entire action space. For some systems, continual adaptations may not be an issue and may even be desirable. Howeve r, continual adaptations for a cognitive radio network implies that significant bandwidth is being consumed to support the signaling overhead required to support these adaptations. For a cognitive radio network, we would prefer that the network settle down to a particular steady state and only adapt as the environment changes. Identifying these steady-states also allows a cognitive radio designer to predict network performance. In the context of our state equation, such a steady state is a fixed point of d t . Definition 3.2 : Fixed Point A point a * ∈ A is said to be a fixed point of d t : A → A if a * = d t ( a* ) ? t ≥ t* .

2

d t is a function that maps from the Cartesian Product of the action space with the set of all update times to the action space, where the action space is a subset of all real n -tuples; that is, given an initial action state, it forms the action space over all time. 3 A function, d t , is Lipschitz continuous if there exists a finite real K, such that for all action states a1 and a 2 in the action space, the Euclidean distance between d t (a 1 ) and d t (a 2 ) is less than K times the distance between a 1 and a2 .

81

For one dimensional sets, it is convenient to envision a fixed point of a function as a point where the function intersects the line x = f ( x ) . Figure 3.1 illustrates a function, f (x ), that has three fixed points.

f(x)

0

x

Figure 3.1: A function with three fixed points (circled). For functions on a one dimensional sets, the points at which the function intersect the line f (x ) = x (dashed) are fixed points. Solving for fixed points can be tedious as it may involve a search over the entire action space (an impossibility for an infinite action space, and a considerable undertaking for most realistic finite action spaces), so we would like to know if a fixed point exists before we begin our search. Fortunately, this can be readily established by the Leray-SchauderTychonoff fixed point theorem given by Proposition 1.3 in Chapter 3 of [Bertsekas_97]. 4 Theorem 3.2 : Leray-Schauder-Tychonoff Fixed Point Theorem If A ? ?n is nonempty, convex, and compact (see Appendix B ), and if d : A → A is a * * continuous function, then there exists some a ∈ A such that a = d t ( a* ) .5 However, there are several limitations to this theorem. First, the theorem is inappropriate for finite action sets – a likely condition – as while finite sets are compact, they are not convex. Second, d may not be a continuous function. Third, actually solving for a fixed point under such general conditions can be much harder, though under these conditions we simultaneous solution of (3.2) is appropriate for identifying steady-states.

4 5

The game theorist may

相关文章:
更多相关标签: