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