傅彬

　　(紹興職業(yè)技術(shù)學(xué)院,浙江 紹興 312000)

        摘要：如何能夠降低無(wú)線傳感網(wǎng)中的節(jié)點(diǎn)能量消耗一直都是研究的熱門。針對(duì)基本Leach路由算法存在節(jié)點(diǎn)能量消耗大、負(fù)載不均衡的缺點(diǎn),文章一方面在Leach算法的簇頭選擇中首先進(jìn)行最優(yōu)解計(jì)算,其次通過(guò)遺傳算法的染色體編碼概念對(duì)簇內(nèi)其他節(jié)點(diǎn)能量排序進(jìn)行優(yōu)化,得到最優(yōu)簇頭；另一方面在簇間路由中進(jìn)行最優(yōu)跳數(shù)的確定,引入轉(zhuǎn)發(fā)概率函數(shù)和最優(yōu)中間點(diǎn)的選擇提高路由效率。在仿真實(shí)驗(yàn)中,與基本Leach算法相比，改進(jìn)算法在節(jié)點(diǎn)死亡時(shí)間、數(shù)據(jù)包接收和能量消耗方面都具有明顯的改善。

　　關(guān)鍵詞：無(wú)線傳感；Leach；簇頭；簇間

　　中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.1674-7720.2017.07.021

　　引用格式：傅彬.無(wú)線傳感網(wǎng)中的一種能量均衡算法的研究［J］.微型機(jī)與應(yīng)用，2017,36（7）：70-73，77.

0引言

　　如何能夠降低無(wú)線傳感網(wǎng)中的能量消耗一直都是研究的熱門方向,這主要是因?yàn)闊o(wú)線傳感網(wǎng)的數(shù)據(jù)之間傳輸逐漸增多,能量消耗也在不斷增大。文獻(xiàn)［1］提出一種兼顧節(jié)點(diǎn)密度的能耗均衡分簇算法，仿真實(shí)驗(yàn)表明該算法能夠有效地降低節(jié)點(diǎn)消耗的能量;文獻(xiàn)［2］挑選出最小跳數(shù)和能量高的路徑傳輸,可以有效地降低網(wǎng)絡(luò)的能量消耗,避免節(jié)點(diǎn)的負(fù)載過(guò)大;文獻(xiàn)［3］利用節(jié)點(diǎn)自身的剩余能量和周圍鄰居節(jié)點(diǎn)的平均剩余能量計(jì)算簇頭報(bào)文發(fā)送的標(biāo)志,進(jìn)一步降低了無(wú)效節(jié)點(diǎn)的能量消耗;文獻(xiàn)［4］提出了一種能量潛能機(jī)會(huì)路由算法，取得了比較好的效果;文獻(xiàn)［5］提出一種基于能量均衡的WSN路由算法,該算法采用回退機(jī)制實(shí)現(xiàn)節(jié)點(diǎn)的自適應(yīng)調(diào)整,有效地保證節(jié)點(diǎn)以較高的幾率成為簇首,該算法能夠有效延長(zhǎng)網(wǎng)絡(luò)壽命;文獻(xiàn)［6］提出將監(jiān)測(cè)區(qū)域看成以基站為中心的扇形區(qū)域,并將此劃分為多個(gè)弧形方塊并成為簇,采用單跳和多跳相結(jié)合來(lái)實(shí)現(xiàn)簇間通信;文獻(xiàn)［7］提出將區(qū)域劃分為4個(gè)大小相同的局部區(qū)域,然后選擇節(jié)點(diǎn)能量方差最小的局部區(qū)域作為路由選擇區(qū)域,采用概率機(jī)制選擇路徑傳輸節(jié)點(diǎn);文獻(xiàn)［8］提出一種能量負(fù)載均衡的多跳路由協(xié)議，采用遺傳模擬退火算法進(jìn)行分簇,并計(jì)算每個(gè)簇的聚類中心,在簇間路由階段,采用最短路徑進(jìn)行多跳路由選擇;文獻(xiàn)［9］提出采用布爾傳感模型確定覆蓋率與單位面積內(nèi)傳感器節(jié)點(diǎn)密度的函數(shù)關(guān)系,依靠Prim算法的貪心策略,有效地降低整個(gè)網(wǎng)絡(luò)中的能量消耗。

　　本文在以上研究的基礎(chǔ)上，從改進(jìn)Leach算法作為解決能量負(fù)載不均衡入手,對(duì)算法的簇頭進(jìn)行最優(yōu)解計(jì)算,通過(guò)遺傳算法中的染色體概念對(duì)簇內(nèi)節(jié)點(diǎn)能量排序,同時(shí)引入轉(zhuǎn)發(fā)概率函數(shù)在最優(yōu)中間點(diǎn)中進(jìn)行選擇,提高了算法性能,并通過(guò)實(shí)驗(yàn)說(shuō)明了本文算法具有明顯的改善。

1路由算法與能量消耗關(guān)系簡(jiǎn)述

　　無(wú)線傳感網(wǎng)中的路由選擇是非常關(guān)鍵的,它主要負(fù)責(zé)將數(shù)據(jù)從源節(jié)點(diǎn)傳送到目的節(jié)點(diǎn)。由于其中節(jié)點(diǎn)的能量有限,因此能量均衡是路由算法需要考慮的問(wèn)題。在無(wú)線傳感網(wǎng)中節(jié)點(diǎn)能量有限,路由算法在設(shè)計(jì)過(guò)程中需要將節(jié)點(diǎn)權(quán)重作為參考權(quán)重,使用過(guò)濾機(jī)制,去除大量冗余的數(shù)據(jù),將節(jié)點(diǎn)采集的數(shù)據(jù)進(jìn)行融合,減少不必要的能量消耗；同時(shí)應(yīng)該保持通信負(fù)載的網(wǎng)絡(luò)平衡,在設(shè)計(jì)路由算法時(shí)增加對(duì)路由選擇的隨機(jī)性,避免最優(yōu)路徑節(jié)點(diǎn)頻繁使用而位置較差的節(jié)點(diǎn)使用少而導(dǎo)致節(jié)點(diǎn)過(guò)早死亡。因此下一跳的節(jié)點(diǎn)剩余能量的選擇需要結(jié)合路由算法來(lái)進(jìn)行考慮。

　　Leach協(xié)議是一種經(jīng)典的層次路由協(xié)議,其過(guò)程是循環(huán)更新簇。首先隨機(jī)選擇簇頭節(jié)點(diǎn)并進(jìn)行分簇,其他未加入簇的節(jié)點(diǎn)選擇通信代價(jià)最小的簇節(jié)點(diǎn)加入；其次是所有節(jié)點(diǎn)采集到的數(shù)據(jù)發(fā)給自己所在的簇節(jié)點(diǎn),簇節(jié)點(diǎn)將各個(gè)成員的節(jié)點(diǎn)進(jìn)行信息處理,通過(guò)數(shù)據(jù)融合將數(shù)據(jù)傳遞給基站,通過(guò)不斷地迭代,將簇節(jié)點(diǎn)的能量分?jǐn)偨o簇內(nèi)每一個(gè)節(jié)點(diǎn),降低能量消耗,但其自身存在簇節(jié)點(diǎn)選擇隨機(jī)性、負(fù)載不均衡性和未考慮簇節(jié)點(diǎn)與基站距離等缺點(diǎn)。

2基于改進(jìn)的能量均衡算法的研究

　　針對(duì)Leach算法存在的不足,本文假設(shè)在以下前提下進(jìn)行研究：傳感器節(jié)點(diǎn)已經(jīng)知道自己的位置,節(jié)點(diǎn)之間的傳輸耗能相同。從簇頭選擇和簇間路由進(jìn)行改進(jìn)。

　　2.1Leach簇頭選擇

　　簇頭選擇在無(wú)線傳感網(wǎng)中的分簇算法中是非常重要的,它決定了整個(gè)網(wǎng)絡(luò)的性能。如果一個(gè)簇頭的位置不好或者能量不足就會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)資源的消耗增加,并且還有可能使網(wǎng)絡(luò)性能下降,因此如何選擇簇頭成為解決問(wèn)題的關(guān)鍵。遺傳算法是一種基于自然選擇的生物進(jìn)化算法,通過(guò)染色體編碼進(jìn)行優(yōu)化,從而找到最優(yōu)解。遺傳算法能夠自動(dòng)地控制優(yōu)化的搜索方向,因此非常適合用于復(fù)雜度高的分簇方法。

　　2.1.1最優(yōu)簇頭計(jì)算

　　在無(wú)線傳感網(wǎng)中,假設(shè)有N個(gè)節(jié)點(diǎn)分布在m×m區(qū)域中,分配h個(gè)簇,因此每個(gè)簇內(nèi)平均有N/h個(gè)節(jié)點(diǎn),其中N/h－1為簇內(nèi)非簇頭節(jié)點(diǎn),設(shè)定網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)都是按照多跳傳輸方式進(jìn)行發(fā)送數(shù)據(jù),設(shè)定傳輸距離為D,簇頭的能量消耗包括簇內(nèi)成員的信息、數(shù)據(jù)融合和數(shù)據(jù)傳送三個(gè)部分的能量消耗。因此每個(gè)簇頭節(jié)點(diǎn)的能量消耗為：

　　式中,k為數(shù)據(jù)包大小,EDA為數(shù)據(jù)融合消耗的能量,D是簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)的距離。因此簇內(nèi)節(jié)點(diǎn)與簇頭之間通信的能耗為：

　　Enon－CH=kEelect+kξfsd2toCH(2)

　　其中,dtoCH為成員節(jié)點(diǎn)與簇頭之間的距離。設(shè)定該區(qū)域?yàn)閳A形,簇頭位于簇中間位置,則得到：

　　結(jié)合無(wú)線傳感網(wǎng)中網(wǎng)絡(luò)節(jié)點(diǎn)均勻分布的特點(diǎn),將式(2)和式(3)結(jié)合：

　　因此,簇內(nèi)發(fā)送整個(gè)一幀數(shù)據(jù)的能量消耗為：

　　在覆蓋區(qū)域中,簇內(nèi)發(fā)送一幀數(shù)據(jù)的的總能耗為：

　　對(duì)式(6)求導(dǎo),取其極小值得到最優(yōu)簇頭數(shù)為:

　　2.1.2染色體編碼

　　得到最優(yōu)簇頭數(shù)目之后,采用遺傳算法中的固定長(zhǎng)度的染色體編碼,將最優(yōu)簇頭數(shù)目設(shè)定為染色體長(zhǎng)度。編碼按照節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)來(lái)進(jìn)行衡量。在整個(gè)無(wú)線傳感網(wǎng)中,剩余能量采用如下方法來(lái)獲得：

　　式中,Eave表示整個(gè)無(wú)線傳感網(wǎng)中的剩余平均能量,將節(jié)點(diǎn)剩余能量大于Eave的節(jié)點(diǎn)從1到M編號(hào)來(lái)代替染色體中的0,1編碼。

　　2.2簇間路由選擇

　　在無(wú)線傳感網(wǎng)中,當(dāng)簇形成之后,簇頭節(jié)點(diǎn)收到來(lái)自簇內(nèi)成員的數(shù)據(jù)之后,通過(guò)融合,向基站發(fā)送數(shù)據(jù)。當(dāng)遠(yuǎn)離基站時(shí)，簇頭節(jié)點(diǎn)就會(huì)消耗過(guò)多的能量,因此采用傳統(tǒng)的多跳方式顯然不是很好的解決辦法,本文將多跳與單跳方式相結(jié)合來(lái)降低簇頭與基站之間的信號(hào)消耗。

　　2.2.1最優(yōu)跳數(shù)的確定

　　在半徑為R的無(wú)線傳感區(qū)域內(nèi)分布了N個(gè)節(jié)點(diǎn),將節(jié)點(diǎn)與基站的距離劃分為n個(gè)區(qū)域,半徑為r1,r2,…rn。為了簡(jiǎn)化計(jì)算,假設(shè)簇頭位于區(qū)域中間位置,每個(gè)區(qū)域的寬度為r,大致估算出r1區(qū)域簇頭半徑為r/2,依次類推rn區(qū)域簇頭的半徑為n+(r/2)。當(dāng)處于r1區(qū)域的簇頭節(jié)點(diǎn)向基站發(fā)送數(shù)據(jù)為k時(shí),每個(gè)簇頭能量消耗為：

　　因此,總體耗能為：

　　式(11)中,當(dāng)簇頭與基站的距離小于d0時(shí),使用單跳傳輸；否則,采用多跳傳輸。

　　2.2.2轉(zhuǎn)發(fā)概率函數(shù)

　　在基站點(diǎn)附近的多跳路由都具有節(jié)點(diǎn)能量消耗快的特點(diǎn),因此造成了靠近基站的節(jié)點(diǎn)能量容易過(guò)早消耗的現(xiàn)象,雖然本文之前描述了單跳和多跳傳輸?shù)倪x擇,但仍然存在這樣的問(wèn)題。根據(jù)這種情況,本文設(shè)定一個(gè)轉(zhuǎn)發(fā)概率函數(shù)來(lái)使得簇間的路由在單跳和多跳中進(jìn)行選擇,盡可能地避免因?yàn)榫嚯x的問(wèn)題而產(chǎn)生能耗不均勻的問(wèn)題。轉(zhuǎn)發(fā)公式如下：

　　Fb=rρ×Elast(12)

　　式中,r為簇頭與基站之間的距離,Elast為簇頭內(nèi)的剩余能量,ρ為均衡系數(shù)。通過(guò)概率轉(zhuǎn)發(fā)函數(shù)可以選擇比較好的路由，均衡簇頭之間的能量消耗,有效延長(zhǎng)簇頭壽命。

　　2.2.3最優(yōu)中間節(jié)點(diǎn)選擇

　　簇與簇之間的信息轉(zhuǎn)發(fā)都是通過(guò)中間節(jié)點(diǎn)傳輸?shù)竭_(dá)基站的,因此中間節(jié)點(diǎn)能量消耗也是無(wú)線傳感網(wǎng)中能耗的重要組成部分。假設(shè)中間節(jié)點(diǎn)1、中間節(jié)點(diǎn)2和基站從左到右依次排列,節(jié)點(diǎn)1發(fā)送數(shù)據(jù)到基站必須經(jīng)過(guò)節(jié)點(diǎn)2。節(jié)點(diǎn)1到節(jié)點(diǎn)2的距離為r1,節(jié)點(diǎn)2到基站的距離為r2,節(jié)點(diǎn)1到基站的距離為r,當(dāng)節(jié)點(diǎn)1向基站發(fā)送數(shù)據(jù)時(shí),節(jié)點(diǎn)1到節(jié)點(diǎn)2,以及節(jié)點(diǎn)2到基站的能量消耗為：

　　Enode1=kξfsr21+kEelect(13)

　　Enode2=kξfsr22+kEelect(14)

　　因此傳輸?shù)哪芰靠傁臑椋?/p>

　　Etotal=kξfs(r21+r22)+2kEelect(15)

　　節(jié)點(diǎn)1到基站之間的能量消耗表達(dá)如下：

　　Etotal=kξfs((r－r2)2+r22)+2kEelect(16)

　　通過(guò)式(16)得到r2=r/2時(shí),Etotal達(dá)到最小,根據(jù)這個(gè)原理,無(wú)線傳感網(wǎng)中的簇頭節(jié)點(diǎn)到基站的距離為d時(shí),最優(yōu)的跳數(shù)為dd0,因此轉(zhuǎn)發(fā)距離為：

　　綜上所述,當(dāng)簇頭節(jié)點(diǎn)的坐標(biāo)為(x,y)時(shí),最優(yōu)下一步的中間點(diǎn)的坐標(biāo)為(xopt,yopt),且：

3仿真實(shí)驗(yàn)

　　3.1仿真環(huán)境

　　為了進(jìn)一步說(shuō)明本文算法在降低能量消耗方面的作用,模擬真實(shí)環(huán)境,節(jié)點(diǎn)數(shù)量為1 000個(gè),分布在100 m×100 m的區(qū)域中,基站處于區(qū)域的中心位置(50 m,50 m),節(jié)點(diǎn)之間的最大通信距離為85 m,能量比較高的節(jié)點(diǎn)占據(jù)總節(jié)點(diǎn)數(shù)量的10% ,傳輸能耗ξfs為1×10－11J。 硬件系統(tǒng)CPU采用酷睿i3,內(nèi)存為4 GB，硬盤容易為500 GB。軟件采用Windows 7,仿真環(huán)境為MATLAB2010。

　　3.2仿真結(jié)果分析

　　3.2.1節(jié)點(diǎn)死亡時(shí)間

　　圖1表示了仿真環(huán)境下的節(jié)點(diǎn)有效生存時(shí)間。從圖中可以發(fā)現(xiàn)基本Leach算法的第一個(gè)節(jié)點(diǎn)死亡時(shí)間比本文算法的節(jié)點(diǎn)死亡時(shí)間早,這說(shuō)明基本Leach算法的網(wǎng)絡(luò)效率開(kāi)始下降,當(dāng)經(jīng)過(guò)一段時(shí)間之后,Leach算法仍然有一部分節(jié)點(diǎn)存活時(shí)間長(zhǎng),這說(shuō)明Leach算法負(fù)載不均衡導(dǎo)致了節(jié)點(diǎn)的使用效率低。本文算法的第一個(gè)節(jié)點(diǎn)死亡時(shí)間要晚于基本Leach算法,這是因?yàn)楸疚乃惴ㄔ诖仡^節(jié)點(diǎn)的選擇上使用了單跳與多跳相結(jié)合的方式來(lái)降低網(wǎng)絡(luò)整體的能量消耗。 在整個(gè)網(wǎng)絡(luò)中,本文算法比基本Leach算法具有更好的曲線傾斜度,這說(shuō)明整個(gè)無(wú)線傳感網(wǎng)的節(jié)點(diǎn)死亡時(shí)間更加集中,具有更好的負(fù)載性。

　　3.2.2數(shù)據(jù)包接收

　　圖2表示了基站接收數(shù)據(jù)包的數(shù)據(jù)量與時(shí)間的關(guān)系。在算法運(yùn)行初期,本文算法與基本Leach算法數(shù)據(jù)包是一致的,經(jīng)過(guò)一段時(shí)間后,Leach算法接收的數(shù)據(jù)包有所下降,主要是因?yàn)長(zhǎng)each算法中存在的負(fù)載不均衡問(wèn)題容易導(dǎo)致部分節(jié)點(diǎn)能耗過(guò)大而失效。而本文算法采用單跳與多跳相結(jié)合的方式使得負(fù)載均衡,無(wú)線傳感網(wǎng)絡(luò)的生命周期有所增長(zhǎng),數(shù)據(jù)包接收數(shù)量較基本Leach算法多。

　　3.2.3能量消耗

　　圖3為能量消耗與時(shí)間的關(guān)系,與基本的Leach算法相比,本文算法的總體能量消耗趨于平穩(wěn),這是因?yàn)樵谒惴ǔ跗?本文算法采用了多跳路由算法與基站進(jìn)行通信,一定程度上降低了節(jié)點(diǎn)的能耗,經(jīng)過(guò)一段時(shí)間之后,由于圖3能量消耗與輪數(shù)的關(guān)系

　　大部分節(jié)點(diǎn)已經(jīng)失效,本文算法的覆蓋面積要大于基本Leach算法,因此能耗比較大。從整個(gè)過(guò)程來(lái)看,本文算法的網(wǎng)絡(luò)一直保持比較穩(wěn)定的能量消耗速度,說(shuō)明本文算法具有很好的穩(wěn)定性,這主要是由于簇頭節(jié)點(diǎn)選擇和簇間路由方面都考慮了節(jié)點(diǎn)負(fù)載的均衡性,達(dá)到了在無(wú)線傳感網(wǎng)中的能量均衡目的。

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

　　針對(duì)無(wú)線傳感網(wǎng)中的能量消耗問(wèn)題,本文在Leach算法的基礎(chǔ)上,對(duì)其進(jìn)行改進(jìn),提高了算法的有效性能,降低了能耗。仿真實(shí)驗(yàn)表明,通過(guò)與基本Leach算法在節(jié)點(diǎn)死亡時(shí)間、數(shù)據(jù)包接收和能量消耗方面進(jìn)行對(duì)比，本文方法都具有明顯的改善。

　　參考文獻(xiàn)

　?。?］ 曹立志,陳瑩.基于學(xué)習(xí)自動(dòng)機(jī)的無(wú)線傳感網(wǎng)能量均衡分簇算法［J］.傳感技術(shù)學(xué)報(bào),2013,26(11):1590-1596.

　　［2］ 樊志平,謝冬青,金政哲.無(wú)線傳感網(wǎng)絡(luò)能量有效負(fù)載均衡的多路徑路由策略［J］.小型微型計(jì)算機(jī)系統(tǒng),2013,34(2):253-257.

　?。?］ 陳志.一種能量感知的無(wú)線傳感網(wǎng)拓?fù)淇刂扑惴ǎ跩］.傳感技術(shù)學(xué)報(bào),2013,26(3):382-387.

　?。?］ 田賢忠,肖赟.一種能量捕獲無(wú)線傳感網(wǎng)絡(luò)機(jī)會(huì)路由算法［J］.計(jì)算機(jī)科學(xué),2016，41(s1):288-290.

　?。?］ 李運(yùn)濤,朱敏,劉昊霖,等.基于能量均衡的無(wú)線傳感網(wǎng)絡(luò)路由算法［J］.四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,49(1):69-74.

　?。?］ 張偉龍,郭成芳.基于能量均衡的無(wú)線傳感器網(wǎng)絡(luò)路由算法［J］.激光雜志,2014,35(12):96-98.

　　［7］ 吳三斌,柳強(qiáng),李成博.基于能量均衡的無(wú)線傳感器網(wǎng)絡(luò)路由算法［J］.計(jì)算機(jī)應(yīng)用研究,2012,29(4):1465-1469.

　?。?］ 張世偉,張海濤,張士杰.基于固定分簇和能量均衡的無(wú)線傳感器網(wǎng)絡(luò)多跳路由算法［J］.傳感器與微系統(tǒng),2013,32(8):117-120.

　?。?］ 鄔學(xué)軍.基于能量控制的無(wú)線傳感網(wǎng)絡(luò)最優(yōu)化算法研究［J］.傳感技術(shù)學(xué)報(bào),2011,24(3):436-439.