On the Resilience of Trafﬁc Networks under Non-Equilibrium Learning Yunian Pan Tao Li and Quanyan Zhu Abstract We investigate the resilience of learning-based

2025-05-02 0 0 2.19MB 8 页 10玖币

侵权投诉

On the Resilience of Trafﬁc Networks under Non-Equilibrium Learning

Yunian Pan, Tao Li, and Quanyan Zhu∗

Abstract— We investigate the resilience of learning-based

Intelligent Navigation Systems (INS) to informational ﬂow at-

tacks, which exploit the vulnerabilities of IT infrastructure

and manipulate trafﬁc condition data. To this end, we propose

the notion of Wardrop Non-Equilibrium Solution (WANES),

which captures the ﬁnite-time behavior of dynamic trafﬁc

ﬂow adaptation under a learning process. The proposed non-

equilibrium solution, characterized by target sets and mea-

surement functions, evaluates the outcome of learning under

a bounded number of rounds of interactions, and it pertains

to and generalizes the concept of approximate equilibrium.

Leveraging ﬁnite-time analysis methods, we discover that under

the mirror descent (MD) online-learning framework, the trafﬁc

ﬂow trajectory is capable of restoring to the Wardrop non-

equilibrium solution after a bounded INS attack. The resulting

performance loss is of order ˜

O(Tβ)(−1

2≤β < 0)), with a

constant dependent on the size of the trafﬁc network, indicating

the resilience of the MD-based INS. We corroborate the results

using an evacuation case study on a Sioux-Fall transportation

network.

I. INTRODUCTION

The past decades have witnessed signiﬁcant growth in the

Internet-based trafﬁc routing demand, along with the rapid

development of modern Intelligent Navigation Systems (INS).

The INS infrastructures, which consists of Online Navigation

Platforms (ONP) such as Google Maps and Waze, together

with the widely adopted Internet-of-Things (IoT), including

smart road sensors and toll gates, are designed to make real-

time, efﬁcient routing recommendations for their users. The

best-effort routing of the individuals leads to macroscopic

trafﬁc conditions, which is encapsulated by the notion of

Wardrop equilibrium (WE) [1] in congestion games.

As transportation networks become increasingly inter-

connected, the number of attack vectors against the entire

transportation system is also on the rise. Consequently, the

well-being of the trafﬁc networks is vulnerable to emerging

cyber-physical threats. For example, attacks on individual

GPS devices and road sensors can lead to the unavailability

of critical information and cause wide disruptions to the

infrastructure. As discussed in [

], a strategic data poisoning

attack on the ONP can lead to signiﬁcant trafﬁc congestion

and service breakdown.

In this work, we focus on a class of man-in-the-middle

(MITM) attacks on ONP systems that aim to mislead the

users to choose routes that are favored by the attackers. A

quintessential case was demonstrated in 2014, Israel, where

two students hacked the Waze GPS app and used bots to

crowdsource false location information, which misled the

∗

The authors are with the Department of Electrical and Computer

Engineering, Tandon School of Engineering, New York University, Brooklyn,

NY, 11201 USA; E-mail: {yp1170,tl2636,qz494}@nyu.edu

Fig. 1. Intelligent Navigation Systems (INS) are vulnerable to informational

attacks when data transmission is intercepted, yielding deteriorated trafﬁc

ﬂows. Mirror descent, as a non-equilibrium learning scheme, is capable of

restoring the path ﬂow to the proposed Wardrop non-equilibrium solution.

users and caused congestion [

]. As reported in [

], the

existing real-time trafﬁc systems are intrinsically vulnerable

to malicious attacks such as modiﬁed cookie replays and

simulated delusional trafﬁc ﬂows.

This class of attacks can be further categorized as infor-

mational attacks on INS. They intercept the communication

channel between individual users and the information infras-

tructure and exploit the vulnerabilities of data transmission

to misguide users and achieve an adversarial trafﬁc condition.

While there have been efforts on preventing and detecting

attacks, it is indispensable to create resilient mechanisms that

can allow users to adapt and recover after the attack since

perfect protection is either cost-prohibitive or impractical

[

], [

]. To achieve this self-healing property, a dynamic

feedback-driven learning-based approach is essential [

], and

a non-equilibrium solution concept in contrast to the classical

Wardrop equilibrium is needed to capture the non-stationary

nature of the ante impetum and post impetum behaviors as

well as enable the time-critical performance assessment and

design for resiliency.

To this end, we investigate the notion of Non-Equilibrium

Solution (NonES) in the context of repeated congestion games.

It measures the probability of the trafﬁc ﬂows “enveloping”

given target sets, with the envelop volume deﬁned by a

measurement function. The Non-Equilibrium learning does not

necessarily yield an equilibrium solution but a trajectory that

falls into the envelope with high probability. Based on NonES,

we deﬁne Wardrop Non-Equilibrium Solution (WANES),

which speciﬁes mean Wardrop equilibrium (MWE) as its

arXiv:2210.03214v1 [eess.SY] 6 Oct 2022

target set, and the weighted potential loss as the measurement.

In this work, we focus on a class of Mirror Descent

Non-Equilibrium learning algorithms and elaborate on its

role in the resilience of trafﬁc networks under adversarial

environments. We ﬁrst establish a high probability bound

on the distance between the output and MWE for generic

Mirror Descent (MD) algorithms without assumptions on the

boundedness of the latency function. This high probability

bound can be transformed into the resilience metrics, showing

that after the attack, a WANES with weighted potential loss

that is sublinear in time can be recovered through learning.

Next, we develop a learning-based resiliency mechanism

based on an MD algorithm as the and two classes of

ﬂow disturbance attacks. We demonstrate the performance

resilience under MD using an evacuation case study to

illustrate the process of learning-based recovery. A schematic

illustration of our non-equilibrium learning approach is

provided in Figure 1.

Outline of this paper.

We brieﬂy discuss the related

works in Section II. In Section III, we introduce the repeated

stochastic congestion game and MWE as the solution concept,

based on which we introduce the notion of Non-Equilibrium

learning and the formalism of resilience. In Section IV, we

establish several ﬁnite-time results for the Non-Equilibrium

learning dynamics and elaborate on the numerical experiments

to illustrate the attack and resilience in Section V.

II. RELATED WORK

Our work bridges the gap between the online-learning and

resilience in trafﬁc assignment. Trafﬁc assignment naturally

ﬁts in the online-learning framework, see [

], [

], where

the convergence in Ces

aro sense is shown as interests. Vu

et al. in [

] improved the rate of Ces

aro convergence to

O(1/T 2)and provided a last-iterate convergence guarantee.

The existent studies on the resilience of trafﬁc assignment

have targeted on event-based disruptions, (see, e.g., [

]),

the system impedance to misinformation disturbance has

been rarely studied. To the best of our knowledge, the ﬁrst

informational equilibrium-poisoning concept was proposed by

Pan et al. [

], such a phenomenon occurs when the sensors,

GPS devices in the INS are under attacks [13].

III. PROBLEM FORMULATION

A. Preliminary: Mean Wardrop Equilirbium

We are given a trafﬁc network represented as a directed,

ﬁnite, and connected graph

G= (V,E)

without self-loops.

The vertices

represent road junctions, and the edges

represent road segments. The set of distinct origin-destination

(OD) pairs is

W ⊆ V ×V

, indexed by

, with cardinality

Let

P:= Sw∈W Pw

be the set of all directed paths between

origins and destinations, where

Pw⊆ P(E)

is the path set

between the pair w.

We assume that there is a set of inﬁnitesimal players

over

, denoted by a measurable space

(X,M, m)

. The

players are non-atomic, i.e.,

m(x) = 0 ∀x∈ X

; they

are split into distinct populations indexed by the OD pairs,

i.e.,

X=Sw∈W Xw

and

XwTXw0=∅,∀w, w0∈ W

For each OD pair

w∈ W

, let

mw=m(Xw)

represent

the trafﬁc demand. Let

M=Pw∈W mw

For each player

x∈ Xw

, we assume that their travel path

a∈ Pw

is ﬁxed

right after the path selection. The action proﬁle of all the

players

induces an edge ﬂow vector

q∈R|E|

≥0

, where

qe:= RX1{e∈a}m(dx), e ∈ E

, and a path ﬂow vector

µ∈∆ := {(µp)p∈∪w∈W Pw|µp:= RXw

1{a=p}m(dx)}.

We deﬁne the edge-path incident matrix of graph

Λ =

[Λ1|,...,|Λ|W|]∈R|E|×|P|

such that

Λw

e,p =1{e∈p},∀e∈

E, w ∈ W, p ∈ Pw

. Hence the compact form of edge-path

ﬂow relation is q= Λµ.

Let

(Ω,F,P)

be the probability space for the formalism,

le:R≥0×Ω7→ R+

be the cost/latency functions, measuring

the travel delay of the edge

e∈ E

determined by its edge ﬂow

and a state variable

ω∈Ω

that is universal for the entire

trafﬁc network, e.g.,

can represent the weather condition,

road incidents or anything that affects the congestion level. Let

l:R|E|

≥0×Ω7→ R|E|

denote the vector-valued latency function.

For an instance

ω∈Ω

, the latency of path

is deﬁned as

`p:= Pe∈ple(qe, ω)=Λ>

pl(Λµ, ω)

, which can be seen as

a function of

and

, written as

`p=`p(µ, ω)

. We write

the vector-valued path latency function as

`: ∆ ×Ω7→ R|P|

Each instance

determines a congestion game, captured by

the tuple

Gω

c= (G,W,X,P, `(·, ω))

. Each path ﬂow proﬁle

µ∈∆

induces a probability measure associated with the

positive random vector `(µ, ·):Ω7→ R|P|

Assumption 1.

For all

e∈ E

, the latency functions

are

-measurable, for all

ω∈Ω

are

-Lipschitz continuous

and differentiable in qewith ∂le(qe, ω)

∂qe

>0for all qe≥0.

Remark.

The continuity assumption reﬂects the fact that

adding a small amount of trafﬁc does not drastically affect

the travel latency; the monotonicity implies the increments

of trafﬁc does not decrease the latency.

We adopt a stochastic alternative deﬁnition of Wardrop

equilibrium. In doing so, we consider a “meta” version of the

congestion game,

Gc= (G,W,X,P,Eω[`(·, ω)])

, with the

utility functions replaced by the expected latency function.

This “meta” congestion game gives rise to a solution concept

corresponding to Deﬁnition 1.

Deﬁnition 1

(Mean Wardrop Equilibrium [

])

A path ﬂow

µ∈∆

is said to be a Mean Wardrop Equilibrium (MWE) if

∀w∈ W

µp>0

indicates

E[`p]≤E[`p0]

for all

p0∈ Pw

The set of all MWE is denoted by

µ∗

. Equivalently,

µ∈µ∗

if and only if the following variational inequality is satisﬁed:

Eω[hµ−µ0, `(µ, ω)i]≤0,∀µ0∈∆

, where

Eω[·]

is the

expectation operator with respect to ω.

The MWE

µ∗

is in general not a singleton, but a convex set

given the strict monotonicity of latency in Assumption 1. The

seeking of MWE can be cast as a minimization problem of

the expectation of the Stochastic Beckmann Potential (SBP)

[

], deﬁned as

φ(µ, ω) = Pe∈E R(Λµ)e

0le(z, ω)dz

, where

(Λµ)e

is the

th element of

Λµ

. We refer to the expectation

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OntheResilienceofTrafcNetworksunderNon-EquilibriumLearningYunianPan,TaoLi,andQuanyanZhuAbstractWeinvestigatetheresilienceoflearning-basedIntelligentNavigationSystems(INS)toinformationalowat-tacks,whichexploitthevulnerabilitiesofITinfrastructureandmanipulatetrafcconditiondata.Tothisend,wepropose...

展开>> 收起<<

On the Resilience of Trafﬁc Networks under Non-Equilibrium Learning Yunian Pan Tao Li and Quanyan Zhu Abstract We investigate the resilience of learning-based.pdf

共8页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

On the Resilience of Trafﬁc Networks under Non-Equilibrium Learning Yunian Pan Tao Li and Quanyan Zhu Abstract We investigate the resilience of learning-based

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: