如何有效監(jiān)測災難突發(fā)區(qū)域

1、浙江工業(yè)大學第十四屆大學生數(shù)學建模競賽所選賽題： A B C我們承諾：Ø 我們仔細閱讀了浙江工業(yè)大學數(shù)學建模競賽的競賽規(guī)則。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人研究、討論與賽題有關的問題。Ø 我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。Ø 我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。參賽隊員（簽名）：張加滿 學院年級：信息分院

2、通信1103聯(lián)系方式：541231參賽隊員（簽名）：宣 波 學院年級：信息分院軟件1101聯(lián)系方式：542082 參賽隊員（簽名）：徐晗景 學院年級：信息分院軟件1102聯(lián)系方式：542115 我們隊伍愿意參加暑期數(shù)學建模培訓，參加全國大學生數(shù)學建模競賽如何有效監(jiān)測災難突發(fā)區(qū)域摘 要 本論文針對自然災難突然發(fā)生時，為實時觀察和監(jiān)測災難區(qū)域的狀態(tài)，需要部署相當數(shù)量的智能裝置構(gòu)成全區(qū)域覆蓋的監(jiān)視系統(tǒng)問題，文章共建立了三個模型用以解決該類問題。 對于問題（1）：我們主要利用一個特定的矩形區(qū)域（10R*10R）展開的，對該正方形區(qū)域進行分析得知：要對矩形區(qū)域用圓進行覆蓋即先需要對圓用多邊形進行覆蓋，由

3、最小覆蓋圓模型知，當且僅當用正多邊形來限制圓的半徑得到的圓可以使得覆蓋整個圖形時所用圓的個數(shù)最少。步驟1）.一定半徑（范圍要求）的圓的內(nèi)接正多邊形可以完全覆蓋該矩形區(qū)域，求若干個該正多邊的外接圓能使得完全覆蓋整個矩形區(qū)域所用圓的個數(shù)最少；步驟2)，滿足限制條件的正多邊形有正三角形，正四邊形，正六邊形，求相鄰兩個圓相交的公共面積不小于一個圓面積的K%。在步驟1）適當?shù)募僭O條件下，對假設的合理性進行說明和驗證，得到了題目所求的最優(yōu)值。用到了幾何知識、覆蓋原理、微積分等一些數(shù)學知識探究了矩形覆蓋的問題，通過計算機模擬分析了不同正多邊形相交率變化趨勢，最后運用mat lab作出符合一般性的程序并得出相

4、關圖形。 對于問題（2）， 該問題可以歸結(jié)為多元目標線性規(guī)劃的問題，目標一是全區(qū)域覆蓋傳感器節(jié)點數(shù)最少；目標二是在智能裝置系統(tǒng)判斷節(jié)點受到損毀后，飛機（以一架飛機為例）如何在高空中飛行使得代價（時間、能量消耗）最小。我們在第一題的基礎上，選擇0-1判斷節(jié)點損毀情況，又假設了一些距離變量，判斷用哈密頓回路，啟發(fā)式算法等思想求最短路徑。 對于問題(3)， 修復后的網(wǎng)絡運行一段時間后，會有一些節(jié)點死亡而導致再次修復。綜合考慮網(wǎng)絡監(jiān)測性能和修復成本，我們會采取問題(2)中所給的覆蓋的方法進行數(shù)據(jù)優(yōu)化。以及傳感器節(jié)點會受到感知其位置附近的各種狀態(tài)變化，如溫度、震動、濕度等，其感知能力隨節(jié)點與目標距離的增

5、加而衰減。我們會給予這些因素以不同的權重。 關鍵詞：監(jiān)測災難區(qū)域，覆蓋原理，數(shù)學建模，多目標規(guī)劃，數(shù)據(jù)優(yōu)化一.問題重述 自然災難突然發(fā)生時，為實時觀察和監(jiān)測災難區(qū)域的狀態(tài)，需要部署相當數(shù)量的智能裝置構(gòu)成全區(qū)域覆蓋的監(jiān)視系統(tǒng)。這種裝置內(nèi)嵌了傳感器，稱為傳感器節(jié)點，用于感知其位置附近的各種狀態(tài)變化，如溫度、震動、濕度等，其感知能力隨節(jié)點與目標的距離增加而衰減。由于每個節(jié)點的感知能力和覆蓋范圍十分有限，需要部署大量的節(jié)點才能實現(xiàn)區(qū)域監(jiān)視。這些節(jié)點通過無線通信相互聯(lián)系和發(fā)送數(shù)據(jù)，以傳感器網(wǎng)絡的形式進行協(xié)同工作。傳感器節(jié)點部署的一般途徑是通過飛機或機器人進行布撒，當節(jié)點所能感知的面積與區(qū)域總面積的比率達

6、到一定數(shù)值時，我們認為該區(qū)域已經(jīng)被有效監(jiān)測。沒有被任何節(jié)點覆蓋到的區(qū)域，稱為覆蓋空洞；只要該區(qū)域被任何一個或多個節(jié)點覆蓋即認為該區(qū)域被有效覆蓋；當節(jié)點受到外部干擾或破壞而損毀時，節(jié)點的死亡或失效也有可能形成覆蓋空洞。這些空洞的總面積不能過大，否則將無法實現(xiàn)區(qū)域的有效監(jiān)測。根據(jù)以上原理，針對10R*10R（R為傳感器節(jié)點的有效感知半徑）的監(jiān)測區(qū)域，試分析和解決如下問題：(1)對于初始部署后存在的覆蓋空洞，給出一種新節(jié)點部署方案，使得網(wǎng)絡的覆蓋率達到95%以上。(2)若節(jié)點隨機死亡，并且當網(wǎng)絡的覆蓋率低于85%時必須進行修復，怎樣部署新的節(jié)點使部署的代價（時間、能量消耗）最?。?3)修復后的網(wǎng)絡運

7、行一段時間后，會有一些節(jié)點死亡而導致再次修復。綜合考慮網(wǎng)絡監(jiān)測性能和修復成本，試給出一種優(yōu)化的修復準則。二.問題分析2.1問題（1） 題目要求是對矩形區(qū)域用圓進行覆蓋，使得完全覆蓋整個矩形區(qū)域所用圓的個數(shù)最少的數(shù)學模型，該問題其實就是利用的覆蓋原理建立的模型。一定半徑（范圍要求）的圓的內(nèi)接正多邊形可以完全覆蓋該矩形區(qū)域，求若干個該正多邊的外接圓能使得完全覆蓋整個矩形區(qū)域所用圓的個數(shù)最少；步驟2)，滿足限制條件的正多邊形有正三角形，正四邊形，正六邊形，求相鄰兩個圓相交的公共面積不小于一個圓面積的K%。在LINGO軟件中，通過設立一約束條件，最后將目標函數(shù)進行最優(yōu)化求解。22問題（2） 該問題可以

8、歸結(jié)為多元目標線性規(guī)劃的問題，所以我們在目標一是全區(qū)域覆蓋傳感器節(jié)點數(shù)最少；目標二是在智能裝置系統(tǒng)判斷節(jié)點受到損毀后，飛機（以一架飛機為例）如何在高空中飛行使得代價（時間、能量消耗）最小的條件下求最短路徑。23問題（3）該問題要求的是綜合考慮修復后的網(wǎng)絡運行一段時間后會有一些節(jié)點死亡而導致再次修復的網(wǎng)絡監(jiān)測性能和修復成本。以及傳感器節(jié)點會受到感知其位置附近的各種狀態(tài)變化，如溫度、震動、濕度等，其感知能力隨節(jié)點與目標的距離增加而衰減。我們會給予這些因素以不同的權重。三模型的假設與符號說明3模型的假設（1）10R*10R（R為傳感器節(jié)點的有效感知半徑）的監(jiān)測區(qū)域進行覆蓋。我們可以把問題簡而言之為一

9、個特定的矩形區(qū)域（10R*10R）中,用半徑為R的圓對其進行完全覆蓋,(為了題目方便，我們暫時性把網(wǎng)絡覆蓋率設為100%，在實驗最后除去5%的覆蓋。設區(qū)域（10*10），半徑為1)。（2）.區(qū)域中所有用于覆蓋的圓是半徑相等的圓。（3）在區(qū)域中所有的地形是相對平整的，不考慮地形的影響。（問題（1),問題（2）中的區(qū)域環(huán)境相對平穩(wěn)，不考慮溫度、震動、濕度等因素）。（4）在覆蓋過程中不考慮圓周長，半徑及圓心的寬度。（5）為研究方便只考慮正多邊形覆蓋，不考慮不規(guī)則多邊形覆蓋。32符號說明 符號符號說明正多邊形的內(nèi)角度數(shù)x正多邊形的邊數(shù)y覆蓋一個圓周所需的正多邊形的個數(shù)正多邊形的邊所對的圓心角K%相交園

10、的公共面積占一個圓面積的百分率Di第i個與第j個傳感器之間的距離Xi第i個傳感器的橫坐標Ai第i個傳感器的縱坐標四.模型的建立與求解41問題1的模型建立與求解4.1.1 解決問題1).圓的排列方式因為不可能窮舉圓的任意形狀的內(nèi)接多邊形來覆蓋這個正方形區(qū)域，所以采用圓的內(nèi)接正多邊形覆蓋方案，此即一個以正多邊形為基本圖形覆蓋某一平面區(qū)域的問題。又有：定理1：若干半徑為R的圓完全覆蓋正方形區(qū)域的充分條件是這些圓的內(nèi)接正多邊形完全覆蓋了正方形區(qū)域。證明：假設正n邊形覆蓋了正方形區(qū)域中的，所有（i1，2，M），覆蓋的區(qū)域包含了正方形區(qū)域B，即所有覆蓋的區(qū)域包含了正方形區(qū)域B。因為對于由形成的外接圓，必包

11、含區(qū)域，所以，所有（i1，2，M）覆蓋的區(qū)域必包含了正方形區(qū)域B。定理2: 兩圓相交面積不小于兩個圓中較大的圓面積的k時，當兩圓半徑相等時，公共面積占兩個圓總面積的百分比最小。證明：如圖兩圓，半徑因為，所以 又因為 ，所以 （當且僅當即時取等）?？紤]在一個無限大的平面內(nèi)采用兩種半徑，的圓相交完全覆蓋平面。定義圓的有效利用率: 則 （當且僅當S1=S2即時取等）。推論：兩圓相交，滿足相交面積不小于一個整圓面積的k的條件下，當兩圓半徑相等時，圓有效利用率最高。 由定理2及推論得知，應選取半徑相同的圓。2).平面拼裝的若干定義和定理 定義1 如果一組圖形拼鋪后完全覆蓋平面，并且這組圖形沒有重疊，則這

12、組圖形稱為平面的拼裝。 定義2 如果在平面的拼裝中，只有一種基本元素圖形，則稱為平面的單元拼裝；如果在單元拼裝中基本元素圖形為正多邊形，則稱為單元正規(guī)拼裝；如果在單元拼裝中基本元素圖形為三角形，則稱為單元三角拼裝。 定理3 拼裝中，其基本元素圖形能且只能是正三角形、正方形和正六邊形。現(xiàn)在我們來證明定理3證明：設在單元正規(guī)拼裝中, 其基本元素圖形為正邊形, 正邊形的每個內(nèi)角值為, 顯然 ，我們設，則 （1）解不定方程(1)可得: 。即: 在單元正規(guī)拼裝中, 其基本元素圖形只可能是正三角形、正四邊形、正六邊形，因此，要使單元正規(guī)拼接的均勻覆蓋效率最大，則應選擇正三角形、正方形或正六邊形拼接正方形區(qū)

13、域。 定理4 在兩等半徑的圓相交的時候，若兩交點夾的劣弧所對的圓心角固定，則相交面積與整個圓面積的比值與圓半徑R無關，為常數(shù)。證明：如圖1，兩圓的圓心分別為，半徑均為R，兩交點為A，B。相交面積為 令 由知，k值與圓的半徑R無關，定理4得證。將中的化為數(shù)量 所以隨著增大，k的值是單調(diào)增加的并且增長速度滿足正弦形式。兩半徑相等圓相交，以公共面積中心為坐標原點，圓心距。則兩圓方程分別為: 公共面積: 令 4.1.2模型建立用半徑為r =1的圓如何完全覆蓋整個矩形區(qū)域（1010），使得相鄰兩圓相交的公共面積不小于一個圓面積的k。因此，我們用正多邊形來覆蓋則需討論用什么類型的正多邊形和什么方式覆蓋1）

14、.正多邊形的類型由多邊形的內(nèi)角和公式可得正多邊形的一個內(nèi)角 ，即 ，我們設，則 （1） y643x346 所以： 則滿足完全覆蓋條件的正多邊形只有正三邊形、正四邊形、正六邊形。 2）.正多邊形的覆蓋方式由于相鄰兩圓相交的公共面積不小于一個圓面積的k,現(xiàn)在設一個圓的內(nèi)接正多邊形的邊所對的圓心角為，由面積之間的關系()則可得關于k的不等式： 當時 ，則k=39.09 當時 ，則k=18.15 當時 ，則k=5.77經(jīng)過重復實驗過后，我們得出了兩種正多邊形的最優(yōu)覆蓋方式： 用正四邊形覆蓋覆蓋整個矩形區(qū)域只需半徑為1的圓64個，其覆蓋的圖形如圖1所示。 圖1 圖2 用正六邊形覆蓋覆蓋整個矩形區(qū)域只需半

15、徑為1的圓45個，其覆蓋的圖形如圖2所示。第1題答案：網(wǎng)絡覆蓋率為100%時，覆蓋整個矩形區(qū)域只需半徑為1的圓45個。除去5%的覆蓋率后，圓的個數(shù)為38。42問題2的模型建立與求解4.2.1解決問題1） 模型選擇：在問題（1）中我們已經(jīng)獲得三種覆蓋方法（正三角形，正四邊形，正六邊形）以及他們所對應的相鄰兩個圓相交的公共面積占一個圓面積的K%值，問題（2）考慮的因素不只是這個，還需要考慮例如：節(jié)點到節(jié)點之間的距離，數(shù)據(jù)處理方式，統(tǒng)計難易程度等?？紤]因素1：相鄰兩個圓相交的公共面積占一個圓面積的K%值 當時 ，則k=39.09 當時 ，則k=18.15 當時 ，則k=5.77我們選擇當 當時 ，則

16、k=5.77?？紤]因素2：節(jié)點到節(jié)點之間的距離（因為考慮到數(shù)據(jù)處理方式，統(tǒng)計難易程度等等方面正三角形就不選擇了）。 考慮到節(jié)點到節(jié)點之間的距離我們選擇正四邊形考慮因素3：數(shù)據(jù)處理方式以及統(tǒng)計難易程度正四邊形的數(shù)據(jù)相對穩(wěn)定，對后期數(shù)據(jù)處理比較方便。正六邊形上面建立坐標軸比較困難（后期求最短路徑是放在坐標軸上做的），而相對于正四邊形建坐標軸比較容易。綜上所述我們在考慮問題（2）的時候我們選擇用正四邊形的覆蓋模型為基礎。2）節(jié)點損毀檢測：注：對于問題(2) “若節(jié)點隨機死亡，并且當網(wǎng)絡的覆蓋率低于85%時必須進行修復，怎樣部署新的節(jié)點使部署的代價（時間、能量消耗）最小”是在問題（1）“對于初始部署后

17、存在的覆蓋空洞，給出一種新節(jié)點部署方案，使得網(wǎng)絡的覆蓋率達到95%以上”上面建立的。我們建立正四邊形是以100%覆蓋率為假設的，但在最我們把網(wǎng)絡的覆蓋率5%是除去的?？紤]到這個遺留因素我們將兩位0-1二進制表示。第一位0-1二進制表示模型除去的5%覆蓋率。第二位表示節(jié)點是否隨機死亡?！?0”或者“01”不予處理；“11”表示節(jié)點正常，而“10”表示節(jié)點是在布點后受到外部干擾或破壞而損毀出現(xiàn)節(jié)點死亡或失效。符號（二進制）說明00或者01不予處理11節(jié)點正常10節(jié)點是在布點后受到外部干擾或破壞而損毀出現(xiàn)節(jié)點死亡或失效。這些節(jié)點通過無線通信相互聯(lián)系和發(fā)送數(shù)據(jù)，以傳感器網(wǎng)絡的形式進行協(xié)同工作。我們選取

18、一個節(jié)點為原點建立一張坐標軸（以最左下角位置上的節(jié)點為原點）。系統(tǒng)對每個節(jié)點進行檢測。當傳感器節(jié)點變?yōu)椤?0”時，記錄其出現(xiàn)的坐標Aij。3）修復機制：1.通過分析我們可以得到當i=0，i=7, j=0,或者j=7是我們需要單獨考慮其損失面積 ; ;；頂點以及邊界位子的特殊情況損失面積：i=0i=7j=0j=7i=0i=7j=0j=7頂點以及邊界位子的特殊情況相鄰節(jié)點A ij, A i+1j, A ij+1,A i-1j , Aij-1中任意兩點同時死亡是則要考慮兩節(jié)點相交的公共面積;當每個節(jié)點(除頂點以及邊界位子)死亡后都會損失的面積，如果有相鄰節(jié)點(除頂點以及邊界位子)A ij, A i+

19、1j, A ij+1,A i-1j , Aij-1中任意兩點同時死亡是則要考慮兩節(jié)點相交的公共面積。當時，進行節(jié)點修復。按傳感器失效的先后順序，分別給他們標號a1,a2.an（原點a0(0,0)）。2.制定修復路徑計算點與點之間的距離Di=制作成一個n階矩陣1 從原點開始，i=0，k=1。2 從第i行中選出該行中的最小數(shù)Di。3 然后i=j(把j賦給i)，且把第i列的值全改為。4 ak=i，k=k+1。5 重復的步驟，直到矩陣中的數(shù)全為。則修復傳感器的順序為a1,a2, a3an，此時所部署的代價（時間、能量消耗）最小。43問題3的模型建立與求解該問題要求的是綜合考慮修復后的網(wǎng)絡運行一段時間后

20、會有一些節(jié)點死亡而導致再次修復的網(wǎng)絡監(jiān)測性能和修復成本。以及感器節(jié)點會受到感知其位置附近的各種狀態(tài)變化，如溫度、震動、濕度等，其感知能力隨節(jié)點與目標的距離增加而衰減。我們會給予這些因素以不同的權重。 圖4.1 圖4.2如圖4.1所示有ABCDEF六個點，（A為起始點）計算出A與他們之間的距離。根據(jù)距離所示我們可以得到如果在情況不是很危急時，去修復D點不是很經(jīng)濟。那我們就暫時性把D放置。飛機從A點開始飛向離它距離最小的B（圖4.2）。然后A點在系統(tǒng)內(nèi)消失。系統(tǒng)默認B變?yōu)槠鹗键c（圖4.3 ）。 圖4.3 圖4.4以B為起始點后測得B點到其他平面內(nèi)的點距離。從經(jīng)濟等各方面考慮D點還是暫時性放置。B點

21、上的飛機就飛往離它距離最小的C點（圖4.4），然后B點在系統(tǒng)內(nèi)消失。系統(tǒng)默認C變?yōu)槠鹗键c（圖4.5 ）。 圖4.5在B消失的同時，出現(xiàn)點GH兩個點，C為起始點，測得C點到其他平面內(nèi)的點距離。從經(jīng)濟等各方面考慮D點還是暫時性放置。C點上的飛機就飛往離它距離最小的G點（圖4.6），然后C點在系統(tǒng)內(nèi)消失。同時平面內(nèi)出現(xiàn)很多點。這時候不能不考慮D點了。再以上述方法進行飛行修復節(jié)點。五模型的分析5.1模型1滿足完全覆蓋條件的正多邊形只有正三角形、正四邊形、正六邊形；正多邊形346K的取值39.0918.155.77則只需k5.77，就可以根據(jù)實際情況找到一種完全覆蓋一個給定的n*n(覆蓋率為100%)矩

22、形的最優(yōu)方式，其變化趨勢如圖5.1 正多邊形相交率K的變化趨勢圖圖5.15.2模型2當時，進行節(jié)點修復。計算點與點之間的距離Di=制作成一個n階矩陣從原點開始，i=0，k=1；從第i行中選出該行中的最小數(shù)Di；然后i=j(把j賦給i)，且把第i列的值全改為；ak=i，k=k+1；重復的步驟，直到矩陣中的數(shù)全為；則修復傳感器的順序為a1,a2, a3an，此時所部署的代價（時間、能量消耗）最小。六模型的評價及改進6.1 模型的評價 三個模型運用了幾何知識等數(shù)學方法。 模型1討論了一定條件下的完全覆蓋問題可以為實際情況提供一些定量分析。模型2討論了關于最短路徑問題。模型3是對模型2進行優(yōu)化和實際化

23、。 模型雖具有一般性，但并不是所有情況都適用。6.2 模型的改進模型1我們先通過具體的實例來討論區(qū)域覆蓋問題，使得問題較為簡單、直觀，而實際情況還有諸多相關因素與要討論的問題相互制約；在現(xiàn)在的經(jīng)濟社會中，應該加以考慮使用的圓的半徑為多少時，能使覆蓋矩形的圓的面積最少，而我們只討論了k（相鄰兩圓相交的公共面積不小于一個圓面積的k）的變動情況，還有待于改進討論方向。模型2所使用的算法不夠優(yōu)化，存在一定的問題。例如：5%的檢測區(qū)域沒有很好的排布，對于一開始所選取的坐標軸不是最優(yōu)的?？梢杂兴膿Q。模型3，數(shù)據(jù)處理不夠明了，考慮客觀實際因素不夠完善。七參考文獻 1 姜啟源,謝金星,葉俊. 數(shù)學模型（第三

24、版），高等教育出版社。 2 楊中華. 平面點列最小覆蓋圓的計算方法，北京工業(yè)大學學報，2000,vol.26(2) 3 數(shù)學模型與計算機模擬，江裕釗、辛培情編，電子科技大學出版社，(1989) 4 數(shù)學建模-方法與范例，壽紀麟等編，西安交通大學出版社(1993) 5 數(shù)學模型，朱思銘、李尚廉編，中山大學出版社，(1995) 6 數(shù)學模型建模分析，蔡常豐編著，科學出版社，(1995) 7 數(shù)學建模競賽教程，李尚志主編，江蘇教育出版社，(1996) 8 數(shù)學建模入門，徐全智、楊晉浩編，成都電子科大出版社，(1996). 9 數(shù)學模型方法，齊歡編著，華中理工大學出版社，(1996)10 數(shù)學建模優(yōu)秀

25、案例選編(工科數(shù)學基地建設叢書)，汪國強主編，華南理工大學出版社，(1998)11 問題解決的數(shù)學模型方法，劉來福，曾文藝編著、北京師范大學出版社， 附錄附錄1、判斷哪些正多邊形能夠完全覆蓋的程序for i=3:1000; m(i)=i; n(i)=2*m(i)/(m(i)-2); if mod(n(i),1)=0; dip('m=',num2str(m(i),' n=',num2str(n(i) endend附錄2、正四邊形完全覆蓋程序r=input('請輸入圓的半徑r=');m=input('請輸入寬m=');n=input(

26、'請輸入高n=');Th=0:0.1:2*pi;for i=0:r*sqrt(2):mfor j=0:r*sqrt(2):n x=i+r*cos(th); y=j+r*sin(th); plot(x,y,'k') hold on axis equalendendhold onfor i=0:(m/(r*sqrt(2)for j=0:(n/(r*sqrt(2) x=-r*sqrt(2)/2+r*sqrt(2)*i; y=-r*sqrt(2)/2+r*sqrt(2)*j;rectangle('Position',x,y,r*sqrt(2),r*sqrt(2)endendhold onrectangle('Position',0,0,m,n,'EdgeColor','r')hold onrectangle('Position',-r*sqrt(2)/2,-r*sqrt(2)/2,m,n,'EdgeColor','b')附錄3、正六邊形完全覆蓋程序clear;clcr=input('請輸入圓的半徑r=');m=input('請輸入寬m=