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