蟻群算法在WSN節點定位算法中的應用*

俞志根 , 姚春風

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

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

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

1 蟻群算法及其特點

1.1 蟻群算法的演進

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

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

(1)

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

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

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

(2)

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

(3)

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

1.1.2 蟻群系統 1996年，Dorigo和Gambardella又對螞蟻系統作了進一步改進，形成了較為成熟的蟻群系統[5]。提出了狀態轉移規則、全局更新規則和局部信息素更新規則，使其在進行優化時更為合理。

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

(4)

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

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

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

(5)

(6)

(5)式中的α是一個根據蟻群系統特征給定的常數；(6)式中的Lgb是全局最優解的路徑長度。

局部信息素更新規則是指在蟻群系統中，人工螞蟻在構造路徑的同時進行局部更新的規劃，數學模型如(7)式：

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

(7)

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

1.2 蟻群算法的特點及應用

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

蟻群算法可應用于靜態組合優化問題中的二次分配問題、車間任務調度問題、車輛路線問題[6]及動態組合優化中的有向連接網絡和無連接網絡系統路由問題，也可應用于求解連續空間優化問題，還可應用在管線敷設問題及機構同構判定問題等許多需要優化計算的場合。

2 用蟻群算法優化WSN節點定位算法的原理分析

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

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

3.1 移動信標發射位置、數量和坐標的計算

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

當只考慮一重覆蓋ROI(感興趣區域)時，需要信標節點的發射位置數量由(8)式計算：

(8)

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

(9)

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

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

第二步，信標節點發射位置坐標的計算，由(12)式計算奇數行的發射位置橫坐標，(13)計算偶數行的發射位置橫坐標，由(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 蟻群算法對移動信標移動路徑的優化

在得到了ROI中的移動信標發射位置和數量后，最重要的問題是如何使移動信標的移動路徑最合理高效，為此，可引入蟻群算法對移動路徑進行最優化，以獲得最佳移動路徑。可采用蟻群算法中的TSP問題求解方法，將WSN中的移動信標節點當成是TSP問題中的城市，進行旅行路徑優化，算法流程為：

第一步：系統初始化

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

第二：最佳路徑的求解

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

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

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

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

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

第三步 全局更新

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

{

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

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

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

}

第四步 輸出最優解

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

否則 返回最優解；

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

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

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

3.1 仿真參數設定

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

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

3.2 仿真結果分析

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

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

圖1 算法結束時節點實際位置與估計位置示意圖 圖2 定位誤差及其標準差與迭代次數的關系

4 結 語

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

參考文獻：

[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] 馬 良,項培軍.螞蟻算法在組合優化中的應用[J].管理科學學報,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] 侯立文,蔣馥.一種基于螞蟻算法的交通分配方法及其應用[J].上海交通大學學報,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的無線傳感器網絡定位技術研究及應用[D].長沙:湖南大學出版社,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] 李石堅,徐從富,楊旸,等.面向傳感器節點定位的移動信標路徑獲取[J].軟件學報,2008,19(2):455-467.