碩士學位論文無線傳感器網絡基于移動信標優化路徑的定位算法研究-資料下載頁

　　

【正文】 網絡，發送足夠的定位信息給未知節點以完成定位算法。目前應用于無線傳感器網絡的移動模型有S型、RWP(Random Way Point)模型和GaussMarkov模型等。這些模型是自組織網絡中廣泛應用的模型，RWP模型對信標的硬件要求小，路徑的隨機性大，并且隨著運動速度逐漸減小，運動軌跡出現在網絡中心區域的概率偏大。S模型則對硬件的要求相對較高。為此本文選擇GaussMarkov運動模型，該模型可以覆蓋網絡的大部分區域，相對于RWP模型，可以避免運動軌跡的突變和邊緣地帶概率減少的缺點[40] ，對硬件的要求也不高，其模型表示如下： () ()v(k)和d(k)表示運動時刻k移動信標的速度和方向。a是方向隨機調節參數，取值為0到1(0=a=1)，vmean, dmean為平均速度和平均運動方向,，代表高斯隨機變量。移動的下一時刻的速度和方向從當前的速度和方向求出： () ()信標節點按照GaussMarkov模型計算每個時刻的運動速度和方向，并由定位裝置獲取當前運動位置的坐標信息，將其廣播到網絡中。因為信標節點要周期性的廣播坐標信息，還要接收網絡中未知節點廣播回來的跳數累加的廣播分組，故在GaussMarkov模型中，設置一個計時器，計時周期為信標節點廣播坐標的周期，每當計時器時間到，移動暫停，廣播當前位置信息，并接收各未知節點返回的跳數廣播分組，記錄在列表中，再繼續移動?；谝苿有艠斯濣c算法的定位過程信標節點在網絡中移動，周期性地將位置信息廣播到網絡中，廣播的信息格式包括當前運動到第幾個點，當前位置坐標，網絡跳數(初始化為0)，在移動信標節點通信范圍的未知節點都接收到該位置的信標節點的定位數據包。每個節點接收到定位信息后，將其中的跳數值加1后繼續廣播。每個節點接收到多個鄰居節點的廣播值都與本身記有的值比較，如果小于自身記有的跳數值，則丟棄這個廣播分組。這一過程與DVHop定位算法相似，不同的是，未知節點判斷接收到的是第幾號位的信標節點廣播，如果為第一個就暫不廣播，直到接收到第二號位的信標廣播時，再把一號位的定位信息包廣播出去，并保存接收到的二號位廣播，等待下一位的廣播后再發送，以此類推。廣播定位信息的過程分為以下幾步：步驟1：移動信標在第一個位置取得當前位置信息，封裝位置信息廣播信息包{LIDi, xi, yi, HOPs}，LIDi表示當前是第幾號位置的廣播包，xi，yi表示當前位置坐標，HOPs為經歷的跳數，初始為0；步驟2：移動信標在第一個位置的通信范圍內所有鄰居節點接收到定位信息包，接收到信息包的節點將其與本身的數據包進行比較，取跳數較小的一項，并丟棄較大的，將跳數一項加1，記錄下這個跳數值，等待下一個定位信息包；步驟3：移動信標移動到下一個位置，將位置信息加1并廣播這個一新位置的定位信息包，同時接收各節點發回的廣播信息，取與前一位置最小跳數的分組，將兩位置的距離除以跳數計算出平均每跳距離(Di)并廣播到網絡中；步驟4：重復步驟3直到位置號達到預先設定的閾值K，K根據所需的虛擬信標密度而定，如果網絡中有N個未知節點，根據精度要求得出虛擬信標比例q，則；步驟5：節點根據接收到的各個虛擬信標的平均跳距離按權值進行校正，并根據記錄的跳數計算出到各個虛擬信標的距離，挑選出最優的虛擬信標節點距離信息，按優化的三邊測量法計算自己的位置。加權值法計算平均跳距離為了更準確的計算出估計的平均跳距離值，本文引入權值的概念，運用加權值對平均跳距離進行校正是基于網絡并非完全的均勻分布，各個節點接收到多個虛擬節點的平均跳距離值，越是靠近未知節點其平均跳距離值更能反映出未知節點所在的網絡區域的情況，對其平均跳距離的影響也越大，所以應當占有更大的權值，這樣比只計算平均值更接近真實值，計算出來的未知節點位置更精確。為了方便表達，我們假設網絡中的未知節點Nj接收到多個虛擬信標的平均跳距離值，虛擬信標Ai計算的平均跳距離記為Di，節點Nj到信標Ai的跳數為Hi。加權因子體現的是各個虛擬信標節點計算出來的平均跳距離值對未知節點計算平均跳距離值的影響力，假設未知節點N1接收到三個虛擬信標節點(A1,A2,A3)的平均跳距離值(D1,D2,D3)，而該節點查找表中所記的跳數值知道其距離三個虛擬信標的跳數分別為：H1，H2，H3。那么節點計算其平均距離值如下式： ()各個平均跳距離的權值相加為1，反映的是各個平均跳距離值對最終計算的跳距離值的影響程度，這樣計算節點Nj的平均跳距離值就為： ()至此，各未知節點已得到與各個虛擬信標的跳數，并可據此求出適合自己網絡區域內的平均跳距離值，因此可利用三邊測量法計算出未知節點Nj的坐標。 仿真分析為了驗證算法的性能，將提出的算法在OMNeT++平臺進行仿真，并用MATLAB進行實驗數據的輔助分析，在OMNeT++平臺上，將100個傳感器節點隨機分布在一個5050的區域中，節點通信半徑為10。網絡中還有一個可獲得自身位置的移動信標按GaussMarkov模型移動，平均速度為5，初始方向角設為90o，在邊緣區域時轉變系數，即式(4,5)中=，移動信標的廣播計算器設置為2秒，即移動信標節點每移動2秒后即在網絡中進行定位信息的廣播。為了使仿真結果更接近實際的情況，仿真結果是經過20次獨立仿真結果平均值獲得。定位精度與定位覆蓋率分析移動信標以預定的運動模型運動，并周期性的廣播定位信息包， 即虛擬信標的增長速度，虛擬信標越多，定位精度越高，所花的定位時間也越多，他們存在圖33中的關系。圖中所示的關系是顯然的，隨著時間的推移，移動信標在網絡中移動的距離越遠，廣播的定位信息越多，虛擬信標也越多，定位的誤差也隨之減小。同樣的，隨著移動信標的軌跡覆蓋了越多的地方，越來越多的未知節點獲得定位信息包而計算自己的位置，定位的覆蓋率也不斷增加。圖33定位誤差與定位覆蓋率 Localization error and Localization ratio信標節點廣播定位信息周期T的影響當移動信標節點以參數一定的GaussMarkov模型運動時，廣播周期越小，則虛擬信標越密，即單位區域內虛擬信標越多，必然導致節點通信消耗的增大，誤差也增大。當周期T增大到一定程序時，再增大，則廣播的定位信息大少，用于定位的虛擬信標大少，也會導致定位誤差的增大。最優的定位周期的大小由節點由通信半徑決定，當通信半徑越大時，廣播的周期也應相應的增大。在同樣的移動模型下，當廣播周期T變化時，定位誤差與其關系如下圖34所示：圖34移動信標廣播周期T與平均定位誤差 Broadcast Period T for Mobile Beacon and Average Positioning Error定位誤差比較算法的性能主要以定位的誤差來評價，移動信標以2秒的周期廣播定位信息包，即在網絡中構造一個虛擬信標。仿真結果的比較如圖35所示。圖35移動信標廣播周期T與平均定位誤差 Relationship between mobile beacon brocasting period and average position error 如圖35中可見，兩種定位算法的誤差隨著信標節點的增加都會減少，在信標節點越多的時候，本文提出的算法誤差減少更明顯，這是因為采用了加權處理來求各未知節點的平均跳距離，當一個節點獲得越多其周圍的虛擬信標計算的平均跳距離，加權處理后的平均跳距離就越接近真實的網絡情況。DVHop是一種經典的無需測距的定位算法，具有定位算法簡單，定位精度較高的優點，但其定位精度依賴于網絡連通狀況，對于各向同性的網絡，可以獲得較適當的定位精度，而對于不規則拓撲的網絡定位誤差則較大[41] 。DVHop算法在獲得平均每跳距離的計算過程中，節點之間的通信量過大，將網絡作為一個整體考慮，所有節點在計算自己與參考節點的距離時使用同一個平均跳距離，導致平均定位誤差較大。DVHop算法在網絡平均連通度為10，參考節點比例為10%的各向同性網絡中定位精度約為33%。該算法的缺點是僅僅在各向同性的密集網絡中，才能合理地估算平均每跳的距離[10] 。針對這種情況，提出了一種基于移動信標動態選擇的改進DVHop定位算法(DSBDVHop)，通過引入移動信標在網絡中按預定軌跡漫游，并在每個虛擬信標節點的位置單獨計算網絡各部位的平均跳距離后廣播其位置分組，未知節點記錄到每個虛擬信標的跳數，動態選擇能獲得最高計算精度的信標節點來進行三邊測量法計算自己的位置，減少無線傳感器網絡定位的成本，并且提高了定位精度。最后通過仿真證明此算法可以提高定位精度，減少算法的計算量，提高了定位的效率。 DVHop定位算法平均跳距離計算誤差來源分析在運行DVHop定位算法時，會先預定在網絡中進行洪泛的數據包的跳數，包含信標節點位置信息的數據包只經過預定的跳數。節點每接到一個數據包會在表示其生命周期的跳數加1，當達到預定的跳數時，則不再轉發這一數據包。在上述的DVHop定位算法的過程中，信標節點會根據他接收到的所有信標節點發來的數據包的信息計算平均每跳距離。當信標節點計算好自身網絡的平均跳距離后，把這個跳距離廣播到自己的網絡中，同樣制定了表示其生存周期的預定跳數。即在其指定跳數范圍內的未知節點會接收到這個平均跳距離的數據包。未知節點只記錄其接收到的第一個信標節點發來的平均跳距離，作為自己計算與信標節點的距離的依據。如圖36所示的情況中，我們可以看到：當某未知節點N接收到來自其周圍3跳距離內的信標節點的定位信息時，其列表中將有5個信標節點的位置及跳數。由圖中所示情況我們可以看到，信標節點A4和A5與未知節點的距離經過中間節點時“彎曲”的比其它信標節點要厲害些。如果按同樣的平均跳距離計算時，未知節點N與A4和A5的距離是要小于它到其它節點的距離。因此，在定位計算中，如果把A1, A2, A3, A4, A5都計算在內，其得到的誤差必然會增大，因為A4和A5兩個信標節點雖然都在A節點的兩跳通信距離內，在其實際距離并沒有平均跳距離的兩倍，從節點A到這兩個節點時傳輸的分組數據包是“曲折”的，而A1, A2和A3都是近似直線的。在定位計算過程中，當這種節點增多時，對于定位誤差的影響顯而易見。文獻[42] 通過實驗發現在這種條件下分析每一個未知節點定位的精度時，有些誤差達到200%。假設從圖36中得到的5個信標節點的列表中選擇三個信標節點的數據包分組來進行三邊定位計算，如果選擇不同的信標節點，對計算的誤差是顯而易見的。我們可以從中選取兩種組合來比較，如A3，A4和A5的組合和A1，A2和A3的組合。圖37是兩種組合下的計算情況的示意圖，從圖中我們可以看到，當A4和A5這兩個節點參與三邊定位計算時，其定位的誤差明顯增加。因此，設計移動信標的動態選擇算法來選擇最佳的虛擬信標的數據參與三邊定位計算，將直接影響其定位計算的精度。圖36 DVHop定位算法誤差來源分析 The resource of Localization error of DVHop (a). 選擇A1，A2和A3計算(a). Select A1, A2 and A3 to run trilateration algorithm(b) 選擇A3，A4和A5計算(b). Select A3, A4 and A5 to run trilateration algorithm圖37 選擇不同的信標節點進行三邊定位計算示意 Select diffirent beacon nodes for trilateration calculating帶有定位裝置的信標節點裝載在可移動的平臺或移動機器人上，就構造了一個移動信標，移動信標在一定規律的移動過程中，可實時獲取自身位置，并周期性的廣播自身的位置信息，以幫助未知節點進行定位。當未知節點獲得足夠多的虛擬信標的信息時，我們需要動態選擇最優的虛擬信標參與三邊定位計算來提高計算精度，本文接下從信標節點的移動模型，虛擬信標的動態選擇算法來分析如何選擇進行基于移動信標動態選擇的改進型DVHop定位算法。信標節點移動模型移動信標節點采用什么樣的方式移動才能盡可能的遍歷整個網絡，這個本身就是一個研究的熱點，網絡中傳感器節點本身是隨機散布的，節點位置本身信息是未知的，為了使這些節點全部進行定位，需要設計出一種運動模型，使移動信標的運動軌跡能在盡少的時間內遍歷網絡，發送足夠的定位信息給未知節點以完成定位算法。目前應用于無線傳感器網絡的移動模型有S型、RWP(Random Way Point)模型和GaussMarkov模型等。這些模型是自組織網絡中廣泛應用的模型，RWP模型對信標的硬件要求小，路徑的隨機性大，并且隨著運動速度逐漸減小，運動軌跡出現在網絡中心區域的概率偏大。S模型則對硬件的要求相對較高。，該模型可以覆蓋網絡的大部分區域，相對于RWP模型，可以避免運動軌跡的突變和邊緣地帶概率減少的缺點[6]，對硬件的要求也不高。信標節點按照GaussMarkov模型計算每個時刻的運動速度和方向，并由定位裝置獲取當前運動位置的坐標信息，將其廣播到網絡中。因為信標節點要周期性的廣播坐標信息，還要接收網絡中未知節點廣播回來的跳數累加的廣播分組，故在GaussMarkov模型中，設置一個計時器，計時周期為信標節點廣播坐標的周期，每當計時器時間到，移動暫停，廣播當前位置信息，并接收各未知節點返回的跳數廣播分組，記錄在列表中，再繼續移動定位算法過程信標節點在網絡中移動，周期性地將位置信息廣播到網絡中，廣播的信息格式包括當前運動到第幾個點，當前位置坐標，網絡跳數(初始化為0)，在移動信標節點通信范圍的未知節點都接收到該位置的信標節點的定位數據包。每個節點接收到定信息后，將其中的跳數值加1后繼