7.5 CodeOn: a Cooperative Popular Content Broadcast Scheme for VANETs Based on SLNC

In this section, we study the cooperative broadcast of popular contents in VANETs. Next we introduce specific design requirements of such MCD service. After that, the main design will be given, followed by detailed simulation and performance evaluation results.

7.5.1 Design Objectives

For any popular content distributed by the MCD service, the primary objective is to achieve low average downloading delay, which is equivalent to high average downloading rate. For each vehicle in an AoI, its downloading delay is defined as the elapsed time from downloading start to 100% completion. Meanwhile, it is desirable to achieve a high degree of fairness, i.e., the variation of downloading delays among different vehicles should be small. Finally, high-rate content distribution cannot come at the cost of incurring too much protocol overhead and data traffic, otherwise the MCD service would be less compatible with other possible services in the service channel. Thus it is also important to maintain high protocol efficiency.

We first define the main notations used in this chapter in Table. 7.1.

Table 7.1 Frequently used notations

Notation	Definition
F	The file to be distributed
N	Data packet size (bytes)
L	File length (number of generations)
K	Generation size (number of pieces)
J	Piece size (bytes)
M	Number of symbols in a packet
Gi	Generation i
	The Galois field used in network coding
U(v)	The utility of a node v
	The neighbor set of node u
	Average symbol rank of Gi in vehicle v
γ	Average received SNR or SINR for a symbol

Reproduced by permission of © 2011 IEEE.

7.5.2 Design Overview

CodeOn is a push-based cooperative MCD protocol, where a large file F is actively distributed from the APs to the vehicles inside the AoI through the help of a dynamic set of relay nodes. Each AP is a source for F, and F is divided into equal-sized generations (chunks), and the SLNC is performed within each generation. In Figure 7.9, we illustrate the general process of content distribution in CodeOn, assuming F has only one generation consisting of three pieces.

Each AP/source broadcasts the source file to vehicles in its range based on vehicles' reception status, which is not shown in Figure 7.9. Outside the ranges of APs, vehicles distribute the file cooperatively by choosing a set of relay nodes distributively. This is the core to CodeOn, which consists of three steps.

7.5.3 Network Coding Method

We now describe the way that SLNC actually operates in CodeOn. Assume F with size |F| is divided into L generations G1, G2, …, GL, where each generation contains K pieces. A piece has size J and contains J/N packets. Then, |F| = L · K · J. In order to reduce the overhead brought by SLNC, we adopt “piece-division, run-length SLNC.”

The reasons are twofold. On the one hand, if a generation is divided into packets (packet-division), in order to keep low computational overheads we must use relatively small K (the computation complexity of decoding is usually O(K3)), thus a large number of generations is required for large F. This reduces the gain of NC due to the “coupon collector's problem” (Lee et al. 2008), and increases the communication overhead for exchanging the content availability. On the other hand, using multipacket pieces (piece-division), K can be maintained at a reasonable value by scaling the piece length linearly with file size. However, the number of symbols in a piece () increases with the piece length. In the extreme case that every symbol in a piece has a different coding vector, the communication overhead is at least bits, which equals to 10 KB if J = 20 KB, N = 1 KB, K = 32, M = 32, q = 8. This is clearly unacceptable. Fortunately, run-length coding method (Katti et al. 2008) can be used to reduce the communication overhead of SLNC, in which one coding vector is used for each sequence of consecutive clean symbols (run). Dynamic programming is used to choose appropriate combination of runs to minimize the overhead (Katti et al. 2008). Therefore, in CodeOn, we combine run-length SLNC with the piece division to achieve higher network coding gain and reduce the communication overhead, which we call piece-division run-length SLNC. When a coded piece is transmitted, it is separated into several packets; only the header of the first packet contains the coding vectors of runs that composing the piece, while subsequent packets only have normal small headers. Thus, a piece can be regarded as a “big packet.”

Compared with PLNC, the gain from symbol-level diversity can be easily seen from the analysis in Section 7.4. Meanwhile, the overhead of our method is always smaller than run-length SLNC combined with packet division. Generally, the number of coding vectors in a piece equals to the number of runs. However, using packet division a run may be fragmented into more than one runs, which needs more coding vectors in total. In the worst case, each symbol is a run and the overheads are equal. This is illustrated in Figure 7.10. In reality, the symbols errors are often bursty (due to packet collisions) so the number of runs is usually much smaller compared with the number of symbols. For example, if there are 20 runs in a 20 KB piece the overhead is about 640 B, which is 3.2% of piece size.

In order to balance the gain and overhead of SLNC in CodeOn, we fix the number of pieces in a generation (K) and the number of generations (L) (e.g. 32 and 50, respectively). Although the piece size J scales linearly with the file size because SLNC tolerates symbol errors, the size of a piece has small impact on the protocol performance.

7.5.4 Efficient Exchange of Content Reception Status

An important piece of information exchanged in CodeOn is every node's content reception status (i.e., how much content is downloaded for each generation), which is essential to enabling optimized, distributed transmission decisions. It could be obtained by sending gossip messages in each service time slot but this consumes a large portion of a service time slot. In CodeOn, we choose to piggyback the reception status in safety messages, thus adding zero overhead in the service channel.

However, for SLNC, representing the exact reception status of each generation will incur large overheads. The decoding matrix can be represented by a single null-space vector (Lee et al. 2006). However, the size of the reception status information adds up to bits, where Kq is the maximum size of one null-space vector. For L = 50, J/N = 20, M = 32, K = 32, q = 8, this amounts to 1 MB which is too large.

Therefore, in CodeOn we propose a fuzzy average rank method to represent the reception status in an efficient way. An important property of network coding is that the rank of the decoding matrix determines the amount of received information. For two nodes u and v with symbol ranks ru, i, j and rv, i, j for position j in Gi, respectively, if ru, i, j > rv, i, j, then a recoded symbol sent from u is innovative to v with high probability (Ahlswede et al. 2000). Otherwise, this does not hold7. We can therefore substitute each null-space vector with a rank, which has log2K bits. For a generation Gi received by node u, there are many symbol positions with different rank values. But because the size of a piece is relatively small (e.g., J = 20 KB) compared to what can be transmitted in a 50 ms slot using DSRC (55 KB when data rate is 11 mbps), the ranks of various symbol positions are expected to increase at similar rates thus are similar to each other.

Therefore, we use the average rank across all symbol positions in Gi to represent how much information is received for Gi. It is rounded to an integer, because it is more meaningful to interpret the average rank as how many “pieces” are received. It does not make much difference when the variation of is smaller than 1. The range of the rank is in [0, K]; if , this means “some information in Gi is received”; and means “Gi is received completely.” Therefore, the total overhead becomes L · (log2K) bits, which equals 31B when L = 50, K = 32. Note that, this is independent of the piece size and also the file size. Now, the overhead takes an acceptable percentage (≈10%) of the typical size of a safety message (300B) and is small enough to be piggybacked without affecting the QoS of safety applications (Xu et al. 2004). The average rank representation is illustrated in Figure 7.11.

7.5.5 Distributed Relay Selection in Cooperative PCD

Once vehicles are out of the range of an AP, they begin distributing the content cooperatively through the VANET. Due to the mobile nature of the VANET, the very notion of “cooperative” is captured in that vehicles distributively agree on a set of relay nodes, based only on local information.

7.5.5.1 Node Utility Calculation

In order to determine a set of relay nodes that can bring the largest useful amount of content to the others, each node needs to calculate its own “utility” based on neighbors' content reception status collected from the safety messages in the control channel. The utility of a generation at node u is defined as:

7.10

where Step(x) = x, if x > 0, otherwise, Step(x) = 0. This quantity measures how much innovative information Gi of node u can provide to its neighbors in total.

The utility U(v) of node v is defined as the maximum value among all generations' utilities of v. This estimates the maximum additional amount of innovative information v can provide to all neighbors, and reflects v's priority in accessing the wireless medium. We do not look at the aggregate utility of multiple generations because to transmit many generations takes a long time while the VANET topology could change dramatically.

7.5.5.2 Transmission Coordination

After nodes' priorities are determined, only a subset of the high-priority nodes (relays) will become the ones who actually broadcast their contents, in order to achieve high downloading rate and prevent from severe interference. Those relays are decided via a contention process, in a local and opportunistic way. In particular, the vehicles with the highest priorities in their locality should access the channel first, and suppress the others to avoid unnecessary packet collisions.

To this end, at the beginning of each service time slot, each vehicle v sets a backoff delay Δt which is inversely proportional to its utility before it makes the, channel access decision. When the timer expires, v senses the channel; if it is clear v will broadcast a short control message that is sent immediately by the MAC layer, even without additional random backoff in 802.11. Note that an AP always has the highest utility, so it will be a relay every time if there are vehicles still in need of the file in its local range.

Backoff delay function. A straightforward one is as follows:

7.11

where parameter Δtmax is the maximum allowable backoff delay (e.g., 2 ms). However, Equation (7.11) suffers from a major problem. That is, each node v has different neighborhood and . If v merely has one neighbor but its generation utility for Gi is K, it will have the highest priority and Δt(v) = 0. However, compared with another node w that has ten neighbors and utility 5K, v is obviously not as beneficial to the whole network as w. Ideally, the should be a maximum possible neighborhood size () and be the same for all vehicles, so that they have a common basis of priority comparison. However, setting it to be a fixed value is undesirable because the vehicle density will change.

Therefore, we estimate the maximum local neighborhood size. To do so, each node broadcasts its neighborhood size to others, and propagates its own estimation about the maximum neighborhood size. After several rounds, all nodes can obtain the same . Although the VANET topology may change every second so that varies over that time, we actually need not to maintain the same for all nodes in the network. Rather, it is sufficient for vehicles in a local one-hop range to agree on the same estimated , while the local propagation requires only very few rounds to converge. To achieve this, each vehicle will attach its local estimate of in the safety message, and update it in a way similar to distance updates in distance vector routing.

In addition, to resolve ties, a random jitter is added to the backoff delay of each vehicle. Thus, in CodeOn, each vehicle sets its backoff delay according to the following:

7.12

where TJ is the maximum jitter.

Discussion of parameter selection. First, Δtmax must be large enough to distinguish two vehicles with adjacent utility rankings. For a common neighbor vc of two vehicles v1 and v2, the minimum difference between U(v1) and U(v2) is 1. Therefore, the minimum difference between v1 and v2's backoff delays is , which should be larger than the signal propagation delay. When their distance d(v1, v2) = 300 m the propagation delay is s. Therefore, we can choose Δtmax > 2 ms, i.e., when , K = 32, min{|Δt(v1) − Δt(v2)|} > 1.2 μs. On the other hand, Δtmax shall not be too large since it will waste bandwidth. For Δtmax = 2 ms, if transmission of one generation spans 10 service time slots (500 ms), the percentage of wasted time can be as low as 2/500 = 0.4%.

Second, TJ should be both large enough to distinguish two contending nodes v1 and v2 with the same utility, and small enough to preserve the priorities between nodes with different utilities. Assume all the contending nodes have the same neighbor set. Node utility is an integer, for node v1, so the utility of the node v3 with priority next to v1 is at most (since for some Gi, Gj and every neighbor is counted once). Thus, the utility difference is at least . Therefore, we have (e.g. 0.1 ms). Note that we do not consider since this is rare in reality, i.e., contending nodes always share a large proportion of neighbors.

7.5.5.3 The Merit of Carrier Sense Under SLNC

We have used carrier sense in the contention process for transmission opportunities by potential relay nodes. That is, a node quits the contention for channel access whenever it detects the energy of an ongoing transmission, otherwise it is allowed to transmit concurrently with others. Traditionally for packet-level broadcast (with/without NC), this leads to the well-known “hidden terminal” problem, because such concurrent transmissions may cause interference at their neighbors8. Various mechanisms have been proposed to solve this problem, such as clearing the channel within a range larger than carrier sensing range (Li et al. 2009). However, due to SLNC's better tolerance in transmission errors and interference, more aggressive concurrent transmission is possible. In Section 7.4, we demonstrated that the simple carrier-sensing rule actually provides near-optimal performance in terms of average downloading rate, as the impact of hidden terminals is greatly alleviated by SLNC.

7.5.6 Broadcast Content Scheduling

Finally, we briefly highlight the way that broadcast content scheduling is dealt with in CodeOn.

7.5.6.1 Content Scheduling at APs

In CodeOn, the APs broadcast the contents in a round-robin way to maintain the “information difference” between vehicles moving out of the AP range at different times. In order to make more efficient use of the VANET bandwidth, the content scheduling should also be aware of local vehicles' reception status. Therefore an AP will sort its file generations according to their utilities; in addition to round robin, it transmits the one with both larger ID and the highest utility that hasn't been transmitted in the last “batch”.

7.5.6.2 Content Scheduling at Vehicles

After a vehicle becomes a relay node, it broadcasts the generation with the maximum utility. To avoid from transmitting duplicate information, it is important for vehicles to decide when to stop the transmission.

To this end, we estimate the number of pieces that each relay should send in one batch. The intended number of (innovative) pieces that v sends to a neighbor w for Gi is estimated as . Then, the number of pieces that v should send to all neighbors for Gi is computed as

7.13

which is also the size of a batch. When the average rank and those of all of its neighbors are equal to K (full rank), we set Zv(Gi) = 0. Note that the above is a conservative estimation, which treats the link qualities as perfect.

In addition, we need to deal with two situations. 1. If a batch spans multiple service time slots, relay v accesses the channel deterministically by setting its Δt(v) = 0 during the following time slots in order to finish transmitting its batch. 2. If the transmission of a batch terminates before the end of some service time slot k, to avoid waste of VANET bandwidth, v will fill the rest of the channel by transmitting additional coded pieces from the same Gi until time slot k is used up.

7.5.7 Performance Evaluation

7.5.7.1 Methodology

In this section, we evaluate the performance of CodeOn by simulations. We compare CodeOn with an enhanced version of CodeTorrent (Lee et al. 2008), which is pull based and uses PLNC. The AP is treated as a normal node. Each node periodically broadcasts a gossip message to tell others about its content availability. Based on this, a node v periodically broadcasts a downloading request, asking for the index of the rarest generation Gi among its neighbors, and attaches a null-space vector of Gi computed from v's corresponding decoding matrix. Each neighbor w, upon receiving the request, checks if it has Gi. If yes, and if the null-space vector is not orthogonal to the subspace spanned by w's coding vectors of Gi, w responds v with one coded piece from Gi via unicast, after waiting for a random backoff delay to reduce collisions. Only the first packet in a piece contains the coding vector; if that packet is lost then the whole piece is lost. Upon successful reception of a piece, node v continues sending another downloading request. Otherwise, v waits till the next period to broadcast its request. Nodes other than v exploit opportunistic overhearing, i.e., buffer a piece sent to v if that piece is useful and received correctly.

We made the following additional modifications to CodeTorrent. We equip it with multichannel capability as in CodeOn. To ensure a fair comparison, we apply the same channel switching mechanism in CodeTorrent, which results in a 1/2 reduction in the downloading rate. Also, in order to increase the success probability of overhearing, each node is allowed to overhear multiple different pieces during the same period and there is no reserved time for receiving one piece. Moreover, the packets in a piece do not have to arrive in order; a node flushes an incomplete piece after a certain time from its first reception, say 0.5 s.

In addition, we introduce a variation of CodeOn, CodeOnBasic, which is also push based with piece division but based on PLNC. A piece is used as a whole for encoding and decoding. A node buffers any overheard piece as long as it receives the coding vector in the first packet of that piece, and the same buffer flushing mechanism as in CodeTorrent is adopted. Moreover, in content scheduling a relay node pads a service slot with whole pieces. If the remaining service slot time is not enough for sending a whole piece, it terminates the current batch, rather than filling with individual packets. Other than that, CodeOnBasic is the same with CodeOn.

We implemented CodeOn, CodeOnBasic and CodeTorrent in NS-2.34 (www.isi.edu/nsnam/ns). For CodeOn, we implemented the run-length coding with dynamic programming algorithm to minimize the communication overhead in sending each coded piece (Katti et al. 2008). We simulate independent symbol errors in a packet, and in simulation the number of runs seldom exceeds 20 for 10 KB pieces. Packet capture effect is enabled and, when two packets collide, if no packet can be captured, the symbols from the point of collision are all discarded. Otherwise, the captured packet is received as usual. We do not consider vehicular buffer constraints.

We have a few notes on broadcast data rate selection. First, the safety message's communication range shall be larger than that of PCD data packets, so that the neighbor set used in relay selection can cover the set of nodes that can receive a data packet. Otherwise, the utility cannot truthfully reflect a node's total content usefulness. Considering the reliability of safety messages, we chose the base rate (3 mbps) for broadcasting safety messages. Second, we want to achieve a high downloading rate for PCD. For SLNC, choosing a higher data rate is beneficial because it has better error-tolerance. Since rate that is too high is also undesirable due to very small communication range, the data rate of PCD packets is set to be 12 mbps throughout the chapter.

7.5.7.2 Simulation Settings

We consider both highway and urban scenarios (Figure 7.12). We use a VANET mobility generator (http://nile.cise.ufl.edu/important/software.htm.) to generate the movement patterns. Vehicles are placed uniformly at random in the road area; when a vehicle hits the boundary it randomly selects another entry point of the map. This removes the boundary effect; equivalently, the AoI is infinitely large. Table 7.2 is a list of parameters.

Table 7.2 Simulation parameter settings

The highway scenario consists of a bi-direction, four lane highway with length 6 km. Vehicles' speeds are randomly drawn from [20,30]m/s with a maximum acceleration of 0.5 m/s2. The urban scenario is 4 km × 4 km as shown in Figure 7.12. In order to evaluate the impact of topology and traffic density, we simulate sparse and dense traffic for both scenarios. The sparse settings simulate delay-tolerant network (DTN), where the total number of vehicles is 100 for highway and 160 for urban. The dense highway setting has 300 vehicles while the dense urban has 400 vehicles.

7.5.8 Simulation Results

7.5.8.1 Downloading Performance

We evaluate the downloading performance from three aspects: 1. downloading progress, which is the change of average downloaded percentage of the file with the elapsed time (averaged upon each vehicle); 2. average downloading delay: the average elapsed time from downloading start to 100% completion; 3. average downloading rate, where the downloading rate for each vehicle is the file size divided by its downloading delay.

We present the downloading progress in Figure 7.13–Figure 7.16 for all four scenarios. It can be seen that CodeOn significantly outperforms both CodeOnBasic and CodeTorrent. The downloading progress of CodeOn is the fastest, especially when the average downloaded file percentage is below 90%. The comparison between CodeOnBasic over CodeTorrent demonstrates the effectiveness of our new push-based protocol design and the comparison between CodeOn and CodeOnBasic shows the advantage of the use of SLNC, which we will discuss later.

Next, we evaluate the average downloading delays and rates in Figure 7.17 and Figure 7.18. Some of the average delays are not shown since their downloading progresses cannot reach 100% within the given simulation period. There are two key observations. First, the average downloading rates of CodeOn are much higher than both CodeOnBasic and CodeTorrent, for both highway and urban scenarios and both sparse and dense traffic. Second, CodeOn maintains high downloading rate in all cases shown, especially for the two extremes, i.e., sparse urban scenario and dense highway cases which represent the lowest and highest traffic density, respectively. This means CodeOn is the most robust to variations in topology and vehicle density.

The first phenomenon above is attributed to the push-based protocol design combined with SLNC. In CodeOn, using a prioritized relay selection mechanism with the transmission coordination that avoids heavy packet collisions, the contents can be distributed proactively to the vehicles in the AoI so that the VANET bandwidth is fully utilized. Moreover, each transmitted piece of content has a high probability of being useful to a relay's neighboring vehicles, in terms of increasing the ranks of their decoding matrices. In addition, with SLNC, the symbols in content pieces are received with a higher rate from APs and relays, which results in a higher downloading rate.

The robustness of CodeOn under low traffic density is mainly attributed to the enhanced reception reliability brought by SLNC. Compared with PLNC, SLNC actually enables vehicles in a larger range to receive some useful information in a piece. In the sparse urban setting, although the vehicular contact opportunities are much less, CodeOn is able to mitigate the impact of low traffic density.

On the other hand, CodeOn is less affected under dense VANET. For the dense scenarios, the differences between CodeOn's downloading rates and those of CodeOnBasic and CodeTorrent are both larger than the sparse scenarios (Figure 7.18). For CodeTorrent, the performance degradation is due to lack of coordination and the use of PLNC for a large file. 1. Under dense VANET, the number of requesting vehicles in a node's neighborhood increases. Since there may be more than one responder for each requester, the chance of packet collisions also increases. The unicast-with-overhearing mechanism retransmits packets after they are collided, which aggravates the problem. 2. For both CodeTorrent and CodeOnBasic, the use of PLNC prevents a requester from receiving a whole piece under frequent packet collisions. However, CodeOn alleviates the above problems dramatically through prioritized relay selection and the use of SLNC.

7.5.8.2 Fairness

Fairness is embodied in the distribution of downloading delays of all vehicles, shown in Figure 7.19—Figure 7.21. We show the distributions for all three cases. The fairest situation has zero variance, i.e, all the delays are equal. From the figures, one can see that the distributions of CodeOn are more concentrated (more fair) than those of CodeOnBasic and CodeTorrent. Few vehicles need a very long time to receive the whole file. Again, the same robustness of CodeOn to variations in traffic density can be observed.

The superiority of CodeOn in fairness is still attributed to the use of SLNC. This enables more reliable reception of the coded symbols, because an overhearing node will buffer any innovative clean symbol it received. In CodeOn, because the granularity of information reception is smaller and vehicles have similar opportunities to contact APs and other vehicles within a time period in the order of 1000 s, their reception progress has low variance. However in CodeOnBasic and CodeTorrent, a vehicle either receives a whole piece or receive nothing, so the variance among reception progress is larger. Again, the results on fairness demonstrate the benefit of using SLNC and the effectiveness of CodeOn's protocol design.

7.5.8.3 Protocol Efficiency

One may wonder if CodeOn achieves fast push-based downloading by sacrificing protocol efficiency. To further investigate this issue, we present the results on protocol efficiency in Table 7.3 and Table 7.4.

Table 7.3 Protocol efficiency (total number of pieces in the file: 1600)

Protocols	Percentage of non innovative received pieces	Average no. of failed overheard pieces per received piece
Sparse highway scenario
CodeOn	N/A	N/A
CodeOnBasic	0.476	4.26
CodeTorrent	0.325	27.27
Sparse urban scenario
CodeOn	N/A	N/A
CodeOnBasic	0.228	3.47
CodeTorrent	0.167	80.74

Reproduced by permission of © 2011 IEEE.

Table 7.4 Protocol efficiency (continued)

Protocols	Average no. of pieces sent by a vehicle	Average no. of pieces sent by an AP
Sparse highway scenario
CodeOn	2202.12	26023.00
CodeOnBasic	4054.87	51578.00
CodeTorrent	32889.87	53665.00
Sparse urban scenario
CodeOn	1031.14	43445.25
CodeOnBasic	3525.31	143905.00
CodeTorrent	52465.69	222287.50

Reproduced by permission of © 2011 IEEE.

As we have shown in the last section, the protocol overhead of CodeOn is small. To evaluate the amount of data traffic experienced, we show the average number of pieces sent by a vehicle and an AP during the whole simulation time (a node will not transmit when all of its neighbors receive 100% of the file). CodeOn has the smallest number among the three protocols. Its high protocol efficiency comes from both the high symbol reception probability due to SLNC and the high usefulness of the transmitted symbols due to relay selection. As CodeOnBasic adopts the same relay selection mechanism, it enjoys similar high protocol efficiency to CodeOn. However, CodeTorrent sends many pieces due to a large number of failed overhears explained below. Note that the APs are always the most advantageous nodes so they transmit a lot in all three protocols.

To further study the role of relay selection we compute the percentage of total number of noninnovative pieces out of the total number of received pieces, which reflects the usefulness of the received content. We also calculate the average number of failed overheard pieces (in which the coding vectors are received but not all the subsequent packets) per received piece. For the former, CodeOnBasic is slightly higher than CodeTorrent but for the latter CodeOnBasic is much lower than CodeTorrent. This is because in CodeTorrent, a responder uses the requester's null-space vector to decide whether to transmit a coded piece, which is definitely innovative to the requester. However, in CodeTorrent, a responder's transmission mainly benefits the requester itself but few others due to uncoordinated transmissions. On the other hand, in CodeOnBasic the selected relays can benefit their whole neighborhood, while the broadcasted contents are still highly useful. As a result, both the downloading rate and efficiency are high.

7.5.8.4 Discussion

Finally, we give some insights that can be obtained from our results.

Push versus pull. First we compare the push-versus-pull-based content distribution in VANETs. CodeOnBasic and CodeTorrent are both based on PLNC, but the former performs much better than the latter for all scenarios in Figure 7.13—Figure 7.16 and Figure 7.19—Figure 7.21. An obvious reason is the difference in bandwidth utilization. CodeOnBasic lets the APs and relays broadcast proactively (push), so that the service time slots are almost fully utilized. However, in CodeTorrent each node make requests (pull) periodically and responders transmit passively. Whenever it receives a piece in error, a requester will wait until the next period to make subsequent requests. Due to the lossy property of the wireless channel in VANETs, this happens frequently so the service channel is under utilized.

However, a more fundamental reason that the push method in CodeOn and CodeOnBasic is better is related to to the relay selection mechanism. If there was no transmission coordination between vehicles, the push-based content distribution could easily lead to frequent packet collisions. For CodeTorrent, which is pull-based, its high chance of packet collisions is already evident from the large number of failed overheard pieces of CodeTorrent in Table 7.3. One can imagine that this situation will be aggravated if CodeTorrent is changed to push-based distribution where nodes transmit more aggressively.

Apart from transmission coordination, in designing a push-based protocol, it is always critical to maximize the usefulness of the broadcasted content from each relay nodes. As nodes do not make explicit downloading requests, and as “push” uses broadcast transmission, it is basically impossible to ensure the usefulness of broadcast content of a relay for all its neighbors. In CodeOn and CodeOnBasic, our approach is to select a relay to be the one that can bring the maximum amount of useful content to all its neighbors by implicitly calculating node utilities based on fuzzy average rank differences. In contrast, in CodeTorrent each responder will only ensure the content to be 100% innovative for one requestor, using accurate null-space indicators. Interestingly, as one can see from the number of noninnovative pieces in Table 7.3, the number of CodeOnBasic is quite close to that of CodeTorrent, which can be regarded as a lower bound. This proves the effectiveness of our relay selection approach.

SLNC versus PLNC. The advantage of using SLNC is evident by comparing CodeOn with CodeOnBasic in Figure 7.13—Figure 7.16, which are only different in the network coding method. With PLNC, in CodeOnBasic a coded packet is discarded whenever it is received in error, which leads to unsuccessful reception of the whole piece. However, with SLNC, CodeOn records every innovative received symbol in a piece and then combines innovative symbols to decode the piece.

As previously mentioned, SLNC is superior in tolerating transmission error. This is a direct reason of why CodeOn has the best robustness under dense traffic scenarios. By both coding and receiving according to a small granularity of symbols (yielding higher content diversity), vehicles have a better chance of receiving some useful information, even when packet collisions are frequent due to dense traffic, or when there are few vehicles or APs around. However, with PLNC, the content diversity is lower. Although our push-based protocol design is able to choose the best relay nodes and alleviate collision, without SLNC, small downloading delays and a high level of fairness are very hard to achieve for all topologies and traffic densities.