面向不同目標(biāo)覆蓋要求的異構(gòu)有向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法

李明　林新宇　彭鵬

摘要：針對(duì)給定部署區(qū)域中不同的監(jiān)測(cè)目標(biāo)有不同的覆蓋需求和現(xiàn)有的調(diào)度算法大多針對(duì)同構(gòu)有向傳感器節(jié)點(diǎn)忽略了節(jié)點(diǎn)異構(gòu)對(duì)調(diào)度性能的影響的問(wèn)題，提出兩種異構(gòu)有向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度策略。一種方法是通過(guò)對(duì)問(wèn)題進(jìn)行數(shù)學(xué)建模，將節(jié)點(diǎn)調(diào)度問(wèn)題轉(zhuǎn)化為目標(biāo)優(yōu)化問(wèn)題，采用改進(jìn)的和聲搜索算法進(jìn)行求解。改進(jìn)和聲搜索算法針對(duì)原始和聲搜索在陷入局部最優(yōu)時(shí)的過(guò)早收斂問(wèn)題，通過(guò)將和聲搜索算法和模擬退火算法結(jié)合增強(qiáng)其局部搜索能力。另一種方法采用貪婪算法求解滿足條件的節(jié)點(diǎn)集合。仿真結(jié)果顯示，與原始和聲搜索算法相比，改進(jìn)和聲搜索算法能有效提高網(wǎng)絡(luò)的工作時(shí)間，證明了改進(jìn)算法的有效性。

關(guān)鍵詞：有向傳感器網(wǎng)絡(luò);異構(gòu)網(wǎng)絡(luò);和聲搜索算法;模擬退火算法;節(jié)點(diǎn)調(diào)度

中圖分類號(hào)：TP393? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）03-0001-04

Abstract： Two node scheduling strategies for heterogeneous directional sensor networks are proposed to solve the heterogeneous coverage requirements of the targets in the deployed area. The characteristic of node heterogeneity and heterogeneous coverage requirements of the targets have great impacts on performance of scheduling algorithm， which are neglected by most of the existing research. One of the proposed algorithms formulate the scheduling problem as an objective optimization problem and improved harmony search algorithm （shortly for IHS） is utilized to address such scheduling problem. The IHS hybrid harmony search algorithm and simulated annealing algorithm to address the premature convergence problem especially when one or more initial harmonies are in the vicinity of local optimal. The other proposed algorithm is based on greedy algorithm to construct as more cover set as possible. Simulation results shows that the proposed IHS achieves better performance than the primitive harmony algorithm （shortly for HS）， which proves the effectiveness of the proposed algorithm.

Key words： directional sensor networks; heterogeneous network; harmony search algorithm; simulating annealing algorithm; node scheduling

隨著傳感器網(wǎng)絡(luò)應(yīng)用廣度和深度不斷拓展，由視頻傳感器、聲音傳感器和雷達(dá)傳感器等有向感知模型的傳感器節(jié)點(diǎn)構(gòu)成的有向傳感器網(wǎng)絡(luò)在工程實(shí)踐中得以廣泛應(yīng)用[1]。如何更有效的實(shí)施目標(biāo)監(jiān)測(cè)和延長(zhǎng)網(wǎng)絡(luò)壽命，是有向傳感器網(wǎng)絡(luò)應(yīng)用時(shí)需要解決的關(guān)鍵問(wèn)題。節(jié)點(diǎn)調(diào)度是一種降低傳感器網(wǎng)絡(luò)能耗和延長(zhǎng)網(wǎng)絡(luò)工作時(shí)間的有效方法，得到了越來(lái)越多研究者的重視[2]。文獻(xiàn)[3]提出一種公平的有向傳感器網(wǎng)絡(luò)方向優(yōu)化和節(jié)點(diǎn)調(diào)度算法。文獻(xiàn)[4]提出一種基于離散網(wǎng)格的有向傳感器網(wǎng)絡(luò)冗余節(jié)點(diǎn)調(diào)度算法。文獻(xiàn)[5]通過(guò)建立目標(biāo)部署圓內(nèi)覆蓋最多鄰居目標(biāo)點(diǎn)的候選節(jié)點(diǎn)集合對(duì)隨機(jī)部署的節(jié)點(diǎn)進(jìn)行調(diào)度，提出一種面向目標(biāo)的有向傳感器網(wǎng)絡(luò)連通覆蓋算法。文獻(xiàn)[6]提出了一種基于啟發(fā)式的有向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法延長(zhǎng)網(wǎng)絡(luò)壽命。文獻(xiàn)[7]提出了一種基于貪婪算法的應(yīng)用于智能城市場(chǎng)合的有向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法。在異構(gòu)有向傳感器網(wǎng)絡(luò)方面，文獻(xiàn)[8]提出一種基于遺傳算法的感知半徑可調(diào)的有向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法。文獻(xiàn)[9]提出一種自動(dòng)學(xué)習(xí)機(jī)的異構(gòu)節(jié)點(diǎn)調(diào)度算法延長(zhǎng)網(wǎng)絡(luò)壽命。

上述文獻(xiàn)[3]到文獻(xiàn)[7]都是針對(duì)相同參數(shù)的有向傳感器節(jié)點(diǎn)也就是同構(gòu)傳感器節(jié)點(diǎn)，忽視了在工程實(shí)踐中，由于制造工藝等原因傳感器節(jié)點(diǎn)的性能參數(shù)不可能完全相同，異構(gòu)才是有向傳感器節(jié)點(diǎn)最普遍的存在方式，使得上述成果不能很好應(yīng)用工程實(shí)際。針對(duì)離散目標(biāo)監(jiān)測(cè)這種應(yīng)用場(chǎng)合，盡管文獻(xiàn)[8]和文獻(xiàn)[9]對(duì)異構(gòu)有向傳感器節(jié)點(diǎn)調(diào)度問(wèn)題進(jìn)行研究并取得了一定的研究成果，但由于實(shí)際應(yīng)用中目標(biāo)出現(xiàn)的頻率不盡相同，導(dǎo)致監(jiān)測(cè)目標(biāo)的重要性也不盡相同。對(duì)于重要的監(jiān)測(cè)目標(biāo)為了保證監(jiān)測(cè)質(zhì)量和容錯(cuò)性的要求，一般采用多個(gè)節(jié)點(diǎn)同時(shí)監(jiān)測(cè)同一個(gè)重點(diǎn)監(jiān)測(cè)目標(biāo)。也就是說(shuō)，不同的監(jiān)測(cè)目標(biāo)有不同的監(jiān)測(cè)（覆蓋）要求。上述兩篇文獻(xiàn)忽略了監(jiān)測(cè)目標(biāo)覆蓋的要求可能不同，導(dǎo)致研究成果適用性受到限制。針對(duì)上述文獻(xiàn)存在的問(wèn)題，本文提出了兩種算法——基于改進(jìn)和聲搜索算法和基于貪婪算法的異構(gòu)有向傳感器節(jié)點(diǎn)調(diào)度算法來(lái)解決具有不同覆蓋要求的目標(biāo)監(jiān)測(cè)的應(yīng)用場(chǎng)合的異構(gòu)有向傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)調(diào)度問(wèn)題，以延長(zhǎng)網(wǎng)絡(luò)工作時(shí)間和增強(qiáng)網(wǎng)絡(luò)的服務(wù)質(zhì)量。

1 問(wèn)題模型分析

假定平面區(qū)域A中，分布有N個(gè)有向傳感器節(jié)點(diǎn)和T個(gè)需要監(jiān)測(cè)的目標(biāo)Ti （i =1，2，...，T），假定有向傳感器節(jié)點(diǎn)的感知方向Di的數(shù)量為|Di|（i =1，2，...，N）和壽命Li （i =1，2，...，N）均不同，且同一時(shí)刻只能有一個(gè)感知方向處于工作狀態(tài)。監(jiān)測(cè)目標(biāo)具有不同的優(yōu)先級(jí)，分為優(yōu)先級(jí)高的監(jiān)測(cè)目標(biāo)和優(yōu)先級(jí)低的監(jiān)測(cè)目標(biāo)，其中優(yōu)先級(jí)高的監(jiān)測(cè)目標(biāo)要求同時(shí)被多個(gè)傳感器節(jié)點(diǎn)監(jiān)測(cè)（覆蓋）到，優(yōu)先級(jí)低的監(jiān)測(cè)目標(biāo)只要被傳感器節(jié)點(diǎn)監(jiān)測(cè)到即可。如何在保證滿足監(jiān)測(cè)目標(biāo)監(jiān)測(cè)的要求條件下，盡可能延長(zhǎng)傳感器網(wǎng)絡(luò)的壽命是本文要研究的問(wèn)題。

根據(jù)上文的闡述，我們采用集合覆蓋的思想，將傳感器網(wǎng)絡(luò)節(jié)點(diǎn)集合劃分成多個(gè)符合監(jiān)測(cè)目標(biāo)監(jiān)測(cè)覆蓋要求的集合，通過(guò)集合之間不同的切換，達(dá)到延長(zhǎng)網(wǎng)絡(luò)壽命的目標(biāo)。用形式化的語(yǔ)言可描述為：

[其中xi，j，k=1 if Di，j∈Ck0 其他，tk≥0]tk表示每個(gè)集合的工作時(shí)間，K表示劃分的覆蓋集合最大數(shù)量，Di，j表示節(jié)點(diǎn)Si的第j感知方向，Ck表示第k個(gè)滿足條件的覆蓋集合，Li表示節(jié)點(diǎn)Si的壽命，C_Tm表示能覆蓋監(jiān)測(cè)目標(biāo)Tm的感知方向的集合，[m=1，2，…，T];[ Req（Tm）]表示監(jiān)測(cè)目標(biāo)Tm的監(jiān)測(cè)要求。式子（2）保證節(jié)點(diǎn)工作的時(shí)間不會(huì)超過(guò)它的壽命;式子（3）保證在滿足條件的集合中一個(gè)傳感器節(jié)點(diǎn)最多只有一個(gè)感知方向處于工作狀態(tài);式子（4）保證每個(gè)監(jiān)測(cè)目標(biāo)的監(jiān)測(cè)要求都能被滿足，Req（Tm）為對(duì)目標(biāo)Tm的監(jiān)測(cè)要求，為正整數(shù)，具體取值根據(jù)目標(biāo)的重要性確定。

2 改進(jìn)和聲搜索算法

2.1 原始和聲搜索算法簡(jiǎn)介

和聲搜索算法通過(guò)對(duì)音樂(lè)家的創(chuàng)作過(guò)程進(jìn)行模擬，將決策變量和解向量分別類比樂(lè)器的音調(diào)和各種音調(diào)的和聲，優(yōu)化目標(biāo)和種群分別類比適應(yīng)度（評(píng)價(jià)）函數(shù)和和聲記憶庫(kù)，通過(guò)不斷的迭代優(yōu)化來(lái)實(shí)現(xiàn)問(wèn)題的求解[10]。算法步驟包括初始化和聲記憶庫(kù)（ harmony memory，HM），新產(chǎn)生的解有兩部分來(lái)源，一部分來(lái)源于HM，其占比為HMCR;另一部分在問(wèn)題可行區(qū)域內(nèi)隨機(jī)取值。來(lái)源于HM的新解以概率PAR用參數(shù)BW進(jìn)行局部擾動(dòng)。若新產(chǎn)生解的適應(yīng)度函數(shù)優(yōu)于HM原有的最差解，則新解替換最差解。算法不斷迭代進(jìn)行上述步驟直到滿足停止的條件[11]。

原始的和聲搜索若在算法初始化時(shí)產(chǎn)生的解向量若在問(wèn)題的局部值附近，則容易陷入早熟收斂，影響算法的優(yōu)化效率。針對(duì)這一問(wèn)題，借鑒模擬退火算法的思想和其局部搜索能力強(qiáng)的優(yōu)點(diǎn)，將模擬退火算法與和聲搜索算法結(jié)合，提出一種改進(jìn)的和聲搜索算法

2.2 改進(jìn)的和聲搜索算法IHS

改進(jìn)算法的步驟同原始和聲搜索算法相同，區(qū)別在于對(duì)于最差解的處理。原始和聲搜索算法中若新產(chǎn)生的解優(yōu)于最差解，則最差解被新產(chǎn)生的解替換。改進(jìn)算法IHS中考慮到算法可能陷入局部最優(yōu)的狀況，結(jié)合模擬退火算法的思想，針對(duì)種群進(jìn)化過(guò)程中的由于局部最優(yōu)而導(dǎo)致過(guò)早收斂問(wèn)題，采用對(duì)最差解以一定概率接受的策略，增強(qiáng)種群的多樣性以提升算法優(yōu)化能力。改進(jìn)和聲搜索算法的偽代碼為：

輸入：和聲搜索算法參數(shù)，包括：HMCR，PAR， BW和初始化記憶庫(kù)HMS;模擬退火算法參數(shù)，包括初始溫度T0，溫度變化參數(shù)α

輸出：最優(yōu)和聲（解向量）

初始化和聲搜索算法參數(shù)HMCR ，PAR， BW和和聲記憶庫(kù)HMS

初始化模擬退火算法T0，并設(shè)T=T0

1 While（和聲搜索算法不滿足結(jié)束條件）

2 Find current worst harmony in HM

3 For i=1 to Dim

4 If（rand（）<=HMCR）

5 Hi =[HMji] where j = rand_int（1，col （HM））

6 If （rand（）<=PAR）

7 Hi = Hi[±]rand（）×BW

8 End if

9 Else

10 Generate Hi randomly within the allowed bounds

11 End if

12 End for

13 Dif = f（H）-f（Worst）

14 If（Dif <0 or rand（）<[e-DifT']）

15 Update HM by replacing Worst harmony by H

16 End if

17 T =α×T

18 End while

19 Output Best harmony as solution

上述的偽代碼其中行1-行18為和聲搜索算法迭代過(guò)程，行2先尋找當(dāng)前的最差的和聲個(gè)體，行3-行12對(duì)于每個(gè)和聲個(gè)體的每一維執(zhí)行和聲算法步驟，也就是每一維有概率HMCR來(lái)源自原來(lái)的和聲記憶庫(kù)HM，這部分個(gè)體中有PAR比率的個(gè)體會(huì)進(jìn)行參數(shù)為BW的隨機(jī)擾動(dòng)以增加個(gè)體多樣性;有1-HMCR概率是在問(wèn)題可行區(qū)域內(nèi)隨機(jī)取值。對(duì)于新產(chǎn)生的和聲個(gè)體若優(yōu)于最差和聲（行14，此處假定求最小值問(wèn)題）或者滿足rand（）<[e-DifT']條件（行14），則新個(gè)體替換最差個(gè)體。算法最后輸出最優(yōu)和聲個(gè)體作為問(wèn)題的解。Dim為優(yōu)化問(wèn)題的維數(shù)，函數(shù)f（）為待求解問(wèn)題的函數(shù)，rand（）為區(qū)間（0，1）之間的隨機(jī)數(shù);函數(shù)rand_int（A，B）為返回整型數(shù)A到B之間的隨機(jī)整數(shù);col（C）作用為返回向量C的列向量個(gè)數(shù)。

2.3 節(jié)點(diǎn)調(diào)度問(wèn)題的求解

利用和聲搜索算法解決異構(gòu)節(jié)點(diǎn)調(diào)度問(wèn)題時(shí)，要解決優(yōu)化目標(biāo)的選擇，適應(yīng)度函數(shù)的設(shè)計(jì)，以及解的表示也就是編碼問(wèn)題三個(gè)關(guān)鍵問(wèn)題。

1）優(yōu)化目標(biāo)

對(duì)于本文的優(yōu)化問(wèn)題，一方面要使?jié)M足覆蓋條件的集合數(shù)量最大化，另一方面使得節(jié)點(diǎn)剩余壽命（跟節(jié)點(diǎn)的能量成正比）最大化。根據(jù)文獻(xiàn)[12]滿足覆蓋條件節(jié)點(diǎn)集合數(shù)的上限值K為能覆蓋監(jiān)測(cè)要求最高目標(biāo)的節(jié)點(diǎn)的壽命（若有多個(gè)節(jié)點(diǎn)，則選擇壽命最小的）與監(jiān)測(cè)要求最大值的比值，即[K=Lgmax（t）]，其中，L表示能覆蓋監(jiān)測(cè)要求最高目標(biāo)的節(jié)點(diǎn)的壽命;gmax（t）表示監(jiān)測(cè)目標(biāo)中監(jiān)測(cè)要求最大的值。

本文要優(yōu)化的目標(biāo)有兩個(gè)：符合覆蓋要求的節(jié)點(diǎn)集合和節(jié)點(diǎn)的剩余壽命，即：

其中Q為滿足覆蓋要求的集合格式，f1取值范圍為[0，1]; f2為剩余壽命，tanh為雙曲正切函數(shù)，β為比例系數(shù)，在本文中設(shè)為1;f2值域?yàn)閇0，1]。

2）適應(yīng)度設(shè)計(jì)

根據(jù)對(duì)優(yōu)化目標(biāo)的分析，對(duì)于本文的多目標(biāo)優(yōu)化算法，采用文獻(xiàn)[13]隨機(jī)加權(quán)的方式，將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題。兩個(gè)目標(biāo)函數(shù)對(duì)應(yīng)的權(quán)值按照下面的式子確定：

3）問(wèn)題編碼表示

種群中的每個(gè)個(gè)體代表求解問(wèn)題的一個(gè)候選解，本文中采用整型編碼的方法，編碼示意圖如圖1所示。

3 貪婪算法

為了驗(yàn)證提出的IHS的節(jié)點(diǎn)調(diào)度算法的性能，提出一種基于貪婪算法的離散目標(biāo)節(jié)點(diǎn)覆蓋算法作為比較算法。貪婪算法的思想為每次選擇節(jié)點(diǎn)剩余能量最多的且同時(shí)能覆蓋最多監(jiān)測(cè)目標(biāo)的感知方向（在實(shí)現(xiàn)時(shí)，用這兩個(gè)指標(biāo)的乘積的值確定），其主要步驟為：

1） 初始化算法參數(shù)，包括可用的傳感器集合S_K，設(shè)置其初值為所有的傳感器節(jié)點(diǎn);目標(biāo)監(jiān)測(cè)要求集合Req_T，并設(shè)置臨時(shí)目標(biāo)監(jiān)測(cè)要求集合temReq_T，使其等于Req_T;傳感器節(jié)點(diǎn)的壽命Li;已覆蓋目標(biāo)集合covered_T ={}，未覆蓋目標(biāo)集合uncovered_T ，并賦初值為監(jiān)測(cè)目標(biāo)集合T;節(jié)點(diǎn)是否用過(guò)數(shù)組isUsed，并設(shè)初值為0，表示所有節(jié)點(diǎn)均沒(méi)用過(guò);存儲(chǔ)滿足覆蓋條件的結(jié)果集合Result = {}，該集合中每個(gè)元素都為滿足覆蓋要求的感知方向集合;對(duì)于每一個(gè)節(jié)點(diǎn)Si的每一個(gè)感知方向Di，j，求解其對(duì)應(yīng)的COVi，j和D_Ti，j;

2）符合覆蓋要求的集合求解： 對(duì)于每個(gè)傳感器節(jié)點(diǎn)的每個(gè)感知方向，計(jì)算COVi，j [×]Li 的值，并按照值的大小進(jìn)行排序;

3）節(jié)點(diǎn)參數(shù)和監(jiān)測(cè)目標(biāo)覆蓋狀況更新。通過(guò)每一次選擇合適的感知方向后，考慮到同一時(shí)刻一個(gè)傳感器節(jié)點(diǎn)只能有一個(gè)感知方向處于工作狀，將該感知方向和該感知方向所屬的傳感器節(jié)點(diǎn)刪除。當(dāng)所有的監(jiān)測(cè)目標(biāo)都符合覆蓋要求時(shí)，更新有向傳感器節(jié)點(diǎn)的壽命，同時(shí)重新計(jì)算COVi，j [×]Li 的值。若有壽命為0的傳感器節(jié)點(diǎn)，則將此節(jié)點(diǎn)從可用傳感器節(jié)點(diǎn)集合S_K中刪除。并且將變量Req_T、uncovered_T和isUsed按照（1）重新初始化，繼續(xù)下一輪的貪婪算法，直到節(jié)點(diǎn)壽命為0或沒(méi)有符合覆蓋要求的節(jié)點(diǎn)集合。每一輪貪婪算法的主要步驟為：

（1）判斷當(dāng)前可用的感知方向是否能符合目標(biāo)覆蓋的要求，若不符合直接執(zhí)行6）;否則執(zhí)行2） ;

（2）當(dāng)uncovered_T不空時(shí)（或者還有未符合覆蓋要求的監(jiān)測(cè)目標(biāo)時(shí)），選擇值最大的COVi，j [×]Li，并將傳感器節(jié)點(diǎn)的序號(hào)和感知方向序號(hào)放入集合Result，即Result=Result∪{{i，j}}。若值最大的感知方向有多個(gè)則選擇序號(hào)最小的節(jié)點(diǎn)和感知序號(hào) ;

（3）更新所選節(jié)點(diǎn)的isUsed數(shù)組的值，設(shè)為1 ;

（4）根據(jù)D_Ti，j，更新監(jiān)測(cè)目標(biāo)要求集合temReq_T。根據(jù)更新集合的情況，若已有監(jiān)測(cè)目標(biāo)符合覆蓋要求，則更新未覆蓋目標(biāo)集合uncovered_T ;

（5）繼續(xù)執(zhí)行步驟2），否則執(zhí)行步驟6）;

（6）得到求解結(jié)果R 。

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

4.1 仿真環(huán)境設(shè)置

在MATLAB平臺(tái)對(duì)本文提出的算法進(jìn)行仿真驗(yàn)證。節(jié)點(diǎn)部署區(qū)域設(shè)為50×50，部署節(jié)點(diǎn)數(shù)量N為30，節(jié)點(diǎn)的其他參數(shù)設(shè)置如表4所示。監(jiān)測(cè)目標(biāo)數(shù)T為6，分為兩種類型：重點(diǎn)目標(biāo)和非重點(diǎn)目標(biāo)，其中對(duì)于重點(diǎn)目標(biāo)，要求覆蓋度不少于2，其余目標(biāo)覆蓋度為1，每一種類型的監(jiān)測(cè)目標(biāo)數(shù)量隨機(jī)產(chǎn)生。β和聲搜索算法的參數(shù)設(shè)置為：種群數(shù)為50，迭代次數(shù)為400，HMCR為0.8，PAR =0.4，BW = 0.01。模擬退火算法中T = T0=100， α=0.99。

4.2 仿真結(jié)果及分析

1）不同節(jié)點(diǎn)密度下集合數(shù)目比較

為比較改進(jìn)算法IHS和原始IHS算法在問(wèn)題求解過(guò)程中的性能，對(duì)兩種算法在求解過(guò)程中的平均適應(yīng)度進(jìn)行比較。結(jié)果如圖2所示。從圖中可以看出，隨著部署節(jié)點(diǎn)數(shù)量的增加，IHS算法、原始HS算法和貪婪算法求得的滿足條件的集合數(shù)量也隨之增加，究其原因在于，節(jié)點(diǎn)數(shù)量增加后能參與目標(biāo)覆蓋的感知方向隨之增加，滿足覆蓋要求的感知方向集合也就相應(yīng)的增加;在部署節(jié)點(diǎn)數(shù)和監(jiān)測(cè)目標(biāo)數(shù)量一定的條件下，改進(jìn)HIS算法優(yōu)于原始HS算法和貪婪算法，證明了IHS算法改進(jìn)方案的有效性。

2）適應(yīng)度比較

將監(jiān)測(cè)目標(biāo)數(shù)T設(shè)為6，節(jié)點(diǎn)數(shù)N為45，其他參數(shù)如4.1設(shè)置，比較改進(jìn)算法IHS和原始和聲搜索算法HS的平均適應(yīng)度，每個(gè)算法運(yùn)行30次，并取30次實(shí)驗(yàn)的平均值作為算法的結(jié)果。仿真結(jié)果如圖3所示。從圖中可以看出，隨著迭代次數(shù)的增加，平均適應(yīng)度都在增加，且趨于收斂;同時(shí)，改進(jìn)算法IHS的平均適應(yīng)度優(yōu)于原始和聲搜索算法，證明了改進(jìn)算法的有效性。

5 結(jié)論

本文提出了一種基于改進(jìn)和聲搜索算法的節(jié)點(diǎn)調(diào)度策略，解決在異構(gòu)有向傳感器節(jié)點(diǎn)網(wǎng)絡(luò)中面向不同目標(biāo)監(jiān)測(cè)要求的情形下的傳感網(wǎng)壽命的最大化問(wèn)題。在未來(lái)，將研究分布式的異構(gòu)有向傳感器節(jié)點(diǎn)調(diào)度策略，降低集中式算法執(zhí)行過(guò)程中消息通信帶來(lái)的功耗，從而進(jìn)一步優(yōu)化異構(gòu)有向傳感器網(wǎng)絡(luò)的能源使用效率。

參考文獻(xiàn)：

[1] H.Shen， G.Bai. Routing in wireless multimedia sensor networks： A survey and challenges ahead[J]. Journal of Network and Computer Applications， 2016， 71：30-49.

[2] P. Musilek， P. Kr?mer， T. Bartoň. Review of nature-inspired methods for wake-up scheduling in wireless sensor networks[J]. Swarm and Evolutionary Computation， 2015， 25：100-118.

[3] 溫俊， 蔣杰， 竇文華.公平的有向傳感器網(wǎng)絡(luò)方向優(yōu)化和節(jié)點(diǎn)調(diào)度算[J].軟件學(xué)報(bào)， 2009，20（3）： 644-659.

[4] 高睿. 有向傳感器網(wǎng)絡(luò)覆蓋和節(jié)點(diǎn)冗余算法研究[D].太原： 太原理工大學(xué)， 2018.

[5] 黃帥，程良倫. 一種面向目標(biāo)的有向傳感器網(wǎng)絡(luò)連通覆蓋算法[J].傳感器與微系統(tǒng)， 2012，31（1）： 65-68，72.

[6] A. Singh， A. Rossi， M. Sevaux. Heuristics for lifetime maximization in camera sensor networks[J]. Information Sciences. 2017，385–386： 475–491.

[7] S. Sharmin， F.N. Nur， M.A. Razzaque， M.M. Rahman， A. Almogren， M.M. Hassan.Tradeoff between sensing quality and network lifetime for heterogeneous target coverage using directional sensor nodes[J]. IEEE Access 2017，5：15490–15504.

[8] A.Alibeiki， H.Motameni，H. Mohamadi. A new genetic-based approach for maximizing network lifetime in directional sensor networks with adjustable sensing ranges[J]. Pervasive and Mobile Computing， 2019，52： 1–12.

[9] 李明，胡江平.基于學(xué)習(xí)自動(dòng)機(jī)的異構(gòu)有向傳感器節(jié)點(diǎn)調(diào)度算[J].計(jì)算機(jī)工程，2018， 44（8）：199-203.

[10] T. Zhang， Z.W.Geem. Review of harmony search with respect to algorithm structure[J]. Swarm and Evolutionary Computation， 2019，48（8）： 31-43.

[11] 李明，曹曉莉，胡衛(wèi)軍.基于多目標(biāo)和聲搜索的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法[J].儀器儀表學(xué)報(bào)，2014，35（1）：162-168.

[12] Cardei M.， Thai M， Li Y. ， et al. Energy-efficient target coverage in wireless sensor networks. In Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies （INFOCOM）， Miami， FL， USA， 13-17 March 2005，2005： 1976-1984.

[13] Ishibuchi HMurata.Multi-Objective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling[J].? IEEE Trans. Syst. Man. Cy. B， 1998，28（3） ：392-402.

【通聯(lián)編輯：代影】