趙東方 施偉斌

摘 要：為了均衡傳統(tǒng)分簇路由算法中的簇間傳輸能耗，減少簇首更換開銷，提出基于最優(yōu)化模型的能耗均衡分簇路由協(xié)議opt_leach。將區(qū)域節(jié)點(diǎn)劃分成大小相同的簇，均衡不同簇的簇內(nèi)通信開銷;簇間通信采用多種路由組合的方式通信，均衡簇間通信開銷;簇內(nèi)節(jié)點(diǎn)可以連續(xù)充當(dāng)簇首，減少簇首更換開銷。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)分簇路由算法相比，該算法可更好地實(shí)現(xiàn)能耗均衡，延長網(wǎng)絡(luò)生存時間。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);分簇路由協(xié)議;能耗均衡;最優(yōu)化;線性規(guī)劃

DOI：10. 11907/rjdk. 191936 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2020）005-0204-05

0 引言

無線傳感器網(wǎng)絡(luò)（WSN）廣泛應(yīng)用于醫(yī)療保健、污染監(jiān)測和目標(biāo)跟蹤系統(tǒng)等領(lǐng)域[1]。WSN由大量節(jié)點(diǎn)組成，其計算、傳感和無線通信能力有限，能效是一個重要問題，直接影響到WSN的網(wǎng)絡(luò)壽命[2]。與非聚類協(xié)議相比，聚類通?？梢詼p少沖突和空閑偵聽造成的能量耗散。因?yàn)樵诿總€集群中，簇首都會為每個節(jié)點(diǎn)分配一個獨(dú)占的時間槽，從而避免沖突。此外，節(jié)點(diǎn)不需要在每個時分多址（TDMA）幀中保持清醒，只需要在其特定的時隙中保持清醒[3]。因此，集群是延長WSN網(wǎng)絡(luò)生存期的常用策略。

為解決WSN中能量均衡高效問題，Heinzelman等[4]提出了最早的分簇路由協(xié)議。該協(xié)議充分利用數(shù)據(jù)融合技術(shù)，是分簇路由協(xié)議的代表;HEED[5]協(xié)議采用迭代的方式選取簇首，并考慮了節(jié)點(diǎn)的剩余能量、通信代價和網(wǎng)絡(luò)中簇首的分布，避免能量少的節(jié)點(diǎn)過早死亡，延長了網(wǎng)絡(luò)生存時間;李成法等[6]提出EEUC協(xié)議，將網(wǎng)絡(luò)組織成大小非均勻的簇，以解決多跳路由傳感器網(wǎng)絡(luò)中常見的“熱區(qū)”問題，但未說明多跳路由路徑的建立過程;黃利曉等[7]提出通過加入間距因子、剩余能量因子和節(jié)點(diǎn)密度因子改進(jìn)簇首選擇概率函數(shù)的閾值計算式，綜合考慮節(jié)點(diǎn)剩余能量和地理位置選擇簇首，取得了一些改進(jìn)效果;胡源等[8]通過對監(jiān)測區(qū)域的等間距環(huán)形劃分和等夾角扇形劃分，選擇同一扇形區(qū)域內(nèi)的下一跳節(jié)點(diǎn)以保證源節(jié)點(diǎn)與基站的通信距離最短;UCF[9]協(xié)議提出一種基于模糊邏輯的不等聚類方法，改進(jìn)了非均勻成簇的半徑確定，進(jìn)一步均衡了簇間通信;Peyman Neamatollahi等[10]提出了一種基于動態(tài)超循環(huán)策略（DHRP）的能量感知集群算法SEDC，通過減少頻繁重新聚類的開銷延長集群WSN中的網(wǎng)絡(luò)生存期，但是沒有對簇首持續(xù)輪數(shù)進(jìn)行理論推導(dǎo)。

傳統(tǒng)的分簇方法采用概率競爭的方式選擇簇首，每一輪簇首分布情況未知，因此難以對簇間通信建立能耗均衡路由規(guī)劃，導(dǎo)致不同區(qū)域的簇首傳輸能耗不均衡;同時，每個節(jié)點(diǎn)當(dāng)選簇首的持續(xù)時間較短，增加了更換簇首的開銷。為此，本文提出一種基于最優(yōu)化模型的能耗均衡分簇路由協(xié)議opt_leach。首先將區(qū)域節(jié)點(diǎn)均勻劃分成大小相同的簇，保證網(wǎng)絡(luò)各個簇的簇內(nèi)通信消耗均衡;其次簇間通信采用多種路由組合方式，使用線性規(guī)劃求解每種路由方式的最優(yōu)比例。在每一個簇內(nèi)，使用線性規(guī)劃求解每個節(jié)點(diǎn)充當(dāng)簇首的最優(yōu)輪數(shù)，使得節(jié)點(diǎn)可以連續(xù)充當(dāng)簇首，從而減少了重新聚類的頻率和開銷。仿真實(shí)驗(yàn)表明，與傳統(tǒng)分簇路由算法相比，本文提出的opt_leach算法可以更好地實(shí)現(xiàn)能耗均衡并延長網(wǎng)絡(luò)生存時間。

1 分簇路由模型介紹

為便于比較，本文采用分簇路由協(xié)議研究中的典型分析模型[4，7，10-12]，對網(wǎng)絡(luò)模型和硬件能耗模型作出假設(shè)與約束。

1.1 傳感器節(jié)點(diǎn)模型

（1）傳感器節(jié)點(diǎn)隨機(jī)、相對均勻分布在規(guī)則圖形的監(jiān)測區(qū)域中。

（2）所有的傳感器節(jié)點(diǎn)具有相同的數(shù)據(jù)處理能力和通信能力，初始能量相同。

（3）傳感器節(jié)點(diǎn)被隨機(jī)分散后位置固定，網(wǎng)絡(luò)部署后不再進(jìn)行人為干涉。

（4）傳感器節(jié)點(diǎn)可以知悉自身剩余能量，位置可被知悉。

（5）節(jié)點(diǎn)部署具有冗余度，一定區(qū)域范圍內(nèi)節(jié)點(diǎn)間的數(shù)據(jù)可以進(jìn)行數(shù)據(jù)融合。

（6）節(jié)點(diǎn)可以根據(jù)數(shù)據(jù)需要發(fā)送的距離調(diào)整發(fā)射功率。

1.2 硬件能耗模型

（1）發(fā)送l bit數(shù)據(jù)能耗。當(dāng)l bit的數(shù)據(jù)需要傳輸時，節(jié)點(diǎn)所消耗的能量主要由兩部分組成：發(fā)送l bit數(shù)據(jù)的基本能量耗損以及功率放大電路的能量耗損;同時，針對不同的發(fā)射距離d選擇不同的發(fā)送功率。

當(dāng)傳輸距離為d時，功率放大器所消耗的能量需要依據(jù)發(fā)送器與接收器的距離d與閾值d0進(jìn)行比較。其中，[d0=εfsεamp]是區(qū)分兩種消耗的閾值。當(dāng)傳輸間距dd0時使用第二種模式。

（2）接收l bit數(shù)據(jù)能耗：Erv（l，d）=l×Eelec。

（3）數(shù)據(jù)融合l bit數(shù)據(jù)能耗：Eag（l，d）=l×Eelec。

2 協(xié)議及算法介紹

Opt_leach協(xié)議是一種集中式和分布式相結(jié)合的并行成簇算法。

初始階段：sink收集節(jié)點(diǎn)的位置信息和能量信息：①將節(jié)點(diǎn)均勻分簇，每個節(jié)點(diǎn)分配一個固定的簇編號，此后節(jié)點(diǎn)所屬的簇編號不再改變;②計算不同編號的簇間通信路由組合最佳比例，寫入路由表;③計算每個簇內(nèi)節(jié)點(diǎn)充當(dāng)簇首的順序和最優(yōu)持續(xù)輪數(shù)，寫入簇首順序表;④sink節(jié)點(diǎn)將以上結(jié)果分發(fā)至每個節(jié)點(diǎn)。初始階段只執(zhí)行一次。

分布式階段：①每個初始簇首為簇首順序表的第一個節(jié)點(diǎn)，相同簇編號的節(jié)點(diǎn)加入同一個簇，簇首為每個成員分配TDMA時隙;②簇首更換：簇首輪數(shù)若達(dá)到最優(yōu)輪數(shù)，則指定簇首順序表的下一個節(jié)點(diǎn)在下一輪成為簇首，并使用該節(jié)點(diǎn)的TDMA時隙，簇內(nèi)其它節(jié)點(diǎn)TDMA時隙不變;③簇間通信：簇首節(jié)點(diǎn)按照事先分配的路由表中的路由路徑傳輸數(shù)據(jù)至sink節(jié)點(diǎn)。

2.1 均勻分簇

因?yàn)楣?jié)點(diǎn)位置固定，所以可對節(jié)點(diǎn)進(jìn)行區(qū)域劃分[6，9，13-16]。本文對節(jié)點(diǎn)區(qū)域均勻劃分，首先將節(jié)點(diǎn)按照相對于匯聚節(jié)點(diǎn)在垂直方向上劃分成Y個區(qū)域，再將水平方向劃分成X個區(qū)域，這樣一共得到X×Y個區(qū)域。每個區(qū)域的節(jié)點(diǎn)獲得相同的簇編號，即每個區(qū)域的節(jié)點(diǎn)將始終在同一個簇內(nèi)。圖1展示了100m×100m區(qū)域內(nèi)在隨機(jī)均勻分布100節(jié)點(diǎn)情況下，節(jié)點(diǎn)被均勻分成4個簇的情形。

2.2 簇間通信方式確定

在LEACH協(xié)議中，每個簇首采用單跳直接與匯聚節(jié)點(diǎn)通信。當(dāng)節(jié)點(diǎn)分布區(qū)域逐漸增大時，靠近匯聚節(jié)點(diǎn)的簇和遠(yuǎn)離匯聚節(jié)點(diǎn)的簇能耗差異明顯，距sink節(jié)點(diǎn)較遠(yuǎn)的簇節(jié)點(diǎn)能量會先耗盡。若簇首采用多跳方式往往會導(dǎo)致靠近sink節(jié)點(diǎn)的簇節(jié)點(diǎn)能量先耗盡[17-18]。因此，本文簇首間通信采用多種路由組合的方式傳輸數(shù)據(jù)，并計算最優(yōu)比例。

假設(shè)一共有n個簇首節(jié)點(diǎn)，每個節(jié)點(diǎn)用于簇首傳輸?shù)哪芰繛镋i，則簇首節(jié)點(diǎn)共有m（m=2n（n-1）/2）種可能路徑。圖2為當(dāng)n=3時的路由情況，c節(jié)點(diǎn)有4種路徑選擇（c→b→a→sink，c→b→sink，c→a→sink，c→sink），b節(jié)點(diǎn)有兩種路徑選擇（b→a→sink，b→sink），a節(jié)點(diǎn)有一種路徑選擇（a→sink），則根據(jù)乘法規(guī)則，n=3時一共有4*2*1=8種路由方式。

在每一輪中，簇首會從所有路由路徑中選擇一種作為簇首通信方式。若第i（1≤i≤n）個簇首在第k（1≤k≤m）種路由方式中傳輸一輪數(shù)據(jù)的能耗為CHcostik，則第k種路由方式的使用次數(shù)為lk輪。在每個簇首i用于傳輸數(shù)據(jù)的能量不超過Ei前提下，通過確定不同路由最優(yōu)比例獲得簇首可傳輸數(shù)據(jù)的最大輪數(shù)lmax，可使用最優(yōu)化模型中的線性規(guī)劃求解。

當(dāng)n逐漸增大時，求解出的路由組合可能有很多種。實(shí)際應(yīng)用中可以忽略占比低于閾值Routeth的路由路徑，保留占比較大且切換較容易的幾種路由，再作一次線性規(guī)劃得到最優(yōu)比例，具體閾值和路由數(shù)量可根據(jù)實(shí)際情況作相應(yīng)調(diào)整。

2.3 簇內(nèi)節(jié)點(diǎn)成為簇首的輪數(shù)和順序

在均衡每個簇的簇首能耗后，區(qū)域中每個簇可以看成近似等價。在每個固定的簇中，不同位置節(jié)點(diǎn)當(dāng)選簇首時節(jié)點(diǎn)能耗分布不同。為了均衡簇內(nèi)每個節(jié)點(diǎn)的消耗，分析每個節(jié)點(diǎn)當(dāng)選簇首的最優(yōu)輪數(shù)。

2.3.1 節(jié)點(diǎn)成為簇首的輪數(shù)確定

假設(shè)某個簇內(nèi)一共有n個節(jié)點(diǎn)，每個節(jié)點(diǎn)的初始能量為E。由于單個簇內(nèi)同時只有一個簇首，所以一共有n種成簇情況，即每個節(jié)點(diǎn)輪流當(dāng)一次簇首。第j個節(jié)點(diǎn)在第i個節(jié)點(diǎn)當(dāng)選簇首時的能耗 costij可由式（4）計算，其中i=j時，為節(jié)點(diǎn)當(dāng)選簇首時使用多種路由組合的加權(quán)平均消耗。

2.3.2 簇首順序確定

當(dāng)簇內(nèi)節(jié)點(diǎn)i成為簇首的最優(yōu)輪數(shù)已知后，節(jié)點(diǎn)i在第k種路由方式下充當(dāng)簇首的次數(shù)在沒有達(dá)到Rik之前的任何一輪都可以成為簇首。當(dāng)節(jié)點(diǎn)i在第k種路由方式下成為簇首的次數(shù)達(dá)到Rik時，在第k種路由方式下不再成為簇首，所以簇首的順序確定可依據(jù)實(shí)際應(yīng)用靈活變化。

本文將簇內(nèi)節(jié)點(diǎn)i到sink的距離di作為簇首節(jié)點(diǎn)的順序指標(biāo)。在第k種路由方式下，di小的節(jié)點(diǎn)先成為簇首，并且連續(xù)充當(dāng)簇首Rik輪，即節(jié)點(diǎn)連續(xù)充當(dāng)簇首的輪數(shù)為當(dāng)前路由方式的最優(yōu)輪數(shù)。這樣做的好處是簇首不必頻繁切換，有利于路由的穩(wěn)定并降低控制信息的能耗。當(dāng)整個簇內(nèi)節(jié)點(diǎn)執(zhí)行完當(dāng)前路由方式的輪數(shù)后，整體切換成路由表中的下一種路由方式。

3 仿真分析

本文在Matlab平臺上對LEACH、HEED、SEDC和本文的opt_leach協(xié)議分別進(jìn)行仿真。假設(shè)100個節(jié)點(diǎn)隨機(jī)均勻分布在從（0，0）到（100m，100m）的網(wǎng)絡(luò)區(qū)域內(nèi)[4，7，11-12]，匯聚節(jié)點(diǎn)部署在網(wǎng)絡(luò)區(qū)域之外的坐標(biāo)（50m，175m）。為了保證區(qū)域的連通性[5]，本文假設(shè)每間隔10m×10m方形區(qū)域內(nèi)至少有一個節(jié)點(diǎn)，因?yàn)檫B通性是保障節(jié)點(diǎn)可以通過多跳的方式傳輸數(shù)據(jù)的重要條件，在實(shí)際應(yīng)用中這個假設(shè)也是合理且易于實(shí)現(xiàn)的。表1列出了實(shí)驗(yàn)參數(shù)。

3.1 opt_leach參數(shù)計算

區(qū)域劃分的參數(shù)為x=2，y=2，即簇首的最大跳數(shù)為2，節(jié)點(diǎn)共有兩種路由選擇。通過計算得到兩種路由方式的最佳比例為單跳Route1=0.401 9，多跳Route2=0.598 1。4個簇計算出的多跳輪數(shù)分別為577、580、580、576，單跳輪數(shù)分別為385、387、385、386。將不同區(qū)域的輪數(shù)統(tǒng)一為計算出的最小值，得到最終每個區(qū)域的節(jié)點(diǎn)將以576輪簇首多跳路由和385輪簇首單跳通信，共持續(xù)961輪。單個簇內(nèi)每個節(jié)點(diǎn)的輪數(shù)如圖3所示。

在到達(dá)最大可持續(xù)輪數(shù)后，節(jié)點(diǎn)會相繼死亡，opt_leach協(xié)議著重于節(jié)點(diǎn)全部存活時傳輸數(shù)據(jù)的能耗均衡最優(yōu)化，所以未對節(jié)點(diǎn)相繼失效時的分簇進(jìn)行討論。為了便于與其它協(xié)議進(jìn)行對比，在節(jié)點(diǎn)到達(dá)最大可持續(xù)輪數(shù)后，采用SEDC[10]協(xié)議對剩余節(jié)點(diǎn)進(jìn)行分簇。

3.2 協(xié)議對比與分析

通過比較執(zhí)行完opt_leach的最大輪數(shù)后，將每個協(xié)議的節(jié)點(diǎn)存活數(shù)量和每一輪能耗速率作為評估opt_leach協(xié)議性能指標(biāo)，并對opt_leach協(xié)議的能耗均衡性和可預(yù)測性展開分析。

3.2.1 節(jié)能性對比

由圖4可知，當(dāng)輪數(shù)達(dá)到961時，opt_leach協(xié)議的節(jié)點(diǎn)全部存活，符合最大可持續(xù)輪數(shù)的計算結(jié)果。opt_leach的第一個節(jié)點(diǎn)死亡（FND）出現(xiàn)在第962輪，而SEDC、HEED和LEACH的FND分別出現(xiàn)在915、709和624輪;SEDC、HEED和LEACH的最后一個節(jié)點(diǎn)死亡（LND）分別在1016、935、941和1126輪。從圖5可知，opt_leach協(xié)議能量衰減曲線一直保持較小的斜率，這是因?yàn)樵趏pt_leach協(xié)議算法中，節(jié)點(diǎn)在選擇簇間路由方式比例和簇內(nèi)節(jié)點(diǎn)充當(dāng)簇首的輪數(shù)都是線性規(guī)劃的最優(yōu)解，且固定簇首可以減少因?yàn)轭l繁更換簇首而帶來的控制消息能耗。

3.2.2 opt_leach協(xié)議能耗均衡性分析

圖6是961輪之后每個節(jié)點(diǎn)的剩余能量，100個節(jié)點(diǎn)中大部分節(jié)點(diǎn)的剩余能量在0.02J左右，具有高度的能量均衡性。只有2個節(jié)點(diǎn)剩余能量較高，其中最高的約為0.06J。這是因?yàn)榧词箤^(qū)域節(jié)點(diǎn)均勻分成4個固定簇，每個簇的內(nèi)部節(jié)點(diǎn)位置也不可能完全相同，最終每個簇計算出的最大可持續(xù)輪數(shù)會有微小差異。最終統(tǒng)一將輪數(shù)設(shè)置為不同區(qū)域中計算出的最小值，此時個別節(jié)點(diǎn)依然可以充當(dāng)幾輪簇首，最終這些節(jié)點(diǎn)能量會略高于其它節(jié)點(diǎn)。

4 結(jié)語

本文針對分簇路由協(xié)議提出一種改進(jìn)算法——opt_leach協(xié)議，其思想是使用最優(yōu)化模型中的線性規(guī)劃計算簇間不同路由組合的最優(yōu)比例，以及簇內(nèi)節(jié)點(diǎn)充當(dāng)簇首的最優(yōu)輪數(shù)。實(shí)驗(yàn)結(jié)果表明，使用最優(yōu)化方法確定分簇路由協(xié)議中的簇間傳輸路徑和選擇簇首，可以降低網(wǎng)絡(luò)總能耗，延長網(wǎng)絡(luò)整體壽命。

參考文獻(xiàn)：

[1] LIU X X. Atypical hierarchical routing protocols for wireless sensor networks： a review[J]. ?IEEE Sensors Journal， 2015， 15（10）： 5372-5383.

[2] KHAN I， BELQASMI F，GLITHO R， et al. Wireless sensor network virtualization： a survey[J]. ?IEEE Communications Surveys and Tutorials， 2016， 18（1）： 553-576.

[3] FADEL， ETIMAD， GUNGOR ?V C， et al. A survey on wireless sensor networks for smart grid[J]. ?Computer Communications， 2015， 71（1）： 22-33.

[4] 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.

[5] YOUNIS O， FAHMY ?S. HEED： a hybrid， energy-efficient， distributed clustering approach for ad ? hoc sensor networks[J]. ?IEEE Transactions on Mobile Computing， 2004， 3（4）： 366-379.

[6] 李成法，陳貴海，葉懋，等. 一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 計算機(jī)學(xué)報，2007，30（1）：27-36.

[7] 黃利曉，王暉，袁利永，等. 基于能量均衡高效WSN的LEACH協(xié)議改進(jìn)算法[J]. 通信學(xué)報，2017，38（Z2）：164-169.

[8] 胡源，牛玉剛，鄒媛媛. 基于區(qū)域劃分的WSN非均勻多跳分簇路由算法[J]. 控制與決策，2017，32（9）：1695-1700.

[9] NEAMATOLLAHI P，NAGHIBZADEH M. Distributed unequal clustering algorithm in large-scale wireless sensor networks using fuzzy logic[J]. ?Journal of Supercomputing， 2018， 74（6）： 2329-2352.

[10] NEAMATOLLAHI， PEYMAN， NAGHIBZADEH， et al. Distributed clustering-task scheduling for wireless sensor networks using dynamic hyper round policy[J]. ?IEEE Transactions on Mobile Computing， 2018， 17（2）： 334-347.

[11] WANG A M，YANG D L，SUN D Y. A clustering algorithm based on energy information and cluster heads expectation for wireless sensor networks[J]. ?Computers & Electrical Engineering， 2012， 38（3）： 662-671.

[12] ZHU X R，SHEN L F，YUM TAK-SHING PETER. Hausdorff clustering and minimum energy routing for wireless sensor networks[J]. ?IEEE Transactions on Vehicular Technology，2009，58（2）： 990-997.

[13] GOU H S，YOO Y W. An energy balancing leach algorithm for wireless sensor networks[C]. Information Technology： New Generations （ITNG），2010 Seventh International Conference on，2010：822-827.

[14] 孫彥清，彭艦，劉唐，等. 基于動態(tài)分區(qū)的無線傳感器網(wǎng)絡(luò)非均勻成簇路由協(xié)議[J]. 通信學(xué)報，2014，35（1）：198-206.

[15] 余秀雅，劉東平，楊軍. 基于K-means++的無線傳感網(wǎng)分簇算法研究[J]. 計算機(jī)應(yīng)用研究，2017，34（1）：181-185.

[16] 張雅瓊. 基于K-Means的無線傳感網(wǎng)均勻分簇路由算法研究[J]. 控制工程，2015，22（6）：1181-1185.

[17] 劉述鋼，劉宏立，詹杰，等. 無線傳感網(wǎng)絡(luò)中能耗均衡的混合通信算法研究[J]. 通信學(xué)報，2009，30（1）：12-17.

[18] 孫勇，景博，張宗麟，等. 分簇路由的無線傳感器網(wǎng)絡(luò)通信模式與能量有效性研究[J]. 電子與信息學(xué)報，2007，29（9）：2262-2264.

（責(zé)任編輯：杜能鋼）