基于靜態無線傳感器網絡的APIT改進算法

楊凌云，馮友宏，王再見

(安徽師范大學 物理與電子信息學院,安徽 蕪湖 241000)

?

基于靜態無線傳感器網絡的APIT改進算法

楊凌云，馮友宏，王再見

(安徽師范大學 物理與電子信息學院,安徽 蕪湖 241000)

摘要：在靜態無線傳感器網絡中，傳統的APIT算法認為未知節點是在由錨節點組成的三角形內部的，在這種前提下得到未知節點的位置判斷結論的判斷存在著很大的位置判別誤差，從而影響了未知節點定位的精度，為了減少這種判別錯誤的出現，在傳統APIT算法的基礎上提出了一種基于三角形面積判別的方法，同時通過對能量值加權的質心算法估計出未知節點的坐標。同時通過Matlab對算法進行了仿真比較，該方法在一定程度上提高了定位精度，減少了估計誤差。

關鍵詞：APIT算法；面積判決；精度；質心定位；能量值加權

0引言

無線傳感器網絡是一種低損耗的無線網絡傳輸技術[1]，它在很多領域特別是人類無法親自到達的區域進行信息跟蹤、數據采集等方面發揮著重要作用[2]。在這些地區，節點是隨機播撒在指定區域的各個地方的，節點在初始狀態下是不知道自身位置的，而節點沒有自身位置信息是沒有辦法實現數據采集等工作的，節點自身定位是實現數據采集的非常關鍵的一個初始化行為。目前研究的節點自身定位方法根據是否與距離有關[2]，可以分為兩大類：與距離有關的定位和與距離無關的定位方法[3]，其中APIT技術是一種典型的與距離無關的定位算法之一。它適合于高密度的節點自身定位，而且思想簡單，容易實現，是目前比較有優勢的一種自身定位算法[4]。本文針對APIT算法中對未知節點的是否在錨節點組成的三角形內部的判斷提出自己的觀點，它可獲得更好的精度估計[5]。

1APIT算法

APIT算法中的PIT測試的核心思想就是在定位之前首先要確定要定位的未知節點是否在3個錨節點組成的三角形的內部，如果在就執行相關算法，估計出未知節點的值；如果不在，則認為是不合格的錨節點三角形，不予計算。這樣就無形中提高了定位精度，剔除了一些誤差比較大的估計值。但它是相對于動態節點的，如果未知節點同時遠離或者靠近3個錨節點，那么節點就在三角形外，否則就在三角形內部[6,7]。但對于靜態網絡而言，節點位置相對來說是靜止的，這種方法行不通，后來就有人提出通過比較這個未知節點的鄰居節點與錨節點的距離關系[8]，如果鄰居節點與錨節點距離同時大于或者小于未知節點與錨節點的距離，認為在三角形外部，否則認為在三角形內部[9-11]。

同時，在上面in-out判別算法的基礎上，找出所有未知節點在錨節點組成的三角形內部的集合，計算所有集合的中心，估計出位置信息[12,13]。所以可以看到in-out判別方法和精確度直接關系著位置估計的精度，是一個非常關鍵的環節。針對PIT測試估計在一些極端情況下容易出現較大誤差[14,15]，比方說，未知節點比較靠近錨節點組成三角形的一個邊時，或者它的鄰居節點位置比較分散，造成未知節點和鄰居節點分別在三角形內部和外部時等[16,17]，提出一種新的基于三角形面積的in-out判斷方法(NA-APIT算法)。

2改進算法(NA-APIT)

定理：在圖1和圖2中分別給出了未知節點D在錨節點ABC組成的內部和外部2種情況，可以看到，圖1中未知節點在三角形內部時，未知節點和錨節點組成的新的三角的面積之和等于錨節點組成三角形的面積。而圖2中未知節點在錨節點外部時，面積之和大于錨節點面積。

圖1　未知節點在　　　　圖2　未知節點在　三角形內部　三角形外部

證明：錨節點進行信息傳遞時，傳遞的信息包括節點能量信息和節點自身的位置信息，那么根據通用的能量傳遞公式，能量的傳遞與距離的平方是成反比例的關系，

即：

(1)

式中，E1為到達未知節點的能量，E0為錨節點發送時刻的能量，d1為未知節點與錨節點的距離，k為一常數，它與信號波長，傳輸環境等信息有關，特定的條件下為一常數，用k表示。

通過能量比值很容易得到未知節點到錨節點的相對精確的距離值，這樣很容易得到三角形面積值，通過面積比較久可以得出未知節點D是否在錨節點組成的三角形的內部。

3改進后NA-APIT的算法流程

①所有的錨節點在通信半徑范圍內，向各個方向廣播自己的節點位置信息和初始能量信息。

②未知節點把接收到的能量信息和初始能量信息相比較，并通過式(1)計算出未知節點到相對應錨節點的距離值。

④根據三角形加權質心定位算法，估計出這組估計值。這里提出一種精度更高的權值計算方法，即

三角形質心加權定位估計值為：

(2)

這里設三角形的3個點分別是A點(坐標(xA,yA))、B點坐標(xB,yB)和C點坐標(xC,yC)，未知節點到這3個錨節點的距離分別為d1、d2和d3。

⑥對所有符合條件的關于未知節點的估計值求平均，設有m個估計值，則估計值為：

(3)

⑦與實際的位置信息相比較，計算出估計誤差：

(4)

式中，(x，y)為未知節點的實際二維坐標。

4算法仿真分析

在仿真實驗中，選取的仿真環境為100×100的一片區域，在未知節點和錨節點隨機分布在這篇區域，錨節點可以廣播自己的位置信息和能量信息，仿真參數為錨節點的個數和通信半徑，在不同的錨節點個數和不同的通信半徑下2種算法的誤差進行比較。

錨節點的個數為30個，節點通信距離從20~50 m之間的誤差值如圖3所示。從圖3可以看出，在圖中給出的通信范圍內，改進后的算法有效降低了誤差，提高了定位精度。

圖3　不同通信距離的誤差值比較

保持通信距離不變，錨節點的個數從30~60個之間的一個誤差值如圖4所示。錨節點個數的增加是每5個測試一次，從圖4中同樣可以得出結論：改進后的算法有效地降低了誤差，提高了定位精度。

圖4　不同錨節點個數的誤差比較

5結束語

APIT算法是一種經典的靜態無線傳感器節點的定位算法，它的優點在于未知節點的定位與距離無關，隨著對節點定位精度的提高，需要對其進行改進，針對APIT算法中未知節點與錨節點三角形位置關系的in-out判斷方法進行了改進，提出了基于三角形面積的in-out判斷方法，分別在改變距離和錨節點這2種條件下進行仿真，對2種算法進行誤差比較，結果表明該改進算法有效地提高了未知節點的定位精度。

參考文獻

[1]孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京：清華大學出版社，2005：151-152.

[2]Niculescu D，Nath B.DV based Positioning in Ad Hoc Networks[J].Journal of Tele- communication Systems，2003，22(1)：267-280.

[3]嵇瑋瑋,劉中.DV-Hop定位算法在隨機傳感器網絡中的應用研究[J].電子與信息學報,2008,30(4):970-974.

[4]Mechitov K，Sundresh S，Kwon Y， et al．Cooperative Tracking with Binary Detection Sensor Networks[C]∥Proceedings of the 1st Intemational Conference on Embedded Networked Sen-sor Systems，New York:ACM Press,2003:332-333．

[5]He Tian，Huang Cheng-du，Blum B M， et a1．Range-free Localization Schemes in Large Scale Sensor Networks[C]∥Proceedings of the 9th Annual International Conference on Mobile Computing and Networking MOBICOM’ 2003，San Diego，CA，USA，2003:81-95．

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

[7]Bulusu N，Heidemann J，Estrin D.GPS-less Low Cost Outdoor Localization for Very Small Devices[J]． IEEE Personal Communications Magazine， 2000,7(5):28- 34．

[8]Wang Jia，Fu Jingqi.Research on APIT and Monte Carlo Method of Localization Algorithm for Wireless Sensor Networks[C]∥Life System Modeling and Intelligent Computing，2010：128-137.

[9]孫庭波， 屈玉貴， 趙保華.一種無線傳感器網絡安全定位的新方法[J].小型微型計算機系統，2009,130 (9)：1738-1741.

[10]趙成林，毛松，譚虎.無線傳感器網絡能量均衡分簇路由協議[J].無線電工程，2011，41(3):1-4.

[11]陳愛斌，張陸勇，夏新蘭，等.無線傳感器網絡能量異構分簇算法的研究[J].無線電工程，2012，42(1):7-10.

[12]梁小滿，姜小奇，李英玲． 無線傳感器網絡節點的三維質心定位算法研究[J].通信技術，2009，42(2):121-123．

[13]趙清華，劉少飛，張朝霞，等.一種無需測距節點定位算法的分析和改進[J]．傳感技術學報，2010,23(1):122-127.

[14]萬國峰,鐘俊.基于三角形理論的無線傳感器網絡定位算法[J].計算機應用研究,2013,30(1):249-251.

[15]徐小玲,張福強,李少彪.基于APIT的無線傳感器網絡質心算法研究[J].傳感器與微系統,2011,30(7):57-59,63.

[16]俞黎陽,王能,張衛,等． 異構無線傳感器網絡中異構節點的部署與優化.計算機科學，2008,35(9):48-51．

[17]馮秀芳,關志艷,全欣娜.基于虛擬力的異構節點網絡覆蓋增強算法[J].計算機工程,2009(5):103-105.

Modified APIT Algorithm Based on Static Wireless Sensor Network

YANG Ling-yun,FENG You-hong,WANG Zai-jian

(College of Physics and Electronic Information,Anhui Normal University,Wuhu Anhui 241000,China)

Abstract：In static wireless sensor networks,the traditional APIT algorithm has a default consideration that the unknown sensor is inside the beacon triangle,and this may lead to serious error in position determination of the unknown sensor,which will influence the location precision.In order to reduce such errors,based on traditional APIT algorithm,the paper proposes a new method of energy weighting triangle area judgment to evaluate the unknown sensor’s position.Compared with the traditional APIT algorithm by Matlab,the result shows that the new method improves the location precision and reduces the estimation errors.

Key words：APIT algorithm; area judgment; precision; energy weighting

中圖分類號：TP393

文獻標識碼：A

文章編號：1003-3114(2016)02-20-3

作者簡介：楊凌云(1983—)，女，講師，主要研究方向：無線電網絡。馮友宏(1979—)，男，副教授，主要研究方向：無線電網絡。

基金項目：國家自然科學基金項目(61401004)

收稿日期：2015-12-03

doi:10.3969/j.issn.1003-3114.2016.02.05

引用格式：楊凌云，馮友宏，王再見.基于靜態無線傳感器網絡的APIT改進算法[J].無線電通信技術,2016,42(2):20-22.