現(xiàn)代通信技術(shù)課程9

1、4、 網(wǎng)絡(luò)路由協(xié)議原理網(wǎng)絡(luò)路由協(xié)議原理 4.1 有線路由協(xié)議有線路由協(xié)議 4.2 無(wú)線路由協(xié)議無(wú)線路由協(xié)議 4.3 機(jī)會(huì)路由協(xié)議機(jī)會(huì)路由協(xié)議 現(xiàn)代通信技術(shù)課程現(xiàn)代通信技術(shù)課程主講：宋梁，主講：宋梁，LSONGIEEE.ORGLSONGIEEE.ORGQQQQ群：群：3149458742015-20162015-2016本堂內(nèi)容本堂內(nèi)容無(wú)線自組網(wǎng)無(wú)線自組網(wǎng)無(wú)線傳感網(wǎng)無(wú)線傳感網(wǎng)什么是無(wú)線自組網(wǎng)？無(wú)線自組網(wǎng)（Wireless Adhoc Network）是一組以無(wú)線鏈路進(jìn)行通信、由移動(dòng)節(jié)點(diǎn)動(dòng)態(tài)形成的網(wǎng)絡(luò)，它是一個(gè)多跳的臨時(shí)性自治系統(tǒng)。最早由美國(guó)DOD的PRNET項(xiàng)目進(jìn)行研究，主要用于軍事領(lǐng)域。但是由

2、于無(wú)線自組網(wǎng)構(gòu)造時(shí)不需要預(yù)先存在的網(wǎng)絡(luò)基礎(chǔ)設(shè)施，如基站等，因此在民用領(lǐng)域中也具有廣闊的應(yīng)用，如發(fā)生地震、水災(zāi)后的營(yíng)救等。隨著無(wú)線通信技術(shù)和移動(dòng)終端技術(shù)的發(fā)展，Ad hoc網(wǎng)絡(luò)在軍用和民用等領(lǐng)域的應(yīng)用日益受到重視，各方面的研究不斷展開(kāi)。無(wú)線自組網(wǎng)路由協(xié)議設(shè)計(jì)面臨的問(wèn)題多播支持QoS 支持節(jié)能支持位置支持單向信道支持有限帶寬支持當(dāng)前主要無(wú)線分組網(wǎng)路由協(xié)議分析 無(wú)線分組網(wǎng)路由協(xié)議根據(jù)所采用的路由策略可分為主動(dòng)路由和按需路由兩種。主動(dòng)路由 采用預(yù)先獲?。≒roactive）策略按需路由 采用按需獲?。≧eactive）策略當(dāng)前主要無(wú)線分組網(wǎng)路由協(xié)議分析主動(dòng)路由協(xié)議DSDVDSDVOLSROLSRLAN

3、MARLANMAR主動(dòng)路由協(xié)議要求每個(gè)節(jié)點(diǎn)維護(hù)一張或幾張路由表，其中包含了網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的路由信息。所有節(jié)點(diǎn)周期性地更新這些路由表，以保證路由信息是一致和最新的，當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)改變時(shí)，節(jié)點(diǎn)向整個(gè)網(wǎng)絡(luò)傳播路由變更消息。主動(dòng)路由的優(yōu)點(diǎn)是當(dāng)?shù)侥繕?biāo)節(jié)點(diǎn)的路由存在時(shí)，延時(shí)很小；缺點(diǎn)是需要花費(fèi)較大的開(kāi)銷保持路由更新。DSDVDSDV（Distance Source Distance Distance Source Distance VectorVector）DSDV 協(xié)議是著名的Bellman-Ford 路由算法的增強(qiáng)版本,是在DVA 基礎(chǔ)上進(jìn)行改進(jìn)設(shè)計(jì)的，被認(rèn)為是最早的自組網(wǎng)路由協(xié)議。在DSDV 協(xié)

4、議中，每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)路由表，用于記錄到所有可達(dá)目標(biāo)的“下次跳轉(zhuǎn)”。DSDV 協(xié)議的特點(diǎn)是采用了序列號(hào)機(jī)制來(lái)區(qū)別路由的新舊程度，防止路由環(huán)的產(chǎn)生；其缺點(diǎn)是不適應(yīng)快速變化的自組網(wǎng)，不支持單向信道。DSDVDSDVOLSROLSR（Optimized Link State RoutingOptimized Link State Routing）OLSR 是對(duì)鏈路狀態(tài)協(xié)議的優(yōu)化，以適應(yīng)無(wú)線自組網(wǎng)的需求。OLSR 的關(guān)鍵是使用了多點(diǎn)中繼MPR（MultiPointRelay）。節(jié)點(diǎn)通常選擇一組一次跳轉(zhuǎn)鄰居節(jié)點(diǎn)作為它的MPR集，在MPR 和MPR 選擇者之間必須存在雙向鏈路，并且MPR 集能夠與MPR

5、選擇者的所有二次跳轉(zhuǎn)鄰居通信。在 OLSR 協(xié)議中，信息通過(guò)MPR 在網(wǎng)絡(luò)中傳遞,因?yàn)橹挥泻苌俚腗PR,所以控制包的數(shù)目和大小都得到很大精簡(jiǎn)。OLSR 協(xié)議比較適合于節(jié)點(diǎn)數(shù)目多且密集的網(wǎng)絡(luò)。OLSROLSRLANMARLANMAR（Landmark Routing Protocol for Landmark Routing Protocol for Large ScaleLarge Scale NetworksNetworks）當(dāng)網(wǎng)絡(luò)尺度增大和節(jié)點(diǎn)的移動(dòng)性增強(qiáng)時(shí)，過(guò)多的處理開(kāi)銷使得平面形式的主動(dòng)路由模式變得不可行，LANMAR 使用層次路由解決網(wǎng)絡(luò)伸縮性和路由開(kāi)銷問(wèn)題。LANMAR 協(xié)議將網(wǎng)絡(luò)

6、劃分為一些邏輯子網(wǎng)，這些子網(wǎng)中的成員具有某種共性，因此子網(wǎng)節(jié)點(diǎn)很可能作為一個(gè)群體整體性地移動(dòng)。LANMAR在邏輯子網(wǎng)內(nèi)使用FSR（Fisheye State Routing）無(wú)線自組網(wǎng)協(xié)議，一個(gè)節(jié)點(diǎn)與距離較近的節(jié)點(diǎn)交換路由信息的頻率要遠(yuǎn)大于與距離遠(yuǎn)的節(jié)點(diǎn)交換路由信息的頻率，因此可以減少路由開(kāi)銷。LANMARLANMAR當(dāng)前主要無(wú)線分組網(wǎng)路由協(xié)議分析按需路由協(xié)議DSRDSRAODV層次路由層次路由與表驅(qū)動(dòng)的主動(dòng)路由協(xié)議不同，按需路由協(xié)議并不在每個(gè)節(jié)點(diǎn)上維護(hù)最新的路由信息，而是在某個(gè)路由信息需要時(shí)才去動(dòng)態(tài)獲取路由信息。采用按需路由協(xié)議的優(yōu)點(diǎn)是不需要進(jìn)行周期性的路由信息廣播，節(jié)省了一定的網(wǎng)絡(luò)資源；缺

7、點(diǎn)是發(fā)送數(shù)據(jù)分組時(shí)，如果沒(méi)有去往目標(biāo)節(jié)點(diǎn)的路由，數(shù)據(jù)分組需要等待因路由發(fā)現(xiàn)而帶來(lái)的延時(shí)。 DSR 是最早采用按需路由思想的路由協(xié)議，它使用了源路由機(jī)制進(jìn)行分組轉(zhuǎn)發(fā)，在每個(gè)包的包頭攜帶一個(gè)完整的節(jié)點(diǎn)序列，由于包本身已經(jīng)包含了所有的路由判定，因此中間節(jié)點(diǎn)不需要維護(hù)最新的路由信息就能完成包轉(zhuǎn)發(fā)。DSRDSR（D DYNAMICYNAMIC S SOURCEOURCE R ROUTINGOUTING）DSR協(xié)議主要由兩個(gè)機(jī)制構(gòu)成：路由發(fā)現(xiàn)和路由維護(hù)，這兩種機(jī)制都采用按需方式操作。當(dāng)源節(jié)點(diǎn)不知道到達(dá)標(biāo)節(jié)點(diǎn)的路由時(shí)，源節(jié)點(diǎn)采用路由發(fā)現(xiàn)機(jī)制動(dòng)態(tài)地獲得這個(gè)路由，源節(jié)點(diǎn)向網(wǎng)絡(luò)廣播路由請(qǐng)求（RREQ）包。每個(gè)接收

8、到RREQ包的節(jié)點(diǎn)將重傳這個(gè)包，除非它本身是目標(biāo)節(jié)點(diǎn)或者在該節(jié)點(diǎn)的路由緩沖中保持了到達(dá)目標(biāo)節(jié)點(diǎn)的路由，在后兩種情況下，該節(jié)點(diǎn)將向源節(jié)點(diǎn)發(fā)送路由應(yīng)答（RREP）包。為了減少路由發(fā)現(xiàn)過(guò)程的開(kāi)銷，每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)源路由緩沖，這樣可以減少RREQ包的發(fā)送。如果源路由中的某條鏈路中斷，源節(jié)點(diǎn)會(huì)收到RERR通知，此時(shí)，源節(jié)點(diǎn)可以重新發(fā)起路由發(fā)現(xiàn)過(guò)程。DSRDSR（D DYNAMICYNAMIC S SOURCEOURCE R ROUTINGOUTING）DSR 路由協(xié)議的優(yōu)點(diǎn)是中間節(jié)點(diǎn)不用維護(hù)去往全網(wǎng)所有節(jié)點(diǎn)的路由信息，而且可以避免出現(xiàn)路由環(huán)路。它的缺點(diǎn)是每個(gè)數(shù)據(jù)分組都攜帶了路徑信息，造成協(xié)議開(kāi)銷較大，而

9、且也不適合于網(wǎng)絡(luò)直徑大的無(wú)線自組網(wǎng),網(wǎng)絡(luò)可擴(kuò)展性不強(qiáng)。DSRDSR（D DYNAMICYNAMIC S SOURCEOURCE R ROUTINGOUTING）AODV 協(xié)議是在DSDV 協(xié)議基礎(chǔ)上結(jié)合類似DSR 中的按需路由機(jī)制進(jìn)行改進(jìn)后提出的，不同之處在于AODV采用了逐跳轉(zhuǎn)發(fā)分組方式，而DSR 是源路由方式。 在 AODV 路由協(xié)議中，源節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)廣播路由請(qǐng)求（RREQ），鄰居節(jié)點(diǎn)記錄一個(gè)反向路由，然后轉(zhuǎn)發(fā)這個(gè)請(qǐng)求，直到請(qǐng)求到達(dá)目標(biāo)節(jié)點(diǎn)或擁有到達(dá)目標(biāo)節(jié)點(diǎn)路由的某個(gè)中間節(jié)點(diǎn)。如果中間節(jié)點(diǎn)擁有到達(dá)目標(biāo)節(jié)點(diǎn)的路由，該節(jié)點(diǎn)將構(gòu)造一個(gè)路由應(yīng)答（RREP）包，選擇一個(gè)反向路由的最佳鏈路將其發(fā)送

10、；如果由于節(jié)點(diǎn)的移動(dòng)，路由上的某個(gè)鏈路失效，即某個(gè)中間節(jié)點(diǎn)不可達(dá)，此時(shí)該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)將檢測(cè)到這一情況，并且發(fā)送路由錯(cuò)誤（RERR）消息給它的上游節(jié)點(diǎn)，RERR 消息將最終到達(dá)源節(jié)點(diǎn)，源節(jié)點(diǎn)可以重新發(fā)起路由發(fā)現(xiàn)過(guò)程。AODVAODV（A AD D H HOCOC O ONN-D-DEMANDEMAND D DISTANCEISTANCE V VECTORECTOR）AODV 路由協(xié)議的顯著特點(diǎn)是加入了組播路由協(xié)議擴(kuò)展，支持QoS。它的缺點(diǎn)是不支持單向信道，因?yàn)锳ODV協(xié)議基于雙向信道的工作，路由回答分組直接沿著路由請(qǐng)求的反方向回到源節(jié)點(diǎn)。AODVAODV（A AD D H HOCOC O ON

11、N-D-DEMANDEMAND D DISTANCEISTANCE V VECTORECTOR） 層次路由協(xié)議通過(guò)組合使用按需獲取和預(yù)先獲取等路由策略，避免了主動(dòng)路由協(xié)議中過(guò)量的控制消息流量問(wèn)題和按需路由協(xié)議中的長(zhǎng)時(shí)延問(wèn)題，常見(jiàn)的層次路由協(xié)議包括：DDR, CBRP, CEDAR, GSR,FSR, HARP, ZRP, HSR, BRP,IARP, IERP, LANMAR 等，其中最具代表性的就是區(qū)域路由協(xié)議ZRP（Zone Routing Protocol）。AODVAODV（A AD D H HOCOC O ONN-D-DEMANDEMAND D DISTANCEISTANCE V V

12、ECTORECTOR） ZRP 是第一個(gè)利用層次結(jié)構(gòu)并混合使用按需路由策略和主動(dòng)路由策略的自組網(wǎng)路由協(xié)議。在ZRP 中，每個(gè)節(jié)點(diǎn)維護(hù)的區(qū)域大小由區(qū)域半徑指定，為了綜合利用按需路由和主動(dòng)路由的優(yōu)點(diǎn)，ZRP 協(xié)議規(guī)定每個(gè)節(jié)點(diǎn)采用DVA 主動(dòng)路由協(xié)議維護(hù)去往區(qū)域內(nèi)其他節(jié)點(diǎn)的路由，采用類似DSR 協(xié)議中的按需路由機(jī)制尋找去往區(qū)城外節(jié)點(diǎn)的路由。所以ZRP協(xié)議的性能很大程度上由區(qū)域半徑?jīng)Q定。通常小區(qū)域半徑適合于由移動(dòng)速度較快的節(jié)點(diǎn)組成的密集型網(wǎng)絡(luò)；大區(qū)域半徑適合于由移動(dòng)速度較慢的節(jié)點(diǎn)組成的稀疏網(wǎng)絡(luò)。當(dāng)前主要無(wú)線分組網(wǎng)路由協(xié)議分析分析對(duì)比分析對(duì)比 路由協(xié)議是實(shí)現(xiàn)無(wú)線自組網(wǎng)最關(guān)鍵的部分。為了適應(yīng)無(wú)線自組網(wǎng)帶寬

13、、能量有限等特性，認(rèn)為無(wú)線自組網(wǎng)的路由協(xié)議應(yīng)滿足以下幾點(diǎn)需求：分布式操作按需獲取路由預(yù)先獲取路由支持“靜默”支持單向鏈路安全性要好避免路由環(huán)無(wú)線自組網(wǎng)路由協(xié)議實(shí)現(xiàn)技術(shù)探討無(wú)線自組網(wǎng)的路由功能可以在 OSI 參考模型的第二層或者第三層實(shí)現(xiàn)。美軍JTRS 系統(tǒng)早期的無(wú)線自組網(wǎng)方案就是將節(jié)點(diǎn)移動(dòng)性隱藏于第二層的，這種方法的不足是當(dāng)網(wǎng)絡(luò)的規(guī)模很大時(shí)，必須在各個(gè)域之間有很多的橋接，導(dǎo)致過(guò)多的廣播流量，擁塞整個(gè)網(wǎng)絡(luò)。在第二層實(shí)現(xiàn)無(wú)線自組網(wǎng)路由的好處是可以利用某些鏈路層的信息和特征進(jìn)行路由優(yōu)化，但通過(guò)使用下面介紹的自適應(yīng)網(wǎng)絡(luò)協(xié)議棧結(jié)構(gòu)，這種優(yōu)化帶來(lái)的益處同樣可以在第三層中實(shí)現(xiàn)。無(wú)線自組網(wǎng)路由協(xié)議實(shí)現(xiàn)技術(shù)探討

14、在 第 三 層 實(shí) 現(xiàn) 無(wú) 線 自 組 網(wǎng) 路 由 的 例 子 有 美 軍MIL-STD-188-220C 標(biāo)準(zhǔn)和MANET 路由協(xié)議。第三層移動(dòng)路由的好處是“為使用混合物理層介質(zhì)節(jié)點(diǎn)組成的多跳網(wǎng)絡(luò)提供了網(wǎng)絡(luò)級(jí)的一致性”，使用無(wú)線技術(shù)A 和無(wú)線技術(shù)B 的裝備分別形成各自的無(wú)線自組網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)中存在同時(shí)具備A 和B 接口的裝備時(shí)，通過(guò)使用第三層路由，兩個(gè)無(wú)線自組網(wǎng)的節(jié)點(diǎn)之間可以透明地通信，實(shí)現(xiàn)不同技術(shù)體制裝備間的“動(dòng)中通”。無(wú)線自組網(wǎng)鏈路代價(jià)和路由判定的準(zhǔn)據(jù)(Metrics)，如帶寬、時(shí)延、應(yīng)用特性、物理位置和電池電量等，其信息的來(lái)源分布于網(wǎng)絡(luò)協(xié)議棧的各個(gè)層次。本堂內(nèi)容本堂內(nèi)容無(wú)線自組網(wǎng)無(wú)線自組

15、網(wǎng)無(wú)線傳感網(wǎng)無(wú)線傳感網(wǎng)概述概述無(wú)線傳感器網(wǎng)絡(luò)中路由協(xié)議的主要任務(wù)是建立從源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的路由，并可靠地傳輸數(shù)據(jù)。路由協(xié)議直接關(guān)系到無(wú)線傳感器網(wǎng)絡(luò)多跳自組織功能的實(shí)現(xiàn)。作為無(wú)線傳感器網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)闹笓]者，路由協(xié)議主要有以下兩個(gè)方面的功能：n建立源節(jié)點(diǎn)到目的節(jié)點(diǎn)的優(yōu)化路徑。n將數(shù)據(jù)沿著優(yōu)化路徑進(jìn)行傳輸。與有線網(wǎng)絡(luò)和蜂窩式無(wú)線網(wǎng)絡(luò)不同，WSN中沒(méi)有基礎(chǔ)設(shè)施和全網(wǎng)統(tǒng)一的控制中心。在這種無(wú)中心的環(huán)境下，路由可以看成分布式地獲取網(wǎng)絡(luò)拓?fù)湫畔?，以一定?zhǔn)則計(jì)算路徑并對(duì)路徑進(jìn)行維護(hù)的過(guò)程。概述概述n網(wǎng)絡(luò)特點(diǎn)是路由設(shè)計(jì)的主要依據(jù)，對(duì)網(wǎng)絡(luò)特點(diǎn)的分析是進(jìn)行協(xié)議設(shè)計(jì)的前提。n無(wú)線傳感網(wǎng)絡(luò)中，網(wǎng)絡(luò)業(yè)務(wù)的最大特點(diǎn)是具有

16、明顯的方向性。 為了實(shí)現(xiàn)信息采集的目的，WSN的網(wǎng)絡(luò)業(yè)務(wù)大都發(fā)生在數(shù)據(jù)匯聚節(jié)點(diǎn)（sink）和普通的傳感器節(jié)點(diǎn)之間，包括sink節(jié)點(diǎn)到傳感器節(jié)點(diǎn)的下行業(yè)務(wù)（如查詢指令下達(dá)）和傳感器節(jié)點(diǎn)到sink的上行業(yè)務(wù)（如采集信息的回傳）。 傳感器節(jié)點(diǎn)之間的橫向業(yè)務(wù)所占比例較小，主要是網(wǎng)絡(luò)的控制信息和網(wǎng)內(nèi)信息處理所需要的信息。n無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)基本理念是以大量低成本節(jié)點(diǎn)組網(wǎng)，通過(guò)節(jié)點(diǎn)之間的協(xié)作節(jié)點(diǎn)之間的協(xié)作獲得比單一的高精度、高可靠性和高成本的傳感器更好的信息采集效果。傳感器節(jié)點(diǎn)的能量約束和無(wú)線通傳感器節(jié)點(diǎn)的能量約束和無(wú)線通信鏈路的不可靠是無(wú)線傳感器網(wǎng)絡(luò)固有的，將對(duì)協(xié)議設(shè)計(jì)產(chǎn)生信鏈路的不可靠是無(wú)線傳感器網(wǎng)

17、絡(luò)固有的，將對(duì)協(xié)議設(shè)計(jì)產(chǎn)生較大影響較大影響。概述概述路由路由協(xié)議的分類協(xié)議的分類無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議有多種分類方法。根據(jù)網(wǎng)絡(luò)拓?fù)浣M織結(jié)構(gòu)，可分為平面型路由協(xié)議平面型路由協(xié)議和層次（分簇）型路由協(xié)議層次（分簇）型路由協(xié)議。n平坦型路由協(xié)議各個(gè)節(jié)點(diǎn)間的地位平等，節(jié)點(diǎn)通過(guò)局部信息來(lái)生成路由，其優(yōu)點(diǎn)是結(jié)構(gòu)簡(jiǎn)單，魯棒性較好，但對(duì)網(wǎng)絡(luò)動(dòng)態(tài)變化的反應(yīng)較慢，且有可能存在對(duì)資源盲目使用的情況。概述概述平面路由協(xié)議的典型代表有：定向擴(kuò)散路由(Directed Diffusion，DD)、謠傳路由(Rumor Routing)與閑聊路由(Gossiping)、GBR、HREEMR 協(xié)議和SPIN 協(xié)議等。概述概述

18、n層次（分簇）型路由網(wǎng)絡(luò)被劃分為若干個(gè)簇，每個(gè)簇由一個(gè)簇頭節(jié)點(diǎn)和若干個(gè)簇成員節(jié)點(diǎn)組成。簇頭節(jié)點(diǎn)負(fù)責(zé)簇內(nèi)成員節(jié)點(diǎn)數(shù)據(jù)信息的收集和融合處理，以及簇間數(shù)據(jù)的轉(zhuǎn)發(fā)。分簇協(xié)議中設(shè)計(jì)簇頭的選舉策略是一個(gè)重要議題。典型的分簇路由協(xié)議有：LEACH、PEGASIS、TEEN、APTEEN、HEED和CHEF等。平坦平坦型路由協(xié)議型路由協(xié)議洪洪泛泛(Flooding)(Flooding)協(xié)議和閑聊協(xié)議和閑聊(Gossiping)(Gossiping)協(xié)議協(xié)議洪泛協(xié)議：洪泛協(xié)議： 是一種傳統(tǒng)的路由協(xié)議，它不要求維護(hù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和計(jì)算路由。收到數(shù)據(jù)的節(jié)點(diǎn)以廣播形式向所有的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)收到數(shù)據(jù)的節(jié)點(diǎn)以廣播形式向所有

19、的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)，直到數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)或者達(dá)到預(yù)先設(shè)定的最大跳數(shù)為止。平坦平坦型路由協(xié)議型路由協(xié)議協(xié)議機(jī)制： 源節(jié)點(diǎn)S希望發(fā)送數(shù)據(jù)給目的節(jié)點(diǎn)D。S發(fā)起數(shù)據(jù)廣播，然后任意一個(gè)收到廣播的節(jié)點(diǎn)都無(wú)條件將該數(shù)據(jù)副本廣播出去，每一節(jié)點(diǎn)都重復(fù)這樣的過(guò)程直到數(shù)據(jù)遍歷全網(wǎng)或者達(dá)到規(guī)定的最大跳數(shù)。 洪泛法具有實(shí)現(xiàn)簡(jiǎn)單、路徑容錯(cuò)性好、時(shí)延短等優(yōu)點(diǎn)，但存在消息消息內(nèi)爆內(nèi)爆(Implosion) 、重疊重疊(Overlap)和盲目使用資源盲目使用資源的問(wèn)題，數(shù)據(jù)傳輸時(shí)能量消耗巨大、資源浪費(fèi)嚴(yán)重。一般用于軍事或與其它算法進(jìn)行性能上的比較。消息內(nèi)爆：節(jié)點(diǎn)幾乎同時(shí)從鄰居節(jié)點(diǎn)收到多份相同數(shù)據(jù)的現(xiàn)象。浪費(fèi)能量 重疊：節(jié)點(diǎn)先后收

20、到監(jiān)控同一區(qū)域的多個(gè)節(jié)點(diǎn)發(fā)送的幾乎相同的數(shù)據(jù)。浪費(fèi)能量 盲目使用資源：即不考慮各節(jié)點(diǎn)能量可用狀況，在任何情況下都轉(zhuǎn)發(fā)數(shù)據(jù)。平坦平坦型路由協(xié)議型路由協(xié)議 消息內(nèi)爆 重疊平坦平坦型路由協(xié)議型路由協(xié)議 閑聊協(xié)議（閑聊協(xié)議（ Gossiping Gossiping ）：）： 是對(duì)洪泛協(xié)議的改進(jìn)，為了節(jié)省能量，節(jié)點(diǎn)收到數(shù)據(jù)后隨機(jī)選取一個(gè)相鄰節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，而不采用廣播形式，避免了消息的內(nèi)爆，但隨機(jī)選取節(jié)點(diǎn)的機(jī)制導(dǎo)致了路徑質(zhì)量較差，增加了端到端的傳輸時(shí)延，并且無(wú)法解決消息重疊和盲目使用資源的問(wèn)題。優(yōu)點(diǎn)：降低了數(shù)據(jù)轉(zhuǎn)發(fā)重疊的可能性，避免了信息內(nèi)爆現(xiàn)象的產(chǎn)生。缺點(diǎn)：點(diǎn)到點(diǎn)的時(shí)延增大。由于隨機(jī)轉(zhuǎn)發(fā)某一個(gè)節(jié)點(diǎn)的方向

21、并不一定在距離目的節(jié)點(diǎn)更近的方向上，因此容易造成數(shù)據(jù)到達(dá)目的節(jié)點(diǎn)時(shí)間過(guò)長(zhǎng)或者跳數(shù)己達(dá)到最大，而數(shù)據(jù)還沒(méi)有到達(dá)目的節(jié)點(diǎn)，造成遞送失敗。 共同點(diǎn)：不需要維護(hù)路由信息，也不需要任何算法，簡(jiǎn)單但擴(kuò)展性差。4.2 4.2 平坦型路由協(xié)議平坦型路由協(xié)議SPINSPIN協(xié)議（協(xié)議（sensor protocol for information via sensor protocol for information via negotiationnegotiation）nSPIN協(xié)議是第一個(gè)以數(shù)據(jù)為中心的自適應(yīng)路由協(xié)議，通過(guò)協(xié)商機(jī)制協(xié)商機(jī)制來(lái)解決洪泛算法中的“內(nèi)爆”和“重疊”問(wèn)題，節(jié)省了能量的消耗。n節(jié)點(diǎn)在傳

22、輸數(shù)據(jù)之前先進(jìn)行協(xié)商，這種協(xié)商機(jī)制可確保數(shù)據(jù)傳輸?shù)挠行裕苊饬嗣つ總鞑ィń鉀Q信息“內(nèi)爆”和“重疊”問(wèn)題）。n節(jié)點(diǎn)間通過(guò)發(fā)送元數(shù)據(jù)元數(shù)據(jù)(即描述傳感器節(jié)點(diǎn)采集的數(shù)據(jù)屬性的數(shù)據(jù)，meta-data)，而不是采集的整個(gè)數(shù)據(jù)進(jìn)行協(xié)商。由于元數(shù)據(jù)小于采集的實(shí)際數(shù)據(jù)，所以，傳輸元數(shù)據(jù)消耗的能量相對(duì)較少。為避免盲目使用資源，所有傳感器節(jié)點(diǎn)必須監(jiān)控各自的能量變化情況，如果處于低能量水平，則中斷一些操作，例如數(shù)據(jù)轉(zhuǎn)發(fā)。 平坦平坦型路由協(xié)議型路由協(xié)議n協(xié)議提供了3種類型的消息：ADV、REQ和DATA。包含元數(shù)據(jù)的ADV消息用于通知鄰節(jié)點(diǎn)有數(shù)據(jù)要發(fā)送，REQ消息用于鄰節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)，DATA用于發(fā)送原始數(shù)據(jù)到鄰節(jié)

23、點(diǎn)。 ADV：用于數(shù)據(jù)的廣播，當(dāng)某一個(gè)節(jié)點(diǎn)有數(shù)據(jù)可以發(fā)送時(shí)，可以用ADV數(shù)據(jù)包通知其鄰居節(jié)點(diǎn)。 REQ：用于請(qǐng)求發(fā)送數(shù)據(jù)，當(dāng)某一個(gè)收到ADV的節(jié)點(diǎn)希望接收DATA數(shù)據(jù)包時(shí)，發(fā)送REQ數(shù)據(jù)包。 DATA：為原始感知數(shù)據(jù)包，里面裝載了原始感知數(shù)據(jù)。n工作機(jī)制：如下圖所示，當(dāng)傳感器節(jié)點(diǎn)有數(shù)據(jù)要發(fā)送時(shí)，先廣播ADV消息（使用元數(shù)據(jù)），鄰近節(jié)點(diǎn)收到ADV消息后，如果愿意接收該數(shù)據(jù)，就向發(fā)送節(jié)點(diǎn)發(fā)出REQ請(qǐng)求消息，最后發(fā)送節(jié)點(diǎn)向請(qǐng)求的鄰居節(jié)點(diǎn)發(fā)送DATA數(shù)據(jù)包。平坦平坦型路由協(xié)議型路由協(xié)議SPINSPIN工作過(guò)程工作過(guò)程平坦平坦型路由協(xié)議型路由協(xié)議SPIN協(xié)議簇有4種不同的形式：SPIN-BC：適合于廣播

24、信道的SPIN協(xié)議SPIN-PP：適合于點(diǎn)對(duì)點(diǎn)信道的SPIN協(xié)議SPIN-EC：在SPIN-PP基礎(chǔ)上增加了能量限制SPIN-RL：考慮信道上存在分組丟失的SPIN協(xié)議SPIN協(xié)議的優(yōu)點(diǎn)：簡(jiǎn)單，不需要進(jìn)行路由維護(hù)；通過(guò)數(shù)據(jù)協(xié)商機(jī)制保證了只向需要的節(jié)點(diǎn)發(fā)送數(shù)據(jù)，提高了轉(zhuǎn)發(fā)效率。小ADV消息解決了內(nèi)爆問(wèn)題；通過(guò)數(shù)據(jù)命名減輕了重疊問(wèn)題；節(jié)點(diǎn)根據(jù)自身資源和應(yīng)用信息決定是否進(jìn)行ADV通告，避免了資源利用盲目問(wèn)題?？捎糜谝苿?dòng)WSN。SPIN協(xié)議的缺點(diǎn)：ADV消息采用廣播方式傳輸，開(kāi)銷比較大；每次發(fā)送數(shù)據(jù)包之前都要進(jìn)行協(xié)商，數(shù)據(jù)傳輸延遲較大。當(dāng)產(chǎn)生或收到數(shù)據(jù)的節(jié)點(diǎn)的所有鄰節(jié)點(diǎn)都不需要該數(shù)據(jù)時(shí)，將導(dǎo)致數(shù)據(jù)不能

25、繼續(xù)轉(zhuǎn)發(fā)，以致較遠(yuǎn)節(jié)點(diǎn)無(wú)法得到數(shù)據(jù)。平坦平坦型路由協(xié)議型路由協(xié)議基本基本概念概念 DD是無(wú)線傳感器網(wǎng)絡(luò)中以數(shù)據(jù)為中心（基于信息查詢）的里程碑式平面路由協(xié)議，得到了廣泛的應(yīng)用和研究。sink節(jié)點(diǎn)首先采用泛洪(flooding)方式向全網(wǎng)廣播Interest Interest (sink感興趣的數(shù)據(jù))；其次建立相鄰節(jié)點(diǎn)間的梯度梯度(反映沿該方向獲得匹配數(shù)據(jù)的性能的矢量值)；具有匹配Interest數(shù)據(jù)的節(jié)點(diǎn)接收到Interest后，依據(jù)梯度選擇路徑并將數(shù)據(jù)送回sink。因此，DD協(xié)議包含興趣（interest）擴(kuò)散、梯度（gradient）建立、數(shù)據(jù)（data message）傳播（探測(cè)）以及路徑

26、加固（routing reinforcement）4個(gè)主要?jiǎng)討B(tài)過(guò)程。興趣、數(shù)據(jù)、梯度興趣、數(shù)據(jù)、梯度三個(gè)基本概念要透徹理解。節(jié)點(diǎn)收到一個(gè)興趣消息后該如何處理？節(jié)點(diǎn)收到一個(gè)數(shù)據(jù)消息后該如何處理？梯度如何建立？路徑如何加強(qiáng)？平坦平坦型路由協(xié)議型路由協(xié)議（1 1）命名機(jī)制）命名機(jī)制（如何描述興趣？如何描述數(shù)據(jù)？）無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)沒(méi)有全局惟一的編號(hào)標(biāo)識(shí)，每個(gè)傳感器節(jié)點(diǎn)都只是每個(gè)傳感器節(jié)點(diǎn)都只是知道鄰近節(jié)點(diǎn)的情況知道鄰近節(jié)點(diǎn)的情況，而不知道全局所有傳感器節(jié)點(diǎn)信息，所以為了保證源節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)能夠傳輸?shù)奖O(jiān)測(cè)者所在的任務(wù)管理節(jié)點(diǎn)，就需要把興趣和采集的數(shù)據(jù)以一種方式對(duì)應(yīng)起來(lái)。定向擴(kuò)散協(xié)議是一種以數(shù)據(jù)為中

27、心的路由協(xié)議，所有的任務(wù)數(shù)據(jù)都是經(jīng)過(guò)數(shù)據(jù)命名的，而這種命名方式就是通過(guò)命名機(jī)制完成的。這種命名機(jī)制就是一種簡(jiǎn)單的屬性和值的配對(duì)（屬性和值的配對(duì)（ Attribute-Value pairs ）的列表，這樣就可以對(duì)興趣消息進(jìn)行匹配。例如，對(duì)車輛的跟蹤任務(wù)可能被描述為以下興趣：type=wheeled vehicle /興趣類型興趣類型interval=20ms /事件的傳輸時(shí)間間隔事件的傳輸時(shí)間間隔duration=10s /興趣的生存時(shí)間興趣的生存時(shí)間rect=-100, 100, 200, 400 /興趣的傳感區(qū)域興趣的傳感區(qū)域平坦平坦型路由協(xié)議型路由協(xié)議對(duì)興趣的響應(yīng)也使用了類似的名字命名方

28、案。所以，一個(gè)傳感器節(jié)點(diǎn)檢測(cè)到輪式車輛后可能會(huì)以產(chǎn)生下面的數(shù)據(jù)回答：type=wheeled vehicle /類型類型instance=truck /類型的實(shí)例類型的實(shí)例location=127, 200 /節(jié)點(diǎn)位置節(jié)點(diǎn)位置intensity=0.7 /信號(hào)強(qiáng)度信號(hào)強(qiáng)度confidence=0.80 /匹配的確信度匹配的確信度timestamp=00:24:40 /信號(hào)采集時(shí)間信號(hào)采集時(shí)間在無(wú)線傳感器網(wǎng)絡(luò)中，針對(duì)定向擴(kuò)散協(xié)議的第一步是設(shè)計(jì)一個(gè)命名方案（這個(gè)命名方案并不固定）。通常而言，一個(gè)興趣的屬性組合描述要包括：監(jiān)測(cè)對(duì)象，監(jiān)測(cè)區(qū)域，起始時(shí)間，有效時(shí)間，發(fā)送速率等，不同的任務(wù)可以增加各自的特

29、殊的屬性項(xiàng)。平坦平坦型路由協(xié)議型路由協(xié)議（2 2）興趣和梯度）興趣和梯度興趣用來(lái)表示查詢的任務(wù)，例如監(jiān)測(cè)區(qū)域內(nèi)的溫度、動(dòng)物的運(yùn)動(dòng)軌跡等信息。一個(gè)查詢?nèi)蝿?wù)作為一個(gè)興趣通過(guò)無(wú)線傳感器網(wǎng)絡(luò)傳播，通過(guò)匯聚節(jié)點(diǎn)廣播興趣消息。梯度是一個(gè)寬泛的概念。一般梯度定義應(yīng)包括一個(gè)數(shù)據(jù)的傳輸方向和傳輸速率。在不同的設(shè)計(jì)中，設(shè)計(jì)者可以根據(jù)所關(guān)注的網(wǎng)絡(luò)性能不同，采用不同的梯度策略，例如，梯度列表項(xiàng)可包括如下幾個(gè)字段：上一跳節(jié)點(diǎn)ID（方向，記錄著興趣地直接來(lái)源）；事件傳輸速率（值，記錄興趣中要求的事件傳輸間隔）；生存期（記錄興趣的生存期）。 總的來(lái)說(shuō)，梯度就是一個(gè)值和一個(gè)方向，方向指明事件可能會(huì)傳向的鄰居，而值表明節(jié)點(diǎn)以何

30、種傳輸速率將事件傳給方向指向的鄰居。 每個(gè)節(jié)點(diǎn)都維持一個(gè)興趣列表，該興趣列表中可有多個(gè)興趣，每個(gè)興趣可能對(duì)應(yīng)多個(gè)梯度，如圖所示。平坦平坦型路由協(xié)議型路由協(xié)議定向擴(kuò)散的路由機(jī)制定向擴(kuò)散的路由機(jī)制定向擴(kuò)散的路由機(jī)制可以分為周期性的興趣擴(kuò)散興趣擴(kuò)散、梯度的建立梯度的建立、數(shù)據(jù)探測(cè)數(shù)據(jù)探測(cè)和路徑的加強(qiáng)路徑的加強(qiáng)四個(gè)階段，如圖所示。平坦平坦型路由協(xié)議型路由協(xié)議（1）興趣擴(kuò)散將任務(wù)通過(guò)命名機(jī)制構(gòu)建成一個(gè)興趣。例如：type=wheeled vehicle /興趣類型興趣類型interval=1s /事件的傳輸時(shí)間間隔事件的傳輸時(shí)間間隔duration=60s /興趣的生存時(shí)間興趣的生存時(shí)間rect=-10

31、0, 100, 200, 400 /興趣的傳感區(qū)域興趣的傳感區(qū)域timestamp=01: 01: 22 /初始化時(shí)間初始化時(shí)間expiresAt=01: 02: 22 /終止時(shí)間終止時(shí)間平坦平坦型路由協(xié)議型路由協(xié)議對(duì)于每個(gè)任務(wù)，為了動(dòng)態(tài)適應(yīng)節(jié)點(diǎn)失效、拓?fù)渥兓惹闆r，匯聚節(jié)點(diǎn)周期性周期性的向網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)廣播興趣消息。在網(wǎng)絡(luò)的初始階段，由于處于探索的階段，興趣在網(wǎng)內(nèi)擴(kuò)散的目的僅僅是嘗試探測(cè)是否有事件源的存在，因此興趣內(nèi)所包含的匹配事件的傳輸間隔（interval）比較長(zhǎng)，這樣可以避免過(guò)多的通信量。每個(gè)節(jié)點(diǎn)在本地都有一個(gè)興趣列表。對(duì)于每一個(gè)興趣，列表中都有一個(gè)梯度表項(xiàng)記錄發(fā)來(lái)該興趣消息的來(lái)源（鄰

32、居節(jié)點(diǎn)）、數(shù)據(jù)發(fā)送速率和時(shí)間戳等任務(wù)相關(guān)信息，以建立該節(jié)點(diǎn)向匯聚節(jié)點(diǎn)傳遞數(shù)據(jù)的梯度關(guān)系。每個(gè)表項(xiàng)還有一個(gè)字段用來(lái)表示該表項(xiàng)的有效時(shí)間值，超過(guò)這個(gè)時(shí)間后，節(jié)點(diǎn)將刪除這個(gè)表項(xiàng)。每個(gè)興趣可能對(duì)應(yīng)多個(gè)鄰居節(jié)點(diǎn)，而每個(gè)鄰居節(jié)點(diǎn)則只對(duì)應(yīng)一個(gè)梯度信息。當(dāng)一個(gè)節(jié)點(diǎn)接收到一個(gè)興趣消息時(shí)，節(jié)點(diǎn)要對(duì)該興趣消息進(jìn)行記錄和轉(zhuǎn)發(fā)，按以下流程處理：平坦平坦型路由協(xié)議型路由協(xié)議注意：注意：1.1.節(jié)點(diǎn)節(jié)點(diǎn)B B應(yīng)該能夠判斷是否要將該興趣轉(zhuǎn)發(fā)，應(yīng)該能夠判斷是否要將該興趣轉(zhuǎn)發(fā)，如果發(fā)現(xiàn)已對(duì)該興趣進(jìn)行了廣播，就不如果發(fā)現(xiàn)已對(duì)該興趣進(jìn)行了廣播，就不再轉(zhuǎn)發(fā)了。再轉(zhuǎn)發(fā)了。2.2.對(duì)于對(duì)于B B節(jié)點(diǎn)來(lái)說(shuō)，這個(gè)興趣僅僅來(lái)自節(jié)點(diǎn)來(lái)說(shuō)，這個(gè)興趣

33、僅僅來(lái)自A A節(jié)節(jié)點(diǎn)，而不管它來(lái)自哪個(gè)點(diǎn)，而不管它來(lái)自哪個(gè)SinkSink節(jié)點(diǎn)，興趣節(jié)點(diǎn)，興趣表中也不包含表中也不包含SinkSink節(jié)點(diǎn)的信息。即只需節(jié)點(diǎn)的信息。即只需記錄局部信息，而不是全部。記錄局部信息，而不是全部。AB平坦平坦型路由協(xié)議型路由協(xié)議（2）梯度建立定向擴(kuò)散中，梯度的概念非常重要。梯度是在興趣的發(fā)送過(guò)程中形成的，通過(guò)梯度，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)就通過(guò)梯度作為路徑聯(lián)系起來(lái)了。梯度包括鄰居節(jié)點(diǎn)鄰居節(jié)點(diǎn)、數(shù)據(jù)傳送率數(shù)據(jù)傳送率、有效期有效期等信息。當(dāng)節(jié)點(diǎn)B從它的鄰節(jié)點(diǎn)A收到某個(gè)興趣后，它判斷將要轉(zhuǎn)發(fā)該興趣，于是廣播出去。這時(shí)A又會(huì)收到剛轉(zhuǎn)發(fā)的該興趣，這樣在A和B之間就建立了雙向梯度。這樣的

34、一個(gè)雙向梯度可以保證網(wǎng)絡(luò)中的節(jié)點(diǎn)能夠被“興趣”覆蓋到。AB平坦平坦型路由協(xié)議型路由協(xié)議（3）數(shù)據(jù)探測(cè)（傳播）當(dāng)傳感器節(jié)點(diǎn)采集到與興趣匹配匹配的數(shù)據(jù)時(shí)，就把數(shù)據(jù)發(fā)送到梯度上的鄰居節(jié)點(diǎn)（組播或廣播），并且按照梯度上的數(shù)據(jù)傳輸速率（例如每秒傳送一條數(shù)據(jù)）設(shè)定無(wú)線傳感器模塊采集數(shù)據(jù)的速率。由于可能從多個(gè)鄰居節(jié)點(diǎn)收到興趣消息，節(jié)點(diǎn)向多個(gè)鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)，匯聚節(jié)點(diǎn)可能收到經(jīng)過(guò)多個(gè)路徑的相同數(shù)據(jù)。數(shù)據(jù)發(fā)送的形式如下：type=wheeled vehicle /類型類型instance=truck /類型的實(shí)例類型的實(shí)例location=127, 200 /節(jié)點(diǎn)位置節(jié)點(diǎn)位置intensity=0.7 /信號(hào)強(qiáng)

35、度信號(hào)強(qiáng)度confidence=0.80 /匹配的確信度匹配的確信度timestamp=01:02:01 /信號(hào)采集時(shí)間信號(hào)采集時(shí)間平坦平坦型路由協(xié)議型路由協(xié)議 中間節(jié)點(diǎn)接收數(shù)據(jù)的處理流程如下：AB平坦平坦型路由協(xié)議型路由協(xié)議簡(jiǎn)單地說(shuō)，傳感器節(jié)點(diǎn)（源節(jié)點(diǎn)）收集到數(shù)據(jù)，與緩存中的興趣記錄進(jìn)行匹配，如果匹配程度達(dá)到要求，就認(rèn)為該數(shù)據(jù)是Sink節(jié)點(diǎn)需要的。然后，它把數(shù)據(jù)包往相鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)（廣播）。而相鄰（中轉(zhuǎn)）節(jié)點(diǎn)接受到新的數(shù)據(jù)包時(shí)，也會(huì)在它的緩存中尋找是否有匹配的興趣項(xiàng)，如果沒(méi)有，則認(rèn)為該數(shù)據(jù)包無(wú)效，以丟棄的方式進(jìn)行處理；要是有匹配的興趣項(xiàng)，則看是否在過(guò)去曾接收轉(zhuǎn)發(fā)過(guò)同一數(shù)據(jù)，如果是，則也作丟棄的方

36、式處理，如果不是，則記錄相關(guān)信息，再次轉(zhuǎn)發(fā)給自己的鄰居節(jié)點(diǎn)。如此，數(shù)據(jù)包就可以由源節(jié)點(diǎn)逐步擴(kuò)散傳輸?shù)綌?shù)據(jù)接收發(fā)送器。平坦平坦型路由協(xié)議型路由協(xié)議（4）路徑的建立和加強(qiáng)在上述描述的過(guò)程中，sink節(jié)點(diǎn)開(kāi)始時(shí)不斷的將一個(gè)興趣注入到網(wǎng)絡(luò)中進(jìn)行傳播，興趣傳播時(shí)速率較低。興趣的傳播過(guò)程是為了尋找到合適的區(qū)域節(jié)點(diǎn)興趣的傳播過(guò)程是為了尋找到合適的區(qū)域節(jié)點(diǎn)的通路的通路。興趣在傳播的過(guò)程中建立了許多梯度（稱之為探測(cè)梯度探測(cè)梯度），這些梯度連通起來(lái)構(gòu)成了sink節(jié)點(diǎn)和源節(jié)點(diǎn)之間的許多條數(shù)據(jù)通路。當(dāng)源節(jié)點(diǎn)發(fā)現(xiàn)了匹配的目標(biāo)后，它會(huì)發(fā)送試探性的探測(cè)數(shù)據(jù)探測(cè)數(shù)據(jù)，這些數(shù)據(jù)沿著上述的若干條通道返回給sink節(jié)點(diǎn)，發(fā)送的數(shù)據(jù)

37、傳輸速率較低，因?yàn)檫@時(shí)初始化興趣的間隔值較高。在探測(cè)數(shù)據(jù)到達(dá)sink后，sinksink會(huì)根據(jù)從不同的數(shù)據(jù)通路接收數(shù)據(jù)會(huì)根據(jù)從不同的數(shù)據(jù)通路接收數(shù)據(jù)的效果，選出一條或幾條的效果，選出一條或幾條“高效高效”的通路的通路，以后就在這些高效通路上傳送的數(shù)據(jù)。為了加強(qiáng)鄰居，sink重新發(fā)送興趣（點(diǎn)對(duì)點(diǎn)），但是發(fā)送興趣時(shí)用較高的數(shù)據(jù)傳輸速率。type=wheeled vehicle /興趣類型興趣類型interval=10ms /事件的傳輸時(shí)間間隔事件的傳輸時(shí)間間隔duration=60s /興趣的生存時(shí)間興趣的生存時(shí)間rect=-100, 100, 200, 400 /興趣的傳感區(qū)域興趣的傳感區(qū)域ti

38、mestamp=01: 01: 22 /初始化時(shí)間初始化時(shí)間expiresAt=01: 02: 22 /終止時(shí)間終止時(shí)間平坦平坦型路由協(xié)議型路由協(xié)議假設(shè)以數(shù)據(jù)傳輸延遲作為路由加強(qiáng)的標(biāo)準(zhǔn)以數(shù)據(jù)傳輸延遲作為路由加強(qiáng)的標(biāo)準(zhǔn)，匯節(jié)點(diǎn)選擇首先發(fā)來(lái)最新數(shù)據(jù)的鄰居節(jié)點(diǎn)作為加強(qiáng)路徑的下一跳節(jié)點(diǎn)，向該鄰居節(jié)點(diǎn)發(fā)送路徑加強(qiáng)消息。路徑加強(qiáng)消息中包含新設(shè)定的較高發(fā)送數(shù)據(jù)速率值。鄰居節(jié)點(diǎn)收到消息后，經(jīng)過(guò)分析確定該消息描述的是一個(gè)己有的興趣，只是增加了數(shù)據(jù)發(fā)送速率，那么該節(jié)點(diǎn)按照同樣的規(guī)則選擇加強(qiáng)路徑的下一跳鄰居節(jié)點(diǎn)。路徑加強(qiáng)的標(biāo)準(zhǔn)不是唯一的路徑加強(qiáng)的標(biāo)準(zhǔn)不是唯一的，例如可以選擇在一定時(shí)間內(nèi)發(fā)送數(shù)據(jù)最多的節(jié)點(diǎn)作為路徑加強(qiáng)

39、的下一跳節(jié)點(diǎn)，也可以選擇數(shù)據(jù)傳輸最穩(wěn)定的節(jié)點(diǎn)那作為路徑加強(qiáng)的下一條節(jié)點(diǎn)。在加強(qiáng)路徑上的節(jié)點(diǎn)如果發(fā)現(xiàn)下一跳節(jié)點(diǎn)的發(fā)送數(shù)據(jù)速率明顯減少，或者收到來(lái)自其他節(jié)點(diǎn)的新位置估計(jì)，推斷加強(qiáng)路徑的下一跳節(jié)點(diǎn)失效，就需要使用上述的路徑加強(qiáng)機(jī)制重新確定下一跳節(jié)點(diǎn)。平坦平坦型路由協(xié)議型路由協(xié)議基于定向擴(kuò)散路由的設(shè)計(jì)選擇基于定向擴(kuò)散路由的設(shè)計(jì)選擇前面介紹了定向擴(kuò)散協(xié)議的路由機(jī)制，對(duì)于不同的應(yīng)用需求或者不同的網(wǎng)絡(luò)狀況，可以對(duì)定向擴(kuò)散協(xié)議的路由機(jī)制的各個(gè)過(guò)程進(jìn)行不同的路由選擇。平坦平坦型路由協(xié)議型路由協(xié)議定向擴(kuò)散路由協(xié)議特點(diǎn)定向擴(kuò)散路由協(xié)議特點(diǎn)定向擴(kuò)散的本質(zhì)是一種框架性的協(xié)議，通過(guò)對(duì)梯度及路徑加固策略的改變可得到不同的具

40、體協(xié)議，例如：GBR路由(Gradient-Based Routing)協(xié)議， EAR(Energy Aware Routing)路由協(xié)議，CADR路由(Constrained Anisotropic Diffusion routing)協(xié)議等。以數(shù)據(jù)為中心的路由算法，使得無(wú)線傳感器網(wǎng)絡(luò)的通信不再依賴特定的節(jié)點(diǎn)，而依賴于網(wǎng)絡(luò)中的數(shù)據(jù)。采用多路徑，健壯性好；使用數(shù)據(jù)融合能減少數(shù)據(jù)通信量；節(jié)點(diǎn)遵循本地交互的原則。節(jié)點(diǎn)只需要知道局部(鄰居)節(jié)點(diǎn)的情況，無(wú)需了解整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，也不需要特定的節(jié)點(diǎn)來(lái)計(jì)算路由。可以說(shuō)，定向擴(kuò)散的尋路是自適應(yīng)的；興趣傳播及Gradient的建立開(kāi)銷很大；對(duì)于大規(guī)模網(wǎng)絡(luò)，

41、會(huì)帶來(lái)較大開(kāi)銷和時(shí)延。資源盲目使用導(dǎo)致能耗不均勻，可能導(dǎo)致某些節(jié)點(diǎn)的過(guò)早死亡。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議分分簇路由協(xié)議概述簇路由協(xié)議概述前面所講的平面型路由協(xié)議具有以下特點(diǎn)：所有節(jié)點(diǎn)功能一致、地位平等，不存在瓶頸節(jié)點(diǎn)，網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)單、健壯性好。但平面結(jié)構(gòu)中所有節(jié)點(diǎn)都需要生成到達(dá)匯聚節(jié)點(diǎn)的路由，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，會(huì)帶來(lái)大量的控制開(kāi)銷，因此，可擴(kuò)展性差，對(duì)網(wǎng)絡(luò)動(dòng)態(tài)變化的反應(yīng)慢。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議在分簇路由協(xié)議中，網(wǎng)絡(luò)通常被劃分為簇(cluster)。所謂簇，就是具有某種關(guān)聯(lián)的網(wǎng)絡(luò)節(jié)點(diǎn)集合。每個(gè)簇由一個(gè)簇頭(cluster head)和多個(gè)簇內(nèi)成員(clu

42、ster member)組成，低一級(jí)網(wǎng)絡(luò)的簇頭是高一級(jí)網(wǎng)絡(luò)中的簇內(nèi)成員，由最高層的簇頭與基站BS(base station)通信。如下圖所示：層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議分簇路由協(xié)議具有以下特點(diǎn)：1)由簇首對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行集中管理，能夠動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，可擴(kuò)展性好，非常適合于規(guī)模比較大的網(wǎng)絡(luò)系統(tǒng)。2)由簇首構(gòu)成一個(gè)骨干網(wǎng)完成遠(yuǎn)距離的數(shù)據(jù)轉(zhuǎn)發(fā)，簇成員可以按TDMA時(shí)隙輪流采集數(shù)據(jù)，在空閑時(shí)可以關(guān)閉通信模塊，節(jié)省了能量。3)簇成員僅需要將數(shù)據(jù)傳輸?shù)酱厥?，縮短了傳輸距離；簇首可以對(duì)簇內(nèi)數(shù)據(jù)進(jìn)行必要的融合后再轉(zhuǎn)發(fā)，減少了網(wǎng)絡(luò)的通信量。4)分簇路由只由簇首參與路徑計(jì)算，極大地減少

43、了路由節(jié)點(diǎn)的數(shù)目，降低了路由開(kāi)銷。5)分簇算法復(fù)雜，簇首選舉過(guò)程中節(jié)點(diǎn)間需要交換大量的控制消息，帶來(lái)一定的開(kāi)銷。6)簇首是網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，一旦簇首出現(xiàn)故障，容易造成較大面積的網(wǎng)絡(luò)癱瘓。7)簇首的能耗遠(yuǎn)大于其它成員節(jié)點(diǎn)，如果沒(méi)有較好的能量平衡措施，容易造成簇首節(jié)點(diǎn)過(guò)早耗盡能量而死亡。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議分分簇算法的評(píng)價(jià)標(biāo)準(zhǔn)簇算法的評(píng)價(jià)標(biāo)準(zhǔn)(1)簇首數(shù)量合適簇首數(shù)量決定了分簇網(wǎng)絡(luò)系統(tǒng)的結(jié)構(gòu)和特性，不宜太多或太少，應(yīng)根據(jù)應(yīng)用要求以盡量減少控制開(kāi)銷和降低能耗為原則來(lái)確定。另外，在每輪分簇過(guò)程中，簇首數(shù)量應(yīng)該相對(duì)穩(wěn)定，以保證應(yīng)用系統(tǒng)的數(shù)據(jù)采集精度。(2)簇首位置分布均勻簇首是網(wǎng)

44、絡(luò)的關(guān)鍵節(jié)點(diǎn)，要負(fù)責(zé)簇內(nèi)數(shù)據(jù)的融合處理和成員節(jié)點(diǎn)的協(xié)調(diào)，實(shí)現(xiàn)簇間數(shù)據(jù)轉(zhuǎn)發(fā)。因此，簇首應(yīng)均勻分布在整個(gè)監(jiān)控區(qū)域。簇首的分布情況可以用簇間重疊度來(lái)評(píng)價(jià)，其計(jì)算方法如下公式所示：其中，n為簇首數(shù)，xi為第i個(gè)簇內(nèi)的節(jié)點(diǎn)數(shù)（總數(shù)），N為節(jié)點(diǎn)總數(shù)。K為簇間重疊度，其值大于或等于1，其值越小，則簇首分布越均勻。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議(3)簇首負(fù)載均衡簇首負(fù)載分為簇內(nèi)負(fù)載和簇間轉(zhuǎn)發(fā)負(fù)載兩部分，簇間轉(zhuǎn)發(fā)負(fù)載與節(jié)點(diǎn)的位置有關(guān)，而簇內(nèi)負(fù)載與簇內(nèi)節(jié)點(diǎn)的數(shù)量有關(guān)。要實(shí)現(xiàn)簇內(nèi)負(fù)載均衡要求各個(gè)簇具有相近的節(jié)點(diǎn)數(shù)，其負(fù)載均衡程度的計(jì)算方法如公式所示：其中，n為簇首的個(gè)數(shù)，xi為第i個(gè)簇的成員節(jié)點(diǎn)數(shù)，B

45、為負(fù)載均衡程度，其值越小，負(fù)載均衡程度越好。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議(4)節(jié)點(diǎn)能量平衡節(jié)約能量是無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)的首要目標(biāo)，簇結(jié)構(gòu)的生成和維護(hù)必須具有較小的通信開(kāi)銷，盡量減少節(jié)點(diǎn)的能量消耗。另外，保持節(jié)點(diǎn)間的能量平衡也是設(shè)計(jì)路由協(xié)議時(shí)需要考慮的關(guān)鍵因素，它直接影響網(wǎng)絡(luò)的有效工作時(shí)間。節(jié)點(diǎn)能量平衡程度的計(jì)算方法如公式所示：其中，N為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)，Ei為第i個(gè)節(jié)點(diǎn)的剩余能量，EB表示能量平衡程度，其值越小，意味著網(wǎng)絡(luò)的能量消耗越能均勻地分配到各個(gè)傳感器節(jié)點(diǎn)上。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議分分簇算法的分類簇算法的分類（1）按組織方式分：固定分簇和動(dòng)態(tài)分簇

46、固定分簇：預(yù)先分配好節(jié)點(diǎn)是簇首或是簇成員，并且其身份始終保持不變，適合于異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)。動(dòng)態(tài)分簇：簇首通過(guò)分簇算法選舉產(chǎn)生，簇首和簇成員的身份動(dòng)態(tài)變化，適合于同構(gòu)無(wú)線傳感器網(wǎng)絡(luò)。（2）按簇內(nèi)跳數(shù)分：?jiǎn)翁执睾投嗵执貑翁执兀捍爻蓡T采用一跳傳輸將數(shù)據(jù)發(fā)送到簇首。結(jié)構(gòu)簡(jiǎn)單，但簇首數(shù)量較多，簇內(nèi)傳輸距離較遠(yuǎn)，能量消耗較大。多跳分簇：簇成員采用多跳傳輸將數(shù)據(jù)發(fā)送到簇首。簇首數(shù)量少，簇覆蓋范圍大，節(jié)點(diǎn)發(fā)送距離短，但簇生成算法復(fù)雜。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議（3）按分簇時(shí)機(jī)分：主動(dòng)分簇和被動(dòng)分簇主動(dòng)分簇：分簇算法中每隔固定的時(shí)間間隔對(duì)簇首進(jìn)行輪換，有利于保持節(jié)點(diǎn)間的能量平衡，避免簇

47、首消耗過(guò)多的能量。被動(dòng)分簇：簇結(jié)構(gòu)相對(duì)穩(wěn)定，在異常情況（如簇首死亡或簇首能量小于額定值）發(fā)生時(shí)才重新分簇。開(kāi)銷較小，但簇結(jié)構(gòu)變化慢，容易導(dǎo)致部分節(jié)點(diǎn)能量消耗過(guò)度。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議LEACHLEACH協(xié)議協(xié)議1. 1. 協(xié)議簡(jiǎn)介協(xié)議簡(jiǎn)介L(zhǎng)EACH（Low Energy Adaptive Clustering Hierarchy）是由MIT的Heinzelman W等人在2000年提出的第一個(gè)基于數(shù)據(jù)聚合的自適應(yīng)分簇路由協(xié)議?；舅枷耄簩⑺泄?jié)點(diǎn)分成若干個(gè)簇，每個(gè)簇選取一個(gè)簇頭，其余的節(jié)點(diǎn)為簇內(nèi)成員。簇內(nèi)成員發(fā)送數(shù)據(jù)給簇頭，簇頭需要把數(shù)據(jù)進(jìn)行融合后再發(fā)送給匯聚節(jié)點(diǎn)。通過(guò)

48、等概率地隨機(jī)循環(huán)選擇簇頭，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)，從而達(dá)到降低網(wǎng)絡(luò)能量耗費(fèi)、延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。協(xié)議特征：采用自適應(yīng)成簇技術(shù)和簇首節(jié)點(diǎn)輪換技術(shù)。簇首動(dòng)態(tài)選舉、簇結(jié)構(gòu)由本地協(xié)調(diào)產(chǎn)生、簇內(nèi)實(shí)現(xiàn)數(shù)據(jù)融合等。LEACH的執(zhí)行過(guò)程是周期性的。LEACH將一個(gè)工作周期稱為一“輪”（round），每輪分為簇形成階段和數(shù)據(jù)傳輸階段兩部分。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議2. 2. 網(wǎng)絡(luò)模型和拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)模型和拓?fù)浣Y(jié)構(gòu)LEACH協(xié)議的網(wǎng)絡(luò)模型為：(1)網(wǎng)絡(luò)中有固定基站(Sink節(jié)點(diǎn))且遠(yuǎn)離傳感器節(jié)點(diǎn)，研究中不考慮基站的能量消耗，假定其具有充足的能量供應(yīng)；(2)網(wǎng)絡(luò)中所有節(jié)點(diǎn)

49、同構(gòu)且具有有限的能源；(3)網(wǎng)絡(luò)中所有節(jié)點(diǎn)具有相同的起始能量；(4)節(jié)點(diǎn)是靜止的；(5)節(jié)點(diǎn)總是有數(shù)據(jù)要發(fā)送；(6)節(jié)點(diǎn)可感知它的剩余能量，并能改變發(fā)射功率。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議3. 3. 工作原理及過(guò)程工作原理及過(guò)程LEACH中的操作是按“輪”(round)進(jìn)行的。每一輪包含簇的建立階段簇的建立階段和穩(wěn)定的數(shù)據(jù)傳輸階段數(shù)據(jù)傳輸階段。簇的建立階段主要形成簇，穩(wěn)定的數(shù)據(jù)傳輸階段是進(jìn)行數(shù)據(jù)傳輸。為了使能量消耗最小，通常第二個(gè)階段持續(xù)時(shí)間要比第一個(gè)階段的時(shí)間長(zhǎng)。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議（1）簇建立階段簇首選舉在每

50、一輪的開(kāi)始，節(jié)點(diǎn)隨機(jī)產(chǎn)生一個(gè)0，1之間的隨機(jī)數(shù)，然后與系統(tǒng)閾值T(n)相比，決定自己能否成為簇首。若當(dāng)前輪中這個(gè)值小于設(shè)定的閾值T(n)，則該節(jié)點(diǎn)稱為簇首， T(n) 按下式計(jì)算：其中，P 是期望的期望的簇頭節(jié)點(diǎn)與網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的比例（例如 p=0.05），r 是當(dāng)前選舉的輪數(shù)（第一輪，r=0），G 表示這一輪循環(huán)中未當(dāng)選簇頭的節(jié)點(diǎn)集合。使用這個(gè)閾值，可保證每個(gè)節(jié)點(diǎn)會(huì)在使用這個(gè)閾值，可保證每個(gè)節(jié)點(diǎn)會(huì)在1/p 1/p 輪操作內(nèi)充當(dāng)一次簇首。輪操作內(nèi)充當(dāng)一次簇首。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議分析：在r=0時(shí)，T(n)=p，每個(gè)簇首節(jié)點(diǎn)的概率P是相同的。r的值越大， T(n)的值越來(lái)越

51、大，這樣未當(dāng)過(guò)簇首節(jié)點(diǎn)成為簇首的概率就越大。當(dāng) r=l/p-1時(shí)， T(n)=1，網(wǎng)絡(luò)中從未當(dāng)過(guò)簇首的節(jié)點(diǎn)都可能成為簇首。當(dāng) r=l/p 與 r=O 時(shí)T(n)的取值相同，r=l/p+l與 r=l時(shí)T(n)的取值相同，經(jīng)過(guò)1/p輪，所有節(jié)點(diǎn)又重新開(kāi)始新一輪的循環(huán)。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議簇的形成一旦簇首節(jié)點(diǎn)被隨機(jī)選舉出后，簇首節(jié)點(diǎn)需要告知其它節(jié)點(diǎn)自己已當(dāng)選為簇簇首節(jié)點(diǎn)需要告知其它節(jié)點(diǎn)自己已當(dāng)選為簇首的消息首的消息。該消息是非持續(xù)的一CSMA的ADV消息，ADV消息包含簇首節(jié)點(diǎn)標(biāo)號(hào)和一個(gè)報(bào)頭。簇首節(jié)點(diǎn)需要在整個(gè)網(wǎng)絡(luò)內(nèi)用最大發(fā)射功率進(jìn)行廣播簇首節(jié)點(diǎn)需要在整個(gè)網(wǎng)絡(luò)內(nèi)用最大發(fā)射功率

52、進(jìn)行廣播（由于ADV消息較小，增大簇首發(fā)射功率并不會(huì)造成額外大的能量消耗），以保證所有節(jié)點(diǎn)都能收到。普通節(jié)點(diǎn)普通節(jié)點(diǎn)接收到簇首廣播ADV消息后，選擇信號(hào)最強(qiáng)的簇首作為此輪要加入的選擇信號(hào)最強(qiáng)的簇首作為此輪要加入的簇簇。接收到的廣播信號(hào)最強(qiáng)則表示它與簇首距離最短。普通節(jié)點(diǎn)普通節(jié)點(diǎn)確定了所要加入的簇后，需要向簇首節(jié)點(diǎn)發(fā)送一個(gè)請(qǐng)求加入消息需要向簇首節(jié)點(diǎn)發(fā)送一個(gè)請(qǐng)求加入消息。該請(qǐng)求加入消息由節(jié)點(diǎn)自身ID、簇頭ID及報(bào)頭三部分組成。節(jié)點(diǎn)根據(jù)先前接收到的簇首節(jié)點(diǎn)的廣播ADV信號(hào)，調(diào)整向簇首節(jié)點(diǎn)發(fā)射的功率，使其和簇首節(jié)點(diǎn)廣播信號(hào)功率相同。簇首節(jié)點(diǎn)收到節(jié)點(diǎn)的請(qǐng)求加入消息后，會(huì)為其建立一個(gè)簇首節(jié)點(diǎn)收到節(jié)點(diǎn)的請(qǐng)求

53、加入消息后，會(huì)為其建立一個(gè)TDMATDMA時(shí)隙表時(shí)隙表。最后根最后根據(jù)成員節(jié)點(diǎn)的數(shù)目產(chǎn)生一個(gè)據(jù)成員節(jié)點(diǎn)的數(shù)目產(chǎn)生一個(gè)TDMATDMA時(shí)隙調(diào)度表，以廣播的方式發(fā)送出去時(shí)隙調(diào)度表，以廣播的方式發(fā)送出去，告訴成員在什么時(shí)刻可以發(fā)送數(shù)據(jù)。層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議工作流程：層次層次（分簇）型路由協(xié)議（分簇）型路由協(xié)議（2）穩(wěn)定階段（數(shù)據(jù)傳輸）一旦簇形成，TDMA調(diào)度表確定，數(shù)據(jù)傳輸就開(kāi)始了。簇頭節(jié)點(diǎn)在收到成員節(jié)點(diǎn)傳來(lái)的數(shù)據(jù)后對(duì)數(shù)據(jù)進(jìn)行數(shù)據(jù)融合和壓縮，將融合處理后的數(shù)據(jù)傳輸給Sink節(jié)點(diǎn)。在經(jīng)歷一段時(shí)間后，新的一輪重新開(kāi)始，上述過(guò)程又開(kāi)始循環(huán)進(jìn)行。具體過(guò)程如下：簇內(nèi)節(jié)點(diǎn)依據(jù)TDMA調(diào)度表所規(guī)定的時(shí)隙，將采集數(shù)據(jù)傳輸?shù)酱厥?。在?/p>