Analysis of Breakdown Probability of Wireless Sensor
Networks with Unreliable Relay Nodes
Takayuki Nozaki1 , Takafumi Nakano2 , Tadashi Wadayama21 Yamaguchi University
2 Nagoya Institute of Technology
This work is supported by JSPS Grant-in-Aid for Scientific Research
16K16007 and 16H02878

ISIT2017
26th June 2017

Abstract(n ) j(n−j ) λ min{n1 ,j}n−j n−j−1∑∑
j ϵ (1 − ϵ)n1Pλ,n (ϵ) ≤2 i1(λn)(λ(n−j))2 λj
n1 =1i1 =0
j=0
λn1()()λnλ(n − n1 ) − i12×.
λ(n − n1 − j)i1 , λn12−i1 , λ(n−n21 )−i1n∑Background (1)Wireless sensor networks (WSNs) are represented by graphs
There are possibilities that nodes are breakdown (or flat batteries)
The network is breakdown if survivor graph is separated
Survivor graph is a subgraph constructed from the remaining nodes
We analyze the network breakdown probability for WSNs with unreliablenodes

network is breakdown

network is not breakdown

Background (2)Networks with unreliable edges
Moore and Shannon [2] considered network reliability problem
Provan and Ball [3] and Vailant [4] showed that network reliability
problem is #P-complete
Karger [5] presented a randomized polynomial time approximation
algorithm for the all terminal network reliability problems
Networks with unreliable nodes
There are no works, as far as the authors know.
Outline1 Models
122

Random graph model
Node fault model

Main result
Main theorem (upper bound)
Computer simulations
3 Proof12

Graph and Bipartite Graph
Any graph can be converted into a bipartite graph

Graph G

Bipartite Graph GbGraph Ensemble and Node fault model
Define graph ensemble in a similar way to LDPC code ensemble

Graph Ensemble
T (n, λ, 2) : (λ, 2)-regular bipartite graph ensemble
G(n, λ) : counterpart of T (n, λ, 2) (λ-regular random graph ensemble)

Node fault model
Each node is independently broken w.p. ϵ.

..
.

Random PermutationnT (n, λ, 2)

..
.

λn2

Main Theorem
Theorem 1
Pλ,n (ϵ) : ensemble average of network breakdown probabilityn ( )∑n j(U )ϵ (1 − ϵ)n−j Qj,λ,n ,jj=0(n−j ) λ min{n1 ,j}n−j−1∑∑1(U )
n1Qj,λ,n := (λn)
2 i1(λ(n−j))
2 λj n1 =1i1 =0λn1)()(λnλ(n − n1 ) − i12.
×λ(n − n1 − j)i1 , λn12−i1 , λ(n−n21 )−i1
(U )Pλ,n (ϵ) ≤ Pλ,n (ϵ) :=( ){n!
, if k, n ∈ Z+ ,n:= k!(n−k)!
k0,otherwise,(){(a1 +a2 +···+ak )!
,a1 + a2 + · · · + ak
a1 !a2 !···ak !
:=a1 , a2 , . . . , ak0,if a1 , a2 , . . . , ak ∈ Z+ ,otherwise.

Computer experiments (1)λ = 5, n = 100, 1000
Upper bound is tight for small ϵComputer experiments (2)n = 100
Network breakdown probability appears an exponential function of λ

Proof (1: Ensemble average)
G \ Z : Survivor graph
E[·] : average over ensemble G(n, λ)Pλ,n (ϵ) =n∑∑

E[I[G \ Z : separated]]ϵj (1 − ϵ)n−jj=0 Z⊂N,|Z|=j=n∑∑Qj,λ,n ϵj (1 − ϵ)n−jj=0 Z⊂N,|Z|=jn ( )∑n j=ϵ (1 − ϵ)n−j Qj,λ,n .
jj=0Qj,λ,n : average of network breakdown probability when fixed j nodes arebroken
Qj,λ,n := E[I[G \ Z : separated]],(|Z| = j)
∑I[(G \ Z)b : separated]=(nλ)!
Gb ∈T (n,λ,2)

Proof (2: Bipartite configuration)∑It is not trivial to count Gb ∈T (n,λ,2) I[(G \ Z)b : separated]
We will derive upper bound by counting bipartite configurations
Bipartite configuration
C1

V1

V2
I1

V0

C2

I2

C0If nodes in V0 are broken, the network is breakdown
Bipartite configuration represents a bipartite graph that are separated if V0are removed

Proof (3: Bipartite configuration)
Each bipartite graph corresponds to at least 2 bipartite configurations
If count the bipartite∑ configuration with certain condtion, we have an
upper bound of Gb ∈T (n,λ,2) I[(G \ Z)b : separated]
Example: n = 7, λ = 2
V1

I1

V0
v1

I2
c1

V2
v2

v5

c4

v4

c3

v3

C2

C1

c2

c2

V1
v2

I1
c1

V0
v1

I2

V2v3

c3

v4

c4

v5

c7
c5
V1

v7

I1

c7v6

c7v7

V0v1c6I2c1v4

c3

V2v2v3v6

c5

V1v2

c6
I1
c1V0v1I2V2v3c3v4c7v7v6c6v7
C2

C1c2c2c4c6v6

c4v5c5v5c5

Proof (4: Number of bipartite configuration)n0 := |V0 |, n1 := |V1 |, i1 := |I1 |, i2 := |I2 |(Number of the other sets of nodes depends on n0 , n1 , i1 , i2 )An0 ,n1 ,i1 ,i2 : the number of bipartite configuration with n0 , n1 , i1 , i2(An0 ,n1 ,i1 ,i2 = (λn)!

C1nn0 ,n1 ,n2)(λn/2i1 ,i2 ,c0 ,c1 ,c2()λnλn0 ,λn1 ,λn2V2V1I1C0V0I2C2)
2i1 +i2 .

Proof (5: Upper bound)
K(j): the number of bipartite configurations n0 = jn−j−1 λ min{j,n2 ,λj−i1 }∑ 1 } min{λn∑1 ∑()Aj,n1 ,i1 ,i2 .
K(j) = nj

n1 =1Qj,λ,n =1(λn)!

≤i1 =0∑i2 =0I[(G \ Z)b : separated]]

Gb ∈T (n,λ,2)

1 K(j)(U )=: Qj,λ,n(λn)! 2(each bipartite graph corresponds to at least 2 bipartite configurations)(U )Qj,λ,n :=)()(n−j ) λ min{n1 ,j} (n−j−1λn∑∑1λ(n − n1 ) − i1n1i122( )(λ(n−j))λ(n − n1 − j)2 λni1 , λn12−i1 , λ(n−n21 )−i1λj
n1 =1i1 =0
λn1Conclusion and on going work
Conclusion
We have studied the network reliability problem under node fault
model
We have derived an upper bound of average network breakdown
probability
Simulation results shows that the upper bound is tight

On going work
Asymptotic analysis of network breakdown probability under node
fault model