孫 麗 孫順遠(yuǎn)，2

（1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 無錫 214122）（2.江南大學(xué)輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗室 無錫 214122）

1 引言

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

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

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

2 LEACH路由協(xié)議

LEACH 協(xié)議是一種以循環(huán)方式隨機(jī)選擇CH，執(zhí)行簇的重構(gòu)過程的無線傳感器網(wǎng)絡(luò)分層路由協(xié)議，其中節(jié)點(diǎn)細(xì)節(jié)由CH處理。CH收集簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)將其壓縮并轉(zhuǎn)發(fā)到基站（sink）。為了降低能耗，增加網(wǎng)絡(luò)壽命，LEACH 使用了包含許多迭代的分層方法。每次迭代都包含LEACH 協(xié)議的簇建立和穩(wěn)定數(shù)據(jù)傳輸?shù)膬蓚€階段。在簇的建立階段，根據(jù)網(wǎng)絡(luò)中所需CH的總數(shù)和目前為止每個節(jié)點(diǎn)被當(dāng)選為CH 的次數(shù)來選擇CH 節(jié)點(diǎn)，節(jié)點(diǎn)被選為CH 的次數(shù)越多再被選為CH的概率越小。節(jié)點(diǎn)隨機(jī)選擇0～1 的數(shù)，如果所選隨機(jī)數(shù)小于閾值T(n)，則該節(jié)點(diǎn)成為本輪的CH。閾值計算公式如下：

其中：p 為簇頭占所有節(jié)點(diǎn)的百分比；G 為包含過去1 p 輪中未被選為簇頭的節(jié)點(diǎn)的集合；r 為當(dāng)前輪數(shù)。

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

3 LEACH協(xié)議改進(jìn)算法

3.1 最優(yōu)簇頭選擇

假設(shè)簇內(nèi)傳輸階段很長，所有數(shù)據(jù)節(jié)點(diǎn)都可以將數(shù)據(jù)發(fā)送給它們的CH，并且簇間傳輸足夠長，所有CH都可以將它們的數(shù)據(jù)發(fā)送給基站。在將數(shù)據(jù)轉(zhuǎn)發(fā)到BS 之前，CH 需要進(jìn)行數(shù)據(jù)聚合和壓縮。根據(jù)空間密度函數(shù)，求得傳感器節(jié)點(diǎn)概率最優(yōu)的被選為CH。

節(jié)點(diǎn)發(fā)送M 比特數(shù)據(jù)，距離為l 時的能量消耗為

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

節(jié)點(diǎn)接收M 比特數(shù)據(jù)時的能量消耗：

每一輪中CH的能量消耗為

其中，N 為網(wǎng)絡(luò)的隨機(jī)分布的節(jié)點(diǎn)數(shù)；K 為網(wǎng)絡(luò)的簇頭數(shù)；EDA為融合每比特數(shù)據(jù)時的能量。

普通節(jié)點(diǎn)的能量消耗為

一個簇中所有節(jié)點(diǎn)的能量消耗為

假設(shè)在面積為A2的網(wǎng)絡(luò)區(qū)域中隨機(jī)分布N個傳感器節(jié)點(diǎn)，簇頭節(jié)點(diǎn)位于每個簇的中心，則節(jié)點(diǎn)密度系數(shù)為，考慮節(jié)點(diǎn)的非均勻分布：

整個網(wǎng)絡(luò)的能量消耗為

根據(jù)上式可知，網(wǎng)絡(luò)總能耗是關(guān)于簇頭數(shù)K的函數(shù)，根據(jù)函數(shù)求極限可得：

則，一個普通節(jié)點(diǎn)成為簇頭的最優(yōu)概率為

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

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

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

1）從網(wǎng)絡(luò)中N 個節(jié)點(diǎn)的集合{ x1，x2，…，xN}中隨機(jī)取K(K ≤N) 個節(jié)點(diǎn)，作為K 個初始簇C={C1，C2，…，CK}的各自的初始聚類中心；

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

其中，μj表示聚類對象的中心坐標(biāo)值。

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

4）將N個節(jié)點(diǎn)按照新的中心重新聚類；

5）循環(huán)2）到4）直到每個聚類不再發(fā)生變化，得到K 個簇。

3.3 算法描述

//網(wǎng)絡(luò)初始化

//簇建立過程

Kopt=Cal culate() //計算最優(yōu)簇頭數(shù)

Unequal clustering

D=Calculate（）//計算節(jié)點(diǎn)到聚類中心的距離

t=find（）//節(jié)點(diǎn)屬于第t類

//循環(huán)迭代將所有節(jié)點(diǎn)分成K個簇中

Election of Cluster-heads

n=find（）//根據(jù)節(jié)點(diǎn)與聚類中心的距離，找出距離聚類中心最近的節(jié)點(diǎn)作為CH，n為CH的id

Broadcast（）//簇頭廣播消息給簇內(nèi)成員

Receive_msg（）//節(jié)點(diǎn)接收簇頭發(fā)送的消息

//數(shù)據(jù)傳輸過程

SendDatatoCH（） //簇內(nèi)節(jié)點(diǎn)發(fā)送數(shù)據(jù)到CH

If（id==id_head）

ReNodeData（） //接收簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)

SendDatatoBS（）

End

4 仿真結(jié)果及分析

本文采用Matlab 進(jìn)行仿真實(shí)驗。為驗證本文算法的優(yōu)越性，對傳統(tǒng)LEACH［14］協(xié)議、SEP［15］以及本文新的算法進(jìn)行仿真，并對實(shí)驗結(jié)果從網(wǎng)絡(luò)剩余節(jié)點(diǎn)數(shù)，剩余能量以及網(wǎng)絡(luò)吞吐量三個方面進(jìn)行性能對比分析。將100個節(jié)點(diǎn)隨機(jī)分布在100 100的區(qū)域中，表1為仿真參數(shù)。

表1 仿真參數(shù)

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

圖1 簇中節(jié)點(diǎn)分布

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

圖2 剩余節(jié)點(diǎn)數(shù)

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

圖3 剩余能量

5 結(jié)語

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