無(wú)線傳感網(wǎng)絡(luò)第七章

1、第7章,無(wú)線傳感器網(wǎng)絡(luò)的路由協(xié)議,7.1 路由協(xié)議概述,7.1.1無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議的考慮因素 設(shè)計(jì)無(wú)線傳感器網(wǎng)絡(luò)的路由要考慮的因素很多，大致分為以下兩種類(lèi)型。 (1)網(wǎng)絡(luò)特征：無(wú)線傳感器網(wǎng)絡(luò)具有與眾不同的特征，應(yīng)用于路由協(xié)議設(shè)計(jì)時(shí)，主要應(yīng)該考慮能量損耗、節(jié)點(diǎn)部署和網(wǎng)絡(luò)拓?fù)渥兓?2)數(shù)據(jù)傳輸特征：無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)采集和傳輸要求與其他網(wǎng)絡(luò)不同，因此路由協(xié)議設(shè)計(jì)時(shí)也需要加以區(qū)別，主要考慮數(shù)據(jù)傳輸方式、無(wú)線傳輸手

2、段以及數(shù)據(jù)融合技術(shù)等。,7.1.2路由的過(guò)程,無(wú)線傳感器網(wǎng)絡(luò)的路由過(guò)程主要分為以下4個(gè)步驟： ①某一個(gè)設(shè)備發(fā)出路由請(qǐng)求命令幀，啟動(dòng)路由發(fā)現(xiàn)過(guò)程； ②對(duì)應(yīng)的接收設(shè)備收到該命令后，回復(fù)應(yīng)答命令幀； ③對(duì)潛在的各條路徑開(kāi)銷(xiāo)(跳轉(zhuǎn)次數(shù)、延遲時(shí)間)，進(jìn)行評(píng)估比較； ④將評(píng)估確定之后的最佳路由記錄添加到此路徑上各個(gè)設(shè)備的路由表中。,7.1.3無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議分類(lèi)方法,1．按源節(jié)點(diǎn)獲取路徑的方法主動(dòng)路由

3、協(xié)議、按需路由協(xié)議 、混合路由協(xié)議2．按節(jié)點(diǎn)參與通信的方式直接通信路由協(xié)議、平面路由協(xié)議、層次路由協(xié)議3．按路由的發(fā)現(xiàn)過(guò)程 以位置信息為中心的路由協(xié)議、以數(shù)據(jù)為中心的路由協(xié)議4．按路由選擇是否考慮服務(wù)質(zhì)量(QoS)約束 保證QoS的路由協(xié)議是指在路由建立時(shí)，考慮時(shí)延、丟包率等QoS參數(shù)，從多條可行的路由中選擇一條最適合QoS應(yīng)用要求的路由；或者根據(jù)業(yè)務(wù)類(lèi)型，保證滿足不同業(yè)務(wù)需求的QoS路由協(xié)議。,7.2 平面路由協(xié)議

4、7.2.1 Flooding and Grossing協(xié)議,1. 洪泛路由協(xié)議洪泛路由協(xié)議(Flooding Protocol)是一種最早的路由協(xié)議，接收到消息的節(jié)點(diǎn)以廣播的轉(zhuǎn)發(fā)報(bào)文給所有的鄰居節(jié)點(diǎn)， (如圖7-1,2所示)。,2. 閑聊法閑聊法(Grossing)是洪泛法的改進(jìn)版本。如圖7-3所示,洪泛路由協(xié)議,洪泛路由算法是一個(gè)簡(jiǎn)單有效的路由算法，其基本思想是每個(gè)節(jié)點(diǎn)都是用廣播轉(zhuǎn)發(fā)收到的數(shù)據(jù)分組，若收到重復(fù)分組則進(jìn)行丟

5、棄處理。洪泛協(xié)議會(huì)導(dǎo)致數(shù)據(jù)分組以源節(jié)點(diǎn)為中心進(jìn)行擴(kuò)散，為了不造成大面積的擴(kuò)散占用過(guò)多的網(wǎng)絡(luò)資源以及使擴(kuò)散收斂，需要設(shè)定合適的TTL值（IP包被路由器丟棄之前允許通過(guò)的最大網(wǎng)段數(shù)量），保證數(shù)據(jù)分組只經(jīng)過(guò)有限跳路由；此外為了進(jìn)行重復(fù)分組檢測(cè)，每個(gè)節(jié)點(diǎn)需要維護(hù)一個(gè)數(shù)據(jù)分組序號(hào)SEQ和一張路由表，源節(jié)點(diǎn)每發(fā)送一個(gè)數(shù)據(jù)分組則將SEQ增1，并將該SEQ添加到數(shù)據(jù)分組的IP頭部，其余節(jié)點(diǎn)收到數(shù)據(jù)分組后會(huì)將該SEQ記錄到路由表并根據(jù)該SEQ進(jìn)行重復(fù)分

6、組檢測(cè)。,洪泛路由協(xié)議,洪泛算法最大的問(wèn)題是會(huì)產(chǎn)生大量的重復(fù)分組，占用網(wǎng)絡(luò)資源，使路由器和鏈路的資源過(guò)于浪費(fèi)，以致效率很低。但是洪泛路由算法是一個(gè)最簡(jiǎn)單和最可靠的路由算法，在節(jié)點(diǎn)運(yùn)動(dòng)劇烈、進(jìn)出網(wǎng)絡(luò)頻繁變化的場(chǎng)景下，全網(wǎng)洪泛是有效的方式，其具有極好的健壯性，可用于軍事應(yīng)用，也可以作為衡量標(biāo)準(zhǔn)評(píng)價(jià)其他的路由算法。,Grossing（閑聊）路由協(xié)議,Grossing（閑聊）路由協(xié)議在Flooding協(xié)議的基礎(chǔ)上進(jìn)行了改進(jìn)，節(jié)點(diǎn)對(duì)于產(chǎn)生或收到的

7、數(shù)據(jù)并不是無(wú)條件轉(zhuǎn)發(fā)，而是隨機(jī)轉(zhuǎn)發(fā)，因此在一定程度上解決了Flooding協(xié)議廣播風(fēng)暴的問(wèn)題。但是隨機(jī)轉(zhuǎn)發(fā)數(shù)據(jù)增加了信息傳輸?shù)钠骄鶗r(shí)延，導(dǎo)致傳輸速度變慢，并且無(wú)法解決部分交疊和盲目利用資源問(wèn)題。,7.2.2 SPIN協(xié)議,基于協(xié)商機(jī)制的傳感器網(wǎng)絡(luò)SPIN協(xié)議(Sensor Protocols for Information via Negotiation)是一種以數(shù)據(jù)為中心的白適應(yīng)通信方式，使用3種類(lèi)型的信息進(jìn)行通信，即ADV、REQ和

8、DATA信息。圖7-4表示了SPIN協(xié)議的工作過(guò)程。,SPIN協(xié)議的缺點(diǎn)是沒(méi)有考慮節(jié)能和多種信道條件下的數(shù)據(jù)傳輸問(wèn)題。因此，后續(xù)又出現(xiàn)了SPIN-PP (Point to Point，點(diǎn)到點(diǎn)的通信模式)、SPIN-EC (Energy Control，點(diǎn)到點(diǎn)模式下的節(jié)能路由)、SPIN-RL (Route Lossy，點(diǎn)到點(diǎn)通信中的信道衰減模式)、SPIN-BC (Broadcast Channel，廣播信道模式)等在SPIN基礎(chǔ)上改進(jìn)

9、的路由協(xié)議。,7.2.3 SAR、DD和MCFA協(xié)議,1．SAR協(xié)議順序分配路由SAR協(xié)議(Sequential Assignment Routing)是第一個(gè)具有QoS意識(shí)的路由協(xié)議。該協(xié)議通過(guò)構(gòu)建以Sink的單跳鄰居節(jié)點(diǎn)為根節(jié)點(diǎn)的多播樹(shù)來(lái)實(shí)現(xiàn)傳感器節(jié)點(diǎn)到Sink節(jié)點(diǎn)的多跳路徑。2．DD協(xié)議定向擴(kuò)散路由DD協(xié)議(Directed Diffusion)是一種以數(shù)據(jù)為中心的信息傳播協(xié)議，與已有的路由算法有著截然不同的實(shí)現(xiàn)機(jī)制

10、。3．MCFA協(xié)議 最小開(kāi)銷(xiāo)前行算法MCFA協(xié)議(Minimum Cost For warding Algorithm for Large Sensor Networks)充分利用了傳感器網(wǎng)絡(luò)中的數(shù)據(jù)傳輸不對(duì)稱(chēng)的特點(diǎn)，即大多的數(shù)據(jù)流都是從傳感器節(jié)點(diǎn)向Sink節(jié)點(diǎn)的方向傳輸。,7.2.3 SAR、DD和MCFA協(xié)議,1．SAR協(xié)議順序分配路由SAR協(xié)議(Sequential Assignment Routing)是

11、第一個(gè)具有QoS意識(shí)的路由協(xié)議。該協(xié)議通過(guò)構(gòu)建以Sink的單跳鄰居節(jié)點(diǎn)為根節(jié)點(diǎn)的多播樹(shù)來(lái)實(shí)現(xiàn)傳感器節(jié)點(diǎn)到Sink節(jié)點(diǎn)的多跳路徑。2．DD協(xié)議定向擴(kuò)散路由DD協(xié)議(Directed Diffusion)是一種以數(shù)據(jù)為中心的信息傳播協(xié)議，與已有的路由算法有著截然不同的實(shí)現(xiàn)機(jī)制。3．MCFA協(xié)議 最小開(kāi)銷(xiāo)前行算法MCFA協(xié)議(Minimum Cost For warding Algorithm for Large S

12、ensor Networks)充分利用了傳感器網(wǎng)絡(luò)中的數(shù)據(jù)傳輸不對(duì)稱(chēng)的特點(diǎn)，即大多的數(shù)據(jù)流都是從傳感器節(jié)點(diǎn)向Sink節(jié)點(diǎn)的方向傳輸。,7.3 層次路由協(xié)議,7.3.1 LEACH 低功耗自適應(yīng)聚類(lèi)分級(jí)LEACH協(xié)議(LOW Energy Adaptive Clustering Hierarchy)是無(wú)線傳感器網(wǎng)絡(luò)中最早提出的分層路由算法。LEACH可以將網(wǎng)絡(luò)整體生存時(shí)間延長(zhǎng)15％，其基本思想是通過(guò)隨機(jī)循環(huán)地選擇簇頭節(jié)點(diǎn)將整個(gè)網(wǎng)

13、絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)中，從而降低網(wǎng)絡(luò)能源消耗，提高網(wǎng)絡(luò)整體生存時(shí)間。,7.3 層次路由協(xié)議,LEACH在運(yùn)行過(guò)程中不斷的循環(huán)執(zhí)行簇的重構(gòu)過(guò)程，每個(gè)簇重構(gòu)過(guò)程可以用回合的概念來(lái)描述。每個(gè)回合可以分成兩個(gè)階段：簇的建立階段和傳輸數(shù)據(jù)的穩(wěn)定階段。為了節(jié)省資源開(kāi)銷(xiāo)，穩(wěn)定階段的持續(xù)時(shí)間要大于建立階段的持續(xù)時(shí)間。簇的建立過(guò)程可分成4個(gè)階段：簇頭節(jié)點(diǎn)的選擇、簇頭節(jié)點(diǎn)的廣播、簇頭節(jié)點(diǎn)的建立和調(diào)度機(jī)制的生成。簇頭節(jié)點(diǎn)的選擇依據(jù)網(wǎng)絡(luò)中所需

14、要的簇頭節(jié)點(diǎn)總數(shù)和迄今為止每個(gè)節(jié)點(diǎn)已成為簇頭節(jié)點(diǎn)的次數(shù)來(lái)決定。具體的選擇辦法是：每個(gè)傳感器節(jié)點(diǎn)隨機(jī)選擇0-1之間的一個(gè)值。如果選定的值小于某一個(gè)閾值，那么這個(gè)節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)。選定簇頭節(jié)點(diǎn)后，通過(guò)廣播告知整個(gè)網(wǎng)絡(luò)。網(wǎng)絡(luò)中的其他節(jié)點(diǎn)根據(jù)接收信息的信號(hào)強(qiáng)度決定從屬的簇，并通知相應(yīng)的簇頭節(jié)點(diǎn)，完成簇的建立。最后，簇頭節(jié)點(diǎn)采用TDMA方式為簇中每個(gè)節(jié)點(diǎn)分配向其傳遞數(shù)據(jù)的時(shí)間點(diǎn)。穩(wěn)定階段中，傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)傳送到簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)對(duì)簇中

15、所有節(jié)點(diǎn)所采集的數(shù)據(jù)進(jìn)行信息融合后再傳送給匯聚節(jié)點(diǎn)，這是一種較少通信業(yè)務(wù)量的合理工作模型。穩(wěn)定階段持續(xù)一段時(shí)間后，網(wǎng)絡(luò)重新進(jìn)入簇的建立階段，進(jìn)行下一回合的簇重構(gòu)，不斷循環(huán)，每個(gè)簇采用不同的CDMA代碼進(jìn)行通信來(lái)減少其他簇內(nèi)節(jié)點(diǎn)的干擾。,LEACH協(xié)議特點(diǎn),1 為了減少傳送到匯聚節(jié)點(diǎn)的信息數(shù)量，簇首節(jié)點(diǎn)負(fù)責(zé)融合來(lái)自簇內(nèi)不同源節(jié)點(diǎn)所產(chǎn)生的數(shù)據(jù)，并將融合后的數(shù)據(jù)發(fā)送到匯聚點(diǎn)。2 LEACH采用基于TDMA/CDMA的MAC層機(jī)制來(lái)減少簇內(nèi)和

16、簇間的沖突。3 由于數(shù)據(jù)采集是集中的和周期性的，因此該協(xié)議非常適合于要求連續(xù)監(jiān)控的應(yīng)用系統(tǒng)。4 對(duì)于終端使用者來(lái)說(shuō)，由于它并不需要立即得到所有的數(shù)據(jù)，因此協(xié)議不需要周期性的傳輸數(shù)據(jù)，這樣可以達(dá)到限制傳感器節(jié)點(diǎn)能量消耗的目的。5 在給定的時(shí)間間隔后，協(xié)議重新選舉簇首節(jié)點(diǎn)，以保證無(wú)線傳感器網(wǎng)絡(luò)獲取統(tǒng)一的能量分布。,LEACH局限性,1 由于LEACH假定所有節(jié)點(diǎn)能夠與匯聚節(jié)點(diǎn)直接通信，并且每個(gè)節(jié)點(diǎn)都具備支持不同MAC協(xié)議的計(jì)算能力，因

17、此該協(xié)議不適合在大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)中應(yīng)用。2 協(xié)議沒(méi)有說(shuō)明簇頭節(jié)點(diǎn)的數(shù)目怎么分布才能及于整個(gè)網(wǎng)絡(luò)。因此，很可能出現(xiàn)被選的簇頭節(jié)點(diǎn)集中在網(wǎng)絡(luò)某一區(qū)域的現(xiàn)象，這樣就會(huì)使得一些節(jié)點(diǎn)的周?chē)鷽](méi)有任何簇頭節(jié)點(diǎn)。3 由于LEACH假定在最初的簇頭選擇回合中，所有的節(jié)點(diǎn)都攜帶相同的能量，并且每個(gè)成為簇頭的節(jié)點(diǎn)都消耗大致相同的能量。因此，協(xié)議不適合節(jié)點(diǎn)能量不均衡的網(wǎng)絡(luò)。,7.3.2 PEGASIS,高能效采集傳感器信息系統(tǒng)PEGASIS協(xié)議(Po

18、wer　Efficient Gathering in Sensor Information Systems)是在LEACH協(xié)議上提出的一種改進(jìn)路由算法。PEGASIS路由協(xié)議在網(wǎng)絡(luò)中選擇一個(gè)節(jié)點(diǎn)作為起始節(jié)點(diǎn)建立一條最優(yōu)回路鏈，起始節(jié)點(diǎn)將數(shù)據(jù)融合后的數(shù)據(jù)信息發(fā)送給Sink節(jié)點(diǎn)。由于起始節(jié)點(diǎn)的負(fù)載較重，PEGASIS采用了全網(wǎng)節(jié)點(diǎn)輪流作為回路鏈起始節(jié)點(diǎn)的方式來(lái)進(jìn)行均衡。 該路由協(xié)議中使用了貪婪算法(Greedy Algorit

19、hm)來(lái)形成鏈，如圖7-5所示。在每一輪通信之前才形成鏈。為確保每個(gè)節(jié)點(diǎn)都有其相鄰節(jié)點(diǎn)，從離基站最遠(yuǎn)的節(jié)點(diǎn)開(kāi)始構(gòu)建，鏈中鄰居節(jié)點(diǎn)的距離會(huì)逐漸增大，因?yàn)橐呀?jīng)在鏈中的節(jié)點(diǎn)不能被再次訪，當(dāng)其中一個(gè)節(jié)點(diǎn)失效時(shí)，鏈必須重構(gòu)。,7.3.3 TEEN,閾值敏感的高效傳感器網(wǎng)絡(luò)TEEN協(xié)議(Threshold Sensitive Energy Efficient Sensor Network)，是一個(gè)基于簇群的路由協(xié)議，也是由LEACH發(fā)展而來(lái)，在這個(gè)

20、協(xié)議中定義了硬門(mén)限和軟門(mén)限兩個(gè)概念。 這個(gè)算法適用于實(shí)時(shí)性要求較高的應(yīng)用場(chǎng)合，用戶可以及時(shí)獲取感興趣的信息。由于感應(yīng)數(shù)據(jù)所耗能量比傳輸數(shù)據(jù)所耗能量要少得多，雖然節(jié)點(diǎn)一直處于感應(yīng)狀態(tài)，但是由于減少了很多不必要的數(shù)據(jù)傳輸，因此相對(duì)來(lái)說(shuō)還是節(jié)能的。該協(xié)議也有一些不足之處： ①門(mén)限值達(dá)不到，節(jié)點(diǎn)就永遠(yuǎn)不會(huì)和簇頭節(jié)點(diǎn)通信，用戶就無(wú)法從網(wǎng)絡(luò)得到任何數(shù)據(jù)，即使節(jié)點(diǎn)已經(jīng)死亡，用戶也不知情； ②TDMA機(jī)制的運(yùn)用保證了群

21、中不會(huì)出現(xiàn)數(shù)據(jù)沖撞的情況，但是如果一個(gè)節(jié)點(diǎn)沒(méi)有數(shù)據(jù)要發(fā)送的話，屬于它的時(shí)隙就浪費(fèi)掉了，而其他節(jié)點(diǎn)卻還在等待自己的時(shí)隙，這樣會(huì)向系統(tǒng)中引入過(guò)多的時(shí)延，不適于實(shí)時(shí)性要求太高的場(chǎng)合； ③沒(méi)有相應(yīng)的機(jī)制去區(qū)分那些沒(méi)有感應(yīng)到足夠大變化的節(jié)點(diǎn)和處于關(guān)閉狀態(tài)的節(jié)點(diǎn)。群頭節(jié)點(diǎn)的接收機(jī)要時(shí)刻處于激活狀態(tài)，以便接收任何時(shí)候由成員節(jié)點(diǎn)傳來(lái)的數(shù)據(jù)，在某種程度上增加了簇頭節(jié)點(diǎn)的負(fù)擔(dān)。,7.3.4 APTEEN、TTDD和EARSN協(xié)議,1．APTEEN

22、APTEEN (Adaptive Periodic TEEN)協(xié)議是對(duì)TEEN的擴(kuò)展，它是一種結(jié)合響應(yīng)型和主動(dòng)型傳感器網(wǎng)絡(luò)策略的混合型網(wǎng)絡(luò)路由協(xié)議，可以根據(jù)用戶需要和應(yīng)用類(lèi)型來(lái)設(shè)定協(xié)議的周期性和相關(guān)閥值，即可以周期性采集數(shù)據(jù)又可以對(duì)突發(fā)事件作出快速反應(yīng)。APTEEN在TEEN的基礎(chǔ)上定義了一個(gè)計(jì)數(shù)時(shí)間，當(dāng)節(jié)點(diǎn)從上一次發(fā)送數(shù)據(jù)開(kāi)始經(jīng)歷這個(gè)計(jì)數(shù)時(shí)間還沒(méi)有發(fā)送數(shù)據(jù)，那么不管當(dāng)前的數(shù)據(jù)是否滿足軟、硬門(mén)限的要求都會(huì)發(fā)送這個(gè)數(shù)據(jù)。APTEEN

23、可以通過(guò)改變計(jì)數(shù)時(shí)間來(lái)控制能量消耗。,2．TTDD 雙列數(shù)據(jù)分發(fā)TTDD(TWO-Tier Data Dissemination)，協(xié)議假設(shè)節(jié)點(diǎn)靜態(tài)，且各節(jié)點(diǎn)的位置信息已知。網(wǎng)絡(luò)中可以存在多個(gè)Sink節(jié)點(diǎn)，Sink節(jié)點(diǎn)可以在網(wǎng)絡(luò)中任意移動(dòng)。網(wǎng)絡(luò)中的節(jié)點(diǎn)以虛擬柵格的形式劃分為若干區(qū)域，當(dāng)監(jiān)測(cè)區(qū)域發(fā)生事件，附近的多個(gè)節(jié)點(diǎn)將選擇一個(gè)節(jié)點(diǎn)觸發(fā)數(shù)據(jù)上報(bào)消息。發(fā)送數(shù)據(jù)上報(bào)消息的簇頭節(jié)點(diǎn)將上報(bào)報(bào)文發(fā)送給柵格外的其他4個(gè)柵格的鄰接節(jié)點(diǎn)，由鄰接

24、節(jié)點(diǎn)轉(zhuǎn)發(fā)給該柵格的另外3個(gè)鄰接節(jié)點(diǎn)，最后將上報(bào)的數(shù)據(jù)報(bào)文發(fā)送到每一個(gè)柵格。這樣無(wú)論Sink節(jié)點(diǎn)移動(dòng)到網(wǎng)絡(luò)中的任何地方，都能夠從距離最近的節(jié)點(diǎn)上收到上報(bào)的數(shù)據(jù)報(bào)文。,7.3.4 APTEEN、TTDD和EARSN協(xié)議,3．EARSN 簇頭固定的分簇結(jié)構(gòu)路由協(xié)議EARSN (Energy Aware Routing for Cluster Based Sensor Network)是基于三層體系結(jié)構(gòu)的路由協(xié)議。該協(xié)議要求網(wǎng)絡(luò)運(yùn)行前

25、由終端用戶將傳感器節(jié)點(diǎn)劃分成簇，并通知每個(gè)簇頭節(jié)點(diǎn)的ID標(biāo)識(shí)和簇內(nèi)所分配節(jié)點(diǎn)的位置信息。傳感器節(jié)點(diǎn)可以以活動(dòng)方式和備用的低能源方式兩種方式運(yùn)行，并可以感知、轉(zhuǎn)發(fā)、感知并轉(zhuǎn)發(fā)和休眠4種方式之一存在。與其他路由協(xié)議不同的是，該協(xié)議的簇頭不受能量的限制。它作為網(wǎng)絡(luò)的中心管理者，可以監(jiān)控節(jié)點(diǎn)的能量變化，決定并維護(hù)傳感器的4種狀態(tài)。算法依據(jù)兩個(gè)節(jié)點(diǎn)間的能量消耗、延遲最優(yōu)化等性能指標(biāo)計(jì)算路徑代價(jià)函數(shù)。簇頭節(jié)點(diǎn)利用代價(jià)函數(shù)作為鏈路成本，選擇最小成本的

26、路徑作為節(jié)點(diǎn)與其通信的最優(yōu)路徑。經(jīng)仿真分析，該協(xié)議在運(yùn)行過(guò)程中具有很好的節(jié)能性、較高的吞吐量和較低的通信延遲。,7.3.4 APTEEN、TTDD和EARSN協(xié)議,表7-1為各種協(xié)議之間的簡(jiǎn)單對(duì)比，主要從移動(dòng)性、能量需求、路徑長(zhǎng)度、擴(kuò)展性、路由狀態(tài)復(fù)雜度、計(jì)算和通信所需開(kāi)銷(xiāo)、數(shù)據(jù)融合技術(shù)等多方面進(jìn)行了分析比較。,7.3.5 平面路由協(xié)議和層次路由協(xié)議比較,總體來(lái)看，由于網(wǎng)絡(luò)結(jié)構(gòu)的不同，平面路由和層次路由體現(xiàn)出了以下幾處差異。 ①

27、移動(dòng)性 ②能量使用 ③路由選擇 ④可拓展性 ⑤開(kāi)銷(xiāo),7.3.5 平面路由協(xié)議和層次路由協(xié)議比較,7.4 能量感知路由,7.4.1 能量消耗源 1．通信相關(guān)的能量消耗 通信相關(guān)的能耗包括對(duì)傳輸器、中轉(zhuǎn)器和接收器的使用。 2．計(jì)算相關(guān)的能量消耗 計(jì)算相關(guān)的能耗主要涉及協(xié)議的處理，主要包括對(duì)CPU、主要存儲(chǔ)器、一個(gè)很小的外設(shè)、磁盤(pán)或其他一些組成部分的使用。同樣的，數(shù)

28、據(jù)壓縮技術(shù)在減少數(shù)據(jù)包長(zhǎng)度的同時(shí)也因?yàn)橛?jì)算量的增大而增加了能量消耗。,7.4.2能量路由,在如圖7-6所示的網(wǎng)絡(luò)中，源節(jié)點(diǎn)是一般功能的傳感器節(jié)點(diǎn)，完成數(shù)據(jù)采集工作。匯聚節(jié)點(diǎn)是數(shù)據(jù)發(fā)送的目標(biāo)節(jié)點(diǎn)。大寫(xiě)字母表示節(jié)點(diǎn)，如節(jié)點(diǎn)A，節(jié)點(diǎn)右側(cè)括號(hào)內(nèi)的數(shù)字表示節(jié)點(diǎn)的可用能量。圖中的雙向線表示節(jié)點(diǎn)之間的通信鏈路，鏈路上的數(shù)字表示在該鏈路上發(fā)送數(shù)據(jù)消耗的能量。在圖中，從源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的可能路徑有4條。,,路徑1：源節(jié)點(diǎn)—B—A—匯聚節(jié)點(diǎn)，路徑上所有節(jié)

29、點(diǎn)PA之和為4，在該路徑上發(fā)送分組需要的能量之和為3； 路徑2：源節(jié)點(diǎn)—C—B—A—匯聚節(jié)點(diǎn)，路徑上所有節(jié)點(diǎn)PA之和為6，在該路徑上發(fā)送分組需要的能量之和為6； 路徑3：源節(jié)點(diǎn)—D—匯聚節(jié)點(diǎn)，路徑上所有節(jié)點(diǎn)PA之和為3，在該路上發(fā)送分組需要的能量之和為4； 路徑4：源節(jié)點(diǎn)—F—E—匯聚節(jié)點(diǎn)，路徑上所有節(jié)點(diǎn)PA之和為5，在該路徑上發(fā)送分組需要的能量之和為6。 能量路由選擇策略主要有以下幾種：最大可用能量路由

30、、最小能量消耗路由、最少跳數(shù)路由和最大最小PA節(jié)點(diǎn)路由。,7.4.3能量多路徑路由,能量多路徑路由的主要流程描述如下： (1)發(fā)起路徑建立 (2)判斷是否轉(zhuǎn)發(fā)路徑建立消息 (3)計(jì)算能量代價(jià) (4)節(jié)點(diǎn)加入路徑條件 (5)節(jié)點(diǎn)選擇概率計(jì)算 (6)代價(jià)平均值計(jì)算,7.5基于查詢的路由,基于查詢的路由協(xié)議，在需要不斷查詢傳感器節(jié)點(diǎn)采集的數(shù)據(jù)

31、的應(yīng)用中，通信流量主要產(chǎn)生于查詢節(jié)點(diǎn)和傳感器節(jié)點(diǎn)之間的命令和數(shù)據(jù)傳輸，同時(shí)傳感器節(jié)點(diǎn)的采樣信息在傳輸路徑上通常要進(jìn)行數(shù)據(jù)融合，通過(guò)減少通信流量來(lái)節(jié)省能量。,7.5.1定向擴(kuò)散路由,定向擴(kuò)散(Directed Diffusion，DD)是一種基于查詢的路由機(jī)制，是專(zhuān)門(mén)為無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)的。 定向擴(kuò)散路由機(jī)制包括周期性的興趣擴(kuò)散、梯度建立、數(shù)據(jù)傳播、路徑加強(qiáng)等階段 。 1．興趣擴(kuò)散階段 2．梯度建立階段

32、 3．?dāng)?shù)據(jù)傳播階段 4．路徑加強(qiáng)階段,DD路由算法,該算法實(shí)現(xiàn)的過(guò)程包括三個(gè)階段：興趣擴(kuò)散，梯度建立以及路徑加強(qiáng) 。　　興趣擴(kuò)散：Sink節(jié)點(diǎn)查詢興趣消息，興趣消息采用泛洪的方法傳播到網(wǎng)絡(luò)，來(lái)通知整個(gè)網(wǎng)絡(luò)中的其他節(jié)點(diǎn)它需要的信息。 　　梯度建立：在興趣消息擴(kuò)散的同時(shí)相應(yīng)的路由路經(jīng)也建立完成。有“興趣消息”相關(guān)數(shù)據(jù)的普通節(jié)點(diǎn)將自己采集的數(shù)據(jù)通過(guò)建立好的路徑傳送到Sink節(jié)點(diǎn)。 

33、　　路徑加強(qiáng)：最后sink節(jié)點(diǎn)選擇一條最優(yōu)路徑作為強(qiáng)化路徑。優(yōu)點(diǎn)： 　　數(shù)據(jù)中心路由，定義不同任務(wù)類(lèi)型/目標(biāo)區(qū)域消息； 　　路徑加強(qiáng)機(jī)制可顯著提高數(shù)據(jù)傳輸?shù)乃俾剩?#160;　　周期性路由：能量的均衡消耗； 缺點(diǎn)： 　　周期性的洪泛機(jī)制---能量和時(shí)間開(kāi)銷(xiāo)都比較大； 　　節(jié)點(diǎn)需要維護(hù)一個(gè)興趣消息列表，代價(jià)較大； 　　不能用于大規(guī)模的網(wǎng)絡(luò)以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷變化的

34、網(wǎng)絡(luò)。,7.5.2謠傳路由,謠傳路由(Rumor Routing)，其路由的建立是由Sink節(jié)點(diǎn)和源節(jié)點(diǎn)共同發(fā)起并完成的。謠傳路由的原理如圖7-8所示。,謠傳路由協(xié)議的執(zhí)行過(guò)程如下： ①每個(gè)傳感器節(jié)點(diǎn)維護(hù)一個(gè)鄰居列表和一個(gè)事件列表。 ②當(dāng)傳感器節(jié)點(diǎn)在本地檢測(cè)到一個(gè)事件時(shí)，就在事件列表中增加一個(gè)表項(xiàng)，設(shè)置相關(guān)的事件名稱(chēng)、跳數(shù)等，同時(shí)根據(jù)一定的概率產(chǎn)生一個(gè)代理消息。代理消息是一個(gè)包含生命期等事件信息的分組，用來(lái)攜帶相關(guān)的信息

35、通告給它傳輸經(jīng)過(guò)的每一個(gè)傳感器節(jié)點(diǎn)。,③網(wǎng)絡(luò)的任何節(jié)點(diǎn)都可以對(duì)一個(gè)特定的事件生成查詢消息。 ④若查詢消息和代理消息的路徑出現(xiàn)交叉的情況，交叉節(jié)點(diǎn)會(huì)沿著查詢消息的反方向?qū)⑹录畔魉偷讲樵児?jié)點(diǎn)。如果查詢節(jié)點(diǎn)在一段時(shí)間內(nèi)沒(méi)有收到事件消息，就認(rèn)為查詢消息并沒(méi)有到達(dá)事件區(qū)域，可以選擇重傳、放棄或洪泛查詢,7.6地理位置路由7.6.1 GEAR路由,1.GEAR路由的基本思想GEAR采用查詢驅(qū)動(dòng)數(shù)據(jù)傳送模式，根據(jù)事件區(qū)域的地理位置

36、信息，建立基站或者匯聚節(jié)點(diǎn)到事件區(qū)域的優(yōu)化路徑。,2.GEAR中查詢消息的傳播 (1) 查詢消息傳送到事件區(qū)域 GEAR路由用實(shí)際代價(jià)(1earned cost)和估計(jì)代價(jià)(estimated cost)兩種代價(jià)值來(lái)表示路徑代價(jià)。GEAR通過(guò)如圖7-9所示的方式來(lái)解決通信空洞問(wèn)題，從而使路由進(jìn)行下去。,(2) 查詢消息在事件區(qū)域內(nèi)傳播當(dāng)查詢命令被轉(zhuǎn)發(fā)進(jìn)入事件區(qū)域后，大多數(shù)情況下采用遞歸的、基于地理信息的轉(zhuǎn)發(fā)方式在事件區(qū)域

37、內(nèi)發(fā)布查詢命令。如圖7-10所示。,,2.GEAR中查詢消息的傳播,(3)GEAR路由的性能 GEAR路由定義估計(jì)路由代價(jià)為節(jié)點(diǎn)到事件區(qū)域的距離和節(jié)點(diǎn)剩余能量，并利用捎帶機(jī)制獲取實(shí)際路由代價(jià)，進(jìn)行數(shù)據(jù)傳輸?shù)穆窂絻?yōu)化，從而形成能量高效的數(shù)據(jù)傳輸路徑。GEAR路由采用的貪婪算法是一個(gè)局部最優(yōu)的算法，適合無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)只知道局部拓?fù)湫畔⒌那闆r，其缺點(diǎn)是由于缺乏足夠的拓?fù)湫畔?，路由過(guò)程中可能遇到路由空洞，反而降低了路由效率。,7

38、.6.2 GAF路由,地域自適應(yīng)保真算法GAF (Geographic Adaptive Fidelity)是基于有限能量和位置信息的路由算法，,GAF算法的執(zhí)行過(guò)程包括兩個(gè)階段。 第一階段是虛擬網(wǎng)格的劃分。根據(jù)節(jié)點(diǎn)的位置信息和通信半徑，將網(wǎng)絡(luò)區(qū)域劃分成若二干虛擬網(wǎng)格，保證相鄰單元格中的任意兩個(gè)節(jié)點(diǎn)都能夠直接通信。假設(shè)節(jié)點(diǎn)已知整個(gè)監(jiān)測(cè)區(qū)域的位置信息和本身的位置信息，節(jié)點(diǎn)可以通過(guò)計(jì)算得知自己屬于哪個(gè)網(wǎng)格。 第二階段是虛擬網(wǎng)

39、格中簇頭節(jié)點(diǎn)的選擇。節(jié)點(diǎn)周期性地進(jìn)入睡眠和工作狀態(tài)，從睡眠狀態(tài)喚醒之后與本單元其他節(jié)點(diǎn)交換信息，以確定自己是否需要成為簇頭節(jié)點(diǎn)。,每個(gè)節(jié)點(diǎn)處于發(fā)現(xiàn)(discovery)、活動(dòng)(active)以及睡眠(sleeping)3種狀態(tài)，如圖7-13所示。,7.6.3 GPSR路由,GPSR (Greedy Perimeter Stateless Routing)路由協(xié)議是貪婪算法(Greedy)和圖形算法的結(jié)合，它不需要維護(hù)路由表，是一種無(wú)狀態(tài)

40、的路由協(xié)議。 GPSR協(xié)議具有貪婪轉(zhuǎn)發(fā)((Greedy Forwarding)和周界轉(zhuǎn)發(fā)(Perimeters Forwarding)兩種分組轉(zhuǎn)發(fā)方式。1. 貪婪轉(zhuǎn)發(fā)算法 貪婪轉(zhuǎn)發(fā)算法是一種基于地理信息的路由算法。貪婪轉(zhuǎn)發(fā)算法的前提是每個(gè)分組都已包含其目的節(jié)點(diǎn)位置或目標(biāo)區(qū)域位置，每個(gè)節(jié)點(diǎn)都已知自己及自接鄰節(jié)點(diǎn)的位置。 貪婪轉(zhuǎn)發(fā)算法總是朝距離目的節(jié)點(diǎn)最近的鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)分組，如圖7-14所示。,2．周界轉(zhuǎn)發(fā)

41、 如圖7-15所示，采用周界轉(zhuǎn)發(fā)方式時(shí)，通常采用右手規(guī)則確定轉(zhuǎn)發(fā)的路徑。,,7.6.3 GPSR路由,圖7-16給出了右手規(guī)則的基本原理。當(dāng)一個(gè)數(shù)據(jù)分組從節(jié)點(diǎn)x到達(dá)節(jié)點(diǎn)y時(shí)，它經(jīng)過(guò)下一邊時(shí)以y為頂點(diǎn)，沿(y,x)逆時(shí)針?lè)较蛏系牡谝粭l鏈路，如圖所示的為(y,z)，后續(xù)的同樣依照此規(guī)則來(lái)確定，直到數(shù)據(jù)到達(dá)目的節(jié)點(diǎn)為止。 GPSR路由協(xié)議同時(shí)采用了貪婪算法和周界轉(zhuǎn)發(fā)來(lái)對(duì)數(shù)據(jù)分組進(jìn)行傳送。在完整的拓?fù)鋱D中采用貪婪轉(zhuǎn)發(fā)，當(dāng)貪婪轉(zhuǎn)

42、發(fā)找不到下一跳節(jié)點(diǎn)時(shí)，則在平面圖中采用周界轉(zhuǎn)發(fā)決定數(shù)據(jù)分組的下一跳。,7.6.4 GEM和MECN路由,1．GEM路由 GEM (Graph Embedding)路由協(xié)議是一種適用于數(shù)據(jù)中心存儲(chǔ)(Data Centric Storage)方式的基于位置的路由協(xié)議。其基本思想是建立一個(gè)虛擬極坐標(biāo)系統(tǒng)，用來(lái)表示實(shí)際的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。,2.MECN路由 MECN (Minimum Energy Communication N

43、etwork)和SMECN (Small MECN) 協(xié)議的主要思想是構(gòu)建子網(wǎng)，每個(gè)子網(wǎng)有一個(gè)主站(Master Site)，相當(dāng)于層次路由中的簇頭節(jié)點(diǎn)，要求子網(wǎng)內(nèi)部所含節(jié)點(diǎn)數(shù)目少并且任意兩個(gè)節(jié)點(diǎn)之間傳輸數(shù)據(jù)都消耗更少的能量。,MECN的實(shí)現(xiàn)分兩個(gè)階段完成。 (1)第一階段：獲取位置信息，由節(jié)點(diǎn)內(nèi)部的計(jì)算來(lái)構(gòu)建包含所有發(fā)送節(jié)點(diǎn)外圍的外圍圖； (2)第二階段：在外圍圖中搜索最優(yōu)路徑，采用以能量消耗作為度量代價(jià)的分布式最短路

44、徑算法來(lái)實(shí)現(xiàn)。,7.7 可靠路由協(xié)議7.7.1不相交多路徑路由機(jī)制,不相交多路徑的建立過(guò)程如圖7-17所示，其基本思想是：首先由匯聚節(jié)點(diǎn)發(fā)出主路徑增強(qiáng)消息，建立一條由匯聚節(jié)點(diǎn)到源節(jié)點(diǎn)的主路徑P，如圖7-17(a)所示；然后進(jìn)行備用路徑的建立。匯聚節(jié)點(diǎn)向其次優(yōu)節(jié)點(diǎn)A發(fā)出次優(yōu)路徑增強(qiáng)消息，節(jié)點(diǎn)A再將該消息發(fā)給自己的最優(yōu)節(jié)點(diǎn)B。,纏繞多路徑的建立如圖7-18所示。理想的纏繞多路徑由一組纏繞路徑構(gòu)成，如圖7-18(a)所示，在主路徑上的每個(gè)節(jié)

45、點(diǎn)都能找到一條不包括本身的從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最優(yōu)路徑(實(shí)際上是次優(yōu)路徑)。而局部纏繞多路徑則是經(jīng)過(guò)運(yùn)算后有可能在某些主路徑的節(jié)點(diǎn)處找不到能繞過(guò)該節(jié)點(diǎn)的理想路徑，如圖7-18(b)所示。,纏繞多路徑可以克服主路徑E單個(gè)節(jié)點(diǎn)失敗的問(wèn)題。 纏繞多路徑的建立如圖7-18所示。理想的纏繞多路徑由一組纏繞路徑構(gòu)成，如圖7-18(a)所示，在主路徑上的每個(gè)節(jié)點(diǎn)都能找到一條不包括本身的從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最優(yōu)路徑(實(shí)際上是次優(yōu)路徑)。而局部纏繞多路

46、徑則是經(jīng)過(guò)運(yùn)算后有可能在某些主路徑的節(jié)點(diǎn)處找不到能繞過(guò)該節(jié)點(diǎn)的理想路徑，如圖7-18(b)所示。,,7.7.1不相交多路徑路由機(jī)制,7.7.2 ReInForM路由,可靠多路徑信息轉(zhuǎn)發(fā)ReInForM (Reliable Information Forwarding using Multiple paths)路由在數(shù)據(jù)傳輸方面從數(shù)據(jù)源節(jié)點(diǎn)開(kāi)始，把監(jiān)測(cè)數(shù)據(jù)發(fā)送給匯聚節(jié)點(diǎn)，考慮信道質(zhì)量以及傳感器節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的跳數(shù)，決定需要的傳輸路徑數(shù)目，

47、以及下一跳節(jié)點(diǎn)數(shù)目和相應(yīng)的節(jié)點(diǎn)，具有滿足可靠性要求的優(yōu)點(diǎn)。ReInForM路由考慮不同的傳輸可靠性要求，選擇最優(yōu)的路徑進(jìn)行數(shù)據(jù)傳輸。 ReInForM路由的形成主要包括3個(gè)步驟： 1、計(jì)算傳輸路徑數(shù)； 2、下一跳節(jié)點(diǎn)選擇和路徑分配； 3、鄰居節(jié)點(diǎn)重新計(jì)算路徑。,7.7.3 SPEED協(xié)議,SPEED協(xié)議首先在相鄰節(jié)點(diǎn)之間交換傳輸延遲，以得到網(wǎng)絡(luò)負(fù)載情況然后節(jié)點(diǎn)利用局部地理信息和傳輸速

48、率信息選擇下一跳的節(jié)點(diǎn)。同時(shí)通過(guò)鄰居反饋機(jī)制保證網(wǎng)絡(luò)傳輸暢通，并且通過(guò)反向壓力路由變更機(jī)制避開(kāi)延遲太大的鏈路和路由空洞。,包括7部分：SPEED接口(SPEED API)、鄰居信標(biāo)交換(Neighborhood Beacon Exchange)、延遲估計(jì)(Delay Estimation Scheme)、無(wú)狀態(tài)的非確定的地理轉(zhuǎn)發(fā)算法(Stateless Non Deterministic Geographic Forwarding，SN

49、GF)、鄰居反饋策略(Neighborhood Feedback Loop，NFL)、反向壓力重路由(Backpressure Rerouting)和最后一跳的處理(Last mile processing)，各部分之間的關(guān)系如圖7-19所示。,7.8路由協(xié)議自主切換,一個(gè)路由服務(wù)的通信模型如圖7-20所示。,,南加州大學(xué)的Y.He等人提出了一個(gè)可編程的傳感器網(wǎng)絡(luò)框架，如圖7-21所示，,在路由服務(wù)選擇協(xié)議的過(guò)程中，定義了3種組件用以描