# Anomaly Detection for Internet of Vehicles: A Trust Management Scheme with Affinity Propagation

Authors: Shu Yang; Zhihan Liu; Jinglin Li; Shangguang Wang; Fangchun Yang
Journal: Mobile Information Systems
 (2016)

---

## Abstract

Anomaly detection is critical for intelligent vehicle (IV) collaboration. Forming clusters/platoons, IVs can work together to accomplish complex jobs that they are unable to perform individually. To improve security and efficiency of Internet of Vehicles, IVs’ anomaly detection has been extensively studied and a number of trust-based approaches have been proposed. However, most of these proposals either pay little attention to leader-based detection algorithm or ignore the utility of networked Roadside-Units (RSUs). In this paper, we introduce a trust-based anomaly detection scheme for IVs, where some malicious or incapable vehicles are existing on roads. The proposed scheme works by allowing IVs to detect abnormal vehicles, communicate with each other, and finally converge to some trustworthy cluster heads (CHs). Periodically, the CHs take responsibility for intracluster trust management. Moreover, the scheme is enhanced with a distributed supervising mechanism and a central reputation arbitrator to assure robustness and fairness in detecting process. The simulation results show that our scheme can achieve a low detection failure rate below 1%, demonstrating its ability to detect and filter the abnormal vehicles.


---

## Body

## 1. Introduction

Internet of Vehicles (IoV) is an open converged network system supporting human-vehicles-environment cooperation [1]. Fusing multiple advanced terms, such as VANET [2], autonomous driving [3], cloud computing [4], and multiagent system (MAS) [5], this hybrid concept plays a fundamental role towards a cooperative and effective intelligent transport system. An anomaly detection scheme is desirable in an environment filled up with uncertainty. Primarily, the security problem is motivated by the question [6] “How can I trust the information content I receive?” This issue is then decomposed into two subterms: “Is the communication channel via which I receive messages from a sender secure?” and “How can I trust the sender of the messages I receive?” The decomposition allows us to tell the difference betweencomputational trust andbehavioral trust. Being a complementary part ofcomputational trust (such as encryption and tamper-proofing), the model ofbehavioral trust admits information’s imperfection in an open system; therefore, individuals need extra trust-related information in decision-making [7]. Extra trust-related information could be extracted from history reputation or could be elicited from interaction experience between two individuals. Being capable of providing a measurement of trustworthiness, behavioral-based trust management enables intelligent vehicles to improve collaborations by reducing false or malicious behaviors. Anomaly detection technology is the key method to build behavioral trust.This paper aims to detect anomaly vehicles in autonomous driving environment. As commercial IVs are drawing near, we have to face the facts that vehicles are more and more intelligent. Meanwhile, cyber vehicles are unprecedented and vulnerable when supported by an uncertain and dynamic network [8]. Malicious attacks and information tampering, along with system failures, will directly threaten human lives and properties. Anomaly vehicles include malicious vehicles and incapable vehicles. Malicious vehicles are entities with intentions to make damage in driving environment. Incapable vehicles are not intentionally to give negative influence; however, they may disturb order due to their limited capability. For example, an incapable intelligent vehicle could not behave properly in a rigid and accurate-ordered automatic driving platoon but may behave well in a normal driving pattern. On the other hand, a malicious intelligent vehicle should be forbidden in any situation. To highlight our motivations, we present the following two illustrative scenarios.Scenario 1: in cluster/platoon-based driving, IVs frequently communicate with each other to maintain lateral/longitudinal control. Vehicles with incapability or malicious intention may join the cluster or platoon. Their malicious or false behaviors are very likely to temper/disturb collaboration. In this safety-oriented case, local vehicles should be able to maintain robust intracluster trust to wipe out unqualified vehicles.Scenario 2: in efficiency-oriented case, where IVs need to collaborate in a broad area, they exchange message to presence traffic conditions, request parking plot information through VANET, and even negotiate routes to prevent traffic congestions. None of these three functions would be efficient without trustworthy collaboration. The above two scenarios suggest that a trust management scheme with anomaly detection is urgently need.Solutions on IoV’s anomaly detection still face many challenges raised by mobility including dynamic vehicle groups, real-time constraints, and intrinsic dynamic property of trust itself, which makes single or static trust measurement ineffective. Considering the mobile nature of vehicles, topology is changing so rapidly that preestablished trust relationships are likely to be invalid. As a result, two nodes need to build up trust in a timely fashion. Moreover, trust is not constant but changing along with different driving situations. An accurate trust should capture the context of interaction and history reputation. For example, a car with good reputation may not be trustworthy when it is over speed. Trust management system therefore calls for the ability to synthesize multiple resources, either from roads or from cloud. The essence of Internet of Vehicles is to obtain more safety and efficiency by integrating multiple infrastructures, networks, and vehicle intelligence. In accordance with this idea, we propose a hybrid approach called Cluster-Based Anomaly Detection (CAD). Figure1 describes the framework of CAD. CAD is composed of two big components, namely, cluster-based trust component and central reputation component. Cluster-based trust component builds time-fashioned trust to reflect dynamic situation while central reputation component is to evaluate one’s trust from a long-term perspective. These two components interact by evidence uploading and reputation providing. Cluster-based trust component has two major functions, namely, trust-based AP clustering and mutual supervision to maintain the robustness of dynamic trust.Figure 1
Framework of CAD.The major contribution of this paper lies in the following two aspects:(i)
We identify cluster-based trust and reputation as two major components of anomaly detection. To exploit cluster-based trust, we propose a cluster-based trust evaluation algorithm, which modifiesAffinity Propagation Clustering to generate the most trustworthy cluster head based on evaluation and communication. The algorithm runs in a distributed manner and shows robustness to malicious/incapable vehicles.
(ii)
We adopt a sparse RSU-enhanced reputation provision scheme. Central Arbitrator (CA) collects evidences from sparse RSUs. Then, a reputation system is established to evaluate global and history reputation from accumulated data.


## 2. Related Work

Trust issues stem from secure and social psychology fields and have been growing theoretically in organization management. More recently, as network technology is constantly changing the way people interact, former stable and well-structured organizations are likely to transform into another paradigm featured by agile structures and ad hoc groups. IoV, for example, is a typical agile structure that calls for collaboration among agents. Ramchurn et al. [9] pointed out that “trust pervades multiagent interaction at all levels,” generally including (
1
) individual-level trust, whereby an agent has some beliefs about the honesty or reciprocative nature of its interaction partners, and (
2
) system-level trust, whereby the agents in the system are forced to be trustworthy by the rules of encounter that regulate the system. Although various schemes have been investigated, the author noticed that trust at these two levels has been dealt with separately in most times. This insight inspired us to develop a hybrid framework which takes both levels of trust into consideration.Most existing systems in VANETs use distributed approach. Raya et al. [10] argue that the trust should be attributed to data per se in ephemeral ad hoc networks and proposed a framework for data-centric trust establishment. Their scheme shows high resilience to attackers and could converge to stable right decision. However, Raya’s trust mechanism may make no contribution to reduce attackers in system level; since there is no punishment for cheating, attackers are seldom suppressed. Chen et al. [11] present a decentralized framework combined with message propagation and trust evaluation in VANET. Specifically, trust measurement consists of role-based trust and experience-based trust. It is a good attempt to synthesize static priori trust (role-based trust) with dynamic situational trust (experience-based trust). Nonetheless, they did not take historical reputation into consideration. Rostamzadeh et al. [12] focus on trustworthy information dissemination by assigning trust value to each road segment. The dissemination task is to find a path which consists of a series of safe road segments. Their work is featured by good scalability and thus potential in many applications. DTM2 [13] is a distributed trust model inspired by Job Market model. With the help of third party hardware, system could incent good behaviors and punish malicious behaviors by changing each vehicle’s signal value. To conclude, the decentralized approach is developed under the assumption that there is no centralized third party to evaluate and maintain the trust value.Recently, the RSU deployment is promoted by intelligent transport system group. Centralized trust management is not an ambiguous goal with the help of RSUs. Centralized approach is able to evaluate trust value from a global and historical view. Therefore, many works have preliminarily emerged centralized trend as a complementary of distributed system. Wang et al. [14] proposed a vertical handoff method, which improves availability of network access. Their method therefore makes contributions to building centralized trust management system. Machado and Venkatasubramanian [15] aim to aggregate advantages of both centralized and distributed trust computation. The authors categorize the messages exchanged in VANET intoalerts andreports; alerts are time-critical in response to an incident while reports are evidence to evaluate quality of alerts. RSUs play Central Authority (CA) who keep track of messages and accordingly maintain a global reputation for each vehicle. Their central grading system could efficiently distinguish dishonest nodes in real-life scenarios. Huang et al. [16] utilize identity-based cryptography to integrate entity-based trust and social trust in proxy server. The email interactions among individuals are mined to obtain social trust. Trust measurement should be requested and acquired from this server. One disadvantage of this system, as the author mentioned, is that service may experience long delay due to network latency and the management entities to mine the email source. Such latency problem bothers centralized reputation system. The author then proposes a situation-aware trust architecture for VANETs [17]. A predictive trust setup system is designed to reduce on-the-scene trust setup latency. They also envision that the roadside infrastructure deserves more attention and research.


## 3. Trust Establishment by Peer Detecting

In this section, we illustrate the establishment of cluster-based trust. To establish trust among IVs, the key is to generate the trustworthy CH. Cluster and its head are generated after several rounds of iteration. The generated CH is an authoritative node managing intracluster trust. One of the cluster algorithms which works by passing messages between nodes isAffinity Propagation (AP). To start, measures of similarities are calculated for each pair; real-valued messages are then exchanged between pairs of nodes until high quality exemplars and corresponding clusters gradually emerge. The schematic is shown in Figure 2.Figure 2
Four steps of Peer Detecting-based trust establishment.AP works by passing messages between nodes, which is naturally more suitable for trust establishment than other clustering algorithms because of the following characteristics:(
1
) transitivity: in trust theory, if n
o
d
e
A has no direct trust with n
o
d
e
C, it could still build an indirect trust relation via n
o
d
e
B to n
o
d
e
C; likewise, in our AP, v
e
h
i
c
l
e
A makes a judgement about v
e
h
i
c
l
e
C with the help of indirect judgement from other nodes; the primitive AP clustering algorithm therefore well-reflects transitivity, making it fit into trust establishment; (
2
) asymmetry: trust is not symmetric; that n
o
d
e
A trusts n
o
d
e
B does not guarantee n
o
d
e
B trusts n
o
d
e
A. AP has the ability to cluster by asymmetric “distance measurement”; (
3
) distributed manner: AP runs in a completely distributed manner, increasing robustness to attacks; (
4
) moreover, it achieves a much lower average squared error than normal clustering method [18].The AP algorithm works iteratively. The similaritys
(
i
,
j
) is sent from n
o
d
e
i to n
o
d
e
j to measure “distance” between a pair. The responsibility r
(
i
,
j
) is sent from n
o
d
e
j to n
o
d
e
i to tell how eager i wants j to be CH. The availability a
(
i
,
j
) is sent from n
o
d
e
i to n
o
d
e
j to tell how eager j wants to bei’s CH. The self-responsibility r
(
i
,
i
) and self-availability a
(
i
,
i
) both represent accumulated evidence reflecting if i is suitable to be CH. The updating process for responsibility and availability in every iteration procedure is illustrated below. More detailed works are [18, 19], which have lain the foundation of our work.Primitive AP Iteration Process is as follows:(1)
r
i
,
j
⟵
s
i
,
j
-
max
k
s
.
t
.
k
≠
j
⁡
a
i
,
k
+
s
i
,
k
,
a
i
,
j
⟵
min
⁡
0
,
r
j
,
j
+
∑
∀
k
≠
i
,
j
m
a
x
0
,
r
k
,
j
,
a
j
,
j
⟵
∑
k
s
.
t
.
k
≠
j
m
a
x
0
,
r
k
,
j
.To make real-valued message converge, messages are damped byλ, M
e
s
s
a
g
e
n
e
w
=
λ
M
e
s
s
a
g
e
o
l
d
+
1
-
λ
M
e
s
s
a
g
e
n
e
w, where λ is a weighing factor that ranges from 0 to 1. When messages converged, a CH is generated:(2)
C
H
i
=
m
a
x
j
a
i
,
j
+
r
i
,
j
.


### 3.1. UntrustDegree

Our proposed scheme uses the fundamental idea of Affinity Propagation from a trust perspective. In general, AP could detect anomaly vehicles in a group. We design anUntrustDegree function as “distance measurement” for AP algorithm to find “the most trustworthy node,” that is, to find the node which minimizes overall UntrustDegree. The function U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j is automatically calculated by IV. An IV can observe other vehicles’ behaviors and give an UntrustDegree according to its knowledge:(3)
U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
=
F
i
I
d
e
n
t
i
t
y
,
S
i
t
u
a
t
i
o
n
→
,
B
e
h
a
v
i
o
r
→
j
∈
0,1
.Identity is one item from set I
d
=
{
b
u
s
,
t
a
x
i
,
p
o
l
i
c
e
,
p
r
i
v
a
t
e
,
…
} denoting real identity of one car and could be represented by a unique digital number. S
i
t
u
a
t
i
o
n
→ is a vector predefined as some basic values which gives environmental context (e.g., the weather). B
e
h
a
v
i
o
r
j
→ is a vector recording basic actions that I
V
j has done recently. With the help of behavior detection technologies [20] or interactive gaming [21], we reasonably assume that IVs are intelligent enough to evaluate each other. The value, U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
∈
0,1, is primarily positive but set negative, namely, -
U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
∈
-
1,0, to fit AP algorithm.The self UntrustDegree,U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
i, is initialized to the same value. It should be noted that a higher self-trust degree makes it more likely to become the cluster head. In our final model (discussed in Section 5.2), valid self-trust is set at a value which balancesIV’s evaluation andhistorical reputation.Historical reputation can only be legally announced by CA. When a group of IVs pass by a RSU, RSU will proactively download/broadcast reputations to IVs.


### 3.2. Mutual Supervisor Model

EachI
V
i receives responsibility r
(
i
,
j
) from the neighborhood. Also, I
V
i broadcasts a
(
i
,
j
) to the neighborhood to claim how suitable it is to become a CH. However, a malicious/incapable node can cheat/mistake in this message passing process by broadcasting a false a
(
i
,
j
). For example, if I
V
i broadcasts very high a
(
i
,
j
) to other nodes, it is more likely to be elected CH according to the AP algorithm. We need a mechanism to prevent nodes broadcast false availability or responsibility.We proposed a supervisor model to alleviate cheating/mistaking in this process. The core of mutual supervisor model is to matchI
V
i with a supervisor I
V
j. Among moving companions of one vehicle, a supervisor is anotherIV which can receive almost the same broadcast information by sharing the same wireless channel. A supervisor therefore listens to the supervisee related message to validate availability/responsibility by repeating the calculation of suspicious I
V
i. The result calculated by I
V
i itself is R
e
s
u
l
t
i
i. The supervisor I
V
j’s calculation result for I
V
i is R
e
s
u
l
t
i
j. If the two results R
e
s
u
l
t
i
i and R
e
s
u
l
t
i
j have large difference, then this means I
V
i is very likely to have cheated in message passing process. The integral mechanism of supervisor model is illustrated in Figure 3.Figure 3
Mutual supervisor model.To assure a stable and honest supervisor, we apply Algorithm1. From this algorithm, we see that I
V
i has possibility to supervise another I
V
j only when (1) I
V
i does not tend to believe I
V
j and (2) I
V
i and I
V
j have small relative mobility. That is, they are stable driving companions. This mechanism builds up mutual supervision relationship between two adversary nodes so that supervisor and supervisee are not likely to collude. More important, it can identify cheating nodes in message passing process.Algorithm 1:Supervisor Matching algorithm.
Input: a supervisor I
V
i, nearby node’ states (position, speed)
Output: pair(supervisor, supervisee)
(1) ForNode  I
V
j  in DSRC(Dedicated Short Range Communication) range
(2)M
i
,
j
=
M
o
b
M
e
t
r
P
o
s
i
,
P
o
s
j
,
S
p
e
e
d
i
,
S
p
e
e
d
j //calculate mobility metric
(3) IfI
V
j  has no supervisor and U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
≤
T
h
r
e
s
h
o
l
d
(4)Then Add  I
V
j  in Supervisee Candidate List
(5) End For
(6) ForI
V
j  in Supervisee Candidate List
(7)  IfM
i
,
j
<
M
min
⁡ Then k
=
j   //find the most stable supervisee
(8) End For
(9) Returnmatched pair(I
V
i, I
V
k)     //i  supervises  kThe input of Algorithm1 is IV’s state tuples (position, speed). For I
V
i, running this algorithm will work out a supervisee. For each I
V
j in DSRC range, I
V
i calculates mobility metric M
i
,
j (lines (1)-(2)); the smaller the metric is, the more similar the two motions are. Thus, a small metric indicates a stable driving companion. If any I
V
j has no supervisor and U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
≤
T
h
r
e
s
h
o
l
d (this indicates that i does not tend to trust j), I
V
i adds I
V
j in Supervisee Candidate List (Line (3)-(4)). After that, I
V
i chooses the most stable candidate (with the smallest mobility metric) to be the supervisee (lines (6)–(8)). Finally, a pair (I
V
i
,
I
V
j) is returned (line (9)).


### 3.3. Generating CH by Message Passing

We try to use a distributed algorithm to reach a consensus among large amounts of opinions. EachI
V
i maintains a neighbor list N
i. As Table 1 shows, the list consists of N
i
j for each neighbor I
V
j. Additionally, I
V
i also maintains a supervision field for a supervisee I
V
k.Table 1
Neighbor and supervision field.
Neighbor field
Supervision field
(
x
,
y
)
j
Position ofI
V
j
a
′
(
k
,
j
)
I
V
k’s last availability received from I
V
j
(
v
x
,
v
y
)
j
Speed ofI
V
j
U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
UntrustDegree fromI
V
i to I
V
j
a
′
(
j
,
k
)
I
V
k’s last availability sent to I
V
j
a
(
i
,
j
)
Last availability received fromI
V
j
a
(
j
,
i
)
Last availability sent toI
V
j
r
′
(
k
,
j
)
I
V
k’s last responsibility received from I
V
j
r
(
i
,
j
)
Last responsibility received fromI
V
j
r
(
j
,
i
)
Last responsibility sent toI
V
j
r
′
(
j
,
k
)
I
V
k’s last responsibility sent to I
V
j
C
H
c
n
v
g
,
j
Cluster head converge flag forI
V
j
S
U
P
V
E
j
I
V
j’s superviseeGenerating CH needs several iterations which are periodically triggered by time. Besides, broadcasting and supervising also need a synchronous clock.Hello beacons are broadcast and received to maintain local awareness.Broadcast and Receive Hello Beacons Process is as follows:(1)
For everyT
h
e
l
l
o, each I
V
j broadcasthello beacon is(4)
j
,
x
,
y
j
,
v
x
,
v
y
j
,
C
H
j
,
S
U
P
V
E
j
.
(2)
Each receiving neighborI
V
i calculates U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j if they are traveling in the same direction.
(3)
I
V
i adds/updates N
i
j in its neighbor list:(5)
j
,
x
,
y
j
,
v
x
,
v
y
j
,
U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
,
C
H
j
,
S
U
P
V
E
j
.Availability and responsibility messages should be broadcast periodically. We define this period asT
m
e
s
s
a
g
e. Each I
V
i will calculate a
(
j
,
i
) and r
(
j
,
i
) for each neighbor I
V
j. This value is damped with the previous value stored in the neighbor list. I
V
j then broadcasts a
(
j
,
i
) and r
(
j
,
i
) of all neighbors I
V
j.According to mutual supervisor model, the process of calculatinga
(
j
,
i
) and r
(
j
,
i
) should be supervised. Each IV automatically chooses a supervisee bySupervisor Matching algorithm. Supervisor checks supervisee’s calculation result and releasesalert on condition that supervisee’s message is suspicious. The process enhanced by mutual supervisor model is illustrated below.Supervising and Message Passing Process. For every T
m
e
s
s
a
g
e, each I
V
i will do the following:(1)
It will find a matching superviseeI
V
k which is prepared for the next T
r
o
u
n
d’s iteration. If found in this T
m
e
s
s
a
g
e, it is claimed by S
U
P
V
E
j. If failed, it will try next T
m
e
s
s
a
g
e.
(2)
If it hears analert about I
V
n, each I
V
i will ignore I
V
n’s messages in this T
r
o
u
n
d.
(3)
It will calculate responsibilityr
(
i
,
j
) for each neighbor I
V
j.
(4)
It will update with damping factor and store:r
i
,
j
=
1
-
λ
r
i
,
j
n
e
w
+
λ
r
i
,
j
o
l
d.
(5)
It will calculate availabilitya
(
j
,
i
) for each neighbor I
V
j.
(6)
It will update with damping factor and store:a
j
,
i
=
1
-
λ
a
j
,
i
n
e
w
+
λ
a
j
,
i
o
l
d.
(7)
It will determine if itself is converged to CH: ifr
i
,
i
+
a
i
,
i
>
0, then set C
H
c
n
v
g
,
j.
(8)
It will broadcast Responsibility and Availability array,r
(
i
,
j
) and a
(
j
,
i
).
(9)
It will superviseI
V
k: I
V
i updates and calculates r
′
(
j
,
k
) and a
′
(
j
,
k
) for I
V
k.
(10)
I
V
i listens to I
V
k’s messages: r
(
k
,
j
) and a
(
j
,
k
); if r
(
k
,
j
)
-
r
′
(
k
,
j
)
>
T
h
r
e
s
h
o
l
d or a
(
k
,
j
)
-
a
′
(
k
,
j
)
>
T
h
r
e
s
h
o
l
d, then it will broadcastalert about I
V
k.T
m
e
s
s
a
g
e must be small enough to allow algorithm converged within a T
r
o
u
n
d. We have injected a supervision mechanism into clustering process. Any node that broadcasts false availability and responsibility would very likely be discovered. The punishment to malicious nodes is twofold: first, its message would be ignored by neighbors throughalert; second, a malicious behavior would be reported to CA.In anyr
o
u
n
d
r, there is a C
H
r
-
1 generated from r
o
u
n
d
r
-
1. C
H
r
-
1 will claim its role and broadcastFinal Message, which represents CH’s final evaluation to each cluster member V
I
i:(6)
F
i
n
a
l
M
e
s
s
a
g
e
=
U
n
t
r
u
s
t
D
e
g
r
e
e
C
H
r
-
1
,
i
.FinalMessage is trustworthy since it is sent from CH, which is elected as “the most trustworthy node” by all group members. Built uponFinalMessage, intracluster trust management is relatively reliable to support IVs’ collaborations.


## 3.1. UntrustDegree

Our proposed scheme uses the fundamental idea of Affinity Propagation from a trust perspective. In general, AP could detect anomaly vehicles in a group. We design anUntrustDegree function as “distance measurement” for AP algorithm to find “the most trustworthy node,” that is, to find the node which minimizes overall UntrustDegree. The function U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j is automatically calculated by IV. An IV can observe other vehicles’ behaviors and give an UntrustDegree according to its knowledge:(3)
U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
=
F
i
I
d
e
n
t
i
t
y
,
S
i
t
u
a
t
i
o
n
→
,
B
e
h
a
v
i
o
r
→
j
∈
0,1
.Identity is one item from set I
d
=
{
b
u
s
,
t
a
x
i
,
p
o
l
i
c
e
,
p
r
i
v
a
t
e
,
…
} denoting real identity of one car and could be represented by a unique digital number. S
i
t
u
a
t
i
o
n
→ is a vector predefined as some basic values which gives environmental context (e.g., the weather). B
e
h
a
v
i
o
r
j
→ is a vector recording basic actions that I
V
j has done recently. With the help of behavior detection technologies [20] or interactive gaming [21], we reasonably assume that IVs are intelligent enough to evaluate each other. The value, U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
∈
0,1, is primarily positive but set negative, namely, -
U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
∈
-
1,0, to fit AP algorithm.The self UntrustDegree,U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
i, is initialized to the same value. It should be noted that a higher self-trust degree makes it more likely to become the cluster head. In our final model (discussed in Section 5.2), valid self-trust is set at a value which balancesIV’s evaluation andhistorical reputation.Historical reputation can only be legally announced by CA. When a group of IVs pass by a RSU, RSU will proactively download/broadcast reputations to IVs.


## 3.2. Mutual Supervisor Model

EachI
V
i receives responsibility r
(
i
,
j
) from the neighborhood. Also, I
V
i broadcasts a
(
i
,
j
) to the neighborhood to claim how suitable it is to become a CH. However, a malicious/incapable node can cheat/mistake in this message passing process by broadcasting a false a
(
i
,
j
). For example, if I
V
i broadcasts very high a
(
i
,
j
) to other nodes, it is more likely to be elected CH according to the AP algorithm. We need a mechanism to prevent nodes broadcast false availability or responsibility.We proposed a supervisor model to alleviate cheating/mistaking in this process. The core of mutual supervisor model is to matchI
V
i with a supervisor I
V
j. Among moving companions of one vehicle, a supervisor is anotherIV which can receive almost the same broadcast information by sharing the same wireless channel. A supervisor therefore listens to the supervisee related message to validate availability/responsibility by repeating the calculation of suspicious I
V
i. The result calculated by I
V
i itself is R
e
s
u
l
t
i
i. The supervisor I
V
j’s calculation result for I
V
i is R
e
s
u
l
t
i
j. If the two results R
e
s
u
l
t
i
i and R
e
s
u
l
t
i
j have large difference, then this means I
V
i is very likely to have cheated in message passing process. The integral mechanism of supervisor model is illustrated in Figure 3.Figure 3
Mutual supervisor model.To assure a stable and honest supervisor, we apply Algorithm1. From this algorithm, we see that I
V
i has possibility to supervise another I
V
j only when (1) I
V
i does not tend to believe I
V
j and (2) I
V
i and I
V
j have small relative mobility. That is, they are stable driving companions. This mechanism builds up mutual supervision relationship between two adversary nodes so that supervisor and supervisee are not likely to collude. More important, it can identify cheating nodes in message passing process.Algorithm 1:Supervisor Matching algorithm.
Input: a supervisor I
V
i, nearby node’ states (position, speed)
Output: pair(supervisor, supervisee)
(1) ForNode  I
V
j  in DSRC(Dedicated Short Range Communication) range
(2)M
i
,
j
=
M
o
b
M
e
t
r
P
o
s
i
,
P
o
s
j
,
S
p
e
e
d
i
,
S
p
e
e
d
j //calculate mobility metric
(3) IfI
V
j  has no supervisor and U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
≤
T
h
r
e
s
h
o
l
d
(4)Then Add  I
V
j  in Supervisee Candidate List
(5) End For
(6) ForI
V
j  in Supervisee Candidate List
(7)  IfM
i
,
j
<
M
min
⁡ Then k
=
j   //find the most stable supervisee
(8) End For
(9) Returnmatched pair(I
V
i, I
V
k)     //i  supervises  kThe input of Algorithm1 is IV’s state tuples (position, speed). For I
V
i, running this algorithm will work out a supervisee. For each I
V
j in DSRC range, I
V
i calculates mobility metric M
i
,
j (lines (1)-(2)); the smaller the metric is, the more similar the two motions are. Thus, a small metric indicates a stable driving companion. If any I
V
j has no supervisor and U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
≤
T
h
r
e
s
h
o
l
d (this indicates that i does not tend to trust j), I
V
i adds I
V
j in Supervisee Candidate List (Line (3)-(4)). After that, I
V
i chooses the most stable candidate (with the smallest mobility metric) to be the supervisee (lines (6)–(8)). Finally, a pair (I
V
i
,
I
V
j) is returned (line (9)).


## 3.3. Generating CH by Message Passing

We try to use a distributed algorithm to reach a consensus among large amounts of opinions. EachI
V
i maintains a neighbor list N
i. As Table 1 shows, the list consists of N
i
j for each neighbor I
V
j. Additionally, I
V
i also maintains a supervision field for a supervisee I
V
k.Table 1
Neighbor and supervision field.
Neighbor field
Supervision field
(
x
,
y
)
j
Position ofI
V
j
a
′
(
k
,
j
)
I
V
k’s last availability received from I
V
j
(
v
x
,
v
y
)
j
Speed ofI
V
j
U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
UntrustDegree fromI
V
i to I
V
j
a
′
(
j
,
k
)
I
V
k’s last availability sent to I
V
j
a
(
i
,
j
)
Last availability received fromI
V
j
a
(
j
,
i
)
Last availability sent toI
V
j
r
′
(
k
,
j
)
I
V
k’s last responsibility received from I
V
j
r
(
i
,
j
)
Last responsibility received fromI
V
j
r
(
j
,
i
)
Last responsibility sent toI
V
j
r
′
(
j
,
k
)
I
V
k’s last responsibility sent to I
V
j
C
H
c
n
v
g
,
j
Cluster head converge flag forI
V
j
S
U
P
V
E
j
I
V
j’s superviseeGenerating CH needs several iterations which are periodically triggered by time. Besides, broadcasting and supervising also need a synchronous clock.Hello beacons are broadcast and received to maintain local awareness.Broadcast and Receive Hello Beacons Process is as follows:(1)
For everyT
h
e
l
l
o, each I
V
j broadcasthello beacon is(4)
j
,
x
,
y
j
,
v
x
,
v
y
j
,
C
H
j
,
S
U
P
V
E
j
.
(2)
Each receiving neighborI
V
i calculates U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j if they are traveling in the same direction.
(3)
I
V
i adds/updates N
i
j in its neighbor list:(5)
j
,
x
,
y
j
,
v
x
,
v
y
j
,
U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
j
,
C
H
j
,
S
U
P
V
E
j
.Availability and responsibility messages should be broadcast periodically. We define this period asT
m
e
s
s
a
g
e. Each I
V
i will calculate a
(
j
,
i
) and r
(
j
,
i
) for each neighbor I
V
j. This value is damped with the previous value stored in the neighbor list. I
V
j then broadcasts a
(
j
,
i
) and r
(
j
,
i
) of all neighbors I
V
j.According to mutual supervisor model, the process of calculatinga
(
j
,
i
) and r
(
j
,
i
) should be supervised. Each IV automatically chooses a supervisee bySupervisor Matching algorithm. Supervisor checks supervisee’s calculation result and releasesalert on condition that supervisee’s message is suspicious. The process enhanced by mutual supervisor model is illustrated below.Supervising and Message Passing Process. For every T
m
e
s
s
a
g
e, each I
V
i will do the following:(1)
It will find a matching superviseeI
V
k which is prepared for the next T
r
o
u
n
d’s iteration. If found in this T
m
e
s
s
a
g
e, it is claimed by S
U
P
V
E
j. If failed, it will try next T
m
e
s
s
a
g
e.
(2)
If it hears analert about I
V
n, each I
V
i will ignore I
V
n’s messages in this T
r
o
u
n
d.
(3)
It will calculate responsibilityr
(
i
,
j
) for each neighbor I
V
j.
(4)
It will update with damping factor and store:r
i
,
j
=
1
-
λ
r
i
,
j
n
e
w
+
λ
r
i
,
j
o
l
d.
(5)
It will calculate availabilitya
(
j
,
i
) for each neighbor I
V
j.
(6)
It will update with damping factor and store:a
j
,
i
=
1
-
λ
a
j
,
i
n
e
w
+
λ
a
j
,
i
o
l
d.
(7)
It will determine if itself is converged to CH: ifr
i
,
i
+
a
i
,
i
>
0, then set C
H
c
n
v
g
,
j.
(8)
It will broadcast Responsibility and Availability array,r
(
i
,
j
) and a
(
j
,
i
).
(9)
It will superviseI
V
k: I
V
i updates and calculates r
′
(
j
,
k
) and a
′
(
j
,
k
) for I
V
k.
(10)
I
V
i listens to I
V
k’s messages: r
(
k
,
j
) and a
(
j
,
k
); if r
(
k
,
j
)
-
r
′
(
k
,
j
)
>
T
h
r
e
s
h
o
l
d or a
(
k
,
j
)
-
a
′
(
k
,
j
)
>
T
h
r
e
s
h
o
l
d, then it will broadcastalert about I
V
k.T
m
e
s
s
a
g
e must be small enough to allow algorithm converged within a T
r
o
u
n
d. We have injected a supervision mechanism into clustering process. Any node that broadcasts false availability and responsibility would very likely be discovered. The punishment to malicious nodes is twofold: first, its message would be ignored by neighbors throughalert; second, a malicious behavior would be reported to CA.In anyr
o
u
n
d
r, there is a C
H
r
-
1 generated from r
o
u
n
d
r
-
1. C
H
r
-
1 will claim its role and broadcastFinal Message, which represents CH’s final evaluation to each cluster member V
I
i:(6)
F
i
n
a
l
M
e
s
s
a
g
e
=
U
n
t
r
u
s
t
D
e
g
r
e
e
C
H
r
-
1
,
i
.FinalMessage is trustworthy since it is sent from CH, which is elected as “the most trustworthy node” by all group members. Built uponFinalMessage, intracluster trust management is relatively reliable to support IVs’ collaborations.


## 4. Degrading Anomaly by Evidence Evaluation

Reputation-based method has been widely used in web service [22, 23] and cloud computing [24] to enhance system reliability and robustness. We believe this method could also improve system performance in Internet of Vehicles. In this scenario, IVs will observe and evaluate qualities of each other. Moreover, they formevidences and report them to CA. CA is supported by strong storage and computational resources, thus being capable of computing reputation from a global view. A global reputation is valuable for on-the-road IVs to choose potential collaborators. More importantly, reputation can be increased or degraded, as a system-level enforcement, to incent good behaviors as well as to punish bad ones.IVs leverage “store-upload” mechanism in delivering evidences to a CA. Since RSUs are sparsely deployed, each IV would store evidences in its storage firstly and then upload them when moving into a RSU’s service range. Evidence evaluation lies in the core of reputation. CA is able to make a conclusion on certain behavior by evaluating and merging different pieces of evidences from different individuals. Note that not all evidences are consistent, and not all evidences are trustworthy. For instance, in order to disturb reputation system, a malicious node may report false evidences.To mathematically model evidence evaluation, assume CA has to decide among several basic behaviorsβ
i
∈
Ω, based on K pieces of evidences {
e
k
j
} to I
V
j which are uploaded from different k IVs. Let B
j denote the final judgement on behavior type of I
V
j. The following three methods are leveraged to get a consensus evaluation, with the ability to filter false evidences.(A) Majority Voting. The final evaluation accords with the majority. Given counts of each type of observed behaviors, c
o
u
n
t
i, the behavior type of V
I
j is defined by(7)
B
j
=
β
a
r
g
m
a
x
c
o
u
n
t
i
.(B) Weighted Voting. For each behavior, this method sums up all the votes value supporting this behavior. The votes are weighed by corresponding trust level r
k
i. Then, the type with the highest value is final evaluation:(8)
B
j
=
β
a
r
g
m
a
x
1
/
c
o
u
n
t
i
∑
r
k
i
.(C) Bayesian Inference. Among the data fusion techniques, Bayesian Inference (BI) is the most popular one used for trust building and managing. To use BI, the a priori probability of each action β
i is firstly assigned. A posterior probability of each action β
i is calculated given a set of evidences e
=
{
e
1
j
,
e
2
j
,
e
3
j
,
…
,
e
k
j
} using Bayes’ theorem. For I
V
j,(9)
P
β
i
∣
e
=
P
β
i
×
∏
k
=
1
K
P
e
k
j
∣
β
i
∑
l
=
1
I
P
β
l
×
∏
k
=
1
K
P
e
k
j
∣
β
l
.Final consensus is the actions type with the maximum posterior probability:(10)
B
j
=
β
a
r
g
m
a
x
P
β
i
∣
e
.Besides evidence evaluation, reputation evolution rule is another critical issue. An effective reputation system requires appropriate reputation evolving rules. We will discuss rules in Section5.1.


## 5. Performance and Analysis

To evaluate performance of our scheme, we ran an extensive simulation in TransModeler with real map and high fidelity data. We use a map of urban area of San Antonio, USA. We feed real macroscopic traffic data, which are measured in critical roads and sections, to reconstruct real traffic scenario. We believe that macroscopic data could reflect traffic dynamic to a high extent. We do not simulate the wireless medium in this case since it is orthogonal to our evaluation. All simulations were performed with approximately 400 vehicles on a 6 miles’ expressway. Five RSUs are sparsely deployed along the expressway as Figure4. The DSRC range is set at 300 m. Each simulation ran for 600 s; however, only the last 400 s were used for performance metric calculations.Figure 4
RSUs’ deployment.As noted earlier, an IV will be observed and evaluated by neighbor IVs. We use the example with threeBasic Behaviors in Table 2. Each behavior causes different interactive trust. According to reputation evolution rules, one behavior deserves change in reputation.Table 2
Three basic behaviors.
β
i
Basic behavior type
UntrustDegree
Reputation change
Example
β
1
Life-critical events
0.9
Exponential degrade
2
7
128
→
2
6
64
β
2
Efficiency reduction events
0.5
Linear degrade
128
→
120
β
3
Normality
0.1
No change
128
→
128To depict complex malicious/inappropriate behaviors, which are often mixed with different basic behaviors, we simulate severalbehavior patterns in Table 3. An anomaly node produces one behavior in every T
r
o
u
n
d. These patterns are simplified to make simulation feasible. We believe they could still well-reflect validity of our designed scheme.Table 3
Five behavior patterns.
Scenario number
Anomaly nodes behavior pattern
β
1
β
2
β
3
1
100%
0
0
2
0
100%
0
3
50%
50%
0
4
30%
50%
20%
5
20%
30%
50%


### 5.1. The Effect of AP Algorithm

Ideally, AP clustering would generate a CH for every on-the-road vehicle. However, a small portion of vehicles,N
l
e
f
t, could be left alone when iterations are finished. There are two major reasons for these nodes: (
1
) the node could not find a converged CH candidate in its neighborhood and (
2
) the node itself is the CH but is the only member of cluster. Beside N
l
e
f
t, there are N
i
n nodes which form M normal clusters. In anomaly node-free simulation, several results are shown in Table 2.Covered ratio is a parameter describing how much the clustering results could cover the whole participants:(11)
C
o
v
e
r
R
a
t
i
o
=
N
i
n
N
i
n
+
N
l
e
f
t
.In anomaly simulation, several results are shown in Table3. The simulations are ran several times so Figures 5, 6, 7, and 8 are averaged. A trade-off betweenCovered Ratio andCluster Member Number could be found through Table 4. The higher theCovered Ratio, the lower theCluster Member Number.Table 4
The results of primary AP clustering.
Damping factor
Iteration cycle
DSRC range
Average cover-ratio
Average normal cluster number
Average member number
State
0.6
6
300 m
85.8%
26.5
13.2
Underdamping
0.7
5
300 m
38.9%
9.3
17.8
Underiteration
0.7
6
200 m
91.5%
46.7
8.5
Ok
0.7
6
300 m
94.3%
39.9
10.0
Ok
0.7
7
300 m
95.5%
85.5
4.8
Overiteration
0.8
6
300 m
74.3%
18.5
22.5
OverdampingFigure 5
Effects of three merging techniques.Figure 6
Reputation evolution of four anomaly nodes.Figure 7
Percentage-Failure Rate curve.Figure 8
Percentage-Risk Degree curve.According to reference [18],Damping Factor is critical for convergence. DifferentDamping Factors result in different cluster outcomes. In general, a biggerDamping Factor leads to a relatively higherCovered Ratio and a lowerCluster Member Number. We recommend to set λ
∈
0.6,0.8 so that algorithm tends to come out as an approximate but stable solution.Another important parameter not mentioned in [18] isIteration Cycle. Mathematically, the convergence of AP clustering is only influenced byDamping Factor, because the authors implicitly assume AP clustering could always have enough time for iteration. However, we have modified and applied this algorithm for anomaly detection where the communicating topology is constantly changing. Thus, the communication environment could not always provide plenty of time for clustering. SoIteration Cycle should be regarded as a critical parameter. If it is too short, clustering process will not be able to produce enough CHs to cover most nodes. On the other hand, if the cycle is too long, over-iteration will generate too many CHs. To conclude, modified AP clustering is oriented to real application other than a pure math problem and several parameters should be meticulously adjusted for real deployment, among which the most important ones areDamping Factor andIteration Cycle.We use two metrics to measure effectiveness of modified AP algorithm.(
1) Direct Influence. We define oneFailure as an anomaly node elected to be CH;Failure Rate is to measure direct influence of one anomaly node, also called unsuccessful anomaly detection rate:(12)
F
a
i
l
u
r
e
R
a
t
e
=
N
u
m
b
e
r
a
n
o
m
a
l
y
-
C
H
N
u
m
b
e
r
a
n
o
m
a
l
y
-
n
o
d
e
.(
2) Indirect Influence. We defineRisk Degree to feature how much potential influence an anomaly V
I
i has when it is in one cluster:(13)
R
i
s
k
D
e
g
r
e
e
=
1
-
U
n
t
r
u
s
t
D
e
g
r
e
e
C
H
,
i
×
N
u
m
b
e
r
c
l
u
s
t
e
r
m
e
m
b
e
r
s
.If an anomaly node becomes CH, UntrustDegree is 0; otherwise, UntrustDegree is referred to CH’sFinal Message, which expresses CH’s opinion of each node.Risk Degree could feature the indirect influence of an unqualified node according to its role (CH or member) and UntrustDegree. For example, if an unqualified is admitted into a 20-member cluster, and CH’s final message claims its UntrustDegree is 0.5, then itsRisk Degree is 10. If it is admitted into a 5-member cluster, Risk Degree is 2.5. The later risk is much smaller because the anomaly node has fewer potential partners and thus may have fewer threats.


### 5.2. Comparison of Four Models

Our performance evaluation is based on four models: Primary AP model (PAP), Tempering AP model (TAP), Tempering&Supervising AP model (TSAP), and Converged AP model (CAP). PAP is directly derived from AP clustering algorithm. TAP models the clustering scenario where anomaly nodes could temper/disturb message passing process. In short, TAP considers tempering/disturb behaviors over PAP. To alleviate influence of tempering/disturbing, TSAP model injectsMutual Supervision Model into PAP to identify anomaly nodes. Finally, CAP is a converged model which enhanced TSAP with historical reputation.As a converged model, CAP combines historical reputation with real-time cluster-based trust. CA collects uploaded evidences from on-road vehicles and uses three techniques to fuse evidences:(
1
) Majority Voting, (
2
) Weighted Voting, and (
3
) Bayesian Inference. For Bayesian Inference, the prior distribution of behaviors and observed results are defined in Table 5.Table 5
Prior distribution of behaviors and observed behaviors.
Observed
Behavior
β
1
β
2
β
3
β
1
0.7
0.15
0.1
β
2
0.2
0.7
0.1
β
3
0.1
0.15
0.8We assume that anomaly nodes use a random reporting strategy, which means they generate evidences randomly regardless of what other nodes really have done. Normal nodes will always report true evidences. Figure5 describes the effects of different evidence merging techniques. In this simulation, three techniques are almost equally effective. However, MV and WV are more suitable for data merging since they have less computation overhead. Figure 6 shows four anomaly nodes’ reputation evolves in system. Anomaly nodes would be distinguished and punished by CA.In a process of iteration, IVs with larger values of Self-UntrustDegree are more likely to be chosen as CH. These values are “preferences.” In PAP/TAP/TSAP,I
V
n preference is set as median of U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
n. However, in CAP where historical reputation is considered by algorithm, I
V
n’s preference is calculated by(14)
P
r
e
f
e
r
e
n
c
e
n
=
P
u
n
i
s
h
F
a
c
t
o
r
n
×
M
e
d
i
a
n
U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
n
.WhenI
V
n’s reputation is low, P
u
n
i
s
h
F
a
c
t
o
r
n
∈
1,2 is big; preference therefore becomes small (preference is a negative real number), indicating I
V
n is not suitable to be CH.Figure7 shows the comparison of four models. We set unqualified node percentage as variable. We simulate with different percentages ranges from [
0,0.25
] because too high percentage is not realistic.Generally, when anomaly nodes percentage is low (≤5%),Failure Rate is 0%. As percentage goes up,Failure Rate also goes higher. TAP is a model with tempering/disturbing and no supervision mechanism, so it performs worse than PAP (no tempering/disturbing) and TSAP (tempering/disturbing, supervision model). In contrast, CAP is a converged model (tempering/disturbing, supervision model, and reputation) with a strong defense to anomaly nodes, so it shows the highest robustness among four models. Furthermore, either model could limit failure rate below 1% even when anomaly nodes percentage is up to 25%.Risk Degree features how much potential influence an anomaly node has when it is in one cluster. Figure 8 shows theAnomaly Percentage-Risk Degree curve for four models. Risk Degree is firstly low whenAnomaly Node Percentage is low. However, it suddenly goes to peak whenPercentage slightly increases. Finally, it stably declines with increasingpercentage. The explanation for this curve is as follows: (
1
) whenPercentage is very low (≤1%), tempering/disturbing is few, and anomaly nodes therefore are easily distinguished by normal nodes. As a result, anomaly nodes are very likely to be left alone. That is, they are excluded from big clusters by AP algorithm. So the overallRisk Degree is low. (
2
) WhenPercentage goes higher but not that high (≤5%), this percentage still indicates a “safe environment”; IVs tend to form “big clusters.” However, with more anomaly nodes percentage, more anomaly nodes have chances to join big clusters by more tempering/disturbing. According to formula (13), even one anomaly node in a big cluster would cause a big risk degree. (
3
) WhenPercentage increases over 5%, our algorithms tend to be conservative and form “small clusters,” which have fewer cluster members. Fewer members render lowerRisk Degree. According to Figure 8, CAP could limit Risk Degree under 4, demonstrating that our trust management is effective on risk control.


## 5.1. The Effect of AP Algorithm

Ideally, AP clustering would generate a CH for every on-the-road vehicle. However, a small portion of vehicles,N
l
e
f
t, could be left alone when iterations are finished. There are two major reasons for these nodes: (
1
) the node could not find a converged CH candidate in its neighborhood and (
2
) the node itself is the CH but is the only member of cluster. Beside N
l
e
f
t, there are N
i
n nodes which form M normal clusters. In anomaly node-free simulation, several results are shown in Table 2.Covered ratio is a parameter describing how much the clustering results could cover the whole participants:(11)
C
o
v
e
r
R
a
t
i
o
=
N
i
n
N
i
n
+
N
l
e
f
t
.In anomaly simulation, several results are shown in Table3. The simulations are ran several times so Figures 5, 6, 7, and 8 are averaged. A trade-off betweenCovered Ratio andCluster Member Number could be found through Table 4. The higher theCovered Ratio, the lower theCluster Member Number.Table 4
The results of primary AP clustering.
Damping factor
Iteration cycle
DSRC range
Average cover-ratio
Average normal cluster number
Average member number
State
0.6
6
300 m
85.8%
26.5
13.2
Underdamping
0.7
5
300 m
38.9%
9.3
17.8
Underiteration
0.7
6
200 m
91.5%
46.7
8.5
Ok
0.7
6
300 m
94.3%
39.9
10.0
Ok
0.7
7
300 m
95.5%
85.5
4.8
Overiteration
0.8
6
300 m
74.3%
18.5
22.5
OverdampingFigure 5
Effects of three merging techniques.Figure 6
Reputation evolution of four anomaly nodes.Figure 7
Percentage-Failure Rate curve.Figure 8
Percentage-Risk Degree curve.According to reference [18],Damping Factor is critical for convergence. DifferentDamping Factors result in different cluster outcomes. In general, a biggerDamping Factor leads to a relatively higherCovered Ratio and a lowerCluster Member Number. We recommend to set λ
∈
0.6,0.8 so that algorithm tends to come out as an approximate but stable solution.Another important parameter not mentioned in [18] isIteration Cycle. Mathematically, the convergence of AP clustering is only influenced byDamping Factor, because the authors implicitly assume AP clustering could always have enough time for iteration. However, we have modified and applied this algorithm for anomaly detection where the communicating topology is constantly changing. Thus, the communication environment could not always provide plenty of time for clustering. SoIteration Cycle should be regarded as a critical parameter. If it is too short, clustering process will not be able to produce enough CHs to cover most nodes. On the other hand, if the cycle is too long, over-iteration will generate too many CHs. To conclude, modified AP clustering is oriented to real application other than a pure math problem and several parameters should be meticulously adjusted for real deployment, among which the most important ones areDamping Factor andIteration Cycle.We use two metrics to measure effectiveness of modified AP algorithm.(
1) Direct Influence. We define oneFailure as an anomaly node elected to be CH;Failure Rate is to measure direct influence of one anomaly node, also called unsuccessful anomaly detection rate:(12)
F
a
i
l
u
r
e
R
a
t
e
=
N
u
m
b
e
r
a
n
o
m
a
l
y
-
C
H
N
u
m
b
e
r
a
n
o
m
a
l
y
-
n
o
d
e
.(
2) Indirect Influence. We defineRisk Degree to feature how much potential influence an anomaly V
I
i has when it is in one cluster:(13)
R
i
s
k
D
e
g
r
e
e
=
1
-
U
n
t
r
u
s
t
D
e
g
r
e
e
C
H
,
i
×
N
u
m
b
e
r
c
l
u
s
t
e
r
m
e
m
b
e
r
s
.If an anomaly node becomes CH, UntrustDegree is 0; otherwise, UntrustDegree is referred to CH’sFinal Message, which expresses CH’s opinion of each node.Risk Degree could feature the indirect influence of an unqualified node according to its role (CH or member) and UntrustDegree. For example, if an unqualified is admitted into a 20-member cluster, and CH’s final message claims its UntrustDegree is 0.5, then itsRisk Degree is 10. If it is admitted into a 5-member cluster, Risk Degree is 2.5. The later risk is much smaller because the anomaly node has fewer potential partners and thus may have fewer threats.


## 5.2. Comparison of Four Models

Our performance evaluation is based on four models: Primary AP model (PAP), Tempering AP model (TAP), Tempering&Supervising AP model (TSAP), and Converged AP model (CAP). PAP is directly derived from AP clustering algorithm. TAP models the clustering scenario where anomaly nodes could temper/disturb message passing process. In short, TAP considers tempering/disturb behaviors over PAP. To alleviate influence of tempering/disturbing, TSAP model injectsMutual Supervision Model into PAP to identify anomaly nodes. Finally, CAP is a converged model which enhanced TSAP with historical reputation.As a converged model, CAP combines historical reputation with real-time cluster-based trust. CA collects uploaded evidences from on-road vehicles and uses three techniques to fuse evidences:(
1
) Majority Voting, (
2
) Weighted Voting, and (
3
) Bayesian Inference. For Bayesian Inference, the prior distribution of behaviors and observed results are defined in Table 5.Table 5
Prior distribution of behaviors and observed behaviors.
Observed
Behavior
β
1
β
2
β
3
β
1
0.7
0.15
0.1
β
2
0.2
0.7
0.1
β
3
0.1
0.15
0.8We assume that anomaly nodes use a random reporting strategy, which means they generate evidences randomly regardless of what other nodes really have done. Normal nodes will always report true evidences. Figure5 describes the effects of different evidence merging techniques. In this simulation, three techniques are almost equally effective. However, MV and WV are more suitable for data merging since they have less computation overhead. Figure 6 shows four anomaly nodes’ reputation evolves in system. Anomaly nodes would be distinguished and punished by CA.In a process of iteration, IVs with larger values of Self-UntrustDegree are more likely to be chosen as CH. These values are “preferences.” In PAP/TAP/TSAP,I
V
n preference is set as median of U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
n. However, in CAP where historical reputation is considered by algorithm, I
V
n’s preference is calculated by(14)
P
r
e
f
e
r
e
n
c
e
n
=
P
u
n
i
s
h
F
a
c
t
o
r
n
×
M
e
d
i
a
n
U
n
t
r
u
s
t
D
e
g
r
e
e
i
,
n
.WhenI
V
n’s reputation is low, P
u
n
i
s
h
F
a
c
t
o
r
n
∈
1,2 is big; preference therefore becomes small (preference is a negative real number), indicating I
V
n is not suitable to be CH.Figure7 shows the comparison of four models. We set unqualified node percentage as variable. We simulate with different percentages ranges from [
0,0.25
] because too high percentage is not realistic.Generally, when anomaly nodes percentage is low (≤5%),Failure Rate is 0%. As percentage goes up,Failure Rate also goes higher. TAP is a model with tempering/disturbing and no supervision mechanism, so it performs worse than PAP (no tempering/disturbing) and TSAP (tempering/disturbing, supervision model). In contrast, CAP is a converged model (tempering/disturbing, supervision model, and reputation) with a strong defense to anomaly nodes, so it shows the highest robustness among four models. Furthermore, either model could limit failure rate below 1% even when anomaly nodes percentage is up to 25%.Risk Degree features how much potential influence an anomaly node has when it is in one cluster. Figure 8 shows theAnomaly Percentage-Risk Degree curve for four models. Risk Degree is firstly low whenAnomaly Node Percentage is low. However, it suddenly goes to peak whenPercentage slightly increases. Finally, it stably declines with increasingpercentage. The explanation for this curve is as follows: (
1
) whenPercentage is very low (≤1%), tempering/disturbing is few, and anomaly nodes therefore are easily distinguished by normal nodes. As a result, anomaly nodes are very likely to be left alone. That is, they are excluded from big clusters by AP algorithm. So the overallRisk Degree is low. (
2
) WhenPercentage goes higher but not that high (≤5%), this percentage still indicates a “safe environment”; IVs tend to form “big clusters.” However, with more anomaly nodes percentage, more anomaly nodes have chances to join big clusters by more tempering/disturbing. According to formula (13), even one anomaly node in a big cluster would cause a big risk degree. (
3
) WhenPercentage increases over 5%, our algorithms tend to be conservative and form “small clusters,” which have fewer cluster members. Fewer members render lowerRisk Degree. According to Figure 8, CAP could limit Risk Degree under 4, demonstrating that our trust management is effective on risk control.


## 6. Conclusion and Future Work

Our system aims to build a trustworthy platform to detect abnormal vehicles. To this end, we modifiedAffinity Propagation to elect a most trustworthy node, called cluster head, among vehicles. CH maintains trust management during a period until a new CH is elected. We also considered that AP is executed in a distributed manner thus easily tempered by malicious nodes. So we presented a mutual supervision model to tackle tempering behaviors. Lastly, we blend another component, CA, into our system. CA consisted of servers and sparse RSUs and is able to provide historical reputation for better decision-making. Overall, this trust management system could detect and filter anomaly nodes.In the future, great efforts are needed on both the in-vehicular system and RSUs to strengthen our secure system. These efforts include deploying mobile and local CA using cloud computing techniques, improving intelligence of mutual trust evaluation, and reducing overhead of detection process.



---

*Source: 5254141-2016-03-24.xml*