# UAV-Assisted Sensor Data Dissemination in mmWave Vehicular Networks Based on Network Coding

Authors: Shidong Huang; Chuanhe Huang; Dongfang Wu; Yabo Yin; M. Wasim Abbas Ashraf; Bin Fu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Due to good maneuverability, UAVs and vehicles are often used for environment perception in smart cities. In order to improve the efficiency of sensor data sharing in UAV-assisted mmWave vehicular network (VN), this paper proposes a sensor data sharing method based on blockage effect identification and network coding. The concurrent sending vehicles selection method is proposed based on the availability of mmWave link, the number of target vehicles of sensor data packet, the distance between a sensor data packet and target vehicle, the number of concurrent sending vehicles, and the waiting time of sensor data packet. The construction method of the coded packet is put forward based on the status information about the existing packets of vehicles. Simulation results demonstrated that efficiency of the proposed method is superior to baseline solutions in terms of the packet loss ratio, transmission time, and packet dissemination ratio.


---

## Body

## 1. Introduction

With the development of 5G technology, the arrival of 6G communication technology will further promote the process of smart city. Application of smart transportation, smart logistics, smart medical care, and smart manufacturing and other related technologies have greatly changed people’s lifestyles. The combination of 5G and related technologies such as remote control, remote operation, and machine vision [1, 2] will make digital workshops and smart factories a reality. 5G combined with unmanned vehicle transportation and intelligent robotics will enable unmanned monitoring and scheduling of the logistics process [3, 4], which will greatly improve current urban logistics efficiency. Application of 5G in intelligent traffic control and autonomous driving makes road condition monitoring, congestion guidance, intelligent parking, high-precision positioning, and emergency accident handling more efficient and convenient [5, 6]. With the aid of 5G communication technology, real-time monitoring of patient, remote surgery, and nursing guidance will become a reality [7, 8], and people can enjoy higher quality of medical services.In various application scenarios of smart city, relevant sensing technologies play a very important role. In order to achieve efficient urban environmental data sensing, vehicle-based data sensing is a common solution; it plays an important role in the construction of smart city. Relevant equipment can be installed on the vehicle to sense the traffic information on the road, and an efficient traffic scheduling scheme can be made based on the current traffic information [9, 10]. Different sensors are installed on the vehicle to sense the current road and obstacles in real time [11, 12], which is the current implementation solution for autonomous driving. Sensors and corresponding devices installed on multiple vehicles can be applied to identify and locate the persons who owned the special identity [13, 14], which can make the urban life safer and more convenient.Sensing technology based on vehicular networks plays an important role in the construction of smart city. Multiple vehicles cooperating with each other to accomplish a specific sensing task is very common, and the sharing of sensing data among multiple vehicles can achieve a larger range of environmental sensing and monitoring. Vehicles can take more effective control measures based on these sensing data. In order to improve the sharing efficiency of sensor data, the paper proposes a UAV-assisted sensor data sharing scheme for mmWave VN based on link availability identification and network coding technology to improve the data distribution efficiency. The main contributions of this paper are as follows.(i)
The paper proposes the concurrent sending vehicles selection method based on the availability of mmWave link, the number of target vehicles, the distance between sensor data packet and requested vehicles, and the waiting time of sensor data packet, which can improve the efficiency of sensor data sharing(ii)
To improve the efficiency of sensory data sharing, the paper designs a data distribution method based on network coding techniques. Construction method of coded packet is proposed, which can improve the efficiency of the multiple antennas in mmWave VN(iii)
Simulation results showed that the proposed method improves the efficiency of sensor data sharing of mmWave VN in term of time consumed and packet loss ratioThe rest of the paper is organized as follows. Section2 introduces the related work; Section 3 introduces the system model. Section 4 introduces sensor data dissemination method based on network coding. Simulation and result discussion are presented in Section 5; Section 6 concludes this paper.


## 2. Related Work

### 2.1. Data Sensing Based on VN

Vehicles as a carrier of sensors for sensing the urban environment is a common solution. To accomplish the data collection from sensors deployed in different locations in urban, data forwarding schema based on the probability of a vehicle to reach a road side unit was proposed in the literature [15]; a distributed age-aware data collection scheme was proposed based on Lyapunov optimization technique in the literature [16], including a sampling method with a threshold at the source vehicle and a data forwarding strategy based on learning. For the traffic data collection in urban scene, P. Salvo et al. proposed a traffic data collection method based on LTE and V2V [17], and the way of data collection can switch between LTE and V2V according to the vehicle density.In order to meet the requirements of ITS applications for accuracy and timeliness of sensor data, while achieving efficient use of bandwidth resources, W. Nie et al. formalized the problem as the minimized communication overhead problem [18] and proposed two different solutions with mixed-integer linear programming and deviation-detection method. An adaptive vehicle clustering mechanism and online parameter adjustment method were designed in [19] to satisfy the ITS requirements for accuracy and timeliness of sensor data.As to sensor data sharing in vehicular networks with the mmWave communication technology, X. Chen et al. proposed the graph-based routing selection mechanism [20], and heading vehicles are responsible for the selection of the transmission and receiving vehicles. To solve the problem that the communication performance is vulnerable to blocking and interference effects with the mmWave in VNs, a distributed dissemination mechanism was proposed with the consideration of blocking and interference effect to improve the efficiency of sensor data distribution [21]. For efficient data access in urban vehicle sensing networks, hybrid network architecture based on dedicated short-range communication and vehicular ad hoc network was proposed in the literature [22], and duplicated data suppression mechanism was designed based on signaling procedure and executed in distributed way among vehicles. As to UAV-assisted data dissemination in V2X networks, dynamic trajectory scheduling algorithm was designed for UAV to complete the data caching in the proactive caching phase, and relay selection method was proposed to improve the efficiency of data dissemination through V2V and V2I in the data dissemination phase [23]. Y. Meng et al. proposed a network architecture based on information-centric networking [24] and designed a distributed data caching strategy to alleviate the system pressure caused by user requests. Due to the good maneuverability, UAVs are often used in different IoT applications.


### 2.2. UAV-Assisted Sensor Data Collection and Dissemination

In UAV-assisted data collection scenarios, UAV deployment problem was studied in the literature [25] to maximize the available time of the user uplink in disaster relief scenarios; user devices were clustered and then each cluster was served by one UAV. The age of information and the power consumption of UAV are taken into consideration in the literature [26] and the data collection problem was formalized as a mixed-integer linear programming problem to be solved. To achieve efficient data collection in IoT, UAV-assisted data collection with NOMA was proposed in [27], and the location of UAV, sensor grouping, and power control are jointly considered in the solution. As to the scenario that sensors located on a straight line, the data collection intervals, the UAV’s speed, and the sensors’ transmit powers needed to be considered simultaneously to minimize flight time of the UAV to complete the data collection [28]. For UAV-assisted integrated sensing and communication system, a new sensing and communication mechanism was designed in the literature [29] to maximize the user available rate with the joint optimization of UAV trajectory, transmit precoder, and sensing start instant.As to UAV-assisted sensor data distribution scenario, the flight track and speed, sending power, and data demand of sensors were needed to be considered simultaneously to minimize the data distribution time [30, 31]; the joint optimization problem was simplified into a convex optimization problem for solution. Multi-UAV-assisted data distribution for sensors in post-disaster areas was studied in the literature [31]. To realize the efficient data distribution to the receiving nodes within a specific region, file dispatching scheme based on graph theory with nonorthogonal multiple access (NOMA) was proposed in [32]; ground users and UAV can share the time-frequency resource block simultaneously. In the scenario where the UAV and the primer user shared the spectrum resources to distribute data to the sensors, to maximize the minimum number of bits of data received by the sensors while ensuring the communication quality of the primer user, the optimization problem was formalized as a mixed-integer non-linear program [33] and the corresponding convex approximation algorithm was designed to solve it.The blocking effect in mmWave VN is considered in the above related work, but the network coding technique is not introduced in the solution. In this paper, we design a new UAV-assisted sensing data distribution scheme based on link availability identification and network coding techniques. Concurrent sending vehicles selection mechanism and coded packet construction method are proposed in this paper to improve the efficiency of sensor data sharing in mmWave VN.


## 2.1. Data Sensing Based on VN

Vehicles as a carrier of sensors for sensing the urban environment is a common solution. To accomplish the data collection from sensors deployed in different locations in urban, data forwarding schema based on the probability of a vehicle to reach a road side unit was proposed in the literature [15]; a distributed age-aware data collection scheme was proposed based on Lyapunov optimization technique in the literature [16], including a sampling method with a threshold at the source vehicle and a data forwarding strategy based on learning. For the traffic data collection in urban scene, P. Salvo et al. proposed a traffic data collection method based on LTE and V2V [17], and the way of data collection can switch between LTE and V2V according to the vehicle density.In order to meet the requirements of ITS applications for accuracy and timeliness of sensor data, while achieving efficient use of bandwidth resources, W. Nie et al. formalized the problem as the minimized communication overhead problem [18] and proposed two different solutions with mixed-integer linear programming and deviation-detection method. An adaptive vehicle clustering mechanism and online parameter adjustment method were designed in [19] to satisfy the ITS requirements for accuracy and timeliness of sensor data.As to sensor data sharing in vehicular networks with the mmWave communication technology, X. Chen et al. proposed the graph-based routing selection mechanism [20], and heading vehicles are responsible for the selection of the transmission and receiving vehicles. To solve the problem that the communication performance is vulnerable to blocking and interference effects with the mmWave in VNs, a distributed dissemination mechanism was proposed with the consideration of blocking and interference effect to improve the efficiency of sensor data distribution [21]. For efficient data access in urban vehicle sensing networks, hybrid network architecture based on dedicated short-range communication and vehicular ad hoc network was proposed in the literature [22], and duplicated data suppression mechanism was designed based on signaling procedure and executed in distributed way among vehicles. As to UAV-assisted data dissemination in V2X networks, dynamic trajectory scheduling algorithm was designed for UAV to complete the data caching in the proactive caching phase, and relay selection method was proposed to improve the efficiency of data dissemination through V2V and V2I in the data dissemination phase [23]. Y. Meng et al. proposed a network architecture based on information-centric networking [24] and designed a distributed data caching strategy to alleviate the system pressure caused by user requests. Due to the good maneuverability, UAVs are often used in different IoT applications.


## 2.2. UAV-Assisted Sensor Data Collection and Dissemination

In UAV-assisted data collection scenarios, UAV deployment problem was studied in the literature [25] to maximize the available time of the user uplink in disaster relief scenarios; user devices were clustered and then each cluster was served by one UAV. The age of information and the power consumption of UAV are taken into consideration in the literature [26] and the data collection problem was formalized as a mixed-integer linear programming problem to be solved. To achieve efficient data collection in IoT, UAV-assisted data collection with NOMA was proposed in [27], and the location of UAV, sensor grouping, and power control are jointly considered in the solution. As to the scenario that sensors located on a straight line, the data collection intervals, the UAV’s speed, and the sensors’ transmit powers needed to be considered simultaneously to minimize flight time of the UAV to complete the data collection [28]. For UAV-assisted integrated sensing and communication system, a new sensing and communication mechanism was designed in the literature [29] to maximize the user available rate with the joint optimization of UAV trajectory, transmit precoder, and sensing start instant.As to UAV-assisted sensor data distribution scenario, the flight track and speed, sending power, and data demand of sensors were needed to be considered simultaneously to minimize the data distribution time [30, 31]; the joint optimization problem was simplified into a convex optimization problem for solution. Multi-UAV-assisted data distribution for sensors in post-disaster areas was studied in the literature [31]. To realize the efficient data distribution to the receiving nodes within a specific region, file dispatching scheme based on graph theory with nonorthogonal multiple access (NOMA) was proposed in [32]; ground users and UAV can share the time-frequency resource block simultaneously. In the scenario where the UAV and the primer user shared the spectrum resources to distribute data to the sensors, to maximize the minimum number of bits of data received by the sensors while ensuring the communication quality of the primer user, the optimization problem was formalized as a mixed-integer non-linear program [33] and the corresponding convex approximation algorithm was designed to solve it.The blocking effect in mmWave VN is considered in the above related work, but the network coding technique is not introduced in the solution. In this paper, we design a new UAV-assisted sensing data distribution scheme based on link availability identification and network coding techniques. Concurrent sending vehicles selection mechanism and coded packet construction method are proposed in this paper to improve the efficiency of sensor data sharing in mmWave VN.


## 3. UAV-Assisted Data Sensing Based on Vehicular Networks

### 3.1. System Model

Assuming that vehicles are equipped with sensing device and millimeter wave antenna, sensing device is used to sense the environment, such as road conditions, accident scene, and emergency vehicles, millimeter wave antenna is used to share the sensor data with other vehicles, and vehicles exchange the sensor data with each other to obtain complete information about surrounding environment information. The information can be used to make decisions, such as avoiding traffic accident and congested roadways. The vehicles use mmWave directional antenna in D2D communication. One data transmission, there are up toM receiving vehicles that can receive the transmitted data simultaneously, because vehicles use multiple antennas to send data through M RF chains [21].Environment sensing procedure consists of two phases, sensing data acquisition and distribution. In the sensing stage, vehicle uses the sensors installed on the vehicle to sense the surrounding environment and then reports the sensor data to the UAV with the sub 6GHz link. In the stage of data dissemination, UAV gives the corresponding scheduling solution according to the sensor data owned by each vehicle located in its coverage and informs the vehicle with the scheduling solution, and then vehicles use mmWave communication technology to distribute or receive the sensor data in D2D at the corresponding time slot according to the scheduling solution distributed by UAV. The structure of the system is shown in Figure1. After this round of data sharing is completed, then vehicles perform a new round of data sensing and then report the sensor data to UAV, then UAV distributes new scheduling solution to vehicles, and vehicles share the new sensor data with each other to realize the perception of the surrounding environment.Figure 1
Scenario of UAV-assisted sensor data dissemination.


### 3.2. Link Availability Identification

In the stage of sharing sensor data, vehicles broadcast sensor data to neighbor vehicles with mmWave communication technology. The communication link is prone to blockage from the intermediate vehicles, which cause the failure of data transmission. So UAV needs to consider the link availability among the vehicles when make the scheduling decisions. As shown in Figure2, v1, v2, and v3 are all neighboring nodes of vs node, and the communication link between vs and v3 is blocked by vehicle v1, which results in v3 cannot receive the data sent by vehicle vs successfully.Figure 2
Link availability identification.Suppose the length of vehiclev1 is Lv, take the center position of vehicle v1 as the center and make a circle with Lv/2 as the radius; if the LOS path between the sending node and the receiving node passes through the circular area, then the link between the sending node and the receiving node is blocked by vehicle node v1; otherwise, the link is not blocked by vehicle v1, as shown in Figure 2, and v2 can successfully receive the data sent by vs node, but v3 cannot. Based on the coordinates of vs, v1, and v3, and the length Lv of v1, it can be determined whether the sending signal of vs is blocked by v1. Using this method, we can get the set of effective neighbor nodes and blocked neighbor nodes of any sending vehicle. During a time slot, multiple vehicles may send data simultaneously, vehicle may receive the data from multiple vehicles simultaneously, and the receiving noise of a vehicle can be got according to formula (1) [21]. Pj means the received power, Pi means the transmission power, Gi and Gi indicate the gain of transmit antenna and received antenna, respectively, L0 denotes the reference path loss at 1 m, and rij is the distance between the transmitting vehicle and receiving vehicle. If the received noise strength is greater than a threshold, the vehicle cannot receive any data correctly; the vehicle is regarded as the interfered node.


### 3.3. Formalization of Problem

When a vehicle broadcasts data, at mostM vehicles can receive the sent data. The data set consisting of sensed data of all vehicles is Ltotal=p1,p2,⋯,pK. In a certain time slot, sending vehicles are selected to send the corresponding coded data packets based on the existing data items located on vehicles and the link availability between vehicles. It is expected to spend the minimum number of time slots so that each vehicle gets all the data items in Ltotal, and the blockage and interference effects are needed to be considered during the schedule.Now assume that the existing data items on the vehicles are shown in Figure3. An edge between two nodes indicates that a link between the two vehicles is available. v1 owns the sensor data items set L1=p1,p5, v2 owns the sensor data items set L2=p1,p2,p3, v3 owns the sensor data items set L3=p3,p5, v4 owns the sensor data items set L4=p4, v5 owns the sensor data items set L5=p3,p5, v6 owns the sensor data items set L6=p6, v7 owns the sensor data items set L7=p1,p2, and the total sensor data item set Ltotal=p1,p2,p3,p4,p5,p6.Figure 3
Request state graph of vehicles.Assume that when a vehicle sends data, at most3 vehicles can receive the sent data. In the current time slot, v1 sends coded packet p1⊕p5, v2, v3, and v5 are the receiving vehicles, and v2 receives the coded packet p1⊕p5 and then can decode the required packet p5 with the existing packets p1; v3 decode the required packet p1 with the existing packet p5; v5 can decode the required packet p1 with the existing packet p5. Since v1 being transmitting state, v4 and v6 are in the state of interference; there are no other optional vehicles as sending vehicles in this time slot. In the next time slot, the existing packets state of vehicles has changed, and then the new sending nodes and corresponding encoded packets are scheduled according to the updated state information with the expectation that all vehicles can get all the sensor data items in Ltotal with the minimum number of time slots spent.
(1)Pj=PiGiGjL0rijα.


## 3.1. System Model

Assuming that vehicles are equipped with sensing device and millimeter wave antenna, sensing device is used to sense the environment, such as road conditions, accident scene, and emergency vehicles, millimeter wave antenna is used to share the sensor data with other vehicles, and vehicles exchange the sensor data with each other to obtain complete information about surrounding environment information. The information can be used to make decisions, such as avoiding traffic accident and congested roadways. The vehicles use mmWave directional antenna in D2D communication. One data transmission, there are up toM receiving vehicles that can receive the transmitted data simultaneously, because vehicles use multiple antennas to send data through M RF chains [21].Environment sensing procedure consists of two phases, sensing data acquisition and distribution. In the sensing stage, vehicle uses the sensors installed on the vehicle to sense the surrounding environment and then reports the sensor data to the UAV with the sub 6GHz link. In the stage of data dissemination, UAV gives the corresponding scheduling solution according to the sensor data owned by each vehicle located in its coverage and informs the vehicle with the scheduling solution, and then vehicles use mmWave communication technology to distribute or receive the sensor data in D2D at the corresponding time slot according to the scheduling solution distributed by UAV. The structure of the system is shown in Figure1. After this round of data sharing is completed, then vehicles perform a new round of data sensing and then report the sensor data to UAV, then UAV distributes new scheduling solution to vehicles, and vehicles share the new sensor data with each other to realize the perception of the surrounding environment.Figure 1
Scenario of UAV-assisted sensor data dissemination.


## 3.2. Link Availability Identification

In the stage of sharing sensor data, vehicles broadcast sensor data to neighbor vehicles with mmWave communication technology. The communication link is prone to blockage from the intermediate vehicles, which cause the failure of data transmission. So UAV needs to consider the link availability among the vehicles when make the scheduling decisions. As shown in Figure2, v1, v2, and v3 are all neighboring nodes of vs node, and the communication link between vs and v3 is blocked by vehicle v1, which results in v3 cannot receive the data sent by vehicle vs successfully.Figure 2
Link availability identification.Suppose the length of vehiclev1 is Lv, take the center position of vehicle v1 as the center and make a circle with Lv/2 as the radius; if the LOS path between the sending node and the receiving node passes through the circular area, then the link between the sending node and the receiving node is blocked by vehicle node v1; otherwise, the link is not blocked by vehicle v1, as shown in Figure 2, and v2 can successfully receive the data sent by vs node, but v3 cannot. Based on the coordinates of vs, v1, and v3, and the length Lv of v1, it can be determined whether the sending signal of vs is blocked by v1. Using this method, we can get the set of effective neighbor nodes and blocked neighbor nodes of any sending vehicle. During a time slot, multiple vehicles may send data simultaneously, vehicle may receive the data from multiple vehicles simultaneously, and the receiving noise of a vehicle can be got according to formula (1) [21]. Pj means the received power, Pi means the transmission power, Gi and Gi indicate the gain of transmit antenna and received antenna, respectively, L0 denotes the reference path loss at 1 m, and rij is the distance between the transmitting vehicle and receiving vehicle. If the received noise strength is greater than a threshold, the vehicle cannot receive any data correctly; the vehicle is regarded as the interfered node.


## 3.3. Formalization of Problem

When a vehicle broadcasts data, at mostM vehicles can receive the sent data. The data set consisting of sensed data of all vehicles is Ltotal=p1,p2,⋯,pK. In a certain time slot, sending vehicles are selected to send the corresponding coded data packets based on the existing data items located on vehicles and the link availability between vehicles. It is expected to spend the minimum number of time slots so that each vehicle gets all the data items in Ltotal, and the blockage and interference effects are needed to be considered during the schedule.Now assume that the existing data items on the vehicles are shown in Figure3. An edge between two nodes indicates that a link between the two vehicles is available. v1 owns the sensor data items set L1=p1,p5, v2 owns the sensor data items set L2=p1,p2,p3, v3 owns the sensor data items set L3=p3,p5, v4 owns the sensor data items set L4=p4, v5 owns the sensor data items set L5=p3,p5, v6 owns the sensor data items set L6=p6, v7 owns the sensor data items set L7=p1,p2, and the total sensor data item set Ltotal=p1,p2,p3,p4,p5,p6.Figure 3
Request state graph of vehicles.Assume that when a vehicle sends data, at most3 vehicles can receive the sent data. In the current time slot, v1 sends coded packet p1⊕p5, v2, v3, and v5 are the receiving vehicles, and v2 receives the coded packet p1⊕p5 and then can decode the required packet p5 with the existing packets p1; v3 decode the required packet p1 with the existing packet p5; v5 can decode the required packet p1 with the existing packet p5. Since v1 being transmitting state, v4 and v6 are in the state of interference; there are no other optional vehicles as sending vehicles in this time slot. In the next time slot, the existing packets state of vehicles has changed, and then the new sending nodes and corresponding encoded packets are scheduled according to the updated state information with the expectation that all vehicles can get all the sensor data items in Ltotal with the minimum number of time slots spent.
(1)Pj=PiGiGjL0rijα.


## 4. Sensor Data Dissemination Based on Network Coding

### 4.1. Selection of Concurrent Sending Vehicles

For the distribution of sensor data in each time slot, it is necessary to determine the concurrent sending vehicles and the corresponding packets to be sent. When selecting the sending vehicles, the distance to the vehicle which has the missing sensor packets, the generation time of sensor data, the number of valid receiving vehicles, and the number of concurrent sending vehicles need to be considered.wn,i is the weight corresponding to the vn sending packet pi calculated with formula (2). disn,pi means the max shortest distance between vn and the vehicles lacking of pi, which can be achieved with Floyd’s algorithm. tpi,n means the waiting time of the packet pi on vehicle vn, currn,pi means the number of the effective neighbor receiving vehicles when vn sends the packet pi, and εn,pi means the number of concurrent sending vehicles when vn sends the packet pi. nwpi means the vehicle that is lacking of pi and has the max shortest distance between itself and the vehicle vn.
(2)wn,i=disn,pi+tpi,n+currn,pi+εn,pi,(3)disn,pi=distancen,nwpi,(4)wn=maxwn,i,(5)wn=sizeofQvnmax.The selection process of concurrent transmitting nodes is shown in Algorithm1. The vehicle with max weight wn according to formula (4) is selected as the first sending node that is shown in lines 5 to 6. After the first sending vehicle is determined, its receiving vehicles and the corresponding interfered vehicles set are also determined which are denoted as InferenceSet. Remove selected sending vehicles, receiving vehicles, and interfered vehicles from the set of the current available vehicles to get the new available vehicle set AvaVelSet, which is shown in lines 15 to 16. Calculate new weight for the vehicle in the new available vehicle set AvaVelSet with formula (5), which is shown in line 8, Qvnmax is the maximum clique of decoding capability graph (DCG) of vn. The construction process of decoding capability graph is discussed in Section 4.2. Select the vehicle with the maximum weight as the second sending node and then update the set of sending vehicle set SenderSet, the set of receiving vehicles, and the set of interfered vehicles InferenceSet. Lastly, the updated available vehicles set AvaVelSet can be achieved. Repeat the procedure to select the new concurrent sending vehicle until the set of available vehicles AvaVelSet is empty, and finally the set of concurrent sending vehicles SenderSet can be achieved; the details is shown as Algorithm 1.
(6)case1pjrequestedbyviplrequestedbyvki≠kl=j,case2pjrequestedbyviplrequestedbyvkplownedbyvipjownedbyvki≠kl≠j.Algorithm 1: Concurrent sending vehicles selection.
Require: VehicleSetEnsure: SenderSet1: SetAvaVelSet=VehicleSet;2:whileAvaVelSet≠Null3:Wmax=0;4:forvi∈AvaVelSet.5:ifAvaVelSet==VehicleSet6:    CalculateWi of vi according to formula (4);7:else8:     CalculateWi of vi according to formula (5);9:end if10:ifWi>Wmax11:Wmax=Wi;12:end if13:end for14:  Selectvk with the Wmax and add vk inSenderSet;15:  CalculateInferenceSet with the currentSenderSet;16:AvaVelSet=AvaVelSet−SenderSet−InferenceSet;17:end while18: returnSenderSet;


### 4.2. Construction of Decoding Capability Graph

Decoding Capability Graph ofvnDCGvn is constructed based on the existing packets and its valid neighbor nodes. Firstly, the vertex of DCGvn are generated. If a valid neighbor vehicle vi missing the packet pj which cached on vn, then the vertex ϑij is generated, all vertexs in DCGvn are produced with the same way. Then, edges of DCGvn are produced. For any two vertices ϑij and ϑkl, if they satisfy the cases1 or case2, an edge is added between ϑij and ϑkl, all edges in DCGvn are obtained by this way. case1 means that vehicle vi and vehicle vk miss the same packet pj which exists on vn; case2 means that vehicle vi and vehicle vk each has the missing packet of the other. Vehicle vi has packet pl requested by vehicle vk, vehicle vk has packet pj requested by vehicle vi, and both pj and pl exist on vehicle vn.An example is given to illustrate the procedure of creatingDCG for a vehicle. Suppose that vehicle v2 has valid neighbors v1, v3 and v7, as shown in Figure 3. The set of existing sensor packets of vehicle v2, v1, v3, v7 are L2=p1,p2,p3, L1=p1,p5, L3=p3,p5, L7=p1,p2 separately. Construct the DCG for v2 with the above method, we can get DCGv2 shown as Figure 4. Maximum clique of a graph can be achieved with the heuristic algorithm in [34]. Maximum clique of DCGv2 is Qv2max = {ϑ13, ϑ31, ϑ73} which locating in dashed line, the weight of v2 is 3 according to formula (5). Packets requested of Qvnmax is p1,p3. If v2 broadcast the coded packet Pcoded=p1⊕p3, v7 can decode the packet p3 with the existing packet p1, v3 can decode the packet p1 with the existing packet p3, v1 can decode the packet p3 with the existing packet p1.Figure 4
Decoding capability graph ofv2.


### 4.3. Data Dissemination of Selected Vehicles

Once the concurrent sending nodes in the system are identified, the packets to be sent by each sending node need to be determined in order to achieve efficient sharing of sensor data. Based on the current identified sending vehicles, receiving vehicles, and interfered vehicles, UAV can get the effective neighbor nodes setNeighvn of any vehicle vn. Then, the DCG of any vehicle vn can be constructed based on the existing packets and missing packets of its effective neighbor nodes and the existing packets set of vn.When vehicle disseminates sending sensor data, the first selected vehicle will broadcast the packetpi with the maximum weight according to formula (2) that is shown in lines 1 to 4. If it is not the first selected vehicle, for any existing packet pi of vn, calculate the number of neighbor vehicles that lack the packet pi among its effective neighbor vehicles; if the number of neighbor vehicles that lack the packet pi is greater than or equal to M, then vn broadcasts the packet pi directly to M neighbor nodes among effective neighbor nodes which lack the packet pi, which is shown in lines 5 to 11. For every packet pi owned by vn, if the number of effective neighboring nodes lacking it is less than M, and then find the maximum clique Qvnmax of DCGvn; if the number of vertices of Qvnmax is greater or equal to M, choose any M vertices from Qvnmax, and the requested packets of the selected M vertices from Qvnmax are used to construct the coded packet Pcoded; and lastly, vn broadcasts the coded packet Pcoded to the neighbor vehicles associated with the selected M vertices from the maximum clique Qvnmax, as thown in lines 12 to 16. If the number of vertices of Qvnmax is less than M, construct the coded packet Pcoded with the requested packets of the M vertices in the maximum clique Qvnmax, and lastly, vn broadcasts the coded packet Pcoded, which is shown in lines 17 to 21. The procedure of vehicle broadcast is described as Algorithm 2. After the data sharing of the current time slot, update the data state of vehicles; and then the new set of sending nodes is determined based on the updated data state information to complete the sensor data distribution for the next time slot. Repeat the procedure until each vehicle gets all the sensor data.Algorithm 2: Vehicle broadcast.
Require: Sending vehicle SenderSet;Ensure: Void;1:whilevn∈SenderSetdo2:if (vn is the first selected sending vehicle) then3:vn broadcasts pi with the maximum weight ac-cording to formula (2);4:else5::   CalculateNeighvn of vn according to avai-lable link identification and interference thresh-old;6:while Any packet pi cached on vndo7:ifNeighvnpi>=Mthen8:vn broadcasts the packet pi to any M ve-hicles fromNeighvnpi;9:     Return;10:end if11:end while12:vn finds the maxclique Qvnmax from DCGvn;13:ifSizeQvnmax>=Mthen14:    Select anyM vetexex from Qvnmax;15:    ConstructPcoded with the packets requestedby the selectedM vertex;16:vn broadcasts Pcoded;17:else18:     ConstructPcoded with the packets requestedby every vertex fromQvnmax;19:vn broadcasts Pcoded;20:end if21:end if22:end while


### 4.4. Complexity Analysis

Assuming that there areN vehicles and K sensory packets, concurrent sending nodes are selected based on the weight of vehicle. The distance between vehicle where the sensory packet is located to the vehicles lacking of the packet needs to be obtained, which can be resolved by Floyd’s algorithms, and the computational complexity is ON3. The subsequent sending nodes are determined according to the maximum clique of DCG, which can be achieved by heuristic algorithm in [35], and its computational complexity is ON2K.In the sensor data dissemination phase, if the sending node is the first one chosen, the sending packet is determined according to formula (2), and the computation complexity of it is ON3, which is same as above. If the sending node is not the first one chosen, the sending packet is constructed based on the maximum clique of DCG, and the computation complexity of the procedure is ON2K.


## 4.1. Selection of Concurrent Sending Vehicles

For the distribution of sensor data in each time slot, it is necessary to determine the concurrent sending vehicles and the corresponding packets to be sent. When selecting the sending vehicles, the distance to the vehicle which has the missing sensor packets, the generation time of sensor data, the number of valid receiving vehicles, and the number of concurrent sending vehicles need to be considered.wn,i is the weight corresponding to the vn sending packet pi calculated with formula (2). disn,pi means the max shortest distance between vn and the vehicles lacking of pi, which can be achieved with Floyd’s algorithm. tpi,n means the waiting time of the packet pi on vehicle vn, currn,pi means the number of the effective neighbor receiving vehicles when vn sends the packet pi, and εn,pi means the number of concurrent sending vehicles when vn sends the packet pi. nwpi means the vehicle that is lacking of pi and has the max shortest distance between itself and the vehicle vn.
(2)wn,i=disn,pi+tpi,n+currn,pi+εn,pi,(3)disn,pi=distancen,nwpi,(4)wn=maxwn,i,(5)wn=sizeofQvnmax.The selection process of concurrent transmitting nodes is shown in Algorithm1. The vehicle with max weight wn according to formula (4) is selected as the first sending node that is shown in lines 5 to 6. After the first sending vehicle is determined, its receiving vehicles and the corresponding interfered vehicles set are also determined which are denoted as InferenceSet. Remove selected sending vehicles, receiving vehicles, and interfered vehicles from the set of the current available vehicles to get the new available vehicle set AvaVelSet, which is shown in lines 15 to 16. Calculate new weight for the vehicle in the new available vehicle set AvaVelSet with formula (5), which is shown in line 8, Qvnmax is the maximum clique of decoding capability graph (DCG) of vn. The construction process of decoding capability graph is discussed in Section 4.2. Select the vehicle with the maximum weight as the second sending node and then update the set of sending vehicle set SenderSet, the set of receiving vehicles, and the set of interfered vehicles InferenceSet. Lastly, the updated available vehicles set AvaVelSet can be achieved. Repeat the procedure to select the new concurrent sending vehicle until the set of available vehicles AvaVelSet is empty, and finally the set of concurrent sending vehicles SenderSet can be achieved; the details is shown as Algorithm 1.
(6)case1pjrequestedbyviplrequestedbyvki≠kl=j,case2pjrequestedbyviplrequestedbyvkplownedbyvipjownedbyvki≠kl≠j.Algorithm 1: Concurrent sending vehicles selection.
Require: VehicleSetEnsure: SenderSet1: SetAvaVelSet=VehicleSet;2:whileAvaVelSet≠Null3:Wmax=0;4:forvi∈AvaVelSet.5:ifAvaVelSet==VehicleSet6:    CalculateWi of vi according to formula (4);7:else8:     CalculateWi of vi according to formula (5);9:end if10:ifWi>Wmax11:Wmax=Wi;12:end if13:end for14:  Selectvk with the Wmax and add vk inSenderSet;15:  CalculateInferenceSet with the currentSenderSet;16:AvaVelSet=AvaVelSet−SenderSet−InferenceSet;17:end while18: returnSenderSet;


## 4.2. Construction of Decoding Capability Graph

Decoding Capability Graph ofvnDCGvn is constructed based on the existing packets and its valid neighbor nodes. Firstly, the vertex of DCGvn are generated. If a valid neighbor vehicle vi missing the packet pj which cached on vn, then the vertex ϑij is generated, all vertexs in DCGvn are produced with the same way. Then, edges of DCGvn are produced. For any two vertices ϑij and ϑkl, if they satisfy the cases1 or case2, an edge is added between ϑij and ϑkl, all edges in DCGvn are obtained by this way. case1 means that vehicle vi and vehicle vk miss the same packet pj which exists on vn; case2 means that vehicle vi and vehicle vk each has the missing packet of the other. Vehicle vi has packet pl requested by vehicle vk, vehicle vk has packet pj requested by vehicle vi, and both pj and pl exist on vehicle vn.An example is given to illustrate the procedure of creatingDCG for a vehicle. Suppose that vehicle v2 has valid neighbors v1, v3 and v7, as shown in Figure 3. The set of existing sensor packets of vehicle v2, v1, v3, v7 are L2=p1,p2,p3, L1=p1,p5, L3=p3,p5, L7=p1,p2 separately. Construct the DCG for v2 with the above method, we can get DCGv2 shown as Figure 4. Maximum clique of a graph can be achieved with the heuristic algorithm in [34]. Maximum clique of DCGv2 is Qv2max = {ϑ13, ϑ31, ϑ73} which locating in dashed line, the weight of v2 is 3 according to formula (5). Packets requested of Qvnmax is p1,p3. If v2 broadcast the coded packet Pcoded=p1⊕p3, v7 can decode the packet p3 with the existing packet p1, v3 can decode the packet p1 with the existing packet p3, v1 can decode the packet p3 with the existing packet p1.Figure 4
Decoding capability graph ofv2.


## 4.3. Data Dissemination of Selected Vehicles

Once the concurrent sending nodes in the system are identified, the packets to be sent by each sending node need to be determined in order to achieve efficient sharing of sensor data. Based on the current identified sending vehicles, receiving vehicles, and interfered vehicles, UAV can get the effective neighbor nodes setNeighvn of any vehicle vn. Then, the DCG of any vehicle vn can be constructed based on the existing packets and missing packets of its effective neighbor nodes and the existing packets set of vn.When vehicle disseminates sending sensor data, the first selected vehicle will broadcast the packetpi with the maximum weight according to formula (2) that is shown in lines 1 to 4. If it is not the first selected vehicle, for any existing packet pi of vn, calculate the number of neighbor vehicles that lack the packet pi among its effective neighbor vehicles; if the number of neighbor vehicles that lack the packet pi is greater than or equal to M, then vn broadcasts the packet pi directly to M neighbor nodes among effective neighbor nodes which lack the packet pi, which is shown in lines 5 to 11. For every packet pi owned by vn, if the number of effective neighboring nodes lacking it is less than M, and then find the maximum clique Qvnmax of DCGvn; if the number of vertices of Qvnmax is greater or equal to M, choose any M vertices from Qvnmax, and the requested packets of the selected M vertices from Qvnmax are used to construct the coded packet Pcoded; and lastly, vn broadcasts the coded packet Pcoded to the neighbor vehicles associated with the selected M vertices from the maximum clique Qvnmax, as thown in lines 12 to 16. If the number of vertices of Qvnmax is less than M, construct the coded packet Pcoded with the requested packets of the M vertices in the maximum clique Qvnmax, and lastly, vn broadcasts the coded packet Pcoded, which is shown in lines 17 to 21. The procedure of vehicle broadcast is described as Algorithm 2. After the data sharing of the current time slot, update the data state of vehicles; and then the new set of sending nodes is determined based on the updated data state information to complete the sensor data distribution for the next time slot. Repeat the procedure until each vehicle gets all the sensor data.Algorithm 2: Vehicle broadcast.
Require: Sending vehicle SenderSet;Ensure: Void;1:whilevn∈SenderSetdo2:if (vn is the first selected sending vehicle) then3:vn broadcasts pi with the maximum weight ac-cording to formula (2);4:else5::   CalculateNeighvn of vn according to avai-lable link identification and interference thresh-old;6:while Any packet pi cached on vndo7:ifNeighvnpi>=Mthen8:vn broadcasts the packet pi to any M ve-hicles fromNeighvnpi;9:     Return;10:end if11:end while12:vn finds the maxclique Qvnmax from DCGvn;13:ifSizeQvnmax>=Mthen14:    Select anyM vetexex from Qvnmax;15:    ConstructPcoded with the packets requestedby the selectedM vertex;16:vn broadcasts Pcoded;17:else18:     ConstructPcoded with the packets requestedby every vertex fromQvnmax;19:vn broadcasts Pcoded;20:end if21:end if22:end while


## 4.4. Complexity Analysis

Assuming that there areN vehicles and K sensory packets, concurrent sending nodes are selected based on the weight of vehicle. The distance between vehicle where the sensory packet is located to the vehicles lacking of the packet needs to be obtained, which can be resolved by Floyd’s algorithms, and the computational complexity is ON3. The subsequent sending nodes are determined according to the maximum clique of DCG, which can be achieved by heuristic algorithm in [35], and its computational complexity is ON2K.In the sensor data dissemination phase, if the sending node is the first one chosen, the sending packet is determined according to formula (2), and the computation complexity of it is ON3, which is same as above. If the sending node is not the first one chosen, the sending packet is constructed based on the maximum clique of DCG, and the computation complexity of the procedure is ON2K.


## 5. Performance Evaluation

The simulation scenario is a 16 m×500 m road consisting of 4 lanes, and the number of vehicles on each lane follows Poisson’s distribution with density of λv. Control signals between UAV and vehicles are transmitted using sub-6GHz omni-directional antenna, the inter-vehicle communication is carried out using mmWave directional antennas, the data plane is based on 802.11ad implementation in literature [36], and the simulation parameters are shown in Table 1. The proposed method BADDNC in this paper is compared with methods BAMD [21], w/o LAD [21], and GBRS [20] in terms of packet loss rate, transmission time, and packet distribution ratio. BAMD considers millimeter wave blocking effect but does not use coded distribution technology; w/o LAD is a simplification of BAMD, in which there is no link availability identification process; sending vehicle selection of GBRS is based on the utility value of vehicle nodes, which takes into account vehicle distance, number of neighbors, and packet queue.Table 1
Simulation parameters.
ParametersValueTransmission power of vehicles30 dBmCarrier frequency28 GHzSize of sensor data packet1600BBandwidth of mmWave2.16GHzTransmission rate of mmWave link1GbpsAntenna gains of vehiclesGt=Gr=1Half-power beamwidth of antennaθ=45∘Number of RF chains for transmission antennaM=4Path loss exponents of channelα=2.7(LOS)SNR thresholdPth=10dBSINR thresholdγ=5dBNoise power of vehiclesN0=−174dBmInterference thresholdσ=−54dBmTime slot intervalΔt=0.0625msPacket loss rate (PLR) is the ratio of the number of users who unsuccessfully received the sent packet to the number of target users, shown as formula (7). Numitar is the number of target users of ith transmission. Numisucc is the number of users who received the packet successfully of ith transmission.
(7)PLR=1−∑i=1KNumisucc∑i=1KNumitar.Transmission time (TT) means the time consumed that each vehicle gets all the sensor data packets, shown as formula (8). NumDiss is the number of concurrent transmissions; Δt is the time consumed to complete a transmission.
(8)TT=NumDiss·Δt.Packet dissemination ratio (PDR) denotes the ratio of the number of missing packets that all vehicles have got and the sum of missing packets of all vehicles, shown as formula (9). Numvitcur is the number of missing packets of vehicle vi at time tcur. Numviw is the number of missing packets of vehicle vi.
(9)PDR=1−∑vi∈VNumvitcur∑vi∈VNumviw.In Figure5, packet loss ratio of four methods is given when λv=0.01. During the distribution of sensor data, the feedback information of link availability will be used for the next sensor data dissemination. It can be seen from Figure 5 that both BADDNC and BAMD have a lower packet loss ratio, because the sending vehicles perform link availability identification before they disseminate sensor data with BADDNC and BAMD. In comparison with BAMD and BADDNC, BGRS and w/o LAD do not perform link availability identification during the data dissemination process and have a higher packet loss rate. As the transmission process proceeds, more link feedback information is collected and then the packet loss rate of BGRS and w/o LAD finally remains at a relatively stable state.Figure 5
Packet loss ratio whenλv=0.01.In Figure6, transmission delay of four methods is given at different vehicle densities. As can be seen in Figure 6, the transmission delay of several schemes increases as the vehicle density increases; because as the vehicle density increases, the amount of sensor data by the vehicles increases, then the time required to distribute the sensor data increases accordingly. The transmission delay of BADDNC, BAMD, and w/o LAD is significantly less than BGRS, because these three methods are able to schedule more concurrent transmission at each time slot. BADDNC has the smallest data transmission delay compared to the other three methods because BADDNC performs an available link identification to discover available receiving vehicles before each transmission and also uses a network coding method during data distribution, which can improve the data distribution efficiency to some extent. BAMD has shorter distribution delay than w/o LAD because BAMD performs the available link identification process before data distribution to select the neighboring nodes with better link status as the receiving nodes.Figure 6
Transmission delay vs. vehicle density.Packet dissemination ratio of several schemes increases as the transmission time increases, as can be seen in Figure7. This is because the number of sensor packets received by vehicles increases with the transmission time. The packet dissemination ratio of BADDNC, BAMD, and w/o LAD is higher than BGRS because these three methods are able to schedule more concurrent transmissions at each time slot. BADDNC has the highest packet dissemination ratio compared to the other three methods because BADDNC performs an available link identification process to discover available receiving vehicles before each transmission and also uses network coding technology during data distribution, which can increase the number of receiving vehicles that can successfully receive packets. By this way, it can improve the efficiency of sensor data distribution. BAMD has a higher packet dissemination ratio than w/o LAD because BAMD performs the available link identification process before data distribution and selects the neighboring nodes without the link blockage. The comparison between Figures 7 and 8 illustrates that as the number of vehicle increases, more transmission time is required to complete the distribution of sensor data. In the case of different vehicle densities, the proposed method BADDNC has a higher packet dissemination ratio and can improve the efficiency of sensor data packet dissemination.Figure 7
Packet dissemination ratio whenλv=0.01.Figure 8
Packet dissemination ratio whenλv=0.02.


## 6. Conclusion

The paper proposed a sensor data dissemination method based on available link identification and network coding to improve the sensor data sharing efficiency in mmWave VN. Concurrent sending vehicles selection method are proposed based on the availability of mmWave link, the number of target vehicles, the distance between sensor data packet and requested vehicles, the number of concurrent sending vehicles, and the waiting time of sensor data packet. Construction method of coded packet is put forward based on the status information about the existing packets of vehicles. The proposed method can speed up the sensor data sharing in mmWave VN. The simulation results indicate that our proposed sensor data dissemination solution is best when the efficiency of sensor data dissemination is a real concern in VN. In the future, the new network coding method will be explored to facilitate the sensor data dissemination.



---

*Source: 2576182-2022-09-19.xml*