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

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

三角測量法(Triangulation)原理如圖2.3所示，已知A、B、C三個節(jié)點(diǎn)的坐標(biāo)分別（xa,ya（xb,yb（xc,yc∠BDCD的坐標(biāo)為(x,y)對于節(jié)點(diǎn)A、C和角∠ADC，如果弧段AC在?ABC內(nèi)，那么能夠惟一確定一個圓，設(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個節(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ù)語。這8個指標(biāo)。最后對現(xiàn)有的從6個角度進(jìn)行分類，提出本文重點(diǎn)研究基于非第三 基于非測距的定位算法研究與分成本較高，會提高網(wǎng)絡(luò)部署成本。在基于非測距的定位算法點(diǎn)通過跳數(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)識。此時網(wǎng)絡(luò)中的KtK或者收到數(shù)據(jù)包的時間超過t，那么節(jié)點(diǎn)則停止接收這些來自不同信標(biāo)節(jié)點(diǎn)的數(shù)據(jù)，并且以之前收的質(zhì)心（即坐標(biāo)平均值）作為估算坐標(biāo)，如公式3.1所示。(??,??)=(????1+?+??????, 結(jié)結(jié)開開否是APIT近似三角形內(nèi)測法(ApproximatePoint-In-TriangulationTest,APIT)算法[45]的定位原在信標(biāo)節(jié)點(diǎn)中取出三個組成三角形，然后利用APIT原理判斷自身在這個三角形中與]APIT算法的定位過程中，未知節(jié)點(diǎn)首先收集信標(biāo)節(jié)點(diǎn)在全網(wǎng)絡(luò)中廣播的數(shù)據(jù)的估算坐標(biāo)。而在判斷是否在三角形內(nèi)測時，該算法使用近似三角形內(nèi)點(diǎn)測試法(ApproximatePointinTriangulationTestAPIT)，它的理論基礎(chǔ)是最佳三角形內(nèi)點(diǎn)測試AMAMCBAMCBPITM和三角形ΔABC內(nèi)，如果存在一個方向，該方向上的MA、BCM在三角形ΔABC外部。否則，M在ΔABC。而在WSN中，待定位的未知節(jié)點(diǎn)無法移動，所以不能進(jìn)行理性的PIT測試，因此使用APIT方法。A31A31M2B4CA31M24BC信標(biāo)節(jié)點(diǎn)的信號強(qiáng)度來表示節(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è)的情況。，開開對未知節(jié)點(diǎn)否對未知節(jié)點(diǎn)否是結(jié)算法進(jìn)行定APIT算法在網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)部署且無線信號模型不規(guī)則的網(wǎng)絡(luò)條件下性能穩(wěn)點(diǎn)比例較低的WSN中，該算法無法實(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)收到一個包含距某個信標(biāo)節(jié)點(diǎn)有更小跳數(shù)值的數(shù)據(jù)包，則替代表格中的???????且自增1，否則忽略該數(shù)據(jù)

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

中的坐標(biāo)，?????iji然后，信標(biāo)節(jié)點(diǎn)向全網(wǎng)洪泛廣播利用公式3.2計算出的??opSize??，未知節(jié)點(diǎn)接收HopSize和到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)計算未知節(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ù)值計算與信標(biāo)節(jié)點(diǎn)之間的距離。計算未知節(jié)點(diǎn)坐計算未知節(jié)點(diǎn)坐信標(biāo)節(jié)點(diǎn)跳否定位結(jié)HopSize可以估算出未知節(jié)點(diǎn)的位置。它對硬件的要求較低且Amorphous無定形的定位(Amorphous)算法與DV-HOP算法類似，主要分為三個階段代替，如公式3.4所示。

=∑??∈????????(??)???+???? 與之前數(shù)據(jù)包比接 跳數(shù)信是否開是與之前數(shù)據(jù)包比接 跳數(shù)信是否開是 (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計算與信標(biāo)節(jié)點(diǎn)距離，從而使Amorphous算法的性能較好。但是由于它基于經(jīng)驗(yàn)?zāi)Ｐ投ㄎ唬W(wǎng)絡(luò)擴(kuò)展性比算法仿算法、Amorphous算法進(jìn)行介紹，并深入分析了算法思想、算法流程及算法步驟。本首先，在表3-1實(shí)驗(yàn)參數(shù)條件下，對質(zhì)心算法、APIT算法、DV-HOP算法、Amorphous算法進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)過程中設(shè)置100m×100m大小的正方形平面模擬監(jiān)測區(qū)域，隨機(jī)播撒200個傳感器節(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ā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。在該條件下，四個算法的定位誤差區(qū)別較為明顯，其中質(zhì)心算法定定位誤差最大，而在本實(shí)驗(yàn)中差較高是因?yàn)閷⑼ㄐ虐霃阶鳛槠骄刻嚯x，而本實(shí)驗(yàn)中實(shí)現(xiàn)的是經(jīng)典的改進(jìn)Amorphous算法。下面針對信標(biāo)節(jié)點(diǎn)比例、節(jié)點(diǎn)密度這兩個因素對四種基于非測距定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)比例變化而變化的曲線圖，由圖可知四個算法的定0.10.55，APITDV-HOP0.35-0.43.10APIT從信標(biāo)節(jié)點(diǎn)比例為0.2開始，算法的定位誤差變化較平穩(wěn)。直至信標(biāo)節(jié)點(diǎn)比例為0.5定位相比其他三個算法準(zhǔn)確，且變化幅度較小，保持在0.25-0.27之間。3.10為定位覆蓋率隨信標(biāo)節(jié)點(diǎn)變化而變化的曲線圖，由圖可知算法的定位覆蓋的定位覆蓋率較低0.80.98，因?yàn)檫@兩個算法對通信半徑內(nèi)信標(biāo)節(jié)點(diǎn)的依13.11為仿真實(shí)驗(yàn)過程中命令窗口的輸出結(jié)果，可以作為參照來分析圖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時會遇到網(wǎng)絡(luò)不連通、無法定位的情況，因此圖中此條件下這兩個算80200時，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時，其定位覆蓋率只有0.62，并隨著節(jié)點(diǎn)數(shù)量的增加，可定位節(jié)點(diǎn)比例逐（0.9862000.99，是該變化過程中的最大值。同時，質(zhì)心算法的定位覆蓋率也受40時，節(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)過程中命令窗口的輸出結(jié)果，可以作為參照來分析圖3.12和圖3.13。對比分

3.14輸出結(jié)果圖通過對質(zhì)心算法、APIT算法、DV-HOPAmorphous算法進(jìn)行仿真實(shí)驗(yàn)3-4APIT算 良 良影響比最 影響比較量影響比較 影響比較 最大影響比較 影響比較所需信標(biāo)節(jié)點(diǎn) 適合各向同性度 集網(wǎng) 算法的定位誤差和定位覆蓋率沒有影響，整個變化過程平穩(wěn)，且實(shí)現(xiàn)簡單。而APITAPIT算法相比具有較高的定位覆蓋率，并且與質(zhì)心Amorphous算法，介紹了算法的定位原理、定位流程與定位步驟。然后對以上算法進(jìn)第四DV-HOP根據(jù)上一章對WSN中基于非測距定位算法的深入研究和對比分析，本章選擇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)分布圖，其中星號代表信標(biāo)節(jié)點(diǎn)，空心4-3為該實(shí)驗(yàn)的定位誤差圖，其中空心圓表示這些節(jié)點(diǎn)的估計4.24.3DV-HOP算法中未知節(jié)點(diǎn)的誤差分布規(guī)律，誤差相對較小的節(jié)點(diǎn)坐標(biāo)的是正方形中間區(qū)域的坐標(biāo)。通過多輪實(shí)驗(yàn)驗(yàn)證，此規(guī)律DV-HOP算法估算的估計坐標(biāo)之間的差別.具4.14.2可以計算出網(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個未知節(jié)點(diǎn)的4.4位誤差均值的未知節(jié)點(diǎn)分布情況如圖4.5所示。觀察圖4.4和圖4.5可以發(fā)現(xiàn)，定位誤本節(jié)根據(jù)4.1節(jié)中的誤差來源分析出現(xiàn)上述分布情況的原因，可知在DV-HOP算節(jié)點(diǎn)共享平均每跳距離，未知節(jié)點(diǎn)通過附近的信標(biāo)節(jié)點(diǎn)來確定自身的平均每跳距離。依據(jù)信標(biāo)節(jié)點(diǎn)的位置分布情況判斷產(chǎn)生節(jié)點(diǎn)誤差分布與部署位置相關(guān)的原因是由算與信標(biāo)節(jié)點(diǎn)的距離，計算方式是平均每跳距離乘以跳數(shù)。然而，分布在區(qū)域邊緣部積的跳數(shù)越多，距離中估算的程度就越大，誤差累積也相對增多，從而造成了邊緣節(jié)∑beacons_??HSLbeacons=

∑beacons_??

∑nodes_??HSLnodes=

beacons_n)代表beacons_n個信標(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個節(jié)點(diǎn)的坐標(biāo)，Hop(nodes_n)nodes_n個節(jié)點(diǎn)的跳數(shù)，HSLnodes的結(jié)果代表長度為nodes_n的數(shù)組。使用公式4.4計算出的HSLnodes得出全網(wǎng)所有節(jié)點(diǎn)平均每跳距離的均值，如公4.5∑??????????_nHSaverage=

4.4中，HSaverage代表全網(wǎng)節(jié)點(diǎn)平均每跳距離均值，nodes_nHSLnodes(nodes_n)代表第nodes_n個節(jié)點(diǎn)的平均每跳距離信標(biāo)節(jié)點(diǎn)為一類，超出此范圍的信標(biāo)節(jié)點(diǎn)為另一類，具體如圖4.6和圖4.7所示。是平均每跳距離在均值1m范圍內(nèi)波動改進(jìn)方4.7中信標(biāo)節(jié)點(diǎn)的坐標(biāo)，獲取所分布圓環(huán)區(qū)域的范圍，強(qiáng)制圓環(huán)區(qū)域DV-HOP算法步驟二（計算未知節(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計算出HSLaverage。 是否接受過該 是否接受過該否是否否DV-HOP3個方面對算法的誤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所計算的最初的HopSize值；若不在Dmin—Dmax范圍內(nèi)，則尋找距離該信標(biāo)節(jié)點(diǎn)最近的圓環(huán)區(qū)域內(nèi)的信標(biāo)節(jié)點(diǎn)，其HopSize，從而修正自身的HopSize，即代替由公式3.2計算的HopSize。????stance(i)=2√(???????o)2+(Yi? 5.1中，Distance(i)i個信標(biāo)節(jié)點(diǎn)到點(diǎn)O的距離，(Xi,Yi)i個信標(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和三邊測量法估算自身坐標(biāo)。仿真實(shí)驗(yàn)結(jié)果如圖5.1所示。5.1DV-HOP高。本章對改進(jìn)算法及原始算法進(jìn)行了100輪實(shí)驗(yàn)，每輪實(shí)驗(yàn)兩個算法的實(shí)驗(yàn)參數(shù)及節(jié)點(diǎn)分布情況均相等，得出改進(jìn)算法的定位精度平均可以提高0.3。當(dāng)WSN網(wǎng)絡(luò)環(huán)境較個方面對改進(jìn)DV-HOP算法的定位性能進(jìn)行評估。DV-HOPDV-HOP率均為1，因此本節(jié)只比較兩個算法的定位誤差變化情況。信標(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上下小幅度波動，在信標(biāo)節(jié)點(diǎn)比例為50%時，改進(jìn)算法的定位誤差下降到0.27，原始算0.29240%時，兩個算法的平均定位誤差最大（0.03，說明該條件下改進(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ù)量來表示節(jié)點(diǎn)密度，改變節(jié)點(diǎn)數(shù)量分別為：、、、、、、、180、200。目前在節(jié)點(diǎn)數(shù)量較少的稀疏5.34060100輪實(shí)驗(yàn)中會出現(xiàn)網(wǎng)絡(luò)無法連通的情況，若加大通信半徑會改善這一問題，但是節(jié)點(diǎn)的信號會增加同時能耗0.27較比原始算法的0.29定位精度高出002原始DV-HOP算法。通信半

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

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

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)境測控中的應(yīng)用[J].電氣傳動自動化,2006,28(2):50-,.WSN?？把訹J].學(xué)報,2007,18(5):1077-LiRX,FangZY,HaoBC,etal.ResearchonIndoorWirelessLocalizationSystemforRadioactiveSourcesBasedonZigBee[J].ComputingControlandIndustrialEngineering(CCIE).2010,2:359-362周賢偉,,覃伯平.WSN密鑰管理方案的研究[J].計算機(jī)應(yīng)用研究,2007,24(1):144-Hairong,SitharamaQS,Iyengear,KrishnenduChakrabarty.Distributedsensornetworks-areviewofrecentresearch[J].JournaloftheFranklinInstitute338.2001:655-688,郭鐵成.IBM“智慧地球”我國的思考[N].學(xué)習(xí),2012-10-,.WSN[M].:電子工業(yè),許琦敏.我國無線傳感技術(shù)完整價值鏈己初步完成[N].中華建筑報,2006-11-WSN技術(shù)在電力系統(tǒng)中的應(yīng)用[N].國家電網(wǎng)報,2008-03-中國信息領(lǐng)域研究組.中國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