【正文】 2004， 30(7):130314 劉運(yùn)杰，金明錄， 位算法[J].，23(5):07170515 汪場， ，30(l):590416 王建剛，王福豹， 應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2006，36(9):410317 陳鵬，錢徽，[ 學(xué)，2009，36(11):2300318 Wong，WAccuracy和BorderLength成正比關(guān)系；和NodeAmount成反比關(guān)系；和BeaconAmount成反比關(guān)系；和R成反比關(guān)系。在比較Rangefree和Rangebased算法優(yōu)劣性基礎(chǔ)上，將其中的Rangefree定位算法作為本文研究的主要內(nèi)容，并對其中的DVHop算法進(jìn)行了分析。Accuracy和BorderLength成正比關(guān)系；和NodeAmount成反比關(guān)系；和BeaconAmount成反比關(guān)系；和R成反比關(guān)系，從而給出一個最佳的定位方案。方案6參數(shù)如下：BorderLength=50；NodeAmount=100；BeaconAmount=10；UNAmount=NodeAmountBeaconAmount；R=40；此時error = ，Accuracy = 仿真結(jié)果如圖420，圖421。算法的平均誤差定義為：取基本方案（方案1）如下：BorderLength=100；NodeAmount=200；BeaconAmount=20；UNAmount=NodeAmountBeaconAmount；R=60；此時error = ，Accuracy（定位精度） = 仿真結(jié)果如圖410，圖411：表格 定位方案方案BorderLengthNodeAmountBeaconAmountRErrorAccuracy11002002060220020020603100100206041002001060510020020406501001040方案2仿真結(jié)果如圖412和413；方案3仿真結(jié)果如圖414和415；方案4仿真結(jié)果如圖416和417；方案5仿真結(jié)果如圖418和419；方案6仿真結(jié)果如圖420和421；通過修改基本方案1的參數(shù)，每次只改變一個，從而得到對比性很強(qiáng)的方案2到方案5。利用此得到以跳數(shù)估計(jì)的距離。用MATLAB 仿真軟件對無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的定位算法進(jìn)行仿真：（1）產(chǎn)生節(jié)點(diǎn)均勻隨機(jī)分布的網(wǎng)絡(luò)拓?fù)?，用符合均勻分布的隨機(jī)數(shù)生成每個節(jié)點(diǎn)的坐標(biāo)。（6）節(jié)點(diǎn)擁有兩種不同的標(biāo)記：anchor、single，分別用來表示錨節(jié)點(diǎn)和無法定位的節(jié)點(diǎn)。（2）傳感器節(jié)點(diǎn)采用自由空間電波傳播模型，即節(jié)點(diǎn)的通信范圍一個圓。同時由于MATLAB對矩陣和線性代數(shù)的支持使得工具箱本身也具有強(qiáng)大的數(shù)學(xué)計(jì)算能力。由于其完整的專業(yè)體系和先進(jìn)的設(shè)計(jì)開發(fā)思路，使得MATLAB在多種領(lǐng)域都有廣闊的應(yīng)用空間。每個節(jié)點(diǎn)維護(hù)一張到網(wǎng)絡(luò)中已知位置節(jié)點(diǎn)的距離估計(jì)和下一跳的路由表。（1）洪泛協(xié)議，是最簡單的路由協(xié)議，此協(xié)議中沒有任何路由算法。已知節(jié)點(diǎn)的程序流程圖如圖(45)所示，未知節(jié)點(diǎn)的程序流程圖如圖(46)所示。未知節(jié)點(diǎn)的權(quán)值一旦大于1，或者連續(xù)2次得到的坐標(biāo)極其接近，則終止該循環(huán)步驟。節(jié)點(diǎn)利用加權(quán)最小二乘法來改變它的坐標(biāo)等數(shù)據(jù)。利用MINMAX算法，未知節(jié)點(diǎn)憑借鄰居已知節(jié)點(diǎn)的位置與通訊模型，根據(jù)公式 (410)，能夠求解出它所處的范圍。在的情況下，估算值的均方誤差達(dá)到最低，其中M表示長度誤差的方差矩陣。在無距離估算值的前提下，使用公式(410)，來求解待測節(jié)點(diǎn)的估算坐標(biāo)值。如果未知節(jié)點(diǎn)的鄰居已知節(jié)點(diǎn)數(shù)是v，則它的坐標(biāo)一定在這些已知節(jié)點(diǎn)通訊范圍的交集中，如圖44所示。(l)MINMAX算法MINMAX算法用已知節(jié)點(diǎn)做圓心，把待測節(jié)點(diǎn)到此已知節(jié)點(diǎn)的長度估算值看作半徑，并創(chuàng)建此圓的外接正方形。定位精度的高低主要取決已知節(jié)點(diǎn)數(shù)量的多少。通過使用lenef值與avgeef值，待測節(jié)點(diǎn)即可得到其與所有已知節(jié)點(diǎn)的長度。如果新的hopk值比舊的的hopk值小，則用 hopk的新值來代替{IDk，xk，yk，hopk，mm、lenef、avgeef}中的舊值；否則拋棄掉此信息。使得任意一個已知節(jié)點(diǎn)都能得到其它已知節(jié)點(diǎn)的m、lenef、avgeef等值。Y0：0均值的高斯分布隨機(jī)變量。假若己知節(jié)點(diǎn)e的平均每跳長度用HopDisef表示，已知節(jié)點(diǎn)e到f(e≠f）的總跳數(shù)是m，Disef已知節(jié)點(diǎn)e到己知節(jié)點(diǎn)喲每跳長度和，Disef己知節(jié)點(diǎn)e到已知節(jié)點(diǎn)動實(shí)際長度。但在真實(shí)的環(huán)境中，待測節(jié)點(diǎn)到已知節(jié)點(diǎn)的路程通常都是曲線，用原算法會產(chǎn)生較大誤差。用這個方法求出的坐標(biāo)，存在一定的誤差，且定位精度不高。待測節(jié)點(diǎn)要和已知節(jié)點(diǎn)取得聯(lián)系，就一定要經(jīng)過中間節(jié)點(diǎn)刁一可以取得聯(lián)系。圖43 第3類bad節(jié)點(diǎn)的示意圖(2)待測節(jié)點(diǎn)與已知節(jié)點(diǎn)之間的每跳跳距，是用已知節(jié)點(diǎn)之間的平均每跳距離來表示的。(iii)bad節(jié)點(diǎn)是節(jié)點(diǎn)群。如圖42所示，節(jié)點(diǎn)N同樣也能夠出現(xiàn)在N這個地方。換句話說，我們無法判斷節(jié)點(diǎn)N所在的地方。19第4章 DVHop算法改進(jìn)和MATLAB仿真 第4章 DVHop算法改進(jìn)和MATLAB仿真 DVHop算法的缺陷(1)在無線傳感器網(wǎng)絡(luò)中，由于節(jié)點(diǎn)被隨機(jī)分布，所以會存在一些bad節(jié)點(diǎn)；(i)節(jié)點(diǎn)N在一跳之內(nèi)僅存在1個節(jié)點(diǎn)。在上例中，假設(shè)A從L2獲得校正值，則它與3個錨節(jié)點(diǎn)之間的距離分別為L13*，L22*，L33*，然后使用三邊測量法確定節(jié)點(diǎn)A的位置。當(dāng)接收到校正值之后，節(jié)點(diǎn)根據(jù)跳數(shù)計(jì)算與錨節(jié)點(diǎn)之間的距離。首先使用典型的距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得距錨節(jié)點(diǎn)的跳數(shù)(distance in hops)。錨節(jié)點(diǎn)計(jì)算完每跳平均距離后，用帶有生存期字段的消息分組廣播到網(wǎng)絡(luò)中，未知節(jié)點(diǎn)僅記錄接收到的第一個每跳平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。AdHoc positioning中將其稱為DVHop，Robust positioning中則將其稱為HopTERRAIN。在基于測距的方法中，未知節(jié)點(diǎn)只能獲得到自己射頻覆蓋范圍內(nèi)的錨節(jié)點(diǎn)的距離，而DVHop算法可以獲得到未知節(jié)點(diǎn)無線射程以外的錨節(jié)點(diǎn)的距離，這樣就可以獲得更多的有用數(shù)據(jù)，提高定位精度。為了將跳數(shù)值轉(zhuǎn)換成物理距離，系統(tǒng)需要估計(jì)網(wǎng)絡(luò)中平均每跳的距離。此信標(biāo)在網(wǎng)絡(luò)中被以泛洪的方式傳播出去，信標(biāo)每次被轉(zhuǎn)發(fā)時跳數(shù)都增加1。由于質(zhì)心算法完全基于網(wǎng)絡(luò)連通性，無需信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的協(xié)調(diào)，因此簡單、易于實(shí)現(xiàn)。多邊形ABCDE的頂點(diǎn)坐標(biāo)分別為：A，B，C、D、E，其質(zhì)心坐標(biāo)：。具體過程為：錨節(jié)點(diǎn)每隔一段時間向鄰居節(jié)點(diǎn)廣播一個信標(biāo)信號，信號中包含有錨節(jié)點(diǎn)自身的ID和位置信息。在二維平面上的，雙曲線的幾何意義是到兩個定點(diǎn)的距離之差為一個常數(shù)的所有點(diǎn)的集合，兩個定點(diǎn)稱作焦點(diǎn)。通過記錄兩種不同信號的到達(dá)時間差異，根據(jù)已知的兩種信號的傳播速度，直接把時間差轉(zhuǎn)化為距離。在這種方法中，若電波從錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的傳播時間為t，電波傳播速度為c，則錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離為t*c。未知節(jié)點(diǎn)首先測量到鄰居節(jié)點(diǎn)的距離或角度，然后進(jìn)一步計(jì)算到臨近錨節(jié)點(diǎn)的距離或角度，在計(jì)算到臨近錨節(jié)點(diǎn)的距離時，可以計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的直線距離，也可以用二者之間的跳段距離作為直線距離的近似；（2）定位階段。假設(shè)有m個節(jié)點(diǎn)的坐標(biāo)事先知道，它們的坐標(biāo)是(xi，si)(i=l，2，…，m)，己知節(jié)點(diǎn)的個數(shù)m必須大于等于3(m≧3)；ri表示第i個已知節(jié)點(diǎn)與未知節(jié)點(diǎn)N之間的長度。因此會有下面的公式成立： （33）通過公式(33)的推導(dǎo)，即可以得到圓心C1的坐標(biāo)和半徑d1。這種方式前提是已知錨節(jié)點(diǎn)數(shù)，另外其位置估算的精度會隨著測試次數(shù)的增加而增加；（2）結(jié)合角度測量即通過方向性天線，利用AOA測量的角度值來定位。但是，由于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的硬件和能耗限制，所以節(jié)點(diǎn)間測距誤差較大，因此可能會出現(xiàn)三個圓無法交于一點(diǎn)的情況。這個的方法是利用以三個錨節(jié)點(diǎn)為中心的圓交點(diǎn)作為未知節(jié)點(diǎn)的位置。而基于非測距的定位機(jī)制無需距離或角度信息，或者不用直接測量這些信息，僅根據(jù)網(wǎng)絡(luò)的連通性等信息實(shí)現(xiàn)節(jié)點(diǎn)的定位。相對于基于測距技術(shù)的定位算法而言，距離無關(guān)定位在網(wǎng)絡(luò)密度、通信開銷方面比較大，但在能量、可擴(kuò)張性方面具有較大的優(yōu)勢。因此，本論文的目前主要的研究工作是利用傳感器網(wǎng)絡(luò)中少量已知位置的節(jié)點(diǎn)來獲得其他未知位置節(jié)點(diǎn)的位置信息。9第3章 無線傳感器網(wǎng)絡(luò)定位技術(shù) 第3章 無線傳感器網(wǎng)絡(luò)定位技術(shù) WSN定位技術(shù)分類關(guān)于無線傳感器網(wǎng)絡(luò)的定位問題分為兩類，一類是無線傳感器網(wǎng)絡(luò)對自身傳感器節(jié)點(diǎn)的定位[9]，另一類是無線傳感器網(wǎng)絡(luò)對外部目標(biāo)的定位[9]。但在一般情形下，大部分傳感器節(jié)點(diǎn)的位置不會改變。節(jié)點(diǎn)數(shù)量可能會達(dá)到成千上萬個，它們被緊密地部署在監(jiān)測范圍中。 與現(xiàn)有無線網(wǎng)絡(luò)的區(qū)別移動無線自組網(wǎng) [8](Mobile AdHoc Network)是一種對等網(wǎng)絡(luò)，具備多跳移動、動態(tài)組網(wǎng)、無線通訊等特點(diǎn)，含有幾十、甚至幾百個節(jié)點(diǎn)。在WSN中，軟硬件環(huán)境與網(wǎng)絡(luò)協(xié)議都存在著許多不一樣的地方。在WSN中，節(jié)點(diǎn)被任意分布，它的編號和位置是無絕對關(guān)聯(lián)的。(5)無線傳感器網(wǎng)絡(luò)具有可靠性在WSN中，傳感器節(jié)點(diǎn)也許會被撒播在非常糟糕的環(huán)境下，也許會被撒播在人們不容易進(jìn)入的區(qū)域。WSN的自組織能力，可以滿足該拓?fù)浣Y(jié)構(gòu)易變的要求。(3)無線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)易變化，它具有自組織能力對于WSN，我們需要考慮傳感器節(jié)點(diǎn)的節(jié)能性，所以這些節(jié)點(diǎn)應(yīng)該能在運(yùn)行與休眠狀態(tài)下方便切換。因此，數(shù)據(jù)在傳遞的過程中，使用空間位置尋址。 無線傳感器網(wǎng)絡(luò)的特征 無線傳感器網(wǎng)絡(luò)的特點(diǎn)無線傳感器網(wǎng)絡(luò)主要包含以下特征:(1)傳感器節(jié)點(diǎn)數(shù)量大、密度高，用空間位置尋址為了確保網(wǎng)絡(luò)的生存周期，WSN中可能會有數(shù)以千計(jì)的傳感器節(jié)點(diǎn)。無線通訊模塊的作用是，能夠使傳感器節(jié)點(diǎn)與除它之外的傳感器節(jié)點(diǎn)取得聯(lián)系(通訊)，并互換操作的數(shù)據(jù)、獲取并發(fā)送監(jiān)測信息。傳感器節(jié)點(diǎn)結(jié)構(gòu)[14]的示意圖如圖22所示:圖22 傳感器節(jié)點(diǎn)結(jié)構(gòu)傳感器模塊的作用是，獲取監(jiān)控范圍中的數(shù)據(jù)與轉(zhuǎn)換這些內(nèi)容。它實(shí)現(xiàn)了WSN與外部網(wǎng)絡(luò)的互連，能夠使2個協(xié)議棧間的通訊協(xié)議相互轉(zhuǎn)變，并且廣播管理節(jié)點(diǎn)的感知內(nèi)容，最后監(jiān)測到的信息被傳遞給互聯(lián)網(wǎng)。故從網(wǎng)絡(luò)用途的角度來考慮，所有傳感器節(jié)點(diǎn)都具備普通網(wǎng)絡(luò)節(jié)點(diǎn)的2個功能:終端與路由。監(jiān)測人員通過任務(wù)管理節(jié)點(diǎn)配置與管理WSN，發(fā)布監(jiān)測任務(wù)及獲取監(jiān)測數(shù)據(jù)。WSN由以下幾個部分組成:傳感器節(jié)點(diǎn)(sensor node)、網(wǎng)關(guān)[12](或匯聚節(jié)點(diǎn)sink node)、互聯(lián)網(wǎng)或通訊衛(wèi)星、任務(wù)管理節(jié)點(diǎn)。最后是參考文獻(xiàn)、致謝、附錄。重點(diǎn)研究了以下內(nèi)容：計(jì)算出用RSSI[5]測量的距離值與每跳距離和的均值，然后利用該均值與實(shí)際距離的差值，得到總距離與平均每跳的距離誤差校正值。第二章主要介紹無線傳感器網(wǎng)絡(luò)相關(guān)背景知識。用MINMAX[5]與加權(quán)最小二乘法的混合定位法替換了三邊測量法。本文研究了基于測距和無需測距的定位算法，并總結(jié)了這類算法的優(yōu)劣勢。可以看出，WSN節(jié)點(diǎn)定位技術(shù)的運(yùn)用前景相當(dāng)好。在知道任意一個節(jié)點(diǎn)與其周邊節(jié)點(diǎn)的坐標(biāo)后，網(wǎng)絡(luò)才可以達(dá)到改善路由的目的。傳感器節(jié)點(diǎn)一般被隨機(jī)撒播在監(jiān)測范圍內(nèi)，例如它們被撒播在監(jiān)測生態(tài)環(huán)境、火災(zāi)現(xiàn)場等場所，這些傳感器節(jié)點(diǎn)并不清楚自己的位置，故要求傳感器節(jié)點(diǎn)一旦被分布，就應(yīng)該可以快速自定位。通訊、嵌入式與傳感器這3項(xiàng)技術(shù)的逐漸成熟，使得WSN快速發(fā)展。因此，WSN與自組織網(wǎng)，能夠?qū)ζ浒l(fā)展起到促進(jìn)作用。無基本設(shè)備支撐的無線自組織網(wǎng)，其具有以下特性:多跳、自組織與可重構(gòu)。清華大學(xué)、中國科技大學(xué)、浙江大學(xué)、華中科技大學(xué)、天津大學(xué)、南開大學(xué)、北京郵電大學(xué)、東北大學(xué)、西北工業(yè)大學(xué)、西南交通大學(xué)、沈陽理工大學(xué)和上海交通大學(xué)等單位紛紛開展了有關(guān)無線傳感器網(wǎng)絡(luò)方面的基礎(chǔ)研究工作。俄亥俄州正在開發(fā)“沙地直線”（A Line in the Sand）無線傳感器網(wǎng)絡(luò)系統(tǒng)。這就要求我們必須設(shè)計(jì)出適合在WSN中使用的節(jié)點(diǎn)定位算法。用GPS定位使得成本增大，不符合WSN的價格低廉性。其次，WSN的工作環(huán)境特別復(fù)雜，不能一定使接收儀器與衛(wèi)星之間可以無阻礙的進(jìn)行通訊。這會讓我們現(xiàn)在的生活發(fā)生翻天覆地的變化。因此在傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)的精確、快速定位對各種應(yīng)用有著重要的作用。在真實(shí)的運(yùn)用環(huán)境中，獲取數(shù)據(jù)會遇到以下難題:不容易布置線路、獲取信息的面積大。第1章 緒論 無線傳感器網(wǎng)絡(luò)單元定位算法研究與實(shí)現(xiàn)畢業(yè)論文 緒論 選題背景和研究意義微電子、無線通訊與計(jì)算機(jī)技術(shù)的發(fā)展，促使低能耗多用途傳感器被廣泛運(yùn)用在各個領(lǐng)域。傳感技術(shù)的任務(wù)是獲取數(shù)據(jù)，通訊技術(shù)的任務(wù)是傳遞數(shù)據(jù)，計(jì)算機(jī)技術(shù)的任務(wù)是處理數(shù)據(jù)。協(xié)助路由，為網(wǎng)絡(luò)提供命名空間，如直接用節(jié)點(diǎn)位置信息進(jìn)行數(shù)據(jù)傳遞的地理路由一協(xié)議，避免信息在整個網(wǎng)絡(luò)中的擴(kuò)散，并可以實(shí)現(xiàn)定向的信息查詢；進(jìn)行網(wǎng)絡(luò)管理，利用傳感器節(jié)點(diǎn)傳回的位置信息構(gòu)建網(wǎng)絡(luò)拓?fù)鋱D，并實(shí)時統(tǒng)計(jì)網(wǎng)絡(luò)覆蓋隋況，對節(jié)點(diǎn)密度低的區(qū)域及時采取必要的措施，實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡以及網(wǎng)絡(luò)拓?fù)涞淖耘渲?，等等。如果我們認(rèn)為互聯(lián)網(wǎng)組建了虛擬世界，使人們的通訊方式發(fā)生了變化，則WSN便融合了虛擬世界與現(xiàn)實(shí)世界，這無疑使人和自然的交流發(fā)生了變化。因?yàn)镚PS消耗能量特別大，所以不適合給每個傳感器節(jié)點(diǎn)都配置能耗較大的GPS設(shè)備。最后，WSN中的傳感器節(jié)點(diǎn)被大量分布在監(jiān)測范圍內(nèi)，數(shù)量達(dá)到了幾千乃至上萬個?？紤]到傳感器節(jié)點(diǎn)在能量、體積、環(huán)境、價格等方面的一些要素，可知GPS不完全適用于WSN。尤其是今年最新試制成功的低成本美軍“狼群”地面無線傳感器網(wǎng)絡(luò)標(biāo)志