無線傳感器網(wǎng)絡(luò) 第08章 容錯(cuò)設(shè)計(jì)技術(shù)

1、無線傳感器網(wǎng)絡(luò)(wnglu)技術(shù)講義第八章、容錯(cuò)設(shè)計(jì)(shj)技術(shù)2007年8月20日共五十一頁內(nèi)容提要(ni rn t yo)概述 故障模型故障檢測故障修復(fù)(xif)可靠性協(xié)議共五十一頁內(nèi)容提要(ni rn t yo)概述(i sh) 故障模型故障檢測故障修復(fù)可靠性協(xié)議共五十一頁概述(i sh)以往容錯(cuò)研究(ynji)關(guān)注的領(lǐng)域:大規(guī)模集成電路分布式系統(tǒng)數(shù)據(jù)庫互聯(lián)網(wǎng)共五十一頁概述(i sh)容錯(cuò)方面(fngmin)的術(shù)語:故障（Fault）差錯(cuò)（Error）失效（Failure）可靠性（Dependability）共五十一頁概述(i sh)WSN容錯(cuò)的重要性：技術(shù)和實(shí)現(xiàn)因素。通常需要直接暴露

2、在環(huán)境中，在受到成本和能量限制的同時(shí)，需要完成一系列的任務(wù)。無線傳感器網(wǎng)絡(luò)是一個(gè)新興的研究和工程領(lǐng)域，處理特定問題的最優(yōu)方法(fngf)還不明確。無線傳感器網(wǎng)絡(luò)的應(yīng)用模式。無線傳感器網(wǎng)絡(luò)通常是運(yùn)行在無人干預(yù)模式，它們需要具有更強(qiáng)的容錯(cuò)能力。 共五十一頁概述(i sh)大鴨島試驗(yàn)(shyn)結(jié)果共五十一頁概述(i sh)-一個(gè)容錯(cuò)實(shí)例用聲音(shngyn)、高度兩個(gè)特征區(qū)分一間辦公室的六個(gè)人共五十一頁內(nèi)容提要(ni rn t yo)概述(i sh) 故障模型故障檢測故障修復(fù)可靠性協(xié)議共五十一頁故障(gzhng)模型部件故障傳感、供電、通信等部件發(fā)生故障，測量值偏離了實(shí)際(shj)值節(jié)點(diǎn)故障節(jié)點(diǎn)無

3、法連上網(wǎng)絡(luò)共五十一頁故障(gzhng)模型故障級(jí)別故障表征故障檢測修復(fù)機(jī)制部件故障節(jié)點(diǎn)能夠正常通信，但是測量數(shù)據(jù)是錯(cuò)誤的檢測出錯(cuò)誤的測量數(shù)據(jù)舍棄或校正出錯(cuò)的測量數(shù)據(jù)節(jié)點(diǎn)故障節(jié)點(diǎn)不能與其它節(jié)點(diǎn)進(jìn)行通信通過詢問或重新路由等方法檢測故障節(jié)點(diǎn)通過移動(dòng)冗余節(jié)點(diǎn)彌補(bǔ)形成的連接和覆蓋問題共五十一頁故障(gzhng)模型傳感部件故障固定故障 偏移(pin y)故障倍數(shù)故障方差下降故障共五十一頁內(nèi)容提要(ni rn t yo)概述(i sh) 故障模型故障檢測故障修復(fù)可靠性協(xié)議共五十一頁故障(gzhng)檢測部件故障檢測基于(jy)空間相關(guān)性基于貝葉斯網(wǎng)絡(luò)節(jié)點(diǎn)故障檢測集中式分布式共五十一頁部件故障(gzhng)

4、檢測基于空間相關(guān)性 除了(ch le)節(jié)點(diǎn)n或節(jié)點(diǎn)8，其它節(jié)點(diǎn)都感應(yīng)到事件發(fā)生 共五十一頁部件(bjin)故障檢測基于(jy)空間相關(guān)性 節(jié)點(diǎn)n在三個(gè)可信節(jié)點(diǎn)的三角區(qū)域內(nèi) 共五十一頁部件(bjin)故障檢測比較策略多數(shù)投票(tu pio)均值中值 共五十一頁部件(bjin)故障檢測決策(juc)判斷實(shí)例 共五十一頁部件(bjin)故障檢測加權(quán)中值判斷(pndun)結(jié)果 加權(quán)后的理論識(shí)別率（鄰居數(shù)為4） 共五十一頁部件故障(gzhng)檢測加權(quán)中值判斷(pndun)結(jié)果 加權(quán)后的理論誤報(bào)率（鄰居數(shù)為4） 共五十一頁部件故障(gzhng)檢測基于貝葉斯網(wǎng)絡(luò) 貝葉斯信任網(wǎng)絡(luò)包含一個(gè)有向圖和與之對(duì)應(yīng)的

5、概率表集合。有向圖中的頂點(diǎn)表示變量(binling)，邊表示變量(binling)之間的影響關(guān)系。貝葉斯信任網(wǎng)絡(luò)的關(guān)鍵特征是能夠模型化并推理出不確定因素。模型化節(jié)點(diǎn)間的可靠關(guān)系是通過節(jié)點(diǎn)概率表實(shí)現(xiàn)。 共五十一頁部件(bjin)故障檢測基于貝葉斯網(wǎng)絡(luò)(wnglu)-以大鴨島試驗(yàn)為例共五十一頁部件(bjin)故障檢測基于(jy)貝葉斯網(wǎng)絡(luò)-以大鴨島試驗(yàn)為例溫度、電壓的概率分布 共五十一頁部件故障(gzhng)檢測基于(jy)貝葉斯網(wǎng)絡(luò)-以大鴨島試驗(yàn)為例氣壓、相對(duì)濕度的條件概率分布 共五十一頁部件故障(gzhng)檢測基于(jy)貝葉斯網(wǎng)絡(luò)-以大鴨島試驗(yàn)為例計(jì)算推理共五十一頁節(jié)點(diǎn)(ji din)故障

6、檢測集中式故障(gzhng)檢測匯聚節(jié)點(diǎn)收集的信息名稱描述鄰居列表由鄰居ID號(hào)組成的一個(gè)列表鏈路質(zhì)量用0（100丟失）至100（100傳送）間的一個(gè)數(shù)來表示字節(jié)數(shù)節(jié)點(diǎn)傳輸和收到的字節(jié)數(shù)下一跳路由的下一跳節(jié)點(diǎn)（路由表）路徑丟失從節(jié)點(diǎn)到Sink節(jié)點(diǎn)的鏈接質(zhì)量的一種衡量（路由表）共五十一頁節(jié)點(diǎn)故障(gzhng)檢測集中式故障(gzhng)檢測匯聚節(jié)點(diǎn)做出的判斷事件名描述用來識(shí)別事件的信息節(jié)點(diǎn)丟失節(jié)點(diǎn)沒有出現(xiàn)在任何節(jié)點(diǎn)的鄰居列表中所有鄰居表孤立節(jié)點(diǎn)節(jié)點(diǎn)沒有任何鄰居此節(jié)點(diǎn)的鄰居表路由改變比較當(dāng)前路由表與上次路由表的變化此節(jié)點(diǎn)的路由表信息鄰居表改變比較當(dāng)前路由表與上次的鄰居表的變化此節(jié)點(diǎn)的鄰居表鏈路質(zhì)量改

7、變此節(jié)點(diǎn)與鄰居的鏈路質(zhì)量低于統(tǒng)計(jì)定義的門檻值。把當(dāng)前的和以前的鏈接質(zhì)量寫入日志。此節(jié)點(diǎn)的鄰居表共五十一頁節(jié)點(diǎn)(ji din)故障檢測分布式故障(gzhng)檢測每個(gè)節(jié)點(diǎn)判斷的算法共五十一頁內(nèi)容提要(ni rn t yo)概述 故障(gzhng)模型故障檢測故障修復(fù)可靠性協(xié)議共五十一頁故障(gzhng)修復(fù)基于連接的修復(fù) 部署k連通(lintng)拓?fù)?非k連通圖 基于覆蓋的修復(fù) 共五十一頁故障(gzhng)修復(fù)基于連接的修復(fù)(xif) -部署k連通拓?fù)?V7失效會(huì)導(dǎo)致網(wǎng)絡(luò)斷開成三部分共五十一頁故障(gzhng)修復(fù)基于(jy)連接的修復(fù) -部署k連通拓?fù)?三連通圖共五十一頁故障(gzhng)修

8、復(fù)基于連接的修復(fù)(xif) -部署k連通拓?fù)?在完全圖中找最小代價(jià)的K連通子圖的算法集中式 分布式 共五十一頁故障(gzhng)修復(fù)基于連接的修復(fù) -非k連通(lintng)拓?fù)?基站收不到某些節(jié)點(diǎn)的消息 共五十一頁故障(gzhng)修復(fù)基于連接的修復(fù)(xif) -非k連通拓?fù)?重新路由共五十一頁故障(gzhng)修復(fù)基于連接(linji)的修復(fù) -選擇容錯(cuò)節(jié)點(diǎn) Sk可作為S3的容錯(cuò)節(jié)點(diǎn)共五十一頁故障(gzhng)修復(fù)基于(jy)覆蓋的修復(fù)名稱定義計(jì)算方法覆蓋區(qū)域節(jié)點(diǎn)單獨(dú)覆蓋的區(qū)域整個(gè)感知區(qū)域去掉與其它節(jié)點(diǎn)重疊的感知區(qū)域移動(dòng)區(qū)域有效節(jié)點(diǎn)移動(dòng)到該區(qū)域即可重新覆蓋漏掉的區(qū)域以遺漏區(qū)域的邊界為圓心，

9、節(jié)點(diǎn)感知半徑為半徑作圓所形成的所有區(qū)域共五十一頁故障(gzhng)修復(fù)基于(jy)覆蓋的修復(fù)共五十一頁故障(gzhng)修復(fù)基于(jy)覆蓋的修復(fù)1，初始化階段；節(jié)點(diǎn)計(jì)算自己的覆蓋區(qū)域、每個(gè)覆蓋區(qū)域?qū)?yīng)的移動(dòng)區(qū)域。2，恐慌請(qǐng)求階段；垂死節(jié)點(diǎn)廣播求助消息。3，恐慌回應(yīng)階段；垂死節(jié)點(diǎn)的鄰居收到求助消息后計(jì)算如果自己移動(dòng)到垂死節(jié)點(diǎn)的移動(dòng)區(qū)域，是否會(huì)影響到自身的覆蓋區(qū)域，如果不影響則給求助節(jié)點(diǎn)返回消息。4，決策階段；垂死節(jié)點(diǎn)根據(jù)收到的回應(yīng)信息，決定讓哪個(gè)節(jié)點(diǎn)移動(dòng)。 共五十一頁內(nèi)容提要(ni rn t yo)概述 故障模型故障檢測故障修復(fù)(xif)可靠性協(xié)議共五十一頁可靠性協(xié)議(xiy)物理層 鏈路層網(wǎng)

10、絡(luò)層傳輸層共五十一頁可靠性協(xié)議(xiy)物理層 物理層是實(shí)現(xiàn)無線網(wǎng)絡(luò)通信的基石，其可靠性能的優(yōu)劣直接影響到整個(gè)系統(tǒng)的容錯(cuò)能力。物理層主要負(fù)責(zé)數(shù)據(jù)的編碼調(diào)制、解調(diào)解碼、發(fā)送與接收。對(duì)于(duy)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)間的通信，為了使得數(shù)據(jù)能夠被可靠地傳輸或接收，必須要做到高的接收機(jī)靈敏度、低的背景噪聲及較強(qiáng)的抗干擾能力。 共五十一頁可靠性協(xié)議(xiy)鏈路層 數(shù)據(jù)鏈路層主要負(fù)責(zé)數(shù)據(jù)流的多路選擇、數(shù)據(jù)幀偵測、媒介訪問、差錯(cuò)控制 ，保證了點(diǎn)到點(diǎn)、點(diǎn)到多點(diǎn)的可靠性鏈接。媒介訪問控制為數(shù)據(jù)傳輸建立(jinl)通信鏈路，并提供對(duì)共享媒介的公平、有效的訪問。它需要減少或避免媒介中的包沖突。 差錯(cuò)控制主要采用自動(dòng)

11、重發(fā)請(qǐng)求（ARQ）和前向糾錯(cuò)（FEC）。 共五十一頁可靠性協(xié)議(xiy)網(wǎng)絡(luò)層 建立(jinl)局部多路徑共五十一頁可靠性協(xié)議(xiy)網(wǎng)絡(luò)層 定向(dn xin)洪泛共五十一頁可靠性協(xié)議(xiy)傳輸層事件(shjin)匯聚到Sink共五十一頁可靠性協(xié)議(xiy)傳輸層 ESRT協(xié)議沒有增加存儲(chǔ)空間而實(shí)現(xiàn)了可靠傳輸。它由一個(gè)擁塞(yngs)控制組件來得到可靠性和控制能量。而且，ESRT運(yùn)行在SINK上，對(duì)于普通節(jié)點(diǎn)沒有增加任何成本開銷。 共五十一頁可靠性協(xié)議(xiy)傳輸層 - 從匯聚節(jié)點(diǎn)到傳感節(jié)點(diǎn)的傳輸 PSFQ（Pump Slowly, Fetch Quickly）為無線傳感器網(wǎng)絡(luò)的重編

12、程或重新指定任務(wù)提供了可靠傳輸，并提供了到接收端延遲保證。源節(jié)點(diǎn)低速向網(wǎng)絡(luò)注入數(shù)據(jù)包以避免網(wǎng)絡(luò)擁塞，接收節(jié)點(diǎn)有足夠的時(shí)間來檢測(jin c)這些數(shù)據(jù)包是否丟失，假如發(fā)生丟失就請(qǐng)求重傳。當(dāng)節(jié)點(diǎn)收到的包序號(hào)不等于上一個(gè)包序號(hào)加1，那么就認(rèn)為有包丟失。這個(gè)節(jié)點(diǎn)在收到正確的包之前停止繼續(xù)發(fā)送包。 共五十一頁可靠性協(xié)議(xiy)傳輸層 - 從匯聚(hu j)節(jié)點(diǎn)到傳感節(jié)點(diǎn)的傳輸 PSFQ重傳機(jī)制 共五十一頁謝謝(xi xie)！共五十一頁內(nèi)容摘要無線傳感器網(wǎng)絡(luò)技術(shù)講義。無線傳感器網(wǎng)絡(luò)是一個(gè)新興的研究和工程領(lǐng)域，處理特定問題的最優(yōu)方法還不明確。傳感、供電、通信等部件發(fā)生故障，測量值偏離了實(shí)際值。節(jié)點(diǎn)n在三個(gè)可信節(jié)點(diǎn)的三角區(qū)域內(nèi)。有向圖中的頂點(diǎn)表示變量，邊表示變量之間的影響(yngxing)關(guān)系。