UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Designing location and mobility aware solutions for message dissemination in vehicular ad-hoc networks Hosseininezhad, Seyedali 2016

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2016_november_hosseininezhad_seyedali.pdf [ 1.1MB ]
JSON: 24-1.0314117.json
JSON-LD: 24-1.0314117-ld.json
RDF/XML (Pretty): 24-1.0314117-rdf.xml
RDF/JSON: 24-1.0314117-rdf.json
Turtle: 24-1.0314117-turtle.txt
N-Triples: 24-1.0314117-rdf-ntriples.txt
Original Record: 24-1.0314117-source.json
Full Text

Full Text

Designing Location and Mobility Aware Solutions forMessage Dissemination in Vehicular Ad-hoc NetworksbySeyedali HosseininezhadBSc., Amirkabir University of Technology, 2005MSc., Amirkabir University of Technology, 2008A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of Applied ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Electrical and Computer Engineering)The University of British Columbia(Vancouver)August 2016c© Seyedali Hosseininezhad, 2016AbstractVehicular Ad-hoc Network (VANET) is one of the potential solutions for provid-ing low cost and best efforts connectivity platforms which can coexist with cellularand WiFi technologies. Due to high mobility of nodes and short lifetime of links,server-to-client and server-to-server communications become challenging. Effec-tive context-aware broadcasting of information to the destination areas is also achallenge in VANET’s. It is usually assumed that the information about these areasis known a priori, either by a centralized source of information or by the entire setof vehicles. However, in reality, this information may not be available on demand.Message dissemination using partially known location information can reduce theoverall throughput of the network.We propose to enhance the performance of server selection in a heterogeneousVANET by taking link reliability into consideration in the server selection mecha-nism.Thereby, extra client-to-server hand-offs are avoided and the need of server-to-server synchronization is reduced.We also propose an adaptive broadcasting scheme based on distributed rein-forcement learning. In this scheme, vehicles collaboratively tune the rate of theirmessage broadcasts based on the network dynamics without any initial knowl-iiedge about the geographical distribution of Areas of Interest (AOI). The proposedapproach enables a more practical implementation of distributed context-awarebroadcasting, which requires no global information and only partial synchroniza-tion.In our third contribution, we propose a message dissemination algorithm forlocation-aware services in vehicular networks. The objective is to reduce informa-tion delivery time in intermittently connected urban vehicular networks by usinghistorical mobility information of vehicles. Roads are divided into dense and sparsepaths based on observed traffic density and vehicles share their current knowledgeabout fastest possible message delivery time to contouring dense roads.We evaluate and compare our methods to well known and related literature byrunning network and mobility simulations using tools such as network simulatorsNS2, NS3 and Matlab. Mobility simulations are done using SUMO simulator.iiiPrefaceThe following publications describe the work completed in this thesis. In somecases, the conference papers contain materials overlapping with the journal paper.All the chapters are based on these papers co-authored with Dr. Victor C.M. Leung,who also supervised the research. Dr. Ghasem Naddaf was involved in preparationand coding of the simulations for Chapter 3. I am the principal author of all thepublications which means that the ideas, calculations and evaluations presented inthese publications were done by me. Journal Paper Published:• Hosseininezhad, S., Leung, V., Reliability-based Server Selection for Het-erogeneous VANETs, ICST Transactions on Mobile Communications andApplications, Vol. 11, Issues 7-9, July-September 2011.Conference Papers Published:• Hosseininezhad, Seyedali, and Victor CM Leung. ”Location Management inHeterogeneous VANETs: A Mobility Aware Server Selection Method.” AdHoc Networks. Springer Berlin Heidelberg, 2010. 64-81.• Hosseininezhad, Seyedali, Ghasem Naddafzadeh Shirazi, and Victor Leung.”RLAB: Reinforcement learning-based adaptive broadcasting for VehicularivAd-Hoc Networks.” Vehicular Technology Conference (VTC Spring), 2011IEEE 73rd. IEEE, 2011.• Hosseininezhad, Seyedali, and Victor Leung. ”Data dissemination for delaytolerant vehicular networks: using historical mobility patterns.” Proceedingsof the third ACM international symposium on Design and analysis of intel-ligent vehicular networks and applications. ACM, 2013.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Reliability Based Server Selection for Heterogeneous Vehicular Ad-hoc Network (VANET) . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.1.1 Service Discovery in Mobile Ad-hoc Network (MANET) . 102.1.2 Location Services and Server Selection Problem . . . . . 14vi2.2 Location Management over Heterogeneous VANET - The Architec-ture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3 Mobility Aware Service Selection and Packet Relay . . . . . . . . 192.3.1 Reliability vs. Distance . . . . . . . . . . . . . . . . . . . 212.3.2 Reliability Measurement . . . . . . . . . . . . . . . . . . 222.3.3 Potential Assignment for Path Construction and Server Se-lection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.3.4 Location Update . . . . . . . . . . . . . . . . . . . . . . 272.3.5 Location Query . . . . . . . . . . . . . . . . . . . . . . . 282.4 Performance Evaluations . . . . . . . . . . . . . . . . . . . . . . 282.4.1 Hybrid Network Scenario . . . . . . . . . . . . . . . . . 392.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403 Reinforcement Learning-based Adaptive Broadcasting for VANET . 433.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.1.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . 453.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.2.1 State Space . . . . . . . . . . . . . . . . . . . . . . . . . 493.2.2 Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . 493.2.3 State Transitions . . . . . . . . . . . . . . . . . . . . . . 503.3 RLAB: Distributed Q-Learning with Local States . . . . . . . . . 503.3.1 Calculating Immediate Rewards . . . . . . . . . . . . . . 523.3.2 Calculating Delayed Rewards . . . . . . . . . . . . . . . 533.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . 543.4.1 Convergence . . . . . . . . . . . . . . . . . . . . . . . . 55vii3.4.2 Broadcast Comparison . . . . . . . . . . . . . . . . . . . 573.4.3 Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584 Data Dissemination for Delay Tolerant Vehicular Networks: UsingHistorical Mobility Patterns . . . . . . . . . . . . . . . . . . . . . . . 604.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.2 Message Dissemination in VANET . . . . . . . . . . . . . . . . . 674.3 Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 694.3.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . 694.3.2 Road Segment Categorization . . . . . . . . . . . . . . . 704.3.3 Exploitation of Travel History and Contacts . . . . . . . . 724.3.4 Calculating Travel Time . . . . . . . . . . . . . . . . . . 744.3.5 Travel Time Synchronization . . . . . . . . . . . . . . . . 754.3.6 Data Dissemination Algorithm . . . . . . . . . . . . . . . 774.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 83Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89viiiList of TablesTable 2.1 Variables definition in (2.11) . . . . . . . . . . . . . . . . . . 33Table 3.1 Variables definition in (3.1) . . . . . . . . . . . . . . . . . . . 51Table 4.1 Important Simulation Parameters . . . . . . . . . . . . . . . . 78ixList of FiguresFigure 1.1 VANET is composed of Vehicle to Vehicle (V2V) and Vehicleto Infrastructure (V2I) communication. [1] . . . . . . . . . . 4Figure 2.1 Heterogeneous VANET Architecture for Location Management 17Figure 2.2 Variation in neighbors regarding their relative speed . . . . . . 24Figure 2.3 Extracted map of Vancouver downtown from OpenStreetMap[2]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Figure 2.4 Simulation Procedure . . . . . . . . . . . . . . . . . . . . . . 30Figure 2.5 Linear prediction average error for three scenarios . . . . . . 32Figure 2.6 Average Client-Server Connection Lifetime (Downtown) . . . 34Figure 2.7 Average Client-Server Connection Lifetime (Highway) . . . . 35Figure 2.8 Normalized overhead of update packets being sent over Wire-less Local Area Network (WLAN) and Worldwide Interoper-ability for Microwave Access (WIMAX) (K=100) . . . . . . . 36Figure 2.9 Signaling cost based on cost factor (K) in (2.11) . . . . . . . . 36xFigure 2.10 Average Client-Server Message Passing Delay in Downtown(Only Query/Response messages are considered for QuorumBased Method) . . . . . . . . . . . . . . . . . . . . . . . . . 37Figure 2.11 Average Client-Server Connection Lifetime with Hybrid Net-work in Highway . . . . . . . . . . . . . . . . . . . . . . . . 40Figure 2.12 Scaled Proportion of Network Usage . . . . . . . . . . . . . 41Figure 3.1 Two applications with different domains of interest. . . . . . . 46Figure 3.2 Delayed rewarding after message is found useful: Black car insegment B5 uses message and reward is given to segments inwhich packet was broadcast. . . . . . . . . . . . . . . . . . . 53Figure 3.3 Normalized Deviation in value of state Good in a useful roadsegment vs. simulation time (seconds) . . . . . . . . . . . . . 55Figure 3.4 Number of Broadcasts sent vs. simulation time (seconds) . . . 56Figure 3.5 Normalized Cumulative Ratio of Useful Broadcasts to TotalNumber of Broadcasts vs. simulation time (seconds) . . . . . 56Figure 3.6 Packet delivery delay for Areas of Interest (AOI) vs. simulationtime (seconds) . . . . . . . . . . . . . . . . . . . . . . . . . 57Figure 4.1 Sample scenario: Two different frequent paths can be usedbased on frequent trajectory patterns. . . . . . . . . . . . . . 68Figure 4.2 Streets in city of Cologne, Germany extracted from [3]. denseroads are shown in dark. . . . . . . . . . . . . . . . . . . . . 75Figure 4.3 Data delivery ratio for each running iteration. . . . . . . . . . 79Figure 4.4 Average delay of first data delivery as a function of the numberof sources. . . . . . . . . . . . . . . . . . . . . . . . . . . . 80xiFigure 4.5 Generated traffic per kilobyte of background Data when net-work is fully utilized. . . . . . . . . . . . . . . . . . . . . . . 81xiiGlossaryVANET Vehicular Ad-hoc NetworkDOD U.S. Department of DefenceMANET Mobile Ad-hoc NetworkDSRC Dedicated Short Range CommunicationsWAVE Wireless Access in Vehicular EnvironmentsFCC Federal Communications CommissionETSI European Telecommunications Standards InstituteITS Intelligent Transportation SystemsV2V Vehicle to VehicleV2I Vehicle to InfrastructurePCN Post Crash NotificationCRN Congestion Road NotificationLCA Lane Change AssistancexiiiCCW Cooperative Collision WarningAOI Areas of InterestGPS Global Positioning SystemWIMAX Worldwide Interoperability for Microwave AccessWLAN Wireless Local Area NetworkRSSI Radio Signal Strength IndicationRLAB Reinforcement Learning-based Adaptive BroadcastRSU Road-Side UnitTTI Traffic and Travel InformationxivAcknowledgmentsFirst, I would like to express my gratitude to my supervisor Dr. Victor Leung forhis support and guidance throughout my years in UBC. I would also like to thankDr. David Michelson and Dr. Garland Chow for their invaluable feed-backs on myresearch.My sincere thanks also go to Dr. Ghasem Naddafzadeh Shirazi for his collab-oration in my research. I would also like to take this opportunity to appreciate thefriendship and companionship of my endeared UBC friends Mr. Mohsen Amiri,Dr. Kaveh Shafiee, Dr. Hasen Nicanfar, Dr. Javad Hajipour and Dr. PeymanTalebifard. Their insights and supports made it possible for me to carry on.I would like to thank my father, my mother and my siblings Mehdi, Susan,Nasrin and Mitra for their support and love. Without them I would have nevermade it.Last but definitely not least, I would like to thank my beautiful and kind-heartedwife, Golnoosh Saeedi Nejad. Her unconditional love and kindness, her selfless-ness and sacrifices, her lovable personality are all exemplary and unique. Herpresence beside me during all the ups and downs of the last 7 years has been thexvindispensable inspiration and the crucial motivation I needed to continue. Withouther, I would have been lost in many cross-roads I faced during the last decade.xviChapter 1IntroductionThe advances in the field of ad-hoc wireless networking is one of the most sig-nificant developments in networking and telecommunications in the last 15 years[1,2]. The research in this domain started to fulfill the military needs, speciallyas sponsored by the U.S. Department of Defence (DOD) for purposes such as mil-itary combat operations in hostile territories. However, the application domainhas since evolved tremendously and have grown to include the synergistic areaof sensor networks. Military applications are still the target of the majority ofthe research in these areas. This approach has changed, specially within the lastdecade, with the advent of the automobile industry showing interest in the futureof Vehicular Ad-hoc Network (VANET), mainly for safety applications. This isthe largest commercial application of ad hoc networks which are realistic and areproposing concrete applications (such as safety) and the underlying technology isdriven forward in this domain. With the development in wireless communications,Intelligent Transportation Systems (ITS) applications are proposed for car-to-carcommunication standards. Protocols such as Wireless Access in Vehicular Envi-1ronments (WAVE) [4] and Dedicated Short Range Communications (DSRC) [5] areproposed as ground work for vehicular communications. WAVE and DSRC stan-dards are in IEEE 1609.1-4 and 802.11p respectively. So far, the Federal Com-munications Commission (FCC) has dedicated a 75Mhz bandwidth in 5.9Ghz band[6] and the European Telecommunications Standards Institute (ETSI) has allocated30MHz of spectrum in 5.9GHz for ITS [7]. These allocations vividly indicate thatthis is a trend and it is destined to grow into commercially viable technologies [3,4].VANETs are emerging as one of the most important practical applications ofMobile Ad-hoc Network (MANET). ITS are the first category of application inthis scheme that has drawn the attention of researchers and engineers. Many au-tonomous intelligent systems have already been implemented on-board for vehi-cles. However, cooperative networking of vehicles is uncommon today and willbe more prevalent in the future. Wireless data communications will have a hugeimpact on the ITS.Over the past few years, numerous dissemination protocols have been proposedfor VANETs. These protocols can be categorized in two main groups of:• Single-hop dissemination• Multi-hop dissemination/routingThe main difference between these two categories is the re-broadcasting andrelaying of the packets. In single-hop dissemination, vehicles do not flood thepackets. Upon receiving a packet, vehicle saves the message and will carry thepacket along the road in its itinerary. The information is re-distributed to the othervehicles when a new contact is discovered. These methods are also called carry-2and-forward methods. The following protocols belong to this category: SODAD[8], TrafficInfo [9], TrafficView [10], CRCP [11] and Abiding Geocast [12].In multi-hop information dissemination, a packet propagates through the net-work by fast rebroadcasting (a.k.a. flooding). In general, when a source vehicledisseminates a packet, some of the adjacent vehicles become the next hop and re-lay node and perform a relaying task by re-iterating the packet further. Similarly,after a relay node rebroadcasts the packet, some of the vehicles in its vicinity willbecome the next relay nodes and forward the packet further. As a result of themulti-hop dissemination, the information packet will be able to propagate from thesource to the other distant vehicles.The common focus in both of the categories is to reduce the excessive rebroad-cast packets. In multi-hop dissemination protocols, the rate control is done byaddition of a delay and probability assignment functions. These methods adjustthe waiting delay and the rebroadcast probability relative to the vehicle locationand the physical characteristics of the context such as the vehicle density. Readerscan find more information regarding these methods in papers such as [13–17] fordelay control and papers such as [17–20] discuss dissemination probability basedon the context. The number of packet transmissions may also be controlled us-ing network coding approaches. In single-hop broadcasting protocols, where eachvehicle rebroadcasts the packet periodically, the suppression of excessive rebroad-cast packets is usually done by letting each vehicle adjust its rebroadcast intervaldynamically. For network coding approaches readers can refer to [21–23]. Thesemethods are beyond the scope of our research and we will not discuss this category.The main characteristic of VANETs is that its nodes are vehicles equipped withon-board devices, commuting on predefined trajectories (i.e., roads and lanes).3Figure 1.1: VANET is composed of V2V and V2I communication. [1]There are two types of communication in VANET: communication among vehic-ular nodes for dissemination of messages via V2V communication protocols, andcommunication between vehicles and fixed road-side Access Points (i.e.,WAN orcellular network infrastructure), known as V2I communication.Connected vehicles constitute the future of concurrent use of technologies forcomputers, data infrastructures, and vehicles. Vehicular communication is alsoan enabler for driver-less cars in the future. Currently, there is a strong need to4enable vehicular communication for applications such as safety messaging, trafficand congestion monitoring and general purpose Internet access and infotainment.VANETs are emerging to deploy new and traditional applications. They arecharacterized by high mobility, dynamic topology, and ephemeral, one-time inter-actions. Both VANETs and MANETs are characterized by the movement and self-organization (therefore ad-hoc). However, due to high speeds movement and largetopologies as well as distinct mobility patterns, VANET’s characteristics are intrin-sically different from the typical features of MANETs. VANETs are also character-ized by rapid but somewhat predictable topology changes, with frequent topologyfragmentation and small effective network diameter.Vehicular applications are classified in three categories (i) active road safetyapplications, (ii) traffic efficiency and management applications, and (iii) comfortand infotainment applications [24]. Active road safety is the first and foremost cat-egory and it is designed to help drivers and other road users to reduce the risk of caraccidents which results in improving the general road safety. This is done by dis-seminating information about hazards and road obstacles, and thus increasing thedrivers’ awareness and allowing him/her to react faster. Active road safety is themost demanding category. Vehicles collaborate to provide crucial safety informa-tion to other vehicles in the Areas of Interest (AOI) [25, 26]. In these applications,message propagation is very sensitive to delays. Consequently, a message wouldbe unworthy if propagation to a desired area is not fast enough. Safety applicationsare always necessary to reduce the number of accidents. The main focus is to avoidaccidents in the first place. For example, TrafficView [10] and StreetSmart [27] in-form drivers about traffic conditions in their close proximity and farther down theroad. Vehicle platooning is another way to improve road safety [28]. By eliminat-5ing the complexity of lane change and speed correction, platooning allows vehiclesto travel efficiently and safely together [27]. Some of the most promising applica-tions which are under study by several car manufacturers are Post Crash Notifica-tion (PCN), Congestion Road Notification (CRN), Lane Change Assistance (LCA)and Cooperative Collision Warning (CCW). In all of these applications, V2V isplaying a key role in facilitating the connectivity and information disseminationamong vehicular nodes.The second category of applications, i.e. traffic security and management, isaimed at optimizing vehicular traffic flows by reducing travel time and avoidingtraffic jam situations. Applications such as enhanced route guidance/navigation,traffic light optimal scheduling, and lane merging assistance, are designed to op-timize routes, and to help in reduction of greenhouse gas emissions and fuel con-sumption [29, 30]. The delay constraint in this category is not as strict as the firstcategory. Therefore the amount of data can be expanded and also the area of inter-est can be larger than of the first category.The third category, i.e. the comfort and infotainment applications, is designedto create added value and commercial opportunities by increasing the number ofvehicles equipped with on-board wireless devices. This category of applicationscan provide the road users (on-board and pedestrians) with context sensitive infor-mation and entertainment to improve the experience. Multimedia streams, newsbroadcasting, entertainments, peer to peer applications, local advertisements, carpooling and local cab services are some examples of the broad range of feasibleapplications. To facilitate these applications, vehicles should be equipped withpositioning and communication devices [31–34].6The overall objective of the works presented in this thesis is to facilitate andimprove message dissemination performance for applications and services whichare essential in a VANET. Our focus is specifically on exploiting mobility and loca-tion information of the contributing nodes in the network to decrease the overheadsimposed by protocols and services.At the time of writing this thesis, there have been several citations to our publi-cations. For example we can mention [35], [36], [37],[38],[39],[40], [41] and[42].During recent years, there have been several survey papers covering delay tol-erant VANET’s, such as [43], [44] and [45].Furthermore, a new line of research about VANET’s has been opened. Social-aware routing in delay tolerant networks is described as a mean to provide contextto vehicular networks. The social context is comprised of the social interactions ofthe nodes, which can offer an insight on how the social relationships among nodeshave been created [46].In Chapter 2, we focus on the enhancement of server selection in VANETs whileworking in heterogeneous network environments. We propose a method to measureand use link reliability in choosing the mobile server. We assumed that the serversare special vehicles equipped with short range and long range wireless technolo-gies. Short range network is used to communicate with surrounding vehicles (i.e.clients) and long range wireless connections are used to create a mesh network ofservers. This type of environment has been chosen because in practice vehiclesequipped with long range and short range wireless connections have lesser marketpenetration compared to vehicles equipped with short range only. Therefore thesevehicles can act as service providers to other vehicles in situations that there is notenough infrastructure in the environment.7In Chapter 3, we focus on targeted (context aware) broadcasting in homoge-neous VANETs. We assume that disseminated information is either generated byvehicles on road or is originated from a road side unit and is handed to vehiclesto be disseminated towards areas of interest. The goal is to choose the broadcast-ing scheme without any prior knowledge about geographical distribution of areaswhere information may be considered as useful information. In this chapter, we tryto show that we can adaptively tune the rate and direction of message disseminationwith the feed-backs received from information recipients.In Chapter 4, we turn our attention to link instability in VANETs. Vehicle pop-ulation density in different geographical regions may vary and thus the stability ofrelay path in vehicular networks is not deterministic. In these situations, informa-tion dissemination can be interrupted frequently. Therefore, carry and forward isutilized to avoid data loss. In urban areas the density of on road vehicles is differentin major roads (dense) compared to other areas. We propose a message dissemi-nation approach with consideration of the fact that major roads in cities normallycreate contouring edges around areas with less traffic. In our proposed messagedissemination algorithm, vehicles share their knowledge about dissemination delayfor the major roads to form a distributed global knowledge of the vehicle densityin nearby major roads. Using this information, the direction of dissemination ischosen and messages are relayed to the closest major roads.8Chapter 2Reliability Based Server Selectionfor Heterogeneous VANETHeterogeneous wireless networks are capable of providing customers with betterservices while service providers can offer more applications to more customerswith lower costs. To provide services, some applications rely on existing servers inthe network. In a VANET some mobile nodes may function as servers. Due to highmobility of nodes and short lifetime of links, server-to-client and server-to-servercommunications become challenging. In this chapter, we propose to enhance theperformance of server selection by taking link reliability into consideration in theserver selection mechanism, thereby avoiding extra client-to-server hand-offs andreducing the need of server-to-server synchronization. As a case study, we focuson location management service in a heterogeneous VANET.We provide a routing algorithm for transactions between location servers andmobile nodes. We assume that location servers are vehicles equipped with at least9one long-range and one short-range radio interface, whereas regular nodes (clients)are only equipped with a short-range radio interface. The primary goal of our de-sign is to minimize hand-offs between location servers while limiting the delaysof location updates. Taking advantage of vehicle mobility patterns, we propose amobility-aware server selection scheme and show that it can reduce the number ofhand-offs and yet avoid large delays during location updates. We present simula-tion results to show that proposed scheme significantly lowers the costs of signalingand rate of server hand-offs by increasing the connection lifetime between clientsand servers.2.1 IntroductionVANET’s are emerging as one of the most important practical applications ofMANET. As the demand for pervasive computing is increasing, providing ser-vices to nodes in the network is also becoming critical. For instance, locationmanagement is becoming one of the most important modules in vehicular net-working. Multimedia streams, news broadcasting, entertainment and other appli-cations which require Internet connectivity, peer-to-peer applications, local adver-tisements, vehicle pooling and local cab services are some examples of the broadrange of feasible applications when vehicles are equipped with positioning andcommunication capabilities [31, 33].2.1.1 Service Discovery in MANETIn MANET with various devices in the network, a service is a facility or capabil-ity that is provided by some of the nodes that can be used by other mobile nodes.These services are usually implemented as an application inside the nodes. Service10discovery has been solved in wired networks and single hop wireless networks.DEAPSpace [47] is a service sharing mechanism produced by IBM research forshort-range, single hop wireless networks. However, in multi-hop mobile net-works, the physical proximity and mobility of nodes are issues that impact servicediscover. Therefore existing approaches may not be suitable for multi-hop MANET.Service discovery protocols consist of four components:• Service Description provides an abstraction of the services being provided.This information help clients to choose between provided services and con-nect to the server which is providing required services. Usually a servicedescription is composed of server identification, server characteristics andservice characteristics.• Service Registration and Advertisement includes the procedure of storingservice descriptions in nodes and advertisement of the services in the net-work. Depending on the approach, advertisement and registration could besimple flooding of information or based on a hierarchical directory storageapproach.• Service Discovery is the method employed by requesters to find services.Service discovery can also include the decision making mechanism to choosebetween available services. Service discovery and service advertisements arecomplementary to each other in a system. Therefore, more complexity in onecould be traded off for more simplicity in the other. When the services arediscovered, the service selection is done based on some criteria.11• Routing includes the process of relaying service advertisements, service dis-covery, service requests and replies. Routing could be done based on differ-ent criteria as well. Since we are focusing on VANET’s with very high nodemobility, the performance of routing is very sensitive to decision makingmechanisms used in service discovery. A combination of good advertise-ment and service discovery methods could decrease the number of neededpacket relays and lower the rate of route changes in the network.There are several service discovery methods designed for MANETs [48–50].Based on literature, service discovery mechanisms are divided into directory basedvs. directory-less approaches. In networks with high mobility, less reliance ontopology information would lead to a better performance because the topologyis changing very fast and updating would be very costly. Therefore instead ofdirectory based methods like [49], directory-less methods have been proposed [48].In a survey by Mian et al. [51] service discovery protocols are categorizedbased on their performance under various network conditions. Based on this com-parison, there is a trade-off between the extent of covered area and supported mo-bility. There is no one-size-fits-all method that is capable of handling high mobilitywhile the size of network is relatively large.Service Discovery Inspired by Field TheoryLenders et al. [48] defined an approach for efficient and robust service discovery.This concept is similar to anycast routing, which is supported in IPv6 [52]. Inanycast routing, an address is associated with more than one interface belonging todistinct nodes that are similar in nature. As it is preferable for clients to get service12from the nearest among several potential servers, use of anycasting would allowthe desired server to be reached easily.From electromagnetic field theory, the point potential of a spot is related to itsdistance to the maxima potential charge. In wireless networks, the most commonlyused definition for distance is based on hop count; nonetheless geographical dis-tance is also applicable. In [48], hop count is considered as the distance betweennodes:ϕ(n) =N∑i=1Qidist(n,ni), (2.1)where Qi is the potential assigned to server i and ϕ(n) is the total received potentialby node n from all servers. The amount of potential assigned to each server couldbe a factor of their capacity or quality of service (QoS) metrics.Reliability Consideration in Route SelectionWhereas in highly mobile networks, hop-based distance metrics may be unreliableand unstable, and route maintenance may cause extra signaling overhead and delay,route reliability can be a more suitable metric for route selection. Longevity of aroute is introduced in [53] as a new metric for route assessment, measured by theassociation between two nodes. It is assumed that a link is reliable if the associationbetween the two end-nodes is higher than a certain threshold. A route-lifetimeassessment based routing (RABR) algorithm is proposed in [54], in which routeselection is based on a hybrid criteria of route lifetime and path length. The routelifetime is measured by the link affinity, which is calculated based on the receivedsignal strength. Since in practice the signal strength varies over time, RABR canmake wrong decisions especially in an urban environment with rapid signal fading.13It is desirable to utilize the concept of link lifetime as a decision factor in routing,but a new measure of link lifetime tailored for the variable conditions of VANET’sis needed.2.1.2 Location Services and Server Selection ProblemWith increasing demand for pervasive computing, location management is becom-ing an essential function in VANET’s. Location management is a service for de-termination of each vehicle’s location and making this information available toother nodes. A location management system is generally composed of locationservers and clients. Location servers are responsible to hold the location informa-tion of clients and to retrieve the information to requesters. Nowadays localizationtechnologies have become widespread and it is a justifiable assumption that all ve-hicles in a VANET can determine their positions using on-board Global PositioningSystem (GPS) receivers. Therefore we assume that each vehicle can determine itsgeographic coordinate and report it to the corresponding location server(s). Sinceconnection to stationary resources may not be guaranteed in VANET’s, vehiclesshould form a location management overlay on the infrastructure-less network.When mobile clients need to register, update or query about location informationof other nodes, they should choose a server based on proper decision factors andsend their request to it. Choosing a server for location service can be considereda specific case of server selection in service discovery. We shall next provide ashort review of current location management approaches and their limitations. Weshall consider location management as a specific scenario of service discovery, andpropose a method to select location servers in a heterogeneous VANET.14Location Management Methods in MANETSeveral protocols have been designed to handle the mobility of nodes [55–62].Location servers are responsible for handling the geographic location informationof nodes in the vicinity and provide them to others when needed. Different cate-gories of location management have been classified in to flooding-based locationmanagement and quorum-based location management.Flooding-based location management is the most straight forward method forpassing location information. Due to high redundancy overhead, researchers havestrived to decrease unnecessary packet relays. The hypothesis of methods likeDREAM [56] is that relative locations of closer nodes are changing faster com-pared to nodes far away from each other. Therefore, location updates are sent morefrequently to location servers close by than those that are farther away.Quorum-based location management is another category that is based on assur-ing a rendezvous between queries and updates. A localized quorum-based locationservice is proposed in [57], which disperses the location of every node horizon-tally and vertically. As the authors have stated, this method is proper for networkswithout a significant relative motions. VANET’s with high relative speeds are notsuitable environments for this class of location management systems.The GLS method [58] for distributed location service management divides thearea into different degrees of grids in a way that in every grid around the nodethere is a fixed number of servers that collect location information about that node.As grids grow larger, the probability of a server being chosen for other nodesdecreases. This method is not very flexible for highly variant environments likeVANET’s. Hierarchical methods [61, 62] for server allocation are highly scalable15because the rates of location updates are reduced for servers in higher levels. How-ever, in VANET’s, the number of servers may not be very high and forming a hier-archical structure may not be feasible.In high mobility networks such as VANET’s, keeping track of location informa-tion would be a huge overhead on the network if location information is saved onall location servers. Therefore having the record of every node in network whilenodes are rapidly changing their locations can be performed better if we are able tosave this information in a specific set of nodes. Moreover, to reduce the detrimen-tal effect of mobility, we focus on hop-by-hop packet relaying rather than finding adeterministic route from clients to servers. We consider location management as aservice to vehicles, which is offered by some specific nodes in the area. Thereforewe need a service discovery mechanism to find the service providers.Many different wireless access technologies can be employed in VANET’s.Short-range technologies include wireless local area networks (Wireless LocalArea Network (WLAN)s) and its variant called DSRC, specifically targeting vehic-ular communications. Long-range wireless technologies include cellular networksand wireless metropolitan area networks such as Worldwide Interoperability forMicrowave Access (WIMAX). VANET’s employing short-range radio access faceproblems in area coverage and fast hand-offs between nodes. Because of high mo-bility speed, rate of hand-offs in the network becomes a limiting factor in locationregistration and updates.In the presence of these difficulties, heterogeneity can come to the rescue forservices like location management. Using long-range wireless access as a higherlayer of communications, we can interconnect location servers together as a logicalmesh network. We can assume that a connected graph of location servers can16Cellular ConnectivityLS1LS4LS2LS3Multi-homed (Public Transit)Single-homed (Private Car) 3G/WiMAX link 802.11 linkEgress NetworkEgress Location ServerConnection PeerConnection PeerConnection PeerFigure 2.1: Heterogeneous VANET Architecture for Location Managementexchange signaling messages through this logical mesh network. We shall base ourwork on utilizing available long-range wireless connections to facilitate locationmanagement in VANET’s.In Section 2.2 we propose an architecture for a heterogeneous VANET to pro-vide location service. After clarifying the problems and challenges in this serverselection scenario, we present the proposed method for reliability-based server se-lection in Section 2.3. In Section 2.4 we give the methodology for performanceevaluations, present the results and discuss their significance. Section 2.5 con-cludes the chapter.2.2 Location Management over Heterogeneous VANET -The ArchitectureFig. 2.1 depicts a heterogeneous VANET architecture with partial Internet connec-tivity. In this system, nodes equipped for heterogeneous wireless access are con-17nected to each other and edge gateways using their long-range wireless access ca-pability.The requirements and assumptions in the aforementioned architecture are:1. All vehicles are considered to have a mechanism to extract their own geo-graphic location, e.g. using an onboard GPS receiver.2. All nodes are equipped with at least one short-range radio (e.g.802.11a/b/g/p).3. Some special nodes with heterogeneous wireless access capability areequipped with all valid short-range communication interfaces and one long-range communication interface (e.g., WIMAX). These nodes function as lo-cation servers that are interconnected to each other in a logical mesh networkto exchange their location records, and to stationary gateways for Internet ac-cess.4. In consideration of valuable licensed spectrum used for long-range wirelessaccess, the use of long-range radio should be minimized. Therefore, it is ourgoal to reduce the numbers of queries between servers and server hand-offsfor vehicles.5. Location queries and updates should not be propagated more than a certainnumber of hops.6. Server advertisements should not be rebroadcasted more than a certain limit.In one scenario of this architecture, a public transportation system providesa wireless Internet relay service inside an urban area. Public transit vehicles are18equipped with multiple radios and they are tasked to provide connectivity and re-lated services to other vehicles. They utilize their long-range radios to relay localdata network traffic to stationary gateways and to provide a location managementservice to vehicles in their vicinity by exchanging location information with otherlocation servers.For location servers to advertise location service and receive updates andqueries from vehicles, we propose a service discovery mechanism to find routesto location servers in the area with the best matching mobility pattern. We shallevaluate the effect of this service discovery method with different scenarios of ur-ban and highway mobility.2.3 Mobility Aware Service Selection and Packet RelayVehicular mobility patterns (urban or highway) generally follow roadways withrandom changes of directions at intersections. We assume that every vehicle re-sponsibly sends its location information to a location server. This location in-formation can be used by other vehicles or service providers to present locationbased services. When a vehicle and its location server move away from each otherand the distance grows more than a certain hop distance, path delay and high linkbreakage probability make their interactions ineffective. Therefore the client hasto hand off from the old server to another server that is better in terms of delay,robustness and lifetime. Every hand-off between two location servers is comprisedof several ’server to server’ and ’server to client’ signalling interactions. However,server-to-server interaction are more expensive because they use licensed spectrumto communicate.19Based on expectations and assumptions in the architecture of Fig. 2.1, if wewant to use the field theory approach explained before, clients should send theirlocation management packets toward other relays or servers in the vicinity, whichhave the highest potential. Signalling for a location update comprises of a primaryphase of registration between client and server. After the registration, the clientis able to update the server periodically or when triggered by specific events. If aclient is unable to send updates to the designated server, a new registration withan available server is required. Based on our proposed architecture and locationmanagement procedure, the field theoretic method reviewed in Section 2.1.1 hasthe following deficiencies that should be addressed:1. The measure for distance between nodes is unrealistic, since mobility patternis not considered in server selection. In our case, the relative speed between aclient and its server defines the connectivity lifetime and we prefer to choosea server that has a higher connectivity lifetime as long as the path delay isless than a certain limit.2. The server selection is stateless. Service discovery would lead to a set ofchoices for each relay to forward the packet. However there is no guaranteethat a packet will be relayed to the same server to which the former packetis sent. It is desirable for a client to send location updates to a server thatit has already registered in. It means that if a client selects a server withhighest potential as its location server, all the relay nodes should be notifiedto relay the packet from that client toward the same server. Consequently,a server hand-off does not happen unless the delay threshold is exceeded ordisconnection occurs.20By modifying the service discovery method proposed in [48], we propose a lo-cation management method that minimizes hand-offs, which is applicable to geo-graphical and topological location management.2.3.1 Reliability vs. DistanceHop distance is a simple and effective criterion for route selection, but in cases withhigh mobility this measure is very unstable. To avoid this problem we propose touse link stability and usability (also known as reliability) as the route selection cri-teria instead. The set of links in the chosen path between s and d is P(s,d). Wewant to account for reliability of each link l ∈ P(s,d) and choose a path with high-est aggregated reliability. Reliability of a link is directly related to the estimatedlink lifetime. However, calculation of reliability includes error and an unmeasuredfactor of future alternative connections. For instance, a weak link could be replacedin the future by a new relay node which is not present at the moment. Due to thisfactor, it is not rational to underrate a path by considering the reliability of theweakest link in the path as decision factor. On the other hand, we cannot rely onarithmetic average because strong links in the path would cause overestimation ofthe path reliability.Since we want the factor to tend toward the most realistic reliability value ofthe path (to mitigate the impact of links with excellent reliability in calculation oftotal path reliability), we desire to have the smallest average value as the measuringfactor. Instead of using arithmetic mean, we use harmonic mean to calculate thereliability factor. Harmonic means tend toward the smallest values compared togeometric and arithmetic means. Hence, with rl being the reliability of link l and21the number of hops |P(s,d)|= n we have:11n ∑l∈P(s,d))1rl≤ n√∏l∈P(s,d)rl ≤ 1n ∑l∈P(s,d)rl . (2.2)To apply the value of reliability in routing decision, we define the distance factorin (2.1) as:D(s,d) =1n ∑l∈P(s,d)1reliability(l). (2.3)In every calculation period, each node will predict the locations of current neigh-bors and based on estimated path-loss exponent of the environment and foreseenmobility patterns, calculate the link’s lifetime. Path prediction and lifetime estima-tion are two major ongoing research topics and they are explained more in 2.3.2.Intuitively, a longer link’s lifetime leads to a more reliable path between nodesand location servers. Notwithstanding, due to high error rates in prediction mech-anisms [63], we cannot rely solely on measures of one link. Therefore, we willdefine reliability factor for all (node,server) pairs to show how reliable the nodecould be to relay packets toward the server. Based on the assumption that a highernode density can make the route more reliable, we define the reliability factor asthe probability of a packet being successfully relayed by a node to another whichis closer to server.2.3.2 Reliability MeasurementWe define the link reliability between two neighbors as the estimated expectedremaining time of connectivity between the node-pair. To calculate the link relia-bility we assume that each node will listen to data packets and beacons sent by itsneighbors. Using sampled signal characteristics and location information, the re-22ceiver predicts how link condition will change in the future. Therefore, to calculatethe reliability factors, nodes need to have knowledge about future variations in linkconnectivity. In [64] a method for estimating link residual time and link stabilityhas been proposed. In this method, after denoising and classification of the Ra-dio Signal Strength Indication (RSSI) from neighbors, future lifetime is estimated.In [63], Euclidean distance information is utilized to estimate future trajectory. Itseems that by using relative mobility between nodes and digital map informationtogether, future estimations can become more precise [65]. A method to calculatethe probability of turns in road intersections is proposed in [66], based on the theorythat turning options that lead to more destinations in shorter times are more popularthan those that lead to local areas or take more time to reach destinations. In [67],mobility behavior of nodes is used to classify their transportation mode. Moreover,using particle filter method they estimate parameters in a Bayesian network forpath selection decisions. By learning these parameters, they try to estimate futurevelocities and turning selections.Fig. 2.2 shows an example of vehicular mobilities in two time steps. The vari-ations in links caused by their relative speeds are visible. In this example, nodes 5and 6 will get into the range of S while 1, 3 and 4 move out of range. Therefore,the reliability of a connection with 5 from S is less than that with k or 2.To calculate the link reliability in a path toward a server, every node will cal-culate the cumulative probability of connectivity to the next hop for each server.The next hop is defined as any node in communication range that has a loop-freepath to the server. In practice every node can put a short hash value of its uniqueaddress in the forwarded advertisement to avoid considering the routes which are23S VS2 V23V31V1k Vk4V 45 V56V6(a) t = 0S VS2 V23V31V1k Vk4V 45 V56V6(b) t = ∆tFigure 2.2: Variation in neighbors regarding their relative speedoriginated from itself. Hashing can reduce the length of a string to a few bits andyet avoid duplicate indexes with a high probability.We assume that a link connectivity prediction method can provide a processconsisting of connectivity probabilities during a prediction period. For a specificenvironment and mobility pattern, a prediction method is able to predict futuremotions and channel states for n time units. Moreover, we can extract the averagepercentage of error in lifetime prediction (which can be empirically found) as E(eˆ).This error extraction could be enforced to the system as an a-priori known measureor it could be re-adjusted based on observations from the past (by comparing pre-diction and real condition after it happened). Therefore, Pl(i)(t) is the probabilityof link l(i) being connected from t0 (now) until t0+ t and is equal to:Pl(i)(t) = (1−E(eˆ))P(Lˆi, t) , (2.4)24where P(Lˆi, t) represents the link condition (alive/dead) which is calculated us-ing the desired mobility prediction method. As mentioned before, each mobilityprediction and link classification method has a distinct estimation capability in dif-ferent environments. Therefore, values of E(eˆ) and P(Lˆi, t) are highly dependenton the method of prediction being used. We will evaluate our method in Section 2.4based on a simple linear prediction. However, as long as a prediction method yieldsa prediction of the link’s lifetime and an estimate of the error, it can be integratedinto our approach.Having estimates of the link’s lifetimes for all the links in the path, the proba-bility of having an undisrupted path from node k toward the server S for the nextt time units (complement of the probability of no link being capable of relayingpackets from k to S) is:CkS(t) = 1− ∏l(i)∈Hk(S)(1−Pl(i)(t)), (2.5)where Hk(S) is the set of links between node k and its neighbors that have a loopfree path to server S. We use the cumulative distribution of Ck(t) (for t = 0 · · · tmaxwith tmax equal to the maximum duration of predictability) as a factor which showshow reliable the node k is to pass the packets toward the server S:reliability(k) = cdftmaxt0 (CkS) =tmax∑t=0CkS(t0+ t) . (2.6)We need to extract the reliability of a node for all the servers being discovered.To avoid extra calculations, we define a maximum hop threshold for acceptablepotentials received from neighbors. Intuitively it is obvious that information re-25garding faraway servers are not of any interest because of the extra relay overheadand delay.Finally, we define the distance between client c and server S as:D(c,S) = ∑k∈P(c,S)1cdftmaxt0 (CkS). (2.7)Notice that as the hop number increases, the distance is affected and the chance ofbeing chosen as the best path decreases. Based on this definition of distance, no-madic mobility patterns lead to higher potentials, and connection between vehicleswith opposite directions and/or sparse connectivity conditions cause less potentialdispersion.2.3.3 Potential Assignment for Path Construction and ServerSelectionUsing (2.3) as the distance measure for (2.1), every node can receive a potentialfrom servers based on the relative mobility and link condition of all the nodesin the path from that server to the node. As described in Algorithm 1, everynode advertises all valid server information received from neighbors to its adjacentnodes. After receiving these advertisements, the node sets the current potentialreceived from a server to the highest received value. These values are valid up to acertain time after the last advertisement. Whenever the node wants to send or relaya packet toward a server, it will choose the server with the highest potential. Thispolicy leads to selection of a server which has the best mobility correlation withthe transmitter.26Algorithm 1 Potential Assignment1: Input servers advertisements[ ]2: for each servers in f o in servers advertisements3: L← servers in f o.source4: predict link condition(L)5: servers[L]← servers in f o6: for each S in servers in f o7: rel f actor← reliability(S)8: D(S.id) = S.pot.originalS.pot.originalS.pot.received+1rel f actor9: pot[S.id]← max(pot[S.id], S.pot.originalD(S.id))10: next hop[S.id]← argmaxl∈neighbors l.servers[S.id].pot11: end for12: end for2.3.4 Location UpdateTo choose a new server for location updates, each node will select the accessibleserver with the highest potential. After choosing the best server, location updatesare sent toward it using the neighbor who has the largest potential from that par-ticular server. Using this approach instead of [48] we can make sure that locationupdate packets will not face misroute to other servers which are not moving in fa-vorable directions. Decision to hand over to another server is performed by a clientwhen the hop distance to the current server has exceeded a certain threshold. Sinceit is assumed that location update messages are not in a high priority class and theirpacket size is reasonably small, packet relay in short-range wireless would still bemore favorable compared to expensive long-range network. Anyhow, decision forwhen to hand off is still open to users and they can choose between prompt updatesand lower cost. We will discuss about this trade-off in the next section. Packet relayto a chosen server is also done very easily by comparing the potential of the serverreceived from current alive links and therefore source routing is not necessary.272.3.5 Location QueryTo find the location of another user, a requester would send a location query to thebest available server at the moment (the one with the highest available potential).The packet relay mechanism would be similar to that for location updates. Afterreceiving the query, the server looks up in its local database to see if it has up-to-date location entry. Otherwise it will send a query to its neighbors using long-rangewireless. Since we assume that long-range wireless links form a connected graphtopology, queries will have answer from one of the servers and this answer willreach the original server.2.4 Performance EvaluationsTo evaluate the performance of our proposed framework, we have modeled thesystem using the ns-2 network simulator [68]. We have added a new service dis-covery agent over the currently implemented network stack and added our logic asan application agent. Using application agent, we can use any routing algorithmfor packet routing. We have tried our protocol on several test scenarios. Thesescenarios are based on the realistic vehicular traffic generated by the SUMO ve-hicular traffic generator [69]. This microscopic vehicle traffic generator is able tocreate mobility patterns based on defined traffic flows, using the street maps thatare imported into SUMO to generate different test cases. The traces generated bySUMO yield a mobility log for vehicle movements based on road and traffic regu-lations. We have imported several maps with different key features for evaluations.Transmission range is set to 100m with 95% confidence interval. This means thata transmission between two cars 100 meters away would be successful with 95%probability. For short-range communication we use IEEE 802.11 with the mini-28Figure 2.3: Extracted map of Vancouver downtown from OpenStreetMap [2].mum data rate (1Mbps). We use log distance shadowing with parameters set tovalues provided in [70].The first imported map is a 10 Km long highway with 2 lanes in each direction.Two kinds of vehicles have been considered to commute on the road: private vehi-cles with short-range radios and public transit vehicles equipped with long-rangeand short-range radios. The two categories of vehicles have different characteris-tics in speed limit, acceleration and deceleration. The second scenario is a realisticurban area extracted from actual street maps. These maps are extracted from freemaps available in OpenStreetMap [2]. Fig. 2.3 depicts an extracted map of thedowntown area in Vancouver, BC. Obviously the most significant property of adowntown area is its high number of turning options and signalled intersections.29OpenStreetMap SUMO NS-2Mobility PredictionOutput Analysis1 23 45Figure 2.4: Simulation ProcedureAfter adding traffic lights to the map, we use SUMO to generate mobility tracesfor 10000 seconds. The procedure of map extraction and simulation is shown inFig. 2.4. After generating mobility traces, they are fed into ns-2 as the mobilityscenario and the simulation is performed by ns-2. Since we need prediction inour method and it is not performed in ns-2, we do the simulation twice; The firstrun is done to extract exact location of every vehicle during the simulation. Thenwe use this data in the next run as a precise prediction of future mobility patternsin the network. To make the prediction more realistic, we add noise to locationinformation. Since prediction precision is strongly dependent on prediction mech-anism, we use one of the simplest predictions: In every second, each node predictsx(t+1) = v+ x(t), where x(t) is the location of node in time t (0≤ t ≤ tmax). tmaxis the maximum time that prediction can be reasonably valid. We will set tmax to avalue so that:E(Pr(C(t))Pr( ˆC(t))+Pr(C(t))Pr( ˆC(t)))> threshold,1 < t < tmax .(2.8)This is the sum of expected probability for having a true guess, whether positive ornegative, on having a connection. This probability should be more than a certainthreshold. To find this value we run the simulation and calculate the predicted and30actual locations in the future. We consider a link as active if its RSSI is more thana threshold. Since measurement of RSSI is impacted by environmental clutters, itis impractical to deterministically define the link connectivity threshold. So we usethe propagation model in [71]:Pr(d) = Pt −PL(d) = Pt − (PL(d)+Xδ ) . (2.9)PL(d) is the log-distance path loss from the transmitter to receiver and Xδ is azero-mean Gaussian distributed random shadowing effect with standard deviationδ . Values of path loss exponent and δ are usually extracted from the empiricaldata. We have borrowed these values from the experiment done by Otto et al. in[70]. Finally, the probability of RSSI being more than γ (dBm) in distance d(m) is:Pr[Pr(d)> γ(dBm)] = Q(γ−Pr(d)σ) . (2.10)Fig. 2.5 shows the estimated error in the aforementioned prediction method. Re-sults show that in the highway scenario prediction is close to reality and the con-nection condition after 40 seconds is predicted correctly with a 70% probability.However, in the suburban scenarios and downtown areas, nondeterministic stopsand turning probabilities cause the prediction errors to grow. For downtown sce-nario, we find that predictions are 50% successful only for 20 seconds ahead. Insuburban areas with less stops and turns compared to downtown, it is up to 35seconds. We apply these errors in calculating the path reliability factor for eachscenario.To avoid excessive delay caused by late hand-offs we have to set a thresholdfor maximum allowable hop distance between nodes and servers. The trade-off is310 5 10 15 20 25 30 35 4000. Period(s)Average Prediction ErrorDowntownSuburbHighwayFigure 2.5: Linear prediction average error for three scenariosbetween the location update cost (which is related to the amount of the relayed dataand the type of media used for it) and the end-to-end delay.X=d(i,S)( fu.LU+ fq(LQ+LR)) d(i,S)< thrK ∗ (N−1)∗SYN+d(i,Snew)( fu.LU+ fq(LQ+LR)) otherwise(2.11)To calculate the proper threshold, we set our objective to minimize Cost ∗Delayfor the location update packets. Using (2.11) as the cost function and by know-ing d(i,S′), the distance between a node and its second best server with eligible32Table 2.1: Variables definition in (2.11)d(i,S) Hop distance between i and Server Sifu Frequency of location update messagesfq Frequency of location query messagesLU Size of location update messageLQ Size of location query messageLR Size of location reply messageK Usage cost/Kb for long-range networkN Number of location serversSYN Size of synchronization messagehop distance, every node can calculate the threshold as follows (for definition ofvariables in (2.11) see Table 2.1):thr =√d2(i,S′)+K ∗ (N−1)∗SYNfu.LU+ fq(LQ+LR).d(i,S′) . (2.12)Here we assumed that delay is only based on hop distance and did not consider thedelay caused by collisions.After finding the estimation errors, we run the algorithm based on these estima-tion properties. We try to establish connections between server nodes and regularnodes using the short-range wireless network.We compare client-server path length and traffic cost with three other methods:[48] (shortest path is the metric for route selection), [54] (affinity based on signal-to-noise ratio) and [57] (quorum based method with column based advertisementand row based query). Fig. 2.6 shows the average lifetime of connections betweenmobile nodes and location servers in the downtown mobility pattern. Hereafter weshall refer to our method as Lifetime-based method (LT). SP-1 represents the short-est path anycasting based on [48]. In SP-2 we use the same method as SP-1 except3310 25 50 100 150 200 250050100150200250300350Cars/Km2Average Client−Server Connection Lifetime(s)LTSP−1SP−2RABRQuorumFigure 2.6: Average Client-Server Connection Lifetime (Downtown)that whenever a server is selected for a node as a location server, it will remain cho-sen as long as the distance is less than the maximum hop distance. Results showthat using lifetime as the distance metric results in significant connection lifetimeimprovements specially for higher node densities.In the affinity based method, SNR is considered as the measuring factor for de-cision making. Therefore, for downtown areas with highly volatile SNR conditionsRABR can not perform much better than SP-2. Since in quorum based method cho-sen servers are changed rapidly after any change in topology, connection lifetimesare not comparable to other methods.3410 25 50 100 150 200 2500100200300400500600700800Car/Km2Average Client−Server Connection Lifetime(s)LTSP−1SP−2RABRQuorumFigure 2.7: Average Client-Server Connection Lifetime (Highway)Fig. 2.7 shows the same measures as Fig. 2.6 but for highway scenarios. Re-sults show a 57% overall improvement in connection lifetime compared to SP-2. Incomparison to shortest path method, our proposal significantly improves connec-tion lifetime, especially in lower vehicle density scenarios. Because of the steadymobility of vehicles, connection lifetime improves if paths are selected from vehi-cles moving along the same direction.RABR performs better in highway scenarios due to less perturbations in SNR.However, the quorum based method exhibits the same behavior as in the downtownscenario.350 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1102550100150200250Scaled Proportion of Sent Update PacketsCar Density (Cars/Km2/Minute)WiFiWiMaxLTLTLTLTLTLTLTSPSPSPSPSPSPSPRABRRABRRABRRABRRABRRABRRABRQuorumQuorumQuorumQuorumQuorumQuorumQuorumFigure 2.8: Normalized overhead of update packets being sent over WLANand WIMAX (K=100)100 101 102 103 104 10500. Factor (K)Normalized CostLTSPFigure 2.9: Signaling cost based on cost factor (K) in (2.11)360.01 0.1 0.3 0.4 0.5200300400500600700800900100011001200Bus/Car RatioClient−Server Message Passing Delay (ms) LTSPRABRQuorumFigure 2.10: Average Client-Server Message Passing Delay in Downtown(Only Query/Response messages are considered for Quorum BasedMethod)Fig. 2.8 compares the overhead caused by the location update packets. Thequorum based method uses several location servers, hence location updates be-come costly. Moreover, as mobility and interactions between nodes increase, theoverhead of quorum based method increases drastically. We have assumed that thequorum based method uses WLAN and WIMAX based on availability with no pref-erences. To compare the proportion of WLAN usage, we assumed that parameterK in (2.11) is equal to 100 (every transmission on WIMAX is 100 times more ex-pensive than WLAN). We can see that the usage of WIMAX in low traffic densities37is significantly low and as mobility patterns grow more dynamic, the differencebetween LT and other three methods become noticeable.Fig. 2.9 depicts the normalized total cost of location management for differentvalues of K. Since the cost of RABR is very close to SP and the cost of the quorumbased method is significantly higher than other methods, we have only comparedthe cost of SP vs. LT. As one can observe, for K ≥ 100 our method outperforms theshortest path method. K can be interpreted as a priority or preference parameterand could be tuned based on the trade-off between delay and cost efficiency. Ifproviders prefer faster and more precise location updates, they can decrease K. Incontrast, for better efficiencies (e.g. for less location sensitive applications) highervalues will lead to better spectrum conservation.Fig. 2.10 shows the average delay experienced by signaling packets (LocationUpdate, Location Query and Responses) for the downtown scenario. It is impor-tant to note that the quorum based method uses more than one location manage-ment servers and always every immediate neighbor in the same row of the node isacting as a location server. As a result, signaling delays for location updates andresponses are very low. However, when it comes to location query, signaling de-lay is relatively higher than updates. Our method is always performing better thanRABR in terms of delays but compared to SP, it suffers a 20% increase in delay.As the number of location servers (in this case described as buses) increases, theoverall signaling delay for all methods decreases. We can see that if half of thevehicles in our system could act as location servers, delay would have become aslow as SP and quorum based methods.382.4.1 Hybrid Network ScenarioNow we are going to consider a scenario in which infrastructure is available insome positions and road side units are placed in some spots to provide services ofinterest. We evaluate the highway scenario with this configuration. To see the effectof including the wired network infrastructure, we place Road-Side Unit (RSU)’swith specific distances between them. RSU’s are considered to provide locationservice to mobile nodes. The selection of location servers will be identical to fullyad-hoc mode. However location prediction for RSU’s is accurate and estimationerror is set to zero. We compare the effect of different RSU densities on our lifetimebased method and the shortest path method.In Fig. 2.11 a comparison of average connection lifetime is shown. We havecompared the average connection lifetime for three different vehicle densities.Clearly, when the density increases the connection lifetime increases as well.This means in denser traffic conditions the capability to relay the packets betweenservers and clients helps to increase scalability. Similar to ad-hoc-only network, theconnection lifetime of the shortest path method is less than that of the LT method.As the number of RSU’s increases, the connection lifetime starts to decrease. In theshortest path method, this change is more visible because server selection is basedon physical distance. This means when vehicles get close to RSU’s, they preferto change their connection to a closer RSU. In contrast, connection lifetime is notdramatically changed in the LT method.Fig. 2.12 compares our LT method with the shortest path method in terms ofnetwork usage. When the number of utilized RSU’s increases, utilization of thewired network as well as the usage of the WIMAX increases. The reason is that390 0.5 1 1.5 20100200300400500600700RSU/KmAverage Client−Server Connection Lifetime LT−10LT−50LT−100SP−10SP−50SP−100Figure 2.11: Average Client-Server Connection Lifetime with Hybrid Net-work in Highwayevery synchronization caused by selecting an RSU as location server leads to extrasynchronizations with the WIMAX servers. This comparison shows that even ifwe use RSU’s to collaborate with other mobile servers, still there is a chance thatselection of an RSU as server would result in higher overheads. However, this isthe price to pay in order to gain a better reliability. RSU’s are essential when thenetwork density is low and connectivity is weak.2.5 ConclusionLocation management is a critical function in VANET’s. In this paper we have as-sumed that some of the mobile nodes in a VANET are equipped with heterogeneous400 0.5 1  1.5 2  0.10.512Scaled Proportion of Network UsageRSU/KmWiFiWiMaxWiredLTSPLTLTLTSPSPSPFigure 2.12: Scaled Proportion of Network Usagewireless connectivity. These vehicles are able to act as location servers for other ve-hicles and cooperate using their long-range radios. We have proposed a new serverselection and packet relay mechanism that minimizes the rate of server hand-offsby relaying location update packets toward the server that has the lowest possibil-ity of disconnection. This is done by proposing a new definition of distance. Theproposed method has been evaluated by extensive computer simulations. The re-sults show significant improvements in client-server connection lifetimes. Higherconnection lifetime lowers the costs of server hand-offs, which require the use oflong-range communications to update the record for the client at all the servers.We have provided a tuning factor which can be used for decision making based41on tolerable delay and cost. The comparison has been made against three methods:associativity based routing, shortest path selection and quorum based location man-agement. Results show that in scenarios with high mobility our method achievesthe lowest costs and also acceptable delays compared to the other three methods.We have also compared our method to the shortest path method in a hybridnetwork scenario. The results show similar behavior in connection lifetime (i.elonger connection lifetime obtained by our method). However, in hybrid scenarios,the cost factor of using wired network is lower than the cost of short range wireless.Therefore, users may prefer to choose shorter link lifetime to obtain faster locationupdates.42Chapter 3Reinforcement Learning-basedAdaptive Broadcasting for VANETEffective context-aware broadcasting of information to the AOI is a challengingproblem in VANET. It is usually assumed that the information about these AOIis known a priori, either by a centralized source of information or by the en-tire set of vehicles. We propose a self-adaptive broadcasting scheme based ondistributed reinforcement learning in which vehicles collaboratively tune the rateof their broadcasts based on the network dynamics without any initial knowledgeabout the geographical distribution of AOI. The proposed approach enables a morepractical implementation of distributed context-aware broadcasting which requiresno global information and only partial synchronization.The convergence and broadcasting performance of the proposed learning sys-tem is evaluated using simulations for several setups. These results show a signifi-43cant improvement in terms of number of useful broadcasts and delay, over existingapproaches, such as gossip-based broadcasting.3.1 IntroductionOne of the main challenges in VANET is to find an efficient and reliable approach todisseminate information to interested parties. Extensive literature exists on broad-casting and data propagation techniques for MANET, and in particular, VANET’s[8, 72–79].There are two major approaches to disseminate information among vehicles.Pull-based methods like [75] are designed to query information from the sourceand retrieve it to the destination. However, in VANETs with intermittent link losses,it is very challenging to handle two-way connections in a timely manner and inmany cases data could become obsolete. Push-based methods like [73] are de-signed to treat information as broadcast messages. DV-Cast [79] proposes a pro-tocol to handle both dense and sparse traffic regimes in highway environments.The main contribution is to handle seamless switching between broadcast sup-pression in dense traffic and store-carry-forward in sparse areas. By exploitinglimited mobility patterns along highways, this method achieves better performancein broadcast success rate and scalability. However, this method still needs moresophisticated control messages for handling urban traffic conditions.The main focus in methods like [73] and [79] is on efficiency and reliabil-ity of broadcasts by exploiting the mobility pattern of adjacent vehicles. Anotherconcern in data dissemination is to shape the data diffusion towards favorable lo-cations. This issue is addressed in [72] as Geographical-Temporal Multicasting,which is concerned with delivering a message from a data source to all devices in a44distant contoured area. This multicasting method is applicable only if destinationsare known a priori; however, multicast clients in VANETs may be configured dy-namically rather than registered ahead of time. Moreover, the AOI might reside inmore than one contoured area. In such cases, the complexity of finding the optimalbroadcasting strategy is cumbersome.In [77], broadcast strategies based on the Gossip protocol are presented. AGossip(p,k) is a strategy in which all nodes that are more than k hops away fromthe source of data will re-broadcast the data with probability p. Although Gossipand similar epidemic-based broadcast strategies are simple to implement, the maindisadvantage is the excessive number of useless broadcasts, especially in areas thatare outside the AOI.In [80], a scenario with multiple disjoint AOI is suggested. The decision tobroadcast toward destinations is based on a custom defined propagation functionthat is aimed to classify locations according to how useful it is to have a receiveror a transmitter residing in each location. However there is no discussion aboutthe design of the propagation function itself. SPACE [76] is a spatial-aware datadissemination approach designed for traffic dissemination systems (e.g., Trafficand Travel Information (TTI) applications). Their main contribution is to confinebroadcast of traffic flow information into predefined zones of interest.3.1.1 ContributionsTo the best of our knowledge, existing research has focused on finding optimal orheuristic methods to relay broadcasts towards known AOI. We consider a morerealistic situation, i.e. when the AOI is unknown to the traffic sources or their geo-graphical locations are dynamically changing. For instance, in the TTI application45 Cam1A BCDE(a) TTI ApplicationFood CourtSubwayBus StopABCDE F(b) Advertisement ApplicationFigure 3.1: Two applications with different domains of interest.in [76], if the travel behaviours of vehicular nodes (including the average road traf-fic) are not given, or if this information is not updated to meet the latest changes,such as new constructions or roadblocks, then decisions to classify regions of in-terest for TTI data become considerably inefficient. Our goal is hence to provide adistributed self-adaptive learning mechanism for vehicles to autonomously recog-nize AOI by means of dynamic feedback from other vehicles, and also to classifylocations in which broadcasting is more helpful. This leads to an efficient deliveryof information to the AOI by avoiding useless broadcasts and dynamically learningfrom the VANET environment.The rest of this chapter is organized as follows. In Section 3.2 the system modelis elaborated, and in Section 3.3, our method called Reinforcement Learning-basedAdaptive Broadcast (RLAB) is proposed. In Section 3.4, simulation results arepresented to evaluate the performance of RLAB in comparison with Gossip-basedbroadcast. The conclusions are presented in Section 3.5.463.2 System ModelWe consider an adaptive broadcast framework for data dissemination in differentVANET applications without prior knowledge about AOI. In Figure 3.1, two dif-ferent categories of such applications are illustrated. In 3.1a a traffic monitoringsensor equipped with standalone transmitter is located near junction C. Regard-less of traffic condition, the packets transmitted from this sensor can be relayed bynodes travelling in CD or it can be back-propagated in CB from there to A. If wedo not have the traffic flow information about this map (which is usually the case),existing methods are unable to choose the effective policy for broadcasting in roadsegments CD, CB and BA. Another example is shown in 3.1b. Densely populatedareas are potentially the best place to advertise. However, if the distributions ofinterested users under different traffic profiles (e.g. rush hour vs. regular hoursor weekdays vs. weekends) are unknown, then the geographical-temporal broad-casting used in the existing literature would have no advantage against context-oblivious broadcasting methods.Based on these two examples we propose RLAB, in which the vehicles learn theAOI as well as the locations where broadcasts are useful. Specifically, RLAB tunesthe rate of broadcasts based on distributed reinforcement learning so that vehiclesare more likely to broadcast in the locations which boost the delivery of data to-wards the AOI. In distributed reinforcement learning [81], every collaborator, i.e. avehicle with transmission capability, learns their actions individually but they col-laborate with each other to share their feedbacks and shape a distributed learningsystem.47In order to reduce the complexity, we divide the roads and intersections intofixed size segments. The size of each segment is less than the transmission range,and therefore, we can assume that all the vehicles inside a road segment can com-municate with each other. After performing the segmentation, we calculate thecommunication overlap between adjacent road segments. The coverage is calcu-lated as the expectation of connection probability based on the log-normal shad-owing model [71] and path loss exponents extracted from different vehicular envi-ronments in [70]. These values will be used later in reward assignments.Inspired by distributed reinforcement learning approach in [81], we considerevery road segment as a unified packet distribution point. Vehicle(s) residing in aroad segment act as agent(s). Presuming that road segments are not changing dur-ing a reasonably long time (unless there is a construction or traffic detour), we canassume that every distributor has fixed neighbours and links to those neighbourshave unchanging characteristics. Even if this condition does not hold, our methodwill learn the environment but the learning would take more time to converge.Consider N vehicles commuting in the area within a set of road segments rep-resented as S . Since interest of users could be different based on the time of day(e.g., rush hour vs. non-rush hour) or day of week (e.g., week day vs. weekend),we differentiate among sets of space-time combinations in our state space so thateach of them can be evaluated separately. Si(t) is defined as the road segment inwhich vehicle i is residing at time t (Si(t) ∈S ,∀i ∈ N). We consider a Markov de-cision process (MDP) for each road segment k ∈S as a tuple Mk = (Ak,Sk,Tk,ρk)that represents the behavior of every vehicle residing in this road segment. In roadsegment k, Ak is the set of possible actions the vehicle may perform, Sk is the set48of states, Tk is the set of transition probabilities of the MDP, and ρk is the set ofrewards corresponding to the set of actions Ak in this MDP.3.2.1 State SpaceFor every road segment k ∈S we define a finite state Markov chain (FSMC) withstates (Tk,rk), ∀ Tk ∈ T and ∀ rk ∈ R. T is the set of temporal traffic con-ditions (rush hour v.s. non-rush hour) and R is the set of broadcast rates, with ahigh rate corresponding to a situation where it is more desirable to broadcast thereceived data message. For simplicity, we have defined two states for the road seg-ment, namely Good and Bad, which indicate whether the nodes are encouraged tobroadcast in this segment or not.3.2.2 ActionsLogically all vehicles which are inside the same road segment at the same time,are experiencing the same state. However, since our mechanism operates in a com-pletely distributed manner, each vehicle has to trace its own state and save thetransition probabilities and current state locally. Implementation details will bediscussed later. We design our action based on the state space of each road seg-ment.Actions are selected from a set with two members: {broadcast,carry}. How-ever, there is a third action, namely idle, but in segments without a conveyingvehicle to perform broadcasting there is no learning involved (this could be alsoexplained as a standby state for learning agents).493.2.3 State TransitionsThe state of a road segment changes based on the feedback received from otherroad segments. If a packet reaches an interested user, reward is given to all of theroad segments in which the broadcast was performed to enable this packet delivery.Consequently, the state for the rewarded road segments are changed to Good. Onthe other hand, if no reward is given to a road segment during a predefined period, itcauses a transition to state Bad. These states transitions are performed by all nodeslocally. It is necessary to synchronize the latest feedbacks for a road segmentsbetween those of nodes that are passing the road segment, because the decision onthe state is based on how previous broadcasts in this road segment has affected theenvironment.3.3 RLAB: Distributed Q-Learning with Local StatesHere we explain the learning mechanism proposed for RLAB. Since the globalstate of the system is not recognizable by vehicles, modeling of the problem asa distributed reinforcement learning is not possible. To solve this problem, weconsider local states for each distributor. The idea of using local states has beenexplained in [81]. Since local states are only perceivable by local agent(s), agentsshould negotiate their values, not their states. The value of every distributor isbased on its current state and former rewards obtained by its actions.In distributed Q-Learning with local states, every node has its own state set andthere is no global knowledge about current state of the system. However, an actionchosen by a node will affect the value of other nodes in the system and therefore50should be considered in calculating rewards [81]:Qi(xi,ai) = (1−α)Qi(xi,ai)+ (3.1)α(Ri(xi,ai)+ γ∑jf (i, j)Vj(x′j)),Vi(xi) = maxa∈AiQi(xi,a).Table 3.1: Variables definition in (3.1)α,γ Learning and discount factorsQi Local value of node ixi Current local state of node iai Local action chosen by iRi Instant local reward to node ij Other nodes in systemf (i, j) Importance factor of j’s reward in i’s valueVj j’s current valueA Set of actions for iWe define two feedbacks for every action. The first feedback is an immediatereward given to the local broadcaster after deciding whether to broadcast or not(Ri). This feedback will represent the local impact of the decision on the othernodes in the vicinity. Remember the goal is to disseminate the information as muchas possible using as few broadcasts as possible. The second feedback is issued byvehicles who find the received message useful. We replace the values of adjacentdistributors orVj in Equation 3.1 with a dedicated reward if the broadcast action ofthis distributor has led to delivery of the packet to an interested user in segment j.f (i, j) is calculated as 1− TrecvTexpire or in other words, if the relay path is mostly basedon broadcasting relay, the rewards would be higher for distributors compared towhen the path is mostly comprised of data carrying periods.513.3.1 Calculating Immediate RewardsFor immediate rewards we consider local parameters effective in decisions. Thefirst factor is based on how vehicles are moving around the transmitter. If vehiclesare moving with variant speeds it is more likely that information scatters aroundcompared to when vehicle are moving with a nomadic pattern. Therefore, thereward should be more for a broadcast in an area with variant speeds. Secondly,we consider a broadcast more effective if the area is populated and it is highlydesirable to have more listeners when a packet is broadcasted. Third, we considerduplicate broadcasts less valuable. If the vehicles in vicinity of a broadcaster havenot received the message before, the reward for broadcasting is higher. We considerthe message lifetime as an effective factor in rewarding. However, to encourage thenodes to propagate messages over wider areas, a reward is decreased only when themessage is expired.Based on the decision factors described above, we formulate the reward func-tion. If a node decides not to broadcast the packet, the immediate reward will bezero. However, for node s with a set of neighbours N(s), the reward for broadcast-ing is:Rs(b, t+1) =(⌈T (t+1)Texpire⌉√∑i∈N(s) (vs− vi)2|N(s)| max(dV )+κ(t+1)) Kc|N(s)| I−1, (3.2)κ(t+1) = 0 if Q(t) = Broadcastκ(t)+ ε otherwise. (3.3)52B3B5A4A1A2 A3A5B1B2B4Node with interest in dataBroadcastingCarryingA1 Rewarded SegmentA2 Unrewarded SegmentFigure 3.2: Delayed rewarding after message is found useful: Black car insegment B5 uses message and reward is given to segments in whichpacket was broadcast.Texpire and T (t) denote the message lifetime and remaining time of validity, respec-tively. I represents the importance factor for the type of information that is beingbroadcast, vs and vi respectively represent the moving speeds of the broadcasterand its neighbours, and dV is the maximum relative speed while connectivity canbe preserved. Kc is the number of neighbours who have not already received thebroadcast information.To avoid early back-offs in action selection, κ is added to Equation 3.2, whichincreases every time that a broadcast is neglected and the reward for broadcastinggrows consequently. The value of κ can grow to more than zero if message has notbeen broadcast for a while. The growth speed depends on the value of ε .3.3.2 Calculating Delayed RewardsIn Figure 3.2 the vehicle in up-left corner carries the message and broadcasts it inthe road segment A1. Consequently blue car receives the message and carries itto the road segment A4. Since A4 and B3 are in range, the red car overhears the53broadcast and carries the message to B5 and broadcasts it again. Eventually theblack car which is interested in receiving messages of this specific type receivesthe packet and updates feedback rewards for the road segments A1,A4,B3 and B5.These updates are local but they will be dispersed in the network gradually until allnodes are updated.Since every car has a local instance of rewards, synchronization becomes a veryimportant and challenging part of our system. Although global synchronization isnot needed for convergence, if nodes that are using these rewards in their actionselection policy can access the latest updates, convergence becomes faster and ac-tions are more accurate. An intuitive approach for synchronization is to spreadnew updates toward the rewarded segments as soon as possible and the latest ver-sions should be kept alive in the respective segments as long as possible. Using theLINGER method proposed by Borsetti et.al. in [82], update message can be keptalive in the area as long as there exists an updated vehicle in the region.We do notfocus on data synchronization problem here to limit the scope of this chapter.3.4 Performance EvaluationIn this section, we show our simulation results and investigate the convergence andperformance of RLAB, in terms of the number of useful broadcasts as well as the de-lay. We compare our results with a simple Gossip broadcasting method from [77].We should note that the scope of methods like [75] and [82] differs from ours sincethey are designed for scenarios with known AOI. We have implemented a simula-tor in Matlab which handles the broadcasting and learning sequence. We extractthe mobility traces generated by the SUMO traffic generator [69]. For the simu-lations, we have used a 4 km×1 km square field with Manhattan (grid) topology540 0.5 1 1.5 2 2.5 3x 10400. Standard DeviationRLABFigure 3.3: Normalized Deviation in value of state Good in a useful roadsegment vs. simulation time (seconds)and 100 commuting cars. Roads are divided into segments with length of 100 m,and intersections are considered as segments with the radius of 100 m. Variable αin Equation 3.1 is decreased from 0.3 to 0.01 during the simulation time, and γ isset to 0.9. Also, ε varies between 0.05 and 0.15 based on the convergence rate ofthe state values. We considered an AOI at the north-west of the map, and a packetgenerator at the south-east transmitting one packet per second. To avoid excessiveoverhead, each node broadcasts its buffered packets at most once per second.3.4.1 ConvergenceAfter running the simulation, the rewarded road segments remain in the state Good,and the rest of the road segments are considered as Bad segments for broadcast. InFigure 3.3, the standard deviation in value (V ) of state Good is shown for a Goodroad segment. As can be seen, the value of this road segment is eventually con-550 0.5 1 1.5 2 2.5 3x 10401020304050607080TimeNumber of  Broadcasts Gossip(0.65,1)RLABFigure 3.4: Number of Broadcasts sent vs. simulation time (seconds)0 0.5 1 1.5 2 2.5 3x 10400. ratio of Usefuls/Broadcasts RLABGossip(0.65,1)Figure 3.5: Normalized Cumulative Ratio of Useful Broadcasts to TotalNumber of Broadcasts vs. simulation time (seconds)560 0.5 1 1.5 2 2.5 3x 104100200300400500600700TimeDelay (second)Gossip(0.65,1)RLABFigure 3.6: Packet delivery delay for AOI vs. simulation time (seconds)verged, and hence, the actions for this road segment is fixed. In other words, RLABis able to converge to a broadcast strategy after some time. We should note thatthe convergence time depends on the performance of the reward synchronization.Particularly, if a car does not come back to the road segments it has previouslypassed, the other vehicles cannot receive the reward and the convergence wouldtake longer.3.4.2 Broadcast ComparisonTo show the effect of RLAB on the number of broadcasts, we compare our methodwith Gossip(0.65,1) borrowed from [77]. Figure 3.4 shows the total number ofbroadcasts in each time period. We also fit the data with curves of degree 1 and4 for RLAB and Gossip(0.65,1), respectively. As can be seen, although the sizeof our network is relatively small (i.e., only 100 active cars), there is a significantdifference between the total number of broadcasts in the two methods. Specifically,57the average number of broadcasts remains fixed in Gossip(0.65,1). On the otherhand, as RLAB learns the best road segments for broadcasting, the total number ofbroadcasts decreases over time. This is due to the fact that RLAB avoids uselessbroadcasts in Bad road segments.In Figure 3.5, we compare the ratio of useful packets, i.e. delivered insidethe AOI, to the total number of broadcast packets. As can be seen, RLAB is ableto deliver the same number of useful packets with almost 5 times less number ofbroadcasts compared to Gossip(0.65,1).3.4.3 DelayFigure 3.6 depicts the average delay experienced by packets before reaching theAOI in Gossip(0.65,1) and RLAB and their corresponding fitted curves. As can beobserved, the delay is slightly increased over time for Gossip(0.65,1) because ofthe imposed one broadcast per second restriction. On the other hand, the delayof RLAB is less than that in Gossip method. The reason is that in Gossip(0.65,1),the nodes broadcast with the probability equal to 0.65 everywhere, but in RLAB,the probability of broadcast in Good road segments, which deliver data to the AOIfaster, is higher. We can also observe that the RLAB delay is a decreasing functionof time since the learning of Good road segments is improved over time.3.5 ConclusionsWe have proposed a distributed reinforcement learning approach to tune the mes-sage broadcasting rates in VANET. We assume that AOI’s are unknown but corre-lated for vehicles within the same areas. Our method enables the broadcasting rateto be tuned in favor of packet relays towards the AOI. Using simulations we have58shown that our approach converges quickly, and achieves a better delivery ratio andless delay compared to the existing methods. While our proposed method can sig-nificantly increase broadcast efficiency, it is mostly applicable for location basedservices. The convergence time is related to inter-vehicle synchronization as wellas the persistence of AOI regions. Therefore, further studies may be useful to mea-sure the convergence time in different synchronization mechanisms and dynamicmap configurations.59Chapter 4Data Dissemination for DelayTolerant Vehicular Networks:Using Historical MobilityPatternsWe propose a message dissemination algorithm for location-aware services in ve-hicular networks. The objective is to reduce information delivery time in intermit-tently connected urban vehicular networks by using historical mobility informa-tion of vehicles. Roads are divided based on observed traffic density into denseand sparse paths and vehicles share their current knowledge about fastest possiblemessage delivery time to contouring dense roads.We use a Dijkstra based shortest path calculation with link weights set to packetdissemination time based on observed traffic and available relays in the vicinity. To60simplify the shortest path calculation we calculate delay under two strategies. Thefirst strategy is to relay information to closest dense road and use relaying. Thesecond strategy is to try carry and forward towards the destination. Historical mo-bility information is used to find the best carrier candidate. On dense roads, infor-mation will be broadcast towards the destination without the carrying phase, whileon sparse roads knowledge about the historical mobility patterns improves the nextrelay selection efficiency. Using simulations we show the superiority of our pro-posed method in delay and reliability of packet delivery compared to conventionaldata dissemination methods such as VADD in city traffic scenarios.4.1 IntroductionVANET is composed of collections of wireless radios embedded in vehicles andaiming to provide a medium for cars and their users to share and deliver criticaland non-critical information to vehicles and stationary nodes. Due to the natureof vehicular environments it is very likely that packet forwarding over some roadsis disconnected at different times of the day causing excessive delivery delays. Indisconnected network topologies the vehicles intending to forward messages alongsparsely populated roads have to carry the messages for some time until a new nodeemerges.Although this type of network is considered as a sub-category of ad-hoc Net-works, there are some limitations and potentials which make these networks inneed of different routing and message dissemination mechanisms. VANETs are dif-ferent from MANETs in many aspects. One of these aspects that can be used toimprove message dissemination (routing) is the distinctive mobility patterns of ve-hicles. More specifically, being limited to travel in road topology and the repetition61of the paths selected by vehicular users provides abundant information which canbe used by message dissemination protocols.There has been extensive research in the area of vehicular traffic engineering,showing that the traffic patterns of many vehicles are repeatable and many com-muters indeed repeat the same trajectory as in previous similar temporal periods[83–85](e.g. the same hours of the day or the same days of the week).In this work, we exploit these repetitive mobility patterns in the design of ourproposed data dissemination mechanism to find the most desirable paths to the tar-get location. Having observed and saved the driver’s mobility patterns over a longenough time span, the radio deployed in the vehicle can then share this informationwith other neighboring vehicles introducing itself as a packet carrying alternative.Clearly, in order for our mechanism to be scalable, every vehicle needs to aggregatethe information received from neighboring vehicles. Although during a trip a vehi-cle may receive numerous updates from neighbors, the aggregation of informationleads to constant size of updates which is a key factor for bandwidth-efficiency andscalability.There has been a large number of studies addressing data aggregation for trafficinformation systems (TIS) in vehicular/mobile environments.In [86] an encoding method based on two-dimensional cubic spline interpo-lation is proposed to compress the trajectory information for better transmissionefficiency. Although this method provides a promising compression rate, it con-siders trajectory information under a two dimensional coordination system whichdoes not provide information about road segments. In our proposed method, wedefine the road segments and use common road segment indexes between nodes toreduce overhead.62Although data encoding and compression can be helpful to conserve band-width, if every vehicle includes the complete paths of itself and its neighbors in theaggregates, the aggregates will become extremely large units of data consuminghuge network resource. Hence, the next question to answer is what parts of theirend-to-end paths should the vehicles share with each other to be included in theaggregates. In other words, every vehicle should only share its trajectory over alimited area contoured around its present location with neighboring vehicles.In Vehicle Assisted Data Delivery (VADD) [75] the candidate road segmentsfor fastest path are chosen from an overlay ellipse around the current carrier’s loca-tion and destination. Upon every contact, the current carrier considers the adjacentvehicle residing in the road segment belonging to best path is chosen as next car-rier. To find the path they have created a linear equation system and used Gaussianelimination algorithm to solve it. However, a fixed area between destination andsource may not include the most efficient path from source to destination, speciallyin sparsely populated roads. We propose a new approach in which every vehicleonly shares the times required to carry a given message from current location to thefirst upcoming road segments with high traffic densities in four opposite directions.Note that every vehicles is aware of all of the high vehicle density road segmentsin its proximity through its digital map and is not necessarily its own experience.As a result the aggregate includes the time needed to reach any of the immediatehigh density road segments in the neighborhood. In a grid layout road-map, theaggregate is expected to include the times needed to reach four high density roadsegments, thereby reducing the size of aggregates. Note that the vehicle’s currenttrajectory is not important in this phase (i.e. information aggregation) because thevehicle is not going to be a relay. During the packet relay phase, after the packet63reaches the dense traffic, packet relay mechanism will be totally different and ituses geographic broadcasting to relay the packet towards the destination.In [87] Jeong et al. have proposed a method which calculates the forwardingprobability on every intersection based on the possibility to contact other vehiclesin intersections. This method considers a similar scenario as ours. They calculatethe contact probability over every intersection and also a link delay model. How-ever this contact probabilities are weighted in relation to the geographical distanceof every path. They also have not considered the coexistence of a roads with heavytraffic beside the light traffic roads.In [88] a method to deliver the packet to a mobile target is proposed. Thismethod is for relaying the traffic from an access point to a specific moving vehicle.In this method it is assumed that there is a centralized entity (e.g. organisationalcontrol center) which is able to provide the trajectory of the vehicles to accesspoints without privacy compromise. In this architecture the delay imposed to thepacket is tightly following the vehicle movement delay which is relatively high.We believe that a pure vehicular based data forwarding is not reasonable where(due to assumptions) a centralized supervision (and therefore connectivity such ascellular link) is needed.In [89] we have proposed RLAB, a new method to iteratively find the best spotsfor broadcasts when the exact locations of interested nodes are unknown. In thismethod we have shown that it is possible to use repetition of movement patternsto find the proper relaying points. However since this method is distributed everynode experiences a local observation of the global knowledge and hence it needs amethod to share the learning parameters with other nodes. The knowledge sharingmechanism used in this work can be applied to the work presented in [89].64There has been extensive studies on message propagation in vehicular networks[72, 73, 75, 79]. However these methods are mainly designed to handle homoge-neous vehicle traffic patterns and densities meaning that the change in traffic regimeis not considered to change the message dissemination protocol. The probabilisticmodeling of the traffic patterns and vehicle distribution has been studied in [90].In [91] a two dimensional analytic message propagation model has been proposed.However in their models they have not considered carry-and-forward mechanism,which is necessary when connectivity is intermittent.The main focus in methods like [73] and [79] is on the efficacy and reliability ofbroadcasts by exploiting the mobility pattern of adjacent vehicles. In MDDV [72]the effort is to shape the data diffusion toward favorable locations which is doneby Geographical-Temporal Multicasting, or simply to deliver a message from adata source to all devices in a distant contoured area. However, MDDV does notconsider the fact that traffic condition is not similar over large areas such as cities.According to statistical information extracted in [92] about 35% of the destinationschosen by a driver is in residential category which means it is very likely that carsare on their path toward residential areas. The areas with lower traffic density,such as residential areas, are susceptible to loss of the information when relayingprotocol is solely relying on current neighbors location and movement direction. Ifthe next hop is chosen based on candidate’s current direction of movement, it canlead to relay of packet to vehicles that are either choosing to change their directionor to stop at their destination (which mostly happens in residential areas).We introduce an approach to aggregate and distribute the knowledge aboutthe best paths for relaying the content toward interested areas. Unlike previousmethods, which rely on contemporary network topology and immediate neighbors65knowledge, we consider previously experienced contacts and their experienced de-lay of passing a packet along the road segments. This information is sensed usinga distributed algorithm which includes a knowledge aggregation phase. Every in-dividual node calculates its own estimated travel time along its path. Moreover,by broadcasting estimated travel times, receivers aggregate information along withtheir own experienced travel time. This information is being re-broadcast as soonas a new neighbor is found. We have proposed a weighted sum to consider thereliability of new messages when the aggregation is done. When a node needs torelay an information packet toward the destination, it requests a candidate for relayfrom its immediate neighbors. If a neighbor founds itself a better candidate com-pared to the requester, it will respond and hence, the requester relays the packet tothe candidate. Every relay recalculates the best strategy based on its own projectedpath and therefore the predicted packet delivery delay.The advantage of this method is that nodes can follow two different relayingregimes based on traffic density. If a node resides in sparse traffic condition, itchooses to use the previous history to select an optimal relay, even with the costof extra overhead. In contrast, while residing in high traffic condition, the nodechooses a fast relaying based on geographical broadcasting toward the destination.We are focusing on how we can use multi-hop information of useful contactsto relay the packet toward the desired destination location. This is done by amethod for sharing past experiences of nodes with each other. Sharing the infor-mation about experienced contacts among neighbors introduces extra communica-tion overhead. However, this overhead is applied only in sparse traffic condition.Our method follows a geographical broadcasting approach when the relay residesin streets with high traffic density. Therefore no extra overhead is enforced in66conditions with highly utilized spectrum. We have studied the effect of protocoloverhead for different traffic regimes in city scenarios.The rest of this chapter is organised as follows. In Section II we explain theproperties of message dissemination services in VANETs. in Section III we ex-plain the proposed algorithm. In Section IV we present the simulation results andevaluations. Section V concludes the chapter.4.2 Message Dissemination in VANETIn VANET the temporal and geographical properties of message are important.While traffic information related to an area within past few minutes is beneficial tocollocated users, it becomes wasteful dissemination after content expiration timeas well as within irrelevant parts of the map. Although the nature of this networkis still considered to be delay tolerant, it is the goal of message dissemination pro-tocols to provide realistically reliable (best effort) service and to consider findingpaths with lower delays. The combination of these two goals leads to a hard opti-mization problem even in centralized network. Therefore we propose a decentral-ized heuristic approach with the goal set to minimize the delivery delay. We aim toincrease the reliability by disseminating multiple copies of the message toward thearea of interest. However by choosing the best carriers out of adjacent nodes, we tryor contain the number of copies to avoid broadcast flooding. The goal of our algo-rithm is to provide service for small informative messages (e.g. road safety alerts,traffic information and context sensitive commercial messages) which are destinedto AOI. The destinations of these messages are specific areas, not specific nodesand thus the messages should be considered as proactively disseminated contents.67XXCABDEXSender1st encounter2nd encounter3rd encounter Delivery by D4th encounterDelivery by ECarried by AArea of InterestDensely Populated Road SegmentRelayRelayFigure 4.1: Sample scenario: Two different frequent paths can be used basedon frequent trajectory patterns.In terms of usage, we assume that most of the road users follow a repetitivemobility pattern (in [85] authors have claimed that about 70% of collected tracesfrom different drivers include repeated trips). In other words, it is very likely thata user follows a mobility pattern based on his/her schedules and activities relatedto the time. In this case we assume that it is statistically viable to exploit tracesof repetitive occasions of meetings between cars. Based on this information wecalculate the usefulness factor of a neighbour and utilize this factor as a measureto decide whether it should be chosen as a carrier of the current message. As anexample, Figure 4.1 depicts a scenario in which the RSU in the left originates amessage, while the destination of the message is within the bottom right section(We should emphasize that the transmitters and receivers can be stationary or mo-bile and there can be more than one receivers per generated content). Each of thecars stores its own trajectory history and based on this history predicts the futurepath. Upon every encounter between two vehicles, they exchange their previousknowledge regarding the time it takes for a packet to be delivered to four populatedroads within four directions. Obviously, all delay measurements are not similarand as a result the deviation of experienced delays could be very large. Therefore68information exchange should also consider aggregation of similar information cap-tured previously from other contacts. Since recording multi-hop encounters leadsto exponentially growing demand in storage, our method aims to aggregate the en-counters and introduce a measure of message delivery delay toward closest popularpaths. As a result, every message carrier can take advantage of the more precisemeasurements from previous encounters of current neighbors.The depicted scenario in Figure 4.1 shows three streets. The lower street hashigh density traffic. When A receives the message from the top left corner of themap, it calculates the expected delay for message to reach the bottom right cornerof the map. Based on predicted trajectory and previous encounters with vehicles inother paths, A decides to relay the message to B instead of carry-and-forward it toE. After B takes the message, it relays it to C because the delay for C to carry-and-forward the message en route is less than B (due to delay of passing constructionarea). As we emphasized before, each vehicle calculates the delivery delay to eithercarry-and-forward the message toward destination or to carry the message to a roadwith dense traffic so it can be relayed toward the destination.In the next section, we will explain the algorithm and the message passingprocedure for our proposed method.4.3 Proposed Algorithm4.3.1 AssumptionsAs we mentioned before, we assume that every node can carry a copy of dissemi-nated information which means there could be more than one copies of a messagebeing propagated in the network. In our setup, we have defined each road segment69as the part of the street which is between two intersections and/or the end/startof the street. Therefore we assume that in general, being in a road segment canbe identified as being in one place. It may bring the question that in long roadssuch as highways, the cars may not meet each other, however this algorithm isonly triggered when two cars are in communication range and when a car is trav-elling along a road segment, either it covers the whole road segment or it covers itpartially before leaving the network.We also assume that each collaborating vehicular node in the network mainlytakes two roles: a carrier and/or a broadcaster. Being a carrier means that thenode listens to the other nodes and as soon as it receives a propagation request,it evaluates its own route plan and based on its own measure of effectiveness, itdecides whether to accept the message or not. Being a broadcaster means thatwhen the vehicular node is carrying a message, it should try to find other carriersalong its travel path, which are potentially able to relay the message toward thedestination zone, faster and more efficiently. By this approach we aim to decreasethe message delivery delay without reducing reliability.4.3.2 Road Segment CategorizationFor simplicity, we consider a road segment to have exclusive traffic density fea-tures. Therefore during similar temporal context, every vehicle in one road segmentwould sense the same traffic density. However during different times of day/week(e.g. rush hours vs. off-peak traffic) these features may vary.It is accepted in the literature that inter-vehicle distances follow an exponentialdistribution, with a mean distance equal to 1/ρs where ρs is the vehicle densityin road segment s. Since we consider the sensed density in a road segment to be70uniform, we can use this assumption and follow the literature. Therefore we defineds, packet forwarding delay in road segment s equal to:ds = (1− e−Rρs) lsRc+ e−Rρs lsvs. (4.1)The density of cars, ρs, can either be calculated in a car using the number ofencountered neighbors in s or by using previously captured statistical data (e.g. us-ing induction loops on intersections or traffic cameras). Based on this assumption,we categorize the roads into two categories namely dense and sparse. The trafficin road segment s is considered as dense if the expected delay of relaying a packetis less than of carrying it (by factor α):(1− e−Rρs) lsRc< αe−Rρslsvs0 < α < 1 (4.2)where R is the average transmission range and ls is the length of the road segments. c is the constant to approximate the delay for relaying a packet between twoneighbors. vs is the average travel speed of vehicles in s. We assume that thecategorization of road segments is identical for all of the vehicles. This is practicalif we consider availability of digital maps with temporal statistical information ofthe roads and intersections. We will use this categorization of roads later to selecta relay path with lowest delay.By using realistic simulations of vehicular traffic, it becomes clear that thetraffic is not uniformly distributed in all the streets. As it is also intuitive, thesimulations show that dense road segments normally create one connected mesh ora set of smaller connected meshes which are partitioned by sparse road segments.Using traces provided in [3] and elaborated in [93], we have extracted dense road71segments which are shown in Figure 4.2. As it is clear, the dense roads are dividingthe map into smaller tiles and are mostly connected. Therefore every source anddestination pair can be either surrounded by the same dense roads or separated intodifferent tiles. In both cases carrier/relay nodes may end up choosing the best pathswhich include parts of contouring dense road segments. In the following sectionswe show how the dense roads are used to limit the amount of needed informationsharing about message delivery delay.4.3.3 Exploitation of Travel History and ContactsSo far we have shown how to identify roads based on their traffic features. By usingthis knowledge, methods like VADD select the road with lowest possible delay andtry to find relay nodes which are following these paths. The difficulty of usingmethods like VADD arises when the traffic density is very sparse and therefore thepossibility of finding a favorable relay is rare. VADD tries to find the next best pathbased on the current available relays in range to compensate. However, the lack ofknowledge about future path of candidate neighbors may lead the node to choose acandidate which will change its course. Therefore the chosen relay can stray fromthe best path and become a useless choice and the non-chosen relay may follow thepath with lowest delay. In both cases, VADD has chosen a wrong next relay.As explained before, our intention is to utilize future path prediction while min-imizing the exposure of private information to unknown collaborators. The goal isto find a path with lowest possible delay. However to achieve an optimum delay, allthe road segments within the optimum path should have carrier/relay nodes at theexact moment that a packet reaches there. This assumption is unrealistic speciallyfor road segments with sparse traffic. Therefore we use a heuristic approach and72reduce the path selection into a few decisions. These decisions are taken to selectbetween a path which may include road segments belonging to shortest path, aswell as the ones that are not leading directly to destination but instead, are fromdense roads. The advantage of using dense roads is the seamless connectivityamong nodes which leads to significantly lower delay by using relays instead ofpacket carriers.We know that a majority of nodes in the street are following predictable paths(The concept of road regularity has been studied in [85]). Based on their experi-ments the top ten most frequent routes make up 50% of a driver’s trips). Hence itis reasonable to trust the knowledge of a neighbour regarding its future path and touse it to calculate the empirical delivery delay within the area.To choose a path from aforementioned strategies, we need to calculate the Ex-pected Forwarding Time in road segment s, hereafter referred as Tf wd(s):Tf wd(s) =lsvs, for s ∈ sparse (4.3)ds, for s ∈ denseThe reason behind Section 4.3 is that nodes residing in dense road segments areexpected to quickly rebroadcast the messages toward the destination. This is verysimilar to VADD approach. Therefore the expected forwarding time is relative tothe density of the nodes in the road segment. However, in sparse road segments,this option is not available and nodes are generally carrying the message throughthe road segment. Moreover, because of privacy issues, as well as the overhead,knowledge about future paths of neighbors is not shared among neighbors. Hence73we cannot determine the total expected delivery time of a message when consider-ing relays in sparse road segments.To avoid the need to have global knowledge about travel times, every nodehas to calculate the delivery delay of a message. We have used Dijkstra’s shortestpath algorithm to calculate the delivery delay from current road segment to theother road segments. As explained before, we are initially using statistical trafficinformation to calculate the delays. However, the method to calculate the delay fordense roads is different from ofsparse roads.4.3.4 Calculating Travel TimeThe selection of best carrier is based on the node’s own travel history as well aspreviously experienced contacts with other neighbors. We define Expected TravelTime from road segment s to one of four dense road segments that surround s (inquadrant q and closest to current spot) as T qexp(s). Initially this value is set to thesum of Expected Forwarding Times starting from the current segment until thenode reaches the first dense road in its path. In every iteration of passing from apath, this initial value changes based on actual experienced travel time and is re-ferred as T avgexp (s). Moreover, the overall expected travel time value keeps changingby every update received from neighbors. Every time a node encounters a newneighbor, it tries to synchronize its experienced travel times with them. When anew time is received from a neighbor (named as T newexp (s)), update is performed asfollowing:Texp(s) = ω(αT newexp (s)+(1−α)T oldexp (s))+(1−ω)T avgexp (s) (4.4)74Figure 4.2: Streets in city of Cologne, Germany extracted from [3]. denseroads are shown in dark.ω is a weight factor to adjust the effect of neighbors time in overall travel time:ω = e−log2σ2neighboursσ2avg (4.5)4.3.5 Travel Time SynchronizationEvery vehicular node is set to broadcast any updated travel time toward dense pathsaround current road segment if there exists a neighbor which has not received thelatest updates (known by receiving a beacon that contains a smaller update version75number). The process of synchronization is a periodic event which is triggeredonce every Tinterval . As mentioned before, we adapt the rate of synchronizationbased on latest sensed background traffic. If the network is heavily utilized and/orthe future contact time with the neighbors is very long, the synchronization broad-casts are not transmitted. We calculate Psync, the probability of sending the syncpacket, as following:Psync = e(−K.T.U) (4.6)whereT =1Tmax 1n ∑ni=11b Tcon(i)Tint c+ε(4.7)andU =∑mj=1S jR jTint(4.8)K is a constant acting as an adjustment factor. T represents the time urgency ofsending the broadcast and it depends on the predicted contact period with currentneighbors which have not received current update (Tcon is the remaining contacttime and Tint is the interval for sending the updates). Tmax is the maximum predic-tion period and is statically set within a simulation. We use factor T to avoid longdelays which may cause loss of opportunity to update neighbors. U represents thecurrent utilization ratio of network and is given by the amount of the time spentto transmit and receive application and control data to the total time interval. S isthe number of bits for every transmission and R is the transmission rate (in bitsper second). In practice, every node listens to its network interface in promiscuous76mode and logs the number of received bits. We should mention that this methoddoes not consider the hidden and exposed terminals.4.3.6 Data Dissemination AlgorithmOne of the objectives of the proposed data dissemination method is to combinethe bandwidth efficiency of relay selection in sparse configuration with time effi-ciency of fast relay in densely populated areas. We define two different settings toseparate the phases of relaying. The first is when the packet is being transmittedalong dense vehicular traffic. In this setting, relaying speed is significantly higherthan carrying. Therefore it is not necessary to introduce extra transmission andprocessing overhead to select the best next relay. In the second setting we considerthe areas with low traffic density and hence higher relaying delay. In such a sce-nario, selection of a proper carrier becomes essential because there are not manyalternative carriers available and finding a faster path may become impossible.4.4 EvaluationIn order to evaluate our proposed method, we have implemented our method alongwith a version of VADD introduced in [75] and Epidemic routing [94] as baselinesrepresenting the literature. Although more recent methods such as [88] could beused for comparison, VADD is still accepted as a basic comparison method in theresearch community because it can be used for a large domain of applications invehicular networks. Epidemic routing is also chosen because of its simplicity.We chose NS-3 [95], a new simulator that is intended to eventually replace theaging and well-known NS-2. We have implemented the broadcasting and beacon77Table 4.1: Important Simulation ParametersParameter ValueNetwork interface 802.11a1Data rate 2MbpsNumber of nodes 250,500Beacon interval 1 secSync interval 2 secTransmission range 100mMax predicted contact time 30 secDaily iterations 20Packet sources 5 ∼ 30Packet rate 0.1/secPacket size 4KBPacket TTL 300 sectransmissions as well as a new module to communicate with a MySQL databasein order to store and retrieve experienced knowledge of vehicular nodes. We usedthe map topology and mobility traces of Tapas-Cologne project [3]. The providedtraces were generated using SUMO [69], the urban mobility simulator.The overall topology is shown in Figure 4.2, a simulated map for city ofCologne, Germany. Since simulated traces include a very large number of vehi-cles, for each run we randomly select a number of them and therefore we simulatedifferent contacts per run. We also have cropped the map to include a smaller partof the city to make the program runnable. In order to extract the necessary infor-mation about the topology, we have written several java tools to extract unique roadsegments (refinement was necessary because of duplicate names of streets) and theaverage traffic densities. Moreover to speedup the simulation, we have importedstreet based locations for run-time lookups. Every vehicle has a separate trip routeand this route is also stored in the database. When a node enters the simulation,1Although in a realistic scenario 802.11p is a better candidate for inter-vehicle communication,due to lack of required physical model in ns-3 implementation at the time we have done this, 802.11awas chosen. Compared to other options available, 802.11a is the closest alternative to DSRC.780 5 10 15 200.550.60.650.70.750.80.850.90.951IterationData Delivery rate  Predict (250 nodes)Epidemic (250 nodes)VADD (250 nodes)Predict (500 nodes)Epidemic (500 nodes)VADD (500 nodes)Figure 4.3: Data delivery ratio for each running iteration.it fetches its last experienced knowledge and iteratively improves it as being ex-plained in Equation 4.7. The important network simulation parameters are shownin Table 4.1.We compare the performance results of our method (mentioned hereafter asPredict) with VADD and conventional Epidemic methods in terms of delivery rate,delay and overhead. We consider two setups, one with less traffic (250 nodes) andone with more traffic which is mainly flowing in dense roads.In Figure 4.3 we compare the delivery ratio as a function of the number of it-erations. Each iteration represents a re-run of the simulation while knowledge ofnodes is adjusted in the last run. Delivery is arrival of a packet in a road segmentwhich is defined as destination. Therefore if a node located in the destination road795 10 15 20 25 30102030405060708090Number of SourcesAverage First Delivery Delay (s)  Predict (250 nodes)Epidemic (250 nodes)VADD (250 nodes)Predict (500 nodes)Epidemic (500 nodes)VADD (500 nodes)Figure 4.4: Average delay of first data delivery as a function of the numberof sources.segment receives the packet, the timer will stop, even if deliveries to other resid-ing nodes continue. Epidemic method should have the highest delivery rate but itseems that over broadcasting causes excessive collision rate (especially in densersetup). At first our method starts with very low delivery rate because there is notenough knowledge about neighbor nodes. However after seven iterations in sparsesetup, and 15 iterations in dense setup, it outperforms VADD. The reason for betterperformance in sparse traffic condition (compared to VADD) is that better carriersare chosen in sparse road segments and since there are not many contact opportu-nities in these road segments, the better carrier causes significant improvements.In Figure 4.4 we compare the average first delivery delay. Epidemic methodhas the worst performance and that is because of high rate of packet rebroadcasting805 10 15 20 25 300481215Number of SourcesTraffic per KB of Background Data  Predict (250 nodes)Epidemic (250 nodes)VADD (250 nodes)Predict (500 nodes)Epidemic (500 nodes)VADD (500 nodes)Figure 4.5: Generated traffic per kilobyte of background Data when networkis fully utilized.which leads to excessive collisions. As it is shown here, our method can outperformVADD in both dense and sparse traffic. The packet delay is relatively low even forhigh number of packet generators. One advantage of using relay in dense roads isthat packet delivery delay is significantly lowered compared to the time that trafficsparsity does not allow seamless connectivity. This is the reason that we intend toutilize dense road segments as much as possible.To show the overhead effect of dissemination methods on the background data,we present Figure 4.5. In this figure, we compare the amount of generated dataand control packets to the background data. Note that this comparison is doneonly when the network is fully utilized. As we can see the amount of overheadgenerated by Epidemic method is very high. In this condition data dissemination81using Epidemic routing causes serious disruption in network functionality. Sincevehicular network is primarily designed for safety applications, over utilizationin not acceptable. Compared to VADD, our method is generating slightly moreoverhead, which is caused by synchronization packets. However, because we arecontrolling the rate of synchronization by monitoring the background traffic, overutilization does not happen.4.5 ConclusionIn this chapter we have proposed a macroscopic mobility aware data disseminationprocedure which can be used in delay tolerant VANET. We have based our workon the assumption that most of the users follow a repetitive mobility pattern whichcan be used to predict the future mobility paths. Every node in this procedureis responsible for carrying and forwarding data packets. Our goal is to providehigh delivery rate to vehicles that are commuting in the destination area and toprovide the best possible delivery times. However we have to consider packet relaywithin non-sparse network conditions in order to achieve better delivery times.The simulations show improvement in packet delivery delay while the imposedoverhead is contained. In future work, we are going to add more performancecomparisons with more diverse network and traffic conditions. We have to improvethe queueing system to consider deadlines while more than one packets are carriedby a node. Sudden changes (e.g. accidents and traffic jams) are not considered inour simulations and should be included in the future.82Chapter 5Concluding remarksVANET is emerging as one of the most important practical divisions of MANET. ITSis the first category of applications in this scheme which has drawn the attentionof researchers and engineers. Many autonomous intelligent systems have alreadybeen implemented on-board for vehicles. However, cooperative networking of ve-hicles is uncommon today and will be more prevalent in the future. Wireless datacommunications will have a huge impact on ITS.One of the principal challenges to address is data dissemination. This is due tothe dynamic nature of VANET caused by high speed mobility of contributing nodesand temporal changes in connectivity.Temporal and geographical context of the network introduces a challenge butthere are potential solutions. On the one hand, the changing traffic condition duringdifferent hours of the day, as well as days of the week and special occasions in ayear causes regular broadcasting to become inefficient. On the other hand, learningand considering these changes in network topology and density can help the data83dissemination algorithms to become more efficient in fast relaying of the packetswhere necessary.In Chapter 2, we have focused on the enhancement of server selection in VANETwhile working in heterogeneous network environments. We chose heterogeneousnetworks because the penetration ratio of long range data connections in vehicu-lar networks is not high enough to be considered an inclusive and generic meshnetwork. Therefore, fewer vehicles which are equipped with both long range andshort range wireless adapters are able to act as proxies or mobile servers to provideservices such as location services. To maintain the location information on othernodes in the network, nodes use vehicular location servers which are also vehiclesin nature.We proposed a method to measure and use link reliability for choosing the mo-bile server. We assumed that the servers are special vehicles in nature, equippedwith short range and long range wireless technologies. Short range network isused to communicate with surrounding vehicles (i.e. clients) and long range wire-less connections are used to create a mesh network of servers. Therefore, thesevehicles can act as service providers to other vehicles in situations where there isnot enough infrastructure in the environment. By using the link reliability factor,we are proposing a method to choose a server based on the durability of the currentconnection to that server.While the proposed method in Chapter 2 is designed to choose reliable serversby focusing on heterogeneous networks, we assumed that the trajectories of theservers are known. We justify this assumption because we considered these serversas special nodes in the network. However, when moving from these multi-homednodes (e.g. public transit vehicles) in network toward single-homed nodes, the pre-84condition of having a-priori known trajectories becomes unrealistic. Consideringthis assumption, we have proposed a protocol to minimize the usage of expensivelong range wireless media and provided a method to choose location servers us-ing path reliability. Vehicles that are not capable of long range communication, usemulti-homed nodes as location servers and choose one based on the future link life-time. Our approach achieves better link lifetime and consequently provides loweroverhead in valuable long range wireless communication. The proposed method isnovel in terms of using path prediction and link quality estimation for choosing alocation server. This method is useful if the cost of using long range communica-tion is relatively higher than usage of short range communication.In Chapter 3, we focused on targeted (context-aware) broadcasting in a homo-geneous VANET. We assumed that the disseminated information is either gener-ated by vehicles on road or is originated from a road side unit and is handed tothe vehicles to be disseminated towards the AOI. The goal is to choose the broad-casting scheme without any prior knowledge about geographical distribution of ar-eas where information is considered as useful information. The work done in thischapter is based on a distributed reinforcement learning mechanism we proposed tolearn the AOI for every message type. Let’s consider a message which is about thetraffic condition in a specific area of the map, without any prior knowledge aboutareas where this message may become useful for other vehicles. Our proposedmethod can be used to find out in which areas of the map the message is receivedby an endpoint receiver which is eventually going to reward the arrival of the mes-sage. The benefit of this approach is that when there is no known geographicalcontext about useful broadcasts, the learning mechanism builds the context. Our85proposal in this chapter needs further work to develop a practical synchronizationmechanism.In Chapter 4, we focused our attention on link instability in VANET’s. This as-pect of the homogeneous VANET’s was not addressed in Chapter 3. Vehicle densityin various geographical regions may vary. Therefore, the stability of relay path invehicular networks is not deterministic. In such situations, information dissemina-tion can be interrupted frequently. Thus, carry and forward is utilized to avoid dataloss. In urban areas, the density of on road vehicles is different in major roads (i.e.dense) compared to other areas. We proposed a message dissemination approachwhile considering the fact that major roads in cities normally create contouringedges around areas with less traffic. In our proposed message dissemination al-gorithm, vehicles share their knowledge about dissemination delay for the majorroads to form a distributed global knowledge of the vehicle density in nearby majorroads. Using this information, direction of dissemination is chosen and messagesare relayed to the closest major roads.We have created a two phase message dissemination regime. In the first phase,the effort is to carry and forward the packet to reach the closest major road. In thesecond phase, packets are relayed toward the AOI. The benefit of this approach isthat the amount of time spent to carry and forward the packets is minimised (thedelay caused by carry and forward is significantly higher than the delay to relaythe packets). Based on the simulation results and comparisons to other methodssuch as VADD [75], our method is reducing the data delivery delay. To contain thetransmission overhead, we are limiting the travel time negotiation to sparse roadsegments. Using this constraint, the amount of transmission overhead is contained.In this thesis, we have proposed solutions for two major problems in VANET’s.86Firstly, we have proposed a method to decrease the transmission cost and mes-sage delivery delay in heterogeneous VANET’s.Secondly, we have proposed two methods for data dissemination in two differ-ent conditions. First, we assumed that there is no geographical context for loca-tions that are critical for forwarding messages. Second, we assumed that historicalmobility information is available. In both cases, we proposed proper methods toimprove message delivery and reduce the delay.For future research, we propose further studies on the security and privacy is-sues of sharing historical mobility information. We have tried to minimize thetraces of private information in shared data by aggregation and abstraction of his-torical information. However, it may be possible to extract footprints of trajectorieswithin the shared information.To improve the proposed method in Chapter 3, further studies are needed toobtain a better synchronization mechanism between vehicular nodes. Our work inaforementioned chapter is focused on the learning system. However, the conver-gence of the proposed method depends on the quality of the synchronization. Ifvehicular nodes cannot share the learnt state values, the convergence may becomepractically impossible. Therefore, we think it is imperative to study and proposebetter methods for distributed synchronization. This work could also be improvedby studying the effect of sudden traffic pattern changes. For example, if an acci-dent occurs, and consequently the traffic pattern changes, how it would affect thelearning convergence of RLAB.Additionally, more diverse network and traffic conditions can be used for evalu-ation and improvement of our proposed methods. We have used available mobility87scenarios and simulated vehicular trajectories. Any further mobility models andcommunication protocols in the future can be used for evaluation of our research.88Bibliography[1] M. Saini, A. Alelaiwi, and A. E. Saddik, “How close are we to realizing apragmatic vanet solution? a meta-survey,” ACM Computing Surveys(CSUR), vol. 48, no. 2, p. 29, 2015. → pages x, 4[2] “Open Street Map,” Accessed April 2016. [Online]. Available:http://www.openstreetmap.org/ → pages x, 29[3] “Tapascologne project,” Accessed April 2016. [Online]. Available:http://sourceforge.net/apps/mediawiki/sumo/index.php?title=Data/Scenarios/TAPASCologne → pages xi, 71, 75, 78[4] D. Jiang and L. Delgrossi, “Ieee 802.11 p: Towards an international standardfor wireless access in vehicular environments,” in Vehicular TechnologyConference, 2008. VTC Spring 2008. IEEE. IEEE, 2008, pp. 2036–2040.→ pages 2[5] D. Jiang, V. Taliwal, A. Meier, W. Holfelder, and R. Herrtwich, “Design of5.9 ghz dsrc-based vehicular safety communication,” IEEE WirelessCommunications, vol. 13, no. 5, pp. 36–43, 2006. → pages 2[6] “Dedicated Short Range Communications (DSRC),” Accessed April 2010.[Online]. Available:http://www.standards.its.dot.gov/Documents/advisories/dsrc advisory.htm→ pages 2[7] “Cars Talking and Hearing in Harmony a Smart Move for ETSI Short RangeCommunications (DSRC),” Accessed September 2011. [Online]. Available:http://www.etsi.org/WebSite/NewsandEvents/2008 09 Harmonizedstandards ITS.aspx → pages 2[8] L. Wischhof, A. Ebner, and H. Rohling, “Information dissemination inself-organizing intervehicle networks,” IEEE Transactions on intelligenttransportation systems, vol. 6, no. 1, pp. 90–101, 2005. → pages 3, 4489[9] T. Zhong, B. Xu, and O. Wolfson, “Disseminating real-time trafficinformation in vehicular ad-hoc networks,” in Intelligent VehiclesSymposium, 2008 IEEE. IEEE, 2008, pp. 1056–1061. → pages 3[10] T. Nadeem, S. Dashtinezhad, C. Liao, and L. Iftode, “Trafficview: Ascalable traffic monitoring system,” in Mobile Data Management, 2004.Proceedings. 2004 IEEE International Conference on. IEEE, 2004, pp.13–26. → pages 3, 5[11] T. Fujiki, M. Kirimura, T. Umedu, and T. Higashino, “Efficient acquisitionof local traffic information using inter-vehicle communication with queries,”in Intelligent Transportation Systems Conference, 2007. ITSC 2007. IEEE.IEEE, 2007, pp. 241–246. → pages 3[12] Q. Yu and G. Heijenk, “Abiding geocast for warning message disseminationin vehicular ad hoc networks,” in Communications Workshops, 2008. ICCWorkshops’ 08. IEEE International Conference on. IEEE, 2008, pp.400–404. → pages 3[13] G. Korkmaz, E. Ekici, F. O¨zgu¨ner, and U¨. O¨zgu¨ner, “Urban multi-hopbroadcast protocol for inter-vehicle communication systems,” inProceedings of the 1st ACM international workshop on Vehicular ad hocnetworks. ACM, 2004, pp. 76–85. → pages 3[14] E. Fasolo, A. Zanella, and M. Zorzi, “An effective broadcast scheme for alertmessage propagation in vehicular ad hoc networks,” in Communications,2006. ICC’06. IEEE International Conference on, vol. 9. IEEE, 2006, pp.3960–3965. → pages[15] D. Li, H. Huang, X. Li, M. Li, and F. Tang, “A distance-based directionalbroadcast protocol for urban vehicular ad hoc network,” in WirelessCommunications, Networking and Mobile Computing, 2007. WiCom 2007.International Conference on. IEEE, 2007, pp. 1520–1523. → pages[16] N. Wisitpongphan, O. Tonguz, J. S. Parikh, P. Mudalige, F. Bai, andV. Sadekar, “Broadcast storm mitigation techniques in vehicular ad hocnetworks,” Wireless Communications, IEEE, vol. 14, no. 6, pp. 84–94, 2007.→ pages[17] S. Khakbaz and M. Fathy, “A reliable method for disseminating safetyinformation in vehicular ad hoc networks considering fragmentationproblem,” in Wireless and Mobile Communications, 2008. ICWMC’08. TheFourth International Conference on. IEEE, 2008, pp. 25–30. → pages 390[18] H. ALshaer and E. Horlait, “An optimized adaptive broadcast scheme forinter-vehicle communication,” in Vehicular Technology Conference, 2005.VTC 2005-Spring. 2005 IEEE 61st, vol. 5. IEEE, 2005, pp. 2840–2844. →pages[19] A. Wegener, H. Hellbru¨ck, S. Fischer, C. Schmidt, and S. Fekete, “Autocast:An adaptive data dissemination protocol for traffic information systems,” inVehicular Technology Conference, 2007. VTC-2007 Fall. 2007 IEEE 66th.IEEE, 2007, pp. 1947–1951. → pages[20] S. Panichpapiboon and G. Ferrari, “Irresponsible forwarding,” in ITSTelecommunications, 2008. ITST 2008. 8th International Conference on.IEEE, 2008, pp. 311–316. → pages 3[21] L. E. Li, R. Ramjee, M. Buddhikot, and S. Miller, “Network coding-basedbroadcast in mobile ad-hoc networks,” in INFOCOM 2007. 26th IEEEInternational Conference on Computer Communications. IEEE. IEEE,2007, pp. 1739–1747. → pages 3[22] S. Yang and J. Wu, “Efficient broadcasting using network coding anddirectional antennas in manets,” Parallel and Distributed Systems, IEEETransactions on, vol. 21, no. 2, pp. 148–161, 2010. → pages[23] N. Kadi and K. Al Agha, “Mpr-based flooding with distributed fountainnetwork coding,” in Ad Hoc Networking Workshop (Med-Hoc-Net), 2010The 9th IFIP Annual Mediterranean. IEEE, 2010, pp. 1–5. → pages 3[24] H. Moustafa and Y. Zhang, Vehicular networks: techniques, standards, andapplications. Auerbach publications, 2009. → pages 5[25] A. Int, “Standard Specification for Telecommunications and InformationExchange Between Roadside and Vehicle Systems-5GHz Band DedicatedShort Range Communications (DSRC) Medium Access Control (MAC) andPhysical Layer (PHY) Specifications,” ASTM E2213-03, 2003. → pages 5[26] H. Menouar, F. Filali, and M. Lenardi, “A survey and qualitative analysis ofMAC protocols for vehicular ad hoc networks,” Wireless Communications,IEEE, vol. 13, no. 5, pp. 30–35, 2006. → pages 5[27] S. Dornbush and A. Joshi, “Streetsmart traffic: Discovering anddisseminating automobile congestion using vanet’s,” in VehicularTechnology Conference, 2007. VTC2007-Spring. IEEE 65th. IEEE, 2007,pp. 11–15. → pages 5, 691[28] P. Fernandes and U. Nunes, “Platooning with ivc-enabled autonomousvehicles: Strategies to mitigate communication delays, improve safety andtraffic flow,” Intelligent Transportation Systems, IEEE Transactions on,vol. 13, no. 1, pp. 91–106, 2012. → pages 5[29] S. Ghahremani, M. R. J. Sattari, S. Khorsandroo, M. Ahmed, and R. M.Noor, “A traffic control model on vanet environment for minimum road riskin a shortest way,” in Green High Performance Computing (ICGHPC), 2013IEEE International Conference on. IEEE, 2013, pp. 1–5. → pages 6[30] L. Wischoff, A. Ebner, H. Rohling, M. Lott, and R. Halfmann, “SOTIS-aSelf-Organizing Traffic Information System,” in Vehicular TechnologyConference, 2003. VTC 2003-Spring. The 57th IEEE Semiannual, vol. 4.IEEE, 2003, pp. 2442–2446. → pages 6[31] e. Baldessari, R., “C2C-CC Manifesto,” Car 2 Car CommunicationConsortium, Tech. Rep., Accessed August 2010. [Online]. Available:http://www.car-to-car.org/fileadmin/downloads/C2C-CC manifesto v1.1.pdf→ pages 6, 10[32] P. Zhou, T. Nadeem, P. Kang, C. Borcea, and L. Iftode, “EZCab: A cabbooking application using short-range wireless communication,” in ThirdIEEE International Conference on Pervasive Computing andCommunications, PerCom 2005, vol. 1, 2005, pp. 27–40. → pages[33] T. Willke, P. Tientrakool, and N. Maxemchuk, “A survey of inter-vehiclecommunication protocols and their applications,” IEEE CommunicationsSurveys and Tutorials, vol. 11, no. 2, pp. 3–20, 2009. → pages 10[34] E. Hossain, G. Chow, V. Leung, R. McLeod, J. Misic, V. Wong, and O. Yang,“Vehicular telematics over heterogeneous wireless networks: A survey,”Computer Communications, vol. 33, no. 7, pp. 775–793, 2010. → pages 6[35] A. T. Akabane, E. R. M. Madeira, and L. A. Villas, “Atena: abroadcast-storm-aware solution for highway environments,” IEEE LatinAmerica transactions, vol. 12, no. 3, pp. 436–441, 2014. → pages 7[36] X. Shi, G. Zhang, C. Liu, and T. Han, “A novel trace-aided datadissemination algorithm in vehicular networks,” in 2015 IEEE 12th Intl Confon Ubiquitous Intelligence and Computing and 2015 IEEE 12th Intl Conf onAutonomic and Trusted Computing and 2015 IEEE 15th Intl Conf onScalable Computing and Communications and Its Associated Workshops(UIC-ATC-ScalCom). IEEE, 2015, pp. 99–104. → pages 792[37] H. Nguyen-Minh, A. Benslimane, and M. Radenkovic, “Social delaytolerant approach for safety services in vehicular networks,” in 2015International Wireless Communications and Mobile Computing Conference(IWCMC). IEEE, 2015, pp. 1199–1204. → pages 7[38] A. T. Akabane, E. R. M. Madeira, and L. A. Villas, “A suitable vehicularbroadcast protocol under different traffic patterns for urban scenario,” IEEELatin America Transactions, vol. 13, no. 1, pp. 222–227, 2015. → pages 7[39] C. Sobin, V. Raychoudhury, G. Marfia, and A. Singla, “A survey of routingand data dissemination in delay tolerant networks,” Journal of Network andComputer Applications, 2016. → pages 7[40] S. Maaroufi and S. Pierre, “Vehicular social systems: an overview and aperformance case study,” in Proceedings of the fourth ACM internationalsymposium on Development and analysis of intelligent vehicular networksand applications. ACM, 2014, pp. 17–24. → pages 7[41] H. R. Arkian, R. E. Atani, A. Diyanat, and A. Pourkhalili, “A cluster-basedvehicular cloud architecture with learning-based resource management,” TheJournal of Supercomputing, vol. 71, no. 4, pp. 1401–1426, 2015. → pages 7[42] B. Younes and M. Y. Saleh, “Efficient traffic control protocols for vehicularad-hoc networks,” Ph.D. dissertation, Universite´ d’Ottawa/University ofOttawa, 2015. → pages 7[43] W. Chen, Vehicular communications and networks: Architectures, protocols,operation and deployment. Elsevier, 2015. → pages 7[44] A. V. Vasilakos, Y. Zhang, and T. Spyropoulos, Delay tolerant networks:Protocols and applications. CRC press, 2016. → pages 7[45] A. P. Silva, S. Burleigh, C. M. Hirata, and K. Obraczka, “A survey oncongestion control for delay and disruption tolerant networks,” Ad HocNetworks, vol. 25, pp. 480–494, 2015. → pages 7[46] K. Wei, X. Liang, and K. Xu, “A survey of social-aware routing protocols indelay tolerant networks: applications, taxonomy and design-related issues,”IEEE Communications Surveys & Tutorials, vol. 16, no. 1, pp. 556–578,2014. → pages 7[47] M. Nidd, “Service discovery in DEAPspace,” Personal Communications,IEEE, vol. 8, no. 4, pp. 39–45, 2002. → pages 1193[48] V. Lenders, M. May, and B. Plattner, “Service discovery in mobile ad hocnetworks: A field theoretic approach,” Pervasive and Mobile Computing,vol. 1, no. 3, pp. 343–370, 2005. → pages 12, 13, 21, 27, 33[49] U. Kozat and L. Tassiulas, “Network layer support for service discovery inmobile ad hoc networks,” in INFOCOM 2003. Twenty-Second Annual JointConference of the IEEE Computer and Communications. IEEE Societies,vol. 3. IEEE, 2003, pp. 1965–1975. → pages 12[50] J. Tyan and Q. Mahmoud, “A network layer based architecture for servicediscovery in mobile ad hoc networks,” in Electrical and ComputerEngineering, 2004. Canadian Conference on, vol. 3. IEEE, 2004, pp.1379–1384. → pages 12[51] A. Mian, R. Baldoni, and R. Beraldi, “A Survey of Service DiscoveryProtocols in Multihop Mobile Ad Hoc Networks,” IEEE PervasiveComputing, vol. 8, pp. 66–74, 2009. → pages 12[52] R. Hinden and S. Deering, “IP Version 6 Addressing Architecture, RFC2373,” http://ietfreport.isoc.org/rfc/rfc2373.txt, 1998 (Accessed March2012). → pages 12[53] C. Toh, “Associativity-based routing for ad hoc mobile networks,” WirelessPersonal Communications, vol. 4, no. 2, pp. 103–139, 1997. → pages 13[54] S. Agarwal, A. Ahuja, J. Singh, and R. Shorey, “Route-lifetime assessmentbased routing (RABR) protocol for mobile ad-hoc networks,” in IEEEInternational Conference on Communications, vol. 3. Citeseer, 2000, pp.1697–1701. → pages 13, 33[55] R. Friedman and G. Kliot, “Location Services in Wireless Ad Hoc andHybrid Networks: A Survey,” Department of Computer Science,Technion,Tech. Rep., 2006. → pages 15[56] S. Basagni, I. Chlamtac, V. Syrotiuk, and B. Woodward, “A distance routingeffect algorithm for mobility (DREAM),” in Proceedings of the 4th annualACM/IEEE international conference on Mobile computing and networking,1998, pp. 76–84. → pages 15[57] D. Liu, I. Stojmenovic, and X. Jia, “A scalable quorum based locationservice in ad hoc and sensor networks,” in 2006 IEEE InternationalConference on Mobile Adhoc and Sensor Systems (MASS), 2006, pp.489–492. → pages 15, 3394[58] J. Li, J. Jannotti, D. S. De Couto, D. R. Karger, and R. Morris, “Scalablelocation service for geographic ad hoc routing,” in Proceedings of theAnnual International Conference on Mobile Computing andNetworking(MOBICOM), 2000, pp. 120–130. → pages 15[59] H. Saleet, R. Langar, O. Basir, and R. Boutaba, “Proposal and analysis ofregion-based location service management protocol for VANETs,” in IEEEGlobal Telecommunications Conference(GLOBECOM), 2008, pp. 491–496.→ pages[60] M. D. Dikaiakos, A. Florides, T. Nadeem, and L. Iftode, “Location-awareservices over vehicular ad-hoc networks using car-to-car communication,”Selected Areas in Communications, IEEE Journal on, vol. 25, no. 8, pp.1590–1602, 2007. → pages[61] W. Kieß, H. Fu¨ßler, J. Widmer, and M. Mauve, “Hierarchical locationservice for mobile ad-hoc networks,” ACM SIGMOBILE Mobile Computingand Communications Review (MC2R), vol. 8, no. 4, pp. 47–58, 2004. →pages 15[62] S. Ahmed, G. C. Karmakar, and J. Kamruzzaman, “Hierarchical adaptivelocation service protocol for mobile ad hoc network,” in WirelessCommunications and Networking Conference, 2009. WCNC 2009. IEEE.IEEE, 2009, pp. 1–6. → pages 15[63] Z. J. Haas and E. Y. Hua, “Residual link lifetime prediction with limitedinformation input in mobile ad hoc networks,” in Proceedings of IEEEINFOCOM, 2008, pp. 26 – 30. → pages 22, 23[64] N. Sofra and K. K. Leung, “Link classification and residual time estimationthrough adaptive modeling for vanets,” in IEEE VTC, 2009, pp. 1 –5. →pages 23[65] H. Menouarand, M. Lenardi, and F. Filali, “Movement Prediction-basedRouting (MOPR) concept for position-based routing in vehicular networks,”in IEEE Vehicular Technology Conference, 2007, pp. 2101 – 2105. → pages23[66] J. Krumm, “Where will they turn: predicting turn proportions atintersections,” Personal and Ubiquitous Computing, Springer, AccessedAugust 2012. [Online]. Available:http://www.springerlink.com/content/n41v0m2q08g84554/ → pages 2395[67] D. Patterson, L. Liao, D. Fox, and H. Kautz, “Inferring high-level behaviorfrom low-level sensors,” Lecture Notes in Computer Science, pp. 73–89,2003. → pages 23[68] “The Network Simulator NS-2,” Accessed April 2011. [Online]. Available:http://www.isi.edu/nsnam/ns/ → pages 28[69] “Simulation of Urban MObility,” Accessed April 2015. [Online]. Available:http://sourceforge.net/apps/mediawiki/sumo/ → pages 28, 54, 78[70] J. S. Otto, F. E. Bustamante, and R. A. Berry, “Down the block and aroundthe corner: The impact of radio propagation on inter-vehicle wirelesscommunication,” in Proceedings - International Conference on DistributedComputing Systems, Montreal, QC, Canada, 2009, pp. 605 – 614. → pages29, 31, 48[71] T. Rappaport, Wireless communications: principles and practice. PrenticeHall PTR Upper Saddle River, NJ, USA, 2001. → pages 31, 48[72] H. Wu, R. Fujimoto, R. Guensler, and M. Hunter, “Mddv: a mobility-centricdata dissemination algorithm for vehicular networks,” in Proceedings of the1st ACM international workshop on Vehicular ad hoc networks. ACM,2004, pp. 47–56. → pages 44, 65[73] J. Zhao, Y. Zhang, and G. Cao, “Data pouring and buffering on the road: Anew data dissemination paradigm for vehicular ad hoc networks,” VehicularTechnology, IEEE Transactions on, vol. 56, no. 6, pp. 3266–3277, 2007. →pages 44, 65[74] T. Spyropoulos, K. Psounis, and C. Raghavendra, “Efficient routing inintermittently connected mobile networks: The multiple-copy case,”IEEE/ACM Transactions on Networking (TON), vol. 16, no. 1, pp. 77–90,2008. → pages[75] J. Zhao and G. Cao, “VADD: Vehicle-assisted data delivery in vehicular adhoc networks,” IEEE Transactions on Vehicular Technology, vol. 57, no. 3,pp. 1910–1922, 2008. → pages 44, 54, 63, 65, 77, 86[76] A. To¨ro¨k, P. Laborczi, and G. Gerha´th, “Spatially ConstrainedDissemination of Traffic Information in Vehicular Ad Hoc Networks,” inVehicular Technology Conference. IEEE, 2008, pp. 1–5. → pages 45, 4696[77] Z. Haas, J. Halpern, and L. Li, “Gossip-based ad hoc routing,” IEEE/ACMTransactions on Networking (TON), vol. 14, no. 3, p. 491, 2006. → pages45, 54, 57[78] B. Garbinato, A. Holzer, and F. Vessaz, “Six-shot broadcast: Acontext-aware algorithm for efficient message diffusion in manets,” On theMove to Meaningful Internet Systems: OTM 2008, pp. 625–638, 2008. →pages[79] O. Tonguz, N. Wisitpongphan, and F. Bai, “DV-CAST: a distributedvehicular broadcast protocol for vehicular ad hoc networks,” IEEE WirelessCommunications, vol. 17, no. 2, pp. 47–56, 2010. → pages 44, 65[80] P. Costa, D. Frey, M. Migliavacca, and L. Mottola, “Towards lightweightinformation dissemination in inter-vehicular networks,” in Proceedings ofthe 3rd international workshop on Vehicular ad hoc networks. ACM, 2006,pp. 20–29. → pages 45[81] J. Schneider, W. Wong, A. Moore, and M. Riedmiller, “Distributed valuefunctions,” in Machine learning: proceedings of the Sixteenth InternationalConference (ICML’99), Bled, Slovenia, June 27-30, 1999. MorganKaufmann Pub, 1999, pp. 371–378. → pages 47, 48, 50, 51[82] D. Borsetti, M. Fiore, C. Casetti, and C. Chiasserini, “When mobile servicesgo local,” in Proceedings of the 12th ACM international conference onModeling, analysis and simulation of wireless and mobile systems. ACM,2009, pp. 235–244. → pages 54[83] J. Krumm and E. Horvitz, “Predestination: Inferring destinations frompartial trajectories,” in UbiComp 2006: Ubiquitous Computing. Springer,2006, pp. 243–260. → pages 62[84] J. Krumm, “Real time destination prediction based on efficient routes,” SAETechnical Paper, Tech. Rep., 2006. → pages[85] J. Froehlich and J. Krumm, “Route prediction from trip observations,” SAESP, vol. 2193, p. 53, 2008. → pages 62, 68, 73[86] M. Koegel, W. Kiess, M. Kerper, and M. Mauve, “Compact vehiculartrajectory encoding,” in Vehicular Technology Conference (VTC Spring),2011 IEEE 73rd. IEEE, 2011, pp. 1–5. → pages 6297[87] J. Jeong, S. Guo, Y. Gu, T. He, and D. Du, “Tbd: Trajectory-based dataforwarding for light-traffic vehicular networks,” in Distributed ComputingSystems, 2009. ICDCS’09. 29th IEEE International Conference on. IEEE,2009, pp. 231–238. → pages 64[88] J. Jeong, S. Guo, Y. Gu, T. He, and D. H. Du, “Trajectory-based statisticalforwarding for multihop infrastructure-to-vehicle data delivery,” MobileComputing, IEEE Transactions on, vol. 11, no. 10, pp. 1523–1537, 2012. →pages 64, 77[89] S. Hosseininezhad, G. N. Shirazi, and V. Leung, “Rlab: Reinforcementlearning-based adaptive broadcasting for vehicular ad-hoc networks,” inVehicular Technology Conference (VTC Spring), 2011 IEEE 73rd. IEEE,2011, pp. 1–5. → pages 64[90] M. Scho¨nhof, A. Kesting, M. Treiber, and D. Helbing, “Coupled vehicle andinformation flows: Message transport on a dynamic vehicle network,”Physica A: Statistical Mechanics and its Applications, vol. 363, no. 1, pp.73–81, 2006. → pages 65[91] Y. Zhuang, J. Pan, and L. Cai, “A probabilistic model for messagepropagation in two-dimensional vehicular ad-hoc networks,” in Proceedingsof the seventh ACM international workshop on VehiculAr InterNETworking.ACM, 2010, pp. 31–40. → pages 65[92] J. Krumm, “How people use their vehicles: Statistics from the 2009 nationalhousehold travel survey,” SAE Technical Paper, Tech. Rep., 2012. → pages65[93] S. Uppoor and M. Fiore, “Large-scale urban vehicular mobility fornetworking research,” in Vehicular Networking Conference (VNC), 2011IEEE. IEEE, 2011, pp. 62–69. → pages 71[94] A. Vahdat, D. Becker et al., “Epidemic routing for partially connected adhoc networks,” Technical Report CS-200006, Duke University, Tech. Rep.,2000. → pages 77[95] “Ns-3 network simulator.” Accessed April 2016. [Online]. Available:http://www.nsnam.org → pages 7798


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



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"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items