專題2(無線傳感器網(wǎng)絡(luò)專題)

專題2(無線傳感器網(wǎng)絡(luò)專題)第一頁，共88頁。第三章無線傳感器網(wǎng)絡(luò)WSN無線傳感器網(wǎng)絡(luò)的基本概念無線傳感器網(wǎng)絡(luò)的應(yīng)用無線傳感器網(wǎng)絡(luò)中的幾種典型路由協(xié)議無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)無線傳感器網(wǎng)絡(luò)中的幾個(gè)研究熱點(diǎn)第二頁，共88頁。1.1無線傳感器網(wǎng)絡(luò)的基本概念無線傳感器網(wǎng)絡(luò)的歷史第一代傳感器網(wǎng)絡(luò)：無線傳感器網(wǎng)絡(luò)的構(gòu)想最初是由美國(guó)軍方提出的，美國(guó)國(guó)防部高級(jí)研究所計(jì)劃署（DARPA）于1978年開始資助卡耐基－梅隆大學(xué)進(jìn)行分布式傳感器網(wǎng)絡(luò)的研究。通過將傳統(tǒng)傳感器采用點(diǎn)對(duì)點(diǎn)傳輸、連接傳感控制器而構(gòu)成傳感器網(wǎng)絡(luò)雛形。第二代傳感器網(wǎng)絡(luò)：傳感器網(wǎng)絡(luò)具有了獲取多種信息信號(hào)的綜合處理能力，并通過與傳感控制器的相聯(lián)，組成了有信息綜合和處理能力的傳感器網(wǎng)絡(luò)。第三代傳感器網(wǎng)絡(luò)：從上世紀(jì)末開始，現(xiàn)場(chǎng)總線技術(shù)開始應(yīng)用于傳感器網(wǎng)絡(luò)，人們用其組建智能化傳感器網(wǎng)絡(luò)，大量多功能傳感器被運(yùn)用，并使用無線技術(shù)連接，無線傳感器網(wǎng)絡(luò)逐漸形成。第三頁，共88頁。發(fā)展背景1.1無線傳感器網(wǎng)絡(luò)的基本概念第四頁，共88頁。1.1無線傳感器網(wǎng)絡(luò)的基本概念無線傳感器網(wǎng)絡(luò)的定義無線傳感器網(wǎng)絡(luò)是大量的靜止或移動(dòng)的傳感器以自組織和多跳的方式構(gòu)成的無線網(wǎng)絡(luò),其目的是協(xié)作地感知、采集、處理和傳輸網(wǎng)絡(luò)覆蓋地理區(qū)域內(nèi)感知對(duì)象的監(jiān)測(cè)信息,報(bào)告給用戶。無線傳感器網(wǎng)絡(luò)WSN（WirelessSensorNetwork）也稱為智能灰塵（Smart

Dust）。被稱為二十一世紀(jì)最具挑戰(zhàn)性的研究課題之一。第五頁，共88頁。傳感器節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)：從上圖我們可以看到一個(gè)典型的傳感器節(jié)點(diǎn)由數(shù)據(jù)獲取單元、數(shù)據(jù)處理單元、數(shù)據(jù)傳輸單元、以及能量供應(yīng)單元四部分組成。每一個(gè)模塊的功能如下：第六頁，共88頁。1.1無線傳感器網(wǎng)絡(luò)的基本概念傳感器節(jié)點(diǎn)各部分的功能數(shù)據(jù)獲取單元：負(fù)責(zé)監(jiān)視區(qū)域內(nèi)信息的采集和數(shù)據(jù)轉(zhuǎn)換。數(shù)據(jù)處理單元：負(fù)責(zé)控制整個(gè)傳感器節(jié)點(diǎn)的操作，存儲(chǔ)處理本身采集的數(shù)據(jù)以及其它節(jié)點(diǎn)發(fā)來的數(shù)據(jù)。數(shù)據(jù)傳輸單元：負(fù)責(zé)與其它傳感器節(jié)點(diǎn)進(jìn)行無線通信，交換控制信息和收發(fā)采集數(shù)據(jù)。能量供應(yīng)單元：為傳感器節(jié)點(diǎn)提供運(yùn)行所需的能量，通常采用微型電池。第七頁，共88頁。傳感器實(shí)物體積小能耗小能量受限處理能力受限存儲(chǔ)能力受限1.1無線傳感器網(wǎng)絡(luò)的基本概念第八頁，共88頁。WSN的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

結(jié)構(gòu)如上圖所示，傳感器網(wǎng)絡(luò)系統(tǒng)通常包括傳感器節(jié)點(diǎn)（sensornode），匯聚節(jié)點(diǎn)（sinknode），和管理節(jié)點(diǎn)。大量傳感器節(jié)點(diǎn)隨機(jī)的部署在檢測(cè)區(qū)域內(nèi)部或附近，能夠通過自組織方式構(gòu)成網(wǎng)絡(luò)。傳感其節(jié)點(diǎn)檢測(cè)的數(shù)據(jù)沿著其它節(jié)點(diǎn)逐跳的進(jìn)行傳輸，其傳輸過程可能經(jīng)過多個(gè)節(jié)點(diǎn)處理，經(jīng)過多跳后到達(dá)匯集節(jié)點(diǎn)，最后通過互聯(lián)網(wǎng)和衛(wèi)星達(dá)到管理節(jié)點(diǎn)，用戶通過管理節(jié)點(diǎn)對(duì)傳感器網(wǎng)絡(luò)進(jìn)行配置和管理，發(fā)布檢測(cè)任務(wù)以及收集檢測(cè)數(shù)據(jù)。1.1無線傳感器網(wǎng)絡(luò)的基本概念互聯(lián)網(wǎng)和衛(wèi)星任務(wù)管理中心用戶匯聚節(jié)點(diǎn)監(jiān)測(cè)區(qū)域傳感器節(jié)點(diǎn)BAC第九頁，共88頁。

WSN的相關(guān)技術(shù)無線傳感器網(wǎng)絡(luò)是應(yīng)用相關(guān)性網(wǎng)絡(luò)，是一種應(yīng)用中產(chǎn)生和發(fā)展的技術(shù)，所以不同的應(yīng)用領(lǐng)域使用不同的網(wǎng)絡(luò)技術(shù)實(shí)現(xiàn)，目前實(shí)現(xiàn)WSN的主要技術(shù)有：Zigbee：一種近距離（10-75m）、低復(fù)雜度、低功耗（兩節(jié)普通５號(hào)干電池可使用２年

）、低數(shù)據(jù)速率（250Kbps）、低成本的無線網(wǎng)絡(luò)技術(shù)。WI-FI：無線保真技術(shù)（WirelessFidelity），一種短距離（目前已達(dá)幾百公里）無線技術(shù)。最大傳輸數(shù)據(jù)速率為54Mbps。BlueTooth：藍(lán)牙，傳輸距離一般在10m左右，最大傳輸數(shù)據(jù)速率小于10M。UWB：一種超寬帶（UltraWideBand）的短距離（10m左右）通信技術(shù)

，1GHz以上帶寬。1.1無線傳感器網(wǎng)絡(luò)的基本概念第十頁，共88頁。1.1無線傳感器網(wǎng)絡(luò)的基本概念無線傳感器網(wǎng)絡(luò)的特點(diǎn)與挑戰(zhàn)：節(jié)點(diǎn)帶寬窄，節(jié)點(diǎn)通信覆蓋范圍只有幾十到幾百米,而且經(jīng)常變化挑戰(zhàn)：如何在如此有限通信能力的條件下,高質(zhì)量地完成感知數(shù)據(jù)的查詢、分析、挖掘與傳輸？多源、多跳是主要通信方式挑戰(zhàn)：如何為多源信息傳輸選擇優(yōu)化通信路徑？第十一頁，共88頁。1.1無線傳感器網(wǎng)絡(luò)的基本概念無線傳感器網(wǎng)絡(luò)的特點(diǎn)與挑戰(zhàn)（Cont.）：節(jié)點(diǎn)移動(dòng)、斷接頻繁挑戰(zhàn)：通信路徑重構(gòu)成為突出問題？路由算法必須具有自適應(yīng)性？節(jié)點(diǎn)電源能量有限、且難于補(bǔ)充挑戰(zhàn)：如何傳感器網(wǎng)絡(luò)在工作過程中節(jié)省能，實(shí)現(xiàn)能源均衡，最大化網(wǎng)絡(luò)生命周期？節(jié)點(diǎn)計(jì)算能力有限挑戰(zhàn)：如何使用大量具有有限計(jì)算能力的傳感器設(shè)計(jì)能源有效的高性能分布式算法?第十二頁，共88頁。1.1無線傳感器網(wǎng)絡(luò)的基本概念無線傳感器網(wǎng)絡(luò)的特點(diǎn)與挑戰(zhàn)（Cont.）：傳感器數(shù)量大、分布范圍廣挑戰(zhàn)：如何使傳感器網(wǎng)絡(luò)軟硬件具有高強(qiáng)壯性和容錯(cuò)性？感知數(shù)據(jù)流無限挑戰(zhàn)：如何設(shè)計(jì)高效率、能源有效、實(shí)時(shí)的海量感知數(shù)據(jù)流的查詢、分析和挖掘的分布式算法？傳感器網(wǎng)絡(luò)是以數(shù)據(jù)為中心的網(wǎng)絡(luò)挑戰(zhàn)：如何建立以數(shù)據(jù)為中心的傳感器網(wǎng)絡(luò)?第十三頁，共88頁。1.1無線傳感器網(wǎng)絡(luò)的基本概念無線傳感器網(wǎng)絡(luò)的特點(diǎn)與挑戰(zhàn)（Cont.）：挑戰(zhàn)：傳感器的投放或撒播理論與技術(shù)挑戰(zhàn)：傳感器的定位問題挑戰(zhàn)：時(shí)鐘同步問題

挑戰(zhàn)：組網(wǎng)連通可靠性研究和探測(cè)覆蓋率研究

挑戰(zhàn)：傳感器網(wǎng)絡(luò)安全性問題和抗干擾問題挑戰(zhàn)：信號(hào)的協(xié)作處理第十四頁，共88頁。1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用軍事應(yīng)用:作戰(zhàn)環(huán)境偵查與監(jiān)控軍事偵查、情報(bào)獲取戰(zhàn)場(chǎng)監(jiān)測(cè)與指揮民事應(yīng)用:環(huán)境監(jiān)測(cè)交通管理災(zāi)難預(yù)防(如森林火災(zāi)監(jiān)測(cè))危險(xiǎn)區(qū)域監(jiān)測(cè)有滅絕危險(xiǎn)或珍貴動(dòng)物的跟蹤監(jiān)護(hù)民用和工程基礎(chǔ)設(shè)施的安全性監(jiān)測(cè)等等，等等第十五頁，共88頁。大地與環(huán)境監(jiān)測(cè)1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用第十六頁，共88頁。1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用第十七頁，共88頁。1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用第十八頁，共88頁。

污染流監(jiān)控1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用第十九頁，共88頁。Sensorattachedtoeveryvehicle.Capableofdetectingtheirlocation,vehiclesizes,speedsand;roadconditions…Alternateroutes,estimatetriptimes…

TrafficControl1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用第二十頁，共88頁。

BiologicalSystems1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用第二十一頁，共88頁。作戰(zhàn)環(huán)境偵查1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用第二十二頁，共88頁?？臻g探測(cè)：對(duì)星球表面的監(jiān)測(cè)和探索1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用第二十三頁，共88頁。1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用無線傳感器網(wǎng)絡(luò)的最新應(yīng)用：

2004/03/18日經(jīng)BP社報(bào)道】英特爾向美國(guó)政府人員等演示了無線傳感器網(wǎng)絡(luò)的家庭護(hù)理技術(shù)。通過在鞋、家具以家用電器等家中道具和設(shè)備中嵌入半導(dǎo)體傳感器，幫助老齡人士、阿爾茨海默氏病患者以及殘障人士的家庭生活。利用無線通信將各傳感器聯(lián)網(wǎng)可高效傳遞必要的信息從而方便接受護(hù)理。而且還可以減輕護(hù)理人員的負(fù)擔(dān)。第二十四頁，共88頁。1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用無線傳感器網(wǎng)絡(luò)的最新應(yīng)用（Cont.）：

著名的沃爾瑪連鎖店已經(jīng)投入資金，在其貨物上加裝射頻識(shí)別條型碼芯片（RFID），使該公司和供應(yīng)商能夠跟蹤從生產(chǎn)廠到收款臺(tái)的商品流向。這種技術(shù)可望減少商品失竊率和其他損失，并能節(jié)省倉(cāng)庫(kù)占用及商店的人力成本。目前每個(gè)條型碼芯片的成本為24美分，未來將會(huì)降到僅僅幾美分。第二十五頁，共88頁。1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用無線傳感器網(wǎng)絡(luò)的最新應(yīng)用（Cont.）：

美國(guó)約克國(guó)際公司為6萬家客戶管理通風(fēng)系統(tǒng)。計(jì)劃在未來5年內(nèi)，為其客戶的空調(diào)裝置上安裝幾萬個(gè)網(wǎng)絡(luò)化的傳感器。傳感器將監(jiān)視溫度，并自動(dòng)地將最新信息傳送給辦公室，從而使維修人員對(duì)客戶的空調(diào)運(yùn)行狀況一目了然。大大減少該公司2444名技術(shù)人員的工作負(fù)荷，使生產(chǎn)力提高15％。第二十六頁，共88頁。1.2無線傳感器網(wǎng)絡(luò)的應(yīng)用無線傳感器網(wǎng)絡(luò)的最新應(yīng)用（Cont.）：

美國(guó)《每日防務(wù)》2004年3月18日?qǐng)?bào)道無線傳感器網(wǎng)絡(luò)技術(shù)將會(huì)在戰(zhàn)場(chǎng)上帶來革命性的變化，并將改變戰(zhàn)爭(zhēng)的樣式。它不僅可以感覺到運(yùn)動(dòng)的或靜止的金屬，而且可以感覺到聲音、光線、溫度、化學(xué)物品，以及動(dòng)植物的生理特征。無線傳感器網(wǎng)絡(luò)技術(shù)，預(yù)示著為戰(zhàn)場(chǎng)上帶來新的電子眼和電子耳，“能夠在未來幾十年內(nèi)變革戰(zhàn)場(chǎng)環(huán)境”。第二十七頁，共88頁。1.3無線傳感器網(wǎng)絡(luò)中的幾種典型路由協(xié)議WSN路由協(xié)議面臨的挑戰(zhàn):考慮網(wǎng)絡(luò)和節(jié)點(diǎn)能量?jī)?yōu)化（能量受限&難于補(bǔ)充）具有高可擴(kuò)展性（網(wǎng)絡(luò)規(guī)模&自組織）適應(yīng)強(qiáng)網(wǎng)絡(luò)拓?fù)渥兓ü?jié)點(diǎn)移動(dòng)&無線信道）適應(yīng)非規(guī)則數(shù)據(jù)流量分布（以數(shù)據(jù)為中心&數(shù)據(jù)流）具有一定的安全性（處理能力受限&存儲(chǔ)能力受限）第二十八頁，共88頁。1.3無線傳感器網(wǎng)絡(luò)中的幾種典型路由協(xié)議WSN路由協(xié)議的分類:

WSN路由協(xié)議負(fù)責(zé)在Sink點(diǎn)和Sensor節(jié)點(diǎn)間可靠地傳輸數(shù)據(jù)。由于WSN與應(yīng)用高度相關(guān)，單一的路由協(xié)議不能滿足各種應(yīng)用需求，因而人們研究了眾多的路由協(xié)議。根據(jù)路由協(xié)議采用的通信模式、路由結(jié)構(gòu)、路由建立時(shí)機(jī)、狀態(tài)維護(hù)、節(jié)點(diǎn)標(biāo)識(shí)和投遞方式等策略，可對(duì)其進(jìn)行了如下分類：根據(jù)傳輸過程中采用路徑的多少，可分為單路徑路由協(xié)議和多路徑路由協(xié)議。單路徑路由節(jié)約存儲(chǔ)空間，數(shù)據(jù)通信量少，多路徑路由容錯(cuò)性強(qiáng)，健壯性好，且可從眾多路由中選擇一條最優(yōu)路由。第二十九頁，共88頁。1.3無線傳感器網(wǎng)絡(luò)中的幾種典型路由協(xié)議WSN路由協(xié)議的分類（Cont.）:根據(jù)節(jié)點(diǎn)在路由過程中是否有層次結(jié)構(gòu)、作用是否有差異，可分為平面路由協(xié)議和層次路由協(xié)議。平面路由簡(jiǎn)單，健壯性好，但建立、維護(hù)路由的開銷大，數(shù)據(jù)傳輸跳數(shù)多，適合小規(guī)模網(wǎng)絡(luò)。層次路由擴(kuò)展性好，適合大規(guī)模網(wǎng)絡(luò)，但簇的維護(hù)開銷大，且簇頭是路由的關(guān)鍵節(jié)點(diǎn)，其失效將導(dǎo)致路由失敗。第三十頁，共88頁。1.3無線傳感器網(wǎng)絡(luò)中的幾種典型路由協(xié)議WSN路由協(xié)議的分類（Cont.）:根據(jù)路由建立時(shí)機(jī)與數(shù)據(jù)發(fā)送的關(guān)系，可分為主動(dòng)路由協(xié)議、按需路由協(xié)議和混合路由協(xié)議。主動(dòng)路由建立、維護(hù)路由的開銷大，資源要求高。按需路由在傳輸前需計(jì)算路由，時(shí)延大?；旌下酚蓜t綜合利用這兩種方式。根據(jù)是否以地理位置來標(biāo)識(shí)目的地、路由計(jì)算中是否利用地理位置信息，可分為基于位置的路由協(xié)議和非基于位置的路由協(xié)議。有大量WSN應(yīng)用需要知道突發(fā)事件的地理位置，這是基于位置的路由協(xié)議的應(yīng)用基礎(chǔ)，但需要GPS定位系統(tǒng)或者其他定位方法協(xié)助節(jié)點(diǎn)計(jì)算位置信息。第三十一頁，共88頁。1.3無線傳感器網(wǎng)絡(luò)中的幾種典型路由協(xié)議WSN路由協(xié)議的分類（Cont.）:根據(jù)是否以數(shù)據(jù)來標(biāo)識(shí)目的地，可分為基于數(shù)據(jù)的路由協(xié)議和非基于數(shù)據(jù)的路由協(xié)議。有大量WSN應(yīng)用要求查詢或上報(bào)具有某種類型的數(shù)據(jù)，這是基于數(shù)據(jù)的路由協(xié)議的應(yīng)用基礎(chǔ)，但需要分類機(jī)制對(duì)數(shù)據(jù)類型進(jìn)行命名。根據(jù)節(jié)點(diǎn)是否編址、是否以地址標(biāo)識(shí)目的地，可分為基于地址的路由協(xié)議和非基于地址的路由協(xié)議?；诘刂返穆酚稍趥鹘y(tǒng)路由協(xié)議中較常見，而在WSN中一般不單獨(dú)使用而與其他策略結(jié)合使用。第三十二頁，共88頁。1.3無線傳感器網(wǎng)絡(luò)中的幾種典型路由協(xié)議WSN路由協(xié)議的分類（Cont.）:根據(jù)路由選擇是否考慮QoS約束，可分為保證QoS的路由協(xié)議和不保證QoS的路由協(xié)議。保證QoS的路由協(xié)議是指在路由建立時(shí)，考慮時(shí)延、丟包率等QoS參數(shù)，從眾多可行路由中選擇一條最適合QoS應(yīng)用要求的路由。根據(jù)數(shù)據(jù)在傳輸過程中是否進(jìn)行聚合處理，可分為數(shù)據(jù)聚合的路由協(xié)議和非數(shù)據(jù)聚合的路由協(xié)議。數(shù)據(jù)聚合能減少通信量，但需要時(shí)間同步技術(shù)的支持，并使傳輸時(shí)延增加。第三十三頁，共88頁。1.3無線傳感器網(wǎng)絡(luò)中的幾種典型路由協(xié)議WSN路由協(xié)議的分類（Cont.）:根據(jù)路由是否由源節(jié)點(diǎn)指定，可分為源站路由協(xié)議和非源站路由協(xié)議。源站路由協(xié)議節(jié)點(diǎn)無須建立、維護(hù)路由信息，從而節(jié)約存儲(chǔ)空間，減少通信開銷。但如果網(wǎng)絡(luò)規(guī)模較大，數(shù)據(jù)包頭的路由信息開銷也大，而且如果網(wǎng)絡(luò)拓?fù)渥兓l繁，將導(dǎo)致路由失敗。根據(jù)路由建立時(shí)機(jī)是否與查詢有關(guān)，可分為查詢驅(qū)動(dòng)的路由協(xié)議和非查詢驅(qū)動(dòng)的路由協(xié)議。查詢驅(qū)動(dòng)的路由協(xié)議能夠節(jié)約節(jié)點(diǎn)存儲(chǔ)空間，但數(shù)據(jù)時(shí)延較大，且不適合環(huán)境監(jiān)測(cè)等需緊急上報(bào)的應(yīng)用。第三十四頁，共88頁。幾種代表性的WSN路由協(xié)議:基于梯度(Gradient)的路由協(xié)議DD(DirectedDiffusion)基于協(xié)商機(jī)制(Negotiation)的路由協(xié)議SPIN(SensorProtocolforInformationviaNegotiation)基于位置信息(LocationInformation)的路由協(xié)議GEAR(GeographicandEnergyAwareRouting)基于單層簇的路由協(xié)議LEACH(LowEnergyAdaptiveClusteringHierarchy)基于多層簇的路由協(xié)議TTDD(TwoTierDataDissemination)基于謠言的路由協(xié)議Rumor無線傳感器網(wǎng)絡(luò)的組播與選播路由協(xié)議1.3無線傳感器網(wǎng)絡(luò)中的幾種典型路由協(xié)議第三十五頁，共88頁。1.3.1DD(DirectedDiffusion)

DD是一種查詢驅(qū)動(dòng)的DC(Data-Centric)路由協(xié)議。在DC協(xié)議中，源節(jié)點(diǎn)采集的原始數(shù)據(jù)首先在某些中間節(jié)點(diǎn)處進(jìn)行合并處理，然后再將匯聚后的數(shù)據(jù)統(tǒng)一發(fā)送到目的節(jié)點(diǎn)，從而實(shí)現(xiàn)減低通信開銷，達(dá)到節(jié)能的目的?；贒C路由協(xié)議的數(shù)據(jù)傳播模型如下。

第三十六頁，共88頁。1.3.1DD(DirectedDiffusion)

DD采用基于消息驅(qū)動(dòng)(Information-Driven的數(shù)據(jù)傳播模式，以節(jié)點(diǎn)可以提供的數(shù)據(jù)作為尋址依據(jù)，即Sink節(jié)點(diǎn)在網(wǎng)絡(luò)中廣播以某種數(shù)據(jù)格式構(gòu)成的消息來告之所有傳感節(jié)點(diǎn)它所感興趣的監(jiān)測(cè)數(shù)據(jù)，這種消息簡(jiǎn)稱為興趣(Interests)。DD協(xié)議的工作原理如下：Step1（請(qǐng)求擴(kuò)散）：Sink節(jié)點(diǎn)發(fā)出的興趣查詢逐級(jí)擴(kuò)散，最終遍歷全網(wǎng)，找到所有匹配的原始數(shù)據(jù)。

第三十七頁，共88頁。1.3.1DD(DirectedDiffusion)

DD協(xié)議的工作原理（Cont.)：Step2（梯度場(chǎng)建立）：在Sink節(jié)點(diǎn)的興趣擴(kuò)散過程中，有一個(gè)稱為“梯度(Gradient)”的變量與整個(gè)業(yè)務(wù)請(qǐng)求的擴(kuò)散過程相聯(lián)系，其反映了網(wǎng)絡(luò)中間節(jié)點(diǎn)對(duì)匹配請(qǐng)求條件的數(shù)據(jù)源的近似判斷。

第三十八頁，共88頁。1.3.1DD(DirectedDiffusion)

DD協(xié)議的工作原理（Cont.)：Step3（數(shù)據(jù)傳輸）：傳感節(jié)點(diǎn)通過與Sink節(jié)點(diǎn)的興趣匹配，最終將會(huì)在整個(gè)網(wǎng)絡(luò)中為Sink節(jié)點(diǎn)的請(qǐng)求建立一個(gè)臨時(shí)的“梯度”場(chǎng)，從而使得匹配數(shù)據(jù)可以沿“梯度”最大的方向中繼返回Sink節(jié)點(diǎn)。數(shù)據(jù)在回傳Sink節(jié)點(diǎn)的過程中，算法將利用沿途的中間節(jié)點(diǎn)進(jìn)行數(shù)據(jù)匯聚處理，從而使得數(shù)據(jù)傳輸?shù)耐ㄐ砰_銷減低，達(dá)到節(jié)能的目的。第三十九頁，共88頁。1.3.1DD(DirectedDiffusion)

DD協(xié)議的優(yōu)缺點(diǎn)：其優(yōu)點(diǎn)是由于“梯度”場(chǎng)的建立及采用了數(shù)據(jù)匯聚思想，因此DD協(xié)議比較節(jié)能。其缺點(diǎn)是“梯度”場(chǎng)的建立過程復(fù)雜、Sink節(jié)點(diǎn)的興趣廣播采用洪泛(Flooding)機(jī)制、數(shù)據(jù)均沿最短路徑進(jìn)行傳輸，沒考慮均衡所有節(jié)點(diǎn)的能量消耗，不具有能量感知功能，因此，算法易于使得部分節(jié)點(diǎn)因能耗過大而失效，從而導(dǎo)致網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)經(jīng)常變化，影響了算法的路由性能。第四十頁，共88頁。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN是第一個(gè)采用DC思想的基于洪泛的路由協(xié)議。洪泛協(xié)議具有延時(shí)小和分布式的特點(diǎn)。

SPIN的主要思想是通過協(xié)商機(jī)制來解決洪泛協(xié)議中的”內(nèi)爆”問題。

在SPIN中，傳感節(jié)點(diǎn)通過廣播發(fā)送數(shù)據(jù)的描述信息，而不是真實(shí)數(shù)據(jù)，僅當(dāng)有相應(yīng)的數(shù)據(jù)請(qǐng)求時(shí)，才有目的地發(fā)送實(shí)際數(shù)據(jù)，從而通過減低數(shù)據(jù)廣播的通信開銷來達(dá)到節(jié)能的目的。

SPIN的路由原理圖如下：第四十一頁，共88頁。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN協(xié)議的工作原理:Step1：SPIN包括三種類型的數(shù)據(jù)：ADV、REQ以及DATA。在實(shí)際廣播DATA消息前，如圖的Step1所示，源節(jié)點(diǎn)首先向鄰節(jié)點(diǎn)廣播攜帶DATA描述的ADV消息。第四十二頁，共88頁。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN協(xié)議的工作原理(Cont.):Step2：若某個(gè)鄰節(jié)點(diǎn)對(duì)該DATA消息感興趣，則該鄰節(jié)點(diǎn)將如圖的Step2所示，通過回送REQ消息來向源節(jié)點(diǎn)申請(qǐng)數(shù)據(jù)DATA。第四十三頁，共88頁。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN協(xié)議的工作原理(Cont.):Step3：源節(jié)點(diǎn)在收到REQ消息后，再如圖的Step3所示，將實(shí)際采集的DATA消息發(fā)送給該鄰節(jié)點(diǎn)。第四十四頁，共88頁。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN協(xié)議的工作原理(Cont.):Step4-6：該鄰節(jié)點(diǎn)在收到DATA之后，將如圖的Step4~6所示，重復(fù)上述路由過程，最后，網(wǎng)絡(luò)中所有對(duì)該DATA消息感興趣的節(jié)點(diǎn)均可收到該消息的一份拷貝。第四十五頁，共88頁。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN協(xié)議的優(yōu)缺點(diǎn):與傳統(tǒng)Flooding協(xié)議相比，由于SPIN采用三步握手(ADV-REQ-DATA)協(xié)商機(jī)制與鄰節(jié)點(diǎn)協(xié)商解決洪泛算法中的“內(nèi)爆”與“重疊”問題，因此比傳統(tǒng)Flooding協(xié)議要更加節(jié)能。另外，無需路由維護(hù)，對(duì)網(wǎng)絡(luò)拓?fù)渥兓幻舾?。其缺點(diǎn)是要求所有節(jié)點(diǎn)均具有路由功能，因此節(jié)點(diǎn)的路由開銷大。

第四十六頁，共88頁。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

Flooding協(xié)議的“內(nèi)爆”與“重疊”問題:“內(nèi)爆”：節(jié)點(diǎn)向鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，而不管其是否已經(jīng)收到相同的數(shù)據(jù)。“重疊”：傳感器節(jié)點(diǎn)感知區(qū)域有重疊，導(dǎo)致數(shù)據(jù)冗余。

第四十七頁，共88頁。1.3.3GEAR(GeographicandEnergyAwareRouting)

GEAR是一種基于位置信息的DC路由協(xié)議。在GEAR協(xié)議中，傳感節(jié)點(diǎn)首先利用GPS定位裝置通過衛(wèi)星定位等方式來獲知自己的地理坐標(biāo)位置，同時(shí)假定其知道目標(biāo)區(qū)域的位置信息。然后利用目標(biāo)區(qū)域的位置信息與鄰節(jié)點(diǎn)的能量信息來決定路由的下一跳，直到將數(shù)據(jù)發(fā)送到目標(biāo)區(qū)域(TargetRegion)R。當(dāng)數(shù)據(jù)發(fā)送到目標(biāo)區(qū)域R之后，在R內(nèi)，算法將目標(biāo)區(qū)域分解為幾個(gè)子區(qū)域再利用一種遞歸地理轉(zhuǎn)發(fā)算法(RecursiveGeographicForwarding)來將數(shù)據(jù)向各個(gè)子區(qū)域的中心位置分發(fā)。

第四十八頁，共88頁。1.3.3GEAR(GeographicandEnergyAwareRouting)

GEAR協(xié)議中的遞歸地理轉(zhuǎn)發(fā)算法原理：圖中假設(shè)目標(biāo)區(qū)域R是一個(gè)矩形區(qū)域，且節(jié)點(diǎn)Ni收到發(fā)送給R的數(shù)據(jù)包P。此時(shí)，Ni將首先發(fā)現(xiàn)自己在目標(biāo)區(qū)域R之中，然后如圖所示，Ni將R劃分為4個(gè)子區(qū)域，然后生成4個(gè)包P的拷貝分別轉(zhuǎn)發(fā)到R的4個(gè)子區(qū)域(Sub-Region)。當(dāng)子區(qū)域中的某個(gè)節(jié)點(diǎn)收到數(shù)據(jù)包P后，重復(fù)上述過程，顯然最終所有目的節(jié)點(diǎn)均能收到源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包P。

第四十九頁，共88頁。1.3.3GEAR(GeographicandEnergyAwareRouting)

GEAR的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：利用位置信息和遞歸地理轉(zhuǎn)發(fā)算法，避免了使用Flooding來查詢消息。缺點(diǎn)：不適合在移動(dòng)WSN中使用。

第五十頁，共88頁。1.3.4LEACH(LowEnergyAdaptiveClusteringHierarchy)

LEACH是第一個(gè)提出數(shù)據(jù)聚合思想的單層簇DC協(xié)議。其主要思想為通過在每個(gè)周期內(nèi)通過一個(gè)概率函數(shù)隨機(jī)選擇簇頭(ClusterHead),由簇頭來平均分擔(dān)中繼通信業(yè)務(wù)以實(shí)現(xiàn)延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。一旦簇頭被選定，則簇成員(ClusterMember)節(jié)點(diǎn)將采集到的監(jiān)測(cè)數(shù)據(jù)傳與簇頭，簇頭在進(jìn)行必要的數(shù)據(jù)匯聚處理之后，再將匯聚數(shù)據(jù)直接發(fā)送到用戶。LEACH具有能量感知功能，能均衡節(jié)點(diǎn)的能量消耗，提高網(wǎng)絡(luò)的穩(wěn)定性與生命周期；但算法中對(duì)簇頭可通過長(zhǎng)距離信號(hào)發(fā)射直接與用戶進(jìn)行通信的假設(shè)不切實(shí)際，因此算法的實(shí)用性較差。

第五十一頁，共88頁。1.3.4LEACH(LowEnergyAdaptiveClusteringHierarchy)

LEACH中概率函數(shù)的推導(dǎo)過程需求：讓所有節(jié)點(diǎn)輪流成為簇頭，從而使得網(wǎng)絡(luò)中各節(jié)點(diǎn)的能耗更加均勻。Step1：首先要確定得經(jīng)過多少輪才能使得所有節(jié)點(diǎn)都有機(jī)會(huì)能成為簇頭？顯然，為了解決該問題，則需要增加一個(gè)限制條件，即需要預(yù)先知道將整個(gè)網(wǎng)絡(luò)劃分為多少個(gè)簇，否則問題將無法求解?；谏鲜龇治?，因此可先給出一個(gè)假定如下：假定簇頭節(jié)點(diǎn)占網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的百分比為p。由該假定即可計(jì)算出經(jīng)過1/p輪才能使得所有節(jié)點(diǎn)都有機(jī)會(huì)能成為簇頭。第五十二頁，共88頁。1.3.4LEACH(LowEnergyAdaptiveClusteringHierarchy)

LEACH中概率函數(shù)的推導(dǎo)過程(Cont.)Step2：顯然，在最近1/p輪中已經(jīng)成為過簇頭的節(jié)點(diǎn)不能再成為簇頭。因此，可初步設(shè)計(jì)判定節(jié)點(diǎn)n在當(dāng)前輪中成為簇頭的概率函數(shù)T(n)如下：T(n)=0，若nG，其中G表示網(wǎng)絡(luò)中最近1/p輪未當(dāng)選簇頭的節(jié)點(diǎn)的集合。顯然，現(xiàn)在剩下的問題是需要針對(duì)nG時(shí)給出其在當(dāng)前輪中成為簇頭的概率函數(shù)T(n)。Step3：那么，如何確定T(n)呢？先考慮最特殊的情形，假定當(dāng)前輪為第1/p輪，顯然，所有未當(dāng)選為簇頭的節(jié)點(diǎn)均需要當(dāng)選為簇頭，即nG時(shí)，其成為簇頭的概率函數(shù)T(n)應(yīng)等于1。因此，可修正判定節(jié)點(diǎn)n在當(dāng)前輪中成為簇頭的概率函數(shù)T(n)如下：T(n)=1，若nG，且rmod1/p=1/p-1{即1/p–(rmod1/p)=1}，其中r表示到目前為止經(jīng)過的總的輪數(shù)。至此，剩下的問題為僅需要確定當(dāng)nG，且1/p–(rmod1/p)1時(shí)其在當(dāng)前輪中成為簇頭的概率函數(shù)T(n)。

第五十三頁，共88頁。1.3.4LEACH(LowEnergyAdaptiveClusteringHierarchy)

LEACH中概率函數(shù)的推導(dǎo)過程(Cont.)Step4：顯然，節(jié)點(diǎn)n在最近1/p輪中越晚未當(dāng)選為簇頭，其應(yīng)以越大的概率在當(dāng)前輪中成為簇頭，即當(dāng)1/p-(rmod1/p)越小，則節(jié)點(diǎn)n在當(dāng)前輪中成為簇頭的概率應(yīng)越大。因此，可修正判定節(jié)點(diǎn)n在當(dāng)前輪中成為簇頭的概率函數(shù)T(n)如下：T(n)==，若nG。Step5：綜上所述，可得到節(jié)點(diǎn)n在當(dāng)前輪中成為簇頭的概率函數(shù)T(n)如下：第五十四頁，共88頁。1.3.4LEACH(LowEnergyAdaptiveClusteringHierarchy)LEACH的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：使得網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗更加均勻。

缺點(diǎn)：不能保障簇頭節(jié)點(diǎn)能夠遍及整個(gè)網(wǎng)絡(luò)，也不能保證簇的大小近似均勻。

第五十五頁，共88頁。1.3.5TTDD(TwoTierDataDissemination)

TTDD是一種基于層次簇的路由協(xié)議，其適用的環(huán)境為靜止傳感區(qū)域內(nèi)的移動(dòng)Sink節(jié)點(diǎn)的情形。在TTDD協(xié)議中，由源節(jié)點(diǎn)首先基于節(jié)點(diǎn)的位置信息分布式地將傳感區(qū)域劃分成網(wǎng)格(Grid)，同時(shí)為每個(gè)網(wǎng)格確定一個(gè)傳播節(jié)點(diǎn)(Disseminationnode)，并使得相鄰傳播節(jié)點(diǎn)之間的距離為1跳；源節(jié)點(diǎn)默認(rèn)為其所在網(wǎng)格的傳播節(jié)點(diǎn)。

在實(shí)際進(jìn)行路由時(shí)，Sink節(jié)點(diǎn)利用不同方式分兩個(gè)層次進(jìn)行路由。

首先Sink節(jié)點(diǎn)利用洪泛在自己所屬的網(wǎng)格內(nèi)廣播查詢，直到查詢消息到達(dá)其所屬網(wǎng)格的傳播節(jié)點(diǎn)；該路由過程稱為”低層”路由。當(dāng)查詢到達(dá)Sink節(jié)點(diǎn)所屬網(wǎng)格的傳播節(jié)點(diǎn)后，傳播節(jié)點(diǎn)直接將查詢轉(zhuǎn)發(fā)給自己相鄰網(wǎng)格的傳播節(jié)點(diǎn)，依次類推，直到查詢到達(dá)源節(jié)點(diǎn)；該路由過程稱為”高層”路由。源節(jié)點(diǎn)在傳輸數(shù)據(jù)時(shí)，數(shù)據(jù)通過傳播節(jié)點(diǎn)的轉(zhuǎn)發(fā)最終到達(dá)Sink節(jié)點(diǎn)，在傳輸過程中，傳播節(jié)點(diǎn)對(duì)數(shù)據(jù)進(jìn)行匯聚處理，從而可以減低數(shù)據(jù)的傳輸開銷，達(dá)到節(jié)能的目的。

第五十六頁，共88頁。1.3.5TTDD(TwoTierDataDissemination)

TTDD的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：提出了一種新的應(yīng)用場(chǎng)景，支持Sink移動(dòng)的網(wǎng)絡(luò)環(huán)境。

缺點(diǎn)：需要地理位置信息的支持，且網(wǎng)格大小不容易確定。

第五十七頁，共88頁。1.3.6Rumor

Rumor的工作原理：如果Sink點(diǎn)的一次查詢只需一次上報(bào)，DirectedDiffusion協(xié)議開銷就太大了，Rumor協(xié)議正是為解決此問題而設(shè)計(jì)的。該協(xié)議借鑒了歐氏平面圖上任意兩條曲線交叉幾率很大的思想。當(dāng)節(jié)點(diǎn)監(jiān)測(cè)到事件后將其保存，并創(chuàng)建稱為Agent的生命周期較長(zhǎng)的包括事件和源節(jié)點(diǎn)信息的數(shù)據(jù)包，將其按一條或多條隨機(jī)路徑在網(wǎng)絡(luò)中轉(zhuǎn)發(fā)。收到Agent的節(jié)點(diǎn)根據(jù)事件和源節(jié)點(diǎn)信息建立反向路徑，并將Agent再次隨機(jī)發(fā)送到相鄰節(jié)點(diǎn)，并可在再次發(fā)送前在Agent中增加其已知的事件信息。Sink點(diǎn)的查詢請(qǐng)求也沿著一條隨機(jī)路徑轉(zhuǎn)發(fā)，當(dāng)兩路徑交叉時(shí)則路由建立。如不交叉，Sink點(diǎn)可flooding查詢請(qǐng)求。

在多Sink點(diǎn)、查詢請(qǐng)求數(shù)目很大、網(wǎng)絡(luò)事件很少的情況下，Rumor協(xié)議較為有效。但如果事件非常多，維護(hù)事件表和收發(fā)Agent帶來的開銷會(huì)很大。

第五十八頁，共88頁。1.3.7無線傳感器網(wǎng)絡(luò)的組播與選播路由協(xié)議

目前，無線傳感器網(wǎng)絡(luò)路由協(xié)議著重研究的基本上是單播(Unicast)路由。事實(shí)上，在傳感器網(wǎng)絡(luò)應(yīng)用中還經(jīng)常要求提供組播(Multicast)和選播(Anycast)支持技術(shù)。例如，在對(duì)軍事目標(biāo)的監(jiān)控中經(jīng)常要求對(duì)同一目標(biāo)進(jìn)行分組監(jiān)測(cè)等。而組播與選播技術(shù)的引入必將導(dǎo)致對(duì)服務(wù)質(zhì)量的要求。目前，典型的QoS組播和選播算法包括：QoS組播算法：Mobicast(Mobicast:Just-in-timemulticastforsensornetworksunderspatiotemporalconstraints)、VLM2(VeryLightweightMobileMulticast)等。QoS選播算法：SARP(Sink-basedAnycastRoutingProtocol)等。

第五十九頁，共88頁。1.3.7無線傳感器網(wǎng)絡(luò)的組播與選播路由協(xié)議

組播、廣播、單播、選播的定義：組播：是指一臺(tái)主機(jī)與一組目的主機(jī)之間的通信。廣播：是指一臺(tái)主機(jī)與所有目的主機(jī)之間的通信。單播：是指一臺(tái)主機(jī)與另一臺(tái)目的主機(jī)之間的通信。從投遞目的地的數(shù)量而言，單播和廣播均可看作是組播的一個(gè)子集。單播可以看作僅包括一臺(tái)機(jī)器群組的組播；廣播可以看作包含了所有機(jī)器的組播。選播：是指一臺(tái)主機(jī)與一組目的主機(jī)之間最“近”的一個(gè)之間的通信。

第六十頁，共88頁。1.3.8無線傳感器網(wǎng)絡(luò)路由協(xié)議的發(fā)展趨勢(shì)

減少通信量以節(jié)約能量：由于WSN中數(shù)據(jù)通信最為耗能，因此應(yīng)在協(xié)議中盡量減少數(shù)據(jù)通信量。例如，可在數(shù)據(jù)查詢或者數(shù)據(jù)上報(bào)中采用某種過濾機(jī)制，抑制節(jié)點(diǎn)上傳不必要的數(shù)據(jù)。或采用數(shù)據(jù)聚合機(jī)制，在數(shù)據(jù)傳輸?shù)絊ink點(diǎn)前就完成可能的數(shù)據(jù)計(jì)算。保持通信量負(fù)載平衡：通過更加靈活地使用路由策略讓各個(gè)節(jié)點(diǎn)分擔(dān)數(shù)據(jù)傳輸，平衡節(jié)點(diǎn)的剩余能量，提高整個(gè)網(wǎng)絡(luò)的生存時(shí)間。例如，可在層次路由中采用動(dòng)態(tài)簇頭。在路由選擇中采用隨機(jī)路由而非穩(wěn)定路由。在路徑選擇中考慮節(jié)點(diǎn)的剩余能量。第六十一頁，共88頁。1.3.8無線傳感器網(wǎng)絡(luò)路由協(xié)議的發(fā)展趨勢(shì)

路由協(xié)議應(yīng)具有容錯(cuò)性：由于WSN節(jié)點(diǎn)容易發(fā)生故障，因此應(yīng)盡量利用節(jié)點(diǎn)易獲得的網(wǎng)絡(luò)信息計(jì)算路由，以確保在路由出現(xiàn)故障時(shí)能夠盡快得到恢復(fù)，并可采用多路徑傳輸來提高數(shù)據(jù)傳輸?shù)目煽啃浴Ｂ酚蓞f(xié)議應(yīng)具有安全機(jī)制：由于WSN的固有特性，其路由協(xié)議極易受到安全威脅，尤其是在軍事應(yīng)用中。目前的路由協(xié)議很少考慮安全問題，因此在一些應(yīng)用中必須考慮設(shè)計(jì)具有安全機(jī)制的路由協(xié)議。WSN路由協(xié)議將繼續(xù)向基于數(shù)據(jù)、基于位置的方向發(fā)展。這是由WSN一般不統(tǒng)一編址和以數(shù)據(jù)、位置為中心的特點(diǎn)決定的。第六十二頁，共88頁。1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

TopologyControl研究問題介紹在保證一定的網(wǎng)絡(luò)連通質(zhì)量和覆蓋質(zhì)量的前提下,一般以延長(zhǎng)網(wǎng)絡(luò)的生命期為主要目標(biāo)，兼顧通信干擾、網(wǎng)絡(luò)延遲、負(fù)載均衡、簡(jiǎn)單性、可靠性、可擴(kuò)展性等其他性能，形成一個(gè)優(yōu)化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。TopologyControl的重要性拓?fù)淇刂剖且环N重要的節(jié)能技術(shù)拓?fù)淇刂票ＷC覆蓋質(zhì)量和連通質(zhì)量拓?fù)淇刂颇軌蚪档屯ㄐ鸥蓴_延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間提高M(jìn)AC(mediaaccesscontrol)協(xié)議和路由協(xié)議的效率為數(shù)據(jù)融合提供拓?fù)浠A(chǔ)提高網(wǎng)絡(luò)的可靠性、可擴(kuò)展性等其他性能拓?fù)淇刂茖?duì)網(wǎng)絡(luò)性能具有重大的影響第六十三頁，共88頁。網(wǎng)絡(luò)中常見的拓?fù)浣Y(jié)構(gòu):

1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第六十四頁，共88頁。無線傳感器網(wǎng)絡(luò)中TopologyControl研究的主流方向:功率控制:就是為傳感器節(jié)點(diǎn)選擇合適的發(fā)射功率;睡眠調(diào)度:就是控制傳感器節(jié)點(diǎn)在工作狀態(tài)和睡眠狀態(tài)之間的轉(zhuǎn)換.

TopologyControl的主要形式:靜態(tài)節(jié)點(diǎn)不可控部署靜態(tài)節(jié)點(diǎn)隨機(jī)地部署到給定的區(qū)域；稀疏網(wǎng)絡(luò)的功率控制和對(duì)密集網(wǎng)絡(luò)的睡眠調(diào)度是兩種主要的拓?fù)淇刂萍夹g(shù)；靜態(tài)節(jié)點(diǎn)可控部署節(jié)點(diǎn)通過人或機(jī)器人部署到固定的位置.拓?fù)淇刂浦饕峭ㄟ^控制節(jié)點(diǎn)的位置來實(shí)現(xiàn)的,功率控制和睡眠調(diào)度雖然可以使用,但已經(jīng)是次要的了動(dòng)態(tài)節(jié)點(diǎn)不可控部署稱為移動(dòng)自組織網(wǎng)絡(luò)(mobileadhocnetwork,簡(jiǎn)稱MANET)其挑戰(zhàn)是無論獨(dú)立自治的節(jié)點(diǎn)如何運(yùn)動(dòng),都要保證網(wǎng)絡(luò)的正常運(yùn)轉(zhuǎn).功率控制是主要的拓?fù)淇刂萍夹g(shù)動(dòng)態(tài)節(jié)點(diǎn)可控部署移動(dòng)節(jié)點(diǎn)能夠相互定位.拓?fù)淇刂茩C(jī)制融入到移動(dòng)和定位策略中.因?yàn)橐苿?dòng)是主要的能量消耗,所以節(jié)點(diǎn)間的能量高效通信不再是首要問題.因?yàn)橐苿?dòng)節(jié)點(diǎn)的部署不太可能是密集的,所以睡眠調(diào)度也不重要.1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第六十五頁，共88頁。相關(guān)概念:覆蓋:看成是對(duì)傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的度量.區(qū)域覆蓋:研究對(duì)目標(biāo)區(qū)域的覆蓋(監(jiān)測(cè))問題;點(diǎn)覆蓋:研究對(duì)一些離散的目標(biāo)點(diǎn)的覆蓋問題;柵欄覆蓋:研究運(yùn)動(dòng)物體穿越網(wǎng)絡(luò)部署區(qū)域被發(fā)現(xiàn)的概率問題.k-覆蓋/覆蓋度為k:如果目標(biāo)區(qū)域中的任何一點(diǎn)都被k個(gè)傳感器節(jié)點(diǎn)監(jiān)測(cè).部分覆蓋漸近覆蓋:當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)趨于無窮大時(shí),完全覆蓋目標(biāo)區(qū)域的概率趨于1完全覆蓋:Voronoi圖是常用的覆蓋分析工具.

1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第六十六頁，共88頁。Voronoi圖/泰森多邊形/Dirichlet圖:它是由一組由連接兩鄰點(diǎn)直線的垂直平分線組成的連續(xù)多邊形組成，N個(gè)平面上有區(qū)別的點(diǎn)，按照最鄰近原則劃分平面；每個(gè)點(diǎn)與它的最近領(lǐng)區(qū)域相關(guān)聯(lián)。

應(yīng)用：(1)圖形學(xué)、機(jī)械工程、虛擬現(xiàn)實(shí)、地理信息系統(tǒng)、機(jī)器人、圖像處理、CAD等;(2)解決距離計(jì)算、碰撞檢測(cè)、路徑規(guī)劃、Delaunay三角化、骨架計(jì)算、凸包計(jì)算以及可見性計(jì)算等計(jì)算幾何其它問題的有效工具1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第六十七頁，共88頁。相關(guān)概念:連通:k-連通/連通度為k:如果至少要去掉k個(gè)傳感器節(jié)點(diǎn)才能使網(wǎng)絡(luò)不連通討論漸近意義下的連通,亦即當(dāng)部署區(qū)域趨于無窮大時(shí),網(wǎng)絡(luò)連通的可能性趨于1網(wǎng)絡(luò)生命期:定義為直到死亡節(jié)點(diǎn)的百分比低于某個(gè)閾值時(shí)的持續(xù)時(shí)間;可以通過對(duì)網(wǎng)絡(luò)的服務(wù)質(zhì)量的度量來定義網(wǎng)絡(luò)的生命期.吞吐能力:目標(biāo)區(qū)域是一個(gè)凸區(qū)域,每個(gè)節(jié)點(diǎn)的吞吐率為λbits/s.

A是目標(biāo)區(qū)域的面積;W是節(jié)點(diǎn)的最高傳輸速率;π是圓周率;Δ是大于0的常數(shù);L是源節(jié)點(diǎn)到目的節(jié)點(diǎn)的平均距離;n是節(jié)點(diǎn)數(shù);r是理想球狀無線電發(fā)射模型的發(fā)射半徑通過功率控制減小發(fā)射半徑和通過睡眠調(diào)度減小工作網(wǎng)絡(luò)的規(guī)模,在節(jié)省能量的同時(shí),可以在一定程度上提高網(wǎng)絡(luò)的吞吐能力.1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第六十八頁，共88頁。補(bǔ)充：1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第六十九頁，共88頁。相關(guān)概念:干擾和競(jìng)爭(zhēng):

減小通信干擾、減少M(fèi)AC層的競(jìng)爭(zhēng)和延長(zhǎng)網(wǎng)絡(luò)的生命期基本上是一致的網(wǎng)絡(luò)無線信道競(jìng)爭(zhēng)區(qū)域的大小與節(jié)點(diǎn)的發(fā)射半徑r成正比,所以減小r就可以減少競(jìng)爭(zhēng).網(wǎng)絡(luò)延遲:

當(dāng)網(wǎng)絡(luò)負(fù)載較低時(shí),高發(fā)射功率減少了源節(jié)點(diǎn)到目的節(jié)點(diǎn)的跳數(shù),所以降低了端到端的延遲;當(dāng)網(wǎng)絡(luò)負(fù)載較高時(shí),節(jié)點(diǎn)對(duì)信道的競(jìng)爭(zhēng)是激烈的,低發(fā)射功率由于緩解了競(jìng)爭(zhēng)而減小了網(wǎng)絡(luò)延遲.拓?fù)湫再|(zhì):

除了連通性之外,對(duì)稱性、平面性、稀疏性、節(jié)點(diǎn)度的有界性、有限伸展性(spannerproperty)等,都是希望具有的性質(zhì),還要考慮諸如負(fù)載均衡、簡(jiǎn)單性、可靠性、可擴(kuò)展性等其他方面.拓?fù)淇刂频母鞣N設(shè)計(jì)目標(biāo)之間有著錯(cuò)綜復(fù)雜的關(guān)系.

對(duì)這些關(guān)系的研究也是拓?fù)淇刂蒲芯康闹匾獌?nèi)容.

1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第七十頁，共88頁。功率控制通過降低節(jié)點(diǎn)的發(fā)射功率來延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間睡眠調(diào)度

對(duì)于節(jié)點(diǎn)密集型和事件驅(qū)動(dòng)型的網(wǎng)絡(luò)十分有效1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第七十一頁，共88頁。功率控制/RangeAssignment(RA)問題.設(shè)N={u1,…,un}是d(d=1,2,3)維空間中代表網(wǎng)絡(luò)節(jié)點(diǎn)位置的點(diǎn)的集合,r(ui)代表節(jié)點(diǎn)ui的發(fā)射半徑.RA問題就是要在保證網(wǎng)絡(luò)連通的前提下,使網(wǎng)絡(luò)的發(fā)射功率(各節(jié)點(diǎn)的發(fā)射功率的總和)最小.Min試圖尋找功率控制問題的最優(yōu)解是不現(xiàn)實(shí)的,應(yīng)該從實(shí)際出發(fā),尋找功率控制問題的實(shí)用解/可行解;1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第七十二頁，共88頁。功率控制算法分類：

(1)與路由協(xié)議結(jié)合的功率控制(2)基于節(jié)點(diǎn)度的功率控制(3)基于方向的功率控制(4)基于鄰近圖的功率控制(5)XTC算法

1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第七十三頁，共88頁。功率控制算法分類：(1)與路由協(xié)議結(jié)合的功率控制

COMPOW:(CommonPower)基本思想是:所有傳感器節(jié)點(diǎn)使用一致的發(fā)射功率,在保證網(wǎng)絡(luò)連通的前提下,將功率最小化.基本步驟:

優(yōu)缺點(diǎn):在節(jié)點(diǎn)分布均勻的情況下,COMPOW具有較好的性能.但是,一個(gè)相對(duì)孤立的節(jié)點(diǎn)會(huì)導(dǎo)致所有的節(jié)點(diǎn)使用很大的發(fā)射功率,所以在節(jié)點(diǎn)分布不均的情況下,它的缺陷是明顯的.1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第七十四頁，共88頁。功率控制算法分類：

(2)基于節(jié)點(diǎn)度的功率控制LMA:LocalMeanAlgorithmLMN:LocalMeanofNeighborsAlgorithm

基本思想是:

給定節(jié)點(diǎn)度的上限和下限,每個(gè)節(jié)點(diǎn)動(dòng)態(tài)地調(diào)整自己的發(fā)射功率,使得節(jié)點(diǎn)的度數(shù)落在上限和下限之間.缺點(diǎn):算法一般難以保證網(wǎng)絡(luò)的連通性.

1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第七十五頁，共88頁。功率控制算法分類：(3)基于方向的功率控制CBTC:(Cone(圓錐)-baseddistributedtopology-control),能夠保證網(wǎng)絡(luò)連通性的基于方向的算法

基本思想是:節(jié)點(diǎn)u選擇最小功率pu,ρ,使得在任何以u(píng)為中心的角度為ρ的錐形區(qū)域內(nèi)至少有一個(gè)鄰居.文章證明了當(dāng)ρ≤5π/6時(shí),可以保證網(wǎng)絡(luò)的連通.特點(diǎn):基于方向的算法需要可靠的方向信息,因而需要很好地解決到達(dá)角度問題,節(jié)點(diǎn)需要配備多個(gè)有向天線,因而對(duì)傳感器節(jié)點(diǎn)提出了較高的要求.

1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第七十六頁，共88頁。功率控制算法分類：(4)基于鄰近圖的功率控制DRNG:DirectedRelativeNeighborhoodGraph)基于有向RNG(鄰近圖)DLMST:DirectedLocalMinimumSpanningTree)基于有向局部MST(最小生成樹)基本思想是:

設(shè)所有節(jié)點(diǎn)都使用最大發(fā)射功率發(fā)射時(shí)形成的拓?fù)鋱D是G,按照一定的鄰居判別條件求出該圖的鄰近圖G′,每個(gè)節(jié)點(diǎn)以自己所鄰接的最遠(yuǎn)節(jié)點(diǎn)來確定發(fā)射功率.特點(diǎn):能夠保證網(wǎng)絡(luò)的連通性在平均功率和節(jié)點(diǎn)度等方面具有較好的性能.基于鄰近圖的功率控制一般需要精確的位置信息1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第七十七頁，共88頁。功率控制算法分類：(5)XTC算法

微軟亞洲研究院的Wattenhofer等人提出的XTC[18]算法:對(duì)傳感器節(jié)點(diǎn)沒有太高的要求對(duì)部署環(huán)境也沒有過強(qiáng)的假設(shè),提供了一個(gè)面向簡(jiǎn)單、實(shí)用的研究方向.XTC代表了功率控制的發(fā)展趨勢(shì)XTC的基本思想:是用接收信號(hào)的強(qiáng)度作為RNG(relativeneighborhoodgraph)中的距離度量.XTC算法可分為如下3步:1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第七十八頁，共88頁。偏序：若集合X上的關(guān)系R是自反的、反對(duì)稱的和傳遞的，則稱只是集合X上的偏序關(guān)系。(如：實(shí)數(shù)集上的<=關(guān)系,>=關(guān)系)全序：設(shè)R是集合X上的偏序(Partial

Order)，如果對(duì)每個(gè)x,y∈X必有xRy或yRx，則稱R是集合X上的全序關(guān)系。

直觀地看，偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。功率控制算法分類：(5)XTC算法補(bǔ)充概念：(集合論)三歧性定理：在實(shí)數(shù)域，這種關(guān)系表現(xiàn)為“三歧性”，即對(duì)任意兩個(gè)實(shí)數(shù)，必然存在：要么a>b；要么a<b；要么a=b。1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第七十九頁，共88頁。功率控制算法分類：(5)XTC算法

XTC的優(yōu)缺點(diǎn):不需要位置信息對(duì)傳感器節(jié)點(diǎn)沒有太高的要求適用于異構(gòu)網(wǎng)絡(luò)也適用于三維空間與大多數(shù)其他算法相比,XTC更簡(jiǎn)單,更實(shí)用XTC與實(shí)用化要求仍然有一定的距離(如:XTC并沒有考慮到通信鏈路質(zhì)量的變化)1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第八十頁，共88頁。睡眠調(diào)度算法分類：(1)非層次型網(wǎng)絡(luò)的睡眠調(diào)度算法當(dāng)然也可以用在層次型網(wǎng)絡(luò)中,因?yàn)樗鼈兛梢栽诖氐膬?nèi)部使用.(2)層次型網(wǎng)絡(luò)的睡眠調(diào)度算法非層次型/平面的:如果網(wǎng)絡(luò)中的節(jié)點(diǎn)都具有相同的功能,扮演相同的角色層次型的/基于簇的:反之1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第八十一頁，共88頁。睡眠調(diào)度算法分類：(1)非層次型網(wǎng)絡(luò)的睡眠調(diào)度算法基本思想是:每個(gè)節(jié)點(diǎn)根據(jù)自己所能獲得的信息,獨(dú)立地控制自己在工作狀態(tài)和睡眠狀態(tài)之間的轉(zhuǎn)換.它與層次型睡眠調(diào)度的主要區(qū)別在于:每個(gè)節(jié)點(diǎn)都不隸屬于某個(gè)簇,因而不受簇頭節(jié)點(diǎn)的控制和影響.RIS:RandomizedIndependentSleepingRIS將時(shí)間劃分為周期,在每個(gè)周期的開始,每個(gè)節(jié)點(diǎn)以某一概率獨(dú)立地決定自己是否進(jìn)入睡眠狀態(tài).RIS需要較為嚴(yán)格的時(shí)間同步1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第八十二頁，共88頁。睡眠調(diào)度算法分類：(2)層次型網(wǎng)絡(luò)的睡眠調(diào)度算法基本思想是:由簇頭節(jié)點(diǎn)組成骨干網(wǎng)絡(luò)(Backbone),則其他節(jié)點(diǎn)就可以(當(dāng)然未必)進(jìn)入睡眠狀態(tài).層次型網(wǎng)絡(luò)睡眠調(diào)度的關(guān)鍵技術(shù)是分簇.

LEACH:需要較為嚴(yán)格的時(shí)間同步,也不能保證簇頭均勻分布EECS:EnergyEfficientClusteringScheme能夠保證簇頭的均勻分布,但EECS與LEACH一樣,簇頭與匯聚節(jié)點(diǎn)的單跳通信方式限制了網(wǎng)絡(luò)的規(guī)模LDS:LinearDistance-basedScheduling適用于基于簇的高密度傳感器網(wǎng)絡(luò),只考慮簇內(nèi)的睡眠調(diào)度,它假設(shè)分簇結(jié)構(gòu)已經(jīng)存在.但是,LDS不能保證能量的均勻消耗1.4無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍夹g(shù)

第八十三頁，共88頁。睡眠調(diào)度算法分類：(2)層次型網(wǎng)絡(luò)的睡眠調(diào)度算法GAF:GeographicalAdaptiveFidelity以節(jié)點(diǎn)地理位置為分簇依據(jù),把監(jiān)測(cè)區(qū)域劃分成正方形虛擬單元格,將節(jié)點(diǎn)按照位置信息劃入相應(yīng)的單元格,相鄰單元格的任意兩個(gè)節(jié)點(diǎn)可直接通信.GAF節(jié)點(diǎn)有3種狀態(tài):工作狀態(tài)、睡眠狀態(tài)、發(fā)現(xiàn)狀態(tài).每個(gè)單元格只有一個(gè)隨機(jī)產(chǎn)生的簇頭節(jié)點(diǎn)處于工作狀