IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 63, NO.

16, AUGUST 15, 2015

4411

Sensor Selection and Precoding Strategies for

Wireless Sensor Networks
Alessandro Nordio, Member, IEEE, Alberto Tarable, Member, IEEE, Fabrizio Dabbene, Senior Member, IEEE, and
Roberto Tempo, Fellow, IEEE

AbstractSensor selection has recently received a growing interest in the literature, motivated by the worldwide deployment
of wireless sensor networks and by the increase in the number of
available applications. In our framework, sensors take remote measurements of a quantity of interest and communicate their observations through a noisy, multiantenna wireless communication link.
In this context, we propose a scheme for optimally selecting out
sensor nodes on the basis of the amount of information they
of
convey to a common receiver/actuator. Moreover, a suitable linear
precoder is employed and optimized at each transmitter with the
aim of maximizing the mutual information between the observed
variable and the signal received by the actuator. The sensor selection problem is known to be combinatorial, and several computable relaxations are available in the literature. In this paper,
the optimality conditions are formally expressed in an information-theoretic context, and both semi-denite-programming relaxations and greedy schemes, leading to computable techniques for
large values of and , are presented. Moreover, specic results
for the cases of high and low signal-to-noise ratio on the wireless
channel are derived. Numerical simulations show that knowledge
of the channel state at the transmitter may lead to an increase of the
achievable mutual information and determine a different choice of
sensors, thus pointing out that our approach signicantly improves
upon selection schemes that neglect the characteristics of the communication layer.
Index TermsChannel precoding, convex relaxation, green networks, mutual information, sensor selection, wireless sensor networks.

I. INTRODUCTION

IRELESS SENSOR NETWORKs (WSNs) and wireless sensor-and-actuator networks (WSANs) have
found applications in many elds, including trafc control,
weather forecast, pollution control, environmental monitoring
and surveillance, see for instance the surveys [1], [2]. In
WSNs/WSANs, the sensors measure a given physical variable
and transmit their observations to a processing center, sometimes coinciding with the network gateway, which processes
the received information.

Manuscript received June 27, 2014; revised February 20, 2015; accepted May
04, 2015. Date of publication June 01, 2015; date of current version July 09,
2015. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Y.-W. Peter Hong.
The authors are with IEIIT-CNR (Institute of Electronics, Telecommunications and Information Engineering of the Italian National Research
Council), Torino 10129, Italy (e-mail: alessandro.nordio@polito.it; alberto.tarable@polito.it; fabrizio.dabbene@polito.it; roberto.tempo@polito.it).
Color versions of one or more of the gures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Object Identier 10.1109/TSP.2015.2439239

The technology growth of recent years has allowed for a reduction in the production and deployment cost of sensors. As
a consequence, the number of deployed sensors is often larger
than needed for processing. On the other hand, the operational
cost of sensors is usually still rather large, due to battery consumption, especially in the signal transmission phase. To cope
with this issue, at xed time intervals, the processing center
needs to perform a sensor selection, with the aim of reducing
the number of transmitting sensors, while keeping the others in
sleep mode. This green-network strategy allows power saving
and increases the lifetime of sensor batteries.
Motivated by these issues, the literature considering the
problem of optimally selecting a subset of sensors from a set of
possible choices has received increasing interest. The interested
reader is referred to [3] for a survey on different schemes
currently used to select sensors, based on different kinds of
metrics (coverage, target-tracking and localization schemes,
single/multiple mission assignments). Clearly, whenever the
number of sensors is large, optimal selection becomes a computationally difcult combinatorial problem. Several approaches
have been proposed to obtain suitablerelaxations with the goal
of making the problem computationally feasible, even for a
moderate-to-large number of sensors.
For example, in [4] the sensor scheduling problem is reformulated as a nonlinear deterministic optimal control problem that
could be in principle attacked via a tree-search approach, but this
solution is generally impractical for a relatively large number of
sensors. The work [5] proposes a convex relaxation technique
to reduce the combinatorial problem to a convex programming
problem, which can be easily solved in polynomial time. The
most prominent advantages of this approach are its immediate
applicability, due to the powerful existing convex optimization
algorithms, and the possibility of handling various performance
criteria with energy and topology constraints. In [6], the case of
multistep measurements is considered, and the process state is
estimated by means of a Kalman lter with the goal of minimizing an objective function related to the Kalman lter error
covariance matrix.
An information-theoretic approach to sensor selection and localization in sensor networks for target tracking is studied in [7].
There, the problem of choosing a sensor from a set of candidates
is formulated, with the goal of minimizing the expected conditional entropy of the posterior target location distribution. In this
case, both the prior target location distribution and the locations
and observation models of the candidate sensors are assumed to
be known. In [8], [9], it is shown that the information gain is a
submodular function. This property allows to prove guaranteed

1053-587X 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

4412

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 63, NO. 16, AUGUST 15, 2015

lower bounds on the performance of a greedy selection scheme,

in which the sensor providing the larger performance gain is
added to the selected ones iteratively. In particular, the performance of a greedy algorithm is proved to be within a fraction
of
from the optimal one. In [10] the so-called budgeted
case is considered, in which a positive integer cost is associated
to each sensor. The paper presents a general algorithm for maximizing non-decreasing submodular functions under a budget
constraint with general (additive) costs, which still guarantees
the same optimality gap of
. A greedy selection algorithm is also proposed in [11], whose complexity scales linearly
with the total number of sensors.
It should be remarked that the approaches previously discussed assume that all sensors send their observations to
a centralized processing center. However, all these works
completely neglect the inuence of the wireless channel characteristics, which can largely affect the quality of the received
signal. This consideration is at the basis of the present work, in
which we demonstrate how optimal sensor selection strongly
benets from the knowledge of the channel characteristics, and
how a careful transmitter design should take into account the
statistics of the observations.
In order to carry out this task, we study a WSN composed of
sensors, transmitting signals to a common receiver through
multiple antennas. We explicitly consider the inuence of the
communication channel characteristics on the sensor selection
problem and we assume that sensors communicate by using
orthogonal channels, so that they do not interfere with each
other. Among the total of
received signals, the receiver has
to choose , (
) according to some optimality criterion.
To formally dene this criterion, we follow an information-theoretic approach. In particular, we adopt as objective function of
the wireless sensor selection problem the mutual information
between the measured variable and the set of selected signals.
Such mutual information is maximized by employing at each
node an optimal linear precoder. This scenario is also considered in our previous work [12]. However, in [12], the sensors
do not employ precoders to optimize the amount of information
conveyed to the receiver/actuator. The addition of suitably optimized precoders proves to be crucial in the considered framework.
Signal precoding for multiantenna systems is a widely investigated technique, which has also been implemented in many
commercial applications (see [13] and references therein).
The idea is to process the information to be transmitted by
exploiting the knowledge of the communication channel. In
particular, linear precoding techniques are the most commonly
used, thanks to their low complexity and their optimality from
the information-theoretic point of view. In our scenario, sensor
precoding is akin to relay precoding in amplify-and-forward
relay communication systems, for which optimal precoding
is derived in [14]. There, however, a single-relay network is
considered, while in our case multiple sensor nodes perform
linear precoding. In [15], joint precoder optimization in a
network of multiple nodes transmitting correlated signals is
considered. However, in our scenario, sensor node inputs are
affected by independent noise samples, and this makes the joint
precoder optimization of [15] not applicable. The main novelty
of the precoders proposed in this paper is that they take into

specic account the available information on the remote sensor

characteristics.
In summary, the contributions of our work are:
the formulation of the sensor selection problem in presence of a multiple-input multiple-output (MIMO) wireless channel with channel state information available at the
transmitters (CSIT);
introduction and optimization of precoders taking into specic account sensor characteristics, by using an information-theoretical approach;
relaxation of the optimization problem to a suboptimal
semidenite program (SDP) [5] and approximation
through a greedy algorithm;
analysis of the cases of high and low signal-to-noise ratio
(SNR) on the wireless links;
numerical assessment of the impact of sensor selection parameters and of the inuence of CSIT on the system performance.
The rest of the paper is structured as follows. Section II describes in detail the considered scenario. In Section III, we
derive locally optimal linear precoders for sensor nodes.
In Section IV, we formulate the problem of optimal sensor
selection for our scenario. In Section V, we describe suboptimal solutions based on relaxation and greedy search. In
Section VI, we consider the limit regimes for high and low
received signal-to-noise ratio (SNR) on the wireless channel.
In Section VII, we compare the proposed sensor selection
algorithms by means of numerical simulations and we also
assess the impact of the precoders on the performance. Finally,
in Section VIII, we draw some conclusions.
II. SYSTEM MODEL
We consider the scenario where we are interested in estifrom the observations
mating an unknown vector1
sensing devices. This approach is similar to
performed by
the one discussed in [5] and subsequent works. However, differently from these works, we here consider the more realistic
situation where the sensing devices act remotely, and their observations are to be sent to a common receiver through a wireless channel.
Each sensing device performs a different observation of the
linear measurements corrupted by
quantity , and obtains
additive noise, which can be written as

and
is the -th observation
where
is a vector of size
(different for each sensor). The meamatrix of size
surement noise vectors are modeled as independent Gaussian
,
random variables with zero mean and covariance matrices
. Similarly, we assume that the quantity is a
Gaussian random vector with zero mean and covariance matrix
.
As summarized in Fig. 1, in the setup considered in this paper,
the sensors have to transmit their observations through a wireless channel, and are hence equipped with transmit antennas.
1Throughout the paper, uppercase and lowercase boldface letters denote matrices and vectors, respectively. The identity matrix is denoted by , and
denotes the determinant of the matrix .

NORDIO et al.: SENSOR SELECTION AND PRECODING STRATEGIES FOR WIRELESS SENSOR NETWORKS

4413

III. PRECODER OPTIMIZATION

The precoders represent free variables of the system. Usually, they are designed in order to maximize a suitable cost
function. In our case, we are interested in the amount of information about the unknown that the sensors convey towards
the receiver, under the transmit power constraints in (1). Indeed, by maximizing the information transfer, we allow the receiver to form better estimates of . The information-theoretical
concept of mutual information [16] between two random variables provides us with the suitable quantitative measure. Theremaxifore, our aim is to nd the optimal precoding matrix
. Such optimal precoder
mizing the mutual information
can be obtained by solving the following constrained maximization problem

Fig. 1. Wireless sensor.

To optimize transmission, the observation

is rst precoded
and then sent to the antennas. In other words,
by the matrix
where the prethe transmitted signal is given by
are
matrices. Due to limited sensor energy,
coders
the average power irradiated by the transmitter of the -th sensor
is assumed to be bounded by , i.e.,

(5)
denotes the mutual information between and
where
, conditioned on the knowledge of
and . For Gaussian
is dened as
random variables
(6)

(1)
The sensing devices transmit their (precoded) signals to a
common processing center, which consists of a wireless receiver equipped with
antennas. Signals are assumed to be
transmitted over MIMO orthogonal channels, so that they do
not interfere with each other. The signal received by the processing center from the -th sensor is then given by

where
and
are
, respectively. Also, the
the covariance matrices of and
symbol in (6) denotes conditioning. It follows that the mutual
can be written as
information

(2)
where the
matrix
represents the -th MIMO channel
represents additive noise, assumed independent of ,
and
and modeled as a complex Gaussian random vector with zero
. More specically, the
-th
mean and covariance matrix
is the gain of the link connecting the
entry of the matrix
-th transmit antenna to the -th receive antenna. In the case
all sensors transmit, the received signals can be arranged in the
, of size
, given by
vector
..
.

..
.

..
.

where in the third line of (7) we used the property

(Sylvesters theorem) and in the last
and
. Then the
equality we dened
term
in (7) can be rewritten as follows

(3)

,
We dene the matrices
, and
. Note that and
are block-diagonal of size
and
respectively, and is of size
. Then, we can rewrite
where
(3) more compactly as
and
collect the measurement noise and the thermal noise, respectively. The equivalent
noise at the receiver is represented by the random vector
, which has covariance matrix

and

(7)

(8)

(4)

where in the rst equality we used the expression for

given
in (4), and in the second equality we applied the matrix inversion
,
lemma [17] (i.e.,
where
and
). Moreover, in (8) for
the sake of simplicity we dened
. The
last equality of (8) comes from the fact that
. By joining the
results in (7) and (8) the mutual information can be rewritten as

is the covariance matrix of .

(9)

4414

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 63, NO. 16, AUGUST 15, 2015

By denition the covariance matrix

is block-diag,
is also block-diagonal with
onal with blocks
and
where
blocks
. Then,
is also block-diagonal with
blocks
(10)
As for the transmit power constraint in (1), we have

where
,
, and
are obtained from
the matrices
the eigenvalue decomposition of the Hermitian matrices
and
, i.e.,
and
;
the eigenvalues are ordered in decreasing order, i.e,
where
and
where
;

is an
rectangular diagonal matrix whose diagonal elements are given by
(15)

(11)
Then, the maximization problem in (5) can be rewritten as

(12)
where
. We observe that the solution
of the above problem involves a joint optimization of all pre,
coders. In general, the optimal precoder for the -th sensor,
and
, but rather depends on the
is function not only of
and . This follows from the fact that the
whole matrices
does not have a block-diagonal structure and the
matrix
cost function in (12) cannot be written as a sum of terms, each
depending on the parameters of a single sensor. Thus, the computation of the optimal precoder, , requires the knowledge of
the matrices and at every sensor. This assumption is however unrealistic in our case since it would require an intensive
exchange of information among sensors.
We then resort to a locally optimal solution: instead of
, we compute the precoder
nding the optimal precoder
where
is obtained by solving the
local maximization problem

, where

and
. Moreover
, and the parameter
is chosen so that
.
The expression of the locally optimal precoder in (14) has
the following intuitive explanation: the purpose of the unitary
and
is to rotate the channel and observation
matrices
matrices, respectively, in order to allow the precoder to act
directly over the system eigenvalues. The term
normalizes to unity the average power of the signal
, and
shares the available power,
, among
the diagonal matrix
the available channel modes. The proof of (14) is given in
Appendix A. Expressions for the locally optimal precoder in
the high- and low-SNR regimes are derived in Section VI.
IV. SENSOR SELECTION PROBLEM
As discussed in Section I, we are interested in selecting a
maximizing
suitable subset of sensors of cardinality
an appropriate performance metric, i.e, in our case, mutual information. In practice, to estimate the quantity , the processing
available, at
center makes use of sensors only, out of the
the advantage of a lower complexity and energy saving. Clearly,
better estimates can be obtained if the amount of information
contained in the selected signals is larger.
Mathematically, the sensor selection problem can be formalselection matrix , which
ized by introducing a
left-multiplies the vector . This matrix is formed by
sub-blocks of size
each, and the
-th block of ,
, is dened as
if sensor is the -th selected sensor
otherwise

(13)
. In (13) we recalled the denition of
for
given in (10). We moreover observe that the dependence on
can be found only in the term
. Then, solving the
the mutual
above problem is equivalent to maximize over
information
at each sensor, and the solution,
, does
and
for
. Therefore no exchange of
not depend on
information among sensors is required.
Proposition 1: The locally optimal precoder
that maximizes the problem in (13) is given by
(14)

and
. Also has the following
for
, there exists one and only
properties: i) for each
, and ii) for each
,
one index such that
.
there is at most one index such that
In particular, i) guarantees that exactly sensors are selected,
while ii) ensures that sensors are selected no more than once.
With this notation dened, the optimal sensor selection can be
formulated as the following problem.
Problem 1 (Wireless sensor selection): Based on the knowledge of sensor characteristics (i.e., measurement matrices
and measurement noise covariance matrices
,
), and of the wireless communication channels
,
and thermal
(i.e., transmission matrices

NORDIO et al.: SENSOR SELECTION AND PRECODING STRATEGIES FOR WIRELESS SENSOR NETWORKS

noise variance
), the problem of choosing the selection
, can
matrix that maximizes the mutual information
be formulated as:

Finally, by substituting (20) in (19), we obtain that the mutual

information
can be expressed as
(21)

(16)
where denotes the received signal in the case the optimal
precoders
have been designed according to (14), i.e.,
where
and
. The mutual information obtained by an optimal choice of
. In the
signals received from sensors is thus given by
next section we show how this problem can be reformulated in
terms of the notation introduced so far.

4415

This observations allow us to state the next proposition, which

provides a useful reformulation of the optimal sensor selection
problem in terms of the Boolean selection vector .
Proposition 2 (Optimal wireless sensor selection): The optimal selection vector that maximizes the mutual information
is given by the solution of the following optimization
problem

A. Problem Reformulation
Since and are Gaussian random variables we rst rewrite
as
the mutual information
(17)
where
and
are,
and
, and where
respectively, the covariance matrices of
denotes the covariance matrix of . Thus (17) rewrites

(18)
It is important to observe that, by construction, the covariance matrix
has a block-diagonal structure with blocks of
. Such a property is due to the fact that both
size
and
are block-diagonal matrices. Therefore we can write
whence it follows that the mutual
information (18) can be rewritten as

(19)
where in
we have applied Sylvesters theorem, and in
we dened
, we exploited the fact that the matrix
is idempotent (i.e.,
) and that, because of the block-diagonal structure of
,
. Note also that is
block-diagonal matrix with blocks
.
a
Specically the -th block of , , can be written as
where
,
, are Boolean variables. It
turns out that the sensor selection problem can be reformulated
deby introducing the Boolean selection vector
where
means that the -th
ned as
is
sensor has been selected. It follows that the matrix
where
block-diagonal and its -th block is given by
is the -th diagonal block of
and is given by

(22)
where
is dened in (20), and
denotes the -norm,
equal to the number of nonzero elements in .
Remark 1: Note that the problem formulated in Proposition
2 can be solved based solely on the knowledge of the quantities
,
,
,
, , and thus can be solved prior to performing the actual measurements, thus allowing to switch off
sensors that are not selected. This will permit an
the
optimization of the energy resources.
In the next Section, we show relaxations and greedy algorithms aiming at reducing the complexity of the sensor selection
problem in Proposition 2.
V. SENSOR SELECTION ALGORITHMS
The solution of the optimal wireless sensor selection problem
formulated in Proposition 2 amounts at solving a hard nonconvex optimization problem, due to its intrinsic combinatorial
nature. In principle, a solution would require the evaluation of
possible selections
the performance index for each of the
of active sensors. Specic branch-and-bound techniques, in the
spirit of [18], [19], can be devised for the numerical solution
of this problem, but this approach is clearly not practical unare relatively small. In the other cases, different
less and
approximations or relaxations are possible, as discussed in the
next subsections.
A. Concave Relaxation
A computable continuous relaxation of the optimization
problem (22) can be immediately obtained by relaxing the
requirement that the selection vector is to be binary. In fact,
is concave for
the cost function
. This approach, analogous of that introduced in [5],
leads to the following semidenite program (SDP)

(23)
Thus

where

(20)

Note that, in the above maximization problem, the -norm is

replaced by the -norm. This is a standard technique employed
in optimization to derive convex relaxations for combinatorial

4416

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 63, NO. 16, AUGUST 15, 2015

problems, and has been applied, e.g., in the context of compressive sensing in [20]. The complexity of this SDP algorithm
, and hence it can be applied also to rather large
scales as
networks. In general, the optimal solution of this SDP relaxation will take fractional values, so that some kind of sorting
and rounding is necessary to obtain the desired solution. The
simplest approach consists in selecting the elements of
with the largest values. A more sophisticated technique, which
leads to better solutions, consists in applying an iterative procedure, where each iteration solves a reweighted -problem. This
procedure has been suggested in [21] to enhance the sparsity of
the solution of a -minimization problem, and is summarized
in Algorithm 1.

1) 1) Initialization:
,
2) 2) Solve the weighted SDP relaxation:

larger than
, GOTO 2.

In Algorithm 1 at step the weights

are updated to give
, in order to force
more importance to the smallest values of
their values towards zero. For a formal analysis of the algorithm
at step 3) is
the reader is referred to [21]. The parameter
introduced in order to provide stability and to ensure that a zerodoes not strictly prohibit a nonzero
valued component in
. In particular, in [21] it is suggested to
component at step
select slightly smaller than the expected nonzero magnitudes
of the components of , but the algorithm is rather robust to this
choice.
B. Greedy Algorithm
In this section, we study the properties of a greedy selection scheme providing an approximated solution of the problem
described in Proposition 2. The greedy algorithm consists in
choosing the sensors one at a time, until sensors are nally
), the selected sensor
selected. At the -th step (
is the one maximizing the objective function when combined
. Formally, we rst note that
with the previously chosen
the objective function in (22) can be rewritten as the following
set-function2}
(24)
where is a set of sensors. The greedy sensor selection algorithm is described in Algorithm 2.
2A

1) 1) Initialization:
,
,
2) 2) Select greedily the next sensor:
(25)
3) 3) Update the selected measurement set:
(26)
4) 4) Set

, IF

GOTO 2.

The use of Algorithm 2 in the context of sensor selection has

been originally proposed in [11], [22], where its suboptimality
properties are discussed in details, based on the concept of submodularity. Submodularity plays for discrete functions the same
role as convexity for continuous functions, see e.g. the survey
[23], and has been leveraged in various problems in the contexts
of optimal sensor placement [24] and leader selection [25].
Definition 1 (Submodular function): For a given nite set ,
, where
denotes the power set, is
a set-function
, and for any
said to be submodular if for any
, it holds

Algorithm 1: Reweighted SDP Relaxation

3) 3) Update the weights:

4) IF
OR the number of elements of
is equal to then EXIT; ELSE set

Algorithm 2: Greedy Sensor Selection

set-function is dened as a function whose input is a given set

(27)
In other words, a submodular function satises the so-called
diminishing increments property. The submodular function is
,
.
monotone if
The importance of the submodularity stems from the results
proven in [26], where the authors study the problem of maximizing a monotone submodular function under a simple cardinality constraint, that is
(28)
They prove that the solution of the greedy procedure applied to
times the optimal
problem (28) is not less than
one. Since the mutual information in (21) is a submodular function [23], an immediate application of Denition 1 provides the
following lemma.
Lemma 1 (Suboptimality of the greedy algorithm): Let
be the mutual information obtained by solving Algorithm 2 and
let be the mutual information achieved by the optimal solution
of (22). Then,

It should be remarked that in [26], [27] it is also shown that

the performance of the greedy algorithm is the best practi. Indeed, they show that no
cally achievable, unless
polynomial-time algorithm can provide a better bound than
. This consideration motivates our choice of adopting
the greedy algorithm in the solution of the numerical examples
bound does
in Section VII. On the other hand, the
not hold for more general constraints than the cardinality one
considered here, and specically tailored algorithms have to be
devised, see e.g. the works [9], [10] that consider budget-type
constraints. In this latter case, the use of the SDP relaxation,

NORDIO et al.: SENSOR SELECTION AND PRECODING STRATEGIES FOR WIRELESS SENSOR NETWORKS

where such constraints can be included in the problem almost

for free, can become competitive.

where

4417

has rank . It follows that

. Thus, for
, (9) be-

comes
VI. HIGH- AND LOW-SNR REGIMES
In this section, we consider two particular scenarios for
which the sensor selection problem considerably simplies, i.e., the cases of high and low SNR on the wireless
channel. More precisely, the high-SNR regime is dened
, while the low-SNR regime corby the condition
. For the whole section, let the
responds to
eigenvalue decompositions of
and
be, respecand
tively,
where

and
.

A. High-SNR Regime
We start from the high-SNR regime and assume that
,
. This condition can be
, and supposing that
obtained by choosing
are all full rank: the latter assumption
the channel matrices
is physically common both in the case when the receiver is in
line of sight, provided that it is not exceedingly far from the
transmitter, and when the receiver is not in line of sight, in
presence of a rich-scattering propagation environment. With
such hypotheses, we can prove that optimal sensor selection be,
,
comes independent of the channel matrices
and boils down to the same problem of, e.g., [5]. As a direct
consequence, in the high-SNR regime it is inessential to precode the transmitted signals.
,
Proposition 3(High-SNR regime): If
, then, for
, the mutual information
does not depend anymore on the channel realizations. More precisely, the optimal sensor selection problem dened in (22) can
be rewritten as

(29)
Proof: Under the hypotheses of the theorem, from (15) we
see that, for
, the optimal precoder for the -th sensor
satises

is a constant needed to satisfy

where
substituting the above values into (14), we obtain

(30)
. By
(31)

is the diagonal matrix of the

largest eigenvalues
. In turn, this can be substituted into (10), where
, yielding
.
Now, suppose that
has rank
. As a consequence,
we have that, for
where
of

(32)

(33)
which does not depend on the channel matrices .
Next, we derive the expression of the optimal sensor
selection problem in the high-SNR regime. We rst oband any nonzero constant ,
serve that for any matrix
. Thus the term
in (20) can be rewritten as
where
is given in (10) and
. By substituting this result into (20) we obtain,
for

(34)
Substituting the above expression into (22), we obtain (29).
The fact that, in the high-SNR regime, the optimal sensor selection does not depend on channel realizations has a great practical importance. Indeed, the problem (29) can be solved once
at the beginning and can be used whenever the channels are in
good conditions, without the need for changing the selection according to channel time variations. However, notice that the receiver must know the channel realizations for the selected nodes
in order to properly exploit the received signals.
full rank will
Notice also that any precoder that makes
give the same mutual information as in (33) for
. Even
, the rewithout precoding, i.e., with a choice like
sulting mutual information would be the same as in the case of
optimal precoding. Seeing the overall channel from to as a
cascade of the measurement channel from to and the comsaturates
munication channel from to , at high SNR
, and the sensor selection problem becomes equivato
lent to the one treated in [5].
B. Low-SNR Regime
In the next proposition, we consider instead the low-SNR
regime and we show that, in such case, the cost function to be
maximized is a linear combination of the contributions of each
sensor.
, the optimal
Proposition (Low-SNR regime): If
sensor selection problem in (22) reduces to

(35)

4418

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 63, NO. 16, AUGUST 15, 2015

Proof: It is shown in Appendix B that, for large , all

dened in (15) eventually reach zero but the rst. Thus, for
, we obtain
otherwise

(36)

In words, beamforming in the direction of the best parallel

channel is the optimal precoding strategy in the low-SNR
regime, as it is usual for waterlling power allocation.
Regarding the mutual information given in (19), we observe
,
. Under this condition (19)
that, for
becomes
Fig. 2. (Top) Achievable mutual information versus SNR for the optimal
sensor selection algorithm and its counterparts designed for high-SNR and
low-SNR regimes. (Bottom) Sets of sensors selected by the optimal algorithm,
for different SNR (circle markers), and by its low- and high-SNR counterparts
(triangle markers).

(37)
where we have used the fact that for
,
, and
. The trace
in (37) can be written as

(38)
where we have used the expression of the optimal precoder in
(14) and the value of
in (36). Substituting (38) into (37) and
operator the constant terms innoticing that under the
dependent of can be removed, we nd that the optimal sensor
selection can be written as in (35).
The locally optimal precoder can be computed by observing
that the problem in (35) can be easily solved by a greedy algorithm that takes the largest values of

. Unlike the high-SNR case, however, the soluand thus must be

tion does depend on the channel matrices
recomputed every time the channel realizations change. Moreover, the value of can be interpreted as the total useful power
reaching the receiver from the -th sensor.
VII. NUMERICAL RESULTS
In this section, through computer simulations, we assess the
performance of the different sensor selection algorithms and we
evaluate the impact of the precoder on the achievable mutual
information. In our tests, sensors are chosen out of a total set
of
. The variable under control has length
. We
, except otherwise stated. Each sensor performs
assume
scalar measurements and transmits through
antennas. The receiver is equipped with
antennas. The

Fig. 3. Comparison among sensor selection algorithms in terms of achievable

mutual information versus SNR, with and without precoder. Average over 100
channel realizations.

measurement noise vectors have covariance matrices

,
. In each simulation, the matrices
,
, are kept xed and their (real) entries are drawn from
a normal distribution.
,
, are i.i.d. comThe entries of the matrices
plex circularly Gaussian with zero-mean and unit-variance, as it
is the case when the sensors transmit through Rayleigh-fading
channels.
To assess the benet of precoding, we compare the case where
is chosen to be equal to the locally optimal precoder
dened in (13) (or its counterparts for high or low SNR) with
. In all cases, the average
the no-precoder case, i.e.,
,
transmitted power of sensor is set to
. The signal-to-noise ratio of every wireless channel is
.
therefore
In a rst test, we concentrate on the benets of the optimal
sensor selection of Proposition 2. To this end, we set
and we keep xed the set of
s and the corresponding locally
optimal precoder for the whole simulation.
The results are depicted in Fig. 2, where we also show the
mutual information achieved by the high-SNR and low-SNR
approximations of optimal selection, as dened in Propositions
3 and 4, respectively. In the lower part of Fig. 2, we show the
sets of sensors selected by each algorithm as a function of SNR.
As it can be seen, the performance of the algorithm adapted
to the low-SNR regime and described in Proposition 4 merges

NORDIO et al.: SENSOR SELECTION AND PRECODING STRATEGIES FOR WIRELESS SENSOR NETWORKS

4419

Fig. 4. Outage probability plotted vs. SNR for 5.5 bit threshold mutual information (a), and plotted vs. the threshold mutual information for
and
.
In both gures

with the performance of the optimal selection scheme for SNRs

not larger than 0 dB, while it exhibits bumps for medium SNR
values due to the fact the low-SNR selection rule is suboptimal.
For high SNR, the low-SNR algorithm reaches an asymptotic
value of about 6.5 bits, which is more than 1 bit lower than the
maximum achievable mutual information. The high-SNR algorithm of Proposition 3 merges with the optimal selection for
, while it loses up to 1 bit of mutual information for medium SNR values. There are barely perceptible slope
changes in the optimal selection curve in correspondence with
changes in the set of selected sensors. It can be observed that,
, the optimal selection signicantly differs
for
from the choice made neglecting the effect of the transmission
channel. For instance, for SNR around 10 dB the optimal choice
corresponds to sensors 2, 17 and 20, while the choice made neglecting the channel would be 1, 8 and 13, corresponding to a
loss of about 0.4 bits.
In a second test shown in Fig. 3 we compare the mutual information achieved by the optimal sensor selection of Proposition 2, the reweighted convex relaxation of Algorithm 1 and the
greedy sensor selection of Algorithm 2. We also evaluate the
benet of introducing the locally optimal precoder, by considering the cases with and without signal precoding. To this end,
and we average over 100 Rayleigh-fading channel
we set
realizations. We here consider the case where the entries of
are correlated. To this end in this test the covariance matrix of
is kept xed and drawn from a Wishart distribution. As it can
be seen, the precoder yields a gain of almost 2 dB at low SNR,
while for sufciently high SNR the gain in terms of mutual information provided by the optimal precoders tends to be negligible. In both scenarios, the two approximated algorithms perform almost as well as the optimal sensor selection for low SNR,
while they become slightly suboptimal for larger SNR, losing
about 0.2 bits w.r.t. optimal performance. Among the two suboptimal solutions, concave relaxation has a slightly better performance for medium SNR values than greedy sensor selection,
although the gain is always lower than 0.1 bits. Considering that
concave relaxation still exhibits a larger complexity than greedy
sensor selection, our conclusion is that the latter represents the
better trade-off between algorithm complexity and achievable
mutual information.
In the next two tests, we investigate more in detail the performance of the greedy algorithm and in particular we derive
its outage probability which is dened as the probability that

(b).

the achieved mutual information is below a given threshold. We

compare in terms of outage probability the cases where locally
optimal precoders and no precoders are used. In addition, we
consider a suboptimal precoder which neglects the information
about the sensors matrices. This precoder maximizes
, are uncorreby assuming that the signals ,
lated. The expression of this suboptimal precoder is given by
where the -th diagonal element of

is

given by
where
is a constant allowing
is the -th eigenvalue of
. In
for power normalization and
Fig. 4(a), we show the outage probability versus SNR for a mutual information threshold equal to 5.5 bit, while in Fig. 4(b) we
depict the outage probability versus the threshold on the mutual
. In both gures, we observed
information for
10000 channel realizations per point and we selected
sensors out of a total of
.
provides a
As it can be seen from Fig. 4(a), the choice
in terms of both
signicant gain with respect to the case
SNR and decay slope. In general, the decay slope increases with
due to the diversity effect provided by the channel matrices,
which are assumed to be independent. For all considered values
of , the locally optimal precoder can save up to 3 dB of SNR
w.r.t. the case where no precoder is employed, at an outage prob. Instead, the suboptimal precoder loses 12 dB
ability of
there is a further gain
against the no-precoder case. For
, at the price
of about 45 dB with respect to the case
of a small increase in the complexity of the greedy algorithm.
These results clearly show the impact of the precoder on the performance of sensor selection and that a careful precoder design
cannot neglect the information on the sensor matrices.
In Fig. 4(b), the outage probability provided by the greedy seand
is depicted
lection algorithm for
as a function of the threshold mutual information. In this case,
an increase of from 2 to 3 yields a gain of about 1.5 bits at
, while a further increase of to 4
an outage probability of
provides an additional gain of more than 1 bit, for all considered
precoder optimization entails
precoders. Notice that for
a gain of almost 1 bit.
VIII. CONCLUSIONS
In this paper, we studied the sensor selection problem in the
case where the observations are transmitted through noisy wireless MIMO channels. At each transmitter we employed and op-

4420

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 63, NO. 16, AUGUST 15, 2015

timized linear precoders in order to maximize the information

conveyed to the processing center. The optimality conditions
have been derived in an information-theoretic framework. The
numerical simulations clearly demonstrate how optimal sensor
selection strongly benets from the knowledge of the channel
characteristics, and how precoder design should take into account the structure of the sensor matrices. This testies for the
importance of the aggregate framework proposed in this paper,
which considers simultaneously the sensor and the channel characteristics. Further studies will consider the problem of remote
Kalman ltering in the same wireless context. Finally, the possibility of introducing additional constraints in the choice of the
sensors can be considered, as in [28].
APPENDIX A
PROOF OF PROPOSITION 1
In order to solve (13) we rst consider the eigenand
value decompositions
, where
and
are unitary
matrices. We also assume that the eigenvalues are ordered
where
in decreasing order, i.e,
and
where
. By following the same steps as in [14] we
dene the arbitrary
matrix
such that
is given by
(39)
By using (39) in (10) the matrix

APPENDIX B
PRECODER OPTIMIZATION IN THE LOW-SNR REGIME
To prove that for
the result in (36) holds we rst regiven in (15). Also, we remind that
call the solution for
and
appearing in (15) are the
and
, respectively, sorted in deeigenvalues of
creasing order. We start by noticing that for any value of ,
if
(42)
After some elementary manipulations, such condition can be
written as
where
,
.
and
Notice that, since
, then also
. From
what we have said, it follows that there are exactly nonzero
if and only if
precoder gains
. Now suppose that
and that
, i.e., only the
rst precoder gain is nonzero. As a consequence, we have:
(43)
where the second equality comes from the power normalization.
gives
Solving for
(44)

is given by
and the

constraint in (13) reduces to

. Then, by substituting these results in (13)
and after some algebra, we can show that the problem in (13)
is equivalent to nding the matrix
solving the following
problem [14]

(40)
, it has been shown in [14]
For the case of a square matrix
is diagonal. Even though in our case
is
that the optimal
rectangular, the same result applies. In particular the diagonal
, are given by
elements of

where
and
.
This result can be obtained by following the same steps as in
[14, Section III] and generalizing for the case of a rectangular
. For a diagonal
(40) takes the form

(41)
The value of the variables
solving (41) can be obtained by
applying the Karush-Kuhn-Tucker conditions, as done in [14],
and is given by (15).

It is easy to verify that

is a continuous, strictly
with
increasing function of
and
. Because of that, and since
, there will be a value of , call it , for which
. It follows that, for all
, only the rst
precoder gain is nonzero.
REFERENCES
[1] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, A survey
on sensor networks, IEEE Commun. Mag., vol. 40, no. 8, pp. 102114,
2002.
[2] J. Yick, B. Mukherjee, and D. Ghosal, Wireless sensor network
survey, Comput. Netw., vol. 52, no. 12, pp. 22922330, 2008.
[3] H. Rowaihy, S. Eswaran, M. Johnson, D. Verma, A. Bar-Noy, T.
Brown, and T. L. Porta1, A survey of sensor selection schemes in
wireless sensor networks, SPIE, vol. 6562, p. 65621A, 2007.
[4] L. Meier, J. Peschon, and R. Dressler, Optimal control of measurement subsystems, IEEE Trans. Autom. Control, vol. 12, no. 5, pp.
528536, 1967.
[5] S. Joshi and S. Boyd, Sensor selection via convex optimization, IEEE
Trans. Signal Process., vol. 57, no. 2, pp. 451462, 2009.
[6] Y. Mo, R. Ambrosino, and B. Sinopoli, Sensor selection strategies
for state estimation in energy constrained wireless sensor networks,
Automatica, vol. 47, pp. 13301338, 2011.
[7] H. Wang, K. Yao, and D. Estrin, Information-theoretic approaches for
sensor selection and placement in sensor networks for target localization and tracking, J. Commun. Netw., vol. 7, no. 4, pp. 438449, Dec.
2005.
[8] A. Krause and C. Guestrin, Near-optimal value of information in
graphical models, presented at the Conf. Uncertainty Artif. Intell.
(UAI), Edinburgh, Scotland, U.K., Jul. 2629, 2005.
[9] A. Krause and C. Guestrin, Optimizing sensing: From water to the
web, IEEE Comput. Mag., vol. 42, no. 8, pp. 3845, 2009.
[10] M. Sviridenko, A note on maximizing a submodular set function subject to knapsack constraint, Oper. Res. Lett., vol. 32, pp. 4143, 2004.
[11] M. Shamaiah, S. Banerjee, and H. Vikalo, Greedy sensor selection
under channel uncertainty, IEEE Wireless Commun. Lett., vol. 1, no.
4, pp. 376379, 2012.

NORDIO et al.: SENSOR SELECTION AND PRECODING STRATEGIES FOR WIRELESS SENSOR NETWORKS

[12] A. Nordio, A. Tarable, and F. Dabbene, Optimal sensor selection

strategies in the presence of wireless communication links, presented
at the 19th World Congr. Int. Federation Autom. Control (IFAC), Cape
Town, South Africa, Aug. 2429, 2014.
[13] M. Vu and A. Paulraj, MIMO Wireless Linear Precoding, IEEE
Signal Process. Mag., vol. 24, no. 5, pp. 86105, Sep. 2007.
[14] X. Tang and Y. Hua, Optimal design of non-regenerative MIMO
wireless relays, IEEE Trans. Wireless Commun., vol. 6, no. 4, pp.
13981407, 2007.
[15] J. Fang, H. Li, Z. Chen, and Y. Gong, Joint precoder design for distributed transmission of correlated sources in sensor networks, IEEE
Trans. Wireless Commun., vol. 12, no. 6, pp. 29182929, Jun. 2013.
[16] D. MacKay, Information Theory, Inference and Learning Algorithms. New York, NY, USA: Cambridge Univ. Press, 2002.
[17] R. Horn and C. Johnson, Topics in Matrix Analysis. Cambridge, U.K.:
Cambridge Univ. Press, 1991.
[18] E. Lawler and D. Wood, Branch-and-bound methods: A survey,
Oper. Res., vol. 14, pp. 699719, 1966.
[19] W. Welch, Branch-and-bound search for experimental designs based
on D-optimality and other criteria, Technometrics, vol. 24, no. 1, pp.
4148, 1982.
[20] D. Donoho, Compressed sensing, IEEE Trans. Inf. Theory, vol. 52,
no. 4, pp. 12891306, 2006.
[21] E. Cands, M. Wakin, and S. Boyd, Enhancing sparsity by reweighted
minimization, J. Fourier Anal. Appl., vol. 14, pp. 877905, 2008.
[22] M. Shamaiah, S. Banerjee, and H. Vikalo, Greedy sensor selection:
Leveraging submodularity, presented at the IEEE Conf. Decision
Control, Atlanta, GA, USA, Dec. 1517, 2010.
[23] A. Krause and D. Golovin, Submodular function maximization, in
Tractability: Practical Approaches to Hard Problems (to appear).
Cambridge, U.K.: Cambridge Univ. Press, Feb. 2014.
[24] A. Krause, R. Rajagopal, A. Gupta, and C. Guestrin, Simultaneous optimization of sensor placements and balanced schedules, IEEE Trans.
Autom. Control, vol. 56, no. 10, pp. 23902405, Oct. 2011.
[25] A. Clark, L. Bushnell, and R. Poovendran, A supermodular optimization framework for leader selection under link noise in linear
multi-agent systems, IEEE Trans. Autom. Control, vol. 59, no. 2, pp.
283297, 2014.
[26] G. Nemhauser, L. Wolsey, and M. Fisher, An analysis of the approximations for maximizing submodular set functions, Math. Programm.,
vol. 14, pp. 265294, 1978.
[27] A. Krause, A. Singh, and C. Guestrin, Near-optimal sensor placements in Gaussian processes: Theory, efcient algorithms and empirical studies, J. Mach. Learn. Res., vol. 9, pp. 235284, 2007.
[28] Y. Wang, M. Sznaier, and F. Dabbene, A convex optimization approach to worst-case optimal sensor selection, presented at the IEEE
Conf. Decision Control, Firenze, Italy, Dec. 1013, 2013.

Alessandro Nordio (S00M03) is a Researcher

with the Institute of Electronics, Computer and
Telecommunication Engineering of the Italian
National Research Council. In 2002 he received
the Ph.D. in Telecommunications from Ecole
Polytechnique Federale de Lausanne, Lausanne,
Switzerland. From 1999 to 2002, he performed
active research with the Department of Mobile
Communications at Eurecom Institute, Sophia
Antipolis (France). From 2002 to 2009 he was a
post-doc researcher with the Electronic Department
of Politecnico di Torino, Italy. His research interests are in the eld of signal
processing, wireless sensor networks, theory of random matrices, and crowdsourcing systems.

4421

Alberto Tarable (S00M02) received the Laurea

degree (summa cum laude) in 1998 and the Ph.D.
degree in Electronic Engineering in February 2002,
both from Politecnico di Torino. From 2002 to 2012,
he worked as a researcher in the Department of
Electronics and Telecommunications of Politecnico
di Torino. From 2012, he holds a research position in
the Institute of Electronics, Computer and Telecommunication Engineering of the Italian National
Research Council. His research interests include
MIMO systems and space-time coding, anytime
coding and coding schemes for relay channels.

Fabrizio Dabbene (M02SM09) is currently

Senior Researcher at CNR-IEIIT, Torino, Italy.
He received the Ph.D. in Systems and Computer
Engineering in 1999 from Politecnico di Torino.
His research interests include probabilistic and
randomized methods for systems and control, robust
control and identication of complex systems,
convex optimization and modeling of environmental
systems. On these topics, he has published more
than 80 research papers, which include 30 articles
published in international journals a monograph
and an edited book. Dr. Dabbene has been an Associate Editor for the IEEE
TRANSACTIONS ON AUTOMATIC CONTROL (20082012) and of Automatica
(20082014), Program Chair for the CACSD Symposium of the 2010 IEEE
MSC, Chair of the IEEE Technical Committee on CACSD (20102013) and of
the IFAC Technical Committee on Robust Control (2011-present), member of
CEB (20022008) and IPC member of various IEEE conferences. He is elected
member of the IEEE-CSS Board of Governors for the years 20142016, and
serves as IEEE-CSS Vice-President for Publication Activities for the year 2015.

Roberto Tempo (F00) is currently a Director of

Research at CNR-IEIIT, Torino, Italy. He has held
visiting positions at Chinese Academy of Sciences,
Beijing, China; Kyoto University, Kyoto, Japan; The
University of Tokyo, Tokyo, Japan; University of
Illinois at Urbana-Champaign, USA; and Columbia
University, New York, USA. He is a co-author of
the book Randomized Algorithms for Analysis and
Control of Uncertain Systems (Springer-Verlag,
London) 2013. His research activities are focused
on the analysis and design of complex systems with
uncertainty, and various applications within information technology.
Dr. Tempo is a Fellow of the IFAC. He is a recipient of the IFAC Outstanding Paper Prize Award for a paper published in Automatica and of the
Distinguished Member Award from the IEEE Control Systems Society. He is
a Corresponding Member of the Academy of Sciences, Institute of Bologna,
Italy, Class Engineering Sciences. In 2010 he has served the IEEE Control
Systems Society as President. Since 2015, he is serving as Editor-in-Chief
of Automatica. He has been Editor for Technical Notes and Correspondence
of the IEEE TRANSACTIONS ON AUTOMATIC CONTROL in 20052009 and a
Senior Editor of the same journal in 20112014. He was General Co-Chair for
the IEEE Conference on Decision and Control, Florence, Italy, in 2013.