精品資料（2021-2022年收藏的）無線傳感網(wǎng)絡(luò)設(shè)計問題DOC

1、第二次個人賽論文 姓名代碼：88無線傳感網(wǎng)絡(luò)設(shè)計問題摘要本文針對無線傳感網(wǎng)絡(luò)節(jié)點的放置和節(jié)點間相互通信的路徑選擇問題做了深入的研究。對于問題（1），本文根據(jù)概率論知識（當(dāng)試驗次數(shù)足夠大時，可以近似認(rèn)為事件發(fā)生的頻率等于其概率）采用計算機仿真法，在監(jiān)視區(qū)域內(nèi)隨機安放n個節(jié)點，組建無線傳感網(wǎng)絡(luò)，然后在監(jiān)視區(qū)域隨機取20000個點，通過檢驗這些點是否全部被所組建的無線傳感網(wǎng)絡(luò)覆蓋來判斷所組建的無線傳感網(wǎng)絡(luò)能否成功覆蓋整個區(qū)域。進(jìn)行多次仿真，統(tǒng)計并計算出由這n個節(jié)點組成的無線傳感網(wǎng)絡(luò)成功覆蓋整個區(qū)域的頻率，將此頻率與95%比較，然后根據(jù)不同情況適當(dāng)調(diào)整n的大小，最后找出能成功覆蓋整個區(qū)域的概率在95%

2、以上的最少節(jié)點數(shù)n為565個。 對于問題（2），本文建立圖論模型，在滿足題設(shè)節(jié)點間通信條件的前提下，考慮通信的及時性的時效性，以通信所用時間最短為選取最優(yōu)通路的原則，先建立所給的120個節(jié)點間的距離矩陣，然后將距離矩陣中大于10的元素變?yōu)闊o窮大，從而將距離矩陣轉(zhuǎn)化為帶權(quán)鄰接矩陣，最后用matlab軟件求解，通過調(diào)用Dijkstraf算法，求解出10組節(jié)點間的通信通路，比如節(jié)點1與節(jié)點90間的通信通路為 1 80 64 25 46 65 66 93 13 3 87 15 60 90（詳見表1）。最后，本文對問題（1）和問題（2）中的模型進(jìn)行了評價，并對第一問中的仿真模型求解時只檢驗無線傳感網(wǎng)絡(luò)對

3、整個監(jiān)視區(qū)域是否完全覆蓋，而沒有考慮隨機安放的節(jié)點間能否相互通信的問題進(jìn)行了進(jìn)一步討論，并提出以節(jié)點間距離的最小值為判斷依據(jù)，在原覆蓋的基礎(chǔ)上剔除一些與其他節(jié)點間最小距離大于10的節(jié)點的修正方案。并對模型進(jìn)行了簡單的推廣。關(guān)鍵詞： 計算機仿真；圖論模型；概率論；Dijkstraf算法一、 問題的提出和重述1.1問題的提出大氣污染所引起的地球氣候異常，導(dǎo)致地震、旱災(zāi)等自然災(zāi)害頻頻發(fā)生，給人民的生命財產(chǎn)造成巨大損失。因此，不少國家政府都在研究如何有效監(jiān)測自然災(zāi)害的措施。在容易出現(xiàn)自然災(zāi)害的重點地區(qū)放置高科技的監(jiān)視裝置，建立無線傳感網(wǎng)絡(luò)，使人們能準(zhǔn)確而及時地掌握險情的發(fā)展情況，為有效地?fù)屜染葹?zāi)創(chuàng)造有

4、利條件。科技的迅速發(fā)展使人們可以制造不太昂貴且具有通訊功能的監(jiān)視裝置。放置在同一監(jiān)視區(qū)域內(nèi)的這種監(jiān)視裝置（以下簡稱為節(jié)點）構(gòu)成一個無線傳感網(wǎng)絡(luò)。如果監(jiān)視區(qū)域的任意一點都處于放置在該區(qū)域內(nèi)某一節(jié)點的監(jiān)視范圍內(nèi)，則稱節(jié)點能覆蓋該監(jiān)視區(qū)域。研究能確保有效覆蓋且數(shù)量最少的節(jié)點放置問題顯然具有重要意義。1.2問題的重述圖1 無線傳感網(wǎng)絡(luò)覆蓋示意圖圖1中，叉形表示一個無線傳感網(wǎng)絡(luò)節(jié)點，虛線的圓形區(qū)域表示該節(jié)點的覆蓋范圍。可見，該無線傳感網(wǎng)絡(luò)節(jié)點完全覆蓋了區(qū)域B，部分覆蓋了區(qū)域A。網(wǎng)絡(luò)節(jié)點間的通信設(shè)計問題是無線傳感器網(wǎng)絡(luò)設(shè)計的重要問題之一。如前所述，每個節(jié)點都有一定的覆蓋范圍，節(jié)點可以與覆蓋范圍內(nèi)的節(jié)點進(jìn)行

5、通信。但是當(dāng)節(jié)點需要與不在其覆蓋范圍內(nèi)的節(jié)點通信時，需要其它節(jié)點轉(zhuǎn)發(fā)才可以進(jìn)行通信。圖2 無線傳感網(wǎng)絡(luò)節(jié)點通信示意圖圖2所示，節(jié)點C不在節(jié)點A的覆蓋范圍之內(nèi)，而節(jié)點B在A與C的覆蓋范圍之內(nèi)，因此A可以將數(shù)據(jù)先傳給B，再通過B傳給C。行成一個ABC的通路。問題1：在一個監(jiān)視區(qū)域為邊長b=100(長度單位)的正方形中，每個節(jié)點的覆蓋半徑均為r=10(長度單位)。在設(shè)計傳感網(wǎng)絡(luò)時，需要知道對給定監(jiān)視區(qū)域在一定的覆蓋保證下應(yīng)放置節(jié)點的最少數(shù)量。對于上述給定的監(jiān)視區(qū)域及覆蓋半徑，確定至少需要放置多少個節(jié)點，才能使得成功覆蓋整個區(qū)域的概率在95%以上？問題2：在1所給的條件下，已知在該監(jiān)視區(qū)域內(nèi)放置了12

6、0個節(jié)點，它們位置的橫、縱坐標(biāo)如表1所示。請設(shè)計一種節(jié)點間的通信模型，給出任意10組兩節(jié)點之間的通信通路，比如節(jié)點1與節(jié)點90如何通信等。二、 問題的分析根據(jù)查詢的相關(guān)資料，無線傳感網(wǎng)絡(luò)設(shè)計中的節(jié)點放置和節(jié)點間通信問題是近今年的熱門課題。由于地理條件的復(fù)雜，一般情況下無線傳感網(wǎng)絡(luò)設(shè)計中的節(jié)點只能采用非均勻投放的方法。鑒于此，本文對題目中的問題做了如下分析：針對問題一：由于安放節(jié)點是隨機的，某事件發(fā)生的概率可以用多次實驗中該事件發(fā)生的頻率代替,而兩者均可用計算機仿真實現(xiàn)，因此可通過計算機不斷產(chǎn)生隨機數(shù)模擬節(jié)點安放和監(jiān)視區(qū)域各點被覆蓋的情況，再以題目中95%為約束，找出最優(yōu)節(jié)點數(shù)。針對問題二：對于

7、該問題，根據(jù)題目中所給的120個節(jié)點的坐標(biāo)，很容易求出各節(jié)點間的距離，由題設(shè)可知，一個節(jié)點不在另一個節(jié)點覆蓋的范圍之內(nèi)，則兩節(jié)點間不能直接通信，要通過其它節(jié)點間接通信。在通過其它節(jié)點實現(xiàn)間接通信的過程中，肯定會產(chǎn)生不同的通信通路，本文要做的是找出任意兩點間的最優(yōu)通信通路。這很容易讓人聯(lián)想到圖論模型最短路徑的求法，于是可根據(jù)題設(shè)限制條件，將各點間的距離矩陣轉(zhuǎn)化為帶權(quán)鄰接矩陣，通過matlab軟件求解出各點間的最優(yōu)通信通路。三、 模型假設(shè)1、 各節(jié)點的覆蓋范圍相同且穩(wěn)定，不受天氣及電磁干擾；2、 任何節(jié)點與其覆蓋范圍內(nèi)的節(jié)點間的通信強度相同；3、 節(jié)點間的通信距離與通信所用的時長成正比。四、 符號

8、及變量說明：每次仿真隨機產(chǎn)生的節(jié)點數(shù)；N：每次安放好節(jié)點后在監(jiān)視區(qū)域內(nèi)隨機取的檢驗點個數(shù)；：監(jiān)視區(qū)域內(nèi)第i個隨機點與第j個節(jié)點間的距離（i=1,2N；j=1，2n）；：第i個監(jiān)測點與n個節(jié)點的距離最小值(i=1,2N)；：每個節(jié)點的覆蓋半徑，r=10；T；仿真次數(shù)；：可以成功覆蓋整個監(jiān)視區(qū)域的仿真次數(shù)；：仿真中能成功覆蓋整個監(jiān)視區(qū)域的頻率；：n個節(jié)點成功覆蓋整個監(jiān)視區(qū)域的概率；：問題2中所給120個點中第i個點與第j個點之間的距離（i，j=1,2120）；：問題2中所給120個點之間的距離矩陣；：問題2中所給120個點中第i個點與第j個點之間通信路徑權(quán)值（i，j=1,2120）；：問題2中所給

9、120個點之間的帶權(quán)鄰接矩陣；：第i個節(jié)點域其他節(jié)點距離的最小值（i=1,2n）；五、 模型的建立和求解5.1對于問題一的模型建立和求解查閱相關(guān)文獻(xiàn)得知，無線傳感網(wǎng)絡(luò)中的節(jié)點安放是非均勻的，本文建立仿真模型，通過計算機在監(jiān)視區(qū)域內(nèi)隨機產(chǎn)生n個節(jié)點來模擬節(jié)點的非均勻安放根據(jù)概率論知識：當(dāng)試驗次數(shù)足夠大時，可以近似認(rèn)為事件發(fā)生的頻率等于其概率，于是可通過計算機在已將安放好節(jié)點的監(jiān)視區(qū)域內(nèi)隨機產(chǎn)生N個檢驗點，并求出這N個點與各節(jié)點間的距離 然后選出每個檢驗點與n個節(jié)點的距離最小值，根據(jù)題設(shè)節(jié)點間的通信條件，將與覆蓋半徑r比較，對于所有的i=1,2N(N取足夠大) ，若滿足 <r則可以認(rèn)為這n個

10、節(jié)點組成的無線通信網(wǎng)絡(luò)可以成功將監(jiān)視區(qū)域覆蓋，否則則認(rèn)為沒有成功覆蓋。對上述過程進(jìn)行T次仿真,統(tǒng)計能成功覆蓋整個監(jiān)視區(qū)域次數(shù)t，并計算出相應(yīng)的頻率f,當(dāng)T取足夠大時，可以認(rèn)為這n個節(jié)點能成功覆蓋整個監(jiān)視區(qū)域的概率根據(jù)題目要求，比較p與95%的大小若則增大n值；反之則減小n值，再重復(fù)上述仿真過程，直至找出時的最小n值。仿真算法流程圖如下： 初始化系統(tǒng)狀態(tài) 手動調(diào)整n值 N仿真次 數(shù)到了嗎？ 求頻率，等于95%嗎在監(jiān)視區(qū)內(nèi)隨機產(chǎn)生n個節(jié)點 Y在已經(jīng)安放好節(jié)點的區(qū)內(nèi)隨機取檢驗點 頻數(shù)增加 Y N 檢驗點被 覆蓋了嗎？ N 檢驗次數(shù)到了嗎？ 本文仿真程序相應(yīng)的參數(shù)為：T=1000 N=20000（詳見

11、附錄二第一題程序），通過不斷手動調(diào)整n的大小，最后找出能成功覆蓋整個區(qū)域的概率在95%以上的最少節(jié)點數(shù)為565個。5.2對于問題二模型的建立和求解根據(jù)題意，兩節(jié)點間能直接相互通信的條件為<r否則要通過其它節(jié)點間接進(jìn)行通信，在通過其它節(jié)點實現(xiàn)間接通信的過程中，肯定會產(chǎn)生不同的通信通路，本文要做的是找出任意兩點間的最優(yōu)通信通路。于是本文建立圖論模型，考慮到通信的時效性和及時性，以通信所用時間最短為選取最優(yōu)通路的原則，并根據(jù)本文條件假設(shè)3（節(jié)點間的通信距離與通信所用的時長成正比），將通信時間最短轉(zhuǎn)化為路徑最短，采用Dijkstraf算法求出任意給定的兩點間的最優(yōu)通信通路。Matlab程序求解步

12、驟如下：Step1：求出120點兩兩之間的距離矩陣 ；Step2：將D中大于r的元素變?yōu)?，將距離矩陣D轉(zhuǎn)化為帶權(quán)鄰接矩陣 ；Step3：采用Dijkstraf算法，將W帶入其中，計算出任意給定兩節(jié)點間的最優(yōu)通信通路。所得的十組節(jié)點間的最優(yōu)通信通路如表1：表11-2 1 11 107 70 41 95 102 18 36 104 103 21-10 1 80 64 25 101-20 1 11 5 62 106 4 54 111 98 99 201-30 1 11 5 62 106 301-40 1 80 55 401-50 1 80 501-60 1 80 64 25 46 65 66 93

13、13 3 87 15 601-70 1 11 107 701-80 1 801-90 1 80 64 25 46 65 66 93 13 3 87 15 60 90六、 模型的評價和改進(jìn)6.1模型的評價6.1.1優(yōu)點1 對于問題1本文在題目信息和查閱相關(guān)資料的基礎(chǔ)上，用計算機仿真法模擬無線網(wǎng)絡(luò)節(jié)點的不規(guī)則放置和檢驗無線網(wǎng)絡(luò)的覆蓋率，充分利用計算機的優(yōu)勢，化繁為簡，以頻率代替概率，得出的結(jié)論可信度高。2 在仿真過程中，對重要參數(shù)調(diào)整問題，本文采用手動調(diào)整法，這樣可以避免計算機仿真次數(shù)過多，程序運行時間過長的問題，既可以節(jié)省時間又可以較準(zhǔn)確判斷最理想的n值。3 求解問題2時，本文在考慮通信的時效性

14、和及時性的基礎(chǔ)上，建立圖論模型，并以通信時間最短為最佳路徑選取依據(jù)，又通過合理假設(shè)將時間最短轉(zhuǎn)換成距離最短，這樣就能與Dijkstraf算法完美結(jié)合，也能很便捷的求出題目要求的制定兩點間的通信通路。6.1.2缺點1. 計算機仿真次數(shù)有限，所得結(jié)果不可避免會有一定誤差2. 在建立仿真模型，檢驗監(jiān)視區(qū)域是否完全被覆蓋時，只考慮了區(qū)內(nèi)點的被覆蓋的概率，沒有考慮所有節(jié)點間是否能實現(xiàn)相互通信。6.2模型的改進(jìn)本文通過分析對問題1的中的仿真模型進(jìn)行改進(jìn)。在每次隨機布置好節(jié)點后，先通過節(jié)點間的距離對這n個節(jié)點布置合理性進(jìn)行初步檢驗，以一個節(jié)點與其他各節(jié)點距離的最小值為判斷依據(jù)，當(dāng)>r時，則該節(jié)點與其他

15、節(jié)點不能實現(xiàn)通信，應(yīng)該講該節(jié)點剔除。修改后測程序見附表二。講過修改后，得到能成功覆蓋整個區(qū)域的概率在95%以上的最少節(jié)點數(shù)為571個。七、 模型的推廣和應(yīng)用本文所建立的仿真模型，用到了隨機抽取和循環(huán)迭代思想，可廣泛應(yīng)用于估計某些事件可能發(fā)生的概率。本文建立的圖論模型也可廣泛應(yīng)用到無線設(shè)備比如手機的信號傳遞路徑選取上。參考文獻(xiàn)：1陶丹，馬華東，劉亮 無線傳感器網(wǎng)絡(luò)節(jié)點部署問題研究,北京 1008762茆詩松，程依明，濮曉龍.概率論與數(shù)理統(tǒng)計教程M.北京：高等教育出版社.2009；3劉衛(wèi)國 主編 MATLAB程序設(shè)計教程 (第二版)M. 水利水電出版社出版社.2010；附錄一：120個節(jié)點的坐標(biāo)表

16、節(jié)點標(biāo)號XY節(jié)點標(biāo)號XY節(jié)點標(biāo)號XY節(jié)點標(biāo)號XY157583163361329591744429574328596247719241253341233643763504393392143168342213645643949551552673569436556259572766304368083664725967987157537761367806497784487552388894681096981080975303925956912339988910652840624570637010015951155634170707139910145901241614245427281891027082

17、133620433597343141039078147224447541741725104847815161045359175805510520701685494656307645611064071178690472792779240107557018759048929078782210859519322049255879894510973182059250445280515111022282116355158081409011117802225665217338265491125010237245390583767113552024683354257484309811487222561355

18、5584785263411572982637785695286289911655792748465787728725811772288131586888882963118852029239059302889408311935503035666099904111201068附錄三：第一題程序clcclearn=565; %設(shè)定n個節(jié)點T=1000; %隨機設(shè)定節(jié)點的次數(shù)N=20000; %檢驗覆蓋率的仿真次數(shù)r=10; %覆蓋半徑t=0; %被完全覆蓋次數(shù)for i=1:T m=0; %覆蓋的點的個數(shù)，每次循環(huán)初始化為零 Q=0; %區(qū)域覆蓋率，每次循環(huán)初始化為零for i=1:n %在監(jiān)視區(qū)域

19、內(nèi)隨機產(chǎn)生n個節(jié)點 A(i)=100*rand; %橫坐標(biāo) B(i)=100*rand; %縱坐標(biāo)end for i=1:N %在監(jiān)視區(qū)域內(nèi)隨機取N個點看其是否被覆蓋 x=100*rand; %橫坐標(biāo) y=100*rand; %縱坐標(biāo) for i=1:n d(i)=sqrt(x-A(i).2+(y-B(i).2); %計算該點與n個節(jié)點的距離 end if min(d)<=r %判斷該點是否被覆蓋 m=m+1; end endif m=N %判斷是否被完全覆蓋 t=t+1endend p=t/T %監(jiān)視區(qū)域被完全覆蓋的頻率第二題程序clcclearx=load('x.txt');y=load('y.txt'); %輸入節(jié)點坐標(biāo)for i=1:120 for j=1:120 d(i,j)=sqrt(x(i)-x(j).2+(y(i)-y(j)2); %求出各節(jié)點間的距離矩陣 if d(i,j)>10 %將距離矩陣轉(zhuǎn)化為帶權(quán)鄰接矩陣 d(i,j)=inf; end endend dis, path=dijkstraf(d, 1, 5