樊寬剛，么曉康，蘇建華

(1.江西理工大學(xué) 機(jī)電工程學(xué)院，江西 贛州341000;2.中國(guó)科學(xué)院 自動(dòng)化研究所 復(fù)雜系統(tǒng)與智能科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100190)

0 引 言

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

本文根據(jù)上述節(jié)點(diǎn)部署不足之處，針對(duì)WSNs 節(jié)點(diǎn)在有障礙物二維地理環(huán)境中靜態(tài)位置優(yōu)化問題，在建立無線信道衰減模型基礎(chǔ)上，提出一種基于Dijkstra 算法和蟻群算法相結(jié)合的WSNs 節(jié)點(diǎn)靜態(tài)優(yōu)化部署策略。

1 工程背景

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

圖1 節(jié)點(diǎn)部署環(huán)境Fig 1 Environment of node deployment

2 無線信道能耗衰減模型

本文將按梯度層次場(chǎng)數(shù)據(jù)傳遞［8］引入WSNs，同時(shí)給出假設(shè):1)所有節(jié)點(diǎn)同構(gòu)，部署前有相同能量，部署后固定;2)節(jié)點(diǎn)有相同傳輸半徑;3)位置坐標(biāo)測(cè)量可得;4)節(jié)點(diǎn)采用多跳方式通信;5)采用等距布置。

Heinzelman W B 等人提出了無線信道能耗自由空間和多路徑衰減模型［9］?；诶碚摵蜏y(cè)試的無線信號(hào)傳播模型，信道平均接收信號(hào)功率隨距離變化呈對(duì)數(shù)衰減。對(duì)于任意發(fā)射機(jī)和接收機(jī)距離，平均大尺度路徑損耗［9］如公式(1)所示

式中 n 為路徑損耗指數(shù)，體現(xiàn)距離長(zhǎng)度對(duì)路徑損耗影響程度。建筑物內(nèi)視距傳播路徑損耗指數(shù)［10］n=1.6～1.8，數(shù)值計(jì)算取n=1.7，則

式中 ERec(k，d)，ETrd(k，d)為在收、發(fā)距離為d 時(shí)傳輸k比特?cái)?shù)據(jù)能耗，Eelec為一個(gè)比特?cái)?shù)據(jù)在無線傳感器節(jié)點(diǎn)中進(jìn)行信號(hào)數(shù)字編碼調(diào)制電子器件所消耗能量，εfx為距離衰減放大器系數(shù)，d0為收發(fā)能耗判斷閾值，表示為

式中 L 為無線傳輸損耗，hTrd，hRec為發(fā)送和接收天線高度，λ 為電磁波波長(zhǎng)。設(shè)Edata為一個(gè)節(jié)點(diǎn)融合單位比特需要能量，則經(jīng)過特定節(jié)點(diǎn)轉(zhuǎn)發(fā)融合m 個(gè)節(jié)點(diǎn)k 比特需要能量為

網(wǎng)絡(luò)節(jié)點(diǎn)總跳數(shù)Hsum－L和各個(gè)節(jié)點(diǎn)梯度層次數(shù)Li關(guān)系如下

其中，N 為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。由式(2)～式(5)得無線傳感節(jié)點(diǎn)信道能耗衰減兩個(gè)模型:

1)當(dāng)R≤d0時(shí)，不考慮數(shù)據(jù)融合，鏈上所有傳感器給簇首發(fā)送y 比特?cái)?shù)據(jù)能耗Ef

2)當(dāng)R≤d0時(shí)，考慮數(shù)據(jù)融合，一次傳感網(wǎng)內(nèi)完全融合壓縮所需能量E，式(7)中yh和yd分別為包頭、數(shù)據(jù)比特?cái)?shù)

3 WSNs 節(jié)點(diǎn)靜態(tài)部署策略

3.1 節(jié)點(diǎn)靜態(tài)部署策略實(shí)現(xiàn)步驟

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

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

3.2 基于蟻群算法的靜態(tài)WSNs 節(jié)點(diǎn)部署

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

1)評(píng)價(jià)函數(shù):線傳感節(jié)點(diǎn)在有礙環(huán)境中優(yōu)化部署，最終目標(biāo)是減少WSNs 通信能耗，實(shí)際為達(dá)到節(jié)點(diǎn)通信路徑最短，因此，選爬行路程長(zhǎng)度作為評(píng)價(jià)參數(shù)，建立評(píng)價(jià)函數(shù)為

式中 n 為總行走步數(shù)，ek螞蟻第k 步選擇節(jié)點(diǎn)，dekek+1為螞蟻?zhàn)哌^相鄰點(diǎn)間路徑長(zhǎng)度。

2)概率選擇策略:螞蟻選擇下一點(diǎn)采用偽隨機(jī)比例規(guī)則，則一只位于i 點(diǎn)螞蟻選擇下一個(gè)節(jié)點(diǎn)j 的選擇轉(zhuǎn)移規(guī)則如下

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

3)禁忌判斷規(guī)則禁忌向量實(shí)現(xiàn)，防止螞蟻重復(fù)過點(diǎn)。

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

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

圖3 ACO 算法節(jié)點(diǎn)路徑部署優(yōu)化流程圖Fig 3 Flow chart of node path deployment optimization based on ACO algorithm

4 仿真實(shí)驗(yàn)與分析

4.1 對(duì)于圖1(a)環(huán)境的仿真

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

表1 能耗模型參數(shù)值Tab 1 Parameters of energy consumption model

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

圖4 節(jié)點(diǎn)在狹長(zhǎng)空間中部署線路圖Fig 4 Path of node deployment in long and narrow space

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

表2 普通部署和ACO 算法優(yōu)化部署對(duì)比Tab 2 Contrast between common deployment and optimized deployment of ACO algorithm

4.2 對(duì)于圖1(b)環(huán)境節(jié)點(diǎn)部署仿真

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

圖6 Dijkstra 算法節(jié)點(diǎn)部署初步規(guī)劃線路Fig 6 Initial planning route of node deployment based on Dijkstra algorithm

圖7 基于Dijkstra-ACO 算法的節(jié)點(diǎn)部署線路圖Fig 7 Path graph of node deployment based on Dijkstra-ACO algorithm

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

5 結(jié) 論

本文主要研究WSNs 節(jié)點(diǎn)在有障礙物環(huán)境中優(yōu)化部署方案，提出了一種基于無線信道能耗衰減模型、蟻群算法和Dijkstra 算法的無線傳感節(jié)點(diǎn)在有障環(huán)境中具體優(yōu)化部署新方法。能很好實(shí)現(xiàn)節(jié)點(diǎn)部署線路規(guī)劃設(shè)計(jì)，達(dá)到了節(jié)約WSNs 能量目的。該方法具有較好的實(shí)踐應(yīng)用領(lǐng)域，可將兩種有障簡(jiǎn)化模型綜合應(yīng)用于礦井巷道、公路鐵路隧道、狹長(zhǎng)山谷、大型建筑物等的等水平無線傳感器節(jié)點(diǎn)部署優(yōu)化。

表3 Dijkstra 和Dijkstra-ACO 優(yōu)化部署結(jié)果對(duì)比Tab 3 Results contrast of optimized deployment by Dijkstra and Dijkstra-ACO algorithm

［1］ 王 雪，丁 梁，王 晟，等.層次分簇的無線傳感網(wǎng)絡(luò)多級(jí)優(yōu)化測(cè)量［J］.機(jī)械工程學(xué)報(bào)，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］ 周廣東，李愛群.大跨橋梁監(jiān)測(cè)無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)布置方法研究［J］.振動(dòng)工程學(xué)報(bào)，2011(4):405－411.

［5］ 吳 寅.采用環(huán)境能量的自供電WSNs 關(guān)鍵技術(shù)研究［D］.南京:南京航空航天大學(xué)，2013:2－10.

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

［7］ 肖德琴，王景利，羅錫文.大規(guī)模農(nóng)田傳感器網(wǎng)絡(luò)通信能耗模型［J］.計(jì)算機(jī)科學(xué)，2009(8):75－78.

［8］ 朱紅松，孫利民，徐勇軍，等.基于精細(xì)化梯度的WSNs 匯聚機(jī)制及分析［J］.軟件學(xué)報(bào)，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］拉帕波特.無線通信原理與應(yīng)用［M］.北京:電子工業(yè)出版社，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］樊平毅.網(wǎng)絡(luò)信息論［M］.北京:清華大學(xué)出版社，2009:48－50.

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