李 明，胡江平，曹曉莉

(1. 電子科技大學(xué)自動(dòng)化工程學(xué)院 成都 611731；2. 重慶工商大學(xué)人工智能學(xué)院 重慶 南岸區(qū) 400067)

近年來，無線視頻傳感器(其感知具有方向性，隸屬于有向傳感器)逐漸取代有線視頻監(jiān)控傳感器，其安裝簡便，價(jià)格便宜，應(yīng)用場景不斷拓展。傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋調(diào)度對(duì)于網(wǎng)絡(luò)同步與分布式優(yōu)化起著重要作用[1-4]。在滿足監(jiān)測目標(biāo)監(jiān)測覆蓋的要求下，如何借助節(jié)點(diǎn)調(diào)度算法延長有向傳感器網(wǎng)絡(luò)的工作時(shí)間是有向傳感器網(wǎng)絡(luò)的重要研究內(nèi)容。文獻(xiàn)[5]提出一種基于概率覆蓋圓的連通有向傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋增強(qiáng)算法。文獻(xiàn)[6]提出了一種面向有向傳感器網(wǎng)絡(luò)的基于遺傳算法的k覆蓋算法，通過求解多個(gè)滿足目標(biāo)k覆蓋要求且節(jié)點(diǎn)數(shù)量最少的集合延長網(wǎng)絡(luò)的壽命。文獻(xiàn)[7]通過建立一種混合二進(jìn)制整數(shù)線性規(guī)劃模型，求解得到多個(gè)互不相交的覆蓋集合來延長有向傳感器網(wǎng)絡(luò)的壽命。這些研究都是假設(shè)參與節(jié)點(diǎn)調(diào)度的傳感器節(jié)點(diǎn)參數(shù)相同，未考慮異構(gòu)節(jié)點(diǎn)對(duì)調(diào)度算法的影響。同時(shí)，均假定監(jiān)測目標(biāo)在區(qū)域內(nèi)均勻分布，未考慮監(jiān)測目標(biāo)的重要性、出現(xiàn)頻率對(duì)網(wǎng)絡(luò)服務(wù)質(zhì)量的影響。對(duì)于異構(gòu)有向傳感器網(wǎng)絡(luò)，文獻(xiàn)[8]提出兩種啟發(fā)式算法解決有向傳感器網(wǎng)絡(luò)的壽命最大化問題，兩種算法的區(qū)別在于每次選取節(jié)點(diǎn)感知方向的標(biāo)準(zhǔn)不同。一種為每次選取對(duì)目標(biāo)覆蓋貢獻(xiàn)最大(也就是覆蓋最多目標(biāo))的感知方向，另一種為每次選擇能覆蓋監(jiān)測目標(biāo)且能量最少的感知方向，兩種算法結(jié)束的條件均為直到所有的目標(biāo)滿足覆蓋要求。文獻(xiàn)[9]提出一種基于學(xué)習(xí)自動(dòng)機(jī)的算法解決感知半徑可調(diào)的有向傳感器網(wǎng)絡(luò)的k-覆蓋問題。文獻(xiàn)[10]提出一種基于遺傳算法的壽命最大化策略來延長半徑可調(diào)的有向傳感器網(wǎng)絡(luò)的壽命。針對(duì)異構(gòu)有向傳感器網(wǎng)絡(luò)的壽命優(yōu)化問題，利用集合覆蓋的思想，文獻(xiàn)[11]通過改進(jìn)的和聲搜索算法求解滿足目標(biāo)覆蓋要求的集合，解決差異化覆蓋條件下異構(gòu)有向傳感網(wǎng)絡(luò)壽命的問題。文獻(xiàn)[12]將學(xué)習(xí)自動(dòng)機(jī)引入差分進(jìn)化算法，實(shí)現(xiàn)算法參數(shù)的自適應(yīng)并增強(qiáng)算法的優(yōu)化能力，使壽命達(dá)到最大化。但這些文獻(xiàn)沒有考慮網(wǎng)絡(luò)的連通性，使得算法在工程實(shí)踐中受到影響。盡管文獻(xiàn)[13-14]對(duì)差異化覆蓋連通問題進(jìn)行了研究，但其研究對(duì)象為全向感知和節(jié)點(diǎn)同構(gòu)的傳感器網(wǎng)絡(luò)，研究成果不適用于感知模型為有向的異構(gòu)有向傳感器網(wǎng)絡(luò)。

針對(duì)上述研究中存在的問題，在滿足應(yīng)用場景監(jiān)測目標(biāo)覆蓋要求差異化和網(wǎng)絡(luò)連通的條件下，本文提出一種面向異構(gòu)有向傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)調(diào)度算法，達(dá)到降低網(wǎng)絡(luò)能耗和延長網(wǎng)絡(luò)工作時(shí)長的目標(biāo)。

1 問題描述及數(shù)學(xué)建模

在二維監(jiān)測區(qū)域中隨機(jī)部署N個(gè)不同的感知半徑ri、通信半徑ci、攜帶能量Ei、感知角度 θi的傳感器節(jié)點(diǎn)si(i=1,2,···,N)，用于監(jiān)測W個(gè)目標(biāo)。由節(jié)點(diǎn)的感知角度得出可用的感知方向?yàn)?，本文假定?jié)點(diǎn)的感知方向不重疊，在工作狀態(tài)時(shí)傳感器節(jié)點(diǎn)消耗的能量ei不同，非工作狀態(tài)時(shí)節(jié)點(diǎn)不消耗能量，則可得出節(jié)點(diǎn)的壽命為Li=Ei/ei。根據(jù)監(jiān)測目標(biāo)出現(xiàn)的頻率將其分為重點(diǎn)目標(biāo)(出現(xiàn)頻率高)和非重點(diǎn)目標(biāo)。為保證網(wǎng)絡(luò)服務(wù)質(zhì)量和網(wǎng)絡(luò)可靠性，要求至少兩個(gè)傳感器節(jié)點(diǎn)對(duì)對(duì)重點(diǎn)目標(biāo)進(jìn)行監(jiān)測，其他目標(biāo)只要能監(jiān)測到就符合應(yīng)用需求。

定義傳感網(wǎng)絡(luò)的壽命[12]網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)能提供符合監(jiān)測目標(biāo)的監(jiān)測要求且能保持網(wǎng)絡(luò)連通的時(shí)間。

在滿足監(jiān)測目標(biāo)的監(jiān)測覆蓋需求和保持網(wǎng)絡(luò)連通的前提下，如何延長傳感網(wǎng)絡(luò)的壽命是本文要解決的問題。其形式化的描述為：

除了增加式(5)的連通要求，該數(shù)學(xué)模型與文獻(xiàn)[11]相同。式中，K表示滿足覆蓋連通要求的集合數(shù)；tk為第k個(gè)覆蓋連通集的工作時(shí)長，其大小由集合中能量最小的節(jié)點(diǎn)決定；Di,j為 節(jié)點(diǎn)si的第j個(gè)感知方向；Ck為第k個(gè)符合連通覆蓋要求的節(jié)點(diǎn)集合；C_Tk,m表 示在Ck中能覆蓋監(jiān)測目標(biāo)Tm的感知方向的集合； Req(Tm)表 示監(jiān)測目標(biāo)Tm要求同時(shí)被多少個(gè)傳感器節(jié)點(diǎn)監(jiān)測，取值為正整數(shù)，由目標(biāo)本身的特性或出現(xiàn)的區(qū)域決定。采用文獻(xiàn)[15]中的有邊界的帕累托分布模擬目標(biāo)在某一時(shí)間段內(nèi)的出現(xiàn)情況，其參數(shù)取值與文獻(xiàn)[15]相同，仿真結(jié)果如圖1 所示。其中，“□”目標(biāo)出現(xiàn)頻繁的區(qū)域?yàn)橹攸c(diǎn)區(qū)域，對(duì)于這些區(qū)域的監(jiān)測目標(biāo)要求Req(Tm)≥2， 其他區(qū)域 Req(Tm)=1即可。式(2)對(duì)節(jié)點(diǎn)的能量進(jìn)行約束，使得其工作時(shí)消耗的總能量不超過其攜帶的總能量。式(3)表示傳感器節(jié)點(diǎn)在工作狀態(tài)時(shí)只能有一個(gè)感知方向。式(4)表示由傳感器節(jié)點(diǎn)構(gòu)成的集合能滿足所有監(jiān)測目標(biāo)要求。式(5)保證傳感器節(jié)點(diǎn)之間是相互連通的，本文假定傳感器節(jié)點(diǎn)在其通信半徑內(nèi)有其他節(jié)點(diǎn)存在時(shí)則該節(jié)點(diǎn)連通的。

圖1 監(jiān)測目標(biāo)出現(xiàn)區(qū)域示意圖

考慮到集合覆蓋問題為NP-hard 問題[11]，本文利用珊瑚礁算法進(jìn)行求解。

2 連通覆蓋調(diào)度算法

2.1 原始珊瑚礁優(yōu)化算法

珊瑚礁算法[16]是一種模擬珊瑚蟲行為的智能進(jìn)化算法，已用于求解農(nóng)場風(fēng)力資源優(yōu)化、有向傳感器網(wǎng)絡(luò)資源優(yōu)化[17]等組合優(yōu)化問題。該算法的步驟為：初始化、繁殖過程、競爭過程和淘汰過程。其中，種群初始化實(shí)現(xiàn)算法參數(shù)的初始化，包括：珊瑚礁的面積(通常為W×L矩形)、珊瑚礁中存在珊瑚蟲的比例pro、迭代數(shù)I_MAX、非性繁殖(即雌雄同體)的比重Fa、迭代過程中子代尋找珊瑚礁附著時(shí)允許嘗試的最大次數(shù)T_MAX、珊瑚蟲被淘汰的概率pro_coral 和被淘汰珊瑚蟲與珊瑚蟲總數(shù)的比重pro_no。珊瑚蟲的繁殖行為包括：非性繁殖行為(其比例占所有繁殖行為的比例為Fa)和在符合要求范圍內(nèi)隨機(jī)產(chǎn)生子代和有性繁殖行為(其比例占所有繁殖行為的比例為Fb)。珊瑚蟲競爭珊瑚礁的過程，也就是珊瑚蟲尋找可附著珊瑚礁的過程。若該珊瑚礁上沒有其他珊瑚蟲，則珊瑚蟲直接可占據(jù)此珊瑚礁；否則，需要進(jìn)行珊瑚蟲適應(yīng)度大小的比較，根據(jù)比較結(jié)果擇優(yōu)附著在珊瑚礁上。若競爭失敗，可嘗試占據(jù)其他珊瑚礁，若達(dá)到最大嘗試次數(shù)仍未找到可附著的珊瑚礁，則該珊瑚蟲死亡。在淘汰過程中，依據(jù)適應(yīng)度排序，對(duì)珊瑚蟲進(jìn)行淘汰操作。淘汰后的珊瑚蟲其附著的珊瑚礁隨之被空出，以備后續(xù)珊瑚蟲使用。

2.2 增強(qiáng)的珊瑚礁算法

1) 種群初始化策略的改進(jìn)

種群初始化后產(chǎn)生的初始解對(duì)算法的優(yōu)化能力具有非常重要的影響。為了使初始解均勻分布，將種群數(shù)均勻分為兩部分，每一部分采用不同的初始化策略。第一部分種群使用低差異的SOBOL 序列產(chǎn)生，使得初始解更均勻的分布在多維超體中[18]。其數(shù)學(xué)表達(dá)式為：

式中，變量L和H分別表示解允許取值范圍的最小值和最大值；S為SOBOL 序列產(chǎn)生的[0,1]的隨機(jī)數(shù)。

第二部分種群使用反向?qū)W習(xí)產(chǎn)生，先隨機(jī)產(chǎn)生種群中每個(gè)染色體的初始值P=(p1,p2,···,pn),pi∈[L,H]，每個(gè)染色體的基因?yàn)椋?/p>

2)非性繁殖過程的改進(jìn)

CRO 算法中的非性繁殖過程是隨機(jī)產(chǎn)生的，這種操作不利于繼承種群中的較優(yōu)解。為保存非性繁殖過程中的優(yōu)秀解，借鑒生物地理學(xué)算法[19]、和聲搜索算法[20]和差分進(jìn)化算法[12]對(duì)其進(jìn)行改進(jìn)。具體為，子代個(gè)體中每一維的來源有3 種可能：① 直接來自父代的概率為1 ?λi，為避免繼承較差的基因，以概率PAR[20]對(duì)其進(jìn)行隨機(jī)擾動(dòng)；② 在可行區(qū)域內(nèi)隨機(jī)產(chǎn)生，其概率為 λi(1?cr?1/D)，cr為差分進(jìn)化算法中的交叉概率，本文取0.9[12]。③ 剩余的 λi(cr+1/D)的概率來自非性繁殖父代個(gè)體之間的差分變異操作。變量 λi為生物地理學(xué)算法的參數(shù)，為解的第i維遷移率[19]，λi=i/D，參數(shù)D是解的維數(shù)；PAR 為來自和聲搜索算法的參數(shù)，采用文獻(xiàn)[20]自適應(yīng)縮放因子，即：

式中，k為當(dāng)前的迭代次數(shù)；K為最大迭代次數(shù)；PARmax=0.8； PARmin=0.8[20]。

差分變異操作中差分變異策略和控制參數(shù)對(duì)算法的性能有重要影響。為增強(qiáng)算法性能，采用自適應(yīng)變異策略和設(shè)置控制參數(shù)，變異策略為：

式中，r1，r2，r3，r4，r5 為種群中不同于i的個(gè)體；為迭代次數(shù)為t時(shí)種群中適應(yīng)度最好的個(gè)體；表 示個(gè)體的適應(yīng)度；favg(Xt)表示迭代次數(shù)為t時(shí)種群的平均適應(yīng)度。

采用自適應(yīng)的參數(shù)選擇策略，具體為：

式中，F(xiàn)min和Fmax分別表示F的最小值和最大值。當(dāng)種群個(gè)體有早熟的趨勢(shì)時(shí)，采用較大的F值進(jìn)行抑制，保持種群的多樣性；反之，當(dāng)種群個(gè)體收斂較慢時(shí)，采用較小的F值加快種群的收斂；其他情況下，產(chǎn)生隨機(jī)的F。

3)混合策略提升種群中的最差個(gè)體

在競爭和淘汰過程之間增加最差個(gè)體提升過程，通過兩種方法改善其優(yōu)化能力，并通過適應(yīng)度評(píng)價(jià)選擇兩種方法中改善效果最顯著的作為其最終的結(jié)果。如式(8)的反向?qū)W習(xí)操作和式(9)的差分操作：

式中，變量L和H分別表示解的最小值和最大值；函數(shù)rand()為產(chǎn)生0～1 的隨機(jī)數(shù)；和分別為循環(huán)次數(shù)為t時(shí)種群中適應(yīng)度最差和最好的個(gè)體；F為差分參數(shù)，在區(qū)間[0.1, 0.9]隨機(jī)取值。通過適應(yīng)度評(píng)價(jià)，選擇式(8)和式(9)中表現(xiàn)較好的作為最差個(gè)體新的解，可使其跳出其目前所處最差區(qū)域，增強(qiáng)其優(yōu)化能力。

2.3 壽命最大化問題的求解

通過求解盡可能多滿足覆蓋連通要求的集合，達(dá)到延長網(wǎng)絡(luò)壽命的目的。每次循環(huán)完畢后，珊瑚礁算法輸出種群中的最優(yōu)解，執(zhí)行節(jié)點(diǎn)能量的更新，反復(fù)迭代，直到滿足算法終止的條件。其中要解決解質(zhì)量的評(píng)價(jià)和如何表示解這兩個(gè)關(guān)鍵問題。

1) 解質(zhì)量的評(píng)價(jià)

對(duì)于珊瑚礁算法而言，解質(zhì)量的評(píng)價(jià)也就是設(shè)計(jì)健康度函數(shù)。針對(duì)解決問題的特點(diǎn)，設(shè)計(jì)了3 個(gè)優(yōu)化目標(biāo)：① 形成盡可能多的滿足監(jiān)測要求的集合；② 形成滿足要求的集合后，節(jié)點(diǎn)的剩余能量最多；③ 最后一個(gè)是要求集合中節(jié)點(diǎn)的連通度越高越好。用形式化的語言描述為：

式中，W′表示符合監(jiān)測覆蓋要求的監(jiān)測目標(biāo)數(shù)量；W表示監(jiān)測目標(biāo)的數(shù)量；f1的值域?yàn)閇0,1]；f2是用雙曲正切函數(shù)表示的剩余能量的函數(shù)，取值范圍為[0,1]；β 是權(quán)重系數(shù)，在文中設(shè)為1；f3值域?yàn)閇0,1]。

利用隨機(jī)線性加權(quán)的方法[21]將多目標(biāo)優(yōu)化問題變成單目標(biāo)優(yōu)化問題，即：

式中， γ1、 γ2和 γ3為f1、f2和f3對(duì) 應(yīng)的系數(shù)； r andi為區(qū)間(0,1)之間的隨機(jī)數(shù)。

2) 解的表示

考慮到求解問題的特點(diǎn)，對(duì)節(jié)點(diǎn)和感知方向進(jìn)行整數(shù)編號(hào)，根據(jù)該編號(hào)能確定屬于節(jié)點(diǎn)的感知方向，如圖2 所示。

圖2 解的示意圖

圖中解的每個(gè)位置ti的含義如式(11)所述，其中 |Di|為 有向傳感器節(jié)點(diǎn)si感知方向的數(shù)量。由于節(jié)點(diǎn)冗余性和特定節(jié)點(diǎn)的某個(gè)感知方向可覆蓋多個(gè)監(jiān)測目標(biāo)，可能出現(xiàn)解的某個(gè)位置的值為0 的情況。

2.4 ECRO 算法時(shí)間復(fù)雜度分析

結(jié)合上述分析，ECRO 算法的總的時(shí)間復(fù)雜度是上述所有過程時(shí)間復(fù)雜度的總和，即TC= TC1+TC2+ TC3+ TC4+ TC5+ TC6

3 實(shí)驗(yàn)與分析

本節(jié)首先測試增強(qiáng)珊瑚礁算法ECRO在數(shù)值計(jì)算上的性能，然后將其用于解決異構(gòu)有向傳感器網(wǎng)絡(luò)壽命最大化的問題。

3.1 數(shù)值運(yùn)算

在表1 的4 個(gè)測試函數(shù)上測試各算法的性能。將遺傳算法(genetic algorithm, GA)、模擬退火算法(simulating algorithm, SA)、原始差分進(jìn)化算法(differential evolution, DE)、文獻(xiàn)[11]中的改進(jìn)和聲搜索算法(enhanced harmony search, EHS)和文獻(xiàn)[12]中的基于學(xué)習(xí)自動(dòng)機(jī)的差分進(jìn)化算法(learning automata differential evolution, LADE)作 為對(duì)比算法參與數(shù)值運(yùn)算。函數(shù)的具體信息詳見表1 所示。

表1 測試函數(shù)具體信息

CRO 算法中W×L設(shè)為10×5，其他參數(shù)Fb、Fa、pro、T_MAX、pro_coral 和pro_no 分別設(shè)為0.9,0.1,0.7,3,0.1 和 0.01[16]； ECRO 算 法 中Fmin=0.1，F(xiàn)max=0.9[22]，維數(shù)n為30，其他參數(shù)的值與文獻(xiàn)[12]取值相同。算法結(jié)果為程序運(yùn)行30 次所得結(jié)果的平均值。從表2 的求解結(jié)果可以得出：在F3 函數(shù)中，所有參與測試的算法均取得全局優(yōu)化解0；除此之外的數(shù)值測試結(jié)果顯示，相比較于其他算法，ECRO 算法求解結(jié)果最優(yōu)。數(shù)值計(jì)算結(jié)果表明，與其他算法比較，本文提出的ECRO 算法性能最佳，證明了算法的有效性。

表2 結(jié)果比較

3.2 覆蓋調(diào)度算法性能比較

3.2.1 仿真環(huán)境配置

覆蓋調(diào)度算法的仿真平臺(tái)為MATLAB 2013。監(jiān)測區(qū)域大小為50 m×50 m，節(jié)點(diǎn)數(shù)量N為30，每個(gè)連通覆蓋集合工作時(shí)間wt=1s，節(jié)點(diǎn)可選的感知方向?yàn)?|Di|=，且感知方向之間無重疊區(qū)域，其中 θi表 示感知角度 θi。節(jié)點(diǎn)信息如表3 所示。監(jiān)測目標(biāo)隨機(jī)分布在監(jiān)測區(qū)域內(nèi)，其數(shù)量W=6。若某一監(jiān)測目標(biāo)在某個(gè)監(jiān)測周期里出現(xiàn)頻率較高，則認(rèn)定為重點(diǎn)監(jiān)測目標(biāo)，此類監(jiān)測目標(biāo)要求被兩個(gè)傳感器節(jié)點(diǎn)監(jiān)測到，其余監(jiān)測目標(biāo)被1 個(gè)傳感器節(jié)點(diǎn)監(jiān)測到即可，每種類型的監(jiān)測目標(biāo)數(shù)量隨機(jī)產(chǎn)生。

表3 節(jié)點(diǎn)參數(shù)表

為更好地衡量改進(jìn)算法ECRO 的性能，本文提出一種貪婪算法(以下簡稱Greedy)作為對(duì)照算法。其求解步驟為，每一輪選擇的感知方向，為以下3 個(gè)指標(biāo)乘積的最大值：1)該感知方向所在節(jié)點(diǎn)的剩余能量；2)該感知方向監(jiān)測目標(biāo)數(shù)量；3)該感知方向與其他已選擇節(jié)點(diǎn)的連通性(式(5)不等號(hào)左端的值)。選擇感知方向的操作會(huì)一直進(jìn)行，直到所有監(jiān)測目標(biāo)的監(jiān)測要求被滿足，這樣就產(chǎn)生了一個(gè)符合監(jiān)測目標(biāo)要求且連通的感知方向集合。執(zhí)行節(jié)點(diǎn)能量更新操作后，繼續(xù)下一輪集合的選擇，直到不滿足覆蓋連通要求或節(jié)點(diǎn)因能量耗盡而死亡。

3.2.2 結(jié)果分析

1) 收斂性能比較

將種群的平均適應(yīng)度作為種群收斂性能的指標(biāo)，進(jìn)行算法收斂性能的比較，圖3 為ECRO 和CRO 算法的平均適應(yīng)度變化情況。觀察圖3 可以得出，ECRO 和CRO 兩種算法都隨著迭代次數(shù)變大而趨于收斂，并且ECRO 算法種群的平均適應(yīng)度大于CRO 算法，驗(yàn)證了改進(jìn)算法ECRO 的收斂性能較好。同時(shí)，兩種算法在未進(jìn)入迭代(迭代次數(shù)為0)時(shí)，ECRO 算法的種群平均適應(yīng)度優(yōu)于CRO 算法，證明了本文提出的種群初始化策略的有效性。

圖3 算法平均適應(yīng)度比較

2) 監(jiān)測要求與網(wǎng)絡(luò)壽命的關(guān)系

假定監(jiān)測目標(biāo)數(shù)目W=8，用M′代表重點(diǎn)監(jiān)測目標(biāo)的數(shù)量，其值分別設(shè)為3 和5；k′代表重點(diǎn)監(jiān)測目標(biāo)對(duì)應(yīng)的監(jiān)測覆蓋要求，其值分別設(shè)為2 和3，用ECRO 算法求解覆蓋連通問題。從圖4 求解得到的結(jié)果可以看出：1)節(jié)點(diǎn)數(shù)越多，網(wǎng)絡(luò)壽命越長。2)節(jié)點(diǎn)數(shù)和監(jiān)測覆蓋要求k′固定時(shí)，重點(diǎn)目標(biāo)數(shù)M′越大，相應(yīng)地網(wǎng)絡(luò)壽命也就越短。3)節(jié)點(diǎn)數(shù)和重點(diǎn)目標(biāo)數(shù)M′固定時(shí)，重點(diǎn)目標(biāo)的監(jiān)測覆蓋要求k′越大，網(wǎng)絡(luò)壽命就越短。

圖4 不同覆蓋要求對(duì)節(jié)點(diǎn)壽命的影響

3) 均勻比例下節(jié)點(diǎn)數(shù)量對(duì)網(wǎng)絡(luò)壽命的影響

設(shè)置不同的節(jié)點(diǎn)總數(shù)，等比例混合3 種類型的傳感器節(jié)點(diǎn)，研究節(jié)點(diǎn)數(shù)量對(duì)網(wǎng)絡(luò)壽命的影響。監(jiān)測目標(biāo)數(shù)為8，其他參數(shù)值與前面相同。從圖5的求解結(jié)果可以得出：1)隨著部署節(jié)點(diǎn)數(shù)的增加，網(wǎng)絡(luò)的壽命也隨之延長。究其原因在于，傳感器節(jié)點(diǎn)數(shù)量的增加使得可選的用于工作的感知方向增多，導(dǎo)致滿足監(jiān)測覆蓋需求的集合數(shù)目隨之增加；2)在部署節(jié)點(diǎn)數(shù)固定的情況下，提出的ECRO 算法明顯優(yōu)于其他算法。如當(dāng)節(jié)點(diǎn)數(shù)為60 時(shí)，與貪婪算法Greedy、LADE、未改進(jìn)的CRO 算法和EHS 算法[12]相比，改進(jìn)算法壽命分別延長97%、27.4% 、33.9%和21.5%。究其原因在于，貪婪算法盡管每一步都是當(dāng)前最優(yōu)，但局部最優(yōu)不保證最終得到全局最優(yōu)解。改進(jìn)算法得益于種群初始化、算法過程和最差個(gè)體的改進(jìn)，使得算法優(yōu)化能力得以增強(qiáng)。

圖5 算法比較

4) 非均勻比例下節(jié)點(diǎn)數(shù)量對(duì)網(wǎng)絡(luò)壽命的影響

研究非均勻比例對(duì)網(wǎng)絡(luò)壽命的影響。表4 為具體構(gòu)成比例，其中情況1 表示，3 種類型的傳感器節(jié)點(diǎn)數(shù)量都相同，也就是所占的比例均為1/3，情況2 表示3 種傳感器節(jié)點(diǎn)數(shù)量不同，3 種類型節(jié)點(diǎn)的參數(shù)詳見表3。監(jiān)測目標(biāo)數(shù)設(shè)為8，其他的算法參數(shù)與前面相同。從圖6 的結(jié)果可以得出：1)對(duì)于某一算法，在部署節(jié)點(diǎn)數(shù)固定的條件下，與情況1 相比，情況2 中的網(wǎng)絡(luò)壽命較好。如對(duì)于ECRO算法來說，當(dāng)節(jié)點(diǎn)總數(shù)為90 時(shí)，情形1 的網(wǎng)絡(luò)壽命為100 s，情形2 網(wǎng)絡(luò)壽命為120 s，壽命提高20%。2) 在節(jié)點(diǎn)比例和部署節(jié)點(diǎn)數(shù)都相同的條件下，較之其他算法，本文提出的ECRO 算法表現(xiàn)最好，驗(yàn)證了改進(jìn)算法的優(yōu)越性。

表4 節(jié)點(diǎn)構(gòu)成比例表

圖6 不同節(jié)點(diǎn)構(gòu)成比例下網(wǎng)絡(luò)壽命的比較

4 結(jié) 束 語

本文提出了一種基于增強(qiáng)珊瑚礁算法的網(wǎng)絡(luò)壽命最大化策略，解決應(yīng)用場景中監(jiān)測目標(biāo)差異化的監(jiān)測要求和網(wǎng)絡(luò)連通條件下異構(gòu)有向傳感器節(jié)點(diǎn)調(diào)度的問題。相比現(xiàn)有的節(jié)點(diǎn)調(diào)度算法，本文研究問題的特色在于，節(jié)點(diǎn)異構(gòu)、監(jiān)測目標(biāo)差異化監(jiān)測和網(wǎng)絡(luò)連通的要求更加符合有向傳感器網(wǎng)絡(luò)部署的實(shí)際情況。未來將應(yīng)用本文提出的方法研究三維空間內(nèi)的異構(gòu)有向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的覆蓋連通調(diào)度問題；另外在網(wǎng)絡(luò)連通方面，將引入中繼節(jié)點(diǎn)實(shí)現(xiàn)網(wǎng)絡(luò)多跳連通，在此基礎(chǔ)上研究更寬泛意義上的異構(gòu)有向傳感器網(wǎng)絡(luò)連通覆蓋調(diào)度算法，使得算法更具實(shí)用性。