柏 琪，佘星星，徐善山，鄭 昊，許 凱

（安徽信息工程學(xué)院 計(jì)算機(jī)與軟件工程學(xué)院，安徽 蕪湖 241000）

1 引言

無線傳感器網(wǎng)絡(luò)（WSN）作為一種準(zhǔn)確、實(shí)時(shí)的信息獲取方式，具有自組織、低能耗、配置方便、成本低等特點(diǎn)，在農(nóng)業(yè)、工業(yè)、軍事等方面都具有廣闊的應(yīng)用前景[1-2]。WSN由大量空間分布、無線連接、自治的傳感器節(jié)點(diǎn)組成，部署在監(jiān)測(cè)環(huán)境中，感知、處理和傳輸數(shù)據(jù)，但工作時(shí)間受到能量限制。因此，有必要設(shè)計(jì)一種有效的數(shù)據(jù)采集策略來降低節(jié)點(diǎn)的能量消耗，延長(zhǎng)WSN的壽命。

經(jīng)典的LEACH算法[3]是目前常用的一種分簇路由算法，但它仍然存在一定不足：（1）該算法沒有對(duì)簇頭的分布進(jìn)行規(guī)定，很可能出現(xiàn)被選中的簇頭集中在網(wǎng)絡(luò)的某一區(qū)域，一些節(jié)點(diǎn)的周圍沒有任何簇頭。（2）它在選取簇頭時(shí)是完全隨機(jī)的，導(dǎo)致能量不足的節(jié)點(diǎn)可能會(huì)成為簇頭，加速該節(jié)點(diǎn)死亡，減少整個(gè)網(wǎng)絡(luò)的生命周期。文獻(xiàn)[4]中普通節(jié)點(diǎn)可以計(jì)算自身剩余能量和周圍節(jié)點(diǎn)數(shù)量的比值，但是該算法對(duì)節(jié)點(diǎn)硬件要求太高，不符合實(shí)際。文獻(xiàn)[5]提出基于集中節(jié)能與距離的CEED算法，在選取簇頭節(jié)點(diǎn)時(shí)會(huì)考慮到節(jié)點(diǎn)的剩余能量，但該算法降低了簇頭節(jié)點(diǎn)選取的范圍。

本文對(duì)傳統(tǒng)的LEACH算法進(jìn)行改進(jìn)。改進(jìn)的U-LEACH算法中在簇頭的選擇上首先考慮剩余能力較大的節(jié)點(diǎn)，并在此基礎(chǔ)上考慮節(jié)點(diǎn)距離簇重心的距離，算法保證了簇頭的選舉更加合理，最大程度保證網(wǎng)絡(luò)的能耗平衡，延長(zhǎng)網(wǎng)絡(luò)生命周期。

2 網(wǎng)絡(luò)模型與節(jié)點(diǎn)能耗模型

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

假設(shè)WSN是由多個(gè)初始能量相同的、位置固定的和隨機(jī)部署在監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)組成。WSN中的每個(gè)節(jié)點(diǎn)都可以獲取自己的地理位置，感知自己的剩余能量。假設(shè)傳感器節(jié)點(diǎn)模型如下：

（1）傳感器節(jié)點(diǎn)是固定的，每個(gè)節(jié)點(diǎn)都有自己唯一的ID，N個(gè)傳感器節(jié)點(diǎn)和一個(gè)移動(dòng)sink的ID號(hào)集合為 M={n1，n2，n3，...，ni}，其中 ni是第 i個(gè)固定傳感器節(jié)點(diǎn)；

（2）所有傳感器節(jié)點(diǎn)同構(gòu)，能夠進(jìn)行數(shù)據(jù)融合；

（3）無線通信鏈路是雙向?qū)ΨQ的。該節(jié)點(diǎn)具有測(cè)距功能，可根據(jù)通信距離隨時(shí)調(diào)整發(fā)射功率；

（4）在沒有數(shù)據(jù)采集任務(wù)時(shí)，簇成員節(jié)點(diǎn)可以休眠，簇頭可以定時(shí)喚醒成員節(jié)點(diǎn)，請(qǐng)求其傳輸感測(cè)到的數(shù)據(jù)；

（5）傳感器節(jié)點(diǎn)存儲(chǔ)容量有限。當(dāng)未發(fā)送的感知數(shù)據(jù)量超過最大存儲(chǔ)容量時(shí)，節(jié)點(diǎn)將保存最新的數(shù)據(jù)，丟棄最早的數(shù)據(jù)。

2.2 能耗模型

本文提出算法的能耗模型是基于無線通信系統(tǒng)的能耗模型[6]。傳感器節(jié)點(diǎn)的能耗由發(fā)射端和接收端兩部分能耗組成。發(fā)射端的能耗包括射頻模塊和信號(hào)放大器的能耗，接收端的能耗僅包括接收電路的能耗。信號(hào)放大器的能量消耗是以發(fā)射端和接收端之間的距離為基礎(chǔ)的，可以使用自由空間衰落模型和多徑衰落模型。

某個(gè)傳感器節(jié)點(diǎn)發(fā)送L位數(shù)據(jù)所消耗的能量如公式（1）所示。

接收L位數(shù)據(jù)所消耗的能量與傳輸距離無關(guān)，如公式（2）所示：

3 算法描述

3.1 基于網(wǎng)格分簇

本文假設(shè)WSN是一個(gè)M×M個(gè)矩形區(qū)域，N個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在網(wǎng)絡(luò)中。如圖1所示，將網(wǎng)絡(luò)劃分為若干個(gè)等面積網(wǎng)格。

圖1 網(wǎng)絡(luò)網(wǎng)格圖

網(wǎng)格總數(shù)Cnum由N確定，如公式（3）所示。每個(gè)虛擬網(wǎng)格的寬度Cl可用公式（4）表示。

當(dāng)每個(gè)網(wǎng)格被視為一個(gè)簇時(shí)，整個(gè)網(wǎng)絡(luò)被劃分?jǐn)?shù)量為Cnum的相同大小的簇。傳感器節(jié)點(diǎn)屬于哪個(gè)簇，由其邏輯坐標(biāo)決定。

3.2 選擇簇頭

根據(jù)無線通信能耗模型，簇頭與簇中節(jié)點(diǎn)之間的通信能耗主要與距離有關(guān)。因此，為了減少和平衡簇內(nèi)的通信能耗，作為簇頭的節(jié)點(diǎn)應(yīng)該靠近簇的重心。網(wǎng)絡(luò)中k個(gè)簇可以表示為Ck(k=1，2，…，n)，CHk為簇Ck的簇頭，每個(gè)簇中的節(jié)點(diǎn)數(shù)為Nk。每個(gè)簇Ck的重心坐標(biāo)為（CCk，YCk），如公式（6）所示。

此外，由于簇頭需要轉(zhuǎn)發(fā)數(shù)據(jù)和管理簇，作為簇頭的節(jié)點(diǎn)也應(yīng)該有更多的剩余能量。所以，節(jié)點(diǎn)離重心越近，剩余能量越多，就越有可能被選擇為簇頭。因此，對(duì)于k個(gè)網(wǎng)格，構(gòu)造了簇頭選擇的加權(quán)和函數(shù)，如公式（7）所示。

根據(jù)公式（8），計(jì)算簇Ck中每個(gè)節(jié)點(diǎn)的f，并選擇以f最大的節(jié)點(diǎn)作為簇頭。在公式（7）中，ω的值根據(jù)實(shí)際需要確定的，如果ω值較大，則簇頭選擇更關(guān)注節(jié)點(diǎn)與重心之間的距離，否則則關(guān)注節(jié)點(diǎn)的剩余能量。

在每一輪結(jié)束時(shí)，簇中的每個(gè)節(jié)點(diǎn)都會(huì)報(bào)告其剩余的能量和到簇頭的重心的距離。簇頭根據(jù)公式（7）計(jì)算并比較每個(gè)節(jié)點(diǎn)的f值，f最大的節(jié)點(diǎn)將被選為下一輪的簇頭。

3.3 簇內(nèi)的數(shù)據(jù)傳輸

分簇并選擇簇頭完成后，簇中的其他節(jié)點(diǎn)向簇頭發(fā)送連接請(qǐng)求，該請(qǐng)求包含自己的ID。簇頭根據(jù)成員節(jié)點(diǎn)的數(shù)量將時(shí)間劃分為若干個(gè)時(shí)隙，即采用TDMA[7]機(jī)制為每個(gè)成員節(jié)點(diǎn)分配相應(yīng)的傳輸時(shí)隙。每個(gè)簇成員節(jié)點(diǎn)在自己的時(shí)隙內(nèi)收集并向簇頭發(fā)送數(shù)據(jù)，在其他時(shí)隙內(nèi)休眠以節(jié)省能量，簇頭收集信息并對(duì)數(shù)據(jù)進(jìn)行融合。

4 仿真與分析

4.1 模擬參數(shù)設(shè)置

仿真在MATLABr2018a環(huán)境下運(yùn)行。在仿真實(shí)驗(yàn)中，100-600個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在指定的范圍內(nèi)進(jìn)行多輪數(shù)據(jù)采集，每個(gè)節(jié)點(diǎn)的初始能量為1J，數(shù)據(jù)生成速率是隨機(jī)的，傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)發(fā)送的數(shù)據(jù)存在冗余。1位數(shù)據(jù)處理電路的ERF為50×10-9J/bit，單節(jié)點(diǎn)最大數(shù)據(jù)存儲(chǔ)容量為32kbit。綜合考慮剩余能量和距離，選擇ω為0.5。仿真參數(shù)如表1所示。

表1 模擬參數(shù)

4.2 結(jié)果和分析

為了分析該算法的有效性，將本文的U-LEACH算法與傳統(tǒng)的LEACH算法和文獻(xiàn)[5]的CEED算法進(jìn)行比較，將對(duì)三種算法的存活節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)生命周期進(jìn)行比較分析。

4.2.1 存活節(jié)點(diǎn)數(shù)比較

隨著網(wǎng)絡(luò)的運(yùn)行，一些節(jié)點(diǎn)由于能量耗盡，經(jīng)過一些回合后就會(huì)死亡。3種方法在不同輪次中對(duì)應(yīng)的活節(jié)點(diǎn)數(shù)如圖2所示。網(wǎng)絡(luò)生命周期可分為穩(wěn)定期和不穩(wěn)定期。在網(wǎng)絡(luò)的FND（第一節(jié)點(diǎn)死亡時(shí)間）之前，網(wǎng)絡(luò)處于穩(wěn)定期；網(wǎng)絡(luò)FND后，網(wǎng)絡(luò)處于不穩(wěn)定期。從圖中可以看出。U-LEACH和CEED的穩(wěn)定期明顯長(zhǎng)于LEACH。并且U-LEACH和CEED在不穩(wěn)定期的活節(jié)點(diǎn)數(shù)總是大于LEACH。這是因?yàn)閁-LEACH和CEED在網(wǎng)絡(luò)節(jié)點(diǎn)能耗平衡方面優(yōu)于LEACH，所以FND出現(xiàn)較晚，節(jié)點(diǎn)的生存時(shí)間更長(zhǎng)。結(jié)果表明，U-LEACH的網(wǎng)絡(luò)能量消耗比CEED更加均衡。

圖2 節(jié)點(diǎn)數(shù)隨輪數(shù)變化的比較

4.2.2 網(wǎng)絡(luò)生存期比較

圖3顯示了在不同網(wǎng)絡(luò)規(guī)模下的第一個(gè)節(jié)點(diǎn)死亡的時(shí)間，橫坐標(biāo)表示傳感器節(jié)點(diǎn)的數(shù)量，縱坐標(biāo)表示網(wǎng)絡(luò)的生命周期。這里以FND的輪數(shù)作為衡量標(biāo)準(zhǔn)。隨著傳感器節(jié)點(diǎn)數(shù)量的增加，LEACH算法的網(wǎng)絡(luò)生命周期呈下降趨勢(shì)，而U-LEACH和CEED的網(wǎng)絡(luò)壽命呈上升趨勢(shì)。U-LEACH和CEED算法在簇頭的選擇上都加入了新的影響因子，簇頭的選擇更合理，其中U-LEACH效果更突出。結(jié)果表明，本文U-LEACH算法能夠一定程度地延長(zhǎng)網(wǎng)絡(luò)的生命周期。

圖3 網(wǎng)絡(luò)生命周期比較圖

5 結(jié)語

本文提出了一種基于虛擬網(wǎng)格的LEACH改進(jìn)算法。將無線傳感器網(wǎng)絡(luò)劃分為若干個(gè)網(wǎng)格，每個(gè)網(wǎng)格是一個(gè)簇，簇頭的選取考慮了剩余能量和距離，最后對(duì)本文算法進(jìn)行了仿真，并與CEED算法和LEACH算法進(jìn)行了比較。結(jié)果表明，本文提出的算法在平衡網(wǎng)絡(luò)能耗和延長(zhǎng)網(wǎng)絡(luò)生存期方面具有很大的優(yōu)勢(shì)。但本文考慮的網(wǎng)絡(luò)簡(jiǎn)單，傳感器節(jié)點(diǎn)同構(gòu)，下一步實(shí)際應(yīng)用中應(yīng)考慮異構(gòu)節(jié)點(diǎn)的情況。