Optimal sensor hop selection: Sensor energy minimization and network lifetime maximization with guaranteed system performance

Optimal Sensor Hop S

elec tion: Sensor Ener gy

Minimization and

Network Lifetime Max imization with Guarantee d S

ystem

Per formance

Ling

Sh i

∗

, Karl Henrik

Johanss on

†

and Richard M.

Murr ay

∗

Abstract

—

In this paper

we c

onsider

state e

stimation carr ied

ov er

a sensor network. A fusion ce nter

forms a local multi-hop

tree

of sensors and

ga teway s and

fuses the data into a

state

estimate. It is s

hown that t he optimal estimator ov er

a sensor

tree

is given b

y a

Kalman fi

lter of cer

tain structure . The nu

mber

of hops that t he sensors use to comm

icate data with the fusion

ce nter

is optimize d such that either

the ov er all transmiss ion

ener gy

is minimize d

or the network

li fetime is max imize d.

In b

oth cases the fusion ce nter

prov ides a spec ified level of

estimation acc uracy. Some heuristic algo rithms are

proposed

which lead to sub

optimal solutions in the e

ner gy

minimization

problem, whil e an algo rithm

that leads to the global optimal

solution is proposed in the li fetime max imization p

roblem. In

both cases, the algo rithms are

shown to hav e low compu

tational

complexity. Exa mples are

prov ided to demonstrate the theory

and

algo rithms.

I. I

NTRODU

CTION

Wireless s ensor networks have a tt rac ted much att enti on in

the past few yea rs and this area of r esea rch b ring s tog ether

resea rchers fr om compu ter science , comm un ica ti on , con trol,

etc. [1]. A typ ica l wireless s ensor network con sists of a

large nu mber of sensor nod es, some gateway nod

es and

some base stati on s. Sensor nod es are usuall y b att ery po wered

and h ave li mit ed p roce ss ing ca pabiliti es. They interac t wit h

the phy sica l world and coll ec t i nformati on o f interest, e.g,

temperature, hu midit y, press ure, air densit y, etc. Depend ing

on the Media Acce ss Con trol (MAC) and rou ti ng p rotocols,

as well as the a vail able resou rce s (network b and width, nod e

energy , etc.), the c oll ec ted d ata a re transmitt ed to their final

desti nati on , usuall y a fusion ce nter, at app rop riate ti mes.

Sensor networks have a wide rang e of app li ca ti on s, includ ing

env iron ment and h abit at mon it oring , hea lt h ca re, ho me a nd

office a utomati on and traffic c on trol [2].

Alt hough

tremendou

s prog ress has bee n made in the past

few yea rs in making sensor network an enabli ng tec hno logy ,

many chall eng ing p rob lems remain to b e solved, e.g, network

topo logy

con trol and rou ti ng , coll abo rati ve sign al coll ec -

ti on and informati on p roce ss ing , and syn chron iza ti on [3].

In p arti cular any p rac ti ca l design must full y con sider the

con straints po sed by

the li mit ed p roce ss ing ca pabilit y and

energy supp ly o f eac h ind ividu al sensor.

∗

: Con trol and Dyn amica l Systems, Cali fornia Instit ute of Tec hno logy ,

Pasadena, CA 91106

. Email:

{

shili ng , murr ay

}

@cds.ca lt ec h.edu .

†

: Schoo l of Elec trica l Eng inee ring , Roy al Instit ute of Tec hno logy ,

Stockho lm, Sweden. Email: kall ej@ee .kth.se.

Tel: (626 ) 395 -2313 , Fax: (626 ) 395 -6170 .

The work by

L. Shi and R. M. Murr ay is s uppo rted in p art by AFOSR

grant FA9550 -06 -1-0303 . The work by

K. H. Joh anss on was s uppo rted by

the Swedish Resea rch Coun cil and the Swedish Found ati on for Strategic

Resea rch.

Fig. 1. Sensor Network wit h Gateways

We inv esti gated such con straints in [4] by look ing at

LQG con trol ov er a wireless s ensor network. We presented a

sensor tree rec on figu rati on algo rit hm to mee t a spec ified level

of con trol perf ormance in such a way that t he total energy

usage of the ac ti ve sensor nod es is minimize d. However,

when a sensor nod e is no t a lea f nod e, it no t on ly n ee ds to

send a mea surement data pac ket, bu t also n ee ds to rece ive,

agg regate a nd forward d ata pac kets fr om it s chil d nod

es.

The fac t t hat rece iving a pac ket costs con siderable a moun t

of energy [2], tog ether wit h the rece ntl y p ropo sed Wireless

HA RT protocol [5], moti vates the c urr ent work. In add iti on to

the set of sensor nod es

{

, S

}

con sidered in [4],

we a lso ass ume a set of gateway nod

{

, G

}

avail able (Fig. 1). Gateway nod

es are a lrea dy v ery popu

lar

in Wireless HA RT app li ca ti on s. These gateway nod

es ac t

as relay nod

es, i.e., they do no

t t ake a ny mea surements bu t

simply agg regate a nd forward any incoming d ata pac kets.

The gateways form the bac kbon

es of the network and exec ute

a kno wn rou ti ng p rotocol.

The main con tribu ti on o f this paper is that a c oll ec ti on o f

efficient algo rit hms are propo sed to d etermine which sensor

comm un ica tes to which g ateway in such a way that eit her

the total t ransmiss ion energy o f the sensors is minimize d o r

the network li feti me is maximize d. In bo th ca ses, a ce rtain

spec ified level of esti mati on acc urac y at t he fusion ce nter

is gu arantee d. When the network p ath for the sensor data

is op ti mize d, the resulti ng loca l sensor topo logy h

as the

structure of a tree for which the fusion ce nter is the roo t.

When the plant i s given by

a li nea r system, the op ti mal

esti mator is given by

a Kalman filt er wit h extra memory

Proceedings of the

47th IEEE Conference on Decision and Control

Cancun, Mexico, Dec. 9-11, 2008

WeA14.4

2344

du e to the c omm un ica ti on d elays.

The rapid d evelop ments of wireless and sensor tec hno lo-

gies enable drasti c c hang e of the a rchit ec ture a nd embedd ed

intelli gence in these systems. The theory and d esign too ls for

these systems wit h spati all y and tempo rall y v arying con trol

demand s are no t well develop ed, bu t t here a re a lot of curr ent

resea rch.

One way to d ea l wit h the prob lem of asyn chronou

generati on o f sensor data is to u se e vent-trigg ered con trol

instea d o f conv enti on al ti me-trigg ered con trol [6], [7]. How

to efficientl y encod e c on trol i nformati on for event-trigg ered

con trol ov er comm un ica ti on chann els wit h severe band width

li mit ati on s is discuss ed in [8].

Kalman filt ering und

er ce rtain informati on con straints,

such as dece ntrali ze d implementati on , has bee n extensively

stud ied [9]. Implementati on s for which the c ompu tati on s

are distribu ted among n

etwork nod

es is con sidered in [10 ]–

[12 ]. Kalman filt ering ov

er loss y n etworks is con sidered in

[13 ], [14 ]. The interac ti on b

etwee n Kalman filt ering and

ho w data is rou ted on

a network see ms to b e less s tud ied.

Rou ti ng o

f data pac kets in n etworks are typ ica ll y don

based on

the distance to the rece iver nod e [15 ]. Some

rece nt work add ress es ho w to coup le data rou ti ng wit h

the sensing task u sing informati on theoreti c mea sures [16 ].

An h euristi c a lgo rit hm for event detec ti on and ac tuator

coo rdinati on is propo sed in [17 ]. For con trol ov er wireless

sensor networks, the e xp erience d d elays and p ac ket l oss es

are impo rtant parameters. Rando mize d rou ti ng p rotocols that

gives prob abili sti c gu arantee s on d elay and loss are propo sed

in [18 ], [19 ].

A robu st con trol app roac h to con trol ov er multi -hop n

et-

works is discuss ed in [20 ]. A general cross -layer app roac h

to con trol and d ata rou ti ng see ms to b e a n op en and rather

difficult t op ic du e to many p

rac ti ca l con straints. Our ap-

proac h is diff erent i n that we make the a ss umpti on that a

tree -structured sensor topo logy wit h ce rtain p rop erti es ca n

be sup erimpo sed on

the sensor network. The rou ti ng o

ind ividu al pac kets is no t con sidered, bu t i nstea d p aths are

dyn amica ll y establi shed b etwee n the sensor nod es and the

fusion ce nter.

The rest of the paper is organize d as foll ows. The e nergy

minimiza ti on and n etwork li feti me maximiza ti on p rob lems

are formulated in Sec ti on II . After the op ti mal esti mati on

for fixed nu mber of hop s betwee n the sensors and the fusion

ce nter is ob tained in Sec ti on III , algo rit hms are presented

to solve the e nergy minimiza ti on and the network li feti me

maximiza ti on p rob lems in Sec ti on IV and V respec ti vely. An

example is given in Sec ti on VI to d emon strate the theory and

algo rit hms develop ed in the paper. Con clud ing remarks and

future work are given in Sec ti on VII in the e nd .

II . P

ROBLE M

A. System and S

ensor Network Mod els

Con sider the foll owing LT I system who se state dyn amics

is given by

−

(1)

where

∈

is the state,

∈

is the proce ss no ise

which is whit e Gauss ian, ze ro-mea n and wit h cov ariance

matrix

∈

, Q

≥

A w ireless s ensor network is used to mea sure the state in

Eqn (1). The network con sists of a fusion ce nter, a set of

gateways

and a set of sensor nod es

. When

takes a

mea surement of the state in Eqn (1), it returns

(2)

where

∈

is the mea surement,

∈

is the

mea surement no ise which is whit e Gauss ian, ze ro-mea n

and wit h cov ariance matrix

∈

. The

sensor mea surements are sent t o the fusion ce nter via these

gateways. The fusion ce nter then p roce ss es the rece ived

mea surements and compu tes the op ti mal state e sti mate.

We suppo

se that t here is a non -ze ro sing le-hop comm u-

nica ti on d elay, which is s mall er than the sampli ng ti me of

the proce ss . All sensors are syn chron ize d in ti me, so the data

pac ket t ransmitt ed fr om

to the fusion ce nter is delayed on e

sample when compared wit h it s parent nod e. For example, in

Fig. 1,

is the parent nod e of

and the mea surement fr om

to fusion ce nter is delayed on e step compared wit h

. We

ass ume perf ec t data c omm un ica ti on s, i.e., we do no

t con sider

po ss ible data pac ket drop s introdu ce d by

the wireless li nk s.

B. Sensor Energy Cost Mod el

We a ss ume that t he gateways are e xternall y po wered whil e

the sensor nod es are batt ery po wered. Sensors s pend energy

in many ways, i.e., sensing , idle li stening , compu ti ng , pac ket

transmiss ion and rece pti on , etc. [2]. By app rop riately d esign -

ing the MAC protocol (such as TDMA), pac ket t ransmiss ion

do minates the total energy u sage. Define

as the e nergy

cost for

send ing a mea surement pac ket t o it s parent nod e,

which typ ica ll y g rows rapidly wit h the distance to it s parent

nod e

. Almost all t ransce ivers in sensor nod es no wadays

have a n adjustable transmiss ion po

wer, so wit hou t l oss of

generalit y, we a ss ume that

ca n send it s mea surements

to a sub set of the gateways or to fusion ce nter direc tl y by

adjusti ng it s transmiss ion po

wer.

C. Opti mal Hop S elec ti on Prob lem

Define the foll owing qu

antiti es at t he fusion ce nter.

[

all measurements up to

]

[(

−

)(

−

)

′

]

∞

li m

→∞

if the li mit exists

Deno te

as the hop nu

mber betwee n

and fusion ce nter,

then the delay o f a mea surement fr om

to fusion ce nter

−

. Wit hou t l oss of generalit y, we a ss ume the

transmiss ion energy

(

)

is dec rea sing in

. For example,

in Fig. 1,

ca n send it s mea surements to fusion ce nter,

, G

wit h corr espond

ing hop nu

mbers

An esti mate of

ca n b e be c ompu ted b ased on

the c on sidered wireless

tec hno logy . A comm on mod el i s that i f the distance betwee n

and the

rece iver is

, then

(

)

, where

represents the stati c part

of the e nergy con sumpti on and

(

)

the dyn amic part. The path loss

expon ent

is typ ica ll y b etwee n 2 and 6 .

47th IEEE CDC, Cancun, Mexico, Dec. 9-11, 2008

WeA14.4

2345

and wit h d ec rea sing transmiss ion energy . On the other hand ,

the stea dy state e rr or cov ariance

∞

grows wit h increa sing

delays of the mea surements. Hence there is an app arent

tradeoff betwee n

and

∞

. Let us define the

network

lif eti me

to b e the maximum ti me before a ny on

e of the

sensors s top s working du

e to insufficient energy supp ly, and

we c on sider the foll owing op

ti miza ti on p rob lems

Prob lem 2.1:

(Sensor Energy Minimiza ti on )

min

(

,τ

)

∑

(

)

sub jec t t o

∞

(

, τ

)

≤

desired

≤

, i

= 1

, q.

Prob lem 2.2:

(Network Lifeti me Maximiza ti on )

max

(

,τ

)

min

(

)

sub jec t t o

∞

(

, τ

)

≤

desired

≤

, i

= 1

, q,

where

is the upp er bound o

f the maximum nu mber of

hop s betwee n

and the fusion ce nter, and

is the initi al

energy level of

Intuiti vely, the total t ransmiss ion energy o f the sensors

is minimize d in Prob lem 2.1 and the network li feti me is

maximize d in Prob lem 2.2. The first prob lem is moti vated

fr om the ca se where the diff erence betwee n sensor energy

levels is s mall , and the sec ond on

e is moti vated fr om the

ca se when the diff erence is large. For bo th p rob lems, the

variables that t he ob jec ti ve fun cti on is op ti mize d ov er are

the hop nu

mbers betwee n

’s and fusion ce nter. We will

present soluti on s to bo th p rob lems in the next few sec ti on s.

III . O

PTIMAL

STIMATION FOR

IXED

In o rder to solve Prob lems 2.1 and 2 .2, we nee d to evaluate

∞

(

, τ

)

given

(

, τ

)

so as to find the fea sible

set t o the prob lems. Let

be a nod e that i s

hop s away

fr om fusion ce nter and for

∈

, X

≥

, define

min

{

, τ

}

max

{

, τ

}

[

;

]

, j

min

, τ

max

[Γ

;

; Γ

]

, i

min

, τ

max

diag

{

}

, j

min

, τ

max

diag

{

}

, i

min

, τ

max

(

)

AXA

′

(

)

AXA

′

−

AXC

′

[

′

]

−

′

Further define

−

as all mea surements avail able a t t he

fusion ce nter f or ti me

−

at ti me

k, i

min

, τ

max

For example, in Fig. 1,

min

= 1

, τ

max

= 4

and

{

}

−

{

−

, y

−

, y

−

, y

−

}

−

{

−

, y

−

, y

−

, y

−

, y

−

}

Wit h these definiti on s, we have the foll owing theorem

which sho ws ho w w e ca n ob tain the c losed form soluti on

∞

(

, τ

)

Theorem 3.1:

Given

(

, τ

)

and

ca n b e c om-

pu ted as

min

−

(ˆ

−

min

)

min

−

(

−

min

)

and

(ˆ

−

, P

−

) =

(ˆ

−

, P

−

, C

, Q, R

)

where

min

, τ

max

and

deno tes the stand ard

Kalman filt er. If the li mit s exists,

∞

sati sfies

∞

min

−

(

−

∞

−

∞

′

min

−

min

−

∞

)

(3)

where

Σ =

min

−

∞

′

min

−

∞

min

◦

max

−

(

−

∞

)

and

−

∞

is the un iqu e soluti on to

max

(

−

∞

) =

−

∞

Proo f:

Simil ar to the proo f f or Theorem 4.1 in [4].

IV. O

PTIMAL

ELE

CTION

: M

INIMIZING

OTAL

NERGY

In this s ec ti on , we prov ide soluti on to Prob lem 2.1.

When

and

’s are small , we ca n find the glob al op ti mal

soluti on to Prob lem 2.1 v ia the foll owing algo rit hm.

Globa l Opti mal Search Algo rit hm

1 :

For eac h

= 1

, q

•

for eac h

= 1

, m

∞

(

, τ

)

≤

desired

rec ord

(

, τ

)

as well as

∑

(

)

2 :

Return arg

min

∑

(

)

App arentl y, the

Globa l Opti mal Search Algo rit hm

takes

ti me

(

∏

)

. For large

∏

, it t hen b ec omes

very inefficient, therefore we propo se some loca l sea rch

algo rit hms to app rox imate the op ti mal soluti on . Before we

present some c lass ica l l oca l sea rch algo rit hms, we prov ide

ano ther efficient algo rit hm. It i s also simpler to implement

than most l oca l sea rch algo rit hms [21 ].

The a lgo rit hm we propo se is

Gree dy Efficiency Search

Algo rit hm

. For simpli cit y, let us define

(

) =

∑

(

)

as the total energy cost given

. We a lso writ e

(

)

(

−

, τ

)

when we look at t he hop nu

mber of

Gree dy Efficiency Search Algo rit hm

1 :

:= 1

, i

= 1

, q

2 :

For eac h

, if

∞

(

−

, τ

+ 1)

≤

desired

•

compu te

∆(

) =

∆

where

∆

(

−

, τ

)

−

(

−

, τ

+ 1)

∆

∞

(

−

, τ

+ 1)

−

∞

(

−

, τ

)

3 :

Let

arg

max ∆(

)

. Upd ate

+ 1

4 :

Repea t Step 2 un

til t he incremental dec rea se of the

total energy is wit hin a ce rtain thresho ld.

47th IEEE CDC, Cancun, Mexico, Dec. 9-11, 2008

WeA14.4

2346

Remark 4.1:

It i s ea sy to v erify that t he soluti on fr om

the

Gree dy Efficiency Search Algo rit hm

always s ati sfies the

acc urac y con straint. And in every it erati on , the total energy

dec rea ses. It i s also ea sy to no te that i f at ce rtain it erati on ,

the glob al op ti mal soluti on is ac hieved, then the a lgo rit hm

stop s and returns that op ti mal soluti on .

We prov ide a no ther two class ica l sea rch algo rit hms, i.e.,

the

Rando

mized Gree dy Search

and the

TAB U Search

, and

we c ompare the perf ormance s of the three a lgo rit hms in

Sec ti on VI.

Define

(

)

as the neighbo

rhood

soluti on s of

. The size

(

)

determines the ti me c omplexit y and the op ti malit y

of the soluti on . App arentl y, we nee d to p ick up

(

)

rea son able size . For instance , we define

(

) =

{

′

: 1

≤

′

≤

′

−

≤

}

as the neighbo

rhood

soluti on s for the e xample in Sec ti on VI.

In the e xtreme ca se, if

(

) =

{

′

: 1

≤

′

≤

}

, then

the

Rando

mized Gree dy Search a lgo rit hm

is the same a s

the

Globa l Opti mal Search Algo rit hm

. The multi ple see ds

version o f the

Rando

mized Gree dy Search a lgo rit hm

run s

by exec uti ng the on e see d v ersion a few ti mes. Let

∗

(

)

deno tes the op ti mal soluti on found

at eac h ti me

. The the

minimum of

∗

(

)

and the c orr espond

ing

∗

(

)

is returned.

Rando

mized Gree dy Search: One See d

1 :

∗

is rando mly d etermined.

∗

(

∗

)

2 :

Whil e (stop crit erion is no t met)

•

generate

(

∗

)

•

for eac h

∈

(

∗

)

- if

(

)

∗

τ,

∗

(

)

As we ca n see ,

Rando

mized Gree dy Search

algo rit hm uses

a fixed structure of neighbo

rhood

soluti on s

(

∗

)

at eac h

it erati on . The

TAB U Search

algo rit hm [22 ], [23 ], on the other

hand , uses a dyn amic structure of neighbo

rhood

soluti on s. It

maintains a memory structure: on ce a

po tenti al soluti on is

visit ed, it i s marked as “taboo ” a nd is inserted into a tabu

li st,

, so that t he a lgo rit hm do es no t visit t hat soluti on

repea tedly. The leng th o f

, the size of

(

)

, as well as

the initi al soluti on aff ec t t he perf ormance of the a lgo rit hm.

There a re variou s version s of

TAB U Search

algo rit hms, and

we c on sider on e version b elow.

TAB U Search

1 :

Selec t an initi al

∗

(

∗

)

. Set t he

it erati on coun ter

:= 0

and b egin wit h

empty.

2 :

Generate

(

)

(

)

−

is empty, go to Step 4 .

Otherwise, set

+ 1

and selec t

(

)

∈

(

)

−

which h as

min

(

)

3 :

Let

(

)

. If

(

)

∗

, let

∗

4 :

If a c ho sen nu mber of it erati on s has elapsed eit her

in total or since

∗

was last upd ated, or if

(

)

−

∅

upon

reac hing this s tep d irec tl y

fr om Step 2 , stop ; Otherwise, insert

into

and d elete the oldest entry in

if it i s full .

Return to Step 2 .

V. O

PTIMAL

ELE

CTION

: M

AX IMIZING

IFET IME

In this s ec ti on , we study Prob lem 2.2. Unli ke Prob lem 2.1,

where the glob al op ti mal soluti on ca nno t be found

efficientl y

in g eneral, glob al op ti mal soluti on to Prob lem 2.2 ca n b e

solved v ery efficientl y v ia the foll owing algo rit hm.

Max Lif eti me Search Algo rit hm

1 :

:= 1

2 :

For

= 1

, q

•

let

[

] = min

{

(

)

≤

}

[

]

> m

, go to Step 4 .

3 :

∞

(

[

]

, τ

[

])

≤

desired

•

∗

[

]

•

+ 1

; go to Step 2 .

else go to Step 4 .

4 :

Return

∗

Define

∗

as the maximum network li feti me, i.e.,

∗

= max

(

,τ

)

min

(

)

Theorem 5.1:

The

Max Lif eti me Search Algo rit hm

returns

the op ti mal

∗

and

∗

−

when the a lgo rit hm stop s.

Proo f:

Let

∗

be the op ti mal soluti on corr espond

ing to

∗

We divide the proo f into two p arts.

1) For any

c < l

∗

∞

(

[

]

, τ

[

])

≤

desired

and

[

]

≤

for all

= 1

, q

2) For any

c > l

∗

, eit her

∞

(

[

]

, τ

[

])

desired

or there e xists at l ea st on e

such that

[

]

> m

Once these two p arts are prov ed, the op ti malit y o f the

algo rit hm foll ows as the a lgo rit hm stop s exac tl y at

∗

Proo f f or part 1): Since

∗

is op ti mal,

[

∗

]

≤

for all

= 1

, m

, and

∗

must be fea sible, i.e.,

∞

(

[

∗

]

, τ

[

∗

])

≤

desired

Hence for any

c < l

∗

[

] = min

{

(

)

≤

}

≤

min

{

(

)

≤

∗

}

[

∗

]

≤

The first i nequ alit y ho lds as

(

)

is dec rea sing in

. From

Lemm a 1.1 in App end ix ,

∞

(

[

]

, τ

[

])

≤

∞

(

[

+ 1]

, τ

[

])

≤

∞

(

[

∗

]

, τ

[

])

≤

∞

(

[

∗

]

, τ

[

∗

])

≤

desired

47th IEEE CDC, Cancun, Mexico, Dec. 9-11, 2008

WeA14.4

2347

100

200

300

400

500

−4

−2

T_0\S_3

true state

estimate

100

200

300

400

500

−4

−2

T0 −> T1 −> T2 −> T0

true state

estimate

100

200

300

400

500

−5

100

200

300

400

500

−5

Fig. 2. Dyn amic Sensor Selec ti on

which completes the proo f f or part 1).

Proo f f or Part 2): If

c > l

∗

and

∞

(

[

]

, τ

[

])

≤

desired

and

[

]

≤

for all

, then

[

]

is a fea sible soluti on and

c > l

∗

violates the op ti malit y ass umpti on o f

∗

VI. E

XA MPLE

In this s ec ti on , we c on sider an example to d emon strate

the a lgo rit hms develop ed so far. As the

Max Lif eti me Search

Algo rit hm

returns the op ti mal soluti on , we focus on the

algo rit hms for the e nergy minimiza ti on p rob lem presented

in Sec ti on IV.

We c on sider the foll owing system and sensor mod els.

= 0

−

, i

= 1

The foll owing p arameters are used throughou

t t his s ec ti on .

= 0

= Π

= 0

(

) = [5 3

8 2

6 1

5 1 0

4 0

1 0

08 ]

(

) = [5

0 4 2

8 1

2 0

5 0

15 0

12 ]

(

) = [4

5 3

3 2

1 1

2 0

5 0

24 0

05 0

04 ]

Ass ume the foll owing p erf ormance spec ifica ti on is rece ived

at t he fusion ce nter:

∞

≤

100

∞

≤

101

≤

200

∞

≤

201

≤

300

∞

≤

301

≤

500

Define

the nu mber of f easible soluti on s tha t each

algo rit hm visit s

du ring it s exec uti on . Table I- III

sho w the

result s when we run the diff erent algo rit hms corr espond

ing

to d iff erent

desired

. Since in this example,

∏

= 512

we a re a ble to compu te the glob al op ti mal soluti on v

exh austi ve sea rch.

When

desired

= 0

, the

Gree dy Efficiency Search

the best among all t hree a lgo rit hms which is also the same

TABLE I

DESIRED

= 0

Algo rit hms

(

)

∞

Glob al Opti mal

9.58

0.1802

512

Gree dy Sea rch

10 .04

0.1802

Gree dy Efficiency

9.58

0.1802

TABU Sea rch

10 .04

0.1802

TABLE II

DESIRED

= 1

Algo rit hms

(

)

∞

Glob al Opti mal

3.5

0.7419

512

Gree dy Sea rch

3.5

0.7419

136

Gree dy Efficiency

4.12

0.7419

TABU Sea rch

3.5

0.7419

182

as the glob al op ti mal soluti on , as s ho wn in Table I. It also

visit s the lea st nu mber of f ea sible soluti on s before returning

the op ti mal soluti on . When

desired

= 1

, bo th

Rando

mized

Gree dy Search

and

TAB U Search

return the op ti mal soluti on

and are bett er than

Gree dy Efficiency Search

, bu t at t he

price of visiti ng much more fea sible soluti on s. When we

further increa se

desired

to b e 1.5, neit her algo rit hm return the

op ti mal soluti on and the

Gree dy Efficiency Search

algo rit hm

still visit s the lea st nu mber of f ea sible soluti on s.

In p rac ti ce , we ca n run the three a lgo rit hms and take the

best soluti on o f them. Fig. 2 sho ws the simulati on result

of esti mati ng

using the e sti mati on scheme presented in

Theorem 3.1. The left hand figu res demon strate the result

when a fixed topo logy is used (

= [8 8 2

]

) in which ca se,

∞

= 0

7419

and a c on stant energy con sumpti on o f 3.5

un it s per ti me is requ ired. The righ t hand figu res s ho w that

the dyn amic hop selec ti on is used to adapt t o p erf ormance

spec ifica ti on . As we ca n see , du ring

101

≤

200

, a new

topo logy is used (

= [8 1 1

]

) and the e nergy con sumpti on

is increa sed to 9 .58 un

it s per ti me, ho wever,

∞

redu ce s to

0.1802

which sati sfies the perf ormance spec ifica ti on . Simi-

larly

∞

is requ ired to b e less than 1 .5 when

201

≤

300

a diff erent sensor topo logy (

= [4 8 8

]

) is adop ted which

on ly requ ires 1.66 un

it s energy con sumpti on p er ti me.

By dyn

amica ll y d etermine the sensor hop nu

mbers, we

ca n therefore minimize the sensor energy con sumpti on as

much as po ss ible yet still gu arantee a

spec ified level of

perf ormance .

TABLE III

DESIRED

= 1

Algo rit hms

(

)

∞

Glob al Opti mal

1.4

1.3918

512

Gree dy Sea rch

1.66

1.3918

155

Gree dy Efficiency

1.92

1.3918

TABU Sea rch

1.66

1.3918

182

47th IEEE CDC, Cancun, Mexico, Dec. 9-11, 2008

WeA14.4

2348

Fig. 3.

→

+ 1

VII . C

ON CLUSION AND

UTURE

ORK

In this paper, we have c on sidered the op ti mal sensor

hop selec ti on p rob lem for state e sti mati on ov

er a wireless

sensor network. Efficient algo rit hms are propo sed to solve

the e nergy minimiza ti on and n etwork li feti me maximiza ti on

prob lems. For bo th p rob lems, a ce rtain spec ified level of

system perf ormance is gu arantee d.

There a re a few extension s of the c urr ent work that we

will pu rsue in the future which includ e c losing the loop

based on

the e sti mati on scheme; exp erimentall y evaluate the

algo rit hms develop ed in the paper; con sider pac ket drop s

iss ues in the c omm un ica ti on li nk which is often see n du e to

the nature of wireless comm un ica ti on s.

Ack no wledg ement:

The a utho rs wou ld li ke to thank Profes-

sor Mikae l Joh anss on at KTH for discuss ion s of the variou s

loca l sea rch method s.

PP END IX

Lemm a 1 .1:

For any

≤

∞

([

, τ

])

≤

∞

([

, τ

+ 1

, τ

])

Proo f:

We give a proo f f or the foll owing ca se (Fig. 3).

The e xtension to g eneral ca se is s traigh tforward. From The-

orem 3.1,

∞

([

= 2

, τ

= 3]) =

(

−

∞

)

where

(

) =

−

′

[

′

+ Π

]

−

and

−

∞

sati sfies

[

;

]

(

−

∞

) =

−

∞

. Simil arly,

∞

([

= 2

, τ

= 4]) =

(

−

∞

)

where

−

∞

(

−

∞

)

. Therefore

∞

([

= 2

, τ

= 4])

(

−

∞

)

≥

(

[

;

]

(

−

∞

)

(

−

∞

)

∞

([

= 2

, τ

= 3])

where the inequ alit y foll ows fr om Lemm a 1.2.

Lemm a 1 .2:

For any

≥

, the foll owing ho

lds

(

)

≥

(

)

and

(

)

≥

(

)

[

;

]

(

)

≤

(

)

Proo f:

For proo f of part 1), see [13 ]. For proo f of part

2), see [4].

EFERENCES

[1] D. Cull er, D. Estrin, and M. Srivastava, “Overview of wireless s ensor

networks,”

IEEE

Compu ter, Sp ec ial Iss ue in S ensor Networks

, Aug

2004 .

[2] N. P. M. (Ed.),

Sensor Networks and Configu

rati on

. Spring er, 2007 .

[3] C.-Y. Chong

and S. P. Kumar, “Sensor networks: Evo luti on , oppo rtu-

niti es, and chall eng es,”

Procee ding s of t he IEEE

, vo l. 91 , no . 8, Aug

2003 .

[4] L. Shi, K. H. Joh anss on , and R. M. Murr ay, “Chang e sensor topo logy

when n ee ded: How to efficientl y u se system resou rce s in con trol and

esti mati on ov

er wireless networks.” Procee ding s of the 46 th IEEE

Con ference on Dec ision and Con trol, New O rlea ns, Dec 2007 .

[5] htt p:// www

.hartcomm 2.org.

[6] H. Kop etz, “Shou ld respon sive systems be e vent t rigg ered o r ti me

trigg ered?”

IEICE Tran s. on Informati on and S

ystems

, vo l. E76 -D(10 ),

pp . 1525–1532

, 1993 .

[7] K. J.

Astr ̈om and B. Bernh ardss on , “Comparison o f period ic a nd event

based sampli ng for first-order stochasti c systems,” vo l. J. In Preprints

14 th World Cong ress of I FAC, Beiji ng , P.R. China, pp . 301–306

[8] L. Bao, M. Skog lund , and K. H. Joh anss on , “Encod er–d ec od er de-

sign for event-trigg ered fee db ac k con trol ov er band li mit ed chann els.”

America n Con trol Con ference , Minn ea po li s, Minn esota, USA, 2006 .

[9] D. Silj ak,

Large-Scale Dyna mic Systems: Stab ilit y and S

tructure

North-Holl and , New Y ork, 1978 .

[10 ] P. Alrikss on and A. Rantze r, “Distribu ted k alman filt ering u

sing

weigh ted averaging .” Proc. 17 th Internati on al Sympo sium on Math-

emati ca l Theory o f Networks and Systems, Kyo to, Japan, 2006 .

[11 ] R. Olfati -Saber, “Distribu ted k alman filt er wit h embedd ed con sensus

filt ers.” Procee ding s of the 44 th IEEE

Con ference on Dec ision and

Con trol and Europ ea n Con trol Con ference , 2005 .

[12 ] D. Spano s, R. Olfati -Saber, and R. M. Murr ay, “Distribu ted k alman

filt ering in sensor networks wit h qu anti fiable perf ormance .” Procee d-

ing s of the 4th Internati on al Con ference on Informati on Proce ss ing in

Sensor Networks, 2005 .

[13 ] B.Sinopo li , L.Schenato, M.France schetti , K.Poo ll a, M.Jordan, and

S.Sastry, “Kalman filt ering wit h intermitt ent ob servati on s,”

IEEE

Tran sacti on s on Automati c Con trol

, vo l. 49 , no . 9, pp . 1453–1464

2004 .

[14 ] J. Hespanh a, P. Nagh shtabrizi, and Y. Xu, “Networked con trol systems:

Analysis and d esign ,”

To app

ear in the Proc. of IEEE , Sp ec ial Iss ue

on Networke d Con trol Systems

, 2007 .

[15 ] D. P. Bertsekas and R. Gall ager,

Data Networks

, 2nd ed. Prenti ce

Hall , 1991 .

[16 ] F. Z. Juan Liu and D. Petrov ic, “Informati on -direc ted rou ti ng in ad

ho c sensor networks,”

IEEE

JOU RNAL ON SELECTED AREA

S IN

COMM UNICATIONS

, vo l. 23 , no . 4, April 2005 .

[17 ] E. Ngai, M. Lyu , and J. Liu, “A rea l-ti me c omm un ica ti on fr amework

for wireless s ensor- ac tuator networks.” Aerospace Con ference , 2006

IEEE , 2006 .

[18 ] A. Bon ivento, C. Fischion e, and A. Sang iov ann i-Vince ntelli , “Ran-

do mize d p rotocol stac k for ub iqu it ou s networks in indoo r env iron -

ment,”

IEEE

CCNC

, vo l. 1, April 2006 .

[19 ] W. Lai and I. C. Paschali dis, “Rou ti ng through no

ise a nd slee ping

nod es in sensor networks: l atency v s. energy trade-off s.” Procee ding s

of the 45 th IEEE

Con ference on Dec ision and Con trol, San Diego , CA,

USA, Dec 2006 , pp . 551 – 555

[20 ] A. Panou sopou lou , G. Niko lakopou

los, A. Tze s, and J. Lyg eros, “Ex-

perimental evaluati on o f a mob il e a d-ho c networked (manet)con troll ed

system.”

Proc. 17 th Internati on al Sympo sium on Mathemati ca l

Theory o f Networks and Systems, Kyo to, Japan, 2006 .

[21 ] C. Blum and A. Roli , “Metaheuristi cs in combinatorial op ti miza ti on :

Overview and con ce ptual comparison ,”

ACM Compu ti ng Su

rvey s

vo l. 35 , no . 3, pp . 268–308

, September 2003 .

[22 ] F. Glov er, “Tabu sea rch - part i ,”

ORSA Jou rna l on Compu ti ng

, vo l. 1,

pp . 190–206

, Summ er 1989 .

[23 ] —— , “Tabu sea rch - part ii ,”

ORSA Jou rna l on Compu ti ng

, vo l. 2,

pp . 4–32 , Winter 1990 .

47th IEEE CDC, Cancun, Mexico, Dec. 9-11, 2008

WeA14.4

2349