【正文】 遠(yuǎn)近來(lái)模仿PIT中的節(jié)點(diǎn)移動(dòng)方向，假如在節(jié)點(diǎn)M的鄰節(jié)點(diǎn)中，相對(duì)于節(jié)點(diǎn)M沒(méi)有。同時(shí)遠(yuǎn)離或靠近三個(gè)錨節(jié)點(diǎn)A. B。 C，就可判定節(jié)點(diǎn)對(duì)在4ABC內(nèi)幾。否則，就在其外。APIT算法的定位過(guò)程大體可描述如下:首先目標(biāo)定位節(jié)點(diǎn)收集其臨近錨節(jié)點(diǎn)的信息，然后從這些錨節(jié)點(diǎn)組成的集合中任意選取三個(gè)錨節(jié)點(diǎn)組成三角形。假設(shè)集合中有n個(gè)錨節(jié)點(diǎn)，那么共有C}n種不同的選取方法:確定C}n個(gè)不同的三角形，通過(guò)采用近似的三角形內(nèi)點(diǎn)測(cè)試法逐一測(cè)試目標(biāo)節(jié)點(diǎn)是否位于每個(gè)三角形內(nèi)部，直到達(dá)到所需精度，否則就窮盡所有三角形。最后計(jì)算所有包含目標(biāo)節(jié)點(diǎn)的三角形的重疊區(qū)域，重疊區(qū)域的質(zhì)心即為目標(biāo)定位節(jié)點(diǎn)的估計(jì)位置。，陰影部分區(qū)域是包含目標(biāo)節(jié)點(diǎn)的多個(gè)三角形的重疊區(qū)域，黑點(diǎn)即為重疊區(qū)域的質(zhì)心，也就是目標(biāo)節(jié)點(diǎn)的位置所在。相對(duì)于計(jì)算簡(jiǎn)單的類(lèi)似的質(zhì)心定位算法，APIT算法定位精度高且性能穩(wěn)定，對(duì)錨節(jié)點(diǎn)的分布要求較低，但是APIT測(cè)試對(duì)網(wǎng)絡(luò)連通性有著很高的要求。4)Amorphous定位算法Amorphous算法[19]由麻省理工學(xué)院的Radhika Nagpal等提出。采用與DVhop類(lèi)似的方法獲取距錨節(jié)點(diǎn)的最小跳數(shù)路徑，稱(chēng)為梯度值，不同的是Amorphous將通信半徑作為平均跳距，具體定位過(guò)程可以分為以下三個(gè)階段:第一個(gè)階段，未知節(jié)點(diǎn)計(jì)算與每個(gè)錨節(jié)點(diǎn)之間的最小跳數(shù)路徑，這一階段與DVhop算法相同。第二個(gè)階段，把節(jié)點(diǎn)通信半徑作為網(wǎng)絡(luò)平均跳距，計(jì)算未知節(jié)點(diǎn)與每個(gè)錨節(jié)點(diǎn)之間的距離，這一階段的前提是假設(shè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的通信半徑相同。第三個(gè)階段，利用三邊定位算法或其它定位方法，實(shí)現(xiàn)未知節(jié)點(diǎn)的定位。由于該方法把通信半徑作為平均跳距而造成定位誤差較大，所以Radhika Nagpal等在文獻(xiàn)[70]中在基于經(jīng)驗(yàn)?zāi)Ｐ偷幕A(chǔ)上對(duì)該算法進(jìn)行了以下兩方面的改進(jìn)，克服了通信半徑作為平均跳距帶來(lái)的定位誤差較大的問(wèn)題:首先，用下式計(jì)算平均跳距替代算法中把通信半徑作為平均跳距。 ()這里:是通信半徑，是本地鄰節(jié)點(diǎn)數(shù)即平均連通度。然后，利用下式計(jì)算錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的最小跳數(shù)來(lái)代替算法中的最小跳數(shù)。 (3 .18)式中，和分別是節(jié)點(diǎn)和在第一步中獲得的跳數(shù)值。是在節(jié)點(diǎn)的通信半徑:范圍內(nèi)的所有節(jié)點(diǎn)。未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離可以通過(guò)來(lái)計(jì)算。該算法在實(shí)驗(yàn)環(huán)境下可以取得較理想的效果，當(dāng)網(wǎng)絡(luò)平均連通度在15以上時(shí)，即使節(jié)點(diǎn)通信半徑存在10%的偏差，平均定位誤差也可以控制在20%以下。但是該算法在實(shí)施定位以前需要事先預(yù)知網(wǎng)絡(luò)平均連通度，并且其定位效果受到節(jié)點(diǎn)密度的制約。質(zhì)心、DVHop 、Amorphous 和APIT算法是完全分布式的，僅需要相對(duì)少量通信和簡(jiǎn)單計(jì)算，具有良好的擴(kuò)展性。得出質(zhì)心算法定位誤差最大，但其性能不受節(jié)點(diǎn)密度影響，實(shí)現(xiàn)最簡(jiǎn)單，通信開(kāi)銷(xiāo)最小。而DVHop因?yàn)樵诰€(xiàn)計(jì)算平均每跳距離，所以通信開(kāi)銷(xiāo)最大，但它在這一點(diǎn)比Amorphous 算法具有更好的健壯性和適應(yīng)性；雖然節(jié)點(diǎn)密度對(duì)APIT算法影響最小，并且APIT 通信量也較小，但它所需信標(biāo)點(diǎn)密度最大。3．4 本章小結(jié)本章主要對(duì)無(wú)線(xiàn)傳感網(wǎng)絡(luò)定位技術(shù)進(jìn)行了全面的討論。首先簡(jiǎn)單闡述了定位的含義，接著對(duì)無(wú)線(xiàn)傳感網(wǎng)絡(luò)定位技術(shù)的特點(diǎn)、定位的基本方法和定位技術(shù)的分類(lèi)進(jìn)行了詳細(xì)論述。然后又重點(diǎn)介紹了幾種現(xiàn)有的典型定位算法和定位系統(tǒng)。最后定性地分析了幾個(gè)常用的無(wú)線(xiàn)傳感網(wǎng)絡(luò)定位算法的評(píng)價(jià)標(biāo)準(zhǔn)。通過(guò)本章可以知道，每種定位系統(tǒng)或算法都有各自的特點(diǎn)和適用范圍，不存在絕對(duì)最優(yōu)的情況，因此在實(shí)際應(yīng)用中，應(yīng)該根據(jù)具體情況綜合考慮來(lái)選擇合適的定位算法或系統(tǒng)。4DVhop算法研究4．1 引言基于非測(cè)距的定位算法不需要任何特定硬件去獲得距離信息，因此基于非測(cè)距的定位算法更經(jīng)濟(jì)有效，適用于大規(guī)模的無(wú)線(xiàn)傳感網(wǎng)。DVhop算法是由Niculescu and NatP2在Navigate項(xiàng)目中提出的一種分布式基于非測(cè)距的定位算法。其優(yōu)勢(shì)就在于它的簡(jiǎn)單性和不依賴(lài)于測(cè)量誤差的事實(shí)，但該算法存在定位精度不高的缺點(diǎn)。為了提高定位精度，已經(jīng)有許多改進(jìn)的DVhop算法被提出來(lái)，例如:加權(quán)DVhop算法，該算法通過(guò)計(jì)算距離權(quán)值而得出較精確的位置估計(jì)?；诠簿€(xiàn)度的定位算法。共線(xiàn)度引入到了DVhop中從而提出一種基于共線(xiàn)度的DVhop算法。盡管這些改進(jìn)算法在某種程度上提高了定位精度，但大多數(shù)存在著定位精度提高幅度不大，或者是算法復(fù)雜度較高，或者是需要增加額外的硬件設(shè)備的不足。本章將在前人研究基礎(chǔ)上，對(duì)DVhop定位算法做出進(jìn)一步改進(jìn)，提出了一種新的D Vhop算法，即引入權(quán)值改進(jìn)計(jì)算平均跳距的方法，使其更加合理，利用拓?fù)潢P(guān)系對(duì)錨節(jié)點(diǎn)進(jìn)行選取，最后用加權(quán)質(zhì)心算法進(jìn)行位置估計(jì)。該算法能夠在不需要任何額外硬件的支持下，降低算法復(fù)雜度，減小定位誤差。4．2 傳統(tǒng)DVhop算法D Vhop算法由三部分組成。首先，利用典型的距離矢量路由協(xié)議使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得距離錨節(jié)點(diǎn)的最小跳數(shù)。然后，計(jì)算網(wǎng)絡(luò)平均每跳的距離(簡(jiǎn)稱(chēng)平均跳距)，并將其作為一個(gè)校正值廣播到整個(gè)網(wǎng)絡(luò)，當(dāng)未知節(jié)點(diǎn)收到這個(gè)值的時(shí)候計(jì)算出到錨節(jié)點(diǎn)的距離。最后，未知節(jié)點(diǎn)通過(guò)三邊定位或多邊定位計(jì)算它們的位置。第一步，每個(gè)錨節(jié)點(diǎn)廣播一個(gè)信標(biāo)信息到整個(gè)網(wǎng)絡(luò)中，此信標(biāo)信息包含了一個(gè)初始化為1的跳數(shù)值。每個(gè)收到此信息的節(jié)點(diǎn)將保留它所收到的每個(gè)錨節(jié)點(diǎn)的所有信標(biāo)信息中包含最小跳數(shù)值的信息，而丟棄較大值的信息。通過(guò)這種機(jī)制，網(wǎng)絡(luò)中所有的節(jié)點(diǎn)將得到距離每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)值。第二步，一旦一個(gè)錨節(jié)點(diǎn)得到了距離其它錨節(jié)點(diǎn)的最小跳數(shù)值，它就估計(jì)網(wǎng)絡(luò)中平均跳距，然后采用可控泛洪法將其值廣播到整個(gè)網(wǎng)絡(luò)中。當(dāng)未知節(jié)點(diǎn)收到平均跳距和距離其它錨節(jié)點(diǎn)的跳數(shù)后，它們將用平均跳距乘以跳數(shù)從而估計(jì)出到它們所能收到的所有錨節(jié)點(diǎn)的距離。錨節(jié)點(diǎn)i用下面的公式估計(jì)平均跳距: ()這里是錨節(jié)點(diǎn)和的坐標(biāo)，是錨節(jié)點(diǎn)和之間的跳數(shù)。每個(gè)未知節(jié)點(diǎn)將收到的第一個(gè)平均跳距值作為它的平均跳距并拋棄來(lái)自其它錨節(jié)點(diǎn)的其它平均跳距值。這樣可保證大多數(shù)節(jié)點(diǎn)可接收獲得第一個(gè)平均跳距值。這一步的最后，未知節(jié)點(diǎn)基于平均跳距和距離錨節(jié)點(diǎn)的最小跳數(shù)可計(jì)算出到錨節(jié)點(diǎn)的距離為: ()第三步，每個(gè)未知節(jié)點(diǎn)計(jì)算它的位置坐標(biāo)。假設(shè)和分別是未知節(jié)點(diǎn)和第個(gè)錨節(jié)點(diǎn)位置坐標(biāo)。用試表示第個(gè)錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離，可得到下面的公式: ()未知節(jié)點(diǎn)位置X可通過(guò)()式求得(此處M表示錨節(jié)點(diǎn)個(gè)數(shù)): ()（）式可展開(kāi)為 ()用矩陣形式表示如下: ()此處 的最小二乘估計(jì)是 ()4．3 傳統(tǒng)DVhop算法誤差分析DVhop算法把用兩點(diǎn)間的最小跳數(shù)表示的兩點(diǎn)間最短路徑看作一條直線(xiàn)，利用網(wǎng)絡(luò)平均跳距計(jì)算節(jié)點(diǎn)間的距離進(jìn)行定位。但在實(shí)際應(yīng)用中，首先，由于受到環(huán)境的影響，每個(gè)節(jié)點(diǎn)的通信范圍并不是一個(gè)標(biāo)準(zhǔn)的理想的圓域，而會(huì)呈現(xiàn)為一個(gè)相當(dāng)不規(guī)則多邊形。其次，網(wǎng)絡(luò)節(jié)點(diǎn)是隨機(jī)部署的，網(wǎng)絡(luò)拓?fù)鋾?huì)對(duì)定位性能產(chǎn)生相當(dāng)大的影響。最后，網(wǎng)絡(luò)中錨節(jié)點(diǎn)的比例對(duì)定位性能也有很大的影響。這些都在一定程度上影響DVhop算法的定位性能。1．拓?fù)潢P(guān)系對(duì)定位精度的影響。一般來(lái)講，未知節(jié)點(diǎn)選擇的錨節(jié)點(diǎn)越多，估計(jì)的精度應(yīng)該越高。但許多情況下并非如此。事實(shí)上，錨節(jié)點(diǎn)之間的拓?fù)潢P(guān)系和錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的拓?fù)潢P(guān)系在很大程度上將影響未知節(jié)點(diǎn)的定位。a．當(dāng)三個(gè)錨節(jié)點(diǎn)在一條直線(xiàn)上時(shí)，定位誤差將會(huì)很大。，當(dāng)錨節(jié)點(diǎn)、在一條直線(xiàn)上時(shí)，它們通信圓周的交點(diǎn)將會(huì)出現(xiàn)不確定性，即圖中所示的O和Q兩點(diǎn)，這勢(shì)必會(huì)導(dǎo)致估算位置與實(shí)際位置存在很大的誤差。b．當(dāng)任意兩個(gè)錨節(jié)點(diǎn)相距太近且它們又距離未知節(jié)點(diǎn)較遠(yuǎn)時(shí)，更容易導(dǎo)致較大的定位誤差。，錨節(jié)點(diǎn)、位置離得很近，而與未知節(jié)點(diǎn)O卻相距較遠(yuǎn)，這就會(huì)出現(xiàn)與和到口的距離相比，:之間的距離幾乎可以忽略不計(jì)，因此，就可能導(dǎo)致D的估算位置出現(xiàn)在口處，造成很大的定位誤差。c．當(dāng)三個(gè)錨節(jié)點(diǎn)很接近，且未知節(jié)點(diǎn)距離它們比較遠(yuǎn)時(shí)，無(wú)論它們組成什么三角形，將導(dǎo)致一個(gè)很大的定位誤差。，錨節(jié)點(diǎn), ,距離很近，而未知節(jié)點(diǎn)O的位置又距離此三個(gè)錨節(jié)點(diǎn)很遠(yuǎn)，如果節(jié)點(diǎn)間的估算誤差較大，那么未知節(jié)點(diǎn)O到這三個(gè)錨節(jié)點(diǎn)的估算距離就很可能幾乎一樣，此時(shí)如果利用這三個(gè)錨節(jié)點(diǎn)進(jìn)行位置估算，很可能將得到無(wú)解的結(jié)果或者定位誤差很大。d．錨節(jié)點(diǎn)的拓?fù)潢P(guān)系:對(duì)平均跳距的影響。如果在計(jì)算平均跳距時(shí)，某些錨節(jié)點(diǎn)由于相距太近而分不出彼此時(shí)，將會(huì)嚴(yán)重影響平均跳距的精度。e．網(wǎng)絡(luò)中的空洞對(duì)定位性能的影響。DVhop算法的估計(jì)位置誤差在節(jié)點(diǎn)分布的嚴(yán)重不均勻的情況下將有顯著增加。當(dāng)網(wǎng)絡(luò)中有空洞存在時(shí)，節(jié)點(diǎn)之間的最小跳數(shù)路徑將繞過(guò)“空洞這勢(shì)必會(huì)造成平均跳距偏小，反映不出真實(shí)情況。這種情況將會(huì)給節(jié)點(diǎn)的估計(jì)位置帶來(lái)很大的定位誤差。f．由于網(wǎng)絡(luò)拓?fù)涞挠绊?，?jié)點(diǎn)之間每一跳的距離彼此各不相同且最短路徑并不是事實(shí)上的直線(xiàn)，通過(guò)網(wǎng)絡(luò)平均跳距計(jì)算兩點(diǎn)間的距離會(huì)有很大的誤差。2．節(jié)點(diǎn)密集度和錨節(jié)點(diǎn)比例的影響。網(wǎng)絡(luò)中錨節(jié)點(diǎn)比例直接或間接的影響到網(wǎng)絡(luò)的各種性能。對(duì)于DVhop算法錨節(jié)點(diǎn)數(shù)量對(duì)其性能的影響也是巨大的。a．網(wǎng)絡(luò)布設(shè)的節(jié)點(diǎn)密集程度會(huì)對(duì)DVhop算法的各方性能產(chǎn)生直接的影響，如網(wǎng)絡(luò)平均的估算、網(wǎng)絡(luò)連通性、定位覆蓋率以及定位精度等。b．節(jié)點(diǎn)之間的估算距離誤差是隨著兩點(diǎn)間跳數(shù)的增加而增加的。，假設(shè)未知節(jié)點(diǎn)在錨節(jié)點(diǎn)和的最短路徑上，且此最短路徑為一條直線(xiàn)，通信半徑為R，錨節(jié)點(diǎn)到的平均跳距為,錨節(jié)點(diǎn)到的平均跳距為到，未知節(jié)點(diǎn)距離錨節(jié)點(diǎn)和都是跳，于是可以知道錨節(jié)點(diǎn)和之間的實(shí)際距離就是，和之間的實(shí)際距離為: ，但是通過(guò)DVhop算法得到和之間的距離為，可以得出DVhop估算兩點(diǎn)間距離的誤差 ,由此可以看出誤差將隨著跳數(shù)的增加而增加。因此，DVhop算法的定位精度跟錨節(jié)點(diǎn)的密度有很大的關(guān)系。當(dāng)錨節(jié)點(diǎn)的密度增加時(shí)，從未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的累積誤差將隨著兩點(diǎn)之間最短路徑的減少而降低，從而導(dǎo)致定位精度的增加。c．定位覆蓋率受網(wǎng)絡(luò)連通性影響。由于網(wǎng)絡(luò)中空洞的存在或其它因素的影響，很多未知節(jié)點(diǎn)將由于不能夠接收到滿(mǎn)足定位的錨節(jié)點(diǎn)信息而不能夠?qū)崿F(xiàn)定位幾。隨著網(wǎng)絡(luò)中錨節(jié)點(diǎn)數(shù)量的增加網(wǎng)絡(luò)覆蓋率也將得到相應(yīng)的增長(zhǎng)。3．關(guān)鍵信息浪費(fèi)的影響。在 DVhop中，往往假設(shè)距離未知節(jié)點(diǎn)最近的錨節(jié)點(diǎn)能為其提供最精確的平均跳距，但在網(wǎng)絡(luò)中有許多錨節(jié)點(diǎn)，這些錨節(jié)點(diǎn)每一個(gè)都包含有特定的平均跳距信息，但是在定位過(guò)程中大多數(shù)錨節(jié)點(diǎn)的平均跳距信息沒(méi)有得到充分的利用而被浪費(fèi)掉了。這將對(duì)平均跳距的精度產(chǎn)生嚴(yán)重的影響，從而導(dǎo)致較大的定位誤差。4．4 新的DVhop算法的設(shè)計(jì)及其實(shí)現(xiàn)傳統(tǒng)DVhop算法有三個(gè)階段，改進(jìn)后的算法也按三個(gè)階段進(jìn)行。4．4．1 跳數(shù)計(jì)算本階段的目標(biāo)是網(wǎng)絡(luò)中的節(jié)點(diǎn)獲得距離錨節(jié)點(diǎn)的最小跳數(shù)，與傳統(tǒng)DVhop算法相同。4．4．2 節(jié)點(diǎn)距離的計(jì)算這一階段具體又需要三步:第一步是計(jì)算每個(gè)錨節(jié)點(diǎn)的平均跳距。第二步是計(jì)算未知節(jié)點(diǎn)的平均跳距。最后再算出相距每個(gè)錨節(jié)點(diǎn)的距離。第一步:計(jì)算每個(gè)錨節(jié)點(diǎn)的平均跳距。1． 首先通過(guò)（）式和（）式算出每個(gè)錨節(jié)點(diǎn)的臨時(shí)平均跳距。 ()這里是錨節(jié)點(diǎn)和的坐標(biāo)，是錨節(jié)點(diǎn)和之間的跳數(shù)。表示錨節(jié)點(diǎn)和之間的平均跳距。 (}這里 是錨節(jié)點(diǎn)的數(shù)量，表示錨節(jié)點(diǎn)與所有其它錨節(jié)點(diǎn)間平均跳距求平均。2．然后，錨節(jié)點(diǎn)計(jì)算錨節(jié)點(diǎn)的平均跳距權(quán)值和錨節(jié)點(diǎn)的平均跳距:通過(guò)（）和（）式估算每個(gè)錨節(jié)點(diǎn)的平均跳距 ()這里是節(jié)點(diǎn)的通信距離。( () 表示錨節(jié)點(diǎn)的平均跳距。3．最后錨節(jié)點(diǎn)廣播到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)。第二步:第一步廣播后，所有節(jié)點(diǎn)得到了所有錨節(jié)點(diǎn)的。未知節(jié)點(diǎn)利用()和(()式計(jì)算錨節(jié)點(diǎn)的跳數(shù)權(quán)值和自身的平均跳距如下: () ()這里是錨節(jié)點(diǎn)的數(shù)量，,為錨節(jié)點(diǎn)的平均跳距，是未知節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的最小跳數(shù)。第三步:未知節(jié)點(diǎn)通過(guò)求出距錨節(jié)點(diǎn)的距離。最短路徑和未知節(jié)點(diǎn)平均跳距知道后根據(jù)文獻(xiàn)利用距離誤差進(jìn)一步改進(jìn)節(jié)點(diǎn)之間的距離。, 與錨節(jié)點(diǎn)D之間的跳數(shù)為 , (假設(shè)未知節(jié)點(diǎn), 在錨節(jié)點(diǎn), 的最短路徑上)未知節(jié)點(diǎn), 與錨節(jié)點(diǎn)之間的跳數(shù)為 , 。錨節(jié)點(diǎn)通過(guò)這條路徑到錨節(jié)點(diǎn)的跳數(shù)為，未知節(jié)點(diǎn), 的平均跳距為。, 之間的距離可以通過(guò)下式來(lái)計(jì)算: (),之間的距離可以通過(guò)下式來(lái)計(jì)算: ()通過(guò)以上的方法從而使未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離更加的真實(shí)可靠。4．4．3 錨節(jié)點(diǎn)組的選定和位置估計(jì)這一階段計(jì)算未知節(jié)點(diǎn)的位置坐標(biāo)。1．共線(xiàn)性文獻(xiàn)分析了錨節(jié)點(diǎn)拓?fù)潢P(guān)系對(duì)定位精度的影響，并為提高定位精度而提出了通過(guò)采用由錨節(jié)點(diǎn)組成三角形的三個(gè)高中的最小值作為判_定三個(gè)錨節(jié)點(diǎn)_是否共線(xiàn)的參數(shù)來(lái)選擇合適的