基于和聲搜索的能量有效路由算法

王寶亮，彭 程，李 科

(天津大學(xué) 電氣自動(dòng)化與信息工程學(xué)院，天津 300072)

0 引 言

隨著物聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，越來(lái)越多的環(huán)境需要提供實(shí)時(shí)檢測(cè)。無(wú)線傳感網(wǎng)絡(luò)(wireless sensor network，WSN)通過(guò)在布控范圍內(nèi)按需分布不同種類(lèi)的傳感器節(jié)點(diǎn)，實(shí)現(xiàn)對(duì)環(huán)境信息的收集。由于環(huán)境的不確定性，節(jié)點(diǎn)部署后往往得不到進(jìn)一步的能量供應(yīng)，這就要求網(wǎng)絡(luò)有一定的自組織能力，避免能量黑洞的出現(xiàn)。

路由搜索問(wèn)題屬于一種典型的NP-Hard問(wèn)題，目前，解決這類(lèi)問(wèn)題更多的是使用元啟發(fā)算法[1]。國(guó)內(nèi)外眾多學(xué)者大多將焦點(diǎn)集中在遺傳算法(GA)[2]、和聲搜索算法(HS)、蟻群優(yōu)化算法[3](ACO)及粒子群優(yōu)化算法(PSO)[4]等等上。這些算法在解決實(shí)際問(wèn)題時(shí)，往往針對(duì)不同的應(yīng)用場(chǎng)景，結(jié)合具體的問(wèn)題進(jìn)行開(kāi)發(fā)設(shè)計(jì)，沒(méi)有統(tǒng)一有效的解決方案。

本文基于以上研究背景，選擇和聲搜索算法作為基礎(chǔ)算法，提出了能有效延長(zhǎng)網(wǎng)絡(luò)運(yùn)行時(shí)長(zhǎng)的路由搜索策略。該算法相比之前同類(lèi)算法，更加側(cè)重提高WSN網(wǎng)絡(luò)使用過(guò)程中邊緣節(jié)點(diǎn)的參與度，在傳統(tǒng)HS算法的基礎(chǔ)上，結(jié)合全新的和聲記憶庫(kù)路由編碼方式，引入更為有效分段式目標(biāo)函數(shù)，同時(shí)在路由選擇后期加入節(jié)點(diǎn)移除策略和角度偏移方法，進(jìn)一步提高WSN運(yùn)行后期邊緣節(jié)點(diǎn)的使用頻率，一定程度上延長(zhǎng)網(wǎng)絡(luò)的生命周期，可以獲得較好的能量均衡效果。

1 相關(guān)工作

文獻(xiàn)[5]提出了一種基于能量效率的和聲搜索路由算法(EEHSBR)，其規(guī)定了路由傳輸?shù)幕经h(huán)境和限制條件，并使用傳統(tǒng)的和聲搜索算法進(jìn)行分析實(shí)現(xiàn)，為HS算法的使用提供了一種全新的解決方案。文獻(xiàn)[6]在EEHSBR 算法的基礎(chǔ)上，更換了和聲記憶庫(kù)的編碼形式和路由的生成方式，同時(shí)刪除了部分冗余的參數(shù)，引入新的目標(biāo)函數(shù)，提出一種IHSBEER算法。該算法總體來(lái)說(shuō)兼顧了能量消耗和路徑長(zhǎng)度，但在網(wǎng)絡(luò)使用后期，一味考慮路徑長(zhǎng)度會(huì)使節(jié)點(diǎn)的剩余能量差距明顯，網(wǎng)絡(luò)運(yùn)行期間過(guò)于依賴于主要節(jié)點(diǎn)，使其能量迅速降低。

經(jīng)典的HS算法具有較強(qiáng)的全局搜索能力，邏輯較為簡(jiǎn)單，控制流程的參數(shù)較少[7]，HMCR和PAR的配對(duì)使用可以解決大多數(shù)的問(wèn)題。HS算法主要用于處理連續(xù)值的優(yōu)化問(wèn)題，無(wú)論是和聲記憶庫(kù)(harmony memory，HM)的生成還是微調(diào)階段的處理，得到的值均為連續(xù)的。而路由的尋址問(wèn)題上，節(jié)點(diǎn)分布是隨機(jī)的，路徑的選擇是離散的，每個(gè)節(jié)點(diǎn)擁有唯一的ID編碼[8]。無(wú)論是節(jié)點(diǎn)的選擇，還是路徑的選擇都是離散分布的問(wèn)題。因此，針對(duì)WSN路由問(wèn)題的特點(diǎn)，經(jīng)典的HS算法需要進(jìn)行如下改進(jìn)：

(1)新的路徑以路徑組Xi的形式保存在HM中

Xi=(s,x1,x2,x3,…d)

(1)

每條路徑的第一個(gè)值為源節(jié)點(diǎn)s，最后一個(gè)值為目的節(jié)點(diǎn)d(即sink節(jié)點(diǎn))，中間依次存放下一跳節(jié)點(diǎn)的信息。

(2)HM的維數(shù)不再統(tǒng)一為某一固定值，新路徑的長(zhǎng)度允許不同，HM中存放著有限條由源節(jié)點(diǎn)到目的節(jié)點(diǎn)的通路集合

(2)

(3)根據(jù)新路徑的長(zhǎng)度及其能耗情況設(shè)置相應(yīng)的目標(biāo)函數(shù)[9]，生成的新路徑都需要經(jīng)過(guò)目標(biāo)函數(shù)的判斷來(lái)決定是否可以使用。

(4)HMCR的取值不再固定，采用自適應(yīng)的HMCR，避免引起早熟現(xiàn)象。

2 本文提出的算法

在這一節(jié)中，首先介紹了算法適用的系統(tǒng)模型，然后簡(jiǎn)述信息傳遞過(guò)程中使用的能量傳輸模型[10]；最后在經(jīng)典HS算法基礎(chǔ)上，詳細(xì)介紹本文提出的BTPHS算法。

2.1 系統(tǒng)模型

本文算法在設(shè)計(jì)時(shí)，主要針對(duì)無(wú)后續(xù)能量補(bǔ)充的大范圍部署節(jié)點(diǎn)的使用環(huán)境。因此對(duì)傳感器節(jié)點(diǎn)的分布和使用情況做出如下約定：

(1)在M×M的有限區(qū)域內(nèi)隨機(jī)分布N個(gè)傳感器節(jié)點(diǎn)；

(2)傳感器節(jié)點(diǎn)確定后，不可隨意移動(dòng)，不可中途充電，且各個(gè)節(jié)點(diǎn)的初始能量相同；

(3)sink節(jié)點(diǎn)回收所有監(jiān)測(cè)信息，具有不間斷的電源供應(yīng)，同時(shí)還具有一定的計(jì)算能力與存儲(chǔ)空間，以便執(zhí)行復(fù)雜的路由選擇算法；

(4)各個(gè)節(jié)點(diǎn)間傳遞信息的過(guò)程均遵循能量傳輸模型；

(5)所有節(jié)點(diǎn)可檢測(cè)本身的剩余能量，并擁有唯一標(biāo)識(shí)ID。

2.2 能量傳輸模型

本文采用文獻(xiàn)[11]提供的近似能量模型來(lái)估計(jì)信息傳遞過(guò)程中的能量消耗。節(jié)點(diǎn)能耗主要受數(shù)據(jù)包長(zhǎng)度、節(jié)點(diǎn)間距等主要因素的影響。假設(shè)在一個(gè)基本的無(wú)線信道中，發(fā)射機(jī)或接收機(jī)的能耗系數(shù)為Eelec,發(fā)射放大器的能耗系數(shù)為Eamp。通信能耗模型如圖1所示。

圖1 通信能耗模型

節(jié)點(diǎn)在工作時(shí)，信息收集、數(shù)據(jù)收發(fā)、熱量損耗等都會(huì)消耗能量，其中信息的傳輸所消耗的能量占據(jù)絕大多數(shù)。因此，在通信耗能模型中，只考慮通信過(guò)程中產(chǎn)生的能量損失。

通信過(guò)程中若將l比特?cái)?shù)據(jù)傳送至d米處，節(jié)點(diǎn)發(fā)送能耗為

ETx(l,d)=Eelec·l+Eamp·l·d2

(3)

節(jié)點(diǎn)接收能耗為

ERx(l)=Eelec·l

(4)

兩節(jié)點(diǎn)間的能耗總和為

E(X)=2Eelec·l+Eamp·l·d2

(5)

2.3 本文的改進(jìn)

如前所述，基于WSN的路由特性，新路徑的生成與和聲記憶庫(kù)的儲(chǔ)存形式都進(jìn)行了相應(yīng)的變化。為進(jìn)一步平衡網(wǎng)絡(luò)運(yùn)行過(guò)程中能量的分布問(wèn)題，本小節(jié)提出了一種側(cè)重網(wǎng)絡(luò)運(yùn)行后期能耗均衡的BTPHS算法。該算法主要有3點(diǎn)改進(jìn)策略：交叉變異、角度偏移方法及節(jié)點(diǎn)移除策略和分段式目標(biāo)函數(shù)。

2.3.1 交叉變異

為了使交叉變異操作更容易理解，本節(jié)給出如下定義：

在HM中存在兩條不同的路徑Xi、Xj，若兩個(gè)不同的無(wú)線傳感器節(jié)點(diǎn)u、v同時(shí)存在于Xi、Xj中，則稱節(jié)點(diǎn)u、v為一組扭轉(zhuǎn)節(jié)點(diǎn)。

HS算法執(zhí)行前期，搜索的范圍較廣，生成的路徑線路普遍偏長(zhǎng)，算法執(zhí)行時(shí)間必然增長(zhǎng)。這一改進(jìn)策略在現(xiàn)有優(yōu)秀和聲的基礎(chǔ)上進(jìn)一步生成新和聲，同時(shí)可以保證線路的多樣性。交叉變異環(huán)節(jié)交換HM中兩條已知線路的一部分，進(jìn)而生成兩條新的線路。具體而言，首先確定一組扭轉(zhuǎn)節(jié)點(diǎn)；接著在兩條線路中分別選定扭轉(zhuǎn)節(jié)點(diǎn)間的線路段；然后交換線路段組成新的路由線路。

從圖2中可以找到HM里存在的兩條線路

圖2 交叉變異過(guò)程

(6)

首先，確定一組扭節(jié)點(diǎn)(18,24)；選定兩條線路中扭轉(zhuǎn)節(jié)點(diǎn)間的路徑并進(jìn)行交換，得到兩條全新的路徑

(7)

由該操作產(chǎn)生的新路徑不僅兼顧到HM中和聲的優(yōu)異性，同時(shí)不再進(jìn)行算法的循環(huán)操作，縮短算法時(shí)間的同時(shí)，保障了新和聲的多樣性。

2.3.2 角度偏移方法和節(jié)點(diǎn)移除策略

節(jié)點(diǎn)部署后由自身的電池進(jìn)行供電，存在嚴(yán)格的電量約束，為此在路由算法設(shè)計(jì)時(shí)，需要平衡網(wǎng)絡(luò)的能耗需求。特別是在網(wǎng)絡(luò)運(yùn)行后期，關(guān)鍵節(jié)點(diǎn)不同于邊緣節(jié)點(diǎn)，參與多次的信息傳送任務(wù)，能量消耗較多。因此，BTPHS算法的主要思路是：提高循環(huán)后期邊緣節(jié)點(diǎn)的使用頻率，降低關(guān)鍵節(jié)點(diǎn)的曝光率。

文獻(xiàn)[12]提出了一種改進(jìn)算法，該算法在整個(gè)網(wǎng)絡(luò)的運(yùn)行階段中，下一跳節(jié)點(diǎn)的生成策略主要考慮了鄰居節(jié)點(diǎn)的剩余能量情況。因此，不均衡的能量分布僅僅體現(xiàn)在當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中，沒(méi)有更好地體現(xiàn)全局能量的分布特點(diǎn)。為了考慮到網(wǎng)絡(luò)整體能量的影響，BTPHS算法根據(jù)網(wǎng)絡(luò)中實(shí)時(shí)最小能量Emin的大小，將整個(gè)網(wǎng)絡(luò)的生命周期分為3個(gè)階段，每個(gè)階段在使用HS算法進(jìn)行下一跳節(jié)點(diǎn)選擇時(shí)，采取不同的節(jié)點(diǎn)選擇策略(網(wǎng)絡(luò)初始階段每個(gè)節(jié)點(diǎn)擁有的初始能量值均為E0)。

策略1：當(dāng)Emin的值介于[0.3E0,E0]時(shí)，整個(gè)網(wǎng)絡(luò)的能量較為均衡，處于網(wǎng)絡(luò)運(yùn)行前期階段，下一跳節(jié)點(diǎn)在選擇時(shí)，采用經(jīng)典的輪賭法進(jìn)行。輪盤(pán)構(gòu)成來(lái)源于鄰居節(jié)點(diǎn)當(dāng)前能量在總能量中的比例。在此階段，該策略可以迅速識(shí)別當(dāng)前網(wǎng)絡(luò)的主干道，便于后續(xù)的分支使用。

策略2：當(dāng)Emin的值介于[0.1E0,0.3E0]時(shí)，網(wǎng)絡(luò)中能量開(kāi)始出現(xiàn)一定程度的偏差，處于網(wǎng)絡(luò)運(yùn)行中期階段，下一跳節(jié)點(diǎn)在選擇時(shí)，采用角度偏移方法。利用角度偏移法選擇節(jié)點(diǎn)i的下一跳的具體步驟如下：

首先確定源節(jié)點(diǎn)s和sink節(jié)點(diǎn)d的具體坐標(biāo)(xs,ys)、(xd,yd)，并生成一個(gè)指向節(jié)點(diǎn)d的主干向量D，D計(jì)算規(guī)則如下

(8)

統(tǒng)計(jì)節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)的個(gè)數(shù)記作N0相應(yīng)的坐標(biāo)(xt,yt)，組成坐標(biāo)集；以節(jié)點(diǎn)i的坐標(biāo)(xi,yi)為始，依次計(jì)算指向坐標(biāo)Pt

Pt:((xt,xi),(yt,yi)),t=1,2,3,…,N0

(9)

計(jì)算N0個(gè)指向坐標(biāo)Pt與主干向量D之間的夾角θ，θ值的大小由其對(duì)應(yīng)的余弦函數(shù)值進(jìn)行控制，其計(jì)算規(guī)則如下

(10)

在系統(tǒng)模型的前提下，節(jié)點(diǎn)的分布具有隨機(jī)性，故θ值也是隨機(jī)的。余弦函數(shù)值的大小與偏離角度是一一對(duì)應(yīng)的關(guān)系，當(dāng)偏離角度超過(guò)90°時(shí)，余弦函數(shù)值會(huì)出現(xiàn)負(fù)數(shù)的情況，此時(shí)，信息可能會(huì)造成回傳的情況。因此，需要終止此次偏移。主干向量方向上的節(jié)點(diǎn)用于傳輸信息的頻率較高，剩余能量普遍較低。BTPHS算法通過(guò)控制θ值的大小，干預(yù)下一跳節(jié)點(diǎn)的選擇方向，在下一跳節(jié)點(diǎn)選取時(shí)，偏離主干向量方向，增加邊緣節(jié)點(diǎn)的曝光率和參與度。

策略3：當(dāng)Emin的值介于[0,0.1E0]時(shí)，網(wǎng)絡(luò)中能量差距已經(jīng)很大，處于網(wǎng)絡(luò)運(yùn)行后期階段，下一跳節(jié)點(diǎn)在選擇時(shí)采用節(jié)點(diǎn)移除策略。該策略的基本思想如下：

網(wǎng)絡(luò)的容錯(cuò)率在每一個(gè)時(shí)段都是不同的，并且每個(gè)階段都有可能因?yàn)樵u(píng)判機(jī)制的不同而造成更大的能量差距。網(wǎng)絡(luò)運(yùn)行的截止標(biāo)志為網(wǎng)絡(luò)中首次出現(xiàn)節(jié)點(diǎn)能量為0的時(shí)刻，因此，當(dāng)下一跳節(jié)點(diǎn)瀕臨死亡時(shí)，BTPHS算法進(jìn)行選擇性刪除。在下一輪選擇時(shí)，若節(jié)點(diǎn)p的當(dāng)前能量值低于0.1E0，本算法將節(jié)點(diǎn)p進(jìn)行暫時(shí)刪除，使其不進(jìn)入下一次的選擇范圍[13]。刪除節(jié)點(diǎn)的個(gè)數(shù)同樣需要限制，刪除節(jié)點(diǎn)過(guò)多，會(huì)導(dǎo)致出現(xiàn)信息無(wú)法傳輸?shù)侥康墓?jié)點(diǎn)，因此，刪除節(jié)點(diǎn)的總數(shù)不能超過(guò)0.2N。

2.3.3 分段式目標(biāo)函數(shù)

目標(biāo)函數(shù)是整個(gè)BTPHS算法的最終評(píng)判目標(biāo)，路徑選擇成功與否很大程度上取決于目標(biāo)函數(shù)的篩選過(guò)程。目標(biāo)函數(shù)在選擇時(shí)，需要衡量多個(gè)因素，來(lái)保證整個(gè)搜索過(guò)程向最優(yōu)解的方向逐步靠近[14]。列入衡量的因素包括：新路徑的長(zhǎng)度L(即信息傳遞過(guò)程中途徑節(jié)點(diǎn)的個(gè)數(shù))、路徑的節(jié)點(diǎn)平均剩余能量E(X)、全局最小能量Emin等。不僅如此，針對(duì)網(wǎng)絡(luò)中不同階段的能量分布特點(diǎn)，目標(biāo)函數(shù)也需要進(jìn)行相應(yīng)的變化，來(lái)保證整個(gè)網(wǎng)絡(luò)向良性方向發(fā)展。根據(jù)2.3.2節(jié)提到的3個(gè)節(jié)點(diǎn)選擇策略，BTPHS算法將目標(biāo)函數(shù)分為3個(gè)不同的部分進(jìn)行分段判別，如式(11)所示

(11)

在網(wǎng)絡(luò)運(yùn)行前期，BTPHS算法主要側(cè)重于生成路徑長(zhǎng)度短、能耗相對(duì)較少的路由路徑，盡快組成最優(yōu)和聲搜索庫(kù)；在網(wǎng)絡(luò)運(yùn)行中期，部分節(jié)點(diǎn)能量損耗較為嚴(yán)重，BTPHS算法在選擇線路時(shí)，開(kāi)始有意識(shí)地避開(kāi)這些節(jié)點(diǎn)，生成的線路不再刻意要求長(zhǎng)度最短，但依舊要保證整體網(wǎng)絡(luò)的能耗水平較低；在網(wǎng)絡(luò)運(yùn)行后期，個(gè)別節(jié)點(diǎn)已經(jīng)處在能量耗盡的邊緣，生成新路徑的過(guò)程中，這些節(jié)點(diǎn)已經(jīng)被視為死亡節(jié)點(diǎn)，新路徑的長(zhǎng)度必然會(huì)增加，此時(shí)，BTPHS算法再衡量新路徑標(biāo)準(zhǔn)時(shí)，不再考慮路徑長(zhǎng)度L的因素。顯然，根據(jù)式(11)表述的數(shù)學(xué)意義，路徑長(zhǎng)度越短、路徑平均剩余能量和網(wǎng)絡(luò)最小剩余能量越大，目標(biāo)函數(shù)值越大，符合這些特征的路由方案越容易保留下來(lái)。

綜上，BTPHS算法的算法流程如下：

BTPHS算法：

輸入：節(jié)點(diǎn)分布坐標(biāo)及能量信息

源節(jié)點(diǎn)s

目的節(jié)點(diǎn)d

輸出：當(dāng)前最優(yōu)路徑R

初始化：HM HMCR R rand Tmax

(1)fort=1,2,3,…,Tmaxdo

(2)while路由線路未達(dá)到d

(3)ifrand

(4)then下一跳節(jié)點(diǎn)從HM中選取

(5)else下一跳節(jié)點(diǎn)從鄰居節(jié)點(diǎn)中選取

(6)endif

(7)ifEmin>0.3E0

(8) 下一跳采用輪賭法進(jìn)行選取

(9)elseifEmin>0.1E0

(10) 下一跳采用角度偏倚法進(jìn)行選取

(11)else下一跳采用節(jié)點(diǎn)去除法進(jìn)行選取

(12)endif

(13)endwhile

(14)if新路徑Routing優(yōu)于HM中的任意一條

(15) 更新HM

(16)endif

(17)endfor

(18)R←Routing

(19)ReturnR

3 實(shí)驗(yàn)部分

本節(jié)給出了BTPHS算法的仿真實(shí)驗(yàn)結(jié)果。仿真軟件使用Matlab 2018a，運(yùn)行設(shè)備為Mac mini 2014，2.6 GHz Intel Core i5，內(nèi)存為8 G。根據(jù)有效通訊半徑，隨機(jī)生成8個(gè)不同的節(jié)點(diǎn)分布場(chǎng)景。場(chǎng)景中的節(jié)點(diǎn)數(shù)量從10個(gè)依次遞增至80個(gè)，增量為10個(gè)節(jié)點(diǎn)。為驗(yàn)證BTPHS算法的可行性，實(shí)驗(yàn)部分引入兩種同樣基于和聲搜索算法的對(duì)比算法EEHSBR、IHSBEER進(jìn)行比較。對(duì)于每個(gè)實(shí)驗(yàn)場(chǎng)景，測(cè)試環(huán)節(jié)均使用兩個(gè)指標(biāo)來(lái)評(píng)價(jià)算法的表現(xiàn)：網(wǎng)絡(luò)壽命(即網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡時(shí)發(fā)送信息的輪數(shù))和平均剩余能量(網(wǎng)絡(luò)中所有節(jié)點(diǎn)能量的平均值)。

為了更加全面驗(yàn)證BTPHS算法的可行性，在數(shù)據(jù)傳輸環(huán)節(jié)，本文模擬設(shè)計(jì)了兩種不同的發(fā)送形式：固定節(jié)點(diǎn)持續(xù)發(fā)送和全節(jié)點(diǎn)循環(huán)發(fā)送。

固定節(jié)點(diǎn)持續(xù)發(fā)送：所有傳感器節(jié)點(diǎn)擁有相同的初始能量，數(shù)據(jù)包均從某一固定節(jié)點(diǎn)發(fā)送至sink節(jié)點(diǎn)。

全節(jié)點(diǎn)循環(huán)發(fā)送：所有傳感器節(jié)點(diǎn)擁有相同的初始能量，每個(gè)傳感器節(jié)點(diǎn)定期向sink節(jié)點(diǎn)發(fā)送數(shù)據(jù)包。

相關(guān)參數(shù)見(jiàn)表1。實(shí)驗(yàn)結(jié)果均為模擬進(jìn)行20次得到的平均值。

表1 參數(shù)設(shè)置

3.1 節(jié)點(diǎn)調(diào)度測(cè)試

本節(jié)實(shí)驗(yàn)測(cè)試的內(nèi)容主要針對(duì)2.3.2節(jié)所提出的角度偏移及節(jié)點(diǎn)移除策略。在8個(gè)不同的節(jié)點(diǎn)分布場(chǎng)景中，測(cè)試算法在全節(jié)點(diǎn)循環(huán)發(fā)送過(guò)程中節(jié)點(diǎn)的活躍程度。節(jié)點(diǎn)活躍度反映了節(jié)點(diǎn)在WSN中的使用頻率，界定標(biāo)準(zhǔn)采用當(dāng)前節(jié)點(diǎn)的剩余能量值。剩余能量越低，節(jié)點(diǎn)在網(wǎng)絡(luò)使用過(guò)程中消耗的能量越多，該節(jié)點(diǎn)的頻率越高，即節(jié)點(diǎn)的活躍度越高。本文選定3個(gè)不同的剩余能量閾值進(jìn)行3組對(duì)比實(shí)驗(yàn)，測(cè)試條件如下：

測(cè)試A：網(wǎng)絡(luò)死亡時(shí)，剩余能量不足E0的；

測(cè)試B：網(wǎng)絡(luò)死亡時(shí)，剩余能量不足0.9E0的；

測(cè)試C：網(wǎng)絡(luò)死亡時(shí)，剩余能量不足0.8E0的。

結(jié)果如圖3～圖5所示。角度偏移及節(jié)點(diǎn)移除策略的主要目的是盡可能多地利用邊緣節(jié)點(diǎn)進(jìn)行傳輸。在WSN中，信息傳遞主要依賴于主干道上的節(jié)點(diǎn)，考慮到傳播時(shí)效，生存成本等因素，邊緣節(jié)點(diǎn)的使用很難完全替代主干道上的傳感器節(jié)點(diǎn)。測(cè)試A表示在整個(gè)網(wǎng)絡(luò)生存過(guò)程中，所有參與節(jié)點(diǎn)的個(gè)數(shù)情況，此時(shí)只要節(jié)點(diǎn)參與傳輸信息，即被統(tǒng)計(jì)在內(nèi)。

圖3 測(cè)試A下的節(jié)點(diǎn)活躍度

圖4 測(cè)試B下的節(jié)點(diǎn)活躍度

圖5 測(cè)試C下的節(jié)點(diǎn)活躍度

圖3可以看出，3種算法在節(jié)點(diǎn)數(shù)較少的環(huán)境下表現(xiàn)基本持平，當(dāng)環(huán)境中的節(jié)點(diǎn)個(gè)數(shù)增多時(shí)，BTPHS算法調(diào)動(dòng)的節(jié)點(diǎn)明顯增多。

圖4和圖5可看作邊緣節(jié)點(diǎn)的輕度、中度使用行為。剩余能量可以快速衡量出節(jié)點(diǎn)是否多次參與網(wǎng)絡(luò)傳輸，剩余能量閾值降低，篩選出的節(jié)點(diǎn)活躍度越高。兩種情況下BTPHS算法的表現(xiàn)均優(yōu)于EEHSBE算法和IHSBEER算法，這是因?yàn)?.3.2節(jié)提出的改進(jìn)策略在生成信息傳遞路徑時(shí)，下一跳節(jié)點(diǎn)的選擇為邊緣節(jié)點(diǎn)提供了更多的可能性，增大的邊緣節(jié)點(diǎn)的曝光率。圖3～圖5顯示的3組實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證了角度偏移及節(jié)點(diǎn)移除策略的可行性。

3.2 固定節(jié)點(diǎn)持續(xù)發(fā)送下的實(shí)驗(yàn)結(jié)果

圖6和圖7分別顯示了兩個(gè)指標(biāo)在8個(gè)實(shí)驗(yàn)環(huán)境中的對(duì)比情況。兩幅實(shí)驗(yàn)對(duì)比圖中的橫軸表示不同規(guī)模場(chǎng)景下的傳感器節(jié)點(diǎn)個(gè)數(shù)，圖6的縱軸表示網(wǎng)絡(luò)的生命周期(當(dāng)出現(xiàn)能量黑洞時(shí)，網(wǎng)絡(luò)一共循環(huán)的信息傳遞輪數(shù))，圖7的縱軸表示平均剩余能量。

圖6 網(wǎng)絡(luò)壽命對(duì)比

圖7 平均剩余能量對(duì)比

從圖6的結(jié)果可以看出，BTPHS算法在部分場(chǎng)景中體現(xiàn)出了最好的結(jié)果，特別是在節(jié)點(diǎn)數(shù)目較大的環(huán)境中。WSN范圍內(nèi)節(jié)點(diǎn)數(shù)目越多意味著節(jié)點(diǎn)間的路由關(guān)系更復(fù)雜，每個(gè)節(jié)點(diǎn)鄰居路由的數(shù)量也會(huì)相應(yīng)更多。因此，在網(wǎng)絡(luò)循環(huán)的后期，WSN網(wǎng)絡(luò)的抗風(fēng)險(xiǎn)性就會(huì)越大，人為刪除疑似死亡節(jié)點(diǎn)后，網(wǎng)絡(luò)依舊可以生成可行的路由方案，進(jìn)一步延長(zhǎng)網(wǎng)絡(luò)的使用時(shí)間。

對(duì)比圖7可以看到，基于和聲搜索的3種不同的算法在剩余能量的控制上差別不是很大，從這一點(diǎn)可以得出，和聲搜索算法適于解決NP-hard問(wèn)題。剩余能量相差不大表明，在該環(huán)境下，3種算法生成的路由方案在總體能耗表現(xiàn)上較為平衡。較高的能量剩余意味著較低的能量成本，IHSBEER算法的優(yōu)化，降低了網(wǎng)絡(luò)工作期間的平均能量算耗。BTPHS算法著重使用邊緣節(jié)點(diǎn)，在算法循環(huán)后期，犧牲路徑長(zhǎng)度，提高邊緣節(jié)點(diǎn)的曝光率，路徑總能耗隨即增加，符合算法最初的設(shè)計(jì)邏輯。故在平均剩余能量表現(xiàn)方面，BTPHS算法在大部分的實(shí)驗(yàn)場(chǎng)景中，均略低于IHSBEER算法，這一現(xiàn)象表明，BTPHS算法在均衡能量方面表現(xiàn)更為優(yōu)秀，在現(xiàn)有能量環(huán)境下，可以更多利用曝光率低的節(jié)點(diǎn)進(jìn)行工作。

3.3 全節(jié)點(diǎn)循環(huán)發(fā)送下的實(shí)驗(yàn)結(jié)果

圖8和圖9分別顯示了兩個(gè)指標(biāo)在8個(gè)實(shí)驗(yàn)環(huán)境中的對(duì)比情況。

圖8 網(wǎng)絡(luò)壽命對(duì)比

圖9 平均剩余能量對(duì)比

從圖8中可以觀察到，在8種不同的節(jié)點(diǎn)分布環(huán)境下，BTPHS算法的表現(xiàn)依舊突出。節(jié)點(diǎn)分布范圍更大，節(jié)點(diǎn)總數(shù)更多，但單位面積內(nèi)節(jié)點(diǎn)的分布密度卻變小。從測(cè)試數(shù)據(jù)可以看出，BTPHS算法獲得的輪數(shù)有著顯著提升，特別是在50節(jié)點(diǎn)的測(cè)試環(huán)境中，相比EEHSBR算法提升12.9%，相比IHSBEER算法提升5.52%。BTPHS算法中的交叉變異環(huán)節(jié)，可以在網(wǎng)絡(luò)運(yùn)行后期，通過(guò)扭轉(zhuǎn)節(jié)點(diǎn)對(duì)路徑的切割與拼接，實(shí)現(xiàn)路徑的大范圍變化，從而有效避免瀕臨死亡節(jié)點(diǎn)的利用。圖9顯示的測(cè)試結(jié)果大體與固定節(jié)點(diǎn)持續(xù)發(fā)送橫式下的實(shí)驗(yàn)數(shù)據(jù)相似。

隨著網(wǎng)絡(luò)面積增大，節(jié)點(diǎn)密度降低，BTPHS算法向sink節(jié)點(diǎn)傳輸相同大小的數(shù)據(jù)包時(shí)，消耗的能量偏多，維持的輪數(shù)相比其它算法有進(jìn)一步的提升，這一測(cè)試結(jié)果驗(yàn)證了BTPHS算法的可行性。

3.4 結(jié) 論

從兩種測(cè)試環(huán)境的對(duì)比情況可以看到，BTPHS算法在節(jié)點(diǎn)較多的環(huán)境中，表現(xiàn)尤為突出。在能耗損失方面略輸于EEHSBR算法和IHSBEER算法，與此同時(shí)，由于角度偏移方法和節(jié)點(diǎn)移除策略的引入，使得邊緣節(jié)點(diǎn)進(jìn)入路由方案的概率有所提升，進(jìn)一步分擔(dān)主干路上節(jié)點(diǎn)的使用頻率。目標(biāo)函數(shù)從單一的評(píng)判標(biāo)準(zhǔn)更新為三段式評(píng)判，保證BTPHS算法在不同階段選擇出當(dāng)下最優(yōu)的轉(zhuǎn)發(fā)路徑。在保持網(wǎng)絡(luò)能量效率的前提下，可以提高網(wǎng)絡(luò)的可拓展性。對(duì)于當(dāng)前的大多數(shù)應(yīng)用，如智能家居、工業(yè)和制造自動(dòng)化等，節(jié)點(diǎn)的數(shù)量較為中等，結(jié)合Matlab的仿真結(jié)果可以得出，BTPHS算法在路由選擇領(lǐng)域有廣泛的發(fā)展前景。

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

本文提出了一種基于和聲搜索的能量路由算法BTPHS，該算法以HS算法為基礎(chǔ)，生成新的路由方案，并根據(jù)目標(biāo)函數(shù)不斷優(yōu)化和聲庫(kù)中的路由路線，從而不斷產(chǎn)生最優(yōu)解。該算法主要思想是提高邊緣節(jié)點(diǎn)的參與度，通過(guò)角度偏移方法和節(jié)點(diǎn)移除策略不斷降低主干道節(jié)點(diǎn)的使用頻率。經(jīng)檢測(cè)BTPHS算法生成路由方案，可以進(jìn)一步平衡能量分布情況，還能一定程度上延長(zhǎng)的網(wǎng)絡(luò)的使用周期。但BTPHS算法在運(yùn)行時(shí)長(zhǎng)上依舊有提升的空間，同時(shí)，節(jié)點(diǎn)移除策略的引入，使得網(wǎng)絡(luò)可能造成回路、短路現(xiàn)象，后續(xù)還需要進(jìn)一步完善。