【正文】 目 錄1 引言 12 定位技術(shù) 2 基本概念和算法 2 感器節(jié)點(diǎn)定位的基本概念 2 基本術(shù)語 2 計(jì)算節(jié)點(diǎn)位置的基本方法 3 定位算法分類 5 基于距離的定位 6 基于TOA的定位 6 基于TDOA的定位 7 基于AOA的定位 7 基于RSSI的定位 9 距離無關(guān)的定位算法 9 質(zhì)心算法 10 DVHOP算法 10 APIT算法 123 算法實(shí)現(xiàn)與仿真 14 仿真的硬件平臺 14 TinyOS集成開發(fā)環(huán)境與nesC編程語言 14 nesC編程語言 14 TinyOS系統(tǒng) 15 基于RSSI信號傳播的理論模型的DVHOP定位算法 17 用TinyOS的TOSSIM及圖形化工具TinyViz進(jìn)行仿真 214 結(jié)語 26致謝 27參考文獻(xiàn) 28附錄 281 引言無線傳感器網(wǎng)絡(luò)是由一些相互配合的節(jié)點(diǎn)組織成的一個(gè)網(wǎng)絡(luò)。每個(gè)節(jié)點(diǎn)都具有處理能力（有一個(gè)或多個(gè)微控制器，CPU或DSP芯片），還可包括多種類型的存儲器（程序，數(shù)據(jù)和閃存），一個(gè)射頻收發(fā)器（能常是用一個(gè)全方位的定向天線），電源（如電池和太陽能電池），和各種傳感器、執(zhí)行器。這些節(jié)點(diǎn)被部署在一個(gè)特定的環(huán)境中后，它們通常通過自組織的形式，實(shí)現(xiàn)無線通信。在計(jì)算機(jī)科學(xué)領(lǐng)域，傳感器網(wǎng)絡(luò)是一個(gè)研究熱點(diǎn)，每年都會召開很多的會議。在眾多的研究熱點(diǎn)問題中出了MAC（介質(zhì)訪問控制協(xié)議）、路由、時(shí)鐘同步、電源管理這些問題之外，最重要的便是節(jié)點(diǎn)定位問題。節(jié)點(diǎn)定位是確定在系統(tǒng)中的每個(gè)節(jié)點(diǎn)的地理位置的問題。定位問題對于WSN來說是必須解決的最基本的問題之一。無線傳感器網(wǎng)絡(luò)中，事件發(fā)生的位置是傳感器節(jié)點(diǎn)監(jiān)測和應(yīng)用中需要的重要信息，沒有位置信息的監(jiān)測往往沒有意義[1]。定位信息除用來報(bào)告事件發(fā)生的地點(diǎn)外，還具有下列用途：目標(biāo)跟蹤，實(shí)時(shí)監(jiān)視目標(biāo)的行動路線，預(yù)測目標(biāo)的前進(jìn)軌跡；協(xié)助路由，如直接利用節(jié)點(diǎn)位置信息進(jìn)行數(shù)據(jù)傳遞的地理路由協(xié)議，避免信息在整個(gè)網(wǎng)絡(luò)中的擴(kuò)散等等。因此，確定事件發(fā)生的位置或獲取消息的節(jié)點(diǎn)位置是傳感器網(wǎng)絡(luò)最基本的功能，對傳感器網(wǎng)絡(luò)的應(yīng)用起著關(guān)鍵的作用。雖然使用GPS來定位，比較常見成熟，但無線傳感網(wǎng)對成本、和電源有嚴(yán)格的限制，有些場合不適合用來定位。目前，主要解決方法是利用少量已知節(jié)點(diǎn)，通過節(jié)點(diǎn)定位算法，以獲得節(jié)點(diǎn)的信息。因此，要采用一定的定位機(jī)制與算法來實(shí)現(xiàn)WSN的節(jié)點(diǎn)定位。本論文在第二章對當(dāng)前的定位技術(shù)進(jìn)行了詳細(xì)的闡述。在陳述了節(jié)點(diǎn)定位技術(shù)的基本概念和術(shù)語后，分析了計(jì)算節(jié)點(diǎn)位置的三種常見方法，包括三邊定位，三角定位，極大似然估計(jì)。根據(jù)定位算法定位時(shí)是否需要測量距離為標(biāo)準(zhǔn)，將無線傳感器的定位算法分為：基于距離的算法和距離無關(guān)的算法，前者著重分析了基于RSSI、TOA等測距的4種定位算法的的原理和思想；距離無關(guān)的定位算法講了質(zhì)心算法、DVHOP、APIT算法的理論基礎(chǔ)和定位步驟等。最后對這幾種算法做了簡單的比較，對不同的應(yīng)用提供參考。在第三章中，以信號傳播的理論模型為基礎(chǔ)，在Mica2硬件平臺，用TinyOS操作系統(tǒng)和nesC語言，實(shí)現(xiàn)基于RSSI測距的DVHOP定位算法，并利用TOSSIM進(jìn)行了仿真，對得到的結(jié)果進(jìn)行了簡要分析。定位算法的具體實(shí)現(xiàn)可以為將來實(shí)際定位系統(tǒng)提供一些借鑒。2 定位技術(shù) 基本概念和算法 傳感器節(jié)點(diǎn)定位的基本概念在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)中，根據(jù)節(jié)點(diǎn)是否已知自身的位置，把傳感器節(jié)點(diǎn)分為信標(biāo)節(jié)點(diǎn)（beacon node）和未知節(jié)點(diǎn)（unknown node）。信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)節(jié)點(diǎn)中所占的比例很小，可以通過攜帶GPS定位設(shè)備等手段獲得自身的精確位置。信標(biāo)節(jié)點(diǎn)是未知節(jié)點(diǎn)定位的參考點(diǎn)。除了信標(biāo)節(jié)點(diǎn)外，其他傳感器節(jié)點(diǎn)就是未知節(jié)點(diǎn)，它們通過信標(biāo)節(jié)點(diǎn)的位置信息來確定自身位置。在如圖1所示的傳感器網(wǎng)絡(luò)中，M代表信標(biāo)節(jié)點(diǎn)，S代表未知節(jié)點(diǎn)。S節(jié)點(diǎn)通過與鄰近M節(jié)點(diǎn)或已經(jīng)得到位置信息的S節(jié)點(diǎn)之間的通信，根據(jù)一定的定位算法計(jì)算出自身的位置[2]。圖1　傳感器網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn) 基本術(shù)語鄰居節(jié)點(diǎn)（neighbor nodes）：傳感器節(jié)點(diǎn)通信半徑內(nèi)的所有其他節(jié)點(diǎn)，稱為該 節(jié)點(diǎn)的鄰居節(jié)點(diǎn)；跳數(shù)（hop count）：兩個(gè)節(jié)點(diǎn)之間間隔的跳段總數(shù)，稱為兩個(gè)節(jié)點(diǎn)間的跳數(shù)；跳段距離（hop distance）：兩個(gè)節(jié)點(diǎn)之間間隔的各跳段距離之和，稱為兩節(jié)點(diǎn) 間的跳段距離；基礎(chǔ)設(shè)施（infrastructure）：協(xié)助傳感器節(jié)點(diǎn)定位的已知自身位置的固定設(shè)備， 如衛(wèi)星、基站等；到達(dá)時(shí)間（time of arrival，TOA）：信號從一個(gè)節(jié)點(diǎn)傳播到另一節(jié)點(diǎn)所需要的 時(shí)間，稱為信號的到達(dá)時(shí)間；到達(dá)時(shí)間差（time difference of arrival，TDOA）：兩種不同傳播速度的信號從一 個(gè)節(jié)點(diǎn)傳播到另一個(gè)節(jié)點(diǎn)所需要的時(shí)間之差，稱為信號的到達(dá)時(shí)間差；接收信號強(qiáng)度指示（received signal strength indicator，RSSI）：節(jié)點(diǎn)接收到無線信號的強(qiáng)度大小，稱為接收信號的強(qiáng)度指示；到達(dá)角度（angle of arrival，AOA）：節(jié)點(diǎn)接收到的信號相對于自身軸線的角度， 稱為信號相對接收節(jié)點(diǎn)的到達(dá)角度；視線關(guān)系（line of sight，LOS）：兩個(gè)節(jié)點(diǎn)間沒有障礙物間隔，能夠直接通信， 稱為兩個(gè)節(jié)點(diǎn)間存在視線關(guān)系；非視線關(guān)系（NLOS，no LOS）：兩個(gè)節(jié)點(diǎn)之間存在障礙物。 計(jì)算節(jié)點(diǎn)位置的基本方法 三角計(jì)算法 三角測量法（triangulation）原理如圖2所示，已知A，B，C三個(gè)節(jié)點(diǎn)的坐標(biāo)圖2　三角測量法圖示分別為，節(jié)點(diǎn)D相對于節(jié)點(diǎn)A，B，C的角度分別為：∠ADB，∠ADC，∠BDC，假設(shè)節(jié)點(diǎn)D的坐標(biāo)為。對于節(jié)點(diǎn)A，C和角∠ADC，如果弧段AC在△ABC內(nèi)，那么能夠惟一確定一個(gè)圓，設(shè)圓心為，半徑為，那么，并存在下列公式： (21)由式(21)能夠確定圓心點(diǎn)的坐標(biāo)和半徑。同理對，和，分別確定相應(yīng)的圓心、半徑、圓心和半徑。最后利用三邊測量法，由點(diǎn)，，確定D點(diǎn)坐標(biāo)。 三邊測量法在無線傳感器網(wǎng)絡(luò)中，坐標(biāo)系大多是二維空間，因此，只要知道一個(gè)未知節(jié)點(diǎn)到3個(gè)或3個(gè)以上錨節(jié)點(diǎn)的距離就可以確定該未知節(jié)點(diǎn)的坐標(biāo)。在基于測距的定位算法中，三邊測量法是計(jì)算坐標(biāo)的基本途徑。所圖2所示。圖3　三邊測量法圖示三邊測量定位法的基本原理就是求3個(gè)已知半徑和坐標(biāo)圓心的圓的交點(diǎn)。已知A，B，C三個(gè)節(jié)點(diǎn)的坐標(biāo)分別為，，以及它們到未知節(jié)點(diǎn)D的距離分別為，假設(shè)節(jié)點(diǎn)D的坐標(biāo)為。那么，存在下列公式： (22)由式(22)可以得到節(jié)點(diǎn)D的坐標(biāo)為： (23) 極大似然估計(jì)法極大似然估計(jì)法(maximum likelihood estimation)如圖4所示，已知1，2，3等圖4　極大似然估計(jì)法圖示n個(gè)節(jié)點(diǎn)的坐標(biāo)分別為，它們到節(jié)點(diǎn)D的距離分 別為，假設(shè)節(jié)點(diǎn)D的坐標(biāo)為。那么，存在下列公式： (24)從第一個(gè)方程開始分別減去最后一個(gè)方程，得： (25)式(25)的線性方程表示方式為：，其中： (26) (27)使用標(biāo)準(zhǔn)的最小均方差估計(jì)方法可以得到節(jié)點(diǎn)D的坐標(biāo)為：。 定位算法分類在傳感器網(wǎng)絡(luò)中，定位算法通常有以下幾種分類：基于距離的定位算法和距離無關(guān)的定位算法根據(jù)定位過程中是否測量實(shí)際節(jié)點(diǎn)間的距離，把定位算法分為：基于距離的(rangebased)定位算法和距離無關(guān)的(rangefree)定位算法[3]。前者需要測量相鄰節(jié)點(diǎn)間的絕對距離或方位，并利用節(jié)點(diǎn)間的實(shí)際距離來計(jì)算未知節(jié)點(diǎn)的位置；后者無需測量節(jié)點(diǎn)間的絕對距離或方位，而是利用節(jié)點(diǎn)間的估計(jì)距離計(jì)算節(jié)點(diǎn)位置。本章將以此種分類為線索介紹各種定位算法。遞增式的定位算法和并發(fā)式的定位算法根據(jù)節(jié)點(diǎn)定位的先后次序不同，把定位算法分為：遞增式的（incremental）定位算法和并發(fā)式的（concurrent）定位算法。遞增式的定位算法通常從信標(biāo)節(jié)點(diǎn)開始，信標(biāo)節(jié)點(diǎn)附近的節(jié)點(diǎn)首先開始定位，依次向外延伸，各節(jié)點(diǎn)逐次進(jìn)行定位這類算法的主要缺點(diǎn)是定位過程中產(chǎn)生的誤差會越積越多；并發(fā)式的定位算法中所有的節(jié)點(diǎn)同時(shí)進(jìn)行位置計(jì)算?；谛艠?biāo)節(jié)點(diǎn)的定位算法和無信標(biāo)節(jié)點(diǎn)的定位算法根據(jù)定位過程中是否使用信標(biāo)節(jié)點(diǎn)，把定位算法分為：基于信標(biāo)節(jié)點(diǎn)的(beaconbased)定位算法和無信標(biāo)節(jié)點(diǎn)的(beaconfree)定位算法。前者在定位過程中，以信標(biāo)節(jié)點(diǎn)作為定位中的參考點(diǎn)，各節(jié)點(diǎn)定位后產(chǎn)生整體絕對坐標(biāo)系統(tǒng)；后者只關(guān)心節(jié)點(diǎn)間的相對位置，在定位過程中無需信標(biāo)節(jié)點(diǎn)，各節(jié)點(diǎn)先以自身作為參考點(diǎn)，將鄰近的節(jié)點(diǎn)納入自己定義的坐標(biāo)系中，相鄰的坐標(biāo)系統(tǒng)依次轉(zhuǎn)換，最后產(chǎn)生整體相對坐標(biāo)系統(tǒng)。 基于距離的定位基于距離的定位機(jī)制（rangebased）是通過測量相鄰節(jié)點(diǎn)間的實(shí)際距離或方位進(jìn)行定位。具體過程通常分為三個(gè)階段：第一個(gè)階段是測距階段，未知節(jié)點(diǎn)首先測量到鄰居節(jié)點(diǎn)的距離或角度，然后進(jìn)一步計(jì)算到鄰近信標(biāo)節(jié)點(diǎn)的距離或方位，在計(jì)算到鄰近信標(biāo)節(jié)點(diǎn)的距離時(shí)，可以計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的直線距離，也可以用二者之間的跳段距離作為直線距離的近似；第二個(gè)階段是定位階段，未知節(jié)點(diǎn)在計(jì)算出到達(dá)三個(gè)或三個(gè)以上信標(biāo)節(jié)點(diǎn)的距離或角度后，利用三邊測量法、三角測量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)；第三個(gè)階段是修正階段，對求得的節(jié)點(diǎn)的坐標(biāo)進(jìn)行求精，提高定