汪 晨，張玲華

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

0 引 言

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

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

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

1 人工魚群算法

1.1 基本思想

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

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

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

1.2 人工魚的基本行為描述

(1)覓食行為。

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

Xj=Xi+Visual*Rand()

(3)

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

(4)

(5)

(2)聚群行為。

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

(6)

(3)追尾行為[13]。

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

(4)隨機行為。

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

(7)

(5)公告板。

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

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

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

(8)

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

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

(9)

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

(10)

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

(11)

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

(12)

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

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

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

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

4 仿真實驗與分析

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

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

(13)

4.2 結(jié)果分析

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

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

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

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

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

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

5 結(jié)束語

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

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

參考文獻：

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

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

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

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

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

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

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

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

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

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

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

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