AdHoc網(wǎng)絡(luò)中的區(qū)域劃分和資源分配問題第二組

1、全國第三屆研究生數(shù)學(xué)走棧丸拳題冃ad hoc網(wǎng)絡(luò)中的區(qū)域劃分和資源分配問題摘要：近年來無線網(wǎng)絡(luò)通信得到了迅速的發(fā)展，而ad hoc網(wǎng)絡(luò)做為一 種無線通信的載體發(fā)展迅速。木文首先建立了 ad hoc網(wǎng)絡(luò)一跳覆蓋 區(qū)的基k模型，充分的論證了k取不同值時效果的優(yōu)劣，得出問題1 結(jié)論：5%時采用基6模型，3信道，需45個圓；18%時采用基4模 型，2信道，需60個圓。對于問題2,采用基6模型，得出圓半徑之 和最小為4450o論文主要對問題3進(jìn)行了詳細(xì)分析，捉出漫路分簇算法，將節(jié)點(diǎn) 進(jìn)行分簇，建立基于模擬退火的圓心漂移模型和最小覆蓋圓模型，去 除圓心位置兀余和半徑長度兀余，同時進(jìn)行限制性條件檢驗，得到無

2、 湖、有湖最小半徑之和分別為3925、3625o基于問題3的討論，對問題4、5、6進(jìn)行了進(jìn)一步闡述。（由組委會填寫）參賽密碼參賽隊號10422007一、問題的描述隨著人們對擺脫有線網(wǎng)絡(luò)束縛、隨時隨地可以進(jìn)行自由通信的渴望，近兒年 來無線網(wǎng)絡(luò)通信得到了迅速的發(fā)展，無線網(wǎng)絡(luò)的設(shè)計成為當(dāng)前網(wǎng)絡(luò)和通信技術(shù)研 究的熱點(diǎn)本題ad hoc網(wǎng)絡(luò)的通信設(shè)計問題就是在這樣一個背景下提出的。 ad hoc網(wǎng)絡(luò)的出現(xiàn)推進(jìn)了人們實(shí)現(xiàn)在任意環(huán)境下的自出通信的進(jìn)程，同吋它也 為軍事通信、災(zāi)難救助和臨吋通信提供了有效的解決方案。該題討論的是對一個特定的正方形區(qū)域（1000x1000）,采用有一定半徑范 圍耍求的圓冇重疊的全部

3、覆蓋或者對正方形區(qū)域屮特定位置的節(jié)點(diǎn)進(jìn)行覆蓋。問題有如卜幾個方面：在滿足一定條件下，如何找到最小數(shù)目的覆蓋圓？如 何找到所冇半徑和最小的覆蓋圓的區(qū)域分劃？在特定的區(qū)域分劃下，如何確定信 道的數(shù)口？如何討論網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的抗毀性？當(dāng)正方形區(qū)域屮存在一個湖泊吋， 如何改變以上設(shè)計尋求最優(yōu)？當(dāng)正方形區(qū)域中有一定數(shù)目固定節(jié)點(diǎn)和運(yùn)動節(jié)點(diǎn) 時，如何實(shí)現(xiàn)圓覆蓋？并討論其連通性和抗毀性。當(dāng)把能量、功率、時間等實(shí)際 網(wǎng)絡(luò)運(yùn)行因素考慮進(jìn)來后，如何實(shí)現(xiàn)i員i覆蓋？并提出口己的網(wǎng)絡(luò)設(shè)計觀點(diǎn)。二、問題的簡化（模型假設(shè)）我們針對不同的問題，捉出了下列假設(shè)：針對問題（1）,假設(shè)覆蓋i員i的i員i心位置坐標(biāo)可以精確定位，在正方

4、形區(qū)域內(nèi) 地形是完全相同的，不考慮地形因索帶來的影響；覆蓋圓的半徑大小也是相同的, 都為100；節(jié)點(diǎn)位于圓心或者公共部分的屮心。針對問題（2）,假設(shè)覆蓋圓的半徑可以在75-100之間隨意選擇；兩個面積 不等的圓相交，公共部分的而積不小于大圓而積的5%。針對問題（3）,假設(shè)在一個較短的時間間隔內(nèi)，網(wǎng)絡(luò)的連通性不變；有轉(zhuǎn)發(fā) 任務(wù)的相鄰圓的公共部分面積不小于較大圓的5%；覆蓋圓的半徑不大于100o針對問題（4）,假設(shè)數(shù)據(jù)文件給出的前十個數(shù)據(jù)只做折線運(yùn)動，每30個單 位時間可能改變一次運(yùn)動的方向和速度，運(yùn)動的方向角、速度是分別服從在0, 2ti、0, 2上均勻分布的隨機(jī)變量；-其他節(jié)點(diǎn)不移動；節(jié)點(diǎn)到達(dá)

5、正方形區(qū)域邊 界后只能向區(qū)域內(nèi)運(yùn)動。針對問題（5）假設(shè)發(fā)射功率與最大傳輸距離的三次方成正比；網(wǎng)絡(luò)運(yùn)行期, 節(jié)點(diǎn)保持靜止；在a、b兩個節(jié)點(diǎn)通信時，不存在同吋收發(fā)的問題；兩節(jié)點(diǎn)平均 通信次數(shù)與距離的平方成反比；發(fā)射、接收和備用狀態(tài)z間的轉(zhuǎn)換時間以及為獲 取網(wǎng)絡(luò)結(jié)構(gòu)、路曲等公共信息所花的時間和其他資源忽略不計。針對問題（6）假設(shè)通信過程屮，重發(fā)3次或者延吋30個吋間單位就可能丟 包。三、模型的分析定理1：若干半徑為r的圓完全覆蓋正方形區(qū)域的充分條件是這些圓的內(nèi)接 正多邊形完全覆蓋了正方形區(qū)域。證明：假設(shè)正n邊形&覆蓋了正方形區(qū)域中的色，所有4（i=l，2,， m）,覆蓋的區(qū)域包含了正方形區(qū)域

6、即所有色覆蓋的區(qū)域包含了正方形區(qū)域乩 因為對于由4形成的外接圓q,必包含區(qū)域色，所以，所冇q （i=l, 2, m）覆蓋的區(qū)域必包含了正方形區(qū)域b。定理2：四色定理對于一幅地圖，最多使用4種顏色，就可以時任意相鄰的區(qū)域涂上不同顏色, 其等價命題為：沒有割邊的三正則平面圖的邊可以三色著色。簡單的說明如下：根據(jù)“拓?fù)鋵W(xué)”原理，任何復(fù)雜形狀的每一塊區(qū)域都可看 成是一個點(diǎn)的集合，兩塊區(qū)域之間相互有交界的可看成這兩點(diǎn)之間有連線，只要 證明在一個平而內(nèi)，相互z間都冇連線的點(diǎn)不會超過四個，也就證明了“四色問 題”。推論：對于1000x1000的正方形平面區(qū)域內(nèi)的任意一跳覆蓋區(qū)劃分，最多 使用4種信道，就可以

7、保證相鄰的一跳覆蓋區(qū)擁有不同的信道。定理3：在兩等半徑的i員i相交的時候，若兩交點(diǎn)夾的劣弧所對的i員i心角e 固定，則相交面積'與整個圓面積s的比值與圓半徑r無關(guān)，為常數(shù)。證明：如圖1,兩圓的圓心分別為q,勺，半徑均為心兩交點(diǎn)為a, bo相交面積為sr辭宀押訕色生fsin.今上= _smstir1180 7i由知，k值與圓的半徑r無關(guān)，定理1得證。 將sin&屮的夕化為數(shù)量sin空180.071dk d 0 sin 1801ottde de iso 7i一 (1 ov)=(1-cos)>0180180所以隨著&增大，k的值是單調(diào)增加的并且增k速度滿足正弦形式。兩半

8、徑相等圓相交，以公共而積中心為坐標(biāo)原點(diǎn)，圓心距d = 2o。則兩圓方程分別為(x-a)2 + y2=r2(x + 6z)2 + y2 = r2公共面積s° = 4叮尺ylr2-(x-a)2dx 令 x-a = t x = t +a50=4*fv/?2-r26/r廠 arcsin仝 99s*” kr2cos20d02s° = tir1 - 2r2 arcsin 一 2ajw = hjir1r針對問題中的相交面積5%, 18%兩種情況，由上面公式計算出£亠=5% 時，& = 57.1°sr 亠= 18% 時，& = 89.7°s對于

9、基6模型， = 60 >57.1°,此時k二乞= 5.77%,所以，基6模型可以很好 s的解決公共面積不小于5%的要求。£同理，對于基4模型0 = 90°89.7。，此時，= = 18.17%所以，基4模型可以 s很好的解決公共面積不小于18%的要求。定理4：在保證兩圓相交面積不小于兩個圓中較大的圓面積的£%時，當(dāng)兩圓半徑相等時，公共而積占兩個圓總而積的百分比最小。證明：如圖兩圓，半徑/?, > r2 o因為 /?. > /?2,所以soi >so2又因為訂所臨綱£=l > 2k%（當(dāng)且僅當(dāng)s,】=s°2

10、即r產(chǎn)&時取等）。s°1 + s°2 + 沁s°考慮在一個無限大的平面內(nèi)采用兩種半徑k, r2的圓相交完全覆蓋平面。定義圓的有效利用率77 =實(shí)際兩圓在平面內(nèi)占的面積兩圓總而積k%s。 +s°2 _r%s°1s°1 + s°2（當(dāng)且僅當(dāng)s。嚴(yán)so2即r= r2時取等）。推論：兩i員i相交，滿足相交面積不小于一個整i員i面積的£%的條件下，當(dāng)兩 圓半徑相等時，圓冇效利用率最高。由定理4及推論，在采用的基k模型當(dāng)屮，我們選用圓半徑相同的情況。定理5：網(wǎng)絡(luò)拓?fù)浣Y(jié)果中任一節(jié)點(diǎn)a不能實(shí)現(xiàn)自身對外通信的充要條件為a 節(jié)

11、點(diǎn)所在的一跳覆蓋區(qū)內(nèi)無其他節(jié)點(diǎn)。四、模型建立和求解4.1基k模型算法要將邊長為1000的正方形區(qū)域用若干各半徑為100的圓完全覆蓋，圓與圓 z間必然相互交疊，從大止方形和圓的幾何形狀綜合考慮，我們提出基k模型 算法，來實(shí)現(xiàn)使用圓對正方形的完全覆蓋。算法思想：畫出每個圓的內(nèi)接正k邊形，使用正k邊形替代圓對正方形區(qū) 域進(jìn)行覆蓋。這樣便可以使正k邊形之間不發(fā)生重疊。滿足正k邊形之間無縫 連接時，只要 10002 （m：正k邊形個數(shù)，sj 個正k邊形的面積），即 可實(shí)現(xiàn)全覆蓋，當(dāng)然此時要考慮正k邊形超出正方形的面積。所以實(shí)際操作吋, 只要實(shí)現(xiàn)無縫拼接時沿水平垂直兩個方向每個正k邊形的有效貢獻(xiàn)乘以個數(shù)大

12、 于等于1000,即可實(shí)現(xiàn)全覆蓋，所需正k邊形個數(shù)即為兩個方向上的個數(shù)乘積, 也就是所需闘的個數(shù)。不難得知，正k邊形無縫拼接充要條件：正k邊形的角能夠整除36（7。下而針對不同k的取值，給出算法的具體實(shí)現(xiàn)：（1）當(dāng)k=3時，即為圓內(nèi)接止三角形，如圖所 示。圓半徑為100,可知正三角形邊長為iooa/3 ,正 三角形內(nèi)角為6（/,所以，可以實(shí)現(xiàn)無縫拼接。一個三 角形沿水平垂宜兩個方向的有效貢獻(xiàn)分別為503 , 150 （其中處在兩次邊界的三角形水平貢獻(xiàn)為，另一半處于三角形外）?？梢缘贸鏊椒较蛐枵切蝹€數(shù)為卩啤+ 1 = 13個，垂直方向需要的個數(shù)為50v3=7個。所以，若用i員i內(nèi)接正三角形

13、無縫無重疊覆蓋正方形所需的個數(shù)為13x7 = 91個。(2) 當(dāng)k=4時，即為圓內(nèi)接正方形，如圖所示。其邊t為100v2 ,內(nèi)角為9(t,也可實(shí)現(xiàn)無縫拼接。止方形若正放，沿兩個方向上的有效貢獻(xiàn)皆為 100血，個數(shù)為単1=8個，所以兩個方向上都需| 100v2 |要8個，總數(shù)為8x8 = 64個。所以垂直方向需要11個止方形，水平方向：第1,3, 5, 7, 9, 11 行需要5個，第2, 4, 6, 8, 10行需要6個，一共是60個。(3) 當(dāng)k = 5時，即為圓內(nèi)接正五邊形，其內(nèi)角為108無法整除360。，所以無縫實(shí)現(xiàn)無縫拼接。(4) 當(dāng)k=6吋，即為圓內(nèi)接正六邊形，如圖所示。其內(nèi)角為12

14、0。，可以實(shí)現(xiàn)無縫連接，邊長為100o垂直 方向貢獻(xiàn)150 (其中處于邊界的一個止六邊形僅貢獻(xiàn) 100),水平方向：奇數(shù)行有效貢獻(xiàn)為100命，偶數(shù)行， 首尾兩個六邊形有效貢獻(xiàn)為50的。所以垂直方向需要正六邊形的個數(shù)為器+匸7,水平方向共7行，奇數(shù)行每行需要6個,偶數(shù)行每行需要1000 100-150+ 1=7,所以總共需要正六邊正方形若與水平成45。放置，垂直方向的有效貢獻(xiàn): 處于邊界的兩個正方形共貢獻(xiàn)100,其余屮間部分每個 正方形貢獻(xiàn)100,水平方向的貢獻(xiàn)：奇數(shù)行貢獻(xiàn)200； 偶數(shù)行兩個邊界的正方形各貢獻(xiàn)100,其余貢獻(xiàn)200。形個數(shù)為45個。(5) 當(dāng)27時，圓內(nèi)接正k邊形的內(nèi)角必然大于

15、120。且小于1妙,可知無法整除360“。所以，只要圓內(nèi)接止k邊形邊數(shù)大于等于7,就無法時間無縫拼接了?；鵮模型的優(yōu)點(diǎn)：（1）基k模型有效的解決了使用圓形完全覆蓋正方形的問題，實(shí)現(xiàn)了無縫 拼接。（2）一個正k邊形對應(yīng)一個圓，可以方便的計算出對任意區(qū)域不同方式全 覆蓋時所需耍的i員i的個數(shù)。（3）圓內(nèi)接正k邊形的一條邊與圓圍成的弓形，即為相鄰兩個圓的公共面 積的一半，可以方便解決不同公共面積大小的需求。4.2基6模型分析（滿足相交面積不小于5%的要求）我們選用如下圖所示的基6模型小單元，4.2.1垂直方向如果只有一行，覆蓋矩形區(qū)域的高為以后每增加一行，其步進(jìn)距離為 h=i.5r,所以當(dāng)水平有加行

16、時，能夠覆蓋的有效矩形高度為y = hi（m_v）r + r = 1.5m/?-0.5/?4.2.2水平方向如果只有一列，其覆蓋矩形長度為術(shù)/?（從上向下每行鬪個數(shù)依次上 12121.）,以后每増加一列（每行圓數(shù)壇加1）,能步進(jìn)距離也r,所以當(dāng) 豎值有h行時，能夠覆蓋的有效矩形長度為x = hn-l）r + y/3r = y/3nr4.2.3基6單元排布（正方形區(qū)域）正方形區(qū)域x = y = 1000j x = y/3nr則由兩式y(tǒng) = l,5mr-0.5/?又因為/?只能取75100 z間的數(shù)值，加，取正整數(shù)。我們采用兩種方案尋找較優(yōu)的加，n以及r方案（1）：固定式的血值，計算出再代入式計算

17、值，對n向上取 整，然后再由m, n的值，計算出所需圓的個數(shù)。mnr所需圓個數(shù)半徑總和761004545008786.96605217.69876.92765845.9方案（2）：固定式的弘計算出/?,再代入式計算加值，對加向上取整, 然后再由加，川的值，計算出所需i員i的個數(shù)，再由個數(shù)乘以半徑得到半徑總和, 計算結(jié)果如下表。nmr所需圓個數(shù)半徑總和6896.26525005.57982.48675526.24.2.4結(jié)論:由上面兩種方案分析可以看出，/?在75100之間隨意變動時，半徑總和隨 著/?的增大而變小，兩者成反比。所以，對于問題2建立的目標(biāo)函數(shù)使全部圓半徑z和為最小，總體上采用/?

18、 = 100的基6模型進(jìn)行區(qū)域分劃。4.2.5信道分配方案給上圖紅、綠、藍(lán)三種顏色的圓分別賦予不同的信道，由于相同顏色的圓沒 有相交的情況。故使用3種信道即可以保證通信。4.2.6基6模型網(wǎng)絡(luò)抗毀性分析定義：網(wǎng)絡(luò)的抗毀性，即從節(jié)點(diǎn)集合中隨機(jī)的抽取若干數(shù)量的節(jié)點(diǎn)后網(wǎng)絡(luò)是 否仍然連通。由定理5,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)屮任一節(jié)點(diǎn)依靠與之相鄰的若干節(jié)點(diǎn)（即一跳覆蓋區(qū)中的節(jié)點(diǎn)）中轉(zhuǎn)從而實(shí)現(xiàn)對外通信。對于基6模型，任一節(jié)點(diǎn)a的一跳覆蓋區(qū)中的其余節(jié)點(diǎn)個數(shù)m可以取3, 4, 5等數(shù)值。一旦同時抽取了 a的這m個節(jié)點(diǎn)，a將無法通信。對應(yīng)于m,我們 計算出圖1屮符合條件的a的節(jié)點(diǎn)數(shù)n,見下表。a相鄰節(jié)點(diǎn) 個數(shù)m3456 符

19、合條件的a的個數(shù)n1012845 根據(jù)基6模型，我們做出了全部155個節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，如圖7所示。半徑為100的圓覆蓋正方形下面分析隨機(jī)的從基6模型網(wǎng)絡(luò)小抽取k個節(jié)點(diǎn)后網(wǎng)絡(luò)的連通性。觀察上面兩圖即可發(fā)現(xiàn)，因為m最小值為3,即某些節(jié)點(diǎn)當(dāng)抽取其周圍僅有的m = 3個節(jié)點(diǎn)后，該節(jié)點(diǎn)即失去其連通性。而符合這個最壞情況的節(jié)點(diǎn)a共冇n= 10個。我們采用概率統(tǒng)計的方法對網(wǎng)絡(luò)抗毀性進(jìn)行分析。當(dāng)抽取節(jié)點(diǎn)數(shù)為k的時 候，對滿足m<k的節(jié)點(diǎn)，都冇口j能因一跳覆蓋區(qū)的m個節(jié)點(diǎn)被抽取而脫離網(wǎng) 絡(luò)。對于這樣的節(jié)點(diǎn)a,我們計算其脫離網(wǎng)絡(luò)的概率。(1) k=3：154(2) k=4：154154(3) k=5：

20、x 晉+護(hù)+*c154c154c154(4) k=6：門ioc；12c：8c；45r = + + +6廠3廣4廠5廠6c154c154c154c154(5)當(dāng)k的值取得比較大時，影響概率的主要是前幾項，這里取前三項。幾乎+護(hù)+獸c154c154c154用matlab計算出相應(yīng)的k值與人之間的關(guān)系曲線圖如下所示。因為網(wǎng)絡(luò)的節(jié)點(diǎn)個數(shù)為155個，隨機(jī)抽取2%, 5%, 10%, 15%的點(diǎn)的個數(shù)依次為4個，8個，16個，24個。由上面分析，其導(dǎo)致網(wǎng)絡(luò)不連通的概率如卜表所示。網(wǎng)絡(luò)隨機(jī)抽取比例2%5%10%15%抽取節(jié)點(diǎn)個數(shù)（k）481624導(dǎo)致網(wǎng)絡(luò)不連通的概率以0.00662%0.00957%1.02

21、%3.96%當(dāng)抽取60個節(jié)點(diǎn)，即抽取比例為38.71%時，網(wǎng)絡(luò)變的一定不連通。4.3基4模型分析（滿足相交面積不小于18%的要求）我們選用如下圖所示的基4模型小單元，4.3.1垂直方向主要考慮要覆蓋住正方形區(qū)域的上下邊界。我們用紅圓來實(shí)現(xiàn)，至少需要5 列，6行。水平跨度為800,垂直跨度為1000。4.3.2水平方向主要考慮要覆蓋住正方形區(qū)域的左右邊界。我們用綠圓來實(shí)現(xiàn)，至少需要5 行，6列。水平跨度為1000,垂直跨度為800o這樣采用了雙色圓如上圖排列，垂直方向和水平方向互相彌補(bǔ)，覆蓋住了正 方形所有的區(qū)域，實(shí)現(xiàn)了最有覆蓋。所用圓個數(shù)為：5x6x2 = 60。4.3.3信道分配方案給上圖紅

22、、綠兩闘分別賦予不同的信道，由于相同顏色的i員i相切沒有公共的 區(qū)域，不同顏色的圓恰好滿足18%的公共面積，所以使用兩種信道即可保證通 信。444基4模型網(wǎng)絡(luò)抗毀性分析根據(jù)分析基6模型的思想，我們同樣統(tǒng)計了基4模型（圖6）的節(jié)點(diǎn)個數(shù)共計 160 個。對于基4模型，任一節(jié)點(diǎn)a的一跳覆蓋區(qū)中的其余節(jié)點(diǎn)個數(shù)m可以取3, 4, 5等數(shù)值。一旦同時抽取了 a的這m個節(jié)點(diǎn)，a將無法通信。對應(yīng)于m,符合 條件的a的節(jié)點(diǎn)數(shù)記為n,兩者關(guān)系見下表。a相鄰節(jié)點(diǎn) 個數(shù)m3456 符合條件的a的個數(shù)n1012845 用matlab計算出相應(yīng)的k值與pk之間的關(guān)系曲線圖如下所示。因為網(wǎng)絡(luò)的節(jié)點(diǎn)個數(shù)為160個，隨機(jī)抽取2

23、%, 5%, 10%, 15%的點(diǎn)的個數(shù)依次為4個，8個，16個，24個。由上面分析，其導(dǎo)致網(wǎng)絡(luò)不連通的概率如下表所示。網(wǎng)絡(luò)隨機(jī)抽取比例2%5%10%15%抽取節(jié)點(diǎn)個數(shù)（k）481624導(dǎo)致網(wǎng)絡(luò)不連通的概率人1.37%6.41%27.97%66.52%當(dāng)抽取29個節(jié)點(diǎn)，即抽取比例為18.12%時，網(wǎng)絡(luò)變的一定不連通。4.5問題1的解答采用半徑為100的圓對正方形區(qū)域進(jìn)行完全覆蓋（1）若耍求相鄰兩個圓的公共部分而積不小于一個圓而積的5%,最少需要45個 圓。若給每個圓分配一個信道，使得有公共部分的圓擁有不同的信道，最少 需要3個信道，信道分配見下圖。使用了 3種信道（如圖用紅、綠、藍(lán)三種 顏色代

24、替），可以保證有公共部分的一跳覆蓋區(qū)使用不同的信道進(jìn)行通信。從節(jié)點(diǎn)集合中隨機(jī)抽掉2%、5%、10%、15%的節(jié)點(diǎn)后，導(dǎo)致網(wǎng)絡(luò)不連通的 概率依次為:0.00662%、0.00957%、1.02%、3.96%。（2）若要求相鄰兩個圓的公共部分面積不小于一個圓面積的18%,最少需要60 個圓（見下圖）。若給每個圓分配一個信道，使得有公共部分的圓擁有不同 的信道，最少需要2個信道，信道分配見下圖。使用了 2種信道（如圖用紅、 綠網(wǎng)種顏色代替），可以保證有公共部分的一跳覆蓋區(qū)使用不同的信道進(jìn)行 通信。從節(jié)點(diǎn)集合屮隨機(jī)抽掉2%、5%、10%、15%的節(jié)點(diǎn)后，導(dǎo)致網(wǎng)絡(luò)不 連通的概率依次為：1.37%、6.4

25、1%、27.97%、66.52%。4.6問題2的解答4.6.1引理一：在半徑范圍為7510（）的i員i相交后，如杲半徑大的i員i滿足相交弦 所對的圓心角大于57.1度（或者大于60度），那么無論小圓的半徑是多少，都 滿足相交后面積大于大圓面積的5%o證明：如下圖，顯然，當(dāng)大圓與小圓相交的時候，同樣的相交弦，大圓所對 應(yīng)的弓形而積a必然小于小圓所對應(yīng)的弓形而積b。當(dāng)兩個大圓相交時，如果 圓心角都是57度的時候，相交的面積剛好為大i員i面積（兩個都是大i員i）的5%； 現(xiàn)在一個換成了小圓，相交的面積會增大，即a + b的面積會大于大圓面積的 5%。所以大圓與小圓相交的時候，只需要注意大圓的圓心角在

26、57.1度以上，就 可以保證相交面積大于大圓面積的5%。57.1根據(jù)這個引理，我們可以計算出兩個不同半徑的圓的圓心距，本題我們先用 半徑為100的大圓覆蓋整個1000x1000的正方形，遇見湖而后，去掉湖里而的 闘心，這樣必然會使一部分湖周圍的面積不在覆蓋區(qū)內(nèi)，需要向那些面積中投放 新的比較小的半徑的圓。其中的極限情況是加入了半徑為75的小圓，這樣的話, 計算出來的圓心距為162.5207,所以當(dāng)小圓半徑在75100之間活動的吋候，圓 心距在162.5207173.2之間活動。所以加入小圓的時候，只需要保證加入的小 圓與大圓z間的圓心距大于162.5207,則可以保證相交而積為大圓而積的5%。

27、 4.6.2湖泊的處理橢圓形湖泊中心在（550, 550）,長軸與正方形水平的成30度角。長軸為 410,短軸為210,其與用半徑為/?=100的圓進(jìn)行區(qū)域分劃后的相對位置圖像如 下圖所示：可以看到將湖泊屮的節(jié)點(diǎn)（圓）去掉后，湖泊周圍出現(xiàn)了幾塊未能覆蓋的區(qū) 域。因為 /?=100, m = 7, /2 = 5.77 （取整后 =6）。所以覆蓋了止方形區(qū)域的基6模型，在水平方向存在冗余，在豎直方向布存 在。即在水平方向可以輕微的左右移動。我們利用matlab進(jìn)行水平微調(diào)處理后，使圓心未被覆蓋的區(qū)域面積盡量少。 這樣，我們對未被覆蓋的區(qū)域再用半徑較小的圓進(jìn)行覆蓋，并滿足公共相交面積 不小于大圓而積

28、的5%的要求，最后做出的區(qū)域分劃圖如下，半徑總和為4450。信道分配方案仍采用3信道。4.7問題3的解答：前面兩問分析了采用基6模型的靜態(tài)區(qū)域分劃方案。靜態(tài)區(qū)域分劃方案雖然 可以保證處于正方形區(qū)域的節(jié)點(diǎn)在任意位置都可以實(shí)現(xiàn)通信，但由于其未考慮吋 間節(jié)點(diǎn)的分別情況，因而覆蓋圓的個數(shù)及半徑存在冗余。對于附件1給岀的數(shù)據(jù)作為靜止節(jié)點(diǎn)，我們采用基于節(jié)點(diǎn)的劃分方式。（-）無湖情況分析我們給出如下分析步驟：第一步：采用漫路分簇算法，將正方形區(qū)域內(nèi)的926個節(jié)點(diǎn)進(jìn)行分簇；第二步：建立基于模擬退火的圓心飄移模型，對整個分簇之后的圓一跳覆蓋區(qū)域 進(jìn)行圓的位置調(diào)整，去除位置冗余；第三步：建立最小圓覆蓋模型，對于每

29、一個一跳覆蓋區(qū)進(jìn)行半徑調(diào)整，去除半徑 冗余；第四步：對調(diào)整之后的一跳覆蓋區(qū)，檢驗是否滿足兩個限制條件：節(jié)點(diǎn)的連通性 和有轉(zhuǎn)發(fā)任務(wù)的節(jié)點(diǎn)面積不小于大圓面積的5%。若滿足，轉(zhuǎn)向第五步；若不滿 足，增大半徑進(jìn)行再次檢驗；第五步：計算岀每個一跳覆蓋區(qū)對應(yīng)的圓的半徑、圓的個數(shù)，求出全部一跳覆蓋 區(qū)半徑之和。(1)針對第一步：我們提出如下漫路分簇算法。算法： 對附錄中926個節(jié)點(diǎn)，首先按橫坐標(biāo)的大學(xué)進(jìn)行排序，形成926x2的節(jié)點(diǎn)矩 陣a。 初始化生成50x2的零矩陣b和926x2的零矩陣c。 將a的笫一個節(jié)點(diǎn)a (1)放到b中，b中節(jié)點(diǎn)的重心o為b (l)o 依次取a中第k個節(jié)點(diǎn)a (k), k = 2,

30、 3,，926,比較a (k)與重心o之 間的距離d,若dw200,則將a (k)放到矩陣b中并重新計算b中所有節(jié)點(diǎn) 重心o；若d>200,則將a (k)放到c中。 若矩陣c全為0,則程序停止，若c非0,則將矩陣c全部賦給矩陣a,重新 進(jìn)行的計算。采用漫路分簇算法后的節(jié)點(diǎn)劃分圖如下：原始圖02004006008001000由48個大圓組成，大圓半徑為100,半徑z和為4800。可以看到，分簇后都采用半徑為r=100的圓覆蓋是不合理的，并且簇與簇 之間覆蓋圓存在圓位置的冗余和圓半徑長度帶來的冗余。因此，我們采取下面處 理方式除掉這兩塊兀余。（2）基于模擬退火的圓心漂移模型保持一跳覆蓋區(qū)的半

31、徑r=100不變，對于某一個一跳覆蓋區(qū)m,其圓心坐 標(biāo)為（兀"兒），內(nèi)部的節(jié)點(diǎn)為加個（分別為，燈）。我們隨機(jī)產(chǎn)生一個小 的增量込”,a）；”，使覆蓋區(qū)m的圓心坐標(biāo)移至（?！?心加兒+ay），以此圓心 做半徑為r=100的圓，計算其內(nèi)部所包含的節(jié)點(diǎn)的個數(shù)叫。若新形成的圓不能 包含原來的加個節(jié)點(diǎn)«,心，,匕，則放棄此次調(diào)整；若新形成的i員i包含了原來的 m個節(jié)點(diǎn)，則進(jìn)行下一步分析m與s的關(guān)系。若加（）m ,將圓心依一個小概率移至（，九+兒）處；若叫 m ,則令叫=m ,并將圓心依一個較大概率移至（?！?+, ym + avw ）。無湖全大圓情況結(jié)果如下圖所示：100090080

32、0700600500400300200100002004006008001000圖中只需要40個大圓，圓半徑為100,半徑之和為4000o可以看擊，基于 模擬退火的圓心漂移模世冇效的去除了由丁圓的位置兎疊帶來的兀余。（3）建立最小圓覆蓋模型在本步驟中我們主要去除曲于某些一跳覆蓋區(qū)半徑r過人引起的冗余。分析某一跳覆蓋區(qū)m,圓心q”為（?！本牛?，半徑為r,連接圓心乙與節(jié)點(diǎn)處,交圓于弘記 = 0“£一0北=r-臥建立口標(biāo)函數(shù)求使得d為最小的圓心（乙，兒）和半徑心。;=1（4）對于限制條件的解決限制條件1：由轉(zhuǎn)發(fā)任務(wù)的相鄰一跳覆蓋區(qū)公共面積不小于較大一跳覆蓋 區(qū)而積的5%；限制條件厶所有節(jié)點(diǎn)

33、連通。對于某一跳覆蓋區(qū)m,記其周圍相鄰的一跳覆蓋區(qū)有刃個，分別為（/=1,，n） o定義兩個集合：d=被包含的節(jié)點(diǎn)；d, = 被m包含的節(jié)點(diǎn) o若經(jīng)過（1）（2）（3）的處理后，dm o d ,則將一跳覆蓋區(qū)m去掉;若dm a d , 則保留mo分別記冏（j=l,，m）的圓心坐標(biāo)為q （i=l,，）,m的圓心為q”。下而分析如何滿足限制條件1：大圓半徑為r,小圓半徑為門記 s（）=5%r2 極限條件下為小圓面積2=s°=5%臨f,則- = v05o即當(dāng)兩不等圓半r徑z比（小的比大的）73厲時，限制條件1不能滿足。若- = voi）5,小r圓被大圓完全包圍，小圓的作用完全消失，如圖。

34、卜面分析小圓遠(yuǎn)離大圓運(yùn)動，遠(yuǎn)離過程中口身半徑變大，當(dāng)兩圓心z間距離 為侖/?時，小圓半徑r等于大圓半徑r,如圖所示。恰為前面討論的基6模 型的一個小單元。 當(dāng)兩圓圓心之間距離d滿足(l-vo05)/?<j<v3/? dt,小圓的弦相對的圓心角為20,大圓為2a,弦長一半為仁a = arcsin r0 = arcsin r-r22a-r2sn2a + -r226-r2sn23 = 5%7rr22 2 2 2r2 arcsin -ljr，一卩 + r arcsin-llr2 -i2 = 5%7tr2rr由可得r, r與/的關(guān)系，由式可以求出/的值。/已知，則可以求出圓心距d = v/?

35、2-/2+vr2-/2所以對于一跳覆蓋區(qū)m周圍的n個相鄰覆蓋區(qū)找出至少有一個d = °” -q滿足式的關(guān)系。下而分析如何滿足限制條件2：設(shè)一跳覆蓋區(qū)m與周圍的斤個覆蓋區(qū)m, (z=l, n)相交區(qū)域為4 (i =1,，m),定義bj=4中的節(jié)點(diǎn)數(shù)。若bub2uub”h0則可滿足條件2；若不滿足，則采取擴(kuò)大m半徑的方式來尋求式的滿足。若擴(kuò)大m半徑至100仍不滿足式，則隨機(jī)抽取擴(kuò)大其半徑直至式滿 足。無湖大小圓情況經(jīng)過上述步驟處理后，我們得到了無湖情況卜全部一跳覆蓋半徑z和為最小 的一跳覆蓋區(qū)劃分方案。如下圖所示。1000900800700600500400300200100其中半徑為1

36、00的圓30個，半徑為98、95、85、77的圓分別為2個，半徑 為83、72、60各1個，總共41個圓，半徑之和為3925。其相應(yīng)圓的圓心處標(biāo) 見附錄。信道分配仍采用3信道通信。（-）有湖情況有湖時，節(jié)點(diǎn)數(shù)目由926個變?yōu)?66個。具體實(shí)現(xiàn)算法和無湖時大致相同， 只是在對節(jié)點(diǎn)進(jìn)行分簇之前，首先要將落在湖中的節(jié)點(diǎn)去掉，再進(jìn)行類似于無湖 情況的處理：基于漫路算法的分簇處理；基于模擬退火的圓心漂移模型的去除圓 位置兀余；基于最小圓覆蓋模型的去除圓的半徑長度兀余；限制條件的檢驗等， 在此不再贅述。侑湖泊）大小圓情況處理z后的結(jié)果如21000900800700600500400300200100其中半

37、徑為100的圓32個，半徑為90、80的圓各2個,半徑85的圓1個, 總共37個圓,半徑之和為3625o4.8問題4的解答:（1）節(jié)點(diǎn)運(yùn)動一次概率分布對任一運(yùn)動的節(jié)點(diǎn)分析其一次運(yùn)動后的情況，以運(yùn)動前位置為坐標(biāo)原點(diǎn)。 因為節(jié)點(diǎn)£運(yùn)動方向角，速度服從0,2刃，0, 2上的均勻分布，所以一次運(yùn)動 后p必落在半徑為60的圓內(nèi)，并11對于固定的環(huán)環(huán)寬度d, pj落在兩個圓環(huán)%內(nèi)的概率相等。設(shè)p沿原點(diǎn)向外分布的概率密度為p(r) r 0,6060貝|j f(廠)=>(/)(/+ &)2_尸=«(/)*2伽0 0i f(0) = 0f(60) = 1 所以，p(t) = -

38、9 2cr =,得出 c =一，t60120c1所以p(r) = - =re 0,60r 120rf(廠)=右 y0,604.9問題5的解答：(1)能量與傳輸距離關(guān)系設(shè)節(jié)點(diǎn)處于發(fā)射、接收和備用三種狀態(tài)下功率分別為片,£，人，月.人：£：£ =11:10:1。令人=1 比肝，則p2=10kd39 p3=kd3o節(jié)點(diǎn)在r= 100發(fā)送狀態(tài)下工作總時間為400個時間單位，節(jié)點(diǎn)總能量e為e = pt = l r,/?3 *400 = 4.4 *109則節(jié)點(diǎn)總能量e與傳輸距離d的關(guān)系為e = pxt = kxd3,(2) 通信次數(shù)與傳輸距離的關(guān)系節(jié)點(diǎn)i與節(jié)點(diǎn)j的原始通信次數(shù)

39、設(shè)為® ,令代吟每個節(jié)點(diǎn)平均產(chǎn)生25次呼出，必然對應(yīng)平均25次呼入。926 925©=25*2*926z=1 jw=l解上述兩個方程可得込=30273027no =(3) 網(wǎng)絡(luò)節(jié)點(diǎn)運(yùn)行能力與一跳覆蓋區(qū)半徑關(guān)系對于r=100,發(fā)送狀態(tài)下工作總時間為400個時間單位，取e = 400o在平 均意義上，每個節(jié)點(diǎn)平均產(chǎn)生25次呼出必有25次接收，每次通信時間平均為4 個單位時間。w3=p3t3 = p3(1200-t-t2) =1000tt=91h*100 = 91wj +w2+w3 =282 <400故r=100的圓作為一跳覆蓋區(qū)在平均意義下網(wǎng)絡(luò)可以運(yùn)行1200個時間單 位

40、。下面分析半徑r減小到任一節(jié)點(diǎn)可以保持在最高功率工作1200個時間單位 的狀況。對于節(jié)點(diǎn)其中為中轉(zhuǎn)。因為中轉(zhuǎn)時既需要接收也需要發(fā)射，故中轉(zhuǎn)節(jié)點(diǎn)工作時其功率&)=(11 + 10)你/3=2比夕，所以全部工作持續(xù)時間為*400,所以若想其工21作1200個時間單位，其最遠(yuǎn)發(fā)射距離為21任(心a j * 100 = 2 比 * 100? * 耳 * 400解得尺杯=55.9所以當(dāng)圓半徑/?<55.9時，可以保證網(wǎng)絡(luò)中任一節(jié)點(diǎn)在任何條件下運(yùn)行1200 個單位吋間。(4) r,網(wǎng)絡(luò)節(jié)點(diǎn)平均距離7與中轉(zhuǎn)點(diǎn)個數(shù)的關(guān)系:926 926廠 527.86計算網(wǎng)絡(luò)中926個節(jié)點(diǎn)的平均距離所以在7長度

41、下，屮轉(zhuǎn)點(diǎn)個數(shù)m考慮到時間傳送繞路,d0rrr+血r+血r + 2血 屮轉(zhuǎn)點(diǎn)n012 1(925)2/=1 >1考慮在一排平行圓排列情況可以看出每增加的/?長度，其中轉(zhuǎn)點(diǎn)個數(shù)增1。取"=備。節(jié)點(diǎn)m,實(shí)現(xiàn)對目標(biāo)憶一次通信消耗的網(wǎng)絡(luò)能量為£, =(ll + 10+21n)/?3f = 84(/? +1* r3兩節(jié)點(diǎn)z間平均通信次數(shù)列=務(wù)嚶dij dij3027m,通信一次引起的網(wǎng)絡(luò)的總能量消耗e = e、nff = 84代+ 1腫 °2784 g-yr疋+ 3027咖嗚r3總能耗e取值越少，則整個網(wǎng)絡(luò)的能耗越少。(5) 網(wǎng)絡(luò)節(jié)點(diǎn)退出分析t（t） =926 926

42、 一 /? l一亍離 j= 252.55平均每個中轉(zhuǎn)點(diǎn) e“.261200 e25（ v + 仔）+ （彳 + 停）* 5.26 + 出（1200 - 50f -10.52/）1200e當(dāng)/一時，° = 0 k其中：k = 2.0872e a = 2.08724.10問題6的解答在問題(5)中，已經(jīng)計算出了網(wǎng)絡(luò)中存在轉(zhuǎn)發(fā)任務(wù)的節(jié)點(diǎn)大約是46個，每 個節(jié)點(diǎn)在整個網(wǎng)絡(luò)運(yùn)行時間內(nèi)在平均的轉(zhuǎn)發(fā)任務(wù)是5.26個。因為網(wǎng)絡(luò)屮任務(wù)最為繁忙的是有轉(zhuǎn)發(fā)任務(wù)的節(jié)點(diǎn)，因此網(wǎng)絡(luò)屮其它節(jié)點(diǎn)相對 于轉(zhuǎn)發(fā)節(jié)點(diǎn)的通信也最不容易滿足，即最容易丟包。兩節(jié)點(diǎn)z間平均通信次數(shù)®=¥=攀,%5取 n.=3

43、027在平均距離下一次通信引起的轉(zhuǎn)發(fā)點(diǎn)個數(shù):n = l-v3/?所以由通信概率加權(quán)后的一次通信引起的轉(zhuǎn)發(fā)點(diǎn)個數(shù)為:_ _ 3027 d _ 3027可見，因為d為常數(shù)，所以通信一次引起平均轉(zhuǎn)發(fā)點(diǎn)的個數(shù)與使用的一跳覆 蓋區(qū)的半徑成反比。五. 模型評價及改進(jìn)模型優(yōu)點(diǎn)： 在對正方形區(qū)域進(jìn)行節(jié)點(diǎn)劃分過程中，針對所有圓半徑最小的目標(biāo)要求，我 們的模型建立了完善的算法（漫路分簇算法、模擬退火的圓心漂移算法和最 小覆蓋圓算法），這是木模型的第一大特色。 該模型冇嚴(yán)格的理論基礎(chǔ)，在模型分析中，將本題實(shí)際和經(jīng)典的數(shù)學(xué)理論結(jié) 合在一起是該模型的又一一大特色。在嚴(yán)格的數(shù)學(xué)定理、定律的支持下，下 面的討論變得充分有力

44、。 模型充分論證了基k模型，通過分析計算，從k的取值屮挑選出適合5%要 求的基6模型和適合18%要求的基4模型，并且反面說明了其它基k模型存 在的不足。通過正反對比，得出基k （k=4、6）是較優(yōu)的解決該問題的工具。模型不足：我們的模型仍然存在很大的不足，主要體現(xiàn)在一下兒個方面： 最大的不足是在用模擬退火進(jìn)行尋找半徑z和最小時，無法證明結(jié)論達(dá)到全局最優(yōu)。這也是該類模型最大的一個理論證明上的不足。 對問題4、5、6的論證不是很充分。下面我們對模型進(jìn)行少許的改進(jìn)：根據(jù)移動通訊的蜂窩模型，針對相交面積比例是5%的要求，我們提出了圓 心為頂點(diǎn)的正六邊形排列方式，繪制出了如下的圖，如圖1,這種方法排列需

45、要 45個半徑為100的圓，圓心距為巧計算其每兩個相交圓之間的比例占圓面 積的5.5%,符合題意。當(dāng)相交面積的比例由5%增大到18%的時候，我們提出 了正四邊形的排列方式，如圖2,這種方法排列需要60個半徑為100的圓，圓 心距為血尺。這種排列口j以是相交面積比例可以達(dá)到18.2%,也剛好滿足要求。推廣：我們看到第二幅圖中有49個圖完全占據(jù)了大多數(shù)的正方形面積，只 剩下兩個1000x10的窄矩形窗口，如果再用半徑為100的圓覆蓋，是非常浪費(fèi) 的，于是我們考慮，是否能將圓心距稍微增大（即犬于近r）,這樣所有的圓就有可能全部覆蓋住止方形區(qū)域。鑒于時間的原因，在此未能做進(jìn)一步的分析和討 論。圖1圖2

46、有窄圖3曲于時間的原因，論文還冇很多值得改進(jìn)的地方，懇請老師批評改正。參考文獻(xiàn)：1 姜啟源，謝金星，葉俊.數(shù)學(xué)模型(第三版)，高等教育出版社。2 楊中華.平面點(diǎn)列最小覆蓋圓的計算方法，北京工業(yè)大學(xué)學(xué)報, 2000,vol.26(2).3 蔡鎖章.數(shù)學(xué)建模原理與方法，海軍出版社。附錄部分程序清單：1無湖泊半徑為100的圓所截節(jié)點(diǎn)圖(x,y為附錄中節(jié)點(diǎn)坐標(biāo))plot(x；yjb);axis equal;axis(0 1000 0 1000);山1*(無湖泊)半徑為10()的圓所截節(jié)點(diǎn)圖jhold onfor m=-9:9for k=-5:5t=0:pi/200:2*piplot( 100*cos(

47、t)+500)+100*sqrt(3)*k-50*sqrt(3)*m,( 100*sin(t)+500)+150*m,t)endend2. 冇湖泊半徑為100的関所截節(jié)點(diǎn)圖t=0:(pi/100):2*pi;a=550+205*cos(t);b=550+105*sin(t);c=cos(-pi/6)*205*cos(t)+sin(-pi/6)* 105*sin(t)+550;d=-sin(-pi/6)*205 *cos(t)+cos(-pi/6) * 105 *sin(t)+550;% c;d=lcos(pi/6),sin(pi/6);-sin(pi/6),cos(pi/6)*la;bj;pl

48、ot(c,d,k);for i= 1:926訐(sqrt(3)*(x(i)-550)/2+(y(i)-550)/2).a2/205.a2+(-(x(i)-550)/2+sqrt(3)*(y(i)-550)/2).a2/105.a2-l<0 plot(x(i),y(i)；w/);elseendendtitlcc(冇湖泊)半徑為100的圓所截節(jié)點(diǎn)圖)hold onfor m=-9:9for k=-5:5t=0:pi/200:2*piplot(100*cos(t)+500)+ 100*sqrt(3)*k-50*sqrt(3)*m,( 100*sin(t)+500)+150*m,t)endend

49、hold ont=0:pi/200:2*piplot( 100*cos(t)+500,100*sin(t)+500,'w.')t=0:pi/200:2*piplot( 100*cos +500+50*sqrt(3), 100*sin(t)+500+150,'wj)t=0:pi/200:2*pi plot(sqrt(3)*50*cos(t)4-50()4-50*sqrt(3),50*sqrt(3)*sin(t)4-500+200,'g')3. 網(wǎng)絡(luò)抗毀分析程序：for k= 1:62y=10*k*(k-l)*(k-2)/(155*154*153)+12*k

50、*(k-l)*(k-2)*(k-3)/(155*154*153*152)+8*k*(k-l)*(k- 2)*(k-3)*(k-4)/(155*154*153*152*151)+45*k*(k-l)*(k-2)*(k-3)*(k-4)*(k-5)/(155*154*153*152*151*150)plot(k,y；r.')hold onend4. 有湖時補(bǔ)圓程序：t=0:(pi/100):2*pi;a=550+205*cos(t);b=550+105*sin(t);c=cos(-pi/6)*205*cos(t)+sin(-pi/6)*105*sin(t)+550;d=-sin(-pi/6

51、)*205 *cos(t)+cos(-pi/6) * 105 *sin(t)+550;% c;d=cos(pi/6),sin(pi/6);-sin(pi/6),cos(pi/6)*a;b;plot(c,d,k);axis equal;axisdo 1000 0 1000j);hold onfor i= 1:926訐(sqrt(3)*(x(i)-550)/2+(y(i)-550)/2).a2/205.a2+(-(x(i)-550)/2+sqrt(3)*(y(i)-550)/2).a2/105.a2-l<0 plot(x(i),y(i)；w?);elseendendhold onfor m=-9:9for k=-5:5t=0:pi/200:2*piplot( 100*cos(t)+50)+300*k+150*m,( 100*sin(t)+50*sqrt(3)+100*sqrt(3)*m,'r*)endendhold onplot( 100*cos(t)+