PDF Version contains many figures
433-654 Sensor Networks and Applications
1. Describe major problems in every component, address features of WSN and explain major problems in one sentence.
/***********************************
Solution:
WSN features:
l Small-scale sensor nodes
l Limited power they can harvest or store
l Harsh environmental conditions
l Node failures
l Mobility of nodes
l Dynamic network topology
l Communication failures
l Heterogeneity of nodes
l Large scale of deployment
l Unattended operation
Power Supply: Most nodes are battery powered, have limited lifetime. It is almost impossible to replace battery for each node, since large quantity and deployed site.
Sensors:
Memory: Limited memory space, since node is small and low cost.
Micro Processor: Limited CPU processing power since to reserve battery and keep low cost.
Radio: Short range wireless communication, cost large amount of energy (1000 times larger than computation).
***********************************/
2. While designing algorithms to run on WSN using some generic sensors like Xbow Mote for example. What is the main constraint that we have to consider that exists in our sensors and which component and operation has effect on this.
/***********************************
Solution:
Energy is the main constraint in sensor. Since most of sensor nodes are powered by battery, the lifetime of whole system is depend on battery life. And replace battery is impossible due to large amount of nodes and deploy environment like battlefield.
Every component in sensor needs energy to work. The communication component is a big consumer. It takes 1000 times more energy to transmit data than to process it. So, to extend lifetime, the system should keep a low duty cycle and keep communication as low as possible. In this case, the in-network process and in-network data aggregation is preferred.
***********************************/
3. Multi-hop RF network for establishing WSN rather than requiring each sensor to directly connect to a base station. A multi-hop network is more power efficient. Explain it in detail.
/***********************************
Solution:
l r: r is a distance value in multi-hop style.
l Nr: Nr is the distance from sender to receiver in one-hop style.
l : The power to send message from sender to receiver.
l : The minimum receive signal strength from receiver’s view.
l : The power to send message from one sender node o another receiver node in multi-hop style.
The curve in figure above shows the signal attenuation. The power advantage of multi-hop over one-hop is:
The α value is signal attenuation constant.
***********************************/
4. What is duty cycle in WSN? What is the aim of design engineering with this parameter?
/***********************************
Solution:
For low-powered electronic device like nodes in WSN, they at least have two states “Sleep” and “Awake”. In “Awake” mode, all components in node working and consume energy. In “Sleep” mode, most of components are in energy saving mode which cost few energy. Tasks and events can awake sleeping components. The duty cycle is defined as above. The aim of WSN duty cycle is 0.1% to 1%.
***********************************/
5. What is APIT test and how does the location algorithm that we saw in class work that uses this test?
/***********************************
Solution:
APIT stands for Approximate Point-In-triangulation Test. It is a range-free location algorithm.
1. The unknown node collects location information from all neighbor landmarks.
2. Randomly select tree of them, and do a triangulation test to check whether the unknown node is in the triangle. Iteratively do this step until get desired accuracy.
3. Use centroid approach to compute all triangles and the overlapped area is the location of unknown node.
***********************************/
6. Routing data in WSN. A greedy algorithm can be utilized. Although greedy algorithms are simple and powerful, they may get stuck in local. Why this will happen? How to deal with this?
/***********************************
Solution:
If all neighbor nodes’ costs are larger than the cost of the node itself to reach a destination, but the destination is still out of reach. This is called routing void.
To deal with it, the routing void node can select the neighbor node which cost least and report this node to previous node. Next time, the previous node can choose the neighbor node to communicate rather than routing void node. Route along the perimeter of a face using right hand rule on the sub-graph.
***********************************/
7. Write a COUGAR like query language according to the statement below
“Find the max temperature level for towns in Tasmania for two hours starting from now by sampling every 10 minutes if that town also has an average humidity for 90% or above.”
/***********************************
SELECT MIN(humidity), town
FROM sensors
WHERE state = ‘Queensland’
GROUP BY town
HAVING MAX(temperature) > 30
DURATION [now, now + 600 min]
SAMPLING PERIOD 30 min
Solution:
SELECT MAX(temperature), town
FROM sensor
WHERE state=’ Tasmania’
GROUPBY town
HAVING AVG(humidity)>90
DURATION[now, now+7200]
EVERY 600
***********************************/
8. Compare tree-based and multi-path-based data aggregation schemas from at list two points of view.
/***********************************
Solution:
l Tree-based: The base station is the root of routing tree. The tree, that is utilized to distribute the query, is also utilized to collect the data. TinyDB is an example.
l Multi-path-based: To prevent failures, the same sensor value can be sent along multiple paths.
Main disadvantage of tree-based is that it can loose large sub-trees/data due to central point of failure. Multi-path-based schema consumes more energy than tree-based. And data aggregation can be applied to tree-based schema which significantly reduces energy cost. The multi-path-based schema also can do data aggregation, but will lead to multiple different approximation value when reaching sink node.
***********************************/
9. Fractional Cascading is a distributed hierarchical aggregation and storage method. Explain how Fractional Cascading works.
/***********************************
Solution:
Fractional Cascading is a distributed hierarchical aggregation and storage method.
In most cases, queries in WSN are highly spatially correlated. Because WSN measure physical phenomena and physical interaction are mostly localized in space and/ or time.
The key idea is each does not need to know the exact value of other node, but a “fraction’ information of that area. Further the node between the areas, less and coarser value the node has.
For example, Fractional Cascading works in this style:
1. Setup Quad-tree in sensor field
2. Each sensor stores values from three siblings
From P’s point of view, the P has exact value of P’s three siblings (Darkest area). P has highest value of parent’s three siblings (Darker area). P has a few knowledge of lightest area. When the query is injected into sensor field, the closer the query to the hot area, the precise value it will get.
l The total amount of information duplication across all sensors is kept small, because of the geometric decrease with distance.
l The communication costs required to build and maintain the index remain reasonable, as on the average information travels only a short distance.
l Neighboring sensors have highly correlated world views.
l It is very fast when region is local and small.
GHT stores data far away from the node generated it.
It restricted geographic flooding, but the communication cost of visiting hot spots and canonical pieces dominates the total query cost.
***********************************/
10. WSN can observe various kinds of security problems. One of these attacks is known as “Sink hole”. Describe how “Sink hole” attack works and main effect.
/***********************************
Solution:
In this attack, the adversary lures all the traffic of the network to pass through a compromised node creating a metaphorical sinkhole with the adversary at the centre. This is achieved by the routing algorithm being used. As a result, the surrounding nodes route all traffic to the base station via the compromised node.
The compromised node is yielding to other node saying: “Hello! I have best route to transmit your data!” But actually, do nothing and drop all packets. The real sink node then can not get any information.
***********************************/
11. What is SensorML? Describe the main reasons of why one may want to use SensorML.
/***********************************
Solution:
SensorML is a XML file describing sensor properties and information needed for data processing.
SensorML enables discovery and control of sensors on the Web and enables geo-location of measurements. It provides node’s performance and calibration characteristics, describes the sequence of processes by which an observation was made. It enables derived observations. It also gives function model of sensor system.
Advantages:
l Tree style, some parts can be ignored which saves time.
l Platform independent, the XML file is platform neutral.
l If some parts loose, it still works
Disadvantages:
l Verbose and redundant, data occupies a lot of space. This causes overhead in storage, energy cost, communication bandwidth, process speed and so on. The nodes right have limited capability to deal resource hungry XML.
l SensorML is a complex and developing standard.
l WSN is data-centric network, no one want to spend time on annotate nodes.
***********************************/
12. The figure below presents different strategies for routing and communication single targets state information in WSN. State advantages and disadvantages of each method.
a b c
/***********************************
Solution:
l a: Every node in the network stores and updates target state information. It is very robust. The challenges are how to maintain information consistency and it is difficult to response user’s queries effective and correct.
l b: Leader nodes are selected in the succession according to information such as vehicle movement. A leader is elected combines with measurements from nearby sensor. As the target moves, the initial node is no longer desired. The current leader handoff target state information to new elected leader until task finish. It is advantage in reducing the overall bandwidth consumption and increase the network lifetime. The main challenge is how to elect a good leader node.
l c: A fix node stores the target state from other relevant nodes through communication. The communication cost would be very high and the fix node is a single point of failure reducing the robustness of the whole task.
***********************************/
13. Why developing software in WSN a programmer can choose from different programming paradigms. We have mentioned two such. Name and describe each.
/***********************************
Solution:
l Node-centric: Programmers think of how a node should behave in environment. Node-level OS provides hardware and networking abstractions of a sensor node o programmers, or it can be a language platform, which provides a library of components to programmers. TinyOS is a node-centric OS.
l State-centric: Take PIECES (Programming and Interaction Environment for Collaborative Embedded System) as example. It contains two parts principals and port agent. Principal maintains state corresponding to certain aspects of physical phenomenon of interest. It updates state from time to time. Port agents facilitate communication between principals Agents can be active or passive. Active – pushes data autonomously to destinations; Passive – sends data only when consumers request it
***********************************/
14. What is ZigBee? Wht purpose of ZigBee? Why? What advantages and disadvantages it has? Describe ZigBee architecture and application domain.
/***********************************
Solution:
ZigBee is a suit of protocol designed for low-cost, low-power, low-date-rate and small-scale wireless devices. It is based on the IEEE 802.15.4. ZigBee is targeted at RF applications that require a low data rate, long battery life, and secure networking.
ZigBee is mainly used in monitor and control applications.
Advantage
l Network size: support mesh, star, hybrid network architecture.
l Low power consumption: Devices can run for years.
Disadvantages
l Cost still high: Like Blootooth years before.
l Interfere with other wireless protocol: Use free ISM band.
l Dynamic routing: It is lack of dynamic routing, making it impossible to build self healing networks that can restructure itself when a router or coordinator is disconnected.
l Secure transfer: Although encryption exists on the hardware level there is no support for setting the current key or performing key exchange with other nodes. These features are lacking because they where not specified in version 0.92 of the ZigBee standard.
***********************************/
Extend Question
15. Describe PDT.
/***********************************
Solution:
Pocket-Driven Trajectories (PDT) Algorithm is selectivity-aware, localized and adaptive. It is highly efficient for queries with predicates on spatially correlated attributes and long-running queries.
It aims to minimize the use of non-selected parts by computing selectivity-aware data collection paths and reconfigure spatial network efficiently when nodes can move or when they die.
Typical performance improvement of 30%−40% for selective queries.
***********************************/
16. Describe tracking issues and DEH (Distributed Euler Histogram) algorithm
/***********************************
Solution:
Distributed Euler Histogram is a low cost algorithm designed for Distinct Entries query but also can answer Total Traffic query and performs well for the Distinct Objects query.
DEH maintains Face Counts and Edge Counts in a Voronoi diagram. The answer for Distinct Entries query is Face Count – Edge Count.
For example:
Distinct Entries in P= 6 – 5 = 1;
Distinct Entries in Q= 2 – 1 = 1;
Distinct Entries in R= 4 – 2 = 2.
Data is commonly aggregated using a random tree in WSNs that we also use in our method
GPSR is used for routing.
l Distributed Euler Histogram is an efficient approach to solve aggregate queries in WSNs
l Distributed Euler Histogram is better than ID-based System because:
l DEH achieves similar accuracy for Distinct Objects query
l DEH achieves higher accuracy for Distinct Entries query
l DEH has much less cost than keeping IDs
***********************************/
17. Describe “Worm hole”.
/***********************************
Solution:
In a wormhole attack, the adversary tunnels messages received in one part of the network to another part of the network over a low-latency link and replays the messages in this part of the network. The wormhole attack requires two at least two malicious nodes. An adversary situated close to the base station may be able to convince all the nodes that are several hops away from the base station that they are only one hop away via the wormhole. All routes will then pass through the wormhole-thereby creating a sinkhole. The attacker can then selectively forward packets or manipulate data and thereby pose various kinds of security threats.
Figure below depicts the wormhole attack scenario discussed above. The malicious nodes/adversaries are depicted in red color. The wormhole is depicted in gray color and the generated as a result of the false belief that the base station is closer via the adversary. There is a sinkhole created at both the adversaries as a result of this wormhole.
***********************************/
18. Describe the detection and SNR advantage.
/***********************************
Solution:
In sensor field, denser sensor field can get higher accurate result by 10logN due to Signal Noise Ratio. Increasing the sensor density by a factor of N gives a SNR advantage of:
***********************************/
19. Describe proactive and reactive protocol
/***********************************
Solution:
l Proactive Protocol: These algorithms maintain fresh lists of destinations and their routes by distributing routing tables in the network periodically. The main disadvantages are maintaining a large routing table, communication overhead. But the first message would be very fast and optimal.
l Reactive Protocol: The protocol finds the route on demand by flooding the network with Route Request packets. The main disadvantages of such algorithms are 1. Delay in route finding. 2. Excessive flooding can lead to network clogging.
***********************************/
20. Describe Rumor Routing
/***********************************
Solution:
It is a agent-based routing protocol. Source nodes send out packets through random nodes and sink node also send query packet through random nodes. If two routs overlap then the route is found.
The disadvantages are:
l Routs are not optimal
l No delivery guarantee
l Performance depends on topology
***********************************/
21. Describe ADOV
/***********************************
Solution:
ADOV (ad hoc on-demand distance vector protocol) is a reactive routing protocol.
***********************************/
22. Describe GLS
/***********************************
Solution:
In GLS (Geographic location service), nodes act as a location server in their neighborhood. Sensor field is organized in a hierarchy Quad-tree mode. GLS tries to map the node IDs to node location.
***********************************/
23. Attack from layers in WSN
/***********************************
Solution:
Layer
Attack
Defend
Physical
Tampering
Fake node,
Compromised self-check
Capture and subversion
Link Layer
Jamming
Frequency hop
Contention
Exhaustion
Black list
Network Layer
Flooding
Challenge and response
Traffic redirection
Authentication
Spoofing
Packet dropping
Homing
Encryption,
node to node authentication
Application Layer
Eavesdropping
Encryption
Replay
Nonce
Data insertion
MAC
Data modification
MAC
***********************************/
没有评论:
发表评论