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

劉彥隆，呂顯朋，王相國

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

0 引言

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

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

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

1 相關理論

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

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

利用最小二乘法

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

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

則問題可化為求解

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

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

2 混合GA求解約束問題

2.1 算法的原理

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

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

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

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

2.2 求解約束問題

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

式中Cmax為最大系數。

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

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

綜上，算法基本流程為:

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

2）隨機的產生群體規模為n的初始群體。

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

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

5）GA的操作，產生新的一代Ps:

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

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

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

d.更新:p←ps。

6）第4步最優的5個個體與第5步遺傳操作后的個體數為n-5的群體ps組成新群體。

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

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

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

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

4 仿真實驗與評價

4.1 仿真場景與參數設置

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

用網絡的覆蓋程度與平均定位誤差評價定位性能的優劣［16］，定位誤差

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

4.2 結果分析

1）網絡連通度對定位精度的影響

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

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

2）信標節點數目對定位精度的影響

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

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

3）信標節點數目對網絡覆蓋率的影響

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

圖3 信標節點數目對網絡覆蓋率的影響Fig 3 Impacts of beacon node number on network coverage rate

5 結論

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

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

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

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

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

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

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

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

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

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

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

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

［12］Chehri A，Fortier 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］.北京:機械工業出版社，2012.

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

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

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