無線傳感器網(wǎng)絡(luò)

1、第一次個(gè)人賽論文 姓名代碼：89無線傳感網(wǎng)絡(luò)設(shè)計(jì)問題摘要本文通過研究無線傳感網(wǎng)絡(luò)的覆蓋問題和節(jié)點(diǎn)的通信模型設(shè)計(jì)，建立無線傳感網(wǎng)絡(luò)，可以準(zhǔn)確而及時(shí)地掌握險(xiǎn)情的發(fā)展情況。針對(duì)問題一，在給定區(qū)域面積和節(jié)點(diǎn)覆蓋半徑，且要求必須覆蓋整個(gè)區(qū)域的前提下，通過隨機(jī)模擬確定最少的節(jié)點(diǎn)數(shù)。首先通過蜂窩網(wǎng)格法，分析得到理論上覆蓋整個(gè)區(qū)域所需最少的節(jié)點(diǎn)數(shù)為45個(gè)。然后通過軟件在監(jiān)視區(qū)域內(nèi)產(chǎn)生N個(gè)隨機(jī)測(cè)試點(diǎn)，再產(chǎn)生隨機(jī)均勻分布的M個(gè)節(jié)點(diǎn)，觀察這些節(jié)點(diǎn)圓是否已完全覆蓋這些測(cè)試點(diǎn)，并保證覆蓋整個(gè)區(qū)域的概率在95%以上,利用matlab通過500次模擬得到。考慮到隨機(jī)產(chǎn)生的測(cè)試點(diǎn)不穩(wěn)定，可以做進(jìn)一步優(yōu)化，使得這些測(cè)試點(diǎn)完全轉(zhuǎn)

2、化為區(qū)域內(nèi)的固定點(diǎn)，當(dāng)各點(diǎn)間隔趨于無窮小時(shí)，便可均勻覆蓋整個(gè)區(qū)域，再分析節(jié)點(diǎn)圓覆蓋整個(gè)區(qū)域的概率。通過對(duì)這兩種方法進(jìn)行對(duì)比，得出后者更優(yōu)，最后確定至少為535個(gè)。針對(duì)問題二，設(shè)計(jì)了兩種節(jié)點(diǎn)間的相互通信模型。已知每個(gè)節(jié)點(diǎn)覆蓋半徑，且節(jié)點(diǎn)只能與覆蓋范圍內(nèi)的節(jié)點(diǎn)進(jìn)行通信，即兩節(jié)點(diǎn)之間的距離要小于半徑。方法一把能相互通信的點(diǎn)連線，可以得到節(jié)點(diǎn)間的通信路徑圖，通過該圖可以找出任意兩個(gè)節(jié)點(diǎn)間的通信路徑，并給出了十組任意節(jié)點(diǎn)之間的通路。方法二在節(jié)點(diǎn)通信路徑圖的基礎(chǔ)上進(jìn)行優(yōu)化，通過Dijkstra算法求最短路徑，準(zhǔn)確快速實(shí)現(xiàn)任意兩個(gè)節(jié)點(diǎn)之間的最短通路及最距離大小。通過對(duì)這兩種方法的對(duì)比分析，可知方法一通信路徑

3、并不唯一，對(duì)于距離較短，節(jié)點(diǎn)少時(shí)，簡(jiǎn)單易用，但當(dāng)通信距離較大、節(jié)點(diǎn)多時(shí)，不易觀察，且計(jì)算路徑繁瑣。方法二計(jì)算準(zhǔn)確快速，適用性更廣。因此，Dijkstra算法更適用于大范圍的無線傳感網(wǎng)絡(luò)設(shè)計(jì)。最后，本文對(duì)采用的模型方法進(jìn)行了分析，并提出了適當(dāng)?shù)母倪M(jìn)方案。關(guān)鍵詞：隨機(jī)模擬；節(jié)點(diǎn)通信；Dijkstra算法一、 問題的提出和重述1.1問題的提出大氣污染所引起的地球氣候異常，導(dǎo)致地震、旱災(zāi)等自然災(zāi)害頻頻發(fā)生，給人民的生命財(cái)產(chǎn)造成巨大損失。因此，研究如何有效監(jiān)測(cè)自然災(zāi)害的措施十分必要。在容易出現(xiàn)自然災(zāi)害的重點(diǎn)地區(qū)放置高科技的監(jiān)視裝置，建立無線傳感網(wǎng)絡(luò)，使人們能準(zhǔn)確而及時(shí)地掌握險(xiǎn)情的發(fā)展情況。如果監(jiān)視區(qū)域的

4、任意一點(diǎn)都處于放置在該區(qū)域內(nèi)某一節(jié)點(diǎn)的監(jiān)視范圍內(nèi)，則稱節(jié)點(diǎn)能覆蓋該監(jiān)視區(qū)域。研究能確保有效覆蓋且數(shù)量最少的節(jié)點(diǎn)放置問題顯然具有重要意義。圖1 無線傳感網(wǎng)絡(luò)覆蓋示意圖如圖1所示，叉形表示一個(gè)無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)，虛線的圓形區(qū)域表示該節(jié)點(diǎn)的覆蓋范圍。該無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)完全覆蓋了區(qū)域B，部分覆蓋了區(qū)域A。網(wǎng)絡(luò)節(jié)點(diǎn)間的通信設(shè)計(jì)問題是無線傳感器網(wǎng)絡(luò)設(shè)計(jì)的重要問題之一。節(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ǎ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

5、，再通過B傳給C，行成一個(gè)ABC的通路。1.2問題的重述查找相關(guān)資料，建立數(shù)學(xué)模型解決以下兩個(gè)問題：1、在一個(gè)監(jiān)視區(qū)域?yàn)檫呴L(zhǎng)b=100(長(zhǎng)度單位)的正方形中，每個(gè)節(jié)點(diǎn)的覆蓋半徑均為r=10(長(zhǎng)度單位)。對(duì)于上述給定的監(jiān)視區(qū)域及覆蓋半徑，確定至少需要放置多少個(gè)節(jié)點(diǎn)，才能使得成功覆蓋整個(gè)區(qū)域的概率在95%以上？2、在1所給的條件下，已知在該監(jiān)視區(qū)域內(nèi)放置了120個(gè)節(jié)點(diǎn)，它們的橫、縱坐標(biāo)如附表1所示。設(shè)計(jì)一種節(jié)點(diǎn)間的相互通信模型，并給出任意10組兩節(jié)點(diǎn)之間的通信通路。二、 問題的分析通過建立無線傳感網(wǎng)絡(luò)，可以準(zhǔn)確而及時(shí)地掌握險(xiǎn)情的發(fā)展情況。因此，本文研究的是傳感網(wǎng)絡(luò)的覆蓋問題，確定設(shè)置多少個(gè)節(jié)點(diǎn)使得

6、成功覆蓋概率達(dá)95%，同時(shí)設(shè)計(jì)一個(gè)合理有效的節(jié)點(diǎn)通信模型，使得整個(gè)無線傳感網(wǎng)絡(luò)可以準(zhǔn)確快速通信，且經(jīng)濟(jì)實(shí)用。針對(duì)問題一，在給定區(qū)域面積和節(jié)點(diǎn)覆蓋半徑的前提下，需要確定至少需要放置多少個(gè)節(jié)點(diǎn)，才能使得成功覆蓋整個(gè)區(qū)域的概率在95%以上。在必須覆蓋整個(gè)區(qū)域的要求下，可以通過仿真模擬來確定最少的節(jié)點(diǎn)數(shù)，并計(jì)算覆蓋效率（覆蓋效率越大越經(jīng)濟(jì)）。首先通過蜂窩網(wǎng)格法1，可以分析理論上覆蓋整個(gè)區(qū)域所需最少的節(jié)點(diǎn)數(shù)。通過蒙特卡洛模擬編程2實(shí)現(xiàn)，在監(jiān)視區(qū)域內(nèi)產(chǎn)生隨機(jī)均勻分布的N個(gè)測(cè)試點(diǎn)，再產(chǎn)生隨機(jī)均勻分布的M個(gè)節(jié)點(diǎn)，觀察這些節(jié)點(diǎn)是否已完全覆蓋這些測(cè)試點(diǎn)，并進(jìn)行多次模擬，保證覆蓋整個(gè)區(qū)域的概率在95%以上?？紤]到隨

7、機(jī)產(chǎn)生的測(cè)試點(diǎn)不穩(wěn)定，我們可以進(jìn)一步優(yōu)化，使得這些測(cè)試點(diǎn)轉(zhuǎn)化為區(qū)域內(nèi)的固定點(diǎn)，各點(diǎn)間隔趨于無窮小時(shí)，便可均勻覆蓋整個(gè)區(qū)域，再分析節(jié)點(diǎn)覆蓋整個(gè)區(qū)域的概率。針對(duì)問題二，設(shè)計(jì)一種節(jié)點(diǎn)間的相互通信模型。已知每個(gè)節(jié)點(diǎn)都有一定的覆蓋范圍，根據(jù)節(jié)點(diǎn)只能與覆蓋范圍內(nèi)的節(jié)點(diǎn)進(jìn)行通信，即兩節(jié)點(diǎn)之間的距離要小于半徑，把能相互通信的點(diǎn)連線，可以得到節(jié)點(diǎn)間的通信路徑圖，通過該圖可以找出任意兩個(gè)節(jié)點(diǎn)間的通信路徑。但此方法當(dāng)通信距離較大、節(jié)點(diǎn)多時(shí)，不易觀察，且手工計(jì)算路徑繁瑣。因此，在節(jié)點(diǎn)通信路徑圖的基礎(chǔ)上進(jìn)行優(yōu)化，通過Dijkstra算法（以下簡(jiǎn)稱D算法）可以準(zhǔn)確快速實(shí)現(xiàn)任意兩個(gè)節(jié)點(diǎn)之間的最短通路及最短路徑大小，比如節(jié)點(diǎn)

8、5到其余任何點(diǎn)的最短通路。三、 模型假設(shè)1、 節(jié)點(diǎn)裝置在監(jiān)視區(qū)域內(nèi)是呈均勻分布隨機(jī)放置的。2、 定義覆蓋效率為監(jiān)視區(qū)域除以各節(jié)點(diǎn)能覆蓋的面積總和；3、 不考慮節(jié)點(diǎn)周圍環(huán)境對(duì)通信范圍的影響。4、 假設(shè)在兩個(gè)節(jié)點(diǎn)覆蓋圓臨界位置（相切處）不可通信。四、 符號(hào)及變量說明:隨機(jī)測(cè)試點(diǎn)數(shù)；:節(jié)點(diǎn)數(shù)； :隨機(jī)模擬次數(shù)；:覆蓋整個(gè)區(qū)域的概率；: 覆蓋效率；：正方形小網(wǎng)格邊長(zhǎng)；五、 模型的建立和求解5.1針對(duì)問題一的求解5.1.1理論最少節(jié)點(diǎn)數(shù)的求解 根據(jù)數(shù)學(xué)定理：如果3個(gè)半徑相同的圓兩兩相交，且覆蓋面積最大，則三圓相交于一點(diǎn)，且三個(gè)圓心圍成等邊三角形。如圖（1）所示，根據(jù)此定理，在的監(jiān)視范圍內(nèi)平鋪，利用CAD

9、畫圖得到圖（2）。圖（1） 圖（）在此平鋪狀態(tài)下，即為蜂窩網(wǎng)格法，得到最少的節(jié)點(diǎn)數(shù)為45個(gè)，其覆蓋效率為。此狀態(tài)在隨機(jī)模擬下出現(xiàn)的概率幾乎為零，因此要使成功覆蓋整個(gè)區(qū)域的概率在95%以上，節(jié)點(diǎn)數(shù)遠(yuǎn)大于45個(gè)。5.1.2 隨機(jī)測(cè)試點(diǎn)求最少節(jié)點(diǎn)數(shù)通過在監(jiān)視區(qū)域內(nèi)產(chǎn)生個(gè)均勻分布隨機(jī)測(cè)試點(diǎn)，再往監(jiān)視區(qū)域內(nèi)隨機(jī)放置個(gè)節(jié)點(diǎn)，若這個(gè)節(jié)點(diǎn)能完全覆蓋這個(gè)測(cè)試點(diǎn)，則認(rèn)為該區(qū)域被完全覆蓋，通過次模擬，保證覆蓋整個(gè)區(qū)域的次數(shù)至少為，以此求得最小的值。通過編程實(shí)現(xiàn)模擬500次，得到表（）和圖（），并解得當(dāng)時(shí)，左右。由表（）可以看出值與值并不成比例關(guān)系，值不穩(wěn)定，難以確定具體為多少時(shí)，概率，因此，該方法仍有待進(jìn)一步優(yōu)化。

10、N530531532533534535536537538539P0.94330.92670.93000.96330.93670.93330.95670.94670.96000.9533表（）十組值對(duì)應(yīng)的值 圖（）隨機(jī)測(cè)試點(diǎn)模擬圖5.1.3 固定測(cè)試點(diǎn)求最少節(jié)點(diǎn)數(shù) 對(duì)于的覆蓋區(qū)域，分成面積為的正方形小網(wǎng)格，并賦予每個(gè)小網(wǎng)格為0值，當(dāng)時(shí)，每個(gè)小網(wǎng)格趨向于點(diǎn)，網(wǎng)格數(shù)也就越多。為便于計(jì)算，這里取1，以網(wǎng)格中心點(diǎn)代表整個(gè)網(wǎng)格，當(dāng)該中心點(diǎn)到隨機(jī)分布的任意一個(gè)節(jié)點(diǎn)的距離小于半徑時(shí)，網(wǎng)格被賦值為1。按此循環(huán)，當(dāng)每個(gè)網(wǎng)格均被賦值為1時(shí)，即表示節(jié)點(diǎn)覆蓋了整個(gè)區(qū)域，達(dá)到要求。通過matlab編程模擬500次，得到表

11、（2）和圖（4）。通過對(duì)表（1）與表（2）的對(duì)比分析可知，值更為穩(wěn)定，通過線性擬合圖（5）也可知用固定點(diǎn)模擬的方法更好。綜上，在一定范圍內(nèi)，得出在時(shí)，符合要求。N530531532533534535536537538539P0.94170.93330.93000.94330.94270.95000.95000.95370.97330.9667表（2）十組值對(duì)應(yīng)的值 圖（4）固定測(cè)試點(diǎn)模擬圖圖（5）兩種方法線性擬合對(duì)比圖5.2針對(duì)問題二的求解5.2.1 可通信節(jié)點(diǎn)路徑分布圖的設(shè)計(jì)已知每個(gè)節(jié)點(diǎn)都有一定的覆蓋范圍（），節(jié)點(diǎn)只能與覆蓋范圍之內(nèi)的節(jié)點(diǎn)進(jìn)行通信，任意兩個(gè)節(jié)點(diǎn)之間的歐式距離可表示為：所以當(dāng)?shù)?/p>

12、兩個(gè)節(jié)點(diǎn)之間才可以進(jìn)行通信，因此，通過matlab編程（附錄程序三）將120節(jié)點(diǎn)中所有的兩節(jié)點(diǎn)之間用直線連接，得到節(jié)點(diǎn)通信路徑圖，如圖（6）所示：圖（6）節(jié)點(diǎn)通信路徑圖通過觀察此節(jié)點(diǎn)通信圖，可以知道任意兩節(jié)點(diǎn)之間的通信通路，任取10組節(jié)點(diǎn)，找出其通信路徑，并計(jì)算其通信距離，如下表（3）所示，并通過圖（7）可直接觀測(cè)其通信通路：序號(hào)起始節(jié)點(diǎn)終止節(jié)點(diǎn) 通信路徑 通信距離16087 601587 16.292673 64373 16.5139310 93666510 27.434 14 28 14928 12.795816 87516 13.6468012 805512 16.5674118 419

13、510818 20.0886211 62511 11.40949106 498830106 20.18109954 9998710554 29.76表（3）：10個(gè)任意節(jié)點(diǎn)的通信路徑及通信距離圖（7）：上述10個(gè)節(jié)點(diǎn)的通路圖通過直接觀測(cè)通信圖，可知通信路徑并不唯一，對(duì)于距離較短，節(jié)點(diǎn)少時(shí)，簡(jiǎn)單易用，但是當(dāng)通信距離較大、節(jié)點(diǎn)多時(shí)，則不易觀察，且計(jì)算繁瑣，不宜采用。因此下面通過適當(dāng)算法來更準(zhǔn)確快速實(shí)現(xiàn)通信圖的設(shè)計(jì)。5.2.1 Dijkstra算法通信路徑的設(shè)計(jì)D算法思路3：采用標(biāo)號(hào)作業(yè)法,每次迭代產(chǎn)生一個(gè)永久標(biāo)號(hào), 從而生長(zhǎng)一顆以為根的最短路樹,在這顆樹上每個(gè)頂點(diǎn)與根節(jié)點(diǎn)之間的路徑皆為最短路徑。該

14、算法核心是求得鄰階矩陣，計(jì)算某點(diǎn)到其余點(diǎn)的距離，若其余某點(diǎn)在該點(diǎn)的通信范圍內(nèi)，則。反之，。本文可以得到一個(gè)鄰階矩陣，調(diào)用D算法程序，實(shí)現(xiàn)通信路徑及距離的計(jì)算。為方便比較，仍取上述表（3）中的起始節(jié)點(diǎn)和終止節(jié)點(diǎn)，通過matlab編程得到圖（8）D算法最短通信路徑及距離分布圖圖（8）D算法最短通信路徑及距離分布圖通過圖（7）和圖（8）的對(duì)比分析，其通信路徑及距離是完全吻合的，但用D算法明顯更為優(yōu)越，能夠快速準(zhǔn)確地給出任意兩節(jié)點(diǎn)之間的最短通信路徑以及此時(shí)的最短通信距離，且誤差很小。六、 模型的評(píng)價(jià)和改進(jìn)6.1模型的評(píng)價(jià)6.1.1優(yōu)點(diǎn)(1)本文通過多次模擬來求解全部覆蓋的概率，方法實(shí)用簡(jiǎn)單，容易編程實(shí)

15、現(xiàn)。(2)運(yùn)用D算法求解最短通信路徑和距離時(shí)，準(zhǔn)確快速可靠，且容易編程實(shí)現(xiàn)，易于推廣。 （3）通過對(duì)覆蓋效率的計(jì)算，便于經(jīng)濟(jì)、實(shí)用方面的分析。6.1.2缺點(diǎn)(1) 通過隨機(jī)模擬不可避免會(huì)有誤差，若模擬次數(shù)不夠多，造成的誤差也大。每次的模擬會(huì)有不同的在微小范圍內(nèi)浮動(dòng)值。(2) 軟件編程時(shí)計(jì)算量大，運(yùn)算時(shí)間長(zhǎng)。6.2模型的改進(jìn)從第一問的覆蓋效率可知，效率偏低，因此十分有必要提高其覆蓋效率，可以對(duì)覆蓋區(qū)域進(jìn)行全面了解后，通過精確計(jì)算確定各個(gè)節(jié)點(diǎn)位置，減少隨機(jī)模擬的誤差，對(duì)于重復(fù)覆蓋頻率高的地區(qū)減少節(jié)點(diǎn)數(shù)，對(duì)于重復(fù)覆蓋頻率很低的地區(qū)增加節(jié)點(diǎn)數(shù)，使其均勻化，從而增加了覆蓋效率，也更加經(jīng)濟(jì)。七、 模型的推

16、廣和應(yīng)用 本文對(duì)研究無線傳感網(wǎng)絡(luò)的覆蓋問題和節(jié)點(diǎn)的通信模型設(shè)計(jì)進(jìn)行了討論，建立無線傳感網(wǎng)絡(luò)，可以準(zhǔn)確而及時(shí)地掌握險(xiǎn)情的發(fā)展情況，在森林防火、災(zāi)區(qū)空投物資、戰(zhàn)場(chǎng)空投等方面都具有一定的指導(dǎo)作用。參考文獻(xiàn)：1陸克中、毛睿等 基于蜂窩結(jié)構(gòu)的傳感器網(wǎng)絡(luò)覆蓋問題求解算法 計(jì)算機(jī)研究與發(fā)展學(xué)報(bào) 第3期：80-84，2012；2薛山 MATLAB基礎(chǔ)教程 清華大學(xué)出版社 2011-03-01;3Dijkstra最短路徑算法（百度文庫(kù)）鏈接:附錄： 附表1 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)XY15758316336132959174442957432859624771924125

17、334123364376350439339214316834221364564394955155267356943655625957276630436808366472596798715753776136780649778448755238889468109698108097530392595691233998891065284062457063701001595115563417070713991014590124161424542728189102708213362043359734314103907814722444754174172510484781516104535917580551

18、052070168549465630764561106407117869047279277924010755701875904892907878221085951932204925587989451097318205925044528051511102228211635515808140901111780222566521733826549112501023724539058376711355202468335425748430981148722256135555847852634115729826377856952862899116557927484657877287258117722881

19、31586888882963118852029239059302889408311935503035666099904111201068%程序（一）：隨機(jī)模擬覆蓋的概率clearclcfor n=530:540;%設(shè)置節(jié)點(diǎn)數(shù)T=10000;m=0;for k=1:500 %模擬次數(shù)x=100*rand(n,1); %產(chǎn)生n個(gè)圓心坐標(biāo)y=100*rand(n,1);p=0;c=0;for i=1:T x0=100*rand; %產(chǎn)生T個(gè)隨機(jī)點(diǎn)坐標(biāo) y0=100*rand; for j=1:n if (x0-x(j)2+(y0-y(j)2<100 p=p+1; break; end end

20、end if p=T %已全部覆蓋 m=m+1; endendc=m/300c=0;end%程序（二）：固定點(diǎn)覆蓋的概率%clearclcm=0;h=1;%間隔c=100;K=500;%模擬次數(shù)P=0;%覆蓋率%產(chǎn)生c*c個(gè)固定點(diǎn)坐標(biāo)，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個(gè)節(jié)點(diǎn)圓

21、心坐標(biāo) 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);%