On Latency Reductions in Vehicle-to-Vehicle Networks by Random Linear Network Coding

Tiantian Zhu,Congduan Li,Yanqun Tang,Zhiyong Luo

School of Electronics and Communication Engineering,Sun Yat-sen University,Shenzhen Guangdong 518000,China

Abstract:In the Internet of vehicles(IoV),direct communication between vehicles,i.e.,vehicle-tovehicle(V2V)may have lower latency,compared to the schemes with help of Road Side Unit(RSU)or base station.In this paper,the scenario where the demands of a vehicle are satisfied by cooperative transmissions from those one in front is considered.Since the topology of the vehicle network is dynamic,random linear network coding is applied in such a multisource single-sink vehicle-to-vehicle network,where each vehicle is assumed to broadcast messages to others so that the intermediate vehicles between sources and sink can reduce the latency collaboratively.It is shown that the coding scheme can significantly reduce the time delay compared with the non-coding scheme even in the channels with high packet loss rate.In order to further optimize the coding scheme,one can increase the generation size,where the generation size means the number of raw data packets sent by the source node to the sink node in each round of communication.Under the premise of satisfying the coding validity,we can dynamically select the Galois field size according to the number of intermediate nodes.It is not surprised that the reduction in the Galois field size can further reduce the transmission latency.

Keywords:random linear network coding;Vehicleto-Vehicle;Markov process;Time-critical

I.INTRODUCTION

Vehicle to Everything(V2X)is a new mobile communication technology that deeply integrates automobiles,communications,and transportation[1].With the opening of the first year of 5G commercial use,accelerating the promotion of V2X technological innovation has attracted much attention.V2X includes Vehicle-to-Infrastructure(V2I),Vehicle-to-Road(V2R),Vehicle-to-Network(V2N)and Vehicleto-Vehicle(V2V)[2].They are not completely independent of each other.For example,in recent scenarios where mobile edge computing(MEC)is applied to the Internet of Vehicles(IoV),V2V communication data may also be transmitted to the Road Side Unit(RSU)for calculation and storage through V2R[3].The vehicle is not only the main service provider,but also the main service receiver.Therefore,V2V is an important research aspect in V2X.

The Dedicated Short Range Communication(DSRC)technology based on IEEE 802.11p has been used internationally for V2V wireless communication for 20 years[4].This technology requires a large number of roadside units,and the deployment cost is high.The C-V2X technology proposed in recent years supports the advantages of longer communication distance and higher capacity[5].The standardization development of V2V technology in 3GPP can be divided into three stages.In 2017,a direct link(PC5 interface)communication method working in the 5.9 GHz frequency band was introduced,and the Uu interface of the public mobile cellular network was optimized[6].In 2018,technologies such as carrier aggregation and high-order modulation were introduced to the PC5 interface to increase the data rate,and some technologies that can reduce the delay were introduced.In 2019,the PC5 interface supports three modes of unicast,multicast and broadcast to provide the ability to support different services.In addition,the Uu interface network also introduces features such as communication slicing and edge computing to meet the needs of the IoV for low latency,high reliability,and large bandwidth[7].The above changes in V2V technology are mostly aimed at improvements in facilities and signal modulation methods.There are still shortcomings in the optimization of the entire V2V transmission process.For example,bandwidth resources are preciously limited.In 1999,the United States designated(5855-5865MHz)as a dedicated channel for V2V communication[8].How to transmit more information under limited bandwidth is a challenge.Network coding,as a promising technology in the network layer to increase the throughput of the network,may shed a light on the V2V solution.

Network coding was first proposed by Ahlswede et al.in 2000.Different from the traditional relay method of store-and-forward at the intermediate node,the data packet is sent out after being encoded at the intermediate node[9].Then Li et al.proposed linear network coding in 2003.They applied linear network coding to the multicast network and proved that the max-flow from the source to each receiving node can be reached[10].T.Ho et al.proposed random linear network coding in 2003.The intermediate node selects coefficients in the finite field independently and randomly,then uses these coefficients to linearly combine the received data packets,and finally sends the encoded data packets.This encoding method ensures that the receiving node can decode successfully with a higher probability[11].Subsequently,the application of random linear network coding in wireless broadcast networks has attracted attention gradually.Wu studied the impact of random linear network coding on multicasting packet network asymptotic throughput[12].Various methods are adopted to improve random linear network coding,thereby increasing network throughput[13–15].There are also many studies on network coding complexity[16–19].

To minimize the delay in broadcasting network with erasure channels and feedback was studied in[20].They used network coding and feedback information to shorten the delay.Atilla et al.studied the delay and throughput in an unreliable packet network.They provided asymptotic expressions for the delay with and without random linear network coding[21].The finite field size,the coding batch size and the number of nodes will affect the performance of random linear network coding[22].The asymptotic expressions for the delay refers to the change of delay when a certain influencing factors tend to infinity[21].For practical applications,it is not appropriate to use asymptotic delay as a performance standard.The network coding average delay in multiple receivers broadcast network was investigated in[23,24].It is found that the greater the number of receivers,the smaller the average delay[23].The average delay can reflect the overall performance of the system[25,26].Although the average delay is meaningful for performance analysis in many scenarios,it cannot provide the worst-case delay[27].However,sometimes the worst-case delay should be considered instead of the average delay.The delay distribution of random linear network coding was extensively studied in[22,24].They mainly analyzed the delay probability distribution in the single-source multi-sink network with erasure channels[27].Su et al.proposed a scheme to balance the delay and complexity of random linear network coding in wireless broadcast networks[28].They only considered a single-hop broadcast system.The source node directly broadcasts the information to sink nodes.This scheme is limited due to the restrictions on communication distance in practice.

In this paper,we considered a system model that is more in line with the practical application of vehicleto-vehicle(V2V)communication.Multiple vehicles,which work as the source nodes,carry the information requested by a vehicle behind them,which works as the single sink node.We consider the problem of how other vehicles may help one vehicle with respect to low latency.With the assumption that each vehicle is able to broadcast information to all vehicles with some distance,we can model the scenario as a multi-source single-sink wireless broadcast network.Note that the distances between vehicles changes rapidly and the vehicle communication range is limited,the routes from the source nodes to the sink node may need assistance from some intermediate nodes.Since the vehicle is moving,it is necessary to shorten the communication delay to ensure that the transmission of information is completed within the communicable range.Otherwise,the costs of maintaining the communications between the source nodes and the sink node will increase significantly.As the vehicles are constantly moving,the network topology composed of vehicle nodes is changing by time.Random linear network coding does not need to know the topology of the network,and is suitable for this scenarios.Therefore,it has strong practicability for V2V networks.We analyzed the impact of packet loss rate and packet sending queue length on the delay probability distribution.In addition,we analyzed the impact of the finite field size on the random linear network coding.Through the above analysis,we can not only obtain the average transmission delay,but also the possibility of different delays and the worst case delay.We can also optimize the model based on the factors such as the length of the sending queue.

The main contributions of this paper includes:i)it is shown that the random linear network coding can effectively reduce the latency in V2V networks,compared to the non-coding scheme;ii)the reduction in latency by network coding is still significant when channel qualities are bad;iii)it is shown that the increase of the generation size fastens the transmission,while the reduction of the network coding field size can further reduce the transmission latency,as expected.

The remainder of this paper is organized as follows.§II introduces the system model and§III formulates the various transmission states.In § IV,we analyze the performance in the respect of generation probability,receiving probability,and time delay.An optimized protocol is presented in§V.We compare the coding scheme and non-coding scheme in§VI.§VII concludes the paper.

II.SYSTEM MODEL

We consider a multi-source single-sink V2V wireless broadcasting network.Wireless channel may lose packets(with Bernoulli packet loss).The source nodes are assumed to transfer packets to the sink node via some intermediate nodes as relays.Each source node has a sending queue of lengthM,which can storeMdifferent raw packets.In a time slot,each source node sends one packet.Without network coding,each source node will randomly select a raw packet from the sending queue to send.If we apply random linear network coding at each source node,Mraw packets are encoded into an encoded packet.As Figure 1 shows,msource nodes can broadcast a total ofmencoded packets tonintermediate nodes.Each intermediate node get packets from source nodes,and then send packets to the sink node.Each intermediate node is also assumed to send one packet in a time slot.Random linear network coding is also applied at each intermediate node before sending packet.Sink node receives the encoded packets from intermediate nodes.

Suppose each source node’s sending queue is the same,they all storeMdifferent raw packets.We called theseMraw packets as a generation.As Figure 1 shows,all sending queues will be updated to transmit next generation when the sink node receives(or decode)Mraw packets.Since we applied random linear network coding at source nodes and intermediate nodes,when the sink node receives sufficient number of linearly independent packets,decoding is performed.

Figure 1.System model:m source nodes communicate with a sink node through n intermediate nodes.Nodes in a circle can communicate directly.

Figure 2.The status change of sink node B(M raw packets,two intermediate nodes).

III.RECEIVER′ S DYNAMIC STATES

According to the decoding process of random linear network coding,sink node needs to receiveMlinearly independent encoded packets to decode the originalMdata packets.If sink node has receivedilinearly independent encoded packets,the status of the sink node isi.

At the beginning,the source nodes communicate with the intermediate nodes.The status of the sink node is 0.We call this state the initial state.When the intermediate nodes receive the data packets,they start sending encoded packets to the sink node.Suppose the current state of the sink node isi.If the encoding coefficient vector of the data packet is linearly dependent to the encoding coefficient vector of the previously received encoding data packet by the sink node,we call the data packet a linearly dependent packet.In a time slot,if sink node does not receive packet or receives linearly dependent packets,the status of the sink node will not change.If sink node receivesk(0

Lemma 1.Receiver’s state dynamics is a Markov process.

Proof.The status of the sink node isstate(t)at slott,state(t)∈[0,1,2,...,M −1,M].

The status of the sink node isstate(t+ 1)at slott+ 1,state(t+ 1)∈[state(t)+0,state(t)+1,...,state(t)+n]andstate(t+1)∈[0,1,2,...,M −1,M].

The status of the sink node at slott+1 depends on the number of linearly independent packets received in the time slott+1,and whether the received data packets are linearly independent or not is only related to the state of the sink node at slott.

The status of the sink node satisfies Markov property:P{state(t+ 1)|state(t),state(t −1),...,state(1)}=P{state(t+1)|state(t)}.Thus,the receiver’s state dynamics is a Markov process.

IV.PERFORMANCE ANALYSIS

We hope that the number of time slots required to transmit some packets from source nodes to the sink node is as few as possible.Therefore,we choose the number of time slots to express the system performance.The system needsTtime slots to transmitMdata packets.In other words,the sink node receivesMlinearly independent data packets afterTtime slots.In the case of different packet loss rates,different sending queue lengths and different network sizes,we analyzed the changes in the number of time slots for the system to transmit packets.

According to Lemma 1,the current state of the sink node only depends on the state of the previous time slot and the number of linearly independent data packets received in this time slot.There is no need to consider the status of the sink node in earlier time slots.Therefore,when analyzing the generation probability,we only need to analyze the linear dependence between the received data packets in this time slot and the existing data packets.

4.1 Generation Probability

As Figure 1 shows,we applied random linearly network coding at each source node.Encoded packets are as follows:

Figure 3.In the case of different numbers of packets received by the sink node,the generation probability varies with the Galois field size(where the number of raw packets M=7,the number of intermediate nodes n=3,Galois field size q=[4,8,16,32,64,128,256],and the number of packets received by the sink node i=[1,2,3,4,5,6]).

whereP(Aα)is the encoded packet sent by the source nodeAα,rβis theβth raw packet in the sending queue,andaα(β)is the coding coefficient of theαth source node’s theβth raw packet,whenα∈[1,m],andβ∈[1,M].

In order to simplify the study,we assumed that all wireless channel between source nodes and intermediate nodes are ideal.Each source node or intermediate node only needs one time slot to encode and send packets.Each intermediate node receivesmencoded packets from source nodes after a time slot.They will recodemencoded packets before sending them.

We denote the generation probability as the probability that the recoding packets are linearly independent.In other words,the recoding packets are not only linearly independent of the packets received by the sink node,but also linearly independent of each other.

4.1.1 Receiver′s Statei ≤M −n

The saturation state of the sink node isi=M,so the maximum value of state transition isnwhen the status of the sink nodei ≤M −n.Allnintermediate nodes recode the receivedmencoded packets.Recoding packets are as follows:

The matrix form is as follows:

whereP(Cγ)is the recoding packet sent by the intermediate nodeCγ,bγαaα(β)(orcγ(β))is the recoding coefficient of theγth intermediate node’s theβth raw packet,Cn×Mis the recoding coefficient matrix,and RM×1is the raw packet matrix,whenγ∈[1,n],α∈[1,m]andβ∈[1,M].

The sink node has receivedilinearly independent packets.Received packets are as follows:

The matrix form is as follows:

whereP(Bδ)is theδth received packet,dδ(β)is the coefficient of theδth received packet’sβth raw packet,Di×Mis the coefficient matrix,and RM×1is the raw packet matrix,whenδ∈[1,i],andβ∈[1,M].

We assumed that the sink node received everyP(Cγ).Received packets matrix form is as follows:

where E(i+n)×Mis the coefficient matrix.

The generation probability is equivalent to the probability that E(i+n)×Mis a full-rank matrix(orrank(E)=i+n)wheni ≤M −n.

Theorem 1.Generation probability is of the form:.

whereiis the number of linearly independent packets that the sink node has received,qis the Galois field size of random linearly network coding,Mis the number of raw packets,andnis the number of intermediate nodes(or recoding packets).

Proof.Please refer to the Appendix A for detailed proof.

4.1.2 Receiver′s Statei>M −n

The saturation state of the sink node isi=M,so the maximum value of state transition isM −iwhen the status of the sink nodei>M −n.If allnintermediate nodes participate in re-encoding,there must be at leastn −(M −i)linearly related recoding packets.In other words,there are at leastn −(M −i)redundant packets.Therefore,we consider only allowingM −iintermediate nodes to participate in recoding.Recoding packets are as follows:

whereP(Cγ)is the recoding packet sent by the intermediate nodeCγ,C(M−i)×Mis the recoding coefficient matrix,and RM×1is the raw packet matrix,whenγ∈[1,M −i].

We assumed that the sink node received everyP(Cγ).Received packets matrix form is as follows:

where EM×Mis the coefficient matrix.

The generation probability is equivalent to the probability that EM×Mis a full-rank matrix(orrank(E)=M)wheni>M −n.

Theorem 2.Generation probability is of the form:,when i>M-n.

whereiis the number of linearly independent packets that the sink node has received,qis the Galois field size of random linearly network coding,Mis the number of raw packets,andnis the number of intermediate nodes(or recoding packets).

Proof.Please refer to the Appendix A for detailed proof.

Combining Theorem 1 and Theorem 2,we get the generation probability is as follows:

As Figure 3 shows,wheni ≤M −n,as the Galois field sizeqincreases,the generation probability increases.When Galois field sizeqis constant,as theiincreases,the generation probability decreases.Wheni >M −n,as the Galois field sizeqincreases,the generation probability increases.When Galois field sizeqis constant,as theiincreases,the generation probability increases.When the Galois field is large enough(GF(256)),the generation probability is close to 1(≈0.996)for eachi.

Proof.Please refer to the Appendix B for detailed proof.

4.2 Receiving Probability

Wireless channels between intermediate nodes and sink node may lose packets(with Bernoulli packet loss).The intermediate nodes sendn(orM −i)recoding packets to the sink node in each time slot.The probability that the sink node receiveskrecoding packets successfully is as follows:

wherekis the number of recoding packets received by sink node,peis the packet loss rate of wireless channels between intermediate nodes and sink node.

4.3 Time Delay Analysis

When the Galois field is large enough(GF(256)),the generation probability is always close to 1(≈0.996).In other words,each packet sent by the intermediate nodes is linearly independent in each time slot when the Galois field is large enough.Therefore,the state transition depends almost only on the receiving probability.

According to Figure 2,the sink node in each time slot will have different state transitions with different probabilities.We construct a transition matrix.This matrix composed of the probability of the sink node’s state transfer k-step in each time slot.

Case 1.(0≤i ≤M −n)

where.

Case 2.(M −n

where.

Note:Differenticorresponds to different P′and different.For example,,wheni=M −n+1;,wheni=M −n+2.

All row vectors P and P′form the transition matrix:

Each row of the transition matrixfrom top to bottom corresponds to P(or P′)whenigoes from 0 toM −1.

After a time slot,the status of the sink node may change,that is,the number of linearly independent data packets that the sink node has received changes.We constructed a state matrix.In a certain time slot,the probability that the sink node is in various possible states forms a state matrix.

We usecompletion probabilityto denote the probability that the sink node has receivedMlinearly independent packets(or one generation of packet transmission is completed)at time slot t.

We have completion probabilitywhereη∈[0,M −1]andt∈[1,+∞).

As Figure 4 shows,whenM=7,n=3 andpe=0.05,the completion probability distribution is concentrated which reaches 0.9340 in the fourth time slot.WhenM=15,n=4 andpe=0.05,the probability of completing the transmission in the fifth time slot is 0.7413,and the probability of completing the transmission in the sixth time slot is 0.2432.The sum of the above completion probabilities has reached 0.9845.As the packet loss rate increases,the completion probability distribution gradually diverges.WhenM=7,n=3 andpe=0.5,the completion probability is 0.2381 in the 6th time slot,and the probability is 0.2022 in the 7th time slot.WhenM=15,n=4 andpe=0.5,the completion probability is approximately 0.2 from the eighth time slot to the eleventh time slot,and the distribution is even.

Figure 4.Completion probability distribution under different packet loss rates pe =[0.05,0.1,0.2,0.5].

In the same communication scenario,the lower the packet loss rate,the earlier the system can complete the transmission ofMdata packets with a greater probability.For example,whenM=7,n=3 andpe=0.05,the communication system completes the transmission task ofMdata packets in four time slots with a probability of 93.4%.In other words,the probability that more time slots are needed to transmit data packets will be very low.Because the data packet transmission has been completed in four time slots,the system does not need to continue to transmit theseMdata packets in the fifth time slot.

As Figure 5 shows,whenM=7,n=3 andpe=0.05,the cumulative completion probability reaches 0.9966 in the 5th time slot.In other words,source nodes and the sink node transmit a generation of packets within five time slots with high probability.As the packet loss rate increases,the cumulative completion probability distribution curve becomes flat gradually.Whenpe=0.5,the cumulative completion probability only reaches 0.2466 in the fifth time slot.It only reaches 0.9512 in the tenth time slot.Obviously,the higher the packet loss rate,the fewer packets the sink node receives in each time slot,so the more time slots are required to complete the transmission.WhenM=15,n=4 andpe=0.2,The cumulative completion probability is only 0.1196 in the fifth time slot,which means that the probability of the system completing the transmission ofMdata packets in five time slots is extremely low.Therefore,there is a high probability that more time slots are needed to continue to transmit data packets.Between the fifth time slot and the sixth time slot,the cumulative completion probability rises fastest,which means that in this communication scenario,the probability of completingMdata packet transmissions in the sixth time slot is the greatest.In the eighth time slot,the cumulative completion probability has reached 0.9781,which does not mean that the probability of completing the transmission ofMdata packets in the eighth time slot is 0.9781.In the eighth time slot,there is a high probability that the transmission has been completed,but the transmission may have been completed in an earlier time slot.The lower the packet loss rate,the narrower the distribution range of the time delay,and the smaller the variance of the time delay.

Observing from both Figure 4 and Figure 5,it can be found that there is a situation where the completion probability is 0 in the first few time slots.In the first time slot,the source nodes communicate with the intermediate nodes.Therefore,the sink node has not received any data packets yet.It is impossible to complete the transmission in the first time slot.Starting from the second time slot,the intermediate nodes start to communicate with the sink node.After each time slot,assuming there is no packet loss,the sink node can receive at mostndata packets.Therefore,the sink node needs at leasttime slots to receiveMdata packets.Therefore,the completion probability is 0 in the firsttime slots.Take one of the communication scenarios(whereM=7,n=3)as an example.The completion probability is 0 in the first three time slots,so the cumulative completion probability is also 0.

Figure 5.Cumulative completion probability distribution under different packet loss rates pe =[0.05,0.1,0.2,0.5].

In order to reflect the overall trend of the impact of packet loss rate on time delay,we calculated the average time delay under different packet loss rates.

Definition 1.(Average time delay).The average timedelay of transmitting M packets,.

As Table 1,as the packet loss rate increases,so does the average time delay.If we want to shorten the time delay,we should try to optimize the wireless channel performance to reduce the packet loss rate.Although the packet loss rate increases rapidly,but the time delay increases slowly,it can be inferred that the robustness of the coding scheme is better.

Table 1.Average time delay under different packet loss rates in time slots.

We analyzed the impact of generation sizeMon time delay.Keepingpeandnunchanged,we increaseMto observe the change of unit time delay.As Figure 6,whenM=7,it is possible to complete the transmission from the fourth time slot,and whenM=15,it is possible to complete the transmission from the sixth time slot.The larger the generation size(the more raw packets),the more linearly independent packets required for the sink node to decode.However,the number of intermediate nodes is constant,so more time slots are needed to transmit packets.

Figure 6.Cumulative completion probability distribution under different generation sizes.pe =0.1,n=3 and M=[7,9,11,13,15].

Although the transmission time delay becomes longer,more packets are transmitted.Therefore,it is of little significance to observe the delay of transmitting a generation of packets.We choose to observe unit time delay.As Table 2,as the generation size becomes larger,the average time delay increases,but the unit time delay decreases.Therefore,if we want to transmit all the packets quickly,we should try to increase the generation size under the limit of the source node’s storage capacity.

Table 2.Unit time delay under different generation sizes in time slots.

Definition 2.(Unit time delay).The average time delay of transmitting a packet,.

We analyzed the impact of network size on time delay.We adjust the network size by changing the number of intermediate nodes.The application background of this paper is vehicle-to-vehicle communication on highways,so the number of intermediate nodes is generally less than 10.This means that the network size will not be very large.KeepingpeandMunchanged,we increasento observe the change of time delay.As Figure 7 shows,whenn=2,it is possible to complete the transmission from the ninth time slot,and whenn=5,it is possible to complete the transmission from the fourth time slot.Asnincreases,the cumulative completion probability curve shifts to the left,which means that the system can complete the transmission of data packets faster.

Figure 7.Cumulative completion probability distribution under different network sizes.pe =0.1,M=15 and n=[2,3,4,5].

When analyzing the impact of packet loss rate,sending queue length,and network size on the delay above,we have analyzed the average delay more.This kind of delay analysis is more suitable for the transmission of non-urgent information such as media.However,for emergency messages such as car accident warning,once the probability of the worst-case delay increases slightly,it will bring huge losses.Therefore,the worst-case delay situation should be avoided as much as possible.Observing Figure 4,we can find that the lower the packet loss rate,the lower the probability of the worst-case delay.Observing Figure 7 we can find that the more intermediate nodes,the earlier the curve value can reach 1,which means the lower the probability of the worst-case delay.Therefore,reducing the packet loss rate or increasing the number of intermediate nodes will help reduce the probability of the worst-case delay.

Figure 8.In the case of different numbers of intermediate nodes,the minimum of generation probability varies with the Galois field size.

V.OPTIMIZED PROTOCOL

According to § IV,We apply random linear network coding in the process of packet transmission.If we want to shorten the time delay,we should reduce the packet loss rate,increase the Galois field size,and increase the generation size.However,neither the storage capacity of the source node nor the packet loss rate of the channel can be optimized by the coding scheme.We consider to optimize the scheme by adjusting the Galois field size.We chooseGF(256)to generate random linear network codes,so that the generation probability reaches 0.996.AlthoughGF(256)is achievable,the larger the Galois field size,the more space is needed to store the code vector and the more time to decode.Therefore,the time delay will increase.According to the proof in Appendix B,the generation probability takes the minimum value wheni=M−n.The generation probability will be affected by the number of intermediate nodes.Therefore,we consider dynamically selecting the Galois field size according ton.It can not only make the generation probability large enough,but also make the Galois field size as small as possible.

For example,the lower bound of the generation probability is given as Ω when the number of intermediate node isn.According to the proof in Appendix B:

∵GF(q),whereq=2k

∴ChooseGF(qmin)as follows:

As Figure 8 shows,when the Galois field size is determined,as the number of intermediate nodes increases,the minimum of generation probability decreases.When the number of intermediate nodes is determined,as the Galois field size increases,the minimum of generation probability increases.The growth rate is fast betweenGF(2)andGF(8).The minimum of generation probability reaches 0.9 whenGF(16).AfterGF(16),the growth rate becomes slow.It can be seen that whenq=16,linear independent packets can already be generated with great probability.For example,GF(qmin)=GF(32)whenn=3 and Ω=95%.

The scenario studied in this paper is a vehicle-tovehicle communication system running on the road.For each vehicle,there are usually less than ten vehicles within its communication range.We first calculate the minimum of generation probability(Pmin)when the number of intermediate vehicles isn(n∈[1,9])and the Galois field size isq=2m(m∈[1,8]).Then we upload each set of data[n,q,Pmin]to the network platform of the Internet of Vehicles.The roadside unit collects the number of intermediate vehicles(n)and the required generation probability(Pmin)in the communication scene,and uploads them to the network platform.The network platform determines the minimum Galois field size(qmin)that meets the requirements according tonandPmin,and sends the result to the roadside unit.The roadside unit then informs the Galois field size(qmin)of all vehicles in the communication scene,and the vehicle performs coding and decoding operations in this coding domain.The above is the process of random linear network coding in the dynamic coding domain with the help of the network platform and the roadside unit in the vehicle-to-vehicle system.

VI.CODING VS.NON-CODING

We use random linear network coding to reduce time delay.Therefore,we need to compare coding and noncoding schemes to prove that coding schemes can reduce time delay.The non-coding scheme is also used in a multi-source single-sink V2V wireless broadcasting network.The system model is exactly the same as Figure 1.Without coding,each source node randomly selects one ofMraw packets,and then broadcasts it to all intermediate nodes.Due to the randomness of selecting packets,msource nodes may select the same raw packet.Each intermediate node receivesmraw packets,then randomly selects one from themraw packets,and then sends it to the sink node.In the above,the ”store-and-forward”method of the traditional relay system is adopted at the intermediate node.In the simulation,we assume that all wireless channels are ideal.Each time the above process is repeated,the sink node will receivenpackets.Of course,thesenpackets are not necessarily different from each other,and there is even a high probability that two or more packets are the same.Repeat the above process until the sink node receivesMdifferent raw packets.The above is the application process of the non-coding scheme in the same system model.Taking into account the randomness of sending packets in the non-coding scheme,we repeated the simulation one hundred thousand times and then took the average value as the time delay.

As Table 3 indicates,in the same communication background,the time delay of the non-coding scheme is much longer than that of the coding scheme.Even when the coding scheme is simulated,the packet loss rate is 0.5;when the non-coding scheme is simulated,the channels are ideal.The time delay of the noncoding scheme is still much longer than that of the coding scheme.Adopting the coding scheme can not only shorten the time delay,but also be more robust to non-ideal channels.

Table 3.Time delay comparison between coding and noncoding schemes in time slots.

VII.CONCLUSION

In this paper,we study the latency reduction problem of a multi-source single-sink V2V network with wire-less broadcasting channels.In the traditional storeand-forward relay mode,the time delay is huge,and the channel quality affects the time delay significantly.To solve these problems,we applied random linear network coding in such a V2V network.We found that the coding scheme can reduce the time delay,and the time delay is less affected by non-ideal channels.The generation-by-generation packet sending method was used and it was found that the increase of the generation size helps the transmission in terms of speed.At the same time,we have further optimized the coding scheme by reducing the Galois field size of random linear network coding as much as possible,which can further reduce the time delay and computational overhead.

ACKNOWLEDGEMENT

This work was supported in part by the Guangdong Basic and Applied Basic Research Foundation under Key Project 2019B1515120032,in part by the National Science Foundation of China(NSFC)with grant no.61901534,in part by the Science,Technology and Innovation Commission of Shenzhen Municipality with grant no.JCYJ20190807155617099,in part by the University Basic Research Fund 20lgpy43,in part by the Guangdong Natural Science Foundation of Grant No.2019A1515011622 and the Foundation of Grant No.2019-JCJQ-JJ-411.

These authors contributed equally:Tiantian Zhu,Congduan Li.

APPENDIX A

Wheni ≤M −n,the proof of the generation probability is as follows:

Step 1:According to the definition of random linear network coding,M raw packets are encoded on the Galois field(GF(q))to generate an encoded packet,and there areqM −1 situations in total.At this time,it is not considered whether the encoded packet is linearly independent.

Step 2:If an encoded packet is linearly correlation of the received i packets,there are a total ofqi −1 cases.

Step 3:Combining step1 and step2,if it is desired to generate an encoded packet linearly independent of the received i packets,there are(qM −1)−(qi −1)=qM −qicases in total.

Step 4:The n intermediate nodes generate n encoded packets in a time slot.n encoded packets constitute a combination.There aresituations in this combination.

Step 5:If the i+n packets at the sink node are linearly independent of each other after the sink node receives n encoded packets.There are a total ofcases for the combination of n encoded packets.

Step 6:Combining step4 and step5,generation probability:

Step 7:SimplifyPge=nin step 6 as follows:

Take the logarithm of both sides of the Eq.(1):

∵qM >>n

Wheni>M −n,the proof of the generation probability is as follows:

SimplifyPge=M−ias follows:

APPENDIX B

When Galois field size q,the number of raw packets M and the number of intermediate nodes n are all constant,.In other words,as i increases,Pge=ngradually decreases wheni ≤M −n.As i increases,Pge=M−igradually increases wheni>M −n.

Step 1:i ↑ ⇒l ↑ ⇒M −l ↓ ⇒qM−l ↓ ⇒.

Step 2:∵M −n

whenl=i+1:

Step 3:Combining step1 and step2,: