面向不同目標覆蓋要求的異構有向傳感器網絡節點調度算法

李明　林新宇　彭鵬

摘要：針對給定部署區域中不同的監測目標有不同的覆蓋需求和現有的調度算法大多針對同構有向傳感器節點忽略了節點異構對調度性能的影響的問題，提出兩種異構有向傳感器網絡節點調度策略。一種方法是通過對問題進行數學建模，將節點調度問題轉化為目標優化問題，采用改進的和聲搜索算法進行求解。改進和聲搜索算法針對原始和聲搜索在陷入局部最優時的過早收斂問題，通過將和聲搜索算法和模擬退火算法結合增強其局部搜索能力。另一種方法采用貪婪算法求解滿足條件的節點集合。仿真結果顯示，與原始和聲搜索算法相比，改進和聲搜索算法能有效提高網絡的工作時間，證明了改進算法的有效性。

關鍵詞：有向傳感器網絡;異構網絡;和聲搜索算法;模擬退火算法;節點調度

中圖分類號：TP393? ? 文獻標識碼：A

文章編號：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

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

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

1 問題模型分析

假定平面區域A中，分布有N個有向傳感器節點和T個需要監測的目標Ti （i =1，2，...，T），假定有向傳感器節點的感知方向Di的數量為|Di|（i =1，2，...，N）和壽命Li （i =1，2，...，N）均不同，且同一時刻只能有一個感知方向處于工作狀態。監測目標具有不同的優先級，分為優先級高的監測目標和優先級低的監測目標，其中優先級高的監測目標要求同時被多個傳感器節點監測（覆蓋）到，優先級低的監測目標只要被傳感器節點監測到即可。如何在保證滿足監測目標監測的要求條件下，盡可能延長傳感器網絡的壽命是本文要研究的問題。

根據上文的闡述，我們采用集合覆蓋的思想，將傳感器網絡節點集合劃分成多個符合監測目標監測覆蓋要求的集合，通過集合之間不同的切換，達到延長網絡壽命的目標。用形式化的語言可描述為：

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

2 改進和聲搜索算法

2.1 原始和聲搜索算法簡介

和聲搜索算法通過對音樂家的創作過程進行模擬，將決策變量和解向量分別類比樂器的音調和各種音調的和聲，優化目標和種群分別類比適應度（評價）函數和和聲記憶庫，通過不斷的迭代優化來實現問題的求解[10]。算法步驟包括初始化和聲記憶庫（ harmony memory，HM），新產生的解有兩部分來源，一部分來源于HM，其占比為HMCR;另一部分在問題可行區域內隨機取值。來源于HM的新解以概率PAR用參數BW進行局部擾動。若新產生解的適應度函數優于HM原有的最差解，則新解替換最差解。算法不斷迭代進行上述步驟直到滿足停止的條件[11]。

原始的和聲搜索若在算法初始化時產生的解向量若在問題的局部值附近，則容易陷入早熟收斂，影響算法的優化效率。針對這一問題，借鑒模擬退火算法的思想和其局部搜索能力強的優點，將模擬退火算法與和聲搜索算法結合，提出一種改進的和聲搜索算法

2.2 改進的和聲搜索算法IHS

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

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

輸出：最優和聲（解向量）

初始化和聲搜索算法參數HMCR ，PAR， BW和和聲記憶庫HMS

初始化模擬退火算法T0，并設T=T0

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

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為和聲搜索算法迭代過程，行2先尋找當前的最差的和聲個體，行3-行12對于每個和聲個體的每一維執行和聲算法步驟，也就是每一維有概率HMCR來源自原來的和聲記憶庫HM，這部分個體中有PAR比率的個體會進行參數為BW的隨機擾動以增加個體多樣性;有1-HMCR概率是在問題可行區域內隨機取值。對于新產生的和聲個體若優于最差和聲（行14，此處假定求最小值問題）或者滿足rand（）<[e-DifT']條件（行14），則新個體替換最差個體。算法最后輸出最優和聲個體作為問題的解。Dim為優化問題的維數，函數f（）為待求解問題的函數，rand（）為區間（0，1）之間的隨機數;函數rand_int（A，B）為返回整型數A到B之間的隨機整數;col（C）作用為返回向量C的列向量個數。

2.3 節點調度問題的求解

利用和聲搜索算法解決異構節點調度問題時，要解決優化目標的選擇，適應度函數的設計，以及解的表示也就是編碼問題三個關鍵問題。

1）優化目標

對于本文的優化問題，一方面要使滿足覆蓋條件的集合數量最大化，另一方面使得節點剩余壽命（跟節點的能量成正比）最大化。根據文獻[12]滿足覆蓋條件節點集合數的上限值K為能覆蓋監測要求最高目標的節點的壽命（若有多個節點，則選擇壽命最小的）與監測要求最大值的比值，即[K=Lgmax（t）]，其中，L表示能覆蓋監測要求最高目標的節點的壽命;gmax（t）表示監測目標中監測要求最大的值。

本文要優化的目標有兩個：符合覆蓋要求的節點集合和節點的剩余壽命，即：

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

2）適應度設計

根據對優化目標的分析，對于本文的多目標優化算法，采用文獻[13]隨機加權的方式，將多目標優化問題轉化為單目標優化問題。兩個目標函數對應的權值按照下面的式子確定：

3）問題編碼表示

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

3 貪婪算法

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

1） 初始化算法參數，包括可用的傳感器集合S_K，設置其初值為所有的傳感器節點;目標監測要求集合Req_T，并設置臨時目標監測要求集合temReq_T，使其等于Req_T;傳感器節點的壽命Li;已覆蓋目標集合covered_T ={}，未覆蓋目標集合uncovered_T ，并賦初值為監測目標集合T;節點是否用過數組isUsed，并設初值為0，表示所有節點均沒用過;存儲滿足覆蓋條件的結果集合Result = {}，該集合中每個元素都為滿足覆蓋要求的感知方向集合;對于每一個節點Si的每一個感知方向Di，j，求解其對應的COVi，j和D_Ti，j;

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

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

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

（2）當uncovered_T不空時（或者還有未符合覆蓋要求的監測目標時），選擇值最大的COVi，j [×]Li，并將傳感器節點的序號和感知方向序號放入集合Result，即Result=Result∪{{i，j}}。若值最大的感知方向有多個則選擇序號最小的節點和感知序號 ;

（3）更新所選節點的isUsed數組的值，設為1 ;

（4）根據D_Ti，j，更新監測目標要求集合temReq_T。根據更新集合的情況，若已有監測目標符合覆蓋要求，則更新未覆蓋目標集合uncovered_T ;

（5）繼續執行步驟2），否則執行步驟6）;

（6）得到求解結果R 。

4 仿真結果與分析

4.1 仿真環境設置

在MATLAB平臺對本文提出的算法進行仿真驗證。節點部署區域設為50×50，部署節點數量N為30，節點的其他參數設置如表4所示。監測目標數T為6，分為兩種類型：重點目標和非重點目標，其中對于重點目標，要求覆蓋度不少于2，其余目標覆蓋度為1，每一種類型的監測目標數量隨機產生。β和聲搜索算法的參數設置為：種群數為50，迭代次數為400，HMCR為0.8，PAR =0.4，BW = 0.01。模擬退火算法中T = T0=100， α=0.99。

4.2 仿真結果及分析

1）不同節點密度下集合數目比較

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

2）適應度比較

將監測目標數T設為6，節點數N為45，其他參數如4.1設置，比較改進算法IHS和原始和聲搜索算法HS的平均適應度，每個算法運行30次，并取30次實驗的平均值作為算法的結果。仿真結果如圖3所示。從圖中可以看出，隨著迭代次數的增加，平均適應度都在增加，且趨于收斂;同時，改進算法IHS的平均適應度優于原始和聲搜索算法，證明了改進算法的有效性。

5 結論

本文提出了一種基于改進和聲搜索算法的節點調度策略，解決在異構有向傳感器節點網絡中面向不同目標監測要求的情形下的傳感網壽命的最大化問題。在未來，將研究分布式的異構有向傳感器節點調度策略，降低集中式算法執行過程中消息通信帶來的功耗，從而進一步優化異構有向傳感器網絡的能源使用效率。

參考文獻：

[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] 溫俊， 蔣杰， 竇文華.公平的有向傳感器網絡方向優化和節點調度算[J].軟件學報， 2009，20（3）： 644-659.

[4] 高睿. 有向傳感器網絡覆蓋和節點冗余算法研究[D].太原： 太原理工大學， 2018.

[5] 黃帥，程良倫. 一種面向目標的有向傳感器網絡連通覆蓋算法[J].傳感器與微系統， 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] 李明，胡江平.基于學習自動機的異構有向傳感器節點調度算[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] 李明，曹曉莉，胡衛軍.基于多目標和聲搜索的無線傳感器網絡分簇路由算法[J].儀器儀表學報，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.

【通聯編輯：代影】