Information Technology Reference
In-Depth Information
Traffic information center
Figure 14.8
Network architecture used in the design and implementation of a vehicle-to-vehicle based
traffic information system.
position and destination position can be represented by the ID of roadside
unit. In the reactive approach, the routing information is generated in an
on-demand fashion. That is, TIC will only calculate the quickest path for a
given source position and a destination position after it receives a navigation
request. The on-demand routing information is usually delivered to the
requesting guided vehicle via unicast delivery. The main problem with the
proactive approach is that a large routing table will be generated because the
total number of all pairs of source position and destination position is large.
For example, if the number of source positions (or roadside units) is
n
= 10
4
,
then the routing table will have
n
2
= 10
8
entries. It is difficult to deliver such
a large routing table to all vehicles. To conquer this difficulty, a hierarchical
addressing scheme can be employed to reduce the size of the routing table
[9]. With hierarchical addressing, a map is divided into several tiers. For
example, the digital map in Figure 14.9 is divided into nine tier-3 zones (i.e.,
A, B, C, …), each of which is divided into nine tier-2 zones (i.e., a, b, c, …).
Each tier-2 zone is further divided into nine tier-3 zones. A routing table
is generated for each tier-3 zone. Each tier-3 zone is covered by a BS. For
example, Table 14.1 shows the routing table for a tier-3 zone “E.e.a”. There
are only 24 entries in the routing table. However, if there is no hierarchical
addressing, the entries in the routing table will be
n
2
, where
n
= 9
3
. Another
common problem with proactive routing is that the computing complexity is
high for finding the quickest path between any two given nodes in a graph.
If the Floyd shortest path algorithm is employed, the
time complexity will be
Θ(
n
3
), where
n
is usually a large number. The main problem with the reactive
