無線傳感器網路Dv-hop定位演算法

1.演算法原理

DV-Hop演算法的定位步驟如下：

（1）各錨節點向通信范圍內的鄰居節點廣播自身的位置資訊，接收節點則記錄到每個錨節點的最小跳數，同時忽略來自同一個錨節點的較大的跳數資訊，而后將跳數值加1轉發給鄰居節點，

（2）每個錨節點根據所記錄的其他錨節點的坐標資訊和跳數，通過式（1）估算網路平均跳距距離，
H o p S i z e i = ∑ j ≠ i ( x i ? x j ) 2 + ( y i ? y j ) 2 ∑ j ≠ i h o p S i j (1) HopSize_i=\frac{\sum_{j\neq i}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}}{\sum_{j\neq i }hopS_{ij}}\tag{1} HopSizei?=∑j?=i?hopSij?∑j?=i?(xi??xj?)2+(yi??yj?)2 ??(1)
式中， j j j為錨節點 i i i資料表中的其他錨節點號， h o p S i j hopS_{ij} hopSij? 為錨節點 i i i和 j j j??之間的跳數，

錨節點將所計算的平均跳距廣播至整個網路后，未知節點僅記錄所收到的第一個平均跳距，并向鄰居節點轉發，未知節點接收到平均跳距后，跟據所記錄的跳數資訊，按式（2）估算未知節點 i 到某個錨節點的距離：
L i = S i ? H o p S i z e (2) L_i=S_i*HopSize \tag{2} Li?=Si??HopSize(2)
（3）設 P 1 ( x 1 , y 1 ) , . . . , P n ( x n , y n ) P_1(x_1,y_1),...,P_n(x_n,y_n) P1?(x1?,y1?),...,Pn?(xn?,yn?)表示 n n n個錨節點的坐標位置，待定位節點D的位置為 ( x , y ) (x,y) (x,y) ，其與標節點估計距離分別為 d 1 , d 2 , . . . , d n ? 1 d_1,d_2,...,d_{n-1} d1?,d2?,...,dn?1?? ，可以建立式（3）的方程，
{ ( x 1 ? x ) 2 + ( y 1 ? y ) 2 = d 1 2 ( x 2 ? x ) 2 + ( y 2 ? y ) 2 = d 2 2 . . . ( x n ? x ) 2 + ( y n ? y ) 2 = d n 2 (3) \begin{cases} (x_1-x)^2+(y_1-y)^2=d_1^2\\ (x_2-x)^2+(y_2-y)^2=d_2^2\\ ...\\ (x_n-x)^2+(y_n-y)^2=d_n^2 \end{cases}\tag{3} ??????????(x1??x)2+(y1??y)2=d12?(x2??x)2+(y2??y)2=d22?...(xn??x)2+(yn??y)2=dn2??(3)
第一個方程組減去第后一個方程后，到得：
{ 2 ( x 1 ? x n ) x + 2 ( y 1 ? y n ) y = x 1 2 ? x n 2 + y 1 2 ? y n 2 ? d 1 2 + d n 2 2 ( x 2 ? x n ) x + 2 ( y 2 ? y n ) y = x 2 2 ? x n 2 + y 2 2 ? y n 2 ? d 2 2 + d n 2 . . . 2 ( x n ? 1 ? x n ) x + 2 ( y n ? 1 ? y n ) y = x n ? 1 2 ? x n 2 + y n ? 1 2 ? y n 2 ? d n ? 1 2 + d n 2 (4) \begin{cases} 2(x_1-x_n)x+2(y_1-y_n)y=x_1^2-x_n^2+y_1^2-y_n^2-d_1^2+d_n^2\\ 2(x_2-x_n)x+2(y_2-y_n)y=x_2^2-x_n^2+y_2^2-y_n^2-d_2^2+d_n^2\\ ...\\ 2(x_{n-1}-x_n)x+2(y_{n-1}-y_n)y=x_{n-1}^2-x_n^2+y_{n-1}^2-y_n^2-d_{n-1}^2+d_n^2\\ \end{cases}\tag{4} ??????????2(x1??xn?)x+2(y1??yn?)y=x12??xn2?+y12??yn2??d12?+dn2?2(x2??xn?)x+2(y2??yn?)y=x22??xn2?+y22??yn2??d22?+dn2?...2(xn?1??xn?)x+2(yn?1??yn?)y=xn?12??xn2?+yn?12??yn2??dn?12?+dn2??(4)
用線性方程組表示為 A L = b AL = b AL=b，其中，
A = [ 2 ( x 1 ? x n ) 2 ( y 1 , y n ) . . . . . . 2 ( x n ? 1 ? x n ) 2 ( y n ? 1 ? y n ) ] (5) A=\left[\begin{matrix} 2(x_1-x_n)&2(y_1,y_n)\\ ...&...\\ 2(x_{n-1}-x_n)&2(y_{n-1}-y_n) \end{matrix}\right]\tag{5} A=???2(x1??xn?)...2(xn?1??xn?)?2(y1?,yn?)...2(yn?1??yn?)????(5)

L = [ x y ] (6) L=\left[\begin{matrix} x\\ y\end{matrix}\right]\tag{6} L=[xy?](6)

b = [ x 1 2 ? x n 2 + y 1 2 ? y n 2 + d n 2 ? d 1 2 . . . x n ? 1 2 ? x n 2 + y n ? 1 2 ? y n 2 + d n 2 ? d n ? 1 2 ] (7) b=\left[\begin{matrix} x_1^2-x_n^2+y_1^2-y_n^2+d_n^2-d_1^2\\ ...\\ x_{n-1}^2-x_n^2+y_{n-1}^2-y_n^2+d_n^2-d_{n-1}^2 \end{matrix}\right]\tag{7} b=???x12??xn2?+y12??yn2?+dn2??d12?...xn?12??xn2?+yn?12??yn2?+dn2??dn?12?????(7)

采用最小二乘法得到方程組的解為:
L = ( A T A ) ? 1 A T b L=(A^TA)^-1A^Tb L=(ATA)?1ATb

2.演算法測驗

設定節點覆寫范圍為200x200，總節點數為：200，信標節點數20,通信半徑為30，未知節點數為180，采用歸一化平均定位誤差作為評價指標：
e r r o r = ∑ i = 1 m ( x i ? x i ? ) 2 + ( y i ? y i ? ) 2 k ? m ? r (8) error = \frac{\sum_{i=1}^m\sqrt{(x_i-x_i^*)^2+(y_i-y_i^*)^2}}{k*m*r}\tag{8} error=k?m?r∑i=1m?(xi??xi??)2+(yi??yi??)2 ??(8)
式中， m m m為未知節點的數目； k k k為實驗次數； r r r?為節點的通信半徑； ( x i , y i ) (x_i,y_i) (xi?,yi?)為未知節點的估計坐標； ( x i ? , y i ? ) (x_i^*,y_i^*) (xi??,yi??)為該未知節點的真實坐標，

基礎DV-hop的歸一化定位誤差：0.5384

3.參考文獻

[1]吳曦德,方杰,楊世杰,周慶標.基于GPSO-DVHop的傳感器節點定位方法[J].計算機工程與應用,2013,49(22):95-99.

[1]張恒. 無線傳感器節點定位方法的研究與實作[D].華南理工大學,2012.

4.Matlab代碼