PSO結(jié)合SA優(yōu)化算法的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議＊

楊建輝， 吳 聰

（1.周口師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 周口466001；2.周口師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 周口466001）

無(wú)線傳感器網(wǎng)絡(luò)（WSN）是由多個(gè)靜態(tài)傳感器組成，通過無(wú)線介質(zhì)連接，執(zhí)行物理世界的分布式感知［1］.WSN中傳感器節(jié)點(diǎn)容易部署，但其功率和帶寬資源比較稀缺，所以在設(shè)計(jì)WSN的運(yùn)作協(xié)議時(shí)，需要考慮這些因素［2］.將網(wǎng)絡(luò)構(gòu)建成分簇結(jié)構(gòu)是延長(zhǎng)網(wǎng)絡(luò)壽命的有效方法之一［3］.目前典型的用于延長(zhǎng)網(wǎng)絡(luò)壽命的分簇協(xié)議為：低功耗自適應(yīng)分層分簇（LEACH）協(xié)議，然而該協(xié)議也存在很多缺點(diǎn).對(duì)此，［4］提出一種能量感知的LEACH協(xié)議：LEACH－EP，該協(xié)議中，具有較多能量的節(jié)點(diǎn)有更多機(jī)會(huì)成為簇頭（CH），并根據(jù)期望節(jié)點(diǎn)成為CH的百分比、當(dāng)前剩余能量和上一輪所有CHs的平均剩余能量來(lái)計(jì)算能量閾值，該協(xié)議比LEACH提高了33%的網(wǎng)絡(luò)壽命.為了優(yōu)化傳統(tǒng)LEACH構(gòu)建的簇頭表，獲得最佳分簇方案，基于群智能的方法已經(jīng)應(yīng)用到WSN中.［5］提出一種使用遺傳算法（GA）對(duì)WSN進(jìn)行優(yōu)化，利用LEACH算法構(gòu)建初始簇頭表，使用GA進(jìn)行高效搜索找到近似最優(yōu)解，以此來(lái)提高 WSN的壽命，然而其容易陷入局部最優(yōu)解.［6］根據(jù)剩余能量、節(jié)點(diǎn)連通度以及當(dāng)選CH的總時(shí)間進(jìn)行簇頭選舉，并利用模擬退火（SA）算法來(lái)優(yōu)化調(diào)整所有節(jié)點(diǎn)，直到所有聚類的能耗趨近均衡.然而，SA進(jìn)行全局搜索的時(shí)間較長(zhǎng).

本文提出一種融合粒子群優(yōu)化（PSO）和模擬退火（SA）優(yōu)化的WSN分簇協(xié)議，綜合考慮多項(xiàng)節(jié)點(diǎn)因素來(lái)進(jìn)行分簇，并通過提出的PSO－SA算法對(duì)多項(xiàng)參數(shù)進(jìn)行優(yōu)化，自適應(yīng)調(diào)整參數(shù)值，以此獲得最適合的分簇結(jié)構(gòu).實(shí)驗(yàn)結(jié)果表明，本文方法在網(wǎng)絡(luò)壽命和網(wǎng)絡(luò)延遲方面具有較好的性能.

1 分簇協(xié)議

1.1 簇頭選舉

LEACH協(xié)議中簇頭（CH）選舉沒有考慮節(jié)點(diǎn)的剩余能量和在網(wǎng)絡(luò)中的位置等因數(shù)［7］.因此本文對(duì)此進(jìn)行改進(jìn)，在分簇協(xié)議中考慮了多種傳感器節(jié)點(diǎn)因素來(lái)計(jì)算選舉CH的閾值，分別為：距Sink節(jié)點(diǎn)的距離、剩余能量、先前成為CH的次數(shù)、距其他CH的距離，分別表示為子閾值項(xiàng)T1到T4，節(jié)點(diǎn)的CH選舉閾值TASLPR（n）計(jì)算如下：

式中，Z（n）＝α1T1（n）＋α2T2（n）＋α3T3（n）＋α4T4（n），α1、α2、α3和α4為用于調(diào)整多項(xiàng)閾值TASLPR（n）中4個(gè)子閾值項(xiàng)影響能力的加權(quán)系數(shù)，其中為閾值參數(shù).4個(gè)子閾值表達(dá)式分別表示如下：

式中，N為網(wǎng)絡(luò)中存活的傳感器節(jié)點(diǎn)數(shù)量，P為期望節(jié)點(diǎn)成為CHs的概率，E（n）為節(jié)點(diǎn)n的當(dāng)前剩余能量，dsink（n）為從節(jié)點(diǎn)n到Sink節(jié)點(diǎn)的距離，dch（j，i）為節(jié)點(diǎn)i和CH節(jié)點(diǎn)j之間的距離，Nch（n）為節(jié)點(diǎn)n被選作CH節(jié)點(diǎn)的總輪數(shù)，M為當(dāng)前輪中已經(jīng)被選作CHs的節(jié)點(diǎn)數(shù)，此外，t2和t3為兩個(gè)閾值常量參數(shù).

1.2 分簇過程

在建立階段，每個(gè)傳感器節(jié)點(diǎn)n從0和1之間選擇一隨機(jī)數(shù)，如果其隨機(jī)數(shù)小于本文提出的多項(xiàng)式閾值TASLPR（n），則節(jié)點(diǎn)n在本輪作為CH.CHs選擇之后，將自己為CH的信息廣播給網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn).非CH節(jié)點(diǎn)接收到通知，則會(huì)選擇一個(gè)具有最小通信距離的CH來(lái)作為它的聚類［8］.

2 PSO－SA算法優(yōu)化分簇參數(shù)

2.1 問題描述

本文分簇協(xié)議中利用多種傳感器節(jié)點(diǎn)參數(shù)來(lái)選舉CHs，共有7個(gè)可控參數(shù)，包括：α1、α2、α3、α4、t1、t2和t3，改變這些參數(shù)會(huì)使分簇結(jié)構(gòu)具有不同的性能，因此，分簇協(xié)議需要能夠自適應(yīng)調(diào)整這些參數(shù)，使其可以在各種應(yīng)用程序下良好運(yùn)行.例如，如果設(shè)置α1＝1，t2＝0.5、α2＝α3＝α4＝t1＝t3＝0，則提出的協(xié)議與LEACH－EP類似.協(xié)議中，每個(gè)α1必須在［0.1］范圍內(nèi)，每個(gè)tj需在［0.2］范圍內(nèi)，本文使用二進(jìn)制編碼，為了實(shí)現(xiàn)0.01的分辨率，所以對(duì)每個(gè)αk的編碼需要7個(gè)比特位，每個(gè)ts需要8個(gè)比特位.這樣，可行解則可表示為長(zhǎng)度為L(zhǎng)的二進(jìn)制字符串，其中L＝52，可行解的實(shí)例如圖1所示.包括所有可能解的整個(gè)搜索空間的大小為2L，因此，要尋找出最優(yōu)解是一種NP困難問題.本文中，運(yùn)用一種混合PSO和SA算法來(lái)優(yōu)化可控參數(shù)，尋找出最優(yōu)參數(shù)解.

2.2 適應(yīng)度函數(shù)

WSN中，網(wǎng)絡(luò)壽命的定義根據(jù)不同的應(yīng)用要求有不同標(biāo)準(zhǔn)，包括第一節(jié)點(diǎn)死亡（FND），50%節(jié)點(diǎn)死亡（HND）和最后節(jié)點(diǎn)死亡（LND）等［14］.

協(xié)議中的適應(yīng)度函數(shù)應(yīng)該基于應(yīng)用程序指標(biāo)來(lái)定義，為了評(píng)估提出的分簇協(xié)議，本文適應(yīng)度函數(shù)及其約束定義如下：

式中，w1至w3為三個(gè)常量權(quán)重，用于調(diào)整提出的成本函數(shù)中三個(gè)目標(biāo)項(xiàng)的相對(duì)重要性.如果應(yīng)用程序中僅需要考慮FND情況，則設(shè)置w1＝1和w2＝w3＝0.

2.3 PSO－SA優(yōu)化算法

本文利用粒子群優(yōu)化（PSO）和模擬退火（SA）的混合算法來(lái)優(yōu)化分簇協(xié)議的可控參數(shù)，使分簇協(xié)議能夠自適應(yīng)調(diào)整其參數(shù)，以便獲得最佳性能.PSO算法是一種基于群體智能的隨機(jī)優(yōu)化算法，粒子群中的每一個(gè)粒子代表一種可行解，粒子在整個(gè)解空間中運(yùn)動(dòng)，逐漸向最優(yōu)個(gè)體靠攏，最終找出最優(yōu)解［10］.SA算法是一種元啟發(fā)式優(yōu)化算法，基于物理退火過程與組合優(yōu)化之間的相似性來(lái)尋找最優(yōu)解.PSO算法收斂速度快，但是收斂精度低.SA算法以一定概率接受較差點(diǎn)，所以其具有能跳出局部最優(yōu)的能力，但搜索時(shí)間長(zhǎng).因此，本文將這兩種算法相結(jié)合.首先，執(zhí)行PSO在搜索空間進(jìn)行全局搜索，然后將PSO獲得的個(gè)體最優(yōu)解作為SA的初始解，SA進(jìn)行局部搜索從而找到最終解.混合PSO－SA算法用于分簇協(xié)議優(yōu)化的整體流程圖如圖2所示，其算法執(zhí)行步驟如下：

步驟1：初始化粒子群，包括每個(gè)粒子的位置和速度，設(shè)置當(dāng)前迭代次數(shù)tPSO＝1和最大迭代次數(shù)max＿iterPSO，確定種群大小N和粒子維度D.

步驟2：計(jì)算每個(gè)粒子的適應(yīng)度值，產(chǎn)生粒子的個(gè)體最優(yōu)解和全局最優(yōu)解.

步驟3：判斷全局最優(yōu)解是否停滯或達(dá)到指定的迭代次數(shù).

步驟4：將PSO獲得的最優(yōu)解作為SA的初始解，設(shè)置初始溫度Tinitial，最終溫度Tfinal.在當(dāng)前解（solutioncurrent）鄰域內(nèi)生成新解（solutionnew）.

步驟5：計(jì)算兩個(gè)解的適應(yīng)度并根據(jù)準(zhǔn)則更新解.如果Enew＜Ecurrent，則用新解替換當(dāng)前解；如果Enew＞Ecurrent，則以概率Pw＝exp（－ （ΔE）／T）接 收 新 解，其 中，ΔE＝Enew－Ecurrent.注意，Enew和Ecurrent分別為solutionnew和solutioncurrent的成本值，其中E＝1／fitness.

步驟6：判斷是否達(dá)到要求，若不滿足則降溫，返回步驟5，直到獲得最終解或達(dá)到最低溫度.

SA算法執(zhí)行過程中，溫度T從Tinitial（初始溫度）線性降低到Tfinal（最終溫度），tSA和max＿iterSA分別為當(dāng)前迭代和定義的SA最大迭代次數(shù).當(dāng)Enew＞Ecurrent時(shí)，若T＝0，則意味著不能接受新解.T越大，接收較差解的概率越高.SA中使用二進(jìn)制交換算子進(jìn)行局部搜索，其中，改變基因的概率設(shè)為Pchange，使用自適應(yīng)局部搜索策略來(lái)提高SA的收斂性.執(zhí)行算法過程中Pchange從線性降低至，Pchange越大，相比與solutioncurrent，solutionnew中變化越多.

3 實(shí)驗(yàn)及分析

利用NS2網(wǎng)絡(luò)仿真軟件構(gòu)建實(shí)驗(yàn)環(huán)境，將本文提出的基于PSO－SA優(yōu)化的分簇協(xié)議與能量感知LEACH－EP協(xié)議［4］、基于SA優(yōu)化的分簇協(xié)議［6］和基于GA優(yōu)化的分簇協(xié)議［5］進(jìn)行比較，在不同網(wǎng)絡(luò)場(chǎng)景下，對(duì)于第一節(jié)點(diǎn)死亡（FND）、50%節(jié)點(diǎn)死亡（HND）和100%節(jié)點(diǎn)死亡（LND）時(shí)的網(wǎng)絡(luò)性能數(shù)據(jù).

3.1 仿真設(shè)置

實(shí)驗(yàn)中，設(shè)置PSO算法中粒子種群大小為15，最大迭代數(shù)設(shè)為30.由于SA算法并非基于種群，且不是基于單一解的算法，所以設(shè)置SA算法中最大迭代數(shù)設(shè)為150，Tinitial和Tfinal分別為0.1和0，和分別為0.05和0.02.

為了證明本文分簇協(xié)議在延長(zhǎng)網(wǎng)絡(luò)壽命方面的有效性，在3種不同結(jié)構(gòu)網(wǎng)絡(luò)中進(jìn)行仿真實(shí)驗(yàn).WSN＃1場(chǎng)景中，隨機(jī)部署100個(gè)傳感器節(jié)點(diǎn)在100m×100m拓?fù)鋮^(qū)域內(nèi).WSN＃2場(chǎng)景中，隨機(jī)部署200個(gè)傳感器節(jié)點(diǎn)在150m×150m拓?fù)鋮^(qū)域內(nèi).WSN＃3場(chǎng)景中，隨機(jī)部署500個(gè)傳感器節(jié)點(diǎn)在200m×200m拓?fù)鋮^(qū)域內(nèi).為了證明各種協(xié)議在不同傳感器節(jié)點(diǎn)數(shù)量下的網(wǎng)絡(luò)延遲情況，隨機(jī)部署50到250個(gè)節(jié)點(diǎn)在150m×150m區(qū)域內(nèi).網(wǎng)絡(luò)中只有一個(gè)Sink節(jié)點(diǎn)，且位于網(wǎng)絡(luò)的中心，所有傳感器節(jié)點(diǎn)均具有1J的初始能量.

3.2 仿真結(jié)果

（2）的適應(yīng)度函數(shù)內(nèi)的權(quán)重參數(shù)應(yīng)基于應(yīng)用程序的技術(shù)指標(biāo)和壽命定義進(jìn)行設(shè)定.實(shí)驗(yàn)中，設(shè)定適應(yīng)度權(quán)重參數(shù)為w1＝0.7、w2＝0.3、w3＝0，則意味著FND是主要因素，HND是次要因素，LND不重要.本文經(jīng)由混合PSO－SA算法自適應(yīng)調(diào)整分簇協(xié)議的控制參數(shù)，獲得最優(yōu)分簇結(jié)構(gòu)，延長(zhǎng)網(wǎng)絡(luò)壽命.在3種不同WSN中運(yùn)用PSO－SA算法，獲得的優(yōu)化參數(shù)如表1所示.

表1 通過PSO－SA算法優(yōu)化得到的控制參數(shù)Tab.1 The control parameters obtaines by PSO and SA algorithm

圖3～圖5分別顯示了4種協(xié)議在WSN＃1（100的節(jié)點(diǎn)）、WSN＃2（200個(gè)節(jié)點(diǎn)）和 WSN＃3（500個(gè)節(jié)點(diǎn)）時(shí)，不同輪數(shù)下的網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù).可以看出，本文協(xié)議比其他協(xié)議更加穩(wěn)定，具有最長(zhǎng)的生命周期，且從第一個(gè)節(jié)點(diǎn)死亡開始，線性減少直到所有傳感器節(jié)點(diǎn)死亡.

表2給出了4種協(xié)議在FND、HND和LND時(shí)的網(wǎng)絡(luò)壽命數(shù)據(jù)（輪數(shù)），該數(shù)據(jù)為運(yùn)行5次實(shí)驗(yàn)的平均值.可以看出，WSN＃1中，與SA、GA、LEACH－EP比較，本文協(xié)議的FND處的壽命分別提高了86.8%、64.8%和7.9%；WSN＃2中，分別提高了117%、70%和6.4%；WSN＃3中，分別提高了203%、119%、20%.

表2 4種協(xié)議的網(wǎng)絡(luò)壽命數(shù)據(jù)表2 The network life data of 4protocols

為了驗(yàn)證各協(xié)議的網(wǎng)絡(luò)延遲，分別部署50、100、150、200和250個(gè)節(jié)點(diǎn)在150m×150m區(qū)域內(nèi)，分別執(zhí)行10次實(shí)驗(yàn)取平均值，各協(xié)議的網(wǎng)絡(luò)延遲如圖6所示.

由圖6可以看出，隨著傳感器節(jié)點(diǎn)的增加，網(wǎng)絡(luò)延遲逐漸上升，本文協(xié)議延時(shí)變化曲線比較平穩(wěn)，增長(zhǎng)速度最慢.這是因?yàn)椋疚膮f(xié)議克服了陷入局部最優(yōu)缺陷，收斂速度快，所尋找到的路徑最優(yōu)，傳感器節(jié)點(diǎn)之間能夠快速地進(jìn)行數(shù)據(jù)傳輸，降低了網(wǎng)絡(luò)延時(shí).

4 結(jié)束語(yǔ)

本文提出了一種基于群智能算法的WSN分簇協(xié)議，考慮多種節(jié)點(diǎn)因素，利用融合PSO和SA來(lái)優(yōu)化分簇階段簇頭選舉閾值，使網(wǎng)絡(luò)獲得最佳分簇結(jié)構(gòu).和現(xiàn)有基于遺傳優(yōu)化、基于模擬退火優(yōu)化和LEACH－EP協(xié)議相比，本文協(xié)議獲得的分簇結(jié)構(gòu)具有較長(zhǎng)的網(wǎng)絡(luò)壽命和較小的網(wǎng)絡(luò)傳輸延遲.未來(lái)研究將考慮處理移動(dòng)傳感器節(jié)點(diǎn)，使提出的協(xié)議適用于移動(dòng)網(wǎng)絡(luò).

［1］張震，石志東，單聯(lián)海，等.WSN中一種自適應(yīng)功率控制及調(diào)度算法［J］.計(jì)算機(jī)工程，2013，39（4）：18－21.

［2］陳曉娟，王卓，吳潔.一種基于LEACH的改進(jìn) WSN路由算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26（1）：116－121.

［3］薛曉亮，祁榮賓，錢鋒.基于能量均衡的WSN多跳非均勻分簇路由算法［J］.華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，37（3）：352－358.

［4］JIA J G，HE Z W，KUANG J M，et al.An energy consumption balanced clustering algorithm for wireless sensor network［C］／／Wireless Communications Networking ＆ Mobile Computing International Conference，2011：1－4.

［5］BOJAN S，NIKOLA Z.Genetic algorithm as energy optimization method in WSN［C］／／Telecommunications Forum （TELFOR），IEEE，2013：97－100.

［6］AZAMI M，RANJBAR M，ROSTAMI A S，et al.Increasing the network life time by simulated annealing algorithm in WSN with point coverage［J］.International Journal of Ad Hoc Sensor ＆ Ubiquitous Computing，2013，34（2）：97－102.

［7］郝曉辰，賈楠，劉彬.基于擁塞預(yù)知的WSN多徑尋優(yōu)路由協(xié)議［J］.電子與信息學(xué)報(bào)，2011，33（5）：1 261－1 265.

［8］PING A，GONG G J，LIU X J.WSN energy estimation route protocol algorithm［J］.Computer Simulation，2013，30（8）：285－288.

［9］ALAYEV Y，CHEN F，HOU Y，et al.Throughput maximization in mobile WSN scheduling with power control and rate selection［J］.Wireless Communications IEEE Transactions on，2012，13（7）：33－40.

［10］秦智超，周正，趙小川.利用粒子群優(yōu)化的WSN環(huán)狀簇路由協(xié)議［J］.北京郵電大學(xué)學(xué)報(bào)，2012，35（5）：26－30.