【文章內(nèi)容簡介】 間的跳數(shù)。跳段距離(hop distance):兩個節(jié)點之間間隔的各跳段距離之和，稱為兩節(jié)點間的跳段距。接收信號強度指示(Received Signal Strength Indicator,RSSI):節(jié)點接收到無線信號的強度大小，稱為接收信號的強度指示。到達(dá)時間(Time of Arrival,TOA):信號從一個節(jié)點到另一個節(jié)點所需要的時間，稱為信號到達(dá)時間。到達(dá)時間差(Time Difference Of Arrival,TDOA):兩種不同傳播速度的信號從一個節(jié)點傳播到另一個節(jié)點所需要的時間之差，稱為信號的到達(dá)時間差。到達(dá)角度(Angle Of Arrival,AOA):節(jié)點接收到的信號相對于自身軸線的角度，稱為信號相對接收節(jié)點的到達(dá)角度。視線關(guān)系(Line Of Sight,LOS):兩個節(jié)點間沒有障礙物間隔，能夠直接通信，稱為兩個節(jié)點間存在視線關(guān)系。 作為一個研究熱點，許多學(xué)者根據(jù)不同的應(yīng)用背景和前提假設(shè)，運用了不同的定位算法，對這些算法目前還沒有統(tǒng)一的分類標(biāo)準(zhǔn)，本節(jié)介紹了幾類不同的分類方法。根據(jù)計算方式劃分:分布式和集中式。集中式定位算法需要一個中心節(jié)點負(fù)責(zé)所有節(jié)點的定位，該節(jié)點可能具有某些特殊的配置，如計算能力強、能量相對充足等。這類算法由于統(tǒng)籌了全局信息，能夠給出比較精確的定位，但是該方法往往伴隨著較高的通信代價，而且一旦中心節(jié)點出現(xiàn)問題，將會影響整個定位功能。分布式算法中，節(jié)點根據(jù)本地信息進(jìn)行自我定位。該策略獲得了大多數(shù)研究者的青睞，因為分布式計算符合了傳感器網(wǎng)絡(luò)本身的設(shè)計特點，這種方法具有較好的容錯性。 如果根據(jù)在定位過程中是使用特定硬件測量節(jié)點間的距離或角度，還是直接使用節(jié)點間的跳數(shù)，可以將現(xiàn)有定位算法分為:基于測距和非測距定位算法。測距算法定位精度較高，需要測距硬件，成本、功耗也相對較大。常用的測距技術(shù)有RSSI、TOA、TDOA和AOA。在目前的測距定位研究中RSSI技術(shù)用的較多，這種技術(shù)主要使用RF信號，不需要額外硬件，并且功率低、成本小，具有實際的應(yīng)用價值。然而，此項測距技術(shù)主要根據(jù)接收的信號強度，使用理論或者經(jīng)驗?zāi)Ｐ娃D(zhuǎn)換成距離，在實際應(yīng)用中可能受環(huán)境影響較大，如多徑、陰影等，測距誤差較大，影響定位精度。TOA(Time of Arrival)是根據(jù)信號的傳播時間和傳播速度計算兩點間的距離，如大家熟知的GPS定位系統(tǒng)，此種測距技術(shù)需要精確的時鐘同步，在硬件和功耗上要求都很高，對傳感器網(wǎng)絡(luò)來說不是合適的選擇。TDOA(Time Difference On Arrival)發(fā)送端同時發(fā)送兩種信號，根據(jù)到達(dá)時間差和傳播速度估計距離，硬件要求也比較高。AOA(Angle of arrival)是接收節(jié)點通過天線陣列或多個超聲波接收機(jī)感知發(fā)射節(jié)點信號的到達(dá)方向，從而構(gòu)成一條從接收機(jī)到發(fā)射機(jī)的方位線，兩根方位線的交點即為普通節(jié)點的位置。由于功耗和成本因素的約束，加上易受環(huán)境因素的影響，測距定位在實際應(yīng)用中并無太大優(yōu)勢。為此，許多學(xué)者運用了非測距的定位算法，常見的如質(zhì)心、DvHop、Amorphous、APIT、凸規(guī)劃及MDSMAP等。由于非測距算法直接使用連通信息，無需測距硬件，節(jié)約成本，但存在著定位精度相對較低或者通信開銷過大等缺點。根據(jù)是否有參考節(jié)點進(jìn)行劃分。有參考節(jié)點的算法稱為絕對定位算法。無參考節(jié)點參與的算法稱為相對定位算法。 在目前研究中，大多數(shù)算法關(guān)注的都是絕對定位，如質(zhì)心、DvHop、Amorphous、APIT等。絕對定位中節(jié)點位置唯一，受節(jié)點移動性影響較小，應(yīng)用廣泛。相對定位無需信標(biāo)節(jié)點，對系統(tǒng)硬件要求較低，可以節(jié)約成本，并且可以滿足一定的應(yīng)用需求，如基于地理位置的路由等。此外，若給定具有絕對坐標(biāo)的參考點后，相對坐標(biāo)可轉(zhuǎn)變成絕對坐標(biāo)，增加適用性。典型的相對定位算法和系統(tǒng)有SPA，LPS，SpotON，而MDSMAP既可實現(xiàn)絕對定位又能夠提供相對定位。 根據(jù)信標(biāo)節(jié)點是否需要有線媒介連接到中心控制器把定位算法分為緊密耦合和松散耦合定位。緊密耦合定位系統(tǒng)中，信標(biāo)節(jié)點的部署經(jīng)過預(yù)先設(shè)計，并連接到控制中心，方便節(jié)點間的時間同步和協(xié)調(diào)，實時性強、定位精度較高。但也存在著擴(kuò)展性差，部署成本和時間開銷大，在室內(nèi)等小范圍場景比較適合。如比較典型的緊密耦合定位系統(tǒng)有ATamp。T的Active Bat系統(tǒng)等。在松散型定位系統(tǒng)中網(wǎng)絡(luò)以ad hoc方式部署，無需中心控制器的連接，采用分布式自協(xié)調(diào)方式，部署靈活，可擴(kuò)展性好，適用范圍較廣。目前大多數(shù)定位算法都屬于松散型的，如APS，APIT，MDSMAP等。然而與緊密耦合型定位相比精確性相對較差。且由于缺乏中心節(jié)點的協(xié)調(diào)，節(jié)點間因信道競爭而產(chǎn)生較大的通信干擾，造成通信不穩(wěn)定性。為此，劍橋大學(xué)的Mike Hazas等人運用使用寬帶擴(kuò)頻技術(shù)解決多路訪問和帶內(nèi)噪聲干擾問題。 由于定位技術(shù)在無線傳感器網(wǎng)絡(luò)中的重要性，許多學(xué)者從不同的角度和應(yīng)用出發(fā)開展了定位相關(guān)的研究，運用了不同的定位算法和定位系統(tǒng)。本節(jié)從定位中網(wǎng)絡(luò)節(jié)點的不同狀態(tài)這一角度出發(fā)，對當(dāng)前已有的典型研究工作進(jìn)行分類總結(jié)，對靜態(tài)無線傳感器網(wǎng)絡(luò)定位研究現(xiàn)狀進(jìn)行了詳細(xì)介紹。 目前對于靜態(tài)無線傳感器網(wǎng)絡(luò)定位的研究較多，這里根據(jù)集中式和分布式兩種不同的計算模式對一些經(jīng)典的研究進(jìn)行介紹。(1)凸規(guī)劃定位算法Doherty等將節(jié)點間點到點的通信連接視為節(jié)點位置的幾何約束，以此約束限定普通節(jié)點位置的可行解集。最后通過把整個網(wǎng)絡(luò)模型化為一個凸集，將節(jié)點定位問題轉(zhuǎn)化為了凸約束優(yōu)化問題。網(wǎng)絡(luò)中節(jié)點的坐標(biāo)向量表示為,其中前m個節(jié)點坐標(biāo)已知，目的就是求出后mn節(jié)點位置以滿足給定的約束，使用半定規(guī)劃和線性規(guī)劃方法得到一組全局優(yōu)化解。算法的優(yōu)點是把定位歸結(jié)到凸約束優(yōu)化問題，能夠直接利用現(xiàn)有的求解凸優(yōu)化問題的方法，并且只需要節(jié)點間的連通信息，無需配置硬件進(jìn)行節(jié)點間距離的測定，節(jié)約成本，并能夠獲得較好的性能。然而作為一種集中式定位算法，計算開銷和通信開銷較大，可擴(kuò)展性差，不適合大規(guī)模網(wǎng)絡(luò)。并且定位精度受信標(biāo)節(jié)點的部署位置影響較大，信標(biāo)部署到網(wǎng)路邊緣，精度較高。(2)MDSMAPMDSMAP是基于多維標(biāo)度（MDS,multidimensional scaling）的一種定位算法多維標(biāo)度常用于心理學(xué)和精神物理學(xué)的數(shù)據(jù)分析，基本原理是從己知的多維空間節(jié)點的一個或幾個距離矩陣(或估計矩陣)，來發(fā)現(xiàn)節(jié)點在低維空間(二維或三維空間)中的位置MDSMAP提供兩種定位形式：僅使用節(jié)點間連通信息的定位和利用測距信息的定位MDSMAP算法主要有三個步驟:Step1:計算所有節(jié)點間的最短路徑，建立MDS所需節(jié)點測量矩陣。首先從全局角度生成網(wǎng)絡(luò)拓?fù)溥B通圖，并為圖中每條邊賦測量值（跳數(shù)或測量距離）。然后使用最短路徑算法例如Dijkstra或Floyd算法，生成節(jié)點測量矩陣。Step2:對測量矩陣應(yīng)用標(biāo)準(zhǔn)MDS技術(shù)，生成整個網(wǎng)絡(luò)的二維或三維相對坐標(biāo)系統(tǒng)。Step3:當(dāng)擁有足夠的錨節(jié)點時(二維最少需要3個，三維最少需要4個)，通過線性變換把相對坐標(biāo)系統(tǒng)轉(zhuǎn)化為絕對坐標(biāo)系統(tǒng)。與凸規(guī)劃定位算法類似，MDSMAP可以不需要信標(biāo)節(jié)點，僅使用節(jié)點間的連通信息獲取節(jié)點間的相對位置估計，并且如果能夠獲取節(jié)點間測距信息，可以提供絕對位置，具有較大的靈活性。同樣，作為集中式定位算法，通信開銷和計算開銷較大，擴(kuò)展性差。此外，定位精度和定位成功率受節(jié)點連通度和密度影響較大。網(wǎng)絡(luò)密度小，定位誤差大，無法定位節(jié)點增加。所以此算法適用于小規(guī)模的稠密無限傳感器網(wǎng)絡(luò)的應(yīng)用。在MDSMAP基礎(chǔ)之上，運用了一種改進(jìn)算法，利用非度量多維標(biāo)度技術(shù)，直接根據(jù)無線信號強度值來進(jìn)行節(jié)點定位,避免了信號強度到距離的轉(zhuǎn)換時帶來的誤差和計算量。(3)基于核學(xué)習(xí)的定位算法 許多算法都是分為兩步，首先使用某種測距技術(shù)獲取兩點間的距離，接著根據(jù)距離信息設(shè)計某種定位算法估計普通節(jié)點位置。然而由于多徑、陰影等影響，造成了一定的測距誤差，勢必影響定位精度。為繞開測距步驟,使用核學(xué)習(xí)理論，把節(jié)點定位問題轉(zhuǎn)變?yōu)橐粋€統(tǒng)計分類問題，直接由節(jié)點間的信號強度測量空間映射到節(jié)點的位置空間。算法分為兩步：分類函數(shù)的訓(xùn)練和節(jié)點位置估計。 整個部署區(qū)域分成若干小區(qū)域，由于信標(biāo)節(jié)點位置已知，可確定自己所屬區(qū)域，目標(biāo)就是確定位置節(jié)點所屬區(qū)域，可把區(qū)域中心看作自身位置，自然的把定位問題歸結(jié)到了分類問題上。在訓(xùn)練階段，通過各信標(biāo)節(jié)點廣播通信，每個節(jié)點能夠獲取到各個信標(biāo)的信號強度。信標(biāo)節(jié)點將到其它信標(biāo)的信號強度及所在區(qū)域標(biāo)志發(fā)送到中心節(jié)點，中心節(jié)點以此作為訓(xùn)練數(shù)據(jù)，選擇一個分層的高斯核函數(shù)，利用支持向量機(jī)（SVR）分類方法得到一個判別函數(shù)。接著，中心節(jié)點分發(fā)判別函數(shù)參數(shù)到各節(jié)點。定位階段中，各普通節(jié)點根據(jù)存儲的到各信標(biāo)節(jié)點的信號強度，利用接收的判別函數(shù)，即可估計自身所在的區(qū)域，以區(qū)域中心作為估計位置。假定每個節(jié)點都能夠直接測量到各信標(biāo)的信號強度，等于限定了網(wǎng)絡(luò)規(guī)模，適用范圍有限。使用類似的技術(shù)，使用連通信息替代了信號強度，把部署區(qū)域分成網(wǎng)格，支持向量機(jī)與決策樹相結(jié)合，估計節(jié)點所在的網(wǎng)格，以網(wǎng)格中心作為節(jié)點位置。(4)質(zhì)點彈簧優(yōu)化模型定位算法 假定節(jié)點為彈簧連接的剛性實體，把節(jié)點間的距離表示為不同長度的彈簧，作為系統(tǒng)的約束，目的就是尋找一組節(jié)點位置使得整個系統(tǒng)勢能最小。在定位開始階段每個節(jié)點給定一個初始值，然后計算每個節(jié)點i到j(luò)的估計距離 則節(jié)點i和j之間估計距離和測量距離之間的差別可用力表示，其中表示單位向量，表示兩節(jié)點間測量距離。由此可以得到節(jié)點i與所有鄰居節(jié)點的受力總和為=∑，沿力的方向移動改變節(jié)點位置，使得在新的節(jié)點位置合力減小。對每個節(jié)點不斷重復(fù)著類似操作，直到最大運行次數(shù)或者系統(tǒng)能量平衡。此方法運行周期較長，且容易陷入局部最小解。同樣把節(jié)點當(dāng)作質(zhì)點，節(jié)點間的距離作為彈力，但從全局的角度出發(fā)，建立了系統(tǒng)能量優(yōu)化函數(shù)，使用最短路徑距離的方法考慮了節(jié)點到非鄰居節(jié)點的相互作用，然后引入Kamada Kawai畫圖算法進(jìn)行迭代求解，取得了很好的定位性能。另外，其它比較經(jīng)典的集中式定位算法如PDM算法，針對不規(guī)則網(wǎng)絡(luò)拓?fù)洌约坝捎诘乩硇螤?、障礙物等引起的各向異性的通信特性，采用非奇異分解(SVD)方法來分析近似測量矩陣，得到一個近似測量矩陣到地理距離空間的變換矩陣，普通節(jié)點到各信標(biāo)的近似測量矩陣與此變換矩陣相乘即可得到到各信標(biāo)節(jié)點的距離，然后使用其它定位算法進(jìn)行位置估計。此外，類似于凸規(guī)劃方法，有些學(xué)者運用了一些細(xì)粒度的半正定規(guī)劃算法。. 2分布式定位(1)質(zhì)心算法 質(zhì)心算法由南加州大學(xué)的Nirupalna Bulus等運用，算法思想簡單，計算復(fù)雜性很小，并且不需要測距硬件，僅使用網(wǎng)絡(luò)節(jié)點間的連通性（跳數(shù)）進(jìn)行位置估計。網(wǎng)絡(luò)部署后，信標(biāo)節(jié)點開始間隔一個固定周期向鄰居節(jié)點廣播由ID和自身位置信息組成的數(shù)據(jù)包。普通節(jié)點只需接收信標(biāo)信息，無需反饋，減少了通信開銷。當(dāng)普通節(jié)點接收到不同信標(biāo)信息的數(shù)量超過一個設(shè)定的閾值或接收一定時間信息后，即可計算接收的信標(biāo)節(jié)點所組成的多邊形的質(zhì)心，以此作為自身位置估計。仿真顯示節(jié)點定位精度不高，且受信標(biāo)節(jié)點密度的影響較大，由于它非常簡單，對于能耗、存儲能力和計算能力有限的無線傳感器節(jié)點來說，在位置精度要求不高的場景中具有一定實際意義。Shen等人運用了加權(quán)質(zhì)心算法對質(zhì)心算法進(jìn)行了改進(jìn),將接收信號強度作為計算質(zhì)心時的權(quán)重系數(shù)加以考慮從而提高質(zhì)心算法的性能。 (2)APS Dragos Niculesc等人運用了一系列經(jīng)典的分布式定位算法，合稱為APS(AdHoc Positioning System)。信標(biāo)節(jié)點位置信息使用距離矢量路由交換協(xié)議傳輸后，普通節(jié)點可以獲取到各信標(biāo)的距離或跳數(shù)，然后可利用類似于GPS定位原理進(jìn)行位置估計。根據(jù)信息傳輸方法不同，分為DVHop、DVDistance和Euclidean三種。 DVHop：此算法需要兩次數(shù)據(jù)洪泛。首先使用典型的距離矢量路由交換協(xié)議，廣播所有信標(biāo)節(jié)點信息，包括ID、位置和跳數(shù)，若信標(biāo)節(jié)點的鄰居節(jié)點第一次接收某個信標(biāo)節(jié)點信息則直接存儲，然后跳數(shù)加1后向鄰居節(jié)點繼續(xù)廣播。若信標(biāo)節(jié)點ID已經(jīng)存在，并且跳數(shù)小于存儲的跳數(shù)，更新后轉(zhuǎn)發(fā)，否則直接丟棄。每個節(jié)點執(zhí)行類似操作，直到達(dá)到限定的最大傳輸跳數(shù)。最終，網(wǎng)絡(luò)中各節(jié)點能夠獲得到信標(biāo)節(jié)點的跳數(shù)。當(dāng)信標(biāo)節(jié)點獲得到其他信標(biāo)節(jié)點的位置和間隔跳數(shù)之后，可計算網(wǎng)絡(luò)平均每跳距離，然后將其作為一個校正值(correction)廣播至網(wǎng)絡(luò)中，進(jìn)行第二次洪泛。普通節(jié)點接收到校正值之后，根據(jù)先前獲取的到信標(biāo)節(jié)點的跳數(shù)估計到信標(biāo)節(jié)點的距離。若普通節(jié)點獲得的信標(biāo)節(jié)點距離達(dá)到3個或更多時，則執(zhí)行三邊測量進(jìn)行位置估計。，信標(biāo)節(jié)點到之間的距離和跳數(shù)已知，則由計算得到校正值(即平均每跳距離)為(40+75)/(2+5)=。廣播后，節(jié)點A可從獲得此校正值，即可計算到信標(biāo)節(jié)點的距離分別為2,3。DVHop在各向同性的密集網(wǎng)絡(luò)中，校正值才能合理地估算平均每跳距離，并且信標(biāo)密度越大估計相對越精確。 DVDistance：與DVHop非常類似，但無需兩次洪泛，直接根據(jù)RSSI測量相鄰節(jié)點間的距離，在利用類似距離矢量路由的方法傳播信標(biāo)位置信息時直接累計到信標(biāo)節(jié)點的距離而非跳數(shù)，普通節(jié)點獲取三個以上信標(biāo)節(jié)點距離后即可使用三邊測量進(jìn)行位置估計。DVDistance算法也僅適用于各向同性的密集網(wǎng)絡(luò)，并且受測距誤差的影響較大。 Euclidean：此方法仍需要廣播信標(biāo)位置信息，但最大傳輸跳數(shù)限定為2跳，并運用了鄰居票決和共同鄰居兩種計算方法。，B、C為信標(biāo)L的鄰居節(jié)點，同時也是A的鄰居節(jié)點，距離BL、CL、BC、AB和AC可由RSSI估計得到，則四邊形的的邊長和一對角線已知，根據(jù)畢達(dá)哥拉斯理論可計算出AL的距離，但可得到A的兩個可能位置A和A′，作者給出了兩種選擇方法:(1)鄰居節(jié)點票決法：假如A還有其它鄰居節(jié)點D與L相鄰，且與B或C之一相鄰，則可以使用D來替換B或C再次計算AL的距離，則A節(jié)點就能在兩個可能的位置中選擇出正確的一個。如果有更多的鄰居節(jié)點可用，節(jié)點A就可做出更加準(zhǔn)確的選擇。(2)共同鄰居法：若節(jié)點D是B、C、L共同的鄰居節(jié)點，而A與D不相鄰，則認(rèn)為A與L