基于人工魚群算法的改進(jìn)質(zhì)心定位算法

汪 晨，張玲華

(1.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003； 2.江蘇省通信與網(wǎng)絡(luò)技術(shù)工程研究中心，江蘇 南京 210003)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)[1]是一種分布式自組織網(wǎng)絡(luò)，由于網(wǎng)絡(luò)的部署方式，傳感器節(jié)點(diǎn)通常無(wú)法知道自身的位置[2]，例如由飛機(jī)向監(jiān)測(cè)區(qū)域拋撒傳感器節(jié)點(diǎn)。但是節(jié)點(diǎn)位置信息是大多數(shù)無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用的關(guān)鍵，一方面監(jiān)測(cè)消息如果不攜帶位置信息往往是毫無(wú)意義的，另一方面節(jié)點(diǎn)位置信息還是眾多無(wú)線傳感器網(wǎng)絡(luò)技術(shù)的基礎(chǔ)，如負(fù)載均衡、拓?fù)渑渲肹3]等。

通常情況下，無(wú)線傳感器網(wǎng)絡(luò)定位算法可分為兩類：基于距離的(range-based)和距離無(wú)關(guān)的(range-free)[4]?；诰嚯x的定位算法[5]使用到達(dá)角度或RSSI等技術(shù)測(cè)量點(diǎn)到點(diǎn)之間的距離；距離無(wú)關(guān)的定位算法[6]則利用跳數(shù)或網(wǎng)絡(luò)連通度等信息來(lái)估計(jì)未知節(jié)點(diǎn)的坐標(biāo)，因此它在成本和功耗方面與前者相比具有一定優(yōu)勢(shì)[7]。

文中提出了一種基于人工魚群算法優(yōu)化的節(jié)點(diǎn)定位算法，先利用加權(quán)質(zhì)心算法獲取待定位節(jié)點(diǎn)和錨節(jié)點(diǎn)的距離信息，然后利用多邊定位算法構(gòu)建誤差函數(shù)，最后采用人工魚群算法對(duì)誤差函數(shù)進(jìn)行優(yōu)化以獲得更好的定位精度。

1 人工魚群算法

1.1 基本思想

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

假定第i條人工魚當(dāng)前位置為Xi(t)，下一個(gè)狀態(tài)為Xi(t+1)，每次迭代人工魚都選擇一種行為來(lái)更新自己的位置信息，即在原位置Xi(t)的基礎(chǔ)上加上一個(gè)增量Δ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之間產(chǎn)生的隨機(jī)數(shù)；Xbetter(t+1)為更好的人工魚位置。

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

1.2 人工魚的基本行為描述

(1)覓食行為。

設(shè)Xi為人工魚i的當(dāng)前狀態(tài)，Xj為人工魚i在其視野Visual內(nèi)的隨機(jī)狀態(tài)，其公式如下：

Xj=Xi+Visual*Rand()

(3)

若求極大值時(shí)，當(dāng)滿足Xi>Xj(若求極小值滿足Xi

(4)

(5)

(2)聚群行為。

設(shè)Xi為人工魚i的當(dāng)前狀態(tài)，nf表示人工魚數(shù)，Xc表示魚群的中心位置，若Xc/nf>δXi，表示人工魚的數(shù)量少，且在魚群中心位置有豐富的食物，此時(shí)由式6繼續(xù)更新人工魚的狀態(tài)。若不滿足Xc/nf>δXi，重新進(jìn)行覓食行為。

(6)

(3)追尾行為[13]。

設(shè)人工魚i的當(dāng)前狀態(tài)為Xi，在魚群搜索范圍內(nèi)(dijδXi時(shí)，Xj為最優(yōu)狀態(tài)，此時(shí)說(shuō)明Xj方向食物充足，則人工魚i向伙伴Xj方向前進(jìn)一步；否則執(zhí)行覓食行為。

(4)隨機(jī)行為。

根據(jù)人工魚的當(dāng)前狀態(tài)Xi，在其視野范圍Visual內(nèi)隨機(jī)選取一個(gè)狀態(tài)，如式7所示。

(7)

(5)公告板。

人工魚的狀態(tài)信息記錄在公告板中。當(dāng)完成上述行為后，對(duì)比此時(shí)狀態(tài)和公告板中記錄的狀態(tài)。若當(dāng)前狀態(tài)比公告板中的狀態(tài)好，則更新公告板，反之保持不變。

2 距離加權(quán)質(zhì)心定位算法

質(zhì)心定位算法是一種基于網(wǎng)絡(luò)連通性的定位算法。其中心思想為：利用待測(cè)節(jié)點(diǎn)通信范圍內(nèi)的鄰居錨節(jié)點(diǎn)進(jìn)行位置估算，將所有錨節(jié)點(diǎn)分布位置連成一多邊形，求出多邊形質(zhì)心作為待測(cè)節(jié)點(diǎn)的位置。由于質(zhì)心算法中各個(gè)錨節(jié)點(diǎn)廣播的信息存在誤差，每個(gè)錨節(jié)點(diǎn)對(duì)待測(cè)節(jié)點(diǎn)影響程度也不同，特別當(dāng)錨節(jié)點(diǎn)密度過低時(shí)甚至?xí)霈F(xiàn)無(wú)法定位的現(xiàn)象。針對(duì)這一缺點(diǎn)，可以通過加權(quán)因子體現(xiàn)各錨節(jié)點(diǎn)對(duì)質(zhì)心位置的影響程度[14]，反映它們的內(nèi)在關(guān)系。

(8)

由于傳統(tǒng)的三邊定位法在復(fù)雜的環(huán)境因素下定位精度不高，因此提出一種改進(jìn)的加權(quán)質(zhì)心方法以提高定位精度。將三邊定位法求出的質(zhì)心點(diǎn)通過改進(jìn)的人工魚群算法進(jìn)行迭代更新，直至得到最優(yōu)解。

3 人工魚群質(zhì)心定位算法

(9)

對(duì)于與待定位節(jié)點(diǎn)相關(guān)的n個(gè)錨節(jié)點(diǎn)，誤差函數(shù)表示如下：

(10)

由于不同距離測(cè)距誤差不同，所以對(duì)不同的錨節(jié)點(diǎn)進(jìn)行加權(quán)，對(duì)距離較遠(yuǎn)的用較小權(quán)值，對(duì)距離較近的用較大權(quán)值。所以，通過待定位節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離的倒數(shù)作為對(duì)誤差函數(shù)的加權(quán)系數(shù)來(lái)構(gòu)造人工魚群算法的適應(yīng)度函數(shù)。

(11)

通過人工魚群算法對(duì)加權(quán)質(zhì)心算法進(jìn)行優(yōu)化，記錄未知節(jié)點(diǎn)與錨節(jié)點(diǎn)估計(jì)距離，與實(shí)際距離相比較，尋找誤差最小值，從而估算未知節(jié)點(diǎn)的位置。文中的算法的流程如下：

(12)

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

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

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

Step5：判斷是否滿足結(jié)束條件，如果滿足則返回Step4，公告板值即最優(yōu)值。

4 仿真實(shí)驗(yàn)與分析

4.1 仿真環(huán)境與參數(shù)

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

(13)

4.2 結(jié)果分析

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

圖1 不同錨節(jié)點(diǎn)密度的定位誤差曲線

圖2為平均定位誤差隨總節(jié)點(diǎn)個(gè)數(shù)的變化曲線。仿真時(shí)保持錨節(jié)點(diǎn)密度為20%不變，節(jié)點(diǎn)通信半徑為30 m。仿真結(jié)果表明，魚群質(zhì)心算法的定位精度隨總節(jié)點(diǎn)數(shù)的增加而提高，且明顯優(yōu)于其他兩種算法。

圖2 不同總節(jié)點(diǎn)數(shù)的定位誤差曲線

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

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

5 結(jié)束語(yǔ)

文中提出的改進(jìn)算法是在加權(quán)質(zhì)心算法的基礎(chǔ)上，引入人工魚群智能算法。利用人工魚群算法穩(wěn)定性好、全局尋優(yōu)能力強(qiáng)的特點(diǎn)，減少質(zhì)心定位算法中三邊測(cè)量法帶來(lái)的誤差。該算法不可避免地增加了少量

的計(jì)算開銷，但與傳統(tǒng)質(zhì)心算法和加權(quán)質(zhì)心算法的對(duì)比表明，該算法具有更高的定位精度。

參考文獻(xiàn)：

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

[2] 王福豹，史 龍，任豐原．無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J]．軟件學(xué)報(bào)，2005，16(5):857-868．

[3] 陳節(jié)節(jié).無(wú)線傳感器網(wǎng)絡(luò)三邊測(cè)量法研究概述[J].硅谷,2010(24):7.

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

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

[6] 陳星舟，廖明宏，林建華.基于粒子群優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位改進(jìn)[J].計(jì)算機(jī)應(yīng)用,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] 張先超，劉興長(zhǎng)，張春園．基于次錨節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)改進(jìn)加權(quán)質(zhì)心定位算法[J]．傳感器與微系統(tǒng)，2015，34(2)：143-146．

[10] 江銘炎，袁東風(fēng)．人工魚群算法及其應(yīng)用[M]．北京：科學(xué)出版社，2012.

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

[11] 黃 仁，秦占明．基于人工魚群算法的無(wú)線室內(nèi)定位優(yōu)化[J]．計(jì)算機(jī)應(yīng)用，2015，35：14-17．

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

[13] 李凌燕,杜永貴.改進(jìn)型粒子群優(yōu)化在WSNs節(jié)點(diǎn)定位中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2014,31(4):69-72.

[14] 朱 博，陳 曙．一種無(wú)線傳感器網(wǎng)絡(luò)質(zhì)心定位改進(jìn)算法[J]．傳感技術(shù)學(xué)報(bào)，2010，23(6)：868-872.