【文章內容簡介】 個參考節(jié)點的距離分別是r１、r２、r３。有方程組如下： （） 解得M的位置坐標為： （）三邊測量法相比較其他定位計算方法來說，算法的復雜度較低，由于基于測距技術，實現(xiàn)起來也比較容易，不需要附加額外的硬件設備。但是在三邊測量法中，不能保證三個圓一定交于一點，導致無法得到正確的解，產生定位誤差。三角測量法三角測量法是根據三角形的幾何關系進行位置估算。前提是已知參考節(jié)點數(shù)，可進行“點在三角形中”的測試，即任意選取三個參考節(jié)點組成三角形，以測試節(jié)點是否落在該三角形內。根據測試結果的交集，大致確定節(jié)點位置。因此測試次數(shù)越多，位置估算的精度越高。三角測量法也可結合角度測量，即通過方向性天線，利用 AOA 測量的角度值來定位。確定二維坐標分別需要一個距離和角度值；確定三維位置則需兩個角度、一個距離和方位角，方位角是在水平方向上從正北開始順時針旋轉的角度。該計算方法需要附加額外的硬件設備來測量角度值，增加了無線傳感器網絡系統(tǒng)的成本。最大似然估計法極大似然估計法實際上就是多邊測量法，它是以三邊測量法為基礎得出的一種計算方法。P1P2P3P4MPn 極大似然估計法示例 如圖所示，未知節(jié)點M到n（n＞3）個參考節(jié)點P１、P２、P３。Pｎ的距離分別為d１，d２，d３．．．．．．dｎ，已知n個參考節(jié)點的坐標分別為P１（x１，y１），P２（x２，y２），P３（x３，y３）．．．．．．Pｎ（xｎ，yｎ），那么可以得到以下方程組： （）用線性方程表示為Ax=b，其中： （）用最小二乘法公式就可以得到未知節(jié)點的P的坐標為：?。ǎ┳畲笏迫还烙嫹ㄏ鄬τ谌厹y量法來說，雖然提高了定位的精度，但是另一方面也大大的增加的算法的復雜度，這對于微型的傳感器的低功耗來說是非常不利。 節(jié)點定位算法的分類基于距離的定位算法和非基于距離的定位算法最常見的定位機制就是基于距離和非基于距離的定位算法。前者根據節(jié)點間的距離信息，結合幾何學原理，解算節(jié)點位置；后者則利用節(jié)點間的鄰近關系和網絡連通性進行定位。通過物理測量獲得節(jié)點之間的距離或連接有向線段的夾角信息來對節(jié)點進行定位的算法，是基于測距的定位算法。不是通過周邊參考節(jié)點的測距，而是利用節(jié)點的連通性和多條路由信息交換來對節(jié)點進行定位的算法就是非基于距離的定位算法?；跍y距的定位算法定位精度高，但對于硬件設備的費用支出和相關的功耗較大；總的來講，非基于距離定位算法實施的成本較低?；谛艠斯?jié)點的定位算法和無信標節(jié)點的定位算法如果使用了信標節(jié)點及信標節(jié)點數(shù)據的定位算法叫基于信標節(jié)點的定位算法，否則就是無信標節(jié)點的定位算法?；谛艠斯?jié)點的定位算法以信標節(jié)點為參考點，通過定位后，完成了絕對坐標系中坐標描述；無信標節(jié)點的定位算法無需其他節(jié)點的絕對坐標數(shù)據信息，只依靠節(jié)點的相對位置關系確定待定位節(jié)點的位置，這樣所得出的位置信息是在相對坐標系中進行的，定位數(shù)據也是在相對坐標系中描述的。物理定位算法和符號定位算法通過定位后得到傳感器節(jié)點的物理位置的算法是物理定位算法，如獲得節(jié)點的三維坐標和方位角等；若通過定位后得到傳感器節(jié)點的符號位置的算法就是符號定位算法，如獲得節(jié)點的定位信息是傳感器節(jié)點位于建筑物中的多少號房間。有些應用場合適合使用符號定位算法，如建筑物特定火情監(jiān)測區(qū)域中，火災傳感器的分布，使用符號定位算法就很方便；大多數(shù)定位算法都能提供物理定位信息。遞增式的定位算法和并發(fā)式的定位算法　　在定位的過程中，首先是從信標節(jié)點開始，對與信標節(jié)點相鄰的節(jié)點進行定位，再逐漸地向遠離信標節(jié)點的位置對節(jié)點進行定位，這種定位算法就是遞增式的定位算法。遞增式定位算法會產生較大的累積誤差。如果同時性地處理節(jié)點定位信息則是并發(fā)式的定位算法。 基于距離的定位算法基于AOA的APS算法基于AOA的幾點定位技術稱為到達角交匯定位（AOA，Angle of Arrival）技術。該技術在兩個以上的位置點設置方向性天線或陣列天線，獲取節(jié)點發(fā)射的無線電波角度，通過陣列天線或多個接收器結合確定相鄰節(jié)點發(fā)送信號的方向，從而構成一根從接收機到發(fā)射機的方位線，兩根方位線的交點即為待定位節(jié)點的位置，待定位節(jié)點得到與參考節(jié)點1和參考節(jié)點2所構成的角度之后，通過交匯法確定自身位置。另外，AOA信息還可以與其他一些信息一起使用，形成定位精度更高的混合定位法。AOA定位法使用的硬件系統(tǒng)設備較為復雜。 節(jié)點1節(jié)點2未知節(jié)點3 AOA算法示例基于AOA的APS（Ad Hoc Positioning System）算法，利用兩個能感知方向信息和距離信息的接收器（如超聲波接收器），量測不同節(jié)點之間的角度信息通過這些角度信息以及它們之間的幾何關系來對未知幾點定位。一般情況下，待定位節(jié)點的相鄰節(jié)點不都是信標節(jié)點，因此，待定位節(jié)點就不能與信標節(jié)點通信獲取兩者之間的方向角?；贏OA的APS算法使用了方位轉發(fā)的方法解決待定位節(jié)點的定位問題。基于TOA的定位通過掌握已知信號的傳播速度，根據信號的傳播時間來計算傳感器節(jié)點間的距離，對未知節(jié)點進行定位的算法稱為基于TOA（time of arrival）的定位算法。測距、利用節(jié)點之間的幾何關系實現(xiàn)傳感器網絡中未知節(jié)點自定位算法。該方法計算量小、算法簡單，且定位精度高。無線收發(fā)模式微處理器聲波射束發(fā)射模塊無線收發(fā)模塊微處理器聲波射束接收模塊 一個使用聲波發(fā)送和接收進行測距定位的裝置節(jié)點1通過聲波射束發(fā)射模塊發(fā)出聲波射束，節(jié)點2接收到聲波射束，已知聲波射束的傳輸速度和從發(fā)射到接收所用時間（即聲波射束的傳播時間）,兩個節(jié)點間的距離就已經測出。該裝置中，無線收發(fā)模塊進行信號發(fā)送的同步，目的是為聲波射束的發(fā)送和接收提供計時的起始和終止時間。節(jié)點在計算出相鄰的多個信標節(jié)點和自己的距離后，通過幾何關系就可以對自身進行定位?；赥OA（time of arrival）的定位算法精度高，但要求發(fā)送測距信號的和接收測距信號的節(jié)點之間保持精確的時間同步，所以傳感器節(jié)點的功耗較大以及對硬件要求較高?；赥DOA的定位算法之一的AHLos算法基于TDOA的定位算法是指“到達時間差定位（TDOA，Time difference of Arrival）算法”。在這種定位機制中，向外發(fā)送無線信號的發(fā)送節(jié)點同時向接收節(jié)點發(fā)送兩種傳播速率不同的無線信號波束，接收節(jié)點根據兩種信號到達的時間差以及兩個不同的傳播速率，就可以計算發(fā)送節(jié)點到接收節(jié)點之間的距離，再通過一定的定位算法解算出節(jié)點的位置信息。基于TDOA的定位算法之一的AHLos(Ad Hoc Localization System)算法是一個迭代的定位算法。該算法的起始階段，信標節(jié)點對外廣播自身的位置信息，待定位節(jié)點測量與相鄰的信標節(jié)點之間的距離并收獲知信標節(jié)點的未知信息。在信標節(jié)點的數(shù)量是3個或3個以上，就使用最大似然估計節(jié)點位置計算法來計算待定位節(jié)點的位置信息。如果待定位節(jié)點的位置信息已經解算出來，該節(jié)點就轉化為信標節(jié)點，開始向外廣播自身的位置信息，因此傳感器網絡中信標節(jié)點的數(shù)量隨著定位算法定位和完成，逐漸在增多。根據傳感器網絡中待定位節(jié)點周圍信標節(jié)點的分布情況不同，AHLos算法定義了三種不同的子算法。（1）原子多邊算法當待定位節(jié)點相鄰的信標節(jié)點數(shù)為3個或3個以上時，使用最大似然估計法這里也叫原子多邊算法。這里所講的信標節(jié)點數(shù)是指傳感器網絡部署完畢后初始的情況，即還沒有執(zhí)行過定位算法之前的情況，因為只要執(zhí)行了定位算法，一部分待定位節(jié)點就可能轉化成了信標節(jié)點。（2）迭代多邊算法當待定位節(jié)點相鄰的信標節(jié)點數(shù)小于3個小時，與之相鄰的信標節(jié)點通過廣播自身的位置信息并被待定位節(jié)點知悉，經過這些信息運算處理后，確定了自身的位置，也成為信標節(jié)點。當未知節(jié)點的相鄰信標節(jié)點的數(shù)量達到3個或3個以上時，使用最大似然估計法完成未知節(jié)點的定位算法。（3）協(xié)作多邊算法無線傳感器網絡中的傳感器節(jié)點部署在很多應用場合中是隨機的，而且信標節(jié)點的數(shù)量也很少，這種情況下如果要使用信標節(jié)點的信息來對未知節(jié)點進行定位，就無法使用原子多邊算法或迭代多邊算法。協(xié)作多邊算法為：經過多次迭代定位后，待定位節(jié)點的鄰居節(jié)點數(shù)量仍然不足3個，此時要依托多跳的局部信息（即通過其他節(jié)點的協(xié)助）來計算自身的位置。基于RSSI的定位算法接收信號強度指示(RSSI)測距技術是一種常用的測距技術，因為其應用非常簡單，只需要在無線傳感器芯片中添加一個接收信號強度指示器就可以完成測距的功能，而這個接收信號強度指示器又非常的廉價一般的無線設備都配有這個功能，這樣就不需要消耗電能和增加傳感器的大小或者花費。所以在無線傳感器網絡節(jié)點定位領域中，該技術比起其他的測距技術來說，有較廣的應用范圍和應用前景。RSSI 測距技術是接收端通過測量射頻端信號的能量來確定與傳輸端之間的距離。在自由空間中，在各項條件都相同的情況下，RSSI 變化與接收端和傳輸端之間距離的平方成反比。我們設定接收功率為 Pr(d)，接收功率 Pr(d)可以被距離 d 通過路徑損耗公式得出，如以下公式所示，Pt 是發(fā)送功率，Gt 為發(fā)送天線增益，Gr 接收天線增益， λ為傳輸信號的波長。 （）自由空間路徑損耗模型只是一個理論公式，在實際的應用中信號的傳播受反射，衍射和散射的影響，當然環(huán)境因素包括建筑物，天氣，室內或者室外的不同也會給信號的傳播造成不同的影響。所以就提出一種經驗公式，在該經驗公式中，無論這些影響因素是反射、衍射還是散射等，都可以計算出 RSSI 的值。該經驗公式通過附加一個隨機的對數(shù)正態(tài)值來代替所有的干擾項。如以下公式： （）其中，P0(d0)是一個已知的功率參數(shù)，以 dBm 為單位。該參數(shù)為傳輸距離為 d0時的接收功率。np為路徑損耗指數(shù)， Xσ為一個零平均值的高斯隨機值，標準差為σ，用它來代表隨機的環(huán)境或者傳播影響?；赗SSI的定位算法的定位過程描述如下：步驟1：錨節(jié)點向網絡中周期性地廣播自身信息信標,信標中包含錨節(jié)點的節(jié)點ID和自身位置信息；步驟2：未知節(jié)點接收到鄰居錨節(jié)點的信標和RSSI測量值，然后根據信道傳播模型計算到相應錨節(jié)點的距離；步驟3：未知節(jié)點如果總共接收到3個或以上的不同錯節(jié)點的信息，利用三邊測量法或最大似然估計法計算未知節(jié)點的位置。：錨節(jié)點廣播自身信息信標開始未知節(jié)點接收鄰居節(jié)點信標、RSSI值接收到的鄰居錨節(jié)點數(shù)量=3利用信道模型轉換RSSI值為距離三邊測量法或最大似然法計算估計坐標終止no接收到的鄰居錨節(jié)點數(shù)量=3yes RSSI算法流程圖 與距離無關的定位算法 質心算法質心算法是美國學者提出的一種僅基于網絡連通性的室外定位算法，該算法的中心思想是待定位節(jié)點以所有在其通信范圍內的信標節(jié)點的幾何質心作為自己的位置坐標估計值。 平面上一個多邊形的質心是指它的幾何中心，多邊形的質心坐標就是多邊行各頂點的坐標平均值。如圖所示，一個多邊形ABCDEF各點的坐標分別為A（xa,ya）、B(xb,yb)、C(xc,yc)、D(xd,yd)、E(xe,ye)和F(xf,yf),則質心的坐標P(x,y)為： （） （）實際應用中，各傳感器節(jié)點的布置位置相當于多邊形的頂點，計算出該多邊形的質心作為待定位節(jié)點的位置。 在監(jiān)測區(qū)域中部署無線傳感器網絡后，信標節(jié)點向相鄰的節(jié)點周期性地廣播自身的信息，消息中包含信標節(jié)點的標識編碼和位置數(shù)據。相鄰的非信標節(jié)點接收到信標節(jié)點的消息后，進行累計，一旦接收到不同信標節(jié)點的消息達到一個設定閾值時，就確定這些已知信標節(jié)點位置數(shù)據中的坐標值作為質心算法中的多邊形的諸頂點坐標數(shù)據，參與計算。質心算法完全基于傳感器網絡的連通性進行定位，實現(xiàn)過程較為簡單，計算量小，不需要網絡中各節(jié)點的較復雜的協(xié)調，擴展性好。但該算法的定位精度不高，盡管如此，也能夠滿足對傳感器相對位置數(shù)據信息精度要有不高的場合應用。P（x,y）ABCDEF 質心算法示例2 、DVHop算法該算法是基于距離矢量計算跳數(shù)的算法。該算法的基本思想是，將待定位節(jié)點到信標節(jié)點之間的距離用網絡中節(jié)點平均每跳距離和到信標節(jié)點間的跳數(shù)乘積來標識，再使用三邊測量法和最大似然估計法來獲得將待定位節(jié)點的位置信息。第一個階段：計算待定位節(jié)點與每個信標節(jié)點之間的最小跳數(shù)。第二個階段：計算每一個信標節(jié)點與其他信標節(jié)點的實際跳段距離。第三個階段：完成待定位節(jié)點的位置估計。待定位節(jié)點利用第二個階段獲取的網絡中每一個信標節(jié)點與其他信標節(jié)點的實際跳段距離的數(shù)據，使用三邊測量法和最大似然估計法來估計待定位節(jié)點的位置信息。DVHop算法的優(yōu)點是比較簡單，無需進行節(jié)點之間的距離測量，可以避免測量時帶來的誤差，傳感器節(jié)點不需要其他的附加硬件支持，是無線傳感器網絡節(jié)點定位的一個較經濟可行的方案。但是這種算法有一些值得改進的地方：在獲得平均每跳的計算過程中，節(jié)點之間通信量較大，而且沒有考慮網絡中存在不良節(jié)點的影響，造成平均定位誤差較大。DVDistance算法DVdistance算法類似于DVHop算法，它們之間的區(qū)別在于，DVHop算法是通過節(jié)點的平均每跳距離和跳數(shù)算出節(jié)點間的距離，而DVdistance算法是通過節(jié)點間使用射頻通信來測量出節(jié)點間的距離，即使用RSSI測量節(jié)點間點到點距離,然后利用距離矢量路由的方法傳播與鋪節(jié)點的累計距離