一種新型的無線傳感器網絡能效路由算法

摘 要：為了解決重復分簇而加劇能量消耗的問題，提出了一種新的無線傳感器網絡能效路由算法——基于簇樹的非均勻分簇路由算法（UCCT）。該算法分為兩步。第一步，劃分網絡區域為面積不相等的兩個區域，對每個區域內的節點集，利用K-中心算法確定其質心節點；以每個質心作為一個簇，計算其中繼能耗開銷；確定各簇間的通信路由。第二步，利用線性規劃方法來確定非質心節點所屬的簇，選取各簇中剩余能量最高的節點為相應的簇頭。該算法的特點是無須重復分簇。仿真結果表明，與ANRB相比，采用UCCT進行通信路由，無線傳感器網絡的壽命延長10.97%，數據吞吐量提高了13.09%。

關鍵詞：無線傳感器網絡； 非均勻分簇； 多跳通信； 線性規劃

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695（2023）08-035-2461-06

doi：10.19734/j.issn.1001-3695.2022.10.0633

Novel energy-efficient routing algorithm in wireless sensor network

Zeng Weijian Liang Jiarong

（1.School of Computer， Electronic amp; Information， Guangxi University， Nanning 530004， China; 2.Guangxi Key Laboratory of Multimedia Communications amp; Network Technology， Nanning 530004， China）

Abstract：To address the problem of increasing energy consumption caused by repeating clustering， this paper proposed a novel energy-efficient routing algorithm for wireless sensor networks—uneven clustering routing algorithm based on cluster tree （UCCT）， which was a two-stage algorithm. In the first stage， the algorithm divided network area into two regions with diffe-rent size. For each region， the algorithm used K-medoids to compute the center nodes in its node set， set each center node obtained as an initial cluster， calculated the relay energy consumption for each cluster，and then determined the routing of inter-cluster communication. In the second stage， the algorithm used linear programming method to add non-center nodes to the initial clusters for forming corresponding new clusters， and selected the node with highest residual energy as the cluster head in its corresponding cluster. The trait of the algorithm was that it didn’t need to repeat clustering. The simulation results show that for a given wireless sensor network， the network lifetime and the throughout obtained by UCCT algorithm are 10.97% and 13.09% more than those obtained by ANRB.

Key words：wireless sensor network; uneven clustering; multi-hop; linear programming

無線傳感器網絡由大量無線傳感器節點組成，主要應用于環境數據的監測和傳輸［1］。當今，無線傳感器網絡已廣泛地應用到災難求助、環境監控、現代戰場、醫療等眾多領域［2，3］。然而，無線傳感器網絡缺點是其節點是電池供能的。因此，在無線傳感器網絡的研究中，能量消耗的效率是一個極為重要的問題［4，5］。為了延長網絡壽命，研究人員提出了諸多能效路由算法， 其中分簇路由算法是研究熱門。LEACH（low energy adaptive clustering hierarchy）是經典的分簇路由算法［6］，其思路是隨機選取網絡中部分節點作為簇頭，成為簇頭的次數越多，下一次成為簇頭的概率越低，以此平衡節點的能耗。但是簇頭選取的隨機性可能導致簇頭位置過于相近，簇頭覆蓋區域重疊而導致能量浪費。算法HEED（hybrid energy-efficient distributed clustering approach）依據主、次兩個參數來選舉簇頭［7］，主參數是節點剩余能量，次參數是簇內傳輸能耗，但是其忽視了遠離基站的簇頭能耗過高問題。文獻［8～11］中簇頭間使用多跳路由的通信方式，降低了遠離基站的簇頭能耗，但是其均勻分簇會導致熱點問題［12］。熱點問題指在多跳路由的無線網絡中，靠近基站的節點因為同時承擔中繼任務和簇內通信任務，流量負載過重導致網絡擁塞甚至網絡中斷。為了緩解熱點問題，文獻［13，14］使用了非均勻分簇，平衡了各簇頭的能耗，但重復分簇會加劇用于控制通信的能量消耗。

上述文獻均采用重復分簇的方式，以提升每次分簇的效果和簇頭選取的質量，但并未考慮到分簇過程中消耗的能量，即控制通信的能量消耗，而這個能量消耗隨著分簇次數的增加而線性增長，當考慮這方面的能耗時，其實際的總能耗往往大大增加。針對這一問題，本文提出一種基于簇樹的非均勻分簇路由算法UCCT（uneven clustering routing algorithm based on cluster tree）。該算法為了減少控制通信的能耗，采取固定分簇策略，只在網絡運行的第一個工作周期內進行分簇，后續工作周期則維持該分簇結果不變，可以有效降低控制通信的能耗；同時為了解決“熱點”問題，通過構建一顆根節點為基站的簇樹，樹中其余節點各自表示一個簇，同時限制靠近基站的簇內網絡節點數量，即增加根節點的孩子節點數量，實現非均勻分簇的目的；該算法有效地降低了網絡能耗，延長了網絡壽命。

1 相關工作

為了延長網絡壽命，文獻［15］最早提出了基于非均勻分簇的路由算法EEUC（energy-efficient uneven clustering），該算法提出了競爭半徑的概念，隨機在網絡中選取部分節點作為臨時簇頭，計算它們的競爭半徑，越靠近基站的半徑越小，反之越大。每個臨時簇頭都需要和相鄰的臨時簇頭競爭，因為靠近基站的臨時簇頭競爭半徑更小，更多簇頭將會勝出，從而形成較小的簇，降低了簇頭在簇內通信的能耗，更多的能量可以用于簇間通信。但是基于隨機的機制會使得簇頭數量有波動，造成能耗的不均衡。文獻［16］在EEUC的基礎上進行了改進，提出了UCR（unequal clustering routing），在簇頭競爭階段，加入了節點剩余能量、中繼節點的能耗開銷和節點到基站的距離等指標的衡量，延長了網絡的壽命。

聚類算法是一種無監督學習方法［17］，可以對無標簽的樣本點根據數據之間的信息關系進行數據分類，對數據對象實現分組。常見的聚類算法有K-means［18］、K-medoids［19］和Affinity Propagation［20］等算法。聚類算法也被廣泛用于無線網絡分簇算法。文獻［21］提出一種能量感知的分簇算法，對網絡中所有節點使用K-medoids，把網絡分成K個子網絡，每個子網絡內部使用LEACH算法把數據發送至子網絡內的網關節點，再由網關節點直接轉發至基站。但是網關節點沒有采用多跳路由的方式，距離基站較遠的網關節點能量消耗過高。文獻［22］提出一個基于K-medoids的分簇算法，先使用K-medoids把網絡劃分為若干簇，質心作為簇頭，通過遺傳算法（genetic algorithm）計算基站的最優位置來減少簇頭的通信能耗。但是并未考慮到能量消耗的不均問題，簇內承擔多跳路由的中繼節點和遠離基站的簇頭能耗過高。文獻［23］提出一種基于改進K-medoids的分簇算法，但是其僅適用于車載自組網絡，且均勻分簇不利于能耗的平衡。文獻［24］使用模糊C-均值和遺傳算法優化分簇效果，依據節點到簇內其余節點的平均距離、節點到基站的距離和節點的剩余能量三個參數選舉簇頭，得到了良好的成簇效果，但動態分簇加劇了額外的控制通信能耗開銷。

2 預備知識

3 算法

UCCT是集中式算法，使用固定分簇的策略，以輪的工作方式運行，第一輪包括簇間路由構建、聚類分簇、簇頭競選和數據傳輸四個階段，第二輪以及往后輪次包括簇頭競選和數據傳輸兩個階段。在網絡初始化時，網絡中所有節點把自身位置信息發送至基站，基站接收到節點的信息后匯總，進入簇間路由構建和聚類分簇階段，基站完成計算后把聚類信息廣播至所有節點，各節點依據接收的信息組成相應的簇群，各簇群選取簇內剩余能量最高的節點作為簇頭，然后進入數據傳輸階段。從第二輪起，簇間路由構建和聚類分簇兩階段的工作不再執行。每一輪工作周期的最后，簇頭間相互廣播一次消息，以確定是否出現簇死亡而需要更新簇間路由。

在簇間路由構建階段，首先劃分監控區域為兩個子區域，靠近基站的面積小，遠離基站的面積大，分別對兩塊區域內的節點使用K-medoids算法得到質心的點集；計算每個質點的中繼能耗開銷，選擇其中開銷最小者對應的節點作為其中繼節點，令每個質點作為一個簇，確定簇間的多跳路由；在聚類分簇階段，建立關于通信能耗的線性規劃問題f，求解f可得簇的網絡壽命；對于每個簇，計算當前簇的壽命，在剩余節點集中選擇距離簇最近一個，加入該點到簇內，計算加入新節點后簇的壽命，令簇更新的代價等于簇加入新節點前的壽命減去加入新節點后的壽命，選擇所有簇的更新代價中最小者，更新相應的簇為加入新節點的簇。每次僅更新一個簇，不斷循環，直到沒有節點剩余。分簇完成后，多跳路由固定，無須再次分簇，每個工作周期都由簇內剩余能量最高的節點作為簇頭，以平衡簇內各節點的能耗。

3.1 簇間路由構建

3.2 聚類分簇

3.3 簇頭選舉

3.4 算法性能分析

4 仿真結果與分析

4.1 實驗參數設置

4.2 仿真實驗一

四種算法的存活節點數和運行輪數對比曲線如圖3所示，四種算法在第1、100、200和300個節點的存活時間如圖4所示。定義第1個節點死亡時間為網絡的壽命。從圖3、4可得UCCT算法下網絡壽命為951輪，對比857輪的ANRB、689輪的EBRAA和579輪的I-LEACH，分別提升了10.97%、38.02%和64. 25%。對比33%的節點死亡時間、66%的節點死亡時間和全部節點死亡時間，本文算法均優于ANRB、EBRAA和I-LEACH。在節點存活時間的仿真中，UCCT算法總體上優于其余三者。本文算法采用固定分簇策略、非均勻分簇方法和多跳通信方式，相比重復分簇的ANRB、均勻分簇的EBRAA和單跳通信的I-LEACH，降低了簇頭的通信能耗，緩解了部分簇頭能耗高而過早死亡問題，從而延長了網絡生命周期。

圖5給出了四種算法在網絡能耗方面的對比。分析可知UCCT算法能量消耗速度低于ANRB、EBRAA和I-LEACH，在簇頭采取多跳通信情況下，可以避免簇頭直接與基站通信造成能耗加劇；且其余三種算法頻繁地進行分簇工作，也會進一步加劇額外的能量消耗，而UCCT無須重復分簇，降低了額外的能量開銷，從而在能量消耗速度上優于ANRB、EBRAA和I-LEACH。

網絡中的能量消耗分為數據通信能耗和控制通信能耗，前者是每一輪工作周期中節點發送數據至簇頭和簇頭轉發到其他簇頭或基站的能耗，后者包括聚類分簇、競選簇頭和建立多跳路由等步驟中所消耗的能量。對于UCCT，其控制通信能耗包含兩部分，簇頭競選的能耗和簇頭間相互發送消息以計算多跳路由的能耗。ANRB和EBRAA相比UCCT增加了聚類分簇的能耗，每一輪工作周期開始前，節點要發送一個控制消息到基站，基站對當前存活的節點進行重新分簇后，再回復一個控制消息到節點。I-LEACH是分布式算法，控制通信能耗僅包含聚類分簇能耗，首先隨機選取部分節點成為簇頭，在分簇階段，全部簇頭節點向全部非簇頭節點廣播一個消息，非簇頭節點在接收了簇頭發來的消息后根據接收的先后順序，回復消息給第一個簇頭以確定加入該簇。圖6給出了四種算法在總能量消耗中控制通信能耗占比的對比，本文算法無須重復分簇，控制通信能耗占比最低；ANRB和EBRAA需要重復分簇，控制通信能耗占比高于UCCT；I-LEACH需要反復分簇，且分布式算法需要節點間頻繁發送消息，所消耗的能量，高于其余三種集中式算法，故占比最高。

4.4 仿真實驗三

吞吐量是衡量路由算法優劣的一個重要指標。定義吞吐量為網絡中全體節點死亡時，基站在整個過程中接收到的數據包個數。四種算法在吞吐量方面的對比如圖7所示，在UCCT算法下基站總共接收了326 272個數據包，分別是ANRB的1.131倍、EBRAA的1.284倍和I-LEACH的1.591倍。UCCT算法可以延長節點的存活時間，從而提高基站接收數據包的個數。

4.5 仿真實驗四

在無線傳感器網絡中，時延表示一個周期內基站成功接收到所有節點數據包的總耗時，時延越小，數據的傳輸效率越高。假定每個節點有固定的概率在采集數據后發送數據包，成功發送一個數據包需要一個時隙，本文使用文獻［31］的延時計算方式。四種算法的網絡時延對比如圖8所示，UCCT采取固定分簇策略和使用線性規劃近似計算節點能耗，使得分簇的效果更合理，時延總體上低于ANRB和EBRAA。I-LEACH采用隨機分簇方式，當前輪次簇頭數量過少時，可能出現部分簇內節點過多而導致時延過長，呈現出一定波動。

4.6 仿真實驗五

計算開銷是衡量算法性能的一個重要指標，圖9是四種算法的運行總耗時對比圖，從網絡初始化階段開始，直到網絡中所有節點能量耗盡結束。I-LEACH是分布式算法，效率最高；UCCT僅在第一輪需要等待基站計算分簇結果，總耗時30.603 s，高于I-LEACH，低于ANRB的和EBRAA，后兩者在每一個工作周期內的分簇階段均需要循環迭代以取得更好的成簇效果。

5 結束語

本文提出了一種降低網絡能耗的算法——基于簇樹的非均勻分簇路由算法。該算法把網絡區域劃分為面積不等的兩個子區域，分別對兩區域內的節點進行分簇從而實現非均勻分簇。首先通過聚類算法得到質心點集，計算質點的中繼能耗，確定質點間的多跳路由，令每個質點作為一個簇，從而確定簇間多跳路由；建立線性規劃求解簇的壽命，通過循環，讓每個非質心節點加入對簇壽命提升最大的對應的簇，直到沒有節點剩余，最終得到一顆根節點為基站的簇樹，簇樹中每個節點對應一個簇。該算法僅分簇一次，有效降低了控制通信的能量消耗。從仿真結果分析中可知，相比ANRB、EBRAA和I-LEACH算法，UCCT算法提高了能量的利用效率，平衡了節點的能耗，延長了網絡的生命周期。一定數量的節點故障或者鏈路失效時仍能保證正常路由的虛擬骨干構建是一個有趣的問題，下一步工作是無線網絡的容錯虛擬骨干的能效路由算法研究。

參考文獻：

［1］Fu Xiuwen， Yao Haiqing， Yang Yongsheng. Modeling cascading fai-lures for wireless sensor networks with node and link capacity［J］. IEEE Trans on Vehicular Technology， 2019，68（8）： 7828-7840.

［2］Haque M E， Baroudi U. Dynamic energy efficient routing protocol in wireless sensor networks［J］. Wireless Networks， 2020，26（5）： 3715-3733.

［3］Chen Jie， Date P， Chancellor N， et al. Controller-based energy-aware wireless sensor network routing using quantum algorithms［J］. IEEE Trans on Quantum Engineering， 2022，3：1-12.

［4］梅家棟， 南建國. 無人機自組網基于加權的穩定分簇算法［J］. 計算機應用研究， 2021，38（11）： 3411-3416. （Mei Jiadong， Nan Jianguo. Weighted stable clustering algorithm for flying Ad hoc networks［J］. Application Research of Computers， 2021，38（11）： 3411-3416.）

［5］呂濤， 朱清新， 朱玉玉. 一種能耗均衡的無線傳感器網絡分簇算法［J］. 計算機應用， 2012，32（11）： 3107-3111. （Lyu Tao， Zhu Qingxin， Zhu Yuyu. Energy-balanced adaptive clustering algorithm for wireless sensor network［J］. Journal of Computer Applications， 2012，32（11）： 3107-3111.）

［6］Heinzelman W R， Chandrakasan A， Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks［C/OL］//Proc of the 33rd Annual Hawaii International Conference on System Sciences. （2002-08-06）. https：//doi.org/10.1109/HICSS.2000.926982.

［7］Younis O， Fahmy S. HEED： a hybrid， energy-efficient， distributed clustering approach for Ad hoc sensor networks［J］. IEEE Trans on Mobile Computing， 2004，3（4）： 660-669.

［8］朱開磊， 孫愛晶. 基于布谷鳥優化K均值的WSN分簇路由算法［J］. 物聯網學報， 2022，6（1）： 73-81. （Zhu Kailei， Sun Aijing. WSN clustering routing algorithm based on Cuckoo search algorithm optimized K-means［J］. Chinese Journal on Internet of Things， 2022，6（1）： 73-81.）

［9］余秀雅， 劉東平， 楊軍. 基于K-means+的無線傳感網分簇算法研究 ［J］. 計算機應用研究， 2017，34（1）： 181-185. （Yu Xiuya， Liu Dongping， Yang Jun. Research on wireless sensor networks clustering algorithm based on K-means+［J］. Application Research of Computers， 2017，34（1）： 181-185.）

［10］葉繼華， 萬葉晶， 劉長紅， 等. 一種結合K-means均勻分簇和數據回歸的WSN能量均衡策略［J］. 小型微型計算機系統， 2017，38（8）： 1688-1692. （Ye Jihua， Wan Yejing， Liu Changhong， et al. An energy balanced strategy for WSN combine uniform clustering by K-means and data regression［J］. Journal of Chinese Computer Systems， 2017，38（8）： 1688-1692.）

［11］Lipare A， Edla D R， Dharavath R. Fuzzy rule generation using modified PSO for clustering in wireless sensor networks［J］. IEEE Trans on Green Communications and Networking， 2021，5（2）： 846-857.

［12］Arjunan S， Pothula S. A survey on unequal clustering protocols in wireless sensor networks［J］. Journal of King Saud University-Computer and Information Sciences， 2019，31（3）： 304-317.

［13］李成法， 陳貴海， 葉懋， 等. 一種基于非均勻分簇的無線傳感器網絡路由協議［J］. 計算機學報， 2007（1）： 27-36. （Li Chengfa， Chen Guihai， Ye Mao， et al. An uneven cluster-based routing protocol for wireless sensor networks［J］. Chinese Journal of Compu-ters， 2007（1）： 27-36.）

［14］熊科， 樊曉平， 劉少強， 等. 一種基于非均勻分布雙簇頭的無線傳感器網絡分簇算法［J］. 傳感技術學報， 2008（7）： 1207-1211. （Xiong Ke， Fan Xiaoping， Liu Shaoqiang， et al. Clustering algorithm based on uneven distributed double cluster heads for wireless sensor networks［J］. Chinese Journal of Sensors and Actuators， 2008（7）： 1207-1211.）

［15］Li Chengfa， Ye Mao， Chen Guihai， et al. An energy-efficient unequal clustering mechanism for wireless sensor networks［C］//Proc of IEEE International Conference on Mobile Ad hoc and Sensor Systems. Piscataway， NJ： IEEE Press， 2005： 604.

［16］Chen Guihai， Li Chengfa， Ye Mao， et al. An unequal cluster-based routing protocol in wireless sensor networks［J］. Wireless Networks， 2009，15（2）： 193-207.

［17］楊俊闖， 趙超. K-means聚類算法研究綜述［J］. 計算機工程與應用， 2019，55（23）： 7-14. （Yang Junchuang， Zhao Chao. A survey of K-means clustering algorithms［J］. Computer Engineering and Applications， 2019，55（23）： 7-14.）

［18］Kanungo T， Mount D M， Netanyahu N S， et al. An efficient K-means clustering algorithm： analysis and implementation［J］. IEEE Trans on Pattern Analysis and Machine Intelligence， 2002，24（7）： 881-892.

［19］Park H S， Jun C H. A simple and fast algorithm for K-medoids clustering［J］. Expert Systems with Applications， 2009，36（2）： 3336-3341.

［20］Frey B J， Dueck D. Clustering by passing messages between data points［J］. Science， 2007，315（5814）： 972-976.

［21］Faid A， Sadik M， Sabir E. EACA： an energy aware clustering algorithm for wireless IoT sensors［C］//Proc of the 28th International Conference on Telecommunications. Piscataway， NJ： IEEE Press， 2021： 1-6.

［22］Mukase S， Xia Kewen， Umar A. Optimal base station location for network lifetime maximization in wireless sensor network［J］. Electronics， 2021，10（22）： 2760.

［23］Hajlaoui R， Alsolami E， Moulahi T， et al. An adjusted K-medoids clustering algorithm for effective stability in vehicular Ad hoc networks［J］. International Journal of Communication Systems， 2019，32（12）： e3995.

［24］董發志， 丁洪偉， 楊志軍， 等. 基于遺傳算法和模糊C均值聚類的WSN分簇路由算法［J］. 計算機應用， 2019，39（8）： 2359-2365. （Dong Fazhi， Ding Hongwei， Yang Zhijun， et al. WSN clustering routing algorithm based on genetic algorithm and fuzzy C-means clustering［J］. Journal of Computer Applications， 2019，39（8）： 2359-2365.）

［25］方旺盛， 陳朕浩， 胡中棟. 分區和能耗均衡的LEACH路由改進算法［J］. 計算機工程與設計， 2019，40（10）： 2746-2751. （Fang Wangsheng， Chen Zhenhao， Hu Zhongdong. Improved LEACH algorithm based on parting and energy consumption balanced［J］. Computer Engineering and Design， 2019，40（10）： 2746-2751.）

［26］劉大同， 周建寶， 郭力萌， 等. 鋰離子電池健康評估和壽命預測綜述［J］. 儀器儀表學報， 2015，36（1）： 1-16. （Liu Datong， Zhou Jianbao， Guo Limeng， et al. Survey on lithiumion battery health assessment and cycle life estimation ［J］. Chinese Journal of Scientific Instrument， 2015，36（1）： 1-16.）

［27］Cohen M B， Lee Y T， Song Zhao. Solving linear programs in the current matrix multiplication time［J］. Journal of the ACM， 2021，68（1）： article No. 3.

［28］張帥， 楊清海， 馮友兵. 基于能耗均衡的LEACH改進方法［J］. 計算機應用與軟件， 2020，37（1）：133-137. （Zhang Shuai， Yang Qingmei， Feng Youbing. LEACH improved method based on energy consumption balance［J］. Computer Applications and Software， 2020，37（1）： 133-137.）

［29］茍平章， 張芬， 毛剛， 等. 基于AGENS聚類的能耗均衡WSNs優化路由算法［J］. 計算機工程與科學， 2020，42（4）： 620-627. （Gou Pingzhang， Zhang Fen， Mao Gang， et al. An energy-balanced WSNs routing optimization algorithm based on AGENS clustering［J］. Computer Engineering and Science， 2020，42（4）： 620-672.）

［30］苗俊先， 趙一帆， 李波， 等. WSN中能耗均衡的非均勻分簇路由算法［J］. 計算機工程與設計， 2022，43（2）： 301-307. （Miao Junxian， Zhao Yifan， Li Bo， et al. Non-uniform clustering routing algorithm for balanced energy consumption in WSN［J］. Computer Engineering and Design， 2022，43（2）： 301-307.）

［31］熊成彪， 丁洪偉， 董發志， 等. 一種基于LEACH的低延遲和低功耗的WSN分簇算法［J］. 計算機科學， 2020，47（1）： 258-264. （Xiong Chengbiao， Ding Hongwei， Dong Fazhi， et al. Low-delay and low-power clustering algorithm based on LEACH［J］. Computer Science， 2020，47（1）： 258-264.）