大規(guī)模無線傳感網基于CFSFDP和泊松混合模型的分簇路由算法*

陶志勇,王和章,劉 影

(遼寧工程技術大學電子與信息工程學院,遼寧 葫蘆島 125105)

大規(guī)模無線傳感網基于CFSFDP和泊松混合模型的分簇路由算法*

陶志勇*,王和章,劉 影

(遼寧工程技術大學電子與信息工程學院,遼寧 葫蘆島 125105)

針對無線傳感網隨規(guī)模的擴大其節(jié)點能量利用率較低的問題,提出了一種適用于大規(guī)模無線傳感網的基于CFSFDP和泊松混合模型的分簇路由算法(CRCPMM)。其核心思想是:在基站利用改進的CFSFDP算法自動估計簇的數目K值并選取聚類中心,然后運用泊松混合模型將節(jié)點合理聚類,以保證聚類效果最優(yōu);簇間采用多跳傳輸方式,綜合考慮簇首等效剩余能量、簇首之間的距離以及多跳路徑與理想最優(yōu)路徑之間的角度。仿真結果表明:與低功耗自適應集簇(LEACH)協(xié)議、分布式能量有效非均勻成簇(DEBUC)協(xié)議相比,CRCPMM協(xié)議在大規(guī)模網絡中具有明顯的優(yōu)勢,能夠有效均衡節(jié)點能耗,延長網絡生命周期。

無線傳感器網絡;能耗均衡;CFSFDP;泊松混合模型;角度

隨著MEMS(Micro Electro Mechanical System)和無線通信技術的發(fā)展,無線傳感器網絡WSN(Wireless Sensor Networks)的應用越來越廣泛,如軍事偵察、醫(yī)療監(jiān)護等[1]。WSN是由大量廉價的具有一定計算、存儲和通信能力的傳感器節(jié)點相互協(xié)作而形成的,傳感器節(jié)點一般采用能量受限的電池供電,且部署后無法更換,這嚴重限制了WSN的發(fā)展[2]。由于傳感器節(jié)點的能耗與網絡的路由息息相關,因此如何設計能量高效的路由協(xié)議成為了WSN研究的重要目標[3]。

為了延長網絡生命周期[4],許多基于成簇的路由協(xié)議被提出[5]。分簇減少了數據的冗余度,降低了傳輸能耗。早期的成簇路由協(xié)議大多采用單跳通信的方式,其網絡擴展性較差。隨著研究的深入,越來越多的成簇網絡采用多跳通信的方式,這雖然能夠節(jié)省能量,但易導致能量空洞[6]。

LEACH[7]是最早提出的一種均勻分簇路由協(xié)議,相比較于平面路由協(xié)議,其能量利用率較高,生命周期較長;但隨機的簇首選舉和簇間單跳通信易導致某些節(jié)點由于能耗過快而過早死亡。因此,李成法等人[8]提出了一種不均勻的成簇路由協(xié)議-EEUC(Energy-Efficient Uneven Clustering),它通過控制簇首的競爭半徑來調整簇的規(guī)模,使靠近基站的簇規(guī)模較小,這樣距離基站較近的簇首會由于簇內能耗的降低而預留足夠的能量來轉發(fā)其他簇首的數據;然而簇首的選擇只由概率和門限值決定,無法保證所選簇首最優(yōu)。Hui等人[9]提出了混合整數線性規(guī)劃模型,以此來確定簇首的最佳位置。陳海南等人[10]提出利用遺傳算法和概率準則的有效結合來均衡網絡能耗。張雅瓊[11]提出利用K-means算法均勻分簇,避免了極大簇和極小簇的情況;但K-means算法對初始聚類中心敏感,聚類效果不理想。Rodriguez等人[12]提出了一種綜合考慮局部密度和距離的聚類算法-CFSFDP(Clustering by Fast Search and Find of Density Peaks),該算法能夠從網絡中選取最優(yōu)聚類中心;但聚類中心的選擇需要借助人工輔助,很難應用于實踐。因此,在此基礎上,馬春來等人[13]提出了一種聚類中心自動選取策略,通過引入拐點實現CFSFDP算法的自動化。

蔣暢江等人[14]提出了DEBUC(Distributed Energy-Balanced Unequal Clustering)協(xié)議,它利用節(jié)點的競爭半徑選擇候選簇首,根據候選簇首以及其鄰居節(jié)點的剩余能量通過基于時間的競爭算法選舉最終簇首,同時在簇間運用貪婪算法選擇中繼節(jié)點,均衡了能耗;但由于隨著網絡規(guī)模的增大,競爭半徑逐漸增加,簇內通信距離達到自由空間模型的極限值,導致數據傳輸時能耗增加較快。孫彥清等人[15]提出了UCDP(Uneven Clustering routing protocol based on Dynamic Partition)協(xié)議,它利用能量均衡的非均勻分區(qū)算法將網絡合理動態(tài)分區(qū),選舉簇首與區(qū)頭協(xié)作通信,通過簇內單跳、區(qū)內以及區(qū)間多跳相結合的方式建立一個能耗最優(yōu)的路由協(xié)議;但在路徑建立時,簇內以及簇間需要多次通信。

本文綜合以上問題,在改進算法的基礎上提出了一種適用于大規(guī)模無線傳感網的分簇路由算法。該算法在基站利用改進的CFSFDP算法自動估計類數K值和選取聚類中心;通過泊松混合模型將節(jié)點依概率合理分簇;在簇間采用多跳路由方式,將等效能量、距離和角度因素相結合,對多跳路徑進行優(yōu)化。實驗數據表明:該協(xié)議能夠有效延長網絡壽命,均衡節(jié)點能耗,并且在大規(guī)模網絡中具有良好的性能。

1 網絡模型與能耗模型

1.1 網絡模型

本文假設N個傳感器節(jié)點隨機分布在M×M的監(jiān)測區(qū)域內,且傳感器網絡具有如下性質[14]:①基站在監(jiān)測區(qū)域外,傳感器節(jié)點在監(jiān)測區(qū)域內,部署后位置均不變。②所有節(jié)點同構,即具有相似的能力(處理/通信),且都有唯一的節(jié)點標識號。③鏈路對稱,即已知發(fā)射端的發(fā)射功率,接收端可以根據接收到的信號強度估算兩者的距離。④節(jié)點的發(fā)射功率以及通信半徑可以根據需要自動調整。⑤節(jié)點具有位置感知能力。⑥相對于節(jié)點感知范圍而言,監(jiān)測區(qū)域遠大于單個節(jié)點的感知區(qū)域。

1.2 能耗模型

本文采用文獻[7]的能耗模型,即一階無線電模型。發(fā)射端向距離為d的接收端發(fā)送l比特數據的能耗為:

(1)

接收端接收l比特的數據所消耗的能量為:

ERx(l)=lEelec

(2)

簇首將普通節(jié)點的數據進行融合同樣需要消耗能量,本文采用文獻[15]的融合模型,即無論簇首接收到多少普通節(jié)點的數據均將其融合成l比特。

2 大規(guī)模分簇路由算法-CRCPMM

針對LEACH協(xié)議以及大多基于其改進的路由協(xié)議如DEBUC等隨著網絡規(guī)模的擴大其能量利用率較低的問題,本文提出了一種基于CFSFDP和泊松混合模型的大規(guī)模無線傳感網分簇路由算法。該算法通過在基站運行改進的CFSFDP算法來估計K值和選取聚類中心,然后在此基礎上利用泊松混合模型實現K值的優(yōu)化和節(jié)點分簇;同時在簇間綜合考慮等效能量因素、距離因素以及角度因素,建立最優(yōu)多跳傳輸路徑。

2.1 改進的CFSFDP算法

經典聚類算法如K-means、K-medoids等在聚類時首先需要確定最終聚類數K以及初始種子節(jié)點,而兩者的選擇大多采用隨機或人為指定的方式,這使得算法帶有一定的主觀性和隨意性。因此本文提出在利用泊松混合聚類前先采用改進的CFSFDP聚類算法選取初始種子節(jié)點以及估計網絡K值。為了降低能耗,本文采用集中式的方法,由基站控制運行改進的CFSFDP算法。

局部密度ρi主要用來刻畫聚類中心的鄰居節(jié)點個數。鄰居節(jié)點個數越多,ρi越大;反之,ρi越小。根據局部密度的含義,其表達式為:

(3)

式中:dc為截斷距離。由式(3)可知,與節(jié)點xi的距離小于dc的節(jié)點數越多,ρi越大。

d1≤d2≤…≤dNN

(4)

取dc=df(NNt),f(NNt)表示對NNt進行四舍五入運算,t取經驗值0.02[12]。

ρq1≥ρq2≥…ρqN

(5)

根據距離的含義,其表達式為:

(6)

盡管CFSFDP無需復雜的參數設置和迭代運算[13],但是在選取聚類中心時仍需要人工輔助。基于此,本文在局部密度ρi和距離δi的基礎上提出一種適用于CFSFDP的聚類中心自動選取策略,其核心思想在于對決策圖中拐點的刻畫。

聚類中心自動選取策略首先將ρi和δi的歸一化乘積γi作為節(jié)點的決策值,其表達式為式(7)。然后將γi按照降序排列并取前n(n=N/3)[13]個節(jié)點作為聚類中心候選節(jié)點。本文以網絡中共有100個節(jié)點為例,其決策圖如圖1。

(7)

圖1 決策圖

由圖1可知,按照γi減小的方向聚類中心候選節(jié)點的密度逐漸增大,且在某一特殊點密度變化最大,此特殊點即為拐點。候選節(jié)點xi的密度為與xi的γi值小于ε的其他候選節(jié)點數目,其表達式為:

(8)

式中:χij為特殊函數,其計算公式為:

(9)

為了更好地刻畫拐點,本文引入密度變化率,其表達式為式(10)。根據上述拐點的含義,密度變化率最大的候選節(jié)點即為拐點,圖1的拐點判斷圖如圖2所示。設拐點的決策值為γt,則K值為決策值不小于γt的聚類中心候選節(jié)點數目,其所對應的節(jié)點即為初始種子節(jié)點。本文以上述K值和初始種子節(jié)點對泊松混合聚類進行初始化。

DCRi=βi+1-βi

(10)

圖2 拐點判斷圖

2.2 加速泊松混合聚類

在二維地理空間位置部署的大量傳感器節(jié)點通常是獨立隨機分布的,這種分布方式適用于分析沒有先驗知識的地理環(huán)境。傳感器節(jié)點通常采用高空灑落的方式部署在難以監(jiān)測的環(huán)境中,節(jié)點的位置可以看作服從二維泊松分布[16]。設傳感器節(jié)點在單位監(jiān)測區(qū)域A內呈密度為λ的隨機分布,則區(qū)域內的節(jié)點數N(A)服從泊松分布,其概率為:

(11)

式中:‖A‖表示單位監(jiān)測區(qū)域的面積。

2.2.1 建立泊松混合模型

傳統(tǒng)聚類算法如DBSCAN、Birch、AGNES等判斷節(jié)點的所屬類時一般只考慮距離因素,并沒有關注節(jié)點的分布;而在實際環(huán)境中,節(jié)點是否屬于某一類與節(jié)點的分布有較大的關系。針對上述思想,本文提出了一種基于泊松混合模型的加速聚類算法。

假設服從泊松混合分布的隨機節(jié)點為xi,則其概率可表示為:

(12)

式中:πk為每個泊松模型分量的混合系數,代表其所包含的節(jié)點數占總節(jié)點數的比例;K為泊松模型分量的個數;MDik為節(jié)點xi與聚類中心ck的曼哈頓距離,MDmin為MDik的最小值,即MDmin=min{MDik,k=1,2,…,K};P(xi|λk,nk)表示第k個泊松模型的分布律,λk為其均值,nk為該模型分量所包含的節(jié)點數,其表達式為:

(13)

設Z={zik}為隱變量集,zik表示節(jié)點xi屬于第k類的概率,泊松模型的參數為θk=(λk,nk),則節(jié)點集的最大對數似然函數為:

(14)

2.2.2 改進的EM算法

本文采用EM算法迭代求解式(14)的最大似然參數。EM算法(Expectation Maximization Algorithm)是一種迭代優(yōu)化求解概率模型參數的最大似然估計方法,其具體步驟分為兩步:E-Step和M-Step。

對式(14),由Jensen不等式可得:

(15)

(16)

(17)

由EM算法求出最大似然參數估計值。其中,混合系數:

(18)

泊松模型分量的均值:

(19)

隱變量:

(20)

(21)

(22)

(23)

為了在泊松混合聚類的迭代初期使參數θk快速逼近最優(yōu)解,本文采用Steffensen加速方法。當θk接近最優(yōu)解時,由于EM算法步長變化緩慢,本文使用Broyden對稱秩1校正公式進行校正,使算法快速收斂。因此在整個迭代周期算法的迭代次數明顯減少,達到了加速收斂的目的。

(24)

式中:α為調節(jié)系數,滿足0≤α≤1,其取值為:

(25)

為了使算法快速逼近最優(yōu)解,迭代開始時令α=1,同時初始化混合系數πk=1/K。隨著迭代的進行,相比較于式(14),式(24)的似然函數L(zik,πk|x)增加速度較快,且前后兩次迭代的混合系數差異越來越小,直到α=0,迭代停止。

(26)

(27)

(28)

2.2.3 求解最優(yōu)K值

2.2.4 加速泊松混合聚類的基本步驟

Step 10 利用隱含參數信息熵原理,求出三維數組Ω中不同K值的信息熵H,則H的最小值所對應的K值即為泊松模型成份數的最優(yōu)解。

Step 11 根據最優(yōu)成份數K值所對應的zik以及能耗均衡性確定節(jié)點的簇標記,即對于節(jié)點xi,從zik中選擇兩個較大值,并計算其能負比,從中選擇值最大的作為節(jié)點的簇。能負比為聚類中心的剩余能量與該類中節(jié)點數的比值,其表達式為式(29),Ej表示剩余能量,nj表示節(jié)點個數。

ECRj=Ej/nj

(29)

由以上步驟可以看出,加速泊松混合聚類在每次迭代過程中有一次分量的消除過程(Step 5)以及兩次加速收斂的步驟(Step 2和Step 8),這將大大地減少算法的迭代次數。同時算法擁有最佳K值以及節(jié)點簇標記的判定過程(Step 10和Step 11),這將使最終得到的模型成份數最優(yōu),節(jié)點聚類更合理。聚類完成后,算法進入簇內選擇簇首階段。

2.3 簇首選擇

本文算法在簇內采用文獻[17]的三級簇首選擇機制選舉簇首,同時考慮剩余能量、簇內總能耗以及簇內節(jié)點的能耗均衡3個因素。

由文獻[15]可知,節(jié)點可以獲取自身的當前剩余能量Er;由1.1可知,節(jié)點具有位置感知能力,即任意兩個節(jié)點之間的距離是已知的,則簇內某一節(jié)點當選為簇首時的簇內總能耗TECi為:

(30)

式中:l,Eelec,εfs,dk-i的意義與式(1)相同。

由式(1)可知,簇內節(jié)點向簇首發(fā)送數據時所消耗的能量與距離的平方成正比,簇內節(jié)點到簇首的距離的差異越小,簇內節(jié)點的能耗越均衡。因此,當簇內某一節(jié)點當選為簇首時,簇內節(jié)點的能耗均衡性EBi為:

(31)

首輪時,簇內所有節(jié)點參與競選,選舉的簇首不但具有較高的剩余能量,而且能夠保證簇內總能耗較低和簇內節(jié)點能耗均衡。后續(xù)輪次時,本文算法采用由上一輪簇首指定下一輪簇首的方式。若上一輪簇首的剩余能量最高,則簇首不變;否則,上一輪簇首根據節(jié)點剩余能量以及與自身的距離選擇下一輪簇首。下一輪簇首與上一輪簇首的距離越近,簇內總能耗越低,簇內節(jié)點能耗越均衡。簇首確定后,算法進入穩(wěn)定的數據傳輸階段。

2.4 數據傳輸

數據傳輸階段分為簇內通信和簇間通信。在簇內,若節(jié)點到基站的距離小于到簇首的距離,則節(jié)點直接將數據傳輸至基站,否則,節(jié)點將數據傳輸至簇首。在簇間,采用數據包在相鄰簇首間中繼轉發(fā)的方式,相鄰簇首包括已當選為簇首的節(jié)點和直接與基站通信的節(jié)點。

簇間中繼時,下一跳簇首的選擇除了與等效剩余能量和距離有關外,實際上還與方向有關[18]。因此,本文提出了一種綜合考慮等效能量、距離和角度的多跳路由策略。

根據貪婪邊界無狀態(tài)路由GPSR[18]的思想,下一跳簇首應具有較大的前進距離。設N為當前簇首,M為下一跳簇首,T為基站。為了更好地衡量前進距離,本文提出相對距離的概念。相對距離即下一跳簇首到基站的距離與當前最優(yōu)路徑的比值,當前最優(yōu)路徑為當前簇首與基站的連線,其表達式為:

(32)

根據CR[18]的思想,路由策略應選擇與當前最優(yōu)路徑夾角φ較小的簇首作為下一跳,這樣選擇的下一跳路徑能最快收斂于當前最優(yōu)路徑,且整個轉發(fā)路徑最先收斂于理想最優(yōu)路徑,理想最優(yōu)路徑為源簇首到基站的連線。在WSN中,該夾角φ可以通過定位技術計算得出[19]。考慮余弦函數的特性,當夾角越小時,其值越大,否則,其值越小。因此,本文以cosφ來衡量下一跳路徑與當前最優(yōu)路徑的夾角。

為了均衡簇首的能耗,路由策略應選擇等效剩余能量較大的簇首作為下一跳。等效剩余能量為簇首剩余能量與簇內節(jié)點個數的關系,本文以sin(πEi)來衡量簇首的剩余能量,以式(33)來衡量簇內節(jié)點個數,mi為第i個簇內的節(jié)點數,mmax為最大的簇所包含的節(jié)點數。等效剩余能量的計算公式為式(34),由公式可知,簇首剩余能量越大,所包含的節(jié)點數越少,其等效剩余能量越大。

(33)

(34)

綜上,新的簇間路由策略應選擇等效剩余能量較大、相對距離較近且角度較小的簇首作為下一跳。本文以值Wi作為其度量標準,其計算式為:

(35)

2.5 算法時間復雜度分析

CRCPMM算法的時間復雜度由四部分組成,即CFSFDP的時間復雜度、加速泊松混合聚類的時間復雜度以及簇首選擇和數據傳輸的時間復雜度。

假設網絡中共有N個節(jié)點,候選聚類中心個數為n,簇首數目為K,則CRCPMM算法的時間復雜度為O(N2)。

證明CRCPMM算法利用改進的CFSFDP自動估計聚類中心個數。首先,基站計算參數dij,ρi,δi,時間復雜度均為O(N2);其次,計算ρi和δi的歸一化乘積γi,并將γi按照降序排列,時間復雜度分別為O(N)和O(nlogn);然后,計算βi和密度變化率DCRi,時間復雜度分別為O(n2)和O(n)。因此,CFSFDP的時間復雜度為:

O(N2+N2+N2+N+nlogn+n2+n)=O(N2)

(36)

在加速泊松混合聚類中,首先建立泊松混合模型,時間復雜度為O(N);其次,利用EM算法迭代求解概率模型參數,設迭代次數為t,則其時間復雜度為O(NKt);然后將節(jié)點聚類,時間復雜度為O(N)。因此,加速泊松混合聚類的時間復雜度為O(N+N+NKt)。

在簇首選擇過程中,節(jié)點需要計算其作為簇首時的TECi和EBi,時間復雜度均為O(N)。在數據傳輸過程中,簇首需要計算下一跳簇首的EREi,cosφ,Rd,時間復雜度均為O(K2)。因此,簇首選擇和數據傳輸過程的時間復雜度為O(N+N+K2+K2+K2),即O(N+K2)。

根據以上分析,由于N≥K且N≥t,因此整個算法的時間復雜度為O(N2)。

3 實驗分析

為了驗證CRCPMM算法的性能,本文分別在不同的網絡規(guī)模下仿真LEACH[7]、DEBUC[14]和CRCPMM 3種協(xié)議的網絡壽命、網絡總能耗以及節(jié)點平均剩余能量,橫坐標為仿真時間,以輪數表示。其中,4種網絡規(guī)模分別為100 m×100 m、200 m×200 m、400 m×400 m以及800 m×800 m,網絡中的節(jié)點總數分別為100、400、1600和6400。具體仿真參數如表1所示。

表1 仿真參數表

3.1 網絡壽命

本文定義網絡壽命為從WSN的第一輪開始到10%節(jié)點失效的輪數。圖3～圖6分別為4種不同網絡規(guī)模下3種協(xié)議的網絡壽命對比圖,縱坐標為網絡中存活的節(jié)點個數。

圖3 規(guī)模為100 m×100 m的網絡壽命對比

圖4 規(guī)模為200 m×200 m的網絡壽命對比

圖5 規(guī)模為400 m×400 m的網絡壽命對比

圖6 規(guī)模為800 m×800 m的網絡壽命對比

由以上4個圖可知,隨著網絡規(guī)模的增大,3種協(xié)議的網絡壽命在不斷減小。在小規(guī)模網絡中(如圖3和圖4),3種協(xié)議的網絡壽命分別為435輪、516輪、559輪和389輪、488輪、546輪,相對于LEACH和DEBUC協(xié)議,CRCPMM協(xié)議在網絡壽命上分別延長28.5%、8.33%和40.35%、11.88%;在中規(guī)模網絡中(如圖5),3種協(xié)議的網絡壽命分別為135輪、416輪和526輪,CRCPMM協(xié)議在網絡壽命上分別延長289.6%和26.44%;而在大規(guī)模網絡中(如圖6),3種協(xié)議的網絡壽命分別為48輪、241輪和383輪,CRCPMM協(xié)議在網絡壽命上分別延長697.9%和58.92%。

以上數據表明:相比較于小規(guī)模和中規(guī)模網絡,CRCPMM協(xié)議在大規(guī)模網絡中能夠明顯延長網絡壽命。這是因為隨著網絡規(guī)模的增大,LEACH協(xié)議的單跳通信以及DEBUC協(xié)議競爭半徑的增加導致了能量的快速消耗,而本文利用改進的CFSFDP算法和泊松混合模型優(yōu)化了K值,實現了節(jié)點的最優(yōu)聚類,降低了能量的消耗速度,因此CRCPMM協(xié)議更加適用于大規(guī)模網絡。

3.2 網絡總能耗

圖7～圖10為4種不同網絡規(guī)模下3種協(xié)議的網絡總能耗對比圖,縱坐標為網絡的總能量消耗。

圖9 規(guī)模為400 m×400 m的網絡總能耗

圖7 規(guī)模為100 m×100 m的網絡總能耗

圖8 規(guī)模為200 m×200 m的網絡總能耗

圖10 規(guī)模為800 m×800 m的網絡總能耗

由圖7～圖10可知,在小規(guī)模(如圖7和圖8)和中規(guī)模網絡中(如圖9),3種協(xié)議的總能耗差異相對較小;而在大規(guī)模網絡中(如圖10),CRCPMM協(xié)議的總能耗明顯低于其余兩種協(xié)議,說明在大規(guī)模網絡中CRCPMM協(xié)議能夠有效降低能耗。

隨著網絡規(guī)模的增大,LEACH協(xié)議由于簇間采用單跳通信,其節(jié)點能耗增加較快;DEBUC協(xié)議由于競爭半徑增大,簇內采用多徑衰落模型,其能耗增加也較快;而本文算法通過將改進的CFSFDP和泊松混合聚類相結合,優(yōu)化了簇的數目K值,選舉了最優(yōu)聚類中心,實現了節(jié)點的合理分簇,減緩了能耗的增加速率。因此,CRCPMM協(xié)議更加適應于大規(guī)模網絡。

圖12 規(guī)模為200 m×200 m的節(jié)點平均剩余能量

3.3 節(jié)點平均剩余能量

圖11～圖14為4種不同網絡規(guī)模下3種協(xié)議的節(jié)點平均剩余能量對比圖,縱坐標為節(jié)點的平均剩余能量。

圖11 規(guī)模為100 m×100 m的節(jié)點平均剩余能量

圖13 規(guī)模為400 m×400 m的節(jié)點平均剩余能量

圖14 規(guī)模為800 m×800 m的節(jié)點平均剩余能量

節(jié)點的平均剩余能量越高,節(jié)點的能耗越均衡。從圖中可以得出,在小規(guī)模(如圖11和圖12)和中規(guī)模網絡中(如圖13),3種不同協(xié)議的節(jié)點平均剩余能量雖然不同,但差異相對較小;而在大規(guī)模網絡中(如圖14),本文算法的節(jié)點平均剩余能量在相同的輪數(如200輪)都明顯高于其余兩種協(xié)議,這說明在大規(guī)模網絡中CRCPMM協(xié)議能夠更好地均衡節(jié)點能耗。

隨著監(jiān)測區(qū)域規(guī)模的增加,LEACH協(xié)議中與基站較遠的簇首和與基站較近的簇首的能耗差距逐漸增大;DEBUC協(xié)議在簇間通信時由于重點考慮距離因素會使得簇首在選擇下一跳節(jié)點時過多偏離理想最優(yōu)路徑,從而增加多跳跳數和能量消耗;而本文算法不僅在節(jié)點聚類時考慮了能負比,且在多跳通信時綜合考慮了等效剩余能量因素、距離因素和角度因素,在保證多跳路徑偏離最優(yōu)路徑較小的情況下,選擇能耗均衡的下一跳簇首。因此,與其余兩種協(xié)議相比,CRCPMM協(xié)議更加適應于大規(guī)模網絡。

4 結束語

針對諸多路由協(xié)議如LEACH、DEBUC等在大規(guī)模無線傳感網中的局限性,本文提出了一種適用于大規(guī)模網絡的基于CFSFDP和泊松混合模型的分簇路由算法。該算法利用改進的CFSFDP和泊松混合模型實現節(jié)點的合理分簇;在簇間兼顧等效能量、距離和角度建立能耗均衡的多跳路徑。實驗仿真表明:與LEACH、DEBUC協(xié)議相比,本文算法在大規(guī)模網絡中具有較明顯的優(yōu)勢,能夠有效延長網絡生命周期,均衡節(jié)點的能耗。

雖然本文算法在大規(guī)模網絡中表現了良好的性能,但實際環(huán)境中移動節(jié)點以及異構網絡的應用越來越廣泛,為了更好地適應傳感器網絡的發(fā)展,下一步的主要工作是在異構網絡中對算法做出改進,使其更加適用于實際場合。

[1] Zhang D,Li G,Zheng K,et al. An Energy-Balanced Routing Method Based on Forward-Aware Factor for Wireless Sensor Network[J]. IEEE Transactions on Industrial Informatics,2013,10(1):766-773.

[2] Gherbi C,Aliouat Z,Benmohammed M. An Adaptive Clustering Approach to Dynamic Load Balancing and Energy Efficiency in Wireless Sensor Networks[J]. Energy,2016(114):647-662.

[3] Arora V K,Sharma V,Sachdeva M. A Survey on LEACH and Other’s Routing Protocols in Wireless Sensor Network[J]. Optik-International Journal for Light and Electron Optics,2016,127(16):6590-6600.

[4] 吳勇,張靈. 基于多目標優(yōu)化的WSN簇首選擇算法[J]. 傳感技術學報,2016,29(7):1062-1067.

[5] Barati H,Movaghar A,Rahmani A M. EACHP:Energy Aware Clustering Hierarchy Protocol for Large Scale Wireless Sensor Networks[J]. Wireless Personal Communications,2015,85(3):765-789.

[6] Mohemed R E,Saleh A I,Abdelrazzak M,et al. Energy-Efficient Routing Protocols for Solving Energy Hole Problem in Wireless Sensor Networks[J]. Computer Networks,2017,114(2):51-66.

[7] Heinzelman W,Chandrakasan A,Balakrishnan H. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communication,2002,1(4):660-670.

[8] 李成法,陳貴海,葉懋,等. 一種基于非均勻分簇的無線傳感器網絡路由協(xié)議[J]. 計算機學報,2007,30(1):27-36.

[9] Lin H,Uster H. Exact and Heuristic Algorithms for Data-Gathering Cluster-Based Wireless Sensor Network Design Problem[J]. IEEE Transactions on Networking,2014,22(3):903-916.

[10] 陳海南,劉廣聰,吳曉鴿,等. 一種基于遺傳算法與概率轉發(fā)的分簇協(xié)議[J]. 計算機科學,2015,42(3):71-73.

[11] 張雅瓊. 基于K-means的無線傳感網均勻分簇路由算法研究[J]. 控制工程,2015,22(6):1181-1185.

[12] Rodriguez A,Laio A. Clustering by Fast Search and Find of Density Peaks[J]. Science,2014,344(6191):1492-1496.

[13] 馬春來,單洪,馬濤,等. 一種基于CFSFDP改進算法的重要地點識別方法研究[J]. 計算機應用研究,2017,34(1):136-140.

[14] 蔣暢江,石為人,唐賢倫,等. 能量均衡的無線傳感器網絡非均勻分簇路由協(xié)議[J]. 軟件學報,2012,23(5):1222-1232.

[15] 孫彥清,彭艦,劉唐,等. 基于動態(tài)分區(qū)的無線傳感器網絡非均勻成簇路由協(xié)議[J]. 通信學報,2014,35(1):198-206.

[16] Liu B Y,Towsley D. A Study of the Coverage of Large-Scale Sensor Networks[C]//Proceedings of 2004 IEEE International Conference on Mobile Ad-Hoc and Sensor Systems. Piscataway:IEEE Press,2004:475-483.

[17] 翟春杰,徐建閩,劉永桂. 基于分區(qū)的能耗均衡路由協(xié)議[J]. 傳感技術學報,2016,29(1):80-87.

[18] 謝志恒,張向利,何龍,等. 基于距離和角度的無線傳感器網絡路由方案[J]. 計算機工程與應用,2010,46(31):109-110.

[19] 李建洲,王海濤,陶安. 一種能耗均衡的WSN分簇路由協(xié)議[J]. 傳感技術學報,2013,26(3):396-401.

陶志勇(1978-),男,博士,副教授,碩士生導師,主要研究方向是多媒體通信,82456020@qq.com;

王和章(1992-),男,碩士研究生,主要研究方向是無線傳感網路由協(xié)議;

劉影(1983-),女,博士,講師,主要研究方向是無線網絡定位和物聯(lián)網。

ClusteringRoutingAlgorithmBasedonCFSFDPandPoissonMixtureModelinLarge-ScaleWirelessSensorNetworks*

TAOZhiyong*,WANGHezhang,LIUYing

(School of Electrics and Information Engineering,Liaoning Technical University,Huludao Liaoning 125105,China)

With the expansion of the scale in wireless sensor networks,the node energy utilization becomes lower. A clustering routing algorithm is proposed,which was based on CFSFDP and poisson mixture model(CRCPMM)for the large-scale wireless sensor networks. Its core idea is that it uses modified CFSFDP algorithm to estimate theKvalue of the number of clusters and select clustering center automatically at base station. Then it utilizes poisson mixture model to cluster the nodes reasonably to ensure the optimal clustering. In the inter-cluster,the CRCPMM algorithm adopts multi-hop transmission mode,which considers cluster-heads equivalent residual energy,the distances among cluster-heads and the angles between multi-hop paths and ideal optimal path. Simulation results show that compared with the LEACH(Low Energy Adaptive Clustering Hierarchy)protocol and the DEBUC(Distributed Energy Balanced Unequal Clustering routing)protocol,the CRCPMM protocol has obvious advantages in the large-scale networks,which can balance energy consumption of nodes and extend the network lifetime effectively.

wireless sensor networks;energy consumption balancing;CFSFDP;poisson mixture model;angle

TP393

A

1004-1699(2017)11-1719-10

項目來源:國家自然科學基金項目(61240014);遼寧省自然基金項目(2015020100);遼寧省博士啟動基金(20170520098)

2017-04-17修改日期2017-07-05

10.3969/j.issn.1004-1699.2017.11.018