Medium Access Control Protocol Design forIn-Vehicle Power Line CommunicationbyAmir Kenarsari AnhariB.Sc., Sharif University of Technology, Iran, 2011A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)October 2013c? Amir Kenarsari Anhari, 2013AbstractNowadays, the number of electronic devices in vehicles grows at an exponential rate.For the purpose of communication between these components, several standardizedcommunication protocols such as controller area network (CAN), local interconnectnetwork (LIN), and FlexRay have been developed and are used in vehicles. However,the use of additional wires for data communication still results in a significant in-crease in the complexity, volume, weight, and cost of wiring harness. Vehicular powerline communication (V-PLC) is an interesting alternative that offers numerous ad-vantages. This technology reuses the existing direct current (DC) power network invehicles as the physical medium for data transmission and allows eliminating some ofthe wiring harnesses devoted to convey data signals. Hence, This technology can po-tentially reduce the vehicle cost, weight, and fuel consumption. However, to providereliable communication over power lines, several challenges need to be addressed.These include impulsive noise produced by electrical devices connected to the busand frequency-selective behavior of the power line channels introduced by impedancemismatches in the wiring harness.In this thesis, we study research challenges for the medium access control (MAC)protocol design of V-PLC networks. We propose MAC protocols for such systems,which provide fast collision resolution, and perform performance evaluations on theseprotocols in terms of collision probability, system throughput, and packet delay. Ourresults show that these protocols outperform the previously proposed protocol, con-iiAbstracttention detection and resolution (CDR) [1] in all scenarios.We then investigate the effect of carrier sensing errors on the performance ofthe proposed MAC protocols. We start with addressing the problem of detection ofunknown signals in impulsive noise by using a robust detector, which first removesthe impulses from the signal and then performs linear signal detection on the cleanedsamples. We obtain the network throughput and delay of the proposed protocols asa function of carrier sensing errors. We then suggest a framework for the optimaljoint design of the physical layer signal detector and MAC layer protocol.iiiPrefaceHereby, I declare that I am the first author of this thesis. Chapters 3-5 are based onwork that has been published or submitted for publication. The related publicationswere co-authored by Professor Victor C.M. Leung. The work in Chapter 4 was donein collaboration with Professor Lutz Lampe.For all publications, I conducted the paper survey on related topics, performed theanalysis, and carried out the simulations of the considered communication systems.The papers were originally prepared by me, and further revised by all the co-authors.The following publications are accomplished through this research.Conference Papers? Amir Kenarsari-Anhari, Victor C.M. Leung, and Lutz Lampe, ?A DistributedMAC Protocol for In-Vehicle Power Line Communication under Imperfect Car-rier Sensing,? in Proc of IEEE International Symposium on Personal, Indoorand Mobile Radio Communications (PIMRC), London, UK, September 2013.? Amir Kenarsari-Anhari and Victor C.M. Leung, ?Multi-Carrier Medium AccessControl for In-Vehicle Power Line Communication with Imperfect Sensing,? inProc of IEEE Vehicular Technology Conference (VTC Spring), Dresden, Ger-many, June 2013.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivations and Objectives . . . . . . . . . . . . . . . . . . . . . . . 21.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 32 Background and Related Work . . . . . . . . . . . . . . . . . . . . . 52.1 Vehicular Power Line Communication . . . . . . . . . . . . . . . . . 52.2 Controller Area Network . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Related Work on Random Access MAC Protocols for V-PLC . . . . 72.4 Basics of Carrier Sensing and Impulse Filtering . . . . . . . . . . . . 9vTable of Contents3 Frequency-Domain Contention Resolution Algorithm with Imper-fect Carrier Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.1 Motivations and Assumptions . . . . . . . . . . . . . . . . . . . . . 143.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.2.1 Sensing Model . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2.2 Probability of Successful Transmission . . . . . . . . . . . . . 183.2.3 Time Utilization . . . . . . . . . . . . . . . . . . . . . . . . . 203.3 Optimal Selection Distribution . . . . . . . . . . . . . . . . . . . . . 203.3.1 Analysis of Optimal Scheme with Finite n . . . . . . . . . . 213.3.2 Asymptotic Analysis of Optimal Scheme as n ? ? . . . . . . 223.4 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.4.1 Performance under Different SNRs . . . . . . . . . . . . . . . 253.4.2 Performance under Different Number of Nodes . . . . . . . . 263.4.3 Time Utilization . . . . . . . . . . . . . . . . . . . . . . . . . 273.4.4 Comparison with CDR Protocol . . . . . . . . . . . . . . . . 283.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 Time-Domain Contention Resolution Algorithm with Imperfect Car-rier Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.1 Motivations and Assumptions . . . . . . . . . . . . . . . . . . . . . . 304.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2.1 MAC Protocol Operation . . . . . . . . . . . . . . . . . . . . 324.3 MAC Protocol Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 344.3.1 Probability Distribution of Survivors . . . . . . . . . . . . . . 344.3.2 Throughput and Delay Analysis . . . . . . . . . . . . . . . . 404.4 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42viTable of Contents4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455 Multi-channel Contention Resolution Algorithm with Imperfect Car-rier Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.2 Performance Analysis under Perfect Sensing . . . . . . . . . . . . . . 485.3 Performance Analysis under the Presence of Sensing Errors . . . . . 535.4 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . 676.1 Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . . 676.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . 68Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70AppendicesA Probability Generating Functions . . . . . . . . . . . . . . . . . . . . 73viiList of Tables3.1 Optimal Parameters in Example 1 . . . . . . . . . . . . . . . . . . . . 234.1 Optimal parameters for (nc=16, ns=6, ?=0.6) . . . . . . . . . . . . . 39viiiList of Figures2.1 Block diagram of a robust signal detector. . . . . . . . . . . . . . . . 122.2 Samples of the received signal before and after preprocessing. . . . . . 132.3 ECDF of the real, preprocessed, and impulse-free received signal. . . 133.1 A view of the frame structure. . . . . . . . . . . . . . . . . . . . . . . 163.2 Probability of successful transmission versus SNR for different numberof subcarriers at Ns = 10. . . . . . . . . . . . . . . . . . . . . . . . . 253.3 Probability of successful transmission versus SNR for different numberof samples at Nc = 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.4 Probability of successful transmission as a function of number of nodesfor different SNRs, Nc = 8 and Ns = 10. . . . . . . . . . . . . . . . . 273.5 ?1 versus Ns and Nc, SNR = -5dB and n = 16. . . . . . . . . . . . . . 283.6 Probability of successful transmission of the proposed and CDR pro-tocol as a function of number of nodes. . . . . . . . . . . . . . . . . . 294.1 Illustration of the protocol operation. . . . . . . . . . . . . . . . . . . 334.2 ps as a function of ?, when the optimal probabilities are obtained for?=0.6 (perfect sensing). . . . . . . . . . . . . . . . . . . . . . . . . . 404.3 Probability of success for selective tournaments and CDR versus nc fordifferent number of slots (perfect sensing). . . . . . . . . . . . . . . . 414.4 ? versus pf for different SNR values, u = 5. . . . . . . . . . . . . . . . 43ixList of Figures4.5 Optimum false alarm error versus SNR for different values of u. . . . 444.6 Maximum throughput as a function of SNR for different values of u. . 444.7 Network delay versus SNR for different values of u. . . . . . . . . . . 455.1 A view of a single transmission cycle. . . . . . . . . . . . . . . . . . . 485.2 Channel selection probabilities when M = 10 channels are availablefor multiple choices of ?. . . . . . . . . . . . . . . . . . . . . . . . . . 515.3 Success probability versus number of contending nodes for differentvalues of ?, N = 50, k = 6, M = 2. . . . . . . . . . . . . . . . . . . . 585.4 Average success probability versus number of channels for differentnumber of time slots (k), N = 50, ? = 0.6. . . . . . . . . . . . . . . . 595.5 ?1 versus number of channels for different number of time slots (k),N = 50, ? = 0.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.6 The average success probability versus total number of nodes con-nected to the harness (N), ? = 0.6. . . . . . . . . . . . . . . . . . . . 605.7 Probability mass function of the number of transmission cycles re-quired to transmit the first packet when there are 25 contenders,N = 50, ? = 0.6, k = 4, M = 3. . . . . . . . . . . . . . . . . . . . . . 615.8 Probability mass function of the number of transmission cycles re-quired to transmit all packets when there are 25 contenders, N = 50,? = 0.6, k = 4, M = 3. . . . . . . . . . . . . . . . . . . . . . . . . . . 615.9 Probability mass function of the number of transmission cycles re-quired to transmit the first packet when there are 5 contenders, N =50, ? = 0.6, k = 4, M = 3. . . . . . . . . . . . . . . . . . . . . . . . . 62xList of Figures5.10 Probability mass function of the number of transmission cycles re-quired to transmit all packets when there are 5 contenders, N = 50,? = 0.6, k = 4, M = 3. . . . . . . . . . . . . . . . . . . . . . . . . . . 625.11 Success probability of the proposed protocol and CDR versus numberof contending nodes, M = 3, N = 50, ? = 0.6. . . . . . . . . . . . . . 635.12 The average success probability versus false alarm errors, N = 50,? = 0.6, k = 6, M = 2, u = 10. . . . . . . . . . . . . . . . . . . . . . . 645.13 Success probability versus number of contending nodes for multiplevalues of r, where good channel is indexed 1, k = 6, M = 2, N =50, ? = 0.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645.14 Success probability versus number of contending nodes for multiplevalues of r, where bad channel is indexed 1, k = 6, M = 2, N =50, ? = 0.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65xiList of AcronymsACK AcknowledgmentADC Analog-to-Digital ConverterAWGN Additive White Gaussian NoiseBPF Band-pass FilterCAN Controller Area NetworkCDF Cumulative Distribution FunctionCDMA Code Division Multiple AccessCDR Contention Detection and ResolutionCRC Cyclic Redundancy CheckCSMA Carrier Sense Multiple AccessCSMA/CA Carrier Sense Multiple Access with Collision AvoidanceCSMA/CD Carrier Sense Multiple Access with Collision DetectionDC Direct CurrentECDF Empirical Cumulative Distribution FunctionECU Electronic Control UnitED Energy DetectionFDMA Frequency Division Multiple AccessIEEE Institute of Electrical and Electronics EngineersI.i.d. Independent and Identically DistributedLIN Local Interconnect NetworkxiiList of AcronymsMAC Medium Access ControlPdf Probability Density FunctionPHY Physical layerPLC Power Line CommunicationQoS Quality of ServiceROC Receiver Operating CharacteristicSNR Signal-to-Noise RatioTDMA Time Division Multiple AccessUART Universal Asynchronous Receiver/TransmitterV-PLC Vehicular Power Line CommunicationxiiiAcknowledgmentsI would like to express my greatest gratitude to my supervisor, Professor Victor C.M.Leung, for his guidance and valuable advice throughout my graduate study.I would also like to thank Professor Lutz Lampe for his helpful comments andassistance during the course of this work.This work was supported by a grant from AUTO21 under the Canadian Networkof Centres of Excellence Program.xivChapter 1IntroductionThe automotive industry introduces more and more electronic devices to ensure safetyand comfort of occupants. There are several electronic control units (ECUs) to controlthe crucial on-board subsystems, such as ignition and braking systems. For thepurpose of communication between ECUs, several standardized wire protocols suchas CAN, LIN, and FlexRay were introduced and used in vehicles. However, each ofthese protocols requires its own dedicated communication lines which results in theincreasingly complex network architectures, higher volume, weight and cost of thewiring harnesses [2]. V-PLC offers the advantage of using the existing power cablesin vehicles for data transmissions, and therefore can significantly reduce the vehiclecost, weight, and fuel consumption.The use of power line communication inside vehicles has attracted a lot of at-tentions from industry in a past few years. For instance, Yamar Electronics. Ltd.introduced the DC-BUS technology which enables the transfer of both data andpower over a single cable [3]. They also designed several chips for the various ap-plications supporting LIN, CAN, and universal asynchronous receiver/transmitter(UART) protocols to communicate over DC-BUS.In order to fully exploit PLC technology in vehicles, MAC layer must be properlydesigned to provide reliable data transmission. We focus on random access MACprotocols which arbitrate the packet transmissions over power lines. The goal of theMAC protocol is to allow users to share a channel in an efficient manner by providing1Chapter 1. Introductiona low collision rate, a high throughput, and a low delay average.However, there are several challenges for deploying PLC system in vehicles thatneed to be considered while designing a MAC protocol for such a system. For instance,the measurements reported in [2, 4?6] confirm the frequency-selective behavior ofV-PLC transmission channels. Another difficulty encountered in designing a PLCsystem for vehicles is the presence of non-stationary impulsive noise caused by variouselectrical devices connected to the V-PLC network [7]. Hence, in this thesis, we aimto investigate the effect of the carrier sensing errors on the performance of the MAClayer.1.1 Motivations and ObjectivesThe related work on the design of a random access protocol for V-PLC networkis limited. The authors in [1] proposed a random access protocol which resolvesthe contention by randomly switching between carrier sense and carrier transmissionmodes in each slot. They have calculated the collision probability by mathematicalanalysis with the assumption of perfect carrier sensing. On the contrary, as we men-tioned before, measurements of V-PLC transmission channels indicate the presenceof non-stationary impulsive noise. Hence, our work in this thesis, considers imperfectcarrier sensing and also attempts to improve the MAC layer efficiency by includingthe physical layer parameters into the MAC layer design process. Our results alsoshow that the proposed MAC protocols in this thesis outperform the MAC protocolin [1] significantly. We would like to remark that, to the best of our knowledge, thework in [1] is the only existing random access MAC protocol designed for V-PLCsystems.2Chapter 1. Introduction1.2 ContributionsWe can summarize our contributions in this thesis as follows:? We propose MAC protocols to provide random access over power line network.The first protocol uses multiple channels to arbitrate the packet transmission.The second protocol minimizes the contention between nodes in time by con-structing a tournament between contending nodes, and the third protocol uses acombination of the techniques used in the design of the first two MAC protocols.? We provide a mathematical framework for investigating the impact of carriersensing errors on the performance of the proposed protocols.? Based on the above framework, we design a communication system which pro-vides better performance in terms of throughput and delay.1.3 Structure of the ThesisThe rest of the thesis is organized as follows. In Chapter 2, we give an overviewof the V-PLC system and present a summary of the related works. In addition,Chapter 2 covers the fundamentals of CAN protocol and carrier sensing. Chapter 3introduces a frequency-domain collision resolution scheme that uses a combinationof time and frequency multiplexing for resolving the contention between differentdevices connected to the harness. We also investigate the impact of carrier sensingerrors on the performance of the proposed MAC protocol in Chapter 3. In Chapter 4,we introduce a time-domain collision resolution MAC protocol for V-PLC system andanalyze its performance under imperfect carrier sensing errors. Chapter 5 introducesa multi-channel MAC protocol, which first resolves the contention over frequency3Chapter 1. Introductiondomain, and then resolves the contention by constructing a tournament scheme oneach frequency channel. Chapter 6 outlines the main contributions of this thesis anddescribes possible future works.4Chapter 2Background and Related WorkIn this chapter, we first give an overview of the V-PLC system, followed by a descrip-tion of the challenges in developing such a system. We then describe an automotiveprotocol, which is referred to as CAN protocol, used in vehicles for connecting ECUs.After that, we briefly describe the V-PLC MAC protocol reported in [1], which similarto CAN protocol, provides random access for data transmission in vehicles. Since westudy MAC protocols under imperfect carrier sensing in Chapters 3-5, we introducethe basics of carrier sensing in this chapter as well.2.1 Vehicular Power Line CommunicationIn the previous chapter, we have stated the benefits of using PLC technology invehicles such as reducing the vehicle cost, weight, and fuel consumption. We alsodescribed a number of challenges that need to be addressed while designing a V-PLCsystem. V-PLC is much different from the PLC for home applications due to itscomplicated wiring topologies, transmission channel characteristics, attenuation, andnoise. Therefore, special attention should be taken while designing such a system.In the design and analysis of a conventional communication system, noise isusually modeled as additive white Gaussian noise (AWGN). However, the measure-ments [6?8] show that this model is not valid for V-PLC channels. The measurementsof V-PLC system confirms that there are three types of noise in vehicles: (i) colored5Chapter 2. Background and Related Workbackground noise. (ii) narrow-band noise. (iii) impulsive noise. Knowledge of thenoise characteristics is thus essential for optimizing the communication system, e.g.,modulation schemes, channel codings, MAC protocols, etc.2.2 Controller Area NetworkThe CAN bus is a serial communication bus in which all connected ECUs can sendas well as receive messages. CAN bus was initially designed by Robert Bosch GmbHin the mid-1980s for multiplexing the increasing number of ECUs in cars and thus fordecreasing the wire harnesses. Consequently, it became an open systems interconnec-tion (OSI) standard in 1994 and is now a de facto standard in Europe for in-vehicledata transmission. Today, CAN is used as a society of automotive engineers (SAE)class C network in the power-train and chassis domains providing up to 1Mbps, butit also serves as a class B network with a bit rate up to 125Kbps for the electronicsin the body domain.CAN protocol uses a bitwise arbitration mechanism, called carrier sense multipleaccess with collision detection (CSMA/CD) for providing random access to the bus.The CAN protocol controls bus traffic by allowing high-priority messages access tothe bus over lower-priority messages. Every message begins with the arbitration field,which identifies the message and determines its priority. If two or more nodes attemptto transmit messages at the same time, the node with the lowest numeric identifierwins the arbitration and continues with the transmission of its message. The othernodes will retire from contention and must wait until the bus becomes idle againbefore attempting to re-transmit their messages. The requirement of this mechanismis that the duration of each bit must be sufficient for the signal to propagate thelength of the network.6Chapter 2. Background and Related WorkData frames are used for information transmission over CAN network. There aretwo different formats of CAN messages, according to the type of message identifierthat is used by the protocol. Standard and extended frames are frames with 11-bitand 29-bit identifier fields, respectively. Each frame starts with a dominant synchro-nization bit, signaling to all receivers to synchronize their clocks. It is followed by anarbitration filed, which may be either 11 bits (CAN 2.0A) or 29 bits (CAN 2.0B). Itis used to determine which node can access the bus and also to identify the type ofdata that message contains. The next field is the control field which specifies mainlythe number of bytes of data contained in the message. The cyclic redundancy check(CRC) field is 15 bits long. The receiver uses the value in this field to detect the pos-sible transmission errors in the data field. The acknowledgment (ACK) filed consistsof two bits. The transmitter node expects from at least one receiver to acknowledgethe error-free reception of the transmitted message. This acknowledgment is givenby the transmission of a dominant bit in the acknowledge slot by all nodes in thenetwork which received the message free of errors.2.3 Related Work on Random Access MACProtocols for V-PLCWhen multiple users try to communicate with each other via shared transmissionmedium, there is a need for a MAC protocol to resolve the contention betweenusers. MAC protocols for PLC networks can be grouped into two categories, namely,contention-free and contention-based MAC protocols. Contention-free protocols aremainly the ones based on time-division multiple access (TDMA), frequency-divisionmultiple access (FDMA), or code-division multiple access (CDMA). Contention-free7Chapter 2. Background and Related WorkMAC protocols usually rely on a central control point and perform very poorly whenthe number of contending nodes is unknown or keeps varying. On the other hand,contention-based MAC protocols are random access protocols, and usually operatein a distributed manner. They can be categorized into carrier sense multiple access-(CSMA-) based or non-CSMA-based MAC protocols. In this thesis, we focus ondesigning CSMA-based MAC protocols for V-PLC system.Yamar Electronics Ltd. introduced a CSMA-based protocol for in-vehicle PLC,which is referred to as CDR protocol [1]. It uses several slots to resolve the contentionamong contending nodes. Each node randomly switches between carrier sense andcarrier transmission modes. During a slot, when a node hears a carrier, it drops outof the contention, and the other nodes move to the next slot. This procedure repeatsuntil the end of contention, and the goal of the protocol is to have only one survivorby the end of contention with a high probability.The following steps are executed with respect to a single node:1 . An n-bit register is constructed, whose content is randomly determined priorto each packet transmission.2 . The node waits until the bus is idle, followed by a random time delay.3 . The node switches between carrier sensing and carrier transmission accordingto the bit content of the register in step 1. The node performs carrier sensingif the bit content is zero and carrier transmission otherwise.4 . The node proceed with the transmission of its preamble if no carrier wasdetected during any of the carrier sensing modes. Otherwise, if the carrier isdetected, the node retires from contention.8Chapter 2. Background and Related WorkWe later present three alternative MAC protocols in Chapters 3-5. We show thatour proposed MAC protocols perform considerably better than CDR in all scenarios.2.4 Basics of Carrier Sensing and ImpulseFilteringCarrier sensing is a fundamental mechanism in CSMA-based MAC protocols. Eachuser senses the channel before a transmission and defers its transmission if it senses abusy channel to reduce the collision. There are typically two types of errors associatedwith the carrier sensing module: false alarm and miss detection probabilities. Theseprobabilities are widely used as performance criteria for different sensing schemes.The probability of false alarm is the probability that the carrier is absent but issensed as present by the user. The probability of missed detection is the probabilitythat the carrier is present but is sensed as absent by the user. Comparisons betweendifferent carrier sensing schemes are usually done based on these two types of errors.In carrier sensing, there are two hypotheses, whereH0 is denoted as the hypothesisthat a carrier is absent andH1 as the hypothesis that a carrier is present. The receivedsignal for these hypotheses can be expressed asH0 : r(t) = n(t)H1 : r(t) = h s(t) + n(t) (2.1)where s(t) and n(t) denote the transmitted signal and noise, respectively.Energy detection is the most common detector in carrier sensing with a low cost9Chapter 2. Background and Related Workand hardware complexity. In energy detection, the received signal is squared and inte-grated within a bandwidth W over time period T , and is compared with a pre-definedthreshold ?. If it exceeds the threshold (hypothesis H1), the detector declares thepresence of the transmitted signal; otherwise, it is decided that there is no transmis-sion in the sensed frequency channel (hypothesis H0). The time-bandwidth productis u = TW , and is assumed to be a positive integer.The decision statistics of the energy detector is the average energy of the receivedsignal and can be expressed asT = 12u2u?k=1|r(k)|2 (2.2)where r(k) denotes the received signal sampled at sampling frequency fs, and 2u isthe total number of samples taken from the received signal.To determine whether the channel is busy, the detection statistics is comparedwith a predetermined threshold ?. The probability of false alarm pf is the probabilitythat the hypothesis test chooses H1 while it is in fact H0pf = P (T > ?|H0) (2.3)The probability of detection pd is the probability that the test correctly decidesH1 when it is H1pd = P (T > ?|H1) (2.4)We can also define the probability of miss detection aspm = 1? pd (2.5)10Chapter 2. Background and Related WorkNow assume the noise is a stationary AWGN. In this case, the probability of missdetection (pm) and false alarm (pf) can be calculated as [9]pm = 1?Qu(?2?,??) (2.6)pf =?(u, ?2 )?(u) (2.7)where Qu(., .) is the generalized Marcum-Q function, ?(., .) is the upper incompletegamma function [10], and ? is the ratio of signal energy to one-sided noise spectraldensity, i.e., ? = u?SNR, where SNR is the signal-to-noise ratio of the preprocessedsignal.The fact is that noise in power lines is not AWGN. Therefore, we can express thenoise asn(t) = w(t) + i(t) (2.8)where w(t) and i(t) denote the background Gaussian noise and impulsive noise compo-nent, respectively. Since the statistical behavior of the noise over V-PLC is unknown,it is best to remove the impulse components from the noise by using a robust im-pulse filtering technique. The overall structure of the detector is depicted in Fig. 2.1.The received signal passes through a band-pass filter (BPF) of bandwidth W and anAnalog-to-Digital Converter (ADC) with sampling rate fs to discretize the input sig-nal, followed by a preprocessor and a linear signal detector. We use energy detectoras a signal detection scheme for its low complexity. We would like to remark, howeverthat any other signal detection scheme of interest can also be used in the system.We used the preprocessor proposed in [11] as it provides a simple real-time techniqueto replace the impulse components in the received signal. The preprocessor has an11Chapter 2. Background and Related Workimpulse detector which is composed of a blanking nonlinearity to mitigate the effectsof the impulsive corruptions, followed by a reconstruction filter that selects betweeninput and predicted samples.BPFr(t)ADC impulse detectorrnreconstructionfilterlinearsignaldetectordecide H0or H1Figure 2.1: Block diagram of a robust signal detector.We performed an experiment to illustrate the effectiveness of the preprocessor.Consider the received signal is corrupted by a Gaussian noise with variance one,plus an impulsive noise with probability of occurrence 0.1 and variance 10. Fig. 2.2shows one thousand samples of the received signal before and after preprocessing.It can be observed that the preprocessor successfully removes the impulses from thesignal. To better understand its performance, we plotted the empirical cumulativedistribution function (ECDF) of the received signal in Fig. 2.3. It can be seen that thepreprocessor removes the heavy tail of the signal, and the preprocessed signal almostmatches the Gaussian distribution, i.e., impulse-free signal. We then use an energydetector which compares the average energy of the output of the preprocessor overthe sensing period T to a predetermined threshold ?. The time-bandwidth product isu = TW , and is assumed to be a positive integer. The probability of miss detection(pm) and false alarm (pf) can be calculated as in (2.6) and (2.7).12Chapter 2. Background and Related Work0 100 200 300 400 500 600 700 800 900 1000?10?5051015Samples [n]Amplitude[V] received signalreceived signal afterpreprocessingFigure 2.2: Samples of the received signal before and after preprocessing.?15 ?10 ?5 0 5 10 1500.10.20.30.40.50.60.70.80.91Amplitude [V] ECDFreceived signalreceived signalafter preprocessingreceived signal withoutimpulsive componentFigure 2.3: ECDF of the real, preprocessed, and impulse-free received signal.13Chapter 3Frequency-Domain ContentionResolution Algorithm withImperfect Carrier SensingIn this chapter, we present a MAC protocol for V-PLC system, which uses a com-bination of time and frequency multiplexing to resolve the contention among nodes.We first present our motivations and assumptions, followed by system model. Wefind the optimal parameters of the protocol with the assumption of imperfect carriersensing in Section 3.3. In Section 3.4, we present the performance evaluation of theproposed scheme using numerical examples, followed by a summary of the chapter inSection 3.5.3.1 Motivations and AssumptionsYamar Electronics Ltd. introduced a contention-based MAC protocol for V-PLCsystem, referred to as CDR, in [1]. The protocol uses several slots to arbitrate packettransmission. It resolves the contention between contending nodes by switching be-tween carrier transmission and carrier sensing modes in each slot. Similar to CDRprotocol, our proposed MAC scheme tries to arbitrate packet transmission over powerlines. Our protocol, however, uses multiple frequency channels to arbitrate packets14Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingwithin slots. Hence, it is a novel solution to overcome the frequency-selective be-havior of V-PLC transmission channels. CDR does a good job in handling scenarioswith small numbers of nodes, but does not handle large numbers of nodes well. Theauthors in [12] designed a MAC protocol called Alert for low latency applications.It attempts to resolve a contention through randomized subcarrier assignments thatare optimized to minimize latency. Our protocol is similar to Alert in the sensethat it uses the same subcarrier/round structure. However, our approach does notrequire that the sum of the subcarrier selection probabilities be equal to unity; inother words, nodes may or may not choose a subcarrier. We show later, that thisapproach improves the MAC layer performance. Moreover, we generalize the solu-tion proposed in [12] by examining the effects of carrier sensing errors on the MAClayer efficiency. We also construct a cross-layer optimization problem, and obtain theoptimized physical layer (PHY) and MAC layer parameters together.3.2 System ModelWe assume the system uses a multi-carrier physical layer as proposed in [8]. Ourscheme follows the model depicted as in Fig. 3.1. The channel is assumed to be idlewhen nodes simultaneously try to transmit packets. Data transmission is dividedinto contention rounds and multiple subcarriers are available in each round. Wepresent our protocol concepts with an example. Assume two nodes N1 and N2 aretrying to transmit a packet to node R. Each node, with a probability that we define,starts with the transmission of its preamble on the subcarrier index i, chosen from1, . . . , Nc. Further assume that, each node is equipped with a single transceiver; thus,can not simultaneously transmit and receive packets. Here, assume N1 and N2 havetransmitted on subcarriers f1 and f2, respectively, and f1 < f2. At the beginning of15Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier SensingFigure 3.1: A view of the frame structure.the contention round, R listens for signals on all subcarriers starting from subcarrierindex 1, and if any are detected, it locks on the subcarrier and waits to receive thepacket. In this example, since N1 has transmitted on the earlier subcarrier, it wins thecontention. If the packet is received correctly, R sends back an ACK over subcarrierf1 at the end of the contention round. There are, however, some scenarios that mightcause R not to receive the packet sent by N1. If R senses a high signal at subcarrierindex < f1, due to the interference or noise, R never receives a packet from any node.If R does not detect the signal on subcarrier f1, no packet arrives from N1. It isobvious that theses sensing errors have a huge influence on the performance of theprotocol.There are two design parameters that need to be known while protocol is in op-eration. (1). number of subcarriers (2). probability distribution over subcarriers.We can reduce the contention between nodes by using a large number of subcarriers.However, this also results in larger time slots and reduces the number of time slotswithin a period, and therefore introduces a tradeoff. Similarly, assigning low proba-bilities to the low-indexed subcarriers while the workload is high would arbitrate the16Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingpackets. On the other hand, when the workload is low, assigning low probabilities tolow-indexed subcarriers will result in longer delays. Therefore, it is important to findthe values for these parameters which optimize the performance of the protocol.3.2.1 Sensing ModelWe follow the procedure described in Chapter 2 for carrier sensing. This means thereceived signal is passed through the preprocessor to remove the impulsive compo-nents. We then employ the commonly used energy detector for channel sensing dueto its simplicity. We should remark, however that, the analysis presented in thischapter can be easily extended for any other detection schemes as will be addressedin Section 3.3. Suppose that the received signal has passed through the preprocessorand is sampled at sampling frequency fs. We are interested in detecting of the trans-mitted signal in a given subcarrier. In energy detection, the received signal is squaredand integrated within a bandwidth W over time period T , and is compared with apre-defined threshold ?. If it exceeds the threshold (hypothesis H1), the detectordeclares the presence of the transmitted signal; otherwise, it is decided that there isno transmission in the sensed subcarrier (hypothesis H0). The received signal undertwo hypotheses at time t can be represented asH0 : r(t) = b(t)H1 : r(t) = hs(t) + b(t) (3.1)where b(t) is the noise signal at the receiver, and is assumed to be a circularly sym-metric complex Gaussian (CSCG) random variable, independent and identically dis-tributed (i.i.d.) with mean zero and variance ?2b . The samples of transmitted signal,17Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensings(t), also follows CSCG, i.i.d. sequence with mean zero and variance ?2s , and the PLCchannel gain h is set to unity. In energy detection, the probabilities of false alarm(pf) and miss-detection (pm) can be evaluated by [10]pf = p (decide H1 | H0) = 1? ?(Ns,??2b) (3.2)pm = p (decide H0 | H1) = ?(Ns,??2b + ?2s) (3.3)where Ns denotes the number of samples taken by the receiver at each subcarrier.?(x, t) =? t0 e?yyx?1dy??0 e?yyx?1dyis the incomplete gamma function. The detection threshold isgiven by [10]? = ?2b??1(Ns, 1? pf) (3.4)??1(x; .) is the inverse function of ?(x; .) with respect to its second variable. Finally,we can express pm in terms of pf aspm = ?(Ns,11 + ???1(Ns, 1? pf))(3.5)where signal?to?noise ratio (SNR) at the receiver is denoted as ? = ?2s?2b . We assumeSNRs are different at each subcarrier, and can be expressed as ?i for i = 1, 2, . . . , Nc.Therefore, in the remainder of the chapter, pim and pif correspond to the probabilityof miss-detection and false alarm of the subcarrier index i, respectively.3.2.2 Probability of Successful TransmissionThe channel is assumed to be idle when nodes try to send data onto the medium atthe same time. Each node may choose one of Nc subcarriers to send its data. Letp = (p1, p2, . . . , pNc) be the selection distribution that each node uses to select one of18Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier SensingNc subcarriers. We say that subcarrier j is successful if and only if(i) j is the smallest index among chosen subcarriers and there is no false alarmerror on the earlier subcarriers.(ii) there is only one node transmitting on the subcarrier j with no miss-detectionerror.Suppose that number of nodes in a contention is n. The probability of successfultransmission ispns = nNc?j=1pj(1? pj)n?1(1? pjm)j?1?t=0(1? pt)n(1? ptf ) (3.6)where p0f , 0 and p0 , 0.Let S1 be a random variable that shows the number of rounds required to suc-cessfully receive the first packet from n nodes. If the probability of success in eachround is constant and equal to pns , then the probability that mth round is the firstsuccess has a Geometric distribution with expected value 1pns (S1 ? Geom(pns )), andis defined asP(S1 = m) = pns (1? pns )m?1 m = 1, 2, . . . (3.7)where we assumed that the PHY parameters are constant in each round which leadsto a constant probability of success. By the same argument, we need Geom(pn?1s )rounds to receive the second packet. In general, the distribution of the number ofrounds required to receive the kth packet successfully is19Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier SensingSk ?n?i=n?k+1Geom(pis) (3.8)3.2.3 Time UtilizationFrom our previous discussions, it is clear that we can reduce the expected numberof rounds to receive packets by using a larger number of subcarriers in a contentionround. On the other hand, a larger number of subcarriers increases the length of acontention round. We define the average time utilization corresponding to the first kreceived packets ?k as?k =k(td + tack)E(Sk)TCR(3.9)where td and tack are time durations required for data and acknowledgment trans-missions, respectively. E(Sk) is the expected value of number of contention roundsto successfully receive k packets, and the duration of a contention round TCR isTCR =NsfsNc + td + tack (3.10)where Nsfs specifies the sampling time required by the receiver to take Ns samplesfrom a subcarrier. Note that in (3.10), we assumed that the switching time betweensubcarriers is negligible.3.3 Optimal Selection DistributionIn this section, we find the selection distribution p? and sensing threshold ?? thatmaximizes pns , the probability of successful packet delivery in one round for a knownnumber of nodes. We derive optimal distributions in the cases of both finite and20Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensinginfinite number of nodes.3.3.1 Analysis of Optimal Scheme with Finite nFirst, we assume that the values of pm and pf for each subcarrier are known. Then,the question is what is the selection distribution that maximizes the probability ofsuccessful transmission for known sensing errors?Proposition 1: For a given pim and pif , i = 1, . . . , Nc, the probability distributionthat maximizes (3.6) satisfies the following recursive equationp?k =1? (1? p?k+1)n?1vk(1? pk+1m )n? (1? p?k+1)n?1vk(1? pk+1m )(3.11)for k = 1, . . . , Nc ? 1 with p?Nc = 1n , andvk =1? pkf1? pkm(3.12)Proof: Assume that the values of p?i , i = 1, 2, . . . , Nc?1 are already known. Then,p?Nc maximizes (3.6) if ddp?Nc (pns ) = 0. Differentiating (3.6), we have(1? p?Nc)n?1 ?(n?1)p?Nc(1? p?Nc)n?2 = 0. One solution is p?Nc = 1 which is clearly not the optimalanswer, and the second solution is p?Nc = 1n . Next, by a similar approach, we derivep?Nc?1 assuming that the values of p?i , i = 1, 2, . . . , Nc ? 2 are known. Again, onesolution is p?Nc?1 = 1, and the acceptable answer is the one given in (3.11), withk = Nc ? 1. Repeating this procedure yields to the optimum distribution in (3.11).After obtaining the optimum selection distribution p? in terms of carrier sensingerrors, we range pif , i = 1, . . . , Nc in (3.5) from 0 to 1 for a given Ns and SNR, andobtain pf and pm for each subcarrier which are optimized to maximize the probabilityof successful transmission in (3.6). The following example is given to further illustrate21Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingthe design procedure.Example 1: Consider a V-PLC network with n = 5 nodes and Nc = 10 subcarri-ers. The energy detector takes Ns = 10 samples from a transmitted signal in eachsubcarrier. We consider the following two cases:1 . all subcarriers have the same SNR and is equal to 0dB.2 . subcarrires have different SNRs and the relation is given by?k = ?m + 10(k ? 1) log?; k = 1, 2, . . . , Ncwhere k is the subcarrier index, ?m = 5dB, and ? = 0.8. Using the results in proposi-tion 1, we can obtain the optimal parameters (p?, p?f , p?m) as shown in Table 3.1. Theresults, in both cases, show that the subcarrier selection probability p?k increases ask increases. The probability of success for case 1 and 2 are 0.577 and 0.7496, respec-tively. We also would like to note that using (3.4), we can determine the optimumdetection threshold ??k for a given noise variance in each subcarrier.For this example with no sensing errors, our scheme and Alert [12] achieve theprobability of success of 0.8668 and 0.8541, respectively. As previously mentioned, inour model, the sum of subcarrier selection probabilities may not be equal to 1, andthus provides more chance for nodes to choose different subcarriers which leads to ahigher probability of success.3.3.2 Asymptotic Analysis of Optimal Scheme as n ? ?We now provide asymptotic expressions for optimum selection distribution and max-imum probability of success when n ??.22Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier SensingTable 3.1: Optimal Parameters in Example 1Case 1 Case 2p? p?f p?m p? p?f p?mk1 0.0813 0.0921 0.1899 0.064 0.0058 0.02342 0.0819 0.0929 0.1888 0.0715 0.0125 0.03993 0.0828 0.0943 0.1871 0.0797 0.0249 0.06214 0.0843 0.0963 0.1846 0.0888 0.0463 0.08795 0.0868 0.0998 0.1803 0.099 0.0804 0.11446 0.0912 0.1065 0.1776 0.1109 0.1325 0.13627 0.0987 0.1187 0.16 0.1262 0.2146 0.14448 0.1118 0.1416 0.14 0.1474 0.3478 0.1299 0.1372 0.2016 0.1021 0.1985 0.977 0.001410 0.2 1 ? 0 0.2 1 ? 0Proposition 2: The maximum probability of successful transmission for n ? ?is given byp?s = (1? p1m)e?q?1 (3.13)where q?k for k = 1, 2, . . . , Nc is recursively defined asq?k =???????1 for k = Nc1? (1?pkf )(1?pk+1m )(1?pkm)e?q?k+1 else.Proof : As discussed earlier, the selection probabilities depend on number of nodes.Therefore, in order to get a non-zero probability of success, we assume that theoptimal probabilities are expressed as p?k =q?kn for k = 1, 2, . . . , Nc. By using theseprobabilities in (3.6) and taking n ??, we havep?s =Nc?j=1q?j e?q?j (1? pjm)j?1?t=0e?q?t (1? ptf ) (3.14)23Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingwhere we used limn??(1 + xn)n = ex for x ? R. Taking the derivation of (3.14) withrespect to q?i i = 1, . . . , Nc, and imposing it equal to zero, we obtaine?q?i (1? pim)i?1?t=0e?q?t (1? ptf)(1?Nc?j=iq?je??jk=i+1 q?k1? pjm1? pimj?1?t=i(1? ptf ))= 0 (3.15)hence,Nc?j=iq?j e??jk=i+1 q?k1? pjm1? pimj?1?t=i(1? ptf) = 1 (3.16)Setting i = Nc in (3.16) gives q?Nc = 1. Then, for i = 1, 2, . . . , Nc ? 1, we canrewrite (3.16) as1 =q?i +(1? pif )(1? pi+1m )e?q?i+11? pimNc?j=i+1q?j e??jk=i+2 q?k1? pjm1? pi+1mj?1?t=i+1(1? ptf) (3.17)It can be seen that the summation in (3.17) is the same as (3.16) for i + 1, andtherefore is equal to one which gives the solution in (3.13). As an example, withno sensing errors, we can achieve the probability of success of 0.8418 with Nc = 10subcarriers which is very close to the one previously calculated in example 1 for n = 5nodes.3.4 Numerical ResultsIn this section, we present some numerical results to evaluate the proposed MACscheme with different PHY parameters. PHY bit rate is 1Mbps, and the payload size24Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingof a packet is fixed to 64 Bytes [14]. Transmitted signal is sampled at a frequencyof 100MHz to avoid aliasing errors [6]. Throughout this section, we assume, forsimplicity, that all subcarriers have the same SNR.3.4.1 Performance under Different SNRsIn this experiment, number of nodes is fixed at 16. The channel average SNR variesfrom -15dB to 15dB. The probability of successful transmission for different numberof subcarriers at Ns = 10, and for different number of samples at Nc = 8 are shownin Fig. 3.2 and Fig. 3.3, respectively. It can be seen that, given the same number of?15 ?10 ?5 0 5 10 150.350.40.450.50.550.60.650.70.750.80.85SNR(dB)p16 s Nc = 4Nc = 8Nc = 12Figure 3.2: Probability of successful transmission versus SNR for different number ofsubcarriers at Ns = 10.sampling, ps increases as SNR increases. Note also that a higher Nc leads to a largervalue for ps. This is expected as increasing the number of subcarriers increases thelikelihood that nodes select different subcarriers and thus yields higher ps. As shown25Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingin Fig. 3.3, by increasing Ns, we can achieve the same ps for smaller values of SNR.However, the difference tends to dwindle in the high SNR region (SNR?5dB).?15 ?10 ?5 0 5 10 150.350.40.450.50.550.60.650.70.750.8SNR(dB)p16 s Ns = 10Ns = 30Ns = 100Figure 3.3: Probability of successful transmission versus SNR for different number ofsamples at Nc = 8.3.4.2 Performance under Different Number of NodesThe effect of number of nodes on the probability of success for multiple cases isillustrated in Fig. 3.4. Nc is 8, and Ns is set to 10. For a fixed SNR, as n increases, pnsdrops initially, then becomes almost constant. It can be observed that with perfectsensing, we can achieve highest pns , and the probability of success drops as SNRdecreases.26Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensing1 10 20 30 40 50 60 70 80 90 1000.40.50.60.70.80.91npn s idealSNR = 0dBSNR = 5dBSNR = ?5dBFigure 3.4: Probability of successful transmission as a function of number of nodesfor different SNRs, Nc = 8 and Ns = 10.3.4.3 Time UtilizationNumber of nodes in a contention is 16 and the channel SNR is set to -5dB. Fig. 3.5shows time utilization of the first packet as a function of Ns and Nc for the proposeddesign approach. For a fixed number of subcarriers, ?1 increases with number ofsampling and then decreases. This happens since increasing Ns leads to a lowerE(S1) as shown in Fig. 3.3. On the other hand, as we increase Ns, the length of eachround is increased, and therefore there is a value for Nc that maximizes ?1. Similarly,for a fixed number of sampling, ?1 increases with number of subcarriers and thendecreases. Furthermore, we notice from Fig. 3.5 that the maximum time utilizationis 0.76, and is occurred at Nc = 13 and Ns = 261.27Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensing12004006008001000258111417200.40.50.60.70.8NsNc? 1Figure 3.5: ?1 versus Ns and Nc, SNR = -5dB and n = 16.3.4.4 Comparison with CDR ProtocolIn this subsection, we compare the performance of the proposed scheme with CDR [1].We plot the probability of success for different values of Nc for both protocols asshown in Fig. 3.6. To make a fair comparison, we note that using Nc subcarriers inour scheme increases the packet overhead by the same length as employing Nc slotsin the ER of CDR protocol. Number of contending nodes varies from 2 to 100. Theresults show that the success rates of both schemes decrease as the network size grows.However, the decrease rate of our scheme is much lower than that of CDR. CDR isobserved to have a slightly better performance when the number of contending nodesis small. However, our scheme outperforms CDR when network size increases, anddisparity between two schemes becomes larger as number of nodes increases.28Chapter 3. Frequency-Domain Contention Resolution Algorithm with Imperfect Carrier Sensing2 10 20 30 40 50 60 70 80 90 10000.10.20.30.40.50.60.70.80.91npn s Nc = 5Nc = 7Nc = 9Nc = 11CDRprotocolProposedprotocolFigure 3.6: Probability of successful transmission of the proposed and CDR protocolas a function of number of nodes.3.5 SummaryIn this chapter, we have introduced a random access MAC protocol which uses a novelcontention mechanism in which nodes use subcarriers to perform channel contention.Through mathematical analysis, we have examined the effect of carrier sensing errorson the protocol performance. We have derived expressions for optimum selectiondistribution p? that nodes employ to choose a subcarrier for data transmission, andfor design parameters involved in carrier sensing scheme. With numerical examples,we have verified the effectiveness of our proposed scheme.29Chapter 4Time-Domain ContentionResolution Algorithm withImperfect Carrier SensingIn the previous chapter, we introduced a MAC protocol that resolves the contentionbetween nodes by using multiple frequency channels. Now, we focus on MAC pro-tocols which attempt to resolve the contention on a given frequency channel in aconstant number of slots. We first state our motivations and assumptions. We thendescribe the system model and give an example of the protocol operation in Sec-tion 4.2. Section 4.3 presents the detailed analysis of the protocol under carriersensing failures. Section 4.4 provides numerical examples and finally summary isgiven in Section 4.5.4.1 Motivations and AssumptionsIn Chapter 2, we described the previously developed contention-based MAC protocol,referred to as CDR, for V-PLC system in detail. Here, we briefly state its operation.CDR resolves the contention in a number of slots by randomly switching betweencarrier sense and carrier transmission modes. During a slot, nodes drop out of con-tention, if they were listening and hear a carrier on the bus. The remaining nodes30Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingsurvive and move to the next slot. This process repeats until the contention finishesand the goal here is to have one survivor at the end of the contention with a highprobability. The authors in [1] provided mathematical analysis of the protocol withthe assumption of perfect carrier sensing.However, as mentioned in Chapter 2, the measurements of V-PLC channels [4,7],show that it is necessary to analyze the performance of the MAC protocols undercarrier sensing errors to improve the overall system performance. Hence, the objectiveof this chapter is to extend the study of contention based MAC protocols suitablefor in-vehicle PLC to the more realistic scenario of imperfect carrier sensing. To thisend, we consider the MAC protocol from [13], which is called selective tournaments,and is very similar to CDR. In particular, as in CDR, it switches between carriersense and carrier transmission in each slot. However, nodes use a unique nonuniformprobability distribution to select their operation in each slot, which minimizes thecollision between contending nodes, and hence offers a fast contention resolutionwhile its performance degrades at a much slower rate than CDR with the increase innumber of contending nodes.4.2 System ModelWe consider a network setting where nc nodes are connected to the harness. Weassume time is slotted and nodes in the network are time synchronized. We furtherassume that each node in the network is equipped with a half-duplex transceiver,i.e., it cannot transmit and listen to one channel at the same time. Nodes withpackets to transmit contend over a fixed number of slots. Nodes choose to transmita carrier on the bus by using a probabilistic approach. In a given slot, nodes lose thecontention if they were sensing the bus and hear a valid carrier. Otherwise, they move31Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingto the next slot. We use the procedure described in Chapter 2 for carrier sensing,where sensing is performed by preprocessing the received signal so that it containsno impulsive component and then applying energy detection on the preprocessedsignal. The protocol operation under imperfect carrier sensing will be presented inthe next subsection. The mathematical formulation of the protocol, as well as theanalysis of the carrier sensing error on the performance of the protocol are presentedin Section 4.3. We then present the numerical results to evaluate the performance ofthe protocol under imperfect carrier sensing, followed by a summary of the chapterin Sections 4.4 and 4.5, respectively.4.2.1 MAC Protocol OperationWe now describe the operation of the selective tournaments MAC protocol in detail.We also show that, by considering different scenarios, how carrier sensing errors canaffect the results of the operation. The protocol resolves the contention betweencontending nodes over ns slots. All the contending nodes go through the followingprocedure. Before the ith slot with i ? {1, 2, . . . , ns}, a node generates a binaryrandom integer ci with a predetermined probability. It then transmits a carrier onthe bus if ci = 1. Otherwise, it listens to the bus for a slot duration. We denoteci = 0 and 1 as signal 0 and signal 1, respectively. A node that is listening and sensesthe bus busy will retire from the contention. On the other hand, if a node sensesthe bus idle, it stays in the contention. A node that transmits a carrier on the bussurvives and moves to the next slot.Fig. 4.1 illustrates an example of the protocol with three slots. The left and rightbranches correspond to the events of choosing signal 1 and 0, respectively. Assumenodes A and B have packets to transmit. In the first slot, each node chooses signal 132Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingwith probability q. In this example, both nodes selected signal 0, and moved to thesecond slot. Now assume node A has detected a carrier due to the false alarm. In thatcase, node A would retire from contention. In the second slot, a node chooses signal1 with probability q1 if it has emitted a carrier in the first slot, and with probabilityq0 otherwise. Here, in the second slot, nodes A and B have selected signal 1 and0, respectively. Thus, node A preempts node B. However, in this example, wehave assumed that node B has not detected the carrier from node A, and hencestayed in the contention (miss detection error). In the third slot, both nodes choseto transmit a carrier, and therefore survived the whole process. We can describe thewhole process with a set of three binary digits. We can then conclude that a nodewith the largest value wins the contention. However, this might not be true withthe presence of sensing errors. In this example, nodes A and B have chosen 011 and001, respectively. Hence, node A has a larger binary value and wins the contentionwith the assumption of perfect carrier sensing. However, the result is unknown withimperfect sensing as in the above example, both nodes won the contention.qq1q11111 110q10101 100q0q01011A010Aq00001B000BABFigure 4.1: Illustration of the protocol operation.33Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensing4.3 MAC Protocol AnalysisThis section presents an analysis to provide an insight into the impact of imperfectcarrier sensing on the performance of selective tournaments MAC protocol.We consider a PLC network with a total population of nc nodes. We modelthe number of contending nodes at a given time by a truncated power-law degreedistribution due to its flexibility, which is given bypnc,n =1?(?)n? (4.1)with n ? {2, . . . , nc}, and ?(?) =?ncz=21z? is the scaling factor to make the proba-bilities sum to one. This distribution is widely applied to model self-similar arrivalin packet traffic. However, we would like to point it out that the analyses in thischapter are valid for any other distribution of interest.4.3.1 Probability Distribution of SurvivorsWe define G(z) as the probability generating function for the number of contendingnodes, which is given byG(z) := E(zn) =nc?n=2pnc,n zn (4.2)We derive the probability generating function for the number of contending nodesstill in the contention after the elapse of one time slot. We know that if a node thatis listening does not hear the carrier on the bus, it will select itself as a winner. So,depending on the number of nodes who choose signal 1, we derive expressions forthe distribution of survivors. We use subscripts 0 and 1 on probability generating34Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingfunctions to denote the cases when all nodes choose signal 0 or at least one nodechooses signal 1, respectively. We first calculate the probability generating functionfor the case when all nodes choose to listen to the bus, which can be expressed asG0 (z) =nc?n=2pnc,n(1? q)nn?i=0(ni)(1? pf)ipn?if zi=nc?n=2pnc,n(1? q)n [(1? pf)z + pf ]n= G ((1? q)zf) (4.3)where zf := (1? pf)z + pf . q is the probability of transmitting a carrier in the firstslot, and pf is the false alarm probability given in (2.7). In this case, a node movesto the second slot if it has not detected a carrier on the bus, which happens withprobability 1 ? pf . We used Binomial distribution to denote the probability that iout of n nodes have not detected the carrier, and thus moved to the second slot.We now derive the probability generating function for the number of survivingnodes conditioning that at least one node has transmitted a carrier in the first slot.The expression for G1 is given byG1(z) =nc?n=2pnc,nn?i=1(ni)qi(1? q)n?izin?i?j=0(n? ij)pjm(1? pm)n?i?j zj= G (qz + (1? q)zm)?G ((1? q)zm) (4.4)where zm := pmz+1?pm, and pm is the miss detection probability defined in (2.6). Inthis case, all nodes that have transmitted a carrier in the first slot survive and moveto the second slot. However, nodes that chose to listen to the bus and have detected35Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingthe carrier, which happens with probability 1 ? pm would retire from contention.Others that have listened to the bus and did not hear the carrier (with probabilitypm) will continue the contention.We denote c = [c1 . . . ci . . . ck] as the signaling pattern of a node in the first k slots,i.e., ci = 1 and 0 correspond to signal 1 and 0, respectively. We are now interested incalculating the probability generating function of survivors after the elapse of k + 1slots. By mathematical induction and using (5.13) and (5.14), we haveGc0(z) = Gc ((1? qc)zf ) (4.5)andGc1(z) = Gc (qcz + (1? qc)zm)?Gc ((1? qc)zm) (4.6)where qc is the probability of emitting a carrier in slot k + 1, given the signalingpattern c in the first k slots. Gc is the probability generating function of survivorscorresponding to the signaling pattern c, and G? := G. Hence, the probabilitygenerating function of survivors after ns slots is ?c?CnsGc(z), where Cns contains allthe codewords of length ns form the alphabet {0, 1}. Moreover, the distribution ofsurvivors is completely characterized by pnsnc,n = 1n! dndzn?c?Cns Gc(z)|z=0, where n is thenumber of winners at the end of the contention. We can compute the probabilityof successful transmission, which is defined as the probability that at the end of thecontention only one survivor remains, by the following equationps = pnsnc,1 =ddz?c?CnsGc(z)|z=0 (4.7)The system may remain idle even after the completion of contention. This canhappen since there might be a situation where in a slot, all nodes in the contention36Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingchoose to listen and all of them hear a carrier due to the false alarm error, and henceretire from contention. This probability can be calculated aspi = pnsnc,0 =?c?CnsGc(0) (4.8)and the probability that two or more nodes remain at the end of the contention, i.e.,collision probability, is simply given bypc = 1? ps ? pi (4.9)We need to find the values for probabilities that nodes use to select betweensignal 1 and 0 in different slots, i.e., ?ns?1i=0 2i = 2ns?1 parameters. We obtain thesevalues by using the procedure provided in [13], which first approximates the collisionrate with a Riemann integral and then obtains the parameters that minimizes thecollision between nodes with the assumption of perfect carrier sensing. The proposedprocedure is summarized in Algorithm 1, and optimal parameters for (nc, ns, ?)=(16,6, 0.6) are presented in Table 4.1.Suppose we use the optimum probabilities obtained from Algorithm 1 for a knownpnc,n with the assumption of perfect carrier sensing. Now, consider the case whenthe probability distribution of contending nodes differs from pnc,n. The probabilityof success in this case is smaller from the one calculated with the true probabilitydistribution of contending nodes. Hence, it is interesting to measure the sensitivity ofprobability of success with ?. We also assume the number of nodes connected to bus,nc, is a constant and can not be changed. Fig. 4.2 shows the probability of successas a function of ?, when optimum probabilities are calculated for ? = 0.6. It can beseen that the shape of the curve is similar to a logistic function and ? = 0.6 is in the37Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier SensingAlgorithm 1 : Algorithm to minimize pc with perfect sensing.1: Set U?(z) :=?G??(z) /* G?? (z) is the second derivative of G(z) with respect to z */2: Initialization: Set n := 2ns, N := 10n, and U0 := 03: for i = 1 to N do4: Ui := Ui?1 + U?(i? 12N)5: end for6: Set x0 := 0, and xn := 17: for t = 1 to n? 1 do8: xt = 1N min{i : UiUN?1 ?tn}9: end for10: Set q := 1? x(n2 )x(n)11: for l = 1 to ns ? 1 do12: Set L := 2ns?l?113: for j = 0 to 2l?1 do14: Convert j into l bits binary number c15: qc := x(2L(j+1))?x(L(2j+1))x(2L(j+1))?x(2Lj)16: end for17: end formiddle part of the curve. We can also observe that the range of the changes in ps issmall, and therefore we can conclude that the performance of the protocol is almostindependent of ?, when the optimum probabilities are calculated for ? = 0.6.We now compare the performance of the selective tournaments scheme with CDRunder perfect carrier sensing. To make a fair comparison, we note that, with the samenumber of slots, both schemes increase the packet overhead by the same length. Weplotted the probability of success as a function of nc, number of nodes connected tothe bus, for different number of slots in Fig. 4.3. We have also assumed the numberof contending nodes, for both schemes, follows the probability distribution given in(5.1) for ?= 0.6. It can be observed that the selective tournaments with six slots hasa much better performance than CDR scheme with five, seven, and nine slots, andstill a higher probability of success than CDR with eleven slots.38Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier SensingTable 4.1: Optimal parameters for (nc=16, ns=6, ?=0.6)q = 0.189 q0110 = 0.483 q01011 = 0.5q0 = 0.279 q0111 = 0.481 q01100 = 0.5q1 = 0.396 q1000 = 0.5 q01101 = 0.466q00 = 0.371 q1001 = 0.473 q01110 = 0.5q01 = 0.4 q1010 = 0.47 q01111 = 0.461q10 = 0.438 q1011 = 0.466 q10000 = 0.454q11 = 0.458 q1100 = 0.5 q10001 = 0.454q000 = 0.434 q1101 = 0.5 q10010 = 0.5q001 = 0.438 q1110 = 0.454 q10011 = 0.444q010 = 0.448 q1111 = 0.545 q10100 = 0.444q011 = 0.465 q00000 = 0.486 q10101 = 0.5q100 = 0.463 q00001 = 0.475 q10110 = 0.5q101 = 0.468 q00010 = 0.49 q10111 = 0.428q110 = 0.461 q00011 = 0.489 q11000 = 0.428q111 = 0.5 q00100 = 0.5 q11001 = 0.571q0000 = 0.458 q00101 = 0.472 q11010 = 0.5q0001 = 0.46 q00110 = 0.484 q11011 = 0.5q0010 = 0.461 q00111 = 0.5 q11100 = 0.5q0011 = 0.459 q01000 = 0.5 q11101 = 0.6q0100 = 0.458 q01001 = 0.5 q11110 = 0.4q0101 = 0.461 q01010 = 0.476 q11111 = 0.539Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensing?100 ?80 ?60 ?40 ?20 0 20 40 60 80 1000.9560.9580.960.9620.9640.9660.9680.970.9720.9740.976?p s ? = 0.6Figure 4.2: ps as a function of ?, when the optimal probabilities are obtained for?=0.6 (perfect sensing).4.3.2 Throughput and Delay AnalysisWe define the network throughput ? as a ratio of time occupied by the transmittedpacket to the total medium access time for successfully transmitting a packet as? = psTpktpsTs + pcTc + piTi(4.10)where Tpkt is the time to transmit a packet. Ts and Tc denote the time taken by asuccessfully and a collided transmission, respectively, and Ti is the time consumed byan idle cycle.We can also derive the average delay for a successful transmitted packet, which isdefined as a time spent from the moment that the packet reaches the head-of-line ofthe queue to the time that it is transmitted successfully. Assume a given node has a40Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensing2 5 10 15 20 25 30 35 40 45 500.20.30.40.50.60.70.80.91ncp s ns = 5ns = 7ns = 9ns = 11CDRSelective tournaments, ns=6Figure 4.3: Probability of success for selective tournaments and CDR versus nc fordifferent number of slots (perfect sensing).packet to send, the probability that it wins the contention is given byp?s =nc?k=2p?s(k)k pnc,k (4.11)where p?s(k) is the probability of successful data transmission calculated in (5.18) forpnc,n = ?(n ? k), and ?(.) denotes the dirac delta function. Note that the optimalprobabilities are still calculated using Algorithm 1 with pnc,n given in (5.1). However,we are evaluating the success probability with ?(n? k) since we are interested in thecase when exactly k nodes are contending for the medium. For a given node, theprobability that a successful transmission is followed by j fails is p?s(1 ? p?s)j, and41Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingthus the average delay is expressed byD =??j=0p?s(1? p?s)j(Ts + jTavg) = Ts +Tavgp?s(4.12)where Tavg is the average transmission time, and is given byTavg = psTs + pcTc + piTi (4.13)4.4 Numerical ResultsIn this section, we evaluate the MAC layer throughput and delay as a function ofphysical layer sensing errors. We assume the following parameters for our evaluations.Physical layer bit rate is set to 1Mbps, and the sampling rate of the ADC is 500kHz.The packet has a payload size of 14 bytes [14]. We also assume the preprocessorintroduced in Chapter 2 can completely remove the impulses from received signal,and therefore we obtain the results under Gaussian noise assumption. Throughoutthis section, the number of slots is fixed to 6, and nc and ? in (5.1) are set to 16 and0.6, respectively, unless specified otherwise.The effect of false alarm error on the network throughput is illustrated in Fig. 4.4.The number of samples taken from the signal is set to 10, which is twice the time-bandwidth product. The SNR varies from -5dB to 5dB. As can be seen, for a fixedSNR, there is an optimum false alarm error that maximizes the throughput. It canalso be observed that as SNR increases, the optimum point moves to the left, andtherefore maximum throughput is achieved with smaller values of false alarm errors.When we increase the false alarm error from its optimum value, the throughputdegrades at a much higher rate for higher SNR values. Hence, it is crucial to find the42Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensing0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 100.10.20.30.40.50.60.70.80.91pf?SNR = -5dBSNR increasesFigure 4.4: ? versus pf for different SNR values, u = 5.optimum value for false alarm error which maximizes the network throughput.Figs. 4.5-4.7 show the behavior of network throughput, delay, and false alarmerror as a function of SNR for different number of samples. Fig. 4.5 shows the falsealarm errors that maximize the network throughput. We obtained these values bynumerically evaluating (2.6), (2.7), and (4.10). It can be observed that for a fixednumber of samples, the optimum pf decreases as SNR increases, and for a fixed SNR,as number of samples increases, the optimal pf decreases. Fig. 4.6 plots the maxi-mum throughput achieved by using the optimal values of pf obtained from Fig. 4.5.The interesting observation is that the network throughput decreases as number ofsamples increases in low SNR regions. The reason is as follows. As we increment u,false alarm error decreases, while miss detection error decreases slightly and remainshigh, and results in an increase in the value of collision probability. Moreover, thenetwork throughput decreases as the slot time increases, and thus reduces the value43Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensing?10 ?8 ?6 ?4 ?2 0 2 4 6 8 1000.10.20.30.40.50.60.7SNR (dB)p f u = 2u = 3u = 4u = 5u = 6u = 7u = 8Figure 4.5: Optimum false alarm error versus SNR for different values of u.?10 ?8 ?6 ?4 ?2 0 2 4 6 8 100.40.50.60.70.80.91SNR (dB)? u = 2u = 3u = 4u = 5u = 6u = 7u = 8Figure 4.6: Maximum throughput as a function of SNR for different values of u.44Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensing?10 ?8 ?6 ?4 ?2 0 2 4 6 8 101234567SNR (dB)D(ms) u = 2u = 3u = 4u = 5u = 6u = 7u = 8Figure 4.7: Network delay versus SNR for different values of u.of throughput. Finally, Fig. 4.7 illustrates the effect of the throughput maximizationon the average packet delay. One can observe that for a fixed number of samples, asthe optimum value of pf decreases, the average delay increases.4.5 SummaryIn this chapter, we have extended the analysis of a contention-based MAC protocol,called selective tournaments, suitable for in-vehicle PLC, under carrier sensing errors.We have shown that the selective tournaments significantly outperforms CDR, thecontention-based MAC protocol proposed for in-vehicle PLC. We have obtained thenetwork throughput and delay as a function of physical layer sensing errors: falsealarm and miss detection. We have shown that the behavior of throughput dependson the false alarm and miss detection errors. We have also obtained the false alarm45Chapter 4. Time-Domain Contention Resolution Algorithm with Imperfect Carrier Sensingerrors that maximize the throughput using numerical methods in different scenarios,and showed the effect of those variables on the network delay.46Chapter 5Multi-channel ContentionResolution Algorithm withImperfect Carrier SensingIn the previous two chapters, we have introduced two random access protocols forV-PLC systems. The first protocol resolved the contention in the frequency-domain,and the second protocol resolved the contention using a robust CSMA-like approach.In this chapter, we introduce a new MAC protocol that uses a combination of thetechniques used in the previous two protocols to resolve the contention. We firstpresent our system model and give a brief description of the MAC protocol operationin Section 5.1. Section 5.2 provides mathematical analysis of the proposed MACprotocol, under the assumption of perfect sensing, whereas in Chapter 5.3, we presentthe mathematical analysis of the protocol with the presence of sensing errors. Wepresent numerical results in Section 5.4, and summarize in Section 5.5.5.1 System ModelWe consider a V-PLC network in which N nodes are connected to the harness. Timeis divided into a fixed-size transmission cycles, where multiple frequency channels canbe used by the senders or receivers. Despite the using of multiple channels, we assume47Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensingthat each node including the receiver, has only one antenna. We further assume allnodes in the V-PLC network are time synchronized. Fig. 5.1 depicts the structureof a single transmission cycle. First, the contention between senders is resolved onthe frequency domain where each sender, at the beginning of the transmission cycle,picks up a channel randomly. Then, if more than one sender select the same channel,the contention is resolved over number of slots by randomly perform one of the twofollowing actions in each slot: a carrier sense (cs) operation or a carrier transmission(ct) operation. At each time slot, the sender defers its transmission to the nexttransmission cycle if it senses the channel busy. But if the sender does not hear thecarrier, it stays on the contention. At the end of the last slot, the remaining senderstransmit a long preamble on their selected channel. After that the receiver startssampling the signal level on each channel starting with the channel 1, and if detectsany valid carriers, it locks on the channel and waits to receive the packet. Notethat the procedure performed on each channel is the contention resolution algorithmproposed in Chapter 4, and the channel selection algorithm is the same scheme asthe one introduced in Chapter 3.5.2 Performance Analysis under Perfect SensingConsider a system scenario, where at a given time, n nodes try to transmit packetsover the dc power line. We assume the value of n is not known to the nodes, but its1 32 4 k Packet ACK... ...1 2 3 MFrequency channelsContention slotsFigure 5.1: A view of a single transmission cycle.48Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensingprobability mass function is known to all nodes in the network, and can be expressedaspN(n) =1?(?)n? (5.1)where n ? {2, . . . , N}, N is the number of nodes connected to the dc-bus, and?(?) =?Nz=21z? , where ? is the shape parameter of the distribution.We are now ready to formulate the problem. Let p = (p1, p2, . . . , pM) be thechannel selection distribution, where pm is the probability that the m-th channel isselected by a sender. Assume the collision resolution algorithm uses k slots, and letq(m) be the probability vector of size?k?1i=0 2i = 2k?1, used to resolve the contentionon the m-th channel. Therefore, the probability vectors on all M channels can beexpressed with a matrix q = [q(1), q(2), . . . , q(M)]T . Suppose the number of senders inthe contention is n. A transmission cycle is successful if the contention is successfullyresolved in the first non-idle frequency channel, thus, the success probability is givenbypip(n) =M?m=1m?1?t=0(1? pt)nn?i=1(ni)(pm)i(1? pm)n?i?q(m)(i) (5.2)where p0 := 0, and ?q(m)(i) is the probability that the contention is successfullyresolved on the m-th channel when i nodes selected that channel. Averaging pip(n)over the distribution described in (5.1), the average success probability can be writtenaspip = E[pip(n)] =N?n=2pN(n)pip(n) (5.3)Furthermore, in order to calculate ?q(m) , we need to find the probability massfunction of the number of contending nodes on the m-th channel. For a given vector49Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensingp, this distribution can be expressed asp(m)N (l) =N?n=l(nl)(pm)l(1? pm)n?lpN (n) (5.4)where m ? {1, . . . ,M} and l ? {0, . . . , N}. We need to find the values in the vector pthat provide fast collision resolution. For this purpose, we have chosen the truncatedgeometric distribution used in the design of Sift protocol [16]. Sift is a randomizedcarrier sense multiple access- (CSMA-) based protocol for wireless sensor networks,where nodes use a truncated geometric distribution for selecting their contentionslots. Similarly, in our protocol, senders use this geometrically-increasing probabilitydistribution for picking their channels in the transmission cycle. Its expression form = 1, . . . ,M is given bypm =? mM ? ?m?1M? ? 1 (5.5)where ? is the parameter that needs to be carefully designed. Fig. 5.2 illustrates theimpact various values of ? have on the channel probabilities when M = 10 channelsare used. We have obtained these probabilities for three values of ?; ? = 10, ? = 100,and ? = 1000. It can be observed that the channel probabilities increase much fasteras ? increases.Now, we try to find the probability distribution p and matrix q that maximizethe success probability described in (5.3), i.e.,argmaxp,qpip (5.6)Algorithm 2 describes how we can calculate the optimal vector q(m) for the m-thchannel, given the distribution of contenders on the m-th channel, i.e., the value ofpm is assumed to be known. We have used the method proposed in [13] to minimize50Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensing1 2 3 4 5 6 7 8 9 1000.050.10.150.20.250.30.350.40.450.5Channel index (m)p m ? = 10? = 100? = 1000Figure 5.2: Channel selection probabilities when M = 10 channels are available formultiple choices of ?.the collision probability on the m-th channel, which finds the optimum solution byapproximating the collision probability with a Riemann integral. Using Algorithm 2and (5.5), the optimization problem in (5.6) can be solved by numerical methods [17].Suppose that the random variable T1 denotes the number of transmission cyclesrequired to successfully transmit the first packet. If there are n contenders, thenP(T1 = r) = pip(n)(1? pip(n))r?1 (5.7)where r ? {1, 2, . . . }, and pip(n) is the probability of success described in (5.2) whenthere are n contenders. Note that T1 describes the delay correspond to the firstpacket successfully transmitted to the receiver. By a similar argument, we find thedistribution of Tw, the number of transmission cycles needed to transmit w packets51Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier SensingAlgorithm 2 : Algorithm to maximize success probability on the m-th frequencychannel.1: Set u?(z) :=?g??(z) /* g?? (z) is the second derivative of g(z) = ?Nn=2 p(m)N (n)zn with respect to z */2: Initialization: Set b := 2k, B := 10b, and u0 := 03: for i = 1 to B do4: ui := ui?1 + u?( i? 12B)5: end for6: Set x0 := 0, and xb := 17: for t = 1 to b? 1 do8: xt = 1B min{i : uiuB?1 ?tb}9: end for10: Set q(m) := 1? x(b2)x(b)11: for L = 1 to k ? 1 do12: Set L := 2k?l?113: for j = 0 to 2l?1 do14: Convert j into l bits binary number c15: q(m)c :=x(2L(j+1))?x(L(2j+1))x(2L(j+1))?x(2Lj)16: end for17: end forto the destination. Let Xi denote the number of transmission cycles required totransmit the i-th packet, conditioned that the previous packets have been transmittedsuccessfully. Form (5.7), it is obvious that Xi has a geometric distribution withaverage 1?p(n?i+1) . We can express the random variable Tw asTw =w?i=1Xi (5.8)Thus, the expected value of Tw isE[Tw] =n?i=n?w+11pip(i)(5.9)with w ? {1, 2, . . . , n}. The normalized throughput under consideration in this paperis defined as a fraction of time the network is used to successfully transmit packets.52Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier SensingWe define the throughput correspond to the w-th received packet as the ratio?w(n) =w?dE[Tw]?cycle(5.10)with the transmission cycle duration is defined as ?cycle = k?s + M?c + ?d, where?s represents the amount of time required by a node to determine the presence ofthe carrier on a frequency channel, ?c is the time duration needed by the receiverto sample a frequency channel and switch to the next channel, and ?d specifies theamount of time needed for transmitting a packet and receiving an ACK.5.3 Performance Analysis under the Presence ofSensing ErrorsSuppose there are N nodes connected to the dc power line network and the num-ber of nodes with packets follows the distribution described in (5.1). Furthermore,assume that sensing is not perfect, and there are sensing errors due to the channelimpairments. Let p(m)fa and p(m)md denote the false alarm and miss-detection probabili-ties for senders on the m-th channel, respectively. Similarly, we define q(m)fa and q(m)mdas the probabilities of false alarm and miss-detection related to the receiver on them-th channel, respectively. We also use the signal detector introduced in Chapter2 for signal detection. Next, we calculate the success probability when there are ncontenders. Assume m is the channel selected by at least one node. We say thatthe contention is successfully resolved on the m-th channel if and only if: (i) onlyone node remains on the m-th channel after the completion of the collision resolutionprotocol. (ii) the receiver is able to correctly determine the states of the first m53Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensingchannels. Hence, the success probability can be expressed aspip(n) =M?m=1(1? q(m)md )m?1?t=0(1? pt)n(1? q(t)fa)n?i=1(ni)(pm)i(1? pm)n?i?q(m)(i, p(m)fa , p(m)md )(5.11)where p0 := 0, p(0)fa := 0, and the expected value of success probability is expressedby (5.3).Next, we derive the success probability, ?q(m) , on the m-th channel when sensingis not perfect. We define the probability generating function (PGF) of the numberof contending nodes on the m-th channel asg(m)(z) := E(zn) =N?n=0p(m)N (n) zn (5.12)We are now able to find the PGF of the number of contenders still in the competitionafter the elapse of one time slot. For simplicity of computation, we assume that, byusing the preprocessor suggested in Chapter 2, all nodes in the competition experiencethe same average SNR and therefore, we can use binomial distribution to denote theprobability that i out of n nodes estimated the channel state correctly. Because thisPGF depends on the number of nodes who selected ct operation in the previous slot,we derive its expression for the following cases:? Case 1: If no carrier has been emitted in the first slot, then a node moves to thesecond slot if it senses the channel idle, which happens with probability 1?pfa.54Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier SensingThe PGF denoted as g(m)0 , is given asg(m)0 (z) =N?n=0p(m)N (n)(1? q(m))nn?i=0(ni)(1? p(m)fa)i (p(m)fa)n?izi=N?n=0p(m)N (n)(1? q(m))n ((1? p(m)fa)z + p(m)fa)n= g(m)((1? q(m))z(m)fa)(5.13)where z(m)fa :=(1? p(m)fa)z + p(m)fa , q(m) is the probability of transmitting acarrier in the first time slot, and p(m)fa is the false alarm probability on the m-thchannel given in (2.7).? Case 2: In this case, we consider scenarios where at least one node has emitteda carrier in the previous slot. All nodes in the contention that have emitteda carrier in the first slot survive and move to the second time slot. However,nodes that have sensed the channel busy, which happens with probability 1?pmdwill retire from contention. Others that have miss-detected the carrier on thechannel, will continue the contention. Therefore, the expression for its PGF,g(m)1 , is expressed byg(m)1 (z) =N?n=1p(m)N (n)n?i=1(ni)(q(m))i (1? q(m))n?i zin?i?j=0(n? ij)(p(m)md)j (1? p(m)md)n?i?jzj= g(m)(q(m)z + (1? q(m))z(m)md)? g(m)((1? q(m))z(m)md)(5.14)where z(m)md := p(m)md z + 1 ? p(m)md , and p(m)md is the miss detection probability onthe m-th channel defined in (2.6).55Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier SensingLet c = [c1 . . . ci . . . ct] be an t-bit binary number that shows the operations performedby a sender in each slot, where ci = 0 or 1 denotes the events of choosing cs and ctin the i-th slot, respectively. We are now able to find the PGF of the nodes in thecontention after the elapse of t+1 slots. Following mathematical induction and using(5.13) and (5.14), we haveg(m)c0 (z) = g(m)c((1? q(m)c )z(m)fa)(5.15)andg(m)c1 (z) = g(m)c(q(m)c z + (1? q(m)c )z(m)md)? g(m)c((1? q(m)c)z(m)md)(5.16)where q(m)c is the probability that, in slot t + 1, nodes emit a carrier on the m-thchannel, given the signaling pattern c in the first t slots, g(m)c is the PGF of survivors,when the signaling pattern in the first t slots is c, and g(m)? := g(m). Hence, the PGFof the number of contenders on the m-th channel after k slots is ?c?Ckg(m)c (z), whereCk denotes the set of all binary numbers of length k from the alphabet {0, 1}. So thedistribution of survivors is given byPr {n nodes remain on the m-th channel} = 1n!dndzn?c?Ckg(m)c (z)|z=0 (5.17)where n denotes the number of survivors at the end of the contention. The successprobability, which is defined as the probability that at the end of the contention onlyone survivor remains, is given as?q(m) =ddz?c?Ckg(m)c (z)|z=0 (5.18)56Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensing5.4 Numerical ResultsIn this section, we present numerical results obtained by evaluating the expressionsderived in Sections 5.2 and 5.3 to illustrate the performance of the proposed protocol.Throughout this section we assume the number of nodes connected to the dc powerline, N , is 50, and the shape parameter of the distribution in (5.1) is set to 0.6,unless specified otherwise. The reason behind choosing ? = 0.6 is that the systemwill perform well in both high and low traffic loads as shown in Fig. 5.3. Here, thereare N = 50 nodes connected to the harness, and the system uses M = 2 channels andk = 6 slots to resolve the contention between nodes. It can be noted that the systemwith ? = 0 (uniform distribution) performs well when the number of contenders islarge, whereas the system with ? = 1 gives a better performance when the number ofcontending nodes is small, and the system with ? = 0.6 provides a good performancein both cases. Our experiments confirm that ? = 0.6 provides a balanced performancefor other configurations as well, i.e., different values of M and k.Figs. 5.4 and 5.5 show the success probability and the system throughput asthe number of channels varies between 2 and 8 for different number of contentionslots, respectively. To evaluate the effects of the number of frequency channels andcontention slots on the system throughput, we define a ratio between time constantsin each transmission cycle as r := ?s?d =?c?d . Here, we considered that ?s = ?c,however, the case of ?s 6= ?c can be easily included in the numerical evaluations aswell. Expectedly, as can be observed in Fig. 5.4, with an increase in the numberof contention slots or frequency channels, the success probability of the protocolincreases. However, as the number of contention slots increases, the gain of usingmultiple frequency channels decreases since the protocol is capable of resolving thecontention on each channel with a high probability. In Fig. 5.5, we assume that the57Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensing1 5 10 15 20 25 30 35 40 45 500.940.950.960.970.980.991Number of contending nodes (n)Successprobability(pip(n)) ? = 1? = 0.6? = 0Figure 5.3: Success probability versus number of contending nodes for different valuesof ?, N = 50, k = 6, M = 2.packet size is relatively large, and therefore r = 160 . Each point describes the expectedthroughput computed as?Nn=2 pN(n)?1(n), and the maximum point along each curveis specified with a marker. We can observe that, as the number of contention slotsincreases, the maximum point along each curve moves to the left and thus, occurs ata smaller number of channels. It can also be seen that adding a channel to the systemdoes not improve the system performance when number of contention slots used inthe system is high. The reason behind this behavior is that the system with large kcan handle a wide range of traffic loads, and therefore the success probability will notimprove much by separating contenders across more channels. On the other hand,adding one channel will increase the packet overhead and thus, could potentiallydegrade the system performance.Fig. 5.6 shows the average success probability of the system as a function of thenetwork size. The protocol operational parameters (k,M) are set to the values give58Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensing2 3 4 5 6 7 80.70.750.80.850.90.951Number of channels (M)Successprobability(pip) k = 2k = 3k = 4k = 5k = 6Figure 5.4: Average success probability versus number of channels for different num-ber of time slots (k), N = 50, ? = 0.6.2 3 4 5 6 7 80.650.70.750.80.850.9Number of channels (M)? 1 k increasesk = 2Figure 5.5: ?1 versus number of channels for different number of time slots (k),N = 50, ? = 0.6.59Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensing5 10 20 30 40 50 60 70 80 90 100 110 1200.880.90.920.940.960.981Total number of nodes (N)Successprobability(pip) (k = 2, M = 7) (3,5) (4,3) (5,2) (6,2)Figure 5.6: The average success probability versus total number of nodes connectedto the harness (N), ? = 0.6.the maximum throughput as shown in Fig. 5.5. It could be noticed that the systemshows the least performance degradation when k = 6 and M = 2. The reason is thatas we increase the number of contention slots in each channel, the collision resolutionalgorithm performed on each channel is more capable of resolving the contention ina wide range of traffic loads, and also less sensitive to the number of contenderscompared to the channel selection algorithm.In Figs. 5.7-5.10, we report the probability mass functions of the number of trans-mission cycles required to transmit the first and all packets, when there are 25 and5 contenders. We assume there are k = 4 slots available on each channel to resolvethe contention, and the system uses M = 3 channels as according to Fig. 5.5, thisconfiguration provides the highest throughput when k = 4. We have plotted thesesdistributions by using (5.8), and the results obtained by solving the optimizationproblem given in (5.6). The figures show that the protocol delivers the packets with60Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensing1 2 3 4 500.10.20.30.40.50.60.70.80.91Transmission cycle number (l)Pr(T 1=l)Figure 5.7: Probability mass function of the number of transmission cycles requiredto transmit the first packet when there are 25 contenders, N = 50, ? = 0.6, k = 4,M = 3.20 25 30 35 4000.050.10.150.20.250.30.35Transmission cycle number (l)Pr(T 25=l)Figure 5.8: Probability mass function of the number of transmission cycles requiredto transmit all packets when there are 25 contenders, N = 50, ? = 0.6, k = 4, M = 3.61Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensing1 2 3 4 5 600.10.20.30.40.50.60.70.80.91Transmission cycle number (l)Pr(T 1=l)Figure 5.9: Probability mass function of the number of transmission cycles requiredto transmit the first packet when there are 5 contenders, N = 50, ? = 0.6, k = 4,M = 3.5 10 1500.10.20.30.40.50.60.70.8Transmission cycle number (l)Pr(T 5=l)Figure 5.10: Probability mass function of the number of transmission cycles requiredto transmit all packets when there are 5 contenders, N = 50, ? = 0.6, k = 4, M = 3.62Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensing2 5 10 15 20 25 30 35 40 45 5000.10.20.30.40.50.60.70.80.91Number of contending nodes (n)Successprobability RAR size = 5RAR size = 7RAR size = 9Proposedprotocol k = 2k is increased by twoCDR protocolFigure 5.11: Success probability of the proposed protocol and CDR versus numberof contending nodes, M = 3, N = 50, ? = 0.6.small latency and also scales well with respect to the number of contenders.Fig. 5.11 gives a success probability comparison between our proposed MAC pro-tocol and CDR [1], when the number of contending nodes varies between 2 and 50.To make a fair comparison, we note that adding one channel or slot to our systemincreases the packet overhead by the same amount as adding one slot to the CDRprotocol. The number of channels, in our system, is fixed to 3. We would like toremark that the parameters used in our protocol are calculated by solving the opti-mization problem in (5.6) with the distribution in (5.1), when N = 50 and ? = 0.6an thus, the protocol does not need to know about the number of contenders. It canbe observed that our protocol performs much better in all scenarios, and its perfor-mance drops out at a much lower rate compared to CDR as we increase the numberof contending nodes.The effect of sensing errors on the average success probability is depicted in63Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensing10?210?110?210?10.750.80.850.90.95p(2)fap(1)faSuccessprobability(pip)Figure 5.12: The average success probability versus false alarm errors, N = 50,? = 0.6, k = 6, M = 2, u = 10.2 5 10 15 20 25 30 35 40 45 500.750.80.850.90.951Number of contending nodes (n)Successprobability r = 160r = 120r = 320Figure 5.13: Success probability versus number of contending nodes for multiplevalues of r, where good channel is indexed 1, k = 6, M = 2, N = 50, ? = 0.6.64Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier Sensing2 5 10 15 20 25 30 35 40 45 500.650.70.750.80.850.90.951Number of contending nodes (n)Successprobability r = 160r = 120r = 320Figure 5.14: Success probability versus number of contending nodes for multiplevalues of r, where bad channel is indexed 1, k = 6, M = 2, N = 50, ? = 0.6.Fig. 5.12. We consider the scenario where k = 6 slots and M = 2 channels areused in the system as it provides a high throughput according to the Fig. 5.5. Thevalues of SNRs are set between -5dB to 5dB, and are chosen randomly in each chan-nel. Note that each point in the figure represents the average probability of successas in (5.3), and is averaged over 1,000 runs. We also assume that the sensing moduletakes 20 samples to determine the presence or absence of the carrier. As can be seen,the success probability is sensitive to the false alarm errors on both channels, andthere is an optimal point which maximizes the success probability. Next, we designa robust system by considering the carrier sensing errors. We plot the results forthree cases correspond to r = 160 , 120 , 320 . Note that in all cases the packet length isfixed, and instead the number of samples taken from the received signal changes.There are M = 2 channels available in the system for contention, and assume theSNRs correspond to these channels are 5dB (good channel) and 0dB (bad channel).65Chapter 5. Multi-channel Contention Resolution Algorithm with Imperfect Carrier SensingFigs. 5.13-5.14 show the systems where the detector operating point is optimized oneach channel with respect to the physical layer characteristics, and are correspond tothe cases where the good channel is indexed as the first channel and vice versa, re-spectively. We can make the following observation. The success probability decreaseswhen the bad channel is indexed 1. This happens since, according to (5.5), the re-ceiver will receive the packet from the low-indexed channels with high probability,and a low SNR on the selected channel can degrade the performance of the collisionresolution algorithm performed on that channel. Hence, we can shuffle the order ofthe channels in each transmission cycle to reduce the impact of the noise and fadingon the MAC protocol performance.5.5 SummaryIn this chapter, we have introduced a random access MAC protocol based on thecombination of time and frequency multiplexing. Nodes in the contention randomlyselect a frequency channel to perform channel contention in a number of slots. Afterthat, the receiver samples the signal level on each frequency channel and stops onthe first non-idle channel to receive the packet. We mathematically analyzed theperformance of the proposed MAC protocol under both perfect and imperfect sens-ing. With numerical evaluations, we have verified our analysis and demonstrate theeffectiveness of our MAC protocol. Our results show that the system demonstratesa good performance in terms of collision probability, system throughput, and delay.In this work, we have also considered that the system is not free from carrier sensingerrors, and we have observed that a great care must be taken into account whendesigning such a system.66Chapter 6Conclusions and Future WorkIn this chapter, we first summarize the results and highlight the contributions of thisthesis. Then, we propose possible future research directions.6.1 Summary of ContributionsIn this thesis, we focused on PLC systems employing carrier-sense-based MAC pro-tocols for in-vehicle networks. Three contention-based MAC protocols were proposedand their performances were analyzed under imperfect carrier sensing. We then ob-tained optimum carrier sensing parameters to improve the MAC layer performance.In the following, we summarize the main contributions of the thesis.? In Chapter 3, we have introduced a multi-carrier MAC protocol for in-vehiclePLC networks. The protocol employs a combination of time and frequencymultiplexing to resolve the contention between nodes. We addressed physicallayer related carrier sensing errors, i.e., false alarm and miss detection, andobtained the probability of successful transmission and time utilization as afunction of these errors. To maximize the probability of successful transmission,we proposed a cross-layer approach where the average signal?to?noise ratio andsampling rate in each subcarrier were included in calculating the probabilitydistribution that nodes use to randomly select subcarriers, and carrier sensingthreshold that is being employed in each subcarrier.67Chapter 6. Conclusions and Future Work? In Chapter 4, we have studied the effect of carrier sensing errors on the per-formance of a contention-based MAC protocol, called selective tournaments,well suited for in-vehicle power line communication. We obtained the networkthroughput and delay as a function of carrier sensing errors. Finally, numericalresults were presented to demonstrate the sensitivity of the network throughputand delay with respect to the carrier sensing threshold.? In Chapter 5, we have introduced a random access protocol, which consists oftwo key features: (i) a distributed channel selection policy that arbitrates packettransmission across different channels, and also provides robustness against in-terference and noise and (ii) a distributed collision resolution algorithm thatallows each node to compete for the use of its selected channel. We have ob-tained the protocol-operational parameters that reduce the collision probabilityamong senders. In addition, we have considered the impact of sensing errors onthe performance of the proposed protocol, and analyzed the performance of theproposed protocol under the presence of sensing errors. We demonstrated theimpact of the selection of the protocol parameters in determining the perfor-mance of the proposed protocol, and provided useful guidelines for developinga robust contention-based protocol for vehicular power line communication sys-tems.6.2 Suggestions for Future WorkIn the following, we propose several interesting future research directions that arebased on the work in this thesis.68Chapter 6. Conclusions and Future Work1. Developing a discrete-event simulator for the MAC layer of in-vehiclePLC network. In this thesis, we have introduced and analyzed three MACprotocols for collision resolution in automotive environments. It is interestingto evaluate the performance of these protocols via simulations of the PHY andMAC layers. By doing this, we can also investigate the impact of carrier sensingerrors on the performance of the MAC layer more accurately.2. Estimation of impulsive noise parameters using neural networks. InChapter 2, we introduced a simple impulse filter to mitigate the impulsive noisecomponents from received signal. It is also possible to model the in-vehiclePLC noise with a Partitioned Markov Chain (PMC) [15]. One possible futureresearch direction is to estimate the parameters of the PMC with a neuralnetwork. By doing so, it is possible to design a more robust communicationsystem for in-vehicle PLC.69Bibliography[1] O. Amrani and A. Rubin, ?Contention detection and resolution for multiple-access power-line communications,? IEEE Trans. Veh. Technol., vol. 56, no.6, pp. 3879-3887, Nov. 2007.[2] E. Bassi, F. Benzi, L. Almeida, and T. Nolte, ?Powerline communication inelectric vehicles,? in Proc. IEMDC 2009, May 2009, pp. 1749-1753.[3] Y. Maryanka, ?Wiring reduction by battery power line communication,? inProc. IEE Seminar on Passenger Car Electrical Architecture, Jun. 2000, pp.8/1-8/4.[4] M. Mohammadi, L. Lampe, M. Lok, M. Mirvakili, R. Rosales, and P. van Veen,?Measurement and transmission for in-vehicle power line communication,? inProc. IEEE ISPLC 2009, Dresden, Germany, Apr. 2009, pp. 73-78.[5] M. Lienard, M. O. Carrion, V. Degardin, and P. Degauque, ?Modeling andanalysis of in-vehicle power line communication channels,? IEEE Trans. onVeh. Technol., vol. 57, no. 2, pp. 670-679, Mar. 2008.[6] Y. Yabuuchi, D. Umehara, M. Morikura, T. Hisada, S. Ishiko, and S. Horihata,?Measurement and analysis of impulsive noise on in-vehicle power lines,? inProc. ISPLC 2010, Copacabana Rio de Janeiro, Brazil, Mar. 2010, pp. 325-330.[7] V. Degardin, M. Lienard, P. Degauque, E. Simon, and P. Laly, ?Impulsive noisecharacterization of in-vehicle power line channels,? IEEE Trans. Electromagn.Compat., vol. 50, no. 4, pp. 861-868, Nov. 2008.[8] V. Degardin, M. Lienard, P. Degauque, and P. Laly, ?Performances of thehomeplug PHY layer in the context of in-vehicle powerline communications,?in Proc. IEEE ISPLC 2007, Pisa, Italy, Mar. 2007, pp. 93-97.[9] H. Urkowitz, ?Energy detection of unknown deterministic signals,? Proc. IEEE,vol. 55, pp. 523-531, April 1967.[10] H. Poor, An Introduction to Signal Detection and Estimation, 2Ed. New York:Springer-Verlag, 1994.70Bibliography[11] A. J. Efron and H. Jeen, ?Detection in impulsive noise based on robust whiten-ing,? IEEE Trans. Signal Processing, vol. 42, pp. 1572-1573, June 1994.[12] V. Namboodiri and A. Keshavarzian, ?Alert: an adaptive low-latency event-driven MAC protocol for wireless sensor networks,? in Proc. IPSN2008, St.Louis, Missouri, USA, pp. 159-170.[13] J. Galtier, ?Tournament methods for WLAN: analysis and efficiency,? Graphsand Algorithms in Communication Networks (Springer), pp. 379-400, 2010.[14] ISO 11898-1:2003, ?Road vehicles?Controller Area Network (CAN)?Part 1:Data link layer and physical signaling,? ISO International Standard, 2003.[15] B. D. Fritchman, ?A binary channel characterization using partitioned Markovchains,? IEEE Trans. Inform. Theory, vol. 13, no. 2, pp. 221-227, Apr. 1967.[16] K. Jamieson, H. Balakrishnan, and Y. Tay, ?Sift: A MAC protocol for event-driven wireless sensor networks,? in Proc. EWSN 2006, Zurich, Switzerland,Feb. 2006, pp. 260-275.[17] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge, U.K.: Cam-bridge University Press, 2004.[18] CAN Specification, Version 2.0, Stuttgart, 1991, R. Bosch GmBh, Std.[19] A. Schiffer, ?Statistical channel and noise modeling of vehicular DC-lines fordata communication,? in Proc. IEEE VTC 2000-Spring, Tokyo, Japan, May2000, pp. 158-162.[20] N. Taherinejad, R. Rosales, L. Lampe, and S. Mirabbasi, ?Channel character-ization for power line communication in a hybrid electric vehicle,? in Proc.ISPLC 2012, Beijing, China, Mar. 2012, pp. 328-333.[21] J.W. Chong, D.K. Sung, and Y. Sung, ?Cross-layer performance analysis forCSMA/CA protocols: impact of imperfect sensing,? IEEE Trans. on Veh. Tech-nol., vol. 59, no. 3, pp. 1100-1108, Mar. 2010.[22] D. Fertonani and G. Colavolpe, ?On reliable communications over channelsimpaired by bursty impulse noise,? in Proc. ISPLC2008, Jeju Island, Korea,April 2008, pp. 357-362.[23] M. Abramowitz and I. A. Stegun, Eds., Handbook of Mathematical Functionswith Formulas, Graphs, and Mathematical Tables., National Bureau of Stan-dards Applied Mathematics Series 55, Washington, D. C.: U. S. GovernmentPrinting Office, 1964.71Bibliography[24] N. Navet, Y. Song, F. Simonot-Lion, and C. Wilwert, ?Trends in automotivecommunication systems,? inProc. IEEE, vol. 93, no. 6, pp. 1204-1224, Jun.2005.[25] T. Benzi, T. Facchinetti, T. Nolte, and L. Almeida, ?Towards the power line al-ternative in automotive applications?, inProc. WFCS2008, Dresden, Germany,May 2008, pp. 259-262.72Appendix AProbability Generating FunctionsWe will briefly introduce the definitions and notations related to probability gener-ating functions. Generating functions provide a technique for dealing with sum ofindependent random variables. Let X be a discrete random variable taking valuesin the non-negative integers {0, 1, 2, . . .} with P (X = j) = pj . Upper case lettersdenote a random variable, while lower case letters denote a realization.DefinitionThe probability generating function of the random variable X defined over non-negative integers, is given by the polynomialG(z) = p0 + p1z + p2z2 + ? ? ? =??j=0pjzj = E(zX) (A.1)An important property of a probability generating function is that it converges for|s| ? 1 since G(1) =??j=0 pj = 1. The probability generating function can be usedto derive the probability of the random variable, as well as its moments asP (X = j) = pj =1j!djG(z)dzj (A.2)73
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Medium access control protocol design for in-vehicle...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Medium access control protocol design for in-vehicle power line communication Kenarsari Anhari, Amir 2013
pdf
Page Metadata
Item Metadata
Title | Medium access control protocol design for in-vehicle power line communication |
Creator |
Kenarsari Anhari, Amir |
Publisher | University of British Columbia |
Date Issued | 2013 |
Description | Nowadays, the number of electronic devices in vehicles grows at an exponential rate. For the purpose of communication between these components, several standardized communication protocols such as controller area network (CAN), local interconnect network (LIN), and FlexRay have been developed and are used in vehicles. However, the use of additional wires for data communication still results in a significant increase in the complexity, volume, weight, and cost of wiring harness. Vehicular power line communication (V-PLC) is an interesting alternative that offers numerous advantages. This technology reuses the existing direct current (DC) power network in vehicles as the physical medium for data transmission and allows eliminating some of the wiring harnesses devoted to convey data signals. Hence, This technology can potentially reduce the vehicle cost, weight, and fuel consumption. However, to provide reliable communication over power lines, several challenges need to be addressed. These include impulsive noise produced by electrical devices connected to the bus and frequency-selective behavior of the power line channels introduced by impedance mismatches in the wiring harness. In this thesis, we study research challenges for the medium access control (MAC) protocol design of V-PLC networks. We propose MAC protocols for such systems, which provide fast collision resolution, and perform performance evaluations on these protocols in terms of collision probability, system throughput, and packet delay. Our results show that these protocols outperform the previously proposed protocol, contention detection and resolution (CDR) in all scenarios. We then investigate the effect of carrier sensing errors on the performance of the proposed MAC protocols. We start with addressing the problem of detection of unknown signals in impulsive noise by using a robust detector, which first removes the impulses from the signal and then performs linear signal detection on the cleaned samples. We obtain the network throughput and delay of the proposed protocols as a function of carrier sensing errors. We then suggest a framework for the optimal joint design of the physical layer signal detector and MAC layer protocol. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2013-10-25 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0103289 |
URI | http://hdl.handle.net/2429/45394 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2013-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2013_fall_kenarsarianhari_amir.pdf [ 592.36kB ]
- Metadata
- JSON: 24-1.0103289.json
- JSON-LD: 24-1.0103289-ld.json
- RDF/XML (Pretty): 24-1.0103289-rdf.xml
- RDF/JSON: 24-1.0103289-rdf.json
- Turtle: 24-1.0103289-turtle.txt
- N-Triples: 24-1.0103289-rdf-ntriples.txt
- Original Record: 24-1.0103289-source.json
- Full Text
- 24-1.0103289-fulltext.txt
- Citation
- 24-1.0103289.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0103289/manifest