基於優化平均每跳距離和優選錨節點的wsn定位方法
2023-10-09 14:41:49
基於優化平均每跳距離和優選錨節點的wsn定位方法
【專利摘要】為了降低定位誤差，提高定位精度，本發明深入研究了無線傳感器網絡中的定位算法。在DV-Hop定位算法的基礎上提出了一種基於優化平均每跳距離和優選錨節點的WSN定位方法。首先根據錨節點校正值的誤差及錨節點與未知節點間的跳數，對各錨節點的校正值歸一化加權處理，以優化未知節點的平均每跳距離。然後根據錨節點與未知節點間跳數，優選參與定位計算的錨節點，以避免誤差積累和減少計算量。最後，對於不同錨節點組合計算所得的定位坐標值進行歸一化加權優化，作為未知節點的最終定位坐標。仿真結果表明，本發明能夠充分利用錨節點信息，有效地降低節點平均定位誤差，提高定位覆蓋率。
【專利說明】基於優化平均每跳距離和優選錨節點的WSN定位方法
【技術領域】
[0001]本發明涉及一種基於優化平均每跳距離和優選錨節點的WSN定位方法，具體是一種基於優化未知節點的平均每跳距離和優選錨節點的加權與優選DV-Hop定位方法(WSDV-Hop)，屬於無線傳感器網絡定位【技術領域】。
【背景技術】
[0002]在無線傳感器網絡(wireless sensor network, WSN)研究的很多領域,往往必須知道節點的實際位置才有應用意義，在某些特殊應用場合數據所處的位置比數據本身更具價值，比如火災發生的位置、水位上升的水域以及軍事應用領域等，所以節點定位研究是必不可缺的環節。而全球定位系統GPS由於價格、功耗及體積等方面的制約，很難完全應用於WSN中。此外，一些已有的定位算法由於計算複雜度和需要相關硬體設備支持等原因，也不適用於WSN。因此，在資源受限的前提下，設計出高定位精度、計算量適中、無需額外硬體條件且適合實際WSN環境的節點定位方法具有現實意義。
[0003]目前，WSN的主要定位方法中依據是否需要測量節點間實際的距離可分為基於測距的算法和基於非測距的算法。基於測距的定位算法首先通過額外的裝置測量節點間的距離或角度，再計算未知節點的坐標，典型算法有:RSS1、T0A、TD0A、A0A等。基於非測距的定位算法只需要利用節點間跳數等信息並加以簡單運算就可以估計出節點間的距離，主要算法包括有質心、凸規劃、DV-Hop, MDS-MAP等。基於測距的算法總體上能取得較好的定位精度，但是所需成本、節點的能量消耗也會較大。基於非測據的算法依靠節點間的連通性進行定位，計算量小、實現簡單但定位誤差較大。通過研究與改進，不少已經可以滿足WSN的定位需求，其中DV-Hop是最備受:關注的算法之一。
[0004]DV-Hop算法實現簡單，通過節點的平均每跳距離、跳數進行定位計算就可以得到未知節點的坐標，算法成本低，計算和通信開銷適中，對硬體要求較低，適用於分布式網絡，擴展性好。但是DV-Hop算法也依然存在一些不足之處，比如算法中未知節點僅利用離它最近的錨節點的校正值作為平均每跳距離，會使節點間的估計距離和最終的定位計算產生較大的誤差；在定位計算時隨機選取的錨節點組合也會對定位精度造成較大的影響。
[0005]DV-Hop定位算法
[0006]DV-Hop算法的核心是利用節點間的估計距離代替實際測量距離，而估計距離則是通過未知節點與錨節點之間的跳數和平均每跳距離相乘來得到；然後通過估計距離和錨節點的坐標計算未知節點的定位坐標。DV-Hop算法由三個階段組成:
[0007]第一步:獲得節點間的最小跳數
[0008]錨節點以廣播的方式向鄰居節點發送包括跳數欄位的自身位置信息元組，跳數欄位的初值設為O。接收節點接收到該信息元組後將跳數加1，記錄下該錨節點的位置和跳數，並將該元組轉發給它的鄰居節點。若節點接收到多個來自同一錨節點的元組，則節點只保留跳數最小的元組信息。通過這種方法網絡中每個節點都能夠記錄下自己到每個錨節點的最小跳數，並獲得錨節點的位置信息。
[0009]第二步:估算未知節點與錨節點之間的距離
[0010]假設錨節點總數為m，其中任一錨節點Ai在獲得網絡中其餘錨節點坐標及與它們間的最小跳數後，可計算自己的平均每跳距離Ci,也稱為網絡校正值:
【權利要求】
1.一種基於優化平均每跳距離和優選錨節點的WSN定位方法，其特徵在於，該方法包括三部分: (1).優化平均每跳距離 未知節點可接收來自多個錨節點的校正值，然後對各校正值賦予不同的權值，權值大小由兩個因素決定，一是錨節點校正值誤差的大小，另一個是錨節點與未知節點間的跳數；最後對各錨節點校正值歸一化加權處理，得到平均每跳距離； (2).優選錨節點 未知節點優選出距離自己較近的一部分錨節點參與定位計算，使這些錨節點和未知節點之間的跳數值小於所有錨節點和該未知節點間的平均跳數； (3).優化定位坐標值 將通過不同錨節點組合計算得到的未知節點的坐標值都作為網絡中的候選坐標，通過加權優化計算出最優的坐標值；假設網絡中有η個未知節點，優選出的錨節點為m個，對於任一未知節點隊，u = 1,2,…n，在錨節點中隨機抽取三個可產生的組合為0種，使用三邊測量法計算得到節點坐標，記為Ek，k = \X-Xl，可作為Nu的候選定位坐標；對每個候選坐標，所賦予的權值大小根據其所採用的三個錨節點與所求未知節點間跳數之和來決定，跳數之和較小的賦予較大的權值，而對於跳數之和較大的則賦予較小的權值。
2.如權利要求1所述的基於優化平均每跳距離和優選錨節點的WSN定位方法，其特徵在於，優化平均每跳距離的具體步驟如下: (11)網絡中每個錨節點計算其與各錨節點間的最小跳數； (12)錨節點計算自己的校正值及校正值誤差，並將校正值及其誤差信息在全網廣播； (13)未知節點接收錨節點發出的信息，獲得距離錨節點的最小跳數，並根據校正值誤差大小和距錨節點的跳數對各錨節點校正值歸一化加權優化，作為平均每跳距離； 假設網絡中有M個錨節點，η個未知節點，未知節點Nu(u = 1，2，...，!!)，由公式⑴可以得到錨節點Ai的校正值Ci ；
式中，(Xi, Yi)，(Xj, Yj)分別是錨節點Ai和Aj的坐標軋是錨節點Ai和Aj之間的最小跳數； 由於兩個錨節點Ai和之間的實際距離為:
而錨節點Ai和Aj之間根據校正值得到的估算距離為:
Destij j = Ci Xhij (3) 那麼錨節點Ai校正值的誤差為:
假設未知節點Nu與錨節點Ai間的跳數記為hopu，i，那麼可以賦予錨節點Ai校正值的權值為:
然後根據各錨節點校正值和相應權值就可以加權計算出未知節點Nu的平均每跳距離:
通過歸一化加權處理，每個錨節點的權值各不相同，離未知節點跳數越小且自身校正值誤差越小的錨節點賦予的權值越大，同時使各錨節點校正值的權值之和為I。
3.如權利要求2所述的基於優化平均每跳距離和優選錨節點的WSN定位方法，其特徵在於，優選錨節點的具體步驟如下: 先求出未知節點Nu距離所有錨節點的跳數平均值；
當某個錨節點Ai與未知節點Nu的跳數大於平均跳數時，即
捨去該錨節點，而其餘未被捨棄的錨節點則可參與到定位計算，經過優選後的錨節點個數記為m。
4.如權利要求3所述的基於優化平均每跳距離和優選錨節點的WSN定位方法，其特徵在於，優化定位坐標值的具體步驟如下: 假設優選後的錨節點記為AJr = 1,2,…，m);未知節點Nu經過第一步求得平均每跳距離後，根據公式⑶與距離4的跳數相乘，獲得與錨節點4間的估計距離Destu-;由於每三個錨節點的隨機組合共有Cl巾,那麼利用這些錨節點組合，對估計距離Destu-採用三邊測量法計算，可得<個未知節點Nu的估計定位坐標，記為Ek，其中?=1，2，…，C1I; 假設用來計算候選定位坐標Ek的三個錨節點與未知節點的跳數分別為hopphopp, hopq, (r, p, q = 1,2,…，m),記這三個錨節點與未知節點的跳數和為Sk, Sk =hopr+hopp+hopq,那麼賦予候選定位坐標Ek的權值為:
進行歸一化加權處理後，每個候選定位坐標的權值各不相同，賦予錨節點組合中與未知節點跳數和較小的那些候選坐標值以較大的權值，同時保證權值之和為I ; 最後計算未知節點的定位坐標； 根據每個候選定位坐標值以及式(9)得到的相應權值就可以計算出未知節點的定位坐標:
通過對候選定位坐標值的加權修正使其可以更好地降低網絡拓撲情況的隨機性對節點定位產生的影響，降低定位誤差。
【文檔編號】H04W84/18GK104185272SQ201410369559
【公開日】2014年12月3日 申請日期:2014年7月30日 優先權日:2014年7月30日
【發明者】顧燕, 郭潔, 李旭傑, 王嫻珏, 季必曄 申請人:河海大學