1 引 言

　　無線傳感器網(wǎng)絡(WSNs)是由許多傳感器節(jié)點通過自組織的形式組成的一種特殊的Ad-hoc網(wǎng)絡，每一個傳感器節(jié)點由數(shù)據(jù)采集模塊、數(shù)據(jù)處理和控制模塊、通信模塊和供電模塊等組成，此外還可能包括與應用相關的其他部分，比如定位系統(tǒng)、動力系統(tǒng)等。借助于內置多樣的傳感器，可以測量溫度、濕度、氣壓、化學等我們感興趣的物理現(xiàn)象。由于無線傳感器網(wǎng)絡在軍事、醫(yī)學、環(huán)境保護等領域有著非常廣闊的應用前景，受到眾多國家科研機構的重視。

　　傳感器節(jié)點的自身定位是傳感器網(wǎng)絡應用的基礎。例如目標監(jiān)測與跟蹤、基于位置信息的路由、智能交通、物流管理等許多應用都要求網(wǎng)絡節(jié)點預先知道自身的位置，并在通信和協(xié)作過程中利用位置信息完成應用要求。若沒有位置信息，傳感器節(jié)點所采集的數(shù)據(jù)幾乎是沒有應用價值的。所以，在無線傳感器網(wǎng)絡的應用中，節(jié)點的定位成為關鍵的問題。 采用GPS(全球定位系統(tǒng))是獲得位置信息的一種方法，應用是非常廣泛的。但他不適用于傳感器網(wǎng)絡，首先，無線傳感器網(wǎng)絡中節(jié)點數(shù)目比較多，因此單個節(jié)點的成本不能太高，為每一個節(jié)點配備GPS的方案太昂貴了；其次，由于傳感器網(wǎng)絡的布設特點，能源不易更換，要求網(wǎng)絡有較長的生命周期，而GPS定位系統(tǒng)對能源的消耗過大，同時還會增加傳感器節(jié)點的體積，也不適宜；最后，GPS不適于在屋內、水下和嚴重信號阻礙等環(huán)境下的應用。因為傳感器網(wǎng)絡的定位技術要適應傳感器微型化、低成本和低能耗的要求，盡量延長傳感器網(wǎng)絡的生命期，只有通過網(wǎng)絡內部節(jié)點之間的相互測距和信息交換，形成一套全網(wǎng)節(jié)點的坐標，才是經濟可行的定位方案。

　　2 現(xiàn)有定位算法研究

　　最早期的基于無線網(wǎng)絡的室內定位系統(tǒng)，都采用了額外的硬件和設備，如AT&T Cambridge的Active Bat系統(tǒng)，采用了超聲波測距技術，定位的物體攜帶由控制邏輯、無線收發(fā)器和超聲波換能器組成的稱為Bat的設備，發(fā)出的信號由安裝在房間天花板上的超聲波接收器接收，所有接收器通過有線網(wǎng)絡連接；在微軟的RADAR系統(tǒng)中，定位目標要攜帶具有測量RF信號強度的傳感器，還要有基站定期發(fā)送RF信號，在事先實現(xiàn)的RF信號的數(shù)據(jù)庫中查詢實現(xiàn)定位；MIT開發(fā)了最早的松散耦合定位系統(tǒng)Cricket，錨節(jié)點(預先部署位置的節(jié)點)隨機地同時發(fā)射RF和超聲波信號，RF信號中包括該錨節(jié)點的位置，未知節(jié)點接收這些信號，然后使用TDOA技術測量與錨節(jié)點的距離來實現(xiàn)定位。

　　以上系統(tǒng)都需要事先的網(wǎng)絡部署或數(shù)據(jù)生成工作，無法適用于Ad-hoc網(wǎng)絡�，F(xiàn)階段研究較多的是不基于測距(Range-free)的定位算法，這樣就無需增加額外的硬件，還可以減小傳感器節(jié)點的體積。除此之外，較好的算法還要具備以下幾點特性：

　　(1) 較小的能耗

　　傳感器節(jié)點所攜帶能源有限和不易更換的特點要求定位算法應該是低能耗的。

　　(2) 較高的定位精度

　　這是衡量定位算法的一個重要指標，一般以誤差與無線射程的比值來計算，20％表示定位誤差相當于節(jié)點無線射程的20％。

　　(3) 計算方式是分布式的

　　分布式的定位算法，即計算節(jié)點位置的工作在節(jié)點本地完成，分布式算法可以應用于大規(guī)模的傳感器網(wǎng)絡。

　　(4) 較低的錨節(jié)點密度

　　錨節(jié)點定位通常依賴人工部署或GPS實現(xiàn)。大量的人工部署不適合Ad-hoc網(wǎng)絡，而且錨節(jié)點的成本比普通節(jié)點要高兩個數(shù)量級。

　　(5) 較短的覆蓋時間。

　　2.1 算法分析

　　近些年提出很多典型的算法，但都有各自比較明顯的優(yōu)點和缺點。早期提出的質心算法和APIT算法要求有較高的錨節(jié)點密度，凸規(guī)劃算法和MDS-MAP算法需要集中式的計算；Euclidean算法基于圍繞在錨節(jié)點周圍的節(jié)點的局部幾何拓撲，但距離的測量較為復雜。在所有算法中Savarese等提出的Robust positioning算法和Sav-vides等提出的N-hop multilateration算法是典型的求精算法，與其他算法相比，是較為優(yōu)秀的算法。

　　2.1.1 Robust positioning算法

　　Robust positioning算法分為測距、定位和求精三階段，在測距階段，算法采用了DV-hop算法的思想，首先使用典型的距離矢量交換協(xié)議，使網(wǎng)絡中所有節(jié)點獲得距錨節(jié)點的跳數(shù)(distance in hops)。第二階段，在獲得其他錨節(jié)點位置和相隔跳距后，錨節(jié)點計算網(wǎng)絡平均每跳距離，然后將其作為一個校正值(correction)廣播至網(wǎng)絡中。當接收到校正值后，節(jié)點根據(jù)跳數(shù)計算與錨節(jié)點距離。如圖1所示，錨節(jié)點L2計算出他的網(wǎng)絡平均每跳距離為(40+75)／(2+5)=16.4 m。

　　在定位階段，采用了最小二乘法(Lateration)進行計算，當未知節(jié)點獲得與3個或3個以上錨節(jié)點(xi，yi)的距離di時，根據(jù)以下式子，可推出計算公式：

　　由式(1)可推出： 
 
 

　　令：

　　利用公式(2)，(3)可求得：

　　最后利用公式：

 
　　來判斷所求的結果是否有效，當residue超過無線射程時，結果是無效的。
　　在求精階段，節(jié)點測量得到所有一跳鄰居的距離并依次更新自己的位置。該算法的所有位置計算都使用最小二乘法。算法引入了置信度來提高求精階段的性能，置信度被用來在三邊定位中加權。當未知節(jié)點更新其位置估計時同樣也更新其置信度。這樣，網(wǎng)絡的平均置信度將隨迭代而增加，提高了覆蓋度和精度。

　　該算法的定位精度比較高，在網(wǎng)絡連通度較高的情況下能較好地容忍距離誤差。但由于對網(wǎng)絡拓撲的依賴，需要較長的覆蓋時間。

　　2.1.2 N-hop multilateration算法

　　在N-hop multilateration算法中，測距使用的是超聲波測距技術，該算法也分為3個階段，第一階段是生成協(xié)作子樹，根據(jù)判定條件，在網(wǎng)絡中生成多個由未知節(jié)點和錨節(jié)點組成的限制條件完整或超限制條件的構形，稱為協(xié)作子樹。每個構形包括n個未知變量(未知節(jié)點的坐標)和至少n個非線性方程式，并確保每個未知變量擁有惟一解。未被協(xié)作子樹包含的節(jié)點在整個算法的后處理階段進行定位。

　　第二階段是對未知節(jié)點位置的粗略估計，他通過粗略未知節(jié)點和錨節(jié)點問的距離來估算未知節(jié)點的位置。如圖2所示，未知節(jié)點C在錨節(jié)點A，B所形成的Boundingbox里面，可推算出節(jié)點所在位置的x坐標的取值范圍是(|xA-a|，|xB+(b+c)|)。

　　第三階段采用了循環(huán)求精，根據(jù)預設的定位精度，使用卡爾曼濾波技術在每個協(xié)作子樹范圍內(每個節(jié)點位置有惟一解)對第二階段的結果進行循環(huán)求精。

　　該算法要求錨節(jié)點要求錨節(jié)點要部署在網(wǎng)絡的邊緣才能達到較好的效果，而且循環(huán)求精的次數(shù)無法預知。

　　2.1.3 算法分析

　　對于傳感器網(wǎng)絡節(jié)點定位算法，定位精度是個主要的評估標準，上述兩種算法都采用了求精的步驟，仿真結果顯示定位精度有了比較大的提高，但各自又有不足之處，在測距階段，Robust positioning算法采用了DV-hop的算法，DV-hop算法是基于距離矢量交換協(xié)議的，在大型網(wǎng)絡中需要較長的覆蓋時間，而N-hop multilateration算法卻采用了硬件測距的方法，提高了網(wǎng)絡的成本。

　　N-hop muItilateration算法可以根據(jù)配置采用集中式和分布式兩種計算方式，通信開銷基本相當，他在定位階段，采用了Bounding box的方法，計算量要比最小二乘法小很多，是非常值得借鑒的思想。而對N-hop multi-lateration算法，錨節(jié)點的密度和分布對算法的定位精度有較大的影響，而Robust positioning算法在這方面的影響較小�？傮w上講，Robust positioning算法要比N-hopmultilateration算法具有更大的優(yōu)勢，今后主要的工作是如何提高該算法的覆蓋速度，來適應大規(guī)模網(wǎng)絡的需要。

　　3 結 語

　　近些年來，國內外提出了很多關于傳感器網(wǎng)絡節(jié)點的定位算法，每一種算法都有各自的特點。對于精度比較高的算法，通信開銷和收斂速度等方面的性能可能就會有所下降，采用硬件測距可以提高定位精度，但同時會增加傳感器節(jié)點的成本。根據(jù)具體業(yè)務的需要，定位的條件和要求會有所不同，因此，要針對具體的應用設計和采用適合的定位算法。傳感器網(wǎng)絡定位技術還有比較大的研究空間，主要集中在傳感器節(jié)點測距硬件技術的研究、傳感器網(wǎng)絡定位算法仿真平臺的研究與開發(fā)和基于復雜地理條件下的定位算法研究等方面。

　　轉載請注明來源：賽斯維傳感器網(wǎng)（ywhs9.com）