基于最優(yōu)化的能耗均衡分簇路由協(xié)議

趙東方 施偉斌

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

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

DOI：10. 11907/rjdk. 191936 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP393文獻標識碼：A 文章編號：1672-7800（2020）005-0204-05

0 引言

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

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

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

1 分簇路由模型介紹

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

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

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

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

（3）傳感器節(jié)點被隨機分散后位置固定，網絡部署后不再進行人為干涉。

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

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

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

1.2 硬件能耗模型

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

當傳輸距離為d時，功率放大器所消耗的能量需要依據(jù)發(fā)送器與接收器的距離d與閾值d0進行比較。其中，[d0=εfsεamp]是區(qū)分兩種消耗的閾值。當傳輸間距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é)議是一種集中式和分布式相結合的并行成簇算法。

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

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

2.1 均勻分簇

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

2.2 簇間通信方式確定

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

假設一共有n個簇首節(jié)點，每個節(jié)點用于簇首傳輸?shù)哪芰繛镋i，則簇首節(jié)點共有m（m=2n（n-1）/2）種可能路徑。圖2為當n=3時的路由情況，c節(jié)點有4種路徑選擇（c→b→a→sink，c→b→sink，c→a→sink，c→sink），b節(jié)點有兩種路徑選擇（b→a→sink，b→sink），a節(jié)點有一種路徑選擇（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ī)劃求解。

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

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

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

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

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

2.3.2 簇首順序確定

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

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

3 仿真分析

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

3.1 opt_leach參數(shù)計算

區(qū)域劃分的參數(shù)為x=2，y=2，即簇首的最大跳數(shù)為2，節(jié)點共有兩種路由選擇。通過計算得到兩種路由方式的最佳比例為單跳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é)點將以576輪簇首多跳路由和385輪簇首單跳通信，共持續(xù)961輪。單個簇內每個節(jié)點的輪數(shù)如圖3所示。

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

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

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

3.2.1 節(jié)能性對比

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

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

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

4 結語

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

參考文獻：

[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] 李成法，陳貴海，葉懋，等. 一種基于非均勻分簇的無線傳感器網絡路由協(xié)議[J]. 計算機學報，2007，30（1）：27-36.

[7] 黃利曉，王暉，袁利永，等. 基于能量均衡高效WSN的LEACH協(xié)議改進算法[J]. 通信學報，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ū)的無線傳感器網絡非均勻成簇路由協(xié)議[J]. 通信學報，2014，35（1）：198-206.

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

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

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

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

（責任編輯：杜能鋼）