【導(dǎo)讀】前者精度較高，但是大都需要額外地增加硬件開銷，點的距離或進(jìn)行距離測量，在成本和功耗方面與前者相比具有更加明顯的優(yōu)勢。重點研究了無需測距的無線傳感器網(wǎng)絡(luò)定位算法。外研究現(xiàn)狀，對無線傳感器網(wǎng)絡(luò)定位技術(shù)做了一個整體概述。之后，論文闡述了無線傳。表性的算法及系統(tǒng)的原理和特點，并對其中的幾種進(jìn)行了簡要介紹。最后，論文重點對。對算法的仿真實驗，統(tǒng)計分析了各種因素對算法定位性能的影響。

　　

【正文】 信標(biāo)節(jié)點的標(biāo)識編碼和位置數(shù)據(jù)。相鄰的非信標(biāo)節(jié)點接收到信標(biāo)節(jié)點的消息后，進(jìn)行累計，一旦接收到不同信標(biāo)節(jié)點的消息達(dá)到一個設(shè)定閾值時，就確定這些已知信標(biāo)節(jié)點位置數(shù)據(jù)中的坐標(biāo)值作為質(zhì)心算法中的多邊形的諸頂點坐標(biāo)數(shù)據(jù)，參與計算。 質(zhì)心算法完全基于傳感器網(wǎng)絡(luò)的連通性進(jìn)行定位，實現(xiàn)過程較為簡單，計算量小，不需要網(wǎng)絡(luò)中各節(jié)點的較復(fù)雜的協(xié)調(diào)，擴(kuò)展性好。但該算法的定位精度不高，盡管如此，也能夠滿足對傳感器相對位置數(shù)據(jù)信息精度要有不高的場合應(yīng)用。 圖 質(zhì)心算法示例 2 、 DVHop 算法 該算法是基 于距離矢量計算跳數(shù)的算法。該算法的基本思想是，將待定位節(jié)點到信標(biāo)節(jié)點之間的距離用網(wǎng)絡(luò)中節(jié)點平均每跳距離和到信標(biāo)節(jié)點間的跳數(shù)乘積來標(biāo)識，再使用三邊測量法和最大似然估計法來獲得將待定位節(jié)點的位置信息。 第一個階段：計算待定位節(jié)點與每個信標(biāo)節(jié)點之間的最小跳數(shù)。 第二個階段：計算每一個信標(biāo)節(jié)點與其他信標(biāo)節(jié)點的實際跳段距離。 第三個階段：完成待定位節(jié)點的位置估計。待定位節(jié)點利用第二個階段獲取的網(wǎng)絡(luò)中每一個信標(biāo)節(jié)點與其他信標(biāo)節(jié)點的實際跳段距離的數(shù)據(jù)，使用三邊測量法和最大似然估計法來估計待定位節(jié)點的位置信息。 DVHop 算法的優(yōu)點是比較簡單，無需進(jìn)行節(jié)點之間的距離測量，可以避免測量時帶來的誤差，傳感器節(jié)點不需要其他的附加硬件支持，是無線傳感器網(wǎng)絡(luò)節(jié)點定位的一個較經(jīng)濟(jì)可行的方案。但是這種算法有一些值得改進(jìn)的地方：在獲得平均每跳的計算過程中，節(jié)點之間通信量較大，而且沒有考慮網(wǎng)絡(luò)中存在不良節(jié)點的影響，造成平均定位沈陽理工大學(xué)學(xué)士學(xué)位論文 20 誤差較大。 DVDistance 算法 DVdistance 算法類似于 DVHop 算法，它們之間的區(qū)別在于， DVHop 算法是通過節(jié)點的平均每跳距離和跳數(shù)算出節(jié)點間的距離，而 DVdistance 算法是通過節(jié)點間 使用射頻通信來測量出節(jié)點間的距離，即使用 RSSI 測量節(jié)點間點到點距離 ,然后利用距離矢量路由的方法傳播與鋪節(jié)點的累計距離 ,未知節(jié)點只保留到相應(yīng)描節(jié)點最小跳數(shù)路徑的累計跳段距離 ,并用該路徑的累計跳段距離表示歐式距離 ,當(dāng)未知節(jié)點獲得與 3個或更多鋪節(jié)點的距離后使用三邊測量法或最大似然法定位。 DVDistance 算法具體的定位過程可以分為 2 個步驟： 圖 DVDistance 定位算法示例 步驟 1：獲取未知節(jié)點與描節(jié)點之間最短路徑的累計跳段距離。 首先，利用“洪泛”的方式，鋪節(jié)點向網(wǎng)絡(luò) 周期性地廣播包含跳段和累計跳段距離（均初始化為 0）的自身位置信標(biāo)，收到信標(biāo)的節(jié)點只記錄到相應(yīng)描節(jié)點具有最小跳數(shù)路徑上傳遞過來的信息，并累加該最短路徑上的所有跳段距離，然后該節(jié)點將跳數(shù)加 1轉(zhuǎn)發(fā)信標(biāo)，最后，網(wǎng)絡(luò)中所有節(jié)點都能得到相應(yīng)錨節(jié)點的最短路徑累計跳段距離。如上圖所示，鋪節(jié)點 A A A A4 都會利用網(wǎng)絡(luò)把包括自身信息的信息包發(fā)送給未知節(jié)點 U，未知節(jié)點 U 和錨節(jié)點 A1之間的通信會經(jīng)過另外一個未知節(jié)點 T，當(dāng)錨節(jié)點 A1把信息包傳給這個中間節(jié)點 T 時，節(jié)點 T 就會知道它到錨節(jié)點 A1的距離，當(dāng)它把 A1的信息包轉(zhuǎn)發(fā)給未 知節(jié)點 U 時會把它到錨節(jié)點 A1的距離累加在累計跳段距離變量上，因此當(dāng)未知節(jié)點 U 接收到這個轉(zhuǎn)發(fā)來的包以后利用自己到中間節(jié)點 T 的距離累加在剛才的沈陽理工大學(xué)學(xué)士學(xué)位論文 21 累計跳段距離變量上，就可以獲得 U 到 A1之間的距離了，如上圖中 A1到 U 的累計跳段距離為 2+3=4。其他的錨節(jié)點 A A A4到未知節(jié)點的累計跳段距離也同理可得： 2+ 2+2+2 。 步驟 2：未知節(jié)點根據(jù)記錄的最小累計跳段距離表示到相應(yīng)錨節(jié)點之間的歐氏距離，利用三邊測量法或最大似然法計算得到自身位置。如圖所示，未知節(jié)點 U與錨節(jié)點 AA A A4 的估計歐氏距離分別 表示 為： DU， 1→ DU， 2→ DU， 3→ DU， 4→ 6，就可以建立方程組求解未知節(jié)點 U的位置了。 定位性能的評價標(biāo)準(zhǔn) 定位精度 定位精度： 定位技術(shù) 最重要 的評價指標(biāo)就是定位精度，目前最常用的指標(biāo)是定位解的均方誤差 (MSE)、均方根誤差 (RMSE)、克拉美 羅下界 (CRLB)、圓誤差概率 (CEP)、幾何精度因子 (GDOP)等。也用誤差值與節(jié)點無線射程的比例表示定位精度，例如，定位精度為 15%表示定位誤差相當(dāng)于節(jié)點無線射程的 15%。 節(jié)點密度與參考節(jié)點密度 節(jié)點密度。 在無線傳感器網(wǎng)絡(luò)中，節(jié)點密度增大不僅意味著網(wǎng)絡(luò)部署費用的增加，而且會因為節(jié)點間的通信沖突問題帶來有限帶寬的阻塞。節(jié)點密度通常以網(wǎng)絡(luò)的平均連通度來表示。許多定位算法的精度都受節(jié)點密度的影響。 參考節(jié)點密度：參考節(jié)點的定位一般依賴人工部署或全球定位系統(tǒng)（ GPS）實現(xiàn)。人工部署參考節(jié)點的方式不僅受網(wǎng)絡(luò)部署環(huán)境的限制，還嚴(yán)重制約了網(wǎng)絡(luò)和應(yīng)用的可擴(kuò)展性。而使用全球定位系統(tǒng)定位，參考節(jié)點的費用會比普通節(jié)點高兩個數(shù)量級，這意味著即使僅有 10%的節(jié)點是參考節(jié)點，整個網(wǎng)絡(luò)的價格也將增加 10 倍。因此，參考節(jié)點密度也是評價 定位系統(tǒng)和算法性能的重要指標(biāo)之一。 容錯性和自適應(yīng)性 容錯性和自適應(yīng)性。節(jié)點定位算法都需要比較理想的無線通信環(huán)境和可靠的網(wǎng)絡(luò)節(jié)點設(shè)備。但在真實應(yīng)用場合中常會有諸如以下的問題：外界環(huán)境中存在嚴(yán)重的多徑傳播、沈陽理工大學(xué)學(xué)士學(xué)位論文 22 衰減、非視距、通信盲點等問題；網(wǎng)絡(luò)節(jié)點由于周圍環(huán)境或自身原因而出現(xiàn)失效的問題；外界影響和節(jié)點硬件精度限制造成節(jié)點間點到點的距離或角度測量誤差增大的問題。由于環(huán)境、能耗和其他原因，物理地維護(hù)或替換傳感器節(jié)點或使用其他高精度的測量手段常常是十分困難或不可行的。因此，節(jié)點定位算法的軟、硬件必須具有很 強(qiáng)的容錯性和自適應(yīng)性，能夠通過自動調(diào)整或重構(gòu)糾正錯誤、適應(yīng)環(huán)境、減小各種誤差的影響，以提高定位精度。 功耗、代價與規(guī)模 功耗：功耗是對無線傳感器網(wǎng)絡(luò)的設(shè)計和實現(xiàn)影響最大的因素之一。由于傳感器節(jié)點電池能量有限，因此在保證定位精度的前提下，與功耗密切相關(guān)的定位所需的計算量、通信開銷、存儲開銷和時間復(fù)雜度是一組關(guān)鍵性指標(biāo)。 代價：節(jié)點定位算法的代價可從幾個不同方面來評價。時間代價包括一個系統(tǒng)的安裝時間、配置時間、定位所需時間?？臻g代價包括一個定位算法所需的基礎(chǔ)設(shè)施和網(wǎng)絡(luò)節(jié)點的數(shù)量、硬件尺寸等。資金代 價則包括實現(xiàn)一種定位算法的基礎(chǔ)設(shè)施、節(jié)點設(shè)備的總費用。 規(guī)模：不同的節(jié)點定位系統(tǒng)或算法也許可在園區(qū)內(nèi)、建筑物內(nèi)、一層建筑物或僅僅是一個房間內(nèi)實現(xiàn)定位。另外，給定一定數(shù)量的基礎(chǔ)設(shè)施或在一段時間內(nèi)，一種技術(shù)可以定位多少目標(biāo)也是一個重要的評價指標(biāo)。 上述七個性能指標(biāo)，即是無線傳感器網(wǎng)絡(luò)節(jié)點定位算法的評價標(biāo)準(zhǔn)，也是其設(shè)計和實現(xiàn)的優(yōu)化目標(biāo)。這些指標(biāo)相互聯(lián)系，需根據(jù)應(yīng)用的具體需求做出權(quán)衡，以選擇合適的節(jié)點定位算法。 沈陽理工大學(xué)學(xué)士學(xué)位論文 23 4 基于 MATLAB 的 DVdistance 測距算法性能分析 DVdistance 定位算法 算法簡述 該算法由兩個階段組成：第一階段利用洪泛協(xié)議，使未知節(jié)點獲得錨節(jié)點周期性發(fā)送的信息分組，其中包括最小跳數(shù)和累計 跳段 距離。第二階段通過距離矢量交換協(xié)議，在二維平面區(qū)域內(nèi)使未知節(jié)點獲得三個或者三個以上錨節(jié)點的信息分組：最小跳數(shù)和累計跳段距離。通過這一機(jī)制就避免了廣播信息的無限循環(huán)，并得到了未知節(jié)點與參考節(jié)點的最小跳數(shù)和累計跳段距離。第三階段將最小跳數(shù)當(dāng)做實際距離使用，并通過三邊算法或者最大似然估計法獲得未知節(jié)點的位置信息，實現(xiàn)定位。 具體實現(xiàn)見第 3 章的“ DVdistance” 算法部分 。 在 DVdistance 算法中，使用到兩種重要的路由協(xié)議 ： 洪泛協(xié)議和距離矢量 交換 協(xié)議。 洪泛協(xié)議，是最簡單的路由協(xié)議，此協(xié)議中沒有任何路由算法。節(jié)點向它的所有鄰居節(jié)點廣播所收到的數(shù)據(jù)，直到數(shù)據(jù)到達(dá)目的節(jié)點或達(dá)到數(shù)據(jù)報的最大跳數(shù)。洪泛協(xié) 議 的缺點是容易引起信息重疊，造成網(wǎng)絡(luò)擁塞。因此針對洪泛協(xié)議中的重疊信息，DVdistance 算法采用了可控洪泛法。 距離矢量 交換 協(xié)議，是簡單路徑的分布式路由算法。每個節(jié)點維護(hù)一張到網(wǎng)絡(luò)中已知位置節(jié)點的距離估計和下一跳的路由表。節(jié)點周期性地向鄰居節(jié)點廣播自 己的路由表，同時節(jié)點根據(jù)接收到的居節(jié)點的路由廣播來更新自己的路由表。每個節(jié)點只記錄到目的節(jié)點的跳數(shù)和通向目的節(jié)點的下一跳。節(jié)點接收到數(shù)據(jù)后，根據(jù)數(shù)據(jù)包頭部的目的地址來查找路由表，并將其轉(zhuǎn)發(fā)到下一跳所指定的節(jié)點。該類路由協(xié)議有 AODV(Ad hoc on Demand Distance Vector)等。 DVdistance 算法利用距離矢量路由協(xié)議來實現(xiàn)未知節(jié)點在接收到錨節(jié)點發(fā)出的信標(biāo)消息時判斷出自身與該錨節(jié)點相隔的跳數(shù) 。 沈陽理工大學(xué)學(xué)士學(xué)位論文 24 開始 錨節(jié)點周期性地廣播自身信息信標(biāo) 未知節(jié)點接收錨節(jié)點的信息包 收到的錨節(jié)點數(shù)量 =3 利用累計跳段距離表示對應(yīng)錨節(jié)點的歐式距離 三邊測量法或最大似然法計算估計坐標(biāo) 結(jié)束 no yes 算法流程圖 DVdistance 算法由 3 個階段組成 ，流程如下圖 。 圖 DVdistance 算法流程圖 沈陽理工大學(xué)學(xué)士學(xué)位論文 25 網(wǎng)絡(luò)初始 調(diào)用 DVdistance（ typt） 節(jié)點剩余能量 E0 保存多次測量結(jié)果進(jìn)行由大 到小排序 延時 最小值是否為 0 迭加 返回 Y N 網(wǎng)絡(luò)總體流程圖如下： 圖 網(wǎng)絡(luò)總體流程圖 沈陽理工大學(xué)學(xué)士學(xué)位論文 26 錨節(jié)點模塊流程圖如下： 圖 錨節(jié)點模塊流程圖 定時廣播錨節(jié)點信息 接收和轉(zhuǎn)發(fā)其他錨節(jié)點信息 是否第一次收到某錨節(jié)點信息 判斷跳數(shù)是否小于已存跳數(shù) 丟棄該數(shù)據(jù) 將接收到的信息存入錨節(jié)點信息表 更新錨節(jié)點信息表中的跳數(shù) 錨節(jié)點信息表中的錨節(jié)點是否大于 2 計算平均每跳距離并廣播 N Y Y N Y N 初始化 沈陽理工大學(xué)學(xué)士學(xué)位論文 27 未知節(jié)點模塊流程圖如下： 圖 未知節(jié)點模塊流程圖 MATLAB仿真環(huán)境簡介 Matlab 是近幾年來在國外廣泛流行的一種可視化科學(xué)計算軟件，它不但具有結(jié)構(gòu)簡單、數(shù)值計算高效、圖形功能完備和圖像處理方便的特點，還具有符號計算、文字處理、可視化仿真和實時控制能力，該軟件已經(jīng)成為適合多學(xué)科、多部門要求的新一代應(yīng)用軟件。 Matlab 語言是由美國 MathWork 公司推出的計算機(jī)軟件，經(jīng)過多年的逐步發(fā)展與完善，已經(jīng)成為國際公認(rèn)的最優(yōu)秀的科學(xué)計算與數(shù)學(xué)應(yīng)用軟件之一。其內(nèi)容涉及矩陣代數(shù)、微積分、應(yīng)用數(shù)學(xué)、有限元法、科學(xué)計算、信號與系統(tǒng)、神經(jīng)網(wǎng)絡(luò)、小波分析及其應(yīng) 用、數(shù)學(xué)圖像處理、計算機(jī)圖形學(xué)、電子線路、電機(jī)學(xué)、自動控制與通信技術(shù)、物理、力學(xué)、和機(jī)械振動等方面。 初始化網(wǎng)絡(luò) 接收和轉(zhuǎn)發(fā)接收到的錨節(jié)點節(jié)點信息將接到的錨節(jié)點信息寫入錨節(jié)點信息表 利用三邊測量法計算自身坐標(biāo) 錨節(jié)點信息表中錨節(jié)點數(shù)是否大于 3 回傳 坐標(biāo)信息 Y N 沈陽理工大學(xué)學(xué)士學(xué)位論文 28 Matlab 是 Matrix Laboratory（矩陣實驗室）的縮寫，最初由 Cleve Moler 博士在 70年代末講授矩陣?yán)碚摵蛿?shù)據(jù)分析等課程時編寫的軟件包 Linpack 與 Eispack 組成，旨在使應(yīng)用人員免去大量經(jīng)常重復(fù)的矩陣運算和基本數(shù)學(xué)運算等繁瑣的編程工作。 與 Fortran 語言和 C 等高級語言比較， Matlab 的語法規(guī)則更簡單，更重要的是它貼近人思維方式的編程特點，使得用 Matlab 編寫程序猶如在便 箋上列公式和求解。 80 年代初期， CleveMoler 和 John Little 采用 C 語言改寫了 Matlab 的內(nèi)核。不久，他們成立了 MathWork 軟件開發(fā)公司并將 Matlab 正式推向市場。 1999年 1月推出了 ( ),真正實現(xiàn)了 32位運算 ,其速度更快、功能更完善、界面更友好，并且提供了 Inter 搜索引擎，可協(xié)助用戶尋求在線幫助。新版本 又作了更精細(xì)的改進(jìn)，相對于 版本，新版本增加了許多新功能，主要表現(xiàn)在以下幾方面： ? 增強(qiáng)了