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

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

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

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