無線感測器網路中的節點定位技術解析
無線感測器網路的許多應用要求節點知道自身的位置資訊，才能向用戶提供有用的檢測服務。沒有節點位置資訊的監測資料在很多場合下是沒有意義的。比如，對於森林火災檢測、天然氣管道監測等應用，當有事件發生時，人們關心的一個首要問題就是事件發生在哪裡，此時如果只知道發生了火災卻不知道火災具體的發生地點，這種監測沒有任何實質的意義，因此節點的位置資訊對於很多場合是至關重要的。
操作方法
（01）在許多場合下，感測器節點被隨機部署在某個區域，節點事先無法知道自身的位置，因此需要在部署後通過定位技術來獲取自身的位置資訊。目前最常見的定位技術就是GPS（Global Positioning System）了，它能夠通過衛星對節點進行定位，並且能夠達到比較高的精度。因此要想對感測器節點進行定位，最容易想到的方法就是給每個節點配備一個GPS接收器，但是這種方法不適用於感測器網路，主要原因有以下幾點：1）GPS接收器通常能耗高，而對於無線感測器網路中的節點來說，一般能耗很有限，給每個節點配備一個GPS接收器會大大縮短網路壽命；2）GPS接收器成本比較高，給無線感測器網路中的每個節點配備一個GPS接收器，需要投入很大成本，尤其對於大規模的無線感測器網路來說不是很適合；因此有必要研究適合無線感測器網路的定位技術。下面分兩個部分來介紹節點定位的相關研究：1）節點定位的基本概念；2）節點定位的基本思路；3）常見演算法。
節點定位的基本概念
（01）無線感測器網路中的節點定位是指感測器節點根據網路中少數已知節點的位置資訊，通過一定的定位技術確定網路中其他節點的位置資訊的過程。在無線感測器網路中節點通常可以分為信標節點（beacon node or anchor node）和未知節點（unknown node），其中信標節點也稱為錨節點或者參考點，未知節點也稱為普通節點。信標節點是位置資訊已知的節點，未知節點是未知資訊未知的節點。信標節點一般所佔比例很小，通常通過手工配置或者配備GPS接收器來獲取自身的位置資訊。除此之外還有一種節點稱為鄰居節點（neighbor node），鄰居節點是指感測器節點通訊半徑內的其他節點。以下是幾個常用術語：到達時間（Time of Arrvial，TOA），訊號從一個節點傳播到另一個節點所需時間到達時間差（Time Diffrential of Arrival，TDOA），不同傳播速度的訊號從一個節點到達另一個基點所需要的時間之差到達角度（Angle of Arrival，AOA），節點接收到的訊號相對於自身軸線的角度接收訊號強度（Received Sinnal Strength，RSS），節點接收到無限訊號強度的大小，也有稱Received Sinnal Strength Indicator（RRSI），兩個意思基本是一樣的視距關係（Light of Sight，LOS），兩個節點之間沒有障礙物，能夠直接通訊非視距關係（Non Light of Sight，NLOS），兩個節點之間有障礙物，不能直接通訊跳數（Hop Count），兩個節點之間的跳段之和
節點定位技術的基本思路
（01）節點定位的基本思路主要有兩種：1.基於測距（Range-based）：假設在感測器網路中某些節點位置資訊已知，通過某些手段來估算其他節點的位置資訊。在這裡面通常有兩個步驟：測距位置估算因為要通過信標節點得到未知節點的位置資訊，必須先確定信標節點到未知節點的距離，才能得到未知節點的位置資訊。舉個例子說明一下：
（02）假如信標節點A位置已知為（x1，y1），節點M位置未知，要想求得M的位置，最簡單的想法：假設B位置為（x，y），A到B的距離為d1，則有d12=（x-x1）2+（y-y1）2顯然只根據一個方程這樣是無法求得x和y的值，假若有兩個信標節點呢？
（03）這樣一來的話又多了一個方程：d22=（x-x2）2+（y-y2）2，此時可以解得方程組得到x和y，但是此時x和y是有兩組解的，無法唯一確定x和y的值，因此需要考慮再假如一個信標節點：
（04）這樣一來的話就可以唯一確定x和y的值了，最基本的定位思想就是這樣。這裡舉的例子是採用距離，還可以採用角度。一般情況最少需要知道未知節點和信標節點的三組距離或角度值，然後再通過位置估算方法確定位置。通常測距的方法有4種：1）基於到達時間（TOA）的測距這種方法是根據已知訊號的傳播速度及訊號在傳送節點和接收節點之間的傳播時間來估算距離，這種方法要求能夠非常精確地獲取傳送節點和接收節點之間的傳播時延，這個是比較困難的，難度很大，不太適合無線感測器網路。2）基於到達時間差（TDOA）的測距這種方法中傳送節點同時傳送兩種不同傳播速度的訊號、接收節點根據兩種訊號到達的時間差和他們的傳播速度來計算距離。假若兩種訊號的傳寶速度為v1和v2，到達時間分別為t1和t2，傳送節點到接收節點的距離為d，則有：t1-t2=d/v1-d/v2可得d=（t1-t2）v1v2/（v2-v1）3）基於到達角度（AOA）的測距這種方法根據接收訊號到達時候與自身軸線的角度來計算，這種方法對硬體成本要求很高，要求配備天線陣列，不太適合無線感測器網路4）基於接收訊號強度（RSS）的測距訊號在傳播過程中會有衰減，無線訊號的發射功率和接收功率存在某種對映關係，因此可以利用關係這個來估算距離，在獲得了距離之後，就可以來估算位置了，常用的位置估算方法有下面兩種：1）三邊測量法上面舉的例子中的位置估算方法就是三邊測量法，此處不再贅述。至於某些文獻上提到的三角測量法個人覺得跟三邊測量法是一回事，就不再介紹了。3）最大似然估計法已知n個節點的座標為（x1，y1），（x2，y2）......（xn，yn），它們到未知節點M的距離分別為d1，，則有：（x-x1）2+（y-y1）2=d12（x-x2）2+（y-y2）2=d22......（x-xn）2+（y-yn）2=dn2依次用第一個方程減去最後一個方程，可得：x12-xn2+y12-yn2+dn2-d12=2x(x1-xn)+2y(y1-yn)-12-xn2+yn-12+dn2-dn-12=2x(xn-1-xn)+2y(yn-1-yn)則可以表示成 AX = B
（05）2.無需測距（range-free）無需測距的方法一般是利用網路連通性或者拓撲結構來估算距離，再利用三邊測量法或者極大似然估計來估算位置。
常見演算法
（01）1.基於測距（range-based）1）AHLos 演算法該演算法是基於到達時間差的測距，信標節點首先向鄰居節點以兩種射頻訊號來廣播訊息，然後鄰居節點根據到達時間差來估算距離，在接收到三個信標節點的訊息之後，則根據三邊測量法估算位置，鄰居節點確定自己的位置之後轉變為信標節點，也向鄰近節點廣播訊息重複上述過程直至所有節點定位完成。2）RADAR演算法該演算法是基於RSS的測距，而基於RSS測距該演算法有兩種模型：經驗模型和訊號傳播模型先說一下經驗模型：
（02）在經驗模型中，節點被分散在一定的區域內，並且保證所有的未知節點能夠與信標節點直接通訊，如圖所示。然後事先在該區域內採集一些位置進行RSS強度測試，並以（x，y，RSS）的形式記錄到資料庫中。當進行定位時，未知節點同資料庫中的資料進行比對，選擇差值最小的三個或者三個以上點作為估算位置，然後再採用三邊測量法或者下文的質心法來估算位置。訊號傳播模型：訊號傳播模型主要有兩種模型：自由空間模型和shadowing模型自由空間模型假定訊號發射功率和訊號接收功率存在確定的對映關係：
（03）其中PR是接收處的功率，PS是發射處的功率，d是發射點距接收點的距離，α是傳播因子，視環境而定。shadowing模型：
（04）其中P（d）是未知節點處的訊號強度或者訊號發射功率，P（d0）是距信標節點或者基站d0處的訊號發射功率（其中d0是參考距離，一般取1m），n是衰減因子，由於實際環境中存在噪聲，所以引入了ß，比如在室內傳播，會有牆壁或者門這些障礙物，就需要計算ß。2.無需測距（range-free）無需測距的定位演算法不需要直接測量節點之間的距離或者角度，而是根據網路的連通性來實現位置估計得，典型的無需測距的演算法主要有以下幾種：1）質心演算法質心演算法基於兩個假設條件：射頻訊號的傳播遵循理想的圓球模型；節點的通訊半徑相同且不會改變。該演算法利用了計算幾何中質心的思想，假設n邊形的頂點座標分別為（x1，y1）......（xn，yn），設其質心座標為（x，y），則有x=（x1+x2....+xn）/ ny=（y1+y2+....+yn）/ n演算法核心思想為：信標節點週期性地廣播包含自身位置資訊的訊息，在時間t內未知節點收到來自信標節點i的訊息數目為Nr（i，t），而時間t內信標節點i發出的訊息數目為Ns（i，t），那麼未知節點和信標節點的連通指標為：C=Nr（i，t）/ Ns（i，t）如果C大於設定的閾值，則認為未知節點處於信標節點i的覆蓋區域內，即與信標節點i連通。這樣對於每個未知節點都可以選出與其連通的所有信標節點，然後把這些信標節點的質心作為該未知節點的座標。質心演算法是一種完全基於網路連通性的定位演算法，其計算和實施難度都比較小，但是演算法精度不高，並且通常要求信標節點具有較高的密度。2）DV-HOP（Distance Vector-Hop）演算法DV-HOP演算法是為了避免對節點距離直接測量而提出的一種基於向量路由的非測距定位演算法。該演算法的核心思想是通過距離向量路由方法獲取未知節點與信標節點之間的最小跳數，並計算每跳的平均距離，然後以每跳的平均距離與最小跳數的乘積作為未知節點與信標節點的估算距離，再使用三邊測量法估算未知節點的座標位置。舉個例子：
（05）A、B、C為信標節點，M為未知節點，A到B和C的距離分別為40m和100m，而A到B和C的最小跳數分別為2和5，則A的平均跳距為：（40+100）/ （2+5）=20m，同理可以得到B和C的平均跳數為24m和22.5m，則可以計算M距離三個信標節點的距離分別為：3*20m，2*24m，3*22.5m，然後就可以利用三邊測量法估算出M的座標。這種方法實現比較簡單，但是精度較差，不適合稀疏的以及拓撲不規則的網路。3）APIT演算法APIT演算法的基本思想同質心演算法的思想類似，它利用由信標節點組成的三角形覆蓋重疊區域來確定未知節點的位置。在APIT演算法中，未知節點首先在其鄰居節點中收集信標節點的資訊。然後任意選取3個信標節點，判斷自己是否在這3個信標節點組成的三角形區域內，然後不斷這樣迴圈選取3個信標節點進行判斷，這樣，未知節點可以確定多個包含自己的三角形區域，這些三角形區域的重疊部分是一個多邊形，它確定了更小的包含未知節點的區域，然後以這個多邊形區域的質心作為未知節點的座標。4）MAP演算法MAP（Mobile Anchor Point）是一種基於移動信標節點的非測距定位演算法，也有稱為MAN（Mobile Anchor Node）。其基本思想是利用可移動的信標節點在監測區域中移動並週期性的廣播其當前的位置資訊，然後可以確定兩條以未知節點為圓心的弦，這兩條弦的垂直平分線的交點就是圓心。
（06）如圖所示，S為未知節點，M為移動的信標節點，在T1時刻M移動到S的通訊範圍之內，然後在T5時刻移出S的通訊範圍，這樣就可以確定了兩條弦 T1T5，在T12時刻M又重新移動到S的通訊範圍之內，然後又在T15時刻移出S的通訊範圍，這樣又可以確定一條弦T12T15，這兩條弦的垂直平分線的交點即為圓心S的座標，然後以圓心座標作為未知節點S的位置。該演算法有與其他非測距定位演算法相比有較高的精確度，但是缺點是移動節點是必須要有足夠能量支援其在監測區域內移動，並且當未知節點的位置發生變化時，該演算法有比較大的誤差。5）Amorphous演算法Amorphous演算法與DV-HOP演算法類似，其分為三個階段：第一階段：計算未知節點與每個信標節點之間的最小跳數第二階段：假設網路中的節點通訊半徑相同，並且每跳的平均距離等於節點的通訊半徑，計算未知節點到每個信標節點的距離第三階段：採用三邊測量法或者最大似然估計法估算未知節點的位置6）凸規劃定位演算法凸規劃定位演算法的核心思想是：如果兩個節點能夠直接進行通訊，則它們之間的距離必定小於節點的通訊半徑。
（07）如圖所示，黑色實心點為信標節點，白色空心點為未知節點，假若未知節點能與信標節點通訊，則其必在以信標節點為圓心、通訊半徑為半徑的圓內，這樣的話，多個這樣的圓的相交區域必然包含了未知節點，然後以相交區域構成的矩形的質心作為未知節點的座標。7）Ring-Overlapping演算法
（08）該演算法利用交疊環的思想進行定位，比如S為未知節點，A、B、C為信標節點，若A發出射頻訊號，而S處的訊號強度RSS小於B處的訊號強度而大於C處的訊號強度，則S必在以A-B為內半徑、A-C為外半徑的環形區域內，類似地分別可以得到以B、C為中心的環形區域，而S必在這些環形區域的交疊區域內，然後以交疊區域的質心作為S的座標。以上演算法都是有信標節點的定位演算法，曾有人提出了一些沒有信標節點的定位演算法如SPA（Self-positioning Algorithm）演算法，這種演算法主要是建立全域性座標系來估算未知節點的位置，但是這種演算法複雜度非常高，不適合用於大規模網路，也有人提出針對SPA演算法的改進演算法，如SDGPSN（Scalable and Distributed GPS free Positioning for Sensor Networks）演算法。還有一部分人提出了一些其他的演算法，比如AFL（Anchor-Free Distributed Localization in Sensor Networks）演算法，其利用的是區域性估算方法。還有人提出了基於分簇的定位演算法（Using Clustering Information for Sensor Network Localization）。
