無線傳感器網(wǎng)絡(luò)中基于有效三角形判定的改進APIT定位方法*

譚 真， 湯大權(quán)， 史宗麟

(國防科技大學(xué) 信息系統(tǒng)工程重點實驗室，湖南 長沙 410073)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)是由大量具有獨立數(shù)據(jù)采集功能傳感器節(jié)點組成的、基于任務(wù)的信息采集平臺。由于部署方便、快捷，其應(yīng)用范圍十分廣泛，如環(huán)境檢測、災(zāi)害防護、交通檢測、目標跟蹤等[1,2]。在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點自身位置的確定，即節(jié)點自定位是網(wǎng)絡(luò)的基本功能，它在無線傳感器網(wǎng)絡(luò)應(yīng)用領(lǐng)域中具有重要意義。它不僅可以確定發(fā)生感知數(shù)據(jù)的具體地理位置或者相對某一個參照系的位置，為進一步跟蹤目標奠定基礎(chǔ)；而且可以通過自定位信息選擇最短的路徑傳輸信息，使得在提高路由效率的同時減少通信開銷。

現(xiàn)階段，很多人針對如何降低傳感器能耗問題進行研究。Jung Deokwoo提出了一種交叉使用高能耗和低能耗的傳感器來降低傳感器的能耗，這種利用增加硬件來降低能耗的方法增加了使用成本[3]；Coleri S和 Ergen M提出了一種混合數(shù)據(jù)模型的傳感器生命周期分析方法[4]，但其算法不滿足節(jié)點隨機分布的特性；Wu Lidong提出了一種用最少傳感器覆蓋所有探測區(qū)域的方法[5]，該方法有效提高傳感器的使用率，但無法進行節(jié)點自定位。

針對APIT定位算法存在的算法復(fù)雜度高、定位過程能耗較大的問題，本文提出了一種利用分離定理和面積法排除無效三角形的方法，該方法可以有效地減小定位方法的計算量，降低通信能耗，以此延長無線傳感器網(wǎng)絡(luò)的壽命。

1 APIT方法及其缺陷

APIT定位算法的理論基礎(chǔ)是三角形內(nèi)點測試(perfect point-in-triangulation text,PIT)法。PIT的基本原理如圖1所示，假設(shè)存在一個方向，節(jié)點M沿著這個方向移動會同時遠離或接近頂點O，P，Q,那么節(jié)點位于△OPQ外；否則,M位于△OPQ內(nèi)。在傳感器網(wǎng)絡(luò)中節(jié)點通常是靜止的，文獻[2]為了在靜態(tài)的環(huán)境中實現(xiàn)三角形內(nèi)點測試，提出了APIT法：假如在節(jié)點M的所有鄰居節(jié)點中，相對于節(jié)點M沒有同時遠離或靠近3個信標節(jié)點O，P，Q,那么節(jié)點M位于△OPQ內(nèi);否則,節(jié)點M位于△OPQ外。

2 改進APIT方法

針對上述APIT算法的不足，研究人員提出了很多的改進方法，周四清提出了一種IAPIT方法，該方法提高了算法定位的精度，但大幅度地增加了硬件成本和能量消耗[6]，本文提出了一種只針對有效三角形進行APIT的方法，即在進行APIT前判斷該三角形是否為有效三角形，若為無效三角形，則不需要進行APIT算法。這樣大大減少了APIT的次數(shù)，因此，減少了自定位過程中的通信量，降低了節(jié)點能耗，增加了網(wǎng)絡(luò)壽命。

首先說明2個定理：

定理1 分離定理[7]：平面上2個三角形不相交,當且僅當在這2個三角形的所有邊中至少存在一條邊，這2個三角形位于這條邊所在直線的異側(cè)。

定理2 面積法[7]：如果△PBC，△PAB和△PAC的面積之和與△ABC的面積相等，即可判定點P在△ABC內(nèi)(包括在三條邊上)。

2.1 算法描述

本文提出的APIT改進方法使用了上述2個定理。其定位步驟如下:

1)初始化構(gòu)造三角形：假設(shè)在目標定位區(qū)域存在一個三角形將所有的傳感器節(jié)點包括在內(nèi)。所謂構(gòu)造三角形就是人為構(gòu)造一個將未知節(jié)點包括在其內(nèi)部的三角形。

2)遍歷三角形：用面積法和分離定理判斷所遍歷的三角形是否是無效三角形，若為無效三角形,則排除;若為有效三角形，則進行APIT算法，然后判斷有效三角形的面積是否小于構(gòu)造三角形，若小于,則將當前的有效三角形視為構(gòu)造三角形。所謂有效三角形就是與構(gòu)造三角形相交或內(nèi)含與構(gòu)造三角形的三角形；反之，即為無效三角形。

3)求質(zhì)心：對包含未知節(jié)點的所有三角形求交集，即為未知節(jié)點所在區(qū)域，求其質(zhì)心，得到未知節(jié)點的位置。

2.2 算法舉例

2.2.1 初始化三角形

如圖1所示在目標定位區(qū)域設(shè)計一個大的△OPQ，記為最初的構(gòu)造三角形，記錄其所有邊的函數(shù)，計算三角形的面積，將節(jié)點所感知區(qū)域內(nèi)的所有的傳感器節(jié)點都包括在內(nèi)。

圖1 初始化三角形

2.2.2 遍歷三角形

1)對于任意一個所遍歷的△ABC，利用面積法判斷其是否包含傳感器所在的△OPQ，若包含如圖2(a)，則△ABC內(nèi)部的所有柵格加1，然后遍歷下一個三角形(break)。

2)利用分離定理判斷所遍歷的△ABC是否與當前的△OPQ相交，若不相交,如圖2(b)，則△ABC內(nèi)部的所有柵格減1，然后遍歷下一個三角形(break)。

3)使用APIT算法，判斷傳感器節(jié)點是否在所遍歷三角形內(nèi)部:

a.若在傳感器節(jié)點在所遍歷△ABC內(nèi)部，則將△ABC內(nèi)部的所有柵格加1，然后比較△ABC同△OPQ的面積;若當前S△ABCS△OPQ，△ABC內(nèi)部的所有柵格加1，然后遍歷下一個三角形(break)。

b.若在傳感器節(jié)點在所遍歷△ABC外部，如圖2(d)所示，則△ABC內(nèi)部的所有柵格減1，然后進行下一次遍歷(break)。

圖2 遍歷三角形

2.2.3 柵格法求質(zhì)心

最終將柵格內(nèi)的最大數(shù)所在區(qū)域記為傳感器所在區(qū)域，所在區(qū)域柵格的個數(shù)記為Count，求出所在區(qū)域的質(zhì)心(X,Y)即視為傳感器的坐標所在地，如圖3所示，質(zhì)心公式如下

其中，Xi,Yj為每個柵格的中心點坐標。

圖3 利用柵格法求質(zhì)心

2.3 算法設(shè)計

假設(shè)未知節(jié)點M周圍有N個鄰居信標節(jié)點，則每次APIT的算法復(fù)雜度為O(N)，而利用分離定理和面積法判斷三角形是否是無效三角形的算法復(fù)雜度為O(1)，所以,排除無效三角形法可以有效降低算法復(fù)雜度。APIT改進算法如下：

square_random(1000,300,0.2);%布置節(jié)點 GPS誤差為0

model=‘Regular Model’;%選擇通信模型

Init Triangle();%初始化三角形

fori=unknown_node_index %遍歷所有節(jié)點

fora=1:neighboring_anchor_n-2%遍歷所有三角形

forb=a+1:neighboring_anchor_n-1

forc=b+1:neighboring_anchor_n

if(squaremethod( Triangle[a,b,c])>0)

%面積法排除無效三角形

break;

elseif(separate theorem(Triangle[a,b,c])>

0)

%分離定理排除無效三角形

break;

else

APIT(grid_length);%使APIT定位

end

end

end

end

gird(Triangle[a,b,c]) ;%柵格法求質(zhì)心

end

3 仿真實驗

在基于APIT的自定位算法過程中，影響定位精度與能耗的條件有很多：1)信標節(jié)點在節(jié)點中所占的比例：所占比例越大，定位的精度越高，但定位的復(fù)雜度就越高，能耗就越大。2)節(jié)點的分布狀況：信標節(jié)點的分布對定位的精度有很大的影響，當未知節(jié)點不再任何一個信標節(jié)點構(gòu)成的三角形內(nèi)部時，就無法達到定位的效果。3)柵格的大小：柵格越小，定位的精度越高，但是太小的柵格就使傳感器的能耗大大增加，進而導(dǎo)致傳感器的使用壽命降低。

本文就APIT與其改進算法分別做仿真，以此比較兩者的優(yōu)劣。

3.1 仿真實驗參數(shù)

本文采用Matlab進行仿真，仿真參數(shù)如表1所示。在仿真實驗的過程中，著重考慮算法的精度和復(fù)雜度，并針對算法的復(fù)雜度進行分析，并以信標節(jié)點個數(shù)的變化作為條件統(tǒng)計APIT使用次數(shù)，以此項指標判斷算法的有效性。

表1 仿真實驗參數(shù)設(shè)置

3.2 實驗結(jié)果比較

3.2.1 APIT次數(shù)統(tǒng)計比較

由文獻[2]可知，每次進行APIT時，自定位節(jié)點都需要和周圍的信標節(jié)點進行至少一次通信，而通信的過程即是消耗能量的過程，所以,在實驗中可以通過統(tǒng)計每次定位過程中所需要的APIT次數(shù)來近似測算節(jié)點所消耗的能量。實驗中假設(shè)在長、寬各為100 m的區(qū)域中部署了100個未知節(jié)點，信標節(jié)點的個數(shù)從10個一直增加到35個，圖4展示了在信標節(jié)點個數(shù)不同的情況下APIT的次數(shù)。改進算法在APIT次數(shù)明顯低于原算法，尤其在信標節(jié)點個數(shù)為30時改進算法的APIT次數(shù)較原算法降低了53 %。由此可見改進后的算法將大大降低計算量，以此為節(jié)點節(jié)省大量能量。

圖4 APIT的次數(shù)

3.2.2 能耗比較

通常1 bit的信息傳輸100 m距離所需要的能量大約相當于執(zhí)行3 000條計算指令所消耗的能量[8]。通過這一換算關(guān)系對算法的能耗進行仿真計算，結(jié)果如圖5所示。相比較于APIT算法，改進后的算法在能耗方面有了很大的降低，當信標節(jié)點為20時降低大約42 %。這是由于改進算法在計算的過程中大大減少了未知節(jié)點與周圍節(jié)點的通信。從而使能耗的大大降低，傳感器的使用壽命延長。

圖5 能耗比較

3.3 定位誤差比較

所謂定位誤差，就是未知節(jié)點實際未知與估計未知之間的距離與通信半徑之間的比值。

1)柵格大小對定位誤差的影響

本文通過改變柵格大小仿真柵格邊長對定位精度的影響。在仿真過程中，未知節(jié)點的通信半徑為50 m，得到結(jié)果如圖6。通過觀察發(fā)現(xiàn)，當柵格邊長較小時，改進的APIT算法定位誤差略高于APIT算法的定位誤差，當柵格的大小增加到通信半徑的1/10時，改進后APIT算法的定位誤差將高于原APIT算法的誤差，這時不宜采用改進的APIT 算法。

圖6 柵格大小對定位誤差的影響

2)信標節(jié)點個數(shù)對定位誤差的影響

為了進一步研究信標節(jié)點個數(shù)對定位誤差的影響，設(shè)置柵格邊長為2 m，分別對信標節(jié)點個數(shù)為10,15,20,25的情況進行仿真實驗，定位誤差結(jié)果如圖7所示。從結(jié)果來看，改進后算法的定位誤差有所增大，但與原算法十分接近，因此,改進后算法的定位結(jié)果準確、可靠。

圖7 信標節(jié)點個數(shù)對定位誤差的影響

4 結(jié)束語

本文利用面積法和分離定理提出了一種排除無效三角形的方法來改進APIT算法，降低算法的復(fù)雜度，以此降低能耗，增加網(wǎng)絡(luò)壽命。仿真實驗結(jié)果表明：該方法可以在不失定位精度的同時大量減少APIT的次數(shù)、降低能耗、增加傳感器網(wǎng)絡(luò)的使用壽命，有效解決了原APIT能耗問題，滿足了用戶對增加網(wǎng)絡(luò)壽命的需求。

參考文獻:

[1] 孫利民.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005.

[2] He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]∥Proc 9th Annual Int’l Conf on Mobile Computing and Networking (MobiCom),San Diego,CA,2003:81-95.

[3] Jung Deokwoo ,Savvides Andreas .An energy efficiency evaluation for sensor nodes with multiple processors,radios and sensor-s[C]∥Proceedings of IEEE INFOCOM 2008 ,Palma De Mallorca,Spain,2008:1112-1120.

[4] Coleri S,Ergen M.Lifetime analysis of a sensor networkwith hybrid automata modeling[C]∥1st ACM International Workshop on Wireless Sensor Networks and Applications(WSNA),Turin,2002.

[5] Wu Lidong ,Du Hongwei,Wu Weili.Approximationsfor minimum connected sensor cover[C]∥Proceedings of IEEE INFOCOM 2013,Italy,2013:1188-1194.

[6] 周四清,陳銳標.無線傳感器網(wǎng)絡(luò)APIT定位算法及其改進[J].計算機工程,2009,35(7):87-89.

[7] 何大華,陳傳波.兩個三角形不相交的充要條件[J].應(yīng)用數(shù)學(xué)， 2002 (1)：37-41.

[8] 趙 靜,潘 斌,王 進,等.無線傳感器網(wǎng)絡(luò)能耗分析與策略研究[J].通信技術(shù),2010,10(43)：85-89.

[9] Jung D,Teixeira T,Barton-Sweeney A.Model-based design exploration of wireless sensor node lifetimes[C]∥European Confe-rence on Wireless Sensor Networks,EWSN’07,Chicago,2007:277-292.

[10] Li Xinrong.Collaborative localization with received-signal strength in wireless sensor networks[J].IEEE Transactions on Vehicular Technology,2007,56(6):3807-3817.

[11] Wang C,Wang G.Reconciling privacypreservation and intrusion detection in sensory data aggregation[C]∥Proceedings of 31th IEEE International Conference on Computer Communications,Seoul,Korea,2011:336-340.