俞志根 , 姚春風(fēng)

(1.湖州職業(yè)技術(shù)學(xué)院 機電工程分院, 浙江 湖州 313000； 2.湖州市公安局 信息通訊處, 浙江 湖州 313000)

WSN(無線傳感器網(wǎng)絡(luò))[1]技術(shù)是21世紀最為核心的先進技術(shù)之一，必將影響到人們生活的方方面面。目前它已經(jīng)進入應(yīng)用研究階段，在應(yīng)用中有待突破的關(guān)鍵技術(shù)有節(jié)點定位技術(shù)、節(jié)點資源管理及網(wǎng)絡(luò)安全技術(shù)等，而節(jié)點定位問題是WSN應(yīng)用中需要解決的一個最基本的問題，是近年來的研究熱點。雖然，可用GPS全球定位系統(tǒng)進行節(jié)點定位，但由于GPS只適用于室外，且成本較高，對于室內(nèi)的小型WSN自組網(wǎng)還是不適用的，而WSN正是大量的這種室內(nèi)小型自組網(wǎng)，故大多數(shù)情況下用GPS進行節(jié)點定位并不適合。現(xiàn)在，WSN節(jié)點定位技術(shù)主要有基于測距的定位技術(shù)和無需測距的定位技術(shù)兩大類。前者如三邊測量法、三角測量法或最大似然估計法等；后者有質(zhì)心法、凸規(guī)劃算法、APIT算法等[2]，但定位精度都不高，相對定位誤差很難達到±40 %以上。

本文基于三邊測量定位技術(shù)[3]，在移動信標節(jié)點的移動路徑優(yōu)化上引入了蟻群算法，以獲得一條沿發(fā)射位置移動的最佳路徑。移動信標節(jié)點沿這一最佳路徑移動時能使信標節(jié)點起到最好的無線信號發(fā)射效果，產(chǎn)生最大覆蓋范圍，讓普通節(jié)點能更好地接收定位信號，獲得與信標節(jié)點的距離參數(shù)，然后再由三邊測量定位法等數(shù)學(xué)方法得到普通節(jié)點的空間位置，實現(xiàn)WSN節(jié)點的定位。由于用蟻群算法優(yōu)化了移動路徑，不僅減少了信標節(jié)點的數(shù)量，降低了節(jié)點能耗，而且大大提高了節(jié)點定位的精度，迭代次數(shù)70次時的相對定位誤差就能達到10 %左右。

1 蟻群算法及其特點

1.1 蟻群算法的演進

1.1.1 螞蟻系統(tǒng) 蟻群算法[4]最初是由意大利學(xué)者M.Dorigo于1991年提出的，是一種基于螞蟻覓食習(xí)慣的新型優(yōu)化算法，它引入人工螞蟻的概念，利用信息素對行動路徑進行最優(yōu)控制。蟻群在尋找食物時依靠相互之間信息素的傳遞，實現(xiàn)了所有螞蟻都走最短的路徑到達目標地，其核心是最優(yōu)路徑的選擇問題。后由意大利學(xué)者M.Dorigo、V.Maniezzo和A.Colomi進行深入研究，提出了基于螞蟻覓食行為的優(yōu)化算法，也稱為第一代蟻群算法(螞蟻系統(tǒng))，主要有以下幾個重要概念：

(1)轉(zhuǎn)換概率。螞蟻系統(tǒng)是一種概率尋優(yōu)方法，螞蟻通過留在路徑上的信息素濃度，利用轉(zhuǎn)換概率的高低來確定下一個路徑方向的選擇。轉(zhuǎn)換概率由下式表示：

(1)

式中：τij(t)是路徑節(jié)點i、j在時間t的信息素濃度，η(i,j)為期望值，是節(jié)點i、j間距的倒數(shù)，Jk(i)是節(jié)點i處的螞蟻k沒有訪問過的臨近節(jié)點的集合，α、β為兩個系數(shù)，用以決定信息素濃度與距離間的相對重要性。

(2)信息素蒸發(fā)率。與蟻群覓食相似，蟻群留在地上的信息素具有揮發(fā)性，會越來越少。人工螞蟻系統(tǒng)為了防止信息素的局部積聚，需要它不斷地蒸發(fā)，以促使人工螞蟻探索各種可能的路徑。另外，是為了讓人工螞蟻對曾經(jīng)取得的可行解經(jīng)過設(shè)定時間后能及時遺忘，有利于獲得新的更好的求解。當(dāng)然，信息素蒸發(fā)太快將不利于獲得求解經(jīng)驗，不利于人工螞蟻系統(tǒng)的求解效率，因此，在人工螞蟻系統(tǒng)中要設(shè)置適當(dāng)?shù)男畔⑺卣舭l(fā)率。

(3)節(jié)點信息素的更新。螞蟻會在自己路過的地方留下一定的信息素，留有信息素的路徑稱為信息素路徑，以與沒有螞蟻路過或信息素已經(jīng)揮發(fā)的路徑作出區(qū)分。人工螞蟻系統(tǒng)需要對各個節(jié)點的信息素進行不斷更新，以保持其尋優(yōu)能力，各個節(jié)點信息素的更新公式為：

(2)

其中：τij(t+i)與τij(t)是節(jié)點i與j節(jié)點在時間t及t+1時的信息素濃度。

(3)

其中:Lk為螞蟻k所走過路徑L的總長度，Q為0到1之間的一個隨機值，ρ為信息素蒸發(fā)系數(shù)，0<ρ<1。

1.1.2 蟻群系統(tǒng) 1996年，Dorigo和Gambardella又對螞蟻系統(tǒng)作了進一步改進，形成了較為成熟的蟻群系統(tǒng)[5]。提出了狀態(tài)轉(zhuǎn)移規(guī)則、全局更新規(guī)則和局部信息素更新規(guī)則，使其在進行優(yōu)化時更為合理。

在原螞蟻系統(tǒng)中，人工螞蟻采用隨機比例規(guī)則，完全依靠轉(zhuǎn)換概率來選擇路徑。而在蟻群系統(tǒng)中，人工螞蟻依據(jù)狀態(tài)轉(zhuǎn)移規(guī)則，采取偽隨機比例規(guī)則。這一決策規(guī)則具有雙重功能：可以利用先驗知識，也可以進行有傾向性的探索。狀態(tài)轉(zhuǎn)移規(guī)則的數(shù)學(xué)模型如下：

(4)

上式中：q和q0是[0-1]之間的隨機取值參數(shù)；J為屬于Jk(i)的某一節(jié)點，選擇方式是由基于AS的轉(zhuǎn)換概率隨機選取的。

蟻群系統(tǒng)與原來的人工螞蟻系統(tǒng)在全局更新上也有不同，原人工螞蟻系統(tǒng)的全局更新規(guī)則每次會對所有人工螞蟻都進行更新，因此，最優(yōu)解的搜索效率較低。為了使人工螞蟻的搜索行為很快集中到最優(yōu)路徑上來，新的蟻群系統(tǒng)全局更新規(guī)則規(guī)定每次循環(huán)后只對最優(yōu)路徑的信息素進行增強，這就使人工螞蟻的搜索行為能夠較快地集中到最優(yōu)路徑附近，從而提高蟻群算法的效率。蟻群算法的全局更新規(guī)則如(5)和(6)式：

τ(i,j)=(1-α)τ(i,j)+αΔτ(i,j)

(5)

(6)

(5)式中的α是一個根據(jù)蟻群系統(tǒng)特征給定的常數(shù)；(6)式中的Lgb是全局最優(yōu)解的路徑長度。

局部信息素更新規(guī)則是指在蟻群系統(tǒng)中，人工螞蟻在構(gòu)造路徑的同時進行局部更新的規(guī)劃，數(shù)學(xué)模型如(7)式：

τ(i,j)=(1-ρ)τ(i,j)+vτ0

(7)

(7)式中ρ是信息素的揮發(fā)系數(shù)，τ0是蟻群的實際信息素濃度，τ0=(NLnn)-1，N為系統(tǒng)節(jié)點總數(shù)，Lnn為求解的總路徑距離。

1.2 蟻群算法的特點及應(yīng)用

蟻群算法主要有以下幾方面的特點：一是具有較強的魯棒性。可應(yīng)用于靜態(tài)、動態(tài)等各種最佳路徑的優(yōu)化問題，且只需稍作修改，就可用于各種優(yōu)化算法；二是能夠進行分布式計算。因它是一種基于種群的進化算法，具有本質(zhì)并行性，故能進行分布式計算；三是具有較強的融合性。蟻群算法很容易與其它各種啟發(fā)式算法相融合，進一步提高算法的各種性能；四是蟻群算法具有很強的優(yōu)化能力。因為算法中的正反饋原理有利于加快進化過程，且它是一種本質(zhì)并行算法，不同個體之間不斷進行信息交流和傳遞，因此，能更快地得到優(yōu)化結(jié)果。

蟻群算法可應(yīng)用于靜態(tài)組合優(yōu)化問題中的二次分配問題、車間任務(wù)調(diào)度問題、車輛路線問題[6]及動態(tài)組合優(yōu)化中的有向連接網(wǎng)絡(luò)和無連接網(wǎng)絡(luò)系統(tǒng)路由問題，也可應(yīng)用于求解連續(xù)空間優(yōu)化問題，還可應(yīng)用在管線敷設(shè)問題及機構(gòu)同構(gòu)判定問題等許多需要優(yōu)化計算的場合。

2 用蟻群算法優(yōu)化WSN節(jié)點定位算法的原理分析

WSN節(jié)點定位方法可分為基于測距和無需測距兩大類[7]。前一種方法定位精度較高，但實現(xiàn)起來較復(fù)雜，成本較高，后一種反之。為了得到較高的定位精度，本文以第一類定位方法為基礎(chǔ)研究引入蟻群優(yōu)化算法，以進一步提高定位精度。

在基于測距的定位方法中，WSN中的節(jié)點分為普通節(jié)點和信標節(jié)點兩類，一般可通過接收信號強度(RSSI)[8]測量普通節(jié)點到信標節(jié)點的距離或角度信息，再用三邊測量法就可對普通節(jié)點進行定位[9]。信標節(jié)點的數(shù)量和布置對這種定位方法的定位精度有很大的影響，雖然，采用較多的信標節(jié)點能提高網(wǎng)絡(luò)節(jié)點的定位精度，但會使成本上升。因此，本文根據(jù)文獻[10]提出的基于移動信標進行節(jié)點定位的思想，為了得到信標節(jié)點的最佳移動路徑，提出用三重優(yōu)化覆蓋的方法來選取最少的發(fā)射位置，并引入蟻群算法對信標移動路徑進行優(yōu)化，以獲取最佳移動路徑，從而實現(xiàn)WSN信標節(jié)點的數(shù)量和移動路徑的最佳優(yōu)化，以提高普通節(jié)點的定位精度。

3.1 移動信標發(fā)射位置、數(shù)量和坐標的計算

移動信標的發(fā)射位置、數(shù)量和坐標的計算可采用三邊測量法并結(jié)合三重覆蓋法進行，文獻[11][12]對此進行了詳細研究，算法模型和步驟如下：

當(dāng)只考慮一重覆蓋ROI(感興趣區(qū)域)時，需要信標節(jié)點的發(fā)射位置數(shù)量由(8)式計算：

(8)

采用等距三重優(yōu)化覆蓋時由(9)式計算：

(9)

一般ROI形狀為矩形，故可由ROI的各頂點坐標得到信標發(fā)射位置坐標，計算步驟是：

第一步，信標節(jié)點發(fā)射位置數(shù)量的計算，由(10)式計算每行中信標節(jié)點發(fā)射位置的數(shù)量，由(11)計算所需的信標節(jié)點行數(shù)，總數(shù)為兩者的乘積；

第二步，信標節(jié)點發(fā)射位置坐標的計算，由(12)式計算奇數(shù)行的發(fā)射位置橫坐標，(13)計算偶數(shù)行的發(fā)射位置橫坐標，由(14)式計算縱坐標。

NodeNum_Line=A/r

(10)

(11)

Xij=(j-1)r

(12)

Xij=A-(J-1)r

(13)

(14)

式中A為ROI的長度，B為其寬，r為信號有效半徑，i為行號，j列號。

3.2 蟻群算法對移動信標移動路徑的優(yōu)化

在得到了ROI中的移動信標發(fā)射位置和數(shù)量后，最重要的問題是如何使移動信標的移動路徑最合理高效，為此，可引入蟻群算法對移動路徑進行最優(yōu)化，以獲得最佳移動路徑?？刹捎孟伻核惴ㄖ械腡SP問題求解方法，將WSN中的移動信標節(jié)點當(dāng)成是TSP問題中的城市，進行旅行路徑優(yōu)化，算法流程為：

第一步：系統(tǒng)初始化

設(shè)NC=0；設(shè)置路徑(r，s)的信息素濃度初值：τ(r，s)=τ0，Δτ(r，s)=0；m只螞蟻在n個信標節(jié)點上隨機布置，禁忌表置空：tabuk=φ；

第二：最佳路徑的求解

二是真抓實干，求真務(wù)實。一抓經(jīng)營模式，鞏固農(nóng)資經(jīng)營基礎(chǔ)。二抓項目建設(shè)，增強企業(yè)發(fā)展動力。三抓融資渠道，增加資金供給規(guī)模。四抓應(yīng)收賬款，保障資金運行安全。五抓風(fēng)險防控，堅守安全發(fā)展底線。要加強風(fēng)險管控，在集團管控上要創(chuàng)新管理模式，規(guī)范管理行為。在基礎(chǔ)管理上要照章辦事，認真貫徹落實。在風(fēng)險管理上要做到準確識別、科學(xué)研判、有效控制風(fēng)險。在全面預(yù)算管理上要做到“先算后花，先算后干，過程監(jiān)控，結(jié)果考核”，提高企業(yè)運行的質(zhì)量。

for(i=1；i≤n；i++)

for(k=l；k≤m；k++){

將螞蟻k所在的初始傳感節(jié)點添加到tabuk中；

If(k未完成指定任務(wù)且tabuk未滿)

第三步 全局更新

for(k=l；k≤m；k++)

{

If(N次迭代最優(yōu)解無明顯改進)

{按式(4)更新ρ值；}

按式(5)、(6)對最優(yōu)路徑進行全局更新；

}

第四步 輸出最優(yōu)解

If(不滿足終止條件){清空所有k的禁忌表；對每條路徑(r，s)，置Δτ(r，s)=0；且Nc=Nc+l；返回第二步；}

否則 返回最優(yōu)解；

通過這一算法就可得到一條經(jīng)過優(yōu)化了的信標節(jié)點移動路徑，信標節(jié)點按照這條路徑移動到每一個信號發(fā)射點，普通節(jié)點通過RSSI技術(shù)測得與信標節(jié)點之間的距離，然后使用三邊測量定位法即可定位普通節(jié)點，這種新的WSN節(jié)點定位方法稱為基于蟻群算法的WSN節(jié)點定位方法。

3 基于蟻群算法的WSN節(jié)點定位仿真試驗

為了驗證以上的路徑優(yōu)化算法，本文建立了一個由200個節(jié)點組成的仿真WSN，先用等距三重優(yōu)化算法獲得移動信標發(fā)射位置的數(shù)量和坐標后，引入蟻群算法對移動路徑進行優(yōu)化，并將信標節(jié)點的移動路徑設(shè)定為經(jīng)優(yōu)化后的最優(yōu)路徑移動，最后，普通節(jié)點的位置由三邊測量算法獲得，仿真結(jié)果表明，信標節(jié)點沿經(jīng)蟻群算法優(yōu)化后的最佳路徑移動能提高普通節(jié)點的定位精度，使定位的相對誤差控制在15 %以內(nèi)。具體的仿真過程如下：

3.1 仿真參數(shù)設(shè)定

仿真試驗參數(shù)設(shè)定：WSN節(jié)點總數(shù)設(shè)為200個，均布在15×15的正方形網(wǎng)格區(qū)域內(nèi)；信標節(jié)點密度φ=12.5%，即信標節(jié)點數(shù)目Nanchor=25，普通節(jié)點數(shù)Nnon-anchor=175。節(jié)點隨機分布在規(guī)定區(qū)域內(nèi)；節(jié)點的通信半徑R=2.0，網(wǎng)絡(luò)連通度connectivity=12.2；另外，設(shè)定未知節(jié)點具有測量自身到鄰節(jié)點距離的能力，且測距無誤差；而且，所有節(jié)點在布撒之后均不作移動。

仿真工具用MATLAB9.0版軟件，在高配計算機(2G內(nèi)存，雙核PⅣ)上進行仿真運算，蟻群算法參數(shù)的取值如下：螞蟻數(shù)目K=10N，初始步長λ(0)=0.1；步長縮減系數(shù)ξ=0.96；信息素濃度設(shè)為τ0=0.15，揮發(fā)率設(shè)為ρ=0.618；迭代60次后將重新初始化信息素濃度。這些參數(shù)的設(shè)置還缺乏嚴格的理論依據(jù)，只能由經(jīng)驗取得。

3.2 仿真結(jié)果分析

具體的仿真結(jié)果如圖1，圖中的實心正方形表示信標節(jié)點，共有25個；空心圓表示普通節(jié)點的實際位置，共有170個；星形表示經(jīng)過蟻群算法優(yōu)化后得到的普通節(jié)點的計算位置。由圖可知，經(jīng)蟻群算法優(yōu)化后能比較準確地計算出大部分普通節(jié)點的位置，證明蟻群算法在WSN節(jié)點定位中能起到提高定位精確度的作用，是一種較有前途的定位算法新方法。

圖2是節(jié)點定位誤差及其標準差與算法迭代次數(shù)之間的關(guān)系曲線，由圖可知，在10次迭代次數(shù)以前，定位誤差及其標準差下降，說明這種優(yōu)化算法具有良好的收斂性。當(dāng)對定位精度要求不高時，可適當(dāng)減少迭代次數(shù)，以縮短算法運行時間。在前述仿真參數(shù)條件和機器配置下，算法運行時間在60分鐘以內(nèi)。如要獲得較高的定位精度，則需要較多的迭代次數(shù)，由圖可知，迭代次數(shù)60次時的相對定位誤差為10%，能滿足大多數(shù)WSN的定位要求。

圖1 算法結(jié)束時節(jié)點實際位置與估計位置示意圖 圖2 定位誤差及其標準差與迭代次數(shù)的關(guān)系

4 結(jié) 語

通過在WSN節(jié)點的三邊測量定位算法中引入蟻群算法，對移動信標節(jié)點的移動路徑進行優(yōu)化，建立了蟻群算法模型和流程。并在15×15的區(qū)域內(nèi)分布200個WSN節(jié)點的條件下進行了仿真試驗研究，結(jié)果表明這是一種更加有效的WSN節(jié)點定位算法，能使WSN節(jié)點定位相對誤差提高到10%以內(nèi)，具有良好的應(yīng)用前景。

參考文獻：

[1] Ren F.Wireless Sensor Networks[J].Journal of Software,2003,14,(7):1282-1291.

[2] Bulusu N. Heidemann J, Estrin D.GPS2 Less Low Cost Outdoor Localization for Very Small Devices[J].IEEE Personal Communications, 2000,7,(5):28-34.

[3] Niculescu D, Nath B.DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems, 2003,22,(l):267-268.

[4] 馬 良,項培軍.螞蟻算法在組合優(yōu)化中的應(yīng)用[J].管理科學(xué)學(xué)報,2001,4(2):32-36.

[5] Akyildiz I F, Su W, Sankarasubramaniam Y, et al.Wireless Sensor Network:A Survey[J].Computer Networks, 2003, 38(4):393-422.

[6] 侯立文,蔣馥.一種基于螞蟻算法的交通分配方法及其應(yīng)用[J].上海交通大學(xué)學(xué)報,2001,35,(6):486- 490.

[7] Wang FB, Shi L, Ren FY.Self-localization Systems and Algorithms for Wireless Sensor Networks[J].Journal of Software, 2005,16(5):857-868.

[8] 杜 敏.基于RSSI的無線傳感器網(wǎng)絡(luò)定位技術(shù)研究及應(yīng)用[D].長沙:湖南大學(xué)出版社,2009:23.

[9] Niculescu D, Nath B.Position and Orientation in Ad Hoe Networks[J].Ad Hoe Networks, 2004,2(2):133-151.

[10] Sichitiu ML, Ramadurai V.Localization of Wireless sensor Networks with a Mobile Beacon[A].In: Proc.Of the IEEE Int’l Conf. on Mobile Ad-hoe and Sensor Systems[C].IEEE Computer Society, 2004:174-183.

[11] Zhang HH, Hou JC.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks[J].Wireless Ad Hoe and Sensor Networks, 2005,l(1):89-93.

[12] 李石堅,徐從富,楊旸,等.面向傳感器節(jié)點定位的移動信標路徑獲取[J].軟件學(xué)報,2008,19(2):455-467.