無線定位技術(shù)課件

無線定位技術(shù)

無線定位技術(shù)

一、引言二、節(jié)點(diǎn)定位技術(shù)基本概念三、基于距離的定位算法四、與距離無關(guān)的定位算法五、總結(jié)無線定位技術(shù)課件引言無線傳感器節(jié)點(diǎn)的位置信息對于傳感網(wǎng)來說至關(guān)重要，沒有位置信息的監(jiān)測數(shù)據(jù)往往毫無意義。在傳感網(wǎng)的各種應(yīng)用中，監(jiān)測到事件后關(guān)心的一個(gè)重要問題就是該事件發(fā)生的位置。如在環(huán)境監(jiān)測應(yīng)用中需要知道采集的環(huán)境信息所對應(yīng)的具體區(qū)域位置；對于突發(fā)事件，需要知道森林火災(zāi)現(xiàn)場位置，戰(zhàn)場上敵方車輛運(yùn)動(dòng)的區(qū)域，天然氣管道泄漏的具體地點(diǎn)等。傳感器節(jié)點(diǎn)自身定位就是根據(jù)少數(shù)已知位置的節(jié)點(diǎn)，按照某種定位機(jī)制確定自身位置。只有在傳感器節(jié)點(diǎn)自身正確定位之后，才能確定傳感器節(jié)點(diǎn)監(jiān)測到的事件發(fā)生的具體位置，這需要監(jiān)測到該事件的多個(gè)傳感器節(jié)點(diǎn)之間的相互協(xié)作，并利用它們自身的位置信息，使用特定定位機(jī)制確定事件發(fā)生的位置。引言無線傳感器節(jié)點(diǎn)的位置信息對于傳感網(wǎng)來說至關(guān)重要，沒有位置引言全球定位系統(tǒng)GPS(GlobalPositionSystem)是目前應(yīng)用最廣泛最成熟的定位系統(tǒng)，通過衛(wèi)星的授時(shí)和測距對用戶節(jié)點(diǎn)進(jìn)行定位，具有定位精度高、實(shí)時(shí)性好、抗干擾能力強(qiáng)等優(yōu)點(diǎn)，但是GPS定位適應(yīng)于無遮擋的室外環(huán)境，用戶節(jié)點(diǎn)通常能耗高體積大，成本也比較高，需要固定的基礎(chǔ)設(shè)施等，這使得不適用于低成本自組織的傳感網(wǎng)。在機(jī)器人領(lǐng)域中，機(jī)器人節(jié)點(diǎn)的移動(dòng)性和自組織等特性，其定位技術(shù)與傳感網(wǎng)的定位技術(shù)具有一定的相似性，但是機(jī)器人節(jié)點(diǎn)通常攜帶充足的能量供應(yīng)和精確的測距設(shè)備，系統(tǒng)中機(jī)器人的數(shù)量很少，所以這些機(jī)器人定位算法也不適用于傳感網(wǎng)。受到成本、功耗、擴(kuò)展性等問題的限制，為每個(gè)傳感器安裝GPS模塊等這些傳統(tǒng)定位手段并不實(shí)際，甚至在某些場合可能根本無法實(shí)現(xiàn)，因此必須采用一定的機(jī)制與算法實(shí)現(xiàn)傳感器節(jié)點(diǎn)的自身定位返回引言全球定位系統(tǒng)GPS(GlobalPositionSy節(jié)點(diǎn)定位技術(shù)基本概念1．定位的含義無線傳感網(wǎng)定位問題是指網(wǎng)絡(luò)通過特定方法提供節(jié)點(diǎn)的位置信息。其定位方式可分為節(jié)點(diǎn)自身定位和目標(biāo)定位。自身定位：是確定網(wǎng)絡(luò)節(jié)點(diǎn)的坐標(biāo)位置的過程。節(jié)點(diǎn)自身定位是網(wǎng)絡(luò)自身屬性的確定過程，可以通過人工標(biāo)定或者各種節(jié)點(diǎn)的自定位算法完成。目標(biāo)定位：是確定網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)一個(gè)事件或者一個(gè)目標(biāo)的坐標(biāo)位置。目標(biāo)定位是以位置已知的網(wǎng)絡(luò)節(jié)點(diǎn)作為參考，確定事件或者目標(biāo)在網(wǎng)絡(luò)覆蓋范圍內(nèi)所在的位置。位置信息有多種分類方法。通常有物理位置和符號位置兩大類。物理位置指目標(biāo)在特定坐標(biāo)系下的位置數(shù)值，表示目標(biāo)的相對或者絕對位置。符號位置指目標(biāo)與一個(gè)基站或者多個(gè)基站接近程度的信息，表示目標(biāo)與基站之間的連通關(guān)系，提供目標(biāo)大致的所在范圍。節(jié)點(diǎn)定位技術(shù)基本概念1．定位的含義在很多傳感網(wǎng)應(yīng)用場合中，必須知道各節(jié)點(diǎn)物理位置的坐標(biāo)信息。通過人工測量或配置來獲得節(jié)點(diǎn)坐標(biāo)的方法往往不可行。通常傳感網(wǎng)能夠通過網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)之間的相互測距和信息交換，形成一套全網(wǎng)節(jié)點(diǎn)的坐標(biāo)。這才是經(jīng)濟(jì)和可行的定位方案。從廣義上來講，無線傳感網(wǎng)的定位問題包括傳感器節(jié)點(diǎn)的自身定位和對監(jiān)控目標(biāo)的定位。目標(biāo)定位側(cè)重于傳感網(wǎng)在目標(biāo)跟蹤方面的應(yīng)用，是對監(jiān)控目標(biāo)的位置估計(jì)，它以先期的節(jié)點(diǎn)自身定位為基礎(chǔ)。從不同的角度出發(fā)，無線傳感網(wǎng)的定位方法可以進(jìn)行如下分類。（1）根據(jù)是否依靠測量距離，分為基于測距的定位和不需要測距的定位。（2）根據(jù)部署的場合不同，分為室內(nèi)定位和室外定位。（3）根據(jù)信息收集的方式，網(wǎng)絡(luò)收集傳感器數(shù)據(jù)用于節(jié)點(diǎn)定位被稱為被動(dòng)定位，節(jié)點(diǎn)主動(dòng)發(fā)出信息用于定位被稱為主動(dòng)定位。在很多傳感網(wǎng)應(yīng)用場合中，必須知道各節(jié)點(diǎn)物理位置的坐標(biāo)信息。通2．基本術(shù)語（1）信標(biāo)節(jié)點(diǎn)：指預(yù)先獲得位置坐標(biāo)的節(jié)點(diǎn)，也被稱作錨點(diǎn)。其余節(jié)點(diǎn)被稱為非錨點(diǎn)。（2）測距：指兩個(gè)相互通信的節(jié)點(diǎn)通過測量的方式來估計(jì)出彼此之間的距離或角度。（3）連接度：包括節(jié)點(diǎn)連接度和網(wǎng)絡(luò)連接度兩種含義。節(jié)點(diǎn)連接度是指節(jié)點(diǎn)可探測發(fā)現(xiàn)的鄰居節(jié)點(diǎn)個(gè)數(shù)。網(wǎng)絡(luò)連接度是所有節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目的平均值，它反映了傳感網(wǎng)節(jié)點(diǎn)配置的密集程度。（4）鄰居節(jié)點(diǎn)：傳感節(jié)點(diǎn)通信半徑以內(nèi)的所有其他節(jié)點(diǎn)，被稱為該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。（5）接收信號強(qiáng)度指示（ReceivedsignalStrengthIndicator，RSSI）：節(jié)點(diǎn)接收到無線信號的強(qiáng)度大小，被稱為接收信號的強(qiáng)度指示。（6）到達(dá)角度（AngleofArrival，AoA）：節(jié)點(diǎn)接收到的信號相對于自身軸線的角度，被稱為信號相對接收節(jié)點(diǎn)的到達(dá)角度。（7）視線關(guān)系（Lineofsight，LoS）:如果兩個(gè)節(jié)點(diǎn)之間沒有障礙物，能夠?qū)崿F(xiàn)直接通信，則稱這兩個(gè)節(jié)點(diǎn)間存在視線關(guān)系。（8）非視線關(guān)系（NoneLineofsight，NLoS）：兩個(gè)節(jié)點(diǎn)之間存在障礙物，影響了它們直接的無線通信。2．基本術(shù)語（1）信標(biāo)節(jié)點(diǎn)：指預(yù)先獲得位置坐標(biāo)的節(jié)點(diǎn)，也被稱3．定位性能的評價(jià)指標(biāo)（1）定位精度：定位精度指提供的位置信息的精確程度，它分為相對精度和絕對精度。絕對精度指以長度為單位度量的精度。例如，GPS的精度為1～10m，現(xiàn)在使用GPS導(dǎo)航系統(tǒng)的精度約5m。一些商業(yè)的室內(nèi)定位系統(tǒng)提供30cm的精度，可以用于工業(yè)環(huán)境、物流倉儲(chǔ)等場合。相對精度通常以節(jié)點(diǎn)之間距離的百分比來定義。例如，若兩個(gè)節(jié)點(diǎn)之間距離是20m，定位精度為2m，則相對定位精度為10％。由于有些定位方法的絕對精度會(huì)隨著距離的變化而變化，因而使用相對精度可以很好地表示精度指標(biāo)。設(shè)節(jié)點(diǎn)的估計(jì)坐標(biāo)與真實(shí)坐標(biāo)在二維情況下的距離差值為，則個(gè)未知位置節(jié)點(diǎn)的網(wǎng)絡(luò)平均定位誤差為。（2）覆蓋范圍：覆蓋范圍和定位精度是一對矛盾性的指標(biāo)。例如超聲波可以達(dá)到分米級精度，但是它的覆蓋范圍只有10多米；Wi-Fi和藍(lán)牙的定位精度為3米左右，覆蓋范圍可以達(dá)到100米左右；GSM系統(tǒng)能覆蓋千米級的范圍，但是精度只能達(dá)到100米。由此可見，覆蓋范圍越大，提供的精度就越低。提供大范圍內(nèi)的高精度通常是難以實(shí)現(xiàn)的。3．定位性能的評價(jià)指標(biāo)（1）定位精度：3．定位性能的評價(jià)指標(biāo)（3）刷新速度：刷新速度是指提供位置信息的頻率。例如，如果GPS每秒刷新1次，則這種頻率對于車輛導(dǎo)航已經(jīng)足夠了，能讓人體驗(yàn)到實(shí)時(shí)服務(wù)的感覺。對于移動(dòng)的物體，如果位置信息刷新較慢，就會(huì)出現(xiàn)嚴(yán)重的位置信息滯后，直觀上感覺已經(jīng)前進(jìn)了很長距離，提供的位置還是以前的位置。因此，刷新速度會(huì)影響定位系統(tǒng)實(shí)際工作提供的精度，它還會(huì)影響位置控制者的現(xiàn)場操作。如果刷新速度太低，可能會(huì)使得操作者無法實(shí)施實(shí)時(shí)控制。（4）功耗：功耗作為傳感網(wǎng)設(shè)計(jì)的一項(xiàng)重要指標(biāo)，對于定位這項(xiàng)服務(wù)功能，需要計(jì)算為此所消耗的能量。采用的定位方法不同，功耗的差別會(huì)很大，主要原因是定位算法的復(fù)雜度不同，需要為定位提供的計(jì)算和通信開銷方面存在數(shù)量上的差別，導(dǎo)致完成定位服務(wù)的功耗有所不同。（5）代價(jià)：定位系統(tǒng)或算法的代價(jià)可從幾個(gè)不同方面來評價(jià)。時(shí)間代價(jià)包括一個(gè)系統(tǒng)的安裝時(shí)間、配置時(shí)間、定位所需時(shí)間?？臻g代價(jià)包括一個(gè)定位系統(tǒng)或算法所需的基礎(chǔ)設(shè)施和網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量、硬件尺寸等。資金代價(jià)則包括實(shí)現(xiàn)一種定位系統(tǒng)或算法的基礎(chǔ)設(shè)施、節(jié)點(diǎn)設(shè)備的總費(fèi)用。返回3．定位性能的評價(jià)指標(biāo)（3）刷新速度：返回基于距離的定位算法基于測距的定位技術(shù)是通過測量節(jié)點(diǎn)之間的距離，根據(jù)幾何關(guān)系計(jì)算出網(wǎng)絡(luò)節(jié)點(diǎn)的位置。解析幾何里有多種方法可以確定一個(gè)點(diǎn)的位置。比較常用的方法是多邊定位和角度定位。這里重點(diǎn)介紹通過距離測量的方式，它可以用來計(jì)算傳感網(wǎng)中某一未知位置的節(jié)點(diǎn)坐標(biāo)。基于距離的定位算法基于測距的定位技術(shù)是通過測量節(jié)點(diǎn)之間的距測距方法1．接收信號強(qiáng)度指示（RSSI）2．到達(dá)時(shí)間（ToA）3．到達(dá)時(shí)間差（TDoA）4．到達(dá)角（AoA）測距方法1．接收信號強(qiáng)度指示（RSSI）1．接收信號強(qiáng)度指示（RSSI）基于RSSI定位算法，是通過測量發(fā)送功率與接收功率，計(jì)算傳播損耗。利用理論和經(jīng)驗(yàn)?zāi)Ｐ?，將傳播損耗轉(zhuǎn)化為發(fā)送器與接收器的距離。該方法易于實(shí)現(xiàn)，無需在節(jié)點(diǎn)上安裝輔助定位設(shè)備。當(dāng)遇到非均勻傳播環(huán)境，有障礙物造成多徑反射或信號傳播模型過于粗糙時(shí)，RSSI測距精度和可靠性降低，有時(shí)測距誤差可達(dá)到50%。一般將RSSI和其他測量方法綜合運(yùn)用來進(jìn)行定位。1．接收信號強(qiáng)度指示（RSSI）基于RSSI定位算法，是通過2．到達(dá)時(shí)間（ToA）

這類方法通過測量傳輸時(shí)間來估算兩節(jié)點(diǎn)之間距離。精度較好。但由于無線信號的傳輸速度快，時(shí)間測量上的很小誤差就會(huì)導(dǎo)致很大的誤差值，所以要求傳感器節(jié)點(diǎn)有較強(qiáng)的計(jì)算能力。這兩種基于時(shí)間的測距方法適用于多種信號，如射頻、聲學(xué)、紅外和超聲波信號等。ToA機(jī)制是已知信號的傳播速度，根據(jù)信號的傳播時(shí)間來計(jì)算節(jié)點(diǎn)間的距離。如圖6-1所示為某于ToA測距的簡單實(shí)現(xiàn)過程示例，采均偽噪聲序列信號作為聲波信號，根據(jù)聲波的傳播時(shí)間來測量節(jié)點(diǎn)之間的距離。2．到達(dá)時(shí)間（ToA）

這類方法通過測量傳輸時(shí)間來估算兩節(jié)點(diǎn)2．到達(dá)時(shí)間（ToA）(2)假設(shè)兩個(gè)節(jié)點(diǎn)預(yù)先變現(xiàn)了時(shí)間同步，在發(fā)送節(jié)點(diǎn)發(fā)送偽噪聲序列信號的同時(shí)，無線傳輸模塊通過無線電同步消息通知接收節(jié)點(diǎn)偽噪聲序列信號發(fā)送的時(shí)間，接收節(jié)點(diǎn)的麥克風(fēng)模塊檢測到偽噪聲序列信號后，根據(jù)聲波信號的傳播時(shí)間和速度來計(jì)算節(jié)點(diǎn)間的距離。節(jié)點(diǎn)在計(jì)算出多個(gè)鄰近的信標(biāo)節(jié)點(diǎn)后，利用多邊測量算法和極大似然估計(jì)算法算出自身的位置。ToA采用的聲波信號進(jìn)行到達(dá)時(shí)間測量。由于聲波頻率低，速度低。對節(jié)點(diǎn)硬件的成本和復(fù)雜度的要求很低，但聲波的傳播速度易受大氣條件的影響。ToA算法的定位精度高，但要求節(jié)點(diǎn)間保持精確的時(shí)間同步，對傳感器節(jié)點(diǎn)的硬件和功耗提出了較高的要求。2．到達(dá)時(shí)間（ToA）(2)假設(shè)兩個(gè)節(jié)點(diǎn)預(yù)先變現(xiàn)了時(shí)間同步，3．到達(dá)時(shí)間差（TDoA）在基于TDoA的定位機(jī)制中，發(fā)射節(jié)點(diǎn)同時(shí)發(fā)射兩種不同傳播速度的無線信號，接收節(jié)點(diǎn)根據(jù)兩種信號到達(dá)的時(shí)間差以及這兩種信號的傳播速度計(jì)算兩個(gè)節(jié)點(diǎn)之間的距離。如圖6-2所示，發(fā)射節(jié)點(diǎn)同時(shí)發(fā)射無線射頻信號和超聲波信號，接收節(jié)點(diǎn)記錄下這兩種信號的到達(dá)時(shí)間T1、T2，巳知無線射頻信號和超聲波的傳播速度為c1、c2，那么兩點(diǎn)之間的距離為(T2-T1)S，其中S=c1c2/(c2-c1)。3．到達(dá)時(shí)間差（TDoA）在基于TDoA的定位機(jī)制中，發(fā)射節(jié)3．到達(dá)時(shí)間差（TDoA）(2)由于無線射頻信號的傳播速度要遠(yuǎn)大于超聲波的傳播速度，因而未知節(jié)點(diǎn)在收到無線射頻信號時(shí)，會(huì)同時(shí)打開超聲波信號接收機(jī)。根據(jù)兩種信號的到達(dá)時(shí)間間隔和各自的傳播速度，未知節(jié)點(diǎn)算出和該信標(biāo)節(jié)點(diǎn)之間的距離，然后通過比較到各個(gè)鄰近信標(biāo)節(jié)點(diǎn)的距離，選擇出離自身最近的信標(biāo)節(jié)點(diǎn)，從該信標(biāo)節(jié)點(diǎn)廣播的信息中取得自身的位置。TDoA技術(shù)對節(jié)點(diǎn)硬件的要求高，其對成本和功耗的要求使得該技術(shù)對低成本、低功耗的傳感網(wǎng)設(shè)計(jì)提出了挑戰(zhàn)。當(dāng)然TDoA技術(shù)的測距誤差小，具有較高精度。3．到達(dá)時(shí)間差（TDoA）(2)由于無線射頻信號的傳播速度要4．到達(dá)角（AoA）該方法通過配備特殊天線來估測其他節(jié)點(diǎn)發(fā)射的無線信號的到達(dá)角度。它的硬件要求較高，每個(gè)節(jié)點(diǎn)要安裝昂貴的天線陣列和超聲波接收器。在基于AoA的定位機(jī)制中，接收節(jié)點(diǎn)通過天線陣列或多個(gè)超聲波接收機(jī)，來感知發(fā)射節(jié)點(diǎn)信號的到達(dá)方向，計(jì)算接收節(jié)點(diǎn)和發(fā)射節(jié)點(diǎn)之間的相對方位和角度，再通過三角測量法計(jì)算節(jié)點(diǎn)的位置。如圖6-3所示，接收節(jié)點(diǎn)通過麥克風(fēng)陣列，探測發(fā)射節(jié)點(diǎn)信號的到達(dá)方向。AoA定位不僅能夠確定節(jié)點(diǎn)的坐標(biāo)，還能夠確定節(jié)點(diǎn)的方位信息。但是AoA測距技術(shù)易受外界環(huán)境影響，且需要額外硬件，因此它的硬件尺寸和功耗指標(biāo)并不適用于大規(guī)模的傳感網(wǎng)。4．到達(dá)角（AoA）該方法通過配備特殊天線來估測其他節(jié)點(diǎn)發(fā)射節(jié)點(diǎn)定位計(jì)算方法在傳感器節(jié)點(diǎn)定位過程中，未知節(jié)點(diǎn)在獲得對于鄰近信標(biāo)節(jié)點(diǎn)的距離，或獲得鄰近的信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的相對角度后，通常使用下列方法計(jì)算自己的坐標(biāo)。（1）三邊測量法（2）三角測量法（3）極大似然估計(jì)法節(jié)點(diǎn)定位計(jì)算方法在傳感器節(jié)點(diǎn)定位過程中，未知節(jié)點(diǎn)在獲得對于（1）三邊測量法

三邊測量法（trilateration）如圖6-4所示，已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(xa,ya)、(xb,yb)、(xc,yc)，以及它們到未知節(jié)點(diǎn)D的距離分別為da、db、dc，假設(shè)節(jié)點(diǎn)D的坐標(biāo)為(x,y)。那么存在下列公式：可以得到節(jié)點(diǎn)D的坐標(biāo)為（1）三邊測量法

三邊測量法（trilateration）如（2）三角測量法三角測量法(triangulation)原理如圖6-5所示，已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(xa,ya)、(xb,yb)、(xc,yc)，節(jié)點(diǎn)D相對于節(jié)點(diǎn)A、B、C的角度分別為∠ADB、∠ADC

、∠BDC

，假設(shè)節(jié)點(diǎn)D的坐標(biāo)為(x,y)。對于節(jié)點(diǎn)A、C和角∠ADC

，如果弧段AC在△ABC內(nèi)，那么能夠惟一確定一個(gè)圓，設(shè)圓心為O1(xo1,yo1)，半徑為r1，那么角α=∠AO1C=2π-2∠ADC，并存在下列公式：由式（6.3）能夠確定圓心點(diǎn)的坐標(biāo)和半徑。同理對A、B、∠

ADB和B、C、∠

BDC分別確定相應(yīng)的圓心、半徑。最后利用三邊測量法，由三個(gè)圓心點(diǎn)及其半徑確定D點(diǎn)坐標(biāo)。（2）三角測量法三角測量法(triangulation)原理（3）極大似然估計(jì)法

極大似然估計(jì)法(maximumlikelihoodestimation，MLE)如圖2.4所示，己知1、2、3等個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(x1,y1)、(x2,y2)、…、(xn,yn)，它們到未知節(jié)點(diǎn)的距離分別為d1、d2、、…、dn，假設(shè)未知節(jié)點(diǎn)的坐標(biāo)為(x,y)。有公式：解方程得：其中：返回（3）極大似然估計(jì)法

極大似然估計(jì)法(maximumlik與距離無關(guān)的定位算法

與距離無關(guān)的定位技術(shù)不需要直接測量距離和角度信息。它不是通過測量節(jié)點(diǎn)之間的距離來定位的，而是僅根據(jù)網(wǎng)絡(luò)的連通性確定網(wǎng)絡(luò)中節(jié)點(diǎn)之間的跳數(shù)，同時(shí)根據(jù)已知位置的參考節(jié)點(diǎn)的坐標(biāo)等信息估計(jì)出每一跳的大致距離，然后估計(jì)出節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置。與距離無關(guān)的定位算法無須測量節(jié)點(diǎn)間的絕對距離或方位，降低了對節(jié)點(diǎn)硬件的要求。目前主要有兩類距離無關(guān)的定位方法：一類是先對未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)之間的距離進(jìn)行估計(jì)，然后利用多邊定位等方法完成對其他節(jié)點(diǎn)的定位；另一類是通過鄰居節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)來確定包含未知節(jié)點(diǎn)的區(qū)域，然后將這個(gè)區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)。距離無關(guān)的定位方法精度低，但能滿足大多數(shù)應(yīng)用的要求。距離無關(guān)的定位算法主要有質(zhì)心算法、DV-Hop算法、Amorphous算法、APIT算法等。與距離無關(guān)的定位算法

與距離無關(guān)的定位技術(shù)不需要直接測量距離1．質(zhì)心算法在計(jì)算幾何學(xué)里，多邊形的幾何中心被稱為質(zhì)心，多邊形頂點(diǎn)坐標(biāo)的平均值就是質(zhì)心節(jié)點(diǎn)的坐標(biāo)。假設(shè)多邊形頂點(diǎn)位置的坐標(biāo)向量表示為，則這個(gè)多邊形的質(zhì)心坐標(biāo)計(jì)算方法如下。這種方法的計(jì)算與實(shí)現(xiàn)都非常簡單，可以根據(jù)網(wǎng)絡(luò)的連通性確定信標(biāo)節(jié)點(diǎn)周圍的信標(biāo)參考節(jié)點(diǎn)，直接求解信標(biāo)參考節(jié)點(diǎn)構(gòu)成的多邊形的質(zhì)心。在傳感網(wǎng)的質(zhì)心定位系統(tǒng)的實(shí)現(xiàn)中，信標(biāo)節(jié)點(diǎn)周期性地向鄰近節(jié)點(diǎn)廣播分組信息，該信息包含了信標(biāo)節(jié)點(diǎn)的標(biāo)識和位置。在未知節(jié)點(diǎn)接收到來自不同信標(biāo)節(jié)點(diǎn)的分組信息數(shù)量超過某一門限或在接收了一定時(shí)間之后，就可以計(jì)算這些信標(biāo)節(jié)點(diǎn)所組成的多邊形的質(zhì)心，并以此確定自身位置。質(zhì)心定位算法雖然實(shí)現(xiàn)簡單、通信開銷小，但僅能實(shí)現(xiàn)粗精度定位，并且需要信標(biāo)節(jié)點(diǎn)具有較高的密度，各信標(biāo)節(jié)點(diǎn)部署的位置也對定位效果有影響。1．質(zhì)心算法在計(jì)算幾何學(xué)里，多邊形的幾何中心被稱為質(zhì)心，多邊2．DV-Hop算法距離向量-跳數(shù)（distancevector-hop，DV-Hop）算法定位機(jī)制非常類似于傳統(tǒng)網(wǎng)絡(luò)中的距離向量路由機(jī)制。在距離向量定位機(jī)制中，未知節(jié)點(diǎn)首先計(jì)算與信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，然后估算平均跳數(shù)的距離，利用最小跳數(shù)乘以平均每跳距離，得到未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的估計(jì)距離，再利用三邊測量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。DV-Hop算法的定位過程分為以下三個(gè)階段：（1）計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的最小跳數(shù)信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身的位置信息的分組，其中包括跳數(shù)字段，初始化為0。接收節(jié)點(diǎn)記錄具有到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，忽略來自同一個(gè)信標(biāo)節(jié)點(diǎn)的最大跳數(shù)的分組。然后將跳數(shù)值加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。通過這種方法，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)能夠記錄下到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。如圖6-7所示，信標(biāo)節(jié)點(diǎn)A廣播的分組以近似于同心圓的方式在網(wǎng)絡(luò)中逐次傳播，圖中的數(shù)字代表距離信標(biāo)節(jié)點(diǎn)A的跳數(shù)。2．DV-Hop算法距離向量-跳數(shù)（distancevec圖6-7信標(biāo)節(jié)點(diǎn)廣播分組傳播過程圖示圖6-7信標(biāo)節(jié)點(diǎn)廣播分組傳播過程圖示（2）計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳數(shù)距離每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)第一個(gè)階段記錄的其他信標(biāo)節(jié)點(diǎn)的位置信息和相距跳數(shù)，利用式估算平均跳數(shù)的實(shí)際平均距離值。（6.8）

其中（xi,yi)，(xj,yj)是信標(biāo)節(jié)點(diǎn)I,j的坐標(biāo)，hij是信標(biāo)節(jié)點(diǎn)I,j與之間的跳數(shù)。然后，信標(biāo)節(jié)點(diǎn)將計(jì)算的每跳平均距離用帶有生存期字段的分組廣播到網(wǎng)絡(luò)中，未知節(jié)點(diǎn)僅記錄接收到的每一跳平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。這個(gè)策略確保了絕大多數(shù)節(jié)點(diǎn)從最近的信標(biāo)節(jié)點(diǎn)接收每跳平均距離值。未知節(jié)點(diǎn)接收到平均值每跳距離后，根據(jù)記錄的跳數(shù)，計(jì)算到每個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離。（2）計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳數(shù)距離（3）利用三邊測量法或極大似然估計(jì)法計(jì)算自身位置未知節(jié)點(diǎn)利用第二階段中記錄的每個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離，利用三邊測量法或極大似然估計(jì)法計(jì)算自身坐標(biāo)。如圖6-8給出了DV-Hop算法示例。經(jīng)過第一階段和第二階段，能夠計(jì)算出信標(biāo)節(jié)點(diǎn)L1、L2、L3間的實(shí)際距離和跳數(shù)，那么信標(biāo)節(jié)點(diǎn)L2計(jì)算的每跳平均距離為d=(40+75)/(2+5)=16.42m。假設(shè)未知節(jié)點(diǎn)A從L2獲得每跳平均距離，則節(jié)點(diǎn)與三個(gè)信標(biāo)節(jié)點(diǎn)之間的距離分別為：3d，2d，3d，最后利用三邊測量法計(jì)算出節(jié)點(diǎn)的坐標(biāo)。（3）利用三邊測量法或極大似然估計(jì)法計(jì)算自身位置3.DV-Distance算法DV-Distance算法類似于DV-Hop算法，它們之間的區(qū)別就在于DV-Hop算法是通過節(jié)點(diǎn)的平均每跳距離和跳數(shù)算出節(jié)點(diǎn)間的距離，而DV-Distance算法是通過節(jié)點(diǎn)間使用射頻通信來測量出節(jié)點(diǎn)間的距離，即利用RSSI來測量節(jié)點(diǎn)間的距離，然后再應(yīng)用三角測量法計(jì)算出節(jié)點(diǎn)的位置。與DV-Hop算法相比較，DV-Distance算法對傳感器節(jié)點(diǎn)的功能要求比較低，不要求節(jié)點(diǎn)能夠儲(chǔ)存網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的位置信息，同時(shí)還較大幅度地減少了節(jié)點(diǎn)間的通信量，也就降低了節(jié)點(diǎn)工作的能源消耗。不足之處在于，因?yàn)樗苯訙y量節(jié)點(diǎn)間的距離，這樣對距離的敏感性要求較高，尤其對測距的誤差很敏感，因此算法的誤差較大。3.DV-Distance算法DV-Distance算法類4.APIT算法

近似三角形內(nèi)點(diǎn)測試法（approximatepoint-intriangulationtest，APIT），首先確定多個(gè)包含未知節(jié)點(diǎn)的三角形區(qū)域，這些三角形區(qū)域的交集是一個(gè)多邊形，它確定了更小的包含未知節(jié)點(diǎn)的區(qū)域；然后計(jì)算這個(gè)多邊形區(qū)域的質(zhì)心，并將質(zhì)心作為未知節(jié)點(diǎn)的位置。未知節(jié)點(diǎn)首先收集其鄰近信標(biāo)節(jié)點(diǎn)的信息，然后從這些信標(biāo)節(jié)點(diǎn)組成的集合中任意選取三個(gè)信標(biāo)節(jié)點(diǎn)。假設(shè)集合中有個(gè)元素，那么共有種不同的選取方法，確定個(gè)不同的三角形，逐一測試未知節(jié)點(diǎn)是否位于每個(gè)三角形內(nèi)部，直到窮盡所有種組合或達(dá)到定位所需精度；最后計(jì)算包含目標(biāo)節(jié)點(diǎn)所有三角形的重疊區(qū)域，將重疊區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的位置。如圖6-9所示，陰影部分區(qū)域是包含未知節(jié)點(diǎn)的所有三角形的重疊區(qū)域，黑點(diǎn)指示的質(zhì)心位置作為未知節(jié)點(diǎn)的位置。4.APIT算法

近似三角形內(nèi)點(diǎn)測試法（approximat4.APIT算法(2)

APIT算法的理論基礎(chǔ)是最佳三角形內(nèi)點(diǎn)測試法（perfectpoint-intriangulationtest，PIT），PIT測試原理如圖6-10所示，假如存在一個(gè)方間。節(jié)點(diǎn)沿著這個(gè)方向移動(dòng)會(huì)同時(shí)遠(yuǎn)離或接近頂點(diǎn)A、B、C，那么節(jié)點(diǎn)M位于ABC外；否則，節(jié)點(diǎn)M位三角形ABC內(nèi)。在傳感網(wǎng)中，信標(biāo)節(jié)點(diǎn)通常是靜止的。為了在靜態(tài)的環(huán)境中觀察三角形內(nèi)點(diǎn)測試，提出了近似的三角形內(nèi)點(diǎn)測試法：假如在節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)里，相對于節(jié)點(diǎn)沒有同時(shí)遠(yuǎn)離或靠近三個(gè)信標(biāo)節(jié)點(diǎn)A、B、C，那么節(jié)點(diǎn)M在三角形ABC內(nèi)；否則，節(jié)點(diǎn)M在三角形ABC外。近似的三角形內(nèi)點(diǎn)測試?yán)镁W(wǎng)絡(luò)中相對較高的節(jié)點(diǎn)密度來模擬節(jié)點(diǎn)移動(dòng)，利用無線信號的傳播特性來判斷是否遠(yuǎn)離或靠近信標(biāo)節(jié)點(diǎn)。通常在給定方向上，一個(gè)節(jié)點(diǎn)離另一個(gè)節(jié)點(diǎn)越遠(yuǎn)，接收到信號的強(qiáng)度越弱。鄰居節(jié)點(diǎn)通過交換各自接收到信號的強(qiáng)度，判斷距離某一信標(biāo)節(jié)點(diǎn)的遠(yuǎn)近，從而模仿PIT中的節(jié)點(diǎn)移動(dòng)。4.APIT算法(2)

APIT算法的理論基礎(chǔ)是最佳三角形內(nèi)4.APIT算法(3)APIT定位具體步驟：（1）收集信息：未知節(jié)點(diǎn)收集鄰近信標(biāo)節(jié)點(diǎn)的信息，如位置、標(biāo)識號、接收到的信號強(qiáng)度等，鄰居節(jié)點(diǎn)之間交換各自接收到的信標(biāo)節(jié)點(diǎn)的倍息；（2）APIT測試：測試未知節(jié)點(diǎn)是否在不同的信標(biāo)節(jié)點(diǎn)組合成的三角形內(nèi)部；（3）計(jì)算重疊區(qū)域：統(tǒng)計(jì)包含未知節(jié)點(diǎn)的三角形，計(jì)算所有三角形的重疊區(qū)域；（4）計(jì)算未知節(jié)點(diǎn)位置：計(jì)算重疊區(qū)域的質(zhì)心位置，作為未知節(jié)點(diǎn)的位置。在無線信號傳播模式不規(guī)則和傳感器節(jié)點(diǎn)隨機(jī)部署的情況下，APIT算法的定位精度高，性能穩(wěn)定，但APIT測試對網(wǎng)絡(luò)的連通性提出了較高的要求。相對于計(jì)算簡單的質(zhì)心定位算法，APIT算法精度高，對信標(biāo)節(jié)點(diǎn)的分布要求低。返回4.APIT算法(3)APIT定位具體步驟：返回總結(jié)基于距離的定位機(jī)制是通過測量相鄰節(jié)點(diǎn)間的實(shí)際距離或方位來計(jì)算未知節(jié)點(diǎn)的值。通常采用測距、定位和修正等步驟?；诰嚯x的定位分為基于ToA、TDoA、AoA以及RSSI的定位等?；诰嚯x的定位機(jī)制通過實(shí)際測量節(jié)點(diǎn)間的距離或角度，通常定位精度相對較高，但對節(jié)點(diǎn)的硬件也提出了很高的要求，定位過程中消耗的能量相對多。距離無關(guān)的定位機(jī)制無需實(shí)際測量節(jié)點(diǎn)間的絕對距離或方位就能夠計(jì)算未知節(jié)點(diǎn)的位置，目前主要有質(zhì)心算法、DV-Hop算法、APIT算法等。距離無關(guān)的定位機(jī)制無需測量節(jié)點(diǎn)間的絕對距離或方位，對節(jié)點(diǎn)硬件的要求較低，使得節(jié)點(diǎn)成本更適合于大規(guī)模的傳感網(wǎng)。距離無關(guān)的定位機(jī)制定位性能受外界環(huán)境的影響小，定位誤差相應(yīng)較大，但定位精度能夠滿足多數(shù)傳感網(wǎng)使用的要求，是目前重點(diǎn)關(guān)注的定位機(jī)制?？偨Y(jié)基于距離的定位機(jī)制是通過測量相鄰節(jié)點(diǎn)間的實(shí)際距離或方位來

TheEndTheEnd無線定位技術(shù)

無線定位技術(shù)

一、引言二、節(jié)點(diǎn)定位技術(shù)基本概念三、基于距離的定位算法四、與距離無關(guān)的定位算法五、總結(jié)無線定位技術(shù)課件引言無線傳感器節(jié)點(diǎn)的位置信息對于傳感網(wǎng)來說至關(guān)重要，沒有位置信息的監(jiān)測數(shù)據(jù)往往毫無意義。在傳感網(wǎng)的各種應(yīng)用中，監(jiān)測到事件后關(guān)心的一個(gè)重要問題就是該事件發(fā)生的位置。如在環(huán)境監(jiān)測應(yīng)用中需要知道采集的環(huán)境信息所對應(yīng)的具體區(qū)域位置；對于突發(fā)事件，需要知道森林火災(zāi)現(xiàn)場位置，戰(zhàn)場上敵方車輛運(yùn)動(dòng)的區(qū)域，天然氣管道泄漏的具體地點(diǎn)等。傳感器節(jié)點(diǎn)自身定位就是根據(jù)少數(shù)已知位置的節(jié)點(diǎn)，按照某種定位機(jī)制確定自身位置。只有在傳感器節(jié)點(diǎn)自身正確定位之后，才能確定傳感器節(jié)點(diǎn)監(jiān)測到的事件發(fā)生的具體位置，這需要監(jiān)測到該事件的多個(gè)傳感器節(jié)點(diǎn)之間的相互協(xié)作，并利用它們自身的位置信息，使用特定定位機(jī)制確定事件發(fā)生的位置。引言無線傳感器節(jié)點(diǎn)的位置信息對于傳感網(wǎng)來說至關(guān)重要，沒有位置引言全球定位系統(tǒng)GPS(GlobalPositionSystem)是目前應(yīng)用最廣泛最成熟的定位系統(tǒng)，通過衛(wèi)星的授時(shí)和測距對用戶節(jié)點(diǎn)進(jìn)行定位，具有定位精度高、實(shí)時(shí)性好、抗干擾能力強(qiáng)等優(yōu)點(diǎn)，但是GPS定位適應(yīng)于無遮擋的室外環(huán)境，用戶節(jié)點(diǎn)通常能耗高體積大，成本也比較高，需要固定的基礎(chǔ)設(shè)施等，這使得不適用于低成本自組織的傳感網(wǎng)。在機(jī)器人領(lǐng)域中，機(jī)器人節(jié)點(diǎn)的移動(dòng)性和自組織等特性，其定位技術(shù)與傳感網(wǎng)的定位技術(shù)具有一定的相似性，但是機(jī)器人節(jié)點(diǎn)通常攜帶充足的能量供應(yīng)和精確的測距設(shè)備，系統(tǒng)中機(jī)器人的數(shù)量很少，所以這些機(jī)器人定位算法也不適用于傳感網(wǎng)。受到成本、功耗、擴(kuò)展性等問題的限制，為每個(gè)傳感器安裝GPS模塊等這些傳統(tǒng)定位手段并不實(shí)際，甚至在某些場合可能根本無法實(shí)現(xiàn)，因此必須采用一定的機(jī)制與算法實(shí)現(xiàn)傳感器節(jié)點(diǎn)的自身定位返回引言全球定位系統(tǒng)GPS(GlobalPositionSy節(jié)點(diǎn)定位技術(shù)基本概念1．定位的含義無線傳感網(wǎng)定位問題是指網(wǎng)絡(luò)通過特定方法提供節(jié)點(diǎn)的位置信息。其定位方式可分為節(jié)點(diǎn)自身定位和目標(biāo)定位。自身定位：是確定網(wǎng)絡(luò)節(jié)點(diǎn)的坐標(biāo)位置的過程。節(jié)點(diǎn)自身定位是網(wǎng)絡(luò)自身屬性的確定過程，可以通過人工標(biāo)定或者各種節(jié)點(diǎn)的自定位算法完成。目標(biāo)定位：是確定網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)一個(gè)事件或者一個(gè)目標(biāo)的坐標(biāo)位置。目標(biāo)定位是以位置已知的網(wǎng)絡(luò)節(jié)點(diǎn)作為參考，確定事件或者目標(biāo)在網(wǎng)絡(luò)覆蓋范圍內(nèi)所在的位置。位置信息有多種分類方法。通常有物理位置和符號位置兩大類。物理位置指目標(biāo)在特定坐標(biāo)系下的位置數(shù)值，表示目標(biāo)的相對或者絕對位置。符號位置指目標(biāo)與一個(gè)基站或者多個(gè)基站接近程度的信息，表示目標(biāo)與基站之間的連通關(guān)系，提供目標(biāo)大致的所在范圍。節(jié)點(diǎn)定位技術(shù)基本概念1．定位的含義在很多傳感網(wǎng)應(yīng)用場合中，必須知道各節(jié)點(diǎn)物理位置的坐標(biāo)信息。通過人工測量或配置來獲得節(jié)點(diǎn)坐標(biāo)的方法往往不可行。通常傳感網(wǎng)能夠通過網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)之間的相互測距和信息交換，形成一套全網(wǎng)節(jié)點(diǎn)的坐標(biāo)。這才是經(jīng)濟(jì)和可行的定位方案。從廣義上來講，無線傳感網(wǎng)的定位問題包括傳感器節(jié)點(diǎn)的自身定位和對監(jiān)控目標(biāo)的定位。目標(biāo)定位側(cè)重于傳感網(wǎng)在目標(biāo)跟蹤方面的應(yīng)用，是對監(jiān)控目標(biāo)的位置估計(jì)，它以先期的節(jié)點(diǎn)自身定位為基礎(chǔ)。從不同的角度出發(fā)，無線傳感網(wǎng)的定位方法可以進(jìn)行如下分類。（1）根據(jù)是否依靠測量距離，分為基于測距的定位和不需要測距的定位。（2）根據(jù)部署的場合不同，分為室內(nèi)定位和室外定位。（3）根據(jù)信息收集的方式，網(wǎng)絡(luò)收集傳感器數(shù)據(jù)用于節(jié)點(diǎn)定位被稱為被動(dòng)定位，節(jié)點(diǎn)主動(dòng)發(fā)出信息用于定位被稱為主動(dòng)定位。在很多傳感網(wǎng)應(yīng)用場合中，必須知道各節(jié)點(diǎn)物理位置的坐標(biāo)信息。通2．基本術(shù)語（1）信標(biāo)節(jié)點(diǎn)：指預(yù)先獲得位置坐標(biāo)的節(jié)點(diǎn)，也被稱作錨點(diǎn)。其余節(jié)點(diǎn)被稱為非錨點(diǎn)。（2）測距：指兩個(gè)相互通信的節(jié)點(diǎn)通過測量的方式來估計(jì)出彼此之間的距離或角度。（3）連接度：包括節(jié)點(diǎn)連接度和網(wǎng)絡(luò)連接度兩種含義。節(jié)點(diǎn)連接度是指節(jié)點(diǎn)可探測發(fā)現(xiàn)的鄰居節(jié)點(diǎn)個(gè)數(shù)。網(wǎng)絡(luò)連接度是所有節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目的平均值，它反映了傳感網(wǎng)節(jié)點(diǎn)配置的密集程度。（4）鄰居節(jié)點(diǎn)：傳感節(jié)點(diǎn)通信半徑以內(nèi)的所有其他節(jié)點(diǎn)，被稱為該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。（5）接收信號強(qiáng)度指示（ReceivedsignalStrengthIndicator，RSSI）：節(jié)點(diǎn)接收到無線信號的強(qiáng)度大小，被稱為接收信號的強(qiáng)度指示。（6）到達(dá)角度（AngleofArrival，AoA）：節(jié)點(diǎn)接收到的信號相對于自身軸線的角度，被稱為信號相對接收節(jié)點(diǎn)的到達(dá)角度。（7）視線關(guān)系（Lineofsight，LoS）:如果兩個(gè)節(jié)點(diǎn)之間沒有障礙物，能夠?qū)崿F(xiàn)直接通信，則稱這兩個(gè)節(jié)點(diǎn)間存在視線關(guān)系。（8）非視線關(guān)系（NoneLineofsight，NLoS）：兩個(gè)節(jié)點(diǎn)之間存在障礙物，影響了它們直接的無線通信。2．基本術(shù)語（1）信標(biāo)節(jié)點(diǎn)：指預(yù)先獲得位置坐標(biāo)的節(jié)點(diǎn)，也被稱3．定位性能的評價(jià)指標(biāo)（1）定位精度：定位精度指提供的位置信息的精確程度，它分為相對精度和絕對精度。絕對精度指以長度為單位度量的精度。例如，GPS的精度為1～10m，現(xiàn)在使用GPS導(dǎo)航系統(tǒng)的精度約5m。一些商業(yè)的室內(nèi)定位系統(tǒng)提供30cm的精度，可以用于工業(yè)環(huán)境、物流倉儲(chǔ)等場合。相對精度通常以節(jié)點(diǎn)之間距離的百分比來定義。例如，若兩個(gè)節(jié)點(diǎn)之間距離是20m，定位精度為2m，則相對定位精度為10％。由于有些定位方法的絕對精度會(huì)隨著距離的變化而變化，因而使用相對精度可以很好地表示精度指標(biāo)。設(shè)節(jié)點(diǎn)的估計(jì)坐標(biāo)與真實(shí)坐標(biāo)在二維情況下的距離差值為，則個(gè)未知位置節(jié)點(diǎn)的網(wǎng)絡(luò)平均定位誤差為。（2）覆蓋范圍：覆蓋范圍和定位精度是一對矛盾性的指標(biāo)。例如超聲波可以達(dá)到分米級精度，但是它的覆蓋范圍只有10多米；Wi-Fi和藍(lán)牙的定位精度為3米左右，覆蓋范圍可以達(dá)到100米左右；GSM系統(tǒng)能覆蓋千米級的范圍，但是精度只能達(dá)到100米。由此可見，覆蓋范圍越大，提供的精度就越低。提供大范圍內(nèi)的高精度通常是難以實(shí)現(xiàn)的。3．定位性能的評價(jià)指標(biāo)（1）定位精度：3．定位性能的評價(jià)指標(biāo)（3）刷新速度：刷新速度是指提供位置信息的頻率。例如，如果GPS每秒刷新1次，則這種頻率對于車輛導(dǎo)航已經(jīng)足夠了，能讓人體驗(yàn)到實(shí)時(shí)服務(wù)的感覺。對于移動(dòng)的物體，如果位置信息刷新較慢，就會(huì)出現(xiàn)嚴(yán)重的位置信息滯后，直觀上感覺已經(jīng)前進(jìn)了很長距離，提供的位置還是以前的位置。因此，刷新速度會(huì)影響定位系統(tǒng)實(shí)際工作提供的精度，它還會(huì)影響位置控制者的現(xiàn)場操作。如果刷新速度太低，可能會(huì)使得操作者無法實(shí)施實(shí)時(shí)控制。（4）功耗：功耗作為傳感網(wǎng)設(shè)計(jì)的一項(xiàng)重要指標(biāo)，對于定位這項(xiàng)服務(wù)功能，需要計(jì)算為此所消耗的能量。采用的定位方法不同，功耗的差別會(huì)很大，主要原因是定位算法的復(fù)雜度不同，需要為定位提供的計(jì)算和通信開銷方面存在數(shù)量上的差別，導(dǎo)致完成定位服務(wù)的功耗有所不同。（5）代價(jià)：定位系統(tǒng)或算法的代價(jià)可從幾個(gè)不同方面來評價(jià)。時(shí)間代價(jià)包括一個(gè)系統(tǒng)的安裝時(shí)間、配置時(shí)間、定位所需時(shí)間?？臻g代價(jià)包括一個(gè)定位系統(tǒng)或算法所需的基礎(chǔ)設(shè)施和網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量、硬件尺寸等。資金代價(jià)則包括實(shí)現(xiàn)一種定位系統(tǒng)或算法的基礎(chǔ)設(shè)施、節(jié)點(diǎn)設(shè)備的總費(fèi)用。返回3．定位性能的評價(jià)指標(biāo)（3）刷新速度：返回基于距離的定位算法基于測距的定位技術(shù)是通過測量節(jié)點(diǎn)之間的距離，根據(jù)幾何關(guān)系計(jì)算出網(wǎng)絡(luò)節(jié)點(diǎn)的位置。解析幾何里有多種方法可以確定一個(gè)點(diǎn)的位置。比較常用的方法是多邊定位和角度定位。這里重點(diǎn)介紹通過距離測量的方式，它可以用來計(jì)算傳感網(wǎng)中某一未知位置的節(jié)點(diǎn)坐標(biāo)?；诰嚯x的定位算法基于測距的定位技術(shù)是通過測量節(jié)點(diǎn)之間的距測距方法1．接收信號強(qiáng)度指示（RSSI）2．到達(dá)時(shí)間（ToA）3．到達(dá)時(shí)間差（TDoA）4．到達(dá)角（AoA）測距方法1．接收信號強(qiáng)度指示（RSSI）1．接收信號強(qiáng)度指示（RSSI）基于RSSI定位算法，是通過測量發(fā)送功率與接收功率，計(jì)算傳播損耗。利用理論和經(jīng)驗(yàn)?zāi)Ｐ?，將傳播損耗轉(zhuǎn)化為發(fā)送器與接收器的距離。該方法易于實(shí)現(xiàn)，無需在節(jié)點(diǎn)上安裝輔助定位設(shè)備。當(dāng)遇到非均勻傳播環(huán)境，有障礙物造成多徑反射或信號傳播模型過于粗糙時(shí)，RSSI測距精度和可靠性降低，有時(shí)測距誤差可達(dá)到50%。一般將RSSI和其他測量方法綜合運(yùn)用來進(jìn)行定位。1．接收信號強(qiáng)度指示（RSSI）基于RSSI定位算法，是通過2．到達(dá)時(shí)間（ToA）

這類方法通過測量傳輸時(shí)間來估算兩節(jié)點(diǎn)之間距離。精度較好。但由于無線信號的傳輸速度快，時(shí)間測量上的很小誤差就會(huì)導(dǎo)致很大的誤差值，所以要求傳感器節(jié)點(diǎn)有較強(qiáng)的計(jì)算能力。這兩種基于時(shí)間的測距方法適用于多種信號，如射頻、聲學(xué)、紅外和超聲波信號等。ToA機(jī)制是已知信號的傳播速度，根據(jù)信號的傳播時(shí)間來計(jì)算節(jié)點(diǎn)間的距離。如圖6-1所示為某于ToA測距的簡單實(shí)現(xiàn)過程示例，采均偽噪聲序列信號作為聲波信號，根據(jù)聲波的傳播時(shí)間來測量節(jié)點(diǎn)之間的距離。2．到達(dá)時(shí)間（ToA）

這類方法通過測量傳輸時(shí)間來估算兩節(jié)點(diǎn)2．到達(dá)時(shí)間（ToA）(2)假設(shè)兩個(gè)節(jié)點(diǎn)預(yù)先變現(xiàn)了時(shí)間同步，在發(fā)送節(jié)點(diǎn)發(fā)送偽噪聲序列信號的同時(shí)，無線傳輸模塊通過無線電同步消息通知接收節(jié)點(diǎn)偽噪聲序列信號發(fā)送的時(shí)間，接收節(jié)點(diǎn)的麥克風(fēng)模塊檢測到偽噪聲序列信號后，根據(jù)聲波信號的傳播時(shí)間和速度來計(jì)算節(jié)點(diǎn)間的距離。節(jié)點(diǎn)在計(jì)算出多個(gè)鄰近的信標(biāo)節(jié)點(diǎn)后，利用多邊測量算法和極大似然估計(jì)算法算出自身的位置。ToA采用的聲波信號進(jìn)行到達(dá)時(shí)間測量。由于聲波頻率低，速度低。對節(jié)點(diǎn)硬件的成本和復(fù)雜度的要求很低，但聲波的傳播速度易受大氣條件的影響。ToA算法的定位精度高，但要求節(jié)點(diǎn)間保持精確的時(shí)間同步，對傳感器節(jié)點(diǎn)的硬件和功耗提出了較高的要求。2．到達(dá)時(shí)間（ToA）(2)假設(shè)兩個(gè)節(jié)點(diǎn)預(yù)先變現(xiàn)了時(shí)間同步，3．到達(dá)時(shí)間差（TDoA）在基于TDoA的定位機(jī)制中，發(fā)射節(jié)點(diǎn)同時(shí)發(fā)射兩種不同傳播速度的無線信號，接收節(jié)點(diǎn)根據(jù)兩種信號到達(dá)的時(shí)間差以及這兩種信號的傳播速度計(jì)算兩個(gè)節(jié)點(diǎn)之間的距離。如圖6-2所示，發(fā)射節(jié)點(diǎn)同時(shí)發(fā)射無線射頻信號和超聲波信號，接收節(jié)點(diǎn)記錄下這兩種信號的到達(dá)時(shí)間T1、T2，巳知無線射頻信號和超聲波的傳播速度為c1、c2，那么兩點(diǎn)之間的距離為(T2-T1)S，其中S=c1c2/(c2-c1)。3．到達(dá)時(shí)間差（TDoA）在基于TDoA的定位機(jī)制中，發(fā)射節(jié)3．到達(dá)時(shí)間差（TDoA）(2)由于無線射頻信號的傳播速度要遠(yuǎn)大于超聲波的傳播速度，因而未知節(jié)點(diǎn)在收到無線射頻信號時(shí)，會(huì)同時(shí)打開超聲波信號接收機(jī)。根據(jù)兩種信號的到達(dá)時(shí)間間隔和各自的傳播速度，未知節(jié)點(diǎn)算出和該信標(biāo)節(jié)點(diǎn)之間的距離，然后通過比較到各個(gè)鄰近信標(biāo)節(jié)點(diǎn)的距離，選擇出離自身最近的信標(biāo)節(jié)點(diǎn)，從該信標(biāo)節(jié)點(diǎn)廣播的信息中取得自身的位置。TDoA技術(shù)對節(jié)點(diǎn)硬件的要求高，其對成本和功耗的要求使得該技術(shù)對低成本、低功耗的傳感網(wǎng)設(shè)計(jì)提出了挑戰(zhàn)。當(dāng)然TDoA技術(shù)的測距誤差小，具有較高精度。3．到達(dá)時(shí)間差（TDoA）(2)由于無線射頻信號的傳播速度要4．到達(dá)角（AoA）該方法通過配備特殊天線來估測其他節(jié)點(diǎn)發(fā)射的無線信號的到達(dá)角度。它的硬件要求較高，每個(gè)節(jié)點(diǎn)要安裝昂貴的天線陣列和超聲波接收器。在基于AoA的定位機(jī)制中，接收節(jié)點(diǎn)通過天線陣列或多個(gè)超聲波接收機(jī)，來感知發(fā)射節(jié)點(diǎn)信號的到達(dá)方向，計(jì)算接收節(jié)點(diǎn)和發(fā)射節(jié)點(diǎn)之間的相對方位和角度，再通過三角測量法計(jì)算節(jié)點(diǎn)的位置。如圖6-3所示，接收節(jié)點(diǎn)通過麥克風(fēng)陣列，探測發(fā)射節(jié)點(diǎn)信號的到達(dá)方向。AoA定位不僅能夠確定節(jié)點(diǎn)的坐標(biāo)，還能夠確定節(jié)點(diǎn)的方位信息。但是AoA測距技術(shù)易受外界環(huán)境影響，且需要額外硬件，因此它的硬件尺寸和功耗指標(biāo)并不適用于大規(guī)模的傳感網(wǎng)。4．到達(dá)角（AoA）該方法通過配備特殊天線來估測其他節(jié)點(diǎn)發(fā)射節(jié)點(diǎn)定位計(jì)算方法在傳感器節(jié)點(diǎn)定位過程中，未知節(jié)點(diǎn)在獲得對于鄰近信標(biāo)節(jié)點(diǎn)的距離，或獲得鄰近的信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的相對角度后，通常使用下列方法計(jì)算自己的坐標(biāo)。（1）三邊測量法（2）三角測量法（3）極大似然估計(jì)法節(jié)點(diǎn)定位計(jì)算方法在傳感器節(jié)點(diǎn)定位過程中，未知節(jié)點(diǎn)在獲得對于（1）三邊測量法

三邊測量法（trilateration）如圖6-4所示，已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(xa,ya)、(xb,yb)、(xc,yc)，以及它們到未知節(jié)點(diǎn)D的距離分別為da、db、dc，假設(shè)節(jié)點(diǎn)D的坐標(biāo)為(x,y)。那么存在下列公式：可以得到節(jié)點(diǎn)D的坐標(biāo)為（1）三邊測量法

三邊測量法（trilateration）如（2）三角測量法三角測量法(triangulation)原理如圖6-5所示，已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(xa,ya)、(xb,yb)、(xc,yc)，節(jié)點(diǎn)D相對于節(jié)點(diǎn)A、B、C的角度分別為∠ADB、∠ADC

、∠BDC

，假設(shè)節(jié)點(diǎn)D的坐標(biāo)為(x,y)。對于節(jié)點(diǎn)A、C和角∠ADC

，如果弧段AC在△ABC內(nèi)，那么能夠惟一確定一個(gè)圓，設(shè)圓心為O1(xo1,yo1)，半徑為r1，那么角α=∠AO1C=2π-2∠ADC，并存在下列公式：由式（6.3）能夠確定圓心點(diǎn)的坐標(biāo)和半徑。同理對A、B、∠

ADB和B、C、∠

BDC分別確定相應(yīng)的圓心、半徑。最后利用三邊測量法，由三個(gè)圓心點(diǎn)及其半徑確定D點(diǎn)坐標(biāo)。（2）三角測量法三角測量法(triangulation)原理（3）極大似然估計(jì)法

極大似然估計(jì)法(maximumlikelihoodestimation，MLE)如圖2.4所示，己知1、2、3等個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(x1,y1)、(x2,y2)、…、(xn,yn)，它們到未知節(jié)點(diǎn)的距離分別為d1、d2、、…、dn，假設(shè)未知節(jié)點(diǎn)的坐標(biāo)為(x,y)。有公式：解方程得：其中：返回（3）極大似然估計(jì)法

極大似然估計(jì)法(maximumlik與距離無關(guān)的定位算法

與距離無關(guān)的定位技術(shù)不需要直接測量距離和角度信息。它不是通過測量節(jié)點(diǎn)之間的距離來定位的，而是僅根據(jù)網(wǎng)絡(luò)的連通性確定網(wǎng)絡(luò)中節(jié)點(diǎn)之間的跳數(shù)，同時(shí)根據(jù)已知位置的參考節(jié)點(diǎn)的坐標(biāo)等信息估計(jì)出每一跳的大致距離，然后估計(jì)出節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置。與距離無關(guān)的定位算法無須測量節(jié)點(diǎn)間的絕對距離或方位，降低了對節(jié)點(diǎn)硬件的要求。目前主要有兩類距離無關(guān)的定位方法：一類是先對未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)之間的距離進(jìn)行估計(jì)，然后利用多邊定位等方法完成對其他節(jié)點(diǎn)的定位；另一類是通過鄰居節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)來確定包含未知節(jié)點(diǎn)的區(qū)域，然后將這個(gè)區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)。距離無關(guān)的定位方法精度低，但能滿足大多數(shù)應(yīng)用的要求。距離無關(guān)的定位算法主要有質(zhì)心算法、DV-Hop算法、Amorphous算法、APIT算法等。與距離無關(guān)的定位算法

與距離無關(guān)的定位技術(shù)不需要直接測量距離1．質(zhì)心算法在計(jì)算幾何學(xué)里，多邊形的幾何中心被稱為質(zhì)心，多邊形頂點(diǎn)坐標(biāo)的平均值就是質(zhì)心節(jié)點(diǎn)的坐標(biāo)。假設(shè)多邊形頂點(diǎn)位置的坐標(biāo)向量表示為，則這個(gè)多邊形的質(zhì)心坐標(biāo)計(jì)算方法如下。這種方法的計(jì)算與實(shí)現(xiàn)都非常簡單，可以根據(jù)網(wǎng)絡(luò)的連通性確定信標(biāo)節(jié)點(diǎn)周圍的信標(biāo)參考節(jié)點(diǎn)，直接求解信標(biāo)參考節(jié)點(diǎn)構(gòu)成的多邊形的質(zhì)心。在傳感網(wǎng)的質(zhì)心定位系統(tǒng)的實(shí)現(xiàn)中，信標(biāo)節(jié)點(diǎn)周期性地向鄰近節(jié)點(diǎn)廣播分組信息，該信息包含了信標(biāo)節(jié)點(diǎn)的標(biāo)識和位置。在未知節(jié)點(diǎn)接收到來自不同信標(biāo)節(jié)點(diǎn)的分組信息數(shù)量超過某一門限或在接收了一定時(shí)間之后，就可以計(jì)算這些信標(biāo)節(jié)點(diǎn)所組成的多邊形的質(zhì)心，并以此確定自身位置。質(zhì)心定位算法雖然實(shí)現(xiàn)簡單、通信開銷小，但僅能實(shí)現(xiàn)粗精度定位，并且需要信標(biāo)節(jié)點(diǎn)具有較高的密度，各信標(biāo)節(jié)點(diǎn)部署的位置也對定位效果有影響。1．質(zhì)心算法在計(jì)算幾何學(xué)里，多邊形的幾何中心被稱為質(zhì)心，多邊2．DV-Hop算法距離向量-跳數(shù)（distancevector-hop，DV-Hop）算法定位機(jī)制非常類似于傳統(tǒng)網(wǎng)絡(luò)中的距離向量路由機(jī)制。在距離向量定位機(jī)制中，未知節(jié)點(diǎn)首先計(jì)算與信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，然后估算平均跳數(shù)的距離，利用最小跳數(shù)乘以平均每跳距離，得到未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的估計(jì)距離，再利用三邊測量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。DV-Hop算法的定位過程分為以下三個(gè)階段：（1）計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的最小跳數(shù)信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身的位置信息的分組，其中包括跳數(shù)字段，初始化為0。接收節(jié)點(diǎn)記錄具有到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，忽略來自同一個(gè)信標(biāo)節(jié)點(diǎn)的最大跳數(shù)的分組。然后將跳數(shù)值加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。通過這種方法，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)能夠記錄下到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。如圖6-7所示，信標(biāo)節(jié)點(diǎn)A廣播的分組以近似于同心圓的方式在網(wǎng)絡(luò)中逐次傳播，圖中的數(shù)字代表距離信標(biāo)節(jié)點(diǎn)A的跳數(shù)。2．DV-Hop算法距離向量-跳數(shù)（distancevec圖6-7信標(biāo)節(jié)點(diǎn)廣播分組傳播過程圖示圖6-7信標(biāo)節(jié)點(diǎn)廣播分組傳播過程圖示（2）計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳數(shù)距離每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)第一個(gè)階段記錄的其他信標(biāo)節(jié)點(diǎn)的位置信息和相距跳數(shù)，利用式估算平均跳數(shù)的實(shí)際平均距離值。（6.8）

其中（xi,yi)，(xj,yj)是信標(biāo)節(jié)點(diǎn)I,j的坐標(biāo)，hij是信標(biāo)節(jié)點(diǎn)I,j與之間的跳數(shù)。然后，信標(biāo)節(jié)點(diǎn)將計(jì)算的每跳平均距離用帶有生存期字段的分組廣播到網(wǎng)絡(luò)中，未知節(jié)點(diǎn)僅記錄接收到的每一跳平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。這個(gè)策略確保了絕大多數(shù)節(jié)點(diǎn)從最近的信標(biāo)節(jié)點(diǎn)接收每跳平均距離值。未知節(jié)點(diǎn)接收到平均值每跳距離后，根據(jù)記錄的跳數(shù)，計(jì)算到每個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離。（2）計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳數(shù)距離（3）利用三邊測量法或極大似然估計(jì)法計(jì)算自身位置未知節(jié)點(diǎn)利用第二階段中記錄的每個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離，利用三邊測量法或極大似然估計(jì)法計(jì)算自身坐標(biāo)。如圖6-8給出了DV-Hop算法示例。經(jīng)過第一階段和第二階段，能夠計(jì)算出信標(biāo)節(jié)點(diǎn)L1、L2、L3間的實(shí)際距離和跳數(shù)，那么信標(biāo)節(jié)點(diǎn)L2計(jì)算的每跳平均距離為d=(40+75)/(2+5)=16.42m。假設(shè)未知節(jié)點(diǎn)A從L2獲得每跳平均距離，則節(jié)點(diǎn)與三個(gè)信標(biāo)節(jié)點(diǎn)之間的距離分別為：3d，2d，3d，最后利用三邊測量法計(jì)算出節(jié)點(diǎn)的坐標(biāo)。（3）利用三邊測量法或極大似然估計(jì)法計(jì)算自身位置3.DV-Distance算法DV