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

(國(guó)防科技大學(xué) 信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410073)

0 引 言

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

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

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

1 APIT方法及其缺陷

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

2 改進(jìn)APIT方法

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

首先說(shuō)明2個(gè)定理：

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

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

2.1 算法描述

本文提出的APIT改進(jìn)方法使用了上述2個(gè)定理。其定位步驟如下:

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

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

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

2.2 算法舉例

2.2.1 初始化三角形

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

圖1 初始化三角形

2.2.2 遍歷三角形

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

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

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

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

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

圖2 遍歷三角形

2.2.3 柵格法求質(zhì)心

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

其中，Xi,Yj為每個(gè)柵格的中心點(diǎn)坐標(biāo)。

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

2.3 算法設(shè)計(jì)

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

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

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

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

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

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)

%面積法排除無(wú)效三角形

break;

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

0)

%分離定理排除無(wú)效三角形

break;

else

APIT(grid_length);%使APIT定位

end

end

end

end

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

end

3 仿真實(shí)驗(yàn)

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

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

3.1 仿真實(shí)驗(yàn)參數(shù)

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

表1 仿真實(shí)驗(yàn)參數(shù)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果比較

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

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

圖4 APIT的次數(shù)

3.2.2 能耗比較

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

圖5 能耗比較

3.3 定位誤差比較

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

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

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

圖6 柵格大小對(duì)定位誤差的影響

2)信標(biāo)節(jié)點(diǎn)個(gè)數(shù)對(duì)定位誤差的影響

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

圖7 信標(biāo)節(jié)點(diǎn)個(gè)數(shù)對(duì)定位誤差的影響

4 結(jié)束語(yǔ)

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

參考文獻(xiàn):

[1] 孫利民.無(wú)線(xiàn)傳感器網(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] 周四清,陳銳標(biāo).無(wú)線(xiàn)傳感器網(wǎng)絡(luò)APIT定位算法及其改進(jìn)[J].計(jì)算機(jī)工程,2009,35(7):87-89.

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

[8] 趙 靜,潘 斌,王 進(jìn),等.無(wú)線(xiàn)傳感器網(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.