基于免疫粒子群優(yōu)化的移動(dòng)Sink路徑規(guī)劃算法

張 紅，薛東亮，李戰(zhàn)明*

(1 蘭州理工大學(xué) 電氣工程與信息工程學(xué)院，蘭州 730050；2 河南信息工程學(xué)校，鄭州 450011 )

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)通常由大量分布的自主傳感器節(jié)點(diǎn)和 Sink 節(jié)點(diǎn)組成,通過協(xié)同通信實(shí)現(xiàn)對(duì)環(huán)境參數(shù)的持續(xù)監(jiān)測(cè).因此，在工業(yè)過程監(jiān)控、智能家居控制、交通監(jiān)控處理等領(lǐng)域具有廣泛的應(yīng)用價(jià)值和極具吸引力的市場(chǎng)潛力[1].由于節(jié)點(diǎn)受電池約束以及系統(tǒng)采用無線通信方式，能量效率是無線傳感網(wǎng)研究領(lǐng)域關(guān)注的主要問題.在配置靜態(tài)Sink 節(jié)點(diǎn)的傳感網(wǎng)中,多跳路由相比單跳能顯著地減少節(jié)點(diǎn)平均能耗，但是也易使靠近 Sink 節(jié)點(diǎn)的傳感節(jié)點(diǎn)因?yàn)槌休d更多的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)導(dǎo)致失效較早，形成熱點(diǎn)問題[2].于是,很多學(xué)者考慮在WSN引入可移動(dòng)的 Sink 節(jié)點(diǎn)，通過變換駐留點(diǎn)位置實(shí)現(xiàn)更為均衡的節(jié)點(diǎn)能量消耗，從而延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間.在這種模式下，Sink 節(jié)點(diǎn)的停留位置和移動(dòng)路徑的規(guī)劃是研究的主要熱點(diǎn).

移動(dòng)Sink的路徑選擇與優(yōu)化關(guān)系到無線傳感網(wǎng)的能量效率.Wichmann等[3]以飛行器作為移動(dòng)Sink節(jié)點(diǎn)進(jìn)行大范圍傳感器節(jié)點(diǎn)收集的載體并建立旅行商問題(Traveling Salesman Problem，TSP)算法的模型,充分考慮長(zhǎng)路徑條件下的數(shù)據(jù)延遲約束，但是對(duì)網(wǎng)絡(luò)生存周期的關(guān)注不夠.Kumar 等[4]假定節(jié)點(diǎn)都具備GPS模塊，可以獲得精確的位置信息，再利用分簇算法并將簇頭節(jié)點(diǎn)位置設(shè)定為移動(dòng)Sink的駐留點(diǎn)位置，進(jìn)行路徑的優(yōu)化選擇.Tashtarian 等[5]考慮了消息截止時(shí)間和事件驅(qū)動(dòng)的應(yīng)用場(chǎng)景，以節(jié)點(diǎn)事件觸發(fā)的機(jī)制來規(guī)劃Sink的移動(dòng).針對(duì)監(jiān)控區(qū)域內(nèi)Sink移動(dòng)軌跡中可能遇到障礙物的情況，Ghosh等[6]提出了一種移動(dòng)采集路徑規(guī)劃策略以提高網(wǎng)絡(luò)的能量效率.Salarian等[7]提出了一種稱為加權(quán)交會(huì)規(guī)劃(weighted rendezvous planning, WRP)的啟發(fā)式算法，根據(jù)每個(gè)傳感器節(jié)點(diǎn)到駐留點(diǎn)位置和其要發(fā)送的數(shù)據(jù)量分配相應(yīng)的權(quán)重，使得移動(dòng)Sink的數(shù)據(jù)收集效率最大化.為了保證網(wǎng)絡(luò)所有節(jié)點(diǎn)的能量下降同步以延長(zhǎng)網(wǎng)絡(luò)的生命周期，Lee等[8]從節(jié)點(diǎn)的地理分布和鄰居節(jié)點(diǎn)能量消耗速度監(jiān)測(cè)兩個(gè)方面入手，提出一種分布式啟發(fā)算法來求解移動(dòng)Sink的停留位置選擇問題.

本文將人工免疫算法和粒子群算法相結(jié)合，提出了基于免疫粒子群優(yōu)化的移動(dòng)Sink數(shù)據(jù)收集算法來進(jìn)行路由規(guī)劃，求解WSN移動(dòng)Sink最優(yōu)路徑,有效提高網(wǎng)絡(luò)整體的數(shù)據(jù)采集效率.

1 系統(tǒng)模型與問題描述

假設(shè)在M×M的矩形監(jiān)測(cè)區(qū)域隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)和1個(gè)移動(dòng)Sink節(jié)點(diǎn)，其中：傳感器節(jié)點(diǎn)均有唯一標(biāo)識(shí),且為靜止?fàn)顟B(tài)；節(jié)點(diǎn)間可以以多跳形式轉(zhuǎn)發(fā)采集的數(shù)據(jù)；所有傳感器節(jié)點(diǎn)具有相同的通信半徑r和相同的初始能量E9; Sink節(jié)點(diǎn)可外接電源進(jìn)行能量補(bǔ)充.

網(wǎng)絡(luò)初始化后，Sink節(jié)點(diǎn)從初始位置開始，與通信范圍內(nèi)的傳感器節(jié)點(diǎn)進(jìn)行數(shù)據(jù)回收，匯集完畢后再移動(dòng)到下一個(gè)區(qū)域，最終回到初始位置形成數(shù)據(jù)采集回路.設(shè)Tp為移動(dòng)Sink完成一個(gè)周期的數(shù)據(jù)匯集形成的路徑，該路徑由多個(gè)駐留點(diǎn)的連接線路組成.假設(shè)駐留點(diǎn)數(shù)量為n，第i個(gè)駐留點(diǎn)坐標(biāo)為：pi=(xi,yi)，移動(dòng)Sink的遍歷路徑可以表示為：Tp={s,p1,p2,…,pn,s}，s=(x0,y0)為Sink節(jié)點(diǎn)初始位置.

為了問題描述方便，假設(shè)所有傳感器節(jié)點(diǎn)采用固定的發(fā)射和接收功率,則在每一周期的能耗可以表示為:

(1)

因此,網(wǎng)絡(luò)中的整體能耗可以表示為最小跳數(shù)和的形式：

(2)

從(2)式可以得到,系統(tǒng)能耗的最小化與所有節(jié)點(diǎn)到駐留點(diǎn)跳數(shù)之和最小化正相關(guān).而傳感器節(jié)數(shù)據(jù)轉(zhuǎn)發(fā)的跳數(shù)與移動(dòng)Sink節(jié)點(diǎn)選擇的駐留點(diǎn)之間的距離有關(guān).因此，Sink的移動(dòng)路徑的選擇將直接影響整個(gè)網(wǎng)絡(luò)的整體能耗.

此外，從直觀上看，Sink的移動(dòng)路徑的長(zhǎng)短會(huì)直接影響節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)延遲.因此，綜合上述分析，將WSNs中移動(dòng)Sink的路徑規(guī)劃問題的求解定義為多目標(biāo)優(yōu)化函數(shù)，表示為:

f(Tp)=D(Tp)+ETp(d),

(3)

其中，D(Tp)為路徑總長(zhǎng)度，ETp(d)為Sink通信半徑d條件下的網(wǎng)絡(luò)整體能耗.

2 免疫粒子群優(yōu)化

對(duì)于路徑優(yōu)化問題，建立在生物智能或物理現(xiàn)象基礎(chǔ)上的隨機(jī)搜索算法被廣泛采用.在眾多的群智能搜索算法中，粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)由Kennedy等人提出后就受到廣泛關(guān)注.PSO算法通過基于種群搜索策略的自適應(yīng)隨機(jī)優(yōu)化，能夠充分利用群體間個(gè)體信息的共享，使得整個(gè)群體能夠沿著最優(yōu)解的方向不斷遷移，不斷迭代最終找到最優(yōu)解，該算法在控制參數(shù)設(shè)置、實(shí)現(xiàn)的易用性等方面具有顯著優(yōu)點(diǎn)；其不足之處在于算法的種群多樣性較低以及易陷入局部最優(yōu).

本文將粒子群算法與人工免疫算法相結(jié)合，利用免疫算法在全局尋優(yōu)和種群多樣性保持能力等方面的優(yōu)點(diǎn)，將免疫系統(tǒng)的自適應(yīng)識(shí)別以及對(duì)侵入機(jī)體的抗原異物進(jìn)行排斥的特性引入到粒子種群的演化過程中，以提高算法的收斂性能并有效避免傳統(tǒng)算法在求解過程中陷入局部最優(yōu).

2.1 粒子的產(chǎn)生與更新

設(shè)粒子群大小為M，每個(gè)粒子對(duì)應(yīng)一個(gè)路徑規(guī)劃方案，每個(gè)方案包括駐留點(diǎn)pi及遍歷順序Tp.算法初始化時(shí)，先隨機(jī)設(shè)置駐留點(diǎn)和訪問順序，一旦駐留點(diǎn)被選擇，則將其從備選點(diǎn)集合中刪除，用D維向量來表示粒子i的信息，其位置信息為xi=(xi1,xi2,…,xiD)，速度信息為vi=(vi1,vi2,…，viD)，適應(yīng)度值fitness.迭代過程中，粒子通過跟蹤兩個(gè)極值來進(jìn)行更新：一是粒子本身所能找到的個(gè)體最優(yōu)解Pbest，另一個(gè)是整個(gè)粒子種群目前所找到的歷史最優(yōu)解gbest.位置信息和速度信息的更新表示為：

vij(k+1)=wvij(k)+c1r1(Pbest(k)-xij(k))+

c2r2(gbest(k)-xij(k)),

(4)

xij(k+1)=xij(k)+vij(k+1),

(5)

其中,w表示慣性權(quán)重，r1和r2是介于[0,1]之間的隨機(jī)數(shù)，c1和c2是取非負(fù)值的學(xué)習(xí)因子，pbest(k)為第i個(gè)粒子在迭代輪次k所找到的個(gè)體最優(yōu)值位置，gbest(k)為整個(gè)粒子種群在迭代輪次k所找到的全局最優(yōu)值位置.

2.2 選擇概率

在人工免疫算法中，一般通過親和度對(duì)解的優(yōu)良程度進(jìn)行評(píng)價(jià).將函數(shù)的候選解看做抗體((第i個(gè)粒子)，將目標(biāo)函數(shù)的最優(yōu)解看做抗原.當(dāng)親和度越高時(shí)，抗體與抗原越接近.因此，親和度評(píng)價(jià)函數(shù)可以定義為：

g(xi)=emin{f(Tp,xi)}.

(6)

以多個(gè)最佳個(gè)體的平均值為疫苗的選取參照，定義疫苗為：

(7)

相似抗體越多，則算法越容易陷入局部最優(yōu)，因而需要對(duì)相似的抗體采取抑制措施.定義抗體濃度來衡量抗體多樣性程度.用X來表示抗體集合，有X={x1,x2,…,xn}，抗體濃度可以定義為：

(8)

為了保證選擇過程中，對(duì)于某些濃度雖低但發(fā)展趨勢(shì)較好的抗體也能有機(jī)會(huì)進(jìn)化，將抗體促進(jìn)與抑制的選擇概率Prs定義為：

(9)

其中，δ為比例因子.

選擇概率Prs能充分體現(xiàn)，對(duì)于濃度越高的抗體,選擇的概率越小.另外，對(duì)于親和度越高的抗體，也具有較高的選擇概率.

2.3 算法步驟

算法的主要步驟描述如下：

步驟1：待優(yōu)化函數(shù)的最優(yōu)解為抗原，候選解為抗體.對(duì)WSN傳感器節(jié)點(diǎn)數(shù)量，仿真區(qū)域大小等進(jìn)行設(shè)定，設(shè)置粒子數(shù)量M，每個(gè)粒子代表一個(gè)可行的路徑，學(xué)習(xí)因子c1,c2，權(quán)重wmax，wmin,當(dāng)前迭代次數(shù)λ=1，迭代次數(shù)最大值λmax；初始抗體生成；

步驟2：抗體采用實(shí)數(shù)編碼.在自變量范圍內(nèi)隨機(jī)產(chǎn)生候選解X=(x1,x2,…,xn)T作為初始抗體群,初始速度V==(v1,v2,…,vn)T，計(jì)算所有抗體的親和度.根據(jù)親和度,計(jì)算出每個(gè)抗體和整個(gè)抗體群所經(jīng)歷的歷史最好位置pbest和gbest；

步驟3：將親和度從小到大排序，取一定比例的親和度所對(duì)應(yīng)的抗體作為抗體免疫記憶，以多個(gè)優(yōu)良個(gè)體對(duì)應(yīng)的基因的平均值作為疫苗；

步驟4：如果抗原是新的，則通過隨機(jī)方式產(chǎn)生n個(gè)新抗體形成抗體群；否則，則從免疫記憶庫進(jìn)行抽取.計(jì)算抗體促進(jìn)與抑制的選擇概率后，采用輪盤賭方法選擇進(jìn)入下一代的抗體；

步驟5：對(duì)疫苗中一半的基因含量進(jìn)行隨機(jī)抽取，然后選擇部分親和度較低的抗體進(jìn)行基因替換操作，提高種群的多樣性選擇.如果接種后的抗體其親和度不如父代，則放棄并選擇原有的抗體；

步驟6：粒子的位置按照公式(5)執(zhí)行更新操作；

步驟7：重新計(jì)算每個(gè)抗體的親和度.將每個(gè)抗體當(dāng)前的pbest和所有經(jīng)歷過的pbest進(jìn)行比較，如果優(yōu)于則更新；同理，對(duì)整個(gè)抗體群，將當(dāng)前gbest與所有經(jīng)歷過的gbest比較，優(yōu)于則更新.粒子的速度按照公式(4)執(zhí)行更新操作；

步驟8：一旦達(dá)到最大迭代次數(shù)或目標(biāo)函數(shù)值收斂,算法終止;否則，跳轉(zhuǎn)至步驟3繼續(xù)執(zhí)行.

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

首先，實(shí)驗(yàn)對(duì)傳統(tǒng)粒子群算法與本文提出的算法在求解問題時(shí)，隨迭代次數(shù)適應(yīng)度值的變化情況如圖1所示，在算法迭代相同次數(shù)下，本文算法得到的適應(yīng)度值更低，表明加入了免疫算法的粒子群優(yōu)化在求解最優(yōu)解的過程中表現(xiàn)出更好的收斂性.圖2是隨算法的迭代，所能找到的解所對(duì)應(yīng)的移動(dòng)Sink對(duì)應(yīng)路徑，總體上來看本文提出的優(yōu)化算法能夠找到更優(yōu)化的解，而且在迭代次數(shù)上可以反映免疫算法對(duì)解的優(yōu)良程度的改進(jìn)作用明顯.

圖1 適應(yīng)度值的比較Fig.1 Comparison of fitness values

圖2 路徑長(zhǎng)度的比較Fig. 2 Comparison of path length

為了對(duì)比算法在路徑規(guī)劃和能量效率的性能，本文算法與算法FDG-PS[9]和SMGF[10]在不同節(jié)點(diǎn)數(shù)量分布的環(huán)境下進(jìn)行了仿真實(shí)驗(yàn).在相同區(qū)域范圍了配置不同數(shù)量的傳感器節(jié)點(diǎn)，算法的其他參數(shù)保持不變.圖3為三種算法所求得的Sink移動(dòng)路徑的總長(zhǎng)度，圖4為完成一次數(shù)據(jù)收集過程的網(wǎng)絡(luò)整體能耗，Sink覆蓋范圍內(nèi)的節(jié)點(diǎn)可采用多跳方式與Sink進(jìn)行通信.從實(shí)驗(yàn)結(jié)果可以看到，隨著傳感器節(jié)點(diǎn)的增多,Sink節(jié)點(diǎn)的移動(dòng)路徑增加,AAA算法的路徑長(zhǎng)度小于其他兩種算法的路徑長(zhǎng)度，說明本文算法找的解更優(yōu).另外，節(jié)點(diǎn)的能耗與數(shù)據(jù)轉(zhuǎn)發(fā)的跳數(shù)有關(guān)，最終反映到Sink節(jié)點(diǎn)的駐留點(diǎn)位置選擇上，本文算法能夠得到更好的能量效率.

圖3 網(wǎng)絡(luò)平均能耗的比較Fig.3 Comparison of network average energy consumption

圖4 路徑長(zhǎng)度的比較Fig.4 Comparison of path length

4 結(jié)語

針對(duì)無線傳感網(wǎng)中采用移動(dòng)Sink的方式收集節(jié)點(diǎn)采集帶來的路徑優(yōu)化問題，本文提出了將人工免疫算法和粒子群算法相結(jié)合，尋求近似最優(yōu)解.與其他算法進(jìn)行了性能比較，本文提出的優(yōu)化算法能夠有效減少能耗和縮短遍歷路徑.后續(xù)我們將進(jìn)一步研究基于多Sink的移動(dòng)數(shù)據(jù)收集，以及考慮節(jié)點(diǎn)之間的協(xié)作來進(jìn)一步壓縮訪問點(diǎn)的空間來研究進(jìn)一步優(yōu)化移動(dòng)Sink路徑.