無(wú)線傳感網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題.doc

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