《無線傳感器網(wǎng)絡(luò)》word版.doc

《《無線傳感器網(wǎng)絡(luò)》word版.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《《無線傳感器網(wǎng)絡(luò)》word版.doc（14頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

第一次個(gè)人賽論文 姓名代碼：89 無線傳感網(wǎng)絡(luò)設(shè)計(jì)問題 摘要 本文通過研究無線傳感網(wǎng)絡(luò)的覆蓋問題和節(jié)點(diǎn)的通信模型設(shè)計(jì)，建立無線傳感網(wǎng)絡(luò)，可以準(zhǔn)確而及時(shí)地掌握險(xiǎn)情的發(fā)展情況。 針對問題一，在給定區(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ī)測試點(diǎn)，再產(chǎn)生隨機(jī)均勻分布的M個(gè)節(jié)點(diǎn)，觀察這些節(jié)點(diǎn)圓是否已完全覆蓋這些測試點(diǎn)，并保證覆蓋整個(gè)區(qū)域的概率在95%以上,利用matlab通過500次模擬得到?？紤]到隨機(jī)產(chǎn)生的測試點(diǎn)不穩(wěn)定，可以做進(jìn)一步優(yōu)化，使得這些測試點(diǎn)完全轉(zhuǎn)化為區(qū)域內(nèi)的固定點(diǎn)，當(dāng)各點(diǎn)間隔趨于無窮小時(shí)，便可均勻覆蓋整個(gè)區(qū)域，再分析節(jié)點(diǎn)圓覆蓋整個(gè)區(qū)域的概率。通過對這兩種方法進(jìn)行對比，得出后者更優(yōu)，最后確定至少為535個(gè)。 針對問題二，設(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)之間的最短通路及最距離大小。通過對這兩種方法的對比分析，可知方法一通信路徑并不唯一，對于距離較短，節(jié)點(diǎn)少時(shí)，簡單易用，但當(dāng)通信距離較大、節(jié)點(diǎn)多時(shí)，不易觀察，且計(jì)算路徑繁瑣。方法二計(jì)算準(zhǔn)確快速，適用性更廣。因此，Dijkstra算法更適用于大范圍的無線傳感網(wǎng)絡(luò)設(shè)計(jì)。 最后，本文對采用的模型方法進(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)測自然災(zāi)害的措施十分必要。在容易出現(xiàn)自然災(zāi)害的重點(diǎn)地區(qū)放置高科技的監(jiān)視裝置，建立無線傳感網(wǎng)絡(luò)，使人們能準(zhǔn)確而及時(shí)地掌握險(xiǎn)情的發(fā)展情況。 如果監(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)放置問題顯然具有重要意義。 圖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，再通過B傳給C，行成一個(gè)A－B－C的通路。 1.2問題的重述 查找相關(guān)資料，建立數(shù)學(xué)模型解決以下兩個(gè)問題： 1、在一個(gè)監(jiān)視區(qū)域?yàn)檫呴Lb=100(長度單位)的正方形中，每個(gè)節(jié)點(diǎn)的覆蓋半徑均為r=10(長度單位)。對于上述給定的監(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)使得成功覆蓋概率達(dá)95%，同時(shí)設(shè)計(jì)一個(gè)合理有效的節(jié)點(diǎn)通信模型，使得整個(gè)無線傳感網(wǎng)絡(luò)可以準(zhǔn)確快速通信，且經(jīng)濟(jì)實(shí)用。 針對問題一，在給定區(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è)測試點(diǎn)，再產(chǎn)生隨機(jī)均勻分布的M個(gè)節(jié)點(diǎn)，觀察這些節(jié)點(diǎn)是否已完全覆蓋這些測試點(diǎn)，并進(jìn)行多次模擬，保證覆蓋整個(gè)區(qū)域的概率在95%以上。考慮到隨機(jī)產(chǎn)生的測試點(diǎn)不穩(wěn)定，我們可以進(jìn)一步優(yōu)化，使得這些測試點(diǎn)轉(zhuǎn)化為區(qū)域內(nèi)的固定點(diǎn)，各點(diǎn)間隔趨于無窮小時(shí)，便可均勻覆蓋整個(gè)區(qū)域，再分析節(jié)點(diǎn)覆蓋整個(gè)區(qū)域的概率。 針對問題二，設(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算法（以下簡稱D算法）可以準(zhǔn)確快速實(shí)現(xiàn)任意兩個(gè)節(jié)點(diǎn)之間的最短通路及最短路徑大小，比如節(jié)點(diǎn)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)境對通信范圍的影響。 4、 假設(shè)在兩個(gè)節(jié)點(diǎn)覆蓋圓臨界位置（相切處）不可通信。 四、 符號(hào)及變量說明 :隨機(jī)測試點(diǎn)數(shù)； :節(jié)點(diǎn)數(shù)； :隨機(jī)模擬次數(shù)； :覆蓋整個(gè)區(qū)域的概率； : 覆蓋效率； ：正方形小網(wǎng)格邊長； 五、 模型的建立和求解 5.1針對問題一的求解 5.1.1理論最少節(jié)點(diǎn)數(shù)的求解 根據(jù)數(shù)學(xué)定理：如果3個(gè)半徑相同的圓兩兩相交，且覆蓋面積最大，則三圓相交于一點(diǎn)，且三個(gè)圓心圍成等邊三角形。如圖（1）所示，根據(jù)此定理，在的監(jiān)視范圍內(nèi)平鋪，利用CAD畫圖得到圖（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ī)測試點(diǎn)求最少節(jié)點(diǎn)數(shù) 通過在監(jiān)視區(qū)域內(nèi)產(chǎn)生個(gè)均勻分布隨機(jī)測試點(diǎn)，再往監(jiān)視區(qū)域內(nèi)隨機(jī)放置個(gè)節(jié)點(diǎn)，若這個(gè)節(jié)點(diǎn)能完全覆蓋這個(gè)測試點(diǎn)，則認(rèn)為該區(qū)域被完全覆蓋，通過次模擬，保證覆蓋整個(gè)區(qū)域的次數(shù)至少為，以此求得最小的Ｍ值。 通過編程實(shí)現(xiàn)模擬500次，得到表（１）和圖（３），并解得當(dāng)時(shí)，左右。由表（１）可以看出Ｎ值與Ｐ值并不成比例關(guān)系，值不穩(wěn)定，難以確定具體Ｎ為多少時(shí)，概率，因此，該方法仍有待進(jìn)一步優(yōu)化。 N 530 531 532 533 534 535 536 537 538 539 P 0.9433 0.9267 0.9300 0.9633 0.9367 0.9333 0.9567 0.9467 0.9600 0.9533 表（１）十組值對應(yīng)的值 圖（３）隨機(jī)測試點(diǎn)模擬圖 5.1.3 固定測試點(diǎn)求最少節(jié)點(diǎn)數(shù) 對于的覆蓋區(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次，得到表（2）和圖（4）。通過對表（1）與表（2）的對比分析可知，值更為穩(wěn)定，通過線性擬合圖（5）也可知用固定點(diǎn)模擬的方法更好。 綜上，在一定范圍內(nèi)，得出在時(shí)，，，符合要求。 N 530 531 532 533 534 535 536 537 538 539 P 0.9417 0.9333 0.9300 0.9433 0.9427 0.9500 0.9500 0.9537 0.9733 0.9667 表（2）十組值對應(yīng)的值 圖（4）固定測試點(diǎn)模擬圖 圖（5）兩種方法線性擬合對比圖 5.2針對問題二的求解 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ù)膬蓚€(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）可直接觀測其通信通路： 序號(hào) 起始節(jié)點(diǎn) 終止節(jié)點(diǎn) 通信路徑 通信距離 1 60 87 601587 16.29 2 6 73 64373 16.51 3 93 10 93666510 27.43 4 14 28 14928 12.79 5 8 16 87516 13.64 6 80 12 805512 16.56 7 41 18 419510818 20.08 8 62 11 62511 11.40 9 49 106 498830106 20.18 10 99 54 9998710554 29.76 表（3）：10個(gè)任意節(jié)點(diǎn)的通信路徑及通信距離 圖（7）：上述10個(gè)節(jié)點(diǎn)的通路圖 通過直接觀測通信圖，可知通信路徑并不唯一，對于距離較短，節(jié)點(diǎn)少時(shí)，簡單易用，但是當(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), 從而生長一顆以為根的最短路樹,在這顆樹上每個(gè)頂點(diǎn)與根節(jié)點(diǎn)之間的路徑皆為最短路徑。該算法核心是求得鄰階矩陣，計(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）的對比分析，其通信路徑及距離是完全吻合的，但用D算法明顯更為優(yōu)越，能夠快速準(zhǔn)確地給出任意兩節(jié)點(diǎn)之間的最短通信路徑以及此時(shí)的最短通信距離，且誤差很小。 六、 模型的評價(jià)和改進(jìn) 6.1模型的評價(jià) 6.1.1優(yōu)點(diǎn) (1)本文通過多次模擬來求解全部覆蓋的概率，方法實(shí)用簡單，容易編程實(shí)現(xiàn)。 (2)運(yùn)用D算法求解最短通信路徑和距離時(shí)，準(zhǔn)確快速可靠，且容易編程實(shí)現(xiàn)，易于推廣。 （3）通過對覆蓋效率的計(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í)間長。 6.2模型的改進(jìn) 從第一問的覆蓋效率可知，效率偏低，因此十分有必要提高其覆蓋效率，可以對覆蓋區(qū)域進(jìn)行全面了解后，通過精確計(jì)算確定各個(gè)節(jié)點(diǎn)位置，減少隨機(jī)模擬的誤差，對于重復(fù)覆蓋頻率高的地區(qū)減少節(jié)點(diǎn)數(shù)，對于重復(fù)覆蓋頻率很低的地區(qū)增加節(jié)點(diǎn)數(shù)，使其均勻化，從而增加了覆蓋效率，也更加經(jīng)濟(jì)。 七、 模型的推廣和應(yīng)用 本文對研究無線傳感網(wǎng)絡(luò)的覆蓋問題和節(jié)點(diǎn)的通信模型設(shè)計(jì)進(jìn)行了討論，建立無線傳感網(wǎng)絡(luò)，可以準(zhǔn)確而及時(shí)地掌握險(xiǎn)情的發(fā)展情況，在森林防火、災(zāi)區(qū)空投物資、戰(zhàn)場空投等方面都具有一定的指導(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; [3]Dijkstra最短路徑算法（百度文庫） 鏈接:http://wenku.baidu.com/view/680ebde29b89680203d82598.html 附錄： 附表1 120個(gè)節(jié)點(diǎn)的坐標(biāo)表 節(jié)點(diǎn)標(biāo)號(hào) X Y 節(jié)點(diǎn)標(biāo)號(hào) X Y 節(jié)點(diǎn)標(biāo)號(hào) X Y 節(jié)點(diǎn)標(biāo)號(hào) X Y 1 57 58 31 6 33 61 32 95 91 74 44 2 95 74 32 85 9 62 47 71 92 41 25 3 34 12 33 64 37 63 50 43 93 39 21 4 31 68 34 22 13 64 56 43 94 95 51 5 52 67 35 69 43 65 56 25 95 72 76 6 30 4 36 80 83 66 47 25 96 79 8 7 15 75 37 76 13 67 80 64 97 78 44 8 75 52 38 88 94 68 10 96 98 10 80 9 75 30 39 25 95 69 12 33 99 8 89 10 65 28 40 62 45 70 63 70 100 15 95 11 55 63 41 70 70 71 39 9 101 45 90 12 41 61 42 45 42 72 81 89 102 70 82 13 36 20 43 35 9 73 43 14 103 90 78 14 72 24 44 75 41 74 17 25 104 84 78 15 16 10 45 35 91 75 80 55 105 20 70 16 85 49 46 56 30 76 45 61 106 40 71 17 86 90 47 27 92 77 92 40 107 55 70 18 75 90 48 92 90 78 78 22 108 5 95 19 32 20 49 25 58 79 89 45 109 73 18 20 5 92 50 44 52 80 51 51 110 22 28 21 16 35 51 5 80 81 40 90 111 17 80 22 25 66 52 17 33 82 65 49 112 50 10 23 72 4 53 90 5 83 76 7 113 55 20 24 68 33 54 25 74 84 30 98 114 87 22 25 61 35 55 58 47 85 26 34 115 72 98 26 37 78 56 95 2 86 28 99 116 55 79 27 48 46 57 87 72 87 25 8 117 7 2 28 81 31 58 68 88 88 29 63 118 85 20 29 23 90 59 30 28 89 40 83 119 35 50 30 35 66 60 9 9 90 4 11 120 10 68 %程序（一）：隨機(jī)模擬覆蓋的概率 clear clc for 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 end if p==T %已全部覆蓋 m=m+1; end end c=m/300 c=0; end %程序（二）：固定點(diǎn)覆蓋的概率 %% clear clc m=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:99 x((1+100*i):(100+100*i),1)=0.5+i; end for i=1:100 Y(i,1)=i-0.5; end y=[]; for i=1:99 y((1+100*i):(100+100*i),1)=Y; end for n=530:540 for k=1:K f=0; x0=100*rand(n,1); %產(chǎn)生n個(gè)節(jié)點(diǎn)圓心坐標(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; end end P=m/K m=0; end %程序（三）：通信路徑圖 clear clc X=load(shuju.txt); x0=X(:,2); y0=X(:,3); plot(x0,y0,.) text(x0,y0,num2cell(1:120)) hold on for 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 end end title(通信路徑圖) xlabel(X) ylabel(Y) %程序（四）：D算法最短通信路徑圖 clear clc X=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 end end w=dis; m=[60 6 93 14 8 80 41 62 49 99]; %取十組節(jié)點(diǎn) n= [87 73 10 28 16 12 18 11 106 54]; for i=1:10 [dis, path]=dijkstraf(w,m(i),n(i)) %調(diào)用dijkstraf.m文件 end clear clc A=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 end end w=dis; m=[60 6 93 14 8 80 41 62 49 99];%取上述十組節(jié)點(diǎn) n=[87 73 10 28 16 12 18 11 106 54]; for i=1:10 [dis,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 end plot(X,Y) xlabel(X) ylabel(Y) title(D算法最短通信路徑圖) hold on X=0; Y=0; end