束仁義，沈曉波，葛先雷，蔡 俊

(淮南師范學(xué)院電子工程學(xué)院，安徽淮南，232038)

定位技術(shù)是無線傳感器網(wǎng)絡(luò)重要的支撐技術(shù)［1］。所謂定位就是確定節(jié)點的具體位置，而在無線傳感器網(wǎng)絡(luò)定位技術(shù)中，每個節(jié)點都有預(yù)先確定的位置是不可取的，同時為每個節(jié)點配置GPS設(shè)備也是不現(xiàn)實的，因為考慮到成本和具體的環(huán)境問題。因此，無線傳感器網(wǎng)絡(luò)節(jié)點的定位研究在實際應(yīng)用中具有重要的意義。

定位方法的探索與應(yīng)用一直以來都備受國內(nèi)外專家和學(xué)者的重視，近年來在定位算法的研究上已取得了一些成績和進步。例如，江南大學(xué)的熊偉麗、唐蒙娜、徐保國提出了一種基于最優(yōu)加權(quán)最小二乘估計的節(jié)點定位改進方法，此方法能有效抑制累積誤差中測距誤差與定位誤差帶來的影響，提高了節(jié)點定位精度［2］;重慶大學(xué)的何小敏、熊慶宇、石為人等提出一種基于網(wǎng)格劃分的遞增式定位算法，該算法能夠有效地解決累計誤差和能耗問題，提高全網(wǎng)定位的效率［3］;越南海防私立大學(xué)的Trong－The Nguyen，Thi－Kien Dao和澳大利亞佛林德斯大學(xué)的John F.Roddick等人提出一種基于多目標(biāo)螢火蟲算法的智能定位算法，它能夠提高定位精度［4］?？傊?，無線傳感器網(wǎng)絡(luò)定位算法的研究一直在進行中，尤其在改善定位精度方面將持續(xù)跟進，不斷更新算法或改進成熟的定位技術(shù)。

近年來，業(yè)界提出了一種新型的智能算法——蝙蝠算法。蝙蝠算法的基礎(chǔ)近似使用以下基本規(guī)則［5］:

(1)所有蝙蝠使用回聲來感知距離，它們能夠以一種不可思議的方式來辨別食物和障礙物;

(2)蝙蝠在某個位置xi，具有最小頻率fmin，以速度vi隨機飛行，通過變化的波長λ和脈沖響度A0來搜索食物。它們能夠自動地調(diào)節(jié)發(fā)射脈沖的波長，其中調(diào)節(jié)脈沖發(fā)射率γ∈［0，1］，它取決于蝙蝠對目標(biāo)的接近程度;

(3)盡管脈沖響度能夠以不同方式來變化，我們均假設(shè)脈沖響度變化從一個大的(正的)值A(chǔ)0連續(xù)變化到一個最小值A(chǔ)min。

蝙蝠算法比常見的粒子群算法具有更好的性能［6］，因此文中將蝙蝠算法應(yīng)用到無線傳感器網(wǎng)絡(luò)節(jié)點遞增定位方法中，并和常見的三邊定位算法進行比較，通過Matlab軟件仿真，在三維空間(3D)區(qū)域進行定位精度的對比。仿真實驗表明基于蝙蝠算法的遞增定位較成熟的三邊定位算法在定位精度上有所提高。

1 定位技術(shù)

1.1 三邊測量方法

無線傳感器網(wǎng)絡(luò)節(jié)點定位方法可以分為基于距離測量和距離無關(guān)兩類［7］。最常見的定位方法是基于距離測量的定位方法，距離測量常用RSSI算法，而節(jié)點的具體位置坐標(biāo)通常用三邊測量方法獲得。

圖1 節(jié)點定位圖示Fig.1 Diagram of node location

節(jié)點一般分為錨節(jié)點(或稱已知節(jié)點)和盲節(jié)點(或稱未知節(jié)點)兩種。設(shè)在一個3D區(qū)域內(nèi)有若干個節(jié)點，設(shè)某個盲節(jié)點M坐標(biāo)為(x，y，z)，在有效通信半徑范圍內(nèi)取四個錨節(jié)點 P1、P2、P3 和 P4，對應(yīng)的坐標(biāo)分別為 (x1，y1，z1)、

(x2，y2，z2)、(x3，y3，z3) 和(x4，y4，z4) ，四個錨節(jié)點剛好位于同一個球面上，而盲節(jié)點則是球心，如圖1所示。

假設(shè)測得M到P1、P2、P3和P4的距離分別為d1、d2、d3和d4，根據(jù)距離公式可得:

求得盲節(jié)點M的坐標(biāo)為:

1.2 逐步遞增式定位

無線傳感器網(wǎng)絡(luò)節(jié)點定位方法也可以分為并發(fā)式和遞增式。如果節(jié)點數(shù)目多，覆蓋范圍廣，通過人工測量手段獲取大量節(jié)點的位置信息是不可取的，這時往往采用遞增式定位方法［8］。逐步遞增式定位的基本思想是:初始少量節(jié)點作為參考節(jié)點，其余節(jié)點均為未知節(jié)點，在通信范圍內(nèi)，通過參考節(jié)點來求未知節(jié)點的坐標(biāo)，再將已定位的未知節(jié)點作為參考節(jié)點并進行下一級的定位，逐級定位直至所有的盲節(jié)點都已成為已知節(jié)點。

假設(shè)3D區(qū)域內(nèi)有L個節(jié)點，初始參考節(jié)點數(shù)為L0(4≤L0≤L)，L和L0均為正整數(shù)，則盲節(jié)點數(shù)目為L－L0。設(shè)初始參考節(jié)點集合為:

設(shè)逐步遞增定位中第j(j=0，1，2，…，k)次參考節(jié)點的集合為:

其中N1，N2，…，Nj分別表示每一步遞增定位的節(jié)點。用T(.)表示遞增式定位算法，則有:

其中D表示測距集合，以矩陣形式存儲任意兩個節(jié)點的距離值，因此D是一個方陣。由于每個節(jié)點都有唯一的標(biāo)識號，故D可寫成:

其中dmn(1≤m≤L，1≤n≤L)表示標(biāo)識號第m個節(jié)點到第n個j節(jié)點的距離，則有關(guān)系式:D=DT;dmn=0(m=n)。

2 蝙蝠算法

根據(jù)蝙蝠算法遵循的基本規(guī)則，我們模擬蝙蝠的虛擬運動。首先我們在3D中對蝙蝠的位置和飛行速度進行實時控制并更新，假設(shè)在t時刻的位置和速度分別記為和，則有:

其中 β∈［0，1］，和分別表示t+1時刻的速率與位置，x*是當(dāng)前全局的最優(yōu)解。

其中α和γ是常數(shù)。對于任意0＜α＜1以及γ＞0，當(dāng)t→!時有:

因此，蝙蝠算法的偽代碼［9］描述如下:初始化蝙蝠種群數(shù)xi和vi(i=1，2，…，n);初始化頻率fi，脈沖發(fā)射率ri和聲音響度Ai;while(小于最大迭代次數(shù))

通過調(diào)節(jié)頻率來產(chǎn)生新的解;

根據(jù)式(7)、(8)、(9)更新速率和位置;

if(rand＞ri)

在最優(yōu)解中選擇一個解;

從選擇的最優(yōu)解中產(chǎn)生一個局部解;

end if

通過隨機飛動產(chǎn)生一個新解;

if(rand＜Ai＆f(xi)＜f(x*))

接受這個新解;

增加ri并減少Ai;

end if

對所有蝙蝠進行排列并找到

當(dāng)前最好的解x*;

end while

3 算法仿真

3.1 基于蝙蝠算法的遞增式定位流程

由于實際測距可能存在誤差，式(1)中的距離值就不是真實值，求出的位置點的坐標(biāo)也就有偏差，因此3D定位問題可以轉(zhuǎn)化為求目標(biāo)函數(shù)

最小值的優(yōu)化問題，我們可以利用蝙蝠算法去求解。

假設(shè)盲節(jié)點的真實位置為(x，y，z)，根據(jù)定位算法求得的解為(x'，y'，z')，則定位誤差ε定義為:

算法流程如下圖2所示:

3.2 仿真實驗

在Matlab 2010b中進行仿真實驗，3D仿真區(qū)域為50m×50m×50m，隨機分布200個節(jié)點，初始參考節(jié)點數(shù)為4，其余均為盲節(jié)點數(shù)。蝙蝠算法的參數(shù)及對應(yīng)的初始值如下表1所示。

圖2 基于蝙蝠算法遞增定位流程圖Fig.2 Flowchart of increasing localization based on bat algorithm

表1 蝙蝠算法參數(shù)Table 1 Parameters of bat algorithm

假設(shè)節(jié)點在無測距誤差且通信距離不限(即遞增定位級數(shù)為1)環(huán)境下利用蝙蝠算法進行定位，得到如下圖3所示的仿真結(jié)果。

圖3仿真結(jié)果表明基于蝙蝠算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位可以取得很好的定位效果，因此，可以將蝙蝠算法應(yīng)用到遞增式定位算法中。假設(shè)節(jié)點在有測距誤差且通信距離不限環(huán)境下，再利用蝙蝠算法定位并和三邊定位法進行比較，得到如圖4所示的定位節(jié)點誤差對比圖。

圖3 基于蝙蝠算法3D定位仿真Fig.3 Simulation of positioning based on bat algorithm in 3D

圖4 基于三邊測量法與蝙蝠算法初步定位誤差對比Fig.4 Comparison of positioning error in the first step based ontrilateration and bat algorithm

圖4表明在有測距誤差的環(huán)境下，基于蝙蝠算法的定位要比三邊測量法的定位在總體定位精度上要高。假設(shè)節(jié)點通信距離為30m，則在測距誤差環(huán)境下，由于遞增式定位隨著級數(shù)的增加，定位誤差也累積增大，將三邊測量法與蝙蝠算法各級節(jié)點比較，得到如圖5所示的節(jié)點誤差對比圖。圖5表明在級數(shù)開始的時候，基于蝙蝠算法的定位要比三邊測量法的定位在定位精度上要稍好些，但是隨著累計誤差增加，定位精度也逐漸降低，甚至某些點的定位效果已經(jīng)不理想。

圖5 基于三邊測量法與蝙蝠算法多級遞增定位誤差對比Fig.5 Comparison of positioning error step by step based on trilateration and bat algorithm

綜上實驗結(jié)果可知:基于蝙蝠算法和測距原理的逐步遞增定位在4個參考節(jié)點的初始條件下能夠定位出所有的盲節(jié)點。因此，通過和其它文獻提出的定位算法比較，文中應(yīng)用的定位算法比文獻［2］的遞增定位需要更少的初始參考節(jié)點，相對文獻［3］的算法產(chǎn)生更少的累積誤差且搜索速率更快，定位耗時短。

4 結(jié)束語

針對傳統(tǒng)的三邊測量法在定位精度上的不足，提出將基于全局優(yōu)化的蝙蝠算法應(yīng)用到無線傳感器網(wǎng)絡(luò)節(jié)點遞增式定位中。通過實驗仿真，蝙蝠算法可以很好地應(yīng)用在3D定位中，相比于三邊測量法，定位精度有較明顯地改善，特別在遞增定位的前幾級，累積誤差也相對較小。因此，蝙蝠算法為無線傳感器網(wǎng)絡(luò)節(jié)點遞增式定位提供了一種較好的技術(shù)方案。

參考文獻:

［1］孫利民.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.

［2］熊偉麗，唐蒙娜，徐保國.一種用于無線傳感器網(wǎng)絡(luò)節(jié)點遞增式定位的新方法［J］.傳感技術(shù)學(xué)報，2011，24(04):576－580.

［3］何小敏，熊慶宇，石為人，等.基于網(wǎng)格劃分的遞增式定位算法［J］.計算機應(yīng)用研究，2012，29(02):687－689.

［4］NGUYEN TT，PAN JS，CHU SC，et al.Optimization Localization in Wireless Network Based on Multi－Objective Firefly Algorithm［J］.Journal of Network Intelligence，2016，1(04):130－138.

［5］YANG X.Bat Algorithm for Multi－objective Optimization［J］.International Journal of Bio－Inspired and Computation，2011，3(05):267－274(8).

［6］李煜，馬良.新型全局優(yōu)化蝙蝠算法［J］.計算機科學(xué)，2013，40(09):225－229.

［7］王行甫，劉志強，黃秋原，等.WSN中一種改進的邊界盒定位算法［J］.計算機工程，2011，37(20):57－59.

［8］CHEN S，YU Y.Incremental localization algorithm based on distance matrix in wireless sensor networks［J］.International Journal of Information and Communication Technology，2017，11(01):38－47.

［9］YANG X S.Nature－Inspired Metaheuristic Algorithms:Second Edition［M］.Beckington:Luniver Press，2010.