田思琪,郎百和,韓太林

0 引 言

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

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

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

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

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

速度為

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

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

1.1 改進(jìn)的混沌粒子群

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

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

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

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

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

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

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

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

1.2 量子粒子群

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

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

用于抑制粒子的速度。

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

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

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

2.1 代價函數(shù)

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

分簇緊湊評價因子

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

能量評價因子

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

位置評價因子

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

則當(dāng)選簇頭的代價公式為

其中a+b+c=1。

2.2 分簇算法

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

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

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

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

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

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

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

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

3 WSN模型及能耗模型

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

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

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

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

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

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

4 仿真與分析

4.1 參數(shù)設(shè)置

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

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

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

4.2 仿真分析

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

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

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

圖5 能量方差Fig.5 Varianceofenergy

5 結(jié) 語

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

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

[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].吉林大學(xué)學(xué)報:信息科學(xué)版,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].吉林大學(xué)學(xué)報:信息科學(xué)版,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)絡(luò)非均勻分簇路由協(xié)議[J].計(jì)算機(jī)應(yīng)用研究,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].通信學(xué)報,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)化算法的慣性權(quán)值遞減策略研究[J].西安交通大學(xué)學(xué)報,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.