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

　

【正文】 摘要多目標進化算法在WSN動態覆蓋控制中的應用摘要隨著無線傳感器網絡的廣泛應用，關于無線傳感器網絡的問題，特別是無線傳感器網絡的動態覆蓋的問題得到了越來越多的關注。研究如何規劃傳感器合理的激活方案，來使無線傳感器網絡既要達到合理的區域覆蓋度，又盡可能的延長網絡壽命已經成為研究的一個熱點。本文以多目標進化算法在無線網絡傳感器網絡動態覆蓋中的應用為研究課題，首先概述無線傳感器網絡和無線傳感器網絡動態覆蓋問題的基礎知識，作為本文研究的理論基礎；然后，以無線網絡傳感器網絡的評價標準，即網絡覆蓋率和網絡壽命，確定性部署和隨機部署為依據構建無線傳感器網絡覆蓋問題模型；在此基礎上提出多目標遺傳算法的概念、特點、關鍵技術和基本流程，并以此為依據對無線網絡傳感器網絡動態覆蓋問題進行算法設計，通過基于多目標遺傳算法的無線傳感器網絡動態覆蓋問題算法設計，實現無線傳感器網絡動態覆蓋的最大優化。關鍵詞：無線傳感器網絡；動態覆蓋；模型；多目標遺傳算法AbstractMUITIOBJECTIVE EVOLUTIONARY ALGORITHM IN WSN DYNAMIC OVERLAYAbstractWith a wide range of issues related to the application of wireless sensor networks , wireless sensor networks , especially dynamic coverage problem in wireless sensor networks , namely, how to activate the program through rational planning sensor reaches a certain target area under the premise of coverage as possible the extension of the life of the network has bee a hot research. In this paper, multi target algorithm in wireless sensor networks dynamic overlay network for research , first outlined the basics of wireless sensor networks and wireless sensor networks dynamic coverage problem , as the theoretical basis for this study 。 then to a wireless network sensor networks evaluation criteria, that is, network coverage and network lifetime , deterministic and stochastic deployment is based on the deployment of wireless sensor network coverage issue to build the model 。 concept proposed multiobjective genetic algorithm based on this , characteristics, basic key technologies and processes, and to this is based on wireless sensor network dynamic network coverage problem for algorithm design, dynamic coverage problem algorithm design through pre arranged opening sequence based wireless sensor networks , wireless sensor networks to achieve maximum optimization of dynamic coverage.Keywords : wireless sensor networks 。 dynamic coverage 。 model 。 multiobjective Genetic Algorithms目錄第1章 緒論 1 1 2 2 3 3 4第2章WSN網絡覆蓋模型分析 4 5 WSN的動態覆蓋問題 6 網絡覆蓋度的評價標準 6 傳感器探測概率模型 8 9 9 10 10第3章 多目標進化算法分析 12 13 13 13 各類多目標進化算法分析 14 分布式啟發式算法 14 16 18 21第4章 基于多目標進化算法的WSN動態覆蓋問題算法實現 25 25 25 26 26 27 仿真結果分析 31 31 33第5章 總結與展望 35第6章 致謝 37參考文獻 39I第1章 緒論第1章 緒論無線傳感器網絡憑借它的廣闊應用前景而受到外界廣泛關注,無線傳感器網絡指的是那些工作在沒有人值守的地方，它消耗的能量很少，但是能源的限制能制約網絡覆蓋度及傳感器工作的時間，傳感器工作的時間又可稱為網絡壽命，從而我們知道了無線傳感器網絡的網絡覆蓋度和網絡壽命這兩個評價標準。從目前的研究前景來看，無線傳感器網絡的動態覆蓋問題中的核心就是對傳感器組成網絡進行合理的布局規劃，來使無線傳感器網絡能在不同的場合都能達到在一定的網絡覆蓋度前提下，盡可能的延長網絡壽命。采用何種方法來優化網絡覆蓋度以及網絡壽命成為我們研究的核心，在現實生活中，很多的優化問題是為了實現一個目標的最大化，而我們研究的網絡覆蓋度和網絡壽命是兩個互相作用且互相沖突的目標，顯而易見它的最優解肯定不會是一個解，而是一組均衡解。對于這個問題，我們選擇用多目標進化算法來解決是個可行的方案，首先我們了解進化算法是一種群體智能搜索方法，它比較適合用來求解多目標優化的問題。從1980年開始，人類就運用進化算法來解決多目標優化的問題。近年來，國內外的學者研究了大量的多目標進化算法，其中的一些算法已經可以成熟的應用到工程實踐的過程中。如何使多目標優化算法更加趨于完美，即進化多目標優化算法和多目標優化領域成為當今的熱門的研究方向。多目標進化算法能用來組合優化問題，具有重要的理論研究和工程應用價值，并且常常被用來測試多目標進化算法的性能，而利用多目標優化算法來對無線傳感器網絡動態覆蓋問題進行算法設計可以找到網絡覆蓋度和網絡壽命的最優解。鑒于此，本文選擇基于多目標進化算法用來研究無線傳感器網絡動態覆蓋問題，構建無線傳感器網絡動態覆蓋問題模型，并根據多目標進化算法的關鍵技術和基本流程，對基于無線傳感器網絡動態覆蓋問題算法進行設計，以期對實現無線傳感器網絡動態覆蓋最優化有所幫助。在無線傳感器技術發展日趨成熟的今天，無線傳感器通信也由原來有了長足的進步，無線傳感器技術發展日益成熟，它的應用方向更趨于多元化，很多的數據采集和通信工作都采用了無線技術。低成本、低功耗、小體積的傳感器節點的產生使得微機電系統和低功耗高集成數字設備的發展得以實現。大量的傳感器節點配合各種型號的傳感器，就能組成一個無線傳感器網絡。無線傳感網絡的產生開創了一個新的應用領域，它是一種新興的概念和技術，無線傳感器網絡被認為是未來四大高科技技術產業之一，可見它的研究價值。無線技術被廣泛應用于中大型區域領域，如大型的無人值守環境監測和目標跟蹤，可以適用于戰爭。因此，傳感器技術和傳感器網絡的研究被認為是最重要的方向。無線傳感器節點的工作環境對電池供電是非常苛刻的，因為大量的傳感器和難以更換，所以低功率無線傳感器網絡的一個最重要的設計標準，即延長傳感器網絡的壽命，使得傳感器更加可靠，耐用。綜上所述，在無線傳感技術應用如此廣泛的今天，在使得網絡覆蓋度盡可能大的前提下，又能實現傳感器的低功耗非常具有研究價值。（1）研究目的無線傳感技術的研究發展日新月異，傳感器節點的低功耗是它的發展方向之一，而低功耗與高網絡覆蓋度的結合目前難以實現。如何實現更好的無線傳感模塊功能，增加模塊的可靠性和使用壽命是當今熱門的問題。我們知道通過降低無線傳感節點的硬件功耗，確定無線傳感模塊各單元的基本功率消耗，并進行相應比較，確定需重點降耗的單元能夠增加網絡壽命。本文對從硬件上的探討不予研究，我們選擇基于多目標進化算法用來研究無線傳感器網絡動態覆問題，構建無線傳感器網絡動態覆蓋問題模型，并根據多目標進化算法的關鍵技術和基本流程，對基于無線傳感器網絡動態覆蓋問題算法進行設計，以期獲得一組最優解。 （2）研究意義無線傳感器網絡是一種新的理念和技術，它可以創造很多新的應用。無線傳感器技術以其廣闊的應用前景和巨大的價值，被認為是在未來十大改變世界的技術之一。目前，無線傳感器網絡節點的穩定運行的研究，可以提高整個網絡的可靠性，低功耗無線傳感器模塊的研究具有重要的研究價值，它的功能的實現對理論和實際應用都大有裨益。在實踐中，許多現有的研究中，高性能和低功耗相結合的研究很少進行，而有些研究只考慮低功耗，有的只在性能上追求卓越而忽視能源消耗的問題。只有綜合了性能和低功耗的共同需求，通過對芯片的數據的深入分析，才能得出低功耗高性能的無線傳感模塊的硬件設計方案。增加傳感模塊在無線傳感模塊應用中已經非常的廣泛，除了對組成無線傳感網絡的應用，無線傳感技術還能應用到環境監測中去，特別是一些極端惡劣、無人值守的環境，它還可以運用于短距離的無線通信。若能實現無線傳感模塊的低功耗和高性能的目標，那么其對電能的需求就會更小，能耗的減少能使得無線傳感網絡的應用范圍得到進一步的擴大。當前無線傳感器網絡巨大的應用前景得到了越來越多的關注,從而學者從上個世紀70年代就展開對無線傳感網絡的研究。最早可以追溯到1978年,美國國防部高級研究計劃署在當時就成立了一個分布式傳感器網絡學習組，并在卡內基梅隆大學對其展開研究。隨著嵌入式技術、傳感技術等不斷發展和進步的80年代，無線傳感器憑借具有更強的信息信號采集、處理能力構成了具有信息融合和處理能力的傳感器網絡。當今社會，國內外涌現了許多基于無線傳感器網絡節點的硬件平臺，典型的傳感器包括ImoteMica系列、IRIS系列等。各硬件平臺采用了不同的處理器和無線通信模塊是其主要的區別。有的傳感器節點（Telos、Mica）由于設計的歷史很早，其性能已經落后于當今的集成電路工業設計水平，能耗也非常巨大，只能完全進行重做。而有的傳感器為了追求具有高性能，使得其功耗過大，而當前能量受限的應用環境已經不再適用。我們知道無線傳感器網絡的節點采用電池供電，且一般工作在極端惡劣、無人值守的環境。由于傳感器節點電池更換困難以及數量龐大的原因，使其能耗耗完后和出現故障時的難以替換，無線傳感器網絡最重要的設計準則之一就是降低傳感器節點的功耗。在21世紀初，美國再生能源辦公室工業技術計劃（ITP）發布的報告“21世紀工業無線技術”第一頁中就引用了總統科技顧問的一段話的提到：無線傳感器可將傳感器的能源損耗變得更少，能源利用率能提高到原來的110%。而Intel(r)Mote等一些后來的科學研究項目，更注重低功耗操作、系統級集成和硬件的重新配置這三個方面的要求。當今的研究是為了做到低功耗和高性能的平衡，MIT發展的模塊化平臺對于具體的傳感器有不同的硬件設計，傳感器的主要功能是數據收集，采用垂直連接器來使不同的處理層整合到一起，為了實現傳感器網絡的低功耗、低成本和通用性,使得無線傳感器網絡的實現有了新的解決方案。覆蓋控制技術是無線傳感器網絡的研究最根本的問題之一，它是一種通過傳感器感知建模，使用傳感器節點配置和監控目標的感知模型來實現充分和有效地獲取必要的信息手段。無線傳感器網絡反映了物理世界的無線傳感器網絡的感知根本，無線傳感器網絡是從現有的移動網絡和無線網絡的不同點出發，網絡覆蓋將面臨設計方案與節點的能量供給約束的溝通能力和計算能力，傳感器節點的部署有大量，分布范圍廣，網絡動態性強的特點。該協議的一個重要目標是擴大網絡覆蓋網絡的壽命，并延長網絡的生存能有效地節省資金重新部署的傳感器節點。此外，由于傳感器節點通常是依靠電池作為能量源，并且節點數量巨大，也有可能被部署在偏遠地區或無法達到的區域，這樣不能更換傳感器節點的電池能量作為主要約束網絡系統的生命周期。因此，提高節點的能量效率，延長系統的壽命是無線傳感器網絡中是必不可少的。并有各種不同的方式來延長系統的壽命，主要是從減少能源消耗和平衡節點的能量消耗，節點之間的兩方面考慮降低節點的能量消耗可以使系統更加可靠，從而延長網絡壽命周期，可避免能源系統的幾個節點過早耗盡而提前終止網絡周期，節點之間的能量消耗應得到平衡。綜上所述，覆蓋控制技術取決于傳感器節點的綜合質量，基礎研究的問題也是服務于一種無線傳感器網絡。本課題是基于多目標進化算法在WSN的動態覆蓋控制中應用，通過學習多目標進化算法，多目標遺傳進化對無線傳感器網絡動態覆蓋問題進行算法設計，我們知道多目標進化算法是解決多目標優化問題的一種方法，在現實生活中，很多的優化問題是為了實現一個目標的最大化，而我們研究的網絡覆蓋度和網絡壽命是兩個互相作用且互相沖突的目標，顯而易見它的最優解肯定不會是一個解，而是一組均衡解，所以大大增加了問題的復雜程度。利用多目標進化算法求解多目標問題是進幾年新出現的一種求解思路，在無線傳感器網絡的應用中，兩個重要的參考指標就是網絡覆蓋度和網絡壽命，我們可以用兩個函數來表示網絡覆蓋度和網絡壽命，再利用多目標進化算法來求解兩個目標的最優解，這就是求一個雙目標問題的最優解集。本文主要做的兩個工作為：(1) 無線傳感器網絡動態覆蓋問題的建模。根據傳感器能源特性、布局特點等因素，建立動態覆蓋問題模型，明確網絡覆蓋度和網絡壽命兩個評價標準的具體定義。(2) 基于多目標進化算法對無線傳感器網絡動態覆蓋問