異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)的分簇算法

摘 ?要：針對(duì)LEACH算法缺乏對(duì)網(wǎng)絡(luò)中能量異構(gòu)性的考慮問(wèn)題，為延長(zhǎng)網(wǎng)絡(luò)穩(wěn)定周期，均衡節(jié)點(diǎn)能量消耗，提出一種改進(jìn)的分簇算法。算法充分利用高級(jí)節(jié)點(diǎn)的能量?jī)?yōu)勢(shì)，在簇頭選舉階段，優(yōu)先選舉高級(jí)節(jié)點(diǎn)當(dāng)選簇頭，改善異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中的簇頭選舉機(jī)制。仿真結(jié)果表明，改進(jìn)后的算法均衡了網(wǎng)絡(luò)能量消耗，延長(zhǎng)了網(wǎng)絡(luò)的穩(wěn)定周期和一半節(jié)點(diǎn)死亡輪數(shù)。

關(guān)鍵詞：異構(gòu);無(wú)線傳感器網(wǎng)絡(luò);分簇;算法

中圖分類號(hào)：TN929.5;TP212.9 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）15-0149-04

Abstract：LEACH lacks the consideration of energy heterogeneity in the network. In order to prolong the network stability period and balance the energy consumption of nodes，an improved clustering algorithm was proposed. The algorithm makes full use of the energy advantages of advanced nodes. In the cluster head election stage，it elects advanced nodes to be cluster head preferentially，which improves cluster head election mechanism in heterogeneous wireless sensor networks. The simulation results show that the improved algorithm balances energy consumption of network，prolongs stability period of network and also the death rounds of half nodes.

Keywords：heterogeneous;wireless sensor networks;cluster;algorithm

0 ?引 ?言

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）是一門綜合性的交叉學(xué)科，是物聯(lián)網(wǎng)的重要組成部分[1]。無(wú)線傳感器網(wǎng)絡(luò)由大量的傳感器節(jié)點(diǎn)組成。根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)是否相同，分為同構(gòu)無(wú)線傳感器網(wǎng)絡(luò)和異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)[2]。無(wú)線傳感器網(wǎng)絡(luò)的異構(gòu)性分為計(jì)算能力異構(gòu)性、鏈路異構(gòu)性、網(wǎng)絡(luò)協(xié)議異構(gòu)性、節(jié)點(diǎn)能量異構(gòu)性[3]。當(dāng)網(wǎng)絡(luò)工作一段時(shí)間或部署新的節(jié)點(diǎn)后，各節(jié)點(diǎn)的能量不盡相同，因此，在大多數(shù)情況下，無(wú)線傳感器網(wǎng)絡(luò)普遍存在節(jié)點(diǎn)能量異構(gòu)性。

在環(huán)境惡劣或危險(xiǎn)的監(jiān)測(cè)區(qū)域，基本是無(wú)人值守的，無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)一旦部署就無(wú)法補(bǔ)充能量或替換[4]。節(jié)點(diǎn)能量的受限性，使得如何更好地利用節(jié)點(diǎn)能量成為WSNs的首要設(shè)計(jì)目標(biāo)。分簇路由算法能比平面路由算法更有效地利用能量，節(jié)省網(wǎng)絡(luò)能耗[5]。

現(xiàn)有的經(jīng)典分簇算法存在簇頭能耗過(guò)高、選舉機(jī)制不合理等問(wèn)題，特別當(dāng)網(wǎng)絡(luò)中能量異構(gòu)性強(qiáng)時(shí)，沒(méi)有充分利用高級(jí)節(jié)點(diǎn)能量?jī)?yōu)勢(shì)，使得網(wǎng)絡(luò)出現(xiàn)能耗不均衡、穩(wěn)定周期短等不良特性。針對(duì)以上問(wèn)題，基于本校“無(wú)線傳感器網(wǎng)絡(luò)的節(jié)能分簇算法研究”項(xiàng)目，作者在LEACH（Low-Energy Adaptive Clustering Hierarchy）[6]算法基礎(chǔ)上進(jìn)行改進(jìn)，提出一種適用于異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)的分簇算法。在前面輪數(shù)中，網(wǎng)絡(luò)中能量異構(gòu)性較強(qiáng)時(shí)，選擇高級(jí)節(jié)點(diǎn)當(dāng)選簇頭;當(dāng)能量異構(gòu)性表現(xiàn)得不明顯時(shí)，提高剩余能量高的節(jié)點(diǎn)當(dāng)選簇頭的幾率，優(yōu)化簇頭選舉機(jī)制，延長(zhǎng)網(wǎng)絡(luò)穩(wěn)定周期。

1 ?相關(guān)研究

1.1 ?LEACH算法

LEACH算法是一個(gè)經(jīng)典的分布式分簇路由算法。在LEACH算法中，工作周期按輪進(jìn)行，每輪分為簇建立階段和數(shù)據(jù)傳輸階段[6]。在簇建立階段，每個(gè)節(jié)點(diǎn)生成一個(gè)隨機(jī)數(shù)，與設(shè)定的閾值作比較，決定自己是否成為簇頭。在此階段，整個(gè)網(wǎng)絡(luò)劃分為若干個(gè)分簇，每個(gè)分簇包含一個(gè)簇頭節(jié)點(diǎn)和若干個(gè)簇內(nèi)成員節(jié)點(diǎn)。簇內(nèi)成員節(jié)點(diǎn)負(fù)責(zé)監(jiān)測(cè)區(qū)域內(nèi)的傳感信息，發(fā)送至所在分簇的簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)融合各簇內(nèi)成員節(jié)點(diǎn)的信息，發(fā)送至匯聚節(jié)點(diǎn)。簇內(nèi)成員節(jié)點(diǎn)不直接與匯聚節(jié)點(diǎn)通信，而每輪中，簇頭節(jié)點(diǎn)都與匯聚節(jié)點(diǎn)直接通信，因此簇頭節(jié)點(diǎn)耗能較多。為了均衡簇頭的能耗，LEACH算法采用隨機(jī)選舉簇頭的方式，讓所有節(jié)點(diǎn)以輪流的方式當(dāng)選耗能較多的簇頭節(jié)點(diǎn)。當(dāng)序號(hào)n節(jié)點(diǎn)生成的隨機(jī)數(shù)小于式（1）的閾值T（n）時(shí)，如果此節(jié)點(diǎn)在前面1/p輪中沒(méi)有當(dāng)選過(guò)簇頭節(jié)點(diǎn)，則在此輪中當(dāng)選為簇頭節(jié)點(diǎn)。

簇頭節(jié)點(diǎn)選舉后，其余節(jié)點(diǎn)加入到最近的分簇中，簇頭節(jié)點(diǎn)向其簇內(nèi)節(jié)點(diǎn)發(fā)送TDMA調(diào)度表，簇內(nèi)各節(jié)點(diǎn)根據(jù)TDMA調(diào)度表，向簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)。

1.2 ?異構(gòu)分簇算法

針對(duì)LEACH算法假定節(jié)點(diǎn)初始能量相同，適用于同構(gòu)無(wú)線傳感器網(wǎng)絡(luò)，國(guó)內(nèi)外學(xué)者考慮節(jié)點(diǎn)能量異構(gòu)性，提出了各種改進(jìn)策略。文獻(xiàn)[5]提出一種基于能量分布的非均勻分簇算法，簇頭的選舉中考慮節(jié)點(diǎn)剩余能量分布狀況，采用非均勻的簇半徑，形成大小非均勻的簇。文獻(xiàn)[7]中考慮節(jié)點(diǎn)采集數(shù)據(jù)周期差異、初始能量的異構(gòu)性和分布密度，結(jié)合模糊邏輯原理，采用競(jìng)爭(zhēng)方式來(lái)選舉最優(yōu)簇頭集合，成員節(jié)點(diǎn)采用類勾股定理的方法來(lái)選擇加入分簇。文獻(xiàn)[8]采用一種異構(gòu)感知的分布式算法，針對(duì)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中不同能量級(jí)別的節(jié)點(diǎn)，根據(jù)能量來(lái)設(shè)置不同的簇頭當(dāng)選閾值，增大高級(jí)節(jié)點(diǎn)當(dāng)選簇頭的幾率。文獻(xiàn)[9]提出一種基于能量異構(gòu)的多鏈路算法，根據(jù)高級(jí)節(jié)點(diǎn)能量和全網(wǎng)平均能量來(lái)確定簇頭的閾值，采用層間多鏈路多跳傳輸和簇內(nèi)單跳傳輸?shù)姆绞?。文獻(xiàn)[10]提出一種多級(jí)異構(gòu)的能量?jī)?yōu)化分簇算法，簇頭的閾值函數(shù)中考慮節(jié)點(diǎn)位置和剩余能量，提高離匯聚節(jié)點(diǎn)近且剩余能量高的節(jié)點(diǎn)當(dāng)選簇頭幾率。

為了均衡網(wǎng)絡(luò)能量消耗，針對(duì)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中不同能量的節(jié)點(diǎn)，設(shè)置不同的當(dāng)選簇頭幾率，才能有效利用網(wǎng)絡(luò)中節(jié)點(diǎn)能量異構(gòu)性，提高網(wǎng)絡(luò)性能。

2 ?改進(jìn)分簇算法

2.1 ?網(wǎng)絡(luò)模型

根據(jù)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)的特征，提出以下假設(shè)：

（1）網(wǎng)絡(luò)是靜態(tài)或近似靜態(tài)的，節(jié)點(diǎn)隨機(jī)部署后，位置不再變化。

（2）只有一個(gè)匯聚節(jié)點(diǎn)，位于網(wǎng)絡(luò)上邊界的中點(diǎn)處，能量充足，不受限制。

（3）節(jié)點(diǎn)可與匯聚節(jié)點(diǎn)通信，具有唯一的ID號(hào)，能感知自身的能量水平和位置信息。

（4）網(wǎng)絡(luò)中有兩種不同初始能量水平的節(jié)點(diǎn)，能量高的為高級(jí)節(jié)點(diǎn)，能量低的為普通節(jié)點(diǎn)，節(jié)點(diǎn)能量不可補(bǔ)充。

（5）無(wú)線信道具有對(duì)稱性。

（6）所有節(jié)點(diǎn)的發(fā)射功率可控制。

2.2 ?能量消耗模型

本文采用無(wú)線電能量消耗模型，節(jié)點(diǎn)發(fā)送數(shù)據(jù)的能耗ETX與通信距離d、數(shù)據(jù)包大小L有關(guān)，如式（2）所示：

2.3 ?簇頭選舉與分簇

在簇頭選舉階段，考慮普通節(jié)點(diǎn)和高級(jí)節(jié)點(diǎn)初始能量不一樣，高級(jí)節(jié)點(diǎn)比普通節(jié)點(diǎn)高出能量倍數(shù)為α，為了充分利用網(wǎng)絡(luò)中高級(jí)節(jié)點(diǎn)的能量?jī)?yōu)勢(shì)，算法優(yōu)先選舉高級(jí)節(jié)點(diǎn)為簇頭節(jié)點(diǎn)。

在前面輪數(shù)中，當(dāng)輪數(shù)小于或等于輪數(shù)閾值r0時(shí)，高級(jí)節(jié)點(diǎn)比普通節(jié)點(diǎn)高出的能量較多，即網(wǎng)絡(luò)中節(jié)點(diǎn)的能量異構(gòu)性較強(qiáng)，選擇高級(jí)節(jié)點(diǎn)為簇頭節(jié)點(diǎn)，承擔(dān)耗能較多通信任務(wù);普通節(jié)點(diǎn)不當(dāng)選簇頭節(jié)點(diǎn)。

由于高級(jí)節(jié)點(diǎn)在前面輪數(shù)中當(dāng)選了簇頭，能量消耗比普通節(jié)點(diǎn)多。隨著輪數(shù)增大，網(wǎng)絡(luò)工作一段時(shí)間后，當(dāng)輪數(shù)大于輪數(shù)閾值r0時(shí)，此時(shí)高級(jí)節(jié)點(diǎn)與普通節(jié)點(diǎn)的剩余能量差異縮小，即網(wǎng)絡(luò)中節(jié)點(diǎn)的能量異構(gòu)性減弱時(shí)，對(duì)兩種節(jié)點(diǎn)設(shè)置不同的當(dāng)選簇頭幾率。普通節(jié)點(diǎn)當(dāng)選簇頭幾率pnrm為式（4），高級(jí)節(jié)點(diǎn)當(dāng)選簇頭幾率padv為式（5）：

2.4 ?算法流程圖

改進(jìn)后算法流程圖如圖1所示。

3 ?仿真結(jié)果分析

3.1 ?仿真環(huán)境

為了驗(yàn)證算法的可用性和可靠性，本文采用MATLAB R2014a軟件進(jìn)行仿真分析。在M×M m2的正方形區(qū)域內(nèi)，隨機(jī)部署N個(gè)節(jié)點(diǎn)，其中，高級(jí)節(jié)點(diǎn)的比例為m，其能量為E0（1+α），其余為普通節(jié)點(diǎn)，其能量為E0，匯聚節(jié)點(diǎn)位于正方形區(qū)域上邊界中點(diǎn)處，當(dāng)M=100 m時(shí)，匯聚節(jié)點(diǎn)坐標(biāo)為（50，100）。當(dāng)M=100 m時(shí)，各節(jié)點(diǎn)分布如圖2所示，其中，▲為匯聚節(jié)點(diǎn)，□為高級(jí)節(jié)點(diǎn)，○為普通節(jié)點(diǎn)。

仿真實(shí)驗(yàn)中采用的網(wǎng)絡(luò)場(chǎng)景參數(shù)設(shè)置如表1所示。

3.2 ?仿真結(jié)果

改進(jìn)后算法和LEACH算法的網(wǎng)絡(luò)生存時(shí)間對(duì)比如圖3所示。從網(wǎng)絡(luò)開始運(yùn)行到第一個(gè)節(jié)點(diǎn)死亡的時(shí)間間隔，稱為網(wǎng)絡(luò)穩(wěn)定周期，在此時(shí)間內(nèi)，所有節(jié)點(diǎn)存活，網(wǎng)絡(luò)能穩(wěn)定持續(xù)地監(jiān)測(cè)環(huán)境信息和采集數(shù)據(jù)，網(wǎng)絡(luò)處于穩(wěn)定的工作階段。從圖中可知，LEACH算法的穩(wěn)定周期624輪，改進(jìn)后算法的穩(wěn)定周期為772輪，對(duì)比LEACH算法，延長(zhǎng)了23.72%。從網(wǎng)絡(luò)開始運(yùn)行到一半節(jié)點(diǎn)死亡的時(shí)間間隔內(nèi)，出現(xiàn)部分節(jié)點(diǎn)死亡，但比例不高，網(wǎng)絡(luò)仍能工作。圖中LEACH算法一半節(jié)點(diǎn)死亡的輪數(shù)為732輪，改進(jìn)后算法一半節(jié)點(diǎn)死亡的輪數(shù)為874輪，對(duì)比LEACH算法，延長(zhǎng)了19.40%。改進(jìn)后算法的穩(wěn)定周期和一半節(jié)點(diǎn)死亡的輪數(shù)均比LEACH算法更優(yōu)。

改進(jìn)后算法和LEACH算法向匯聚節(jié)點(diǎn)發(fā)送數(shù)據(jù)量對(duì)比如圖4所示。LEACH算法的傳輸量為11 037 L，改進(jìn)后算法的傳輸量為23 704 L，約是LEACH算法的2.15倍。改進(jìn)后的算法優(yōu)先選舉剩余能量較多的高級(jí)節(jié)點(diǎn)當(dāng)選簇頭節(jié)點(diǎn)，在前面輪數(shù)中，網(wǎng)絡(luò)能量異構(gòu)性較強(qiáng)，高級(jí)節(jié)點(diǎn)高出普通節(jié)點(diǎn)的能量較多，選舉的簇頭數(shù)量比LEACH算法較多，因此，改進(jìn)后的算法向匯聚節(jié)點(diǎn)發(fā)送數(shù)據(jù)量較多。而LEACH算法不考慮節(jié)點(diǎn)能量異構(gòu)性，把高級(jí)節(jié)點(diǎn)和普通節(jié)點(diǎn)視作一樣的節(jié)點(diǎn)，具有相同的當(dāng)選簇頭幾率。隨著網(wǎng)絡(luò)工作時(shí)間推移，在輪數(shù)為732輪以后，由于LEACH算法中出現(xiàn)過(guò)半節(jié)點(diǎn)死亡，網(wǎng)絡(luò)剩余節(jié)點(diǎn)數(shù)量越來(lái)越少，LEACH算法向匯聚節(jié)點(diǎn)發(fā)送數(shù)據(jù)量明顯減少。

4 ?結(jié) ?論

本文在異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)環(huán)境下，基于LEACH算法，提出了一種改進(jìn)的分簇算法。該算法考慮高級(jí)節(jié)點(diǎn)和普通節(jié)點(diǎn)的能量不同，通過(guò)優(yōu)先選舉高級(jí)節(jié)點(diǎn)當(dāng)選簇頭，充分利用節(jié)點(diǎn)的能量異構(gòu)性，提高節(jié)點(diǎn)能量利用率。仿真結(jié)果表明，改進(jìn)后的算法均衡了網(wǎng)絡(luò)能量消耗，延長(zhǎng)了網(wǎng)絡(luò)的穩(wěn)定周期和一半節(jié)點(diǎn)死亡輪數(shù)，網(wǎng)絡(luò)性能更佳，算法可適用于能量異構(gòu)網(wǎng)絡(luò)。

參考文獻(xiàn)：

[1] 馬颯颯，張磊，夏明飛，等.無(wú)線傳感器網(wǎng)絡(luò)概論 [M].北京：人民郵電出版社，2015.

[2] 楊柳.基于分簇結(jié)構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能路由協(xié)議研究 [D].重慶：重慶大學(xué)，2016.

[3] 李繼榮.異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題研究 [D].濟(jì)南：山東大學(xué)，2010.

[4] 徐晶晶，張欣慧，許必宵，等.無(wú)線傳感器網(wǎng)絡(luò)分簇算法綜述 [J].計(jì)算機(jī)科學(xué)，2017，44（2）：31-37.

[5] 張春花，劉方愛(ài)，申志遠(yuǎn)，等.一種新的異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)分簇算法 [J].傳感器與微系統(tǒng)，2013，32（6）：143-146.

[6] HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

[7] 徐世武.異構(gòu)無(wú)線傳感網(wǎng)絡(luò)最優(yōu)簇首選擇機(jī)制 [J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2016，25（1）：187-191.

[8] SMARAGDAKIS G，MATTA I，BESTAVROS A. SEP：a stable election protocol for clustered heterogeneous wireless sensor networks [C].In：Second International Workshop on Sensor and Actor Network Protocols and Applications，2004：223-233.

[9] 王衛(wèi)星，黃虹，孫道宗，等.基于能量異構(gòu)的WSN多鏈路算法 [J].華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，43（9）：74-80.

[10] 胡中棟，伍華林.多級(jí)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)能量?jī)?yōu)化分簇算法 [J].江西理工大學(xué)學(xué)報(bào)，2017，38（1）：73-78.

作者簡(jiǎn)介：伍敏君（1986—），女，漢族，廣東中山人，講師，碩士，研究方向：無(wú)線傳感器網(wǎng)絡(luò)技術(shù)、計(jì)算機(jī)應(yīng)用技術(shù)。