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