孫 環(huán)，陳宏濱

（桂林電子科技大學(xué)信息與通信學(xué)院，廣西桂林 541004）

（*通信作者電子郵箱chbscut@guet.edu.cn）

0 引言

目前，無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是物聯(lián)網(wǎng)研究的熱點(diǎn)領(lǐng)域之一，通過(guò)無(wú)線方式進(jìn)行數(shù)據(jù)交換，在智能家居、軍事勘測(cè)、遠(yuǎn)程醫(yī)療、交通等眾多領(lǐng)域都取得了一些應(yīng)用成果［1-2］。同時(shí)，在WSN 領(lǐng)域中，節(jié)點(diǎn)部署問(wèn)題是主要研究之一［3-4］。合理的節(jié)點(diǎn)部署策略不僅可以提高網(wǎng)絡(luò)數(shù)據(jù)傳輸效率和網(wǎng)絡(luò)資源利用率，還可以根據(jù)實(shí)際應(yīng)用需求的變化改變節(jié)點(diǎn)的數(shù)目以及狀態(tài)，動(dòng)態(tài)地調(diào)整網(wǎng)絡(luò)狀況。文獻(xiàn)［5］中提出了一種基于蟻群優(yōu)化算法的WSN 節(jié)點(diǎn)部署策略，主要針對(duì)節(jié)點(diǎn)的盲目連接以及網(wǎng)絡(luò)中盲目地進(jìn)行負(fù)載均衡部署，分別設(shè)計(jì)了基于組的連接機(jī)制和負(fù)載均衡部署機(jī)制，有效降低了部署成本；但該部署策略沒(méi)有考慮網(wǎng)絡(luò)的最大化覆蓋問(wèn)題。文獻(xiàn)［6］中提出了一種自然啟發(fā)式的離散螢火蟲算法（Firefly Algorithm，F(xiàn)A），用于WSN 中的最佳移動(dòng)數(shù)據(jù)收集，有效減少了移動(dòng)距離，提高了能源效率。文獻(xiàn)［7］中通過(guò)使用混合粒子群算法的FA 進(jìn)行節(jié)點(diǎn)部署，實(shí)現(xiàn)簇頭（Cluster Head，CH）的最佳定位，有效改善了網(wǎng)絡(luò)生命周期。文獻(xiàn)［8］中針對(duì)簇頭負(fù)載不均衡問(wèn)題，提出了一種非均勻密度WSN 節(jié)點(diǎn)的部署方案。該方案使得簇頭能保持均勻的能量消耗，從而延長(zhǎng)了網(wǎng)絡(luò)生命周期。文獻(xiàn)［9］中針對(duì)多種不同類型的需求提出了不同的部署策略：對(duì)于確定性和基于網(wǎng)格的部署問(wèn)題，提出了一種基于成本的部署算法，即節(jié)點(diǎn)進(jìn)行最短距離的連接，最小化移動(dòng)距離，從而最小化部署成本；此外，針對(duì)節(jié)點(diǎn)的負(fù)載情況，提出了基于網(wǎng)絡(luò)生命周期的部署算法，在負(fù)載過(guò)大的節(jié)點(diǎn)附近部署額外的節(jié)點(diǎn)，提高了網(wǎng)絡(luò)生存周期，但該算法依賴較多的傳感器節(jié)點(diǎn)。

文獻(xiàn)［10］中利用改進(jìn)正弦余弦算法進(jìn)行節(jié)點(diǎn)部署優(yōu)化，實(shí)驗(yàn)結(jié)果表明利用該算法部署的節(jié)點(diǎn)覆蓋率優(yōu)于改進(jìn)粒子群優(yōu)化算法和改進(jìn)灰狼優(yōu)算法，有效提高了網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋率。文獻(xiàn)［11］中提出了一種自適應(yīng)節(jié)點(diǎn)部署算法，利用最少的傳感器節(jié)點(diǎn)數(shù)目達(dá)到最大化網(wǎng)絡(luò)覆蓋范圍目標(biāo)，同時(shí)減小了節(jié)點(diǎn)的總移動(dòng)距離。文獻(xiàn)［12］中通過(guò)研究傳感器節(jié)點(diǎn)數(shù)量對(duì)部署的影響，提出了一種實(shí)現(xiàn)覆蓋最大化的部署方案；但該方案只是單一地進(jìn)行傳感器數(shù)量的研究，沒(méi)有考慮整個(gè)網(wǎng)絡(luò)的能耗均衡。文獻(xiàn)［13］中研究了一種具有無(wú)參數(shù)配置的異構(gòu)無(wú)線傳感器節(jié)點(diǎn)部署算法。該算法分為兩個(gè)部分：首先利用Delaunay 三角剖分方法查找出最大的覆蓋空洞；然后，采用eVForce方法避開障礙物進(jìn)行節(jié)點(diǎn)的部署。仿真結(jié)果表明，該算法的性能優(yōu)于隨機(jī)部署和傳統(tǒng)的Delaunay 三角網(wǎng)部署，并提高了節(jié)點(diǎn)異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋范圍和網(wǎng)絡(luò)生命周期。文獻(xiàn)［14］中提出了一種基于改進(jìn)FA 的移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方案，通過(guò)快速地移動(dòng)最密集區(qū)域節(jié)點(diǎn)的方式，使得WSN 在最短時(shí)間內(nèi)達(dá)到最大覆蓋范圍，從而擴(kuò)大了網(wǎng)絡(luò)范圍，獲取了更好的無(wú)線傳感器網(wǎng)絡(luò)分布；節(jié)點(diǎn)的能耗均衡問(wèn)題在傳感器節(jié)點(diǎn)的部署過(guò)程中很重要，它決定了網(wǎng)絡(luò)的運(yùn)行狀況，但在上述研究中并未考慮。

文獻(xiàn)［15］中提出了一種中繼節(jié)點(diǎn)能量感知部署方案，研究了能源豐富和能源有限兩類節(jié)點(diǎn)的部署，通過(guò)考慮節(jié)點(diǎn)的能源情況，移動(dòng)中繼節(jié)點(diǎn)；該部署方案確保了可持續(xù)的覆蓋，延長(zhǎng)了網(wǎng)絡(luò)的生命周期，但是移動(dòng)節(jié)點(diǎn)的能耗比較大。文獻(xiàn)［16］中利用FA來(lái)確定傳感器的最佳位置，最小化傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋和網(wǎng)絡(luò)連接時(shí)間。文獻(xiàn)［17］中提出了一種混沌FA 的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布優(yōu)化策略，有效地實(shí)現(xiàn)了網(wǎng)絡(luò)節(jié)點(diǎn)的優(yōu)化部署，并且具有優(yōu)化效果好、穩(wěn)定性好、魯棒性強(qiáng)的優(yōu)點(diǎn)。文獻(xiàn)［18］中提出了一種基于節(jié)點(diǎn)能耗均衡的分區(qū)域節(jié)點(diǎn)重部署算法，利用虛擬力對(duì)不同區(qū)域的節(jié)點(diǎn)進(jìn)行移動(dòng)，降低移動(dòng)能耗；但在節(jié)點(diǎn)分布過(guò)密或過(guò)疏的初始情況下，節(jié)點(diǎn)移動(dòng)數(shù)目多且頻繁，距離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn)能耗較大，縮短了網(wǎng)絡(luò)生命周期。

針對(duì)上述研究中的能量空洞問(wèn)題，本文綜合考慮網(wǎng)絡(luò)負(fù)載和節(jié)點(diǎn)能耗，提出了一種基于FA的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署（Node Redeployment Based on FA，NRBFA）策略。首先，建立一種節(jié)點(diǎn)非均勻部署的網(wǎng)絡(luò)模型，將節(jié)點(diǎn)隨機(jī)分布在網(wǎng)絡(luò)中，利用k-means 算法［19］對(duì)節(jié)點(diǎn)進(jìn)行分簇，在滿足覆蓋要求的情況下，篩選出冗余節(jié)點(diǎn)，使其進(jìn)入休眠狀態(tài)（此時(shí)冗余節(jié)點(diǎn)不進(jìn)行感知和發(fā)送數(shù)據(jù)）；然后，當(dāng)無(wú)線傳感器網(wǎng)絡(luò)運(yùn)行一段時(shí)間后，由于簇頭承擔(dān)著大量的數(shù)據(jù)融合和傳輸任務(wù)，導(dǎo)致簇頭的能量快速消耗，當(dāng)其剩余能量消耗達(dá)到一定閾值時(shí)，即小于網(wǎng)絡(luò)中存活的非冗余節(jié)點(diǎn)的剩余能量平均值的2/5時(shí)，不再進(jìn)行數(shù)據(jù)傳輸，此時(shí)喚醒冗余節(jié)點(diǎn)，利用FA 移動(dòng)冗余節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行重部署。換句話說(shuō)，就是將節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)間的歐氏距離作為兩個(gè)吸引力，通過(guò)計(jì)算選出吸引力最大的節(jié)點(diǎn)，即最佳冗余節(jié)點(diǎn)，去替換簇頭，成為新的簇頭，再進(jìn)行數(shù)據(jù)傳輸。同時(shí)，原簇頭也通過(guò)FA 尋找目標(biāo)節(jié)點(diǎn)，即具有最大吸引力的普通節(jié)點(diǎn)（Normal Node，NN），然后移動(dòng)到該目標(biāo)節(jié)點(diǎn)附近，替代目標(biāo)節(jié)點(diǎn)。最后，目標(biāo)節(jié)點(diǎn)成為新的冗余節(jié)點(diǎn)（Redundant Node，RN），更新冗余節(jié)點(diǎn)。該部署策略最大限度地使節(jié)點(diǎn)能耗均衡，延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期。本文的主要工作如下：

1）本文考慮了無(wú)線傳感器網(wǎng)絡(luò)中用于數(shù)據(jù)收集的能量空洞問(wèn)題，其中，傳感器節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量不一致，充分利用無(wú)線傳感器網(wǎng)絡(luò)中的冗余節(jié)點(diǎn)。

2）為解決能量空洞問(wèn)題，本文設(shè)計(jì)了一種基于FA的節(jié)點(diǎn)重部署策略。該策略旨在有效地移動(dòng)冗余節(jié)點(diǎn)以進(jìn)行節(jié)點(diǎn)重部署，而且該算法的復(fù)雜度較低。

3）通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了本文NRBFA 策略能有效地緩解能量空洞問(wèn)題，均衡網(wǎng)絡(luò)能耗，延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期。

1 系統(tǒng)模型

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

如圖1 所示，無(wú)線傳感器網(wǎng)絡(luò)模型主要由匯聚節(jié)點(diǎn)、簇頭、普通節(jié)點(diǎn)和冗余節(jié)點(diǎn)組成。其中，匯聚節(jié)點(diǎn)負(fù)責(zé)從簇頭收集數(shù)據(jù)；普通節(jié)點(diǎn)感知數(shù)據(jù)，然后將數(shù)據(jù)傳輸給該簇相應(yīng)的簇頭；簇頭節(jié)點(diǎn)負(fù)責(zé)收集、融合、轉(zhuǎn)發(fā)簇內(nèi)所有普通節(jié)點(diǎn)的數(shù)據(jù)；冗余節(jié)點(diǎn)負(fù)責(zé)替換簇頭，并且初始時(shí)處于休眠狀態(tài)。網(wǎng)絡(luò)執(zhí)行過(guò)程以網(wǎng)絡(luò)工作輪數(shù)的形式進(jìn)行，每一輪都包含數(shù)據(jù)的通信階段。

圖1 無(wú)線傳感器網(wǎng)絡(luò)模型Fig.1 Wireless sensor network model

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署的過(guò)程如下：首先，在邊長(zhǎng)為L(zhǎng)的正方形監(jiān)測(cè)區(qū)域內(nèi)，隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)，利用k-means 算法對(duì)所有傳感器節(jié)點(diǎn)進(jìn)行分簇；然后，普通節(jié)點(diǎn)將感知數(shù)據(jù)傳輸?shù)酱貎?nèi)簇頭，簇頭將簇內(nèi)所有節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行融合，并將融合后的數(shù)據(jù)傳輸?shù)絽R聚節(jié)點(diǎn)；最后，當(dāng)有簇頭的剩余能量達(dá)到設(shè)定的閾值時(shí)，冗余節(jié)點(diǎn)移動(dòng)替換簇頭。

受文獻(xiàn)［11］和文獻(xiàn)［20］的啟發(fā)，為了更好地實(shí)現(xiàn)本文研究目標(biāo)，本文中的節(jié)點(diǎn)位置信息都可以通過(guò)特殊方式獲得。因?yàn)楸疚膶R聚節(jié)點(diǎn)設(shè)置在監(jiān)測(cè)區(qū)域中心位置，若選擇多跳通信方式，則距離匯聚節(jié)點(diǎn)近的簇頭會(huì)加快能量消耗速度，節(jié)點(diǎn)的可移動(dòng)性有利于節(jié)點(diǎn)初始部署后的重部署。具體的假設(shè)如下：

1）每個(gè)節(jié)點(diǎn)都能通過(guò)全球定位系統(tǒng)（Global Positioning System，GPS）或其他一些特殊定位算法［20-21］知道自己的位置，相鄰節(jié)點(diǎn)間可以互相通信，每個(gè)傳感器節(jié)點(diǎn)有其唯一身份標(biāo)識(shí)號(hào)（Identity Document，ID）和相同的初始能量。

2）所有簇頭都以單跳方式向匯聚節(jié)點(diǎn)發(fā)送數(shù)據(jù)，簇內(nèi)普通節(jié)點(diǎn)也以單跳方式向自己的簇頭傳輸數(shù)據(jù)。

3）整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)在初始部署后都是可移動(dòng)的，并且簇與簇之間不存在信息的傳遞。

1.2 節(jié)點(diǎn)關(guān)系模型

在一個(gè)邊長(zhǎng)為L(zhǎng)的正方形內(nèi)隨機(jī)部署N個(gè)無(wú)線傳感器節(jié)點(diǎn)，定義為T={T1，T2，…，TN}，其中節(jié)點(diǎn)Ti的位置坐標(biāo)為(xi，yi)(i=1，2，…，N)，且每個(gè)節(jié)點(diǎn)具有相同的性能。本文為了尋找冗余節(jié)點(diǎn)，假設(shè)節(jié)點(diǎn)的感知半徑為RS，節(jié)點(diǎn)的檢測(cè)半徑為r，且RS＞r。在節(jié)點(diǎn)Ti的檢測(cè)半徑內(nèi)，假設(shè)存在一個(gè)冗余節(jié)點(diǎn)Tj，它的位置坐標(biāo)為(xj，yj)，則兩節(jié)點(diǎn)之間的歐氏距離dij的計(jì)算公式如式（1）所示：

則可以得到傳感器節(jié)點(diǎn)Ti感知到冗余節(jié)點(diǎn)Tj存在的感知概率P(i，j)為：

當(dāng)冗余節(jié)點(diǎn)Tj在傳感器節(jié)點(diǎn)Ti的感知范圍內(nèi)時(shí)，感知到的概率為1；反之，感知到的概率為0。

1.3 能量消耗模型

能量消耗在無(wú)線傳感器網(wǎng)絡(luò)中占重要地位，主要體現(xiàn)在數(shù)據(jù)通信階段，本文采用的能量消耗模型如下：

1）普通節(jié)點(diǎn)能耗。

假設(shè)節(jié)點(diǎn)間的通信距離為d，采用不同的能耗模式，節(jié)點(diǎn)i發(fā)送hbit 數(shù)據(jù)至節(jié)點(diǎn)j的能量損耗ET(h，d)的計(jì)算公式如式（2）所示：

節(jié)點(diǎn)接收hbit 數(shù)據(jù)的能量消耗ER(h)的計(jì)算公式如（3）所示：

其中：d0為距離閾值；Eelec是發(fā)送/接收1 bit 數(shù)據(jù)的能量消耗。εfs表示當(dāng)d≤d0時(shí)，自由空間中發(fā)送電路的放大系數(shù)，其值設(shè)為12 pJ/（bit·m-2）；εamp表示當(dāng)d＞d0時(shí)，多徑信道中發(fā)送電路的放大系數(shù)，其值設(shè)為0.001 2 pJ/（bit·m-2）；節(jié)點(diǎn)在感知過(guò)程中消耗的能量忽略不計(jì)。

2）簇頭節(jié)點(diǎn)能耗。

簇頭（CH）的能耗ECH主要由三部分組成：接收數(shù)據(jù)能耗Er、融合數(shù)據(jù)能耗Ef和發(fā)送數(shù)據(jù)能耗Es。根據(jù)文獻(xiàn)［22］中設(shè)定的簇頭數(shù)據(jù)融合率并結(jié)合本文無(wú)線傳感器網(wǎng)絡(luò)模型，進(jìn)行大量實(shí)驗(yàn)后，有以下規(guī)定：

1）簇頭的融合率rf為0.8；

2）當(dāng)簇頭接收h0bit數(shù)據(jù)的能耗Er表示為h0Eelec；

3）融合本簇內(nèi)h0bit數(shù)據(jù)的能耗Ef表示為h0ef，其中，ef為融合1 bit數(shù)據(jù)能耗；

4）發(fā)送h0bit 數(shù)據(jù)到距離為dCH?BS的基站的能耗Es計(jì)算公式如式（4）所示：

因此，在本簇內(nèi)CHi（簇頭i）的能耗ECHi公式如式（5）所示：

3）冗余節(jié)點(diǎn)能耗。

節(jié)點(diǎn)移動(dòng)的能量損耗Emove為：

其中：e為單位距離內(nèi)節(jié)點(diǎn)移動(dòng)的能耗，其值為5× 10-5J/m；dx為節(jié)點(diǎn)移動(dòng)距離。

2 問(wèn)題描述

本章描述傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)重部署的原因。首先，給出以下定義：

定義1生命周期。當(dāng)網(wǎng)絡(luò)中死亡節(jié)點(diǎn)數(shù)目達(dá)到網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)目的10%時(shí)，表示該網(wǎng)絡(luò)生命周期結(jié)束。

定義2死亡率。網(wǎng)絡(luò)中死亡節(jié)點(diǎn)數(shù)目與節(jié)點(diǎn)數(shù)目N的比值。

定義3冗余節(jié)點(diǎn)的集合R：R=｛R1，R2，…，Rx｝，且R∈T。

在無(wú)線傳感器網(wǎng)絡(luò)中，由于節(jié)點(diǎn)能量有限且難以進(jìn)行補(bǔ)充或替換、多對(duì)一通信等特點(diǎn)，容易產(chǎn)生能量空洞現(xiàn)象，導(dǎo)致節(jié)點(diǎn)能量消耗不均衡。在無(wú)線傳感器網(wǎng)絡(luò)初始部署階段，大量的傳感器節(jié)點(diǎn)在初始階段被隨機(jī)部署在監(jiān)測(cè)區(qū)域，不可避免地會(huì)產(chǎn)生重疊區(qū)域，從而會(huì)造成能量的浪費(fèi)而且產(chǎn)生大量冗余數(shù)據(jù)，占用有限的網(wǎng)絡(luò)帶寬。隨著網(wǎng)絡(luò)的運(yùn)行，簇頭不斷收集數(shù)據(jù)，能量消耗過(guò)快，將無(wú)法承擔(dān)數(shù)據(jù)接收和轉(zhuǎn)發(fā)的任務(wù)，網(wǎng)絡(luò)將停止運(yùn)行，嚴(yán)重影響了網(wǎng)絡(luò)的生命周期。因此，如何通過(guò)節(jié)點(diǎn)重部署來(lái)均衡節(jié)點(diǎn)能耗，以最大限度地延長(zhǎng)網(wǎng)絡(luò)生命周期是一個(gè)值得研究的問(wèn)題。

將N個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在監(jiān)測(cè)區(qū)域中，每個(gè)節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量m是隨機(jī)的。首先，本文在初始部署過(guò)程中引入冗余節(jié)點(diǎn)，在避免重復(fù)收集數(shù)據(jù)的情況下，減少了節(jié)點(diǎn)的能耗。然后，在網(wǎng)絡(luò)運(yùn)行過(guò)程中，當(dāng)簇頭達(dá)到數(shù)據(jù)承載極限、剩余能量達(dá)到一定閾值時(shí)，利用FA進(jìn)行節(jié)點(diǎn)移動(dòng)。具體方法是以節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)間的歐氏距離為FA 中的兩個(gè)吸引力，找出最佳冗余節(jié)點(diǎn)。最后，最佳冗余節(jié)點(diǎn)移動(dòng)替換簇頭，原簇頭替代目標(biāo)節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)變?yōu)槿哂喙?jié)點(diǎn)，更新冗余節(jié)點(diǎn)。利用節(jié)點(diǎn)能耗均衡來(lái)衡量傳感器網(wǎng)絡(luò)的生命周期，有效地延長(zhǎng)了無(wú)線傳感器網(wǎng)絡(luò)的生命周期。

本文的目標(biāo)函數(shù)是最小化所有簇頭剩余能量的標(biāo)準(zhǔn)差，以均衡網(wǎng)絡(luò)能耗，表示如式（7）所示：

其中：NCH為簇頭數(shù)目；Eres(CHi)為簇頭的剩余能量。

其中：Eres_max（CH）表示簇頭剩余的最大能量；NRN為冗余節(jié)點(diǎn)數(shù)目。

3 NRBFA描述

3.1 螢火蟲算法

螢火蟲算法（FA）是一種啟發(fā)式算法，有以下三個(gè)基本假設(shè)：

1）所有螢火蟲都是無(wú)性別之分，每一只螢火蟲只會(huì)被比其更亮的螢火蟲所吸引。

2）螢火蟲之間的吸引力與它們的亮度成正比，對(duì)于任意兩個(gè)螢火蟲，亮度低的螢火蟲向亮度高的螢火蟲移動(dòng)，越靠近亮度越強(qiáng)，吸引力越大，即吸引力與亮度成正比，而亮度隨距離的增加而變?nèi)?，則吸引力與距離成反比。

3）螢火蟲的亮度由目標(biāo)函數(shù)決定［23］。

3.2 NRBFA步驟

本文提出了一種基于FA 的無(wú)線傳感器節(jié)點(diǎn)重部署策略NRBFA 來(lái)解決節(jié)點(diǎn)能耗不均衡問(wèn)題，該策略的具體描述如下：

NRBFA 策略利用螢火蟲之間的吸引力，以節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)間的距離作為吸引力，使得冗余節(jié)點(diǎn)向需要被替換的簇頭方向移動(dòng)，同時(shí)被替換后的原簇頭向目標(biāo)節(jié)點(diǎn)移動(dòng)，實(shí)現(xiàn)冗余節(jié)點(diǎn)的移動(dòng)和更新。該策略最小化簇頭剩余能量的標(biāo)準(zhǔn)差，使得網(wǎng)絡(luò)負(fù)載和節(jié)點(diǎn)能耗均衡。此外，該算法具有較強(qiáng)的局部搜索能力，可以在一個(gè)較小的區(qū)域內(nèi)找到最優(yōu)解，操作方便，實(shí)現(xiàn)簡(jiǎn)單，參數(shù)較少；且從圖2 算法流程圖分析可知，本文NRBFA 的時(shí)間復(fù)雜度為O（TNlogN），復(fù)雜性較低。其中：T為最大迭代次數(shù)，N為節(jié)點(diǎn)數(shù)目。因此，利用FA來(lái)優(yōu)化節(jié)點(diǎn)位置，可以更好地提高網(wǎng)絡(luò)能量效率，延長(zhǎng)網(wǎng)絡(luò)的生命周期。

具體算法步驟如下：

步驟1 節(jié)點(diǎn)隨機(jī)分布在監(jiān)測(cè)區(qū)內(nèi)，然后利用k-means 算法對(duì)傳感器節(jié)點(diǎn)進(jìn)行分簇，選出冗余節(jié)點(diǎn)，冗余節(jié)點(diǎn)一開始處于睡眠狀態(tài)，不進(jìn)行任何通信，不消耗能量。

步驟2 計(jì)算出每個(gè)簇頭到達(dá)基站的距離dCH-BS以及每個(gè)簇內(nèi)普通節(jié)點(diǎn)到CH的距離dNN-CH。

步驟3 計(jì)算出冗余節(jié)點(diǎn)到簇頭的距離dRN-CH以及剩余能量，并進(jìn)行排序。

步驟4 當(dāng)簇頭的剩余能量小于其設(shè)定的能量閾值時(shí)，通過(guò)FA選擇最佳冗余節(jié)點(diǎn)RNbest，然后移動(dòng)RNbest去替換簇頭；原簇頭也利用FA 找到目標(biāo)節(jié)點(diǎn)，向目標(biāo)節(jié)點(diǎn)移動(dòng)，此時(shí)目標(biāo)節(jié)點(diǎn)成為新的冗余節(jié)點(diǎn)。

步驟4.1 在運(yùn)用FA 移動(dòng)冗余節(jié)點(diǎn)和簇頭時(shí)，簇頭與普通節(jié)點(diǎn)間的吸引力F(I1)以及簇頭與冗余節(jié)點(diǎn)間的吸引力F(I2)分別表示為：

式（9）中：I0為螢火蟲個(gè)體自身的無(wú)衰減的發(fā)光亮度，即最大的發(fā)光亮度；F（I）表示為節(jié)點(diǎn)間的吸引力，即為適應(yīng)度函數(shù)，進(jìn)行節(jié)點(diǎn)替換時(shí)，選擇適應(yīng)度函數(shù)最好的節(jié)點(diǎn)進(jìn)行移動(dòng)；dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離。在本文中，節(jié)點(diǎn)間的吸引力由節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)間的歐氏距離組成。式（10）～（11）中：γ為光強(qiáng)吸收系數(shù)，其值設(shè)為1，用來(lái)表示螢火蟲的發(fā)光亮度與距離成反比的關(guān)系；Eres_TN為目標(biāo)節(jié)點(diǎn)的剩余能量；Eres_RN為冗余節(jié)點(diǎn)的剩余能量；dCH_TN為簇頭到目標(biāo)節(jié)點(diǎn)的距離；dRN_CH為冗余節(jié)點(diǎn)到簇頭的距離，在計(jì)算過(guò)程中都將剩余能量和距離進(jìn)行了歸一化。λ1和λ2是權(quán)重系數(shù)，為常數(shù)，分別表示為冗余節(jié)點(diǎn)更新螢火蟲系數(shù)和冗余節(jié)點(diǎn)替換簇頭螢火蟲系數(shù)。

步驟4.2 節(jié)點(diǎn)進(jìn)行移動(dòng)后的位置更新公式如式（12）所示：

節(jié)點(diǎn)間的吸引度β可表示為：

其中：xi和xj分別代表節(jié)點(diǎn)i和j在搜索空間中的位置；α 為［0，1］上的常數(shù)，設(shè)為0.5；rand為［0，1］上服從均勻分布的隨機(jī)因子；β0為螢火蟲在光源處的最大吸引度，設(shè)為1。

步驟4.3 當(dāng)簇頭節(jié)點(diǎn)能量耗盡，冗余節(jié)點(diǎn)替換簇頭節(jié)點(diǎn)進(jìn)行工作，但此時(shí)不再尋找目標(biāo)節(jié)點(diǎn)，即冗余節(jié)點(diǎn)不再更新，若網(wǎng)絡(luò)中沒(méi)有冗余節(jié)點(diǎn)可以替換簇頭，則網(wǎng)絡(luò)生命周期結(jié)束。

步驟5 節(jié)點(diǎn)替換后，若在網(wǎng)絡(luò)生命周期內(nèi)，則繼續(xù)收集數(shù)據(jù)，迭代次數(shù)加1；反之，網(wǎng)絡(luò)生命結(jié)束。

所提出的NRBFA策略的算法流程如圖2所示。

圖2 NRBFA策略的算法流程Fig.2 Algorithm flowchart of NRBFA strategy

4 仿真與結(jié)果分析

本文仿真在Matlab R2014a 環(huán)境下運(yùn)行。在仿真實(shí)驗(yàn)中，分別測(cè)試50、100、150、200個(gè)傳感器節(jié)點(diǎn)在網(wǎng)絡(luò)規(guī)模為100 m的正方形區(qū)域范圍內(nèi)進(jìn)行節(jié)點(diǎn)重部署后的網(wǎng)絡(luò)性能表現(xiàn)?；疚挥诰W(wǎng)絡(luò)中心，利用k-means 算法進(jìn)行分簇，簇的個(gè)數(shù)為6，各節(jié)點(diǎn)的初始能量都為1 J，每個(gè)節(jié)點(diǎn)采集數(shù)據(jù)量在1 000～2 000 bit 內(nèi)隨機(jī)產(chǎn)生，收發(fā)電路處理1 bit 的數(shù)據(jù)能耗Eelec為50 × 10-9J，簇頭融合1 bit 的數(shù)據(jù)能耗為50 × 10-9J，權(quán)重系數(shù)λ1和λ2都取0.5。將文獻(xiàn)［18］中的節(jié)點(diǎn)部署策略作為基準(zhǔn)方案，它是基于虛擬力的分區(qū)域節(jié)點(diǎn)重部署方案VFA（Virtual Force Algorithm），該方案將圓形區(qū)域均勻劃分為6 個(gè)相等的扇形區(qū)域，節(jié)點(diǎn)基于虛擬力進(jìn)行移動(dòng)。本文為了在同一環(huán)境下進(jìn)行比較，現(xiàn)將圓形區(qū)域等價(jià)于邊長(zhǎng)為100 m 的正方形區(qū)域中，將本文算法與基于虛擬力的節(jié)點(diǎn)部署算法在不同部署范圍內(nèi)的節(jié)點(diǎn)能耗均衡以及網(wǎng)絡(luò)生命周期進(jìn)行比較。

圖3 展示了網(wǎng)絡(luò)總能耗隨網(wǎng)絡(luò)工作輪數(shù)的變化趨勢(shì)。在計(jì)算網(wǎng)絡(luò)總能耗的過(guò)程中，節(jié)點(diǎn)傳輸數(shù)據(jù)所消耗的能量占主要部分，網(wǎng)絡(luò)的總能耗隨網(wǎng)絡(luò)工作輪數(shù)的增加呈增長(zhǎng)的趨勢(shì)；并且，網(wǎng)絡(luò)中部署的節(jié)點(diǎn)數(shù)目越多，節(jié)點(diǎn)所傳輸?shù)臄?shù)據(jù)越多，網(wǎng)絡(luò)的總能耗就越大。在網(wǎng)絡(luò)運(yùn)行的前203 輪內(nèi)，在VFA 的部署方案中，由于部分節(jié)點(diǎn)一開始就進(jìn)行區(qū)間移動(dòng)，而在本文的部署策略中，只有當(dāng)簇頭的剩余能量大于設(shè)定的閾值時(shí)，網(wǎng)絡(luò)中沒(méi)有節(jié)點(diǎn)進(jìn)行移動(dòng)，并且冗余節(jié)點(diǎn)處于睡眠狀態(tài)，不進(jìn)行感知和傳輸數(shù)據(jù)，不消耗能量，導(dǎo)致VFA 方案中的網(wǎng)絡(luò)總能耗比本文的NRBFA 策略的總能耗大。但在203 輪之后，基于VFA 的部署方案中，節(jié)點(diǎn)數(shù)目為200 的網(wǎng)絡(luò)總能耗不再變化，此時(shí)網(wǎng)絡(luò)已經(jīng)不能工作，節(jié)點(diǎn)數(shù)目分別為50、100、150 的網(wǎng)絡(luò)也在315輪后能耗全部停止增加，而本文算法卻在500輪之后的網(wǎng)絡(luò)總能耗還是趨于增長(zhǎng)的趨勢(shì)。圖3 體現(xiàn)了NRBFA 策略要優(yōu)于VFA 方案，具有更長(zhǎng)的網(wǎng)絡(luò)生命周期和更高的網(wǎng)絡(luò)能量效率。

圖4 是網(wǎng)絡(luò)總傳輸數(shù)據(jù)量隨著網(wǎng)絡(luò)工作輪數(shù)的變化。在50、100、150、200個(gè)節(jié)點(diǎn)部署范圍內(nèi)，由于NRBFA策略中存在冗余節(jié)點(diǎn)，基于VFA 的部署方案一開始傳輸?shù)臄?shù)據(jù)量要比NRBFA 策略多，但隨著網(wǎng)絡(luò)運(yùn)行輪數(shù)的不斷增加，VFA 中的網(wǎng)絡(luò)在315 輪基本不能工作，之后就沒(méi)有傳輸數(shù)據(jù)，而本文方案在500 輪之后網(wǎng)絡(luò)總傳輸數(shù)據(jù)量還呈增長(zhǎng)趨勢(shì)，總的數(shù)據(jù)傳輸量遠(yuǎn)遠(yuǎn)多于VFA方案。

圖3 VFA與NRBFA的網(wǎng)絡(luò)總能耗隨輪數(shù)的變化情況Fig.3 Total energy consumption of network of VFA and NRBFA changes with number of rounds

圖4 VFA與NRBFA的網(wǎng)絡(luò)總傳輸數(shù)據(jù)量隨輪數(shù)的變化情況Fig.4 Total amount of data transmitted on network of VFA and NRBFA changes with number of rounds

圖5 是不同部署范圍下的網(wǎng)絡(luò)生命周期變化情況。由圖5 可知，隨著網(wǎng)絡(luò)部署的節(jié)點(diǎn)數(shù)目增加，由于網(wǎng)絡(luò)中的主要能耗來(lái)源于網(wǎng)絡(luò)的節(jié)點(diǎn)的數(shù)據(jù)傳輸，節(jié)點(diǎn)數(shù)目越多，傳輸?shù)臄?shù)據(jù)越多，消耗的能量越大，網(wǎng)絡(luò)生命周期總體為下降趨勢(shì)。當(dāng)網(wǎng)絡(luò)中部署50 個(gè)節(jié)點(diǎn)時(shí)，兩個(gè)方案的生命周期都是最長(zhǎng)的，分別為3 585 輪和315 輪，隨著節(jié)點(diǎn)數(shù)目的增加，網(wǎng)絡(luò)生命周期相應(yīng)地縮短。NRBFA 策略和VFA 方案相比，在相同的部署范圍內(nèi)，本文的部署策略效果更好，網(wǎng)絡(luò)生命周期遠(yuǎn)遠(yuǎn)長(zhǎng)于VFA方案對(duì)應(yīng)的網(wǎng)絡(luò)生命周期。

圖5 VFA與NRBFA在不同部署范圍的網(wǎng)絡(luò)生命周期對(duì)比Fig.5 Network lifetime comparison of VFA and NRBFA under different deployment scopes

圖6 顯示不同部署范圍下的節(jié)點(diǎn)能耗均衡狀況。由于每一輪節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量是在1 000～2 000 bit 范圍內(nèi)隨機(jī)產(chǎn)生的，網(wǎng)絡(luò)出現(xiàn)首個(gè)死亡節(jié)點(diǎn)的輪數(shù)和總輪數(shù)可能會(huì)有一定差異，本文以最終保存的數(shù)據(jù)為準(zhǔn)。由圖6 可知，隨著網(wǎng)絡(luò)部署節(jié)點(diǎn)數(shù)目的增加，本文部署策略的首個(gè)節(jié)點(diǎn)死亡輪數(shù)到網(wǎng)絡(luò)死亡輪數(shù)之差變化曲線呈增長(zhǎng)的趨勢(shì)，波動(dòng)范圍較小，在20輪以內(nèi)；而VFA 方案中波動(dòng)范圍較大，在200輪左右。從而可以得出，本文的部署策略在節(jié)點(diǎn)能耗均衡方面較VFA 方案效果好，節(jié)點(diǎn)能耗也更均衡。

圖6 VFA與NRBFA在不同部署范圍的節(jié)點(diǎn)能耗均衡對(duì)比Fig.6 Node energy consumption balance comparison of VFA and NRBFA under different deployment scopes

本文的實(shí)驗(yàn)數(shù)據(jù)主要是從數(shù)據(jù)量、網(wǎng)絡(luò)能耗以及網(wǎng)絡(luò)生命周期來(lái)進(jìn)行說(shuō)明的。本文的仿真結(jié)果表明，NRBFA 策略在數(shù)據(jù)收集、緩解能量空洞問(wèn)題以及延長(zhǎng)網(wǎng)絡(luò)生命周期方面優(yōu)于VFA 方案。該策略在兼顧網(wǎng)絡(luò)能耗均衡的同時(shí)，也保證了數(shù)據(jù)的有效收集，且在不同節(jié)點(diǎn)部署范圍內(nèi)，同樣有效地均衡了節(jié)點(diǎn)能耗，緩解了能量空洞問(wèn)題，延長(zhǎng)了網(wǎng)絡(luò)生命周期。

5 結(jié)語(yǔ)

在網(wǎng)絡(luò)運(yùn)行過(guò)程中，由于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的能量有限，難以補(bǔ)充或更改，故節(jié)點(diǎn)部署是無(wú)線傳感器網(wǎng)絡(luò)中均衡節(jié)點(diǎn)能耗、延長(zhǎng)網(wǎng)絡(luò)生命周期的主要問(wèn)題之一。針對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)能耗不均衡問(wèn)題，本文提出了一種基于螢火蟲算法（FA）的節(jié)點(diǎn)重部署策略NRBFA，考慮到無(wú)線傳感網(wǎng)絡(luò)進(jìn)行一段時(shí)間的數(shù)據(jù)采集后，簇頭負(fù)載過(guò)大，能量急劇消耗，當(dāng)其剩余能量達(dá)到設(shè)定閾值時(shí)，不再具備擔(dān)任簇頭和轉(zhuǎn)發(fā)數(shù)據(jù)的能力。此時(shí)，基于FA 進(jìn)行節(jié)點(diǎn)重部署，以節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)間的距離為吸引力判定指標(biāo)，冗余節(jié)點(diǎn)移動(dòng)替換簇頭，原簇頭尋找目標(biāo)節(jié)點(diǎn)，更新冗余節(jié)點(diǎn)，以最小化網(wǎng)絡(luò)簇頭剩余能量的標(biāo)準(zhǔn)差，使網(wǎng)絡(luò)能耗更均衡。仿真結(jié)果表明，在不同部署范圍內(nèi)，相較基于VFA的節(jié)點(diǎn)部署方案，本文提出的NRBFA策略使得節(jié)點(diǎn)能耗更均衡，網(wǎng)絡(luò)生命周期更長(zhǎng)且復(fù)雜度更低。此外，下一步考慮各集群的數(shù)據(jù)量不均勻，引入冗余節(jié)點(diǎn)，進(jìn)行集群的拆分，改變集群的規(guī)模，使簇的數(shù)據(jù)量相對(duì)平衡。