竇佩佩，曾玉琴，盧 毅，馬洪亮，徐夢(mèng)穎，周 杰

(石河子大學(xué) 信息科學(xué)與技術(shù)學(xué)院，新疆維吾爾自治區(qū) 石河子 832003)

無(wú)線傳感器網(wǎng)絡(luò)通常由大量廉價(jià)的微型傳感器節(jié)點(diǎn)構(gòu)成。無(wú)線傳感器網(wǎng)絡(luò)融合了無(wú)線通信技術(shù)、傳感器技術(shù)、嵌入式計(jì)算技術(shù)等關(guān)鍵技術(shù)，網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)能夠?qū)ν獠凯h(huán)境中的對(duì)象進(jìn)行監(jiān)測(cè)并采集相關(guān)數(shù)據(jù)[1-2]。隨著相關(guān)技術(shù)的飛速發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)在軍事、醫(yī)學(xué)、農(nóng)業(yè)、工業(yè)、環(huán)境監(jiān)測(cè)等領(lǐng)域的應(yīng)用變得更加廣泛[3-7]，在防震、航空等特殊領(lǐng)域也表現(xiàn)出了相應(yīng)價(jià)值[8-9]。隨著5G技術(shù)的蓬勃發(fā)展，未來(lái)無(wú)線傳感器網(wǎng)絡(luò)在智能灌溉、智慧城市等領(lǐng)域?qū)⒂袕V闊的發(fā)展空間[10-12]。

在無(wú)線傳感器網(wǎng)絡(luò)內(nèi)，傳感器節(jié)點(diǎn)的部署位置通常較為隨機(jī)。由于大多數(shù)傳感器節(jié)點(diǎn)體積較小且由電池供電，其能源總量受到限制，故降低網(wǎng)絡(luò)能耗、提高能源利用率是無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)重要研究方向。研究表明，采用分簇算法對(duì)網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)進(jìn)行分簇能夠有效地降低網(wǎng)絡(luò)能耗。分簇算法將無(wú)線傳感器網(wǎng)絡(luò)內(nèi)的傳感器節(jié)點(diǎn)分成若干個(gè)節(jié)點(diǎn)簇，每一個(gè)節(jié)點(diǎn)簇中包含多個(gè)成員節(jié)點(diǎn)和一個(gè)簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)主要用于匯集數(shù)據(jù)處理結(jié)果和發(fā)放監(jiān)測(cè)任務(wù)，成員節(jié)點(diǎn)主要用于監(jiān)測(cè)。當(dāng)上行傳輸數(shù)據(jù)時(shí)，成員節(jié)點(diǎn)首先將采集到的監(jiān)測(cè)對(duì)象相關(guān)數(shù)據(jù)信息進(jìn)行處理，然后把處理結(jié)果發(fā)送給所屬簇的簇頭節(jié)點(diǎn)；在下行傳輸數(shù)據(jù)時(shí)，各個(gè)成員節(jié)點(diǎn)接收來(lái)自所屬簇中的簇頭節(jié)點(diǎn)發(fā)放的監(jiān)測(cè)任務(wù)。簇頭節(jié)點(diǎn)和成員節(jié)點(diǎn)在數(shù)據(jù)傳輸?shù)倪^(guò)程中會(huì)消耗較多能量，因此尋找合適的簇頭節(jié)點(diǎn)是降低網(wǎng)絡(luò)通信能耗的關(guān)鍵。

針對(duì)如何降低無(wú)線傳感器網(wǎng)絡(luò)能耗、延長(zhǎng)網(wǎng)絡(luò)壽命這一問(wèn)題，文獻(xiàn)[13]提出了一種基于模糊聚類和粒子群算法的簇頭選擇方法，利用模糊算法初始聚類，然后利用粒子群算法選擇簇頭節(jié)點(diǎn)。該算法能夠有效地降低節(jié)點(diǎn)的死亡率，但當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的部署密度較大時(shí)，算法復(fù)雜度也隨之增長(zhǎng)，算法的搜索效率也跟著下降。文獻(xiàn)[14]提出了一種灰狼優(yōu)化算法，該算法能夠有效降低網(wǎng)絡(luò)能耗，但存在收斂速度不夠理想的缺點(diǎn)。文獻(xiàn)[15]提出了一種蟻群算法，該算法能夠有效縮短收斂時(shí)間，但容易陷入局部最優(yōu)。文獻(xiàn)[16]提出了一種基于模糊邏輯的土狼優(yōu)化聚類方法，先利用模糊邏輯算法獲得初始分簇方案，再利用土狼優(yōu)化算法進(jìn)行優(yōu)化；該算法有效延長(zhǎng)了無(wú)線傳感器網(wǎng)絡(luò)壽命，但分簇方案中的簇頭節(jié)點(diǎn)分布較為不均勻。文獻(xiàn)[17]提出了一種改進(jìn)的人工蜂群算法進(jìn)行分簇，該算法能夠合理地選出簇頭節(jié)點(diǎn)，但算法易陷入進(jìn)化停滯。

針對(duì)以上問(wèn)題，筆者提出了一種基于克隆精英遺傳算法的分簇方法，且將其和基于精英遺傳算法的分簇方法、基于蛙跳算法的分簇方法進(jìn)行了仿真比較。從仿真結(jié)果中可以看出，基于克隆精英遺傳算法的分簇方法能夠找到更加合適的簇頭節(jié)點(diǎn)進(jìn)行合理分簇，且網(wǎng)絡(luò)能耗明顯低于基于精英遺傳算法的分簇方法和基于蛙跳算法的分簇方法。

1 無(wú)線傳感器網(wǎng)絡(luò)分簇模型

在監(jiān)測(cè)范圍內(nèi)節(jié)點(diǎn)隨機(jī)分布的無(wú)線傳感器網(wǎng)絡(luò)分簇結(jié)構(gòu)如圖1所示。在大多數(shù)無(wú)線傳感器網(wǎng)絡(luò)中，通信能耗占網(wǎng)絡(luò)能耗總量的一半以上，故分簇時(shí)需要重點(diǎn)考慮如何降低發(fā)送和接收數(shù)據(jù)時(shí)的通信能耗。將大小為bbit的數(shù)據(jù)包發(fā)送到距離為d的接收節(jié)點(diǎn)時(shí)所消耗的能量為

圖1 無(wú)線傳感器網(wǎng)絡(luò)分簇結(jié)構(gòu)

Es(b，d)=bEelec+bεampdi。

(1)

接收節(jié)點(diǎn)接收大小為b的數(shù)據(jù)包所消耗的能量為

Er(b)=bEelec，

(2)

其中，Eelec表示電子能量參數(shù)，εamp表示功率放大參數(shù)。i的取值主要取決于所處的環(huán)境，周圍的環(huán)境越差，i的值就越大。通常i的取值范圍是[2，4]。

2 基于克隆精英遺傳算法的無(wú)線傳感器網(wǎng)絡(luò)分簇方法

2.1 克隆精英遺傳算法

遺傳算法(Genetic Algorithm，GA)最早是由美國(guó)的 John Holland于20世紀(jì)70年代提出的。它是一種能夠在全局中進(jìn)行尋優(yōu)搜索的算法，具有隨機(jī)、迭代和進(jìn)化等特點(diǎn)。但是它在對(duì)簇頭節(jié)點(diǎn)方案進(jìn)行選擇、交叉和變異操作時(shí)，很有可能會(huì)破壞原本較好的簇頭節(jié)點(diǎn)方案，使得新一代簇頭節(jié)點(diǎn)方案網(wǎng)絡(luò)能耗可能高于上一代簇頭節(jié)點(diǎn)方案的網(wǎng)絡(luò)能耗的情況。為了保證迭代過(guò)程中簇頭節(jié)點(diǎn)方案不斷優(yōu)化，網(wǎng)絡(luò)能耗越來(lái)越低，將克隆算子和精英算子引入遺傳算法，以增加最佳總體解決方案的可能性。

2.2 算法流程

基于克隆精英遺傳算法的無(wú)線傳感器網(wǎng)絡(luò)分簇方法的基本流程是：在擁有一定數(shù)量傳感器節(jié)點(diǎn)的監(jiān)測(cè)范圍內(nèi)，選擇一定比例的節(jié)點(diǎn)當(dāng)作簇頭節(jié)點(diǎn)，接著將未被選擇的節(jié)點(diǎn)列入距離其最近的簇頭節(jié)點(diǎn)所在簇內(nèi)，可以得到在當(dāng)前的簇頭節(jié)點(diǎn)方案下的網(wǎng)絡(luò)通信能耗，然后利用克隆精英遺傳算法優(yōu)化當(dāng)前的簇頭節(jié)點(diǎn)方案，通過(guò)不斷優(yōu)化使得網(wǎng)絡(luò)通信能耗越來(lái)越小。算法的具體步驟如下，

(1) 編碼?？寺【⑦z傳算法的一個(gè)重要步驟就是編碼，其將能量高效分簇問(wèn)題轉(zhuǎn)換為克隆精英遺傳算法能夠處理的問(wèn)題。在選擇、交叉和變異的過(guò)程中，編碼的好壞對(duì)算法運(yùn)行效率有著直接的影響。采用二進(jìn)制向量的方式對(duì)節(jié)點(diǎn)進(jìn)行編碼，二進(jìn)制向量中的每一位代表一個(gè)傳感器節(jié)點(diǎn)，也就是代表一個(gè)基因位點(diǎn)。

(2) 初始化種群。在基于克隆精英遺傳算法的分簇方法中，初始化種群時(shí)采用隨機(jī)生成的方法。例如在一定的監(jiān)測(cè)范圍內(nèi)有m個(gè)傳感器節(jié)點(diǎn)，對(duì)這m個(gè)傳感器節(jié)點(diǎn)進(jìn)行長(zhǎng)度為m的二進(jìn)制編碼。從這m個(gè)傳感器節(jié)點(diǎn)中隨機(jī)選擇一定比例的節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)，并將二進(jìn)制向量中簇頭節(jié)點(diǎn)對(duì)應(yīng)位置的值設(shè)為1，這樣該向量就代表了一個(gè)個(gè)體。以同樣的方法依次生成n個(gè)個(gè)體，這些個(gè)體就組成了初始種群，也就是初始的n個(gè)簇頭節(jié)點(diǎn)方案。

(4) 選擇。能量高效分簇是一個(gè)求解最小值的問(wèn)題，在基于克隆精英遺傳算法的分簇方法中，利用克隆算子對(duì)簇頭節(jié)點(diǎn)方案進(jìn)行選擇。將簇頭節(jié)點(diǎn)方案按照能耗從小到大進(jìn)行排序，按照一定的比率克隆能耗較小的簇頭節(jié)點(diǎn)方案，對(duì)克隆后的方案以較高的變異概率實(shí)施變異，從而組成新的種群。此時(shí)種群是由原種群中最優(yōu)的幾個(gè)簇頭節(jié)點(diǎn)方案經(jīng)過(guò)克隆和變異生成的，能量消耗小的分簇方案盡可能地保留了下來(lái)。

(5) 交叉。在使用克隆精英遺傳算法解決無(wú)線傳感器網(wǎng)絡(luò)分簇問(wèn)題的過(guò)程中，對(duì)簇頭節(jié)點(diǎn)方案進(jìn)行兩兩交叉，即隨機(jī)選擇一個(gè)交叉點(diǎn)將兩個(gè)簇頭節(jié)點(diǎn)方案中的相應(yīng)基因位點(diǎn)進(jìn)行交換。若兩個(gè)簇頭節(jié)點(diǎn)方案中有部分相同的基因位點(diǎn)，則可能出現(xiàn)交叉后兩個(gè)方案沒有任何變化的情況。為了避免這種情況的發(fā)生，先將兩個(gè)方案中相同的基因位點(diǎn)剔除，然后對(duì)剔除相同基因位點(diǎn)后的兩個(gè)方案進(jìn)行交叉。交叉后，再將被剔除掉的相同基因位點(diǎn)重新加入到方案中，以保證方案中簇頭節(jié)點(diǎn)數(shù)目和比例不變。種群中的所有個(gè)體都按順序進(jìn)行兩兩交叉，這樣就通過(guò)交叉操作生成了新的種群。

(6) 變異。在解決無(wú)線傳感器網(wǎng)絡(luò)分簇問(wèn)題的過(guò)程中，克隆精英遺傳算法在變異過(guò)程中采用的是隨機(jī)變異的方法。從種群中隨機(jī)選擇簇頭節(jié)點(diǎn)方案，然后隨機(jī)反轉(zhuǎn)方案中的部分基因位點(diǎn)，并將新生成的個(gè)體當(dāng)作新的簇頭節(jié)點(diǎn)方案，這樣就形成了新的種群。在變異時(shí)，由1翻轉(zhuǎn)至0的基因位點(diǎn)和由0翻轉(zhuǎn)至1的基因位點(diǎn)數(shù)量相同，因此變異操作過(guò)程中簇頭節(jié)點(diǎn)數(shù)目和比例不變。

(7) 精英個(gè)體的保留和更新。在使用克隆精英遺傳算法解決無(wú)線傳感器網(wǎng)絡(luò)分簇時(shí)，將上一代通信能耗最低的簇頭節(jié)點(diǎn)方案與當(dāng)前迭代過(guò)程中通信能耗最低的簇頭節(jié)點(diǎn)方案進(jìn)行對(duì)比。如果上一代最低通信能耗高于當(dāng)前迭代過(guò)程中的最低通信能耗，那么就將本代精英個(gè)體更新為當(dāng)前迭代過(guò)程中通信能耗最低的簇頭節(jié)點(diǎn)方案，否則直接將上一代精英個(gè)體作為本代精英個(gè)體。

(8) 迭代結(jié)束。判斷基于克隆精英遺傳算法的分簇方法迭代過(guò)程是否結(jié)束時(shí)，如果達(dá)到設(shè)定的迭代次數(shù)時(shí)，就結(jié)束迭代并輸出精英個(gè)體作為最優(yōu)簇頭節(jié)點(diǎn)方案；否則，重復(fù)選擇交叉變異等操作過(guò)程。

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

在無(wú)線傳感器網(wǎng)絡(luò)中，大部分傳感器節(jié)點(diǎn)上行發(fā)送數(shù)據(jù)的通信能耗遠(yuǎn)大于其接收下行控制指令時(shí)的通信能耗，所以在此仿真實(shí)驗(yàn)中只考慮節(jié)點(diǎn)在上行發(fā)送數(shù)據(jù)時(shí)的通信能耗。實(shí)驗(yàn)在Windows 10系統(tǒng)、 酷睿i5處理器、 8 GB內(nèi)存的PC機(jī)上，通過(guò)Matlab R2015b軟件進(jìn)行仿真。在仿真實(shí)驗(yàn)中，設(shè)置簇頭節(jié)點(diǎn)的比率為10%，網(wǎng)絡(luò)能耗利用式(1)計(jì)算。公式中的各個(gè)參數(shù)的取值為，數(shù)據(jù)包大小b的值取為1 KB，i的值取為3，Eelec的值取為50 nJ/bit，εamp的值取為100 pJ/(bit·m-2)。

在400 m×400 m的監(jiān)測(cè)范圍內(nèi)隨機(jī)部署傳感器節(jié)點(diǎn)，利用基于克隆精英遺傳算法的分簇方法、基于精英遺傳算法的分簇方法和基于蛙跳算法的分簇方法對(duì)WSN的網(wǎng)絡(luò)能耗進(jìn)行優(yōu)化。所提分簇方法中基因位點(diǎn)設(shè)為100個(gè)，變異概率設(shè)為0.1，過(guò)高的變異概率容易使算法陷入局部最優(yōu)。基于精英遺傳算法的分簇方法中基因位點(diǎn)設(shè)為100個(gè)，變異概率設(shè)為0.1?；谕芴惴ǖ姆执胤椒ㄖ星嗤芊N群數(shù)設(shè)為20個(gè)，每個(gè)種群有5只青蛙，組內(nèi)迭代數(shù)為10。

圖2和圖3是傳感器節(jié)點(diǎn)數(shù)為100和200時(shí)，基于克隆精英遺傳算法的分簇方法、基于精英遺傳算法的分簇方法和基于蛙跳算法的分簇方法選出的簇頭節(jié)點(diǎn)產(chǎn)生的能耗隨迭代次數(shù)的變化。從圖2中可以看到，基于克隆精英遺傳算法的分簇方法的最低能耗約為1.475 8 J，基于精英遺傳算法的分簇方法的最低能耗約為1.557 9 J，基于蛙跳算法的分簇方法的最低能耗約為1.643 2 J?；诳寺【⑦z傳算法的分簇方法優(yōu)化結(jié)果比基于精英遺傳算法的分簇方法的優(yōu)化結(jié)果好約5.27%，比基于蛙跳算法的分簇方法優(yōu)化結(jié)果好約10.19%。從圖3中可以看到，基于克隆精英遺傳算法的分簇方法的最低能耗約為1.102 2 J，基于精英遺傳算法的分簇方法的最低能耗約為1.178 5 J，基于蛙跳算法的分簇方法的最低能耗約為1.517 1 J。基于克隆精英遺傳算法的分簇方法優(yōu)化結(jié)果比基于精英遺傳算法的分簇方法的優(yōu)化結(jié)果好約6.47%，比基于蛙跳算法的分簇方法優(yōu)化結(jié)果好約27.35%?；诳寺【⑦z傳算法的分簇方法在降低網(wǎng)絡(luò)能耗上的效果明顯比另外兩種分簇方法分簇方法好，對(duì)延長(zhǎng)網(wǎng)絡(luò)壽命有顯著作用。

圖2 能耗對(duì)比(傳感器節(jié)點(diǎn)數(shù)為100)

圖3 能耗對(duì)比(傳感器節(jié)點(diǎn)數(shù)為200)

為了更加直觀地看到3種分簇方法選出的簇頭節(jié)點(diǎn)的分布情況，利用3種分簇方法對(duì)100個(gè)傳感器節(jié)點(diǎn)進(jìn)行分簇，結(jié)果如圖4至圖6所示。從圖4至圖6中可以看出，利用所提方法和基于精英遺傳算法的分簇方法選出的分簇方案中，簇頭節(jié)點(diǎn)分布較為均勻。而利用基于蛙跳算法的分簇方法選出的簇頭節(jié)點(diǎn)分布較為不均勻，部分簇頭節(jié)點(diǎn)之間的距離較近。圖7為3種分簇方法對(duì)100個(gè)傳感器節(jié)點(diǎn)進(jìn)行分簇的成簇情況，一條數(shù)據(jù)表示一個(gè)簇中的成員節(jié)點(diǎn)數(shù)。在圖7中可以看到，所提方法的分簇方案中每個(gè)簇內(nèi)的成員節(jié)點(diǎn)數(shù)目較為平均，基于精英遺傳算法的分簇方法的分簇方案中成員節(jié)點(diǎn)數(shù)目較不平均，而基于蛙跳的分簇方法中成員節(jié)點(diǎn)數(shù)目不一。綜上所述，基于克隆精英遺傳算法的分簇方法的分簇方案，簇頭節(jié)點(diǎn)分布均勻，成員節(jié)點(diǎn)數(shù)目平均，比另外兩種分簇方法的分簇方案更為合理。

圖4 基于克隆精英遺傳算法的分簇方法分簇結(jié)果

圖5 基于精英遺傳算法的分簇方法分簇結(jié)果

圖6 基于蛙跳算法的分簇方法分簇結(jié)果

圖7 3種分簇方法的分簇結(jié)果對(duì)比(100個(gè)節(jié)點(diǎn))

表1為圖2和圖3中3種方法的運(yùn)行時(shí)間對(duì)比。從表1中可以看出，基于蛙跳算法的分簇方法的運(yùn)行時(shí)間最長(zhǎng)，且隨著網(wǎng)絡(luò)節(jié)點(diǎn)密度的增加，運(yùn)行時(shí)間也增加得更多?；诳寺【⑦z傳算法的分簇方法的運(yùn)行時(shí)間比基于精英遺傳算法的分簇方法的運(yùn)行時(shí)間略小，但其最終優(yōu)化的網(wǎng)絡(luò)能耗低于基于精英遺傳算法的分簇方法的，即基于克隆精英遺傳算法的分簇方法在保證優(yōu)化效果的同時(shí)，擁有較低的時(shí)間復(fù)雜度。

表1 運(yùn)行時(shí)間對(duì)比 s

4 結(jié)束語(yǔ)

為了有效提高能源利用率、降低無(wú)線傳感器網(wǎng)絡(luò)能耗，筆者給出了一種基于克隆精英遺傳算法的分簇方法，用來(lái)找出合適的簇頭節(jié)點(diǎn)以降低無(wú)線傳感器網(wǎng)絡(luò)的通信能耗。將基于克隆精英遺傳算法的分簇方法與基于精英遺傳算法的分簇方法、基于蛙跳算法的分簇方法分別從不同節(jié)點(diǎn)數(shù)下能量消耗、簇頭節(jié)點(diǎn)分布、簇內(nèi)成員節(jié)點(diǎn)數(shù)目以及運(yùn)行時(shí)間進(jìn)行仿真比較。仿真結(jié)果顯示，基于克隆精英遺傳算法的分簇方法在優(yōu)化網(wǎng)絡(luò)能耗上的效果優(yōu)于基于精英遺傳算法的分簇方法和基于蛙跳算法的分簇方法，有效地延長(zhǎng)了網(wǎng)絡(luò)壽命，且分簇結(jié)果中簇頭節(jié)點(diǎn)分布與簇內(nèi)節(jié)點(diǎn)數(shù)較為合理，算法運(yùn)行時(shí)間較短。