汪華斌，曾少寧，羅偉

（1.惠州學院 計算機科學系，廣東 惠州 516007；2.華南理工大學 電子與信息學院，廣東 廣州 510640；3.惠州學院 教育技術(shù)中心，廣東 惠州 516007）

引言

無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）是在無線自組織網(wǎng)絡基礎上發(fā)展起來的一種網(wǎng)絡，作為物聯(lián)網(wǎng)不可或缺的一部分，極具發(fā)展前景。隨著技術(shù)的不斷完善和成熟，行業(yè)對無線傳感器網(wǎng)絡的應用需求與日俱增。在軍事作戰(zhàn)、環(huán)境監(jiān)測、搶險救災，大型建筑安全監(jiān)測等方面，正確定位是無線傳感器網(wǎng)絡中節(jié)點捕獲感知事件發(fā)生位置的重要前提［1］，因此節(jié)點定位算法的研究具有極其重要意義，涉及傳感器節(jié)點的定位及應用也因此成為業(yè)界的一個研究熱點［2，3］。目前節(jié)點定位主要分兩類：基于測距的定位算法（Ranged-based Methods）和非測距的定位算法（Ranged-free Methods）［4］。前者通過信號強度或角度等信息得到較為精準的位置信息，但增加了額外硬件，產(chǎn)生了大量計算和通信開銷；后者主要依靠網(wǎng)絡布局和連通性等信息進行定位，精度較差，能耗低［5］。典型的基于測距的定位算法主要有：基于到達角度的定位算法（Angle of Arrival，AOA），基于到達時間的定位算法（Time of Arrival，TOA），基于到達時間差的定位算法（Time Difference of Arrival，TDOA）和基于信號接收強度指示RSSI（Received Signal Strength Indication）的定位算法［6］。

1 RSSI測距基本概念

RSSI測距技術(shù)是一種低功率、廉價、使用方便的測距技術(shù)［7］。RSSI測距技術(shù)易受到各種環(huán)境因素的影響，定位精確度普遍較低。相對單純的非測距算法，RSSI增加了額外的有用信息，定位精度有所提高，且RSSI值的獲取過程簡單，因而RSSI測距成為目前使用較為廣泛的一種位置估算方法。同時，由于無須測量節(jié)點間的絕對距離或方位，降低了對節(jié)點硬件的要求，使其更適合于大規(guī)模無線傳感器網(wǎng)絡［1］。RSSI根據(jù)所在環(huán)境中的無線傳感器網(wǎng)絡節(jié)點的接收信號強度指示來進行定位，其單位為dbm。在RSSI定位中，通常已知發(fā)射節(jié)點的發(fā)射信號強度，接收節(jié)點則根據(jù)收到信號的強度，計算出信號的傳播損耗，利用相關(guān)理論和經(jīng)驗模型將傳輸損耗轉(zhuǎn)化為距離，再利用已有的算法計算出節(jié)點的位置。目前由于無線傳感器網(wǎng)絡節(jié)點自身硬件普遍具備RSSI感知能力，因此采用RSSI定位無須額外增加硬件投入［8］。

實際環(huán)境中，由于多徑、障礙物、繞射等因素隨機存在，其損耗模型通常由經(jīng)驗模型替代，經(jīng)驗模型具有較強的針對性，往往也只適用于某一場景，目前RSSI定位常采用對數(shù)——常態(tài)分布模型（log-distance distribution）［9，10］。

通過對無線信號傳播的衰減模型評估與參數(shù)修正，根據(jù)RSSI值，得到對位置距離節(jié)點的距離估算公式為：

上述公式為經(jīng)典的距離RSSI與d的計算關(guān)系。公式中：d0是參考點距發(fā)射點的距離，通常采用1米時的值代替，d是接收點距發(fā)射點的距離，n為路徑損耗指數(shù)，一般取2～4。Χ?是一個單位為dbm，標準差為?的服從正太高斯分布的隨機變量，反映了當距離一定時接收到的信號變化，標準范圍4～10。

2 極大使然法

在三維空間中，若已知4個或4個以上的已知錨節(jié)點與未知節(jié)點的距離，就可以計算出未知節(jié)點的坐標位置。在測量時，只要多次測量得到的距離個數(shù)大于變量的個數(shù)，就可以采用極大使然法來進行估算，這就是通常所說的多邊測距方法。為簡化計算，本文采用二維空間。假定未知節(jié)點坐標為(x，y)，已知錨節(jié)點的坐標為ki(xi，yi)，其中i=l，2，…n，di為第i個錨節(jié)點到未知節(jié)點的距離，下列方程組成立：

上述方程組可以寫成線性方程組的形式AX=b，求解得到：

其中：

3 PSO粒子群優(yōu)化算法

3.1 PSO算法概述

粒子群優(yōu)化（Partical Swarm Optiminal，PSO）算法是一種群智能算法。在1995年，由美國的Eberhart博士和Kennedy博士受鳥類群體覓食行為的影響共同提出。與遺傳算法類似，是一種基于迭代的優(yōu)化工具。粒子群算法將每個個體看成是D維搜索空間的一個隨機解，并以一定的速度飛行。粒子飛行速度由個體自身的飛行經(jīng)驗與群體的飛行經(jīng)驗進行動態(tài)調(diào)整，最后通過多次迭代找到最優(yōu)解。

其中：Vi(t)為粒子i在t輪的速度，ω為慣性權(quán)重，c1、c2為學習因子，r1、r2為0～1之間的隨機數(shù)，pi(t)為個體的歷史最優(yōu)位置，pg(t)為群體的最優(yōu)位置。

3.2 適應值函數(shù)及定位應用

假設二維空間中有N個節(jié)點，其中m個為錨節(jié)點。錨節(jié)點的坐標為ki(xi，yi)，其中i=l，2，…m，而未知節(jié)點坐標為(x，y)?？梢园盐粗?jié)點的坐標估計看成是一個優(yōu)化求解的過程，將迭代計算適應值函數(shù)的最小值來求出未知節(jié)點的坐標位置。假定未知節(jié)點到錨節(jié)點間的距離為d，d為測量或估算的距離，而不是真實距離，因此問題可歸納為優(yōu)化求解的過程。其中最優(yōu)解應滿足公式（7）：

網(wǎng)絡布署后，錨節(jié)點以周期性向相鄰節(jié)點發(fā)送自己的信息（節(jié)點id+坐標信息）。未知的節(jié)點接收并記錄鄰居連通錨節(jié)點的相關(guān)信息，根據(jù)RSSI模型公式估算出自身與錨節(jié)點間的距離d。連接收到3個以上的錨節(jié)點信息后，利用公式（7）計算適應值，運行PSO粒子算法進行求優(yōu)，通過求優(yōu)得到自身定位誤差最小的結(jié)果。

4 仿真實驗

4.1 計算誤差公式

設未知節(jié)點實際位置為（x，y），通過定位算法計算出的位置為(xe，ye)，定義誤差公式為：

其中r為無線傳感器網(wǎng)絡的通信半徑。

4.2 仿真實驗步驟

為計算簡便，采用二維空間，對于上述測距思想，設計如下步驟

（1）在仿真場景中隨機產(chǎn)生m個錨節(jié)點ki（xi，yi）（i=1，2……m），及未知節(jié)點真實坐標為（x，y）。

（2）根據(jù)未知節(jié)點接收到來自錨節(jié)點（xi，yi）的信標幀信息，記錄錨節(jié)點RSSI值，其中誤差區(qū)間為（-0.05，0.05）。根據(jù)RSSI測距公式（2）得到錨節(jié)點與未知節(jié)點（x，y）的估算距離di。

（3）通過已知錨節(jié)點的坐標（xi，yi）及到未知節(jié)點（x，y）的估算距離di，用極大使然法計算出未知節(jié)點的坐標（x'，y'）；

（4）利用已知錨節(jié)點到未知節(jié)點的估算距離di，根據(jù)適應值函數(shù)式（7），利用PSO粒子群優(yōu)化算法，通過多次迭代，計算出未知節(jié)點的坐標（x"，y"）。

（5）利用公式（8）計算定位誤差。

4.3 仿真實驗環(huán)境與結(jié)果分析

實驗采用NS2+MATLAB平臺進行仿真，對提出的測距定位算法性能進行研究。在仿真實驗環(huán)境中加入了均值為0，方差為11.8的高斯噪聲［11］。仿真平臺設定為一個50m*50m的二維區(qū)域，通信半徑采用NS2中的默認值250米，實驗場景設定為10個。每個場景隨機產(chǎn)生21個節(jié)點，其中錨節(jié)點20個，未知節(jié)點1個，每個場景仿真100次，取平均值作為最后實驗結(jié)果。PSO粒子群采用文獻［12］中所描述的參數(shù)，如表1所示。實驗結(jié)果如表2所示。

表1 PSO粒子群優(yōu)化算法參數(shù)

表2定位結(jié)果

從表2可以看出，由于RSSI測量定位技術(shù)本身存在誤差，兩種算法的定位結(jié)果均不可避免的存在誤差，其中極大使然法的平均誤差為0.9978%，比粒子群優(yōu)化算法的誤差0.5180%更大。PSO粒子群優(yōu)化算法由于采用了多次迭代的方法，有效的減小了誤差。

5 結(jié)束語

節(jié)點定位問題作為無線傳感器網(wǎng)絡捕獲安全故障事件所發(fā)生位置的一個重要前提，一直備受關(guān)注。目前許多應用對于節(jié)點定位精度要求越來越高，如何利用最小的成本獲取最大的定位精度是定位算法的研究目標。對于多維空間的節(jié)點定位，為提高定位精度，引入了PSO粒子群優(yōu)化算法。首先利用RSSI測距技術(shù)得到未知節(jié)點到錨節(jié)點的距離，再根據(jù)PSO粒子群優(yōu)化算法估算出未知節(jié)點的坐標，仿真結(jié)果表明引入PSO算法有效的減小了定位的誤差。

［1］王茂臣，樊秀梅.單個錨節(jié)點的路徑規(guī)劃機制及定位方法研究［J］.天津科技大學學報，2013，28(2)：74-78.

［2］金彥亮，薛用，張勇.基于RSSI的WSN節(jié)點室內(nèi)定位分析［J］.上海大學學報自然科學版，2012，8(5)：470-474.

［3］李牧東，熊偉，郭龍.基于最優(yōu)跳距處理策略的無線傳感器網(wǎng)絡智能定位算法［J］.計算機應用，2012，32(7)：1836-1839.

［4］VODMN，VOD，CHALLAS，et al.Nonmetric MDS for sensor localization［J］.Procof the 3rd International Symposium on Wireless Pervasive Computing，2008，：396-400.

［5］杜娟娟.無跡卡爾曼濾波在無線傳感器網(wǎng)絡節(jié)點定位中的應用［J］.南京郵電大學學報（自然科學版），2013，33(1)：84-90.

［6］趙雁航，錢志鴻，尚小航等.基于跳距修正粒子群優(yōu)化的WSN定位算法［J］.通信學報，2013，34(9)：105-114.

［7］LUTHY K A，Grant E;Henderson T C.Leverging RSSI for Robotic Repair of Disconnected Wireless Sensor Networks［J］.Proceeding of 2007 IEEE International Conference on Robotics and Automation.Rome，Italy，2007，1（10）：10-14.

［8］張亞明，史浩山，程偉等.一種無線傳感器網(wǎng)絡中的進化定位機制［J］.西北工業(yè)大學學報，2013，31(4)：633-638.

［9］NIGEL DACVIES，KEITH CHEVERST，KEITHMITCHDL，et al.Using and Determining Location in a Context-sensitive Tour Guide［J］.IEEE Computer，2011，34(8)：135-41.

［10］張潔穎，王俠.基于與的動態(tài)距離估計算法［J］.電子測量技術(shù)，2007，30(2)：142-145.

［11］尚少鋒，張雪英，王峰.一種基于RSSI校正的加權(quán)質(zhì)心定位算法［J］.科學技術(shù)與工程，2013，13(10)：2832-2835，2840.

［12］XU Lei，ZHANG Huimin，SHI Weiren.Mobile Anchor Assisted Node Localization in Sensor Networks Based on Particle Swarm Optimization［J］.Progress in Informatics and Computing(PIC)，2010 IEEE International Conference，2010，：495-498.