異構傳感網成本優化的節點部署策略

李 明，胡江平，曹曉莉

(1.重慶工商大學 檢測控制與系統集成重點實驗室，重慶 400067；2.電子科技大學 自動化工程學院，四川 成都 611731)

節點部署技術是傳感器網絡的一項關鍵技術，對傳感器網絡性能有著重要影響[1-2]。按照部署方式，節點部署分為確定性部署和隨機部署。確定性部署是指在部署前已知節點位置信息或網絡狀態較為穩定的部署技術。如何在確定性部署的方式下保障網絡的連通性和覆蓋性能，備受研究者青睞[1]。文獻[3]提出一種能量有效的采用分簇拓撲結構的分布式覆蓋算法，但其為保證網絡連通性的路由構造算法較為復雜。文獻[4]提出了一種適用于同構節點構成的無線傳感器網絡最小剛性拓撲控制算法以滿足覆蓋與節能應用需求。文獻[5]提出了一種基于量子退火算法的無線傳感器網絡二維目標覆蓋算法，但文獻研究對象是同構傳感器網絡。文獻[6]提出了一種基于選擇框的，含有最少節點的有向強柵欄覆蓋算法。文獻[7]提出了兩種基于Voronoi的移動無線傳感器網絡覆蓋控制方法用于優化在給定區域內無線傳感器網絡的覆蓋控制。文獻[8]利用遺傳算法解決異構傳感器網絡中覆蓋優化問題，但未考慮到網絡連通問題。文獻[9]提出一種基于和聲搜索算法的同構節點部署策略，但忽略了工程實踐中異構節點才是節點的普遍狀態。同時該文章假定節點部署成本在整個區域中都是相同的，與節點的部署實際不符。上述文獻[3-9]對解決節點覆蓋問題提出了有效方案，然而卻大多忽略了節點之間的相互通信，也就是傳感器網絡的連通性問題。同時僅適用于同構節點構成的傳感網絡，當應用于異構網絡時存在諸多限制。文獻[10]利用粒子群算法解決節點非均勻分布條件下異構傳感網絡的覆蓋控制問題，但未考慮網絡的連通性問題，導致成果的適用性受到限制。針對用最少的傳感器節點覆蓋感興趣區域并確保傳感器節點之間連通的最優化問題，文獻[11]提出了基于集合覆蓋的傳感器網絡目標覆蓋算法。文獻[12]對網絡中存在移動sink節點的連通覆蓋算法進行研究。但該算法僅適用于同構節點構成的網絡。文獻[13]提出一種面向能量異構的期望網絡覆蓋優化算法。文獻[14]對節點異構條件下的傳感器網絡覆蓋問題進行研究，忽略了網絡的連通性。

上述文獻盡管對傳感器網絡的覆蓋問題進行研究并取得了一定成果，但大多忽視了網絡連通性問題，也就是不僅要保證對象被監測和感知到，同時還要把監測到的數據傳輸到后臺以進行處理。還應注意到，應用于工程實踐的傳感器由于制造工藝或類型不同(比如，溫度傳感器、濕度傳感器和紅外傳感器等)，其感知半徑、通信半徑和成本等參數也不同。現有的研究成果大多假定傳感器網絡由相同參數的節點構成，將這些研究成果應用于由不同參數的節點構成的傳感器網絡中有很大的局限性。再者，傳感器網絡節點經常部署在惡劣的工作環境中，由于能量耗盡、物理環境和人為破壞導致節點的故障率較高。如何保證網絡的容錯性和提供可靠的監測服務，對于面向目標監測的傳感器網絡至為重要。最后，上述研究成果在部署節點時，大多假定區域中節點的成本相同，未考慮到由于部署位置差異造成的部署成本不同。

針對這些問題，考慮到目標監測應用中部署節點眾多、網絡連通和目標覆蓋性能不高和容錯性差的特點，筆者針對在給定的具有不同代價的部署位置中如何部署具有不同性能參數的傳感器節點，使得在同時滿足監測目標多重覆蓋和部署傳感器節點之間多重連通條件下的成本優化問題進行研究，提出了一種適合目標監測的最小代價的異構傳感器網絡容錯部署策略。通過構建異構傳感器節點的多重連通覆蓋數學模型，借助改進的珊瑚礁算法對優化問題進行求解，在部署代價優化條件下，保證傳感器網絡的多重覆蓋和連通性能。

1 系統模型與問題描述

1.1 節點感知模型和連通模型

節點的感知模型是研究網絡覆蓋性能的關鍵。筆者使用布爾感知模型，通過判斷目標ti與節點si的距離與節點si的感知半徑的關系決定監測目標是否被傳感器節點覆蓋。若為小于等于關系，那么目標ti被節點si感知(覆蓋)。對于k覆蓋和c連通，筆者采用文獻[9]中的概念。

概念1(k覆蓋)k覆蓋是指在節點部署區域中，每個監測對象ti(i=1，2，…，W)至少能被k個傳感器節點感知(覆蓋)[9]。

概念2(連通) 若節點si和節點sj之間距離不大于節點si的通信半徑，則兩個節點si和sj是連通的。注意：此處的連通對同構節點來說是雙向連通，對于異構節點則為單向連通[9]。

概念3(c連通)c連通是指每個部署在監測區域的傳感器節點都至少與c個部署在監測區域內傳感器節點連通[9]。

1.2 問題描述

在工程實踐中，為了更準確地刻畫監測對象的性質，可在監測對象周圍部署不同類型(參數)的傳感器節點。比如，在野外動植物監測系統中，通常要部署溫度傳感器節點、濕度傳感器節點、紅外傳感器節點和視頻采集傳感器節點等。這些傳感器節點的感知半徑、通信半徑、成本等參數均不相同(或者即使同一種類型的傳感器節點由于制造工藝等原因其參數也不完全相同)，同時由于部署位置不同和傳感器本身的特點使得節點部署代價均不同。如何在保證監測質量和網絡容錯性的前提下，以經濟的方式部署傳感器節點，是一個非常重要的問題。

對上述的工程實踐問題進行抽象，也就是：假定二維監測區域內有W個監測對象ti(i=1，2，…，W) 和M個用于部署傳感器節點的位置Pi(i=1，2，…，M)，每個部署位置的代價為di(i=1，2，…，M)。其中，每個監測目標ti的位置已知，且每個位置只能部署一個傳感器節點。如何在現有的M個候選位置中，選擇合適的部署位置(不同部署位置的部署代價不同)部署傳感器節點si，u(傳感器節點性能參數和成本不同)，在滿足所有的監測目標能夠被傳感器節點k覆蓋(k≥1)和布設的傳感器節點之間能夠c連通(c≥1)的條件下，網絡部署成本最小。假定傳感器節點si，u的性能指標諸如感知半徑、通信半徑和成本bi，u均不同，按照性能指標進行分類，有U種類型(u=1，2，…，U)。最小網絡部署成本用數學語言描述為

(1)

(2)

約束(1)為每個監測目標為k覆蓋；約束(2)為布設的異構傳感器節點之間滿足c連通的條件，S為選擇的部署位置的數量。

命題：要解決的問題為NP-complete問題。

證明：首先證明其為NP問題，然后通過歸約方式證明該問題的一個特殊情形(或稱特例)是NP-complete 問題，從而證明該問題為NP-complete問題。

假設A為問題的一個解，采用廣度遍歷算法驗證以當前部署位置節點為根節點的樹是否符合c連通要求，其時間復雜度為O(M2)。接著，來驗證對于每個監測目標是否符合k覆蓋的要求。可知驗證M個節點W個監測目標是否滿足k覆蓋，其時間復雜度為O(M×W)。可以看出，驗證解A是否滿足覆蓋和連通的要求需要多項式的時間。因此，首先證明要解決的問題是NP問題。

當候選部署位置的部署代價都相同，且用于部署的傳感器節點類型和成本都相同，要解決的成本優化問題，即轉化成了如何在候選位置集合中選擇最少的部署位置，使得部署的傳感器節點滿足k覆蓋，并且每個傳感器節點的類型和成本都相同。而這一問題已經在文獻[15]和文獻[16]中被證明了是一個NP-complete問題。綜上，命題得證，要解決的問題是NP-complete問題。

考慮到要解決的問題是NP-complete問題，傳感器網絡大規模部署以及資源受限的情況，傳統的算法比如窮舉方式耗費資源較多，因此，筆者采用生物啟發式算法得到算法的近似解。

2 基于改進珊瑚礁算法的異構傳感器網絡容錯部署策略

2.1 珊瑚礁算法

圖1 珊瑚礁算法流程圖

珊瑚礁算法(Coral Reef Optimization algorithm，CRO)是由SALCEDO-SANZ在2014年提出的一種模擬珊瑚蟲行為的智能進化算法[17]，具有良好的搜索能力和收斂速度。目前已應用于北歐風力農場設計優化[17]、有向傳感器網絡資源優化[18]、約束條件下的移動傳感器網絡部署問題[19]等組合優化問題。該算法的流程圖如圖1所示。

圖1中，種群初始化主要完成算法參數的設置，包括附著珊瑚蟲的珊瑚礁的大小，一般設為矩形；附著珊瑚蟲的珊瑚礁占總珊瑚礁的比例r1，最大迭代次數T1，非性繁殖(即雌雄同體)的比例Fa，進化過程中子代允許附著的最大次數T2，每次迭代珊瑚蟲被淘汰的概率g1和淘汰的數量比例r2。珊瑚蟲的繁殖過程分為兩類，一類為雌雄同體的繁殖過程，通過在可行區域內隨機產生，另一類為雌雄異體的繁殖過程，通過模擬二進制交叉的方式產生2個子代。競爭過程，也就是子代珊瑚蟲尋找珊瑚礁的過程，若尋找到的珊瑚礁無其他珊瑚蟲附著，則尋找成功，該珊瑚蟲附著于此，否則若已有其他珊瑚蟲附著此珊瑚礁，則比較兩個珊瑚蟲的健康度(即適應度)，適應度優的珊瑚蟲勝出，占有該珊瑚礁。此過程一直繼續，直到達到最大允許的嘗試次數T2。若達到最大允許的嘗試次數T2時仍沒找到，則該珊瑚蟲死亡。淘汰過程為按照初始化時設定的淘汰概率g1和淘汰數量比例r2自動淘汰部分珊瑚蟲，被淘汰的珊瑚蟲附著的珊瑚礁就會被空出，以便供其他的珊瑚蟲進行競爭。

2.2 改進珊瑚礁算法

改進算法(Enhanced version of CRO，ECRO)依然沿用圖1所示的原始的珊瑚礁算法的流程。為了增強原始CRO算法的優化能力，一方面，借鑒和聲搜索算法[20]中具有良好全局優化能力的HMCR過程和PAR局部擾動過程，并將其引入CRO算法，進一步增強算法的全局優化能力；另一方面，充分利用算法求解過程中得到的優秀解，使其更好地發揮“引導”作用。具體改進之處在于以下兩點。

(1) 與和聲搜索算法結合

和聲搜索算法中新產生的解向量一方面來自和聲記憶庫(Harmony Memory，HM)，其概率為H；另一方面，新產生解向量來自變量允許的范圍內的隨機取值，其概率為 1-H。在新的解向量產生后，對來自和聲記憶庫的解向量以概率P進行局部微調[20]。通過參數H和參數P控制解產生的來源和解質量，從而使得算法具有良好的優化能力。結合原始CRO算法中雌雄異體的珊瑚蟲隨機產生后代的方式，筆者借鑒和聲搜索算法中產生子代過程，將雌雄異體的珊瑚蟲子代設定有H比例是來自于雌雄異體的珊瑚蟲個體，其余的1-H比例的雌雄同體的珊瑚蟲子代為按式(3)隨機產生。對于雌雄同體的珊瑚蟲產生子代后，以概率P進行局部擾動(類似遺傳算法的變異操作)，從而增強CRO算法的優化能力和避免過早收斂。固定數值的H和P不能根據算法過程中種群的進化情況做出相應的調整，對算法的優化能力產生不利影響。為此，采用文獻[21]中自適應的算法參數，即

(3)

(4)

其中，x為當前的迭代次數，X為最大迭代次數，Hmin和Hmax分別為H的最小值和最大值，Pmin和Pmax分別為P的最小值和最大值。隨著迭代次數的增加，H的值逐漸減少，P的值逐漸增大，使得雌雄異體子代一方面通過H參數的控制能保持原有種群的優化能力，另一方面P的擾動增強了算法的局部搜索能力，使得算法的探索能力和開發能力得以平衡，滿足問題求解的需求。

(2) 算法中優秀基因再利用

2.3 改進珊瑚礁算法時間復雜度分析

2.4 應用ECRO求解異構傳感器網絡容錯部署問題

對于節1.2所描述的異構傳感網絡的容錯部署問題，通過數學建模，將其轉換成目標優化問題，以筆者提出的ECRO算法為工具得到優化的部署策略。結合待解決問題的特點，算法的關鍵部分敘述如下：

(1) 解的編碼

珊瑚礁種群中的每個個體表示問題的一個解，解的維數為M×U，解的編碼示意圖如圖2所示。

圖2 解的編碼示意圖

圖2中，解的每個位置pi，h表示第i個候選位置里是否部署傳感器節點，也就是

(2) 健康度函數的設計

根據要解決的問題，在滿足監測目標k覆蓋和布設傳感器節點之間c連通的條件下，在給定的位置集合中選擇合適的位置布設合適的節點，使得部署成本最低，設計合適的健康度函數(適應度函數)。對于要處理的約束問題，采用將約束優化問題轉化為多目標優化問題。結合前面的分析，筆者優化的目標有3個，分別為：

(5)

(6)

(7)

其中，max(bi，u) 表示成本最大的傳感器節點。

(8)

(9)

S為選擇的部署位置的數量，即布設在監測區域的傳感器節點數量。對于上述3個優化目標選取的依據為：一方面，要保證沒有量綱；另一方面，使目標函數的取值在[0，1]之間，也就是進行歸一化處理。

對于3個優化目標在進行優化時是相互沖突的。這主要由于，一方面要保證節點的多重連通和目標的多重覆蓋，使得必須選擇更多的候選位置來部署更多的節點，而這導致部署成本的增加；另一方面，為降低網絡部署成本，使得部署位置和部署節點類型的選擇受到限制，從而又影響了網絡的連通性和目標的覆蓋。加權方式作為一種經典的多目標轉化為單目標的方法，廣泛應用在傳感器網絡資源優化上[22-23]。筆者用子目標加權的方法將多目標函數優化轉換成單目標函數優化問題，即

F=α1f1+α2f2+α3f3，

(10)

其中，α1+α2+α3=1，αi∈[0，1]，i=1，2，3。f1為部署代價的子目標函數，其值域為[0，1]；f2為k覆蓋的子函數，值域為[0，1]；f3為c連通的子函數，取值范圍為[0，1]。F為最終要優化的目標函數，α1、α2和α3為3個子函數所對應的權重。F為[0，1]之間的一個值，該值越大，表示得到的解越好。

3 仿真及結果分析

3.1 仿真環境設置

表1 傳感器參數表

在MATLAB 2013b平臺上對提出的算法進行數值仿真驗證。監測區域大小設置為200 m×200 m，監測目標數量W為75，可部署傳感器節點的位置M為400。每個候選位置布設節點的代價為區間[1，5]上隨機數(假定代價單位為￥)。采用文獻[21]的模型，假定節點的通信半徑是其感知半徑的2倍。考慮到工程實踐中，節點的參數性能越高，價格越貴。假定傳感器節點的性能參數如表1所示。

對于部署傳感器節點的位置，預設兩種情形，情形1：部署傳感器節點的位置隨機分布在監測區域內；情形2：首先將監測區域劃分成大小為10 m×10 m的網格，每個網格的中心點即為部署傳感器節點的位置。CRO算法中，矩形區域設為10×5，Fa=0.1，r1=0.7，T2=3，g1=0.1，r2=0.01[17]；ECRO算法中，Hmin=0.6，Hmax=0.8，Pmin=0.05，Pmax=0.3[20]，最大迭代次數T1為400，E=1，其他參數設置同CRO算法。進行優秀基因再利用中的參數Z設置為當前迭代次數能整除20時進行。

下面通過仿真實驗來檢驗提出的ECRO算法的性能表現。為確保結果的可信性，每一個仿真結果均為50次獨立運行算法所得到結果的平均值。

3.2 仿真結果及分析

(1) 不同權重下子目標比較

設置覆蓋度k=2和連通度c=2，分別在情形1和情形2兩種情形下對改進算法和未改進珊瑚礁算法的3個子函數進行比較，仿真實驗結果詳見表2和表3。

表2 情形1不同權重下子目標取值

表3 情形2不同權重下子目標取值

從結果可以看出，在不同的權值系數條件下，改進算法ECRO求解的3個子目標函數F1、F2和F3均優于原始CRO求解算法，證明了改進方案的優越性。得益于筆者提出的兩種改進種群優化能力的策略使得珊瑚蟲種群的全局和局部搜索能力增強，從而在目標函數優化方面優于原始的CRO算法。同時，當3個子目標的權重分布比較均勻即取值為(0.3，0.35，0.35)時，子目標取值在表中所列出的權值集合中取值最優。

(2) 不同數量候選位置條件下的網絡部署代價比較

為比較在不同連通和覆蓋要求以及不同候選位置條件下改進算法ECRO部署成本的優化效果，分別在場景1和場景2利用ECRO算法進行仿真，3個子目標的權值分別設為0.3、0.35和0.35，結果如圖3和圖4所示。其中，(k|c)為監測目標的覆蓋度和布設節點的連通性要求。從圖中可以看出，在相同的可放置節點的候選位置數目條件下，連通和覆蓋要求越高，所需的節點部署代價越多。在相同的連通和覆蓋條件下，隨著橫坐標可放置節點的候選位置數目的增加，縱坐標算法求解得到的網絡部署代價也隨之增加。這主要由于節點候選位置的增加具有隨機性，增加的候選位置若分布比較分散且在該位置的部署節點代價較高的話，就需要更多的節點部署在新增的代價較高的部署區域以維持區域的覆蓋度和節點之間的連通度，從而導致節點部署代價的增加。

圖3 情形1中不同連通和覆蓋要求下的網絡部署代價

圖4 情形2中不同連通和覆蓋要求下的網絡部署代價

(3)算法性能對比

將部署傳感器節點的位置M設為200，分別在情形1和情形2下對提出的改進算法、原始珊瑚礁算法、文獻[21]提出的GA算法、LADE算法和貪婪算法進行仿真實驗，3個子目標的權值分別設為0.3、0.35和0.35，求解結果詳見圖5～圖10。圖中橫坐標(k|c)為監測目標的覆蓋度和布設節點的連通性要求。從圖中的結果可以得出，在(k|c)的值一定的情況下，提出的改進算法求解的網絡部署代價、子函數F2和F3均優于其余4種比較算法。比如，當橫坐標為(3|3)時，較之貪婪算法、CRO算法、GA算法和LADE算法，ECRO算法在保證F2和F3取值最優情況下，部署代價最低。其中，情景1中ECRO算法求解的部署代價降低13.6%、4.6%、 8.7%和1.6%，情景2中ECRO算法求解的結果降低11.4%、6.3%、7.67%和5.2%。同時，ECRO算法在表征覆蓋和連通性能的F2和F3中也優于4種比較算法，證明了改進算法的有效性。出現上述結果的原因為：使用貪婪算法得到的結果本質上是個局部最優解，在諸如筆者要解決的連通覆蓋一類的復雜組合優化問題上，求解得到的結果往往劣于具有全局優化能力的進化算法。較之原始CRO算法、GA算法和LADE算法，改進算法ECRO一方面通過借鑒和聲搜索算法中良好的算法結構框架，使得算法全局搜索能力增強，另一方面通過對算法迭代過程中優秀解基因的再利用，提高了算法的優化能力。

圖5 情形1中的函數F2比較

圖6 情形2中的函數F2比較

圖7 情形1中的函數F3比較

圖8 情形2中的函數F3比較

圖9 情形1中的網絡部署代價比較

圖10 情形2中算法的網絡部署代價比較

4 結束語

筆者提出了一種基于改進珊瑚礁算法的面向目標監測異構傳感網成本優化的覆蓋連通算法。該算法主要用于解決二維區域內節點性能指標異構和傳感器節點之間的多重連通以及區域監測目標的多重覆蓋條件下的成本優化部署問題。下一步的工作在于，研究更貼近工程實踐的優化方法和優化模型。在優化方法上，尋求一種低復雜度且不依賴經驗確定權重的解評價方法。在優化模型上，一方面，將障礙物引入部署模型，對有障礙物條件下的部署優化技術進行研究；另一方面，將連通概念與多跳路由算法結合，拓展連通概念的內涵，研究更具普適意義的覆蓋連通算法，滿足工程實踐的要求。