【正文】 在這里我謹(jǐn)向何老師致以最崇高的敬意和最誠摯的感謝，感謝他對我的幫助。最終給出了網(wǎng)絡(luò)的動態(tài)覆蓋問題模型，對于給出的動態(tài)覆蓋問題的模型，因為網(wǎng)絡(luò)壽命是不確定的，這就給多目標(biāo)遺傳算法的編碼帶來了較大困難。工作節(jié)點數(shù)總體上呈減少趨勢，在算法運行過程中有很小的震蕩，這是因為由于各區(qū)域總節(jié)點數(shù)不同，需要保持區(qū)域的網(wǎng)絡(luò)能耗平衡，部分節(jié)點可能特別關(guān)鍵，需要處于工作狀態(tài)以平衡各區(qū)域間的能耗差異。%迭代次數(shù)cross_rate = 。接下來就是選擇操作、交叉操作、變異操作，這三種算法在上一節(jié)中有詳細(xì)描述。 best_generation = G。 fitness_value(min) = temp。endmin = 1。global fitness_table。算法開始是先在監(jiān)測區(qū)域內(nèi)隨機(jī)放置100個節(jié)點，再設(shè)置節(jié)點感知半徑 Rs=5m，節(jié)點的通信半徑Rc=10m，檢測模型參數(shù)λ1為1，λ2為0，β1為1，,，種群數(shù)=50，最大迭代次數(shù)=150。另外，如果后代的適應(yīng)值函數(shù)值超過取代的個體，則進(jìn)行取代操作。為了保證雙親的基因盡可能地在子代中得到保留，采用循環(huán)重組的方法。 elseif r fitness_table(mid) last = mid。/*fitness_value為種群的適應(yīng)度，fitness_table為種群累積適應(yīng) 度*/for i=1:pop_size r = rand*fitness_table(pop_size)。選擇算子采用比例選擇法，每一個染色體被選中并遺傳到下一代種群中的概率與該個體的適應(yīng)度的大小成正比。采用二進(jìn)制編碼方式的原因是基于無線傳感器網(wǎng)絡(luò)中節(jié)點隨機(jī)分布的特點，原因是二進(jìn)制編碼相對其他編碼來說編碼和解碼的操作相對簡單，染色體的交叉、變異操作便于實現(xiàn)。（6）變異算子遺傳算法的輔助算子，有優(yōu)異的局部搜索能力。二進(jìn)制編碼是最基礎(chǔ)的編碼，得到了廣泛的應(yīng)用。適應(yīng)度函數(shù)是用于將輸入的唯一要求，可以計算輸出進(jìn)行比較。在初代種群產(chǎn)生之后，即根據(jù)各個個體適應(yīng)值的大小，逐代演化產(chǎn)生適應(yīng)值越來越好的個體。計算機(jī)信息工程學(xué)院畢業(yè)設(shè)計說明書第4章 基于多目標(biāo)進(jìn)化算法的WSN動態(tài)覆蓋問題算法實現(xiàn)第4章 基于多目標(biāo)進(jìn)化算法的WSN動態(tài)覆蓋問題算法實現(xiàn)由于文章的篇幅限制以及個人精力有限,要用多目標(biāo)進(jìn)化算法實現(xiàn)對無線傳感器網(wǎng)絡(luò)的動態(tài)覆蓋問題的算法實現(xiàn)，我們要進(jìn)行算法設(shè)計和仿真結(jié)果分析，最后得出結(jié)論，本文就選擇用多目標(biāo)遺傳算法來進(jìn)行研究。能量均衡系數(shù)f3為各區(qū)域之間能量最差值的比。3)網(wǎng)絡(luò)中的各個節(jié)點具有相同的初始能量、感知半徑 Rs和通信半徑 Rc，并且有 Rc= 2Rs。但是大量的冗余數(shù)據(jù)傳輸網(wǎng)絡(luò)會導(dǎo)致傳感器節(jié)點會產(chǎn)生沖突，從而導(dǎo)致過度的能量消耗，因而在網(wǎng)絡(luò)的過早地失效。多目標(biāo)遺傳算法常用的基本概念主要包括個體、群體、基因、基因型、適應(yīng)值等。在本算法中，對于主動檢測睡眠時間表的自適應(yīng)方法來關(guān)閉或啟動傳感器節(jié)點。本算法旨在對人工很難準(zhǔn)確監(jiān)測的環(huán)境，使用固定傳感器和移動傳感器來構(gòu)建混合無線傳感器網(wǎng)絡(luò)，研究如何最大限度地提高無線傳感器網(wǎng)絡(luò)監(jiān)控和網(wǎng)絡(luò)部署優(yōu)化策略，來提高網(wǎng)絡(luò)的范圍覆蓋。在滿足網(wǎng)絡(luò)覆蓋指標(biāo)后，整個網(wǎng)絡(luò)的能耗越少，網(wǎng)絡(luò)性能越好： 公式33（3） 可靠性因子:基于多目標(biāo)差分算法的傳感器隨機(jī)覆蓋控制問題求解流程如圖33所示：圖33多目標(biāo)差分進(jìn)化算法流程無線傳感器網(wǎng)絡(luò)覆蓋控制策略，本文考慮了K重覆蓋，節(jié)點的單位能耗和可靠性因子這三項指標(biāo)的信度系數(shù)。基于壽命的網(wǎng)絡(luò)覆蓋模型從連通性對生命周期的角度可靠性分析定義了以下三個概念：（1）第一個傳感器節(jié)點的能量耗盡可視為網(wǎng)絡(luò)生活。最后，使用算法驗證了算法性能，特別相比較于隨機(jī)覆蓋算法，能大大減低覆蓋盲區(qū)比例。圖31有向感知節(jié)點模型本文研究的有向K覆蓋問題屬于目標(biāo)覆蓋，K覆蓋算法可解釋為如圖32所示的模型：假設(shè)有一個內(nèi)存覆蓋區(qū)有四個傳感器和三個目標(biāo)點，在一個特定的方向四個方向的傳感器傳感器，因此，目標(biāo)1是傳感器1和2和傳感器4覆蓋，目標(biāo)2所覆蓋的傳感器2和4中，在靶3上覆蓋傳感器2和3，具有至少兩個包括的傳感器傳感器的所有目標(biāo)，以滿足K 為2的覆蓋范圍。 3）在許多復(fù)雜的應(yīng)用問題中搜索最優(yōu)解還存在一定的困難。 二、多目標(biāo)優(yōu)化問題的特點顧名思義，多目標(biāo)問題肯定具有多個目標(biāo)函數(shù)，而且各個函數(shù)之間在最優(yōu)化方向上存在沖突。資源分配的一種理想狀態(tài)就被稱為帕累托最優(yōu)，我們假定有可分配的資源分配給固定的一群人，在沒有是任何一個人的資源變少的情況下，從改變分配的方式，使得群體中至少有一個人的資源更多，這就被稱為帕累托改進(jìn)或帕累托最優(yōu)化。在這種情況下的最優(yōu)解，得到為一個有限的時間周期來確定最節(jié)能的解決方案是不能夠維持網(wǎng)絡(luò)的壽命最長。那么網(wǎng)絡(luò)壽命的定義就是無線傳感器網(wǎng)絡(luò)能維持所要求覆蓋度的時間段數(shù)。但是我們又考慮到非功能性網(wǎng)絡(luò)的具體應(yīng)用時，無線傳感器網(wǎng)絡(luò)節(jié)點的壽命可以是死亡的時間或范圍發(fā)生的損失的第一個跨度。我們用c(s,p)為傳感器s對格點p的探測概率，那么我們定義m(s,p)=1c(s,p)，m(s,p)稱為丟失概率，設(shè)S={s1,s2…sn}為無線傳感器集合，傳感器si對目標(biāo)點p(xp,yp)的檢測概率為：公式21其中，d（si，p）為傳感器節(jié)點si與目標(biāo)點p的歐氏距離。我們通常把探測的目標(biāo)區(qū)域離散化為格點，從而將區(qū)域覆蓋問題轉(zhuǎn)化為點覆蓋問題。我們一一解釋，如下：（1）障礙覆蓋度障礙覆蓋度指的是通過障礙物而未被發(fā)現(xiàn)的概率，圖22是一個障礙覆蓋度的示意圖，其中出發(fā)點和終點分別在矩形區(qū)域上下的邊上。從目前的研究看出，評價方式有障礙覆蓋度、區(qū)域覆蓋度和點覆蓋度，我們是從這三個方式來評價一個無線傳感器網(wǎng)絡(luò)的探測質(zhì)量。（3）無線傳感器網(wǎng)絡(luò)是一個以數(shù)據(jù)為中心的網(wǎng)絡(luò)。傳感器節(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ā)送到集中處理的后臺管理中心。依次進(jìn)行分析和學(xué)習(xí)，找到適合的算法設(shè)計過程，進(jìn)行仿真環(huán)境和參數(shù)的設(shè)定，對得到的仿真結(jié)果進(jìn)行分析和比較，得出結(jié)論。并有各種不同的方式來延長系統(tǒng)的壽命，主要是從減少能源消耗和平衡節(jié)點的能量消耗，節(jié)點之間的兩方面考慮降低節(jié)點的能量消耗可以使系統(tǒng)更加可靠，從而延長網(wǎng)絡(luò)壽命周期，可避免能源系統(tǒng)的幾個節(jié)點過早耗盡而提前終止網(wǎng)絡(luò)周期，節(jié)點之間的能量消耗應(yīng)得到平衡。在21世紀(jì)初，美國再生能源辦公室工業(yè)技術(shù)計劃（ITP）發(fā)布的報告“21世紀(jì)工業(yè)無線技術(shù)”第一頁中就引用了總統(tǒng)科技顧問的一段話的提到：無線傳感器可將傳感器的能源損耗變得更少，能源利用率能提高到原來的110%。最早可以追溯到1978年,美國國防部高級研究計劃署在當(dāng)時就成立了一個分布式傳感器網(wǎng)絡(luò)學(xué)習(xí)組，并在卡內(nèi)基梅隆大學(xué)對其展開研究。 （2）研究意義無線傳感器網(wǎng)絡(luò)是一種新的理念和技術(shù)，它可以創(chuàng)造很多新的應(yīng)用。無線技術(shù)被廣泛應(yīng)用于中大型區(qū)域領(lǐng)域，如大型的無人值守環(huán)境監(jiān)測和目標(biāo)跟蹤，可以適用于戰(zhàn)爭。近年來，國內(nèi)外的學(xué)者研究了大量的多目標(biāo)進(jìn)化算法，其中的一些算法已經(jīng)可以成熟的應(yīng)用到工程實踐的過程中。 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 。本文以多目標(biāo)進(jìn)化算法在無線網(wǎng)絡(luò)傳感器網(wǎng)絡(luò)動態(tài)覆蓋中的應(yīng)用為研究課題，首先概述無線傳感器網(wǎng)絡(luò)和無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋問題的基礎(chǔ)知識，作為本文研究的理論基礎(chǔ)；然后，以無線網(wǎng)絡(luò)傳感器網(wǎng)絡(luò)的評價標(biāo)準(zhǔn)，即網(wǎng)絡(luò)覆蓋率和網(wǎng)絡(luò)壽命，確定性部署和隨機(jī)部署為依據(jù)構(gòu)建無線傳感器網(wǎng)絡(luò)覆蓋問題模型；在此基礎(chǔ)上提出多目標(biāo)遺傳算法的概念、特點、關(guān)鍵技術(shù)和基本流程，并以此為依據(jù)對無線網(wǎng)絡(luò)傳感器網(wǎng)絡(luò)動態(tài)覆蓋問題進(jìn)行算法設(shè)計，通過基于多目標(biāo)遺傳算法的無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋問題算法設(shè)計，實現(xiàn)無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋的最大優(yōu)化。采用何種方法來優(yōu)化網(wǎng)絡(luò)覆蓋度以及網(wǎng)絡(luò)壽命成為我們研究的核心，在現(xiàn)實生活中，很多的優(yōu)化問題是為了實現(xiàn)一個目標(biāo)的最大化，而我們研究的網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命是兩個互相作用且互相沖突的目標(biāo)，顯而易見它的最優(yōu)解肯定不會是一個解，而是一組均衡解。低成本、低功耗、小體積的傳感器節(jié)點的產(chǎn)生使得微機(jī)電系統(tǒng)和低功耗高集成數(shù)字設(shè)備的發(fā)展得以實現(xiàn)。如何實現(xiàn)更好的無線傳感模塊功能，增加模塊的可靠性和使用壽命是當(dāng)今熱門的問題。增加傳感模塊在無線傳感模塊應(yīng)用中已經(jīng)非常的廣泛，除了對組成無線傳感網(wǎng)絡(luò)的應(yīng)用，無線傳感技術(shù)還能應(yīng)用到環(huán)境監(jiān)測中去，特別是一些極端惡劣、無人值守的環(huán)境，它還可以運用于短距離的無線通信。而有的傳感器為了追求具有高性能，使得其功耗過大，而當(dāng)前能量受限的應(yīng)用環(huán)境已經(jīng)不再適用。該協(xié)議的一個重要目標(biāo)是擴(kuò)大網(wǎng)絡(luò)覆蓋網(wǎng)絡(luò)的壽命，并延長網(wǎng)絡(luò)的生存能有效地節(jié)省資金重新部署的傳感器節(jié)點。根據(jù)傳感器能源特性、布局特點等因素，建立動態(tài)覆蓋問題模型，明確網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命兩個評價標(biāo)準(zhǔn)的具體定義。第四章選取了基于多目標(biāo)遺傳算法的進(jìn)化算法對WSN進(jìn)行算法設(shè)計，得出仿真結(jié)果并對結(jié)果進(jìn)行分析比對，從而得出結(jié)論。微型傳感器節(jié)點通常密集分布在需要監(jiān)測的區(qū)域環(huán)境中，由于規(guī)模巨大，這是不可能人工照顧每個節(jié)點的網(wǎng)絡(luò)系統(tǒng)往往在無人值守的狀態(tài)下工作。移動終端可以在任何高速網(wǎng)絡(luò)和任意方式移動，可隨時關(guān)閉；無線收發(fā)裝置的天線類型多種多樣，與發(fā)射功率帶來的變化中的能量變化；再加上廣播的頻道，地形和氣候的方式和等因素可能會發(fā)生在由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化和改變所形成的任何無線電信道的移動終端的沖擊速度的組合之間的相互干擾是難以預(yù)測的。在滿足覆蓋率要求的前提下，科學(xué)合理的規(guī)劃傳感器的激活順序，才能盡量延長無線傳感器網(wǎng)絡(luò)的使用壽命這就是無線傳感器網(wǎng)絡(luò)的動態(tài)覆蓋問題。點覆蓋度C=N1/N2，其中N1是可以被探測到的點數(shù)，N2是總的需要探測的點數(shù)。我們把傳感器si放置在格點（x,y）,若覆蓋區(qū)域的點p坐標(biāo)為（i,j）,我們就用s與p之間的歐氏距離d(s,p)=來表示s和p的距離。所以我們要設(shè)置一個覆蓋度門檻為，使得各個時間段的覆蓋度都不能小于。探測區(qū)域有產(chǎn)生冗余一般由兩個原因?qū)е拢海?）網(wǎng)絡(luò)規(guī)模過大；（2）傳感器節(jié)點密集太過密集，這些原因會使電池間斷的工作比持續(xù)工作維持時間提高了一倍不止，由此我們可以得知間斷的打開各個傳感器節(jié)點能延長網(wǎng)絡(luò)壽命。那么這就是最優(yōu)的方案了嗎？我們繼續(xù)往下分析，當(dāng)A和C兩個傳感器電量耗盡之后，剩余的節(jié)點B、D、E、F全部打開都不能覆蓋到點G，即網(wǎng)絡(luò)覆蓋度達(dá)不到 100%，這個方案的網(wǎng)絡(luò)壽命就是A和C兩個節(jié)點的運行時間。39計算機(jī)信息工程學(xué)院畢業(yè)設(shè)計說明書第3章 多目標(biāo)進(jìn)化算法分析第3章 多目標(biāo)進(jìn)化算法分析一、多目標(biāo)進(jìn)化算法概念進(jìn)化算法又稱為演化算法，是一種模擬自然進(jìn)化過程的隨機(jī)優(yōu)化算法。我們通過不同的多目標(biāo)進(jìn)化算法，能獲得在目標(biāo)空間廣泛分布的不同的解，這就使我們有了更多的選擇余地。（1）算法過程輸入：基于多目標(biāo)算法的通用算法過程輸出：多目標(biāo)優(yōu)化解集步驟1：初始化種群步驟2：適應(yīng)值評價步驟3：進(jìn)化算子操作，生成新的種群（a） 選擇算子（b） 組合算子（c） 交叉算子步驟4：如果滿足終止條件，結(jié)束算法迭代，否則轉(zhuǎn)到步驟2。 分布式啟發(fā)式算法本文基于分布式啟發(fā)式算法對無線傳感器網(wǎng)絡(luò)的研究借鑒了文獻(xiàn)[8]的知識，K覆蓋問題的定義是：有些傳感器網(wǎng)絡(luò)中對監(jiān)測區(qū)域或目標(biāo)的覆蓋質(zhì)量具有特殊的要求，因此要求監(jiān)測區(qū)域中的每個目標(biāo)點至少被K個不同傳感器節(jié)點同時覆蓋。下面給出有向感知K覆蓋算法偽代碼：初始化：網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G（N，E）及目標(biāo)集合M分布%每一輪時間周期內(nèi)重新選擇For(Round1,...7){所有節(jié)點發(fā)送Beacon消息%按節(jié)點序號在一跳鄰居范圍內(nèi)自行遴選方向For（i=1，...,N）｝1. 收集所有一跳鄰居節(jié)點的數(shù)據(jù)，更新方向目標(biāo)集合2. 遍歷所有的目標(biāo)集合M，計算覆蓋每個集合的方向節(jié)點3. 根據(jù)遍歷結(jié)果計算本節(jié)點所有方向的效用函數(shù)值4. 計算每個方向的歸一化效用函數(shù)值5. 一效用函數(shù)值為概率隨機(jī)選擇覆蓋方向綜上所述，對無線視頻傳感器網(wǎng)絡(luò)中的有向K重覆蓋問題，假設(shè)有向傳感器節(jié)點可在幾個覆蓋方向中切換，根據(jù)傳感器節(jié)點的覆蓋方向協(xié)同優(yōu)化，實現(xiàn)覆蓋區(qū)域和目標(biāo)的最大化有向覆蓋。從網(wǎng)絡(luò)上的生命周期的工作傳感器節(jié)點的數(shù)目的影響，提出了一種可靠性因子，獲得了網(wǎng)絡(luò)的可靠性趨勢知覺半徑和傳感器節(jié)點密度的影響。通過上述推導(dǎo)的優(yōu)化問題，區(qū)域覆蓋優(yōu)化可以被定義為下面的多目標(biāo)。本文基于多目標(biāo)粒子群進(jìn)化算法對無線傳感器網(wǎng)絡(luò)的研究主要來自[10]。目標(biāo)區(qū)域A內(nèi)任一離散網(wǎng)格k，其中心坐標(biāo)為（xk，yk），如果與最鄰近傳感器節(jié)點si（xi，yi）的距離 公式34那么k點被傳感器ｓ感知到的概率P（k，s）=1；否則P（k，s）=0，