基于最優簇數和改進引力搜索的WSN路由算法

李新春，高佰勝

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

基于最優簇數和改進引力搜索的WSN路由算法

李新春1，高佰勝2*

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

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

無線傳感器網絡；非均勻分簇；引力搜索；網絡能耗；生命周期

0 引言

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

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

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

1 系統模型

1.1 網絡模型

本文對網絡模型作如下假設：1)N個傳感器節點隨機分布在M×M監測區域內，基站位于監測區域之外。2)基站和所有節點靜止不動，節點能量有限，基站能量無限。3)節點同構，即具有相同的屬性，且具有唯一的ID。4)無線信道滿足對稱性，即正向傳輸和反向傳輸的能量消耗相同。5)節點可感知得到自身的位置坐標。6)節點可根據通信距離調整無線發射功率。

1.2 能量模型

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

(1)

接收lbit數據所消耗的能量為：

ERx(l)=lEelec

(2)

1.3 數據融合模型

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

2 ONCIGS

網絡初始化時，每個節點將自身ID以及感知到的位置坐標發送給基站，以便基站掌握整個網絡中節點的分布情況，為之后的運算提供條件。

2.1 非均勻分簇

2.1.1 ONCIGS最優簇數

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

設將網絡區域劃分為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)

網絡節點密度λ=N/M2，則第i+1個簇內的節點數為：

(6)

設第i+1個簇內普通節點到簇頭的距離為dtoCH，則有：

(7)

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

(8)

那么第i+1個簇內的成員節點平均消耗的能量為：

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)

因此，整個網絡每一輪的總能耗為：

(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聚類的非均勻分簇

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

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

(17)

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

ED(Ci)=

(18)

其中：|Ci|表示Ci內的傳感器節點個數；xk、yk分別表示Ci內節點k的橫、縱坐標；xBS、yBS分別表示基站的橫、縱坐標。相對鄰近度衡量了簇對到基站的距離，簇對到基站距離越大，相對鄰近度越大。

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

(19)

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

(20)

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

(21)

關于兩個簇之間的距離，本文采用平均距離：

(22)

綜合上述定義，設計簇對Ci與Cj對應的權值S如下：

(23)

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

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

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

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

2.2 簇頭選舉

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

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

2.3 簇的路由

為了均衡簇間能耗，簇間路由結合改進的引力搜索算法(Gravitational Search Algorithm, GSA)，尋找各簇頭與基站之間的最優路徑，簇頭沿著最優路徑將數據轉發到基站。

2.3.1 改進的引力搜索算法

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

(24)

以第t次迭代的執行過程為例，對算法的實現描述如下。

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

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

(25)

(26)

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

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

(27)

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

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

(28)

其中：rankj是0到1之間的隨機數。

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

(29)

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

(30)

針對基本GSA易陷入局部最優的問題，本文首先引入反向學習機制[16]，以增強種群的多樣性；隨后結合精英策略思想，來提高種群的質量。

(31)

(32)

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

(33)

Xi_new=Xi_best×F

(34)

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

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

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

(35)

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

(36)

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

(37)

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

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

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

設網絡中有7個簇頭節點，簇頭集合為{CH1,CH2,…,CH7}。在[0,1]范圍內隨機產生N個粒子，粒子的維數為簇頭節點的個數，每個粒子代表一種多跳路徑。

統計每個簇頭通信范圍內的前向簇頭節點，構建候選下一跳簇頭列表，假設如表1所示。

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

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

(39)

為均衡簇頭能耗、延長網絡壽命，本文將簇頭剩余能量的標準差作為改進GSA的適應值函數，具體表示如下：

(40)

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

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

(41)

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

優化過程的詳細步驟如下：

步驟1 在[0,1]區間內隨機初始化種群。

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

步驟3 計算粒子的慣性質量。

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

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

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

步驟7 如果rand(0,1)

步驟8 跳轉至步驟2繼續執行，直到達到最大迭代次數。

3 實驗仿真與分析

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

3.1 最優簇數

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

圖2 不同網絡規模最優簇數Fig. 2 Optimal number of clusters for different network sizes

3.2 網絡生命周期

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

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

3.3 網絡總能耗

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

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

圖3 不同網絡規模網絡生命周期對比Fig. 3 Comparison of network life cycle for different network sizes

圖4 不同網絡規模網絡總能耗對比Fig. 4 Comparison of network total energy consumption for different network sizes

3.4 網絡節點平均剩余能量

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

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

圖5 不同網絡規模節點平均剩余能量對比Fig. 5 Comparison of average residual energy of nodes for different network sizes

4 結語

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

References)

[1] 徐晶晶,張欣慧,許必宵,等.無線傳感器網絡分簇算法綜述[J].計算機科學,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] 李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報,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] 蔣暢江,石為人,唐賢倫,等.能量均衡的無線傳感器網絡非均勻分簇路由協議[J].軟件學報,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] 翟春杰,徐建閩,劉永桂.基于分區的能耗均衡路由協議[J].傳感技術學報,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] 李雙雙,楊文忠,吳向前.基于非均等分區的無線傳感器網絡路由協議[J].計算機應用,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] 吳標,崔琛,余劍,等.基于非均勻成簇的無線傳感器網絡多跳路由算法[J].計算機科學,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] 馮建平,李華.隨機虛擬骨干樹結合改進BDCP的無線傳感器網絡多級路由算法[J].計算機應用研究,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] 顏然,楊云,史庭俊,等.一種基于節點位置和密度的非均勻分簇路由算法[J].計算機科學,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] 周志華.機器學習[M].北京:清華大學出版社,2016:214-215.(ZHOU Z H. Machine Learning [M]. Beijing: Tsinghua University Press, 2016: 214-215.)

[14] 尚鳳軍,任東海.無線傳感器網絡中分布式多跳路由算法研究[J].傳感技術學報,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—)，男，遼寧朝陽人，高級工程師，碩士，主要研究方向：無線傳感器網絡； 高佰勝(1992—)，男，遼寧鐵嶺人，碩士研究生，主要研究方向：無線傳感器網絡。

1001- 9081(2017)12- 3374- 07

10.11772/j.issn.1001- 9081.2017.12.3374

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

TP393.04

A