【正文】 節(jié)點(diǎn)M沒(méi)有。APIT算法的定位過(guò)程大體可描述如下:首先目標(biāo)定位節(jié)點(diǎn)收集其臨近錨節(jié)點(diǎn)的信息，然后從這些錨節(jié)點(diǎn)組成的集合中任意選取三個(gè)錨節(jié)點(diǎn)組成三角形。相對(duì)于計(jì)算簡(jiǎn)單的類(lèi)似的質(zhì)心定位算法，APIT算法定位精度高且性能穩(wěn)定，對(duì)錨節(jié)點(diǎn)的分布要求較低，但是APIT測(cè)試對(duì)網(wǎng)絡(luò)連通性有著很高的要求。第三個(gè)階段，利用三邊定位算法或其它定位方法，實(shí)現(xiàn)未知節(jié)點(diǎn)的定位。 (3 .18)式中，和分別是節(jié)點(diǎn)和在第一步中獲得的跳數(shù)值。但是該算法在實(shí)施定位以前需要事先預(yù)知網(wǎng)絡(luò)平均連通度，并且其定位效果受到節(jié)點(diǎn)密度的制約。3．4 本章小結(jié)本章主要對(duì)無(wú)線傳感網(wǎng)絡(luò)定位技術(shù)進(jìn)行了全面的討論。通過(guò)本章可以知道，每種定位系統(tǒng)或算法都有各自的特點(diǎn)和適用范圍，不存在絕對(duì)最優(yōu)的情況，因此在實(shí)際應(yīng)用中，應(yīng)該根據(jù)具體情況綜合考慮來(lái)選擇合適的定位算法或系統(tǒng)。為了提高定位精度，已經(jīng)有許多改進(jìn)的DVhop算法被提出來(lái)，例如:加權(quán)DVhop算法，該算法通過(guò)計(jì)算距離權(quán)值而得出較精確的位置估計(jì)。本章將在前人研究基礎(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ì)。然后，計(jì)算網(wǎng)絡(luò)平均每跳的距離(簡(jiǎn)稱平均跳距)，并將其作為一個(gè)校正值廣播到整個(gè)網(wǎng)絡(luò)，當(dāng)未知節(jié)點(diǎn)收到這個(gè)值的時(shí)候計(jì)算出到錨節(jié)點(diǎn)的距離。通過(guò)這種機(jī)制，網(wǎng)絡(luò)中所有的節(jié)點(diǎn)將得到距離每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)值。每個(gè)未知節(jié)點(diǎn)將收到的第一個(gè)平均跳距值作為它的平均跳距并拋棄來(lái)自其它錨節(jié)點(diǎn)的其它平均跳距值。用試表示第個(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)間最短路徑看作一條直線，利用網(wǎng)絡(luò)平均跳距計(jì)算節(jié)點(diǎn)間的距離進(jìn)行定位。這些都在一定程度上影響DVhop算法的定位性能。事實(shí)上，錨節(jié)點(diǎn)之間的拓?fù)潢P(guān)系和錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的拓?fù)潢P(guān)系在很大程度上將影響未知節(jié)點(diǎn)的定位。，錨節(jié)點(diǎn)、位置離得很近，而與未知節(jié)點(diǎn)O卻相距較遠(yuǎn)，這就會(huì)出現(xiàn)與和到口的距離相比，:之間的距離幾乎可以忽略不計(jì)，因此，就可能導(dǎo)致D的估算位置出現(xiàn)在口處，造成很大的定位誤差。如果在計(jì)算平均跳距時(shí)，某些錨節(jié)點(diǎn)由于相距太近而分不出彼此時(shí)，將會(huì)嚴(yán)重影響平均跳距的精度。這種情況將會(huì)給節(jié)點(diǎn)的估計(jì)位置帶來(lái)很大的定位誤差。對(duì)于DVhop算法錨節(jié)點(diǎn)數(shù)量對(duì)其性能的影響也是巨大的。因此，DVhop算法的定位精度跟錨節(jié)點(diǎn)的密度有很大的關(guān)系。隨著網(wǎng)絡(luò)中錨節(jié)點(diǎn)數(shù)量的增加網(wǎng)絡(luò)覆蓋率也將得到相應(yīng)的增長(zhǎng)。4．4 新的DVhop算法的設(shè)計(jì)及其實(shí)現(xiàn)傳統(tǒng)DVhop算法有三個(gè)階段，改進(jìn)后的算法也按三個(gè)階段進(jìn)行。最后再算出相距每個(gè)錨節(jié)點(diǎn)的距離。表示錨節(jié)點(diǎn)和之間的平均跳距。3．最后錨節(jié)點(diǎn)廣播到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)。最短路徑和未知節(jié)點(diǎn)平均跳距知道后根據(jù)文獻(xiàn)利用距離誤差進(jìn)一步改進(jìn)節(jié)點(diǎn)之間的距離。4．4．3 錨節(jié)點(diǎn)組的選定和位置估計(jì)這一階段計(jì)算未知節(jié)點(diǎn)的位置坐標(biāo)。錨節(jié)點(diǎn)通過(guò)這條路徑到錨節(jié)點(diǎn)的跳數(shù)為，未知節(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ù)。2．然后，錨節(jié)點(diǎn)計(jì)算錨節(jié)點(diǎn)的平均跳距權(quán)值和錨節(jié)點(diǎn)的平均跳距:通過(guò)（）和（）式估算每個(gè)錨節(jié)點(diǎn)的平均跳距 ()這里是節(jié)點(diǎn)的通信距離。1． 首先通過(guò)（）式和（）式算出每個(gè)錨節(jié)點(diǎn)的臨時(shí)平均跳距。4．4．2 節(jié)點(diǎn)距離的計(jì)算這一階段具體又需要三步:第一步是計(jì)算每個(gè)錨節(jié)點(diǎn)的平均跳距。在 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)掉了。c．定位覆蓋率受網(wǎng)絡(luò)連通性影響。b．節(jié)點(diǎn)之間的估算距離誤差是隨著兩點(diǎn)間跳數(shù)的增加而增加的。2．節(jié)點(diǎn)密集度和錨節(jié)點(diǎn)比例的影響。DVhop算法的估計(jì)位置誤差在節(jié)點(diǎn)分布的嚴(yán)重不均勻的情況下將有顯著增加。，錨節(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āng)錨節(jié)點(diǎn)、在一條直線上時(shí)，它們通信圓周的交點(diǎn)將會(huì)出現(xiàn)不確定性，即圖中所示的O和Q兩點(diǎn)，這勢(shì)必會(huì)導(dǎo)致估算位置與實(shí)際位置存在很大的誤差。一般來(lái)講，未知節(jié)點(diǎn)選擇的錨節(jié)點(diǎn)越多，估計(jì)的精度應(yīng)該越高。其次，網(wǎng)絡(luò)節(jié)點(diǎn)是隨機(jī)部署的，網(wǎng)絡(luò)拓?fù)鋾?huì)對(duì)定位性能產(chǎn)生相當(dāng)大的影響。這一步的最后，未知節(jié)點(diǎn)基于平均跳距和距離錨節(jié)點(diǎn)的最小跳數(shù)可計(jì)算出到錨節(jié)點(diǎn)的距離為: ()第三步，每個(gè)未知節(jié)點(diǎn)計(jì)算它的位置坐標(biāo)。當(dāng)未知節(jié)點(diǎn)收到平均跳距和距離其它錨節(jié)點(diǎn)的跳數(shù)后，它們將用平均跳距乘以跳數(shù)從而估計(jì)出到它們所能收到的所有錨節(jié)點(diǎn)的距離。第一步，每個(gè)錨節(jié)點(diǎn)廣播一個(gè)信標(biāo)信息到整個(gè)網(wǎng)絡(luò)中，此信標(biāo)信息包含了一個(gè)初始化為1的跳數(shù)值。4．2 傳統(tǒng)DVhop算法D Vhop算法由三部分組成。共線度引入到了DVhop中從而提出一種基于共線度的DVhop算法。DVhop算法是由Niculescu and NatP2在Navigate項(xiàng)目中提出的一種分布式基于非測(cè)距的定位算法。然后又重點(diǎn)介紹了幾種現(xiàn)有的典型定位算法和定位系統(tǒng)。得出質(zhì)心算法定位誤差最大，但其性能不受節(jié)點(diǎn)密度影響，實(shí)現(xiàn)最簡(jiǎn)單，通信開(kāi)銷(xiāo)最小。未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離可以通過(guò)來(lái)計(jì)算。 ()這里:是通信半徑，是本地鄰節(jié)點(diǎn)數(shù)即平均連通度。采用與DVhop類(lèi)似的方法獲取距錨節(jié)點(diǎn)的最小跳數(shù)路徑，稱為梯度值，不同的是Amorphous將通信半徑作為平均跳距，具體定位過(guò)程可以分為以下三個(gè)階段:第一個(gè)階段，未知節(jié)點(diǎn)計(jì)算與每個(gè)錨節(jié)點(diǎn)之間的最小跳數(shù)路徑，這一階段與DVhop算法相同。最后計(jì)算所有包含目標(biāo)節(jié)點(diǎn)的三角形的重疊區(qū)域，重疊區(qū)域的質(zhì)心即為目標(biāo)定位節(jié)點(diǎn)的估計(jì)位置。 C，就可判定節(jié)點(diǎn)對(duì)在4ABC內(nèi)幾。為了在無(wú)線傳感網(wǎng)絡(luò)中實(shí)現(xiàn)三角形內(nèi)點(diǎn)測(cè)試，近似三角形內(nèi)，點(diǎn)測(cè)試法被提了出來(lái)。3)APIT定位算法APIT算法[ys}的理論基礎(chǔ)就在于如何判斷一點(diǎn)位于三角形內(nèi)部，即最佳三角形內(nèi)點(diǎn)測(cè)試法PIT Cperfect pointintriangulation test。例如，假設(shè)未知節(jié)點(diǎn)接收到信標(biāo)信號(hào)的錨節(jié)點(diǎn)組的位置向量表示為: ()則該未知節(jié)點(diǎn)的坐標(biāo)就可表示為:(3 .15) ()質(zhì)心算法的優(yōu)點(diǎn)就在于不需要錨節(jié)點(diǎn)和未知節(jié)點(diǎn)之間相互協(xié)調(diào)，完全利用網(wǎng)絡(luò)連通性，簡(jiǎn)單易行。2)質(zhì)心算法質(zhì)心算法是Nirupama Bulusu等提出的一種基于網(wǎng)絡(luò)連通性的定位算法。最后，未知節(jié)點(diǎn)通過(guò)三邊定位或多邊定位計(jì)算它們的位置。1)DVhop算法Rutgers University的Dragos Niscules等人利用距離矢量路由(Distance VectorRouting)和GPS定位原理提出的DVhop, Euclidean, DV distance, DV Bearing ,DV coordinate和DV Radial六種分布式定位算法，合稱為APS。但該算法會(huì)產(chǎn)生大量的運(yùn)算和通信開(kāi)銷(xiāo)。首先未知節(jié)點(diǎn)利用TDOA測(cè)距技術(shù)測(cè)量到錨節(jié)點(diǎn)的距離。首先未知節(jié)點(diǎn)利用TOA測(cè)距技術(shù)測(cè)量到錨節(jié)點(diǎn)的距離。當(dāng)未知節(jié)點(diǎn)在測(cè)量出到達(dá)三個(gè)以上錨節(jié)點(diǎn)的距離后，利用三角定位法或其它方法估算出自身的位置坐標(biāo)。雖然在實(shí)驗(yàn)環(huán)境中該定位算法具有良好的特性。較典型的基于測(cè)距的定位算法主要有基于RSSI的定位算法、基于AOA的定位算法、基于TOA的定位算法和基于TDOA的定位算法等。這樣的誤差在實(shí)際應(yīng)用中是不可避免的，為了克服這種情況排除多余的節(jié)點(diǎn)取得最優(yōu)解，通常采用以下幾種估計(jì)方法。在計(jì)算出這些數(shù)據(jù)后，可以利用三邊定位方法，算出未知節(jié)點(diǎn)的位置坐標(biāo)。它到錨節(jié)點(diǎn)的角度分別為創(chuàng)。根據(jù)檢測(cè)的結(jié)果可以確定出未知節(jié)點(diǎn)的大致位置。，已知平面上三點(diǎn)個(gè)節(jié)點(diǎn)的坐標(biāo)，以及它們到未知節(jié)點(diǎn)的距離分別為: 和。分別表示之間的距離，的最小跳數(shù)分別表示為。不同的距離如果相差倍，則測(cè)量獲得的相位相同。由于該技術(shù)受外界環(huán)境的影響比較明顯，所以，測(cè)距精度會(huì)產(chǎn)生較大偏差，同時(shí)該技術(shù)還需要額外的硬件設(shè)備完成測(cè)角。該技術(shù)的測(cè)距精度可以達(dá)到厘米級(jí)，但受到超聲波信號(hào)的限制(超聲波信號(hào)傳播距離69米)和非視距問(wèn)題的影響，網(wǎng)絡(luò)需要密集部署，會(huì)產(chǎn)生大量運(yùn)算和通信開(kāi)銷(xiāo)。其計(jì)算公式分別如式()和()，式中為信號(hào)傳播速度。另一種方法是測(cè)量信號(hào)往返時(shí)間即RTOF，信號(hào)在到達(dá)接收節(jié)點(diǎn)后直接返回，發(fā)送節(jié)點(diǎn)測(cè)量收發(fā)的時(shí)間差作為途經(jīng)時(shí)間，此方法避免了節(jié)點(diǎn)間時(shí)間同步的要求。該技術(shù)最典型的應(yīng)用如GPS，在無(wú)線傳感網(wǎng)絡(luò)中，由于節(jié)點(diǎn)之間的距離相對(duì)較小，采用傳播時(shí)間測(cè)距難度較大，同時(shí)節(jié)點(diǎn)價(jià)格、功耗和硬件設(shè)備也限制了該技術(shù)在無(wú)線傳感網(wǎng)絡(luò)中的應(yīng)用。表示標(biāo)準(zhǔn)偏差，是由遮蔽效應(yīng)引起的正態(tài)隨機(jī)變量，單位。它的誤差主要來(lái)源于多徑傳播、反射、非視距傳播以及天線增益等，這些因素都會(huì)造成相同距離產(chǎn)生顯著不同的傳播損耗，從而造成信號(hào)傳播模型建模的復(fù)雜性，因此精度比較低，有時(shí)RSSI的測(cè)距誤差可達(dá)到50%。3．2．2 節(jié)點(diǎn)間距離的測(cè)量方法測(cè)量節(jié)點(diǎn)之間角度或距離的方法有很多，直接測(cè)距的方法有接收信號(hào)強(qiáng)度(RSSSI)，到達(dá)時(shí)間(TOA)，往返傳播時(shí)間(Roundtrip Time of Flight,RTOF ),到達(dá)時(shí)間差(TDOA)，以及到達(dá)角度(AOA)等。盡管現(xiàn)有的定位算法各不相同，但從基本原理上講，現(xiàn)有的無(wú)線傳感網(wǎng)絡(luò)定位機(jī)制通常由以下三步組成：第一步，未知節(jié)點(diǎn)通過(guò)一定的手段或方法估計(jì)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離。2．每一個(gè)節(jié)點(diǎn)都具有全網(wǎng)唯一的ID。如果采用直接獲得節(jié)點(diǎn)位置的方式即為每個(gè)節(jié)點(diǎn)裝備全球定位系統(tǒng)(GPS)，考慮到價(jià)格、體積、功耗等因素的限制，通常該方案也被排除在外。此種優(yōu)化路由需要網(wǎng)絡(luò)中的節(jié)點(diǎn)知曉每個(gè)節(jié)點(diǎn)或者至少相鄰節(jié)點(diǎn)的位置信息，據(jù)此做出優(yōu)化的路由選擇。對(duì)天然氣管道泄露具體位置進(jìn)行監(jiān)控等。另外，在工廠、物流管理和醫(yī)院儀器管理等環(huán)境中都有很廣泛的應(yīng)用和迫切的需求。2．目標(biāo)跟蹤目標(biāo)跟蹤是指網(wǎng)絡(luò)實(shí)時(shí)監(jiān)測(cè)目標(biāo)的行動(dòng)路線，預(yù)測(cè)目標(biāo)的前進(jìn)軌跡。無(wú)線傳感網(wǎng)絡(luò)中不但有很多特定應(yīng)用都依賴于節(jié)點(diǎn)或目標(biāo)物體的地理位置信息，而且很多網(wǎng)絡(luò)運(yùn)行和管理也需要位置信息的輔助，如基于地理位置信息的路由、資源的有效配置、對(duì)外部目標(biāo)的定位和跟蹤等。3．能量高效性為了盡量延長(zhǎng)網(wǎng)絡(luò)的生存周期，要盡可能的減少節(jié)點(diǎn)間的通信開(kāi)銷(xiāo)，減少算法中計(jì)算的復(fù)雜度，用盡量少的能量完成盡可能多的工作。通常無(wú)線傳感網(wǎng)絡(luò)定位技術(shù)具備以下特點(diǎn)。基礎(chǔ)設(shè)施:協(xié)助傳感器節(jié)點(diǎn)定位的已知自身位置的固定設(shè)備，如衛(wèi)星、基站等。視線關(guān)系:沒(méi)有任何障礙物間隔的兩個(gè)節(jié)點(diǎn)間能夠直接通信的關(guān)系。到達(dá)時(shí)間:一種信號(hào)從一個(gè)節(jié)點(diǎn)傳播到另一個(gè)節(jié)點(diǎn)所需的時(shí)間。跳數(shù):兩個(gè)節(jié)點(diǎn)之間間隔的跳段總數(shù)。另一種是符號(hào)位置，它表示的是目標(biāo)與基站之間的連通關(guān)系，提供目標(biāo)大致的所在范圍，即指在目標(biāo)與一個(gè)基站或者多個(gè)基站接近程度的信息。它是網(wǎng)絡(luò)自身屬性的確定過(guò)程，是網(wǎng)絡(luò)的支撐，可以通過(guò)人工配置或各種節(jié)點(diǎn)自定位算法完成，它是整個(gè)無(wú)線傳感網(wǎng)絡(luò)存在的必要的支撐技術(shù)之一。3．1 無(wú)線傳感網(wǎng)絡(luò)定位技術(shù)概述3．1．1 無(wú)線傳感網(wǎng)絡(luò)定位的概念對(duì)于定位一般的理解就是確定位置。還可以用于目標(biāo)跟蹤、目標(biāo)軌跡預(yù)測(cè)、協(xié)助路由等。節(jié)點(diǎn)只有知道了自身的位置信息，才能夠提供有效的監(jiān)測(cè)消息。這些傳感器節(jié)點(diǎn)形成一個(gè)無(wú)線傳感交通網(wǎng)，通過(guò)該網(wǎng)絡(luò)可以查詢信息或者發(fā)出控制指令。通過(guò)把傳感器節(jié)點(diǎn)嵌入到家具和家電中組成無(wú)線傳感網(wǎng)絡(luò)，并與互聯(lián)網(wǎng)連接相連，為人類(lèi)的生活提供更加方便、舒適和人性化的智能環(huán)境。2．環(huán)境監(jiān)測(cè)當(dāng)今社會(huì)環(huán)境問(wèn)題受到越來(lái)越多的關(guān)注，環(huán)境保護(hù)越來(lái)越受到重視。因此，應(yīng)用層的研究主要是各種無(wú)線傳感網(wǎng)絡(luò)應(yīng)用系統(tǒng)的開(kāi)發(fā)和多任務(wù)之間的協(xié)調(diào)。在無(wú)線傳感網(wǎng)絡(luò)操作系統(tǒng)的支持下，多個(gè)應(yīng)用可以并發(fā)地使用系統(tǒng)的有限資源。另外，很多研究機(jī)構(gòu)把IEEE 。8．無(wú)線通信技術(shù)無(wú)線傳感網(wǎng)絡(luò)的通信帶寬窄而且經(jīng)常變化，通信覆蓋范圍只有幾十到幾百米。7．?dāng)?shù)據(jù)管理從數(shù)據(jù)存儲(chǔ)的角度來(lái)看，無(wú)線傳感網(wǎng)絡(luò)是一種分布式數(shù)據(jù)庫(kù)。數(shù)據(jù)融合可以在各個(gè)傳感器節(jié)點(diǎn)收集數(shù)據(jù)的過(guò)程中利用節(jié)點(diǎn)的本地計(jì)算和存儲(chǔ)能力去除冗余信息，減少傳輸?shù)臄?shù)據(jù)量，從而有效的節(jié)省能量。4．定位技術(shù)位置信息是無(wú)線傳感網(wǎng)絡(luò)正常工作和應(yīng)用中不可缺少的部分，缺少位置信息網(wǎng)絡(luò)很可能無(wú)法正常工作，在某些應(yīng)用中缺少位置信息也將會(huì)是致命的。3．時(shí)間