基于k-means聚類的無線傳感器網(wǎng)絡低功耗路由算法

摘 要：為提高無線傳感器網(wǎng)絡（WSN）中傳感器節(jié)點的能量利用率以延長傳感器網(wǎng)絡的生命周期，提出基于k-means聚類的WSN低功耗路由算法。先按照距離乘積最大規(guī)則選取聚類初始簇中心，并在k-means算法迭代過程中引入能耗因子來優(yōu)化k-means的分簇效果，降低基站附近節(jié)點的能耗和簇內的數(shù)據(jù)傳輸能耗；再使用Dijkstra算法搜尋簇首和基站間的最低功耗傳輸路徑，以降低簇首能耗。仿真結果表明，該算法提高了網(wǎng)絡的能量利用率，有效延長了網(wǎng)絡的生命周期，使首個死亡節(jié)點延后出現(xiàn)，對WSN實現(xiàn)了更好的優(yōu)化。

關鍵詞：WSN；k-means均值聚類算法；低功耗路由；最低功耗傳輸路徑；Dijkstra算法；能耗均衡

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2025）02-00-05

0 引 言

WSN（Wireless Sensor Network）主要由大量具備無線通信能力的傳感器節(jié)點和少量基站組成，可以實現(xiàn)對于某一區(qū)域的實時監(jiān)測。其中傳感器節(jié)點負責采集監(jiān)測數(shù)據(jù)，并傳輸給基站以便處理分析，但一些傳感器的安裝環(huán)境使得節(jié)點維護變得困難且大多傳感器由電池供電，一旦電能耗盡，則該節(jié)點立即失效。因此，如何在能量有限的情況下延長傳感器節(jié)點的生命周期已成為WSN技術的重要研究方向。

針對該問題，基于分簇路由協(xié)議的研究層出不窮。文獻[1]提出了LEACH算法，該算法基于分簇路由協(xié)議，通過等概率隨機選取簇首來均衡各節(jié)點的能耗，使節(jié)點有更長的生命周期，但沒有考慮到節(jié)點剩余能量、節(jié)點所處位置以及節(jié)點密度，這可能使某些節(jié)點過快凋亡。針對LEACH算法存在的問題，文獻[2]提出了LEACH-CE算法，通過設定能量閾值使剩余能量過低的節(jié)點避免被選為簇首，避免小部分節(jié)點過早死亡。文獻[3]將k-means算法和LEACH算法進行綜合，實現(xiàn)有效分簇，降低了簇內的通信能耗。文獻[4]提出了混合節(jié)能分布式分簇（HEED）協(xié)議，該協(xié)議通過綜合節(jié)點剩余能量和次要參數(shù)（例如節(jié)點的鄰近度）來定期選擇簇頭。文獻[5]設計了一種基于非均勻分簇的分層路由協(xié)議，通過分層機制及競爭機制選取簇首，使簇首節(jié)點分布更加合理，有效地均衡了節(jié)點能量消耗。文獻[6]提出了一種雙層樹型高能效多鏈路由算法，對成鏈過程中產(chǎn)生的孤立點進行樹型結構化處理，縮短了數(shù)據(jù)傳遞路徑長度，對宿節(jié)點附近的普通節(jié)點和鏈頭進行不入鏈操作以減少數(shù)據(jù)逆?zhèn)鬟f。文獻[7]提出了一種基于改進灰狼優(yōu)化算法的分區(qū)多鏈路由協(xié)議，該協(xié)議采用分區(qū)成鏈的方法，使每個分簇構造一條最優(yōu)簇內鏈，采用改進的灰狼優(yōu)化算法進行簇頭尋優(yōu)并構造一條簇頭鏈，最終通過這條鏈將采集到的信息朝基站方向傳遞。文獻[8]用k-means算法進行分簇，以簇內分層方式選取距離基站更近、剩余能量更多的節(jié)點作為簇首。

以上算法針對WSN能耗問題進行了改進，本文綜合考慮WSN能耗問題，提出了基于k-means聚類的WSN低功耗路由算法（Low-power Routing Algorithm based on k-means Clustering for Wireless Sensor Networks），降低了WSN的能耗，實現(xiàn)了更好的分簇效果[9]。

1 Dijkstra算法和k-means聚類算法

1.1 Dijkstra算法

Dijkstra算法[10]由荷蘭科學家Dijkstra于1959年提出，用于解決具有邊權重的有向圖單源最短路徑問題。本文使用Dijkstra算法搜尋所有節(jié)點與基站之間的最低功耗傳輸路徑，使傳輸路徑上所有節(jié)點消耗的總能量最低。

1.2 k-means聚類算法

k-means聚類算法[11]是一種無監(jiān)督學習算法，可根據(jù)相似性對數(shù)據(jù)進行分類。本文基于k-means聚類算法，提出了一種WSN低功耗路由算法。

2 系統(tǒng)架構

2.1 系統(tǒng)模型

假定所有傳感器節(jié)點隨機分布在正方形區(qū)域內，并有以下設定：

（1）WSN由多個傳感器節(jié)點和一個基站組成；

（2）基站的能量無限制；

（3）傳感器節(jié)點和基站靜止，且坐標已知；

（4）任意節(jié)點都能進行數(shù)據(jù)融合。

2.2 能耗模型

在WSN低功耗路由算法研究中，一般采用一階能耗模型，故本文也采用一階能耗模型。

發(fā)送數(shù)據(jù)所消耗的能量由式（1）可得：

（1）

式中：L為數(shù)據(jù)量，單位是bit；Eelec為發(fā)射電路和接收電路的功耗；εfs為自由空間信道模型下放大器功率的放大倍數(shù)；εamp為多路徑衰減模型下放大器功率的放大倍數(shù)；d為發(fā)送節(jié)點與接收節(jié)點之間的歐氏距離。劃分空間模型的閾值d0由式（2）計算可得：

（2）

接收數(shù)據(jù)所消耗的能量由式（3）可得：

（3）

在分簇路由算法中，簇首將簇內普通節(jié)點采集的數(shù)據(jù)進行數(shù)據(jù)融合。對長度為L的數(shù)據(jù)包進行融合時消耗的能量EDA由式（4）可得：

（4）

2.3 算法流程

本文算法的流程如下：

（1）基站確定初始簇中心；

（2）基站利用改進的k-means聚類算法進行網(wǎng)絡分簇；

（3）基站確定簇首到基站的數(shù)據(jù)傳輸路徑；

（4）數(shù)據(jù)傳輸；

（5）確定是否有新的節(jié)點死亡，若有，則轉向步驟（6），否則轉向步驟（2）；

（6）確定網(wǎng)絡節(jié)點是否全部死亡，若是，則流程結束，否則轉向步驟（1）。

算法流程如圖1所示。

3 基于k-means聚類的WSN低功耗路由算法

3.1 網(wǎng)絡分簇

本文算法下，WSN通過分簇結構進行數(shù)據(jù)傳輸，普通節(jié)點將數(shù)據(jù)直接傳輸給簇首或在與基站距離較近時直接傳輸給基站。網(wǎng)絡數(shù)據(jù)傳輸路徑如圖2所示。

3.1.1 最優(yōu)分簇數(shù)

最優(yōu)分簇數(shù)K由式（5）可得：

（5）

式中：N為節(jié)點個數(shù)；M為正方形區(qū)域的邊長；dtoBS為基站與節(jié)點之間的平均距離。

3.1.2 初始簇中心的選取

在傳統(tǒng)k-means聚類算法中，隨機選取K個節(jié)點作為初始簇中心，然而當初始簇中心分布比較集中時，在迭代過程中不同的簇中心可能距離過近甚至完全重合，使得不同的簇出現(xiàn)重疊。為了避免這種情況出現(xiàn)，使用文獻[12]的初始簇中心選取方式，為網(wǎng)絡的全部N個節(jié)點選出K個初始簇中心。

3.1.3 簇首選取

傳統(tǒng)k-means聚類算法在選取新的簇中心時沒有考慮向基站傳輸數(shù)據(jù)時的能耗，這使得當簇中心距離基站較遠時能耗更高。因此引入能耗因子概念，并通過計算簇內節(jié)點的能耗因子來確定新的簇中心。

若某節(jié)點di所在的簇共有l(wèi)個節(jié)點（d1～dl），則節(jié)點di的能耗因子ds（di）由式（6）計算可得：

（6）

式中：dir（di， dj）為節(jié)點di和節(jié)點dj之間直接傳輸一次數(shù)據(jù)時兩個節(jié)點所消耗的總能量；ene（di）為節(jié)點di沿最低功耗路徑向基站傳輸數(shù)據(jù)時該路徑上各節(jié)點消耗的總能量。

為避免剩余能量過低的節(jié)點被選取為簇中心，需在k-means算法迭代過程中選取新的簇中心，方法如下：每次迭代后，計算簇內每個節(jié)點di的能耗因子ds（di），以及簇內每個節(jié)點的剩余能量與簇內平均剩余能量的差，若差值大于閾值α，則相應節(jié)點不能被選取為簇中心，應從剩余節(jié)點中選取能耗因子ds（di）最小的節(jié)點作為新的簇中心。

3.1.4 普通節(jié)點入簇

在傳統(tǒng)k-means聚類算法中，所有普通節(jié)點都加入距離最近的簇中心所在的簇，但距離基站更近的節(jié)點向簇中心傳輸數(shù)據(jù)時會消耗更多的能量。針對該問題，本文對k-means聚類算法做了如下改進：若普通節(jié)點與基站的距離小于該節(jié)點與簇中心的距離，則該節(jié)點加入以基站為首的簇，否則加入距離最近的簇中心所在的簇。

所有簇中心不再變化時k-means算法的迭代過程結束，此時簇中心被選取為簇首，普通節(jié)點加入距離最近的簇首所在的簇或加入以基站為首的簇。

3.2 簇首向基站傳輸數(shù)據(jù)的路徑優(yōu)化

由于大部分簇首距離基站較遠，如果簇首通過單跳的方式直接向基站傳輸數(shù)據(jù)，則會使簇首在此過程中消耗大量能量。為了避免簇首消耗過多能量，簇首通過多跳的方式向基站傳輸數(shù)據(jù)。

3.2.1 最低功耗傳輸路徑

為降低簇首通過多跳方式向基站傳輸數(shù)據(jù)時網(wǎng)絡的總能耗，使用Dijkstra算法搜尋所有節(jié)點與基站之間的最低功耗傳輸路徑，使任意節(jié)點沿其最低功耗傳輸路徑向基站傳輸數(shù)據(jù)時，傳輸路徑上所有節(jié)點消耗的總能量最低。

3.2.2 節(jié)點能耗平衡

路徑上某些節(jié)點因能量消耗過快而過早凋亡，使簇首并非總沿著最低功耗傳輸路徑向基站傳輸數(shù)據(jù)，因此需要為每個節(jié)點尋找多條能耗較低的傳輸路徑。

尋找多條能耗較低的傳輸路徑時，需要為每個節(jié)點選取多個子節(jié)點。為便于描述，先做如下約定：Ave（B）表示節(jié)點B向基站傳輸數(shù)據(jù)的全部可用路徑的平均總功耗，Q（B）表示節(jié)點B向基站傳輸數(shù)據(jù)的可用傳輸路徑的個數(shù)，H（B）表示最低功耗傳輸路徑下節(jié)點B的子節(jié)點（最低功耗傳輸路徑下節(jié)點B向子節(jié)點H（B）傳輸數(shù)據(jù)），G（B）表示所有節(jié)點B的子節(jié)點的集合（簇首向基站傳輸數(shù)據(jù)的路徑上，節(jié)點B只能從集合G（B）中選取進行數(shù)據(jù)傳輸），Re（B）表示節(jié)點B的剩余能量。選取子節(jié)點的步驟如下：

（1）全部節(jié)點中，在最低功耗傳輸路徑上直接向基站傳輸?shù)墓?jié)點排序在前，剩余節(jié)點按最低功耗傳輸路徑的總功耗從小到大排序，設最終排序為{B1， B2， ...， B100}。

（2）假設有3個節(jié)點的最低功耗傳輸路徑直接向基站傳輸，則這3個節(jié)點分別是B1、B2、B3，且Ave（B1）=h（B1），Ave（B2）=h（B2），Ave（B3）=h（B3）。

（3）因為{B1， B2， ...， B100}按照最低功耗從小到大排序，為了盡可能降低功耗，排序靠前的節(jié)點不應向排序靠后的節(jié)點傳輸數(shù)據(jù)。步驟如下：

①計算Ave（B1）+dir（B4， B1）、Ave（B2）+dir（B4， B2）、Ave（B3）+dir（B4， B3），將這些數(shù)值小于h（B4）的節(jié)點按數(shù)值從小到大排序并從中選出前2個節(jié)點，G（B4）由這2個節(jié)點、h（B4）和基站組成。

②計算Ave（B1）+dir（B5， B1）、Ave（B2）+dir（B5， B2）、Ave（B3）+dir（B5， B3）、Ave（B4）+dir（B5， B4），將這些數(shù)值小于h（B5）的節(jié)點按數(shù)值從小到大排序并從中選出前2個節(jié)點，G（B5）由這2個節(jié)點、h（B5）和基站組成。

……

計算Ave（B1）+dir（B100， B1）、Ave（B2）+dir（B100， B2）、Ave（B3）+dir（B100， B3）、…、Ave（B99）+dir（B100， B99），將這些數(shù)值小于h（B100）的節(jié)點按數(shù)值從小到大排序并從中選出前2個節(jié)點，G（B100）由這2個節(jié)點、h（B100）和基站組成。

在簇首向基站傳輸數(shù)據(jù)的路徑上，每個節(jié)點只能從上述步驟選出的子節(jié)點中選取一個節(jié)點進行數(shù)據(jù)傳輸。為避免選取剩余能量過低的子節(jié)點進行數(shù)據(jù)傳輸，本文引入如下兩條規(guī)則：

（1）若G（B）中所有節(jié)點剩余能量的平均值與G（B）中某節(jié)點剩余能量的差值小于閾值β1，則在簇首向基站傳輸數(shù)據(jù)的路徑上，節(jié)點B不能向該節(jié)點傳輸數(shù)據(jù)。

（2）若節(jié)點B的剩余能量Re（B）與G（B）中所有節(jié)點剩余能量的平均值的差值大于閾值β2，則在簇首向基站傳輸數(shù)據(jù)的路徑上，節(jié)點B直接向基站傳輸數(shù)據(jù)。

簇首向基站傳輸數(shù)據(jù)時，在滿足上述兩個規(guī)則的條件下，在可用的傳輸路徑中選擇總功耗最低的路徑作為數(shù)據(jù)傳輸路徑。

4 仿真及結果分析

4.1 仿真參數(shù)及性能指標

為分析算法的性能，本文利用MATLAB對算法進行仿真，并將本文提出的算法與LEACH算法、LEACH-C算法和FA-LEACH算法[9]進行對比。

WSN仿真模型：設定在400 m×400 m正方形區(qū)域內隨機分布100個節(jié)點，在正方形區(qū)域的正中心有1個基站。本文算法中的閾值α、β1和β2均取0.01 J。其他仿真參數(shù)見表1。

網(wǎng)絡剩余總能量的變化情況反映了網(wǎng)絡總體能量的消耗速度以及能量的利用率，而存活節(jié)點個數(shù)的變化情況反映了WSN的監(jiān)測區(qū)域覆蓋率和WSN的生命周期，因此本文用網(wǎng)絡的剩余總能量和存活節(jié)點個數(shù)這兩項指標來評估算法的性能。

4.2 仿真結果分析

通過改進k-means聚類算法對網(wǎng)絡進行分簇，由式（5）計算得到最優(yōu)分簇數(shù)為9，因此選取9個初始簇中心。普通節(jié)點根據(jù)與初始簇中心之間的距離和與基站之間的距離入簇，且網(wǎng)絡每傳輸20輪都避開能量過低的節(jié)點重新分簇。初始分簇與多次迭代后的網(wǎng)絡分簇如圖3所示。

不同算法下存活節(jié)點數(shù)隨網(wǎng)絡運行輪數(shù)的變化如圖4所示。

根據(jù)圖4可知，本文算法下的網(wǎng)絡中首個節(jié)點死亡時間相較于LEACH、LEACH-C和FA-LEACH分別延長了130%、57%和18%。當有節(jié)點死亡后，就可能造成WSN的覆蓋空洞。數(shù)據(jù)表明，本文算法能夠有效延長網(wǎng)絡在無覆蓋空洞下的工作時長。本文算法下的網(wǎng)絡中全部節(jié)點死亡時間相較于LEACH、LEACH-C和FA-LEACH分別延長了56%、30%和10%，表明本文算法能夠有效延長網(wǎng)絡的生命周期。

不同算法下網(wǎng)絡的剩余總能量隨輪數(shù)的變化如圖5所示。從圖5可以看出，本文算法下網(wǎng)絡的剩余總能量始終高于LEACH、LEACH-C和FA-LEACH算法，并且當網(wǎng)絡剩余總能量為50%時，LEACH、LEACH-C、FA-LEACH和本文算法下的網(wǎng)絡分別運行了275輪、349輪、440輪和504輪，這表明相較于其他3種算法，本文算法的能量利用率更高。

5 結 語

本文提出了基于k-means聚類的WSN低功耗路由算法，按距離乘積最大規(guī)則選取聚類初始簇中心，使初始簇中心盡可能分散以提高k-means聚類的穩(wěn)定性和收斂速度。本文在k-means算法迭代過程中引入能耗因子概念并通過計算能耗因子更合理地選取簇中心和簇首，使距離基站較近的節(jié)點加入以基站為首的簇以降低基站附近節(jié)點的能耗，使簇首通過多跳的方式向基站傳輸數(shù)據(jù)以降低簇首的能耗，并為每個節(jié)點尋找多條向基站傳輸數(shù)據(jù)的路徑，以平衡簇首向基站傳輸數(shù)據(jù)的路徑上各節(jié)點的能耗。

仿真結果表明，相較于LEACH、LEACH-C和FA-LEACH算法，本文提出的算法能夠有效地延后首個死亡節(jié)點出現(xiàn)的時間、延長網(wǎng)絡生命周期和提高能量利用率。

注：本文通訊作者為張贊。

參考文獻

[1] HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An application-specific protocol architecture for wireless micro sensor networks [J]. IEEE trans on wireless communications， 2002， 1（4）： 660-670.

[2] TRIPATHI M， BATTULA R B， GAUR M S， et al. Energy efficient clustered routing for wireless sensor network [C]// 2013 IEEE 9th Int Conf on Mobile Ad-hoc and Sensor Networks. Dalian， China： IEEE， 2013： 330-335.

[3] MAHBOUB A， ARIOUA M， EN-NAIMI E M. Energy-efficient hybrid k-means algorithm for clustered WSN [J]. International journal of electrical and computer engineering， 2017， 7（4）： 2054-2060.

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

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

[6]胡中棟，張康，王振東.一種雙層樹型高能效多鏈路由算法[J].傳感技術學報，2019，32（1）：127-132.

[7]安葳鵬，邵一帆.基于改進灰狼優(yōu)化算法的無線傳感器網(wǎng)絡路由協(xié)議[J].傳感技術學報，2022，35（5）：676-682.

[8]池濤，嚴浩偉，陳明.無線傳感器網(wǎng)絡LEACH算法的研究與改進[J].小型微型計算機系統(tǒng)，2018，39（10）：2222-2225.

[9]劉三陽，鄭亞林，白藝光.基于能耗區(qū)域感知的無線傳感器網(wǎng)絡路由算法[J].控制與決策，2019，34（7）：1425-1432.

[10] DIJKSTRA E W. A note on two problems in connection with graphs [J]. Numerische mathematics， 1959， 1（1）： 269-271.

[11]何選森，何帆，徐麗，等. k-means算法最優(yōu)聚類數(shù)量的確定[J].電子科技大學學報，2022，51（6）：904-912.

[12]馮勇，張學理，王嶸冰，等.融入密度和距離的k-means初始簇中心優(yōu)選方法研究[J].小型微型計算機系統(tǒng)，2018，39（8）：1805-1808.

作者簡介：袁 曄（1987—），男，碩士，工程師，主要研究方向為無線傳感網(wǎng)絡、無線電監(jiān)測與頻譜管理技術。

肖 劍（1975—），男，博士，副教授，主要研究方向為嵌入式系統(tǒng)與物聯(lián)網(wǎng)技術、無線傳感器網(wǎng)絡建模與優(yōu)化。

何志成（1995—），男，碩士，主要從事嵌入式系統(tǒng)及低功耗無線傳感器網(wǎng)絡研究。

張 贊（1987—），男，博士，講師，主要研究方向為機器學習、光電傳感技術。

程鴻亮（1977—），男，碩士，講師，主要研究方向為機器人與物聯(lián)網(wǎng)技術、FPGA加速與優(yōu)化技術。

收稿日期：2023-12-14 修回日期：2024-02-21

基金項目：寧夏回族自治區(qū)重點研發(fā)計劃項目（2022BEG03072）；陜西省秦創(chuàng)原“科學家+工程師”隊伍建設項目（2024QCY-KXJ-161）