基于靜態(tài)無線傳感器網(wǎng)絡(luò)的APIT改進算法

楊凌云，馮友宏，王再見

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

?

基于靜態(tài)無線傳感器網(wǎng)絡(luò)的APIT改進算法

楊凌云，馮友宏，王再見

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

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

關(guān)鍵詞：APIT算法；面積判決；精度；質(zhì)心定位；能量值加權(quán)

0引言

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

1APIT算法

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

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

2改進算法(NA-APIT)

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

圖1　未知節(jié)點在　　　　圖2　未知節(jié)點在　三角形內(nèi)部　三角形外部

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

即：

(1)

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

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

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

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

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

④根據(jù)三角形加權(quán)質(zhì)心定位算法，估計出這組估計值。這里提出一種精度更高的權(quán)值計算方法，即

三角形質(zhì)心加權(quán)定位估計值為：

(2)

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

⑥對所有符合條件的關(guān)于未知節(jié)點的估計值求平均，設(shè)有m個估計值，則估計值為：

(3)

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

(4)

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

4算法仿真分析

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

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

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

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

圖4　不同錨節(jié)點個數(shù)的誤差比較

5結(jié)束語

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

參考文獻

[1]孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，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定位算法在隨機傳感器網(wǎng)絡(luò)中的應(yīng)用研究[J].電子與信息學(xué)報,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]韓彪， 徐昌彪， 袁海， 等.無線傳感器網(wǎng)絡(luò)中一種改進的APIT 定位算法[J].計算機工程與應(yīng)用，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，F(xiàn)u 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]孫庭波， 屈玉貴， 趙保華.一種無線傳感器網(wǎng)絡(luò)安全定位的新方法[J].小型微型計算機系統(tǒng)，2009,130 (9)：1738-1741.

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

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

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

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

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

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

[16]俞黎陽,王能,張衛(wèi),等． 異構(gòu)無線傳感器網(wǎng)絡(luò)中異構(gòu)節(jié)點的部署與優(yōu)化.計算機科學(xué)，2008,35(9):48-51．

[17]馮秀芳,關(guān)志艷,全欣娜.基于虛擬力的異構(gòu)節(jié)點網(wǎng)絡(luò)覆蓋增強算法[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—)，女，講師，主要研究方向：無線電網(wǎng)絡(luò)。馮友宏(1979—)，男，副教授，主要研究方向：無線電網(wǎng)絡(luò)。

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

收稿日期：2015-12-03

doi:10.3969/j.issn.1003-3114.2016.02.05

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