一種引入單純形法的能量均衡路由算法

湯文兵，陳亞楠，張 牧

(安徽理工大學 計算機工程學院，安徽 淮南 232000)

0 引 言

無線傳感器網(wǎng)絡(wireless sensor network，WSNs)有由許多廉價并且能進行無線通信的節(jié)點組成，具有監(jiān)測水平高、覆蓋面積大、可遠距離監(jiān)控等優(yōu)點，在軍事、醫(yī)療或者農(nóng)業(yè)等眾多領域應用廣泛[1-3]。傳感器節(jié)點一般部署在非常危險或者無法抵達的地方，網(wǎng)絡中節(jié)點的能量非常有限，這些節(jié)點的能量還不能得到及時的補充，所以節(jié)省節(jié)點能耗，均衡網(wǎng)絡消耗，延長網(wǎng)絡的生存周期是無線傳感器網(wǎng)絡研究的熱點。

建立高效的通信路徑實現(xiàn)與基站通信是研究無線傳感器網(wǎng)絡路由算法的重點。文獻[4-5]研究了基于LEACH算法的路由協(xié)議，解決了傳統(tǒng)算法中隨機選取簇頭的問題，但在均衡網(wǎng)絡能量方面有待提高。PEGASIS算法是在LEACH算法的基礎上發(fā)展而來，該算法采用跟貪婪算法相似的原理生成一條通信路徑，隨機選取簇頭節(jié)點實現(xiàn)與基站通信，但未考慮節(jié)點的能量問題，使得路徑中節(jié)點的能量消耗不均衡，導致一些節(jié)點過早死亡，影響了網(wǎng)絡的生存周期。文獻[6]針對該問題提出了解決方案。文獻[7]說明遺傳算法也能解決路徑優(yōu)化問題，并考慮了節(jié)點能量有限的問題，但未考慮尋優(yōu)過程中簇頭選取和收斂速度的問題。以上算法都有其優(yōu)點，在路徑優(yōu)化的過程中，節(jié)點要經(jīng)過大量的計算，對于能量有限的網(wǎng)絡來說，這種優(yōu)化過程非常受限。針對上述問題，并結(jié)合文獻[8-15]，提出一種遺傳算法和單純形算法的混合算法來均衡網(wǎng)絡中節(jié)點的能耗，延長無線傳感器網(wǎng)絡的生存時間。遺傳算法的隨機搜索特點和單純形算法的局部尋優(yōu)和確定性特點互相補充，能加快路徑尋優(yōu)的速度，在尋優(yōu)中不會陷入局部最優(yōu)的問題。

1 網(wǎng)絡能耗模型

無線傳感器網(wǎng)絡的能量消耗主要體現(xiàn)在節(jié)點與節(jié)點之間的通信消耗。提出的能耗模型[16]如下：

發(fā)送數(shù)據(jù)消耗的能量為：

Etransmit(k,d)=k*Eelec+ε*k*d2

(1)

接收數(shù)據(jù)消耗的能量為：

Ereceive(k)=k*Eelec

(2)

數(shù)據(jù)融合消耗的能量為：

Efusion(k)=k*EF

(3)

設d為無線傳感器網(wǎng)絡中節(jié)點之間的通信距離，Eelec為節(jié)點接收或者發(fā)送1 bit數(shù)據(jù)所消耗的能量，k為發(fā)送或接收數(shù)據(jù)的量(單位為bit)，ε為功率放大的能耗系數(shù)，EF為融合1 bit數(shù)據(jù)消耗的能量。那么網(wǎng)絡中每個節(jié)點所消耗的總能量為：

Eall=Etransmit(k,d)+Ereceive(k,d)+Efusion(k)=2kEelec+k(εd2+EF)

(4)

2 混合遺傳算法

2.1 遺傳算法(GA)

遺傳算法屬于進化算法(evolutionary algorithms)的一種，該算法通過模仿自然界的選擇與遺傳的原理求解最優(yōu)解。遺傳算法與枚舉、啟發(fā)式算法相比，以生物進化為基礎，所以具有收斂性強、魯棒性強、運算計時少和隨機搜索能力強等優(yōu)點。

2.2 單純形算法(SM)

單純形算法是指在一個多維空間中構建一個多面體，比較多面體的頂點，找出最好、最差和次優(yōu)的頂點；通過單純形中的反射、擴張、壓縮等操作獲得較優(yōu)的探索點，然后探索點取代最差點。重復迭代，替換最差點，這樣逐漸逼近最優(yōu)解。設最優(yōu)點為xb，次優(yōu)點為xg，最差點為xw，反射點為xr，擴張點為xe，壓縮點為xt，收縮點為xf，則有：

反射：xr=xc+θ(xr-xw),θ≤1；

擴張：xe=xe+ρ(xw-xc),ρ>1；

壓縮：xt=xc+?(xw-xc),?<1；

收縮：xf=xc-?(xw-xc),?<1。

2.3 混合遺傳算法(GA-SM)

單純形算法是一種局部尋優(yōu)算法，在一定區(qū)域內(nèi)具有較好的搜索效率。而遺傳算法是一種全局尋優(yōu)算法。通過遺傳算法的并行性，分布式計算解空間中的解，從而提高求解的速度。但遺傳算法的局部搜索效率不高，會導致相同的節(jié)點可能會被搜索很多次，增加了算法的延時，降低了整個算法的效率。單純形算法能解決遺傳算法過早收斂的問題，通過單純形算法對遺傳算法中的節(jié)點進行更新操作，縮小算法范圍。同樣，遺傳算法使單純形走出局部范圍內(nèi)的搜索趨勢，所以引入混合遺傳算法能均衡全局和局部搜索，高效地尋找最優(yōu)路徑。

2.3.1 算法設計

分布在一定監(jiān)測區(qū)域內(nèi)的普通節(jié)點位置固定不變且能量有限，Sink節(jié)點的能量無限。通過廣播的方式，Sink節(jié)點掌握區(qū)域內(nèi)所有節(jié)點的位置和能量信息，廣播消耗的能量很小，所以路徑優(yōu)化的工作由Sink節(jié)點完成。然后從Sink節(jié)點開始廣播要形成通信路徑的消息，告知網(wǎng)絡中的普通節(jié)點生成通信鏈路。

數(shù)據(jù)鏈路形成之后，要實現(xiàn)與Sink節(jié)點的通信，就需要在鏈路中尋找一個簇頭完成通信。在LEACH算法中，選擇小于一個隨機數(shù)的閾值，作為一輪的簇首節(jié)點，在PEGASIS算法中，網(wǎng)絡中的節(jié)點都能與基站通信，簇首的選擇也是隨機的，這樣增加消耗節(jié)點的有限能量，這些節(jié)點在一定階段會出現(xiàn)大量死亡，就縮短了網(wǎng)絡的生存周期。簇頭的選擇既要考慮該節(jié)點的剩余能量，保證有足夠的能量實現(xiàn)與基站的通信，又要考慮該簇頭節(jié)點與基站間的距離問題，節(jié)點距離較遠會消耗過多的能量，增加網(wǎng)絡負載。

如果一個節(jié)點比較忙碌，那么該節(jié)點的剩余能量會相對較少。用τ(vi)表示節(jié)點vi的忙碌程度，E0(vi)表示節(jié)點vi的初始能量，Eall(vi)表示節(jié)點vi在通信過程中消耗的能量。相應公式如下所示：

(5)

設基站用vt表示，那么節(jié)點vi到基站vt的距離用dvt,vi表示，有：

φ(vi)=τ(vi)dvt,vi

(6)

即

(7)

鏈路形成后，可知各節(jié)點的φ(vi)，選取φ(vi)值最小的節(jié)點作為該鏈路的簇頭，實現(xiàn)與Sink節(jié)點的通信。

2.3.2 GA-SM算法步驟

(1)產(chǎn)生遺傳算法的初始種群。設文中節(jié)點的分布范圍為100×100，并在該范圍內(nèi)隨機生成100個節(jié)點，其中Sink節(jié)點的位置為(50,150)。為了產(chǎn)生優(yōu)質(zhì)的初始種群，減少算法優(yōu)化的過程，提高算法整體的效率，文中采用路徑編碼方式，利用均勻分布的偽隨機數(shù)，在監(jiān)測區(qū)域內(nèi)生成相對均勻分布的70條路徑作為遺傳算法的初始種群。

(2)計算個體的適應度值，確定遺傳算法是否收斂。適應度函數(shù)[13]的選取應考慮該鏈路的剩余能量和路徑消耗這兩個方面。路徑消耗是指傳輸信息在傳輸途中的消耗。通過路徑中所有節(jié)點的忙碌情況決定該路徑的剩余能量，如果路徑中多數(shù)節(jié)點處于忙碌狀態(tài)，那么該路徑整體的剩余能量就越少。即路徑X={v1,v2,…,v100}的適應度函數(shù)如下：

(8)

其中，α表示影響節(jié)點忙碌的權重；β表示影響路徑消耗的權重。適應度f的值越小，說明該鏈路越好，遺傳到下一代的可能性就越高。以迭代15次作為遺傳算法的收斂條件，如果滿足收斂條件，則輸出最優(yōu)結(jié)果，否則進行下一步操作。

(3)選擇操作。如果遺傳算法未結(jié)束，就繼續(xù)執(zhí)行選擇操作。由步驟1產(chǎn)生了70條路徑。選擇操作采用輪盤賭選擇算法。根據(jù)公式9決定路徑被選中的概率：

(9)

其中，P(i)指路徑i被選中的概率；Fi=1/fi，fi指路徑i的適應度值。這樣P(i)值越大，被選擇的概率越大，保證了優(yōu)良個體能遺傳到下一代。

(5)變異操作。取變異概率Pm=0.1，從新的種群中隨機選取需要執(zhí)行變異操作的路徑。文中隨機選取變異點，然后通過倒序和插入操作實現(xiàn)變異操作。比如X=(v1,…,vk-1,vk,vk+1,…,v100)，選取變異點vk，執(zhí)行變異操作后，X=(vk+1,…,v100,vk,v1,…,vk-1)。變異操作形成一條新的路徑，增加了種群的多樣性，不陷入局部尋優(yōu)，有效地避免了遺傳算法過早收斂。

若遺傳算法未截止，則進入下一輪的步驟3，直到遺傳算法收斂條件滿足，遺傳算法結(jié)束，得出一個最優(yōu)路徑和一個種群，進入單純形算法。

(6)產(chǎn)生單純形算法的初始種群。已知在無線傳感器網(wǎng)絡中包含100個節(jié)點，那么單純形算法就要求這100個點形成101條路徑方案。遺傳算法結(jié)束后，產(chǎn)生一個最優(yōu)解和包含69個解的種群，即仍是70條路徑。那么再隨機生成31條路徑方案和遺傳算法的70條路徑方案，構成單純形的初始種群。101條路徑作為多維空間中多面體的頂點。頂點的集合為S=(X1,X2,…,X101)，集合S中的每個頂點表示一種路徑方案。通過式8決定各種路徑方案的優(yōu)劣。用Xb表示最優(yōu)方案，Xw表示最差方案，Xg表示次優(yōu)方案，即Xb=minf(Xi)，Xw=maxf(Xi)。

(7)選取單純形算法的質(zhì)心。質(zhì)心Xc決定著算法尋找最優(yōu)路徑方案的方向。除最差路徑方案外，選取與平均適應度函數(shù)值最小的方案作為質(zhì)心Xc。

(10)

|f(Xc)-fave(t)|<δ,0<δ<1

(11)

(8)反射操作。最差路徑方案Xw關于質(zhì)心Xc做反射操作，做最差方案關于質(zhì)心的反方向操作，以便能探索空間中各種可行的路徑方案。作以質(zhì)心Xc為圓心，Xc與Xw距離d(Xc,Xw)為半徑的圓。在這個圓形區(qū)域內(nèi)存在其他路徑方案。找一個與直線XcXw角度γ(0<γ<π)最大的方案。如圖3所示，找出一個反射方案Xr。

(9)具體尋優(yōu)操作。根據(jù)反射操作，判斷該反射方向是否是產(chǎn)生最優(yōu)方案的方向。

(a)若f(Xr)

作以反射點Xr為圓心，距離d(Xr,Xc)為半徑的圓。在圓形區(qū)域內(nèi)找一個與直線XcXr角度最大作為擴張方案。若f(Xe)

(b)若f(Xb)

(d)若f(Xr)>f(Xw)，說明反射操作不可行。調(diào)整尋優(yōu)方向。除最優(yōu)路徑方案外，其他所有路徑方案進行壓縮操作。各路徑中的點分別作以最優(yōu)路徑中的點為圓心，兩點之間的距離為半徑的圓，在圓中尋找與這兩點夾角最大的點，這些點組成壓縮方案Xt。

反射，擴張，收縮方式如圖1所示。

圖1 單純算法執(zhí)行過程

(10)以迭代35次作為單純形算法的截止條件，如果滿足結(jié)束條件，則輸出最優(yōu)結(jié)果，否則繼續(xù)執(zhí)行單純形算法。

混合算法執(zhí)行過程如圖2所示。

圖2 混合遺傳算法執(zhí)行過程

3 實驗仿真及分析

仿真參數(shù)如表1所示。

表1 仿真參數(shù)

從失效節(jié)點的情況、算法收斂速度和能耗三個方面作比較，以體現(xiàn)文中的算法的優(yōu)越性。

3.1 節(jié)點失效仿真

圖3給出在不同的通信輪數(shù)下，GA、GASM和LEACH三種算法節(jié)點失效的情況。LEACH算法的通信輪數(shù)達1 000次左右時，大量節(jié)點死亡。LEACH算法中簇頭的選擇沒考慮節(jié)點能量問題，所以通信輪數(shù)越多，失效節(jié)點的數(shù)目就越多。第一個節(jié)點出現(xiàn)死亡時，文中算法的通信輪數(shù)達到傳統(tǒng)遺傳算法的130%。在60%的節(jié)點死亡前，文中算法的通信輪數(shù)比GA和LEACH算法都多。但在節(jié)點死亡數(shù)達到90%時，GA的通信輪數(shù)和GA-SM差不多，這是因為遺傳算法中輪流選擇節(jié)點作為簇頭節(jié)點，但此時存活的節(jié)點數(shù)很少，失去了研究的意義。文中算法結(jié)合了單純形算法和遺傳算法，單純形算法對遺傳算法形成的優(yōu)質(zhì)種群進行更優(yōu)的操作，替換路徑中能量較少的節(jié)點，使路徑的通信時間更長，所以GA-SM形成的路徑壽命更長，延長了網(wǎng)絡的生存周期。

圖3 死亡節(jié)點對比

3.2 算法收斂速度仿真

GA和GASM算法都進行20次實驗，每次實驗前網(wǎng)絡中節(jié)點的分布是隨機的，給出每次實驗收斂時的迭代次數(shù)，如圖4所示。

圖4 收斂速度

可以看出，GA-SM的收斂速度比GA提高了100%～150%。遺傳算法尋優(yōu)方式是全局尋優(yōu)，搜索范圍很廣，所以算法收斂速度相對較慢。而文中算法是在遺傳算法的基礎上加上單純形算法，單純形算法是一種確定性的局部尋優(yōu)算法，所以該混合算法能加快算法的收斂性，提高尋優(yōu)的速度并且還能提升算法尋找最優(yōu)路徑的質(zhì)量。

3.3 網(wǎng)絡能耗仿真

當網(wǎng)絡中出現(xiàn)第一個節(jié)點死亡時，實驗就結(jié)束，GA-SM、GA和LEACH三種算法分布在區(qū)域內(nèi)節(jié)點的剩余能量如圖5所示。GA-SM算法中剩余能量高的節(jié)點數(shù)所占的比例很少，這是由于每次迭代時，都會尋找能量較高的探索點代替最差點，考慮了能量因素。GA算法也考慮了節(jié)點的能量問題，但剩余能量較多的節(jié)點數(shù)目比混合遺傳算法的多。而LEACH算法生成通信路徑時，沒有考慮能量問題，所以實驗結(jié)束時，含有剩余能量多的節(jié)點數(shù)目遠大于GA-SM和GA算法?；旌线z傳算法有效均衡了節(jié)點能量消耗，提高了網(wǎng)絡的生存周期。

圖5 節(jié)點剩余能量分布

4 結(jié)束語

文中提出的基于遺傳和單純形混合的能耗均衡路由算法，利用了遺傳算法和單純形算法兩者優(yōu)點尋找全局最優(yōu)路徑，然后優(yōu)化簇頭選擇方式，實現(xiàn)節(jié)點與Sink節(jié)點通信。實驗結(jié)果表明，與傳統(tǒng)的LEACH算法、遺傳算法相比，該算法的收斂速度快、網(wǎng)絡生存周期長、能耗低，適合節(jié)點能量有限的無線傳感器網(wǎng)絡。