如果找到了对您有用的资料,烦请点击右手边的Google广告支持我继续共享知识,谢谢! http://dengpeng.spaces.live.com/

2007年6月6日星期三

433-654 Sensor Networks and Applications Model Paper and Solutions Ver. 0.8

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

***********************************/

9 条评论:

匿名 说...

加盟 洗鞋 洗包包 包裝 設計 pe膜 冬令營 坐月子 food processing equipment Telecom PCB 泡菜 團購美食 美國月子中心 愛情 彌月 gaming machine 大陸直航 新竹餐廳 下午茶 Biodegradable 搬家公司 喇叭網 塑膠射出廠 油飯 熱轉印 團體服訂做

匿名 说...

徵信 板橋法拍屋 大台北法拍屋 原裝進口燈飾 流行燈飾 3D立體印刷 印刷服務 徵信社 外遇 徵信 徵信社 浴室 漏水 舊屋翻新 裝潢 防水工程 壁癌 健康飲食 台北素食餐廳 吃素 團購美食 水餃 seo 網站設計 超耐磨地板 店面出租 Precision Mold 加盟創業 冷凍宅配 宅配美食 Light guide panelsseo seo 線上客服 seo 網頁設計 Plastic Products Mold design hand dryer 電波拉皮 房屋貸款 剖腹生產 沖孔網 飛梭雷射 金屬擴張網 彌月送禮 喜餅 宜蘭旅遊 教育訓練 品質管理 Ohsas 18001 清水溝 沙發 室內設計公司 室內設計 室內裝潢設計 裝潢設計 澳門自由行 搬家公司

匿名 说...

彌月禮 玻尿酸 星座運勢 算命 皮膚科 皮膚科診所 肉毒桿菌 肉毒桿菌瘦臉 脈衝光 除斑 Flex PCB PCB Electronic PCB 房屋仲介 法拍屋 法拍 法拍屋查詢系統 室內裝潢設計 照明 彩盒 水晶燈 日租套房 台北日租 apartment 太平山民宿 宜蘭民宿推薦 借錢 素食 素食食譜 省電熱水器 電波拉皮 姓名配對 星座casino gaming machine 泰國清邁 外遇 模具設計 素食料理 素食水餃 開運印章 風水 外遇 徵信 壁癌 屋頂防水 屋頂隔熱 抓漏 油漆 徵信社 外遇 徵信 徵信社 外遇 徵信 徵信社 外遇 紙盒印刷

匿名 说...

皺紋 減肥 禿頭 醫學美容 網路行銷 中古車 涼麵 POLO衫 電波拉皮 雷射溶脂 肉毒桿菌 玻尿酸 痘疤 婦產科診所 室內設計 埋線 內分泌失調 黃體不足 針灸減肥 公益團體 愛心捐款 捐款 坐月子中心 婦產科 玫瑰花束 盆栽 網路花店 花店 鍛造 樓梯扶手 欄杆 通馬桶 喜餅價格 訂婚禮盒 訂婚喜餅 宜蘭民宿 泰國 關鍵字廣告 seo 網頁設計公司 雷射溶脂外遇 徵信 徵信社 清潔公司 喜餅禮盒 塑膠射出 柔膚雷射 獸醫師 創業 鞋之澡堂 洗鞋子 洗包包加盟 彌月禮盒 模具

匿名 说...

義賣活動 二手車 環保袋 環保袋 環保袋 十分瀑布 台北旅遊網 月子餐 飛梭雷射 太陽能熱水器 太陽能 三久太陽能 三久 身體檢查 健康檢查 台北民宿 薰衣草花園 花園餐廳 螢火蟲 渡假村 鐵道之旅 團體服 滷味 滷味加盟 滷味批發 滷味食材 滷味宅配 滷雞翅 滷雞腳 健康滷味 租店面 魯味 加盟創業 慈善 慈善機構 公益彩券 肉毒桿菌 系統家具鐵門 採光罩 清水溝 通水管 台中漆彈場 漆彈 團體服 團體服 月子中心 全身健康檢查 統一發票5 6月 104人力銀行 104求職人力銀行 團體服 T恤 圍裙 健康食品 慈善基金會美白 塑膠射出模具

匿名 说...

義賣活動 二手車 環保袋 環保袋 環保袋 十分瀑布 台北旅遊網 月子餐 飛梭雷射 太陽能熱水器 太陽能 三久太陽能 三久 身體檢查 健康檢查 台北民宿 薰衣草花園 花園餐廳 螢火蟲 渡假村 鐵道之旅 團體服 滷味 滷味加盟 滷味批發 滷味食材 滷味宅配 滷雞翅 滷雞腳 健康滷味 租店面 魯味 加盟創業 慈善 慈善機構 公益彩券 肉毒桿菌 系統家具鐵門 採光罩 清水溝 通水管 台中漆彈場 漆彈 團體服 團體服 月子中心 全身健康檢查 統一發票5 6月 104人力銀行 104求職人力銀行 團體服 T恤 圍裙 健康食品 慈善基金會美白 塑膠射出模具

匿名 说...

月子餐外送 月子餐食譜 統一發票9 10月 金價 統一發票9 10月 找工作 統一發票7 8月 求職 1111求職人力銀行 104求職人力銀行 104人力銀行 塑膠袋 統一發票1 2月 金價 肉毒桿菌 黃金 sum中古車 1111人力銀行 104求職人力銀行 1111人力銀行求職 黃金價格查詢 中古車買賣 塑膠袋 統一發票9 10月 抽水肥 水管不通 化糞池 通馬桶 導光板 洗水塔 自由行 塑膠袋批發 中古車 中古車買賣 消防公司 團體服創意 地板施工 網路廣告 網路行銷 平溪 景觀餐廳 桃園房屋買賣 關鍵字行銷 關鍵字 seo 關鍵字行銷 關鍵字 seo 熱水器 衛浴設備 節能減碳 電熱水器 中古車 義賣

匿名 说...

月子中心 seo 關鍵字廣告 關鍵字 關鍵字行銷 今日金價 網路行銷 通姦 徵信社 外遇 桃園房屋仲介 桃園房屋買賣 桃園房屋 醫學美容診所 淨膚雷射 雷射溶脂 飛梭雷射黃金價格 金價查詢 黃金買賣 環保袋 微晶瓷 植髮 團體服 團體服訂做 抽化糞池 訂房 雄獅旅遊 汽車美容 汽車美容 三久太陽能 黃金價格查詢 貸款 信用貸款 微晶瓷 3D飛梭雷射 淨膚雷射 汽車借款 汽車貸款 徵信 徵信社 膠框 創業 加盟 早餐店加盟 統一發票3 4月 坐月子 meat processing equipment food processing mixers 衝孔網 藥盒 金價查詢 月子餐 月子中心 坐月子餐 賣車 辦公室風水

匿名 说...

月子中心 seo 關鍵字廣告 關鍵字 關鍵字行銷 今日金價 網路行銷 通姦 徵信社 外遇 桃園房屋仲介 桃園房屋買賣 桃園房屋 醫學美容診所 淨膚雷射 雷射溶脂 飛梭雷射黃金價格 金價查詢 黃金買賣 環保袋 微晶瓷 植髮 團體服 團體服訂做 抽化糞池 訂房 雄獅旅遊 汽車美容 汽車美容 三久太陽能 黃金價格查詢 貸款 信用貸款 微晶瓷 3D飛梭雷射 淨膚雷射 汽車借款 汽車貸款 徵信 徵信社 膠框 創業 加盟 早餐店加盟 統一發票3 4月 坐月子 meat processing equipment food processing mixers 衝孔網 藥盒 金價查詢 月子餐 月子中心 坐月子餐 賣車 辦公室風水