Delay, Reliability, and Trust in Information Dissemination in VehicularNetworksbyKarim RostamzadehB.Sc., Isfahan University of Technology, 2006M.Sc., Isfahan University of Technology, 2008A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)July 2015c© Karim Rostamzadeh, 2015AbstractThe cost of road accidents globally is more than $500 B every year. Intelligent Transporta-tion Systems (ITS) is a promising solution and Vehicular Networks is an ideal candidate forproviding a communication platform for ITS applications. Safety-critical applications formthe main motivation for intelligent transportation systems. Studying the major concernsin such applications, i.e., delay and reliability, through mathematical analysis is extremelybeneficial because it enables us to design optimized schemes. Such analysis is, however,challenging due to the dynamics of a vehicular network.In this research, we have three main contributions. First, we present a mathematicalmodel to study delay and reliability of emergency message dissemination in vehicular net-works. This model includes three modules to address effects of channel, contention, andpartitioning on delivery delay. This is the first delay model to the best of our knowledgethat does all of these, and it gives network architects insight into the limitations of thenetwork and helps them tune parameters such as transmission power and slot time dura-tion. Simulation studies indicate that our model does capture the delay characteristics ofvehicular networks for both highway and urban scenarios.An interesting observation from the analytical model confirms the fact that using thevehicle density on the road is a good metric for setting the right forwarding probabil-ity in vehicles. We exploit this conclusion and as our second contribution, we proposea completely distributed forwarding strategy, called Middle Is Next or MIN. Extensivesimulations affirm the effectiveness of MIN in terms of delay and single-hop reliability iniiAbstractcomparison with other well-known routing methods.Trusted communication in vehicular networks is of crucial importance without whichall efforts for minimizing the delay or maximizing the reliability could be voided. As ourthird contribution, we propose FACT: Framework for Application-oriented Context-awareTrust-based communication in vehicular networks. FACT assigns a trust value to eachroad segment and one to each neighbourhood, instead of each car. Thus, it scales up easilyand is completely distributed. Experimental results demonstrate that FACT outperformsother well-known routing protocols since it routes the messages via trusted paths.iiiPrefaceHereby, I declare that Chapters 2-4 encompass work that has been published in papers thatare co-authored by Dr. Sathish Gopalakrishnan who supervised me through this research.Chapter 4 includes published and to-be-published work co-authored by Hasen Nicanfar,Narjes Torabi, and Dr. Victor C.M. Leung. Hasen and Narjes helped me in simulationverification and proof-reading. The following publications are accomplished through thisresearch.Journal Papers, Published• Rostamzadeh, K. and Gopalakrishnan, S.;, “Analysis of Message Dissemination inVehicular Networks,” IEEE Transactions on Vehicular Technology, vol. 62, issue 8,pp. 3974-3982, Oct. 2013 [Impact factor: 2.64].Journal Papers, Accepted for Publications• Rostamzadeh, K.; Nicanfar, H.; Torabi, N.; Gopalakrishnan, S.; Leung, V.;, “AContext-aware Trust-based Information Dissemination Framework for Vehicular Net-works,” IEEE Internet of Things Journal, Nov. 2014.• Rostamzadeh, K. and Gopalakrishnan, S.;, “Analysis of Message Delivery Delay inVehicular Networks,” IEEE Transactions on Vehicular Technology, Aug. 2014 [Im-pact factor: 2.64].ivPreface• Narjes Torabi, Karim Rostamzadeh, Victor C.M. Leung, “IEEE 802.15.4 BeaconingStrategy and the Coexistence Problem in ISM Band,” IEEE Transactions on SmartGrid, July 2014 [Impact factor: 4.33].Conference Papers, Published• Rostamzadeh, K.; Nicanfar, H.; Gopalakrishnan, S.; Leung, V.;, “A Context-awareTrust-based Communication Framework for VNets,” in Proc. of IEEE Wireless Com-munications and Networking Conference (WCNC), pp. 3296-3301, April 2014.• Narjes Torabi, Karim Rostamzadeh, Victor C.M. Leung, “Rank-Optimal ChannelSelection Strategy in Cognitive Networks,”in Proc. of IEEE Global CommunicationsConference (Globecom), Anaheim, California, December 2012.• Dahr, D.; Gopalakrishnan, S.; Rostamzadeh, K.;, “Optimal Sensing Using QueryArrival Distributions,” in Proc. of ACM DIVANet, pp. 39-46, October 2012.• Rostamzadeh, K. and Gopalakrishnan, S.;, “Analysis of Emergency Message Dis-semination in Vehicular Networks,” in Proc. of IEEE Wireless Communications andNetworking Conference (WCNC), pp. 575-580, March 2011.• Rostamzadeh, K. and Gopalakrishnan, S.;, “On Bounding Information DisseminationDelays in Vehicular Networks,” in Proc. of IEEE Consumer Communications andNetworking Conference(CCNC)’s Workshop, pp. 70-74, January 2011.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Research Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3 Organization of this Dissertation . . . . . . . . . . . . . . . . . . . . . . . . 102 Analysis of Message Dissemination in Vehicular Networks . . . . . . . . 122.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13viTable of Contents2.3 Theoretical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3.2 Reliability-Delay Analysis . . . . . . . . . . . . . . . . . . . . . . . . 162.3.3 PD Transition Speed with Respect to k . . . . . . . . . . . . . . . . 192.4 The Effect of q on Reliability-Delay Model . . . . . . . . . . . . . . . . . . 222.4.1 Physical Layer Modeling . . . . . . . . . . . . . . . . . . . . . . . . . 232.5 An Efficient Forwarding Policy . . . . . . . . . . . . . . . . . . . . . . . . . 292.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 Analysis of Message Delivery Delay in Vehicular Networks . . . . . . . 393.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.3 MAC Layer Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.3.2 Mathematical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 443.4 Partitioning Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.5.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.5.2 Delay and Reliability in Highway Scenario . . . . . . . . . . . . . . . 573.5.3 Delay and Reliability in Urban Scenario . . . . . . . . . . . . . . . . 583.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604 A Trust-based Information Dissemination Framework for Vehicular Net-works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64viiTable of Contents4.3 The Proposed Trust Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.3.1 Trust Calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714.4 FACT Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744.4.1 Admission Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764.4.2 Dissemination Module . . . . . . . . . . . . . . . . . . . . . . . . . . 804.5 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824.5.1 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834.5.2 Comparison Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 874.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 894.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . 945.1 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . 96Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100viiiList of Tables2.1 Configuration Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.1 Configuration Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.1 Comparing the features of the surveyed proposals in Section 4.2 and our proposal 874.2 Configuration Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90ixList of Figures2.1 A warning dissemination scenario due to an accident. Arrows represent suc-cessful transmissions between neighbour vehicles. . . . . . . . . . . . . . . 162.2 End-to-end delivery probability vs. number of transmission rounds for λs =52(veh/km), q = 0.8 and Pf = 0.6. . . . . . . . . . . . . . . . . . . . . . . 182.3 Minimum number of transmissions we need for at least 90% reliability vs. λsand Pf for q = 0.8 and d = 2000m. . . . . . . . . . . . . . . . . . . . . . . 192.4 BCi vs. distance for r = 200 and two different λs. . . . . . . . . . . . . . . . 312.5 End-to-end delivery probability vs. number of transmission rounds: simula-tion vs. numerical results for λs = 40(veh/km), q = 0.9 and Pf = 0.7. . . . 342.6 Minimum number of transmissions we need for at least 90% end-to-end reli-ability vs. λs: simulation vs. numerical results for q = 0.9 and Pf = 0.7. . . 352.7 Single-hop reliability vs. success rate, for d = 2000m. . . . . . . . . . . . . . 362.8 Average delivery delay varying number of cars, for d = 2000m. . . . . . . . . 373.1 A safety warning dissemination example. Arrows represent successful trans-missions between neighbours and dashed arcs are transmission ranges of thetransmitters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.2 Average delay for delivery to the distance of d = 2000 m. . . . . . . . . . . . 473.3 Forwarding probability of MIN in order to achieve delayF = simulation delay±5%. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48xList of Figures3.4 The histogram and the exponential fit for the carry phase. . . . . . . . . . . 503.5 The histogram and the exponential fit for the forward phase. . . . . . . . . . 513.6 The histogram and the exponential fit for the total case. . . . . . . . . . . . 523.7 The two-state Markov chain for modelling the information propagation in apartitioned vehicular network. . . . . . . . . . . . . . . . . . . . . . . . . . 523.8 Average delivery delay in the highway scenario for d = 3000 m. . . . . . . . 583.9 Packet delivery ratio in the highway scenario for λs = 20 veh/km and d = 3000m. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593.10 Average delivery delay in the urban scenario. . . . . . . . . . . . . . . . . . 603.11 Average delivery delay in the urban scenario when there are fewer intersections. 613.12 Packet delivery ratio in the urban scenario for 72 vehicles. . . . . . . . . . . 614.1 Right: map of the city divided to different neighbourhoods. Left: each neigh-bourhood consists of different road segments. . . . . . . . . . . . . . . . . . 694.2 FACT’s framework and how modules function and communicate to each other. 754.3 An example for distance calculation in the carry phase to find tc(d). . . . . . 774.4 Delivery delay vs. different vehicle densities for 90% reliability. . . . . . . . . 914.5 Number of times the source retransmits its message because of the packetdrops by malicious nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 914.6 Packet delivery ratio vs. delivery delay. . . . . . . . . . . . . . . . . . . . . . 924.7 Delivery delay vs. different average vehicle speeds for 90% reliability. . . . . 924.8 FACT packet delivery ratio vs. delivery delay for different average speeds. . 93xiList of NotationsBCi Back-off counter of car iBC Average back-off counterd Area of relevance’s radiusdelayC Delay in Carry statedelayF Delay in Forward statedelayT Total average delivery delayDk Distance covered by k transmittersI0 Modified Bessel function of first kind and zero orderK Rician K-factorkmin Minimum required number of transmissions to achieve PminLcar Average length of a carLi Distance between (i− 1)th and ith transmittersλ Poisson distribution parameter for Mλs Exponential distribution parameter for xM Number of transmitters up to d(1/2)µ2 Power of dominant componentN Maximum number of cars in rtNf Number of times a message stays in Forward statep Instantaneous signal powerxiiList of NotationsPD End-to-end reliabilityPf Forwarding probabilitypi Total interference powerPmin Minimum acceptable value for PDP¯r Average received powerps Power of desired messageP¯t Average transmitted powerq Success rater/rt Transmission rangeσ2 Average scattered powerSIR Signal to interference ratiox/X Inter-vehicle distancexd Desired distancexij Distance from jth interfering carzi Distance of car i from transmitterxiiiList of AbbreviationsAI Artificial IntelligenceBC Back-off CounterBS Base StationCDF Cumulative Density FunctionDIFS Distributed Inter-Frame SpaceDSRC Dedicated Short Range CommunicationDTN Delay-Tolerant NetworksFACT Framework for Application-oriented Context-aware Trust-based communicationFCC Federal Communications CommissionGPS Global Positioning SystemICT Information and Communication TechnologyIEEE Institute of Electrical and Electronics EngineersITS Intelligent Transportation SystemsIVD Inter-Vehicle DistanceLTE Long-Term EvolutionMAC Media Access ControlMANETs Mobile Ad hoc NetworksMIN Middle Is NextOSI Open Systems InterconnectionxivList of AbbreviationsP2P Peer-to-PeerPDF Probability Density FunctionPDR Packet Delivery RatioQoS Quality of ServiceRPGM Reference Point Group MobilityRSU Road-Side UnitRTT Round-Trip TimeRWP Random WayPointSIFS Short Inter-Frame SpaceSIR Signal to Interference RatioTA Trusted AuthorityV2I Vehicle to InfrastructureV2V Vehicle to VehicleVNets Vehicular NetworksVSD Vehicular Service DeliveryWAVE Wireless Access in Vehicular EnvironmentsxvAcknowledgmentsFirst and foremost, I have to thank my academic advisor, Dr. Sathish Gopalakrishnanwithout whom this research would not be possible. I want to thank him for his continuoussupport, patience, technical and non-technical guidance that helped me accomplish thisresearch; and, for his understanding of the conditions and problems that I was involvedwith as a new international student. I must especially thank him for his trust in me inchoosing the right research avenues.Second, I want to declare my sincerest gratitude to my wife, Narjes Torabi, for herenormous help, patience, encouraging words and support in all those difficult momentsthat I frequently experienced throughout my PhD program.Third, special thanks to my friends Theepan Moorthy, Hasen Nicanfar, Javad Hajipoor,Bader Alahmad, and Debojit Dhar for all discussions, collaborations, and fun moments wehad which made my PhD more pleasurable.Last but certainly not least, I feel indebted to my great family, especially my mother,my father and my sister for their everlasting love and support not only in these years butalso throughout my entire life.This work was in part supported by the Natural Sciences and Engineering ResearchCouncil (NSERC) of Canada through the Discovery Grants Program and the DIVA Strate-gic Network..xviChapter 1IntroductionThe main question we answer in this research is the probability of delivering a message to acertain distance in a specific time. Delay, reliability, and trust are the main components ofthis question and they are the main focus of this work. What motivates us to think aboutthis question is that there are more than 1.2 million deaths in road accidents globally everyyear, from which 80% are from low or middle income countries with only 50% of worldvehicles [1]. The total cost for road accidents is estimated at $518 billion. Intelligent Trans-portation Systems (ITS) seem to be a promising solution for this huge problem. ITS is“the application of advanced and emerging technologies (computers, sensors, control, com-munications, and electronic devices) in transportation to save lives, time, money, energyand the environment” [2]. We make a modelling choice and assume that ITS has two mainlayers: the Application layer and the Information Dissemination layer. This modellingchoice is to simplify the design process. Very similar to the Open Systems Interconnection(OSI) model, application layer is responsible for defining requirements for each applicationand essentially creating guidelines for the information dissemination layer. It is the mainpoint of contact with the user where they can initiate an application/service1 and latersee the results. Once an application and its requirements are defined/initiated, it is theinformation dissemination layer’s job to figure out the best path to deliver the information.A very good candidate for the information dissemination layer is a network of connectedvehicles a.k.a. Vehicular Networks, where messages can be exchanged among cars (Vehicle-1We use application and service interchangeably in this dissertation.1Chapter 1. Introductionto-Vehicle or V2V) who are in the vicinity of each other (within the transmission range ofeach other) as well as between cars and Road-Side Units (RSUs) (Vehicle-to-Infrastructureor V2I). In a vehicular network, both V2V and V2I communications are autonomous usingsensors and proper algorithms on the processing unit in the car, and drivers are usuallynot involved. The focus of this dissertation is on the information dissemination layer.Vehicular Networks is an excellent choice for the ITS information dissemination layerbecause of four main reasons: 1) thanks to advances in electronics and wireless communica-tions, it is now feasible to form a network of cars connected to each other using inexpensivewireless transceivers. Many car companies have already started equipping some of theirmodels with the capability of communicating with other cars or RSUs, e.g., Sync by Ford,MBrace by Mercedes, and OnStar by GM. 2) The Federal Communications Commission(FCC) has allocated 75 MHz of bandwidth within the 5.85 − 5.925 GHz frequency spec-trum for Dedicated Short Range Communication (DSRC), specifically designed for vehic-ular communication [3]. 3) Institute of Electrical and Electronics Engineers (IEEE) hasa special task group named 802.11p which has developed an amendment on IEEE 802.11standard to make it suitable for the vehicular environment. It has defined a new modeof operation called Wireless Access in Vehicular Environments (WAVE) “for use by IEEEStandard 802.11 devices in environments where the physical layer properties are rapidlychanging and where very short-duration communications exchanges are required” [4]. 4)Delay in vehicular networks is much less than other main alternative, i.e., cellular networks.Round-Trip Time (RTT) is more than 300 ms for 3G and even greater than 100 ms forLTE (Long-Term Evolution) [5] when the average two-hop delay in vehicular networks isbetween 3 and 50 ms for the vehicle density of 50 vehicles per kilometre [6]. That hugedifference is particularly important when the application is a safety-related one with highsensitivity to the delay.2Chapter 1. IntroductionThe main motivation behind ITS is improving the safety of drivers and passengers onthe road [7], although several non-safety applications have also been proposed [8]. In fact,safety and comfort are the main drivers behind vehicular networks. Examples of safety-related applications are accident, traffic, and emergency brake notifications and non-safetyor infotainment applications include peer-to-peer applications such as file and information(available parking, recommended restaurants, etc) sharing as well as third-party servicessuch as autonomous tolling and advertising. Internet access is another example of non-safety services in vehicular networks, and it has been shown that different data demandrequires different infrastructure ranging from Road Side Units for high data rates to thecellular network’s Base Stations (BSs) for low traffic rates [9]. Both safety and non-safety applications provide different services to drivers, passengers, and transportationauthorities.Most of the times, safety-related applications are implemented using periodic near-space messages a.k.a. beacons. Each vehicle sends its location, speed, and direction inthose beacons. Therefore, nearby vehicles (neighbours) can identify their neighbours anduse the speed and direction information for scheduling/routing purposes. For example, itcan forward its message to a neighbour that is going towards the desired destination withthe highest speed.Safety and non-safety related applications have different quality of service (QoS) re-quirements, such as delay, single-hop and end-to-end reliability, and bandwidth. On oneside, emergency notifications, such as accident and emergency brake, have very strict delayand reliability constraints but they only need a small part of the bandwidth for communica-tion. On the other hand, however, general-purpose Internet access needs a large bandwidthwhile the latency and reliability requirements are much more relaxed.Offering infotainment services along with safety-related ones has two major benefits:3Chapter 1. Introductiona) it expedites the vehicular network implementation, hence increasing the market pene-tration, by creating new commercial opportunities for the private sector and incentivizingthem to invest in the technology more, b) infotainment services make the on-the-road timemore pleasant both for the drivers and for the travelers.It is worth mentioning that the communication in a vehicular network can be doneinside a vehicle or between vehicles. These scenarios are called intra-vehicle and inter-vehicle communication, respectively. Our work is focused on the latter case.1.1 Research ProblemsThere are three major research questions we try to answer in this dissertation:1. What is the effect of channel, contention, vehicle density, and mobility ondelay and reliability in information dissemination in vehicular networks?As mentioned in the previous subsection, there is a diverse range of applicationsin vehicular networks and each application has its own set of requirements. Relia-bility and delay are two main factors in almost all vehicular network applications.Reliability can be single-hop or end-to-end. Single-hop reliability is essentially theprobability of successfully receiving a message by a car. This can be achieved by morethan one transmission by the sender. End-to-end reliability, on the other hand, is theprobability of successfully receiving a message by nodes at a certain distance, alsoreferred to as destination nodes. Note that almost all safety-related applications arebroadcast-based where the objective is to notify every car within a desired distance.End-to-end reliability is also known as the packet delivery ratio (PDR). Delay, inthis dissertation, is always the end-to-end, or delivery, delay.In every vehicular network application, some information has to be disseminated4Chapter 1. Introductionamong vehicles (in the information dissemination layer). Therefore, it is extremelybeneficial to have a mathematical model for this information dissemination process.Modelling gives us insight about the limitations of the network and the level ofachievable QoS. It is particularly important in vehicular networks because the avail-able bandwidth is very limited and this bandwidth is shared among different ap-plications. An analytical model guides us in the designing of different parametersinvolved in this process, such as delay threshold and transmission power or even thetransportation-related parameters such as speed limits and speed zoning. We canextract bounds on delivery delay or the relationship between delay and reliability inmessage propagation. If network designers have a good model that closely followsthe behaviour of the network, they can tune the parameters like the transmissionpower, slot time, and back-off time accordingly to get the fastest while most reliableforwarding (scheduling/routing) policy.Developing a good mathematical model for information dissemination in vehicularnetworks is, however, very challenging due to unique characteristics of such networks.The first challenge is mobility; vehicles move with a very high speed (especially inhighways) making it very difficult to capture the topology changes in the model.The other difficulty is the fact that vehicles move on some predefined routes, i.e.,streets or road segments, which makes it hard, compared to Mobile Ad hoc Networks(MANETs), to develop a mobility model.There are two main reasons for an unsuccessful transmission in a vehicular network:a) bad channel conditions, and b) collisions with other transmissions. A good modelshould capture the impacts of these issues on the delay and reliability in the in-formation dissemination process. The next important feature which is unique invehicular networks is the partitioning problem. Studying traffic traces suggests that5Chapter 1. Introductioncars, especially on highways, tend to form disconnected groups [10]. In other words,if one could look at the highways from above, she would see some islands of groupedcars. This phenomenon affects the delivery delay and end-to-end reliability signifi-cantly and needs to be considered in the model. To the best our knowledge, thereis no comprehensive mathematical model that takes into account the effects of chan-nel conditions, collisions, and partitioning on the delay and reliability in vehicularnetworks.2. What does an efficient forwarding policy for vehicular networks look like?One of the main challenges in information dissemination in vehicular networks isthe fact that due to highly dynamic nature of these networks, contact times, i.e., thetime when two cars are within the transmission range of each other and therefore cancommunicate together, are very small. This challenge calls for a very lightweight yetreliable forwarding method. A good forwarding policy is the one that has minimumoverhead, minimizes the collision, and ensures a certain level of reliability. Althoughmany approaches have been proposed in the literature, most of them focus on eitherdelay or reliability and not both.3. How can we reduce the impact of malicious nodes in information dissem-ination in vehicular networks?Finally, the last but certainly not the least research challenge worth mentioning hereis security in vehicular networks. Even the best, fastest, and most reliable informa-tion dissemination scheme, without considering security issues, is futile. The focusof the research community has been mostly on designing a fast and reliable dataexchange policy in vehicular networks with no attention to security. Suppose thereis(are) malicious vehicle(s) attempting individual(collusion) attacks in the network.6Chapter 1. IntroductionThe exchanged information can be easily manipulated/dropped and other cars oreven authorities do not even find out. The attacker is also able to inject maliciousinformation and other cars simply forward it because they are not equipped with asecurity check mechanism. This can jeopardize the whole network since it is impos-sible to offer safety-related applications anymore. Proposing new frameworks thatguarantee the security of the information dissemination process is imperative.1.2 ContributionsWe have six major contributions in this research.1. In our first contribution, we propose a basic mathematical model that captures thejoint reliability-delay characteristics of a vehicular network. Having some knowledgeabout delay behaviour is useful, particularly in building delay-sensitive services wherethe main goal is to quickly disseminate the message with very high reliability. Weshow by simulation that this model completely follows the actual reliability and delaybehaviour of the system and it gives close bounds on these two important metrics.An interesting corollary from numerical results is that the end-to-end reliability has aquick transition. In the second step, we formally prove that the end-to-end reliabilityswiftly grows from 0 to 1 as we increase the number of transmissions.2. The modelling mentioned above has some simplifying assumptions. To make it moreprecise and as our second contribution, we enhance this analysis using Rician distri-bution to model channel fading in a vehicular environment. The new model is muchmore realistic and as expected, the results confirm that it can follow the reliabilityand delay characteristics of the network more closely. The proposed analytical modelis useful in protocol design as a reference point for delay-reliability behaviour of the7Chapter 1. Introductionnetwork.3. So far, our model addresses one of the main reasons for an unsuccessful transmission,i.e., bad channel conditions. The other reason, as mentioned in the previous part, iscollisions with other transmissions. In our third contribution, we study and describethe effect of MAC layer including the contention and the collision on the deliverydelay. To reflect this effect in our model, we add a new component that brings delayresults closer to the actual values.4. As the fourth contribution, we add another component to reflect the partitioningproblem explained in Section 1.1. A message in a vehicular network propagates onlyin two cases of Forward and Carry. By means of extensive simulations, we showthe common hypothesis in the literature based on which the inter-vehicle distances(IVDs) are assumed to follow an exponential distribution with the same parameter[11–13], is incorrect. This is an interesting observation not noticed previously byresearchers, which hugely affects the message delivery delay modelling. Only whendifferent distributions for IVDs are considered for two cases mentioned above, thedelay model can follow the actual delay. This observation is addressed by proposinga new two-part model for IVDs, which better represents the dynamics of vehicularnetworks in different cases. Then, we propose a Markov model to analyze delay ininformation dissemination in vehicular networks and we use this Markov process toimprove our delivery delay model so that it addresses the partitioning phenomenonin addition to channel conditions and contention. At this point, our mathematicalmodel is complete; it captures physical layer’s characteristics, considers contentionand collision, and addresses partitioning problem. To the best of our knowledge, thisis the first delay model that accomplishes all those things at the same time. Urbantraffic designers can use the results of this model to enhance the traffic conditions and8Chapter 1. Introductionsafety level in a city. As an example, if the delivery delay for message propagation iscalculated using our model, an urban designer can set speed limits in different zonessuch that a fast delivery is guaranteed even in the worst-case scenario. An importantfeature of our proposed model is its modularity; network designers can substitutesdifferent modules of the model based on their preferences and assumptions, e.g.,Rayleigh distribution instead of Rician distribution, or a different model for con-tention, and the rest of the model still firmly holds. Finally, we run an extensive setof simulations to validate the effectiveness of the proposed model.5. The proposed model has some interesting insights. One of them is that if vehiclesmake their forwarding decisions based on the vehicle’s density on the road, the de-livery delay will significantly reduced. We make progress in this direction, and asour fifth contribution, we propose a fully distributed forwarding strategy for a safetyapplication. Our method is called Middle Is Next, or MIN because, it always tries topick the closest car to the middle of previous transmitter’s communication range asthe next transmitter. Our scheme not only ensures a minimum level of reliability forall nodes in a certain area, but also has a much lower delivery delay than some otherwell-known routing approaches. Simulation results confirm the performance of MINagainst some other well-known forwarding policies.6. Now that we have a comprehensive mathematical model and an efficient forwardingpolicy in place, in our sixth contribution, we focus on the trust problem in vehic-ular networks. This contribution has two steps: in the first step, we survey thestate-of-the-art in trust models/systems and routing protocols in vehicular networks.Then in the second step, we propose a novel two-layer Framework for Application-oriented Context-aware Trust-based communication (FACT) in vehicular networks,where nodes only use their most trusted neighbours to forward the message otherwise9Chapter 1. Introductionthey carry the message by themselves. FACT consists of two modules: Admission andDissemination. The key distinction of the FACT lies in its “space-centric” nature. Itis a combination of entity-/data-centric methods in addition to its focus on location.Once a message is received, FACT first applies three safety checks in the Admissionmodule to make sure the message is trustwothy. Then, FACT admits the messageand pushes it to the Dissemination module to be forwarded through a trusted path.After explaining the details of FACT, we evaluate our framework via simulation andshow that FACT outperforms other routing protocols when some areas of the city arenot trusted. FACT gives network designers a framework which delivers trustworthymessages through a safe path with high reliability and in a short amount of time.It is flexible enough meaning network admins can tune the parameters based on thenetwork condition. Designers can incorporate their desired scheduling and routingschemes into FACT and still disseminate the messages safely.1.3 Organization of this DissertationThesis contributions and results are organized as follows:1. In Chapter 2 we first present a simplified mathematical model to study reliabilityand delay in information dissemination in vehicular networks. Then, we improveour model using Rician fading for the channel fading. Using the insights we getfrom the model, we propose a distributed forwarding policy called Middle Is Next, orMIN. Finally, we present an extensive set of simulations to validate our model andto showcase how MIN outperforms other well-known forwarding methods.2. In Chapter 3, we build on our model in 2, by first studying the contention/collisioneffect on the delivery delay. After that, with use of extensive simulations, we show10Chapter 1. Introductionthe general assumption of having the same exponential distribution for inter-vehicledistances is wrong. Then, we complete our model by incorporating the partitioningphenomenon using a Markov chain. Finally, we use simulation to validate our model.3. In Chapter 4, we first do a comprehensive survey on the state-of-the-art in trustmodels in vehicular networks. Then, we present a two-layer trust-based frameworkcalled FACT, for secure communication in vehicular networks. Simulation resultspresented at the end of this chapter show the FACT outperforms other well-knownrouting protocols when the network is not secure.4. In Chapter 5, we provide thesis conclusions and discuss potential future extensions.11Chapter 2Analysis of Message Dissemination inVehicular Networks2.1 IntroductionContributions of this chapter are four folded. The main theme in these four contributionsis analytical modelling of information propagation in vehicular networks. For this, a math-ematical modelling is proposed using some simplified assumptions. Then, the model isenhanced by applying more accurate parameters. There are some observations from themodelling which are used in proposing a distributed forwarding policy. Next, we explainall four contributions in detail.First, an analytical model to study reliability and delay when a message is propagatedin vehicular networks is proposed. Simulation results (Section 2.6) show that this modelcompletely follows the actual reliability and delay behaviour of the system and it givesclose bounds on these two important metrics. Numerical results reveals some interestingoutcomes, one of which is the quick transition of the end-to-end reliability. As our secondThis chapter is based on the following papers:Rostamzadeh, K. and Gopalakrishnan, S.;, “Analysis of Message Dissemination in Vehicular Networks,”IEEE Transactions on Vehicular Technology, vol. 62, issue 8, pp. 3974-3982, Oct. 2013.Rostamzadeh, K. and Gopalakrishnan, S.;, “Analysis of Emergency Message Dissemination in VehicularNetworks,” in Proc. of IEEE Wireless Communications and Networking Conference (WCNC), pp. 575-580, Mar. 2011.Rostamzadeh, K. and Gopalakrishnan, S.;, “On Bounding Information Dissemination Delays in VehicularNetworks,” in Proc. of IEEE Consumer Communications and Networking Conference(CCNC)’s Workshop,pp. 70-74, Jan. 2011.12Chapter 2. Analysis of Message Dissemination in Vehicular Networkscontribution, it is proved that packet delivery ratio exponentially grows as the numberof transmissions increases (Section 2.3.3). We used some simplifying assumptions in ourmentioned model. As our third contribution and to enhance this analysis, Rician distri-bution is used to model channel fading in a vehicular environment. As we expect, thedelay and reliability characteristics of the network are followed more closely by the newmodel. Protocol designers can use the proposed model to study delay and reliability of thenetwork. Next, we propose a distributed information dissemination scheme for vehicularnetworks. We use this fact that using the vehicle’s density on the road is a good measurefor selecting the next transmitter. The proposed scheme, called Middle Is Next or MIN,offers the same level of packet delivery ratio as other well-known forwarding methods butin a much shorter time. The speed and reliability of MIN is confirmed through simulations.This part encompasses our fourth contribution.2.2 Related WorkModelling of vehicular traffic has gained researchers’ attention over the past years. Mobilitymodelling first touched by Johnson for Random Waypoint (RWP) model [14]. Afterward,some more accurate models like Reference Point Group Mobility (RPGM) [15] were pro-posed. Harri et al. [16] presented a comprehensive survey for different mobility models inliterature. The main factor that differentiates VANETs from MANETs, i.e., cars can onlymove within some predefined roads, is addressed by most of presented mobility models.However, most of them capture some of the vehicle’s movement’s characteristics assumingsome simplifications.On the other hand, there are some analytical approaches that model the data dissem-ination in vehicular networks. Wu et al. [10] proposed an analytical model to study thespatial propagation of information in a vehicular network. Besides assuming an idealized13Chapter 2. Analysis of Message Dissemination in Vehicular Networkstransmission model where all of transmissions are successful and there is no contention inthe network, authors did not validate their model through simulation. The same idealizedassumptions were made by Fracchia and Meo [17], where they considered average valuesfor studying the number of informed vehicles in a gossip scenario, and Abboud et al. [18]where they used clustering to calculate delay in a flooding scenario. Our analytical modelis based on a more realistic communication model in terms of packet loss and we extendour work to an efficient forwarding strategy. Resta et al. [11] presented a mathemati-cal analysis for a centralized message propagation scheme assuming a global and preciseknowledge about the state of all vehicles which is clearly not available to the cars.Routing is one of the main challenging components in vehicular network. Epidemicrouting [19] is among the first and yet main routing protocols for vehicular networks.Epidemic replicates the message until it reaches a certain destination. It uses an upperbound on the message hop count and a per-node buffer space for carrying other nodes’messages, in order to maximize message delivery and minimize message latency. Zhao andCao proposed VADD which uses a carry-and-forward strategy to allow packets to be carriedby vehicles in sparse networks for eventual forwarding when another appropriate nodeenters the broadcast range [20]. With the VADD protocol, the carry-and-forward strategyis used by transferring packets along vehicles on the fastest roads available. Since vehiclesmay deviate from predicted paths, the routing path should be recomputed continuouslyduring the forwarding process. Trigoni and Skordylis presented two unicast forwardingstrategies, D-Greedy and D-MinCost [21]. The authors tried to support different prioritiesfor packets with different delay thresholds until they were delivered to one of the APs.Unlike VADD, D-Greedy and D-MinCost do not try to minimize delay of packet delivery.Their goal is to minimize the number of packet transmissions required to satisfy packet-specific delay thresholds.14Chapter 2. Analysis of Message Dissemination in Vehicular NetworksThere are a few analytical works in the literature regarding the connectivity problemin vehicular networks. The number of connected vehicles was examined by Fujimoto et al.[22] using an analytical model and some experiments. Bai and Krishnamachari [23] studiedthe path availability in VANETs after modelling the real highway traffic with exponentialdistribution.As discussed here, there has been an increasing attention to analytical modelling ofvehicular data traffic and related applications. Nevertheless, there are still lots of rooms formore precise models and more importantly leveraging the analysis to design new paradigms.Particularly, taking advantage of a good modelling in order to propose efficient strategiesbased on the modelling’s outcomes is what we are trying to do in this chapter.2.3 Theoretical Analysis2.3.1 AssumptionsWe use empirical results from Wisitpongphan et al. [24] where the distances between suc-cessive vehicles (x) are identically and independently distributed based on an exponentialdistribution with parameter λs (veh/m). Further we assume that the transmission rangeof vehicles is r. We consider a network that is sufficiently dense such that each car finds(at least) one car in its transmission range to forward its message. We show by an examplethat this is a reasonable assumption. Note that the probability of having k connectedvehicles is (1 − e−λsr)k, using the characteristics of x. For typical values of λs = 0.052(from [24]), r = 200m and k = 50, this probability is 0.99.We assume a transmission success rate of q. It is shown that by using a well-chosen q,the channel model always underestimates the actual reception probability [11]. Therefore,the real channel condition is always better than the fixed q. Simulation results in Section15Chapter 2. Analysis of Message Dissemination in Vehicular NetworksAccident!...... ......Figure 2.1: A warning dissemination scenario due to an accident. Arrows represent suc-cessful transmissions between neighbour vehicles.2.6 show that despite these simplifications for r and q (because they are assumed to befixed), our model effectively captures the behaviour of the vehicular network and gives abound on the actual end-to-end reliability and delay.Finally, let the probability that each car forwards the received warning be Pf . We startwith a fixed Pf , but since Pf , as we see in section 2.3.2, directly affects the performanceof the dissemination scheme, in section 2.5 we propose a novel distributed forwardingapproach. In the proposed approach, Pf depends on the location of the car. A list ofnotations used in this chapter is presented in the beginning of this dissertation.2.3.2 Reliability-Delay AnalysisWe start with the case where one vehicle generates an emergency message (due to accidentdetection, emergency brake, etc.) and broadcasts it to its neighbours. When a neighboursuccessfully receives the packet, it transmits the message with probability Pf . The sameprocedure is followed until the packet reaches the desired destination. In order to reduceredundancy, each vehicle only forwards a new packet. It discards the received packet if ithas already transmitted a copy of this packet (by means of caching the original packet).Each packet depending on its nature has a lifetime which is set by the original sender andshows when it expires from the cache.We consider x = 0, as the starting point of the network where the first message isgenerated. Fig. 2.1 shows a typical dissemination scenario and notations used in our model.16Chapter 2. Analysis of Message Dissemination in Vehicular NetworksLi represents the distance between the (i − 1)th and ith transmitters. d shows the areaof relevance where all cars in this area should be informed about the emergency situation.Let M denote the number of transmitters up to d. This number can be equivalently seenas the number of transmission rounds, because there is no retransmission by the samenode in our system and each node is able to transmit an emergency message one time atmost. Note that the number of nodes (regardless of being a transmitter or not) up to dhas a Poisson distribution with parameter λs. Soong [25] showed the fact that Poissondistribution generates itself under addition of independent random variables. Thus, thenumber of cars participating in warning forwarding, M , has a Poisson distribution withparameter λ = qPfλs. Similarly, Li is exponentially distributed with the same parameterλ.Let Dk be the distance covered by k transmitters. In other words, Dk is the sum ofk i.i.d. random variables Li, Dk =∑i=ki=1 Li. So, the probability density function (pdf) ofDk, fDk(x), is given by the n-fold convolution of the pdf of Li, fLi(x), such thatfDk(x) = fL1(x) ∗ . . . ∗ fLk(x) =xk−1λke−λx(k − 1)!(2.1)Using the relationship between the number of transmitters, M , and the distance coveredby them, Dk, we getPD = Pr(M ≤ k) = Pr(Dk ≥ d) =∫ ∞dfDk(x)dx (2.2)where, PD means the end-to-end reliability.Suppose the required end-to-end reliability for the warning dissemination is Pmin. Em-17Chapter 2. Analysis of Message Dissemination in Vehicular Networks0 10 20 30 40 50 60 70 80 90 10000.10.20.30.40.50.60.70.80.91kP D d=2000 md=1000 mFigure 2.2: End-to-end delivery probability vs. number of transmission rounds for λs =52(veh/km), q = 0.8 and Pf = 0.6.ploying (2.2) in the inequality PD ≥ Pmin yields a kmin which is the minimum requirednumber of transmissions to get Pmin. It means that if the message passes kmin trans-missions, it reaches the desired distance, d, with probability Pmin. Note that kmin is anindicator of minimum delay for achieving a certain end-to-end reliability.To make the discussion clear, PD versus k is plotted for two different distances (Fig.2.2). As seen in the figure, for Pmin = 0.9, we get kmin = 32 and 60 for d = 1000m and2000m, respectively. We also investigate the effect of traffic conditions and the forwardingprobability on kmin (see Fig. 2.3). As it is clearly shown in the figure, kmin increasesalmost linearly with vehicle density for a given Pf . When the forwarding probability, Pf ,is 0.6, we get kmin = 79 for λs = 70(veh/km). However, when we repeat the same scenariofor Pf = 0.2, it results in kmin = 30. The difference is even bigger when we comparebetween Pf = 0.2 and Pf = 0.9 when λs = 90(veh/km), which results in kmin = 37and kmin = 145, respectively. This observation is interesting since it indicates that fordense-enough networks, by decreasing the forwarding probability we get a much faster18Chapter 2. Analysis of Message Dissemination in Vehicular Networks0 2040 6080 1000.20.40.60.81050100150 Average vehicle density, λs (veh/km)Forwarding probability, Pf k minFigure 2.3: Minimum number of transmissions we need for at least 90% reliability vs. λsand Pf for q = 0.8 and d = 2000m.information dissemination with the same end-to-end reliability. It justifies that a smartforwarding strategy based on the vehicle density is beneficial. We use this result as a basisin section 2.5 to propose a distributed forwarding policy.By knowing the delay of each transmission round (which consists of processing, trans-mission, and propagation delays), we can calculate the minimum required time to deliverthe warning to distance d with probability at least Pmin. Another important observationfrom Fig. 2.2 is that PD has a fairly fast transition with respect to k (see Fig. 2.2). Inthe next part, we formally show how fast this transition is. We also evaluate these resultsthrough simulation in section 2.6.2.3.3 PD Transition Speed with Respect to kThe following theorem proves that PD has an exponential fall-off with respect to k.Theorem 2.1 : The probability that an emergency message is delivered to a node atdistance d from the source in k transmission rounds, i.e., PD = P (M ≤ k), increases19Chapter 2. Analysis of Message Dissemination in Vehicular Networksexponentially at a threshold kcrit from 0 to 1.Proof : We prove this result in two steps. First, we show that PD has a tight upper tailbound (i.e., for k > kcrit).For any random variable, Z ≥ 0, and constants α, c ≥ 0, it is easy to show thatPr(Z ≥ α) = Pr (ecz ≥ ecα) (2.3)On the other hand, from Markov’s inequality, we havePr(Z ≥ α) ≤E[Z]α(2.4)From (2.3) and (2.4), we obtainPr(Z ≥ α) ≤E[ecz]ecα(2.5)Writing the moment-generating function for our Poisson random variable, M , yieldsE[ecM ] =m=∞∑m=0ecme−λd(λd)mm!= e−λdm=∞∑m=0(λdec)mm!= e−λdeλdec= eλd(ec−1) (2.6)20Chapter 2. Analysis of Message Dissemination in Vehicular NetworksSubstituting (2.6) in (2.5), we getPr(M ≥ α) ≤ eλd(ec−1)−cα (2.7)Choosing c = ln(α/(λd)) will minimize the right hand side of (2.7). In that case, c > 0as long as α > (λd). Rewriting (2.7) based on this value for c, yieldsPr(M ≥ α) ≤ e−λd+α(1−ln(αλd )) (2.8)By letting α = α′λd in (2.8) and using the mean value for M , i.e., E[M ] = λd, we havePD = Pr(M ≥ α′E[M ])≤ e−(1−α′+α′lnα′)E[M ] (2.9)Notice that (2.9) shows that as we go away from the mean, PD decreases exponentially.We name this threshold as kcrit.The second part of the proof demonstrates that PD has a tight lower tail bound (i.e.,for k < kcrit). It is almost identical to the proof for the lower tail bound. We first introduceparameters α, c ≥ 0:Pr(Z ≤ α) = Pr(e−cz ≥ e−cα)(2.10)Applying Markov’s inequality to the RHS of (2.10) and using (2.6) in the result, we get21Chapter 2. Analysis of Message Dissemination in Vehicular NetworksPr(M ≤ α) ≤ eλd(e−c−1)+cα (2.11)Choosing c = ln((λd)/α), where c > 0 for α < (λd) and letting α = α′λd in (2.11) andusing the mean value for M , we getPr(M ≤ α′E[M ])≤ e−(1−α′+α′lnα′)E[M ] (2.12)Equations (2.9) and (2.12) clearly show that Pr(M) is highly concentrated aroundM = λd. They also prove that PD at k = kcrit has a tight threshold in both directions.Finally, note that PD increases from 0 to 1 because it is a CDF function. This completesthe proof. As shown in this section, the value of Pf has an important impact on the end-to-end reliability. In the next section, we will present an efficient forwarding scheme thatguarantees a minimum reliability for all vehicles up to d.2.4 The Effect of q on Reliability-Delay ModelWe used a fixed-value q as the reception probability. However, this may be a significantapproximation. In general, we can divide the sources of an unsuccessful reception (orequivalently an unsuccessful transmission) into two categories: physical layer issues, upperlayer issues. For the physical layer, one might list path loss (distance from the transmitter),channel fading, shadowing, interference from other (not close) transmitters working at thesame frequency channel, modulation, bit rate, type of coding, and the channel noise as22Chapter 2. Analysis of Message Dissemination in Vehicular Networksthe main causes for a capture failure. On the other hand, medium access control’s (whichis CSMA in the context of vehicular networks) low throughput and contention are majorupper level reasons for an unsuccessful reception.2.4.1 Physical Layer ModelingDifferent studies show that Rician distribution is a good model for the physical layercharacteristics of a vehicular network [26–28]. The Rician fading has a similar distributionto Rayleigh fading (which is widely used to model the channel in cellular networks), exceptthat in Rician fading a strong dominant component is present. This dominant componentcan for instance be the line-of-sight wave. Refined Rician models also consider that thedominant wave can be a phasor sum of two or more dominant signals, e.g. the line-of-sight,plus a ground reflection. This combined signal is then mostly treated as a deterministic(fully predictable) process [29].Besides the dominant component, the mobile antenna receives a large number of re-flected and scattered waves. In Rician fading model, both in-phase and quadrature com-ponents have Gaussian distribution. For a signal amplitude of a, Rician pdf is as followsfa(a) =aσ2exp(−a2 + µ22σ2)I0(µaσ2) (2.13)where 12µ2 is the power of the dominant component, σ2 is the average (local-mean) scatteredpower, and I0 is the modified Bessel function of the first kind and zero order.Note that for µ = 0, the equation (2.13) turns to a Rayleigh distribution. The Ricianfading is usually described by σ2 and Rician K-factor, which is defined as the ratio of thepower of the dominant component over the scattered power23Chapter 2. Analysis of Message Dissemination in Vehicular NetworksK =µ22σ2(2.14)Using (2.14), the local-mean received signal, P¯r, which is the sum of the power in thedirect signal and the scattered signals, can be expressed asP¯r =12µ2 + σ2 = (K + 1)σ2 (2.15)From path loss we know that the received power at distance x from the sender is givenbyP¯r = cP¯txn(2.16)where, c is a constant which depends on the characteristics of both transmitter and receiverantennas, P¯t is the average transmitted power, and n is the path loss exponent, whose valueis normally in the range of 2 to 4 (where 2 is for propagation in the free space and 4 is forpropagation in lossy environments where there are obstacles).Assuming a similar average transmission power, P¯t, for all vehicles, we can combine P¯tand c in a new constant C. Combining equations (2.13)-(2.16) gives the probability densityfunction for the instantaneous signal power, p, at distance x from the transmitter24Chapter 2. Analysis of Message Dissemination in Vehicular Networksfp(p|x) =(K + 1)xne−KCexp(−(K + 1)xnCp). I0(2√K(K + 1)xnCp)(2.17)where, we used p = 12a2 to get (2.17).From (2.17) we can extract the probability distribution that a packet is received suc-cessfully at a given distance. To do this, we first explain our interference scenario. Weassume n interfering vehicles, where n depends on the scheduling-routing algorithm thatis used in the network. For example, in Flooding it is likely that all cars in the interfer-ence range of the desired receiver, ri, are transmitting at the same time. Thus, n in thisexample (in the worst-case scenario) is the total number of cars in ri. On the other hand,the desired receiver is defined to be the receiver next to the transmitter.The desired receiver can successfully capture the message only when the power of thatmessage sufficiently exceeds the power of interfering cars. In other words, the signal tointerference ratio (SIR) is greater than SIRmin. Therefore, the probability of a successfulreception, q, at the desired distance, xd, has the following distributionFq(SIRmin|xd) = Pr (SIR > SIRmin|xd)= Pr(pspi> SIRmin|xd)=∫ ∞0∫ ∞piSIRminfps(ps|xd)fpi(pi|xd) dps dpi(2.18)where, ps is the power of desired message (signal power) and pi is the total interference25Chapter 2. Analysis of Message Dissemination in Vehicular Networkspower from n interfering cars {i = i1, ..., in}.Next, we calculate the pdf for both signal and interference powers in (2.18). Recall thatthe inter-vehicle spacing is approximated using the exponential distribution with parameterλs. So, the distance of the desired receiver from the transmitter, xd, is exponentiallydistributed such thatfxd(xd) = λse−λsxd (2.19)fps(ps|xd) =(K + 1)xnde−KCexp(−(K + 1)xndCps). I0(2√K(K + 1)xndCps)(2.20)For interfering cars, however, we need to make some assumptions first. In our scenario,the first interfering car is the second car from the transmitter with distance xi1 fromit. Conditioning the distribution of xi1 on xd yields an exponential distribution which isexpressed asfxi1 (xi1|xd) = λse−λs(xi1−xd) (2.21)and consequently, the pdf for the interference power from this car, pi1 , isfpi1 (pi1|xd) =∫ rixdfpi1 (pi1|xi1)fxi1 (xi1|xd) dxi1 (2.22)26Chapter 2. Analysis of Message Dissemination in Vehicular Networkswhere, ri is the interference range and fpi1 (pi1|xi1) can be written asfpi1 (pi1|xi1) =(K + 1)xni1e−KCexp(−(K + 1)xni1Cpi1). I0(2√K(K + 1)xni1Cpi1)(2.23)Similarly, the pdf for the distance of the second interfering car, xi2 , and the pdf for itspower, pi2 , are given byfxi2 (xi2|xi1) = λse−λs(xi2−xi1 ) (2.24)fpi2 (pi2|xi1) =∫ rixi1fpi2 (pi2|xi2)fxi2 (xi2|xi1) dxi2 (2.25)where,fpi2 (pi2|xi2) =(K + 1)xni2e−KCexp(−(K + 1)xni2Cpi2). I0(2√K(K + 1)xni2Cpi2)(2.26)One can continue with this procedure to extract distribution for all n interfering cars,fpi(pi), which will be conditioned on xd. After doing that, we getfpi(pi|xd) =∫ rixd∫ rixi1. . .∫ rixin−1fpi1 (pi1|xd) . fpi2 (pi2|xi1) . . .. fpin (pin|xini−1 ) dxin . . . dxi2 dxi1 (2.27)27Chapter 2. Analysis of Message Dissemination in Vehicular NetworksCombining equations (2.18), (2.20), and (2.27) yields the distribution of the success rate,Fq(SIRmin|xd). To apply this distribution to our modelling, we need to show that the newstochastic process formed by the new λ = Pfλsq which has the CDF of Fλ(SIRmin|xd) =PfλsFq(SIRmin|xd), also has a Poisson distribution. For this, we use Sampling a PoissonProcess proposition which is proved by Ross [30]. We include the proposition here for thesake of completeness.Suppose that there are k possible types of events and that the probability that an eventis classified as a type l event, l = 1, ..., k, depends on the time the event occurs. Specifically,suppose that if an event occurs at time y then it will be classified as a type l event,independently of anything that has previously occurred, with probability Pl(y), l = 1, ..., kwhere∑kl=1 Pl(y) = 1. The mentioned proposition is as follows.Proposition 2.2 : If Nl(t), l = 1, ..., k, represents the number of type l events occurringby time t then Nl(t), l = 1, ..., k, are independent Poisson random variables having meansE[Nl(t)] = λ∫ t0Pl(s)ds (2.28)We can apply Proposition 2.2 by:1. assuming a continuous distribution for Pl(y), i.e., Fλ(xd) = Fλ(SIRmin|xd)fxd(xd),and2. using distance instead of time, because in our case, the number of successful trans-mitters at a given distance follows a Poisson distribution.Consequently, the number of cars participating in warning forwarding, M , has a Poissondistribution with parameter28Chapter 2. Analysis of Message Dissemination in Vehicular Networksλ = Pfλs∫ rt0Fq(SIRmin|xd)fxd(xd)dxd (2.29)where, rt is the transmission range of the transmitter, and Fq(SIRmin|xd) is given byequations (2.18), (2.20), and (2.27).A very important feature of our proposed model is its flexibility in using sub-modelswithout affecting the overall framework. For example, one can substitute Rician distri-bution with Rayleigh distribution and Fq(SIRmin|xd) is updated consequently. In fact,Rayleigh distribution makes the analysis mentioned in this section, much easier. Therefore,sub-models can be changed based on the network designer’s preferences without changingthe process.2.5 An Efficient Forwarding PolicyIn this section, we propose an efficient forwarding strategy that not only guarantees aminimum reliability for all vehicles within the desired range, but also is very fast. Ourscheme is derived from this fact that the density of cars directly affects the number ofrequired hops that a message has to pass before reaching the desired distance. So, asmart dissemination approach is the one that exploits this density information in theforwarding process. In the proposed strategy, each car chooses an appropriate Pf withoutany assistance from a centralized authority. Let us first explain the intuition that we use inour strategy. Assume that a given node X receives a message successfully with probability0.7. Then, if X receives this message two times from other nodes, the probability that Xwill have at least one successful reception is simply (1−(0.3)2) = 0.9. We call this value thesingle-hop reliability. Based on this intuition, we propose a forwarding policy that ensures29Chapter 2. Analysis of Message Dissemination in Vehicular Networksat least two receptions of the same warning for each vehicle, thus it provides reasonablyhigh single-hop reliability for nodes. We call our strategy Middle Is Next or MIN becauseeach transmitter tries to select a vehicle in the middle of its transmission range to be thenext transmitter.It is assumed that all vehicles know their location via GPS and each transmitter sendsits location with the warning. When a car, e.g., i, receives the warning successfully, itcalculates its distance from the transmitter as zi, 0 ≤ zi ≤ r (r is known for all cars,because transmission power is fixed throughout the network.) Then, it sets a back-offcounter, BCi. This procedure happens for all vehicles that had successful reception. Theyall continue to listen to the channel while counting down. The first car that its counterreaches zero transmits the warning and all other cars stop counting after this transmission.There could be some rare situations in real life where some cars that are counting down,stand outside of the transmission range of this first car because of a huge difference intheir speeds. But following definition of BCi assures a very big back-off counter for thosecars (See Fig. 2.4). Thus, their transmission after a very long delay does not affect theperformance of the network. This fact is confirmed by simulation in section 2.6. Clearly,the value of BC has a significant impact on the performance of our strategy in terms ofdelay. To reduce the delay and collision on one side and to improve the reliability on theother side, BCi for car i is defined as a function of zi such that:BCi = be(λs(zi− r2 ))22 c (2.30)MIN has two main components in which both of them are considered at the same time:1) forwarding based on the distance, and 2) forwarding based on the vehicle density. Settinga back-off counter instead of simply forwarding the warning with probability Pf (which30Chapter 2. Analysis of Message Dissemination in Vehicular Networks20 40 60 80 100 120 140 160 18005101520253035z ( meters )BC λs = 0.033λs = 0.025Figure 2.4: BCi vs. distance for r = 200 and two different λs.is implemented in most broadcasting mechanisms for VANET) reduces collision. Becauseeach car selects its specific BC depending on its distance from the transmitter (the firstcomponent). In other words, difference in zi results in difference in BCi as illustrated inFig. 2.4. Also, it is shown that collision does not affect the number of informed vehicles ina probabilistic broadcasting [17]. The main impact of collision is, however, on the deliverydelay. The motivation for using a location-aware probabilistic forwarding, i.e., by settingthe back-off counter based on the location, in the proposed algorithm is to reduce thisimpact.We extract (2.30) from a normal distribution with parameters µ = r/2 and σ = 1/λs(second component). These sets of parameters result in a small back-off counter for carsaround the middle of transmitter’s communication range and a larger back-off counterfor other cars. In fact, the next transmitter of the warning is more likely to be the cararound r2 . This strategy guarantees a minimum of two reception opportunities of the samewarning for all cars. In addition, a fast warning dissemination is achieved since the carwith the smallest back-off counter (usually BC = 1, i.e., the minimum possible delay)forwards the message. Selecting the midpoint is a trade-off between delay and reliabilityin the information dissemination process. The role of the second component in MIN tunes31Chapter 2. Analysis of Message Dissemination in Vehicular Networksthe size of BC proportional to the vehicle density. For example, if the road is relativelycongested it is very likely to have cars very close to each other. Therefore, setting theσ = 1/λs for a higher λs means a more concentrated distribution for BC and equivalentlya less chance of having similar back-off counter sizes for adjacent neighbours. Clearly, ithelps cars avoid collision.The selection of 1/λs as the standard deviation of BCi ensures that for different trafficdensities our forwarding policy works well in terms of delay and reliability. There are sometechniques in the literature that dynamically estimate the vehicle density, λs, while thecar moves on the road (e.g., [31]). Thus, our forwarding strategy is implemented in acompletely decentralized manner.The set of parameters ( r2 ,1λs) can be dynamically tuned based on the requirementsand characteristics of the network, such as required delay or the channel condition. Forexample, for a poor channel with high bit error rate, e.g., q = 0.6, one appropriate settingcould be ( r3 ,1λs). Under this setting, the single-hop reliability is increased from (1− q2) to(1 − q3). We plan to investigate this relationship and come up with tuning algorithms inthe future.As for the case when the environment is highly dynamic and the topology changesvery fast, again we expect that MIN performs robustly. As it can be seen in Fig. 2.4,the majority of the next transmitters are selected from the middle part of the originaltransmitter’s transmission range. As a result, their back-off counter value is expected tobe less than 5 for most cases. Assuming 5msec for each slot, it means that the time untilnext transmission is less than 25msec most of the time. Even for a highway where carshave a speed of 100km/h, this delay equals to less than one meter displacement of thecar and it will not affect the forwarding mechanism. This observation is verified in thesimulation results in Section 2.6.32Chapter 2. Analysis of Message Dissemination in Vehicular NetworksThere are some (rare) situations in which none of the sender’s neighbours receive thewarning due to the poor channel condition. To address them, a timeout mechanism isconsidered. First, the sender i waits for T seconds. If none of i’s neighbours transmits thewarning in that time, it will retransmit the emergency message. The value of T should becarefully selected to avoid stalling the warning propagation. A good choice for T based onthe above argument is 25msec which is equals to 5 time slots. This suggestion is basedon an observation in Section 2.6 where evaluation results show that for more than 95% ofthe time, the transmitter’s back-off counter value is 4 or less. In the next section, we showthat MIN provides a reliable and fast warning propagation.2.6 EvaluationThe objective of this section is assessing the performance of the proposed forwarding pol-icy, MIN, for a typical emergency dissemination. Also, the mathematical model presentedin Section 2.3.2 is validated. To do this, a vehicular network simulator is implemented.To model the channel, Rician fading model is used. Because it is proved as an appro-priate model for capturing the channel behaviour in a vehicular environment [28]. In thementioned Rician fading model, there is a strong dominant component (usually the line-of-sight wave plus a strong roadway reflection) in addition to scattered components. Weassume a Rician K-factor (defined as the ratio of signal power in dominant component overthe scattered power) of 10 based on past measurements for real channel characteristics invehicular networks [27]. A summary of the simulation parameters is presented in Table2.1.Wisitpongphan et al. [24] based on real-world traffic traces, showed that the speed ofvehicles follows a normal distribution, in which their mean and variance vary dependingon the traffic conditions. We used their results and deployed our proposed forwarding33Chapter 2. Analysis of Message Dissemination in Vehicular NetworksTable 2.1: Configuration ParametersParameter ValueChannel modelling Rician with K = 10Scenario HighwayMinimum vehicle speed (km/h) 40Maximum vehicle speed (km/h) 130Packet length (B) 200Data rate (Mbit/s) 60 10 20 30 40 50 60 70 80 9000.10.20.30.40.50.60.70.80.91kP D d=500m, basic modeld=500m, enhanced modeld=500m, simulationd=1500m, basic modeld=1500m, enhanced modeld=1500m, simulationFigure 2.5: End-to-end delivery probability vs. number of transmission rounds: simulationvs. numerical results for λs = 40(veh/km), q = 0.9 and Pf = 0.7.strategy in the simulator. The minimum and maximum values for vehicle speeds areselected to reflect the actual values on a typical highway. The packet size and data rateare assumed to be 200(Bytes) and 6(Mbit/sec), respectively. In each simulation run, thenumber of transmissions till the warning reaches the desired destination is recorded. Afteraccumulating these data for 10, 000 runs, we derive the empirical CDF of PD over timeand distribution of kmin for different traffic conditions (see Fig. 2.5 and Fig. 2.6). Allexperiments are repeated for d = 500m and d = 1500m. The bounds derived in section2.3.2 are also presented in these figures to be compared against simulation.As observed in Fig. 2.5, despite simplified assumptions we made in our model regardingq and r, these analytical bounds accurately follow the simulation results with the same34Chapter 2. Analysis of Message Dissemination in Vehicular Networks20 25 30 35 40 45 50 55 600102030405060708090100110Average vehicle density, λs (veh/km)k min d=500m, basic modeld=500m, enhanced modeld=500m, simulationd=1500m, basic modeld=1500m, enhanced modeld=1500m, simulationFigure 2.6: Minimum number of transmissions we need for at least 90% end-to-end relia-bility vs. λs: simulation vs. numerical results for q = 0.9 and Pf = 0.7.slope. The other interesting observation is the transition of PD as we progress in time: itis relatively fast but faster for d = 500m as we anticipated from the numerical results.Next, we investigate the performance of our proposed dissemination scheme, MIN, fordifferent traffic conditions. For this reason we derive kmin for Pmin = 0.9 which is basicallythe 90% quantile of the PD’s CDF for different vehicle densities (Fig. 2.6). First, notethat the analytical bounds get closer to the simulation results as we increase the trafficdensity. It suggests that for dense environments such as urban areas, the analytical modelcan be used as a precise model and not just for calculating bounds. Second, the reportedresults show that MIN disseminates the warning to a relatively far destination (1.5km)in less than half a second for all traffic conditions (assuming 5msec for each transmissionround which is reasonable based on the data rate and packet size). Thus, our approach isfast. On the other hand, our simulation results for the single-hop reliability show that ourproposed algorithm provides more than 99.6% of nodes up to d have received the warningwhen it is received at the destination.A more detailed set of simulations is done to better understand the effect of the successrate, q on MIN, particularly in comparison to Epidemic routing [19] which is a well-known35Chapter 2. Analysis of Message Dissemination in Vehicular Networks0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.950.850.90.951Success rate, qSingle−hop reliability 24 cars, Proposed Algorithm24 cars, Epidemic Routing50 cars, Proposed Algorithm50 cars, Epidemic RoutingFigure 2.7: Single-hop reliability vs. success rate, for d = 2000m.routing algorithm for vehicular networks (Fig. 2.7). q is calculated based on bit errorrate, thus higher bit error rates mean a lower success rate and vice versa. Note that theresults are within the same range for both algorithms and both schemes perform veryrobust against bad channel conditions. For the proposed algorithm, this again comes fromthe two-time reception opportunity that we deliberately included in our forwarding policyas discussed in Section 2.5. These observations clearly yield that the proposed methodeffectively utilizes the trade-off between delay and reliability.Next, we compare (in terms of delay) our proposed forwarding algorithm in section 2.5,MIN, with three well-known forwarding approaches for vehicular networks, i.e., VADD[20], D-Greedy [21], and Epidemic routing [19]. For the sake of fairness, we implementeda broadcast-based version of Epidemic routing and D-greedy to be able to compare theirresults with the outcome of MIN. The results are for the case where the end-to-end re-liability is 95%. As you can see, MIN outperforms other approaches, significantly. Themain reason is the concept of back-off counter to minimize collisions and the fact that mostpackets are sent with the minimum value of BCi, i.e., 1. The results from the simulation36Chapter 2. Analysis of Message Dissemination in Vehicular Networks10 20 30 40 50 60 7000.511.522.533.5Number of CarsAverage Delivery Delay (sec) Proposed AlgorithmEpidemicVADDD−GreedyFigure 2.8: Average delivery delay varying number of cars, for d = 2000m.show that for more than 95% of the time, the transmitter’s back-off counter value is 4or less. On the other hand, other methods use normal exponential back-off procedure inIEEE 802.11 which leads to unnecessary silent periods in this specific scenario. Epidemicrouting’s performance is in particular worse than others because of the gossip-based natureof it. Note that the main advantage of our algorithm is to achieve high single-hop/end-to-end reliability, which is almost the same as other approaches’ values, in a much shortertime.2.7 SummaryIn this chapter and in two steps, we proposed a mathematical model to study delay-reliability characteristics of information dissemination in vehicular networks. We startedwith a simplified model for the channel and then the model was enhanced using Ricianfading which is the most realistic channel model for a vehicular environment. Using theinsights we got from the presented model, we proposed a distributed forwarding policy,named Middle Is Next, MIN. In the end, we validated our mathematical model and also37Chapter 2. Analysis of Message Dissemination in Vehicular Networksshowed how our proposed forwarding scheme outperform other well-known approachesusing extensive simulations.38Chapter 3Analysis of Message Delivery Delayin Vehicular Networks3.1 IntroductionOne of the main ingredients in many data dissemination schemes for vehicular networksis frequent broadcasting of the location by each car. However, this broadcasting couldresult in broadcast storm problem [32] because of which the delay is hugely increased andresources are wasted. In this chapter and as our first contribution, we study how thedelivery delay is impacted by contention and collision.Studying traffic traces suggests that cars, especially on highways, tend to form discon-nected groups [10]. In other words, if one could look at the highways from above, shewould see some islands of grouped cars. This is called the partitioning problem. Everycar is connected to other cars in the same island either in a single hop or multiple hops.In fact, there are two cases for disseminating a message in a vehicular network: 1) withinan island 2) between islands. In the first case, the message is forwarded very fast usingwireless transmissions. In the second case, the last car that has the message is responsiblefor carrying it until there is a vehicle in its transmission range, rt. There is a commonassumption in the research community which says the inter-vehicle distances (IVDs) inThis chapter is based on the following paper:Rostamzadeh, K. and Gopalakrishnan, S.;, “Analysis of Message Delivery Delay in Vehicular Networks,”accepted to be published in IEEE Transactions on Vehicular Technology, Aug. 2014.39Chapter 3. Analysis of Message Delivery Delay in Vehicular Networksboth above-mentioned cases follow the same exponential distribution [11–13]. We showusing extensive simulations that this assumption is wrong. This interesting observationhas a huge impact on modelling the delivery delay. Based on this observation, we proposea new two-variable model for IVDs which is used in our delay model.Next and as our third contribution, we propose a mathematical model for the totaldelivery delay which includes a Markov chain to address the partitioning problem. To thebest of our knowledge, this is the first delay model that both captures physical (presentedin Chapter 2) and MAC layers’ characteristics and addresses the partitioning problem. Theresults of this model can be used by urban traffic designers to enhance the traffic conditionsand safety level in a city. Finally, our proposed model is validated using simulations.3.2 Related WorkDelay-reliability analysis constitutes the majority of analytical models in the literature.Suthaputchakun et al. proposed some modifications to IEEE 802.11p standard in order todecrease delay and increase the message dissemination speed [33]. Modifications includelowering the Distributed Inter-Frame Space (DIFS) period and also partitioning the trans-mission range to small sectors and picking the furthest vehicle as the next transmitter.The single-hop reliability and more importantly the end-to-end delay are two importantparameters missing in their analysis. The problem of where to place road side units (RSUs)is addressed by Abdrabou et al. [34]. Abdrabou et al. analyzed the delivery delay in aspecial case when there is no vehicle in the transmission range and cars use the oppositetraffic for delivering their messages. Then, the maximum inter-RSU distance to achieve adesired delay is studied. This work does not consider the MAC layer characteristics andtheir huge effect on the delay. Apart from that, this analysis is applicable only to a specificforwarding policy.40Chapter 3. Analysis of Message Delivery Delay in Vehicular NetworksA delay model for message propagation in vehicular networks is presented by Liu etal. [35]. Their model is only for one road segment and it is mainly focused on delayin the carry mode. The channel is also assumed to be perfect. Analytical bounds fordissemination distance and hitting time, i.e., the amount of time the message takes toinform nodes at certain locations, are calculated by Li and Wang [36]. Authors assumeda random mobility for cars which is very different from an actual vehicular network. Onthe other hand and even though the hitting time is helpful in understanding the deliverydelay, it is not clear how exactly these two metrics are related. An analytical model forthe average forwarding distance in message dissemination in vehicular networks with twoclasses of traffic is presented by Khabazian et al. [37]. Authors assumed a one-dimensionalnetwork with stationary vehicles. One of the findings of this work is that the probability ofa receiving node being exposed to interference increases with the increase of transmissionrange.Application of multi-path routing and its impact on the end-to-end reliability anddelay is investigated by Huang and Fang [38]. They showed that by careful path selection,multi-path routing performs better than single path routing, and it consumes almost thesame energy. Abdrabou and Zhuang proposed an analytical upper bound on deliverydelay in vehicular network [39]. Their approach is only for single-hop communication fromthe source to an RSU, and it does not consider physical and MAC layer delays. TheShared-Trajectory-based Data Forwarding Scheme utilizes the vehicle shared trajectoryinformation to predict encounters and then routes the messages based on this prediction[40]. Although it is efficient in unicast application by finding faster paths, it relies heavilyon global trajectory information exchange between cars which is unrealistic considering thenumber of vehicles in a city. Static-node-assisted Adaptive Data dissemination in Vehicularnetworks is proposed by Ding and Xiao [41] which uses static nodes at intersections to store41Chapter 3. Analysis of Message Delivery Delay in Vehicular NetworksIncident locationFigure 3.1: A safety warning dissemination example. Arrows represent successful trans-missions between neighbours and dashed arcs are transmission ranges of the transmitters.the data when there is no car to forward the message. When an optimal path becomesavailable, the static node relays the message in which case the delivery delay is reduced.3.3 MAC Layer Analysis3.3.1 System ModelThe inter-vehicle distances, X, are assumed to follow an exponential distribution withparameter λs (veh/km) [12]. They are also assumed to be identically and independentlydistributed. In this section, we consider a dense enough network in which every car finds(at least) one car in its transmission range to forward its packet. The general case wherethere is disconnectivity in the network is studied in Section 3.4. It is also assumed thatthe traffic has a normal flow, so there is no traffic jams.A typical scenario is given in Fig. 3.1, where warnings are generated and transmittedafter an incident, e.g., an accident. Let Pf denote the probability that a vehicle decides42Chapter 3. Analysis of Message Delivery Delay in Vehicular Networksto participate in the forwarding process which is the same for all vehicles. Therefore, theprobability of having k cars in the transmission range of a sample vehicle i, denoted asPr(n = k), follows a Poisson point process with parameter λ and is defined asPr(n = k) =e−λrt(λrt)kk!(3.1)λ’s distribution can be written as (2):λ = Pfλs∫ rt0Fq(SIRmin|xd)fxd(xd)dxd , (3.2)where rt is the transmission range of the vehicle i, and Fq(SIRmin) is the distributionof the success rate for a given minimum signal to interference ratio of SIRmin. A list ofnotations used in this chapter is presented in the beginning of this dissertation.Delivery delay is assumed to be the time it takes a message from the moment it iscreated by the source vehicle (due to an accident for example), until a copy of that messageis received by the destination vehicle or a vehicle past the area of relevance with radius d.Other than the transmission rate (including the type of modulation and coding and thebit rate), issues related to the channel and the MAC layer in addition to the partitioningproblem are the main contributors to the delivery delay. On the physical layer side, pathloss, channel fading, shadowing, and interference from far-away nodes working at the samefrequency channel are the major causes of packet loss and therefore more delay (studiedin Chapter 2). Delay can also be increased by contention, collision and low throughput inthe MAC layer (Section 3.3.2). On the other hand, when there is no vehicle to which themessage can be forwarded, it has to be carried by last receiver and this process significantlyincreases the delivery delay (Section 3.4).43Chapter 3. Analysis of Message Delivery Delay in Vehicular Networks3.3.2 Mathematical AnalysisIn this section, our mathematical modelling to analyze delay-reliability characteristics ofinformation dissemination in vehicular networks (Chapter 2) is considered. Building onthe system model explained in Section 3.3.1, we enhance the previous model by addingthe MAC layer features to our design. Note that even when the channel is good andthere are packets to be sent, a vehicle may not be able to send its packet simply becausethere is competition to capture the medium. This means more delay and even a degree ofdegradation in reliability due to collisions. Depending on the MAC protocol the network isusing, modelling MAC could be challenging. MIN (presented in Chapter 2) is selected asthe improvement to our mathematical modelling because it outperforms other well-knownforwarding protocols.In MIN, a given car i after receiving a message successfully sets a back-off counter ofBCi defined asBCi = be(λs(zi− rt2 ))22 c , (3.3)where zi is the distance between car i, i.e., a car that has successfully received the message,and the transmitter. This means zi is an exponential random variable with parameter λ,as discussed in Section 3.3.1.It is assumed that cars know their location using GPS or a similar device. In addition,each transmitter inserts its location into the message and then forwards it to its neighbours,therefore zi can be easily calculated using i’s and transmitter’s locations. Note that alltransmitter’s neighbours who successfully received the message set a value for their back-offcounters and start counting down. The neighbour with the smallest BCi reaches zero firstand it starts transmitting when other neighbours stop counting. This is an effective wayfor alleviating contention and eliminating collisions without sacrificing delay. For a given44Chapter 3. Analysis of Message Delivery Delay in Vehicular Networkstransmitter i, MIN always tries to select the car closest to the middle of i’s transmissionrange, rt/2, as the next transmitter. If there are two cars on both sides of zi = rt/2 andwith the same distance from it, MIN picks the farther vehicle (from i) to improve thedelay. This decision is made in the receiver vehicle as it can easily determine whether it islocated before or after the midpoint (using its location, the transmitter’s location, and thetransmission range). Since zi is a random variable, BCi is also a random variable. Basedon this discussion and for a typical retransmission of the message, the expected value ofthe back-off counter, E[BC], isE[BC] = BC =Nmax∑k=1P (BCi ≥ k)= P (BCi ≥ 1) + P (BCi ≥ 2) + ...+ P (BCi ≥ k)+ ... + P (BCi ≥ Nmax) (3.4)where Nmax is the maximum value for BCi which happens when zi = rt. In defining BC,the expected value’s property for non-negative random variables is used. It is easy to seethat P (BCi ≥ 1) = 1. For the other terms, consider the example term of P (BCi ≥ k). WehaveP (BCi ≥ k) = P((zi −rt2)2 ≥2ln(k)λ2s)= P((zi ≥rt2+ c) ∪ (0 ≤ zi ≤rt2− c))= P (zi ≥rt2+ c) + P (0 ≤ zi ≤rt2− c)= e−λ(rt2 +c) + 1− e−λ(rt2 −c) (3.5)where c =√2ln(k)λs. In the second line of (3.5), we used the fact that (zi ≥ rt2 + c) ∩ (0 ≤zi ≤ rt2 − c) = ∅.45Chapter 3. Analysis of Message Delivery Delay in Vehicular NetworksBy substituting (3.5) in (3.4), BC can be determined. The delivery delay can nowbe computed using the average back-off counter. There are on average kmin transmissionrounds for achieving an end-to-end reliability of Pmin. kmin can be determined usingthe Poisson distribution for number of transmitters and the Gamma distribution for thedistance covered by them (details in Chapter 2). Therefore, using (3.4), the average deliverydelay, delayF , is calculated asdelayF = kmin × (BC + 1)× Ts , (3.6)where Ts is the duration of one time slot or equivalently the duration of one transmissionround because there is a transmission in each slot. Note that delivery delay in (3.6) is calleddelayF to reflect the fact that it only represents the delay when there is no disconnectivityin the network. However, in a realistic scenario there are periods when there is no vehiclein the transmission range and the message should be carried by the current car until a newcar is detected. More details are given in Section 3.4.The validity of the presented MAC analysis is evaluated through a set of simulations.We implemented a highway scenario in MATLAB where vehicles’ speed ranges from 80km/h to 130 km/h. As for the propagation model, Rician fading model which is provedto be appropriate in capturing the channel behaviour, is used [26, 27]. In Rician fading,there is a strong dominant signal, e.g., line of sight wave, in addition to reflected andscattered waves. The ratio of the dominant component’s power over the scattered poweris called Rician K-factor. A value of K = 10 is shown to best follow the real channelcharacteristics in a vehicular environment [27]. Packet length and data rate are 200 B and6 Mbit/s, respectively. First, we compare the delivery delay between the proposed modelin this section and our previous model (Chapter 2) versus the simulation (as a measure of46Chapter 3. Analysis of Message Delivery Delay in Vehicular Networksreal traces) for different vehicle densities (see Fig. 3.2). As it is seen, the new model issignificantly closer to the simulation. The difference between the previous model and thesimulation is between 14% and 37% while the difference between the simulation and thenew model is between 3% and 12%. Also note that the new model can effectively followthe slope of change in the delay, whereas the previous model is almost linear.10 15 20 25 30100150200250300350400450500 Average vehicle density, λs (veh/km)Average delivery delay (msec)SimulationNew ModelPrevious ModelFigure 3.2: Average delay for delivery to the distance of d = 2000 m.One of the main advantages of MIN over other forwarding mechanisms and MAC pro-tocols is that it dynamically changes the forwarding probability based on the perceivedvehicle density. This unique feature is examined by calculating the corresponding Pf thatresults in delayF = delaysim ± 5% (see Fig. 3.3). d represents the delivery distance or theradius of interest to where the message is expected to reach. As expected, MIN decreasesthe forwarding probability as the vehicle density increases to avoid collision and to utilizethe medium. The other observation is that Pf declines as d becomes bigger. One possiblereason is because when d has a bigger value, it translates to an expected bigger delay toachieve the same end-to-end reliability. In other words, delivery delay is not as tight asother cases when d is small and, therefore, MIN decrements Pf a little bit to achieve evenbetter performance in terms of collision and communication cost.47Chapter 3. Analysis of Message Delivery Delay in Vehicular NetworksSince the proposed model (using MIN) is based on calculating the average back-offcounter in order to come up with a value for delay, the same analysis is also applicableto other MAC layers as long as they have a back-off counter mechanism to cope withcontention. So, it is a general model which approximates the MAC layer’s contributionsto the delivery delay for a range of MAC protocols.At this point, the proposed model for delay in (3.6) captures the message disseminationcharacteristics in the physical and MAC layers when there is always a neighbour to whichthe message can be forwarded. However, in an actual vehicular network, cars can travelfor a long distance without coming across another car in which case the last vehicle shouldcarry the message. The vehicular network in this case is called partitioned. In the nextsection, we make the delay model more precise by addressing the partitioning problem.15 20 25 300.40.50.60.70.80.91Average vehicle density, λs (veh/km)Forwarding probability, Pf d =1500md = 2000md = 3500mFigure 3.3: Forwarding probability of MIN in order to achieve delayF = simulation delay±5%.3.4 Partitioning AnalysisStudying traffic traces, specially on highways, shows that vehicles tend to form isolatedislands [10]. This means that the delay model proposed in (3.6) captures only part of48Chapter 3. Analysis of Message Delivery Delay in Vehicular Networkstotal message delivery delay, and we also need to address the other part. A message in avehicular network propagates only in two ways: 1) Forward phase, when vehicles are closeenough in which case they transmit the message to each other. 2) Carry phase, when thedistance between two successive vehicles is larger than each vehicle’s transmission range,i.e., rt, and the message is carried by the last vehicle until it finds another vehicle in itsrange. Since the speed of message dissemination in each of these cases is dramaticallydifferent, one solution is to calculate the delay in each phase and then add them togetherto get the total delay. delayF which represents the delay in the forward phase was definedin Section 3.3. Delay in the carry phase, denoted by delayC , depends mainly on the velocityof vehicles. The analysis in this section is based on the system model presented in Section3.3.1 except for the fact that there are both Forward and Carry phases in the system.Although the inter-vehicle distance, X, is assumed and proved to follow an exponentialdistribution with parameter λs [12, 13], the values of inter-vehicle distance in this discussionare divided into two categories, i.e., forward and carry, and the new distribution for eachcategory could be different from the original exponential. To address this concern and tobetter understand the behaviour of data in each category, an extensive set of simulationswere done. We implemented a highway scenario with d = 2000 and λs = 20 veh/km.Inter-vehicle distances during the simulation were recorded separately for the connectedparts and disconnected parts. Then, using EasyFit [42], each of those data sets was fittedto a curve. Although exponential distribution was a very good fit for the forward phase’sdata set, surprisingly, the same was not true for the carry phase (see Fig. 3.4 and Fig.3.5).As seen in these figures, the exponential distribution does not fit the histogram forthe carry phase. In fact, a two-parameter (or shifted) exponential distribution is one ofthe best fits for this set of data. This observation makes sense because every point in the49Chapter 3. Analysis of Message Delivery Delay in Vehicular Networks200 400 600 800 100001234567x 105Xf(X) Histogram of inter−vehicle distancesExponential distribution fitFigure 3.4: The histogram and the exponential fit for the carry phase.carry phase’s data is taken when there is no vehicle in the neighbourhood and the networkis disconnected. Thus, one could assume those distances are greater than the effective(based on channel conditions) transmission range, rt, which means that the shift in thetwo-parameter exponential distribution should be equal to rt. In other words, up to thatrt there is nothing and once that point is passed, everything again follows an exponentialdistribution. That is why both distributions have almost identical parameters. For thecase when all values of X are taken into account, exponential distribution is still a verygood fit (see Fig. 3.6). This is consistent with the mentioned common assumption in theliterature.Based on the above discussion, when X ≤ rt, the rate of the exponential distributionis λ1 = λs. However, when X > rt, the shifted exponential distribution is in place and thenew rate, λ2, will be the shifted version of λ1 as followsλ2 =11λ1+ rt(3.7)50Chapter 3. Analysis of Message Delivery Delay in Vehicular Networks0 50 100 150 200 250 3000123456x 106Xf(X) Histogram of inter−vehicle distancesExponential distribution fitFigure 3.5: The histogram and the exponential fit for the forward phase.Since X for both the forward and carry phases follows an exponential distribution, theinformation propagation delay in a vehicular network can be modelled using a two-stateMarkov process. Figure 3.7 shows the Markov chain of this alternating renewal process aswell as the transition rates. Let piF and piC denote the limiting (or stationary) probabilitiesfor this Markov chain. That is, they will be the unique non-negative solution ofpiF + piC = 1piF × 11λ1+rt= piC × λ1(3.8)By solving (3.8), we getpiF = 1+rtλ12+rtλ1piC = 12+rtλ1(3.9)51Chapter 3. Analysis of Message Delivery Delay in Vehicular Networks0 100 200 300 400 500 600012345x 106Xf(X) Histogram of inter−vehicle distancesExponential distribution fitFigure 3.6: The histogram and the exponential fit for the total case.ForwardCarryߣ 1ܲሺܺݎ ݐሻ ܲሺܺݎ ݐሻߣ 2 Figure 3.7: The two-state Markov chain for modelling the information propagation in apartitioned vehicular network.For a message to reach X = d, a number of Forward and Carry cycles should berepeated. It is also possible to use a renewal process to better understand this procedure.An outside observer looking at the traversed distance, would see some amount of time themessage traveling in the Forward state followed by some amount of time when it travelsin the Carry state. This sequence of FC continues (renews) until the message reaches itsdestination. Therefore, if the average time spent in one sequence, i.e., time in F plus timein C, is calculated, the total delivery delay to X = d could be determined by multiplyingthe sequence delay by the ratio Rd which is defined as52Chapter 3. Analysis of Message Delivery Delay in Vehicular NetworksRd =ddistFC, (3.10)where distFC is a random variable and represents the distance traveled in one sequence ofFC. To calculate the average distFC or E[distFC ], first we need to determine how manytimes on average, a message loops back to the Forward state. Consider a geometric randomvariable Nf with failure probability of p = P (X ≤ rt) = 1 − e−λ1rt . Then, Nf representsthe number of times a message stays in F. The average number of times until the firstsuccess, i.e., transitioning to C, is as followsE[Nf ] =p1− p= eλ1rt − 1Using the fact that in the Carry state, the message travels 1λ2 and in the Forward state,the message travels 1λ1 in each transmission, we haveE[distFC ] =E[Nf ]λ1+1λ2(3.11)Since Rd is also a random variable and a convex function of distFC , using Jensen’sinequality we haveE[Rd] = E[ddistFC] ≥dE[distFC ](3.12)By substituting (3.11) in (3.12), E[Rd]min is determined. Then, the average total53Chapter 3. Analysis of Message Delivery Delay in Vehicular Networksdelivery delay, delayT , can be expressed as a function of delayF and delayC as followsdelayT = (piF × delayF + piC × delayC)× E[Rd]min (3.13)where piF and piC are given in (3.9), delayF is derived from (3.6), and delayC =1/λ2Vwhere,V is the average speed of vehicles. Since the minimum value for E[Rd] is used in (3.13),this equation gives a lower bound for the delivery delay.Based on (3.9), as λs increases, i.e., higher vehicle density, the percentage of time onecar spends in the forward state, i.e., piF , also goes up. This is expected because the morevehicle density, the higher the chances of a car finding another car in its transmissionrange. A bigger value of piF itself results in a smaller value for delayT as delayC is alwaysmuch bigger than delayF . This is again because when vehicles are mainly in the forwardstate, the message propagates very fast. We believe the delay expression in (3.13) very wellcaptures the behaviour of information dissemination in vehicular networks. This claim isvalidated Section 3.5 when a set of simulations is presented to evaluate the proposed modelfor delay.As mentioned in the introduction, the delay model presented in this chapter can be usedby network designers to tune important parameters such as transmission power, back-offduration, and slot time. For example, if the network is sparse, i.e., for small values of λs,and the message is usually in the carry state, delayC and consequently delayT become verylarge. This is a sign that tells the network designer to increase the transmission powerto have a higher transmission range. Similarly, if the value of BCi given in (3.3) is big,it increases delayF and consequently delayT , in which case the network designer shouldtry to set MAC layer parameters in a way that the average value of back-off counter isreduced. Slot time can change delayF according to (3.6). Similar to previous discussion,54Chapter 3. Analysis of Message Delivery Delay in Vehicular Networksthe network designer can change the slot time based on the delay requirements.Note that although there is no notion of traffic light in our analysis, our proposed delaymodel is general enough in the sense that time a car (and thus its message) spends on ared light is captured in the Carry state. Therefore, having traffic lights means a biggerdelayC .Finally, it is worth mentioning that although the model in (3.13) mainly represents thedelay for Middle Is Next or MIN forwarding algorithm because delayF calculated in (3.6)is based on MIN, the second term, i.e., delayC is the same in any forwarding algorithm forvehicular networks. In addition, the presented model in this section for calculating delayTand the stationary probabilities, is applicable to any forwarding policy. One only needs tocalculate delayF for that specific algorithm and then plug it into (3.13) to determine theaverage delivery delay. This is a big value-add for our proposed delay model because wehave been able to propose a mathematically tractable model to compute the delivery delayin a vehicular network despite all the complications associated with modelling this highlydynamic network.3.5 Performance EvaluationThe objectives of this section are 1) to validate the proposed mathematical model forinformation dissemination delay in a vehicular network presented in Section 3.4, 2) to assessMIN forwarding policy against three other well-known forwarding methods for vehicularnetworks, i.e., Epidemic routing [19], SADV [41], and VADD [20]. Since SADV relies onstatic nodes at intersections, we use it as a benchmark in the urban scenario mentioned inthe simulation setup. The metrics we use to address this objectives are delivery delay andthe end-to-end reliability or packet delivery ratio (PDR). A detailed definition for deliverydelay is given in Section 3.3.1. PDR is the average number of packets that are successfully55Chapter 3. Analysis of Message Delivery Delay in Vehicular Networksreceived by vehicles in a certain radius in a given time.3.5.1 Simulation SetupWe have implemented a MATLAB-based vehicular network simulator. The velocity of carsis assumed to follow a normal distribution according to work by Wisitpongphan et al. [13]using real traffic traces. Traffic is assumed to move in one direction. In fact using thetraffic on the opposite direction is shown to improve the information dissemination processin terms of delay and reliability [10, 13, 43]. Therefore, the highway scenario presentedin this section gives an upper bound on the delivery delay and it is safe to assume thatthe actual delay is equal or less than the presented results. Simulation parameters aresummarized in Table 3.1. Note that a bigger packet size, 500(Bytes) for instance, does notimpact the overall delivery delay as transmission delay is negligible compared with otherdelays caused by contention and partitioning. For a data rate of 6 Mb/s, the difference intransmission delay between packet sizes of 200(Bytes) and 500(Bytes) is only 0.4 msec.There are two scenarios that are implemented at which the mentioned objectives areaddressed. Even though, it is fair to assume that results for a semi-urban or rural scenariowould fall between these two scenarios, we believe vehicular networks are mainly designedfor urban or highway areas where may safety-related applications can be defined.• Highway Scenario: All vehicles are moving at the same direction. A source startsthe dissemination at X = 0, and the message travels until it reaches X = 3000m.Vehicles’ speed ranges from 80 km/h to 130 km/h.• Urban Scenario: A grid of size 3000m by 1000m with 14 intersections is simulated.Vehicles’ speed ranges from 30 km/h to 70 km/h. Each vehicle at an intersectioneither turns (left or right) or goes straight, with the same probability of 1/3. Sourcesand destinations are paired up randomly on the edges of the grid. Even though56Chapter 3. Analysis of Message Delivery Delay in Vehicular NetworksTable 3.1: Configuration ParametersParameter ValueChannel modelling Rician with K = 10Packet length (B) 200MAC standard IEEE 802.11pCommunication frequency 5.9 GHzData rate (Mbit/s) 6Data Traffic Periodic with T = 50 msecVehicle Length (m) 5Slot duration 13 µsSIFS 32 µsDIFS 58 µsScenario Highway UrbanMinimum vehicle speed (km/h) 80 40Maximum vehicle speed (km/h) 130 70Average vehicle speed (km/h) 100 50there is no traffic light, it is fair to assume that with high probability, there is alwaysanother car in the intersection that is in the transmission range of the car carryingthe message. Therefore, the message can be transmitted even at a red light.3.5.2 Delay and Reliability in Highway ScenarioThe average delivery delay in the highway scenario is reported in Fig. 3.8. As it can beseen, the proposed modelling for the delay in Section 3.4 and particularly Eq. (3.13) almostperfectly follows the actual delivery delay of MIN with the increase of vehicle density. Thedifference between the delay derived from (3.13) and the simulation delay is between 4%and 13%. This figure also shows the how MIN outperforms Epidemic routing and VADDin terms of delay. MIN delivers the messages 47% − 410% faster than Epidemic routingand 47% − 730% quicker than VADD. One can also see how the average delay decreasesas λs goes up. This is in fact because as the number of cars increases there is more chancefor a transmission which means the message is in the Forward state more than before.Next, we investigate the packet delivery ratio of MIN against Epidemic routing and57Chapter 3. Analysis of Message Delivery Delay in Vehicular Networks15 20 25 30 3505001000150020002500Average vehicle density, λs (veh/km)Average delivery delay (msec) Proposed modelMINEpidemicVADDFigure 3.8: Average delivery delay in the highway scenario for d = 3000 m.VADD versus delay for λs = 20 (see Fig. 3.9). Note that MIN achieves a high packetdelivery ratio in a shorter amount of time. For example, it takes 1204 msec for MIN toget to PDR = 80% while to get to the same PDR, it takes 2380 msec and 3553 msec forEpidemic routing and VADD, respectively.3.5.3 Delay and Reliability in Urban ScenarioAnother set of simulations explores how the results change when vehicles are moving inan urban setting. We start with the average delivery delay versus number of vehicles(see Fig. 3.10). As it is shown, the proposed mathematical model in (3.13) for the totaldelay matches the actual delay from simulation. The other observation is the differencein delivery delays among different algorithms. Again, MIN delivers the messages muchfaster than Epidemic routing, SADV, and VADD. This time, however, the results arecloser compared to the highway scenario especially when the vehicle density is higher;the difference is anything from 74% to 83%, from 81% to 109%, and from 84% to 198%compared to Epidemic routing, SADV, and VADD, respectively. One reason could be the58Chapter 3. Analysis of Message Delivery Delay in Vehicular Networks0 1000 2000 3000 4000 5000020406080100Delay (msec)Packet delivery ratio (%) MINEpidemicVADDFigure 3.9: Packet delivery ratio in the highway scenario for λs = 20 veh/km and d = 3000m.fact that in an urban setting there are several road segments and vehicles scatter all aroundthe map. Therefore, all forwarding methods turn to a near-gossiping algorithm. To verifythis speculation, we repeat the urban scenario but this time with 8 intersections (see Fig.3.11). As shown from the results, the difference between MIN and VADD, SADV, andEpidemic routing is bigger compared to Fig. 3.10, i.e., the difference is now from 82% to153%, from 93% to 211%, and from 140% to 313% in comparison with Epidemic routing,SADV, and VADD, respectively. Note that all four algorithms produce bigger numbers fordelivery delay compared to Fig. 3.8. The reason is that more transmissions are neededdue to the fact that cars do not stay on one segment all the time and they may turn ateach intersection. Again, the general trend is that as the network gets denser, the averagedelay decays.Finally, Fig. 3.12 shows how the PDR changes with delay. Again, MIN reaches a highPDR in a shorter amount of time. As an example and for PDR = 80%, the delay forMIN, Epidemic routing, SADV, and VADD are 1432 msec, 2680 msec, 2816 msec, and3966 msec, respectively.59Chapter 3. Analysis of Message Delivery Delay in Vehicular Networks50 60 70 80 90 1000123456789Number of vehiclesAverage delivery delay (sec) Proposed modelMINEpidemicSADVVADDFigure 3.10: Average delivery delay in the urban scenario.3.6 SummaryIn this chapter, we build on our proposed model in Chap. 2. We first present a math-ematical analysis of MAC layer’s effects on delivery delay. Then, by means of extensivesimulations, we show that in contrary to the common assumption, inter-vehicle distancesfollow different distributions in the Forward and Carry states. After that and using aMarkov chain, we propose an additional layer to our model to address the partitioningproblem. Simulation results validate the accuracy of out model in both urban and high-way scenarios. Delay for other scenarios such as rural areas is expected to fall in betweenthese two scenarios. The final delivery delay model can be used by urban traffic designersto enhance the traffic conditions and safety level in a city. As an example, if the deliverydelay for message propagation is calculated using our model, an urban designer can setspeed limits in different zones such that a fast delivery is guaranteed even in the worst-casescenario.60Chapter 3. Analysis of Message Delivery Delay in Vehicular Networks50 60 70 80 90 1000123456789Number of vehiclesAverage delivery delay (sec) Proposed modelMINEpidemicSADVVADDFigure 3.11: Average delivery delay in the urban scenario when there are fewer intersec-tions.0 1 2 3 4 50102030405060708090100Delay (sec)Packet delivery ratio (%) MINEpidemicSADVVADDFigure 3.12: Packet delivery ratio in the urban scenario for 72 vehicles.61Chapter 4A Trust-based InformationDissemination Framework forVehicular Networks4.1 IntroductionOver the past few years, researchers have proposed several broadcasting and unicastingrouting protocols for Vehicular Networks (VNets) that minimize the delivery delay or thecommunication interference [19–21]. However, the missing key point in those methods isthe security analysis. A node is assumed to be malicious when it manipulates or inten-tionally drops a message. Consider this simple example that explains the significance ofthe problem: suppose one vehicle has a message and it has two neighbours from which itchooses to forward its message. One of the neighbours is a trustworthy node that relaysevery message without any problem; however, routing from that node increases the delay.The other neighbour on the other hand, is on a fast route to the destination but it ismalicious and drops the messages half the time. Now, based on a normal routing protocolThis chapter is based on the following papers:Rostamzadeh, K.; Nicanfar, H.; Torabi, N.; Gopalakrishnan, S.; Leung, V.;, “A Context-aware Trust-based Information Dissemination Framework for Vehicular Networks,” accepted to be published in IEEEInternet of Things Journal, Nov. 2014.Rostamzadeh, K.; Nicanfar, H.; Gopalakrishnan, S.; Leung, V.;, “A Context-aware Trust-based Commu-nication Framework for VNets,” in Proc. of IEEE Wireless Communications and Networking Conference(WCNC), pp. 3296-3301, Apr. 2014.62Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksthat its only focus is on minimizing the delay, the malicious node will be selected to routethe message faster. However, there is a chance of 50% that the message will be dropped atthis node and it never reaches the destination. So, ignoring malicious nodes can void thewhole algorithm efforts to minimize the delay. This example clearly shows why there is aneed for a safe and reliable communication framework in vehicular networks. Note that ourfocus is on having a secure packet delivery in addition to a reliable one. Packet reliability,a.k.a. packet delivery ratio, could be damaged by environment and network characteristicssuch as channel fading or collisions. Secure packet delivery on the other hand, can be hurtbecause of attacks and intentional manipulations by malicious nodes.Trust is a human and psychological factor that is historically very well known in thesocial interactions. Using Artificial Intelligence (AI) and bringing the concept of the trustto the Information and Communication Technology (ICT) has been proposed and studiedduring the last decade [44]. For instance, trust of a relay node, i, can be defined as thenumber of packets that i has relayed without manipulating them, out of the total numberof packets given to the i to be relayed. Then, the probability of i relaying a new packet isthe trust value of i based on this simple rule: “A node acts the same way that it has doneso far”. As our first contribution, we leverage this concept to cover a range of applicationrequirements such as security, privacy, delay, and reliability to name a few. There is a trustvalue calculated for each of these parameters. Then, we develop a function of all these trustvalues to calculate the total trust for each path, which is our reference for choosing thebest route.Trust in a vehicular network faces two main challenges: first challenge is the speed ofvehicles that changes the topology constantly and minimizes the contact times betweenthe nodes. The second challenge is the lack of a centralized third party to evaluate andmaintain the trust values. Majority of the trust models proposed for vehicular networks63Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksare entity-centric in which the focus is on verifying the vehicle credentials [45]. Oncethe source is authenticated, the message can be trusted. There are a few data-centricapproaches that focus on the correctness of the received message, instead [46]. Both ofthese models suffer from scalability and the entity-centric models have the assumption thatthere is always a third-party certificate issuer in the vicinity that is often not valid in thecontext of vehicular networks.We present a survey of trust systems and routing protocols in vehicular networks. Thenas our next contribution, we propose FACT: Framework for Application-oriented Context-aware Trust-based communication in vehicular networks. There are two modules in FACT::Admission and Dissemination. FACT is “space-centric”, meaning location plays a key role.After receiving a message, FACT makes sure the origin and the content of the message aretrusted and it traverses a trusted route without any attacks. This is done in the Admissionmodule. Then, the message is sent to the Dissemination module where it is sent on atrusted path. Vehicular networks’ applications are categorized into three classes. For eachapplication in these classes, FACT (as a general framework) addresses the correspondingrequirements while the whole communication process is done in a trusted manner. Finally,FACT is validated through simulations. We show that in an untrusted network, FACToutperforms other well-known routing protocols.4.2 Related WorkSecure routing, privacy, and trust in vehicular networks have gained attention from theresearch community over the past few years. However, private communication is still in itsearly days, and routing remains challenging.The authors of [47] concentrate on trust in the peer-to-peer (P2P) file-sharing networks,based on the peers’ history of uploads, called EigenTrust. They proposed an algorithm64Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksaiming at decreasing the number of downloads of inauthentic files in the network thatassigns each peer a unique global trust value. They also described a distributed and securemethod to compute global trust values, based on Power iteration. In fact, peers use thesevalues to choose from whom they download, while the network identifies malicious peersand isolates them from the network. This proposal mainly concentrates on P2P and directlydownloading the files. However, in a dynamic environment, like vehicular networks, witha high mobility, using the concepts such as score manager is not feasible.The framework presented in [48] aimed at dealing with potentially untrustworthy infor-mation. The framework includes a computational trust model for estimating the amountof received information uncertainty. In order to realize the drivers goals, the frameworkalso has a probabilistic beliefs-desires-intentions agent system for reasoning about this un-certain information. In order to secure Delay-Tolerant Network (DTN) routing towardefficient trust establishment, iTrust scheme proposed by H. Zhu et al. [49], as proba-bilistic misbehaviour detection. They used a Trusted Authority (TA) to judge the nodesbehaviour, which is periodically available, based on the collected routing evidences andprobabilistically checking. For the TA to ensure the security of DTN routing at a reducedcost, they modelled the inspection game and used game theoretical analysis to demonstratethat, by setting an appropriate investigation probability. Also to improve the efficiencyof the proposed scheme, they allowed a dynamic detection probability determined by thetrust of users by correlating detection probability with the reputation of that node.The proposed mechanism in [50] aimed at ad-hoc environment by designing an AODVbased routing protocol that combines the hop count and trust value. When a source studiesdifferent path opportunities, it multiplies the trust value of each node to obtain the trustvalue of the path. Although it may be true in the packet delivery ratio, the trust value ofthe path cannot be always calculated by a multiplication of the trust value of the nodes65Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksalong the path, e.g. in anonymity based one. Moreover, the proposed routing protocol in[51] is trust-based aimed at MANET that concentrates on energy efficiency.SAT [45], a trust architecture for vehicular networks, reveals the identity of the usersby using a social network. The trust system proposed in [46], designed for the receiversand broadcast communication, shifts the concentration from the sender to the data itself.In fact, the content of the message defines the trust value even the message is generated bydifferent vehicles that have different trust levels. The Markov chain-based trust model forvehicular networks presented in [52] is a hybrid model evaluating trust based on the dataand the entity together, in order to filter out malicious and selfish nodes. Aside from thecomplexity of the proposed method, it is not clear how this algorithm works when thereis no connectivity in the network or when the application needs a set of delay-reliabilityrequirements.The aim of TRIP [53] is broadcast communication in vehicular networks. It is designedfor a receiver evaluating the trustworthiness of the received message, while the messagecan be accident (safety) or a weather condition (non-safety). Their guideline for designinga trust system in vehicular network identifies five characteristics such as: Simple, light andfast; Accurate; Scalable; Resilient to security and privacy threats; and Not dependent onmobility patterns. The scope of VARS (Vehicle Ad-hoc Network Reputation System) [54]is also broadcasting messages. A relay node in forwarding a message, generates its ownopinion based on the sender if it is known, or based on similar received messages in thepast, and sends the opinion along with the message. However, considering dynamic natureof vehicular networks, VARS mainly relies on others’ opinion along with indirect trustvalues for a receiver on trusting a message that is not trusted enough and valid sourcesfor the receiver. Moreover, the proposed trust model in [55] concentrates on broadcastcommunication of safety related messages where it is limited to utilizing the signature of66Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksa message issued by the originator to preserve trust of the messages.The trust model proposed by [56] is designed for senders. A sender finds similar vehiclesto forward the message. Finding similar nodes based on location, energy and brand is notpractical and does not guarantee of being a better candidate: the same brand does notmake any difference; a node with the same energy level cannot be a good one, if the senderis frustrated of low energy where it requires a neighbour with a higher energy; and energyis not a case in the vehicular networks at all.In a highway and reporting the traffic congestion, a malicious vehicle may sends boguscongestion information to others, which is the focus of D. Huang et al. in [57]. In theirdesign, they leveraged traffic flow theory to observe the Kinematic wave caused by con-gestion. So without a need to a centralized controlled congestion detection and predictionsystem, each vehicle only relies on local speed and distance measurements to validate thecongestion event that is sent by another vehicle. In [58], an RSU and beacon based trustmanagement system is proposed that aimed at broadcasting message opinions quickly.Therefore and in a privacy-enhanced VANET environment, if an internal attacker sendsor forwards forged messages, the message will be foiled. M. H. Eiza et al. [59] leveragedlocation and velocity information of vehicles in order to calculate link reliability for theirreliability-based routing scheme for VANETs. Their objective was routing process in whichthey tried to facilitate Quality of Service (QoS) support in it.In order to receive trusted traffic information by a vehicle, M. Teler et al. [60] designeda trust based security system, where regardless of source of the data, the trust is measuredfor individual pieces of data referring to a specific event. In this model, a driver evaluatedthe trust of received information, and then disseminates the trust value to other vehiclesin order to improve the accuracy in the trustworthiness of an event. In [61], a decentral-ized lightweight authentication scheme for vehicle-to-vehicle communication networks is67Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksproposed, which is called trust-extended authentication mechanism. In fact, they aimedat improving the performance of the authentication procedure by using the concept oftransitive trust relationships.In [62], authors proposed DTM2 aimed at issue of malicious and selfish nodes in theVANET. They used the concept of cost, in which they assumed a sender transmits a signal,which has a cost based on the message and sender behaviour, with its message to show aguarantee of the truthfulness of the message to the potential receivers. In this paradigm,the cost is calculated in a way that the cost increases when the behaviour of the sendergets worse. Therefore, the cost for the malicious and selfish nodes increases eventually, as apunishment. Similarly, the cost for the benign nodes decreases as a reward proportionallyto the signals value. In [63], C. Liao et al. brought into account the trustworthiness of themessage originator and the forwarding nodes, if any, to calculate the trust of the messageitself, in a V2V communication. They used the existing V2I communication facilitiesdeployed and managed by central traffic authorities for collection of the vehicle behaviourin a crowd-sourcing fashion.4.3 The Proposed Trust ModelIn this section, first we describe some of the definitions for our framework. Then, calcu-lations regarding trust value and the total trust are presented to be used in our design aspart of Section 4.4.The level of performing the expected service by a trustee is called satisfaction, whichin fact derived the trustworthiness. We assume the trust value to be a number between(0, 1). The four major parts of the trust system are initial trust, trust metric, operationand trust management. Identifying the appropriate trust metric, which is relevant to theapplication, and a mechanism to measure the metric, e.g. a binary or percentage unit, are68Chapter 4. A Trust-based Information Dissemination Framework for Vehicular NetworksN 5N 6N 4N 3N 2N 1N 8N 7Figure 4.1: Right: map of the city divided to different neighbourhoods. Left: each neigh-bourhood consists of different road segments.part of a trust system. In addition, designing a system that manages the trust is needed,which can be centralized, distributed or a combination of them.Trust assessment can be direct or indirect. In direct assessment, a trustor relies on itsown experience about a trustee. For instance, in a wireless communication environment,if node S (trustor) sends a packet to node R (trustee), which is one hop away, to forward(service) the packet to node D, which is two hops away, S can overhear R and observes ifR is genuinely sending the packet. On the other hand and in indirect assessment, a trustorrelies on other nodes experience of dealing with a trustee.FACT is based on carry-and-forward information dissemination. Therefore, if there isno vehicle in the vicinity, the vehicle carrying the message should continue carrying themessage until it comes across another vehicle and then decide on forwarding the message.The rest of this section is based on the assumption of having at least one vehicle in thetransmission range. FACT is a general framework that allows messages of different cate-gories of traffic to be securely delivered to their destinations based on their requirements.As shown in Fig. 4.1, all vehicles maintain a trust map which divides the city into severalneighbourhoods and each neighbourhood itself is divided to multiple segments. A segment69Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksis part of the road between two intersections. Our work is not limited to a specific sectoringmethod; it can be symmetrical or asymmetrical sectoring. Map division should be donein a way that meets the network administrator’s resolution requirement without imposingexcessive overhead. In the mentioned trust map and for every segment, a trust value TR,is recorded for each time of the day in each specific day of the week. For simplicity, we onlyconsider rush hour and regular hour for one day, i.e., two entries per day and 14 entriesin total per week for each segment. It is possible to further simplify and only differenti-ate between weekdays and weekends that lower the number of entities for a segment tofour. Every vehicle starts with an initial trust value of 0.5 for each neighbourhood. Then, itgradually updates different entries of the trust map for that segment/neighbourhood basedon its experience. For example, if this vehicle experiences a trustworthy communication inthat segment during rush hour in weekdays, then it increases the corresponding trust valuefor those times and days and makes it close to 1. Whenever a vehicle is calculating thetrust value of a road segment for the first time, it uses the neighbourhood’s trust instead.Note that each car needs to only store trust values of a handful of neighbourhoods and alimited number of road segments. Therefore, memory is not a constraint. The details ofthe trust model and the updates are discussed in Section 4.3.1.Note that the key component of our trust framework is that instead of assigning atrust value to each node, which is not scalable and hard to maintain and even inefficient,we assign a trust value to a neighbourhood and to each segment of that neighbourhood.In other words, our main contribution is that FACT is space-centric, i.e., it uses locationinformation to evaluate the trustworthiness of messages. There is a similar scenario in areal city where some neighbourhoods are safer than the others. This is the intuition behindFACT. Note that there is no predefined trust values for different neighbourhoods becauseall cars start the FACT by assigning the same value of 0.5 to all neighbourhoods and then70Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksthey gradually update their database as they learn more about different areas. However,in different times of the day, cars from other parts of the city may travel to these areasand lower the actual trustworthiness of these areas. That is why FACT assigns differenttrust values to different times of the day and constantly modifies these values. The biggestadvantage of FACT is its scalability and low complexity even for a metropolitan area. Theother advantage is its efficiency. In approaches like [45, 64] where there is a trust valueper node, resources are often wasted because we never come across that car again, but itis much more likely that we travel to the same area more than once.4.3.1 Trust CalculationIn this work, trust is assumed to have multiple dimensions based on the service requirementsof the corresponding application. For instance, delay, reliability, security/confidentiality,privacy/anonymity to name a few. FACT guarantees security and offers Quality of Service(QoS) based on the application requirements. Different applications on a vehicular networkcan be divided to three general categories based on their specific set of requirements: (a)Cata: safety-related services such as accident, high traffic, and emergency brake notifica-tions, and critical services when there is a disastrous situation like earthquake in place. Inthis category, delay, end-to-end reliability and data integrity are important. Some safety-related applications may be more tolerant to delay than others like when a road conditionneeds to be reported to incoming cars. As for data integrity, receivers must be assured thatthe information based on which they are making decision, is genuine. (b) Catb: infotain-ment such as parking availability and gas price notifications. Reliability, access control,source anonymity, and integrity are the main parameters to be considered in this category.Access control assures that only appropriate pairs can communicate to each other sinceeach piece of information is destined for a specific vehicle or a set of vehicles. Source au-71Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksthentication along with access control helps vehicles trust their communication by makingsure information is coming from a reliable source. (c) Catc: third-party services such aswhen taxis working for the same company want to share passenger availability information.Applications in this category need source authentication to guarantee that their informa-tion is from the right person, and reliability to maximize number of cars receiving theinformation.The overall trust value for a given path, m, is defined astTRm = FTR((α1, TR1), (α2, TR2), ...(αk, TRk)) (4.1)where, FTR is a function that combines the trust dimensions TRi to obtain the total trustvalue of tTR. Note that the value of αi represents the weight of the TRi, e.g. delay, in thecalculation of the total trust driven by the application. Given the category of the trafficas mentioned above, FACT assigns appropriate αi’s and calculates the overall trust for apath. One simple example of the function is a linear combination by having αi = 1/k for∀i. One other example is having 0 for the non-important αi’s.The model in [65] is used for calculating trust between agents in a multi-agent environ-ment. TRi is defined as a function of its current and historical values as follows:(TRτv)i = η × (TRcur)i + (1− η)× (TRτv−1)i (4.2)where, τ is the period of time (e.g. an hour, one day or one week) and v is the numberof the experiments that are considered so far. The value of η (0 ≤ η ≤ 1) is used togive weight to the trust value of current period, (TRcur)i, comparing to last v − 1 periods((TRτv−1)i) of the system in final trust calculation ((TRτv)i). Since we only rely on the72Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksdirect trust calculation in this model, the current trust value (TRcur)i is equal to the finalsatisfaction level of current period as per (4.3).(TRcur)i = STτn (4.3)where, ST τn is the satisfaction value of the trustee calculated by a trustor and is defined asST τn = γ × STcur + (1− γ)× STτn−1, STτ0 = 0.5 (4.4)where, γ (0 ≤ γ ≤ 1) represents the weight that is given to the current experiment (STcur)comparing to the last experiments in this period (ST τn−1) to calculate the final satisfactionvalue (ST τn ).Satisfaction (ST τn or STcur) is a value between zero and one, where one means fullysatisfied and zero means completely unsatisfied. We use the beta function to calculate thesatisfaction value via (4.5), as it is the most referred function in the literature.STcur =Nsuc + 1Nfail +Nsuc + 2(4.5)where, STcur is the satisfaction level based on the number of successful (Nsuc) and failed(Nfail) operations/services in an experiment which consists of one or multiple packet(s)delivery. For instance, in a safety application, there may be only one packet while in theon-line social networking the experiment consists of multiple packets.Finally, every vehicle uses the total trust on each path as the reward of the path (1/cost)to choose the best path. In other words, FACT maximizes the trust value and selects thepath that delivers the maximum trust. Let SetP denote the set of l paths where each onehas a total trust value of tTRm (1 ≤ m ≤ l). The path with the maximum total trustvalue of tTRm is the selected path as per (4.6).73Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksmax tTRmsubject to m ∈ SetP(4.6)It is easy to be shown that (4.6) is a concave function with a global maximum.4.4 FACT FrameworkWe make the following assumptions for the vehicular network in which FACT is imple-mented:• Vehicles know their location using GPS or other localization methods.• There are very few (3, for example) access points deployed in different parts of thecity. They are used to propagate system updates and urgent notifications. Trafficinformation is uploaded into all vehicles once they join the vehicular network. Afterthat and every time they meet an access point, this information is updated.• Similar to approaches like [20, 21, 55, 58], vehicles transmit beacon periodically to lettheir neighbours know about their existence. Each beacon has information about thelocation of the car, its velocity, and the direction it is heading. Using these beacons,each vehicle can determine the neighbourhood in which its neighbour is located inorder to calculate its trust value.• Vehicles are equipped with a tamper proof device. Moreover, they can connect toa certificate authority using an access point to receive their certificates. Therefore,they can sign their packets, e.g., source authentication.74Chapter 4. A Trust-based Information Dissemination Framework for Vehicular NetworksFACT Framework Message Discard Database Update Admission Module Trust Check Manipulation Check History Check 𝑇𝑇𝑖𝑗 Calculation 𝑡𝑇𝑇 𝑚 Calculation 𝑡𝑇𝑇 𝑚𝑚𝑚 Identification Message Forward Through 𝑚∗ Dissemination Module / Figure 4.2: FACT’s framework and how modules function and communicate to each other.• Whenever there is an incident in the network, such as accident or road problems,two notifications are sent: one at the beginning of that incident and another whenthe incident is finished. These notifications are called the incident and clearancenotifications, respectively.Note that the first four assumptions are typical in any vehicular network. The last assump-tion increases the overhead, however, this increase is far less than alternative approachessuch as sending an acknowledgment for each message. This small increase in overhead istraded to achieve a much better security level.When a vehicle receives a message, it has to make sure the message is authentic. FACTis a two-layer framework that consists of Admission and Dissemination modules. We dividethe vehicle to three types: (i) source, which originates the message, (ii) relay, which is inthe middle of the path and helps pass the message to its destination(s), (iii) destination,that is the last node on the path for which the message is intended. All these types havethe FACT framework presented in Fig. 4.2.75Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networks4.4.1 Admission ModuleWhen the receiving vehicle is a relay or destination node, the process of authenticatingthe message happens in the Admission module. FACT applies three checks to the messageto make sure it is authentic. First of all, the message’s origin should be determined. Todo that, each node i on the path (including the source) is required to add its location,i.e., its latitude and longitude, (xi, yi), which can be translated to its road segment and itsneighbourhood or (ri, ni), to the message header. In addition, each node has to also add atime-stamp ti to the message header showing the current time. Time-stamp and locationfields are both assumed to be 4B. xi and yi each has 2B allocated in the location field.Since the message size is assumed to be 512B, 8B overhead has a negligible impact on theoverall performance of FACT. Using the mentioned fields, when a message is received, thereceiver can easily identify the location of the source, e.g., locs = (rs, ns). Then, it can useits trust database and based on TRrs and TRns , decide whether it can trust the message’ssource. FACT uses a simple rule in which a location loci = (ri, ni) is considered trusted ifthe following inequalities holdTRri > ΦrTRni > Φn(4.7)where Φr and Φn are acceptable threshold for having a trusted road segment and neigh-bourhood, respectively. The values of Φr and Φn are tuned by the network administratorbased on the application and the characteristics of the environment. The same check isapplied to all nodes on the path in addition to the source in which case the message passesthe first check only if (4.7) holds for all previous nodes. Even the current location of themessage, i.e., (rx, nx) for node x, is evaluated using (4.7). If both inequalities in (4.7) hold76Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networkstc(d) =d(i,i)v¯iif i & i+ 1 are on the same road segmentd(i,int1)+d(int1,int2)+...+d(intj ,i)v¯iif otherwise(4.8)𝒅𝒊−𝒊𝒏𝒕𝟏 ii-1ii+1𝒅𝒊𝒏𝒕𝟏−𝒊𝒏𝒕𝟐 𝒅𝒊𝒏𝒕𝟐−𝒊 Intersection 1Intersection 2(i-1)'s Transmission RangeFigure 4.3: An example for distance calculation in the carry phase to find tc(d).for (rx, nx), then it means that x can trust its current neighbourhood. When the messagepasses the first check, FACT applies the second check.In the second check, there is a metric that enables FACT to detect any maliciousbehaviour along the path: the time-location pairs, (ti, loci), attached to the message whereeach pair corresponds to one vehicle on the path. If any of the nodes manipulates itslocation or/and time-stamp in the message to deceive other nodes about the trustworthinessof its (ri, ni) pair (and consequently, the values of TRri and TRni), the next node on thepath, x, can use (ti, loci) for {∀i, i = s, 1, 2, .., x} and easily spot any suspicious informationin the (ti, loci) pairs. In fact, x takes advantage of traffic information it has about (ri, ni)pairs to come up with an estimate of the time it takes to reach from (rs, ns) to (rx, nx)through the path traveled by the message, denoted by tes.77Chapter 4. A Trust-based Information Dissemination Framework for Vehicular NetworksTo calculate tes, let v¯i denote the average vehicle speed of the road segment ri usingthe historical traffic information. When a message is received by a car x and dependingon the implemented forwarding policy and the current vehicle density, it either forwardsthe message instantaneously (or with a very short processing delay) or it decides to keepand carry the message for a while, e.g., until it reaches another vehicle. These two casesare called forward and carry phases, respectively. Let tf denote the transmission timeplus the processing delay and tc(d) denote the time it takes x to travel d meters. Wealways have tc(d) tf . Assume each message goes through k1 forward and k2 carryphases until it reaches node x. Vehicle x calculates k1 and k2 by looking at ti − ti−1 for{∀i, i = s, 1, 2, .., x} and incrementing k1 when ti− ti−1 ≤ tf±δ1 and incrementing k2 whenti− ti−1 ≤ tc(d)± δ2. Parameters δ1 and δ2 are tuned based on the channel conditions andthe vehicle speed variance, respectively.For two successive nodes i and i+ 1, tc(d) is calculated as given in (4.8), where d(i,i) isthe distance that vehicle i traverses until it decides to forward the message to vehicle i+ 1.When i and i + 1 are on different road segments, vehicle i has to travel until it reachesi + 1 and on its way, it may cross j intersections. The nominator in the second term in(4.8) shows the total distance traveled by i before the next transmission. An example ofthis scenario for j = 2 is given in Fig. 4.3. d(i,int1) for example, is the distance betweenvehicle i and the intersection int1. Using (4.8), x calculates tes as followstes = k1tf +k2∑k=1tc(d(k,k+1)) (4.9)Then, x compares the calculate estimate with the actual time tac = tx − ts and iftac − tes > ∆, x concludes that the message is altered on its way. The value of ∆ dependson the size of a neighbourhood and time it takes to traverse it because if one vehicle decides78Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksto manipulate the message, it has to change its location to a more trusted neighbourhooddifferent from its current one.If the message passes the second check as well, x applies the third and final check. In thethird check, x takes advantage of the historic knowledge about the location of the source.In fact, this check is a content-based check in which case x validates the event/incidentreported in the message. As an example, suppose the message is about an accident at(rs, ns). x looks at its knowledge about that location and if rs is a high traffic road withprior accidents, it concludes the content can be valid. However, if rs is a road with verylight daily traffic and no history of accidents, it sees an anomaly which may or may not betrue. For this purpose, we define an accident threshold ζ to differentiate between a highaccident area and a low one. Note that the system administrator can tune this thresholdin addition to other system parameters. If x is a relay node, it sets a flag in the messagesuggesting that the received message is bogus and it cannot be trusted. It then pushes themessage down to the FACT’s Dissemination module to be forwarded to the next node. Onthe other hand, if x is the destination node, it waits until it receives the same informationfrom multiple sources (three sources for example) then takes an appropriate action, e.g.,it uses an alternative route. If another source confirms that incident without the flagbeing set, because of the contradiction between different sources, x cannot decide whetherthe message is genuine or not. Therefore, it does not take any action except saving acopy of the message for some time, Tinc, which represents the average delay between theincident and clearance messages and is set by the network administrator. If during Tinc,x receives the clearance notification, meaning that the report was correct, it recalculatesthe corresponding trust values in its database. Otherwise and when Tinc expires, meaningthat the report was bogus, x just discards the message. Similarly, when x is a relaynode and it realizes that the message was actually correct (using Tinc), it updates its79Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksknowledge by adding that incident to its database. This means that bogus messages andthe corresponding attacks do not hurt the trustworthiness of an area.4.4.2 Dissemination ModuleWhen the receiving vehicle x is a relay node and if the message passes all three checksexplained in Section 4.4.1, x pushes the message down to the Dissemination module in orderto be forwarded to the next vehicle. Four cases can be imagined for FACT’s Disseminationmodule based on the type of the node and its location: Case I when it is a source nodeat intersection, it follows the pseudo code given in Algorithm 4.1. Note that each vehicleknows the location of its neighbours and the corresponding trust values using the periodicbeacons. Case II when it is a relay node at an intersection that wants to decide on the nexthop, because the traffic category, Cat, is already in the message, the relay node followsAlgorithm 4.1 from step 3 to the end. Case III when the vehicle is a source and in themiddle of a street, it takes the first two steps of Algorithm 4.1 and then forwards the packetto the closest neighbour to the destination. In fact, all vehicles on that segment have thesame segment trust value and it does not matter which vehicle is selected as the next hop.Hence, it is best to send the message to the closest node to the destination. At the end,the sender updates its trust value for that segment. Case V, when the vehicle is a relaynode and in the middle of the road segment, it just forwards the message to the closestneighbour to the destination and updates its trust value for that segment.Note that in situations where there is an adversary node in a trusted area, STcur willbe dropped temporarily and so is tTR for that neighbourhood. But, when this node movesout of the trusted area, the total trust will go back to normal. There are cases where allpossible paths have very weak total trust values. In those cases, the vehicle carrying themessage, regardless of being the source or a relay node, uses a threshold TRmin. If ∃i where80Chapter 4. A Trust-based Information Dissemination Framework for Vehicular NetworksProcedure 4.1 FACT at Intersection1: Based on the content of the message or the nature of the event, the appropriate trafficcategory, Cat, is determined.2: Based on the selected category, the corresponding αi’s are specified.3: For set of neighbours, j = 1 : w:4: For set of parameters, i = 1 : k:5: TRji is calculated.6: For set of paths, m = 1 : l:7: tTRm is calculated using the αi’s calculated in step 2.8: tTRmax is identified.9: The winning path, m∗, is selected and the message including the traffic category, Cat, isforwarded to the neighbour on m∗, i.e., j∗.10: FOR i = 1 : k:11: Based on the forwarding experience, STm∗i and TRm∗i are updated.αi 6= 0 and TRim ≤ TRmin for ∀m ∈ SetP , then the vehicle continues carrying the messageuntil the next intersection to see whether the trust condition changes on that intersection.There are situations when due to a temporary reason, for instance a construction projector a festival, the trust condition of a road segment or a neighbourhood is changed and sois the corresponding trust value in the trust map of vehicles traveling to that area. Butwhen that reason does not exist anymore, if cars use (4.2), it will take a while for the trustvalue to converge to the actual value and we say the trust value has a bias. To addressthis, we consider a parameter, NUMbias as the number of times FACT allows the currenttrust, TRcur , to be hugely different from the historical trust. For example, if NUMbias = 3and this is the fourth time that the current trust is much bigger than the historical one,then FACT uses the average of the last three values of TRcur as the trust value for thatsegment. The size of the gap between the current and the historical trust, i.e., the size ofthe bias, should be carefully selected to avoid erroneous decisions. One example could be50% of the historical trust.One limitation of FACT is when a malicious vehicle travels in a known-to-be-trustedsegment. Therefore, all messages that are relayed to this vehicle will be either manipulatedor destroyed. The other vehicles receive a very bad feedback and they try to update their81Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networkstrust estimate for this segment. Using the above mentioned mechanism and assuming themalicious vehicle corrupts the packets more than NUMbias times, the trust value will bedeclined dramatically. But, as the malicious node exits this segment, the trust value forthat segment goes back to normal after at most NUMbias times of genuine transmissions.Based on this discussion, the impact of infiltrating a malicious node in a trusted segmentcan be minimized by choosing a small value for NUMbias, so that both discovery andrecovery periods are small.Note that FACT is based on only the direct trust assessment. It is also possible, andlikely beneficial, for cars to share their trust values to be used in the trust evaluation inSection 4.3.1. That is called indirect trust assessment and it is a topic for our future work.Finally, it is obvious that the same satisfaction value caused by a car experiment cal-culated via (4.5) will affect the trust value of the segment as well as the neighbourhood,as per (4.2) and (4.4). However, the effect of the current value should have less influenceon the neighbourhood compare to the segment. Therefore, the system administrator, thatsets the parameters of the vehicle, may set the values of γ and η of the neighbourhoodless than the parameters γ and η of a segment in that neighbourhood. There is a similarsituation when setting the values of τ and n in (4.4) and τ and v in (4.2), where theadministrator needs to be careful in choosing the appropriate values for the segment andfor the neighbourhood.4.5 AnalysisIn this section, we analyze our proposed framework from the security point of view andthen present a qualitative comparison between FACT and other trust-based approaches.82Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networks4.5.1 Security AnalysisWe follow the well-known Dolev-Yao approach [66] and provide an adversary analysis.Dolev-Yao assumes that all packets are delivered to and received from an adversary, whichis capable of recording, deleting, re-playing, re-routing, re-ordering and re-scheduling thepackets. To attack this system, an adversary can be a sender or a relay node. Therefore,we provide three adversary models representing three positions of the adversary. In ourfirst model, our adversary is a sender, and in second and third models, our adversary is arelay node.First adversary modelIn this model, we assume our adversary is a sender. To be more precise, he sends the bogusmessages about events such as traffic.Objective The objective of the adversary can be misleading the receivers about thetraffic in an area (e.g. street), and/or defecting a neighbourhood/segment.Initial capability Initially, he knows the detailed information about our proposed frame-work as well as the overall topology and map of the area.Capability during the attack He is capable of sending many bogus messages aboutan event that has never happened. Moreover, he is capable of modifying the source of themessages to be other nodes, a benign/valid car, or a dummy car. Also, he can keep drivingand move from one area (neighbourhood/segment) to another to reduce the trust valuesof multiple areas.Discussion As per our design, explained in Section 4.4.2, by having NUMbias, a receiverwaits for NUMbias reports about the same event before it relies on the report. This83Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networksvalue can be tuned up if necessary, if the system is attacked especially distributed attack.Note that distributed attack in this case means our adversary should have multiple carsin different streets and areas to be able to completely destroy the trust evaluation andmislead the receivers, which is a very expensive attack and may not be feasible.Finally, since the adversary is the packet generator, it might be misleading for thereceiver at first, however, after a few times catching the errors and finding out aboutthe bogusness of the packets, the receiver can identify that particular sender as a mali-cious/attacker in which case it denies the entire information generated by the sender fromthat point.Note that if our adversary generates the bogus messages and modifies the sender ofeach one to be a benign/valid car or a dummy car to perform the attack, it may still affectthe trust value of an area. It is obvious that if he tries to impersonate a benign car, thebenign car will receive the message as well, as a receiver per our design, and will distributea correction message to disregard the bogus one. In case of impersonating a dummy car,as per our discussion in Section 4.4.1, our proposed solution catches and ignores thoseattacks.Second adversary modelIn this model, we assume our adversary is a relay node. To be more precise, he does notgenerate any packet, and instead, he only relays the packets sent by others while modifyingthem.Objective The objective of the adversary can be destroying/modifying the senders’ mes-sages about an event or an area.84Chapter 4. A Trust-based Information Dissemination Framework for Vehicular NetworksInitial capability Initially, he knows the detailed information about our proposed frame-work and also he is well equipped to receive and then send the packets as well as showinghimself as a ready node to relay.Capability during the attack He is capable of receiving and sending the messages. Hecan read inside the packet and can modify any part of the message, like the time stamp,street name, and overall the event. For instance, he can change a message such thatinstead of saying “there is an accident”, it says “the accident is cleared/traffic is smooth”.He can also receive the message and drop it, or deliver it to a wrong direction, in case ofunicast/multicast communication. In this case, he may modify the destination as well tomislead other relay nodes that will receive this message, which has passed the adversarynode.Discussion First of all, in our design, we assume there is an under-layer security mech-anism such that the integrity of the messages and packets are preserved. In this case,when the affected/modified packet is received by the next relay node/ or a receiver (ifthe adversary is the last node before the receiver), the receiver and next relay nodes arecapable of catching the attack as part of their Admission module of the FACT framework(Section 4.4.1).In case of the next node being a receiver, the receiver does not rely on packets receivedfrom the adversary anymore and expects the message from others.When the next node is a relay node, it is again capable of finding the attack andtherefore it can easily stop cooperating with the adversary for the following communication.Note that, since each relay node should add a time stamp to the packets, if the adversaryattacks the system by more than one car, meaning damaging the packet by first car andpassing it to the next attacker car to relay, the attack can still be discovered along the85Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networkspath or in worst case scenario, by a receiver. In either case, the benign node(s) ignorespackets passing the attackers.Similar to the first model and as per Section 4.4.2, by having NUMbias, a receiver waitsfor NUMbias reports about the same event before it relies on the report. This value canbe tuned up if necessary, if the system is attacked especially distributed attack. Note thatdistributed attack in this case means our adversary should have multiple cars in differentstreets and areas to be able to completely destroy the trust evaluation and mislead thereceivers, which is a very expensive attack and may not be feasible.Finally and similar to the first model, since the adversary is the packet generator, itmight be misleading for the at first, however, after a few times catching the errors andfinding out about the bogusness of the packets, the receiver can identify that particularsender as a malicious/attacker in which case it denies the entire information generated bythe sender from that point.Third adversary modelIn this model, we assume our adversary is again a relay node. However and unlike thesecond model, he does not change the messages; instead, he forwards the messages alonga wrong path (with low trust value).Objective The objective of the adversary can be nullifying the messages that reportan event. The message can be about an accident happening now or about clearing thetraffic caused by an accident. With a good approximation, the former one is similar to agood-mouthing attack, and the later one is similar to a bad-mouthing attacks.Initial capability Initially, he knows the detailed information about our proposed frame-work as well as the overall topology and map of the area.86Chapter 4. A Trust-based Information Dissemination Framework for Vehicular NetworksCapability during the attack He is capable of playing the role of a relay node. Heforwards the messages, but not to the proper direction. Therefore, he keeps his reputationto others as a benign node although he is performing the attack. Note that, this attack canbe similar to the black-hole attack in a unicast communication scenario where the relaynode sends the packets to a malicious node to be dropped at that node.Discussion As per our previous discussion, our application is data dissemination. There-fore, we do not have a single receiver (like in the unicast communication scenario). In fact,the messages are being forwarded and disseminated by other cars, as well. So, if an at-tacker tries to send the messages to a path with low trust value, to perform the attack,other benign cars will redirect the messages back to the proper path with a high trustvalue.4.5.2 Comparison AnalysisTable 4.1: Comparing the features of the surveyed proposals in Section 4.2 and our proposalItem/ Data- Entity- Source- Receiver- Path- Infrastructure- Application- Broadcast/Paper centric centric centric centric centric based oriented Unicast[45] 6 4 4 6 6 4 6 B[46] 4 6 6 4 6 4 6 B[48] 6 6 6 6 4 4 6 U[49] 6 4 4 6 4 4 6 U[50] 6 4 4 6 6 6 6 B[51] 6 4 4 6 6 6 6 B[52] 4 4 4 6 4 6 6 B[53] 4 6 6 4 6 6 6 B[54] 4 4 6 4 6 6 6 B[55] 4 6 6 4 6 4 6 B[56] 6 4 4 6 6 6 6 B[57] 6 4 4 6 6 6 6 B[58] 4 4 4 6 6 4 6 U[59] 6 6 6 6 4 6 6 U[60] 4 4 4 6 6 6 6 U[61] 6 4 4 4 6 6 6 U[67] 6 4 4 6 4 6 6 U[62] 4 6 4 6 4 6 6 U[63] 4 4 4 6 4 6 6 UFACT 4 4 4 4 4 6 4 B&U87Chapter 4. A Trust-based Information Dissemination Framework for Vehicular NetworksTABLE 4.1 presents a brief summary of the comparison between the studied mod-els in Section 4.2 and our proposal. Rows of the table show the characteristics of themechanism/systems, as follows:• Data-centric: If the mechanism/system concentrates on the content of the packet.• Entity-centric: If the mechanism/system concentrates on the entity, e.g. sender,receiver and/or a relay node/vehicle.• Source-centric: If the mechanism/system is designed to be used by the senders, e.g.,for choosing the next hop or the best path.• Receiver-centric: If the mechanism/system is designed to be used by the receivers,e.g., for trusting the received message.• Path-centric: If the mechanism/system is designed to be used for choosing a path orevaluating the trustworthiness of the path.• Infrastructure-based: If the mechanism/system requires having an infrastructure, in-cluding road side unit or even certificate authority.• Application-oriented: If the mechanism/system considers requirements of the appli-cation that is running.• Broadcast/Unicast: If the mechanism/system uses broadcasting or unicasting forcommunicating between vehicles.FACT is data-centric because it checks the content of the message once for determiningtraffic category and again in the third check of the Admission module. It is entity-centricsimply because FACT assures that the message can be trusted only when all the nodes88Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networks(entities) on the path are trustworthy (at least to some extent). FACT is both source-centric and receiver-centric because each receiving car first makes sure the received messagecan be trusted (in Admission module), and then it chooses a trusted path for forwardingthe message (in Dissemination module). Using the same reasoning, it is easy to see thatFACT is path-centric, as well. Since having roadside units are not necessary for FACTto work, it is not infrastructure-based. It is application-oriented because it specifies αi’sbased on the application. Finally, both broadcast and unicast are supported by FACT.4.6 Performance EvaluationTo evaluate the performance of the FACT, we ran an extensive set of simulations usingMATLAB. We divided the whole city into three regions: 1) Very trusted neighbourhood,Nt, where 90% of transmissions are genuine while 10% of times packets are destroyed. Thesize of Nt on the other hand is bigger than the other two regions and it has a lower vehicledensity resulting in a bigger delay. 2) Untrusted neighbourhood, Nu, where only 10%of transmissions are genuine. However, Nu has a smaller size and higher vehicle densitycompared to other two regions which means a smaller delivery delay. 3) Semi-trustedneighbourhood, Ns, where 50% of transmissions are genuine. The size and the vehicledensity in Ns are between the respective values in Nt and Nu, which results in a delayvalue between other two regions’ delays. The application is assumed to be a safety-relatedservice with αi = 1/3 for delay, reliability, and data integrity. We assumed a transmissionrange of 250m and Rician fading with shadowing as the propagation model. The velocityof cars is assumed to follow a normal distribution according to work by Wisitpongphan etal. [13] using real traffic traces. Simulation parameters are summarized in Table 4.2.The results of the simulations for delay are reported in Fig. 4.4 for FACT vs. Epidemicrouting and VADD. As it is shown in this figure, FACT outperforms other two algorithms89Chapter 4. A Trust-based Information Dissemination Framework for Vehicular NetworksTable 4.2: Configuration ParametersParameter ValueChannel modelling Rician with K = 10Packet length (B) 200MAC standard IEEE 802.11pCommunication frequency 5.9 GHzData rate (Mbit/s) 6Data Traffic Periodic with T = 50 msecSlot duration 13 µsSIFS 32 µsDIFS 58 µsMinimum vehicle speed (km/h) 80Maximum vehicle speed (km/h) 130Average vehicle speed (km/h) 100in terms of delay while achieving the same level of reliability although they use fasterpaths. FACT performance vs. VADD is particularly interesting because even thoughVADD chooses the fastest path and benefits half of FACT’s communication delay pertransmission, delivery delay in FACT is significantly improved (between 400% − 600%).The reason is the excessive number of retransmissions in VADD as a result of packetdrops in the untrusted neighbourhood (see Fig. 4.5). Each time a packet is dropped by amalicious vehicle, the source vehicle has to resend the original message that leads to higherdelivery delay.On the other hand, packet delivery ratio (or the end-to-end reliability) is the other vic-tim of untrusted vehicles. As shown in Fig. 4.6, FACT jumps to maximum packet deliveryratio in a much shorter time compared to Epidemic routing and particularly comparedto VADD. It means that FACT achieves higher reliability in a shorter time. Note thatalthough Epidemic routing is a close competitor to FACT in these figures, but because ofthe flooding nature of it, Epidemic routing imposes a huge communication cost in termsof the interference and congestion to the network. However, FACT has a communication90Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networks10 15 20 2501000200030004000500060007000Vehicle density (car/km)Delay (msec) FACTEpidemicVADDFigure 4.4: Delivery delay vs. different vehicle densities for 90% reliability.10 15 20 2505001000150020002500Vehicle density (veh/km)Number of re−initializations FACTEpidemicVADDFigure 4.5: Number of times the source retransmits its message because of the packet dropsby malicious nodes.cost comparable to VADD, which is much less than Epidemic.Next, we study the effect of vehicle speed on delivery delay. A comparison betweenFACT and VADD and Epidemic routing in terms of delivery delay against different speedsis presented in Fig. 4.7. The average vehicle speed ranges from 50km/h which is typicalfor an urban scenario to 110km/h which is more suited for a highway environment. Asit is shown in this figure, vehicle speed’s impact on delivery delay is very high for VADDand very low for FACT. As expected, increasing the speed reduces the delivery delay forall three algorithms.Finally, the impact of vehicle speed on the FACT packet delivery ratio is studied. As91Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networks0 1000 2000 3000 4000 5000 6000 70002030405060708090Delay (msec)Packet delivery ratio (%) FACTEpidemicVADDFigure 4.6: Packet delivery ratio vs. delivery delay.shown in Fig. 4.8, there is a fairly big gap between when the speed is 50km/h and the restof speeds. It seems 50km/h is a transitional speed in this regard. The results for speed of70km/h and 90km/h are very close to each other. The next transitional speed seems to be110km/h.50 60 70 80 90 100 1100100020003000400050006000700080009000Average vehicle speed (km/h)Delay (msec) FACTEpidemicVADDFigure 4.7: Delivery delay vs. different average vehicle speeds for 90% reliability.92Chapter 4. A Trust-based Information Dissemination Framework for Vehicular Networks0 200 400 600 800 10002030405060708090Delay (msec)Packet delivery ratio (%) Speed = 50 km/hSpeed = 70 km/hSpeed = 90 km/hSpeed = 110 km/hFigure 4.8: FACT packet delivery ratio vs. delivery delay for different average speeds.4.7 SummaryIn this chapter, after a survey of security and trust mechanisms, we present a secure anddistributed information dissemination framework for vehicular networks named FACT.FACT is a trust-based two-layer framework. In the first layer, Admission, FACT makessure the message is originated from a trusted source and has not been manipulated on itspath, so far. Then in the second layer, Dissemination, FACT finds a trusted path to thedestination and forwards the message on that path. Finally and by means of simulations,it is shown that FACT’s performance is much better than other well-known forwardingpolicies.93Chapter 5Conclusions and Future Work5.1 Research ContributionsIn this chapter, we summarize the results and highlight the contributions of this thesis.• In Chapter 2, we first presented a mathematical model to study the behaviour ofemergency message dissemination in vehicular networks in terms of delay and relia-bility. To do this, the minimum number of transmissions to guarantee a minimumend-to-end reliability is calculated. The end-to-end reliability exponentially falls offover time as it is mathematically proved. Then, we enhanced our mathematical anal-ysis by using a realistic distribution for channel fading instead of a fixed value. It isalso observed from the analytical model that using the vehicle density on the road is agood metric for setting the right forwarding probability in vehicles. This formed thebasis of our proposed distributed forwarding strategy. Finally, the proposed modelis validated through extensive simulations. In addition, simulation results showedthe effectiveness of the proposed warning dissemination scheme in terms of delay andsingle-hop reliability against other well-known routing policies. Furthermore, theysuggest that by increasing the traffic on the road, analytical bounds converge to thesimulation values. As a future work, we are extending our model for other safetyapplications.• In Chapter 3, we proposed a mathematical model for delivery delay in vehicular net-94Chapter 5. Conclusions and Future Workworks. We started by modelling the MAC layer part of delay and then includingthis into a Markov chain. This Markov model tracks the information disseminationboth when the car is alone and should carry the message and when there are neigh-bours to which the message can be forwarded. To the best of our knowledge, thisis the first delay model that both captures physical and MAC layers’ characteristicsand addresses the partitioning problem. The proposed model can be used by net-work architects to tune the parameters such as the transmission power, slot time,and back-off duration accordingly to achieve the fastest yet most reliable forward-ing (scheduling/routing) policy. We have also discovered that the commonly usedassumption that inter-vehicle distances are exponentially distributed is flawed whenthe vehicular network is susceptible to partitioning. It was shown that the IVD’sdistribution when the cars are connected should be different from when they arealone. A new and more accurate model was subsequently presented. Finally, theproposed model is validated through several simulations for both highway and urbanscenarios. They also indicate how effective the proposed Middle Is Next (MIN) for-warding policy is compared to other well-known routing protocols. MIN can be usedas a sublayer for the MAC layer in order to have faster and more reliable messagedelivery in vehicular networks.• In Chapter 4, first we present a survey on routing, security and trust systems/mechanisms,mainly in vehicular networks and ad-hoc environment. Then, we propose a two-layertrust-based information dissemination framework called FACT and its application invehicular networks. FACT, is an application-oriented framework designed to sup-port broadcast, multicast and unicast communication in vehicular networks. FACTmaintains the trust values of the neighbourhoods and segments of the city. It firstmakes sure the message is originated from and traveled through trusted nodes and95Chapter 5. Conclusions and Future Workthe content is valid. It then uses stored trust values to choose the best path to routethe message, or if needed, to carry the messages. Simulation results show that FACToutperforms other well-known routing protocols like VADD. They also validate theeffectiveness (in terms of communication cost) and scalability of FACT. FACT givesnetwork designers a full package which delivers trustworthy messages through a safepath with high reliability and in a short amount of time. It is flexible enough meaningnetwork admins can tune the parameters based on the network condition. Design-ers can incorporate their desired scheduling and routing schemes into FACT andstill disseminate the messages safely. FACT is a framework that supports differentapplications with different requirements.5.2 Suggestions for Future WorkIn this section, we consider possible extensions to our current work.1. Vehicular Service Delivery Framework: By emerging new applicationsfor vehicular network and gaining more attention from the government and thesociety, a system is missing that can provide different services under the umbrellaof vehicular networks. It is worth emphasizing that in a vehicular network, weare mostly interested in area- and time-specific services. Thus, there should be asystematic way to map these services to the vehicular environment consideringhigh level of mobility. As mentioned in Chapter 1, there is a diverse rangeof safety and non-safety applications in vehicular networks. A system whichis constituted of a comprehensive set of protocols can offer services from trafficmonitoring to localized advertisement. We plan to extend our work by designingsuch system and we call it Vehicular Service Delivery (VSD).96Chapter 5. Conclusions and Future WorkVehicular Service Delivery framework divides the city to a number of zones. Theradius of the zone is of course something which needs to be carefully investigated.Choosing a big radius means sharing the local information among more cars,which on the other hand causes more interference and needs more bandwidth.Making the radius very short can make the information dissemination inefficient.Because in most cases we need to have the information of at least a minimumnumber of cars to offer meaningful services. VSD then offers its localized serviceswithin that zone. Services of each zone are specific to cars in that zone. Eachservice has its own set of requirements. The service’s requirements basicallydetermine what kind of local information is required and with what level ofreliability and delay. For example, one interesting service that Vehicular ServiceDelivery framework can offer is parking space finding: each car can use its GPSand a preloaded map of parking spaces of the zone to find detect the locationof a free space where it can be parked. Each car notifies other cars in the zonewhen it is parked. This information then is reflected on the map of cars andcars will know about the free spaces within a short amount of time. Whenthe requirements are determined, a proper forwarding policy will be selected.For the example of Parking Solution, one good dissemination option is MIN,presented in Chapter 2).One general goal of VSD is to balance the load of cars in term of information.By employing a suitable P2P communication approach, we can distribute therequests among the cars in the zone. The concept of having zones itself helpsus to balance the incoming traffic of each vehicle. This way, we involve morecars in the communication which potentially decreases the interference and thedelay by capturing the information from a closer car.97Chapter 5. Conclusions and Future Work2. Route Planning: The idea of using GPS brings up an interesting applicationnamed Route Planning.The idea is to use route information based on the destination that people enterinto their GPS devices when they start their trip. This information is highlybeneficial because someone can use them and predict the traffic on differentsections using some average trip time for each section. Consider a table, Ttraff ,which has N rows, where N is the number of sections on the map. We defineone iteration as the time it takes a car to traverse a section. It is not necessaryto have equal iterations as it is not equal in the real world and for a real map.Assume that we have access to all GPS information with minimum delay. Then,it is possible to fill Ttraff with this information and get a sense of the currentand the future traffic for each section of the map. This traffic forecasting tableis especially important because we can exploit it and find the best and fastestroute for an incoming car.As mentioned above, Ttraff can be used for a new car to choose the best pathbased on the current and future traffic of each section. However, this idea ismuch more rewarding when we use it for all cars including the ones that wehave used their GPS data. There are two approaches for this: 1) the centralizedmethod, and 2) the distributed method. The centralized method gathers all GPSinformation, forms the table for all cars on the map (for all zones), calculatesthe best path for each car and sends back the results to the cars, so they canact accordingly. The best path is defined as the shortest and fastest path,considering the distance and the quality of the section, i.e., whether it is anarrow road or a wide highway. We plan to solve this optimization problemusing a relevant objective function such as the total travel time of all cars on98Chapter 5. Conclusions and Future Workthe map. Although the centralized method gives the optimum for each car andfor the sum of travel time over all cars, but a) collecting all GPS data at almostno time, which is dynamic and new cars are always coming, b) calculatingshortest path for that number of nodes very fast, and then c) sending back theresults to the cars again with minimum delay, are strong assumptions which aremost of the times impossible to satisfy.The distributed method on the other hand is much more practical, even thoughit most probably gives a sub-optimal answer. In this method we restrict theroute planning problem to each zone and to cars of that zone. The intuitionbehind it is that each car is much more concerned about deciding which way togo for the next few sections and not for the whole path. Obviously, if each carchooses the best route in its zone, Zi, based on the local traffic forecasting tablefor that zone, T itraff , the total travel time of all cars converges to the optimalgiven by the centralized method when the radius of Zi converges the radius ofthe city map, R. Nevertheless, we believe that we can still get a very accuratesub-optimal while minimizing the decision delay by carefully selecting the radiusof the zone, Zi < R. We then use the result of the centralized approach as areference to see how much close our distributed approach is the optimal.99Bibliography[1] “Global status report on road safety 2013,” World Health Organization, April2015. [Online]. Available: http://www.who.int/violence injury prevention/road safety status/2013/en/[2] ITS Canada, April 2015. [Online]. Available: http://www.itscanada.ca/it/index.html[3] DSRC on ITS USA, April 2015. [Online]. Available: http://www.its.dot.gov/DSRC/dsrc faq.htm[4] IEEE 802.11p Task Group, April 2015. [Online]. Available: http://grouper.ieee.org/groups/802/11/Reports/tgp update.htm[5] Y.-C. Chen, D. Towsley, E. M. Nahum, R. J. Gibbens, and Y.-s. Lim, “Charac-terizing 4g and 3g networks: Supporting mobility with multipath tcp,” 2012.[6] Y. Yao, L. Rao, X. Liu, and X. Zhou, “Delay analysis and study of ieee 802.11pbased dsrc safety communication in a highway environment,” in INFOCOM,2013 Proceedings IEEE, April 2013, pp. 1591–1599.[7] ITS USA, April 2015. [Online]. Available: http://www.its.dot.gov/faqs.htm[8] H. Hartenstein and K. Laberteaux, Eds., VANET Vehicular Applications andInter-Networking Technologies. Chichester, UK: Wiley, 2010.[9] N. Lu, N. Zhang, N. Cheng, X. Shen, J. Mark, and F. Bai, “Vehicles meetinfrastructure: Toward capacity-cost tradeoffs for vehicular access networks,”Intelligent Transportation Systems, IEEE Transactions on, vol. 14, no. 3, pp.1266–1277, 2013.[10] H. Wu, R. Fujimoto, G. Riley, and M. Hunter, “Spatial propagation of infor-mation in vehicular networks,” Vehicular Technology, IEEE Transactions on,vol. 58, no. 1, pp. 420 –431, jan. 2009.[11] G. Resta, P. Santi, and J. Simon, “Analysis of multi-hop emergency messagepropagation in vehicular ad hoc networks,” in ACM International Symposiumon Mobile Ad Hoc Networking and Computing (MobiHoc), 2007, pp. 140–149.[12] X. Chen, L. Li, and Y. Zhang, “A markov model for headway/spacing distribu-tion of road traffic,” Intelligent Transportation Systems, IEEE Transactions on,vol. 11, no. 4, pp. 773–785, 2010.100Bibliography[13] N. Wisitpongphan, F. Bai, P. Mudalige, V. Sadekar, and O. Tonguz, “Routing insparse vehicular ad hoc wireless networks,” Selected Areas in Communications,IEEE Journal on, vol. 25, no. 8, pp. 1538–1556, 2007.[14] D. B. Johnson and D. A. Maltz, “Dynamic source routing in ad hoc wirelessnetworks,” in Mobile Computing. Kluwer Academic Publishers, 1996, pp. 153–181.[15] X. Hong, T. J. Kwon, M. Gerla, D. L. Gu, and G. Pei, “A mobility frameworkfor ad hoc wireless networks,” in Mobile Data Management, 2001, pp. 185–196.[16] J. Harri, F. Filali, and C. Bonnet, “Mobility models for vehicular ad hoc net-works: a survey and taxonomy,” Communications Surveys Tutorials, IEEE,vol. 11, no. 4, pp. 19 –41, 2009.[17] R. Fracchia and M. Meo, “Analysis and design of warning delivery service inintervehicular networks,” IEEE Transactions on Mobile Computing, vol. 7, no. 7,pp. 832–845, 2008.[18] K. Abboud and W. Zhuang, “Modeling and analysis for emergency messagingdelay in vehicular ad hoc networks,” in Global Telecommunications Conference,2009. GLOBECOM 2009. IEEE, Nov. 2009, pp. 1–6.[19] A. Vahdat and D. Becker, “Epidemic routing for partially connected ad hocnetworks,” Duke University, Tech. Rep.[20] J. Zhao and G. Cao, “Vadd: Vehicle-assisted data delivery in vehicular ad hocnetworks,” Vehicular Technology, IEEE Transactions on, vol. 57, no. 3, pp. 1910–1922, 2008.[21] A. Skordylis and N. Trigoni, “Efficient data propagation in traffic-monitoringvehicular networks,” Intelligent Transportation Systems, IEEE Transactions on,vol. 12, no. 3, pp. 680–694, 2011.[22] R. M. Fujimoto, H. Wu, R. Guensler, and M. Hunter, Modeling and Simula-tion Tools for Emerging Telecommunication Networks. US: Springer, 2006, ch.Evaluating Vehicular Networks: Analysis, Simulation, and Field Experiments.[23] F. Bai and B. Krishnamachari, “Spatio-temporal variations of vehicle traffic invanets: facts and implications,” in VANET ’09: Proceedings of the sixth ACMinternational workshop on VehiculAr InterNETworking, 2009, pp. 43–52.[24] N. Wisitpongphan, F. Bai, P. Mudalige, and O. K. Tonguz, “On the routingproblem in disconnected vehicular ad-hoc networks,” in INFOCOM, 2007, pp.2291–2295.[25] T. T. Soong, Fundamentals of Probability and Stochastics for Engineers. Chich-ester, UK: Wiley, 2004.[26] H. Reijmers and R. Prasad, “Packet success probabilities for intelligent vehiclehighway systems using measured headway distributions,” in Vehicle Navigationand Information Systems Conference, 1994, pp. 127–132.101Bibliography[27] I. Davis, J.S. and J. Linnartz, “Vehicle to vehicle rf propagation measurements,”in Conference Record of the Twenty-Eighth Asilomar Conference on Signals,Systems and Computers, vol. 1, 1994, pp. 470 –474.[28] J. Yin, G. Holland, T. ElBatt, F. Bai, and H. Krishnan, “Dsrc channel fadinganalysis from empirical measurement,” in Communications and Networking inChina, 2006. ChinaCom ’06. First International Conference on, oct. 2006, pp.1 –5.[29] J.-P. M. Linnartz, Ed., Multipath Fading in Wireless Channels, April 2015.[Online]. Available: http://www.wirelesscommunication.nl/reference/chaptr03/ricepdf/rice.htm[30] S. M. Ross, Introduction to Probability Models, Ninth Edition. Orlando, FL,USA: Academic Press, Inc., 2006.[31] M. Artimy, “Local density estimation and dynamic transmission-range assign-ment in vehicular ad hoc networks,” Intelligent Transportation Systems, IEEETransactions on, vol. 8, no. 3, pp. 400–412, 2007.[32] R. Chen, W.-L. Jin, and A. Regan, “Broadcasting safety information in vehicularnetworks: issues and approaches,” Network, IEEE, vol. 24, no. 1, pp. 20–25,2010.[33] C. Suthaputchakun, M. Dianati, and Z. Sun, “Trinary partitioned black-burstbased broadcast protocol for time-critical emergency message dissemination invanets,” Vehicular Technology, IEEE Transactions on, vol. 63, no. 6, pp. 2926–2940, 2014.[34] A. Abdrabou, B. Liang, and W. Zhuang, “Delay analysis for sparse vehicu-lar sensor networks with reliability considerations,” Wireless Communications,IEEE Transactions on, vol. 12, no. 9, pp. 4402–4413, 2013.[35] Y. Liu, J. Niu, J. Ma, L. Shu, T. Hara, and W. Wang, “The insights of mes-sage delivery delay in vanets with a bidirectional traffic model,” Network andComputer Applications, Journal of, vol. 36, no. 5, pp. 1287–1294, 2013.[36] Y. Li and W. Wang, “Horizon on the move: Geocast in intermittently connectedvehicular ad hoc networks,” in IEEE International Conference on ComputerCommunications (INFOCOM), 2013, pp. 2553–2561.[37] M. Khabazian, S. Aissa, and M. Mehmet-Ali, “Performance modeling of messagedissemination in vehicular ad hoc networks with priority,” Selected Areas inCommunications, IEEE Journal on, vol. 29, no. 1, pp. 61–71, 2011.[38] X. Huang and Y. Fang, “Performance study of node-disjoint multipath routingin vehicular ad hoc networks,” Vehicular Technology, IEEE Transactions on,vol. 58, no. 4, pp. 1942–1950, 2009.102Bibliography[39] A. Abdrabou and W. Zhuang, “Probabilistic delay control and road side unitplacement for vehicular ad hoc networks with disrupted connectivity,” SelectedAreas in Communications, IEEE Journal on, vol. 29, no. 1, pp. 129–139, 2011.[40] F. Xu, S. Guo, J. Jeong, Y. Gu, Q. Cao, M. Liu, and T. He, “Utilizing sharedvehicle trajectories for data forwarding in vehicular networks,” in IEEE In-ternational Conference on Computer Communications (INFOCOM), 2011, pp.441–445.[41] Y. Ding and L. Xiao, “Sadv: Static-node-assisted adaptive data disseminationin vehicular networks,” Vehicular Technology, IEEE Transactions on, vol. 59,no. 5, pp. 2445–2455, 2010.[42] “Mathwave easyfit,” http://www.mathwave.com/easyfit-distribution-fitting.html, April 2015, [Online].[43] A. Agarwal, D. Starobinski, and T. D. C. Little, “Exploiting downstream mobil-ity to achieve fast upstream message propagation in vehicular ad hoc networks,”in Mobile Networking for Vehicular Environments, 2007, pp. 13–18.[44] J.-H. Cho, A. Swami, and R. Chen, “A survey on trust management for mobilead hoc networks,” IEEE Communications Surveys & Tutorials, vol. 13, no. 4,pp. 562–583, 2011.[45] D. Huang, X. Hong, and M. Gerla, “Situation-aware trust architecture for vehic-ular networks,” Communications Magazine, IEEE, vol. 48, no. 11, pp. 128–135,2010.[46] M. Raya, P. Papadimitratos, V. Gligor, and J.-P. Hubaux, “On data-centrictrust establishment in ephemeral ad hoc networks,” in INFOCOM 2008. The27th Conference on Computer Communications. IEEE, 2008, pp. 1238–1246.[47] S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina, “The eigentrust algo-rithm for reputation management in p2p networks,” in Proceedings of the 12thInternational Conference on World Wide Web, 2003, pp. 640–651.[48] A. Koster, A. G. Tettamanzi, A. L. Bazzan, C. D. C. Pereira et al., “UsingTrust and Possibilistic Reasoning to Deal with Untrustworthy Communicationin VANETs,” in Proceedings of the 16th International IEEE Annual Confer-ence on Intelligent Transportation Systems October 6-9, 2013, The Hague, TheNetherlands, 2013.[49] H. Zhu, S. Du, Z. Gao, M. Dong, and Z. Cao, “A probabilistic misbehavior de-tection scheme toward efficient trust establishment in delay-tolerant networks,”Parallel and Distributed Systems, IEEE Transactions on, vol. 25, no. 1, pp.22–32, Jan 2014.[50] X. Li, Z. Jia, P. Zhang, R. Zhang, and H. Wang, “Trust-based on-demandmultipath routing in mobile ad hoc networks,” Information Security, IET, vol. 4,no. 4, pp. 212–232, 2010.103Bibliography[51] S. Sarkar and R. Datta, “A trust based protocol for energy-efficient routing inself-organized manets,” in India Conference (INDICON), 2012 Annual IEEE.IEEE, 2012, pp. 1084–1089.[52] T. Gazdar, A. Rachedi, A. Benslimane, and A. Belghith, “A distributed ad-vanced analytical trust model for vanets,” in Global Communications Conference(GLOBECOM), 2012 IEEE, 2012, pp. 201–206.[53] F. Go´mez Ma´rmol and G. Mart´ınez Pe´rez, “Trip, a trust and reputationinfrastructure-based proposal for vehicular ad hoc networks,” Journal of Net-work and Computer Applications, vol. 35, no. 3, pp. 934–941, 2012.[54] F. Dotzer, L. Fischer, and P. Magiera, “Vars: A vehicle ad-hoc network repu-tation system,” in World of Wireless Mobile and Multimedia Networks, 2005.WoWMoM 2005. Sixth IEEE International Symposium on a. IEEE, 2005, pp.454–456.[55] D. Tian, Y. Wang, H. Liu, and X. Zhang, “A trusted multi-hop broadcastingprotocol for vehicular ad hoc networks,” in Connected Vehicles and Expo (IC-CVE), 2012 International Conference on, 2012, pp. 18–22.[56] J. Wang, Y. Liu, X. Liu, and J. Zhang, “A trust propagation scheme in vanets,”in Intelligent Vehicles Symposium. IEEE, 2009, pp. 1067–1071.[57] D. Huang, S. A. Williams, and S. Shere, “Cheater Detection in Vehicular Net-works,” in Trust, Security and Privacy in Computing and Communications(TrustCom), 2012 IEEE 11th International Conference on. IEEE, 2012, pp.193–200.[58] Y.-C. Wei and Y.-M. Chen, “An Efficient Trust Management System for Balanc-ing the Safety and Location Privacy in VANETs,” in Trust, Security and Privacyin Computing and Communications (TrustCom), 2012 IEEE 11th InternationalConference on. IEEE, 2012, pp. 393–400.[59] M. H. Eiza and Q. Ni, “A reliability-based routing scheme for vehicular ad hocnetworks (vanets) on highways,” in Trust, Security and Privacy in Computingand Communications (TrustCom), 2012 IEEE 11th International Conferenceon. IEEE, 2012, pp. 1578–1585.[60] M. Teler and V. Cristea, “Securing Vehicular Networks Using DeterministicSchemes for Computing Trust,” in Intelligent Networking and Collaborative Sys-tems (INCoS), 2012 4th International Conference on. IEEE, 2012, pp. 214–221.[61] M.-C. Chuang and J.-F. Lee, “Team: Trust-extended authentication mechanismfor vehicular Ad Hoc networks,” pp. 1–1, 2013.[62] N. Haddadou and A. Rachedi, “DTM2: Adapting job market signaling for dis-tributed trust management in vehicular ad hoc networks,” in Communications(ICC), 2013 IEEE International Conference on. IEEE, 2013, pp. 1827–1832.104Bibliography[63] C. Liao, J. Chang, I. Lee, and K. K. Venkatasubramanian, “A trust model forvehicular network-based incident reports,” in Wireless Vehicular Communica-tions (WiVeC), 2013 IEEE 5th International Symposium on. IEEE, 2013, pp.1–5.[64] S. Buchegger and J.-Y. Le Boudec, “Performance analysis of the CONFIDANTprotocol,” in Proceedings of the 3rd ACM international symposium on Mobilead hoc networking & computing. ACM, 2002, pp. 226–236.[65] A. Das and M. M. Islam, “Securedtrust: A dynamic trust computation modelfor secured communication in multiagent systems,” IEEE Transactions on De-pendable and Secure Computing, vol. 9, no. 2, pp. 261–274, 2012.[66] D. Dolev and A. Yao, “On the security of public key protocols,” IEEE Transac-tions on Information Theory, vol. 29, no. 2, pp. 198–208, 1983.[67] T. Gazdar, A. Rachedi, A. Benslimane, and A. Belghith, “A distributed ad-vanced analytical trust model for VANETs,” in Global Communications Confer-ence (GLOBECOM), 2012 IEEE. IEEE, 2012, pp. 201–206.105
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Delay, reliability, and trust in information dissemination...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Delay, reliability, and trust in information dissemination in vehicular networks Rostamzadeh, Karim 2015
pdf
Page Metadata
Item Metadata
Title | Delay, reliability, and trust in information dissemination in vehicular networks |
Creator |
Rostamzadeh, Karim |
Publisher | University of British Columbia |
Date Issued | 2015 |
Description | The cost of road accidents globally is more than ＄500 B every year. Intelligent Transportation Systems (ITS) is a promising solution and Vehicular Networks is an ideal candidate for providing a communication platform for ITS applications. Safety-critical applications form the main motivation for intelligent transportation systems. Studying the major concerns in such applications, i.e., delay and reliability, through mathematical analysis is extremely beneficial because it enables us to design optimized schemes. Such analysis is, however, challenging due to the dynamics of a vehicular network. In this research, we have three main contributions. First, we present a mathematical model to study delay and reliability of emergency message dissemination in vehicular networks. This model includes three modules to address effects of channel, contention, and partitioning on delivery delay. This is the first delay model to the best of our knowledge that does all of these, and it gives network architects insight into the limitations of the network and helps them tune parameters such as transmission power and slot time duration. Simulation studies indicate that our model does capture the delay characteristics of vehicular networks for both highway and urban scenarios. An interesting observation from the analytical model confirms the fact that using the vehicle density on the road is a good metric for setting the right forwarding probability in vehicles. We exploit this conclusion and as our second contribution, we propose a completely distributed forwarding strategy, called Middle Is Next or MIN. Extensive simulations affirm the effectiveness of MIN in terms of delay and single-hop reliability in comparison with other well-known routing methods. Trusted communication in vehicular networks is of crucial importance without which all efforts for minimizing the delay or maximizing the reliability could be voided. As our third contribution, we propose FACT: Framework for Application-oriented Context-aware Trust-based communication in vehicular networks. FACT assigns a trust value to each road segment and one to each neighbourhood, instead of each car. Thus, it scales up easily and is completely distributed. Experimental results demonstrate that FACT outperforms other well-known routing protocols since it routes the messages via trusted paths. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2015-07-27 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0166438 |
URI | http://hdl.handle.net/2429/54174 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2015-09 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2015_september_rostamzadeh_karim.pdf [ 1.47MB ]
- Metadata
- JSON: 24-1.0166438.json
- JSON-LD: 24-1.0166438-ld.json
- RDF/XML (Pretty): 24-1.0166438-rdf.xml
- RDF/JSON: 24-1.0166438-rdf.json
- Turtle: 24-1.0166438-turtle.txt
- N-Triples: 24-1.0166438-rdf-ntriples.txt
- Original Record: 24-1.0166438-source.json
- Full Text
- 24-1.0166438-fulltext.txt
- Citation
- 24-1.0166438.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:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0166438/manifest