無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)

楊 鵑，韓雪松

(承德石油高等專科學(xué)校計(jì)算機(jī)與信息工程系，河北承德 067000)

1 無線網(wǎng)絡(luò)

網(wǎng)絡(luò)體系主要由四部分構(gòu)成，分別為傳感節(jié)點(diǎn)、匯聚節(jié)點(diǎn)、通訊方式和數(shù)據(jù)終端。

傳感節(jié)點(diǎn)由多個(gè)微型傳感器節(jié)點(diǎn)構(gòu)成，負(fù)責(zé)對(duì)本地信息進(jìn)行采集，相互間采用無線、多跳、自組織的的網(wǎng)絡(luò)連接方式。匯聚節(jié)點(diǎn)也被稱為sink節(jié)點(diǎn)，主要負(fù)責(zé)采集傳感節(jié)點(diǎn)信息、發(fā)布執(zhí)行命令給本地。通信方式采用低功耗短距離的無線通信技術(shù)，目前采用的技術(shù)大多為IEEE802.15.4(zigbee技術(shù))、Wi-Fi、藍(lán)牙、UWB、3G、CDMA等，不同的應(yīng)用需求可采用不同的通信技術(shù)。

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

2 常用的定位技術(shù)

2.1 基于測距技術(shù)的定位算法

在無線傳感器網(wǎng)絡(luò)中，基于測距的定位技術(shù)由測距和節(jié)點(diǎn)定位兩部分組成。該方法首先測量節(jié)點(diǎn)間的角度或距離，然后再通過節(jié)點(diǎn)定位算法實(shí)現(xiàn)節(jié)點(diǎn)定位。

2.1.1 測距技術(shù)

測距技術(shù)主要有 RSSI、TDOA、AOA、TOA。

TDOA(time difference on arrival):系統(tǒng)應(yīng)安裝超聲波收發(fā)器和RF收發(fā)器，測距時(shí)，同時(shí)發(fā)射信號(hào)，在接收端通過記錄兩種不同信號(hào)到達(dá)時(shí)間的差異，基于已知信號(hào)傳播速度，直接把時(shí)間轉(zhuǎn)化為距離。缺點(diǎn)是超聲波距離有限或是NLOS問題對(duì)超聲波信號(hào)的傳播影響。

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

TOA(time of arrival):利用測量信號(hào)傳播時(shí)間來測量距離，網(wǎng)絡(luò)系統(tǒng)需要利用GPS和高精度的電子設(shè)備來準(zhǔn)確同步衛(wèi)星時(shí)鐘，故應(yīng)用起來有一定的限制。

2.1.2 節(jié)點(diǎn)定位計(jì)算方法

三邊算法:未知節(jié)點(diǎn)與至少三個(gè)以上的錨節(jié)點(diǎn)之間能夠?qū)崿F(xiàn)數(shù)據(jù)通信，通過檢測未知節(jié)點(diǎn)到三個(gè)錨節(jié)點(diǎn)之間的距離，建立方程組，求解。

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

極大似然估計(jì):該方法在至少有三個(gè)以上的錨節(jié)點(diǎn)的情況下使用。根據(jù)錨節(jié)點(diǎn)的位置和未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離建立方程組，并使用最小方差估計(jì)求得未知節(jié)點(diǎn)的坐標(biāo)。

2.1.3 目前基于測距技術(shù)的應(yīng)用

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

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

在AOA/TOA系統(tǒng)中，為提高定位精度，陳奎［3］等提出采用MPM方法對(duì)信道頻率響應(yīng)進(jìn)行時(shí)延估計(jì)，然后天線接收信號(hào)的頻域陣列信號(hào)進(jìn)行AOA估計(jì)，根據(jù)估計(jì)的結(jié)果在二維平面內(nèi)確定目標(biāo)的位置。

為降低了定位誤差，劉超［4］等研究由于天線發(fā)射角度的影響導(dǎo)致RSSI定位方法出現(xiàn)誤差的問題，采用規(guī)劃好的錨節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)進(jìn)行未知估計(jì)，根據(jù)得到的天線的角度，補(bǔ)償修正RSSI的值。

為提高定位精度，王偉［5］等提出在RSSI定位的節(jié)點(diǎn)定位系統(tǒng)中，采用最小均方差誤差估計(jì)求解路徑損耗指數(shù)及方差，并校正節(jié)點(diǎn)位置估計(jì)，在校正過程中，設(shè)定各個(gè)錨節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的位置校正不相關(guān)，將所有參考節(jié)點(diǎn)的校正坐標(biāo)的幾何質(zhì)心作為未知節(jié)點(diǎn)的校正位置。該方法在適當(dāng)增加系統(tǒng)計(jì)算量的前提下，實(shí)現(xiàn)了精度的提高。

2.2 與距離無關(guān)的定位算法

2.2.1 DV-hop 算法［6］

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

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

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

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

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

W.Wang［10］等提出未知網(wǎng)絡(luò)節(jié)點(diǎn)位置信息無需掌握的情況下，基于概率統(tǒng)計(jì)方法，采用序列蒙特卡羅定位方法，實(shí)現(xiàn)了用較少的導(dǎo)標(biāo)對(duì)節(jié)點(diǎn)準(zhǔn)確定位。

J.Sheu［11］等提出一種改進(jìn)的蒙特卡羅算法，該算法中首先導(dǎo)標(biāo)信息由未知節(jié)點(diǎn)接收，并根據(jù)一跳范圍內(nèi)已定位的未知節(jié)點(diǎn)的估計(jì)位置信息，預(yù)測節(jié)點(diǎn)的移動(dòng)方向完成定位。

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

MDS-MAP是一種集中式定位算法，可在Range-Based和Range-Free兩種方式下根據(jù)網(wǎng)絡(luò)配置分別實(shí)現(xiàn)相對(duì)和絕對(duì)定位。該算法首先生成全局網(wǎng)絡(luò)拓?fù)溥B通圖，如果節(jié)點(diǎn)有測距能力，測距結(jié)果就是節(jié)點(diǎn)間拓?fù)鋱D邊線的距離值。如果節(jié)點(diǎn)間無須測距，只是節(jié)點(diǎn)間連通，則拓?fù)鋱D邊線長度賦值為1。根據(jù)生成的網(wǎng)絡(luò)拓?fù)溥B通圖，使用最短路徑算法，生成節(jié)點(diǎn)間矩陣。根據(jù)節(jié)點(diǎn)間矩陣，應(yīng)用MDS技術(shù)，生成多維相對(duì)坐標(biāo)系統(tǒng)。如果錨節(jié)點(diǎn)足夠多，再通過數(shù)據(jù)處理將其轉(zhuǎn)換為絕對(duì)坐標(biāo)系統(tǒng)。該算法系統(tǒng)無需設(shè)置錨節(jié)點(diǎn)，當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)密度小時(shí)，定位誤差大，因而使用與適用于節(jié)點(diǎn)密度大的網(wǎng)絡(luò)環(huán)境。可能存在的問題是網(wǎng)絡(luò)需要集中計(jì)算，部分節(jié)點(diǎn)能耗過大可能節(jié)點(diǎn)失效。

為提高定位精度，陳歲生［13］等在基于測距的MDS-MAP算法定位的基礎(chǔ)上，應(yīng)用擴(kuò)展卡爾曼濾波和不敏卡爾曼濾波這兩種非線性濾波算法對(duì)MDS-MAP的結(jié)果修正。該方法的缺點(diǎn)是加大了系統(tǒng)的計(jì)算量，系統(tǒng)能耗過大。

為減少節(jié)點(diǎn)能耗，馬震［14］等將傳感網(wǎng)絡(luò)劃分成多個(gè)具有簇首的局部網(wǎng)絡(luò)。局部網(wǎng)絡(luò)采用MDSMAP算法實(shí)現(xiàn)定位后，再通過網(wǎng)絡(luò)融合算法將局部相對(duì)坐標(biāo)圖合并成全局絕對(duì)坐標(biāo)圖。該算法有效降低了系統(tǒng)的計(jì)算量，減少了節(jié)點(diǎn)能耗，但是在定位精度方面沒有較大提高。

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

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

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

2.2.5 質(zhì)心定位算法

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

3 無線網(wǎng)絡(luò)現(xiàn)有定位算法存在的問題

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

2)與距離無關(guān)的定位算法大多要求錨節(jié)點(diǎn)密度，增加了系統(tǒng)的成本。如果采用移動(dòng)錨節(jié)點(diǎn)，可有效解決密度問題，降低了價(jià)格，但是附加的問題是如何對(duì)移動(dòng)節(jié)點(diǎn)進(jìn)行路徑規(guī)劃以提高定位精度，這是目前的研究熱點(diǎn)之一。

3)節(jié)點(diǎn)定位按照數(shù)據(jù)處理的方式分為集中式和分布式。集中式處理數(shù)據(jù)的方式是將傳感節(jié)點(diǎn)收集到的信息匯聚到匯聚節(jié)點(diǎn)進(jìn)行處理，需要大量的通信和計(jì)算開銷，適用于靜態(tài)節(jié)點(diǎn)定位。分布式的處理方式目前應(yīng)用較多的是將網(wǎng)絡(luò)劃分出簇，簇內(nèi)節(jié)點(diǎn)間經(jīng)過信息融合后再傳遞給匯聚節(jié)點(diǎn)，這樣減少了節(jié)點(diǎn)間的數(shù)據(jù)通信和能量損耗，適用于有實(shí)時(shí)性要求的移動(dòng)節(jié)點(diǎn)定位。

4)靠近基站節(jié)點(diǎn)計(jì)算量過大，消耗了網(wǎng)絡(luò)的大部分能量，容易造成網(wǎng)絡(luò)不通。

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

4 結(jié)論

本文對(duì)現(xiàn)有的無線傳感網(wǎng)絡(luò)定位算法進(jìn)行了對(duì)比分析，從中可以看出測距技術(shù)依賴硬件支持，研究的重點(diǎn)是低成本和低功耗的算法;而與距離無關(guān)的定位算法依賴于網(wǎng)絡(luò)部署，因此研究趨勢集中在低節(jié)點(diǎn)密度、低功耗和低復(fù)雜度的算法。目前，面對(duì)各種算法的各自優(yōu)缺點(diǎn)，合理有效的選擇適合于無線網(wǎng)絡(luò)應(yīng)用的定位算法是非常重要的。根據(jù)系統(tǒng)的環(huán)境狀況和精度需求，設(shè)定合理的定位方法，也是研究的重點(diǎn)內(nèi)容之一。

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

［2］張宏君，毛永毅.改進(jìn)的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法［J］.計(jì)算機(jī)應(yīng)用，2012，32(8):2103－2105.

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

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

［5］王偉，陳岱，周勇.基于測距修正和位置校正的RSSI定位算法［J］.計(jì)算機(jī)工程與設(shè)計(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］申鉉京，李成岳，王碩，等.基于最優(yōu)錨節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法［J］.吉林大學(xué)學(xué)報(bào)(工學(xué)版)，2011，41(1):208－211.

［8］鄭君剛，吳成東，楚好，等.基于DV-Hop和距離幾何約束的定位算法［J］.東北大學(xué)學(xué)報(bào)(自然科學(xué)版)，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］黃書廣.無線傳感器網(wǎng)絡(luò)定位算法研究［D］.北京郵電大學(xué)碩士論文，2011.

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

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

［15］甘文杰.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究及軟件實(shí)現(xiàn)［D］.北京郵電大學(xué)碩士論文，2012.

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

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