一種無線傳感器網絡的混合定位方法

2023-07-12 17:33:56

專利名稱：一種無線傳感器網絡的混合定位方法
技術領域：
本發明涉及無線傳感器網絡定位，具體是一種利用已知傳感器節點的位置和相鄰傳感器節點間的測距來估計未知傳感器節點位置的方法，適合於部分傳感器節點位置已知、相鄰傳感器節點能測距的無線傳感器網絡的定位，屬於無線網絡信息技術領域。
背景技術：
由多個能感知信息、處理信息、有通信能力的傳感器節點自組織構成的無線傳感器網絡被廣泛應用在環境監測、目標跟蹤等應用中，在這些應用中傳感器節點的位置信息至關重要。給每個傳感器節點配備GPS定位模塊不僅花費過高，GPS模塊的耗電也會大大縮短整個無線傳感器網絡的使用壽命。目前，最主流的無線傳感器網絡定位方法是根據部分已知傳感器節點(錨節點)的位置和相鄰傳感器節點間的測距來估計未知傳感器節點的位置，可分為集中式定位方法和分布式定位方法。集中式定位方法首先將傳感器節點間的測距及錨節點的位置信息通過多跳路由傳輸到匯聚節點(一般，匯聚節點信息處理能力強大、電源能量充足。可將匯聚節點看作無線傳感器網絡中一個特殊的傳感器節點。)，而後匯聚節點根據接收到的信息估計未知傳感器節點的位置，最後再將估計出的傳感器節點的位置信息通過多跳路由傳輸到相應的傳感器節點上。2003年Siang Y.等人基於Multidimensional Scaling(MDS)技術提出基於MDS的無線傳感器網絡定位方法 MDS-MAP(Shang Y. , Ruml W., Zhang Y.Localization from Mere Connectivity.In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and COmpUting，2003)，這種方法對傳感器節點分布比較分散的無線傳感器網絡效果較差。 分布式定位方法則通過交換相鄰傳感器節點間的信息使傳感器節點相互協作來估計未知傳感器節點的位置，可分為自適應多邊測量定位法(adapted multilateration methods) 和迭代優化法(successive refinement methods)。自適應多邊測量定位法通過在整個無線傳感器網絡上泛洪錨節點的位置信息來估計每跳的距離進而估計未知傳感器節點與錨節點間的距離，而後再基於多邊測量定位技術來估計未知傳感器節點的位置。當錨節點分布比較稀疏時，估計出的未知傳感器節點與錨節點間的距離誤差比較大，進而估計出的傳感器節點位置誤差比較大。迭代優化法則是通過傳感器節點間的相互協作迭代優化目標函數來估計傳感器節點的位置信息。2006年Costa等人通過分布式迭代優化權重MDS 目標函數，提出 dwMDS 定位算法(Costa J. Α. , Patwari N. , Hero III Α. 0. Distributed Weighted-Multidimensional Scaling for Node Localization in Wireless Sensor Networks. ACM Transaction on Sensor Networks, 2 (1) :2006 :39-64.)，這種方法的估計精度比較差。2009年Khan等人基於重心坐標系提出分布式定位算法(Khan U. Α.，Kar S. , Moura J. Μ. F. Distributed Sensor Localization in Random Environments Using Minimal Number of Anchor Nodes. IEEE Transactions on Signal Processing,2009, 57(5) :2000-2016.)，這種方法運行速度快並證明是收斂的，但它要求所有未知傳感器節點都位於由錨節點構成的凸殼中，這一條件在現實應用中很難滿足。

發明內容
本發明的目的在於提供一種無線傳感器網絡的定位算法，用於估計無線傳感器網絡中未知傳感器節點的位置信息。本發明的執行分為兩個階段分布式階段和集中式階段。 在分布式階段，相鄰傳感器節點互換測距信息，並根據與相鄰節點間的測距信息計算相應的重心坐標；在集中式階段，將所有傳感器節點的重心坐標、已知傳感器節點的位置信息通過多跳路由傳輸給匯聚節點，匯聚節點根據得到的信息估計無線傳感器網絡中未知傳感器節點的位置信息，並通過多跳路由將估計出的位置信息傳遞給相應的傳感器節點。為實現上述目的，本發明採取以下技術方案整個技術方案包括分布式階段和集中式階段兩個階段。al分布式階段分布式階段包括以下具體步驟al. IV/ = 1,2,... ，傳感器節點i向所有相鄰傳感器節點發送自己的鄰居節點集Ni ；al.2V/ = l,2,... ，傳感器節點i根據接收到的集合Nj, j e Ni,確定與相鄰傳感器節點j間的公有相鄰節點集Cij = {k|k e Ni Λ k e NjI ；al.3V/ = l,2,... ，傳感器節點i向相鄰傳感器節點j j e Ni發送傳感器節點i與公有相鄰節點集Cij中傳感器節點的測距集{pik|k e CijI，其中傳感器節點i到傳感器節點 k 的測距 pik 為傳感器節點 i 基於 RSSI (Received Signal Strength Indication)技術計算出的到傳感器節點k的距離；al. 4 V/ = 1,2,... ，傳感器節點i窮舉由相鄰節點構成的三角形，並判斷是否位於這些三角形中；計算完傳感器節點i所在的所有由相鄰節點構成的三角形的重心坐標並累加；每個傳感器節點的相鄰節點都比較少，因此窮舉由其相鄰節點構成的三角形複雜度比較小，判斷傳感器節點i是否位於由相鄰傳感器節點j，k，1構成的三角形中的準則是由j，k，1構成的三角形Trjkl的面積A (Trjkl)是否等於三角形TriklJrjil和Trjki的面積之和
A (Trikl)+A (Trjil)+A (Trjki)，其中三角形 Trjkl 面積的平方為:,( ) = ~^τ。ρ，其中
m是傳感器節點所處空間的維數加1，如果設傳感器節點所處空間的維數為D，則m = D+1， 本發明主要考慮傳感器傳感器節點處於平面時的定位問題，因此可認為m為3，0是由1構成的m維列向量，P是由元素^，Pi,P2kk,P2kl,片，rf，W構成的mXm矩陣，^是傳感器節點j與傳感器節點k測距的平方；al. 5 V/= 1,2, ..., ，設置傳感器節點i與傳感器節點j j ￡隊間的重心係數％ = 0，如果傳感器節點i位於由相鄰節點j，k，1構成的三角形內，則計算相應的重心坐標， bik' bil 並更新 a, ij = Hij^bij, a, ik = aik+bik, a, α = aa+bil a^· = a, ij aik = a, ik， aii = il ;當傳感器節點i位於由其相鄰傳感器節點構成的三角形內，則相應的重心坐標存在且唯一。如傳感器節點i位於由相鄰傳感器節點j，k，1構成的三角形內，則相應的重心坐標，bik，ba存在且唯一，同時傳感器節點i又位於由其相鄰節點h，u, V構成的三角形內，則相應的重心坐標bih，biu，biv存在且唯一，其中Λ=，TrU}\⑴表示由節點{j，
k，l} + {i}-{j}構成的三角形，A(Ti·jkl)表示傳感器節點j，k，1構成的三角形Trjkl的面積。a2集中式階段集中式階段包括以下具體步驟a2. 1錨節點將已知的位置信息通過多跳路由傳輸給匯聚節點，V/ = l,2,..., ，當 Bij Φ 0傳感器節點i將重心係數通過多跳路由傳輸給匯聚節點，所有不能被相鄰傳感器節點構成的三角形包圍的傳感器節點將它與相鄰節點的測距集通過多跳路由傳輸給匯聚節佔.
JWS a2. 2匯聚節點優化如下目標函數，估計未知傳感器節點的位置。由於目標函數比較複雜，直接優化代價較高，本發明基於Majorization方法，將目標函數近似為一系列二次規劃問題。通過對這一系列二次規劃問題的優化，求得目標函數的最優解，具體步驟為 a2. 2. 1 到 a2. 2. 5。
ηχ* = arg min Q(x) = arg min(l - a)^
xgXxgXs.t. X1=X1Vjgk其中，α e (0,1)是權重因子，當無線傳感器網絡中不能被鄰居節點構成的三角形包含的傳感器節點所佔比較較高時，α在取值範圍內取較大值；反之當無線傳感器網絡中不能被鄰居節點構成的三角形包含的傳感器節點所佔比較較低時，α在取值範圍內取較小值，一般可取中間值0. 5。χ*為目標函數的最優解，即本發明所估計的無線傳感器網絡中所有傳感器節點的位置矩陣，D為傳感器節點所處空間的維數，Xi是一個D維列向量，表示傳感器節點i的估計位置，χ = [X1, X2, ... , xn]表示無線傳感器網絡中所有傳感器節點的位置信息，I IxiI I表示向量Xi的二範數，X是一個DXn的矩陣空間，表示χ的取值範圍，Ci 是由傳感器節點i的相鄰節點構成的能包含傳感器節點i的三角形的個數，Ni是傳感器節點i的相鄰節點集，Bij是傳感器節點i在所有不同三角形中對應於傳感器節點j的重心坐標之和，也稱傳感器節點i與傳感器節點j間的重心係數，U是不能由相鄰節點構成的三角形包含的傳感器節點的集合，Pij是傳感器節點i與傳感器節點j的實際測距，Clij(X)=
Xi-Xj I是根據X計算出的傳感器節點i與傳感器節點j間的歐式距離，K是錨節點集，f 是錨節點i的位置向量。
2目標函數的前一項;￡ C1X1 - X ^xj基於重心坐標系約束傳感器節點的估計位
i=lJGNi
置儘量滿足由傳感器節點間的測距揭示的相對結構，而後一項Σ Σ (α _《(x))2約束不能
i&U JGNi
由鄰居節點構成的三角形包含的節點與鄰居節點的測距儘量保持不變。a2. 2. 1令迭代次數t = 1，給每個未知傳感器節點的初始位置向量Xi (0)賦D維0 向量，完成初始化DXn位置矩陣x+(0)，令位置矩陣y(l) =x+(0)，取ε為一極小正數；a2. 2. 2通過對a2. 2中的目標函數Q(χ)做變換，構造ηΧη的矩陣H1, H2 ；Bi是由傳感器節點i相應的重心係數構成的列向量，a〖=[an,ai2,...,am]，基於 構
權利要求
1. 一種無線傳感器網絡的混合定位方法，其特徵在於，包括分布式階段和集中式階段兩個階段al分布式階段分布式階段包括以下具體步驟al. 1 V/= 1,2,... ，傳感器節點i向所有相鄰傳感器節點發送自己的鄰居節點集Ni ； al. 2 V/ = 1,2,... ，傳感器節點i根據接收到的集合Nj, j e Ni,確定與相鄰傳感器節點 j間的公有相鄰節點集Cij = {k|k e Ni Λ k e NjI ；al. 3 V/= 1,2,... ，傳感器節點i向相鄰傳感器節點j j e Ni發送傳感器節點i與公有相鄰節點集Cij中傳感器節點的測距集{pik|k e CijI，其中傳感器節點i到傳感器節點k的測距Pik為傳感器節點i計算出的到傳感器節點k的距離；al.4V/ = l,2,... ，傳感器節點i窮舉由相鄰節點構成的三角形，並判斷是否位於這些三角形中；al.5V/ = l,2,..., ，設置傳感器節點i與傳感器節點j j e Ni間的重心係數 」=0，如果傳感器節點i位於由相鄰節點j，k，1構成的三角形內，則計算相應的重心坐標，bik， bii，並更新 ij = Hij^bij, ik = aik+bik, α = aa+bil a^· = ij aik = ik，aa =a' α ；計算完傳感器節點i所在的所有由相鄰節點構成的三角形的重心坐標並累加；當傳感器節點i位於由其相鄰傳感器節點構成的三角形內，則相應的重心坐標存在且唯一；如傳感器節點i位於由相鄰傳感器節點j，k，1構成的三角形內，則相應的重心坐標 bij; bik，bn存在且唯一，同時傳感器節點i又位於由其相鄰節點h，u, ν構成的三角形內，則相應的重心坐標bih，biu，biv存在且唯一，其中，
全文摘要
一種無線傳感器網絡的混合定位方法屬於無線網絡信息技術領域。該方法包括兩個階段分布式階段和集中式階段。在分布式階段相鄰傳感器節點互換與公有相鄰傳感器節點間的測距信息，而後傳感器節點基於測距信息依次判斷是否位於由相鄰傳感器節點構成的三角形中並計算相應的重心坐標；在集中式階段，傳感器節點將計算出的重心坐標、錨節點將已知的位置信息通過多跳路由傳輸到匯聚節點，匯聚節點根據接收到的信息估計未知傳感器節點的位置信息，保持錨節點的位置不變並使無線傳感器網絡滿足由重心坐標揭示的相對結構，最後匯聚節點將估計出的位置信息通過多跳路由傳輸給相應的傳感器節點。該方法極大提高了傳感器節點的定位精度。
文檔編號H04W64/00GK102325372SQ20111027227
公開日2012年1月18日 申請日期2011年9月14日 優先權日2011年9月14日
發明者侯義斌, 侯翠琴, 黃樟欽 申請人:北京工業大學