# Improved Data Transmission Scheme of Network Coding Based on Access Point Optimization in VANET

Authors: Zhe Yang; Lingzhi Li; Wenqiang Yao; Kaisheng Xu; Dongxin Tang
Journal: Journal of Electrical and Computer Engineering
 (2014)

---

## Abstract

VANET is a hot spot of intelligent transportation researches. For vehicle users, the file sharing and content distribution through roadside access points (AP) as well as the vehicular ad hoc networks (VANET) have been an important complement to that cellular network. So the AP deployment is one of the key issues to improve the communication performance of VANET. In this paper, an access point optimization method is proposed based on particle swarm optimization algorithm. The transmission performances of the routing protocol with random linear network coding before and after the access point optimization are analyzed. The simulation results show the optimization model greatly affects the VANET transmission performances based on network coding, and it can enhance the delivery rate by 25% and 14% and reduce the average delay of transmission by 38% and 33%.


---

## Body

## 1. Introduction

As an important part of intelligent transportation system, VANET can effectively realize a variety of applications like accident early warning, aided driving, road traffic information query, and Internet access service [1]. It is expected in the near future that, with the mass deployment of VANET, VANET will play an important role in the accident early warning, traffic safety, traffic management, and passenger entertainment and offer the comfortable and safe driving environment to users. It can be a typical application of the Internet of things [2].Vehicular network has attracted the considerable attention in the research field and commercial field. The industry has put forward many protocol standards and mechanisms to support the V2V (vehicle to vehicle) communication and V2I (vehicle to infrastructure) communication such as dedicated short range communication standard-IEEE802.11p [3]. However, due to the problems of fast movement of vehicle node, dynamic changes of network topology, and “hidden terminals,” it is still challenging to achieve high-speed information passing and seamless connection. In order to improve information exchange capacity of vehicular network, this paper proposes the mechanism of optimizing the access points and wireless network coding to improve the performance of network and the connection between the vehicle and the infrastructure.


## 2. Related Works

There are two communication modes: V2I and V2V. V2V refers to the communication between vehicle nodes in the ad hoc network of vehicle nodes. V2I means the communication between the vehicle nodes and access points. The vehicle nodes communicate with other networks like Internet through V2I and the vehicle nodes inside the VANET communicate with each other through V2V. VANET takes the moving vehicles and access points as the nodes to conduct the information exchanges of V2V and V2I. Access points assist the vehicle nodes in realizing information transmission. Due to the large transmission range and the big information storage, the access point plays an important role in VANET. It is of great value to study how to deploy access points to improve the performance of the VANET network data transmission.At present, most of the researches of the optimized deployment of access points focus on the wireless sensor networks. And there are few researches that emphasize the AP optimization. In the conditions of full coverage, [4] proposed a method based on genetic algorithm to minimize the quantity of covered node. [5] realized the girding of areas and neglected the moving cost of network, maximizing the network coverage with the uniform deployment of nodes in grids. [6, 7] took the network coverage as targets to optimize the layout of nodes with ant colony algorithm and particle swarm optimization algorithm, respectively.The access points will adopt different relaying strategies to facilitate the information transmission between source nodes and destination nodes according to actual scenarios, such as information forwarding after the signal amplification or information forwarding after decoding [8]. Cooperative relaying can be realized through self-adaptation or fixed modes. Because of the fast environment change of vehicular network, the fixed modes will easily cause the decrease of bandwidth utilization and the lower adaptability and the self-adaptation can be more suitable for the environment of vehicular network. In self-adaptation, the relay nodes usually choose the suitable relaying strategies according to the quality of channels between source nodes and relay nodes or source nodes and destination nodes and the feedback information from target nodes. In cooperative relaying, the connectivity and communication quality of network will be improved. But the cooperative relaying communication may decrease the handling capacity of network due to the delay with the introduction of the relay.In recent years, the application of network coding technology in the wireless network has gained more and more attention. It adopts the broadcast characteristics of wireless network to process information at the relay nodes to improve the efficiency of information transmission according to the principles of storage-coding-forwarding [9]. Network coding can be applied to the different layers of OSI protocol stack. For example, in the network layer, the packet-level network coding will packet multiple data packages for forwarding and different receivers can use the data packages obtained to extract the data packages needed from the coded ones. In the physical layer, the analog network coding can combine different signals to improve the bandwidth utilization. A great number of researches show that network coding can save the times of information transmission and improve the robustness and adaptability of information transmission.In existing studies, some literatures have proposed to combine the cooperative communication system and network coding to improve the network performance. In [10], Katti et al. presented the cooperative relaying to enhance the connectivity in case of the poor quality of channels between vehicle nodes and access points, further adopting the analog network coding technology to increase the communication efficiency at relaying nodes if it was the two-way communication. In [11], Zhang and Yeo recommended choosing access points by predicting the motion trails of vehicles; they proposed to first receive useful information from the center nodes to distribute it to vehicles which will move to the coverage of these access points and then distribute information through network coding. However, at the present stage, the vehicular network is immature and the infrastructure is scarce; so, it is not feasible to adopt the mechanism of [11]. In [12], Nandan et al. raised a new content distribution mechanism to increase the handling capacity of VANET. In [13], Li et al. combined the symbol level network coding to present an optimized content distribution mechanism. However, [11–13] emphasized the content distribution of vehicles, seldom exploring the file sharing and information exchange between vehicle nodes and access points.This paper emphasizes the access points and proposes a mechanism combining the cooperative communication and network coding to improve the connectivity between the access points and vehicle nodes. This mechanism can enhance the utilization of access points to reduce the error rates of information transmission and increase the handling capacity of vehicular network in the conditions of incomplete coverage of access points. Compared with ad hoc network coding, symbol level network coding has a larger tolerability for bit error; therefore, it can allow more simultaneous transmission to gain larger handling capacity.


## 3. Location Optimization of Access Points

In order to make the model clear, this paper specifies the following symbols. If there are two nodesi and j in the two-dimensional space, then consider the following.(i)
dij is the distance between i and j.(ii)
ξ is the minimum distance of any two nodes in the two-dimensional space [14].(iii)
ri is the transmission radius of i.(iv)
li→j is the signal loss rate on the link from i to j.(v)
si→j is the data transmission speed from i to j.


### 3.1. Establishment of the Optimization Model

To simplify the research, this problem is decomposed into two subproblems. The first is within the limited areaG, if there are k vehicle nodes, so at least how many APs should be deployed to ensure there is no isolated vehicle node? The second is that after the confirmation of the number of APs, how should the APs be deployed to ensure the optimal performance?First, it is assumed thatN APs are selected in the area G and these APs should ensure the connectivity of the nodes in area G. That is to say, the transmission radius ri to any node in G should be greater than minimum distance between the node and other nodes as follows:
(1)ri≥ξ=min⁡dij.Second, the optimal location of the APm should ensure the connectivity of the area and keep the transmission overhead minimum. So, if there are k vehicle nodes in the network, the transmission energy eit of node i can be expressed as follows:
(2)eit=∑j=1k,j≠ili→j·si→j=∑j=1k,j≠i(β1+β2·dijα)·si→j,
where, β1 and β2 are path loss coefficients and α is path loss exponent. The receiving energy of node i,eir can be expressed:
(3)eir=δ·∑j=1k,j≠isj→i,
where δ is the energy receiving rate. Within the same period, the data volume of each node i is balanced. That is to say, the data volume sent equals the sum of the data volume received and the data volume produced. Then, we get the balanced data rate equation as follows:
(4)∑j=1k,j≠isj→i+sAP→i=∑j=1k,j≠isi→j+si→AP.Forei, the energy of node i, there is the following limited condition:
(5)∑j=1k,j≠iδ·sj→i+∑j=1k,j≠ili→j·si→j+li→AP·si→AP≤ei.According to the distance matrix, when the area is limited, the number of neighbor nodes can replace the density of neighbor node. According to limits of the optimal AP, the objective function of the AP optimization is(6)min⁡E=∑i=1N(β1+β2·dAPiα)·si→AP.


### 3.2. Solutions

The following parts analyze and explore objective functions (1) and (6) to first obtain the number of APs and then work out the optimal location of AP.


#### 3.2.1. Optimization of the Number of APs

[14] presented that ξ, the minimum distance of two nodes in G, follows Poisson’s distribution with the following probability distribution function:
(7)f(ξ)=2πρξ·e-ρπξ2(ξ>0),
where p, the density of node, is the ratio of the number of nodes n and the area of G. From (7), we can obtain the probability that a node has no neighbor node is
(8)P(ξ>ri)=1-P(ξ≤ri)=e-ρπri2.If we assume that every node is independent from each other, and then the probability that there is no isolated node inG is(9)p=P(ri≥ξ)=(1-e-ρπri2)N.From (10), we can find that the number of APs is
(10)N=⌈log1-e-ρπri2p⌉.


#### 3.2.2. Optimization of Location of AP

This paper adopts the particle swarm optimization algorithm [15] to optimize the locations of AP. First, consider the condition of only one AP; the location of the optimal node should satisfy (7). When the number of APs is N, the location of the optimal node should satisfy the following objective function:
(11)min⁡E=∑k=1N{∑i=1N(β1+β2·dAPkiα)·si→APk}.The locations ofN nodes satisfying the conditions of (11) are the location distribution of AP.


## 3.1. Establishment of the Optimization Model

To simplify the research, this problem is decomposed into two subproblems. The first is within the limited areaG, if there are k vehicle nodes, so at least how many APs should be deployed to ensure there is no isolated vehicle node? The second is that after the confirmation of the number of APs, how should the APs be deployed to ensure the optimal performance?First, it is assumed thatN APs are selected in the area G and these APs should ensure the connectivity of the nodes in area G. That is to say, the transmission radius ri to any node in G should be greater than minimum distance between the node and other nodes as follows:
(1)ri≥ξ=min⁡dij.Second, the optimal location of the APm should ensure the connectivity of the area and keep the transmission overhead minimum. So, if there are k vehicle nodes in the network, the transmission energy eit of node i can be expressed as follows:
(2)eit=∑j=1k,j≠ili→j·si→j=∑j=1k,j≠i(β1+β2·dijα)·si→j,
where, β1 and β2 are path loss coefficients and α is path loss exponent. The receiving energy of node i,eir can be expressed:
(3)eir=δ·∑j=1k,j≠isj→i,
where δ is the energy receiving rate. Within the same period, the data volume of each node i is balanced. That is to say, the data volume sent equals the sum of the data volume received and the data volume produced. Then, we get the balanced data rate equation as follows:
(4)∑j=1k,j≠isj→i+sAP→i=∑j=1k,j≠isi→j+si→AP.Forei, the energy of node i, there is the following limited condition:
(5)∑j=1k,j≠iδ·sj→i+∑j=1k,j≠ili→j·si→j+li→AP·si→AP≤ei.According to the distance matrix, when the area is limited, the number of neighbor nodes can replace the density of neighbor node. According to limits of the optimal AP, the objective function of the AP optimization is(6)min⁡E=∑i=1N(β1+β2·dAPiα)·si→AP.


## 3.2. Solutions

The following parts analyze and explore objective functions (1) and (6) to first obtain the number of APs and then work out the optimal location of AP.


### 3.2.1. Optimization of the Number of APs

[14] presented that ξ, the minimum distance of two nodes in G, follows Poisson’s distribution with the following probability distribution function:
(7)f(ξ)=2πρξ·e-ρπξ2(ξ>0),
where p, the density of node, is the ratio of the number of nodes n and the area of G. From (7), we can obtain the probability that a node has no neighbor node is
(8)P(ξ>ri)=1-P(ξ≤ri)=e-ρπri2.If we assume that every node is independent from each other, and then the probability that there is no isolated node inG is(9)p=P(ri≥ξ)=(1-e-ρπri2)N.From (10), we can find that the number of APs is
(10)N=⌈log1-e-ρπri2p⌉.


### 3.2.2. Optimization of Location of AP

This paper adopts the particle swarm optimization algorithm [15] to optimize the locations of AP. First, consider the condition of only one AP; the location of the optimal node should satisfy (7). When the number of APs is N, the location of the optimal node should satisfy the following objective function:
(11)min⁡E=∑k=1N{∑i=1N(β1+β2·dAPkiα)·si→APk}.The locations ofN nodes satisfying the conditions of (11) are the location distribution of AP.


## 3.2.1. Optimization of the Number of APs

[14] presented that ξ, the minimum distance of two nodes in G, follows Poisson’s distribution with the following probability distribution function:
(7)f(ξ)=2πρξ·e-ρπξ2(ξ>0),
where p, the density of node, is the ratio of the number of nodes n and the area of G. From (7), we can obtain the probability that a node has no neighbor node is
(8)P(ξ>ri)=1-P(ξ≤ri)=e-ρπri2.If we assume that every node is independent from each other, and then the probability that there is no isolated node inG is(9)p=P(ri≥ξ)=(1-e-ρπri2)N.From (10), we can find that the number of APs is
(10)N=⌈log1-e-ρπri2p⌉.


## 3.2.2. Optimization of Location of AP

This paper adopts the particle swarm optimization algorithm [15] to optimize the locations of AP. First, consider the condition of only one AP; the location of the optimal node should satisfy (7). When the number of APs is N, the location of the optimal node should satisfy the following objective function:
(11)min⁡E=∑k=1N{∑i=1N(β1+β2·dAPkiα)·si→APk}.The locations ofN nodes satisfying the conditions of (11) are the location distribution of AP.


## 4. Simulation Results and Analyses

This part comparatively analyzes the transmission performance of network coding before and after the AP optimization. It first introduces the simulation environment and specific processes.


### 4.1. Simulation Environment and Process

This paper adopts NS2 to simulate the network transmission performance of vehicle nodes in the fixed topology scope and the routing protocol uses the random linear network coding (RLNC) [16]. Simulating the different vehicle numbers and moving traces, it obtains the transmission performance. Table 1 shows the main simulation parameter settings. Based on the main simulation parameters in Table 1, we can work out the number of nodes N=5 according to (1). The following parts analyze the network transmission performance from the aspects of delivery rate and transmission delay.Table 1
Main simulation parameter settings.
Simulation parameter
Value
β
1
1
β
2
0.5
α
2
G
1
*
1 km2
Number of vehicles
10~100
Probability of no isolated nodeP
0.9
Vehicle transmission radius
30 m
AP transmission radius
300 m
Packet delivery rate
10 kbps
Packet size
500 bytes


### 4.2. Performance Analysis

Packet delivery rate and average transmission delay are the two important indicators of VANET performance evaluation. From these two aspects, this paper conducts the network performance analysis.


#### 4.2.1. Packet Delivery Rate

The packet delivery rate is defined as the ratio of the number of data packets received by the node (or successfully decoded) and the total number of data packets. Figure1 shows the packet delivery rates of the networks with different numbers of vehicles. Random_AP and Optimization_AP represent the performance of random AP and optimized AP. Random_AP+NC and Optimization_AP+NC represent the performance of random AP and optimized AP with network coding. From Figure 1, we can see the delivery rate of the network equipped with optimized APs is larger than that of the network with random APs, which is consistent with the expected results. And the average improvement ratios are 25% (Optimization_AP versus Random_AP) and 14% (Optimization_AP+NC versus Random_AP+NC).Figure 1
Comparison chart of packet delivery rate.


#### 4.2.2. Average Transmission Delay

Transmission delay is defined as the difference between the time of successfully receiving (decoding) the packet and the time of first sending the packet. Figure2 shows the delivery delays of the networks with different numbers of nodes. In the simulation process, the random AP may easily cause the isolation of nodes, resulting in the failure of a node to receive information from other nodes in the transmission process. The transmission delays of these nodes are infinite. Therefore, in the process of statistics, the delivery rates of these nodes are set to be 5 times of the maximum transmission delays. From Figure 2, we can see that the average transmission delay of the application of the optimized APs is larger than that of the network without the optimized APs. And the average improvement ratios are 38% (Optimization_AP versus Random_AP) and 33% (Optimization_AP+NC versus Random_AP+NC).Figure 2
Comparison figure of the average transmission delay.


## 4.1. Simulation Environment and Process

This paper adopts NS2 to simulate the network transmission performance of vehicle nodes in the fixed topology scope and the routing protocol uses the random linear network coding (RLNC) [16]. Simulating the different vehicle numbers and moving traces, it obtains the transmission performance. Table 1 shows the main simulation parameter settings. Based on the main simulation parameters in Table 1, we can work out the number of nodes N=5 according to (1). The following parts analyze the network transmission performance from the aspects of delivery rate and transmission delay.Table 1
Main simulation parameter settings.
Simulation parameter
Value
β
1
1
β
2
0.5
α
2
G
1
*
1 km2
Number of vehicles
10~100
Probability of no isolated nodeP
0.9
Vehicle transmission radius
30 m
AP transmission radius
300 m
Packet delivery rate
10 kbps
Packet size
500 bytes


## 4.2. Performance Analysis

Packet delivery rate and average transmission delay are the two important indicators of VANET performance evaluation. From these two aspects, this paper conducts the network performance analysis.


### 4.2.1. Packet Delivery Rate

The packet delivery rate is defined as the ratio of the number of data packets received by the node (or successfully decoded) and the total number of data packets. Figure1 shows the packet delivery rates of the networks with different numbers of vehicles. Random_AP and Optimization_AP represent the performance of random AP and optimized AP. Random_AP+NC and Optimization_AP+NC represent the performance of random AP and optimized AP with network coding. From Figure 1, we can see the delivery rate of the network equipped with optimized APs is larger than that of the network with random APs, which is consistent with the expected results. And the average improvement ratios are 25% (Optimization_AP versus Random_AP) and 14% (Optimization_AP+NC versus Random_AP+NC).Figure 1
Comparison chart of packet delivery rate.


### 4.2.2. Average Transmission Delay

Transmission delay is defined as the difference between the time of successfully receiving (decoding) the packet and the time of first sending the packet. Figure2 shows the delivery delays of the networks with different numbers of nodes. In the simulation process, the random AP may easily cause the isolation of nodes, resulting in the failure of a node to receive information from other nodes in the transmission process. The transmission delays of these nodes are infinite. Therefore, in the process of statistics, the delivery rates of these nodes are set to be 5 times of the maximum transmission delays. From Figure 2, we can see that the average transmission delay of the application of the optimized APs is larger than that of the network without the optimized APs. And the average improvement ratios are 38% (Optimization_AP versus Random_AP) and 33% (Optimization_AP+NC versus Random_AP+NC).Figure 2
Comparison figure of the average transmission delay.


## 4.2.1. Packet Delivery Rate

The packet delivery rate is defined as the ratio of the number of data packets received by the node (or successfully decoded) and the total number of data packets. Figure1 shows the packet delivery rates of the networks with different numbers of vehicles. Random_AP and Optimization_AP represent the performance of random AP and optimized AP. Random_AP+NC and Optimization_AP+NC represent the performance of random AP and optimized AP with network coding. From Figure 1, we can see the delivery rate of the network equipped with optimized APs is larger than that of the network with random APs, which is consistent with the expected results. And the average improvement ratios are 25% (Optimization_AP versus Random_AP) and 14% (Optimization_AP+NC versus Random_AP+NC).Figure 1
Comparison chart of packet delivery rate.


## 4.2.2. Average Transmission Delay

Transmission delay is defined as the difference between the time of successfully receiving (decoding) the packet and the time of first sending the packet. Figure2 shows the delivery delays of the networks with different numbers of nodes. In the simulation process, the random AP may easily cause the isolation of nodes, resulting in the failure of a node to receive information from other nodes in the transmission process. The transmission delays of these nodes are infinite. Therefore, in the process of statistics, the delivery rates of these nodes are set to be 5 times of the maximum transmission delays. From Figure 2, we can see that the average transmission delay of the application of the optimized APs is larger than that of the network without the optimized APs. And the average improvement ratios are 38% (Optimization_AP versus Random_AP) and 33% (Optimization_AP+NC versus Random_AP+NC).Figure 2
Comparison figure of the average transmission delay.


## 5. Conclusions

This paper proposes a data distribution mechanism based on network coding in VANET, adopting the energy constraint method to solve the problem of the number of APs and the particle swarm optimization algorithm to solve the problem of location optimization of AP. The laboratory simulations show that the data delivery rate and the average transmission delay improve. Routing protocol used in this paper is the random linear network coding based on the flooding mechanism. In the future, the research will focus on the selection of appropriate routing paths for network coding to improve the handling capacity of VANET.



---

*Source: 185412-2014-07-03.xml*