林鳳德，陳佳品，丁 凱，李振波

(1.上海交通大學(xué)電子信息與電氣工程學(xué)院，薄膜與微細(xì)技術(shù)教育部重點實驗室，上海 200240；2.無錫近地面探測技術(shù)重點實驗室，江蘇無錫 214035)

0 引言

近年來，隨著微機電系統(tǒng)(MEMS)、集成電路系統(tǒng)技術(shù)、通信技術(shù)以及計算機軟件的巨大進(jìn)步，帶動了大規(guī)模分布式無線傳感器網(wǎng)絡(luò)的快速發(fā)展。無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是由部署在檢測區(qū)域內(nèi)的大量低成本傳感器節(jié)點通過無線通信方式形成的一種多跳自組織的網(wǎng)絡(luò)系統(tǒng)。其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知的對象信息，并發(fā)送給觀察者。WSN 提供了一種新穎的信息獲取和處理方法，在醫(yī)療衛(wèi)生、環(huán)境監(jiān)測、軍事作戰(zhàn)等方面具有廣泛的應(yīng)用，所以，WSN已經(jīng)成為21世紀(jì)最受矚目的科技之一[1-2]。

在WSN中，將現(xiàn)有定位算法分為基于測量距離的定位算法和基于非測距定位算法方法2類。基于測量距離的定位算法定位精度較高，需要測距硬件，功耗、成本也相對較大，不適合應(yīng)用到大規(guī)模的網(wǎng)絡(luò)環(huán)境中。常用的測距方法有TOA、TDOA、AOA和RSSI等[2-4]。而非測距定位算法利用連通情況來估測未知節(jié)點的位置,常見的非測距算法如質(zhì)心、DV-Hop、APIT以及MDS-MAP等。由于非測距定位算法直接使用連通信息，硬件要求更低，在功耗和成本上具備更大優(yōu)勢，并且定位精度可以滿足多數(shù)傳感網(wǎng)絡(luò)的應(yīng)用要求，更適合應(yīng)用于低成本、低功耗的無線傳感網(wǎng)絡(luò)。其中DV-Hop定位算法[5-6]技術(shù)以其方便性、可操作性等優(yōu)點得到了廣泛的應(yīng)用，而傳統(tǒng)的DV-Hop定位算法在由已知節(jié)點得到未知節(jié)點的位置時存在很大的誤差，并且算法的收斂性性能也較差，導(dǎo)致傳統(tǒng)的DV-Hop算法精度不夠、計算時間較長，無法達(dá)到一些工程要求。針對以上問題，本文提出了一種基于遺傳算法和二進(jìn)制蟻群算法改進(jìn)的DV-Hop定位算法，其中遺傳算法采用復(fù)制-交叉-變異算子的方式進(jìn)行循環(huán)搜索，在產(chǎn)生新個體的基礎(chǔ)上，利用改進(jìn)的蟻群算法進(jìn)行進(jìn)一步搜索，蟻群算法采用二進(jìn)制編碼的方式遍歷搜索能力更強，并且提高了收斂的速度，從而提高了節(jié)點定位精度和縮短了節(jié)點定位所消耗的時間。

實驗結(jié)果顯示，本文提出新的算法比傳統(tǒng)的DV-Hop算法和基于遺傳算法的DV-Hop算法有更好的收斂性，而且通過改變未知節(jié)點個數(shù)、錨節(jié)點密度、通信距離R等條件，本文提出的算法比傳統(tǒng)的DV-Hop算法、基于遺傳算法的DV-Hop算法有更好的定位精度。

1 定位模型設(shè)計理論

1.1 DV-Hop定位算法

DV-Hop[5-6]是一種利用距離矢量路由和GPS定位思想提出的定位算法，這個算法由3個階段組成[5-6]。第一個階段：網(wǎng)絡(luò)中的每個未知節(jié)點計算到每個錨節(jié)點的最小跳數(shù)值；第二階段：通過一個簡單的公式估計每跳的平均距離，然后廣播到全局網(wǎng)絡(luò)讓所有的節(jié)點都得到每跳的平均距離，這樣未知節(jié)點將估計到錨節(jié)點的距離。第三階段：利用三邊測量法或極大似然估計法計算出未知節(jié)點的位置。

1.1.1 計算最小跳數(shù)值

每個錨節(jié)點向其鄰居節(jié)點廣播信標(biāo)數(shù)據(jù)包，數(shù)據(jù)包的格式是{id，xi,yi,Hi},其中標(biāo)識符id每個節(jié)點的唯一標(biāo)識，錨節(jié)點i的坐標(biāo)為(xi,yi)，到錨節(jié)點最小跳數(shù)的值為Hi，其中Hi初始值為0。在鄰居節(jié)點接收到具有較小跳數(shù)值的特定錨節(jié)點的信標(biāo)包之后，它們保存錨節(jié)點的位置，并在將其發(fā)送到其他相鄰節(jié)點之前將其計數(shù)值增加1。具有到特定的錨節(jié)點有較高跳數(shù)值的信標(biāo)包，將被定義為過時的信息，并且被忽略。通過這種機制，網(wǎng)絡(luò)中的每個節(jié)點都會得到每個錨節(jié)點的最小跳數(shù)值。

1.1.2 估計節(jié)點間距離

首先，利用式(1)計算每個錨節(jié)點之間的一跳的平均距離為HopSizei：

(1)

式中：(xi,yi)和(xj,yj)為錨節(jié)點i和j的坐標(biāo)；Hij為錨節(jié)點i和j之間的最小跳數(shù)；m為錨節(jié)點的個數(shù)。

計算完HopSizei后，每個錨節(jié)點在整個網(wǎng)絡(luò)中廣播HopSizei，當(dāng)未知節(jié)點從錨節(jié)點得到HopSizei后；應(yīng)用式(2)，計算他們之間的距離：

di=HopSizei×Hij

(2)

1.1.3 確定的位置

根據(jù)每個錨節(jié)點的坐標(biāo)以及在第二階段中未知節(jié)點到錨節(jié)點之間的距離，通過多點定位的方式來計算未知節(jié)點的坐標(biāo)。設(shè)未知節(jié)P點的坐標(biāo)為(x,y)，錨節(jié)點i的坐標(biāo)為(xi,yi)。因此，未知節(jié)點P和m個錨節(jié)點之間的距離關(guān)系如式(3)所示：

(3)

展開后可以被寫成矩陣Ax=b

(4)

(5)

(6)

可以得出：

X=(ATA)-1ATb

(7)

1.2 遺傳算法

遺傳算法[7]是模仿自然生物進(jìn)化思想而衍生出來的一種自適應(yīng)啟發(fā)式全局搜索算法[8]。在本質(zhì)上，它是一個由選擇、交叉、變異算子構(gòu)成的循環(huán)過程[7-9]。在這個過程中尋找全局最優(yōu)解，算法不需要梯度信息和微積分計算，它可以只通過操作選擇、交叉、變異算子的操作，以很高的概率找到全局最優(yōu)解或接近最優(yōu)解的解空間。因此，它可以減少陷入局部的解空間。

1.3 二進(jìn)制蟻群算法

蟻群算法[10]是一種新的模擬進(jìn)化算法。螞蟻在尋找食物時會釋放出一種特殊的信息素，使其他螞蟻感受到這種特殊性，并趨向于高密度的方向。蟻群算法通過信息素的積累和更新收斂最優(yōu)路徑，并通過適當(dāng)?shù)牡螖?shù)實現(xiàn)優(yōu)化。二進(jìn)制蟻群算法[10-11]直接用二進(jìn)制編碼來表示參數(shù)，與十進(jìn)制編碼相比，該算法占用的存儲空間小，算法復(fù)雜度低。此外，二進(jìn)制編碼的遍歷搜索能力優(yōu)于十進(jìn)制編碼。

2 基于遺傳-二進(jìn)制蟻群算法的DV-Hop算法的定位

2.1 WSN定位算法數(shù)學(xué)模型

在DV-Hop算法[5-6]中，距離是一個估計值，所以必然有誤差。WSN定位問題的主要目標(biāo)是最小化誤差。在本文中，我們提出了一種基于遺傳-二進(jìn)制蟻群算法的DV-Hop算法[11-12]。

假設(shè)在傳感器網(wǎng)絡(luò)中有M+N個傳感器節(jié)點，包括M個錨節(jié)點(坐標(biāo)已知)和N個待測節(jié)點(未知節(jié)點)。已知錨節(jié)點的坐標(biāo)為(xi,yi),(i=1,2,…,m)和未知節(jié)點的坐標(biāo)為(x,y),(i=1,2,…,n)。根據(jù)DV-Hop算法的第二個階段?？梢垣@得未知節(jié)點和錨節(jié)點i,(i=1,2,…,m)之間的距離di,所以可以得到以下的公式：

(8)

因為距離di是一個估計值，那么必定存在誤差。為此，改進(jìn)算法是將WSN定位問題的誤差降到最小，定位問題可以歸結(jié)為

(9)

根據(jù)式(9)所示的目標(biāo)函數(shù)，設(shè)置適應(yīng)度函數(shù)如下：

(10)

式中α為正實系數(shù)。

2.2 算法的步驟

步驟1：計算每個節(jié)點到每個錨節(jié)點的最小跳數(shù)值，根據(jù)式(1)估計每個錨節(jié)點的一跳的平均大小，通過使用最小跳計數(shù)值和一跳的平均大小，每個未知節(jié)點根據(jù)式(2)估計到錨節(jié)點的距離；

步驟2：確定每個未知節(jié)點的種群可行域，并在可行域內(nèi)生成初始種群；為了提高定位精度或收斂速度，我們限制了一個樣本種群的可行區(qū)域，如圖1所示：假設(shè)未知節(jié)點N有3個最近的錨節(jié)點K1,K2,K3；他們的坐標(biāo)是(x1，y1),(x2,y2)和(x3,y3)，并且錨節(jié)點K1,K2,K3與未知節(jié)點N之間的最小跳數(shù)值分別為(H1,H2,H3)。所有傳感器節(jié)點的通信半徑為R。我們構(gòu)建了用3個錨節(jié)點為中心的3個正方形，分別以2RH1、2RH2、2RH3為3個正方形邊長。如圖1所示，初始種群是在可行域中隨機生成的，未知節(jié)點N的坐標(biāo)上界和下界可以定義如式(11)所示。

(11)

式中(xN,yN)為未知節(jié)點N的坐標(biāo)。

圖1 初始種群區(qū)

(12)

而后根據(jù)適應(yīng)性函數(shù)進(jìn)行逆轉(zhuǎn)變異，設(shè)交叉搜索產(chǎn)生的種群中個體為Bn，其中Bn∈(Cn,Dn)。按式(13)進(jìn)行變異產(chǎn)生下一代：

(13)

式中random(0，1)表示隨機取0或者1。

Δ(t,α)=α[1-r(1-h/L)b]

(14)

式中：r為[0,1]范圍內(nèi)符合均勻概率分布的一個隨機數(shù)；h為當(dāng)下進(jìn)化代數(shù)；L為最大進(jìn)化代數(shù)；b為一個系統(tǒng)參數(shù)。

(15)

式中：α(α≥0)為一個移動路徑的參數(shù)，取α=1；β(β≥0)為每只螞蟻可見性的參數(shù)，取β=2;τij為在節(jié)點i,j連接t時刻殘留的信息量；ηi,j為在i,j連接的可見性；allowedk={0,1}為下一個選擇的狀態(tài)。

M只螞蟻開始遍歷N個節(jié)點，在遍歷的過程中按照式(15)更新所有路徑的信息素τi,j。隨著時間的流逝，留下的信息逐漸消失。N分鐘后，螞蟻完成一個循環(huán)，則：

τi,j(t+1)=ρ·τi,j(t)+Δτi,j

(16)

式中ρ(0≤ρ≤1)為一個移動路徑的持久性，1-ρ表示的是信息損失程度。

Δτi,j=1/fbest(x,y)

(17)

式中fbest(x,y)為迭代最優(yōu)解或者全部的最優(yōu)解。

步驟5：按照如上從步驟3到步驟5迭代次數(shù)為300次時候則終止，則得到最優(yōu)解此時F(x,y)最小。

3 仿真與實驗結(jié)果

為了評估該算法的定位性能，實驗仿真是在window10環(huán)境下，用MATLAB 9.1.0來實現(xiàn)。然后分析了它的性能，并與傳統(tǒng)的DV-Hop算法、基于遺傳算法的DV-Hop算法進(jìn)行了比較。我們使用的每個未知節(jié)點的定位誤差，是由式(18)來定義誤差：

(18)

式中：(xest,yest)為未知節(jié)點的估算坐標(biāo)；(xi,yi)為未知節(jié)點的確切坐標(biāo)。

定義了平均定位誤差如式(19)所示：

(19)

實驗中仿真的參數(shù)如表1所示:

在進(jìn)行實驗的時候，固定區(qū)域為200 m×200 m的正方形區(qū)域，在這個區(qū)域內(nèi)隨機部署300個傳感器節(jié)點，其中有240個未知節(jié)點、60個錨節(jié)點，通信距離R

表1 仿真參數(shù)列表

為30 m，每個節(jié)點的通信半徑是相等的。圖2(a)是傳統(tǒng)的DV-Hop算法的誤差圖，圖中星號代表錨節(jié)點，實點代表未知節(jié)點的真實位置，圓圈代表未知節(jié)點的估計位置，線段代表未知節(jié)點估計位置和真實位置之間的誤差。從圖中可以看出傳統(tǒng)的DV-Hop算法的定位誤差總體來說比較大，還有一些點的定位與真實值之間的存在著很大的差距，圖2(b)是利用本文提出的GABAC-DV-Hop算法定位，仿真結(jié)果的定位誤差比圖2(a)的定位誤差總體上小了很多，而且不存在誤差較大的點，因此可以看出本文提出的算法的定位比傳統(tǒng)的DV-Hop算法的誤差有很大的提高。

(a)傳統(tǒng)的DV-Hop定位算法的誤差

(b)GABAC-DV-Hop定位算法的誤差圖2 DV-HOP算法與GABAC-DV-Hop算法誤差對比

圖3是在200 m×200 m區(qū)域內(nèi)隨機部署節(jié)點，其中錨節(jié)點數(shù)為60個，每個節(jié)點的通信距離R為30 m，改變未知節(jié)點個數(shù)測定各算法平均定位誤差。從圖3可以得出GABAC-DV-Hop算法和GADV-Hop算法比傳統(tǒng)的DV-Hop算法的精度高很多，平均誤差大概是傳統(tǒng)的DV-Hop算法的1/3～1/2，當(dāng)未知節(jié)點較少的時候，GABAC-DV-Hop定位算法的準(zhǔn)確性比GADV-Hop定位算法低，當(dāng)未知節(jié)點較多的時候，GABAC-DV-Hop算法的精確度較好。可能的原因是當(dāng)未知節(jié)點較少的時候，GABAC-DV-Hop定位算法中的二進(jìn)制蟻群算法搜索對于結(jié)果有一定的干擾，所以其定位的精確度比GADV-Hop的精確度低。

圖3 不同未知節(jié)點個數(shù)的各算法平均定位誤差圖

圖4是在200 m×200 m區(qū)域內(nèi)隨機部署300個節(jié)點，每個節(jié)點的通信距離R為30 m，改變錨節(jié)點密度(即錨節(jié)點與節(jié)點總數(shù)的比例)測定各算法平均定位誤差，從圖4可以得出總體上GABAC-DV-Hop定位算法和GADV-Hop定位算法的精確度比傳統(tǒng)的DV-Hop定位算法的精確度要高很多。但是隨著錨節(jié)點的密度增加，GABAC-DV-Hop定位算法和GADV-Hop定位算法的平均誤差先減小，而后增大，說明不是錨節(jié)點的密度越高，定位精確度就越高。對于GABAC-DV-Hop定位算法錨節(jié)點密度在0.2～0.5都是比較適合的，而從成本上看，錨節(jié)點個數(shù)一般要少，所以一般錨節(jié)點比例取25%。

圖4 不同錨節(jié)點密度的各算法平均定位誤差圖

圖5是在200 m×200 m區(qū)域內(nèi)隨機部署300個節(jié)點，其中錨節(jié)點個數(shù)為60，未知節(jié)點的個數(shù)為240，改變各個節(jié)點通信距離R，測定各算法平均定位誤差。從圖5可以得到，總體上來看GABAC-DV-Hop定位算法和GADV-Hop定位算法比傳統(tǒng)的DV-Hop定位算法的平均定位誤差小，隨著通信距離R的增加，3種定位算法的平均定位誤差都變大。并且GABAC-DV-Hop定位算法比GADV-Hop定位算法的平均定位誤差更小，精確度更大。而從圖5可知在通訊距離為30～40 m之間平均定位誤差對于GABACDV-Hop定位算法影響不大，而一般考慮功率的因素，所以一般通訊距離取30 m。

圖5 不同通信距離R的各算法平均定位誤差圖

從圖2～圖5中可以得到GABAC-DV-Hop定位算法比GADV-Hop定位算法和傳統(tǒng)的DV-Hop定位算法有更好的定位精度，并且考慮算法精度和系統(tǒng)的功率來看，對于GABAC-DV-Hop定位算法一般取錨節(jié)點密度為25%，通信距離為30 m作為實際應(yīng)用中的參數(shù)。

4 結(jié)論

無線傳感器網(wǎng)絡(luò)中的定位問題實際上是一個優(yōu)化問題，其目標(biāo)是最小化WSN定位問題的總估計誤差。本文提出的GABACDV-Hop定位算法結(jié)合了遺傳算法和二進(jìn)制蟻群算法優(yōu)勢，不僅能夠提高初始種群的質(zhì)量，在迭代過程中后代的種群質(zhì)量也能夠相應(yīng)提高，從而提高了算法的定位精度，而且應(yīng)用二進(jìn)制蟻群算法能更快地提高收斂性。仿真結(jié)果表明，GABAC-DV-Hop定位算法的定位效果優(yōu)于GADV-Hop定位算法和傳統(tǒng)的DV-Hop算法的定位效果，并且收斂速度也較快，是一種有較大應(yīng)用價值的定位方法。