無線傳感器網絡APIT算法邊界效應的改進

冀常鵬　豐竹松　華一陽

1(遼寧工程技術大學電子與信息工程學院　遼寧 葫蘆島 125100)

2(遼寧工程技術大學研究生院　遼寧 葫蘆島 125100)

?

無線傳感器網絡APIT算法邊界效應的改進

冀常鵬1豐竹松2華一陽1

1(遼寧工程技術大學電子與信息工程學院遼寧 葫蘆島 125100)

2(遼寧工程技術大學研究生院遼寧 葫蘆島 125100)

摘要在無線傳感器網絡中，針對APIT算法存在邊界效應導致定位精度不足的問題，提出一種基于節點信號強度和的改進定位算法SAPIT(sum of signal strength based APIT)。該算法在PIT測試前，先確定三角形內所有節點收到三個錨節點信號強度和的最小值，利用該最小值排除引起邊界效應的鄰居節點；然后結合PIT測試和網格掃描算法，確定待定位節點的坐標位置。仿真結果表明，SAPIT算法降低了In-To-Out Error和Out-To-In Error的發生概率，有效地提高了節點的定位精度。

關鍵詞無線傳感器網絡邊界效應信號強度和定位精度

IMPROVEMENT OF BOUNDARY EFFECTS OF APIT IN WSN

Ji Changpeng1Feng Zhusong2Hua Yiyang1

1(School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125100,Liaoning,China)2(Institute of Graduate,Liaoning Technical University,Huludao 125100,Liaoning,China)

AbstractIn wireless sensor networks, for the problem that the boundary effects existing in APIT algorithm cause the lack of localisation precision, we proposed an improved localisation algorithm which is based on the sum of signal strength of nodes (SAPIT). The SAPIT algorithm determines the minimum sum of signal strength of three anchor nodes received by all the nodes in triangle before the PIT test. Then the algorithm uses the minimum sum to eliminate the neighbour nodes incurring the boundary effects. Finally, it combines PIT test with gird scanning algorithm to determine the coordinate positions of the unknown nodes. Simulation results showed that the SAPIT algorithm reduced the probabilities of occurrence of in-to-out error and out-to-in error, and effectively improved the precision of nodes localisation.

KeywordsWireless sensor networksBoundary effectsSum of signal strengthLocalisation precision

0引言

在無線傳感器網絡中存在著大量隨機分布的傳感器節點，每一節點都可作為一個獨立的數據采集器，對檢測區域進行實時監控。對節點返回的數據信息進行處理時，如果節點的位置信息不能得到確定，那么采集的數據將失去意義。因此，傳感器節點的自定位問題成為無線傳感器網絡的重要研究內容之一。如今傳感器在實際中被廣泛應用，如環境檢測、汽車跟蹤、地理標記以及水下傳感器[1]，都需要將節點位置信息作為一項重要指標。此外，節點的位置信息也被用于改進網絡方案，譬如在基于路由協議的網絡中，位置的確定能省去路由遍歷的過程，從而節省尋找路由所用的時間和能量[2]。

目前存在的定位算法根據其是否需要測定節點間的距離分為兩大類：一類是基于測距的定位算法，代表算法有RSSI、TDOA、TOA和AOA等定位算法[3]；一類是非基于測距的定位算法[4]，常用算法有質心算法、APIT算法和DV-hop算法等[5]。基于測距的定位算法比非基于測距的定位算法的定位精度高，但同時對硬件有較高要求，成本也隨之增加。非基于測距的定位算法雖然定位精度稍低，但完全可以滿足實際需要，且對硬件要求較低，在成本和功耗方面均具有優勢。因此，非基于測距的定位算法一直是研究的熱點。

APIT算法由He等人在2003年提出[6]，相比于其他非基于測距的定位算法，APIT算法由于定位精度高，通信開銷小等優點而備受關注。但是APIT算法一直存在邊界效應問題，即In-To-Out Error和Out-To-In Error。針對Out-To-In Error問題，周勇等人提出了三角形重心掃描算法[7]，而針對In-To-Out Error問題，韓彪[8]等人通過設置影響因子來減小誤差。由于改進后誤差仍然較大，王新生[9]等人在前人改進的基礎上，設置計數器來減小誤差，但該方法增加了能量損耗。文獻[10]利用三角形面積和對有效三角形進行判斷，文獻[11]利用角度和對有效三角形進行判斷，但兩種方法計算量很大，致使定位時間加長[10,11]。文獻[12-14]通過結合其他定位算法進行改進，在提高定位精度的同時加大了算法的復雜程度。Chiti和姚艷等人分別從掃描算法上對APIT算法進行改進，沒從根本上解決邊界效應帶來的誤差[15,16]。以上算法均對APIT算法進行了改進，在一定程度上減小了定位誤差，但都沒有同時對In-To-Out Error和Out-To-In Error進行很好地解決。本文從引起邊界效應的根源入手，對APIT算法進行改進，提出一種基于節點信號強度和的定位算法—SAPIT算法。該算法較好地解決了邊界效應的問題，明顯提高了節點的定位精度。

1APIT算法分析

APIT算法的主要思想：在初始階段，未知節點先收集鄰居錨節點信息;然后通過判斷確定包含未知節點的三角形，把多個三角形形成的重疊區域的質心作為未知節點的坐標。

1.1APIT算法步驟

第一步信息收集階段。未知節點收集鄰居錨節點的信息，包括信號強度、坐標等，同時鄰居節點之間交換所接收到的錨節點信息。

第二步PIT測試階段。用三角形內點測試法判斷未知節點是否位于錨節點組成的三角形內，重復進行直至所有錨節點組合測試完畢。

第三步利用網格掃描算法得出三角形重疊部分，求出該重疊區域的質心位置，以此作為待定位節點的坐標[17,18]。

1.2APIT算法誤差分析

在APIT算法中，判斷未知節點是否位于錨節點組成的三角形內部是算法的關鍵步驟。該步驟以三角形內點測試法(PIT)作為理論依據，其定義如下：若點M位于三角形外部，則存在一個方向，使得點M沿此方向移動時，能夠同時靠近或遠離三角形的三個頂點A、B、C；否則，點M位于三角形內部。

在上述PIT測試中，節點M被假定為可移動的。但在實際傳感器網絡中，待定位節點大多是靜止的，這使得APIT測試應運而生。其定義如下：假設節點M的所有鄰居節點均不同時靠近或遠離3個錨節點A、B、C，那么點M位于三角形內部；否則，點M位于三角形外部。

在APIT算法中，要想判斷未知節點是否位于三角形內部，必須通過與鄰居節點交換信息，這使得算法判斷結果與鄰居節點的分布密切相關。并且APIT只能判斷有限的方向，因此，在實際測試中，常出現將內部節點判斷為外部節點(In-To-Out Error)或將外部節點判斷為內部節點(Out-To-In Error)的情況，統稱為邊界效應[19,20]。

如圖1中(a)所示，節點M原本位于三角形內部，但鄰居節點1從三個錨節點收到的信號強度值均小于M收到錨節點的信號強度值。根據APIT定義，判定M位于三角形外部，發生In-To-Out Error。由此可知，只有當鄰居節點沒有移出三角形外部時，PIT測試才能成立。

如圖1中(b)所示，節點M原本位于三角形外部，與鄰居節點1、2對比后，沒有同時遠離或者同時接近三個錨節點的鄰居節點。根據APIT定義，判定M位于三角形內部，發生Out-To-In Error。這是由于鄰居節點數目過少，節點密度低造成的。

圖1　In-To-Out Error和Out-To-In Error

2SAPIT算法

通過對APIT算法分析可知，APIT算法產生誤差的主要原因是部分鄰居節點導致了邊界效應。若能減少此類鄰居節點，則可以提高節點定位的精確度。基于這一思想，本文提出一種基于信號強度和的改進算法。該算法在PIT測試前，先確定三角形內所有節點收到三個錨節點信號強度和的最小值，利用該最小值排除引起邊界效應的鄰居節點，然后結合PIT測試和網格掃描算法，確定待定位節點的坐標位置。

2.1傳播模型

無線電傳播模型分為規則傳播模型和不規則傳播模型。其中不規則傳播模型更加接近于現實傳播[21,22]。不規則傳播模型相比規則傳播模型，增加了相關參數，但對SAPIT算法理論推導沒有影響，因此選擇規則傳播模型作為該算法推導的基礎。規則傳播模型公式如下：

(1)

其中，PR(d)是距離發送節點d米處收到的信號強度，Pr為發送節點的發送功率，PL(do)是參考距離為d0米的路徑損耗。參照規則傳播模型的經典取值，將η取為4，A=Pr-PL(do)，d0=1m，故可寫成：

PR(d)=A-40logd

(2)

2.2確定最小信號強度和

在三角形內，若某一節點收到的三個錨節點信號強度之和最小，那么三角形內任意節點信號強度和均大于該最小信號強度和。又由于信號在傳播過程中逐漸減小，那么三角形外任意節點收到的信號強度和均小于該最小信號強度和。在APIT算法中，產生誤差的主要原因在于鄰居節點的合法性(即是否會產生邊界效應)不能保證。而在SAPIT算法中應用上述理論，可對鄰居節點的合法性進行判斷，通過最小信號強度和能夠把不合法的鄰居節點排除，從而使PIT測試更加準確。下面推出此最小信號強度和的位置所在。

若某點處的節點收到三個錨節點信號強度之和最小，其中di、dj、dk為此點到三個錨節點的實際距離，那么：

Pmin=PR1(di)+PR2(dj)+PR3(dk)

=3A-40log(di×dj×dk)

(3)

圖2　錨節點構成銳角三角形

令S= di×dj×dk，當P取最小值時，S取最大值。因此，要想求得Pmin，可以通過求Smax獲得。

為求錨節點組成的三角形內的Smax，分別對可能形成的銳角三角形、直角三角形、鈍角三角形進行分析，每類三角形各取5點作為參考。圖2-圖4為三類三角形示意圖，表1-表3為三類三角形S值表。

表1　銳角三角形各點S值

對10個銳角三角形各取50個點計算其S值，最終確定S的最大值點位于最長邊的中點處。

圖3　錨節點構成直角三角形

取點位置N(最長邊中點)O(直角邊一點)L(直角邊AC一點)E(三角形外一點)J(三角形內一點)S=di×dj×dk21693.39198.88284.64165.85

對10個直角三角形各取50個點計算其S值，最終確定S的最大值點位于最長邊的中點處。

圖4　錨節點構成鈍角三角形

取點位置T(三角形最長邊中點)K(靠近T的點)M(三角形邊一點)L(三角形邊一點)F(三角形外一點)S=di×dj×dk128.29137.19118.9975.20187.38

對10個鈍角三角形各取50個點計算其S值，其最大值點并非位于最長邊的中點處。三邊S值分布大體趨勢如圖5所示，從圖中可以看出，最大值點位于最長邊的中點附近。

圖5　鈍角三角形三邊各點的S值(AB最長)

通過對三類三角形分析可知，當錨節點構成的三角形為銳角三角形或直角三角形時，Smax點位于三角形最長邊的中點處；當錨節點構成的三角形為鈍角三角形時，Smax點位于最長邊中點的附近，由于誤差比(Smax-S中)/Smax最大約為5%，對算法判定影響很小，因此誤差可忽略，仍將Smax點看作位于最長邊的中點處。錨節點組成的三角形越不規則，S最大值點偏離最長邊中點處的程度越大。但在傳感器網絡中，傳播模型大致為圓形，錨節點組成三角形相對規則。綜上所述，三角形最長邊中點處的S值最大，同時信號強度和最小。因此取三角形最長邊中點處的信號強度和為最小信號強度和。

2.3改進算法的步驟

1) 在進行PIT測試前，錨節點通過廣播向其通信范圍內的所有未知節點發送坐標、標識號、信號強度等信息，節點在傳感器內寄存所接收到的信息。表4為節點收到的錨節點信息，其中A、B、C表示錨節點，(X,Y)為錨節點的坐標信息，SS為節點接收的錨節點信號強度值。

表4　接收的錨節點信息

2) 在錨節點廣播信息后，待定位節點同其通信范圍的鄰居節點交換并存儲節點信息。表5為交換后的信息表。

表5　信息交換后節點的信息

3) 待定位節點收到廣播信息后，從接收到信號的所有錨節點中任意選取3個，計算所組成的三角形各邊長以獲得最長邊。求其中點坐標，計算中點到三個錨節點距離，然后通過傳播模型計算三角形內最小信號強度和。過程如下:anchor_i(xi，yi), anchor_j(xj，yj),anchor_k(xk，yk)分別為錨節點坐標。

(4)

比較Dij、Dik、Djk，若Dij≥Dik≥Djk，取Dij中點M的坐標為：

(5)

計算：

(6)

求得：

Pmin=PR1(Dmi)+PR2(Dmj)+PR3(Dmk)

=3A-40log(Dmi×Dmj×Dmk)

(7)

4) 確定Pmin后，將鄰居節點收到的三個錨節點信號強度相加，同最小信號強度和Pmin作比較。若鄰居節點的信號強度和滿足同時大于或同時小于該最小信號強度和，則進行PIT測試。若不滿足，則對不滿足的鄰居節點進行下一組錨節點測試準備。重復步驟3)、步驟4)，直到所有錨節點組合測試完畢。

5) 利用網格掃描算法找出三角形重疊部分，對重疊區域求其質心作為待定位節點的坐標。

3算法仿真

本文采用MATLAB軟件對SAPIT算法和APIT算法進行仿真，算法流程如圖6所示。

圖6　算法流程圖

1) 傳感器節點部署區域為1000 m×1000 m的正方形區域。

2) 300個節點隨機分布在網絡區域，普通節點的通信半徑為200 m，錨節點的通信半徑為普通節點的2倍，即400 m。

網絡連通度：網絡連通度表示在未知節點通信范圍內的鄰居節點的個數。

圖7是錨節點個數為90，節點總數為300的隨機分布圖；圖8和圖9分別是用APIT算法和SAPIT算法得到的定位誤差圖。

將圖8和圖9進行對比可以發現，相比于APIT算法，SAPIT算法的定位誤差更小。在APIT算法中，由于存在較嚴重的邊界效應，導致PIT測試不準確，有效三角形判斷錯誤，從而產生多個重疊區域。這使得APIT算法的定位誤差不僅表現為數值較大，而且具有多個方向值。SAPIT算法通過判斷鄰居節點的合法性，在很大程度上抑制了邊界效應的發生，使PIT測試更加準確，重疊區域較好地反映了節點的實際位置，使定位更加精準。

圖10為APIT算法和SAPIT算法在不同網絡連通度下歸一化的平均誤差(定位誤差和通信半徑之比)的比較。

圖7　節點分布圖　　　　　　圖8　APIT定位誤差圖

圖9　SAPIT定位誤差圖　　　圖10　不同連通度下的誤差

從圖10可以看出，在連通度較低的情況下，SAPIT算法比APIT算法定位精度要高，此時影響定位精度的因素絕大部分是 Out-To-In Error，這說明SAPIT算法在一定情況下有效地抑制了Out-To-In Error，具體情況如圖11所示。

隨著網絡連通度的增加，Out-To-In Error對精度的影響程度減小，In-To-Out Error對精度影響程度加大。從圖10可以看出，隨著連通度增加，APIT算法的定位誤差出現反彈現象，這是由于隨著鄰居節點的增加，致使APIT算法發生In-To-Out Error概率增大，從而導致短時間內誤差增大。而SAPIT算法的定位誤差沒有出現反彈現象，這是由于在PIT測試前，通過把鄰居節點的合法性進行判定，把不符合要求的鄰居節點排除，再進行PIT測試，避免了大部分In-To-Out Error，較好地控制了反彈現象。從圖10中還可以看出，在網絡連通度達到10以后，SAPIT算法定位精度明顯高于APIT算法定位精度，說明對In-To-Out Error很好地解決，大大提高了定位精度。

圖12是節點總數為300個，不同錨節點個數的情況下兩種算法歸一化的平均誤差(定位誤差和通信半徑之比)的比較。

圖11　特殊的Out-To-In Error　圖12　不同錨節點數目下的誤差

圖12表明，當錨節點個數占總體比為10%左右時，APIT算法和SAPIT算法定位誤差都較大。這是由于錨節點比例較小，很多未知節點不能收到錨節點信息所導致的。當錨節點數目逐漸增多，可以看到SAPIT算法定位精度有顯著提升。其原因是SAPIT算法有效地解決了In-To-Out Error，并在一定程度上減少了Out-To-In Error，使有效三角形的數量增多，錯誤三角形的數量減少，三角形重疊部分質心很好地反映了未知節點的具體位置。在仿真實驗中，隨著錨節點數目的增加，定位時間加長，故選取最大錨節點個數占總體比例的50%，相較于APIT算法，SAPIT算法將定位精度提高了14%左右。

4結語

本文針對APIT算法中存在In-To-Out Error和Out-To-In Error，提出了一種基于節點信號強度和的SAPIT算法。仿真結果表明，SAPIT算法較于APIT算法，有效地提高了定位精度。相較于其他的APIT改進算法，SAPIT算法不需要結合其他定位算法，也不需要進行大量的計算和三角形分割，有效地節省了傳感器的能量，在實際應用中具有廣闊前景。但SAPIT算法仍有不足，改進算法只對一定情況下的Out-To-In Error進行了修正。下一步的工作將集中針對Out-To-In Error做出更精確的修正，提高算法的定位精度。

參考文獻

[1] Guo Y,Liu Y.Localization for anchor-free underwater sensor networks[J].Computers & Electrical Engineering,2013,39(6):1812-1821.

[2] Zhang G,Ding Y,Xu J,et al.Tracking Algorithm of WSN Based on Improved Particle Filter[C]//2012 11thInternational Symposium on Distributed Computing and Applications to Business,Engineering & Science (DCABES).Guilin China:IEEE,2012:149-152.

[3] Zheng J,Wu C,Chu H,et al.An Improved RSSI Measurement In Wireless Sensor Networks[J].Procedia Engineering,2011(15):876-880.

[4] Luo X,Liu Y,Long C,et al.Range-free localization algorithms in wireless sensor networks[C]//Fifth International Conference on Machine Vision (ICMV 12).Wuhan China:SPIE,2013:87842A-8.

[5] Xiangqun L,Heng G,Linlin L.An improved APIT algorithm based on direction searching[C]//2009 5thInternational Conference on Wireless Communications,Net-working and Mobile Computing (WiCOM).Beijing China:IEEE,2009:1-4.

[6] He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9thannual international conference on Mobile computing and networking.San Diego CAUSA:ACM,2003:81-95.

[7] 周勇,夏士雄,丁世飛,等.基于三角形重心掃描的改進APIT無線傳感器網絡自定位算法[J].計算機研究與發展,2009,46(4):566-574.

[8] 韓彪,徐昌彪,袁海,等.無線傳感器網絡中一種改進的APIT定位算法[J].計算機工程與應用,2008,44(4):122-124.

[9] 王新生,廖世奇.基于區域分割的無線傳感器網絡定位算法[J].計算機應用與軟件,2013,30(4):231-234.

[10] Wang J,Jin H.Improvement on APIT localization algorithms for wireless sensor networks[C]//International Conference on Networks Security,Wireless Communications and Trusted Computing (NSWCTC 2009).Wuhan.NY:IEEE,2009,1:719-723.

[11] Zeng F,Yu M,Zou C,et al.An Improved Point-in-Triangulation Localization Algorithm Based on Cosine Theorem[C]//Wireless Communications,Networking and Mobile Computing (WiCOM),2012 8th International Conference on.Shanghai China:IEEE,2012:1-4.

[12] Xiufang F,Huibo Q.Improvement and Simulation for a Localization Based on APIT[C]//2009 International Conference on Computer Technology and Development (ICCTD 2009).Kota Kinabalu Malaysia:IEEE,2009,2:68-72.

[13] 冀常鵬,陳美玲.無線傳感網絡APIT定位算法的改進[J].儀表技術與傳感器,2012,8(8):84-86.

[14] 馮秀芳,崔秀鋒,祈會波.無線傳感器網絡中基于移動錨節點的APIT的改進定位算法[J].傳感技術學報,2011,24(2):269-274.

[15] Chiti F,Pierucci L.API 2 T:a bit of improvement for applications in critical scenarios[C]//Proceedings of the 6th International Wireless Communications and Mobile Computing Conference.Chengdu China:ACM,2010:794-798.

[16] 姚艷,禹繼國,郭強.基于網格掃描的無線傳感器網絡定位算法[J].計算機工程,2012,38(9):86-89,96.

[17] Tan H,Liu F.Research and implementation of APIT positioning algorithm in WSN[C]//2012 9thInternational Conference on Fuzzy Systems and Knowledge Discovery (FSKD).Chongqing:IEEE,2012:2212-2215.

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

[19] Zhang S,Cao J,Zeng Y,et al.On accuracy of region based localization algorithms for wireless sensor networks[J].Computer Communications,2010,33(12):1391-1403.

[20] Chen B,Sun J,Xu W B,et al.A Mixed Localization Algorithm Based on RSSI and APIT with Fitness Analysis and Optimization[C]//2012 11th International Symposium on Distributed Computing and Applications to Business,Engineering & Science (DCABES).Guilin China:IEEE,2012:164-168.

[21] Chengxu F,Zhong L.A New Node Self-Localization Algorithm Based RSSI for Wireless Sensor Networks[C]//2013 Fifth International Conference on Computational and Information Sciences (ICCIS).Shiyan China:IEEE,2013:1616-1619.

[22] Wang S S,Shih K P,Chang C Y.Distributed direction-based localization in wireless sensor networks[J].Computer Communications,2007,30(6):1424-1439.

中圖分類號TP393

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.025

收稿日期：2014-08-11。國家自然科學基金項目(61172144)。冀常鵬，教授，主研領域：計算機通信，無線網絡。豐竹松，碩士生。華一陽，碩士生。