Adaptive Target Tracking in Sensor Networks Xingbo Yu,Koushik Niyogi,Sharad Mehrotra,Nalini Venkatasubramanian

University of California,Irvine

Abstract

Recent advances in processor,memory and radio tech-nology have enabled cheap nodes capable of sensing, communication and https://www.wendangku.net/doc/759992283.html,works of distributed microsensors are rapidly emerging as a feasible solution to a wide range of data gathering applications.How-ever,the key impediments to successful deployment of microsensor nodes are their energy and longevity con-straints.We propose a quality aware information col-lection protocol in sensor networks for tracking appli-cations.The protocol explores trade-off between en-ergy and application quality to signi?cantly reduce en-ergy consumption in the sensor network thereby enhanc-ing the lifetimes of sensor nodes.Simulation results over elementary movement patterns in a tracking application scenario strengthen the merits of our adaptive informa-tion collection framework.

Key Words:wireless sensor networks,mobile target tracking,quality of service

1Introduction

With advances in computation,communication and sensing capabilities,large scale sensor-based distributed environments are emerging as a predominant mobile computing infrastructure.Sensor applications typically monitor real-world phenomena and utilize the accurate knowledge of current state to dynamically optimize ap-plication execution.Traditionally,a critical issue in en-abling wide-spread use of mobile computing is that of effective power management to extend battery life.This is further exacerbated in sensor environments where it is often dif?cult or infeasible to replenish power supplies of wireless devices.Power supply in sensors is used for a variety of purposes:for basic sensing operations, for powering the memory and CPU,and for communica-tion.While the speci?c rate of energy consumption for each of these operations is sensor and application spe-ci?c,much of the existing literature indicates that com-munication constitutes a major source of power drain[4]. Modern sensors try to be power-aware,shutting down components(e.g.,radio)when they are not needed and/or scaling the frequency/voltage of the processor depending upon the workload[3,7].

While well engineered sensor technology can signi?-cantly conserve power,for a variety of applications much further gain can be accrued by exploiting the natural tradeoff between application quality and energy conser-vation.In this paper,we explore a framework that ex-ploits resource versus quality tradeoff to reduce commu-nication in the context of information collection for mo-bile target tracking in sensor environments.The proposed framework exploits the application tolerance by collect-ing data at only the accuracy levels needed to meet the application’s requirements.The greater the application’s tolerance to error in sensor values,the lower the commu-nication overhead between sensors and server,and hence higher the resulting savings.

The rest of the paper is organized as follows.Sec-tion2introduces sensor nodes and target tracking using sensor networks.Section3describes adaptive protocols proposed in this paper.Section4illustrates the savings that result from our protocol by a set of simulations.Re-lated work is presented in Section5.

2Quality Aware Information Collection and Tracking Applications

2.1Sensor Nodes and Sensor Networks

The overall environment for adaptive information col-lection is illustrated in Figure1,where applications em-ploy information collection protocol to obtain the desired information from a distributed sensor network infrastruc-ture.

Prediction module

Sensor Selection

AQ-MQ translation

Figure https://www.wendangku.net/doc/759992283.html,rmation collection architec-

ture

S 0

S1

S2

quasi-active

monitor

active

Figure 2.State transition diagram for

sensor node in target tracking

A sensor node consists of the embedded sensor,a pro-cessor with some limited memory and the radio circuitry [3].Each component is controlled by a micro operating system that decides which device to turn off and on.A power aware sensor node has3different states of opera-tion(see Figure2).While in state(active state),a sen-sor node transmits and receives messages at every time instant.State(quasi-active state)is a reduced energy state in which the sensor sends a message to the server at a reduced frequency as explained later.The most en-ergy ef?cient state is the monitor state in which the sensor turns its radio off and senses the environment for signals.The state transitions of the sensor are dictated by the adaptive information collection protocols.A sensor senses the environment at periodicity and commu-nicates its readings to the server at periodicity.For simplicity we assume that is the same as.We consider time to be discretized into units of length each.A sensor reading at time unit is represented as .

The system architecture considered in this paper is logical.Physically,the server architecture may itself be centralized,distributed or hierarchical.Furthermore,a part of the server module might reside on a computation-ally superior sensor node,which may be responsible for both sensing as well as fusing the readings from other sensor nodes.In the latter case,the server(super sen-sor node)may host both the sensor module as well as the server module.Furthermore,the issue of wireless net-work routing of data between the sensors and servers is orthogonal to our work and is abstracted out.One may have a direct communication link between the server and each sensor node,or a multi-hop routing scheme from a sensor node to the server as discussed in[11].

2.2Mobile Target Tracking

In our application scenario,each sensor has an unique identi?er,coordinates,and visibility radius.For low cost and low energy consumption,we assume passive sen-sors that operate only on the received acoustic or seis-mic waveforms from non-cooperative sources.A sensor senses the environment and communicates its readings to the server periodically;the server triangulates the loca-tion of the object using the readings.The signal attenua-tion of the target source power is governed by equation ,where is the Euclidean distance between the object and a sensor node.This relation is the basic equation used in triangulation.

Let be the real track of object and

be its approximate track perceived by the server.We for-mally de?ne the notion of track quality and sensor measurement quality

below:

Figure3.tracking quality

Track Quality:Track quality,,is de?ned as the maximum distance between the real track of the target object and the approximate track generated at the user end(see?gure3):

Sensor Measurement Quality:If we consider the measurement at a sensor S as a time series which is approximated by,the measurement quality is the maximum divergence between and

at any time i.e:

Given a user de?ned track quality parameter, the sensor network tracks an object with an error bound of with small communication overhead.We map track quality to measurement quality below,where we utilize a simple tracking approach of triangulating3sen-sor readings to determine the location of an object.

Consider three sensors whose locations ()are known.The inten-sity readings of the sensors at the time of triangulation are and.We then have the following set of equations:

(1)

,and

For the above triangulation scheme,we can show that the tracking error tolerance is proportional to the ratio

from tracking quality .This provides,for each sensor,a relative mea-surement error tolerance which is subsequently used in our adaptive protocols.

There are two issues with the above approach.Firstly, we observe that?rst

’s,we can show that when, is under-estimated and when,is over-estimated.We overcome this problem by scaling as follows:

If,then scale by

,where.

If,then scale by

,where.

Secondly,in our tracking algorithm,the target source power was assumed to be constant.However,when the source power is unknown,tracking and error translation are more complicated.We discuss this issue in detail in [8].

3Quality Aware Information Collection Protocols

As per the state transition diagram of a sensor node, at a particular instant of time some sensors will be ac-tive while the others will be in a monitor or quasi-active state.The sensor selection phase determines which sen-sors should be active at a particular time instant,and controls the state transition of the sensors from active to quasi active and monitor states.It also implements pre-cision based measurement update.The following sub-sections describe the sensor selection process in detail at the server and the sensor side.

3.1The Sensor Module

A sensor may be triggered by an external event to move from a monitor state to an active state.An external event in a tracking application would be an ob-ject moving within the visible radius of a sensor node. In its active state,a sensor sends continuous updates at each time interval to the server module.An update packet consists of the sensor reading,timestamp and state of the sensor(e.g.energy statistics).The server module may decide to transit the sensor to a quasi-active state by sending the measurement tolerance corresponding to the desired application tolerance.The sensor now makes a transition to a quasi-active state,and sends an update to the server module only if its reading exceeds its previous reading by the measurement tolerance.

Sensor Module

::time,:reading at time,

)

=S0or

=S2;

4.else if(external event)

5.if(

);

8.if(

);

12.;

13.else do nothing;

14.end procedure

Table1.Sensor side algorithm for adapta-

tion and state transition

The server on receiving the value update will make the

corresponding update for the sensor measurement in its

sensor database.A sensor may transit from the active or

quasi-active states to the monitor state due to either an

external event(e.g.,sensing measurement falling below

a threshold),or a message from the server.If the transi-

tion happens due to an external trigger,the sensor sends

a corresponding message to the server.Table1shows the

sensor module for precision based adaptation and state

transition at a sensor node.

3.2The Server Module

The server maintains an active list of sensor nodes

which contains an array of sensors and a history of their

readings over a time period.For the sake of simplic-

ity,we bound the communication latency in the sensor

network,i.e.the time taken for an intensity reading to

reach the server by.Thus the network latency is less

than for any node in the network.At time,

when the server receives an update from sensor,it

waits for(to receive all possible sensor readings at

that time instant)and checks to see if the sensor is in

mode(active state).If so,it adds this sensor to its ac-

tive list and sends an error update message containing the

tolerable measurement error.However,if the sensor

is in state(quasi-active),the server looks up the active

list to determine whether the sensor readings are already

in use by applications at the server.If so,it adds the lat-

est reading of sensor along with its timestamp to the

sensor’s history list(see Table2).Alternatively,if the

sensor is not in the active list of the server(i.e.,its value

is not needed by the server),the server sends a message to

the sensor to shift to the monitor state.On receipt of the

message from the sensor that it has transited into monitor

state,the server looks up its active list and removes the

corresponding entry in the list.

The framework described above ensures that for each active sensor,the server maintains in its database an approximate measurement that is within the tolerable threshold of the actual sensor measurement.The reduced rate of communication between the sensor and the server in the quasi-active state and switching off of the radio in the monitor state result in energy conservation.

Server Module

::sensor id,:time,:sensor reading,:sensor state :Active list of sensor nodes,:tracking quality Procedure Recv Send

1.if(=S0)

2..add(,,);

https://www.wendangku.net/doc/759992283.html,pute;

4.Send update(sid,);

5.else

6.Look up in;

7.if(.contains());

8.Add to the corresponding entry in;

9.end procedure

Table2.Server side sensor selection proto-

col

A triangulation based tracking application program sits at the server above the proposed middleware frame-work.It takes readings from the active list of the server module and pinpoints the location of the moving object with bounded tracking quality guarantees.

3.3Prediction Models and Local Aggregation

The communication cost of the precision based ap-proach can be further reduced by exploiting the pre-dictability of readings of a sensor.If we consider a pre-cision based approach,whenever the current location of the object deviates from its previous reported position by ,the sensor has to communicate its readings to the server.If the sensor and the server can decide on the mo-bility model of the target object,they can predict its lo-cation in the near future and further communication sav-ings can be achieved.In such a case,our approach can be modi?ed such that a sensor reports its readings only if the observed value deviates from the expected value based on the prediction model by a pre-de?ned error bound. Such prediction models may be integrated into the client and server modules of the information collection frame-work to gain further savings in energy.Many issues need to be resolved in incorporating prediction models,such as who determines the prediction model,the sensor or the server;the protocol by which a sensor or the server choose a model;dynamic model switching when the prediction model needs to be changed.We address the above mentioned issues in[8].

In order to further reduce the long range communi-cation cost between sensors and the server,local aggre-

Figure4.Precision and Prediction based experiments for mobility model

M1 Figure5.Precision and Prediction based experiments for mobility model M2

interval of0.2seconds to the server.PREC-GA is a precision based adaptive protocol which has an user de?ned tolerance parameter associated with it.This means that the user speci?es at the application level the quality at which he wants the object to be tracked.The application quality is mapped to the measurement quality, based on which a sensor sends an update to the server.In PRED-GA,we allow the sensor to?t a constant velocity based prediction model(see[8])to track the object.The fourth algorithm PREC-LA implements the local aggre-gation mechanism where an leader node is elected among a group of sensors and each active sensor in the group sends its update based on its measurement error to the leader,who forwards it to the server only if the overall group quality is violated.Also,for the sake of simplicity we abstract our algorithm from the underlying routing al-gorithm which routes a packet from a sensor node to the leader.

We vary the error tolerance from2to10meters,and measure the energy consumption at each node and over the entire grid for the period of simulation.In each of these graphs the energy consumption is measured in terms of micro joules per bit.Figure4shows the results obtained for mobility model.The graphs show(a) the track of the object,(b)the variation of the total en-ergy consumption per bit using the four algorithms de-scribed above.We get a signi?cant savings(50-60%)in communication costs over the network(neglecting costs in switching from one active state to another).PRED-GA outperforms the precision based PREC-GA since the object follows a linear velocity model throughout its trajectory.However,at a certain track error,energy savings from prediction and precision based algorithms reach a saturation level as further optimizations are not feasible.PREC-LA outperforms PRED-GA since it per-forms lesser number of global server updates based on local computation at the leader node.

Figure5shows the same results for mobility model .We notice that using a prediction based algorithm PRED-GA,we quickly reach a saturation point and the precision based algorithm PREC-GA starts performing better at a certain value of track error.This is because the object now follows a more random path than in mobil-ity model which leads to model switching and more communication overhead at a sensor node when we use a prediction based approach.

Figure6shows the impact of send time interval and velocity of the moving object to energy savings at the sensor node.The?rst graph plots the energy savings with an increase in or the time interval at which a node sends an update in the non-adaptive algorithm.We notice that at lower values of we obtain signi?cant energy ef?ciency.However,when is suf?ciently large,the quality of the true track as governed by is not?ne grained enough to be optimized.In the second graph, the velocity of the object was varied from5m/s to15

Figure6.Effect of and object velocity in mobility model

m/s while the track error was?xed at10m and=0.2 seconds for object model.At lower velocities,our energy savings are very high,since the sensor nodes in a grid cell send much fewer readings than in the non-adaptive case(both in case of PREC-GA and PRED-GA).

5Related Work

The issue of quality and communication trade-off has been studied by Olston et al.[1]to reduce communica-tion between a server and a single source.In[12],the authors extend their work to a best effort synchronization of source data objects and cached copies subject to band-width and other resource constraints at the source.The techniques did not take into account sensor state transi-tion.

Several localized algorithms have been suggested in the literature[9,10]to track an object using sensor col-laboration.Zhao et al.[9]propose a distributed algorithm which routes a query related to the position of an object to a region of potential events,where a sensor node can answer it.The model of a sensor node there is differ-ent from the one we propose,since a sensor is able to ?gure out the position and the direction of a target ob-ject by itself and is in an active state throughout its life-time.Estrin et al.[10]also describe a localized algorithm for coordination among sensor nodes,thereby electing a cluster-head among a group of sensor nodes which does the sensing and the triangulation.Our information collec-tion framework is applicable to such localized algorithms too,since the server module would now reside on a sen-sor node or a cluster-head.

References

[1]C.Olston,B.T.Loo,and J.Widom.Adaptive pre-

cision setting for cached approximate values ACM Sigmod,2001

[2]M.Bhardwaj,A.P Chandrakasan.Bounding the

Lifetime of Sensor networks via optimal Role as-signments Proceedings of INFOCOM,2002

[3]A.Sinha,A.Chandrakasan.Dynamic Power Man-

agement in Wireless Sensor networks IEEE Design

and Test of Computers,2001

[4]G.J.Pottie and W.J.Kaiser.Wireless Integrated net-

work sensors Communications of the ACM,2000 [5]R.Min et al.An architecture of a power aware dis-

tributed microsensor network IEEE workshop on

Signal Processing systems,2000

[6]T.Rappaport.Wireless Communications:Principles

and Practice Prentice Hall Inc,1996

[7]S.Singh and C.S Raghavendra.PAMAS-Power

Aware Mult-Access protocol with signaling for ad-

hoc networks SIGCOMM Computer Communica-tion Review,July1998

[8]X.Yu,K.Niyogi,S.Mehrotra and N.Venkatasubra-

manian.An Adaptive Information Collection Mid-

dleware for Sensor Network Applications.Techni-

cal Report TR-DB-02-08,ICS,UC Irvine,2002 [9]F.Zhao,J.Shin and https://www.wendangku.net/doc/759992283.html,rmation driven

Dynamic Sensor Collaboration for tracking appli-

cations IEEE Signal processing magazine,2002 [10]D.Estrin,https://www.wendangku.net/doc/759992283.html,indan,J.Heidemann and S.Ku-

mar.Next Century Challenges:Scalable Coordina-

tion in Sensor Networks MobiCOM,1999

[11]W.R.Heinzelman,J.Kulik and H.Balakrishnan.

Adaptive protocols for information dissemination

in wireless sensor networks ACM/IEEE Mobicom

Conference,1999

[12]C.Olston and J.Widom.Best-Effort Cache Syn-

chronization with Source Cooperation SIGMOD

2002

[13]https://www.wendangku.net/doc/759992283.html,/ito/research/sensit/index.html

HTML标签以及各个标签属性大全(网页制作必备).

取消换行和
相反 总类（所有HTML文件都有的） -------------------------------------------------------------------------------- 文件类型（放在档案的开头与结尾） 文件主题（必须放在「文头」区块内） 文头（描述性资料，像是「主题」） 文体（文件本体） 结构性定义（由浏览器控制的显示风格） -------------------------------------------------------------------------------- 标题（？表示从1到6，有六层选择）数值越高字越小 标题对齐左对齐、居中对齐、右对齐 区分