混合遺傳算法在WSNs定位中的應用*

劉彥隆，呂顯朋，王相國

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

0 引言

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

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

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

1 相關理論

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

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

利用最小二乘法

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

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

則問題可化為求解

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

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

2 混合GA求解約束問題

2.1 算法的原理

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

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

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

單純形法通過相應的一系列轉換，把各種非標準形式的問題變化成標準形式，從而求解;因此，它對含有很多個約束條件的非標準形式的線性問題的求解非常有效。

2.2 求解約束問題

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

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

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

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

綜上，算法基本流程為:

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

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

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

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

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

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

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

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

d.更新:p←ps。

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

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

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

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

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

4 仿真實驗與評價

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

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

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

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

4.2 結果分析

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

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

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

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

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

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

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

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

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

5 結論

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

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

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

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

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

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

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

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

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

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

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

［11］范玉紅，彭 宏，朱陳良.一種基于遺傳模擬退火算法和RSSI的無線傳感器網(wǎng)絡定位算［J］.西安大學學報，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］張清華.人工智能技術及應用［M］.北京:中國石化出版社，2011.

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

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