sensing, this M2CIC problem is much more complicated
than the uni-modality coverage problems.
3PROBLEM FORMULATION
3.1 Confident Information Coverage
We first briefly review the CIC model proposed in our pre-
vious study [1]. For field reconstruction, we refer to recon-
struct the attributes of some spatial-temporal physical
phenomenon via deployed sensors. Let z
t
ðxÞ denote the
true value of the phenomenon attribute at some reconstruc-
tion point x at time t, and
^
z
t
ðxÞ its reconstructed (estimated)
value. Let z
t
ðsÞ denote the measurement of a sensor s.A
reconstruction function can be described as f : fz
t
ðs
i
Þjs
i
2
SðxÞg !
^
z
t
ðxÞ, where SðxÞ denotes the set of sensors within
the reconstruction area of x.
The purpose of physical at trib ute reconstruction is t o
minimize the estimation error jz
t
ðxÞ^z
t
ðxÞj.Thetrue
value z
t
ðxÞ is different at different sampling instant as
the physical attribute is a temporal-spatial process. The
estimation error jz
t
ðxÞ
^
z
t
ðxÞj can be modeled as a ran-
dom variable, but i ts probability distribution may be
unknown. So we use the time-average root mean square
error (RMSE) to evaluate the reconstruction quality for
each reconstruction point, that is,
FðxÞ
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
1
T
X
T
t¼1
ðz
t
ðxÞ
^
z
t
ðxÞÞ
2
v
u
u
t
: (1)
The reconstruction RMSE measures how well the physical
attribute at the point x can be reconstructed by its surround-
ing sensors’ measurements, which is the motivation of the
CIC model:
Confident information coverage (F-Coverage). Given a recon-
struction function f, a space point x is called being confident
information covered (or F-covered), if the time-average
RMSE of its reconstructed information FðxÞ is not larger
than the application requirement ",i.e.,FðxÞ".
In this paper, we use an Ordinary Kriging estimator as the
construction function [8], [30], [31], because it only requires
the physical attribute to be a second-order stationary pro-
cess. Furthermore, for some of such processes, such as soil
temperature and humidity, we use a Gaussian variogram
model to captured the characteristics of a physical attribute:
gðhÞ¼
0;h¼ 0;
D
0
þ Dð1e
h
2
a
2
Þ h>0;
(
(2)
where D
0
, D, a are called nugget, sill and correlation range,
respectively. The correlation range is the distance which sep-
arates the correlated and uncorrelated physical attributes.
For a specific physical attribute and a point x, because of the
spatial correlation, only the points within the correlation
range of the x carry correlated and significant information
for reconstruction. Generally, different physical attributes
have different spatial correlation, which should be modeled
by different random processes and correlation models.
For a reconstruction point, the ordinary kriging uses the
weighted average of the measurements of those sensors
within its reconstruction zone SðxÞ to interpolate the attri-
bute value
^
z
t
ðxÞ,
^
zðxÞ¼
X
jSðxÞj
i¼1
i
zðs
i
Þ;s
i
2SðxÞ; (3)
where
i
s are the interpolation weights. According to the
unbiased property of ordinary kriging, the sum of weights
equal to 1, i.e.,
P
jSðxÞj
i¼1
i
¼ 1. The optimal weights are
obtained by minimizing the kriging variance. Using a
Lagrange multiplier mðxÞ for the minimization yields a lin-
ear kriging system of n þ 1 equations with n þ 1 unknowns,
where n ¼jSðxÞj,
1
.
.
.
n
mðxÞ
0
B
B
B
B
@
1
C
C
C
C
A
¼
gðs
1
;s
1
Þ ...gðs
1
;s
n
Þ 1
.
.
.
.
.
.
gðs
n
;s
1
Þ ...gðs
n
;s
n
Þ 1
1... ...1 0
0
B
B
B
B
@
1
C
C
C
C
A
1
gðs
1
;xÞ
.
.
.
gðs
n
;xÞ
1
0
B
B
B
B
@
1
C
C
C
C
A
;
(4)
where gðs
i
;s
j
Þ and gðs
i
;xÞ can be computed from the vario-
gram functions. Eq. (3) is the reconstruction function for the
reconstruction point. Furthermore, the RMSE of a recon-
struction point can be computed by
FðxÞ¼
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
X
n
i¼1
i
gðs
i
;xÞþmðxÞ
s
: (5)
For a second-order stationary physical phenomenon
whose spatial correlations are characterized by a variogram
gðhÞ, each
i
is only dependent on the geometric relations
among the location x and the locations of the sensors. If
FðxÞ", then the reconstruction location x is Fcovered.
Therefore, the theoretical RMSE of Eq. (5) indicates that we
can determine whether a point is Fcovered simply by the
geometric relations among itself and its neighboring sensors.
The benefits of the proposed CIC coverage model are as
follows. The first, it can capture sensors’ capability and
quality for reconstructing physical phenomena within a
sensor field. The second, with the aid of phenomenon
modeling and reconstruction function, the proposed model
relates the reconstruction quality with the geometric dis-
tances among a space point and its surrounding sensors.
The third, based on the CIC model, we can determine how
many sensors are needed for a given sensing area and their
locations in the deterministic deployment. Furthermore,
the proposed model is downward compatible with the
disk coverage model, while it can greatly reduce sensor
density for area coverage due to its exploitation of collabo-
rative interpolation.
3.2 The M2CIC Problem
In this section, we define and formulate the multi-modal con-
fident information coverage problem in sensor networks.
In a W W ðkm
2
Þ sensor field, there are L phy-
sical attributes, V ¼fv
1
;v
2
; ...;v
L
g, to be reconstructed and
Fcovered. Without loss of generality, the spatial correla-
tion ranges of these attributes are assumed to be
904 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 26, NO. 3, MARCH 2015