無線傳感網(wǎng)路由協(xié)議

1、第四章 路由協(xié)議 lWSN路由協(xié)議概述 lWSN路由協(xié)議分類 l能量感知路由協(xié)議 l基于查詢的路由協(xié)議 l集群結(jié)構(gòu)路由協(xié)議 l地理位置路由協(xié)議 重要性：在傳感節(jié)點(diǎn)和網(wǎng)絡(luò)匯聚節(jié)點(diǎn)之 間建立高效的傳輸路徑。 lWSN路由協(xié)議概述 lWSN路由協(xié)議分類 l能量感知路由協(xié)議 l基于查詢的路由協(xié)議 l集群結(jié)構(gòu)路由協(xié)議 l地理位置路由協(xié)議 n 定義： nWSN路由協(xié)議是一套將數(shù)據(jù)從源節(jié)點(diǎn)傳輸?shù)侥康墓?jié)點(diǎn)的機(jī)制。 n 路由是WSN的核心技術(shù)之一 n WSN不適合設(shè)計(jì)通用的路由協(xié)議：能耗、 計(jì)算復(fù)雜度。 nWSN是無基礎(chǔ)設(shè)施的網(wǎng)絡(luò)，一般用電池供電、 無人看守，電池不能補(bǔ)充，要延長網(wǎng)絡(luò)壽 命就必須降低能耗。 n

2、能耗主要用戶數(shù)據(jù)無線傳輸上，所以單跳 傳輸距離不能太遠(yuǎn)，要實(shí)現(xiàn)WSN大范圍覆蓋， 就需要多跳中繼，即路由 n設(shè)計(jì)目標(biāo) 滿足應(yīng)用需求 （WSN路由與應(yīng)用相關(guān)） 低網(wǎng)絡(luò)開銷 （內(nèi)存、計(jì)算復(fù)雜度、節(jié)能） 資源利用的整體有效性 網(wǎng)絡(luò)高吞吐率 nWSN使用環(huán)境惡劣 無線信道不穩(wěn)定 節(jié)點(diǎn)的移動(dòng)與失效 WSN拓?fù)浣Y(jié)構(gòu)隨時(shí)可能變化，這與 傳統(tǒng)Internet不同，因此傳統(tǒng)路由不能 用于WSN n與傳統(tǒng)網(wǎng)絡(luò)不同： （傳統(tǒng)網(wǎng)絡(luò)（如GSM）放在QoS上；WSN重點(diǎn)在 能耗上） nWSN特點(diǎn) 自組織的網(wǎng)絡(luò)（隨機(jī)部署） 數(shù)據(jù)的冗余性（多節(jié)點(diǎn)監(jiān)測同一事件，需要數(shù)據(jù)融合） 基于局部拓?fù)湫畔ⅲㄓ布拗疲?網(wǎng)絡(luò)功能：數(shù)據(jù)收集，

3、多對一 （一個(gè)sink節(jié)點(diǎn)） WSN路由與應(yīng)用相關(guān)，(不同的應(yīng)用采用不同的路由，降低路由復(fù) 雜度) 以數(shù)據(jù)為中心 n要求 能量高效（協(xié)議簡單 缺點(diǎn)：點(diǎn)到點(diǎn)的時(shí)延較大 由于隨機(jī)轉(zhuǎn)發(fā)某一個(gè)節(jié)點(diǎn)的方向并不一定在距離目的節(jié)點(diǎn)更近的方向上， 因此容易造成數(shù)據(jù)到達(dá)目的節(jié)點(diǎn)時(shí)間過長或者跳數(shù)己達(dá)到最大，而數(shù)據(jù) 還沒有到達(dá)目的節(jié)點(diǎn)，造成遞送失敗。 剛開始的很短的時(shí)間內(nèi)發(fā)送速率很大，但是隨著數(shù)據(jù)的發(fā)送，速度會明 顯降低，而且它并不能很好解決重疊的問題。 52 這是第1個(gè)基于數(shù)據(jù)的路由協(xié)議。該協(xié)議以抽象的元數(shù)據(jù) 對數(shù)據(jù)進(jìn)行命名，命名方式?jīng)]有統(tǒng)一標(biāo)準(zhǔn)。節(jié)點(diǎn)產(chǎn)生或收 到數(shù)據(jù)后，為避免盲目傳播，用包含元數(shù)據(jù)的ADV消息向

4、 鄰節(jié)點(diǎn)通告，需要數(shù)據(jù)的鄰節(jié)點(diǎn)用REQ消息提出請求，數(shù) 據(jù)通過DATA消息發(fā)送到請求節(jié)點(diǎn)。協(xié)議的優(yōu)點(diǎn)是： 小ADV消息減輕了內(nèi)爆問題；通過數(shù)據(jù)命名解決了交疊問題； 節(jié)點(diǎn)根據(jù)自身資源和應(yīng)用信息決定是否進(jìn)行ADV通告，避免了 資源利用盲目問題。 與Flooding和Gossiping協(xié)議相比，有效地節(jié)約了能量。 其缺點(diǎn)是： 當(dāng)產(chǎn)生或收到數(shù)據(jù)的節(jié)點(diǎn)的所有鄰節(jié)點(diǎn)都不需要該數(shù)據(jù)時(shí)， 將導(dǎo)致數(shù)據(jù)不能繼續(xù)轉(zhuǎn)發(fā)，以致較遠(yuǎn)節(jié)點(diǎn)無法得到數(shù)據(jù)，當(dāng) 網(wǎng)絡(luò)中大多節(jié)點(diǎn)都是潛在sink點(diǎn)時(shí)，問題并不嚴(yán)重，但當(dāng) sink點(diǎn)較少時(shí)，則是一個(gè)很嚴(yán)重的問題；且當(dāng)某sink點(diǎn)對任 何數(shù)據(jù)都需要時(shí)，其周圍節(jié)點(diǎn)的能量容易耗盡；雖然減輕了

5、 數(shù)據(jù)內(nèi)爆，但在較大規(guī)模網(wǎng)絡(luò)中，ADV內(nèi)爆仍然存在。 53 該協(xié)議考慮到了WSN中的數(shù)據(jù)冗余問題：臨近的 節(jié)點(diǎn)所感知的數(shù)據(jù)具有相似性，通過節(jié)點(diǎn)間協(xié)商 (Nagotiation)的方式減少網(wǎng)絡(luò)中數(shù)據(jù)的傳輸?shù)?數(shù)據(jù)量。節(jié)點(diǎn)只廣播其他節(jié)點(diǎn)所沒有的數(shù)據(jù)以減 少冗余數(shù)據(jù)，從而有效減少能量消耗。 在SPIN協(xié)議中提出了元數(shù)據(jù)（mete data，是對 節(jié)點(diǎn)感知數(shù)據(jù)的抽象描述）的概念，元數(shù)據(jù)是原 始感知數(shù)據(jù)的一個(gè)映射，可以用來描述原始感知 數(shù)據(jù)，而且元數(shù)據(jù)所需的數(shù)據(jù)位比原始感知數(shù)據(jù) 要小，采用這種變相的數(shù)據(jù)壓縮策略可以進(jìn)一步 減少通信過程中的能量消耗。 54 SPIN協(xié)議采用三次握手協(xié)議來實(shí)現(xiàn)數(shù)據(jù)的交互，

6、協(xié)議運(yùn)行過程中使用三種報(bào)文數(shù)據(jù)，分別為ADV、 REQ和DATA。ADV用于數(shù)據(jù)的廣播，當(dāng)某一個(gè)節(jié)點(diǎn) 有數(shù)據(jù)可以共享時(shí)，可以用ADV數(shù)據(jù)包通知其鄰 居節(jié)點(diǎn)；REQ用于請求發(fā)送數(shù)據(jù)，當(dāng)某一個(gè)收到 ADV的節(jié)點(diǎn)希望接收DATA數(shù)據(jù)包時(shí)，發(fā)送REQ數(shù)據(jù) 包；DATA為原始感知數(shù)據(jù)包，里面裝載了原始感 知數(shù)據(jù)。 SPIN協(xié)議還包括了4個(gè)協(xié)議： SPIN-BC：適合于廣播信道的SPIN協(xié)議 SPIN-PP：適合于點(diǎn)對點(diǎn)信道的SPIN協(xié)議 SPIN-EC：在SPIN-PP基礎(chǔ)上增加了能量限制 SPIN-RL：考慮信道上存在分組丟失的SPIN協(xié)議 55 SPINSPIN：Sensor Protocol fo

7、r Sensor Protocol for Information via NegotiationInformation via Negotiation 該協(xié)議是最早的一類WSN路由協(xié)議的代 表，是對Flooding協(xié)議的改進(jìn) 考慮到WSN的數(shù)據(jù)冗余，臨近節(jié)點(diǎn)所感 知的數(shù)據(jù)具有相似性，通過節(jié)點(diǎn)間協(xié)商 方式減少數(shù)據(jù)傳輸量，只廣播其他節(jié)點(diǎn) 沒有的數(shù)據(jù) 元數(shù)據(jù)：對節(jié)點(diǎn)感知數(shù)據(jù)的抽象，是原 始感知數(shù)據(jù)的壓縮，可以描述原始感知 數(shù)據(jù) （傳元數(shù)據(jù)可以節(jié)省能耗） SPIN協(xié)議有兩種工作模式：SPIN1和 SPIN2，（SPIN2在SPIN1 的基礎(chǔ)上考慮 了節(jié)點(diǎn)剩余能量） SPIN采用三次握手機(jī)制，有三種分

8、組： ADV（相當(dāng)于數(shù)據(jù)的索引，很短）、REQ、DATA n協(xié)商通過元數(shù)據(jù)進(jìn)行協(xié)商通過元數(shù)據(jù)進(jìn)行 元數(shù)據(jù)描述實(shí)數(shù)據(jù) 元數(shù)據(jù)與實(shí)數(shù)據(jù)一一對應(yīng) n協(xié)議消息協(xié)議消息 消息廣播包：Advertise (ADV)Advertise (ADV) 數(shù)據(jù)請求包：Request (REQ)Request (REQ) 數(shù)據(jù)包：Data transfer (DATA)Data transfer (DATA) A A A A A A 節(jié)點(diǎn)A有新數(shù)據(jù)，通過ADV發(fā) 布新數(shù)據(jù)信息，使用元數(shù)據(jù) B節(jié)點(diǎn)收到ADV后，發(fā)現(xiàn)自己 沒有該數(shù)據(jù)，通過REQ向A請求 新數(shù)據(jù) A節(jié)點(diǎn)向B節(jié)點(diǎn)傳送源數(shù)據(jù) B節(jié)點(diǎn)融合新數(shù)據(jù)，并通過 ADV發(fā)

9、布新數(shù)據(jù)消息 如果節(jié)點(diǎn)ADV中描述的數(shù)據(jù)的 副本就忽略該消息 圖圖 SPINSPIN協(xié)議工作流程協(xié)議工作流程 n通過和鄰居節(jié)點(diǎn)的協(xié)商來通過和鄰居節(jié)點(diǎn)的協(xié)商來減少減少FloodingFlooding帶來的帶來的內(nèi)爆內(nèi)爆 和重疊和重疊的影響的影響 n通過通過元數(shù)據(jù)元數(shù)據(jù)來完成協(xié)商過程來完成協(xié)商過程 元數(shù)據(jù)：一種對源數(shù)據(jù)的映射，比源數(shù)據(jù)短 避免傳輸冗余數(shù)據(jù) n3 3步握手協(xié)議步握手協(xié)議(ADV-REQ-DATA)(ADV-REQ-DATA) nSPIN-2SPIN-2在在SPIN-1SPIN-1的基礎(chǔ)上加入了能量閾值的基礎(chǔ)上加入了能量閾值 當(dāng)一個(gè)節(jié)點(diǎn)的剩余能量低于能量閾值后，減少其在協(xié)議中參 與的活

10、動(dòng)。 SPIN2模式考慮了剩余能量值，當(dāng)節(jié)點(diǎn) 能量值低于某個(gè)門限值時(shí)，該節(jié)點(diǎn)就不 再參與DATA報(bào)文的轉(zhuǎn)發(fā)，只是接收報(bào)文 和發(fā)出REQ報(bào)文，進(jìn)一步降低了能耗 模擬結(jié)果表明，SPIN2比傳統(tǒng)方式節(jié)省 能耗一半以上 SPIN利用三步握手機(jī)制 （解決內(nèi)爆） SPIN利用數(shù)據(jù)融合（DC），部分解決 了重疊問題 n優(yōu)點(diǎn) 解決了內(nèi)爆問題和部分解決了重疊問題 不需要進(jìn)行路由維護(hù) 對網(wǎng)絡(luò)拓?fù)渥兓幻舾?，可用于移?dòng)WSN n缺點(diǎn) 本質(zhì)上SPIN還是向全網(wǎng)擴(kuò)散新消息，開銷 比較大 當(dāng)多個(gè)節(jié)點(diǎn)向同一個(gè)節(jié)點(diǎn)同時(shí)發(fā)送REQ時(shí)， 需要退避算法 SPIN協(xié)議還包括了4個(gè)協(xié)議： SPIN-BC：適合于廣播信道的SPIN協(xié)議

11、SPIN-PP：適合于點(diǎn)對點(diǎn)信道的SPIN協(xié)議 SPIN-EC：在SPIN-PP基礎(chǔ)上增加了能量限 制 SPIN-RL：考慮信道上存在分組丟失的SPIN 協(xié)議 DD:Directed DD:Directed DiffusionDiffusion 定向擴(kuò)散定向擴(kuò)散 思路：Sink節(jié)點(diǎn)周期性地廣播一種稱為 “興趣”的分組，告訴其他節(jié)點(diǎn)，我要 收集什么興趣。興趣在擴(kuò)散的過程中也 反向建立了路由路徑，與“興趣”匹配 節(jié)點(diǎn)通過路徑傳送數(shù)據(jù)到Sink節(jié)點(diǎn) 三個(gè)階段： 興趣擴(kuò)散（采用泛洪）； 梯度建立（反向建立）； 強(qiáng)化路徑（Sink節(jié)點(diǎn)會收到多條路徑，選 最優(yōu)路徑，進(jìn)行加強(qiáng)，以后的數(shù)據(jù)按照加 強(qiáng)路徑傳送）

12、 圖 DD路由機(jī)制 nSink節(jié)點(diǎn)查詢興趣消息 興趣消息采用泛洪的方法傳播到網(wǎng)絡(luò) 有和興趣匹配數(shù)據(jù)的節(jié)點(diǎn)發(fā)送數(shù)據(jù) 興趣擴(kuò)散階段建立節(jié)點(diǎn)到Sink的路徑 n興趣的定義： 由屬性值對組成 type = four-legged animal / detect animal location interval = 20 ms / send back events every 20 ms duration = 10 seconds / . for the next 10 seconds rect = -100, i00, 200, 400 / from sensors within rectangle

13、Sink節(jié)點(diǎn)向全網(wǎng)查詢興趣 建立源節(jié)點(diǎn)和Sink間路徑 興趣在全網(wǎng)中擴(kuò)散 對每一個(gè)活動(dòng)任務(wù)，Sink周期進(jìn)行查詢 鄰居更新自己的興趣cache，并且轉(zhuǎn)發(fā) 興趣cache中的條目(興趣表項(xiàng)) 時(shí)間戳：指示接收到相關(guān)興趣消息的最近時(shí)間 若干梯度域：每個(gè)梯度和其鄰居節(jié)點(diǎn)相關(guān)聯(lián) （每條表項(xiàng)有 多個(gè)梯度域） 一個(gè)梯度標(biāo)示一個(gè)鄰居 每個(gè)梯度中含有一個(gè)指定的數(shù)據(jù)傳輸率 持續(xù)時(shí)間：該興趣消息的有效期 n查詢消息的傳播建立數(shù)據(jù)的傳輸梯度 Sink節(jié)點(diǎn)發(fā)送查詢消息 興趣消息：任務(wù)性質(zhì)、數(shù)據(jù)采集/發(fā)送數(shù)率、時(shí)間戳等 中間節(jié)點(diǎn)： 記錄 轉(zhuǎn)發(fā) 梯度：表示了數(shù)據(jù)的傳輸方向 n加強(qiáng)路徑上的節(jié)點(diǎn)可以觸發(fā)和啟動(dòng)路徑 的加強(qiáng)過程

14、 新路徑 C和源節(jié)點(diǎn) 之間路徑 斷裂 n優(yōu)點(diǎn) 數(shù)據(jù)中心路由，定義不同任務(wù)類型/目標(biāo)區(qū)域 消息； 路徑加強(qiáng)機(jī)制可顯著提高數(shù)據(jù)傳輸?shù)乃俾剩?周期性路由：能量的均衡消耗； n缺點(diǎn) 周期性的洪泛機(jī)制-能量和時(shí)間開銷都比較 大； Sink周期性廣播，不適用于大規(guī)模網(wǎng)絡(luò) 節(jié)點(diǎn)需要維護(hù)一個(gè)興趣消息列表，代價(jià)較大； nGBR路由(Gradient-Based Routing)協(xié)議： 梯度域擴(kuò)展（傳感器節(jié)點(diǎn)到Sink節(jié)點(diǎn)的跳數(shù)信息、無線鏈路 評估信息） nEAR(Energy Aware Routing)路由協(xié)議 建立路由過程中加入能量評估機(jī)制； 路由路徑的能量開銷大于某一閾值不采用； nCADR路由(Cons

15、trained Anisotropic Diffusion routing)協(xié)議 興趣消息往指定方向發(fā)送 有些傳感器網(wǎng)絡(luò)的應(yīng)用中，數(shù)據(jù)傳輸量較少或者已知事 件區(qū)域。定向擴(kuò)散路由并不是高效的路由機(jī)制。 Boulis 等人提出了謠傳路由,適用于數(shù)據(jù)傳輸量較小的 傳感器網(wǎng)絡(luò)。 謠傳路由機(jī)制引入了查詢消息的單播隨機(jī)轉(zhuǎn)發(fā)，克服了 使用洪泛方式建立轉(zhuǎn)發(fā)路徑帶來的開銷過大問題。它的 基本思想是： 事件區(qū)域中的傳感器節(jié)點(diǎn)產(chǎn)生代理（ agent ） 消息， 代理 消息沿隨機(jī)路徑向外擴(kuò)散傳播。 同時(shí)匯聚節(jié)點(diǎn)發(fā)送的查詢消息也沿隨機(jī)路徑在網(wǎng)絡(luò)中傳播。 當(dāng)代理消息和查詢消息的傳輸路徑交叉在一起時(shí)， 就會形成 一條匯聚節(jié)

16、點(diǎn)到事件區(qū)域的完整路徑。 75 76 謠傳路由的原理如圖所示，謠傳路由的工作 過程如下： 每個(gè)傳感器節(jié)點(diǎn)維護(hù)一個(gè)鄰居列表和一個(gè)事件列 表。 事件列表的每個(gè)表項(xiàng)都記錄事件相關(guān)的信息，包 括事件名稱、到事件區(qū)域的跳數(shù)和到事件區(qū)域的 下一跳鄰居等信息。 當(dāng)傳感器節(jié)點(diǎn)在本地監(jiān)測到一個(gè)事件發(fā)生時(shí)，在 事件列表中增加一個(gè)表項(xiàng)，設(shè)置事件名稱、跳數(shù) （為零）等，同時(shí)根據(jù)一定的概率產(chǎn)生一個(gè)代理 消息。 77 代理消息是一個(gè)包含生命期等事件相關(guān)信息的分組， 用來將攜帶的事件信息通告給它傳輸經(jīng)過的每一個(gè)傳 感器節(jié)點(diǎn)。 對于收到代理消息的節(jié)點(diǎn)，首先檢查事件列表中是否 有該事件相關(guān)的表項(xiàng)，列表中存在相關(guān)表項(xiàng)就比較代 理

17、消息和表項(xiàng)中的跳數(shù)值，如果代理中的跳數(shù)小，就 更新表項(xiàng)中的跳數(shù)值，否則更新代理消息中的跳數(shù)值。 如果事件列表中沒有該事件相關(guān)的表項(xiàng)，就增加一個(gè) 表項(xiàng)來記錄代理消息攜帶的事件信息。然后，節(jié)點(diǎn)將 代理消息中的生存值減 1 ，在網(wǎng)絡(luò)中隨機(jī)選擇鄰居 節(jié)點(diǎn)轉(zhuǎn)發(fā)代理消息，直到其生存值減少為零。 通過代理消息在其有限生存期的傳輸過程，形成一段 到達(dá)事件區(qū)域的路徑。 78 網(wǎng)絡(luò)中的任何節(jié)點(diǎn)都可能生成一個(gè)對特定事件的 查詢消息。 如果節(jié)點(diǎn)的事件列表中保存有該事件的相關(guān)表項(xiàng)， 說明該節(jié)點(diǎn)在到達(dá)事件區(qū)域的路徑上，它沿著這 條路徑轉(zhuǎn)發(fā)查詢消息。否則，節(jié)點(diǎn)隨機(jī)選擇鄰居 節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢消息。 查詢消息經(jīng)過的節(jié)點(diǎn)按照同樣方式

18、轉(zhuǎn)發(fā)，并記錄 查詢消息中的相關(guān)信息，形成查詢消息的路徑。 查詢消息也具有一定的生存期，以解決環(huán)路問題。 79 lWSN路由協(xié)議概述 lWSN路由協(xié)議分類 l能量感知路由協(xié)議 l基于查詢的路由協(xié)議 l集群結(jié)構(gòu)路由協(xié)議 l地理位置路由協(xié)議 n地理位置信息路由協(xié)議要求每個(gè)節(jié)點(diǎn)地理位置信息路由協(xié)議要求每個(gè)節(jié)點(diǎn)知知 道自己在網(wǎng)絡(luò)中的位置道自己在網(wǎng)絡(luò)中的位置 n下列方法可確定節(jié)點(diǎn)位置下列方法可確定節(jié)點(diǎn)位置 GPS(Global Positioning System)Global Positioning System) 超聲波三角定位系統(tǒng) 標(biāo)定標(biāo)定 n用途用途 地理位置信息作為其它路由算法的輔助 直接用于路

19、由的計(jì)算 GPSRGPSR： Greedy Perimeter Stateless RoutingGreedy Perimeter Stateless Routing 貪婪算法 利用節(jié)點(diǎn)的地理位置信息 轉(zhuǎn)發(fā)節(jié)點(diǎn)（下一跳）選取： 選擇鄰居節(jié)點(diǎn)中離目的節(jié)點(diǎn)D 最近的點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn) 貪婪算法的缺點(diǎn)：出現(xiàn)局部優(yōu)化問題 存在x到D的路徑 x的鄰居w,y離D的距離比x大 解決方法：邊界轉(zhuǎn)發(fā) 空曠區(qū)域空曠區(qū)域 n平面圖： 二維空間結(jié)構(gòu)； 平面圖中任意兩條邊都不相交； nGPSR算法中構(gòu)造平面圖的方法是刪除網(wǎng) 絡(luò)拓?fù)鋱D中交叉的邊 n算法： RNG(Relative Neighborhood Graph) GG

20、(Gabriel Graph) n節(jié)點(diǎn)u，v之間存在邊的條件是對于任意一個(gè)節(jié)點(diǎn)w，u 到v的距離要小于或等于u到w或是v到w的距離的最大 值，用下式表示： ),(),(max),(:,wvdwudvudvuw n節(jié)點(diǎn)u，v之間存在邊的條件是在以d(u， v)為直徑的圓中沒有其它節(jié)點(diǎn)，用下式 表示： ),(),(),(:, 222 wvdwudvudvuw 一個(gè)數(shù)據(jù)分組從節(jié)點(diǎn)y到達(dá)節(jié)點(diǎn)x； 下一條邊的選擇： 下一邊是以x為頂點(diǎn)，沿(x，y)逆時(shí)針方向上的第一條邊，圖 中為(x，z) 后續(xù)各邊同樣依次法則確定 n平面圖的邊將整個(gè)圖分 成許多小的互不重疊的 有界多邊形和一些無界 區(qū)域，這些有界多邊形

21、 和無界區(qū)域統(tǒng)稱為face。 n其中，有界區(qū)域稱為內(nèi) 部face，無界區(qū)域稱為 外部face。圖中xD通過3 個(gè)有界face和一個(gè)無界 face。 數(shù)據(jù)包在x點(diǎn)進(jìn)入邊界轉(zhuǎn)發(fā)模 式，通過face邊界向目的節(jié) 點(diǎn)D轉(zhuǎn)發(fā)，這些face都被xD穿 越； 轉(zhuǎn)發(fā)邊的選擇采用右手法則， 初始邊為xD； 數(shù)據(jù)包在同一個(gè)face中轉(zhuǎn)發(fā) 時(shí)采用右手法則，當(dāng)碰到與 xD相交的邊時(shí)，進(jìn)行face切 換，進(jìn)入下一個(gè)face； n優(yōu)點(diǎn) 采用局部最優(yōu)的貪婪算法，不需要維護(hù)網(wǎng) 絡(luò)拓?fù)洌酚砷_銷?。?可適用于靜態(tài)和移動(dòng)的WSN網(wǎng)絡(luò)； n缺點(diǎn) 需要地理位置信息的支持； 需要維護(hù)鄰居節(jié)點(diǎn)位置信息； nGRA（Geographica

22、l Routing Algorithm)： 發(fā)生局部優(yōu)化問題時(shí)通過泛洪查找到目的節(jié)點(diǎn)的路由 nf-GEDIR(f表示泛洪)和c-GEDIR ： 發(fā)生局部優(yōu)化問題，采用盡最大努力發(fā)送的方式： f-GEDIR：向所有鄰節(jié)點(diǎn)廣播該分組 c-GEDIR：選擇部分鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)該分組 收到數(shù)據(jù)包的節(jié)點(diǎn)繼續(xù)使用GPSR協(xié)議轉(zhuǎn)發(fā)該數(shù)據(jù)分組 n2-hop GEDIR ： 節(jié)點(diǎn)保存一跳和兩跳范圍鄰居節(jié)點(diǎn)的位置信息 nMFR(Most Forward within Radius)： 使到目的節(jié)點(diǎn)的 跳數(shù)最少 nNFP(Nearest with Forward Progress)： 使節(jié)點(diǎn)之間干擾 最少 nCR(Com

23、pass Routing) ： 減小數(shù)據(jù)傳輸范 圍 GEAR GEAR ： Geographic and Energy Aware RoutingGeographic and Energy Aware Routing n應(yīng)用 建立到特定區(qū)域的路由 查詢工作方式 n前提 已知目標(biāo)區(qū)域的位置信息 節(jié)點(diǎn)知道自己位置信息和剩余能量 節(jié)點(diǎn)間無線鏈路是對稱的 n分兩個(gè)階段： 查詢消息到達(dá)目的區(qū)域的路徑 查詢消息在目標(biāo)區(qū)域的傳播 n選路依據(jù) 節(jié)點(diǎn)到查詢區(qū)域通信能量能耗 節(jié)點(diǎn)本身的剩余能量 最小代價(jià)節(jié)點(diǎn)為轉(zhuǎn)發(fā)節(jié)點(diǎn) n查詢命令傳送到目標(biāo)區(qū)域 貪婪算法選擇鄰居 節(jié)點(diǎn)到達(dá)指定區(qū)域的代價(jià) 估計(jì)代價(jià)： F(Ni ,R)

24、=Distance( Ni , R) + (1)Left_Enery(Ni ) 實(shí)際代價(jià)： F(Ni ,R)=Enery_Cost(Ni ,R)+(1)Left_Enery(Ni ) Ni為有轉(zhuǎn)發(fā)需求的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，R為目標(biāo)區(qū)域的中心位 置。當(dāng)N不知道Ni的實(shí)際代價(jià)時(shí)使用估計(jì)代價(jià)。 n查詢在監(jiān)測區(qū)域內(nèi)傳送：洪泛方式，迭代地理轉(zhuǎn)發(fā) n將目標(biāo)區(qū)域分解為若干子區(qū)域、 向子區(qū)域的中心位置轉(zhuǎn)發(fā)） n路由空洞 鄰居節(jié)點(diǎn)傳輸代價(jià)都比本地節(jié)點(diǎn)大； 選擇鄰居節(jié)點(diǎn)中代價(jià)最小的作為轉(zhuǎn)發(fā)節(jié)點(diǎn)； 修改本地節(jié)點(diǎn)的轉(zhuǎn)發(fā)代價(jià)； F(N ,R)= F(Nmin,R)+C(N,Nmin) ， C(N,Nmin)表示將數(shù)據(jù)包從N

25、傳送到Nmin的代價(jià) n優(yōu)點(diǎn) 利用了位置信息，避免了查詢消息的Flooding； 考慮了消耗的能量和節(jié)點(diǎn)剩余能量，均衡消息； 路徑選擇可達(dá)到局部最優(yōu)； 迭代地理轉(zhuǎn)發(fā)對洪泛機(jī)制的補(bǔ)充； n缺點(diǎn) 可能出現(xiàn)路由空洞（局部信息）- 兩跳信息； 不適合在移動(dòng)WSN使用 n現(xiàn)階段WSN路由設(shè)計(jì)主要關(guān)注下面幾個(gè) 方面 提高能量效率，實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載的平衡，延 長網(wǎng)絡(luò)生存時(shí)間； 滿足各種應(yīng)用場景的參數(shù)指標(biāo)(也就是 QOS)； 實(shí)現(xiàn)一定程度的數(shù)據(jù)安全性。 Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks n需要解決的問題 多源單匯數(shù)據(jù)流遠(yuǎn)遠(yuǎn)大于控制流 離匯聚節(jié)點(diǎn)近能量消耗快 需要解決流量和能量的均衡問題 n提出的方法 l最優(yōu)移動(dòng)策略 Sink節(jié)點(diǎn)在網(wǎng)絡(luò)外邊 界移動(dòng)，左圖為圓形 網(wǎng)絡(luò)模型，灰色區(qū)域 是Sink節(jié)點(diǎn)移動(dòng)區(qū)域。 匯聚節(jié)點(diǎn)移動(dòng) B為Sink