text: QSSA AND NUMERICS FOR A VOLUME-SURFACE REACTION-DIFFUSION SYSTEM 25 The major aim of the paper is to provided the basic mathematical theory con- cerning such VSRD models: well-posedness, numerical discretisation and rigorous quasi-steady-state approximation with respect to a biologically large parameter. We expect that many of the results and methods of this paper can be carried over to similar VSRD models. In performing the QSSA, mathematical diﬃculty arises from the volume-surface coupling, in particular from the singularity occurring in the Neumann boundary condition of P. In the case without surface diﬀusion terms, we were able to prove in Section the necessary a-priori estimates and rigorously perform the QSSA to a reduced model system. For the full VSRD system (1.1)–(1.3), the weakly-reversible structure of (1.1)–(1.3) leads to technical diﬃculties in ﬁnding suitable a-priori estimates and thus prevents so far a rigorous proof of the QSSA. The VSRD model system (1.1)–(1.3) describes the asymmetric localisation of Lgl during mitosis, which subsequently leads to the asymmetric localisation of the cell-fate determinate Numb during the asymmetric stem cell division of Drosophila SOP precursor cells. Despite the lack of experimentally measured parameters, the numerical simulation of (1.1)–(1.3) allows nevertheless to study the qualitative behaviour of the model. Two such qualitative questions present themselves from the biological back- ground: First, the role of surface diﬀusion and secondly, the fact the p-Lgl release rate ξ is large. The ﬁrst point is related to the experimental observation of a cortical gap be- tween the Par complex, i.e. the active boundary part Γ and the resulting locali- 2 sation of the cell-fate determinants in neuroblasts cells, but not in SOP cells, see [29]. It has been suggested by the experimentalists, that surface diﬀusion may play a role in creating this spectral gap. The numerical simulation performed in Fig. 3a shows clearly that surface dif- fusion will spread out the l-Lgl proﬁle. This can suggest an explanation for the cortical gap in neuroblast cells, by assuming, for instance, that neuroblast cells need a higher l-Lgl concentration to localise Numb than SOP cells, where no spec- tral gap is observed. Moreover, larger surface diﬀusion rates would lead to further ﬂattened l-Lgl proﬁles and, thus, an even larger cortical gap. However, our simulations also present two counter-indications: Firstly, even without surface diﬀusion, the model will always feature an indirect surface dif- fusion eﬀect as a consequence of volume diﬀusion and reversible sorption of Lgl between cytoplasm and cortex, yet the magnitude of the indirect surface diﬀusion eﬀect will always be signiﬁcantly lower, see Section and Fig. 3. Nevertheless, the indirect surface diﬀusion eﬀect will increase if just one of the volume diﬀusion rates is increased, see Fig. 5 with tenfold increased d . L Secondly, Fig. 4 shows that surface diﬀusion together with the weakly-reversible structure of the model system (1.1)–(1.3) can lead to an unexpected maximum of L-Lgl in the cytoplasm, which seems biologically unlikely. As a summary, one could conjecture that while surface diﬀusion may play an important role in the asymmetric localisation of Lgl and in the subsequent asym- metric stem cell division, the magnitude of the surface diﬀusion can not be seen independently from the parameters of the weakly-reversible Lgl kinetics and the volume diﬀusion rates.

text: QSSA

text: AND

text: NUMERICS

text: FOR

text: A

text: VOLUME-SURFACE

text: REACTION-DIFFUSION

text: SYSTEM

text: The

text: major

text: aim

text: of

text: the

text: paper

text: is

text: to

text: provided

text: the

text: basic

text: mathematical

text: theory

text: con-

text: cerning

text: such

text: VSRD

text: models:

text: well-posedness,

text: numerical

text: discretisation

text: and

text: rigorous

text: quasi-steady-state

text: approximation

text: with

text: respect

text: to

text: a

text: biologically

text: large

text: parameter.

text: We

text: expect

text: that

text: many

text: of

text: the

text: results

text: and

text: methods

text: of

text: this

text: paper

text: can

text: be

text: carried

text: over

text: to

text: similar

text: VSRD

text: models.

text: In

text: performing

text: the

text: QSSA,

text: mathematical

text: diﬃculty

text: arises

text: from

text: the

text: volume-surface

text: coupling,

text: in

text: particular

text: from

text: the

text: singularity

text: occurring

text: in

text: the

text: Neumann

text: boundary

text: condition

text: of

text: P.

text: In

text: the

text: case

text: without

text: surface

text: diﬀusion

text: terms,

text: we

text: were

text: able

text: to

text: prove

text: in

text: Section

text: the

text: necessary

text: a-priori

text: estimates

text: and

text: rigorously

text: perform

text: the

text: QSSA

text: to

text: a

text: reduced

text: model

text: system.

text: For

text: the

text: full

text: VSRD

text: system

text: the

text: weakly-reversible

text: structure

text: of

text: leads

text: to

text: technical

text: diﬃculties

text: in

text: ﬁnding

text: suitable

text: a-priori

text: estimates

text: and

text: thus

text: prevents

text: so

text: far

text: a

text: rigorous

text: proof

text: of

text: the

text: QSSA.

text: The

text: VSRD

text: model

text: system

text: describes

text: the

text: asymmetric

text: localisation

text: of

text: Lgl

text: during

text: mitosis,

text: which

text: subsequently

text: leads

text: to

text: the

text: asymmetric

text: localisation

text: of

text: the

text: cell-fate

text: determinate

text: Numb

text: during

text: the

text: asymmetric

text: stem

text: cell

text: division

text: of

text: Drosophila

text: SOP

text: precursor

text: cells.

text: Despite

text: the

text: lack

text: of

text: experimentally

text: measured

text: parameters,

text: the

text: numerical

text: simulation

text: of

text: allows

text: nevertheless

text: to

text: study

text: the

text: qualitative

text: behaviour

text: of

text: the

text: model.

text: Two

text: such

text: qualitative

text: questions

text: present

text: themselves

text: from

text: the

text: biological

text: back-

text: ground:

text: First,

text: the

text: role

text: of

text: surface

text: diﬀusion

text: and

text: secondly,

text: the

text: fact

text: the

text: p-Lgl

text: release

text: rate

text: ξ

text: is

text: large.

text: The

text: ﬁrst

text: point

text: is

text: related

text: to

text: the

text: experimental

text: observation

text: of

text: a

text: cortical

text: gap

text: be-

text: tween

text: the

text: Par

text: complex,

text: i.e.

text: the

text: active

text: boundary

text: part

text: Γ

text: and

text: the

text: resulting

text: locali-

text: sation

text: of

text: the

text: cell-fate

text: determinants

text: in

text: neuroblasts

text: cells,

text: but

text: not

text: in

text: SOP

text: cells,

text: see

text: It

text: has

text: been

text: suggested

text: by

text: the

text: experimentalists,

text: that

text: surface

text: diﬀusion

text: may

text: play

text: a

text: role

text: in

text: creating

text: this

text: spectral

text: gap.

text: The

text: numerical

text: simulation

text: performed

text: in

text: Fig.

text: shows

text: clearly

text: that

text: surface

text: dif-

text: fusion

text: will

text: spread

text: out

text: the

text: l-Lgl

text: proﬁle.

text: This

text: can

text: suggest

text: an

text: explanation

text: for

text: the

text: cortical

text: gap

text: in

text: neuroblast

text: cells,

text: by

text: assuming,

text: for

text: instance,

text: that

text: neuroblast

text: cells

text: need

text: a

text: higher

text: l-Lgl

text: concentration

text: to

text: localise

text: Numb

text: than

text: SOP

text: cells,

text: where

text: no

text: spec-

text: tral

text: gap

text: is

text: observed.

text: Moreover,

text: larger

text: surface

text: diﬀusion

text: rates

text: would

text: lead

text: to

text: further

text: ﬂattened

text: l-Lgl

text: proﬁles

text: and,

text: thus,

text: an

text: even

text: larger

text: cortical

text: gap.

text: However,

text: our

text: simulations

text: also

text: present

text: two

text: counter-indications:

text: Firstly,

text: even

text: without

text: surface

text: diﬀusion,

text: the

text: model

text: will

text: always

text: feature

text: an

text: indirect

text: surface

text: dif-

text: fusion

text: eﬀect

text: as

text: a

text: consequence

text: of

text: volume

text: diﬀusion

text: and

text: reversible

text: sorption

text: of

text: Lgl

text: between

text: cytoplasm

text: and

text: cortex,

text: yet

text: the

text: magnitude

text: of

text: the

text: indirect

text: surface

text: diﬀusion

text: eﬀect

text: will

text: always

text: be

text: signiﬁcantly

text: lower,

text: see

text: Section

text: and

text: Fig.

text: Nevertheless,

text: the

text: indirect

text: surface

text: diﬀusion

text: eﬀect

text: will

text: increase

text: if

text: just

text: one

text: of

text: the

text: volume

text: diﬀusion

text: rates

text: is

text: increased,

text: see

text: Fig.

text: with

text: tenfold

text: increased

text: d

text: L

text: Secondly,

text: Fig.

text: shows

text: that

text: surface

text: diﬀusion

text: together

text: with

text: the

text: weakly-reversible

text: structure

text: of

text: the

text: model

text: system

text: can

text: lead

text: to

text: an

text: unexpected

text: maximum

text: of

text: L-Lgl

text: in

text: the

text: cytoplasm,

text: which

text: seems

text: biologically

text: unlikely.

text: As

text: a

text: summary,

text: one

text: could

text: conjecture

text: that

text: while

text: surface

text: diﬀusion

text: may

text: play

text: an

text: important

text: role

text: in

text: the

text: asymmetric

text: localisation

text: of

text: Lgl

text: and

text: in

text: the

text: subsequent

text: asym-

text: metric

text: stem

text: cell

text: division,

text: the

text: magnitude

text: of

text: the

text: surface

text: diﬀusion

text: can

text: not

text: be

text: seen

text: independently

text: from

text: the

text: parameters

text: of

text: the

text: weakly-reversible

text: Lgl

text: kinetics

text: and

text: the

text: volume

text: diﬀusion

text: rates.


text: 26 T.Q. BAO, K. FELLNER, S. ROSENBERGER Concerning the fast release of p-Lgl, Figs. 6 conﬁrms the natural intuition that larger ξ will lead to a faster release of cortical p-Lgl and the formation of an initial- boundary layer of P-Lgl, see Fig. 7. However, for the steady state of the system (1.1)–(1.3) and also for the reduced QSSA system (3.4)–(3.6), Fig. 8 shows that the steady state of these two weakly-reversible systems is independent of ξ in the case with zero surface diﬀusion, see Remark 3.1 (and also essentially independent of ξ in cases with suﬃciently small surface diﬀusion, data not shown). A biological interpretation of this observation has to recall that non-phosphorylated cortical Lgl, i.e. l-Lgl is active in the localisation of Pon and Numb. The concen- tration of l-Lgl, however, is not a direct results of the fast release of p-Lgl, but the consequence of the dynamics of the entire weakly-reversible system (1.1)–(1.3). For very large release rates ξ, it thus follows that the other reaction/sorption rates of (1.1)–(1.3) will be rate limiting in converging to a steady state and the overall process of asymmetric Lgl localisation will no further be speeded up. Nev- ertheless, for suﬃciently large ξ, the QSSA obtained in Section will certainly pro- vide a good approximation, which will even predict the identical stationary state compared to (1.1)–(1.3), see Remark 3.1. 6. Appendix Proof. The prove of the Lemma is based on a duality argument. We shall denote by ∗ ∈ ∞ × ∞ → | T : (Φ ) ≤ ≤ C (Ω) (C (Ω ))N (z(0), z, z ) i 0 i N 0 0 T ∂Ω ∗ the adjoint operator T of T, where z is the solution of (cid:40) (cid:80) − − − z d ∆z = Φ N ∂ Φ , t P 0 i=1 xi i (6.1) d ∂z/∂ν = 0, z(T) = 0. P By integration by parts: for Φ = (Φ ) ≤ ≤ i 1 i N (cid:90) (cid:90) (cid:90) (cid:104) ∗ (cid:105) (cid:104) | (cid:105) T (Φ , Φ), (w , Θ, g) = (z(0), z, z ), (w , Θ, g) 0 0 Γ 0 (cid:90) −(cid:90) = z(0)w + z(w d ∆w) + zg 0 t P Ω ΩT ΓT (cid:90) − − − ∇ · = w(z + d ∆z) = w( Φ + Φ) t P 0 ΩT ΩT ∇ (cid:104) ∇ (cid:105) = (Φ w + Φ w) = (Φ , Φ), (w , w) 0 0 0 (cid:104) ΩT (cid:105) = (Φ , Φ), T(w , Θ, g) . 0 0

label: paragraph

text: T.Q.

text: BAO,

text: K.

text: FELLNER,

text: S.

text: ROSENBERGER

text: Concerning

text: the

text: fast

text: release

text: of

text: p-Lgl,

text: Figs.

text: conﬁrms

text: the

text: natural

text: intuition

text: that

text: larger

text: ξ

text: will

text: lead

text: to

text: a

text: faster

text: release

text: of

text: cortical

text: p-Lgl

text: and

text: the

text: formation

text: of

text: an

text: initial-

text: boundary

text: layer

text: of

text: P-Lgl,

text: see

text: Fig.

text: However,

text: for

text: the

text: steady

text: state

text: of

text: the

text: system

text: and

text: also

text: for

text: the

text: reduced

text: QSSA

text: system

text: Fig.

text: shows

text: that

text: the

text: steady

text: state

text: of

text: these

text: two

text: weakly-reversible

text: systems

text: is

text: independent

text: of

text: ξ

text: in

text: the

text: case

text: with

text: zero

text: surface

text: diﬀusion,

text: see

text: Remark

text: (and

text: also

text: essentially

text: independent

text: of

text: ξ

text: in

text: cases

text: with

text: suﬃciently

text: small

text: surface

text: diﬀusion,

text: data

text: not

text: shown).

text: A

text: biological

text: interpretation

text: of

text: this

text: observation

text: has

text: to

text: recall

text: that

text: non-phosphorylated

text: cortical

text: Lgl,

text: i.e.

text: l-Lgl

text: is

text: active

text: in

text: the

text: localisation

text: of

text: Pon

text: and

text: Numb.

text: The

text: concen-

text: tration

text: of

text: l-Lgl,

text: however,

text: is

text: not

text: a

text: direct

text: results

text: of

text: the

text: fast

text: release

text: of

text: p-Lgl,

text: but

text: the

text: consequence

text: of

text: the

text: dynamics

text: of

text: the

text: entire

text: weakly-reversible

text: system

text: For

text: very

text: large

text: release

text: rates

text: ξ,

text: it

text: thus

text: follows

text: that

text: the

text: other

text: reaction/sorption

text: rates

text: of

text: will

text: be

text: rate

text: limiting

text: in

text: converging

text: to

text: a

text: steady

text: state

text: and

text: the

text: overall

text: process

text: of

text: asymmetric

text: Lgl

text: localisation

text: will

text: no

text: further

text: be

text: speeded

text: up.

text: Nev-

text: ertheless,

text: for

text: suﬃciently

text: large

text: ξ,

text: the

text: QSSA

text: obtained

text: in

text: Section

text: will

text: certainly

text: pro-

text: vide

text: a

text: good

text: approximation,

text: which

text: will

text: even

text: predict

text: the

text: identical

text: stationary

text: state

text: compared

text: to

text: see

text: Remark

text: Appendix

text: Proof.

text: The

text: prove

text: of

text: the

text: Lemma

text: is

text: based

text: on

text: a

text: duality

text: argument.

text: We

text: shall

text: denote

text: by

text: T

text: (Φ

text: C

text: (Ω)

text: (C

text: (Ω

text: ))N

text: z,

text: z

text: i

text: i

text: N

text: T

text: ∂Ω

text: the

text: adjoint

text: operator

text: T

text: of

text: T,

text: where

text: z

text: is

text: the

text: solution

text: of

text: z

text: d

text: ∆z

text: Φ

text: N

text: Φ

text: t

text: P

text: xi

text: i

text: d

text: ∂z/∂ν

text: z(T)

text: P

text: By

text: integration

text: by

text: parts:

text: for

text: Φ

text: (Φ

text: i

text: i

text: N

text: T

text: (Φ

text: Φ),

text: (w

text: Θ,

text: g)

text: z,

text: z

text: (w

text: Θ,

text: g)

text: Γ

text: z(w

text: d

text: ∆w)

text: zg

text: t

text: P

text: Ω

text: ΩT

text: ΓT

text: w(z

text: d

text: ∆z)

text: w(

text: Φ

text: Φ)

text: t

text: P

text: ΩT

text: ΩT

text: (Φ

text: w

text: Φ

text: w)

text: (Φ

text: Φ),

text: (w

text: w)

text: ΩT

text: (Φ

text: Φ),

text: T(w

text: Θ,

text: g)


text: HEEGAARD DIAGRAMS CORRESPONDING TO TURAEV SURFACES 3 Figure 2. Each crossing in a link diagram is labeled in one of two ways. The label tells one how to adjust the link after inserting a crossing ball. is a Heegaard diagram for S3, then the circles of α and β together generate H (Σ). The 1 Appendix provides an easy proof of this fact, using Seifert surfaces. ##LTFigure## ##LTLine## ##LTLine##

text: HEEGAARD

text: DIAGRAMS

text: CORRESPONDING

text: TO

text: TURAEV

text: SURFACES

text: Figure

text: Each

label: caption

text: crossing

text: in

text: a

text: link

text: diagram

text: is

text: labeled

text: in

text: one

text: of

text: two

text: ways.

text: The

text: label

text: tells

text: one

text: how

text: to

text: adjust

text: the

text: link

text: after

text: inserting

text: a

text: crossing

text: ball.

text: is

text: a

text: Heegaard

text: diagram

text: for

text: then

text: the

text: circles

text: of

text: α

text: and

text: β

text: together

text: generate

text: H

text: (Σ).

text: The

text: Appendix

text: provides

text: an

text: easy

text: proof

text: of

text: this

text: fact,

text: using

text: Seifert

text: surfaces.

text: ##LTFigure##

label: figure

font: default

text: ##LTLine##

text: ##LTLine##


text: entering path with the least metric as its survisor, Step 5. Compute the f-function values of the successors of and delete the remaining. Let c(s¯ ) be this least the top path in the Open Stack, and delete the top (cid:96) metric. path from the Open Stack. If the f-function value Step 3. If (cid:96) = 0, stop the algorithm; otherwise, go to Step 2. of any successor is equal to or greater than ρ, just delete it. In the second phase, the priority-ﬁrst search algorithm is Step 6. For all remaining successor paths that reach level operated on trellis T in the usual forward fashion (i.e., from − − n 1, set ρ to be the least path metric among them, level 0 to level∼nC 1); hence, the second phase always outputs and update x as the successor path corresponding to a codeword in . this least path metric and discard all the others. Now for each p(cid:0)ath w(cid:1)ith lab(cid:0)els x(cid:1)((cid:96)) on(cid:0)trelli(cid:1)s T, an evaluation Step 7. Insert the remaining successor paths (from Steps 5 function f associated with it is deﬁned as: and 6) into the Open Stack, and re-order the paths in the Open Stack according to ascending f-function f x = g x + h x , ((cid:96)) ((cid:96)) ((cid:96)) values. Go to Step 3. where the val(cid:40)ue of g-function is assigned according to: (cid:0) (cid:1) IV. OPTIMALITY OF THE PROPOSED ALGORITHM (cid:0) (cid:1) − This section proves the optimality of the proposed two- 0, (cid:96) = 1; phase decoding algorithm. We begin with two essential lem- g x = − ((cid:96)) g x − + M(x ), (cid:96) = 0, 1, . . . , n 1 mas required for the optimality proof. ((cid:96) 1) ((cid:96)) (3) Lemma 1: Let path x be an immediate successor of ((cid:96)+1) and the value of h-(cid:0)functi(cid:1)on is given by: path x((cid:96)) on trellis T. Denote the ending states of x((cid:96)+1) and x by s and s , respectively. Then, ((cid:96)) (cid:96)+1 (cid:96) h x = c (β(s )) . (4) β(s ) = β(s ) + x h¯ , ((cid:96)) (cid:96) (cid:96)+1 (cid:96) (cid:96)+1 (cid:96)+1 where h¯ is the ((cid:96) + 2)th column of parity-check matrix H (cid:96)+1 In (4), s(cid:96) is the ending state of the path with label x((cid:96)), . In other words, there exists a branch between β(s(cid:96)) and and β(s−(cid:96)) is the state s¯(cid:96) on super-trellis T that has the same β(s(cid:96)+1) with label x(cid:96)+1 over super-trellis T. ﬁrst (n k¯) components as s . Note that β(s ) exists and is Proof: Recall that (cid:96) (cid:96) well-deﬁned for every s on trellis T since the parity-check (cid:20) (cid:21) matrices of ∼C and ∼C(cid:0)satis(cid:96)fy(cid:1)(1). s(cid:96)+1 = s(cid:96) + x(cid:96)+1h(cid:96)+1 It can be veriﬁed that f(x(n−1)) = g(x(n−1)) since and h¯ β(s − ) = 0 and h x − = c(β(s − )) = 0. This implies h = (cid:96)+1 n 1 (n 1) n 1 (cid:96)+1 p that the path with the minimum f-function value on trellis T (cid:96)+1 is exactly the one with the minimum ML path metric. for some p according to (1). It is thus obvious that (cid:96)+1 Two storage spaces are necessary for the priority-ﬁrst search β(s ) = β(s ) + x h¯ over trellis T. The Open Stack records the paths visited thus (cid:96)+1 (cid:96)− (cid:96)+1 (cid:96)+1 far by the priority-ﬁrst search, while the Close Table keeps the since h¯(cid:96)+1 contains the ﬁrst (n k¯) components of h(cid:96)+1. (cid:0) (cid:1) (cid:0) (cid:1) starting and ending states and ending levels of the paths that Lemma 2: f is a non-decreasing function along any path on have ever been on top of the Open Stack. They are so named trellis T, i.e., ≤ because the paths in the Open Stack can be further extended f x f x , ((cid:96)) ((cid:96)+1) and hence remain open, but the paths with information in the where path x is an immediate successor of path x over Closed Table are closed for further extension. ((cid:96)+1) ((cid:96)) trellis T. We summarize the priority-ﬁrst search algorithm over trellis Proof: The fundamental attribute of the backward Viterbi T in the following. algorithm in the ﬁrst phase gives that c(β(s )) is the minimum (cid:104) (cid:105) (cid:96) Phase 2: The Priority-First Search Algorithm metric among all backward paths that end at state β(s ) at ∞ ∅ (cid:96) Step 1. Let ρ = , and assign x = . level (cid:96). By Lemma 1, we have: Step 2. Load into the Open Stack the path containing only ≤ − c(β(s )) c(β(s )) + M(x ), the initial state s− at level 1. (cid:96) (cid:96)+1 (cid:96)+1 1 Step 3. If the Open Stack is empty, output x as the ﬁnal ML where s(cid:96)+1 and s(cid:96) are respectively the states that paths x((cid:96)+1) decision, and stop the algorithm. and x (cid:0) end a(cid:1)t. Hence,(cid:0)we deri(cid:1)ve: (cid:0) (cid:1) ((cid:96)) Step 4. If the starting and ending states and ending level of (cid:0) (cid:1) the top path in the Open Stack have been recorded f x = g (cid:0)x (cid:1) + h x ((cid:96)+1) ((cid:96)+1) ((cid:96)+1) in the Close Table, discard the top path from the = g (cid:0)x (cid:1)+ M(x ) + c(β(s )) Open Stack, and go to Step 3; otherwise, record the ((cid:96)) (cid:96)+1 (cid:96)+1 ≥ starting and ending states and ending level of this g x((cid:96)) + c(β(s(cid:96))) top path in the Close Table. = f x . ((cid:96)) 3 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: entering

text: path

text: with

text: the

text: least

text: metric

text: as

text: its

text: survisor,

text: Step

text: Compute

text: the

text: f-function

text: values

text: of

text: the

text: successors

text: of

text: and

text: delete

text: the

text: remaining.

text: Let

text: c(s¯

text: be

text: this

text: least

text: the

text: top

text: path

text: in

text: the

text: Open

text: Stack,

text: and

text: delete

text: the

text: top

text: metric.

text: path

text: from

text: the

text: Open

text: Stack.

text: If

text: the

text: f-function

text: value

text: Step

text: If

text: stop

text: the

text: algorithm;

text: otherwise,

text: go

text: to

text: Step

text: of

text: any

text: successor

text: is

text: equal

text: to

text: or

text: greater

text: than

text: ρ,

text: just

text: delete

text: it.

text: In

text: the

text: second

text: phase,

text: the

text: priority-ﬁrst

text: search

text: algorithm

text: is

text: Step

text: For

text: all

text: remaining

text: successor

text: paths

text: that

text: reach

text: level

text: operated

text: on

text: trellis

text: T

text: in

text: the

text: usual

text: forward

text: fashion

text: (i.e.,

text: from

text: n

text: set

text: ρ

text: to

text: be

text: the

text: least

text: path

text: metric

text: among

text: them,

text: level

text: to

text: level∼nC

text: hence,

text: the

text: second

text: phase

text: always

text: outputs

text: and

text: update

text: x

text: as

text: the

text: successor

text: path

text: corresponding

text: to

text: a

text: codeword

text: in

text: this

text: least

text: path

text: metric

text: and

text: discard

text: all

text: the

text: others.

text: Now

text: for

text: each

text: T,

text: an

text: evaluation

text: Step

text: Insert

text: the

text: remaining

text: successor

text: paths

text: (from

text: Steps

text: function

text: f

text: associated

text: with

text: it

text: is

text: deﬁned

text: as:

text: and

text: into

text: the

text: Open

text: Stack,

text: and

text: re-order

text: the

text: paths

text: in

text: the

text: Open

text: Stack

text: according

text: to

text: ascending

text: f-function

text: f

text: x

text: g

text: x

text: h

text: x

text: values.

text: Go

text: to

text: Step

text: where

text: the

text: of

text: g-function

text: is

text: assigned

text: according

text: to:

text: IV.

text: OPTIMALITY

text: OF

text: THE

text: PROPOSED

text: ALGORITHM

text: This

text: section

text: proves

text: the

text: optimality

text: of

text: the

text: proposed

text: two-

text: phase

text: decoding

text: algorithm.

text: We

text: begin

text: with

text: two

text: essential

text: lem-

text: g

text: x

text: g

text: x

text: M(x

text: n

text: mas

text: required

text: for

text: the

text: optimality

text: proof.

text: Lemma

text: Let

text: path

text: x

text: be

text: an

text: immediate

text: successor

text: of

text: and

text: the

text: value

text: of

text: is

text: given

text: by:

text: path

text: on

text: trellis

text: T.

text: Denote

text: the

text: ending

text: states

text: of

text: and

text: x

text: by

text: s

text: and

text: s

text: respectively.

text: Then,

text: h

text: x

text: c

text: (β(s

text: β(s

text: β(s

text: x

text: h¯

text: where

text: h¯

text: is

text: the

text: column

text: of

text: parity-check

text: matrix

text: H

text: In

text: is

text: the

text: ending

text: state

text: of

text: the

text: path

text: with

text: label

text: In

text: other

text: words,

text: there

text: exists

text: a

text: branch

text: between

text: and

text: and

text: is

text: the

text: state

text: on

text: super-trellis

text: T

text: that

text: has

text: the

text: same

text: with

text: label

text: over

text: super-trellis

text: T.

text: ﬁrst

text: (n

text: k¯)

text: components

text: as

text: s

text: Note

text: that

text: β(s

text: exists

text: and

text: is

text: Proof:

text: Recall

text: that

text: well-deﬁned

text: for

text: every

text: s

text: on

text: trellis

text: T

text: since

text: the

text: parity-check

text: matrices

text: of

text: ∼C

text: and

text: It

text: can

text: be

text: veriﬁed

text: that

text: since

text: and

text: h¯

text: β(s

text: and

text: h

text: x

text: c(β(s

text: This

text: implies

text: h

text: n

text: (n

text: n

text: p

text: that

text: the

text: path

text: with

text: the

text: minimum

text: f-function

text: value

text: on

text: trellis

text: T

text: is

text: exactly

text: the

text: one

text: with

text: the

text: minimum

text: ML

text: path

text: metric.

text: for

text: some

text: p

text: according

text: to

text: It

text: is

text: thus

text: obvious

text: that

text: Two

text: storage

text: spaces

text: are

text: necessary

text: for

text: the

text: priority-ﬁrst

text: search

text: β(s

text: β(s

text: x

text: h¯

text: over

text: trellis

text: T.

text: The

text: Open

text: Stack

text: records

text: the

text: paths

text: visited

text: thus

text: far

text: by

text: the

text: priority-ﬁrst

text: search,

text: while

text: the

text: Close

text: Table

text: keeps

text: the

text: since

text: contains

text: the

text: ﬁrst

text: (n

text: k¯)

text: components

text: of

text: starting

text: and

text: ending

text: states

text: and

text: ending

text: levels

text: of

text: the

text: paths

text: that

text: Lemma

text: f

text: is

text: a

text: non-decreasing

text: function

text: along

text: any

text: path

text: on

text: have

text: ever

text: been

text: on

text: top

text: of

text: the

text: Open

text: Stack.

text: They

text: are

text: so

text: named

text: trellis

text: T,

text: i.e.,

text: because

text: the

text: paths

text: in

text: the

text: Open

text: Stack

text: can

text: be

text: further

text: extended

text: f

text: x

text: f

text: x

text: and

text: hence

text: remain

text: open,

text: but

text: the

text: paths

text: with

text: information

text: in

text: the

text: where

text: path

text: x

text: is

text: an

text: immediate

text: successor

text: of

text: path

text: x

text: over

text: Closed

text: Table

text: are

text: closed

text: for

text: further

text: extension.

text: trellis

text: T.

text: We

text: summarize

text: the

text: priority-ﬁrst

text: search

text: algorithm

text: over

text: trellis

text: Proof:

text: The

text: fundamental

text: attribute

text: of

text: the

text: backward

text: Viterbi

text: T

text: in

text: the

text: following.

text: algorithm

text: in

text: the

text: ﬁrst

text: phase

text: gives

text: that

text: c(β(s

text: is

text: the

text: minimum

text: Phase

text: The

text: Priority-First

text: Search

text: Algorithm

text: metric

text: among

text: all

text: backward

text: paths

text: that

text: end

text: at

text: state

text: β(s

text: at

text: Step

text: Let

text: ρ

text: and

text: assign

text: x

text: level

text: By

text: Lemma

text: we

text: have:

text: Step

text: Load

text: into

text: the

text: Open

text: Stack

text: the

text: path

text: containing

text: only

text: c(β(s

text: c(β(s

text: M(x

text: the

text: initial

text: state

text: s−

text: at

text: level

text: Step

text: If

text: the

text: Open

text: Stack

text: is

text: empty,

text: output

text: x

text: as

text: the

text: ﬁnal

text: ML

text: where

text: and

text: are

text: respectively

text: the

text: states

text: that

text: paths

text: decision,

text: and

text: stop

text: the

text: algorithm.

text: and

text: x

text: end

text: Step

text: If

text: the

text: starting

text: and

text: ending

text: states

text: and

text: ending

text: level

text: of

text: the

text: top

text: path

text: in

text: the

text: Open

text: Stack

text: have

text: been

text: recorded

text: f

text: x

text: g

text: h

text: x

text: in

text: the

text: Close

text: Table,

text: discard

text: the

text: top

text: path

text: from

text: the

text: g

text: M(x

text: c(β(s

text: Open

text: Stack,

text: and

text: go

text: to

text: Step

text: otherwise,

text: record

text: the

text: starting

text: and

text: ending

text: states

text: and

text: ending

text: level

text: of

text: this

text: g

text: top

text: path

text: in

text: the

text: Close

text: Table.

text: f

text: x

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: the received scalar r ; thus, the metric associated with a path j x can be equival(cid:0)ently(cid:1)sim(cid:88)pliﬁed to ((cid:96)) Based on these two lemmas, the next theorem proves the (cid:44) (cid:96) ⊕ | | optimality of the proposed two-phase algorithm. M x (y x ) r , ((cid:96)) (cid:40) j j j Theorem 1: In the second phase, the priority-ﬁrst search j=0 algorithm always output an ML path. where Proof: It sufﬁces to prove that if the Open Stack is empty, y (cid:44) 1, if rj < 0; the algorithm will output an ML path as claimed in Step 3. j 0, otherwise. This can be conﬁrmed by showing that Steps 4 and 5 never The decoding complexity in the ﬁrst phase is clearly deter- delete any ML path. mined by the number of bit metric computations performed. Suppose that in Step 4, the starting and ending states and We emphasize that the decoding complexity in the second ending level of the new top path x have been recorded in ((cid:96)) phase can also be regulated by the number of f-function eval- the Close Table at some previous time due to path xˆ . Since ((cid:96)) uations (equivalently, the number of bit metric computations path x must be an offspring of some path x that once ((cid:96)) (j) as indicated in (3)) during the priority-ﬁrst search. This is coexisted with path xˆ in the Open Stack at the time path (cid:0) (cid:1)((cid:96)) (cid:0) (cid:1) (cid:0) (cid:1) due to that the cost of searching and re-ordering of stack xˆ was on top of the Open Stack, where j < (cid:96), we have ((cid:96)) elements can be made a constant multiple of the computational ≥ ≥ complexity by adopting a priority-queue data structure in stack f x f x f xˆ . (5) ((cid:96)) (j) ((cid:96)) implementation [16]. One can even employ a hardware-based stack structure [17] and attain constant complexity in stack Notably, the ﬁrst inequality in (5) follows from Lemma 2, maintenance. Therefore, to use the number of overall metric and the second inequality in (5) is valid because the top path in computations as the key determinant of algorithmic complexity the Open Stack always carries the minimum f-function value for our proposed two-phase decoding algorithm is justiﬁed. among all coexisting paths. As a result, the offsprings of path We now turn to empirical examination of the average − x ending at level n 1 cannot yield smaller metrics than decoding complexity of the proposed tpMLSD algorithm. The ((cid:96)) (cid:80) (cid:0) (cid:1) those length-n offsprings of path xˆ , and hence deletion of linear block code considered is the rth order binary Reed- ((cid:96)) path x will not compromise the optimality of the decoding Muller code, RM(r, m), which is an (n, k) linear block code ((cid:96)) algorithm. with n = 2m and k = 1 + r m . It is known [18] i=1 i ≥ For Step 5, we argue that ρ is either a trivial upper bound of that RM(r + i, m) is a supercode of RM(r, m) for i 1. ∼C ∼C the ﬁnal ML path (cf. Step 1) or the metric of a valid path that In our simulations, is RM(2, 6) and is RM(4, 6); hence, − reaches level n 1 (cf. Step 6), so deletion of any successor n = 64, k = 22 and k¯ = 57. Under the same optimal ML paths whose f-function values are no less than ρ will never performance, we compare the proposed two-phase ML soft- eliminate any ML path. This completes the proof of optimality decision decoding (tpMLSD) algorithm with the recursive ML of the proposed algorithm. decoding (RMLD) algorithm [1] and the list ML decoding (LMLD) algorithm [14] in average decoding complexity, and V. EVALUATION OF COMPUTATIONAL EFFORTS summarize the results in Table I. In this section, we investigate by simulations the compu- Note that instead of listing the decoding complexity of the tational effort of the proposed decoding algorithm over the LMLD, lower bounds obtained from decoding its supercode additive white Gaussian noise (AWGN) channels. We assume counterpart using the marking algorithm are given [14]. Ap- that the codeword is antipodally modulated, and hence the parently, the real decoding complexity of the LMLD is higher received vector is given by than this lower bound. The table then shows that the LMLD √ − E is much more complex than the other two algorithms, and rj = ( 1)vj + λj, our two-phase decoding algorithm consumes only 1/13 of ≤ ≤ − E for 0 j n 1, where is the signal energy per channel the computational effort of the RMLD at SNRb = 4.5 dB, { } − bit, and λ n 1 are independent noise samples of a white in which circumstance the bit error rate (BER) is around j j=0 − Gaussian process with single-sided noise power per hertz N . 10 5. Further, when SNRb is reduced to 3 dB, the average 0 The signal-to-noise ratio (SNR) for the channel is therefore computational complexity of the proposed two-phase decoding given by SNR (cid:44) E/N . In order to account for the code scheme can still reach 1/8 of that of the RMLD. 0 redundancy for different code rates, we will use the SNR per VI. CONCLUSION (cid:18) (cid:19) information bit in the following discussion, which is deﬁned In this work, we proposed a two-phase scheme for ML soft- as E E decision decoding of linear block codes. This novel decoding n /k n SNRb = = . algorithm has two phases, where the backward Viterbi algo- N0 k N0 rithm is employed on a supercode of the linear block code It can be easily veriﬁed that for antipodal-input AWGN in the ﬁrst phase, while the priority-ﬁrst search algorithm is channels, the log-likelihood ratio φ is a ﬁxed multiple of performed on the trellis of the linear block code in the second j 4 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: the

text: received

text: scalar

text: r

text: thus,

text: the

text: metric

text: associated

text: with

text: a

text: path

text: j

text: x

text: can

text: be

text: to

text: Based

text: on

text: these

text: two

text: lemmas,

text: the

text: next

text: theorem

text: proves

text: the

text: optimality

text: of

text: the

text: proposed

text: two-phase

text: algorithm.

text: M

text: x

text: (y

text: x

text: r

text: j

text: j

text: j

text: Theorem

text: In

text: the

text: second

text: phase,

text: the

text: priority-ﬁrst

text: search

text: algorithm

text: always

text: output

text: an

text: ML

text: path.

text: where

text: Proof:

text: It

text: sufﬁces

text: to

text: prove

text: that

text: if

text: the

text: Open

text: Stack

text: is

text: empty,

text: y

text: if

text: rj

text: the

text: algorithm

text: will

text: output

text: an

text: ML

text: path

text: as

text: claimed

text: in

text: Step

text: j

text: otherwise.

text: This

text: can

text: be

text: conﬁrmed

text: by

text: showing

text: that

text: Steps

text: and

text: never

text: The

text: decoding

text: complexity

text: in

text: the

text: ﬁrst

text: phase

text: is

text: clearly

text: deter-

text: delete

text: any

text: ML

text: path.

text: mined

text: by

text: the

text: number

text: of

text: bit

text: metric

text: computations

text: performed.

text: Suppose

text: that

text: in

text: Step

text: the

text: starting

text: and

text: ending

text: states

text: and

text: We

text: emphasize

text: that

text: the

text: decoding

text: complexity

text: in

text: the

text: second

text: ending

text: level

text: of

text: the

text: new

text: top

text: path

text: x

text: have

text: been

text: recorded

text: in

text: phase

text: can

text: also

text: be

text: regulated

text: by

text: the

text: number

text: of

text: f-function

text: eval-

text: the

text: Close

text: Table

text: at

text: some

text: previous

text: time

text: due

text: to

text: path

text: xˆ

text: Since

text: uations

text: (equivalently,

text: the

text: number

text: of

text: bit

text: metric

text: computations

text: path

text: x

text: must

text: be

text: an

text: offspring

text: of

text: some

text: path

text: x

text: that

text: once

text: (j)

text: as

text: indicated

text: in

text: during

text: the

text: priority-ﬁrst

text: search.

text: This

text: is

text: coexisted

text: with

text: path

text: xˆ

text: in

text: the

text: Open

text: Stack

text: at

text: the

text: time

text: path

text: due

text: to

text: that

text: the

text: cost

text: of

text: searching

text: and

text: re-ordering

text: of

text: stack

text: xˆ

text: was

text: on

text: top

text: of

text: the

text: Open

text: Stack,

text: where

text: j

text: we

text: have

text: elements

text: can

text: be

text: made

text: a

text: constant

text: multiple

text: of

text: the

text: computational

text: complexity

text: by

text: adopting

text: a

text: priority-queue

text: data

text: structure

text: in

text: stack

text: f

text: x

text: f

text: x

text: f

text: xˆ

text: (j)

text: implementation

text: One

text: can

text: even

text: employ

text: a

text: hardware-based

text: stack

text: structure

text: and

text: attain

text: constant

text: complexity

text: in

text: stack

text: Notably,

text: the

text: ﬁrst

text: inequality

text: in

text: follows

text: from

text: Lemma

text: maintenance.

text: Therefore,

text: to

text: use

text: the

text: number

text: of

text: overall

text: metric

text: and

text: the

text: second

text: inequality

text: in

text: is

text: valid

text: because

text: the

text: top

text: path

text: in

text: computations

text: as

text: the

text: key

text: determinant

text: of

text: algorithmic

text: complexity

text: the

text: Open

text: Stack

text: always

text: carries

text: the

text: minimum

text: f-function

text: value

text: for

text: our

text: proposed

text: two-phase

text: decoding

text: algorithm

text: is

text: justiﬁed.

text: among

text: all

text: coexisting

text: paths.

text: As

text: a

text: result,

text: the

text: offsprings

text: of

text: path

text: We

text: now

text: turn

text: to

text: empirical

text: examination

text: of

text: the

text: average

text: x

text: ending

text: at

text: level

text: n

text: cannot

text: yield

text: smaller

text: metrics

text: than

text: decoding

text: complexity

text: of

text: the

text: proposed

text: tpMLSD

text: algorithm.

text: The

text: those

text: length-n

text: offsprings

text: of

text: path

text: xˆ

text: and

text: hence

text: deletion

text: of

text: linear

text: block

text: code

text: considered

text: is

text: the

text: rth

text: order

text: binary

text: Reed-

text: path

text: x

text: will

text: not

text: compromise

text: the

text: optimality

text: of

text: the

text: decoding

text: Muller

text: code,

text: RM(r,

text: m),

text: which

text: is

text: an

text: (n,

text: k)

text: linear

text: block

text: code

text: algorithm.

text: with

text: n

text: and

text: k

text: r

text: m

text: It

text: is

text: known

text: i

text: For

text: Step

text: we

text: argue

text: that

text: ρ

text: is

text: either

text: a

text: trivial

text: upper

text: bound

text: of

text: that

text: RM(r

text: i,

text: m)

text: is

text: a

text: supercode

text: of

text: RM(r,

text: m)

text: for

text: i

text: ∼C

text: ∼C

text: the

text: ﬁnal

text: ML

text: path

text: (cf.

text: Step

text: or

text: the

text: metric

text: of

text: a

text: valid

text: path

text: that

text: In

text: our

text: simulations,

text: is

text: and

text: is

text: hence,

text: reaches

text: level

text: n

text: (cf.

text: Step

text: so

text: deletion

text: of

text: any

text: successor

text: n

text: k

text: and

text: k¯

text: Under

text: the

text: same

text: optimal

text: ML

text: paths

text: whose

text: f-function

text: values

text: are

text: no

text: less

text: than

text: ρ

text: will

text: never

text: performance,

text: we

text: compare

text: the

text: proposed

text: two-phase

text: ML

text: soft-

text: eliminate

text: any

text: ML

text: path.

text: This

text: completes

text: the

text: proof

text: of

text: optimality

text: decision

text: decoding

text: (tpMLSD)

text: algorithm

text: with

text: the

text: recursive

text: ML

text: of

text: the

text: proposed

text: algorithm.

text: decoding

text: (RMLD)

text: algorithm

text: and

text: the

text: list

text: ML

text: decoding

text: (LMLD)

text: algorithm

text: in

text: average

text: decoding

text: complexity,

text: and

text: V.

text: EVALUATION

text: OF

text: COMPUTATIONAL

text: EFFORTS

text: summarize

text: the

text: results

text: in

text: Table

text: I.

text: In

text: this

text: section,

text: we

text: investigate

text: by

text: simulations

text: the

text: compu-

text: Note

text: that

text: instead

text: of

text: listing

text: the

text: decoding

text: complexity

text: of

text: the

text: tational

text: effort

text: of

text: the

text: proposed

text: decoding

text: algorithm

text: over

text: the

text: LMLD,

text: lower

text: bounds

text: obtained

text: from

text: decoding

text: its

text: supercode

text: additive

text: white

text: Gaussian

text: noise

text: (AWGN)

text: channels.

text: We

text: assume

text: counterpart

text: using

text: the

text: marking

text: algorithm

text: are

text: given

text: Ap-

text: that

text: the

text: codeword

text: is

text: antipodally

text: modulated,

text: and

text: hence

text: the

text: parently,

text: the

text: real

text: decoding

text: complexity

text: of

text: the

text: LMLD

text: is

text: higher

text: received

text: vector

text: is

text: given

text: by

text: than

text: this

text: lower

text: bound.

text: The

text: table

text: then

text: shows

text: that

text: the

text: LMLD

text: E

text: is

text: much

text: more

text: complex

text: than

text: the

text: other

text: two

text: algorithms,

text: and

text: rj

text: λj,

text: our

text: two-phase

text: decoding

text: algorithm

text: consumes

text: only

text: of

text: E

text: for

text: j

text: n

text: where

text: is

text: the

text: signal

text: energy

text: per

text: channel

text: the

text: computational

text: effort

text: of

text: the

text: RMLD

text: at

text: SNRb

text: dB,

text: bit,

text: and

text: λ

text: n

text: are

text: independent

text: noise

text: samples

text: of

text: a

text: white

text: in

text: which

text: circumstance

text: the

text: bit

text: error

text: rate

text: (BER)

text: is

text: around

text: j

text: Gaussian

text: process

text: with

text: single-sided

text: noise

text: power

text: per

text: hertz

text: N

text: Further,

text: when

text: SNRb

text: is

text: reduced

text: to

text: dB,

text: the

text: average

text: The

text: signal-to-noise

text: ratio

text: (SNR)

text: for

text: the

text: channel

text: is

text: therefore

text: computational

text: complexity

text: of

text: the

text: proposed

text: two-phase

text: decoding

text: given

text: by

text: SNR

text: E/N

text: In

text: order

text: to

text: account

text: for

text: the

text: code

text: scheme

text: can

text: still

text: reach

text: of

text: that

text: of

text: the

text: RMLD.

text: redundancy

text: for

text: different

text: code

text: rates,

text: we

text: will

text: use

text: the

text: SNR

text: per

text: VI.

text: CONCLUSION

text: information

text: bit

text: in

text: the

text: following

text: discussion,

text: which

text: is

text: deﬁned

text: In

text: this

text: work,

text: we

text: proposed

text: a

text: two-phase

text: scheme

text: for

text: ML

text: soft-

text: as

text: E

text: E

text: decision

text: decoding

text: of

text: linear

text: block

text: codes.

text: This

text: novel

text: decoding

text: n

text: /k

text: n

text: SNRb

text: algorithm

text: has

text: two

text: phases,

text: where

text: the

text: backward

text: Viterbi

text: algo-

text: k

text: rithm

text: is

text: employed

text: on

text: a

text: supercode

text: of

text: the

text: linear

text: block

text: code

text: It

text: can

text: be

text: easily

text: veriﬁed

text: that

text: for

text: antipodal-input

text: AWGN

text: in

text: the

text: ﬁrst

text: phase,

text: while

text: the

text: priority-ﬁrst

text: search

text: algorithm

text: is

text: channels,

text: the

text: log-likelihood

text: ratio

text: φ

text: is

text: a

text: ﬁxed

text: multiple

text: of

text: performed

text: on

text: the

text: trellis

text: of

text: the

text: linear

text: block

text: code

text: in

text: the

text: second

text: j

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 7 Road junction Onshore wind farm Offshore wind farm Fig. 3. Transferred energy and energy loss at different efﬁciencies. Fig. 2. Locations of road junctions, and onshore and offshore wind farms (adopted from Google Earth). TABLE I SPECIFICATIONS OF SOME POPULAR ELECTRIC CARS IN THE MARKET Model Range per Battery capacity Ref. charge (km) (kWh) Tesla Model S 373–484 85 [20], [36] Nissan Leaf 117 24 [19], [36] BMW i3 129–161 18.8 [17], [36] Tesla Roadster 356–394 53 [21], [36] Fig. 4. Transferred energy and energy loss in various periods of time. Toyota RAV4 EV 166 27.4 [22], [36] Honda Fit EV 132–212 20 [18], [36] packet size w of 0.1 kWh, efﬁciency rate z of 0.95, and time period T of 5 hours. Table I gives the speciﬁcations of nodes and 2470 arcs (a ’s). We adopt one set of real trafﬁc data i some popular EVs available in the market, showing that our acquired in June 2013 to specify the journey time, distance, energy packet size is rather conservative. In the following, we and vehicular ﬂow for each of the road segments (i.e., arcs). study the total transferred energy (reaching London from the We randomly create 4788 vehicular routes (r ’s) in the road i wind farms) and the corresponding energy loss by varying one network, each of which is composed of several connected road parameter in each case. Each data point is computed from the segments no longer than 200 km. The trafﬁc ﬂow and total right-hand side of either (3) or (4), in which, for simplicity, journey time of each r are set with the minimum of vehicular i only some paths are considered instead of all possible energy ﬂows of the corresponding composite a ’s and the sum of i paths. individual journey times of the composite a ’s, respectively. i Fig. 3 shows the impact of total transferred energy and U.K. is the sixth largest nations producing wind energy, with × energy loss by changing z from the nominal setting. In ﬁve an annual energy production of more than 26 106 MWh [32], hours, the amounts of energy transferred are in the order of but only 26% was brought online in 2013 [33]. According to MWh. Note that the allowed period has already included the [34] and [35], there are 203 onshore and 20 offshore wind time required for the EVs to move from one place to another. farms. Fig. 2 shows the locations of the road junctions and The more efﬁcient the wireless energy transfer technology, the wind farms. We select 67 nodes in the the road network, the more energy can be transferred with smaller energy loss. which are close to the wind farms, as the energy sources (s’s) When z is smaller than 0.83,6 the amount of energy loss in VEN. We select one junction near London as the energy can overshoot the transferred energy. Hence z is an important destination t for demonstrative purpose. Energy paths pj(s, t)’s factor when we design VEN. However, if there is no VEN or are constructed by augmenting sub-routes of the 4788 ri’s. other similar energy transmission architecture available, the Energy is transmitted from the sources to the destination along huge amount of renewable energy may need to be stored at some of the energy paths. the original generation locations and eventually wasted due Consider the nominal setting of 0.1% EV penetration rate,4 5The industry expects the efﬁciency of wireless energy transfer on moving vehicles can exceed 90% [37]. NASA has developed a prototype called 4The EV penetration rate refers to the percentage of participating EVs in EVWireless with over 90% energy efﬁciency [38]. the vehicle population. When the EV penetration rate is 0.1%, one out of 6This threshold actually depends on the energy paths chosen for energy 1000 cars supports VEN. transmission. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Road

text: junction

text: Onshore

text: wind

text: farm

text: Offshore

text: wind

text: farm

text: Fig.

text: Transferred

text: energy

text: and

text: energy

text: loss

text: at

text: different

text: efﬁciencies.

text: Fig.

text: Locations

text: of

text: road

text: junctions,

text: and

text: onshore

text: and

text: offshore

text: wind

text: farms

text: (adopted

text: from

text: Google

text: Earth).

text: TABLE

text: I

text: SPECIFICATIONS

text: OF

text: SOME

text: POPULAR

text: ELECTRIC

text: CARS

text: IN

text: THE

text: MARKET

text: Model

label: table

text: Range

text: per

text: Battery

text: capacity

text: Ref.

text: charge

text: (km)

text: (kWh)

text: Tesla

text: Model

text: S

text: Nissan

text: Leaf

text: BMW

text: Tesla

text: Roadster

text: Fig.

text: Transferred

text: energy

text: and

text: energy

text: loss

text: in

text: various

text: periods

text: of

text: time.

text: Toyota

text: EV

text: Honda

text: Fit

text: EV

text: packet

text: size

text: w

text: of

text: kWh,

text: efﬁciency

text: rate

text: z

text: of

text: and

text: time

text: period

text: T

text: of

text: hours.

text: Table

text: I

text: gives

text: the

text: speciﬁcations

text: of

text: nodes

text: and

text: arcs

text: (a

text: ’s).

text: We

text: adopt

text: one

text: set

text: of

text: real

text: trafﬁc

text: data

text: i

text: some

text: popular

text: EVs

text: available

text: in

text: the

text: market,

text: showing

text: that

text: our

text: acquired

text: in

text: June

text: to

text: specify

text: the

text: journey

text: time,

text: distance,

text: energy

text: packet

text: size

text: is

text: rather

text: conservative.

text: In

text: the

text: following,

text: we

text: and

text: vehicular

text: ﬂow

text: for

text: each

text: of

text: the

text: road

text: segments

text: (i.e.,

text: arcs).

text: study

text: the

text: total

text: transferred

text: energy

text: (reaching

text: London

text: from

text: the

text: We

text: randomly

text: create

text: vehicular

text: routes

text: (r

text: ’s)

text: in

text: the

text: road

text: i

text: wind

text: farms)

text: and

text: the

text: corresponding

text: energy

text: loss

text: by

text: varying

text: one

text: network,

text: each

text: of

text: which

text: is

text: composed

text: of

text: several

text: connected

text: road

text: parameter

text: in

text: each

text: case.

text: Each

text: data

text: point

text: is

text: computed

text: from

text: the

text: segments

text: no

text: longer

text: than

text: km.

text: The

text: trafﬁc

text: ﬂow

text: and

text: total

text: right-hand

text: side

text: of

text: either

text: or

text: in

text: which,

text: for

text: simplicity,

text: journey

text: time

text: of

text: each

text: r

text: are

text: set

text: with

text: the

text: minimum

text: of

text: vehicular

text: i

text: only

text: some

text: paths

text: are

text: considered

text: instead

text: of

text: all

text: possible

text: energy

text: ﬂows

text: of

text: the

text: corresponding

text: composite

text: a

text: ’s

text: and

text: the

text: sum

text: of

text: i

text: paths.

text: individual

text: journey

text: times

text: of

text: the

text: composite

text: a

text: ’s,

text: respectively.

text: i

text: Fig.

text: shows

text: the

text: impact

text: of

text: total

text: transferred

text: energy

text: and

text: U.K.

text: is

text: the

text: sixth

text: largest

text: nations

text: producing

text: wind

text: energy,

text: with

text: energy

text: loss

text: by

text: changing

text: z

text: from

text: the

text: nominal

text: setting.

text: In

text: ﬁve

text: an

text: annual

text: energy

text: production

text: of

text: more

text: than

text: MWh

text: hours,

text: the

text: amounts

text: of

text: energy

text: transferred

text: are

text: in

text: the

text: order

text: of

text: but

text: only

text: was

text: brought

text: online

text: in

text: According

text: to

text: MWh.

text: Note

text: that

text: the

text: allowed

text: period

text: has

text: already

text: included

text: the

text: and

text: there

text: are

text: onshore

text: and

text: offshore

text: wind

text: time

text: required

text: for

text: the

text: EVs

text: to

text: move

text: from

text: one

text: place

text: to

text: another.

text: farms.

text: Fig.

text: shows

text: the

text: locations

text: of

text: the

text: road

text: junctions

text: and

text: The

text: more

text: efﬁcient

text: the

text: wireless

text: energy

text: transfer

text: technology,

text: the

text: wind

text: farms.

text: We

text: select

text: nodes

text: in

text: the

text: the

text: road

text: network,

text: the

text: more

text: energy

text: can

text: be

text: transferred

text: with

text: smaller

text: energy

text: loss.

text: which

text: are

text: close

text: to

text: the

text: wind

text: farms,

text: as

text: the

text: energy

text: sources

text: (s’s)

text: When

text: z

text: is

text: smaller

text: than

text: the

text: amount

text: of

text: energy

text: loss

text: in

text: VEN.

text: We

text: select

text: one

text: junction

text: near

text: London

text: as

text: the

text: energy

text: can

text: overshoot

text: the

text: transferred

text: energy.

text: Hence

text: z

text: is

text: an

text: important

text: destination

text: t

text: for

text: demonstrative

text: purpose.

text: Energy

text: paths

text: pj(s,

text: t)’s

text: factor

text: when

text: we

text: design

text: VEN.

text: However,

text: if

text: there

text: is

text: no

text: VEN

text: or

text: are

text: constructed

text: by

text: augmenting

text: sub-routes

text: of

text: the

text: ri’s.

text: other

text: similar

text: energy

text: transmission

text: architecture

text: available,

text: the

text: Energy

text: is

text: transmitted

text: from

text: the

text: sources

text: to

text: the

text: destination

text: along

text: huge

text: amount

text: of

text: renewable

text: energy

text: may

text: need

text: to

text: be

text: stored

text: at

text: some

text: of

text: the

text: energy

text: paths.

text: the

text: original

text: generation

text: locations

text: and

text: eventually

text: wasted

text: due

text: Consider

text: the

text: nominal

text: setting

text: of

text: EV

text: penetration

text: industry

text: expects

text: the

text: efﬁciency

text: of

text: wireless

text: energy

text: transfer

text: on

text: moving

text: vehicles

text: can

text: exceed

text: NASA

text: has

text: developed

text: a

text: prototype

text: called

text: EV

text: penetration

text: rate

text: refers

text: to

text: the

text: percentage

text: of

text: participating

text: EVs

text: in

text: EVWireless

text: with

text: over

text: energy

text: efﬁciency

text: the

text: vehicle

text: population.

text: When

text: the

text: EV

text: penetration

text: rate

text: is

text: one

text: out

text: of

text: threshold

text: actually

text: depends

text: on

text: the

text: energy

text: paths

text: chosen

text: for

text: energy

text: cars

text: supports

text: VEN.

text: transmission.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 8 complement the power network and enhance the overall power transmission rate. VI. POTENTIAL EXTENSIONS In this paper, we introduce VEN and show its capability. Below we give some potential extensions of VEN worth further investigations. In our setting of the model, we have assumed that each G node in is equipped with a small energy storage. With enhanced storage, nodes can act as big energy reservoirs. We may accumulate energy at some nodes, and we can make the energy transfer rate larger when there are more EVs passing Fig. 5. Transferred energy and energy loss with various buffer sizes. through (especially when the trafﬁc conditions are changing). This allows us to have better control of the whole energy transfer process. With the energy packet-switching design, VEN shares many similarities with the packet-switched data communication net- work, and thus, many ideas and techniques originally designed for the data network may be applied to VEN. In most cases, there exist multiple energy sources and destinations. The matching between the sources and destinations and the connections between them need to be carefully designed. Depending on VANET and other system settings, we may possess different information of the intended routes of the participating EVs. The levels of details of the vehicular routing information affect the number of charging-discharging cycles Fig. 6. Transferred energy and energy loss with different EV penetration required. For example, we can rely on vehicles without routing rates. information to transport for one hop only.7 We can make use of those EVs with a longer known route to carry energy further to surplus renewable production. As technology of wireless away. The levels of details of predictable vehicular routes energy transfer keeps advancing, the overall efﬁciency will impact the system performance. improve. Fig. 4 studies the impact of the allowed time period. ≤ With T 1 hour, the transferred energy is very small as most of the EVs carrying the energy have not reached the VII. CONCLUSION destination. With larger T, more transferred energy and energy The smart grid introduces many new elements which are loss occur. The gap between transferred energy and energy not easily incorporated into the existing power system due to loss grows with T showing that the energy transfer is more power reliability and security reasons. Many novel and inter- efﬁcient in a longer time period. Fig. 5 illustrates the impact esting smart grid implementations rely on the power network of the packet size. More energy will reach the destination and to convey power and they can be more easily realized if there more energy is also lost when a larger amount of energy can be exists an independent infrastructure for power transmission (dis)charged each time. A larger packet size leads to a higher without interference to the existing power network. In this efﬁciency as more energy can be transmitted than lost. Finally, paper, we introduce VEN, which is capable of transporting Fig. 6 shows that the transferred energy and energy loss grow energy across a large geographical area with EVs. VEN linearly with the EV penetration rate. is built upon the trafﬁc network and it relies on existing To summarize, we set up a VEN to transport renewable well-developed technologies. Small amounts of energy, as energy from remote wind farms to London. Note that the total energy packets, are carried by EVs through multiple vehicular transferable energy and loss shown above are not optimal, as routes. By carefully designing the energy packet routing, we we have just selected some of the energy paths to transport can transport energy from energy sources to destinations. In the energy. In fact, there may be shorter paths experiencing this paper, we give a thorough preliminary study of VEN fewer charging-discharging cycles. Nevertheless, the amount and discuss its characteristics and possible drawbacks. We of energy transferable through VEN in our illustration is still demonstrate its signiﬁcance by setting up a VEN with real road very signiﬁcant. Although there is energy loss in VEN, most trafﬁc data in the U.K. and show that a considerable amount of the energy to be transported in VEN would be eventually lost in the case without VEN. This shows that VEN can 7A vehicle which has gone onto a road segment must exit that segment. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: complement

text: the

text: power

text: network

text: and

text: enhance

text: the

text: overall

text: power

text: transmission

text: rate.

text: VI.

label: section

text: POTENTIAL

text: EXTENSIONS

text: In

text: this

text: paper,

text: we

text: introduce

text: VEN

text: and

text: show

text: its

text: capability.

text: Below

text: we

text: give

text: some

text: potential

text: extensions

text: of

text: VEN

text: worth

text: further

text: investigations.

text: In

text: our

text: setting

text: of

text: the

text: model,

text: we

text: have

text: assumed

text: that

text: each

text: G

text: node

text: in

text: is

text: equipped

text: with

text: a

text: small

text: energy

text: storage.

text: With

text: enhanced

text: storage,

text: nodes

text: can

text: act

text: as

text: big

text: energy

text: reservoirs.

text: We

text: may

text: accumulate

text: energy

text: at

text: some

text: nodes,

text: and

text: we

text: can

text: make

text: the

text: energy

text: transfer

text: rate

text: larger

text: when

text: there

text: are

text: more

text: EVs

text: passing

text: Fig.

text: Transferred

text: energy

text: and

text: energy

text: loss

text: with

text: various

text: buffer

text: sizes.

text: through

text: (especially

text: when

text: the

text: trafﬁc

text: conditions

text: are

text: changing).

text: This

text: allows

text: us

text: to

text: have

text: better

text: control

text: of

text: the

text: whole

text: energy

text: transfer

text: process.

text: With

text: the

text: energy

text: packet-switching

text: design,

text: VEN

text: shares

text: many

text: similarities

text: with

text: the

text: packet-switched

text: data

text: communication

text: net-

text: work,

text: and

text: thus,

text: many

text: ideas

text: and

text: techniques

text: originally

text: designed

text: for

text: the

text: data

text: network

text: may

text: be

text: applied

text: to

text: VEN.

text: In

text: most

text: cases,

text: there

text: exist

text: multiple

text: energy

text: sources

text: and

text: destinations.

text: The

text: matching

text: between

text: the

text: sources

text: and

text: destinations

text: and

text: the

text: connections

text: between

text: them

text: need

text: to

text: be

text: carefully

text: designed.

text: Depending

text: on

text: VANET

text: and

text: other

text: system

text: settings,

text: we

text: may

text: possess

text: different

text: information

text: of

text: the

text: intended

text: routes

text: of

text: the

text: participating

text: EVs.

text: The

text: levels

text: of

text: details

text: of

text: the

text: vehicular

text: routing

text: information

text: affect

text: the

text: number

text: of

text: charging-discharging

text: cycles

text: Fig.

text: Transferred

text: energy

text: and

text: energy

text: loss

text: with

text: different

text: EV

text: penetration

text: required.

text: For

text: example,

text: we

text: can

text: rely

text: on

text: vehicles

text: without

text: routing

text: rates.

text: information

text: to

text: transport

text: for

text: one

text: hop

text: We

text: can

text: make

text: use

text: of

text: those

text: EVs

text: with

text: a

text: longer

text: known

text: route

text: to

text: carry

text: energy

text: further

text: to

text: surplus

text: renewable

text: production.

text: As

text: technology

text: of

text: wireless

text: away.

text: The

text: levels

text: of

text: details

text: of

text: predictable

text: vehicular

text: routes

text: energy

text: transfer

text: keeps

text: advancing,

text: the

text: overall

text: efﬁciency

text: will

text: impact

text: the

text: system

text: performance.

text: improve.

text: Fig.

text: studies

text: the

text: impact

text: of

text: the

text: allowed

text: time

text: period.

text: With

text: T

text: hour,

text: the

text: transferred

text: energy

text: is

text: very

text: small

text: as

text: most

text: of

text: the

text: EVs

text: carrying

text: the

text: energy

text: have

text: not

text: reached

text: the

text: VII.

text: CONCLUSION

text: destination.

text: With

text: larger

text: T,

text: more

text: transferred

text: energy

text: and

text: energy

text: The

text: smart

text: grid

text: introduces

text: many

text: new

text: elements

text: which

text: are

text: loss

text: occur.

text: The

text: gap

text: between

text: transferred

text: energy

text: and

text: energy

text: not

text: easily

text: incorporated

text: into

text: the

text: existing

text: power

text: system

text: due

text: to

text: loss

text: grows

text: with

text: T

text: showing

text: that

text: the

text: energy

text: transfer

text: is

text: more

text: power

text: reliability

text: and

text: security

text: reasons.

text: Many

text: novel

text: and

text: inter-

text: efﬁcient

text: in

text: a

text: longer

text: time

text: period.

text: Fig.

text: illustrates

text: the

text: impact

text: esting

text: smart

text: grid

text: implementations

text: rely

text: on

text: the

text: power

text: network

text: of

text: the

text: packet

text: size.

text: More

text: energy

text: will

text: reach

text: the

text: destination

text: and

text: to

text: convey

text: power

text: and

text: they

text: can

text: be

text: more

text: easily

text: realized

text: if

text: there

text: more

text: energy

text: is

text: also

text: lost

text: when

text: a

text: larger

text: amount

text: of

text: energy

text: can

text: be

text: exists

text: an

text: independent

text: infrastructure

text: for

text: power

text: transmission

text: (dis)charged

text: each

text: time.

text: A

text: larger

text: packet

text: size

text: leads

text: to

text: a

text: higher

text: without

text: interference

text: to

text: the

text: existing

text: power

text: network.

text: In

text: this

text: efﬁciency

text: as

text: more

text: energy

text: can

text: be

text: transmitted

text: than

text: lost.

text: Finally,

text: paper,

text: we

text: introduce

text: VEN,

text: which

text: is

text: capable

text: of

text: transporting

text: Fig.

text: shows

text: that

text: the

text: transferred

text: energy

text: and

text: energy

text: loss

text: grow

text: energy

text: across

text: a

text: large

text: geographical

text: area

text: with

text: EVs.

text: VEN

text: linearly

text: with

text: the

text: EV

text: penetration

text: rate.

text: is

text: built

text: upon

text: the

text: trafﬁc

text: network

text: and

text: it

text: relies

text: on

text: existing

text: To

text: summarize,

text: we

text: set

text: up

text: a

text: VEN

text: to

text: transport

text: renewable

text: well-developed

text: technologies.

text: Small

text: amounts

text: of

text: energy,

text: as

text: energy

text: from

text: remote

text: wind

text: farms

text: to

text: London.

text: Note

text: that

text: the

text: total

text: energy

text: packets,

text: are

text: carried

text: by

text: EVs

text: through

text: multiple

text: vehicular

text: transferable

text: energy

text: and

text: loss

text: shown

text: above

text: are

text: not

text: optimal,

text: as

text: routes.

text: By

text: carefully

text: designing

text: the

text: energy

text: packet

text: routing,

text: we

text: we

text: have

text: just

text: selected

text: some

text: of

text: the

text: energy

text: paths

text: to

text: transport

text: can

text: transport

text: energy

text: from

text: energy

text: sources

text: to

text: destinations.

text: In

text: the

text: energy.

text: In

text: fact,

text: there

text: may

text: be

text: shorter

text: paths

text: experiencing

text: this

text: paper,

text: we

text: give

text: a

text: thorough

text: preliminary

text: study

text: of

text: VEN

text: fewer

text: charging-discharging

text: cycles.

text: Nevertheless,

text: the

text: amount

text: and

text: discuss

text: its

text: characteristics

text: and

text: possible

text: drawbacks.

text: We

text: of

text: energy

text: transferable

text: through

text: VEN

text: in

text: our

text: illustration

text: is

text: still

text: demonstrate

text: its

text: signiﬁcance

text: by

text: setting

text: up

text: a

text: VEN

text: with

text: real

text: road

text: very

text: signiﬁcant.

text: Although

text: there

text: is

text: energy

text: loss

text: in

text: VEN,

text: most

text: trafﬁc

text: data

text: in

text: the

text: U.K.

text: and

text: show

text: that

text: a

text: considerable

text: amount

text: of

text: the

text: energy

text: to

text: be

text: transported

text: in

text: VEN

text: would

text: be

text: eventually

text: lost

text: in

text: the

text: case

text: without

text: VEN.

text: This

text: shows

text: that

text: VEN

text: can

text: vehicle

text: which

text: has

text: gone

text: onto

text: a

text: road

text: segment

text: must

text: exit

text: that

text: segment.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: 11 V. SUMMARY AND DISCUSSION rather than just enhanced density ﬂuctuations, remain somewhat unclear; in particular steric or other interac- (cid:39) tions at volume fractions above Ψ 0.15 (with HIs) or In this study, we have numerically investigated the ef- (cid:39) Ψ 0.2 (without) apparently suppress phase separation fects of HIs on the collective dynamics of active suspen- under conditions where the observed dependence of the sions, modeling each micro-organism as a stroke-averaged mean swim speed v on Ψ might lead one to expect it dumbbell swimmer with a prescribed force dipole (and an s [4, 12, 13]. Such corrections to the theory have also been overlap rule). Our results can be summarized as follows. reported for spherical self-propelled particles [19], but not With HIs, when the separation distance between the at such low densities. swimmers is comparable to their sizes, their swimming motions are strongly inﬂuenced by one another. The In considering the eﬀects of HIs on collective dynamics, activity-induced ﬂow ﬁeld creates both attractive and re- we note in addition important diﬀerences between alter- pulsive eﬀects that depend on the relative positions and native types of models. In a recent simulation of two- orientations of the swimmers. These eﬀects are signiﬁ- dimensional squirming disks [22], it was found that the cantly more complex than could be expected for simpler activity-induced phase separation is strongly suppressed models of spherical particles (such as squirmers) in which by HIs. In that system, because the slip velocity is pre- the nonhydrodynamic forces between particles are spher- scribed at their surfaces, when two squirmers come very ically symmetric. Although in the far ﬁeld swimming close, they generally tend to strongly rotate and repel. dumbbells attract, at intermediate separations the HI- Thus, crowding enhances the reorientation of the swim- induced torques tend to disalign the swimming directions mers and reduces their tendency to trap one another. causing swimmers to move apart. Then, at closer dis- In contrast, in our model of force-prescribed dumbbells, tances, these repulsive eﬀects are suppressed; hydrody- although the reorientation is enhanced at low enough namic forces promote preferred structures, in which the volume fractions, at higher ones both the translational swimmers are close to parallel alignment (or, with our and rotational motions become much slower than without overlap rule, antiparallel). These states can last much HIs. Moreover, at a certain intermediate volume fraction, longer than the intrinsic characteristic time for an en- the hydrodynamic trapping eﬀect (and indeed the clus- counter, τ = (cid:96) /v . Our simulation results strongly sug- tering) is most pronounced. Further simulation studies a 0 0 gest that such activity-induced HIs should be signiﬁcant and analysis will be required to clarify the detailed con- ∼ at rather smaller volume fraction (Ψ 5%), where they ditions for phase separation with and without HIs in our cause strong enhancement of a clustering tendency that dumbbell model. is already apparent, albeit in a weaker form and by a In previous works by Graham and co-workers [23– diﬀerent mechanism, when HIs are absent. 25], it was found that, in suspensions of force-prescribed Our simulation results for the density dependence dumbbell pushers, HIs among them cause coherent ﬂuid of motility parameters show distinctly diﬀerent behav- motions with a correlation length larger than the swim- iors with and without HIs. At a relatively small vol- mer size. Interestingly, such correlated motions are ume fraction, with HIs, the translational swimming mo- hardly seen in suspensions of pullers. Saintillan and tion becomes slower, while rotational diﬀusion becomes Shelley [41–43] reported similar results by simulating a faster; these are natural consequences of the far-ﬁeld and similar model, where the active particle is modeled as intermediate-range pair interactions just described, and a stress-prescribed rigid rod. Furthermore, they also are stronger than the corresponding eﬀects without HIs. found that an isotropic or aligned homogeneous state On the other hand, at large enough volume fractions, the becomes unstable due to HIs and some non-linear hy- translational and rotational motions are both strongly drodynamic eﬀects lead to steady-state structure with suppressed. With crowding, because less space is avail- a pronounced density inhomogeneity and local orienta- able around a swimmer, the ability of each force dipole tional order of swimmers [61]. Although these previous to set up a coherent propulsive ﬂow ﬁeld is diminished, studies do not contradict our simulations, we found that, weakening both the motility and the HIs. However, due at certain intermediate densities, the clustering caused by to the incompressible nature of HIs, neighboring swim- activity-induced attractions (or hydrodynamic trapping) mers push and pull each other around even without di- is greater than previously reported, which, as already dis- rect contact. This impedes both the translational and cussed, can be attributed to the eﬀects of near-ﬁeld HIs. rotational motions much more than is the case without The advantage of the hybrid simulation methods such HIs, where only direct collisional forces act between the as that used in the present study is that, by directly swimmers. taking the solvent dynamics into account, we can accu- The diﬀerent volume fraction dependences of the motil- rately treat HIs among ﬁnite-sized particles at moderate ity with and without HIs inﬂuence the tendency to form separations, and also capture some signiﬁcant near-ﬁeld clusters. For our chosen interaction and propulsion pa- eﬀects. In the previous studies, on the other hand, ac- rameters, clustering is maximal at an intermediate vol- tive particles are essentially represented as pairs of point ume fraction in each case, but this volume fraction is forces and HIs are simply evaluated by using the usual lower, and clustering stronger, with HIs than without. Stokeslet. However, such an approach based on far-ﬁeld The conditions under which bulk phase separation arises, hydrodynamics is not able to fully capture the collective

text: V.

text: SUMMARY

text: AND

text: DISCUSSION

text: rather

text: than

text: just

text: enhanced

text: density

text: ﬂuctuations,

text: remain

text: somewhat

text: unclear;

text: in

text: particular

text: steric

text: or

text: other

text: interac-

text: tions

text: at

text: volume

text: fractions

text: above

text: Ψ

text: (with

text: HIs)

text: or

text: In

text: this

text: study,

text: we

text: have

text: numerically

text: investigated

text: the

text: ef-

text: Ψ

text: (without)

text: apparently

text: suppress

text: phase

text: separation

text: fects

text: of

text: HIs

text: on

text: the

text: collective

text: dynamics

text: of

text: active

text: suspen-

text: under

text: conditions

text: where

text: the

text: observed

text: dependence

text: of

text: the

text: sions,

text: modeling

text: each

text: micro-organism

text: as

text: a

text: stroke-averaged

text: mean

text: swim

text: speed

text: v

text: on

text: Ψ

text: might

text: lead

text: one

text: to

text: expect

text: it

text: dumbbell

text: swimmer

text: with

text: a

text: prescribed

text: force

text: dipole

text: (and

text: an

text: s

text: Such

text: corrections

text: to

text: the

text: theory

text: have

text: also

text: been

text: overlap

text: rule).

text: Our

text: results

text: can

text: be

text: summarized

text: as

text: follows.

text: reported

text: for

text: spherical

text: self-propelled

text: particles

text: but

text: not

text: With

text: HIs,

text: when

text: the

text: separation

text: distance

text: between

text: the

text: at

text: such

text: low

text: densities.

text: swimmers

text: is

text: comparable

text: to

text: their

text: sizes,

text: their

text: swimming

text: motions

text: are

text: strongly

text: inﬂuenced

text: by

text: one

text: another.

text: The

text: In

text: considering

text: the

text: eﬀects

text: of

text: HIs

text: on

text: collective

text: dynamics,

text: activity-induced

text: ﬂow

text: ﬁeld

text: creates

text: both

text: attractive

text: and

text: re-

text: we

text: note

text: in

text: addition

text: important

text: diﬀerences

text: between

text: alter-

text: pulsive

text: eﬀects

text: that

text: depend

text: on

text: the

text: relative

text: positions

text: and

text: native

text: types

text: of

text: models.

text: In

text: a

text: recent

text: simulation

text: of

text: two-

text: orientations

text: of

text: the

text: swimmers.

text: These

text: eﬀects

text: are

text: signiﬁ-

text: dimensional

text: squirming

text: disks

text: it

text: was

text: found

text: that

text: the

text: cantly

text: more

text: complex

text: than

text: could

text: be

text: expected

text: for

text: simpler

text: activity-induced

text: phase

text: separation

text: is

text: strongly

text: suppressed

text: models

text: of

text: spherical

text: particles

text: (such

text: as

text: squirmers)

text: in

text: which

text: by

text: HIs.

text: In

text: that

text: system,

text: because

text: the

text: slip

text: velocity

text: is

text: pre-

text: the

text: nonhydrodynamic

text: forces

text: between

text: particles

text: are

text: spher-

text: scribed

text: at

text: their

text: surfaces,

text: when

text: two

text: squirmers

text: come

text: very

text: ically

text: symmetric.

text: Although

text: in

text: the

text: far

text: ﬁeld

text: swimming

text: close,

text: they

text: generally

text: tend

text: to

text: strongly

text: rotate

text: and

text: repel.

text: dumbbells

text: attract,

text: at

text: intermediate

text: separations

text: the

text: HI-

text: Thus,

text: crowding

text: enhances

text: the

text: reorientation

text: of

text: the

text: swim-

text: induced

text: torques

text: tend

text: to

text: disalign

text: the

text: swimming

text: directions

text: mers

text: and

text: reduces

text: their

text: tendency

text: to

text: trap

text: one

text: another.

text: causing

text: swimmers

text: to

text: move

text: apart.

text: Then,

text: at

text: closer

text: dis-

text: In

text: contrast,

text: in

text: our

text: model

text: of

text: force-prescribed

text: dumbbells,

text: tances,

text: these

text: repulsive

text: eﬀects

text: are

text: suppressed;

text: hydrody-

text: although

text: the

text: reorientation

text: is

text: enhanced

text: at

text: low

text: enough

text: namic

text: forces

text: promote

text: preferred

text: structures,

text: in

text: which

text: the

text: volume

text: fractions,

text: at

text: higher

text: ones

text: both

text: the

text: translational

text: swimmers

text: are

text: close

text: to

text: parallel

text: alignment

text: (or,

text: with

text: our

text: and

text: rotational

text: motions

text: become

text: much

text: slower

text: than

text: without

text: overlap

text: rule,

text: antiparallel).

text: These

text: states

text: can

text: last

text: much

text: HIs.

text: Moreover,

text: at

text: a

text: certain

text: intermediate

text: volume

text: fraction,

text: longer

text: than

text: the

text: intrinsic

text: characteristic

text: time

text: for

text: an

text: en-

text: the

text: hydrodynamic

text: trapping

text: eﬀect

text: (and

text: indeed

text: the

text: clus-

text: counter,

text: τ

text: /v

text: Our

text: simulation

text: results

text: strongly

text: sug-

text: tering)

text: is

text: most

text: pronounced.

text: Further

text: simulation

text: studies

text: a

text: gest

text: that

text: such

text: activity-induced

text: HIs

text: should

text: be

text: signiﬁcant

text: and

text: analysis

text: will

text: be

text: required

text: to

text: clarify

text: the

text: detailed

text: con-

text: at

text: rather

text: smaller

text: volume

text: fraction

text: (Ψ

text: where

text: they

text: ditions

text: for

text: phase

text: separation

text: with

text: and

text: without

text: HIs

text: in

text: our

text: cause

text: strong

text: enhancement

text: of

text: a

text: clustering

text: tendency

text: that

text: dumbbell

text: model.

text: is

text: already

text: apparent,

text: albeit

text: in

text: a

text: weaker

text: form

text: and

text: by

text: a

text: In

text: previous

text: works

text: by

text: Graham

text: and

text: co-workers

text: diﬀerent

text: mechanism,

text: when

text: HIs

text: are

text: absent.

text: it

text: was

text: found

text: that,

text: in

text: suspensions

text: of

text: force-prescribed

text: Our

text: simulation

text: results

text: for

text: the

text: density

text: dependence

text: dumbbell

text: pushers,

text: HIs

text: among

text: them

text: cause

text: coherent

text: ﬂuid

text: of

text: motility

text: parameters

text: show

text: distinctly

text: diﬀerent

text: behav-

text: motions

text: with

text: a

text: correlation

text: length

text: larger

text: than

text: the

text: swim-

text: iors

text: with

text: and

text: without

text: HIs.

text: At

text: a

text: relatively

text: small

text: vol-

text: mer

text: size.

text: Interestingly,

text: such

text: correlated

text: motions

text: are

text: ume

text: fraction,

text: with

text: HIs,

text: the

text: translational

text: swimming

text: mo-

text: hardly

text: seen

text: in

text: suspensions

text: of

text: pullers.

text: Saintillan

text: and

text: tion

text: becomes

text: slower,

text: while

text: rotational

text: diﬀusion

text: becomes

text: Shelley

text: reported

text: similar

text: results

text: by

text: simulating

text: a

text: faster;

text: these

text: are

text: natural

text: consequences

text: of

text: the

text: far-ﬁeld

text: and

text: similar

text: model,

text: where

text: the

text: active

text: particle

text: is

text: modeled

text: as

text: intermediate-range

text: pair

text: interactions

text: just

text: described,

text: and

text: a

text: stress-prescribed

text: rigid

text: rod.

text: Furthermore,

text: they

text: also

text: are

text: stronger

text: than

text: the

text: corresponding

text: eﬀects

text: without

text: HIs.

text: found

text: that

text: an

text: isotropic

text: or

text: aligned

text: homogeneous

text: state

text: On

text: the

text: other

text: hand,

text: at

text: large

text: enough

text: volume

text: fractions,

text: the

text: becomes

text: unstable

text: due

text: to

text: HIs

text: and

text: some

text: non-linear

text: hy-

text: translational

text: and

text: rotational

text: motions

text: are

text: both

text: strongly

text: drodynamic

text: eﬀects

text: lead

text: to

text: steady-state

text: structure

text: with

text: suppressed.

text: With

text: crowding,

text: because

text: less

text: space

text: is

text: avail-

text: a

text: pronounced

text: density

text: inhomogeneity

text: and

text: local

text: orienta-

text: able

text: around

text: a

text: swimmer,

text: the

text: ability

text: of

text: each

text: force

text: dipole

text: tional

text: order

text: of

text: swimmers

text: Although

text: these

text: previous

text: to

text: set

text: up

text: a

text: coherent

text: propulsive

text: ﬂow

text: ﬁeld

text: is

text: diminished,

text: studies

text: do

text: not

text: contradict

text: our

text: simulations,

text: we

text: found

text: that,

text: weakening

text: both

text: the

text: motility

text: and

text: the

text: HIs.

text: However,

text: due

text: at

text: certain

text: intermediate

text: densities,

text: the

text: clustering

text: caused

text: by

text: to

text: the

text: incompressible

text: nature

text: of

text: HIs,

text: neighboring

text: swim-

text: activity-induced

text: attractions

text: (or

text: hydrodynamic

text: trapping)

text: mers

text: push

text: and

text: pull

text: each

text: other

text: around

text: even

text: without

text: di-

text: is

text: greater

text: than

text: previously

text: reported,

text: which,

text: as

text: already

text: dis-

text: rect

text: contact.

text: This

text: impedes

text: both

text: the

text: translational

text: and

text: cussed,

text: can

text: be

text: attributed

text: to

text: the

text: eﬀects

text: of

text: near-ﬁeld

text: HIs.

text: rotational

text: motions

text: much

text: more

text: than

text: is

text: the

text: case

text: without

text: The

text: advantage

text: of

text: the

text: hybrid

text: simulation

text: methods

text: such

text: HIs,

text: where

text: only

text: direct

text: collisional

text: forces

text: act

text: between

text: the

text: as

text: that

text: used

text: in

text: the

text: present

text: study

text: is

text: that,

text: by

text: directly

text: swimmers.

text: taking

text: the

text: solvent

text: dynamics

text: into

text: account,

text: we

text: can

text: accu-

text: The

text: diﬀerent

text: volume

text: fraction

text: dependences

text: of

text: the

text: motil-

text: rately

text: treat

text: HIs

text: among

text: ﬁnite-sized

text: particles

text: at

text: moderate

text: ity

text: with

text: and

text: without

text: HIs

text: inﬂuence

text: the

text: tendency

text: to

text: form

text: separations,

text: and

text: also

text: capture

text: some

text: signiﬁcant

text: near-ﬁeld

text: clusters.

text: For

text: our

text: chosen

text: interaction

text: and

text: propulsion

text: pa-

text: eﬀects.

text: In

text: the

text: previous

text: studies,

text: on

text: the

text: other

text: hand,

text: ac-

text: rameters,

text: clustering

text: is

text: maximal

text: at

text: an

text: intermediate

text: vol-

text: tive

text: particles

text: are

text: essentially

text: represented

text: as

text: pairs

text: of

text: point

text: ume

text: fraction

text: in

text: each

text: case,

text: but

text: this

text: volume

text: fraction

text: is

text: forces

text: and

text: HIs

text: are

text: simply

text: evaluated

text: by

text: using

text: the

text: usual

text: lower,

text: and

text: clustering

text: stronger,

text: with

text: HIs

text: than

text: without.

text: Stokeslet.

text: However,

text: such

text: an

text: approach

text: based

text: on

text: far-ﬁeld

text: The

text: conditions

text: under

text: which

text: bulk

text: phase

text: separation

text: arises,

text: hydrodynamics

text: is

text: not

text: able

text: to

text: fully

text: capture

text: the

text: collective