物聯(lián)網(wǎng)講座05-WSN路由協(xié)議

物聯(lián)網(wǎng)技術(shù)概論內(nèi)容提綱1WSN路由協(xié)議概要2WSN路由協(xié)議分類3WSN協(xié)議的主要最新成果物聯(lián)網(wǎng)技術(shù)概論1WSN路由協(xié)議概要物聯(lián)網(wǎng)技術(shù)概論1WSN路由協(xié)議概要作用：路由協(xié)議負(fù)責(zé)將數(shù)據(jù)從源節(jié)點(diǎn)(S)通過(guò)網(wǎng)絡(luò)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)(D)。功能：尋找源節(jié)點(diǎn)和目的節(jié)點(diǎn)的優(yōu)化路徑：公平高效、低延遲、避免擁塞、均衡網(wǎng)絡(luò)流量；將數(shù)據(jù)協(xié)議沿著路由協(xié)議正確轉(zhuǎn)發(fā)；設(shè)計(jì)目標(biāo)滿足應(yīng)用需求低網(wǎng)絡(luò)開(kāi)銷資源利用的整體有效性網(wǎng)絡(luò)高吞吐率節(jié)約能量物聯(lián)網(wǎng)技術(shù)概論WSN網(wǎng)絡(luò)特點(diǎn)特點(diǎn)自組織的網(wǎng)絡(luò)（隨機(jī)部署）數(shù)據(jù)的冗余性（多節(jié)點(diǎn)監(jiān)測(cè)同一事件）基于局部拓?fù)湫畔ⅲㄓ布拗疲┚W(wǎng)絡(luò)功能（數(shù)據(jù)收集）數(shù)據(jù)為中心物聯(lián)網(wǎng)技術(shù)概論WSN路由協(xié)議設(shè)計(jì)要求無(wú)線傳感網(wǎng)絡(luò)具有很強(qiáng)的應(yīng)用相關(guān)性，所以路由協(xié)議沒(méi)有一個(gè)通用的萬(wàn)能的協(xié)議，應(yīng)根據(jù)具體應(yīng)用來(lái)選擇路由協(xié)議。要求 能量高效（協(xié)議簡(jiǎn)單&節(jié)省能量&均衡消耗）可擴(kuò)展性（網(wǎng)絡(luò)范圍&節(jié)點(diǎn)密度）魯棒性（節(jié)點(diǎn)變化&拓?fù)渥兓┛焖偈諗啃造`活性物聯(lián)網(wǎng)技術(shù)概論WSN路由協(xié)議關(guān)鍵技術(shù)考慮網(wǎng)絡(luò)和節(jié)點(diǎn)能量?jī)?yōu)化（硬件限制）具有高可擴(kuò)展性（網(wǎng)絡(luò)規(guī)模&自組織）

適應(yīng)強(qiáng)網(wǎng)絡(luò)拓?fù)渥兓ü?jié)點(diǎn)移動(dòng)&無(wú)線信道）傳感器網(wǎng)絡(luò)路由中使用數(shù)據(jù)融合技術(shù)（數(shù)據(jù)為中心）傳感器網(wǎng)絡(luò)中流量分布不對(duì)稱（數(shù)據(jù)收集網(wǎng)絡(luò)&多源單Sink)物聯(lián)網(wǎng)技術(shù)概論WSN路由協(xié)議的挑戰(zhàn)自組織布撒（Adhocdeployment）能量消耗（Energyconsumption）路由精度（Routingaccuracy）計(jì)算能力（Computationcapabilities）通信能力（Communicationtolerance）容錯(cuò)能力（Faulttolerance）可擴(kuò)展性（Scalability）控制負(fù)載（Controloverhead）物聯(lián)網(wǎng)技術(shù)概論路由的性質(zhì)a)單播b)廣播c)多播d)任播e)k-任播物聯(lián)網(wǎng)技術(shù)概論2WSN路由協(xié)議分類物聯(lián)網(wǎng)技術(shù)概論WSN路由協(xié)議分類從具體應(yīng)用出發(fā)，進(jìn)行分類，大致可分類四類：能量感知路由協(xié)議基于查詢的路由協(xié)議地理位置路由協(xié)議Qos路由協(xié)議物聯(lián)網(wǎng)技術(shù)概論能量感知路由協(xié)議物聯(lián)網(wǎng)技術(shù)概論能量感知路由特點(diǎn)：從數(shù)據(jù)傳輸中的能量消耗出發(fā)，討論最優(yōu)能量消耗路徑以及最長(zhǎng)網(wǎng)絡(luò)生存周期。路由方式：根據(jù)節(jié)點(diǎn)的可用能量（PA，poweravailable）或傳輸路徑上的能量需求，進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)。節(jié)點(diǎn)的可用能量就是剩余能量。物聯(lián)網(wǎng)技術(shù)概論能量路由算法示意圖匯聚節(jié)點(diǎn)源節(jié)點(diǎn)a1=1a2=1a3=2a4=2a6=2a10=2a7=1a8=2a9=1a5=2A(PA=2)B(PA=2)C(PA=2)D(PA=3)E(PA=1)F(PA=4)路徑1：源-B-A-SINK，所有節(jié)點(diǎn)的PA之和為4，在該路徑上轉(zhuǎn)發(fā)分組需要能量之和為3;路徑2：源-C-B-A-SINK,所有節(jié)點(diǎn)的PA之和為6，在該路徑上轉(zhuǎn)發(fā)分組需要能量之和為6;路徑3：源-D-SINK,所有節(jié)點(diǎn)的PA之和為3，在該路徑上轉(zhuǎn)發(fā)分組需要能量之和為4;路徑4：源-F-E-SINK,所有節(jié)點(diǎn)的PA之和為5，在該路徑上轉(zhuǎn)發(fā)分組需要能量之和為6；物聯(lián)網(wǎng)技術(shù)概論路由策略分析路由策略：最大PA路由：路徑2的PA之和最大，但包含了路徑1，不是最優(yōu)解，應(yīng)選擇路徑4。最小能量消耗路由：路徑1能量消耗最小。最少跳數(shù)路由：選擇從源到匯聚節(jié)點(diǎn)的最小跳數(shù)路徑，選擇路徑3最大最小PA節(jié)點(diǎn)路由：路徑上每個(gè)節(jié)點(diǎn)的可用能量不同，從中選取每條路徑中最小能量的節(jié)點(diǎn)表示這條路徑的可用能量，最大最小路徑就是選擇可用能量最大的路徑。物聯(lián)網(wǎng)技術(shù)概論能量路由算法分析較好的解決了能量均衡問(wèn)題，延長(zhǎng)了網(wǎng)絡(luò)生存周期。算法的收斂性較好網(wǎng)絡(luò)負(fù)載未必均衡節(jié)點(diǎn)需要知道全局網(wǎng)絡(luò)信息，但WSN資源約束，節(jié)點(diǎn)只能獲得局部網(wǎng)絡(luò)信息。物聯(lián)網(wǎng)技術(shù)概論能量多路徑路由（1）傳統(tǒng)網(wǎng)絡(luò)的路由機(jī)制往往選擇從源到目的節(jié)點(diǎn)之間跳數(shù)最小的路徑，但是再WSN中，頻繁的使用同一條路徑傳輸數(shù)據(jù)，就會(huì)造成該路徑上的節(jié)點(diǎn)因能量消耗過(guò)快而過(guò)早失效，從而使網(wǎng)絡(luò)分割成互不相連的孤立部分，減少了網(wǎng)絡(luò)生存期。能量多路徑路由在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立多條路徑，根據(jù)路徑上節(jié)點(diǎn)的通信消耗及節(jié)點(diǎn)剩余能量情況，給每條路徑賦予一定概率，使數(shù)據(jù)傳輸均衡消耗網(wǎng)絡(luò)能量。物聯(lián)網(wǎng)技術(shù)概論能量多路徑路由（2）能量多路徑路由包括路徑建立、數(shù)據(jù)傳播和路由維護(hù)三個(gè)過(guò)程。每個(gè)節(jié)點(diǎn)需要知道到達(dá)目的節(jié)點(diǎn)的所有下一跳節(jié)點(diǎn)，并計(jì)算選擇每個(gè)下一跳節(jié)點(diǎn)的概率。概率的選擇根據(jù)節(jié)點(diǎn)到目的節(jié)點(diǎn)的通信代價(jià)來(lái)計(jì)算的，用Cost(Ni)表示節(jié)點(diǎn)i到目的節(jié)點(diǎn)的通信代價(jià)。節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑很多，這個(gè)代價(jià)值是加權(quán)平均值物聯(lián)網(wǎng)技術(shù)概論能量多路徑路由（3）過(guò)程描述如下：1）目的節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播路徑建立消息，啟動(dòng)路徑建立過(guò)程。路徑建立消息中包含一個(gè)代價(jià)域，表示發(fā)出該消息的節(jié)點(diǎn)到目的節(jié)點(diǎn)路徑上的能量信息，初始值為0.2）當(dāng)節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)的路徑建立消息時(shí)，相對(duì)發(fā)送該消息的鄰居節(jié)點(diǎn)，只有當(dāng)自己距源節(jié)點(diǎn)更近，而且距目的節(jié)點(diǎn)更遠(yuǎn)的情況下，才需要轉(zhuǎn)發(fā)該消息，否則丟棄該消息。3）如果節(jié)點(diǎn)決定轉(zhuǎn)發(fā)該消息，需要重新計(jì)算代價(jià)值替代原來(lái)的代價(jià)值。當(dāng)路徑建立消息從節(jié)點(diǎn)Ni到節(jié)點(diǎn)Nj時(shí)，該路徑的通信代價(jià)為節(jié)點(diǎn)Ni的代價(jià)值加上兩個(gè)節(jié)點(diǎn)間的通信代價(jià)，即：物聯(lián)網(wǎng)技術(shù)概論能量多路徑路由（4）4)節(jié)點(diǎn)要放棄代價(jià)太大的路徑，節(jié)點(diǎn)Nj將節(jié)點(diǎn)Ni加入本地路由表FTj的條件是：5）節(jié)點(diǎn)為路由表中每個(gè)下一跳節(jié)點(diǎn)計(jì)算選擇概率，節(jié)點(diǎn)的選擇概率與能量消耗成反比。節(jié)點(diǎn)Nj選擇公式如下：6）節(jié)點(diǎn)根據(jù)路由表中每項(xiàng)的能量代價(jià)和下一跳節(jié)點(diǎn)選擇概率計(jì)算本身到目的節(jié)點(diǎn)代價(jià)Cost(Nj)。Cost(Nj)定義為經(jīng)由路由表中節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)代價(jià)的平均值，即：物聯(lián)網(wǎng)技術(shù)概論能量多路徑路由性能分析將通信代價(jià)分散到多跳路徑上，實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的能量平穩(wěn)降級(jí)，最大限度的延長(zhǎng)網(wǎng)絡(luò)生存周期。維護(hù)代價(jià)太高，需要周期性的從目的節(jié)點(diǎn)到源節(jié)點(diǎn)實(shí)施洪泛查詢來(lái)維持所有路徑的活動(dòng)性。擴(kuò)展性不好，不適宜節(jié)點(diǎn)動(dòng)態(tài)加入和離去。物聯(lián)網(wǎng)技術(shù)概論基于查詢的路由定向擴(kuò)散路由（directeddiffusion,DD)謠傳路由（rumorrouting)物聯(lián)網(wǎng)技術(shù)概論定向擴(kuò)散路由匯聚節(jié)點(diǎn)通過(guò)興趣消息發(fā)出查詢?nèi)蝿?wù)，采用洪泛方式傳播興趣消息到整個(gè)區(qū)域或部分區(qū)域內(nèi)的所有傳感器節(jié)點(diǎn)。興趣消息采用表示查詢的任務(wù)，表達(dá)網(wǎng)絡(luò)用戶對(duì)監(jiān)測(cè)區(qū)域內(nèi)感興趣的信息，例如監(jiān)測(cè)區(qū)域的溫度、濕度等。在興趣消息的傳播過(guò)程中，協(xié)議逐跳地在每個(gè)傳感器節(jié)點(diǎn)上建立反向的從數(shù)據(jù)源到匯聚節(jié)點(diǎn)的數(shù)據(jù)傳輸梯度(gradient)。傳感器節(jié)點(diǎn)將采集到的數(shù)據(jù)沿著梯度方向傳送到匯聚節(jié)點(diǎn)。物聯(lián)網(wǎng)技術(shù)概論定向擴(kuò)散路由Sink節(jié)點(diǎn)向全網(wǎng)查詢興趣M建立源節(jié)點(diǎn)和Sink間路徑興趣在全網(wǎng)中擴(kuò)散對(duì)每一個(gè)活動(dòng)任務(wù)，Sink周期進(jìn)行查詢鄰居更新自己的興趣消息，并且轉(zhuǎn)發(fā)興趣消息中的條目時(shí)間戳：指示接收到相關(guān)興趣消息的最近時(shí)間若干梯度域：每個(gè)梯度和其鄰居節(jié)點(diǎn)相關(guān)聯(lián)每個(gè)梯度中含有一個(gè)指定的數(shù)據(jù)傳輸率持續(xù)時(shí)間：該興趣消息的有效期物聯(lián)網(wǎng)技術(shù)概論定向擴(kuò)散路由查詢消息的傳播—建立數(shù)據(jù)的傳輸梯度匯聚節(jié)點(diǎn)發(fā)送查詢消息興趣消息：任務(wù)性質(zhì)、數(shù)據(jù)采集/發(fā)送速率、時(shí)間戳等中間節(jié)點(diǎn)：記錄轉(zhuǎn)發(fā)梯度：表示了數(shù)據(jù)的傳輸方向定向擴(kuò)散路由路徑增強(qiáng)---匯聚節(jié)點(diǎn)在收到許多低速率數(shù)據(jù)后，向數(shù)據(jù)到達(dá)最快的鄰居節(jié)點(diǎn)發(fā)送增強(qiáng)消息，增強(qiáng)消息表示匯聚節(jié)點(diǎn)要求高速率的發(fā)送數(shù)據(jù)，相應(yīng)鄰居節(jié)點(diǎn)按照同樣的方式，一次傳遞增強(qiáng)信息給其鄰居節(jié)點(diǎn)，直到到達(dá)數(shù)據(jù)源，據(jù)此構(gòu)建數(shù)據(jù)發(fā)送的主路徑。DD適用持續(xù)性查詢的應(yīng)用而不適用于一次性查詢的應(yīng)用，代價(jià)較大。物聯(lián)網(wǎng)技術(shù)概論物聯(lián)網(wǎng)技術(shù)概論定向擴(kuò)散路由協(xié)議-路徑修復(fù)加強(qiáng)路徑上的節(jié)點(diǎn)可以觸發(fā)和啟動(dòng)路徑的加強(qiáng)過(guò)程新路徑C和源節(jié)點(diǎn)之間路徑斷裂物聯(lián)網(wǎng)技術(shù)概論定向擴(kuò)散路由協(xié)議分析優(yōu)點(diǎn)數(shù)據(jù)中心路由，定義不同任務(wù)類型/目標(biāo)區(qū)域消息；路徑加強(qiáng)機(jī)制可顯著提高數(shù)據(jù)傳輸?shù)乃俾剩恢芷谛月酚桑耗芰康木庀?；缺點(diǎn)周期性的洪泛機(jī)制---能量和時(shí)間開(kāi)銷都比較大；節(jié)點(diǎn)需要維護(hù)一個(gè)興趣消息列表，代價(jià)較大；物聯(lián)網(wǎng)技術(shù)概論DD協(xié)議族GBR路由(Gradient-BasedRouting)協(xié)議：梯度域擴(kuò)展（傳感器節(jié)點(diǎn)到Sink節(jié)點(diǎn)的跳數(shù)信息、無(wú)線鏈路評(píng)估信息）EAR(EnergyAwareRouting)路由協(xié)議建立路由過(guò)程中加入能量評(píng)估機(jī)制；路由路徑的能量開(kāi)銷大于某一閾值不采用；CADR路由(ConstrainedAnisotropicDiffusionrouting)協(xié)議興趣消息往指定方向發(fā)送物聯(lián)網(wǎng)技術(shù)概論謠傳路由傳感器節(jié)點(diǎn)采用代理消息，代理消息沿隨機(jī)路徑向外擴(kuò)散傳播，匯聚節(jié)點(diǎn)發(fā)送的查詢消息也隨機(jī)在網(wǎng)絡(luò)中傳播。物聯(lián)網(wǎng)技術(shù)概論謠傳路由工作原理1）每個(gè)傳感器節(jié)點(diǎn)維護(hù)一個(gè)鄰居列表和一個(gè)事件列表；事件列表包括事件名稱、跳數(shù)等，同時(shí)根據(jù)一定的概率產(chǎn)生一個(gè)代理消息。2）收到代理消息的節(jié)點(diǎn)，將代理消息和事件列表的表項(xiàng)做比較，根據(jù)跳數(shù)值決定更新代理消息或事件列表的表項(xiàng)。如本地事件列表無(wú)此表項(xiàng)，則將生存期減1，再隨機(jī)轉(zhuǎn)發(fā)。3）任何節(jié)點(diǎn)可以產(chǎn)生查詢消息4）查詢消息路徑和代理消息路徑的交叉節(jié)點(diǎn)沿查詢消息反向路徑建立連接。物聯(lián)網(wǎng)技術(shù)概論謠傳路由分析通過(guò)消息生存期解決環(huán)路問(wèn)題。避免了洪泛方式，減小了網(wǎng)絡(luò)開(kāi)銷隨機(jī)性強(qiáng)，不能做到優(yōu)化路由。物聯(lián)網(wǎng)技術(shù)概論地理位置路由物聯(lián)網(wǎng)技術(shù)概論地理位置路由在一些傳感器網(wǎng)絡(luò)的應(yīng)用中，不光要知道網(wǎng)絡(luò)中產(chǎn)生的事件，還需要知道事件產(chǎn)生的位置。如在森林防火中，不光需要知道發(fā)生了火災(zāi)，還需要知道在哪發(fā)生了火災(zāi)。地理位置路由假設(shè)節(jié)點(diǎn)知道自己的地理位置信息，以及目的節(jié)點(diǎn)和目的區(qū)域的地理位置信息。以地理位置信息作為路由依據(jù)。地理位置的精確度和代價(jià)相關(guān)，在不同的應(yīng)用中會(huì)選擇不同精確的位置信息來(lái)實(shí)現(xiàn)數(shù)據(jù)的路由轉(zhuǎn)發(fā)。物聯(lián)網(wǎng)技術(shù)概論GEAR路由協(xié)議應(yīng)用建立到特定區(qū)域的路由查詢工作方式前提已知目標(biāo)區(qū)域的位置信息節(jié)點(diǎn)知道自己位置信息和剩余能量節(jié)點(diǎn)直到鄰居節(jié)點(diǎn)的位置信息和剩余能量節(jié)點(diǎn)間無(wú)線鏈路是對(duì)稱的物聯(lián)網(wǎng)技術(shù)概論GEAR路由協(xié)議分兩個(gè)階段：查詢消息到達(dá)目的區(qū)域的路徑查詢消息在目標(biāo)區(qū)域的傳播選路依據(jù)節(jié)點(diǎn)到查詢區(qū)域通信能量能耗節(jié)點(diǎn)本身的剩余能量最小代價(jià)節(jié)點(diǎn)為轉(zhuǎn)發(fā)節(jié)點(diǎn)物聯(lián)網(wǎng)技術(shù)概論GEAR路由協(xié)議查詢命令傳送到目標(biāo)區(qū)域貪婪算法－選擇鄰居節(jié)點(diǎn)到達(dá)指定區(qū)域的代價(jià)估計(jì)代價(jià)：

F(Ni,R)=α?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à)。

物聯(lián)網(wǎng)技術(shù)概論GEAR路由協(xié)議查詢?cè)诒O(jiān)測(cè)區(qū)域內(nèi)傳送：洪泛方式，迭代地理轉(zhuǎn)發(fā)將目標(biāo)區(qū)域分解為若干子區(qū)域、向子區(qū)域的中心位置轉(zhuǎn)發(fā)）物聯(lián)網(wǎng)技術(shù)概論GEAR路由協(xié)議-路由空洞問(wè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傳送到Nmin的代價(jià)物聯(lián)網(wǎng)技術(shù)概論GEAR路由協(xié)議-路由空洞KLTFGHIJABCDES物聯(lián)網(wǎng)技術(shù)概論GEAR路由評(píng)價(jià)優(yōu)點(diǎn)利用了位置信息，避免了查詢消息的Flooding；考慮了消耗的能量和節(jié)點(diǎn)剩余能量，均衡消息；路徑選擇可達(dá)到局部最優(yōu)；迭代地理轉(zhuǎn)發(fā)對(duì)洪泛機(jī)制的補(bǔ)充；缺點(diǎn)可能出現(xiàn)路由空洞（局部信息）-兩跳信息；不適合在移動(dòng)WSN使用物聯(lián)網(wǎng)技術(shù)概論GPSR路由協(xié)議GPSR（greedyperimeterstatelessrouting）這是一個(gè)典型的基于位置的路由協(xié)議.使用GPSR協(xié)議,網(wǎng)絡(luò)節(jié)點(diǎn)都知道自身地理位置并被統(tǒng)一編址,各節(jié)點(diǎn)利用貪婪算法盡量沿直線轉(zhuǎn)發(fā)數(shù)據(jù).GPSR路由協(xié)議當(dāng)節(jié)點(diǎn)S需要向節(jié)點(diǎn)D轉(zhuǎn)發(fā)數(shù)據(jù)分組的時(shí)候，它首先在自己的所有鄰居節(jié)點(diǎn)中選擇一個(gè)距節(jié)點(diǎn)D最近的節(jié)點(diǎn)作為數(shù)據(jù)分組的下一跳，然后將數(shù)據(jù)傳送給它。該過(guò)程一直重復(fù)，直到數(shù)據(jù)分組到達(dá)目的節(jié)點(diǎn)D或某個(gè)最佳節(jié)點(diǎn)。利用節(jié)點(diǎn)的地理位置信息轉(zhuǎn)發(fā)節(jié)點(diǎn)選?。哼x擇鄰居節(jié)點(diǎn)中離目的節(jié)點(diǎn)更近的點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)物聯(lián)網(wǎng)技術(shù)概論物聯(lián)網(wǎng)技術(shù)概論局部?jī)?yōu)化問(wèn)題存在x到D的路徑x的鄰居w,y離D的距離比x大解決方法：邊界轉(zhuǎn)發(fā)物聯(lián)網(wǎng)技術(shù)概論邊界轉(zhuǎn)發(fā)平面圖：二維空間結(jié)構(gòu)；平面圖中任意兩條邊都只相交于頂點(diǎn)；GPSR算法中構(gòu)造平面圖的方法是刪除網(wǎng)絡(luò)拓?fù)鋱D中交叉的邊算法：RNG(RelativeNeighborhoodGraph)GG(GabrielGraph)物聯(lián)網(wǎng)技術(shù)概論平面圖講解下面的(a)、(b)、(c)、(d)為四個(gè)平面圖.數(shù)一數(shù),每個(gè)平面圖各有多少個(gè)頂點(diǎn)?多少條邊?它們分別圍成了多少個(gè)區(qū)域（內(nèi)部）?請(qǐng)將結(jié)果填入下表(按填好的樣子做).(2)觀察表格，推斷一個(gè)平面圖的頂點(diǎn)數(shù)、邊數(shù)、區(qū)域數(shù)之間有什么關(guān)系？

3)現(xiàn)已知某個(gè)平面圖有999個(gè)頂點(diǎn)，且圍成了999個(gè)內(nèi)部區(qū)域，試根據(jù)以上關(guān)系確定這個(gè)圖有多少條邊.平面圖的判斷平面圖判斷公式：（歐拉公式）面+定點(diǎn)-邊=2物聯(lián)網(wǎng)技術(shù)概論物聯(lián)網(wǎng)技術(shù)概論RNG節(jié)點(diǎn)u，v之間存在邊的條件是對(duì)于任意一個(gè)節(jié)點(diǎn)w，u到v的距離要小于或等于u到w或是v到w的距離的最大值，用下式表示：

物聯(lián)網(wǎng)技術(shù)概論GG節(jié)點(diǎn)u，v之間存在邊的條件是在以d(u，v)為直徑的圓中沒(méi)有其它節(jié)點(diǎn)，用下式表示：物聯(lián)網(wǎng)技術(shù)概論物聯(lián)網(wǎng)技術(shù)概論邊界轉(zhuǎn)發(fā)時(shí)的右手法則一個(gè)數(shù)據(jù)分組從節(jié)點(diǎn)y到達(dá)節(jié)點(diǎn)x；下一條邊的選擇：下一邊是以x為定點(diǎn)，沿(x，y)順時(shí)針?lè)较蛏系牡谝粭l邊，圖中為(x，z)后續(xù)各邊同樣依次法則確定物聯(lián)網(wǎng)技術(shù)概論Face平面圖的邊將整個(gè)圖分成許多小的互補(bǔ)重疊的有界多邊形和一些無(wú)界區(qū)域，這些有界多邊形和無(wú)界區(qū)域統(tǒng)稱為face。其中，有界區(qū)域稱為內(nèi)部face，無(wú)界區(qū)域稱為外部face。途中xD通過(guò)3個(gè)有界face和一個(gè)無(wú)界face。物聯(lián)網(wǎng)技術(shù)概論邊界轉(zhuǎn)發(fā)數(shù)據(jù)包在x點(diǎn)進(jìn)入邊界轉(zhuǎn)發(fā)模式，通過(guò)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；物聯(lián)網(wǎng)技術(shù)概論GPSR協(xié)議評(píng)價(jià)優(yōu)點(diǎn)采用局部最優(yōu)的貪婪算法，不需要維護(hù)網(wǎng)絡(luò)拓?fù)洌酚砷_(kāi)銷??；可適用于靜態(tài)和移動(dòng)的WSN網(wǎng)絡(luò)；缺點(diǎn)需要地理位置信息的支持；需要維護(hù)鄰居節(jié)點(diǎn)位置信息；物聯(lián)網(wǎng)技術(shù)概論基于Qos的路由物聯(lián)網(wǎng)技術(shù)概論基于Qos的路由無(wú)線傳感網(wǎng)絡(luò)的某些應(yīng)用對(duì)通信的服務(wù)質(zhì)量有較高要求，如高可靠性和實(shí)時(shí)性等；而由于網(wǎng)絡(luò)鏈路的穩(wěn)定性難以保證，通信信道質(zhì)量比較低，拓?fù)渥兓容^頻繁，要在無(wú)線傳感網(wǎng)絡(luò)中實(shí)現(xiàn)一定服務(wù)質(zhì)量的保證，需要設(shè)計(jì)基于Qos的路由協(xié)議?；诓幌嘟宦窂降亩嗦窂铰酚蓹C(jī)制SPEED協(xié)議物聯(lián)網(wǎng)技術(shù)概論基于不相交路徑的多路徑路由機(jī)制在WSN中，引入多路徑路由是為了提高數(shù)據(jù)傳輸?shù)目煽啃院蛯?shí)現(xiàn)網(wǎng)絡(luò)負(fù)載平衡。在多徑路由中，首要的問(wèn)題是解決如何建立源到目的地址的多跳路徑。主要思想：首先建立主路徑，再建立多跳備用路徑。數(shù)據(jù)從主路徑傳輸，同時(shí)利用備用路徑低速傳輸數(shù)據(jù)維護(hù)路由有效性。物聯(lián)網(wǎng)技術(shù)概論基于不相交路徑的多路徑路由機(jī)制物聯(lián)網(wǎng)技術(shù)概論纏繞多路徑局部纏繞多路徑：主路徑上的每一個(gè)節(jié)點(diǎn)（除兩頭節(jié)點(diǎn)外）都發(fā)送備用路徑增強(qiáng)消息給自己的次優(yōu)節(jié)點(diǎn)A，A尋找自己的最優(yōu)節(jié)點(diǎn)B，如果B不再主路徑上將繼續(xù)向自己的最優(yōu)路徑轉(zhuǎn)發(fā)，直到與主路徑相交。Speed協(xié)議物聯(lián)網(wǎng)技術(shù)概論物聯(lián)網(wǎng)技術(shù)概論SPEED協(xié)議SPEED是一個(gè)實(shí)時(shí)路由協(xié)議，在一定程度上實(shí)現(xiàn)了端到端的傳輸速率保證、網(wǎng)絡(luò)擁塞控制以及負(fù)載平衡機(jī)制。首先要求節(jié)點(diǎn)交換節(jié)點(diǎn)的傳輸延遲，以得到負(fù)載情況；然后利用局部地理信息和傳輸速率作出路由決定，同時(shí)通過(guò)鄰居反饋機(jī)制保證網(wǎng)絡(luò)傳輸速率在一個(gè)全局定義的傳輸速率閥值之上。物