【基于非測距的物聯(lián)網(wǎng)定位算法展開探究10000字（論文）】

--PAGE5-基于非測距的物聯(lián)網(wǎng)定位算法展開研究目錄TOC\o"1-2"\h\u30718第一章緒論 283061.1課題的研究背景及意義 228231.3物聯(lián)網(wǎng)定位技術(shù)研究現(xiàn)狀 3284581.4研究內(nèi)容和章節(jié)安排 410258第二章物聯(lián)網(wǎng)定位技術(shù)介紹 668052.1定位技術(shù)簡介 6173532.2基于非測距的定位算法 6319082.3基于測距的定位算法 8206412.5本章小結(jié) 1217714第三章DV-Hop算法及其改進 1344383.1DV-Hop算法 13320203.3DV-Hop算法誤差分析 1482703.2DV-Hop算法優(yōu)化 15159833.2本章小結(jié) 1623306第四章仿真實驗與分析 1724344第五章總結(jié)與展望 28第一章緒論1.1課題的研究背景及意義物聯(lián)網(wǎng)IOT是指通過各種各樣的信息傳感器、射頻識別技術(shù)、全球定位系統(tǒng)、紅外感應(yīng)器、激光掃描器等各種裝置或技術(shù)，通過各類存在的網(wǎng)絡(luò)進行接入，將各種各樣傳感器與網(wǎng)絡(luò)結(jié)合起來而實現(xiàn)在任何時間、任何地點，人、機、物互聯(lián)互通的網(wǎng)絡(luò)統(tǒng)稱。早在15世紀(jì)時，當(dāng)人類開始將目光投向廣闊的海洋并決定對其展開探索時，定位技術(shù)就已經(jīng)給當(dāng)時的人們帶來了很大的幫助，但由于當(dāng)時的定位技術(shù)尚處于剛開始發(fā)展的階段，所以當(dāng)時的定位方法也十分的粗糙，例如，出海的船只能依賴于航海線和引航燈航行、運用航海圖和星象圖來大致確認(rèn)自己所處的位置這便是物聯(lián)網(wǎng)定位的前身。在物聯(lián)網(wǎng)的眾多相關(guān)技術(shù)中，感知層的定位技術(shù)定位技術(shù)在該網(wǎng)絡(luò)的眾多技術(shù)中起決定性作用，同時也是物聯(lián)網(wǎng)推廣應(yīng)用的前提條件，該技術(shù)主要是對一些目標(biāo)進行監(jiān)測、識別和跟蹤。隨著硬件設(shè)備行業(yè)的不斷發(fā)展，帶來了物聯(lián)網(wǎng)領(lǐng)域的飛速發(fā)展，定位技術(shù)在技術(shù)手段、定位的精確度、定位范圍及可用性等方面都有了質(zhì)的飛躍。科技的進步，帶來的是我們生活環(huán)境的巨大變化，當(dāng)然，這種變化是朝向帶給人們快捷和便利的方向的。舉一個很簡單的例子，現(xiàn)代社會的人們的日常生活幾乎離不開手機的使用，而手機中的多數(shù)軟件的使用都需要用到手機的位置信息，利用定位技術(shù)獲取的定位信息在這些軟件的相關(guān)功能中扮演者及其重要的角色。往更高的層面看，在國防領(lǐng)域，一些精準(zhǔn)制導(dǎo)的導(dǎo)彈只有通過定位技術(shù)獲取到目標(biāo)的精確位置后才能將導(dǎo)彈發(fā)射到隔著十萬八千里的目標(biāo)位置并根據(jù)目標(biāo)的位置變化調(diào)整導(dǎo)彈的飛行軌跡。由此可見定位技術(shù)的重要性。在目前成熟的定位技術(shù)中，全球定位系統(tǒng)GPS和北斗衛(wèi)星等全球衛(wèi)星定位系統(tǒng)是對目標(biāo)進行定位的主要手段，但它們對硬件設(shè)備的成本、功耗和體積等方面都提出了很高的要求。此外，物聯(lián)網(wǎng)定位技術(shù)還包括如近幾年發(fā)展的蜂窩網(wǎng)絡(luò)通過無線電和基站的定位技術(shù)，以及基于RFID標(biāo)簽的定位技術(shù)等。定位技術(shù)很多很多，通過對簡單的定位技術(shù)進行分析比較，得到它們的優(yōu)缺點，找到它們不同的適合應(yīng)用場景，這是在定位技術(shù)研究領(lǐng)域的熱門課題，也是設(shè)計出更加優(yōu)秀的+定位算法的必要條件。1.3物聯(lián)網(wǎng)定位技術(shù)研究現(xiàn)狀節(jié)點定位技術(shù)牽涉到的相關(guān)技術(shù)指標(biāo)比較多，包括節(jié)點定位的誤差大小、通信網(wǎng)絡(luò)是否可靠、路由算法、功率大小及硬件成本等，這些導(dǎo)致不同的定位算法在使用它們進行定位計算時，會出現(xiàn)不同的優(yōu)缺點，這帶來了它們有著各自不同的適用領(lǐng)域。對于這些定位算法，按照定位機制，一般可將其劃分為基于測距（Range-Based）和非測距（Range-Free）的定位算法，這也是目前最廣為人所采用的劃分依據(jù)?；跍y距的定位算法，指布置額外的硬件設(shè)備來得節(jié)點數(shù)據(jù)，再利用這些得到的已知節(jié)點的數(shù)據(jù)信息來估算未知節(jié)點的位置坐標(biāo)信息。比較常見的基于測距的定位算法有基于最小二乘法的定位算法、基于接受信號強度RSSI測距的定位算法、基于到達時間TOA的定位算法，基于到達時間差TDOA的定位算法等。這些基于測距的定位算法因為需要部署額外的硬件設(shè)備，所以它們的節(jié)點布設(shè)硬件成本很高，通信開銷也較大，但相對的，這些算法的覆蓋率以及定位精確度都相對較高?；诜菧y距的定位算法，在于不用去像基于測距的算法那樣部署節(jié)點得到節(jié)點數(shù)據(jù)，而是只需通過網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的節(jié)點之間的關(guān)系和已經(jīng)知道的信息，便可以通過相關(guān)數(shù)學(xué)公式大致計算出目標(biāo)的位置信息。目前這一算法算是學(xué)者們最常研究的定位算法方向，因為它更加適用于在一些無需高精確度的場景中，而且無需顧慮過高硬件成本、環(huán)境影響等因素。這些算法包括質(zhì)心定位算法、網(wǎng)格定位算法、DV-Hop算法等。現(xiàn)有的物聯(lián)網(wǎng)定位算法在一定程度上能夠滿足大多數(shù)節(jié)點的定位問題，但是應(yīng)用場景需要滿足特定的限制條件。如果在不滿足限制條件的情況下使用，往往會出現(xiàn)與預(yù)期差距過大的情況，即定位的精確度和穩(wěn)定性會大幅度地下降，以至于無法得到正常的使用。分析已有算法的優(yōu)缺點，在滿足限制條件的情況下，提高定位算法的性能是當(dāng)前研究的熱門問題。算法是定位技術(shù)的核心。監(jiān)測區(qū)域中的錨節(jié)點是定位算法的基石，考慮到硬件成本和運行維護能耗等問題，我們一般會將監(jiān)測區(qū)域內(nèi)的錨節(jié)點控制在一定范圍之內(nèi)，當(dāng)降低監(jiān)測區(qū)域內(nèi)錨節(jié)點的部署密度時，定位算法的定位精度和定位覆蓋率會出現(xiàn)較為明顯的下降。文獻[1]通過將粒子群算法與DV-Hop算法結(jié)合，利用適應(yīng)度函數(shù)搜索到的群體最優(yōu)值作為未知節(jié)點的位置坐標(biāo),以此來提高節(jié)點的定位精度。文獻[2]將接收信號強度與Sigmoid函數(shù)結(jié)合起來作為權(quán)重以此來改進加權(quán)質(zhì)心定位算法，通過優(yōu)化后的算法來計算出未知節(jié)點的坐標(biāo)，通過仿真實驗表明，這種改進能夠極大提升算法性能。由此來說，在更加接近真實環(huán)境的非理想驗環(huán)境下，如何通過優(yōu)化已有的算法來來提高算法的性能是物聯(lián)網(wǎng)定位算法研究領(lǐng)域的研究熱點。1.4研究內(nèi)容和章節(jié)安排1.4.1主要工作和內(nèi)容本文首先介紹了物聯(lián)網(wǎng)定位算法的研究背景以及研究現(xiàn)狀。接著介紹了幾種基于測距的定位算法的實現(xiàn)原理，以及它們的優(yōu)缺點，在第三章中著重介紹了基于非測距的三種基本算法，以及改進的加權(quán)質(zhì)心定位算法，并通過仿真實驗數(shù)據(jù)橫向?qū)Ρ确治隽速|(zhì)心定位算法與加權(quán)質(zhì)心定位算法。1.4.2章節(jié)安排本文在大量學(xué)者的不斷努力上，對經(jīng)典算法的原理進行了相關(guān)介紹，結(jié)合其他相關(guān)研究成果，著重研究了DV-Hop及它的一個優(yōu)化后的定位算法。結(jié)構(gòu)安排如下：第一章：緒論章節(jié)主要介紹了物聯(lián)網(wǎng)定位技術(shù)的當(dāng)前研究背景和研究意義、研究現(xiàn)狀以及介紹了部分學(xué)者對該領(lǐng)域的研究情況，最后對本論文的研究內(nèi)容和組織結(jié)構(gòu)進行了介紹。第二章：介紹了幾種經(jīng)典的定位算法，如基于非測距的質(zhì)心定位、加權(quán)質(zhì)心定位、網(wǎng)格定位。基于測距的最小二乘法定位，RSSI定位、TDA/TDOA定位算法等。第三章：著重介紹了基于非測距的DV-Hop及其優(yōu)化算法，對他們的原理、誤差進行了分析。第四章為實驗仿真部分。本章節(jié)首先定義了仿真實驗的誤差。仿真實驗驗證了三種經(jīng)典的非測距定位算法以及一種優(yōu)化的DV-Hop算法，結(jié)果證明改進的算法對性質(zhì)有了顯著提升。第五章為文章的全文總結(jié)及未來展望部分，本章節(jié)總結(jié)了本論文完成的主要工作，以及在最后對下一步研究的方向進行了規(guī)劃。

第二章物聯(lián)網(wǎng)定位技術(shù)介紹2.1定位技術(shù)簡介目標(biāo)定位算法是獲取目標(biāo)位置的手段之一，利用觀測到的數(shù)據(jù)信息，采用適當(dāng)?shù)亩ㄎ凰惴?、結(jié)合應(yīng)用場景的特點進行目標(biāo)定位能達到較好的效果。通過定位算法是無法得到與目標(biāo)真實位置完全一致的位置信息的，但使用它能從最大程度上逼近真實位置，從而使定位誤差降到合理的閾值以下。目標(biāo)定位算法分為基于測距的定位算法和基于非測距的定位算法。2.2基于非測距的定位算法非測距定位Range-free，廣泛的指不依賴于任何信息，無需測量目標(biāo)與節(jié)點之間的距離、角度等數(shù)據(jù)信息，或者當(dāng)被測目標(biāo)與節(jié)點間的在距離和角度方面的誤差非常大時，只能用這些信息作權(quán)值使用的算法?；诜菧y距的定位算法，只能依靠觀測站的物理部署和簡單的觀測站是否探測到目標(biāo)的“0”“1”二進制信息來對目標(biāo)位置進行估計。非測距定位算法主要包有質(zhì)心定位算法、加權(quán)質(zhì)心定位算法和網(wǎng)格定位算法等，它們雖然能估計出具體位置，但是這個位值往往與目標(biāo)真實位置的偏差比較大。2.2.1質(zhì)心定位算法質(zhì)心即質(zhì)量中心，指物質(zhì)系統(tǒng)上被認(rèn)為該物體質(zhì)量集中于此的一個假象點。三角形三條中線的交點、平行四邊形的對角線、正六邊形的對角線交點，這些點都可以看做是這些常見幾何圖形的質(zhì)心，如下圖所示圖2.1幾何圖形的質(zhì)心對于多質(zhì)點系統(tǒng)來說，假定每個質(zhì)點的重量為mi，位置為p(xi,yi,zi),那么該質(zhì)點的質(zhì)心計算方法可以用公式（2-1）來表示：（2-1）當(dāng)考慮各質(zhì)點的質(zhì)量一樣時，那么多質(zhì)點系統(tǒng)質(zhì)心的計算方法則可以簡化為：（2-2）上述即為質(zhì)心定理，通常用來計算一個圖形或者物體的質(zhì)心坐標(biāo)，當(dāng)將此定理的原理用在物聯(lián)網(wǎng)定位領(lǐng)域上，它便變成了熟知的質(zhì)心定位算法：假定在一個場地內(nèi)，分布著若干個觀測站，每一個觀測站的位置設(shè)為p(xi,yi,zi)，將能夠探測到的目標(biāo)的所有觀測站看成一個多質(zhì)點系統(tǒng)，此時按照簡化后的質(zhì)心計算方法便可以計算得到一個位置，這個位置便是目標(biāo)位置的估計值。2.2.2加權(quán)質(zhì)心定位算法觀測站在探測目標(biāo)時，傳感器可以根據(jù)探測到的目標(biāo)信號的強度，如聲音信號強度（dB）或無線接收信號強度（RSSI）粗略的判斷目標(biāo)的遠(yuǎn)近，并將這個強度作為一個權(quán)值，用在質(zhì)心定位算法中，這便是加權(quán)質(zhì)心定位算法了，它可以被表示為： （2-3）式（2-3）中，（xc,yc,zc）表示第i個基站的位置，w是權(quán)值。那么，在使用計算機進行仿真時，需要通過一定的數(shù)學(xué)關(guān)系來建模并表示這一權(quán)值w：一般地，權(quán)值與距離被認(rèn)為會具有一定的比例關(guān)系，如RSSI與距離有近似反比的關(guān)系，建模時可粗略的認(rèn)為： （2-4）式（2-4）中，r為目標(biāo)與觀測站的距離；n為噪聲，表示觀測站測得的RSSI和聲音信號的強度是受到噪聲干擾的。噪聲的給定方法可以參考信噪比（SignalToNoiseRatio,SNR）參數(shù)，它的定義如下： （2-5）式（2-5）中，S表示信號值，在這里表示接收到的信號強度值（聲音強度值）；N表示噪聲的方差。假如信噪比是10dB,那么。2.2.3網(wǎng)格定位算法將觀測站均勻的部署在檢測場地，并將它們整齊地排列成隊列網(wǎng)絡(luò)的形式，以此來計算目標(biāo)位置的算法稱為網(wǎng)格定位算法。網(wǎng)格定位算法的特點是將監(jiān)控區(qū)域網(wǎng)格劃分，它在位置表示、坐標(biāo)系建立、后臺管理等方面具有優(yōu)勢在網(wǎng)格中，所有節(jié)點都位于監(jiān)測區(qū)域內(nèi)，當(dāng)將此區(qū)域D進一步劃分為n2或nm個單元時，通信半徑一般為大于1個單元而小于2個單元區(qū)域，即邊長為2個單元的正方形區(qū)域。由于觀測站部署密集，為了簡單有效，對于進入檢測區(qū)域內(nèi)的目標(biāo)，可以選用探測到目標(biāo)信號最強的幾個觀測站的位置信息來估計目標(biāo)的位置。網(wǎng)格定位是一種避免網(wǎng)絡(luò)大量通信的節(jié)能的定位算法。適合大量部署的檢測環(huán)境，如無線傳感器網(wǎng)絡(luò)。它也是一種在硬件節(jié)點探測能力有限的或傳感器信息準(zhǔn)確度較低的場合中應(yīng)用的一種有效的定位算法。2.3基于測距的定位算法基于非測距的定位算法誤差通常來說是比較大的，要想提高精確度往往得提高觀測站的部署密集度。但是對于很多功能強大的觀測站，尤其是能實現(xiàn)精確測距和測角的觀測站，實現(xiàn)精確定位就很容易。例如雷達、聲吶等能非常準(zhǔn)確地測量其與目標(biāo)之間的距離。對于定位算法而言，它只能最大限度地降低誤差，而不能完全地消除誤差。下面介紹的是兩種常見的基于測距的定位算法（Range-based）：最小二乘定位算法和基于RSSI測距的定位算法。2.3.1最小二乘定位算法設(shè)目標(biāo)的坐標(biāo)為M(x,y)，監(jiān)測區(qū)域內(nèi)有n個觀測站，它們的的坐標(biāo)分別為（x1,y1）,(x2,y2),…，（xn,yn）,目標(biāo)到觀測站的距離分別是d1,d2,…，dn,則： （2-6）在式（2-6）的基礎(chǔ)上，從上至下依次與最后一式相減，就可以得到如下式 （2-7）由最小二乘原理原理可以得到目標(biāo)位置的最小二乘估計值X： （2-8）式中，此式是基于觀測距離的目標(biāo)定位系統(tǒng)中最常用的定位算法。式中，當(dāng)矩陣A大于等于2時，解有唯一一個。換句話說，只通過觀測距離而要對二維平面目標(biāo)定位需要至少3個并且是部署在不同位置的觀測站，同樣的道理，對三位空間目標(biāo)定位時，需要至少4個并且是部署在不共面的空間位置中的的觀測站。2.3.2基于RSSI測距的定位算法漸變模型（ShadowingModel）是在無線信號傳輸中被普遍采用的理論模型： （2-9）式中,d表示發(fā)射端與接收端的距離；p(d)表示RSSI值，即接收端與發(fā)射端之間的距離為d時接收到的信號強度；p(d0)表示接收端與發(fā)射端之間的距離為d0時接收到的信號功率；d0為參考距離；n是路徑損耗PassLoss指數(shù)，通常由實際測量得到，障礙物越多，n值越大，從而接收到的平均能量下降的速度會隨著距離的增加而變得越來越快：X是一個以dBm為單位、平均值為0的高斯隨機變量，表示當(dāng)距離一定時接收機接收到的能量值的變化情況。實際應(yīng)用中一般采用簡化的漸變模型： （2-10）為了便于表達和計算，通常取d0為1m。把p(d)改成RSSI，于是可得： （2-11）式中，A為無線收發(fā)節(jié)點之間相距1m時接收節(jié)點接收到的無線信號強度RSSI值。根據(jù)式（2-11）中給定的RSSI與d的函數(shù)模型，只需知道接收機接收到的RSSI值，接收機與發(fā)射機之間的距離d便可以通過此式計算得出。基于RSSI測距的定位算法流程如下：圖2.2RSSI測距流程圖2.3.3基于TOA的定位算法基于TOA的測距通過測量兩個節(jié)點之間信號的傳輸速度和時間延遲來估算兩點之間的距離精度的。如圖2.3所示，信號在t1時刻從節(jié)點A發(fā)出,在t2時刻到達節(jié)點B，t3時刻時從節(jié)點B返回，最后在t4時刻節(jié)點A重新收到該信號，設(shè)信號傳播速度為v，那么節(jié)點A、B之間的距離d為： （2-12）圖2.3TOA測距示意圖基于TOA測距的方法由于無線信號的傳輸速度快，時間測量即便有很小的誤差都會導(dǎo)致結(jié)果距離出現(xiàn)很大的誤差值，另外它對于傳感器節(jié)點有很高的計算能力要求。2.3.4基于TDOA的定位算法兩個節(jié)點發(fā)送無線電磁波、超聲波信號兩種不同的信號，接收節(jié)點通過信號的到達時間差，根據(jù)這兩種信號的傳播速度來計算收發(fā)節(jié)點間距離的方法，就是基于TDOA到達時間差的測距方法。如圖2.4所示，節(jié)點A在t0時刻發(fā)送兩種不同的信號給節(jié)點B，節(jié)點B分別在t1和t2時刻收到這兩種信號，兩種信號的傳播速度分別設(shè)為v1、v2,那么節(jié)點A、B之間的距離d可用式來表示： （2-13）圖2.4TDOA測距示意圖由于超聲波信號的傳播速度比較低（約為331.4m/s）,因此基于超聲波的TDOA定位機制可以在時間測量并不是特別精準(zhǔn)的條件下進行精準(zhǔn)定位。同時在使用TDOA方式進行定位時不需要全局時間同步，也不需要利用信號到達的絕對是件來確定節(jié)點的位置，降低了設(shè)備在時間方面的要求，因此易于實現(xiàn)且精度較高。但是。基于超聲波的TDOA定位算法在距離的測量上還存在著一定的局限性。首先，由于超聲波信號的傳播具有方向性，當(dāng)收發(fā)節(jié)點之間存在障礙物時，會帶來較大的測距偏差；其次，此方法需要超聲波信號收發(fā)節(jié)點在一定的角度范圍內(nèi)才能收集到數(shù)據(jù)，并且角度的不同也會帶來測距精度的上下浮動；第三，因為超聲波信號衰減較快，所以它的傳播距離往往較短，通常在十幾米的范圍內(nèi)；另外，超聲波的傳播特性會在一定程度上受到風(fēng)向、溫度等環(huán)境因素的影響。綜上，超聲波定位比較適合范圍小、精度高的室內(nèi)定位環(huán)境。2.5本章小結(jié)物聯(lián)網(wǎng)定位技術(shù)可以分為基于非測距的定位技術(shù)和基于測距的定位技術(shù)兩類：對于非測距的定位算法而言，它們的精確度一般都不高，并且精確度往往與檢測場地部署的觀測站密度有關(guān)。但是基于非測距的定位算法無需測量節(jié)點的距離、方位、到達時間等，而是利用網(wǎng)絡(luò)連通度的信息以及信標(biāo)節(jié)點與未知節(jié)點間的幾何關(guān)系求出未知節(jié)點的坐標(biāo)。這種類型的定位算法對傳感器節(jié)點設(shè)備的要求較小。

DV-Hop算法及其改進3.1DV-Hop算法DV-Hop算法在APS算法系列中是最為研究者研究的定位算法，在DV-Hop的算法過程中，它不依賴于通過測距方法得到測量的物理量，而是利用多跳信標(biāo)節(jié)點信息來進行信標(biāo)定位。它所采用的算法機制與傳統(tǒng)網(wǎng)絡(luò)中的距離路由向量路由機制十分相似，在其中，未知的節(jié)點通過跳數(shù)和平均跳距計算出與信標(biāo)節(jié)點之間的最小跳數(shù)，然后估算平均每跳距離，之后將最小跳數(shù)與平均每跳距離相乘得到估算出的未知節(jié)點和信標(biāo)節(jié)點之間的距離，在最后通過這些計算得到的距離，使用三邊測距法或者極大似然估計法即可求得未知節(jié)點的坐標(biāo)。DV-Hop定位算法可分為以下三個步驟：計算未知節(jié)點與每一個錨節(jié)點的最小跳數(shù)在初始化網(wǎng)絡(luò)時，網(wǎng)絡(luò)中的已知節(jié)點就會不斷地向周圍節(jié)點廣播自己的位置信息的分組，在初始階段將跳數(shù)字段設(shè)置為0.網(wǎng)絡(luò)中的接收節(jié)點會接受并記錄具有到每一個錨節(jié)點的最小跳數(shù)。在將來自同一個信標(biāo)節(jié)點的較大跳數(shù)的分組忽略后，將跳數(shù)值加1，之后將其轉(zhuǎn)發(fā)給鄰居節(jié)點，之后通過不斷地接收-轉(zhuǎn)發(fā)網(wǎng)絡(luò)中的所有的節(jié)點都能夠接收到相應(yīng)的數(shù)據(jù)信息并將信息中的每一個節(jié)點的最小跳數(shù)記錄下來。計算未知節(jié)點和錨節(jié)點的平均每一跳距離根據(jù)步驟（1）記錄的其他錨節(jié)點的位置信息和相距跳數(shù)，每個錨節(jié)點利用下式估算平均每跳的實際距離： （3-1）其中，（xi,yi）為錨節(jié)點i的位置坐標(biāo)；hj為錨節(jié)點i與j（j≠i）之間的跳段數(shù)。之后，錨節(jié)點將計算得到的每跳平均距離用特殊字段廣播到網(wǎng)絡(luò)中，未知節(jié)點只記錄接收到的第一個每跳平均距離，并將其轉(zhuǎn)發(fā)給周圍節(jié)點。這種方式可以讓網(wǎng)絡(luò)中的大部分未知節(jié)點從最近的錨節(jié)點接收每跳平均距離。在未知節(jié)點全部記錄下平均每跳距離后，根據(jù)記錄的跳數(shù)，計算每個錨節(jié)點之間的距離未知節(jié)點計算自身位置利用步驟（2）中得到的到每個錨節(jié)點的跳段距離，未知節(jié)點利用三邊測量法或極大似然估計法可以計算得出自身的位置坐標(biāo)。圖3.1是DV-Hop算法示意圖：經(jīng)過步驟（1）和步驟（2），可以計算出節(jié)點L1和L2、L3之間的距離和跳數(shù)。錨節(jié)點L2計算得到每跳平均距離為.假設(shè)未知節(jié)點A從L2獲取每跳平均距離，則它與3個錨節(jié)點之間的距離分別為，最后使用三邊測距法即可確認(rèn)節(jié)點A的位置。圖3.1DV-Hop算法測距示意圖3DV-Hop算法誤差分析在DV-Hop定位算法中，算法的步驟（1）中，由于傳感器節(jié)點隨機分布和廣播分組過程中可能存在沖突等因素，節(jié)點得到的到錨節(jié)點的最小跳數(shù)存在有一定偏差，且跳數(shù)越多，偏差越大。在錨節(jié)點采用步驟（1）估算平均每跳距離時，所利用的是除了當(dāng)前節(jié)點外所有其他的錨節(jié)點，所以得到的是全網(wǎng)絡(luò)范圍內(nèi)的平均每跳距離，不足以反映錨節(jié)點一定范圍內(nèi)的網(wǎng)絡(luò)密度分布情況，因此，采用該方法得出的平均每跳距離在密度均勻的各項同性網(wǎng)絡(luò)中沒有太大影響，但在密度不均勻的各項異性網(wǎng)絡(luò)中，就會帶來很大的計算誤差。在DV-Hop算法的步驟（3）中，未知節(jié)點利用了到所有錨節(jié)點的距離數(shù)據(jù)信息，但是根據(jù)前面的分析，未知節(jié)點到錨節(jié)點的最小跳數(shù)可能有偏差，跳數(shù)越多，偏差越大，并且步驟（2）得出的平均每跳距離也只是對實際距離的一種估算，不可避免會存在著誤差，這樣錨節(jié)點距未知節(jié)點跳距越多，錨節(jié)點和未知節(jié)點的跳段距離誤差就越大，利用較遠(yuǎn)錨節(jié)點的距離信息參與位置計算，反而可能降低了定位結(jié)果的精確度。3.2DV-Hop算法優(yōu)化由3.1對經(jīng)典的DV-Hop算法介紹可知，DV-Hop算法采用其中描述的三個步驟來對網(wǎng)絡(luò)中的節(jié)點進行定位，該方法對硬件設(shè)備要求不高，實現(xiàn)也簡單。其缺點是利用跳段距離來代替直線距離，存在一定的誤差：在步驟（2）估算平均跳距時，由于估計過程中存在誤差，在利用數(shù)學(xué)方法計算未知節(jié)點坐標(biāo)時，將含誤差的數(shù)據(jù)直接使用，因此定位準(zhǔn)確度會得不到保證。根據(jù)上面的分析，本文對DV-Hop算法的一種優(yōu)化算法做了研究，優(yōu)化后的算法計算過程在大體上仍與原DV-Hop算法大致相同，下面只對改進之處進行說明。在DV-Hop算法的步驟（1）中，錨節(jié)點向周圍節(jié)點廣播自身信息的分組時，該分組加上生存期字段n，其他節(jié)點在轉(zhuǎn)發(fā)該廣播包時，首先檢測包含生存期數(shù)據(jù)字段，如果n大于1，則將n=n-1，之后轉(zhuǎn)發(fā)廣播包,以保證該分組僅在n跳范圍內(nèi)廣播。這樣每個節(jié)點僅收到n跳范圍內(nèi)信標(biāo)節(jié)點信息，降低了原DV-Hop算法高通信開銷、高分組沖突概率等問題。圖3.2優(yōu)化算法步驟一在DV-Hop算法的步驟（2）中，利用步驟一中的式估算平均每跳實際距離時，錨節(jié)點j取自該節(jié)點n跳范圍內(nèi)跳數(shù)最少的的m個錨節(jié)點。這樣處理保證估算的平均每跳實際距離更加符合該節(jié)點附近的節(jié)點分布情況，提高了距離估計精確度，并使該方法適用于各向異性網(wǎng)絡(luò)。最后，在未知節(jié)點利用最小二乘法計算自身坐標(biāo)時，由于錨節(jié)點距離該未知節(jié)點跳段越近，未知節(jié)點和錨節(jié)點間的距離估計就越精確（概率意義上），所以這里只選跳段距離最近的I個節(jié)點進行最大似然估計法運算。這樣，既能提高算法的定位精確度，又可以降低節(jié)點的計算開銷。參數(shù)m、n、I的取值要綜合考慮錨節(jié)點比例、網(wǎng)絡(luò)的連通度、傳感器節(jié)點分布等因素。一般情況下，n要保證絕大多數(shù)未知節(jié)點一個節(jié)點能收到3個以上的錨節(jié)點分組，而m、I取4~6即可取得相對高的精確度。3.2本章小結(jié)本章先是介紹了經(jīng)典的DV-Hop算法原理，接著研究了一種DV-Hop算法的優(yōu)化算法，并介紹了優(yōu)化算法的優(yōu)化思路

第四章仿真實驗與分析4.1仿真環(huán)境和參數(shù)為了比較幾種基本算法的優(yōu)缺點，以及為了驗證改進后的DV-Hop算法的性能，在MatlabR2019b平臺上進行了仿真實驗4.2基于非測距的三種經(jīng)典定位算法4.2.1質(zhì)心定位算法觀測站被隨機分布在100m×100m的正方形區(qū)域內(nèi)，假定它們的探測距離為50m,即在以觀測站為中心的、半徑為100m的范圍內(nèi)都能會被目標(biāo)探測到，場地上部署N=6個觀測站，一個目標(biāo)隨機出現(xiàn)在檢測場地內(nèi)，被其中的幾個觀測站探測到，并計算估計位置。當(dāng)只有一個觀測站探測到目標(biāo)時：當(dāng)三個觀測站探測到目標(biāo)時：當(dāng)6個觀測站全部能探測到目標(biāo)時：當(dāng)能觀測到目標(biāo)的觀測站數(shù)量為1、3、6時，估計位置和實際位置的誤差距離分別為41.5265m、31.83m、17.3004m,由此可見，使用質(zhì)心定位算法時，隨著能觀測到目標(biāo)的觀測站數(shù)量的增加，對目標(biāo)的定位精確度是逐步上升的。即質(zhì)心定位算法的定位誤差與觀測站的位置及部署密度關(guān)系密切。4.2.2加權(quán)質(zhì)心定位算法觀測站被隨機分布在100m×100m的正方形區(qū)域內(nèi)，假定它們的探測距離為50m,即在以觀測站為中心的、半徑為100m的范圍內(nèi)都能會被目標(biāo)探測到，并且觀測站能夠探測到目標(biāo)距離觀測站的聲音信號強弱，觀測站部署數(shù)量為6。一個目標(biāo)隨機出現(xiàn)在檢測場地內(nèi)，被其中的幾個觀測站探測到，并計算估計位置。當(dāng)探測到目標(biāo)的觀測站數(shù)量為1時當(dāng)探測到目標(biāo)的觀測站數(shù)量為3時當(dāng)全部觀測站都能探測到目標(biāo)時當(dāng)能探測到目標(biāo)節(jié)點的的觀測站數(shù)量分別為1、3、6時，定位誤差分別為14.8732m，9.267m,5.3037m,即加權(quán)質(zhì)心定位算法還是滿足定位誤差與觀測站位置和部署密度關(guān)系密切的性質(zhì)，但在相同的能探測到目標(biāo)的觀測站數(shù)目條件下，加權(quán)質(zhì)心定位算法能大幅度降低定位誤差。實現(xiàn)結(jié)果證明，權(quán)值的引入對于質(zhì)心定位算法來說，能夠有效地降低定位誤差。4.2.3網(wǎng)格定位算法使用網(wǎng)格定位算法進行MATLAB算法仿真時，運行三次得到的結(jié)果分別為6.3349m、3.0264m、5.9012m,平均誤差距離為5.0875m，從結(jié)果得出的定位精確度來看，網(wǎng)格定位精確度相比前兩種算法得到的精確度更高，但網(wǎng)格定位算法需要部署大量的觀測站節(jié)點，所以他比較適合大量部署的檢測環(huán)境，如無線傳感器網(wǎng)絡(luò)。4.3DV-Hop算法在100m×100m的正方形區(qū)域的監(jiān)測區(qū)域內(nèi)，初始分布100個網(wǎng)絡(luò)節(jié)點以及40個信標(biāo)節(jié)點，節(jié)點的通信距離R定為40m.通過DV-Hop算法計算每個未知節(jié)點的誤差。之后改變信標(biāo)節(jié)點比例或者節(jié)點的通信半徑，分別得出算法的平均定位誤差和信標(biāo)節(jié)點比例以及節(jié)點通信距離的關(guān)系。由以上仿真圖可知，DV-Hop算法的定位誤差在總體上會受到信標(biāo)節(jié)點比例以及節(jié)點的通信半徑的影響：信標(biāo)節(jié)點比例和節(jié)點通信半徑的提高均會在一定程度上提升算法的定位精確度。4.3優(yōu)化后的DV-Hop算法不改變DV-Hop算法的運行條件，只改變信標(biāo)節(jié)點比例或者節(jié)點通信距離，將DV-Hop算法及其改進算法進行比較分析，得出兩者在相同條件下定位誤差與信標(biāo)節(jié)點比例以及節(jié)點通信半徑的關(guān)系圖。由以上仿真圖可知，DV-Hop優(yōu)化算法與原來算法相比，在同一運行條件下，能夠明顯的降低原來算法的定位誤差。第五章總結(jié)與展望5.1工作總結(jié)本文圍繞基于非測距的物聯(lián)網(wǎng)