多目標進化算法在wsn的動態覆蓋控制中應用畢業論文(編輯修改稿)

　

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