b may; , . ..‘.._‘h_' “w .— ' “L. [In .L'wm' 1157 an a a. .. . r" .‘:.r 11;! f-(w .zg ' a “SIS >005 LIBRARY MIChinnn Qtate University This is to certify that the dissertation entitled SECURE COMMUNICATION SYSTEM DESIGN FOR WIRELESS NE'IWORKS presented by QI LING has been accepted towards fulfillment of the requirements for the Doctoral degree in Electrical and Computer Engineerigq Major Professor's Signature 12/07/ 2007 Date MSU is an affinnative-action, equal-opportunity employer PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 6/07 p:/ClRC/DateDue.indd-p.1 SECURE COMMUNICATION SYSTEM DESIGN FOR WIRELESS NETWORKS By Qi Ling A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Electrical and Computer Engineering 2007 ABSTRACT SECURE COMMUNICATION SYSTEM DESIGN FOR WIRELESS NETWORKS By Qi Ling Due to lack of a protective physical boundary, wireless communication is fragile to hostile jamming, detection and interception. Security becomes the key enabler for wireless networks now and in the future. Motivated by the observation that patching or add-on security is inadequate for addressing the needs on wireless security and can greatly complicate communication systems, in this dissertation, we focus on the fun- damental study of developing spectrally efficient wireless system with built-in security. First, we investigate the modeling and detection of hostile jamming in wireless com- munications. Hostile jamming, in which the jammer deliberately saturates the receiver with noise or false information, is one of the most commonly used techniques for limit- ing the effectiveness of an opponent’s communications. Unlike existing jamming mod- els that assume the jamming remains invariant during the signal transmission period, we propose a two-dimensional jamming generation model to characterize time-varying jamming phenomenons, and establish a novel jamming classification framework. In- cluding all the existing jamming models as special cases, the new framework provides a broader horizon for systematic jamming modeling, jamming pattern recognition and adaptive transmitter design for optimum jamming resistance. New jamming detection methods are developed for both frequency hopping and DS-CDMA systems. Equaliza- tion and / or interference cancellation techniques are exploited to mitigate self-jamming and thus improve the accuracy of hostile jamming detection. Next, we break new ground on spectrally-efficient anti-jamming system design. Mainly limited by multiuser interference, today’s jamming resistant systems suffer from low spectral efficiency. In this research, first, we propose an innovative message- driven frequency hopping (MDFH) scheme, in which a large portion of information is embedded into the hopping frequency selection process and transmitted with no extra cost on bandwidth or power, leading to the significantly improved spectral efficiency. MDFH also reinforces information confidentiality since the hopping pattern is totally unpredictable. Secondly, we introduce the concept of collision-free frequency hopping (CFFH) from a cross-layer perspective. The CFFH scheme is developed based on the OFDM framework and the ABS-controlled secure subcarrier assignment algorithm. While maintaining the inherent anti-jamming security feature, the proposed CFFH system can achieve high information capacity through collision-free multiple access. Finally, we consider physical (PHY) layer built-in security enhancement for wireless systems. Generally, the PHY layer alone does not possess built-in security features except for spread spectrum systems. The inherent security provided by the exist- ing spread spectrum systems is far from adequate and acceptable in wireless data communications. In this research, we propose to strengthen the PHY layer built-in in- formation privacy by integrating cryptography techniques into the wireless transceiver design, and formulate a joint PHY layer and upper layer privacy protection mechanism. The proposed approaches are based on both cryptographic techniques and inherent ambiguity in signal detection over multiple access wireless channels. It turns out that PHY layer built-in security can introduce significant gains over the traditional iso- lated privacy protection. In fact, since complex signal detection/ extraction processes must be performed first before decryption in every attack, the built-in security makes information recovery much more formidable to a malicious user. Copyright © by Qi Ling 2007 Dedicated to my family ACKNOWLEDGMENTS I would like to take this opportunity to express my appreciation to my advisor, Dr. Tongtong Li, for her constant support, guidance and encouragement throughout the past four and half years. She makes her best endeavors to help me in every aspect, from providing advice on research to personal development and growth. I want to thank Dr. Richard Enbody from Department of Computer Science and Engineering, and Dr. Jian Ren and Dr. Ning Xi from Department of Electrical and Computer Engineering for serving on my committee. I am deeply indebted to them for their kind support, either in the classroom or in all thoughtful correspondences. I would also like to thank Dr. Zhi Ding from Department of Electrical and Computer Engineering, University of California, Davis, for his recommendation of graduate study at Michigan State University and valuable help in research. I am grateful to all my friends who have made my life at Michigan State University an enjoyable experience. I would like to extend my heartfelt thanks to Yong Ding, Yun Liu, Zhenwen Peng, Qionghua Qiang, Yingying Shi, Feng Wei, Channa Zhang and Miaomiao Zhang for being my great friends and for all the fun we have together. I would also like to send a special thank you to my lab mates Dr. Weiguo Liang, Mr. Leonard Lightfoot and Dr. Huahui Wang, for the valuable discussions on research and for the advice on the daily life in the United Statas. Last, but not the least, I would like to thank my parents, my sister, my grand- parents, my aunts and uncles for their love and continuous support. A special thanks goes to my friends, Kai Hu, Lei Zhu and Fanglei Zhuang, who always care for me as brothers and sisters and have given me good suggestions and ceaseless encouragement. vi TABLE OF CONTENTS LIST OF TABLES x LIST OF FIGURES xi 1 Introduction 1 1.1 Security in Wireless Communications ................... 1 1.2 Limitations with Existing Security Solutions ............... 2 1.2.1 Lack of PHY Layer Security .................... 2 1.2.2 Pure Signal Processing Based PHY Layer Security Techniques . 3 1.2.3 PHY Layer Security in Spread Spectrum Systems ........ 5 1.2.4 Summary of Major Limitations .................. 7 1.3 Proposed Research Directions ....................... 8 1.3.1 Resilient Time-Variant Jamming Modeling and Detection . . . . 8 1.3.2 Spectrally Efficient Anti-Jamming System Design ........ 9 1.3.3 PHY-Driven Built-in Security Enhancement ........... 10 1.4 Overview of the Dissertation ........................ 10 2 Modeling and Detection of Hostile Jamming in Spread Spectrum Systems 14 2.1 Introduction ................................. 15 2.2 A General Jamming Generation Model .................. 18 2.3 Jamming Model for Frequency Hopping Systems ............. 20 2.4 Jamming Model for DS-CDMA Systems ................. 23 2.4.1 Single-User Systems ........................ 23 2.4.2 Multi-User Systems ......................... 25 2.5 Classification of Jamming Models ..................... 28 2.5.1 Jamming Classification Based on the Conventional Jamming Models ................................ 28 2.5.2 Jamming Classification Based on the Time-Variant Jamming Generation Model .......................... 31 2.6 Detection of Hostile Jamming ....................... 35 2.6.1 Jamming Detection in Frequency Hopping Systems ....... 35 2.6.2 Jamming Detection in DS—CDMA Systems ............ 39 2.7 Simulation Results ............................. 40 2.7.1 Examplas on Jamming Detection ................. 40 2.7.2 Examples on Jamming Classification ............... 42 2.8 Summary .................................. 45 vii 3 Spectrally Efficient Anti-Jamming System Design for Wireless Net- works 46 3.1 Introduction ................................. 47 3.2 Challenges in the Transceiver Design of Frequency Hopping Systems . . 50 3.3 Message-Driven Frequency Hopping .................... 52 3.3.1 Tfansmitter Design ......................... 52 3.3.2 Receiver Design ........................... 55 3.3.3 Efficiency Enhanced MDFH .................... 58 3.3.4 Collision-Free MDF H in Multiple Access Environment ..... 61 3.3.5 Bit-Error—Rate Analysis ...................... 66 3.3.6 Spectral Efficiency Analysis .................... 75 3.4 Collision-Free Frequency Hopping ..................... 83 3.4.1 Signal 'Itansmission and Detection ................ 83 3.4.2 Secure Subcarrier Assignment Algorithm ............. 87 3.4.3 Performance Analysis in the Presence of Fixed-Band Jamming . 90 3.4.4 Simulation Examples ........................ 92 3.5 Summary .................................. 95 4 PHY Layer Built-in Security Analysis and Enhancement Algorithms 97 4.1 Introduction ................................. 98 4.2 System Description ............................. 100 4.3 Physical Layer Built-in Security Evaluation for 18—95 and 3GPP UMTS CDMA Systems ............................... 102 4.3.1 Recovery of the Long Code Sequences in IS-95 Systems ..... 102 4.3.2 Recovery of the Long Code Sequences in 3GPP UMT S Systems 105 4.3.3 Recovery of the Desired Information ............... 107 4.4 Confidentiality Enhancement through Secure Scrambling and Secure Interleaving ................................. 108 4.4.1 Security Scrambling Based on AES ................ 109 4.4.2 Relationship between Scrambling and Interleaving ........ 111 4.4.3 System Model for DS-CDMA Systems with Chip-Level Inter- leaving ................................ 112 4.4.4 Secure Block Interleaving Based on AES ............. 114 4.5 Security Analysis of the Proposed Scrambling and Interleaving Processesll7 4.5.1 Security Based on the Large Key Space .............. 117 4.5.2 Security Based on the Inherent Ambiguity in Signal Detection . 119 4.6 Performance Analysis of CDMA Systems with Security Enhancement Strategies .................................. 123 4.6.1 Computational Complexity ..................... 124 4.6.2 System Performance with Secure Scrambling and Further Im- provement Using Separately Scrambled Training Sequence . . . 125 viii 4.6.3 Performance Improvement Using Secure Interleaving ...... 129 4.7 Discussions and Extension to Other Wireless Systems .......... 134 4.8 Summary .................................. 137 5 Conclusions and Future Work 138 5.1 Conclusions ................................. 138 5.2 Related Future Work ............................ 141 APPENDICES 143 A List of Abbreviations and Acronyms 144 BIBLIOGRAPHY 147 2.1 3.1 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 LIST OF TABLES Classification confusion matrices: JSR = 4dB, SNR = 3dB. ............................... 43 Comparison of information bit rate between the conventional fast F H system and the proposed E—MDF H scheme for various hop rates: Nc= 64 (Be = 6), 33 = 4, 39 = 2. .................................................................................................. 82 Complexity of training-based channel estimation methods. .............................. 120 Complexity of commonly used symbol detection methods. .............................. 120 Complexity evaluation of signal detection and source data decryption in the single-user case. ....................................................................................... 121 Computational complexity of two iterative multiuser receivers. ....................... 122 Complexity evaluation of signal detection in the multi-user case. .................... 122 Maximum complexity of recovering all four users’ information. ..................... 123 Complexity comparison of two generation methods of long scrambling sequences and one generation method of secure block interleaver. .................. 125 Settings of the DS-CDMA system and the channel model in the simulation. 127 2.1 2.2 2.3 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 LIST OF FIGURES Flow diagram of classifying the traditional jamming models. ............................ 29 Probability of miss versus J SR (here the probability of false alarm z 0.04). 41 Probability of error in estimating pf versus J SR. ................................................. 44 Block diagram of the conventional frequency hopping scheme. ......................... 51 The nth block of the information data .................................................................. 53 Transmitter structure of MDF H. .......................................................................... 54 Receiver structure of MDF H, here ABS means taking the absolute value .......... 56 Probability of collision (Ph) versus the number of users (starting at the two-user case) for Nc = 64. ................................................................................................ 62 Block-wise user multiplexer and de-multiplexer, designed to process one data block of length L consisting of bits from Nu users Here b'j denotes the ith bit of user j in the block. ........................................................................................... 64 Infrastructure of the TD-MDF H scheme. ............................................................ 65 BER comparison of the carrier bits and the ordinary bits in E-MDF H: M, = 3, Nc=64(Bc=6),Bs=4,Bg=2. .......................................................................... 74 BER comparison of the conventional F H and the proposed E-MDF H in the single-user case: N0 = 64 (BC = 6), 83 = 4, 89 = 0. ............................................. 77 BER comparison of the carrier bits and the ordinary bits in E-MDF H: M, = 3, Nc=64(Bc=6),Bs=4,Bg=0. ......................................................................... 78 Performance comparison of E-MDF H and conventional F H in the multiuser case:Nh=5,Nc=64(Bc=6),Bs=4,Bg=2. ................................................... 82 BER comparison of CF F H and conventional F HMA system over AWGN channels: Nc = 128, Nu = 8 ............................................................................ . ....... 93 xi 3.13 BER comparison for three systems under hostile jamming: N0 = 256, Nu = 16, 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 SNR = 7dB. .......................................................................................................... 95 Block diagram of a long code DS-CDMA system ............................................. 101 Long code generator in IS-95 systems. .............................................................. 103 Scrambling sequence generator in 3GPP UMTS systems. ............................... 106 Design of physical layer secure scrambling in DS-CDMA systems. ................ 110 Block diagram of a DS-CDMA system with chip-level interleaving. ............... 113 Design flowchart of secure block interleaving. ................................................. 117 BER comparison of conventional scrambling and secure scrambling. Results from Rake receiver with no channel coding, four-ray multipath channel, pro- cessing gain N = 16, number of user Nu = 4. .................................................. 128 BER versus SNR, performance comparison over deep fading channel, proce- ssing gain N = 16, number of users Nu = 8. ................................................... 130 BER versus system load, performance comparison over deep fading channel, processing gain N = 16, SNR = 20dB. ............................................................... 131 4.10 BER versus SNR, performance comparison over channel with strong burst noise, processing gain N = 16, number of users Nu = 8. ................................ 132 4.11 BER versus system load, performance comparison over channel with strong burst noise, processing gain N = 16, SNR = 20dB. ........................................... 133 4.12 Conventional turbo encoder and secure turbo encoder. ..................................... 135 4.13 BER comparison of the proposed secure turbo coding and the conventional turbo coding. ...................................................................................................... 136 “Images in this dissertation are presented in color” xii CHAPTER 1 Introduction 1.1 Security in Wireless Communications Wireless technology offers ease of accessibility, and enables freedom of mobility for users by releasing the constraint of physical connections to networks. Over the last few decades, wireless communication has exhibited explosive growth as an efficient transmission mechanism for voice, video and data services. In civilian communica- tions, it is estimated that the number of wireless subscribers worldwide will reach 2.3 billion by 2009 [1]. In military communications, more than 98% of information transmission relies on wireless networks [2]. As people are relying more and more on wireless networks for critical information exchange in personal, industrial and military applications, the near ubiquitous wireless interconnectivity has given openings for ma- licious agents to exploit vulnerabilities on a widespread basis, such as wireless mobile Internet and e—commerce [3]. Due to lack of a protective physical boundary, wireless communications are much more vulnerable than their wireline counterparts. As data is being transmitted through the airlink, wireless transmissions are subjected to hostile jamming and interference. In addition, inherent broadcast nature of wireless communications results in potential interception and eavesdropping, since information intended to be received only by authorized users can actually be intercepted by any suitable RF equipments within the radio range. Phrthermore, the mobility and portability of wireless devices make them prone to losses and theft. All these factors cause serious and urgent security threats in wireless networks. The future of wireless communications depends on our ability to strengthen security and provide a reliable information exchange platform. Patching or add-on security may be effective in the short run, but is far from adequate for addressing the needs on wireless security and can greatly complicate wireless communication systems. Driven by the ever-increasing demand on secure wireless networking, novel wireless systems with built-in security have become the next development impetus in communications. 1.2 Limitations with Existing Security Solutions 1.2.1 Lack of PHY Layer Security Although security has emerged as an important issue in the design and develOpment of wireless networks, most of research attention has been concentrated on the higher layers of the OSI model rather than the PHY layer. Take privacy protection as an example. Privacy protection is the security service that ensures the confidentiality of the user data and control signals, for authorized users in a protected network. The most effective technique to achieve data privacy and information confidentiality is encryption. Encryption is a mechanism by which a message (i.e., plaintext) is combined with secret information (i.e., key) to generate a text (i.e., ciphertext) that cannot be recovered without the knowledge of the secret information. So far, source data encryption is the most widely used technique to ensure information confidentiality. In today’s wireless systems, privacy protection is primarily performed at upper lay- ers, independent of the physical layer characteristics. This implies that data encryp- tion and decryption are not assisted by, and considered in, physical layer transmitter- receiver designs. The major limitation with such an isolated privacy protection scheme is: Without the cooperation of a PHY layer enabled with built-in security, eavesdrop- pers can receive the encrypted message accurately. This potentially makes adversaries’ job easier as the only barrier to obtaining the original information is the need for cor- rect decryption, which is not too difficult when taking the weakness of some existing encryption algorithms into account. For example, several research groups [4—6] have reported some security holes and demonstrated to easily crack the 40-bit/128-bit WEP (Wired Equivalent Privacy) [7] because of the relatively weak encryption algorithm it uses. The fact is, the PHY layer of a communication system, in general, does not possess security features. However, all the information transmission eventually takes place in the PHY layer. Without a inherently secure PHY layer, wireless signals are fragile to hostile jamming, information detection and interception. 1.2.2 Pure Signal Processing Based PHY Layer Security Techniques With advances in array signal processing, some power-based and channel-based ap- proaches have been proposed to strengthen PHY layer security by exploiting pure signal processing techniques. Power-Based Approaches The adoption of smart or adaptive antenna arrays has been introduced as a promising technology to increase the capacity and improve the performance [8—12]. Compared to the traditional omnidirectional antenna, the smart directional antenna can be used to physically keep intruder away from the legal user’s propagation range to avoid the intentional interception. Some smart antennas can even provide a steerable beam to detect and distinguish the real signal and unwanted signal, and produce the sectored beam to the desired users and depress unwanted signals. The enhancement of information assurance in wireless networks can also be achieved through the use of adaptive antennas in conjunction with power control [13,14]. Even with all the benefits of smart antennas, power-based security techniques have three problems. First, it is only an ideal case that the unauthorized user has null- receiving energy by simply deploying a directional antenna. There always exists some amount of energy leaking to the adversary, leading to a chance that the unauthorized user with powerful reception equipments can extract full/ part of useful information. Second, smart antennas in general require heavy computation for eliminating inter- ference, tracking source locations and synthesizing patterns. Many of these systems are thus limited by the speeds of analog-to-digital (A / D) converters or the complexity of the applied algorithms in the digital signal processing (DSP) domain. Third, the physical size of smart antennas is generally too large to fit into mobile devices and portable equipments. Channel-Based Approaches Methods in this class aim to achieve information security by utilizing the wireless medium to either convey a confidential message or generate a secret key. Some transmission schemes have been designed by properly exploiting the channel between the transmitter and desired receiver, while the eaves- drOpper expects to experience considerable diversity loss based on the assumption any potential transmitter-eavesdropper channel will have totally different channel state in- formation (CSI) [15—17]. As the channel condition matching to the true demodulator is required at the receiver side, the secure access on physical layer is realized [18—21]. It is also shown that a secret key can be generated from the natural environment of communication channels, i.e., the multi-path fading of a radio wave [22,23]. The reciprocity in wave propagation is utilized to provide a secret key agreement scheme without intractable key management and key distribution processes. However, the reciprocity of channels between the transmitter and the authorized user generally cannot be guaranteed in practical systems, since wireless medium itself is tirnevarying and unreliable. Moreover, the adversary can actively approach the authorized user, resulting in that the assumption that their transmissions are over different channels becomes invalid. Even if their channels are completely different, the unauthorized user may use blind estimation and equalization [24—32] to estimate channels and recover the original message subsequently, which makes many channel- based approaches lose secrecy. 1.2.3 PHY Layer Security in Spread Spectrum Systems Generally, the PHY layer alone does not possess built-in security features except for spread spectrum systems. Historically developed for secure communication and mili- tary use, spread spectrum techniques, including direct-sequence code division multiple access (DS-CDMA) and frequency hopping (FH), are new major modulation and mul- tiple access techniques in broadband cellular networks and WLAN communications. Not only does spectral spreading force the interceptor to monitor an expanded frequency band, it also enables anti-jamming capability and location privacy [33,34]. Although spread spectrum systems are resistant to narrow-band jamming, in reality, other jamming attacks can be used to compromise legal users’ communication and the jammer may very likely switch frequently from one pattern to another to improve its effectiveness. It is thus crucial to study the essential characteristics of commonly used hostile jamming attacks in spread spectrum systems and develop jamming classifica- tion methods, so that the appropriate anti-jamming procedures can be applied in an active, adaptive manner. The inherent privacy potential of the DS-CDMA systems is based on the assump- tion that unintended receivers do not know the initial state used to generate the pseudo-random (PN) spreading sequence. Specifically, desired receivers use the initial seed to reconstruct, via a linear feedback shift register (LFSR), the spreading PN sequence. Unintended counterparts without the knowledge of the initial seed face a composite detection problem, whereby the unknown spreading sequence lies within an enormous set of valid choices. However, the seed of conventional binary-valued PN spreading sequences from known LFSRs can be consistently estimated based on noisy observations. Indeed, simple suboptimal estimators of the initial state of the LF SR can correctly identify the seed with very high probability based on just a fraction of the sequence period, even at very low chip power-to-noise ratios [35,36]. For FH systems, the inherent security relies on the difficulty to follow the desired user’s transmitting frequency without the knowledge of the hopping pattern. Al- though frequency hopping is designed to minimize the probability of the unauthorized interception of telecommunications, the conventional FH systems suffer from low spec- tral efl‘iciency over large bandwidth. Typically, FH systems require large bandwidth, which is proportional to the product of the hopping rate and the total number of all the available channels. In multiple access environment, collisions, caused by in- dependent hops among different users, affect the system performance and reduce the spectral efficiency drastically. In the literature, considerable efforts have been devoted to increasing the spectral efficiency of PH systems by applying high-dimensional mod- ulation schemes [37—43]. However, existing work is far from adequate to address the enormously increased demand on inherently secure high speed wireless communication. 1.2.4 Summary of Major Limitations 0 Without a secure PHY layer, wireless communication is fragile to lower layer attacks. An unprotected PHY layer enables the adversaries to perform traffic analysis / modification attacks and lowers the barrier to theft of user and network information. 0 Strengthening the PHY layer security through pure signal processing techniques is an interesting research direction. However, some important issues go against their prevalence: High computational complexity and additional hardware cost severely restrict the practical application of power-based approaches; Channel- based approaches depend on some strong, unrealistic assumptions on channel state information, which can easily be violated in practical situations. 0 The existing spread spectrum systems can provide a near—satisfactory PHY layer built-in security solution to voice—centric wireless communication, consisting gen- erally of very short episodes. Nevertheless, the security provided by these sys- tems is far from adequate and acceptable in wireless data communications. At the same time, driven by the ever increasing demand on high speed multimedia services, existing systems are also challenged to improve their spectral efficiency to support higher data rate without increasing the bandwidth. 1.3 Proposed Research Directions This dissertation is focused on the fundamental study of developing spectrally efficient and inherently secure wireless air interface by integrating advanced signal processing techniques and cryptographic techniques into the PHY layer transceiver design. Multi- layer approaches are also investigated for secure information transmission in multiple access environment. More specifically, the proposed research directions are briefly summarized in the following subsections. 1.3.1 Resilient Time-Variant Jamming Modeling and Detec- tion In wireless networks, one of the most commonly used techniques for limiting the ef- fectiveness of an opponent’s communication is referred to as jamming, in which the authorized user’s signal is deliberately interfered by the malicious user(s). Currently, jamming signals are classified into four groups: full-band jamming [44,45], partial-band jamming [46—48], tone jamming [49—51] and partial-time jamming [52—54]. Existing work on jamming detection and jamming prevention has generally been focused on a particular type of jamming, in which the jamming pattern is assumed to be known and invariant during the signal transmission period [51, 55—62]. However, in practical scenarios, hostile jamming can be dynamic and time variant. To the best of our knowl- edge, little attention has been paid to time-varying jamming modeling and jamming detection. In this dissertation, we will study time-variant hostile jamming through the follow- ing thrusts: (i)Introduce a general, two-dimensional (2D) jamming generation model to characterize the time-varying jamming phenomenons; (ii) Establish a systematic jamming classification framework based on the 2D model. The new framework will in- clude all the existing jamming models as special cases. Statistics that characterize the average jamming lasting time and bandwidth will be introduced, to help achieve dy- namic transmitter adjustment for optimum jamming resistance. (iii) Distinct hostile jamming from self-jamming (which is caused by multipath propagation and multiuser interference), and increase the accuracy of hostile jamming detection by exploiting self-jamming mitigation techniques. 1.3.2 Spectrally Efficient Anti-Jamming System Design Existing jamming resistant systems, including DS-CDMA systems and FH systems, rely heavily on rich time-frequency diversity over large spread spectrum [63, 64]. Mainly limited by multiuser interference (caused by multipath propagation and asyn- chronization in DS-CDMA systems and by collision effects in FH systems), the spectral efficiency of existing jamming resistant systems are very low due to inefficient use of the large bandwidth. While these systems work reasonably well for voice centric commu- nications which only requires relatively narrow bandwidth, their low spectral efficiency can no longer provide sufficient capacity for today’s high speed multimedia wireless services. This turns out to be the most significant obstacle in planting anti-jamming features to high speed wireless communication systems, for which spectrum is one of the most precious resources. The major challenge here is: How to design wireless sys- tems which are highly efficient but at the same time have excellent jamming resistance features? ' In this dissertation, we aim to: (i) Incorporate advanced signal processing tech- niques and cryptographic algorithms into transmitter innovation; (ii) Integrate anti- jamming design into highly efficient communication systems (such as OF DM) through a network-centric perspective. More specifically, we will introduce the concepts of message-driven frequency hopping and collision-free frequency hopping. 1.3.3 PHY-Driven Built-in Security Enhancement As mentioned earlier, the PHY layer of most wireless systems (such as OFDM [65], GSM [66]) does not possess built-in security features. However, all the information exchange activities eventually have to take place in the PHY layer. Without the cooperation of a PHY layer enabled with built-in security, wireless signals are fragile to hostile jamming, detection and interception. This lowers the barrier to PHY layer attacks on user and network information, and also leads to inefficient transmission. In this dissertation, by exploiting cryptographic encryption and inherent ambiguity in signal detection over multiple access channels, we plan to enhance the PHY layer built-in information confidentiality by integrating cryptography techniques into the transceiver design, and formulate a joint PHY layer and upper layer privacy protec- tion mechanism. In essence, with the same computational complexity for the autho- rized parties, the built-in security makes information recovery much more formidable to a malicious user, since in every attack, complex (if at all possible) signal detec- tion/extraction processes must be performed first before decryption. We will start with DS-CDMA, and then explore the establishment of PHY-layer built-in security in general wireless systems. 1.4 Overview of the Dissertation In the dissertation, we aim to address the following specific problems: 0 How to characterize time-varying jamming phenomenons and classify jamming 10 patterns efficiently? o How to improve the spectral efficiency of the conventional F H systems, while maintaining the anti-jamming security feature? 0 How to enhance the physical layer built-in security in wireless communications? The dissertation is structured as follows. Chapter II explores the time-varying jamming modeling and classification in wire- less communications. First, a general, two-dimensional jamming generation model is introduced to characterize time-varying jamming phenomenons, including all the ex- isting jamming models as special cases. The model is then studied closely and refined for spread spectrum systems, including both FH and DS-CDMA systems. According to our observation that self-jamming can be caused by multipath propagation and multiple access interference, we propose to study the difference between self-jamming and hostile-jamming. Taking DS-CDMA as the underlying communication system, self-jamming mitigation is discussed by exploiting interference cancellation methods. This is particularly important in improving the accuracy of hostile jamming detec- tion in multiple access wireless environment. Novel jamming classification frameworks based on the time-varying jamming model are established, providing a broader hori- zon for systematic jamming modeling and jamming pattern recognition. By means of the statistical hypothesis test and the measurement/ calculation of power spectral density (PSD) of the received signal, training-based and blind jamming detection ap- proaches are developed. Finally, simulation examples are provided to demonstrate the effectiveness of the proposed approaches. Chapter III presents two spectrally efficient secure communication interfaces: message-driven frequency hopping (MDFH) and collision-free frequency hopping 11 (CF F H). In MDFH, part of the message stream will be acting as the the PN sequence for hopping frequency selection, leading to the significantly improved spectral effi- ciency. Through blind detection of carrier frequencies, the MDFH scheme can resolve the synchronization limitation suffered by the conventional FH systems. From the security point of view, information confidentiality is also reinforced since the hopping pattern is message-driven, hence totally unpredictable. To make full use of the avail- able spectrum in multiple access environment and further improve design flexibility, a highly bandwidth-efficient CFFH scheme is proposed. Based on the OFDM framework and the secure subcarrier assignment algorithm, the OFF H system can achieve high information capacity through collision-free multiple access, and can successfully relax the strict synchronization requirement. At the same time, as each user still transmits through a pseudo-random frequency hopping scheme, CFFH can maintain the inher- ent anti-jamming, anti-interception security features of the conventional FH system. The proposed schemes can be used for both civilian and military applications where secure high speed information transmission is needed. Chapter IV exploits encryption based protection mechanism to strengthen the physical layer security in DS—CDMA systems and investigates possible extension to general wireless systems. First, security weakness of the Operational and proposed CDMA airlink interfaces is analyzed. It is proved that the maximum complexity to recover the long code sequence is only 0(242), which implies that the built-in infor- mation privacy provided by these systems is fairly unsatisfactory. Secondly, instead of using the conventional scrambling method, encrypted long code based on AES (advanced encryption standard) is proposed to enhance the security of DS-CDMA systems. Thirdly, motivated by the fact that chips spread from one symbol still clus- ter together after scrambling and are fragile to deep fading and / or strong burst errors, 12 chip-level secure interleaving is introduced as a substitution of securing scrambling to improve the system performance. Performance analysis demonstrates that infor- mation privacy can be significantly improved by integrating cryptographic techniques into the scrambling and / or interleaving process. Simulation examples are presented to illustrate the robustness of DS-CDMA systems with secure interleaving in adverse environments. Furthermore, both secure scrambling and secure interleaving can be ex- tended to wireless systems other than DS-CDMA in multiple ways. As a start point, secure interleaving is integrated with the commonly deployed F EC (forward error con- trol) process so that strong information confidentiality can be achieved through secure channel coding. The simplicity and effectiveness of the proposed schemes make them particularly attractive for 3G systems and beyond. Chapter V summarizes the contributions and conclusions of the dissertation. An outline of related future work is also provided. 13 CHAPTER 2 Modeling and Detection of Hostile Jamming in Spread Spectrum Systems In this chapter, a general, two-dimensional jamming generation model is presented to characterize jamming signals from both the time domain and the frequency domain. The model is studied closely and refined for spread spectrum systems, including both frequency hopping and direct-sequence CDMA systems. Self-jamming mitigation is investigated to increase the accuracy of hostile jamming detection by exploiting inter- ference cancellation techniques. Novel jamming classification frameworks are estab- lished to provide a broader horizon for systematic jamming modeling and jamming pattern recognition. By means of the statistical hypothesis test and the measure- ment/ calculation of power spectral density of the received signal, jamming detection approaches are deveIOped. Simulation examples are provided to demonstrate the ef- fectiveness of the proposed approaches. 14 2. 1 Introduction The fast computational speed improvement, rapid receiver technology advance and price declination facilitate the malicious attackers with an easy access to the wireless communication channels in the air. One of the most commonly used techniques for limiting the effectiveness of an opponent’s communications is referred to as jamming. Generally, intentional jamming, also known as hostile jamming, intends to disable the legitimate transmission by saturating the receiver with noise or false information through deliberate radiation of radio signals, and thus significantly decreasing the signal-to—interference—plus—noise ratio (SINR). 'Ifaditionally, hostile jamming has been characterized from either the frequency domain or the time domain: (i) Tone-jamming [49—51], where the jamming power is concentrated around carrier frequencies; (ii) Band-jamming [44—48], in which the jamming signal is modeled as a zero-mean wide sense stationary Gaussian random process. In general, band-jamming is further classified into full-band [44,45], partial- band [46—48]. The power of full-band jamming is uniformly distributed over the band- width of interest with PSD N J. Partial-band jamming is characterized by the additive Gaussian noise interference with PSD flp-l over a fraction p of the total bandwidth and negligible interference over the remaining fraction (1 — p) of the band; (iii) Partial-time jamming [52—54], where the jamming occurs at certain time periods during the signal transmission. It is basically a two-state Markov process. When the jammer is in state 0, it is off; when it is in state 1, the jammer emits the interfering signal. State 1 occurs with probability of p, along with the variance of jamming signals 97/01. (1 —- p) is the probability of occurrence of state 0, for which the variance of jamming signals is 0. A considerable amount of work, see [51, 55—57, 59—62] for example, has been ded- icated to the evaluation of the performance for a particular anti-jamming algorithm, 15 while little attention has been focused on the detection of hostile jamming. In fact, dis- covering jamming attacks is crucial because it is the first step towards building a secure and dependable wireless network. Efficient detection of hostile jamming makes it pos- sible for the transmitter to implement a dynamic anti-jamming transmission scheme, and hence plays a key role in jamming prevention. However, the existing jamming detection methods are far from satisfactory. In virtue of powerful error-control coding (e.g., turbo codes), the maximum a posteriori (MAP) decoding algorithm was utilized to estimate the jammer’s state by calculating the probability of a particular received symbol being jammed during its transmission [58,67]. However, the computational complexity, mainly existing in two MAP algorithms running iteratively at the receiver, is prohibitively high. In [68], a hypothesis test was established with null hypothesis stating that the data channel was affected only by background thermal noise leading to a “small” channel error rate and the alternative hypothesis asserting that the data channel was being jammed with a “large” crossover probability. Basically, it is equiv- alent to measure the bit error rate (BER) of the normal traffic or jammed channel and then set a specific threshold for the BER, while completely ignoring the distinct characteristics of jamming signals with different underlying models. Moreover, existing work on jamming suppression and jamming prevention is gen- erally targeted at a particular jamming model at a time. That is, the jamming pat- tern is assumed to be known and invariant during the signal transmission period, see [51, 55—62] for example. In practice, however, in order to deliberately malfunction the anti-jamming algorithms, the jammer may very likely switch frequently from one pattern to another, with each jamming pattern only lasting a short period of time. In other words, hostile jamming can be dynamic and time—variant. Time-varying jam- ming modeling, classification and dynamic jamming detection, therefore, are highly 16 desirable in the sense that the transmitter can be adjusted adaptively to combat time- variant hostile jamming. To this end, we investigate the modeling and detection of hostile jamming in wire- less communications. First, a general 2D jamming generation model is presented to characterize the more realistic time-varying jamming phenomenons. Using such a model is advantageous to analyze the essential characteristics of commonly used jam- ming models, including the similarity and difference between different models. We extract discrimination features for the traditional jamming patterns and develop a binary decision tree for the purpose of identification. Next, a novel jamming classifi- cation framework is established based on the time-varying jamming model. Motivated by the results on time-varying channel modeling, we analyze the coherence time (the time period over which the jamming remains unchanged) and coherence bandwidth (the frequency range over which the jamming power spectrum is approximately flat) of the jamming generation system, and introduce the concepts of fast jamming, slow jamming, fiat jamming and frequency-selective jamming. Including all the existing jamming models as special cases, this new framework provides a broader horizon for systematic jamming modeling and jamming pattern recognition. Finally, based on our observation that self-jamming can be caused by multipath propagation and mul- tiple access interference, we propose to study the difference between self-jamming and hostile-jamming. Taking CDMA as the underlying communication system, self- jamming mitigation is investigated by exploiting interference cancellation methods. This is particularly important in improving the accuracy of hostile jamming detection in multiple access wireless environment. The rest of the chapter is organized as follows: In Section 2.2, we introduce a general, two—dimensional jamming model. In Section 2.3, the model is studied closely 17 and refined for frequency hopping systems. In Section 2.4, the well-known “self- jamming” in both uplink and downlink CDMA is investiaged, and interference cancel- lation techniques are presented to enhance the discrimination of hostile jamming. In Section 2.5, two jamming classification frameworks are proposed based on the conven- tional and proposed jamming models, respectively. In Section 2.6, jamming detection methods are developed by means of the statistical hypothesis test and the measure- ment / calculation of power spectral density of the received signal. Simulation examples are provided in Section 2.7 and we conclude in Section 2.8. 2.2 A General Jamming Generation Model Motivated by the fact that jamming signals may be time-variant, we propose to char- acterize hostile jamming in wireless systems through a more general and systematic model. We begin with a single-input-single-output AWGN channel. Let s(t) be the transmitted signal, then the received signal can be written as: r(t) = s(t) + n(t) + J(t), (2.1) where n(t) is the white Gaussian noise, J (t) represents the intentional jamming signal. We model the jamming signal J (t) as the output of a time-varying jamming generating system represented by J(t) = 1:9“, T):r(t — 7')d7', (2.2) where s(t) is the input signal and g(t, T) is the time—variant channel response of the jamming system at instant t to an impulse applied at time t - 1'. Assume that g(t,r) is wide-sense stationary (WSS) with respect to 1'. Let 18 Rg(t, Ar) = E [g(t, T + Ar)g(t, 7)] be the time-varying correlation function of g(t, 1'). Define Sg(t, f) as the time-varying power spectral density of g(t, 1'), given by 00 Sg(t, f) = / Rg(t,AT)€_j21rAde(AT). (2.3) —00 Limited by the size and capability of the jamming generation device, the total jamming power is finite. Let P J be the average jamming power, that is, R, = E [1:sgu, f)de . (2.4) Over short periods of time, g(t,1') (as well as Sg(t, f )) may be approximately time-invariant. Taking this into consideration, it can be shown that this general model contains all the existing models as special cases. In fact, if g(t,r) = 9(7) is time-invariant, and x(t) = 6(t), then we have J(t) = g(t), and Sg(t, f) reduces to Sg(f)(= 5J(f))- Let [f0, f1] be the total available frequency band over which the message signal is transmitted, and [t0, t1] be the time duration of the message signal. Let x(t) = 6(t). e If Sg(t,f) = 71—136 2 NJ,Vf E [f0,f1],‘v’t E [t0,t1], then J(t) is traditional full- band jamming model as a white Gaussian process whose power spectral density is flat over the entire bandwidth. 0 If Sg(t,f) = PJd(f - fk),Vt E [t0,t1], where fk E [f0,f1], then J(t) is an ideal single-tone jamming with all the power accumulated on a particular frequency fk. Similar definitions can be extended to multi-tone jamming. More specifically, 590, f) = Z PJU, fk)5(f - fit): with Z PJU, fk) = PJ. (2-5) k=0 k=0 19 where P J(t, fk) stands for the jamming power allocated for the kth frequency component at time instance t, and 6 is the Dirac delta function. If Sg(t, f) is a rectangular pulse along the f-axis and not varying along the t-axis from to to t1, i.e., 0, Vf E lf0,fi)U(fj,f1I,Vt€ lthtll 731:5, = g; w e [f.-.f,-]. Vtelto.t11 390, f) = (2-5) where f,- and f_,- with f,- S fj are certain intermediate frequencies within [f0, f1], p f g éliggé implies the fraction of the bandwidth being jammed, then J (t) is a typical partial-band jamming during the time interval [t0, t1]. If Sg(t, f) is a rectangular pulse along the t-axis during to and t1 and invariant along the f-axis within [f0, f1], 5g“, f) = 0, VtElt0,tm)U(tn,t1llVf E [folfll (27) 71.1356ng = %, Vt e [tm,tnl,Vf E [fafll n — tm t where tm and tn with tm S tn are certain intermediate time instances within [t0, t1], pt 2 fl indicates the fraction of the time interval that the channel is jammed, then J (t) is a typical partial-time jamming signal. 2.3 Jamming Model for Frequency Hopping Sys- tems Assume that the transmitter is able to hop among NC available channels, each of which occupies a bandwidth of Bch. In order to maintain the orthogonality among 20 carriers, BC), needs to be an integer multiple of 71., where T is the symbol interval in slow frequency hopping (SFH) systems or the hopping duration in fast frequency hopping (FFH) systems. In general, we simply set BC}, = 71», in order to save the total bandwidth. Define a binary vector g 3 [a0, 01, , cut/6-1] for the transmitter. For i = 0, 1,. - - ,Nc — 1, a,- = 1 indicates the ith channel is currently used by the transmitter to convey information. Otherwise, the ith channel is idle if a,- = 0. Similarly, g g [50, 51, , fiNc— 1] is defined as the jamming index vector, where the jth entry flj = 1 implies that the jth channel is deliberately jammed, and 63- = 0 means that there is no intentional jamming on the jth channel, for j = 0, 1, - - - , NC — 1. For either SF H or F FH systems, the transmitter changes its desired traffic channels from one hop to another. In other words, g is actually a time-varying vector. On the other hand, the jammer can have its own jamming strategy, by choosing arbitrary g. Specifically, based on the particular choice of g, the jamming model can be generalized as follows: 0 If g = Q, where g is a constant binary vector, then the jamming is independent of time. It is referred to as fired-band jamming. Two special cases are g = Q and g = l, where Q is an all-zero vector and 1 is an all-one vector, corresponding to no jamming and full-band jamming, respectively. 0 If g is a function of time, then random jamming happens when E is randomly chosen during each hopping duration. In the worst case, smart jammers can be implemented as long as the condition that g = Q can always be satisfied. It essentially means the jammer can follow the frequency hop all the time. o If g is neither an all-zero nor an all-one vector at any time instance, it is generally 21 partial—band jamming (either fixed-band or random jamming). If g is an all- zero vector within each hopping duration except for certain time intervals, it is referred to as partial-time jamming. Suppose that the jammer changes its jamming index vector over time and spreads its available power equally over all the channels it intends to jam. We ameliorate the general white Gaussian model into a more sophisticated one with its time-varying power spectral density defined as follows: Nc—l 59c. f) = 733 2 new — f0 - chh). (2.8) j=0 where f0 is the initial frequency shift, flj(t) indicates the jamming index 0, at the time instance t, Nc—l 0, 1f 2: 18].“) _ 01 j: 73— : Nc—l 29 J NV,” . 1f ,2 ainaeo. ( ’ Z [Bj(t)Bch 1:0 J: 1, iff E [0, Belt), X(f) = (2-10) 0, else. 22 2.4 Jamming Model for DS-CDMA Systems 2.4.1 Single-User Systems We begin with the simple case where CDMA signals are sent over an AWGN channel. At the receiver end, it yields r(t) = d(t)p(t) + n(t) + J(t), 0 S t S T, (2.11) where d(t) is the information signal, p(t) is the signature wave, n(t) is the additive white Gaussian noise, J (t) is the jamming signal and T is the symbol period. The power spectral density of d(t) is approximately given by 5m = :r (Sig)? (2.12) Let s(t) é d(t)p(t) be the spreading signal. Since p(t) is the chip-level waveform at a rate of fc chips/second, by substituting 715 for T in (2.12), we can easily obtain the power spectral density of s(t), _ i sinvrf/fc 2 SS”) ’ fc( «m. ) ' (2'13) After despreading, we obtain IID 7‘(t)p(t) (2.14) = d(t) + n(t)p(t) + J(t)p(t), (2.15) 2(t) where J (t)p(t) represents the code-modulated jamming signal. 23 Two scenarios are considered: 1. If the jamming signal expands the whole channel bandwidth, then the code- modulated jamming signal will further spread the spectrum, thus can be ap- proximately modeled as white noise. On the other hand, the desired despread signal’s power is concentrated within [—71~, 71.] Hz. To extract d(t), we can pass z(t) through a lowpass filter with a cutoff frequency 71-. Hz. At the output of the lowpass filter, the desired signal’s power remains largely unchanged, while the jamming power is reduced by a fraction of ch. Therefore, the jamming-to-signal ratio (JSR) is decreased by ch. 2. If the jammer concentrates its available energy within the bandwidth associated with the original signal, for example, J (t) = Wflt E [0, T], where E J is the jamming energy and T is the symbol duration. In this case, the PSD of J (t) has the same form as that of Sd( f) in (2.12). Due to the frequency diversity in CDMA signals, a narrow-band interference elimination filter can be used to filter out the intentional jamming completely before despreading without seriously degrading the system performance. Beyond the AWGN channel, if the channel impulse response is modeled as L—l h(t) = Z h,6(t — d,), (2.16) l=0 where {hl}{’=_(')1 are complex attenuation coefficients and {d1}{’='(')1 are delays for L 24 different paths, then the received signal can be written as L—l r(t) = Z h)s(t — (1,) + n(t) + J(t) (2.17) (=0 L—l = hos(t) + Z h13(t— d1) + n(t) + J(t), (2.18) l=1 where do is assumed to be 0, without loss of generality. As can be seen, in addition to the noise n(t) and the jamming signal J (t), multipath propagation results in self-jamming, i.e., Lil hls(t — d1). Considering the well-known fact that threloriginal data is spread by pseudo-random sequences leading to a wideband signal of s(t), any delayed or scaled version of s(t) does not change the signal’s bandwidth, eventually resulting in the wideband characteristic of the self-jamming term. If J (t) only occupies a narrow frequency band with strong power within that band, the hostile jamming can easily be detected, since the other terms except J (t) on the right-hand side of (2.18) are all wideband signals with low power spectral density. That is, we are able to distinguish partial-band jamming from self-jamming, by simply taking samples over the entire bandwidth of the power spectral density of the received signal. 2.4.2 Multi—User Systems For multiple access DS-CDMA systems, in addition to inter-symbol interference within each user’s signal caused by frequency selective fading, self- jamming among authorized users occurs when the orthogonality of spreading codes among users is not maintained due to multipath prepagation or asynchronous transmission. 25 Uplink In DS-CDMA uplink, users are generally asynchronous. If the kth user’s channel is modeled as L—l = 2 him - at...) (2.19) (=0 where {hk,)}lL=—Ol are complex attenuation coefficients and {dk,l}1L=_01 are delays for L (the maximal channel order among all the multipath channels) different paths, then the received interference—free signal is given by 00 K— _ :2; 1:1,”; Id: W— dk 0PM - dk, z) (2.20) =0 (=0 m=—oo where dk(t) is the kth user’s transmitted signal, pk(t) is the kth user’s signature wave. Consequently, the received data in the presence of the additive noise and hostile jamming can be written as r(t) = s(t) + n(t) + J(t). (2.21) It is reasonable to assume that the base station has the knowledge of all users’ spread- ing codes. Once each uplink channel corresponding to one particular user is accurately estimated using high-power pilot symbols, the desired signal wave along with its de- layed and scaled versions, i.e., s(t), can be completely eliminated from the received signal r(t), leaving only the additive white noise and possible hostile jamming signals behind. Then, if the jamming power is significant enough, simple detection methods at the receiver should be able to discover its occurrence. 26 Downlink The situation is different, however, in DS-CDMA downlink. The signal received by the jth user is K_ H L_ H 12,-) Ed “mu — d -,l) + n(t) + J(t). (2.22) [9:0 [:0 771:-w It is common sense that one user is unaware of any users’ spreading codes except for his own code. Thus, multiuser interference cannot be directly removed from the un- processed signal at the receiver end. Although there exist some approaches to mitigate or completely cancel the effect of self- jamming for downlink communications using ju- diciously designed linear transformation or spreading codes, see [69,70] for example, the characteristics of the hostile jamming signal after performing such procedures are unpredictable, leading it difficult to be modeled and detected. Here, we propose to detect hostile jamming by turns for each user. Accordingly, the jth user’s received signal can be represented by :2 12,-, Z d( ijJ-(t — d-,,) + n(t) + J(t). (2.23) m=—oo It is essentially equivalent to the case of single user’s transmission, in which multipath propagation is the only cause of self-jamming. After obtaining the estimation of {hj,l}lL=—01 and {dj,l}1L=—01, the first term on the right-hand side of (2.23) can be removed by the jth user. Then the jth user can easily identify the jamming pattern on his own channel by following the procedures in Section 2.5. 27 2.5 Classification of Jamming Models 2.5.1 Jamming Classification Based on the Conventional Jamming Models In order to identify the pattern of jamming signals, we first need to investigate distin- guishable features among partial-time jamming (0 < pt < 1), partial-band jamming (0 < pf < 1), flat full-band jamming (pf = 1) and no jamming (pf = 0). According to the definitions, only partial-time jamming has significant changes on power spectrum over a certain interval of time, while partial-band and full-band jam- ming hold a negligible variance on power spectrum with respect to time at individual frequencies. This critical characteristic of partial-time jamming can be used to distinct itself from other jarmning patterns. Similarly, the variance of power with respect to frequency can be exploited as a discriminant measurement between partial-band and flat full-band jamming. Next, it renders an intractable problem of separating fiat full-band jamming from the back- ground white noise. Unfortunately, fiat full-band jamming cannot be easily differ- entiated from the background white noise, if the jamming power allocated for each frequency is unsubstantial. In that case, the hostile jamming signal can simply be regarded as the additional noise, since its negative effect on the system performance is negligible. In other words, it is meaningful to distinguish fiat full-band jamming from the white noise only if the jamming power is significant enough to degrade the system performance drastically. We propose to classify the jamming strategies by using a binary decision tree, where by convention the root node is put at the top, connected by successive links to other nodes, as shown in Figure 2.1. 28 Power spectrum of the signal hange is significan over time? Yes No hange is significan Partial-time jamming over frequency? Yes No ‘ verage power level 1 Partial'b‘md jammmg . -yond the threshold? Yes No Full-band jamming No hostile jamming Figure 2.1. Flow diagram of classifying the traditional jamming models. 29 For real-time applications, the variance of signal power may not be accurately esti- mated due to lack of samples within a short period. Therefore, we resort to detecting step edges on the two—dimensional power spectrum in the sense that a rising/ falling edge canonically represents an abrupt transition. For identification of partial-time jamming and estimation of the corresponding effective time, we utilize two thresholds (i.e., Trl for the rising edge, Tfl for the falling edge). Two different thresholds Trz and ng are similarly set for partial-band jamming. To distinguish flat full-band jam- ming from the background white noise, another threshold T ,3 is used. Classification is carried out through the following procedures: Step 1: Step 2: Step 3: Step 4: Power spectrum is approximately estimated by the magnitude-squared F F T of the received signal using the sliding window approach. Average the power spectrum over frequency and measure the results successively along the time dimension. If none of signals’ power exceeds T ,1, go to step 3. Otherwise, mark the first time instances with the power level over Trl as fl, then below Tfl as th. As a result, ,3, is equal to the ratio of the estimated jamming duration (f), — 5;) to the total observation time. Go to step 5. Take the average of the power spectrum over time, then search the results in sequence along the frequency dimension. Once discovering one signal power ex- ceeding Trg at frequency f), we assume that partial-band jamming is identified. As long as the power is not below T f2 until frequency f),, jamming remains effective. [if is then calculated as the ratio of the estimated jamming band- width (f), — fl) to the total available bandwidth. If partial-band jamming is not discovered, go to step 4, otherwise go to step 5. If the average power level goes beyond TT3, then flat full-band jamming is rec- 30 ognized and ,5, = 1. Otherwise, no jamming occurs in the received signal and fif=0. Step 5: Go to step 1 to process the next received data block. 2.5.2 Jamming Classification Based on the Time-Variant Jamming Generation Model In this subsection, we discuss time-varying jamming classification based on the two— dimensional jamming generation model. We assume 1. g(t,r) is zero-mean. 2. g(t,r) is a WSS process. 3. For any r1 74 r2, g(t,r1) and g(t,7'2) are uncorrelated. It then follows from these assumptions that A 1 Rgmtfllflz) = §Elg(t+At,T2)g*(t.Ti)l = Rg(At,rl)6(r1 — r2). Let At = 0, we have Rg(r) = Rg(0,r) = %E[g(txr)g*(t.r)l = %E[|g(t,r)l2l- 31 (2.24) (2.25) (2.26) (2.27) (2.28) Let C(t, f): f g( (t ,er) ’7 2” 1'd‘r be the Fourier transform of g(t, r) with respect ~00 to variable r. Assume g(t,r) is WSS, so is C(t, f). Define Rg(At, A f) = %E{G(t + At, f + Af)G*(t, f)}. Let At = 0, we obtain Rc(Af) = ;E [Gt,,f+Af)G*(tf)l (2.29) A 00 g(t,Tl)e-j2’r(f+Af)Tldr1][fg(t,r2)e_j2"f72dr2]*](2.30) -(X) \8 = gal Z. Since g(t, T1) and g(t, T2) are assumed to be uncorrelated, E[g (t ,)grl g(t ,r2)*]e-j27rf(71T72)e—j2"Afrldrldr2. (2.31) NIH 00 Ram f) = / Rg(r)e_j27rAdeT. (2.32) —oo This is the frequency correlation function of the jamming generation function. Let (A f )c be the range of frequencies over which Rg(A f ) is approximately fiat (Rg(A f ) 2 0.9 or 0.5), then (A f )c is a coherence bandwidth of the jamming channel. As in the time-varying channel modeling, we introduce the concept of flat jamming and frequency-selective jamming based on the value of (A f )c and the authorized user’s signal bandwidth B. If (A f )c > B, we say that the signal is experiencing flat jamming, otherwise, we say that the signal is undergoing frequency-selective jamming. We can say that full-band jamming belongs to flat jamming, and both partial-band jamming and tone-jamming belong to frequency-selective jamming. 32 If we set Af = 0 in R0(At, Af) and define CXD 120(11): / RG(At,0)e-J'2"VA‘dAt, (2.33) —00 then R001) is the Doppler power density of the jamming channel. Let Bd be the nominal bandwidth of R001), then the coherence time of the jamming channel can be obtained as 1 (At)c z -B—d-, (2.34) which is a statistical measure of the time duration over which the jamming channel is essentially invariant. Let T3 be the symbol duration of the authorized user’s signal. If (At)c < T3, then jamming variations are faster than signal variations, we call it fast jamming; If (At)c 2 T3, then jamming variations are slower than signal variations, and we call it slow jamming. To estimate (At)c, we perform time-frequency analysis on the observed one- dimensional signal wave J (t) to generate a view of the signal represented over both time and frequency simultaneously. The most commonly used methods are Wavelet trans- forms, Wigner-Ville distribution and Short-Time Fourier Tiansform (STFT), which can provide some information about how the spectral content of the signal evolves with time. Assume that the coherence time of jamming signals is invariant and prior knowledge of (At)c through rough estimation/ previous estimate is known: (At)c E [(At)lc, (At)}:‘]. Once the two-dimensional power spectral density S J(t, f) is obtained, fine estimation of (At)c can be carried out as follows: 33 Step 1: Step 2: Step 3: Arbitrarily choose a start time is, then scan SJ(t, f) along the t-axis to find K such that diss(SJ(ts + kAT,f),SJ(t8vf)) S T’ O S k < K (2 35) dISS(SJ(t3 + KAT, f),SJ(t3,f)) > T, where AT is the time resolution of 2-D PSD, T is the specified threshold, and diss(:r, 3;) denotes a function that measures the dissimilarity between a: and y. Specifically, diss(a:, y) returns a nonnegative scaler that indicates the pairwise difference between a: and y. diss(:1:,y) = 0 if and only if :1: = y. For example, if the Euclidean distance is adopted as the difference measure, then (2.35) becomes \/Z ISJ(ts + kATJk) - SJ(ts,fk)I2 S T, 0 g k < K k (2.36) $138.16.. + kAT. fie) — Sm... an? > T. An alternative measurement is correlation, which gives (2.35) another realiza— tion, IZSjlts + kAT.fk)S3(ts.ft)l s “r, 0 s k < K k (2.37) If]; 3.1(ts + kAT, fk)S;(t3a fk)| > T, where ’*’ denotes the conjugate transpose. Let ts = is + KAT, then search for the end time, denoted by te, to get another K by following (2.35). As a result, t6 = t3 + KAT. (At)c = te —— ts. If (At)c does not fall within [(At)lc, (At)g], then the estimation of coherence time is unsuccessful, due to the insignificant change of jamming 34 signals during the time interval from t s to te. To continue, let ts = te and then start over the above procedures. 2.6 Detection of Hostile Jamming An important application of jamming detection is to avoid transmission over the in- tentionally jammed channels, because it is most likely that the detected and decoded information is erroneous due to the low SINR even if jamming suppression approaches are applied at the receiver. The intuitive measurement for jamming is either the signal strength (if jammer emits a constant amplitude signal), or the energy level (if jammer emits a noise- like signal such as white Gaussian signals). Generally, clear, unjammed data record is needed at the receiver end to establish a statistical model describing the normal energy level prior to jamming. 2.6.1 Jamming Detection in Frequency Hopping Systems We follow the idea of the hypothesis test and apply it to jamming detection, H0 : the channel is not jammed, H1 : the channel is jammed. Under the assumption that signals are transmitted over an AWGN channel, the two hypotheses can be represented by where n(t) is white Gaussian noise with single-sided PSD N0 and J (t) is simply modeled as a zero-mean white Gaussian process with single-sided PSD N J. 35 Here, we consider two cases: Training Available First, update r(t) by subtracting the training symbol s(t) from it, then it yields Under the null hypothesis H0, r(t) is a Gaussian random process with single-sided PSD N0; Under the alternative hypothesis H1, r(t) is a Gaussian random process with single-sided PSD N0 + N J. o If N J is unknown (but definitely positive), during training phase, we measure the samples’ energy, and build a threshold representing the normal energy level, e.g., A = E [|r(t)|2] During test phase, we make the final decision whether or not there exists hostile jamming in r(t), by comparing the average energy level obtained from samples {Whit-{=1 with the threshold, that is, H1 1 K 2 REM 2 A. (2.38) k=1 H0 0 If No and N J are fixed and known (or estimated from previous samples), then we can easily formulate two conditional probability density functions: 1 77165 5 Incl? P(£IH0) = We k=1 , (2-39) 1 K 2 PW.) = 1 . ,,e—’ZN°+NJ’k§1’rkl. (2.40) (x/2W(N0+1VJ))I‘ 36 where f = [r1,r2, - -- ,rK]T. In this case, the likelihood ratio test (LRT) can be directly applied, H1 1 2> N—N0+JN———JZIT rkl 7} (241) HO Ag- Training Unavailable Since no pilot symbols are available, we utilize second-order statistics (SOS) based blind detection at the receiver end. First examine the mean of r(t) under two hypotheses. Since both n(t) and J (t) are of zero mean, we have H0: E[r(t)] = E[s (t) ]+ E[n(t)] = EM” (2.42) H1: E[r(t)] = E[s(t) ] + E[n(t )]+ E[J(t)] = EIS (t )I As can be seen from (2.42), H0 and H1 share the same mean. The simplest solution under this circumstance is to calculate the covariance of r(t) through time-averaging. Considering the independence among the data symbol, the additive noise and the jamming signal, we get 37 Ho: E[Ir(t)-EI7‘(t)II21 =E[ISUf)-EIS(t)t)II2I+153IIn(t t2)l I 2 = 0 + N0, 3 (2.43) H1 = E[IT(t)-(EITt)(t)II21 — —E[I8(t )- EI8(t)II2I + Elln(t)lzl + E[|J(t)lzl = 03 + N0 + NJ, where a? is the variance of message signals. Based on (2.43), a simple decision rule can be obtained: H1 1 K K 2< K :ITk— f1; 7"IcI (244) [3:] k1: H0 Taking channel fading effects (slow-varying) into consideration, we stack N samples of the received signal into a column vector 1;, H0: H I‘3 || I03 I: + (2.45) H1 I H + l‘i ll I0: I: I; where s, n and ,1 are N-sample column vectors corresponding to data, noise and jamming, respectively, and H is channel convolution matrix. The covariance matrices of 3 under H0 and H1 are given as follows: - r— r r— 7“ 71:02 [H H0. E[(_ E[_])(_ ELIII sHH +N01, (2.46) H1 = E[(r — E[rl)(r — E21)“ 1 = ofiHH“ + N01 + NJ! where ’H denotes Hermitian transpose, and I represents an (N x N) identity matrix. 38 Note that the discriminant between H0 and H1 only exists on the main diagonal of E [(1 — E [3])(1; — E [1])H]. Consequently, we can calculate the covariance matrix of the received signal vectors, and then take the average of all the entries on the main diagonal. If the average value is greater than a threshold, then H0 is rejected, and vice versa. 2.6.2 Jamming Detection in DS-CDMA Systems Since signals in CDMA systems are characterized by low power spectrum density, jamming detection in frequency domain is more suitable for DS—CDMA systems. Without Self-Jamming Cancellation The amplitude of the normal power at all the frequency components of r(t) under H0 is first derived, where no significant difference in strength among all the frequency components should be detected. Then for the received signal r(t), the power spectrum can be estimated via the magnitude squared of the FFT of the windowed signal [71]. If there is one frequency component with an unusually high amplitude in the estimate of power spectral density, it is most likely that this frequency is jammed and should be excised or interpolated. With Self-Jamming Cancellation To further improve the accuracy of jamming detection, the self-jamming cancellation technique should be exploited. Since the base station has the knowledge of all users’ Spreading codes and training symbols, the following procedures can be carried out to cancel the influence of self- jamming: 39 1. Estimate all the multipath channels using high-power pilot symbols. 2. Eliminate the self-jamming term from the received signal r(t). The remaining signal is equivalent to the signal received from an AWGN channel. 3. Determine whether or not hostile jamming occurs in the remaining signal. 2.7 Simulation Results In the simulation, a CDMA system with spreading factor 16 is considered. The binary spreading codes are randomly generated. BPSK modulation is adopted. J SR is defined as the ratio of the total jamming power to the average signal power, while SNR is defined as the ratio of the average signal power to the noise power. 2.7.1 Examples on Jamming Detection Assume that BPSK signals are transmitted over an AWGN channel. Self-jamming is ignored, for the time being. The jammer uniformly distributes its available power over the randomly-chosen frequency band. At the receiver end, hostile jamming is informed if the unusually high amplitudes of frequency components are discovered beyond a certain threshold. There are basically two types of detection errors: probability of miss and probabil- ity of false alarm. If no jamming is detected when the jammer is actually working, then miss detection happens. On the contrary, if the receiver determines that frequency band is being occupied by the hostile jamming signal when the jammer is actually off, the false alarm arises. Figure 2.2 shows the performance of jamming detection with respect to different levels of JSR. According to the definition, probability of false alarm is not related 40 to JSR, but dependent upon SNR. Thresholds with regard to different SNRs are determined in a way that the probability of false alarm is approximately 0.04. As can be seen, it is more likely that jamming can be exhaustively detected as the total jamming power is increased. Moreover, the noise strength on the channel will affect the performance of jamming detection. Given a fixed amount of jamming power, if the noise power is large enough to make a significant contribution on the receiver’s power spectral density, then the threshold must be high enough to achieve a small probability of false alarm, which consequently leads to a big chance that the receiver will fail to detect the existence of jamming, that is, a miss is most likely to occur. 10-1"IIIIIIII:IZIIIIIIIIZIIIIIII"'IIIIII:III.IICIIIIII ..... .............. é Iiiiiiiiifiiiifiiii'II:i2:Liiif’iiiiiiillii:KIIIII:LTQCIICIIIIIIII, “5 "Z:if:i:iiil'flfiiZIIIiiiiiiiiiiflfifXII.'IIICIC.XXIII: g ................................................ ................... . .D m .......................................................................... .0 r . » — «3 10 r:::::::::::::;::::::::::::::::::::::::::::"-f:::::::::: ::;::::::::'::::: ......................... :...........................u.............e b +SNR=5 ........... ........................... ............... . E SNR=10 ......... ......................................... 4 "+SNR=‘I5 ......... ......................................... , —€>—SNR=oo ; . . > 10'3 L i i i 0 2 4 6 8 10 Jamming-to-signal ratio (dB) Figure 2.2. Probability of miss versus J SR (here the probability of false alarm z 0.04). 41 2.7.2 Examples on Jamming Classification In this example, a four-user CDMA system with random spreading codes of length 16 is considered, where message signals are sent over frequency-selective fading channels. Denote full-band jamming strategy by SI, partial-band jamming by 5'2, partial— time jamming by S3, and no jamming by S4. Assume that the jammer randomly applies one of four strategies to interfere with normal data traffic of CDMA systems in each trial. If partial-time or partial-band jamming is adopted, pt (or pf) is randomly chosen within [0.2, 0.8]. In the simulation, the proposed binary decision tree is tested for different jamming power level by adjusting JSR from 0dB to 10dB while keeping the SN R level fixed. There are totally 10000 Monte Carlo runs for each JSR level. A typical classification confusion matrix without consideration of self-jamming is provided in Table 2.1(a), while identification results after self-jamming elimination are given in Table 2.1(b), under the same JSR and SNR levels. The entry in the ith row and jth column of the matrix represents the number of classifications that Si is identified when S,- is actually applied. Clearly, only the entries on the main diagonal of the confusion matrices are accurate classifications. Different thresholds are adopted in two scenarios. It can be observed that self-jamming in CDMA systems significantly affects the accuracy of classification. When the JSR is medium (e.g., 4dB), it is most likely that the power of jamming signals is not sufficiently high to ensure itself distinguishable from self-jamming, even if different thresholds are attempted. After the interference cancellation technique is applied to eliminate self-jamming, the accuracy of detection on hostile jamming is dramatically improved. Table 2.1(b) gives 100% accuracy of identification of jamming patterns by utilizing the proposed classification approach. Figure 2.3 shows the significant improvement in the estimation accuracy of jam- 42 Table 2.1. Classification confusion matrices: JSR = 4dB, SNR = 3dB. (a) Without self-jamming cancellation Recognized Actual SI 32 S3 34 S 1 1140 0 0 1342 $2 923 515 0 1 154 S3 599 0 954 903 S4 0 0 0 2470 (b) With self- jamming cancellation Recognized Actual SI S2 S3 S4 51 2482 0 0 0 52 0 2592 0 0 S 3 0 0 2456 0 S4 0 0 0 2470 ming bandwidth by exploiting self-jamming cancellation techniques. On the other hand, the error rate for estimation of pf in the case without self-jamming elimination vanishes with a steep gradient as long as the JSR is greater than 7dB, which, from another point of view, illustrates the effectiveness of the decision tree classification. 43 Probability of error of pf 10 E 10'1 . 10" r ----------- 3 ---------- —+— Without self-jamming cancellation “6 3 : —8— With self-jamming cancellation 1 0' i 1 1 1 0 2 4 6 8 10 Jamming-to-signal ratio (dB) Figure 2.3. Probability of error in estimating p f versus JSR. 44 2.8 Summary In this chapter, we focused on modeling and detection of hostile jamming for wire- less systems, particularly, for spread spectrum systems. A general two-dimensional jamming generation model was introduced, including all the existing models as spe- cial cases. The impact of hostile jamming in both frequency hopping and DS-CDMA systems was investigated. In addition, self-jamming effect was studied for uplink and downlink CDMA systems. It was shown that interference cancellation techniques could be exploited to eliminate self-jamming to further increase the accuracy of hos- tile jamming detection. Targeted at spread spectrum systems, jamming classification frameworks were presented, and both training-based and blind jamming detection methods were developed. The effectiveness of the proposed approaches was demon- strated by our simulation results. 45 CHAPTER 3 Spectrally Efficient Anti-Jamming System Design for Wireless Networks In this chapter, we introduce two novel concepts on spectrally-efficient anti-jamming system design: message-driven frequency hopping (MDFH) and collision-free fre- quency hopping (CFFH). Unlike in traditional FH where the hopping pattern of each user is determined by a preselected pseudo-random (PN) sequence, in MDFH, part of the message stream will be acting as the PN sequence, and transmitted through hopping frequency control. As a result, system efficiency is increased significantly since additional information transmission is achieved at no extra cost on either band- width or power. From the security point of view, information confidentiality is rein- forced since the hopping pattern is message—driven, hence totally unpredictable. In CFFH, based on the OFDM framework and the secure subcarrier assignment algo- rithm, the proposed CFFH system can achieve high information capacity through collision-free multiple access. At the same time, as each user still transmits through a pseudo-random frequency hopping scheme, CFFH can maintain the inherent anti— jamming, anti-interception security features of the conventional FH system. The pro- 46 posed schemes can be used for both civilian and military applications where secure high speed information transmission is needed. 3.1 Introduction As one of the two basic modulation techniques used in spread spectrum communica- tions [64], frequency hopping technique was originally designed to be inherently secure and reliable under adverse battle conditions for military purpose. In traditional FH systems, the transmitter “hops” in a pseudo-random manner among available fre- quencies according to a pre—specified algorithm, the receiver then operates in exact synchronization with the transmitter and remains tuned to the same center frequency. Based on the hop duration period, FH systems can be further divided into two categories: fast hopping (FFH) scheme and slow hopping (SFH) scheme. In an FFH system, the carrier hops several times during one symbol period, while in an SFH system, each hop lasts at least one symbol period. Since different bands are unlikely to experience simultaneous fading, FH systems are robust against fast fading. At the same time, pseudo-random frequency hopping during radio transmission minimizes the possibility of hostile jamming and unauthorized interception. In 1978, Cooper and Nettleton [72] first proposed a frequency hopping multiple access (FHMA) system with DPSK (Differential Phase-Shift Keying) for mobile com- munication applications. Later in the same year, Viterbi [73] initiated the use of MF SK (M-ary Frequency-Shift Keying) for low-rate multiple access mobile satellite systems. Since MFSK modulation enables non-coherent detection, it has been widely adopted in FHMA systems [74—77]. There are two major limitations with the con- ventional FH systems: (i) Strong requirement on frequency acquisition. In existing 47 F H systems, exact frequency synchronization has to be kept between transmitter and receiver. The strict requirement on synchronization directly influences the complexity and performance of the system [78], and turns out to be a significant challenge in fast hopping system design. (ii) Low spectral efiiciency over large bandwidth. Typically, F H systems require large bandwidth, which is proportional to the product of the hopping rate and the number of all the available channels. In conventional F HMA, each user hops independently based on its own PN sequence, a collision occurs whenever there are two users transmit in the same frequency band. Mainly limited by the collision effect, the spectral efficiency of conventional F H systems is very low due to inefficient use of the large bandwidth. In the literature, considerable efforts have been devoted to increasing the spectral efficiency of PH systems by applying high—dimensional mod- ulation schemes [37—43]. However, existing work is far from adequate to address the ever increasing demand on inherently secure high speed wireless communication. In this chapter, we propose an innovative message—driven frequency hopping scheme. The basic idea is that part of the message will be acting as the PN se- quence for carrier frequency selection at the transmitter. In other words, selection of carrier frequencies is directly controlled by the (encrypted) message stream rather than by a predetermined pseudo-random sequence as in the conventional FH systems. At the receiver, the transmitting frequency is captured using a filter bank as in the F SK receiver rather than using the frequency synthesizer. Therefore, the carrier frequency (hence the information embedded in frequency selection) can be blindly detected at each hop, and thus largely relaxes the burden of strict frequency synchronization at the receiver. More importantly, by embedding a large portion of information into the hopping selection process, additional information transmission is achieved with no extra cost on bandwidth or power. Therefore, the system spectral efficiency is signif- 48 icantly improved. In addition, MDFH makes it possible for faster frequency hopping in wideband systems. Ptom the security point of view, it also reinforces the jam- ming resistance of the F H system since the message-driven hopping pattern is totally unpredictable. To further increase spectral efficiency, an enhanced version of MDF H, named E- MDFH, is proposed by enabling simultaneous transmissions on multiple channels at each hop. This enhanced transmission scheme provides better design flexibility, and much higher spectral efliciency through a careful design of the hopping frequency selection process. It turns out that E—MDFH contains both MDF H and OF DM as special cases, and can readily be extended to a collision-free multiple access FH sys- tem through user multiplexing. Furthermore, quantitative performance analysis on both bit-error-rate and spectral efficiency is conducted based on theoretical deriva— tion, as well as simulation examples. Our analysis demonstrates that: transmission of information through hopping frequency control essentially adds another dimension to the signal space, and the resulting coding gain can increase the spectral efficiency by multiple times. Motivated by the advantages observed in E-MDFH which allows simultaneous transmissions over multiple frequency bands at each hop, a highly efficient secure communication interface — the collision-free frequency hopping system is developed. The major features of the CFFH scheme can be summarized as follows. First, CFFH is highly spectrally efficient because it is collision-free and makes full use of the available spectrum. Moreover, the spectral efficiency of CFFH is enhanced by the OFDM frame- work. OF DM allows frequency overlapping between subcarriers which are orthogonal to each other, and hence is much more efficient than the conventional FH system where guard band is needed between neighboring channels. Secondly, since OFDM is 49 implemented through F F T, CF F H can relax the complex frequency synchronization problem suffered by conventional F H systems. Thirdly, a dynamic subcarrier assign- ment algorithm is designed for the CFFH scheme. Ensured by AES, CFFH maintains the inherent anti-jamming security feature of conventional FH systems. Fhrthermore, in multiple access environment, anonymous multiparty communication can be achieved by sending dummy bits on certain subcarriers and hence can prevent traffic analysis by the hostile party. The rest of the chapter is organized as follows. Section 3.2 describes major limi- tations of the conventional FH system. In Section 3.3, the concept of MDFH scheme is introduced, and then extended to efliciency enhanced MDFH. Quantitative per- formance analysis on BER and spectral efficiency is presented to demonstrate the superior bandwidth efficiency of MDF H. Section 3.4 is focused on the CFFH scheme. The signal transmission scheme and detection procedures are described, followed by an AES based secure subcarrier assignment algorithm. Performance analysis and sim- ulation examples are provided to illustrate the advantages of CFFH. We conclude in Section 3.5. 3.2 Challenges in the Transceiver Design of Fre- quency Hopping Systems The block diagram of a traditional FH system is shown in Figure 3.1. A main limita- tion with this design structure is the strong requirement on PN acquisition, as exact frequency synchronization has to be kept between transmitter and receiver. The strict requirement on synchronization directly influences the complexity and performance of the system. Slow hopping systems, therefore, have been popular because of their 50 FSK Bandpass ‘ Bandpass FSK generator I filter I filter demodulator PN Frequency Frequency PN code synthesizer synthesizer code Figure 3.1. Block diagram of the conventional frequency hopping scheme. relaxed synchronization requirement. On the other hand, due to their resistance to hostile jamming and interception, fast hopping systems are highly desired in classified information transmission. This raises a big challenge in transmitter-receiver design. In addition, traditional frequency hopping systems are also being challenged to transport more information with little or no increase in allocated bandwidth. Along with rapid development of high-speed multimedia information transmission, spectrum has become the most precious resource in wireless communications, since the total available spectrum has to be shared by all wireless services. FSK generator in Fig- ure 3.1 is generally realized by MF SK modulation. In order to maintain the orthog- onality among carrier frequencies in SFH, the transmitted tones must be spaced at a separation equivalent to the baud rate (or the hop rate in FFH), or a multiple of the baud rate, otherwise it is difficult to separate one tone from another. Therefore, the constellation size M cannot be too large to support high speed communication, considering the stringent restriction of the total bandwidth. Meeting these challenges, i.e., strict synchronization requirement and low spectral efficiency, calls for advanced signaling techniques. 51 3.3 Message-Driven Frequency Hopping In this section, we introduce the concept of message-driven frequency hopping. The basic idea is that part of the message stream will be acting as the PN sequence for carrier frequency selection. Spectral efficiency of MDFH can be further enhanced by allowing simultaneous transmissions over multiple frequency bands at each hop. Including both MDFH and OFDM as special cases, the enhanced MDFH scheme, named E—MDFH, can achieve higher spectral efficiency while providing excellent de- sign flexibility, and can readily be extended to a FH-based collision-free multiple access scheme. Our quantitative analysis on bit-error-rate and spectral efliciency indicates that: transmission of information through hopping frequency control essentially in- troduces another dimension to the signal space, and the corresponding coding gain increases system efficiency by multiple times. 3.3.1 Transmitter Design Let NC be the total number of available channels, with {f1, f2, - - - , f Ne} being the set of all available carrier frequencies. Ideally all the available channels should be involved in the hop selection process, as is required by current frequency hopping specifications (e.g., Bluetooth). The number of bits required to specify each individual channel is c = [logg NC], where [2:] denotes that largest integer less than or equal to x. If NC is a power of 2, then there exists a 1-1 map between the 36-bit strings and the available channels. Otherwise, when NC is not a power of 2, we will allow some Bc-bit strings to be mapped to more than one channels. More specifically, for i = 1, -- - , NC, the ith channel will be associated with the binary representation of the modulated channel index, [(i — 1) mod 230] + 1. In the following, for simplicity of notation, we assume 52 that NC = 230. Let Q be the selected constellation that contains M symbols, then each symbol in the constellation represents 38 = log M bits. Let T3 and Th denote the symbol period and the hop duration, respectively, then the number of hops per symbol period is given by N), g Ts/Th. We assume that N), is an integer larger or equal to 1. In other words, we focus on fast hopping systems. We start by dividing the data stream into blocks of length L 9— Nth + 33. Each block consists of Nth carrier bits and Bs ordinary bits. The carrier bits are used to determine the hOpping frequencies, and the ordinary bits are mapped to a symbol which is transmitted through the selected N), channels successively. Note that the number of the carrier bits is determined by BC (the number of bits used to specify one hopping frequency) and Nh (the number of hops within one symbol period). The number of ordinary bits is exactly the number of bits represented by one individual symbol in constellation Q. Denote the nth block by Xn, we intend to transmit Xn within one symbol period. The carrier bits in block Xn are further grouped into N), vectors of length BC, denoted by [Xn,1, - .. ’XnJVhI' The bit vector composed of Bs ordinary bits is denoted by Yn, as shown in Figure 3.2. Carrier Bit Vectors ~ Ordinary Bit Vector -> I 9 an X122 """ Xn,Nh Yn Figure 3.2. The nth block of the information data. The transmitter block diagram of the proposed MDFH scheme is illustrated in Figure 3.3. Each input data block, Xn, is fed into a serial-to-parallel (S/P) con- 53 verter, where the carrier bits and the ordinary bits are split into two parallel data streams. The selected carrier frequencies corresponding to the nth block are denoted by {fn,1)“ '1fn,Nh}aWhere ea’Ch fn,i 6 {flaf21' " ach}1Vi E [erh] Assume Yn IS mapped to symbol An, and the corresponding baseband signal is denoted as m(t). n-th data block X’bl ’. ' ’Xn’N Carrier Frequency f ",1 " ' '2fn,N )gl Selection S ( ) S/P _ ‘ Converter Y _ Modulation - n Baseband Signal m (0 Generation Figure 3.3. Transmitter structure of MDFH. If pulse amplitude modulation (PAM) is adopted for baseband signal generation, then 00 Ni) =2 2.4,, g( (t— nr, — (z — 1)Th), (3.1) TIT—“.00 i=1 where g(t) is the hpulse-shaping filter. Define mn,,-(t) _A_ An g(t — nTs— (i - 1)T h), then 00 m(t) = Z 1% mn z(t). The corresponding passband waveform can be obtained as: n=—00 i=1 s(t): @128le Nzlmnnu 06]? an’it Xn,i(t)}1 (3'2) where 1, tE [nTs + (z -‘ 1)Th1 ”T8 + z.Thlv Xn,i(t) = (3.3) 0, otherwise. If MFSK is utilized for baseband modulation, then s(t): Th Z i cos27r[ [fn it + Kf/:>o mn ,(r)dr]xn ,(t). (3.4) Tl=—OO 3:1 54 where K f is a preselected constant. Discussions on Bandwidth Requirement As is well known, FM requires much larger bandwidth than PAM. Here, we will focus on PAM based FH systems. In equation (3.2), let sw-(t) 2 [mm- cos 27r fn,;t]xn,,-(t). By definition, the bandwidth of sm-(t) is determined by the spectrum of g(t—nTs - (i — 1)Th)Xn,i(t)) which is given by the convolution .77(g(t — nTs — (i - 1)Th)) *J-‘(xn’z-(fi), where f(:r) denotes the Fourier transform of 2:. If the bandwidth of g(t) is BWg Hz, then the bandwidth of g(t — nTs —- (i — 1)Th)x,,,,-(t) is BWg + 7%. Therefore, in general, the total channel bandwidth in order to avoid inter-carrier interference (ICI) in the FH case will be 2NC(BWg + 7%). In the particular case when g(t) is a rectangular pulse, then 311,1“) = mn,,-(t) cos 27rfn,,-t. Note that If(Xn,i(t))I = Thlsinc(7rThf)|, that is, when f = if)“; k E Z+, |f(xn,,-(t))| = 0. This implies that if carrier frequencies in the PH system are separated by integer times of 71):, there is no ICI between the carriers. Therefore, in this case, the minimum bandwidth requirement is Eff—1, and the s(t) in (3.2) essentially reduces to an OFDM signal. 3.3.2 Receiver Design The structure of the receiver is shown in Figure 3.4. Recall that {f1, f2, ~ .. , f Nc} is the set of all available carrier frequencies. To detect the active frequency band, a bank of NC bandpass filters (BPFs), each centered at f, (i = 1,2, - .. ,Nc), and with the same channel bandwidth as the transmitter, are deployed at the front end. Since only one frequency band is occupied at any given moment, we simply measure the outputs of bandpass filters at each possible signaling frequency. The actual carrier frequency 55 at a certain hopping period can be detected by selecting the one that captures the strongest signal. As a result, blind detection of the carrier frequency is achieved at the receiver. J fn,l’"if Xn,1"°3Xn,Nh —' BPF, f1 —— ABS ——~ Table Look-up X P/S n \f— BPF’ f2 W/i—i ABS H Select Converter—T . La t Demodulation .. " r(t) , rges m(t) Baseband Signal Y}; Detection —. 81$,ch —/ ABS Figure 3.4. Receiver structure of MDF H, here ABS means taking the absolute value. More specifically, the received signal can be written as r(t) = h(t) =1: s(t) + w(t), (3.5) where * stands for convolution, h(t) is the channel impulse response, and m(t) denotes the additive white Gaussian noise. Accordingly, the outputs of bandpass filters are given by 2,-(t) = qz-(t) * r(t), for i = 1, - -- ,Nc, (3.6) where qi(t) is the ideal bandpass filter centered at frequency f;, i = 1, 2, - - - , NC. If the channel is ideal, i.e., h(t) = d(t), then 2,-(t) = q,-(t) * s(t) + uz-(t), for i = 1, - ~~ ,Nc, (3.7) where u,-(t) = q,-(t) =1: m(t) is the filtered version of the noise. If the signal-to-noise ratio is sufficiently high, as in most useful communication systems, there is one and only 56 one significantly strong signal among the outputs of the filter bank. Suppose the lth filter captures this distinctive signal during the ith hop of the nth block, then we have fw- = l. The same procedures can be carried out to determine the carrier frequency at each hop. Next, the estimated hopping frequencies {fn,1, . -- , meh} are used to extract the input signal. On one hand, {f,,,1, - -- , meh} are mapped back to Bc-bit strings to recover the carrier bits. We denote the estimated carrier bit-vectors as {22”,1, - - - ’Xnflhl' On the other hand, the ordinary bit-vector, Y", is first estimated independently for each hop, then bit-wise majority voting is applied for all the N), estimates to make the final decision on each ordinary bit in Y". We denote the esti— mated ordinary bit-vector as 177,. It then follows that the estimate of the nth block Xn can be obtained as: Kn =[Kn,1,--- an,Nh)lA/nl- Remark 3.1 Unlike the conventional FH scheme for which the receiver can be de— signed through a single frequency tunable filter, the receiver that we use in MDFH is a filter bank consisting of bandpass filters, which is similar to the filter bank used for non-coherent detection of FSK signals. In fact, it can be implemented by paralleling several F SK receivers. Along with advances in large scale circuit integration and fab- rication, this receiver design is both feasible and practical. It is interesting to note that in [7.9], the message is used to select the spreading code in CDMA and therefore increases the system capacity. El Remark 3.2 Design of the MDF H receiver leads to a security observation: if such a filter bank is available to a malicious user, then both the conventional FH signals and the MDFH signals can largely be intercepted by an unauthorized party. This implies that to prevent unauthorized interception, information has to be encrypted before being transmitted over an F H system. [3 57 Remark 3.3 One important feature of F H systems is jamming resistance. In MDFH, as the hopping frequency is determined by the encrypted message signal, the hopping pattern is more unpredictable than that in the conventional FH, which is determined by a pre-selected PN sequence. From this point of view, we can see that: while achieving higher spectral efiiciency by embedding bits into the hopping frequency selection process, MDF H also has better or at least comparable jamming resistance with the conventional FH. CI 3.3.3 Efficiency Enhanced MDFH To further improve spectral efliciency and design flexibility, we refine the transceiver design of the MDFH system by allowing simultaneous transmissions over multiple frequency bands. The modified scheme is referred to as enhanced MDFH (E—MDFH). The Modified Hopping Frequency Selection Process Recall that NC = 280 is the number of all available carriers. We split the NC car- riers into Ng non-overlapping groups {03:91, with N9 = 289, then each group has Nf é Nc/Ng = 230—139 carriers. Specifically, Cl = {fl, - .. ,fo},C2 = {fo+1,° " )f2Nf}, ' ” )CNg = {ch—Nf+l,"' ,ch}- NOW we consider to modify the transmitter design in MDF H, such that simultaneous transmissions over multiple frequency bands can be achieved at each hop. An intuitive method is to employ an in- dependent MDFH scheme within each C; for l = 1, - . ~ ,Ng, referred to as FD-MDFH. In this case, the frequency hopping process is limited to N f (<< NC) successive carri- ers, leading to insufficient randomness and therefore inadequate jamming resistance. To maximize the randomness, here we present an alternative approach. We divide the incoming data stream into blocks of length [Nh(Bc — 39) + Bs]Ng. Denote the 58 nth block by X". Xn is further divided into Ng vectors: Xn = [Zn,1, - -- ’ZTl,Ngl' For m = 1,--- ,Ng, each me contains Nh(Bc — 89) + 3,, bits. Write me = [Dam - - - , D71: ’75,, Ymm], where each Dim, is a bit-vector consisting of (BC-By) carrier bits, and bit-vector Yam consists of BS ordinary bits. We adopt the notation “bin2dec” (used in Matlab) to denote the operation of converting a binary vector to a decimal number, and “dec2bin” the reverse operation. For m = 1, - ~ ,Ng,i = 1, - -- ,Nh, we define dam é bin2dec(Df,,m) + 1. Recall that there are N), hops in one symbol period, at each hop, the signal will be transmitted through Ng carriers simultaneously. For i = 1, - . . , Nh, the frequency index for the mth carrier at the ith hop is defined as: $1.1 = dinlr When 7" = 1 (3 8) 1},” = [hm—1 + dam, when m = 2, - -- ,Ng. This carrier selection procedure is designed to ensure that: (i) All the available carriers are involved in the hopping selection process; (ii) The hopping frequencies have no collisions with each other at any given moment. In fact, at each hop, 1,2,, < 1,2,2 < < 13,,Ng, (3.9) since 11“,,l E [I’Nfl’lhz E [';,1+112Nfla‘”,1fi,Ng E IliuNg-l +1,Nc]. After the hopping frequencies are determined for all the N9 carriers, each Ymm (m = 1, - - - ,N9) is mapped into a symbol in constellation Q and then transmitted through the mth carrier, which hops through frequencies f 11 , - -- , f1 Nh . As the result, Xn is now n,m n,m transmitted in one symbol period through simultaneous multicarrier transmission un- der the message-driven frequency hepping framework. 59 Signal Detection As in MDF H, the receiver in E—MDFH also consists of a bank of NC bandpass filters. However, the signal detection procedure needs to be modified. Take the extraction of Xn as an example. At the ith hop, instead of searching for the bandpass filter which captures the strongest output in MDFH, we now identify N9 filters which deliver the largest Ng outputs. According to equation (3.9), the indices of these Ng bandpass filters are sorted in ascending order, to obtain the estimated indices for lam, that is, If” < If]; < - -- < ih,Ng' Now the carrier-bit vectors can be estimated as: 3’. = dec2bin(Ii — 1), when m = 1 .7.” .7.” .. (3-10) Dam = dec2bin(1,’,,m — [fun—l — 1), when m = 2, - .. , N9. At the same time, each ordinary bit-vector Yum is estimated from the received signal corresponding to the mth carrier based on bit-wise majority voting, similar to that in MDFH. Remark 3.4 Taking the carrier usage into consideration, the modified design struc- ture includes both MDFH and OFDM as special cases. In fact, if N9 = 1, then E-MDFH is reduced to MDFH. Likewise, if N9 = NC, then E-MDFH can readily be implemented through an OFDM system. The advantage of E—MDFH is two-fold. First, E-MDFH improves the design flexibility in the sense the transmission scheme can be easily adjusted by tuning the values of 89 or N9. Second, E-MDF H can achieve much higher spectral efficiency than MDFH. Unlike MDFH which occupies only one carrier at a time, E—MDFH makes better use of the available spectrum by allowing simultaneous transmissions over multiple channels. Cl 60 3.3.4 Collision-Free MDFH in Multiple Access Environment Collisions in Conventional FHMA systems One major challenge in the current F HMA system is collision. In FHMA systems, multiple users hop their carrier frequencies independently. If two users transmit si- multaneously in the same frequency band, a collision, or hit occurs. In this case, the probability of bit error is generally assumed to be 0.5. If there are NC available channels and Na active users (i.e., Nu — 1 possible in- terfering users), assuming that all NC channels are equally probable and all users are independent, then the probability that a collision occurs is given by 1N—1 =1—1—— u . P). < N.) (311) Nu” C when NC is large. (3.12) Taking NC = 64 as an example, the relationship between the probability of collision and the number of active users is shown in Figure 3.5. The high collision probability severely limits the number of users that can be simultaneously supported by an FH system. Assuming BFSK modulation and N}, = 1, if two users are not transmitting simultaneously through the same frequency hand, then the probability of bit error is P8 = %€_2%5 where 71% is the bit-level signal-to-noise ratio (SNR). If two users transmit simultaneously in the same frequency hand, then the probability of bit error is generally assumed to be %. The overall probability of bit error can thus be modeled as E. I —§7§9— 1 P6 = 56 0(1- ph) + Eph° (3'13) It follows from equation (3.13) that there exists an error floor (i.e., §ph) for the conven- 61 10 b l I l l l C .9 .«_.e 3 “5 -1 _ g 10 : .5 (U .0 2 :1 —-ar— Empirical results 2 —6— Theoretical values 10‘ 1 L a 1 1 0 10 20 30 40 50 60 Number of users Figure 3.5. Probability of collision (Ph) versus the number of users (starting at the two-user case) for NC = 64. 62 tional FHMA systems. Our discussions above indicate that an alternative approach is to develop collision-free FHMA techniques. PrOposed collision-free MDFH The E—MDFH system can readily be extended to a collision-free MDFH scheme to accommodate more users in the multiple access environment, denoted as CF-MDFH. Assume there are Nu users in the system. Recall that the block length in the E- MDFH system is L. Without loss of generality, we assume that all the users have the same data rate, and the number of bits assigned to each user is an integer Nb = 7(1):. (Otherwise, users may have unequal number of bit assignments so that the total length of the block is L.) Bit streams from different users are mixed through a simple user-multiplexer, as shown in Figure 3.6(a). The ith user’s bit stream is written successively into the ith row of the block interleaver, for i = 1, - -- ,Nu. The content of the interleaver is column—wise read out. A secure scrambler is added after the user multiplexer to further randomize the carrier frequencies occupied by each user. A good example of secure scrambler design can be found in Section 4.4.1 or [80], where the secure scrambling sequence is obtained by encrypting a PN sequence with AES. Finally, the resulting sequence is fed into the input of serial-to—parallel converter in Figure 3.3. At the receiver, the corresponding de—multiplexer, as shown in Figure 3.6(b), is applied to recover the input bits. Separation of users’ information is essentially the reverse operation of data multiplexing. CF—MDFH is a joint time-division (TD) and frequency-division (FD) multiple ac- cessing scheme, including both TD-MDFH [81] and FD-MDFH as special cases. The infrastructure of TD-MDFH is shown in Figure 3.7. For fairness, each user is periodi- 63 L. blbl...b1 b2...bNu 1 2 Nu‘ Nu Parallel-to-Serial Read Out ’ User 1 In L 2 1 —. blNu e e e bl bl User 2 In L S b To S/P Converter — 2 1 = ecure Scram ler __, ———. szu o e 0 b2 b2 User Nu In —L— 2 1 ——H) Nu o e e b b bN Nu Nu u (a) Block-wsie user multiplexer _L_ ‘l ‘l ”1 ‘2 “N b b . . . b b . . . u l 2 NH 1 Nu Serial-to-Parallel Write In User 1 Out L -2 .1 ‘_—_ ‘Nu ° ' ' b1 b1 L From P/S Converter User 2 Out __ 52 131 Secure Descrambler ~ {— AN“ 0 e o 2 2 U N O t L 2 l ser u u —— * " ‘__— bNu e o e bNu bNu Nu (b) Block-wsie user de-multiplexer Figure 3.6. Block-wise user multiplexer and de-multiplexer, designed to process one data block of length L consisting of bits from NH users. Here b3- denotes the ith bit of user j in the block. 64 cally assigned a time slot to transmit his/ her information. Each active user transmits to the base station only in the assigned time slot or slots so that multiple-access inter- ference (MAI) can be completely eliminated, assuming perfect timing synchronization is achieved at both sides. Because blind carrier frequency detection is still applicable in TD-MDFH, each data packet does not have to include a user—ID at each hop for each user, as long as the receiver knows the exact assignment of time slots for the corresponding transmitter. In this case, the reduced overhead results in the further increased spectral efficiency. Y Y Y MDFH MDFH o o o o o o MDFH Userl A User2 L UserN i Time Division Multiple Access Figure 3.7. Infrastructure of the TD-MDFH scheme. Remark 3.5 CF -MDFH enjoys good scalability as the maximum user transmission rate is adaptive, and reversely proportional to the number of users in the system. Moreover, carrier frequencies at each hop are jointly determined by the information bits from all the users, and source anonymity is ensured by both the interleaver and the scrambler. Without the knowledge of the secure scrambler, even if the malicious user has a powerful set of equipments that can monitor the whole spectrum and can perfectly recover the carrier bits and the ordinary bits, extraction and composition of the desired user’s information based on the securely scrambled sequence is a forbidden 65 a. F- task. U 3.3.5 Bit-Error—Rate Analysis Recall that in the MDF H and E-MDFH, the input bit stream is grouped into carrier bits and ordinary bits, where carrier bits are embedded in hopping frequency selection and ordinary bits are mapped to symbols in a certain constellation and then trans- mitted through selected carriers. It is interesting to note that non—uniformity exists between the carrier bits and the ordinary bits, in the sense that they have different BER performances. Since MDF H can be regarded as a special case of E—MDFH, we will focus on E—MDFH for bit error probability analysis. BER of the carrier bits Based on the receiver design in E—MDFH, BER analysis of the carrier bits is analogous to that of non-coherent FSK demodulation. For non-coherent detection of M F-ary FSK signals, the probability of symbol error is given by [63, eqn. (54-46)] IMF—l mlog2M E E MF‘I —1m+1 "—(_YE 103,st (F3) 2 Z (7th "”1 N3, (3“) m=l m where £3- is the bit-level SNR. Let kF = log M p, then the probability of bit error, denoted by Papgg, can be written as Eb 2(kF-1) Eb) —— = ——P — . 3.15 Pe,FSK ( N0) 2’61? _ 1 .9,st N0 ( ) Em For an E-MDF H system with NC channels, M F 2 NC, and kp = BC. Let 0 66 (0) E and 7%— denote the effective bit-level SNR corresponding to the carrier bits and the ordinary bits, respectively, and 715% the average bit-level SNR for the E-MDFH system. Recall that in the E—MDFH scheme, the length of each block is L = [Nh(Bc —- By) + BS]2BQ, out of which there are 83239 ordinary bits and Nh(Bc —— Bg)2Bg carrier bits. Note that in E—MDFH, the carrier bits are embedded in the carrier selection process and do not consume additional transmit power, the average bit-level SNR is — = B , (3.16) where E, is the average symbol power. In fact, let E1, - -- ’ENt be all the possible power levels in constellation Q, and p, the probability that an arbitrary information symbol has power Ei, then the average symbol power E3 is given by ZpiEi = E‘s,where Zpi = 1. (3.17) Without loss of generality, we assume E1 3 E2 3 - - - S E Nt' Taking 16—QAM as an example, Nt = 3, E1 = 2, E2 =10, E3 = 18, and p1: 1/4, p2 = 1/2, p3 =1/4. Since each frequency is uniquely identified by BC bits, and each symbol represents BS bits, the effective bit-level SNR corresponding to the carrier bits and the ordinary bits can be calculated as: (c) - E . b = Eb , (3.18) No NOBC (o) - E b = 3L, (3.19) 67 respectively. Substituting (3.16) into (3.18) & (3.19), it yields that ( ) fl: = [Nh(BC —' By) + BS] _E_b (3 20) N0 Nth No’ ' N0 Nth NO’ ' In the particular case when N9 = 1, E—MDF H is reduced to MDFH. Following (3.14), the BER for the carrier bits in MDFH can be obtained as: Ea) _ Nt N —1 B E- P(C) fl = 2(Bc 1) p. c NC — 1 (____1)m_+le_ 3:“ Efifiw 22) e,MDFH N0 28¢ __ 1 . z m + 1 ' i=1 m=1 m Let PkXJ D F H denote the probability of carrier frequency detection error (correspond- 3» ing to the symbol error in FSK) in MDFH, then we have P(c) Eb _ 286 ‘ 1. 10(0) Eb 3 23 s,MDFH 7‘76 — 2(Bc—1) e,MDFH To - ( - ) In the more general case when Ng 71$ 1, detection of the carrier bits in E—MDFH is similar to that of differential encoding (please refer to Section 3.3.3). Estimation error in one carrier index may cause detection errors in two neighboring carrier bit blocks. Denote the probability of carrier frequency detection error in E—MDFH as Pg: M D F H' It follows from (3.14) that Ea) Nt NC-l N _ 1 m+l mB- E1 (C) Eb _ C (‘1) ‘Z 15 75 PE—MDFH (F0) - 2 :Pi E We "1+ E3 - (3.24) '=1 m=1 m Please note that 71573 in E—MDF H is different from that in MDF H due to their different 68 __ ‘— . — lJ-‘J. block structures. Recall that for i = 1, - -~ ,Nh,m = 1, - -- ,Ng, 133m denotes the frequency index for the mth carrier at the ith hop of the nth symbol period. At each hop, 1%,", should satisfy 132,1 < 131,2 < < 1;, Ng° For signal detection, after each individual carrier index is estimated, they are then sorted in ascending order to recover Ih,m- An error in the carrier index estimation may further introduce errors in the sorting procass, and hence has negative impact on the index estimation for more than one 1,1,". Therefore, if Pg} M D F H (7%) denotes the average probability that an index 1%,", is incorrectly estimated, then we have Pig-)MDFH (715%) 2 PhclMDFH (£3). Since d" 1 is uniquely determined by In 1, it is clear that the probability of error in estimating d; 1 is PEI M D F H (N3). For the rest {rig m}mg _2, each d}, m relies on both [fun and I 1. Therefore, the probability that dim, is correctly detected, n,m-— for m = 2,... ,Ng, is [I‘PgZMDFH (71%)]? Note that P“ E—)MDFH (713%) Z P [(201 M D F H (£73). A lower bound of the BER for the carrier bits can thus be ob- tained as P(c)L Eb e, E— MDFH (N0) = 32€{7il§P1gclMDFH (Nfi) + + {1 ‘ [ PEQMDFH (7%)]1} (3 25) A 2(BC— 39‘” where 13826273739":- Furthermore, the probability that all the indices {1}, m}mg ___1 are correctly esti- Ng mated is [1 - Pg: C) M D F H (713%)]9 . In this case, all the carrier bits can be perfectly recovered. If we assume that any estimation error in {I}, m}mg _1 will mcur detection errors in all the carrier bit blocks, then an upper bound of the BER for the carrier 69 bits can be derived: C) Eb c Eb N9 P§,E— UMDFH(N—0)=P32€{l_[1 Ph)MDFH(NO>] } (3-26) To summarize our discussions above, we have: Proposition 3.1 In E—MDFH, the BER of the carrier bits, P(l)3- MDFH’ is bounded by (C),L Eb (C) Eb (C) U Eb Pe,—E MDFH (N0) SPe,E— MDFH (N0)5Pe,E— MDFH (N0 (3'27) Accordingly, the probability of error on the estimation of dam, Pg? M D F H’ fori = -,Nh,m=1,--- ,Ng isbounded by 0 v 1 P(c),L Eb SPM) E_b < 1 P(c)U Eb 1:882 e,—E MDFH N0 E— MDFH N—O p82 Pe,—E MDFH F 9,, (c),L v E AP E 13,—3E MDFH(N%) Ps,E'— )UMDFH(N%) BER of the ordinary bits BER of the ordinary bits is determined by the modulation scheme used in the system. If FSK is utilized, then the BER of the ordinary bits can be calculated in a similar manner as that of the carrier bits. In the following, we consider the case of transmitting the ordinary bits through M-ary QAM. We start with MDFH, which is easier to analyze, then extend the results to E-MDFH. Recall that if M = 233, where B, is an even integer, the probability of symbol 70 error for M-ary QAM is [63, eqn. (5-2-78) & (5—2-79)] E. _ _ _ ___1_ BlogzME. PS*MQAM(N0)‘1 [1 2‘1 m)Q( (M-1)N0 , (3.28) 00 t2 where Q(:r) = 7%; f equt. 1‘ Taking 16—QAM as an example, we have Eb _ 9 4 4Eb 4 Eb Ps,16-QAM(1—V'6) — Z (3' - Q (WE-1%)) Q (”E-1V6) . (3.29) Accordingly, the probability of bit error is Eb __ 9 4 /4 Eb /4 Eb Pe,16—QAM('1V6) - E (5 — Q( 51%)) Q( EM) . (3.30) In MDFH, each QAM symbol undergoes N), hops. Here we assume that N}, is odd. For signal detection, we first estimate the QAM symbol independently for each hop, and then apply bit-wise majority voting for the N), estimates to make the final decision. Accordingly, the BER of the ordinary bits, Piaf/I D F H, can be calculated as follows: i) BER analysis at each individual hop: At each hop, the bit error can be classified into two types. Type I error: bit is in error given that the carrier frequency is correctly de- tected. When the carrier frequency is detected correctly, for which the prob— ability is (1— P634 D F H (713%)), the probability of bit error can be calcu- lated based on the BER of coherently detected M-ary QAM, given by P61 2 (0) E E N BS EM Pe,MQAM 780— . Here, N3 = W785. 71 Type II error: bit is in error when the carrier frequency is not correctly detected. When the carrier frequency is not correctly detected, for which the probability is 13(6))! D F H (73%), it is reasonable to assume that probability of bit error is ii) Average BER calculation based on majority voting: In MDF H, each QAM sym- r bol is transmitted through N), hops. As a result, an error in a particular bit 1 location is caused by at least [I—VQb-l unsuccessful recovery, where [2:] denotes the smallest integer greater than or equal to 12:. Let Peg, i = 0,1,--- ,Nh, be the conditional probability of bit error given that i out of N), carrier frequencies are L not correctly detected (i.e, N), —i carrier frequencies are correctly detected). Let j denote the number of unsuccessful bit recovery, Eb P6»: (TVS) Nh = Z Prob{errors in j out of N}, h0ps | i carriers are wrong} , N J=f—2b‘l Nh J' = Z Z Prob{k type I and j — k type II errors i carriers are wrong} j=rN7h1k=° Nh j = Z ZPB(k,P.1.Nh — wage — Item, (3.31) . N k=0 J=I—2b‘l .9. n :1: n—a: _ n! a: 1_ n—x H where P301219, n) — (P) (1 -p) — m (p) ( p) - ere a: n we adopt the convention = 0 when n < .73. 72 Taking the effect of the majority voting into consideration, the error probability for the ordinary bits, Page! D F H’ is given by 19(0) fl e,MDFH N0 Nh = Z Prob{bit is in error | i carriers are wrong}Prob{i carriers are wrong} i=0 Nh = 2126,, (fifi) PB“, PifllIDFH’ Nh)- (332) z: To determine the bit error probability for the ordinary bits in E—MDF H, we pro— ceed in a similar manner as in MDF H, except for the use of different error prob- abilities in the detection of carrier frequency. More specifically, lower and upper bounds of the probability of bit error for the ordinary bits can be obtained by sub- stituting 113(32ij DFH (7’53) and 115%ij DFH (7%) for P353413” (7%) in (3.32), respectively. Overall BER for MDFH The overall BER of the MDFH scheme is calculated as the linear combination of P:%_ M D F H and P:%_ M D F H based on the number of carrier bits and the number of ordinary bits in each block, P _E_b) : Nh(Bc — 39) 13(6) (_E_b) e,E—MDFH N0 N,,(Bc _ 39) + 33 e,E—MDFH N0 33 (0) (Eb) + P -— . 3.33 Nll(BC - Bg) + BS 8,E—MDFH N0 ( ) 73 _m’l' Example 3.1 - BER Performance of E-MDFH Assume the number of avail- able carriers NC = 64, and 16-QAM is adopted for baseband modulation in an E- MDFH system. Each 16-QAM symbol is transmitted via three hops. Four carriers are simultaneously used at each h0p. In other words, BC = 6, B3 = 4, N}, = 3, B9 = 2. Figure 3.8 presents BER performance of the system. Non-uniformity can be ob- served in the carrier bits and the ordinary bits. In fact, the BER of carrier bits is worse than that of ordinary bits. The underlying argument is that the ordinary bits are transmitted through multiple hops, therefore, the BER can be substantially im- proved through majority voting. Comparison of the experimental results with the theoretical lower and upper bounds is also provided. + Experimental BER for carrier bits (:1 \ 10'10 — —0- Theoretical BER lower bound for carrier bits - , - . - - f »\- \- . , - - —Q— Theoretical BER upper bound for carrier bits } \ \ —*—— Experimental BER for ordinary bits i 10’12 - - B - Theoretical BER lower bound for ordinary bits - . - ~ ~ 1 ----- X}- — E1 ~ Theoretical BER upper bound for ordinary bits —9— The overall BER _ 7 8 9 10 11 12 13 14 15 -14 10 Figure 3.8. BER comparison of the carrier bits and the ordinary bits in E-MDFH: Nh=3,Nc=64(Bc=6), Bs=4,Bg=2. 74 3.3.6 Spectral Efficiency Analysis We compare the spectral efficiency of the proposed E-MDFH scheme with that of the conventional FH scheme. Single-user Case There is only one user in both systems and no collisions need to be taken into con- sideration. Recall that T, denotes the symbol period and T h the hopping duration, N h = Ts/Th (N), Z 1) is the number of hops per symbol period. For fair comparison, we assume that both systems have the same symbol period T3, the same number of hops per symbol, N h, and use constellation(s) of the same size M, i.e., the number of bits per symbol is 8,, = log2 M. Let Rs 9- 1/T3 be the symbol rate. Accordingly, the bit rate of the conventional FH can be expressed as: 13be = BSRS bits/second (3.34) Recall that the data rate of E—MDFH 121,5;me is [N,,(Bc — 39) + 3,1239 bits every symbol period. That is, Rb,E_MDFH = [Nh(BC — By) '1’ 831289 R3 bitS/Second. (3.35) Given N h: BC, BS, an interesting question is to find the optimal By that maximizes dR _ Rb,E—MDFH- By solving b,Edél;IDFH = 0, we have Bg = BC + 7%:- — Ir‘f'?‘ Note that 39 must be an integer and By E [0, BC]. We have the following results: P ’t' 32LtBi-é OB B 1 dBTé '{B[B+ rop08110n . e g—max{,[c+N:—mj}an g—mm c, c 7%;- — $1}, where [at] denotes the largest integer less than or equal to x and [as] the 75 smallest integer greater than or equal to 1:. The optimal value of 39, denoted by 3*, that maximizes the throughput of the E-MDFH is given by BJ- N B—B-L 329 T 33 = [Nh(Bc—BJ)+le2B-9 (3.36) 3;, otherwise. Given that the total bandwidth WB = m%, where CO is a constant, the spectral efficiency (in bits / second / Hz) of the conventional fast FH and E—MDFH are given by Rb PH 83 = _, = _, 3.37 77FH WB CONcNh ( ) * Rb,E—MDFH [Nthc - 33) + 331239 UE—MDFH = WB = CONcNh (3-38) It is obvious that we always have UE— M DFH > 77FH- That is, E-MDFH is always much more efficient than the conventional fast FH scheme. Example 3.2 - Single-user case Assume the number of available channels is NC = 64, and 16—QAM modulation is adopted for both MDFH and the conventional FH systems. That is, BC = 6 and BS = 4. The BER performance with respect to three different hop rates, i.e., N h = 3, 5, 7, is independently measured for both systems, and the results are depicted in Figure 3.9. As can be seen, the MDFH system outperforms the PH system with big margins. We further compare the BER performances of the carrier bits and the ordinary bits in MDFH, as shown in Figure 3.10. It can be seen that there is almost a perfect 76 ............... a) *5 .......................................................... a: E §§§§€i§§§§§§§555 3:: ”J ...................... . ............ ' 9* m .—*_.Nh=3. conventional FH .5 10 ~ 1—0— Nh=3, proposed MDFH§§== + Nh=5. conventional FH 3 3 .5 _ _e_ Nh=5, proposed MDFH . ‘ _ . 10 Z 2 . . _ at _ Nh=7, conventional FH _ e _ Nh=7, proposed MDFH ‘ ' " 3 -7 . , l 10 L I I I I I I l 5 6 7 8 9 10 11 12 13 14 Eb/N0 (dB) Figure 3.9. BER comparison of the conventional FH and the proposed E—MDFH in the single-user case: NC = 64 (BC = 6), 3,, = 4, B9 = 0. 77 match between the simulation results and the theoretical results derived in (3.22) & (3.32). Moreover, it can be observed that the BER of ordinary bits is much better than that of carrier bits, since the same ordinary, bits are transmitted via multiple hops, and the BER is therefore substantially improved through majority voting even if certain carrier frequencies are not correctly detected. Bit Error Rate 10-8 f —+— Experimental BER for carrier bits \ i -— e — Theoretical BER for carrier bits ; El —x— Experimental BER for ordinary bits f 3 \ _10 - B - Theoretical BER for ordinary bits 5 6 7 8 9 1o 11 12 13 14 Eb/N0(dB) 10 Figure 3.10. BER comparison of the carrier bits and the ordinary bits in E—MDFH: Nh=3, NC=64 (Bc:6), 83:4, 89:0. Multiple-user Case Next, we explore the more general case where there are multiple users in both systems. Consider a conventional fast FH system with Nu(> 1) users, each transmitting 2BC-ary MFSK signals over NC frequencies. At the receiver, after de-hopping, each user creates 78 a 230 x N), decision table. For i = 1, - - - ,2BC andj = 1, - . - ,Nh, if the receiver decides a transmission is present on the ith carrier frequency during the j th hop duration, that is, if the output of the corresponding envelope detector exceeds some threshold, then the ith row and jth column of the decision table is filled, otherwise, it is left as blank. [73,82] Note that in the conventional F HMA systems, different users hops in an indepen- dent manner, any one of the 2B6 — 1 carrier frequencies not occupied by the desired user may be filled incorrectly as a result of a tone transmitted by an interfering user. This event, known as insertion, occurs with probability p = 1 — (1— 5113;)Nu_1. Moreover, additive noise may also result in insertions to the decision table. As a result, the overall insertion probability P; is given by [73] E P; = p + (1 — p)e—027132N3, (3.39) where 0 is the normalized threshold. On the other hand, because the interference may cause the decision statistic to fall below the threshold, a tone from the desire user may not appear among the receiver’s positive decisions, resulting in a deletion in the decision matrix. The probability that a deletion occurs, denoted by PD, is given by [73] (3.40) P =— 1—— 1— ——,6 — D 3” 3)[ Q( NhNO NhNO where Q(:r, y) is the Marcum Q-function [83]. In the ideal case, the row of the decision table, corresponding to the symbol trans- mitted by the desired user, will be fully filled. If it is the only full row, then the decoding is perfect. However, due to the presence of multiple—access interference and 79 additive white noise, insertion as well as deletion in the receive matrix may occur. When the filled entries in another row is more than that of the desired row, a symbol error occurs. When two or more rows in the receive matrix have the same number of entries, random decision (based on the toss of a coin) has to be used for MFSK symbol detection. Let Pd(i) denote the probability that i entries are filled on the desired row of the receive matrix, and P0( j ) the probability that j entries are filled on any other row, then N . _- N wehavedeb'): .- (1-Pp)‘P)§V" ‘. and Pa(j)= c i j (1 — PnNh-J'P}. Let P8921! M A denote the bit-error-rate of the desired user in the conventional FHMA system. Let Nw be the total number of undesired rows, then Nw = 230 — 1. Let jn be the number of filled entries in an undesired row fn, define jg é max{jn}, where the maximum operation is taken over all the undesired rows. As can be seen, a detection error occurs whenever jg Z i. Since the probability that jn = jg occurs in two or more undesired rows is very low, here we only consider the case where only one undesired row has jg entries. As a result, Pg? H M A can be approximated as PM ~ 2086-1) N'” P b' ' 1P b '—' 341 e,FHMA ~ 273;: 1 (1‘0{J>1}+§r0{J—1}). (-) 2‘36"” B N” .H . 1N" . . = 23...,” ._,) ZPoPdw , (3.43) j=1 i=0 j=1 where the factor of % is the probability that the fair coin toss favors the wrong decision rather than the correct one. 80 For the proposed E-MDF H scheme, there is no multiple-access interference, there- fore, the average BER in (3.33) is directly applicable to the multiuser case. From the spectral efficiency perspective, we need to compare the total information bits allowed to be transmitted under the same BER and bandwidth requirements (i.e., the same hop rate). As it is not easy to derive an explicit expression of the maximum date rate in terms of BER for both conventional FHMA and E—MDFH systems, we illustrate the system performance through the following numerical example. Example 3.3 - Multiple-user case Assume NC = 64 (i.e., BC = 6), N), = 5, B, = 4, B9 = 2, and the required BER is 10’4. Consider the transmission over one symbol period. From Figure 3.11(a), it can be seen that the proposed E—MDFH scheme can achieve the desired BER at £3 = 13.6dB. For clarity, this point is marked by a black '*’ in two figures. During one symbol period, the total number of transmitted information bits in E—MDFH is [Nh(Bc — By) + Bs]2Bg = 4(5 . 4 + 4) = 96. Figure 3.11(b) depicts the BER as a function of £3 for Nu = 2, - .. ,7. In each case, the threshold 9 is optimized to minimize the BER. It can be observed that the conventional FHMA system can only accommodate up to 5 users at 715% = 13.6dB, in order to achieve BER = 10-4. Therefore, during one symbol period, the FH system can transmit at most NuBc = 5 - 6 = 30 bits. In this case, E—MDFH achieves an increase of 220% in spectral efficiency. Simulations are also carried out for N}, = 3 and N}, = 7, while keeping all the other parameters unchanged. The overall results are listed in Table 3.1. In E-MDFH, the required BER for the six cases can be obtained at 7% equal to 11.9dB, 13.2dB, 13.6dB, 14.5dB, 13.8dB, 14.7dB, respectively. Subject to the same BER and bit-level 81 (a) E-MDFH 10'2 » 0 0 E E “ 10“» . g E a s s 1 0-6 * 1 e 10 1‘2 144 Eb/No (dB) (b) conventional fast FH 3 1o 12 Eb/No (dB) Figure 3.11. Performance comparison of E-MDF H and conventional FH in the multi- user case: N), = 5, NC = 64 (BC = 6), 8,, = 4, 39 = 2. SN R, the conventional FHMA system can support at most 5, 3, 5, 4, 7, 5 users for the six cases, respectively. As can be seen, E—MDFH can achieve a spectral efficiency up to 4 times higher than that of the conventional FHMA system. Table 3.1. Comparison of information bit rate between the conventional fast FH system and the proposed E-MDFH scheme for various hop rates: NC = 64 (BC = 6), 3,, = 4, By = 2. Case 1 Case 2 Case 3 Case 4 Case 5 Case 6 N), 3 3 5 5 7 7 Required BER 10-3 10*4 10-4 10-5 10-4 10-5 Conventional FH (bits/T3) 30 18 30 24 42 30 E—MDFH (bits/Ts) 64 64 96 96 128 128 The above in-depth quantitative performance analysis and simulation examples demonstrate the superior performance of MDFH in terms of spectral efficiency. 82 3.4 Collision-Free Frequency Hopping In this section, a highly efficient collision-free frequency hopping scheme is presented. The. core components of the CFFH system is the OFDM framework and the dynamic subcarrier assignment algorithm. Although frequency hopping has been used to enrich the frequency diversity in OF DM systems [84,85], we consider the contrary: how to increase the information capacity of FH systems by exploiting the OFDM structure. First, we describe the signal transmission and detection scheme for each individual user. At each symbol period, each user transmits on specific subcarrier(s), based on the user’s information rate requirement and total load of the system. Then, an AES based secure subcarrier assignment algorithm is proposed to ensure that: (i) Each user hops to a different set of subcarriers in a pseudo—random manner at the beginning of each hopping period; (ii) At each hopping period, different users always transmit on non-overlapping sets of subcarriers, and hence are collision-free. We would like to emphasize that while it is possible to design collision-free fre- quency hopping system based on non-OFDM frameworks, the utilization of OFDM in the CFFH scheme has unique advantages which cannot be surpassed by other systems. 3.4.1 Signal Transmission and Detection Consider a system with Nu users, utilizing an OFDM system with NC subcarriers, {f1,. - ° ,ch}. At each OFDM symbol period, each user is assigned a specific subset of the total available subcarriers. Assuming that at the nth symbol, user i has been assigned a set of subcarriers Cn,i = {fW'l’ - -- , f,,,,-Ni}, that is, user i will transmit and only transmit on these subcarriers. Here, N,- is the total number of subcarriers 83 assigned to user i. Note that for any n, Cmiflcm =10, v iyé j. (3.44) That is, users transmit on non-overlapping subcarriers. In other words, there is no collision between the users. Ideally, for full capacity of the OFDM system, Nu U C...- = {fla - -- m}. (3.45) i=1 For the ith user, if N,- > 1, then the ith user’s information symbols are first fed into a serial-to-parallel converter. Suppose that at the nth symbol period, the ith user transmits the information symbols {um “(1') Ni} (which are generally QAM "1,... symbols) through the subcarrier set Cn,i = {fn,,-l, - -- , fnJ-N} User i’s transmitted 1 signal at the nth OFDM symbol can then be written as: n(t) nl€J27rf1l’ilt- (346) g: TIMZ Note that each user transmits zeros on subcarriers which are not assigned to him/ her, and hence ensures collision-free transmission among different users. At the receiver, the received signal is a superposition of the signals transmitted from all users )=Zr,(, )(t) )(+wt (3.47) where rifle) = 4931* m(t). (3.48) and w(t) is the additive noise. In (3.48), h,(t) is the channel impulse response corre- 84 sponding to the ith user. Note that in OFDM systems, guard intervals are inserted between symbols to eliminate inter-symbol interference, so it is reasonable to study the signals in a symbol-by-symbol manner. Equations (3.46)~(3.48) represent an uplink system. The downlink system can be formulated in a similar manner. As is well known, the OFDM transmitter and receiver are implemented through IFFT and F FT, respectively. Denote the N x 1 symbol vector corresponding to the ith user’s nth OFDM symbol as us?) , we have 1159(1) = 0’ ifl¢{2'1,---,i1v,.} (3.49) uff), ifl€{i1,---,z’Ni}. Let T3 denote the OF DM symbol period. The discrete form of the transmitted signal 55: )(t) (sampled at £7763) is 35.3) = FHulf), (3.50) where F is the F FT matrix defined as P - V130 ”gm—1) 1 F:— I , ,—N . ”(IN—DO VISIN—IXN—l) with V13,“ = e—j27mk/N , the superscript H denotes complex conjugate transpose. As we only consider one OFDM symbol at a time, for notation simplification, here we omit the insertion of the guard interval (i.e., the cyclic prefix which is used to ensure that there is no inter-symbol interference between two successive OFDM symbols). Let h,- = [ht-(1), - -- ,hi(N)] be the discrete channel impulse response vector, and 85 let H,- = th- (3.51) be the Fourier transform of hi. Then after FFT, the received signal corresponding to user 2' is 2%) = qu’65 570], [566 b67 b71l, 1 [1996 597 13101], (3-58) [1’97 598 him], [598 (399 19102], [5112 17113 5116], (3-59) [b113 19114 (>115 b116l: , [5120 b121 b122 b123], (3-60) [5121 5122 13123], [(1122 (>123 5124], [19123 (>124 [>125], [5124 19125 5126]»(3-61) [5125 (3126], [b126 (9127], (3-62) [51281- (3-63) There are 64 7—bit groups in (3.57), 32 6-bit groups in (3.58), 16 5-bit groups in 88 (3.59), 8 4-bit groups in (3.60), 4 3-bit groups in (3.61), 2 2-bit groups in (3.62) and 1 1-bit group in (3.63). Each binary vector is then converted to a decimal integer with the first or last element of the vector considered to be the most significant alternately, denoted by Q» for 2' = 1, 2, - ~ ,127. 4. Initialize two sets of integers as N = {1, 2, - - - , 128} and I = d). Randomly take one entry out of N at a time and put it successively into I as an index. Since one index is selected at random from N without replacement (meaning without repetition), after each update, the size of N is decreased by one, while that of 1' is increased by one. Because the first 64 indices are chosen from N with size of greater than 64, seven bits are required to uniquely represent the position of each selected index in N, which is the reason why 64 7-bit vectors are formed as in (3.57). Justification for partition of [b1 b2 5128] corresponding to equations (3.58) ~ (3.63) may be deduced by analogy. From a mathematical point of view, the random assignment algorithm can be achieved as follows: 1(2) = N(<,-%(129 — 2') + 1), for 2' = 1, 2, . -- ,127, (3.64) where the function 23%;; returns the remainder after a: is divided by y. After the procedure in (3.64) is performed successively, the size of I becomes 127 and N only has one element left. Let 1(128) = N (1), then a sophisticatedly designed random index vector 1' of length 128 is obtained. 5. Recall that at each OFDM symbol, N,- subcarriers are assigned to user 2'. We 89 now assign the subcarriers with indices {I (1),]: (2), - - . ,I(N1)} to user 1, assign the subcarriers with indices {I(N1 + 1),I(N1 + 2), - -- ,I(N1 + N2)} to user 2, and so on. 3.4.3 Performance Analysis in the Presence of Fixed-Band Jamming Suppose that the total number of available subcarriers is NC and the ith user is assigned N,- carriers. The jammer intentionally interferes N j fixed subcarriers. Without loss of generality, we assume N,- 2 N j. If subcarriers are allocated to each user randomly, then for the ith user, the probability that k out of N,- selected subcarriers are jammed is given by Nj N—Nj k N-—k P609) = z , fork=O,---,Nj. N Ni In particular, the probability that none of N,- subcarriers are jammed is 0) (N—MMN—Mfl MW—M-Mfl 90 an) 6%) BW) Consequently, we have the probability that at least one of N,- selected subcarriers are jammed: 1 — Pom). If no channel coding is employed, then the system performance can be measured independently for each subchannel and the probability of bit error is determined by the interference over the channel. If the BER is modeled as a function of the signal- to-interference—plus—noise ratio, then the overall system performance for the ith user can be obtained ”1' Pé’“)[kPe( k=0 N,- . JSR - SNR PC: SNR+Nj-JSR)+( Ni.- N,- — k)Pe(SNR)], (3.68) where SN R is defined as the ratio of the average signal power to the noise power, J SR represents the ratio of the total jamming power to the average signal power, and the jammer uniformly distributes its available power over N j channels. Taking channel coding into consideration, even if signals are transmitted over the jammed subchannels, it is still possible to recover the corrupted information due to the strong error-correcting capability of channel codes. All things considered, we have to utilize the average SIN R for the decoding process. Hence, the BER performance is approximately given by N . J __ (k) N,~Nj-JSR-SNR 369 P612136 Pe(k-SNR+N,~N,~JSR ' (' ) In both cases, there exists a lower bound for the overall BER, that is, 75; > Pe(SNR), (3.70) 91 .. '_' can” . where Pe(S N R) denotes the bit error rate of the system at a specific SN R level over an AWGN channel. 3.4.4 Simulation Examples In the following, numerical examples are provided to illustrate the advantages of the CFFH scheme over the conventional FH systems. Example 3.4 - BER performance and spectral efficiency Assume that the total number of available channels (subcarriers) is NC = 128. Consider two systems: (i) A conventional FHMA system with Nu = 8 users, each using 4-FSK modulation; (ii) A CFFH system with 8 users, each transmitting QPSK symbols. The BER comparison of the two systems over AWGN channels is shown in Figure 3.12. As can be seen, the proposed CFFH system delivers excellent results. The conventional FHMA system, on the other hand, is severely limited by the collision effect, and does not really work. And it should be noted that in this example, the spectral efficiency of the CFFH system is 16 times that of the conventional FHMA system. Essentially, CFFH has the same spectral efficiency as the OFDM system, which is much higher than the conventional FHMA system. Example 3.5 - Jamming resistance In the example, the total number of avail- able subcarriers is NC = 256 and the number of users is Nu = 16. Each user is assigned 16 subcarriers. Consider the performance of three systems under hostile jamming: (i) A conventional OFDMA system where each user transmits on 16 fixed subcarriers; (ii) A CFFH system with 16 subcarriers allocated to each user pseudo-randomly based 92 ‘24.. . Bit Error Rate 8 10-10 _ . 10'12 ..................................................................... - 10"14 l ......................................... .. --8— Proposed CFF H 16 —>*— Conventional FH . 3 10‘ . i 0 5 10 15 Eb/No (dB) Figure 3.12. BER comparison of CFFH and conventional FHMA system over AWGN channels: NC = 128, Nu = 8. 93 on the secure subcarrier assignment algorithm. (iii) A CF FH system with the knowl- edge of which subcarriers being jammed, where users are able to choose channels for information transmission to avoid the hostile jamming. The third case is essentially equivalent to a jamming-free CFFH or OFDMA system. We assume that the jammer intentionally interferes 8 subcarriers, which are coincidentally used by a user in system (i). Eb / P J is defined as the ratio of the average bit-level energy to the total jamming power. SNR is defined as the ratio of the average signal power to the noise power, and is fixed at 7 dB in the simulation. At the transmitter, a rate-r) turbo code is utilized for forward error control. The generation matrix of the constituent code is given by [1, w], where (7)06tal and (5)0ctal are the feedback and feedforward polynomials with memory length 2, respec- tively. The block length is 960. After encoding, 1920 bits are mapped into 16—QAM symbols and transmitted over the selected carriers. At the receiver, tentative soft deci- sions are made by 16-QAM demodulation, and then the resulting log-likelihood ratios (LLRs) of the code bits are fed into a turbo decoder. There is no iteration between the demodulator and the turbo decoder. The decoding algorithm is the canonical log- MAP [87]. The number of decoding iterations is 5, and no early termination scheme is applied. The BER comparison of three systems over the same AWGN channel is shown in Figure 3.13. As can be seen, benefited from the jamming resistance property of the frequency hopping system, the proposed CF FH delivers much better performance under hostile jamming than the conventional OF DMA system with fixed carrier allo- cation. The performance of the conventional OFDMA system is severely limited by the jamming interference, even if a powerful error-correcting code (e.g., turbo coding) is employed. System (iii) is essentially jamming-free and its BER performance serves 94 as the lower bound in this example. o 10 .................................. r ................................... 5::333333233323222223322332 +0FDMAwithiammin9 5: , .......................... —~9— CFFH with jamming .. -—-- £3— OFDMA or CFFH with no jamming " Bit Error Rate -15 -1o -5 Eb/PJ (dB) Figure 3.13. BER comparison for three systems under hostile jamming: NC = 256, Nu = 16, SNR = 7dB. 3.5 Summary In this chapter, we presented the design and in—depth analysis of two spectrally-efficient spread spectrum schemes. First, message-driven frequency hopping was proposed. By 95 transmitting a large portion of the information through message-driven hopping fre- quency control, spectral efficiency of the FH systems can be improved by multiple times. It turns out that the enhanced MDFH can further increase the spectral effi- ciency by allowing simultaneous transmission over multiple frequency bands, and can readily be extended to a collision-free multiple access scheme. In the meantime, in- formation confidentiality was reinforced since the message-driven hopping pattern is totally unpredictable. Secondly, the collision-free frequency hopping scheme was de- veloped based on the OFDM framework and the AES-controlled dynamic subcarrier index assignment algorithm. It is a highly efficient secure communication interface from a cross-layer perspective, since users always transmit on non-overlapping sets of subcarriers in multiple access environment. While keeping the inherent anti-jamming feature of the PH system, CFFH can relax the strict synchronization requirement suf- fered by the conventional FH systems. Our quantitative performance analysis and simulation examples demonstrated the superior performance of the proposed schemes. 96 CHAPTER 4 PHY Layer Built-in Security Analysis and Enhancement Algorithms This chapter considers the enhancement of the PHY layer built-in information con- fidentiality of wireless systems by integrating cryptographic techniques into the transceiver design. First, security weakness of the operational and proposed CDMA airlink interfaces is analyzed. Secondly, based on AES, secure scrambling is designed to strengthen the physical layer built-in security of CDMA systems through the en- crypted long code sequence. Thirdly, motivated by the fact that chips spread from one symbol still cluster together after scrambling and are fragile to deep fading and / or strong burst errors, a chip—level secure interleaving procedure is introduced as a sub- stitution of securing scrambling to further protect wireless transmission from severe channel conditions. Security and performance analyses demonstrate that while pro- viding significantly improved information confidentiality, CDMA systems with secure scrambling/ secure interleaving have comparable computational complexity with that of conventionally scrambled systems. Simulation examples are provided to illustrate the robustness of CDMA systems with secure interleaving in adverse environments. 97 Moreover, possible extension of secure scrambling and secure interleaving to general wireless systems is investigated. 4. 1 Introduction Spread spectrum wireless system was historically developed for secure communica- tion and military use. In spread spectrum systems, each user is assigned a specific spreading sequence to modulate its message signal. The spreading process increases the bandwidth of the message signal by a factor N, known as spreading factor or the processing gain, and meanwhile reduces the power spectrum density of the signal also by a factor N. With large bandwidth and low power spectrum density, spread spectrum signals are resistant to malicious narrow-band jamming and can easily be concealed within the noise floor, preventing from being detected by an unauthorized person. Moreover, the message signal cannot readily be recovered unless the spreading sequence is known, which makes it difficult for an unauthorized person to intercept the signal. It is also known as the physical layer built-in security feature of spread spectrum systems. Due to relatively high spectral efficiency and simplicity in system planning [63, 64], spread spectrum is now finding widespread civilian and commercial applications such as cellular phones, personal communications and position location [88]. From multiple access system design point of view, since all users in a spread spectrum system are allowed to transmit through the same frequency band simultaneously, each user has a unique spreading code, which is used at the receiver end to perform multiuser signal separation and detection, spread spectrum system is also termed as code-division multiple access system. As is well known, CDMA is used in the US digital cellular 98 standard IS-95 [89] and has been identified as the major modulation technique for third generation (3G) wireless communications and beyond. Relying on the long pseudo-random spreading sequence generator, the operational CDMA system (IS—95) and the proposed 3GPP UMTS system can provide a near- satisfactory physical layer built-in security solution to voice-centric wireless communi- cations, which generally last only a. short period of time. However, the security features provided by these systems are far from adequate and being acceptable when used for wireless data communications. In [90] and [91], the physical layer security weakness of the operational IS-95 CDMA airlink interface was analyzed. It was pointed out that as long as up to 42 contiguous long code sequence bits are intercepted, the whole long code sequence can be regenerated according to the Berlekamp—Massey algorithm [92]. Once the long code sequence is recovered, the desired user’s signal can be recovered through various signal separation and extraction algorithms, see [93-95] for example. Instead of using the conventional scrambling scheme as in IS—95 or 3GPP UMTS, encrypted long code based on AES is proposed to be used in the scrambling procass. Next, motivated by concern that chips spread from one symbol still cluster together after spreading and scrambling and are thus fragile to severe fading effects or burst errors, in which the whole symbol may be lost, we consider using chip-level secure interleaving to replace secure scrambling. Ensured by AES, the proposed schemes can improve the physical layer built-in security of CDMA systems significantly. Per- formance analysis demonstrates that CDMA systems with secure scrambling have comparable computational complexity and system performance with that of the IS-95 systems, and CDMA systems with secure interleaving gain advantages of combating adverse transmission environments. Moreover, by scrambling the training sequence independently with a different scrambling sequence, both information privacy and 99 system performance can be further improved. Both secure scrambling and secure interleaving can be extended to wireless systems other than DS-CDMA in multiple ways. As a start point, secure interleaving is integrated with the commonly deployed F EC (forward error control) process so that strong information confidentiality can be achieved through secure channel coding. The simplicity and effectiveness of the proposed schemes make them particularly attractive for 3G systems and beyond. The rest of the chapter is organized as follows. Section 4.2 gives a quick review of the conventional DS-CDMA system as well as the built-in security features. In Section 4.3, security weakness of the existing CDMA airlink interfaces is investigated. Section 4.4 introduces two security enhancement approaches based on the AES algorithm, and the relationship between scrambling and interleaving is discussed. Security of the proposed schemes is analyzed in Section 4.5. Comparison of computational complexity and system performance are provided in Section 4.6. Discussion on extension of the developed methods is presented in Section 4.7 and we conclude in Section 4.8. 4.2 System Description In the operational and proposed DS—CDMA systems, as shown in Figure 4.1, each user’s signal is first spread using a code sequence (known as channelization code) spanning over just one symbol or multiple symbols. The spread signal is then fur- ther scrambled using a pseudo-random sequence, to randomize the interference and meanwhile make it difficult to intercept and detect the transmitted signal. Consider a DS-CDMA system with Na users and K receive antennas. Assuming the processing gain is N, that is, there are N chips per symbol. Let uJ-(k) (j = 1, - -- , Nu) 100 noise wi(n) ul(k) ‘ Spreading or x101) Pseudo-randomly y-l(n) 0‘33““ é 1"(i)( n) User j's channehzahon Spread scrambling Scrambled gj (l) J symbol signal signal Figure 4.1. Block diagram of a long code DS—CDMA system. denote the jth user’s kth symbol. Without loss of generality, let cj= [cj(0), cj(1),--- ,cJ-(N — 1)] (4.1) denote the jth user’s channelization code or spreading code. The spread chip-rate signal can be expressed as —2 u (n — kN). (4-2) k=—oo The successive scrambling process is achieved by where dj (n) is the jth user’s chip-rate scrambling sequence. Let {gJ(-i)(l)}ll’=—01 denote the (chip-rate) channel impulse response from the j th user to the ith antenna, the received chip-rate signal at the ith antenna (i = 1, 2, - -- , K) can be written as Nu L—l =ZZg,’>’(lyJ(n—l)+w. 51 g 32 , 33 S40 , S41 S42 Modulo-Z addition LSB * M88 42// Long Code Mask Long Code Sequence Figure 4.2. Long code generator in IS-95 systems. [31(t),32(t), - -- ,342(t)] denote the state of the LF SR at time instance t. The long code sequence C(t) at time t can thus be represented as C(t) = m181(t) + m282(t) + ' " + 772428420), (4-6) where the additions are modulo-2 additions. As is well known, for a sequence generated from an n—stage linear feedback shift register, if an eavesdropper can intercept a 2n—bit sequence segment, then the char- acteristic polynomial and the entire sequence can be reconstructed according to the Berlekamp-Massey algorithm [92]. This leaves an impression that the maximum com- plexity to recover the long code sequence C(t) is 0(284). However, for IS-95, since the characteristic polynomial is known to the public, an eavesdropper only needs to obtain 42 bits of the long code sequence to determine the entire sequence. That is, the maximum complexity to recover the long code sequence C(t) is only 0(242). In fact, since 31 (t), s2(t), - - - ,342(t) are the outputs of the same LFSR, they should 103 all be the same except for a phase difference, i.e., 8420) = 341(t - 1) = = 81(t - 41)- (47) Let a = [a1, a2, - - - ,a42] denote of the coefficient vector of the characteristic polyno- mial in (4.5), then it follows from (4.7) that 31(t) = a131(t—1)+ a232(t — 1) + - - . + (142842(t— 1) = 0181(t — 1) + a231(t - 2) + - - - + (1428105 — 42). (4.8) si(t) = 31(t — i + 1), Vi E [2, 42]. (4.9) After some manipulations on (4.8) and (4.9), we have, for i = 1, . - . , 42, 5,-(t) = als,(t — 1) + agsi(t — 2) + . - - + a423i(t — 42). (4.10) Substituting (4.10) into (4.6), we have 42 C(t) = medt) i=1 42 42 = 2 mi 2 ajSz'U — 1) i=1 j=1 42 42 = Z aj (Z mi5i(t - jl) j=1 i=1 42 = Z a.jc(t — j). j=1 104 Define — a1 1 0 0 " a2 0 1 0 A: s s s 2 , (4.11) an 0 0 1 _ a42 0 0 0 . then it follows that [c(t),c(t—1),--- ,c(t — 41)] = [c(t — 1), c(t — 2), - -- ,c(t — 42)]A. (4.12) Let c(t) = [c(t),c(t — 1), - -- ,c(t — 41)], then for any n 2 t, from (4.12) we have c(n) = c(t)A”"’. (4.13) Thus, as long as c(t) for a time instance t is known, the entire long code sequence can be recovered. In other words, as long as an eavesdropper can intercept/ recover up to 42 contiguous long code sequence bits, the whole long code sequence can be regenerated. Therefore, the long code sequence of IS-95 is vulnerable under ciphertext- only attacks as the maximum complexity to recover it is only 0(242) [91]. 4.3.2 Recovery of the Long Code Sequences in 3GPP UMTS Systems In the 3GPP UMTS standard, Gold codes (1 sequence and Q sequence) generated from two generator polynomials of degree 18 are used as scrambling codes, as shown in Figure 4.3. 105 Figure 4.3. Scrambling sequence generator in 3GPP UMTS systems. Denote the states for the two LFSRs at time instance t as r(t) = [717(t),7"16(t), ' " ,T1(t),r0(t)] and s(t) = [317(t),316(t), - .. ,sl(t), 30(t)], where m(t) = r7(t-1)+To(t-1), ll 317(t) 810(t — 1) + 37(t -- 1) + 85(t — 1) + 30(t — I). Then at time instance t, sequence 1 can be written as 1(t) = m(t — 1) + 30(t — 1), (4.14) while sequence Q can be expressed as [80] 17 17 Q(t) = 204720 — 1) + 2548403 - 1), i=0 i=0 where a,- and b,- are either 0 or 1 as shown in Figure 4.3. Note that m(t) = r1(t - 1) = = r17(t — 17) and 30(t) = 31(t _ 1) = .-= 106 317(t — 17), we have 17 17 Q(t) = Zama + i — 1) + Zbisou + i — 1). (4.15) i=0 i=0 From (4.14) and (4.15), it follows that the maximum complexity to recover the scram- bling code of the 3GPP UMTS system based on ciphertext-only attack is 0(236). This implies that the physical layer built-in security of the 3GPP UMTS system is actually weaker than that of the IS—95 system. 4.3.3 Recovery of the Desired Information Once the long code sequence is recovered, the desired user’s signal can be recovered through signal separation and extraction techniques. If the training sequence is known, simple receivers, for example, the Rake receiver, can be used to extract the desired user’s signal. For secure transmission, it is reasonable to assume that the training sequence of the desired user is unknown, however, it is still possible to recover the signal through blind multiuser detection and signal separation [93,94,96—98], which rely only on the statistics of the input signals and the received signals, but independent of the training sequence. When taking security into consideration, blind signal detection turns out to be a double-edged sword as it can also be used by malicious users to obtain the desired information. Recently, blind multiuser detection methods targeting at long-code CDMA sys- tems have been proposed. Based on the channel model, existing blind algorithms can roughly be divided into three categories: (i) Symbol-by-symbol approaches, see [99—102] for example, in which channel estimation and equalization are carried out for each individually received symbol by taking instantaneous estimates of signal 107 statistics based on the sample values of each symbol. (ii) Frame-by—frame approaches, see [95, 103] for example. Algorithms in this category stack the total received signal corresponding to a whole frame or slot into a long vector, and formulate a determin- istic channel model. (iii) Chip-level equalization, see [104—108] and references therein. In this category, by taking chip-rate information as input, the time-varying effect of the pseudo-random sequence is absorbed into the input sequence, and chip—level equalization is performed as the receiver. All the existing work on blind detection reveals the vulnerability of long-code CDMA systems: recovery of the long code sequence largely implies immediate security compromise and the interception of the user’s data transmission. 4.4 Confidentiality Enhancement through Secure Scrambling and Secure Interleaving Having demonstrated the weakness of the stand-alone CDMA built-in security mech- anism, we plan to fundamentally strengthen the built-in security through design inte- gration with cryptographic techniques, while minimizing the changes required to the existing standards. More specifically, to reinforce information confidentiality, we pro- pose to enhance the physical layer built-in security by integrating the state-of-the-art cryptographic techniques into the physical layer transceiver design. We will focus our discussion on the IS-95 system as it has a stronger physical layer security and the results can be directly applied to 3GPP UMTS systems. 108 4.4.1 Security Scrambling Based on AES In the first stage, advanced cryptographic algorithms are incorporated into the scram- bling process of CDMA systems. Instead of using the pseudo-random sequences di- rectly as scrambling sequences, we encrypt them first with advanced cryptographic algorithms (e.g., ABS), and then use the encrypted sequences as the scrambling se- quences. As shown in Figure 4.4, the proposed secure scrambling is essentially a counter mode AES. In Figure 4.4, soslsgu- represents the output of the LFSR charac- terized by (4.5) as in the IS-95 system, K is the 128-bit common secret encryp- tion key shared between the base station and the mobile station (K can also be 192 bits or 256 bits, as specified by the AES algorithm), and M0,M1,-~ ,Mi de- note successive message blocks with size of 128 bits, d is the shift between the successive inputs to the AES engine. If the input to the i-th encryption block is 3t+id, 3t+1+id, - - - , 3t+127+id with initial delay t, then the input to the (i + 1)-th block is 3t+(i+1)d13t+1+(i+1)d2 - -- 13t+127+(i+1)d' The selection of d should maximize the diversity between different inputs to the AES engine, which can be achieved by re- 242 — 1 be relatively prime. In other words, d should not be divided by quiring d and 3, 7, 43 and 127. The secure scrambling process can be summarized as follows: 1. The base station and the mobile station share a common initial state for the LF SR and an L-bit (L = 128, 192 or 256) common secret encryption key K; 2. The long scrambling sequence is generated through encryption of a particular segment of the sequence generated from the LFSR using the shared secret key K; 109 X1*X2 X3-'X4-’X5 X6~X7 X35 X419X42 ...sss4s3szsl Al x"; 2} fly {fly HR‘ .de \JJ‘ J‘ MW \LJ‘ J‘ St+127St+126 St St+127+dSt+126+d St+d St+127+idSt+126+id St+id l e l ——> Encrypt ——~ Encrypt —N Encrypt M0 M1 Mi CO C 1 Ci Figure 4.4. Design of physical layer secure scrambling in DS-CDMA systems. 3. The scrambling process is realized by implementing the exclusive OR (XOR) operation between the scrambling sequence and the chip-rate spread signal. For the 3GPP system, secure scrambling can be performed in the same manner by applying AES to the I, Q scrambling sequences separately. As described in [109,110], the shared secret data between the mobile station and the base station can be updated from time to time. To prevent malicious key reload, the key update request can only be initiated from the base station. Note that after spreading and scrambling, chips spread from one symbol still clus- ter together, and could be fragile to deep fading or burst errors, in which the whole symbol may be lost. Interleaving is a widely used technique to randomize burst errors. In this following subsections, we first investigate the relationship between interleav- ing and scrambling, and then consider using chip-level secure interleaving to replace 110 scrambling. The purpose is to further protect wireless transmission from strong burst errors and severe fading while enhancing the security measure at the same time. 4.4.2 Relationship between Scrambling and Interleaving Interleaving is commonly used to obtain time diversity without adding any overhead. An interleaver 17 is a permutation i +—+ n(i) that changes the time order of an input data sequence. If the input data sequence is d = [d1 d2 - - - d N], then the interleaved data sequence is given by d7r = d - P, where P is a permutation matrix with a single one in each row and column, all other entries being zero. From a mathematical point of view, the process of chip-level interleaving in a DS-CDMA system with BPSK modulation can be represented by: yg=yj-cj,j=1,---,Nu, (4.16) where yj is the jth user’s chip sequence before interleaving, y; denotes the jth user’s interleaved chip sequence and “-” represents element-wise production. cj turns out to be a binary (:t 1) vector which can be viewed as a special scrambling sequence. That is, interleaving is a special case of scrambling. However, scrambling is not necessarily a case of interleaving, because scrambled chip sequence may not be permuted to the original chip sequence by simply arranging the time order of the scrambled sequence in all possible ways. If the interleaver is deep enough, the resulting cj will be a random sequence, which can scramble the spread data sequence so that the interference caused by multiple access can be effectively suppressed. That is, the major functionality of scrambling sequence can be retained by a random interleaver. 111 The advantage of an interleaver is to randomize the information sequence so that even if the successive data symbols undergo deep fading or strong burst noise, they will not possibly be corrupted at the same time. In fact, after interleaving, the corrupted chips will be uniformly distributed over several original bits so that each bit only suffers a small portion of loss and can still be correctly recovered. Therefore, chip- level interleaver can effectively combat deep fade with relatively long duration, such as more than half of the symbol period, in which case the scrambling process will most likely result in an error during signal detection. 4.4.3 System Model for DS-CDMA Systems with Chip-Level Interleaving Since interleaving can randomize the spread data sequence so as to suppress the in- terference like scrambling, we propose to use chip-level interleaving as a substitution of scrambling. Again consider a DS-CDMA system with Nu users, as shown in Figure 4.5. The chip-rate spread signal can be written as 00 $j(n) = Z uj(k)cJ-(n — kN). (4.17) k=—oo where uj(k) (j = 1, - . - ,Nu) denotes the jth user’s kth symbol, cj(n) is the jth user’s spreading code with processing gain N. The successive interleaving process is achieved by w(n) = 7rj(:vj (71)), (4-18) where 7rj represents a one-to-one mapping from :rj(n) to yj(n). 112 u] (k ) Spreading x1(n) Chip-Level yl(n) Multipath _’ ' with 01 Interleavmg Channel g1 noise '\ \ . n . uNu (ll Spreading x% (n) Chip-Level yM‘( I Multipath ——’[ ' with CNu Interleavmg 11 Channel gNu Channel Estimation “1(1) Despreading x1 (n) Chip-Level -1 J’1(”) MMSE with c] Demterleavmg 1 Equalizer Channel Estimation A -\ A A l - x n n uNu (l ‘ Despreadmg Nu( ) Chip-Level -1 yNX MMSE ¢—— with cNu Deinterleaving M1 Equalizer Figure 4.5. Block diagram of a DS-CDMA system with chip-level interleaving. 113 Let {ggzl (l)}ll‘=—O1 denote the (chip-rate) channel impulse response from the jth user to the ith receiver, the received chip-rate signal can be expressed as Nu L-l an) = Z Z g§"(z)yj