《《無線傳感器網(wǎng)絡(luò)》word版.doc》由會員分享，可在線閱讀，更多相關(guān)《《無線傳感器網(wǎng)絡(luò)》word版.doc（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第一次個人賽論文 姓名代碼：89 無線傳感網(wǎng)絡(luò)設(shè)計問題 摘要 本文通過研究無線傳感網(wǎng)絡(luò)的覆蓋問題和節(jié)點的通信模型設(shè)計，建立無線傳感網(wǎng)絡(luò)，可以準確而及時地掌握險情的發(fā)展情況。 針對問題一，在給定區(qū)域面積和節(jié)點覆蓋半徑，且要求必須覆蓋整個區(qū)域的前提下，通過隨機模擬確定最少的節(jié)點數(shù)。首先通過蜂窩網(wǎng)格法，分析得到理論上覆蓋整個區(qū)域所需最少的節(jié)點數(shù)為45個。然后通過軟件在監(jiān)視區(qū)域內(nèi)產(chǎn)生N個隨機測試點，再產(chǎn)生隨機均勻分布的M個節(jié)點，觀察這些節(jié)點圓是否已完全覆蓋這些測試點，并保證覆蓋整個區(qū)域的概率在95%以上,利用matlab通過500次模擬得到?？紤]到隨機產(chǎn)生的測試點不穩(wěn)定，可以做進一步優(yōu)化，使得這些測試點完全轉(zhuǎn)化為區(qū)域內(nèi)的固定點，當各點間隔趨于無窮小時，便可均勻覆蓋整個區(qū)域，再分析節(jié)點圓覆蓋整個區(qū)域的概率。通過對這兩種方法進行對比，得出后者更優(yōu)，最后確定至少為535個。 針對問題二，設(shè)計了兩種節(jié)點間的相互通信模型。已知每個節(jié)點覆蓋半徑，且節(jié)點只能與覆蓋范圍內(nèi)的節(jié)點進行通信，即兩節(jié)點之間的距離要小于半徑。方法一把能相互通信的點連線，可以得到節(jié)點間的通信路徑圖，通過該圖可以找出任意兩個節(jié)點間的通信路徑，并給出了十組任意節(jié)點之間的通路。方法二在節(jié)點通信路徑圖的基礎(chǔ)上進行優(yōu)化，通過Dijkstra算法求最短路徑，準確快速實現(xiàn)任意兩個節(jié)點之間的最短通路及最距離大小。通過對這兩種方法的對比分析，可知方法一通信路徑并不唯一，對于距離較短，節(jié)點少時，簡單易用，但當通信距離較大、節(jié)點多時，不易觀察，且計算路徑繁瑣。方法二計算準確快速，適用性更廣。因此，Dijkstra算法更適用于大范圍的無線傳感網(wǎng)絡(luò)設(shè)計。 最后，本文對采用的模型方法進行了分析，并提出了適當?shù)母倪M方案。 關(guān)鍵詞：隨機模擬；節(jié)點通信；Dijkstra算法 一、 問題的提出和重述 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ò)，使人們能準確而及時地掌握險情的發(fā)展情況。 如果監(jiān)視區(qū)域的任意一點都處于放置在該區(qū)域內(nèi)某一節(jié)點的監(jiān)視范圍內(nèi)，則稱節(jié)點能覆蓋該監(jiān)視區(qū)域。研究能確保有效覆蓋且數(shù)量最少的節(jié)點放置問題顯然具有重要意義。 圖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é)點可以與覆蓋范圍內(nèi)的節(jié)點進行通信。但是當節(jié)點需要與不在其覆蓋范圍內(nèi)的節(jié)點通信時，需要其它節(jié)點轉(zhuǎn)發(fā)才可以進行通信。 圖2 無線傳感網(wǎng)絡(luò)節(jié)點通信示意圖 圖2所示，節(jié)點C不在節(jié)點A的覆蓋范圍之內(nèi)，而節(jié)點B在A與C的覆蓋范圍之內(nèi)，因此A可以將數(shù)據(jù)先傳給B，再通過B傳給C，行成一個A－B－C的通路。 1.2問題的重述 查找相關(guān)資料，建立數(shù)學(xué)模型解決以下兩個問題： 1、在一個監(jiān)視區(qū)域為邊長b=100(長度單位)的正方形中，每個節(jié)點的覆蓋半徑均為r=10(長度單位)。對于上述給定的監(jiān)視區(qū)域及覆蓋半徑，確定至少需要放置多少個節(jié)點，才能使得成功覆蓋整個區(qū)域的概率在95%以上？ 2、在1所給的條件下，已知在該監(jiān)視區(qū)域內(nèi)放置了120個節(jié)點，它們的橫、縱坐標如附表1所示。設(shè)計一種節(jié)點間的相互通信模型，并給出任意10組兩節(jié)點之間的通信通路。 二、 問題的分析 通過建立無線傳感網(wǎng)絡(luò)，可以準確而及時地掌握險情的發(fā)展情況。因此，本文研究的是傳感網(wǎng)絡(luò)的覆蓋問題，確定設(shè)置多少個節(jié)點使得成功覆蓋概率達95%，同時設(shè)計一個合理有效的節(jié)點通信模型，使得整個無線傳感網(wǎng)絡(luò)可以準確快速通信，且經(jīng)濟實用。 針對問題一，在給定區(qū)域面積和節(jié)點覆蓋半徑的前提下，需要確定至少需要放置多少個節(jié)點，才能使得成功覆蓋整個區(qū)域的概率在95%以上。在必須覆蓋整個區(qū)域的要求下，可以通過仿真模擬來確定最少的節(jié)點數(shù)，并計算覆蓋效率（覆蓋效率越大越經(jīng)濟）。首先通過蜂窩網(wǎng)格法[1]，可以分析理論上覆蓋整個區(qū)域所需最少的節(jié)點數(shù)。通過蒙特卡洛模擬編程[2]實現(xiàn)，在監(jiān)視區(qū)域內(nèi)產(chǎn)生隨機均勻分布的N個測試點，再產(chǎn)生隨機均勻分布的M個節(jié)點，觀察這些節(jié)點是否已完全覆蓋這些測試點，并進行多次模擬，保證覆蓋整個區(qū)域的概率在95%以上?？紤]到隨機產(chǎn)生的測試點不穩(wěn)定，我們可以進一步優(yōu)化，使得這些測試點轉(zhuǎn)化為區(qū)域內(nèi)的固定點，各點間隔趨于無窮小時，便可均勻覆蓋整個區(qū)域，再分析節(jié)點覆蓋整個區(qū)域的概率。 針對問題二，設(shè)計一種節(jié)點間的相互通信模型。已知每個節(jié)點都有一定的覆蓋范圍，根據(jù)節(jié)點只能與覆蓋范圍內(nèi)的節(jié)點進行通信，即兩節(jié)點之間的距離要小于半徑，把能相互通信的點連線，可以得到節(jié)點間的通信路徑圖，通過該圖可以找出任意兩個節(jié)點間的通信路徑。但此方法當通信距離較大、節(jié)點多時，不易觀察，且手工計算路徑繁瑣。因此，在節(jié)點通信路徑圖的基礎(chǔ)上進行優(yōu)化，通過Dijkstra算法（以下簡稱D算法）可以準確快速實現(xiàn)任意兩個節(jié)點之間的最短通路及最短路徑大小，比如節(jié)點5到其余任何點的最短通路。 三、 模型假設(shè) 1、 節(jié)點裝置在監(jiān)視區(qū)域內(nèi)是呈均勻分布隨機放置的。 2、 定義覆蓋效率為監(jiān)視區(qū)域除以各節(jié)點能覆蓋的面積總和； 3、 不考慮節(jié)點周圍環(huán)境對通信范圍的影響。 4、 假設(shè)在兩個節(jié)點覆蓋圓臨界位置（相切處）不可通信。 四、 符號及變量說明 :隨機測試點數(shù)； :節(jié)點數(shù)； :隨機模擬次數(shù)； :覆蓋整個區(qū)域的概率； : 覆蓋效率； ：正方形小網(wǎng)格邊長； 五、 模型的建立和求解 5.1針對問題一的求解 5.1.1理論最少節(jié)點數(shù)的求解 根據(jù)數(shù)學(xué)定理：如果3個半徑相同的圓兩兩相交，且覆蓋面積最大，則三圓相交于一點，且三個圓心圍成等邊三角形。如圖（1）所示，根據(jù)此定理，在的監(jiān)視范圍內(nèi)平鋪，利用CAD畫圖得到圖（2）。 圖（1） 　　　　　　　　　　　　　　　　　 圖（２） 在此平鋪狀態(tài)下，即為蜂窩網(wǎng)格法，得到最少的節(jié)點數(shù)為45個，其覆蓋效率為。此狀態(tài)在隨機模擬下出現(xiàn)的概率幾乎為零，因此要使成功覆蓋整個區(qū)域的概率在95%以上，節(jié)點數(shù)遠大于45個。 5.1.2 隨機測試點求最少節(jié)點數(shù) 通過在監(jiān)視區(qū)域內(nèi)產(chǎn)生個均勻分布隨機測試點，再往監(jiān)視區(qū)域內(nèi)隨機放置個節(jié)點，若這個節(jié)點能完全覆蓋這個測試點，則認為該區(qū)域被完全覆蓋，通過次模擬，保證覆蓋整個區(qū)域的次數(shù)至少為，以此求得最小的Ｍ值。 通過編程實現(xiàn)模擬500次，得到表（１）和圖（３），并解得當時，左右。由表（１）可以看出Ｎ值與Ｐ值并不成比例關(guān)系，值不穩(wěn)定，難以確定具體Ｎ為多少時，概率，因此，該方法仍有待進一步優(yōu)化。 N 530 531 532 533 534 535 536 537 538 539 P 0.9433 0.9267 0.9300 0.9633 0.9367 0.9333 0.9567 0.9467 0.9600 0.9533 表（１）十組值對應(yīng)的值 圖（３）隨機測試點模擬圖 5.1.3 固定測試點求最少節(jié)點數(shù) 對于的覆蓋區(qū)域，分成面積為的正方形小網(wǎng)格，并賦予每個小網(wǎng)格為0值，當時，每個小網(wǎng)格趨向于點，網(wǎng)格數(shù)也就越多。為便于計算，這里取1，以網(wǎng)格中心點代表整個網(wǎng)格，當該中心點到隨機分布的任意一個節(jié)點的距離小于半徑時，網(wǎng)格被賦值為1。按此循環(huán)，當每個網(wǎng)格均被賦值為1時，即表示節(jié)點覆蓋了整個區(qū)域，達到要求。 通過matlab編程模擬500次，得到表（2）和圖（4）。通過對表（1）與表（2）的對比分析可知，值更為穩(wěn)定，通過線性擬合圖（5）也可知用固定點模擬的方法更好。 綜上，在一定范圍內(nèi)，得出在時，，，符合要求。 N 530 531 532 533 534 535 536 537 538 539 P 0.9417 0.9333 0.9300 0.9433 0.9427 0.9500 0.9500 0.9537 0.9733 0.9667 表（2）十組值對應(yīng)的值 圖（4）固定測試點模擬圖 圖（5）兩種方法線性擬合對比圖 5.2針對問題二的求解 5.2.1 可通信節(jié)點路徑分布圖的設(shè)計 已知每個節(jié)點都有一定的覆蓋范圍（），節(jié)點只能與覆蓋范圍之內(nèi)的節(jié)點進行通信，任意兩個節(jié)點之間的歐式距離可表示為： 所以當?shù)膬蓚€節(jié)點之間才可以進行通信，因此，通過matlab編程（附錄程序三）將120節(jié)點中所有的兩節(jié)點之間用直線連接，得到節(jié)點通信路徑圖，如圖（6）所示： 圖（6）節(jié)點通信路徑圖 通過觀察此節(jié)點通信圖，可以知道任意兩節(jié)點之間的通信通路，任取10組節(jié)點，找出其通信路徑，并計算其通信距離，如下表（3）所示，并通過圖（7）可直接觀測其通信通路： 序號 起始節(jié)點 終止節(jié)點 通信路徑 通信距離 1 60 87 601587 16.29 2 6 73 64373 16.51 3 93 10 93666510 27.43 4 14 28 14928 12.79 5 8 16 87516 13.64 6 80 12 805512 16.56 7 41 18 419510818 20.08 8 62 11 62511 11.40 9 49 106 498830106 20.18 10 99 54 9998710554 29.76 表（3）：10個任意節(jié)點的通信路徑及通信距離 圖（7）：上述10個節(jié)點的通路圖 通過直接觀測通信圖，可知通信路徑并不唯一，對于距離較短，節(jié)點少時，簡單易用，但是當通信距離較大、節(jié)點多時，則不易觀察，且計算繁瑣，不宜采用。因此下面通過適當算法來更準確快速實現(xiàn)通信圖的設(shè)計。 5.2.1 Dijkstra算法通信路徑的設(shè)計 D算法思路[3]：采用標號作業(yè)法,每次迭代產(chǎn)生一個永久標號, 從而生長一顆以為根的最短路樹,在這顆樹上每個頂點與根節(jié)點之間的路徑皆為最短路徑。該算法核心是求得鄰階矩陣，計算某點到其余點的距離，若其余某點在該點的通信范圍內(nèi)，則。反之，∞。本文可以得到一個鄰階矩陣，調(diào)用D算法程序，實現(xiàn)通信路徑及距離的計算。 為方便比較，仍取上述表（3）中的起始節(jié)點和終止節(jié)點，通過matlab編程得到圖（8）D算法最短通信路徑及距離分布圖 圖（8）D算法最短通信路徑及距離分布圖 通過圖（7）和圖（8）的對比分析，其通信路徑及距離是完全吻合的，但用D算法明顯更為優(yōu)越，能夠快速準確地給出任意兩節(jié)點之間的最短通信路徑以及此時的最短通信距離，且誤差很小。 六、 模型的評價和改進 6.1模型的評價 6.1.1優(yōu)點 (1)本文通過多次模擬來求解全部覆蓋的概率，方法實用簡單，容易編程實現(xiàn)。 (2)運用D算法求解最短通信路徑和距離時，準確快速可靠，且容易編程實現(xiàn)，易于推廣。 （3）通過對覆蓋效率的計算，便于經(jīng)濟、實用方面的分析。 6.1.2缺點 (1) 通過隨機模擬不可避免會有誤差，若模擬次數(shù)不夠多，造成的誤差也大。每次的模擬會有不同的在微小范圍內(nèi)浮動值。 (2) 軟件編程時計算量大，運算時間長。 6.2模型的改進 從第一問的覆蓋效率可知，效率偏低，因此十分有必要提高其覆蓋效率，可以對覆蓋區(qū)域進行全面了解后，通過精確計算確定各個節(jié)點位置，減少隨機模擬的誤差，對于重復(fù)覆蓋頻率高的地區(qū)減少節(jié)點數(shù)，對于重復(fù)覆蓋頻率很低的地區(qū)增加節(jié)點數(shù)，使其均勻化，從而增加了覆蓋效率，也更加經(jīng)濟。 七、 模型的推廣和應(yīng)用 本文對研究無線傳感網(wǎng)絡(luò)的覆蓋問題和節(jié)點的通信模型設(shè)計進行了討論，建立無線傳感網(wǎng)絡(luò)，可以準確而及時地掌握險情的發(fā)展情況，在森林防火、災(zāi)區(qū)空投物資、戰(zhàn)場空投等方面都具有一定的指導(dǎo)作用。 參考文獻： [1]陸克中、毛睿等 基于蜂窩結(jié)構(gòu)的傳感器網(wǎng)絡(luò)覆蓋問題求解算法 計算機研究與發(fā)展學(xué)報 第3期：80-84，2012； [2]薛山 MATLAB基礎(chǔ)教程 清華大學(xué)出版社 2011-03-01; [3]Dijkstra最短路徑算法（百度文庫） 鏈接:http://wenku.baidu.com/view/680ebde29b89680203d82598.html 附錄： 附表1 120個節(jié)點的坐標表 節(jié)點標號 X Y 節(jié)點標號 X Y 節(jié)點標號 X Y 節(jié)點標號 X Y 1 57 58 31 6 33 61 32 95 91 74 44 2 95 74 32 85 9 62 47 71 92 41 25 3 34 12 33 64 37 63 50 43 93 39 21 4 31 68 34 22 13 64 56 43 94 95 51 5 52 67 35 69 43 65 56 25 95 72 76 6 30 4 36 80 83 66 47 25 96 79 8 7 15 75 37 76 13 67 80 64 97 78 44 8 75 52 38 88 94 68 10 96 98 10 80 9 75 30 39 25 95 69 12 33 99 8 89 10 65 28 40 62 45 70 63 70 100 15 95 11 55 63 41 70 70 71 39 9 101 45 90 12 41 61 42 45 42 72 81 89 102 70 82 13 36 20 43 35 9 73 43 14 103 90 78 14 72 24 44 75 41 74 17 25 104 84 78 15 16 10 45 35 91 75 80 55 105 20 70 16 85 49 46 56 30 76 45 61 106 40 71 17 86 90 47 27 92 77 92 40 107 55 70 18 75 90 48 92 90 78 78 22 108 5 95 19 32 20 49 25 58 79 89 45 109 73 18 20 5 92 50 44 52 80 51 51 110 22 28 21 16 35 51 5 80 81 40 90 111 17 80 22 25 66 52 17 33 82 65 49 112 50 10 23 72 4 53 90 5 83 76 7 113 55 20 24 68 33 54 25 74 84 30 98 114 87 22 25 61 35 55 58 47 85 26 34 115 72 98 26 37 78 56 95 2 86 28 99 116 55 79 27 48 46 57 87 72 87 25 8 117 7 2 28 81 31 58 68 88 88 29 63 118 85 20 29 23 90 59 30 28 89 40 83 119 35 50 30 35 66 60 9 9 90 4 11 120 10 68 %程序（一）：隨機模擬覆蓋的概率 clear clc for n=530:540;%設(shè)置節(jié)點數(shù) T=10000; m=0; for k=1:500 %模擬次數(shù) x=100*rand(n,1); %產(chǎn)生n個圓心坐標 y=100*rand(n,1); p=0; c=0; for i=1:T x0=100*rand; %產(chǎn)生T個隨機點坐標 y0=100*rand; for j=1:n if (x0-x(j))^2+(y0-y(j))^2<100 p=p+1; break; end end end if p==T %已全部覆蓋 m=m+1; end end c=m/300 c=0; end %程序（二）：固定點覆蓋的概率 %% clear clc m=0; h=1;%間隔 c=100; K=500;%模擬次數(shù) P=0;%覆蓋率 %產(chǎn)生c*c個固定點坐標，c=100； x=[]; for i=0:99 x((1+100*i):(100+100*i),1)=0.5+i; end for i=1:100 Y(i,1)=i-0.5; end y=[]; for i=1:99 y((1+100*i):(100+100*i),1)=Y; end for n=530:540 for k=1:K f=0; x0=100*rand(n,1); %產(chǎn)生n個節(jié)點圓心坐標 y0=100*rand(n,1); p=0; for i1=1:c*c/h for p=1:n if (x(i1)-x0(p))^2+(y(i1)-y0(p))^2<100 f=f+1; break; end end end if f==(c*c) m=m+1; end end P=m/K m=0; end %程序（三）：通信路徑圖 clear clc X=load(shuju.txt); x0=X(:,2); y0=X(:,3); plot(x0,y0,.) text(x0,y0,num2cell(1:120)) hold on for i=1:120 for j=1:120 D(i,j)=((x0(i)-x0(j))^2+(y0(i)-y0(j))^2)^0.5; if D(i,j)<10; x=[x0(i) x0(j)]; y=[y0(i) y0(j)]; plot(x,y); hold on end end end title(通信路徑圖) xlabel(X) ylabel(Y) %程序（四）：D算法最短通信路徑圖 clear clc X=load(shuju.txt); x=X(:,2); y=X(:,3); %產(chǎn)生鄰階矩陣 for i=1:120 for j=1:120 dis(i,j)=((x(i)-x(j))^2+(y(i)-y(j))^2)^0.5; if dis(i,j)>=10 dis(i,j)=Inf; end end end w=dis; m=[60 6 93 14 8 80 41 62 49 99]; %取十組節(jié)點 n= [87 73 10 28 16 12 18 11 106 54]; for i=1:10 [dis, path]=dijkstraf(w,m(i),n(i)) %調(diào)用dijkstraf.m文件 end clear clc A=load(shuju.txt); x=A(:,2); y=A(:,3); %產(chǎn)生鄰階矩陣 for i=1:120 for j=1:120 dis(i,j)=((x(i)-x(j))^2+(y(i)-y(j))^2)^0.5; if dis(i,j)>=10 dis(i,j)=Inf; end end end w=dis; m=[60 6 93 14 8 80 41 62 49 99];%取上述十組節(jié)點 n=[87 73 10 28 16 12 18 11 106 54]; for i=1:10 [dis,path]=dijkstraf(w,m(i),n(i))%調(diào)用dijkstraf.m文件 for i=1:length(path) X(i)=x(path(i)); Y(i)=y(path(i)); plot(X,Y,*) hold on end plot(X,Y) xlabel(X) ylabel(Y) title(D算法最短通信路徑圖) hold on X=0; Y=0; end