基于BP神經(jīng)網(wǎng)絡(luò)和蟻群的WSN分簇算法的研究

王改云++胡錦艷

摘 要： 在研究經(jīng)典低能量自適應(yīng)分簇路由算法的基礎(chǔ)上，提出基于BP神經(jīng)網(wǎng)絡(luò)和蟻群的無線傳感器網(wǎng)絡(luò)分簇路由算法。在分簇階段將BP神經(jīng)網(wǎng)絡(luò)應(yīng)用于每個(gè)分簇結(jié)構(gòu)中，把采集的大量信息通過設(shè)計(jì)好的神經(jīng)網(wǎng)絡(luò)模型融合得到反映原始數(shù)據(jù)特征的少量數(shù)據(jù)信息。在數(shù)據(jù)傳遞階段將蟻群算法應(yīng)用到簇間路由機(jī)制中，尋找簇頭到基站的最佳路徑。將融合后的數(shù)據(jù)通過優(yōu)化的路徑傳送到匯聚節(jié)點(diǎn)。仿真結(jié)果表明，該算法和LEACH算法相比，有效地均衡了網(wǎng)絡(luò)的能量消耗，并延長了網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)； 蟻群算法； 神經(jīng)網(wǎng)絡(luò)； 數(shù)據(jù)匯聚

中圖分類號(hào)： TN711?34； TP183 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）17?0045?04

Research on WSN clustering algorithm based on BP neural network

and ant colony algorithm

WANG Gaiyun， HU Jinyan

（Guilin University of Electronic Technology， Guilin 541004， China）

Abstract： On the basis of studying the classic low energy adaptive clustering hierarchy （LEACH） algorithm， the clustering routing algorithm of wireless sensor network （WSN） based on BP neural network and ant colony algorithm （ACA） is proposed. In clustering stage， BP neural network is applied to each clustering structure， and a large amount of acquired information is transited to the designed BP neural network model. A little data information reflecting original data features is obtained by fusion. In data transmission stage， ACA is applied to inter?cluster routing mechanism to search the optimal path from the cluster head to the base station. The fused data is transited to clustering node through the optimized path. The simulation results indicate that in comparison with LEACH algorithm， the proposed algorithm can balance network energy consumption effectively， and lengthen the network life cycle.

Keywords： wireless sensor network； ant colony algorithm； neural network； data clustering

0 引 言

在無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）中，由于傳感器網(wǎng)絡(luò)上節(jié)點(diǎn)能量有限，且不能更換電池，因此如何合理高效地使用能源，盡可能多地延長網(wǎng)絡(luò)的生命周期，成為傳感器網(wǎng)絡(luò)研究的核心問題之一[1]。在無線傳感器網(wǎng)絡(luò)中，研究的重點(diǎn)問題是通信模塊的節(jié)能，而網(wǎng)絡(luò)路由是實(shí)現(xiàn)網(wǎng)絡(luò)高效通信的基礎(chǔ)，所以把重點(diǎn)放在路由算法的研究上。

在設(shè)計(jì)路由協(xié)議時(shí)，考慮均勻使用節(jié)點(diǎn)能量和數(shù)據(jù)融合這兩點(diǎn)[2]。在分簇層次結(jié)構(gòu)中，簇首節(jié)點(diǎn)對(duì)其負(fù)責(zé)區(qū)域的數(shù)據(jù)進(jìn)行融合，然后將有用的信息轉(zhuǎn)發(fā)給匯聚節(jié)點(diǎn)。無線傳感器網(wǎng)絡(luò)在傳感器節(jié)點(diǎn)感知處理數(shù)據(jù)方面相當(dāng)于神經(jīng)網(wǎng)絡(luò)的神經(jīng)元，二者有著類似的功能，再利用傳感器節(jié)點(diǎn)的路由選擇過程和蟻群算法螞蟻的覓食尋優(yōu)行為有著極大的相似性，而且蟻群算法具有自組織、自適應(yīng)、并行搜索等特點(diǎn)，使用蟻群優(yōu)化設(shè)計(jì)WSN。近幾年來，研究人員開展了很多把神經(jīng)網(wǎng)絡(luò)算法和蟻群算法等應(yīng)用到無線傳感器網(wǎng)絡(luò)的研究。文獻(xiàn)[3]提出了將神經(jīng)網(wǎng)絡(luò)的層次結(jié)構(gòu)應(yīng)用到無線傳感器網(wǎng)絡(luò)的分簇結(jié)構(gòu)中，構(gòu)造一個(gè)基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)融合模型，很好地降低了網(wǎng)絡(luò)的傳輸能耗，延長了網(wǎng)絡(luò)生命周期。文獻(xiàn)[4]提出基于蟻群和遺傳算法相結(jié)合的路徑優(yōu)化方法，有效延長了網(wǎng)絡(luò)的生命周期。文獻(xiàn)[5]為大規(guī)?；诖氐臒o線傳感器網(wǎng)絡(luò)提供了一個(gè)有效的路由算法（ERC）。采用兩層路由，在第一層用LEACH算法選擇簇首，第二層通過蟻群算法（ACO），找到一條最佳去匯聚節(jié)點(diǎn)的路徑，只有簇頭參與簇內(nèi)路由。文獻(xiàn)[6]先采用模糊理論的簇頭選舉算法，根據(jù)能量、通信范圍、計(jì)算能力和鄰居節(jié)點(diǎn)數(shù)等因素采用模糊綜合評(píng)判法推選簇首；然后在分簇的基礎(chǔ)上，采用蟻群算法建立最佳路由。文獻(xiàn)[7]通過將節(jié)點(diǎn)能量水平和傳輸距離引入ACO的信息素增量公式，使ACO較好地適應(yīng)于WSN的路由協(xié)議。但是，該算法沒有考慮全網(wǎng)能量均衡使用的問題。

本文通過在經(jīng)典路由算法LEACH的分簇階段引入BP神經(jīng)網(wǎng)絡(luò)，在數(shù)據(jù)傳輸階段引入蟻群算法，提出一種新的基于BP神經(jīng)網(wǎng)絡(luò)和蟻群的BPACA分簇算法，該算法有效地延長了網(wǎng)絡(luò)的生命周期。

1 通信能量消耗模型

本文采用與LEACH算法相同的無線通信能量消耗模型[8]，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都是同構(gòu)的且能量有限，同時(shí)每個(gè)節(jié)點(diǎn)都有惟一標(biāo)識(shí)（ID）。節(jié)點(diǎn)發(fā)送[l]b的數(shù)據(jù)能量消耗由發(fā)射損耗和功率放大損耗兩部分組成，發(fā)送的能量消耗如下：

[ETxl，d=lEelec+lεfsd2，d

接收的能量消耗：

[ERxl=lEelec] （2）

式中：[Eelec]為發(fā)送或接收的功耗，當(dāng)傳輸距離小于閾值[d0]時(shí)，功率放大損耗采用的是自由能量模型；當(dāng)傳輸距離大于[d0] 時(shí)，功率放大損耗則采用多路徑衰減模型，其中相應(yīng)的參數(shù)[εfs]和[εmp]表示的是上述兩種情況下單位功率放大時(shí)需要的能量。

2 基于BP神經(jīng)網(wǎng)絡(luò)和蟻群算法的路由算法

2.1 算法的基本思想

經(jīng)典的路由算法通常分成三個(gè)階段：簇首選舉、簇形成和數(shù)據(jù)傳輸。節(jié)點(diǎn)分為簇首節(jié)點(diǎn)和簇成員節(jié)點(diǎn)兩種。簇成員節(jié)點(diǎn)把數(shù)據(jù)傳輸給簇首，簇首負(fù)責(zé)數(shù)據(jù)的收集、處理和簇間傳輸。

本文對(duì)無線傳感器網(wǎng)絡(luò)路由LEACH算法進(jìn)行分階段改進(jìn)，在簇首選舉階段采用BP神經(jīng)網(wǎng)絡(luò)算法對(duì)其進(jìn)行優(yōu)化處理，即在簇首節(jié)點(diǎn)和成員節(jié)點(diǎn)之間利用BP神經(jīng)網(wǎng)絡(luò)算法對(duì)采集到的原始數(shù)據(jù)進(jìn)行融合，融合傳感器節(jié)點(diǎn)傳遞給簇首的信息，再將信息傳遞給匯聚節(jié)點(diǎn)；在簇間傳遞階段，采用與蟻群算法相結(jié)合的方法，由于蟻群算法和無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的結(jié)構(gòu)十分相似，有并行計(jì)算等優(yōu)點(diǎn)，故使用蟻群算法在此階段進(jìn)行優(yōu)化，整體達(dá)到延長網(wǎng)絡(luò)周期的目的。本算法的流程如圖1所示。

2.2 算法的實(shí)現(xiàn)過程

2.2.1 簇內(nèi)路由階段

簇內(nèi)路由階段包括簇首選舉階段和簇形成階段。先對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行初始化，按照LEACH協(xié)議挑選簇首，簇首挑選穩(wěn)定后，簇首節(jié)點(diǎn)把所有簇內(nèi)節(jié)點(diǎn)的相關(guān)信息發(fā)送給匯聚節(jié)點(diǎn)。在此過程引入BPDF（BPNN Data Fusion）算法[9]，該算法是在簇首節(jié)點(diǎn)和簇成員節(jié)點(diǎn)之間使用BP神經(jīng)網(wǎng)絡(luò)對(duì)數(shù)據(jù)進(jìn)行融合運(yùn)算。先分簇，然后將各傳感器節(jié)點(diǎn)檢測(cè)到的數(shù)據(jù)發(fā)送到它們所在區(qū)域內(nèi)的簇首節(jié)點(diǎn)，該算法的結(jié)構(gòu)和無線傳感器網(wǎng)絡(luò)中的一個(gè)簇相對(duì)應(yīng)。輸入層設(shè)于簇成員節(jié)點(diǎn)中，隱含層和輸出層均設(shè)于簇首節(jié)點(diǎn)中。BPDF算法的模型結(jié)構(gòu)如圖2所示。

在輸入層，對(duì)采集到的數(shù)據(jù)進(jìn)行初步處理，然后等處理后的信息到達(dá)簇首節(jié)點(diǎn)后，再用隱含層和輸出層對(duì)其做進(jìn)一步處理。最后，簇首節(jié)點(diǎn)再將處理的結(jié)果發(fā)送給匯聚節(jié)點(diǎn)。BPDF算法選擇在無線傳感器網(wǎng)絡(luò)匯聚節(jié)點(diǎn)完成對(duì)神經(jīng)網(wǎng)絡(luò)的訓(xùn)練。

BPDF算法的實(shí)現(xiàn)步驟如下：

Step1：首先網(wǎng)絡(luò)初始化，然后分簇并且選舉簇首節(jié)點(diǎn)，簇首負(fù)責(zé)將采集到的信息進(jìn)行傳遞、發(fā)送。

Step2：由Sink節(jié)點(diǎn)針對(duì)簇首、簇成員節(jié)點(diǎn)信息構(gòu)建BP神經(jīng)網(wǎng)絡(luò)。

Step3：應(yīng)用BP神經(jīng)網(wǎng)絡(luò)查找此樣本庫，并訓(xùn)練與簇成員的信息相搭配的樣本獲得簇的BP神經(jīng)網(wǎng)絡(luò)的有關(guān)參數(shù)。

Step4：Sink節(jié)點(diǎn)把所有神經(jīng)元參數(shù)傳遞到對(duì)應(yīng)的簇首簇成員節(jié)點(diǎn)中。

Step5：分簇穩(wěn)定后，簇首把接收的信息完成融合。

Step6：簇首向Sink節(jié)點(diǎn)輸送融合后的數(shù)據(jù)，在WSN運(yùn)行中出現(xiàn)的有關(guān)數(shù)據(jù)也可增加到樣本庫。

2.2.2 簇間路由階段

在完成簇內(nèi)路由階段后，進(jìn)入簇間路由階段，也就是數(shù)據(jù)傳輸階段。在簇首將數(shù)據(jù)傳輸?shù)絊ink階段，簇首會(huì)將數(shù)據(jù)以多跳的通信方式發(fā)到Sink節(jié)點(diǎn)，在此采用蟻群算法建立最佳路由。以TSP問題為例，蟻群算法的結(jié)構(gòu)流程圖如圖3所示。

實(shí)現(xiàn)過程為：首先初始化蟻群，根據(jù)狀態(tài)轉(zhuǎn)移概率公式計(jì)算的概率選擇下一跳元素，修改禁忌表，根據(jù)信息素公式進(jìn)行局部和全局的更新，滿足條件結(jié)束。

在BPACA算法中具體實(shí)現(xiàn)過程如下：

（1） 在每個(gè)簇首節(jié)點(diǎn)上放置[k]只螞蟻，設(shè)置矩陣并初始化。每個(gè)螞蟻都有自己的內(nèi)存表，用Tabu存儲(chǔ)并記錄路徑的生成，用禁忌表 A_citys存儲(chǔ)已經(jīng)過的節(jié)點(diǎn)，以后搜索中不能訪問這些節(jié)點(diǎn)，用allowk存儲(chǔ)允許訪問的節(jié)點(diǎn)。

（2） 由公式（3）計(jì)算出轉(zhuǎn)移概率[pij，]螞蟻按照此概率轉(zhuǎn)移到下一個(gè)訪問的簇首節(jié)點(diǎn)上，將已經(jīng)訪問過的節(jié)點(diǎn)添加到禁忌表中，禁止訪問。重復(fù)步驟（2），直到每個(gè)簇首上的[k]只螞蟻都訪問到 Sink節(jié)點(diǎn)。[pkij=（τij）α（ηij）βj∈allowk（τij）α（ηij）β] （3）

[ηij（t）=1D（i，j）] （4）

[τij=τ′ij+E1α1+Lα2] （5）

式中：[α]和[β]為控制信息素和兩簇首之間距離的權(quán)重系數(shù)；[τij]為鏈接路徑上的信息素濃度；[ηij（t）]為簇首節(jié)點(diǎn)[i]到[j]的啟發(fā)值[。][E1]表示其相鄰簇首節(jié)點(diǎn)的剩余能量；[L]表示其相鄰簇首節(jié)點(diǎn)與基站的距離；[α1，][α2]是其相鄰簇首節(jié)點(diǎn)能量和基站距離所占的比重。

（3） 信息素的更新，從[k]只螞蟻中挑選出耗能少且路徑短的螞蟻，即[E1]大，[L]小，對(duì)其按照公式（5）進(jìn)行信息素的更新。重復(fù)步驟（2）和（3），直到所有的簇首節(jié)點(diǎn)都找到自己到 Sink的最佳路徑。

（4） 當(dāng)簇首節(jié)點(diǎn)的能量減少到比發(fā)送距離為[d0]的數(shù)據(jù)所消耗的能量還小時(shí)，進(jìn)入下一輪的循環(huán)[10]。

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 性能參數(shù)

本文采用與文獻(xiàn)[8]中相同的無線能量模型，無線發(fā)射模塊可以根據(jù)節(jié)點(diǎn)間的距離遠(yuǎn)近，控制發(fā)射功率大小或者自動(dòng)關(guān)閉，以避免接收到不需要的數(shù)據(jù)。仿真工具采用Matlab，具體的仿真環(huán)境和參數(shù)為：在100 m×100 m的正方形區(qū)域內(nèi)隨機(jī)布撒100個(gè)節(jié)點(diǎn)，初始能量為0.02 J，基站坐標(biāo)為（50，50），[Eelec=]50 nJ/b，[εfs=]10 pJ/（b·m2），[εmp=]0.001 3 pJ/（b·m4），[EDA=]5 nJ/b，[p=]0.1，packetLength=4 000。

3.2 仿真結(jié)果分析

為了驗(yàn)證該算法的性能，將BPACA和LEACH在節(jié)點(diǎn)存活數(shù)和網(wǎng)絡(luò)能耗兩方面進(jìn)行了仿真對(duì)比。如圖4所示，LEACH在第230輪出現(xiàn)節(jié)點(diǎn)死亡，而本算法是在接近第600輪出現(xiàn)節(jié)點(diǎn)死亡；LEACH對(duì)應(yīng)半數(shù)節(jié)點(diǎn)死亡的時(shí)間在第600輪左右，而本算法在第950輪左右；LEACH節(jié)點(diǎn)全部死亡在第1 100輪，而本算法在1 600輪左右。通過將本文路由算法和LEACH算法相比，可知本文算法較好地均衡了網(wǎng)絡(luò)能耗，節(jié)省了節(jié)點(diǎn)的消耗，高效地利用了網(wǎng)絡(luò)中有限的能量。

圖4 兩種協(xié)議存活節(jié)點(diǎn)比較圖

網(wǎng)絡(luò)能量消耗如圖5所示，從圖中可以看出，隨著實(shí)驗(yàn)的進(jìn)行，能量消耗都在顯著增加，在第1 000輪左右，LEACH算法的能量全部消耗完，而改進(jìn)的算法是在第1 600輪左右才全部耗盡。由此可以看出，改進(jìn)的算法有效地減少了網(wǎng)絡(luò)的能量消耗，從而延長了網(wǎng)絡(luò)的生命周期。

圖5 兩種協(xié)議網(wǎng)絡(luò)總能耗比較

4 結(jié) 語

本文結(jié)合LEACH算法，將神經(jīng)網(wǎng)絡(luò)算法應(yīng)用到分簇階段，將蟻群算法應(yīng)用到簇間路由機(jī)制中，提出一種基于神經(jīng)網(wǎng)絡(luò)和蟻群算法的無線傳感器網(wǎng)絡(luò)分簇路由算法。仿真結(jié)果表明，該算法在節(jié)點(diǎn)存活方面和節(jié)點(diǎn)能量消耗方面有了顯著改善，達(dá)到了降低系統(tǒng)能耗的目的，延長了網(wǎng)絡(luò)生存周期。但是還存在不足之處，還可以用優(yōu)化的蟻群算法進(jìn)行結(jié)合，獲得更理想的結(jié)果。

參考文獻(xiàn)

[1] 孫利民.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[2] 楊洋.一種基于LEACH的無線傳感器網(wǎng)絡(luò)路由協(xié)議[D].成都：電子科技大學(xué)，2006.

[3] 俞黎陽，王能，張衛(wèi).無線傳感器網(wǎng)絡(luò)中基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)融合模型[J].計(jì)算機(jī)科學(xué)，2009，35（12）：43?47.

[4] 莫桂江.蟻群?遺傳算法的無線傳感器網(wǎng)絡(luò)路徑優(yōu)化[J].微電子學(xué)與計(jì)算機(jī)，2011，28（9）：139?142.

[5] 陳宇.基于改進(jìn)蟻群算法的無線傳感器網(wǎng)絡(luò)路由的研究[D].廣州：華南理工大學(xué)，2012.

[6] 張海娟.基于蟻群算法的無線傳感器網(wǎng)絡(luò)分簇路由算法[D].西安：西北大學(xué)，2010.

[7] CAMILO T， CARRETO C， SILVA J S， et al. An energy?efficient ant?based routing algorithm for wireless sensor networks [C]// Proceedings of 2006 the 5th International Workshop on Ant Colony Optimization and Swarm Intelligence. Brussels： Springer， 2006： 49?59.

[8] HEINZELMAN W R， KULIK J， BALAKRISHNAN H. Adaptive protocols for information dissemination in wireless sensor networks [C]// Proceedings of 2001 the 5th Annual International Conference on Mobile Computing and Networking. New York： ACM， 2001： 174?185.

[9] 孔玉靜，侯鑫，華爾天，等.基于BP神經(jīng)網(wǎng)絡(luò)的無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究[J].傳感技術(shù)學(xué)報(bào)，2013，26（2）：246?251.

[10] 王桂鳳，王勇，陶曉玲.基于蟻群的無線傳感器網(wǎng)絡(luò)分簇路由算法[J].計(jì)算機(jī)工程，2010，36（18）：73?75.