王 珊，梁 敏，路芳瑞，趙冬琴

（1.山西財經(jīng)大學(xué)實驗中心，太原 030006；2.山西財經(jīng)大學(xué)信息學(xué)院，太原 030006）

0 引言

無線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSN）廣泛應(yīng)用于軍事安全、空間探測、環(huán)境監(jiān)測、智能家居、醫(yī)療健康、交通管理等眾多領(lǐng)域［1］。但是無線傳感器節(jié)點一般難以蓄電，有限的能量限制了WSN的生命周期，因此，如何設(shè)計節(jié)能算法以降低傳感器節(jié)點能量消耗成為研究的熱點問題。分簇路由算法［2］相比平面路由協(xié)議，能有效降低能量消耗，因此，對WSN 分簇路由算法的研究具有很好的研究意義和實用價值。

國內(nèi)外眾多專家學(xué)者對WSN 分簇路由算法展開了深入研究。HEINZELMAN 等提出了LEACH 算法，該算法執(zhí)行過程是循環(huán)的“輪”，在每一輪中隨機初始化簇頭，但是簇頭選舉未考慮節(jié)點位置信息［3］。MANJESHWAR 等提出了TEEN 算法，該算法基于閾值，當(dāng)有特定事件發(fā)生時，才發(fā)送數(shù)據(jù)給基站，從而降低能量消耗［4］。LI 等提出了EEUC 算法，簇大小與基站距離成比例，但簇頭選舉采取競爭機制增加了能耗［5］。SERT 等提出了MOFCA 算法，該算法基于模糊邏輯，改進了簇頭選舉機制及競爭半徑［6］。NEAMATOLLAHI 等提出了一種基于遺傳算法的分簇算法，適應(yīng)度函數(shù)考慮節(jié)點與簇頭節(jié)點的總距離以均衡簇頭負(fù)載［7］。任昌鴻等提出了一種改進粒子群算法，結(jié)合分布式空間技術(shù)實現(xiàn)均衡分簇［8］。方旺盛等提出了一種改進K-means 分簇算法，以改進分簇效果［9］。可以看出，以上算法有的側(cè)重優(yōu)化分簇效果，有的側(cè)重優(yōu)化簇頭選舉策略，但兩者皆考慮的很少。

因此，本文提出了一種基于AHP 的改進K 均值分簇算法（K-means clustering algorithm based on AHP，AHPK），主要思想是改進K-means 聚類，改善分簇效果，同時使用AHP 模型計算簇頭選舉影響因素權(quán)重，改善簇頭質(zhì)量，提升網(wǎng)絡(luò)生命周期。

1 相關(guān)模型

1.1 網(wǎng)絡(luò)模型

本文對WSN 的網(wǎng)絡(luò)模型作如下假設(shè)：

1）所有傳感器節(jié)點符合隨機分布，地理位置固定不變，有唯一的標(biāo)識號，節(jié)點集表示為V={v1，v2，…，vn}；2）基站能量無限且不可移動，能獲取每個節(jié)點的位置信息vi（xi，yi）；3）所有傳感器節(jié)點同構(gòu)，能量有限，具有數(shù)據(jù)融合功能，可相互通信，也可與基站直接通信；4）節(jié)點之間的距離可通過接受信號強度指示（received signal strength indication，RSSI）計算得到［10］。

1.2 能耗模型

采用的無線電通信能量模型與文獻［11］相同。

1）節(jié)點發(fā)送數(shù)據(jù)能耗：節(jié)點發(fā)送l bit 數(shù)據(jù)到距離d 位置所消耗的能量為：

式中，Eelec指發(fā)送單位比特數(shù)據(jù)所消耗的能量；εfs和εmp分別指自由空間和多徑衰減信道模型功率放大器能量參數(shù)；d0指閾值距離，其計算公式為：

2）節(jié)點接收數(shù)據(jù)能耗：節(jié)點接收l bit 數(shù)據(jù)所消耗的能量為：

3）節(jié)點融合數(shù)據(jù)能耗：節(jié)點融合l bit 數(shù)據(jù)所消耗的能量為：

2 AHPK 分簇路由算法

2.1 分簇階段

通過改進K-means 聚類［12］對節(jié)點進行分簇，簇一旦形成不再改變。

2.1.1 確定K 值

本算法K 值依據(jù)文獻［13］確定，其計算公式為：

其中，N 指網(wǎng)絡(luò)內(nèi)節(jié)點總數(shù)量；L 指區(qū)域邊長；dtoBS指基站至所有節(jié)點的平均距離?？梢钥闯?，網(wǎng)絡(luò)中節(jié)點個數(shù)越多，區(qū)域邊長越長，基站距節(jié)點的平均距離越短，簇的個數(shù)就越多。

2.1.2 優(yōu)化初始中心點選取

K-means 聚類算法初始中心點是隨機選取的，若初始中心點位置比較集中，聚類結(jié)果就會比較聚集，導(dǎo)致分簇結(jié)果不理想。因此，本算法對初始中心點的選取進行改進，通過計算網(wǎng)絡(luò)中節(jié)點間的最大距離選取K 個中心點，以優(yōu)化分簇效果。具體選取過程如下：

1）計算網(wǎng)絡(luò)中距離最大的兩個節(jié)點，將這兩個節(jié)點加入初始聚類中心點集C 中，此時C 中節(jié)點數(shù)目|C|=2；2）若|C|＜K，跳轉(zhuǎn)至步驟3）；若|C|=K，選取完畢，跳轉(zhuǎn)至步驟4）；3）計算C 以外其余節(jié)點到C內(nèi)每個節(jié)點的距離之和，選出距離和最大的一個節(jié)點加入C，|C|=|C|+1，轉(zhuǎn)至步驟2）；4）K-means 聚類。

2.2 簇頭選舉階段

AHP 模型是將復(fù)雜的問題層次化和量化，對多個影響因素的重要程度進行兩兩比較建立判斷矩陣，計算其最大特征值及對應(yīng)特征向量，得出不同因素重要性程度權(quán)重，為決策者提供依據(jù)［14］。WSN 中簇頭選舉受節(jié)點能量、位置、鄰居節(jié)點密度等多種因素影響，每種因素的權(quán)重難以直接確定，因此，引入AHP 模型計算各影響因素權(quán)重不失為一個很好的方法。

2.2.1 構(gòu)建層次結(jié)構(gòu)模型

根據(jù)影響簇頭選舉的因素，本算法建立簇頭選舉AHP 模型如下頁圖1 所示。

圖1 AHPK 簇頭選舉層次化模型Fig.1 AHPK cluster head election hierarchical model

第1 層為目標(biāo)層，計算簇內(nèi)所有活動節(jié)點的綜合權(quán)值，選取本輪最優(yōu)簇頭；

第2 層為準(zhǔn)則層，由影響簇頭選舉的各因素組成，本文算法選取3 個準(zhǔn)則：節(jié)點剩余能量度、節(jié)點質(zhì)心度、節(jié)點密度。

1）節(jié)點剩余能量度：網(wǎng)絡(luò)運行過程中，簇頭節(jié)點能量消耗最大，應(yīng)考慮剩余能量較多的節(jié)點。節(jié)點剩余能量度E（i）定義如下：

式中，Eres（i）指節(jié)點i 的剩余能量；Eave指當(dāng)前簇內(nèi)所有節(jié)點的平均剩余能量。

2）節(jié)點質(zhì)心度：簇頭節(jié)點應(yīng)選取距離簇內(nèi)質(zhì)心點位置較近的節(jié)點，使得簇內(nèi)大多數(shù)節(jié)點至簇頭節(jié)點的距離較小，以節(jié)省傳輸能耗。節(jié)點質(zhì)心度C（i）定義如下：

式中，di指節(jié)點i 至簇內(nèi)質(zhì)心點的距離；davg指簇內(nèi)所有節(jié)點至質(zhì)心點的平均距離。

3）節(jié)點密度：節(jié)點的鄰居數(shù)量越多，表明該節(jié)點位于簇內(nèi)節(jié)點比較密集的區(qū)域中，這樣可以避免噪聲節(jié)點的干擾。節(jié)點密度U（i）定義如下：

式中，ni指節(jié)點i 的鄰居節(jié)點數(shù)量；n'為當(dāng)前簇內(nèi)活動節(jié)點數(shù)。

第3 層為方案層，由簇內(nèi)所有活動節(jié)點組成。

2.2.2 構(gòu)造比較判斷矩陣

AHP 模型是將兩兩準(zhǔn)則的重要程度比建立判斷矩陣，對3 個準(zhǔn)則構(gòu)建比較判斷矩陣A 如下：

根據(jù)文獻［15］表2.1 對A 進行賦值。計算A 的最大特征根max及其對應(yīng)特征向量W=［w1w2w3］T，隨后根據(jù)文獻［14］中一致性檢驗方法對A 是否存在邏輯錯誤進行檢驗。一致性檢驗通過后，對W 進行歸一化得到W'=［w1' w2' w3'］T即為各準(zhǔn)則權(quán)重，此時節(jié)點i 綜合權(quán)值函數(shù)如下：

可見節(jié)點的綜合權(quán)值越大，代表該節(jié)點擁有較高的剩余能量，距離質(zhì)心節(jié)點越近、節(jié)點的密度越大。因此，節(jié)點綜合權(quán)值最大者當(dāng)選為本輪簇頭。

2.3 AHPK 算法描述

圖2 為本文AHPK 算法的流程圖，首先計算出初始中心點的位置，使用K-means 聚類將網(wǎng)絡(luò)中節(jié)點劃分為K 個簇；然后利用AHP 模型計算影響簇頭選舉的各因素權(quán)重，此后開始每輪工作，每輪工作涉及簇頭選舉和數(shù)據(jù)傳輸兩步，簇頭選舉使用AHP 模型確定各準(zhǔn)則權(quán)重，利用式（10）計算簇內(nèi)活動節(jié)點綜合權(quán)值，最大者選為本輪簇頭節(jié)點，隨后普通節(jié)點將采集到的數(shù)據(jù)以單跳方式發(fā)送至簇頭節(jié)點，簇頭節(jié)點進行數(shù)據(jù)融合后，傳輸數(shù)據(jù)至基站，一輪工作結(jié)束。若網(wǎng)絡(luò)中還有存活節(jié)點，則開始下一輪工作。

3 仿真與分析

使用matlab2014a 進行仿真實驗。為驗證AHPK算法的性能，從分簇結(jié)構(gòu)、生存節(jié)點數(shù)量、網(wǎng)絡(luò)能耗3 個方面與LEACH 算法、K-means 算法進行對比。

1）仿真參數(shù)設(shè)置如表1 所示。

表1 仿真參數(shù)設(shè)置Table 1 Simulation parameter settings

2）根據(jù)文獻［15］賦值規(guī)則，采用經(jīng)驗法對判斷矩陣A 賦值如下：

3.1 分簇結(jié)構(gòu)分析

為更好地驗證本文AHPK 算法的分簇性能，將其與LEACH 算法分簇結(jié)果和K-means 算法分簇結(jié)果進行對比，實驗結(jié)果如圖3 所示。

圖3 分簇結(jié)構(gòu)Fig.3 Clustering structure

其中，圖3（a）～（d）分別為隨機選取的4 組LEACH算法在不同輪次中的分簇結(jié)構(gòu)，可以看出LEACH算法分簇隨機性強，數(shù)量不固定，這是因為LEACH協(xié)議依賴概率模型成簇，因此，簇大小差異較大，分簇效果較差，從而容易造成網(wǎng)絡(luò)能耗不均衡。圖3（e）為K-means 算法分簇結(jié)構(gòu)，5 個簇節(jié)點個數(shù)分別為21、14、28、24、13，可以看出簇大小相差較大，且有的簇質(zhì)心位置比較接近，這是由于初始中心點是隨機選取造成的。圖3（f）為本文AHPK 算法分簇結(jié)構(gòu)，5 個簇內(nèi)節(jié)點個數(shù)分別為17、22、20、17、24，簇大小相差不大，簇質(zhì)心點位置均勻分布在整個網(wǎng)絡(luò)中，說明通過改進K-means 算法固定初始中心點位置能有效改善分簇效果，從而形成較好的分簇結(jié)構(gòu)。

3.2 生存節(jié)點分析

網(wǎng)絡(luò)中的生存節(jié)點個數(shù)直觀地反映網(wǎng)絡(luò)生命周期的長短，因此，將本文AHPK 算法與LEACH 算法、K-means 算法從生存節(jié)點數(shù)量進行比較，實驗結(jié)果如圖4 所示。圖4 中，橫坐標(biāo)代表運行輪數(shù)，縱坐標(biāo)代表每輪次相應(yīng)的存活節(jié)點個數(shù)，可以看出LEACH 算法、K-means 算法第1 個死亡節(jié)點分別是在500 輪和700 輪左右，而AHPK 算法第1 個死亡節(jié)點在第850 輪左右，第1 個死亡節(jié)點相較于前兩種算法延遲上百輪，效率分別提高了近70%和21%，且AHPK 算法在運行至1 000 輪左右的時候存活節(jié)點數(shù)量高達(dá)70%左右，說明使用層次分析法有效設(shè)置了剩余能量度、質(zhì)心度和密度三者的權(quán)重關(guān)系，從而均衡了網(wǎng)絡(luò)能耗，延長了簇頭節(jié)點生存時間。同時LEACH 算法、K-means 算法節(jié)點全部死亡分別在1 000 輪和1 150 輪左右，而AHPK 算法節(jié)點全部死亡在1 250 輪左右，可以看出，AHPK 算法有效延長了整個網(wǎng)絡(luò)的生命周期。

圖4 生存節(jié)點數(shù)量對比圖Fig.4 Comparison chart of the number of surviving nodes

3.3 網(wǎng)絡(luò)能耗分析

網(wǎng)絡(luò)能耗是衡量算法性能的重要指標(biāo)，本文從每輪能量消耗和網(wǎng)絡(luò)剩余總能量兩方面對3 種算法進行比較，實驗結(jié)果如圖5 和圖6 所示。

圖5 每輪能量消耗對比圖Fig.5 Comparison chart of energy consumption per round

圖6 每輪網(wǎng)絡(luò)剩余能量對比圖Fig.6 Comparison chart of remaining energy of each round of network

圖5 為每輪能量消耗對比圖，橫坐標(biāo)代表運行輪次，縱坐標(biāo)代表每輪所有節(jié)點消耗的總能量，可以看出LEACH 算法和K-means 算法在多個輪次出現(xiàn)能量消耗驟增現(xiàn)象，而AHPK 算法每輪消耗能量較穩(wěn)定，這是由于LEACH 算法和K-means 算法在簇頭選舉時只考慮節(jié)點的剩余能量造成的；而AHPK 算法在簇頭選舉時應(yīng)用層次分析法綜合考慮節(jié)點剩余能量、位置和密度因素，因此，各輪能量消耗相對均衡。圖6 為網(wǎng)絡(luò)剩余總能量對比圖，橫坐標(biāo)代表運行輪次，縱坐標(biāo)代表每輪所有節(jié)點剩余總能量，初始總能量為50 J。如圖6 所示LEACH 算法和K-means 算法在360 輪和450 輪左右消耗了網(wǎng)絡(luò)近一半能量，而AHPK 算法在520 輪左右出現(xiàn)，分別推遲了44.4%和15.6%；同時在算法運行到850 輪時，LEACH 算法剩余總能量不足1.5 J，K-means 算法還剩3.5 J 左右，而AHPK 算法所?？偰芰扛哌_(dá)10 J 左右，綜上可見AHPK 算法通過改進分簇結(jié)構(gòu)，引入層次分析法選舉簇頭能很好的降低網(wǎng)絡(luò)能耗，有效延長網(wǎng)絡(luò)生命周期。

4 結(jié)論

本文提出的AHPK 算法通過計算節(jié)點間最大距離改進K-means 初始中心點選取，以改善網(wǎng)絡(luò)成簇效果；之后在每輪運行過程中，引入層次分析法計算節(jié)點權(quán)重，改進簇頭選舉機制，以改善簇頭選取質(zhì)量，降低網(wǎng)絡(luò)能耗。通過仿真實驗對比，本文算法相較于LEACH 算法和K-means 算法，分簇效果更好，簇大小更均勻，每輪能量消耗更穩(wěn)定，網(wǎng)絡(luò)生命周期有較明顯提升。因此，本文算法是一種性能較好的算法。