一種基于AHP 的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法*

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

（1.山西財(cái)經(jīng)大學(xué)實(shí)驗(yàn)中心，太原 030006；2.山西財(cái)經(jīng)大學(xué)信息學(xué)院，太原 030006）

0 引言

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

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

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

1 相關(guān)模型

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

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

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

1.2 能耗模型

采用的無(wú)線電通信能量模型與文獻(xiàn)［11］相同。

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

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

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

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

2 AHPK 分簇路由算法

2.1 分簇階段

通過(guò)改進(jìn)K-means 聚類(lèi)［12］對(duì)節(jié)點(diǎn)進(jìn)行分簇，簇一旦形成不再改變。

2.1.1 確定K 值

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

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

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

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

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

2.2 簇頭選舉階段

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 AHPK 算法描述

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

3 仿真與分析

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

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

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

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

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

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

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

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

3.2 生存節(jié)點(diǎn)分析

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

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

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

網(wǎng)絡(luò)能耗是衡量算法性能的重要指標(biāo)，本文從每輪能量消耗和網(wǎng)絡(luò)剩余總能量?jī)煞矫鎸?duì)3 種算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖5 和圖6 所示。

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

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

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

4 結(jié)論

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