無(wú)線傳感器數(shù)學(xué)模型

1、精選優(yōu)質(zhì)文檔-傾情為你奉上無(wú)線傳感器網(wǎng)絡(luò)壽命優(yōu)化模型組員：秦富春（） 賈媛媛（）王超 （信息學(xué)院）無(wú)線傳感器網(wǎng)絡(luò)壽命優(yōu)化模型【摘要】本文解決的是在壽命判定過(guò)程中，如何解決節(jié)點(diǎn)與Sink之間的能量空洞問(wèn)題以及有效覆蓋率的問(wèn)題。根據(jù)幾個(gè)問(wèn)題，提出了響應(yīng)的數(shù)學(xué)模型和算法。問(wèn)題一：“當(dāng)最小簇壽命結(jié)束后，網(wǎng)絡(luò)有效覆蓋率低于門(mén)限值即時(shí)，網(wǎng)絡(luò)壽命結(jié)束”，這里取；問(wèn)題二：（模型一）定義為“能夠小基站傳輸信息節(jié)點(diǎn)的壽命結(jié)束時(shí)為傳感器網(wǎng)絡(luò)壽命”。本文先動(dòng)態(tài)路由模型，當(dāng)傳感器節(jié)點(diǎn)失效時(shí)，根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)更新節(jié)點(diǎn)的路由，尋找下一個(gè)離基站較近的節(jié)點(diǎn)，以提高網(wǎng)絡(luò)壽命。再根據(jù)線性規(guī)劃最大化最小化建立求解公式，對(duì)此算法

2、進(jìn)行仿真與分析，周期數(shù)提高了74%左右，能量利用率提高了36%，結(jié)果表明這種基于動(dòng)態(tài)路由的算法能夠拓展網(wǎng)絡(luò)壽命，大幅度提高接受或發(fā)送信息的數(shù)量，提高節(jié)點(diǎn)的使用率；（模型二）定義為“當(dāng)最小簇壽命結(jié)束后，失效節(jié)點(diǎn)數(shù)量的增加致使網(wǎng)絡(luò)有效覆蓋率低于門(mén)限值的時(shí)候，則認(rèn)為傳感器網(wǎng)絡(luò)的壽命到期”根據(jù)以上模型的不足，本文提出了基于分簇法與覆蓋定理的動(dòng)態(tài)路由模型，使用了簇與簇頭節(jié)點(diǎn)的耗能響亮來(lái)具體刻畫(huà)每個(gè)簇能量的消耗方式，建立了最大化簇壽命的整數(shù)線性規(guī)劃模型，在此模型中，我們分析了分簇機(jī)制與最大跳數(shù)，進(jìn)一步建立了改進(jìn)的就近分簇機(jī)制下簇中簇頭變換與簇的壽命的關(guān)系，并且根據(jù)GAF算法和ASCENT算法提出了隨機(jī)簇頭

3、選舉算法和節(jié)點(diǎn)狀態(tài)控制算法。最后根據(jù)算法用MATLAB對(duì)其過(guò)程進(jìn)行了仿真，周期數(shù)達(dá)到了350左右，能量利用率達(dá)到97%左右，結(jié)果表明此模型對(duì)于以上問(wèn)題有跟好的優(yōu)化效果問(wèn)題三：在隨機(jī)簇頭選舉算法和ASCENT狀態(tài)控制算法的基礎(chǔ)上建立了一種新的控制和判定算法。此算法的難度為問(wèn)題四：Z =100m ×100m的區(qū)域內(nèi)隨機(jī)拋灑N =100只傳感器，根據(jù)算法三對(duì)其進(jìn)行仿真，周期數(shù)達(dá)到了350左右，能良率用率達(dá)到97%以上。仿真結(jié)果說(shuō)明此算法是對(duì)傳感器網(wǎng)絡(luò)進(jìn)行了很大程度的優(yōu)化【關(guān)鍵詞】動(dòng)態(tài)路由 分簇機(jī)制 覆蓋率 網(wǎng)絡(luò)壽命 GAF ASCENT一、 問(wèn)題的重述隨著通信技術(shù)的日益成熟，具有感知能力、

4、計(jì)算機(jī)能力和通信能力的傳感器開(kāi)始在世界范圍內(nèi)出現(xiàn)。傳感器有電源、感知部件、嵌入式處理器、存儲(chǔ)器、通信部件和軟件幾個(gè)部分組成。由傳感器構(gòu)成的網(wǎng)絡(luò)的性能直接影響其可用性，如何評(píng)價(jià)一個(gè)傳感器網(wǎng)絡(luò)的性能是需要深入研究的課題。傳感器在擁有大量有點(diǎn)的同時(shí)還存在一些不足，例如能源的有效性。如何能讓傳感器達(dá)到人們想要的標(biāo)準(zhǔn)，還需要進(jìn)一步的優(yōu)化。由于傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量、計(jì)算資源、通信能力和節(jié)點(diǎn)可靠性都是十分有限的，因此如何充分利用節(jié)點(diǎn)的能量增加傳感器的壽命成為一個(gè)重要的研究課題。本文要解決的問(wèn)題如下：（1）本文認(rèn)為“網(wǎng)絡(luò)壽命的定義為網(wǎng)絡(luò)中第一個(gè)失效節(jié)點(diǎn)的壽命”是不恰當(dāng)?shù)?，?qǐng)您給出合理的刻畫(huà)傳感器網(wǎng)絡(luò)壽命（生命周

5、期）的定義；（2）假設(shè)網(wǎng)絡(luò)中僅有一個(gè)基站，基站位于場(chǎng)景的某固定位置，傳感器節(jié)點(diǎn)的初始能量，節(jié)點(diǎn)周期采集信息的數(shù)量，以及節(jié)點(diǎn)的通信半徑等已知的，建立了優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)壽命（生命周期）（相應(yīng)于問(wèn)題1中給出）的動(dòng)態(tài)路由策略的數(shù)學(xué)模型；（3）設(shè)計(jì)了優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)壽命（生命周期）的動(dòng)態(tài)路由算法；（4）設(shè)在 Z =100m ×100m的區(qū)域內(nèi)隨機(jī)拋灑N =100只傳感器，它們均勻地分布,基站位于場(chǎng)景的中心位置。傳感器節(jié)點(diǎn)的初始能量為1000J, 發(fā)送信息能耗1J/bit, 傳感器節(jié)點(diǎn)接受信息沒(méi)有能耗,節(jié)點(diǎn)周期采集信息的數(shù)量 S =1bit，節(jié)點(diǎn)的通信半徑 r =20m,節(jié)點(diǎn)在TDMA分配的

6、時(shí)隙內(nèi)周期地向基站發(fā)送信息。使用本文設(shè)計(jì)的算法給出該傳感器網(wǎng)絡(luò)的壽命以及基站接受到的信息的數(shù)量。二、基本假設(shè)（1） 傳感器網(wǎng)絡(luò)僅僅是傳感器和基站作為的節(jié)點(diǎn)網(wǎng)絡(luò)（2） 基站作為網(wǎng)絡(luò)中唯一的信宿，節(jié)點(diǎn)用0號(hào)節(jié)點(diǎn)標(biāo)，基站耗能不予討論（3） 影響傳感器網(wǎng)絡(luò)的壽命就是取決于傳感器的壽命（4） 節(jié)點(diǎn)不工作時(shí)認(rèn)為耗能為0（5） 基站能夠通過(guò)GPS獲得傳感器的位置信息（6） 對(duì)給定的一個(gè)簇，將所有簇內(nèi)節(jié)點(diǎn)采集一次數(shù)據(jù)并通過(guò)路由方式傳給簇頭，最終將數(shù)據(jù)傳送到基站所用的時(shí)間為一個(gè)周期。（7） ,保證在網(wǎng)絡(luò)充分覆蓋時(shí)網(wǎng)絡(luò)總是連通的，因此在覆蓋連通性問(wèn)題可簡(jiǎn)化為單獨(dú)的覆蓋控制問(wèn)題。三、符號(hào)說(shuō)明：節(jié)點(diǎn)之間的跳數(shù)：節(jié)點(diǎn)之

7、間的距離：節(jié)點(diǎn)簇內(nèi)通信半徑：所有節(jié)點(diǎn)的初始能量：隨機(jī)拋灑到場(chǎng)景中傳感器的個(gè)數(shù)：第個(gè)傳感器的鄰居節(jié)點(diǎn)集合：每周期采集的信息量四、模型的建立、求解與分析4.1模型一：基于動(dòng)態(tài)路由優(yōu)化傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)壽命模型由于傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量、計(jì)算資源、通信能力和節(jié)點(diǎn)可靠性都是十分有限的，因此我們將傳感器網(wǎng)絡(luò)的壽命拓展為網(wǎng)絡(luò)中能夠想基站傳輸信息節(jié)點(diǎn)的壽命。問(wèn)題一中把網(wǎng)絡(luò)壽命的定義為“第一個(gè)失效節(jié)點(diǎn)的壽命”。顯然，由于個(gè)別節(jié)點(diǎn)的失效而導(dǎo)致整個(gè)網(wǎng)絡(luò)信息的傳輸過(guò)程的終止時(shí)不能充分利用節(jié)點(diǎn)的能量的。此模型中，我們先將網(wǎng)絡(luò)壽命定義為“能夠小基站傳輸信息節(jié)點(diǎn)的壽命結(jié)束時(shí)為傳感器網(wǎng)絡(luò)壽命”。首先，通過(guò)線性規(guī)劃確定節(jié)點(diǎn)的路由策

8、略以最大最小節(jié)點(diǎn)壽命；其次，當(dāng)場(chǎng)景中的傳感器節(jié)點(diǎn)由于能量耗盡而無(wú)法繼續(xù)相機(jī)站發(fā)送信息時(shí)，基站將根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)更新節(jié)點(diǎn)的路由策略，最后，當(dāng)場(chǎng)景中不再有節(jié)點(diǎn)能夠像基站傳輸信息時(shí)網(wǎng)絡(luò)壽命終止。4.1.1網(wǎng)絡(luò)拓?fù)淠Ｐ徒o定一個(gè)無(wú)線傳感器網(wǎng)絡(luò)，集合是節(jié)點(diǎn)集對(duì)應(yīng)場(chǎng)景中靜止的節(jié)點(diǎn)，集合是邊集。對(duì)，當(dāng)且僅當(dāng)位于相互的傳輸范圍之內(nèi)。是的鄰居節(jié)點(diǎn)集合。為此，可以得到節(jié)點(diǎn)的周期耗能式中為向發(fā)送的信息數(shù)量，是收發(fā)信息的能量損失系數(shù)。則得到節(jié)點(diǎn)的壽命：為的剩余能量。于是，可以推斷出傳感器的壽命為。4.1.2線性規(guī)劃模型基于保證基站接受信息的有效性，則必須場(chǎng)景中的所有傳感器節(jié)點(diǎn)將其采集的信息通過(guò)一定的路由發(fā)送給基站。因

9、此，對(duì)每一個(gè)節(jié)點(diǎn)傳輸?shù)呢?fù)載應(yīng)該是該節(jié)點(diǎn)出示的負(fù)載與從他節(jié)點(diǎn)接受的負(fù)載之和，即。應(yīng)用線性規(guī)劃最大最小網(wǎng)絡(luò)壽命可得目標(biāo)函數(shù)：約束條件：其中對(duì)應(yīng)場(chǎng)景中各個(gè)階段的拓?fù)浣Y(jié)構(gòu)。當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)因耗能而無(wú)法繼續(xù)傳播信息時(shí)，基站個(gè)更新網(wǎng)絡(luò)中的拓?fù)浜笾匦聻楣?jié)點(diǎn)分配路由信息。當(dāng)基站的一跳節(jié)點(diǎn)完全失效后網(wǎng)絡(luò)的壽命結(jié)束，則可以看出：根據(jù)最大最小的定義可將上述問(wèn)題轉(zhuǎn)化為目標(biāo)函數(shù)：約束條件： 4.1.3算法一初始化：獲取場(chǎng)景中的拓?fù)湫畔?，。Step1：執(zhí)行（3）的線性規(guī)劃過(guò)程，獲取節(jié)點(diǎn)的路由信息；Step2：當(dāng)網(wǎng)絡(luò)中有節(jié)點(diǎn)因能量耗盡而失效時(shí)，更新網(wǎng)絡(luò)拓?fù)?，如果存在基站的一跳?jié)點(diǎn)，則轉(zhuǎn)到（1），；Step3：網(wǎng)絡(luò)壽命；Ste

10、p4：結(jié)束end。隨機(jī)拋灑節(jié)點(diǎn)初始化節(jié)點(diǎn)尋找鄰接節(jié)點(diǎn)找離基站最近的鄰接節(jié)點(diǎn)連通出送數(shù)據(jù)基站鄰接節(jié)點(diǎn)能量耗盡網(wǎng)絡(luò)壽命結(jié)束是否為驗(yàn)證算法的有效性，在MATLAB仿真環(huán)境中隨機(jī)均勻的拋灑只傳感器于的場(chǎng)景中，基站位于中心位置，傳感器節(jié)點(diǎn)的初始能量為，發(fā)送信息耗能，傳感器節(jié)點(diǎn)接受信息時(shí)沒(méi)有耗能，節(jié)點(diǎn)周期采集信息的數(shù)量，通信半徑。以TDMA方式周期的向基站發(fā)送信息。4.1.4用MATLAB仿真結(jié)果如下：網(wǎng)絡(luò)壽命比文獻(xiàn)提高了74.58%，并且接受到的信息也增加了84.23，能量使用率36.25%。4.1.5模型一分析本文提出了一種通過(guò)現(xiàn)行規(guī)劃和動(dòng)態(tài)路由更新來(lái)延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)壽命的最優(yōu)算法。當(dāng)場(chǎng)景中的傳感器

11、節(jié)點(diǎn)由于能量耗盡而無(wú)法繼續(xù)想基站傳輸信息時(shí)，基站將根據(jù)網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)更新節(jié)點(diǎn)的路由策略以延長(zhǎng)網(wǎng)絡(luò)壽命，從而增加基站接收信息的數(shù)量和提高節(jié)點(diǎn)能量使用效率。但是，由于本文將傳感器網(wǎng)絡(luò)的壽命定義為網(wǎng)絡(luò)中能夠向基站在一跳范圍內(nèi)直接傳輸信息節(jié)點(diǎn)的壽命。此模型將會(huì)產(chǎn)生基站的“能量空洞”，即由于基站周?chē)墓?jié)點(diǎn)要擔(dān)當(dāng)更多的信息轉(zhuǎn)發(fā)任務(wù)，所以盡管其它節(jié)點(diǎn)剩余能量較多，這些節(jié)點(diǎn)的能量將提早耗盡而使網(wǎng)絡(luò)壽命結(jié)束，如圖：YXRSink節(jié)點(diǎn)傳感器網(wǎng)絡(luò)示意圖基站有效節(jié)點(diǎn)失效節(jié)點(diǎn)由于基站周?chē)?jié)點(diǎn)承擔(dān)更多的數(shù)據(jù)包轉(zhuǎn)發(fā)任務(wù)，這些節(jié)點(diǎn)很容易耗盡自身的能量而過(guò)早失效。此時(shí)，盡管網(wǎng)絡(luò)中還有大量未被充分利用的能量資源，但由于Sin

12、k附近出現(xiàn)的“能量空洞”問(wèn)題，導(dǎo)致網(wǎng)絡(luò)壽命的提早結(jié)束。4.2模型二：基于分簇法與覆蓋定理的動(dòng)態(tài)路由模型以下本文對(duì)動(dòng)態(tài)路由算法進(jìn)行了改進(jìn)，結(jié)合了分簇法和覆蓋定理的運(yùn)用，提出了改進(jìn)的GAF算法和ASCENT算法，有效的控制了節(jié)點(diǎn)能量的充分使用。4.2.1網(wǎng)絡(luò)壽命的定義 網(wǎng)絡(luò)壽命的定義：當(dāng)最小簇壽命結(jié)束后，失效節(jié)點(diǎn)數(shù)量的增加致使網(wǎng)絡(luò)有效覆蓋率低于門(mén)限值的時(shí)候，則認(rèn)為傳感器網(wǎng)絡(luò)的壽命到期。 簇壽命的定義：本為將簇內(nèi)首個(gè)節(jié)點(diǎn)能量消耗殆盡前蓋簇運(yùn)行的周期數(shù)稱(chēng)為簇的壽命。而網(wǎng)絡(luò)的壽命最小值則是所有簇的最小壽命，反之則是網(wǎng)絡(luò)壽命的最大值。4.2.2模型的建立該模型通過(guò)簇的能耗向量和簇頭及誒單的能耗向量來(lái)刻畫(huà)簇

13、在每個(gè)周期的向量消耗情況，建立最大化簇壽命的整數(shù)線性規(guī)劃模型。運(yùn)用該模型對(duì)兩種不同分簇的方法進(jìn)行了比較并對(duì)其進(jìn)行了改進(jìn)?；诰徒c(diǎn)分簇的改進(jìn)：本文以100m*100m的范圍內(nèi)，通信半徑r=20m，基站位于圖形中心位置為例如圖1，進(jìn)行說(shuō)明：100m100m60m60m圖1基站目標(biāo)區(qū)域被劃分成4個(gè)60m*60m的小區(qū)域，在一定的覆蓋率下，該區(qū)域至少要滿足由4個(gè)節(jié)點(diǎn)覆蓋。設(shè)在該區(qū)域內(nèi)共有個(gè)初始節(jié)點(diǎn)，由基站在其中隨機(jī)產(chǎn)生一個(gè)初始簇頭，該區(qū)域的最大跳數(shù)，又到基站的最大跳數(shù)，故該區(qū)域以4跳為最大跳數(shù)。簇成員節(jié)點(diǎn)采用單挑方式將探測(cè)的數(shù)據(jù)發(fā)送到簇頭，簇頭通過(guò)多條方式將數(shù)據(jù)發(fā)送到基站Sink。下面分析就近分簇機(jī)

14、制下的簇結(jié)構(gòu)，其中節(jié)點(diǎn)1為初始節(jié)點(diǎn)，它在兩跳范圍內(nèi)廣播如圖2，對(duì)于初始節(jié)點(diǎn)1，作為簇頭其它節(jié)點(diǎn)把收集到的數(shù)據(jù)傳給節(jié)點(diǎn)1，由節(jié)點(diǎn)1發(fā)送給基站，但在下一個(gè)周期時(shí)，由節(jié)點(diǎn)4擔(dān)當(dāng)簇頭如圖3，我們可以發(fā)現(xiàn)由于粗結(jié)構(gòu)沒(méi)有發(fā)生改變，故節(jié)點(diǎn)1的能耗并不會(huì)減少，由此可以推斷，在就近節(jié)點(diǎn)分發(fā)中初始簇頭節(jié)點(diǎn)必先能量過(guò)早的耗盡，從而使其它節(jié)點(diǎn)的能量不能充分利用。12345圖212345圖34.2.3就近點(diǎn)分簇機(jī)制下簇結(jié)構(gòu)的調(diào)整 在就近點(diǎn)分簇機(jī)制形成的簇結(jié)構(gòu)下，由于要擔(dān)當(dāng)想基站發(fā)送數(shù)據(jù)的任務(wù)分簇初始節(jié)點(diǎn)對(duì)應(yīng)的分量值始終大于其余節(jié)點(diǎn)所對(duì)應(yīng)的分量值。出世界店需要在每個(gè)周期中轉(zhuǎn)發(fā)更多的數(shù)據(jù)，從而過(guò)早的將其能量消耗完畢。 為解

15、決這個(gè)問(wèn)題，在保證每個(gè)簇連通性的前提下，改變簇的結(jié)構(gòu)，使每個(gè)節(jié)點(diǎn)均隨著簇頭的改變來(lái)調(diào)整到達(dá)簇頭的路徑，從而減少分簇初始節(jié)點(diǎn)需要轉(zhuǎn)發(fā)的數(shù)據(jù)量，降低初始節(jié)點(diǎn)能量的消耗，改變后的路徑如圖412345圖44.2.4數(shù)學(xué)模型用圖來(lái)表示一個(gè)簇結(jié)構(gòu)，其中表示點(diǎn)集，表示邊集。如圖，改圖的的鄰接矩陣稱(chēng)為簇的鄰接矩陣，記為.12345圖2則該簇的鄰接矩陣為：令向量，則該簇的能量向量=鄰接矩陣A*向量，能量向量刻畫(huà)了每一個(gè)周期該簇中的各節(jié)點(diǎn)將數(shù)據(jù)發(fā)送到簇頭的過(guò)程中所消耗的能量。圖中所示的簇能耗向量為，其中第一個(gè)節(jié)點(diǎn)及簇頭盡管在一個(gè)周期內(nèi)沒(méi)有發(fā)送信息，但因要向基站發(fā)送接收到的其它節(jié)點(diǎn)信息而消耗更多的能量，如果固定一個(gè)

16、節(jié)點(diǎn)從當(dāng)簇頭，勢(shì)必使該節(jié)點(diǎn)的能量很快耗盡。所以，為了延長(zhǎng)簇的壽命，避免一個(gè)節(jié)點(diǎn)過(guò)早的把能量消耗完，在一個(gè)簇里簇頭應(yīng)該是不停變化的，該模型設(shè)計(jì)的是將簇里所有節(jié)點(diǎn)進(jìn)行輪換當(dāng)簇頭以便避免單個(gè)節(jié)點(diǎn)消耗過(guò)多的能量，每一個(gè)節(jié)點(diǎn)在當(dāng)過(guò)一次簇頭后，由計(jì)數(shù)器對(duì)其進(jìn)行記錄，控制器基站控制器總是尋找PC值最小的節(jié)點(diǎn)對(duì)其發(fā)送路由信息使其擔(dān)當(dāng)下一輪的簇頭直到簇內(nèi)第一個(gè)節(jié)點(diǎn)能量消耗完。簇頭向基站發(fā)送數(shù)據(jù)消耗的能量與簇頭到基站的跳數(shù)有關(guān)，則我們可以定義簇頭向基站發(fā)送數(shù)據(jù)的能量消耗向量為，為簇頭到基站的距離，為節(jié)點(diǎn)間的通信距離。我們定義如下符號(hào)： ;則可以得到關(guān)于網(wǎng)絡(luò)壽命的數(shù)學(xué)模型：目標(biāo)函數(shù)： 約束條件： 顯然這個(gè)是個(gè)整數(shù)規(guī)

17、劃問(wèn)題，目標(biāo)函數(shù)的表示的是所有節(jié)點(diǎn)擔(dān)當(dāng)簇頭周期數(shù)的求和最大值即最大簇壽命4.2.5算法二：Step1：每個(gè)周期開(kāi)始，基站根據(jù)PC值隨機(jī)選取一個(gè)節(jié)點(diǎn)作為簇頭并向其發(fā)送路由信息；Step2：收到路由信息的節(jié)點(diǎn)向其周?chē)l(fā)送一跳的路由信息，并且計(jì)數(shù)器加1；周?chē)?jié)點(diǎn)在第一次接受到發(fā)送節(jié)點(diǎn)的路由信息后繼續(xù)執(zhí)行相同操作Step2，以后的接受的路由信息則忽略不計(jì)，直到計(jì)數(shù)器加到3為止，轉(zhuǎn)入Step3；Step3：接受到路由信息的節(jié)點(diǎn)與它上一級(jí)即對(duì)其發(fā)送路由信息的節(jié)點(diǎn)連接；Step4：由于所有節(jié)點(diǎn)向基站的發(fā)送數(shù)據(jù)的跳數(shù)不會(huì)超過(guò)3，所以在Step2完成時(shí)沒(méi)有接受到路由信息的節(jié)點(diǎn)直接向基站發(fā)送數(shù)據(jù)信息；轉(zhuǎn)入Step

18、1；Step5：直到第一個(gè)節(jié)點(diǎn)能量消耗完時(shí)停止，執(zhí)行Stop命令；算法模擬的流程圖如下：隨機(jī)拋灑節(jié)點(diǎn)初始化節(jié)點(diǎn)基于隨機(jī)簇頭選舉算法選取簇頭簇頭在一跳范圍內(nèi)廣播，PC=PC+1節(jié)點(diǎn)在第一次接到節(jié)點(diǎn)后根據(jù)路由信息與上級(jí)相連，并且記錄跳數(shù)判斷跳數(shù)是否為3否未接受到信息的節(jié)點(diǎn)直接與基站相連是一周期后是否有節(jié)點(diǎn)能量耗盡否簇壽命結(jié)束是基于GAF算法的隨機(jī)簇頭選舉算法基于算法的節(jié)點(diǎn)狀態(tài)控制算法ASCENT基于GAF隨機(jī)簇頭選擇算法：每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)空隙時(shí)發(fā)送消息進(jìn)行選舉，基站根據(jù)的消息內(nèi)送，選擇最大值，再根據(jù)最小值的節(jié)點(diǎn)對(duì)其進(jìn)行隨機(jī)選取，基站向被選中的節(jié)點(diǎn)放送成功消息，其它未選舉成功的節(jié)點(diǎn)進(jìn)入偵聽(tīng)狀態(tài)，準(zhǔn)備加

19、入該簇頭的網(wǎng)絡(luò)結(jié)構(gòu)中。基于ASCENT算法的節(jié)點(diǎn)狀態(tài)控制算法： 把每個(gè)節(jié)點(diǎn)分為4個(gè)狀態(tài),如下：A、 休眠狀態(tài)：節(jié)點(diǎn)關(guān)閉通行模塊，能量消耗最?。籅、 偵聽(tīng)狀態(tài)：節(jié)點(diǎn)只對(duì)信息進(jìn)行偵聽(tīng)，不進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)；C、 測(cè)試狀態(tài)：是一個(gè)暫態(tài)，參與數(shù)據(jù)包的轉(zhuǎn)發(fā)，并且進(jìn)行一定的運(yùn)算，判斷自己是否需要變?yōu)榛顒?dòng)狀態(tài)；D、 活動(dòng)狀態(tài)：節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)包的轉(zhuǎn)發(fā)，能量消耗最大節(jié)點(diǎn)在確定簇頭被選舉后，都處于偵聽(tīng)狀態(tài)，以根據(jù)接收到的路由信息確定自己的簇結(jié)構(gòu)位子，之后進(jìn)入測(cè)試狀態(tài)，如果測(cè)試成功，返回值為“1”，節(jié)點(diǎn)啟動(dòng)為活動(dòng)狀態(tài)，從而進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)。否則返回值為“0”，繼續(xù)進(jìn)入偵聽(tīng)狀態(tài)。4.2.6基于MATLAB的模型仿真求解本文

20、定義基本概念如下：簇壽命值：一個(gè)簇內(nèi)第一個(gè)節(jié)點(diǎn)的能量消耗完時(shí)簇所運(yùn)行的周期數(shù)；簇的能量利用率：當(dāng)壽命結(jié)束時(shí)，簇內(nèi)所有節(jié)點(diǎn)的剩余能量之和與簇內(nèi)個(gè)節(jié)點(diǎn)的初始能量之和的比，為簇能量利用率簇最短壽命值 最短能量利用率（） 簇最長(zhǎng)壽命值 最長(zhǎng)能量利用率（）假設(shè)在S=100m*100m的目標(biāo)區(qū)域內(nèi)，隨機(jī)拋灑100個(gè)節(jié)點(diǎn)，基站位于區(qū)域中央，每個(gè)節(jié)點(diǎn)擁有1000單位能量，每發(fā)送一次需要消耗1單位能量，通信半徑r=20m。根據(jù)以上的數(shù)學(xué)模型以及算法設(shè)計(jì)，用MATLAB對(duì)其進(jìn)行仿真實(shí)驗(yàn)。結(jié)果如下：22092.2%32082.2%91.8%31381.6%21592.8%32582.6%223 從表中數(shù)據(jù)可見(jiàn)，改進(jìn)

21、的算法使得簇的壽命和能量利用率有很大的提高。不僅如此，這表明改進(jìn)的算法能較好地平衡節(jié)點(diǎn)間的能量消耗，提高了網(wǎng)絡(luò)的能量利用率。4.2.7引入覆蓋定理的數(shù)學(xué)模型 該模型研究了理想的數(shù)據(jù)融合技術(shù)下的傳感器網(wǎng)絡(luò)中最大化簇的壽命問(wèn)題。定了了簇的能量消耗向量，分析了簇內(nèi)能量消耗情況，獲得了在固定簇結(jié)構(gòu)下簇內(nèi)能消耗向量不變的性質(zhì)，建立了最大化簇壽命的整數(shù)線性規(guī)劃模型，運(yùn)用該模型分析了在改進(jìn)的分簇機(jī)制下簇的壽命。計(jì)算機(jī)仿真結(jié)果顯示，這種調(diào)節(jié)能有效地延長(zhǎng)簇的壽命，同時(shí)減小信息傳輸?shù)钠骄舆t。 但該模型并沒(méi)有考慮到節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域的網(wǎng)絡(luò)覆蓋率，對(duì)以上模型而言，如果當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)能量消耗完時(shí)，顯然其它節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域的覆

22、蓋率乃無(wú)明顯下降，所以我們可以對(duì)其進(jìn)行優(yōu)化，使其在第一個(gè)節(jié)點(diǎn)能量消耗完時(shí)考慮其它可行的路徑。我們?cè)谶@里引入模型假設(shè)（7）即節(jié)點(diǎn)通行半徑不小于2倍感知半徑，在此假設(shè)我們可以推斷出，只要兩節(jié)點(diǎn)覆蓋區(qū)相交則必能連同。 對(duì)于網(wǎng)絡(luò)中任意目標(biāo)點(diǎn)，節(jié)點(diǎn)與的歐氏距離為： 由于節(jié)點(diǎn)是以隨機(jī)均勻拋灑在目標(biāo)區(qū)域的，所以這種不確定性導(dǎo)致目標(biāo)區(qū)域里的點(diǎn)不是以相同概率被覆蓋的。 針對(duì)這一問(wèn)題，本文提出了一種基于網(wǎng)格劃分的逐點(diǎn)測(cè)定方法。其基本思想如下：（以的目標(biāo)區(qū)域?yàn)槔┤鐖D，100m100m60m60m基站網(wǎng)絡(luò)有效覆蓋率的網(wǎng)格劃分測(cè)定有效節(jié)點(diǎn)Step1：將目標(biāo)區(qū)域均勻劃分成個(gè)矩形格；Step2：依次取定每一矩形格的中心點(diǎn)

23、：，然后根據(jù)與節(jié)點(diǎn)之間的歐氏距離，判定每一中心點(diǎn)是否被覆蓋。Step3：以每一矩形格中心點(diǎn)的覆蓋特性代表整個(gè)矩形格的覆蓋特性，統(tǒng)計(jì)滿足覆蓋的所有矩形的數(shù)量，取有效覆蓋率，低于某一門(mén)限值，時(shí)，我們認(rèn)為網(wǎng)絡(luò)的壽命結(jié)束，這里我們4.2.8算法三：隨機(jī)拋灑節(jié)點(diǎn)初始化節(jié)點(diǎn)基于隨機(jī)簇頭選舉算法選取簇頭簇頭在一跳范圍內(nèi)廣播，PC=PC+1節(jié)點(diǎn)在第一次接到節(jié)點(diǎn)后根據(jù)路由信息與上級(jí)相連，并且記錄跳數(shù)判斷跳數(shù)是否為3否未接受到信息的節(jié)點(diǎn)直接與基站相連是一周期后是否有節(jié)點(diǎn)能量耗盡否是基于GAF算法的隨機(jī)簇頭選舉算法基于算法的節(jié)點(diǎn)狀態(tài)控制算法ASCENT覆蓋率？動(dòng)態(tài)路由算法控制節(jié)點(diǎn)連通工作是網(wǎng)絡(luò)壽命結(jié)束否循環(huán)基于覆蓋

24、定理的判定算法基于模型一的動(dòng)態(tài)路由控制算法產(chǎn)生能量空洞4.2.9基于MATLAB仿真如下：網(wǎng)絡(luò)壽命 能量利用率 網(wǎng)絡(luò)壽命 能量利用率 35234636135534235897.5%97.1%98.5%97.8%96.8%98.1% 顯然此結(jié)果較算法二有了更進(jìn)一步的優(yōu)化改進(jìn)，周期數(shù)大于最大簇的壽命值，并且能量利用率也提高到了97%左右。五、模型的改進(jìn) 模擬實(shí)驗(yàn)表明如果采用以上模型節(jié)點(diǎn)分簇策略，無(wú)線傳感器網(wǎng)絡(luò)能有效的避免“能量空洞”現(xiàn)象。以下本文還從理論上討論了如果采用非均勻分布策略，無(wú)線傳感網(wǎng)絡(luò)更能有效的避免能量空洞和目標(biāo)區(qū)域覆蓋問(wèn)題。 我們假設(shè)節(jié)點(diǎn)分布在一個(gè)半徑為的圓形區(qū)域中。網(wǎng)絡(luò)中唯一的Si

25、nk放置于圓心處，如圖1，所有節(jié)點(diǎn)都用一個(gè)ID號(hào)，通行半徑固定為一個(gè)單位。網(wǎng)絡(luò)被劃分為個(gè)相鄰的環(huán)狀區(qū)域，每個(gè)圓環(huán)的寬度為1個(gè)單位。表示第個(gè)圓環(huán)，乃以的目標(biāo)區(qū)域?yàn)槔?如圖：顯然，處于圓環(huán)中的節(jié)點(diǎn)需要向Sink轉(zhuǎn)發(fā)自身和處于圓環(huán)中節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)。由圖可知，圓環(huán)中的節(jié)點(diǎn)不需要為其他圓環(huán)中的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。每個(gè)節(jié)點(diǎn)的初始能量為，并且基站無(wú)能量限制。每次發(fā)送數(shù)據(jù)與接收數(shù)據(jù)消耗的單位能量分別是、，并且有。100m100m60m60m圖1 能耗分析 根據(jù)以上的分析，圓環(huán)中在單位時(shí)間內(nèi)所有節(jié)點(diǎn)消耗的能量為：表示圓環(huán)中傳感器節(jié)點(diǎn)的數(shù)目；表示圓環(huán)中所有節(jié)點(diǎn)在單位時(shí)間內(nèi)的能量消耗； 而其他圓環(huán)中的節(jié)點(diǎn)既要發(fā)送自身產(chǎn)

26、生的數(shù)據(jù)，又要轉(zhuǎn)發(fā)來(lái)自外部圓環(huán)的數(shù)據(jù)，則有：綜上所述，有：由通信原理可知網(wǎng)絡(luò)能耗同時(shí)為零時(shí)不可能的，即以下等式不成立，其原理我們?cè)谶@里就不具體討論。但是如果能夠?qū)崿F(xiàn)次優(yōu)化的能耗均衡也是非常有用的。我們定義次優(yōu)的能耗均衡是網(wǎng)絡(luò)中除了最外圓環(huán)中的節(jié)點(diǎn)外，其他圓環(huán)中的節(jié)點(diǎn)能夠?qū)崿F(xiàn)能耗均衡。 在這里本文提出了節(jié)點(diǎn)非均勻分布策略下的路由控制數(shù)學(xué)模型。 基于前面的分析，我們定量規(guī)劃網(wǎng)絡(luò)中每個(gè)圓環(huán)中節(jié)點(diǎn)的數(shù)目。假設(shè)圓環(huán)中節(jié)點(diǎn)的密度為，則從最外面的圓環(huán)到最里面的圓環(huán)，節(jié)點(diǎn)密度逐漸下降，有： 從圖1中我們可以看出顏色越深的代表節(jié)點(diǎn)密度遠(yuǎn)大。 當(dāng)圓環(huán)到圓環(huán)中的節(jié)點(diǎn)數(shù)以等比系數(shù)遞增，和中的節(jié)點(diǎn)數(shù)之比為時(shí)，即 并且根

27、據(jù)各圓環(huán)的面積，可以推算出相鄰圓環(huán)和之間的節(jié)點(diǎn)密度之比為： 其控制的基本思想是外層圓環(huán)將自身采集的數(shù)據(jù)逐層發(fā)送至基站（Sink）。外層節(jié)點(diǎn)選擇其相鄰內(nèi)院中的對(duì)應(yīng)節(jié)點(diǎn)作為待選中繼節(jié)點(diǎn)。節(jié)點(diǎn)每次發(fā)送數(shù)據(jù)時(shí)總是選擇待選中繼節(jié)點(diǎn)中剩余能量最多的一個(gè)。 最后基于以上的模型進(jìn)行了模擬實(shí)驗(yàn)，結(jié)果如圖：不同節(jié)點(diǎn)分布策略的網(wǎng)絡(luò)生存周期 六、模型的評(píng)價(jià)【優(yōu)點(diǎn)】 模型一中，由于采用了鄰接矩陣判定方法，所以節(jié)點(diǎn)的連通性能較好的解決，但是由于此模型只考慮了基站一跳范圍內(nèi)的節(jié)點(diǎn)壽命，所以很容易產(chǎn)生“能量空洞”現(xiàn)象，導(dǎo)致盡管其他節(jié)點(diǎn)乃有較多的剩余能量，但由于基站周?chē)墓?jié)點(diǎn)“死亡”而變成了失效節(jié)點(diǎn)。仿真結(jié)果顯示盡管有很大的提

28、高，但乃有些節(jié)點(diǎn)的剩余能量較大。模型二中，提出了基于分簇法與覆蓋定理的動(dòng)態(tài)路由模型，使用了簇與簇頭節(jié)點(diǎn)的耗能響亮來(lái)具體刻畫(huà)每個(gè)簇能量的消耗方式，建立了最大化簇壽命的整數(shù)線性規(guī)劃模型，在此模型中，分析了分簇機(jī)制與最大跳數(shù)，進(jìn)一步建立了改進(jìn)的就近分簇機(jī)制下簇中簇頭變換與簇的壽命的關(guān)系，并且根據(jù)GAF算法和ASCENT算法提出了隨機(jī)簇頭選舉算法和節(jié)點(diǎn)狀態(tài)控制算法。最后仿真結(jié)果顯示模型對(duì)于以上問(wèn)題有更好的優(yōu)化效果?！救秉c(diǎn)】 由于從數(shù)學(xué)理論上很難推算出節(jié)點(diǎn)的實(shí)際覆蓋面積，所以本文采用了以節(jié)點(diǎn)覆蓋代替區(qū)域覆蓋的近似處理，在節(jié)點(diǎn)數(shù)N不夠大時(shí)可能會(huì)產(chǎn)生誤差，本文假設(shè)了通行半徑大于2倍的覆蓋面積，而在實(shí)際運(yùn)用中

29、此式并不一定成立，并且根據(jù)不同的實(shí)際需要，有些區(qū)域的覆蓋次數(shù)并不止一次?！緟⒖嘉墨I(xiàn)】1孫波，高隨祥，無(wú)線傳感器網(wǎng)絡(luò)中最大化簇壽命的優(yōu)化模型，2006-12-272陳劍，常桂然，基于節(jié)點(diǎn)協(xié)同覆蓋的傳感器網(wǎng)絡(luò)壽命最大化模型，2008-08-243劉湘雯，胡悍英，無(wú)線傳感器網(wǎng)絡(luò)壽命的一種新定義方法，2005-4-294曲家慶，張曙，優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)壽命的動(dòng)態(tài)路由算法，2009-08-07七、附件此圖為100個(gè)0到100的隨機(jī)數(shù)的分布概率。假設(shè)節(jié)點(diǎn)是按上述概率分布的 通過(guò)計(jì)算可知每周期需發(fā)送450個(gè)數(shù)據(jù)包獲得 假設(shè)簇頭保持不變且在基站一跳范圍內(nèi)，可得到簇頭剩余能量與周期的關(guān)系圖算法一：functio

30、n mr=input('輸入r=');%輸入通信半徑h=unidrnd(100,1,100);%產(chǎn)生100個(gè)從0到100的隨機(jī)數(shù)for i=1:100; g(i)=(h(i),h(i) g(0)=(50,50);%基站的坐標(biāo)endplotmatrix(h(i),h(i);%將這一百個(gè)隨機(jī)數(shù)放在100*100的坐標(biāo)紙上k=0;for i=1:100; if boxdist(g(i),g(0)<=r %求取并記錄離基站一跳距離的節(jié)點(diǎn) c(k)=g(i); k=k+1; b(i)=0; %用數(shù)組b來(lái)存放每個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)個(gè)數(shù)并賦初值 cnt=0; endfor i=0;k-1;

31、 for j=1:100;%計(jì)算上述k個(gè)節(jié)點(diǎn)的一跳鄰節(jié)點(diǎn)集合的元素個(gè)數(shù) if boxdist(g(i),g(j)<=r %計(jì)算兩個(gè)節(jié)點(diǎn)之間的距離是否滿足傳輸條件 b(i)=b(i)+1; end endend A=|b(0),b(2),.,b(k-1)|; sort(A); %對(duì)上述k個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)個(gè)數(shù)進(jìn)行升序排列 E=input('輸入E=');%為節(jié)點(diǎn)初始能量 S=input('輸入S=');%S為周期信息采集數(shù)量 t=0; while(E/A(k)>0) %計(jì)算第一跳節(jié)點(diǎn)完全失效的時(shí)間（傳感器的最大生命周期） while(k>0) t=t

32、+E/A(k); E=E-A(k-1)*S*t;%計(jì)算地k-1個(gè)節(jié)點(diǎn)的剩余能量 k=k-1; end end（由于算法二包含在算法三內(nèi)，所以在此不做闡述）算法三： function nr=input('輸入r=');%輸入通信半徑h=unidrnd(100,1,100);%產(chǎn)生100個(gè)從0到100的隨機(jī)數(shù)for i=1:100; g(i)=(0,0);endfor i=1:100; g(i)=(h(i),h(i);%給節(jié)點(diǎn)編號(hào) g(0)=(50,50);%基站的坐標(biāo)endplotmatrix(h(i),h(i);%將這一百個(gè)隨機(jī)數(shù)放在100*100的坐標(biāo)紙上for i=1:100; PC(i)=0; E(i)=E0;%初始化節(jié)點(diǎn) =0;endb=0;c=0;d=0;while（E(1)>=0) % 能量消耗最大的節(jié)點(diǎn)能量還沒(méi)消耗完時(shí)執(zhí)行while循環(huán)語(yǔ)句 B=|E(1),E(2).E(100)|; %節(jié)點(diǎn)剩余能量構(gòu)成的1*100維向量 sort(B); %對(duì)B向量的元素進(jìn)行升序排列 for j=99:1; if (E(j)=E(100) else break; end end C=|PC(100),PC