【文章內容簡介】 1：初始化種群步驟2：適應值評價步驟3：進化算子操作，生成新的種群（a） 選擇算子（b） 組合算子（c） 交叉算子步驟4：如果滿足終止條件，結束算法迭代，否則轉到步驟2。（2）優(yōu)缺點1）每輪迭代可以找到多個帕累托近似最優(yōu)解。2）迄今為止還沒有找到其他方法比進化算法更能有效的解決多目標問題。 3）在許多復雜的應用問題中搜索最優(yōu)解還存在一定的困難。 4）多目標進化算法能解決一些不容易解決特征的優(yōu)化問題，如不連續(xù)、多模態(tài)、可行空間不連續(xù)的問題。 5）多個個體能同時找到多種解決方案，即帕累托解集。這對于對問題信息了解較少的情況，或者決策者難以給出偏好時很有用。 各類多目標進化算法分析由于文章的篇幅限制以及個人精力有限，本本文主要研究了四種多目標進化算法，分別為多目標遺傳算法、改進的多目標差分進化算法、多目標粒子群優(yōu)化算法、分布式啟發(fā)式算法，對無線傳感器網(wǎng)絡的動態(tài)覆蓋進行學習與研究。 分布式啟發(fā)式算法本文基于分布式啟發(fā)式算法對無線傳感器網(wǎng)絡的研究借鑒了文獻[8]的知識，K覆蓋問題的定義是：有些傳感器網(wǎng)絡中對監(jiān)測區(qū)域或目標的覆蓋質量具有特殊的要求，因此要求監(jiān)測區(qū)域中的每個目標點至少被K個不同傳感器節(jié)點同時覆蓋。假設有向傳感器節(jié)點可在幾個覆蓋方向中切換，根據(jù)傳感器節(jié)點的覆蓋方向協(xié)同優(yōu)化，實現(xiàn)覆蓋區(qū)域和目標的最大化有向覆蓋。視頻傳感器節(jié)點具有視頻傳感器的感知模型范圍是指傳感器節(jié)點是節(jié)點P（X，Y）為圓心、感知距離為R（半徑）、夾角為α的扇形區(qū)域，扇形區(qū)域的中心線Vp角度為θ，如圖31所示，因此，每個有向感知節(jié)點模型都可以用一個五元組X,Y,R,α,θ來表示，分別表示每個有向感知節(jié)點的中心位置坐標，感知半徑，感知視角及感知方向角。圖31有向感知節(jié)點模型本文研究的有向K覆蓋問題屬于目標覆蓋，K覆蓋算法可解釋為如圖32所示的模型：假設有一個內存覆蓋區(qū)有四個傳感器和三個目標點，在一個特定的方向四個方向的傳感器傳感器，因此，目標1是傳感器1和2和傳感器4覆蓋，目標2所覆蓋的傳感器2和4中，在靶3上覆蓋傳感器2和3，具有至少兩個包括的傳感器傳感器的所有目標，以滿足K 為2的覆蓋范圍。在無線視頻傳感器網(wǎng)絡的實際應用，至少需要一些目標點同時覆蓋K個不同的傳感器傳感器，因此，必須保證設定k的最大目標傳感器已經(jīng)覆蓋到。本算法接著建立了K覆蓋問題，以優(yōu)化理論模型給出的指令級并行的形式整數(shù)線性規(guī)劃的準確描述。圖32視頻傳感器網(wǎng)絡覆蓋模型有向感知K覆蓋控制算法的工作流程如下:無線視頻傳感器網(wǎng)絡部署完成后，視頻傳感器傳感器掃描各個覆蓋方向上的目標信息，并與其一跳鄰居節(jié)點交換目標信息，然后計算每個覆蓋方向的效用函數(shù)值，選取效用函數(shù)值為最大概率選擇自身的工作方向，最后將自己的方向決策通知其一跳鄰居傳感器。同時，有向感知K覆蓋控制算法中進而還可以擴展考慮傳感器的剩余能量：將一個工作時間間隔成為一輪，在每輪時間末期，一跳鄰居傳感器范圍內交換剩余能量信息，依據(jù)自身剩余能量值決定是否在下一輪是否休眠，節(jié)點集按序完成有向覆蓋的任務，從而延長網(wǎng)絡生存時間。下面給出有向感知K覆蓋算法偽代碼：初始化：網(wǎng)絡拓撲結構G（N，E）及目標集合M分布%每一輪時間周期內重新選擇For(Round1,...7){所有節(jié)點發(fā)送Beacon消息%按節(jié)點序號在一跳鄰居范圍內自行遴選方向For（i=1，...,N）｝1. 收集所有一跳鄰居節(jié)點的數(shù)據(jù)，更新方向目標集合2. 遍歷所有的目標集合M，計算覆蓋每個集合的方向節(jié)點3. 根據(jù)遍歷結果計算本節(jié)點所有方向的效用函數(shù)值4. 計算每個方向的歸一化效用函數(shù)值5. 一效用函數(shù)值為概率隨機選擇覆蓋方向綜上所述，對無線視頻傳感器網(wǎng)絡中的有向K重覆蓋問題，假設有向傳感器節(jié)點可在幾個覆蓋方向中切換，根據(jù)傳感器節(jié)點的覆蓋方向協(xié)同優(yōu)化，實現(xiàn)覆蓋區(qū)域和目標的最大化有向覆蓋。本算法利用網(wǎng)絡有向覆蓋的冗余特性，設計一種簡單的分布式啟發(fā)式算法對有向傳感器節(jié)點的感知方向進行調度，使得目標集合被K覆蓋的時間最多。與求解最大有向K覆蓋問題的貪婪算法一樣，有向感知K覆蓋控制算法也屬于一種一跳覆蓋范圍內的分布式方法。最后，使用算法驗證了算法性能，特別相比較于隨機覆蓋算法，能大大減低覆蓋盲區(qū)比例。本文基于多目標差分進化算法對無線傳感器網(wǎng)絡的研究借鑒了文獻[9]的知識，多目標差分進化算法的特點是：收斂速度快，控制參數(shù)小以及容易實現(xiàn)和理解的。建議多目標覆蓋的無線傳感器網(wǎng)絡的控制策略K重覆蓋，無線傳感器網(wǎng)絡節(jié)點的傳感單元的能源消耗和優(yōu)化目標的可靠性系數(shù)，采用改進的多目標進化算法求解差。它們的差別是在覆蓋范圍的分析的控制策略，并結合來自控制高精度K重覆蓋研究的角度考慮，泊松分布模型的傳感器節(jié)點。在研究能量消耗的問題，考慮到調度和傳感器節(jié)點感知半徑可調在這兩種情況下，量化傳感器節(jié)點傳感半徑和工作狀態(tài)傳感傳感器節(jié)點能量消耗的數(shù)量的影響。從網(wǎng)絡上的生命周期的工作傳感器節(jié)點的數(shù)目的影響，提出了一種可靠性因子，獲得了網(wǎng)絡的可靠性趨勢知覺半徑和傳感器節(jié)點密度的影響。仿真結果表明，該控制策略可以保證K重覆蓋，同時有效降低能耗，保證網(wǎng)絡的可靠性。目前的研究無線傳感器網(wǎng)絡的可靠性，通常分為兩大類：基于任務的可靠性模型和基于壽命的網(wǎng)絡可靠性模型?；趬勖木W(wǎng)絡覆蓋模型從連通性對生命周期的角度可靠性分析定義了以下三個概念：（1）第一個傳感器節(jié)點的能量耗盡可視為網(wǎng)絡生活。（2）達到網(wǎng)絡不能夠接受的事件探測率時所用時間，看作網(wǎng)絡壽命；（3）當網(wǎng)絡中存活節(jié)點數(shù)量所占比例低于某一閾值時，可認為已經(jīng)達到網(wǎng)絡壽命。當使用節(jié)點調度機制，處于休眠狀態(tài)的每個節(jié)點，以監(jiān)視在其覆蓋范圍運行狀態(tài)的鄰居節(jié)點，如果該節(jié)點不是活動的，它進入工作狀態(tài)，否則它保持休眠狀態(tài)。第三類是根據(jù)網(wǎng)絡的生命周期定義，這種機制可以有效地延長網(wǎng)絡的生命周期。因此，為了確保在工作狀態(tài)的前提下使網(wǎng)絡壽命得到延長，高可靠性能獲得高覆蓋度，因此，需要定義一個體現(xiàn)可靠性的因子P: 公式31覆蓋模型的用途的范圍是通過設置節(jié)點密度和半徑的合理感知，使得傳感器網(wǎng)絡的覆蓋區(qū)域來監(jiān)視多個滿足預定值時，該網(wǎng)絡的最大覆蓋范圍的前提下，要求控制，最低的能耗，網(wǎng)絡工作壽命最長的。通過上述推導的優(yōu)化問題，區(qū)域覆蓋優(yōu)化可以被定義為下面的多目標。（1） K重覆蓋率。保證目標區(qū)域內的目標事件能夠以最大的概率被感知： 公式32（2） 單位感知能耗。在滿足網(wǎng)絡覆蓋指標后，整個網(wǎng)絡的能耗越少，網(wǎng)絡性能越好： 公式33（3） 可靠性因子:基于多目標差分算法的傳感器隨機覆蓋控制問題求解流程如圖33所示：圖33多目標差分進化算法流程無線傳感器網(wǎng)絡覆蓋控制策略，本文考慮了K重覆蓋，節(jié)點的單位能耗和可靠性因子這三項指標的信度系數(shù)。為確保高覆蓋率監(jiān)控能力的無線傳感器網(wǎng)絡，使能耗低可靠性高的傳感器得以延長網(wǎng)絡的壽命。本文通過對多目標優(yōu)化和改進的多目標差分進化算法的研究，從調節(jié)傳感器K重覆蓋密度和節(jié)點半徑的大小以及單位能耗的角度來看，對有關傳感器可靠性的因素進行了優(yōu)化，以期能獲得最佳的節(jié)點部署密度和傳感半徑，并且能夠確定一段時間內傳感器的睡眠時間的理論數(shù)量。通過改進多目標非支配排序遺傳算法和比較差分進化算法能夠看出，多目標差分進化算法具有更好的數(shù)據(jù)挖掘和保持非支配解能力，還可以提供更豐富的信息，為決策者進行決策提供了多樣性的選擇余地。正如從仿真結果中看到的，該控制策略能夠確保覆蓋區(qū)域的可靠性，同時降低了能量消耗，提供最優(yōu)的實際布局，以期能夠獲得實時的密度傳感器節(jié)點傳感半徑和的大小的參考值。本文基于多目標粒子群進化算法對無線傳感器網(wǎng)絡的研究主要來自[10]。多目標粒子群優(yōu)化算法在最近幾年得到了很大的發(fā)展，被看作是解決多目標優(yōu)化算法的一種有效的群智能算法，算法基于一個群體中的粒子能夠從過去的經(jīng)歷和其他粒子中獲取有效信息這一個假設。因為無線傳感器的部署網(wǎng)絡節(jié)點隨機部署有很高密度和各自的特征，因此大多數(shù)傳感器之間的橫截面覆蓋區(qū)域的重疊一方面，如果同樣的工作將導致能源的浪費和縮短網(wǎng)絡壽命，另一方面一些區(qū)域不需要進行監(jiān)測，這就造成了浪費，因此如何確定網(wǎng)絡覆蓋范圍是無線傳感器網(wǎng)絡中的關鍵問題之一。本算法旨在對人工很難準確監(jiān)測的環(huán)境，使用固定傳感器和移動傳感器來構建混合無線傳感器網(wǎng)絡，研究如何最大限度地提高無線傳感器網(wǎng)絡監(jiān)控和網(wǎng)絡部署優(yōu)化策略，來提高網(wǎng)絡的范圍覆蓋。對于無線傳感器網(wǎng)絡覆蓋問題，部署在除了隨機最大化網(wǎng)絡覆蓋的無線傳感器網(wǎng)絡，有一個值得研究的問題，這將導致傳感器隨機重疊覆蓋區(qū)域的部署，然后換另外的移動傳感器的位置，如在重疊區(qū)域中找到應冗余傳感器進入休眠狀態(tài)中的區(qū)域中，從而提高了網(wǎng)絡的使用壽命。該算法是基于非支配排序策略，通過改進多目標粒子群優(yōu)化算法和粒子群粒子模擬移動節(jié)點的位置，再加上冗余節(jié)點基于加權自適應鄰干擾檢測在每次迭代取適應值的粒子效果，從中選擇最佳的粒子參與的下一次的進化，從而提高網(wǎng)絡的覆蓋范圍并延長無線傳感器網(wǎng)絡的生命周期的目的。目標標區(qū)域A為被離散化成LW個網(wǎng)格的二維矩形平面，每個網(wǎng)格代表一個待監(jiān)測小區(qū)域。在區(qū)域A隨機投放M個移動傳感器節(jié)點和N個固定傳感器節(jié)點構成混合無線傳感器網(wǎng)絡，在不影響問題本質的前提下，作以下假設：①固定傳感器節(jié)點的能量不能補充，即當其能量耗盡時，該節(jié)點不能工作；② 所有節(jié)點的無線通信范圍是以節(jié)點為圓心、半徑的Rc的圓形區(qū)域，節(jié)點感知半徑為Rs且Rc＝2Rs；③所有節(jié)點均采用布爾感知模型；④各節(jié)點通信模型采用布爾通信模型；⑤每個節(jié)點具有工作、偵測和休眠3種狀態(tài)。目標區(qū)域A內任一離散網(wǎng)格k，其中心坐標為（xk，yk），如果與最鄰近傳感器節(jié)點si（xi，yi）的距離 公式34那么k點被傳感器ｓ感知到的概率P（k，s）=1；否則P（k，s）=0，在此基礎上，將網(wǎng)格k（xk，yk）的覆蓋定義為該網(wǎng)格被處于工作狀態(tài)的傳感器節(jié)點集X=｛s1,...,sn｝中至少一個感知到的概率，即： 公式35因此，無線傳感網(wǎng)絡覆蓋就是該網(wǎng)絡中處于工作狀態(tài)的傳感器節(jié)點集X所覆蓋網(wǎng)格點的總和，記為Cov（X）即： 公式36處于休眠狀態(tài)的傳感器數(shù)量記為：Sleep（X）=N+M|X||X|表示集合Ｘ的元素個數(shù)?；旌蠠o線傳感網(wǎng)絡的覆蓋問題就是如何優(yōu)化移動節(jié)點的位置，在保證網(wǎng)絡全連通的前提下，使得處于工作狀態(tài)的傳感器節(jié)點盡可能少，且目標區(qū)域被無線傳感器網(wǎng)絡覆蓋的面積盡可能大。因此，混合無線傳感網(wǎng)絡的覆蓋問題可以歸結為滿足網(wǎng)絡全連通條件兩目標優(yōu)化問題，即：maxF（X）=[f1(X),f2(X)]由于隨機部署的傳感器節(jié)點是很容易形成感知覆蓋重疊區(qū)域，以便關閉由冗余節(jié)點來擴展網(wǎng)絡的生命周期。在本算法中，對于主動檢測睡眠時間表的自適應方法來關閉或啟動傳感器節(jié)點。首先，隨機設置傳感器節(jié)點處于休眠狀態(tài)和工作條件，所以經(jīng)過一段時間的休眠隨機睡眠時間ts后，每個節(jié)點醒來的工作。具體的檢測方法是：節(jié)點的功率喚醒在該地區(qū)的適當直徑為工作節(jié)點的區(qū)域內發(fā)射接收回復信息答復消息，如果睡眠檢測節(jié)點答復消息的一聲，和睡眠時間調整進入休眠狀態(tài)；沒有接收到應答消息，如果在一段時間內，該節(jié)點的睡眠狀態(tài)轉移到工作。本文提出了一種鄰里干擾與多目標粒子群優(yōu)化算法，基于全局最優(yōu)粒子從F1在基于加權法非劣效性面前可供選擇，并從隨機選取的不同，NSGAⅡ非支配排序策略，其自己粒子局部最優(yōu)的粒子。中的運動效應的方程式粒子位置更新，以及基于自適應鄰干擾它們的值相適應。該算法的基本流程如圖34所示：圖34 算法流程圖用基于鄰域擾動的多目標粒子群優(yōu)化算法能較好優(yōu)化隨機部署的混合無線傳感網(wǎng)絡的覆蓋性能，有三個原因：首先，算法對粒子群進行克隆并采用動態(tài)鄰域擾動操作，通過該操作，一方面適應性強的粒子擾動幅度小，達到增強局部精確搜索的目的，另一方面，對于適應性較差的粒子，增大擾動幅度，從而增加發(fā)現(xiàn)更好位置的機會；其次，基于精英保留的非支配排序策略為算法提供了良好的非劣解集；最后，通過加權法從當前非劣解集中選出全局最優(yōu)粒子并從非劣解集中隨機選取個體最優(yōu)粒子從而為粒子下一次進化指引了方向。本文基于多目標遺傳算法對無線傳感器網(wǎng)絡的研究主要來自文獻[11]，多目標遺傳算法通常實現(xiàn)方式為一種計算機模擬。對于一個最優(yōu)化問題，一定數(shù)量的候選解的抽象表示的種群向更好的解進化。多目標遺傳算法常用的基本概念主要包括個體、群體、基因、基因型、適應值等。在無線傳感器網(wǎng)絡中，節(jié)點一般采用電池作為能源，更換節(jié)點電池難以實現(xiàn)，同時其計算能力和通信能力受限，網(wǎng)絡的節(jié)點部署在一定程度上決定了網(wǎng)絡的性能和使用壽命。因此，在運行過程中保證能量有效和延長網(wǎng)絡壽命成為無線傳感器網(wǎng)絡應用的關鍵?；诹Ｗ尤簝?yōu)化的策略，可以提高無線傳感器網(wǎng)絡覆蓋性能，但算法本身就容易陷入局部最優(yōu)，導致無法收斂到全局極值點。很多算法的目標都是優(yōu)化網(wǎng)絡覆蓋度，但不考慮網(wǎng)絡能量平衡的問題，能量平衡也是在運行整個網(wǎng)絡的壽命和穩(wěn)定性決定的一個重要因素。 該算法不同于算法是，在確保使用較少的節(jié)點，同時考慮網(wǎng)絡區(qū)域的能量平衡策略之前工作。仿真結果表明，新的覆蓋控制策略可以顯著提高覆蓋率，節(jié)約能源消耗，并確保網(wǎng)絡的能量平衡。為了獲得較高的覆蓋率的無線傳感器網(wǎng)絡的需要，通?？梢栽黾觽鞲衅鞴?jié)點的密度，這可以有效減少感知盲點出現(xiàn)的概率。但是大量的冗余數(shù)據(jù)傳輸網(wǎng)絡會導致傳感器節(jié)點會產生沖突，從而導致過度的能量消耗，因而在網(wǎng)絡的過早地失效。如果一個節(jié)點可以感知的區(qū)域完全能被其他節(jié)點完全覆蓋，這那么個節(jié)點就被稱為冗余節(jié)點，該傳感器可以進入休眠狀態(tài)并且不影響網(wǎng)絡覆蓋度。通過一些可行的算法來確定冗余節(jié)點的存在，前提是確保最大的網(wǎng)絡覆蓋，同時又使用盡可能少的傳感器節(jié)點，允許冗余節(jié)點休眠，這是一個傳感器網(wǎng)絡既能滿足覆蓋要求又能降低能耗的有效途徑。因此，在網(wǎng)絡的初始階段，選擇對網(wǎng)絡性能的節(jié)點的一個合理的工作和運行成本是十分重要的。在同一時間，該網(wǎng)絡的能量消耗的平衡，對于網(wǎng)絡的穩(wěn)定運行所必需，并延長了網(wǎng)絡壽命，它存在與覆蓋和