基于人工蜂群算法的無線傳感器網(wǎng)絡(luò)路由協(xié)議

，，2， ，

(1.浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023；2.金華市中心醫(yī)院，浙江 金華 321000)

無線傳感器網(wǎng)絡(luò)(Wireless sensor network, WSN)是由一系列微小的自主節(jié)點(diǎn)組成，具有組網(wǎng)靈活、監(jiān)測精度高、部署迅速、容錯性好、抗毀性強(qiáng)等優(yōu)點(diǎn)，在軍事戰(zhàn)爭、環(huán)境科學(xué)、災(zāi)難救援、智能家居、醫(yī)療衛(wèi)生等領(lǐng)域具有廣闊的應(yīng)用前景[1-3].研究人員長期對生物種群進(jìn)行觀察研究，發(fā)現(xiàn)一個有趣的現(xiàn)象：自然界中某些生物個體表現(xiàn)出的行為非常簡單，但當(dāng)個體間相互協(xié)作所表現(xiàn)出的行為特征非常復(fù)雜，而不僅僅是個體行為簡單的疊加[4-5].研究者根據(jù)不同的生物群體表現(xiàn)出的不同行為提出了不同的群體智能算法，包括粒子群算法(Particle swarm optimization, PSO)[6]、蟻群算法(Ant colony algorithm, ACA)[7]、人工魚群算法(Artificial fish school algorithm, AFS)[8]、細(xì)菌覓食算法(Bacterial foraging optimization, BFO)[9]、人工蜂群算法(Artificial bee colony algorithm, ABC)[10]等.蜂群的自組織模擬模型最早由Seeley于1995年提出，后來Karaboga將蜂群算法成功應(yīng)用于函數(shù)的極值優(yōu)化問題，系統(tǒng)的提出了人工蜂群算法，Basturk等在2006年將人工蜂群算法理論用于解決優(yōu)化問題，得到了很好的結(jié)果.

節(jié)點(diǎn)間通信消耗了網(wǎng)絡(luò)的大部分能量，采用合理的路由方式可以減少能量消耗.為了延長整個網(wǎng)絡(luò)的壽命，結(jié)合人工蜂群算法和圖論中的最短路徑樹的思想對LEACH協(xié)議進(jìn)行改進(jìn)，提出一種新的路由協(xié)議.利用改進(jìn)后的人工蜂群算法完成網(wǎng)絡(luò)中簇首節(jié)點(diǎn)的選擇，解決LEACH協(xié)議中簇首節(jié)點(diǎn)分布不均勻的問題；根據(jù)需要在簇內(nèi)生成最短路徑樹，使簇內(nèi)每一個節(jié)點(diǎn)與簇首節(jié)點(diǎn)通信的代價最小，從而減少整個網(wǎng)絡(luò)的能量消耗.

1 人工蜂群算法

在人工蜂群算法中，將蜜蜂分為引領(lǐng)蜂、跟隨蜂和偵察蜂三種，其中引領(lǐng)蜂的數(shù)量與食物源的數(shù)量相等.初始化階段，隨機(jī)產(chǎn)生N個解作為食物源的位置，然后對解進(jìn)行評估，得到適應(yīng)度fitness，適應(yīng)度大小表示食物源的質(zhì)量好壞[11].

引領(lǐng)蜂位置的更新公式為

Yi(t+1)=Yi(t)+δ(Yi(t)-Yk(t))

(1)

式中：Yi(t+1)為新產(chǎn)生的第i個食物源的位置；Yi(t)為原來的第i個食物源的位置；δ為[-1,1]之間的隨機(jī)數(shù)；i,k∈{1,2,…,N},i≠k.

引領(lǐng)蜂在蜂巢內(nèi)的舞蹈區(qū)，將食物源的信息告訴給跟隨蜂，跟隨蜂根據(jù)食物源的適應(yīng)度選擇食物源.

(2)

式中：Fi為第i個食物源的適應(yīng)度大小；pi為第i個食物源被跟隨蜂選中的概率.

隨著采蜜工作的進(jìn)行，食物源的豐富程度會降低，可能出現(xiàn)食物源枯竭的情況.為防止這種現(xiàn)象發(fā)生，若在限定循環(huán)次數(shù)后食物源適應(yīng)度仍沒有得到改善，則放棄該食物源，對應(yīng)的引領(lǐng)蜂就變成偵察蜂，然后產(chǎn)生一個新的食物源位置，即

Yi=Ymin+η(Ymax-Ymin)

(3)

式中η為(0，1)之間產(chǎn)生的一個隨機(jī)數(shù).

2 基于ABC的WSN分簇算法

LEACH協(xié)議是無線傳感器網(wǎng)絡(luò)路由協(xié)議中非常重要的一種層次型路由協(xié)議.在LEACH協(xié)議引入了“輪數(shù)”的概念，每一輪都需要重新選擇簇首節(jié)點(diǎn)，且每一個節(jié)點(diǎn)當(dāng)選為簇首節(jié)點(diǎn)的概率相等.通過分簇的方式將整個網(wǎng)絡(luò)的能耗均衡的分配到各個節(jié)點(diǎn)，從而提高了整個網(wǎng)絡(luò)的壽命.與平面路由協(xié)議相比，LEACH協(xié)議具有非常明顯的優(yōu)勢，但簇首節(jié)點(diǎn)按隨機(jī)方式選擇，無法確定每一輪簇首節(jié)點(diǎn)在網(wǎng)絡(luò)中分布的位置，可能會出現(xiàn)當(dāng)選的簇首節(jié)點(diǎn)聚集在一塊的情況.網(wǎng)絡(luò)中簇首節(jié)點(diǎn)分布不均勻，會使某些節(jié)點(diǎn)必須與較遠(yuǎn)的簇首節(jié)點(diǎn)進(jìn)行通信，增大了通信時的能耗.另一方面，在簇首節(jié)點(diǎn)選定后，LEACH協(xié)議采用TDMA方式使簇首節(jié)點(diǎn)與簇內(nèi)每一個節(jié)點(diǎn)直接通信，這種通信方式對于離簇首節(jié)點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)來說能量消耗太大，容易造成節(jié)點(diǎn)的快速死亡.為減少這兩方面問題對網(wǎng)絡(luò)的影響，通過人工蜂群算法來選擇網(wǎng)絡(luò)中的簇首節(jié)點(diǎn)，在簇首節(jié)點(diǎn)確定后，根據(jù)圖論中的最短路徑思想，在簇內(nèi)以簇首節(jié)點(diǎn)為樹根建立一顆最短路徑樹，使每個簇內(nèi)節(jié)點(diǎn)與簇首節(jié)點(diǎn)通信時所消耗的能量最少.

2.1 人工蜂群算法選擇簇首節(jié)點(diǎn)

無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)消耗的總能量主要取決于節(jié)點(diǎn)通信所消耗的能量，而節(jié)點(diǎn)通信消耗能量由通信距離決定[12].要保證整個網(wǎng)絡(luò)消耗的總能量最少，就要確保每個簇內(nèi)節(jié)點(diǎn)到簇首節(jié)點(diǎn)通信所消耗的能量與簇首節(jié)點(diǎn)到基站通信所消耗的能量的和最小.對于ABC算法，只要能夠構(gòu)造出合適的適應(yīng)度函數(shù)，就可以得到最優(yōu)解.

Friis自由空間方程式表明：在自由空間環(huán)境中，節(jié)點(diǎn)天線的接收功率為

(4)

式中：P1，P2分別為發(fā)射功率和接收功率；G1，G2分別為發(fā)射端增益和接收端增益；λ為工作波長；d為節(jié)點(diǎn)間的距離.

由式(4)可知：節(jié)點(diǎn)之間的距離可以通過測量接收端和發(fā)射端的信號強(qiáng)度來獲得，即

(5)

每個節(jié)點(diǎn)由于自身的硬件限制，只有在接收到的信號功率P2大于某一值S時才能正常的接收數(shù)據(jù)，結(jié)合式(4)有

(6)

對于一個具有n個節(jié)點(diǎn)的簇，消耗的總能量為

(7)

式中：i為節(jié)點(diǎn)號；d為簇內(nèi)節(jié)點(diǎn)到簇首節(jié)點(diǎn)的距離；l為簇首節(jié)點(diǎn)到基站的距離.

由上面的分析可以得到應(yīng)用于無線傳感器網(wǎng)絡(luò)中人工蜂群算法的適應(yīng)度函數(shù)為

(8)

為保證簇首節(jié)點(diǎn)有充足的能量接收簇內(nèi)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，并把接收到的數(shù)據(jù)發(fā)送給基站，在通過ABC算法選擇簇首節(jié)點(diǎn)時應(yīng)保證候選簇首節(jié)點(diǎn)的剩余能量大于接收簇內(nèi)所有節(jié)點(diǎn)數(shù)據(jù)包消耗的能量與發(fā)送融合后的數(shù)據(jù)包到基站消耗的能量的和，對于最大剩余能量小于給定值的節(jié)點(diǎn)不能當(dāng)選為簇首節(jié)點(diǎn).

2.2 簇內(nèi)生成最短路徑樹

LEACH協(xié)議在選定簇首節(jié)點(diǎn)后，簇首節(jié)點(diǎn)廣播信息，通知其他節(jié)點(diǎn)加入.網(wǎng)絡(luò)中其他節(jié)點(diǎn)根據(jù)接收信息的信號強(qiáng)度大小來選擇簇首節(jié)點(diǎn)，從而完成簇的建立.簇首節(jié)點(diǎn)與每個簇內(nèi)節(jié)點(diǎn)之間采用TDMA方式直接通信.由式(6)可以看出：節(jié)點(diǎn)通信時的發(fā)射功率與節(jié)點(diǎn)間距離的平方成正比，對于某些離簇首節(jié)點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)直接通信會過多的消耗節(jié)點(diǎn)能量.相對于直接通信，采用多跳通信的方式消耗的總能量可能比直接通信消耗的能量更少，而且可以確保網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗更加均衡.根據(jù)最短路徑思想，建立以簇首節(jié)點(diǎn)為根的最短路徑樹，使每個簇內(nèi)節(jié)點(diǎn)發(fā)送數(shù)據(jù)到簇首節(jié)點(diǎn)能耗最小.

Dijkstra算法是圖論中計(jì)算最短路徑的經(jīng)典算法，其思想是為每個節(jié)點(diǎn)v保留目前為止所找到的從源節(jié)點(diǎn)S到節(jié)點(diǎn)v的最短距離.只要確定了邊的權(quán)值就能夠通過Dijkstra算法在網(wǎng)絡(luò)中構(gòu)建最短路徑樹，邊的權(quán)值Q由節(jié)點(diǎn)間的距離d和節(jié)點(diǎn)剩余能量Er共同決定，距離越大，邊的權(quán)值越大；節(jié)點(diǎn)剩余能量越大，邊的權(quán)值越小.

2.3 算法描述

為表述方便，將利用人工蜂群算法對LEACH協(xié)議中簇首節(jié)點(diǎn)的選擇過程進(jìn)行改進(jìn)后的算法簡稱為ABCCR算法；將結(jié)合人工蜂群算法和最短路徑樹算法對LEACH協(xié)議進(jìn)行改進(jìn)后的算法簡稱為ABCCR-SPT算法.ABCCR-SPT算法與LEACH協(xié)議的主要區(qū)別在于簇首節(jié)點(diǎn)的選擇過程和簇首節(jié)點(diǎn)與簇內(nèi)節(jié)點(diǎn)之間的通信.網(wǎng)絡(luò)節(jié)點(diǎn)部署完成后，節(jié)點(diǎn)以廣播的方式向網(wǎng)絡(luò)發(fā)送報文，通過式(5)計(jì)算節(jié)點(diǎn)之間的距離.基站收集網(wǎng)絡(luò)中節(jié)點(diǎn)間的距離信息和節(jié)點(diǎn)的剩余能量信息后，通過ABC算法選擇網(wǎng)絡(luò)中的簇首節(jié)點(diǎn)，該計(jì)算過程是在基站內(nèi)部完成.確定網(wǎng)絡(luò)中的簇首節(jié)點(diǎn)后，按照節(jié)點(diǎn)間的距離大小和節(jié)點(diǎn)剩余能量大小把網(wǎng)絡(luò)中其他節(jié)點(diǎn)分配給各個簇，然后利用Dijkstra算法以簇首節(jié)點(diǎn)為樹根在各個簇內(nèi)建立最短路徑樹路由表，基站將各個簇對應(yīng)的樹路由表發(fā)送給簇首節(jié)點(diǎn)，最后在各個簇內(nèi)構(gòu)建最短路徑樹.算法的主流程圖如圖1所示.

圖1 算法主要流程

3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)是在理想情況下進(jìn)行，假設(shè)節(jié)點(diǎn)在數(shù)據(jù)發(fā)送過程中不存在丟包現(xiàn)象，不考慮數(shù)據(jù)傳輸過程中重發(fā)、出錯以及計(jì)算消耗的能量.建立Matlab環(huán)境，對協(xié)議進(jìn)行仿真，設(shè)傳感器節(jié)點(diǎn)個數(shù)為100，傳感區(qū)域?yàn)?00 m×300 m，節(jié)點(diǎn)隨機(jī)分布在傳感區(qū)域中，基站位置分別為(300，150)，節(jié)點(diǎn)初始能量為0.5 J，其他參數(shù)與文獻(xiàn)[13]中仿真參數(shù)相同.在簇首節(jié)點(diǎn)的選舉和簇首節(jié)點(diǎn)與簇內(nèi)節(jié)點(diǎn)的通信兩方面與LEACH協(xié)議，分別作了比較.

圖2描述的是ABCCR算法與經(jīng)典的LEACH協(xié)議關(guān)于網(wǎng)絡(luò)中存活節(jié)點(diǎn)總數(shù)隨著時間變化的關(guān)系圖.

圖2 ABCCR算法與LEACH存活節(jié)點(diǎn)數(shù)比較

從圖2可以看出：ABCCR算法中節(jié)點(diǎn)存活的時間明顯比LEACH協(xié)議中節(jié)點(diǎn)存活的時間長.在網(wǎng)絡(luò)運(yùn)行到700輪左右的時候，LEACH協(xié)議中80%左右的節(jié)點(diǎn)已經(jīng)失效，無法提供有價值的信息，意味著網(wǎng)絡(luò)已經(jīng)癱瘓.而此時ABCCR中還剩下大約60%的節(jié)點(diǎn)，網(wǎng)絡(luò)仍能運(yùn)行正常.相對于LEACH協(xié)議，ABCCR算法構(gòu)造出基于節(jié)點(diǎn)間距離信息和節(jié)點(diǎn)剩余能量信息的適應(yīng)度函數(shù)，應(yīng)用于無線傳感器網(wǎng)絡(luò)的分簇過程，能夠減緩節(jié)點(diǎn)失效的速度，延長了網(wǎng)絡(luò)的壽命.

為了進(jìn)一步說明ABCCR算法的特性，對基站位于分布區(qū)域的中心位置(150，150)的情況進(jìn)行實(shí)驗(yàn)，仿真結(jié)果如圖3所示.

圖3 基站位于分布區(qū)域中心時ABCCR算法與LEACH存活節(jié)點(diǎn)數(shù)比較

由圖3可以看出：此時LEACH協(xié)議表現(xiàn)出較好的性能，只是略差于ABCCR算法.這是因?yàn)楫?dāng)基站在網(wǎng)絡(luò)的中心位置時，基站與網(wǎng)絡(luò)中的簇首節(jié)點(diǎn)的距離較近，即使簇首節(jié)點(diǎn)在網(wǎng)絡(luò)中分布不均，與基站通信消耗的能量也不會太多.對比圖2，3：對于基站位于網(wǎng)絡(luò)的邊緣和位于網(wǎng)絡(luò)中心兩種情況，LEACH協(xié)議的存活節(jié)點(diǎn)數(shù)目變化非常大；而ABCCR算法對于這兩種情況所表現(xiàn)出的性能差別不大.這說明ABCCR算法能夠根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)的不同，合理的對網(wǎng)絡(luò)進(jìn)行分簇，從而達(dá)到減少網(wǎng)絡(luò)的能量消耗的效果.

圖4描述的是ABCCR-SPT算法、ABCCR算法及LEACH關(guān)于網(wǎng)絡(luò)中存活節(jié)點(diǎn)總數(shù)隨著時間變化的關(guān)系圖.從圖4中可以看出：ABCCR-SPT算法在存活節(jié)點(diǎn)數(shù)目上略優(yōu)于ABCCR算法，表明在簇內(nèi)構(gòu)建以簇首節(jié)點(diǎn)為根的最短路徑樹，能夠優(yōu)化簇內(nèi)節(jié)點(diǎn)通信的能量消耗，保證網(wǎng)絡(luò)中節(jié)點(diǎn)存活的時間更長.

圖4 三種算法存活節(jié)點(diǎn)數(shù)比較

4 結(jié) 論

針對LEACH協(xié)議在選擇簇首節(jié)點(diǎn)時存在的不足，對人工蜂群算法進(jìn)行研究，根據(jù)Friis自由空間方程式推導(dǎo)出了人工蜂群算法中的適應(yīng)度函數(shù)，并應(yīng)用于無線傳感器網(wǎng)絡(luò)中簇首節(jié)點(diǎn)的選擇.另外，結(jié)合圖論中的最短路徑思想，提出在簇首節(jié)點(diǎn)確定后，以簇首節(jié)點(diǎn)為樹根最短路徑樹，盡可能的保證每個簇內(nèi)節(jié)點(diǎn)與簇首節(jié)點(diǎn)通信所消耗的能量最少，從而優(yōu)化了簇內(nèi)節(jié)點(diǎn)間通信的能量消耗.仿真結(jié)果表明：所提出的協(xié)議在降低網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗和延長網(wǎng)絡(luò)的生命周期方面比傳統(tǒng)的LEACH協(xié)議有了較大的改善.

參考文獻(xiàn)：

[1] 周曉，李杰，邊裕挺．基于無線傳感器網(wǎng)絡(luò)的環(huán)境溫度監(jiān)測系統(tǒng)設(shè)計(jì)[J]．浙江工業(yè)大學(xué)學(xué)報，2013，41(4):440-443．

[2] 周曉，邊裕挺，李杰．基于Android智能終端的WSN監(jiān)控系統(tǒng)[J]．浙江工業(yè)大學(xué)學(xué)報，2013，41(5):558-561．

[3] 陸歡佳，俞立，董齊芬，等．基于無線傳感器網(wǎng)絡(luò)的樓宇環(huán)境監(jiān)測系統(tǒng)設(shè)計(jì)[J]．浙江工業(yè)大學(xué)學(xué)報，2011，39(6):684-687．

[4] 楊淑瑩，張樺．群體智能與仿生計(jì)算—Matlab技術(shù)實(shí)現(xiàn)[M]．北京：電子工業(yè)出版社，2012．

[5] SALEEM M, GIANNI A, FAROOQ M, et al. Swarm intelligence based routing protocol for wireless sensor networks: survey and future directions[J]. Information Sciences,2011，181(20):4597-4624.

[6] KENNEDY J, EBERHART R．Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks．Perth: IEEE Neural Networks,1995:1942-1948．

[7] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]．IEEE Transaction on Evolutionary Computation,1997,1(1):53-66.

[8] 李曉磊.一種新型的智能優(yōu)化方法—人工魚群算法[D]．杭州：浙江大學(xué)，2003．

[9] PASSINO K M．Biomimicry of bacterial foraging for distributed optimization and control[J]. IEEE Control Systems Magazine,2002,22(3):52-67.

[10] KARABOGA D．An idea based on honey bee swarm for numerical optimization[R]. Kayseri: Computer Engineering Department of Erciyes University,2005.

[11] DELAVA A G, JAVIZ E. A routing algorithm based on bee colony for energy consumption reduction in wireless relay networks[J]. International Journal of Ad Hoc, Sensor & Ubiquitous Computing，2012,3(4)：1-9.

[12] KARABOG D, OKDEM S, OZTURK C. Cluster based wireless sensor network routing using artificial bee colony algorithm[J]. Wireless Networks,2012,18(7):847-860.

[13] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]// Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Maui: Western Periodicals Company,2000:1-10.