WIRELESS SENSOR NETWORKS

- AS PER BPUT SYLLABUS FOR B.TECH.(CS STREAM) 6TH SEMESTER

“The distance between dreams and reality is called action.”
— Brian Tracy

Module-IV

Dr. Abhaya Kumar Samal

Dean(School of Computing), Dean(Project & Consultancy)
Professor in Comp. Sc. Engg.
AGENDA
Module-IV (9 hours):
• Security (11):
• Challenges of Security in WSN (11.2), Security Attacks in Sensor Networks (11.3), Protocols
and Mechanisms for Security (11.4), Introduction to IEEE 802.15.4 and Zig Bee Security (11.6)
• Sensor Network Databases (6):
• Sensor Database Challenges (6.1), Querying the physical environment (6.2), Query interfaces
(6.3), High-level database organization (6.4), In-network Aggregation (6.5), Data Centric
Storage (6.6), Distributed and Hierarchical aggregation (6.8)
• Introduction to discrete event network simulators
Text Book:
1. Fundamentals of Wireless Sensor Network: Theory and Practice;
Waltenegus Dargie and Christian Poellabauer, Wiley Publication, 2010
2. Wireless Sensor Networks: An Information Processing Approach;
Feng Zhao, Leonidas Guibas, Morgan Kaufmann Series in Networking 2004
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHAPTER 11: SECURITY – ROADMAP
• Security fundamentals
• Security challenges
• Security attacks
• Security protocols and mechanisms
• IEEE 802.15.4 and ZigBee security

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
FUNDAMENTALS
 Security and privacy are big challenges for any type of computing and
networking environment
 Well-known CIA security model:
o Confidentiality
 ensure that only the intended receiver can read/interpret a message
 unauthorized access is prevented
o Integrity
 ensure that a message cannot be modified
 unauthorized individuals should not be able to destroy/alter message
o Availability
 ensure that system/network is able to perform its tasks without interruption
 often measured in terms of percentages of up/down time

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
EXAMPLES
 Confidentiality:
o eavesdropping: unauthorized message
reception
 Integrity:
o man-in-the-middle attack: unauthorized
individual/system positions itself
between sender and receiver to
intercept, modify, and retransmit
messages
 Availability:
o denial-of-service attack: attempt to
disrupt transmission or service
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MORE TERMINOLOGY
 Authentication
o process of establishing or confirming the identity of user/device
o ensures that message came from who it claims to have come from
 Nonrepudiation
o process of proving that person/device has performed a certain
transaction/transmission
 Digital signatures
o often used to support authentication, nonrepudiation, and integrity

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CRYPTOGRAPHY
 Process of protecting information using encoding/decoding techniques
 Symmetric key cryptography
o single key shared between communicating parties
o simple example: shift cipher (key fixed shift in alphabet)
o challenge: secure distribution of shared key
o examples: DES, AES, IDEA
 Public key cryptography
o secret key: will never be shared with anyone else
o public key: can be shared freely
o message encrypted with secret key can only be decrypted with corresponding public key
(e.g., for authenticating the sender)
o message encrypted with public key can only be decrypted with corresponding secret key
(e.g., for providing confidentiality)
o examples: RSA, Diffie-Hellman agreement protocol

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHALLENGES OF SECURITY IN WSNS
 Resource constraints
o limited computational, networking, and storage capabilities of sensors
o energy constraints of sensors
 Lack of central control
o large WSNs often don't have centralized control
o requires distributed/decentralized security solutions
 Remote location
o sensors often left unattended
o difficult to prevent unauthorized physical access and tampering
 Error-prone communication
o difficult to distinguish wireless communication errors from attacks

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SECURITY IN WSNS
 WSN characteristics that facilitate security:
 self-managing and self-repairing nature
 redundancy
 Data freshness problem
 WSN security must ensure that sensor data are recent (and not replays of old data)
 particularly important for key distribution schemes
 WSNs provide more opportunities for attacks than other networks
 many sensor protocols require location information
 many sensor nodes require accurate time synchronization
 both can be affected by modifying, injecting, dropping messages (e.g. beacons) carrying such
information

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DENIAL-OF-SERVICE (DOS)
 Attempt to stop network/system from functioning or providing a service
 Physical Layer DoS
o jamming attack
 interfere with the radio frequencies of a WSN
 even small numbers of attacking nodes can be effective if well positioned (e.g., close to an
important node such as a BS) or if their signals are strong
 countermeasure: spread-spectrum communication (e.g., FHSS)
o tampering attack
 attacker obtains physical access to sensor node
 used to modify/destroy node, obtain sensitive information or use as entry points for further
attacks into the network
 countermeasures: tamper-proof materials and enclosures, disable device when attack detected

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DENIAL-OF-SERVICE (DOS)
 Link Layer DoS
o collision attack
 attempt to interfere with packet transmissions
 causes costly exponential backoff procedures and retransmissions
 often tries to cause collisions near the end of a frame, requiring retransmission of entire frame
o exhaustion attack
 attacks (such as collision attack) with the goal of premature depletion of a sensor's energy
sources
 example: issue RTS message to prompt CTS response from another node (exploiting handshake
techniques)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
ATTACKS ON ROUTING
 Blackhole attack
o malicious node on a route simply drops all packets
 Selective forwarding attack
o similar to blackhole attack, but not all traffic is dropped
o more difficult to detect (hard to distinguish attack from poor connectivity)
 Rushing attack
o exploits route discovery techniques of on-demand protocols
o route request packets are rushed towards destination, increasing the malicious node's probability to
be on the selected route
 Sinkhole attack
o node attempts to position itself on as many network flows as possible
 Sybil attack
o attacker claims to have multiple identities or locations
 Wormhole attack
o out-of-band (bandwidth-rich) connection between attackers used to face short path to the gateway,
attracting many flows to these nodes

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
ATTACKS ON TRANSPORT LAYER
 Flooding attack
o exploits fact that many transport protocols maintain state information and are
therefore vulnerable to memory exhaustion
o example: attacker makes many (incomplete) connection requests, forcing a node to
allocate more and more resources
 Desynchronization attack
o attempt to disrupt communication between nodes by repeatedly forging messages
to these nodes
o example: fake packets carry old sequence numbers to make a node believe that its
previous transmissions were not correctly received

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PRIVACY ATTACKS
 Attempts to obtain sensitive information collected and communicated in
WSNs
 Eavesdropping
o made easy by broadcast nature of wireless networks
 Traffic analysis
o used to identify sensor nodes of interest (data of interest), sensor nodes that are
vulnerable, and sensor nodes that are critical to the correct operation of the entire
network (e.g., gateway devices, cluster heads)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SYMMETRIC VERSUS PUBLIC KEY
 Public key cryptography
o used to provide confidentiality, integrity, and authentication
o computationally expensive
o some implementations for resource-constrained devices exist (ECC, liptic curve
cryptography)
 Symmetric key cryptography
o more resource-efficient
o problem of key distribution

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DEFENSES AGAINST DOS ATTACKS
 Jamming attacks
o isolate affected region by re-routing traffic
o use spread-spectrum techniques
 Collision and exhaustion attacks
o error-correcting codes
o rate-limiting schemes
 Spoofing and alteration attacks
o message authentication codes (MAC)
 Path-based DoS attacks
o attacker overwhelms nodes by flooding a multi-hop end-to-end communication
path with replayed or injected packets
o one-way hash chains can be used to validate received packets
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DEFENSES AGAINST ROUTING ATTACKS
 Attacks from "outside" versus "inside" the network
o link-layer encryption and authentication can prevent adversary from joining a network,
preventing many possible routing attacks
o these techniques may be ineffective if network is attacked from the inside (e.g., using a
compromised node)
 Sybil attacks
o sensor nodes can share unique symmetric key with a trusted base station to verify each
other's identity
o base station can also limit the number of neighbors a node is allowed to have (i.e., a
compromised node can communicate with only a few other nodes)
 Sinkhole attacks
o difficult to defend against where protocols are used that establish routes based on
Information that it difficult to verify (e.g., energy)
o easier for routes based on minimum hop counts, but hop counts can be misrepresented
through a wormhole
o with geographic routing, it is difficult to redirect traffic elsewhere to create a sinkhole
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DEFENSES AGAINST ROUTING ATTACKS
 Rushing attacks
o secure neighbor detection approach can be used to allow sender and receiver of a
route request to verify that the other party is in fact within normal transmission
range
o example of a three-round mutual authentication protocol:
 sender sends a neighbor solicitation packet
 receiver responds with neighbor reply packet
 sender sends a neighbor verification message (which includes broadcast authentication of a
timestamp and the link from the source to the destination)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SECURITY PROTOCOLS FOR SENSOR NETWORKS
 SPINS provides:
o Secure Network Encryption Protocol (SNEP) for confidentiality, two-party data
authentication, and data freshness
o a "micro" version of the Timed, Efficient, Streaming, Loss-tolerant Authentication
protocol (µTESLA) for authentication for data broadcast
o assumption is that every node has a secret key shared with the base station

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SECURITY PROTOCOLS FOR SENSOR NETWORKS
 Secure Network Encryption Protocol (SNEP)
o symmetric security (same message is encrypted differently each time)
o replay protection
o low communication overhead
o uses MAC for two-party authentication and integrity
o nodes A and B share a secret master key
o master key used to derive four independent keys using pseudorandom function
 two keys use encryption of messages in each direction (KAB and KBA)
 two keys are used as message integrity codes (K’AB and K’BA)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SECURITY PROTOCOLS FOR SENSOR NETWORKS
 µTESLA
o extension of TESLA protocol (by considering resource limitations)
o focuses on need for authenticated broadcast in WSNs
o relies on symmetric mechanisms provided by SNEP to authenticate first packet in broadcast
message
o TESLA uses digital signatures to authenticate initial packet and has an overhead of 24 bytes
per packet
o µTESLA emulates asymmetric cryptographic mechanism through a delayed disclosure of
symmetric keys
o µTESLA assumes that base station (BS) and sensor nodes are loosely time synchronized and
each sensor knows upper bound on maximum synchronization error
o when BS sends a message, it authenticates it by computing a MAC on the packet with
secret key when a node receives the packet, node knows that MAC key is only known to BS
o node stores packet until the BS broadcasts the verification key to all receivers

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
TINYSEC
 Lightweight and generic link-layer security package
 Can easily be integrated into sensor network applications
 Supports two different security options.
o authenticated encryption (TinySec-AE)
 data payload is encrypted
 MAC is used to authenticate packet
o authentication only (TinySec-Auth)
 entire packet is authenticated with MAC
 payload is left unencrypted
 Relies on cipher block chaining (CBC) With specially formatted 8-byte
initialization vector (IV) for encryption
 Relies on efficient and fast cipher block chaining construction (CBC-MAC) for
computing and verifying MACs
o using block cipher, number of cryptographic primitives that must be implemented is
minimized
o length of MAC is 4 bytes (attacker must try at most 232 blind forgeries)
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
LOCALIZED ENCRYPTION AND AUTHENTICATION PROTOCOL (LEAP)
 LEAP is a key management protocol for sensor networks, designed to support
in-network processing
 Key observation is that different types of packets (control versus data) have
different security requirements
 LEAP provides four keying mechanisms:
o individual keys
 every node has unique key shared with BS
 key used for confidentiality and MAC
o group keys
 globally shared key used by BS to communicate with entire network
o cluster keys
 shared key between sensor and its neighbors
 used for securing local broadcast messages
o pairwise shared keys
 shared key between sensor and one of its immediate neighbors
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
LOCALIZED ENCRYPTION AND AUTHENTICATION PROTOCOL
 LEAP also provides a technique for local broadcast authentication
o every node generates a one-way key chain of certain length
o every node transmits the first key in the chain to each neighbor (encrypted with the
pairwise shared key)
o whenever a node sends a message, it takes the next key from the chain (each key is
called an AUTH key) and attaches it to message
o keys are disclosed in reverse order of their generation and a receiver can verify the
message based on the first received key or a recently disclosed AUTH key

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
IEEE 802.15.4
 Four basic security models:
o access control
o message integrity
o message confidentiality
o replay protection
 Security is handled by the MAC layer
 Application can choose specific security requirements by setting
appropriate parameters in the radio stack (default: no security)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
IEEE 802.15 4: SECURITY SUITES

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
ZIGBEE SECURITY
 Introduces the concept of trust center (responsibility assumed by the
ZigBee coordinator)
o responsible for authentication of devices wishing to join network (trust manager)
o responsible for maintaining and distributing keys (network manager)
o responsible for enabling end-to-end security (configuration manager)
 Residential mode
o trust center allows nodes to join network, but does not establish keys with the
network devices
 Commercial mode
o trust center generates and maintains keys and freshness counters with every device
in the network
o large memory cost
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
ZIGBEE SECURITY
 ZigBee uses the CCM* mode for security, which is a combination of CTR
mode and CBC-MAC mode
 Compared to CCM, CCM* offers encryption-only and integrity-only
capabilities
 ZigBee has several levels of security, including:
o no security
o encryption only
o authentication only
o encryption and authentication
 ZigBee's MAC can vary from 4 to 16 bytes

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHAPTER 6: SENSOR NETWORK DATABASES – ROADMAP
 Sensor Database Challenges
 Querying the physical environment
 Query interfaces
 High-level database organization
 In-network Aggregation
 Data Centric Storage
 Distributed and Hierarchical aggregation

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SENSOR NETWORK DATABASES – PRELUDE
• Sensor network as a distributed database
• collects physical measurements about the environment,
• indexes them, and then
• serves queries from users and other applications external to or from within the
network
• The Key Aspects of Concern of Sensor Network from Database Perspective:
1. how sensor data is organized and stored after sensing actions,
2. what user interfaces to the sensor database may look like, and
3. how queries are processed and served in an efficient manner

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SENSOR NETWORK DATABASES – PRELUDE
• Advantage of the database approach is that it provides a separation
between:
• the logical view (naming, access, operations) of the data held by the sensor network
and
• the actual implementation of these operations on the physical network.

• Diverse sensor network users and applications can focus on:

• the logical structure of the queries they intend to pose and
• are relatively isolated from the details of physical storage and data networking on
the volatile physical infrastructure of the network (sensors can fail, links come and
go, and so on).

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SENSOR NETWORK DATABASES – PRELUDE
Classical database management system (DBMS)
• data is stored in a centralized location
• structure and constraints of the data format (schema) are typically defined
or modified by a DBA using a DDL
• DDL compiler translates these definitions into metadata, a data structure
describing the structure of the database data and the constraints they
must satisfy
• most databases employ relational schemas organizing data into tables whose
• columns are labeled by data attributes, and
• rows are record tuples

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SENSOR NETWORK DATABASES – PRELUDE
• Database is updated through transactions with guaranteed Automicity and
• In apparent isolation from other transactions (concurrency control).
• User or application is shielded from the details of how data is physically
stored on hard disks and other devices
• A user queries the database in a high-level logical query language (SQL)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SENSOR NETWORK DATABASES – PRELUDE
• In distributed database systems
• data storage may be allocated among several geographically separated locations
• need for distribution arises in many contexts - businesses with geographically
dispersed facilities connected by a communications network.
• Data distribution along with data replication makes the entire system:
• more robust to failures
• can provide increased bandwidth and throughput
• greater data availability
• On the other hand, a distributed database makes the job of the query processor
significantly harder
• Distributed databases can vary widely in regards to the number of physical nodes
involved.
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SENSOR DATABASES CHALLENGES
 Each sensor in a sensor network takes time-stamped measurements of
physical phenomena
 A sensor contains descriptions of its characteristics
 Sensor network database comprises all of the above data from every
sensor
 Two approaches to database implementation:
1. transfer all these data to one or a small number of external warehouses, where a
traditional DBMS system could be deployed, or
2. store the data within the network itself and allow queries to be injected
anywhere in the network
 These differences generate several new challenges for sensor network
databases
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SENSOR DATABASES CHALLENGES
• The system as a whole is highly volatile
• nodes may be depleted, links may go down, and so on
• yet the SNDBS has to hide all this from the end user or application
• provide the illusion of a stable, robust environment where queries run to completion
• Relational tables are not static since new data is continuously being sensed
• best regarded as append-only streams where certain useful reordering operations are
no longer available (such as sorting).
• The high energy cost of communication encourages in-networking processing
during query execution
• Access to data may be hampered by arbitrarily long delays, and the arrival
rates of input data to a database operator can be highly variable (like a join).

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SENSOR DATABASES CHALLENGES
• Limited storage on nodes and high communication costs imply that older
data has to be discarded.
• The database system can try to maintain more high-level statistical
summaries of the deleted information, so that queries about the past can
still be answered in some form.
• Classical metrics of database system performance may have to be adjusted
in the WSN context because of high variance in following quantities, such
as:
• throughput (number of queries executable per unit of time) or
• delay (maximum time elapsed for answering a query).

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SENSOR DATABASES CHALLENGES
• There are also significant differences in data at the logical level between
• sensor network data and
• other databases
• Inherently measurements include errors such as
• interference from other signals, device noise, and the like
• exact queries do not make much sense in sensor networks
• Instead, range queries (certain attributes lie in certain intervals) and
probabilistic or approximate queries are more appropriate.

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SENSOR DATABASES CHALLENGES
• Additional operators have to be added to the query language to specify
durations and sampling rates for the data to be acquired
• Sensor networks are deployed to monitor the environment and report
exceptional conditions or other events of interest.
• Thus it is important to have operators for correlating sensor readings and
comparing them with past statistics.

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
QUERYING THE PHYSICAL ENVIRONMENT
• Expressing queries to a SNDB at a logical, declarative level, using relational
languages such as SQL is advantageous
• HLL interfaces allow non-expert users to easily interact with the database
• Query formation in this manner helps
• Independence from the physical structure or organization of a sensor network
• shields users from the implementation details of the database system
• For example
• Actual layout and connectivity of a network may change over the time window within which a
query is processed
• For a non-expert user It would be difficult to anticipate all the possible events and design the
corresponding query execution plan.

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
QUERYING THE PHYSICAL ENVIRONMENT – SQL QUERY
• Consider WSN of a flood warning system for example
• A user from a state emergency management agency may send a query to the
flood sensor database:
• “For the next three hours, retrieve every 10 minutes the maximum rainfall level in each
county in Southern California, if it is greater than 3.0 inches.”
• Example: a long-running, monitoring query, and can be expressed in the following SQL-like syntax:

SELECT max(Rainfall_Level), county

FROM sensors
WHERE state = California
GROUP BY county
HAVING max(Rainfall_Level) > 3.0in
DURATION [now, now+180 min]
SAMPLING PERIOD 10 min

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
QUERYING THE PHYSICAL ENVIRONMENT – SQL QUERY
• Difference from the standard SQL syntax
• addition of the duration clause that specifies the period during which data is to be
collected
• addition of the sampling period clause, which specifies the frequency at which the
query results are returned
• The query is expressed over a single table comprising all the sensors in the
network, each of which corresponds to a row in the table.
• For SQL-style query processing, It is assumed that the SNDB schema is known at a
fixed BS

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
QUERYING THE PHYSICAL ENVIRONMENT – SQL QUERY
• A query may originate from any node in a peer-to-peer system
• For this the SNDB schema have to be broadcasted to every node
• Previous query is example of an aggregate query:
• the query result is computed by integrating data from a set of sensors
• A query can also ask for relations or correlations among a set of events
• For example,
• “Sound an alarm whenever two sensors within 10 meters of each other simultaneously detect
an abnormal temperature”
• Or for example spawn sub-queries
• “Obtain an ID whenever sensors in region R detect a person.”

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
QUERYING THE PHYSICAL ENVIRONMENT – TYPES OF SQL QUERY
• continuous queries – In the previous example, the query has to run over an
extended time window to report results
• snapshot queries report results from the data in the network at a given
point in time
• For example, “Retrieve the current rainfall level for all sensors in Cuttack District”
• historical queries may ask for aggregate information over historical data
• For example, “Display the average rainfall level at all sensors for the last three
months of the previous year”

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
QUERYING THE PHYSICAL ENVIRONMENT – TYPES OF SQL QUERY
• What the queries on sensor networks may need can be summarized as:
• Aggregate data over a group of sensors or a time window.
• Contain conditions restricting the set of sensors from contributing data.
• Correlate data from different sensors.
• Trigger data collection or signal processing on sensor nodes.
• Spawn subqueries as necessary.
• To efficiently support each type of these queries, one must understand:
• how the data organization and query execution are to be meshed with the spatially
distributed processing and communication framework of a sensor network

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
QUERY INTERFACES
Cougar SNDB is an example of how a SNDB query interface appears
• It maintains an SQL-type query interface for users at a front-end server,
connected to a WSN.
• Distributed query execution is optimized for both resource usage and
reaction time.
• Attempts to preserve the abstraction and familiarity of a traditional data
warehousing system in an efficient manner as much as possible

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
QUERY INTERFACES – COUGAR SNDB
• Cougar represents each type of sensor in a network as an abstract data
type (ADT) as in most modern object-relational databases (ORDB)
• An ADT provides controlled access to encapsulated data through a well-
defined set of access functions.
• An ADT object in the Cougar database corresponds to a physical sensor in
the real world.
• In the Cougar data model, sensor measurements are represented as a time
series data, where each measurement is associated with a time stamp
• Cougar assumes that the nodes are time synchronized with one another
reasonably well, so that there is no misalignment when multiple time
series are aggregated.
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
QUERY INTERFACES – PROBABILISTIC QUERIES
• Sensor data invariably contains measurement uncertainty due to device
noise or environmental perturbations.
• Thus requests for exact sensor reading values need to be replaced with a
formalism that allows expression of this inherent uncertainty.
• As a measurement typically is subject to many small and random
perturbations, one way to model such an uncertainty in a database system
is to introduce a Gaussian ADT (GADT), which models the uncertainty as a
continuous probability distribution function (pdf) over possible
measurement values.
• Just like an ordinary ADT in a database, a GADT is a first-class object, with a
set of well-defined functions such as Prob, Diff, and Conf, whose semantics
are defined in.
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
HIGH-LEVEL DATABASE ORGANIZATION
• To be able to efficiently process queries, the design of a sensor database
must be coupled:
• with the underlying routing infrastructure and
• with the application characteristics
• This is to support its data generation and access patterns.
• To illustrate the tradeoffs, let us examine two different ways in which data
from a WSN might be stored.

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
HIGH-LEVEL DATABASE ORGANIZATION – CENTRALIZED WAREHOUSING
• In this approach, each sensor forwards its data to a central server or
warehouse connected to the network via an access point.
• Assuming reasonably uniform distribution of the nodes, we use the
average routing distance (i.e., number of hops) from a node to the access
point
• However, there are distinct disadvantages to this centralized approach.
• The nodes near the access point become traffic hot spots and central points of
failure;
• plus, they may be depleted of energy prematurely.

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
HIGH-LEVEL DATABASE ORGANIZATION – CENTRALIZED WAREHOUSING
• This approach does not take advantage of in-network aggregation of data
to reduce the communication load when only aggregate data needs to be
reported.
• Also, sampling rates have to be set to be the highest that might be needed
for any potential query
• This possibly further burdening the network with unnecessary traffic.

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
HIGH-LEVEL DATABASE ORGANIZATION – IN-NETWORK STORAGE
• This is an attractive alternative to Centralized Warehousing Approach
• This store the data within the network, using the so-called in-network storage.
• At the center of the design here is the appropriate choice of storage points for
the data, so that the overhead to store and access the data is minimized and the
overall load is balanced across the network.
• The communication cost for storing the data remains comparable to that of the
warehousing approach.
• The query time, however, depends strongly on how the data is indexed.
• Most importantly
• the in-network storage allows data to be aggregated before it is sent to an external query,
• takes advantage of locality of information for in-network queries, and,
• if designed carefully, load-balances the database costs across the nodes.
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
HIGH-LEVEL DATABASE ORGANIZATION – PERFORMANCE METRICS
The following metrics are adapted for general SNDB:
• Network usage is characterized by
• Total usage: The total number of packets sent in the network.
• Hot spot usage: The maximal number of packets processed by any particular node.
The hot spot usage impacts the overall network lifetime before partitioning.
• Pre-processing time: The time taken to construct an index.
• Storage space requirement: The storage for the data and index.
• Query time: The time taken to process a query, assemble an answer, and
return this answer.
• Throughput: The average number of queries processed per unit of time.
• Update and maintenance cost: Costs such as processing sensor data
insertions, deletions, or repairs when nodes fail.
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
HIGH-LEVEL DATABASE ORGANIZATION – PERFORMANCE METRICS
To summarize, a SNDB differs from a traditional centralized DBMS in that:
• the resources are severely constrained and
• querying processing is tightly coupled with networking and application
semantics.
• When designing a sensor database, we desire the following properties:
1. Persistence: Data stored in the system must remain available to queries,
despite sensor node failures and changes in the network topology.
2. Consistency: A query must be routed correctly to a node where the data
are currently stored. If this node changes, queries and stored data must
choose a new node consistently.
3. Controlled access to data: Different update operations must not undo
one another’s work, and queries must always see a valid state of the
database.
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
HIGH-LEVEL DATABASE ORGANIZATION – PERFORMANCE METRICS
To summarize, a SNDB differs from a traditional centralized DBMS in that:
• the resources are severely constrained and
• querying processing is tightly coupled with networking and application
semantics.
• When designing a sensor database, we desire the following properties:
4. Scalability in network size: As the number of nodes increases, the
system’s total storage capacity should increase, and the communication
cost of the system should not grow unduly.
5. Load balancing: Storage should not unduly burden any one node. Nor
should any node become a concentration point of communication.
6. Topological generality: The database architecture should work well on a
broad range of network topologies.
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar