【文章內(nèi)容簡介】 是可以滿足應(yīng)用需求的。我們將提出一種改進的粒子群算法，對DVHop算法進行優(yōu)化，以獲得更佳的定位精度。第四章 DVHop算法改進的定位技術(shù) DVHop算法的缺陷(1)下面介紹一下無線傳感器網(wǎng)絡(luò)中的bad節(jié)點；(i)圖41是第一類bad節(jié)點的示意圖，節(jié)點M為已知節(jié)點，其位置坐標(biāo)為已知，節(jié)點N是未知節(jié)點，其位置不確定，它可能在N1，也可能在N…Nn但它的一跳節(jié)點只能是M，則這樣的節(jié)點N被稱為 bad節(jié)點。圖41 第1類bad節(jié)點的示意圖圖42 第2類bad節(jié)點的示意圖(ii)圖42為第2類bad節(jié)點的示意圖，其中E，F(xiàn)為已知節(jié)點，它們的位置坐標(biāo)是已知的，節(jié)點N為未知節(jié)點，它的位置不確定可能出現(xiàn)在N1…Nn ，這個N個位置，但節(jié)點N的一跳節(jié)點為E或F(iii)圖43是第3類bad節(jié)點示意圖，其中節(jié)點M為已知節(jié)點，其位置坐標(biāo)是已知的，bad節(jié)點是節(jié)點群，該節(jié)點群的各個節(jié)點均為未知節(jié)點，通過該圖可以看出該節(jié)點群要同網(wǎng)絡(luò)進行通信，必須經(jīng)過節(jié)點M。圖43 第3類bad節(jié)點的示意圖(2) 利用已知節(jié)點間的平均每跳距離來代替未知節(jié)點與已知節(jié)點之間的跳數(shù)的實際測量值，顯然這種方法存在很大的誤差。(3)已知節(jié)點數(shù)量同其可監(jiān)測的面積成正比。而監(jiān)測覆蓋的面積又同節(jié)點的定位覆蓋率成正比。當(dāng)已知節(jié)點數(shù)目較少時，未知節(jié)點所要經(jīng)過的跳數(shù)就要隨之增多，才能通其進行通信，顯然這樣誤差就會增大。(4)在過程3的定位階段，使用三邊測量法進行估計待測節(jié)點的坐標(biāo)。這種測量方法存在一定的誤差。 DVHop算法的改進 DVHop算法的距離誤差校正在先前傳統(tǒng)算法中，將未知節(jié)點到已知節(jié)點的距離用已知節(jié)點間的平均每跳距離HopDisef乘以跳數(shù)代替，顯然那這種算法存在很大的誤差。而且事實上，未知節(jié)點到已知節(jié)點的距離并不是簡單的直線，多數(shù)情況下是曲線。步驟1已知節(jié)點將會利用廣播的形式將其各種信息發(fā)送給其它已知的節(jié)點，當(dāng)另一個已知節(jié)點收到該已知節(jié)點發(fā)送的信息后，就可以確定出它們之間的實際距離。計算出用RSSI測量的距離值與每跳距離的均值，則兩已知節(jié)點的總長度誤差校正值lenef，即為每跳均值與實際長度的差總長度誤差校正值的表達式為： （41）Disef：己知節(jié)點e到已知節(jié)點f動實際長度；disef：已知節(jié)點e到己知節(jié)點喲每跳長度和；注意e和 f不是同一個節(jié)點路徑損耗的分布模型： （42） （43）K0：接收點的參照長度（k0=1），K0：接收點的參照長度（k0=1），q：路徑損耗系數(shù)，它的取值在（2,4）內(nèi)Y0：0均值的高斯分布隨機變量。在公式（41）中，有以下成立： （44） （45）m為：己知節(jié)點e到已知節(jié)點f的總跳數(shù)HopDisef：己知節(jié)點e的平均每跳長度步驟2，各個未知節(jié)點到同一已知節(jié)點的長度并不相同，因而所產(chǎn)生的距離誤差也不同，不能夠使用統(tǒng)一的校正修正值來計算，因此求e到節(jié)點f的平均每跳誤差校正值avgeef： （46）M：已知節(jié)點e到己知節(jié)點f的總跳數(shù)是m在無線傳感網(wǎng)絡(luò)中，已知節(jié)點會將自己到其它已知節(jié)點的m、lenef、avgeef以廣播形式傳遞出去，當(dāng)另一個節(jié)點接收到這些數(shù)據(jù)后將會保存在一個路由表{IDk，xk，yk，hopk}內(nèi)，接著這個節(jié)點將會在將這些數(shù)據(jù)傳送給與它鄰近的抑制節(jié)點，不過跳數(shù)將變成m+1。當(dāng)已知節(jié)點得到跳數(shù)后，會將{IDk，xk，yk，hopk，mm、lenef、avgeef}中hopk新值同舊值進行對比。如果新的hopk值比舊的的hopk值小，則用其代替舊值若果新的hopk值比舊的的hopk值大，它將被舍棄。通過兩者的對比，即可得到未知節(jié)點到已知節(jié)點的最小長度。步驟3，利用以上兩步找到離待測節(jié)點最近的3個已知節(jié)點?；蚴嵌嘤?個，同時還要獲得這些已知節(jié)點的lenef值和avgeef值，通過這兩個值，即可得到待測節(jié)點到其與所有已知節(jié)點的長度利用上述方法求出待測節(jié)點w與己知節(jié)點e的距離Dwe: （47）M：待測節(jié)點w與已知節(jié)點e之間的總跳數(shù)avgeef：已知節(jié)點e、潤的平均每跳誤差校正值HopDise*M：待測節(jié)點w與已知節(jié)點e的每跳距離和 MINMAX方法與加權(quán)最小二乘法的結(jié)合MINMAX算法同傳統(tǒng)的三邊測量法相比，在求解未知節(jié)點的坐標(biāo)過程中，相對減少了浮點運算量。但其定位的精度要根據(jù)節(jié)點數(shù)量而定。不過當(dāng)已知節(jié)點數(shù)量較多時，其能量消耗及成本都將會有所提高所以此次采用MINMAX與加權(quán)最小二乘法相結(jié)合的算法。利用該方法主要分為兩部分:首先先利用MINMAX算法，進行待測節(jié)點位置的粗略求解然后利用加權(quán)最小二乘法求出估計待測節(jié)點的坐標(biāo)。(l)MINMAX算法圖44 為MINMAX算法示意圖，從圖中可以看出將將已知節(jié)點設(shè)為圓心，待測節(jié)點到它的估算值設(shè)為半徑，建立一個圓形，同時做一個外切于圓的正方形利用同樣的方法建立多個正方形，取它們的交集的幾何中心，該中心即為利待測節(jié)點的估算位置。圖44 MINMAX算法示意圖已知節(jié)點(xs，ys)的范圍由[(xsks)，(ysks)]*[(xs+ks)，(ys+ks)]得到。其中，ks指待測節(jié)點到己知節(jié)點的估算長度。交集范圍可由公式(48)求解出: （48）待測節(jié)點的估算位置是此交叉范圍的幾何中心，見公式（49）：（49） (2)加權(quán)最小二乘法求解待測節(jié)點的估算坐標(biāo)值： （410）ts(x)：是由有G個待測節(jié)點到已知節(jié)點的長度估算所構(gòu)造的值殘差方程注意上式只適用于不知道距離時進行估算。加權(quán)最小二乘的估算值: （411）ws：加權(quán)系數(shù)注意上式只有在知道所有的距離估計值時才可以使用。殘差方程的表達式如下: （412）(x，y)：待測節(jié)點的位置(xs，ys) ：已知節(jié)點的位置ks：度量的長度其中ts(x，y)是非線性函數(shù)，在求解它的過程時要用到非線性最優(yōu)化理論。線性化求解ts(x，y)的表達式，具體如下: （413） （414）式（413）減去式（414）之后，有以下方程組： （415）最終整理為： （416）設(shè)有以下方程組成立： （417）線性處理后，最小二乘的結(jié)果如下： （418）用矩陣可表示成： （419）加權(quán)最小二乘法（WLS）的估算坐標(biāo)是： （420）在公式（420）中， （421） （422） （423）為最小方差無偏估計的其判定的依據(jù)是W為對稱正定矩陣。當(dāng)時估算值的均方誤差最小。（M為長度誤差的方差矩陣）。在此階段，設(shè)已知節(jié)點的權(quán)值是1，它的取值范圍是[0，l]。，循環(huán)求精時。(3)定位過程過程1，主要是對待測位置進行粗略的估算。這一過程主要利用MINMAX算法。求出未知節(jié)點的粗略坐標(biāo)，同時引入了加權(quán)系數(shù)。過程2，利用加權(quán)最小二乘法來改變求的未知節(jié)點的精確坐標(biāo)。 改進算法的流程圖圖45和圖44分別為改進算法的已知節(jié)點程序流程圖和改進算法的未知節(jié)點程序流程圖，由圖可知未知節(jié)點和已知節(jié)點改進過的程序流程圖并不相同 。圖45 改進算法的已知節(jié)點程序流程圖圖46 改進算法的未知節(jié)點程序流程圖 DVHop算法流程圖該算法由三階段組成。具體實現(xiàn)見第3章的DVHop算法部分。在該算法中將會用到兩種重要的路由協(xié)議[9]：洪泛協(xié)議和距離矢量路由協(xié)議。（1）洪泛協(xié)議，是最簡單的路由協(xié)議，此協(xié)議中沒有任何路由算法。當(dāng)數(shù)據(jù)沒有達到目的節(jié)點時，節(jié)點會相其周圍的所有臨近節(jié)點廣播其所收到的數(shù)據(jù)。如果達到數(shù)據(jù)報的最大跳數(shù)還未傳到目的節(jié)點，也會停止廣播。洪泛協(xié)議的缺點是容易引起信息重疊，造成網(wǎng)絡(luò)擁塞。（2）距離矢量路由協(xié)議，是簡單路徑的分布式路由算法。每個節(jié)點維護一張到網(wǎng)絡(luò)中已知位置節(jié)點的距離估計和下一跳的路由表。每個節(jié)點只記錄到目的節(jié)點的跳數(shù)和通向目的節(jié)點的下一跳。節(jié)點接收到數(shù)據(jù)后，根據(jù)數(shù)據(jù)包頭部的目的地址來查找路由表，并將其轉(zhuǎn)發(fā)到下一跳所指定的節(jié)點。該算法的總體流程圖如下：圖47 網(wǎng)絡(luò)總體流程圖圖48 網(wǎng)絡(luò)流程圖圖49 錨節(jié)點模塊流程圖 仿真設(shè)計已知無線傳感器網(wǎng)絡(luò)的側(cè)重點，現(xiàn)在將要對進行節(jié)點定位的網(wǎng)絡(luò)做如下安排：以此類推 （1）無線傳感器網(wǎng)絡(luò)節(jié)點部署在二維的平面區(qū)域上，這樣未知節(jié)自身定位時僅需三個錨節(jié)點的位置和距離信息；以此類推要是三維空間則，則需要四個錨節(jié)點的位置和距離信息。（2）傳感器節(jié)點所采用的模型是自由空間電波傳播模型，該節(jié)點在一個圓內(nèi)進行通信。（3）傳感器節(jié)點可以感知其周圍存在的節(jié)點，并進行通信沒有限制。（4）兩個傳感器節(jié)點間它們的通信能力是對稱的，它們之間傳遞的消息都將可以正確接收。（5）由于種種限制，只有部分傳感器節(jié)點裝有定位裝置進而成為錨節(jié)點，但其他節(jié)點也具有這種處理能力。（6）節(jié)點擁有兩種不同的標(biāo)記：anchor、single，分別用來表示錨節(jié)點和無法定位的節(jié)點。參數(shù)設(shè)置如下：BorderLength：正方形區(qū)域的邊長，單位：mNodeAmount：網(wǎng)絡(luò)節(jié)點的個數(shù)BeaconAmount：信標(biāo)節(jié)點數(shù)Sxy：用于存儲節(jié)點的序號，橫坐標(biāo)，縱坐標(biāo)的矩陣Beacon：信標(biāo)節(jié)點坐標(biāo)矩陣，BeaconAmount*BeaconAmountUN：未知節(jié)點坐標(biāo)矩陣，2*UNAmountDistance：未知節(jié)點到信標(biāo)節(jié)點距離矩陣，2*BeaconAmountH：節(jié)點間初始跳數(shù)矩陣X：節(jié)點估計坐標(biāo)初始矩陣，X=[x，y]R：節(jié)點的通信距離，一般為10100在對定位算法進行仿真之前，首先對算法基于的網(wǎng)絡(luò)結(jié)構(gòu)和通信模型及有關(guān)參數(shù)進行定義。網(wǎng)絡(luò)結(jié)構(gòu)：假設(shè)一個二維無線傳感器網(wǎng)絡(luò)中有N個傳感器節(jié)點，它們均勻的隨機分布于一塊的正方形區(qū)域內(nèi)，無障礙或干擾，其中有一小部分節(jié)點坐標(biāo)已知（GPS定位或人工部署），稱為錨節(jié)點（Beacon Node）。通信模型：設(shè)定該節(jié)點的通信模型是以其自身為中心的圓，半徑為R；錨節(jié)點與未知節(jié)點的通信能力相同，通信半徑均為 R；節(jié)點間具有對稱的通信能力，發(fā)送和接收能力相同。 DVHop算法仿真程序仿真程序如下：%~~~~~~~~~~~~~~~~~~~~~~~~~ DVHop算法 ~~~~~~~~~~~~~~~~~~~~~~~~clear,close all。BorderLength=100。NodeAmount=200。BeaconAmount=20。UNAmount=NodeAmountBeaconAmount。R=60。% D=zeros(NodeAmount,NodeAm