基于改進(jìn)蟻群算法的WSN分簇路由協(xié)議的研究

陳 鵬，王向文，孫 充

(上海電力大學(xué)電子與信息工程學(xué)院，上海 200000)

1 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network， WSN)是由大量隨機(jī)分布的微型傳感器節(jié)點(diǎn)組成的復(fù)雜網(wǎng)絡(luò)系統(tǒng)，可用于接收、處理和傳輸數(shù)據(jù)，其應(yīng)用范圍也從原先的軍事領(lǐng)域逐漸擴(kuò)展到工農(nóng)業(yè)生產(chǎn)、環(huán)境監(jiān)測、醫(yī)學(xué)等其它領(lǐng)域之中。然而，這些傳感器節(jié)點(diǎn)是由其自身攜帶的電源供電的，由于其體積小，所攜帶的能量有限，對其充電又十分的不便，所以常常因?yàn)槟承┕?jié)點(diǎn)的能量耗盡導(dǎo)致整個網(wǎng)絡(luò)無法正常運(yùn)行，嚴(yán)重影響了網(wǎng)絡(luò)的生命周期。

針對此類問題提出較為經(jīng)典的是LEACH協(xié)議[1]，該協(xié)議通過節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)與閾值的比較競選出簇頭節(jié)點(diǎn)，簇內(nèi)節(jié)點(diǎn)將采集到的數(shù)據(jù)傳輸給簇頭節(jié)點(diǎn)融合后，簇頭節(jié)點(diǎn)再以單跳的方式將數(shù)據(jù)轉(zhuǎn)發(fā)給基站節(jié)點(diǎn)。協(xié)議分為分簇和數(shù)據(jù)傳輸兩個階段，在分簇階段由于閾值計(jì)算公式過于簡單，簇頭選擇具有很大的隨機(jī)性，這可能會導(dǎo)致能量不足的節(jié)點(diǎn)成為簇頭，且簇頭分布的密集程度不合理，整個網(wǎng)絡(luò)的能耗處于不平衡的狀態(tài)。對此胡峰松[2]等人充分考慮了節(jié)點(diǎn)的能量和位置因素，提出了一種能耗相對均衡的多跳路由算法，一定程度上優(yōu)化了簇頭的能耗，延長了網(wǎng)絡(luò)的壽命。杜永文[3]等人利用模糊算法綜合考量節(jié)點(diǎn)剩余能量和與基站的距離來計(jì)算節(jié)點(diǎn)的競爭力，最后根據(jù)節(jié)點(diǎn)的競爭力采用非均勻分簇方法進(jìn)行簇首選擇。吉正詢[4]等人按照節(jié)點(diǎn)的剩余能量將網(wǎng)絡(luò)劃分為標(biāo)準(zhǔn)區(qū)和警惕區(qū)，在不同區(qū)域有不同的閾值，節(jié)點(diǎn)成為簇頭的概率也不同，但由于沒有考慮距離的因素，容易出現(xiàn)簇頭節(jié)點(diǎn)分布過于密集的情況。陳相睿[5]等人將最優(yōu)簇頭個數(shù)的概念引入閾值計(jì)算公式，同時兼顧了能量和距離的因素使得簇頭的分布更加合理。在數(shù)據(jù)傳輸階段傳統(tǒng)LEACH協(xié)議表現(xiàn)的不足在于傳輸方式的單一性，許多節(jié)點(diǎn)能耗過快死亡大都因?yàn)榫嚯x基站較遠(yuǎn)但與基站直接通信，所以建立一條節(jié)點(diǎn)到基站的最優(yōu)傳輸路徑對提高WSN網(wǎng)絡(luò)的壽命顯得至關(guān)重要。蟻群算法(Ant Colony Optimization， ACO)在解決路徑規(guī)劃問題上具有良好的表現(xiàn)，近年來國內(nèi)外學(xué)者也在經(jīng)典蟻群算法的基礎(chǔ)上提出了許多優(yōu)化算法。童孟軍[6]等人提出的EEABR(Energy-efficient ant-base routing)算法考慮了節(jié)點(diǎn)能量和螞蟻經(jīng)過的跳數(shù)等因素，優(yōu)化了信息素增量公式，但由于該算法只保存螞蟻?zhàn)罱L問的兩個節(jié)點(diǎn)的信息，易造成螞蟻環(huán)路，無法解決網(wǎng)絡(luò)的能耗均衡問題。肖鋮[7]等人在EEABR算法的基礎(chǔ)上改進(jìn)了啟發(fā)因子的計(jì)算公式，有效地解決了單路徑路由節(jié)點(diǎn)能耗不均衡的問題。喻小惠[8]等人在狀態(tài)轉(zhuǎn)移函數(shù)中加入適應(yīng)度因子，使得節(jié)點(diǎn)密集度較高的節(jié)點(diǎn)成為螞蟻下一跳的概率增加，但他并沒有考慮角度因子，無關(guān)路徑的訪問增加了節(jié)點(diǎn)的能耗。金永賢[9]等人將分簇機(jī)制和蟻群算法相結(jié)合，提出了一種多徑路由協(xié)議MRPCAC，引入了最優(yōu)路徑選取函數(shù)，并在啟發(fā)式因子計(jì)算公式中加入了能量和角度因子，減少了無關(guān)路徑的訪問次數(shù)，加快了算法的收斂速度，但算法運(yùn)行后期容易因信息素的堆積陷入局部最優(yōu)。

根據(jù)上述情況，本文針對LEACH協(xié)議表現(xiàn)出的缺陷，在分簇階段，充分考慮節(jié)點(diǎn)的能量、節(jié)點(diǎn)到基站的距離和節(jié)點(diǎn)的密集程度三個因素，優(yōu)化簇頭的選舉機(jī)制；在數(shù)據(jù)傳輸階段，通過改進(jìn)蟻群算法尋找最優(yōu)傳輸路徑。將偽隨機(jī)規(guī)則加入到狀態(tài)轉(zhuǎn)移函數(shù)中，利用動態(tài)揮發(fā)系數(shù)防止信息素堆積引起算法的局部收斂，同時優(yōu)化信息素更新規(guī)則和啟發(fā)式因子公式，縮小了螞蟻的尋徑范圍。實(shí)驗(yàn)表明，本文所提算法能有效均衡網(wǎng)絡(luò)能耗，提高網(wǎng)絡(luò)的生命周期。

2 系統(tǒng)模型

2.1 WSN網(wǎng)絡(luò)模型

無線傳感器網(wǎng)絡(luò)可視為一個二維平面，平面內(nèi)有一個用于接收所有節(jié)點(diǎn)信息的固定基站和n個隨機(jī)分布的用于采集信息的傳感器節(jié)點(diǎn)。若v1表示第一個傳感器節(jié)點(diǎn)，則V=(v1，v2，…，vn，vsink)代表所有節(jié)點(diǎn)的集合，其中vsink表示基站節(jié)點(diǎn)。節(jié)點(diǎn)之間的鏈路關(guān)系可以表示為E=(e1，e2，…，en)，則整個網(wǎng)絡(luò)的數(shù)學(xué)模型可以用G=(E，V)表示。為了使算法便于實(shí)現(xiàn)，本文提出了如下假設(shè)：

1)網(wǎng)絡(luò)中的節(jié)點(diǎn)隨機(jī)分布且一旦確定位置將不再發(fā)生位移。

2)每個節(jié)點(diǎn)攜帶的能量相同且可以根據(jù)信號的強(qiáng)度判斷節(jié)點(diǎn)間的距離。

3)節(jié)點(diǎn)的發(fā)射功率可以視情況自我調(diào)節(jié)。

2.1 能耗模型

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的能量主要消耗在接收數(shù)據(jù)和輸出數(shù)據(jù)[10]。

相距為d的兩個傳感器節(jié)點(diǎn)每傳輸kbit數(shù)據(jù)所消耗的能量

(1)

節(jié)點(diǎn)每接收kbit數(shù)據(jù)所消耗的能量

Ereceive(k)=k×Eelec

(2)

式中，Eelec是每處理單位數(shù)據(jù)時電池的耗能；εfs和εamp是兩個不同傳輸模型下的能耗參數(shù)；d0為距離閾值，當(dāng)節(jié)點(diǎn)間的距離小于閾值d0時，采用自由空間傳輸模型，否則使用多路徑衰減信道模型。閾值d0的計(jì)算公式

(3)

3 改進(jìn)算法

3.1 分簇階段

傳統(tǒng)的LEACH算法依靠節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)與閾值比較決定簇頭的與否，而閾值計(jì)算公式的值僅與輪數(shù)r一個變量相關(guān)，因此簇頭的分布呈現(xiàn)出很大的隨機(jī)性。部分區(qū)域簇頭分布過于密集，剩余能量不足的節(jié)點(diǎn)被選為能耗較大的簇頭節(jié)點(diǎn)等現(xiàn)象對網(wǎng)絡(luò)的壽命造成極大的影響。因此本文充分考慮節(jié)點(diǎn)的能量、到基站的距離以及節(jié)點(diǎn)的密集程度，重新構(gòu)造閾值計(jì)算公式T’(n)

(4)

式中，p為簇頭節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例；r為輪數(shù)；Eres為節(jié)點(diǎn)i的剩余能量；E0為節(jié)點(diǎn)i的初始能量；dtoBS-i為節(jié)點(diǎn)i到基站的距離；dto-BS-i-max為節(jié)點(diǎn)到基站的最大距離；Nalive為網(wǎng)絡(luò)中尚未死亡的節(jié)點(diǎn)個數(shù)；Ni指的是與節(jié)點(diǎn)i相距不超過設(shè)定半徑R的節(jié)點(diǎn)個數(shù)。

經(jīng)過改進(jìn)后的閾值計(jì)算公式使得剩余能量占比較高、距離基站較近、鄰居節(jié)點(diǎn)較多的節(jié)點(diǎn)更容易擔(dān)任簇頭，完成簇內(nèi)與基站之間的數(shù)據(jù)傳輸。

在簇頭節(jié)點(diǎn)選定后，簇頭節(jié)點(diǎn)向全網(wǎng)絡(luò)發(fā)射廣播信號，信號隨著距離的增加會逐漸減弱，普通節(jié)點(diǎn)根據(jù)信號的強(qiáng)弱選擇簇頭節(jié)點(diǎn)并進(jìn)行入簇。

3.2 數(shù)據(jù)傳輸階段

傳統(tǒng)LEACH協(xié)議無視距離的遠(yuǎn)近統(tǒng)一與基站直接進(jìn)行數(shù)據(jù)傳輸，這使得距離基站較遠(yuǎn)的節(jié)點(diǎn)因能耗過大提前死亡，直接影響了網(wǎng)絡(luò)的正常運(yùn)行。本文簇內(nèi)數(shù)據(jù)傳輸采取了與LEACH協(xié)議一樣的單跳方式，而簇頭節(jié)點(diǎn)與基站之間的數(shù)據(jù)傳輸通過改進(jìn)蟻群算法找尋最佳傳輸路徑。

3.2.1 改進(jìn)狀態(tài)轉(zhuǎn)移公式

算法運(yùn)行的初期，在每條路徑上信息素和啟發(fā)信息都差不多的情況下，螞蟻很難依靠這些信息做出下一跳的判斷，需要一段時間信息素的積累才能避免螞蟻在進(jìn)行下一跳選擇時的盲目性，故而算法收斂速度較慢。其次，隨著算法的推進(jìn)，螞蟻越發(fā)偏向于最優(yōu)路徑，使得最優(yōu)路徑上的節(jié)點(diǎn)因訪問次數(shù)過多消耗大量的能量而提前死亡，嚴(yán)重影響了網(wǎng)絡(luò)的生命周期。針對此問題，本文提出一個偽隨機(jī)原則對狀態(tài)轉(zhuǎn)移函數(shù)進(jìn)行一定的改進(jìn)

(5)

式中，q為一個取值在[0，1]的隨機(jī)數(shù)；q0為一個取值在[0，1]的常數(shù)；τij(t)為t時刻節(jié)點(diǎn)i與節(jié)點(diǎn)j路徑上信息素的含量；ij(t)為啟發(fā)函數(shù)；α和β分別為信息啟發(fā)因子和啟發(fā)函數(shù)因子。在螞蟻每次選擇下一跳節(jié)點(diǎn)之前，先隨機(jī)產(chǎn)生一個隨機(jī)數(shù)q與q0比較，若q≤q0，則選擇[τij(t)]α[ij(t)]β值最大的節(jié)點(diǎn)作為螞蟻的下一跳，否則按照式(6)進(jìn)行下一跳的選擇

(6)

通過改進(jìn)的狀態(tài)轉(zhuǎn)移公式，一方面算法能夠在較短時間內(nèi)收斂于最優(yōu)解的附近，另一方面是在一定程度上實(shí)現(xiàn)了螞蟻的分流，使得最優(yōu)路徑上的節(jié)點(diǎn)不會被過于頻繁地訪問而消耗太多的能量，從而有效延長了網(wǎng)絡(luò)的壽命。

3.2.2 改進(jìn)信息素因子

在傳統(tǒng)的蟻群算法中，各個節(jié)點(diǎn)的初始信息素濃度均為0，每一只螞蟻在到達(dá)目的節(jié)點(diǎn)后都會形成一條可行的路徑，并在該條路徑上留下信息素，后續(xù)螞蟻會選擇信息素濃度較高也就是更多螞蟻曾經(jīng)過的路徑。這樣的正反饋機(jī)制勢必造成濃度較高的路徑信息素增長速度更快，最優(yōu)路徑上的節(jié)點(diǎn)被訪頻率過高而提前死亡。同時非最優(yōu)路徑上的信息素不能得到有效的供給，由于揮發(fā)系數(shù)的存在會變得越來越少，從而導(dǎo)致某些能量充足的路徑被荒廢，算法陷入了局部最優(yōu)。為了引導(dǎo)螞蟻進(jìn)行恰當(dāng)?shù)姆至鳎拐麄€網(wǎng)絡(luò)的能耗相對均衡，從而得到更接近于全局最優(yōu)的解，對此本文將結(jié)合能量因子優(yōu)化信息素的更新方式。

首先，針對某條路徑上信息度濃度過高的問題，本文給定了一個閾值τmax，修改后的信息素計(jì)算公式

(7)

(8)

3.2.3 改進(jìn)揮發(fā)系數(shù)

隨著算法的推進(jìn)，仍不可避免某些路徑上信息素堆積而造成的局部最優(yōu)問題。ρ作為信息素?fù)]發(fā)系數(shù)，它值的大小也代表了信息素消散的速度。在傳統(tǒng)的蟻群算法中，ρ為一個常數(shù)，通過對ρ作如下改進(jìn)

ρ(k)=ρ0·(2-e-λk)

(9)

式中，ρ0是信息啟發(fā)因子的基本值；λ是一個取值在[0，1]的常數(shù)；k代表算法迭代的次數(shù)。通過修改后的揮發(fā)系數(shù)ρ(k)隨著算法迭代次數(shù)k的增加會越來越大。在算法運(yùn)行初期，ρ(k)較小，信息素?fù)]發(fā)速度較慢，螞蟻可以更有效的依靠信息素濃度的高低進(jìn)行路徑的選擇；算法運(yùn)行到后期，ρ(k)也會逐漸增大，信息素的揮發(fā)速度相較之前會有明顯的提升，有效避免了算法后期因信息素堆積引起的局部收斂問題。

3.2.4 改進(jìn)啟發(fā)函數(shù)

(10)

這種計(jì)算方法有失全面性，在螞蟻進(jìn)行下一跳選擇時，會造成部分螞蟻選擇與sink節(jié)點(diǎn)相反的方向，產(chǎn)生大量無關(guān)路徑。對此，本文引入角度因子對啟發(fā)函數(shù)做出改進(jìn)

(11)

(12)

式中，λ1，λ2是常數(shù)，其大小代表距離和角度在計(jì)算啟發(fā)函數(shù)時的權(quán)重；θ是節(jié)點(diǎn)i與sink節(jié)點(diǎn)、節(jié)點(diǎn)i與節(jié)點(diǎn)j兩條連線的夾角，如圖1所示；dij，dis，djs分別對應(yīng)三個節(jié)點(diǎn)間的距離。

圖1 角度因子θ示意圖

通過修改后的啟發(fā)函數(shù)綜合考慮了距離和角度的因素，當(dāng)節(jié)點(diǎn)間距離dij和角度θ都比較小時，啟發(fā)函數(shù)ij(t)的值才會較大，螞蟻選擇該節(jié)點(diǎn)作為下一跳的概率才會較大，由此有效緩解了螞蟻的反向?qū)絾栴}，無關(guān)路徑的減少也為節(jié)點(diǎn)省下了大量的能量，有效延長了網(wǎng)絡(luò)的壽命。

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

為檢驗(yàn)本文算法的實(shí)際效果， 在MATLAB平臺對LEACH協(xié)議[11]、HEED算法[12]和本文算法進(jìn)行仿真，通過節(jié)點(diǎn)平均能耗、節(jié)點(diǎn)能耗的波動性和網(wǎng)絡(luò)壽命三個方面的分析對比驗(yàn)證本文算法的有效性。仿真環(huán)境為一個100m×100m的平面區(qū)域，區(qū)域內(nèi)隨機(jī)分布100個初始能量和性能都相同的傳感器節(jié)點(diǎn)，基站位于區(qū)域的中心(50，50)，每個節(jié)點(diǎn)每一輪都向下一個節(jié)點(diǎn)傳輸4000bits的數(shù)據(jù)，螞蟻數(shù)量為50只。仿真參數(shù)的設(shè)置見表1。

表1 仿真參數(shù)設(shè)置

由于在實(shí)際生產(chǎn)應(yīng)用中傳感器節(jié)點(diǎn)的設(shè)置并不會非常密集，所以往往部分節(jié)點(diǎn)的提前死亡就會出現(xiàn)網(wǎng)絡(luò)不能完全覆蓋的問題，此時網(wǎng)絡(luò)已經(jīng)失去了正常工作的能力，因此比較最后一個節(jié)點(diǎn)的死亡時間是毫無意義的。在此，本文規(guī)定以第一個節(jié)點(diǎn)的死亡時間作為網(wǎng)絡(luò)壽命的評判標(biāo)準(zhǔn)。圖2為三種算法在相同環(huán)境下，節(jié)點(diǎn)存活數(shù)量與輪數(shù)之間的關(guān)系。由圖可見LEACH協(xié)議和HEED算法分別在第110輪和第140輪出現(xiàn)首個死亡節(jié)點(diǎn)，而本文算法在進(jìn)行到第235輪才出現(xiàn)首個死亡節(jié)點(diǎn)，網(wǎng)絡(luò)壽命明顯延長。

圖2 網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)與輪數(shù)的關(guān)系

網(wǎng)絡(luò)壽命的延長很大原因在于節(jié)點(diǎn)本身能耗的降低，圖3顯示了三種算法下節(jié)點(diǎn)平均能耗的對比圖。由圖分析可得：LEACH協(xié)議和HEED協(xié)議節(jié)點(diǎn)的平均能耗大約在9.1mJ和8.4mJ，而本文算法中節(jié)點(diǎn)的平均能耗僅約6.6mJ，這是因?yàn)楸疚乃惴▽π畔⑺匾蜃印]發(fā)系數(shù)和啟發(fā)函數(shù)的改進(jìn)使得螞蟻更快收斂于最優(yōu)解，避免了許多無關(guān)路徑的訪問，減少了許多不必要的能量消耗。

圖3 節(jié)點(diǎn)平均能耗對比

同時，本文算法也在簇首選舉公式和螞蟻的尋徑條件中充分考慮了能量因素，使得整個網(wǎng)絡(luò)的能耗更加均衡，避免了某些節(jié)點(diǎn)某些時刻能耗過快的問題，延長了首個節(jié)點(diǎn)的死亡時間，從而提高了整個網(wǎng)絡(luò)的生命周期，圖4為三種算法前100輪節(jié)點(diǎn)能耗的折線圖，從圖中可以清晰地看出本文算法不僅在能耗上相較于另外兩種算法更低，而且節(jié)點(diǎn)的能耗也相對而言更加穩(wěn)定。

圖4 前100輪節(jié)點(diǎn)能耗

5 結(jié)語

本文針對傳統(tǒng)LEACH協(xié)議的不足，在分簇階段考慮了能量、距離和節(jié)點(diǎn)密集程度等因素優(yōu)化了閾值計(jì)算公式，使得簇首的分布更為合理。蟻群算法在尋徑問題中的良好表現(xiàn)剛好適用于數(shù)據(jù)傳輸階段的路徑規(guī)劃，出于對降低能耗延長壽命等要求的考慮，本文對蟻群算法做出了一定的改進(jìn)：在狀態(tài)轉(zhuǎn)移公式中引入偽隨機(jī)原則，改進(jìn)信息素更新方式，利用動態(tài)揮發(fā)系數(shù)，在啟發(fā)函數(shù)中引入角度因子。仿真表明，本文算法可以有效降低節(jié)點(diǎn)的能耗，延長網(wǎng)絡(luò)的壽命。