1、路由、覆蓋與拓撲技術Agenda12無線傳感器網(wǎng)絡拓撲控制技術無線傳感器網(wǎng)絡覆蓋技術3無線傳感器網(wǎng)絡路由無線傳感器網(wǎng)絡路由1.11.2路由協(xié)議設計的關鍵問題簡單的無結構路由協(xié)議1.31.41.5樹類路由協(xié)議地理路由協(xié)議無線傳感器網(wǎng)絡路由協(xié)議比較1.6無線傳感器網(wǎng)絡路由概述11.1無線傳感器網(wǎng)絡路由概述路由協(xié)議的作用是尋找一條或多條滿足一定條件的，從源節(jié)點到目的節(jié)點的路徑，將數(shù)據(jù)分組沿著所尋找的路徑進行轉發(fā)?？梢姡酚蓞f(xié)議的功能主要有兩個方面：一、搜索滿足條件的從源節(jié)點到目的節(jié)點的優(yōu)化路徑；二、轉發(fā)資料分組。21.1無線傳感器網(wǎng)絡路由概述傳統(tǒng)有線網(wǎng)絡的路由協(xié)議主要運行在路由器上，采用集中控制的路

2、由尋找方法，即將整個網(wǎng)絡拓撲、鏈路狀態(tài)，如帶寬、時延等信息進行收集并計算出相應的路由。31.1無線傳感器網(wǎng)絡路由概述無線自組織網(wǎng)絡Ad-Hoc以及傳統(tǒng)無線局域網(wǎng)WLAN的路由協(xié)議的設計目標是：能夠為終端用戶提供高質(zhì)量的服務；合理利用網(wǎng)絡無線通信鏈路的帶寬；避免發(fā)生網(wǎng)絡擁塞；能夠以較快的速度響應用戶的服務請求。41.1無線傳感器網(wǎng)絡路由概述無線傳感器網(wǎng)絡路由協(xié)議類型： 以數(shù)據(jù)為中心的路由協(xié)議 基于層次結構（樹結構）的路由協(xié)議 基于地理信息路由協(xié)議 基于多路徑的路由協(xié)議在無線傳感器網(wǎng)絡的應用當中，終端用戶往往只關心所采集的數(shù)據(jù)而不關心這些數(shù)據(jù)具體是從哪一個節(jié)點傳送的，用戶只需向網(wǎng)絡發(fā)出一條查詢命令

3、，網(wǎng)絡就將所查詢的數(shù)據(jù)回饋給用戶。目的在于解決如何節(jié)省網(wǎng)絡節(jié)點的能量消耗，均攤網(wǎng)絡能量，延長網(wǎng)絡壽命。它將整個網(wǎng)絡的節(jié)點法劃分為多種類型，同類節(jié)點間可以交換數(shù)據(jù)。在路由選擇中，低一級節(jié)點將數(shù)據(jù)傳輸至簇頭節(jié)點（高一級節(jié)點），簇頭節(jié)點進行數(shù)據(jù)融合，減少了冗余數(shù)據(jù)在網(wǎng)絡中的傳輸，并且由于縮小了節(jié)點下一跳的選擇范圍，加快了路由算法的收斂速度，節(jié)省了能量。網(wǎng)絡中的節(jié)點利用GPS設備、三角定位系統(tǒng)等獲知自身所處的地理坐標，在進行路由選擇時，合理利用這些地理信息，從而將數(shù)據(jù)分組轉發(fā)給一個特定區(qū)域，而不是整個網(wǎng)絡，減少網(wǎng)絡能耗。在網(wǎng)絡數(shù)據(jù)傳輸過程當中，通過增加傳輸?shù)穆窂綌?shù)可以增加網(wǎng)絡的等效帶寬，并且在相同數(shù)據(jù)

4、量的前提下，能夠縮短傳輸時延。對無線傳感器網(wǎng)絡，多路徑路由協(xié)議能夠提高網(wǎng)絡的可靠性，并且可以將傳輸能耗分攤在更多的節(jié)點上。無線傳感器網(wǎng)絡路由路由協(xié)議設計的關鍵問題1.21.1無線傳感器網(wǎng)絡路由概述簡單的無結構路由協(xié)議1.31.41.5樹類路由協(xié)議地理路由協(xié)議無線傳感器網(wǎng)絡路由協(xié)議比較1.6 2路由協(xié)議設計的關鍵問題無線傳感器網(wǎng)絡路由協(xié)議不僅要考慮節(jié)點能量、計算能力、鏈路間帶寬限制的問題，更要從整個網(wǎng)絡系統(tǒng)的角度，根據(jù)具體的應用背景，考慮網(wǎng)絡能量的均衡使用，最終延長整個網(wǎng)絡的壽命。無線傳感器網(wǎng)絡在設計路由協(xié)議時一個最重要的目標就是在傳輸數(shù)據(jù)的同時，最大限度地延長網(wǎng)絡壽命并且避免網(wǎng)絡連通性降低。

5、2路由協(xié)議設計的關鍵問題因此，在設計路由協(xié)議時需要考慮到以下關鍵問題： 節(jié)點部署 數(shù)據(jù)精確性前提下的能耗 以數(shù)據(jù)為中心的數(shù)據(jù)報告模型 魯棒性與容錯性 網(wǎng)絡動態(tài)性 資料融合 2路由協(xié)議設計的關鍵問題 節(jié)點部署無線傳感器網(wǎng)絡節(jié)點的部署根據(jù)不同的應用而變化，并且部署方案對路由協(xié)議的性能有著影響。常用的節(jié)點部署方案有兩種：一是人為手工部署：這種部署方案節(jié)點的拓撲已知，數(shù)據(jù)通過預先定義的路徑傳播；二是隨機部署，節(jié)點通過Ad-Hoc自組織方式建立網(wǎng)絡。如果隨機部署不均，則需要采用優(yōu)化分簇策略，而且一條路徑可能有多跳組成。 2路由協(xié)議設計的關鍵問題數(shù)據(jù)精確性前提下的能耗:無線傳感器網(wǎng)絡中的節(jié)點數(shù)量較多在進行

6、精確計算時，部分節(jié)點可能由于大量計算和傳輸信息，從而使節(jié)點的電池能量消耗殆盡.此時，網(wǎng)絡拓撲發(fā)生變化，從而要求網(wǎng)絡的重新組織和路由發(fā)現(xiàn). 以數(shù)據(jù)為中心的數(shù)據(jù)報告模型:無線傳感器網(wǎng)絡數(shù)據(jù)報告依賴于應用與時間響應特性。數(shù)據(jù)報告模型可分為時間驅(qū)動、事件驅(qū)動、查詢驅(qū)動、和混合驅(qū)動。數(shù)據(jù)報告模型嚴重影響路由協(xié)議的路由穩(wěn)定性和能耗。 2路由協(xié)議設計的關鍵問題 魯棒性與容錯性：一些節(jié)點可能會由于能量耗盡、物理損壞或環(huán)境干擾等因素，造成故障或失效。然而這不能影響整個網(wǎng)絡服務，如果節(jié)點失效，則MAC層協(xié)議和路由協(xié)議必須保證新的鏈路產(chǎn)生，并將數(shù)據(jù)通過路由傳輸?shù)交竟?jié)點。 2路由協(xié)議設計的關鍵問題 網(wǎng)絡動態(tài)性：1)

7、、存在很多應用需要考慮傳感節(jié)點或者基站的移動性；2)、傳感現(xiàn)象本身也可能是動態(tài)的，如動態(tài)目標跟蹤；3)、節(jié)點加入或撤出以及節(jié)點的移動，都會使網(wǎng)絡拓撲發(fā)生變化。 2路由協(xié)議設計的關鍵問題 資料融合：由于傳感節(jié)點可能會產(chǎn)生許多重復冗余的數(shù)據(jù)，從多個不同節(jié)點傳輸?shù)南嗤臄?shù)據(jù)分組可以進行數(shù)據(jù)融合以降低通信量。 數(shù)據(jù)融合對不同傳感節(jié)點傳送的數(shù)據(jù)，根據(jù)某一融合規(guī)則進行融合。這個技術被許多路由協(xié)議用來達到能量有效以及傳輸數(shù)據(jù)優(yōu)化。信號處理技術同樣可以用來進行數(shù)據(jù)融合。無線傳感器網(wǎng)絡路由簡單的無結構路由協(xié)議1.31.1無線傳感器網(wǎng)絡路由概述路由協(xié)議設計的關鍵問題1.21.41.5樹類路由協(xié)議地理路由協(xié)議無線傳

8、感器網(wǎng)絡路由協(xié)議比較1.6 Flooding和Gossiping兩個路由協(xié)議是傳統(tǒng)網(wǎng)絡中最為經(jīng)典和簡單的路由協(xié)議，它們都是基于洪泛機制的路由協(xié)議，可以應用到無線傳感器網(wǎng)絡中。簡單的無結構路由協(xié)議：Flooding和Gossiping路由協(xié)議Flooding路由協(xié)議 Flooding路由協(xié)議不要求維護網(wǎng)絡的拓撲結構和相關路由計算，僅要求傳感器網(wǎng)絡節(jié)點在接收到信息后以廣播的方式向鄰居節(jié)點轉發(fā)數(shù)據(jù)包，鄰居節(jié)點重復執(zhí)行上述過程（轉發(fā)時除去剛剛發(fā)送給它們的節(jié)點），直到數(shù)據(jù)包到達目的地或者該數(shù)據(jù)包的生存時間結束。 無線傳感器網(wǎng)絡中數(shù)據(jù)包的生存時間TTL，一般預先設定這個數(shù)據(jù)包所轉發(fā)的最大跳數(shù)。ABCDEF

9、GHPPPPPPP以此類推，直到p到大匯聚節(jié)點D或到達TTL源節(jié)點A需要將數(shù)據(jù)包p發(fā)送至匯聚節(jié)點D節(jié)點A首先將p的副本廣播，則其鄰居節(jié)點B接收到p副本節(jié)點B直接將p副本通過廣播的形式轉發(fā)給E、F、CFlooding路由協(xié)議優(yōu)缺點 每個節(jié)點只需將接收到的數(shù)據(jù)包進行廣播，而無需查找路由表，選擇下一跳節(jié)點的計算；無需特殊的算法保持網(wǎng)絡拓撲信息的更新以及新路由的發(fā)現(xiàn)。但是Flooding路由協(xié)議的漏洞也是十分明顯且致命的，主要有以下3個方面。 信息內(nèi)爆（Implosion）：所謂信息內(nèi)爆是指網(wǎng)絡中的節(jié)點收到一個數(shù)據(jù)的多個副本的現(xiàn)象。 部分重迭（Overlap）現(xiàn)象：由于無線傳感器網(wǎng)絡節(jié)點密集部署，因此

10、在同一局部區(qū)域中，若干個節(jié)點對區(qū)域內(nèi)同一個事件做出的反應相同，所感知的信息在數(shù)據(jù)性質(zhì)上相似，數(shù)值上相同，那么這些節(jié)點的鄰居節(jié)點所接收到的數(shù)據(jù)副本也具有較大的相關性。Flooding路由協(xié)議優(yōu)缺點 網(wǎng)絡資源利用不合理：每個節(jié)點只是單純地將接收到的數(shù)據(jù)進行廣播，并沒有考慮到網(wǎng)絡中節(jié)點能量消耗的問題，不能發(fā)現(xiàn)下一跳節(jié)點的可行性，從而不具備自適應性，造成網(wǎng)絡資源浪費。盡管Flooding路由協(xié)議在數(shù)據(jù)傳輸時能量消耗巨大，網(wǎng)絡生存時間一般較短，不適應大規(guī)模的網(wǎng)絡，但其具有路徑容錯性好，傳輸延時短的優(yōu)點，適用于對數(shù)據(jù)可靠性要求較高的應用場景。Gossiping路由協(xié)議 Gossiping路由協(xié)議，即閑聊路

11、由協(xié)議，是對Flooding路由協(xié)議的改進，當節(jié)點接收到數(shù)據(jù)之后，并不是像Flooding協(xié)議那樣，采用廣播形式將數(shù)據(jù)包發(fā)送給所有鄰居節(jié)點，而是按照一定概率隨機地將數(shù)據(jù)包轉發(fā)給鄰居節(jié)點中不同于發(fā)送節(jié)點的某一個節(jié)點，這個節(jié)點以相同的方式向其鄰居節(jié)點進行數(shù)據(jù)轉發(fā)直到數(shù)據(jù)到達匯聚節(jié)點。Gossiping路由協(xié)議考慮了節(jié)點的能量消耗，因此在選擇下一跳時只選擇一個節(jié)點進行數(shù)據(jù)轉發(fā)，但在每次選取下一跳節(jié)點時，并沒有采用路徑優(yōu)化相關算法，因此所選擇的路由往往不理想，這將導致數(shù)據(jù)包的端到端延時增加或者生存時間在沒到達目的節(jié)點之前就結束。Ds初始設置每個數(shù)據(jù)包TTL=6此時TTL=0，資料包在此處丟失，不再往下

12、傳至D假設任意兩節(jié)點間的端到端時延相同，節(jié)點間連接表示兩節(jié)點間可通信。從源節(jié)點S到匯聚節(jié)點D時延最短的路徑一共要經(jīng)過6跳。簡單的無結構路由協(xié)議：SPIN路由協(xié)議 SPIN（Sensor Protocols for Information via Negotiation，信息協(xié)商的傳感器協(xié)議）是無線傳感器網(wǎng)絡中一種基于數(shù)據(jù)中心的路由協(xié)議，其通過節(jié)點之間的協(xié)商以建立傳輸路徑。SPIN協(xié)議的設計目標是能夠解決Flooding以及Gossiping協(xié)議的內(nèi)爆、重疊及資源利用不合理現(xiàn)象。簡單的無結構路由協(xié)議：SPIN路由協(xié)議SPIN協(xié)議在路由建立時，一共采用了3種類型的數(shù)據(jù)包：ADV、REQ與DATA。

13、ADV數(shù)據(jù)包是一個路由請求發(fā)起的數(shù)據(jù)包，當某一節(jié)點接收到數(shù)據(jù)包時，它會向其周圍的鄰居節(jié)點廣播這個ADV數(shù)據(jù)包，以通告是否需要接收數(shù)據(jù)，由于ADV數(shù)據(jù)包體積很小，所消耗的能量資源較少。REQ數(shù)據(jù)包是請求響應數(shù)據(jù)包，當鄰居節(jié)點接收到來自傳輸請求節(jié)點發(fā)起的ADV數(shù)據(jù)包后，若其需要接收，則向請求發(fā)起節(jié)點發(fā)送REQ資料包。DATA數(shù)據(jù)包即為傳感采集的數(shù)據(jù)內(nèi)容。154320DATAADVADVADVADV0號節(jié)點向1號節(jié)點發(fā)送傳感數(shù)據(jù)當1號節(jié)點接收到數(shù)據(jù)后，向其周邊鄰居節(jié)點廣播ADV數(shù)據(jù)包，通知鄰居節(jié)點自己有傳感數(shù)據(jù)需要轉發(fā)當1號節(jié)點的鄰居節(jié)點接收到ADV數(shù)據(jù)包后，根據(jù)自己的情況，自主選擇接受數(shù)據(jù)DATA

14、與否，節(jié)點3與節(jié)點5選擇接收數(shù)據(jù)DATA，因此其向1號節(jié)點發(fā)送REQ數(shù)據(jù)包當1號節(jié)點接收到節(jié)點3和節(jié)點5發(fā)送的REQ，即立刻將DATA發(fā)送至這兩個節(jié)點REQREQDATADATASPIN路由協(xié)議轉發(fā)過程簡單的無結構路由協(xié)議：定向擴散路由協(xié)議 定向擴散路由協(xié)議（Directed Diffusion）簡稱DD路由協(xié)議，是一種典型的以數(shù)據(jù)為中心，基于查詢的路由機制。匯聚節(jié)點根據(jù)不同的應用需求定義不同的興趣（Interest）請求消息，并通過洪泛的方式將興趣請求消息數(shù)據(jù)包發(fā)送至全網(wǎng)或者局部網(wǎng)絡的傳感器節(jié)點。在進行興趣消息洪泛發(fā)送過程的同時，每個節(jié)點根據(jù)緩存中的興趣列表，沿著興趣消息發(fā)送方向的反向建立數(shù)

15、據(jù)傳輸梯度（Gradient），當興趣消息到達源節(jié)點后，源節(jié)點則將數(shù)據(jù)沿著之前建立好的傳輸梯度進行正向傳輸，直到匯聚節(jié)點。 定向擴散路由協(xié)議為了能夠適應網(wǎng)絡拓撲的動態(tài)變化，采用周期性地對網(wǎng)絡進行路由維護與更新，其主要分為3個階段：興趣消息擴散、數(shù)據(jù)傳輸梯度建立、路徑加強。興趣消息擴散：DFBACE匯聚節(jié)點節(jié)點B收到節(jié)點A發(fā)送過來的消息之后的操作流程如下：判斷是否與剛才轉發(fā)給D的消息相同，如果是則丟棄該“興趣” ；否則檢查本地興趣列表，如果沒有相同“興趣”，則增加新表項并轉發(fā)“興趣”，否則判斷表項中是否有鄰居節(jié)點等于興趣消息數(shù)據(jù)包中的發(fā)送節(jié)點，如果是則更新最新時間戳，否則添加新鄰居節(jié)點，轉發(fā)“興

16、趣”。以A、B、D演示興趣消息的擴散過程匯聚節(jié)點向傳感器網(wǎng)絡內(nèi)節(jié)點A、B廣播興趣消息節(jié)點A、B接收到興趣消息，然后，節(jié)點A向節(jié)點B、D廣播接收到的消息，同時節(jié)點B向節(jié)點D廣播接收到的消息。簡單的無結構路由協(xié)議：謠傳路由協(xié)議謠傳路由協(xié)議（Rumor Routing Protocol）是在定向擴散路由協(xié)議的基礎上建立起來的，適用于數(shù)據(jù)傳輸量較小的傳感器網(wǎng)絡，被認為是SPIN路由協(xié)議與定向擴散路由協(xié)議的折中，并且加入了Gossiping隨機轉發(fā)給其某一鄰居節(jié)點的轉發(fā)機制。由定向擴散路由協(xié)議可以看出，若匯聚節(jié)點對網(wǎng)絡的數(shù)據(jù)查詢只有一次，并且源節(jié)點只需向匯聚節(jié)點上報一次數(shù)據(jù)，使用定向擴散協(xié)議的開銷就會比

17、較大。謠傳路由協(xié)議正是為了解決這一問題。該路由協(xié)議借鑒了歐式平面幾何中的任意兩條曲線相交的概率較大的思想，從源節(jié)點產(chǎn)生代理數(shù)據(jù)包（Agent）并發(fā)送，匯聚節(jié)點發(fā)送請求探測數(shù)據(jù)包，兩者都隨機進行下一跳節(jié)點的選擇，直到兩個數(shù)據(jù)包在某一節(jié)點上相交，則構成了一條可行路由。匯聚節(jié)點相交節(jié)點傳感器節(jié)點傳感器節(jié)點監(jiān)測區(qū)域謠傳路由協(xié)議示例無線傳感器網(wǎng)絡路由樹類路由協(xié)議1.41.1無線傳感器網(wǎng)絡路由概述路由協(xié)議設計的關鍵問題1.21.31.5簡單的無結構路由協(xié)議地理路由協(xié)議無線傳感器網(wǎng)絡路由協(xié)議比較1.6高彈性多徑路由協(xié)議 無線傳感器網(wǎng)絡由于其節(jié)點的能量有限，應用場景復雜多變，因此其網(wǎng)絡的動態(tài)性較大，節(jié)點往往會

18、由于某種原因而失效，人們將這種情況稱為彈性。為了解決無線傳感器網(wǎng)絡中數(shù)據(jù)傳輸?shù)目煽啃詥栴}，一種常見的策略是采取多條路徑的路由策略。通過利用冗余路徑，當一條路徑失效時，可以選擇其余路徑進行數(shù)據(jù)分發(fā)。在多路徑路由當中，通常將多條路徑中性能最優(yōu)的路徑作為主路徑，性能最優(yōu)可以根據(jù)需要定義不同的衡量標準，其余路徑則作為備選路徑。通常，多路徑路由有兩種：一種是分離多路徑，另一種則是纏繞多路徑。多路徑的彈性和維護開銷有著密切關系：彈性好，意味著協(xié)議能夠快速檢測到路徑失效并切換到另外的路徑上。樹類路由協(xié)議：SAR路由協(xié)議 SAR（Sequential Assignment Routing）有序分配路由協(xié)議是第

19、一個在無線傳感器網(wǎng)絡中保證QoS的主動路由協(xié)議，也是一種基于多路徑的路由協(xié)議。 為了能夠建立起從每個節(jié)點到達匯聚節(jié)點的多徑路由，從匯聚節(jié)點的每個鄰居節(jié)點開始，以它們?yōu)闃涓?，依次擴展建立樹狀結構。從匯聚節(jié)點開始，每一個樹都會盡可能地向具有滿足QoS或者剩余能量較多的鄰居節(jié)點延伸和擴展。樹類路由協(xié)議：SAR路由協(xié)議當構建樹完成后，大多數(shù)節(jié)點都將成為所建樹的一部分，并且由于匯聚節(jié)點周圍的鄰居節(jié)點都是這些樹的樹根節(jié)點，因此所形成的多條路徑針對匯聚節(jié)點周圍的鄰居節(jié)點是不相交的，如圖所示.這樣有效避免了匯聚節(jié)點周圍節(jié)點能量消耗過快的問題。樹類路由協(xié)議：SAR路由協(xié)議 對于每條路徑，都有兩個參數(shù)與其相關聯(lián)：

20、1、如果獨占一條路徑，則能量資源將通過轉發(fā)的最大數(shù)據(jù)分組數(shù)量進行估計，而無需等待流量資源的耗盡；2、額外的QoS度量標準。SAR路由協(xié)議的設計目標就是要尋找一條滿足QoS要求的路徑，并且同時延長網(wǎng)絡壽命。樹類路由協(xié)議：LEACH LEACH(Low Energy Adaptive Clustering Hierachy),低功耗自適應集簇分層型協(xié)議，它打破了原有成簇算法中固定簇頭的思想，采用本地簇頭隨機輪循機制將能量負載均勻分布到網(wǎng)絡中的所有節(jié)點，提升了簇狀無線傳感器網(wǎng)絡的性能。 LEACH也可以說是一種自適應分簇拓撲算法，其基本思想是將節(jié)點組織成簇結構形式，每個簇有一個簇頭節(jié)點（Cluste

21、r Head Node），其他節(jié)點作為非簇頭節(jié)點。所有的非簇頭節(jié)點只與本簇的簇頭節(jié)點通信，感知的數(shù)據(jù)由簇頭節(jié)點傳輸?shù)絊ink節(jié)點，簇頭節(jié)點除了傳輸非簇頭節(jié)點的數(shù)據(jù)外，還要執(zhí)行數(shù)據(jù)融合功能。因此，簇頭節(jié)點要比非簇頭節(jié)點消耗更多能量，為了避免節(jié)點長期擔當簇頭功能而過早耗盡能量，LEACH使用輪轉的方式選舉節(jié)點成為簇頭節(jié)點，從而讓所有的節(jié)點都有機會成為簇頭節(jié)點而達到網(wǎng)絡中節(jié)點能量消耗均勻的目的。LEACH路由拓撲按照規(guī)定選取合適的簇頭當網(wǎng)絡中部分節(jié)點選擇自己為簇頭節(jié)點后,則發(fā)布消息通知網(wǎng)絡中其它節(jié)點自己是簇頭節(jié)點。每個非簇頭節(jié)點根據(jù)自己與簇頭之間的距離來選擇加入哪個簇，并通知該簇頭，簇頭收到消息后將

22、該節(jié)點加入到簇成員表中。非簇頭節(jié)點在簇內(nèi)指定的持續(xù)時間內(nèi)發(fā)送一次數(shù)據(jù)，在沒有數(shù)據(jù)發(fā)送時，將進入休眠狀態(tài)以節(jié)省能量，而簇頭節(jié)點保持工作狀態(tài)以接收數(shù)據(jù)。簇頭收到所有的簇內(nèi)數(shù)據(jù)之后，就執(zhí)行數(shù)據(jù)融合功能，然后將處理后的數(shù)據(jù)傳輸?shù)絊ink節(jié)點。Sink節(jié)點樹類路由協(xié)議：PEGASIS及Hierarchical-PEGASIS路由 PEGASIS（Power-Efficient Gathering in Sensor Information Systems），一種基于LEACH協(xié)議基礎上建立起來的路由協(xié)議，主要解決LEACH協(xié)議中由于簇頭頻繁變更，導致通信開銷較大的問題。與LEACH協(xié)議不同，PEGASI

23、S協(xié)議并不采用全網(wǎng)多個簇頭的方案，而是只采用一個簇頭，其將全網(wǎng)看成是一個簇群，并將其稱為鏈。簇頭節(jié)點與匯聚節(jié)點能夠通過一跳通信，其余傳感器節(jié)點只能通過多跳的形式與簇頭節(jié)點通信。 PEGASIS將全網(wǎng)看成是一個鏈，因此簇頭節(jié)點將鏈分成兩部分，則數(shù)據(jù)分別從兩端傳輸至簇頭節(jié)點，在傳輸?shù)倪^程中，每個節(jié)點必須知道自己的所在地理位置，以便在轉發(fā)時采用貪心策略，將數(shù)據(jù)轉發(fā)給與其距離最近的節(jié)點，并在轉發(fā)過程中應做相應的數(shù)據(jù)融合。當兩端數(shù)據(jù)發(fā)送完畢后，進行下一輪簇頭節(jié)點的選擇。樹類路由協(xié)議：TEEN路由 TEEN(Threshold-sensitive Energy Efficient sensor Netwo

24、rk protocol) 能量有效的閾值敏感路由協(xié)議是一種具有實時性的路由協(xié)議，它采用多簇運行方式，但是它的網(wǎng)絡結構具有多層次的分層結構，即一個簇內(nèi)的普通節(jié)點可以被用作另一個簇的簇頭節(jié)點。 TEEN協(xié)議引入了兩個參數(shù)值：硬門限與軟門限。在數(shù)據(jù)傳輸過程中，仍采用TDMA的機制，首先由匯聚節(jié)點向網(wǎng)絡中傳感器節(jié)點廣播硬門限值，則傳感器節(jié)點根據(jù)這個硬門限值，在第一次將監(jiān)測到的數(shù)據(jù)上報給簇頭節(jié)點時，僅僅上報其值大于硬門限的數(shù)據(jù)，并將當前的監(jiān)測數(shù)據(jù)保存為監(jiān)測值（Sensed Value，SV）。在這之后監(jiān)測到的數(shù)據(jù)則根據(jù)硬門限與軟門限兩者共同決定是否需要上報給簇頭節(jié)點，凡是數(shù)值大于硬門限值且與SV之差的絕

25、對值不小于軟門限時，節(jié)點才向簇頭上報數(shù)據(jù)，并將當前觀測到的數(shù)據(jù)作為最新的SV。樹類路由協(xié)議：APTEEN路由 APTEEN(Adaptive Periodic Threshold-sensitive Energy Efficient sensor Network protocol) 是TEEN協(xié)議的設計者對其自身的改良，是一種混合協(xié)議，兼有主動和響應兩種類型的數(shù)據(jù)傳輸模式，可以根據(jù)用戶需要和應用類型來設定TEEN協(xié)議的周期性和軟、硬門限的值，既可以周期性采集數(shù)據(jù)，又可以對時間做出快速響應，從而避免了協(xié)議在周期性上報數(shù)據(jù)應用中數(shù)據(jù)上報不足的錯誤現(xiàn)象發(fā)生。無線傳感器網(wǎng)絡路由地理路由協(xié)議1.51.1

26、無線傳感器網(wǎng)絡路由概述路由協(xié)議設計的關鍵問題1.21.31.4簡單的無結構路由協(xié)議樹類路由協(xié)議無線傳感器網(wǎng)絡路由協(xié)議比較1.6基于局部地理拓撲的單播路由協(xié)議 基于局部地理拓撲的典型單播路由協(xié)議是指每個節(jié)點僅僅知道其鄰居節(jié)點所在的地理位置，而不知道全網(wǎng)所有節(jié)點地理位置，利用局部地理信息位置，進行路由的選擇。 基于局部地理拓撲的單播路由協(xié)議 經(jīng)典的PALR路由協(xié)議中，要求每個傳感器節(jié)點僅知道自己、目標節(jié)點與其鄰居節(jié)點的地理位置信息。PALR是根據(jù)地理位置來優(yōu)化網(wǎng)絡的傳輸能量?；诰植康乩硗負涞膯尾ヂ酚蓞f(xié)議設網(wǎng)絡中源節(jié)點為S，匯聚節(jié)點為BS，S的鄰居節(jié)點為s1,s2, sn ，則S在選擇路徑時，將整

27、個路徑拆分為兩個部分：一是從S到其鄰居節(jié)點的單跳路徑，二是從其某鄰居節(jié)點到匯聚節(jié)點的單跳或多跳路徑，實線表示源節(jié)點到鄰居節(jié)點的路徑，虛線表示從鄰居節(jié)點到匯聚節(jié)點的路徑?；诰植康乩硗負涞膯尾ヂ酚蓞f(xié)議 對于任意一條從源節(jié)點S到匯聚節(jié)點BS的路徑，其能量消耗可以用兩端路徑消耗能量之和u(.)+v(.) 表示，其中u(.)表示第一段路徑的能量消耗， v(.)表示第二段路徑的能量消耗，則尋找的路徑應滿足minu(.)+v(.) ，即總能量消耗最小。對于u(.)，由于節(jié)點知道其鄰居節(jié)點的地理坐標，因此能夠較為容易且準確地計算出通信代價，但是v(.)并不能準確計算出，因此需要估計出來，PALR采取的辦法是

28、利用最小理想能耗來計算u(.)+v(.) 。每個節(jié)點在選擇下一跳時，都選出使得u(.)+v(.)最小的下一跳節(jié)點?；诘乩砦恢眯畔⒏纳频亩嗖ヂ酚蓞f(xié)議 基于地理位置信息的多播協(xié)議LBM是在保證多播精確度的前提下，利用地理位置信息，進行有目的的廣播數(shù)據(jù)包轉發(fā)，從而降低整個網(wǎng)絡的通信能耗。LBM利用多播目的節(jié)點的地理位置信息，定義了轉發(fā)區(qū)域，只有在轉發(fā)區(qū)域內(nèi)的節(jié)點才會轉發(fā)多播數(shù)據(jù)包。通常，轉發(fā)域主要有以下3種類型:（1）靜態(tài)轉發(fā)域 靜態(tài)轉發(fā)域是通過將目標域與源節(jié)點限制在一定范圍空間中，從而將節(jié)點的數(shù)據(jù)轉發(fā)范圍縮小，有效降低廣播的通信量?；诘乩砦恢眯畔⒏纳频亩嗖ヂ酚蓞f(xié)議（2）自適應轉發(fā)域 自適應轉發(fā)

29、域是指轉發(fā)域會隨著數(shù)據(jù)包的不斷轉發(fā)進行相應的變化。通過自適應將轉發(fā)區(qū)域根據(jù)當前數(shù)據(jù)發(fā)送節(jié)點進行調(diào)整，可以進一步提高網(wǎng)絡數(shù)據(jù)通信效率，避免冗余數(shù)據(jù)通信，但是，由于節(jié)點每一次收到新數(shù)據(jù)時都需要計算自適應轉發(fā)域的大小，增加了個別節(jié)點的計算復雜性程度。（3）基于前進距離的非顯示轉發(fā)域 基于前進距離的非顯示轉發(fā)域不像前面兩種轉發(fā)域那樣具有一種范圍較為準確、形狀相對規(guī)整的區(qū)域，而是一種根據(jù)每個節(jié)點自身計算值，決定是否將數(shù)據(jù)包向前轉發(fā)，即這個轉發(fā)區(qū)域是時刻在變的且沒有固定形狀。柵格劃分：邊長的選擇d是兩節(jié)點之間的通信距離。任意兩個相鄰的柵格之間，若要使得在兩柵格中任意地理位置的兩簇頭都能夠正常通信，則邊長r

30、與通信半徑d滿足：基于地理柵格的分層網(wǎng)絡路由協(xié)議123400123整個網(wǎng)絡劃分成一個個正方形的小柵格，節(jié)點通過每個柵格內(nèi)的簇頭節(jié)點構成網(wǎng)絡的骨干網(wǎng)絡完成數(shù)據(jù)通信。每個柵格都有自己的編號，柵格內(nèi)的所有節(jié)點都共享這個柵格編號，柵格內(nèi)的簇頭節(jié)點負責柵格中分組轉發(fā)。柵格簇頭節(jié)點的選擇原則是按照停留在柵格內(nèi)時間最長的節(jié)點作為簇頭節(jié)點，一旦某節(jié)點擔當了簇頭節(jié)點，只有其離開該柵格時才會進行新一輪的簇頭選擇。GRID路由協(xié)議主要包括3個階段：柵格劃分路由建立路由維護節(jié)點以自己和歸屬柵格中心點的距離設定定時器，定時器到時，選舉自己成為簇頭，并周期性地發(fā)送通告消息，其他節(jié)點接收到消息后，則加入該柵格。如果同時有多

31、個節(jié)點競爭簇頭，在收到其他簇頭的通告消息后，距離柵格中心較遠的簇頭放棄簇頭地位，保證柵格中的簇頭個數(shù)不超過一個。節(jié)點無線傳感器網(wǎng)絡路由無線傳感器網(wǎng)絡路由協(xié)議比較1.61.1無線傳感器網(wǎng)絡路由概述路由協(xié)議設計的關鍵問題1.21.31.4簡單的無結構路由協(xié)議樹類路由協(xié)議地理路由協(xié)議1.5路由協(xié)議單路徑多路徑平面結構樹狀結構混合路由基于地理位置基于數(shù)據(jù)融合Flooding可選Gossiping可能SPIN可能可能DDRumor高彈性多路徑可能可能SARLEACH可能PEGASISH-PEGASISTEENAPTEENPALRLBMGRID基于地理柵格的分層網(wǎng)絡路由協(xié)議路由、覆蓋與拓撲技術無線傳感器網(wǎng)

32、絡拓撲控制技術 2無線傳感器網(wǎng)絡路由 1無線傳感器網(wǎng)絡覆蓋技術 3無線傳感器網(wǎng)絡拓撲控制技術拓撲控制技術概述2.12.2拓撲控制意義拓撲控制的設計目標2.32.42.5功率控制技術典型的層次型拓撲控制方法拓撲控制中的休眠調(diào)度技術2.6 拓撲控制技術是無線傳感器網(wǎng)絡中的基本問題。動態(tài)變化的拓撲結構是無線傳感器網(wǎng)絡最大特點之一，因此拓撲控制策略在無線傳感器網(wǎng)絡中有著重要的意義。 目前，在網(wǎng)絡協(xié)議分層中沒有明確的層次對應拓撲控制機制，但大多數(shù)的拓撲算法是部署于介質(zhì)訪問控制層（MAC）和路由層（Routing）之間，它為路由層提供足夠的路由更新信息，反之，路由表的變化也反作用于拓撲控制機制，MAC層可

33、以提供給拓撲控制算法鄰居發(fā)現(xiàn)等消息。拓撲控制技術概述路由層拓撲管理/控制MAC層拓撲控制技術概述向上提供信息向上提供信息觸發(fā)算法運行觸發(fā)算法運行無線傳感器網(wǎng)絡拓撲控制技術拓撲控制意義2.22.1拓撲控制技術概述拓撲控制的設計目標2.32.42.5功率控制技術典型的層次型拓撲控制方法拓撲控制中的休眠調(diào)度技術2.6拓撲控制的意義 影響整個網(wǎng)絡的生存時間 減小節(jié)點間通信干擾，提高網(wǎng)絡通信效率為路由協(xié)議、時間同步提供基礎 影響數(shù)據(jù)融合 彌補節(jié)點失效的影響無線傳感器網(wǎng)絡節(jié)點一般采用電池供電,節(jié)能是網(wǎng)絡設計主要考慮的問題之一.拓撲控制的一個重要目標就是在保證網(wǎng)絡連通性和覆蓋的情況下,盡量合理高效的使用網(wǎng)絡

34、能量,延長整個網(wǎng)絡的生命存時間.無線傳感器網(wǎng)絡中節(jié)點部署看可能在某范圍內(nèi)很密集，如果每個節(jié)點都以大功率進行通信，會加劇節(jié)點之間的干擾；若節(jié)點發(fā)射功率過小，又會導致網(wǎng)絡的割裂，影響網(wǎng)絡的連通性。在無線傳感器網(wǎng)絡中，只有活動的節(jié)點才能夠進行數(shù)據(jù)轉發(fā)，而拓撲控制可以確定由哪些節(jié)點作為轉發(fā)節(jié)點，同時確定節(jié)點之間的鄰居關系。無線傳感器網(wǎng)絡中的數(shù)據(jù)融合指傳感器節(jié)點將采集的數(shù)據(jù)發(fā)送給骨干節(jié)點，骨干節(jié)點進行數(shù)據(jù)融合，并把融合結果發(fā)送給數(shù)據(jù)收集節(jié)點。而骨干節(jié)點的選擇是拓撲控制的一項重要內(nèi)容。傳感器節(jié)點可能部署在惡劣的環(huán)境中，在軍事應用中甚至部署在敵方區(qū)域中，所以很容易受到破壞而失效。這就要求網(wǎng)絡拓撲結構具有魯棒

35、性以適應這種情況。無線傳感器網(wǎng)絡拓撲控制技術拓撲控制的設計目標2.32.1拓撲控制技術概述拓撲控意義2.22.42.5功率控制技術典型的層次型拓撲控制方法拓撲控制中的休眠調(diào)度技術2.6為了實現(xiàn)傳感器節(jié)點間的相互通信,生成的拓撲必須保證連通性,即從任何一個節(jié)點都可以發(fā)送消息到另外一個節(jié)點。連通性是任何無線傳感器網(wǎng)絡拓撲控制算法都必須保證的一個重要性質(zhì)。覆蓋可以看成是對傳感器網(wǎng)絡服務質(zhì)量的度量。在覆蓋問題中，最重要的因素是網(wǎng)絡對物理世界的感知能力。生成的拓撲必須保證足夠大的覆蓋度，即覆蓋面積足夠大的監(jiān)視區(qū)域。根據(jù)文獻，衡量全網(wǎng)覆蓋情況有一個量化指標平均每個節(jié)點的覆蓋率c（%）：在無線傳感器網(wǎng)絡中，

36、一般情況下是不設置認證中心的，傳感器節(jié)點只能依據(jù)自身從網(wǎng)絡中收集的信息做出決策。另外，任何一種涉及節(jié)點間同步的通信協(xié)議都有建立通信的開銷。顯然，若節(jié)點能夠了解全局拓撲和傳感器網(wǎng)絡中所有節(jié)點的能量，就能做出最優(yōu)的決策；若不計同步消息的開銷，得到的就是最優(yōu)的性能。但是，若所有節(jié)點都要了解全局信息，則同步消息產(chǎn)生的開銷要多于數(shù)據(jù)消息，這將導致網(wǎng)絡系統(tǒng)開銷大大增加，從而使得網(wǎng)絡的生存期減少。當網(wǎng)絡負載較高時，低發(fā)射功率會帶來較小的端到端延遲；而在低負載情況下，低發(fā)射功率會帶來較大的端到端延遲。減少通信干擾、減少MAC層的競爭和延長網(wǎng)絡的生命期基本上是一致的。功率控制可以調(diào)節(jié)發(fā)射范圍，層簇式網(wǎng)絡可以調(diào)節(jié)

37、工作節(jié)點的數(shù)量。這些都能改變一跳鄰居節(jié)點的個數(shù)，即與它競爭信道的節(jié)點數(shù)。無線傳感器網(wǎng)絡拓撲結構的對稱性是指若從節(jié)點m到n有一條邊，那么一定存在從節(jié)點n到m的邊。由于非對稱鏈路在目前的MAC協(xié)議中沒有得到很好的支持，而且非對稱鏈路通信的開銷很大，對于傳感器網(wǎng)絡能量小的特點而言是一個瓶頸，因此一般都要求生成的拓撲中鏈路是對稱的。如何合理利用傳感器節(jié)點能量問題一直都是無線傳感器網(wǎng)絡研究熱點之一，因此，能量優(yōu)化也必然成為無線多跳網(wǎng)絡拓撲控制研究的一個重要目標。Chandrakasan等指出，設計能量消耗最小化的網(wǎng)絡協(xié)議是無線傳感器網(wǎng)絡成功應用的關鍵。拓撲控制的設計目標1能量消耗2覆蓋度3連通性4算法的

38、分布式程度7對稱性8魯棒性和可擴展性5網(wǎng)絡延遲6干擾和競爭無線傳感器網(wǎng)絡是與應用密切相關的,不同的應用對應有不同的拓撲控制設計目標要求.傳感器節(jié)點一般采用干電池來儲備能量，其能量很有限，節(jié)點易造成因能量耗盡而失效，無線通信鏈路易受環(huán)境影響而無法保證通信質(zhì)量。另外，新節(jié)點的加入、部分傳感器節(jié)點的可移動性等均會造成網(wǎng)絡拓撲結構的變化。這就要求拓撲控制具有魯棒性和可擴展性，以適應變化，從而保證網(wǎng)絡的連通性和覆蓋度。無線傳感器網(wǎng)絡拓撲控制技術功率控制技術2.42.1拓撲控制技術概述拓撲控意義2.22.32.5拓撲控制的設計目標典型的層次型拓撲控制方法拓撲控制中的休眠調(diào)度技術2.6功率控制技術在滿足網(wǎng)絡

39、連通的前提下,通過節(jié)點功率控制或動態(tài)調(diào)整節(jié)點的發(fā)射功率,精簡節(jié)點間的無線通信鏈路,以生成一個高效的數(shù)據(jù)轉發(fā)拓撲結構,在保證網(wǎng)絡拓撲連通的基礎上,使得網(wǎng)絡中節(jié)點的能量消耗最小。1統(tǒng)一功率分配算法COMPOW2基于節(jié)點度的功率控制LMN/LMA3基于鄰近圖的功率控制功率控制技術1統(tǒng)一功率分配算法COMPOW2基于節(jié)點度的功率控制LMN/LMA3基于鄰近圖的功率控制功率控制技術COMPOW(COMmon POWer)協(xié)議是一種簡單的將功率控制與路由協(xié)議相結合的解決方案，其基本思想是：所有的傳感器節(jié)點使用一致的發(fā)射功率，在保證網(wǎng)絡連通的前提下將功率最小化。1、COMPOW建立各個功率級的路由表，在功率

40、Pi級時，通過使用功率Pi交換HELLO消息建立路由表RTpi，所有可達節(jié)點都是路由表中的表項。2、COMPOW選擇最小的發(fā)射功率Pcom，使得RTpcom與最大發(fā)射功率具有相同數(shù)量的表項，于是整個網(wǎng)絡使用公共的發(fā)射功率Pcom。但該協(xié)議只適用于節(jié)點分布均勻的情況，缺陷較為明顯。1統(tǒng)一功率分配算法COMPOW2基于節(jié)點度的功率控制LMN/LMA3基于鄰近圖的功率控制功率控制技術功率控制技術節(jié)點的度數(shù)：是指所有距離該節(jié)點一跳的鄰居節(jié)點的數(shù)目?；诠?jié)點度的算法一般是通過動態(tài)調(diào)節(jié)節(jié)點的發(fā)射功率，使得節(jié)點的度數(shù)處于一個合理的區(qū)間。LMA/LMN是基于節(jié)點度數(shù)的算法。LMA: Local Mean Al

41、gorithm，本地平均算法LMN: Local Mean of Neighbors Algorithm ,本地鄰居平均算法LMA和LMN是兩種周期性動態(tài)調(diào)整節(jié)點發(fā)射功率的算法。 功率控制技術LMA算法的主要思想：給定節(jié)點度數(shù)的上下限，動態(tài)調(diào)整節(jié)點的發(fā)射功率，使得節(jié)點的度落在要求區(qū)間內(nèi)。LMN與LMA相似，區(qū)別在于LMN將所有鄰居的鄰居數(shù)求平均值作為自己的平均數(shù)。優(yōu)缺點：1、LMN算法和LMA算法對節(jié)點的要求不高，不需要嚴格的時間同步，可以保證算法的收斂性和網(wǎng)絡的連通性。2、這兩種算法都缺少嚴格的理論推導，還可以進一步研究合理的鄰居節(jié)點判斷條件。1統(tǒng)一功率分配算法COMPOW2基于節(jié)點度的功率

42、控制LMN/LMA3基于鄰近圖的功率控制功率控制技術功率控制技術 RNG、DRNG和DLSS等基于鄰近圖的近似算法在基于鄰近圖的算法中，所有節(jié)點以最大功率發(fā)射時形成的拓撲圖為圖G，定義為G=(V，E)的形式，V代表圖中頂點的集合，E代表圖中邊的集合，E中的元素可以表示為(u，v)，其中u，vV，按照一定的規(guī)則Q，求出該圖的鄰近圖G，最后G中每個節(jié)點以自己所鄰接的最遠通信節(jié)點來確定發(fā)射功率。經(jīng)典的鄰近圖模型有RNG（Relative Neighborhood Graph）、GG（Gabriel Graph）、YG（Yao Graph）以及MST（Minimum Spanning Tree）等。這

43、是一種解決功率分配問題的近似解法?？紤]到傳感器網(wǎng)絡中兩個節(jié)點形成的邊是有向的，為了避免形成單向邊，一般在運用基于鄰近圖的算法形成網(wǎng)絡拓撲之后，還要進行節(jié)點之間的增刪，以使最后得到的網(wǎng)絡拓撲是雙向連通的。無線傳感器網(wǎng)絡拓撲控制技術典型的層次型拓撲控制方法2.52.1拓撲控制技術概述拓撲控意義2.22.32.4拓撲控制的設計目標功率控制技術拓撲控制中的休眠調(diào)度技術2.6層次型拓撲控制是將所有的傳感器節(jié)點分成一定的簇結構形式。每個簇結構由簇頭節(jié)點負責將簇內(nèi)的數(shù)據(jù)通過其他簇頭路由或直接傳送到匯聚節(jié)點，在簇內(nèi)的普通節(jié)點將感知到的數(shù)據(jù)傳送到簇頭節(jié)點。從而由簇頭節(jié)點形成一個處理并轉發(fā)數(shù)據(jù)的骨干網(wǎng)，其他節(jié)點則

44、可以暫時關閉通信模塊，進入睡眠狀態(tài)以節(jié)省能量。LEACHHEEDGAFTopDisc典型的層次型拓撲控制方法LEACHHEEDGAFTopDisc典型的層次型拓撲控制方法典型的層次型拓撲控制方法LEACH是第一個被提出的聚類路由協(xié)議,也是一種自適應分簇拓撲算法,其基本思想是將節(jié)點組織成簇結構形式,每個簇有一個簇頭節(jié)點,其他節(jié)點作為非簇頭節(jié)點.所有的非簇頭節(jié)點只與本簇的簇頭節(jié)點通信,感知的數(shù)據(jù)由簇頭節(jié)點傳輸?shù)絊ink節(jié)點,簇頭節(jié)點除了傳輸非簇頭節(jié)點的數(shù)據(jù)外,還要執(zhí)行數(shù)據(jù)融合功能.因此，簇頭節(jié)點要比非簇頭節(jié)點消耗更多的能量，LEACH使用輪轉的方式選舉節(jié)點成為簇頭節(jié)點，從而讓所有的節(jié)點都有機會成為

45、簇頭節(jié)點而達到網(wǎng)絡中節(jié)點能量消耗均勻的目的。典型的層次型拓撲控制方法LEACHHEEDGAFTopDisc典型的層次型拓撲控制方法 HEED是一種混合式的分簇算法，通過定義簇內(nèi)平均最小可達功率AMRP指標來衡量簇內(nèi)節(jié)點通信成本。HEED算法首先根據(jù)節(jié)點的剩余能量來概率性地選擇一些候選節(jié)點，以簇內(nèi)通信代價的高低來競爭產(chǎn)生最終簇頭，以簇內(nèi)平均可達能量作為衡量簇內(nèi)通信成本的標準。典型的層次型拓撲控制方法HEED算法將操作時間分為成簇持續(xù)時間TCP和網(wǎng)絡操作時間TNO。在成簇持續(xù)時間內(nèi),每個節(jié)點分布式的通過有限次的迭代選舉出簇頭節(jié)點，節(jié)點在網(wǎng)絡操作時間內(nèi)發(fā)送數(shù)據(jù)到本簇簇頭節(jié)點，簇頭節(jié)點可以選擇一種路由

46、協(xié)議將數(shù)據(jù)經(jīng)過多條路徑經(jīng)由其他簇頭節(jié)點傳送到基站或者匯聚節(jié)點。在簇頭選舉階段，每個節(jié)點以不同的初始概率發(fā)送競爭消息，每次迭代將概率加倍直至為1或有鄰節(jié)點己經(jīng)被選為簇頭。簇頭競選成功后，其他節(jié)點在競爭階段根據(jù)收到的簇頭通告信息選擇加入通信代價AMRP最低的簇頭。典型的層次型拓撲控制方法LEACHHEEDGAFTopDisc典型的層次型拓撲控制方法GAF算法將監(jiān)測區(qū)域劃分成虛擬單元格，將節(jié)點按照位置信息劃入相應的單元格，相鄰單元格的任意兩個節(jié)點可直接通信。GAF節(jié)點有3種狀態(tài): 工作狀態(tài)、睡眠狀態(tài)、發(fā)現(xiàn)狀態(tài)。每個單元格只有一個定期選舉產(chǎn)生的簇頭節(jié)點處于工作狀態(tài)。其他節(jié)點周期性地進入睡眠和發(fā)現(xiàn)狀態(tài)、

47、發(fā)現(xiàn)狀態(tài)的節(jié)點可以競爭簇頭。典型的層次型拓撲控制方法LEACHHEEDGAFTopDisc典型的層次型拓撲控制方法 TopDisc是基于走最小支配集問題的典型算法。在TopDisc算法中，由網(wǎng)絡中的一個初始節(jié)點開始發(fā)送用于發(fā)現(xiàn)鄰居節(jié)點的查詢消息，該消息攜帶有發(fā)送節(jié)點的狀態(tài)信息。隨著查詢消息在整個傳感器網(wǎng)絡中的擴散，算法依次為每個傳感器節(jié)點標記上顏色，即狀態(tài)。 根據(jù)算法中節(jié)點狀態(tài)的個數(shù)，TopDisc包括兩種具體的節(jié)點狀態(tài)標記方法：三色算法和四色算法。優(yōu)缺點：TopDisc算法在密集部署的無線傳感器網(wǎng)絡中執(zhí)行速度快，但形成的網(wǎng)絡拓撲靈活性不強，也沒考慮節(jié)點能耗的均衡問題。無線傳感器網(wǎng)絡拓撲控制技

48、術拓撲控制中的休眠調(diào)度技術2.62.1拓撲控制技術概述拓撲控意義2.22.32.4拓撲控制的設計目標功率控制技術典型的層次型拓撲控制方法2.5拓撲控制中的休眠調(diào)度技術拓撲控制中的休眠調(diào)度技術拓撲控制中的休眠調(diào)度技術能夠使節(jié)點在沒有事件發(fā)生時，設置通信模塊為睡眠狀態(tài)；而在有事件發(fā)生時自動醒來并喚醒鄰居節(jié)點,形成數(shù)據(jù)轉發(fā)的拓撲結構。這種機制的引入,使得無線通信模塊大部分時間都處于關閉狀態(tài),只有傳感器模塊處于工作狀態(tài).此機制有效節(jié)省了能量開銷.此機制重點在于解決節(jié)點在睡眠狀態(tài)和活動狀態(tài)之間的切換，不能獨立成為一種拓撲結構控制機制，需要與其它拓撲控制算法結合使用。拓撲控制中的休眠調(diào)度技術拓撲控制中的休

49、眠調(diào)度技術STEMASCENTCCPSPANSTEM算法包含兩種不同的機制：STEM-B 和STEM-T。STEM算法使節(jié)點在整個生存時間中的多數(shù)時間內(nèi)處于睡眠狀態(tài)，適用于類似環(huán)境監(jiān)測或者突發(fā)事件檢測等應用。ASCENT算法的重點在于均衡網(wǎng)絡中骨干節(jié)點的數(shù)量，并保證數(shù)據(jù)通路的暢通。ASCENT算法本質(zhì)上是一個從匯聚節(jié)點向數(shù)據(jù)源節(jié)點回溯建立路由的過程。通過此算法，節(jié)點能根據(jù)網(wǎng)絡情況動態(tài)地改變自身狀態(tài)，從而動態(tài)地改變網(wǎng)絡拓撲結構。節(jié)點可處于4種狀態(tài)：休眠狀態(tài)、偵聽狀態(tài)、測試狀態(tài)、活動狀態(tài)。用CCP來達到網(wǎng)絡睡眠節(jié)點數(shù)最大化的休眠調(diào)度效果。有3個基本的狀態(tài)：工作狀態(tài)、偵聽狀態(tài)和睡眠狀態(tài)。此外，為了避

50、免由于每個節(jié)點根據(jù)局部信息獨立進行調(diào)度而引起的沖突，CCP引入了加入和退出兩個過渡狀態(tài)。SPAN算法的基本思想是在不破壞網(wǎng)絡原有連通性的前提下，根據(jù)節(jié)點的剩余能量、鄰居節(jié)點的個數(shù)、節(jié)點的效用等多種因素，自適應地決定是成為骨干節(jié)點還是進入睡眠狀態(tài)。睡眠節(jié)點周期性地喚醒，以判斷自己是否應該成為骨干節(jié)點，骨干節(jié)點周期性地判斷自己是否應該退出。路由、覆蓋與拓撲技術無線傳感器網(wǎng)絡覆蓋技術32無線傳感器網(wǎng)絡拓撲控制技術無線傳感器網(wǎng)絡路由1無線傳感器網(wǎng)絡覆蓋技術無線傳感器網(wǎng)絡覆蓋算法設計思路及性能評價標準3.13.2無線傳感器網(wǎng)絡覆蓋感知模型無線傳感器網(wǎng)絡覆蓋算法分類3.33.4典型的無線傳感器網(wǎng)絡覆蓋算法

51、與協(xié)議無線傳感器網(wǎng)絡覆蓋算法設計思路及性能評價標準無線傳感器網(wǎng)絡覆蓋算法設計思路及性能評價標準研究的目的:(1)使待檢測區(qū)域中的每一點都至少在一個傳 感器節(jié)點的覆蓋范圍內(nèi)。(2)在保證覆蓋要求的基礎上，同時減少網(wǎng)絡節(jié)點能量消耗、延長網(wǎng)絡壽命。節(jié)點部署方式網(wǎng)絡節(jié)能傳感與通信距離網(wǎng)絡可擴展無線傳感器網(wǎng)絡節(jié)點部署有兩種,即確定性部署和隨機部署無線傳感器網(wǎng)絡往往節(jié)點硬件平臺資源受限、網(wǎng)絡節(jié)點數(shù)量巨大、實際應用的環(huán)境條件復雜且大多不允許對“失效”節(jié)點進行電池更換。在設計覆蓋算法需要考慮節(jié)點的傳感和通信距離。保證網(wǎng)絡的可擴展性是無線傳感器網(wǎng)絡覆蓋技術的另一項關鍵需求。無線傳感器網(wǎng)絡覆蓋技術無線傳感器網(wǎng)絡覆

52、蓋算法設計思路及性能評價標準3.1無線傳感器網(wǎng)絡覆蓋算法分類3.33.4典型的無線傳感器網(wǎng)絡覆蓋算法與協(xié)議3.2無線傳感器網(wǎng)路覆蓋感知模型無線傳感器網(wǎng)絡覆蓋感知模型節(jié)點的感知范圍是一個以節(jié)點為圓心，以感知距離為半徑的圓形區(qū)域，只有落在該圓形區(qū)域內(nèi)的點才能被該節(jié)點覆蓋，數(shù)學表達式為：此模型簡稱為0-1模型，即當監(jiān)控對象處在節(jié)點的感應區(qū)域時，它被節(jié)點監(jiān)控到的概率恒為1，而當監(jiān)控對象處在感應區(qū)域之外時，它被監(jiān)控到的概率恒為0。布爾感知模型節(jié)點的圓形感知范圍內(nèi)，目標被感知到的概率并不是一個常量，而是由目標到節(jié)點間距離、節(jié)點物理特性等諸多因素決定的變量。、節(jié)點不存在鄰居節(jié)點、節(jié)點存在鄰居節(jié)點概率感知模型

53、節(jié)點i對監(jiān)測區(qū)域內(nèi)目標j的感知概率有如下3種定義形式：由于鄰居節(jié)點的感應區(qū)域與節(jié)點自身的感應區(qū)域存在交疊，所以如果節(jié)點j落在交疊區(qū)域內(nèi)，則節(jié)點j的感知概率會受到鄰居節(jié)點的影響。假設節(jié)點i存在N個鄰居節(jié)點n1，n2，nN，節(jié)點i及鄰居節(jié)點的感知區(qū)域分別記為R(i)，R(n1)，R(n2)，R(nN)，則這些感知區(qū)域的重疊區(qū)域為：假設每個節(jié)點對目標的感知是獨立的，根據(jù)概率計算公式，M中任一節(jié)點j的感知概率計算式：無線傳感器網(wǎng)絡覆蓋技術3.1無線傳感器網(wǎng)絡覆蓋感知模型3.23.4典型的無線傳感器網(wǎng)絡覆蓋算法與協(xié)議3.3無線傳感器網(wǎng)絡覆蓋算法分類無線傳感器網(wǎng)絡覆蓋算法設計思路及性能評價標準無線傳感器網(wǎng)

54、絡覆蓋算法分類按照無線傳感器網(wǎng)絡節(jié)點不同配置方式確定性覆蓋隨機性覆蓋根據(jù)無線傳感器網(wǎng)絡不同覆蓋目標面覆蓋點覆蓋柵欄覆蓋隨機覆蓋考慮在網(wǎng)絡中傳感器節(jié)點隨機分布且預先不知道節(jié)點位置的情況下,網(wǎng)絡完成對檢測區(qū)域的覆蓋任務;（動態(tài)網(wǎng)絡覆蓋則是考慮一些特殊環(huán)境中部分傳感器節(jié)點具備一定運動能力的情況,該網(wǎng)絡可以動態(tài)完成相關覆蓋任務.）確定性區(qū)域/點覆蓋是指傳感器節(jié)點位置已知的無線傳感器網(wǎng)絡要完成目標區(qū)域或目標點的覆蓋。確定性網(wǎng)絡路徑/目標覆蓋還特別考慮了如何對穿越網(wǎng)絡的目標或其經(jīng)過的路徑上各點進行感應與追蹤。無線傳感器網(wǎng)絡覆蓋算法分類按照無線傳感器網(wǎng)絡節(jié)點不同配置方式確定性覆蓋隨機性覆蓋根據(jù)無線傳感器網(wǎng)絡不同覆蓋目標面覆蓋點覆蓋柵欄覆蓋面覆蓋算法的目