基于人工魚群算法的改進質心定位算法

汪 晨，張玲華

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003； 2.江蘇省通信與網絡技術工程研究中心，江蘇 南京 210003)

0 引 言

無線傳感器網絡[1]是一種分布式自組織網絡，由于網絡的部署方式，傳感器節點通常無法知道自身的位置[2]，例如由飛機向監測區域拋撒傳感器節點。但是節點位置信息是大多數無線傳感器網絡應用的關鍵，一方面監測消息如果不攜帶位置信息往往是毫無意義的，另一方面節點位置信息還是眾多無線傳感器網絡技術的基礎，如負載均衡、拓撲配置[3]等。

通常情況下，無線傳感器網絡定位算法可分為兩類：基于距離的(range-based)和距離無關的(range-free)[4]。基于距離的定位算法[5]使用到達角度或RSSI等技術測量點到點之間的距離；距離無關的定位算法[6]則利用跳數或網絡連通度等信息來估計未知節點的坐標，因此它在成本和功耗方面與前者相比具有一定優勢[7]。

文中提出了一種基于人工魚群算法優化的節點定位算法，先利用加權質心算法獲取待定位節點和錨節點的距離信息，然后利用多邊定位算法構建誤差函數，最后采用人工魚群算法對誤差函數進行優化以獲得更好的定位精度。

1 人工魚群算法

1.1 基本思想

人工魚群算法是一種新型的智能優化算法[8]，其基本思想是:根據水域中魚的數目最多的地方所含營養物質最多的特點，模仿魚的聚群、覓食、追尾等行為，利用局部最優，經過逐步迭代、優化達到全局尋優。具體過程描述如下:隨機生成n只人工魚(候選解空間)組成初始種群;第i條人工魚候選解表示為Xi=(xi1,xi2,…,xin)，其中d表示解的維數[9]；根據初始種群內的適應度對種群進行初始化設置，包括每條人工魚的初始位置、人工魚的視野Visual、人工魚的步長Step、最大迭代次數IT、嘗試次數Tn、擁擠度因子δ和要執行吞食行為的閾值T_value[10-11]。

假定第i條人工魚當前位置為Xi(t)，下一個狀態為Xi(t+1)，每次迭代人工魚都選擇一種行為來更新自己的位置信息，即在原位置Xi(t)的基礎上加上一個增量ΔXi(t+1)。

人工魚群算法的位置更新公式為[12]：

ΔXi(t+1)=Rand()*Step*[Xbetter(t+1)-Xi(t)]

(1)

Xi(t+1)=Xi(t)+ΔXi(t+1)

(2)

其中，Rand()是0到1之間產生的隨機數；Xbetter(t+1)為更好的人工魚位置。

經過上述更新公式，如果Xi(t+1)比Xi(t)更好，則用Xbetter(t+1)替換Xi(t+1)，否則根據式1和式2進行下次迭代更新，直到迭代結束或搜索到全局最優解。

1.2 人工魚的基本行為描述

(1)覓食行為。

設Xi為人工魚i的當前狀態，Xj為人工魚i在其視野Visual內的隨機狀態，其公式如下：

Xj=Xi+Visual*Rand()

(3)

若求極大值時，當滿足Xi>Xj(若求極小值滿足Xi

(4)

(5)

(2)聚群行為。

設Xi為人工魚i的當前狀態，nf表示人工魚數，Xc表示魚群的中心位置，若Xc/nf>δXi，表示人工魚的數量少，且在魚群中心位置有豐富的食物，此時由式6繼續更新人工魚的狀態。若不滿足Xc/nf>δXi，重新進行覓食行為。

(6)

(3)追尾行為[13]。

設人工魚i的當前狀態為Xi，在魚群搜索范圍內(dijδXi時，Xj為最優狀態，此時說明Xj方向食物充足，則人工魚i向伙伴Xj方向前進一步；否則執行覓食行為。

(4)隨機行為。

根據人工魚的當前狀態Xi，在其視野范圍Visual內隨機選取一個狀態，如式7所示。

(7)

(5)公告板。

人工魚的狀態信息記錄在公告板中。當完成上述行為后，對比此時狀態和公告板中記錄的狀態。若當前狀態比公告板中的狀態好，則更新公告板，反之保持不變。

2 距離加權質心定位算法

質心定位算法是一種基于網絡連通性的定位算法。其中心思想為：利用待測節點通信范圍內的鄰居錨節點進行位置估算，將所有錨節點分布位置連成一多邊形，求出多邊形質心作為待測節點的位置。由于質心算法中各個錨節點廣播的信息存在誤差，每個錨節點對待測節點影響程度也不同，特別當錨節點密度過低時甚至會出現無法定位的現象。針對這一缺點，可以通過加權因子體現各錨節點對質心位置的影響程度[14]，反映它們的內在關系。

(8)

由于傳統的三邊定位法在復雜的環境因素下定位精度不高，因此提出一種改進的加權質心方法以提高定位精度。將三邊定位法求出的質心點通過改進的人工魚群算法進行迭代更新，直至得到最優解。

3 人工魚群質心定位算法

(9)

對于與待定位節點相關的n個錨節點，誤差函數表示如下：

(10)

由于不同距離測距誤差不同，所以對不同的錨節點進行加權，對距離較遠的用較小權值，對距離較近的用較大權值。所以，通過待定位節點與錨節點的距離的倒數作為對誤差函數的加權系數來構造人工魚群算法的適應度函數。

(11)

通過人工魚群算法對加權質心算法進行優化，記錄未知節點與錨節點估計距離，與實際距離相比較，尋找誤差最小值，從而估算未知節點的位置。文中的算法的流程如下：

(12)

Step2：初始化設置，包括人工魚數量N、每條人工魚的初始位置、人工魚的視野Visual、人工魚的步長Step、最大迭代次數IT、嘗試次數Tn、擁擠度因子δ和要執行吞食行為的閾值T-value等。

Step3：比較每條人工魚周圍食物的濃度，選出濃度最大的人工魚信息并記錄在公告板中。

Step4：對每條人工魚執行追尾行為、聚群行為和隨機行為，采用行為選擇策略，計算每條魚食物濃度，選出最優值與公告板中的值相比較。如果好于公告板中的則替換，最終公告板值始終保持最優。

Step5：判斷是否滿足結束條件，如果滿足則返回Step4，公告板值即最優值。

4 仿真實驗與分析

4.1 仿真環境與參數

在Matlab平臺上，將基于人工魚群質心算法、加權質心算法以及質心算法在不同錨節點密度、不同節點密度和不同節點通信半徑三種情況下進行仿真對比。仿真過程中，選擇100 m×100 m的正方形區域，未知節點和錨節點隨機部署在正方形區域內。同時，人工魚群算法中群內解個數N=50，迭代次數IT=100，擁擠度因子δ=1，視野Visual=10，步長Step=8。為了減少實驗中隨機誤差的干擾，每組參數獨立運行50次，定位誤差取50次運行結果的平均值。定位誤差error為：

(13)

4.2 結果分析

在總節點數為100，節點通信半徑為30 m，錨節點數從12個變化到30個的情況下，得到三種算法的定位誤差對比圖(見圖1)。從圖中可以看出，隨著錨節點密度的增加，三種算法的定位誤差都有所降低，但整個過程中魚群質心定位算法的定位誤差始終低于質心算法和加權質心算法的定位誤差。

圖1 不同錨節點密度的定位誤差曲線

圖2為平均定位誤差隨總節點個數的變化曲線。仿真時保持錨節點密度為20%不變，節點通信半徑為30 m。仿真結果表明，魚群質心算法的定位精度隨總節點數的增加而提高，且明顯優于其他兩種算法。

圖2 不同總節點數的定位誤差曲線

圖3中改變錨節點通信半徑，觀察平均定位誤差的變化情況。隨機分布100個傳感器節點，其中錨節點密度為20%。仿真結果表明，在相同條件下，隨著節點通信半徑的增大，魚群質心算法的定位精度高于質心算法和加權質心算法。

圖3 不同半徑的定位誤差曲線

5 結束語

文中提出的改進算法是在加權質心算法的基礎上，引入人工魚群智能算法。利用人工魚群算法穩定性好、全局尋優能力強的特點，減少質心定位算法中三邊測量法帶來的誤差。該算法不可避免地增加了少量

的計算開銷，但與傳統質心算法和加權質心算法的對比表明，該算法具有更高的定位精度。

參考文獻：

[1] YICK J,MUKHERJEE B,GHOSAL D.Wireless sensor network survey[J].Computer Networks,2008,52(12):2292-2330.

[2] 王福豹，史 龍，任豐原．無線傳感器網絡中的自身定位系統和算法[J]．軟件學報，2005，16(5):857-868．

[3] 陳節節.無線傳感器網絡三邊測量法研究概述[J].硅谷,2010(24):7.

[4] 徐原博,鐘麗鴻,崔 洋,等.基于無線傳感器網絡的極大似然定位法的分析[J].傳感器與微系統,2011,30(10):37-40.

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

[6] 陳星舟，廖明宏，林建華.基于粒子群優化的無線傳感器網絡節點定位改進[J].計算機應用,2010,30(7):1736-1738.

[7] NICULESCU D,NATH B.DV based positioning in Ad Hoc net-works[J]. Telecommunication Systems,2003,22(1-4):267-280．

[8] KUANG Luobei, WANG Zhijun, XU Ming. End-to-end transmission time-based opportunistic routing protocols for bus networks[J].Turkish Journal of Electrical Engineering & Computer Sciences，2013,21(2):470-492．

[9] 張先超，劉興長，張春園．基于次錨節點的無線傳感器網絡改進加權質心定位算法[J]．傳感器與微系統，2015，34(2)：143-146．

[10] 江銘炎，袁東風．人工魚群算法及其應用[M]．北京：科學出版社，2012.

[11] 唐 莉,張正軍,王俐莉.人工魚群算法的改進[J].計算機技術與發展,2016,26(11):37-40.

[11] 黃 仁，秦占明．基于人工魚群算法的無線室內定位優化[J]．計算機應用，2015，35：14-17．

[12] 徐善永，黃友銳，曲立國.基于人工魚群算法煤礦井下人員定位技術研究[J].煤炭工程，2013，45(11)：129-131.

[13] 李凌燕,杜永貴.改進型粒子群優化在WSNs節點定位中的應用[J].計算機應用與軟件，2014,31(4):69-72.

[14] 朱 博，陳 曙．一種無線傳感器網絡質心定位改進算法[J]．傳感技術學報，2010，23(6)：868-872.