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