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

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

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

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

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

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

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

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

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

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

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

11、N-D-DEMANDEMAND D DISTANCEISTANCE V VECTORECTOR） 層次路由協(xié)議通過組合使用按需獲取和預先獲取等路由策略，避免了主動路由協(xié)議中過量的控制消息流量問題和按需路由協(xié)議中的長時延問題，常見的層次路由協(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 是第一個利用層次結(jié)構(gòu)并混合使用按需路由策略和主動路由策略的自組網(wǎng)路由協(xié)議。在ZRP 中，每個節(jié)點維護的區(qū)域大小由區(qū)域半徑指定，為了綜合利用按需路由和主動路由的優(yōu)點，ZRP 協(xié)議規(guī)定每個節(jié)點采用DVA 主動路由協(xié)議維護去往區(qū)域內(nèi)其他節(jié)點的路由，采用類似DSR 協(xié)議中的按需路由機制尋找去往區(qū)城外節(jié)點的路由。所以ZRP協(xié)議的性能很大程度上由區(qū)域半徑?jīng)Q定。通常小區(qū)域半徑適合于由移動速度較快的節(jié)點組成的密集型網(wǎng)絡；大區(qū)域半徑適合于由移動速度較慢的節(jié)點組成的稀疏網(wǎng)絡。當前主要無線分組網(wǎng)路由協(xié)議分析分析對比分析對比 路由協(xié)議是實現(xiàn)無線自組網(wǎng)最關(guān)鍵的部分。為了適應無線自組網(wǎng)帶寬

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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