Section 5. Section 6 gives a simulation example to study the effects of different parameters on the proposed algorithm.
Section 7 draws conclusions and summarize the main achievements of this paper.
Notation: The notations are standard. Throughout the paper, the notation e
i
means the i-th basis column vector. 1
N
and 0
N
are, respectively, the N-dimensional vector of all 1 and 0. I
N
and O
N
are, respectively, the N-dimensional identity matrix and
N-dimensional matrix of all 0. k
max
½A and k
min
½A denote, respectively, the maximize and minimize eigenvalue of matrix
A.
.
max
½A and
.
min
½A represent, respectively, the maximize and minimize nonzero entry of matrix A. For the matrix A; r
i
½A
denotes the row sum of the i-th row of A
2
, and R½A¼diagfr
1
½A; ...; r
N
½Ag.
2. Preliminary
In the following, we briefly introduce the spectral graph theory and the framework of probabilistic quantization, and
describe the problem adopted in this paper.
2.1. Spectral graph theory
In this paper, we model a WSN as a time-varying weighted undirected graph GðtÞ ¼ fVðt Þ; EðtÞ; AðtÞg of order N, consisting
of a set of nodes VðtÞ¼f1; 2; ...; Ng, a set of edges EðtÞ# VðtÞVðtÞ, and a weighted adjacent matrix AðtÞ¼½a
ij
ðtÞ 2 R
NN
.An
edge in graph GðtÞ is denoted by e
ij
ðtÞ¼ði; jÞ. If there is an edge from node j to node i, then it is said that nodes i and j can
communicate with each other reliably. As usual, we assume that there is no self-loop in GðtÞ;
8
t. Meanwhile, a
ij
ðtÞ > 0 is the
weight associated with the edge e
ij
ðtÞ; otherwise, a
ij
ðtÞ¼0. Throughout the paper we utilize the Metropolis–Hastings
weights [25] defined as follows:
a
ij
ðtÞ¼
1
maxfd
i
ðtÞ;d
j
ðtÞg
; ði; jÞ2EðtÞ
1
X
j2N
i
ðtÞ
1
maxfd
i
ðtÞ;d
j
ðtÞg
; i ¼ j
0; otherwise
8
>
>
>
<
>
>
>
:
where N
i
ðtÞ¼fjjði; jÞ2EðtÞg is the neighborhood set of node i, and d
i
ðtÞ denotes the cardinality of N
i
ðtÞ. Here, we define the
doubly stochastic matrix P 2 R
NN
as 1
>
N
P ¼ 1
>
N
and P1
N
¼ 1
N
. By construction, it is easy to see that AðtÞ is a nonnegative
doubly stochastic matrix,
8
t.
Since GðtÞ is a time-varying graph which may be an unconnected graph at time t, we need introduce a new measurement
of graph connectivity for GðtÞ to overcome the unavailability of the Fiedler connectivity [3] when the topology is not
connected, defined as follows, where
j
ðAÞ is called as the sieve constant of a graph, first proposed by Leonard [8].
Definition 1. For a nonnegative stochastic matrix A ¼½a
ij
2R
NN
;
j
ðAÞ is defined as
j
ðAÞ¼ min
m¼1;...;N
min
kxk
2
¼1
x
2
m
þ
X
k–l
a
kl
ðx
k
x
l
Þ
2
:
To ensure the topology connectivity of the time-varying network over time, we employ the uniform connectivity condi-
tion [16,28] as shown in the following assumption, which means that once we take all the edges that have appeared between
times kB and ðk þ 1ÞB, the graph is connected.
Assumption 1. There exists an integer B P 1 such that the graph union N;
S
ðkþ1ÞB
kBþ1
EðtÞ
is connected for all nonnegative
integers k.
2.2. Probabilistic quantization
In this subsection, we present a brief review of the probabilistic quantization scheme adopted in this paper, please see [1]
for more details. Assume that the scalar value x
i
2 R is identically uniformly bounded to a finite interval ½U; U.
Furthermore, we wish to obtain a quantized message qðx
i
Þ with length ‘ bits, where ‘ represents the quantization precision.
Therefore, we have L ¼ 2
‘
quantization points given by the set
P
¼f
p
1
;
p
2
; ...;
p
L
g where
p
1
¼U and
p
L
¼ U. The points
are uniformly spaced such that
D
¼
p
jþ1
p
j
for j 2f1; 2; ...; L 1g. It follows that
D
¼ 2U=ð2
‘
1Þ. Now suppose
x
i
2½
p
j
;
p
jþ1
Þ, then x
i
is quantized in a probabilistic manner
Pfqðx
i
Þ¼
p
jþ1
g¼r and Pfqðx
i
Þ¼
p
j
g¼1 r
where r ¼ðx
i
p
j
Þ=
D
. It is easy to see that when the variable is exactly equal to a quantization centroid, there is zero proba-
bility of choosing another centroid.
H. Wang et al. / Information Sciences 309 (2015) 11–25
13