Collecting road traffic information using vehicular ad hoc networks

Road traffic information helps a driver in selecting an appropriate route to the travel destination by avoiding congested road segments. A vehicular ad hoc network (VANET) offers an alternative approach to collect road traffic information without a wired infrastructure and centralized storage. This paper proposes the road traffic collecting (RTC) protocol to gather road traffic information in a VANET on city roads. The key protocol operation is the query dissemination that steers a query message over a set of predefined routes towards the destination location. To collect road traffic information, nodes participating in the query dissemination include their own velocity to the query message so that congestion information on different positions of road segments is gathered. A node nearest to the destination that receives the query message returns the query reply containing road traffic information of the forward route back to the source. Unlike existing broadcasting and geocasting protocols, our proposed protocol uses the message exchange pattern that increases the reliability of query delivery under a collision channel. The simulation on a large network with high vehicle densities and simultaneous query sessions is conducted to evaluate the protocol performance in terms of the percentage of road segment coverage and the query response time under the presence of MAC layer collisions. The results show that RTC can collect 100 % of road traffic information over a set of predefined routes under a few number of parallel query sessions while an existing protocol that mainly uses a broadcast message can achieve only 40–70 %. For a large number of query sessions, RTC achieves 65–80 % of target road segments depending on the vehicle density with the average query time bounded to a few seconds.

Providing road traffic information to drivers can help improve the traffic flow and reduce the traveling time. For example, a driver can choose a less congested route to the destination or avoid routes with an accident. Currently, road traffic information is primarily collected by fixed traffic sensors such as inductive loop detectors and electromagnetic detection systems [1, 2] or by estimating from location data in on-board mobile phones [3]. The gathered data is then relayed to a central server via a cellular network or a wired network infrastructure for later user access. However, installed road sensors may not cover an area of interest due to cost and installation constraints. These approaches also require that each road sensor or mobile phone has the Internet connection to relay collected traffic information to the central server.

A vehicle ad hoc network (VANET) is a wireless ad hoc network formed by vehicles, allowing data exchanges among nodes in a multi-hop fashion without the assistance of a wired infrastructure. One or more nodes connecting to a wired network infrastructure can act as a gateway for the rest. A majority of VANET applications stems from an intelligent transportation system for safety and road traffic management. Safety applications aim to avoid the chance of accidents by disseminating warning information such as accidents or hazardous road conditions to a large number of vehicles. Road traffic management applications are used to improve traffic flow and provide traffic information to drivers to reduce the traveling time. For example, a user may query for road traffic conditions by enquiring nodes in relevant road segments to decide on a route with the lowest traveling time.

Safety applications in a VANET rely on broadcasting to disseminate information such as a warning message from a single vehicle to others within a limited distance from the source node [4–8]. Alternatively, the source node can use geocasting, which is similar to broadcast routing except that receiving nodes and/or forwarding nodes are confined to a specific region [9, 10].

This paper considers the problem of collecting road traffic information in a VANET whereby a source node acquires traffic congestion information along several routes to a given destination, possibly to aid the route navigation decision. Broadcasting and geocasting techniques are designed to disseminate information to all nodes in a given area. In collecting road traffic information, a query message must be disseminated over routes of interest and traffic information is cumulatively added to the query message to be later returned to the source. Such query dissemination requires reliable delivery, and a mechanism for intermediate nodes to return the queried information to the source is needed. In a realistic scenario, the reception of broadcast messages suffers from collisions caused by the hidden node problem, and the proportion of delivery failures can become significant with an increasing amount of interfering traffic. Therefore, existing broadcasting and geocasting protocols must be extended to collect road traffic information with a better reliable message delivery mechanism.

The research contributions of this paper are twofold. First, we propose a road traffic collecting protocol where a source node disseminates a query message into the network to determine road traffic information along predefined routes towards the destination location. The protocol extends upon existing broadcasting and geocasting protocols in the literature to provide a more reliable query delivery under a collision channel, the critical issue which has not been seriously accounted for in previous works. The proposed protocol also has a mechanism to handle the query dissemination over intersections and to steer a query message along the predefined routes. Second, the performance evaluation of our proposed work is extensively evaluated under a large-scale network with multiple query sessions where traffic of different users can collide and with node mobility. Under such circumstances, our protocol shows superior results compared to an existing work in terms of the percentage of road segment coverage at the expense of higher number of transmissions.

The paper is organized as follows. In Section 2, existing VANET broadcasting and geocasting protocols are reviewed. Their limitations and issues when being used for collecting road traffic information are discussed. In Section 3, we propose the protocol for query dissemination to gather road traffic information over road segments of interest in a VANET. The performance evaluation of the proposed protocol with simulation in a large and dense network with multiple query sessions is presented in Section 4. The conclusion is offered in Section 5.

In this section, existing broadcasting and geocasting protocols in a VANET are reviewed. Then, we discuss their limitations and issues when applying them to road traffic collection.

2.1 Broadcasting protocols

In a VANET, a broadcasting protocol is designed to disseminate information such as a warning message of accidents or critical events to other nodes around the source node. One key design aspect of broadcasting protocols is the selection of the rebroadcast node. Most VANET broadcasting protocols attempt to select the rebroadcast node farthest from the current node to rebroadcast. One approach is the current node sending out a probe packet to choose the next rebroadcast node, which requires four broadcast transmissions per hop [4, 5]. The four broadcast messages include (i) the probe packet, (ii) the response to the probe packet, (iii) the data message, and (iv) the acknowledgement of the data message. In urban multi-hop broadcast (UMB) [4], upon receiving the probe packet, each node sends a jamming signal whose duration is proportional to its distance to the current node. The jamming signal from the farthest node thus lasts the longest and only its responding message gets to the current node. The current node then broadcasts a data message that includes the selected node id. The problem is that the jamming signal unnecessarily causes interference that definitely reduces an already limited wireless channel capacity. In addition, the responding delay can be high because of the waiting time for the longest jamming signal to finish. Smart broadcast (SB) [5] and efficient directional broadcast (EDB) [6] reduce the responding delay by making the farthest node respond to the probe packet first. Basically, each node postpones its response to the probe packet by the amount of time inversely proportional to its distance from the sender. In SB, a road segment is divided into sectors and each node uses the number of sectors from the current node to compute the waiting time before responding to the probe packet. EDB uses only the distance from the current broadcast node to compute the waiting delay. The combined technique of UMB and SB is proposed in time-slotted multi-hop transmission (TSM) [11]. In TSM, a road segment is divided into sectors and each sector selects the leader node by using information from periodic beacon messages. Only the leader node can be a relay node. The jamming signal is used to prevent an interference of periodic beacons.

The selection of rebroadcast nodes can be performed in a distributed manner, in which case only one transmission is required per broadcasting hop [7, 8, 12, 13]. When two or more nodes attempt to rebroadcast the same message, they cancel their pending rebroadcast schedules if the message has been broadcast by another node. In weighted p-persistence protocol [7], each node waits a certain time period and rebroadcasts a message with probability proportional to the distance from the current broadcast node and how many times it has received that same broadcast message. The network density and node speed are used by irresponsible forwarding (IF) [8] and speed adaptive probabilistic broadcast (SAB) [13] to adjust the rebroadcast probability, respectively. Particularly, a node is less likely to rebroadcast under a dense network [8] or if it is not moving fast [13]. In slotted 1-persistence protocol [7], each node calculates the waiting time based on the distance from the sender, the number of slots in the communication range, and the slot size such that a node in a closer slot to the sender waits longer. In distributed optimized time (DOT) [12], each node maintains a one-hop neighbor position table constructed by using periodic beacon messages received from its neighbors. When a node receives a broadcast message, it computes the waiting time before rebroadcasting based on its distance from the sender compared to those of its neighbors.

2.2 Geocasting protocols

Geocasting is similar to broadcasting except that it defines an area of target receiving vehicles as well as forwarding vehicles. For example, an alert message for an accident should be propagated only in the proximity of the accident location. Inter-vehicular geocast protocol (IVG) [9] is designed to disseminate an alert or warning message from a crashed vehicle to vehicles in zone of relevance (ZoR), which is defined by a vehicle position and a movement direction. In other words, only a vehicle moving forward to the crashed vehicle is a target of the warning message. The next node selection criteria to geocast are based on the distance similar to EDB [6].

In addition to ZoR, the concept of zone of forwarding (ZoF) is defined in [10] to handle the case when the geocast source itself is in the ZoR. A ZoF defines an area in which vehicles are eligible to participate in message forwarding. Distributed robust geocast protocol (DRG) is proposed to route a geocast message over ZoF to ZoR with the waiting delay similar to EDB [6] except that a node repeats its broadcast if it does not hear the next rebroadcast. Both PREemptive algorithm for DAta Transmission (PREDAT) [14] and Data dissemination pRotocol In VEhicular networks (DRIVE) [15] define a so-called sweet spot area around the current sender such that nodes within the sweet spot have a shorter waiting time before rebroadcasting than those not in the sweet spot. PREDAT uses a periodic beacon to inform the broadcast sender that the sender message has been received. In case of a disconnected network, a node stores a message for later transmission when detecting the beacon.

The closet works to ours are in [16, 17] where many vehicles collect their congestion indices [16] or travelling times [17] on road segments and return them to a single-source vehicle to determine the path with shortest travelling time or least traffic congestion to a destination. Essentially, a source vehicle specifies routes of interest and broadcasts a query message. Each node in the routes of interest rebroadcasts the query at most once and keeps the reverse path entry to its immediate query sender. Each node then unicasts its congestion index or traveling time over the current road segment back to the source vehicle. So, the source vehicle can estimate the average congestion index or average travelling time of individual road segments and determine the best path. In [16], a node also caches the congestion index in a received unicast response message to prevent unnecessary rebroadcasts. Since all nodes must return the information directly to the source, the amount of overheads and collisions can become significant especially under a lots of query sessions or user traffic.

2.3 Discussion

Table 1 compares the protocols discussed previously in terms of the forwarding strategy, the number of messages used per hop, the simulated scenarios, and the assumptions. Most protocols are designed for disseminating information except [16, 17], which are designed to collect information. For the forwarding strategy, most protocols are distanced based in the sense that the waiting time before rebroadcasting is inversely proportional to the distance or the number of slots from the sender. For probabilistic rebroadcasting, the probability of rebroadcasting can be computed from the node speed [13], the distance from the sender [7, 8], and the node density [8]. PREDAT [14] also uses a probabilistic rebroadcast after the node has experienced a disconnected network. For the number of messages transmitted per hop, a majority of the protocols uses a single broadcast message, with IVG [9] and DRG [10] detecting rebroadcast by overhearing. Two messages per hop consisting of a broadcast message and a unicast reply are used by [16, 17], three messages per hop with periodic beacons are used in [11], and four messages per hop are used in [4, 5] but all of them are broadcast. Interestingly, all works except [4, 6, 11, 17] evaluate the performance only in a single query session and in a small network environment. As such, their performances under a high network collision as well as a large network need an investigation. The assumptions indicate whether a GPS device, a digital roadmap, or a road-side unit (RSU) is used in the protocols.

In the context of the road traffic collecting problem, the major issue that has not been sufficiently addressed by existing broadcasting and geocasting protocols is the reliable delivery of a message. Even though most of them are designed to avoid simultaneous broadcast transmissions by applying the waiting delay before rebroadcasting, the broadcast message reception can fail due to the hidden node problem. The sender can repeat its broadcast message if it does not hear a rebroadcast by another node as in IVG [9] and DRG [10], or if it does not receive an acknowledgement as in EDB [6], Geocache [16], and the work in [17]. UMB [4] and SB [5] use four messages in each hop, including the probe message, the probe acknowledgement, the data message, and the data acknowledgement, all of which are broadcast. Nevertheless, the broadcast sender may not hear the rebroadcast message or the acknowledgement because of a collision such that it could end up repeating the broadcast of the same message many times. Also, the larger the broadcast message, the more collisions it suffers when the network load increases. Our proposed protocol in the next section is designed to effectively disseminate a query message in a road network with intersections and in the presence of collisions. The proposed protocol broadcasts only a small probe message to increase the chance of successful reception of potential next rebroadcast nodes and a data message is then unicast. The protocol uses unicasting based on the RTS/CTS mechanism so that message collisions from the hidden node problem are alleviated.

3.1 Model

We consider a city-environment VANET application whose goal is to enable a source vehicle to collect road traffic congestion information such as average vehicle speeds on road segments along one or more routes from itself to a specified destination location. The following information is assumed known to each node—its position and velocity, and the road network topology with detailed road segments and intersections. All nodes have the same transmission range, and each node can communicate with those within its transmission range.

The concept of zone of query, based on zone of forwarding (ZoF) in [18], is defined below for the purpose of query dissemination over routes of interest.

Definition 1 (Zone of query (ZoQ)).

Let L _s =(x _s ,y _s ) be the coordinate of the source node location and L _d =(x _d ,y _d ) be the coordinate of destination location. Define \(d(\boldsymbol {L}_{s},\boldsymbol {L}_{d}) = \sqrt {(x_{s}-x_{d})^{2}+(y_{s}-y_{d})^{2}}\) as the euclidean distance between L _s and L _d , and x _c =(x _s +x _d )/2, y _c =(y _s +y _d )/2. Then, the zone of query is defined by \(Z(\boldsymbol {L}_{s},\boldsymbol {L}_{d},\delta) = \{(x,y)\ | \ \sqrt {(x-x_{c})^{2} + (y-y_{c})^{2}} < (1+\delta)\frac {d(\boldsymbol {L}_{s},\boldsymbol {L}_{d})}{2} \}\), where δ is called the ZoQ extension factor.

An example of ZoQ is illustrated in Fig. 1. The ZoQ extension factor allows queries to propagate on roundabout routes that possibly have a lower road traffic congestion. Given the locations of the source node and the destination, each node in the network can determine the ZoQ of the query and decides if it should involve in the query forwarding.

Zone of query. For a given source node at L _s and destination at L _d , the ZoQ is a circular area whose diameter D is d(L _s ,L _d ) scaled by (1+δ) to allow roundabout routes. Nodes outside a ZoQ ignore a query

Full size image

The road network is modelled by a directed graph where a vertex u represents an intersection or a junction, and an edge e=(u,v) represents a road segment, with u being the emanating vertex of e and v being the incident vertex of e.

For a given ZoQ Z(L _s ,L _d ,δ), we define a subgraph \(\mathcal {G}(Z) = (\mathcal {V}(Z), \mathcal {E}(Z))\) from the road network graph derived from a ZoQ. \(\mathcal {V}(Z)\) is the set of vertices whose coordinates are in Z(L _s ,L _d ,δ) and \(\mathcal {E}(Z) = \{(u,v) \ | \ u,v \in \mathcal {V}(Z)\}\). Because it is wasteful of resources and unnecessary to collect road traffic information in all road segments in \(\mathcal {G}(Z)\), the road traffic information collecting is restricted to segments on a few shortest paths on \(\mathcal {G}(Z)\), referred to as target road segments. This approach enables the use of source routing to prevent routing loops and limits the amount of packets. The effectiveness of our proposed data collecting protocol is evaluated by the amount of target road segment coverage and the time taken to reach a high percentage of target road segments.

We propose the RTC protocol to collect road traffic information on target road segments from a source node to a destination location. The key operation of the RTC protocol is query dissemination, which spreads copies of the query message to collect road traffic information on the target road segments. Once the query message has reached the destination location, the closet nodes to the destination location returns the query message to the source node. Query dissemination and query reply operations in RTC are described next.

3.2 Query dissemination

Our query dissemination extends upon the most forward-routing technique [6, 7, 19] to improve a message delivery reliability along a ZoQ. Initially, the source node creates a traffic collecting (TC) message for a selected destination location that contains the following information:

• Source node id S _id .

• Query sequence number S _n .

• Coordinate of the source node L _s =(x _s ,y _s ) and the coordinate of destination location L _d =(x _d ,y _d ).

• Set of target road segments \(\mathcal {E}_{T}\).

• Set of 0–1 flag variables \(\mathcal {F} = \{F_{e}\}, e=1,2, \ldots, |\mathcal {E}_{T}|\) to indicate whether the query has been over road segment \(e \in \mathcal {E}_{T}\).

• Road traffic information: a set of tuples \(\mathcal {I} = \{(v_{j},\boldsymbol {L}_{j})\}\) of all nodes j that forwards this TC message, where v _j is the velocity of node j and L _j is the position of node j when receiving the TC message from the previous forwarding node. This set is initially empty and grows as the query is forward in the network.

The triplet 〈S _id ,S _n ,L _d 〉 forms a unique identifier of the query session, enabling duplicate query detection. The source node first initializes itself as the current forwarding node of the query session and performs a single-hop broadcast¹ of a neighbor probing (NP) message to find the next forwarding node. The NP message contains all items in the TC message except road traffic information {(v _j ,L _j )}.

The steps for query initiation are given in Algorithm 1 below. If the source cannot find the next forwarding node, the query is declared failed. Otherwise, the source waits for a predefined time period to gather information in query reply messages.

3.2.1 Selection of next forwarding node

After broadcasting the NP message, the current forwarding node waits for acknowledgement from its neighbors within a timeout period T _np and retries for a few times with a back-off period if no acknowledgement was received. The current forwarding node unicasts the TC message to a neighbor whose acknowledge is received first, which becomes the next forwarding node. For all subsequent acknowledgements received, the current forwarding node sends back the TC message only if the acknowledgement comes from the first forwarding node selected.

The situation becomes complicated when the query approaches an intersection as several next forwarding nodes can be expected based on the target road segments. If the current forwarding node is near an intersection, nodes from different road segments may acknowledge and the TC message can be passed to several next forwarding nodes. Consider the situation in Fig. 2 where N ₁ on road segment A is the current forwarding node with N ₂ (road segment A) and N ₄ (road segment C) in its communication range but not N ₃ (road segment B). In this case, N ₁ will receive acknowledgement of the NP message from both N ₂ and N ₄ but not from N ₃. The rule is that N ₁ must return the TC message to nodes in the other road segments with the corresponding flag variable F _i in the TC message set to one to indicate that the current road segment has already been visited. N ₁ must also return the TC message to N ₂ which is the node in the same road segment. If N ₁ ignores the acknowledgement from N ₂, the query will not be able to reach N ₃ because it is out of N ₁’s communication range. When N ₂ subsequently broadcasts an NP message, N ₄ will see this NP message as a duplicate and just ignores it while N ₃ will acknowledge the NP message.

Example when the query approaches an intersection as several next forwarding nodes can be expected. Vehicle N ₂ and N ₄ are selected as the next forwarding nodes by N ₁. Vehicle N ₃ is selected as the next forwarding node by N ₂ in a later NP message broadcast

Full size image

The steps for the next forwarding node selection are given in Algorithm 2 below. The current forwarding node includes the set of target road segments \(\mathcal {E}_{T}\) and the set of corresponding flag variable \(\mathcal {F}\) to indicate segments with traffic information already collected. The number of retries before giving up is set to 6. Only the first NP acknowledgement message from each different segment will trigger the TC message transmission, so does acknowledgements coming from nodes to which TC messages have already been sent.

3.2.2 Response to neighbor probing message

How nodes acknowledge the NP message is critical to the query dissemination because it controls how queries are spread to different road segments in the network. A node is eligible to acknowledge the NP message if none of the following conditions is met:

Non-target road segments. The node locates in a road segment \(e \notin \mathcal {E}_{T}\). This condition ensures that the query will be disseminated only in the target road segments.

Already visited road segments. The node is on one of the already visited road segments listed in the NP message.

Duplicate query. The NP message is for the query session 〈S _id ,S _n ,L _d 〉 that matches one of those in its cache. That is, the node has seen this query message before.

Not closer position. The current forwarding node is on the same road segment as itself and is closer to the destination location. For example, two nodes behind node S with the same moving direction as S in Fig. 3 a will not respond to the NP message because the current forwarding node is closer to the destination location than themselves.

Opposite lane. The node moves in the opposite direction to the current forwarding node. For example, nodes N ₃, N ₄, N ₅, and N ₆ in Fig. 3 a do not respond to the NP message from node S. In Fig. 3 b, nodes N ₄−N ₁₀ do not respond to the NP message.

Different scenarios for nodes to return acknowledgement for the NP message. a Only N ₁ and N ₂ return acknowledgement to the NP message from S. b N ₁−N ₃ are selected as the next forwarding nodes in other segments when the query reaches the intersection. Nodes in segments B, D, F, and G do not respond to the NP message from S

Full size image

To achieve the most forward-routing behavior in query dissemination, each eligible node to acknowledge the NP message waits for the delay t _w inversely proportional to its distance from the current forwarding node before returning acknowledgement:

where T _max is the maximum delay time or the neighbor response timeout, d is distance to the current forwarding node, and R is the transmission range. Because a more distant neighbor has a shorter waiting time, it should return the acknowledgement message earlier and be selected as the next forwarding node. It will then receive the TC message from the current forwarding node.

Other neighboring nodes in the same road segment overhearing the ACK message cancel their ACK transmission if they are still in the waiting duration. If their ACK messages have already been queued in the MAC layer, they will eventually be transmitted but ignored by the current forwarding node. When a node receives the TC message or overhears the ACK message of others, it caches the query identifier 〈S _id ,S _n ,L _d 〉 so that further NP messages for this query session are treated as duplicates.

3.2.3 Query reply

Query replying is initiated when the current forwarding node is closet to the destination location or the query cannot go further due to a disconnected path. Essentially, the query reply (QR) message contains traffic information collected in the received TC message. The current forwarding node knows that it is the closet node to the destination location if the destination location is within its transmission range and there is no acknowledgement for the NP message. The network disconnection is concluded if the destination location is not in the transmission range and no acknowledgement is received after a number of NP message retransmissions.

When the node decides that it should return the QR message based on the above two conditions, the road segments marked in the received TC message are used to form the returning route to the source node. Most forward routing similar to the query dissemination is used except that intermediate nodes not on road segments in the returning route do not participate in the routing. Note that the source node can receive multiple QR messages for each query it has initiated because the query traverses multiple routes to the destination. For each QR message received, the source node will obtain road traffic information on more target road segments. We will show later in the simulation that the source node may terminate the query session either after a few seconds or around ten or more QR messages have been received.

The details of message handling in RTC protocol are given in Algorithm 3 below. All nodes must execute RTCMessageHandling in the background to handle NP messages. The cache \(\mathcal {C}\) to keep track of sessions the node has seen is initially empty. A node receiving an NP message may acknowledge several times in case the NP message sender did not receive acknowledgement due to channel collision and rebroadcast the NP message. If the node is chosen as the next forwarding node, it executes NextForwardSelection() to continue to query dissemination. It will return the query reply message to the query source if it fails to find a next forwarding node.

4.1 Simulation model

The proposed RTC protocol is evaluated by simulation written in OMNet++ version 4.5 with INET framework version 2.4. For the sake of compatibility to INET framework, Simulation of Urban Mobility (SUMO) version 0.15.0 and Vehicle in Network Simulation (Veins) for INET framework are used to create the road topology and vehicle mobility. All nodes have the same transmission power of 2 mW with IEEE802.11g interface. The two-ray ground propagation model with the path-loss exponent 4.0 is used. These parameters result in the node transmission range of 153.4 m. We slightly modified the MAC layer to make a node overhear a unicast acknowledgement to the NP message of other nodes so that it can cancel its acknowledgement during the query dissemination phase.

For each query session, one vehicle is randomly chosen as the source node and one intersection is randomly chosen as the destination location, where the source node and the destination location are forced to be in different road segments. Each source node initiates the query and waits for its own query reply messages. The simulation terminates when no neighbor probing or traffic collecting message exists in the network.

The simulation parameters are summarized in Table 2. Both static node and mobile node scenarios are considered. The static node scenario with a single query source aims to verify the protocol correctness in an ideal situation where the network is connected. The mobility parameters are set based on an experiment in [20] that studies fuel consumption, average speed, average acceleration, and average deceleration of vehicles in Bangkok, Thailand.

The following performance measures are considered:

• Percentage of target road segment coverage: The ratio of the number of road segments traversed by the query message of the RTC protocol and the total number of target road segments \(\mathcal {E}_{T}\).

• Query response time: The time taken from the query message has been sent by a source until the time of the last query reply message received by the source node.

4.2 Experimental setup

We are interested in the RTC performance under a connected network and how the protocol scales in a large network. Therefore, the effects of the following factors are studied—the network size, the node density, and the number of query sessions. The setting of each factor is described below.

Network size. Two sizes of a grid network are used— 4×4 km² (small network) and 8×8 km² (large network) as shown in Fig. 4. Each road segment is 1 km long and has four lanes, two in each direction.

A simulated network size. a Small grid network (4×4 km²). b Large grid network (8×8 km²)

Full size image

Node density. With a 1-km road segment and the node transmission range of 153.4 m (computed from the transmission power and the path-loss model), the node density should be greater than\(\frac {1000}{153.4} = 6.5\) vehicles/km/lane. To be conservative, the range of node density is set between 10 and 25 vehicles/km/lane, or equivalently to 40 and 100 vehicles/km for a 4-lane road segment. From the node density, the total number of vehicles is computed and OMNet++ uses SUMO to evenly distribute vehicles over the road network so that the network is connected under a static scenario. The total number of vehicles ranges from 1600 to 4000 in the 4×4 grid network and from 5760 to 14,400 in the 8×8 grid network. SUMO has a built-in mechanism to prevent nodes from being placed too close to each other depending on the node velocity parameter.

Number of query sessions. For multiple query sessions, we attempt to place query sources throughput in the network by allowing only one source node in each segment. In each query session, the source node and the destination location are randomly placed in the road network with the condition that they must be in different segments. This source and destination placement yields the average route distance of 15.8 and 18.1 km in the 4×4 and 8×8 networks, respectively. With the network topology simulated, the 4×4 grid network allows at most 40 query sessions while the 8×8 grid network allows at most 144 query sessions. So, we set the number of query sessions to 1, 10, and 20 in the small network and 18, 36, and 54 in the large network.

The simulation of each factor level combination described above is repeated for five runs, and the average of performance measures is computed with 95 % confidence interval shown whenever possible.

4.3 Simulation results

Static node scenario. The percentage of target road segment coverage versus the vehicle density is shown in Fig. 5 a. At a single query session, RTC can collect traffic information of all road segments with no NP message acknowledgement timeout. At 10 and 20 query sessions in the small network, the percentage of road segment coverage drops from 97 to 85 % irrespective of the number of query sessions, dropped to around 80 % in the large network.

Simulation results for static node scenario. a Average percentage of target road segment coverage, b average number of NP message acknowledgement timeouts, and c average query response time

Full size image

We found that unsuccessful query dissemination in most segments occur because of the NP message acknowledgement timeout. Because nodes are evenly placed to guarantee the connectivity, the NP message acknowledgement timeout is only caused by NP message collisions among query sessions. The number of NP message acknowledgement timeouts in Fig. 5 b directly relates to the percentage of target road segment coverage and the number of query sessions for both small and large networks. As the NP messages are broadcast, they are more susceptible to collisions than the acknowledgements and the TC messages which are unicast. More query sessions lead to more NP message collisions, causing nodes to give up before the query reaches the destination location. More vehicles also lead to more NP message collisions because different query sessions tend to have different relay nodes contending for the channel.

The average query response time shown in Fig. 5 c is counter-intuitive because it decreases as the node density increases in both small and large networks. Because the waiting time before returning the NP message acknowledgement is inversely proportional to the distance from the current forwarding node, the farthest neighbor has the lowest waiting time. At a higher node density, there exist nodes closer to the transmission range boundary of the current forwarding node, resulting in a lower acknowledgement delay seen by the current forwarding node. The query response time for both small and large networks are nearly the same because of the small difference of the average route distance of both network sizes (15.8 km for the 4×4 network and 18.1 km for the 8×8 network).

Query session termination. In the simulation, we use global information about messages in the network to decide when each query session ends, i.e., no message associated with the query session exists in the network. However, RTC itself does not have such information and cannot indicate when to terminate the query session. Also, it is not possible for RTC to know when the last QR message will be returned. To deal with this issue, we examine how the percentage of target road segment accumulates as more QR messages are received. Figure 6 shows the percentage of road segment coverage as more QR messages are received, where each data point is averaged from all the node densities and the number of query sessions simulated. Each QR message returned provides additional information on different road segments and hence a higher percentage of road segment coverage. Early QR messages provide a significant amount of information while later QR messages only provide marginal information. Based on this result, we may terminate a query session after 15 QR messages have been received or the desired percentage of road segment coverage, say 95 %, has been reached. The query response time in Fig. 5 c suggests that the query timeout of 2.5 s would also be an appropriate choice to terminate the query session.

Average percentage of target road segment coverage versus number of query reply messages received by the source

Full size image

Mobile node scenario. The mobile node scenario is simulated with the same set of parameters in Table 2 as the static node scenario. As shown in Fig. 7, the node mobility apparently affects the percentage of road segment coverage and the number of NP message acknowledgement timeouts. Unlike the static node scenario where the NP message acknowledgement timeout is only caused by excessive message collisions because we evenly place vehicles to guarantee a connected network, the NP message acknowledgement timeout under the mobility scenario is caused by both excessive NP message collisions and a disconnected network due to mobility. We found that at the lowest vehicle density simulated (40 nodes/km), vehicles tend to clutter at intersections and thus the network disconnection is more likely. As the vehicle density increases, the network becomes more connected and hence less NP message acknowledgement timeouts and better percentages of road segment coverage. As the vehicle density gets too high, different query sessions tend to have different relay nodes in the query path, which induce more message collisions.

Simulation results for mobile node scenario. a Average percentage of target road segment coverage, b average number of NP message acknowledgement timeouts, and c average query response time

Full size image

4.4 Comparison to existing work

To demonstrate the advantage of a reliable message delivery provided by RTC, we compared RTC to DRIVE [15], one of the recent geocasting protocols. Similar to RTC, DRIVE can handle intersections in the network without using periodic beacons or road-side units. However, since its operation mainly uses broadcast messages, the comparison with DRIVE will clearly demonstrate the advantage of providing reliable delivery in RTC. We implement DRIVE and run it to disseminate a query message to the destination location and compare the percentage of road segment coverage, the average query response time, and the average of messages transmitted. Each set of parameters is run for five times and the average is taken. The simulation parameters in Table 2 are used except the network size is a 4×4 grid network with node density of 80 vehicles/km and four-lane road segments. The number of query sessions varies from 1 to 5 sessions to investigate the effect of interfering traffic among sessions.

Figure 8 a shows that RTC can cover more than 97 % of targeted road segments for all query sessions simulated while only half of the road segments can be covered by DRIVE at five parallel query sessions. The road segment coverage by DRIVE dramatically drops when the number of query sessions increases because DRIVE suffers from message collisions. At one query session, DRIVE can cover about 70 % of the targeted road segments on the average, with a large error variance. After examining the results, we found that at an intersection, the node in one road segment hearing a rebroadcast from a node in another segment will cancel its broadcast because it does not distinguish a message from a different road segment.

Comparison of RTC and DRIVE [15] in the 4×4 grid network. a Average percentage of target road segment coverage, b average query response time based on the last QR message received, and c number of transmitted messages

Full size image

Figure 8 b shows the average query response time based on the last QR message received. RTC has the average query response time slightly increasing with the number of query sessions, which is consistent with the number of transmitted messages in Fig. 8 c. Because the query disseminations in DRIVE were terminated before covering all of the selected road segments, its average query response time is much lower. Also, because DRIVE uses a single broadcast message in each hop, the average number of transmitted messages is much smaller at the expense of the a less percentage of road segment coverage.

This paper proposes the RTC protocol in a vehicular ad hoc network for traffic collection over road segments on routes from a source node to a destination location. The novelty of the proposed protocol lies in the message exchange sequence to increase the chance of successful delivery under the presence of collisions at the sender and the receivers due to the hidden node problem. Instead of broadcasting a relatively large message which is prone to collisions, we use a small probe message to increase the chance of reception in the presence of collisions. Then, unicast transmissions for both acknowledgement and data delivery are used to ensure that the sender is aware of the next rebroadcast node, rather than relying on the overhearing of the next rebroadcast or an explicit broadcast acknowledgement, which could be lost. The zone of query is first defined based on the source node and destination location, and the query message is disseminated over the zone of query to collect traffic information during the forward path propagation. The query message carrying the road traffic information will be returned by a nearest node to the destination location. Extensive simulation experiments in a large grid network of 64 km² with more than 50 simultaneous query sessions show that RTC can collect around 80 % of target road segments with the query response time bounded to a few seconds. With node mobility, the percentage of road segment coverage varies between 65 and 80 % for a large number of query sessions depending on the vehicle density. It was found that at a small vehicle density, the network disconnection caused by nodes cluttering at intersections disrupts the protocol operation. A mechanism to deal with network disconnection can be used to improve RTC, which is left for future work.

¹ In the rest, the term broadcast means single-hop broadcast unless stated otherwise.

This research is supported by the Thailand Research Fund (TRF) through the Royal Golden Jubilee Ph.D. program under grant no. PHD/0309/2552. A preliminary version of this work was presented at ICSEC 2013.

Authors and Affiliations

1. Department of Computer Engineering, Faculty of Engineering, King Mongkut’s University of Technology Thonburi, Pracha-Utit Rd., Bangkok, 10140, Thailand

   Singha Wongdeethai & Peerapon Siripongwutikorn

Corresponding author

Correspondence to Singha Wongdeethai.

Competing interests

All right and ownership of this research work belong to the Thailand Research Fund. Any commercial profit from outcomes of this research is shared among the Thailand Research Fund and the authors.

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Reprints and permissions