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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

1）初始化。

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

2）繁殖過(guò)程。

珊瑚蟲(chóng)的繁殖分為兩類(lèi)：

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

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

3）競(jìng)爭(zhēng)過(guò)程。

競(jìng)爭(zhēng)過(guò)程，也就是子代珊瑚蟲(chóng)尋找珊瑚礁的過(guò)程：若尋找到的珊瑚礁無(wú)其他珊瑚蟲(chóng)附著，則尋找成功，該珊瑚蟲(chóng)附著于此；否則，若已有其他珊瑚蟲(chóng)附著此珊瑚礁，則比較兩個(gè)珊瑚蟲(chóng)的健康度（即適應(yīng)度），健康度優(yōu)的珊瑚蟲(chóng)勝出占有該珊瑚礁。此過(guò)程一直繼續(xù)，直到達(dá)到最大允許的嘗試次數(shù)。若達(dá)到最大允許的嘗試次數(shù)T_MAX時(shí)仍沒(méi)找到，則該珊瑚蟲(chóng)死亡。

4）淘汰過(guò)程。

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

重復(fù)上述的3 個(gè)過(guò)程，達(dá)到最大的迭代次數(shù)時(shí)，附著在珊瑚礁上且健康度最優(yōu)的珊瑚蟲(chóng)就是問(wèn)題的最優(yōu)解。

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

2.2.1 繁殖過(guò)程的改進(jìn)

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

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

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

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

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

2.2.2 最差個(gè)體優(yōu)化能力增強(qiáng)策略

在珊瑚蟲(chóng)競(jìng)爭(zhēng)過(guò)程結(jié)束之后、進(jìn)入淘汰過(guò)程之前，為增強(qiáng)種群中適應(yīng)度最差個(gè)體的全局優(yōu)化能力，對(duì)珊瑚蟲(chóng)種群中的適應(yīng)度最差的個(gè)體執(zhí)行反向?qū)W習(xí)策略，即：

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

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

2.2.3 局部?jī)?yōu)化能力增強(qiáng)策略

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

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

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

2.2.4 改進(jìn)算法的偽代碼

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

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

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

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

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

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

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

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

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

其中：γ1和γ2為兩個(gè)子目標(biāo)對(duì)應(yīng)的權(quán)重；randi表示區(qū)間（0，1）的隨機(jī)數(shù)。

2.3.2 解的編碼

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

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

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

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

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

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

3.1 數(shù)值測(cè)試

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

表1 測(cè)試函數(shù)說(shuō)明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è)置詳見(jiàn)文獻(xiàn)［17］。取20次實(shí)驗(yàn)的平均值，結(jié)果如表2所示。

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

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

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

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

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

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

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

3.2.2 結(jié)果分析

1）算法收斂性比較。

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

圖3 種群的平均適應(yīng)度Fig.3 Average fitness of population

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

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

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

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

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

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

3）算法性能比較。

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

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

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

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

從圖6中可以看出：

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

②在相同的節(jié)點(diǎn)部署總數(shù)和相同節(jié)點(diǎn)構(gòu)成比例時(shí)，本文的ECRO 均優(yōu)于比較算法，表明了改進(jìn)算法ECRO 的有效性。比如，當(dāng)部署節(jié)點(diǎn)數(shù)為120時(shí)，相較貪婪算法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é)點(diǎn)構(gòu)成比例下網(wǎng)絡(luò)壽命比較Fig.6 Network lifespan comparisons under different node composition proportions

4 結(jié)語(yǔ)

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