第一次個人賽論文 姓名代碼：89無線傳感網(wǎng)絡設計問題摘要本文通過研究無線傳感網(wǎng)絡的覆蓋問題和節(jié)點的通信模型設計，建立無線傳感網(wǎng)絡，可以準確而及時地掌握險情的發(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個。針對問題二，設計了兩種節(jié)點間的相互通信模型。已知每個節(jié)點覆蓋半徑，且節(jié)點只能與覆蓋范圍內(nèi)的節(jié)點進行通信，即兩節(jié)點之間的距離要小于半徑。方法一把能相互通信的點連線，可以得到節(jié)點間的通信路徑圖，通過該圖可以找出任意兩個節(jié)點間的通信路徑，并給出了十組任意節(jié)點之間的通路。方法二在節(jié)點通信路徑圖的基礎(chǔ)上進行優(yōu)化，通過Dijkstra算法求最短路徑，準確快速實現(xiàn)任意兩個節(jié)點之間的最短通路及最距離大小。通過對這兩種方法的對比分析，可知方法一通信路徑并不唯一，對于距離較短，節(jié)點少時，簡單易用，但當通信距離較大、節(jié)點多時，不易觀察，且計算路徑繁瑣。方法二計算準確快速，適用性更廣。因此，Dijkstra算法更適用于大范圍的無線傳感網(wǎng)絡設計。最后，本文對采用的模型方法進行了分析，并提出了適當?shù)母倪M方案。關(guān)鍵詞：隨機模擬；節(jié)點通信；Dijkstra算法一、 問題的提出和重述1.1問題的提出大氣污染所引起的地球氣候異常，導致地震、旱災等自然災害頻頻發(fā)生，給人民的生命財產(chǎn)造成巨大損失。因此，研究如何有效監(jiān)測自然災害的措施十分必要。在容易出現(xiàn)自然災害的重點地區(qū)放置高科技的監(jiān)視裝置，建立無線傳感網(wǎng)絡，使人們能準確而及時地掌握險情的發(fā)展情況。如果監(jiān)視區(qū)域的任意一點都處于放置在該區(qū)域內(nèi)某一節(jié)點的監(jiān)視范圍內(nèi)，則稱節(jié)點能覆蓋該監(jiān)視區(qū)域。研究能確保有效覆蓋且數(shù)量最少的節(jié)點放置問題顯然具有重要意義。圖1 無線傳感網(wǎng)絡覆蓋示意圖如圖1所示，叉形表示一個無線傳感網(wǎng)絡節(jié)點，虛線的圓形區(qū)域表示該節(jié)點的覆蓋范圍。該無線傳感網(wǎng)絡節(jié)點完全覆蓋了區(qū)域B，部分覆蓋了區(qū)域A。網(wǎng)絡節(jié)點間的通信設計問題是無線傳感器網(wǎng)絡設計的重要問題之一。節(jié)點可以與覆蓋范圍內(nèi)的節(jié)點進行通信。但是當節(jié)點需要與不在其覆蓋范圍內(nèi)的節(jié)點通信時，需要其它節(jié)點轉(zhuǎn)發(fā)才可以進行通信。圖2 無線傳感網(wǎng)絡節(jié)點通信示意圖圖2所示，節(jié)點C不在節(jié)點A的覆蓋范圍之內(nèi)，而節(jié)點B在A與C的覆蓋范圍之內(nèi)，因此A可以將數(shù)據(jù)先傳給B，再通過B傳給C，行成一個ABC的通路。1.2問題的重述查找相關(guān)資料，建立數(shù)學模型解決以下兩個問題：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所示。設計一種節(jié)點間的相互通信模型，并給出任意10組兩節(jié)點之間的通信通路。二、 問題的分析通過建立無線傳感網(wǎng)絡，可以準確而及時地掌握險情的發(fā)展情況。因此，本文研究的是傳感網(wǎng)絡的覆蓋問題，確定設置多少個節(jié)點使得成功覆蓋概率達95%，同時設計一個合理有效的節(jié)點通信模型，使得整個無線傳感網(wǎng)絡可以準確快速通信，且經(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ū)域的概率。針對問題二，設計一種節(jié)點間的相互通信模型。已知每個節(jié)點都有一定的覆蓋范圍，根據(jù)節(jié)點只能與覆蓋范圍內(nèi)的節(jié)點進行通信，即兩節(jié)點之間的距離要小于半徑，把能相互通信的點連線，可以得到節(jié)點間的通信路徑圖，通過該圖可以找出任意兩個節(jié)點間的通信路徑。但此方法當通信距離較大、節(jié)點多時，不易觀察，且手工計算路徑繁瑣。因此，在節(jié)點通信路徑圖的基礎(chǔ)上進行優(yōu)化，通過Dijkstra算法（以下簡稱D算法）可以準確快速實現(xiàn)任意兩個節(jié)點之間的最短通路及最短路徑大小，比如節(jié)點5到其余任何點的最短通路。三、 模型假設1、 節(jié)點裝置在監(jiān)視區(qū)域內(nèi)是呈均勻分布隨機放置的。2、 定義覆蓋效率為監(jiān)視區(qū)域除以各節(jié)點能覆蓋的面積總和；3、 不考慮節(jié)點周圍環(huán)境對通信范圍的影響。4、 假設在兩個節(jié)點覆蓋圓臨界位置（相切處）不可通信。四、 符號及變量說明:隨機測試點數(shù)；:節(jié)點數(shù)； :隨機模擬次數(shù)；:覆蓋整個區(qū)域的概率；: 覆蓋效率；：正方形小網(wǎng)格邊長；五、 模型的建立和求解5.1針對問題一的求解5.1.1理論最少節(jié)點數(shù)的求解 根據(jù)數(shù)學定理：如果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)化。N530531532533534535536537538539P0.94330.92670.93000.96330.93670.93330.95670.94670.96000.9533表（）十組值對應的值 圖（）隨機測試點模擬圖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)，得出在時，符合要求。N530531532533534535536537538539P0.94170.93330.93000.94330.94270.95000.95000.95370.97330.9667表（2）十組值對應的值 圖（4）固定測試點模擬圖圖（5）兩種方法線性擬合對比圖5.2針對問題二的求解5.2.1 可通信節(jié)點路徑分布圖的設計已知每個節(jié)點都有一定的覆蓋范圍（），節(jié)點只能與覆蓋范圍之內(nèi)的節(jié)點進行通信，任意兩個節(jié)點之間的歐式距離可表示為： 所以當?shù)膬蓚€節(jié)點之間才可以進行通信，因此，通過matlab編程（附錄程序三）將120節(jié)點中所有的兩節(jié)點之間用直線連接，得到節(jié)點通信路徑圖，如圖（6）所示：圖（6）節(jié)點通信路徑圖通過觀察此節(jié)點通信圖，可以知道任意兩節(jié)點之間的通信通路，任取10組節(jié)點，找出其通信路徑，并計算其通信距離，如下表（3）所示，并通過圖（7）可直接觀測其通信通路：序號起始節(jié)點終止節(jié)點 通信路徑 通信距離16087 601587 16.292673 64373 16.5139310 93666510 27.434 14 28 14928 12.795816 87516 13.6468012 805512 16.5674118 419510818 20.0886211 62511 11.40949106 498830106 20.18109954 9998710554 29.76表（3）：10個任意節(jié)點的通信路徑及通信距離圖（7）：上述10個節(jié)點的通路圖通過直接觀測通信圖，可知通信路徑并不唯一，對于距離較短，節(jié)點少時，簡單易用，但是當通信距離較大、節(jié)點多時，則不易觀察，且計算繁瑣，不宜采用。因此下面通過適當算法來更準確快速實現(xiàn)通信圖的設計。5.2.1 Dijkstra算法通信路徑的設計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é)點位置，減少隨機模擬的誤差，對于重復覆蓋頻率高的地區(qū)減少節(jié)點數(shù)，對于重復覆蓋頻率很低的地區(qū)增加節(jié)點數(shù)，使其均勻化，從而增加了覆蓋效率，也更加經(jīng)濟。七、 模型的推廣和應用 本文對研究無線傳感網(wǎng)絡的覆蓋問題和節(jié)點的通信模型設計進行了討論，建立無線傳感網(wǎng)絡，可以準確而及時地掌握險情的發(fā)展情況，在森林防火、災區(qū)空投物資、戰(zhàn)場空投等方面都具有一定的指導作用。參考文獻：1陸克中、毛睿等 基于蜂窩結(jié)構(gòu)的傳感器網(wǎng)絡覆蓋問題求解算法 計算機研究與發(fā)展學報 第3期：80-84，2012；2薛山 MATLAB基礎(chǔ)教程 清華大學出版社 2011-03-01;3Dijkstra最短路徑算法（百度文庫）鏈接:http:/wenku.baidu.com/view/680ebde29b89680203d82598.html附錄： 附表1 120個節(jié)點的坐標表節(jié)點標號XY節(jié)點標號XY節(jié)點標號XY節(jié)點標號XY1575831633613295917444295743285962477192412533412336437635043933921431683422136456439495515526735694365562595727663043680836647259679871575377613678064977844875523888946810969810809753039259569123399889106528406245706370100159511556341707071399101459012416142454272818910270821336204335973431410390781472244475417417251048478151610453591758055105207016854946563076456110640711786904727927792401075570187590489290787822108595193220492558798945109731820592504452805151110222821163551580814090111178022256652173382654911250102372453905837671135520246833542574843098114872225613555584785263411572982637785695286289911655792748465787728725811772288131586888882963118852029239059302889408311935503035666099904111201068%程序（一）：隨機模擬覆蓋的概率clearclcfor n=530:540;%設置節(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; endendc=m/300c=0;end%程序（二）：固定點覆蓋的概率%clearclcm=0;h=1;%間隔c=100;K=500;%模擬次數(shù)P=0;%覆蓋率%產(chǎn)生c*c個固定點坐標，c=100；x=;for i=0:99x(1+100*i):(100+100*i),1)=0.5+i;endfor i=1:100 Y(i,1)=i-0.5;endy=;for i=1:99 y(1+100*i):(100+100*i),1)=Y;end for n=530:540for 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; endendP=m/Km=0;end%程序（三）：通信路徑圖clearclcX=load(shuju.txt);x0=X(:,2);y0=X(:,3);plot(x0,y0,.)text(x0,y0,num2cell(1:120) hold onfor 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 endendtitle(通信路徑圖)xlabel(X)ylabel(Y)%程序（四）：D算法最短通信路徑圖clearclcX=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 endendw=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:10dis, path=dijkstraf(w,m(i),n(i) %調(diào)用dijkstraf.m文件endclearclcA=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 endendw=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:10dis,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 endplot(X,Y)xlabel(X)ylabel(Y)title(D算法最短通信路徑圖)hold onX=0;Y=0;end