李新春，高佰勝

(1.遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島125105； 2.遼寧工程技術(shù)大學(xué) 研究生院，遼寧 葫蘆島 125105)

基于最優(yōu)簇數(shù)和改進引力搜索的WSN路由算法

李新春1，高佰勝2*

(1.遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島125105； 2.遼寧工程技術(shù)大學(xué) 研究生院，遼寧 葫蘆島 125105)

為了提高無線傳感器網(wǎng)絡(luò)(WSN)的能量利用效率，提出一種基于最優(yōu)簇數(shù)和改進引力搜索的WSN路由算法(ONCIGS)。首先，根據(jù)非均勻分簇的思想計算最優(yōu)簇數(shù)，并采用改進的凝聚嵌套(AGNES)算法實現(xiàn)網(wǎng)絡(luò)的合理分簇；其次，將反向?qū)W習(xí)機制和精英策略思想引入到引力搜索算法中，并基于種群密度對作用力進行自適應(yīng)調(diào)整，以提高搜索精度，加快收斂；然后，將簇頭剩余能量的標(biāo)準(zhǔn)差作為目標(biāo)函數(shù)，搜索能量均衡的簇間數(shù)據(jù)轉(zhuǎn)發(fā)路徑。實驗結(jié)果表明，相比低功耗自適應(yīng)集簇分層型(LEACH)路由算法和分布式能量均衡非均勻成簇(DEBUC)路由算法，ONCIGS在100 m×100 m網(wǎng)絡(luò)規(guī)模下將網(wǎng)絡(luò)生命周期分別延長41.94%和5.77%,在200 m×200 m網(wǎng)絡(luò)規(guī)模下分別延長76.60%和7.82%。ONCIGS能夠有效地延長網(wǎng)絡(luò)壽命，提高能量效率。

無線傳感器網(wǎng)絡(luò)；非均勻分簇；引力搜索；網(wǎng)絡(luò)能耗；生命周期

0 引言

信息技術(shù)、集成電路及傳感器等技術(shù)的迅猛發(fā)展，使得價廉、功耗低、體積微小并具備一定計算、感知、存儲及通信能力的設(shè)備得以實現(xiàn)，并且部署于各種物理環(huán)境之中，形成了無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)。它主要是為了對覆蓋區(qū)域中的目標(biāo)對象進行感知、收集和處理，并且把消息發(fā)送給監(jiān)測者。監(jiān)測者根據(jù)接收的數(shù)據(jù)了解監(jiān)控區(qū)域情況，并根據(jù)數(shù)據(jù)信息對監(jiān)控區(qū)域作相應(yīng)的改變。由于傳感器節(jié)點的能量非常有限，而且通常情況下能量不能及時得到補充，因此能量效率在無線傳感器網(wǎng)絡(luò)中非常重要，它影響了整個網(wǎng)絡(luò)的壽命[1]。為了提高能量效率，路由問題成為無線傳感器網(wǎng)絡(luò)最具有挑戰(zhàn)性的課題。為了解決此難題，專家學(xué)者提出了多種路由協(xié)議。

低功耗自適應(yīng)集簇分層型(Low Energy Adaptive Cluster Hierarchy, LEACH)路由算法[2]是一種典型的分簇路由協(xié)議，以循環(huán)的方式隨機選擇簇頭節(jié)點，有效降低了節(jié)點能耗，延長了網(wǎng)絡(luò)的整體生存時間，但其簇頭選舉的隨機性導(dǎo)致簇頭分布不合理，且簇間單跳通信的方式導(dǎo)致簇頭的能量消耗過快。文獻[3]提出了能量有效的非均勻成簇(Energy-Efficient Uneven Clustering, EEUC)算法，通過使用非均勻的競爭半徑來構(gòu)造大小不等的簇，使得靠近基站的簇的規(guī)模小于遠離基站的簇，均衡了簇頭能耗，然而簇頭的選擇只由概率和門限值決定，無法保證所選簇頭最優(yōu)。分布式能量均衡非均勻成簇(Distributed Energy-Balanced Unequal Clustering, DEBUC)算法[4]也是采用不同的競爭半徑來實現(xiàn)非均勻分簇，簇頭選舉參考候選簇頭的剩余能量和鄰居節(jié)點的剩余能量，采用基于時間的簇頭競爭算法，在簇間運用貪婪算法選擇中繼節(jié)點，均衡了能耗，但存在離基站較遠的簇規(guī)模過大、節(jié)點能量消耗過多的問題?；诓┺睦碚摰挠行Х执厮惴?Game-theoretic Approach for Efficient Clustering, GAEC)[5]采用博弈的方式選擇簇頭，在分簇的過程中還引入了分區(qū)的思想，但區(qū)域數(shù)量是隨機設(shè)置的，容易導(dǎo)致分簇不合理，且該方法并沒有采用循環(huán)方式更換簇頭，會使得簇頭能量消耗過快而過早死亡。翟春杰等[6]設(shè)計了一種優(yōu)化的分區(qū)算法，將節(jié)點基于區(qū)域的劃分而形成簇，解決了簇的個數(shù)和分布的隨機性問題。為了緩解熱點效應(yīng)，數(shù)據(jù)轉(zhuǎn)發(fā)時隔層選擇下一跳簇頭，但該過程僅僅考慮距離因素，容易導(dǎo)致能量不均。李雙雙等[7]通過非均勻分區(qū)對網(wǎng)絡(luò)進行劃分，而后在各個區(qū)內(nèi)綜合考慮節(jié)點能量、距離和密集程度來選舉簇頭，最后構(gòu)造負載均衡路徑樹實現(xiàn)簇間數(shù)據(jù)的轉(zhuǎn)發(fā)，有效地均衡了能量消耗，但其分區(qū)未考慮節(jié)點的分布特征，任何情況下都采用此分區(qū)模型，因此適應(yīng)性較差?；诜蔷鶆虺纱氐亩嗵酚伤惴?Multi-hop Routing Algorithm based on Uneven Clustering, MRAUC)[8]建立了扇型場景下的無線傳感器網(wǎng)絡(luò)非均勻成簇模型，解決了復(fù)雜、不規(guī)則場景下的高效能組網(wǎng)問題，但其依然根據(jù)傳統(tǒng)的概率閾值來進行臨時簇頭的選舉，引入了隨機性；算法以最小能量消耗原則競選最佳中繼簇頭，然而忽略了簇頭能耗的均衡問題。文獻[9]提出一種基于隨機虛擬骨干樹和改進退避分布式聚類協(xié)議的能量感知路由算法，節(jié)省了網(wǎng)絡(luò)能耗，但算法在全局范圍內(nèi)通過定時廣播競選簇頭時，其延時時長僅由節(jié)點的剩余能量決定，這樣可能導(dǎo)致簇頭分布不合理。在簇間路由階段，基于節(jié)點位置和密度的非均勻分簇路由算法(node Location and node Density based Unbalance Clustering routing algorithm, LDUC)[10]利用通信簇頭節(jié)點來分擔(dān)簇頭的簇間數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，減少了簇頭的能耗，但通信簇頭需要進行額外的選舉過程，增加了控制能耗。文獻[11]提出一種新的基于預(yù)測能量消耗效率的分簇路由算法，選擇簇頭時充分考慮節(jié)點度和節(jié)點間的平均距離，因此簇內(nèi)通信代價很?。辉诳紤]預(yù)測能量消耗、跳數(shù)和傳播延遲的基礎(chǔ)上，利用蜂群優(yōu)化(Bee Colony Optimization, BCO)算法來優(yōu)化簇間數(shù)據(jù)傳輸，提高整體的網(wǎng)絡(luò)性能，降低和平衡整個網(wǎng)絡(luò)的能量消耗，延長網(wǎng)絡(luò)的生存時間。

針對以上一些研究中分簇靈活性和合理性較差的問題，且為均衡能耗、提高節(jié)點能量利用效率、延長網(wǎng)絡(luò)壽命，本文提出一種基于最優(yōu)簇數(shù)和改進引力搜索的WSN路由算法(WSN routing algorithm based on Optimal Number of Clusters and Improved Gravitational Search, ONCIGS)。首先，利用最優(yōu)簇數(shù)對改進的凝聚嵌套(AGglomerative NESting, AGNES)算法進行初始化，實現(xiàn)網(wǎng)絡(luò)的合理分簇；然后，將簇頭剩余能量的標(biāo)準(zhǔn)差作為目標(biāo)函數(shù)，采用改進的引力搜索算法搜索能量均衡的簇間數(shù)據(jù)轉(zhuǎn)發(fā)路徑。實驗結(jié)果表明，ONCIGS可以減少并均衡節(jié)點能耗，從而延長網(wǎng)絡(luò)生命周期。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

本文對網(wǎng)絡(luò)模型作如下假設(shè)：1)N個傳感器節(jié)點隨機分布在M×M監(jiān)測區(qū)域內(nèi)，基站位于監(jiān)測區(qū)域之外。2)基站和所有節(jié)點靜止不動，節(jié)點能量有限，基站能量無限。3)節(jié)點同構(gòu)，即具有相同的屬性，且具有唯一的ID。4)無線信道滿足對稱性，即正向傳輸和反向傳輸?shù)哪芰肯南嗤?)節(jié)點可感知得到自身的位置坐標(biāo)。6)節(jié)點可根據(jù)通信距離調(diào)整無線發(fā)射功率。

1.2 能量模型

本文能量模型采用經(jīng)典的一階無線電模型[12]。將lbit數(shù)據(jù)傳輸d距離所消耗的能量如下：

(1)

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

ERx(l)=lEelec

(2)

1.3 數(shù)據(jù)融合模型

本文通過數(shù)據(jù)融合技術(shù)來減少網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量，進而降低網(wǎng)絡(luò)能量消耗。由于不同簇中采集到的數(shù)據(jù)具有較大差異性，本文仿真不考慮簇間數(shù)據(jù)的融合，只考慮簇內(nèi)的數(shù)據(jù)融合。假設(shè)每個簇內(nèi)成員向簇頭發(fā)送的數(shù)據(jù)包大小為lbit，那么無論簇內(nèi)有多少個成員，簇頭均將接收到的數(shù)據(jù)壓縮為lbit。

2 ONCIGS

網(wǎng)絡(luò)初始化時，每個節(jié)點將自身ID以及感知到的位置坐標(biāo)發(fā)送給基站，以便基站掌握整個網(wǎng)絡(luò)中節(jié)點的分布情況，為之后的運算提供條件。

2.1 非均勻分簇

2.1.1 ONCIGS最優(yōu)簇數(shù)

為了合理分簇，需要先確定最優(yōu)簇數(shù)。目前大多數(shù)涉及最優(yōu)簇數(shù)的研究利用在均勻分簇的前提下推導(dǎo)出的最優(yōu)簇數(shù)來指導(dǎo)非均勻分簇，這樣有失合理性。因此，本文在非均勻分簇的條件下確定最優(yōu)簇數(shù)。

設(shè)將網(wǎng)絡(luò)區(qū)域劃分為k+1個簇，簇半徑在Rc/2到Rc之間等步長選取，那么第i+1個簇的半徑為：

Ri+1=(k+i)Rc/(2k)

(3)

第i+1個簇的面積為：

Si+1=πR2=(k+i)2Rc2π/(4k2)

(4)

(5)

網(wǎng)絡(luò)節(jié)點密度λ=N/M2，則第i+1個簇內(nèi)的節(jié)點數(shù)為：

(6)

設(shè)第i+1個簇內(nèi)普通節(jié)點到簇頭的距離為dtoCH，則有：

(7)

其中ρ(x,y)為簇內(nèi)普通節(jié)點的分布密度，計算式如下：

(8)

那么第i+1個簇內(nèi)的成員節(jié)點平均消耗的能量為：

Emember=lEelec+lεfsdtoCH2

(9)

其簇頭消耗的能量為：

ECH=(Ni+1-1)lEelec+Ni+1lEDA+lEelec+lεampdtoBS4

(10)

則第i+1個簇的總能耗為：

Ei+1=ECH+(Ni+1-1)Emember=lEelec(2Ni+1-1)+

Ni+1lEDA+lεampdtoBS4+(Ni+1-1)lεfsdtoCH2

(11)

因此，整個網(wǎng)絡(luò)每一輪的總能耗為：

(12)

(13)

其中：

a=-3 840M2Eelec+3 840M2εampdtoBS4-1 120M2εfsRc2

(14)

b=-280εfsRc4πN+80M2εfsRc2

(15)

c=12εfsRc4πN

(16)

2.1.2 基于改進AGNES聚類的非均勻分簇

確定了最優(yōu)簇數(shù)，本文采用凝聚嵌套(AGNES)算法[13]進行網(wǎng)絡(luò)節(jié)點的聚類。AGNES是一種采用自底向上聚合策略的層次聚類算法，它先將數(shù)據(jù)集中的每個樣本看作一個初始聚類簇，然后在算法運行的每一步中找出距離最近的兩個聚類簇進行合并，該過程不斷重復(fù)，直至達到預(yù)設(shè)的聚類簇個數(shù)[13]。為了緩解能量空洞，需要對AGNES進行必要的改進，實現(xiàn)分簇的非均勻。

定義1 相對鄰近度RC(Ci,Cj)為：

(17)

其中：Ci與Cj分別表示簇i和簇j；ED(Ci)為Ci到基站的距離，具體表示如式(18)；EDmax為當(dāng)前所有簇到基站距離的最大值。

ED(Ci)=

(18)

其中：|Ci|表示Ci內(nèi)的傳感器節(jié)點個數(shù)；xk、yk分別表示Ci內(nèi)節(jié)點k的橫、縱坐標(biāo)；xBS、yBS分別表示基站的橫、縱坐標(biāo)。相對鄰近度衡量了簇對到基站的距離，簇對到基站距離越大，相對鄰近度越大。

定義2 合并開關(guān)因子TH(Ci,Cj)為：

(19)

其中：dmax(Ci,Cj)表示Ci與Cj的最大距離，具體表示如式(20)；φ為限制因子；Rc(Ci,Cj)為限制簇半徑，表達式如式(21)所示。

(20)

其中：dist(x,z)表示節(jié)點x與節(jié)點z的歐氏距離。

(21)

關(guān)于兩個簇之間的距離，本文采用平均距離：

(22)

綜合上述定義，設(shè)計簇對Ci與Cj對應(yīng)的權(quán)值S如下：

(23)

其中：α由用戶指定，用于調(diào)節(jié)相對鄰近度的權(quán)重。權(quán)值S綜合考慮了簇對距離、簇對到基站距離以及簇對合集的幾何尺寸。在聚合的過程中，簇對是否合并不再像原始算法那樣僅僅由簇對之間的距離決定，而是將最大的S值所對應(yīng)的兩個簇合并。那么算法運行時，在簇對合集的規(guī)模不超過限定值即TH(Ci,Cj)=1的前提下，距離基站較遠的相鄰簇對具有較大的相對鄰近度，而距離基站較近的簇對相對鄰近度較小，那么如果此時的davg(Ci,Cj)值大小相當(dāng)，則距離基站較遠的相鄰簇對權(quán)值S較大，即具有較大的可能性合并在一起，而距離基站較近的簇對合并的可能性較小；從而基站附近的簇幾何規(guī)模較小，遠離基站的簇幾何規(guī)模較大，實現(xiàn)了非均勻分簇，基站附近的簇頭將預(yù)留出更多能量來完成數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)。如果某簇對合集的簇幾何尺寸超出限定值，則TH(Ci,Cj)=0，該簇對的權(quán)值S被置零，不具備合并可能性。

非均勻分簇過程的流程如圖1所示。

圖1 非均勻分簇過程流程Fig. 1 Flow chart of uneven clustering process

考慮到降低能耗，本文避免在每一輪都進行重新分簇，而只是在網(wǎng)絡(luò)初始化階段和死亡節(jié)點比例每上升10%時進行分簇操作，簇頭選舉和路由選擇則是每輪都需要進行。分簇完成之后，基站將分簇結(jié)果發(fā)送給網(wǎng)絡(luò)節(jié)點。

2.2 簇頭選舉

為了降低算法復(fù)雜度，本文簇頭的選舉采用文獻[14]的定時廣播方法，等待時間的長短取決于節(jié)點剩余能量的大小，擁有較多剩余能量的節(jié)點有更大的機會當(dāng)選為簇頭。普通節(jié)點接收到其所屬簇的簇頭消息后，向簇頭發(fā)送加入請求消息，簇頭回復(fù)請求并分配時隙，而后開始數(shù)據(jù)的采集與上傳。

考慮到節(jié)省能耗，如果當(dāng)選簇頭沒有改變，依然為上一輪的簇頭，則簇內(nèi)節(jié)點無需發(fā)送加入請求，簇頭也無需重新分配時隙，可直接按照上一輪的拓撲結(jié)構(gòu)和時間表來運行。

2.3 簇的路由

為了均衡簇間能耗，簇間路由結(jié)合改進的引力搜索算法(Gravitational Search Algorithm, GSA)，尋找各簇頭與基站之間的最優(yōu)路徑，簇頭沿著最優(yōu)路徑將數(shù)據(jù)轉(zhuǎn)發(fā)到基站。

2.3.1 改進的引力搜索算法

引力搜索算法(GSA)[15]是一種基于牛頓萬有引力定律和運動定律的啟發(fā)式搜索算法。假設(shè)在一個D維的搜索空間中有N個搜索粒子，其中第i個粒子在該搜索空間中的位置為：

(24)

以第t次迭代的執(zhí)行過程為例，對算法的實現(xiàn)描述如下。

GSA首先初始化各粒子的位置，并計算粒子的適應(yīng)度值。適應(yīng)度值決定了粒子慣性質(zhì)量的大小，使用以下計算式更新粒子的慣性質(zhì)量：

mi(t)=[fi(t)-w(t)]/[b(t)-w(t)]

(25)

(26)

其中：fi(t)表示粒子i的適應(yīng)度值；b(t)、w(t)分別表示種群中的最優(yōu)適應(yīng)度值和最差適應(yīng)度值。

粒子i受到粒子j在第k維上的作用力大小為：

(27)

其中：G(t)是引力常量；Rij(t)表示粒子i和粒子j的歐氏距離；ε是一個很小的常量。

粒子i在第k維上受到的合力為：

(28)

其中：rankj是0到1之間的隨機數(shù)。

依據(jù)牛頓第二定律，粒子i在第k維上的加速度為：

(29)

粒子i在第k維上的速度和位置使用式(30)更新：

(30)

針對基本GSA易陷入局部最優(yōu)的問題，本文首先引入反向?qū)W習(xí)機制[16]，以增強種群的多樣性；隨后結(jié)合精英策略思想，來提高種群的質(zhì)量。

(31)

(32)

F=Rm×rand(-0.5,0.5)/D

(33)

Xi_new=Xi_best×F

(34)

其中：因子F描述了新粒子的產(chǎn)生規(guī)則；Rm表示最優(yōu)粒子與離其最近的粒子之間的歐氏距離；rand(-0.5,0.5)表示[-0.5,0.5]范圍內(nèi)的隨機數(shù)；D為搜索空間的維數(shù)；Xi_new為產(chǎn)生的新粒子的位置。利用Xi_new(i=1,2,…,2N/5)替代合集中后20%較差的粒子，并將合集中的粒子重新排序，最后保留前N個粒子，其余舍棄，至此，種群更新完成。

GSA迭代后期，粒子在最優(yōu)解附近聚集，種群密度較大，因此粒子間相互作用力會變得非常大，導(dǎo)致粒子在最優(yōu)解附近高速振蕩而減慢收斂速度。針對這一問題，本文首先定義種群密度因子。

定義3 種群密度因子δ為：

(35)

其中：N為粒子個數(shù)；δi表示粒子i和其他所有粒子的平均距離，表達式如式(36)所示。

(36)

根據(jù)式(35)對式(27)進行改進：

(37)

其中，Ep(δ)采用如下設(shè)計：

其中：Epmin和Epmax分別表示Ep(δ)的最小值和最大值。如此設(shè)計，當(dāng)種群密度過大時，Rij(t)的指數(shù)變小，那么粒子間的距離對相互作用力的影響也變小，相距很近的粒子間作用力不至于過大，算法的收斂能力得以提升。

2.3.2 基于改進引力搜索的路由

設(shè)網(wǎng)絡(luò)中有7個簇頭節(jié)點，簇頭集合為{CH1,CH2,…,CH7}。在[0,1]范圍內(nèi)隨機產(chǎn)生N個粒子，粒子的維數(shù)為簇頭節(jié)點的個數(shù)，每個粒子代表一種多跳路徑。

統(tǒng)計每個簇頭通信范圍內(nèi)的前向簇頭節(jié)點，構(gòu)建候選下一跳簇頭列表，假設(shè)如表1所示。

表1 候選下一跳簇頭列表Tab. 1 List of candidate next-hop cluster heads

簇頭CHk在其候選下一跳簇頭集合中選擇第nk個簇頭作為最終的下一跳，nk的取值如下：

(39)

為均衡簇頭能耗、延長網(wǎng)絡(luò)壽命，本文將簇頭剩余能量的標(biāo)準(zhǔn)差作為改進GSA的適應(yīng)值函數(shù)，具體表示如下：

(40)

E(i)=Eb(i)-ERx(ldata×PackNum(i))-

ETx(ldata×(PackNum(i)+1),dnext(i))

(41)

其中：Eb表示簇間通信開始前簇頭i的剩余能量；ldata為數(shù)據(jù)包大小；PackNum(i)表示簇頭i接收到的數(shù)據(jù)包個數(shù)；dnext(i)表示簇頭i與下一跳簇頭的距離。

優(yōu)化過程的詳細步驟如下：

步驟1 在[0,1]區(qū)間內(nèi)隨機初始化種群。

步驟2 依據(jù)粒子位置和候選下一跳簇頭列表得到各粒子所代表的多跳路徑，計算各粒子的適應(yīng)度值，并更新b(t)和w(t)。

步驟3 計算粒子的慣性質(zhì)量。

步驟4 計算粒子所受合力。

步驟5 計算粒子的加速度。

步驟6 更新粒子的速度和位置。

步驟7 如果rand(0,1)

步驟8 跳轉(zhuǎn)至步驟2繼續(xù)執(zhí)行，直到達到最大迭代次數(shù)。

3 實驗仿真與分析

為了充分驗證ONCIGS的性能，本文利用Matlab仿真軟件在不同的環(huán)境下對ONCIGS、LEACH和DEBUC算法進行仿真分析，網(wǎng)絡(luò)環(huán)境分為兩種：網(wǎng)絡(luò)覆蓋面積100 m×100 m，節(jié)點數(shù)量100個，基站位置(50,0) m；網(wǎng)絡(luò)覆蓋面積200 m×200 m，節(jié)點數(shù)量400個，基站位置(100,0) m。節(jié)點初始能量設(shè)置為0.5 J，ETx=ERx=Eelec=50 nJ/bit，εfs=10 pJ/(bit·m2)，εamp=0.001 3 pJ/(bit·m4)，數(shù)據(jù)融合能耗設(shè)定為EDA=5 nJ/bit，閾值d0=87 m，數(shù)據(jù)包大小4 000 bit，控制包大小200 bit。對于ONCIGS算法，取c=0.5、φ=1、α=0.5、Epmin=0.5、Epmax=1。

3.1 最優(yōu)簇數(shù)

兩種網(wǎng)絡(luò)規(guī)模中簇數(shù)與每輪總能耗的關(guān)系曲線如圖2所示。從圖2中看出，隨著簇數(shù)的增加，網(wǎng)絡(luò)一輪總能耗呈現(xiàn)出先降低后增長的趨勢，且兩條曲線分別在簇數(shù)為4和9時總能耗達到最低。這是因為簇數(shù)較少時，簇的幾何規(guī)模較大，則簇內(nèi)節(jié)點的通信距離較大，導(dǎo)致了網(wǎng)絡(luò)總能耗較大；而簇數(shù)較多會增加簇間通信的任務(wù)量，也將導(dǎo)致總能耗較大。因此，由圖2可知，網(wǎng)絡(luò)規(guī)模100 m×100 m時的最優(yōu)簇數(shù)為4個，網(wǎng)絡(luò)規(guī)模200 m×200 m時的最優(yōu)簇數(shù)為9個。本文采用此數(shù)值對AGNES進行初始化。

圖2 不同網(wǎng)絡(luò)規(guī)模最優(yōu)簇數(shù)Fig. 2 Optimal number of clusters for different network sizes

3.2 網(wǎng)絡(luò)生命周期

在兩種網(wǎng)絡(luò)規(guī)模下三種算法的網(wǎng)絡(luò)生命周期對比如圖3所示。本文將從網(wǎng)絡(luò)開始運行到20%節(jié)點死亡的輪數(shù)定義為網(wǎng)絡(luò)的生命周期。由圖3可知，網(wǎng)絡(luò)規(guī)模為100 m×100 m時，LEACH、DEBUC和ONCIGS的生命周期分別為465輪、624輪和660輪，相比于LEACH和DEBUC，ONCIGS分別將生命周期延長41.94%和5.77%；網(wǎng)絡(luò)規(guī)模為200 m×200 m時，三種算法的生命周期分別為359輪、588輪和634輪，分別將生命周期延長76.60%和7.82%。

以上數(shù)據(jù)表明，相對于LEACH和DEBUC算法，ONCIGS可有效延長網(wǎng)絡(luò)生命周期。這是因為ONCIGS首先求出非均勻分簇下的最佳簇數(shù)，而后采用改進的AGNES算法進行聚類，并將上述最佳簇數(shù)作為迭代的截止條件，分簇更加合理，簇內(nèi)能耗更低。

3.3 網(wǎng)絡(luò)總能耗

隨著網(wǎng)絡(luò)的運行，三種算法網(wǎng)絡(luò)總能耗的變化情況如圖4所示。從圖4中可以看出，從網(wǎng)絡(luò)開始運行到網(wǎng)絡(luò)能量全部耗盡之前，ONCIGS的總能耗始終低于LEACH和DEBUC算法，這說明ONCIGS能夠有效降低網(wǎng)絡(luò)的能量消耗。

首先，ONCIGS在基于最優(yōu)簇數(shù)進行合理分簇的前提下，通過改進的GSA搜索出理想的多跳路徑，依此進行數(shù)據(jù)包的轉(zhuǎn)發(fā)，簇間通信能耗得以減少；其次，ONCIGS避免了其余兩種算法頻繁分簇的問題，本文方法只在網(wǎng)絡(luò)初始化和死亡節(jié)點比例每上升一定百分點時才進行分簇操作，這進一步降低了能耗。

圖3 不同網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)生命周期對比Fig. 3 Comparison of network life cycle for different network sizes

圖4 不同網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)總能耗對比Fig. 4 Comparison of network total energy consumption for different network sizes

3.4 網(wǎng)絡(luò)節(jié)點平均剩余能量

三種算法的節(jié)點平均剩余能量對比如圖5所示。從圖5中可以看出，在兩種網(wǎng)絡(luò)規(guī)模下，ONCIGS的節(jié)點平均剩余能量均明顯高于其余兩種算法，而較高的節(jié)點平均剩余能量能夠反映出較均衡的能量消耗，因此ONCIGS有效均衡了網(wǎng)絡(luò)能耗。

在路由階段，ONCIGS采用改進的GSA進行多跳路徑的搜索，且將簇頭剩余能量的標(biāo)準(zhǔn)差作為搜索的目標(biāo)函數(shù)，均衡了簇頭能耗。

圖5 不同網(wǎng)絡(luò)規(guī)模節(jié)點平均剩余能量對比Fig. 5 Comparison of average residual energy of nodes for different network sizes

4 結(jié)語

針對現(xiàn)有一些協(xié)議分簇機制或路由機制不完善而導(dǎo)致網(wǎng)絡(luò)節(jié)點能量利用效率較低的問題，本文提出一種基于最優(yōu)簇數(shù)和改進引力搜索的WSN路由算法ONCIGS。首先，推導(dǎo)出非均勻分簇條件下的最優(yōu)簇數(shù)，并通過改進的AGNES算法實現(xiàn)最優(yōu)數(shù)目的非均勻分簇；然后，采用改進GSA搜索能量均衡度較高的簇間多跳路徑。仿真結(jié)果表明，ONCIGS能夠在有效降低網(wǎng)絡(luò)能耗的同時均衡節(jié)點能耗，提高節(jié)點能量的利用效率，進而延長網(wǎng)絡(luò)生命周期。本文雖取得一定成果，但研究是在節(jié)點位置固定的假設(shè)下進行，且對于大規(guī)模網(wǎng)絡(luò)的路由算法研究仍顯不足。因此，進一步的工作將著重于節(jié)點移動的大規(guī)模無線傳感器網(wǎng)絡(luò)路由算法的研究。

References)

[1] 徐晶晶,張欣慧,許必宵,等.無線傳感器網(wǎng)絡(luò)分簇算法綜述[J].計算機科學(xué),2017,44(2):31-37.(XU J J, ZHANG X H, XU B X, et al. Survey of clustering algorithms for wireless sensor networks [J]. Computer Science, 2017, 44(2): 31-37.)

[2] HEINZELMAN W B, CHANDRAKASAN A, BALAKRISHAM H. Energy-efficient communication protocol for wireless microsensor networks [C] // Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Piscataway, NJ: IEEE, 2000: 3005-3014.

[3] 李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計算機學(xué)報,2007,30(1):27-36.(LI C F, CHEN G H, YE M, et al. An uneven cluster-based routing protocol for wireless sensor networks [J]. Chinese Journal of Computers, 2007, 30(1): 27-36.)

[4] 蔣暢江,石為人,唐賢倫,等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].軟件學(xué)報,2012,23(5):1222-1232.(JIANG C J, SHI W R, TANG X L, et al. Energy-balanced unequal clustering routing protocol for wireless sensor networks [J]. Journal of Software, 2012, 23(5):1222-1232.)

[5] XU Z Y, YIN Y, WANG J, et al. A game-theoretic approach for efficient clustering in wireless sensor networks [J]. International Journal of Hybrid Information Technology, 2014, 7(1): 67-80.

[6] 翟春杰,徐建閩,劉永桂.基于分區(qū)的能耗均衡路由協(xié)議[J].傳感技術(shù)學(xué)報,2016,29(1):80-87.(ZHAI C J, XU J M, LIU Y G. Energy-consumption balancing routing protocol based on regions [J]. Chinese Journal of Sensors and Actuators, 2016, 29(1): 80-87.)

[7] 李雙雙,楊文忠,吳向前.基于非均等分區(qū)的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計算機應(yīng)用,2016,36(11):3010-3015.(LI S S, YANG W Z, WU X Q. Routing protocol based on unequal partition area for wireless sensor network [J]. Journal of Computer Applications, 2016, 36(11): 3010-3015.)

[8] 吳標(biāo),崔琛,余劍,等.基于非均勻成簇的無線傳感器網(wǎng)絡(luò)多跳路由算法[J].計算機科學(xué),2017,44(2):157-162.(WU B, CUI C, YU J. et al. Multi-hop routing algorithm for wireless sensor networks based on uneven clustering [J]. Computer Science, 2017, 44(2): 157-162.)

[9] 馮建平,李華.隨機虛擬骨干樹結(jié)合改進BDCP的無線傳感器網(wǎng)絡(luò)多級路由算法[J].計算機應(yīng)用研究,2016,33(8):2454-2457,2461.(FENG J P, LI H. Multi-level routing algorithm of WSN based on fusion of random virtual backbone trees and backoff distributed clustering [J]. Application Research of Computers, 2016, 33(8): 2454-2457, 2461.)

[10] 顏然,楊云,史庭俊,等.一種基于節(jié)點位置和密度的非均勻分簇路由算法[J].計算機科學(xué),2015,42(8):65-69.(YAN R, YANG Y, SHI T J, et al. Uneven cluster routing algorithm based on node location and node density [J]. Computer Science, 2015, 42(8): 65-69.)

[11] ZHANG D G, WANG X, SONG X D, et al. A new clustering routing method based on PECE for WSN [J]. EURASIP Journal on Wireless Communications and Networking, 2015, 2015(1): 162.

[12] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[13] 周志華.機器學(xué)習(xí)[M].北京:清華大學(xué)出版社,2016:214-215.(ZHOU Z H. Machine Learning [M]. Beijing: Tsinghua University Press, 2016: 214-215.)

[14] 尚鳳軍,任東海.無線傳感器網(wǎng)絡(luò)中分布式多跳路由算法研究[J].傳感技術(shù)學(xué)報,2012,25(4):529-535.(SHANG F J, REN D H. A distributed multi-hop routing algorithm in wireless sensor networks [J]. Chinese Journal of Sensors and Actuators, 2012, 25(4): 529-535.)

[15] RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA: a gravitational search algorithm [J]. Information Sciences, 2009, 179 (13): 2232-2248.

[16] TIZHOOSH H R. Opposition-based learning: a new scheme for machine intelligence [C] // Proceedings of the 2005 International Coference on Computational Intelligence for Modeling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce. Washington, DC: IEEE Computer Society, 2005: 695-701.

LIXinchun, born in 1963, M. S., senior engineer. His research interests include wireless sensor network.

GAOBaisheng, born in 1992, M. S. candidate. His research interests include wireless sensor network.

WSNroutingalgorithmbasedonoptimalnumberofclustersandimprovedgravitationalsearch

LI Xinchun1, GAO Baisheng2*

(1.SchoolofElectronicsandInformationEngineering,LiaoningTechnicalUniversity,HuludaoLiaoning125105,China;2.SchoolofGraduate,LiaoningTechnicalUniversity,HuludaoLiaoning125105,China)

In order to improve the energy efficiency of Wireless Sensor Network (WSN), a WSN routing algorithm based on Optimal Number of Clusters and Improved Gravitational Search (ONCIGS) was proposed. Firstly, the optimal number of clusters was calculated according to the idea of uneven clustering, and the improved AGglomerative NESting (AGNES) algorithm was adopted to realize the reasonable clustering of network. Secondly, reverse learning mechanism and elite strategy were introduced into the gravitational search algorithm, and the force was adjusted adaptively based on population density to improve the search precision and speed up the convergence. Then, the standard deviation of residual energy of cluster heads was taken as the objective function to search the energy-balanced inter-cluster data forwarding path. The experimental results show that, compared with the Low Energy Adaptive Clustering Hierarchy (LEACH) routing algorithm and Distributed Energy Balanced Unequal Clustering (DEBUC) routing algorithm, the network life cycle of the proposed ONCIGS is prolonged by 41.94% and 5.77% respectively under the network scale of 100 m×100 m, and it is prolonged by 76.60% and 7.82% respectively under the network scale of 200 m×200 m. The proposed ONCIGS can effectively prolong network lifetime and improve energy efficiency.

Wireless Sensor Network (WSN); uneven clustering; gravitational search; network energy consumption; life cycle

2017- 06- 15;

2017- 08- 27。

李新春(1963—)，男，遼寧朝陽人，高級工程師，碩士，主要研究方向：無線傳感器網(wǎng)絡(luò)； 高佰勝(1992—)，男，遼寧鐵嶺人，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)。

1001- 9081(2017)12- 3374- 07

10.11772/j.issn.1001- 9081.2017.12.3374

(*通信作者電子郵箱2506616143@qq.com)

TP393.04

A