汪 晨,張玲華
(1.南京郵電大學(xué) 通信與信息工程學(xué)院,江蘇 南京 210003; 2.江蘇省通信與網(wǎng)絡(luò)技術(shù)工程研究中心,江蘇 南京 210003)
無(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)化以獲得更好的定位精度。
人工魚群算法是一種新型的智能優(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)覓食行為。
設(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 (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)好,則更新公告板,反之保持不變。 質(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)解。 (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)值。 在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) 在總節(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 不同半徑的定位誤差曲線 文中提出的改進(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.2 距離加權(quán)質(zhì)心定位算法
3 人工魚群質(zhì)心定位算法
4 仿真實(shí)驗(yàn)與分析
4.1 仿真環(huán)境與參數(shù)
4.2 結(jié)果分析
5 結(jié)束語(yǔ)