基于遺傳算法和二進(jìn)制蟻群算法的DV-Hop定位算法的優(yōu)化

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

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

0 引言

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

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

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

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

1.1 DV-Hop定位算法

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

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

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

1.1.2 估計(jì)節(jié)點(diǎn)間距離

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

(1)

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

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

di=HopSizei×Hij

(2)

1.1.3 確定的位置

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

(3)

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

(4)

(5)

(6)

可以得出：

X=(ATA)-1ATb

(7)

1.2 遺傳算法

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

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

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

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

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

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

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

(8)

因?yàn)榫嚯xdi是一個(gè)估計(jì)值，那么必定存在誤差。為此，改進(jìn)算法是將WSN定位問(wèn)題的誤差降到最小，定位問(wèn)題可以歸結(jié)為

(9)

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

(10)

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

2.2 算法的步驟

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

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

(11)

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

圖1 初始種群區(qū)

(12)

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

(13)

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

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

(14)

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

(15)

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

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

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

(16)

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

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

(17)

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

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

3 仿真與實(shí)驗(yàn)結(jié)果

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

(18)

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

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

(19)

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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