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