基於Euclidean算法的無線傳感器三維定位方法
2023-04-24 04:33:36
專利名稱：基於Euclidean算法的無線傳感器三維定位方法
技術領域：
本發明屬於無線傳感器網絡應用技術領域，尤其涉及一種基於Euclidean算法的無線傳感器三維定位方法。
背景技術：
物聯網技術作為新一代信息技術，在受到廣泛關注的同時，已經潛移默化的滲透進社會生活和工業生產的各個方面，在許多領域發揮著越來越重要的作用。當前，包括我國在內的許多國家提出了建設智能電網的宏觀構想，甚至納入了國家發展戰略。結合我國電網建設的實際情況，將物聯網技術引入智能電網，充分發揮物聯網的強大優勢，將是智能電網發展的必然趨勢。物聯網在電力系統監控中，起著「末梢神經」的作用，構成了電力系統監視控制和數據採集(Supervisory Control And Data Acquisition，SCADA)系統的基礎， 為「五遙」(遙測、遙信、遙控、遙視、遙調)的實現提供了重要保障，提高了電力系統的監測、 控制與靈活調度能力。在進行數據採集的過程中，回傳採集數據的同時，確定數據的採集位置也是必不可少的，因此無線傳感器網絡作為物聯網的主要組成部分，其節點定位技術的研究成為了必要。近年來，節點自身定位技術已成為無線傳感器網絡熱點技術之一，很多研究者們一直致力於這一領域的研究，並取得了很大的進展。現有的無線傳感器網絡定位算法大體分為基於測距(range-based)的定位算法和基於非測距(range-free)的定位算法兩大類。 前者需要通過實際測量，獲得節點間距離(角度)信息，再使用三邊或多邊定位法，來計算未定位節點(空間位置信息未知的節點)的位置；後者無需實際測量節點間的距離或角度， 僅根據網絡連通性等信息實現待定位節點的位置。基於測距的定位算法對網絡的硬體設施要求較高，通常需要多次測量來提高定位精度，大大增加了網絡的計算和通信開銷。因此， 基於非測距的定位算法，如質心定位算法、APS系列算法、APIT算法和MAP算法等，受到越來越多的關注。質心算法完全利用未定位節點與導標節點是否連通來進行定位，其優勢是實現簡單，不需要節點之間的協調，具有良好的擴展性，但其定位精度較低，只能滿足一些對位置精度要求不高的應用需求。APIT算法在無線信號傳播模式不規則、傳感器節點隨機部署的情況下，具有較高的定位精度和較穩定的性能，但APIT算法對網絡的連通性要求較高，並且對節點密度的依賴性較強。MAP算法具有較強的分布性、可擴展性和能量有效性，但由於其可移動的導標節點周期性地廣播導標信息，可能引起破壞性的帶寬衝突和擁塞，從而不能正確的選擇導標點，導致較大的定位誤差。由美國路特葛斯大學(Rutgers university)的Dragos Niculescu等人提出的 APS系列算法中的Euclidean定位算法，給出了計算與錨節點相隔兩跳的未定位節點位置的方法，突破了未定位節點必須與錨節點相鄰才能定位的限制，並且可以精確的計算出與錨節點相隔兩跳的未定位節點與錨節點(空間位置信息已知的節點)的距離，較DV-Hop等需要估計平均每跳距離的算法有更高的精確度。但Euclidean定位算法，應用的是平面幾何理論，不能直接擴展到三維空間。
發明內容
本發明的目的在於，針對Euclidean定位算法不適用於三維空間未定位節點計算的問題，提出一種基於Euclidean算法的無線傳感器三維定位方法，用以解決此問題。為實現上述的目的，本發明提供的技術方案是，一種基於Euclidean算法的無線傳感器三維定位方法，其特徵是所述方法包括步驟1 無線傳感器網絡初始化，各節點建立初始化信息鍊表和距離鍊表，設定跳數初值N = 2 ；步驟2 掃描各節點的初始化信息鍊表和距離鍊表，在錨節點N跳範圍內，利用 Euclidean算法建立三維定位模型；步驟3 在所述三維定位模型中，利用坐標法計算未定位節點與錨節點間的距離；步驟4:在無線傳感器網絡中，判斷與4個錨節點距離已知的節點的比例是否達到設定值，如果達到設定值，則執行步驟6 ；否則，執行步驟5 ；步驟5 與錨節點間距離已知的節點轉發各自的距離鍊表，令N = N+1，返回步驟 2 ；步驟6 應用四邊定位法，確定未定位節點坐標，完成定位。所述步驟1包括步驟101 無線傳感器網絡各節點第一次泛洪，錨節點發送包含自身標識、節點ID 和三維空間位置的信息，未定位節點發送含有自身標識和節點ID的信息；步驟102 錨節點的鄰居節點記錄所述錨節點的三維空間位置的信息，形成初始化信息鍊表；步驟103 各節點採用接收信號強度指示RSSI測出與錨節點的鄰居節點間的距離並記錄，形成距離鍊表；步驟104 無線傳感器網絡各節點第二次泛洪，各節點將第一泛洪收到的信息廣播出去，獲取與自身相隔兩跳節點的信息。所述利用Euclidean算法建立三維定位模型具體是，在與錨節點距離已知的節點中，選取3個彼此間距離也已知的節點；再選取與該錨節點距離未知，但與這3個節點距離已知的未定位節點，建立三維定位模型。所述步驟3具體是，將三維定位模型置於三維直角坐標系中，通過各節點的坐標來計算未定位節點到錨節點的距離。本發明將求解未定位節點與錨節點的距離抽象為求解六面體頂點間的距離，成功地將二維Euclidean定位算法擴展到了三維空間。具有定位精度高、計算量小、無需移動載體輔助定位以及定位精度不依賴於錨節點密度和通信半徑的效果。
圖1是基於Euclidean算法的無線傳感器三維定位方法流程圖；圖2是利用Euclidean算法建立的三維定位模型示意圖；圖3是錨節點比例與相對定位誤差的關係示意圖；圖4是錨節點比例與定位比例的關係示意圖。
具體實施例方式下面結合附圖，對優選實施例作詳細說明。應該強調的是，下述說明僅僅是示例性的，而不是為了限制本發明的範圍及其應用。實施例在實施例中，設定無線傳感器網絡中存在節點為Pp P2, P3、P4、P5......等多個節
點。圖1是基於Euclidean算法的無線傳感器三維定位方法流程圖，該方法包括步驟1 無線傳感器網絡初始化，各節點建立初始化信息鍊表和距離鍊表，設定跳數初值N= 2。網絡初始化的過程又包括步驟101 無線傳感器網絡各節點第一次泛洪，錨節點發送包含自身標識、節點ID 和三維空間位置的信息，未定位節點發送含有自身標識和節點ID的信息。在無線傳感器網絡中，一般會為一小部分節點配備GPS，這些節點可以通過GPS確定自身的空間位置，這些空間位置已知的節點即為錨節點。錨節點發送的三維空間位置信息可以是自身的三維坐標 (如橫坐標、縱坐標和高度)。步驟102 錨節點的鄰居節點記錄所述錨節點的三維空間位置的信息，形成初始
化信息鍊表。錨節點的鄰居節點是指在錨節點的通信範圍內的節點。比如錨節點的通信範圍為R，那麼以錨節點為中心，R為半徑區域內的所有節點，都稱為該錨節點的鄰居節點。下表 (表1)為節點P5記錄的錨節點三維空間位置信息後形成的初始化信息鍊表。
權利要求
1.一種基於Euclidean算法的無線傳感器三維定位方法，其特徵是所述方法包括步驟1 無線傳感器網絡初始化，各節點建立初始化信息鍊表和距離鍊表，設定跳數初值 N= 2 ；步驟2:掃描各節點的初始化信息鍊表和距離鍊表，在錨節點N跳範圍內，利用 Euclidean算法建立三維定位模型；步驟3 在所述三維定位模型中，利用坐標法計算未定位節點與錨節點間的距離；步驟4:在無線傳感器網絡中，判斷與4個錨節點距離已知的節點的比例是否達到設定值，如果達到設定值，則執行步驟6 ；否則，執行步驟5 ；步驟5 與錨節點間距離已知的節點轉發各自的距離鍊表，令N = N+1，返回步驟2 ；步驟6 應用四邊定位法，確定未定位節點坐標，完成定位。
2.根據權利要求1所述的一種基於Euclidean算法的無線傳感器三維定位方法，其特徵是所述步驟1包括步驟101 無線傳感器網絡各節點第一次泛洪，錨節點發送包含自身標識、節點ID和三維空間位置的信息，未定位節點發送含有自身標識和節點ID的信息；步驟102 錨節點的鄰居節點記錄所述錨節點的三維空間位置的信息，形成初始化信息鍊表；步驟103 各節點採用接收信號強度指示RSSI測出與錨節點的鄰居節點間的距離並記錄，形成距離鍊表；步驟104 無線傳感器網絡各節點第二次泛洪，各節點將第一泛洪收到的信息廣播出去，獲取與自身相隔兩跳節點的信息。
3.根據權利要求1所述的一種基於Euclidean算法的無線傳感器三維定位方法，其特徵是所述利用Euclidean算法建立三維定位模型具體是，在與錨節點距離已知的節點中， 選取3個彼此間距離也已知的節點；再選取與該錨節點距離未知，但與這3個節點距離已知的未定位節點，建立三維定位模型。
4.根據權利要求1所述的一種基於Euclidean算法的無線傳感器三維定位方法，其特徵是所述步驟3具體是，將三維定位模型置於三維直角坐標系中，通過各節點的坐標來計算未定位節點到錨節點的距離。
全文摘要
本發明公開了無線傳感器網絡應用技術領域中的一種基於Euclidean算法的無線傳感器三維定位方法，用於解決Euclidean定位算法不適用於三維空間未定位節點定位的問題。包括將計算未定位節點與錨節點間的距離問題抽象為求解六面體頂點間距離的問題；根據抽象結果，使用坐標法求解未定位節點與錨節點間的距離；而後採用循環迭代的方式來提高與錨節點間的距離已知的節點的比例；當比例達到設定值時，應用四邊定位法，確定未定位節點在網絡中的位置。本發明將二維Euclidean定位算法擴展到了三維空間，具有定位精度高、計算量小以及不依賴於錨節點密度和通信半徑等優點。
文檔編號H04W64/00GK102209383SQ20111012911
公開日2011年10月5日 申請日期2011年5月18日 優先權日2011年5月18日
發明者唐良瑞, 孫毅, 宮月, 柯珊珊, 樊冰, 祁兵, 羅藝婷 申請人:華北電力大學