陳 鵬，王向文，孫 充

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

1 引言

無(wú)線傳感器網(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)測(cè)、醫(yī)學(xué)等其它領(lǐng)域之中。然而，這些傳感器節(jié)點(diǎn)是由其自身攜帶的電源供電的，由于其體積小，所攜帶的能量有限，對(duì)其充電又十分的不便，所以常常因?yàn)槟承┕?jié)點(diǎn)的能量耗盡導(dǎo)致整個(gè)網(wǎng)絡(luò)無(wú)法正常運(yùn)行，嚴(yán)重影響了網(wǎng)絡(luò)的生命周期。

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

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

2 系統(tǒng)模型

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

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

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

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

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

2.1 能耗模型

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

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

(1)

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

Ereceive(k)=k×Eelec

(2)

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

(3)

3 改進(jìn)算法

3.1 分簇階段

傳統(tǒng)的LEACH算法依靠節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)與閾值比較決定簇頭的與否，而閾值計(jì)算公式的值僅與輪數(shù)r一個(gè)變量相關(guān)，因此簇頭的分布呈現(xiàn)出很大的隨機(jī)性。部分區(qū)域簇頭分布過(guò)于密集，剩余能量不足的節(jié)點(diǎn)被選為能耗較大的簇頭節(jié)點(diǎn)等現(xiàn)象對(duì)網(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)個(gè)數(shù)；Ni指的是與節(jié)點(diǎn)i相距不超過(guò)設(shè)定半徑R的節(jié)點(diǎn)個(gè)數(shù)。

經(jīng)過(guò)改進(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ā)射廣播信號(hào)，信號(hào)隨著距離的增加會(huì)逐漸減弱，普通節(jié)點(diǎn)根據(jù)信號(hào)的強(qiáng)弱選擇簇頭節(jié)點(diǎn)并進(jìn)行入簇。

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

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

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

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

(5)

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

(6)

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

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

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

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

(7)

(8)

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

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

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

(9)

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

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

(10)

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

(11)

(12)

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

圖1 角度因子θ示意圖

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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