【正文】 及微機(jī)電系統(tǒng)(MEMS)這五項(xiàng)技術(shù)結(jié)合而形成的一種全新的信息獲取與處理技術(shù)，就叫做無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)。(2) 基于多目標(biāo)進(jìn)化算法對(duì)無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋問題進(jìn)行算法設(shè)計(jì)。此外，由于傳感器節(jié)點(diǎn)通常是依靠電池作為能量源，并且節(jié)點(diǎn)數(shù)量巨大，也有可能被部署在偏遠(yuǎn)地區(qū)或無法達(dá)到的區(qū)域，這樣不能更換傳感器節(jié)點(diǎn)的電池能量作為主要約束網(wǎng)絡(luò)系統(tǒng)的生命周期。我們知道無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)采用電池供電，且一般工作在極端惡劣、無人值守的環(huán)境。若能實(shí)現(xiàn)無線傳感模塊的低功耗和高性能的目標(biāo)，那么其對(duì)電能的需求就會(huì)更小，能耗的減少能使得無線傳感網(wǎng)絡(luò)的應(yīng)用范圍得到進(jìn)一步的擴(kuò)大。我們知道通過降低無線傳感節(jié)點(diǎn)的硬件功耗，確定無線傳感模塊各單元的基本功率消耗，并進(jìn)行相應(yīng)比較，確定需重點(diǎn)降耗的單元能夠增加網(wǎng)絡(luò)壽命。大量的傳感器節(jié)點(diǎn)配合各種型號(hào)的傳感器，就能組成一個(gè)無線傳感器網(wǎng)絡(luò)。對(duì)于這個(gè)問題，我們選擇用多目標(biāo)進(jìn)化算法來解決是個(gè)可行的方案，首先我們了解進(jìn)化算法是一種群體智能搜索方法，它比較適合用來求解多目標(biāo)優(yōu)化的問題。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；動(dòng)態(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 。 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 。從1980年開始，人類就運(yùn)用進(jìn)化算法來解決多目標(biāo)優(yōu)化的問題。無線傳感網(wǎng)絡(luò)的產(chǎn)生開創(chuàng)了一個(gè)新的應(yīng)用領(lǐng)域，它是一種新興的概念和技術(shù)，無線傳感器網(wǎng)絡(luò)被認(rèn)為是未來四大高科技技術(shù)產(chǎn)業(yè)之一，可見它的研究?jī)r(jià)值。本文對(duì)從硬件上的探討不予研究，我們選擇基于多目標(biāo)進(jìn)化算法用來研究無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆問題，構(gòu)建無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋問題模型，并根據(jù)多目標(biāo)進(jìn)化算法的關(guān)鍵技術(shù)和基本流程，對(duì)基于無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋問題算法進(jìn)行設(shè)計(jì)，以期獲得一組最優(yōu)解。當(dāng)前無線傳感器網(wǎng)絡(luò)巨大的應(yīng)用前景得到了越來越多的關(guān)注,從而學(xué)者從上個(gè)世紀(jì)70年代就展開對(duì)無線傳感網(wǎng)絡(luò)的研究。由于傳感器節(jié)點(diǎn)電池更換困難以及數(shù)量龐大的原因，使其能耗耗完后和出現(xiàn)故障時(shí)的難以替換，無線傳感器網(wǎng)絡(luò)最重要的設(shè)計(jì)準(zhǔn)則之一就是降低傳感器節(jié)點(diǎn)的功耗。因此，提高節(jié)點(diǎn)的能量效率，延長(zhǎng)系統(tǒng)的壽命是無線傳感器網(wǎng)絡(luò)中是必不可少的。利用多目標(biāo)進(jìn)化算法的特點(diǎn)，針對(duì)我們建立的模型，從不同出發(fā)點(diǎn)考慮設(shè)計(jì)算法，得出不同覆蓋水平和網(wǎng)絡(luò)壽命的規(guī)劃方案。由傳感器節(jié)點(diǎn)、匯聚節(jié)點(diǎn)（Sink）、后臺(tái)管理中心三部分組成了無線傳感器網(wǎng)絡(luò)，如圖21所示。由此產(chǎn)生的能量是最重要的限制瓶頸，阻礙了無線傳感器網(wǎng)絡(luò)和應(yīng)用的發(fā)展方向之一。通常情況下，網(wǎng)絡(luò)覆蓋度是評(píng)價(jià)無線傳感器網(wǎng)絡(luò)的探測(cè)質(zhì)量的一個(gè)最重要的標(biāo)準(zhǔn)。網(wǎng)絡(luò)覆蓋度可以分為以下三種，即障礙覆蓋度、區(qū)域覆蓋度以及點(diǎn)覆蓋度。圖24點(diǎn)覆蓋度圖由圖中我們可以看出，黑色圓點(diǎn)處于激活狀態(tài)時(shí)三個(gè)圓的面積就把所有的傳感器包含進(jìn)去了，覆蓋度就是100%。在概率模型下，若存在多個(gè)傳感器同時(shí)工作，則一個(gè)目標(biāo)點(diǎn)p被有效探測(cè)的概率是幾個(gè)傳感器共同作用的結(jié)果。當(dāng)網(wǎng)絡(luò)從部署開始到網(wǎng)絡(luò)不工作的時(shí)間跨度就被稱為無線傳感器網(wǎng)絡(luò)的生存周期。這樣依次輪流打開不同的節(jié)點(diǎn)集合，既能完整的監(jiān)測(cè)需要檢測(cè)的環(huán)境，又能降低能耗。把以有限時(shí)間內(nèi)節(jié)能作為目標(biāo)，求出的最優(yōu)解為{A、C}，而若直接以延長(zhǎng)網(wǎng)絡(luò)壽命為目標(biāo)，則求出的最優(yōu)解為{{A、D、F}，{B、C、E}}。先明確一個(gè)概念：帕累托最優(yōu)解。本文主要研究了四種多目標(biāo)進(jìn)化算法，分別為多目標(biāo)遺傳算法、改進(jìn)的多目標(biāo)差分進(jìn)化算法、多目標(biāo)粒子群優(yōu)化算法、分布式啟發(fā)式算法對(duì)無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋問題進(jìn)行學(xué)習(xí)與分析，下文會(huì)一一進(jìn)行介紹。2）迄今為止還沒有找到其他方法比進(jìn)化算法更能有效的解決多目標(biāo)問題。視頻傳感器節(jié)點(diǎn)具有視頻傳感器的感知模型范圍是指?jìng)鞲衅鞴?jié)點(diǎn)是節(jié)點(diǎn)P（X，Y）為圓心、感知距離為R（半徑）、夾角為α的扇形區(qū)域，扇形區(qū)域的中心線Vp角度為θ，如圖31所示，因此，每個(gè)有向感知節(jié)點(diǎn)模型都可以用一個(gè)五元組X,Y,R,α,θ來表示，分別表示每個(gè)有向感知節(jié)點(diǎn)的中心位置坐標(biāo)，感知半徑，感知視角及感知方向角。與求解最大有向K覆蓋問題的貪婪算法一樣，有向感知K覆蓋控制算法也屬于一種一跳覆蓋范圍內(nèi)的分布式方法。目前的研究無線傳感器網(wǎng)絡(luò)的可靠性，通常分為兩大類：基于任務(wù)的可靠性模型和基于壽命的網(wǎng)絡(luò)可靠性模型。保證目標(biāo)區(qū)域內(nèi)的目標(biāo)事件能夠以最大的概率被感知： 公式32（2） 單位感知能耗。因?yàn)闊o線傳感器的部署網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)部署有很高密度和各自的特征，因此大多數(shù)傳感器之間的橫截面覆蓋區(qū)域的重疊一方面，如果同樣的工作將導(dǎo)致能源的浪費(fèi)和縮短網(wǎng)絡(luò)壽命，另一方面一些區(qū)域不需要進(jìn)行監(jiān)測(cè)，這就造成了浪費(fèi)，因此如何確定網(wǎng)絡(luò)覆蓋范圍是無線傳感器網(wǎng)絡(luò)中的關(guān)鍵問題之一。因此，混合無線傳感網(wǎng)絡(luò)的覆蓋問題可以歸結(jié)為滿足網(wǎng)絡(luò)全連通條件兩目標(biāo)優(yōu)化問題，即：maxF（X）=[f1(X),f2(X)]由于隨機(jī)部署的傳感器節(jié)點(diǎn)是很容易形成感知覆蓋重疊區(qū)域，以便關(guān)閉由冗余節(jié)點(diǎn)來擴(kuò)展網(wǎng)絡(luò)的生命周期。對(duì)于一個(gè)最優(yōu)化問題，一定數(shù)量的候選解的抽象表示的種群向更好的解進(jìn)化。為了獲得較高的覆蓋率的無線傳感器網(wǎng)絡(luò)的需要，通?？梢栽黾觽鞲衅鞴?jié)點(diǎn)的密度，這可以有效減少感知盲點(diǎn)出現(xiàn)的概率。2)網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)的位置信息能通過一定的方式獲取。f2越大，選取的工作節(jié)點(diǎn)數(shù)越少，節(jié)點(diǎn)冗余率就越低，說明網(wǎng)絡(luò)的能耗就相對(duì)越少。仿真結(jié)果表明，改策略能夠在達(dá)到較高覆蓋率的同時(shí)，降低網(wǎng)絡(luò)能耗并保證網(wǎng)絡(luò)能耗均衡，在保持網(wǎng)絡(luò)穩(wěn)定運(yùn)行和延長(zhǎng)網(wǎng)絡(luò)壽命方面具有一定的可行性。一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射工作即編碼工作，這其中要把對(duì)問題有用的參數(shù)反映在編碼里。更重要的是，多目標(biāo)遺傳算法的適應(yīng)度函數(shù)不僅連續(xù)可微的限制，并且它的域可以自由設(shè)定。代碼一般應(yīng)具有完整性，合理性，非冗余原則要得到滿足。（5）交叉算子遺傳算法的主要算子，有優(yōu)異的全局搜索能力。（1）編碼先設(shè)置區(qū)域大小為一個(gè)矩形格點(diǎn)區(qū)域，大小為mn的一個(gè)區(qū)域，依次按照順序?qū)Ω顸c(diǎn)進(jìn)行編號(hào)1，2，3……mn，每一個(gè)數(shù)代表一個(gè)傳感器節(jié)點(diǎn)。然后累加其選擇概率值，每一輪中，通過產(chǎn)生［0，1］內(nèi)的隨機(jī)數(shù)為指針，來確定選擇的個(gè)體。/*pop為前代種群，pop_new為下一代種群*/var fitness_value, fitness_table。 (idx == 1) if r fitness_table(mid) first = mid。 end for end for2. 交叉操作采用最常用的單點(diǎn)交叉方式。變異率為Pm，按概率Pm隨機(jī)選取要變異的個(gè)體矩陣，隨機(jī)選取某一行號(hào)，在選中的個(gè)體矩陣中用隨機(jī)產(chǎn)生的一行整數(shù)序列替換選中的這一行。圖44算法流程 仿真結(jié)果先設(shè)置區(qū)域大小為一個(gè)矩形格點(diǎn)區(qū)域，再設(shè)置監(jiān)測(cè)區(qū)域大小為5050m2.。對(duì)個(gè)體按照適應(yīng)度大小進(jìn)行排序：%對(duì)個(gè)體按適應(yīng)度大小進(jìn)行排序，并且保存最佳個(gè)體%pop_size: 種群大小%chromo_size: 染色體長(zhǎng)度function rank(pop_size, chromo_size)global fitness_value。for i=1:pop_size fitness_table(i) = 0.。 fitness_value(i) = fitness_value(min)。if fitness_value(pop_size) best_fitness best_fitness = fitness_value(pop_size)。clear temp1。%染色體大小generation_size 分別為50，100，150。從而我們能得出一個(gè)結(jié)論，整個(gè)算法迭代過程是搜索向全局最優(yōu)解的方向進(jìn)行，而且代數(shù)越大，選取的傳感器就越少，更多的冗余節(jié)點(diǎn)不工作，那么即網(wǎng)絡(luò)各區(qū)域能耗越來越均衡，網(wǎng)絡(luò)覆蓋率變高，算法不斷完善。其次，考慮了網(wǎng)絡(luò)壽命的定義和網(wǎng)絡(luò)布局特點(diǎn)等因素，給出了網(wǎng)絡(luò)覆蓋度的定義。何老師的榜樣作用深入人心，這也對(duì)我以后的學(xué)習(xí)和工作生活產(chǎn)生深遠(yuǎn)的影響。我還要感謝我的同學(xué)們，在畢業(yè)設(shè)計(jì)的困難他們都給我了許多建議和幫助，在我最困難的時(shí)候伸出援手。而建立的模型，基于多目標(biāo)遺傳算法進(jìn)行了無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋問題的算法設(shè)計(jì)，提出了基于遺傳算法的無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋問題算法，主要是對(duì)多目標(biāo)遺傳算法設(shè)計(jì)，并在此基礎(chǔ)上設(shè)計(jì)無線傳感器網(wǎng)絡(luò)滿足特定覆蓋率的生存時(shí)間，最后通過仿真結(jié)果的有效性分析，驗(yàn)證基于多目標(biāo)遺傳算法的無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋問題算法的有效性。圖45選擇節(jié)點(diǎn)分布從實(shí)際需要出發(fā)，如果注重網(wǎng)絡(luò)覆蓋，可以增加網(wǎng)絡(luò)覆蓋的重量，減少其它兩個(gè)的比重，能源消耗和能量平衡的效果將受到影響；如果專注于能源消耗和網(wǎng)絡(luò)的平衡，可以增加兩個(gè)權(quán)重后，減少覆蓋范圍，這樣的覆蓋度會(huì)受到影響。%交叉概率mutate_rate = 。打印算法迭代過程：%打印算法迭代過程%generation_size: 迭代次數(shù)function plotGA(generation_size)global fitness_avg。 for j=1:chromo_size best_individual(j) = pop(pop_size,j)。 for k = 1:chromo_size temp1(k) = pop(i,k)。temp = 1。global fitness_avg。那么適應(yīng)度函數(shù)定義式為f=+ + (1f3)，有100個(gè)傳感器，則染色體長(zhǎng)度為100。采用最大迭代次數(shù)作為終止程序的判斷條件。交叉方式為隨機(jī)選取兩個(gè)個(gè)體，再隨機(jī)選取個(gè)體矩陣的某個(gè)行號(hào)作為起始行號(hào)，將兩個(gè)體矩陣的起始行號(hào)開始的若干行進(jìn)行交換。 else idx = mid。/*隨機(jī)生成一個(gè)隨機(jī)數(shù)，在0和總適應(yīng)度之間，因?yàn)閒itness_table(pop_size)為最后一個(gè)個(gè)體的累積適應(yīng)度，即為總適應(yīng)度*/ first = 1。在比例選擇法中，各個(gè)個(gè)體的選擇概率和其適應(yīng)度值成比例。用一串二進(jìn)制編碼ni={n1,n2…nn}代表網(wǎng)絡(luò)中的節(jié)點(diǎn)是否被選中的情況，節(jié)點(diǎn)的選擇情況與染色體個(gè)體相互對(duì)應(yīng)，方框顯示1表示該位置上的傳感器被選中作為工作節(jié)點(diǎn)，方框顯示0表示該位置上的傳感器被選中作為工作節(jié)點(diǎn)表示沒有選中，即該節(jié)點(diǎn)休眠。多目標(biāo)遺傳算法交叉和變異通過不斷的互相競(jìng)爭(zhēng)和配合，以平衡全局并完成局部搜索功能。(2)適應(yīng)函數(shù)說的是個(gè)別環(huán)境適應(yīng)性評(píng)價(jià)函數(shù)。此功能使得多目標(biāo)遺傳算法大大擴(kuò)展了其應(yīng)用范圍。在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度大小挑選個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。（1）多目標(biāo)遺傳算法概念多目標(biāo)遺傳算法通常實(shí)現(xiàn)方式為一種計(jì)算機(jī)模擬。反映的是網(wǎng)絡(luò)區(qū)域之間能量消耗的均衡程度，越小表示網(wǎng)絡(luò)能量消耗越均勻，越大則說明網(wǎng)絡(luò)能耗越不均勻，越小越好，f3為： 公式312其中表達(dá)式為： 公式313得出總體目標(biāo)函數(shù)定義f = w1f1+ w2f2+ w3(1f3)，w1，w2和 w3分別為子目標(biāo)函數(shù)對(duì)應(yīng)的權(quán)值，w1+ w2+w3=1。節(jié)點(diǎn)每個(gè)周期消耗一定的能量且可以維持較多的工作周期。如果一個(gè)節(jié)點(diǎn)可以感知的區(qū)域完全能被其他節(jié)點(diǎn)完全覆蓋，這