1

Radio Tomographic Imaging with Wireless

Networks
Joey Wilson and Neal Patwari
The University of Utah

Abstract—Radio Tomographic Imaging (RTI) is an emerging technology for imaging the attenuation caused by physical objects in
wireless networks. This paper presents a linear model for using received signal strength (RSS) measurements to obtain images of
moving objects. Noise models are investigated based on real measurements of a deployed RTI system. Mean-squared error (MSE)
bounds on image accuracy are derived, which are used to calculate the accuracy of an RTI system for a given node geometry. The
ill-posedness of RTI is discussed, and Tikhonov regularization is used to derive an image estimator. Experimental results of an RTI
experiment with 28 nodes deployed around a 441 square foot area are presented.

Index Terms—Wireless, Sensor Networks, Inverse Filtering, Linear Systems, Applications

1 I NTRODUCTION

W HEN an object moves into the area of a wireless

network, links which pass through that object
will experience shadowing losses. This paper explores
in detail the use of shadowing losses on links between
many pairs of nodes in a wireless network to image
the attenuation of objects within the network area. We
refer to this problem as radio tomographic imaging (RTI),
as depicted in Fig. 1.
RTI may be useful in emergencies, rescue operations,
and security breaches, since the objects being imaged
need not carry an electronic device. Using the images to
track humans moving through a building, for example,
provides a basis for new applications in security systems
and “smart” buildings.
The reduction in costs for radio frequency integrated
circuits (RFICs) and advances in peer-to-peer data net- Fig. 1. An illustration of an RTI network. Each node
working have made realistic the use of hundreds or broadcasts to the others, creating many projections that
thousands of simple radio devices in a single RTI de- can be used to reconstruct an image of objects inside the
ployment. Since the relative cost of such devices is low, network area.
large RTI networks are possible in applications that may
be otherwise impractical.
Radio tomography draws from the concepts of two ing method which measures signal strengths on many
well-known and widely used types of imaging systems. different paths through a medium, but similar to radar
First, radar systems transmit RF probes and receive systems, it does so at radio frequencies. It also faces two
echoes caused by the objects in an environment [1]. A de- significant challenges:
lay between transmission and reception indicates a dis- • The system discussed in this paper measures only
tance to a scatterer. Phased array radars also compute an signal strength. No information about the phase or
angle of bearing. Such systems image an object in space the time-domain of a signal is available.
based on reflection and scattering. Secondly, computed • The use of RF, as opposed to much higher frequency
tomography (CT) methods in medical and geophysical EM waves (e.g., x-rays), introduces significant non-
imaging systems use signal measurements along many line-of-sight (NLOS) propagation in the transmis-
different paths through a medium. The measurements sion measurements. Signals in standard commercial
along the paths are used to compute an estimate of the wireless bands do not travel in just the line-of-sight
spatial field of the transmission parameters throughout (LOS) path, and instead propagate in many paths
the medium [2]. RTI is also a transmission-based imag- from a transmitter to a receiver.
 2

1.1 Applications To emphasize the small required bandwidth compared

Despite the difficulties of using RF, there is a major to UWB, some relevant research is being called “ultra-
advantage: RF signals can travel through obstructions narrowband” (UNB) radar [9], [10], [11]. These systems
such as walls, trees, and smoke, while optical or infrared propose using narrowband transmitters and receivers
imaging systems cannot. RF imaging will also work deployed around an area to image the environment
in the dark, where video cameras will fail. Even for within that area. Measurements are phase-synchronous
applications where video cameras could work, privacy at the multiple nodes around the area. Such techniques
concerns may prevent their deployment. An RTI system have been applied to detect and locate objects buried un-
provides current images of the location of people and der ground using what is effectively a synthetic aperture
their movements, but cannot be used to identify a per- array of ground-penetrating radars [12]. Experiments
son. have been reported which measure a static environment
One main future application of RTI is to reduce injury while moving one transmitter or one receiver [11], and
for correctional and law enforcement officers; many are measure a static object on a rotating table in an anechoic
injured each year because they lack the ability to de- chamber in order to simulate an array of transmitters
tect and track offenders through building walls [3]. By and receivers at many different angles [11], [12], [9].
showing the locations of people within a building during Multiple-input-multiple-output (MIMO) radar is another
hostage situations, building fires, or other emergencies, emerging field that takes advantage of multiple trans-
RTI can help law enforcement and emergency respon- mitters and receivers to locate objects within a spatial
ders to know where they should focus their attention. area [13]. In this framework, signals are transmitted into
Another application is in automatic monitoring and the area of interest, objects scatter the signal, and the
control in “smart” homes and buildings. Some building reflections are measured at each receiver. The scattering
control systems detect motion in a room and use it objects create a channel matrix which is comparable to
to control lighting, heating, air conditioning, and even the channel matrix in MIMO communication theory. RTI
noise cancellation [4]. RTI systems can further determine differs from MIMO radar in the same way that it differs
how many people are in a room and where they are from traditional radar. Instead of measuring reflections,
located, providing more precise control. RTI uses the shadowing caused by objects as a basis for
RTI has application in security and monitoring sys- image reconstruction.
tems for indoor and outdoor areas. For example, most Recent research has also used measurements of sig-
existing security systems are trip-wire based or camera- nal strength on 802.11 WiFi links to detect and locate
based. Trip-wire systems detect when people cross a a person’s location. Experiments in [14] demonstrate
boundary, but do not track them when they are within the capability of a detector based on signal strength
the area. Cameras are ineffective in the dark and have measurements determine the location of a person who
limited view angles. An RTI system could serve both as is not carrying an electronic device. In this case, the
a trip-wire, alerting when intruders enter into an area, system is trained by a person standing at pre-defined
and a tracking system to follow their movements. positions, and RSS measurements are recorded at each
location. When the system is in use, RSS measurements
are compared with the known training data, and the best
1.2 Related Work position is selected from a list.
RF-based imaging has been dominated in the commer- Our approach is not based on point-wise detection.
cial realm by ultra-wideband (UWB) based through-the- Instead, we use tomographic methods to estimate an
wall (TTW) imaging devices from companies like Time image of the change in the attenuation as a function of
Domain [5], Cambridge Consultants [6], and Camero space, and use the image estimate for the purposes of
Tech [7]. These companies have developed products indicating the position of a moving object.
using a phased array of radars that transmit UWB
pulses and then measure echoes to estimate a range and 1.3 Overview
bearing. These devices are accurate close to the device, Section 2 presents a linear model relating RSS mea-
but inherently suffer from accuracy and noise issues at surements to the change in attenuation occurring in
long range due to mono-static radar scattering losses and a network area, and investigates statistics for noise in
large bandwidths. Some initial attempts [8] allow 2-4 of dynamic multipath environments. Section 3 describes
these high-complexity devices to collaborate to improve an error bound on image estimation for a given node
coverage. geometry. This is useful to determine which areas of
In comparison, in this paper we discuss using dozens a network can be accurately imaged for a given set of
to hundreds of low-capability collaborating nodes, node locations. Section 4 discusses the ill-posedness of
which measure transmission rather than scattering and RTI, and derives a regularized solution for obtaining
reflection. Further, UWB uses an extremely wide RF an attenuation image. Section 5 describes the setup of
bandwidth, which may limit its application to emer- an actual RTI experiment, the resultant images, and a
gency and military applications. RTI is capable of using discussion of the effect of parameters on the accuracy of
radios with relatively small bandwidths. the images.
 3

2 M ODEL
2.1 Linear Formulation
When wireless nodes communicate, the radio signals
pass through the physical area of the network. Objects
within the area absorb, reflect, diffract, or scatter some
of the transmitted power. The goal of an RTI system is
to determine an image vector of dimension RN that de-
scribes the amount of radio power attenuation occurring
due to physical objects within N voxels of a network
region. Since voxel locations are known, RTI allows one
to know where attenuation in a network is occurring,
and therefore, where objects are located.
If K is the number of nodes in the RTI network, then
2
the total number of unique two-way links is M = K 2−K .
Any pair of nodes is counted as a link, whether or
not communication actually occurs between them. The
signal strength yi (t) of a particular link i at time t is
dependent on:
• Pi : Transmitted power in dB.
Fig. 2. An illustration of a single link in an RTI network that
• Si (t): Shadowing loss in dB due to objects that
travels in a direct LOS path. The signal is shadowed by
attenuate the signal. objects as it crosses the area of the network in a particular
• Fi (t): Fading loss in dB that occurs from construc-
path. The darkened voxels represent the image areas that
tive and destructive interference of narrow-band have a non-zero weighting for this particular link.
signals in multipath environments.
• Li : Static losses in dB due to distance, antenna
patterns, device inconsistencies, etc. where the noise is the grouping of fading and measure-
• νi (t): Measurement noise.
ment noise
Mathematically, the received signal strength is described
as ni = Fi (tb ) − Fi (ta ) + νi (tb ) − νi (ta ) (5)
yi (t) = Pi − Li − Si (t) − Fi (t) − νi (t) (1)
and
The shadowing loss Si (t) can be approximated as 4xj = xj (tb ) − xj (ta ) (6)
a sum of attenuation that occurs in each voxel. Since
the contribution of each voxel to the attenuation of a is the difference in attenuation at pixel j from time ta to
link is different for each link, a weighting is applied. tb .
Mathematically, this is described for a single link as If all links in the network are considered simultane-
N ously, the system of RSS equations can be described in
X
Si (t) = wij xj (t). (2) matrix form as
j=1 4y = W4x + n (7)
where xj (t) is the attenuation occurring in voxel j at where
time t, and wij is the weighting of pixel j for link i. If
a link does not “cross” a particular voxel, that voxel is 4y = [4y1 , 4y2 , ..., 4yM ]T
removed by using a weight of zero. For example, Fig. 4x = [4x1 , 4x2 , ..., 4xN ]T
2 is an illustration of how a direct LOS link might be
weighted in a non-scattering environment. n = [n1 , n2 , ..., nM ]T
Imaging only the changing attenuation greatly simpli- [W]i,j = wij (8)
fies the problem, since all static losses can be removed
over time. The change in RSS 4yi from time ta to tb is In summary, 4y is the vector of length M all link
difference RSS measurements, n is a noise vector, and
4yi ≡ yi (tb ) − yi (ta ) 4x is the attenuation image to be estimated. W is the
= Si (tb ) − Si (ta ) + Fi (tb ) − Fi (ta ) weighting matrix of dimension M ×N , with each column
representing a single voxel, and each row describing the
+νi (tb ) − νi (ta ), (3)
weighting of each voxel for that particular link. Each
which can be written as variable is measured in decibels (dB).
N
X To simplify the notation used throughout the rest of
4yi = wij 4xj + ni , (4) this paper, x and y are used in place of 4x and 4y,
j=1 respectively.
 4

2.2 Weight Model indoor fixed wireless communications systems which

If knowledge of an environment were available, one periodically experienced fading due to motion in the
could estimate the weights {wij }j for link i which re- area of the link. Bultitude found that RSS experienced
flected the spatial extent of multiple paths between trans- intervals of significant fading which were caused by
mitter and receiver. Perhaps calibration measurements human motion in and around the area. Most of the time,
could aid in estimation of the linear transformation W. the measured RSS vary slowly around a nearly constant
However, with no site-specific information, we require mean, what we call a non-fading interval. When in a
a statistical model that describes the linear effect of the fading interval, RSS varies up to 10 dB higher and 20 dB
attenuation field on the path loss for each link. below the non-fading interval mean, with a distribution
An ellipsoid with foci at each node location can be that can be characterized as a Rician distribution [17].
used as a method for determining the weighting for each Other measurements find temporal fading statistics more
link in the network [15]. If a particular voxel falls outside closely match a log-normal distribution [18]. The fading
the ellipsoid, the weighting for that voxel is set to zero. If / non-fading interval process can be modeled as a two-
a particular voxel is within the LOS path determined by state Markov chain [19], which alternates between a low-
the ellipsoid, its weight is set to be inversely proportional variance and high-variance distribution. Over all time,
to the square root of the link distance. Intuitively, longer measurements show a two-part mixture distribution for
links will provide less information about the attenua- the RSS on a fixed link.
tion in voxels that they cross. When link distances are In linear terms, we could model this data as a mixture
very long, the signals reflect and defract around the of two Rician distributions as in [17]; we could also
obstructions. A link with a distance of only a few feet model it as a mixture of log-normal terms as suggested
will experience more change in RSS when an obstruction by results in [18]. We note that the logarithm of a Rician
occurs than a link with a length of hundreds of feet. random variable is often similar in distribution to the
Past studies have shown that the variance of link log-normal, perhaps a cause of disagreement between
shadowing does not change with distance. In accordance measurement studies. We choose to use the log-normal
with these studies, dividing by the square root of the link mixture model for simplicity; in the (dB) scale, this is a
distance ensures that the voxel weighting takes this into two-part Gaussian mixture model:
account [16]. The weighting is described mathematically
u2
 
p
p k exp − 2 ,
X
as fni (u) = (10)
1 1 if dij (1) + dij (2) < d + λ 2πσk2 2σk

wij = √ (9) k∈{1,2}
d 0 otherwise
where pk is the probability of part k, p2 = 1−p1 , σk2 is the
where d is the distance between the two nodes, dij (1)
variance of part k, and fni (u) is the probability density
and dij (2) are the distances from the center of voxel j
function of the noise random variable ni . Without loss
to the two node locations for link i, and λ is a tunable
of generality, we let σ2 > σ1 so that part 2 is the higher
parameter describing the width of the ellipse.
variance component of the mixture.
The width parameter λ is typically set very low in
Past radio link measurements have not distinguished
RTI, such that it is essentially the same as using the LOS
between motion which shadows the line-of-sight path
model as depicted in Fig. 2. The use of an ellipsoid is
(the signal in RTI), and motion which does not shadow
primarily used to simplify the process of determining
the line-of-sight path (the noise) [17], [18], [19], [14]. To
which voxels fall along the LOS path.
investigate the statistics of RTI noise, we present exper-
imental tests which measure the time-varying statistics
2.3 Noise of links during motion which does not obstruct a link.
To complete the model of (7), the statistics of the To collect experimental samples of noise, we set up 28
noise vector n in (7) must be examined. Here, noise is nodes in an indoor office area empty of people. While
caused by time-varying measurement miscalibration of the nodes are transmitting and measuring RSS on each
the receiver, by the contribution of thermal noise to the pairwise link, people move around the outside of the
measured receiver signal strength, and time-variations perimeter of the deployment area. In no case did the
in the multipath channel not caused by changes to motion of a person obstruct the LOS path of any link.
the attenuation experienced by the line-of-sight path. From each link, about 66,000 measurements were taken.
If these contributions are constant with time, then the For example, consider the data on a typical link, the
calibration (when moving attenuator existed in the field) link (3, 20). The temporal fading plot in Figure 3(a)
would have been able to establish it as the baseline. shows similar results to [17], with alternating periods of
Time variation in RSS measurement when no moving heavy fading and low fading. During low fading, data
attenuator is blocking the line-of-sight path is “noise” is confined within a range of 2-3 dB around -84 dBm.
for an RTI system. During high fading, variations at ± 10 dB from the mean
Past studies have considered the time-variation of occur. The histogram shown in Fig. 3(b) correspondingly
RSS in fixed radio links. In particular, the work and shows a mixture of one high-variance and one low-
measurements of Bultitude [17] were used to design variance distribution.
 5

0.5
Histogram
−76 Mixture Model

Est. Probability Density

Received Power (dBm) −78 0.4
−80
−82 0.3
−84
−86 0.2
−88
−90 0.1
−92
0 1 2 3 4 5 6 0
−90 −85 −80 −75
Sample Number x 10
4
Received Power (dBm)
(a) Time plot (b) Histogram

Fig. 3. Temporal fading on link (3, 20) during non-obstructing motion, showing (a) time plot and (b) histogram.

We also summarize the measured data on all 28 where the inequality indicates that the matrix R − J−1


2 links.
The mean was removed from each link’s data, and the is positive semi-definite [21]. The matrix
data was merged. Fig. 4(a) is a quantile-quantile plot T
comparing the removed-mean RSS measurements with a JD = E[{∇x [ln P (y|x)]} {∇x [ln P (y|x)]} ] (13)
Gaussian distribution N (0, σd2 ), where σd2 is the empirical is known as the Fisher information matrix and represents
variance of the measurements. The PDF is approximated the information obtained from the data measurements.
by a Gaussian within ±2.5 quantiles. The matrix
As described, the data seems to follow a mixture T
distribution. From measured data, we estimate the mix- JP = E[{∇x [ln P (x)]} {∇x [ln P (x)]} ] (14)
ture parameters with an expectation-maximization (EM) represents the information obtained from a priori knowl-
algorithm [20], and the results are shown in Table 1. Fig. edge about the random parameters.
4(b) is a quantile-quantile plot comparing the removed- We assume that the noise components n =
mean RSS measurements with a mixture model with the [n1 , . . . , nM ]T are independent and identically dis-
stated parameters. tributed as two-component zero-mean Gaussian mixture
random variables as in (10). The noise is independent
Parameter Value
σ1 0.971 because we assume nodes are placed at distances larger
σ2 3.003 than the coherence distance of the indoor fading channel.
p1 0.548 From (13), we can derive that JD is given by [22, Eqn
p2 0.452
10],
TABLE 1
JD = γWT W
Gaussian-Mixture Noise Model Parameters Estimated
[fni (u)]2
Z ∞ 0
From Measurements where γ = du (15)
−∞ fni (u)

and fn0 i (u) is the derivative of fni (u) with respect to u.

3 E RROR B OUND When p2 = 0, that is, the distribution of ni is purely
Gaussian, γ reverts to 1/σ12 , one over the variance of
3.1 Derivation the distribution. For two-component Gaussian mixtures,
This section presents a lower bound on estimation error we compute γ in (15) from numerical integration. For
for the linear model (7) under the noise model discussed example, for the Gaussian-mixture model parameters
in Section 2.3. The estimation error vector is defined as calculated from the measurement experiment, as given
 = x̂ − x, and the error correlation matrix is in Table 1, we find γ = 0.548.
R = E T .
 
(11) To calculate JP , the prior image distribution P (x) must
be known or assumed. One possibility is to assume that
A well-known result in estimation theory known as the x is a zero-mean Gaussian random field with covariance
MSE, Bayesian or Van Trees bound states that the error matrix Cx . Then
correlation matrix is bounded by 1 −1
e− 2 (x Cx x)
1 T
P (x) = p (16)
R ≥ (JD + JP )−1 = J−1 (12) (2π)N |Cx |
 6

15 15
Measured Data Quantile 10 10

Measured Data Quantile

5 5

0 0

−5 −5

−10 −10

−15 −15

−20 −20

−5 0 5 −10 −5 0 5 10
Gaussian Quantile Gaussian Mixture Quantile
(a) Gaussian Model (b) Mixture Model

Fig. 4. Quantile-quantile plots comparing measured RSS data with Gaussian and Mixture distributions.

Plugging (16) into (14) results in 3.3 Example Error Bounds

The bound in (19) provides a theoretical basis for deter-
JP = C−1
x . (17) mining the accuracy of an image over the network area.
The node locations affect which pixels are accurately
These derivations of JD and JP lead to the linear MSE
estimated, and which are not. To visualize how the node
bound for RTI
locations affect the accuracy of the image estimation,
three examples are provided in Fig. 5. Table 2 shows the
R ≥ (γWT W + C−1
x )
−1
. (18)
parameters of the normalized ellipse weighting model
that were used to generate these bounds.
An important result of the bound in (18) comes from
the following property [21] Parameter Value Description
∆p .1 Pixel width (m)
E[(x − x̂)2i ] ≥ (γWT W + C−1 −1 −1
x )ii = Jii (19) λ .007 Width of weighting ellipse in (9) (m)
δc 1.3 Pixel correlation constant in (20) (m)
σx2 .1 Pixel variance in (20) (dB)2
where E[(x − x̂)2i ] represents the mean-squared-error for γ .5483 Bound parameter in (19)
pixel i. In other words, the diagonal elements of J −1
are the lower bounds on the mean-squared-error for the TABLE 2
corresponding pixels. Reconstruction parameters used to generate MSE
bound surfaces shown in Fig 5.

3.2 Spatial Covariance Model

As seen in the surfaces of Fig. 5, voxels that are
Previous work has shown that an exponential function crossed by many links have a higher accuracy than
is useful in approximating the spatial covariance of an voxels that are rarely or never crossed. The voxels in
attenuation field [23], [16]. The exponential covariance is the corners of the square deployment, the sides of the
a close approximation to the covariance that results from front-back deployment, and the low-density areas in the
modeling the spatial attenuation as a Poisson process, a random deployment, are crossed only by a few links.
common assumption for random placement of objects In some voxels, no links cross at all, and the bound
in space. Applying this model, the a priori covariance surface is limited only by the covariance of the prior
matrix Cx is generated by statistics. The known covariance of the image has the
effect of smoothing the bound surface, since knowledge
[Cx ]kl = σx2 e−dkl /δc , (20) of the attenuation of a voxel is statistically related to its
neighbors.
where dkl is the distance from pixel k to pixel l, δc is
a “space constant” correlation parameter, and σx2 is the
variance at each pixel. 3.4 Effect of Node Density
The exponential spatial covariance model is appealing The node density plays a key role in the accuracy of an
due to its simplicity and low number of parameters. RTI result. Imaging can be expected to be more accurate
Other models based on different distributions of attenu- in areas where nodes are placed closely together than in
ating objects could also be utilized. areas where nodes are spaced at large distances. When
 7

Node Locations

4
0.03
3.5

3 0.025
Y (meters)

2.5 0.02
2
0.015
1.5

1 0.01
6
0.5 4 6
4
0 2 2
0 1 2 3 4 Y (meters) 0 0 X (meters)
X (meters)

(a) 28 nodes located in a square perimeter, 8 on each side. (b) The MSE bound for the node locations shown in Fig. 5(a).

Node Locations

4 0.04
3.5

3 0.03
Y (meters)

2.5

2 0.02
1.5

1
0.01
6
0.5 4 6
4
0 2 2
0 1 2 3 4 Y (meters) 0 0 X (meters)
X (meters)

(c) 16 nodes located in a front-back setup, 8 on each side. (d) The MSE bound for the node locations shown in Fig. 5(c).

Node Locations
5
0.1
4
Y (meters)

3 0.05

0
1 6
4 6
4
0 2 2
0 1 2 3 4 5 Y (meters) 0 0 X (meters)
X (meters)

(e) 22 nodes located randomly in a square area. (f) The MSE bound for the node locations shown in Fig. 5(e).

Fig. 5. MSE bound surface plots for a square, front-back, and random node deployments. These plots were generated
using the normalized elliptical weight model with a Gaussian image prior.
 8

that very few areas contain voxels that are not crossed
Square Deployment by at least some links.
Front-Back Deployment
0.08 Random Deployment
Lower bound on average MSE

4 I MAGE R ECONSTRUCTION
0.07 4.1 Ill-posed Inverse Problem
0.06 Linear models for many physical problems, including
RTI, take the form of
0.05
y = Wx + n (21)
0.04 M M ×N
where y ∈ R is measured data, W ∈ R is a transfer
matrix of the model parameters x ∈ RN , and n ∈ RM is
0.03 a measurement noise vector. When estimating an image
from measurement data, it is common to search for a
0.1 0.2 0.3 0.4 0.5 solution that is optimal in the least-squared-error sense.
Node Density (nodes/sq. foot)
xLS = arg min ||Wx − y||22 (22)
x
Fig. 6. The lower bound on average MSE vs. node density
for three RTI network geometries. In other words, the least-squares solution minimizes the
noise energy required to fit the measured data to the
model. The least-square solution can be obtained by
setting the gradient of (22) equal to zero, resulting in
many links pass through a particular area, more RSS
information can be used to reconstruct the attenuation xLS = (WT W)−1 WT y (23)
occurring in that area. This has the effect of averaging
out noise and other corruptions in the measurements. which is only valid if W is full-rank. This is not the case
Furthermore, when links are close together, the RSS in an RTI system.
information is more concentrated on the voxels that are RTI is an ill-posed inverse problem, meaning that
crossed. This is due to the weighting function that is small amounts of noise in measurement data are am-
inversely proportional to the square root of the link plified to the extent that results are meaningless. This is
distance. due to very small singular values in the transfer matrix
W that cause certain spectral components to grow out of
To illustrate the effect of node density on the MSE
control upon inversion. To see this, W is replaced by its
bound, Fig. 6 shows the lower bound on the average
singular value decomposition (SVD):
MSE over all voxels for the three deployment geometries
shown in Fig. 5 as the density is increased. For each W = UΣVT (24)
point on the curves, the bound surface is calculated, then
averaged over all voxels. The parameters are equal to where U and V are unitary matrices, and Σ is a diagonal
those used previously in Table 2. Each geometry contains matrix of singular values. Plugging (24) into (23), the
the same number of nodes for each point on the curve, least squares solution can be written as
and is deployed around the same area. In the square XN
1 T
geometry, nodes are placed uniformly around a square xLS = VΣ−1 UT y = ui yvi (25)
σ
i=1 i
area. In the front-back geometry, the same number of
nodes are placed along two sides of the square, resulting where ui and vi are the ith columns of U and V,
in the same number of nodes per square foot. In the ran- and σi is the ith diagonal element of Σ. It is evident
dom geometry, the same number of nodes are randomly that when singular values are zero or close to zero,
placed throughout the square. the corresponding singular basis vectors are unbounded
In all three cases shown in Fig. 6, the lower bound upon inversion.
on average MSE for each deployment decreases rapidly The heuristic explanation for the ill-posedness of the
with increasing node density. The square geometry out- RTI model lies in the fact that many pixels are estimated
performs the others, due to the fact that the entire area from relatively few nodes. There are multiple possible
of the square is surrounded by nodes. There are very attenuation images that can lead to the same set of
few voxels that are not crossed by at least a few links, measurement data. For example, assume a particular
and many short links exist that cross the corners of the pixel is not crossed by any link in the network. This
square. The random geometry performs the worst out would result in the same measurement data for every
of the three when density is low, largely due to the fact possible attenuation value of that pixel, so inversion of
that in a random deployment, many voxels will not be the problem would be impossible.
crossed by any links. As density increases, the random Regularization involves introducing additional infor-
deployment out-performs the front-back geometry be- mation into the mathematical cost model to handle the
cause nodes are closer together, and the density is such ill-posedness. In some methods, a regularization term
 9

J(x) is added to the minimization objective function of number of voxels N times the number of unique links
the original problem as M in the network

freg = f (x) + αJ(x), (26) N (K 2 − K)

Nmult = N M = (32)
2
where α is the weighting parameter. Small values of α where K is the number of nodes in the network. We
lead to solutions that fit the data, while large values see that complexity increases linearly as the number of
favor the solution that matches prior information. voxels increases, and quadratically as the number of
Some regularization techniques follow from a nodes in the network increases.
Bayesian approach, where a certain prior distribution
is imposed on the model parameters. Other forms of
regularization modify or eliminate small singular values 5 E XPERIMENTAL R ESULTS
of the transfer matrix. An overview of regularization 5.1 Physical Description of Experiment
and image reconstruction in general can be found in
A wireless peer-to-peer network containing 28 nodes is
[24] and [25].
deployed for the purpose of testing the capability of RTI
to image changed attenuation. Each node is placed three
4.2 Tikhonov Regularization feet apart along the perimeter of a 21x21 foot square,
surrounding a total area of 441 square feet. The network
In Tikhonov regularization [24], an energy term is added
is deployed on a grassy area approximately 15 feet away
to the least squares formulation, resulting in the objective
from the Merrill Engineering Building at the University
function
of Utah. Each radio is placed on a stand at three feet off
1 the ground.
f (x) = ||Wx − y||2 + α||Qx||2 , (27)
2 The area surrounded by the nodes contains two trees
where Q is the Tikhonov matrix that enforces a solution with a circumference of approximately three feet. The
with certain desired properties. network is intentionally placed around the trees so that
In this paper, we use a difference matrix approxi- static objects exist in the tested RTI system. RTI should
mating the derivative operator as the Tikhonov matrix only image attenuation that has changed from the time
Q. By minimizing the energy found within the image of calibration within the deployment area. Markers are
derivative, noise spikes are suppressed and a smooth measured and placed in 35 locations within the network
image is produced. This form of Tikhonov regularization so that the humans’ locations are known and can be
is known as H1 regularization. utilized in the subsequent error analysis. A map and
Since the image is two dimensional, the regularization photo of the experiment are shown in Fig. 7.
should include the derivatives in both the vertical and The network is comprised of TelosB wireless nodes
horizontal directions. The matrix DX is the difference made by Crossbow. Each node operates in the 2.4GHz
operator for the horizontal direction, and DY is the frequency band, and uses the IEEE 802.15.4 standard
difference operator for the vertical direction. The reg- for communication. A base station node listens to all
ularized function can be written in this case as network traffic, then feeds the data to a laptop computer
via a USB port for the processing of the images. Since
1
f (x) = ||Wx − y||2 + α(||DX x||2 + ||DY x||2 ). (28) the base station node is within range of all nodes,
2 the latency of measurement retrieval to the laptop is
Taking the derivative and setting equal to zero results in low, on the order of a few milliseconds. If a multi-hop
the solution RTI network were to be deployed, this latency would
certainly increase.
x̂ = (WT W + α(DTX DX + DTY DY ))−1 WT y. (29) To avoid network transmission collisions, a simple
One major strength of Tikhonov regularization lies in token passing protocol is used. Each node is assigned
the fact that the solution is simply a linear transforma- an ID number and programmed with a known order
tion Π of the measurement data. of transmission. When a node transmits, each node that
receives the transmission examines the sender identifi-
Π = (WT W + α(DTX DX + DTY DY ))−1 WT (30) cation number. The receiving nodes check to see if it is
x̂ = Πy (31) their turn to transmit, and if not, they wait for the next
node to transmit. If the next node does not transmit, or
Since the transformation does not depend on instan- the packet is corrupted, a timeout causes each receiver to
taneous measurements, it can be pre-calculated, and move to the next node in the schedule so that the cycle
then applied for various measurements for fast image is not halted.
reconstruction. This is very appealing for realtime RTI At the arrival of each packet to the laptop, the RTI
systems that require frequent image updates [15], [26]. program running on the laptop updates a link RSS mea-
The total number of multiplications Nmult required to surement vector. At each update, the base station hears
transform the measurements into the image is the total from only one node in the network, so only RSS values
 10

20

Nodes

15
Positions

Trees
Y (feet)

Links

10

0 5 10 15 20

X (feet)

(a) Map (b) Photo

Fig. 7. The network geometry and links that correspond to Fig. 8 are illustrated in (a). (b) is a photo of the deployed
network with an experimenter standing at location (3,9).

on links involving that particular node are updated.

Each link’s RSS measurement is an average of the two Link (0,18) to (18,0)
52
directional links from i to j and j to i. RSS (dBm) 55 No obstruction
LOS obstruction
In this experiment, the system is calibrated by taking 58
61
RSS measurements while the network is vacant from
64
moving objects. The RSS vector is averaged over a 67100 200 300 400 500 600 700 800 900 1000
30 second period, which results in approximately 100
RSS samples from each link. The calibration RSS vector Link (0,9) to (21,9)
60
provides a baseline against which all other RSS measure- 63
RSS (dBm)

ments are differenced, as discussed in Section 2. Other 66

methods of calibration could be used in situations where 69
72
it is impossible to keep the network vacant from moving 75100 200 300 400 500 600 700 800 900 1000
objects. For example, a single past measurement or a
sliding window average of RSS measurement history Link (3,0) to (3,21)
53
could be used as the baseline. 56
RSS (dBm)

59
5.2 Effect of Human Obstruction 62
65
Since RTI is based on the assumption that objects shadow 68100 200 300 400 500 600 700 800 900 1000
individual links in a wireless network, it is helpful to Samples
examine the effect of obstructions on a single link. In
Fig. 8, a human stands at position (9,9) and RSS measure-
ments for each link are collected. These measurements Fig. 8. A comparison of the effect of human obstruction
are compared with the calibration measurements that on three links. In the unobstructed case, the network
were taken when the network was vacant. is vacant from human experimenters. In the obstructed
The top plot in Fig. 8 shows that a significant decrease case, a human stands at coordinate (9,9).
in RSS, anywhere from 5 to 10 dB, is experienced by
link (0,18) to (18,0) as it travels through the obstruction.
investigate the effect of human obstruction on a link’s
The middle plot shows that even though the link (9,0)
RSS when a link passes through walls or other major
to (9,21) passes through the tree, it still experiences
static obstructions. This will be essential in making the
significant loss when the human is present on the LOS
technology practical for the future applications of RTI as
path. The bottom plot in the figure shows an example
previously discussed.
of a link that does not pass through the obstruction,
resulting in very little difference in RSS.
In environments where links travel over long dis- 5.3 Cylindrical Human Model
tances, or when many objects block the direct LOS To assess the accuracy of RTI images, one must first
path, we expect the effect of a human obstruction to know or assume the “true” attenuation field that is being
be lessened. In those cases, certain links may experi- estimated. Since imaging the location of humans is the
ence losses, while others may not. Future research will primary goal of RTI, a model for the size, shape, and
 11

1.0
20
0.9
0.8
15 0.7
0.6

Y (feet)
10 0.5
0.4
0.3
5
0.2
0.1
00 5 10 15 20 0.0
X (feet)
(a) Cylindrical model image (b) RTI result

(c) Cylindrical model image (d) RTI result

Fig. 9. Images of attenuation in a wireless network where each human is modeled as a uniformly attenuating cylinder
of radius RH = 1.3 feet. In (a) and (b), a human stands at coordinate (9,9) and the total squared error is  = .021. In
(c) and (d), two humans stand at coordinates (3,15) and (18,15) and the total squared error is  = .036.

attenuation of the human body at the frequencies of the mean-squared error of the normalized image to be
interest would be required. This information is difficult
||xc − x̂N ||2
to model, since it is dependent on body types, the plane = (34)
of intersection, and other variables. N
For simplicity, a human is modeled as a uniformly where N is the number of voxels in the image.
attenuating cylinder with radius RH . In this case, the
“true” image xc for a human positioned at location cH 5.4 Example Images
can be described as
Using the model and reconstruction algorithms de-
scribed in Sections 2 and 4, we present some typical
1

if ||xj − cH || < RH
xcj = (33) image results for humans standing inside the exper-
0 otherwise
imental RTI network. A human stands at coordinate
(9,9) and RSS data is measured for a few seconds.
where xcj is the center location of voxel j. The data is averaged for 10 samples per link, and this
By scaling the image such that the maximum equals measurement differenced with the calibration data taken
one, resulting in the normalized image x̂N , we can define while the network is vacant. Figure 9 displays both the
 12

“true” attenuation based on the cylindrical model, and parameter, while the weighting ellipse parameter is held
the RTI reconstruction using H1 regularization with the constant at λ = .1. Then, it is repeated for varying ellipse
parameters listed in Table 3. parameters while holding the regularization constant at
α = 4.5. The resultant error curves are shown in Fig. 10.
Parameter Value Description The curves shown in Fig. 10 show that the choice of
∆p .5 Pixel width (feet)
λ .01 Width of weighting ellipse (feet)
regularization and weighting parameters is important
α 5 Regularization parameter in obtaining accurate images. Future research possibly
RH 1.3 Human radius for cylindrical model (feet) will explore the automatic calculation and adjustment of
TABLE 3 these parameters. It should be noted that the error curves
Image reconstruction parameters and optimal values presented are dependent upon the
pixel size used in generating the images. The general
shape of the curves, however, is similar for different pixel
Using the cylindrical human model with a radius of sizes. In this study, pixel size is held constant at .5 feet
RH = 1.3, the squared error for the single-human image for all experiments.
standing at (9,9) was measured to be  = .021. The
squared error for the two-person image was measured to
be  = .036. These error values are in general agreement 0.045

Average error
with the bounds derived in Section 3. 0.040
There are many areas in the images of Fig. 9 where 0.035
0.030
estimated attenuation is above zero, even where no
0.025
obstruction exists. This is due to the fact that a human
100 101 102
not only attenuates a wireless signal, it reflects and Regularization parameter
scatters it. The simple LOS model used in this paper
does not take into account the changes in RSS values due 0.08
0.07
Average error
to multipath caused by the obstructions being imaged. 0.06

For example, a link may be bouncing off the human and 0.05
0.04
destructively interfering with itself on a path that does 0.03
not cross through the obstruction, thus leading to error 0.02
10-2 10-1
in the estimated attenuation. Future research will seek Ellipse parameter
to refine the weighting model used in RTI such that this
modeling error is lessened. Fig. 10. Error vs. parameter curves. In the first plot, the
weighting ellipse width parameter is held constant at λ =
.1 while the regularization parameter α is varied. In the
5.5 Effect of Parameters on Image Accuracy
second, α = 4.5 and the width of the weighting ellipse is
The weighting and regularization parameters play an varied.
important role in generating accurate RTI images. If the
problem is regularized too strongly, the resultant images
may be too smooth to provide a good indication of
obstruction boundaries. If the regularization parameter 6 C ONCLUSION
is set too low, noise may corrupt the results, making it Radio tomographic imaging is a new and exciting
difficult to know if a bright spot is an obstruction or method for imaging the attenuation of physical objects
noise. with wireless networks operating at RF wavelengths.
Another parameter effecting the accuracy of an image This paper discusses a basic model and image recon-
is the width of the weighting ellipse. If the ellipse is too struction technique that has low computational com-
wide, the detail of where attenuation is occurring within plexity. Experimental results show that RTI is capable
the network may be obscured. If the ellipse is too narrow, of imaging the RF attenuation caused by humans in
voxels that do in fact attenuate a link’s signal may not dense wireless networks with inexpensive and standard
be captured by the model. This may result in a loss of hardware.
information that degrades the final image quality. Future research will be important to make RTI real-
In this paper, we empirically identify the parameters istic in security, rescue, military, and other commercial
that provide the most accurate images using the cylin- applications. First, new models and experiments must
drical human model. For each parameter, images are be developed for through-wall imaging. In this case,
formed from data measured while a human is standing the shadowing and fading caused by many objects in
at one of the known positions, as indicated in Fig. the environment may cause the LOS weighting model
7(a). Such an image is formed for each of the possible to be inaccurate. New and possibly adaptive weighting
human positions shown in Fig. 7(a). The squared error models will need to be investigated and tested.
is calculated for each image, and averaged over the Wireless protocols, customized hardware, and signal
entire set. This is performed for a varying regularization design are also important for improving RTI. Protocols
 13

that are capable of delivering low-latency RSS informa- [20] A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum
tion for large networks will be essential when deploying likelihood from incomplete data via the EM algorithm,” Journal
of the Royal Statistical Society, vol. Series B (Methodological) 39,
the technology over large areas. Antennas that direct the no. 1, pp. 1–38, 1977.
RF energy through an area may reduce the effects of [21] H. L. Van Trees, Detection, Estimation, and Modulation Theory. John
multipath and increase the effect of human presence on Wiley and Sons, 1968.
[22] A. Swami and B. M. Sadler, “On some detection and estimation
signal strength. Custom signals, perhaps taking advan- problems in heavy-tailed noise,” Signal Process., vol. 82, no. 12,
tage of frequency diversity may improve the quality of pp. 1829–1846, 2002.
RTI results. [23] B. Ripley and W. InterScience, Spatial statistics. Wiley New York,
1981.
Radio tomographic imaging may provide a low-cost [24] C. R. Vogel, Computational Methods for Inverse Problems. SIAM,
and flexible alternative to existing technologies like 2002.
ultra-wideband radar. This would enable many appli- [25] G. Demoment, “Image reconstruction and restoration: Overview
of common estimation structures and problems,” IEEE Transac-
cations in the areas of security, search and rescue, po- tions on Acoustics Speech and Signal Processing, vol. 37, December
lice/military, and others. 1989.
[26] J. Wilson and N. Patwari, “Radio tomographic imaging with
wireless networks,” tech. rep., University of Utah, Sensing and
Processing Across Networks Lab, 2008.
R EFERENCES
[1] M. Skolnik, Introduction to Radar Systems. McGraw Hill Book Co.,
1980.
[2] A. C. Kak and M. Slaney, Principles of Computerized Tomographic
Imaging. The Institute of Electrical and Electronics Engineers, Inc.,
1988.
[3] A. Hunt, C. Tillery, and N. Wild, “Through-the-wall surveillance
technologies,” Corrections Today, vol. 63, July 2001.
[4] D. Estrin, R. Govindan, and J. Heidemann, “Embedding the
Internet,” Communications of the ACM, vol. 43, pp. 38–41, May
2000.
[5] “Time Domain Corporation.” http://www.timedomain.com.
[6] “Cambridge consultants.” http://www.cambridgeconsultants.com.
[7] “Camero Tech.” http://camero-tech.com.
[8] A. R. Hunt, “Image formation through walls using a distributed
radar sensor network,” in SPIE Conference on Sensors, and Com-
mand, Control, Communications, and Intelligence (C3I) Technologies
for Homeland Security and Homeland Defense IV, vol. 5778, pp. 169–
174, May 2005.
[9] S. L. Coetzee, C. J. Baker, and H. Griffiths, “Narrow band high
resolution radar imaging,” in IEEE Conf. on Radar, pp. 24–27, April
2006.
[10] H. Griffiths and C. Baker, “Radar imaging for combating ter-
rorism,” NATO Advanced Study Institute, http://www. nato-us.
org/imaging2006/lecturers. html¿(Springer, 2006).
[11] M. C. Wicks, B. Himed, L. J. E. Bracken, H. Bascom, and J. Clancy,
“Ultra narrow band adaptive tomographic radar,” in 1st IEEE
Intl. Workshop Computational Advances in Multi-Sensor Adaptive
Processing, Dec. 2005.
[12] M. C. Wicks, “RF tomography with application to ground pene-
trating radar,” in 41st Asilomar Conference on Signals, Systems and
Computers, pp. 2017–2022, Nov. 2007.
[13] A. M. Haimovich, R. S. Blum, and L. J. C. Jr., “MIMO radar
with widely separated antennas,” IEEE Signal Processing Magazine,
pp. 116–129, January 2008.
[14] M. Youssef, M. Mah, and A. Agrawala, “Challenges: Device-
free passive localization for wireless environments,” in MobiCom,
(Montreal, Quebec, Canada), pp. 222–229, ACM, September 2007.
[15] N. Patwari and P. Agrawal, “Effects of correlated shadowing:
Connectivity, localization, and RF tomography,” in IEEE/ACM
Int’l Conference on Information Processing in Sensor Networks
(IPSN’08), April 2008.
[16] P. Agrawal and N. Patwari, “Correlated link shadow fading
in multi-hop wireless networks,” IEEE Transactions on Wireless
Communications, 2009. (Accepted for Publication).
[17] R. J. Bultitude, “Measurement, characterization, and modeling of
indoor 800/900 mhz radio channels for digital communications,”
IEEE Communications Magazine, vol. 25, June 1987.
[18] R. Ganesh and K. Pahlavan, “Effects of traffic and local move-
ments on multipath characteristics of an indoor radio channel,”
IEE Electronics Letters, vol. 26, no. 12, pp. 810–812, 1990.
[19] J. Roberts and J. Abeysinghe, “A two-state Rician model for
predicting indoor wireless communication performance,” in Com-
munications, 1995. ICC ’95 Seattle, ’Gateway to Globalization’, 1995
IEEE International Conference on, vol. 1, pp. 40–43 vol.1, 1995.