【正文】 互相沖突的目標(biāo)，顯而易見它的最優(yōu)解肯定不會是一個解，而是一組均衡解，所以大大增加了問題的復(fù)雜程度。此外，由于傳感器節(jié)點通常是依靠電池作為能量源，并且節(jié)點數(shù)量巨大，也有可能被部署在偏遠(yuǎn)地區(qū)或無法達(dá)到的區(qū)域，這樣不能更換傳感器節(jié)點的電池能量作為主要約束網(wǎng)絡(luò)系統(tǒng)的生命周期。當(dāng)今的研究是為了做到低功耗和高性能的平衡，MIT發(fā)展的模塊化平臺對于具體的傳感器有不同的硬件設(shè)計，傳感器的主要功能是數(shù)據(jù)收集，采用垂直連接器來使不同的處理層整合到一起，為了實現(xiàn)傳感器網(wǎng)絡(luò)的低功耗、低成本和通用性,使得無線傳感器網(wǎng)絡(luò)的實現(xiàn)有了新的解決方案。我們知道無線傳感器網(wǎng)絡(luò)的節(jié)點采用電池供電，且一般工作在極端惡劣、無人值守的環(huán)境。當(dāng)今社會，國內(nèi)外涌現(xiàn)了許多基于無線傳感器網(wǎng)絡(luò)節(jié)點的硬件平臺，典型的傳感器包括ImoteMica系列、IRIS系列等。若能實現(xiàn)無線傳感模塊的低功耗和高性能的目標(biāo)，那么其對電能的需求就會更小，能耗的減少能使得無線傳感網(wǎng)絡(luò)的應(yīng)用范圍得到進(jìn)一步的擴(kuò)大。目前，無線傳感器網(wǎng)絡(luò)節(jié)點的穩(wěn)定運行的研究，可以提高整個網(wǎng)絡(luò)的可靠性，低功耗無線傳感器模塊的研究具有重要的研究價值，它的功能的實現(xiàn)對理論和實際應(yīng)用都大有裨益。我們知道通過降低無線傳感節(jié)點的硬件功耗，確定無線傳感模塊各單元的基本功率消耗，并進(jìn)行相應(yīng)比較，確定需重點降耗的單元能夠增加網(wǎng)絡(luò)壽命。無線傳感器節(jié)點的工作環(huán)境對電池供電是非常苛刻的，因為大量的傳感器和難以更換，所以低功率無線傳感器網(wǎng)絡(luò)的一個最重要的設(shè)計標(biāo)準(zhǔn)，即延長傳感器網(wǎng)絡(luò)的壽命，使得傳感器更加可靠，耐用。大量的傳感器節(jié)點配合各種型號的傳感器，就能組成一個無線傳感器網(wǎng)絡(luò)。多目標(biāo)進(jìn)化算法能用來組合優(yōu)化問題，具有重要的理論研究和工程應(yīng)用價值，并且常常被用來測試多目標(biāo)進(jìn)化算法的性能，而利用多目標(biāo)優(yōu)化算法來對無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋問題進(jìn)行算法設(shè)計可以找到網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命的最優(yōu)解。對于這個問題，我們選擇用多目標(biāo)進(jìn)化算法來解決是個可行的方案，首先我們了解進(jìn)化算法是一種群體智能搜索方法，它比較適合用來求解多目標(biāo)優(yōu)化的問題。 model 。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；動態(tài)覆蓋；模型；多目標(biāo)遺傳算法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 。摘要多目標(biāo)進(jìn)化算法在WSN動態(tài)覆蓋控制中的應(yīng)用摘要隨著無線傳感器網(wǎng)絡(luò)的廣泛應(yīng)用，關(guān)于無線傳感器網(wǎng)絡(luò)的問題，特別是無線傳感器網(wǎng)絡(luò)的動態(tài)覆蓋的問題得到了越來越多的關(guān)注。 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 。 multiobjective Genetic Algorithms目錄第1章 緒論 1 1 2 2 3 3 4第2章WSN網(wǎng)絡(luò)覆蓋模型分析 4 5 WSN的動態(tài)覆蓋問題 6 網(wǎng)絡(luò)覆蓋度的評價標(biāo)準(zhǔn) 6 傳感器探測概率模型 8 9 9 10 10第3章 多目標(biāo)進(jìn)化算法分析 12 13 13 13 各類多目標(biāo)進(jìn)化算法分析 14 分布式啟發(fā)式算法 14 16 18 21第4章 基于多目標(biāo)進(jìn)化算法的WSN動態(tài)覆蓋問題算法實現(xiàn) 25 25 25 26 26 27 仿真結(jié)果分析 31 31 33第5章 總結(jié)與展望 35第6章 致謝 37參考文獻(xiàn) 39I第1章 緒論第1章 緒論無線傳感器網(wǎng)絡(luò)憑借它的廣闊應(yīng)用前景而受到外界廣泛關(guān)注,無線傳感器網(wǎng)絡(luò)指的是那些工作在沒有人值守的地方，它消耗的能量很少，但是能源的限制能制約網(wǎng)絡(luò)覆蓋度及傳感器工作的時間，傳感器工作的時間又可稱為網(wǎng)絡(luò)壽命，從而我們知道了無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命這兩個評價標(biāo)準(zhǔn)。從1980年開始，人類就運用進(jìn)化算法來解決多目標(biāo)優(yōu)化的問題。鑒于此，本文選擇基于多目標(biāo)進(jìn)化算法用來研究無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋問題，構(gòu)建無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋問題模型，并根據(jù)多目標(biāo)進(jìn)化算法的關(guān)鍵技術(shù)和基本流程，對基于無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋問題算法進(jìn)行設(shè)計，以期對實現(xiàn)無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋最優(yōu)化有所幫助。無線傳感網(wǎng)絡(luò)的產(chǎn)生開創(chuàng)了一個新的應(yīng)用領(lǐng)域，它是一種新興的概念和技術(shù)，無線傳感器網(wǎng)絡(luò)被認(rèn)為是未來四大高科技技術(shù)產(chǎn)業(yè)之一，可見它的研究價值。綜上所述，在無線傳感技術(shù)應(yīng)用如此廣泛的今天，在使得網(wǎng)絡(luò)覆蓋度盡可能大的前提下，又能實現(xiàn)傳感器的低功耗非常具有研究價值。本文對從硬件上的探討不予研究，我們選擇基于多目標(biāo)進(jìn)化算法用來研究無線傳感器網(wǎng)絡(luò)動態(tài)覆問題，構(gòu)建無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋問題模型，并根據(jù)多目標(biāo)進(jìn)化算法的關(guān)鍵技術(shù)和基本流程，對基于無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋問題算法進(jìn)行設(shè)計，以期獲得一組最優(yōu)解。在實踐中，許多現(xiàn)有的研究中，高性能和低功耗相結(jié)合的研究很少進(jìn)行，而有些研究只考慮低功耗，有的只在性能上追求卓越而忽視能源消耗的問題。當(dāng)前無線傳感器網(wǎng)絡(luò)巨大的應(yīng)用前景得到了越來越多的關(guān)注,從而學(xué)者從上個世紀(jì)70年代就展開對無線傳感網(wǎng)絡(luò)的研究。各硬件平臺采用了不同的處理器和無線通信模塊是其主要的區(qū)別。由于傳感器節(jié)點電池更換困難以及數(shù)量龐大的原因，使其能耗耗完后和出現(xiàn)故障時的難以替換，無線傳感器網(wǎng)絡(luò)最重要的設(shè)計準(zhǔn)則之一就是降低傳感器節(jié)點的功耗。覆蓋控制技術(shù)是無線傳感器網(wǎng)絡(luò)的研究最根本的問題之一，它是一種通過傳感器感知建模，使用傳感器節(jié)點配置和監(jiān)控目標(biāo)的感知模型來實現(xiàn)充分和有效地獲取必要的信息手段。因此，提高節(jié)點的能量效率，延長系統(tǒng)的壽命是無線傳感器網(wǎng)絡(luò)中是必不可少的。利用多目標(biāo)進(jìn)化算法求解多目標(biāo)問題是進(jìn)幾年新出現(xiàn)的一種求解思路，在無線傳感器網(wǎng)絡(luò)的應(yīng)用中，兩個重要的參考指標(biāo)就是網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命，我們可以用兩個函數(shù)來表示網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命，再利用多目標(biāo)進(jìn)化算法來求解兩個目標(biāo)的最優(yōu)解，這就是求一個雙目標(biāo)問題的最優(yōu)解集。利用多目標(biāo)進(jìn)化算法的特點，針對我們建立的模型，從不同出發(fā)點考慮設(shè)計算法，得出不同覆蓋水平和網(wǎng)絡(luò)壽命的規(guī)劃方案。第二章進(jìn)行了對無線傳感器網(wǎng)絡(luò)進(jìn)行了模型分析，分別包括無線傳感器網(wǎng)絡(luò)的簡介、無線傳感器動態(tài)覆蓋的評價標(biāo)準(zhǔn)和概率模型。由傳感器節(jié)點、匯聚節(jié)點（Sink）、后臺管理中心三部分組成了無線傳感器網(wǎng)絡(luò)，如圖21所示。無線傳感器網(wǎng)路由數(shù)千個微小的傳感器組成，所以通常主要依靠增加的不是單個設(shè)備的能力，而是但大規(guī)模的、冗余的嵌入式設(shè)備協(xié)同工作，來提高系統(tǒng)的可靠性和穩(wěn)定性。由此產(chǎn)生的能量是最重要的限制瓶頸，阻礙了無線傳感器網(wǎng)絡(luò)和應(yīng)用的發(fā)展方向之一。所需的無線傳感器網(wǎng)絡(luò)以數(shù)據(jù)為中心的功能設(shè)計必須檢測數(shù)據(jù)管理和處理中心，它通常說的無線傳感器網(wǎng)絡(luò)是一個以數(shù)據(jù)為中心的網(wǎng)絡(luò)。通常情況下，網(wǎng)絡(luò)覆蓋度是評價無線傳感器網(wǎng)絡(luò)的探測質(zhì)量的一個最重要的標(biāo)準(zhǔn)。為傳感器節(jié)點收集有關(guān)通過其他傳感器節(jié)點的多跳傳輸簡單的數(shù)據(jù)處理環(huán)境的信息，監(jiān)測數(shù)據(jù)可以在傳輸過程中被處理的多個節(jié)點，通過多跳中繼數(shù)據(jù)到宿節(jié)點將最后直接發(fā)送到管理中心或?qū)崿F(xiàn)傳感器網(wǎng)絡(luò)通過互聯(lián)網(wǎng)背景交通管理中心，如通信衛(wèi)星和GPRS，從整個區(qū)域?qū)?shù)據(jù)發(fā)送到集中處理的后臺管理中心。網(wǎng)絡(luò)覆蓋度可以分為以下三種，即障礙覆蓋度、區(qū)域覆蓋度以及點覆蓋度。圖23是隨機(jī)部署的傳感器覆蓋整個矩形區(qū)域的示意圖，黑色圓點是激活的傳感器，空心圓是處于休眠狀態(tài)的傳感器。圖24點覆蓋度圖由圖中我們可以看出，黑色圓點處于激活狀態(tài)時三個圓的面積就把所有的傳感器包含進(jìn)去了，覆蓋度就是100%。圖25是一個傳感器有效覆蓋范圍示意圖：圖25傳感器有效覆蓋范圍示意圖 傳感器探測概率模型在二維網(wǎng)格模型中，傳感器在格點的位置，網(wǎng)格給傳感器網(wǎng)絡(luò)的探測范圍提供了一個度量標(biāo)準(zhǔn)。在概率模型下，若存在多個傳感器同時工作，則一個目標(biāo)點p被有效探測的概率是幾個傳感器共同作用的結(jié)果。從網(wǎng)絡(luò)覆蓋度的實際考慮，一個網(wǎng)絡(luò)工作的過程是許多個時間段之和，為了使網(wǎng)絡(luò)覆蓋度在各個時間段盡可能均衡，考察網(wǎng)絡(luò)的覆蓋質(zhì)量就用它在各個時間段的覆蓋度的最小值作為整個網(wǎng)絡(luò)的覆蓋度，即： 公式23其中，covi為每一時間段網(wǎng)絡(luò)的覆蓋率；為點的總數(shù)目量；為在ti時間段內(nèi)網(wǎng)絡(luò)被覆蓋的覆蓋度。當(dāng)網(wǎng)絡(luò)從部署開始到網(wǎng)絡(luò)不工作的時間跨度就被稱為無線傳感器網(wǎng)絡(luò)的生存周期。這樣的數(shù)據(jù)可以被記錄相鄰傳感器相關(guān)或相同的。這樣依次輪流打開不同的節(jié)點集合，既能完整的監(jiān)測需要檢測的環(huán)境，又能降低能耗。假定網(wǎng)絡(luò)覆蓋度為100%，即A、B、C、D、E、F、G都要被節(jié)點覆蓋到。把以有限時間內(nèi)節(jié)能作為目標(biāo)，求出的最優(yōu)解為{A、C}，而若直接以延長網(wǎng)絡(luò)壽命為目標(biāo)，則求出的最優(yōu)解為{{A、D、F}，{B、C、E}}。這個帶有一個固定量，例如汽車用汽油和機(jī)油，只有汽油和機(jī)油共同作用汽車才能運行，能跑最長時間的，不一定是剩的油總量最多的，若最后全剩下機(jī)油，沒有汽油的配合，也不能開動。先明確一個概念：帕累托最優(yōu)解。這能通過一個單一的目標(biāo)函數(shù)來實現(xiàn)，但在同時有多個目標(biāo)，面對現(xiàn)實中的多目標(biāo)問題，對個體的優(yōu)劣評價適應(yīng)度的困難程度變得相對復(fù)雜。本文主要研究了四種多目標(biāo)進(jìn)化算法，分別為多目標(biāo)遺傳算法、改進(jìn)的多目標(biāo)差分進(jìn)化算法、多目標(biāo)粒子群優(yōu)化算法、分布式啟發(fā)式算法對無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋問題進(jìn)行學(xué)習(xí)與分析，下文會一一進(jìn)行介紹。而網(wǎng)絡(luò)壽命和網(wǎng)絡(luò)覆蓋度又是一對矛盾的對象，要讓網(wǎng)絡(luò)覆蓋度大，那么必然要打開更多的傳感器節(jié)點。2）迄今為止還沒有找到其他方法比進(jìn)化算法更能有效的解決多目標(biāo)問題。這對于對問題信息了解較少的情況，或者決策者難以給出偏好時很有用。視頻傳感器節(jié)點具有視頻傳感器的感知模型范圍是指傳感器節(jié)點是節(jié)點P（X，Y）為圓心、感知距離為R（半徑）、夾角為α的扇形區(qū)域，扇形區(qū)域的中心線Vp角度為θ，如圖31所示，因此，每個有向感知節(jié)點模型都可以用一個五元組X,Y,R,α,θ來表示，分別表示每個有向感知節(jié)點的中心位置坐標(biāo)，感知半徑，感知視角及感知方向角。圖32視頻傳感器網(wǎng)絡(luò)覆蓋模型有向感知K覆蓋控制算法的工作流程如下:無線視頻傳感器網(wǎng)絡(luò)部署完成后，視頻傳感器傳感器掃描各個覆蓋方向上的目標(biāo)信息，并與其一跳鄰居節(jié)點交換目標(biāo)信息，然后計算每個覆蓋方向的效用函數(shù)值，選取效用函數(shù)值為最大概率選擇自身的工作方向，最后將自己的方向決策通知其一跳鄰居傳感器。與求解最大有向K覆蓋問題的貪婪算法一樣，有向感知K覆蓋控制算法也屬于一種一跳覆蓋范圍內(nèi)的分布式方法。它們的差別是在覆蓋范圍的分析的控制策略，并結(jié)合來自控制高精度K重覆蓋研究的角度考慮，泊松分布模型的傳感器節(jié)點。目前的研究無線傳感器網(wǎng)絡(luò)的可靠性，通常分為兩大類：基于任務(wù)的可靠性模型和基于壽命的網(wǎng)絡(luò)可靠性模型。第三類是根據(jù)網(wǎng)絡(luò)的生命周期定義，這種機(jī)制可以有效地延長網(wǎng)絡(luò)的生命周期。保證目標(biāo)區(qū)域內(nèi)的目標(biāo)事件能夠以最大的概率被感知： 公式32（2） 單位感知能耗。通過改進(jìn)多目標(biāo)非支配排序遺傳算法和比較差分進(jìn)化算法能夠看出，多目標(biāo)差分進(jìn)化算法具有更好的數(shù)據(jù)挖掘和保持非支配解能力，還可以提供更豐富的信息，為決策者進(jìn)行決策提供了多樣性的選擇余地。因為無線傳感器的部署網(wǎng)絡(luò)節(jié)點隨機(jī)部署有很高密度和各自的特征，因此大多數(shù)傳感器之間的橫截面覆蓋區(qū)域的重疊一方面，如果同樣的工作將導(dǎo)致能源的浪費和縮短網(wǎng)絡(luò)壽命，另一方面一些區(qū)域不需要進(jìn)行監(jiān)測，這就造成了浪費，因此如何確定網(wǎng)絡(luò)覆蓋范圍是無線傳感器網(wǎng)絡(luò)中的關(guān)鍵問題之一。目標(biāo)標(biāo)區(qū)域A為被離散化成LW個網(wǎng)格的二維矩形平面，每個網(wǎng)格代表一個待監(jiān)測小區(qū)域。因此，混合無線傳感網(wǎng)絡(luò)的覆蓋問題可以歸結(jié)為滿足網(wǎng)絡(luò)全連通條件兩目標(biāo)優(yōu)化問題，即：maxF（X）=[f1(X),f2(X)]由于隨機(jī)部署的傳感器節(jié)點是很容易形成感知覆蓋重疊區(qū)域，以便關(guān)閉由冗余節(jié)點來擴(kuò)展網(wǎng)絡(luò)的生命周期。本文提出了一種鄰里干擾與多目標(biāo)粒子群優(yōu)化算法，基于全局最優(yōu)粒子從F1在基于加權(quán)法非劣效性面前可供選擇，并從隨機(jī)選取的不同，NSGAⅡ非支配排序策略，其自己粒子局部最優(yōu)的粒子。對于一個最優(yōu)化問題，一定數(shù)量的候選解的抽象表示的種群向更好的解進(jìn)化。基于粒子群優(yōu)化的策略，可以提高無線傳感器網(wǎng)絡(luò)覆蓋性能，但算法本身就容易