Ekundayo E.O. Environmental monitoring

Подождите немного. Документ загружается.

Collaborative Environmental Monitoring with

Hierarchical Wireless Sensor Networks

Qing Ling

,GangWu

and Zhi Tian

Department of Automation, University of Science and Technology of China

Department of Electrical and Computer Engineering, Michigan Technological University

China

USA

1. Introduction

In the last decade, advances in wireless communication and micro-fabrication have motivated

the development of large-scale wireless sensor networks (Akyildiz et al., 2002; Yick et al.,

2008). A large number of low-cost sensor nodes, equipped with sensing, computing, and

communication units, organize themselves into a multi-hop network. The wireless sensor

network takes measurements from the environment, processes the sensory data, and transmits

the sensory data to end-users. Beginning from the seminar work in (Estrin et al., 1999; 2002),

the wireless sensor network technology has been well recognized as a revolutionary one that

transforms everyday life. Typical applications of wireless sensor networks include military

target tracking and surveillance (Simon et al., 2004; He et al., 2006), precise agriculture

(Langendoen et al., 2006; Wark et al., 2007), industrial automation (Gungor and Hancke,

2009), structural health monitoring (Li and Liu, 2007; Ling et al., 2009), environmental and

habitat monitoring (Zhang et al., 2004; Corke et al., 2010), to name a few.

1.1 Network infrastructure

To organize the large amount of sensor nodes and enable efﬁcient data collection, a wireless

sensor network generally adopts one of the following three infrastructures: centralized,

decentralized, and hierarchical. In the centralized infrastructure, sensor nodes transmit

the sensory data to the fusion center via multi-hop communication. In the decentralized

infrastructure, each sensor node ﬁrstly reﬁnes the sensory data through collaborative and

decentralized in-network processing with the neighboring sensor nodes, and secondly

transmits the reﬁned data to the fusion center. While in the hierarchical infrastructure, sensor

nodes are divided into multiple clusters, and sensor nodes within one cluster send their

sensory data to the cluster head. These cluster heads either transmit the collected sensory data

to the fusion center, or collaboratively process them and transmit the reﬁned one to the fusion

center. These two different implementations of the hierarchical infrastructure, centralized

processing and decentralized collaboration, are depicted in Figure 1.

In deploying a wireless sensor network, the choice of its infrastructure is decided by

several key factors: energy, bandwidth, robustness, etc. Sensor nodes are often equipped

with batteries and recharging is difﬁcult. Since wireless data transmission is the main

source of energy consumption of a sensor node (Sadler, 2005), the network infrastructure

2 Will-be-set-by-IN-TECH

.....

Fusion Center

Cluster Heads

Sensor Nodes

.....

Cluster Heads

Sensor Nodes

Fig. 1. Two different schemes of implementing the hierarchical infrastructure: (TOP)

centralized processing in a fusion center and (BOTTOM) decentralized collaboration among

cluster heads.

should guarantee that each sensor node has low data transmission rate while successfully

accomplishing the data collection task. Bandwidth is also a kind of precious resource in

wireless environment; over-competition of wireless channels leads to frequent retransmission

and hence consumes more energy. Further, sensor nodes are often fragile due to being out of

batteries or other physical damages. The network infrastructure should be carefully designed

such that the failure of few sensor nodes shall not result in the malfunction of the whole

network.

When the network size is small, the centralized infrastructure is an acceptable choice. Take

a volcano monitoring network containing 3 sensor nodes (Werner-Allen et al., 2005) as an

example, these sensor nodes directly connect to a fusion center which collects sensory data

and transmits them to the end-user. Later on the network is extended to the scale of 16

sensor nodes (Werner-Allen et al., 2006), and the sensor nodes communicate with the fusion

center via multi-hop relays. However, for GreenOrbs (Liu et al., 2011), a large-scale forest

monitoring network composed of up to 330 sensor nodes, experiments demonstrate that

sensor nodes within some "hot areas" may face higher competition for bandwidth, consume

more energy, and be more sensitive to the failure of sensor nodes. The decentralized

infrastructure, on the other hand, has great potential to reduce the total amount of transmitted

data and hence improve the energy efﬁciency via in-network collaboration; further, it also

enhances robustness of the network since all sensor nodes play equal roles (Ling and Tian,

2010). Nevertheless, collaboration of the sensor nodes brings more difﬁculty to network

coordination, and is subject to the limited processing and communication capabilities of

sensor nodes. For this reason, the decentralized infrastructure is still far from practical

applications. To the best of our knowledge, most large-scale wireless sensor networks are

deployed with the hierarchical infrastructure. Following we give some examples: ExScal,

an intrusion detection network with more than 1000 sensor nodes and more than 200

backbone nodes (Arora et al., 2005); VigilNet, a military surveillance network with 200 sensor

nodes (He et al., 2006); Trio, a target tracking network with 557 solar-powered sensor nodes

462

Environmental Monitoring

Collaborative Environmental Monitoring with Hierarchical Wireless Sensor Networks 3

(Dutta et al., 2006); SenseScope, an environmental monitoring network consisting of from 3 to

97 sensor nodes (Barenetxea et al., 2008). In view of this fact, we will focus on the design of a

hierarchical wireless sensor network.

1.2 Our contributions

In some hierarchical wireless sensor networks such as ExScal (Arora et al., 2005), the cluster

heads are speciﬁcally designed, having better data processing and wireless communication

abilities than general sensor nodes, and equipped with stronger or even uninterruptible power

sources. These cluster heads can directly transmit the collected data to a remote fusion center,

without introducing any collaborative processing among cluster heads. However, in most

wireless sensor networks, cluster heads are elected from sensor nodes to simplify design,

deployment, and maintenance. For example, in the LEACH protocol (Heinzelman et al.,

2002), sensor nodes autonomously elect cluster heads, aiming at evenly distributing energy

consumption among all sensor nodes so that there are no overly-utilized sensor nodes that

will run out of energy before the others. In this case, how to process the collected sensory

data in the cluster heads is a critical problem to accomplishing the data collection task while

maximizing the network lifetime.

This chapter addresses this problem; speciﬁcally, we study a generalized environmental

monitoring model with large-scale hierarchical wireless sensor networks, and focus on two

questions: for cluster heads in a hierarchical network, should they collaborate or not collaborate

and how can they collaborate. Our contributions are two-fold.

First, through theoretical analysis and simulation validation, we make the following

recommendations on whether to collaborate or not: when each cluster head has a large

amount of data to process (namely, each cluster contains a large number of sensor nodes)

and multi-hop relay is necessary to communicate with a fusion center (namely, cluster heads

have limited communication range), decentralized data processing among cluster heads is

more efﬁcient; otherwise centralized decision-making with the aid of a fusion center can be

advantageous.

Previous work, such as (Rabbat and Nowak, 2004; Aldosari and Moura, 2004), has suggested

similar network design principles in the context of decentralized infrastructures: when

each sensor node collects a large amount of data or the size of the network is large,

collaborative processing is more efﬁcient than centralized decision-making. This paper

extends the conclusions to hierarchical networks, and compares decentralized versus

centralized processing among cluster heads rather than among all sensor nodes.

Second, we develop a decentralized collaborative algorithm for decision making among the

sub-network of cluster heads, after they have collected sensory data from local sensor nodes

within their individual clusters. Particularly, we study a typical environment monitoring

application, in which a large-scale hierarchical wireless sensor network is deployed to

monitor sparsely occurring phenomena over a large sensing ﬁeld. The monitoring problem

is formulated as a non-negative quadratic program, which optimizes a sparse decision vector

depicting the spatial map of the phenomena of interest. An optimal iterative algorithm, in

which cluster heads iteratively exchange information and make decisions, is proposed based

on the alternating direction method of multipliers (ADMM) (Bertsekas and Tsitsiklis, 1997).

Our development is permeated with the beneﬁts of compressive sensing (Donoho et al., 2006).

Exploiting the sparse nature of the unknown phenomena, we allow the number of sensor

nodes to be much smaller than what would have been required in a traditional scheme for

463

Collaborative Environmental Monitoring with Hierarchical Wireless Sensor Networks

4 Will-be-set-by-IN-TECH

sensing at high spatial resolution over a large ﬁeld. In this sense, our proposed algorithm is

also applicable to other compressive sensing problems in distributed systems.

1.3 Chapter organization

The rest of this chapter is organized as follows. We ﬁrst give a brief survey on the applications

of wireless sensor networks in environmental monitoring. Second, we study a generalized

environmental monitoring model with large-scale hierarchical wireless sensor networks and

develop a decentralized collaborative algorithm for decision making among the cluster heads.

Finally we discuss the design consideration, namely, to collaborate or not to collaborate, based

on theoretical analysis and simulation results.

2. A brief survey

In this section, we give a brief survey on the applications of wireless sensor networks in

environmental and habitat monitoring. Though this overview is far from complete, it reﬂects

the promising future of the wireless sensor network technology in helping us understand and

protect natural environment.

For environmental and habitat monitoring applications, one of the ﬁrst known practical

wireless sensor networks was deployed by a group at Berkeley in 2002, on Great Duck Island

on the coast of Maine, USA. Two networks with a total of 147 sensor nodes collect data to study

the ecology of the Leach’s Storm Petrel (Szewsczyk et al., 2004). Later on, the Macroscope

system which contains 33 sensor nodes, also developed at Berkeley, was used for microclimate

monitoring of a redwood tree (Tolle et al., 2005). Another notable application is ZebraNet,

which used GPS technology to record position data in order to track long term animal

migrations. In the prototype system, researchers deployed 7 sensor nodes on zebras in Kenya

(Zhang et al., 2004). Energy harvesting technologies have also attracted much research interest

to address the challenge of energy supply in remote environmental monitoring applications.

One successful example is LUSTER, which was developed at University of Virginia, featuring

a speciﬁcally designed hybrid multichannel energy harvesting device (Selavo et al., 2007).

Accompanied with the unprecedented data collection opportunities, data processing also

emerges as a new challenge in the wireless sensor network technology. The data processing

task is indeed application-oriented. For example, an ellipsoids-based anomaly detection

algorithm was designed to monitor unusual and anomalous behaviors in a particular marine

ecosystem (Bedzek et al., 2011). The network was deployed in 2009 at the Heron Island,

Australia, as part of the Great Barrier Reef Ocean Observation System.

One signiﬁcant advantage of wireless sensor networks over traditional data collection

techniques is that they can be applied in harsh environments. For example, in the GlacsWeb

system, researchers at University of Southampton deployed 9 sensor nodes inside a glacier

(Martinez et al., 2004). The sensor nodes monitored pressure, temperature, and tilt, in

order to monitor subglacial bed deformation. Even on active volcanos, which are often

forbidden areas for data collection, wireless sensor networks can still work well. In the

work of (Werner-Allen et al., 2005; 2006), one small sensor network with 3 sensor nodes was

deployed on Vlcan Tungurahua in Ecuador as a proof of concept in 2004; then in 2005, the

network size was extended to 16 sensor nodes. Wireless sensor networks are also ﬁt for

aquatic environmental monitoring applications. In (Alippi et al., 2011), a robust, adaptive,

and solar-powered network was developed in 2007 for such an application. The network

was deployed in Queensland, Australia, for monitoring the underwater luminosity and

temperature, information necessary to derive the health status of the coralline barrier. At

464

Environmental Monitoring

Collaborative Environmental Monitoring with Hierarchical Wireless Sensor Networks 5

the same time, sensory data can be used to provide quantitative indications related to cyclone

formations in tropical areas.

However, applying wireless sensor networks in environmental monitoring is still a

challenging task when the network size is large. When the number of sensor nodes increases,

difﬁculties emerge for system integration (creating an end-to-end system that delivers data

to the end-user), performance (reliability, accuracy, and calibration), productivity (how well

the sensory data assists the end-user and how to reduce the total cost in implementing

the wireless sensor network), etc (Corke et al., 2010). One negative example is reported in

(Langendoen et al., 2006), in which researchers at Delft University of Technology deployed

a large-scale network in a potato ﬁeld to improve the protection of potatoes against disease.

The application was not successful due to unanticipated issues; nevertheless, the lessons are

precious, such as software, hardware, and even team coordination. A systematic discussion,

named as ”the hitchhiker’s guide”, is provided in (Barenetxea et al., 2008). Based on the

deployment of a wireless sensor network on a rock glacier located at a mountain in the

Swiss Alps, this guide covers almost all stages of a project, from hardware and software

development, testing and preparation, to deployment. One of the recent efforts to investigate

the practical implementations of large-scale wireless sensor networks is the GreenOrbs system

(Liu et al., 2011). The network with 330 sensor nodes was deployed in Tianmu Mountian,

China, aiming at all-year-around ecological surveillance in the forest. It is shown that many

traditional design guidelines for small-scale wireless sensor networks can be questionable for

large-scale applications.

3. Problem formulation

In this chapter, we focus on a generalized event detection model for environmental monitoring

applications. Let us consider a large-scale wireless sensor network randomly deployed in a

two-dimensional area for monitoring sparsely occurring events. The network has a set of L

sensor nodes, denoted as

L = {v

}

. Sensor nodes are divided into I clusters, each having

one cluster head in the set

I = {c

}

. Sensor nodes within a cluster are able to directly

transmit measurements to the cluster head, and the cluster head is aware of the positions of

all sensor nodes within its cluster. Further, the cluster heads have a common communication

range r

such that the sub-network of cluster heads is bi-directionally connected.

3.1 Basic assumptions

Suppose that at each sampling time, multiple phenomena may occur in the sensing ﬁeld. Our

objective is to detect and identify the source locations and estimate their amplitudes from

sensory measurements. We make the following basic assumptions for the sensing problem of

interest, similar to those in (Bazerque and Giannakis, 2010):

(A1): The sensing ﬁeld is viewed through a spatial grid with K grid points denoted by

K =

{

}

, whose locations are known to the corresponding cluster heads. Each event can occur

only at a grid point, indicating the spatial resolution offered by this sensor network. The

amplitude of an event occurring at grid point g

is x

(A2): The inﬂuence of a unit-amplitude event at grid point g

on a sensor point v

is f

Generally speaking, f

is decided by the distance d

between g

and v

(A3): The measurement of one sensor node is the linear superposition of the inﬂuences of

all phenomena plus random noise. Mathematically, the measurement b

of sensor node v

is hence b

∑

k=1

+ e

in which x

is the amplitude of event at g

∈Kand e

measurement noise.

465

Collaborative Environmental Monitoring with Hierarchical Wireless Sensor Networks

6 Will-be-set-by-IN-TECH

Fig. 2. The sensor nodes denoted as solid squares are uniformly randomly deployed in the

monitoring area. The candidate positions for phenomena are grid points denoted as solid

dots. Phenomena denoted as pentagrams occur at the current snapshot, and the shadow

regions illustrate the inﬂuence of phenomena.

These assumptions are depicted in Figure 2. The sensor nodes denoted as solid squares

are uniformly randomly deployed in the monitoring area. The candidate positions for

phenomena are grid points denoted as solid dots. Phenomena denoted as pentagrams occur

at the current snapshot, and the shadow regions illustrate the inﬂuence of phenomena.

The assumption (A1) simpliﬁes the recovery problem by conﬁning the sources of phenomena

to grid points. Without this assumption, an alternative way is to use positions and amplitudes

of the sources as decision variables and formulate a least squares problem. However, this

formulation is highly nonlinear and intractable, since the number of decision variables is even

unknown. Based on (A1), we can formulate the otherwise nonlinear problem as recovering

the vector x

=[x

, ..., x

]

from linear measurements b

, ∀l.Entriesinx with nonzero values

reveal the locations and amplitudes of the multiple phenomena of interest. This assumption

approximately holds when the grid points are dense; namely, the density of the grid points

decides the spatial resolution of the recovery algorithm.

The assumption (A2) describes the inﬂuence of one event on the entire sensing ﬁeld. For

example, in target tracking or nuclear radioactive detection, the inﬂuence of a source decreases

polynomially as the distance increases. Without loss of generality, we deﬁne the inﬂuence

function as f

= exp(−d

/σ

) for grid point g

and sensor point v

,whereσ is a common

constant. This Gaussian-shaped function well approximates the inﬂuence of many practical

events.

Based on the assumption (A3), we readily have the following least squares formulation for

recovering x:

min

∑

∈L

−

∑

)

(1)

or equivalently in a matrix form:

min

||Fx −b||

(2)

Here b

=[b

, ..., b

]

is the measurement vector and F is the L × K inﬂuence matrix with its

l-th row given by

[ f

, ..., f

466

Environmental Monitoring

Collaborative Environmental Monitoring with Hierarchical Wireless Sensor Networks 7

Nevertheless, the least squares formulation (2) ignores the sparsity of the vector x.Noticethat

when the grid is dense, the number of events is generally much smaller than the number of

grid points; hence the vector x is a sparse vector with a large amount of zero entries. Without

considering this prior knowledge, the least squares formulation (2) leads to a non-sparse

solution, which means a non-neglectable number of false alarms. The sparsity of a signal

vector can be measured by its



norm (Donoho et al., 2006). Exploiting the sparse nature of

x to alleviate false alarms, we formulate the following



regularized least squares problem

(Kim et al., 2007):

min

||Fx −b||

+ ||x||

(3)

Here λ is a non-negative weight.

3.2 Decentralized optimization

In a centralized setting, the 

regularized least squares problem (3) has been extensively

studied in both signal processing and numerical optimization communities (Donoho et al.,

2006; Figueiredo et al., 2007). However, in a large-scale wireless sensor network, centralized

processing is not efﬁcient in terms of energy consumption and communication overhead. In

contrast, collaborative signal processing among cluster heads is preferred, leading to a robust

and scalable network.

We address this issue by developing a collaborative sparse signal recovery algorithm in the

chapter. Sensor nodes or cluster heads do not necessarily exchange information with a fusion

center; rather, sensor nodes only need to transmit measurements to their cluster heads, and

cluster heads iteratively optimize the decision vector x via exchanging information with their

neighboring cluster heads.

For each cluster head c

, let us collect the local measurements {v

} within this cluster and their

corresponding l-th rows in the measurement matrix F into a sub-vector b

and a sub-matrix F

for all sensor nodes v

whose cluster head is c

. Per assumptions (A1) and (A2),eachcluster

head knows all sensor node locations and grid point locations within its cluster, which means

that F

is known to c

. Hence the problem boils down to the following one: suppose that the local

measurement vector b

and corresponding measurement matrix F

are available to each cluster head c

∀i, how can we design a decentralized algorithm to recover the signal x via collaboration among the

cluster heads?

Let x

denote the local copy of the decision vector x at c

, ∀c

∈I. Meanwhile, given

the communication range r

, the set of neighboring cluster heads of c

is denoted by N

with cardinality

|. The formulation in (3) can be transformed to the following consensus

optimization problem:

min

∑

(

||F

−b

s.t. x

= x

, ∀c

∈I, c

∈N

(4)

The K

× 1 all-one vector [1, 1, ..., 1]

is denoted as 1. Here, cluster heads optimize their

own local copies of x separately, and these decision vectors are forced to be equal via the

consensus constraints. An alternative formulation is to force x

to consent with the average of

its neighboring decisions, as follows:

min

∑

(

||F

−b

s.t. x

∑

∈N

, ∀c

∈I.

(5)

It has been proved that if the sub-network of the cluster heads is bi-directionally connected,

then (4) and (5) are equivalent to (3) (Zhu et al., 2007). Both (4) and (5) can be solved similarly,

as below.

467

Collaborative Environmental Monitoring with Hierarchical Wireless Sensor Networks

8 Will-be-set-by-IN-TECH

4. Collaborative environmental monitoring algorithm

We now apply an optimal algorithm, the alternating direction method of multipliers (ADMM)

(Bertsekas and Tsitsiklis, 1997), to solve (4).

4.1 Algorithm development

To solve (4) with the ADMM, we ﬁrst introduce a new block of auxiliary variables. Then (4)

can be rewritten as:

min

},{z

}

∑

(

||F

−b

s.t. x

= z

, x

= z

, ∀c

∈I, c

∈N

(6)

Here z

is an auxiliary vector attached to x

and x

. The augmented Lagrangian function of

(6) is:



}, {z

}, {β

}, {γ

}



∑

(

||F

−b

)

∑

∈N

−z

∑

∈N

||x

−z

∑

∈N

−z

∑

∈N

||x

−z

(7)

in which

{β

} and {γ

} are Lagrange multipliers and d is a positive constant. At time t,the

ADMM optimizes the augmented Lagrangian function as follows:

Step 1: Optimizing the local copies

(t + 1)} = arg min

}



}, {z

(t)}, {β

(t)}, {γ

(t)}



.(8)

Notice that the objective function is separable, x

(t + 1) can be updated as:

(t + 1)=arg min

(

||F

−b

)

∑

∈N

(t)x

∑

∈N

(t)x

∑

∈N

||x

−z

(t)||

∑

∈N

||x

−z

(t)||

(9)

Step 2: Optimizing the Auxiliary Variable

(t + 1)} = arg min

}



(t + 1)}, {z

}, {β

(t)}, {γ

(t)}



. (10)

Here the objective functions is also separable. Therefore:

(t + 1)=arg min

−β

(t)z

−γ

(t)z

||x

(t + 1) − z

||x

(t + 1) − z

(11)

It has an explicit solution:

(t + 1)=



(t + 1)+x

(t + 1)





(t)+γ

(t)



. (12)

Step 3: Updating the Lagrange Multipliers

{β

} and {γ

(t + 1)=β

(t)+d



(t + 1) − z

(t + 1)



(t + 1)=γ

(t)+d



(t + 1) − z

(t + 1)



(13)

468

Environmental Monitoring

Collaborative Environmental Monitoring with Hierarchical Wireless Sensor Networks 9

The updating rules of (9), (11), and (13) can be further simpliﬁed. Substituting (12) to (13)

yields:

(t + 1)=β

(t)+



(t + 1) − x

(t + 1)



−

(β

(t)+γ

(t)),

(t + 1)=γ

(t)+



(t + 1) − x

(t + 1)



−

(β

(t)+γ

(t)).

(14)

Sinceweoftensetβ

(0)=γ

(0)=0 where 0 denotes a K ×1 all-zero vector [0, 0, ..., 0]

, (14)

implies that β

(t)=−γ

(t)=γ

(t). Then (12) becomes:

(t + 1)=



(t + 1)+x

(t + 1)



. (15)

and (13) becomes

(t + 1)=β

(t)+



(t + 1) − x

(t + 1)



= γ

(t + 1),

(t + 1)=γ

(t)+



(t + 1) − x

(t + 1)



= β

(t + 1).

(16)

Summarizing the three sides of (16) and deﬁne a new Lagrangian multiplier α

∑

∈N

∑

∈N

, the updating rule for α

is:

(t + 1)=α

(t)+dx

(t + 1) −

∑

∈N

(t + 1). (17)

Substituting (15) to (9), we have the updating rule for x

(t + 1)=arg min

∑

(

||F

−b

)

+|N

|α

(t)x

+ d

∑

∈N

||x

−



(t)+x

(t)



(18)

Iteratively solving (18) and updating (17) leads to the optimal solution of (4).

It should be noted that the problem we are discussing is indeed a special case of compressive

sensing (Donoho et al., 2006). When the number of sensor nodes is smaller than the number

of grid points, down-sampling is achieved via exploiting the sparse nature of the signal x.

From this viewpoint, the proposed decentralized sparse signal recovery algorithm is also

applicable to other compressive sensing problems, in which distributed sensor nodes hold

parts of measurement matrices as well as measurement vectors, and collaboratively make

decisions.

4.2 Algorithm outline

The collaborative sparse signal recovery algorithm is summarized as follows. The algorithm

is fully decentralized, requiring only collaboration between neighboring cluster heads.

————————————————————- ————————————————————-

Algorithm: Collaborative environmental monitoring

————————————————————- ————————————————————-

Step 1: Initialization. At each sampling point, each cluster head collects position information

and measurements from sensors within its cluster. Hence cluster head c

knows the partial

measurement matrix F

and the partial measurement vector b

. The number of cluster heads

I, the non-negative constant λ, and the positive constant d are also known.

Step 2: Communication. At iteration t

+ 1, each cluster head c

broadcasts to its neighboring

469

Collaborative Environmental Monitoring with Hierarchical Wireless Sensor Networks

10 Will-be-set-by-IN-TECH

cluster heads to acquire intermediate decision vectors x

(t) of iteration t, c

∈N

Step 3: Optimization. At iteration t

+ 1, each cluster head c

updates its Lagrange multiplier

(t + 1) and decision vector x

(t + 1) according to (17) and (18).

Step 4: Iteration. Repeat Step 2 and Step 3 until convergence.

————————————————————- ————————————————————-

5. Performance analysis

In this section we will brieﬂy discuss the impact of parameter settings on the performance

of the algorithm, as well as the design choice of a hierarchical wireless sensor network. By

performance we are mainly concerning: 1) quality of recovery, which includes the number of

false alarms and the gap between the true and estimated amplitudes; and 2) convergence rate,

which directly decides the communication burden of the cluster heads.

5.1 P arameter settings

The role of the non-negative weight λ in (3) has been extensively discussed in compressive

sensing literature, such as (Donoho et al., 2006; Figueiredo et al., 2007). There is a constant

min

= 1/||F

b||

∞

,suchthatifλ ≤ λ

min

the optimal solution is 0.Whenλ goes to inﬁnity,

the optimal solution has the minimum



norm among all points that satisfy F

(Fx −b = 0),if

these points exist. Hence if b is noise-free and F is a full rank square matrix, then the optimal

solution goes to the true signal. However large λ generally leads to a non-sparse solution

under the existence of measurement noise.

In Step 1 of the collaborative environmental monitoring algorithm, we need to know I,the

number of cluster heads. This procedure requires multi-hop communications if the cluster

heads are not directly connected with each other. However, accurate knowledge of I is not

necessary since it is the product λI that decides the optimal solution.

The proposed algorithm converges for any given positive constant d; however, the value

of d inﬂuences the convergence rate, and thus the communication burden. It is possible

to dynamically increase the value of d to inﬁnity to improve the convergence rate during

the iterative optimization process (Bertsekas and Tsitsiklis, 1997). Due to the extra burden of

updating d, we simply choose d as a constant.

One of the most important advantages of the hierarchical infrastructure is its ﬂexibility to

different application scenarios. By setting I

= 1, the infrastructure turns to be centralized;

while with I

= L and sensors being cluster heads, the network is a fully decentralized one.

This ﬂexibility enables the network to adapt to different application scenarios.

5.2 To Collaborate or not to collaborate

Now we revaluate the order of the required communication load in a hierarchical network

without any fusion center. First, at the data acquisition stage, cluster heads need to

collect measurements from sensor nodes and construct the local measurement matrix, at

communication cost on the order

∼ O(L). Second, at the optimization stage, one cluster head

needs to transmit its decision vector to each neighboring cluster head at each iteration. The

lengths of decision vectors are all K; the average number of neighboring cluster heads varies

from

∼ O(1) (multi-hop communications) to ∼ O(I) (one-hop communications) depending

on the communication range r

of cluster heads. Denote the number of iterations as T,which

is in general inﬂuenced by the choices of d and λ,aswellasthetopologyofthenetwork.

Therefore the overall communication load ranges from O

(KIT) to O(KI

T).

470

Environmental Monitoring