無(wú)線傳感器網(wǎng)絡(luò)-GPSR課件

無(wú)線傳感器網(wǎng)絡(luò)GPSR路由協(xié)議研究論文鏈接：基于地理位置的路由協(xié)議一：引言二：基本思想三：信標(biāo)發(fā)送機(jī)制四：局部?jī)?yōu)化問(wèn)題五：邊界轉(zhuǎn)發(fā)六：擴(kuò)展分析七：優(yōu)缺點(diǎn)引言無(wú)線傳感器網(wǎng)絡(luò)(WSN)綜合了傳感器技術(shù)、嵌入式計(jì)算機(jī)技術(shù)、現(xiàn)代網(wǎng)絡(luò)及無(wú)線通信技術(shù)、分布式信息處理技術(shù)等,能夠通過(guò)各類集成化的微型傳感器協(xié)作地實(shí)時(shí)監(jiān)測(cè)、感知和采集各種環(huán)境或監(jiān)測(cè)對(duì)象的信息,這些信息通過(guò)無(wú)線方式被發(fā)送,并以自組多跳的網(wǎng)絡(luò)方式傳送到終端用戶,讓觀察者知道何時(shí)何地發(fā)生何種事情引言傳感網(wǎng)特點(diǎn)：電源能址有限性拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化性節(jié)點(diǎn)自組織性尋址以數(shù)據(jù)為中心通信能力有限，受外界干擾較大計(jì)算能力有限傳感器節(jié)點(diǎn)數(shù)量巨大、分布范圍廣、感知數(shù)量大引言協(xié)議棧結(jié)構(gòu)：感器網(wǎng)絡(luò)由物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、應(yīng)用層、能量管理平面、移動(dòng)性管理平而和任務(wù)竹理平面八個(gè)部分組成。引言數(shù)據(jù)量路層：傳感器節(jié)點(diǎn)的能耗四個(gè)來(lái)源：空閑偵聽(tīng)、沖突、串?dāng)_、控制開(kāi)銷網(wǎng)絡(luò)層路由協(xié)議：平面路由協(xié)議層次路由協(xié)議引言隨著定位技術(shù)的發(fā)展,節(jié)點(diǎn)可以方便地獲得自己的地理位置信息,地理位置路由就是以這些位置信息作為路由選擇的依據(jù),并按照一定的轉(zhuǎn)發(fā)策略把數(shù)據(jù)發(fā)送到目的節(jié)點(diǎn)。信標(biāo)發(fā)送機(jī)制GPSR周期性地向所有鄰居節(jié)點(diǎn)發(fā)送信標(biāo)(Beacon)信號(hào),來(lái)得到需要用到的鄰居節(jié)點(diǎn)的信息。該信標(biāo)信號(hào)中包含了節(jié)點(diǎn)的標(biāo)識(shí)和節(jié)點(diǎn)的地理位置信息,信標(biāo)采用廣播的方式發(fā)送,節(jié)點(diǎn)廣播域中所有的鄰居節(jié)點(diǎn)都會(huì)收到該信標(biāo)信號(hào)。GPSR采用了一種隨機(jī)選取信標(biāo)發(fā)送間隔的策略,一個(gè)節(jié)點(diǎn)前后兩次發(fā)送信標(biāo)的時(shí)間間隔在[0.5B,1.5B]上服從均勻分布,其中B為發(fā)送信標(biāo)的平均時(shí)間間隔。采用該方法,可以降低多個(gè)鄰居節(jié)點(diǎn)發(fā)送信標(biāo)信號(hào)時(shí)的沖突率。采用周期性地發(fā)送信標(biāo)信號(hào)地方式,可以檢測(cè)到是否有鄰居節(jié)點(diǎn)遠(yuǎn)離或者新節(jié)點(diǎn)的加入。邊界轉(zhuǎn)發(fā)空曠域問(wèn)題：由于X在空曠區(qū)域內(nèi)找不到離D更近的鄰居節(jié)點(diǎn)，因此它將盡力在空曠區(qū)域的外部尋找轉(zhuǎn)發(fā)節(jié)點(diǎn)以向D轉(zhuǎn)發(fā)數(shù)據(jù)分組，X節(jié)點(diǎn)將沿著空曠區(qū)域的邊界尋找到達(dá)節(jié)點(diǎn)D的路由。邊界轉(zhuǎn)發(fā)平面圖的構(gòu)造：使用邊界轉(zhuǎn)發(fā)的前提是要事先構(gòu)造一個(gè)平面圖來(lái)描述網(wǎng)絡(luò)拓?fù)?平面圖中任意兩條邊都不相交,GPSR算法中構(gòu)造平面圖的方法是刪除網(wǎng)絡(luò)拓?fù)鋱D中交叉的邊。對(duì)于網(wǎng)絡(luò)中所有節(jié)點(diǎn),假設(shè)一跳通信范圍半徑都為r,并且都位于同一平面內(nèi)。如果節(jié)點(diǎn)n和m的距離d(n,m)<r,則認(rèn)為n和m之間有一條邊(n,m)。邊界轉(zhuǎn)發(fā)平面圖構(gòu)造：算法要保證在刪除圖中的某些邊,使原圖成為RNG或GG時(shí)不會(huì)引起網(wǎng)絡(luò)分割。實(shí)際應(yīng)用中,生成平面圖需要采用分布式算法,每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都要運(yùn)行該算法,它僅僅需要知道附近的網(wǎng)絡(luò)拓?fù)湫畔?在GPSR算法中只需要知道一跳范圍內(nèi)的節(jié)點(diǎn)標(biāo)識(shí)和相關(guān)節(jié)點(diǎn)的位置信息)。邊界轉(zhuǎn)發(fā)平面圖構(gòu)造：RNG(RelativeNeighborhoodGraph)：RNG中節(jié)點(diǎn)u,v之間存在邊的條件是對(duì)于任意的一個(gè)節(jié)點(diǎn)w,u到v的距離要小于或等于u到w或是V到w的距離的最大值。邊界轉(zhuǎn)發(fā)平面圖構(gòu)造：GG(GabrielGraph)的定義如下:GIG中的節(jié)點(diǎn)U,v之間存在邊的條件是在以d(u,v)為直徑的圓中沒(méi)有其他節(jié)點(diǎn)。邊界轉(zhuǎn)發(fā)實(shí)現(xiàn)由RNG或GG建立的平面圖的邊將整個(gè)圖分成許多小的互不重疊的有界多邊形和一些無(wú)界區(qū)域,有界區(qū)域稱為內(nèi)部face,無(wú)界區(qū)域稱為外部face。邊界轉(zhuǎn)發(fā)時(shí)數(shù)據(jù)分組依次沿著這些face的邊界轉(zhuǎn)發(fā),在每個(gè)face中,依據(jù)右手法則選擇下一條邊。邊界轉(zhuǎn)發(fā)如果平面圖中沒(méi)有X到D的路徑,導(dǎo)致鏈路中斷的節(jié)點(diǎn)可能位于內(nèi)部face也可能位于外部face。GPSR規(guī)定不停地轉(zhuǎn)發(fā)數(shù)據(jù)分組直到其進(jìn)入導(dǎo)致鏈路中斷的節(jié)點(diǎn)所處的face,當(dāng)進(jìn)入該face后,由于沿該face的邊界找不到與XD相交的邊,因此數(shù)據(jù)分組不能進(jìn)入下一個(gè)face,它將沿著整個(gè)face邊界傳輸。當(dāng)數(shù)據(jù)分組第2次沿著e0(e0為數(shù)據(jù)分組進(jìn)入當(dāng)前face后的第一條邊)發(fā)送時(shí),就可以推斷目的節(jié)點(diǎn)不可達(dá),立即丟棄該數(shù)據(jù)分組,因此邊界轉(zhuǎn)發(fā)不會(huì)導(dǎo)致數(shù)據(jù)分組在相同的鏈路上傳輸兩次。邊界轉(zhuǎn)發(fā)數(shù)據(jù)分組進(jìn)入邊界模式時(shí),GPSR協(xié)議會(huì)將貪婪轉(zhuǎn)發(fā)失敗的位置Lp(節(jié)點(diǎn)位置)登記到數(shù)據(jù)分組中。邊界轉(zhuǎn)發(fā)過(guò)程中收到該數(shù)據(jù)分組的中間點(diǎn),首先比較Lp和自己的當(dāng)前位置,如果自己到目的節(jié)點(diǎn)的距離比Lp到目的結(jié)點(diǎn)的距離更近,就將該數(shù)據(jù)分組重新標(biāo)記為貪婪轉(zhuǎn)發(fā)模式,并按照貪婪模式進(jìn)行轉(zhuǎn)發(fā)。擴(kuò)展協(xié)議GRA（泛洪解決最佳主機(jī)問(wèn)題）GEDIR(GeographicDistanceRouting)GEDIR協(xié)議也可能出現(xiàn)局部?jī)?yōu)化問(wèn)題,若出現(xiàn)局部?jī)?yōu)化問(wèn)題,GEDIR直接丟棄該數(shù)據(jù)分組?？偨Y(jié)本文詳細(xì)描述了無(wú)線傳感器網(wǎng)絡(luò)地理位置協(xié)議GPSR的特性,當(dāng)貪婪算法遇到空曠域轉(zhuǎn)發(fā)數(shù)據(jù)分組失敗時(shí),就將貪婪轉(zhuǎn)發(fā)轉(zhuǎn)換為邊界轉(zhuǎn)發(fā),在空曠域的邊界尋找到達(dá)目的節(jié)點(diǎn)的路由,依據(jù)右手法則轉(zhuǎn)發(fā)數(shù)據(jù)分組,直到數(shù)據(jù)分組到達(dá)目的節(jié)點(diǎn)。在擴(kuò)展分析中闡述了貪婪算法的幾種機(jī)制和GPSR協(xié)議的幾個(gè)變種。GPSR協(xié)議是一種健壯的地理路由協(xié)議,隨著該