wsn中應(yīng)用層非測(cè)距定位技術(shù)研究

...............................................................................................................................I 第一章緒 研究背景及意 國(guó)內(nèi)外研究現(xiàn) 本文研究工 第二章WSN概 定位基本原 性能評(píng)價(jià)標(biāo) 定位算法分 本章小 第三章基于非測(cè)距的定位算法研究與分 質(zhì)心算 APIT算 Amorphous算 算法仿真與對(duì)比分 本章小 第四章改進(jìn)的DV-HOP算 本章小 第五章仿真實(shí)驗(yàn)及性能分 算法仿真及實(shí)驗(yàn)結(jié) 算法性能評(píng) 本章小 第六章總結(jié)與展 總 展 致 參考文 第一研究背景及意WSN(WirelessSensorNetworkWSN)中無(wú)線通信技術(shù)、計(jì)算技術(shù)、微電子技業(yè)、生態(tài)、軍事、環(huán)境、民防、健康和其它商業(yè)領(lǐng)域[5][6]的大規(guī)模應(yīng)用。WSN是將大個(gè)自組織網(wǎng)絡(luò)系統(tǒng)，傳感器節(jié)點(diǎn)協(xié)同的感知、和處理目標(biāo)對(duì)象的信息，并在網(wǎng)絡(luò)中處理并發(fā)布到的數(shù)據(jù)，發(fā)送給觀察者，以實(shí)現(xiàn)對(duì)實(shí)驗(yàn)區(qū)域的監(jiān)測(cè)，為觀察者的決策提供數(shù)據(jù)支持[1][2]，這些數(shù)據(jù)包括溫度、聲音、濕度、電磁感應(yīng)、波、在傳感器所的數(shù)據(jù)中位置信息是不可缺少的部分，沒(méi)有位置信息的監(jiān)測(cè)消息通常毫無(wú)意義。確定事件發(fā)生的位置或數(shù)據(jù)的節(jié)點(diǎn)位置是WSN最基本的功能之發(fā)生的位置，例如環(huán)境檢測(cè)中需要知道的環(huán)境信息所對(duì)應(yīng)的具體區(qū)域位置；對(duì)于國(guó)內(nèi)外研究現(xiàn)10年來(lái)，WSN定位問(wèn)題研究的進(jìn)展十分可喜，取得了豐富的研究成果。特別WSN點(diǎn)定位的定位問(wèn)題。在基于測(cè)距的定位算法中，學(xué)者們提出了基于RSSI的定位算法、基于TOA的定位算法、基于TDOA的定位算法和基于AOA的定位算法，這不適用于節(jié)點(diǎn)體積小、低功耗的WSN應(yīng)用中。然而基于非測(cè)距的定位算法雖然定位設(shè)備，容易實(shí)現(xiàn)，該類算法逐漸成為WSN研究中的熱點(diǎn)問(wèn)題。質(zhì)心算法是南加州大學(xué)的學(xué)者NirupamaBlusu基于網(wǎng)絡(luò)連通性的經(jīng)典3.1節(jié)。由于該算法僅可以實(shí)現(xiàn)粗略的定位5】中提出了凸規(guī)劃算法，將節(jié)點(diǎn)間的通信連接視為節(jié)點(diǎn)位置的幾何約束，把整個(gè)網(wǎng)絡(luò)模型一個(gè)凸集，從而將節(jié)點(diǎn)定位轉(zhuǎn)化為凸約束優(yōu)化問(wèn)題，然后使用半定規(guī)劃否則節(jié)點(diǎn)的位置估算會(huì)想網(wǎng)絡(luò)中心偏移；文獻(xiàn)【6】提出一種基于弧心的節(jié)點(diǎn)定計(jì)位置；文獻(xiàn)【7】通過(guò)對(duì)無(wú)線電路徑損耗模型的分析，提出一種質(zhì)心定位算法，提出信標(biāo)節(jié)點(diǎn)的概念，節(jié)點(diǎn)到信號(hào)源的距離越近，越大。影據(jù)信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的不同確定因子，以此來(lái)提高定位精度；文獻(xiàn)【李的基礎(chǔ)上，提出了一種基于錨圓交點(diǎn)質(zhì)心的定位算法，該算法通過(guò)因子來(lái)體誤。針對(duì)這些問(wèn)題，文獻(xiàn)【】提出了一種基于三角形重心掃描的無(wú)線傳感器網(wǎng)絡(luò)自定位算法，與網(wǎng)格掃描算法不同的是，該算法不用區(qū)域交集的最大區(qū)域的質(zhì)心一種基于中垂線分割的改進(jìn)APITAPIT算法中用于定位APIT算法定位的三角形分割為4到6未知節(jié)點(diǎn)在哪個(gè)小區(qū)域中。不適用APIT算法中的三角形求區(qū)域，而是使用每個(gè)用于定位的三角形所對(duì)應(yīng)的小區(qū)域求區(qū)域，進(jìn)而求出區(qū)域的質(zhì)心，完成定位疏節(jié)點(diǎn)下APIT算法，該算法在原有算法的基礎(chǔ)上，設(shè)置一個(gè)計(jì)數(shù)器比較判內(nèi)DV-HOP文獻(xiàn)【王馭風(fēng)4】算法是路大學(xué)的DragosNiculescu等人利用距離矢量路由的概念A(yù)PS文獻(xiàn)【王馭風(fēng)3】系列算法之一，是典型的基于非測(cè)距定位算法，并在之后的研究中被廣泛的利用和改進(jìn)。文獻(xiàn)【王馭風(fēng)】基于DV-HOP精度并且適用于節(jié)點(diǎn)稀疏的WSN；文獻(xiàn)【王馭風(fēng)4】提出了一種基于測(cè)距的Malguki文獻(xiàn)【林金朝7】中，定為節(jié)點(diǎn)對(duì)接收到的多個(gè)信標(biāo)節(jié)點(diǎn)的平均每跳距離信息進(jìn)行算術(shù)平均處理，修正hop-size，從而提高了節(jié)點(diǎn)的定位精度；文獻(xiàn)【林金朝】從三個(gè)方DV-HOP算法進(jìn)行了改進(jìn)，采用最小二乘法準(zhǔn)則校正了信標(biāo)節(jié)點(diǎn)間的平均每跳距真結(jié)果表算法的定位精度和精度穩(wěn)定性有明顯改善，是一種可行的改進(jìn)方案；文獻(xiàn)【才】提出了一種基于梯度化鄰居節(jié)點(diǎn)信息的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)距離測(cè)量算法將分辨率從節(jié)點(diǎn)有效通信半徑提高到節(jié)點(diǎn)間距，仿真實(shí)驗(yàn)表明該算法保留了DV-HOP該領(lǐng)域提出越來(lái)越多需要解決的問(wèn)題。認(rèn)為除了對(duì)定位算法本身的研究外，可能技術(shù)和仿真系統(tǒng)來(lái)模擬定位算法的實(shí)現(xiàn)；（3）由成千上萬(wàn)節(jié)點(diǎn)組成的大規(guī)?；虺笠?guī)模網(wǎng)絡(luò)自身定位問(wèn)題的低成本（時(shí)空、功耗、價(jià)格）和高精度的實(shí)現(xiàn)；（4）移動(dòng)網(wǎng)WSN應(yīng)用層非測(cè)距定位算法這一方向首先，針對(duì)WSN介紹了定位算法的分類、性能評(píng)價(jià)標(biāo)準(zhǔn)以及定位的基DV-HOPDV-HOP算法，入的分析及對(duì)比，證明改進(jìn)的算法可以提高節(jié)點(diǎn)定位精度3%。并從信標(biāo)節(jié)點(diǎn)比例、WSN應(yīng)用層非測(cè)距定位算進(jìn)行改進(jìn)，給出改進(jìn)的DV-HOP算法的分析過(guò)程、算法思想以及算法流程。第二章WSN概在WSN研究中，是應(yīng)用層的之一，并且隨著研究的深入開(kāi)展逐漸成為了熱點(diǎn)問(wèn)題。本章對(duì)WSN進(jìn)行概述，首先介紹了現(xiàn)有定位算法的WSN應(yīng)用需求，有較好的可擴(kuò)展性，并且介紹了定位算法的性能評(píng)價(jià)標(biāo)Amorphous跳斷和三邊測(cè)量敘述研究路線WSN定位算法定位基本W(wǎng)SN節(jié)點(diǎn)就是傳感器節(jié)點(diǎn)通過(guò)與少數(shù)已知位置的節(jié)點(diǎn)進(jìn)行有效地通信，信標(biāo)節(jié)點(diǎn)占據(jù)的比例較少，它們通常是提前部署或者運(yùn)用GPS等來(lái)獲取自身的位SSM2.1WSNMMS類型節(jié)點(diǎn)定位算法硬件條件不同，并且算法性能也有差異。通常將WSN的定位算法分為以下幾類：基于測(cè)距的定位算法常用的測(cè)距技術(shù)有I1819202122]2324]，A2526][272829A2829]。測(cè)距技術(shù)具有一定的局限性，例如需要精確時(shí)間同步、需要額外硬件支持、易受外界影響等。雖然可以使用循環(huán)定位30]、多次測(cè)量31]等方法來(lái)彌補(bǔ)測(cè)距技術(shù)的局限、減小誤差，但是它并不適用于一些有低功耗、低成本要求的應(yīng)用領(lǐng)域。質(zhì)心算法[32]、APIT算法[33]、DV-HOP算法[19][20]、Amorphous算法[34]4種基于非測(cè)距的定位算法，在定位精度小于40%時(shí)可滿足大多數(shù)應(yīng)用需求。坐標(biāo)系依次轉(zhuǎn)換合并，從而產(chǎn)生整體相對(duì)坐標(biāo)系統(tǒng)，例如AFL算法[35]和ABC算法[36]度統(tǒng)籌規(guī)劃，幾乎不限制量和計(jì)算量，位置估算相對(duì)精確。但是該類算法網(wǎng)絡(luò)延遲較大、全網(wǎng)節(jié)點(diǎn)能量消耗不均并且具有較高的通信成本。例如凸規(guī)劃[38、強(qiáng)的靈活性，但犧牲了緊密耦合的高精確性，并且易受，帶來(lái)多RadioCamera中的信號(hào)模式匹配專利技術(shù)。性能評(píng)價(jià)定位精度是中最重要的評(píng)價(jià)標(biāo)準(zhǔn)，顯示了節(jié)點(diǎn)的計(jì)算位置與物理位置的點(diǎn)定位精度是30%，即定位誤差相當(dāng)于傳感器節(jié)點(diǎn)通信半徑的30%。通常定位精度在40%以下的算法均可滿足WSN的應(yīng)用需求。么全網(wǎng)的工作代價(jià)就會(huì)越高，并且會(huì)導(dǎo)致通信，發(fā)生網(wǎng)絡(luò)阻塞。因此，合理的設(shè)配置、定位所需時(shí)間等；空間代價(jià)即網(wǎng)絡(luò)的基礎(chǔ)設(shè)施、節(jié)點(diǎn)硬件尺寸及數(shù)量等；代在實(shí)際應(yīng)用場(chǎng)景中部署定位算法要求其在硬件兩個(gè)方面都定位算法的功耗由傳感器節(jié)點(diǎn)的通信、、計(jì)算等操作引起的，由于節(jié)點(diǎn)體積WSN時(shí)，盡可能降低功耗是重要目標(biāo)之價(jià)的重要標(biāo)準(zhǔn)。位置計(jì)算(xb,yb)、(xc,yc)，以及它們到未知節(jié)點(diǎn)D的距離分別為da,db,dc，假設(shè)節(jié)點(diǎn)D的坐標(biāo)√(???????)2+(???????)2={√(???????)2+(???????)2=√(???????)2+(???????)2= 2(?????)2(?????)?1??2???2+??2???2+??2???

[]=

[

??2?? 2(?????????)

??2???2+??2???

AADBC

三角測(cè)量法(Triangulation)原理如圖2.3所示，已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)分別（xa,ya（xb,yb（xc,yc∠BDCD的坐標(biāo)為(x,y)對(duì)于節(jié)點(diǎn)A、C和角∠ADC，如果弧段AC在?ABC內(nèi)，那么能夠惟一確定一個(gè)圓，設(shè)圓心為??1(????1????1)，半徑為??1，那么α∠A??1??=(2π2∠ADC)，并存在下列公式√(????1?????)+(????1?????)= √(????1?????)+(????1?????)= (?????????)2+(?????????)2=2??12?2??12cos分別確定相應(yīng)的圓心??2(????2,????2)、半徑??2、圓心??3(????3,????3)和半徑??3ADBCD(x,y)，O1(xo1,yo1)，O2(xo2,yo2)O3(xo3,yo3)確定D點(diǎn)坐標(biāo)。 umLikelihoodEstimation)如圖2.4所示，己知l、2、3等n個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(x1,y1)(x2,y2)(x3,y3)…(xn,yn)，它們到節(jié)點(diǎn)D的距離分別為d1,d2,d3,…,dn。假設(shè)節(jié)點(diǎn)D的坐標(biāo)為(x,y)。1n2 3{

1(??1?x)2+(??1???)2=??1?(???????)2+(???????)2=??

1??12???2?1

???)??+??2???2?

???)??=??2???111 111?????12???2?

???)??+

2???2?

???)??=

2???2(??1? 2(??1?A= 2(?????1? 2(?????1???12???2+??2???2+??2???b=

?

2

2],??= ?????12?

2+ 2?

2+ ?=首先介紹WSN定位算法的基本原理，介紹了的基本概念及基本術(shù)語(yǔ)。這8個(gè)指標(biāo)。最后對(duì)現(xiàn)有的從6個(gè)角度進(jìn)行分類，提出本文重點(diǎn)研究基于非第三 基于非測(cè)距的定位算法研究與分成本較高，會(huì)提高網(wǎng)絡(luò)部署成本。在基于非測(cè)距的定位算法點(diǎn)通過(guò)跳數(shù)和跳距質(zhì)心算法[2]WSNNirupamaBulusu3.1O為需要定位的未知節(jié)點(diǎn)，A、B、C、D、E、F、GOO在估算自身形ABCDEFG的幾何質(zhì)心。B O 3.1（周期）內(nèi)向其通信范圍內(nèi)的鄰居節(jié)點(diǎn)廣播數(shù)據(jù)包（位置、ID標(biāo)識(shí)。此時(shí)網(wǎng)絡(luò)中的KtK或者收到數(shù)據(jù)包的時(shí)間超過(guò)t，那么節(jié)點(diǎn)則停止接收這些來(lái)自不同信標(biāo)節(jié)點(diǎn)的數(shù)據(jù)，并且以之前收的質(zhì)心（即坐標(biāo)平均值）作為估算坐標(biāo)，如公式3.1所示。(??,??)=(????1+?+??????, 結(jié)結(jié)開(kāi)開(kāi)否是APIT近似三角形內(nèi)測(cè)法(ApproximatePoint-In-TriangulationTest,APIT)算法[45]的定位原在信標(biāo)節(jié)點(diǎn)中取出三個(gè)組成三角形，然后利用APIT原理判斷自身在這個(gè)三角形中與]APIT算法的定位過(guò)程中，未知節(jié)點(diǎn)首先收集信標(biāo)節(jié)點(diǎn)在全網(wǎng)絡(luò)中廣播的數(shù)據(jù)的估算坐標(biāo)。而在判斷是否在三角形內(nèi)測(cè)時(shí)，該算法使用近似三角形內(nèi)點(diǎn)測(cè)試法(ApproximatePointinTriangulationTestAPIT)，它的理論基礎(chǔ)是最佳三角形內(nèi)點(diǎn)測(cè)試AMAMCBAMCBPITM和三角形ΔABC內(nèi)，如果存在一個(gè)方向，該方向上的MA、BCM在三角形ΔABC外部。否則，M在ΔABC。而在WSN中，待定位的未知節(jié)點(diǎn)無(wú)法移動(dòng)，所以不能進(jìn)行理性的PIT測(cè)試，因此使用APIT方法。A31A31M2B4CA31M24BC信標(biāo)節(jié)點(diǎn)的信號(hào)強(qiáng)度來(lái)表示節(jié)點(diǎn)間的距離，進(jìn)而判斷遠(yuǎn)離或者接近。在圖3.5中，點(diǎn)M11AB、C。同樣，M2、3、4通信，并獲取類似結(jié)論，最后判斷是否在ΔABC內(nèi)。圖3.5中左側(cè)為在ΔABC內(nèi)側(cè)的情況，右側(cè)圍在ΔABC外側(cè)的情況。，開(kāi)開(kāi)對(duì)未知節(jié)點(diǎn)否對(duì)未知節(jié)點(diǎn)否是結(jié)算法進(jìn)行定APIT算法在網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)部署且無(wú)線信號(hào)模型不規(guī)則的網(wǎng)絡(luò)條件下性能穩(wěn)點(diǎn)比例較低的WSN中，該算法無(wú)法實(shí)現(xiàn)準(zhǔn)確的節(jié)點(diǎn)定位[47]。DV-HOP距離向量—跳斷DV-HOP(distancevector-hop)是由Niculescu,Dragos一種3且在密集分布的規(guī)則網(wǎng)絡(luò)中定位精度較高[49]格，信息的格式為(????,????,???????)，其中(????,????)代表信標(biāo)節(jié)點(diǎn)i的坐標(biāo)，???????代表距信標(biāo)節(jié)點(diǎn)i的最小跳數(shù)值，初始值為0，每轉(zhuǎn)發(fā)一次自增1。若節(jié)點(diǎn)收到一個(gè)包含距某個(gè)信標(biāo)節(jié)點(diǎn)有更小跳數(shù)值的數(shù)據(jù)包，則替代表格中的???????且自增1，否則忽略該數(shù)據(jù)

= ?????????)= ??≠??

中的坐標(biāo)，?????iji然后，信標(biāo)節(jié)點(diǎn)向全網(wǎng)洪泛廣播利用公式3.2計(jì)算出的??opSize??，未知節(jié)點(diǎn)接收HopSize和到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的估算距離????????????=????????????????× 3.3中，????????????????pi具體DV-HOP算法的定位步驟：short_path，該矩陣的大小是節(jié)點(diǎn)數(shù)量列—節(jié)點(diǎn)數(shù)節(jié)點(diǎn)的HopSize，根據(jù)公式3.3利用最小跳數(shù)值計(jì)算與信標(biāo)節(jié)點(diǎn)之間的距離。計(jì)算未知節(jié)點(diǎn)坐計(jì)算未知節(jié)點(diǎn)坐信標(biāo)節(jié)點(diǎn)跳否定位結(jié)HopSize可以估算出未知節(jié)點(diǎn)的位置。它對(duì)硬件的要求較低且Amorphous無(wú)定形的定位(Amorphous)算法與DV-HOP算法類似，主要分為三個(gè)階段代替，如公式3.4所示。

=∑??∈????????(??)???+???? 與之前數(shù)據(jù)包比接 跳數(shù)信是否開(kāi)是與之前數(shù)據(jù)包比接 跳數(shù)信是否開(kāi)是 (cos?1HopSize=r(1+ ???????∫?1 3.5中，預(yù)設(shè)

=ρπ??2(網(wǎng)絡(luò)點(diǎn)的平均鄰居節(jié)點(diǎn)數(shù)),??=??，其中N代全網(wǎng)節(jié)點(diǎn)的數(shù)量S代表所部屬網(wǎng)絡(luò)的區(qū)域面積r代表預(yù)設(shè)的網(wǎng)絡(luò)點(diǎn)的通信半徑。算法的第三階段是未知節(jié)點(diǎn)使用梯度值和HopSize計(jì)算與信標(biāo)節(jié)點(diǎn)距離，從而使Amorphous算法的性能較好。但是由于它基于經(jīng)驗(yàn)?zāi)Ｐ投ㄎ?，網(wǎng)絡(luò)擴(kuò)展性比算法仿算法、Amorphous算法進(jìn)行介紹，并深入分析了算法思想、算法流程及算法步驟。本首先，在表3-1實(shí)驗(yàn)參數(shù)條件下，對(duì)質(zhì)心算法、APIT算法、DV-HOP算法、Amorphous算法進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)過(guò)程中設(shè)置100m×100m大小的正方形平面模擬監(jiān)測(cè)區(qū)域，隨機(jī)播撒200個(gè)傳感器節(jié)點(diǎn)，將信標(biāo)節(jié)點(diǎn)比例設(shè)為0.3，即有60值(a)節(jié)點(diǎn)分布 (b)鄰居關(guān)系(c)質(zhì)心算法定位誤差 (d)APIT算法定位誤差(e)DV-HOP算法定位誤差圖 圖3.8算法仿真過(guò)程圖體鄰居關(guān)系如圖3.8(b)所示。3.8(c)3.8(d)APIT算法3.8(e)DV-HOP3.8(f)Amorphous算法定位誤05APIT0.3，DV-HOP0.301，Amorphous0.26。在該條件下，四個(gè)算法的定位誤差區(qū)別較為明顯，其中質(zhì)心算法定定位誤差最大，而在本實(shí)驗(yàn)中差較高是因?yàn)閷⑼ㄐ虐霃阶鳛槠骄刻嚯x，而本實(shí)驗(yàn)中實(shí)現(xiàn)的是經(jīng)典的改進(jìn)Amorphous算法。下面針對(duì)信標(biāo)節(jié)點(diǎn)比例、節(jié)點(diǎn)密度這兩個(gè)因素對(duì)四種基于非測(cè)距定1.法、Amorphous算法進(jìn)行仿真實(shí)驗(yàn)，分析算法定位精度及定位覆蓋率隨信標(biāo)節(jié)點(diǎn)比例實(shí)驗(yàn)參 節(jié)點(diǎn)分布區(qū) 通信半 信標(biāo)節(jié)點(diǎn)比 圖3.9為定位誤差隨信標(biāo)節(jié)點(diǎn)比例變化而變化的曲線圖，由圖可知四個(gè)算法的定0.10.55，APITDV-HOP0.35-0.43.10APIT從信標(biāo)節(jié)點(diǎn)比例為0.2開(kāi)始，算法的定位誤差變化較平穩(wěn)。直至信標(biāo)節(jié)點(diǎn)比例為0.5定位相比其他三個(gè)算法準(zhǔn)確，且變化幅度較小，保持在0.25-0.27之間。3.10為定位覆蓋率隨信標(biāo)節(jié)點(diǎn)變化而變化的曲線圖，由圖可知算法的定位覆蓋的定位覆蓋率較低0.80.98，因?yàn)檫@兩個(gè)算法對(duì)通信半徑內(nèi)信標(biāo)節(jié)點(diǎn)的依13.11為仿真實(shí)驗(yàn)過(guò)程中命令窗口的輸出結(jié)果，可以作為參照來(lái)分析圖3.9和圖3.10。3.11輸入結(jié)果圖1.法、Amorphous算法進(jìn)行仿真實(shí)驗(yàn)，分析算法定位精度及定位覆蓋率隨節(jié)點(diǎn)密度變化實(shí)驗(yàn)參數(shù)節(jié)點(diǎn)分布區(qū)域節(jié)點(diǎn)分布模型正方形隨機(jī)分布節(jié)點(diǎn)數(shù)量通信半 信標(biāo)節(jié)點(diǎn)比 4060時(shí)會(huì)遇到網(wǎng)絡(luò)不連通、無(wú)法定位的情況，因此圖中此條件下這兩個(gè)算80200時(shí)，DV-HOP0.3Amorphous0.25。而質(zhì)心算法和APIT算法在節(jié)點(diǎn)數(shù)量由40到200下降，質(zhì)心算法由0.450.35，APIT算法0.360.28。APIT算法的定位覆蓋率受節(jié)點(diǎn)密度影響最大，當(dāng)節(jié)點(diǎn)數(shù)量為40時(shí)，其定位覆蓋率只有0.62，并隨著節(jié)點(diǎn)數(shù)量的增加，可定位節(jié)點(diǎn)比例逐（0.9862000.99，是該變化過(guò)程中的最大值。同時(shí)，質(zhì)心算法的定位覆蓋率也受40時(shí)，節(jié)點(diǎn)定位覆蓋率為0.948，隨著節(jié)點(diǎn)數(shù)量的增加，0.9998（≈1其定位覆蓋率不受節(jié)點(diǎn)密度的影響，直至節(jié)點(diǎn)數(shù)量為200可一直保持為1。圖3.14為仿真實(shí)驗(yàn)過(guò)程中命令窗口的輸出結(jié)果，可以作為參照來(lái)分析圖3.12和圖3.13。對(duì)比分

3.14輸出結(jié)果圖通過(guò)對(duì)質(zhì)心算法、APIT算法、DV-HOPAmorphous算法進(jìn)行仿真實(shí)驗(yàn)3-4APIT算 良 良影響比最 影響比較量影響比較 影響比較 最大影響比較 影響比較所需信標(biāo)節(jié)點(diǎn) 適合各向同性度 集網(wǎng) 算法的定位誤差和定位覆蓋率沒(méi)有影響，整個(gè)變化過(guò)程平穩(wěn)，且實(shí)現(xiàn)簡(jiǎn)單。而APITAPIT算法相比具有較高的定位覆蓋率，并且與質(zhì)心Amorphous算法，介紹了算法的定位原理、定位流程與定位步驟。然后對(duì)以上算法進(jìn)第四DV-HOP根據(jù)上一章對(duì)WSN中基于非測(cè)距定位算法的深入研究和對(duì)比分析，本章選擇DV-HOP算法進(jìn)行算法舉例與誤差分析，并且從基于節(jié)點(diǎn)分布規(guī)律改進(jìn)該算法，給出DV- 算法舉ADV-HOP4.1每跳距離為（40+75）/（2+5）=16.42。假設(shè)A從L2獲得平均每跳距離，則節(jié)點(diǎn)A與A誤差分

DV-HOP算法進(jìn)行距離估算方法的距離，分析了基于跳數(shù)的定位機(jī)面改進(jìn)DV-HOP算法?；诠?jié)點(diǎn)分布規(guī)律改進(jìn)DV-HOP實(shí)驗(yàn)分本章首先用仿真實(shí)驗(yàn)驗(yàn)證原始DV-HOP算法，然后分析實(shí)驗(yàn)結(jié)果及其分布規(guī)律。具體實(shí)驗(yàn)參數(shù)如表4-1所示。4-1實(shí)驗(yàn)參 區(qū)域形 正方區(qū)域面 節(jié)點(diǎn)數(shù) 信標(biāo)節(jié)點(diǎn)比 4.3圖4.2為DV-HOP算法仿真實(shí)驗(yàn)中的節(jié)點(diǎn)分布圖，其中星號(hào)代表信標(biāo)節(jié)點(diǎn)，空心4-3為該實(shí)驗(yàn)的定位誤差圖，其中空心圓表示這些節(jié)點(diǎn)的估計(jì)4.24.3DV-HOP算法中未知節(jié)點(diǎn)的誤差分布規(guī)律，誤差相對(duì)較小的節(jié)點(diǎn)坐標(biāo)的是正方形中間區(qū)域的坐標(biāo)。通過(guò)多輪實(shí)驗(yàn)驗(yàn)證，此規(guī)律DV-HOP算法估算的估計(jì)坐標(biāo)之間的差別.具4.14.2可以計(jì)算出網(wǎng)絡(luò)中未4.1LE4.2LEa4.44.5LE

LEa=

點(diǎn)的估算坐標(biāo)，ComR代表網(wǎng)絡(luò)的通信半徑。4.2中，n代表網(wǎng)絡(luò)中未知節(jié)點(diǎn)數(shù)量（Xrn,Yrn代表網(wǎng)n個(gè)未知節(jié)點(diǎn)的4.4位誤差均值的未知節(jié)點(diǎn)分布情況如圖4.5所示。觀察圖4.4和圖4.5可以發(fā)現(xiàn)，定位誤本節(jié)根據(jù)4.1節(jié)中的誤差來(lái)源分析出現(xiàn)上述分布情況的原因，可知在DV-HOP算節(jié)點(diǎn)共享平均每跳距離，未知節(jié)點(diǎn)通過(guò)附近的信標(biāo)節(jié)點(diǎn)來(lái)確定自身的平均每跳距離。依據(jù)信標(biāo)節(jié)點(diǎn)的位置分布情況判斷產(chǎn)生節(jié)點(diǎn)誤差分布與部署位置相關(guān)的原因是由算與信標(biāo)節(jié)點(diǎn)的距離，計(jì)算方式是平均每跳距離乘以跳數(shù)。然而，分布在區(qū)域邊緣部積的跳數(shù)越多，距離中估算的程度就越大，誤差累積也相對(duì)增多，從而造成了邊緣節(jié)∑beacons_??HSLbeacons=

∑beacons_??

∑nodes_??HSLnodes=

beacons_n)代表beacons_n個(gè)信標(biāo)節(jié)點(diǎn)的坐標(biāo)，Hop(beacons_n)代表當(dāng)前信標(biāo)節(jié)點(diǎn)4.4中，HSLnodes代表全網(wǎng)節(jié)點(diǎn)平均每跳距離，（Xcurrent,Ycurrent）代表當(dāng)前nodes_n個(gè)節(jié)點(diǎn)的坐標(biāo)，Hop(nodes_n)nodes_n個(gè)節(jié)點(diǎn)的跳數(shù)，HSLnodes的結(jié)果代表長(zhǎng)度為nodes_n的數(shù)組。使用公式4.4計(jì)算出的HSLnodes得出全網(wǎng)所有節(jié)點(diǎn)平均每跳距離的均值，如公4.5∑??????????_nHSaverage=

4.4中，HSaverage代表全網(wǎng)節(jié)點(diǎn)平均每跳距離均值，nodes_nHSLnodes(nodes_n)代表第nodes_n個(gè)節(jié)點(diǎn)的平均每跳距離信標(biāo)節(jié)點(diǎn)為一類，超出此范圍的信標(biāo)節(jié)點(diǎn)為另一類，具體如圖4.6和圖4.7所示。是平均每跳距離在均值1m范圍內(nèi)波動(dòng)改進(jìn)方4.7中信標(biāo)節(jié)點(diǎn)的坐標(biāo)，獲取所分布圓環(huán)區(qū)域的范圍，強(qiáng)制圓環(huán)區(qū)域DV-HOP算法步驟二（計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳段距離）這一步中，近的圓環(huán)區(qū)域內(nèi)的信標(biāo)節(jié)點(diǎn)并獲取平均每跳距離，修正自身估算出的累積較大的Hopsize，獲得更準(zhǔn)確地Hopsize，從而使全網(wǎng)平均每條距離均值接近公式4.5計(jì)算出HSLaverage。 是否接受過(guò)該 是否接受過(guò)該否是否否DV-HOP3個(gè)方面對(duì)算法的誤DV-HOP算法的仿真實(shí)驗(yàn)結(jié)果—定位誤差圖分析算法第五章仿真實(shí)驗(yàn)及性能分仿真實(shí)驗(yàn)中WSN網(wǎng)絡(luò)的參數(shù)設(shè)置如表4-1所示。正方形區(qū)域：100m×100m，通信區(qū)域下限，DmaxODmin—Dmax4.7所示的信標(biāo)節(jié)點(diǎn)分布的圓環(huán)區(qū)域。判斷Distance(i)值，若在Dmin—Dmax范圍內(nèi)，則該信標(biāo)節(jié)點(diǎn)向未知節(jié)點(diǎn)廣播公式3.2所計(jì)算的最初的HopSize值；若不在Dmin—Dmax范圍內(nèi)，則尋找距離該信標(biāo)節(jié)點(diǎn)最近的圓環(huán)區(qū)域內(nèi)的信標(biāo)節(jié)點(diǎn)，其HopSize，從而修正自身的HopSize，即代替由公式3.2計(jì)算的HopSize。????stance(i)=2√(???????o)2+(Yi? 5.1中，Distance(i)i個(gè)信標(biāo)節(jié)點(diǎn)到點(diǎn)O的距離，(Xi,Yi)i個(gè)信標(biāo)節(jié)點(diǎn)的真實(shí)坐標(biāo)，(Xo,Yo)為正方區(qū)域中心店O的坐標(biāo)。44，Dmax50FORiFROM1TObeacons_countIFdistance(i)>Dmin且distance(i)<DmaxTHENFORiFROM1TObeacons_countIF!(distance(i)>Dmin且distance(i)<Dmax)THEN正HopSize和三邊測(cè)量法估算自身坐標(biāo)。仿真實(shí)驗(yàn)結(jié)果如圖5.1所示。5.1DV-HOP高。本章對(duì)改進(jìn)算法及原始算法進(jìn)行了100輪實(shí)驗(yàn)，每輪實(shí)驗(yàn)兩個(gè)算法的實(shí)驗(yàn)參數(shù)及節(jié)點(diǎn)分布情況均相等，得出改進(jìn)算法的定位精度平均可以提高0.3。當(dāng)WSN網(wǎng)絡(luò)環(huán)境較個(gè)方面對(duì)改進(jìn)DV-HOP算法的定位性能進(jìn)行評(píng)估。DV-HOPDV-HOP率均為1，因此本節(jié)只比較兩個(gè)算法的定位誤差變化情況。信標(biāo)節(jié)點(diǎn)20030m，DV-HOP算法與原始DV-HOP算法的平均定位進(jìn)行比較。如圖5.2，原始算法的定位誤差為0.32，而改進(jìn)算法的定位誤差為0.316，可以看出當(dāng)改進(jìn)算法的平均定位誤差穩(wěn)步下降，而原始算法的該數(shù)值一直保持較為平穩(wěn)，在0.3上下小幅度波動(dòng)，在信標(biāo)節(jié)點(diǎn)比例為50%時(shí)，改進(jìn)算法的定位誤差下降到0.27，原始算0.29240%時(shí)，兩個(gè)算法的平均定位誤差最大（0.03，說(shuō)明該條件下改進(jìn)DV-HOP算法能夠達(dá)到較DV-HOP算法性能一直保持優(yōu)于原始DV-HOP算法。節(jié)點(diǎn)密

100m×100m的正方形區(qū)域中，信標(biāo)節(jié)點(diǎn)比例設(shè)置0.330m，本節(jié)實(shí)驗(yàn)用節(jié)點(diǎn)數(shù)量來(lái)表示節(jié)點(diǎn)密度，改變節(jié)點(diǎn)數(shù)量分別為：、、、、、、、180、200。目前在節(jié)點(diǎn)數(shù)量較少的稀疏5.34060100輪實(shí)驗(yàn)中會(huì)出現(xiàn)網(wǎng)絡(luò)無(wú)法連通的情況，若加大通信半徑會(huì)改善這一問(wèn)題，但是節(jié)點(diǎn)的信號(hào)會(huì)增加同時(shí)能耗0.27較比原始算法的0.29定位精度高出002原始DV-HOP算法。通信半

于原始DV-HOP算法。當(dāng)通信半徑為20時(shí)，網(wǎng)絡(luò)點(diǎn)間的連通情況較不理想，因0.340.33。隨著通信半徑的增加，兩個(gè)算法的平均定位誤差均平穩(wěn)下降。在變化過(guò)程中，當(dāng)通信半徑為區(qū)（50m0.250.23，均為整體變DV-HOP算法性能一直保持優(yōu)于原始DV-HOP算法。5.3.4通信

WSN中，無(wú)線電的不規(guī)則是一種不可忽視的常見(jiàn)現(xiàn)象[51]。在無(wú)線電范圍內(nèi)的不規(guī)則性和在不同方向上數(shù)據(jù)包丟失的變化，是在上層協(xié)議棧中不對(duì)稱連接的無(wú)線電的方向上每度的最大無(wú)線電范圍的變化。當(dāng)為零時(shí)，不存在范圍變化，無(wú)線電模型為一個(gè)完美的圓形。為了更好的不同無(wú)線電通信模型對(duì)100m×100m20030m、（規(guī)則模型、LAModel（對(duì)數(shù)衰減模型、 Model、RIMModel四個(gè)模型下對(duì)原始DV-HOP算法和改進(jìn)DV-HOP算法進(jìn)行仿真實(shí)驗(yàn)。這四個(gè)模型中，RegularModel 仍假設(shè)節(jié)點(diǎn)通信范圍是一個(gè)完美的原型；模型考慮到節(jié)點(diǎn)的通信范圍不是一個(gè)完 參數(shù)為0.015， 模型是一個(gè)通信范圍，如果在該范入RIM模型[52]進(jìn)行實(shí)驗(yàn)，該模型是通過(guò)MICA2平臺(tái)獲得的經(jīng)驗(yàn)數(shù)據(jù)建立的一個(gè)無(wú) 參數(shù)設(shè)置為0.01。由圖5.5可知，所考慮的網(wǎng)絡(luò)環(huán)境越復(fù)雜，兩個(gè)算法的定位精度越低。具體如下：當(dāng)網(wǎng)絡(luò)通信使用Regular模型時(shí)，改進(jìn)DV-HOP算法的定同時(shí)，當(dāng)通信模型設(shè)置為L(zhǎng)A時(shí)，兩個(gè)算法的定位誤差均有提高，并且二者之差也相型DV-HOPDV-HOP算法有更好的提高；同時(shí)，當(dāng)且其數(shù)量會(huì)隨著距離的變化而產(chǎn)生變化，所以研究無(wú)線電的不規(guī)則性對(duì)WSN定位算法的影響很有必要。在RIM模型的幫助下，本文通過(guò)仿真研究無(wú)線電的不規(guī)則性對(duì) 0.1，對(duì)原始DV-HOP算法和改進(jìn)DV-HOP算法繼續(xù)進(jìn)行仿真實(shí)驗(yàn)。圖5.6RIM中參數(shù)對(duì)算法定位誤差的影如圖5.6中，隨著的增大，定位誤差也隨之增大。因?yàn)楫?dāng)增大時(shí)，標(biāo)節(jié)點(diǎn)，從而增加了跳數(shù)。當(dāng)為0時(shí)，原始算法的定位誤差0.30，而改進(jìn)算法的定位誤差0.27，保持優(yōu)于原始0.03。隨著值的增大，兩個(gè)算法的定位誤差保持上升趨勢(shì)，尤其當(dāng)值大于0.02開(kāi)始，上升曲線斜率明顯增大，但始終保持相等的定位誤差之差（≈0.035。因此，隨著值的變化，改進(jìn)DV-HOP算法的定位性能仍然優(yōu)于原始DV-HOP算法。DV-HOPDV-HOP0.03。然后對(duì)改進(jìn)算法從4個(gè)方面進(jìn)行算法的定位性能評(píng)估，并給出與原始算法的對(duì)比結(jié)果圖，表明改進(jìn)DV-HOP算法從4個(gè)方面均可提高節(jié)點(diǎn)定位精度，具有較好的穩(wěn)定性。第六結(jié)與展總本文首先介紹了WSN的研究背景及意義并且強(qiáng)調(diào)了在WSN的研究中起著至關(guān)重要的作用，然后給出了WSN國(guó)內(nèi)外研究現(xiàn)狀，著重介紹作為關(guān)鍵技術(shù)之一研究現(xiàn)狀，并且給出了當(dāng)前WSN的熱點(diǎn)研究方向。第二，對(duì)WSN進(jìn)行概述，介紹的基本原理、性能評(píng)價(jià)標(biāo)準(zhǔn)，算法、DV-HOP算法、Amorphous算法。介紹了以上算法的定位原理、定位過(guò)程及具細(xì)分析。提出本文重點(diǎn)研究DV-HOP算法，并給出改進(jìn)方案。DV-HOPDV-HOP原始算法定位精度3%。為進(jìn)一步分析改進(jìn)算法性能，本文以信標(biāo)節(jié)點(diǎn)比例、節(jié)點(diǎn)密展DV-HOP算法提出了改進(jìn)策略，并且在仿真平臺(tái)上實(shí)驗(yàn)且進(jìn)行了性能測(cè)試，仿且受到噪聲及無(wú)線電等因素的干擾，網(wǎng)絡(luò)通信模型的值無(wú)法確定，因此，在把改進(jìn)算法應(yīng)用到實(shí)際場(chǎng)景時(shí)要考慮到信號(hào)衰減、參數(shù)、通信范圍是否可達(dá)等因素，致首先衷心感謝導(dǎo)師教授，本是在導(dǎo)師悉心指導(dǎo)下完成的，研感謝物聯(lián)網(wǎng)應(yīng)用技術(shù)與云計(jì)算的馮欣老師在我就讀于長(zhǎng)春理工大學(xué)的本科和期間對(duì)指引和教導(dǎo)，他求實(shí)的工作作風(fēng)和誠(chéng)實(shí)寬厚的處世風(fēng)范都對(duì)我產(chǎn)生一起在學(xué)習(xí)的孫蘇鵬同學(xué)給予幫助和鼓勵(lì)。 參考文任豐原,黃海寧,林闖.WSN[J].學(xué)報(bào):孫利民,,,朱紅松:

AkyildizIF,SuWL,SankarasubramaniamY,etal.Asurveyonsensornetworks[J].IEEECommunications.August,2002,40(8);102-114ChongCY,KumarSP.SensorNetworks:Evolution,Opportunities,andChaIIenges[J],ProceedingsoftheIEEE,August2003,91(8):1247-1256,余先濤 .WSN在車廂環(huán)境測(cè)控中的應(yīng)用[J].電氣傳動(dòng)自動(dòng)化,2006,28(2):50-,.WSN?？把訹J].學(xué)報(bào),2007,18(5):1077-LiRX,FangZY,HaoBC,etal.ResearchonIndoorWirelessLocalizationSystemforRadioactiveSourcesBasedonZigBee[J].ComputingControlandIndustrialEngineering(CCIE).2010,2:359-362周賢偉,,覃伯平.WSN密鑰管理方案的研究[J].計(jì)算機(jī)應(yīng)用研究,2007,24(1):144-Hairong,SitharamaQS,Iyengear,KrishnenduChakrabarty.Distributedsensornetworks-areviewofrecentresearch[J].JournaloftheFranklinInstitute338.2001:655-688,郭鐵成.IBM“智慧地球”我國(guó)的思考[N].學(xué)習(xí),2012-10-,.WSN[M].:電子工業(yè),許琦敏.我國(guó)無(wú)線傳感技術(shù)完整價(jià)值鏈己初步完成[N].中華建筑報(bào),2006-11-WSN技術(shù)在電力系統(tǒng)中的應(yīng)用[N].國(guó)家電網(wǎng)報(bào),2008-03-中國(guó)信息領(lǐng)域研究組.中國(guó)2050年信息科技發(fā)展路線圖[M].:科學(xué)SeapahnMeguerdichian,SesaSlijepcevic,VahagKimyan.MiodragPotkomak.LocalizedAlgorithmsinWirelessAd-hocNetworks:LocationDiscoveryAndSensorExposure.In:Proceeingsofthe2001ACMInternationalSymposiumonMobileAdHocNetworking&Computing.LongBeach,USAACMPress,PriyanthaNB,MiuAKL,BaladrishnanH,lerS.Thecricketcompassforcontext-awaremobileapplications.In:Proc.Ofthe7thAnnualInt’lConf.onMobileComputingandNetworking.Rome:ACMPress,2001.1,14.Compass.pdfTianHe,ChengduHuang,BrianM.Blum,JohnA.Svic,TarekAbdelzaherRange-FreeLocalizationSchemesinLargeScaleSensorNetworks.InProceedingsofthe9thannualinternationalconferenceonMobilecomputingandnetworking( ),SanDiego,Califomia,USA:ACMPress,2(1039,81-95) NicolescuD,NathB.Ad-hocpositioningsystems(APS).In:Proc.Ofthe2001IEEEGlobalmunicationsConf.Vol.5,SanAntonio:IEEECommunicationsSociety,2001.2926.2931./~dnicules/re-sear NiculescuD,NathB.DVbasedpositioninginadhocnetworks.Journalof municationSystems,BulusuN,EstrinD,HeidemannJ.Tradeoffsinlocationsupportsystems:Thecaseforquality-expressivelocationmodelsforapplications.In:Proc.Ofthe p2001WorkshoponLocationModelingforApplications.Atlanta,2001.7.12L.Girod.V.Bvchovskiy,l.Elson.andD.Estrm.Locatingtinysensorsinlimeandspace:acasestudyIn:Proceedingsel2002IEEEInternationalConferenceonComputerDesign.VLSIinComputersandProcessors(ICCD’0.).Freiburg,GermanyIEEEComputerSociety,2002.9,214-21AFidner,A.Hopper.P.Steggles.A.Word.P.WebsterTheanatomyofacontext-awareapplication.InProceedingsofMobileComposingandNetworking( -99).Seattle.Washington,USA.ACMPress,1999,59-68PinPointCorporation.Website,2001. LewisGirodandDeborahEstrin.RobustRangeEstimationusingAcousticandMultimodalSensing.In:ProceedingsofIEEERSJInternationalConferenceonInligentRobotsandSystems(IROS’01),Maui,Hawaii,USA-IEEEComputerSociety200110,vol.31312-JeffreyHightower,GaetanuBoriefo.RovWantSpotON:Anindoor3DLocationSensingTechnologyBasedonBFSignalStrength.TechnicalReportUWCSE00-02-02,UniversityofWashington,DepartmentofComputerScienceandEngineering,Seattle.WA.USA2000.2AndrewsSavvidcs,Chih-ChiehHan,Man,B.Srivastava.DynamicFine-GrainedLocalizationinAd-HocNetworksofSensorsin:ProceedingsofMobileComputingandNetworking( ’01),Rome,Italy.ACMPress,2001,7,166-DragosNiculescuandBedrlNath.AdHocPositioningSystem(APS)usingAeA.In:ProceedingsofThe22ndAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties( 2003),SanFrancisco,CA,USAIEEEComputerandCommunicationsSocieties,2003,1734-1743AsisNasipunandKaiLi,Adirectionalitybasedlocationdiscoveryschemeforwirelesssensornetworks.In:Proceedingsofthe ACMInternationalWorkshoponWirelessSensorNetworksandApplication(WSNA’02),Atlanta,Geia.USA’ACMPress,20029,105-111SavareseC,RabayJ,LangendoenK.Robustpositioningalgorithmsfordistributedad-hocwirelesssensornetworks.In:EllisCS,ed.Proc.OftheUSENIXTechnicalAnnualConf.Monterey:USENIXPress,2002.317.327.nl/~koen/prs/robust-P.Bergamo.0.Maznni.LocalizationinSensorNetworkswithFadingandMobility.In:ProceedingsofThe13thIEEE.InternationalSymposiumOn al,IndoorandMobileRadioCommunications(IEEEPIMRC2002),Lisbon,Portugal:IEEECommunicationsSociety.2002.9,vol.2.750-NinipamaBulusu,JohnHeidemannandDeborahFarm.GPS-lessLowCostOutdoorLocalizationforVerySmallDevicesIEEE alCommunications,200010,Vol.715.2834AlbertaCerpaandDeborahEstrin.Ascent:Adaptiveself-configuringsensornetworktopologies.TechnicalReportC’SD-TR01-009,UniversityofCalifornia.LosAngeles.ComputerSciencedepartment,2001.5RadhikaNagpal.HowardShrobeandJonathanBachrach.anizingaGlabalCoordinateSystemfromlocalinformationonanAdHocSensorNetworkIn:ZhaoFeng,GuibasLeonidasads.Proceedingsofthe2ndinternationalWorkshoponInformationProcessinginSensorNetworks(IPSN’03),PaloAlto,CA,USASpringer-VerlagPress,2003.4,333-348PriyanthaN.B.,BalakrishnanH.,DemaineE.,etal,Anchor-FreeDistributedLocalizationinSensorNetworks,MITLaboratoryforComputerScienceTechReport#892,April2003.SavareseC.,RabaeyJ.M.,BeuJ.,LocationinginDistributedAd-hocWirelessSensorNetworks,In:Proceedingsof2001IEEEInternationalConference,Acoustics,SpeechandSignalProcessing(ICASSP2001),Piscataway,NJ,USA,May2001,2037～2040.ShangY,RumlW,ZhangY,FromherzMPJ.Localizationfrommereconnectivity[J].In:Proc.ofthe4thinternationalsymposium.onMobileAd puting.Annapolis:ACMPress，2003:201-RentalaP,MusunuriR,GandhamS,SaxenaS.Surveyonsensornetworks[R].TechnicalUTDCS-33-02,UniversityofTexasatShuangTian,XinmingZhang,XinguoWang,PengSun,HaiZhang.“ASelectiveAnchorNodeLocalizationAlgorithmforWirelessSensorNetworks”,Proc.OfIEEE2007InternationalConferenceonConvergenceInformationTechnology,Nov.2007,pp.358-362HongChenSezaki,K.DengHingCheungSo,"AnImprovedDV-HopLocalizationAlgorithmforWirelessSensorNetworks",Proc.OfIEEEComputeran