Joon Yoo
School of Computing, Gachon University, 1342, Sujeong-gu, Seongnam-daero, Seongnam-si 13120, Republic of Korea
Mathematics 2023, 11(21), 4426; https://doi.org/10.3390/math11214426Submission received: 29 August 2023 / Revised: 19 October 2023 / Accepted: 24 October 2023 / Published: 25 October 2023
Vehicular ad hoc networks consist of self-organizing nodes using multi-hop wireless links for communication without any infrastructure support. Traditionally, ad hoc routing protocols use the minimum hop count for their routing metric since a smaller number of transmissions is typically equivalent to a higher throughput, lower delay, and minimal power consumption. However, with the muti-rate capability of emerging radio interfaces, e.g., 802.11ax/be standards, the min-hop metric no longer results in high throughput. For instance, if the higher data rate links are selected for the route, it could result in a higher throughput even if the route takes more hop counts. In this paper, we propose a high throughput routing scheme, called MARV, which makes two key contributions. MARV searches for high throughput paths using an on-demand route searching algorithm so that the routing overhead is smaller compared to other multi-rate-aware routing schemes. MARV also searches for multiple paths to maintain both min-hop and high-throughput paths to select the adequate path depending on the data packet size. We conduct simulations to demonstrate that MARV outperforms not only min-hop path metrics but also previously proposed high-throughput metrics.
Vehicle-to-vehicle (V2V) communication in autonomous driving is an essential technology to enable driver safety and traffic efficiency [1,2,3,4]. For example, consider the domain of autonomous driving, where precise vehicle localization demands stringent latency requirements [5]. Furthermore, automated navigation systems, which rely on real-time map and traffic information, necessitate minimum throughput for seamless operation [6]. Here, autonomous vehicles can communicate with each other via ad hoc communications, which does not require infrastructure support [7]. However, due to the limited transmission range of wireless interfaces, the vehicles in vehicular networks may need multi-hop transmissions to communicate with each other. In recent years, many routing protocols have been developed to solve the multi-hop routing problem in vehicular ad hoc networks [8,9,10,11,12,13]. Conventional routing protocols take the minimum hop count (min-hop) as the metric for routing. In a single-rate physical environment, min-hop corresponds to the minimum number of transmissions, thus achieving throughput increase, small delay, and low power consumption.
The recent development of wireless devices such as 802.11ax/be standards [14,15] enables high-bandwidth multi-rate capability. In multi-rate physical environments, min-hop routing may cause throughput loss and reliability loss [16]. Figure 1 shows an example of a vehicular ad hoc routing using min-hop as the metric. We can easily see that the min-hop metric normally chooses long distance links. This means that the link’s channel quality is poor, and thus it operates at a low data rate. This results in a large amount of medium time to transmit data, which in turn causes the overall network throughput to decrease. Long-distance links may also cause high bit-error rate (BER), in other words, reliability loss due to the path loss.
However, using high-data-rate links does not always produce a higher throughput. There is a strict trade-off between the data rate and the transmission range. The long distance range transmissions must operate at a low data rate while high-data-rate transmissions must run on a short distance range. Accordingly, by selecting high-data-rate links, the ad hoc routing protocol must suffer from an increased number of hops. This tradeoff creates a more complex problem in multi-rate-aware routing protocols.
Furthermore, the packet size is an important factor in selecting the adequate path in multi-rate environments. Since the IEEE 802.11 medium access control (MAC) protocol [17] always spends a certain amount of medium time on the fixed physical (PHY) and MAC overhead, the effective throughput is lower than the physical data rate. Due to this fact, the data rate does not affect much on the throughput of small data packets compared to the large ones. This shows that the adequate path may differ according to the packet size.
In this paper, we propose a high throughput routing scheme called multi-path ad hoc routing protocol for vehicular networks, in short MARV. MARV makes three key contributions. First, MARV searches for high throughput paths using an on-demand routing searching algorithm so that the routing is more effective compared to other multi-rate-aware schemes, which are based on proactive routing [16,18,19]. Here, MARV searches for multiple high-throughput paths while limiting the control overhead. Second, MARV searches for multiple paths to maintain both min-hop and high-throughput paths to select the adequate path depending on the flow size. Third, we conduct extensive experiments to show that MARV outperforms the previous methods in terms of throughput, end-to-end delay, and control overhead.
The remainder of this paper is organized as follows. We briefly review previous work related to multi-rate-aware MAC and ad hoc routing protocols in Section 2. We discuss the main motivation of this paper in Section 3, and then in Section 4, we present the effectiveness of MARV and describe it in detail. Section 6 contains performance results, and we provide concluding remarks in Section 7.
Many MAC protocols have been proposed to utilize the multi-rate functionality. The auto rate fallback (ARF) [20,21] is typically implemented in commercial 802.11 products. ARF chooses to raise or lower its transmission rate according to consecutive transmission successes or failures, respectively. In the receiver-based auto rate (RBAR) [22,23], the receiver selects an adequate transmission rate according to the channel quality measured from the received request-to-transmit (RTS) frame. The opportunistic auto rate (OAR) [24,25] protocol is based on RBAR but provides a temporal fairness among the nodes. In effect, the network throughput increases since the high-data-rate links get more opportunities. We employed RBAR for the multi-rate utilization in consideration.
Several multi-rate-aware routing protocols have been proposed to exploit the high throughput routing paths. multi-rate-aware sub-layer (MAS) [19] takes the reciprocal of the estimated raw data rate as the routing metric. To estimate the channel conditions, MAS employs HELLO packets for proactive routing protocols while overhearing RTS/CTS packets for on-demand routing protocols. However, raw data rates are actually different from the effective throughput due to the PHY/MAC overheads as considered in this paper. Exchanging HELLO packets will result in high overhead, while obtaining the channel quality only through RTS/CTS overhearing will not provide enough information.
Medium time metric (MTM) [26] selects the paths with the lowest medium time. The medium time metric is measured by the reciprocal of the effective throughput, which takes into account the PHY/MAC overheads. However, MTM uses DSDV to trade the channel quality information. Since DSDV is a proactive routing protocol, it will cost constant high overhead. MTM also assumes that the data packet size is fixed at 1500 bytes, which is very unrealistic.
The authors in [27] propose a VANET routing protocol that considers real-time road vehicle density as its routing metric. This enables to acquire the route that offers minimum delay. However, this scheme aims to provide high packet-delivery ratio and does not consider throughput.
W-GeoR [28] introduces innovation by incorporating key routing metrics, including node mobility, link expiration time, channel signal-to-noise ratio (SNR), and destination proximity information, to make distinct routing decisions when selecting the next-hop vehicle during the ad hoc route discovery process. Nevertheless, W-GeoR is custom-tailored for health monitoring applications.
The authors in [29] exploit blockchain features to implement a secure VANET routing protocol. They modified the existing AODV routing protocol to compute the trust scores of neighbor nodes. However, this proposal mainly focuses on security rather than throughput.
We summarize the above related work in Table 1.In this section, we discuss the main motivation of this paper. First, we compare proactive and reactive routing protocols and then reveal that payload size determines the optimal routing path.
We can classify ad hoc routing protocols into two major categories: proactive and reactive routing protocols. Proactive routing protocols such as DSDV [12] and OLSR [13] are quite similar to the routing protocols used in wired networks. The nodes employ periodic control messages to exchange routing information with each other. Reactive routing protocols, such as DSR [10] and AODV [11], send out control messages only when required.
The problem with proactive routing protocols is that the nodes have to send out periodic routing messages even when they are not sending any data packets. Although this is not a big concern in wired networks, it would lead to higher power consumption and bandwidth wastage in wireless networks. Furthermore, as the routing information is updated periodically, there is a high possibility that the routing information may become stale, depending on the update period. However, reactive routing protocols send out routing messages only when needed so that the routing information is always fresh. J. Broch et al. [30] showed that the proactive routing protocol performs poorly in the aspect of packet delivery ratio and routing overhead compared to reactive protocols.
Most of the previously proposed multi-rate-aware routing protocols [19,26] modified the proactive routing protocols to achieve their goals since they have to maintain the link quality information of the entire network. Therefore, it would cause huge overhead and power consumption throughout the network. For that reason, we modified the on-demand routing protocol DSR [10] as the muti-rate-aware routing protocol.
The effective throughput of the wireless links is much lower compared to the physical link rates. For example, when we send a 1500-byte data packet on an 11 Mbps link, the maximum effective throughput would be somewhat close to 5 Mbps. The major cause of this phenomenon is the fixed PHY/MAC overheads, including PHY preamble and header, MAC header, RTS/CTS/ACK frames, DIFS/SIFS, backoff duration, and so on. We call these overheads “fixed overheads” since they are transmitted at a predetermined rate spending a fixed amount of medium time. Figure 2 shows the fixed PHY/MAC overheads independent of the selected transmission rate.
The multi-rate-aware routing protocol proposed by Awerbuch et al. [26] uses medium-time as the routing metric. They calculate the medium time as the reciprocal of the effective throughput. One rough assumption is that the MAC payload is fixed at 1500 bytes. In real life, the packet size varies depending on the applications. According to the report from the Cooperative Association for Internet Data Analysis (CAIDA) [31], the actual Internet traffic is governed by small-sized packets of under 100 bytes comprising more than 50%. Most of these small-sized packets are TCP-ACK packets that are 40 bytes in length. Most of the large-sized packets, which are mostly TCP data packets, are about 550 bytes from TCP implementations that do not use path maximum transfer unit (MTU) discovery and 1500 bytes from those use it. Accordingly, fixing the MAC payload at a very high size, e.g., 1500 bytes, would be very unrealistic.
Figure 2a shows the MAC medium time distribution when a 1500-byte payload (the same size as a TCP data packet when path MTU discovery is used) is transmitted, while Figure 2b shows the same distribution when a 40-byte payload (the same size as a TCP-ACK packet) is transmitted. For Figure 2a, the medium time spent by the 1500-byte data payload usually dominates the total medium time. On the other hand, for Figure 2b, the medium time spent by the PHY/MAC overhead occupies most of the medium time. What this means is that when a small-sized packet is transmitted, the data rate does not affect the throughput performance much. In fact, by selecting a high-data-rate link, the source nodes would tend to select a path that has a large number of hops, thus decreasing the overall throughput.
Figure 3 shows a simple three-node topology, where node A is the source node and node C is the destination for constant bit-rate (CBR) traffic. When min-hop routing is used, source node A sends directly to node C, while node B is used as an intermediate hop when MTM is applied. Figure 4a compares the two metrics by the throughput performance for the topology using the ns-2 simulations as the application packet size is varied. The details of the simulation setup are presented in Section 6.1. It seems reasonable to use the MTM when large-sized packets are used, but a further glance at Figure 4b indicates that the min-hop metric is reasonable for small-sized packets. The threshold application packet size is about 140 bytes, which is 172 bytes (adding the UDP and IP header size) as a MAC payload. This also agrees with the actual Internet packet size distribution, where more than 50% of the IP packets are smaller than 100 bytes. This means that more that 50% of the packets may experience performance degradation by always using MTM as the routing metric. We will delve into this issue in Section 4.3.
In essence, the optimal path that generates the maximum throughput would depend on the packet size. For small-sized packets, the min-hop metric is preferable, whereas the large-sized packets would show better performance by using MTM.
At first glance, one may argue that the throughput increase by using min-hop metric instead of MTM for small-sized packets is not significant according to Figure 4b. Actually, the maximum application throughput increase by using min-hop instead of MTM is merely 33.8 kbps (4.2 KBps) when the packet size is 60 bytes. However, the main effect of using min-hop instead of MTM is the reduction in medium time spent per packet delivery as shown in Figure 4c. By reducing the medium time spent for small-sized packets, some other flow that transmits large-sized data packets can utilize the saved medium time and increase the overall network throughput. Furthermore, by using the min-hop metric for small-sized packets, the end-to-end delay would decrease compared to MTM, which can be easily figured out in Figure 2. We will further discuss these issues with the simulation results in Section 6.
Figure 5 shows the basic operation of MARV. The numbers on the link indicate the medium time metric for a 1500-byte packet to be sent. The packet format shown in the figure is the abstract format of the route request (RREQ) packet of MARV. The RREQ of MARV contains the path link quality field, i.e., the path MTM field, which indicates the total sum of the link medium times of the path. Therefore, whenever a node receives an RREQ packet, it adds the MTM value of the receiving link to the path MTM field before rebroadcasting it.
The main objective of the route search mechanism in MARV is to find the path with the lowest path MTM value, i.e., the high-throughput path. Therefore, MARV has to search for link disjoint paths to find the path with the lowest path MTM value. By using the basic DSR route search mechanism, the destination is capable of finding multiple paths, which are node disjoint. However, the basic DSR route search mechanism cannot find the link disjoint multiple paths. For example in Figure 5, assume that node B is the source and node D is the destination. Node D is capable of finding node disjoint paths B-C-D and B-D via the basic route search mechanism. Now, let us assume that node A is the source and node E is the destination. Although A-B-C-D-E and A-B-D-E are link-disjoint paths, the basic route search mechanism forces node D to discard the route request from node C, making the A-B-C-D-E path unknown to destination node E.
There has been some work on multi-path routing in DSR [32], but these mechanisms result in very high routing overhead since route requests are rebroadcasted multiple times. In MARV, we use a similar approach, but with a tighter constraint. For example, in Figure 5, suppose node A is the source and node E is the destination. Node A generates a RREQ packet to be flooded into the network. Node D rebroadcasts the RREQ packet received from node B. Then, node D receives the RREQ sent by node C. Although the RREQ sequence is not new, instead of just discarding the RREQ, node D compares the path MTM value of the newly received RREQ with the minimum path MTM value of the previously received RREQ by using the ignoreRREQ() shown in Algorithm 1. The constant α will be further discussed in Section 4.2. This approach enables MARV to eventually find the high-throughput paths. In this example, node B compares the path MTM values and finds out that the path MTM value 7.89 from node C is smaller than the previously received minimum path MTM value 10.90 and hence rebroadcasts the RREQ packet. Node E will eventually receive the RREQ packet sent via the link–disjoint path A-B-C-D-E.
Destination node E basically replies to all the route requests received, but will check by using the same algorithm used when forwarding the RREQ (see ignoreRREQ() function in Algorithm 1). In other words, the destination will send out an RREP only if the path MTM value of the received RREQ is smaller than the previous received minimum path MTM value.
Source node A then receives multiple RREPs from destination node E and will select between the min-hop path and minimum path MTM path. Function selectPATH() in Algorithm 2 shows the algorithm to select the adequate path for the data packets. Basically, MARV selects the path based on the size of the data packet. For small-sized packets, MARV selects the min-hop path while selecting the minimum MTM path for larger packets. In reality, bulk data traffic for FTP normally takes the high throughput path while small TCP ack packets or small http packets take the min-hop path.
| Algorithm 1 MARV i g n o r e R R E Q ( ) operation. |
| 1: |
