Cognitive MAC Protocols for Mobile Ad-Hoc Networks Abdullah Masrub A thesis submitted in fulfilment of the requirements For the degree of Doctor of Philosophy (PhD) Electronic and Computer Engineering School of Engineering and Design Brunel University, London United Kingdom -June 2013- Abstract The term of Cognitive Radio (CR) used to indicate that spectrum radio could be accessed dynamically and opportunistically by unlicensed users. In CR Networks, Interference between nodes, hidden terminal problem, and spectrum sensing errors are big issues to be widely discussed in the research field nowadays. To improve the performance of such kind of networks, this thesis proposes Cognitive Medium Access Control (MAC) protocols for Mobile Ad-Hoc Networks (MANETs). From the concept of CR, this thesis has been able to develop a cognitive MAC framework in which a cognitive process consisting of cognitive elements is considered, which can make efficient decisions to optimise the CR network. In this context, three different scenarios to maximize the secondary user's throughput have been proposed. We found that the throughput improvement depends on the transition probabilities. However, considering the past information state of the spectrum can dramatically increases the secondary user's throughput by up to 40%. Moreover, by increasing the number of channels, the throughput of the network can be improved about 25%. Furthermore, to study the impact of Physical (PHY) Layer errors on cognitive MAC layer in MANETs, in this thesis, a Sensing Error-Aware MAC protocols for MANETs has been proposed. The developed model has been able to improve the MAC layer performance under the challenge of sensing errors. In this context, the proposed model examined two sensing error probabilities: the false alarm probability and the missed detection probability. The simulation results have shown that both probabilities could be adapted to maintain the false alarm probability at certain values to achieve good results. Finally, in this thesis, a cooperative sensing scheme with interference mitigation for Cognitive Wireless Mesh Networks (CogMesh) has been proposed. Moreover, a priority- based traffic scenario to analyze the problem of packet delay and a novel technique for dynamic channel allocation in CogMesh is presented. Considering each channel in the system as a sub-server, the average delay of the users' packets is reduced and the cooperative sensing scenario dramatically increases the network throughput 50% more as the number of arrival rate is increased. I TTTToooo MMMMyyyy PPPPaaaarrrreeeennnnttttssss II Acknowledgments I would like to thank my supervisor, Professor Hamed Al-Raweshidy, for his valuable advices, encouragement and guidance during my PhD study. He has been very kind, helpful, and supportive throughout the whole work. My deep thanks are also dedicated to my parents, wife, and children Muna, Jana and Taha for being beside me as a source of care, love, motivation and encouragement, which fill me with patience and commitment. Especially to my parents who always urged me to pursue higher level of education. It is my pleasure to thank all my friends and colleagues in Wireless Networks and Communications Centre (WNCC), friends and colleagues at Brunel University and University of Al-Mergib, who always show their care and support, especially those who made this thesis possible. Finally, I gratefully acknowledge my family for their support through time and distance. I am proud of bringing them this accomplishment. III Table of Contents Chapter 1 .................................................................................................................................... 1 Introduction .......................................................................................................................... 1 1.1 Motivations ................................................................................................................ 1 1.2 Aims and Objectives ................................................................................................... 2 1.3 Contribution ............................................................................................................... 3 1.4 Research Methodology .............................................................................................. 4 1.5 Thesis Structure ......................................................................................................... 5 Chapter 2 .................................................................................................................................... 8 Resource Allocation and Channel Assignment ................................................................... 8 2.1 Introduction ............................................................................................................... 8 2.1.1 Characteristics and Advantages .................................................................................... 11 2.2 Wireless Networking ................................................................................................ 12 2.2.1 OSI Model ...................................................................................................................... 12 2.2.2 The Physical Layer ......................................................................................................... 13 2.2.3 The MAC Layer .............................................................................................................. 13 2.2.4 Service Primitives .......................................................................................................... 15 2.3 Multiple Access ........................................................................................................ 16 2.3.1 ALOHA Protocol............................................................................................................. 18 2.3.2 CSMA ............................................................................................................................. 19 2.3.3 IEEE 802.11 standard .................................................................................................... 23 2.3.4 TDMA ............................................................................................................................ 26 2.3.5 FDMA............................................................................................................................. 28 2.3.6 CDMA ............................................................................................................................ 29 2.3.7 OFDMA .......................................................................................................................... 31 2.4 Cognitive Radio ........................................................................................................ 32 2.4.1 Software Defined Radio (SDR) ...................................................................................... 33 2.4.2 Concept and Definition ................................................................................................. 34 2.4.3 Goals and Evolution ...................................................................................................... 36 2.4.4 Reasons and Facts ......................................................................................................... 39 2.4.5 Opportunities and Sharing ............................................................................................ 41 IV 2.5 Conclusion ................................................................................................................ 43 Chapter 3 .................................................................................................................................. 49 Multi-Channel Time Slotted Cognitive MAC Protocols for MANETs .............................. 49 3.1 Introduction ............................................................................................................. 49 3.2 Development of MAC Design ................................................................................... 50 3.2.1 Common Control Channel (CCC) ................................................................................... 50 3.2.2 Multichannel Hidden Terminal Problem ....................................................................... 51 3.2.3 Interference Temperature Measurement .................................................................... 52 3.2.4 Mobility of the users ..................................................................................................... 53 3.2.5 Multi-user Sensing ........................................................................................................ 53 3.3 Background and Related Work ................................................................................ 54 3.3.1 Spectrum Access Models .............................................................................................. 54 3.3.1.1 Direct Access Approach............................................................................................. 56 3.3.1.2 Graph Theory Approach: ........................................................................................... 57 3.3.1.3 Game Theory Approach: ........................................................................................... 58 3.3.1.4 Markov Decision Process Approach: ......................................................................... 59 3.3.2 Scheduling of CR MAC Protocols ................................................................................... 59 3.4 Proposed Model ....................................................................................................... 60 3.4.1 POMDP Framework ....................................................................................................... 60 3.4.2 Primary Network description ........................................................................................ 62 3.4.3 CR user strategy ............................................................................................................ 64 3.4.4 Network Components ................................................................................................... 65 3.4.5 Problem Formulation .................................................................................................... 67 3.5 Simulation Results .................................................................................................... 68 3.5.1 Throughput with different scenarios ............................................................................ 69 3.5.2 Throughput comparison ............................................................................................... 72 3.5.3 Throughput with different number of channels ........................................................... 73 3.6 Conclusion ................................................................................................................ 75 Chapter 4 .................................................................................................................................. 82 Sensing Error-Aware Cognitive MAC protocols for MANETs .......................................... 82 4.1 Introduction ............................................................................................................. 82 V 4.2 Background and Related Work ................................................................................ 83 4.2.1 Spectrum Sensing Methodologies ................................................................................ 83 4.2.2 Design challenges for spectrum sensing ....................................................................... 87 4.2.3 MAC and PHY Layers sensing ........................................................................................ 89 4.2.3.1 MAC Layer Sensing .................................................................................................... 90 4.2.3.2 PHY Layer Sensing ..................................................................................................... 91 4.2.4 Related Work ................................................................................................................ 94 4.3 System Model .......................................................................................................... 96 4.3.1 Network Description ..................................................................................................... 96 4.3.2 Time Slotted Spectrum Sensing .................................................................................... 97 4.3.2.1 Problem Formulation ................................................................................................ 97 4.3.2.2 Joint Sensing and Scheduling .................................................................................... 99 4.4 Simulation Results .................................................................................................. 100 4.5 Conclusion .............................................................................................................. 103 Chapter 5 ................................................................................................................................ 109 Priority Based and Cooperative Sensing for Cognitive Wireless Mesh Networks ...... 109 5.1 Introduction ........................................................................................................... 109 5.1.1 Cognitive Wireless Mesh Networks ............................................................................ 111 5.1.2 Cooperative Spectrum Sensing ................................................................................... 112 5.2 Related Work ......................................................................................................... 117 5.3 System Model ........................................................................................................ 119 5.3.1 Problem Formulation .................................................................................................. 122 5.3.2 Interference avoidance ............................................................................................... 123 5.3.3 Message Fragmentation ............................................................................................. 125 5.3.4 The Sensing and Access Strategy ................................................................................ 126 5.3.4.1 Individual Behavior ................................................................................................. 126 5.3.4.2 Cooperative Behavior.............................................................................................. 126 5.3.4.3 Throughput Aggregation ......................................................................................... 127 5.3.5 Waiting Time Analysis ................................................................................................. 128 5.4 Simulation Results .................................................................................................. 131 5.4.1 Impact of Sensing Errors on MAC Performance ......................................................... 131 5.4.2 Waiting Time Analysis and System Throughput ......................................................... 134 VI 5.5 Conclusion .............................................................................................................. 138 Chapter 6 ................................................................................................................................ 143 Conclusion ......................................................................................................................... 143 List of Papers ..................................................................................................................... 145 VII List of Figures Figure 2-1: Infrastructure based wireless network ................................................................................. 9 Figure 2-2: Mobile ad-hoc network ...................................................................................................... 10 Figure 2-3: The seven layers of the OSI reference model ..................................................................... 12 Figure 2-4: The MAC and PHY layers structure ..................................................................................... 14 Figure 2-5: The service primitives ......................................................................................................... 15 Figure 2-6: Multiple access schemes .................................................................................................... 17 Figure 2-7: Overlapping frames problem in the pure ALOHA ............................................................... 18 Figure 2-8: Time slots in slotted ALOHA ............................................................................................... 19 Figure 2-9: CSMA/CA channel access mechanism ................................................................................ 20 Figure 2-10: The hidden terminal problem ........................................................................................... 21 Figure 2-11: The exposed terminal problem ........................................................................................ 22 Figure 2-12: The different inter-frame spaces defined by the IEEE 802.11 MAC ................................. 24 Figure 2-13: Virtual carrier sense procedure ........................................................................................ 25 Figure 2-14: Time slots in TDMA ........................................................................................................... 27 Figure 2-15: Channel access mechanism in TDMA system ................................................................... 27 Figure 2-16: Frequency bands in FDMA ................................................................................................ 28 Figure 2-17: The spread signal in CDMA ............................................................................................... 30 Figure 2-18: Multiple access scenarios in OFDMA system ................................................................... 32 Figure 2-19: A comparison between software radio and cognitive radio ............................................ 36 Figure 2-20: Functional portions of a cognitive radio ........................................................................... 38 Figure 2-21: Illustration of occupied and white spaces in CR Networks............................................... 41 Figure 3-1: A POMDP framework .......................................................................................................... 61 Figure 3-2: The markov process model for N = 1, two possible states {busy state: S = 0, and idle state: S = 1}...................................................................................................................................................... 63 Figure 3-3: The primary network model: N independent channels with T time slots .......................... 64 Figure 3-4: Throughput comparison using Equation (3-13) with different parameters (bandwidth B = 1, number of channels N = 3, and different transition probabilities {P01, P11}) ................................. 69 Figure 3-5: Throughput comparison using Equation (3-14) with different parameters (bandwidth B = 1, number of channels N = 3, and ignoring the transition probabilities in updating the belief state) . 70 Figure 3-6: Throughput comparison using Equation (3-14) with different parameters (bandwidth B = 1, number of channels N = 3, and generating the initial belief state randomly) .................................. 71 Figure 3-7: Throughput comparison using Equation (3-13), (3-14) and the scheme results proposed in [37]: ....................................................................................................................................................... 73 VIII Figure 3-8: Throughput comparison using Equation (3-13) with different parameters (bandwidth B = 1, transition probabilities {P01 = 0.1, P11 = 0.9}, and different number of channels N) ...................... 74 Figure 3-9: Throughput comparison using Equation (3-14) with different parameters (bandwidth B = 1, different number of channels N, and ignoring the transition probabilities in updating the belief state) ..................................................................................................................................................... 74 Figure 3-10: Throughput comparison using Equation (3-14) with different parameters (bandwidth B = 1, different number of channels N, and generating the initial belief state randomly) ........................ 75 Figure 4-1: The scenario of cooperative spectrum sensing in CR Networks ........................................ 86 Figure 4-2: Illustration of hidden primary user in CR networks ............................................................ 87 Figure 4- 3: The architecture for collaborative spectrum sensing in a CR network .............................. 87 Figure 4-4: Shadowing which caused by the hidden terminal problem ............................................... 88 Figure 4-5: False alarm probability vs. threshold .................................................................................. 99 Figure 4-6: Throughput comparison vs. SNR with different parameters (bandwidth B = 1, number of channels N = 3, and different values of missed detection)................................................................. 101 Figure 4-7: Spectrum efficiency vs. SNR with different parameters (bandwidth B = 1, number of channels N = 3, and different values of missed detection probability) .............................................. 102 Figure 5-1: Wireless Mesh Network Topology: Multiple nodes cooperate to relay a message to its destination .......................................................................................................................................... 110 Figure 5-2: Schematic representation of weighting cooperation for spectrum sensing in CR networks ............................................................................................................................................................ 113 Figure 5-3: Data fusion for cooperative sensing. (a) In centralized mode, the sensing results of individual CRs are sent to a fusion centre in which a global decision is made. (b) In distributed mode, each CR acts as a fusion centre, collecting the sensing measurements from its neighbouring nodes and making its decision independently. ............................................................................................. 114 Figure 5-4: A CogMesh Network ......................................................................................................... 120 Figure 5-5: Two dimensional array ..................................................................................................... 121 Figure 5-6: Complementary ROC of energy detection under AWGN ................................................. 123 Figure 5-7: Illustration of time slot structure in CR networks ............................................................ 124 Figure 5-8: Average waiting time vs. arrival rate ................................................................................ 129 Figure 5-9: Throughput comparison under different Pmd ................................................................. 132 Figure 5-10: Throughput vs. SNR with fixed Pmd (Pmd = 0.5) ........................................................... 133 Figure 5-11: Average system delay under different primary arrival rate ........................................... 134 Figure 5-12: Throughput vs. different arrival rate .............................................................................. 135 Figure 5-13: Average system delay vs. arrival rate for M/D/1 queuing model .................................. 136 IX