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

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

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

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

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

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

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

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

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

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

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

12、驟如下：Step1：求出120點兩兩之間的距離矩陣 ；Step2：將D中大于r的元素變為，將距離矩陣D轉化為帶權鄰接矩陣 ；Step3：采用Dijkstraf算法，將W帶入其中，計算出任意給定兩節點間的最優通信通路。所得的十組節點間的最優通信通路如表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六、 模型的評價和改進6.1模型的評價6.1.1優點1 對于問題1本文在題目信息和查閱相關資料的基礎上，用計算機仿真法模擬無線網絡節點的不規則放置和檢驗無線網絡的覆蓋率，充分利用計算機的優勢，化繁為簡，以頻率代替概率，得出的結論可信度高。2 在仿真過程中，對重要參數調整問題，本文采用手動調整法，這樣可以避免計算機仿真次數過多，程序運行時間過長的問題，既可以節省時間又可以較準確判斷最理想的n值。3 求解問題2時，本文在考慮通信的時效性

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

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

16、節點標號XY節點標號XY節點標號XY節點標號XY157583163361329591744429574328596247719241253341233643763504393392143168342213645643949551552673569436556259572766304368083664725967987157537761367806497784487552388894681096981080975303925956912339988910652840624570637010015951155634170707139910145901241614245427281891027082

17、133620433597343141039078147224447541741725104847815161045359175805510520701685494656307645611064071178690472792779240107557018759048929078782210859519322049255879894510973182059250445280515111022282116355158081409011117802225665217338265491125010237245390583767113552024683354257484309811487222561355

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

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