無線傳感器網絡單元定位算法研究與實現畢業論文(編輯修改稿)

　

【文章內容簡介】 p算法 本章小結 由以上研究明顯可以得出：基于測距的定位算法有明顯的缺點。例如：使傳感器節點造價增高；消耗了有限的電池資源；在測量距離和角度的準確性方面需要大量的研究。而不基于測距的算法不需要知道未知節點到錨節點的距離或者不需要直接測量此距離，在成本和功耗方面比基于測距的方法具有優勢。19第4章 DVHop算法改進和MATLAB仿真 第4章 DVHop算法改進和MATLAB仿真 DVHop算法的缺陷(1)在無線傳感器網絡中，由于節點被隨機分布，所以會存在一些bad節點；(i)節點N在一跳之內僅存在1個節點。節點M的坐標是已知的，節點N在一跳之內，又僅知道節點M的位置。如圖41所示，節點N能夠出現在NN…Nn等任何一個地方。即可知，節點N的位置不唯一。換句話說，我們無法判斷節點N所在的地方。因此，稱節點N為bad節點。圖41 第1類bad節點的示意圖圖42 第2類bad節點的示意圖(ii)節點N在一跳之內僅存在2個節點。節點E、F的坐標是己知的，節點N在一跳之內又僅知道節點E和F的坐標。如圖42所示，節點N同樣也能夠出現在N這個地方。即可知，節點N無法確定其所在之處。換句話說，我們無法判斷節點N的具體坐標。因此，稱節點N為bad節點。(iii)bad節點是節點群。如圖43所示，節點M的坐標是已知的，假若此節點群經過節點M才能和網絡進行通信，并且這個節點群中不存在已知節點，則該群能夠在已知節點M的周圍轉動。換句話說，我們無法判斷它們所在的具體位置。因此，稱這個節點群中全部節點為bad節點。圖43 第3類bad節點的示意圖(2)待測節點與已知節點之間的每跳跳距，是用已知節點之間的平均每跳距離來表示的。每跳跳距的值不可能一樣，所以使用該方法會使誤差增大。(3)在已知節點數量不太多的情況下，可以監測到的面積也相對很少。監測覆蓋的面積越少，節點的定位覆蓋率也就越低。待測節點要和已知節點取得聯系，就一定要經過中間節點刁一可以取得聯系。因為己知節點數量不多，所以要讓它們之間可以通信，就會使得中間的跳數增多。隨著中間跳數的增多，引發的距離誤差也會相應地增大。(4)在過程3的定位階段，使用三邊測量法進行估計待測節點的坐標。用這個方法求出的坐標，存在一定的誤差，且定位精度不高。 DVHop算法的改進 DVHop算法的距離誤差校正在原始算法中，把已知節點間的平均每跳距離[30]HopDisef。看成是待測節點到已知節點的平均每跳距離。即待測節點到已知節點的距離等于平均每跳距離x跳數。但在真實的環境中，待測節點到已知節點的路程通常都是曲線，用原算法會產生較大誤差。步驟1，全部己知節點的坐標、跳數等內容，均以廣播形式發送給其它己知節點。在任意一個己知節點獲取了其它已知節點的數據后，就能夠依據2個已知節點的坐標，求解出它們之間的實際長度。計算出用RSSI測量的距離值與每跳距離和的均值，然后利用該均值與實際長度的差值，得到已知節點e、f的總長度誤差校正值lenef。假若己知節點e的平均每跳長度用HopDisef表示，已知節點e到f(e≠f）的總跳數是m，Disef已知節點e到己知節點喲每跳長度和，Disef己知節點e到已知節點動實際長度。總長度誤差校正值： （41）路徑損耗的分布模型： （42） （43）在公式（41）中，有以下成立： （44） （45）在公式（42）中與公式（43）中，K0：接收點的參照長度（k0=1），k：接收方到發送方的長度。PL(k0)：k0點的接收功率。q：路徑損耗系數，它的取值在（2,4）內。Y0：0均值的高斯分布隨機變量。步驟2，由于每個待測節點到已知節點的長度都不一樣，所以它們的距離誤差值也不一樣。故應該使用不一樣的誤差校正值來參與運算。假若已知節點e到己知節點1的總跳數是m，那么，e到動平均每跳誤差校正值avgeef是: （46）網絡內，所有已知節點把自身到其它已知節點的m、lenef、avgeef都廣播出去。使得任意一個已知節點都能得到其它已知節點的m、lenef、avgeef等值。己知節點一旦獲取到了其它已知節點的m、lenef、avgeef得值，就會把這些內容都保存在一個路由表{IDk，xk，yk，hopk}內。已知節點接著會給其它鄰居節點傳遞這些信息，同時給跳數值加一。在每個節點得到跳數之后，總是和{IDk，xk，yk，hopk，mm、lenef、avgeef}中的hopk舊值做對比。如果新的hopk值比舊的的hopk值小，則用 hopk的新值來代替{IDk，xk，yk，hopk，mm、lenef、avgeef}中的舊值；否則拋棄掉此信息。在這個過程中，同時進行了總長度誤差校正與平均每跳誤差校正。通過以上步驟，表明求出了待測節點與已知節點的最小長度。步驟3，通過前兩個步驟的信息傳遞，使得待測節點擁有了離它最近的3個已知節點或者大于3個已知節點的信息，該信息中包含總長度誤差校正值lenef與平均每跳誤差校正值avgeef。通過使用lenef值與avgeef值，待測節點即可得到其與所有已知節點的長度。假若已知節點e與比間有一個待測節點w，M表示待測節點w與已知節點e之間的總跳數，待測節點w與已知節點e的每跳距離和用HopDise*M表示，avgeef成示已知節點e、潤的平均每跳誤差校正值。求出待測節點w與己知節點e的距離Dwe: （47） MINMAX方法與加權最小二乘法的結合用三邊測量法求解待測節點的坐標，會產生一些誤差，同時產生的浮點運算量也相對高一些。MINMAX算法減少了浮點運算量，使它的計算代價變小。定位精度的高低主要取決已知節點數量的多少。增多了已知節點的數量，勢必引起了成本的提高，同時也增大了功耗。因此，用MINMAX與加權最小二乘法的結合方法，來替換三邊測量法。該方法主要有兩個過程:第一個過程，使用MINMAX算法，依據少許的已知節點坐標，來求解待測節點的粗略位置；第二個過程，使用加權最小二乘法進一步準確地估計待測節點的坐標。(l)MINMAX算法MINMAX算法用已知節點做圓心，把待測節點到此已知節點的長度估算值看作半徑，并創建此圓的外接正方形。用這些估算值、坐標創建一些正方形，找出正方形的交集，其幾何中心就是待測節點的估算位置。在平面坐標系中，若節點的通訊模型是圓，半徑是ks。估計節點的坐標時，把圓的外接正方形看成是它的通訊范圍，它在一跳內的最大通訊長度是(正方形的邊長是2ks)。如果未知節點的鄰居已知節點數是v，則它的坐標一定在這些已知節點通訊范圍的交集中，如圖44所示。圖44 MINMAX算法示意圖已知節點(xs，ys)的范圍由[(xsks)，(ysks)]*[(xs+ks)，(ys+ks)]得到。其中，ks指待測節點到己知節點的估算長度。交集范圍可由公式(48)求解出: （48）待測節點的估算位置是此交叉范圍的幾何中心，見公式（49）：（49） (2)加權最小二乘法有G個待測節點到已知節點的長度估算值，用此值構造的殘差方程是ts(x)。在無距離估算值的前提下，使用公式(410)，來求解待測節點的估算坐標值。 （410）假若知道了所有的距離估算值，則憑借這些值構造加權系數ws。因此，加權最小二乘的估算值是: （411）若待測節點的位置是(x，y)，已知節點的位置是(xs，ys)，度量的長度是ks，則殘差方程的表達式如下: （412）ts(x，y)是非線性函數，求解ts(x，y)的值，實際用非線性最優化來處理。線性化求解ts(x，y)的表達式，具體如下: （413） （414）式（413）減去式（414）之后，有以下方程組： （415）最終整理為： （416）設有以下方程組成立： （417）線性處理后，最小二乘的結果如下： （418）用矩陣可表示成： （419）加權最小二乘法（WLS）的估算坐標是： （420）在公式（420）中， （421） （422） （423）只有W是對稱正定矩陣，才能確定為最小方差無偏估計。在的情況下，估算值的均方誤差達到最低，其中M表示長度誤差的方差矩陣。在此階段，設已知節點的權值是1，它的取值范圍是[0，l]。，循環求精時。(3)定位過程過程1，該過程進行粗略估算位置。利用MINMAX算法，未知節點憑借鄰居已知節點的位置與通訊模型，根據公式 (410)，能夠求解出它所處的范圍。進一步使用公式(411)，可以估計出未知節點的粗略坐標，同時引入了加權系數。若公式 (410)求解得到的區域越小，則用公式 (411)估計的未知節點坐標就越準確，且權值同時也在增大。過程2，該過程是定位求精。節點利用加權最小二乘法來改變它的坐標等數據。在執行完過程1之后，其它未知節點都擁有了初始坐標。再使用加權最小二乘法進行循環求精，每改變一次未知節點的坐標，就需要把周邊節點的加權系數增大一次。隨著循環次數的不斷增多，未知節點的權值也在不斷增大，該值慢慢地朝己知節點的權值1接近。未知節點的權值一旦大于1，或者連續2次得到的坐標極其接近，則終止該循環步驟。在全部未知節點都執行了此過程時，即全部未知節點都己定位，本算法終止。 改進算法的流程圖在定位的過程中，己知節點與未知節點的執行步驟不一樣。因此，它們的程序流程圖也不一樣。已知節點的程序流程圖如圖(45)所示，未知節點的程序流程圖如圖(46)所示。圖45 改進算法的已知節點程序流程圖圖46 改進算法的未知節點程序流程圖 DVHop算法流程圖該算法由三階段組成。具體實現見第3章的DVHop算法部分。在DVhop算法中，使用到兩種重要的路由協議[9]：洪泛協議和距離矢量路由協議。（1）洪泛協議，是最簡單的路由協議，此協議中沒有任何路由算法。節點向它的所有鄰居節點廣播所收到的數據，直到數據到達目的節點或達到數據報的最大跳數。洪泛協議的缺點是容易引起信息重疊，造成網絡擁塞。（2）距離矢量路由協議，是簡單路徑的分布式路由算法。每個節點維護一張到網絡中已知位置節點的距離估計和下一跳的路由表。每個節點只記錄到目的節點的跳數和通向目的節點的下一跳。節點接收到數據后，根據數據包頭部的目的地址來查找路由表，并將其轉發到下一跳所指定的節點。DVHop算法由3個階段組成總體流程圖如下：圖47 網絡總體流程圖圖48 網絡流程圖圖49 錨節點模塊流程圖 MATLAB仿真環境簡介MATLAB[30]產品家族是美國Math Works公司開發的用于概念設計、算法開發、建模仿真和實時實現的理想的集成環境。由于其完整的專業體系和先進的設計開發思路，使得MATLAB在多種領域都有廣闊的應用空間。特別是在MATLAB的主要應用方向：科學計算、建模仿真以及信息工程系統的設計開發上。并且在這些方向上MATLAB已經成為行業內的首選設計工具。 在MATLAB產品家族中，MATLAB工具箱是整個體系的基座，它是一個語言編程型（M語言）開發平臺，提供了體系中其他工具所需要的集成環境（比如M語言的解釋器）。同時由于MATLAB對矩陣和線性代數的支持使得工具箱本身也具有強大的數學計算能力。MATLA產品體系的演化歷程中最重要的一個體系變更是引入了Simulink，用來對動態系統建模仿真。其框圖化的設計方式和良好的交互性，對工程人員本身計算機操作與編程的熟練程度的要求降到了最低，工程人員可以把更多的精力放到理論和技術的創新上去。 DVHop算法仿真結果分析根據無線傳感器網絡所關注的重點，我們對需要進行節點定位的無線傳感器網絡作如下設定：（1）無線傳感器網絡節點部署在二維的平面區域上，這樣未知節自身定位時僅需三個錨節點的位置和距離信息；如果是在三維空間條件下進行自身定位，則需要四個錨節點的位置和距離信息。（2）傳感器節點采用自由空間電波傳播模型，即節點的通信范圍一個圓。（3）傳感器節點能夠發現其鄰居節點，鄰居節點間可以自由通信。（4）傳感器節點間具有對稱的通信能力，通信半徑一致，并且所有的消息最終都可被正確接收。（5）只有一些傳感器節點通過配備GPS接收器或人工部署已經現定位，成為錨節點，其余其它節點則均具有相同的處理能力。（6）節點擁有兩種不同的標記：anchor、single，分別用來表示錨節點和無法定位的節點。參數設置如下：BorderLength正方形區域的邊長，單位：mNodeAmount網絡節點的個數BeaconAmount信標節點數Sxy用于存儲節點的序號，橫坐標，縱坐標的矩陣Beacon信標節點坐標矩陣，BeaconAmount*BeaconAmountUN未知節點坐標矩陣，2*UNAmountDistance未知節點到信標節點距離矩陣，2*BeaconAmounth節點間初始跳數矩陣X節點估計坐標初始矩陣，X=[x，y]R節點的通信距