基于RSSI和融合智能優化算法的無線傳感器網絡定位算法

張先超，劉興長，鐘一洋，張春園

(后勤工程學院 a.后勤信息與軍事物流工程系;b.學員旅，重慶 401311)

無線傳感器網絡(wireless sensor networks，WSN)是由隨機部署在目標區域內的數量巨大的離散傳感器節點組成，通過無線通信方式形成的一個多跳的自組織網絡系統［1］。節點的位置信息至關重要，在導航、跟蹤、監控等應用中起關鍵性作用。根據是否需要測量節點間的距離，定位可以分為基于測距(range-based)的定位和無需測距(range-free)的定位;根據部署的場合可分為室外定位和室內定位［2］。通常情況下，基于測距的定位算法的定位精度高于無需測距的定位算法的定位精度。基于測距定位的常用方法包括角度定位(AOA)［3］、三邊定位(trilateration)和極大似然估計等。常用的測距方式包括接收信號指示強度(RSSI)［4］、信號傳播時間/時間差/往返時間(TOA/TDOA/RTOF)［5］、接收信號相位差(PDOA)、近場電磁測距(NFER)等。由于基于RSSI的測距方式無需增加額外設備、簡單易行，在近年來發表的研究成果中得到廣泛采用。

近年來，許多學者將智能算法應用于基于測距的無線傳感器網絡定位算法中。文獻［6－7］使用粒子群優化算法定位，取得了優于極大似然估計法等算法的定位結果，但是由于單一智能算法性能存在缺陷，必須進行改進以滿足無線傳感器網絡定位的實際應用。文獻［8－10］針對粒子群優化算法的缺點提出改進算法，克服了粒子群優化算法后期易陷入局部最優的缺陷，進一步提高了定位精度。但是上述改進算法避免粒子陷入局部最優的能力有限，不能保證粒子有效逃離局部最優。針對基于粒子群優化的無線傳感器網絡定位算法后期易陷入局部最優、算法穩定性較差的缺陷，提出一種粒子群和人工魚群融合優化算法，將其應用于無線傳感器網絡節點定位中，以克服上述缺陷，提高定位算法的性能。

1 RSSI測距模型

節點在通信時可以直接獲取RSSI值，估計出未知節點與錨節點的距離。很多學者對RSSI測距進行了深入研究，根據實驗環境的不同建立了多種基于RSSI的測距模型。其中，對數－常態分布模型(log-distance distribution)考慮了實際環境的復雜性，能反映信號傳播過程中引入的噪聲對測距結果的影響［11－12］。對數－常態分布模型路徑損耗計算公式如下:

式(1)中:d為發射端與接收端之間的距離;PL(d)是經過距離d后的路徑損耗;n為信道衰減指數，一般取值為2～5;Xδ是均值為0、標準差為δ的高斯隨機噪聲變量，標準差的取值一般為4～10;d0是參考距離，一般取1 m。對式(1)化簡得到:

式(2)中A為1 m處的RSSI值。通常情況下，測距誤差隨著測量距離的增加而增大［13］，即由較大的RSSI值計算得到的距離值誤差較小，而由較小的RSSI值計算得到的距離值誤差較大。

2 相關知識

2.1 粒子群優化算法

粒子群優化(particle swarm optimization，PSO)算法是在無線傳感器網絡定位中常用的一種群體智能優化算法，文獻［6－10］均采用PSO算法或改進的PSO算法。PSO算法是一種操作簡單的群體智能優化算法，其實現原理如下:

假設在D維的搜索空間內，存在一個種群大小為M的粒子群;存在一個數量為N的搜索目標群。每個粒子在空間中的位置坐標 xi=(xi1，xi2，…，xid)，搜索速度 vi=(vi1，vi2，…，vid)，搜索到的個體最優位置為pi=(pi1，pi2，…，pid)，搜索到的全局最優位置為gb=(gb1，gb2，…，gbd)，其中，i=(1，2，…，M)，d=(1，2，…，D)。算法采用下列公式對粒子進行操作［14］:

式中:學習因子c1和c2是非負的常數，常設c1=c2=2;r1和r2是介于［0，1］的隨機數;w為慣性權重，用來保持局部搜索和全局搜索的平衡，較大的w有利于算法的全局搜索能力，較小的w有利于算法的局部搜索能力;vid∈［－vmax，vmax］，vmax過大容易使粒子飛離最優解，vmax過小容易使粒子陷入局部最優，粒子的速度通常設為每維變換范圍的10%～20%;k為當前迭代次數;T為終止迭代次數。

2.2 人工魚群算法

人工魚群(artificial fish school，AFS)算法由李曉磊等于2002年提出［15］，是一種全局尋優能力強、簡單、易操作的群體智能優化算法。該算法通過模擬魚類的覓食、群聚、追尾、隨機等行為在搜索域中進行尋優。AFS算法的數學模型中各變量參數描述如下:人工魚群個體大小為N;人工魚個體的狀態 Xi=(x1，x2，…，xn)，其中xi(i=1，2，…，n)為待優化變量;第i條人工魚當前所在位置的食物濃度即目標函數Yi;人工魚個體之間的距離為di，j;人工魚的感知范圍為Visual;人工魚移動的最大步長為Step;擁擠度為delta;覓食行為嘗試的最大次數為try_number;當前覓食行為次數為n;最大迭代次數為MAXGEN。

1)覓食行為

設Xi為人工魚當前的狀態，Xj為其感知范圍Visual內隨機選擇的一個狀態，如果待優化問題是求極大值，則當Yi＜Yj時人工魚向Xj方向前進1步(若待優化問題是求極小值，則當Yi＞Yj時人工魚向Xj方向前進1步);反之，在感知范圍內重新選擇狀態Xj，判斷是否滿足上述條件。當嘗試次數達到最大值try_number時，若仍未找到滿足條件的Xj，人工魚則隨機移動1步。

2)聚群行為

對于人工魚探索當前范圍內(即di，j＜Visual)的伙伴數目nf及中心位置Xc，若滿足Yc/nf＞delta*Yi，則表明伙伴中心的食物濃度較高并且人工魚數量不多，則人工魚朝伙伴的中心位置方向移動1步;否則執行覓食行為。

3)追尾行為

對于人工魚探索當前范圍內(即di，j＜Visual)的伙伴數目nf及食物濃度最大的伙伴Xj，若滿足Yj/nf＞delta*Yi，則表明伙伴Xj處的食物濃度較高并且周圍人工魚數量不多，則人工魚朝伙伴Xj位置方向移動1步;否則執行覓食行為。

4)隨機行為

隨機行為即人工魚在Visual內隨機選擇一個移動方向Xi ext，人工魚按如下公式進行該行為:

其中r是［－1，1］區間內的隨機數。

2.3 WSN 定位原理

假設在一定區域內布置有M個錨節點，N個未知節點。錨節點的坐標為Ai(xi，yi)，i=(1，2，…，M)，未知節點的坐標為Nj(xj，yj)，j=(1，2，…，N)，已知錨節點和未知節點的距離測量值di。基于測距的WSN定位問題可描述為如下的最優化問題:

基于群體智能優化的WSN定位方法采用式(7)作為適應度函數，WSN的錨節點相當于該算法中的種群S，未知節點的坐標即要搜索的位置。

3 基于粒子群和人工魚群融合優化的WSN定位算法

3.1 算法基本思想

PSO算法和AFS算法都是典型的群體智能優化算法。PSO算法具有收斂速度快的特點，但在算法后期，由于粒子同一化，算法易陷入局部最優;AFS算法尋優速度較快，并具有全局尋優的能力，但算法精度略低于PSO算法。綜合利用兩種算法的優點，提出一種適合WSN定位的粒子群和人工魚群融合優化(hybrid optimization algorithm based on particle swarm and artificial fish swarm algorithm，PSO-AFS)算法，該算法能克服兩種算法各自存在的缺點。

3.2 算法分析和實現

PSO-AFS算法的具體執行過程如下:

1)初始化種群S。在尋優區域內隨機或固定部署一個大小為S的種群，合理設置PSO算法和AFS算法各變量的參數，算法的參數設置如下:

① 對于PSO 算法，c1=c2=2，vmax=5，vmin=－5，wmax=0.9，wmin=0.4;

② 對于AFS算法visual=3.5，step=1，delta=0.618，try_number=50;

③PSO-AFS算法的參數與PSO算法和AFS算法對應的參數相同。

2)設置公告板。公告板數值為besty，用來記錄每次迭代產生的適應度函數的最優值，公告板初值為初始化的種群S對應的適應度函數值。

3)迭代尋優。在每次迭代中對種群分別用PSO算法、AFS算法進行操作，PSO算法每次迭代得到適應度函數最優值為T1，AFS算法每次迭代得到適應度函數最優值為T2。

4)種群變異。分別對兩種算法各自種群個體的適應度函數值排序，對其中最差的30%個體按式:X=bestx+rand進行變異操作，PSO算法和AFS算法各自更新種群，分別得到新的種群S1、S2。

5)更新公告板和種群。比較兩種算法得到的適應度函數最優值T1和T2，對公告板和種群進行更新，其偽代碼如下:

6)停止迭代，輸出結果。當尋優的誤差小于控制值或達到最大迭代次數MAXGEN時停止迭代，輸出尋優結果及其對應的種群個體的狀態，即未知節點位置。

4 算法仿真與分析

本文采用Matlab進行仿真實驗，分別考慮兩種仿真環境:①在一定區域內進行單個未知節點定位;②模擬具體環境，在一定區域內鋪設大量未知節點進行整體定位。

4.1 仿真場景1

在30 m×30 m的面積內隨機部署8個錨節點，1個未知節點，節點通信半徑為30 m，算法的最大迭代次數MAXGEN為50次。

1)算法穩定性和收斂速度仿真結果分析

設定位誤差控制值為0 m，測距誤差為10%。圖1是3種算法的收斂曲線，由圖可知:PSO-AFS算法的收斂曲線與PSO算法、AFS算法相比始終更加平滑、穩定，且收斂速度明顯快于另外兩種算法。

圖1 算法的收斂曲線

設平均定位誤差(誤差控制值)為0.5 m，測距誤差0%，獨立進行20次實驗，分析每次實驗中3種算法的終止迭代次數。由圖2可知:相同精度下PSO-AFS算法每次最終迭代次數的值波動較小，說明PSO-AFS算法的穩定性較好，明顯優于另外兩種算法。

2)算法的定位精度仿真結果分析

為了驗證基于PSO-AFS算法的無線傳感器網絡定位算法的性能，設置不同仿真參數，研究迭代次數和測距誤差對定位誤差的影響，分別獨立進行100次實驗。

設測距誤差為0%，設置不同最大迭代次數進行仿真實驗。圖3為3種算法的平均定位誤差隨迭代次數的變化情況。由于PSO-AFS算法的收斂速度明顯快于AFS、PSO兩種算法，所以在迭代次數較少的情況下，PSO-AFS算法的定位精度明顯高于其他兩種算法，體現了PSO-AFS算法的優越性。由于PSO-AFS算法在進行迭代尋優時收斂速度和尋優精度性能更好，用較短的計算時間即可得到較精確的計算結果。

圖2 算法的終止迭代次數

圖3 迭代次數對平均定位誤差的影響

設最大迭代次數MAXGEN為10次，研究3種算法在不同測距誤差情況下的定位精度。由圖4可知，隨著平均測距誤差的增加，3種算法的定位誤差均呈上升趨勢，這是由于基于測距的定位算法受測距誤差影響較大造成的。盡管3種算法的定位誤差均受測距誤差影響較大，但PSO-AFS算法的定位誤差始終小于其他兩種算法。PSO-AFS算法與PSO算法相比平均定位誤差減小了0.6 m左右，與AFS算法相比平均定位誤差減小了0.4 m左右。

圖4 平均測距誤差對平均定位誤差的影響

4.2 仿真場景2

改變傳感器節點部署區域和節點數目，在100 m×100 m的二維平面內隨機部署n個錨節點和30個未知節點;節點通信半徑為30 m;設最大迭代次數MAXGEN為20次;RSSI測距算法中，設信道衰減指數n為4，為了盡量模擬實際環境噪聲的影響，設零均值高斯隨機噪聲變量Xδ的標準差δ為4。

圖5為未知節點平均定位誤差隨錨節點個數的變化情況，由圖可知:隨著錨節點數目的增加，3種算法的平均定位誤差均呈下降趨勢，但當錨節點個數增加到一定程度時，平均定位誤差的變化趨勢減小甚至達到了臨界狀態，但PSO-AFS算法的平均定位誤差始終小于其他兩種算法的平均定位誤差。

圖5 錨節點數目對平均定位誤差的影響

5 結束語

由于單一智能優化算法存在不同的性能缺陷，基于單一智能優化算法的WSN定位算法也存在著不足。PSO算法收斂速度快、尋優精度高，但后期易陷入局部最優，導致個別時候尋優結果較差;AFS算法的穩定性較好，全局尋優能力強，不易陷入局部最優，但其收斂速度慢于PSO算法，且尋優精度略低于PSO算法。PSO-AFS算法綜合利用了PSO算法收斂速度快、尋優精度高和AFS算法全局尋優能力強、穩定性好的優點，克服了各自存在的不足。基于PSO-AFS算法的WSN定位算法比基于單一PSO算法或AFS算法的WSN定位算法的性能更加優越。仿真結果表明:PSO-AFS定位算法只需較少的迭代次數即可得出較準確的定位結果，且定位精度和穩定性較好，適合于WSN的應用。

［1］宋文，王兵，周應兵，等.無線傳感器網絡技術與應用［M］.北京:電子工業出版社，2007:1－10.

［2］李曉維，徐勇軍，任豐原.無線傳感器網絡技術［M］.北京:北京理工大學出版社，2007:191－192.

［3］Al-Jazzar Saleh，Ghogho Mounir，McLernon Desmond.A joint TOA/AOA constrained minimization method for locating wireless devices in non-line-of-sight environment［J］.IEEE Transactions on Vehicular Technology，2009，58(1):468－472.

［4］方震，趙湛，郭鵬，等.基于RSSI的測距分析［J］.傳感技術學報，2007，20(11):2528－2530.

［5］Savvides A，Han C C，Strivastava M B.Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors［C］//Proc.of MOBICOM.［S.l.］:［s.n.］，2001:166－179.

［6］Low K S，Nguyenh A G.Optimization of sensor node locations in a wireless sensor network［C］//ICNC’08 4th Int Conf on Natural Computation.Piscataway:IEEE，2008:286－290.

［7］陳志奎，司威.傳感器網絡的粒子群優化定位算法［J］.通信技術，2011，44(1):102－104，108.

［8］黃艷，臧傳治，于海斌.基于改進粒子群優化的無線傳感器網絡定位算法［J］.控制與決策，2012，27(1):156－160.

［9］馮秀芳，呂淑芳.基于RSSI和分步粒子群算法的無線傳感器網絡定位算法［J］.控制與決策，2014，29(11):1－7.

［10］王俊，李樹強，劉剛.無線傳感器網絡三維定位交叉粒子群算法［J］.農業機械學報，2014，45(5):233－238.

［11］陳維克，李文鋒，首珩，等.基于RSSI的無線傳感器網絡加權質心算法定位［J］.武漢理工大學學報，2006，30(2):265－268.

［12］張先超，劉興長，張春園.基于次錨節點的無線傳感器網絡改進加權質心定位算法［J］.傳感器與微系統，2015，34(2):143－146.

［13］Chen W，Mei T，Sun L，et al.Error analyzing for RSSI-based localization in wireless sensor networks［C］//Intelligent Control and Automation，2008.WCICA 2008.7th World Congress on.IEEE.［S.l.］:IEEE，2008:2701－2706.

［14］史峰，王輝.MATLAB智能算法30個案例分析［M］.北京:北京航空航天大學出版社，2011:102－107.

［15］李曉磊.一種新型的智能優化方法—人工魚群算法［D］.杭州:浙江大學，2003.