基于混合雞群優化算法的WSN節點部署優化

韋修喜,鄭寶峰

(廣西民族大學 a.人工智能學院;b.電子信息學院,南寧 530006)

無線傳感網絡(WSN)是由一組輕量級、自主的空間分布節點組成,這些節點相互協調,形成一個感知特定應用任務的通信網絡［1］,具有成本低,適應度高等特點.隨著科技的不斷發展,科學家對于WSN的研究也越來越多,并已經應用到許多領域,如:路徑調度目標跟蹤、災難預警和可穿戴設備［2］等.其中WSN的覆蓋率問題是關鍵問題也是難點之一,覆蓋率的大小反映了WSN網絡的性能以及效率的好壞.在傳統WSN網絡中,傳感器的部署位置大多是采用隨機拋撒進行決定的,通過這種方法部署的網絡容易出現節點分布不均的問題,使得一部分空間內的節點密度過高,從而導致網絡的覆蓋率降低,傳感速度和效率變差.而解決這一問題就需要對節點部署方法進行優化.

隨著群智能優化算法的出現,如:教與學優化算法(Teaching-learning-based Optimization,TLBO)［3］,麻雀搜索算法(Sparrow Search Algorithm,SSA)［4］,旗魚優化算法(Sail Fish Optimizer,SFO)［5］等.近年來,群智能優化算法的研究人員越來越多,由于這類優化算法對于解決尋優問題有著顯著的優點,許多國內外學者將群智能優化算法融到WSN節點部署優化中,如:MIAO等［6］等將增強層次結構的灰狼優化算法應用其中,DEEPA等［7］提出了利用Lévy飛行增強的鯨魚優化算法,并應用到WSN覆蓋優化中,并將KNN(K-Nearest Neighbor,KNN)變體整合到WSN中,得到了效率更高、收斂度更好的覆蓋優化方法.宋明智等［8］等提出了改進虛擬力-粒子群算法于WSN節點隨機部署中的應用,最終實驗表明其提出的方法覆蓋率較其他優化算法有3%～5%的提升.

雖然,將群智能優化算法運用到WSN節點部署優化中能使其覆蓋率有一定的提升,但使用基本算法所得到的結果仍然還有許多不足,故這些算法還有許多可以提升和改進的空間.為了獲得更好的WSN網絡性能,還需要進一步開拓群智能優化算法的能力,更好地改善WSN節點部署優化問題,提高覆蓋率.

雞群優化算法(Chicken Swarm Optimization,CSO),于2014年由MENG等［9］提出,該算法作為群智能優化算法中的一員,一經提出就備受研究人員及學者關注.目前CSO算法及其改進算法已經應用到了光伏發電［10］,電動汽車充電站規劃［11］,電網控制［12］等領域中,但應用到WSN節點部署優化的案例還不是很成熟,因此這一方向具有一定的研究意義.并且,WU等［13］根據隨機搜索算法的收斂準則,證明CSO算法滿足兩個收斂準則,保證了全局收斂性,但也指出了該算法的不足.由于算法的學習方法等原因,導致該算法在收斂速度和收斂精度上有所損失,同時易過早陷入局部最優解,因此CSO算法還有許多提升的空間.故DEB等［14］等將TLBO算法與CSO算法相結合,提出了一種基于教與學算法的雞群優化算法.LIANG等［15］提出了一種改進CSO算法用于機器人路徑尋優,該算法引入了具有Lévy飛行特性的搜索策略和非線性遞減策略,尋找到了較好的路徑.雖然已經有許多學者和專家對CSO算法的改進和應用進行了大量的研究,但仍有許多開發的空間.

針對上述不足,本文提出了一種混合雞群優化算法(HCSO)用于WSN節點部署優化的應用.

1 WSN節點部署優化概念與模型

1.1 問題假設

1.2 節點覆蓋模型

設監測區域內分布有N個傳感器節點,每個節點的感知半徑為r,通信半徑為R,并且滿足2r≤R.設T={t1,t2,…,tN},其中ti為第i個傳感器,其位置坐標表示為(xi,yi),若第j個像素點為hj,其位置坐標為(xj,yj).則任意像素點與傳感器之間的歐氏距離可用式(1)來表示:

(1)

對于傳感器與像素點的感知概率,本文使用二元感知模型進行建模,如式(2)表示:

(2)

其中p(ti,hj)為感知概率,r為傳感器的感知半徑,若p(ti,hj)為1則表示像素點hj被傳感器ti所覆蓋,反之則沒有被覆蓋.

在整個監測范圍中,會出現同一個像素點被不同的多個傳感器同時感應到的現象,故需要進行聯合感知概率的計算.像素點與多個傳感器的聯合感知概率如式(3)所展示:

(3)

其中p(T,hj)為聯合感知概率.最終,覆蓋率由式(4)求出:

(4)

其中pcov表示為覆蓋率.綜上所述,式(4)為HCSO應用到WSN節點部署優化的適應度函數,其目標為提高pcov數值.

2 雞群優化算法

公雞為適應度較好的前NR只雞,根據上述表示方法,公雞的位置更新公式為:

(5)

(6)

NH代表母雞的總數,母雞的適應度適中,母雞的位置更新公式如下所示:

(7)

(8)

S2=exp(fr2-fi),

(9)

其中,R1和R2均為［0,1］的隨機數;r1為與母雞同一子群的公雞;r2為另一只隨機選取的雞,且r2≠i,r2≠r1,fr2

適應度最差的個體將被劃分為小雞種群,NC代表種群中小雞的個數.由于小雞是種群中的弱勢群體,故指定其只能跟隨雞媽媽進行覓食.式(10)展示了這一現象的位置更新公式:

(10)

3 混合雞群優化算法

3.1 自適應種群分配

CSO算法是一個全局算法,為了加強其后期的局部搜索能力,本文加入了自適應種群分配策略.該策略使前期公雞種群的粒子個數增加,隨著迭代的過程,慢慢減少;而母雞種群的粒子個數與之相反,是處于慢慢增加的狀態.由于每G次迭代CSO會重新規劃一次種群秩序,故種群數量的改變也是每G次進行一次.該策略的具體實現方法如式(11)所示:

(11)

其中PR,PH,PC分別代表每一個種群個體數量占雞群總數量的百分比;t代表當前迭代次數;T代表最大迭代次數;C1,C2用來控制每次迭代種群個體數量百分比增長或減小的速度;PRmin用來控制最終公雞的數量比;PHmax用來控制母雞的最終數量比,經實驗測試PRmin和PHmax的取值與基本CSO算法的公雞和母雞占比數相同時算法的性能最優.

3.2 融合正余弦思想的公雞位置更新優化

由于CSO算法中公雞位置更新方法只是基于正態分布的變異方法,當算法的種群多樣性變低時,會導致公雞種群的個體難以跳出局部最優,從而使算法效率變慢,收斂精度變低.本文引入正余弦算法(Sine Cosine Algorithm,SCA)［16］的思想來優化公雞位置更新公式,具體方法如下:

(12)

(13)

3.3 改進小雞更新思想

由于CSO算法中,小雞向其母親學習,若其母親陷入局部最優解,小雞也會隨之學習,從而降低算法整體的效率.故本文使小雞向其雙親學習,并增加突變的可能,學習全局最優個體.引進隨機交叉變異思想,改進后的小雞位置更新公式如下:

(14)

(15)

其中FL∈［0,2］為隨機交叉變異的調節參數;Q是［-1,1］的隨機數,該參數為學習調控因子,能夠同時調控兩邊的學習力度;ω是一個自適應權重系數;r為［0,1］之間的隨機數,控制小雞是否發生突變.改進后的小雞更新位置公式使小雞能夠更好地跳出局部最優解,提高適應度,提高算法的效率.

3.4 HCSO節點部署優化流程

步驟1 初始化WSN節點參數和HCSO算法參數,如:節點個數N,感知半徑r,粒子個數pop,最大迭代次數等.

步驟2 初始化粒子位置,并使用式(1)～(4)計算覆蓋率.

步驟3 判斷mod(t,G)是否為1,是則根據式(11)進行種群規劃;否則進行步驟4.

步驟4 每個粒子根據其被劃分的種群,按照式(7)～(9),式(12)～(15)進行位置更新.

步驟5 算法若到最大迭代次數,則輸出優化后的覆蓋率等結果;算法若沒達到最大迭代次數,跳至第3步進行下一次的迭代.

3.5 復雜度分析

假設種群中總粒子數量為N,公雞數量為NR,小雞數量為NC,解空間維度為D,T為最大迭代次數.HCSO引入了自適應種群分配策略,每G次更改一次種群比例,則計算種群百分比的時間復雜度為O(T/G);改進后的公雞位置更新公式時間復雜度為O(NRDT);修改了小雞的學習策略,其時間復雜度為O(NCDT),本算法的時間復雜度與原算法相同.

4 仿真實驗設計與分析

4.1 基準函數測試

4.1.1實驗設計

為了驗證HCSO算法的有效性,本文選取了6個具有代表性的基準測試函數,其中函數f1為簡單的單峰函數,能夠測試算法的收斂速度;函數f2為高維單峰函數,能夠測試算法的收斂精度和收斂速度;函數f3是不連續階梯函數,該函數能夠對算法的有效性進行測試;函數f4～f6為3個不同的多峰函數,能夠很好地檢驗算法的全局搜索能力.通過這些函數對HCSO進行測試,并與PSO［17］,CSO,SCA,GWO［18］,ICSO［15］進行結果對照及分析,表1中給出了函數的具體表達式.每個算法在其搜索空間中共有30個粒子進行搜索,單獨在6個基準函數上運行30次(每次迭代1 000次)所統計出來其優化結果進行比較.各算法的具體參數設計如表1所示,基準函數表達式如表2所示.

4.1.2測試結果分析

圖1、圖2為每個算法在f1～f6的函數收斂圖和箱線圖,附表Ⅰ為每個算法在f1～f6單獨運行30次(每次迭代1 000次)所統計出來的數據表.通過3種不同的展示方法可以明顯看出,HCSO與原算法相比,收斂精度、收斂速度和跳出局部最優能力都有提高.

表1 算法參數表

表2 基準函數表

在單峰測試函數,圖1(a-c)中可以看到雖然本算法沒有優化到理想最優值,但相較于其他算法,HCSO的精度都是最好的.GWO雖然能快速地收斂,但都陷入了局部最優.附表Ⅰ中黑體部分為HCSO運算結果,可以看出 PSO和SCA運行速度非常快,但他們的精度卻不高,雖然HCSO的運行速度總體比PSO和SCA的運行速度慢,但這是由CSO算法本身的結構造成的,HCSO已經比其原算法有所減少.故本算法對于單峰函數優化起到了比較好的效果.

在多峰函數測試中,可以在箱線圖中看出,HCSO是最穩定的,且沒有離群值.對于函數f4和f5,HCSO已經找到了理論最優值,并且十分穩定.附表Ⅰ中可以看到其平均值和標準差都是0,說明獨立運行的30次每次都能找到局部最優.雖然其他算法也能夠找到,但是并不穩定.在圖1(d)和圖1(f)中可以看到,HCSO幾乎在不到100次迭代就可以找到理論最優值,故其收斂速度也很優秀.因此可以看出,HCSO對于多峰函數的優化也很出色,其收斂速度和精度都有大幅度提高,并且穩定性較好.

由圖2的算法箱線圖可以看出,改進后的HCSO算法對于單峰基準函數和多峰基準函數的優化結果都很穩定,沒有較大的離群值和標準差.同時在表3中也可以看到HCSO在每個算法中的標準差都是最小的,因此HCSO的改進也加強了算法的穩定性.

綜上所述,本文提出的HCSO算法在測試中表現的性能均高于PSO,CSO,SCA,GWO,ICSO.其收斂速度和收斂精度以及穩定性非常出色,所耗費的時間大部分也與原算法相仿甚至優于原算法,驗證了改進的有效性.

4.2 WSN節點部署優化測試

由于函數測試中的算法應用到WSN節點部署優化中其表現的性能較差,無法充分驗證HCSO算法在WSN節點部署優化中的性能和效果,因此在此測試中,選擇CSO,ICSO算法和文獻［19-21］中的算法和模型的覆蓋實驗進行對比,并且設置的實驗模型環境與這些文獻中的實驗模型環境相同.

設需要覆蓋區域是一個S=20 m×20 m的二維平面,內有N=24個傳感器節點,其感知半徑為r=2.5 m,通訊半徑為R=5 m.覆蓋率對比曲線如圖3(a)所示.HCSO優化節點分布圖如圖4(a)所示.

表3展示了在本場景中不同算法優化后得到的結果,其中隨機拋撒所獲得的覆蓋率為67.35%,說明這種情況下,傳感器無法均勻分布在整個空間中,有許多范圍沒有被覆蓋到.使用CSO算法優化后,覆蓋率達到了83.90%,使用ICSO算法優化后,覆蓋率達到了87.30%,使用這兩種方法比隨機拋撒策略覆蓋率有了一定的提高,但仍有一定的優化空間.文獻［19］的IWOA算法,將覆蓋提升到了93.56%,分布較為均勻.HCSO算法改進了公雞收斂公式,使其能夠學習SCA算法的更新方法,使得算法中的優秀個體能夠更好地找到最優值.同時改變小雞學習方式,提高了算法整體粒子質量,使得算法所獲得的結果精度更高.從實驗中可以看到,HCSO算法的覆蓋率達到了94.56%,較隨機拋撒提高了27.21個百分點,極大程度地解決了WSN節點分布不均勻問題.

設需要覆蓋區域是一個S=200 m×200 m的二維平面,內有N=60個傳感器節點,其感知半徑為r=20 m,通訊半徑為R=40 m.節點優化后的結果如表4,覆蓋率對比曲線如圖3(b)所示.HCSO優化節點分布圖如圖4(b)所示.

表3 優化結果對比

表4 200×200優化結果對比

在本場景下,HCSO較CSO和ICSO的覆蓋率分別提升了2.96和7.61個百分點,與IWOA所獲得的覆蓋率相差較小,但HCSO的精度更高.通過圖3(b)中的HCSO優化覆蓋圖可以看出,HCSO算法優化的WSN傳感網絡已經幾乎達到了全覆蓋.

設需要覆蓋區域是一個S=50 m×50 m的二維平面,內有N=40個傳感器節點,其感知半徑為r=5 m,通訊半徑為R=10 m.節點優化后的結果如表5,覆蓋率對比曲線如圖3(c)所示.HCSO優化節點分布圖如圖4(c)所示.

根據表5的數據可以看到,HCSO所獲得的覆蓋率相比隨機拋撒最終提高了22.80個百分點.HCSO算法在迭代200次時,所用時間僅比CSO算法慢0.08 s.所獲得的覆蓋率比IWOA算法提高了7.27個百分點,且速度要比IWOA算法快得多.與HPSBA相比,雖然覆蓋率在迭代200次不如HPSBA所得到的結果好,但HPSBA迭代200次所花費的時間比HCSO算法迭代300次所花費的時間還要多,最終HCSO算法所得到的覆蓋率比HPSBA提高了0.07個百分點.HCSO算法使用自適應種群調整策略,較好平衡了算法局部搜索和全局搜索能力,提高了算法的運行速度.迭代次數調整到300次,HCSO算法的運行速度是最快的,同時其獲得的覆蓋率也是精度最高的.

設需要覆蓋區域是一個S=100 m×100 m的二維平面,內有N=50個傳感器節點,其感知半徑為r=10 m,通訊半徑為R=20 m.節點優化后的結果如表6,覆蓋率對比曲線如圖3(d)所示.HCSO優化節點分布圖如圖4(d)所示.

在文獻［20］中,沒有給出ESCA算法的迭代次數和迭代時間的數據.根據覆蓋率可以看到,最終HCSO算法所獲得的覆蓋率比ESCA算法提高了0.68個百分點.在迭代次數為200時,隨機拋撒所得到的覆蓋率僅達到了79.64%,說明存在大部分節點冗余,節點分布不均勻.使用CSO算法和ICSO算法優化后,覆蓋率分別為91.96%和90.55%,起到了一定的優化效果.文獻［19］中的IWOA算法優化后,大幅度提高了節點覆蓋率,達到了97.92%,但仍比HCSO算法優化后的覆蓋率低.HCSO算法優化后覆蓋率達到了98.90%,同時HCSO算法的運行速度也是最快的,耗時為66.75 s.迭代次數調整到300后,HCSO算法仍然能夠繼續尋找更好的分配策略,最終使WSN節點覆蓋率達到了99.26%,從圖4(b)中也可以看到,節點分布比較均勻,很好地解決了節點冗余問題.

5 結 論

本文針對在傳統無線傳感網絡中,使用隨機拋撒策略對傳感器節點進行部署,會出現被覆蓋區域的節點分布不均勻,覆蓋率低等問題.提出了一種混合雞群優化算法.該算法加入了自適應種群分配策略,提高算法的前后期搜索速度及精度;又利用正余弦算法改進CSO公雞的更新策略,提高了跳出局部最優解的能力;最后更新小雞學習策略,使其學習其雙親以及最優個體,還能夠交叉突變,提高小雞群體的質量,從而提高算法整體質量.通過6個基準函數測試,比對了HCSO算法與其他算法所獲得的優化結果.表明HCSO算法均取得了比較理想的適應度值,加快了運行速度和收斂速度.最后將HCSO算法應用到WSN節點部署優化中去,首先與原算法比較基本都能提高2～10個百分點,與其他改進算法進行比較,也能夠對不同環境下的節點覆蓋率進行一定的優化提高,增強了WSN網絡的性能.后續將對多目標的CSO算法進行研究,并準備運用到多目標WSN節點部署問題中.

附 錄

附表Ⅰ見電子版(DOI:10.16366/j.cnki.1000-2367.2023.05.006).