基于蟻群算法的WSNs 節點有障環境中部署優化研究*

樊寬剛，么曉康，蘇建華

(1.江西理工大學 機電工程學院，江西 贛州341000;2.中國科學院 自動化研究所 復雜系統與智能科學國家重點實驗室，北京100190)

0 引 言

如何有效利用能量是無線傳感器網絡(wireless sensor networks，WSNs)研究關鍵問題之一［1］。為節約節點能量，許多研究者針對WSNs 能耗展開研究。文獻［2］提出利用收集數據轉發路徑最短和有效數據時空相關感知收集算法。文獻［3］提出構建感知方向使網絡壽命最大化多項式時間算法和有效延長網絡壽命圓周生成算法。文獻［4］提出基于數據獲取效率為評價網絡標準的橋梁監測WSNs 節點布置方法。文獻［5］設計自供電低功耗無線傳感器節點并提出均勻分簇自適應路由協議。文獻［6］提出基于網格和虛擬力導向蟻群算法高效路由策略。文獻［7］提出在農田傳感網絡中計算無線節點最佳傳輸半徑計算方法。上述文獻主要研究WSNs 路由算法，能量控制策略或自供電等來實現無線節點能量供給優化。但上述沒有具體研究WSNs 節點有障礙物情況下節點靜態部署問題。

本文根據上述節點部署不足之處，針對WSNs 節點在有障礙物二維地理環境中靜態位置優化問題，在建立無線信道衰減模型基礎上，提出一種基于Dijkstra 算法和蟻群算法相結合的WSNs 節點靜態優化部署策略。

1 工程背景

根據部署無線傳感節點實際環境，本文提出兩種有障礙部署環境。一種是狹長彎曲空間(圖1(a))，一種是障礙物塊狀分散構成空間(圖1(b))，圖1(a)有障環境主要解決節點部署位置是近似共面狹長空間節點部署優化問題，如礦井巷道、隧道以及高樓林立彎曲街道等。圖1(b)有障環境主要為解決節點部署位置平面上阻擋物為不連續塊狀空間節點部署優化問題，如多棟散狀分布高樓、礦井工作面巷道復雜多交叉處等。

圖1 節點部署環境Fig 1 Environment of node deployment

2 無線信道能耗衰減模型

本文將按梯度層次場數據傳遞［8］引入WSNs，同時給出假設:1)所有節點同構，部署前有相同能量，部署后固定;2)節點有相同傳輸半徑;3)位置坐標測量可得;4)節點采用多跳方式通信;5)采用等距布置。

Heinzelman W B 等人提出了無線信道能耗自由空間和多路徑衰減模型［9］。基于理論和測試的無線信號傳播模型，信道平均接收信號功率隨距離變化呈對數衰減。對于任意發射機和接收機距離，平均大尺度路徑損耗［9］如公式(1)所示

式中 n 為路徑損耗指數，體現距離長度對路徑損耗影響程度。建筑物內視距傳播路徑損耗指數［10］n=1.6～1.8，數值計算取n=1.7，則

式中 ERec(k，d)，ETrd(k，d)為在收、發距離為d 時傳輸k比特數據能耗，Eelec為一個比特數據在無線傳感器節點中進行信號數字編碼調制電子器件所消耗能量，εfx為距離衰減放大器系數，d0為收發能耗判斷閾值，表示為

式中 L 為無線傳輸損耗，hTrd，hRec為發送和接收天線高度，λ 為電磁波波長。設Edata為一個節點融合單位比特需要能量，則經過特定節點轉發融合m 個節點k 比特需要能量為

網絡節點總跳數Hsum－L和各個節點梯度層次數Li關系如下

其中，N 為網絡節點數。由式(2)～式(5)得無線傳感節點信道能耗衰減兩個模型:

1)當R≤d0時，不考慮數據融合，鏈上所有傳感器給簇首發送y 比特數據能耗Ef

2)當R≤d0時，考慮數據融合，一次傳感網內完全融合壓縮所需能量E，式(7)中yh和yd分別為包頭、數據比特數

3 WSNs 節點靜態部署策略

3.1 節點靜態部署策略實現步驟

1)對WSNs 節點部署環境簡化拆分。2)部署環境平面圖，建立相應信道衰減模型。3)利用無線信道衰減模型確定傳輸半徑。4)對類似圖1 節點部署環境，進行相鄰線段可視分割(如圖2(a))和MAKLINK 圖形［11］分割(如圖2(b))，運用蟻群算法和Dijkstra 算法［12］進行仿真計算。5)分析仿真結果，確定節點個數，進行節點實際部署。

圖2 圖形分割方法Fig 2 Partition method of figure

3.2 基于蟻群算法的靜態WSNs 節點部署

本文選用屬于蟻群優化(ant colony optimization，ACO)算法的蟻周系統［13］。

1)評價函數:線傳感節點在有礙環境中優化部署，最終目標是減少WSNs 通信能耗，實際為達到節點通信路徑最短，因此，選爬行路程長度作為評價參數，建立評價函數為

式中 n 為總行走步數，ek螞蟻第k 步選擇節點，dekek+1為螞蟻走過相鄰點間路徑長度。

2)概率選擇策略:螞蟻選擇下一點采用偽隨機比例規則，則一只位于i 點螞蟻選擇下一個節點j 的選擇轉移規則如下

式中 allowedk為螞蟻k 下一步允許選擇點集合，α 和β 分別反映螞蟻爬行過程中所積累信息素和啟發信息相對重要性，τ(i，u)為邊(i，u)上信息素強度，η(i，u)為邊(i，u)能見度，q 為［0，1］區間均勻分布隨機數，q0為參數(0≤q0≤1)，J 為根據方程式(9)給出概率分布選出一個隨機變量，)為螞蟻k 轉移概率，j 為未經過節點。

3)禁忌判斷規則禁忌向量實現，防止螞蟻重復過點。

4)信息素更新策略:在蟻周系統中，信息素更新公式(11)給出

式中 Δτij(t+n)為在時刻(t，t+n)的循環中路徑(i，j)的信息素的增量，ρ 為信息素蒸發系數。算法流程如圖3。

圖3 ACO 算法節點路徑部署優化流程圖Fig 3 Flow chart of node path deployment optimization based on ACO algorithm

4 仿真實驗與分析

4.1 對于圖1(a)環境的仿真

部署環境中網絡相鄰節點之間距離l 最大35 m，頻段2.4 GHz，參數設置L=1，hTra=0.4 m，hRec=0.4 m，得d0=40.192 m。對式(6)和式(7)參數值如表1。坐標范圍162 m×162 m。傳感器節點坐標(7，16)m，簇首坐標(73，162)m。對圖進行相鄰線段可視分割并對圖每個線段進行最小0.25 m 分割，獲取分割點坐標。生成具有禁忌作用距離權值矩陣，用Matlab 編寫程序。蟻群算法參數設置:α=1，β=2，ρ=0.3，Q=30，k=100，m=30，q0=0.85。

表1 能耗模型參數值Tab 1 Parameters of energy consumption model

從圖4 中可得所提ACO 算法優化效果較好。從圖5 中可得基于蟻群算法收斂性良好，能很好解決這類問題。將中心線位置部署和蟻群算法優化部署進行比較，由表2，相比普通位置部署，蟻群算法優化后，在傳輸能耗上節約18.23%。

圖4 節點在狹長空間中部署線路圖Fig 4 Path of node deployment in long and narrow space

圖5 蟻群算法平均路線長度收斂曲線Fig 5 Convergence curve of average path length of ACO algorithm

表2 普通部署和ACO 算法優化部署對比Tab 2 Contrast between common deployment and optimized deployment of ACO algorithm

4.2 對于圖1(b)環境節點部署仿真

仿真坐標范圍為165 m×165 m。傳感器節點坐標(155.5，7)m，簇首坐標(11.5，148)m。對有障礙物空間進行MAKLINK 圖論方法分割。使用Dijkstra 算法在可行性路徑基礎上再次優化WSNs 節點部署位置線路圖(如圖6)。使用蟻群算法在Dijkstra 優化基礎上更進一步優化蟻群算法，參數設置:α=1，β=5，ρ=0.3，Q=30，k=300，m=30，q0=0.88。通過仿真計算求得Dijkstra 算法解為226.12 m，通過蟻群算法得評價函數的解w=213.881 3 m。從圖7 可以看出優化結果更好，圖8 表明此算法收斂性良好。從表3 中可以看出:Dijkstra 與蟻群算法結合比直接使用Dijkstra 算法在路徑長度上有5.41%提高，在傳輸能耗上有0.32%節約。表2 和表3 說明通過此優化策略可以達到WSNs 節點的更好的部署，并達到節約能耗目的。

圖6 Dijkstra 算法節點部署初步規劃線路Fig 6 Initial planning route of node deployment based on Dijkstra algorithm

圖7 基于Dijkstra-ACO 算法的節點部署線路圖Fig 7 Path graph of node deployment based on Dijkstra-ACO algorithm

圖8 Dijkstra-ACO 算法平均路線長度收斂曲線Fig 8 Convergence curve of average path length based on Dijkstra-ACO algorithm

5 結 論

本文主要研究WSNs 節點在有障礙物環境中優化部署方案，提出了一種基于無線信道能耗衰減模型、蟻群算法和Dijkstra 算法的無線傳感節點在有障環境中具體優化部署新方法。能很好實現節點部署線路規劃設計，達到了節約WSNs 能量目的。該方法具有較好的實踐應用領域，可將兩種有障簡化模型綜合應用于礦井巷道、公路鐵路隧道、狹長山谷、大型建筑物等的等水平無線傳感器節點部署優化。

表3 Dijkstra 和Dijkstra-ACO 優化部署結果對比Tab 3 Results contrast of optimized deployment by Dijkstra and Dijkstra-ACO algorithm

［1］ 王 雪，丁 梁，王 晟，等.層次分簇的無線傳感網絡多級優化測量［J］.機械工程學報，2009(4):1－7.

［2］ Villas L A，Boukerche A，GuidoniD L，et al.An energy－aware spatio－temporal correlation mechanism to perform efficient data collection in wireless sensor networks［J］.Computer Communications，2013，36:1054－1066.

［3］ André Rossi，Alok Singh，Marc Sevaux.Lifetime maximization in wireless directional sensor network［J］.European Journal of Operational Research，2013，231:229－241.

［4］ 周廣東，李愛群.大跨橋梁監測無線傳感網絡節點布置方法研究［J］.振動工程學報，2011(4):405－411.

［5］ 吳 寅.采用環境能量的自供電WSNs 關鍵技術研究［D］.南京:南京航空航天大學，2013:2－10.

［6］ 朱紹文，紀志成，王 艷，等.基于Grid－VFACO 的數字化車間WSNs 路由算法［J］.傳感器與微系統，2014，33(1):134－136.

［7］ 肖德琴，王景利，羅錫文.大規模農田傳感器網絡通信能耗模型［J］.計算機科學，2009(8):75－78.

［8］ 朱紅松，孫利民，徐勇軍，等.基于精細化梯度的WSNs 匯聚機制及分析［J］.軟件學報，2007(5):1138－1151.

［9］ Heinzelman W B，Chandrakasan Anantha P，Balakrishnan Hari.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

［10］拉帕波特.無線通信原理與應用［M］.北京:電子工業出版社，2012:95－113.

［11］Tan Guanzheng，He Huan，Sloman A.Ant colony system algorithm for real－time globally optimal path planning of mobile robot－s［J］.Acta Automatica Sinica，2007，33(3):279－285.

［12］樊平毅.網絡信息論［M］.北京:清華大學出版社，2009:48－50.

［13］Dorigo M，Maniezzo V，Colorni A.Positive feedback as a search strategy［R］.Italy:IRIDIA，Politecnico di Milano，1991.