無線傳感網(wǎng)絡設計問題.doc

第二次個人賽論文 姓名代碼：88無線傳感網(wǎng)絡設計問題摘要本文針對無線傳感網(wǎng)絡節(jié)點的放置和節(jié)點間相互通信的路徑選擇問題做了深入的研究。對于問題（1），本文根據(jù)概率論知識（當試驗次數(shù)足夠大時，可以近似認為事件發(fā)生的頻率等于其概率）采用計算機仿真法，在監(jiān)視區(qū)域內(nèi)隨機安放n個節(jié)點，組建無線傳感網(wǎng)絡，然后在監(jiān)視區(qū)域隨機取20000個點，通過檢驗這些點是否全部被所組建的無線傳感網(wǎng)絡覆蓋來判斷所組建的無線傳感網(wǎng)絡能否成功覆蓋整個區(qū)域。進行多次仿真，統(tǒng)計并計算出由這n個節(jié)點組成的無線傳感網(wǎng)絡成功覆蓋整個區(qū)域的頻率，將此頻率與95%比較，然后根據(jù)不同情況適當調(diào)整n的大小，最后找出能成功覆蓋整個區(qū)域的概率在95%以上的最少節(jié)點數(shù)n為565個。 對于問題（2），本文建立圖論模型，在滿足題設節(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）中的模型進行了評價，并對第一問中的仿真模型求解時只檢驗無線傳感網(wǎng)絡對整個監(jiān)視區(qū)域是否完全覆蓋，而沒有考慮隨機安放的節(jié)點間能否相互通信的問題進行了進一步討論，并提出以節(jié)點間距離的最小值為判斷依據(jù)，在原覆蓋的基礎上剔除一些與其他節(jié)點間最小距離大于10的節(jié)點的修正方案。并對模型進行了簡單的推廣。關(guān)鍵詞： 計算機仿真；圖論模型；概率論；Dijkstraf算法一、 問題的提出和重述1.1問題的提出大氣污染所引起的地球氣候異常，導致地震、旱災等自然災害頻頻發(fā)生，給人民的生命財產(chǎn)造成巨大損失。因此，不少國家政府都在研究如何有效監(jiān)測自然災害的措施。在容易出現(xiàn)自然災害的重點地區(qū)放置高科技的監(jiān)視裝置，建立無線傳感網(wǎng)絡，使人們能準確而及時地掌握險情的發(fā)展情況，為有效地搶先救災創(chuàng)造有利條件?？萍嫉难杆侔l(fā)展使人們可以制造不太昂貴且具有通訊功能的監(jiān)視裝置。放置在同一監(jiān)視區(qū)域內(nèi)的這種監(jiān)視裝置（以下簡稱為節(jié)點）構(gòu)成一個無線傳感網(wǎng)絡。如果監(jiān)視區(qū)域的任意一點都處于放置在該區(qū)域內(nèi)某一節(jié)點的監(jiān)視范圍內(nèi)，則稱節(jié)點能覆蓋該監(jiān)視區(qū)域。研究能確保有效覆蓋且數(shù)量最少的節(jié)點放置問題顯然具有重要意義。1.2問題的重述圖1 無線傳感網(wǎng)絡覆蓋示意圖圖1中，叉形表示一個無線傳感網(wǎng)絡節(jié)點，虛線的圓形區(qū)域表示該節(jié)點的覆蓋范圍。可見，該無線傳感網(wǎng)絡節(jié)點完全覆蓋了區(qū)域B，部分覆蓋了區(qū)域A。網(wǎng)絡節(jié)點間的通信設計問題是無線傳感器網(wǎng)絡設計的重要問題之一。如前所述，每個節(jié)點都有一定的覆蓋范圍，節(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：在一個監(jiān)視區(qū)域為邊長b=100(長度單位)的正方形中，每個節(jié)點的覆蓋半徑均為r=10(長度單位)。在設計傳感網(wǎng)絡時，需要知道對給定監(jiān)視區(qū)域在一定的覆蓋保證下應放置節(jié)點的最少數(shù)量。對于上述給定的監(jiān)視區(qū)域及覆蓋半徑，確定至少需要放置多少個節(jié)點，才能使得成功覆蓋整個區(qū)域的概率在95%以上？問題2：在1所給的條件下，已知在該監(jiān)視區(qū)域內(nèi)放置了120個節(jié)點，它們位置的橫、縱坐標如表1所示。請設計一種節(jié)點間的通信模型，給出任意10組兩節(jié)點之間的通信通路，比如節(jié)點1與節(jié)點90如何通信等。二、 問題的分析根據(jù)查詢的相關(guān)資料，無線傳感網(wǎng)絡設計中的節(jié)點放置和節(jié)點間通信問題是近今年的熱門課題。由于地理條件的復雜，一般情況下無線傳感網(wǎng)絡設計中的節(jié)點只能采用非均勻投放的方法。鑒于此，本文對題目中的問題做了如下分析：針對問題一：由于安放節(jié)點是隨機的，某事件發(fā)生的概率可以用多次實驗中該事件發(fā)生的頻率代替,而兩者均可用計算機仿真實現(xiàn)，因此可通過計算機不斷產(chǎn)生隨機數(shù)模擬節(jié)點安放和監(jiān)視區(qū)域各點被覆蓋的情況，再以題目中95%為約束，找出最優(yōu)節(jié)點數(shù)。針對問題二：對于該問題，根據(jù)題目中所給的120個節(jié)點的坐標，很容易求出各節(jié)點間的距離，由題設可知，一個節(jié)點不在另一個節(jié)點覆蓋的范圍之內(nèi)，則兩節(jié)點間不能直接通信，要通過其它節(jié)點間接通信。在通過其它節(jié)點實現(xiàn)間接通信的過程中，肯定會產(chǎn)生不同的通信通路，本文要做的是找出任意兩點間的最優(yōu)通信通路。這很容易讓人聯(lián)想到圖論模型最短路徑的求法，于是可根據(jù)題設限制條件，將各點間的距離矩陣轉(zhuǎn)化為帶權(quán)鄰接矩陣，通過matlab軟件求解出各點間的最優(yōu)通信通路。三、 模型假設1、 各節(jié)點的覆蓋范圍相同且穩(wěn)定，不受天氣及電磁干擾；2、 任何節(jié)點與其覆蓋范圍內(nèi)的節(jié)點間的通信強度相同；3、 節(jié)點間的通信距離與通信所用的時長成正比。四、 符號及變量說明：每次仿真隨機產(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中所給120個點之間的帶權(quán)鄰接矩陣；：第i個節(jié)點域其他節(jié)點距離的最小值（i=1,2n）；五、 模型的建立和求解5.1對于問題一的模型建立和求解查閱相關(guān)文獻得知，無線傳感網(wǎng)絡中的節(jié)點安放是非均勻的，本文建立仿真模型，通過計算機在監(jiān)視區(qū)域內(nèi)隨機產(chǎn)生n個節(jié)點來模擬節(jié)點的非均勻安放根據(jù)概率論知識：當試驗次數(shù)足夠大時，可以近似認為事件發(fā)生的頻率等于其概率，于是可通過計算機在已將安放好節(jié)點的監(jiān)視區(qū)域內(nèi)隨機產(chǎn)生N個檢驗點，并求出這N個點與各節(jié)點間的距離 然后選出每個檢驗點與n個節(jié)點的距離最小值，根據(jù)題設節(jié)點間的通信條件，將與覆蓋半徑r比較，對于所有的i=1,2N(N取足夠大) ，若滿足 r則可以認為這n個節(jié)點組成的無線通信網(wǎng)絡可以成功將監(jiān)視區(qū)域覆蓋，否則則認為沒有成功覆蓋。對上述過程進行T次仿真,統(tǒng)計能成功覆蓋整個監(jiān)視區(qū)域次數(shù)t，并計算出相應的頻率f,當T取足夠大時，可以認為這n個節(jié)點能成功覆蓋整個監(jiān)視區(qū)域的概率根據(jù)題目要求，比較p與95%的大小若則增大n值；反之則減小n值，再重復上述仿真過程，直至找出時的最小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ù)到了嗎？ 本文仿真程序相應的參數(shù)為：T=1000 N=20000（詳見附錄二第一題程序），通過不斷手動調(diào)整n的大小，最后找出能成功覆蓋整個區(qū)域的概率在95%以上的最少節(jié)點數(shù)為565個。5.2對于問題二模型的建立和求解根據(jù)題意，兩節(jié)點間能直接相互通信的條件為r時，則該節(jié)點與其他節(jié)點不能實現(xiàn)通信，應該講該節(jié)點剔除。修改后測程序見附表二。講過修改后，得到能成功覆蓋整個區(qū)域的概率在95%以上的最少節(jié)點數(shù)為571個。七、 模型的推廣和應用本文所建立的仿真模型，用到了隨機抽取和循環(huán)迭代思想，可廣泛應用于估計某些事件可能發(fā)生的概率。本文建立的圖論模型也可廣泛應用到無線設備比如手機的信號傳遞路徑選取上。參考文獻：1陶丹，馬華東，劉亮 無線傳感器網(wǎng)絡節(jié)點部署問題研究,北京 1008762茆詩松，程依明，濮曉龍.概率論與數(shù)理統(tǒng)計教程M.北京：高等教育出版社.2009；3劉衛(wèi)國 主編 MATLAB程序設計教程 (第二版)M. 水利水電出版社出版社.2010；附錄一：120個節(jié)點的坐標表節(jié)點標號XY節(jié)點標號XY節(jié)點標號XY節(jié)點標號XY1575831633613295917444295743285962477192412533412336437635043933921431683422136456439495515526735694365562595727663043680836647259679871575377613678064977844875523888946810969810809753039259569123399889106528406245706370100159511556341707071399101459012416142454272818910270821336204335973431410390781472244475417417251048478151610453591758055105207016854946563076456110640711786904727927792401075570187590489290787822108595193220492558798945109731820592504452805151110222821163551580814090111178022256652173382654911250102372453905837671135520246833542574843098114872225613555584785263411572982637785695286289911655792748465787728725811772288131586888882963118852029239059302889408311935503035666099904111201068附錄三：第一題程序clcclearn=565; %設定n個節(jié)點T=1000; %隨機設定節(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ū)域內(nèi)隨機產(chǎn)生n個節(jié)點 A(i)=100*rand; %橫坐標 B(i)=100*rand; %縱坐標end for i=1:N %在監(jiān)視區(qū)域內(nèi)隨機取N個點看其是否被覆蓋 x=100*rand; %橫坐標 y=100*rand; %縱坐標 for i=1:n d(i)=sqrt(x-A(i).2+(y-B(i).2); %計算該點與n個節(jié)點的距離 end if min(d)10 %將距離矩陣轉(zhuǎn)化為帶權(quán)鄰接矩陣 d(i,j)=inf; end endend dis, path=dijkstraf(d, 1, 5) %調(diào)用Dijkstraf算法第一題改進后的程序clcclearn=565; %設定n個節(jié)點t=500; %隨機設定節(jié)點的次數(shù)N=5000; %檢驗覆蓋率的仿真次數(shù)r=10; %覆蓋半徑f=0; %被完全覆蓋次數(shù)for i=1:t m=0; %覆蓋的點的個數(shù)，每次循環(huán)初始化為零 Q=0; %區(qū)域覆蓋率，每次循環(huán)初始化為零for i=1:n %在監(jiān)視區(qū)域內(nèi)隨機產(chǎn)生n個節(jié)點 A(i)=100*rand; %橫坐標 B(i)=100*rand; %縱坐標endfor i=1:n %剔除不能與其他節(jié)點相互通信的節(jié)點 for j=1:n d(i,j)=sqrt(A(i)-A(j).2+(B(i)-B(j)2); if d(i,j)=0 d(i,j)=inf; end endendL=min(d);for i=1:n if L(i)10 A(i)=inf; B(i)=in