面向差異化覆蓋的異構(gòu)有向傳感器節(jié)點調(diào)度算法

李 明，胡江平，曹曉莉，彭 鵬

（1.重慶工商大學計算機科學與信息工程學院，重慶 400067；2.電子科技大學自動化工程學院，成都 611731；3.重慶英卡電子有限公司，重慶 400039）

（?通信作者電子郵箱sshjlm@163.com）

0 引言

隨著有向傳感器網(wǎng)絡(luò)應用日益深入［1］，如何在滿足目標覆蓋要求的前提下延長傳感器網(wǎng)絡(luò)的壽命受到了越來越多研究者的重視［2］。文獻［3］基于貪婪算法的思想對感知方向進行優(yōu)化，并通過局部覆蓋集的概念對節(jié)點冗余性進行判斷，達到了延長網(wǎng)絡(luò)生命周期的目的。文獻［4］研究了最大有向區(qū)域覆蓋問題，提出了一種分布式貪婪算法來調(diào)度有向傳感器的工作方向，使覆蓋的區(qū)域面積達到最大值。但文獻［3-4］中貪婪算法求解的結(jié)果為局部優(yōu)化解。文獻［5］借助虛擬節(jié)點提出了一種休眠喚醒策略延長網(wǎng)絡(luò)壽命。利用分簇拓撲結(jié)構(gòu)，文獻［6-9］提出了相應的算法延長傳感器網(wǎng)絡(luò)的壽命。其中，文獻［6］借助分簇對有向傳感器網(wǎng)絡(luò)節(jié)點調(diào)度算法進行研究。文獻［7］以量子人工蜂群算法為求解工具，以節(jié)點的剩余能量、位置分布和密度為優(yōu)化目標，提出了一種能量有效的簇頭優(yōu)化算法。文獻［8］提出了一種基于多信息素的蟻群算法解決傳感器網(wǎng)絡(luò)中分簇拓撲結(jié)構(gòu)數(shù)據(jù)收集問題。為延長網(wǎng)絡(luò)壽命、改善數(shù)據(jù)傳輸中的可靠性和降低數(shù)據(jù)傳輸中消息傳輸造成的能量消耗，文獻［9］提出了一種基于三角模糊的光譜分簇算法。文獻［10-11］通過對數(shù)據(jù)收集過程的能量消耗問題進行研究，分別提出了基于生成樹的分布式算法和多頻段數(shù)據(jù)傳輸方法延長網(wǎng)絡(luò)壽命。文獻［12］提出了三種啟發(fā)式算法解決在部分或全部監(jiān)測目標覆蓋模型下的有向傳感器網(wǎng)絡(luò)壽命優(yōu)化問題。上述研究大多假定參與監(jiān)測任務的傳感器節(jié)點性能參數(shù)相同，忽略了在工程實踐中由于制造工藝、部署地形或網(wǎng)絡(luò)負載等原因，節(jié)點性能參數(shù)異構(gòu)才是節(jié)點最普遍的存在形式。上述研究成果忽視了節(jié)點性能參數(shù)的異構(gòu)對網(wǎng)絡(luò)壽命的影響，降低了算法的適用性。同時，上述研究均假定監(jiān)測目標具有同等重要性（優(yōu)先級），忽視了目標具有不同重要性（優(yōu)先級）條件下針對不同優(yōu)先級的目標而采取不同的覆蓋策略對網(wǎng)絡(luò)壽命的影響。盡管文獻［13-14］對具有不同優(yōu)先級的監(jiān)測目標覆蓋策略進行研究，分別提出了基于貪婪算法和基于改進粒子群的節(jié)點調(diào)度策略。但它們的研究成果是基于性能參數(shù)相同節(jié)點，忽略了節(jié)點參數(shù)異構(gòu)性對算法性能的影響。

在異構(gòu)有向傳感器網(wǎng)絡(luò)調(diào)度方面，文獻［15］提出了一種基于遺傳算法（Genetic Algorithm，GA）的節(jié)點調(diào)度策略，解決感知半徑可調(diào)條件下的網(wǎng)絡(luò)壽命最大化問題。文獻［16］對感知能力異構(gòu)隨機部署的有向傳感器網(wǎng)絡(luò)的節(jié)點調(diào)度問題進行研究，通過對節(jié)點最佳感知方向的求解和工作休眠狀態(tài)的判斷，進而達到延長網(wǎng)絡(luò)生存周期的目的。利用對原始差分算法進行改進，文獻［17］提出了一種基于目標優(yōu)化的節(jié)點調(diào)度策略來延長網(wǎng)絡(luò)的生命周期。上述研究成果都假定監(jiān)測目標的監(jiān)測要求都相同，忽略了監(jiān)測目標覆蓋要求差異化對算法性能的影響，比如：有些監(jiān)測目標由于所在的區(qū)域或本身的特性，為保證服務質(zhì)量常常要求多重覆蓋（多個傳感器節(jié)點同時覆蓋），上述的研究成果在解決上述應用場景的問題時存在較大的局限性。

針對這些問題，本文綜合考慮了節(jié)點異構(gòu)性和監(jiān)測目標不同的覆蓋要求，在滿足異構(gòu)有向傳感器網(wǎng)絡(luò)中監(jiān)測目標差異化的覆蓋要求前提下，以改進珊瑚礁優(yōu)化算法（Enhanced Coral Reef Optimization algorithm，ECRO）為節(jié)點調(diào)度策略的求解工具，通過求解出多個滿足覆蓋要求的集合，借助集合之間的切換實現(xiàn)延長異構(gòu)有向傳感器網(wǎng)絡(luò)壽命的研究目標。改進珊瑚礁算法的改進之處在于：一是在珊瑚礁優(yōu)化算法（Coral Reef Optimization algorithm，CRO）的雌雄同體繁殖過程中融入生物地理學優(yōu)化算法中的遷移操作，保留原有種群的優(yōu)秀解；二是在雌雄同體繁殖過程中采用一種帶有混沌參數(shù)的差分變異因子，增強子代的優(yōu)化能力；三是通過對最差個體執(zhí)行隨機反向?qū)W習增強種群的多樣性；最后，通過與模擬退火（Simulated Annealing，SA）算法結(jié)合，增強算法的局部搜索能力。

1 系統(tǒng)假設(shè)與問題建模

N個位置信息已知的有向傳感器節(jié)點si（i=1，2，…，N）和W個監(jiān)測目標Targeti（i=1，2，…，W）分布在二維平面區(qū)域中。有向傳感器節(jié)點si的感知半徑s_R（si）、當前的能量Ei（i=1，2，…，N）和感知角度θi均不同。在部署區(qū)域中節(jié)點si感知方向Di的數(shù)量為，且這些感知方向相互之間不重合。假定傳感器節(jié)點在工作狀態(tài)時只能有一個感知方向處于工作狀態(tài)，并且在一個工作周期內(nèi)不同類型的傳感器節(jié)點消耗的能量ei不同（性能參數(shù)越高的節(jié)點，消耗的能量越多）。節(jié)點處于非工作狀態(tài)時消耗能量極少，本文假定此時節(jié)點不消耗能量，因此節(jié)點的壽命。監(jiān)測目標分為重點目標和非重點目標兩種，其中重點目標要求同時被多個傳感器節(jié)點監(jiān)測（覆蓋）到，非重點目標只要被傳感器節(jié)點監(jiān)測到即可。

定義1傳感器網(wǎng)絡(luò)的壽命［17］。傳感器網(wǎng)絡(luò)中的傳感器節(jié)點滿足監(jiān)測對象覆蓋要求的時間。

從定義1 可以看出，網(wǎng)絡(luò)壽命是覆蓋優(yōu)劣的一種評價指標。

本文主要研究的問題為：在保證滿足監(jiān)測目標監(jiān)測要求的條件下，如何使得傳感器網(wǎng)絡(luò)的壽命最大化。借助集合覆蓋的思想，通過將所有的傳感器節(jié)點劃分成多個滿足監(jiān)測目標覆蓋要求的集合，借助集合之間的切換達到延長網(wǎng)絡(luò)壽命的目的。其數(shù)學模型為：

其中：K表示劃分的能滿足監(jiān)測對象覆蓋要求的集合數(shù)目；tk表示第k個滿足目標覆蓋要求集合的進行覆蓋的時間，它的值由求解出的滿足覆蓋要求集合中壽命最小的傳感器節(jié)點決定；Di，j表示傳感器節(jié)點si的序號為j的感知方向；Coverk表示第k個滿足條件的覆蓋集合；Ei表示節(jié)點si當前的能量；C_Targetk，m為在Coverk中能覆蓋監(jiān)測對象Targetm（m=1，2，…，W）傳感器節(jié)點感知方向的集合；Req(Targetm)表示監(jiān)測目標Targetm的監(jiān)測要求，即要求同時被多少個傳感器節(jié)點監(jiān)測到，取值為正整數(shù)，可根據(jù)目標本身的特性或目標所在的位置確定。如圖1 所示，目標集中出現(xiàn)的區(qū)域為重點區(qū)域，對于這些區(qū)域的監(jiān)測目標要求Req(Targetm)≥2，其他區(qū)域Req(Targetm)=1 即可。式（2）保證節(jié)點工作時的時間不會超過節(jié)點的壽命；式（3）保證在同一時刻一個傳感器節(jié)點最多只有一個感知方向處于工作狀態(tài)；式（4）保證每個集合中每個監(jiān)測目標的監(jiān)測要求都能被滿足。

由于本文要解決問題本質(zhì)上屬于組合優(yōu)化問題，將采用珊瑚礁優(yōu)化算法進行解決。

2 覆蓋調(diào)度策略

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

珊瑚礁算法是一種對珊瑚蟲行為進行模擬而形成的智能優(yōu)化算法［18］，該算法具有較強的優(yōu)化能力和較快的收斂速度。目前已應用于北歐風力農(nóng)場設(shè)計和布局優(yōu)化［18］、異構(gòu)有向傳感器網(wǎng)絡(luò)覆蓋控制［19］等方面。該算法的步驟分為：

1）初始化。

初始化步驟類似其他生物智能算法，比如遺傳算法、蟻群算法等，主要功能是實現(xiàn)種群初始化和算法參數(shù)的設(shè)置，包括：用于附著珊瑚蟲的珊瑚礁的大小，一般設(shè)為矩形Z×L；附著珊瑚蟲的珊瑚礁占總珊瑚礁的比例pro；最大迭代次數(shù)I_MAX；非性繁殖（即雌雄同體）的比例Fa，通過個體分裂進行繁殖的比例Fb（其值為1-Fa）；進化過程中子代允許附著的最大次數(shù)T_MAX；每次迭代珊瑚蟲被淘汰的概率pro_coral和淘汰的數(shù)量比例pro_no

2）繁殖過程。

珊瑚蟲的繁殖分為兩類：

一類為雌雄異體的繁殖過程，其數(shù)量為Z×L×pro×Fa，繁殖產(chǎn)生子代的方式為在可行區(qū)域內(nèi)隨機取值。

另一類為雌雄同體的繁殖過程，其數(shù)量為Z×L×pro×(1-Fa)，通過模擬二進制交叉的方式結(jié)合產(chǎn)生2個子代。

3）競爭過程。

競爭過程，也就是子代珊瑚蟲尋找珊瑚礁的過程：若尋找到的珊瑚礁無其他珊瑚蟲附著，則尋找成功，該珊瑚蟲附著于此；否則，若已有其他珊瑚蟲附著此珊瑚礁，則比較兩個珊瑚蟲的健康度（即適應度），健康度優(yōu)的珊瑚蟲勝出占有該珊瑚礁。此過程一直繼續(xù)，直到達到最大允許的嘗試次數(shù)。若達到最大允許的嘗試次數(shù)T_MAX時仍沒找到，則該珊瑚蟲死亡。

4）淘汰過程。

按照初始化時設(shè)定的淘汰概率pro_coral和淘汰數(shù)量比例pro_no自動淘汰部分珊瑚蟲。被淘汰的珊瑚蟲附著的珊瑚礁就會被空出，以便供其他的珊瑚蟲進行競爭。

重復上述的3 個過程，達到最大的迭代次數(shù)時，附著在珊瑚礁上且健康度最優(yōu)的珊瑚蟲就是問題的最優(yōu)解。

2.2 改進的珊瑚礁優(yōu)化算法

2.2.1 繁殖過程的改進

原始的珊瑚礁優(yōu)化算法（CRO）雌雄同體的繁殖過程中子代是在可行區(qū)域內(nèi)隨機產(chǎn)生，這使得原來雌雄同體種群中的較優(yōu)解被破壞，同時不利于探索解空間的新區(qū)域，降低了種群的多樣性。受到生物地理學優(yōu)化算法中遷移思想［20］和微分進化算法中變異機制的啟發(fā)，本文的改進方法為：雌雄同體子代的每一維有1-λi的概率來自于雌雄同體的父代，這使得較優(yōu)的解不容易被破壞；有的概率直接來自于其他雌雄同體，這種操作更注重在現(xiàn)有解周圍進行局部開發(fā)，并使得較差的解能從較優(yōu)的解中獲取大量新的特性，有助于提高解的精度；有的概率來源于雌雄同體之間的差分變異，該變異操作有利于增強算法的全局搜索能力和提高種群的多樣性。其中，λi為生物地理學優(yōu)化算法中解的第i維遷移率，，D為解的維數(shù)；cr為微分進化算法中的交叉率，本文中cr=0.9。

DE/rand/1/bin 差分變異策略作為一種常用的差分變異策略，在差分進化（Differential Evolution，DE）算法中得到廣泛應用［21］。本文采用DE/rand/1/bin，即：

其中：xi、xr1和xr2為雌雄同體中3 個不同的個體；Fn為第n次迭代時的縮放因子。采用混沌序列中Logistic 方程產(chǎn)生Fn防止算法的早熟收斂，即式（7）：

在本文中，初始時F1為［0，1］的隨機數(shù)。

改進的珊瑚礁算法一方面充分繼承了原有種群中的較優(yōu)解的“優(yōu)秀基因”，改善了較差解；另一方面，采用混沌序列縮放因子的差分變異策略增強了算法的全局搜索能力，提高了種群的多樣性。

2.2.2 最差個體優(yōu)化能力增強策略

在珊瑚蟲競爭過程結(jié)束之后、進入淘汰過程之前，為增強種群中適應度最差個體的全局優(yōu)化能力，對珊瑚蟲種群中的適應度最差的個體執(zhí)行反向?qū)W習策略，即：

其中：lb和ub分別表示下邊界和上邊界；rand（）為區(qū)間［0，1］的隨機數(shù)；表示當前迭代次數(shù)為t時全局最差的珊瑚蟲個體。對最差個體向量的值在允許可行范圍進行隨機取值，擺脫了原有個體取值導致的個體適應度最差的境地，改進了種群的多樣性，提高了獲得全局最優(yōu)解的概率，進而使得最差個體變成了非最差個體，提高了該個體的求解能力。

相較文獻［22］的反向?qū)W習算法，本文最差個體的反向?qū)W習策略優(yōu)勢在于：首先，進行該操作的對象數(shù)目不同。本文算法僅對最差個體執(zhí)行該操作，文獻［22］算法需要對多個個體（精英個體）執(zhí)行反向?qū)W習算法，而且該精英個體的數(shù)量每次都需要計算，時間復雜度較高。其次，調(diào)整范圍不同。本文算法的反向?qū)W習算法是在種群中可行范圍內(nèi)（也就是上邊界和下邊界之間）隨機取值，該可行范圍在算法運行之初已經(jīng)確定，無需計算。而文獻［22］算法是在多個個體（精英個體）的每一維通過計算得到其最大值和最小值進行調(diào)整，該操作每次迭代都需要進行，時間復雜度較高。

2.2.3 局部優(yōu)化能力增強策略

原始CRO 具有較強的全局搜索能力，但其單純依靠適應度大小來決定解的優(yōu)劣，使得當種群中某個個體適應度較大時，則該個體的基因迅速擴散，降低了種群的多樣性。特別是當前最優(yōu)個體陷入局部最優(yōu)時，其引導作用可以使其將其他種群個體帶入局部早熟收斂的境地。模擬退火算法具有較強的局部搜索能力，將具有良好局部搜索能力的模擬退火算法與全局搜索能力強的算法諸如微分進化算法、CRO 等算法相結(jié)合，可以更好解決種群中的早熟收斂問題［23-24］。借鑒這一思想，本文的具體操作為：將繁殖操作前的群體中最佳個體作為原解，對經(jīng)過繁殖、競爭、淘汰操作所產(chǎn)生的一組新個體中的最佳個體作為新解并進行模擬退火操作。采用Metropolis準則來判斷是否接受新解。在算法優(yōu)化的每一代，若這個新解使得適應度改善，則被接受；否則，以指數(shù)概率形式來決定是否被接受。接受新解的概率公式為：

其中：Fit（k+1）為新解的適應度值，F(xiàn)it（k）為原解的適應度值；p（T（k+1））為溫度T（k+1）下的接受概率；每一次迭代結(jié)束后T（k+1）的計算式為T(k+1)=α×T(k)，α為［0，1］常量，使得算法在開始時有較大的概率接受較差解，在算法后期接受差解的概率降低。

與文獻［23-24］算法不同，本文的珊瑚礁算法與模擬退火算法的結(jié)合特色在于：操作的對象不同，本文僅僅對最優(yōu)個體（適應度最優(yōu)）執(zhí)行模擬退火操作，不像文獻［23-24］算法對種群的所有個體都采用模擬退火策略。原因在于，若種群中最優(yōu)個體陷入局部最優(yōu)，則由于其引導作用，更容易導致其他個體陷入局部最優(yōu)而過早收斂；同時，由于執(zhí)行模擬退火操作的對象僅限于最優(yōu)個體，對算法的運行速度影響較小。文獻［23-24］算法對種群中所有個體都采用模擬退火策略，盡管能在一定程度上增加種群的多樣性，但是當優(yōu)化問題較為復雜、搜索空間較大時，對種群中所有個體都執(zhí)行模擬退火策略，無疑增加了算法復雜度和算法執(zhí)行時間。

2.2.4 改進算法的偽代碼

結(jié)合前文的描述，改進算法ECRO的偽代碼如下所示：

上述偽代碼中各個變量的含義同前文描述的一致。在改進算法ECRO中先對變量進行初始化（第1）～2）行），緊接著進行種群初始化（第3）～5）行）和迭代次數(shù)初始化（第6）行），然后算法進入迭代過程（第7）～34）行）。在迭代過程中，先得到當前種群最好的個體（第9）行），然后分別執(zhí)行繁殖操作（第10）～21）行）、健康度函數(shù)計算（第22）行）、競爭（第23）行）、對最差個體按照式（8）執(zhí)行反向?qū)W習策略（第24）行）、淘汰操作（第25）行）、尋找經(jīng)過上述操作后本次迭代最好的個體（第26）行）和利用模擬退火算法進行局部能力增強操作（第27）～31）行）。其中，種群繁殖的雌雄異體繁殖過程同原始的CRO；在雌雄同體的繁殖過程中采用本文的方法，即新個體每一維的值有1-λi的概率來自于雌雄同體的父代，有λi(1-cr-)的概率直接來自于其他雌雄同體，有λi(cr+)的概率來源于按照式（6）、（7）得到的雌雄同體之間的差分變異。在執(zhí)行模擬退火操作時按照式（9）計算相關(guān)概率，并根據(jù)概率大小選擇合適的更新策略，同時更新退火溫度。種群迭代結(jié)束后，輸出最佳可行解。

2.3 利用珊瑚礁優(yōu)化解決覆蓋調(diào)度問題

以珊瑚礁優(yōu)化算法及其改進算法作為求解工具獲取優(yōu)化的節(jié)點調(diào)度方案時，每一次迭代結(jié)束后，算法輸出一個滿足覆蓋要求的感知方向集合，同時更新節(jié)點的剩余能量，然后進入下一次迭代，繼續(xù)求解符合覆蓋要求的感知方向集合，直到算法結(jié)束。

算法設(shè)計時要解決健康度函數(shù)的設(shè)計和解的編碼兩個關(guān)鍵問題。

2.3.1 健康度函數(shù)的設(shè)計

運用珊瑚礁算法及其改進算法求解問題時，對于每一次迭代求解出的感知方向集合，要滿足兩個條件：一要達到監(jiān)測對象監(jiān)測覆蓋的要求；二要剩余能量最大化。根據(jù)集合覆蓋的思想，節(jié)點在形成滿足覆蓋要求集合后剩余能量越多，才能在后續(xù)的迭代過程中形成更多符合要求的覆蓋集合，實現(xiàn)網(wǎng)絡(luò)壽命的延長?；谝陨峡紤]，對于每一次迭代求解的感知方向集合，設(shè)計如下兩個子目標函數(shù)來評價解的質(zhì)量，分別是滿足覆蓋要求的目標數(shù)和節(jié)點的剩余能量，即：

其中：W′為算法求解得到的滿足覆蓋要求的監(jiān)測目標數(shù)；W為部署的監(jiān)測目標總數(shù)；f1取值范圍為［0，1］；f2為剩余能量的函數(shù)，f2值域為［0，1］；tanh為雙曲正切函數(shù)；β為比例系數(shù)，在本文中設(shè)為1。

上述兩個優(yōu)化子目標，屬于多目標優(yōu)化問題，考慮到傳感器網(wǎng)絡(luò)資源受限的特點，本文采用文獻［25］隨機線性加權(quán)的方式轉(zhuǎn)換為單目標優(yōu)化問題，即：

其中：γ1和γ2為兩個子目標對應的權(quán)重；randi表示區(qū)間（0，1）的隨機數(shù)。

2.3.2 解的編碼

結(jié)合求解問題的特點，本文中采用整型編碼的方法，按照節(jié)點的序號和感知方向序號，為所有部署節(jié)點所有的感知方向依次進行整數(shù)編碼，解的編碼如圖2所示。

圖2 解的編碼示意圖Fig.2 Schematic diagram of solution coding

圖2 中，解的每一位ci表示用于監(jiān)測第i個監(jiān)測目標的有向傳感器感知方向的信息，具體含義為：

其中|Di|為節(jié)點si可用的感知方向數(shù)量?；诠?jié)點每個感知方向可同時監(jiān)測多個離散監(jiān)測目標的考慮，所以即使染色體編碼中出現(xiàn)某些位置取值為0，最終該染色體也可能符合目標監(jiān)測的要求。

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

在本章中，首先在測試函數(shù)上測試改進算法ECRO 的性能，然后將改進算法應用在節(jié)點調(diào)度問題上。

3.1 數(shù)值測試

分別在Sphere 函數(shù)、Rotated hyper-ellipsoid 函數(shù)、Step 函數(shù)和Schwefel 函數(shù)上比較算法的性能。測試函數(shù)的信息詳見表1。參與測試的算法包括：遺傳算法（GA）、模擬退火（SA）算法、原始差分進化（DE）算法、文獻［17］中的基于學習自動機的差分進化（Learning Automata Differential Evolution，LADE）算法。函數(shù)的具體信息如表1所示。

表1 測試函數(shù)說明Tab.1 Description of test functions

CRO 中矩形區(qū)域Z×L設(shè)為10×5，F(xiàn)b=0.9，F(xiàn)a=0.1，pro=0.7，T_MAX=3，pro_coral=0.1，pro_no=0.01［18］；ECRO 中T（1）=1 000 000，α=0.8［26］，優(yōu)化函數(shù)維數(shù)n=30，其他算法參數(shù)的設(shè)置詳見文獻［17］。取20次實驗的平均值，結(jié)果如表2所示。

表2 不同算法的最佳結(jié)果比較Tab.2 Best result comparison of different algorithms

觀察表2可以得出，在F3函數(shù)中，參與比較的算法中除了GA 和SA，其他算法均取得了全局優(yōu)化解0；對于另外的測試函數(shù)，相較其他算法，改進算法的性能也表現(xiàn)優(yōu)異。數(shù)值測試結(jié)果表明，相較其他算法，本文提出的算法ECRO 性能最佳，驗證了所提算法的有效性。

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

3.2.1 仿真環(huán)境設(shè)定

在Windows 10 教育版+Matlab 2013b 平臺上對本文算法性能進行驗證。節(jié)點部署區(qū)域設(shè)為50 m×50 m，部署節(jié)點數(shù)N為30，每個集合每個周期工作的時間wt=1 s，感知方向的個數(shù)為且感知方向之間相互不重合，其中θi表示感知角度。節(jié)點的其他參數(shù)設(shè)置如表3所示。監(jiān)測目標數(shù)W為6，隨機分布在監(jiān)測區(qū)域內(nèi)，根據(jù)其分布區(qū)域分為兩種類型：重點目標和非重點目標。其中，對于分布在圖1 且頻繁出現(xiàn)的目標認定為重點目標，要求滿足至少同時被2 個傳感器節(jié)點覆蓋的要求；其余目標滿足被1 個傳感器節(jié)點覆蓋要求即可。每種類型的監(jiān)測目標數(shù)量隨機產(chǎn)生，且隨機分布在監(jiān)測區(qū)域內(nèi)。

為了更好地比較算法性能，提出了一種基于貪婪算法作為基準的比較算法。其算法思想為每次選擇節(jié)點剩余能量最多的且同時能覆蓋最多監(jiān)測目標的感知方向（在實現(xiàn)時，用這兩個指標乘積的值確定），直到滿足所有的節(jié)點覆蓋要求，此時形成一個滿足覆蓋要求的節(jié)點集合。更新節(jié)點能量后，繼續(xù)進行上述過程，直到不存在滿足目標覆蓋要求的節(jié)點或節(jié)點能量為0為止。

表3 節(jié)點參數(shù)Tab.3 Node parameters

3.2.2 結(jié)果分析

1）算法收斂性比較。

為比較種群的收斂性能，對種群的平均適應度進行比較，結(jié)果如圖3 所示。從圖3 中可以看出，隨著迭代次數(shù)的增加，ECRO 和CRO 兩種算法都趨于收斂，并且ECRO 種群的平均適應度明顯優(yōu)于CRO，表明了ECRO的優(yōu)化能力優(yōu)于CRO。

圖3 種群的平均適應度Fig.3 Average fitness of population

2）覆蓋質(zhì)量要求對網(wǎng)絡(luò)壽命的影響。

設(shè)置目標總數(shù)W為8，其中重點目標的數(shù)量M′分別設(shè)為3 和5，重點目標的覆蓋要求k′分別設(shè)為2 和3，運行本文提出的ECRO，比較網(wǎng)絡(luò)壽命的變化，結(jié)果如圖4 所示。從圖4 中可以看出：

①隨著部署節(jié)點數(shù)的增加，網(wǎng)絡(luò)的壽命在增加。比如，當部署節(jié)點總數(shù)由60 增加至120 時，四種情況下網(wǎng)絡(luò)壽命分別增加了59.4%、60.9%、57.7%和50.7%。

②當部署的節(jié)點數(shù)不變時，相同覆蓋要求下（即k′相同時），重點目標數(shù)越多，網(wǎng)絡(luò)壽命也就越少。這主要源于重點目標數(shù)越多，覆蓋要求也相較非重點目標要求高，就需要更多的感知方向去滿足重點目標的覆蓋要求，從而使得網(wǎng)絡(luò)的壽命減少。

③部署的節(jié)點數(shù)和重點目標數(shù)不變的情況下，重點目標的覆蓋要求越高，相應的網(wǎng)絡(luò)壽命也就越少。

圖4 不同覆蓋要求對網(wǎng)絡(luò)壽命的影響Fig.4 Effect of different coverage requirements on network lifespan

3）算法性能比較。

分別設(shè)置節(jié)點總數(shù)為30、60、90 和120，各種節(jié)點類型數(shù)量比例為1∶1∶1，目標數(shù)M=8，其余參數(shù)的設(shè)置詳見3.2.1節(jié)，運行貪婪算法（Greedy）、CRO、ECRO 和文獻［17］中的LADE算法，求解的結(jié)果如圖5 所示。從圖5 中可以看出，隨著部署節(jié)點數(shù)增加，網(wǎng)絡(luò)的壽命也隨之增加，這主要源于隨著節(jié)點數(shù)的增加，用于目標的覆蓋的方向數(shù)也相應地增加，從而符合覆蓋要求的集合數(shù)也就增加。在部署節(jié)點數(shù)不變的情況下，ECRO 求解的結(jié)果優(yōu)于其他比較算法。比如當節(jié)點數(shù)為90時，相較貪婪算法Greedy、LADE 和CRO，ECRO 求解的網(wǎng)絡(luò)壽命分別提高了53.8%、19.0%和26.6%，表明了改進算法ECRO 的有效性。這主要由于貪婪算法本質(zhì)上是一種局部優(yōu)化算法，局部的最優(yōu)化有時并不一定得到全局優(yōu)化的解；另一方面，改進算法ECRO 通過對雌雄同體繁殖過程、最差解的優(yōu)化和與模擬退火算法結(jié)合避免陷入局部最優(yōu)的策略，改進了算法的優(yōu)化能力。

圖5 不同節(jié)點數(shù)條件下網(wǎng)絡(luò)壽命比較Fig.5 Comparison of network lifespan under different numbers of nodes

研究不同節(jié)點構(gòu)成比例對網(wǎng)絡(luò)壽命的影響。分別設(shè)置A和B 兩種情形，每種情形下節(jié)點的構(gòu)成比例如表4 所示，目標數(shù)M=8，其余參數(shù)的設(shè)置詳見3.2.1節(jié)，結(jié)果如圖6所示。

表4 節(jié)點構(gòu)成比例Tab.4 Node composition proportion

從圖6中可以看出：

①在節(jié)點總數(shù)和運行算法不變的情況下，情形B 求解的結(jié)果優(yōu)于情形A。比如，對于ECRO 來說，當節(jié)點總數(shù)為120時，情形A 的網(wǎng)絡(luò)壽命為121 s，情形B 網(wǎng)絡(luò)壽命為137 s，壽命提高了13.2%。這主要由于在情形B 中類型2 節(jié)點的比例居多，而類型2 在三種類型的節(jié)點中性能參數(shù)如感知角度、能量最高，使得情形B的網(wǎng)絡(luò)壽命優(yōu)于情形A的網(wǎng)絡(luò)壽命。

②在相同的節(jié)點部署總數(shù)和相同節(jié)點構(gòu)成比例時，本文的ECRO 均優(yōu)于比較算法，表明了改進算法ECRO 的有效性。比如，當部署節(jié)點數(shù)為120時，相較貪婪算法Greedy、LADE 和CRO，情形A 條件下，ECRO 求解的網(wǎng)絡(luò)壽命分別提高了40.7%、18.6%和24.7%；情形B 條件下，ECRO 求解的網(wǎng)絡(luò)壽命分別提高了48.9%、19.1%和24.5%。

圖6 不同節(jié)點構(gòu)成比例下網(wǎng)絡(luò)壽命比較Fig.6 Network lifespan comparisons under different node composition proportions

4 結(jié)語

本文對異構(gòu)有向傳感器網(wǎng)絡(luò)中監(jiān)測目標差異化覆蓋要求條件下的節(jié)點調(diào)度問題進行研究，提出了一種基于改進珊瑚礁算法的節(jié)點調(diào)度算法延長網(wǎng)絡(luò)壽命。實驗結(jié)果驗證了所提算法ECRO 的有效性。下一步研究工作可從以下兩個方面考慮：1）在多目標優(yōu)化方面，本文采用的隨機線性加權(quán)方法盡管從仿真結(jié)果上優(yōu)于比較算法，但未能兼顧用戶的偏好，未來將考慮研究一種兼顧用戶偏好且復雜度低的算法；2）將連通性約束加入覆蓋集合中，對異構(gòu)有向傳感器網(wǎng)絡(luò)的連通覆蓋問題進行研究。