無線傳感網絡節點定位技術

楊 鵑，韓雪松

(承德石油高等?？茖W校計算機與信息工程系，河北承德 067000)

1 無線網絡

網絡體系主要由四部分構成，分別為傳感節點、匯聚節點、通訊方式和數據終端。

傳感節點由多個微型傳感器節點構成，負責對本地信息進行采集，相互間采用無線、多跳、自組織的的網絡連接方式。匯聚節點也被稱為sink節點，主要負責采集傳感節點信息、發布執行命令給本地。通信方式采用低功耗短距離的無線通信技術，目前采用的技術大多為IEEE802.15.4(zigbee技術)、Wi-Fi、藍牙、UWB、3G、CDMA等，不同的應用需求可采用不同的通信技術。

傳感節點中的未知節點的位置確定就是節點定位。目前采用的方法大多數是依靠錨節點的坐標來確定，錨節點的多少和分布情況影響著定位精度。節點定位按照錨節點的形式可分為靜態定位技術和動態定位技術。靜態定位技術將錨節點的位置固定，未知節點根據與錨節點的通信確定位置，該技術如果按照是否基于測距技術還可將其分為基于測距技術的定位和與距離無關的定位技術。動態定位技術中錨節點可以移動并周期性的發送自身位置信息給周圍的未知節點，錨節點的數量要求比靜態定位技術需要的少，減少了系統的成本，但是錨節點的移動需要按照算法首先進行路徑規劃，否則會在定位時間和節點功耗上浪費過多。本文主要研究基于節點靜態定位技術的應用和發展。

2 常用的定位技術

2.1 基于測距技術的定位算法

在無線傳感器網絡中，基于測距的定位技術由測距和節點定位兩部分組成。該方法首先測量節點間的角度或距離，然后再通過節點定位算法實現節點定位。

2.1.1 測距技術

測距技術主要有 RSSI、TDOA、AOA、TOA。

TDOA(time difference on arrival):系統應安裝超聲波收發器和RF收發器，測距時，同時發射信號，在接收端通過記錄兩種不同信號到達時間的差異，基于已知信號傳播速度，直接把時間轉化為距離。缺點是超聲波距離有限或是NLOS問題對超聲波信號的傳播影響。

AOA(angle of arrival):通過天線陣列或是多個超聲波接收器陣列來實現定位，除定位外還可進行角度估計。使用上要受到噪聲和NLOS問題的影響，且需要額外硬件，可能無法滿足傳感器節點對硬件尺寸和功耗的要求。

TOA(time of arrival):利用測量信號傳播時間來測量距離，網絡系統需要利用GPS和高精度的電子設備來準確同步衛星時鐘，故應用起來有一定的限制。

2.1.2 節點定位計算方法

三邊算法:未知節點與至少三個以上的錨節點之間能夠實現數據通信，通過檢測未知節點到三個錨節點之間的距離，建立方程組，求解。

三角測量法:首先未知節點的接收器天線檢測錨節點發射電波的入射角，從而求得未知節點與該錨節點的方向線。兩個錨節點與未知節點的方向線的交點就是未知節點的估計位置。位置估計計算時，至少需要三個以上的錨節點與未知節點存在通信，假設有三個錨節點A、B、C，未知節點為D，則首先計算經過錨節點A、B、D的圓的半徑和圓心位置，可根據錨節點A和B的位置和計算求得，以此方法依次求取A、C和與B、C和所構成的圓，最后采用三邊測量法即可求得位置節點的坐標。

極大似然估計:該方法在至少有三個以上的錨節點的情況下使用。根據錨節點的位置和未知節點到錨節點的距離建立方程組，并使用最小方差估計求得未知節點的坐標。

2.1.3 目前基于測距技術的應用

孫懋珩等［1］提出采用RSSI檢測未知節點與錨節點的距離，再用粒子群算法計算未知節點的估計坐標。粒子群算法在定位精度、算法收斂性、算法復雜度等方面比遺傳算法和模擬退火算法更適用于需要低功耗、少計算量的無線網絡定位中，但算法在仿真過程中存在容易陷入局部最優化的問題，未來使用該方法進行應用時應將研究放在如何擺脫局部最優化的問題上。

在TDOA定位的環境中，張宏君等［2］提出采用基于殘差加權算法得出需要定位節點的初始值，再采用牛頓迭代定位算法進行精確定位，該方法解決了牛頓迭代算法可能存在的不收斂的問題，減少了節點計算量。

在AOA/TOA系統中，為提高定位精度，陳奎［3］等提出采用MPM方法對信道頻率響應進行時延估計，然后天線接收信號的頻域陣列信號進行AOA估計，根據估計的結果在二維平面內確定目標的位置。

為降低了定位誤差，劉超［4］等研究由于天線發射角度的影響導致RSSI定位方法出現誤差的問題，采用規劃好的錨節點對未知節點進行未知估計，根據得到的天線的角度，補償修正RSSI的值。

為提高定位精度，王偉［5］等提出在RSSI定位的節點定位系統中，采用最小均方差誤差估計求解路徑損耗指數及方差，并校正節點位置估計，在校正過程中，設定各個錨節點對未知節點的位置校正不相關，將所有參考節點的校正坐標的幾何質心作為未知節點的校正位置。該方法在適當增加系統計算量的前提下，實現了精度的提高。

2.2 與距離無關的定位算法

2.2.1 DV-hop 算法［6］

DV-hop算法適用于各向同性的密集網絡，該算法將未知節點到錨節點之間的距離用網絡平均每跳距離和兩者之間的跳數乘積表示。它采用較少的錨節點，并且不需要節點具備測距能力，計算和通信要求適中，定位精度較高。該算法執行時，如果節點間距離與平均每跳距離大致相近時才有較好的效果，實際情況往往不能滿足，導致了誤差的出現，并且當錨節點距離未知節點距離較遠時，節點間的跳數較多，并且由于每跳距離誤差的存在，導致距離誤差也越大。

針對于本算法的改進研究，近年來也取得了一定的成果。申鉉京［7］等將每個未知節點設定一個門限閾值，確定錨節點的位置信息和平均每跳的距離，未知節點選擇最先接收的N個錨節點信息，用最小二乘法求取未知節點的坐標，該算法內存占用率低，且處理效率高。

鄭君剛［8］等提出了采用二維空間的Cayley-Menger行列式提供的幾何約束對未知節點到錨節點的距離進行優化修正，實驗驗證該方法有效減少了測量過程中出現的誤差大小，提高了定位精度。

2.2.2 蒙特卡羅［9］定位算法

適用于移動傳感器網絡節點定位，系統中不設置錨節點，利用一系列加權采樣值表示可能位置的后驗概率分布，成本較低。在這個定位方法中，動態節點較靜態節點在運動過程中能獲得更多的信息，與傳統定位算法相比，在移動狀態下定位精度更高。但該算法的缺點在于:1)為獲取有效樣本，抽樣次數過多，且容易出現粒子退化現象;2)部分位置估計值精度較高的待定節點并未有效利用，可以對這些節點用其它算法輔助定位其它節點。

W.Wang［10］等提出未知網絡節點位置信息無需掌握的情況下，基于概率統計方法，采用序列蒙特卡羅定位方法，實現了用較少的導標對節點準確定位。

J.Sheu［11］等提出一種改進的蒙特卡羅算法，該算法中首先導標信息由未知節點接收，并根據一跳范圍內已定位的未知節點的估計位置信息，預測節點的移動方向完成定位。

2.2.3 MDS-MAP［12］(MultiDimensional scaling MAP)定位算法

MDS-MAP是一種集中式定位算法，可在Range-Based和Range-Free兩種方式下根據網絡配置分別實現相對和絕對定位。該算法首先生成全局網絡拓撲連通圖，如果節點有測距能力，測距結果就是節點間拓撲圖邊線的距離值。如果節點間無須測距，只是節點間連通，則拓撲圖邊線長度賦值為1。根據生成的網絡拓撲連通圖，使用最短路徑算法，生成節點間矩陣。根據節點間矩陣，應用MDS技術，生成多維相對坐標系統。如果錨節點足夠多，再通過數據處理將其轉換為絕對坐標系統。該算法系統無需設置錨節點，當網絡的節點密度小時，定位誤差大，因而使用與適用于節點密度大的網絡環境?？赡艽嬖诘膯栴}是網絡需要集中計算，部分節點能耗過大可能節點失效。

為提高定位精度，陳歲生［13］等在基于測距的MDS-MAP算法定位的基礎上，應用擴展卡爾曼濾波和不敏卡爾曼濾波這兩種非線性濾波算法對MDS-MAP的結果修正。該方法的缺點是加大了系統的計算量，系統能耗過大。

為減少節點能耗，馬震［14］等將傳感網絡劃分成多個具有簇首的局部網絡。局部網絡采用MDSMAP算法實現定位后，再通過網絡融合算法將局部相對坐標圖合并成全局絕對坐標圖。該算法有效降低了系統的計算量，減少了節點能耗，但是在定位精度方面沒有較大提高。

2.2.4 APIT［15］(Approximate point-in-triangulationtest)定位算法

APIT算法是針對WSN異構網絡的定位算法，網絡結構中錨節點和網絡其他的未知節點通信半徑不同，錨節點通信半徑比未知節點的大。其主要思想是:首先未知節點收集所有鄰近信標節點的信息，并通過測試求得未知節點是否位于不同的三個信標節點組成的三角形內，計算出所有符合上述條件的三角形的集合，取所有三角形公共區域的質心作為估計位置。相對于質心定位算法，APIT定位精度高，對信標節點的分布要求較低，但對網絡的連通性有較高的要求，且所需的錨節點密度最大。該算法的不足在于定位覆蓋率較DV-hop算法低，無法定位的節點率較高，其主要原因在于無法定位的節點鄰居錨節點數量不足3個，或是未知節點在鄰居錨節點構成的三角形的外部。

馬剛等［16］提出將min-max算法應用到APIT定位算法中，如果符合APIT算法執行的條件，就執行傳統的APIT算法，否則就執行MIN-MAX算法。該方法解決了APIT算法定位率低的問題，但是提高了通信費用，后期研究應放在如何降低定位開銷上。

2.2.5 質心定位算法

基于網絡的連通性進行定位的算法。未知節點至少與三個以上的錨節點實現通信。其中網絡連通的每三個錨節點構成一個三角形，三角形的質心就是未知節點的估計值。錨節點的分布和密度對于節點定位有很大的影響，并且當未知節點位于靠近三角形某條邊線時，容易造成測量錯誤，因而，人們又提出了質心算法的加權算法，即解決了檢測錯誤的問題，也提高了錨節點對于未知節點的影響問題，錨節點越靠近未知節點，對于未知節點的位置估計影響越大。質心算法計算簡單，但是精度較低，受環境影響較小，適合于復雜環境的定位計算。許多定位工作集中在如何提高質心算法的定位精度上。王琰琳［17］等提出將遺傳算法用于對改進質心定位算法的權值加以修正，通過仿真驗證了該方法能有效提高定位精度。

3 無線網絡現有定位算法存在的問題

1)基于距離定位的算法大多需要硬件的支持。例如基于TOA定位的算法需要利用天線陣列或是多個超聲波接收器陣列通信，提高了無線網絡系統的價格。

2)與距離無關的定位算法大多要求錨節點密度，增加了系統的成本。如果采用移動錨節點，可有效解決密度問題，降低了價格，但是附加的問題是如何對移動節點進行路徑規劃以提高定位精度，這是目前的研究熱點之一。

3)節點定位按照數據處理的方式分為集中式和分布式。集中式處理數據的方式是將傳感節點收集到的信息匯聚到匯聚節點進行處理，需要大量的通信和計算開銷，適用于靜態節點定位。分布式的處理方式目前應用較多的是將網絡劃分出簇，簇內節點間經過信息融合后再傳遞給匯聚節點，這樣減少了節點間的數據通信和能量損耗，適用于有實時性要求的移動節點定位。

4)靠近基站節點計算量過大，消耗了網絡的大部分能量，容易造成網絡不通。

5)很多定位算法不具有容錯性和可擴展性。

4 結論

本文對現有的無線傳感網絡定位算法進行了對比分析，從中可以看出測距技術依賴硬件支持，研究的重點是低成本和低功耗的算法;而與距離無關的定位算法依賴于網絡部署，因此研究趨勢集中在低節點密度、低功耗和低復雜度的算法。目前，面對各種算法的各自優缺點，合理有效的選擇適合于無線網絡應用的定位算法是非常重要的。根據系統的環境狀況和精度需求，設定合理的定位方法，也是研究的重點內容之一。

［1］孫懋珩，廖根健.基于最優錨WSNs中基于粒子群優化的節點定位算法［J］.測控技術，2011，30(12):111－117.

［2］張宏君，毛永毅.改進的無線傳感器網絡節點定位算法［J］.計算機應用，2012，32(8):2103－2105.

［3］陳奎，黃為勇，田傳耕.基于Matrix Pencil的OFDM信號的TOA/AOA定位［J］.計算機應用研究，2013，30(2):534－540.

［4］劉超，王敬東，李鵬.考慮天線角度的無線傳感器網絡節點定位方法［J］.電子科技，2010，23(8):90－95.

［5］王偉，陳岱，周勇.基于測距修正和位置校正的RSSI定位算法［J］.計算機工程與設計，2011，32(2):409－415.

［6］Niculescu D，Nath B.DV based positioning in ad hoc networks［J］.Journal ofTelecommunication Systems，2003，22(1/4):267－280.

［7］申鉉京，李成岳，王碩，等.基于最優錨節點的無線傳感器網絡節點定位算法［J］.吉林大學學報(工學版)，2011，41(1):208－211.

［8］鄭君剛，吳成東，楚好，等.基于DV-Hop和距離幾何約束的定位算法［J］.東北大學學報(自然科學版)，2011，32(4):457－462.

［9］HU L X，DAVID E.Localization for mobile sensor networks［A］.Proceedings of the 10th Annual International Conference on Mobile Computing and Networking［C］.2004，45 －47.

［10］Wang W D.Zhu Q X.sequential monte carlo localizartion in mobile sensor networks［J］.wireless networks，2009，15(4):481－495.

［11］Sheu J P，Hu W K，Lin J c.Distributed lovalization scheme for mobile sensor networks［J］.IEEE Transaction on mobile computing，2010，9(4):516 －525.

［12］黃書廣.無線傳感器網絡定位算法研究［D］.北京郵電大學碩士論文，2011.

［13］陳歲生，盧建剛，樓曉春.基于MDS-MAP和非線性濾波的WSN定位算法［J］.浙江大學學報(工學版)，2012，46(5):866－872.

［14］馬震，劉云，沈波.基分布式無線傳感器網絡定位算法MDS-MAP［J］.通信學報，2008，29(6):57－62.

［15］甘文杰.無線傳感器網絡節點定位算法研究及軟件實現［D］.北京郵電大學碩士論文，2012.

［16］馬剛，陳盛云.WSN中APIT節點定位改進算法研究［J］.微處理機，2011(3):68－72.

［17］王琰琳，黃友銳，曲立國.改進型質心算法在井下人員定位中的應用［J］.煤礦機械，2012，33(8):76－79.