基于混沌-量子粒子群的分簇路由算法

田思琪,郎百和,韓太林

0 引 言

無線傳感網(wǎng)絡(WSN:Wireless Sensor Network)中的傳感器節(jié)點由于能量有限,在工作過程中不能進行二次充電或更換電池,因此,如何有效提高網(wǎng)絡節(jié)點的能量利用率,延長節(jié)點的生命周期是無線傳感網(wǎng)絡路由算法的關鍵技術之一。路由的表現(xiàn)方式可分為層次路由與平面路由。層次路由相對平面路由具有擴展性好、建立維護路由的開銷小、數(shù)據(jù)傳輸跳數(shù)少和適合大規(guī)模網(wǎng)絡的特點。層次路由通常利用分簇方式提高能量利用率,延長生命周期。分簇路由協(xié)議的思想是:將網(wǎng)絡中所有節(jié)點以一定的競選方式選出N個最優(yōu)節(jié)點作為簇頭,然后其他節(jié)點在以一定的算法機制選擇加入某個簇頭形成簇,最終由簇頭收集其他成員節(jié)點的信息并進行融合發(fā)送給匯聚節(jié)點。但采用分簇路由協(xié)議時,簇的維護開銷較大,所以如何選取最優(yōu)簇頭是優(yōu)化路由的關鍵。LEACH(Low-Energy Adaptive Clustering Hierarchy)是由Heinzelman等[1]首次提出的一種基于分簇的路由協(xié)議。但LEACH協(xié)議并沒有規(guī)定簇頭的分布范圍并加以限定,從而導致選擇的簇頭會集中在某一區(qū)域,使整個傳感網(wǎng)絡能耗分布不均勻。因此,國內(nèi)外學者在簇頭選取方面選擇粒子群、蟻群等智能算法[2-6],在成簇方式上選擇K-Means、EECS(Energy-Efficient Clustering Scheme)等[7-11]聚類策略改善簇頭分布不均的問題。

進化算法具有較強的全局收斂能力和魯棒性,且不需借助特征信息,如導數(shù)等梯度信息。粒子群優(yōu)化算法(PSO:Particle Swarm Optimization)[12]也是一類基于群體智能的隨機優(yōu)化算法,作為簡單有效的隨機搜索算法,在尋求函數(shù)最優(yōu)解、神經(jīng)網(wǎng)絡訓練和模式識別等領域具有很大應用潛力。粒子群算法是1995年由美國社會心理學家James Kennedy和電氣工程師Russell Eberhart共同提出的[13],其基本思想是受他們早期對鳥類群體行為研究結果的啟發(fā),并利用生物學家Frank Heppner的生物群體模型。與其他進化類算法相似,也是用群體與進化的概念,同樣也是依據(jù)個體(微粒)的目標函數(shù)值大小進行操作。PSO算法由于其簡單易懂在許多領域中都有應用,然而該算法也具有收斂速度慢、易陷入局部最優(yōu)的缺點。在無線傳感器網(wǎng)絡路由算法中,利用PSO算法尋找最優(yōu)簇頭的過程中,會使網(wǎng)絡節(jié)點能量消耗過快,引起無線傳感網(wǎng)絡節(jié)點能量消耗不均衡、造成傳感節(jié)點呈現(xiàn)大面積平鋪式的死亡等現(xiàn)象。文獻[13]提出了一種PSO-C(Cluster setup using Particle Swarm Optimization Algorithm)分簇路由算法,在選取簇頭時雖考慮了成員節(jié)點與簇頭之間的距離,但忽略了簇頭與匯聚節(jié)點的距離致使網(wǎng)絡節(jié)點能量消耗過快,生命周期得不到保障;文獻[14]提出的EBUCP(Energy-Balanced Unequal Clustering Protocol)算法綜合考慮了能量、地理位置及簇頭密度等因素,延長了網(wǎng)絡的生命周期,但未改進PSO算法使算法容易陷入局部最優(yōu),導致網(wǎng)絡能量消耗不均衡。

筆者對PSO算法的權重進行改進,采用收斂速度快的凹函數(shù)遞減策略優(yōu)化權重,并引入混沌因子與量子元素,構成雙子粒子群(TSPSO:Two Subpopulation Particle Swarm Optimization)算法,改進了簇頭選取模式,提高了節(jié)點的能量利用率,延長網(wǎng)絡的生命周期。

1 粒子群優(yōu)化算法

PSO算法的數(shù)學模型:假設在D維度空間中,有M個粒子,每個粒子的位置為

速度為

其中i=1,2,…,M。每個粒子經(jīng)過的歷史最優(yōu)位置用pi表示,所有粒子經(jīng)歷過的最好位置用pg表示。每個粒子均按照

進行速度與位置的更新。其中w為慣性權重;c1與c2指自身繼承及社會繼承的學習因子;r1與r2是0～1之間的隨機數(shù)。

1.1 改進的混沌粒子群

傳統(tǒng)的粒子群算法初期收斂較快,而在后期容易陷入早熟狀態(tài),即導致局部最優(yōu)。采用胥小波等[15]提出的混沌粒子群,不再利用混沌序列產(chǎn)生新粒子代替原粒子,而是將混沌態(tài)融入到粒子的運動過程中,使粒子在穩(wěn)定與混沌狀態(tài)間交替運動,在保證精度的前提下,避免算法產(chǎn)生初期收斂過快的現(xiàn)象。

為將粒子混沌化,采用Sole等[16]提出的混沌系統(tǒng)

其中x∈(0,1)表示混沌狀態(tài);μ∈[0,4]表示混沌系統(tǒng)的控制參量。引入混沌變量

在粒子運動過程中控制粒子的混沌狀態(tài)。其中rid表示第i個粒子第d維的混沌因子,且是不大于1的正常數(shù)。

混沌粒子群優(yōu)化系統(tǒng)中的速度更新采用與式(3)相同的方式,而位置更新方式為

其中ψd為搜索測度。當cid→0時,粒子的速度及位置分別按式(3)、式(4)更新;當cid→1時,粒子的速度及位置分別按式(3)、式(7)更新。

根據(jù)陳貴敏等[17]提出的關于慣性權重的理論,非線性慣性權重策略相比線性遞減的慣性權重策略更能有效地控制粒子群算法的全局搜索以及局部搜索。采用凹函數(shù)非線性遞減策略更新慣性權重,規(guī)則為

其中w∈[0.45,0.9];CCurCount為當前迭代輪數(shù);CLoopCount為迭代總輪數(shù)。

1.2 量子粒子群

量子粒子群的思想是由Xu等[18]在2005年提出的,其從量子力學角度出發(fā),使PSO算法中的粒子具有量子行為,用位移模型代替了速度-位移模型,具體迭代方法為

其中Pavebest表示種群平均的最優(yōu)位置;M為種群大小;φ,μ為0～1之間的隨機數(shù);壓縮-擴張因子

用于抑制粒子的速度。

2 基于混沌-量子的TSPSO分簇路由協(xié)議

分簇路由協(xié)議結構圖如圖1所示。TSPSO路由協(xié)議采用分簇的體系結構,將所有的網(wǎng)絡節(jié)點分為兩類:一類是簇頭,簇頭通過代價函數(shù)的約束選取,負責收集普通節(jié)點的消息,并將所有的消息融合后傳送給基站;另一類是普通節(jié)點,根據(jù)分簇算法,尋找其所屬簇頭,并將消息傳送給簇頭。

圖1 分簇路由協(xié)議結構Fig.1 Structure of clustered routing protocol

2.1 代價函數(shù)

為使傳感網(wǎng)絡能耗消耗均衡,并延長其生命周期,算法的代價函數(shù)定義如下。

分簇緊湊評價因子

其中d(ni,Hpj,k)表示普通節(jié)點到對應簇頭的歐氏距離,Cpj,k為當前簇頭所對應的成員個數(shù),K為簇頭個數(shù)。

能量評價因子

其中E(ni)為普通節(jié)點的能量,E(Hpj,k)為簇頭的能量。

位置評價因子

其中d(B,Hpj,k)為基站與當前簇頭的歐氏距離,d(B,N)為基站與網(wǎng)絡中心的距離。

則當選簇頭的代價公式為

其中a+b+c=1。

2.2 分簇算法

TSPSO實現(xiàn)的思想是,將初始化后的粒子等分成兩個種群,分別為主粒子群和輔粒子群,主輔兩種粒子群按自己的位置分別進行更新尋優(yōu),每次迭代更新后比較各自代價函數(shù),代價函數(shù)值較優(yōu)的粒子代替較差的,以此更新種群,從而加快粒子尋優(yōu)的速度。

TSPSO算法中,主粒子群用改進的混沌粒子群尋優(yōu),輔粒子群用量子粒子群尋優(yōu)。數(shù)據(jù)收集以“輪”的形式進行更新,具體算法如下。

1)根據(jù)節(jié)點能量,初始化M個粒子群。將節(jié)點能量大于節(jié)點平均能量的節(jié)點作為候選簇頭,從候選簇頭中隨機選擇K個節(jié)點作為一個粒子群。

2)利用式(13)～式(16)計算每個粒子的代價函數(shù)值。

3)確定每個粒子的個體最優(yōu)解Pid和種群最優(yōu)解Pgd。

4)根據(jù)式(4)～式(12)分別更新主、輔粒子群的速度與位置。

5)重復步驟2)與步驟3),直到達到最大循環(huán)次數(shù)MMaxIter。

迭代完成后,得到傳感網(wǎng)絡中最優(yōu)簇頭,根據(jù)就近原則,普通節(jié)點根據(jù)到各個簇頭的歐氏距離大小選擇加入哪個簇頭。通過這種分簇結構,實現(xiàn)數(shù)據(jù)節(jié)點到基站(匯聚節(jié)點)的路由。

3 WSN模型及能耗模型

算法采用與文獻[19]相同的傳輸能耗模型,定義節(jié)點發(fā)射l bit的數(shù)據(jù)到距離d的位置,能量消耗由發(fā)射電路損耗和功率放大損耗兩部分組成,即

其中d0為發(fā)送者至接收者的距離閾值,根據(jù)不同的傳輸距離選擇不同的能耗模型。εfs、εmp分別為兩種模型下功率放大所需的能量消耗。閾值

節(jié)點接收l bit的數(shù)據(jù)消耗能量為

簇頭融合數(shù)據(jù)消耗能量為

無線通信能耗模型仿真參數(shù)設置如表1所示。

表1 無線通信能耗模型參數(shù)設置Tab.1 Parameter of wireless communication energy consumption model

4 仿真與分析

4.1 參數(shù)設置

仿真在Matlab R2017a環(huán)境下進行,將N=200個網(wǎng)絡節(jié)點隨機灑落在200×200的方形區(qū)域內(nèi),基站坐標為(100,275),模型能耗的參數(shù)設置如表1所示。節(jié)點分布圖如圖2所示,且簇頭個數(shù)

其中A為方形區(qū)域的邊長,dtosink為簇頭到基站的距離。

圖2 節(jié)點分布圖Fig.2 Node distribution map

4.2 仿真分析

筆者將算法與LEACH、PSO-C及EBUCP算法進行了仿真對比分析。圖3為每輪節(jié)點的平均剩余能量,圖4為每輪節(jié)點的存活個數(shù)。TSPSO協(xié)議在簇頭選擇上結合了節(jié)點的能量和位置信息以及與基站的距離,在節(jié)點初始能量相同的情況下,TSPSO協(xié)議每輪的能量消耗明顯較其他3種協(xié)議少,保證了傳感節(jié)點的生命周期。仿真結果證明,TSPSO協(xié)議的生命周期比LEACH協(xié)議、PSO-C協(xié)議分別延長了80.1%和41.4%。說明基于混沌-量子粒子群的TSPSO協(xié)議能更好地延長網(wǎng)絡的生存時間。與EBUCP相比能更好地均衡網(wǎng)絡中節(jié)點的能耗。圖5是4種協(xié)議的能量方差,TSPSO協(xié)議由于采用了混沌與量子結合的兩種模式,使粒子在混沌與量子形態(tài)中較快的尋找到最優(yōu)簇頭,能量方差較小。進一步說明了TSPSO協(xié)議在能量消耗的均衡性方面顯著優(yōu)于其他3種協(xié)議。

圖3 節(jié)點平均剩余能量Fig.3 Node average residual energy

圖4 節(jié)點存活個數(shù)Fig.4 Numberofnodessurviving

圖5 能量方差Fig.5 Varianceofenergy

5 結 語

針對無線傳感網(wǎng)絡分簇路由協(xié)議,首次提出了混沌與量子結合的雙粒子群模式,將改進的混沌粒子群作為主粒子群,量子粒子群作為輔粒子群。

當粒子群陷入早熟收斂時,利用混沌運動的隨機性、對初始值敏感等特點,將混沌態(tài)融入到粒子的運動過程中,使粒子在混沌與量子狀態(tài)間交替運動,以避免陷入局部最優(yōu),從而尋求更優(yōu)解,達到在不影響精度的前提下,使粒子快速收斂的目的。綜合考慮節(jié)點的能量以及位置尋找最優(yōu)簇頭,仿真結果驗證了算法使無線傳感網(wǎng)絡節(jié)點能量消耗更加均衡,顯著延長了網(wǎng)絡生命周期。

[1]HEINZELMAN W,CHANDRAKASAN A,BALAKRISHNAN H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]∥Proceedings of the 33rd Hawaii International Conference on System Sciences.Maui,USA:IEEE,2000:3005-3014.

[2]ELHABYAN R.PSO-HC:Particle Swarm Optimization Protocol for Hierarchical Clustering in Wireless Sensor Networks[C]∥International Conference on Collaborative Computing:Networking,Applications and Worksharing.Miami,FL,USA:IEEE,2015:417-424.

[3]REN Z,WANG L,LEI H.A Study on Energy-Saving Routing Algorithms for Wireless Sensor Networks Based on Particle Swarm Optimization[C]∥Second International Conference on Instrumentation,Measurement,Computer,Communication and Control.Harbin,China:IEEE,2013:638-643.

[4]ZAHEERUDDIN,LOBIYAL D K,PRASAD S.Ant Based Pareto Optimal Solution for QoSAware Energy Efficient Multicast in Wireless Networks[J].Applied Soft Computing,2017,55:72-81.

[5]MAJUMDAR S,SHIVASHANKAR,PRASAD P R,et al.An Efficient Routing Algorithm Based on Ant Colony Optimization for VANETs[C]∥IEEE International Conference on Recent Trends in Electronics,Information&Communication Technology.Bengaluru,India:IEEE,2017:436-440.

[6]FARZANA A H F,NEDUNCHELIYAN S.Ant Based Mobility Aided Routing in Mobile Wireless Sensor Networks[C]∥International Conference on Information Communication and Embedded Systems.Chennai,India:IEEE,2016:1-5.

[7]PARK G Y,KIM H,JEONG H W,et al.A Novel Cluster Head Selection Method Based on K-Means Algorithm for Energy Efficient Wireless Sensor Network[C]∥International Conference on Advanced Information Networking and Applications Workshops.Barcelona,Spain:IEEE,2013:910-915.

[8]BIDAKI MOAZAM,GHAEMI REZA,TABBAKH SEYED REZA KAMEL.Towards Energy Efficient K-Means Based Clustering Scheme for Wireless Sensor Networks[J].International Journal of Grid and Distributed Computing,2016,9(7):265-276.

[9]YE M,LI C,CHEN G,et al.EECS:An Energy Efficient Clustering Scheme in Wireless Sensor Networks[C]∥Performance,Computing,and Communications Conference.Phoenix,AZ,USA:IEEE,2005:535-540.

[10]王白婷,周占穎,蘇真真,等.能耗均衡的非均勻分簇多跳路由協(xié)議[J].吉林大學學報:信息科學版,2016,34(2):174-181.WANG Baiting,ZHOU Zhanying,SU Zhenzhen,et al.Multi-Hop Unequal Clustering Routing Protocol Based on Energy Consumption Balance[J].Journal of Jilin University:Information Science Edition,2016,34(2):174-181.

[11]韓廣輝,張麗翠.基于LEACH協(xié)議的無線傳感網(wǎng)能效分簇算法[J].吉林大學學報:信息科學版,2017,35(1):26-31.HAN Guanghui,ZHANG Licui.Energy Efficient Clustering Algorithm for Wireless Sensor Networks Based on LEACH Protocol[J].Journal of Jilin University:Information Science Edition,2017,35(1):26-31.

[12]KENNEDY J,EBERHART R C.Particle Swarm Optimization[C]∥Proc of IEEE International Conference on Neural Networks.Perth,WA,Australia:IEEE,1995:1942-1948.

[13]LATIFF N M A,TSIMENIDIS C C,SHARIF B S.Energy-Aware Clustering for Wireless Sensor Networks Using Particle Swarm Optimization[C]∥Proc of the 18th IEEE International Symposium on Personal,Indoor and Mobile Radio Communications.Athens,Greece:IEEE,2007:1-5.

[14]蔣暢江,唐賢倫,向敏.基于PSO的無線傳感器網(wǎng)絡非均勻分簇路由協(xié)議[J].計算機應用研究,2012,29(8):3074-3077.JIANG Changjiang,TANG Xianlun,XIANG Min.Heterogeneous Clustering Routing Protocol for Wireless Sensor Networks Based on Particle Swarm Optimization[J].Application Research of Computers,2012,29(8):3074-3077.

[15]胥小波,鄭康鋒,李丹,等.新的混沌粒子群優(yōu)化算法[J].通信學報,2012,33(1):24-30.XU Xiaobo,ZHENG Kangfeng,LI Dan,et al.New Chaotic Particle Swarm Optimization Algorithm[J].Journal on Communications,2012,33(1):24-30.

[16]SOLE R V,MIRAMONTESO,GOODWIN B C.Oscillations and Chaos in Ant Societies[J].Journal of Theoretical Biology,1993,161(3):343-357.

[17]陳貴敏,賈建援,韓琪.粒子群優(yōu)化算法的慣性權值遞減策略研究[J].西安交通大學學報,2006,40(1):53-56.CHEN Guimin,JIA Jianyuan,HAN Qi.Study on Inertia Weight Decreasing Strategy of Particle Swarm Optimization Algorithm[J].Journal of Xi'an Jiaotong University,2006,40(1):53-56.

[18]XU W,SUN J.Adaptive Parameter Selection of Quantum-Behaved Particle Swarm Optimization on Global Level[J].Computer Engineering&Applications,2005,86(12):420-428.

[19]HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNAN H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-669.