New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Mallie Crist


Marketplace > Georgia State University > ComputerScienence > CSC 8910 > COMPUTER SCIENCE TOPICS SEMINR
Mallie Crist
GPA 3.62

Yingshu Li

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Yingshu Li
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 19 page Class Notes was uploaded by Mallie Crist on Monday September 21, 2015. The Class Notes belongs to CSC 8910 at Georgia State University taught by Yingshu Li in Fall. Since its upload, it has received 13 views. For similar materials see /class/209890/csc-8910-georgia-state-university in ComputerScienence at Georgia State University.

Similar to CSC 8910 at GSU

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15
Energy Ef cient Monitoring of Extreme Values in Sensor Networks ACM SIGMOD2006 Presented by V wek Deshmukh Csc 8910 Apr 3rd 2007 Instructor Dr Yingshu Li Introduction Lifetime of a sensor network can be extended by developing query specific plans that limit the data transmitted by the nodes We consider MAX or MIN queries only This query is an example of a more general exemplary query where solution consists of one or more representative values as opposed to a summary where solution IS computed over all values TYPE of query considered Continuous MAX Query Introduction Contd Example Scenarios 1 Maintaining maximum temperature in a factory 2 Tracking the locations and amounts of highest rainfall across geographic regions Distinction between MAX and Selection Queries is that nodes cannot decide their inclusion in the query result by themselves Previous Approaches 1 Temporal Suppression A node transmits its value only if it has changed since the last transmission 2 Range Caching Th3 root caches a range for each value at a remote no e u The remote node synchronously maintains the same range stored at the root The node only reports its value if it violates the range The length of the range controls the tradeoff between accuracy and amount of communication between root and the remote node Range Caching Contd max 100 r 9 max I ll 020 ill Lfal l Sllllill l 11 10 I39 5ll 17 90 RIiIIII39IIiI ITLII39III RELIDITJ 11 10 r50 rIII I I l I I I I I I If I I I I I I Here max 100 Node with v90 should have smaller range Topology Oblivious Algorithms Here we assume all nodes are connected directly to the root in a onelevel tree Algorithm1 Temporal Suppression Algorithm2 Range Caching l Algorithm3 SLAT Single Layer Adaptive Threshold Packet Types used pE if mew gm awn 1 39 mm mm RE ID 1 E It CUMSM MMES 1 rgnm as cunem 111m Afmt quot 39 de 11131 M is m 111m Range Caching Details After receiving Boot packets from root each node ui transmits to the root its value vi and a range E i I The root maintains the max value v maX39 In subsequent rounds ui sends a Trigger packet listing vi along with a new range if vi falls outside lbiubi After root gets all the reports it finds v as follows max Range Caching Details I Let v highest reported value I Let ub highest upperbound of unreported value I Let b highest lowerbound of unreported value I If v gt ub set vmax to v u If ub gt v or if no nodes reported For each unreported node uiwith ubi gt lb root sends query packet requesting vi The solution is the max of all reply packets Range Caching Details Range Adiustment Whenever a node reports its value it expands the length of its range by a factor or gt 1 The new range is then centered at vi Whenever a node ui is queried by the root lt contracts the length of its range by a factor or with 50 probability In both cases it transmits lbi and ubi to synchronize with the root For the node umax the range is always set to zero since its value is always required Range Adjustment Contd Smaller range gt Lesser chance of being quened Larger range gt Lesser chance of being required to report Important nodes contract their range Unimportant nodes expand their range SLAT Single Layer Adaptive Threshold Initialization Each node ui is assigned a threshold Ti known to both ui and root After recv Boot packet each ui sends vi to root and sets Ti vi Root finds the highest reported value v The one who reported v is u maX39 Root sends MaxDesignate packet to u and instructs to perform temporal suppression max SLAT Contd lnvananbt In a particular round thresholds are set such that for each node ui umax Ti lt umax Nodeinitiated reporting 1 stage Max node does temporal suppression sending Trigger packets when required All other nodes transmit a Trigger packet listing vi if vi gt Ti SLAT Contd Rootinitiated duervinq 2nol staqe After all nodes have reported root determines v using all returned values and stored value of umax if umax did not report I Let u be the node with value v u If v 2 thresholds of all sensors set vmax v and umax u Or else send Query packet to each ui for which Ti gt v The query contains v SLAT Contd Rootinitiated queryinq 2nol staqe contd Each ui receiving a Query sends a Reply with its value vi only if vi gt v At root v is set to max of all reply packets max If no nodes reply v stays at v max If umax designation changes MaxOff and MaxDesignate packets are sent to old umax and new u respectively max SLAT Contd Threshold Setting To maintain the invariant each Ti must be updated and stored at ui and root Whenever ui breaks its threshold and sends Trigger to root it waits for a ThresholdUpdate packet The root transmits v threshold update max found in 2ncl stage to all ui waiting for ui updates its Ti to be halfway between its own value vi and vmax The root does the same thing and updates its own copy of Ti using vi and v both are available at the root maX39 SLAT Contd Threshold Settinq Contd When a node is queried in 2nOI stage there are 2 cases Case 1 If vi gt Query Value Ti is set to vi Case 2 If vi lt Query Value Ti is lowered and set between vi and Query Value This is also sent to the root in a reply packet Optimization If doing so does not lower Ti much below query value ui has option of setting Ti to the Query Value and not replying SLAT Contd Some Observations Higher Thresholds gt Lower reporting Higher Querying I Lower Thresholds gt Higher reporting Lower Querying


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.