一種基于優(yōu)化算法的無(wú)線傳感器網(wǎng)絡(luò)定位算法

摘要：該文提出一種基于遺傳模擬退火算法的定位算法。在現(xiàn)有的定位算法中，DV-Hop算法的硬件開(kāi)銷(xiāo)小，但定位精度不高，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的跳數(shù)大于或等于2時(shí)，未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的估計(jì)距離會(huì)產(chǎn)生較大的誤差，為此本文將遺傳模擬退火算法用于DV-Hop算法中，以提高節(jié)點(diǎn)間的平均每跳通信距離估計(jì)精度，進(jìn)一步提高定位精度。仿真結(jié)果與分析表明，新算法的定位精度有一定的提高。

關(guān)鍵詞：定位算法；遺傳算法；模擬退火；DV-Hop

中圖分類(lèi)號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2011)04-0775-02

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是由大量的廉價(jià)微型傳感器節(jié)點(diǎn)通過(guò)無(wú)線通信方式形成的一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng)，而定位是WSN的一個(gè)關(guān)鍵問(wèn)題。節(jié)點(diǎn)準(zhǔn)確地進(jìn)行自身定位在無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用中非常重要。首先，傳感器節(jié)點(diǎn)采集到的數(shù)據(jù)必須結(jié)合其位置信息才有意義，否則，如果不知道數(shù)據(jù)所對(duì)應(yīng)的地理位置，數(shù)據(jù)就失去意義。其次，無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自身定位還可以在外部目標(biāo)的定位和追蹤以及提高路由效率等方面發(fā)揮作用。因此，實(shí)現(xiàn)節(jié)點(diǎn)的自身定位對(duì)無(wú)線傳感器網(wǎng)絡(luò)有著重要的意義。

現(xiàn)有的WSN定位算法是根據(jù)少量的位置已知的節(jié)點(diǎn)（錨節(jié)點(diǎn)）以及它們與其他節(jié)點(diǎn)的通信信息來(lái)估算整個(gè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的位置。WSN定位算法可分為基于距離信息（Range-Based）和不基于距離信息（Range-Free）兩類(lèi)，前者是根據(jù)節(jié)點(diǎn)間的距離或角度等信息定位，后者僅僅根據(jù)節(jié)點(diǎn)間的連通信息實(shí)現(xiàn)節(jié)點(diǎn)定位。本文主要是對(duì)不基于距離信息的定位算法DV-Hop進(jìn)行研究并改進(jìn)。

1 DV-Hop算法

1.1 DV-Hop算法

DV-Hop算法由三個(gè)階段組成。

第一階段，使用典型的距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有未知節(jié)點(diǎn)獲得距初始錨節(jié)點(diǎn)的跳數(shù)；

第二階段，在獲得其他錨節(jié)點(diǎn)位置（xj，yj）和相隔跳數(shù)后，各錨節(jié)點(diǎn)（xi，yi）利用所收集的信息按式（1）計(jì)算平均跳距：

（1）

式中si是錨節(jié)點(diǎn)i的平均每跳距離，hij為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的跳數(shù)；然后將平均每跳距離作為一個(gè)校正值廣播至網(wǎng)絡(luò)中。校正值采用可控洪泛法在網(wǎng)絡(luò)中傳播，這意味著一個(gè)節(jié)點(diǎn)僅接收獲得的第一個(gè)校正值，而丟棄所有后來(lái)者，這個(gè)策略確保了絕大多數(shù)節(jié)點(diǎn)可以從最近的錨節(jié)點(diǎn)接收校正值。在大型網(wǎng)絡(luò)中，可通過(guò)為數(shù)據(jù)包設(shè)置一個(gè)TTL域來(lái)減少通信量。當(dāng)接收到校正值之后，節(jié)點(diǎn)根據(jù)跳數(shù)計(jì)算與錨節(jié)點(diǎn)之間的距離。

第三階段，在二維空間中，一旦一個(gè)未知節(jié)點(diǎn)獲得與3個(gè)或更多錨節(jié)點(diǎn)的距離后，執(zhí)行三邊測(cè)量法或最大似然估計(jì)法計(jì)算自身的位置。

如圖1所示，已知信標(biāo)節(jié)點(diǎn)L1與L2，L3之間的距離和跳數(shù)。L2計(jì)算得到校正值（即平均每跳距離）（40+75）/（2+5）=16.42。假設(shè)A從L2獲得校正值，則它與3個(gè)信標(biāo)節(jié)點(diǎn)之間d1=3×16.42，d2=2×16.42，d3=3×16.42，然后使用三邊測(cè)量法確定節(jié)點(diǎn)A的位置。

1.2 DV-Hop算法中錨節(jié)點(diǎn)平均每跳距離現(xiàn)有的改進(jìn)方法

原DV-Hop算法的主要誤差在于計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的估計(jì)距離時(shí)，是用跳數(shù)乘以平均每跳距離來(lái)表示，而當(dāng)網(wǎng)絡(luò)中的跳數(shù)大于或等于2跳時(shí)，未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的實(shí)際距離與跳數(shù)乘以平均每跳距離所得的值，存在較大的誤差，因此如何提高錨節(jié)點(diǎn)的平均每跳距離的估計(jì)精度是本文改進(jìn)的出發(fā)點(diǎn)。

文獻(xiàn)[2]中對(duì)算法改進(jìn)的思想為：

當(dāng)所有的節(jié)點(diǎn)獲得每跳距離后，使用公式（其中Hopsizei為單個(gè)節(jié)點(diǎn)的每跳距離，n為錨節(jié)點(diǎn)個(gè)數(shù)）計(jì)算全網(wǎng)平均每跳距離，并將該值用于di=hops*Hopsizeave中，計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離。

文獻(xiàn)[3]中對(duì)算法改進(jìn)的思想為：

未知節(jié)點(diǎn)在接收多個(gè)錨節(jié)點(diǎn)的平均每跳距離后，對(duì)各錨節(jié)點(diǎn)估計(jì)的平均每跳距離作歸一化加權(quán)處理，離未知節(jié)點(diǎn)越近的錨節(jié)點(diǎn)的權(quán)值越大。

記錨節(jié)點(diǎn)i估計(jì)的平均每跳距離為si、未知節(jié)點(diǎn)距錨節(jié)點(diǎn)i的跳數(shù)為Ni，其中i=1，2…。設(shè)未知節(jié)點(diǎn)共收到k個(gè)錨節(jié)點(diǎn)的信息，每個(gè)錨節(jié)點(diǎn)的平均每跳距離的加權(quán)值為Wi，則取，即錨節(jié)點(diǎn)i的權(quán)值等于未知節(jié)點(diǎn)到錨節(jié)點(diǎn)j的跳數(shù)的倒數(shù)除以該未知節(jié)點(diǎn)到各錨節(jié)點(diǎn)的跳數(shù)的倒數(shù)和。由各錨節(jié)點(diǎn)估計(jì)的平均每跳距離，可得未知節(jié)點(diǎn)的平均跳距為，即未知節(jié)點(diǎn)的平均每跳估計(jì)等于各錨節(jié)點(diǎn)估計(jì)的平均每跳距離的加權(quán)和。

文獻(xiàn)[6]中對(duì)算法的改進(jìn)思想為：

為了充分利用各錨節(jié)點(diǎn)的信息，未知節(jié)點(diǎn)不僅僅記錄接受到的第一個(gè)平均每跳距離，而是記錄所有錨節(jié)點(diǎn)的平均每跳距離，然后進(jìn)行加權(quán)平均。考慮到各錨節(jié)點(diǎn)距離未知節(jié)點(diǎn)的遠(yuǎn)近不同，對(duì)不同錨節(jié)點(diǎn)的平均每跳距離賦予不同的權(quán)值，權(quán)值取決于未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的跳數(shù)值，按跳數(shù)值大小的反序分配。舉例說(shuō)明，未知節(jié)點(diǎn)A收到L1，L2，L3的平均每跳距離分別為D1，D2，D3。A到L1，L2，L3的跳數(shù)分別為1，2，3。則A分配給D1，D2，D3的權(quán)值分別為3，2，1，用公式為（D1*3+D2*2+D1*1）/（1+2+3）進(jìn)行加權(quán)平均。

2 基于遺傳模擬退火算法的定位算法

遺傳算法（GA）和模擬退火算法（SA）是使用較為廣泛的優(yōu)化算法。遺傳算法是一種全局高效的搜索算法，它是通過(guò)模擬自然界的生物進(jìn)化機(jī)制而發(fā)展起來(lái)的隨機(jī)優(yōu)化方法。它能在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自適應(yīng)地控制搜索過(guò)程以求得最優(yōu)解，但它卻容易陷入局部最小解。相反，模擬退火算法如果初始溫度較高，降溫速率較低，可以克服局部最小解。因此本文提出遺傳模擬退火算法將全局搜索的GA和局部搜索的SA相結(jié)合，以得到性能更好的算法。

遺傳模擬退火算法混合策略是一個(gè)兩層并行搜索結(jié)構(gòu)。內(nèi)部層次上，混合算法在各溫度下串行的依次進(jìn)行遺傳算法和模擬退火算法搜索，是一種兩層串行結(jié)構(gòu)。其中，模擬退火算法的初始解來(lái)自遺傳算法的進(jìn)化結(jié)果，模擬退火算法經(jīng)Metropolis抽樣過(guò)程得到的解又成為遺傳算法進(jìn)一步進(jìn)化的父代種群。外部層次上，遺傳算法提供了并行搜索結(jié)構(gòu)，使模擬退火算法轉(zhuǎn)化成為并行模擬退火算法，因此混合算法始終進(jìn)行種群并行優(yōu)化。

改進(jìn)的GASA算法中根據(jù)交叉和變異概率，對(duì)初始種群進(jìn)行交叉、變異操作，進(jìn)而對(duì)得到的新種群利用模擬退火算法中的Metropolis準(zhǔn)則決定它們是否進(jìn)入下一代種群，然后把這個(gè)種群又作為父代種群繼續(xù)下一代的遺傳操作，整個(gè)過(guò)程反復(fù)、迭代，直到達(dá)到終止條件。

GASA的個(gè)體編碼

針對(duì)WSN節(jié)點(diǎn)數(shù)目較多，計(jì)算量大，且二進(jìn)制編碼不能直接反映所求問(wèn)題的結(jié)構(gòu)特征，本文的定位算法采用實(shí)數(shù)編碼，這便于與模擬退火算法的結(jié)合，并且可以改善算法的計(jì)算復(fù)雜度，提高運(yùn)算效率。

GASA的適應(yīng)度函數(shù)

本文中，遺傳模擬退火算法的適應(yīng)度函數(shù)定義如下：

其中，Hopsizeave是錨節(jié)點(diǎn)的平均每跳距離，nij是錨節(jié)點(diǎn)i與錨節(jié)點(diǎn)j之間的跳數(shù)，(xi，yi)是錨節(jié)點(diǎn) 的坐標(biāo)位置，(xj，yj)是錨節(jié)點(diǎn)j的坐標(biāo)位置。

GASA的算子設(shè)計(jì)

選擇算子采用SA的Metropolis接受準(zhǔn)則；交叉算子采用算術(shù)交叉算子；變異算子采用保優(yōu)，均勻變異。

GASA的終止條件

當(dāng)?shù)螖?shù)達(dá)到預(yù)定次數(shù)或者群體的成熟度滿足一定條件時(shí)，停止迭代。

本文中擬采用GASA算法來(lái)求錨節(jié)點(diǎn)平均每跳距離的最優(yōu)解，以使DV-Hop算法的定位精度有所提高。

3 結(jié)束語(yǔ)

節(jié)點(diǎn)定位是無(wú)線傳感器網(wǎng)絡(luò)的一項(xiàng)關(guān)鍵技術(shù)，無(wú)需測(cè)距定位算法將是定位算法的主流。本文對(duì)無(wú)需測(cè)距的定位算法DV-Hop進(jìn)行分析，針對(duì)它在平均每跳距離可能產(chǎn)生的誤差，提出了一種改進(jìn)的方案，以提高節(jié)點(diǎn)定位精度。

參考文獻(xiàn)：

[1] 郭永紅，萬(wàn)江文，于寧，等.基于跳數(shù)的無(wú)線傳感器網(wǎng)絡(luò)定位求精算法[J].計(jì)算機(jī)工程，2009(3).

[2] CHEN HONG-YANG，SEZAKI K，DENG PING，et al.An improvement DV-HOP algorithm for wireless sensor networks[Z].

[3] 劉鋒，張翰，楊驥.一種基于加權(quán)處理的無(wú)線傳感器網(wǎng)絡(luò)平均跳距離估計(jì)算法[J].電子與信息學(xué)報(bào)，2008，35(5):1221-1224.

[4] 張佳，吳延海，石峰，等.基于DV-HOP的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)應(yīng)用，2010，30(2)

[5] 唐鷺，洪月華，伍華健.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位綜合算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46(4).

[6] 劉明，包亞萍，劉漢義.無(wú)線傳感器網(wǎng)絡(luò)中一種改進(jìn)的DV-Hop算法[J].微計(jì)算機(jī)信息，2009.