【正文】 現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)的傳感器開(kāi)路編碼每個(gè)時(shí)間段的最大動(dòng)態(tài)范圍優(yōu)化。圖43 輪盤(pán)賭選擇輪盤(pán)賭法選擇具體算法如下：Selection Algorithmvar pop, pop_new。 end if end while for j=1:chromo_size pop_new(i,j)=pop(idx,j)。這樣循環(huán)操作，直到滿足終止條件。global G。 endendfitness_tablefitness_avg(G) = fitness_table(pop_size)/pop_size。%種群大小hromo_size = 100。首先，鑒于以前有些文獻(xiàn)把延長(zhǎng)網(wǎng)絡(luò)壽命轉(zhuǎn)化為在有限時(shí)間段內(nèi)節(jié)約能量來(lái)考慮了，首先說(shuō)明了節(jié)約能量和延長(zhǎng)網(wǎng)絡(luò)壽命在有些情況下不是兩個(gè)完全相同的概念，進(jìn)而在考慮了傳感器能源特性的情況下，給出網(wǎng)絡(luò)壽命的定義。大學(xué)四年的共同學(xué)習(xí)和工作，一起奮發(fā)向上，一起廢寢忘食的學(xué)習(xí)，實(shí)現(xiàn)了我們的共同進(jìn)步，再次感謝他們陪我渡過(guò)我人生旅途上最有意義的時(shí)光。然而，對(duì)于整個(gè)網(wǎng)絡(luò)而言，由于加入用于測(cè)量該區(qū)域的能量平衡的基礎(chǔ)上，包括的遺傳算法優(yōu)化的最優(yōu)節(jié)點(diǎn)集的算法的能量消耗的均衡器系數(shù)，以實(shí)現(xiàn)更高的覆蓋率。x = 1:1:generation_size。 pop(i,k) = pop(min,k)。global best_fitness。變異具體算法如下：Mutation algorithmfor i=1:pop_size if rand mutate_rate/*mutate_rate為變異概率*/ mutate_pos = round(rand*chromo_size)。 break。設(shè)群體大小為n，其中個(gè)體i的適應(yīng)度為，則i被選擇的概率，為遺傳算法設(shè)置種群大小我M,染色體r的適應(yīng)度為fitness(r),則該染色體被選中的概率prs為（r=1,2,3，……M） 公式41如圖43所示，根據(jù)選擇概率把圓盤(pán)分成N份，其中第r個(gè)扇形的中心角為2π多目標(biāo)遺傳算法的基本流程如下文字所述：；、適應(yīng)值函數(shù)、交叉率和變異率。4)多目標(biāo)遺傳算法有顯著隱含的并行性，雖然個(gè)人在每一代只有有限數(shù)量的操作，但對(duì)于人口規(guī)模的高階信息處理量。對(duì)于一個(gè)最優(yōu)化問(wèn)題，一定數(shù)量的候選解的抽象表示的種群向更好的解進(jìn)化。設(shè)無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)si的坐標(biāo)為(xi，yi)，目標(biāo)區(qū)域?yàn)槎S矩形區(qū)域，傳感器si對(duì)目標(biāo)點(diǎn)p(xp,yp)的檢測(cè)概率為：公式37其中，d（si，p）為傳感器節(jié)點(diǎn)si與目標(biāo)點(diǎn)p的歐氏距離。因此，在運(yùn)行過(guò)程中保證能量有效和延長(zhǎng)網(wǎng)絡(luò)壽命成為無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用的關(guān)鍵。該算法是基于非支配排序策略，通過(guò)改進(jìn)多目標(biāo)粒子群優(yōu)化算法和粒子群粒子模擬移動(dòng)節(jié)點(diǎn)的位置，再加上冗余節(jié)點(diǎn)基于加權(quán)自適應(yīng)鄰干擾檢測(cè)在每次迭代取適應(yīng)值的粒子效果，從中選擇最佳的粒子參與的下一次的進(jìn)化，從而提高網(wǎng)絡(luò)的覆蓋范圍并延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期的目的。當(dāng)使用節(jié)點(diǎn)調(diào)度機(jī)制，處于休眠狀態(tài)的每個(gè)節(jié)點(diǎn)，以監(jiān)視在其覆蓋范圍運(yùn)行狀態(tài)的鄰居節(jié)點(diǎn)，如果該節(jié)點(diǎn)不是活動(dòng)的，它進(jìn)入工作狀態(tài)，否則它保持休眠狀態(tài)。本算法接著建立了K覆蓋問(wèn)題，以優(yōu)化理論模型給出的指令級(jí)并行的形式整數(shù)線性規(guī)劃的準(zhǔn)確描述。就拿本文我們研究的無(wú)線傳感器網(wǎng)絡(luò)來(lái)說(shuō)，傳感器網(wǎng)絡(luò)有兩個(gè)重要指標(biāo)，即網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命，我們?cè)O(shè)計(jì)的要求是讓網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命盡可能的大。多個(gè)覆蓋網(wǎng)絡(luò)是一種協(xié)同效應(yīng)傳感器節(jié)點(diǎn)的結(jié)果，單一的高能效不一定延長(zhǎng)網(wǎng)絡(luò)的壽命。另一方面，在某些情況下，傳感器節(jié)點(diǎn)可以密集地放置。這種方式同時(shí)也把所監(jiān)測(cè)的區(qū)域離散化，有利于建模，每個(gè)傳感器打開(kāi)會(huì)覆蓋一部分點(diǎn)。由于傳感器的電源能量有限，無(wú)線傳感器網(wǎng)絡(luò)研究的核心問(wèn)題就是如何節(jié)省無(wú)線傳感器網(wǎng)絡(luò)的工作過(guò)程中能量，最大化網(wǎng)絡(luò)的運(yùn)行壽命。圖21無(wú)線傳感器網(wǎng)絡(luò)結(jié)構(gòu)無(wú)線傳感器網(wǎng)絡(luò)具有很多鮮明的特點(diǎn)：（1）網(wǎng)絡(luò)傳感器的規(guī)模巨大。本課題是基于多目標(biāo)進(jìn)化算法在WSN的動(dòng)態(tài)覆蓋控制中應(yīng)用，通過(guò)學(xué)習(xí)多目標(biāo)進(jìn)化算法，多目標(biāo)遺傳進(jìn)化對(duì)無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋問(wèn)題進(jìn)行算法設(shè)計(jì)，我們知道多目標(biāo)進(jìn)化算法是解決多目標(biāo)優(yōu)化問(wèn)題的一種方法，在現(xiàn)實(shí)生活中，很多的優(yōu)化問(wèn)題是為了實(shí)現(xiàn)一個(gè)目標(biāo)的最大化，而我們研究的網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命是兩個(gè)互相作用且互相沖突的目標(biāo)，顯而易見(jiàn)它的最優(yōu)解肯定不會(huì)是一個(gè)解，而是一組均衡解，所以大大增加了問(wèn)題的復(fù)雜程度。當(dāng)今社會(huì)，國(guó)內(nèi)外涌現(xiàn)了許多基于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的硬件平臺(tái)，典型的傳感器包括ImoteMica系列、IRIS系列等。無(wú)線傳感器節(jié)點(diǎn)的工作環(huán)境對(duì)電池供電是非?？量痰?，因?yàn)榇罅康膫鞲衅骱碗y以更換，所以低功率無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)最重要的設(shè)計(jì)標(biāo)準(zhǔn)，即延長(zhǎng)傳感器網(wǎng)絡(luò)的壽命，使得傳感器更加可靠，耐用。 model 。 multiobjective Genetic Algorithms目錄第1章 緒論 1 1 2 2 3 3 4第2章WSN網(wǎng)絡(luò)覆蓋模型分析 4 5 WSN的動(dòng)態(tài)覆蓋問(wèn)題 6 網(wǎng)絡(luò)覆蓋度的評(píng)價(jià)標(biāo)準(zhǔn) 6 傳感器探測(cè)概率模型 8 9 9 10 10第3章 多目標(biāo)進(jìn)化算法分析 12 13 13 13 各類(lèi)多目標(biāo)進(jìn)化算法分析 14 分布式啟發(fā)式算法 14 16 18 21第4章 基于多目標(biāo)進(jìn)化算法的WSN動(dòng)態(tài)覆蓋問(wèn)題算法實(shí)現(xiàn) 25 25 25 26 26 27 仿真結(jié)果分析 31 31 33第5章 總結(jié)與展望 35第6章 致謝 37參考文獻(xiàn) 39I第1章 緒論第1章 緒論無(wú)線傳感器網(wǎng)絡(luò)憑借它的廣闊應(yīng)用前景而受到外界廣泛關(guān)注,無(wú)線傳感器網(wǎng)絡(luò)指的是那些工作在沒(méi)有人值守的地方，它消耗的能量很少，但是能源的限制能制約網(wǎng)絡(luò)覆蓋度及傳感器工作的時(shí)間，傳感器工作的時(shí)間又可稱(chēng)為網(wǎng)絡(luò)壽命，從而我們知道了無(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命這兩個(gè)評(píng)價(jià)標(biāo)準(zhǔn)。綜上所述，在無(wú)線傳感技術(shù)應(yīng)用如此廣泛的今天，在使得網(wǎng)絡(luò)覆蓋度盡可能大的前提下，又能實(shí)現(xiàn)傳感器的低功耗非常具有研究?jī)r(jià)值。各硬件平臺(tái)采用了不同的處理器和無(wú)線通信模塊是其主要的區(qū)別。利用多目標(biāo)進(jìn)化算法求解多目標(biāo)問(wèn)題是進(jìn)幾年新出現(xiàn)的一種求解思路，在無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用中，兩個(gè)重要的參考指標(biāo)就是網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命，我們可以用兩個(gè)函數(shù)來(lái)表示網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命，再利用多目標(biāo)進(jìn)化算法來(lái)求解兩個(gè)目標(biāo)的最優(yōu)解，這就是求一個(gè)雙目標(biāo)問(wèn)題的最優(yōu)解集。無(wú)線傳感器網(wǎng)路由數(shù)千個(gè)微小的傳感器組成，所以通常主要依靠增加的不是單個(gè)設(shè)備的能力，而是但大規(guī)模的、冗余的嵌入式設(shè)備協(xié)同工作，來(lái)提高系統(tǒng)的可靠性和穩(wěn)定性。為傳感器節(jié)點(diǎn)收集有關(guān)通過(guò)其他傳感器節(jié)點(diǎn)的多跳傳輸簡(jiǎn)單的數(shù)據(jù)處理環(huán)境的信息，監(jiān)測(cè)數(shù)據(jù)可以在傳輸過(guò)程中被處理的多個(gè)節(jié)點(diǎn)，通過(guò)多跳中繼數(shù)據(jù)到宿節(jié)點(diǎn)將最后直接發(fā)送到管理中心或?qū)崿F(xiàn)傳感器網(wǎng)絡(luò)通過(guò)互聯(lián)網(wǎng)背景交通管理中心，如通信衛(wèi)星和GPRS，從整個(gè)區(qū)域?qū)?shù)據(jù)發(fā)送到集中處理的后臺(tái)管理中心。圖25是一個(gè)傳感器有效覆蓋范圍示意圖：圖25傳感器有效覆蓋范圍示意圖 傳感器探測(cè)概率模型在二維網(wǎng)格模型中，傳感器在格點(diǎn)的位置，網(wǎng)格給傳感器網(wǎng)絡(luò)的探測(cè)范圍提供了一個(gè)度量標(biāo)準(zhǔn)。這樣的數(shù)據(jù)可以被記錄相鄰傳感器相關(guān)或相同的。這個(gè)帶有一個(gè)固定量，例如汽車(chē)用汽油和機(jī)油，只有汽油和機(jī)油共同作用汽車(chē)才能運(yùn)行，能跑最長(zhǎng)時(shí)間的，不一定是剩的油總量最多的，若最后全剩下機(jī)油，沒(méi)有汽油的配合，也不能開(kāi)動(dòng)。而網(wǎng)絡(luò)壽命和網(wǎng)絡(luò)覆蓋度又是一對(duì)矛盾的對(duì)象，要讓網(wǎng)絡(luò)覆蓋度大，那么必然要打開(kāi)更多的傳感器節(jié)點(diǎn)。圖32視頻傳感器網(wǎng)絡(luò)覆蓋模型有向感知K覆蓋控制算法的工作流程如下:無(wú)線視頻傳感器網(wǎng)絡(luò)部署完成后，視頻傳感器傳感器掃描各個(gè)覆蓋方向上的目標(biāo)信息，并與其一跳鄰居節(jié)點(diǎn)交換目標(biāo)信息，然后計(jì)算每個(gè)覆蓋方向的效用函數(shù)值，選取效用函數(shù)值為最大概率選擇自身的工作方向，最后將自己的方向決策通知其一跳鄰居傳感器。第三類(lèi)是根據(jù)網(wǎng)絡(luò)的生命周期定義，這種機(jī)制可以有效地延長(zhǎng)網(wǎng)絡(luò)的生命周期。目標(biāo)標(biāo)區(qū)域A為被離散化成LW個(gè)網(wǎng)格的二維矩形平面，每個(gè)網(wǎng)格代表一個(gè)待監(jiān)測(cè)小區(qū)域。基于粒子群優(yōu)化的策略，可以提高無(wú)線傳感器網(wǎng)絡(luò)覆蓋性能，但算法本身就容易陷入局部最優(yōu)，導(dǎo)致無(wú)法收斂到全局極值點(diǎn)。Re是傳感器節(jié)點(diǎn)測(cè)量可靠性參數(shù)。多目標(biāo)遺傳算法常用的基本概念主要包括個(gè)體、群體、基因、基因型、適應(yīng)值等。5)多目標(biāo)遺傳算法形式簡(jiǎn)單，它非常適合于大規(guī)模的并行計(jì)算，還能與其他方法簡(jiǎn)單的相結(jié)合，因此可以有效地模擬復(fù)雜適應(yīng)系統(tǒng)和解決多目標(biāo)的優(yōu)化問(wèn)題。,設(shè)k=0。pr。 end if mid = round((last+first)/2)。/*變異位置*/ if mutate_pos == 0 continue。global best_individual。 pop(min,k) = temp1(k)。y = fitness_avg。在同一時(shí)間，降低區(qū)域能耗和保持均衡網(wǎng)絡(luò)，從而延長(zhǎng)網(wǎng)絡(luò)的生命周期。在最后我不能忘了一直陪伴在我身邊的家人和朋友，感謝我的父母家人，是他們?cè)诤诎抵薪o了我光明，是他們用無(wú)私的厚愛(ài)和殷切的期望撐起我人生的大樹(shù)，他們將永遠(yuǎn)是我的指路明燈，使我我在人生道路上獲得前進(jìn)的巨大動(dòng)力，也是我人生中最寶貴的財(cái)富。對(duì)動(dòng)態(tài)覆蓋問(wèn)題的建模由兩個(gè)方面組成：網(wǎng)絡(luò)覆蓋度的定義和網(wǎng)絡(luò)壽命的定義。 將我們?cè)O(shè)定的參數(shù)帶入算法中：pop_size = 50。 else fitness_table(i)=fitness_table(i1)+fitness_value(i)。global pop。/*將變異位置上的數(shù)字置反*/ end ifend for圖44顯示的設(shè)計(jì)多目標(biāo)遺傳算法的算法過(guò)程，從圖中可以看出，算法先生成群體初始節(jié)點(diǎn)分布，再計(jì)算適應(yīng)度，即存儲(chǔ)最佳個(gè)體，接著就是遺傳操作（選擇、交叉、變異），然后適應(yīng)度計(jì)算，選擇出適應(yīng)性最差的個(gè)體，得到后用最佳個(gè)體代替最差個(gè)體。 break。顯然，小扇區(qū)的面積越大，參照點(diǎn)落入其中的概率也越大，即個(gè)體的適應(yīng)度越大，它被選中的機(jī)會(huì)也越多。圖41多目標(biāo)遺傳算法流程圖遺傳算法是基于動(dòng)態(tài)多目標(biāo)算法的一種設(shè)計(jì)理念，這個(gè)算法從不同的出發(fā)點(diǎn)的設(shè)計(jì)考慮算法，設(shè)計(jì)要考慮算法中使用的遺傳算法的特點(diǎn)都伴有不同程度的覆蓋和生命周期規(guī)劃網(wǎng)絡(luò)，動(dòng)態(tài)規(guī)劃方案指的是開(kāi)放型的傳感器節(jié)點(diǎn)的順序，在單位時(shí)間內(nèi)的節(jié)點(diǎn)被分成子集，每個(gè)子集，這樣的覆蓋，以滿足要求的最大數(shù)目，只有一個(gè)負(fù)責(zé)監(jiān)測(cè)目標(biāo)區(qū)域組收集的數(shù)據(jù)的傳播。(1) 編碼指的是在計(jì)算目標(biāo)問(wèn)題的實(shí)際表示，建立染色體位串之間的一一對(duì)應(yīng)關(guān)系。而帶有不同特征的染色體組合成了一個(gè)個(gè)不同的個(gè)體，染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)是某種基因組合，它決定了個(gè)體形態(tài)的外部表現(xiàn)。令Cth為目標(biāo)點(diǎn)能夠被檢測(cè)到的概率閾值，則目標(biāo)點(diǎn)能被有效檢測(cè)到的條件為： 公式39覆蓋模型為：為了有效評(píng)價(jià)網(wǎng)絡(luò)的覆蓋性能，將待監(jiān)測(cè)區(qū)域分為mn個(gè)網(wǎng)格，再將單元格簡(jiǎn)化為像素點(diǎn)。 該算法不同于算法是，在確保使用較少的節(jié)點(diǎn)，同時(shí)考慮網(wǎng)絡(luò)區(qū)域的能量平衡策略之前工作。目標(biāo)區(qū)域A內(nèi)任一離散網(wǎng)格k，其中心坐標(biāo)為（xk，yk），如果與最鄰近傳感器節(jié)點(diǎn)si（xi，yi）的距離 公式34那么k點(diǎn)被傳感器ｓ感知到的概率P（k，s）=1；否則P（k，s）=0，在此基礎(chǔ)上，將網(wǎng)格k（xk，yk）的覆蓋定義為該網(wǎng)格被處于工作狀態(tài)的傳感器節(jié)點(diǎn)集X=｛s1,...,sn｝中至少一個(gè)感知到的概率，即： 公式35因此，無(wú)線傳感網(wǎng)絡(luò)覆蓋就是該網(wǎng)絡(luò)中處于工作狀態(tài)的傳感器節(jié)點(diǎn)集X所覆蓋網(wǎng)格點(diǎn)的總和，記為Cov（X）即： 公式36處于休眠狀態(tài)的傳感器數(shù)量記為：Sleep（X）=N+M|X||X|表示集合Ｘ的元素個(gè)數(shù)。通過(guò)上述推導(dǎo)的優(yōu)化問(wèn)題，區(qū)域覆蓋優(yōu)化可以被定義為下面的多目標(biāo)。下面給出有向感知K覆蓋算法偽代碼：初始化：網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G（N，E）及目標(biāo)集合M分布%每一輪時(shí)間周期內(nèi)重新選擇For(Round1,...7){所有節(jié)點(diǎn)發(fā)送Beacon消息%按節(jié)點(diǎn)序號(hào)在一跳鄰居范圍內(nèi)自行遴選方向For（i=1，...,N）｝1. 收集所有一跳鄰居節(jié)點(diǎn)的數(shù)據(jù)，更新方向目標(biāo)集合2. 遍歷所有的目標(biāo)集合M，計(jì)算覆蓋每個(gè)集合的方向節(jié)點(diǎn)3. 根據(jù)遍歷結(jié)果計(jì)算本節(jié)點(diǎn)所有方向的效用函數(shù)值4. 計(jì)算每個(gè)方向的歸一化效用函數(shù)值5. 一效用函數(shù)值為概率隨機(jī)選擇覆蓋方向綜上所述，對(duì)無(wú)線視頻傳感器網(wǎng)絡(luò)中的有向K重覆蓋問(wèn)題，假設(shè)有向傳感器節(jié)點(diǎn)可在幾個(gè)覆蓋方向中切換，根據(jù)傳感器節(jié)點(diǎn)的覆蓋方向協(xié)同優(yōu)化，實(shí)現(xiàn)覆蓋區(qū)域和目標(biāo)的最大化有向覆蓋。（1）算法過(guò)程輸入：基于多目標(biāo)算法的通用算法過(guò)程輸出：多目標(biāo)優(yōu)化解集步驟1：初始化種群步驟2：適應(yīng)值評(píng)價(jià)步驟3：進(jìn)化算子操作，生成新的種群（a） 選擇算子（b） 組合算子（c） 交叉算子步驟4