異構有向傳感器網絡連通覆蓋調度算法

李 明，胡江平，曹曉莉

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

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

針對上述研究中存在的問題，在滿足應用場景監測目標覆蓋要求差異化和網絡連通的條件下，本文提出一種面向異構有向傳感器網絡的節點調度算法，達到降低網絡能耗和延長網絡工作時長的目標。

1 問題描述及數學建模

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

定義傳感網絡的壽命[12]網絡中的傳感器節點能提供符合監測目標的監測要求且能保持網絡連通的時間。

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

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

圖1 監測目標出現區域示意圖

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

2 連通覆蓋調度算法

2.1 原始珊瑚礁優化算法

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

2.2 增強的珊瑚礁算法

1) 種群初始化策略的改進

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

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

第二部分種群使用反向學習產生，先隨機產生種群中每個染色體的初始值P=(p1,p2,···,pn),pi∈[L,H]，每個染色體的基因為：

2)非性繁殖過程的改進

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

式中，k為當前的迭代次數；K為最大迭代次數；PARmax=0.8； PARmin=0.8[20]。

差分變異操作中差分變異策略和控制參數對算法的性能有重要影響。為增強算法性能，采用自適應變異策略和設置控制參數，變異策略為：

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

采用自適應的參數選擇策略，具體為：

式中，Fmin和Fmax分別表示F的最小值和最大值。當種群個體有早熟的趨勢時，采用較大的F值進行抑制，保持種群的多樣性；反之，當種群個體收斂較慢時，采用較小的F值加快種群的收斂；其他情況下，產生隨機的F。

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

在競爭和淘汰過程之間增加最差個體提升過程，通過兩種方法改善其優化能力，并通過適應度評價選擇兩種方法中改善效果最顯著的作為其最終的結果。如式(8)的反向學習操作和式(9)的差分操作：

式中，變量L和H分別表示解的最小值和最大值；函數rand()為產生0～1 的隨機數；和分別為循環次數為t時種群中適應度最差和最好的個體；F為差分參數，在區間[0.1, 0.9]隨機取值。通過適應度評價，選擇式(8)和式(9)中表現較好的作為最差個體新的解，可使其跳出其目前所處最差區域，增強其優化能力。

2.3 壽命最大化問題的求解

通過求解盡可能多滿足覆蓋連通要求的集合，達到延長網絡壽命的目的。每次循環完畢后，珊瑚礁算法輸出種群中的最優解，執行節點能量的更新，反復迭代，直到滿足算法終止的條件。其中要解決解質量的評價和如何表示解這兩個關鍵問題。

1) 解質量的評價

對于珊瑚礁算法而言，解質量的評價也就是設計健康度函數。針對解決問題的特點，設計了3 個優化目標：① 形成盡可能多的滿足監測要求的集合；② 形成滿足要求的集合后，節點的剩余能量最多；③ 最后一個是要求集合中節點的連通度越高越好。用形式化的語言描述為：

式中，W′表示符合監測覆蓋要求的監測目標數量；W表示監測目標的數量；f1的值域為[0,1]；f2是用雙曲正切函數表示的剩余能量的函數，取值范圍為[0,1]；β 是權重系數，在文中設為1；f3值域為[0,1]。

利用隨機線性加權的方法[21]將多目標優化問題變成單目標優化問題，即：

式中， γ1、 γ2和 γ3為f1、f2和f3對 應的系數； r andi為區間(0,1)之間的隨機數。

2) 解的表示

考慮到求解問題的特點，對節點和感知方向進行整數編號，根據該編號能確定屬于節點的感知方向，如圖2 所示。

圖2 解的示意圖

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

2.4 ECRO 算法時間復雜度分析

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

3 實驗與分析

本節首先測試增強珊瑚礁算法ECRO在數值計算上的性能，然后將其用于解決異構有向傳感器網絡壽命最大化的問題。

3.1 數值運算

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

表1 測試函數具體信息

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

表2 結果比較

3.2 覆蓋調度算法性能比較

3.2.1 仿真環境配置

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

表3 節點參數表

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

3.2.2 結果分析

1) 收斂性能比較

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

圖3 算法平均適應度比較

2) 監測要求與網絡壽命的關系

假定監測目標數目W=8，用M′代表重點監測目標的數量，其值分別設為3 和5；k′代表重點監測目標對應的監測覆蓋要求，其值分別設為2 和3，用ECRO 算法求解覆蓋連通問題。從圖4 求解得到的結果可以看出：1)節點數越多，網絡壽命越長。2)節點數和監測覆蓋要求k′固定時，重點目標數M′越大，相應地網絡壽命也就越短。3)節點數和重點目標數M′固定時，重點目標的監測覆蓋要求k′越大，網絡壽命就越短。

圖4 不同覆蓋要求對節點壽命的影響

3) 均勻比例下節點數量對網絡壽命的影響

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

圖5 算法比較

4) 非均勻比例下節點數量對網絡壽命的影響

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

表4 節點構成比例表

圖6 不同節點構成比例下網絡壽命的比較

4 結 束 語

本文提出了一種基于增強珊瑚礁算法的網絡壽命最大化策略，解決應用場景中監測目標差異化的監測要求和網絡連通條件下異構有向傳感器節點調度的問題。相比現有的節點調度算法，本文研究問題的特色在于，節點異構、監測目標差異化監測和網絡連通的要求更加符合有向傳感器網絡部署的實際情況。未來將應用本文提出的方法研究三維空間內的異構有向傳感器網絡節點的覆蓋連通調度問題；另外在網絡連通方面，將引入中繼節點實現網絡多跳連通，在此基礎上研究更寬泛意義上的異構有向傳感器網絡連通覆蓋調度算法，使得算法更具實用性。