its routing request contains source si and destination di,where On the other hand,distributed routing makes decision siE V,diV.For road (u,v)EE,M(u,v)denotes the locally.There is no central control unit.so the routes are capacity of (u.v).i.e..maximum number of vehicles available computed locally in the nearby sinks.The dynamic traffic for travelling on it. information available is limited to a small range,e.g.,adjacent In regard to the routing result,the routing guidance system roads.For static traffic information,it can be pre-deployed and will reply to vehicle ci with a route Ri in the form of thus be global.Therefore,distributed route guidance scheme (o,1,,vk）,where vo=si,vk=di and v∈V,j= has a much smaller overhead in storage and computing,and 0...k.If we use Rsd to represent the set of all routes from thus more deployable.However,since it lacks global traffic si to di,then Ri should be in the set Rs.d. information,its solution is more likely to be a local optimum The routing target is to make the overall/average travel time one.This architecture can also be applied to Vehicular Ad of all vehicles to be minimum.So the objective of the route hoc NETworks (VANET)since we can choose any point in guidance problem can be represented as follows. the ad-hoc network as the sink minimize T(Ri) (1) B.Analysis Recall that T()is the key parameter in Eg.(1),in order to measure it,we first explore the travel time a vehicle spends subject to around an intersection.Assume that a vehicle is travelling on Ri∈Rs4,d, (2) road (u,v)and will turn to road (v,w),the time duration has two parts:the driving time D(u,v)and the waiting time (u,)∈E,l{ci:c∈C,(u,v)∈Rl≤M(u,v) (3) W(u,v,w),which is represented as follows, where T()is the time duration of route Ri.The second T((u.v.w))=D(u,v)+W(u.v.w) (4) constraint requires that the traffic flow on each road (u,v) should be no greater than its capacity. D(u.v)= Do(u,v) (5) In order to solve this route guidance problem,in this paper S(u.v) we consider two situations based on the infrastructures in vehicular network:centralized route guidance and distributed In Eg.(4).the driving time refers to the time the vehicle route guidance.In the centralized solution,the routing decision spends on the road without being influenced by other vehicles is made in a central control module and requires global or traffic lights.As shown in Eq.(5),it can be calculated using traffic information.In the distributed solution,there is no distance Do(u,v)and speed limit S(u,v)of road (u,v). central controlling and the algorithm only uses local traffic In regard to the waiting time,we measure it from the number information for route guidance. of red lights the vehicle is expected to wait.According to the assumption,the vehicle is on road (u,v)to (v,w),the number IV.SOLUTION of red lights it has to wait depends on both the set of current vehicles before it,F(u,v.w),and the number of vehicles A.System Architecture which can leave the road during one green light,L(u,v,w). Fig.I shows an example of route guidance system architec- We try to find the upper bound of the waiting time in our ture in vehicular networks.In this figure,the components are measurement as shown in Eg.(6). sinks,vehicle-side sensors and a central control unit.Sinks are usually APs in vehicular network,and as discussed in [21. these sinks keep communicating with sensors in the vehicles W(u,v,w)= F(u,v,w) +1 R(u,v,w) (6) such as GPS,cameras,mobile phones,etc.The central control L(u,v,w) unit will exchange data with sinks,but it will only be used in centralized routing.Within this infrastructure,the real-time L(u.v,w)= Gu,v,四）：S(u,v p(u,Uw)】 (7) traffic data and route requests will be shared,and we can utilize these resources to devise efficient route guidance algorithms. In Eq.(6)and Eq.(7),R(u,v,w)and G(u,v,w)represent the the time of one red light and one green light when turning from Central guidance only road (u,v)to (v,w)at intersection v.l is the sum of both Control Unit (average)vehicle length and the gap between two vehicles. p(u,v,w)denotes the density of vehicles during one green light,which is in the range of 0,1. With Eg.(4).T(Rc)can be measured by adding up the travel time of all road-to-road segments in R.. D ● ■ C.Baseline Routing Algorithm Fig.1:An example of route guidance system architecture in To evaluate the route guidance systems,it is essential to vehicular network construct a baseline routing algorithm whose ability is similar to the routing without any guidance.However,for vehicle set In centralized routing,the central control unit collects traffic C from s to d,simply randomly selecting routes from Rs.d information globally.In this way,not only the static traffic uniformly is not reasonable,since by using experiences or information such as the red light duration time.road length. maps,the majority of drivers'routing decisions without any speed limit,etc..but also the dynamic traffic information guidance are more likely to be around the shortest path. like real-time traffic movements can be used in the routing Based on the above understanding,we propose an improved decision for each vehicle.To handle such large amount of data, random routing algorithm,IRR for short.In IRR,we first the central control unit is expected to have abundant storage choose the shortest path from s to d.From the second path,to resources along with powerful computing devices. mimic the imperfection of human beings,we randomly deleteits routing request contains source si and destination di , where si ∈ V, di ∈ V . For road hu, vi ∈ E, M(u, v) denotes the capacity of hu, vi, i.e.,maximum number of vehicles available for travelling on it. In regard to the routing result, the routing guidance system will reply to vehicle ci with a route Ri in the form of hv0, v1, . . . , vki, where v0 = si , vk = di and vj ∈ V, j = 0 . . . k. If we use Rsi,di to represent the set of all routes from si to di , then Ri should be in the set Rsi,di . The routing target is to make the overall/average travel time of all vehicles to be minimum. So the objective of the route guidance problem can be represented as follows, minimize X ci∈C T (Ri) (1) subject to Ri ∈ Rsi,di , (2) ∀hu, vi ∈ E, |{ci : ci ∈ C,hu, vi ∈ Ri}| ≤ M(u, v). (3) where T (·) is the time duration of route Ri . The second constraint requires that the traffic flow on each road hu, vi should be no greater than its capacity. In order to solve this route guidance problem, in this paper we consider two situations based on the infrastructures in vehicular network: centralized route guidance and distributed route guidance. In the centralized solution, the routing decision is made in a central control module and requires global traffic information. In the distributed solution, there is no central controlling and the algorithm only uses local traffic information for route guidance. IV. SOLUTION A. System Architecture Fig.1 shows an example of route guidance system architec￾ture in vehicular networks. In this figure, the components are sinks, vehicle-side sensors and a central control unit. Sinks are usually APs in vehicular network, and as discussed in [2], these sinks keep communicating with sensors in the vehicles such as GPS, cameras, mobile phones, etc. The central control unit will exchange data with sinks, but it will only be used in centralized routing. Within this infrastructure, the real-time traffic data and route requests will be shared, and we can utilize these resources to devise efficient route guidance algorithms. Central Control Unit Sink Sink Sink centralized route guidance only Fig. 1: An example of route guidance system architecture in vehicular network In centralized routing, the central control unit collects traffic information globally. In this way, not only the static traffic information such as the red light duration time, road length, speed limit, etc., but also the dynamic traffic information like real-time traffic movements can be used in the routing decision for each vehicle. To handle such large amount of data, the central control unit is expected to have abundant storage resources along with powerful computing devices. On the other hand, distributed routing makes decision locally. There is no central control unit, so the routes are computed locally in the nearby sinks. The dynamic traffic information available is limited to a small range, e.g., adjacent roads. For static traffic information, it can be pre-deployed and thus be global. Therefore, distributed route guidance scheme has a much smaller overhead in storage and computing, and thus more deployable. However, since it lacks global traffic information, its solution is more likely to be a local optimum one. This architecture can also be applied to Vehicular Ad hoc NETworks (VANET) since we can choose any point in the ad-hoc network as the sink. B. Analysis Recall that T (·) is the key parameter in Eq. (1), in order to measure it, we first explore the travel time a vehicle spends around an intersection. Assume that a vehicle is travelling on road hu, vi and will turn to road hv, wi, the time duration has two parts: the driving time D(u, v) and the waiting time W(u, v, w), which is represented as follows, T (hu, v, wi) = D(u, v) + W(u, v, w) (4) D(u, v) = D0(u, v) S(u, v) (5) In Eq.(4), the driving time refers to the time the vehicle spends on the road without being influenced by other vehicles or traffic lights. As shown in Eq.(5) , it can be calculated using distance D0(u, v) and speed limit S(u, v) of road hu, vi. In regard to the waiting time, we measure it from the number of red lights the vehicle is expected to wait. According to the assumption, the vehicle is on road hu, vi to hv, wi, the number of red lights it has to wait depends on both the set of current vehicles before it, F(u, v, w), and the number of vehicles which can leave the road during one green light, L(u, v, w). We try to find the upper bound of the waiting time in our measurement as shown in Eq.(6). W(u, v, w) = |F(u, v, w)| L(u, v, w)  + 1 · R(u, v, w) (6) L(u, v, w) = G(u, v, w) · S(u, v) l · ρ(u, v, w) (7) In Eq.(6) and Eq.(7), R(u, v, w) and G(u, v, w) represent the the time of one red light and one green light when turning from road hu, vi to hv, wi at intersection v. l is the sum of both (average) vehicle length and the gap between two vehicles. ρ(u, v, w) denotes the density of vehicles during one green light, which is in the range of [0, 1]. With Eq.(4), T (Rc) can be measured by adding up the travel time of all road-to-road segments in Rc. C. Baseline Routing Algorithm To evaluate the route guidance systems, it is essential to construct a baseline routing algorithm whose ability is similar to the routing without any guidance. However, for vehicle set C from s to d, simply randomly selecting routes from Rs,d uniformly is not reasonable, since by using experiences or maps, the majority of drivers’ routing decisions without any guidance are more likely to be around the shortest path. Based on the above understanding, we propose an improved random routing algorithm, IRR for short. In IRR, we first choose the shortest path from s to d. From the second path, to mimic the imperfection of human beings, we randomly delete