基于最優化的能耗均衡分簇路由協議

趙東方 施偉斌

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

關鍵詞：無線傳感器網絡;分簇路由協議;能耗均衡;最優化;線性規劃

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

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

0 引言

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

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

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

1 分簇路由模型介紹

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

1.1 傳感器節點模型

（1）傳感器節點隨機、相對均勻分布在規則圖形的監測區域中。

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

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

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

（5）節點部署具有冗余度，一定區域范圍內節點間的數據可以進行數據融合。

（6）節點可以根據數據需要發送的距離調整發射功率。

1.2 硬件能耗模型

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

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

（2）接收l bit數據能耗：Erv（l，d）=l×Eelec。

（3）數據融合l bit數據能耗：Eag（l，d）=l×Eelec。

2 協議及算法介紹

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

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

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

2.1 均勻分簇

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

2.2 簇間通信方式確定

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

假設一共有n個簇首節點，每個節點用于簇首傳輸的能量為Ei，則簇首節點共有m（m=2n（n-1）/2）種可能路徑。圖2為當n=3時的路由情況，c節點有4種路徑選擇（c→b→a→sink，c→b→sink，c→a→sink，c→sink），b節點有兩種路徑選擇（b→a→sink，b→sink），a節點有一種路徑選擇（a→sink），則根據乘法規則，n=3時一共有4*2*1=8種路由方式。

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

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

2.3 簇內節點成為簇首的輪數和順序

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

2.3.1 節點成為簇首的輪數確定

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

2.3.2 簇首順序確定

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

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

3 仿真分析

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

3.1 opt_leach參數計算

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

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

3.2 協議對比與分析

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

3.2.1 節能性對比

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

3.2.2 opt_leach協議能耗均衡性分析

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

4 結語

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

參考文獻：

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

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

[8] 胡源，牛玉剛，鄒媛媛. 基于區域劃分的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] 孫彥清，彭艦，劉唐，等. 基于動態分區的無線傳感器網絡非均勻成簇路由協議[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.

（責任編輯：杜能鋼）