Trajectory?Based Data Forwarding Schemes forr Vehicular Netwoorrkkss

Jaehoon(Paul)Jeong1,Tian He,and David H.C.Du

(1.Department of Software，Sungkyunkwan University，Suwon 440?746，Republic of Korea;

2.Department of Computer Science and Engineering，University of Minnesota，Minneapolis，MN 55455，USA)

Trajectory?Based Data Forwarding Schemes forr Vehicular Netwoorrkkss

Jaehoon(Paul)Jeong1,Tian He2,and David H.C.Du2

(1.Department of Software，Sungkyunkwan University，Suwon 440?746，Republic of Korea;

2.Department of Computer Science and Engineering，University of Minnesota，Minneapolis，MN 55455，USA)

This paper explains trajectory?based data forwarding schemes for multihop data delivery in vehicular networks where the trajectory is the GPS navigation path for driving in a road network.Nowadays，GPS?based navigation is popular with drivers either for effi?cient driving in unfamiliar road networks or for a better route，even in familiar road networks with heavy traffic.In this paper，we describe how to take advantage of vehicle trajectories in order to design data?forwarding schemes for information exchange in ve?hicular networks.The design of data?forwarding schemes takes into account not only the macro?scoped mobility of vehicular traffic statistics in road networks，but also the micro?scoped mobility of individual vehicle trajectories.This paper addresses the impor?tance of vehicle trajectory in the design of multihop vehicle?to?infrastructure，infrastructure?to?vehicle，and vehicle?to?vehicle data forwarding schemes.First，we explain the modeling of packet delivery delay and vehicle travel delay in both a road segment and an end?to?end path in a road network.Second，we describe a state?of?the?art data forwarding scheme using vehicular traffic statis?tics for the estimation of the end?to?end delivery delay as a forwarding metric.Last，we describe two data forwarding schemes based on both vehicle trajectory and vehicular traffic statistics in a privacy?preserving manner.

VANET;DSRC;vehicular networks;data forwarding;vehicle trajectory

1 Introduction

Vehicular ad hoc networks(VANETs)have been studied intensively in wireless communications be?tween vehicles for the driving safety and efficiency in road networks[1]-[7].Every year，many South Koreans die in road accidents，and the fatality rate is increas?ing[8].VANET can reduce the fatality rate by allowing vehi?cles to communicate directly with each other and avoid colli?sions in road networks.Also，in the era of high oil prices，VANET can determine the most efficient route for a car to take according to the final destination and real?time traffic condi?tions[9].A variety of automotive cloud services[10]can be en?visioned for vehicles and drivers.Such services include intelli?gent navigation，safe driving，automatic update of automotive software，onboard diagnostics(OBD)[11]，reporting for online diagnosis，and smartphone vehicular remote control.

VANET for driving safety and efficiency has been re?searched in earnest since dedicated short range communica?tions(DSRC)was standardized as IEEE 802.11p in 2010[12]-[14].IEEE 802.11p is an extension of IEEE 802.11a and de?fines the vehicular network characteristics，such as high?speed mobility and high vehicle density in roadways.Another impor?tant trend in vehicular networks is GPS?based navigation(e.g.，dedicated GPS navigation[15]and smartphone navigation [16])，which is commonly used by drivers to navigate in unfa?miliar areas.It was expected that 300 million mobile devices would be equipped with GPS receivers in 2009[17].These cut?ting?edge technologies for DSRC and GPS navigation open the way for research into the utilization of vehicle trajectories to make data forwarding more efficient in vehicular networks.

Let us assume the following setting in a vehicular network: The Traffic Control Center(TCC)[18]is a central node that col?lects traffic statistics(e.g.，vehicle inter?arrival rate and aver?age speed per road segment)in a road network.The TCC also maintains the trajectory，current position，speed，and direction of an individual vehicle to track vehicles registered in the TCC.Access points(APs)are sparsely deployed as roadside units(RSUs)[19]and are interconnected in order to provide ve?hicles with connectivity to wired networks(e.g.，the Internet) that lead to the TCC.APs have limited coverage because of the

sparse deployment of APs by the deployment cost，so the vehic?ular networks are Disruption Tolerant Networks(DTNs)such that vehicles adopt the forward?and?carry approach for the mul?tihop data delivery in road networks.Using this forward?and?carry approach，many data forwarding schemes(such as VADD [4]，Delay?bounded Routing[5]and SADV[6])for the vehicu?lar networks have been proposed so far.However，these schemes use only vehicular traffic statistics(e.g.，vehicle arriv?al rate per road segment)to compute a forwarding metric，such as Expected Delivery Delay(EDD)from a packet source to a packet destination.Thus，this EDD is used to select a next?hop vehicle toward the packet destination.

Given vehicle trajectories as future navigation paths avail?able through GPS?based navigation systems，three data for?warding schemes，i.e.，Trajectory?Based Forwarding(TBD)[1]，Trajectory?Based Statistical Forwarding(TSF)[2]，and Trajec?tory?Based Multi?Anycast Forwarding(TMA)[3]have been pro?posed to take advantage of these vehicle trajectories for 1)the better computation of a forwarding metric called EDD and 2) the determination of a target point that is the rendezvous posi?tion of the packet and the destination vehicle.TMA[3]is an extension of TSF[2]for the multicast data delivery from AP to multicast group vehicles as packet destinations.In this paper，we focus on the unicast data delivery scheme with TBD[1]and TSF[2]rather than the multicast data delivery scheme with TMA[3].Note that this paper is the refined version of our early magazine article in[20]，explaining TBD[1]and TSF[2]from the forwarding design aspect.

The remainder of this paper is structured as follows.Section 2 is a literature review of vehicular networking.Section 3 de?scribes the modeling of link delay，packet delivery delay，and vehicle travel delay.Section 4 describes a data?forwarding scheme called vehicle?assisted data delivery(VADD)，which is based on vehicular traffic statistics[4]，as well as two data?for?warding schemes，TBD[1]and TSF[2]，which are based on ve?hicle trajectories.Section 5 analyzes these two trajectory?based forwarding schemes along with VADD.Section 6 con?cludes the paper and describes future work.

2 Related Work

Much research has been done on multihop Vehicle?to?Infra?structure(V2I)[1]，[4]，[5]，Infrastructure?to?Vehicle(I2V)[2]，and Vehicle?to?Vehicle(V2V)[2]data?forwarding for safety and efficiency in vehicular networks.For these networks，VANETs are used for data forwarding over multihop toward the packet destination.VANET is different from traditional mobile ad hoc networks(MANETs)[20]because it supports the net?working in road networks with layout rather than in two?dimen?sional open space assumed by MANETs.VANET is designed to take into account 1)high?speed vehicular mobility on road?ways，2)confined vehicular mobility on roadways，and 3)pre?dictable vehicle mobility through roadmaps.Because of the first characteristic，there is frequent network partitioning and merging，so the forward?and?carry approach[1]is required in?stead of connection?oriented route usually used in MANET [21].Because of the second characteristic，vehicular traffic sta?tistics，such as vehicle arrival rate and average speed per road segment and vehicle branch probability at each intersection，can be collected[1].The third characteristic is due to vehicle trajectory provided by GPS navigator[2].

Many data?forwarding schemes have been proposed with dig?ital roadmaps and vehicular traffic statistics[4]-[6].VADD[4] formulates the data?forwarding process as a stochastic process in road segments or at intersections，and is designed to mini?mize delivery delay.Delay?bounded routing[5]is designed to minimize communication cost in terms of the number of packet transmissions for better channel utilization.SADV[6]is a sta?ble forwarding structure in road networks.It is based on relay nodes and reduces deviation in the delivery delay.These three schemes are for the multihop V2I data delivery，and the packet destination is a static node.Also，they utilize only vehicular traffic statistics to 1)estimate a link delay that is the delivery delay for a packet to be forwarded or carried over a road seg?ment and 2)estimate a forwarding metric of end?to?end(E2E) delivery delay.Thus，these vehicular traffic statistics are macro?scoped vehicular information that describes the overall pat?terns of vehicle mobility in road networks.

Besides the forwarding schemes based on macroscoped ve?hicular information，the following three data?forwarding schemes have been proposed:TBD[1]，TSF[2]，and TMA[3]. These are based on microscoped vehicular information，such as vehicle trajectory.Based on vehicle trajectory information，TBD，TSF，and TMA are designed for the multihop V2I，I2V，and V2V data delivery，respectively.In this paper，we show how useful vehicle trajectory is in the design of data?forward?ing schemes for vehicular networks.Because TMA[3]is an ex?tension of TSF[2]for multicasting in vehicular networks，we fo?cus on TSF along with TBD in this paper.Thus，the main ideas of TBD and TSF will be discussed to provide insight into the design of data?forwarding schemes with vehicle trajectory.

Machine?to?machine(M2M)communications have recently received a lot of attention within the networking community [22].In a road network setting，M2M needs to allow drivers，passengers，and pedestrians to communicate with vehicles，in?frastructure nodes，and Internet servers.This M2M is very im?portant to realize vehicular cloud services that have been iden?tified for next?generation vehicles[10].Nowadays，most vehi?cles have more than 50 embedded computer components[11] including OBD systems.When vehicles connect to vehicular cloud via the infrastructure nodes，they can access the follow?ing vehicular cloud services:1)automatic update of software related to systems embedded in the vehicle，2)intelligent navi?gation for congested road networks，3)automatic vehicle con?trol to mitigate the damage in a road accident，4)accident avoidance to prevent road accidents，and 5)the remote control

of vehicles through mobile devices(e.g.，smartphones and tab?lets).With these vehicular cloud services，DSRC?based data forwarding schemes provide vehicles with the network connec?tivity to the vehicular cloud through VANET at a lower cost by minimizing the usage of cellular networks such as 4G?LTE[23].

3 Delay Modeling

In this section，we describe link delay，E2E packet delivery delay，and E2E vehicle travel delay.We assume that vehicular traffic is one?way traffic to simplify delay modeling.Link delay modeling based on two?way traffic is not covered here.

3.1 Link Delay

In this subsection，we define link delay as the delay of a packet to be delivered over a road segment from its entrance in?tersection to its exit intersection using forward?and?carry.We consider link delay in the following two cases:1)No relay node exists at each intersection，and 2)A relay node exists at each intersection as a temporary packet holder.

3.1.1 Link Delay for a Road Segment without Relay Nodes

We model link delay for a road segment without relay nodes at its intersections that are the end?points of the road segment. As shown in Fig.1a，Packet Carriernk+1arrives at the en?trance of road segment(Ii，Ij).The link delay over the road se?gment lengthlis the sum of the communication delay over the forwarding distancelfand the carry delay over the carry distancelc.For simplicity，we represent the link delay as the carry delay because the forwarding delay in milliseconds is negligible compared with the carry delay in seconds.That is，the carry delay is the dominant factor in the link delay.

▲Figure 1.Link delay modeling for road segment.

To compute the link delay，we first need to compute the for?warding distancelfover road segmentland then compute the carry distancelcasl-lf.Letvbe the average vehicle speed over the road segment.The road segment(Ii，Ij)，the link delaydijcan be computed as the carry delay as follows:

The expected link delayE[dij]is computed as follows:

Thus，forE[dij]in(2)，the expected forwarding distance E[lf]needs to be computed.As shown in Fig.1a，E[lf]can be computed as the sum of vehicle interdistances Dhfor h=1...kfrom the entrance intersectionIi，leading to the co?nnected vehicular ad hoc network.We assume that the vehi?cles arrive at the entrance intersectionIiof road segment(Ii，Ij)by the Poisson process of the arrival rateλ.In light?traffic vehicular networks that are our target settings，this assumption is validated from traffic measurements[24].E[lf]is compu?ted as the conditional expectation of the length of the connect?ed vehicular ad hoc network，consisting of vehicle interdistanc?esDh(forh=1...k)interconnected by the communication rangeR.The vehicle interdistanceDhis the product of vehi?cle interarrival timeThand average vehicle speedvthat is，Dh=vTh.In[1]，the expected forwarding distanceE[lf]is co?mputed as follows:

In(3)，E[lf]is the product of 1)the average interdistance，denotedE[Dh|Dh≤R]，of two consecutive vehicles within the same connected vehicular ad hoc network，and 2)the ratio of the probability，denotedP[Dh≤R]，that the interdistance Dhis less than or equal to the communication rangeRto the probability，denotedP[Dh>R]，that the interdistanceDhis greater than the communication rangeR.

3.1.2 Link Delay for Road Segment with Relay Nodes

We model link delay for a road segment with relay nodes at its intersections.These nodes are end?points of the road seg?ment.A relay node is placed at each intersection as a tempo?rary packet holder for reliable I2V data delivery[2].Fig.1b shows link?delay modeling for a road segment(Ii，Ij)with r?elay nodes at its intersectionsIiandIj.For the case with r?

elay nodes，we consider the following two cases:1)immediate forwarding and 2)wait and carry.The first case is that packet carrierncforwards its packets to the head vehiclen1of the connected vehicular ad hoc network(comprisingkvehicles fromn1tonk)via the relay node(denotednk+1)at the en?tranceIi.The second case is that there are no vehicles within the communication rangeRof the entranceIimoving toward exitIj.In this case，packet carrierncforwards its packets to the relay node at entranceIi，and the relay node holds the packets until a vehicle arrives atIiand moves fromIitoIj.

The link delaydfor the two cases in Fig.1b is given by

The expected link delay is computed as the conditional ex?pectation of the link delay for the two cases as follows:

3.2 E2E Packet Delivery Delay

We define E2E packet delivery delay as the packet delivery delay along a forwarding path from a source position to a desti?nation position in the road network.We model this delay as the sum of the link delays of the road segments on the forwarding path.As in section 3.1.2，the E2E packet delivery delay，denot?edP，can be modeled as a Gamma distribution with the mean and variance of the E2E packet delivery delay as follows，as?suming that the forwarding path consists ofnedges:

3.3 E2E Vehicle Travel Delay

For E2E vehicle travel delay，we take the same approach with the E2E packet delivery delay in section 3.2.Assuming that the vehicle trajectory consists ofnedges，we have the mean and variance of the E2E vehicle delay distribution，de?notedV，as follows:

In next section，we describe three data forwarding schemes，VADD[4]，TBD[1]，and TSF[2].Also，we model the packet delivery delay and vehicle travel delay.

4 Data?Forwarding Schemes

VADD enables us to invent TBD and TSF with vehicle tra?

jectory for the V2I data delivery and the I2V data delivery，re?spectively.First，we explain how VADD computes a forward?ing metric called EDD with only vehicular traffic statistics，used to select a next?hop vehicle in the V2I data delivery.Sec?ond，we describe how TBD plugs in vehicle trajectory in the computation of a forwarding metric EDD for the V2I data deliv?ery.Last，we explain how TSF works for the I2V data delivery with our target point selection algorithm using the distributions of the destination vehicle’s trajectory.

4.1 Vehicle-Assisted Data Delivery for V2I Data Delivery(VADD)

VADD[4]is a data?forwarding scheme for V2I data deliv?ery.It is based on vehicular traffic statistics，such as the vehi?cle arrival rate and average speed per road segment along with the digital roadmaps provided by GPS navigation systems[15]. VADD is explained at first because TBD[1]，as one of vehicle trajectory?based forwarding schemes，enhances the stochastic model of VADD with individual vehicle trajectory.

VADD aims to minimize delivery delay from vehicle to infra?structure node(e.g.，AP).For example，the current packet carri?er(denoted carrier)wants to deliver its packet to AP in the road network(Fig.2a).Carrier has two neighboring vehicles，car1andcar2，within its communication range.The future tr?ajectories of these cars are shown by solid or dotted arrows.As?sume that the trajectory ofcar1passes through a light traffic path where a few vehicles are expected to move.On the other hand，the trajectory ofcar2passes through heavy traffic，and many vehicles are expected to move.Therefore，data forward?ing over communication has a high chance using intermediate vehicles as packet forwarders during the packet’s forward?and?carry process.In this case，definitely，Carrier needs to forward its packets tocar2as a next?hop carrier rather thancar1，as shown in Fig.2b.In VADD，to support this selection of a next?hop carrier based on vehicular traffic statistics，an EDD is com?puted as a forwarding metric by vehicles adjacent to the cur?rent packet carrier.A minimum?EDD vehicle will be selected as the next?hop carrier.Thus，the EDD computation is a key contribution in VADD.

Here，we explain how to compute EDD given the packet’s destination(i.e.，the location of the infrastructure node)along with the vehicular traffic statistics.Fig.2b shows the road net?work graph as an abstract representation for the road network in Fig.2a.This road network graph is a directed graph G=(V，E)，whereVis the vertex set of intersections andEis the directed edge set of road segments.The EDD is computed on the basis of a stochastic model proposed by VADD[4].Let dijbe the expected link delay for edgeeijin(2)，discussed in section 3.1.1.Note thatdijmeansE[dij]in(2)for the simplic?ity of notation.LetDijbe the EDD at the intersectioniwhen a packet is delivered over the edgeeij.The EDDDijis form?ulated recursively as follows:

whereN(j)is the set ofj’s adjacent intersections.This recur?sive formation is reasonable because the packet delivered over edgeeijarrives at intersectionjand it is is forwarded to one ofj’s adjacent intersections，denotedk，with probabilityPjkand the EDDDjk.Refer to TBD in[1]for the detailed comput?ation of the average forwarding probabilityPjk.

Fig.3shows the EDD computation for edgee9，10where Pac?ket Carrier Candidate is currently moving.The EDD D9，10is computed using(11)as follows: D9，10=d9，10+P10，9D10，9+ P10，2D10，2+P10，11D10，11+P10，17D10，17. Even though VADD solves the data forwarding problem through the linear systems

of recursive equations in(11)，the limitation of VADD does not use the vehicle trajectory available for a better forwarding met?ric computation.In the next subsection，TBD[1]is used to take advantage of vehicle trajectory and improve VADD.

▲Figure 2.V2I data forwarding in road network.

▲Figure 3.EDD computation for Edgee9,10.

4.2 Trajectory-Based Data Forwarding for V2I Data Delivery(TBD)

TBD[1]is a data forwarding scheme to improve VADD for the V2I data delivery，using not only vehicular traffic statistics but also vehicle trajectory in the privacy?preserving manner. As an extreme example，assume that Fig.2b describes the data forwarding in an extremely light?traffic vehicular network so that carrier has onlycar1andcar2as the possible next?hop carriers in this road network.That is，we assume that only these three vehicles exist in the road network.The next?hop carrier candidatescar1andcar2are moving toward intersec?tion 16 and intersection 10，respectively.One difference is that the trajectory ofcar1passes through AP，and the trajectory of car2is far away from the communication range of AP.In this case，car1should be selected by carrier as a next?hop carrier becausecar1will be able to deliver carrier’s packets to AP with a shorter EDD thancar2.In this subsection，we explain how individual vehicles compute their EDD with their own tra?jectory in order to allow for this next?hop selection while they do not expose their own trajectory to other vehicles because of privacy concerns.

The main idea of TBD is to divide the data delivery process into the following two steps:1)The packet carry process at the current carrier and 2)the delivery process after the packet leaves the current carrier.Note that in the case of light?traffic vehicular networks，a vehicle could carry a packet continuous?ly over multiple edges along its trajectory until it meets a bet?ter next?hop carrier.

whereP'jkis the forwarding probability to forward a packet at intersection jto another vehicle moving toward intersection k(computed in(6)in[1])，is the carry probability to ca? rry a packet from intersectionhtoh+1such thatis the EDD at edgeejkin(11).

For example，Fig.4 shows the EDD computation for a pack?et carrier candidate with the trajectory(T:10→11→12). The EDDDis computed by(12)as follows:

Therefore，TBD allows individual vehicles to calculate their own EDD based on their own trajectory so that the packet carri?er can select the best next?hop carrier among its neighboring vehicles.However，TBD is designed for the static packet desti?nation.Thus，when the destination is moving in the I2V data delivery，we need a totally different approach that takes into ac?count the mobility of the destination vehicle.In the next sub?section，we introduce TSF[2]for multihop I2V data delivery.

4.3 Trajectory-Based Statistical Data Forwarding for I2V Data Delivery(TSF)

TSF[2]is a data?forwarding scheme for multihop I2V data delivery，which involves the packet destination vehicle trajecto?ry.Fig.5 shows I2V data delivery from AP1to Destination Vehicle.TSF for I2V has one significant difference from VADD and TBD for V2I in that TSF requires relay nodes at in?tersections as temporary packet holders that are not directly connected to the wired network for the deployment cost reduc?tion.The relay nodes are required for the reliable I2V data de?livery from AP to a destination vehicle so that the delivery de?lay standard deviation is bounded to deliver packets from AP to the moving destination vehicle in a timely manner[2]，[6].

▲Figure 4.EDD computation for vehicle trajectory.

The challenge for I2V is in selecting a target point that cor?responds to a relay node in order to guarantee the rendezvous

of the packet from AP and the moving destination vehicle.In Fig.5，AP1selects intersection 13，denotedn13，as a target point through the current position and trajectory of Destination Vehicle.The current positions and trajectories of vehicles are available to APs via TCC[18]because the vehicles regularly report their current position and trajectory to TCC for the loca?tion management in TCC for the mobile vehicles like in Mobile IPv6[27].Thus，TCC is a home agent in managing the location of vehicles in the similar way with Mobile IPv6 so that APs can get the estimated current position and vehicle trajectory of a destination vehicle from TCC.

In TSF，the target point selection is performed with the fol?lowing two delay distributions:1)Vehicle delay distribution from Destination Vehicle’s current position to a Target Point and 2)Packet delay distribution from AP to a Target Point. Fig.6 shows the packet delay distribution from AP1to target point candidaten13and the vehicle delay distribution from Destination Vehicle’s current positionn10to target point can?didaten13.For each intersection as a target point candidate along Destination Vehicle’s trajectory，we can draw a pair of delay distributions，as in Fig.6.

To optimize delivery，we formulate the target point selection as follows.LetIbe a set of intersections along Destination Vehicle’s trajectory.LetPibe the packet delay from AP to target point candidatei.LetVibe the vehicle delay from Des?tination Vehicle’s current position to target point candidatei. As a target point，TSF selects an intersection to minimize the packet delivery from AP to Destination Vehicle，while satisfy?ing the user?defined delivery probability thresholdα(e.g.，95%)as follows:

In(14)，P[Pi≤Vi]is the delivery probability that the pac?ket will arrive at intersectioniearlier than Destination Vehi?cle.In(14)，E[Vi]is the actual packet delivery delay from AP to Destination Vehicle.This is because the packet held by the relay node at intersectioniis forwarded to Destination Vehi?cle when Destination Vehicle passes through intersectioniaf?terE[Vi].

Given the packet delay distribution and the vehicle delay distribution，the delivery probabilityP[Pi≤Vi]is given by

wheref(p)is the probability density function(PDF)of packet delayp，g(v)is the truncated PDF of vehicle delayvwith the integration upper boundTTLthat is the packet’s Time?To?Live(TTL).Note that since the packet is discarded after TTL，the portion of the delivery probability for vehicle delay vbecomes zero afterTTL.

TSF can be used for the multihop V2V data delivery in the combination of V2I and I2V.That is，Source Vehicle sends a packet to a nearby AP using TSF(or TBD)for V2I data deliv?ery.Source Vehicle regards AP’s intersection as a target point (destination).The AP contacts TCC to locate Destination Vehi?cle and obtains the corresponding trajectory to compute a tar?get point.With the target point，AP sends the packet toward the target point for I2V data delivery to Destination Vehicle.

▲Figure 5.I2V data forwarding in road network.

▲Figure 6.Packet delay distribution and vehicle delay distribution.

TSF can be extended to support multicast from AP to a mul?ticast group vehicles moving in a road network.As a multicast version of TSF，we propose TMA[3].TMA computes the multi?ple target points of multicast group vehicles in the same way

that TSF does.With these multiple target points，TMA con?structs a minimum Steiner Tree for multicast data delivery so that multicast delivery cost can be minimized and multicast da?ta can be more efficiently shared between vehicles in a multi?cast group.

One limitation of TSF is that relay nodes need to be de?ployed as infrastructure nodes for reliable I2V data delivery. In future work，we will develop a data?forwarding scheme that supports both I2V and V2V data delivery without relay nodes and fully utilize the trajectories of vehicles moving in a target road network.In the next section，we analyze three forwarding schemes discussed in this section.

5 Analysis of Forwarding Schemes

Table 1shows a comparison of the VANET data?forwarding schemes VADD，TBD and TSF.VADD and TBD only support V2I，and their target application is road condition reports.TSF supports V2I，I2V and V2V，which means there are more tar?get applications，such as road condition sharing and cloud ser?vices(e.g.，navigation and location?based services).These three forwarding schemes use vehicular traffic statistics for for?warding?metric computation.Except for VADD，the other two schemes TBD and TSF take advantage of vehicle trajectory for more efficient forwarding metric computation.TSF supports the more forwarding types，such as V2I，I2V，and V2V.

All three forwarding schemes require access points for con?nectivity to a wired network，such as the Internet.TSF addition?ally requires relay nodes and traffic control center for reliable multihop I2V(or V2V)data delivery，and protects privacy by not exposing the vehicle trajectories.Thus，for vehicular cloud services through vehicular networks，TSF is recommended be?cause it supports bi?directional data communications between vehicles and infrastructure nodes(e.g.，AP).

In the simulations，we evaluated the performance of VADD，TBD，and TSF in an 8.25 km×9 km road network with 49 in?tersections.The DSRC communication range is 200 m.The ve?hicles move in the road network according to a Hybrid Mobili?ty model of City Section Mobility model[28]and Manhattan Mobility model[29].The simulation configuration can be found in the performance evaluation of TBD[1]and TSF[2].

Fig.7shows the performance of VANET data?forwarding schemes.For multihop V2I data delivery，Fig.7a shows theperformance of TBD and VADD in average delivery delay by the number of vehicles(i.e.，vehicular density)[1].TBD has a shorter delivery delay than VADD from the lowest vehicular density to the highest vehicular density by a more effective de?livery delay estimation using the individual vehicle trajectory. This indicates that TBD provides better V2I data delivery than VADD.For multihop I2V data delivery，Fig.7b shows TSF，Random Target Point(RTP)，and Last Target Point(LTP)[2]. These are different in terms of the target point selection mecha?nism for a rendezvous point of the packet and destination vehi?cle.RTP selects a target point as a random intersection among the intersections along the destination vehicle’s trajectory. LTP selects a target point as the last intersection of the destina?tion vehicle’s trajectory.On the other hand，TSF selects a tar?get point by the optimization in(13)with the packet delay dis?tribution and vehicle delay distribution shown in Fig.6.TSF has a shorter delivery delay than both RTP and LTP by the op?timal target point selection(Fig.7b).Therefore，the vehicle tra?jectory is very important information in the design of the data forwarding schemes for either V2I or I2V data delivery.

▼Table 1.The comparison among VANET data forwarding schemes

▲Figure 7.The performance evaluation of VANET data forwardingschemes.

6 Conclusions

In this paper，we have described TBD and TSF data?forward?

ing schemes based on vehicle trajectory in vehicular networks. The vehicle trajectory is a good asset in the design of data?for?warding schemes for multihop V2I or I2V data delivery be?cause it allows for either better forwarding metric computation or better estimation of the location of the packet destination ve?hicle.In future work，we will investigate more of the character?istics of vehicle trajectory in order to achieve better data for?warding performance，considering the minimization of trajecto?ry sharing overhead and the privacy protection on trajectory.In particular，we will design and implement a new data?forward?ing scheme to support multihop V2I，I2V，and V2V data deliv?ery without any relay nodes to reduce deployment cost.For this new data?forwarding scheme，we will investigate how to fully utilize the trajectories of vehicles moving in a target road net?work.That is，this data forwarding scheme will investigate how to combine packet carrying process and packet forwarding pro?cess by predicting the encounter sequence of vehicles as the forwarding chances between the current packet carrier and next?packet carrier candidates with vehicle trajectories.

[1]J.Jeong，S.Guo，Y.Gu，T.He，and D.Du，“Trajectory?based data forwarding for light?traffic vehicular ad hoc networks，”IEEE Transactions on Parallel and Dis?tributed Systems，vol.22，no.5，pp.743-757，May 2011.doi:10.1109/TP?DS.2010.103.

[2]J.Jeong，S.Guo，Y.Gu，T.He，and D.Du，“Trajectory?based statistical forward?ing for multihop infrastructure?to?vehicle data delivery，”IEEE Transactions on Mobile Computing，vol.11，no.10，pp 1523-1537，Oct.2012.doi:10.1109/ TMC.2011.189.

[3]J.Jeong，T.He，and D.Du，“TMA:trajectory?based multi?anycast forwarding for efficient multicast data delivery in vehicular networks”，Elsevier Computer Net?works，vol.57，no.13，pp.2549-2563，Sept.2013.doi:10.1016/j.com?net.2013.05.002.

[4]J.Zhao and G.Cao，“VADD:vehicle?assisted data delivery in vehicular ad hoc networks，”IEEE Transactions on Vehicular Technology，vol.57，no.3，pp.1910-1922，May 2008.doi:10.1109/TVT.2007.901869.

[5]A.Skordylis and N.Trigoni，“Delay?bounded routing in vehicular ad hoc net?works，”in ACM MOBIHOC，Hong Kong，China，May 2008，pp.341-350.doi: 10.1145/1374618.1374664.

[6]Y.Ding，C.Wang，and L.Xiao，“A static?node assisted adaptive routing protocol in vehicular networks，”in Proc.ACM Int’l Workshop Vehicular Ad Hoc Net?works，Montreal，Canada，Sept. 2007，pp.59- 68.doi: 10.1145/ 1287748.1287758.

[7]G.Dimitrakopoulos，“Intelligent transportation systems，”IEEE Vehicular Tech?nology Magazine，vol.5，no.1，pp.77-84，Mar.2010.

[8]OECD report in 2008.(2010，Aug.26).South Korea's Road Fatality Rate Among Worst[Online].Available:http://english.yonhapnews.co.kr/national/2010/08/26/ 89/0302000 000AEN20100826005300315F.HTML

[9]M.Ferreira，R.Fernandes，H.Conceicao，W.Viriyasitavat，and O.K.Tonguz，“Self?organized traffic control，”ACM VANET，Chicago，IL，USA，Sept.2010.pp. 85-90.doi:10.1145/1860058.1860077.

[10]M.Aoyama，“Computing for the next?generation automobile，”IEEE Computer，vol.45，no.6，pp.32-37，Jun.2012.doi:10.1109/MC.2012.153.

[11]On?Board Diagnostics(OBD)[Online].Available:http://epa.gov/otaq/regs/im/ obd/index.htm

[12]Y.Morgan，“Notes on DSRC&WAVE standards suite:its architecture，design，and characteristics，”IEEE Communications Surveys&Tutorials，vol.12，no.4，pp.504-518，Oct.2010.doi:10.1109/SURV.2010.033010.00024.

[13]ETSI.DSRC Standardization[Online].Available:http://www.etsi.org/technolo?gies?clusters/technologies/intelligent?transport/dsrc

[14]SAE International.(2009).DSRC Implementation Guide[Online].Available: http://www.sae.org/standardsdev/dsrc/DSRCImplementationGuide.pdf

[15]Garmin Ltd.(2012).Garmin Traffic[Online].Available:http://www8.garmin. com/traffic，2012.

[16]Smartphone Navigator.(2011，Jan.14).Apps with Maps:11 iPhone GPS Apps Compared[Online].Available:http://www.macworld.com/article/1156720/gps. html

[17]H.Yomogita.Mobile GPS Accelerates Chip Development[Online].Available: http://techon.nikkeibp.co.jp/article/HONSHI/20070424/131605/

[18]Philadelphia Department of Transportation.Traffic Control Center[Online]. Available:http://philadelphia.pahighways.com/philadelphiatcc.html

[19]A.Abdrabou and W.Zhuang，“Probabilistic delay control and road side unit placement for vehicular ad hoc networks with disrupted connectivity，”IEEE Journal on Selected Areas in Communications，vol.29，no.1，pp.129-139，Jan. 2011.doi:10.1109/JSAC.2011.110113.

[20]J.Jeong，“Vehicle trajectory?based forwarding schemes for vehicular ad hoc networks，”KICS Information and Communications Magazine，vol.29，no.8，Aug.2012.

[21]E.M.Royer and C.?K.Toh，“A review of current routing protocols for ad?hoc mobile wireless networks，”IEEE Personal Communications，vol.6，no.2，pp. 46-55，Apr.1999.doi:10.1109/98.760423.

[22]Machine to Machine(M2M)System Requirements Document(SRD)，IEEE 802.16p?10/0004，2011.

[23]C.D.Monfreid，“The LTE network architecture—a comprehensive tutorial，”Tech.Rep.，2009.

[24]N.Wisitpongphan，F.Bai，P.Mudalige，and O.K.Tonguz，“On the routing prob?lem in disconnected vehicular ad hoc networks，”IEEE INFOCOM，Anchorage，AK，USA，May 2007，pp.2291-2295.doi:10.1109/INFCOM.2007.267.

[25]M.DeGroot and M.Schervish，Probability and Statistics，third ed.Boston，MA: Addison?Wesley，2001.

[26]D.S.Berry and D.M.Belmont，“Distribution of vehicle speeds and travel times，”Proc.Second Berkeley Symp.Math.Statist.and Prob.，Berkeley，CA: Univ.of Calif.Press，1951，pp.589-602..

[27]C.Perkins，D.Johnson，and J.Arkko，Mobility Support in IPv6，IETF RFC 6275，July 2011.

[28]T.Camp，J.Boleng，and V.Davies，“A survey of mobility models for ad hoc net?work research，”Wireless Comm.and Mobility Computing,Special Issue on Mo?bile Ad Hoc Networking:Research,Trends and Applications，vol.2，no.5，pp. 483-502，Aug.2002.doi:10.1.1.13.268.

[29]F.Bai，N.Sadagopan，and A.Helmy，“IMPORTANT:a framework to systemati?cally analyze the impact of mobility on performance of routing protocols for ad?hoc networks，”IEEE INFOCOM，San Francisco，CA，USA，2003，vol.2，pp. 825-835.doi:10.1109/INFCOM.2003.1208920.

Manuscript received:February 20，2014

Biograpphhiieess

Jaehoon(Paul)Jeong(pauljeong@skku.edu)is an assistant professor in the Depart?ment of Software，Sungkyunkwan University，Republic of Korea.He received his PhD degree in computer science and engineering from University of Minnesota，USA，in 2009.He received his BS degree in information engineering from Sung?kyunkwan University，Republic of Korea，and his MS degree in computer engineer?ing from Seoul National University，Republic of Korea.His research interests in?clude vehicular networks，cyber?physical systems，and navigation systems.

Tian He(tianhe@cs.umn.edu)is an associate professor in the Department of Com?puter Science and Engineering，University of Minnesota，Twin Cities，USA.He re?ceived his PhD degree under Professor John A.Stankovic at the University of Vir?ginia，USA，in 2004.He has authored or co?authored more than 90 papers in pre?mier sensor network journals and conferences and has more than 4000 citations. His publications have been selected as graduate?level course materials by over 50 universities in the United States and other countries.

David H.C.Du(du@cs.umn.edu)is the Qwest chair professor in the Department of Computer Science and Engineering，University of Minnesota，Twin Cities，USA.He received his BS degree in mathematics from National Tsing?Hua University，Tai?wan.He received his MS and PhD degrees in computer science from the University of Washington，USA in 1980 and 1981.His research interests include cyber securi?ty，sensor networks，multimedia computing，storage systems，and high?speed net?working.He is a fellow of the IEEE.

This work was supported by Faculty Research Fund,Sungkyunkwan University,2013 and by DGIST CPS Global Center.This work was also partly supported by Next?Generation Information Computing Development Program through the National Research Foundation of Korea(NRF)funded by the Ministry of Science,ICT&Future Planning(No.2012033347)and by the IT R&D program of MKE/KEIT(10041244,SmartTV 2.0 Software Platform).