1. 引言
定位技術(shù)是無(wú)線傳感器網(wǎng)絡(luò)中的支撐技術(shù)，缺少位置數(shù)據(jù)的信息往往是沒(méi)有意義的。隨著無(wú)線傳感器網(wǎng)絡(luò)向節(jié)點(diǎn)數(shù)量多，鋪設(shè)范圍廣，基礎(chǔ)設(shè)施簡(jiǎn)單和硬件成本低的方向發(fā)展，如何在減少節(jié)點(diǎn)硬件組件，算法實(shí)現(xiàn)簡(jiǎn)單的同時(shí)獲得相對(duì)準(zhǔn)確的定位信息已成為主要研究的課題之一。現(xiàn)有定位算法根據(jù)定位過(guò)程中是否需要使用已知位置的信標(biāo)節(jié)點(diǎn)，分為絕對(duì)定位算法和相對(duì)定位算法。前者一般是在待測(cè)區(qū)域事先布置一定比例的錨節(jié)點(diǎn)，這些節(jié)點(diǎn)通過(guò)GPS或是其他方法已得知自身絕對(duì)坐標(biāo)，其余的未知節(jié)點(diǎn)通過(guò)與這些信標(biāo)節(jié)點(diǎn)通信獲得自身坐標(biāo)。相對(duì)定位算法則完全不需要事先布置信標(biāo)節(jié)點(diǎn)，通過(guò)算法制定的方案，選取一定數(shù)量的未知節(jié)點(diǎn)建立相對(duì)坐標(biāo)，其余的節(jié)點(diǎn)通過(guò)節(jié)點(diǎn)之間的協(xié)作關(guān)系和消息傳輸獲取自身在相對(duì)坐標(biāo)系中的相對(duì)位置實(shí)現(xiàn)定位。相對(duì)定位算法無(wú)需信標(biāo)節(jié)點(diǎn)和基礎(chǔ)設(shè)施，硬件成本低，并且不會(huì)受到復(fù)雜環(huán)境對(duì)遠(yuǎn)距離信號(hào)傳輸?shù)挠绊懀m合于對(duì)節(jié)點(diǎn)硬件，能耗以及環(huán)境適應(yīng)性有很高要求的無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用。
2. 定位算法分析
在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)定位一般包括三個(gè)部分：距離測(cè)定、位置計(jì)算和定位過(guò)程。
(1) 距離測(cè)定：就是獲得兩個(gè)節(jié)點(diǎn)之間距離的方法，可分為基于測(cè)距和無(wú)需測(cè)距。基于測(cè)距的算法(range-based)通過(guò)節(jié)點(diǎn)自身攜帶的測(cè)距功能直接測(cè)量?jī)蓚€(gè)節(jié)點(diǎn)之間的距離。當(dāng)前比較重要的測(cè)距方法主要是到達(dá)時(shí)間(TOA)、到達(dá)時(shí)間差(TDOA)和信號(hào)強(qiáng)度測(cè)距(RSSI)或者到達(dá)角度(AOA)。
TOA(Time of Arrival)：該技術(shù)通過(guò)測(cè)量信號(hào)傳播時(shí)間來(lái)測(cè)量距離。使用TOA 技術(shù)最基本的定位系統(tǒng)是GPS，GPS 系統(tǒng)需要昂貴、高性能的電子設(shè)備來(lái)精確同步衛(wèi)星時(shí)鐘。因WSN節(jié)點(diǎn)硬件尺寸、價(jià)格和功耗限制，GPS 和其他TOA 技術(shù)無(wú)法廣泛應(yīng)用于WSN。
TDOA(Time Difference On Arrival)：TDOA測(cè)距技術(shù)被廣泛應(yīng)用于WSN定位方案中。通過(guò)記錄兩種不同信號(hào)(常使用RF和超聲波)到達(dá)時(shí)間差異，基于已知信號(hào)傳播速度，直接把時(shí)間轉(zhuǎn)化為距離。已有多種定位算法使用TDOA實(shí)現(xiàn)測(cè)距。但該技術(shù)受限于超聲波傳播距離有限(超聲波信號(hào)通常傳播距離僅為20-30英尺，因而網(wǎng)絡(luò)需要密集部署)和NLOS(Non-Line-Of-Sight)問(wèn)題對(duì)超聲波信號(hào)的傳播影響。雖然已有發(fā)現(xiàn)并減輕NLOS影響的技術(shù)，但都需要大量計(jì)算和通信開(kāi)銷(xiāo)，不適用于低功耗的WSN應(yīng)用中。
RSSI(Received Signal Strength Indicator)：已知發(fā)射功率，在接收節(jié)點(diǎn)測(cè)量接收功率，計(jì)算傳播損耗，使用理論或是經(jīng)驗(yàn)的信號(hào)傳播模型將傳播損耗轉(zhuǎn)化為距離，該技術(shù)主要使用RF 信號(hào)。因傳感器節(jié)點(diǎn)具有無(wú)線通信能力，故是一種低功率、廉價(jià)的測(cè)距方式，RADAR、SpotON等許多項(xiàng)目中使用了該技術(shù)。他的主要誤差來(lái)源是環(huán)境影響所造成的信號(hào)傳播模型的建模復(fù)雜性；反射、多徑傳播、NLOS)、天線增益等問(wèn)題都會(huì)對(duì)相同的距離產(chǎn)生顯著不同的傳播損耗。通常將其看為一種粗糙的測(cè)距技術(shù)，它可能產(chǎn)生50%的測(cè)距誤差。
AOA(Angle of arrival)：該技術(shù)是估算鄰居節(jié)點(diǎn)發(fā)送信號(hào)方向，可通過(guò)天線陣列或多個(gè)接收器來(lái)實(shí)現(xiàn)，除定位外，還能提供方向信息，如MIT 的The Cricket Compass 等項(xiàng)目中都使用AOA 技術(shù)。
無(wú)需測(cè)距的算法(range-free)不需要節(jié)點(diǎn)自身的測(cè)距設(shè)備，通過(guò)跳數(shù)或是其他信息估計(jì)自身到選定的信標(biāo)節(jié)點(diǎn)的距離值，由于是估計(jì)得到的數(shù)值，相對(duì)于基于測(cè)距的算法獲得的距離值誤差偏大。
(2) 位置計(jì)算：在獲取上述距離值之后，節(jié)點(diǎn)需要通過(guò)位置計(jì)算的方法計(jì)算得到坐標(biāo)值。現(xiàn)有的算法一般采用三邊測(cè)量法和三角測(cè)量法計(jì)算坐標(biāo)。
圖1 三邊測(cè)量法示意圖
如圖1 所示，在未知節(jié)點(diǎn)獲得三個(gè)以上的信標(biāo)節(jié)點(diǎn)距離值之后，就可以通過(guò)式(1)、式(2)和式(3)計(jì)算自身坐標(biāo)。式中，(xa , ya)、(xb , yb)、(xc , yc)分別是三個(gè)信標(biāo)節(jié)點(diǎn)的坐標(biāo)，da、db、dc 是未知節(jié)點(diǎn)到三個(gè)信標(biāo)節(jié)點(diǎn)的距離。
式(1)經(jīng)過(guò)線性化，可得線性方程式(2):
式(2)中的N 是由于存在測(cè)距誤差加入的參數(shù)，它是根據(jù)測(cè)距誤差的分布形式存在的一個(gè)隨機(jī)誤差向量。如果未知節(jié)點(diǎn)測(cè)得的到信標(biāo)節(jié)點(diǎn)的距離值大于三個(gè)，則可以加入(1)式中，進(jìn)行更精確的計(jì)算。三角測(cè)量法與三邊測(cè)量法類(lèi)似，通過(guò)獲取相對(duì)三個(gè)信標(biāo)節(jié)點(diǎn)的角度值，計(jì)算得到圖1中三個(gè)圓的半徑，再經(jīng)過(guò)三邊測(cè)量法計(jì)算得到坐標(biāo)。三邊測(cè)量法和三角測(cè)量法由于涉及大量的矩陣運(yùn)算和最小二乘的運(yùn)算，計(jì)算量較大，針對(duì)這種情況，加州大學(xué)洛杉磯分校的Andreas Savvides等人提出的n-hop multilaterationprimitive定位算法中提出的最大最小值法通過(guò)簡(jiǎn)單的折線運(yùn)算估計(jì)未知節(jié)點(diǎn)的位置，如圖2所示。
圖2 最大最小值法示意圖
圖中A點(diǎn)和B點(diǎn)為信標(biāo)節(jié)點(diǎn)，C點(diǎn)為未知節(jié)點(diǎn)。在獲得C點(diǎn)到A點(diǎn)和B點(diǎn)的折線距離a、b、c之后，在三角形ACK中，利用斜邊AC的長(zhǎng)度a代替直角邊AK的長(zhǎng)度，從而K點(diǎn)移動(dòng)到K/點(diǎn)，B點(diǎn)類(lèi)似，從而有：
最大最小值法估計(jì)得到的坐標(biāo)值由于是取矩形區(qū)域的質(zhì)心代替實(shí)際位置，若測(cè)得的距離值本身就存在較大的誤差，那么得出的結(jié)果沒(méi)有三邊定位精確，在一些要求精度不是很?chē)?yán)格的情況或者是結(jié)果經(jīng)過(guò)求精之后，可以滿足需要。
(3) 定位過(guò)程：不同算法根據(jù)上面兩步獲得的有限的距離值和部分節(jié)點(diǎn)的坐標(biāo)，計(jì)算其余未知節(jié)點(diǎn)的機(jī)制。由于各種算法采取的策略不同，各種性能參數(shù)的區(qū)別主要由這一步?jīng)Q定。在分析定位算法的時(shí)候，一般要針對(duì)具體情況綜合考慮上述三個(gè)方面來(lái)考察算法性能。
3. 典型的相對(duì)定位算法
3.1 SPA 算法
瑞士洛桑聯(lián)邦工業(yè)大學(xué)的Srdjan Capkun 等人最早針對(duì)沒(méi)有基礎(chǔ)設(shè)施的移動(dòng)無(wú)線自組網(wǎng)，提出SPA(self–positioning algorithm)算法[23]。它以網(wǎng)絡(luò)中節(jié)點(diǎn)密度最大的地方選取一個(gè)參考點(diǎn)作為全局相對(duì)坐標(biāo)系的原點(diǎn)，其余每個(gè)節(jié)點(diǎn)分別通過(guò)測(cè)距功能測(cè)得鄰居節(jié)點(diǎn)之間的距離值，如圖3所示，實(shí)線表示二者距離可測(cè)得，虛線表示二者不是鄰居節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)在鄰居節(jié)點(diǎn)中選取兩個(gè)點(diǎn)A、B，選取原則是這兩個(gè)點(diǎn)本身也是鄰居節(jié)點(diǎn)，并且三個(gè)點(diǎn)不在同一直線上。以直線OA作為x 軸，以B點(diǎn)在OA上的投影BxB為y 軸正方向建立局部相對(duì)坐標(biāo)系。所有的局部坐標(biāo)系建立完成后，相鄰的坐標(biāo)系通過(guò)坐標(biāo)變換實(shí)現(xiàn)坐標(biāo)統(tǒng)一，最終所有節(jié)點(diǎn)都變換形成以選取的參考點(diǎn)為原點(diǎn)的坐標(biāo)系實(shí)現(xiàn)定位。由于每個(gè)節(jié)點(diǎn)都要參與多次的坐標(biāo)變換，計(jì)算量和通信開(kāi)銷(xiāo)都非常大。此算法開(kāi)始是針對(duì)無(wú)線自組網(wǎng)提出的，不太考慮功耗問(wèn)題，但是用到無(wú)線傳感器網(wǎng)絡(luò)當(dāng)中，這種通信開(kāi)銷(xiāo)和節(jié)點(diǎn)數(shù)量呈指數(shù)比上升的算法需要根據(jù)實(shí)際情況進(jìn)行改進(jìn)。
圖3 SPA算法示意圖
3.2 聚類(lèi) SPA 算法
美國(guó)仁斯利爾理工學(xué)院Rajagopal Iyengar 等人提出的聚類(lèi)SPA(clustering-basedself–positioning algorithm)算法[24]是針對(duì)上述SPA算法通信量過(guò)大而提出的改進(jìn)算法。首先通過(guò)運(yùn)行隨機(jī)的定時(shí)器選取網(wǎng)絡(luò)中的主節(jié)點(diǎn)，主節(jié)點(diǎn)一跳范圍內(nèi)的其他節(jié)點(diǎn)成為它的從節(jié)點(diǎn)。每個(gè)主節(jié)點(diǎn)使用SPA算法中相似的方法建立局部相對(duì)坐標(biāo)系，并計(jì)算得到其余從節(jié)點(diǎn)的局部坐標(biāo)。完成第一步之后，相鄰的局部坐標(biāo)系依據(jù)ID號(hào)由大到小的原則進(jìn)行坐標(biāo)變換，最終以ID號(hào)最小的主節(jié)點(diǎn)為原點(diǎn)建立相對(duì)坐標(biāo)系，從而實(shí)現(xiàn)定位。由于算法以節(jié)點(diǎn)簇為單位進(jìn)行坐標(biāo)變換，計(jì)算量和通信量相對(duì)SPA算法來(lái)說(shuō)都得到大幅度減少，基本與節(jié)點(diǎn)個(gè)數(shù)呈線性比。該算法由于簇之間變換要求拓?fù)浣Y(jié)構(gòu)比較規(guī)則，通信無(wú)障礙，所以在地形復(fù)雜，節(jié)點(diǎn)之間通信容易產(chǎn)生沖突的環(huán)境下，定位效果不是很好，節(jié)點(diǎn)覆蓋率比較低。
… …
5. 結(jié)論
相對(duì)定位算法由于無(wú)需事先布置錨節(jié)點(diǎn)，很大程度上節(jié)約了硬件成本，受外界信號(hào)干擾的影響較小，適合用于對(duì)節(jié)點(diǎn)硬件成本，算法計(jì)算能耗以及節(jié)點(diǎn)分布有嚴(yán)格限制的無(wú)線傳感器網(wǎng)絡(luò)。本文從通信量、覆蓋率和定位精度三個(gè)主要的性能指標(biāo)對(duì)現(xiàn)有的幾種典型定位算法進(jìn)行了綜合分析，通過(guò)圖表的形式比較節(jié)點(diǎn)密度和節(jié)點(diǎn)分布兩個(gè)方面對(duì)算法的影響，闡述了各算法在不同的節(jié)點(diǎn)布置環(huán)境下性能對(duì)比，說(shuō)明了算法具體的適用范圍，并提出了適當(dāng)?shù)母倪M(jìn)方案。目前存在的算法大都需要在節(jié)點(diǎn)密度較高的環(huán)境下能獲得比較理想的定位效果，如何通過(guò)節(jié)點(diǎn)之間的消息傳輸和節(jié)點(diǎn)協(xié)作使得算法在某些節(jié)點(diǎn)密度較低的環(huán)境中也能實(shí)現(xiàn)定位精度和節(jié)點(diǎn)覆蓋率二者很好結(jié)合的問(wèn)題，將是相對(duì)定位算法需要主要關(guān)注的方面。
