孫 麗 孫順遠，2

（1.江南大學物聯網工程學院 無錫 214122）（2.江南大學輕工過程先進控制教育部重點實驗室 無錫 214122）

1 引言

隨著無線通信和低功耗嵌入式技術的迅速發展，以低功耗、低成本、分布式和自組織為特點的無線傳感器網絡（WSN）孕育而生，帶來了一場信息技術的變革［1］。現今，WSN已經融入人們的日常生活中，廣泛應用在軍事、環境、監測、家庭、車輛追蹤、交通流量、醫療衛生等諸多領域［2］。WSN在監測區域內分布著大量廉價微型傳感器節點，這些節點以無線通信的方式組成多跳自組織網絡。所有傳感器節點和數據獲取單元采集的信號，通過無線通信的方式傳輸給簇頭，簇頭將收集到的數據進行聚集和壓縮后，最終傳輸給基站［3］。而基站則通過在整個網絡中轉發查詢信息的方式來請求傳感器節點采集數據。當傳感器節點發現與查詢信息匹配的數據時，路由返回響應消息到基站。通過網絡中被選為簇頭節點的移植，可以實現網絡中能量消耗的最小化。但在整個無線通信過程中，網絡也存在著能量消耗過快，儲存和計算能力不足的問題。為解決傳感器節點過早死亡，能量消耗不均衡以及有效延長網絡壽命的問題，提出了許多路由算法，其中低功耗自適應集簇分層型（LEACH）路由協議就是WSN中分簇路由協議的典型代表［4］。

文獻［5］改進的LEACH 通信協議在簇建立階段，采用主副簇頭交替策略，減少簇頭選擇次數，從而減少了每輪進行簇頭選擇時能量的消耗，同時將初始能量和剩余能量以及主副簇頭選擇次數作為參數加入到閾值的計算中。文獻［6］結合文獻［5］在優化閾值計算的基礎上，增加了最優簇半徑的概念，在控制簇頭數量的同時使得簇頭節點的位置分布更加合理，均衡了網絡能量消耗。文獻［7］將節點相對密度加入到閾值的計算中，同時引入全網簇頭選擇和簇內簇頭選擇兩種方式，有效減少了頻繁簇頭選擇而導致的能量消耗問題。在文獻［8］中，針對傳統LEACH 協議不適合大規模網絡的缺點，提出了采用模擬退火算法確定局部集中式的分簇方法。研究發現，LEACH 協議分為簇建立和數據穩定傳輸兩個階段。在對LEACH 協議的不斷改進中，不管是把節點的初始能量、剩余能量和被選為簇頭的次數加入到閾值中，還是引入最優簇半徑、相對密度和模擬退火算法，都有效均衡了能量消耗，延長了整個網絡的生命周期。但是上述研究都是對簇建立階段的進一步改進，傳輸方式仍然是簇頭到基站的直接傳輸。這種傳輸方式在數據傳輸過程中不利于距離基站較遠的簇頭，會使此類簇頭因距離太遠而消耗過多能量，加速節點的死亡，從而縮短網絡壽命。文獻［9］HRPNC 采用分層和競爭機制相結合的方式選取簇頭，使簇頭節點分布更加合理，同時在數據穩定傳輸階段文獻采用簇內節點單跳和簇間簇頭節點多跳的兩種方式進行數據傳輸，進一步減少數據傳輸過程中的能耗。文獻［10］在簇頭選擇過程中將節點剩余能量和位置分布采用加權和的方法加入到閾值的計算中，同時引入融合節點的概念，將簇頭節點的任務重新分配，將數據傳輸的任務分配給融合節點。在數據傳輸過程中，提出AF-DK 算法，為數據傳輸節點找到最優的傳輸路徑。文獻［11］提出一種新的能量均衡多跳路由算法，在確保簇頭數最優的情況下，簇頭選擇時加入節點能量和位置分布，同時引入PEGASIS 協議中節點成鏈思想，將簇頭與基站的直接傳輸方式改成簇頭間的多跳路由傳輸。

LEACH 協議的大部分改進涉及CH 選擇的方式［12］，而不是在CH 選擇階段選出最優的簇頭數。本文對LEACH 協議進行分析，結合K-means算法，提出了一種基于K 均值聚類的非均勻分簇路由算法。該算法在簇頭選擇之前，根據最優簇頭數K，利用K-means算法，將節點分為K 個類（或簇）。同時，在每個簇中根據節點到其他節點的最短距離確定簇頭（有線連接），且簇頭固定不變，簡化了LEACH 協議中的簇建立階段，有效減少了網絡中頻繁進行簇頭選擇和簇建立過程的能量消耗，使得網絡生命周期得以延長。

2 LEACH路由協議

LEACH 協議是一種以循環方式隨機選擇CH，執行簇的重構過程的無線傳感器網絡分層路由協議，其中節點細節由CH處理。CH收集簇內節點的數據將其壓縮并轉發到基站（sink）。為了降低能耗，增加網絡壽命，LEACH 使用了包含許多迭代的分層方法。每次迭代都包含LEACH 協議的簇建立和穩定數據傳輸的兩個階段。在簇的建立階段，根據網絡中所需CH的總數和目前為止每個節點被當選為CH 的次數來選擇CH 節點，節點被選為CH 的次數越多再被選為CH的概率越小。節點隨機選擇0～1 的數，如果所選隨機數小于閾值T(n)，則該節點成為本輪的CH。閾值計算公式如下：

其中：p 為簇頭占所有節點的百分比；G 為包含過去1 p 輪中未被選為簇頭的節點的集合；r 為當前輪數。

在CH 節點選擇完畢后，通過廣播告知整個網絡所選簇頭節點的基本信息，網絡中的其他節點根據接收到的信號強度加入相對應的簇，并通知相應的CH，完成簇的建立過程。基于每個簇中的節點數，CH 采用TDMA 方式為每個節點發送時分配一個時隙。如果在當前輪中已經選擇了節點作為CH，則閾值T(n)被設置為零。因此，在下一1 p 輪中，節點將不再被選為CH。在基于閾值的方案中，節點建立長距離到達CH，有利CH 將在多輪后不利，從而延長主要節點的使用壽命。在穩態階段，簇內節點定期收集傳感器數據，并將其轉發到分配時隙中的CH，CH 將收集到的數據進行聚合，發送給基站。在此過程中給除非節點到了分配的傳輸時間，否則簇內節點處于關閉狀態［13］。

3 LEACH協議改進算法

3.1 最優簇頭選擇

假設簇內傳輸階段很長，所有數據節點都可以將數據發送給它們的CH，并且簇間傳輸足夠長，所有CH都可以將它們的數據發送給基站。在將數據轉發到BS 之前，CH 需要進行數據聚合和壓縮。根據空間密度函數，求得傳感器節點概率最優的被選為CH。

節點發送M 比特數據，距離為l 時的能量消耗為

其中：Eelec表示每比特的能量消耗；εfs和εmp是功率放大器的能量損耗系數；l 為傳輸距離。lc為傳輸距離的門限值。lc的計算公式為

節點接收M 比特數據時的能量消耗：

每一輪中CH的能量消耗為

其中，N 為網絡的隨機分布的節點數；K 為網絡的簇頭數；EDA為融合每比特數據時的能量。

普通節點的能量消耗為

一個簇中所有節點的能量消耗為

假設在面積為A2的網絡區域中隨機分布N個傳感器節點，簇頭節點位于每個簇的中心，則節點密度系數為，考慮節點的非均勻分布：

整個網絡的能量消耗為

根據上式可知，網絡總能耗是關于簇頭數K的函數，根據函數求極限可得：

則，一個普通節點成為簇頭的最優概率為

3.2 基于K-means算法的非均勻成簇方法

LEACH 協議中簇頭采用隨機選擇的方式，CH數目不確定，過多或過少，都會造成CH節點多余的能量消耗。同時，CH節點位置分布不均勻，也會使得網絡中距離基站較遠的CH節點因為能量消耗過快而過早死亡。本文根據最優概率算法，計算網絡中的最優簇頭數K ，然后，基于K 均值聚類算法，將網絡中的節點隨機分布在K 個簇內，在每個簇中選擇靠近類中心的節點作為CH。此時，簇的建立階段完成，在以后的每一輪中都不在變化，從而減少網絡中簇建立過程的能量消耗，有效提高了網絡壽命。

其算法非均勻分簇的步驟如下所示：

1）從網絡中N 個節點的集合{ x1，x2，…，xN}中隨機取K(K ≤N) 個節點，作為K 個初始簇C={C1，C2，…，CK}的各自的初始聚類中心；

2）計算聚類對象的均值（中心對象），根據均值，計算每個對象與這些中心對象的距離；并根據最小距離重新對相應對象進行劃分，即對以下表達式求最小值：

其中，μj表示聚類對象的中心坐標值。

3）根據聚類結果，重新計算每個（有變化）聚類的均值（中心對象），計算方法是取簇中所有元素各自維度的算術平均值；

4）將N個節點按照新的中心重新聚類；

5）循環2）到4）直到每個聚類不再發生變化，得到K 個簇。

3.3 算法描述

//網絡初始化

//簇建立過程

Kopt=Cal culate() //計算最優簇頭數

Unequal clustering

D=Calculate（）//計算節點到聚類中心的距離

t=find（）//節點屬于第t類

//循環迭代將所有節點分成K個簇中

Election of Cluster-heads

n=find（）//根據節點與聚類中心的距離，找出距離聚類中心最近的節點作為CH，n為CH的id

Broadcast（）//簇頭廣播消息給簇內成員

Receive_msg（）//節點接收簇頭發送的消息

//數據傳輸過程

SendDatatoCH（） //簇內節點發送數據到CH

If（id==id_head）

ReNodeData（） //接收簇內節點的數據

SendDatatoBS（）

End

4 仿真結果及分析

本文采用Matlab 進行仿真實驗。為驗證本文算法的優越性，對傳統LEACH［14］協議、SEP［15］以及本文新的算法進行仿真，并對實驗結果從網絡剩余節點數，剩余能量以及網絡吞吐量三個方面進行性能對比分析。將100個節點隨機分布在100 100的區域中，表1為仿真參數。

表1 仿真參數

圖1 表示網絡中簇建立后的節點分布圖。每個普通節點的初始能量為0.5J，根據最優簇頭數，結合K 均值聚類算法將節點分成5個簇，分別用不同顏色表示，每個簇中距離聚類中心最近的節點為CH，CH 采用有線連接，在整個仿真過程中固定不變。

圖1 簇中節點分布

通過對LEACH 協議、SEP 協議以及本文算法的網絡生命周期的分析，研究隨著網絡中仿真輪數的增加，剩余節點的數量變化。在圖2 中，所提出的算法的第一個死亡節點要比另外兩個協議提高約900 輪，而在1400 輪本文算法的死亡節點約為10 個，從圖中清晰地看出本文算法的網絡壽命比現有協議明顯改善。并且在整個網絡的生命周期結束前保證整個網絡基本具有相同的規模，有效地提高了網絡穩定性。

圖2 剩余節點數

圖3 表示網絡中隨著仿真輪數的不斷增加剩余能量的變化曲線。圖中SEP 協議由于存在高級和普通兩種節點，所以能量是高于LEACH 協議的，而本文算法中，由于假定CH節點能量無限，因此只考慮普通節點的剩余能量。仿真發現，LEACH 和SEP 協議的剩余能量相差不是很大，SEP 協議的剩余能量略高于LEACH 協議，而本文算法的剩余能量明顯高于LEACH 和SEP，相應的網絡壽命也大大長于兩者。這主要因為本文算法提前完成簇的建立，并在此后的每一輪中不在更改，有效減少了網絡不斷進行簇頭選擇和簇建立消耗的能量，提高了網絡生命周期。

圖3 剩余能量

5 結語

本文根據K 均值聚類算法，利用最優簇頭數，將隨機分布在網絡中的節點分成幾個簇，并將距離聚類中心最近的節點作為簇頭，此后每一輪簇保持不變，簡化LEACH 協議的簇建立階段，有效減少了網絡不斷進行簇頭選擇和簇建立的能量消耗。仿真結果表明，本文算法比傳統LEACH 協議、SEP 協議優勢更加顯著，使簇頭數目和位置分布更加合理，節點死亡數和傳輸過程中的能量消耗大大減少，有效延長了網絡壽命。