An Adaptive Single-Hop Medium Access Control Layer For Noisy Channels Except where reference is made to the work of others, the work described in this dissertation is my own or was done in collaboration with my advisory committee. This dissertation does not include proprietary or classi ed information. Derek T. Sanders Certi cate of Approval: Richard O. Chapman Associate Professor Computer Science and Software Engineering John A. Hamilton, Jr., Chair Associate Professor Computer Science and Software Engineering David A. Umphress Associate Professor Computer Science and Software Engineering Martin C. Carlisle Professor Department of Computer Science United States Air Force Academy George T. Flowers Dean Graduate School An Adaptive Single-Hop Medium Access Control Layer For Noisy Channels Derek T. Sanders A Dissertation Submitted to the Graduate Faculty of Auburn University in Partial Ful llment of the Requirements for the Degree of Doctor of Philosophy Auburn, Alabama August 10, 2009 An Adaptive Single-Hop Medium Access Control Layer For Noisy Channels Derek T. Sanders Permission is granted to Auburn University to make copies of this dissertation at its discretion, upon the request of individuals or institutions and at their expense. The author reserves all publication rights. Signature of Author Date of Graduation iii Dissertation Abstract An Adaptive Single-Hop Medium Access Control Layer For Noisy Channels Derek T. Sanders Doctor of Philosophy, August 10, 2009 (Master of Software Engineering, Auburn University, AL, 2008) (Bachelor of Wireless Engineering, Auburn University, AL, 2006) 351 Typed Pages Directed by John A. Hamilton, Jr. The work presented in this dissertation is for a contribution to the data link layer and its responsibility of managing the physical channel in a mobile ad-hoc net- work (MANET). Wireless networks in general are susceptible to noise in the spectrum, which can result in low throughput, loss of critical resources, and high re-transmission rates at the physical and link layers. As a result, there is a growing need for wireless technology that can continue to operate in the presence of noise. A mathematical al- gorithm has recently been developed which uses concurrent and super-imposed codes, which when applied to wireless communications allows for jam-resistant communica- tions without a pre-shared secret. By leveraging this algorithm, the research for this dissertation will create a jam-resistant single-hop medium access control (MAC) pro- tocol that adapts to the level of noise in the channel. The protocol will dynamically adjust the parameters for encoding to overcome the varying levels of interference. iv The new protocol will allow for communications to continue in the presence of noise or jamming attacks. v Acknowledgments A special thank you to my parents and my six siblings who have supported me during this milestone in my life. Thank you to my graduate advisor and committee members for their support, advice, and encouragement. Thank you to the Information Assurance Center graduate students at Auburn University for your support. Thanks to the US Air Force Academy Professors Bill Bahn, Leemon Baird, and Martin Carlisle for their support, advice, and expertise. Thank you to my friend, Mark Kuhr, for keeping me motivated. Thank you to all my other friends who have been there for support and knowl- edge. Thank you to RAM Laboratories, Inc. who have funded me through this re- search. vi Style manual or journal used Journal of Approximation Theory (together with the style known as \aums"). Bibliography follows van Leunen?s A Handbook for Scholars. Computer software used The document preparation package TEX (speci cally LATEX) together with the departmental style- le aums.sty. vii Table of Contents List of Figures xii List of Tables xiv 1 Introduction 1 1.1 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Wireless Technology Overview 10 2.1 Chapter Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Mobile Radio Propagation . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Physical Multiplexing and Spreading Techniques . . . . . . . . . . . . 12 2.4 Signal Jamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5 BBC Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5.2 BBC Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5.3 BBC Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5.4 BBC Decoding With Noise . . . . . . . . . . . . . . . . . . . . 24 2.6 Chapter Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3 Medium Access Control Layer 28 3.1 Chapter Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Flow and Error Control Protocols . . . . . . . . . . . . . . . . . . . . 28 3.3 Wireless Medium Access Control Protocols . . . . . . . . . . . . . . . 31 3.3.1 Contention Free Schemes . . . . . . . . . . . . . . . . . . . . . 32 3.3.2 Contention Based Schemes . . . . . . . . . . . . . . . . . . . . 34 3.4 Chapter Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4 BBC-MAC Initial Protocol Design 53 4.1 Chapter Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2 Protocol Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.3 Chapter Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 viii 5 Protocol Design and Implementation Phase 58 5.1 Chapter Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.2 System Components . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2.1 Hardware Components . . . . . . . . . . . . . . . . . . . . . . 60 5.2.2 Software Components . . . . . . . . . . . . . . . . . . . . . . . 64 5.3 Physical Layer Implementation . . . . . . . . . . . . . . . . . . . . . 73 5.4 BBC-MAC Implementation . . . . . . . . . . . . . . . . . . . . . . . 75 5.5 Chapter Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6 Phase I Experiments: Adaptive Coding Investigation 87 6.1 Chapter Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.2 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.3.1 Jammer RSSI Experiment . . . . . . . . . . . . . . . . . . . . 92 6.3.2 Pulse Jammer Experiment . . . . . . . . . . . . . . . . . . . . 93 6.3.3 Gaussian Jammer Experiment . . . . . . . . . . . . . . . . . . 102 6.4 Chapter Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 7 Phase II Experiments: Protocol Validation 113 7.1 Chapter Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.2 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 7.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.3.1 Initial Protocol Implementation Experiment . . . . . . . . . . 117 7.3.2 Re ned Protocol Implementation Experiment . . . . . . . . . 128 7.4 Adaptive vs Non-Adaptive . . . . . . . . . . . . . . . . . . . . . . . . 140 7.5 Chapter Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 8 Key Contributions 147 9 Conclusion 148 Bibliography 151 Appendices 161 A Source Code Listing 162 A.1 BBC-MAC Data Link Layer Code . . . . . . . . . . . . . . . . . . . . 162 A.1.1 Interface Class (interface.py) . . . . . . . . . . . . . . . . . . . 162 A.1.2 Receiver Class (Receiver.py) . . . . . . . . . . . . . . . . . . . 170 A.1.3 Receiver Handler Class (RxHandler.py) . . . . . . . . . . . . . 172 ix A.1.4 Transmitter Class (Transmitter.py) . . . . . . . . . . . . . . . 176 A.1.5 Transmitter Handler Class (TxHandler.py) . . . . . . . . . . . 177 A.1.6 BBC Con g Class (bbc con g.py) . . . . . . . . . . . . . . . . 181 A.1.7 BBC-MAC Frame Class (bbc frame.py) . . . . . . . . . . . . . 183 A.1.8 Utilities Class (utilities.py) . . . . . . . . . . . . . . . . . . . . 184 A.1.9 CRC16 Class (crc16.py) . . . . . . . . . . . . . . . . . . . . . 185 A.1.10 Stats Module (stats.py) . . . . . . . . . . . . . . . . . . . . . 187 A.2 Radio Scripts Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 A.2.1 USRP Receiver Script (usrp rx c le.py) . . . . . . . . . . . . . 188 A.2.2 USRP Transmitter Script (bbc tx.py) . . . . . . . . . . . . . . 193 A.3 BBC Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 A.3.1 bbcftp.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 A.3.2 bbcftp.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 A.3.3 bu er.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 A.3.4 bu er.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 A.3.5 bytes.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 A.3.6 bytes.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 A.3.7 codec.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 A.3.8 codec.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 A.3.9 con g.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 A.3.10 con g.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 A.3.11 dirtyd.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 A.3.12 dirtyd.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 A.3.13 modem.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 A.3.14 modem.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 A.3.15 sha1.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 A.3.16 sha1.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 A.3.17 sink.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 A.3.18 sink.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 A.3.19 source.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 A.3.20 source.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 A.3.21 usrp.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 A.3.22 Make le . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 A.4 Jammer Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 A.4.1 Main Program Source (jammer.c) . . . . . . . . . . . . . . . . 317 A.4.2 Modi ed BBC modem.h Source . . . . . . . . . . . . . . . . . 319 A.4.3 Modi ed BBC modem.c Source . . . . . . . . . . . . . . . . . 321 A.4.4 Modi ed BBC sink.h Source . . . . . . . . . . . . . . . . . . . 325 A.4.5 Modi ed BBC sink.c Source . . . . . . . . . . . . . . . . . . . 327 x A.4.6 Jammer Make le . . . . . . . . . . . . . . . . . . . . . . . . . 332 B Miscellaneous Files 334 B.1 Data Frame Hexadecimal String . . . . . . . . . . . . . . . . . . . . . 334 B.2 RTS Frame Hexadecimal String . . . . . . . . . . . . . . . . . . . . . 336 xi List of Figures 2.1 Hidden Terminal Problem . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Exposed Terminal Problem . . . . . . . . . . . . . . . . . . . . . . . . 18 5.1 Universal Software Radio Peripheral External View . . . . . . . . . . 60 5.2 Universal Software Radio Peripheral Internal Hardware . . . . . . . . 61 5.3 RFX-1200 Transceiver Daughterboard . . . . . . . . . . . . . . . . . 63 5.4 VERT400 Antenna . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.5 BBC Encoded Transmission without Noise . . . . . . . . . . . . . . . 72 5.6 BBC Encoded Transmission with Pulse Jammer Noise . . . . . . . . . 72 5.7 Physical Layer State Diagram . . . . . . . . . . . . . . . . . . . . . . 74 5.8 BBC-MAC State Diagram . . . . . . . . . . . . . . . . . . . . . . . . 76 6.1 RSSI Value vs Jamming Level . . . . . . . . . . . . . . . . . . . . . . 92 6.2 Collective Pulse Jammer Results . . . . . . . . . . . . . . . . . . . . 94 6.3 Pulse Jammer with Expansion 50 . . . . . . . . . . . . . . . . . . . . 96 6.4 Pulse Jammer with Expansion 75 . . . . . . . . . . . . . . . . . . . . 96 6.5 Pulse Jammer with Expansion 100 . . . . . . . . . . . . . . . . . . . 97 6.6 Pulse Jammer with Expansion 125 . . . . . . . . . . . . . . . . . . . 98 6.7 Pulse Jammer with Expansion 150 . . . . . . . . . . . . . . . . . . . 99 6.8 Pulse Jammer with Expansion 175 . . . . . . . . . . . . . . . . . . . 99 6.9 Pulse Jammer with Expansion 200 . . . . . . . . . . . . . . . . . . . 100 xii 6.10 Pulse Jammer with RTS Frame at Expansion 500 . . . . . . . . . . . 101 6.11 Collective Gaussian Jammer Results . . . . . . . . . . . . . . . . . . 103 6.12 Gaussian Jammer with Expansion 50 . . . . . . . . . . . . . . . . . . 104 6.13 Gaussian Jammer with Expansion 75 . . . . . . . . . . . . . . . . . . 105 6.14 Gaussian Jammer with Expansion 100 . . . . . . . . . . . . . . . . . 105 6.15 Gaussian Jammer with Expansion 125 . . . . . . . . . . . . . . . . . 106 6.16 Gaussian Jammer with Expansion 150 . . . . . . . . . . . . . . . . . 107 6.17 Gaussian Jammer with Expansion 175 . . . . . . . . . . . . . . . . . 108 6.18 Gaussian Jammer with Expansion 200 . . . . . . . . . . . . . . . . . 108 6.19 Gaussian Jammer with RTS Frame At Expansion 500 . . . . . . . . . 109 7.1 Experiment I Latency By Jammer Level . . . . . . . . . . . . . . . . 119 7.2 Experiment I Latency By Expansion Level . . . . . . . . . . . . . . . 120 7.3 Experiment I RTS Transmits By Jammer Level . . . . . . . . . . . . 122 7.4 Experiment I RTS Transmits By Expansion Level . . . . . . . . . . . 123 7.5 Experiment I Data Transmits By Jammer Level . . . . . . . . . . . . 126 7.6 Experiment I Data Transmits By Expansion Level . . . . . . . . . . . 126 7.7 Experiment II Latency By Jammer Level . . . . . . . . . . . . . . . . 131 7.8 Experiment II Latency By Expansion Level . . . . . . . . . . . . . . 132 7.9 Experiment II RTS Transmits By Jammer Level . . . . . . . . . . . . 134 7.10 Experiment II RTS Transmits By Expansion Level . . . . . . . . . . 135 7.11 Experiment II Data Transmits By Jammer Level . . . . . . . . . . . . 137 7.12 Experiment II Data Transmits By Expansion Level . . . . . . . . . . 138 7.13 Adaptive vs Non-Adaptive by DATA-ACK Exchanges . . . . . . . . . 142 7.14 Adaptive vs Non-Adaptive Convergence . . . . . . . . . . . . . . . . . 143 7.15 Pulse Jammer with RTS Frame at Expansion 175 . . . . . . . . . . . 145 xiii List of Tables 2.1 Pre x Hash Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2 Transmission Buckets . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Received Buckets With Noise . . . . . . . . . . . . . . . . . . . . . . 25 6.1 Expansion Factor Impact . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.2 Pulse Jammer Results . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.3 Gaussian Jammer Results . . . . . . . . . . . . . . . . . . . . . . . . 103 6.4 RSSI Failure Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7.1 Expansion RSSI Range . . . . . . . . . . . . . . . . . . . . . . . . . . 114 7.2 Experiment I Latency By Jammer Level . . . . . . . . . . . . . . . . 119 7.3 Experiment I Latency By Expansion Level . . . . . . . . . . . . . . . 119 7.4 Experiment I RTS Transmits By Jammer Level . . . . . . . . . . . . 121 7.5 Experiment I RTS Transmits By Expansion Level . . . . . . . . . . . 122 7.6 Experiment I Data Transmits By Jammer Level . . . . . . . . . . . . 125 7.7 Experiment I Data Transmits By Expansion Level . . . . . . . . . . . 125 7.8 Experiment I Message Errors By Jammer Level . . . . . . . . . . . . 127 7.9 Experiment I Message Errors By Expansion Level . . . . . . . . . . . 128 7.10 Experiment II Latency By Jammer Level . . . . . . . . . . . . . . . . 131 7.11 Experiment II Latency By Expansion Level . . . . . . . . . . . . . . 131 7.12 Experiment II RTS Transmits By Jammer Level . . . . . . . . . . . . 133 xiv 7.13 Experiment II RTS Transmits By Expansion Level . . . . . . . . . . 134 7.14 Experiment II Data Transmits By Jammer Level . . . . . . . . . . . . 136 7.15 Experiment II Data Transmits By Expansion Level . . . . . . . . . . 137 7.16 Experiment II Message Errors By Jammer Level . . . . . . . . . . . . 139 7.17 Experiment II Message Errors By Expansion Level . . . . . . . . . . 140 7.18 Adaptive vs Non-Adaptive . . . . . . . . . . . . . . . . . . . . . . . . 141 7.19 Adaptive vs Non-Adaptive with Modi cation . . . . . . . . . . . . . . 141 xv Chapter 1 Introduction The earliest wireless communications and transmission control project known as ALOHA [Abramson 1970] evolved into the wireless technology seen today. The Packet Radio Network (PRNET) [Jubin and Tornow 1987] grew out of the development of ALOHA and became one of the earliest multi-hop multiple access packet networks. To distinguish multi-hop from single-hop, multi-hop systems or layers are concerned with the movement of packets across multiple nodes or hops. Single-hop, on the other hand, is only concerned with the link between two nodes or hops. As technology progressed, the hardware needed to create diverse networks shrank into a more manageable form and has subsequently allowed for the evolution of small mobile devices in which each device can act as a repeater. This sort of network is commonly referred to as a Mobile Ad-Hoc Network (MANET). These networks can be viewed as simple peer-to-peer networks in which each node will receive packets and either keep it for itself or forward it onto the next destination. Each of the nodes in this network communicates via the wireless medium with other nodes in range without relying on internal infrastructure. The MANET is said to be self-organizing since it should automatically detect any new nodes and infuse them with the rest of the network e ortlessly. Due to the high mobility of these networks it is often di cult to e ectively coordinate access to the medium. This is due to the fact that incoming nodes and moving nodes transmissions can easily inject noise into a previously reserved channel. 1 Some of the characteristics that can be generalized for MANETs are as follows [Agrawal and Zeng 2006]: Dynamic Topologies: Mobility in the network causes the network topology to change at random, and it is often hard to predict where a node may be for the next transmission. The high degree of mobility also has an impact on the power constraints for the nodes. As nodes move, a previously visible node may not be reachable due to one node being limited by antenna power. Bandwidth Constraints: Bandwidth is a two-fold constraint when referring to wireless communications. There is the physical bandwidth of the channel and there is also the overall throughput of the link?s bandwidth. Most ad- hoc networks are constrained to the Industrial, Scienti c, and Medical (ISM) band, and are in turn required by FCC mandates that any radio in the ISM use either Frequency Hopping Spread Spectrum (FHSS) or Direct Sequence Spread Spectrum (DSSS). When considering the bandwidth of a MANET it is important to note that the already limited bandwidth is further reduced after the e ects of multiple access, fading, and interference have been considered. A problem of particular concern is channel saturation, which leads to congestion. This problem is compounded by the addition of noise and jamming attacks. This is due to the fact that the wireless spectrum is inherently error prone which further reduces the e ective throughput of the channel. 2 Limited Energy Potential: Due to the nature of mobile networks it is likely that the nodes will be running on a battery store. This impacts the nodes transmitting power. As previously mentioned, the di erent transmission powers coupled with mobility can sometimes create a unidirectional link. That is, one node is able to transmit to another but not vice versa. Limited Physical Security: Due to the fact that MANETs have no infras- tructure, security is a particular problem. Negotiating security trust levels and key exchanges is a hard problem with no central authority to handle these cre- dentials. Further problems can be found in the areas of Denial of Service (DoS) attacks, man-in-the-middle attacks, and eavesdropping. Noise and jamming, whether caused by other nodes in the network or intention- ally injected into the channel by an adversary, can signi cantly a ect the ability of network communications to carry on. With the increase in noise there is also an in- crease in channel saturation, leading to higher re-transmissions at the data link layer which can pose further threats to the sustainability of the node in terms of its power source. Current mechanisms for handling noise (or avoiding collisions) are handled by the Medium Access Control (MAC) layer protocol. The current protocols do not necessarily handle the noise, rather, they try to avoid collisions in the channel by using various techniques including sensing it before transmission or by splitting the channel into smaller channels. It is ine cient to divide the channel due to the limited bandwidth already asserted in the ISM, and current channel-sensing protocols can 3 starve their node in the presence of noise. These issues can have a signi cant impact on the ability on the network to sustain data ow and for other layers in the stack to properly carry out tasks. To address interference, a new MAC layer is needed that can continue to operate in the presence of noise. A new error-correcting code based upon concurrent codes forms the backbone of this new protocol. The BBC (named after the creators Baird, Bahn, and Collins) algorithm [Baird, Bahn, Collins, Carlisle and Butler 2007], a subset of concurrent codes, is the speci c coding scheme that will be applied to this research. Early research with this algorithm has shown that it can aid in the recovery of a message that has been a ected by noise or collisions. Noise can a ect transmissions by ipping bits, either 0?s to 1?s or vice versa. However, by leveraging this new algorithm the messages contained in the transmission can still be recovered up to a certain bit-error rate (BER). This research will create a new MAC layer, and its supporting facilities, which take advantage of the error correcting abilities of the BBC algorithm. The data link layer transforms the raw transmission ability of the physical layer into a reliable link, which is responsible for the hop-to-hop communications. This layer also transforms the data from the network layer into manageable chunks of data called frames. It is the responsibility of the MAC sub-layer to handle error correction either through correcting code or by retransmitting corrupted frames. Furthermore, the MAC layer is responsible for solving channel access con icts and coordinating the 4 transmission from one node to the next. The data link layer is traditionally thought to handle these four main tasks: Framing: The data link layer separates messages either from the network layer into smaller transmissions frames, or combines frames from the physical layer into their original message for delivery to the network layer. The degree of framing (variable-size) has a direct impact on the error control facility. Flow Control: This facility coordinates the data that can be outstanding before an acknowledgement is received for proper transmission. Flow control e ectively determines the channel saturation from the viewpoint of a single node. Error Control: During transmission at the physical layer the data can become corrupted. It is the responsibility of this facility to either detect and request retransmissions, or attempt to correct the bit errors. Types of correcting codes are block codes, linear block codes, and cyclic codes. One of the simplest forms of error detection falls into checksums. Another aspect of error control is to determine which frames have been lost and need to be retransmitted. Medium Access Control: In literature the MAC sub-layer is traditionally in control of the previous mentioned facilities in the data link layer. The main focus however is coordinating the access to a shared medium. It is responsible for resolving the problems that can arise when multiple nodes wish to access the channel. 5 The MAC layer?s ability to manage the physical medium has a direct e ect on how reliable a link is. It also has an impact on how e cient the link is in terms of overall data throughput. In other words, the MAC layer is the ultimate decider in the level of Quality of Service (QoS) a network can maintain. For this reason the design of a MAC protocol which handles the varying reliability of channel is of considerable importance. 1.1 Goals At the conclusion of this research e ort, this dissertation should demonstrate: A contribution to the area of MAC protocols for MANETs. This research will incorporate the BBC algorithm into a new MAC layer, called BBC-MAC. BBC- MAC will be a new approach to providing adaptive jam-resistant communica- tions without a pre-shared secret. This will be validated using software-de ned radios. A contribution to the current BBC algorithm by providing methods to vary the coding parameters to allow for various levels of jam-resistance to be used. This will allow BBC-MAC to adjust to varying levels of interference. This will be validated using software-de ned radios. The main research contribution contained in this proposal is a MAC layer so- lution to providing jam-resistant communications that can continue during a 6 jamming attack. The layer will achieve this by dynamically adjusting the cur- rent level of jam resistance with respect to the level of interference. 1.2 Challenges Creating a new MAC layer that is jam-resistant and that can be proven on a real-world test bed presents several challenges. As previously mentioned, the MAC layer has a direct impact on the QoS for a link, and creating one that in the end improves upon the current state of MAC protocols is the main challenge. However, by incorporating the BBC algorithm into this new layer, the current state of MANET communications can be advanced to provide greater data transfer reliability. However, the following challenges will need to be addressed. The new layer must be able to e ectively incorporate the BBC algorithm such that the coding parameters can be altered on a link-state basis. If the link has a low degree of noise, the level of encoding can be changed such that throughput goes up. Conversely, if the link has a high degree of noise, the layer should adjust the algorithm such that greater jam-resistance is achieved. The new layer must e ectively handle the congestion and saturation of the channel by incorporating the proper ow and error control facilities. These facilities must be adopted to take advantage of the important jam-resistant nature of the BBC algorithm. 7 The MAC protocol must e ectively coordinate access to the transmission chan- nel amongst multiple nodes while maintaining the proper level QoS. It is unclear how to properly con gure the MAC protocol to control all the other facilities of the data link layer, and is the main focus of this research. 1.3 Outline The remainder of this document is organized as follows: Chapter 2 gives an overview of the lower functions of wireless communications including radio propagation and the physical multiplexing that occurs at the physical level. The chapter concludes with an overview of the BBC algorithm and its operations. Chapter 3 introduces the speci c duties of the data link layer with a main focus on the discussion of current and past medium access control (MAC) protocols for consideration. Chapter 4 discusses the initial design of the protocol. Chapter 5 covers the protocol design and implementation. Chapter 6 covers the initial experiements for determining the proper con gura- tions needed to create the adaptive protocol. Chapter 7 covers the experiments and validation for the adaptive protocol. 8 Chapter 8 discusses the contribution to the research eld. Chapter 9 concludes with a discussion of this dissertation and future work. 9 Chapter 2 Wireless Technology Overview 2.1 Chapter Introduction Understanding the important functions of the lower layers of the wireless protocol stack is crucial for gaining insight into the problems that mobile wireless networks are faced with. The lowest level of interaction is at the physical layer and it is at this layer where noise makes its impact. A layer up sits the data link layer that is tasked with transforming the raw data transmissions provided by the physical layer into a reliable data link usable by the upper layers. This chapter is focused upon giving the reader an overview of the important components in wireless communications. The important concepts within radio propagation will be covered. Additional topics include an explanation of the physical multiplexing techniques, an overview of signal jamming, and an in depth overview of the BBC algorithm. Before continuing into the details of wireless communications a lexicon of terms is provided for the reader as a friendly reminder of the de nitions [Forouzan 2007]. Terminology: Bandwidth: The di erence between the highest and the lowest frequencies of a composite signal. Channel: A communications pathway. 10 Guard Band: The bandwidth separating two signals in a composite signal. Link: The physical communications pathway that transfers data from one device to another. Multiplexing: The process of combining signals from multiple sources for transmission across a single data link. Spectrum: The range of frequencies of a signal. Spread Spectrum: A wireless transmission technique that requires a band- width several times the original bandwidth. 2.2 Mobile Radio Propagation Communications in a MANET use a wireless transmission medium in order to exchange data. For this reason it is important to understand the distinguishing characteristics for radio propagation. Ideally, radio waves would move freely in space without any obstacles and free from interference. However, this is not possible in the real world except in a lab environment where the waves are propagating through a vacuum. When a radio wave does encounter an obstacle it can a ect the wave through re ection, di raction, or scattering. [Agrawal and Zeng 2006] 1. Re ection: Re ection occurs when the radio wave encounters an object that is larger compared to the size of its wavelength. This can be seen when the radio wave hits the side of a building, where it will be re ected o the building. 11 This scenario can be viewed as a positive event since it allows more waves to reach the receiver than would normally, but it also presents a problem since the receiver will have multiple copies of the same wave. 2. Di raction: Di raction occurs when radio waves are blocked by an object with sharp irregular edges. The radio waves will bend around the corner to reach the receiver. Like re ection this allows waves to reach the receiver even in situations where line of sight does not exist. 3. Scattering: Scattering occurs when the radio wave encounters an object that is smaller compared to the size of its wavelength and the incoming wave is scattered into several weaker outgoing signals. An example would be when a radio wave hits street signs or lampposts. 2.3 Physical Multiplexing and Spreading Techniques The physical layer of the network stack is charged with the physical movement of bits from one node to the next. It is the interface that connects the rest of the protocol stack to the physical medium for transport. This physical layer operates on a stream of bits that are encoded or modulated into an electrical or optical signal for transport. The layer is also concerned with the data rate over the medium. The upper bound on the communications network is always going to be the number of sustainable bits sent each second over the physical medium. The physical layer also handles the synchronization that is required at the bit level for communications to 12 take place. The nal important aspect to the physical layer is how it multiplexes the digital stream of bits into a transport form over the wireless medium. Applying speci c multiplexing and spreading techniques can e ciently use the bandwidth of the channel. When using multiplexing the goal is to create an e cient use of the channel by combining multiple signals into a single signal. Spreading the signal allows for privacy and the resistance to signal jamming. These techniques generally fall into the domains of time, frequency, and spreading [Forouzan 2007, Agrawal and Zeng 2006]. Frequency-Division Multiplexing (FDM): Frequency-division multiplexing is an analog multiplexing technique that combines multiple signals. This is used when the bandwidth (hertz) of a link is greater than that of the combined signals being transmitted. The individual signals generated by the devices are modulated on di erent carrier frequencies. These are then combined into a single composite signal to be sent out over the medium. The carrier frequencies are su ciently separated by guard bands to prevent overlap between the individual signals. Time-Division Multiplexing (TDM): Time-division multiplexing is a digital mul- tiplexing technique that combines multiple low-rate channels into a single high- rate channel. In contrast to FDM, TDM shares time on the medium versus frequency as in FDM. Each node that is connected to the medium is given a certain portion of time on the link in which it can occupy. There are two prevail- ing methods of doing TDM: synchronous and statistical. The main di erence between the two is that in synchronous mode, a node is allocated a time slot 13 even if the node does not have any data to send. Statistical TDM dynamically allocates time units as needed which improves the bandwidth e ciency. Orthogonal Frequency-Division Multiplexing (OFDM): Orthogonal frequency- division multiplexing is a technique to split high-rate radio signals into several low-rate signals that are then transmitted over several orthogonal carrier fre- quencies. The sending node breaks down the high-rate streams into n parallel low-speed streams that are then modulated. The key di erence between OFDM and FDM is that in OFDM all the sub-bands are used by a single source at one time, instead of in FDM where the sub-bands are taken up by separate sources. OFDM is used as the multiplexing technique in 802.11a/g/n. Spread Spectrum (SS): Spread spectrum is a technique like multiplexing that brings together multiple signals for transmission. SS was originally designed for military use to avoid jamming in the wireless spectrum. In wireless com- munications, nodes must be able to share the medium in a manner that allows for privacy from eavesdropping and without being susceptible to jamming. SS takes the original signal?s required bandwidth and expands it such that the spreaded bandwidth is much larger (usually twice) that of the original band- width. After the signal has been created, the spreading process uses a spreading code or chip-sequence, which determines how the original signal is spread in the new bandwidth. Currently there are two main techniques for spreading the 14 bandwidth: Direct Sequence Spread Spectrum (DSS) and Frequency Hopping Spread Spectrum (FHSS). 1. Direct Sequence Spread Spectrum (DSSS): Direct sequence spread spec- trum multiplies the original signal by a pseudorandom sequence of bits that is much larger than the original signal, e ectively spreading the origi- nal signals bandwidth. In other words, each data bit in the original signal is multiplied by the chip sequence using polar non-return to zero (NRZ) encoding. DSSS provides privacy from eavesdropping as long as no other nodes have access to the code. DSSS is resistant to interference in the spectrum if each node uses a di erent spreading sequence. 2. Frequency Hopping Spread Spectrum (FHSS): Frequency hopping spread spectrum uses a pseudorandom sequence to spread the original signal across a larger bandwidth. The sequence determines how the radio sig- nal hops between the multiple carrier frequencies. 2.4 Signal Jamming Wireless communications are prone to errors during transmission. Signal jam- ming disrupts the transmission and can occur through un-intentional means such as interference, collisions, or noise. This type of jamming can occur in situations of high network saturation where competing nodes are causing collisions in the spectrum. A 15 more signi cant threat are jamming attacks from adversaries attempting to disrupt or bring down the network. Unintentional Jamming: Friendly jamming is a common occurrence in current wireless communication systems such as 802.11. The collisions that occur at the physical layer are resolved by the data link layer, and generally go unnoticed by the user operating at the application layer. It is only in situations of high network congestion and noise where the problem can be seen in terms of lost packets and high latency. Collisions occur when multiple stations transmit at the same time onto a channel that was designed to only support one transmission. When this happens the signals are combined, which e ectively destroys or corrupts the data from the individual transmissions. The two most familiar situations that can cause unintentional jamming are the exposed and hidden terminal problems [Forouzan 2007]. 1. Hidden Terminal Problem: The hidden terminal problem is depicted in Figure 2.1. In this situation terminal A is able to see the signals broad- casted from both B and C, but B and C are hidden from each other with respect to A. Consider the scenario when terminal B is sending data to terminal A. While this transmission is occurring terminal C also wishes to send data to terminal A. The problem is terminal C can?t sense the channel to see that terminal B is transmitting since C is out of range of 16 B?s transmission radius. When the two begin to transmit it will cause a collision corrupting the data A is receiving. Figure 2.1: Hidden Terminal Problem 2. Exposed Terminal Problem: The exposed terminal problem is depicted in Figure 2.2. In this situation the problem is that terminal C is exposed to the transmissions from terminal A to B. Consider the scenario where ter- minal C wishes to send data to terminal D, and at the same time terminal A is transmitting data to terminal B. Terminal C could send data to D without interfering with the data from A to B, however, since it is being exposed to the transmissions from A to B, it will not begin transmitting to D. In other words, terminal C is wasting time and the actual channel availability by waiting for terminal A to complete its transmission to B. Intentional Jamming: As mentioned before the second type of jamming occurs when an adversary wishes to attack a network. Jamming is a relatively easy task since in the general case no special hardware is needed to carry out the attack, and it can be 17 Figure 2.2: Exposed Terminal Problem implemented by merely listening to the medium and broadcasting at the same frequency, and when carried out correctly it can lead to signi cant network and communications disruptions [Awerbuch, Richa and Scheideler 2008]. The method of attack is usually targeted at the physical medium for the network, but more sophisticated attacks can target the speci c way the MAC protocol operates in the data link layer. Methods for carrying out jamming attacks have been studied and validated through simulation [Chiang and Hu 2007, Law, van Hoesel, Doumen, Hartel and Havinga 2005, Li, Koutsopoulos and Poovendran 2007, Xu, Trappe, Zhang and Wood 2005]. Current defenses against jamming focus on special techniques at the physical layer, such as spreading techniques [Forouzan 2007, Liu, Noubir, Sundaram and Tan 2007, Navda, Bohra, Ganguly and Rubenstein 2007]. Current wireless technologies like 802.11b use a form of spread spectrum. However, 802.11b uses narrow spreading which allows an attacker to jam only a small set of frequencies rendering spread spectrum useless. Furthermore, the MAC protocol in 802.11 does not o er any protection 18 to even the simplest jamming techniques [Forouzan 2007, Bayraktaroglu, King, Liu, Noubir, Rajaraman and Thapa 2008]. 2.5 BBC Algorithm Overview The goal of this research is to create a new MAC layer that provides jam- resistance without a pre-shared secret by taking advantage of the BBC algorithm [Baird, Bahn, Collins, Carlisle and Butler 2007]. Given its pivotal role in this re- search e ort it is important to gain a clear understanding of how it will allow the new layer to accomplish the task of maintaining a reliable link even in the presence of noise. This section will cover the terminology used when referring to BBC opera- tions, explain by example how the algorithm conducts its encode and decode steps, and nally noise will be added to the example to illustrate how it overcomes that obstacle. 2.5.1 Introduction Current technologies such as spread spectrum provide jam-resistance, however, the two communicating parties must possess the same chip sequence in order to com- municate in a private and jam-resistant manner [Forouzan 2007]. Managing the chip sequences for every node is similar to the problem that was faced by the cryptographic community prior to the movement to a public key infrastructure. Prior to public key cryptography both parties had to know the symmetric key in order to cipher messages between the each other. In order to overcome this problem, new wireless technologies 19 are needed that allow for communications to occur which provide jam-resistance and privacy, but also eliminate the need for secret knowledge (chip sequence). The cre- ators of the BBC algorithm had this problem in mind when creating the algorithm. The algorithm allows the communicating parties to talk without a pre-shared key while a ording jam-resistance. Terminology The following glossary of terms is presented for the reader. Many of these terms will be used when referencing the BBC algorithm in this Section and the remainder of the dissertation. Indelible Mark The location of a 1 bit, or a high pulse in a transmission. It is assumed that the mark can never be transformed from a 1 to a 0. Data The payload that is encapsulated in a message. Message The fully constructed message including the necessary checksum bits and header information. Packet This is the combination of multiple messages that are combined with a bitwise OR. The packet is the nal data which the BBC algorithms are enacted upon. The BBC algorithm operates in two modes: encoding and decoding. The en- coding stage transforms binary data into a form, which determines how it is to be physically transmitted. The parameters given to the encoder determine the level 20 of jam-resistance it a ords. The following sections show by example how the BBC algorithm operates. 2.5.2 BBC Encoding Algorithm 1 BBCEncode(M) This function encodes an m-bit message M[1...m] adding k checksum bits to the end of the message. H is a hash function. The de nition of H and the value of m and k are public (not secret). The de nition of "indelible mark" and "location" are speci c to the physical instantiation of BBC used. Append k zero bits to the end of M for i = 1 ... m+k do Make an indelible mark at the location given by H(M[1...i]) end for The BBC Encoding algorithm is shown by Algorithm 1 [Baird, Bahn, Collins, Carlisle and Butler 2007]. It is a fairly straightforward process, compared to the steps taken during decoding. The rst thing that is done is the original message is appended with k checksum (zero) bits. The number of bits is determined in advance based upon the coding parameters and the expected number of errors that is determined by the current interference detected. Next, each pre x of the bit string is sent through a hash function that maps a variable length bit string to some desired mapping where the indelible mark will be. In this example pulse broadcast is used and so it is conceptually mapped to a bucket number representing a period of time where a pulse would be. Using the algorithm, and the example in [Baird, Bahn, Collins, Carlisle and Butler 2007] which uses 25 buckets and 2 checksum bits, the encoding of the message M = 1000 proceeds as follows: 21 1. Append two checksum zeros to M: 100000. 2. Encode each pre x string, s, using the hash function, H as shown in Table 2.1. s H(s) 1 21 10 9 100 20 1000 14 10000 6 100000 10 Table 2.1: Pre x Hash Table 3. Broadcast this message by transmitting a pulse where there is a corresponding 1 in the buckets from Table 2.1. The result of this broadcast in the time period conceptualized by the buckets [0,25] is seen in Table 2.2. Bucket 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 251000 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 Table 2.2: Transmission Buckets 2.5.3 BBC Decoding Decoding on the receiver?s end is considerably more complex than the steps taken to encode the message. This is because the receiver is unaware of what is sent and must begin at the very beginning of any root message and systematically reduce the set of possible messages. The algorithm for decoding the received message is given by Algorithm 2 [Baird, Bahn, Collins, Carlisle and Butler 2007]. It is assumed that the receiver knows the hash function, length of messages, and the length of k. From the encoding example, assuming there was no noise induced in the message, and 22 Algorithm 2 BBCDecode(n) This recursive function can be used to decode all the messages found in a given packet by calling BBCDecode(1). There must be a global M[1...m + k] which is a string of m + k bits. The number of bits in a message is m, and the number of checksum zeros appended to the message is k. The de nition of H and the value of m and k are public (not secret). The de nition of "indelible mark" and "location" are speci c to the physical instantiation of BBC used. if n = m+k + 1 then print "One of the messages is:" M[1:::m] else if n>m then limit(0 else limit(1 end if for i = 0 ... limit do M[n] (i if there is an indelible mark at location H(M[1:::n]) then BBCDecode(M,n+ 1) end if end for end if the receiver began listening at the proper time the queue would look like Table 2.2. Following the decoding algorithm the steps to decode this message would proceed as follows: 1. Determine whether a 0 or 1 was transmitted. H(0) = 4 and H(1) = 21. The receiver will listen for pulses at time slots 4 and 21. From Table 2.2 it is seen that bucket 21 has a pulse, and thus the receiver knows that the message begins with a 1. M0 = 1. 23 2. Next, the current set of pre xes are appended with 0 and 1 to account for all pre xes. M? = 10, 11. H(10) = 9 and H(11) = 21. Both of these locations have pulses and will survive onto the next decoding iteration. M0 = 10, 11. 3. Again, the current set of pre xes are appended with a 0 and 1. M0 = 100, 101, 110, 111. H(100) = 20, H(101) = 24, H(110) = 16, and H(111) = 2. Cross- referencing with Table 2.2, it can be seen that only bucket 20 has a pulse and thus 100 is the only survivor. M0 = 100. 4. Appending the current set of pre xes gives M0 = 1000, 1001. H(1000) = 14, H(1000) = 1. Only bucket 14 has a pulse and reduces the set to M0 = 1000. 5. At this stage the length of the original message has been reached. Thus, from this point on the surviving pre xes will be appending with the checksum bits (0- bits) for at most k times. H(10000) = 6. This does have a pulse and continues onto the nal decoding stage. M0 = 10000. 6. This is the last decoding step since this is the last checksum bit to be appended. H(100000) = 10, and bucket 10 does indeed have a pulse. Removing the k checksum bits from the surviving set of M0 reveals that the only message was sent = 1000, and this matches up with what was encoded in Section 2.5.2. 2.5.4 BBC Decoding With Noise The decoding example in section 2.5.3 illustrated the basic concept of how to use the BBC algorithm for physical encoding and decoding of the messages. However, 24 it lacked the illustration of how the algorithm will decode when a few of the bits are ipped during transmission. It is assumed that the induction of power into the spectrum can only ip the bits from 0 to 1 and not vice versa. For the sake of completeness it will be shown how the algorithm decodes the message when just two bits are ipped, or in this case, there are two buckets that get pulses. Using Table 2.2 as the basis, the following buckets are given pulses: 2 and 24. These buckets are marked with an X in Table 2.3 to di erentiate them from the true pulses sent out by the sender. Bucket 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 251000 0 X 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 X 0 Table 2.3: Received Buckets With Noise The decoding proceeds as follows: 1. Determine whether a 0 or 1 was transmitted. H(0) = 4 and H(1) = 21. The receiver will listen for pulses at time slots 4 and 21. From Table 2.2 it is seen that bucket 21 has a pulse, and thus the receiver knows that the message begins with a 1. M0 = 1 2. Next, the current set of pre xes are appended with 0 and 1 to account for all pre xes. M? = 10, 11. H(10) = 9 and H(11) = 21. Both of these locations have pulses and will survive onto the next decoding iteration. M0 = 10, 11. 25 3. Again, the current set of pre xes are appended with a 0 and 1. M0 = 100, 101, 110, 111. H(100) = 20, H(101) = 24, H(110) = 16, and H(111) = 2. Cross- referencing with Table 2.3, it can be seen that buckets 20, 24, and 2 have pulses. M0 = 100, 101, 111. 4. Appending the current set of pre xes gives M0 = 1000,1001,1010,1011,1110,1111. H(1000) = 14, H(1000) = 1, H(1010) = 15, H(1010) = 2, H(1110) = 14, H(1110) = 23. Buckets 14 and 23 have pulses, and two of the pre xes mapped to 14 which gives the set M0 = 1000, 1011, 1110. 5. At this stage the length of the original message has been reached. Thus, from this point on the surviving pre xes will be appending with the checksum bits (0-bits) for at most k times. H(10000) = 6, H(10110) = 14, H(11100) = 13. Bucket 6 and 14 have transmissions and the follow pre x set survives: M0 = 10000, 10110. 6. This is the last decoding step since this is the last checksum bit to be appended. H(100000) = 10, H(101100) = 12. Only bucket 10 has a pulse leaving M0 = 100000. Removing the k checksum bits from the surviving set of M0 reveals that only message was sent = 1000, and this matches up with what was encoded in Section 2.5.2. This example illustrated clearly how the algorithm reduces the set of possible pre xes to get the actual message even in the presence of corrupted transmissions. The interesting occurrences are the two surviving messages past the original message?s 26 length. These two messages that got eliminated are called hallucinations as termed by the authors of [Baird, Bahn, Collins, Carlisle and Butler 2007]. This example illustrates the importance of the k checksum bits. In the previous decoding example it might have been thought to just stop decoding since the original message was recovered. However, in this example if that were to have occurred three messages would have thought to been received, and even onto the second to last stage two messages would have been received. It is only after the nal decoding step where it is determined how many true messages were sent. 2.6 Chapter Conclusion This chapter began with an introduction to wireless communications and the op- erations that occur at the physical layer for transport. An introduction to the various signal jamming scenarios was presented, and the chapter concluded with an introduc- tion to the BBC algorithm. A toy example was worked through that demonstrated how the BBC algorithm encodes and decodes data, and nally, a decoding example where noise was arti cially induced was given. 27 Chapter 3 Medium Access Control Layer 3.1 Chapter Introduction In relationship to the OSI model, the IEEE 802 standard speci es that the data link layer be divided into two sub-layers: the logical link control (LLC) layer and the medium access control (MAC) layer. The separation is made to allow the MAC protocol layer to be speci c to the type of physical medium used. For example, the LLC in the IEEE 802 standard is the same across all the di erent local area network (LAN) protocols, and it is only the MAC that is modi ed as necessary [Forouzan 2007]. For instance, IEEE 802.3 Wired Ethernet LAN uses a Carrier Sense Multiple Access (CSMA) with Collision Detection, and IEEE 802.11 Wireless LAN uses a specialized version of CSMA with Collision Avoidance, but both use the same IEEE 802.2 LLC. 3.2 Flow and Error Control Protocols The speci c duties assigned to the LLC according the IEEE 802 standard are to provide ow and error control. Flow control refers to the set of mechanisms that dictate the number of outstanding frames that the sender can transmit without re- ceiving an acknowledgement (ACK) frame. Error control is the correction of the 28 problem when an acknowledgement is never received, the receiver never gets an un- expected frame, or the receiver gets a corrupted frame. It is based on the concept of automatic repeat request, or the retransmission of data. Flow and error control are accomplished through the use of a single protocol, with the exception of the error detection mechanisms. The following lists the most familiar protocols to accomplish error and ow control [Forouzan 2007]. Stop-and-Wait Automatic Repeat Request: This is the simplest of the ow and error control protocols. This protocol will have one outstanding frame at any point in time. It will send one frame, and then wait for an ACK frame to be returned from the receiver, or for a timer to expire, in which it will automatically re-transmit the unacknowledged frame. The error control is achieved through the use of the timer. It is assumed that if there isn?t an ACK received after a speci c time that an error has occurred dur- ing transmission and the frame never arrived or the receiver received a corrupted frame. Sequence numbers are used for identifying frames, based on modulo-2 arithmetic. The sequence number inside the returned ACK frame is the number for the frame that the receiver is expecting next. Go-Back-N Automatic Repeat Request: This protocol expands upon the previous one by allowing multiple frames to be sent at once. An abstraction known as the sliding window is used, where within the sliding window resides the frames with the sequence numbers that have not 29 been acknowledged. The window can only slide when a valid acknowledgement is received. Generally, the window can only slide one slot at a time. However, since it is assumed that the receiver only sends back the ACK for the next frame expected, the window can slide directly to that frame number, and send out any frames in the window. This is because the receiver may not send back an ACK for every frame it receives, just the most recent in order frame. Like the Stop-and-Wait protocol, this also uses timers for error control. However, there is only one timer that is kept track of, versus one for each frame. The timer is only maintained for the oldest outstanding frame, and if that timer expires all of the frames within the window are retransmitted. Selective Repeat Automatic Repeat Request: The previous two protocols simpli ed the process carried out at the receiver?s end. The receiver only had to maintain one bu er, the space for the next frame expected. Any out of order frames that were received were simply discarded, and this is a very ine cient use of the link. This problem can be further compounded in noisy channels, like that in wireless communications, where a frame has a high probability of being corrupted. These retransmissions use valuable link bandwidth and further add to the probability of a corrupted frame. Selective Repeat is a protocol meant for noisy channels. In this protocol instead of the sender sending back all the frames in the window, it only retransmits those that have not been acknowledged or have been corrupted. This allows for e cient use 30 of the link, but makes the processing on the receiver?s end much more complex. The receiver can receive as many out of order frames as the window size and will store them until enough in order frames arrive to deliver to the upper layer. The receiver makes use of non-acknowledgment (NAK) frames, which are sent to the sender to remind them to retransmit a speci c frame. A nal level of complexity in this protocol is that every frame is given a timer, since it is only sending back the corrupted frames, and not all the frames in the window. These protocols provide the necessary functionality for error and ow control at the data link layer. This research will however not distinguish them from the MAC layer, and will instead consider them to be under the control of the protocol guiding the access to the medium. 3.3 Wireless Medium Access Control Protocols The MAC layer is responsible for solving the errors and anomalies that can occur at the physical layer. It is the responsibility of this layer to resolve the con icts that arise when multiple nodes wish to use a single channel. The speci c protocol used can have a direct impact on the e ciency of the link and for this reason it is important to consider the quality of service (QoS) constraints when designing a new MAC layer. The protocols can be divided into two main categories: contention free and contention based schemes, and then there are those that combine the two to form hybrid protocols. Contention based schemes can be further divided into those which operate on random access versus those that attempt to reserve the channel and resolve 31 collision. These protocols can be further divided into single channel, multi channel, power aware, and quality of service (QoS) based protocols [Kumar, Raghavan and Deng 2006]. 3.3.1 Contention Free Schemes Contention free schemes are those that divide the channel in such a way that no two nodes should ever be competing for access to the channel at any point in time. These are sometimes called channelization access schemes. These types of schemes divide the available bandwidth of the link into multiple channels through time, frequency, or through codes, and others use polling or are token-based systems. The most familiar of these protocols are Frequency Division Multiple Access (FDMA): Frequency division multiple access (FDMA) divides the available bandwidth into multiple frequency bands. Each node is then allocated a speci c band on which it can transmit data. Like in FDM, guard bands separate the individ- ual bands. However, while FDM and FDMA conceptually operate the same there is a key di erence. As mentioned in Section 2.3, FDM is a physical layer multiplexing technique that combines the data from multiple low-bandwidth channels and transmits them over a single high-bandwidth channel. The dif- ference is that FDMA tells the physical layer to make a band pass signal from the data that is given to it limiting the frequency that the node is transmitting 32 on. The signals from each station are then transmitting at di erent frequen- cies and are combined when they put on the single channel [Forouzan 2007]. FDMA has been applied to various multiplexing schemes in literature including the OFDM-FDMA and OFDM-interleaved-FDMA [Wong, Cheng, Lataief and Murch 1999] schemes. Time Division Multiple Access (TDMA): Time division multiple access (TDMA) divides the channel in time. Each node is given a speci c time slot in which data can be transmitted on its behalf. TDMA su ers from a synchronization issue since each station needs to know exactly when a new time slot is beginning in order to e ectively transmit at the correct time. Again, it needs to be clear that TDMA and TDM as mentioned in Section 2.3 are conceptually the same, but achieve di erent goals. TDM combines the data of slower channels into a single faster channel using a multiplexer that interleaves the data. TDMA however tells the physical layer to use a speci c time slot [Forouzan 2007]. TDMA has been supplemented as an access scheme in literature [Wang and Xiang 2006, van Hoesel, Nieberg, Kip and Havinga 2004, Kanzaki, Hara and Nishio 2007, Gerla and Tzu-Chieh Tsai 1995]. Code Division Multiple Access (CDMA): Code division multiple access (CDMA) is a scheme in which a single channel carries all the data from multiple nodes simultaneously. It is based on cod- ing theory, much like the spreading techniques described in Section 2.3. While 33 CDMA and DSSS might seem similar there is a clear distinction. CDMA uses multiple orthogonal spreading sequences to allow for the multiple node access on the same frequency. However, in the implementation of 802.11b DSSS, ev- ery node uses the same spreading sequence, but allows the nodes to choose from multiple frequencies for simultaneous operation. In CDMA each station is given a speci c code called a chip sequence. By assigning each station their own code multiple stations can communicate on a single channel without inter- fering with other communicating nodes, assuming they know each other?s chip sequence [Forouzan 2007]. CDMA has been proposed [Muqattash and Krunz 2003, Garcia-Luna-Aceves and Raju 1997, Joa-Ng and Lu 1999, Lee and Cho 1995, Sousa and Silvester 1988] and tested [Hui 1984] as a protocol for MANETs in literature. 3.3.2 Contention Based Schemes Protocols that operate on the foundation that nodes must compete for access to the channel are considered contention-based schemes. These are generally called random access protocols where no station is considered to be superior to another. For this reason the MAC layer for contention based schemes can be considerably more complicated than those for controlled access or channelized layers. ALOHA: ALOHA is the earliest random access protocol developed by the University of Hawaii in the early 1970?s. The original protocol is sometimes referred to as 34 pure ALOHA. The protocol is simple in that whenever a station wishes to send a frame it does so. To recover from errors the protocol uses acknowledgments from the receiver. If the sender doesn?t receive an acknowledgment after a time-out period it assumes that frame has been lost. This is similar to the error control protocols discussed in Section 3.2. When the timeout does occur pure ALOHA requires that the sending node wait a random amount of time before retransmitting. By waiting a random period time, the idea is to avoid more collisions. Additionally, in order to avoid congestion from retransmits the protocol further dictates that after a speci ed number of retransmits the station must give up on that frame. A later modi cation to ALOHA is with slotted ALOHA. Much like TDMA, slotted ALOHA divides channel access into periods of time called slots, where a node is only allowed to transmit during their speci ed slot. However, collision can still occur if two stations try to send at the same time slot [Forouzan 2007, Abramson 1970]. Carrier Sense Multiple Access (CSMA): Carrier Sense Multiple Access (CSMA) is a protocol where a station is required to sense the medium prior to transmitting. CSMA is an evolution of ALOHA in the sense that it is reducing the chance of a collision because it senses the channel, but it cannot eliminate collisions. When the station senses that the channel is idle or busy there are three methods that can be used to determine how to precede [Agrawal and Zeng 2006]. 35 { 1-Persistent Method: If the channel is idle, send the frame immedi- ately. If it is busy, keep listening until it is idle and then transmit. { Non-persistent Method: If the channel is idle, send the frame imme- diately. If it is busy, wait a random amount of time and then sense the channel again. { p-Persistent Method: In this method time is considered to be slotted. Each time slot is considered to be the contention period, usually equal to the round trip propagation time. When there is a frame to send the station rst senses the channel. If it nds the channel to be idle it follows these steps: 1. With probability p, the station sends its frame. 2. With probability q = 1 - p, the station waits for the beginning of the next time slot and senses the channel again. (a) If the line is idle, proceed to step 1. (b) If the line is busy, acts the same way as in a collision. Waits a random amount of time and starts all over. Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA): The basic CSMA with collision avoidance (CSMA/CA) protocol relies upon three important strategies in order to provide collision avoidance: inter-frame space, contention window, and acknowledgements. When a station has a frame to send it senses the channel. If it is idle the station will not send immediately, 36 but rather defer transmitting for a speci ed amount of time called the inter- frame space (IFS). After this time it senses the channel again, if it is idle the station can transmit after waiting for a period of time to pass called the con- tention time. The contention window is a time period divided into slots. When the station is ready to transmit it must chose a random number of slots to wait before the transmission can occur. At each time slot the channel is sensed, and if it is busy it must stop its timer, and can only start the timer when the channel is sensed idle again. Once the timer goes to zero, the transmission can occur. Even with the other precautions a collision can occur. The protocol uses timers and acknowledgments to recover from corrupt or lost frames. The basic CSMA/CA protocol still su ers from the hidden and exposed terminal problems discussed in Section 2.4. In order to overcome these problems channel reservation mechanisms have been amended to CSMA/CA. The most basic solution is through the use of request-to-send (RTS) and clear-to-send (CTS) control frames. When a station wishes to send a frame it sends a RTS frame to the receiver. Tobagi and Kleinrock rst proposed the exchange of RTS/CTS in the split-channel reservation multiple access (SRMA) scheme [Tobagi and Kleinrock 1976]. The receiver will reply with a CTS frame. The exchange of these frames still follows the protocol explained previously for sending a data frame. The idea with this exchange is that the channel has been reserved for communication between these two stations. The RTS also lets the receiver know that data is coming and gives it the ability to allocate bu er space for the 37 transmission. Any other station that received these RTS or CTS frames will defer its own transmissions to further reduce the chance of collisions [Forouzan 2007, Agrawal and Zeng 2006]. Multiple Access Collision Avoidance (MACA): The Multiple Access Collision Avoidance (MACA) protocol was proposed by Karn to overcome the problems faced by the basic CSMA/CA protocol discussed above, namely the hidden and exposed terminal problems [Karn 1990]. MACA uses small signaling packets like the RTS and CTS control packets used in CSMA/CA. However, the author drops the carrier sense aspect of CSMA, and instead focuses on extending the CA aspect. The dropping of the CS amounts to the ALOHA protocol with RTS and CTS control frames. As mentioned previously, when other stations overhear a RTS or CTS control frame they are required to defer their transmission for some period of time. It is unclear however how long these stations should defer using the channel, and this is where Karn?s work is important. In MACA the sender includes the size of the data being transferred in the RTS frame, and the receiver will return that same information in the CTS frame. Any node that receives these frames will know approximately how long they should defer transmitting based on the size of the data. A further bene t of this protocol is that the size of the RTS/CTS frames is quite small, compared to the data packets, reducing the probability and risk that collisions between them present. However, MACA does not use 38 acknowledgement frames for the data packets at the MAC layer, and instead leaves it up to the error control facility in the transport layer. An extension to the basic MACA scheme was proposed by Bharghavan et al. [Bharghavan, Demers, Shenker and Zhang 1994] called MACA for wireless (MACAW). MACAW adds acknowledgement frames to the protocol giving it the ability to recover from errors faster than MACA. Other variations of MACA include MACA for underwater acoustic networks with packet train for multiple neighbors (MACA-MN) [Chirdchoo, Soh and Chua 2008], MACA by invita- tion (MACA-BI) [Talucci and Gerla 1997], and the Floor Acquisition Multiple Access protocol [Garcia-Luna-Aceves and Fullmer 1999]. Floor Acquisition Multiple Access (FAMA): The Floor Acquisition Multiple Access (FAMA) protocol proposed by Garcia- Luna-Aceves et al. is a MACA based scheme that dictates that every trans- mitting node must acquire explicit control of the channel prior to transmitting [Garcia-Luna-Aceves and Fullmer 1999]. This protocol di ers from the MACA and MACAW schemes since it requires that both the sender and the receiver take an active role in the collision avoidance process. To "acquire the oor", as the authors put it, the sender sends out a RTS frame either by the FAMA non-persistent packet sensing (FAMA-NPS) or the FAMA non-persistent carrier sensing (FAMA-NCS) scheme. The receiver will reply with a CTS containing the address of the initiating station. Any other station that receives an error 39 free CTS frame will know that the terminal addressed in the CTS frame has reserved the channel. This is the oor acquisition aspect of FAMA. To fur- ther ensure that the channel has been reserved, the CTS are repeated enough times in order to jam any hidden station who did not hear the original RTS acknowledgment. Multiple Access Collision Avoidance by invitation (MACA-BI): The MACA by invitation (MACA-BI) proposed by Talucci and Gerla is a re- ceiver initiated based protocol [Talucci and Gerla 1997]. In sender-initiated protocols the sender will attempt to gain access to the channel by initiating the RTS-CTS handshake. However, MACA-BI requires that the receiver re- quest the data from the sender by using a ready-to-receive (RTR) frame. This reduces the overhead in the exchange by making it an RTR-DATA versus an RTS-CTS-DATA process. This protocol appears to be meant for service net- works where the communications are one way, that is, where the receiver has information it knows the other party has, it will send out a RTR that will be followed by the data. Collision-free Receiver Oriented MAC (CROMA): Collision-free Receiver Oriented MAC (CROMA) [Coupechoux, Baynat, Bonnet and Kumar 2005] is a receiver initiated MAC protocol similar to MACA-BI. CROMA divides time into frames, where each frame is further divided into a xed number N time-slots. Each slot is broken into three sub-slots: request 40 (REQ), ready-to-receiver (RTR), and a data (DATA) slot. The REQ slot is used by nodes to send a REQ frame to a receiving node. The RTR slot is used to acknowledge the REQ frames sent and to poll the nodes that previously sent a successful request and reservation. A DATA frame is then sent once the sender in the RTR slot has been successfully polled. The reservation of the channel is achieved through the polling frames sent in the RTR slot, and this is what makes CROMA a receiver oriented protocol versus a sending oriented one. CROMA di ers from MACA-BI since it does not need to use a tra c prediction algorithm. The division of these slots makes CROMA a collision-free contention-based protocol. IEEE 802.11 MAC: The IEEE 802.11 standard de nes two MAC sub-layers: the point coordination function (PCF) and the distributed coordination function (DCF). The DCF mode of operations was meant for ad hoc networks whereas the PCF mode was meant for infrastructure-supported networks. The DCF function uses CS- MA/CA with acknowledgment and RTS/CTS frames (RTS-CTS-DATA-ACK). The protocol operates much in the same way as described in the CSMA and CSMA/CA description with several di erences [Forouzan 2007, Agrawal and Zeng 2006]. 1. Sending node rst senses the channel by monitoring the energy level on the carrier frequency. 41 (a) If found to be busy a persistent strategy with a back-o timer is used until the channel is idle. (b) Once the channel is found to be idle, the station must wait for a period time called the distributed interframe space (DIFS). After this duration the sender transmits a RTS frame. 2. Upon receiving the RTS frame, the receiver must wait for a period of time called the short interframe space (SIFS) to pass prior to replying with a CTS frame. 3. When the sender successfully receives the CTS frame it must wait for the SIFS to pass prior to sending a data frame. 4. Upon successful reception of a data frame, the receiver must wait for the SIFS to pass prior to returning an ACK frame. This protocol makes use of the SIFS to further reduce the chance of collisions. An additional important addition of the DCF is the network allocation vector (NAV). When a sending station transmits a RTS it includes the duration of time it expect to occupy the channel. Any stations that receive the RTS or replying CTS use this time to create a timer that determines how much time must pass before the station can sense the channel for idleness. Anytime a node wishes to check the channel for idleness it must rst check to see whether the NAV timer has expired. This is similar to the protocol used by MACA where the size of the data is sent along with the RTS/CTS frames. The DCF is the most widely 42 used protocol for wireless local area networks (LANs). It has its roots in the previously explained protocols, and many of the protocols [Fang, Bensaou and Yuan 2004, You, Yeh and Hassanein 2003, Wang and Zhuang 2008, Lau and Chan 2006] found in literature use it as a base of reference. Dual-Channel MAC (DUCHA): Zhai et al. propose the Dual-Channel MAC (DUCHA) scheme that uses two distinct channels to overcome the receiver blocking problem and the hidden and exposed terminal problems [Zhai, Wang and Fang 2006, Zhai, Wang, Fang and Wu 2004]. The receiver blocking problem is a specialized case of the exposed terminal problem where a receiver cannot respond to incoming RTS intended for itself due to the transmissions occurring in its sensing range. DUCHA separates the channels into one for control and the other for data. It also uses a busy tone, much like busy tone multiple access (BTMA) [Wu and Li 1988] and dual busy tone multiple access (DBMTA) [Haas and Deng 2002], to establish channel control to overcome the hidden terminal problem. The blocking receiver problem is solved through negative CTS (NCTS) frames. The authors don?t use ACK frames since they claim collisions in the data channel are guaranteed to not occur. However, they do use a NACK busy tone from the receiver that will be used if the receiver thinks it has received corrupted data. The message exchange proceeds as follows: 43 1. RTS: The sender follows the rules employed by 802.11 with regard to the use of the SIFS and DIFS wait times prior to sending a message. Any node must sense the control channel to be free from a signal or busy tone for a period equal to DIFS prior to sending. If the channel is found to be busy it waits for a period of time to pass prior to sending its frame. 2. CTS/NCTS: In DUCHA any node that overhears a RTS responds with a CTS frame after waiting a period equal to the SIFS regardless if the control channel is busy if the data channel is idle. If both are busy, it will ignore the RTS to avoid interfering with the reception of CTS frames at the sender. NCTS frames are returned when the control channel has been found to be idle for at least one CTS frame length long, and the data channel is busy. The NCTS also provides the sender an estimation for how much longer the data channel will be busy . 3. DATA: Once the sender receives a CTS it should begin to send the data if no busy tone signal is present. If it receives a NCTS, it will defer trans- mitting for the estimated time included in the NCTS frame. If neither is received, it assumes a collision has occurred on the control channel and uses a back o strategy accordingly. 4. Busy Tone: The receiver will begin to sense the channel data channel prior to sending the CTA frame to listen for the data from the sender. If it doesn?t begin to receive the rst bits of the frame in due time (determined 44 by the information in the RTS) it will assume the sender couldn?t trans- mit. Otherwise, once the receiver begins to receive data it will transmit a busy tone signal on the control channel to prevent hidden terminals from transmitting. 5. NACK: The NACK is used by the receiver to notify the sender of a prob- lem receiving the data. The receiver uses a timer to determine how long it should take for the data frames to nish sending. If the timer expires and the receiver hasn?t collected the correct data packet, it assumes a problem has occurred and will extend the busy tone signal for a period past the timer expiration. If it successfully received the packet it discontinues the busy tone signal. The sender assumes that if it doesn?t hear the NACK busy tone during the NACK period that the transmission succeeded, oth- erwise if it sees the signal it will begin its retransmission procedure. Multi Channel CSMA MAC: A multi-channel CSMA protocol was proposed by Nasipuri et al. [Nasipuri, Zhuang and Das 1999] where the total bandwidth of the channel was divided into N distinct channels. The channels can be divided either through CDMA or FDMA. The protocol follows the basic principles described in the section of CSMA. When a station wishes to send, it rst senses the last channel it used to determine whether it is available. If the channel is not free a new one is chosen at random, and if no free channel is located it uses a back o protocol to 45 retry later. The author?s later extended the protocol in [Nasipuri and Das 2000] where the optimal channel is chosen based on the power of the signal observed at the sender side. It was further supplemented in [Jain, Das and Nasipuri 2001] to add an additional control channel to the N divided data channels. This channel is used to exchange control frames that allow the sender to determine the best channel to send the data on. The optimal channel is chosen based on the signal-to-noise ratio (SNR) observed at the receiver. Hop-Reservation Multiple Access (HRMA): Hop-reservation multiple access (HRMA) [Yang and Garcia-Luna-Aceves 1999, Tang and Garcia-Luna-Aceves 1998] is a multi-channel protocol for radios using the FHSS spreading technique described in Section 2.3. Previous work has been done with frequency hopping radios [Pursley 1987, Ephremides, Wieselthier and Baker 1987] to use CDMA in an e ective way that required the radios to switch frequencies part way through data packets. HRMA uses very-slow FHSS in order to take advantage of the time-slotting properties that allow an entire frame to be sent in the same hop. HRMA does not do any carrier sensing prior to transmission, and employs the use of control frames in order for a pair of communicating nodes to reserve a hopping sequence (channel). HRMA requires synchronization where one the N available frequencies is dedicated to synchronization. The remaining frequencies are further divided intobN 12 cpairs, where the rst frequency is used for the hop reservation (HR), CTS, RTS, and 46 data frames, and the second frequency is reserved exclusively for ACK frames. This protocol allows for collision free communications even in the presence of hidden terminals [Yang and Garcia-Luna-Aceves 1999]. Multi-Channel Medium Access Control (MMAC): Multi-channel MAC (MMAC) is a protocol meant to extend the functionality of the DCF in IEEE 802.11 by allowing it to dynamically switch between the 11 available channels [So and Vaidya 2003]. Although 802.11 has the support for these multiple channels it can only utilize one channel at a time. This is for backwards compatibility since hosts with a half-duplex radio can either be in receiving or transmit modes. The protocol divides time into multiple xed-time beacon intervals. At the beginning of each of the intervals is an ad-hoc tra c in- dication message (ATIM) window in which ATIM frames are exchanged between communicating nodes so as to coordinate channel assignments. This protocol is e cient since it doesn?t require that the nodes have multiple radio transceivers as is the case for other multi-channel protocols [Jain, Das and Nasipuri 2001, Wu, Lin, Tseng and Sheu 2000, Tseng, Wu, Lin and Sheu 2001]. The protocol does however require that at the beginning of these ATIM windows, or beacon intervals, every node must synchronize itself with all other nodes on a synchro- nization channel in which these ATIM frames are exchanged. Additionally, each node maintains a preferred channel list (PCL) that keeps track of the channels for prioritization. The authors validated the protocol through simulations, and 47 their results demonstrated that MMAC outperformed IEEE 802.11 with regards to throughput. A Jamming-Resistant MAC Protocol for Single-Hop Wireless Net- works: Awerbuch et al. propose a MAC protocol for maintaining link capacity in the presence of adaptive adversarial jamming attacks [Awerbuch, Richa and Schei- deler 2008]. The authors assume that all nodes are synchronized in time steps, and that an adversary can only jam a (1 )-fraction of the time steps for some constant > 0, and that it must make a decision to jam that time step prior to knowing the actions of other nodes at the current time step. As is expected, the nodes on the network are unable to distinguish between adver- sarial jamming and whether other nodes on the network are simply using the channel. The nodes then use mathematical probabilities in order to determine when they are able to transmit. The nodes keep track of the overall time in which the channel is idle and when exactly one successful transmission occurs. It then uses this information to adjust the probability of a time step in which the transmission can occur. The nodes however, do not consider the time steps in which their transmissions have been blocked making the decision algorithm robust to jamming attacks. The algorithm attempts to adjust the probabilities such that the number of time steps that the channel is found idle is equal to the number of time steps in which exactly one message transmitted. If this is 48 not the case, than the probabilities are adapted to make this true. The authors claim that this protocol is robust to adaptive jamming attacks and is energy e cient. However, the paper does not include any simulation results or data from a physical implementation. Furthermore, the authors assume that the ad- versary is limited by the number of time steps that they can jam, and is limited to \bursty jamming". Another interesting problem is the protocol relies upon the knowledge of when a successful transmission occurred, and it assumes it will know when this is true. Advanced MAC (aMAC): Lau and Chan propose a new protocol call advanced MAC (aMAC) [Lau and Chan 2006] that is based o a previous protocol called the Fair MAC with Co- operation between Sender and Receiver (FMAC/CSR) [Li, Gupta and Nandi n.d.]. The goal of FMAC/CSR is to maintain fairness between contending ow for single-hop ows. However, Lau and Chan show that when it is extended to multi-hop ows the fairness breaks down. This is attributed to the use of the 802.11 binary exponential back o (BEB) algorithm that is used for contention resolution which has been shown to be unfair [Li, Nandi and Gupta 2006, Kloul and Valois 2005, Raza ndralambo and Valois 2006]. aMAC aims to resolve the unfairness issues in FMAC/CSR by replacing BEB with the exponential in- crease exponential decrease (EIED) back o algorithm proposed by Song et al. [Song, Kwak, Song and Miller 2003]. The protocol follows four steps: channel 49 estimation, unfairness detection, sender contention, and the EIED algorithm. Channel estimation monitors the channel to estimate ow?s fair share and ac- tual share. Unfairness detection compares the actual share to the fair share to determine how much the actual shared has deviated from the fare share. The sender contention determines the state of a MAC ow (aggressive, normal, or restrictive). Finally, the EIED algorithm is used to govern the contention win- dow. By integrating EIED the authors state that preliminary results show that aMAC maintains superior medium fairness when compared to similar fairness oriented schemes. Real-time MAC (RT-MAC): Real-time MAC (RT-MAC) is a quality of service (QoS) oriented scheme pro- posed by Baldwin et al. that is a variation of the IEEE 802.11 protocol [Baldwin, Nathaniel J. Davis and Midki 1999]. When IEEE 802.11 is used with real-time tra c constraints two issues impact the e ciency of the network: expired dead- lines and collisions. Since IEEE 802.11 has no method of determining whether a frame has exceeded its deadline it will continue to re-transmit these frames, even though they are no longer useful to the receiver. These collisions and re-transmits waste resources needed by other frames to meet their deadlines. RT-MAC remedies this by avoiding the transmission of expired frames. This is achieved by adding transmission deadlines to the packets received from the net- work layer and by using an enhanced collision avoidance mechanism. Whenever 50 a packet is marked as real-time it is marked with a time stamp from the orig- inating station indicating when the packet should be transmitted. The check for an expired packet occurs at several points: when the back o timer expires, prior to sending, and upon the expiration of the timer for the acknowledgment frame. If at any of these points the frame missed the deadline, it is dropped from the transmission queue. RT-MAC has a unique method for improving the collision avoidance mechanism of 802.11. Prior to sending the frame the send- ing nodes chooses the next back o counter value and records it in this frames header. Any station that overhears this frame being sent out will see this back o value and chose one such that it is di erent. This further eliminates the possibility of collisions. Controlled Access CDMA (CA-CDMA): The authors [Muqattash and Krunz 2003] present the Controlled Access CDMA (CA-CDMA) multi-channel protocol which is based on CDMA. It was men- tioned in the prior section that CDMA is a contention free algorithm, however, the authors of CA-CDMA make the statement their modi cation is actually a contention-based scheme. Much like CSMA/CA, CA-CDMA makes use of the control RTS and CTS packets as a channel reservation mechanism. These con- trol packets are transmitted on a control channel separate from the data channel, at xed power. Just like IEEE 802.11 every node receives these packets, how- ever, nodes may continue to transmit if they meet certain criteria determined 51 by the interference margin algorithm presented in [Muqattash and Krunz 2003]. The nodes use the power levels of the received CTS and RTS packets to deter- mine the power that the node can transmit at without interfering with other transmissions. 3.4 Chapter Conclusion This chapter reviewed the protocols necessary to understanding the current state of MAC layers for ad-hoc wireless networks. The protocols vary from those which rely on contention free schemes, to those concerned about quality of service (QoS), and to the protocols that use multiple channels for either doing control or for multiple data paths. In relation to the jam-resistant goals of this research only one such protocol was found which directly concerned itself with adversarial jamming of the wireless channel. Awerbuch et al. [Awerbuch, Richa and Scheideler 2008] proposed the Jamming-Resistant MAC Protocol for this purpose, but only handled jamming by attempting to send when it predicted no adversarial jamming was occuring. Many of the other protocols address the hidden and exposed terminal problems through the use of control frames, and multiple channels. Protocols such as CSMA/CA, MACAW, DUCHA, and FAMA provide many di erent approaches to solving the hidden and exposed terminal problems, and will be considered for the design of BBC-MAC. 52 Chapter 4 BBC-MAC Initial Protocol Design 4.1 Chapter Introduction The medium access control layer for noisy channels will build upon the current state of ad hoc wireless communications by creating a reliable data link through the use of the BBC algorithm and its error-correcting properties. Combining BBC with the traditional facilities of the data link layer will transform the raw data transmission facility provided by the software-de ned radios into a jam-resistant communications link for mobile ad-hoc networks. This layer will work as a single-hop protocol that will only be concerned with delivery of data to the next terminal, and will not consider multi-path routes for node-to-node delivery. It will be left to the network layer to determine how to properly route the data. 4.2 Protocol Requirements To achieve a reliable data link the new layer must address the issues of framing, addressing, ow and error control, and a primary focus on controlling the channel. A nal requirement for the algorithm to operate properly is the ability to dynamically adjust the coding properties of the BBC algorithm to adjust to the level of noise. By adjusting the coding properties that determine the level of jam-resistance, the layer can sustain link communications up to a certain level of noise. 53 Framing: Physical limitations of the software de ned radios and coding parameters of the BBC algorithm will require that larger packets received from the network layer be broken into smaller frames for encoding and transmission. On the receiving end these will have to be re-combined for proper delivery to the upper layers. The size of the frames can be a xed or dynamic size, but since the size of the frames could be in direct relation to the message length that is encoded by the BBC algorithm, it will have to be a dynamic size. While this was initially determined a requirement, I realized that the BBC algorithm already does framing of data, and for the prototype implementation I considered any data the upper layer passed to be a single data frame. Addressing: Every node in the transmission range must have a unique iden- ti er so that a node receiving a message knows whether they are to be discarded or when the message was meant for it . As mentioned previously, the routing will be considered a job of the network layer, and it assumed the network layer will have a unique identi er for this purpose. This same identi er will be used at the data link layer for addressing. Considering the requirement of the rout- ing, it is anticipated at this time that the data link layer will not keep state information pertaining to nodes in its transmission range. However, this might prove to be useful during research and will not be taken away from considera- tion. The nal protocol prototype assumes that it will be given the address of the node upon initialization. 54 Flow and Error Control: An important property for creating a reliable link is in the ow and error control algorithms. Flow control must alleviate congestion of the link by limiting the amount of data it sends, and error control must be able to recover from frames that the BBC algorithm?s error correcting facility could not handle. It is anticipated a modi ed version of the selective repeat automatic repeat request algorithm described in Section 3.2 will be used for this purpose. The nal implementation does error control on the single data frame it sends by using an acknowledgment frame. Future work would be directed at doing error control on the individual BBC codec frames as well. Access Control: Controlling access to the channel is the most important aspect of this protocol. While the BBC algorithm allows for communications to continue even in the presence of interference, avoiding channel saturation is important. If nodes were left to freely transmit whenever they chose, the level of noise (jamming/collisions) on the channel would continue to grow to the point where the error correcting aspect of BBC could not overcome the problem. To overcome the hidden and exposed terminal problems described in Section 2.4, techniques inspired by the protocols discussed in Section 3.3 will be used. It is anticipated that the protocol will not rely on carrier sensing much like MACA and MACAW, but will incorporate control frames to reserve channel access. The control frames will carry several important pieces of information. The rst is the the size of the data that is going to be transferred in the DATA frame. This will allow any node that overhears this transmission to know how long it 55 should defer its transmissions. The second parameter included in both frames will be the received signal strength indicator (RSSI) value. Upon sending a RTS frame, the sender will include its most recent RSSI, and the receiver will similarly reply with its most recent RSSI value. This is used to prepare the nodes for the proper level of jam-resistance. The nal protocol implementation does use the control frames to reserve the channel for the two communicating nodes for a limited amount of time. Dynamic BBC: Maintaining the link will rely upon the BBC algorithm to overcome noise in the channel. However, the level of noise is likely to be dy- namic in relation to the number of nodes active in the network, and the level of determination by an adversarial jammer. For this reason the layer must be able to adjust the coding parameters of BBC to allow for dynamic jam-resistance. The speci c properties at this time that changes the level of jam-resistance are the hash function and the expansion size of the original data. These two prop- erties determine how large the BBC packet is and where the indelible marks can be placed. The RSSI value included RTS/CTS frames will be used to de- termine at which level of jam-resistance the two nodes will communicate. The node with the highest RSSI value will be the determining level that the remain- ing DATA-ACK communications occur at. This service will also be available for upper layers to adjust. This is a requirement for allowing varying levels of priority from upper layer packets. The nal prototype achieves dynamic BBC by altering the packet expansion in the BBC codec, and adjusting this value 56 based upon the Received Signal Strength Indicator (RSSI) value contained in the control frames. 4.3 Chapter Conclusion The Single-Hop Medium Access Control Layer for Noisy Channels protocol has been conceived to address the many problems that currently a ect the current state of medium access control for MANETs. The protocol will be designed to maintain a reliable communications link in the presence of noise, via either intentional or unin- tentional jamming, and will dynamically adjust either by the layers own mechanism or as dictated by upper layers. The protocol aims to provide data transfer reliability by developing a new layer built upon the foundation of the BBC algorithm. By focusing on maintaining a communications link in the presence of jamming, it is expected that the protocol will be able to overcome obstacles such as adversarial attacks, pre-shared secrets, and the hidden and exposed terminal problems that other protocols fail to. 57 Chapter 5 Protocol Design and Implementation Phase 5.1 Chapter Introduction The previous chapter discussed the initial protocol design and reviewed some of the basic requirements and rudimentary methods for achieving the goals of the proto- col. This chapter covers the end design for the protocol, and how it is implemented. The protocol requires the use of many di erent software and hardware components. Implementation and testing for so many pieces becomes more di cult as the complex- ity of the layer increases. Initially, many of the pieces were built simultaneously and then an attempt at testing was made. However, later development required that new pieces be tested individually in order to reduce the new number of variables which needed to be accounted for when the component failed. As previously noted, one of the goals of this research is to implement and validate the protocol on physical hardware. However, the MAC layer requires that a physical layer exist prior to any implementation on it occuring. The creators of the BBC [Baird, Bahn, Collins, Carlisle and Butler 2007] algorithm had created a basic physical layer implementation for the purposes of research. Their implementation takes a le as an input, encodes it using the BBC algorithm, and then modulates it for proper transmission with the Software De ned Radios (SDRs). The modulated data is then transmitted with a python script that repeats until user-terminated. A similar series 58 of steps occurs on the receiver?s end. A python script receives data from the USRP until user terminated. Then the demodulator is run on the received data and the decoder. If a successful transmission occurred, the same le sent should be in the receivers folder. The code base from this prototype was used as the starting point for the creation of the new upper-layer MAC protocol. The remainder of this chapter begins with a breakdown of the system components used for the creation of this new layer, and then follows with a detailed look at the various operations at the physical layer and those which occur in the BBC-MAC layer. 5.2 System Components The nal implementation presented here relies upon many software and hardware components to create the end prototype. This section covers the di erent components in order to familiarize the reader with the equipment used. Certain components have a direct relation to the way the protocol was designed, speci cally, components like the Universal Software Radio Peripheral (USRP) and the type of daughterboard used have an impact on the hardware abilities of the layer. 59 5.2.1 Hardware Components Universal Software Radio Peripheral (USRP): Figure 5.1: Universal Software Radio Peripheral External View The Universal Software Radio Peripheral (USRP) is the main hardware compo- nent used for developing Software De ned Radios (SDRs). Figure 5.1 shows the external casing of this component. The USRP1, developed by Ettus Research, LLC, pictured in Figure 5.2, was used for the development and testing during this research. The USRP1 contains an Altera Cyclone Field Programmable Gate Array (FPGA), and has four extension sockets that support up to four daughterboards. The FPGA drives four high-speed 12-bit analog-to-digital con- verters (ADC) capable of 64 Mega-Samples/second and four high-speed 14-bit digital-to-analog (DAC) converters capable of 128 Mega-Samples/second. The 60 ADCs are used during the receive chain, and the e ective sampling rate is deter- mined by the decimation rate. Likewise, the DACs are used during the transmit chain and the e ective sampling rate is determined by the interpolation rate. The USRP connects to the external computer through a Cypress EZ-USB FX2 High-speed USB 2.0 controller that allows for speeds approaching 32 Mbytes/s. USB 2.0 speci cation allows for up to 480 Mbit/s or 60 Mbytes/sec, but the current FPGA used doesn?t support the full bandwidth of USB 2.0. This is because the Cypress USB controller uses the bulk transfer mode of USB 2.0, which is limited to roughly 32 Mbytes/s. Figure 5.2: Universal Software Radio Peripheral Internal Hardware 61 RFX-1200 Daughterboard: The USRP has the support for two transmit sockets and two receive sockets, al- lowing for up to two receive daughterboards and two transmit daughterboards, or two transceiver daughterboards. The daughterboard used during this re- search is the RFX-1200 transceiver, pictured in Figure 5.3, that operates in the 1150-1450MHz frequency range with a transmit power of 200+mW (23dBm). The board supports both transmitting and receiving on the same connector, but also supports an auxiliary receive port which allows transmit and receive to occur on separate frequencies. The board has a 30 MHz bandwidth and 70 dB Automatic Gain Control (AGC) range with adjustable transmit power. The nal useful feature which is crucial to this research is the built-in analog Re- ceived Signal Strength Indicator (RSSI) measurement from an auxiliary ADC. This research uses two RFX-1200s in each USRP. VERT400 Vertical Omnidirectional Antenna: The nal component for the radios is the VERT400 omnidirectional antenna pictured in Figure 5.4. This is a seven inch tri-band antenna operating at the 144Mhz, 400Mhz, and 1200Mhz frequencies. Each USRP has two daughter- boards and so there are two of these antennas on each USRP. 62 Figure 5.3: RFX-1200 Transceiver Daughterboard Laptop Computer: The nal hardware component is the computer used to drive the USRPs. In this research, an Apple MacBook Pro running an Intel Core 2 Duo operating at 2.53 GHz with 4GB of DDR3 system memory was used. The computer has an impact in several stages of this research. The rst is at the USB interface where this laptop has two USB 2.0 ports. The second is during the decoding stage of 63 Figure 5.4: VERT400 Antenna received data. The speed of the processor can have a signi cant impact on how fast this stage occurs. Furthermore, the amount of system memory available impacts how many samples from the received sink le the computer can load into memory at a single time for decoding. 5.2.2 Software Components The software components involved in this system are limited to C and Python. The BBC program and the jammer for this research were both written in C. The remainder of the software components were all written in Python due to its ease of development and because the GNU Radio API for USRP interaction is written in Python. GNU Radio Software Library: GNU Radio is a free software toolkit created to give users the ability to learn and create wireless protocols. The GNU Radio Library contains all the necessary 64 runtime and processing blocks to interact with the USRP. The client library is largely written in Python with the signal processing blocks developed in C++. BBC Encoder: The BBC software is written in C and can be found at the site maintained by William Bahn [Bahn March 2009]. This software performs the BBC encoding and also takes on the physical layer task of modulating data into the proper format for the radio transmit script for transmission. The algorithmic details of this software were discussed in Section 2.5. When data is being encoded the following steps occur: 1. The data to be encoded is dumped to a le speci ed by the con guration le, and loaded into memory. 2. The data is then split up into BBC Frames with the following format: { StreamID: 16-bit integer that identi es the data stream. { Checksum: 32-bit checksum value for the payload. { Sequence Number: 16-bit integer indicating which sequence number in the stream this frame is. { Data Bits: 16-bit integer indicating that actual number of bits con- tained in the payload { Data: The payload for this frame. Size is determined by the con gu- ration le. 65 3. Each frame is then sent to the BBC Encoder where the frame is encoded and placed into the packet bu er. 4. The contents of the bu er are then modulated into the proper format and placed in a sink le for transmission. The software was largely left untouched with the exception of a modi cation for the con guration le to accept absolute paths to the source and sink les. The source is compiled into a binary executable which is called upon in the interface. BBC Decoder: The BBC decoder is part of the same piece of software as the encoder and was written by William Bahn [Bahn March 2009]. The BBC decoder performs simi- larly to the encoder, but in reverse. When there is data available for processing the following steps occur: 1. The data that has been received from the radios is loaded into memory and sent to the demodulator, where the received data is transformed into bytes and placed in a bu er for processing. 2. Each bu er read location is then sent to the decoder where it attempts to decode valid messages. Those that it does nd are sent to the sink module. 3. The sink module collects the messages belonging to the same streamid and places them in order for output to the sink le. 66 4. At the end of the execution the sink module purges its contents to the sink le. This part of the code has also been left mostly unaltered, with one exception. If, during the purge of the sink, it is discovered that there are missing sequence numbers, the sink will not dump the contents to the le. BBC-MAC is not doing frame control on the BBC frames at this time, it is unnecessary to output to the le if parts of the transmission are missing. From the point of view of the layer it is just considered a failed transmit or receive. The nal source code for the BBC software used during this research is listed in Section A.3. Python USRP Receiver Script: In order for the layer to interact with the radios, a receiver script is necessary. This is a modi ed version of the example usrp rx c le.py script that comes with the GNU Radio library. The source code can be found in Section A.2.1. The script accepts several important parameters: { freq: This is the frequency that the radio should be tuned to. { nsamples: This is used to tell the receiver it should collect nsamples samples and then exit. This parameter is used to limit the size of the le the BBC decoder can load into memory. { decim: This parameter is the decimation rate of the FPGA. The FPGA can receive at 64 Mega-Samples/second. If the decimation rate is set to 128 then the e ective sampling rate is 64e6128 = 500000 Samples/sec. 67 Beyond initiating the communications with the radios and collecting the sam- ples, this script also performs the important task of collecting the Received Signal Strength Indicator (RSSI) value. Upon starting the receiver script a sep- arate thread of execution is initiated that continuously calls the auxiliary ADC and asks for the RSSI measurement. The thread averages the last 1141 calls and outputs the highest average from the last twenty averages to a le located in the folder for the speci ed radio. These operations can be found in Listing 5.1. The number of reads to the ADC in a single second is roughly 1141, and by only returning the highest average in the last twenty seconds we are able to give the layer a better idea of what level of jamming has recently occured. This is a better safe than sorry approach to the con guration of the jam-resistance. It allows the communicating nodes to con gure their jam-resitance levels to an appropriate level of jamming which has recently been measured, and could possibly occur again in the middle of the transmission. def GetRSSI( self , d, t) : reads = [] avgs = [] while self . rssi run : tmp = self .u. read aux adc ( self . rx subdev [0] ,0) reads .append(tmp) self . rssi = sum( reads [ 1140:])/1140 avgs . append( self . rssi ) file = open( receive . fn+" ssi " , "wt") file . write ( str (max(avgs [ 20:]) )) file . close () Listing 5.1: usrp rx c le.py lines 190-200 68 Python USRP Transmitter Script: The transmitter script handles the duties of transmitting the encoded data with the USRPs. The source for this le can be seen in Section A.2.2. It is a modi ed version of the bbc tx.py script included on the BBC Real-time Research Engine website. The important parameters for this script are: { rf freq: This is the frequency that the radio should be tuned to. { interp: This parameter is the interpolation rate of the FPGA. The FPGA can transmit at 128 Mega-Samples/second. If the interpolation rate is set to 256 then the e ective sampling rate is 128e6256 = 500000 Samples/sec. { jammer: This parameter tells the script how to create the transmission ow graph. 0 = no jammer, 1 = pulse jammer, 2 = Gaussian jammer. { jammer level: This parameter indicates the jamming level to be used if a jammer type is speci ed. { tx time: This parameter tells the ow graph how long it should transmit the data. This time is determined by the BBC-MAC layer based upon the size of data and the con guration options for the encoder. The modi cations were made so that it was possible to transmit on both daugh- terboards simultaneously. This is required since whenever a valid transmission is occurring there are three possible con gurations: 1. The encoded data is being transmitted on one of the daughterboards only. 69 2. The encoded data is being transmitted on one daughterboard and simul- taneously the pulse jammer is being transmitted on the other. 3. The encoded data is being transmitted on one daughterboard and the Gaussian jammer is being transmitted on the other. Pulse Jammer: In order to test the error-correcting ability of the BBC algorithm I created a novel jammer that would send out data at the same symbol rate and modulation scheme as is used by the BBC executable. The main program is a modi ed version of the BBC source code with only the necessary components remaining. The source code for this jammer can be found in Section A.4. It accepts as parameters the jammer level to be used and the number of samples to create. The jammer level is a value in the range of [0,64]. The level indicates that for every 64 time steps, that level time steps should contain a high pulse. The relevant code for this is seen in Listing 5.2. For example, if the jamming level was 13, the program would randomly select 13 locations to set the bit to high in an 64-bit variable. The program also guarantees that there will be 13 locations by ensuring that each new value was not already chosen. The program then pushes the four bytes of that variable onto the bu er and send it to the modulator. This is repeated for as many samples as are needed. 70 for( i = 0; i<(samples/(32 sizeof(unsigned long long))) ; i++)f buf number = 0; ran number = 0; for( j=0;j < jammer level ; j++)f ran number = rand()%(8 sizeof(unsigned long long)) ; while (marked[ ran number]==1)f ran number = rand()%(8 sizeof(unsigned long long)) ; g marked[ ran number ] = 1; // set the bit at ran number to 1 buf number j= (1 << ran number) ; g memcpy( buffer >buffer+buffer >write , buf number , sizeof(unsigned long long)) ; buffer >write+=sizeof(unsigned long long) ; for( j=0;jready = 1; Modulate( config , buffer , modem, sink ) ; g memset(marked ,0x00 , sizeof(unsigned long long) 8) ; g Listing 5.2: jammer.c lines 71-91 The goal of the jammer is to create an attack on the protocol by transmitting random data in the same fashion as the valid encoded data. It aims to test the limits of the error correction of the BBC algorithm and demonstrate an actual interference in a similar fashion as the toy example with noise did in Section 2.5.4. To illustrate how this will a ect the data being transmitted, Figure 5.5 shows what BBC encoded transmission looks like on a software oscilloscope without interference, and Figure 5.6 shows how it looks once we run this jammer at level 20 jamming. While these images are not taken at the same time in the transmission, it is clear that in Figure 5.5 the pulses are fairly distinct with 71 proper spacing, but in Figure 5.6 we see some interference and a signi cantly higher density. Figure 5.5: BBC Encoded Transmission without Noise Figure 5.6: BBC Encoded Transmission with Pulse Jammer Noise Gaussian Jammer: The other jammer used during testing is a Gaussian noise source generator that is part of the GNU Radio library. The generator asks for an amplitude as a parameter which determines the max amplitude of the signal containing the noise. Again, in the script the jammer level is in the range of [0,64] where the level is multiplied by 500 to determine the max amplitude to pass to the Gaussian noise generator. 72 5.3 Physical Layer Implementation This section will cover in greater capacity the operations that are carried out at the physical layer to allow for the BBC-MAC layer to function properly. The physical layer is responsible for the physical transmission of the data that the upper layer passes to it. These responsibilities include the communication with the USRPs, BBC encoding and decoding, and modulation of data for proper transmission. This protocol assumes that all operations with the BBC algorithm are considered part of the physical layer, and the upper layers simply control the operations through con guration adjustments as necessary. The task of communicating with the USRPs is handled by the radio scripts discussed in Section 5.2.2. The scripts are then controlled by the interface class of the BBC-MAC software which handles the control of the physical interface. This class can be found in Section A.1.1. It also handles the execution of the BBC executable for the encoding and decoding of data. The BBC executable handles the complex task of encoding and modulation and the reverse task of demodulation and decoding as discussed in Section 5.2.2. Figure 5.7 shows a high-level depiction of the operations at the physical layer. Whenever the radio is in receiver mode, the decoder is being continually ran on the data that has been received. The transition from receiver to idle can occur as the result of the following situations: 1. When the interface has been told to transmit data by the BBC-MAC layer. 73 Figure 5.7: Physical Layer State Diagram 2. If the decoder signals that that it has successfully decoded data, the receiver script is exited and the received data purged, and then the receiver is started again. The data that has been decoded is passed onto the BBC-MAC Receiver class for processing. 3. When the receiver script has collected the number of samples speci ed by the nsamples parameter. This implementation will exit after collecting 16 million samples. The decoder is allowed to nish a nal attempt to decode the data before the sink is purged and the receiver restarted. 4. If the decoder has been running longer than the time allotted for it to run. In this situation the data in the sink le is considered unusable, the receiver is stopped, and the sink data is purged before beginning the receiver again. The node is never in an intentional continuous state of idleness. Any received data is handed to the upper layer for processing and the node returns to receiving as quickly as possible. In this sense idle is a transitional state. 74 A nal component of the interface is the Network Allocation Vector (NAV) timer. Recall from the overview of the 802.11 protocol in Section 3.3.2 that it uses this timer to determine how long it should defer transmitting for. Likewise in this protocol, if this value has been set by the BBC-MAC layer, then the interface will not transmit any frames until it has expired. The majority of the states that the physical layer can be in are controlled by the BBC-MAC layer. Design characteristics of that layer determine whether a node can transmit data or if it should be in receive mode. 5.4 BBC-MAC Implementation BBC-MAC is where the majority of all work has been directed. It controls and directs the physical layer and transforms it into a reliable medium for communica- tions. The implementation of the protocol is a non-trivial approach to creating a jam-resistant Medium Access Control (MAC) layer that can adapt to the level of noise in the channel. The protocol adapts by measuring the interference in the chan- nel and changing the coding con guration used at the physical layer. The layer is made up of many di erent software components that can be seen in Section A.1. This section will cover the main components of the protocol in such a way as to give com- plete coverage of operations at the layer. Figure 5.8 shows the high level operations in the BBC-MAC implementation. 75 Figure 5.8: BBC-MAC State Diagram BBC-MAC Frame: The layer uses a common header format for all frame types. The header is relatively small, only 21 bytes. The format of the header is as follows: { Destination Address: This is a 16-bit integer that indicates the address of the node where this data is being delivered to. { Source Address: This is a 16-bit integer indicating the address of origi- nating node for this message. { Type: This is an 8-bit integer indicating the type of the frame. 1 is a Request-to-Send (RTS) frame. 2 is a Clear-to-Send (CTS) frame. 3 is a Data frame and 4 is an Acknowledgement (ACK) frame. 76 { Source Stream ID: This is a 16-bit integer indicating the stream ID that this data belongs on the transmitter. It is used for identifying the handler the data is destined to on the transmitters end. { Destination Stream ID: This is a 16-bit integer indicating the stream ID that this data belongs to on the recipients end. It is used for proper delivery of data to the handler for the stream on the receivers end. { RSSI: This is a 16-bit integer for the Received Signal Strength Indicator (RSSI) level at the time of transmission. It is used during the RTS/CTS handshake for con guration of the encoding for subsequent data frames. { CRC: This is a 16-bit integer containing the Cyclic Redundancy Check (CRC) of the payload. { Timestamp: This is a 64-bit integer containing the time at which this frame was transmitted. { Payload: Field containing the payload of the frame. Receiver: The Receiver is the module that interacts with the interface class for all inbound data. The layer views all communications in the forms of streams, where every stream should have an ID associated with it. The Receiver maintains a list of all handlers managing existing streams for both inbound and outbound streams. Whenever data has been received at the interface it is enqueued in the Receiver?s 77 inbound queue. Once the receiver is ready to process the data it will examine the Destination Stream ID eld in the header and the following steps take place: { ID is zero: 1. First attempt to locate a handler which has marked its destination stream ID as the one listed as the Source Stream ID in the current frame. 2. If no such handler exists then this is a new stream. Create a new RxHandler with a stream ID unique to this node. { ID is non-zero: 1. First attempt to locate a handler with the ID matching this ID, and pass the data to it. 2. If no such handler exists, create a new RxHandler with a stream ID matching the Destination ID from the header. The nal component of the Receiver is the callback routine. This is used when an RxHandler has ended itself. If the handler was controlling the interface it will relinquish control of the interface. This will remove the handler from the list of handlers, clean up the memory it was occupying, and then if the statistics module has been turned on it will print out the statistics that it maintained for that stream. The routine also accepts the data that the RxHandler received, if any, and passes it to the upper layer. 78 Transmitter: The Transmitter module handles all interactions with the upper layer for data that is outbound. Whenever the upper layer has data to transmit it enqueues it in this module?s queue. The data is immediately popped from the queue and a TxHandler is created with a unique Stream ID to handle the remainder of the operations associated with the outbound data. Like the Receiver, the Transmitter has a callback routine that is used when the handler has terminated itself. The handler will pass the routine a message to deliver to the upper layer indicating a failure or a success. It will then remove the handler from the list of handlers and clean up the memory being occupied by the handler. If this handler was controlling the interface it relinquishes control of the interface. Finally, if the statistics module is on it will print out the statistics that the handler maintained for the stream. Handlers: The handlers are where most of the decisions in the protocol are made. They maintain the data and operations associated with a stream. There is a handler for inbound streams called an RxHandler and likewise for outbound streams there is a TxHandler. The interface maintains a queue of handlers that are waiting for control of the interface. The handlers also are what make the adap- tive protocol possible. After the RTS/CTS handshake is made the handlers will adjust the con guration to the appropriate jam-resistance level based on 79 the RSSI value. There are ve con gurations where each weigh the bene ts of throughput versus jam-resistance. The following outlines the detailed opera- tions of the handlers: { TxHandler: As soon as the Transmitter has data in its queue it creates a TxHandler with a new stream ID. This ID becomes the source stream ID in any outbound BBC-MAC frames from this handler. The handler maintains two queues. The rst is a send queue that is used by the interface to get the next frame that it should transmit from this handler. The second is the receive queue. Recall that when the interface receives data it passes it onto the Receiver module, which then locates the proper handler for the data. This queue is where the Receiver will push the data. Finally, the handler maintains a BBC Con guration object that holds the con guration options that should be passed to the BBC encoder/decoder executable whenever this handler has control of the interface. The following steps outline what happens after the TxHandler has been created: 1. Set the con guration?s source ID to the current stream ID. Recall that at the BBC encoding stage each time data is sent to the encoder it creates individual BBC frames with sequence numbers belonging to a stream ID. This is that value. 80 2. If the interface is operating in dynamic mode the con guration should be set for the highest jam-resistance level, otherwise leave the con g- uration as is. 3. Create a Request-to-Send frame with the node?s current RSSI value. RTS frames contain the size of the data to be transmitted as the payload. 4. Enqueue the RTS frame in the queue and then place this handler in the interface?s handler queue. Once this initial phase has occurred, the handler must now wait for the interface to signal it via a callback routine that it has transmitted the frame. When the callback is signaled, the interface passes it a copy of the frame it just transmitted and the length of time the interface passed to the bbc tx.py script. The following outlines what occurs when the callback is called with the two frame types that the transmitter sends: Request-to-Send Frame: The handler makes a blocking call to the receive queue that times out after a length of time equal to the transmit time plus bu er time. Blocking Call Returns: 1. The received frame is checked to make sure it is a RTS frame. If it is not, a node is responding with an incorrect frame and it is ignored. 81 2. The RSSI value in the frame is compared to the RSSI value which was sent in the RTS. If it is larger than our RSSI value, then it is used as the determining value for the jam-resistance level. 3. If the interface is in dynamic mode, adjust the con guration to the appropriate jam-resistance level based on the RSSI value. Once the RSSI value is obtained, the handler will do a secondary check on the current RSSI value at the node. If the current value would cause the con guration to jump to the next level of jam- resistance, a new RTS frame is created and sent out to re-adjust the receiver. This step is ignored if we are at the limit of RTS re-transmit attempts, and continue on to transmitting the data frame. 4. Create the data frame and place it in our outbound queue. Blocking Call Times Out: 1. Check to make sure we have not exceeded our retransmit at- tempt value. If we have, then the handler will terminate itself and pass a failure message to the Transmitter module. 2. Otherwise, the frame is updated with the current RSSI value and placed in our outbound queue. 82 Data Frame: The handler will make a blocking call to the receive queue to get data that will timeout after thirty seconds. Blocking Call Returns: 1. The received frame is checked to make sure it is an ACK frame. If it is not, a node is responding with an incorrect frame and it is ignored. 2. Otherwise, the handler has received an ACK frame and this stream has been completed. The handler will terminate itself and signal a successful transmission to the Transmitter module. Blocking Call Times Out: 1. Check to make sure we have not exceeded our retransmit at- tempt value. If we have, then the handler will terminate itself and pass a failure message to the Transmitter module. 2. Otherwise, the frame is re-enqueued in our outbound queue. If the handler is capable of receiving the CTS from the other commu- nicating node, it will claim ownership of the interface and start a timer equal to the length of time in the CTS frame that was received. The handler will continually check to see if the timer has expired, and if it has then the handler must give up control of the interface and signal a failure to the upper layer. This is to ensure fairness on this node for other handlers to gain control of the interface, as well as maintain 83 the mutual agreement of how long any two communicating nodes can claim ownership of the channel. { RxHandler: The RxHandler is created by the Receiver class, and has a signi cantly less complex role than the TxHandler. Upon creation, it is given a stream ID to use as a self identi er. Any frames that it transmits will use this as the Source Stream ID in the BBC-MAC frame header. Like the TxHandler, the RxHandler maintains two queues. The rst is the receive queue where any date from the Receiver module is placed, and the second is the send queue used by the interface to get the data it is to send from this handler. When data is placed in the handler?s receive queue, the following steps occur for each of the following frames: RTS Frame: 1. The frame is rst checked to make sure the destination address is equal to the address speci ed in the interface. If it is not, then the frame is discarded. 2. Compare the RSSI value in the frame to the current RSSI at this node. Select the higher value as the RSSI value for the purposes of con guration adjustments. 3. Create a CTS frame with the selected RSSI value and enqueue it in our send queue. 84 4. At this point this node should have the higher of the two RSSI values. Using the size of the data in the RTS payload this node will estimate the time needed on the channel for the codec con- guration based on the RSSI value and the size of the data and place this in the CTS frames payload. 5. The handler will now wait for the interface to signal that it has transmitted this frame and begin a timer equal to the length of time that was previously estimated that the channel would be needed for. 6. Adjust the jam-resistance level based on the RSSI value and claim ownership of the interface. CTS Frame: If an RxHandler gets a CTS frame it indicates that this CTS was not destined for this node and two other nodes are trying to claim the channel. The value in the payload is extracted and the NAV timer on the interface is updated with that value. Data Frame: 1. The frame is checked to make sure it was destined for this node. If not, it is discarded. 2. An ACK frame is created and placed in the send queue. 3. The handler signals the Receiver class of a successful data recep- tion via the Callback and the handler is terminated. 85 ACK Frame: This frame should have been delivered to a TxHandler if it was meant for this node. The frame is discarded and the handler terminated. 5.5 Chapter Conclusion The purpose of this chapter was to introduce the reader to the main components that make up the implementation of the BBC-MAC protocol. The chapter began with an introduction to the hardware and software components that make it possible to achieve the goal of testing the protocol on physical hardware. We then discussed the new jammer that was created to be used during the subsequent experimental phases. The implementation details of the physical layer and the BBC-MAC protocol were covered in appropriate detail in order familiarize the reader with how the layers interact in order to create the reliable data link layer. The implementation presented in this chapter was meant to create a working prototype in order to demonstrate the feasibility in creating a MAC layer that can adapt to the level of noise detected on the channel. Some of the design decisions in the protocol could have been taken in other directions, but the prototype that has been developed here suits the purpose of demonstrating technical capability of incorporating the BBC algorithm into a protocol stack in order to provide adaptive jam-resistant communications. 86 Chapter 6 Phase I Experiments: Adaptive Coding Investigation 6.1 Chapter Introduction As noted in the previous chapter, the protocol must adjust the coding param- eters used on the BBC algorithm to meet the current needs of the channel. If the channel has a low degree of noise then minimal jam-resistance is needed to increase the throughput. The reverse situation must also be addressed. If there is a high level of interference then greater jam-resistance should be used in order to over- come the noise. In the explanation of the protocol, I settled on using ve levels of jam-resistance, plus an additional level for the smaller RTS/CTS frames. By using ve levels of jam-resistance, the protocol will be able to demonstrate its capacity to adapt to the level of noise in the channel. The goal of this experiment is to test each con guration against di erent levels of jamming, and against several jammers. The experiment clearly showed the tradeo between jam-resistance and throughput, and illustrated that with just one parameter adjustment of the BBC algorithm di erent levels of resistance can be achieved. However, in both jammer types an upper bound was reached where the adjustment made no statistical di erence in the reliability of the con guration. 87 6.2 Experiment Setup The hardware con guration for this experiment required two USRPs, and at least one must have two daughterboards. The USRPs were fairly close to each other; only four feet separated them. Inside each USRP are two daughterboards, where the antennas in each are separated by 3.5 inches. The experiment calls for a jammer to be running while a transmission is occur- ring. I made the design decision to always have the jammer running for at least as long as the transmission was occurring. This allows me to guarantee that the origi- nating signal is always being jammed from the source of the transmission. For this reason, the jammer code was incorporated in the transmitter script so this could be achieved. Two types of jammers were used during this phase of experiments. The rst is a pulse jammer that I created to be a targeted attack on the decoder and the modulation scheme currently used. The second is a Gaussian noise source generator that is part of the GNU Radio API. Each jammer has a range of [0,64] to select for the jamming level. On the pulse jammer the level indicates how many time steps should contain a high pulse, and the Gaussian jammer uses the level to determine the max amplitude. For this experiment the data used for encoding and transmission was a single 802.3 ethernet frame that is 1514 bytes long. The hexadecimal string for this data is listed in Section B.1. After examining notes about the BBC algorithm and reviewing the source code, it is fairly obvious how greater jam-resistance can be achieved. An examination of 88 Algorithm 2 in Section 2.5.3 shows that the upper bound on the decoder is O(2n). The decoder time grows exponentially with respect to the number of 1 bits in the \buckets" for the current message being decoded, or essentially the mark density. On the BBC Real-time Engine website [Bahn March 2009], it is stated that in general, in order to achieve greater jam-resistance the con gurations need to lower the mark density during the encoding. There are two parameters which determine the length of a packet and therein the mark density. The rst is the codec message bits paremeter, which says how many bits long should a message be. The second is the codec expansion parameter, which determines the length in which a BBC packet will be. Multiplying the codec message bits codec expansion gives the length of a BBC packet or the packet bits parameter. The value also impacts the spreadability of the pre x hashing done when determining where a pulse should be located at, and in some cases how many marks there will be. // Generate mark location for present prefix location = 0; for ( i = 0; i < SHA1 HASH DWORDS; i++) location += (( codec >digest ) >Message Digest [ i ])<packet bits ; Listing 6.1: codec.c lines 343-347 The code snippet above shows where in the code this is of importance. The upper bound of where a location can be is in the unsigned integer variable location. How- ever, it is further impacted by the packet bits discussed before. By raising or lowering 89 the codec expansion di erent mark densities can be achieved. A rough estimation for the stream density can be done by dividing the number of marks the encoder created, N, by the number of samples that were created, S. The increase in expansion also increases the number of marks produced. This is because the modular operation on the location is on a larger number, and thus fewer pre x hashes will map to the same location increasing the spreading of the marks. Expansion N S Density Transmit Time Throughput 50 31768 716832 4.43% 6s 2019bps 75 32865 1075232 3.06% 9s 1346bps 100 33451 1433632 2.33% 12s 1009bps 125 33873 1792032 1.89% 15s 807bps 150 34054 2150432 1.58% 18s 673bps 175 34257 2508832 1.37% 21s 578bps 200 34404 2867232 1.19% 23s 527bps RTS @ 500 3406 1433632 0.24% 12s 19bps Table 6.1: Expansion Factor Impact I decided to leave the codec message bits parameter at the default of 512 bits or 64 bytes, and instead vary the codec expansion. This decision was made because I wanted to reduce the number variables changed during testing and implementation, and instead focus on adjusting the parameter which varies the mark density. Table 6.1 shows the result of running the encoder for the chosen levels of expansions. It also lists the transmit time required to transmit each con guration. Recall that for these tests a 1514 byte ethernet frame was used. The transmission time is a simple calculation based around the number of samples that were created. The sampling 90 rate of the USRP?s is 500,000 samples a second, and for each bit modulated there are 4 samples created, and so the time required to transmit isd4 S500000e. The ceiling of that value is used in order to obtain an integer result. This information also lets us display the nominal throughput as a function of time. The table clearly illustrates that as we increase the expansion factor we decrease the stream mark density, but also decrease the throughput. For each expansion factor, thirty messages were sent at each jamming level until it reached two levels in which no messages made it through. It was decided to stop the tests at that point since even if one or two messages got through in subsequent levels it would be statistically irrelevant. A script was created which would begin the receiver, then begin the transmitter, and once the transmitter was nished it would end the receiver script and begin the decoder. The decoder was given thirty seconds to decode the data received. Once that time was expired it was considered a failed transmission. Successful decodes where then checked for proper CRC16 values, and only those that had matching CRC16 values were considered a success. A nal test was carried out on the highest expansion factor that resulted in a reasonable amount of transmit time for a RTS frame in order to determine its resilience to jamming. This is important since these frames are signi cantly smaller than the ethernet frame used during the rest of the tests, and are required in the protocol for establishing channel control and coding con gurations for the communicating parties. The RTS frame is just a BBC-MAC header plus a payload containing the time the initiating node estimates it will need the channel for. For these tests it was only 28 bytes, 91 which, conveniently, an expansion of 500 resulted a transmit time of 12 seconds with an extremely low mark density of just 0.24%. 6.3 Experiments 6.3.1 Jammer RSSI Experiment To gain an initial insight into how the two jammers would a ect the channel, the rst experiment was to run both jammers at each level of jamming and collect the RSSI value. As noted in the previous chapter, the RSSI value is continuously collected during the receiver?s script. The experiments were executed such that only the noise data generated by the respective jammers were transmitted. Figure 6.1: RSSI Value vs Jamming Level 92 Figure 6.1 shows the results of this experiment. The pulse jammer presents a uniform increase in RSSI value, while the Gaussian jammer displays a half bell curve increase. This is not surprising since the random generator used in the pulse jammer is of uniform distribution, while the Gaussian uses a Raleigh distribution. This information is necessary in order to correlate the results of the next series of tests with the con guration needed for a speci c range of RSSI values. 6.3.2 Pulse Jammer Experiment The pulse jammer that I created is meant to attack the decoder in a similar way as my demonstration of the BBC decoder in Section 2.5.4. The jammer places a high pulse where it otherwise would not be. As explained in the previous chapter, the jammer accepts an input level in the range [0,64], where the level given determines how many time steps will contain a pulse. For example, if the level is 13, the jammer will output a sink le where every 64 time steps is guaranteed to contain 13 pulses. This can create a signi cant amount of error and noise for the decoder, but it can not guarantee that it will induce a 1364 ? 20:31% error rate. This is because if the sender was already sending a 1 where the jammer outputted a 1, it would not a ect the signal, and thus it is a maximum of 20.31% bit error rate and not a guaranteed error rate. Figure 6.2 and Table 6.2 show the results of all the tests on the ethernet frame. What is clear from the graph is that each expansion factor gives an advantage over the prior one, but as we increase the expansion we notice less improvement over the 93 Figure 6.2: Collective Pulse Jammer Results previous expansion. Starting at expansion 100 we begin to see the steady decrease in advantage over the previous level. This makes sense since looking back at Table 6.1, there is a very minimal decrease in mark density as we increase the expansion from 100. 94 Jammer Level 50 75 100 125 150 175 200 RTS @ 500 0 25 29 30 26 27 28 28 22 1 26 27 23 27 27 26 23 27 2 16 28 30 24 29 27 15 27 3 4 28 25 26 30 24 20 26 4 0 28 24 26 28 22 21 23 5 0 26 24 23 27 21 20 27 6 0 26 26 28 29 24 22 27 7 0 14 26 24 29 25 23 28 8 0 0 24 26 28 22 22 30 9 0 0 24 28 29 18 24 26 10 0 0 22 28 29 23 20 28 11 0 0 0 26 28 26 26 28 12 0 0 0 1 29 21 24 25 13 0 0 0 0 0 21 27 28 14 0 0 0 0 0 0 11 29 15 0 0 0 0 0 0 0 26 16 0 0 0 0 0 0 0 29 17 0 0 0 0 0 0 0 28 18 0 0 0 0 0 0 0 30 19 0 0 0 0 0 0 0 11 20 0 0 0 0 0 0 0 0 21 0 0 0 0 0 0 0 0 Table 6.2: Pulse Jammer Results Figure 6.3 shows the results of tests with an expansion of 50. This con guration does well through level one jamming where it gets 26 messages through, but then it begins to lose ground with only 16 in level two jamming, and statistically becomes unstable at level three jamming. This con guration was meant to operate in areas of little-to-no noise in order to give high throughput. It can clearly tolerate this requirement. 95 Figure 6.3: Pulse Jammer with Expansion 50 Figure 6.4: Pulse Jammer with Expansion 75 96 Figure 6.4 displays the results of the test on expansion 75. Expansion 75 does signi cantly better than 50. It manages to get 26 messages through at level six jam- ming, and then 14 at level seven before it goes to zero. Figure 6.5: Pulse Jammer with Expansion 100 Figure 6.5 shows the results of tests on expansion 100. This expansion had several jamming levels where it had just barely over 20 messages through. However, while monitoring a lot of these tests, sometimes the radios would cause bu er under runs where the received data was lost. Combined with the randomness of the data, this can add to the low numbers on many of these early jamming levels where we should be seeing high success rates. This con guration did signi cantly better than the previous one. It got 22 messages through on level ten jamming, but then zero on the subsequent levels. 97 Figure 6.6: Pulse Jammer with Expansion 125 Expansion 125 shown in Figure 6.6 did only one level better than the previous one. After level 11 jamming it manages just one successful transmission before going to zero. As mentioned earlier, this is where we begin to see only minor improvements in jam-resistance. Again, the next level of resistance at expansion 150 in Figure 6.7 shows that we are able to compensate for just one more level of jamming. This con guration got 29 messages through on level 12 jamming, but then got zero through on the subsequent tests. 98 Figure 6.7: Pulse Jammer with Expansion 150 Figure 6.8: Pulse Jammer with Expansion 175 99 Expansion 175 shown in Figure 6.8 displays problems early during the jamming tests of just getting data decoded. This con guration manages to get to level 13 jamming with 21 of the messages getting through, and then decays to zero. Figure 6.9: Pulse Jammer with Expansion 200 Expansion 200 shown in Figure 6.9 displays the same problems as 175 did early on in the jamming experiment. However, it did just better than 175 at level 13 with 27 messages being received, and at level 14 it got just 11 messages through. Statistically, 200 does only marginally better than 175. After reviewing the logs on this test, a lot of the problems seen in the early jamming levels were not due to the decoder timing out, but rather that the decoder was indicating a signi cant amount of the sequence numbers were missing and so it dropped the data. 100 Figure 6.10: Pulse Jammer with RTS Frame at Expansion 500 The nal test ran was on the RTS frame with an expansion of 500. Recalling the protocol design, the RTS and CTS frames are used for determining the proper level of jam-resistance needed between the two communicating parties. This requires that we have a high degree of certainty that the these frames are successfully transmitted. Figure 6.10 shows that this con guration allows the frame to make it through level 18 jamming with 30 messages being received, and 11 received at jamming level 19 before decaying to zero. 6.3.2.1 Pulse Jammer Experiment Conclusion This experiment showed how the various con gurations can resist the pulse jam- mer up to a certain level. Each of the con gurations o ers a bene t over the other in the form of throughput or jam-resistance. The highest expansion factor manages 101 to resist a jamming level of 13 which equates to roughly a 20.31% bit error rate at the maximum. Finally, the tests on the RTS frame demonstrate several important factors. The rst is that we can successfully transmit these frames at very high levels of jamming. The expansion of 500 resisted a jamming level of 18 which is roughly a 28.13% bit error rate at the maximum. The second important piece of information is that the smaller frame size was able to do better than the larger at getting successful receptions, but at also a signi cantly lower throughput. 6.3.3 Gaussian Jammer Experiment The Gaussian jammer is a noise source generator part the GNU Radio API li- brary. It accepts as a parameter the maximum amplitude and then uses a Gaussian distribution random generator to determine what amplitude the output signal should be. The generator accepts a jammer level in the range [0,64], where each step con- stitutes and increase in amplitude of 500. The maximum value for the amplitude is 32000, which conveniently works out to 64 levels. Figure 6.11 and Table 6.3 show the results of all the tests on the ethernet frame and the last one on the RTS frame. Again we see the pattern of gradual decrease in resistance as we increase the expansion, but there also appears to be area of con- centration where the limits of the expansions are met. Recalling Figure 6.2 from the pulse test, we notice that there was quite a bit more distinction between the con g- urations. However, looking at how the RSSI values increase from Figure 6.1 for the Gaussian jammer versus the pulse jammer, this rapid decline seems expected. 102 Figure 6.11: Collective Gaussian Jammer Results Jammer Level 50 75 100 125 150 175 200 RTS @ 500 0 28 29 30 30 30 29 24 24 1 26 27 29 28 28 26 19 27 2 26 25 30 30 28 24 15 27 3 24 23 28 28 30 27 20 23 4 26 26 30 26 30 29 24 27 5 25 28 30 28 30 29 17 28 6 21 28 29 30 29 28 9 24 7 9 26 29 29 28 28 18 26 8 0 26 27 30 30 23 10 27 9 0 26 28 30 27 25 9 25 10 0 2 26 27 29 28 6 28 11 0 0 1 26 24 27 10 28 12 0 0 0 8 11 2 0 22 13 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 Table 6.3: Gaussian Jammer Results 103 Figure 6.12: Gaussian Jammer with Expansion 50 Figure 6.12 shows the results of tests with an expansion of 50. The con guration is able to cope with jamming level six, but then declines at seven with just nine successful transmissions, and nally going to zero. Again, this con guration is meant to be used in areas of low noise so as to increase the throughput. Figure 6.13 displays the results of the test on expansion 75. This con gurations is able to edge out the previous by several levels, allowing 26 messages through on level nine jamming, and then just two on level 10 before declining to zero. 104 Figure 6.13: Gaussian Jammer with Expansion 75 Figure 6.14: Gaussian Jammer with Expansion 100 105 Figure 6.14 shows the results of tests on expansion 100. This expansion was only able to do just one level better than expansion 75. There were 26 successful receives on level ten jamming, and just one on 11. At this con guration we begin to see the decline in jam-resistance advantage over the previous con guration. However, com- paring the results of this test to the pulse jammer, this expansion was more stable in the Guassian jammer than in the pulse. Figure 6.15: Gaussian Jammer with Expansion 125 Expansion 125 shown in Figure 6.15 did only one level better than 100. The con guration allowed 26 messages through on level 11 and eight on level 12 before the decoder began to timeout on the subsequent levels. 106 Figure 6.16: Gaussian Jammer with Expansion 150 Figure 6.16 shows the results of expansion 150. Beginning at this con guration we stop seeing a statistical advantage in raising the expansion. At level 11, 24 messages were received, and at level 12 jamming just 11 messages were received. Expansion 175 shown in Figure 6.17 doesn?t show the same problems as this respective test did on the pulse jammer. However, again this expansion was not able to do better than the previous two. It was able to get twenty-seven messages through on jamming level eleven, and just two on jamming level twelve. 107 Figure 6.17: Gaussian Jammer with Expansion 175 Figure 6.18: Gaussian Jammer with Expansion 200 108 Expansion 200 shown in Figure 6.18 displays similar issues as the respective test did in the pulse jammer, but did signi cantly worse. Again, looking at the logs for this test it was observed that the decoder wasn?t timing out, but rather that it was missing many sequence numbers. Figure 6.19: Gaussian Jammer with RTS Frame At Expansion 500 Finally, the test on the RTS frame with an expansion of 500 was ran. Figure 6.19 shows the results of this test. Again, using this con guration the RTS frame could be successfully received at a jamming level beyond what any of the data frames made it to. The con guration allowed the frame to be received 22 times on level 12 jamming before declining to zero on the remaining levels. 109 6.3.3.1 Gaussian Jammer Experiment Conclusion This second experiment on the Gaussian jammer demonstrated that even against a di erent type of jammer the con gurations can successfully use di erent con gu- rations for the proper level of interference in the channel. The con gurations were able to resist the jammer up to a certain point just as in the pulse test, but this time it was seen that the limit was approached far quicker than in the pulse experiment. This can be explained by the fact that the increase in jamming levels for the Gaussian noise source beyond level ten begin to increase the RSSI value signi cantly more than with the pulse jammer. 6.4 Chapter Conclusion When comparing the results of the con gurations from the two jammers, on the surface it seems that the lower expansions were able to resist more of the jamming levels on the Gaussian test than they did on the pulse. However, to e ectively see how the con gurations fared against the two jammers one must look at what RSSI value the particular jamming level creates for the respective jammer. If we consider anything less than a 50 percent success rate a failure and map the last jamming level that particular con guration was successful on, to the RSSI value from Figure 6.1, we get the results found in Table 6.4. The Gaussian jammer trials show that the upper bound for the con guration to correct the errors was reached at level ten jamming. However, what is really happening is they were not able to overcome the next level of jamming which produces an RSSI value of 1603. When the results are compared 110 this way it illustrates that for both jammers, the RSSI value will give us the proper estimation for which con guration to use. Then, with this information in mind, we can ignore the type of jammer used and base the decision on the RSSI. This is im- portant since the protocol will not have forehand knowledge of the jammer type and instead will only be using the RSSI as a determination factor. Jammer 50 75 100 125 150 175 200 RTS @ 500 Pulse 385 790 1161 1256 1356 1433 1433 1769 Gaussian 312 792 1028 1263 1263 1263 596 1603 Table 6.4: RSSI Failure Levels This phase of experiments provided the necessary information to complete the adaptive BBC-MAC protocol. The results showed that by adjusting the expansion factor, we can adapt the encoding to better suit the needs of the channel. Increas- ing the expansion factor reduces our throughput, but gives us greater jam-resistance. While lowering it increases our throughput but leaves us susceptible to weaker jam- ming attacks. The goal of this experiment was to arrive at ve con gurations for the data frames and an additional one for the RTS and CTS frames. I tested seven con- gurations on an 1514 byte ethernet frame and demonstrated each of their abilities to resist di erent levels of jamming on several jammers. After analyzing the results, the con gurations chosen for the protocol are expansions 50, 75, 100, 150, and 175. Expansion 200 was dropped for several reasons. The most obvious is that it is entirely too unstable to be incorporated in the protocol. The second is that in both jammer tests, it gave no statistical advantage over expansion 175. Expansion 125 was not 111 chosen since in terms of RSSI value it only did one level better than expansion 100 and I wanted a more signi cant bu er between the con gurations. The expansion of 500 for the RTS and CTS proved to be more than adequate as evidenced by the fact that it was successfully received at RSSI levels well beyond what the con gurations for the data frame achieved. 112 Chapter 7 Phase II Experiments: Protocol Validation 7.1 Chapter Introduction The nal phase of experiments presented in this chapter focuses on using the data from the rst phase of experiments conducted in Chapter 6. In that phase, an investigation into the BBC algorithm was conducted to determine what must be done to allow for varying levels of jam-resistance. The experiments showed that in order to produce greater jam-resistance the mark density of a message must be reduced. After an examination of the algorithm, the analysis shows that in order to achieve varying levels of mark density, and thus jam-resistance, the expansion factor used in the codec must be altered. Seven variations of that value were tested against two jammers and the results showed that each variation provided a bene t in either jam-resistance or throughput. The values chosen for protocol implementation are 50, 75, 100, 150 and 175. This chapter will include those in the BBC-MAC protocol and conduct the experiments necessary to illustrate how the protocol can use these to adapt to the level of noise. The rst experiment presented in this chapter shows the results of the original protocol with those values. The information from that experiment revealed a problem in the implementation and an important modi cation was made to improve the overall performance of the protocol. 113 7.2 Experiment Setup The physical layout of these experiments remains the same as the experiments conducted in Chapter 6. The USRPs are roughly four feet apart with two transceiver daughterboards in each, where their respective antennas are 3.5 inches apart. The information from the previous set of experiments has been used and applied to the BBC-MAC protocol implementation. Table 7.1 shows the range of RSSI val- ues that each expansion is applied to. These ranges are based on the jamming level that the expansion was able to resist and then correlated to the average RSSI value produced at that level. Expansion Min RSSI Max RSSI 50 0 300 75 301 700 100 701 1050 150 1051 1350 175 1351 4092 Table 7.1: Expansion RSSI Range Prior to conducting the experiments a statistics module was created to allow both a RxHandler and a TxHandler to keep track of relevant information for the stream they are currently managing. The information kept by the TxHandler is: RTS Count: The number of RTS frames that were sent. Data Count: The number of data frames that were sent. 114 Send Time: The Network Time Protocol (NTP) time that the rst RTS frame was sent at. ACK Time: The NTP time that the ACK was received. RTS Fail: Flag set if this stream failed at the RTS/CTS exchange stage. Data Fail: Flag set if this stream failed at the DATA/ACK exchange stage. RSSI: Final RSSI value used for determining the expansion to use. Expansion: The expansion used for the Data transmission. Channel Latency: The di erence in time between the Send and ACK time. On the recipients end the RxHandler also maintains some information: RTS Count: The number of RTS frames that were received. Data Count: The number of Data frames that were received. Data Time: The NTP time that the data frame was received and delivered to the upper layer. ACK Count: The number of ACK frames transmitted. This should be equal to the number of data frames received. CTS Count: The number of CTS frames transmitted. This should be equal to the number of RTS frames received. 115 In the experiments. the following terms will be used to discuss the analysis of the data collected by the statistics on the transmit and receive end for each message that was sent: False Negative: This is where the transmitter signaled its upper layer of a failure to deliver the data, but the receiver had actually received the data and delivered it to its upper layer. False Positive: This is where the transmitter signaled its upper layer of a failure to deliver the data and the other node did not receive it. Nominal Latency: This is the di erence between the Send Time in the Tx- Handler statistics and the Data Time in the RxHandler statistics. It is the time between when the sender rst initiated communications by sending an RTS and when the recipient delivered the data to the upper layer. Under optimal con- ditions this is just the Channel Latency minus the time to deliver the ACK. However, under conditions where the data frame is unnecessarily re-transmited due to a missed ACK, this can be signi cantly lower than the Channel Latency. Optimal Nominal Latency: This is the Nominal Latency when everything worked perfectly. That is, only one RTS frame had to be sent and only one Data frame had to be sent. The experiments were tested with the pulser jammer only. This choice was made since it gave a uniform increase in RSSI value allowing for more granularity of the 116 tests. For each experiment 30 messages were sent at each jammer level in the range of [0,10]. The goal of the experiments are to show that the protocol would adapt to di erent levels of noise and not the demonstration of absolute failure. The expansions respective failure limits were demonstrated in Chapter 6. As with the experiments conducted before, whenever a data transmission was occurring on the radio, a jammer was running on the author daughterboard. 7.3 Experiments 7.3.1 Initial Protocol Implementation Experiment The initial protocol implementation operates in the same fashion as explained in Section 5.4. The ow of a message has the following sequence: 1. The sender encodes a RTS frame with an expansion factor of 500 and transmits. 2. The recipient will respond with a CTS frame encoded with an expansion of 500. 3. The two nodes should now be in agreement on which con guration to use for subsequent frames. 4. The sender now encodes the data frame using the agreed expansion and trans- mits. 5. The recipient will reply with an ACK frame encoded at the agreed expansion. This RTS-CTS-DATA-ACK ow is the complete stream assuming everything is received without error. Recall from Section 5.4 that if upon receiving the CTS the 117 sender requests further expansion re nement, it will re-transmit a RTS to inform the recipient of a new con guration to which they should agree upon. To overcome the possible corruption of RTS and CTS frames, the sender can re-transmit an RTS frame up to two more times past the initial request. The time that the channel is allocated for the two nodes is the time needed for three transmissions of the data frame plus the time needed for a timeout. The decoder is given 30 seconds to decode the data received by the receiver before the data is considered too corrupt for processing and the data purged. The experiment was conducted by sending 30 messages at each jammer level and recording the results from the statistics for analysis. The data used as payload is the same 1514 byte ethernet frame that was used in the experiments from Chapter 6, and the hexadecimal string of the frame can be found in Section B.1. Beginning rst with an analysis of the latency, we can see in Figures 7.1 and 7.2 that on all three measurements there is a gradual increase in latency as we increase the jammer level and thus the expansion factor needed. Tables 7.2 and 7.3 show the numbers that each graph displays, respectively. We can clearly see that there is a bene t in using the lowest jam-resistance level. Compared to the highest jam- resistance level, we are able to transmit almost 16 seconds faster in optimal conditions. Furthermore, as we go from one expansion to the next, there is an increase in latency. These two graphs demonstrate the latency tradeo by adjusting the expansion factor. 118 JammerLevel ChannelLatency(s) NominalLatency(s) OptimalLatency(s) 0 52.5 47.3 43.9 1 55.8 46.5 44.7 2 64.5 49.1 45.7 3 62.4 47.2 46.7 4 53.3 47.2 47.3 5 62.1 50.9 48.4 6 56.8 49.1 49.2 7 71.1 62.3 56.2 8 70.6 64.1 57.3 9 78.3 66.1 60.6 10 79.6 66.0 57.7 Table 7.2: Experiment I Latency By Jammer Level Expansion ChannelLatency(s) NominalLatency(s) OptimalLatency(s) 50 53.0 47.1 42.6 75 60.5 47.6 45.8 100 57.6 49.6 48.3 150 72.1 63.6 57.3 175 78.4 65.3 58.9 Table 7.3: Experiment I Latency By Expansion Level Figure 7.1: Experiment I Latency By Jammer Level 119 Figure 7.2: Experiment I Latency By Expansion Level 120 Continuing on to an analysis of the RTS frames, in Figures 7.3 and 7.4 we see how many RTS frames were sent, how many of those were received, and how many messages were sent. Under optimal conditions there should be a 1:1 ratio between the number sent and received, and not necessarily a 1:1 ratio between the number of RTS frames sent and the number of messages sent. This is because more RTS frames might be sent as needed by the protocol to adjust the expansion factor used in subsequent data and ACK frames. However, the gures clearly indicate that there was a minimal error in the RTS frames and only at level eight jamming was there increase in the adjustments made. The raw data from where this data was collected indicates several times in which expansion 175 had to be used in level eight jamming, accounting for the small separation between the number of RTS received and the number of messages sent at that level. Tables 7.4 and 7.5 numerically display the same data. Jammer Level Messages Sent RTS Sent RTS Received 0 30 33 30 1 30 30 30 2 30 32 30 3 30 30 30 4 30 30 30 5 30 30 30 6 30 30 30 7 30 31 30 8 30 34 33 9 30 33 30 10 30 36 32 All 330 349 335 Table 7.4: Experiment I RTS Transmits By Jammer Level 121 Figure 7.3: Experiment I RTS Transmits By Jammer Level Expansion Messages Sent RTS Sent RTS Received 50 24 27 24 75 96 98 96 100 91 91 91 150 71 78 74 175 48 55 50 All 330 349 334 Table 7.5: Experiment I RTS Transmits By Expansion Level 122 Figure 7.4: Experiment I RTS Transmits By Expansion Level 123 Moving onto an analysis of the data frames, Figures 7.5 and 7.6 show the results of all the data transmissions at each jammer level and expansion factor, respectively. The di erence listed in Tables 7.6 and 7.7 and the gures, represents the di erence between the number of data frames received and the number of messages sent. Be- ginning with the breakdown by jammer level, we can see that from levels one through three there is an extremely high di erence between the number of messages sent and the number of data frames received, and only a minor di erence between the number of data frames sent and received. This indicates a problem in data frames being acknowledged at those levels. If we move to Figure 7.6 with the breakdown by ex- pansion, we can see that expansion 75 is the main expansion used at those levels and presents a problem getting ACK frames through. However, as we move up in expansions this problem seems to to disappear, indicating that as we increase the expansion the ACK frames have a smaller error rate. 124 Jammer Level Messages Sent Data Sent Data Received Di erence 0 30 32 32 2 1 30 43 42 12 2 30 43 42 12 3 30 43 43 13 4 30 32 32 2 5 30 38 35 5 6 30 32 32 2 7 30 34 31 1 8 30 31 30 0 9 30 33 33 3 10 30 38 33 3 All 330 399 385 55 Table 7.6: Experiment I Data Transmits By Jammer Level Expansion Messages Sent Data Sent Data Received Di erence 50 24 26 26 2 75 96 136 134 38 100 91 103 99 8 150 71 76 73 2 175 48 58 53 5 All 330 399 385 55 Table 7.7: Experiment I Data Transmits By Expansion Level 125 Figure 7.5: Experiment I Data Transmits By Jammer Level Figure 7.6: Experiment I Data Transmits By Expansion Level 126 Finally, we conclude by looking at the overall message failure rate broke down by jammer level and expansion factor in Tables 7.8 and 7.9. The tables display the number of false negatives (FN) and false positives (FP) at each jammer level and ex- pansion. Recall the problems with ACK frames from the analysis of the data frames indicates how these FNs can come about. The FN for expansion 75 is at three with only one other FN occurring at the highest jammer level. The FN at the highest jammer level is not surprising since it is approaching the limit of what expansion 175 is able to tolerate. However, the most important statistic is that on no level was there a FP or a failure to actually deliver the data message. Jammer Level Messages Sent False Negatives False Positives 0 30 0 0 1 30 2 0 2 30 1 0 3 30 0 0 4 30 0 0 5 30 0 0 6 30 0 0 7 30 0 0 8 30 0 0 9 30 0 0 10 30 1 0 All 330 4 0 Table 7.8: Experiment I Message Errors By Jammer Level 127 Expansion Messages Sent False Negatives False Positives 50 24 0 0 75 96 3 0 100 91 0 0 150 71 0 0 175 48 1 0 All 330 4 0 Table 7.9: Experiment I Message Errors By Expansion Level This experiment demonstrated the initial capability of the BBC-MAC protocol and its capacity to adjust to the level of noise in the channel. The analysis of the data collected clearly shows that by adjusting the jam-resistance level we can either gain a bene t in throughput or a bene t in the ability to cope with greater jamming levels at the cost of throughput. However, the analysis of the data frames indicated that there was a serious problem at the lower jam-resistance levels in being able to return ACK frames successfully. The next section aims to address this problem by modifying the way the protocol implements the RTS-CTS-DATA-ACK frame exchange sequence. 7.3.2 Re ned Protocol Implementation Experiment After the initial protocol implementation experiment was conducted, the results show that there was a problem on the lower jam-resistance con gurations in getting the ACK frames back to the sender. The analysis showed that there was a relatively small separation between the number of data frames sent and the number received, indicating the weakness in the protocols implementation of the RTS-CTS-DATA- ACK frame exchange. Upon further analysis, this was result of the ACK frames 128 being so small in size, that on the lower resistance levels the smallest amount of noise would corrupt the frame easily. This can then result in much higher data frame re- transmission rates, and as seen, higher levels of false negatives. The simple solution then becomes to always encode the ACK frames at a high jam-resistance level. This nal experiment makes only this modi cation to the protocol and will encode the ACK frames at the same expansion as the RTS and CTS frames. The exchange of frames now follows this series: 1. The sender encodes a RTS frame with an expansion of 500 and transmits. 2. The recipient will respond with a CTS frame encoded with an expansion of 500. 3. The two nodes should now be in agreement about which con guration to use for subsequent messages. 4. The sender now encodes the data frame using the agreed expansion and trans- mits. Once the transmission is complete the transmitter adjusts its codec ex- pansion to be listening on expansion 500. If a timeout occurs, it will adjust its con guration back to the agreed upon level and re-transmit the data frame. 5. The recipient will reply with an ACK frame encoded at expansion 500. Once the transmission is complete, it will adjust its codec expansion back to the previous expansion used for the data frames. This is in case the sender still didn?t receive the ACK and re-transmits the data frame. 129 The goal of this modi cation is to reduce the number of unnecessary re-transmits of the data frames, and increase the channel e ciency by eliminating the need to own it for so long. This should also further reduce the number of false negatives seen at the lower expansions. However, this will also increase the channel latency since it will take longer to transmit the ACK frame encoded at the higher expansion. The experiment is then conducted in the same manner as the one in Section 7.3.1. Thirty messages sent at each jammer level, using the pulse jammer that is always running whenever a transmission is occurring. Beginning again by looking at the latencies in Figures 7.7 and 7.8, we see the same increase in latency from the lowest expansion up to the highest. This is not a siginifcant change in the optimal latency, as expected, since the modi cation doesn?t a ect the time it takes to get a RTS-CTS-DATA through in optimal conditions. However, we are also seeing an increase in the channel latency. It was expected to increase, but it increased signi cantly more than what we see in Figures 7.1 and 7.1. This larger-than-expected jump is due to a higher rate of RTS re-transmissions than what we saw in the prior experiment. However, we again see that each expansion gives us the bene t of either increased throughput or increased jam-resitance. 130 JammerLevel ChannelLatency(s) NominalLatency(s) OptimalLatency(s) 0 58.8 48.1 43.4 1 63.2 49.2 46.3 2 69.0 56.7 47.9 3 69.7 57.5 47.8 4 71.6 57.7 51.3 5 77.3 66.4 50.7 6 78.2 68.1 54.5 7 79.8 64.6 56.4 8 84.5 71.2 57.5 9 78.5 68.0 59.4 10 86.6 74.0 60.9 Table 7.10: Experiment II Latency By Jammer Level Expansion ChannelLatency(s) NominalLatency(s) OptimalLatency(s) 50 58.8 48.1 43,4 75 67.2 54.3 47.2 100 72.8 60.9 51.2 150 79.3 66.3 56.4 175 86.1 74.0 60.1 Table 7.11: Experiment II Latency By Expansion Level Figure 7.7: Experiment II Latency By Jammer Level 131 Figure 7.8: Experiment II Latency By Expansion Level 132 Figures 7.9 and 7.10 show the RTS transmit rates for this experiment. As noted, we see a slightly higher transmission rate of RTS frames. Some of this can be at- tributed to the larger number of expansion adjustments that took place. This is evidenced by the fact that the number of frames received is steadily increasing over the number of frames sent, but there are several levels that display higher RTS er- ror rates. Reviewing the logs of the trials indicated that an unusually large number of RTS transmissions began while the receiver was in an unprepared state, or the receiver had to stop receiving due to sample limitations in the middle of an RTS transmission. However, the protocol never failed at the RTS-CTS handshake, and resolved the problems with re-transmissions. Jammer Level Messages Sent RTS Sent RTS Received 0 30 30 30 1 30 31 31 2 30 34 31 3 30 37 33 4 30 34 33 5 30 40 35 6 30 40 36 7 30 36 35 8 30 37 36 9 30 34 34 10 30 32 32 All 330 385 366 Table 7.12: Experiment II RTS Transmits By Jammer Level 133 Figure 7.9: Experiment II RTS Transmits By Jammer Level Expansion Messages Sent RTS Sent RTS Received 50 30 30 30 75 86 97 90 100 71 86 80 150 74 92 87 175 69 80 79 All 330 385 366 Table 7.13: Experiment II RTS Transmits By Expansion Level 134 Figure 7.10: Experiment II RTS Transmits By Expansion Level 135 We now move onto the analysis of the data frame re-transmit rates. Figures 7.11 7.12 show the results of this experiment. The graphs clearly show that the modi- cation resolved the problem of unnecessary re-transmissions of data frames. The di erence seen from the previous experiment is included on the graphs, and there is a large margin between the two di erences. This indicates that we have successfully reduced the number of data transmissions that went unacknowledged and the num- bers can be seen in Tables 7.14 and 7.15. Jammer Level Messages Sent Data Sent Data Received Di erence 0 30 34 31 1 1 30 34 33 3 2 30 33 31 1 3 30 31 31 1 4 30 32 31 1 5 30 31 30 0 6 30 30 30 0 7 30 32 32 2 8 30 34 31 1 9 30 32 30 0 10 30 41 31 1 All 330 364 341 11 Table 7.14: Experiment II Data Transmits By Jammer Level 136 Figure 7.11: Experiment II Data Transmits By Jammer Level Expansion Messages Sent Data Sent Data Received Di erence 50 30 34 31 1 75 86 94 91 5 100 71 74 72 1 150 74 77 76 2 175 69 85 71 2 All 330 364 341 11 Table 7.15: Experiment II Data Transmits By Expansion Level 137 Figure 7.12: Experiment II Data Transmits By Expansion Level 138 Finally, we conclude by analyzing the message failure rates of this experiment. Tables 7.16 and 7.17 show that on only level ten jamming did we see false negatives, and at no point was there a false positive, or a failure to deliver the data. The seem- ingly static number of false negatives at jammer level ten appears to be an indication that expansion 175 is just barely capable of handling the amount of interference in- duced by that jammer level. However, the number of false positives at the lower jamming levels have been successfully eliminated by the modi cation made for this experiment. Jammer Level Messages Sent False Negatives False Positives 0 30 0 0 1 30 0 0 2 30 0 0 3 30 0 0 4 30 0 0 5 30 0 0 6 30 0 0 7 30 0 0 8 30 0 0 9 30 0 0 10 30 2 0 All 330 2 0 Table 7.16: Experiment II Message Errors By Jammer Level 139 Expansion Messages Sent False Negatives False Positives 50 30 0 0 75 86 0 0 100 71 0 0 150 74 0 0 175 69 2 0 All 330 2 0 Table 7.17: Experiment II Message Errors By Expansion Level This experiment focused on addressing the issue in data frame acknowledgments that we exposed in the rst experiment in Section 7.3.1. The analysis of this ex- periment shows that with the modi cation of encoding the ACK frames at the same expansion level as the RTS and CTS frames, we are able to reduce the number of unnecessary re-transmissions of data frames at the lower expansion levels, and further reduce the number of false negatives. 7.4 Adaptive vs Non-Adaptive To wrap up the discussion on the BBC-MAC protocol I would like to show how the protocol performs when we remove the adaptive portion. Removing the adaptive portion would then eliminate the RTS-CTS exchange, and instead no matter the level of noise the highest expansion of 175 would be used for the DATA frame, and then the expansion 500 on the ACK. Under perfect situations, the RTS/CTS/ACK frames encoded at 500 take 12 seconds to transmit. Table 7.18 then shows the Round Trip Time (RTT) for a single DATA-ACK exchange for the non-adaptive, and then the adaptive protocol at their respective expansion levels. 140 Con guration 50 75 100 150 175 Non-Adaptive RTT (s) 42 45 48 54 57 32 Table 7.18: Adaptive vs Non-Adaptive The table highlights an issue where even at our lowest jam-resistance level, we are not transmitting faster than the non-adaptive protocol. The problem is in the encoding of the RTS/CTS/ACK frames. Since these are encoded at such a high ex- pansion, they require a lot of time to transmit, and thus there is a signi cant penalty in simply transmitting only one DATA-ACK exchange post the RTS-CTS exchange. In order to resolve this problem, we need to lower the penalty incurred by using the RTS-CTS exchange to setup both nodes. I propose that instead of encoding the RT- S/CTS/ACK frames at expansion 500, we lower this to only be as high as the highest expansion used of 175. The frames will now only require ve seconds to transmit, and again assuming perfect conditions, Table 7.19 shows how this modi cation a ects the time needed to complete a transmission with a single DATA-ACK exchange. The modi cation will also reduce the time needed for the non-adaptive protocol since the ACK frame is no longer encoded at 500. Con guration 50 75 100 150 175 Non-Adaptive RTT (s) 21 24 27 33 36 26 Table 7.19: Adaptive vs Non-Adaptive with Modi cation With this modi cation we now have signi cantly reduced overhead in a single DATA-ACK exchange. However, several of the adaptive con gurations still take 141 longer than the non-adaptive protocol for a single DATA-ACK exchange. Most MAC protocols support fragmentation, and thus support multiple DATA-ACK exchanges. 802.11 supports multiple of these exchanges after a single RTS-CTS handshake, as long as the individual fragments do not exceed the length speci ed by the station, and can support up to 16 of the DATA-ACK exchanges for a single RTS-CTS handshake [IEEE 2007]. If we now look at how the adaptive protocol performs against the non- adptive protocol when we allow up to 16 exchanges to occur we arrive at Figure 7.13. Referring to Figure 7.13, the adaptive protocol shows faster round trip transmission times than the non-adaptive protocol in all but the highest expansion level case. As expected, the adaptive 175 never splits because it always has the overhead of the RTS/CTS handshake. However, this handshake is what allows the lower expansions to be used when necessary. Figure 7.13: Adaptive vs Non-Adaptive by DATA-ACK Exchanges 142 A nal thought on the non-adaptive versus adaptive is how well would it perform when an adversary is jamming for some period of time, and then stops jamming. For example, if we were to transmit 100 messages, and the adversary would jam a certain percentage of those, at what point does the non-adaptive protocol start to outperform the adaptive protocol. Assuming that the jammer is either running at full capacity for that percentage or not at all, the adaptive protocol is either using expansion 175 or expansion 50 for those respective scenarios. Figure 7.14 shows at what percentage the adaptive protocol converges with the non-adaptive protocol with respect to the number of DATA-ACK exchanges that occur after the initial RTS-CTS handshake. Figure 7.14: Adaptive vs Non-Adaptive Convergence As expected, the percentage of jamming that the adaptive protocol tolerates over the non-adaptive increases with the respect to the number of DATA-ACK exchanges. 143 The adaptive protocol demonstrates its superiority over the non-adaptive protocol as there are more of these exchanges, and this because the penalty incurred by the RTS-CTS handshake is minimal compared to the number of DATA-ACK exchanges. However, even if there was a single DATA-ACK exchange, the adaptive protocol will still outperform the non-adaptive protocol 33% of the time. Given that we can never gauge how much of the time an adversary will jam, or how much data will need to be framed from the upper layer, we can see that the adaptive protocol will provide a bene t in either situation. The nal aspect of this modi cation that needs to be validated is the RTS frame encoded at expansion 175?s ability to resist at least the same amount of jamming levels that that the highest expansion was able to with the data frames. To test this I ran the same resilience test that was run in Section 6.3.2. The RTS frame was encoded at expansion 175 and I transmitted the frame 30 times at each jammer level until there were two levels where zero frames were successfully received. Figure 7.15 shows the results of this trial. The graph shows that the modi cation allows the RTS frame to be successfully received through level 13 jamming. Recall from Section 6.3.2, that the data frame encoded at expansion 175 was also successful at completing transmissions through level 13 jamming. 144 Figure 7.15: Pulse Jammer with RTS Frame at Expansion 175 The modi cation made to the protocol improves the performance by reducing the time needed to complete the RTS-CTS-DATA-ACK exchange of frames between the sender and the receiver. The modi cation does not alter the e ectiveness of the protocol in adapting to the level noise, and only improves the time required to complete a transmission at all the the resistance levels. The results of the modi ca- tion demonstrates the adaptive BBC-MAC protocols superiority to the non-adaptive protocol that would be using the highest expansion level at all times. 7.5 Chapter Conclusion This chapter presented the nal phase of experiments for the BBC-MAC proto- col. The experiments in this chapter veri ed the capability of the protocol to adapt to the level of noise by controlling the con guration of the BBC encoder and decoder at 145 the physical layer. The rst experiment implemented the information obtained from the rst phase in Chapter 6. After analyzing the results, it was shown that there was an issue in the frame exchange where at lower jam-resistance levels the ACK frame was easily being corrupted. In the second experiment, I proposed a solution where the ACK frames are always encoded at the same jam-resistance level as the RTS and CTS frames. With this one modi cation I was able to improve the e ciency of the protocol by signi cantly reducing the number of unnecessary data frame transmits due to a missed acknowledgment. The second experiment further solidi ed the pro- tocol?s ability to cope with a sundry of jamming levels by only using the necessary jam-resistance as indicated by the RSSI value. A nal discussion of how the pro- tocol performs against a non-adaptive version was given. The analysis showed that the implementation after the second set of experiments was not able to outperform a non-adaptive protocol. A modi cation to the protocol was presented where the RTS/CTS/ACK frames would be encoded at the highest expansion available for the DATA frames. The analysis of this modi cation demonstrated that it was now able to outperform the non-adaptive protocol, and the performance gap increased with respect to the number of DATA-ACK exchanges that occur for each RTS-CTS hand- shake. By controlling the codec con guration used at the physical layer, BBC-MAC is able to provide higher throughput in exchange for lower jam-resistance and vice versa, e ectively adapting to channel needs. 146 Chapter 8 Key Contributions Designed a Medium Access Control (MAC) layer for wireless nodes that can adapt to the level of noise detected in the channel. Implemented a working prototype of a protocol stack for adaptive jam-resistance communications on software de ned radios (SDRs) including the physical layer and a data link layer based on the design presented in the dissertation. Demonstrated how the BBC algorithm could be modi ed and controlled to provide di erent jam-resistance levels. Demonstrated that by altering the con guration options on the BBC algorithm, speci c levels of jam-resistance can be achieved that provide greater throughput or greater jam-resistance. Proved that by combining the BBC algorithm with the BBC-MAC implemen- tation, an adaptive protocol can be created that proactively determines the proper con gurations to use based on channel needs. Improved upon the initial design of the BBC-MAC implementation by altering the frame exchange sequence. Performed a literature review on wireless communications and technologies, the BBC algorithm, and the MAC layer and its supporting facilities. 147 Chapter 9 Conclusion This dissertation presents the relevant technologies and literature for wireless communications, and presents a novel approach to providing jam-resistance at the MAC layer. The current state of MAC layer research has not used the approach to solving noise in the channel that has been presented in this dissertation. Noise on the channel can be induced by many factors including environmental interference, unintentional jamming from other nodes, or intentional jamming. Current protocols attempt to solve the problems induced by unintentional jamming by relying on control frames, multiple channels, or mathematical probabilities. Only one MAC protocol has been presented that is directly concerned with adversarial wireless jamming [Awer- buch, Richa and Scheideler 2008]. However, the protocol attempts predict the time steps that jamming is not occurring, and has no mechanism to allow communications to occur while jamming is taking place. The protocol presented in this dissertation allows communications to continue in the presence of a jamming attack. Corruption of transmissions due to jamming is overcome by leveraging a recent coding algorithm for error-correction. Furthermore, the protocol dynamically adjusts the coding prop- erties of the algorithm to change the level of jam-resistance with respect to the level of noise detected in the channel. By leveraging the BBC message encoding, this re- search provides a MAC layer which is resistant to jamming unlike any other MAC layer protocol currently in existence. 148 Future work with this protocol stack should be directed at using a new modula- tion scheme for the physical transmission of the encoded data. While the modulation scheme used in the prototype served the purposes of demonstrating the technical fea- sibility of the protocol, it also takes a signi cant amount of time to transmit. By combining this research with a mature modulation scheme, the latency of the pro- tocol would be signi cantly improved. The ultimate test of latency is how well does the protocol support voice communications. Future work should be directed at im- proving the latency not only through testing di erent modulation schemes, but also by optimizing the BBC decoder. If the decoder could be optimized to not only have a tighter upper bound, but also to spend less time looking at invalid messages, the latency of the communications could be signi cantly reduced. This research e ort created a bi-layer protocol stack for wireless mobile nodes. A physical layer was implemented based on previous work that handles the coding and modulation of data for transmission, and the necessary components to interact with physical hardware. A MAC layer was then created that would control all ac- tivities at the physical layer. The layer proactively adjusts the coding con guration used at the physical layer to provide an adaptive jam-resistant protocol stack. By adapting to channel needs, BBC-MAC is able to provide only the necessary amount of jam-resistance in order to provide better throughput when possible, and greater jam- resistance when necessary. Uncommon to MAC layers in literature, this dissertation presents a prototype that has been implemented and validated on physical hardware 149 instead of through a computer simulation. The results of the various phases of exper- imentation demonstrate the ability of the layer to react to channel conditions. Based on the experiments in this dissertation it was shown that the protocol is capable of adapting to the level of jamming. The dissertation contributed to the eld of wireless communications by creating an adaptive single-hop MAC layer for noisy channels. 150 Bibliography Abramson, N. [1970], THE ALOHA SYSTEM{Another alternative for computer communications, in ?Proceeding of the Fall Joint Computer Conference?, Vol. 37, pp. 281{285. Agrawal, D. and Zeng, Q. [2006], Introduction to Wireless and Mobile Systems, Nel- son, chapter 3,6,7, pp. 57{78, 125{168. Awerbuch, B., Richa, A. and Scheideler, C. [2008], A Jamming-Resistant MAC Pro- tocol for Single-Hop Wireless Networks, in ?PODC ?08: Proceedings of the twenty- seventh ACM symposium on Principles of distributed computing?, ACM, New York, NY, USA, pp. 45{54. Bahn, W. [March 2009], ?BBC Real-time Engine?. URL: http://www.williambahn.com/bbc/software/real time engine/index.htm Baird, L. C., Bahn, W. L., Collins, M. D., Carlisle, M. C. and Butler, S. C. [2007], Keyless Jam Resistance, in ?Proc. IEEE SMC Information Assurance and Security Workshop IAW ?07?, pp. 143{150. Baldwin, R. O., Nathaniel J. Davis, I. and Midki , S. F. [1999], ?A Real-time Medium Access Control Protocol for Ad Hoc Wireless Local Area Networks?, SIGMOBILE Mob. Comput. Commun. Rev. 3(2), 20{27. 151 Bayraktaroglu, E., King, C., Liu, X., Noubir, G., Rajaraman, R. and Thapa, B. [2008], On the Performance of IEEE 802.11 under Jamming, in ?Proc. INFOCOM 2008. The 27th Conference on Computer Communications. IEEE?, pp. 1265{1273. Bharghavan, V., Demers, A., Shenker, S. and Zhang, L. [1994], MACAW: A Media Access Protocol for Wireless LAN?s, in ?SIGCOMM ?94: Proceedings of the con- ference on Communications architectures, protocols and applications?, ACM, New York, NY, USA, pp. 212{225. Chiang, J. T. and Hu, Y.-C. [2007], Cross-Layer Jamming Detection and Mitigation in Wireless Broadcast Networks, in ?MobiCom ?07: Proceedings of the 13th annual ACM international conference on Mobile computing and networking?, ACM, New York, NY, USA, pp. 346{349. Chirdchoo, N., Soh, W.-S. and Chua, K. C. [2008], MACA-MN: A MACA-Based MAC Protocol for Underwater Acoustic Networks with Packet Train for Multiple Neighbors, in ?Proc. IEEE Vehicular Technology Conference VTC Spring 2008?, pp. 46{50. Coupechoux, M., Baynat, B., Bonnet, C. and Kumar, V. [2005], ?CROMA { An Enhanced Slotted MAC Protocol for MANETs?, Mob. Netw. Appl. 10(1-2), 183{ 197. Ephremides, A., Wieselthier, J. and Baker, D. [1987], ?A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling?, Proceedings of the 152 IEEE 75(1), 56{73. Fang, Z., Bensaou, B. and Yuan, J. [2004], Collision-Free MAC Scheduling Algo- rithms For Wireless Ad Hoc Networks, in ?Proc. IEEE Global Telecommunications Conference GLOBECOM ?04?, Vol. 5, pp. 2770{2774. Forouzan, B. [2007], Data Communications and Networking, fourth, international edition edn, McGraw-Hill, 1221 Avenue, New York, NY, 10020, chapter 6, 11-14, pp. 161{190, 307{444. Garcia-Luna-Aceves, J. J. and Fullmer, C. L. [1999], ?Floor acquisition multiple access (FAMA) in single-channel wireless networks?, Mob. Netw. Appl. 4(3), 157{174. Garcia-Luna-Aceves, J. J. and Raju, J. [1997], Distributed Assignment of Codes for Multihop Packet-Radio Networks, in ?Proc. MILCOM 97?, Vol. 1, pp. 450{454. Gerla, M. and Tzu-Chieh Tsai, J. [1995], ?Multicluster, Mobile, Multimedia Radio Network?, Wireless Networks 1(3), 255{265. URL: http://dx.doi.org/10.1007/BF01200845 Haas, Z. and Deng, J. [2002], ?Dual Busy Tone Multiple Access (DBTMA)-A Multiple Access Control Scheme for Ad Hoc Networks?, Communications, IEEE Transac- tions on 50(6), 975{985. Hui, J. [1984], ?Throughput Analysis for Code Division Multiple Accessing of the Spread Spectrum Channel?, Vehicular Technology, IEEE Transactions on 33(3), 98{102. 153 IEEE [2007], ?IEEE Standard For Information Technology-Telecommunications And Information Exchange Between Systems-Local And Metropolitan Area Networks- Speci c Requirements - Part 11: Wireless LAN Medium Access Control (MAC) And Physical Layer (PHY) Speci cations?, IEEE Std 802.11-2007 (Revision of IEEE Std 802.11-1999) pp. C1{1184. Jain, N., Das, S. R. and Nasipuri, A. [2001], A Multichannel CSMA MAC Pro- tocol with Receiver-Based Channel Selection for Multihop Wireless Networks, in ?Proc. Tenth International Conference on Computer Communications and Net- works?, pp. 432{439. Joa-Ng, M. and Lu, I.-T. [1999], Spread Spectrum Medium Access Protocol with Collision Avoidance in Mobile Ad-hoc Wireless Network, in ?Proc. IEEE Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies INFOCOM ?99?, Vol. 2, pp. 776{783. Jubin, J. and Tornow, J. [1987], ?The DARPA Packet Radio Network Protocols?, Proceedings of the IEEE 75(1), 21{32. Kanzaki, A., Hara, T. and Nishio, S. [2007], An E cient TDMA Slot Assignment Protocol in Mobile Ad Hoc Networks, in ?SAC ?07: Proceedings of the 2007 ACM symposium on Applied computing?, ACM, New York, NY, USA, pp. 891{895. Karn, P. [1990], MACA - A New Channel Access Method for Packet Radio, in ?Com- puter Networking Conference?, Vol. 9, pp. 134{140. 154 Kloul, L. and Valois, F. [2005], Investigating Unfairness Scenarios in MANET using 802.11b, in ?PE-WASUN ?05: Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks?, ACM, New York, NY, USA, pp. 1{8. Kumar, S., Raghavan, V. S. and Deng, J. [2006], ?Medium Access Control protocols for ad hoc wireless networks: A survey?, Ad Hoc Networks 4(3), 326 { 358. URL: http://www.sciencedirect.com/science/article/B7576-4DPGSVH- 1/2/58c0f2f528f8d27ecd834b2e92c21515 Lau, T. H. and Chan, K. S. [2006], aMAC: Advanced MAC Scheme for Mobile Ad- hoc Networks, in ?Proc. Asia-Paci c Conference on Communications APCC ?06?, pp. 1{5. Law, Y. W., van Hoesel, L., Doumen, J., Hartel, P. and Havinga, P. [2005], Energy- E cient Link-Layer Jamming Attacks against Wireless Sensor Network MAC Pro- tocols, in ?SASN ?05: Proceedings of the 3rd ACM workshop on Security of ad hoc and sensor networks?, ACM, New York, NY, USA, pp. 76{88. Lee, S. W. and Cho, D. H. [1995], Distributed Reservation CDMA for Wireless LAN, in ?Proc. IEEE Global Telecommunications Conference GLOBECOM ?95?, Vol. 1, pp. 360{364. Li, M., Koutsopoulos, I. and Poovendran, R. [2007], Optimal Jamming Attacks and Network Defense Policies in Wireless Sensor Networks, in ?Proc. INFOCOM 155 2007. 26th IEEE International Conference on Computer Communications. IEEE?, pp. 1307{1315. Li, Z., Gupta, A. K. and Nandi, S. [n.d.], ?FMAC/CSR: A Fair MAC Protocol for Wireless Ad-hoc Networks?. URL: http://www.cs.jhu.edu/ z i/fmac-csr.pdf Li, Z., Nandi, S. and Gupta, A. K. [2006], ?Modeling the Short-term Unfairness of IEEE 802.11 in Presence of Hidden Terminals?, Perform. Eval. 63(4), 441{462. Liu, X., Noubir, G., Sundaram, R. and Tan, S. [2007], SPREAD: Foiling Smart Jam- mers Using Multi-Layer Agility, in ?Proc. INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE?, pp. 2536{2540. Muqattash, A. and Krunz, M. [2003], CDMA-Based MAC Protocol for Wireless Ad Hoc Networks, in ?MobiHoc ?03: Proceedings of the 4th ACM international sym- posium on Mobile ad hoc networking & computing?, ACM, New York, NY, USA, pp. 153{164. Nasipuri, A. and Das, S. R. [2000], Multichannel CSMA with Signal Power-Based Channel Selection for Multihop Wireless Networks, in ?Proc. 52nd Vehicular Tech- nology Conference IEEE VTS-Fall VTC 2000?, Vol. 1, pp. 211{218. Nasipuri, A., Zhuang, J. and Das, S. R. [1999], A Multichannel CSMA MAC Protocol for Multihop Wireless Networks, in ?Proc. WCNC Wireless Communications and Networking Conference 1999 IEEE?, pp. 1402{1406. 156 Navda, V., Bohra, A., Ganguly, S. and Rubenstein, D. [2007], Using Channel Hopping to Increase 802.11 Resilience to Jamming Attacks, in ?Proc. INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE?, pp. 2526{ 2530. Pursley, M. [1987], ?The Role of Spread Spectrum in Packet Radio Networks?, Pro- ceedings of the IEEE 75(1), 116{134. Raza ndralambo, T. and Valois, F. [2006], Performance Evaluation of Backo Algo- rithms in 802.11 Ad-Hoc Networks, in ?PE-WASUN ?06: Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks?, ACM, New York, NY, USA, pp. 82{89. So, J. and Vaidya, N. [2003], ?A Multi-Channel MAC Protocol for Ad Hoc Wireless Networks?. URL: citeseer.ist.psu.edu/so03multichannel.html Song, N.-O., Kwak, B.-J., Song, J. and Miller, M. [2003], ?Enhancement of IEEE 802.11 Distributed Coordination Function with Exponential Increase Exponential Decrease Backo Algorithm?, Vehicular Technology Conference, 2003. VTC 2003- Spring. The 57th IEEE Semiannual 4, 2775{2778 vol.4. Sousa, E. and Silvester, J. [1988], ?Spreading Code Protocols for Distributed Spread-Spectrum Packet Radio Networks?, Communications, IEEE Transactions on 36(3), 272{281. 157 Talucci, F. and Gerla, M. [1997], MACA-BI (MACA by invitation): A Wireless MAC Protocol for High Speed Ad Hoc Networking, in ?IEEE 6th International Conference on Universal Personal Communications Record Conference Record?, Vol. 2, pp. 913{917. Tang, Z. and Garcia-Luna-Aceves, J. J. [1998], Hop Reservation Multiple Access (HRMA) for Multichannel Packet Radio Networks, in ?Proc. 7th International Con- ference on Computer Communications and Networks?, pp. 388{395. Tobagi, F. and Kleinrock, L. [1976], ?Packet Switching in Radio Channels: Part III{Polling and (Dynamic) Split-Channel Reservation Multiple Access?, Communi- cations, IEEE Transactions on 24(8), 832{845. Tseng, Y.-C., Wu, S.-L., Lin, C.-Y. and Sheu, J.-P. [2001], A Multi-Channel MAC Protocol with Power Control for Multi-Hop Mobile Ad Hoc Networks, in ?Proc. International Conference on Distributed Computing Systems Workshop?, pp. 419{ 424. van Hoesel, L. F. W., Nieberg, T., Kip, H. J. and Havinga, P. J. M. [2004], Advantages of a TDMA based, energy-e cient, self-organizing MAC protocol for WSNs, in ?Proc. VTC 2004-Spring Vehicular Technology Conference 2004 IEEE 59th?, Vol. 3, pp. 1598{1602. Wang, P. and Zhuang, W. [2008], A Collision-Free MAC Scheme for Multimedia Wire- less Mesh Backbone, in ?Proc. IEEE International Conference on Communications 158 ICC ?08?, pp. 4708{4712. Wang, X. and Xiang, W. [2006], ?An OFDM-TDMA/SA MAC Protocol with QoS Constraints for Broadband Wireless LANs?, Wireless Networks 12(2), 159{170. URL: http://dx.doi.org/10.1007/s11276-005-5263-1 Wong, C. Y., Cheng, R., Lataief, K. and Murch, R. [1999], ?Multiuser OFDM with adaptive subcarrier, bit, and power allocation?, Selected Areas in Communications, IEEE Journal on 17(10), 1747{1758. Wu, C. and Li, V. [1988], Receiver-Initiated Busy-Tone Multiple Access in Packet Ra- dio Networks, in ?SIGCOMM ?87: Proceedings of the ACM workshop on Frontiers in computer communications technology?, ACM, New York, NY, USA, pp. 336{342. Wu, S.-L., Lin, C.-Y., Tseng, Y.-C. and Sheu, J.-L. [2000], A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks, in ?Proc. International Symposium on Parallel Architectures, Algo- rithms and Networks I-SPAN 2000?, pp. 232{237. Xu, W., Trappe, W., Zhang, Y. and Wood, T. [2005], The Feasibility of Launching and Detecting Jamming Attacks in Wireless Networks, in ?MobiHoc ?05: Proceed- ings of the 6th ACM international symposium on Mobile ad hoc networking and computing?, ACM, New York, NY, USA, pp. 46{57. Yang, Z. and Garcia-Luna-Aceves, J. J. [1999], Hop-Reservation Multiple Access (HRMA) for Ad-Hoc Networks, in ?Proc. IEEE Eighteenth Annual Joint Conference 159 of the IEEE Computer and Communications Societies INFOCOM ?99?, Vol. 1, pp. 194{201. You, T., Yeh, C.-H. and Hassanein, H. [2003], CSMA/IC: A New Class of Collision- Free MAC Protocols for Ad Hoc Wireless Networks, in ?Proc. Eighth IEEE Interna- tional Symposium on Computers and Communication (ISCC 2003)?, pp. 843{848. Zhai, H., Wang, J. and Fang, Y. [2006], ?DUCHA: A New Dual-Channel MAC Proto- col for Multihop Ad Hoc Networks?, Wireless Communications, IEEE Transactions on 5(11), 3224{3233. Zhai, H., Wang, J., Fang, Y. and Wu, D. [2004], A Dual-Channel MAC Protocol for Mobile Ad Hoc Networks, in ?Proc. IEEE Global Telecommunications Conference Workshops GlobeCom Workshops 2004?, pp. 27{32. 160 Appendices 161 Appendix A Source Code Listing A.1 BBC-MAC Data Link Layer Code A.1.1 Interface Class (interface.py) 1 ? ? ? If you can find someone who can debug two million lines of code and interface 3 eight connection machines for what I bid for this job , I ?d love to see him try ? ? ? 5 import sys import os 7 from stat import import threading 9 from subprocess import import Queue 11 import Receiver , Transmitter import time , random 13 import ethernet frame import bbc frame 15 from optparse import OptionParser from gnuradio import gr , gru 17 from gnuradio import usrp from gnuradio . eng option import eng option 19 from gnuradio import eng notation from gnuradio . eng notation import num to str , str to num 21 from utilities import import bbc config 23 class interface ( threading . Thread) : 25 def init ( self , usb , usrp side , path , address , verbose , chat , dynamic , experiment mode) : threading . Thread. init ( self ) 27 random. seed () self .name = "BBC MAC Interface" 29 self .mode = 1 self . dynamic = dynamic 31 self . experiment mode = experiment mode self . running = True 33 self . config change = False 162 self . handlerQueue = Queue.Queue() 35 self . tx rx pid = 1 self . decoder pid = 1 37 self . rssi = 0 self . address = address 39 self . usb = usb self . usrp side = usrp side 41 self . usrp path = path self . verbose = verbose 43 self . chat mode = chat self . handlers = [] 45 self . interface handler = None self . block transmit = time . time () 47 self . jammer type = 0 self . jammer level = 0 49 self . rcv start = 0 self . default config = bbc config . bbc config (path) 51 if self . dynamic : self . default config . SetResistance (4092 , 200) 53 self .nav = 0.0 self . transmitter = Transmitter . Transmitter( self . address , self ) 55 self . receiver = Receiver . Receiver ( self . address , self ) 57 def ShutDown( self ) : self .mode = 1 59 self . running = False try: 61 os . kill ( self . tx rx pid , 9) except: 63 pass 65 try: os . kill ( self . decoder pid , 9) 67 except: pass 69 self . receiver .ShutDown() 71 for i in range( len ( self . handlers )) : try: 73 self . handlers [ i ]. Shutdown() except: 75 pass 77 def run( self ) : self . receiver . start () 163 79 self . transmitter . start () 81 while self . running : #This is our simple way of not doing anything until the nav expires 83 if self .nav > 0: if self . verbose : 85 print "Deferring for" , self .nav ,"seconds ." time . sleep ( self .nav) 87 self .nav = 0.0 89 self . receive () 91 if self . interface handler == None: try: 93 self . interface handler = self . handlerQueue . get(True , 1) if self . verbose : 95 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, self . interface handler .name+" now owns the interface") try: 97 if time . time () > self . block transmit or self . experiment mode == False : frame = self . interface handler . send queue . get(True , 1) 99 self . transmit (frame , self . interface handler ) except Queue.Empty: 101 pass except Queue.Empty: 103 pass else : 105 try: if time . time () > self . block transmit or self . experiment mode == False : 107 frame = self . interface handler . send queue . get(True , 1) self . transmit (frame , self . interface handler ) 109 except Queue.Empty: pass 111 self .mode = 1 113 def transmit ( self , frame , handler , tx time=0): 115 #dump payload to f i l e frame . timestamp = time . time () 117 f = open( self . usrp path + "/t" , "w") f . write (frame . serialize () ) 119 f . close () 121 try: os . kill ( self . decoder pid , 9) 164 123 except: pass 125 try: 127 os . kill ( self . tx rx pid , 9) except: 129 pass 131 ret code = call ([ self . usrp path + "/usrp" , handler . config . tx () ] , stdout=PIPE, stderr=PIPE ) if tx time == 0: 133 tx time = EstimateTransmitTime( len (frame . serialize () ) , handler . config ) 135 try: os . kill ( ret code . pid , 9) 137 except: pass 139 if frame . type == 4: 141 tx time =1.1 elif frame . type == 2: # or frame . type == 4: 143 tx time =1.5 145 #tx time = 12.0 #transmit 147 if self . verbose : print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "Radio transmitter started") 149 ret code = call ([ self . usrp path + "/bbc tx .py" , " U" , self .usb , " T" , self . usrp side , " f" , "1250M" , " i" , "256" , " S" , self . usrp path + "/r" , " L" , str ( tx time ) , " J" , str ( self . jammer type) , " jammer level" , str ( self . jammer level ) ] , stdout=PIPE, stderr= PIPE) 151 try: 153 os . kill ( ret code . pid , 9) except: 155 pass if self . verbose : 157 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "Transmitted a frame") print frame 159 #inform the handler that we sent the frame 161 handler . Callback(frame , tx time ) 165 return 163 def SetJammerType( self , type) : self . jammer type = type 165 def SetJammerLevel( self , level ) : 167 self . jammer level = level 169 def receive ( self ) : try: 171 os . remove( self . usrp path + "/t") except OSError : 173 pass while self . running and self .mode == 1 and self . CheckInterfaceQueue () == False : 175 try: os . remove( self . usrp path + "/r") 177 except OSError : pass 179 self . tx rx pid = Popen ([ self . usrp path + "/ usrp rx cfile .py" , " U" , self .usb , " R" , self . usrp side , " f" , "1250M" , " d" , "128" , " N" , "16000000" , self . usrp path+"/r" ] , stdout=PIPE, stderr=PIPE) . pid 181 self . rcv start = time . time () if self . tx rx pid != 0 and self . tx rx pid != None: 183 if self . verbose : print "%s %s : %s pid=%i" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self . name, "Radio receiver started" , self . tx rx pid ) 185 else : if self . verbose : 187 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, " Unable to start radio receiver") 189 while self . CheckReceiveExit () : 191 data = None 193 if self . interface handler != None: data = self . Decode( self . interface handler . config ) 195 #? ? ? if self . interface handler != None and data == None and self . interface handler . stage==1 and self . CheckReceiveExit () : 197 #print "%s %s : %s" % (time . strftime("%H:%M:%S", time . gmtime() ) , self . name, "Decoder timeout on handler ?s expansion , testing default ") data = self . Decode( self . default config , 5.5) 199 if data == 1: #Don? t necessarily want to trash the data because this timed out 166 data = None 201 #? ? ? else : 203 data = self . Decode( self . default config ) 205 if data == 1: print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, " Decoder preempted") 207 break 209 elif data != None: try: 211 os . remove( self . usrp path + "/t") except: 213 pass self . rssi = GetRSSI( self . usrp path) 215 #pass the data off to a receive handler frame = bbc frame . bbc frame(data) 217 if self . verbose : print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "Received a frame") 219 print frame self . receiver .Enqueue(frame) 221 break 223 # Kill the Radio Receive try: 225 os . kill ( self . tx rx pid , 2) if self . verbose : 227 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, " Radio receiver stopped") except: 229 if self . verbose : print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, " Radio receiver stopped") 231 pass 233 def Decode( self , config , timeout=30.0) : if self . config change : 235 self . config change = False #print "%s %s : %s" % (time . strftime("%H:%M:%S", time . gmtime() ) , self .name, "Decoder Start ") 237 self . decoder pid = Popen ([ self . usrp path + "/usrp" , config . rx () ] , stdout=PIPE, stderr= PIPE) . pid time now = time . time () 167 239 success = False while time . time () time now < timeout and self . CheckDecodeExit() : 241 try: 243 pid , x = os . waitpid( self . decoder pid , os .WNOHANG) if pid!=0: 245 success = True break 247 except: success = True 249 break time . sleep (0.1) 251 #print "%s %s : %s" % (time . strftime("%H:%M:%S", time . gmtime() ) , self .name, "Decoder Exit % is " % (time . time () time now)) if success == False : 253 try: os . kill ( self . decoder pid , 9) 255 except: pass 257 #return 1 259 try: # Check for f i l e existence , open stats f i l e anyways , no need for two steps 261 f = open( self . usrp path + "/t" , "r") data = f . read () 263 f . close () return data 265 except IOError : if success == False : 267 return 1 else : 269 return None 271 def CheckReceiveExit( self ) : return self . CheckInterfaceQueue () == False and self .mode == 1 and CheckPID( self . tx rx pid ) and self . running and time . time () self . rcv start < 33 273 def InformConfigChange( self ) : 275 self . config change = True 277 def CheckDecodeExit( self ) : return self . CheckInterfaceQueue () == False and self .mode == 1 and self . running and self . config change == False 279 def CheckInterfaceQueue( self ) : 168 281 if self . interface handler == None: return self . handlerQueue .empty() == False 283 else : return self . interface handler . send queue .empty() == False 285 def RelinquishInterfaceControl ( self , handler , time left ) : 287 self . block transmit = time left self . interface handler = None 289 def UpdateNAV( self , timer) : 291 if self . interface handler == None: #Make sure someone doesn ? t already own the interface before setting the NAV self .nav = timer 293 self .mode = 0 295 def Enqueue( self , handler) : if self . verbose : 297 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, handler .name +" added to handler queue") self . handlerQueue . put(handler) 299 #self .mode = 0 301 def LocateHandler( self , streamid) : for i in range( len ( self . handlers )) : 303 if self . handlers [ i ]. streamid == streamid : return self . handlers [ i ] 305 return None 307 def LocateHandlerBySource( self , sstreamid ) : for i in range( len ( self . handlers )) : 309 if self . handlers [ i ]. destination streamid == sstreamid : return self . handlers [ i ] 311 return None 313 def GetNewStreamID( self ) : return random. randint (1 ,65535) 315 317 def main() : 319 parser = OptionParser ( option class=eng option ) parser . add option (" X" , " txrx subdev spec" , type="string" , default="A" , dest="side" , 321 help="select USRP TxRx side A or B") parser . add option(" U" , " usb num" , type="string" , default=0, 323 help="select USRP USB location 0 or 1 ( default=0)") 169 parser . add option(" A" , " node address" , type="int" , default=None, help="Address for this node") 325 parser . add option(" P" , " usrp path" , type="string" , default=None, help="path to usrp folder with scripts") parser . add option(" C" , " chat mode" , action="store true") 327 parser . add option(" J" , " jammer type" , type="int" , default=0) parser . add option (" jammer level" , type="eng float" , default=16e3 , 329 help="set waveform amplitude to AMPLITUDE [ default=%default ]" , metavar=" AMPL") parser . add option(" v" , " verbose" , action="store true" , dest="verbose" , 331 help="print everything to stdout") parser . add option(" dynamic" , action="store true" , default=False , help="Enable dynamic jam resistance") 333 parser . add option(" experiment" , action="store true" , default=False , help="Used to leave handlers running for as long as the channel was allocated") 335 (options , args ) = parser . parse args () f = open( options . usrp path+"/ftp frame 1514 . fr") 337 data = f . read () f . close () 339 i = interface ( options .usb num , options . side , options . usrp path , options . node address , options . verbose , options . chat mode , options .dynamic , options . experiment) 341 i . start () 343 while True: cmd = raw input () 345 cmds = cmd. split (" ") if cmd == "exit": 347 i .ShutDown() raise SystemExit 349 elif cmds[0] == "send": i . transmitter .Enqueue(data , 2222) 351 elif cmds[0] == "kick": i . interface handler .Shutdown() 353 elif cmds[0] == "jam": i .SetJammerType( int (cmds [1]) ) 355 i . SetJammerLevel( int (cmds [2]) ) 357 if name == " main ": main() A.1.2 Receiver Class (Receiver.py) import threading 170 2 import Queue import bbc frame 4 import RxHandler import sys 6 import time 8 class Receiver ( threading . Thread) : def init ( self , address , interface ) : 10 threading .Thread . init ( self ) self . handlers = [] # This should also include TxHandlers in order to properly give them their CTS/ACK Frames 12 self . queue = Queue.Queue() self . running = 1 14 self . address = address self . interface = interface 16 self .name = "Receiver" 18 def run( self ) : while self . running : 20 try: frame = self . queue . get(True ,1) 22 if frame . dstream id == 0: #Check to see if this a duplicate and if the source streamid matches the destination of a handler 24 handler = self . interface . LocateHandlerBySource(frame . sstream id ) if handler != None: 26 handler .Enqueue(frame) else : 28 temp = RxHandler . RxHandler(frame , self . interface .GetNewStreamID() , self . Callback , self . address , self . interface ) self . interface . handlers . append(temp) 30 temp. start () else : 32 handler = self . interface . LocateHandler(frame . dstream id ) if handler != None: 34 handler .Enqueue(frame) else : 36 temp = RxHandler . RxHandler(frame , frame . dstream id , self . Callback , self . address , self . interface ) self . interface . handlers . append(temp) 38 temp. start () except Queue.Empty: 40 pass 42 def Enqueue( self , frame) : 171 self . queue . put nowait(frame) 44 def ShutDown( self ) : 46 self . running = 0 48 def Callback( self , obj , data=None) : 50 print obj . stats if data!=None: 52 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, obj .name+" delivered data from stream "+str (obj . streamid)) try: 54 if self . interface . interface handler == obj : print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "removed "+obj .name+" as interface handler") 56 self . interface . interface handler = None self . interface . InformConfigChange () 58 self . interface . handlers . remove(obj) del obj 60 except: print "Unexpected error :" , sys . exc info () [0] 62 pass A.1.3 Receiver Handler Class (RxHandler.py) import Queue 2 import bbc frame import ethernet frame 4 import threading import bbc config 6 from utilities import from stats import 8 import time 10 class RxHandler( threading . Thread) : def init ( self , frame , streamid , callback , address , interface ) : 12 threading .Thread . init ( self ) self . streamid = streamid 14 self . callback = callback self . recv queue = Queue.Queue() 16 self . send queue = Queue.Queue() self . running = True 18 self . address = address self . interface = interface 20 self . stats = RxStats () 172 self . stage = 0 22 self .name = "RxHandler "+str ( self . streamid) self . rssi = None 24 self . data = None self . config = bbc config . bbc config ( self . interface . usrp path) 26 self . config .SOURCE ID = self . streamid if self . interface . dynamic : 28 self . config . SetResistance (4092 , 175) self . destination address = frame . src addr 30 self . destination streamid = frame . sstream id self . flag = 0 32 self . last frame = None self . t1 = 0 34 self . timeout = 0 self .Enqueue(frame) 36 def Enqueue( self , frame) : 38 if self . last frame == None: self . last frame = frame 40 elif frame . timestamp <= self . last frame . timestamp : if self . interface . verbose : 42 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "Frame discarded (old or duplicate )") return 44 elif frame . corrupt : if self . interface . verbose : 46 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "Frame discarded ( corrupt )") return 48 self . last frame = frame self . recv queue . put nowait(frame) 50 def Shutdown( self ) : 52 self . running = False #self . callback ( self , self . data ) 54 def run( self ) : 56 while self . running : try: 58 frame = self . recv queue . get(True ,1) if frame . type == 1: 60 #Received a RTS, Check to see if this was for us . if frame . dest addr == self . address : 62 self . destination address = frame . src addr self . destination streamid = frame . sstream id 173 64 data len = int (frame . payload) 66 self . rssi = self . interface . rssi if frame . rssi > self . rssi : 68 self . rssi = frame . rssi 70 self . timeout = EstimateChannelTime( data len , self . config , self . config . GetExpansionByRSSI( self . rssi )) 72 if self . interface . dynamic : self . config . SetResistance (4092 , 175) 74 new frame = bbc frame . bbc frame (( self . destination address , self . address , 2, self . streamid , self . destination streamid , self . rssi , self . timeout)) #return a CTS with our current RSSI 76 diff = frame . timestamp + EstimateTransmitTime( len (frame . serialize () ) , self . config ) + 3 time . time () #while time . time () < frame . timestamp+EstimateTransmitTime( len (frame . serialize () ) , self . config )+2:#14.0: #Hack so I ?m not transmitting while they ? re s t i l l transmitting this frame 78 # continue if diff > 0.0: 80 time . sleep ( diff ) self . config .SOURCE ID = self . streamid 82 self . send queue . put nowait(new frame) if self . flag == 0: 84 self . interface .Enqueue( self ) self . flag = 1 86 self . stats . rts count+=1 elif frame . type == 2: 88 #Received a CTS, Extract the time value and update the NAV timer t = float (frame . payload) 90 self . interface .UpdateNAV(t) self . running = False 92 elif frame . type == 3: #Received Data 94 if frame . dest addr == self . address : self . stage = 0 96 self . destination address = frame . src addr self . destination streamid = frame . sstream id 98 new frame = bbc frame . bbc frame (( self . destination address , self . address , 4, self . streamid , self . destination streamid , self . rssi , "ACK")) #return a ACK 100 diff = frame . timestamp + EstimateTransmitTime( len (frame . serialize () ) , self . config ) + 3 time . time () 174 #while time . time () < frame . timestamp+EstimateTransmitTime( len (frame . serialize () ) , self . config )+3:#14.0: #Hack so I ?m not transmitting while they ? re s t i l l transmitting this frame 102 # continue if diff > 0.0: 104 time . sleep ( diff ) self . config .SOURCE ID = self . streamid + 1 106 if self . interface . dynamic : self . config . SetResistance (4092 , 175) 108 self . send queue . put nowait(new frame) if self . flag == 0: 110 self . interface .Enqueue( self ) self . flag = 1 112 self . data = frame . payload if self . stats . data count==0: 114 self . stats . data time = time . time () self . stats . data count+=1 116 elif frame . type == 4: #Received an ACK 118 #this should have been given to a TxHandler , but one doesn ? t exist , so ignore self . running = False 120 except Queue.Empty: if self . t1 !=0: 122 if time . time () self . t1 > self . timeout : self . running = False 124 pass self . callback ( self , self . data) 126 def Callback( self , frame , tx time ) : 128 if frame . type == 2: #Sent out the CTS, now adjust our config and start the timer 130 if self . interface . dynamic : self . config . SetResistance ( self . rssi ) 132 self . interface . InformConfigChange () #if self . t1 == 0: 134 if self . interface . verbose : print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, " Reserved channel for "+str ( self . timeout)+" seconds .") 136 self . t1 = time . time () self . stats . cts count+=1 138 self . stage = 1 elif frame . type == 4: 140 self . stats . ack count+=1 if self . interface . dynamic : 142 self . config . SetResistance ( self . rssi ) 175 self . interface . InformConfigChange () 144 #if frame . type == 4: 146 # self . running = False A.1.4 Transmitter Class (Transmitter.py) import threading 2 import Queue import bbc frame 4 import TxHandler import time 6 import sys 8 class Transmitter( threading .Thread) : def init ( self , address , interface ) : 10 threading .Thread . init ( self ) self . address = address 12 self . interface = interface self . queue = Queue.Queue() 14 self . running = True self .name = "Transmitter" 16 def run( self ) : 18 while self . running : try: 20 payload , destination = self . queue . get(True ,1) temp = TxHandler . TxHandler( self . interface .GetNewStreamID() , self . address , self . Callback , payload , destination , self . interface ) 22 self . interface . handlers .append(temp) except Queue.Empty: 24 pass 26 def Enqueue( self , payload , destination ) : self . queue . put nowait (( payload , destination )) 28 def Callback( self , obj , message=None, time left =0.0) : 30 print obj . stats if message!=None: 32 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, obj .name+" reports that stream "+str (obj . streamid)+" was a "+message) try: 34 if self . interface . interface handler == obj : print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "removed "+obj .name+" as interface handler") 176 36 self . interface . RelinquishInterfaceControl (obj , time left ) #self . interface . interface handler = None 38 self . interface . InformConfigChange () 40 self . interface . handlers . remove(obj) del obj 42 except: print "Unexpected error :" , sys . exc info () [0] 44 pass A.1.5 Transmitter Handler Class (TxHandler.py) import Queue 2 import bbc frame import bbc config 4 import ethernet frame import thread 6 import time from utilities import 8 from stats import 10 class TxHandler : def init ( self , streamid , address , callback , data , destination , interface ) : 12 self . address = address self . destination address = destination 14 self . destination streamid = 0 self . streamid = streamid 16 self . callback = callback self . recv queue = Queue.Queue() 18 self . send queue = Queue.Queue() self . interface = interface 20 self . stats = TxStats(data) self .name = "TxHandler "+str ( self . streamid) 22 self . rssi = None self . data = data 24 self . config = bbc config . bbc config ( self . interface . usrp path) self . config .SOURCE ID = self . streamid 26 if self . interface . dynamic : self . config . SetResistance (4092 , 175) 28 self . running = True rts frame = self .CreateRTS() 30 self . send queue . put nowait( rts frame ) #Enqueue the initial frame out outbound queue self . interface .Enqueue( self ) #Enqueue our handle in the interface 32 self . stats . rts count+=1 self . stage = 0 177 34 self . rtx count = 0 self . thread id = None 36 self . last frame = None self . timeout = 0 38 self . t1 = 0 #print "Created ", self .name 40 def Enqueue( self , frame) : 42 if self . last frame == None: self . last frame = frame 44 elif frame . timestamp <= self . last frame . timestamp : if self . interface . verbose : 46 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "Frame discarded (old or duplicate )") return 48 elif frame . corrupt : if self . interface . verbose : 50 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "Frame discarded ( corrupt )") return 52 self . last frame = frame self . recv queue . put nowait(frame) 54 def Shutdown( self , message=None) : 56 try: self . thread id . exit () 58 except: pass 60 self . callback ( self , message , self . t1 + self . timeout) 62 def Callback( self , frame , tx time ) : if frame . type==1 and self . stats . rts count==1: 64 self . stats . send time = time . time () tx time #This is the very fi r s t callback for the actual transmit if frame . type == 3: 66 if self . interface . dynamic : self . config . SetResistance (4092 , 175) 68 self . interface . InformConfigChange () 70 self . thread id = thread . start new thread ( self . thread ,( frame , tx time )) 72 def thread( self , frame , tx time ) : if frame . type == 1: #We are waiting for a CTS 74 try: 178 rcv frame = self . recv queue . get(True , 30) #Easy way to do a timer , use the queue timeout 76 if rcv frame . type == 2: #We got the CTS, send out Data self . destination streamid = rcv frame . sstream id 78 if rcv frame . rssi > self . rssi : self . rssi = rcv frame . rssi 80 tmp rssi = self . interface . rssi 82 self . stats . rssi = self . rssi 84 diff = rcv frame . timestamp + 1.5 EstimateTransmitTime( len ( rcv frame . serialize () ) , self . config ) + 3 time . time () #while time . time () < rcv frame . timestamp+EstimateTransmitTime( len ( rcv frame . serialize () ) , self . config )+3:#14.0: #Hack so I ?m not transmitting while they ? re s t i l l transmitting this frame 86 # continue if diff > 0.0: 88 time . sleep ( diff ) 90 if self . interface . dynamic : self . config . SetResistance ( self . rssi ) 92 if self . interface . dynamic and self . config . GetExpansionByRSSI( tmp rssi ) > self . config .CODEC EXPANSION and self . rtx count < 2: #catch it early and re transmit the RTS 94 self . config . SetResistance (4092 , 175) rts frame = self .CreateRTS( tmp rssi ) 96 if self . interface . verbose : print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self . name, "Expansion adjustment needed , re sending RTS") 98 self . send queue . put nowait( rts frame ) self . stats . rts count+=1 100 self . rtx count+=1 else : 102 self . timeout = float ( rcv frame . payload) if self . interface . verbose : 104 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self . name, "Reserved channel for "+str ( self . timeout)+" seconds .") if self . t1 == 0: 106 self . t1 = time . time () self . stats . expansion = self . config .CODEC EXPANSION 108 self . config .SOURCE ID = self . streamid + 1 data frame = self . CreateDataFrame() 110 self . send queue . put nowait(data frame) self . stats . data count+=1 179 112 self . rtx count = 0 except Queue.Empty: 114 if self . rtx count < 2: self . config .SOURCE ID = self . streamid 116 rts frame = self .CreateRTS() self . send queue . put nowait( rts frame ) 118 if self . interface . verbose : print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "CTS timeout , re sending RTS") 120 self . stats . rts count+=1 self . rtx count+=1 122 else : #3x is max retransmit time to die if self . interface . verbose : 124 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "RTS retransmission maxed, giving up") #signal upper layer 126 self . stats . rts fail = True self .Shutdown(" failure ") 128 elif frame . type == 3: #We are waiting for an ACK try: 130 rcv frame = self . recv queue . get(True , 30 ) #Easy way to do a timer , use the queue timeout if rcv frame . type == 4: 132 if self . interface . verbose : print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "received ack") 134 self . stats . ack time = time . time () self . stats . latency = self . stats . ack time self . stats . send time 136 self .Shutdown("success") except Queue.Empty: 138 if self . rtx count < 2 and time . time () self . t1 < self . timeout : if self . interface . verbose : 140 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "ACK time out , re sending data frame") self . config .SOURCE ID = self . streamid + 1 142 data frame = self . CreateDataFrame() if self . interface . dynamic : 144 self . config . SetResistance ( self . rssi ) self . send queue . put nowait(data frame) 146 #self . interface . Enqueue( self . CreateDataFrame () , self ) self . rtx count+= 1 148 self . stats . data count+=1 else : #3x is max retransmit time to die 150 if self . interface . verbose : 180 print "%s %s : %s" % (time . strftime ("%H:%M:%S" , time .gmtime() ) , self .name, "Exceeded channel allocation , giving up") 152 #Signal upper layer self . stats . data fail = True 154 self .Shutdown(" failure ") 156 158 def CreateRTS( self , rssi=None) : if rssi==None: 160 self . rssi = GetRSSI( self . interface . usrp path) else : 162 self . rssi = rssi # Create a config based on the RSSI we have and use it for the estimation 164 #self . timeout = EstimateChannelTime( self . data , self . config ) return bbc frame . bbc frame (( self . destination address , self . address , 1, self . streamid , self . destination streamid , self . rssi , str ( len ( self . data)))) 166 def CreateDataFrame( self ) : 168 return bbc frame . bbc frame (( self . destination address , self . address , 3, self . streamid , self . destination streamid , self . rssi , self . data)) 170 def Encode( self , frame) : return A.1.6 BBC Con g Class (bbc con g.py) 1 from cStringIO import StringIO 3 class bbc config : def init ( self , path) : 5 self .DIAGNOSTICS = False self .PATH = path 7 # SCHEDULER Configuration 9 self .SCHEDULER TX notRX = 0 self .SCHEDULER REALTIME = 0 11 # SOURCE Configuration 13 self .SOURCENAME = "r" self .SOURCE ID = 1 15 # CODEC Configuration 17 self .CODEC MESSAGE BITS = 512 self .CODEC RANDOM BITS = 8 181 19 self .CODEC CLAMP BITS = 1 self .CODEC FRAGMENT BITS = 1 21 self .CODEC STOP BITS = 100 self .CODEC EXPANSION = 500 23 self .CODEC PACKET LOAD = 2 self .CODEC DECODE LIMIT = 2 25 # BUFFER Configuration 27 self .BUFFER PACKETS = 4.0 self .BUFFERLAMBDA = 0.4 29 # MODEM Configuration 31 self .MODEM PACKET RATE BPS = 500000 self .MODEM SAMPLES PER BIT = 4 33 self .MODEM GAIN DB = 80.0 self .MODEM CHANNEL LOSS DB = 8.0 35 self .MODEMTHRESHOLDPCT = 46.3744 self .MODEM HYSTERESIS PCT = 5.0 37 self .MODEM JITTER BITS = 2.0 self .MODEM CUSHION PCT = 10.0 39 # SINK Configuration 41 self .SINK NAME = "t" self .SINK SAMPLE LIMIT = 16000000 43 def tx( self ) : 45 self .SOURCENAME = "t" self .SINK NAME = "r" 47 self .MODEM CHANNEL LOSS DB = 3.0 self .SCHEDULER TX notRX = 1 49 f = open( self .PATH+"/tx . ini" , "wt") f . write ( self . format () ) 51 f . close () return self .PATH+"/tx . ini" 53 def rx( self ) : 55 self .SOURCENAME = "r" self .SINK NAME = "t" 57 self .MODEM CHANNEL LOSS DB = 16.0 self .SCHEDULER TX notRX = 0 59 f = open( self .PATH+"/rx . ini" , "wt") f . write ( self . format () ) 61 f . close () return self .PATH+"/rx . ini" 63 182 def format( self ) : 65 s = StringIO () for k,v in self . dict . items () : 67 if str (k) == "DIAGNOSTICS": if v: 69 s . write ("DIAGNOSTICSnn") elif str (k) == "PATH" or str (k) == "SINK NAME" or str (k) == "SOURCENAME": 71 s . write ("%s=n"%sn"nn" % (k,v)) else : 73 s . write ( ?%s=%snn ? % (k,v)) return s . getvalue () 75 def SetResistance ( self , rssi , value=None) : 77 if value!=None: self .CODEC EXPANSION = value 79 return 81 self .CODEC EXPANSION = self . GetExpansionByRSSI( rssi ) 83 def GetExpansionByRSSI( self , rssi ) : if rssi <= 350: 85 return 50 elif rssi <= 700: 87 return 75 elif rssi <= 1050: 89 return 100 elif rssi <= 1350: 91 return 150 else : 93 return 175 A.1.7 BBC-MAC Frame Class (bbc frame.py) 1 import struct import time 3 from crc16 import 5 class bbc frame : def init ( self , raw frame) : 7 self . types = (1 ,2 ,3 ,4) # RTS CTS DATA ACK self . timestamp = time . time () 9 if isinstance (raw frame , str ) : self . raw frame = raw frame 11 try: 183 self . dest addr , self . src addr , self . type , self . sstream id , self . dstream id , self . rssi , self . crc , self . timestamp = struct . unpack("!HHBHHHHd" , raw frame [:21]) 13 self . payload = raw frame [21:] if self . crc != crc16 ( str ( self . payload)) : 15 self . corrupt = True else : 17 self . corrupt = False except: 19 self . corrupt = True else : 21 self . dest addr , self . src addr , self . type , self . sstream id , self . dstream id , self . rssi , self . payload = raw frame self . crc = crc16 ( str ( self . payload)) 23 #self . raw frame = self . serialize () 25 def toString ( self ) : s = "Destination : "+str ( self . dest addr )+"nnSource : "+str ( self . src addr )+"nnType: "+str ( self . type)+"nnSource StreamID : "+str ( self . sstream id )+"nnDestination StreamID : "+str ( self . dstream id )+"nnRSSI: "+str ( self . rssi )+"nnCRC: "+str ( self . crc )+"nnTimestamp: "+str ( self . timestamp)#+"nnPayload :nn"+str ( self . payload ) 27 return s 29 def repr ( self ) : return self . toString () 31 def serialize ( self ) : 33 return struct . pack("!HHBHHHHd" , self . dest addr , self . src addr , self . type , self . sstream id , self . dstream id , self . rssi , self . crc , self . timestamp) + str ( self . payload) 35 def size ( self ) : return len ( self . serialize () ) A.1.8 Utilities Class (utilities.py) import os 2 import bbc config from crc16 import 4 from math import crc = CRC16() 6 def GetRSSI(path) : 8 while True: try: 10 f = open(path+"/ rssi " , "rt") rssi = int ( f . read () ) 184 12 f . close () break 14 except: continue 16 return rssi 18 def EstimateChannelTime( data len , config , expansion=None) : t = 3 (EstimateTransmitTime( data len , config , expansion)+30) #+ 12 + 18 + 12#Worst cast estimation , ACK and RTS frames are same size 20 return t 22 def EstimateTransmitTime( data len , config , expansion=None) : if expansion == None: 24 expansion = config .CODEC EXPANSION one = ceil ( ( data len /(( config .CODEC MESSAGE BITS/8.0) 10.0) )/config .CODEC PACKET LOAD ) 26 two = (( config .CODEC MESSAGE BITS expansion)/8) config .BUFFERLAMBDA three = (( config .CODEC MESSAGE BITS expansion)/8) + 1 28 res = ceil (4 (((one two + three ) 8 4)/config .MODEM PACKET RATE BPS)) return res 30 def CheckPID(pid) : 32 try: os . kill (pid , 0) 34 return True except: 36 return False 38 def StatFileSize (path) : try: 40 return os . stat (path) . st size except: 42 return 0 44 def GetCRC(data) : crc . update( str (data)) 46 return crc . checksum() A.1.9 CRC16 Class (crc16.py) # crc16 . py by Bryan G. Olson , 2005 2 # This module is free software and may be used and # distributed under the same terms as Python i t s e l f . 4 """ 6 CRC 16 in Python , as standard as possible . This is 185 the ? reflected ? version , which is usually what people 8 want . See Ross N. Williams ? /A Painless Guide to CRC error detection algorithms /. 10 """ 12 from array import array 14 def crc16 ( string , value=0): 16 """ Single function interface , like gzip module ?s crc32 """ 18 for ch in string : value = table [ ord(ch) ^ (value & 0xff ) ] ^ (value >> 8) 20 return value 22 class CRC16( object ) : 24 """ Class interface , like the Python library ?s cryptographic hash functions (which CRC?s are definitely not .) 26 """ 28 def init ( self , string=? ?) : self . val = 0 30 if string : self . update( string ) 32 def update( self , string ) : 34 self . val = crc16 ( string , self . val ) 36 def checksum( self ) : return chr( self . val >> 8) + chr( self . val & 0xff ) 38 def hexchecksum( self ) : 40 return ?%04x ? % self . val 42 def copy( self ) : clone = CRC16() 44 clone . val = self . val return clone 46 48 # CRC 16 poly : p(x) = x 16 + x 15 + x 2 + 1 # top bit implicit , reflected 50 poly = 0xa001 table = array( ?H?) 186 52 for byte in range (256) : crc = 0 54 for bit in range (8) : if (byte ^ crc ) & 1: 56 crc = ( crc >> 1) ^ poly else : 58 crc >>= 1 byte >>= 1 60 table . append( crc ) A.1.10 Stats Module (stats.py) from cStringIO import StringIO 2 4 class TxStats : def init ( self , data) : 6 self . raw data = data self . rts count = 0 8 self . data count = 0 self . rts fail = False 10 self . data fail = False self . send time = 0 12 self . ack time = 0 self . rssi = 0 14 self . expansion = 0 self . latency = 0 16 def repr ( self ) : 18 return self . toString () 20 def toString ( self ) : s = StringIO () 22 for k,v in self . dict . items () : if str (k) == "raw data": 24 continue s . write ( ?%snt ? % k) 26 s . write ( ?nn ?) 28 for k,v in self . dict . items () : if str (k) == "raw data": 30 continue s . write ( ?%snt ? % v) 32 s . write ( ?nn ?) 187 34 return s . getvalue () 36 class RxStats : def init ( self ) : 38 self . rts count = 0 self . data count = 0 40 self . ack count = 0 self . cts count = 0 42 self . data time = 0 44 def repr ( self ) : return self . toString () 46 def toString ( self ) : 48 s = StringIO () for k,v in self . dict . items () : 50 if str (k) == "raw data": continue 52 s . write ( ?%snt ? % k) s . write ( ?nn ?) 54 for k,v in self . dict . items () : 56 if str (k) == "raw data": continue 58 s . write ( ?%snt ? % v) s . write ( ?nn ?) 60 return s . getvalue () A.2 Radio Scripts Code A.2.1 USRP Receiver Script (usrp rx c le.py) 1 #!/ usr/bin/env python 3 """ Read samples from the USRP and write to f i l e formatted as binary 5 outputs single precision complex float values or complex short values ( interleaved 16 bit signed short integers ) . 7 """ 9 from gnuradio import gr , gru , eng notation #from gnuradio import audio 188 11 from gnuradio import usrp from gnuradio . eng option import eng option 13 from optparse import OptionParser from usrpm import usrp dbid 15 import time import sys 17 import thread 19 class my graph(gr . flow graph ) : #class my graph( gr . top block ) : 21 def init ( self ) : 23 gr . flow graph . init ( self ) #gr . top block . i n i t ( self ) 25 self . rssi = 0 27 usage="%prog : [ options ] output filename output filename2" parser = OptionParser( option class=eng option , usage=usage) 29 parser . add option(" R" , " rx subdev spec" , type="subdev" , default =(0, 0) , help="select USRP Rx side A or B ( default=A)") 31 parser . add option(" U" , " usb num" , type="int" , default=0, help="select USRP USB location 0 or 1 ( default=0)") 33 parser . add option(" d" , " decim" , type="int" , default=16, help="set fgpa decimation rate to DECIM [ default=%default ]") 35 parser . add option(" f" , " freq" , type="eng float" , default=None, help="set frequency to FREQ" , metavar="FREQ") 37 parser . add option(" g" , " gain" , type="eng float" , default=None, help="set gain in dB ( default is midpoint)") 39 parser . add option(" 8" , " width 8" , action="store true" , default=False , help="Enable 8 bit samples across USB") 41 parser . add option( " no hb" , action="store true" , default=False , help="don ?t use halfband filter in usrp") 43 parser . add option( " s" ," output shorts" , action="store true" , default=False , help="output interleaved shorts in stead of complex floats ") 45 parser . add option(" N" , " nsamples" , type="eng float" , default=None, help="number of samples to collect [ default=+inf ]") 47 parser . add option(" C" , " nchan" , type="int" , default=1, help="set number of channels to use (RX on both daughterboards)") 49 (options , args ) = parser . parse args () 51 if len ( args ) < 1: parser . print help () 53 raise SystemExit , 1 55 #with multiple channels , need multiple f i l e s for receiver sinks so both receivers are not 189 # writing to the same f i l e on the driver computer 57 if options . nchan > 1: filename A = args [0] 59 filename B = args [1] else : 61 filename = args [0] 63 self . fn = filename if options . freq is None: 65 parser . print help () sys . stderr . write ( ?You must specify the frequency with f FREQnn ?) ; 67 raise SystemExit , 1 69 if options . no hb or ( options . decim<8): self . fpga filename="std 4rx 0tx . rbf" #Min decimation of this firmware is 4. contains 4 Rx paths without halfbands and 0 tx paths . 71 if options . output shorts : self .u = usrp . source s (which=options .usb num , decim rate=options . decim , fpga filename=self . fpga filename ) 73 else : self .u = usrp . source c (which=options .usb num , decim rate=options . decim , fpga filename=self . fpga filename ) 75 else : #standard fpga firmware " std 2rxhb 2tx . rbf " contains 2 Rx paths with halfband f i l t e r s and 2 tx paths ( the default ) min decimation 8 77 if options . output shorts : self .u = usrp . source s (which=options .usb num , decim rate=options . decim) 79 else : self .u = usrp . source c (which=options .usb num , decim rate=options . decim) 81 #use more than 1 channel if specified 83 #this will allow a USRP to TX or RX on both daughterboards simultaneously if options . nchan > 1: 85 nchan = options . nchan if self .u.nddc() < nchan : 87 sys . stderr . write ( ?This code requires an FPGA build with %d DDCs. This FPGA has only %d.nn ? % (nchan , self .u.nddc() )) raise SystemExit 89 if not self .u. set nchannels (nchan) : 91 sys . stderr . write ( ? set nchannels(%d) failednn ? % (nchan ,) ) raise SystemExit 93 #self . subdev = self .u. db [0] + self .u. db [1] 95 190 self . subdev = ( self .u.db [0][0] , self .u.db [1][0]) 97 print "Using RX daughterboard %s" % ( self . subdev [0]. side and name () ,) 99 print "Using RX daughterboard %s" % ( self . subdev [1]. side and name () ,) 101 if options . gain is None: g A = self . subdev [0]. gain range () 103 options . gain = float (g A[0]+g A [1]) /2 105 #use the same gain for both sides self . subdev [0]. set gain ( options . gain) 107 self . subdev [1]. set gain ( options . gain) # r = usrp . tune ( self .u, i , self . subdev [ i ] , target freq ) 109 r A = self .u. tune(0 , self . subdev [0] , options . freq ) if not r A : 111 sys . stderr . write ( ? Failed to set frequency for RX daughterboard %snn ? % ( self . subdev [0]. side and name () )) raise SystemExit , 1 113 r B = self .u. tune(1 , self . subdev [1] , options . freq ) 115 if not r B : sys . stderr . write ( ? Failed to set frequency for RX daughterboard %snn ? % ( self . subdev [1]. side and name () )) 117 raise SystemExit , 1 119 else : # using only 1 channel in this case 121 # determine the daughterboard subdevice we ? re using per argument l i s t self . subdev = usrp . selected subdev ( self .u, options . rx subdev spec ) 123 print "Using RX daughterboard %s" % ( self . subdev . side and name () ,) 125 #set the gain if options . gain is None: 127 # if no gain was specified , use the mid point in dB g = self . subdev . gain range () 129 options . gain = float (g[0]+g [1]) /2 131 self . subdev . set gain ( options . gain) 133 r = self .u. tune(0 , self . subdev , options . freq ) if not r : 135 sys . stderr . write ( ? Failed to set frequencynn ?) raise SystemExit , 1 137 if options . width 8 : 191 139 sample width = 8 sample shift = 8 141 format = self .u. make format(sample width , sample shift ) r = self .u. set format (format) 143 if options . output shorts : #default value is fine here for multiple channels since 145 #we will be using complex floats self . dst = gr . file sink (gr . sizeof short , filename ) 147 else : if options . nchan == 1: 149 self . dst = gr . file sink (gr . sizeof gr complex , filename ) else : 151 #establish separate f i l e sinks for the two channels self . dst A = gr . file sink (gr . sizeof gr complex , filename A) 153 self . dst B = gr . file sink (gr . sizeof gr complex , filename B ) 155 if options . nsamples is None:#this is the default if options . nchan == 1: 157 self . connect( self .u, self . dst) else : #multiple channels 159 di = gr . deinterleave (gr . sizeof gr complex ) self . connect( self .u, di ) 161 self . connect (( di ,0) , self . dst A) self . connect (( di ,1) , self . dst B) 163 else : 165 if options . output shorts : self . head = gr . head(gr . sizeof short , int ( options . nsamples) 2) 167 else : self . head = gr . head(gr . sizeof gr complex , int ( options . nsamples)) 169 self . connect( self .u, self .head , self . dst) 171 if options . rx subdev spec is None: options . rx subdev spec = usrp . pick rx subdevice ( self .u) 173 self . rx subdev = options . rx subdev spec 175 self .u. set mux(usrp . determine rx mux value( self .u, options . rx subdev spec )) #self .u. set mux (gru . hexint (0 xf3f2f1f0 )) 177 #PRINT STATEMENTS 179 print "Using USB Port %d" % ( options .usb num) if ( options . nchan > 1) : 181 print "Using %d Channels" % ( options . nchan) else : 183 print "Using %d Channel" % ( options . nchan) 192 185 #display USB sample rate input rate = self .u. adc freq () / self .u. decim rate () 187 print "USB sample rate %s" % ( eng notation . num to str ( input rate )) self . rssi run = True 189 def GetRSSI( self , d, t) : 191 reads = [] avgs = [] 193 while self . rssi run : tmp = self .u. read aux adc ( self . rx subdev [0] ,0) 195 reads . append(tmp) self . rssi = sum( reads [ 1140:])/1140 197 avgs .append( self . rssi ) file = open( receive . fn+" ssi " , "wt") 199 file . write ( str (max(avgs [ 20:]) )) file . close () 201 if name == ? main ? : 203 try: receive = my graph() 205 thread . start new thread ( receive .GetRSSI ,(0 ,0) ) receive . run() 207 print "Receiving Complete ." receive . rssi run = False 209 except KeyboardInterrupt : 211 # pass receive . rssi run = False 213 receive . stop () A.2.2 USRP Transmitter Script (bbc tx.py) #!/ usr/bin/env python 2 # This program reads waveform data from the f i l e " bbc tx . dat" and sends 4 # it to the USRP for broadcast . 6 # This f i l e was derived from the usrp siggen . py f i l e that came with # GNU Radio . It was stripped to just the essentials needed to transmit 8 # a baseband signal from a complex f i l e source . 10 # The f i l e format is complex IQ data pairs where both values are IEEE # single precision floating point numbers in l i t t l e endian format . 12 # The f i r st value is I and the second value is Q. The data is present 193 # only on the I data . The Q data is all zeros . 14 from gnuradio import gr , gru 16 from gnuradio import usrp from gnuradio . eng option import eng option 18 from gnuradio import eng notation from gnuradio . eng notation import num to str , str to num 20 from optparse import OptionParser import sys 22 import time import os 24 from subprocess import 26 class bbc tx graph(gr . top block ) : 28 def init ( self , usb num , sink path , jammer , jammer level=0, sink path B=None) : #included usb num from parameter l i s t to define which usb 30 gr . top block . init ( self ) #default interpolator rate 32 self . interp = 64 34 if jammer==0: self . txfile = gr . file source (gr . sizeof gr complex , sink path ,1) 36 self . usrp = usrp . sink c (usb num , self . interp ) # change from 0 to 1 if necessary self . connect ( self . txfile , self . usrp) 38 elif jammer==1: call ([ "/Users/Derek/Desktop/jammer/jammer" , " C" ,"/Users/Derek/Desktop/jammer/tx . ini" , " N" , "1000000" ," J" , str ( jammer level ) ]) 40 self . txfileA = gr . file source (gr . sizeof gr complex , sink path , 1) self . txfileB = gr . file source (gr . sizeof gr complex , "/Users/Derek/Desktop/jammer/r" , 1) 42 self . usrp = usrp . sink c (which=usb num , interp rate=self . interp , nchan=2) #do connect 44 intl = gr . interleave (gr . sizeof gr complex ) self . connect( self . txfileA , ( intl , 0)) 46 self . connect( self . txfileB , ( intl , 1)) self . connect( intl , self . usrp) 48 elif jammer==2: self . txfileA = gr . file source (gr . sizeof gr complex , sink path , 1) 50 self . noisegen = gr . noise source c (gr .GR GAUSSIAN, 500 jammer level ) self . usrp = usrp . sink c (which=usb num , interp rate=self . interp , nchan=2) 52 #do connect intl = gr . interleave (gr . sizeof gr complex ) 54 self . connect( self . txfileA , ( intl , 0)) 194 self . connect( self . noisegen , ( intl , 1)) 56 self . connect( intl , self . usrp) elif jammer==3: 58 self . noisegen = gr . noise source c (gr .GR GAUSSIAN, 500 jammer level ) self . usrp = usrp . sink c (usb num , self . interp ) # change from 0 to 1 if necessary 60 self . connect ( self . noisegen , self . usrp) 62 def usb freq ( self ) : return self . usrp . dac freq () / self . interp 64 def usb throughput ( self ) : 66 return self . usb freq () 4 68 def set interpolator ( self , interp ) : self . interp = interp 70 self . usrp . set interp rate ( interp ) 72 def set freq single ( self , target freq ) : """ 74 Set the center frequency we ? re interested in . 76 @param target freq : frequency in Hz @rypte : bool 78 Tuning is a two step process . First we ask the front end to 80 tune as close to the desired frequency as it can . Then we use the result of that operation and our target frequency to 82 determine the value for the digital up converter . """ 84 r = self . usrp . tune( self . subdev . which , self . subdev , target freq ) if r : 86 print "r . baseband freq =" , eng notation . num to str (r . baseband freq ) print "r . dxc freq =" , eng notation . num to str (r . dxc freq ) 88 print "r . residual freq =" , eng notation . num to str (r . residual freq ) print "r . inverted =" , r . inverted 90 print " OK" return True 92 return False 94 def set freq multi ( self , side , target freq ) : 96 """ Set the center frequency we ? re interested in . 98 @param side : 0 = side A, 1 = side B 195 100 @param target freq : frequency in Hz @rtype : bool 102 Tuning is a two step process . First we ask the front end to 104 tune as close to the desired frequency as it can . Then we use the result of that operation and our target frequency to 106 determine the value for the digital up converter . """ 108 print "Tuning side %s to %sHz" % (("A" , "B") [ side ] , num to str ( target freq )) 110 r = self . usrp . tune( self . subdev [ side ]. which , self . subdev [ side ] , target freq ) if r : 112 print " r . baseband freq =" , num to str (r . baseband freq ) print " r . dxc freq =" , num to str (r . dxc freq ) 114 print " r . residual freq =" , num to str (r . residual freq ) print " r . inverted =" , r . inverted 116 print " OK" return True 118 else : 120 print " Failed !" 122 return False 124 def main () : parser = OptionParser ( option class=eng option ) 126 parser . add option (" T" , " tx subdev spec" , type="subdev" , default =(0, 0) , help="select USRP Tx side A or B (may also use A:0 or A:1 format)") 128 parser . add option (" f" , " rf freq " , type="eng float" , default=None, help="set RF center frequency to FREQ") 130 parser . add option (" i" , " interp" , type="int" , default=64, help="set fgpa interpolation rate to INTERP") 132 parser . add option(" U" , " usb num" , type="int" , default=0, help="select USRP USB location 0 or 1 ( default=0)") 134 parser . add option(" J" , " jammer" , type="int" , default=0, help="0 = None, 1 = Pulse Jammer, 2 = Gaussian Jammer") parser . add option (" jammer level" , type="int" , default=32, 136 help="set the jammer level [0 ,64]") parser . add option(" S" , " sink path" ,type="string" , default=None, help="set sink file path for transmission 1") 138 parser . add option(" Q" , " sink path B" ,type="string" , default=None, help="set sink file path for transmission 2") parser . add option(" P" , " tx subdev spec B" , type="subdev" , default =(0, 0) , 140 help="select USRP Tx side A or B (may also use A:0 or A:1 format)") 196 parser . add option(" L" , " tx time" ,type="float" , default =8.0, help ="set the length to transmit for") 142 (options , args ) = parser . parse args () 144 if len ( args ) != 0: parser . print help () 146 raise SystemExit 148 if options . rf freq is None: sys . stderr . write ("usrp siggen : must specify RF center frequency with f RF FREQnn") 150 parser . print help () raise SystemExit 152 fg = bbc tx graph( options .usb num , options . sink path , options .jammer , options . jammer level , options . sink path B ) 154 fg . set interpolator ( options . interp ) 156 print "Using USB Port %d" % ( options .usb num) 158 print "Sink path : %s" % ( options . sink path ) if ( options .jammer) : 160 print "Jammer running at level : %i" % ( options . jammer level ) 162 if options .jammer==0: print "Using 1 Channel" 164 # determine the daughterboard subdevice we ? re using if options . tx subdev spec is None: 166 options . tx subdev spec = usrp . pick tx subdevice ( fg .u) 168 m = usrp . determine tx mux value( fg . usrp , options . tx subdev spec ) #print "mux = %#04x" % (m,) 170 fg . usrp . set mux(m) #fg . usrp . set mux (0xba98) 172 fg . subdev = usrp . selected subdev ( fg . usrp , options . tx subdev spec ) 174 print "Using TX daughterboard %s" % ( fg . subdev . side and name () ,) 176 fg . subdev . set gain ( fg . subdev . gain range () [1]) # set max Tx gain 178 if not fg . set freq single ( options . rf freq ) : sys . stderr . write ( ? Failed to set RF frequencynn ?) 180 raise SystemExit 182 fg . subdev . set enable (True)# enable transmitter 197 184 else : # we ? re using both daughterboard slots , thus subdev is a 2 tuple print "Using 2 Channels" 186 fg . subdev = ( fg . usrp .db [0][0] , fg . usrp .db [1][0]) print "Using TX daughterboard %s" % ( fg . subdev [0]. side and name () ,) 188 print "Using TX daughterboard %s" % ( fg . subdev [1]. side and name () ,) 190 #m A = usrp . determine tx mux value ( fg . usrp , options . tx subdev spec ) 192 #m B = usrp . determine tx mux value ( fg . usrp , options . tx subdev spec B ) #print "mux = %#04x" % (m,) 194 #fg . subdev [0]. set mux (m A) #fg . subdev [1]. set mux (m B) 196 #fg . usrp . set mux (m A) fg . usrp . set mux(gru . hexint (0xBA98)) 198 fg . subdev [0]. set gain ( fg . subdev [0]. gain range () [1]) # set max Tx gain 200 fg . subdev [1]. set gain ( fg . subdev [1]. gain range () [1]) # set max Tx gain 202 #use same frequency for both transmitters fg . set freq multi (0 , options . rf freq ) 204 fg . set freq multi (1 , options . rf freq ) #fg . subdev [0]. set freq ( options . rf freq ) 206 #fg . subdev [1]. set freq ( options . rf freq ) 208 fg . subdev [0]. set enable (True) # enable transmitter fg . subdev [1]. set enable (True) # enable transmitter 210 try: 212 #size = os . stat ( options . sink path ) . st size #tx sec = ( size 163840)/( fg . usb freq () ) # num samples/ tx samples sec 214 #if tx sec > 8: # tx sec = 8 216 print "Transmitting for" , str ( options . tx time ) 218 #t1 = time . time () #fg . run () 220 #t2 = time . time () #print "%i" % (t2 t1 ) 222 fg . start () time . sleep ( options . tx time ) 224 fg . stop () print "Transmission Completed.nn" 226 except KeyboardInterrupt : #pass 228 fg . stop () 198 230 if name == ? main ? : main() A.3 BBC Source Code A.3.1 bbcftp.h 1 / Application Layer for the Real time BBC Codec/Modem 3 William L. Bahn 5 Academy Center for Information Security Department of Computer Science 7 United States Air Force Academy USAFA, CO 80840 9 FILE : . . . . . . . . . . . . bbcftp .h 11 DATE CREATED: . . . . 13 SEP 07 DATE MODIFIED : . . . 13 SEP 07 13 15 REVISION HISTORY 17 19 DESCRIPTION 21 / 23 #ifndef BBCFTPdotH #define BBCFTPdotH 25 // 27 // REQUIRED INCLUDES // 29 #include "config .h" 31 #include "source .h" #include "codec .h" 33 #include "buffer .h" #include "modem.h" 35 #include "sink .h" 199 37 #include "dirtyd .h" 39 // // PARAMETER DEFINITIONS 41 // 43 #define BBC FTP BYTES CHECKSUM (4) #define BBC FTP BYTES SEQNUM (2) 45 #define BBC FTP BYTES LOADBITS (2) #define BBC FTP BYTES ID (2) 47 #define BBC FTP OFFSET CHECKSUM (0) 49 #define BBC FTP OFFSET ID (BBC FTP OFFSET CHECKSUM + BBC FTP BYTES CHECKSUM) #define BBC FTP OFFSET SEQNUM (BBC FTP OFFSET ID + BBC FTP BYTES ID ) 51 #define BBC FTP OFFSET LOADBITS (BBC FTP OFFSET SEQNUM + BBC FTP BYTES SEQNUM ) #define BBC FTP OFFSET PAYLOAD (BBC FTP OFFSET LOADBITS + BBC FTP BYTES LOADBITS) 53 #define BBC FTP HEADER BYTES (BBC FTP OFFSET PAYLOAD) 55 // // STRUCTURE TYPE DEFINITIONS 57 // 59 typedef struct BBCFTP BBCFTP; 61 // // STRUCTURE DEFINITIONS 63 // 65 // NOTE: Normally the structure definition would be in the .c f i l e to make // the structure members inaccessible to outside functions except through 67 // public function calls . But for the real time code it has been decided // to make the structure members directly visible to the functions that 69 // manipulate them . 71 struct BBCFTP f 73 CONFIG config ; SOURCE source ; 75 CODEC codec ; BUFFER buffer ; 77 MODEM modem; SINK sink ; 79 g; 81 // 200 // PUBLIC FUNCTION PROTOTYPES 83 // 85 BBCFTP BBCFTP Del(BBCFTP p) ; BBCFTP BBCFTP New(char filename , DWORD errcode ) ; 87 void PrintMessage(BYTE base) ; 89 void SetMessageChecksum(BYTE base , DWORD v) ; 91 void SetMessageSeq(BYTE base , WORD v) ; void SetMessageLoadBits(BYTE base , WORD v) ; 93 void SetMessageID(BYTE base , WORD v) ; void SetMessagePayload(BYTE base , BYTE source , DWORD bytes , int offset ) ; 95 DWORD GetMessageChecksum(BYTE base) ; 97 WORD GetMessageSeq(BYTE base) ; WORD GetMessageLoadBits(BYTE base) ; 99 WORD GetMessageID(BYTE base) ; BYTE GetMessagePayload(BYTE base) ; 101 103 // #endif A.3.2 bbcftp.c 1 / Application Layer Module for the Real time BBC Codec/Modem FTP program 3 William L. Bahn 5 Academy Center for Information Security Department of Computer Science 7 United States Air Force Academy USAFA, CO 80840 9 FILE : . . . . . . . . . . . . bbcftp . c 11 DATE CREATED: . . . . 18 SEP 07 DATE MODIFIED : . . . 18 SEP 07 13 15 REVISION HISTORY 17 19 DESCRIPTION 201 21 This module provides the crude application layer functions for the ftp demo. 23 / 25 // // REQUIRED INCLUDES 27 // 29 #include // malloc () , free () #include // printf () 31 #include // memmove() 33 #include "bbcftp .h" 35 // // STRUCTURE DEFINITIONS 37 // 39 // NOTE: Normally the structure definition would be in the .c f i l e to make // the structure members inaccessible to outside functions except through 41 // public function calls . But for the real time code it has been decided // to make the structure members directly visible to the functions that 43 // manipulate them . 45 // // PRIVATE FUNCTION DEFINITIONS 47 // 49 // 51 // PUBLIC FUNCTION DEFINITIONS // 53 BBCFTP BBCFTP Del(BBCFTP p) 55 f if (p) 57 f p >config = CONFIG Del(p >config ) ; 59 p >source = SOURCE Del(p >source ) ; p >codec = CODEC Del(p >codec) ; 61 p >buffer = BUFFER Del(p >buffer ) ; p >modem = MODEM Del(p >modem) ; 63 p >sink = SINK Del(p >sink ) ; g 202 65 return NULL; g 67 BBCFTP BBCFTP New(char filename , DWORD errcode ) 69 f BBCFTP p; 71 DWORD err ; 73 p = NULL; err = 0; 75 errcode = 0; 77 p = (BBCFTP ) malloc(sizeof(BBCFTP)) ; if (!p) errcode j= 1 << 0; 79 if (! errcode ) 81 f p >config = CONFIG New(filename , &err ) ; 83 if ( err ) errcode j= 1 << 1; g 85 if (! errcode ) 87 f p >source = SOURCE New(p >config , &err ) ; 89 if ( err ) errcode j= 1 << 2; p >codec = CODEC New(p >config , &err ) ; 91 if ( err ) errcode j= 1 << 3; p >buffer = BUFFER New(p >config , &err ) ; 93 if ( err ) errcode j= 1 << 4; p >modem = MODEMNew(p >config , &err ) ; 95 if ( err ) errcode j= 1 << 5; p >sink = SINK New(p >config , &err ) ; 97 if ( err ) errcode j= 1 << 6; g 99 return p; 101 g 103 void BBCFTP ErrorCodes(DWORD err ) f 105 if ( err & ((DWORD) 1 << 0) ) printf ("BBC FTP System Constructor failed to allocatenn") ; 107 if ( err & ((DWORD) 1 << 1) ) printf ("CONFIG Constructor exited with errorsnn") ; 109 if ( err & ((DWORD) 1 << 2) ) 203 printf ("SOURCE Constructor exited with errorsnn") ; 111 if ( err & ((DWORD) 1 << 3) ) printf ("CODEC Constructor exited with errorsnn") ; 113 if ( err & ((DWORD) 1 << 4) ) printf ("BUFFER Constructor exited with errorsnn") ; 115 if ( err & ((DWORD) 1 << 5) ) printf ("MODEM Constructor exited with errorsnn") ; 117 if ( err & ((DWORD) 1 << 6) ) printf ("SINK Constructor exited with errorsnn") ; 119 g 121 void PrintMessage(BYTE base) f 123 int i ; int chunk size bytes ; 125 DWORD checksum ; 127 WORD seqnum , loadbits , id ; 129 checksum = GetMessageChecksum(base) ; seqnum = GetMessageSeq(base) ; 131 loadbits = GetMessageLoadBits(base) ; id = GetMessageID(base) ; 133 printf ("[%04lu ] " , (unsigned long) checksum) ; 135 printf ("[%04lu ] " , (unsigned long) seqnum) ; printf ("[%04lu ] " , (unsigned long) loadbits ) ; 137 printf ("[%04lu ] " , (unsigned long) id ) ; 139 chunk size bytes = loadbits /8; 141 printf ("[") ; for ( i = 0; i < chunk size bytes ; i++) 143 f putc( ( base + BBC FTP OFFSET PAYLOAD + i ) , stdout) ; 145 g printf ("]nn") ; 147 g 149 void SetMessageChecksum(BYTE base , DWORD v) 151 f memmove(base+BBC FTP OFFSET CHECKSUM, &v, BBC FTP BYTES CHECKSUM) ; 153 g 204 155 void SetMessageSeq(BYTE base , WORD v) f 157 memmove(base+BBC FTP OFFSET SEQNUM, &v, BBC FTP BYTES SEQNUM) ; g 159 void SetMessageLoadBits(BYTE base , WORD v) 161 f memmove(base+BBC FTP OFFSET LOADBITS, &v, BBC FTP BYTES LOADBITS) ; 163 g 165 void SetMessageID(BYTE base , WORD v) f 167 memmove(base+BBC FTP OFFSET ID, &v, BBC FTP BYTES ID) ; g 169 void SetMessagePayload(BYTE base , BYTE source , DWORD bytes , int offset ) 171 f memmove(base+BBC FTP OFFSET PAYLOAD+offset , source , bytes) ; 173 g 175 DWORD GetMessageChecksum(BYTE base) f 177 return ((DWORD )(base + BBC FTP OFFSET CHECKSUM)) ; g 179 WORD GetMessageSeq(BYTE base) 181 f return ((WORD )(base + BBC FTP OFFSET SEQNUM)) ; 183 g 185 WORD GetMessageLoadBits(BYTE base) f 187 return ((WORD )(base + BBC FTP OFFSET LOADBITS)) ; g 189 WORD GetMessageID(BYTE base) 191 f return ((WORD )(base + BBC FTP OFFSET ID)) ; 193 g 195 BYTE GetMessagePayload(BYTE base) f 197 return (BYTE )(base + BBC FTP OFFSET PAYLOAD) ; g 199 205 // A.3.3 bu er.h / 2 Data Buffer for the Real time BBC Codec/Modem 4 William L. Bahn Academy Center for Information Security 6 Department of Computer Science United States Air Force Academy 8 USAFA, CO 80840 10 FILE : . . . . . . . . . . . . buffer .h DATE CREATED: . . . . 01 SEP 07 12 DATE MODIFIED : . . . 01 SEP 07 14 REVISION HISTORY 16 18 DESCRIPTION 20 The data buffer stores packet data between the codec and the modem. 22 In the receiver , the buffer accepts packet data from the codec and 24 feeds that data to the modem. In the transmitter , it accepts data from the modem and feeds it to the codec . While the modem, by its nature , 26 generally produces and consumes data at a uniform rate , the codec can be quite erratic in its data rate . Therefore the buffer must be 28 sized sufficiently large to allow for the resulting ebb and flow . This is particularly important in the case of the receiver since , if 30 the buffer can ? t accommodate the data as the modem delivers it , data will be lost . This is not as critical with the transmitter , depending 32 on the nature of the data source and its buffering strategy , since it will normally only reduce the effective data rate as opposed to causing 34 dropped packets . 36 The data is stored in a circular buffer with the following variables : 38 buffer : Pointer to the block of memory where the buffer starts . read : Index of the f i rs t byte of the present packet . 40 write : Index of the next unused buffer location . margin : How many bytes are in buffer beyond the scope of the decoder . 206 42 unused : How many unused bytes are available in the buffer . 44 The buffer is seen by two functions , the one that is demodulating the data packet and the one that is decoding the resulting data . The 46 demodulating function writes to the buffer at a nominally constant rate dictated by the communications link . In this application , this is 48 simulated by reading the stored waveform data from a f i l e and querying the clock to determine how many bytes to add to the buffer each time 50 the function is called . The decoding function , on the other hand , always to decodes eight packets each time it is called provided sufficient data 52 is available . Specifically , it decodes the eight packets that start with the bits in the byte stored at the "read" pointer . Since it can ? t decode 54 packets that are not completely contained in the buffer , the decoding function fi r s t checks to see if " f i l l " is non negative . If it isn ?t , then 56 it returns immediately . At the other end of the spectrum , the demodulator may run out of unused memory to write to . If this happens , data is going 58 to be lost . It is cleaner to throw away old data instead of introducing a gap in present data , therefore the demodulator will push the "read" 60 pointer forward as it overwrites the beginning of the existing packet data . 62 / 64 #ifndef BUFFERdotH 66 #define BUFFERdotH 68 // // REQUIRED INCLUDES 70 // 72 #include "config .h" #include "dirtyd .h" 74 // 76 // STRUCTURE DECLARATIONS // 78 typedef struct BUFFER BUFFER; 80 // 82 // STRUCTURE DEFINITIONS // 84 // NOTE: Normally the structure definition would be in the .c f i l e to make 86 // the structure members inaccessible to outside functions except through 207 // public function calls . But for the real time code it has been decided 88 // to make the structure members directly visible to the functions that // manipulate them . 90 struct BUFFER 92 f size t size ; // Allocated size of buffer ( in bytes ) 94 size t minsize ; // Minimum acceptable buffer size ( in bytes ) BYTE buffer ; // Pointer to the actual buffer 96 DWORD read ; // Index of next position to be read . DWORD write ; // Index of next position to be written . 98 DWORD scope ; // The number of bytes recipient must . SDWORD margin ; // Number of bytes beyond scope of recipient 100 DWORD empty; // Number of bytes available for new data . DWORD ready ; // Number of bytes ready for modulation . 102 DWORD buffermask ; // The used bits in the buffer size DWORD overflows ; // Number of data pushes into read pointer . 104 g; 106 // // PUBLIC FUNCTION PROTOTYPES 108 // 110 BUFFER BUFFER Del(BUFFER p) ; BUFFER BUFFER New(CONFIG c , DWORD errcode ) ; 112 // 114 #endif A.3.4 bu er.c 1 / Data Buffer for the Real time BBC Codec/Modem 3 William L. Bahn 5 Academy Center for Information Security Department of Computer Science 7 United States Air Force Academy USAFA, CO 80840 9 FILE : . . . . . . . . . . . . buffer . c 11 DATE CREATED: . . . . 01 SEP 07 DATE MODIFIED : . . . 01 SEP 07 13 208 15 REVISION HISTORY 17 19 DESCRIPTION 21 The data buffer and its programmer interface is described in buffer .h. 23 / 25 // 27 // REQUIRED INCLUDES // 29 #include // malloc () , free () 31 #include // memset() 33 #include "buffer .h" 35 // // STRUCTURE DEFINITIONS 37 // 39 // NOTE: Normally the structure definition would be in the .c f i l e to make // the structure members inaccessible to outside functions except through 41 // public function calls . But for the real time code it has been decided // to make the structure members directly visible to the functions that 43 // manipulate them . 45 // // PRIMITIVE FUNCTION DEFINITIONS 47 // 49 // // PRIVATE FUNCTION DEFINITIONS 51 // 53 // // PUBLIC FUNCTION DEFINITIONS 55 // 57 BUFFER BUFFER Del(BUFFER p) f 59 if (p) 209 f 61 if (p >buffer ) f free (p >buffer ) ; p >buffer = NULL; g g 63 return NULL; g 65 BUFFER BUFFER New(CONFIG c , DWORD errcode ) 67 f BUFFER p; 69 DWORD err ; 71 p = NULL; err = 0; 73 if (! err ) 75 f p = (BUFFER ) malloc(sizeof(BUFFER)) ; 77 if (!p) err j= 1 << 1; 79 g 81 if (! err ) f 83 p >minsize = ( size t ) (c >bufferbytes per packet c >buffer packets ) ; p >size = 1; 85 while ((0 != p >size )&&(p >size < p >minsize )) p >size <<= 1; 87 if (0 == p >size ) err j= 1 << 2; 89 g 91 if (! err ) f 93 // Allocate buffer memory p >buffer = (BYTE ) malloc(p >size sizeof(BYTE)) ; 95 if (!p >buffer ) err j= 1 << 3; 97 // Initialize buffer state 99 // Common to TX and RX 101 p >buffermask = p >size 1; p >scope = c >bufferbytes per packet ; 103 p >read = 0; p >write = 0; 210 105 p >overflows = 0; 107 // TX and RX specific if (c >scheduler TX notRX) 109 f p >margin = p >size p >scope ; 111 p >ready = 0; p >empty = 0; // Not used 113 g else 115 f p >margin = ((SDWORD)p >scope) ; 117 p >ready = 0; // Not used p >empty = p >size ; 119 g g 121 // Clear entire buffer 123 if (! err ) memset(p >buffer , 0, p >size ) ; 125 if ( err ) 127 p = BUFFER Del(p) ; 129 if (c >diagnostics ) f 131 // Diagnostic Report printf (" nn") ; 133 printf ("PACKET BUFFERnn") ; printf (" Creation : . . . . . . . . . . . . . . . %snn" , (( err )? "FAILED":"SUCCEEDED")) ; 135 printf (" Location : . . . . . . . . . . . . . . . %pnn" , (void ) p) ; printf (" Minimum buffer size : . . . . %lu bytesnn" , (unsigned long) p >minsize ) ; 137 printf (" Buffer size : . . . . . . . . . . . . %lu bytesnn" , (unsigned long) p >size ) ; printf (" Buffer location : . . . . . . . . %pnn" , (void ) p >buffer ) ; 139 printf (" Packet size in buffer : . . %lu bytesnn" , (unsigned long) p >scope) ; printf (" read : . . . . . . . . . . . . . . . . . . . %lu bytesnn" , (unsigned long) p >read) ; 141 printf (" write : . . . . . . . . . . . . . . . . . . %lu bytesnn" , (unsigned long) p >write ) ; printf (" empty : . . . . . . . . . . . . . . . . . . %lu bytesnn" , (unsigned long) p >empty) ; 143 printf (" ready : . . . . . . . . . . . . . . . . . . %lu bytesnn" , (unsigned long) p >ready) ; printf (" margin : . . . . . . . . . . . . . . . . . %li bytesnn" , (long) p >margin) ; 145 printf (" overflows : . . . . . . . . . . . . . . %lu bytesnn" , (unsigned long) p >overflows ) ; printf (" nn") ; 147 g 149 errcode = err ; 211 return p; 151 g 153 // A.3.5 bytes.h 1 / ======================================================================= PROGRAMMER "BAHN, William" 3 TITLE "Integer Storage Size Type Definitions " CREATED 06 FEB 07 5 MODIFIED 06 FEB 07 FILENAME "bytes .h" 7 ======================================================================= GENERAL DESCRIPTION 9 This f i l e contains type definitions so that porting from one processor 11 to another is simpler . ======================================================================= 13 SIZE DEFINITIONS 15 The following definitions are used : 17 SIZE UNSIGNED SIGNED 8 bit BYTE SBYTE 19 16 bit WORD SWORD 32 bit DWORD SDWORD 21 64 bit QWORD SQWORD ( not available on most systems ) 23 ======================================================================= To Verify Sizes 25 Use the VerifySIZES () function passing the largest integer size , in 27 bits , that is of interest . 29 The function returns TRUE if conflicts are found . 31 If an argument of 0 is used , then the return value has a bit set for each type definition that didn ? t verify , starting with the shortest 33 length in the LSB. 35 Example you are interested only in integer sizes up to 32 bits . 37 VerifySIZES (32) or VerifySIZES(BITSinDWORD) ; 212 39 ======================================================================= / 41 #ifndef BYTESdotH 43 #define BYTESdotH 45 #define BITSinBYTE ( 8) #define BITSinWORD (16) 47 #define BITSinDWORD (32) #define BITSinQWORD (64) 49 / ======================================================================= 51 Normal definitions 53 This the only section that should need to be changed . 55 Determine which integer type is the correct number of bits and update the following l i s t . Do not worry about signed/unsigned . 57 It is not recommended that you actually use these definitions in your 59 code they are simply used in the following type definitions . ======================================================================= 61 / 63 #define NBYTE char #define NWORD short 65 #define NDWORD int #define NQWORD long 67 / ======================================================================= 69 UNSIGNED TYPE DEFINITIONS ======================================================================= 71 / 73 typedef unsigned NBYTE BYTE; typedef unsigned NWORD WORD; 75 typedef unsigned NDWORD DWORD; typedef unsigned NQWORD QWORD; 77 / ======================================================================= 79 SIGNED TYPE DEFINITIONS ======================================================================= 81 / 83 typedef signed NBYTE SBYTE; 213 typedef signed NWORD SWORD; 85 typedef signed NDWORD SDWORD; typedef signed NQWORD SQWORD; 87 / ======================================================================= 89 UTILITY FUNCTIONS ======================================================================= 91 / 93 unsigned int VerifySIZES(unsigned int maxlength) ; 95 #endif A.3.6 bytes.c / ======================================================================= 2 PROGRAMMER "BAHN, William" TITLE "Integer Storage Size Type Definitions " 4 CREATED 06 FEB 07 MODIFIED 06 FEB 07 6 FILENAME "bytes . c" ======================================================================= 8 GENERAL DESCRIPTION 10 NOTE: ANY AVAILABLE "USER GUIDE" IS IN THE ASSOCIATED HEADER FILE. 12 This f i l e contains type definitions so that porting from one processor to another is simpler . 14 ======================================================================= 16 / 18 #include "bytes .h" 20 int VerifyBYTE(void) f 22 return (8 sizeof(BYTE) != BITSinBYTE) ; g 24 int VerifyWORD(void) 26 f return (8 sizeof(WORD) != BITSinWORD) ; 28 g 30 int VerifyDWORD(void) 214 f 32 return (8 sizeof(DWORD) != BITSinDWORD) ; g 34 int VerifyQWORD(void) 36 f return (8 sizeof(QWORD) != BITSinQWORD) ; 38 g 40 unsigned int VerifySIZES(unsigned int maxlength) f 42 unsigned int flags ; unsigned int mask; 44 // Generate a flag vector with a 1 set anyplace that does not 46 // verify properly . Note that the bit position is equal to base 2 // log of the number of bytes in the integer type . 48 flags = 0; 50 flags = ( flags << 1) + VerifyQWORD() ; flags = ( flags << 1) + VerifyDWORD() ; 52 flags = ( flags << 1) + VerifyWORD() ; flags = ( flags << 1) + VerifyBYTE() ; 54 // Convert length from bits to smallest compatible number of bytes . 56 maxlength = (maxlength/8) + (( maxlength%8)?1:0) ; 58 // Generate a mask that is set only in those flag positions of interest . 60 if (maxlength) // report on sizes up to and including maxlength . 62 for (mask = 0; maxlength > 0; maxlength /= 2) f 64 mask = (mask << 1) + 1; if (( maxlength > 1)&&(maxlength%2)) 66 mask = (mask << 1) + 1; g 68 else // report on all defined sizes mask = ~0; 70 return ( flags & mask) ; 72 g A.3.7 codec.h 215 / 2 CODEC for the Real time BBC Codec/Modem 4 William L. Bahn Academy Center for Information Security 6 Department of Computer Science United States Air Force Academy 8 USAFA, CO 80840 10 FILE : . . . . . . . . . . . . codec .h DATE CREATED: . . . . 06 SEP 07 12 DATE MODIFIED : . . . 06 SEP 07 14 REVISION HISTORY 16 18 DESCRIPTION 20 The codec encodes and decodes messages to/from BBC encoded packets . 22 24 / 26 #ifndef CODECdotH #define CODECdotH 28 // 30 // REQUIRED INCLUDES // 32 #include "config .h" 34 #include "source .h" #include "buffer .h" 36 #include "sink .h" #include "dirtyd .h" 38 #include "sha1 .h" 40 typedef struct thread data thread data ; 42 44 // // STRUCTURE DECLARATIONS 216 46 // 48 typedef struct CODEC CODEC; 50 // // STRUCTURE DEFINITIONS 52 // 54 // NOTE: Normally the structure definition would be in the .c f i l e to make // the structure members inaccessible to outside functions except through 56 // public function calls . But for the real time code it has been decided // to make the structure members directly visible to the functions that 58 // manipulate them . 60 struct CODEC f 62 // State information SHA1Context state ; // Pointer to single SHA1 structure 64 SHA1Context digest ; // Pointer to single SHA1 structure 66 // Decode buffer BYTE msg; // Array containing the message bit contents (1 bit per byte ) 68 BYTE checkbit ; // Array indicating whether each bit is a message or check bit SHA1Context hashstate ; // Array of SHA1 structures 70 g; 72 struct thread data f 74 CONFIG config ; BUFFER buffer ; 76 CODEC codec ; SINK sink ; 78 int running ; int number; 80 g; 82 // // PUBLIC FUNCTION PROTOTYPES 84 // 86 CODEC CODEC Del(CODEC p) ; CODEC CODEC New(CONFIG c , DWORD errcode ) ; 88 void Encode(CONFIG c , SOURCE source , CODEC codec , BUFFER buffer ) ; void Decode(CONFIG c , BUFFER buf , CODEC codec , SINK sink ) ; 90 217 / DECODER 92 The decoder decodes all eight of the packets that start with each of the 94 eight bits in the byte located at the present "read" location of the buffer . 96 The value of the variable " originbit " determines which of the eight offsets from the beginning of the byte the present packet starts at . The variable 98 " location " refers to the location of the bit in question relative to the beginning of the packet . Therefore , relative to the beginning of the byte 100 where the packet starts , the location is simply " origin + location ". This combined location must then be turned into an index and and offset . The 102 "index" refers to which byte within the buffer contains the bit of interest while the " offset " identifies the bit within that byte . The "index" value 104 must further account for the fact that the fi r s t byte in the packet is located at the "read" point within the index and that the buffer is circular . 106 The " offset " value must be used to mask the byte being examined so that only the bit of interest is considered . For speed purposes , this mask is provided 108 by a lookup table "bitmask ". 110 Taking all of this into account , the following steps will check if a particular packet bit is set : 112 index = fread + floor [( location + originbit ) /8]g mod bufferlength 114 offset = ( location + originbit ) mod 8 status = buffer [ index ] & bitmask [ offset ] 116 Since the buffer length is exactly 2^n long , the residue of the index can 118 be taken by simply retaining only the lower n bits . Similarly , the residue of the offset modulo 8 can be taken by only retaining the lower 3 bits . Both 120 of these can be done by performing a bitwise AND with an appropriate mask. Finally , the division of the effective location within the packet can be 122 performed by right shifting the sum by 3 bits . Hence we have the following equations : 124 index = ( read + (( location + originbit ) >> 3)) & buffermask ; 126 offset = ( location + originbit ) & 0x00000007 ; status = buffer [ index ] & bitmask [ offset ] 128 The most challenging part of the decoding algorithm is the backtracking that 130 must take place when the present partial message is finished , either because it was found to be a dead end or because it resulted in an actual message . 132 The basic task is to traverse the decoding tree backwards until the last partial message bit that was a zero is found . Then that bit is changed to a one 134 and decoding moves forward again . Two special cases have to be taken into account . First , if there are no message bits that are zero , then the decoding 218 136 of that packet is finished . Second , checksum bits are always zero and the decoder must skip over them without turning them to ones . 138 index 0123456789.... check 1001001001.... 140 msg 0010110110.... 142 / 144 // #endif A.3.8 codec.c 1 / CODEC for the Real time BBC Codec/Modem 3 William L. Bahn 5 Academy Center for Information Security Department of Computer Science 7 United States Air Force Academy USAFA, CO 80840 9 FILE : . . . . . . . . . . . . codec . c 11 DATE CREATED: . . . . 06 SEP 07 DATE MODIFIED : . . . 06 SEP 07 13 15 REVISION HISTORY 17 19 DESCRIPTION 21 The codec and its public interface are described in codec .h 23 / 25 // 27 // REQUIRED INCLUDES // 29 #include // free () , malloc () 31 #include "codec .h" 219 33 #include "sha1 .h" 35 #define DECODE LIMIT 0.05 (double)CLOCKS PER SEC 37 // // STRUCTURE DEFINITIONS 39 // 41 // NOTE: Normally the structure definition would be in the .c f i l e to make // the structure members inaccessible to outside functions except through 43 // public function calls . But for the real time code it has been decided // to make the structure members directly visible to the functions that 45 // manipulate them . 47 // // PRIVATE FUNCTION DEFINITIONS 49 // 51 #define SHA1 HASH DWORDS (5) 53 void ExportMessage(CONFIG c , CODEC codec , SINK sink ) f 55 DWORD i ; DWORD bit ; 57 DWORD index , offset ; 59 BYTE message ; 61 // Create pointer to next element in sink memory message = sink >v + (sink >samples sink >sample size bytes ) ; 63 // Discard leading random bits 65 for ( bit = 0, i = 0; i < c >codec random bits ; i++, bit++) f 67 while (codec >checkbit [ bit ]) bit++; 69 g 71 // Extract message bits and pack into byte string for ( i = 0; i < c >codec message bits ; i++, bit++) 73 f while (codec >checkbit [ bit ]) 75 bit++; index = i >> 3; 77 offset = i & 0x00000007 ; 220 message [ index ] &= ~c >bitmask[7 offset ]; 79 if (codec >msg[ bit ]) message [ index ] j= c >bitmask[7 offset ]; 81 g 83 // Zero pad remainder of last byte if necessary while (7 != offset ) 85 f i++; 87 offset = i & 0x00000007 ; message [ index ] &= ~c >bitmask[7 offset ]; 89 g 91 // NUL terminate byte string index++; 93 message [ index ] = ?n0 ? ; // printf ("ntnt%snn",message) ; 95 // Advance sink memory pointer sink >samples++; 97 g 99 // // PUBLIC FUNCTION DEFINITIONS 101 // 103 CODEC CODEC Del(CODEC p) f 105 if (p) f 107 if (p >state ) f free (p >state ) ; p >state = NULL; g if (p >digest ) f free (p >digest ) ; p >digest = NULL; g 109 if (p >hashstate ) f free (p >hashstate ) ; p >hashstate = NULL; g if (p >msg) f free (p >msg) ; p >msg = NULL; g 111 if (p >checkbit ) f free (p >checkbit ) ; p >checkbit = NULL; g g 113 return NULL; g 115 CODEC CODEC New(CONFIG c , DWORD errcode ) 117 f CODEC p; 119 DWORD err ; DWORD check ; 121 DWORD i , run ; err = 0; 221 123 p = (CODEC ) malloc(sizeof(CODEC)) ; 125 if (!p) err = 1 << 0; 127 if (! err ) 129 f // State information 131 p >state = (SHA1Context ) malloc(sizeof(SHA1Context)) ; p >digest = (SHA1Context ) malloc(sizeof(SHA1Context)) ; 133 // Decode Buffer 135 p >msg = (BYTE ) malloc(c >padded message bits ) ; p >checkbit = (BYTE ) malloc(c >padded message bits ) ; 137 p >hashstate = (SHA1Context ) malloc(c >padded message bits sizeof(SHA1Context)) ; 139 // Verify successful memory allocation if (!(p >state )) err j= 1 << 1; 141 if (!(p >digest )) err j= 1 << 2; if (!(p >msg)) err j= 1 << 3; 143 if (!(p >checkbit )) err j= 1 << 4; if (!(p >hashstate )) err j= 1 << 5; 145 g 147 if (! err ) f 149 // Initialize checkbit markers for (check = TRUE, run = 0, i = 0; i < (c >padded message bits c >codec stop bits ) ; i++) 151 f switch (check) 153 f case TRUE: 155 if (run >= c >codec clamp bits ) f 157 check = FALSE; run = 0; 159 g break; 161 case FALSE: if (run >= c >codec fragment bits ) 163 f check = TRUE; 165 run = 0; g 167 break; 222 g 169 p >checkbit [ i ] = check ; run++; 171 g 173 for ( i = 0; i < c >codec stop bits ; i++) p >checkbit [c >padded message bits c >codec stop bits + i ] = TRUE; 175 g 177 if (c >diagnostics ) 179 f // Diagnostic Report 181 printf (" nn") ; printf ("CODECnn") ; 183 printf (" Creation : . . . . . . . . . . . . . . . %snn" , (( err )? "FAILED":"SUCCEEDED")) ; printf (" Location : . . . . . . . . . . . . . . . %pnn" , (void ) p) ; 185 printf (" Message bits : . . . . . . . . . . . %linn" , (unsigned long) c >codec message bits ) ; printf (" Random bits : . . . . . . . . . . . . %linn" , (unsigned long) c >codec random bits ) ; 187 printf (" Clamp bits : . . . . . . . . . . . . . %linn" , (unsigned long) c >codec clamp bits ) ; printf (" Fragment bits : . . . . . . . . . . %linn" , (unsigned long) c >codec fragment bits ) ; 189 printf (" Stop bits : . . . . . . . . . . . . . . %linn" , (unsigned long) c >codec stop bits ) ; printf (" Padded message length : . . %linn" , (unsigned long) c >padded message bits ) ; 191 printf (" Packet expansion : . . . . . . . %linn" , (unsigned long) c >codec expansion ) ; printf (" Packet load : . . . . . . . . . . . . %li messagesnn" , (unsigned long) c >codec packet load ) ; 193 printf (" Decode limit : . . . . . . . . . . . %li messagesnn" , (unsigned long) c >codec decode limit ) ; printf (" Message buffer at : . . . . . . %pnn" , p >msg) ; 195 printf (" Checksum buffer at : . . . . . %pnn" , p >checkbit ) ; printf (" Hash buffer at : . . . . . . . . . %pnn" , p >hashstate ) ; 197 printf (" State buffer at : . . . . . . . . %pnn" , p >state ) ; printf (" Digest buffer at : . . . . . . . %pnn" , p >digest ) ; 199 printf (" nn") ; g 201 if ( err ) 203 p = CODEC Del(p) ; 205 errcode = err ; return p; 207 g 209 / DECODER 211 The decoder decodes all eight of the packets that start with each of the eight bits in the byte located at the present "read" location of the buffer . 223 213 The value of the variable " originbit " determines which of the eight offsets 215 from the beginning of the byte the present packet starts at . The variable " location " refers to the location of the bit in question relative to the 217 beginning of the packet . Therefore , relative to the beginning of the byte where the packet starts , the location is simply " origin + location ". This 219 combined location must then be turned into an index and and offset . The "index" refers to which byte within the buffer contains the bit of interest 221 while the " offset " identifies the bit within that byte . The "index" value must further account for the fact that the fi r s t byte in the packet is 223 located at the "read" point within the index and that the buffer is circular . The " offset " value must be used to mask the byte being examined so that only 225 the bit of interest is considered . For speed purposes , this mask is provided by a lookup table "bitmask ". 227 Taking all of this into account , the following steps will check if a 229 particular packet bit is set : 231 index = fread + floor [( location + originbit ) /8]g mod bufferlength offset = ( location + originbit ) mod 8 233 status = buffer [ index ] & bitmask [ offset ] 235 Since the buffer length is exactly 2^n long , the residue of the index can be taken by simply retaining only the lower n bits . Similarly , the residue 237 of the offset modulo 8 can be taken by only retaining the lower 3 bits . Both of these can be done by performing a bitwise AND with an appropriate mask. 239 Finally , the division of the effective location within the packet can be performed by right shifting the sum by 3 bits . Hence we have the following 241 equations : 243 index = ( read + (( location + originbit ) >> 3)) & buffermask ; offset = ( location + originbit ) & 0x00000007 ; 245 status = buffer [ index ] & bitmask [ offset ] 247 The most challenging part of the decoding algorithm is the backtracking that must take place when the present partial message is finished , either because 249 it was found to be a dead end or because it resulted in an actual message . The basic task is to traverse the decoding tree backwards until the last 251 partial message bit that was a zero is found . Then that bit is changed to a one and decoding moves forward again . Two special cases have to be taken into 253 account . First , if there are no message bits that are zero , then the decoding of that packet is finished . Second , checksum bits are always zero and the 255 decoder must skip over them without turning them to ones . index 0123456789.... 257 check 1001001001.... 224 msg 0010110110.... 259 / 261 // 263 / 265 The encoding function can be implemented in a more compact , efficient way. The method used here is intended to mirror the decode operation 267 as closely as possible . This is reasonable because the encoding operation requires constant time regardless of message and is therefore 269 well constrained . 271 / 273 void Encode(CONFIG c , SOURCE source , CODEC codec , BUFFER buffer ) f 275 DWORD msg bit , pmsg bit , r , i , index , offset ; unsigned int location ; 277 int bit value ; BYTE msg; 279 DWORD message stop ; clock t ticks ; 281 DWORD marks; 283 ticks = clock () ; 285 marks = 0; message stop = source >sample + c >codec packet load ; 287 if (message stop > source >samples) message stop = source >samples ; 289 // Place bookend marks 291 location = 0; index = ( buffer >write + ( location >> 3)) & buffer >buffermask ; 293 offset = location & 0x00000007 ; if ( buffer >buffer [ index ] & c >bitmask [ offset ]) 295 marks ; buffer >buffer [ index ] j= c >bitmask [ offset ]; 297 marks++; 299 location = c >last packet bit ; index = ( buffer >write + ( location >> 3)) & buffer >buffermask ; 301 offset = location & 0x00000007 ; if ( buffer >buffer [ index ] & c >bitmask [ offset ]) 225 303 marks ; buffer >buffer [ index ] j= c >bitmask [ offset ]; 305 marks++; 307 while (source >sample < message stop) f 309 if (c >diagnostics ) printf ("Encoding message #%lunn" , source >sample) ; 311 // Compute pointer to beginning of present message in source buffer msg = (BYTE ) source >v + source >sample source >sample size bytes ; 313 // Initialize Hash Function state to the Initial Vector 315 SHA1Reset(codec >state ) ; 317 // Load message into the codec ?s message buffer for (pmsg bit = 0, r = 0, msg bit = 0 ; pmsg bit < c >padded message bits ; pmsg bit++) 319 f if (codec >checkbit [ pmsg bit ]) 321 bit value = 0; else 323 f if (r < c >codec random bits ) 325 f bit value = rand() < (RANDMAX >> 1) ; 327 r++; g 329 else f 331 index = msg bit >> 3; offset = msg bit & 0x00000007 ; 333 bit value = (msg[ index ] & c >bitmask[7 offset ]) ? 1 : 0; msg bit++; 335 g g 337 SHA1Input(codec >state , c >bitptr + bit value , 1) ; 339 // Compute hash result for present prefix (codec >digest ) = (codec >state ) ; 341 SHA1Result(codec >digest ) ; 343 // Generate mark location for present prefix location = 0; 345 for ( i = 0; i < SHA1 HASH DWORDS; i++) location += (( codec >digest ) >Message Digest [ i ])<packet bits ; 226 349 // Place mark for present prefix index = ( buffer >write + ( location >> 3)) & buffer >buffermask ; 351 offset = location & 0x00000007 ; if ( buffer >buffer [ index ] & c >bitmask [ offset ]) 353 marks ; buffer >buffer [ index ] j= c >bitmask [ offset ]; 355 marks++; g 357 source >sample++; g 359 if (source >sample >= source >samples) 361 f // Last packet has been encoded . Advance buffer past last packet . 363 source >streaming = FALSE; c >buffer advance = c >bufferbytes per packet ; 365 g 367 // Advance buffer write pointer to next packet write location . buffer >write = ( buffer >write + c >buffer advance ) & buffer >buffermask ; 369 buffer >margin = c >buffer advance ; buffer >ready += c >buffer advance ; 371 c >dec ticks += clock () ticks ; 373 g 375 void Decode(CONFIG c , BUFFER buf , CODEC codec , SINK sink ) f 377 379 SDWORD i , bit ; DWORD location , index , offset , originbit ; 381 clock t ticks ; DWORD limit ; 383 ticks = clock () ; // if (c >diagnostics ) 385 // printf (" Begining new Decode buf >read=[%i ]nn", buf >read ) ; // Process all 8 packets that begin within the byte at the front of the buffer 387 for ( originbit = 0; originbit < 8; originbit++ / && ( clock () ticks ) < DECODE LIMIT /) f 389 if (( sink >sample limit sink >samples) > c >codec decode limit ) limit = (sink >sample limit sink >samples) ; 391 else limit = c >codec decode limit ; 227 393 // Check for bookend marks 395 index = (buf >read + ( originbit >> 3)) & buf >buffermask ; offset = ( originbit ) & 0x00000007 ; 397 if ( !( buf >buffer [ index ] & c >bitmask [ offset ]) ) break; 399 index = (buf >read + (( originbit + c >last packet bit ) >> 3)) & buf >buffermask ; 401 offset = ( originbit + c >last packet bit ) & 0x00000007 ; if ( !( buf >buffer [ index ] & c >bitmask [ offset ]) ) 403 break; 405 // Initialize Hash Function state to the Initial Vector SHA1Reset(codec >state ) ; 407 bit = 0; codec >msg[ bit ] = 0; 409 // printf (" index=[%i ] offset=[%i ]nn", index , offset ) ; while (TRUE) // Loop will terminate with a "break" call 411 f / if (( clock () ticks ) > DECODE LIMIT) 413 break ; / // Update the hash state for the new message bit 415 SHA1Input(codec >state , c >bitptr + codec >msg[ bit ] , 1) ; 417 // Compute the packet bit location corresponding to the hash (codec >digest ) = (codec >state ) ; 419 SHA1Result(codec >digest ) ; location = 0; 421 for ( i = 0; i < SHA1 HASH DWORDS; i++) location += (( codec >digest ) >Message Digest [ i ])<packet bits ; 425 // Check for mark at calculated location index = (buf >read + (( originbit + location ) >> 3)) & buf >buffermask ; 427 offset = ( originbit + location ) & 0x00000007 ; // printf ("ntindex=[%i ] offset=[%i ] location=[%i ] (buf >buffer=[%i ] & c >bitmask=[%i ])=[%i ]nn ", index , offset , location , buf >buffer [ index ] , c >bitmask [ offset ] , 429 //(buf >buffer [ index ] & c >bitmask [ offset ]) ) ; if (buf >buffer [ index ] & c >bitmask [ offset ]) 431 f // printf ("ntntEnternn") ; 433 // Update hash state for present partial message codec >hashstate [ bit ] = (codec >state ) ; 435 bit++; // IF a complete message hasn ? t been decoded yet 228 437 if ((DWORD) bit < c >padded message bits ) f 439 // Start with 0 for next bit in partial message codec >msg[ bit ] = 0; 441 // printf ("ntntContinuenn") ; continue; 443 g // ELSE a complete message has been found 445 // printf ("ntntComplete message foundnn") ; c >message count++; 447 ExportMessage(c , codec , sink ) ; bit ; 449 limit ; if (0 == limit )f 451 // printf ("ntntlimit==0 breaknn") ; break; 453 g g 455 // Backtrack to last message bit that is a zero 457 while ( ( bit >= 0) && (codec >checkbit [ bit ] jj codec >msg[ bit ]) ) bit ; 459 // If no bits are zero , then decoding is finished 461 if ( bit < 0) break; 463 // Change last zero bit to a one 465 codec >msg[ bit ] = 1; 467 // Reset hash state if (0 == bit ) // to initial vector 469 SHA1Reset(codec >state ) ; else // to vector of previous partial message 471 (codec >state ) = codec >hashstate [ bit 1]; g 473 g buf >read = (buf >read + 1) & buf >buffermask ; 475 buf >empty++; buf >margin ; 477 // if (c >diagnostics ) // printf ("ntDecode time : %0.05 fnn", (( clock () ticks )/( double )CLOCKS PER SEC)) ; 479 c >dec ticks += clock () ticks ;; g 481 229 // A.3.9 con g.h / 2 Configuration Module for the Real time BBC Codec/Modem 4 William L. Bahn Academy Center for Information Security 6 Department of Computer Science United States Air Force Academy 8 USAFA, CO 80840 10 FILE : . . . . . . . . . . . . config .h DATE CREATED: . . . . 03 SEP 07 12 DATE MODIFIED : . . . 08 SEP 07 14 REVISION HISTORY 16 18 DESCRIPTION 20 This module imports and manages the configuration information for the 22 modem and the codec . 24 / 26 #ifndef CONFIGdotH #define CONFIGdotH 28 // 30 // REQUIRED INCLUDES // 32 #include