??? 摘 要： 作為重要的共性支撐技術之一，傳感器網(wǎng)絡" title="傳感器網(wǎng)絡">傳感器網(wǎng)絡" title="無線傳感器網(wǎng)絡" title="無線傳感器網(wǎng)絡">無線傳感器網(wǎng)絡">無線傳感器網(wǎng)絡的定位問題極具研究價值。分析了近似三角形內(nèi)點測試算法，對該算法進行了改進。仿真分析表明：較之原算法，改進算法降低了錯判發(fā)生的概率。
??? 關鍵詞： 無線傳感器網(wǎng)絡? 定位? 近似三角形內(nèi)點測試算法
?
??? 根據(jù)節(jié)點定位機制可將現(xiàn)有無線傳感器網(wǎng)絡WSN（Wireless Sensor Network）自身定位算法分為兩類[1]：基于距離的(Range-based)和不基于距離的(Range-free)定位算法。Range-based 定位算法通過測量相鄰節(jié)點之間的絕對距離或方位來計算未知節(jié)點的位置，現(xiàn)階段常用的定位算法有：RSSI、TOA、TDOA和AOA。Range-based 定位機制使用各種算法來減小測距誤差對定位的影響，包括多次測量、循環(huán)定位求精[2]。這些算法在獲得相對精確定位結果的同時，對節(jié)點硬件要求高且都要產(chǎn)生大量計算和通信開銷，因此Range-based 定位機制雖在定位精度" title="定位精度">定位精度上有可取之處，卻常常不適用于低功耗、低成本的無線傳感器網(wǎng)絡應用領域。Range-free定位算法則無需節(jié)點間的距離和角度信息，僅根據(jù)網(wǎng)絡連通性等信息實現(xiàn)定位，常用的定位算法有質(zhì)心、DV-Hop、Amorphous和APIT等。Range-free 定位機制在成本、功耗等方面具有優(yōu)勢，對硬件要求也較低，因此備受關注。特別是APIT可以利用現(xiàn)有傳感器節(jié)點" title="傳感器節(jié)點">傳感器節(jié)點自帶的無線功率發(fā)射裝置，在無需增加額外硬件的情況下實現(xiàn)定位。
1 APIT 定位算法[3]
1.1 算法基本思想
??? APIT（Approximate Point in Trangulation Test）定位算法將未知節(jié)點可能的位置區(qū)域利用其通信半徑內(nèi)已知位置的錨節(jié)點進行三角形劃分，取各部分的公共區(qū)域作為未知節(jié)點位置的估計。如圖1 所示，陰影部分區(qū)域是包含未知節(jié)點的所有三角形的重疊區(qū)域，黑點指示的質(zhì)心位置作為未知節(jié)點的位置。
?
?
1.2 PIT 算法原理
??? APIT算法的理論基礎是最佳三角形內(nèi)點測試法PIT(Perfect Point-In-Triangulation Test)， PIT 測試原理如圖2 所示：假如存在一個方向，沿著這個方向未知節(jié)點M 會同時遠離或接近三角形的3 個頂點A、B、C，則M 位于△ABC 外；否則，M 位于△ABC內(nèi)。
?
??? 為了在靜態(tài)網(wǎng)絡中執(zhí)行PIT 測試，如果節(jié)點M的鄰節(jié)點沒有同時遠離或同時靠近3 個錨節(jié)點A、B、C，則就判定M在△ABC 內(nèi)；否則，判定M在△ABC外。
1.3 APIT定位原理
??? APIT算法利用傳感器網(wǎng)絡較高的節(jié)點密度來模擬節(jié)點移動，利用無線信號的傳播特性來判斷是否遠離或靠近錨節(jié)點。通常在給定方向上，一個節(jié)點距錨節(jié)點越遠，接收信號強度越弱，通過信息交換來判斷與某一錨節(jié)點的遠近，以此來仿效PIT 中的節(jié)點移動。圖3(a)中，待定節(jié)點M通過與鄰節(jié)點1 交換信息，得知自身若運動至節(jié)點1，將遠離錨節(jié)點B和C，但會接近錨節(jié)點A，鄰節(jié)點2、3、4 的通信和判斷過程類似，最終確定自身位于△ABC 中；在圖3(b)中，通過信息交換節(jié)點M 可知：自身若移動至鄰節(jié)點2將同時遠離錨節(jié)點A、B、C，故判斷自身在△ABC外。
?
?
??? 在APIT算法中，一個未知節(jié)點在其通信半徑內(nèi)任選3 個錨節(jié)點，測試自己是否位于它們所組成的三角形中，使用不同錨節(jié)點的組合重復測試，直到窮盡所有組合或達到了所需的定位精度。
??? APIT具體步驟：
??? (1)收集信息：未知節(jié)點收集鄰近錨節(jié)點的信息，如位置、標識號、接收到的信號強度等，鄰居節(jié)點之間交換各自接收到的錨節(jié)點的信息；
??? (2)APIT測試：測試未知節(jié)點是否在不同的錨節(jié)點組合成的三角形內(nèi)部；
??? (3)計算重疊區(qū)域：統(tǒng)計包含未知節(jié)點的三角形，計算所有三角形的重疊區(qū)域；
(4)計算未知節(jié)點位置：計算重疊區(qū)域的質(zhì)心位置，作為未知節(jié)點的位置。
1.4 APIT重疊區(qū)域計算的實現(xiàn)
??? APIT測試結束后，APIT 用grid SCAN 算法(如圖4所示)進行重疊區(qū)域的計算。在此算法中，網(wǎng)格陣列代表節(jié)點存在的可能性最大的區(qū)域。首先令每個網(wǎng)格的初值為0。如果判斷出節(jié)點在三角形內(nèi)，則相應三角形所在區(qū)域的每個網(wǎng)格的值加1；同樣，如果判斷出節(jié)點在三角形外，則相應三角形所在區(qū)域的每個網(wǎng)格的值減1。計算出所有的三角形區(qū)域的值后，找出具有最大值的重疊區(qū)域，最后計算出這個重疊區(qū)域的質(zhì)心即為未知節(jié)點的位置。
?
1.5 in-to-out error與out-to-in error
??? 由于APIT只能判斷有限的方向(即鄰節(jié)點的個數(shù))，因此在某些情況下可能做出錯誤的判斷。如圖5(a)所示，未知節(jié)點M 靠近三角形的一條邊，且鄰節(jié)點4 位于三角形外部，可見節(jié)點4 較之未知節(jié)點M 同時遠離3 個端點A、B、C。根據(jù)APIT 的定義，未知節(jié)點M 就做出在△ABC 外的錯誤判斷，稱作in-to-out error。當節(jié)點M 的鄰節(jié)點的分布如圖5(b)所示時，M 就會做出位于△ABC 內(nèi)的錯誤判斷，稱作out-to-in error。
?
??? 分別作出以A、B、C為圓心，AM、BM、CM為半徑的圓在M點的切線。由圖6可見，角1與角2之和越大，發(fā)生out－to－in error的概率越大，即待定位節(jié)點離三角形的邊長越遠，發(fā)生out－to－in error的可能性越小。這與三角形內(nèi)越靠近三角形邊界的節(jié)點越容易發(fā)生in－to－out error的情況是一致的。
?
? ?
??? 試驗顯示[3]，在無線信號傳播模式不規(guī)則和傳感器節(jié)點隨機部署的情況下，APIT 算法的定位精度高、性能穩(wěn)定，測試錯誤概率相對較小(最壞情況下14%)；平均定位誤差小于節(jié)點無線射程的40%。且該算法最大的優(yōu)點是與其他非基于距離的算法相比算法簡單，受節(jié)點密度影響較小且節(jié)點間通信量少，這就大大降低了功耗，對資源受限的傳感器網(wǎng)絡較為適用。
2 APIT 算法改進
??? 三角形內(nèi)的一點移動后是不可能離三個頂點都近的，所以如發(fā)現(xiàn)一點在一個方向上移動后離三個頂點都近，則這點必定在三角形外。于是，在未知節(jié)點獲知所有鄰節(jié)點與判定三角形頂點的遠近距離后，首先判定是否有鄰節(jié)點離三個頂點都近，如有就判未知節(jié)點在圓外，否則，再考慮移動后離三個頂點都遠的情況。
??? 由分析可知，相比于out－to－in error，發(fā)生in－to－out error的可能性大得多。因此本文針對后者提出了一種改進方案：即隨著鄰節(jié)點數(shù)目的改變，相應調(diào)整判定位于三角形外的條件，即要求待判定節(jié)點都遠離三角形三個頂點的鄰節(jié)點的個數(shù)要達到相應的數(shù)目，才判定未知節(jié)點位于相應三角形的外部，而不同于傳統(tǒng)APIT只要求一個方向上都遠離三角形的三個頂點即可，此處要求都遠離的節(jié)點數(shù)滿足大于等于n/m的要求，n為待判定節(jié)點鄰節(jié)點的個數(shù)，m為權重系數(shù)，分析表明m＝4和m＝5時能達到較好的效果。
3 實驗仿真
??? 在未知節(jié)點的通信半徑內(nèi)隨機布設n（4，5，6，7，8，9，10，15，20）個鄰居節(jié)點，在權重分別為4與5時，進行100次仿真實驗，求出錯判的次數(shù)。
??? 設三角形ABC三點分別為A（0，0），B(3,4),C(4,3)，三角形內(nèi)一緊靠三角形AB邊的待判定節(jié)點M1坐標為（1.6,2)，由此可以模擬in-to-out error錯判的情況。令通信半徑為2.60（此數(shù)值為M1點到點" title="點到點">點到點A、B、C的最長距離），隨機布設的區(qū)域為1.6-2.60
??? 由于新算法提高了APIT判三角形外的條件，勢必會產(chǎn)生少量將三角形外點判為三角形內(nèi)點的錯判，即out-to-in error。
??? 另設圓外一點M2(1.5,4)作為待判定節(jié)點， 由此可以模擬out-to-in error 的錯判情況，令通信半徑為4.272（此數(shù)值為M2點到點A、B、C的最長距離），隨機布設的區(qū)域為1.6-4.272
??? 由仿真結果可見，新算法能明顯減少in-to-out error發(fā)生的概率，但也增加了少量的out-to-in error。權重系數(shù)m取4時，相比于m取5能更有效減少in-to-out error的發(fā)生，但也增加了out-to-in error。可以根據(jù)實際情況選取合適的權重系數(shù)。同時，可以看到當鄰節(jié)點個數(shù)達到9個或更多時，新算法產(chǎn)生out-to-in error的可能性已經(jīng)很小。總體而言，新算法改善了APIT的性能，有其可取性。
??? 本文提出了一種APIT判定條件隨著未知節(jié)點的鄰節(jié)點數(shù)的變化而進行相應調(diào)整的新策略，仿真顯示新算法在增加了些許out－to－in error的情況下，顯著減少了in－to－out error的發(fā)生的概率。隨著無線傳感器網(wǎng)絡應用領域的不斷擴展，對傳感器定位的研究也將進一步深化。由于各種應用差別很大，沒有普遍適合于各種應用的定位算法，因此將針對不同的應用，通過綜合考慮節(jié)點的規(guī)模、成本及系統(tǒng)對定位精度的要求，來設計最適合的定位算法系統(tǒng)。
參考文獻
[1]?孫利民，李建中，陳 渝，等. 無線傳感器網(wǎng)絡[M].北京:清華大學出版社，2005.
[2] ?MAO G Q, FIDAN B, ANDERSON B. Wireless sensor ?network localization techniques[J]. Comput. Networks,2007,51(10):2529-2553.
[3] ?HE T, HUANG C D, BLUM B M, et al. Range-free localization schemes in large scale sensor networks. in Proc.ACM/IEEE 9th Annu. Int. Conf. Mobile Computing and Networking(MobiCom’03), 2003.
[4]?史龍,王福豹,段渭軍,等.無線傳感器網(wǎng)絡Rang-Free自身定位機制與算法[J]. 計算機工程與應用,2004(23):127-132.
[5]?LANGENDOEN K, REIJERS N. Distributed localization ?in wireless sensor net-works: a quantitative comparison[J]. Computer Networks 2003,43:499-518.