【文章內(nèi)容簡介】 第一章緒論 節(jié)點的距離成正比例的目標。 ４．基于簇的路由協(xié)議 在這類路由協(xié)議中，將傳感器節(jié)點劃分到一個個簇，采樣數(shù)據(jù)首先傳到簇首， 簇首可以對采樣數(shù)據(jù)進行融合，然后再轉(zhuǎn)發(fā)到Ｓｉｎｋ節(jié)點，以減少網(wǎng)絡流量。這 類路由協(xié)議的典型代表包括ＬＥＡＣＨ，ＴＥＥＨ，ＰＥＧＡＳＩＳ。ＬＥＡＣＨ（ＬｏｗＥｎｅｒｇｙＡｄａｐｔｉｒｅ ＣｌｕｓｔｅｒｉｎｇＨｉｅｒ ａｒｃｈｙ）低功耗自適應聚類路由協(xié)議是2020年麻省理工學院電子 工程和計算機科學系的ＷｅｎｄｉＨｅｉｚｅｌｍａｎ等人為無線傳感器網(wǎng)絡專門設計的。 ＴＥＥＮ協(xié)議和ＰＥＧＡＳＩＳ協(xié)議都是在ＬＥＡＣＨ協(xié)議的基礎上提出來的。 簇類路由協(xié)議是本文的研究重點，將在第二章中詳細介紹。 １．３．４代表性的路由協(xié)議 １．泛洪（Ｆｌｏｏｄ）算法和閑聊（Ｇｏｓｓｉｐｉｎｇ）算法 泛洪（Ｆｌｏｏｄ）算法和閑聊（Ｇｏｓｓｉｐｉｎｇ）算法 ? １是無線傳感器網(wǎng)絡中應用最早 且最簡單的路由協(xié)議，它們不需要任何路由算法，也不需要維護網(wǎng)絡拓撲 結(jié)構(gòu)。 在泛洪協(xié)議中，節(jié)點向它的所有鄰居節(jié)點廣播接收到的數(shù)據(jù)，如此反復，直到數(shù) 據(jù)到達目的節(jié)點或者達到數(shù)據(jù)報的最大跳數(shù)。 根據(jù)路由表建立和維護過程是由ｓｉｎｋ節(jié)點發(fā)起還是由ｓｅｎｓｏｒ節(jié)點發(fā)起的， 泛洪算法可以分為以下三種模式：１）傳統(tǒng)模式：指最基本的泛洪法，ｓｅｎｓｏｒ節(jié) 點以廣播的方式將收到的分組傳遞給自己的鄰居節(jié)點直至該分組到達ｓｉｎｋ節(jié) 點；２）事件驅(qū)動模式（ｅｖｅｎｔ－ｄｒｉｖｅｎ）：以感知環(huán)境數(shù)據(jù)的ｓｅｎｓｏｒ節(jié)點主動廣 播分組為特征，該分組基于路由表選取適當路徑到達ｓｉｎｋ節(jié)點；３）查詢驅(qū)動 模式（ｑｕｅｒｙ－ｄｒｉｖｅ）：以ｓｉｎｋ節(jié)點廣播與應用相關(guān)的查詢請求（ｉｎｔｅｒｅｓｔ），通過 其鄰居節(jié)點泛洪到整個網(wǎng)絡，滿足該查詢請求的ｓｅｎｓｏｒ節(jié)點則選取適當路徑發(fā) 送數(shù)據(jù)。 泛洪協(xié)議的優(yōu)點是：１）實現(xiàn)簡單；２）不需要為保持網(wǎng)絡拓撲信息和實現(xiàn) 復雜的路由發(fā)現(xiàn)算法而消耗計算資源；３）適用于健壯性要求高的場合。缺點是： １）存在信息爆炸（Ｉｍｐｌｏｓｉｏｎ）問題（如圖１－３所示），即出現(xiàn)一個節(jié)點可能得到一 個數(shù)據(jù)多個副本的現(xiàn)象。傳感器節(jié)點Ａ將采集到的數(shù)據(jù)沿著不同的節(jié)點Ｂ、Ｃ傳 輸，最終傳給了同一個節(jié)點Ｄ ，節(jié)點Ｄ對同一個數(shù)據(jù)收到了兩次，就產(chǎn)生了消息 內(nèi)爆的現(xiàn)象；２）部分數(shù)據(jù)重疊（Ｏｖｅｒｌａｐ）的現(xiàn)象（如圖卜４所示），處于同一觀測 環(huán)境的兩個相鄰的同類傳感器節(jié)點Ａ和Ｂ同時對一個事件Ｘ作出反應，二者采集 的數(shù)掘性質(zhì)相同，數(shù)值相近，這兩個節(jié)點的鄰居節(jié)點Ｃ將收到雙份數(shù)據(jù)副本；３） 盲目使用資源，擴散法不考慮各節(jié)點能量的可用狀況，因而無法作出相應的自適 應路由選擇。 碩士學位論文第一章緒論 圖Ｉ－３內(nèi)爆圖Ｉ－４重疊 針對泛洪的內(nèi)爆問題，提出了閑聊（Ｇｏｉｓｐｉｎｇ）路由協(xié)議 ，閑聊法采用隨機性 原則從而節(jié)省能量。一個節(jié)點發(fā)送數(shù)據(jù)，它隨機選擇它的一個鄰居節(jié)點轉(zhuǎn)發(fā)分組， 而不是像泛洪算法那樣向所有鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。該協(xié)議避免了內(nèi)爆問題的產(chǎn) 生，但是仍然無法解決部分數(shù)據(jù)的交疊現(xiàn)象和盲目使用資源的問題，而且增加了 端到端的數(shù)據(jù)傳輸延遲問題。閑聊算法的數(shù)據(jù)重發(fā)現(xiàn)象如圖卜５所示，一個節(jié)點 Ｂ若已經(jīng)收到它的鄰居節(jié)點Ａ的數(shù)據(jù)分組，當再次收到時，它就會將數(shù)據(jù)發(fā)回它 的鄰居節(jié)點Ａ。 圖卜５閑聊算法的數(shù)據(jù)重發(fā)現(xiàn)象 ２．ＳＰＩＮ ＳＰＩＮ（ＳｅｎｓｏｒＰｒｏｔｏｃｏｌｆｏｒｉｎｆｏｒｍａｔｉｏｎｖｉａ Ｎｅｇｏｔｉａｔｉｏｎ） 168。 ２一副是一種以 數(shù)據(jù)為中心的自適應通信路由協(xié)議。其目標是通過使用節(jié)點間的協(xié)商制度和資源 自適應機制，解決擴散法存在的不足之處。為了避免擴散法出現(xiàn)的信息爆炸問題 和部分重疊現(xiàn)象，傳感器節(jié)點在傳送數(shù)據(jù)之前彼此進行協(xié)商，協(xié)商制度可確保傳 輸有用數(shù)據(jù)。節(jié)點間通過發(fā)送元數(shù)據(jù)（即描述傳感器節(jié)點采集的數(shù)據(jù)屬性的數(shù)據(jù)， ｍｅｔａ — ｄａｔａ），而不是采集的整個數(shù)據(jù)進行協(xié)商。由于元數(shù)據(jù)大小小于采集的數(shù)據(jù)， 所以，傳輸元數(shù)據(jù)消耗的能量相對較少。在傳輸或接收數(shù)據(jù)之前，每個節(jié)點都必 須檢查各自可用的能量狀況 ，如果處于低能量水平，必須中斷一些操作，比如充 當數(shù)據(jù)中轉(zhuǎn)站（路由器）角色，停止數(shù)據(jù)轉(zhuǎn)發(fā)操作。ＳＰＩＮ有３種數(shù)據(jù)包類型，即 ＡＤＶ，ＲＥＱ和ＤＡＴＡ。ＡＤＶ用于新數(shù)據(jù)廣播，當一個節(jié)點有數(shù)據(jù)需傳輸時，它可用 碩－上學位論文第一章緒論 ＡＤＶ數(shù)據(jù)（包含元數(shù)據(jù)）對外廣播；ＲＥＱ用于請求發(fā)送數(shù)據(jù)，當一個節(jié)點希望接收 ＤＡＴＡ數(shù)據(jù)包時，發(fā)送ＲＥＱ數(shù)據(jù)包。 ＤＡＴＡ包含附上元數(shù)據(jù)頭（ｍｅｔａ～ｄａｔａｈｅａｄｅｒ）的傳感器采集的數(shù)據(jù)的數(shù)據(jù)包。 ＳＰＩＮ協(xié)議有４種不同的形式：ＳＰ ＩＮ — ＰＰ，ＳＰＩＮ — ＥＣ，ＳＰＩＮ－ＢＣ，ＳＰＩＮ－ＲＬ。一個傳 感器節(jié)點在發(fā)送一個ＤＡＴＡ數(shù)據(jù)包之前，首先向其鄰居節(jié)點廣播ＡＤＶ數(shù)據(jù)包，如 果一個鄰居節(jié)點在收到ＡＤＶ后有意愿接收該ＤＡＴＡ數(shù)據(jù)包，那么它向該節(jié)點發(fā)送 ～個ＲＥＯ數(shù)據(jù)包，接著節(jié)點向該鄰居節(jié)點發(fā)送ＤＡＴＡ數(shù)據(jù)包。類似地進行下去， ＤＡＴＡ數(shù)據(jù)包可被傳輸?shù)竭h方ｓｉｎｋ節(jié)點。ＳＰＩＮ－ＰＰ在傳輸新數(shù)據(jù)的過程中，直接 向鄰居節(jié)點廣播ＡＤＶ數(shù)據(jù)包，而沒有考慮其所有鄰居節(jié)點由于自身能量的原因， 不愿承擔起轉(zhuǎn)發(fā)新數(shù)據(jù)的功能，則新數(shù)據(jù)無法傳愉，將會出現(xiàn) “ 數(shù) 據(jù)盲點 ’’ ，進 而影響整個網(wǎng)絡信息的收集。 ｎＯＡＤＶｒ、ＯＲＥＱｎ ＤＡＴＡ ｎ。 ◆ ? ●● ： ◆● Ｕ ｎＢＡＵＯＢＡＵｒ、ＢＡＵ＼ ’ 一／ 』上 （，］ＤＡＴＡ ｅ－９呦。 ｆ． ▲ ＡＤＶ ｌ烹二 ◆ ｏ ■ Ｂ ： ：： ≥ ：？ｕ ‘ ＢＡ 圖卜６ＳＰＩＮ協(xié)議通信過程 ＳＰＩＮ協(xié)議的通信過程如圖Ｉ－６所示。在發(fā)送一個ＤＡＴＡ數(shù)據(jù)包之前，傳感器 節(jié)點Ａ首先對外廣播ＡＤＶ數(shù)據(jù)包：如果它的鄰居節(jié)點Ｂ在收到ＡＤＶ后有意愿接收 該ＤＡＴＡ數(shù)據(jù)包，那么Ｂ就向該節(jié)點Ａ發(fā)送一個ＲＥＱ數(shù)據(jù)包，接著節(jié)點Ａ向其鄰 居節(jié)點Ｂ發(fā)送ＤＡＴＡ數(shù) 據(jù)包。接下來Ｂ再重復這個過程，這樣整個傳感器網(wǎng)絡中 對此數(shù)據(jù)感興趣的節(jié)點都會得到一份該數(shù)據(jù)的拷貝。 ３．定向擴散路由（ＤＤ） ＤｉｒｅｃｔｅｄＤｉｆｕｓｉｏｎ 168。 爭２ 168。 它是Ｅｓｔｒｉｎ等人專門為傳感器網(wǎng)絡設計的路由策略， 與已有的路由算法有著截然不同的實現(xiàn)機制。匯聚節(jié)點通過興趣消息（ｉｎｔｅｒｅｓｔ） 發(fā)出查詢?nèi)蝿?，采用泛洪方式傳播興趣消息到整個區(qū)域或部分區(qū)域內(nèi)的所有傳感 器節(jié)點。興趣消息用來表示查詢的任務，表達用戶網(wǎng)絡對監(jiān)測區(qū)域內(nèi)感興趣的信 息，例如監(jiān)測區(qū)域內(nèi)的溫度、濕度和光照等環(huán)境信息。在興趣消息的傳播過 程中， 協(xié)議逐跳地在每個傳感器節(jié)點上建立反向的從數(shù)據(jù)源到匯聚節(jié)點的數(shù)據(jù)傳輸梯 度（ｇｒａｄｉｅｎｔ）。傳感器節(jié)點將采集到的數(shù)據(jù)沿著梯度方向傳送到匯聚節(jié)點。 定向擴散路由機制可以分為周期性的興趣擴散、梯度建立以及路徑加強三個 階段。圖Ｉ－７顯示了這三個階段的數(shù)據(jù)傳播路徑和方向。 碩上學位論文第一章緒論 在興趣擴散階段，匯聚節(jié)點周期性地向鄰居節(jié)點廣播興趣消息。興趣消息中 含有任務類型、目標區(qū)域、數(shù)據(jù)發(fā)送速率、時間域等參數(shù)。每個節(jié)點在本地保存 一個興趣列表，對于每一個興趣 ，列表中都有一個表項記錄發(fā)來該興趣消息的鄰 居節(jié)點、數(shù)據(jù)發(fā)送速率和時間域等任務相關(guān)信息，以建立該節(jié)點向匯聚節(jié)點傳遞 數(shù)據(jù)的梯度關(guān)系在數(shù)據(jù)傳播階段，當傳感器節(jié)點采集到與興趣匹配的數(shù)據(jù)時，把 數(shù)據(jù)發(fā)送到梯度上的鄰居節(jié)點，并按照梯度上的數(shù)據(jù)傳輸速率設定傳感器模塊采 集數(shù)據(jù)的速率。在路徑加強階段，鄰居節(jié)點收到消息后，經(jīng)過分析確定該消息描 述的是一個己有的興趣，只是增加了數(shù)據(jù)發(fā)送速率，則斷定這是一條路徑加強消 息，從而更新相應興趣表項的到鄰居節(jié)點的發(fā)送數(shù)據(jù)速率。路由加強的標準不是 唯一的，可以選擇在一定時間內(nèi)發(fā)送數(shù)據(jù) 最多的節(jié)點作為路徑加強的下一跳節(jié) 點。在加強路徑上的節(jié)點如果發(fā)現(xiàn)下一跳節(jié)點的發(fā)送數(shù)據(jù)速率明顯減小，或者收 到來自其他節(jié)點的新位置估計，推斷加強路徑的下一跳節(jié)點失效，就需要使用路 徑加強機制重新確定下一跳節(jié)點。 圓一。圓 （ａ）興趣傳播 ＯＯ 眥 ◆?◇ 一 ● 咖 ＯＯ （ｂ）梯度建立（ｃ）數(shù)據(jù)發(fā)送路徑加強 圖Ｉ－７ＤＤ工作過程 它與已有的路由算法實現(xiàn)機制不同，節(jié)點用一組屬性值來描述數(shù)據(jù)內(nèi)容、通 過梯度矢量信息來描述特定數(shù)據(jù)的需求方向，利用基于反饋信息的迭代優(yōu)化算法 在源節(jié)點與目的節(jié)點間建立一條最佳路徑。匯聚節(jié)點或 基站向所有傳感器發(fā)送對 任務描述的 “ 興趣＂，即一個任務描述數(shù)據(jù)包。 “ 興趣 ” 會通過全網(wǎng)逐漸擴散，最 終找到匹配請求條件的數(shù)據(jù)源，與此同時，也建立起從數(shù)據(jù)源到槽節(jié)點的 “ 梯度＂。 節(jié)點會在它的緩存中存儲興趣入口，興趣入口包含時間標簽域和若干個梯度場， 數(shù)據(jù)源節(jié)點會沿梯度最大的方向?qū)?shù)據(jù)傳回槽節(jié)點。梯度反映了網(wǎng)絡中節(jié)點對匹 配請求條件的數(shù)據(jù)源的近似判斷，更直接的方法是節(jié)點用一組標量值表示它的選 擇，值越大意味著向該方向繼續(xù)搜索獲得匹配數(shù)據(jù)的可能性越大，這樣的處理最 終將會在整個網(wǎng)絡中為ｓｉｎｋ節(jié)點的請求建立一個臨時 的 “ 梯度 ” 場，匹配數(shù)據(jù) 可以沿 “ 梯度＂最大的方向中繼回ｓｉｎｋ節(jié)點。圖卜８描述了定向擴散模型的工 作原理。 碩士學位論文第一章緒論 Ｏｏ 第一步：請求擴散第二步：梯度場建立第三步：數(shù)據(jù)傳輸 圖Ｉ－８定向擴散模型的工作原理 ４．ＧＥＡＲ ＧＥＡＲ（ＧｅｏｇｒａｐｈｉｃａｎｄＥｎｅｒｇｙＡｗａｒｅＲｏｕｔｉｎｇ）乜２側(cè)是充分考慮了能源有 效性的基于位置的路由協(xié)議，它比其它的基于位置的路由協(xié)議能更好地應用于無 線傳感器網(wǎng)絡之中。ＧＥＡＲ根據(jù)事件區(qū)域的地理位置信息，建立匯聚 節(jié)點到事件 區(qū)域的優(yōu)化路徑，避免了泛洪傳播方式，從而減少了路由建立的開銷。ＧＥＡＲ路 由假設己知事件區(qū)域的位置信息，每個節(jié)點知道自己的位置信息和剩余能量信 息，并通過一個簡單的Ｈｏｌｅ，消息交換機知道所有鄰居節(jié)點的位置信息和剩余 能量信息。在ＧＥＡＲ路由中，節(jié)點間的無線鏈路是對稱的。ＧＥＡＲ路由中查詢消息 傳播包括兩個節(jié)點。首先匯聚節(jié)點發(fā)出節(jié)點查詢命令，并根據(jù)時間區(qū)城的地理位 置將查詢命令傳送到區(qū)域內(nèi)距匯聚節(jié)點最近的節(jié)點，然后從該節(jié)點將查詢命令傳 輸?shù)絽^(qū)域內(nèi)的其它所有節(jié)點。監(jiān)測數(shù)據(jù)沿查詢消息的反向路徑向匯聚 節(jié)點傳送。 ｏ＿ｒ一、ｏｕ ｏ ｏ＼ ｌ－－ｌ ，Ｌ ＼ ＼／ｏ ■ 一 ｏｏ廠＿ｏ 卜 Ｕ傳基 ? 節(jié)點 圖Ｉ－９ＧＥＡＲ算法區(qū)域內(nèi)的迭代地理轉(zhuǎn)發(fā) ＧＥＡＲ算法提出：既然傳感器網(wǎng)絡中的數(shù)據(jù)經(jīng)常包含了位置屬性信息，那么 可以利用這一信息，把在整個網(wǎng)絡中擴散的信息傳送到適當?shù)奈恢脜^(qū)域中。同樣 ＧＥＡＲ也采用了查詢驅(qū)動數(shù)據(jù)傳送模式。它傳送數(shù)據(jù)分組到目標域中所有的節(jié)點 的過程包括兩個節(jié)點：目標域數(shù)據(jù)傳送和域內(nèi)數(shù)據(jù)傳送。在目標域數(shù)據(jù)傳送節(jié)點， 當節(jié)點收到數(shù)據(jù)分組，它將鄰接點同目標域的距離和它自己與目標域的距離相比 較，若存 在更小距離則選擇最小距離的鄰接點作為下一跳節(jié)點；若不存在更小距 離，則認為存在 “ ｈｏｌｅ ” ，節(jié)點將根據(jù)鄰居的最小花銷來選擇下一跳節(jié)點。在域 內(nèi)數(shù)據(jù)傳送階段，可通過兩種方式讓數(shù)據(jù)在域內(nèi)擴散：在域內(nèi)直接洪泛和遞歸的 碩士學位論文第一章緒論 目標域數(shù)據(jù)傳送直到目標域剩下唯一的節(jié)點，見圖１－９。ＧＥＡＲ路由通過定義估計 路由代價為節(jié)點到事件區(qū)域的距離和節(jié)點剩余能量，并利用捎帶機制獲取實際路 由代價，進行數(shù)據(jù)傳輸?shù)穆窂絻?yōu)化，從而形成能量高效的數(shù)據(jù)傳輸路徑。ＧＥＡＲ 路由采用的 貪婪算法是一個局部最優(yōu)的算法，適合無線傳感器網(wǎng)絡中節(jié)點只知道 局部拓撲信息的情況，其缺點是由于缺乏足夠的拓撲信息，路由過程中可能遇到 路由空洞，反而降低了路由效率。如果節(jié)點擁有相鄰兩跳節(jié)點的地理位置信息， 可以大大減少路由空洞的產(chǎn)生概率。 ＧＥＡＲ協(xié)議要求每個節(jié)點維護一個預估費用和一個通過鄰居節(jié)點到達目的的 節(jié)點距離的結(jié)合。 預估費用：節(jié)點剩余能量與到目的節(jié)點距離的結(jié)合 學習費用：則是對描述網(wǎng)絡中環(huán)繞在洞周圍路由所需預估費用的改進 洞：是指某個節(jié)點的周圍沒有任何鄰居節(jié)點比它自身更接近目標區(qū)域。如果 沒有洞現(xiàn) 象的產(chǎn)生，那么預估費用等于學習費用。每當一個數(shù)據(jù)包成功到達目的 地，該節(jié)點的學習費用就要傳播到上一跳以便于對下一跳數(shù)據(jù)包的路由建立進行 調(diào)整。 協(xié)議包含２個階段 （１）向目標區(qū)域傳遞數(shù)據(jù)包： 當節(jié)點收到數(shù)據(jù)包時，首先要檢查是否有鄰居節(jié)點比它更接近目標區(qū)域。如 果有，就選擇距離目標區(qū)域最近的節(jié)點作為數(shù)據(jù)傳遞的下一跳節(jié)點。如果相對該 節(jié)點來說，所有鄰居都比它更遠離目標區(qū)域，這就意味著該節(jié)點存在洞現(xiàn)象。在 這種情況下，利用學習費用函數(shù)選擇其中的一個鄰居節(jié)點來傳遞數(shù)據(jù) （２）傳遞已在目標區(qū)域內(nèi)的數(shù)據(jù)包。 如果數(shù)據(jù)包 已經(jīng)到達目標區(qū)域，可以利用遞歸的地理傳遞方式和受限的 Ｆｌｏｏｄｉｎｇ方式發(fā)布該數(shù)據(jù)。當傳感器節(jié)點的分布不太緊密時，受限的ｆｌｏｏｄｉｎｇ 方式是比較好的選擇。而在高密度的無線傳感器網(wǎng)絡內(nèi)，遞歸的地理傳遞方式相 對受限的ｆｌｏｏｄｉｎｇ方式更加節(jié)能。在這種情況下，目標區(qū)域被劃分為４個子區(qū) 域。數(shù)據(jù)包也響應的被復制了４次，這