Query Processing, Data Aggregation and Node Localization
Complete RGPV exam-oriented notes covering query processing in WSN, data aggregation, localization concepts, localization challenges, range-based and range-free techniques, ranging methods and major wireless-localization algorithms.
1. Query Processing in Wireless Sensor Networks 14 Marks
Query processing in a Wireless Sensor Network is the process of accepting a user query, distributing it to relevant sensor nodes, collecting matching sensor data, processing the results and returning the required information to the user.
In a WSN, users generally do not communicate with each individual node. Instead, they issue high-level queries such as:
“Report the average temperature of Zone A every 30 seconds for the next 10 minutes.”
User Query
|
v
Base Station / Sink
|
Query Dissemination
|
v
Relevant Sensor Nodes
|
Sensing + Local Processing
|
v
Aggregation / Routing
|
v
Sink Result
|
v
User
Characteristics
Data-centric operation
Distributed execution
Energy-aware processing
Support for continuous and event-based queries
In-network filtering and aggregation
Approximate or incomplete results may be acceptable
2. Need for Query Processing in WSN 7 Marks
Sensor networks generate a very large amount of raw data.
Transmitting every reading consumes excessive energy.
Users require only application-relevant information.
Queries help select specific regions, sensors and time intervals.
Local processing reduces communication overhead.
Aggregation removes duplicate and redundant readings.
Efficient query plans increase network lifetime.
Communication generally consumes more energy than simple local computation. Therefore, WSN query processing tries to process data near its source.
3. Components of a WSN Query 7 Marks
Target data: Temperature, pressure, humidity or other sensed value.
Region: Physical area or group of nodes.
Condition: Predicate such as temperature greater than 50°C.
Aggregation: Average, count, minimum, maximum or sum.
Sampling period: How frequently data should be measured.
Duration: How long the query should remain active.
Accuracy requirement: Desired precision or confidence.
SELECT AVG(temperature)
FROM sensors
WHERE region = 'Zone A'
SAMPLE PERIOD 30 seconds
FOR 10 minutes
4. Types of Queries in WSN 14 Marks
Snapshot Query
Requests the current value once.
Continuous Query
Remains active and produces results periodically.
Historical Query
Requests previously stored sensor data.
Event-Driven Query
Produces a result only when a specified event occurs.
Aggregate Query
Requests a summary such as average, count or maximum.
Location-Based Query
Selects nodes or data from a particular geographical region.
Top-k Query
Returns the k highest or lowest sensor readings.
Query Type
Example
Snapshot
Current temperature of Room 101
Continuous
Temperature every 20 seconds
Event-driven
Alert when smoke level exceeds threshold
Aggregate
Average humidity of the field
Top-k
Five nodes with highest temperature
5. Query Processing Steps 14 Marks
Query submission: User sends a query to the sink.
Parsing: The system checks query syntax and meaning.
Query optimization: An energy-efficient execution plan is selected.
Query dissemination: Query is forwarded to relevant nodes.
Sampling: Sensor nodes collect requested values.
Local processing: Nodes filter or partially aggregate readings.
Routing: Results travel toward the sink.
Aggregation: Intermediate nodes combine data where possible.
Result generation: Sink prepares the final answer.
Result delivery: Information is presented to the user.
Query
|
Parse
|
Optimize
|
Disseminate
|
Sense Data
|
Filter / Aggregate
|
Route to Sink
|
Final Result
6. Query Optimization in WSN 14 Marks
Query optimization selects an execution strategy that minimizes energy, delay and communication cost while maintaining acceptable result quality.
Optimization Techniques
Predicate push-down near sensor nodes
Early filtering of unwanted readings
In-network aggregation
Adaptive sampling rate
Energy-aware routing
Query sharing among similar requests
Selection of suitable aggregation points
Approximate query processing
Suppression of unchanged values
Optimization Goals
Reduce transmitted packets
Reduce sensing operations
Balance energy consumption
Meet response-time requirements
Improve network lifetime
7. Data Aggregation in Wireless Sensor Networks 14 Marks
Data aggregation is the process of collecting and combining readings from multiple sensor nodes to produce a compact and meaningful result before forwarding it to the sink.
Raw-data transmission wastes energy and bandwidth.
Aggregated information is easier to interpret.
Fewer packets reduce network congestion.
Aggregation can improve network lifetime.
Basic Operations
Filtering
Duplicate suppression
Summarization
Compression
Data fusion
8. Common Aggregation Functions 7 Marks
Function
Purpose
COUNT
Counts matching sensor readings or active nodes
SUM
Adds all readings
AVERAGE
Calculates mean sensor value
MIN
Returns the minimum reading
MAX
Returns the maximum reading
MEDIAN
Returns the middle value
Duplicate Suppression
Removes repeated data
Average = Sum of Sensor Readings / Number of Readings
9. Data Aggregation Architectures 14 Marks
Tree-Based Aggregation
Nodes form a routing tree. Child nodes send data to parents, which aggregate and forward it upward.
Sink
/ \
A1 A2
/ \ / \
N1 N2 N3 N4
Cluster-Based Aggregation
Cluster members send readings to a cluster head, which aggregates and forwards data.
Chain-Based Aggregation
Nodes form a chain, and each node combines its data with data received from a neighbor.
Grid-Based Aggregation
The sensing region is divided into grids, and selected nodes aggregate data within each grid.
Centralized Aggregation
All raw readings are sent directly to one sink for processing.
10. Data Aggregation Techniques 14 Marks
Temporal aggregation: Combines readings collected over time.
Spatial aggregation: Combines readings from nearby nodes.
Hierarchical aggregation: Aggregates data at multiple network levels.
Event-based aggregation: Combines reports related to the same event.
Lossless aggregation: Preserves all required information.
Lossy aggregation: Reduces data size while allowing controlled information loss.
Secure aggregation: Protects readings and aggregated results from attacks.
Advantages
Energy saving
Reduced bandwidth usage
Lower congestion
Improved scalability
Reduced redundant information
Limitations
Loss of individual readings
Additional processing cost
Delay at aggregation points
Aggregator failure
Security and trust issues
11. Challenges in Data Aggregation 14 Marks
Selection of aggregation points
Synchronization of readings
Accuracy and information loss
Dynamic network topology
Node and link failures
Aggregation delay
Different data formats
Malicious or false data
Privacy protection
Balancing computation and communication energy
Duplicate detection
Handling missing readings
12. Node Localization in Wireless Sensor Networks 14 Marks
Node localization is the process of estimating or determining the physical position of a sensor node within the deployment area.
Some nodes called anchors or beacons know their positions. Unknown sensor nodes estimate their locations using measurements or connectivity information from these anchors.
Anchor A (*) Anchor B (*)
\ /
\ /
\ /
Unknown Node (?)
|
|
Anchor C (*)
Output
The estimated position may be represented as two-dimensional coordinates (x, y), three-dimensional coordinates (x, y, z), or a symbolic region such as “Room 4”.
13. Need and Applications of Localization 14 Marks
Associate sensed data with physical location.
Support geographic routing.
Track objects, vehicles, animals or people.
Detect and locate environmental events.
Improve coverage and deployment planning.
Support location-based queries.
Enable rescue and emergency applications.
Assist mobile robots and autonomous systems.
Identify failed or compromised nodes.
A fire-temperature reading becomes useful only when the system also knows where the high temperature was detected.
14. Important Localization Terminology 7 Marks
Anchor or beacon node: Node whose position is known.
Unknown node: Node whose position must be estimated.
Range: Estimated distance between two nodes.
Bearing: Estimated direction or angle toward another node.
Connectivity: Information about which nodes can communicate.
Localization error: Difference between estimated and actual position.
Reference point: Known position used for estimation.
Localization Error = Distance between Actual Position and Estimated Position
15. Challenges of Node Localization Technologies 14 Marks
Limited energy: Measurement and message exchange consume power.
Cost: Equipping every node with GPS is expensive.
Indoor operation: GPS signals may be weak or unavailable.
Signal variation: Obstacles, fading and interference affect measurements.
Clock synchronization: Time-based methods require accurate clocks.
Anchor placement: Poor anchor distribution reduces accuracy.
Scalability: Algorithms must work with many nodes.
Uses measured distance or angle information between nodes.
Range-Free Localization
Uses connectivity, hop count or neighborhood information without direct distance measurement.
Basis
Range-Based
Range-Free
Measurement
Distance or angle
Connectivity or hop count
Hardware
May require additional hardware
Usually no special hardware
Accuracy
Generally higher
Generally lower
Cost
Higher
Lower
Examples
RSSI, ToA, TDoA, AoA
DV-Hop, Centroid, APIT
17. Ranging Techniques for Wireless Sensor Networks 14 Marks
Ranging is the process of estimating distance or direction between sensor nodes using properties of received signals.
Main Ranging Techniques
Received Signal Strength Indicator
Time of Arrival
Time Difference of Arrival
Angle of Arrival
Round-Trip Time
Selection Factors
Required accuracy
Hardware cost
Energy consumption
Synchronization requirement
Indoor or outdoor environment
Line-of-sight availability
18. Received Signal Strength Indicator (RSSI) 14 Marks
RSSI estimates distance from the received radio-signal power. Signal strength generally decreases as distance increases.
Received Power decreases as Distance increases
Working
A transmitter sends a radio signal.
The receiver measures signal strength.
A propagation model converts signal strength into distance.
Distances from multiple anchors are used to estimate position.
Advantages
No additional ranging hardware
Low implementation cost
Available in many radio transceivers
Limitations
Strongly affected by obstacles and multipath.
Environmental changes reduce accuracy.
Requires calibration.
19. Time of Arrival (ToA) 14 Marks
Time of Arrival estimates distance by measuring the time taken by a signal to travel from transmitter to receiver.
Distance = Signal Propagation Speed × Travel Time
Working
Transmission time is known.
Receiver records signal-arrival time.
Travel time is calculated.
Distance is estimated using signal speed.
Advantages
Can provide high accuracy
Direct distance estimation
Limitations
Requires accurate clock synchronization.
Hardware may be costly.
Multipath and non-line-of-sight signals introduce error.
20. Time Difference of Arrival (TDoA) 14 Marks
TDoA estimates distance or position using the difference in arrival times of two signals having different propagation speeds, or the arrival-time difference at multiple receivers.
Common WSN Approach
A node may transmit radio and ultrasound signals at nearly the same time. Radio arrives quickly, while ultrasound arrives later. The time difference estimates distance.
May reduce strict transmitter-clock synchronization
Limitations
Requires additional hardware.
Ultrasound has limited range.
Environmental conditions affect sound speed.
21. Angle of Arrival (AoA) 14 Marks
Angle of Arrival estimates the direction from which a signal reaches a receiver.
Incoming Signal
\
\ Angle θ
\
[ Receiver Array ]
Working
An antenna or microphone array receives the signal.
Differences between array elements are measured.
The arrival angle is estimated.
Angles from multiple anchors determine node position.
Advantages
Provides directional information
Can locate a node using fewer anchors
Limitations
Requires directional antennas or arrays.
Hardware and processing cost are high.
Reflections affect accuracy.
22. Trilateration 14 Marks
Trilateration determines an unknown position using its measured distances from at least three known anchor nodes in a two-dimensional area.
Anchor A (x1,y1) Anchor B (x2,y2)
○-------------------○
\ ? /
r1\ Node /r2
\ /
\ /
○ Anchor C
(x3,y3)
r3
Basic Principle
Each anchor defines a circle whose radius equals the measured distance. The intersection of three circles estimates the unknown node position.
(x - xi)² + (y - yi)² = ri²
Requirements
At least three non-collinear anchors in 2D
At least four non-coplanar anchors in 3D
Reliable distance estimates
23. Triangulation 14 Marks
Triangulation determines a node's location using measured angles from known reference points.
Anchor A Anchor B
○ \ θ1 θ2 / ○
\ /
\ /
\ /
Unknown Node
Working
Angles are measured from two or more anchors.
Lines are extended in the measured directions.
Their intersection estimates the unknown position.
Trilateration vs Triangulation
Basis
Trilateration
Triangulation
Uses
Distance measurements
Angle measurements
Typical input
RSSI, ToA or TDoA ranges
AoA measurements
Hardware
Ranging support
Directional array support
Geometry
Circle intersection
Line or angle intersection
24. Wireless Localization Algorithms 14 Marks
Range-Based Algorithms
Trilateration
Multilateration
Triangulation
Maximum-likelihood estimation
Range-Free Algorithms
Centroid localization
DV-Hop
APIT
Hop-based and connectivity-based methods
Centralized Algorithms
Nodes send measurements to a central sink that calculates positions.
Distributed Algorithms
Sensor nodes estimate positions locally or cooperatively.
Approach
Advantage
Limitation
Centralized
Can run complex algorithms
High communication and central dependency
Distributed
Scalable and local processing
Limited by node resources
25. DV-Hop Localization Algorithm 14 Marks
DV-Hop is a range-free localization algorithm that estimates distance from the number of communication hops between unknown nodes and anchors.
Steps
Anchor nodes broadcast their positions and hop count.
Each node stores the minimum hop count to each anchor.
Anchors calculate average physical distance per hop.
Average hop distance is distributed through the network.
Unknown nodes estimate distance to anchors.
Trilateration estimates the final position.
Estimated Distance = Minimum Hop Count × Average Distance per Hop
Advantages
No special ranging hardware
Suitable for large networks
Simple connectivity-based operation
Limitations
Lower accuracy in irregular networks
Error increases with non-uniform node density
Requires several anchors
26. Centroid Localization Algorithm 7 Marks
The centroid algorithm estimates an unknown node's position by averaging the coordinates of all anchor nodes it can hear.
Estimated x = Sum of Anchor x Coordinates / Number of Anchors
Estimated y = Sum of Anchor y Coordinates / Number of Anchors
Advantages
Very simple
No distance measurement
Low computation cost
Limitations
Accuracy depends on anchor placement.
Ignores actual distance from anchors.
Requires enough nearby anchors.
27. APIT Localization Algorithm 14 Marks
APIT stands for Approximate Point-In-Triangulation. It estimates whether an unknown node lies inside or outside triangles formed by combinations of anchor nodes.
Working
Choose three anchor nodes to form a triangle.
Estimate whether the unknown node lies inside the triangle.
Repeat for many anchor combinations.
Find the overlapping region of all positive triangles.
Use the center of the overlapping area as the estimated position.
Anchor A
/\
/ \
/ ? \
/______\
B C
? = Unknown Node inside anchor triangle
Advantages
Range-free operation
No special measurement hardware
Suitable for dense networks
Limitations
Requires many anchor nodes.
Accuracy depends on node density and triangle geometry.
Point-in-triangle estimation may contain errors.
28. Comparison of Ranging and Localization Techniques 14 Marks
Technique
Measurement
Hardware Cost
Typical Accuracy
Main Limitation
RSSI
Signal strength
Low
Low to moderate
Environmental variation
ToA
Travel time
Moderate to high
High
Clock synchronization
TDoA
Arrival-time difference
High
High
Extra hardware
AoA
Signal angle
High
High
Antenna-array requirement
DV-Hop
Hop count
Low
Moderate
Topology-dependent error
Centroid
Anchor connectivity
Low
Low
Anchor distribution
APIT
Anchor triangles
Low
Moderate
Requires dense anchors
Unit 3 Quick Revision
Query processing converts a user request into distributed sensing operations.
Queries may be snapshot, continuous, historical, event-driven or aggregate.
Query optimization reduces sensing and communication cost.
Data aggregation combines multiple readings into a compact result.
Common functions are count, sum, average, minimum and maximum.
Aggregation may be tree-based, cluster-based, chain-based or grid-based.
Localization determines a sensor node's physical position.
Anchor nodes know their positions; unknown nodes estimate theirs.
Range-based methods use distance or angle measurements.
Range-free methods use connectivity and hop information.
DV-Hop, Centroid and APIT are important range-free algorithms.
Important RGPV Exam Questions
Long Answer Questions
Define query processing in WSN and explain its complete working.
Explain different types of queries used in Wireless Sensor Networks.
Discuss query optimization techniques for WSN.
Define data aggregation and explain its need and advantages.
Explain common aggregation functions and architectures.
Discuss different data-aggregation techniques and challenges.
Define node localization and explain its importance in WSN.
Discuss the major challenges of node-localization technologies.
Classify localization techniques into range-based and range-free methods.
Explain RSSI-based ranging with advantages and limitations.
Explain Time of Arrival and Time Difference of Arrival techniques.
Explain Angle of Arrival localization.
Explain trilateration with a neat diagram.
Differentiate trilateration and triangulation.
Explain centralized and distributed localization algorithms.
Explain DV-Hop localization algorithm step by step.
Explain Centroid localization algorithm.
Explain APIT localization algorithm with a diagram.
Compare RSSI, ToA, TDoA and AoA techniques.
Short Answer Questions
Define query processing.
What is a continuous query?
What is an aggregate query?
Define data aggregation.
Name four aggregation functions.
What is an anchor node?
Define localization error.
What is range-based localization?
What is range-free localization?
Define RSSI.
What is ToA?
What is TDoA?
Define AoA.
What is trilateration?
What is DV-Hop?
What is APIT?
Exam Tip: Query-processing steps, data-aggregation architecture, localization classification, RSSI/ToA/TDoA comparison, trilateration and DV-Hop are high-priority Unit 3 topics.
Download Study Resources
Unit 3 PDF
Printable Unit 3 notes will be available soon.
Coming Soon
Important Diagrams
Aggregation, ranging and localization diagrams.
Coming Soon
Important Questions
Expected Unit 3 RGPV questions.
Coming Soon
Frequently Asked Questions
Query processing user ki information request ko sensor nodes tak distribute karta hai, relevant data collect karta hai aur processed result sink ke through user ko deta hai.
Data aggregation duplicate aur similar readings ko combine karke packets kam karti hai, jisse energy aur bandwidth save hoti hai.
Anchor ya beacon node aisa sensor node hota hai jisko apni physical position already pata hoti hai.
Range-based techniques distance ya angle measurement use karti hain, jabki range-free techniques connectivity aur hop-count information use karti hain.
RSSI obstacles, interference, multipath aur environmental changes se strongly affect hota hai, isliye distance estimation error aa sakta hai.
Nahi. Trilateration distance measurements use karta hai, jabki triangulation angle measurements use karta hai.
DV-Hop minimum hop count ko average distance per hop se multiply karke anchors tak estimated distance calculate karta hai.