# Parking Query in Vehicular Delay-Tolerant Networks with Privacy Protection Based on Secure Multiparty Computation

Authors: Haiping Huang; Juan Feng; Dan Sha; Jia Xu; Hua Dai
Journal: Journal of Sensors
 (2015)

---

## Abstract

Within vehicular delay-tolerant network, conflict exists in the scenario of which two vehicles happen to choose the same parking space. To solve this problem, two protocols are proposed, respectively, which are called privacy protection protocol based on secure multiparty computation and routing protocol based on angle and density. The proposed methods prevent the leaking of privacy information of the vehicles involved during the parking space seeking process and improve the performance of the transmission ratio and reduce the transmission delay by unifying the directions of messages and choosing the vehicle of the highest distribution density as the next hop. The results of the simulation show the efficiency of our method.


---

## Body

## 1. Introduction

Many applications under the delay-tolerant network have been studied and extended to wireless network domains such as mobile ad hoc networks (MANET), vehicular ad hoc networks (VANET), and wireless sensor networks (WSN). In the VANET, communications between two vehicles are intermittent due to the changes of the driving speed and direction.One key issue in VANET is the urban parking problem. It arises along with the rapid expansion of urban population. The intelligent parking space positioning system is developed to address this issue. In this paper, we assume a situation where two nearby vehicles happen to find the same parking space which causes a competition for the limited resource.To solve the resource allocation problem, we propose a multiparty computation based protocol to detect the potential conflict. Once the vehicle detects that the parking space has been already allocated, it continues its searching process. Vehicular delay-tolerant network is full of potential maliciousness, such as attacks and unauthorized operations. The vehicle privacy is also a critical issue. In order to protect it, we design a privacy protection strategy during the secure multiparty computation, along with a routing protocol to increase the transmission ratio while decreasing the transmission delay. The distribution density and the directions of the vehicles are input parameters in estimation function. The direction of the vehicle is calculated by measuring the angle between the reference direction and the line linking itself to the base station. The vehicle near this line has the highest distribution density and will be chosen for the next hop.In this paper, we brief the related work on security and routing protocol of delay-tolerant networks in Section2. The privacy protection strategy based on multiparty computation is designed in Section 3, while the routing protocol based on angle and density is proposed in Section 4. In Section 5, we discuss the security of the proposed method, and the simulation results show the higher transmission ratio and lower transmission delay. Section 6 gives the conclusion of this paper.


## 2. Related Work

The communication interruption and the uncertain network topology are the main reasons that leave the security of delay-tolerant network a challenging issue. However, some existing application system fails to meet the basic requirements for security purpose. Ensuring the security in the delay-tolerant network is an active topic among researchers. Lu et al. [1] proposed a privacy protection strategy by using the filter. The filter is maintained by the corresponding node according to its own interest. Hur and Kang [2] proposed a secure data retrieval scheme that used the CP-ABE for decentralized delay-tolerant networks, and multiple key authorities manage their own attributes. Lv et al. [3] designed an efficient and noninteractive key exchange protocol based on a time-evolving topology model and a two-channel cryptography. A time-evolving model is used to formally analyze the periodic and predetermined behavior patterns, and therefore a node can schedule when and to whom it should send its public key. By analyzing the periodic and predetermined behavior patterns, the time-evolving model decided and prepared the receiver of the node for its public key. The third party methods have drawn the attention of many researchers in delay-tolerant network. Rane et al. [4] presented a scheme using biometric authentication and homomorphic encryption for secure calculation of Hamming distance while protecting the participants’ privacy. And they furthered their study by proposing a secure two-party computation protocol [5] of Euclidean distance using Paillier homomorphic encryption and this protocol is implemented for private querying of face images and maintains low communication overhead. Facial information is utilized for authentication, and communication overhead is kept as a minimum. Yang et al. [6] provided a quantum privacy comparison method. The presence of a semihonest third party allowed the matching of information without revealing the nodes’ privacy. Huang et al. [7] allow the participants to calculate the distance between each other based on an honest third party in order to realize comparison of local data. However, the private values of participants are fully grasped by the third party, which is followed by obvious information leakage and security issues that cannot be ignored. Gao et al. [8] encoded the original data for privacy purpose and select the top N nodes to perform the multicast in network by applying privacy protected data forwarding (PPDF) model.The routing protocol for delay-tolerant network is an active topic in many different contexts. Samuel et al. [9] introduced the dominant set to the routing protocol. They took Markov model to predict the distribution of encountering interval and evaluate the utility value for the next hop. According to the historical statistic data of vehicle routes, Xu et al. [10] suggested the use of statistic method for encountering probability prediction. However, the statistic data might fail in the real scenario. Dunbar and Qu [11] applied the statistic method to preventing the location information of vehicles leaking by communication with RSUs. Hui et al. [12] binned the nodes into several areas according to their encountering probabilities simultaneously taking into account the community attribute and center degree. Fabbri and Verdone [13] considered the characteristic curve of social relations against the time series to plan the routing. Lee et al. [14] extended the current geographical routing protocol by forming a two-level hierarchy for heterogeneous network. However, existing methods either are computationally expensive or are having considerable network delay, not to mention the security issue.In this paper, we design a secure multiparty computation protocol for privacy protection. By using the direction and distribution density to decide the next hop, higher transmission ratio and lower transmission delay have been achieved.


## 3. Privacy Protection Protocol Based on Multiparty Computation

In order to find conflict of the same parking spaces, vehicles must take part in multiparty computation and meanwhile have to exchange the already owned parking space information with others. As a result, a vehicle may excavate some privacy information of other vehicles, and obviously it is dangerous. In the proposed protocol, as the third party, the base station instead of the vehicles will finally calculate the common parking spaces. Space information of each vehicle will be packed with polynomial function before being sent, and then the base station and other vehicles taking part in calculation cannot acquire the real space information. So privacy is protected. In this paper, we consider a scenario where there are three vehicles searching for parking spaces within a certain area.Firstly, each vehicle participating in calculation will search for the parking spaces within a certain communicated area and then generate a set according to the parking spaces discovered by it. Secondly, it will generate the special polynomial function. Thirdly, it will send the function to the base station. Finally, the base station will figure out the common parking spaces and return the result.


### 3.1. Problem Description

Assuming that there are three vehicles within a certain communication area, for example, A, B, and C, the sets they generate according to the parking spaces they have found areSa={a1,a2,a3,…,al}, Sb={b1,b2,b3,…,bm}, and Sc={c1,c2,c3,…,cn}, respectively. The three vehicles expect to deduce common parking spaces without leaking out their private information during the computing process.


### 3.2. Description of the Protocol

Vehicle A and vehicle B generate polynomial functions according toSa={a1,a2,a3,…,al} and Sb={b1,b2,b3,…,bm}, denoted by f(x) and g(x) separately:(1)fx=x-a1×x-a2×x-a3×⋯×x-al,gx=x-b1×x-b2×x-b3×⋯×x-bm.And then vehicle C will calculatef(ci) and g(ci); if f(ci)=0 and g(ci)=0, then element ci must be in sets Sa and Sb; in other words,(2)f(ci)+gci=0∧f(ci)×gci=0.It is equivalent to the fact that(3)f(ci)=0∧g(ci)=0.So,ci∈Sa∧ci∈Sb, which means that element ci is one of the common parking spaces of vehicles A, B, and C.


### 3.3. Implementation of the Protocol

(
1
) Vehicles A, B, and C send request message to the base station, respectively, telling the base station that they want to inquire common parking spaces.(
2
) After the base station receives the request messages, it sends response message to vehicles A, B, and C, and then connection is established.(
3
) Vehicle A generates polynomial function as follows:(4)fx=(x-a1)×(x-a2)×(x-a3)×⋯×(x-al)=∑i=0lpixi=∑i=0lqixi+∑i=0lrixi,where qi, ri (i=1,2,…,l) are all nonzero real numbers.In addition, we assume thatfb(x)=∑i=0lqixi, fc(x)=∑i=0lrixi, fb(x):A→B, and fc(x):A→C.(
4
) Vehicle A then sends fb(x) and fc(x) to the base station using the routing protocol we proposed in the following sections.(
5
) Vehicle B generates polynomial function as follows:(5)gx=(x-b1)×(x-b2)×(x-b3)×⋯×(x-bm)=∑i=0meixi=∑i=0msixi+∑i=0mtixi,where si, ti (i=1,2,…,l) are all nonzero real numbers.In addition, we assume thatga(x)=∑i=0msixi, gc(x)=∑i=0mtixi, ga(x):B→A, and gc(x):B→C.(
6
) Vehicle B then sends ga(x) and gc(x) to the base station using the routing protocol we proposed in the following sections.(
7
) The base station finally receives value of fb(x), fc(x), ga(x), and gc(x); then it calculates hc(x) and the parameter 0.5 is considered according to previous simulation results or experience:(6)hcx=fbx×gcx+0.5×gax×fbx.(
8
) The base station then sends ga(x) to vehicle A.(
9
) After receiving ga(x), vehicle A calculates u(x) and v(x):(7)ux=fx+gax=∑i=0jαixij=max⁡⁡l,m,vx=ga(x)×fc(x)+0.5×ga(x)×fb(x)lllllll=∑i=0kβixik=l+m.(
10
) Vehicle A then generates private vectors on the basis of (7) as follows:(8)X1=α0,α1,…,αj,X2=β0,β1,…,βk.Afterwards, vehicle A sends vectorsX1 and X2 to the base station.(
11
) The base station packs X1, X2, fc(x), gc(x), and hc(x) and then sends the package to vehicle C.(
12
) After receiving package of X1, X2, fc(x), gc(x), and hc(x), vehicle C then calculates h(x):(9)hx=fcx×gcx+hcx.(
13
) Following that, vehicle C implements the following substeps using elements ci (i=1,2,…,n) of set Sc.(a)
Generating private vectors:(10)Y1=1,ci,ci2,…,cij,Y2=1,ci,ci2,…,cik.(b)
Computing vectorsU1 and U2:(11)U1=X1×Y1,U2=X2×Y2.(c)
Calculatinggc(ci) and hci, judging whether U1+gcci=0 and U2+hci=0 in the meantime. If it is true, then ci∈Sa∩Sb; otherwise, ci∉(Sa∩Sb).(
14
) Vehicle C will finally obtain all elements ci which satisfy ci∈Sa∩Sb, and then it sends Su={ci,ci∈(Sa∩Sb),i=1,2,…,n} to the base station.(
15
) The base station sends the common parking spaces set Su to vehicle A and vehicle B. Eventually, the three vehicles acquire their common parking spaces without obtaining private information of others.


## 3.1. Problem Description

Assuming that there are three vehicles within a certain communication area, for example, A, B, and C, the sets they generate according to the parking spaces they have found areSa={a1,a2,a3,…,al}, Sb={b1,b2,b3,…,bm}, and Sc={c1,c2,c3,…,cn}, respectively. The three vehicles expect to deduce common parking spaces without leaking out their private information during the computing process.


## 3.2. Description of the Protocol

Vehicle A and vehicle B generate polynomial functions according toSa={a1,a2,a3,…,al} and Sb={b1,b2,b3,…,bm}, denoted by f(x) and g(x) separately:(1)fx=x-a1×x-a2×x-a3×⋯×x-al,gx=x-b1×x-b2×x-b3×⋯×x-bm.And then vehicle C will calculatef(ci) and g(ci); if f(ci)=0 and g(ci)=0, then element ci must be in sets Sa and Sb; in other words,(2)f(ci)+gci=0∧f(ci)×gci=0.It is equivalent to the fact that(3)f(ci)=0∧g(ci)=0.So,ci∈Sa∧ci∈Sb, which means that element ci is one of the common parking spaces of vehicles A, B, and C.


## 3.3. Implementation of the Protocol

(
1
) Vehicles A, B, and C send request message to the base station, respectively, telling the base station that they want to inquire common parking spaces.(
2
) After the base station receives the request messages, it sends response message to vehicles A, B, and C, and then connection is established.(
3
) Vehicle A generates polynomial function as follows:(4)fx=(x-a1)×(x-a2)×(x-a3)×⋯×(x-al)=∑i=0lpixi=∑i=0lqixi+∑i=0lrixi,where qi, ri (i=1,2,…,l) are all nonzero real numbers.In addition, we assume thatfb(x)=∑i=0lqixi, fc(x)=∑i=0lrixi, fb(x):A→B, and fc(x):A→C.(
4
) Vehicle A then sends fb(x) and fc(x) to the base station using the routing protocol we proposed in the following sections.(
5
) Vehicle B generates polynomial function as follows:(5)gx=(x-b1)×(x-b2)×(x-b3)×⋯×(x-bm)=∑i=0meixi=∑i=0msixi+∑i=0mtixi,where si, ti (i=1,2,…,l) are all nonzero real numbers.In addition, we assume thatga(x)=∑i=0msixi, gc(x)=∑i=0mtixi, ga(x):B→A, and gc(x):B→C.(
6
) Vehicle B then sends ga(x) and gc(x) to the base station using the routing protocol we proposed in the following sections.(
7
) The base station finally receives value of fb(x), fc(x), ga(x), and gc(x); then it calculates hc(x) and the parameter 0.5 is considered according to previous simulation results or experience:(6)hcx=fbx×gcx+0.5×gax×fbx.(
8
) The base station then sends ga(x) to vehicle A.(
9
) After receiving ga(x), vehicle A calculates u(x) and v(x):(7)ux=fx+gax=∑i=0jαixij=max⁡⁡l,m,vx=ga(x)×fc(x)+0.5×ga(x)×fb(x)lllllll=∑i=0kβixik=l+m.(
10
) Vehicle A then generates private vectors on the basis of (7) as follows:(8)X1=α0,α1,…,αj,X2=β0,β1,…,βk.Afterwards, vehicle A sends vectorsX1 and X2 to the base station.(
11
) The base station packs X1, X2, fc(x), gc(x), and hc(x) and then sends the package to vehicle C.(
12
) After receiving package of X1, X2, fc(x), gc(x), and hc(x), vehicle C then calculates h(x):(9)hx=fcx×gcx+hcx.(
13
) Following that, vehicle C implements the following substeps using elements ci (i=1,2,…,n) of set Sc.(a)
Generating private vectors:(10)Y1=1,ci,ci2,…,cij,Y2=1,ci,ci2,…,cik.(b)
Computing vectorsU1 and U2:(11)U1=X1×Y1,U2=X2×Y2.(c)
Calculatinggc(ci) and hci, judging whether U1+gcci=0 and U2+hci=0 in the meantime. If it is true, then ci∈Sa∩Sb; otherwise, ci∉(Sa∩Sb).(
14
) Vehicle C will finally obtain all elements ci which satisfy ci∈Sa∩Sb, and then it sends Su={ci,ci∈(Sa∩Sb),i=1,2,…,n} to the base station.(
15
) The base station sends the common parking spaces set Su to vehicle A and vehicle B. Eventually, the three vehicles acquire their common parking spaces without obtaining private information of others.


## 4. Routing Protocol Based on Angle and Density

During the calculation of common parking spaces, parking information is transmitted in the network, so we propose a routing protocol for vehicles to decide how to choose routes along to the base station when sending messages.In vehicular delay-tolerant networks, wireless communication devices are equipped with vehicles. When the distance of two vehicles is shorter than the communication radius, they can connect and exchange messages. While in some blind areas or in some periods of time, there may be no continuous connections between the source vehicle and the destination vehicle due to the sparse distribution, signal shielding, and high speed mobility of vehicles, which are the fundamental characteristics of delay-tolerant networks, also called intermittent connectivity. If a vehicle wants to send a message, it will firstly carry this message, until it encounters the other vehicle, and then it forwards the message. Due to the “storage-carry-forward” scheme, transmission delay is always an important issue. Consequently, research of routing algorithms and message distribution algorithms is significant to reduce transmission delay.As described above, considerable literatures have studied the characteristics of transmission delay. Liu et al. [15] analyze transmission delay in vehicular delay-tolerant networks with a bidirectional traffic model and it is demonstrated that transmission delay is linearly associated with transmission distance and subsequently indicates that a certain relation exists between transmission delay and vehicle density in the road. The research conclusion will be used in this paper.


### 4.1. Network Model

Figure1 manifests the network model of vehicular delay-tolerant networks, and message is forwarded by assistant node from the source nodes to the base station. In other words, message is transmitted from one vehicle to another vehicle in the range of communication.Figure 1
Network model of vehicular delay-tolerant networks.Different vehicles, as a general rule, may have different speeds; for example, the vehicle in the fast traffic lane usually runs faster than those in the slow traffic lane. We can setn levels of the vehicle speed, from slow to fast, which are denoted by v1,v2,…,vn (vi, i=1,2,...,n), respectively. For convenience sake, we firstly consider vehicles traveling in the same direction. We can assume the set Si={xi,j(t),j∈N}, (i=1,2,…,n), is the set of vehicles traveling at the speed vi, where xi,j(t) indicates the jth vehicle of the set Si at time t and t is discrete, t∈N, and N is the natural number.Assume the relationship of vehicle speedv and vehicle density λ is as follows:(12)v=a-bλ;when λ=0, the vehicle density is 0, and then the vehicle speed v can achieve the largest value vf; that is, when λ=0, then a=vf. When λ=λf, it means the vehicle density achieves the largest value λf, and then the vehicle speed will be 0 and the road is congested; that is, when λ=λf, then b=vf/λf. Thus it can be seen that the relationship of vehicle speed v and vehicle density λ is(13)v=a-bλ=vf-vfλfλ=vf1-λλf.


### 4.2. Definition of Transmission Delay

In vehicular delay-tolerant networks, transmission delay is mainly caused by message retransmission due to communication breakdown or signal interference. While compared with the time of a message transmitted from one vehicle to the other vehicle, message retransmission delay is short enough. So we can ignore it.Assuming that a vehicleN1 broadcasts a message at the time t=0, we can take I(t) as the set of vehicles having received the message from N1 at time t and take T(k)=inf⁡{t≥0:xk∈I(t)} as the time when vehicle Nk receives the message, and then the transmission delay from vehicle Np to vehicle Nq can be defined as follows:(14)Dp,q=Tq-Tp=∑k=pq-1Tk+1-Tk.


### 4.3. Details of Routing Protocol

In the routing protocol based on angle and density (abbreviated to RPAD) proposed in this paper, the density and direction of vehicle are used for estimate. When a vehicle wants to send message to the base station, it will compute the angle between itself and the base station in order to choose relay vehicles in the suitable direction along to the base station, and meanwhile it will confirm the next hop after predicting vehicle density.Assuming vehicle O is the source node, we create a coordinate and take O as the center, shown in Figure2. Vehicles A and B are in the communication range of vehicle O, and vehicle C is in the communication range of vehicle B. To reduce the transmission distance of a message and then to reduce the transmission delay, we need to unify the direction of the next hops and the message could be transmitted in the unified direction along to the base station as a guarantee of delivery ratio. Vehicle O obtains the angle between itself and the base station by the GPS device it equips, and if the angle value is larger than 45°, then it will choose those vehicles whose angle between themselves and the base station is smaller than 45° as the next hops. In Figure 2, the angle between vehicle B and the base station is ∠1<45°, while that between vehicle A and the base station is ∠2>45°, and then vehicle O will choose vehicle B as the next hop and sends message to vehicle B. Similarly, through the comparison of angles, vehicle B will choose vehicle C as the next hop. Consequently, the message of vehicle O will be forwarded along the direction like a stepped appearance shown in Figure 2 finally to the base station.Figure 2
Coordinate of vehicle O.However, there may be many vehicles satisfying the condition of angle direction. When a vehicle decides the next hop, it cannot send a copy of the message to all the condition-satisfied vehicles for the purpose of energy-efficiency. It is found by studies that, in the area of high vehicle density, a source vehicle can transmit messages rapidly step by step through other vehicles as a relay until the destination vehicle, instead of carrying the messages until the source vehicle encounters the destination vehicle. Thus, message can be delivered faster to the destination, and then transmission delay is reduced.Yazhi demonstrates the following theorem [13] through theoretical analysis and simulation experiment.Theorem 1.
There exists a relationship between the transmission delayT0,m and corresponding transmission distance m:(15)limm→∞T0,mm=α.
Based on (15), when the vehicle density and speed are fixed, α is a constant:(16)α=limm→∞E(T0,m)m.Theorem1 demonstrates that the limited ratio of transmission delay and transmission distance is α, and α is a constant when vehicle density is fixed, so transmission delay is linearly associated with transmission distance. The upper bound of the coefficient of the linear relation changes with vehicle density and speed, and so transmission delay decreases with the increase of vehicle density.In RPAD, after selecting a direction, the vehicle will decide to transmit messages to those vehicles with higher density in their own areas.Taking vehicle O for an example,Si={xi,j(t),j∈N}, (i=1,2,…,n), is the set of vehicles traveling at the relative speed vi. In the next time s, S={xi,j(t)+vi(s-t),i=1,2,…,n,j∈N} represents the relative distance between vehicles that satisfied the requirement of angle direction and vehicle O. Vehicle O will further choose those vehicles with higher area density as next hops according to the relative distance and then sends messages to them. Other vehicles repeat the above process until the base station receives the messages.


## 4.1. Network Model

Figure1 manifests the network model of vehicular delay-tolerant networks, and message is forwarded by assistant node from the source nodes to the base station. In other words, message is transmitted from one vehicle to another vehicle in the range of communication.Figure 1
Network model of vehicular delay-tolerant networks.Different vehicles, as a general rule, may have different speeds; for example, the vehicle in the fast traffic lane usually runs faster than those in the slow traffic lane. We can setn levels of the vehicle speed, from slow to fast, which are denoted by v1,v2,…,vn (vi, i=1,2,...,n), respectively. For convenience sake, we firstly consider vehicles traveling in the same direction. We can assume the set Si={xi,j(t),j∈N}, (i=1,2,…,n), is the set of vehicles traveling at the speed vi, where xi,j(t) indicates the jth vehicle of the set Si at time t and t is discrete, t∈N, and N is the natural number.Assume the relationship of vehicle speedv and vehicle density λ is as follows:(12)v=a-bλ;when λ=0, the vehicle density is 0, and then the vehicle speed v can achieve the largest value vf; that is, when λ=0, then a=vf. When λ=λf, it means the vehicle density achieves the largest value λf, and then the vehicle speed will be 0 and the road is congested; that is, when λ=λf, then b=vf/λf. Thus it can be seen that the relationship of vehicle speed v and vehicle density λ is(13)v=a-bλ=vf-vfλfλ=vf1-λλf.


## 4.2. Definition of Transmission Delay

In vehicular delay-tolerant networks, transmission delay is mainly caused by message retransmission due to communication breakdown or signal interference. While compared with the time of a message transmitted from one vehicle to the other vehicle, message retransmission delay is short enough. So we can ignore it.Assuming that a vehicleN1 broadcasts a message at the time t=0, we can take I(t) as the set of vehicles having received the message from N1 at time t and take T(k)=inf⁡{t≥0:xk∈I(t)} as the time when vehicle Nk receives the message, and then the transmission delay from vehicle Np to vehicle Nq can be defined as follows:(14)Dp,q=Tq-Tp=∑k=pq-1Tk+1-Tk.


## 4.3. Details of Routing Protocol

In the routing protocol based on angle and density (abbreviated to RPAD) proposed in this paper, the density and direction of vehicle are used for estimate. When a vehicle wants to send message to the base station, it will compute the angle between itself and the base station in order to choose relay vehicles in the suitable direction along to the base station, and meanwhile it will confirm the next hop after predicting vehicle density.Assuming vehicle O is the source node, we create a coordinate and take O as the center, shown in Figure2. Vehicles A and B are in the communication range of vehicle O, and vehicle C is in the communication range of vehicle B. To reduce the transmission distance of a message and then to reduce the transmission delay, we need to unify the direction of the next hops and the message could be transmitted in the unified direction along to the base station as a guarantee of delivery ratio. Vehicle O obtains the angle between itself and the base station by the GPS device it equips, and if the angle value is larger than 45°, then it will choose those vehicles whose angle between themselves and the base station is smaller than 45° as the next hops. In Figure 2, the angle between vehicle B and the base station is ∠1<45°, while that between vehicle A and the base station is ∠2>45°, and then vehicle O will choose vehicle B as the next hop and sends message to vehicle B. Similarly, through the comparison of angles, vehicle B will choose vehicle C as the next hop. Consequently, the message of vehicle O will be forwarded along the direction like a stepped appearance shown in Figure 2 finally to the base station.Figure 2
Coordinate of vehicle O.However, there may be many vehicles satisfying the condition of angle direction. When a vehicle decides the next hop, it cannot send a copy of the message to all the condition-satisfied vehicles for the purpose of energy-efficiency. It is found by studies that, in the area of high vehicle density, a source vehicle can transmit messages rapidly step by step through other vehicles as a relay until the destination vehicle, instead of carrying the messages until the source vehicle encounters the destination vehicle. Thus, message can be delivered faster to the destination, and then transmission delay is reduced.Yazhi demonstrates the following theorem [13] through theoretical analysis and simulation experiment.Theorem 1.
There exists a relationship between the transmission delayT0,m and corresponding transmission distance m:(15)limm→∞T0,mm=α.
Based on (15), when the vehicle density and speed are fixed, α is a constant:(16)α=limm→∞E(T0,m)m.Theorem1 demonstrates that the limited ratio of transmission delay and transmission distance is α, and α is a constant when vehicle density is fixed, so transmission delay is linearly associated with transmission distance. The upper bound of the coefficient of the linear relation changes with vehicle density and speed, and so transmission delay decreases with the increase of vehicle density.In RPAD, after selecting a direction, the vehicle will decide to transmit messages to those vehicles with higher density in their own areas.Taking vehicle O for an example,Si={xi,j(t),j∈N}, (i=1,2,…,n), is the set of vehicles traveling at the relative speed vi. In the next time s, S={xi,j(t)+vi(s-t),i=1,2,…,n,j∈N} represents the relative distance between vehicles that satisfied the requirement of angle direction and vehicle O. Vehicle O will further choose those vehicles with higher area density as next hops according to the relative distance and then sends messages to them. Other vehicles repeat the above process until the base station receives the messages.


## 5. Experiment Simulation Results and Analysis

### 5.1. Correctness Proof of Privacy Protection Protocol

#### 5.1.1. Certification

It is obvious from Section3 that(17)U1=X1×Y1=α0+α1×ci+⋯+αj×cij+gc(ci)=uci+gcci=fci+gci,U2=X2×Y2=β0+β1×ci+⋯+βk×cik+h(ci)=vci+hci=fci×gci.IfU1=0 and U2=0, then(18)f(ci)+g(ci)=0,f(ci)×g(ci)=0.Therefore,f(ci)=0 and g(ci)=0.Based on (1), ci∈Sa and ci∈Sb.


#### 5.1.2. Disproof

Ifci∈Sa and ci∈Sb, then, with (1), f(ci)=0 and g(ci)=0.WhileU1=fci+g(ci) and U2=f(ci)×g(ci), U1=0 and U2=0.SoU1=0∩U2=0⇔ci∈Sa∩Sb∩Sc.In conclusion, the privacy protocol is proved to be correct.


### 5.2. Security Proof of Privacy Protection Protocol

Next, it will be proved that vehicles A, B, and C will finally obtain the information of common parking spaces without leaking out their respective private information of parking spaces.(a) Vehicles A and B. Vehicle A has ga(x) and vehicle B has fb(x), while ga(x) is justly the part of g(x) and fb(x) is the part of f(x), and as a result vehicle A cannot get gx from ga(x) and vehicle B cannot get f(x) from fb(x). In other words, vehicle A will not obtain private parking space information of vehicle B, and so does vehicle B.(b) Vehicle C. Vehicle C has fc(x) and gc(x), while fc(x) is justly the part of f(x) and gc(x) is the part of g(x). In addition, hcx=fbx×gcx+0.5×ga(x)×fb(x). So vehicle C cannot get f(x) and g(x); that is, vehicle C will not obtain private parking space information of vehicles A and B.Above all, private parking space information of the three vehicles has not been leaked out, so the protocol is secure.


### 5.3. Performance Analysis of Privacy Protection Protocol

Here, the complexity of communication round and computation is evaluated. Performance comparison results of some privacy protection schemes are shown in Table1.Table 1
Performance comparison of some privacy protection schemes.
Communication round complexity
Computation complexity
Degree of privacy protection
Scheme in this paper
3
O
(
n
)
Zero leakage
Shantanu’s scheme [4]
n
O
(
n
3
)
Zero leakage
Shantanu’s promoted scheme [5]
n
O
(
n
3
)
Zero leakage
Yang’s scheme [6]
4
O
(
n
2
)
Zero leakage
Huang’s scheme [6]
3
O
(
n
2
)
The TP obtains all messages from two participantsObviously from Table1, the scheme proposed in this paper has the same communication rounds with Huang’s scheme that is superior to other schemes whose communication cost is proportional to original vector dimensions n. Meanwhile, on the premise of privacy zero leakage, our scheme obtains the best computation complexity O(n), owing to the lightweight mathematical method rather than traditional homomorphism encryption applied in other schemes.


### 5.4. Simulation Results and Analysis of Routing Protocol

We use ONE (opportunistic network environment) to realize the simulations on RPAD proposed in this paper. ONE is specially designed for simulations in delay-tolerant networks, having implemented some classical routing algorithms, like epidemic, SW, SF, and so on. Some main simulation parameters are described in Table2.Table 2
The main simulation parameters.
Parameters
Value
Simulation time (hour)
10
Simulation range (width, height: meter)
80000, 58400
Number of vehicles
100–200
Vehicle speed (high, low: meter/s)
24, 6
Communication distance (meter)
150
Number of copies of SW/SF
10In the experiment, the transmission ratio is defined as the ratio of a number of messages that have been transmitted successfully and that have been generated. Transmission delay is defined in Section3.2. To evaluate the performance of these algorithms RPAD, SW, SF, and PER, we vary the vehicle speed and the number of vehicle nodes.


#### 5.4.1. Influence of Vehicle Speed

Figures3 and 4 indicate the influence of vehicle speed on transmission ratio and transmission delay, respectively. When the vehicle speed increases, the transmission ratio increases and transmission delay decreases, because when the vehicle runs at a higher speed, messages carried by vehicles are forwarded faster; that is, the time from the source node to the destination node will be shorter. It can be concluded from Figures 3 and 4 that RPAD performs better than SW, SF, and PER.Figure 3
The influence of vehicle speed on transmission ratio.Figure 4
The influence of vehicle speed on transmission delay.


#### 5.4.2. Influence of Total Number of Vehicle Nodes

Figures5 and 6 indicate the influence of total number of vehicles on transmission ratio and transmission delay. When the total number of vehicles increases, the transmission ratio increases and transmission delay decreases. In fact, when there are many vehicles in network, messages are transmitted form one vehicle to another quickly, and vehicles do not need to carry the messages for a long time. It can be seen from Figures 5 and 6 that RPAD is superior to SW, SF, and PER.Figure 5
The influence of number of vehicles on transmission ratio.Figure 6
The influence of number of vehicles on transmission delay.


#### 5.4.3. Influence of Time to Live (TTL)

Figures7 and 8 demonstrate the influence of the total number of time to live values on transmission ratio and transmission delay. If the value of TTL is low, all algorithms perform terribly. When the value of TTL increases, transmission ratio increases, while transmission delay decreases, and when more and more nodes are dead, it will take longer for nodes to transmit messages to others. It is clearly observed from Figures 7 and 8 that RPAD holds the higher transmission ratio and shorter transmission delay.Figure 7
The influence of TTL on transmission ratio.Figure 8
The influence of TTL on transmission delay.


## 5.1. Correctness Proof of Privacy Protection Protocol

### 5.1.1. Certification

It is obvious from Section3 that(17)U1=X1×Y1=α0+α1×ci+⋯+αj×cij+gc(ci)=uci+gcci=fci+gci,U2=X2×Y2=β0+β1×ci+⋯+βk×cik+h(ci)=vci+hci=fci×gci.IfU1=0 and U2=0, then(18)f(ci)+g(ci)=0,f(ci)×g(ci)=0.Therefore,f(ci)=0 and g(ci)=0.Based on (1), ci∈Sa and ci∈Sb.


### 5.1.2. Disproof

Ifci∈Sa and ci∈Sb, then, with (1), f(ci)=0 and g(ci)=0.WhileU1=fci+g(ci) and U2=f(ci)×g(ci), U1=0 and U2=0.SoU1=0∩U2=0⇔ci∈Sa∩Sb∩Sc.In conclusion, the privacy protocol is proved to be correct.


## 5.1.1. Certification

It is obvious from Section3 that(17)U1=X1×Y1=α0+α1×ci+⋯+αj×cij+gc(ci)=uci+gcci=fci+gci,U2=X2×Y2=β0+β1×ci+⋯+βk×cik+h(ci)=vci+hci=fci×gci.IfU1=0 and U2=0, then(18)f(ci)+g(ci)=0,f(ci)×g(ci)=0.Therefore,f(ci)=0 and g(ci)=0.Based on (1), ci∈Sa and ci∈Sb.


## 5.1.2. Disproof

Ifci∈Sa and ci∈Sb, then, with (1), f(ci)=0 and g(ci)=0.WhileU1=fci+g(ci) and U2=f(ci)×g(ci), U1=0 and U2=0.SoU1=0∩U2=0⇔ci∈Sa∩Sb∩Sc.In conclusion, the privacy protocol is proved to be correct.


## 5.2. Security Proof of Privacy Protection Protocol

Next, it will be proved that vehicles A, B, and C will finally obtain the information of common parking spaces without leaking out their respective private information of parking spaces.(a) Vehicles A and B. Vehicle A has ga(x) and vehicle B has fb(x), while ga(x) is justly the part of g(x) and fb(x) is the part of f(x), and as a result vehicle A cannot get gx from ga(x) and vehicle B cannot get f(x) from fb(x). In other words, vehicle A will not obtain private parking space information of vehicle B, and so does vehicle B.(b) Vehicle C. Vehicle C has fc(x) and gc(x), while fc(x) is justly the part of f(x) and gc(x) is the part of g(x). In addition, hcx=fbx×gcx+0.5×ga(x)×fb(x). So vehicle C cannot get f(x) and g(x); that is, vehicle C will not obtain private parking space information of vehicles A and B.Above all, private parking space information of the three vehicles has not been leaked out, so the protocol is secure.


## 5.3. Performance Analysis of Privacy Protection Protocol

Here, the complexity of communication round and computation is evaluated. Performance comparison results of some privacy protection schemes are shown in Table1.Table 1
Performance comparison of some privacy protection schemes.
Communication round complexity
Computation complexity
Degree of privacy protection
Scheme in this paper
3
O
(
n
)
Zero leakage
Shantanu’s scheme [4]
n
O
(
n
3
)
Zero leakage
Shantanu’s promoted scheme [5]
n
O
(
n
3
)
Zero leakage
Yang’s scheme [6]
4
O
(
n
2
)
Zero leakage
Huang’s scheme [6]
3
O
(
n
2
)
The TP obtains all messages from two participantsObviously from Table1, the scheme proposed in this paper has the same communication rounds with Huang’s scheme that is superior to other schemes whose communication cost is proportional to original vector dimensions n. Meanwhile, on the premise of privacy zero leakage, our scheme obtains the best computation complexity O(n), owing to the lightweight mathematical method rather than traditional homomorphism encryption applied in other schemes.


## 5.4. Simulation Results and Analysis of Routing Protocol

We use ONE (opportunistic network environment) to realize the simulations on RPAD proposed in this paper. ONE is specially designed for simulations in delay-tolerant networks, having implemented some classical routing algorithms, like epidemic, SW, SF, and so on. Some main simulation parameters are described in Table2.Table 2
The main simulation parameters.
Parameters
Value
Simulation time (hour)
10
Simulation range (width, height: meter)
80000, 58400
Number of vehicles
100–200
Vehicle speed (high, low: meter/s)
24, 6
Communication distance (meter)
150
Number of copies of SW/SF
10In the experiment, the transmission ratio is defined as the ratio of a number of messages that have been transmitted successfully and that have been generated. Transmission delay is defined in Section3.2. To evaluate the performance of these algorithms RPAD, SW, SF, and PER, we vary the vehicle speed and the number of vehicle nodes.


### 5.4.1. Influence of Vehicle Speed

Figures3 and 4 indicate the influence of vehicle speed on transmission ratio and transmission delay, respectively. When the vehicle speed increases, the transmission ratio increases and transmission delay decreases, because when the vehicle runs at a higher speed, messages carried by vehicles are forwarded faster; that is, the time from the source node to the destination node will be shorter. It can be concluded from Figures 3 and 4 that RPAD performs better than SW, SF, and PER.Figure 3
The influence of vehicle speed on transmission ratio.Figure 4
The influence of vehicle speed on transmission delay.


### 5.4.2. Influence of Total Number of Vehicle Nodes

Figures5 and 6 indicate the influence of total number of vehicles on transmission ratio and transmission delay. When the total number of vehicles increases, the transmission ratio increases and transmission delay decreases. In fact, when there are many vehicles in network, messages are transmitted form one vehicle to another quickly, and vehicles do not need to carry the messages for a long time. It can be seen from Figures 5 and 6 that RPAD is superior to SW, SF, and PER.Figure 5
The influence of number of vehicles on transmission ratio.Figure 6
The influence of number of vehicles on transmission delay.


### 5.4.3. Influence of Time to Live (TTL)

Figures7 and 8 demonstrate the influence of the total number of time to live values on transmission ratio and transmission delay. If the value of TTL is low, all algorithms perform terribly. When the value of TTL increases, transmission ratio increases, while transmission delay decreases, and when more and more nodes are dead, it will take longer for nodes to transmit messages to others. It is clearly observed from Figures 7 and 8 that RPAD holds the higher transmission ratio and shorter transmission delay.Figure 7
The influence of TTL on transmission ratio.Figure 8
The influence of TTL on transmission delay.


## 5.4.1. Influence of Vehicle Speed

Figures3 and 4 indicate the influence of vehicle speed on transmission ratio and transmission delay, respectively. When the vehicle speed increases, the transmission ratio increases and transmission delay decreases, because when the vehicle runs at a higher speed, messages carried by vehicles are forwarded faster; that is, the time from the source node to the destination node will be shorter. It can be concluded from Figures 3 and 4 that RPAD performs better than SW, SF, and PER.Figure 3
The influence of vehicle speed on transmission ratio.Figure 4
The influence of vehicle speed on transmission delay.


## 5.4.2. Influence of Total Number of Vehicle Nodes

Figures5 and 6 indicate the influence of total number of vehicles on transmission ratio and transmission delay. When the total number of vehicles increases, the transmission ratio increases and transmission delay decreases. In fact, when there are many vehicles in network, messages are transmitted form one vehicle to another quickly, and vehicles do not need to carry the messages for a long time. It can be seen from Figures 5 and 6 that RPAD is superior to SW, SF, and PER.Figure 5
The influence of number of vehicles on transmission ratio.Figure 6
The influence of number of vehicles on transmission delay.


## 5.4.3. Influence of Time to Live (TTL)

Figures7 and 8 demonstrate the influence of the total number of time to live values on transmission ratio and transmission delay. If the value of TTL is low, all algorithms perform terribly. When the value of TTL increases, transmission ratio increases, while transmission delay decreases, and when more and more nodes are dead, it will take longer for nodes to transmit messages to others. It is clearly observed from Figures 7 and 8 that RPAD holds the higher transmission ratio and shorter transmission delay.Figure 7
The influence of TTL on transmission ratio.Figure 8
The influence of TTL on transmission delay.


## 6. Conclusions

In this paper, we address the conflict of two vehicles happening to choose the same parking space in vehicular delay-tolerant network. We design the routing protocol RPAD from the direction and distribution density of the vehicle and the base station is considered as a reference. The vehicles having the same direction of that along the reference direction and higher distribution density are chosen for the next hop. A multiparty computation based privacy protection scheme is also proposed for security consideration.The remaining work is the validations of our scheme on real data and applications in various delay-tolerant environments where generalizing the assumptions will be taken. Due to the limited time and conditions, now we do not have so many vehicles to solidify the proposed approach, and the demonstration of the validity through some real cases will be done in the further work.



---

*Source: 420912-2015-08-02.xml*