無線傳感網(wǎng)絡(luò)設(shè)計(jì)問題

1、無線傳感網(wǎng)絡(luò)設(shè)計(jì)問題摘要本文針對(duì)無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)展開討論，主要研究在監(jiān)視區(qū)域內(nèi)放置節(jié)點(diǎn)個(gè)數(shù)與成功覆蓋概率的關(guān)系、節(jié)點(diǎn)的通信模型設(shè)計(jì)問題。對(duì)于問題1，首先考慮將節(jié)點(diǎn)分為兩大類，一類節(jié)點(diǎn)一定完全落在監(jiān)視區(qū)域內(nèi)，另一類節(jié)點(diǎn)只能部分落在監(jiān)視區(qū)域內(nèi)，通過這兩類節(jié)點(diǎn)的發(fā)生概率以及這兩類節(jié)點(diǎn)覆蓋面積的期望值，可以求得所有節(jié)點(diǎn)覆蓋面積的期望值。運(yùn)用概率論的知識(shí)綜合兩類節(jié)點(diǎn)的期望，求解出至少要放置88個(gè)節(jié)點(diǎn)，才能使成功覆蓋整個(gè)區(qū)域的概率在95%以上。同時(shí)通過隨機(jī)模擬仿真實(shí)驗(yàn)，我們得出了成功覆蓋概率與節(jié)點(diǎn)個(gè)數(shù)的關(guān)系圖，可以清晰的看出成功覆蓋概率隨著節(jié)點(diǎn)個(gè)數(shù)的變化趨勢(shì)。對(duì)于問題2，首先根據(jù)題目要求描點(diǎn)連線，將不可以

2、通行的路徑去掉，得到節(jié)點(diǎn)通信路徑圖，通過該圖我們可以找出任意兩個(gè)節(jié)點(diǎn)間的通信通路，例如節(jié)點(diǎn)31到節(jié)點(diǎn)74的通信通路為：31692174，但顯然其路徑不唯一，我們?cè)诠?jié)點(diǎn)通信路徑圖的基礎(chǔ)上進(jìn)行優(yōu)化，找出兩個(gè)節(jié)點(diǎn)之間的最短路徑，在解決這個(gè)問題上我們分為兩步優(yōu)化：第一步：運(yùn)用算法求出固定起點(diǎn)到任意點(diǎn)的最短路徑；第二步：運(yùn)用算法求出任意兩節(jié)點(diǎn)間的最短通信通路，例如節(jié)點(diǎn)1到節(jié)點(diǎn)90的最短通信通路為：18064254665669313387156090。對(duì)于問題3，從節(jié)能角度出發(fā)，在問題2通信模型的基礎(chǔ)上，進(jìn)一步考慮無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)間通信半徑與能量消耗的關(guān)系。本文認(rèn)為通信半徑越長，能量消耗越多。因此，問題3

3、的目標(biāo)變?yōu)榱耸瓜噜徆?jié)點(diǎn)間路徑最短，根據(jù)這個(gè)目標(biāo)我們可以引用最小生成樹的思想得到一個(gè)最小生成樹路徑圖，得到從節(jié)能角度考慮設(shè)計(jì)的任意兩節(jié)點(diǎn)間的通信路徑，例如節(jié)點(diǎn)76到節(jié)點(diǎn)19的通信通路為：766019。在問題3上的基礎(chǔ)上我們提出了相應(yīng)的改進(jìn)思想，根據(jù)最小生成樹路徑圖，我們發(fā)現(xiàn)有些節(jié)點(diǎn)處于其他若干個(gè)節(jié)點(diǎn)的通信路徑交匯處，如節(jié)點(diǎn)72、106、107，這類節(jié)點(diǎn)存在過載使用。為避免這種情況，最大最小通信使得節(jié)點(diǎn)的剩余電量盡可能多，即最大化節(jié)點(diǎn)的最小剩余電量。基于以上的思想我們認(rèn)為可以定義一個(gè)電源的開銷函數(shù)。這樣可以避免交叉節(jié)點(diǎn)的過載使用，延長整個(gè)遙測(cè)遙感網(wǎng)的通信壽命。關(guān)鍵詞：成功覆蓋率；通信模型；算法；算

4、法 ；最小生成樹一、 問題的重述自然災(zāi)害頻頻發(fā)生，給人民的生命財(cái)產(chǎn)造成巨大的損失，因此一些國家通過在容易出現(xiàn)自然災(zāi)害的重點(diǎn)地區(qū)放置高科技的監(jiān)視裝置，進(jìn)而建立無線傳感網(wǎng)絡(luò)的方式，幫助人們準(zhǔn)確而及時(shí)地掌握險(xiǎn)情的發(fā)展情況，為有效地?fù)屜染葹?zāi)創(chuàng)造有利條件，這對(duì)于減少人民的生命財(cái)產(chǎn)損失具有重大意義。放置在同一監(jiān)視區(qū)域內(nèi)的這種監(jiān)視裝置（以下簡稱為節(jié)點(diǎn)）可以構(gòu)成一個(gè)無線傳感網(wǎng)絡(luò)如附錄一圖1。如果監(jiān)視區(qū)域的任意一點(diǎn)都處于放置在該區(qū)域內(nèi)某一節(jié)點(diǎn)的監(jiān)視范圍內(nèi)，則稱節(jié)點(diǎn)能覆蓋該監(jiān)視區(qū)域，可見研究能確保有效覆蓋且數(shù)量最少的節(jié)點(diǎn)放置問題顯然具有重要意義。網(wǎng)絡(luò)節(jié)點(diǎn)間的通信設(shè)計(jì)問題也是無線傳感器網(wǎng)絡(luò)設(shè)計(jì)的重要問題之一，每個(gè)節(jié)

5、點(diǎn)都有一定的覆蓋范圍，節(jié)點(diǎn)可以與覆蓋范圍內(nèi)的節(jié)點(diǎn)進(jìn)行通信。但是當(dāng)節(jié)點(diǎn)需要與不在其覆蓋范圍內(nèi)的節(jié)點(diǎn)通信時(shí)，需要其它節(jié)點(diǎn)轉(zhuǎn)發(fā)才可以進(jìn)行通信如附錄一圖2。通過查找相關(guān)資料，建立數(shù)學(xué)模型解決以下問題：問題一：在一個(gè)監(jiān)視區(qū)域?yàn)檫呴Lb=100(長度單位)的正方形中，每個(gè)節(jié)點(diǎn)的覆蓋半徑均為r=10(長度單位)。確定至少需要放置多少個(gè)節(jié)點(diǎn)，才能使得成功覆蓋整個(gè)區(qū)域的概率在95%以上。問題二：在問題一所給的條件下，已知在該監(jiān)視區(qū)域內(nèi)放置了120個(gè)節(jié)點(diǎn)，它們位置的橫、縱坐標(biāo)如附錄二表1中120個(gè)點(diǎn)的坐標(biāo)表所示。試設(shè)計(jì)一種節(jié)點(diǎn)間的通信模型，給出任意10組兩節(jié)點(diǎn)之間的通信通路，比如節(jié)點(diǎn)1與節(jié)點(diǎn)90如何通信等。問題三：

6、對(duì)用于監(jiān)視旱情的遙測(cè)遙感網(wǎng)，由于地處邊遠(yuǎn)地區(qū)，每個(gè)節(jié)點(diǎn)都只能以電池為能源，電池用盡節(jié)點(diǎn)即報(bào)廢。實(shí)際情況下，節(jié)點(diǎn)的覆蓋范圍也會(huì)隨著節(jié)點(diǎn)能量發(fā)生變化。針對(duì)附錄二中表1的數(shù)據(jù)，從節(jié)能角度考慮設(shè)計(jì)，改進(jìn)問題2中的通信模型。給出任意10組兩節(jié)點(diǎn)之間的通信通路，比如節(jié)點(diǎn)1與節(jié)點(diǎn)90如何通信等。二、 問題的分析建立無線傳感網(wǎng)絡(luò)，使人們能準(zhǔn)確而及時(shí)地掌握險(xiǎn)情的發(fā)展情況，但到底要設(shè)置多少個(gè)節(jié)點(diǎn)使得成功覆蓋概率較高的問題值得我們關(guān)注，同時(shí)設(shè)計(jì)一個(gè)合理有效的節(jié)點(diǎn)通信模型也是整個(gè)無線傳感網(wǎng)絡(luò)中的重中之重。對(duì)于問題（1），基于給定的監(jiān)視區(qū)域以及覆蓋半徑，要求放置最少的節(jié)點(diǎn)使得成功覆蓋整個(gè)區(qū)域的概率在95%以上。由于給定

7、監(jiān)視區(qū)域存在邊界，故可以將節(jié)點(diǎn)分為兩大類，一類節(jié)點(diǎn)一定完全落在監(jiān)視區(qū)域內(nèi)，另一類節(jié)點(diǎn)只能部分落在監(jiān)視區(qū)域內(nèi)，這兩類節(jié)點(diǎn)發(fā)生的概率可以由相應(yīng)區(qū)域面積與總監(jiān)視區(qū)域面積之比得出，同時(shí)，可以得到兩類節(jié)點(diǎn)覆蓋面積的期望值，進(jìn)而可以求得隨機(jī)在給定監(jiān)視區(qū)域內(nèi)放置節(jié)點(diǎn)，節(jié)點(diǎn)覆蓋面積的期望值?？梢赃\(yùn)用概率論的知識(shí)綜合兩類節(jié)點(diǎn)的期望求解覆蓋整個(gè)監(jiān)視區(qū)域的概率，令該概率值大于95%即可求解。當(dāng)然，還可以通過設(shè)計(jì)隨機(jī)仿真實(shí)驗(yàn)的方法進(jìn)行進(jìn)一步的分析求解最少的節(jié)點(diǎn)數(shù)目。對(duì)于問題（2），由于每個(gè)節(jié)點(diǎn)都有一定的覆蓋范圍，節(jié)點(diǎn)只可以與其覆蓋范圍內(nèi)的節(jié)點(diǎn)進(jìn)行通信，根據(jù)120個(gè)節(jié)點(diǎn)的坐標(biāo)，即可得到兩兩節(jié)點(diǎn)之間的距離，于是滿足節(jié)點(diǎn)通

8、信條件的所有節(jié)點(diǎn)都可以找到。通過這樣的方法，任意兩節(jié)點(diǎn)之間的通信通路即可得出。由前面的方法可以找到兩節(jié)點(diǎn)的通信路徑，但是路徑不唯一，所以通過算法可以求出固定起點(diǎn)（本文我們固定節(jié)點(diǎn)1為起點(diǎn)）到其余任意節(jié)點(diǎn)的最短通信路徑。借鑒上述求特解的思路，我們又可運(yùn)用算法求出任意兩節(jié)點(diǎn)之間的最短通信路徑，因此本文可以嘗試用上述兩種算法對(duì)模型進(jìn)行進(jìn)一步優(yōu)化從而快速得到任意兩節(jié)點(diǎn)之間的最短通信通路。對(duì)于問題（3），我們需從節(jié)能角度出發(fā)，在問題（2）所得節(jié)點(diǎn)間最短通信路徑模型的基礎(chǔ)上，進(jìn)一步考慮無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)間通信半徑與能量消耗的關(guān)系，即通信半徑越長，能量消耗越多。因此，這里我們可以引用最小生成樹的思想得到一個(gè)最

9、短路徑圖，得到從節(jié)能角度考慮設(shè)計(jì)的任意兩點(diǎn)間的通信路徑。 三、 模型的假設(shè)與符號(hào)的說明3.1模型的假設(shè)（1）監(jiān)視裝置工作穩(wěn)定，不會(huì)突然失效；（2）每個(gè)監(jiān)視裝置單位感知距離內(nèi)耗能相同；3.2符號(hào)的說明：節(jié)點(diǎn)的覆蓋半徑；：正方形監(jiān)視區(qū)域的邊長；：節(jié)點(diǎn)覆蓋面積的期望值；：監(jiān)測(cè)區(qū)域的面積；：放置的節(jié)點(diǎn)數(shù)目；：無線傳感網(wǎng)絡(luò)覆蓋率；：節(jié)點(diǎn)位置的坐標(biāo)，；：節(jié)點(diǎn)位置的坐標(biāo)，；：節(jié)點(diǎn)到節(jié)點(diǎn)的距離，；：無線傳感網(wǎng)絡(luò)的某一節(jié)點(diǎn)；：節(jié)點(diǎn)間的通信半徑：無線傳感網(wǎng)絡(luò)中某一節(jié)點(diǎn)的能量消耗；：無線傳感網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量消耗總和。四、 模型的建立與求解4.1問題（1）的模型建立與求解4.1.1模型一：無線傳感網(wǎng)絡(luò)概率覆蓋模型

10、首先考慮在監(jiān)測(cè)區(qū)域內(nèi)部部署一些節(jié)點(diǎn)，這些節(jié)點(diǎn)構(gòu)造成一個(gè)節(jié)點(diǎn)集合S，每個(gè)節(jié)點(diǎn)的覆蓋面積為為，覆蓋概率為；當(dāng)節(jié)點(diǎn)集合為空時(shí)，放置個(gè)節(jié)點(diǎn)便得到網(wǎng)絡(luò)的覆蓋率：，這樣就得到了S不為空集的情況下，網(wǎng)絡(luò)節(jié)點(diǎn)的覆蓋概率值： （1）式（1）和觀察到的是一致的，它表明了當(dāng)節(jié)點(diǎn)數(shù)目足夠大時(shí)，該區(qū)域是被完全覆蓋的。本文按照?qǐng)D1的方式將網(wǎng)絡(luò)區(qū)域劃分成區(qū)域1和區(qū)域2，節(jié)點(diǎn)放置好之后，或位于區(qū)域1內(nèi)，或位于區(qū)域內(nèi)2。圖1：節(jié)點(diǎn)位于區(qū)域內(nèi)的示意圖由此得到網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋的期望值為： （2）其中，和分別表示節(jié)點(diǎn)被隨機(jī)放置在區(qū)域1和區(qū)域2里的概率。和分別表示其相應(yīng)的覆蓋期望值。由于傳感器節(jié)點(diǎn)的放置服從均勻分布函數(shù)，得到： （3）當(dāng)節(jié)

11、點(diǎn)位于區(qū)域1時(shí)，它的覆蓋范圍被完全包含。覆蓋期望值為。根據(jù)圖1，當(dāng)節(jié)點(diǎn)位于區(qū)域2時(shí)，的面積應(yīng)等于其覆蓋圓周的面積減去弓形區(qū)域的面積。和是節(jié)點(diǎn)的覆蓋圓周和網(wǎng)絡(luò)邊界的交叉點(diǎn)。設(shè)。其面積為： （4）于是，由式（5）得到的期望值： （5）假設(shè)覆蓋半徑為的節(jié)點(diǎn)均勻分布在邊長為的正方形區(qū)域，在考慮邊界因素的情況下，由式（2）式（5）推導(dǎo)得到節(jié)點(diǎn)的覆蓋期望值為： （6）在給定邊長為的正方形區(qū)域，節(jié)點(diǎn)覆蓋半徑是和較小的參數(shù)，要確保網(wǎng)絡(luò)覆蓋率的期望值不小于，根據(jù)式（1），應(yīng)滿足：，這樣得到，由于，可以得到： （7）本題目中，故由（6）（7）式可以得到：，故基于本文給出的監(jiān)視區(qū)域及覆蓋半徑，通過無線傳感網(wǎng)絡(luò)覆蓋模

12、型得出，至少需要88個(gè)節(jié)點(diǎn)才能使得成功覆蓋整個(gè)區(qū)域的概率在95%以上。4.1.2無線傳感網(wǎng)絡(luò)概率覆蓋模型仿真實(shí)驗(yàn)本文設(shè)計(jì)隨機(jī)仿真實(shí)驗(yàn)，經(jīng)過多次重復(fù)實(shí)驗(yàn)，得到無線傳感器網(wǎng)絡(luò)成功覆蓋整個(gè)區(qū)域的概率和節(jié)點(diǎn)數(shù)目的關(guān)系如圖2所示：圖2：成功覆蓋的概率與節(jié)點(diǎn)數(shù)的關(guān)系通過隨機(jī)仿真實(shí)驗(yàn)的方法，結(jié)合圖2所示，本文得出當(dāng)節(jié)點(diǎn)數(shù)目為88時(shí)，成功覆蓋整個(gè)區(qū)域的概率為95.18%。 4.2模型二：無線傳感網(wǎng)絡(luò)通信模型4.2.1節(jié)點(diǎn)通路圖由于每個(gè)節(jié)點(diǎn)都有一定的覆蓋范圍，節(jié)點(diǎn)可以與覆蓋范圍之內(nèi)的節(jié)點(diǎn)進(jìn)行通信。任意兩個(gè)節(jié)點(diǎn)之間的距離為： （8）即對(duì)于的兩個(gè)節(jié)點(diǎn)之間不可以進(jìn)行通信，只有的兩個(gè)節(jié)點(diǎn)之間才可以進(jìn)行通信。因此，本文將

13、所有的兩節(jié)點(diǎn)之間用直線連接，得到節(jié)點(diǎn)通路圖如圖3所示：圖3：節(jié)點(diǎn)通路圖通過圖3的節(jié)點(diǎn)通路圖，可以得到無線傳感網(wǎng)絡(luò)中任意10組兩節(jié)點(diǎn)之間的通信通路，如下表1所示：表 1：節(jié)點(diǎn)1到各節(jié)點(diǎn)的最短通信距離及最短通信通路起始節(jié)點(diǎn)終止節(jié)點(diǎn)通信路徑111180507651112711157650271107111510714111151077041162180507656218611156210626894561848615918064254665669293135911318064254665669293131691806425466566931359851101901806425466566931338

14、73415但是，本文也發(fā)現(xiàn)，該模型下每兩個(gè)節(jié)點(diǎn)之間的通信通路并不唯一，結(jié)合實(shí)際情況，本文認(rèn)為有必要在模型一的基礎(chǔ)上作進(jìn)一步的優(yōu)化，直接獲得兩節(jié)點(diǎn)之間的最短通信通路，為有效地?fù)屜染葹?zāi)創(chuàng)造有利條件。4.2.2固定起點(diǎn)的最短通信路徑求解本文暫且將問題轉(zhuǎn)化為研究節(jié)點(diǎn)1到其他各節(jié)點(diǎn)的最短通信通路問題。為了得到節(jié)點(diǎn)1到其他各節(jié)點(diǎn)的最短通信通路，采用算法進(jìn)行求解。算法步驟：目標(biāo)為求解到之間的最短路徑集合，首先定義三個(gè)集合：路徑集合、記錄距離集合以及節(jié)點(diǎn)間真實(shí)距離集合。1）初始化，置，；2）對(duì)于每一個(gè)，用代替，計(jì)算并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置；3）若，則停止；若，則用代替并轉(zhuǎn)2）。通過上述算法便可以求

15、得和之間的最短路徑集合，進(jìn)而也可以求得最短路徑的長度。這樣便可以求得節(jié)點(diǎn)1到其他各節(jié)點(diǎn)的最短通信距離以及最短通信通路如表2所示：表 2：節(jié)點(diǎn)1到各節(jié)點(diǎn)的最短通信距離以及最短通信通路當(dāng)前節(jié)點(diǎn)12345678910距節(jié)點(diǎn)1距離076.969.533.310.478.536.1上一節(jié)點(diǎn)110313106113105912425當(dāng)前節(jié)點(diǎn)11121314151617181920距節(jié)點(diǎn)1距離5.423.661.344.288.646.760.749.565.272.2上一節(jié)點(diǎn)17693248797721029399當(dāng)前節(jié)點(diǎn)21222324252627282930距節(jié)點(diǎn)1距離88.5

16、39.665.934.328.131.415.148.059.230.9上一節(jié)點(diǎn)110437336410680947106當(dāng)前節(jié)點(diǎn)31323334353637383940距節(jié)點(diǎn)1距離97.365.928.785.229.058.321.8上一節(jié)點(diǎn)693764874018109724755當(dāng)前節(jié)點(diǎn)41424344454647484950距節(jié)點(diǎn)1距離27.420.172.735.446.735.254.766.744.016.3上一節(jié)點(diǎn)7027335892545178880當(dāng)前節(jié)點(diǎn)51525354555657585960距節(jié)點(diǎn)1距離63.886.372.341.817.37

17、8.271.246.471.395.7上一節(jié)點(diǎn)9811032480531041021315當(dāng)前節(jié)點(diǎn)61626364656667686970距節(jié)點(diǎn)1距離51.716.817.318.740.249.257.073.491.320.4上一節(jié)點(diǎn)455808046657510052107當(dāng)前節(jié)點(diǎn)71727374757677787980距節(jié)點(diǎn)1距離72.655.666.285.148.019.658.250.552.39.2上一節(jié)點(diǎn)73189311085799161當(dāng)前節(jié)點(diǎn)81828384858687888990距節(jié)點(diǎn)1距離44.224.662.155.378.557.379.437.637.2101.

18、0上一節(jié)點(diǎn)8955374559613302660當(dāng)前節(jié)點(diǎn)919293949596979899100距節(jié)點(diǎn)1距離34.155.258.160.833.761.938.158.868.068.3上一節(jié)點(diǎn)356666794137351119839當(dāng)前節(jié)點(diǎn)101102103104105106107108109110距節(jié)點(diǎn)1距離45.840.070.564.546.023.812.474.750.279.3上一節(jié)點(diǎn)899510436226211991459當(dāng)前節(jié)點(diǎn)111112113114115116117118119120距節(jié)點(diǎn)1距離51.874.245.359.558.021.4102.957.825

19、.561.7上一節(jié)點(diǎn)54736578181076078507通過觀察表2中數(shù)據(jù)，可以得到節(jié)點(diǎn)1到其他各節(jié)點(diǎn)的最短通路距離及最短通信通路。本文取任意取從節(jié)點(diǎn)1出發(fā)的10組節(jié)點(diǎn)如表3所示。表 3：節(jié)點(diǎn)1到各節(jié)點(diǎn)的最短通信距離及最短通信通路起始節(jié)點(diǎn)終止節(jié)點(diǎn)最短距離最短通信通路1115.411012715.118027110712.411110714127.4111107704116216.811156218657.3111562106268945618615971.3180642546656693135911588.6180642546656693133871516991.3180642546656

20、69313591105269190101.018064254665669313387156090可見，此次模型的改進(jìn)能夠任意得到節(jié)點(diǎn)1到各節(jié)點(diǎn)的最短通信通路和最短通信距離，但是仍舊不能給出任意兩節(jié)點(diǎn)之間的通信通路，仍需要作進(jìn)一步的模型優(yōu)化。4.2.3基于固定起點(diǎn)的最短通信路徑模型的一般化為了能夠快速給出任意兩個(gè)節(jié)點(diǎn)之間的最短通信通路，本文采用算法進(jìn)行模型的二步優(yōu)化，下面簡單介紹算法的實(shí)現(xiàn)過程。算法：1）從任意一條單邊路徑開始，所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則其邊的權(quán)重為無窮大。2）對(duì)于每一對(duì)頂點(diǎn)和，看看是否存在一個(gè)頂點(diǎn)使得從到再到比己知的路徑更短，如果是更新它。只需設(shè)置相

21、應(yīng)的起始節(jié)點(diǎn)和終止節(jié)點(diǎn)，借助算法即可快速求得該兩節(jié)點(diǎn)之間的最短通信通路，如圖4所示，即當(dāng)設(shè)置起節(jié)點(diǎn)為1，終止節(jié)點(diǎn)為90時(shí)，所得兩節(jié)點(diǎn)間的最短通信路徑。圖 4：節(jié)點(diǎn)1與節(jié)點(diǎn)90之間的最短最短通信通路按照同樣的方法，本文另外任意取得表3中的10組節(jié)點(diǎn)組合，得到如下結(jié)果。表 4：任意10組兩節(jié)點(diǎn)之間的最短距離及最短路徑起始節(jié)點(diǎn)終止節(jié)點(diǎn)最短距離最短路徑190101.0180642546656693133871560901410187.714102564275012301062689101383593.238721810295417010711180554035451786.24589261066210

22、770419510218721752596.7521105913936665462564801115637472.463642546656693135911074768231.57650805582829346.98240332546656693911883.69135405580111107704195102181036489.110310436181029541701071118064 通過上述結(jié)果可以看出，通過對(duì)模型二的兩步優(yōu)化，當(dāng)模型采集到任意兩節(jié)點(diǎn)的信息時(shí)，能夠快速準(zhǔn)確地給出任意兩節(jié)點(diǎn)之間的最短通信路徑以及此時(shí)的最短通信距離，可見本文所建模型效果非常顯著。4.3模型三：節(jié)能通信模型

23、一般情況下，無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗是通信半徑的函數(shù)，函數(shù)形式由節(jié)點(diǎn)的特性決定，文獻(xiàn)認(rèn)為節(jié)點(diǎn)的能量消耗模型是節(jié)點(diǎn)通信半徑的次方函數(shù)，那么節(jié)點(diǎn)的能量消耗可以表示為： （9）其中。節(jié)點(diǎn)的通信半徑越大，節(jié)點(diǎn)的能量消耗也越多。因此，從節(jié)能角度考慮，在保證能夠滿足節(jié)點(diǎn)間通信條件的基礎(chǔ)上，節(jié)點(diǎn)的通信半徑越小，節(jié)點(diǎn)的能量消耗也越少。因此，本文可以引用最小生成樹的貪心策略解決該問題。貪心策略：最近頂點(diǎn)策略，任選一個(gè)頂點(diǎn)，并以此建立起生成樹，每一步的貪心選擇是簡單地把不在生成樹中的最近頂點(diǎn)添加到生成樹種。根據(jù)該貪心策略本文采用了算法，即使生成樹以一種自然的方式生長，即從任意頂點(diǎn)開始，每一步為這棵樹添加以個(gè)分枝

24、，直到生成樹中包含全部頂點(diǎn)，同過該算法我們的到如下圖5最小生成樹路徑圖。圖5:最小生成樹路徑圖根據(jù)最小生成樹路徑圖，我們可以得到在節(jié)約能源的情況下任意兩個(gè)節(jié)點(diǎn)間的通信通路，如下表5所示：表5：任意10組兩節(jié)點(diǎn)之間通信通路起始節(jié)點(diǎn)終止節(jié)點(diǎn)通信通路1701116107703111231692162110855919139373112121912278060191009910068108209948174888171078102491478238223839682761976601911621170107662796779167567五、 模型的檢驗(yàn)5.1模型三節(jié)能通信模型的檢驗(yàn)式（8）給出了一個(gè)節(jié)

25、點(diǎn)的能量消耗過程，整個(gè)無線傳感器網(wǎng)絡(luò)的能量消耗為所有網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗之而后，可以表示為如下函數(shù)形式： （10）這里，本文通過研究節(jié)點(diǎn)29與節(jié)點(diǎn)45之間的通信路徑對(duì)模型進(jìn)行進(jìn)一步檢驗(yàn)，文獻(xiàn)中認(rèn)為可取2、4。本文暫取，可以得到基于最小生成樹算法所得通信通路能量消耗與其他算法所得通信通路能量消耗的對(duì)比，如下表6所示：表6:節(jié)點(diǎn)29與節(jié)點(diǎn)45之間的通信通路及能量消耗通信通路能量消耗最小生成樹算法所得通信通路294739868461451631.0其他算法所得通信通路2947454225.4通過表6中的數(shù)據(jù)對(duì)比可以看出，基于最小生成樹算法所得到通信通路能量消耗約占其他算法所得通信通路能量消耗的38.6

26、%，故可以認(rèn)為模型三的效果相當(dāng)顯著。六、 模型的評(píng)價(jià)與改進(jìn)7.1模型的評(píng)價(jià)7.1.1模型的優(yōu)點(diǎn)：（1）模型一：采用一個(gè)WSN概率覆蓋模型，相比現(xiàn)有一些復(fù)雜度較高的網(wǎng)絡(luò)覆蓋率判定方法，該模型能夠快速計(jì)算出不同網(wǎng)絡(luò)覆蓋率下所需部署的節(jié)點(diǎn)數(shù)量；（2）模型二：容易理解，可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離，代碼編寫簡單；（3）模型三：樹型結(jié)構(gòu)是分級(jí)的集中控制式網(wǎng)絡(luò)，成本較低，節(jié)點(diǎn)易于擴(kuò)充，尋找路徑比較方便，但除了葉節(jié)點(diǎn)及其相連的線路外，任一節(jié)點(diǎn)或其相連的線路故障都會(huì)使系統(tǒng)受到影響，易于擴(kuò)展；易于隔離故障。7.1.2模型的缺點(diǎn)：（1）本文是基于離線數(shù)據(jù)的建模，無法得到實(shí)際驗(yàn)證；（2）采用程序操作得出的結(jié)果

27、具有隨機(jī)性；（3）時(shí)間復(fù)雜度比較高，不適合計(jì)算大量數(shù)據(jù)。7.2模型的改進(jìn)方向在問題三上我們主要從單條線路的節(jié)能角度來考慮，對(duì)于整體沒有做出分析，這樣會(huì)導(dǎo)致72、106、107等這類的交叉點(diǎn)過載使用，為避免這種情況，最大最小通信使得節(jié)點(diǎn)的剩余電量盡可能多，即最大化節(jié)點(diǎn)的最小剩余電量。最大最小通信更多的考慮了電池的剩余電量，而最少能量通信考慮的是某次通信需要消耗的電量，基于以上的思想我們將上述兩種可能綜合考慮，定義一個(gè)電源的開銷函數(shù)。這樣可以避免交叉點(diǎn)過載使用，延長整個(gè)遙測(cè)遙感網(wǎng)的通信壽命。 七、 模型的應(yīng)用與推廣本文建立的通信模型主要考慮了通信傳輸距離和節(jié)約能源兩個(gè)方面，本文的通信模型還可以解決

28、許多實(shí)際生活中的問題：（1）城市之間光纜鋪設(shè)問題；（2）地區(qū)之間消防站的設(shè)置問題；（3）省市之間基站的設(shè)置問題。參考文獻(xiàn)1李超良，邢蕭飛，劉躍華。無線傳感器網(wǎng)絡(luò)概率覆蓋模型研究，計(jì)算機(jī)工程，38卷第3期：80-84，2012。.2鄧克波，劉中?；诟兄嚯x調(diào)節(jié)的無線傳感器網(wǎng)絡(luò)節(jié)能區(qū)域覆蓋，電子與信息學(xué)報(bào)，31卷第10期：2305-2309，2009。3So A and Ye Y. On solving coverage problems in a wireless sensor network using voronoidiagramsC.Proc.of Workshop on Interne

29、t and Network Economics,Hong Kong,December 2005:584-593.附錄附錄一： 圖1 無線傳感網(wǎng)絡(luò)覆蓋示意圖圖2 無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)通信示意圖附錄二： 表1 120個(gè)節(jié)點(diǎn)的坐標(biāo)表節(jié)點(diǎn)標(biāo)號(hào)XY節(jié)點(diǎn)標(biāo)號(hào)XY節(jié)點(diǎn)標(biāo)號(hào)XY節(jié)點(diǎn)標(biāo)號(hào)XY157583163361329591744429574328596247719241253341233643763504393392143168342213645643949551552673569436556259572766304368083664725967987157537761367806497784487552388

30、894681096981080975303925956912339988910652840624570637010015951155634170707139910145901241614245427281891027082133620433597343141039078147224447541741725104847815161045359175805510520701685494656307645611064071178690472792779240107557018759048929078782210859519322049255879894510973182059250445280515

31、1110222821163551580814090111178022256652173382654911250102372453905837671135520246833542574843098114872225613555584785263411572982637785695286289911655792748465787728725811772288131586888882963118852029239059302889408311935503035666099904111201068附錄三：無線傳感網(wǎng)絡(luò)概率覆蓋模型的隨機(jī)仿真實(shí)驗(yàn)matlab程序clcclearL=100; % 正方形區(qū)域

32、邊長R=10; % 圓半徑M=zeros(L); % 覆蓋狀態(tài)N=0; % 統(tǒng)計(jì)圓的數(shù)目ss=1; % 循環(huán)控制變量m,n=meshgrid(1:L);axis(0,L,0,L);axis square;hold on;Ar=linspace(0,pi*2,200); % 圓周角度scale=0; % 覆蓋面積比例Tt=title('scale=0, ','N=0');A1=gca;Ax=axes('Position',0.9,0.11,0.04,0.8,'TickDir','out');Fi=fill(0,1,1

33、,0,0,0,0.003,0.003,'r'); % 繪制覆蓋比例的變化axis(0,1,0,1);t=0;p=0;while p<=0.95&&scale=1 for j=1:100 x=L*rand; % 隨機(jī)位置坐標(biāo) y=L*rand; % 隨機(jī)位置坐標(biāo) C=rand(1,3); % 隨機(jī)顏色 axes(A1); plot(x,y,'+','color',C); % 畫圓心 plot(x+i*y+R*exp(i*Ar),'color',C); % 畫圓 D=sqrt(m-x.2+n-y.2); % 計(jì)算

34、坐標(biāo)點(diǎn)到圓心的距離 m0,n0=find(D<=R); % 檢測(cè)出圓覆蓋點(diǎn)的坐標(biāo) Ind=sub2ind(L,L,m0,n0); % 坐標(biāo)與索引轉(zhuǎn)化 M(Ind)=1; % 改變覆蓋狀態(tài) N=N+1; % 增加圓數(shù)目 scale=sum(M(1:end)/L/L; % 計(jì)算覆蓋比例 set(Tt,'string','scale=',num2str(scale*100),'%, N=',num2str(N); set(Fi,'YData',0,0,scale,scale); SC(N)=scale; if scale=1; %

35、 檢測(cè)是否滿足覆蓋比例 t=t+1; scale % 輸出覆蓋比例 N % 輸出圓數(shù)目 end end p=t/j; end figure;plot(1:N,p);plot(1:N,SC);xlabel('itN');ylabel('p');附錄四：節(jié)點(diǎn)通路圖以及基于算法求解節(jié)點(diǎn)1到各節(jié)點(diǎn)之間的最短通信通路以及最短通信距離matlab程序%路徑圖：clearx=load('shuju1.txt');y=load('shuju2.txt');plot(x,y,'.')hold onfor i=1:120 for j=

36、1:120 dist(i,j)=(x(i)-x(j)2+(y(i)-y(j)2)0.5; if dist(i,j)<10; X=x(i) x(j); Y=y(i) y(j); plot(X,Y); hold on end endendtitle('節(jié)點(diǎn)通路圖')xlabel('節(jié)點(diǎn)X坐標(biāo)')ylabel('節(jié)點(diǎn)Y坐標(biāo)')%Dijkstra算法：x=load('shuju1.txt');y=load('shuju2.txt');plot(x,y,'.')text(x,y,num2cell(1:1

37、20) hold onfor i=1:120 for j=1:120 dist(i,j)=(x(i)-x(j)2+(y(i)-y(j)2)0.5; if dist(i,j)>10 dist(i,j)=Inf; end endendw=dist;n=size(w,1); w1=w(1,:); %賦初值 for i=1:n l(i)=w1(i); z(i)=1; end s=; s(1)=1; u=s(1); k=1 l zwhile k<n % 更新 l(v) 和 z(v) for i=1:n for j=1:k if i=s(j) if l(i)>l(u)+w(u,i) l(

38、i)=l(u)+w(u,i); z(i)=u; end end end end l z %求v* ll=l; for i=1:n for j=1:k if i=s(j) ll(i)=ll(i); else ll(i)=inf; end end end lv=inf; for i=1:n if ll(i)<lv lv=ll(i); v=i; end end lv v s(k+1)=v k=k+1 u=s(k) endlz附錄五：基于算法的模型二步優(yōu)化matlab程序clear clcx=load('shuju1.txt');y=load('shuju2.txt

39、9;);plot(x,y,'.')text(x,y,num2cell(1:120) hold onfor i=1:120 for j=1:120 dist(i,j)=(x(i)-x(j)2+(y(i)-y(j)2)0.5; if dist(i,j)<10; X=x(i) x(j); Y=y(i) y(j); plot(X,Y,':'); hold on end if dist(i,j)>10 dist(i,j)=inf; end endenddistD=dist;DD,path,min1,path1=floyd(D,1,90)l=length(pat

40、h1)w=;ww=;for i=1:l-1 w(i)=x(path1(i+1); ww(i)=y(path1(i+1);endwwwplot(w,ww,'-or','LineWidth',2)title('任意兩節(jié)點(diǎn)之間最短通信路徑')xlabel('節(jié)點(diǎn)X坐標(biāo)')ylabel('節(jié)點(diǎn)Y坐標(biāo)')算法的function文件：%解決最短路徑問題，是用來調(diào)用的函數(shù)頭文件%D,path=floyd(a)%輸入?yún)?shù)a是求圖的帶權(quán)鄰接矩陣，D(i,j)表示i到j(luò)的最短距離,path(i,j)i,j之間最短路徑上頂點(diǎn)i的后繼點(diǎn)%D,path,min1,path1=floyd(a,i,j)%輸入?yún)?shù)a是所求圖的帶權(quán)鄰接矩陣，i,j起點(diǎn)終點(diǎn),min1表示i與j最短距離，path1為最短路徑function D,path,mi