劉彥隆，呂顯朋，王相國

（太原理工大學(xué)信息工程學(xué)院，山西太原 030024）

0 引言

無線傳感器網(wǎng)絡(luò)（WSNs）在環(huán)境監(jiān)測、軍事國防、搶險救災(zāi)等很多的領(lǐng)域中具有廣闊的應(yīng)用前景，而網(wǎng)絡(luò)的節(jié)點定位或者是監(jiān)測目標(biāo)定位是WSNs應(yīng)用的支撐，節(jié)點定位又是外部目標(biāo)定位的基礎(chǔ)［1］，所以，節(jié)點定位就顯得異常重要。節(jié)點定位分為基于距離和基于估計距離的定位，后者受復(fù)雜環(huán)境對信號傳輸影響低，并且硬件成本較少，能耗小，非常適合 WSNs的應(yīng)用［2］。

Dragos Niculescu利用GPS和距離矢量路由思想提出的DV—Hop算法就是基于估計距離的定位［3］。DV—Hop沒有直接測量距離，是利用交換距離矢量信息和網(wǎng)絡(luò)連通度，將距離巧妙轉(zhuǎn)換成估計的距離，所以，DV—Hop不需要高裝備的測距單元，尤其在各項同性網(wǎng)絡(luò)里性能良好［2］。

本文針對DV—Hop第三階段利用最小二乘法處理非線性約束問題時精確度較差的問題，提出了基于遺傳算法（GA）單純形法的混合GA，經(jīng)過實驗仿真，混合算法具有良好的性能，是一種適合WSNs的可行算法。

1 相關(guān)理論

DV—Hop定位算法的第三階段［4］:將第一，二階段計算出的未知節(jié)點o（x，y）到信標(biāo)節(jié)點A1（x1，y1），A2（x2，y2），…，An（xn，yn）跳段的距離d1，d2，…，dn，利用極大似然估計的方法計算（x，y）;由兩點間的距離公式，可得

對式（1）化簡整理可得線性方程AX=b，其中

利用最小二乘法

其中，dn存在于b的各個元素中，使得用（ATA）-1ATb求出的坐標(biāo)受制于dn的精度，因此，用最小二乘法求解雖然簡便，卻極大地降低了解的準(zhǔn)確度，因此，可以將問題的求解轉(zhuǎn)化為約束優(yōu)化的問題［6］。

假設(shè)信標(biāo)節(jié)點A1，A2…，An到o的真實距離為r1，r2，…，rn;ε1，ε2，…，εn為傳感器的測距誤差范圍。式（1）可化為

則問題可化為求解

因此，把DV—Hop第三階段轉(zhuǎn)化為求解約束性優(yōu)化問題，f（x，y）的求解即為非線性優(yōu)化問題，眾多學(xué)者提出了用人工蜂群［7］（收斂速度快）、約束粒子群［6］（收斂速度快）、GA［8，9］（解決全局的優(yōu)化問題）、模擬退火算法［10，11］（有效地避免尋得局部最優(yōu)解）、差分進(jìn)化的算法［12］（算法復(fù)雜度低）等求解優(yōu)化問題。

本文提出的用GA+單純形法的混合遺傳性算法優(yōu)化DV—Hop算法，不僅保留了GA的優(yōu)勢，單純形法和最優(yōu)個體保優(yōu)的原則也避免了GA的弊端，得到了更加精確地定位。

2 混合GA求解約束問題

2.1 算法的原理

優(yōu)勝劣汰與適者生存的生物進(jìn)化規(guī)律存在于各階系統(tǒng)中，進(jìn)化過程就是具有較好健壯性自適應(yīng)的過程，受生物進(jìn)化的啟發(fā)，Holland J提出了GA，它非常適合組合和優(yōu)化問題中全局最優(yōu)解的求解［13］，能大概率地獲得最優(yōu)解，而且在數(shù)學(xué)上較容易實現(xiàn)［14］。

GA的基本程序:算法不斷迭代和更新假設(shè)的群體，并且在每次迭代中，用適應(yīng)度函數(shù)計算評價所有個體，以概率的方法選擇適應(yīng)度較高的個體通過選擇、交叉和變異等遺傳算子產(chǎn)生新群體［14］。

但是GA存在運算時間長、局部搜索能力差等固有的缺陷［14］，因此，本文對GA采用了最優(yōu)個體保優(yōu)的原則的改進(jìn)，改善運算時間長的弊端;并且采用了在局部搜索能力領(lǐng)域具有較強先驗性的單純形算法與GA結(jié)合的混合GA。

單純形法通過相應(yīng)的一系列轉(zhuǎn)換，把各種非標(biāo)準(zhǔn)形式的問題變化成標(biāo)準(zhǔn)形式，從而求解;因此，它對含有很多個約束條件的非標(biāo)準(zhǔn)形式的線性問題的求解非常有效。

2.2 求解約束問題

用GA+單純形法的混合GA求解f（x，y），設(shè)計其適應(yīng)度函數(shù)，要使代價函數(shù)f（x，y）最小，采用最大系數(shù)法，即

式中Cmax為最大系數(shù)。

3 一種基于GA+單純形法的DV—Hop定位算法改進(jìn)

假設(shè)有N個節(jié)點存在于一個WSNs中，其中包含M個信標(biāo)節(jié)點，利用M個信標(biāo)節(jié)點去定位N-M個未知節(jié)點，隨著定位的進(jìn)行，未知節(jié)點轉(zhuǎn)換為已知坐標(biāo)的新的信標(biāo)節(jié)點協(xié)助定位，但只有這M個信標(biāo)節(jié)點的位置信息是沒有誤差的精確值，信標(biāo)節(jié)點與未知節(jié)點，未知節(jié)點與未知節(jié)點之間允許有一定的測距誤差，兩節(jié)點之間的距離不能超過WSNs測距的半徑;并假設(shè)WSNs中不存在孤立點，孤立點問題屬于WSNs布局問題［6］，本文不討論。

綜上，算法基本流程為:

1）計信標(biāo)節(jié)點個數(shù)t（初始時t=M），在Mx（初始時Mx=N-M）個未知節(jié)點里，找出鄰居信標(biāo)節(jié)點最多的未知節(jié)點Nx開始以下步驟。

2）隨機的產(chǎn)生群體規(guī)模為n的初始群體。

3）將適應(yīng)度函數(shù)F（x，y）=f'（x，y）+p（x，y）進(jìn)行指數(shù)定標(biāo)，則新的適應(yīng)度函數(shù)為fitness=ekF（x，y）;利用適應(yīng)度函數(shù)，計算群體中所有個體的適應(yīng)度。

4）最優(yōu)個體的保優(yōu)原則，把所有個體按適應(yīng)度高低排列，適應(yīng)度最高的5個個體跳到第6步，剩下的n-5個個體組成群體p繼續(xù)執(zhí)行第5步。

5）GA的操作，產(chǎn)生新的一代Ps:

a.選擇（復(fù)制）:本文采用輪盤賭的方法;

b.交叉（重組）:本文采用二點交叉的方法;

c.突變:選擇一個或多個基因位，按變異概率pm做相應(yīng)的變動;

d.更新:p←ps。

6）第4步最優(yōu)的5個個體與第5步遺傳操作后的個體數(shù)為n-5的群體ps組成新群體。

7）單純形法，在生成的新群體里以一定的概率選擇個體進(jìn)行單純形法，計算后的新個體代替原個體。

8）若群體的性能已經(jīng)滿足性能要求，或達(dá)到了迭代次數(shù)（本文選用后者），執(zhí)行第9步;否則，跳到第3步。

9）由上可得Nx的位置坐標(biāo)，把Nx看做信標(biāo)節(jié)點，t←t+1;t＜N時，跳到第1步，t=N時，WSNs中所有未知節(jié)點都被定位，算法結(jié)束。

算法第3步，將適應(yīng)度函數(shù)F（x，y）進(jìn)行指數(shù)定標(biāo)，形成新的適應(yīng)度函數(shù)fitness，可以擴大個體間的競爭，但又不違反適應(yīng)度函數(shù)基本性原則;算法第4步采用了最優(yōu)個體的保優(yōu)原則，最優(yōu)的個體不經(jīng)歷遺傳算子運算，直接進(jìn)行下一步，降低算法運行的時間，能適當(dāng)減少迭代的次數(shù)，能夠?qū)崿F(xiàn)高效迭代尋優(yōu);算法第7步，采用了單純形法，顯然是作為GA局部搜索的算子，這樣，可以利用單純形法局部搜索能力強的優(yōu)勢加強GA的局部搜索能力。

4 仿真實驗與評價

4.1 仿真場景與參數(shù)設(shè)置

在［100，100］m的區(qū)域內(nèi)，用 Matlab分別對傳統(tǒng) DV—Hop定位算法，GA DV—Hop定位算法與GA+單純形法的DV—Hop定位算法進(jìn)行仿真，為了使算法的仿真結(jié)果更加真實，每一次仿真開始前，由參數(shù)（WSNs的連通度與信標(biāo)節(jié)點的密度）生成網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu);在所有的節(jié)點中隨機生成信標(biāo)節(jié)點，并且信標(biāo)節(jié)點均勻散布在區(qū)域內(nèi)（要比隨機散布性能好）［15］;在每一種條件下仿真多次，之后分別對其結(jié)果求其平均值;只討論各項同性的WSNs。

用網(wǎng)絡(luò)的覆蓋程度與平均定位誤差評價定位性能的優(yōu)劣［16］，定位誤差

GA+單純形法需要設(shè)定參數(shù)，本文采用二進(jìn)制編碼，編碼長度l=14，群體規(guī)模M=50，交叉概率pc=0.9，變異概率pm=0.02，迭代次數(shù)tm=200;本文采用了Nelder-mead單純形法，其中，需要設(shè)定的參數(shù)為反射因子α、擴張因子β、收縮因子 γ，各因子取 α =1，β =0.5，γ =2，經(jīng)仿真實驗，如上參數(shù)的設(shè)置，具有良好的定位性能。

4.2 結(jié)果分析

1）網(wǎng)絡(luò)連通度對定位精度的影響

在區(qū)域內(nèi)布置250個節(jié)點，假設(shè)信標(biāo)節(jié)點的個數(shù)為10，圖1為傳統(tǒng) DV—Hop定位算法、GA DV—Hop定位算法與GA+單純形法的DV—Hop定位算法的仿真圖，由圖可知，當(dāng)連通度小于10時，3種算法的誤差都降低，且幅度較大，而GA定位性能明顯優(yōu)于傳統(tǒng)DV—Hop定位算法，GA+單純形法的定位算法誤差又小于GA，這是由于單純形法彌補了GA的一些弊端;當(dāng)連通度大于10時，由于估計值為相隔的跳數(shù)，隨著網(wǎng)絡(luò)連通度增加，把相隔的跳數(shù)看做估計值估計距離就不精確了，因此，3種定位算法的性能都有所惡化，但是GA+單純形法的DV—Hop算法精確度明顯高于另外2種算法，而且其惡化幅度也較緩慢。

圖1 網(wǎng)絡(luò)連通度對定位精度的影響Fig 1 Impacts of network connectivity on localization precision

2）信標(biāo)節(jié)點數(shù)目對定位精度的影響

在區(qū)域布置250個節(jié)點，信標(biāo)節(jié)點比例由0.02～0.12，圖2為在各向同性網(wǎng)絡(luò)中信標(biāo)節(jié)點比例對3種算法的影響，由圖可知，隨著信標(biāo)節(jié)點比例的增加，3種定位算法的性能都有所改善，誤差減小明顯，這是由于隨著信標(biāo)節(jié)點比例的增加，可利用的定位節(jié)點的數(shù)目增加，網(wǎng)絡(luò)的可知性增強，而且在信標(biāo)節(jié)點的各個比例下，GA+單純形法的定位算法定位精度始終高于另外2種算法。

圖2 信標(biāo)節(jié)點數(shù)目對定位精度的影響Fig 2 Impacts of beacon node number on localization precision

3）信標(biāo)節(jié)點數(shù)目對網(wǎng)絡(luò)覆蓋率的影響

由圖3可知，隨著信標(biāo)節(jié)點比例的增加，3種定位算法的網(wǎng)絡(luò)覆蓋程度都有所加大，而且GA DV—Hop定位精確性優(yōu)于傳統(tǒng)DV—Hop算法，而GA+單純形法的定位性能又顯著優(yōu)于GA DV—Hop定位，在信標(biāo)節(jié)點比例較小的時候，網(wǎng)絡(luò)覆蓋程度增大的幅度較大，3種算法覆蓋程度的差距也較大，信標(biāo)節(jié)點的比例增加到一定的程度，網(wǎng)絡(luò)覆蓋程度增加的也較為緩慢，算法之間的差距也減小，趨于平穩(wěn)。

圖3 信標(biāo)節(jié)點數(shù)目對網(wǎng)絡(luò)覆蓋率的影響Fig 3 Impacts of beacon node number on network coverage rate

5 結(jié)論

GA由于本身的特性適合對傳統(tǒng)的DV—Hop定位得出的位置進(jìn)行修正，本文提出一種基于GA+單純形法的混合GA對傳統(tǒng)的DV—Hop定位的第三階段進(jìn)行優(yōu)化，計算量與能量沒有過多增加，卻保留了GA的優(yōu)勢，也利用了單純較強的領(lǐng)域先驗性彌補了GA的一些固有缺陷，仿真結(jié)果表明:改進(jìn)算法在各項同性的WSNs中比其它定位算法有更高的定位精度與網(wǎng)絡(luò)覆蓋率，非常適合于WSNs的定位，是一種行之有效的改進(jìn)算法。

［1］張西紅，周 順，陳立云.無線傳感網(wǎng)技術(shù)及其軍事應(yīng)用［M］.北京:國防工業(yè)出版社，2010.

［2］景 博，張 劼，孫 勇.智能網(wǎng)絡(luò)傳感器與無線傳感器網(wǎng)絡(luò)［M］.北京:國防工業(yè)出版社，2011.

［3］謝曉松，程良倫.無線傳感器網(wǎng)絡(luò)基于移動信標(biāo)動態(tài)選擇的定位算法［J］.傳感器與微系統(tǒng)，2011，30（1）:123-130.

［4］馬潤澤，余志軍，劉海濤.一種距離無關(guān)的無線傳感器網(wǎng)絡(luò)定位算法［J］.傳感器與微系統(tǒng)，2011，30（11）:131-134.

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

［6］歐陽丹彤，何金勝，白洪濤.一種約束粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法［J］.計算機科學(xué)，2011，38（7）:46-49.

［7］李牧東，熊 偉，郭 龍.基于人工蜂群算法的 DV—Hop定位改進(jìn)［J］.計算機科學(xué)，2013，40（1）:33-36.

［8］陳 坤，李 莉，李繼云.基于遺傳算法的井下無線傳感器網(wǎng)絡(luò)節(jié)點定位研究［J］.煤炭工程，2010（10）:120-122.

［9］鄧 力.基于 遺傳算法 WSNs節(jié)點定位算法研究［J］.計算機仿真，2011，28（9）:161-164.

［10］趙仕俊，孫美玲，唐懿芳.基于遺傳模擬退火算法的無線傳感器網(wǎng)絡(luò)定位算法［J］.計算機應(yīng)用與軟件，2009，26（10）:189-192.

［11］范玉紅，彭 宏，朱陳良.一種基于遺傳模擬退火算法和RSSI的無線傳感器網(wǎng)絡(luò)定位算［J］.西安大學(xué)學(xué)報，2010，29（6）:51-54.

［12］Chehri A，F(xiàn)ortier P，Tardif P M.Geolocation with wireless sensor networks using nonlinear optimization［C］//Proceedings of International Journal of Computer Science and Network Security（IJCSNS），2008:1452154.

［13］柴玉梅，張坤麗.人工智能［M］.北京:機械工業(yè)出版社，2012.

［14］張清華.人工智能技術(shù)及應(yīng)用［M］.北京:中國石化出版社，2011.

［15］郭紹永，談 冉.遺傳算法在無線傳感器網(wǎng)絡(luò)中的應(yīng)用［J］.傳感器與儀器儀表，2009，25（4-1）:125-127.

［16］楊石磊，樊曉平，劉少強.一種改進(jìn)的無線傳感器網(wǎng)絡(luò) DV—Hop定位算法［J］.計算機測量與控制，2008，16（9）:1356-1357.