電子地圖無線傳感器的估算范文

本站小編為你精心準備了電子地圖無線傳感器的估算參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

無線傳感器網絡地理位置路由算法研究

1地理位置路由算法

基于地理位置信息路由算法的核心思想是通過節點的地理位置信息來實現路由。在地理位置信息路由中，節點之間相互通信，通過有效的定位算法獲取自身的地理位置信息。同時，每個節點在通信范圍內，獲取所有鄰居節點的地理位置信息。數據包轉發過程中，在當前節點的鄰居節點內，利用每個鄰居節點和目標節點的地理位置信息來選擇下一跳。由于只需鄰居節點的信息就可以實現數據包的傳輸，該路由機制具有很好的可擴展性和很強的適應網絡的動態變化性。在數據傳輸過程中，只有部分節點參與路由的選擇和數據的接收、發送，能有效減少網絡能源消耗，對延長網絡的生命周期有很大促進作用。同時，通過利用傳感器節點的地理位置信息對算法進行優化，可實現其他無線傳感器網絡路由算法無法實現的功能。近年來，定位模式的研究取得了重大發展，無線傳感網絡中的未知節點可以通過低成本的方式獲取到精確的地理位置信息。這表明，在無線傳感器網絡中，基于地理位置信息的路由很可能在所有路由方式中占據主體地位。

2地理位置路由算法的轉發機制

無線傳感器網絡的地理位置路由算法中，每個節點和鄰居節點進行hello包的通信，使每個節點都可以獲取到所有鄰居節點的地理位置信息，為選擇下一跳提供信息。當前節點根據鄰居節點的地理位置信息如何選擇下一跳路由，是無線傳感器網絡基于地理位置路由算法的主要研究方向。常見的轉發策略有MFR(ForwardwithinRadius)、GRS(GreedyRoutingScheme)、RPF(RandomProgress)、NFP(NearForwardProgress)以及CompassRouting等。其中，GRS即貪婪路由算法，是指在當前節點的鄰居節點內，選擇距離目標節點歐氏距離最近的節點作為下一跳。貪婪轉發由于其原理簡單、計算復雜度低，并且產生的路由路徑接近理想的最優路徑，成為在各種路由轉發策略中最有效、最常用的算法之一。

偽三維的地理位置無線傳感器網絡路由算法

1問題的提出

在三維無線傳感網絡中，S為源節點，D為目的節點，在S的所有鄰居節點內，節點C是距離節點D歐氏距離最近的節點。按照三維貪婪路由算法的轉發策略，S將選擇C作為數據發送的下一跳。這種基于歐氏距離的選路策略在三維空間內節點均勻分布的情況下，能夠保證最終數據傳輸路徑圍繞源到目的節點連線上下浮動，從而保證得到源到目的地的最短路徑。而實際應用中，傳感器節點通常分布在高低不平的曲面上，我們稱之為偽三維分布。取節點C到節點D的縱向剖面，如圖1所示，虛線圈表示節點信號傳輸范圍，節點C到節點D的歐氏距離CD由CA、AB和BD三部分組成，其中CA、BD為懸空，而AB穿越了地表。由于節點分布于地形表面，實際的傳輸路徑應該如圖1中虛線所示，只能沿起伏曲面進行傳播而無法沿著連線CD附近波動，因此偽三維環境下，基于歐氏距離的選路參考標準并不適用。以上分析表明，雖然節點C到目標節點D的歐氏距離最短，但沿起伏地勢表面的路徑長度可能大于其他鄰居節點到目標節點的沿起伏地勢表面路徑長度。為適應實際應用的需求，需提出在起伏地形環境下的新的距離計算方法，以獲得更為優化的端到端最短路徑長度

2起伏地勢上的最短路徑算法

2.1電子地圖

電子地圖是通過衛星遙感技術，對某一地區的地形信息以數字的形式存儲在介質上，其精度能夠達到厘米級。它包含的信息非常多，如道路、河流、建筑物標記、等高線等。在電子地圖上，位置信息通過一串x、y、z坐標表示。假設點p是電子地圖上的一個點，在x、y坐標已知的情況下，可以通過電子地圖得到點p的z坐標。

2.2算法思想

針對3.1中描述的三維貪婪路由算法在起伏地勢上利用歐氏距離作為節點下一跳選擇的不合理現象，本文提出偽三維的地理位置無線傳感器網絡路由算法，該算法采用起伏地勢上的近似最短路徑來替換歐氏距離。算法中利用空間取點的方式，在電子地圖表面選取離散點，這些離散點能整體反映電子地圖表面的起伏趨勢。計算相鄰離散點之間的空間歐氏距離，將相鄰關系映射到二維平面上，運用圖論中最短路徑計算方法，計算出電子地圖表面的離散點之間沿起伏地勢的近似最短路徑。因為這條路徑是在電子地圖上選取的離散點中產生，所以能很好的逼近沿電子地圖表面的最短路徑。當傳感器節點撒在電子地圖描繪的區域時，節點根據自身的地理位置坐標找到與自身最近的那個離散點，根據離散點之間的最短距離來逼近在實際起伏地勢上的最短路徑，利用獲取的最短路徑進行下一跳的選擇。

2.3算法步驟

起伏地勢上最短路徑的計算步驟如下：①建立網格，從電子地圖上獲取離散點。截取需要建立傳感器網絡區域的電子地圖，根據獲取的電子地圖，在電子地圖的垂直投影面上按照X方向和Y方向建立正方形網格。將這些網格交點沿垂直方向獲取與電子地圖的交點，每個交點的X坐標和Y坐標在建立網格時按照電子地圖的長和寬等間隔獲取。而Z坐標則由網格交點的垂線和電子地圖相交時確定。如圖2所示，這些與電子地圖相交所得的離散點可以反映出電子地圖的基本形狀。

②確定電子地圖上交點之間的相鄰關系。電子地圖上的交點投影到XY面是一些按正方形網格分布的離散點，如圖3所示。在投影的平面圖上，每個點只與周圍的8個點為相鄰點，而且規定每個點只計算與其相鄰點之間的距離，例如投影點a只與投影點b、c、d、e、f、g、h、k存在相鄰關系，那么在計算電子地圖上的空間點''''a與其相鄰點之間的距離時，只計算空間點a''''與空間點b''''、c''''、d''''、e''''、f''''、g''''、h''''、k''''之間的距離（空間歐氏距離）。

③將三維空間中的點映射到二維平面并根據各點的鄰接關系建立鄰接矩陣。在投影面上，每個相鄰投影點之間記錄對應空間相鄰點之間的歐氏距離，把空間的各相鄰點之間的距離問題轉化為二維圖上的點與點之間的距離以及鄰接問題。建立鄰接矩陣——矩陣的行數和列數都為空間中點的個數或者投影點個數，i和j為點的序號，矩陣元素ija表示投影點i到投影點j的距離，如果i與j相鄰，則ija表示鄰接距離；若不鄰接，則ija為-1。以節點a為例，除了與之相鄰的點b、c、d、e、f、g、h、k的鄰接距離為L1、L2、L3、L4、L5、L6、L7、L8外，與其他點之間的鄰接距離都為-1，如圖3所示。

④利用圖論方法尋找最短路徑。對于已建立的鄰接矩陣，運用圖論中的Dijkstra最短路徑算法來計算投影面上任意兩點之間的最短路徑，計算結果就是在電子地圖上選取的對應兩點之間在起伏地勢上的近似最短路徑。因此，通過轉化到平面圖中計算兩點之間的最短路徑，從本質上對空間中相應的兩個點之間沿電子地圖表面的最短路徑進行了逼近。

⑤將實際傳感器節點的地理位置映射到對應離散點并獲取最短路徑。實際的傳感器節點已知自身的地理位置，可以依靠節點的X和Y坐標來定位到最相近的離散點上。知道了目標傳感器節點對應的離散點和當前傳感器節點對應的離散點，最短路徑就可以用離散點之間的最短路徑來逼近。

3傳感器節點沿起伏地勢下一跳的選擇策略

以下將對三維貪婪路由算法的空間距離選擇和本文提出的偽三維的地理位置無線傳感器網絡路由算法的沿起伏地勢最短路徑選擇分別進行說明。

3.1空間距離選擇下一跳

利用空間歐氏距離來選擇下一跳的流程：源節點S向目標節點D轉發數據時，首先獲取當前節點的所有鄰居節點的地理位置信息，然后判斷目標節點是否在它的鄰居節點內。如果目標節點在鄰居節點內，直接將數據發送給目標節點；否則，根據鄰居節點的地理位置信息，從鄰居節點中選取離目標節點空間歐氏距離最近的那個節點作為下一跳，直到將數據分組傳到目的節點。

3.2起伏地勢上的最短路徑選擇下一跳

因為電子地圖上的采樣點是均勻、有規律分布的，所以當傳感器節點在電子地圖上均勻分布時，可以很好的定位到采樣點上。但當傳感器節點在起伏地勢隨機分部時，必須采取一定的定位策略使節點定位到最近的采樣點上，以此來逼近當前節點到目標節點在起伏地勢上的最短路徑。本文在后面的仿真實驗中采用四點最近定位的方法將節點定位到采樣點上。具體方法描述如下：根據傳感器節點自身的地理位置坐標，尋找到包含這個節點的由四個采樣點構成的網格。分別對這四個采樣點求到目標節點采樣點在起伏地勢上的最短路徑，取路徑最短的那個采樣點作為這個傳感器節點對應的采樣點。當有多個鄰居節點定位到同一采樣點時，采用空間歐氏距離的方式作為下一跳的選擇。

無線傳感器網絡路由過程中，利用沿起伏地勢最短路徑選擇下一跳的流程如圖4所示。源節點S向目標節點D轉發數據時，首先獲取所有鄰居節點的地理位置信息，然后判斷目標節點是否在它的鄰居節點內。如果目標節點在鄰居節點內，直接將數據發送給目標節點；否則，對當前節點和其鄰居節點以及目標節點采用四點最近定位映射到采樣點。尋找鄰居節點采樣點中距離目標節點采樣點路徑最短的那個采樣點。當有多個鄰居節點對應到該采樣點時，用空間歐氏距離的方式選擇下一跳，否則選取該采樣點對應的鄰居節點作為下一跳。重復以上步驟，直到將數據傳到目標節點。

仿真實驗

1仿真環境的構建

本文選用MATLAB軟件進行仿真環境的構建。在1000m×1000m的范圍內，以100m為間隔構建高度不同的空間離散點，用這些點來模擬電子地圖的起伏趨勢；然后用MATLAB將這些離散空間點擬合成面，構建出電子地圖。

2實驗仿真數據的對比與分析

路由過程中數據包經過的節點數即路由跳數是衡量無線傳感器網絡路由協議的重要指標。在路由過程中所經歷的節點數越少，越能減少網絡的能量消耗，延長網絡的生存時間。所以，本文以路由跳數為指標，對比三維貪婪路由算法，來衡量偽三維的地理位置無線傳感器網絡路由算法的優劣性。本仿真實驗中，對于無線傳感器網絡節點的布采用理想均勻分布和隨機分布兩種分布方式。以下分別對在這兩種分布下，對三維貪婪路由算法和偽三維的基于地理位置的無線傳感器網絡路由算法進行分析比較。

2.1理想均勻分布傳感器節點

理想均勻分布的傳感器節點采用和電子地圖采樣點相同的x坐標和y坐標，在電子地圖上獲取z坐標。采用該分布方式，可以在路由過程中避免節點定位到采樣點時帶來的誤差，從而可以直接分析和比較兩種路由算法的優劣性。設定采樣間隔（網格大小）為10m，從節點1到節點10200，分別對兩種路由算法進行仿真。圖5是兩種路由算法下路由跳數的對比圖。其中，紅色曲線表示采用空間歐氏距離選擇策略的三維貪婪路由算法的路由跳數，藍色曲線表示采用起伏地勢最短路徑選擇策略的偽三維的地理位置無線傳感器網絡路由算法的路由跳數。從圖中可以看出，路由跳數隨著節點傳輸半徑的增大而減少，在傳輸半徑相同的情況下，偽三維的地理位置無線傳感器網絡路由算法的路由跳數明顯少于三維貪婪路由算法的路由跳數。通過仿真，在節點傳輸半徑為30m時，將節點1到節點10200在電子地圖上的路由軌跡顯示出來，如圖6所示。紅色曲線為三維貪婪路由算法下的路徑軌跡。可以看到它沒有考慮地勢狀況。藍色曲線為偽三維的地理位置無線傳感器網絡路由算法下的路徑軌跡。可以明顯看到，它有意識的避開了具有較大起伏的地勢，選擇了一條較為理想的路徑。

2.2隨機分布傳感器節點

沿電子地圖范圍內的x方向和y方向，在每隔10m的正方形內隨機的分布一個節點，從電子地圖上獲取節點的z坐標。這種分布的傳感器節點既可以體現出在整個電子地圖上的均勻分布，又能體現出在一定區域內的隨機分布。以下是在隨機分布的傳感器節點位置不變的情況下，對無線傳感器網絡中兩種路由算法的仿真。電子地圖上的采樣間隔越小，計算出來的最短路徑越和實際相接近。因此，采樣間隔是影響偽三維的地理位置無線傳感器網絡路由算法性能的重要因素。為更加全面的驗證該算法性能的優越性，分別選取不同的采樣間隔計算起伏地勢最短路徑，將使用該最短路徑進行路由的偽三維的地理位置無線傳感器網絡路由算法的仿真結果與三維貪婪路由算法的仿真結果進行對比。

分別取采樣間隔為10m、15m、20m，計算各采樣間隔下節點3到節點8997用偽三維的地理位置無線傳感器網絡路由算法和三維貪婪路由算法在不同傳輸半徑下的路由跳數。圖7是在不同的采樣間隔下兩種路由算法在不同傳輸半徑下路由跳數的仿真結果對比。三維貪婪路由算法使用空間歐氏距離選擇下一跳，與采樣間隔無關，因此，在不同采樣間隔下，三維貪婪路由算法的路由跳數相同。

圖7中，三維貪婪路由算法下的路由跳數用紅色曲線表示。以下從兩方面對該圖進行解釋：

⑴當節點傳輸半徑變化時，偽三維的地理位置無線傳感器網絡路由算法比三維貪婪路由算法的總體效果好得多。但當節點傳輸半徑為34m時，圖中采樣間隔為20m的偽三維的地理位置無線傳感器網絡路由算法的路由跳數略大于三維貪婪路由算法。假如計算得離目標節點近似路徑最短的節點為A，近似路徑次短的節點為B，而節點B的實際最短路徑要比節點A的實際最短路徑短，只是采樣間隔20m較大，在四點最近定位時造成的誤差很大，節點A定位到的那個采樣點要比節點B定位的采樣點到目標節點的采樣點的近似最短路徑短。根據算法思想，將數據包發送給節點A而不是節點B，造成路徑選擇偏差而導致路由跳數的增加。

⑵采樣間隔變化，傳輸半徑固定。總體效果是采樣間隔為10m時好于采樣間隔為15m和20m時。因為采樣間隔越小，計算出的近似最短路徑和實際最短路徑越接近。但有部分間隔10m的跳數略大于間隔為15m時的跳數。原因是隨著傳輸半徑的增大，鄰居節點增多，可選擇的下一跳增多。對于同一個節點，由于采樣為15m的四點最近定位范圍比采樣為10m的范圍大，所以節點在定位到采樣點時，可能會獲取到比10m更為優越的近似最短路徑，使采樣間隔為10m的路由跳數略大于采樣間隔為15m的路由跳數。通過以上仿真實驗可得出結論，對建立在起伏地勢上的無線傳感器網絡，在基于地理位置信息算法的基礎上，用起伏地勢上的最短路徑代替空間距離，能有效減少路由跳數，從而減少能量消耗，延長網絡生存時間。即本文體提出的偽三維的地理位置無線傳感器網絡路由算法比三維貪婪路由算法有較大優越性。

結束語

本文提出了適用于分布在起伏地勢上的無線傳感器網絡的偽三維的地理位置無線傳感器網絡路由算法。該算法的核心思想是用起伏地勢上的近似最短路徑代替空間歐氏距離，使基于地理位置的路由選擇更接近于實際的理想數據傳輸路徑。偽三維的地理位置無線傳感器網絡路由算法在起伏地勢上能有效減少源節點和目標節點之間的路由跳數，降低路由時延，進而減少節點的能量消耗，延長整個網絡的生存時間。

作者：解熒韓陽龍趙剛 于富財胡光岷單位：電子科技大學光纖傳感與通信教育部重點實驗室四川石化南充煉油廠