Ad Hoc網(wǎng)絡(luò)中的區(qū)域劃分和資源分配問(wèn)題第五組.doc

Ad Hoc網(wǎng)絡(luò)中的區(qū)域劃分和資源分配問(wèn)題1 問(wèn)題重述隨著人們對(duì)擺脫有線網(wǎng)絡(luò)束縛、隨時(shí)隨地進(jìn)行自由通信的渴望，近幾年來(lái)無(wú)線網(wǎng)絡(luò)通信得到了迅速的發(fā)展。為了能夠在沒(méi)有固定基站的地方進(jìn)行通信， Ad Hoc網(wǎng)絡(luò)技術(shù)應(yīng)運(yùn)而生。Ad Hoc網(wǎng)絡(luò)不需要有線基礎(chǔ)設(shè)備的支持，通過(guò)移動(dòng)主機(jī)自由的組網(wǎng)實(shí)現(xiàn)通信。就其特點(diǎn)，在給定一些限制條件下，本文提出了關(guān)于如何合理劃分 Ad Hoc網(wǎng)絡(luò)中的區(qū)域和分配資源問(wèn)題。具體內(nèi)容如下：對(duì)一個(gè)指定10001000(面積單位)的正方形區(qū)域內(nèi)構(gòu)建一個(gè)Ad Hoc網(wǎng)絡(luò)，需解決以下問(wèn)題：(1) 以圓的形式對(duì)正方形區(qū)域進(jìn)行覆蓋，在滿(mǎn)足所給定的限制條件下，通過(guò)建立最小半徑和模型，求得圓的最少個(gè)數(shù)。若給每個(gè)圓分配一個(gè)信道，使得有公共部分的圓擁有不同的信道，在此條件下合理分配信道。改變公共面積部分的限制條件，重復(fù)上述問(wèn)題。再根據(jù)條件，提出合理假設(shè)，討論網(wǎng)絡(luò)的抗毀性問(wèn)題。(2) 設(shè)正方形區(qū)域中有一滿(mǎn)足給定條件的橢圓形湖泊。由限制條件：節(jié)點(diǎn)僅能設(shè)置在地面上，以及假設(shè)條件：一跳覆蓋區(qū)圓的半徑可以在75100間隨意選擇，兩個(gè)面積不等的圓相交，它們之間的公共面積應(yīng)不小于大圓面積的5%，建立最小半徑和模型，研究合理的區(qū)域分劃和信道分配方案。(3) 在假設(shè)一個(gè)較短的時(shí)間間隔內(nèi)，網(wǎng)絡(luò)的連通性可能并未變化的情況下，采用基于節(jié)點(diǎn)的劃分方式，在某一時(shí)刻將正方形區(qū)域內(nèi)的節(jié)點(diǎn)（用戶(hù)）分成若干個(gè)簇。給出簇與一跳覆蓋區(qū)的定義，并根據(jù)給定條件結(jié)合數(shù)據(jù)，建立半徑最小和模型，研究一跳覆蓋區(qū)劃分和信道分配方案，找出區(qū)域連通的充分、必要條件，并討論網(wǎng)絡(luò)抗毀性。(4) 在問(wèn)題3的基礎(chǔ)上作進(jìn)一步假設(shè)，根據(jù)所給的條件，考慮在動(dòng)態(tài)情況下，通過(guò)建立模型，考慮網(wǎng)絡(luò)連通性問(wèn)題。(5) 基于前面（3）中所給辦法，從節(jié)能角度出發(fā)，根據(jù)所給條件，建立能量消耗與其所處位置關(guān)聯(lián)的求極值模型，找到比較節(jié)能的區(qū)域分劃方式，使出現(xiàn)第一個(gè)退出網(wǎng)絡(luò)的節(jié)點(diǎn)的時(shí)間盡量長(zhǎng)。并通過(guò)對(duì)該網(wǎng)絡(luò)的運(yùn)行狀況進(jìn)行分析，對(duì)組網(wǎng)方式提出改進(jìn)意見(jiàn)。(6) Ad Hoc網(wǎng)絡(luò)中針對(duì)如何保證通信的質(zhì)量問(wèn)題，根據(jù)所給條件，建立相關(guān)模型，對(duì)上一題中的通信質(zhì)量進(jìn)行定量評(píng)價(jià)。2 模型假設(shè)(1) 節(jié)點(diǎn)可看作質(zhì)點(diǎn)，其所占的面積可忽略不計(jì)；(2) 節(jié)點(diǎn)與其自身通信所消耗的能量為0；3 符號(hào)說(shuō)明：鄰接矩陣；：抗毀性的量化值；：網(wǎng)絡(luò)損毀概率；、：分別表示為總能量、發(fā)射能量、接收能量、備用能量；、：分別表示為發(fā)送、接收、備用功率；、：分別表示為發(fā)送、接收、備用時(shí)間；：第個(gè)節(jié)點(diǎn)對(duì)所有的點(diǎn)發(fā)射信息的距離；、：第個(gè)節(jié)點(diǎn)的坐標(biāo)；：第個(gè)節(jié)點(diǎn)對(duì)所有的點(diǎn)發(fā)射信息所持續(xù)的時(shí)間；、：分別表示為一斷時(shí)間內(nèi)總的發(fā)射次數(shù)、總的時(shí)間；：發(fā)射時(shí)所消耗的能量；：在某一段時(shí)間內(nèi)因發(fā)射所消耗的能量；：節(jié)點(diǎn)與個(gè)節(jié)點(diǎn)的距離之和；F： 能量中心點(diǎn)；：置信區(qū)間；：表示每一次發(fā)射的起始時(shí)刻與下一次發(fā)射的起始時(shí)刻之間的時(shí)間間隔；：節(jié)點(diǎn)在時(shí)間 及位置 時(shí)的概率密度；D：速度的期望值；P：簇內(nèi)某點(diǎn)最后距起始點(diǎn)距離超過(guò)100的概率；4 模型建立與求解4.1 問(wèn)題1的解決4.1.1 相鄰圓的距離相鄰圓的半徑均為100，根據(jù)平面幾何的相關(guān)知識(shí)可以算出當(dāng)相鄰圓的公共面積不小于圓面積的5%時(shí)，兩圓間距為175.66；當(dāng)相鄰圓的公共面積不小于圓面積的18%時(shí)，兩圓間距為141.75。4.1.2 相鄰圓的連接關(guān)系及區(qū)域劃分顯然，當(dāng)圓以蜂窩狀分布時(shí)，有最小覆蓋，以下的圖1給出最簡(jiǎn)構(gòu)造。圖1以上給出的是臨界情況，則連接三個(gè)圓心的封閉折線為正三角形，根據(jù)本題給出的條件100，易得此正三角形的邊長(zhǎng)為。當(dāng)然，在實(shí)際情況中圓心間距是不固定的，因此分以下兩種情況進(jìn)行討論：(1) 圓心間距：此時(shí)，若以為邊長(zhǎng)構(gòu)成正三角形結(jié)構(gòu)，則在正三角形中心位置會(huì)出現(xiàn)小的空隙（見(jiàn)圖2中的陰影部分），這對(duì)于最小覆蓋來(lái)說(shuō)是極其不利的。圖2因此，必須將最上方的圓心位置下移，使得此圓的最低點(diǎn)恰好通過(guò)下方兩圓交點(diǎn)中y方向數(shù)值較大的點(diǎn)(如圖2中y點(diǎn)所示)，顯然連接此三個(gè)圓圓心構(gòu)成的封閉折線為頂角大于60的等腰三角形。就本題來(lái)說(shuō)，當(dāng)相鄰圓的公共面積不小于圓面積的5%時(shí)，兩圓間距s為175.66，滿(mǎn)足此條件。由于等腰三角形頂角大于60，則兩腰長(zhǎng)度小于底邊長(zhǎng)度，即上下兩層相鄰的圓的圓心間距小于175.66，顯然此時(shí)兩圓之間的公共部分更大，符合題目要求。按照此方案，則如圖3所示，MATLAB程序見(jiàn)附錄程序二（注：其中調(diào)用circle函數(shù)見(jiàn)附錄程序一）。圖3通過(guò)計(jì)算可知，長(zhǎng)度 為1000的邊至少需要6個(gè)圓才能完整覆蓋。最下面一層中相鄰圓交點(diǎn)中 軸方向數(shù)值較小的點(diǎn)與 軸相交，則最有利于最小覆蓋。由基礎(chǔ)的平面幾何知識(shí)可求出最下面一層圓的圓心 坐標(biāo)為47.81，再根據(jù)上述“等腰三角形”的理論可得各層間圓的圓心 坐標(biāo)間距Sy為152.126，這樣按層級(jí)6、7、6、7間雜排列，就可以得到結(jié)果。而 軸方向有空間富余，若發(fā)現(xiàn)在邊界區(qū)域有部分空隙未能覆蓋，則可通過(guò)在 軸方向的坐標(biāo)平移來(lái)修正。最后檢驗(yàn)四條邊界及四個(gè)頂點(diǎn)，均可落在所有圓覆蓋的區(qū)域里，則如圖3，當(dāng)相鄰圓的公共面積不小于圓面積的5%時(shí)可用45個(gè)半徑 為100的圓覆蓋此區(qū)域。 (2) 圓心間距 ：此時(shí)，若以s為邊長(zhǎng)構(gòu)成正三角形結(jié)構(gòu)，則在正三角形中心位置會(huì)出現(xiàn)重疊部分（見(jiàn)圖4陰影部分）。.圖4就直觀而言似乎可以將上層圓的位置上移，但結(jié)合本題來(lái)說(shuō)是不符合要求的。如：當(dāng)相鄰圓的公共面積不小于圓面積的18%時(shí)，兩圓間距為141.75，符合此情況。如果上移圓的位置，則連接此三圓圓心構(gòu)成的封閉折線為頂角小于60的等腰三角形，兩腰長(zhǎng)度就大于底邊長(zhǎng)度，即上下兩層相鄰的圓的圓心間距大于141.75，同時(shí)當(dāng)相鄰圓的公共面積就會(huì)小于圓面積的18%。因此，本情況只能以邊長(zhǎng)為圓心間距的正三角形為基礎(chǔ)架構(gòu)可得出區(qū)域劃分方案（如圖5）。MATLAB程序見(jiàn)附錄程序三（注：其中調(diào)用circle函數(shù)見(jiàn)附錄程序一）。圖5與上面類(lèi)似，通過(guò)計(jì)算可知，長(zhǎng)度 為1000的邊至少需要7個(gè)圓才能完整覆蓋，則以邊長(zhǎng) 為141.75的正三角形為基本構(gòu)架，即各層間圓心在y軸方向間距 為122.759，按層級(jí)7、8、7、8間雜排列，可得到結(jié)果。最后檢驗(yàn)四條邊界及四個(gè)頂點(diǎn)，最下層的7個(gè)圓為了使交點(diǎn)與 軸重合，所能覆蓋的 方向長(zhǎng)度不到994，而在此情況中最上層與最下層中相鄰圓交點(diǎn)在 軸方向上間距 為1000.3，幾乎沒(méi)有在 軸方向上做坐標(biāo)平移的可能，所以只好再補(bǔ)一個(gè)圓，即圖5中右下角的圓。則當(dāng)相鄰圓的公共面積不小于圓面積的18%時(shí)可以用61個(gè)半徑為100的圓覆蓋此區(qū)域。4.1.3 信道分配可將圖3中圓按序編號(hào)進(jìn)行改造，如表1：相鄰圓的距離示意圖s=175.6601 02 03 04 05 0607 08 09 10 11 12 1314 15 16 17 18 1920 21 22 23 24 25 2627 28 29 30 31 3233 34 35 36 37 38 3940 41 42 43 44 45表1以下根據(jù)表1，提出鄰接矩陣M4545的概念：當(dāng)i和j鄰接時(shí)：Mij=1；當(dāng)i和j不鄰接時(shí)：Mij=0。具體的矩陣形式參見(jiàn)附錄程序五中的MVNVN定義。此后的問(wèn)題就轉(zhuǎn)化為子集的劃分問(wèn)題，即已知集合A=a1,a2,an，A中關(guān)系R=(ai,aj)|ai,ajA,ij，(ai,aj)表示ai與aj間存在關(guān)系。要求將A劃分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均無(wú)關(guān)系，同時(shí)要求子集個(gè)數(shù)盡可能少。在此可通過(guò)編寫(xiě)子集劃分程序來(lái)實(shí)現(xiàn)，簡(jiǎn)要的算法描述如下： 集合A進(jìn)Q；result和work全部置0；當(dāng)前組號(hào)group=1； 依次出隊(duì)列得e，若worke=0（只考查關(guān)系未定的元素），則在work中，標(biāo)記e的沖突關(guān)系。即： 若Mei=1 & worki=0，則worki=1； （避免改寫(xiě)worki為-1的單元） 若worki=0，則resulti=group; worki=-1; 若worki=1，則worki=0; 將所有worki=0的元素，再進(jìn)隊(duì)列； group+； 轉(zhuǎn)，直至Q為空。具體的程序見(jiàn)附錄程序五(注：程序所需Division.h文件見(jiàn)附錄程序四)。由此可得出滿(mǎn)足相鄰圓的公共面積不小于圓面積的5%條件信道劃分結(jié)果，見(jiàn)表2：信道1信道2信道3信道41,3,5,13,14,16,18,26,27,29,31,39,40,42,442,4,6,7,15,17,19,20,28,30,32,33,41,43,458,10,12,21,23,25,34,36,389,11,22,24,35,37表2由此可知道要使公共部分的圓擁有不同的信道，最少需要4個(gè)信道，示意圖見(jiàn)圖6。同理，將圖5中圓按序編號(hào)進(jìn)行改造，也可以得到滿(mǎn)足相鄰圓的公共面積不小于圓面積的18%條件的信道劃分結(jié)果也為4個(gè)，其示意圖見(jiàn)圖7。圖6圖74.1.4 抗毀性討論在通信中，抗毀性的定義是在網(wǎng)絡(luò)有故障時(shí)的通信能力，在本題中可以理解為位于圓心的節(jié)點(diǎn)在有與外界進(jìn)行通信的需求時(shí)，即使在此圓所覆蓋的區(qū)域內(nèi)有部分節(jié)點(diǎn)不能正常工作，依然有與外界進(jìn)行通信的能力；而處于兩圓公共部分的節(jié)點(diǎn)在這兩個(gè)圓的圓心節(jié)點(diǎn)被抽取時(shí)就不具備通信能力了。根據(jù)以上的理解可以認(rèn)為，當(dāng)相臨圓心的節(jié)點(diǎn)被抽掉以及一個(gè)圓周?chē)乃信c其它圓聯(lián)通的節(jié)點(diǎn)都被抽掉的時(shí)候，就會(huì)影響整個(gè)網(wǎng)絡(luò)的連通性。針對(duì)以上的分析，分以下兩種情況進(jìn)行討論：(1) 當(dāng)抽取圓公共部分節(jié)點(diǎn)時(shí)情況比較復(fù)雜，于是考慮將問(wèn)題簡(jiǎn)化為抽出特定的一組不在圓心的節(jié)點(diǎn)后，網(wǎng)絡(luò)可能被毀。表3表示這種特定點(diǎn)的分組情況抽取特定點(diǎn)數(shù)5的情況18的情況2033106481354662333表3由古典概型的定義可以得出抗毀性的量化標(biāo)準(zhǔn)，但由于計(jì)算繁瑣，可近一步簡(jiǎn)化。將以上兩組數(shù)據(jù)加權(quán)平均后可得其值都近似等于5，故可以認(rèn)為特定的5個(gè)不位于圓心的節(jié)點(diǎn)為抗毀性的基本單位，只要此特定的5點(diǎn)不同時(shí)被抽取則可認(rèn)為網(wǎng)絡(luò)正常。(2) 當(dāng)抽取圓中心節(jié)點(diǎn)時(shí)，若節(jié)點(diǎn)數(shù)小于2則不影響網(wǎng)絡(luò)連通；若節(jié)點(diǎn)數(shù)等于2時(shí)，則根據(jù)上面的結(jié)構(gòu)可得出公共面積為5%時(shí)網(wǎng)絡(luò)損毀概率為，公共面積為18%時(shí)網(wǎng)絡(luò)損毀概率為；而若節(jié)點(diǎn)數(shù)大于2時(shí)，因?yàn)楦鶕?jù)題意，在三圓公共部分沒(méi)有節(jié)點(diǎn)，故可近似看作先取兩相鄰圓在任意取其它圓，則損毀概率與等于2時(shí)相同。綜合兩種情況，再利用古典概型的定義，可近似得出抗毀性的量化值k，羅列如下：公共面積5%的情況抽掉2%（3點(diǎn)）： 抽掉5%（8點(diǎn)）： 抽掉10%（15點(diǎn)）： 抽掉15%（23點(diǎn)）： 公共面積18%的情況抽掉2%（4點(diǎn)）： 抽掉5%（11點(diǎn)）： 抽掉10%（21點(diǎn)）： 抽掉15%（32點(diǎn)）： 4.1.5 問(wèn)題1總結(jié)經(jīng)過(guò)上述四個(gè)步驟的計(jì)算、編程、求解，我們可以得出，將此正方形區(qū)域用若干個(gè)半徑都是100的圓完全覆蓋，在相鄰兩個(gè)圓的公共面積不小于一個(gè)圓面積的5%的情況下，最少需要45個(gè)圓；相鄰兩個(gè)圓的公共面積不小于一個(gè)圓面積的18%的情況下，則最少需要61個(gè)圓。分別考慮在公共面積不小于一個(gè)圓面積的5%和18%兩種情況下，若給每個(gè)圓分配一個(gè)信道使得有公共部分的圓擁有不同的信道，最少需要的信道數(shù)都為4個(gè)。若每個(gè)公共部分中心和相應(yīng)圓心各恰有一個(gè)節(jié)點(diǎn)，在節(jié)點(diǎn)集合中，隨機(jī)地抽掉2%、5%、10%、15%等數(shù)量的節(jié)點(diǎn)，在公共面積不小于5%和18%的兩種情況下，網(wǎng)絡(luò)的抗毀性可以定量分析得出。對(duì)于問(wèn)題1各問(wèn)的結(jié)果，我們匯總?cè)绫?。公共面積5情況公共面積18情況覆蓋圓的個(gè)數(shù)4561所需信道個(gè)數(shù)44抗毀性抽掉288.8991.69%抽掉588.87%91.6%抽掉1088.8%91.51%抽掉1587.02%88.57%表44.2 問(wèn)題2的解決4.2.1 替代圓規(guī)則為了更好的表述改進(jìn)后的情況，首先作出相應(yīng)的圖形（見(jiàn)圖8）。圖8又由于最關(guān)心的數(shù)據(jù)為所有圓的半徑和，表5給出部分半徑分別為100和75的圓的各自的半徑和。圓的個(gè)數(shù)半徑75圓的半徑和半徑100圓的半徑和1751002150200322530043004005375500表5由上表可以直觀的看出我們可以接受的替換：1個(gè)小圓替換1個(gè)大圓，2個(gè)小圓替換2個(gè)大圓，4個(gè)小圓替換3個(gè)大圓，6個(gè)小圓替換5個(gè)大圓而4個(gè)小圓可覆蓋面積為22500，3個(gè)大圓可覆蓋面積為30000；6個(gè)小圓可覆蓋面積為33750，5個(gè)大圓可覆蓋面積為50000。顯然，由于面積與半徑為平方關(guān)系，需要覆蓋多個(gè)大圓面積就需要更多的小圓，因此除去大圓覆蓋大面積無(wú)效的情況，最實(shí)惠的做法是用1個(gè)小圓去替換1個(gè)大圓。顯然，在圖8中間位置與湖面相交的圓可以用半徑為75的小圓代替，左右兩邊界各有3個(gè)大圓可用小一些的圓替代。根據(jù)相鄰圓之間的公共面積不小于大圓面積的5%，及以我們的方案進(jìn)行區(qū)域劃分時(shí)相鄰兩層圓的圓心距不得小于152.126的條件，可以得出這6個(gè)圓最小半徑約為80。改動(dòng)后的區(qū)域劃分如圖9所示，其半徑和為4355。圖94.2.2 信道分配這里的原理與1.3相同，因此直接給出結(jié)果示意圖，見(jiàn)圖10。圖104.3 問(wèn)題3的解決4.3.1 區(qū)域的劃分首先根據(jù)所給的數(shù)據(jù)畫(huà)出這些點(diǎn)在正方形區(qū)域內(nèi)的分布散點(diǎn)圖，如圖11所示。圖11顯而易見(jiàn)，這些大量的點(diǎn)的分布是雜亂無(wú)章的，可由如下思想對(duì)此進(jìn)行分簇：(1) 通過(guò)定義一組起始簇中心進(jìn)行分簇，初始簇中心可隨機(jī)產(chǎn)生。(2) 根據(jù)輸入數(shù)據(jù)把每個(gè)數(shù)據(jù)分到與其最相似的簇。(3) 在分完所有的數(shù)據(jù)后，更新簇中心以反映分到每一個(gè)簇的新的數(shù)據(jù)情況。(4) 再次檢查記錄，以確定是否將其重新分到別的簇。(5) 進(jìn)行遞歸，直到達(dá)到最大遞歸次數(shù)或者前后兩次遞歸之間的差異不超過(guò)指定閥值。可以方便地利用統(tǒng)計(jì)軟件SPSS對(duì)這些數(shù)據(jù)進(jìn)行分簇，只需滿(mǎn)足條件：每個(gè)簇中的所有節(jié)點(diǎn)到簇中心的最大距離小于等于100即可。其結(jié)果見(jiàn)附錄表一，示意圖見(jiàn)圖12。圖12此圖所示各圓所包含的節(jié)點(diǎn)使用相同的信道，由于Ad Hoc網(wǎng)絡(luò)一跳覆蓋區(qū)的圓心、半徑在不斷變化，以上僅是區(qū)域劃分示意圖。當(dāng)區(qū)域中有湖時(shí)，編寫(xiě)程序先剔除位于湖中的節(jié)點(diǎn)，具體程序見(jiàn)附錄程序六。再利用SPSS進(jìn)行分簇，具體圖示見(jiàn)圖13。圖13圖14圖15但僅僅以上的結(jié)論并不一定能夠滿(mǎn)足有轉(zhuǎn)發(fā)任務(wù)的公共面積不小于較大一跳覆蓋區(qū)面積的5%，因此需要對(duì)得到的數(shù)據(jù)進(jìn)行修正。為此我們?cè)O(shè)計(jì)了“自適應(yīng)修正算法”，此算法由兩個(gè)子程序組成，分別附于附錄程序七和程序八。通過(guò)程序七可初步檢驗(yàn)出所有不滿(mǎn)足公共面積5%條件的圓心對(duì)，但根據(jù)題意，沒(méi)有轉(zhuǎn)發(fā)任務(wù)的公共區(qū)域并沒(méi)有5%的要求，顯然當(dāng)公共區(qū)域中沒(méi)有節(jié)點(diǎn)時(shí)就可以認(rèn)為沒(méi)有轉(zhuǎn)發(fā)任務(wù)。將程序七得出的數(shù)據(jù)再傳入程序八，可進(jìn)一步判斷出有轉(zhuǎn)發(fā)任務(wù)且不滿(mǎn)足5%條件的公共區(qū)域。將與這些公共區(qū)域相關(guān)的圓的半徑稍作放大（始終讓其不大于100）后得到新的數(shù)據(jù)重新傳入程序七進(jìn)行迭代，并在此過(guò)程中記錄下不滿(mǎn)足條件的節(jié)點(diǎn)數(shù)最少時(shí)的狀態(tài)。經(jīng)過(guò)一定次數(shù)的迭代后，若仍然存在不滿(mǎn)足條件的節(jié)點(diǎn)，則調(diào)出先前的最佳記錄，通過(guò)微調(diào)圓心位置使所有節(jié)點(diǎn)滿(mǎn)足要求。修正后的示意圖分別見(jiàn)圖14和圖15。此時(shí)，得到的在無(wú)湖和有湖狀態(tài)下全部一跳覆蓋區(qū)的半徑和分別為4670.42672與4361.02504。4.3.2 信道分配方案信道劃分的方法如前所述，這里不再贅述，僅給出示意圖：圖16、圖17。圖16圖174.3.3 區(qū)域連通的充分、必要條件由于這里的組網(wǎng)方式是基于簇的，所以在同一簇里的節(jié)點(diǎn)既可以作為一跳覆蓋區(qū)的中心節(jié)點(diǎn)，也可以作為公共部分的節(jié)點(diǎn)。當(dāng)一個(gè)簇里有節(jié)點(diǎn)處在工作狀態(tài)下，則所處區(qū)域也出于連通狀態(tài)，這就是區(qū)域連通的充分條件；反之，當(dāng)區(qū)域連通時(shí)，所在簇中至少有一個(gè)節(jié)點(diǎn)出于工作狀態(tài)，這即為必要條件。4.3.4 網(wǎng)絡(luò)的抗毀性對(duì)于網(wǎng)絡(luò)的抗毀性，可借鑒問(wèn)題1的思路，并根據(jù)以上充分、必要條件加以討論。無(wú)湖時(shí)的分簇情況有湖時(shí)的分簇情況組號(hào) 包含點(diǎn)個(gè)數(shù)組號(hào) 包含點(diǎn)個(gè)數(shù)114.000217.000315.000420.000514.000620.000717.000817.000920.0001016.0001118.0001225.0001315.0001419.0001513.0001618.0001714.0001815.0001915.0002020.0002118.0002216.0002313.0002418.0002517.0002620.0002719.0002816.0002920.0003019.0003117.0003214.0003318.0003419.0003515.0003616.0003720.0003817.0003919.0004017.0004111.0004217.0004314.0004411.0004518.0004619.0004722.0004813.0004920.0005019.0005121.0005218.0005311.0005422.000116.000215.000315.000422.000517.000618.000717.000817.000917.0001020.0001111.0001220.0001319.0001420.0001513.0001616.0001720.0001821.0001914.0002023.0002116.0002223.0002316.0002417.0002517.0002620.0002714.0002817.0002915.0003021.0003119.0003214.0003317.0003417.0003516.0003615.0003714.0003818.0003917.0004018.0004121.0004218.0004311.0004418.0004519.0004613.0004723.0004818.0004919.0005014.000根據(jù)以上表格可認(rèn)為在無(wú)湖與有湖狀態(tài)下的最小抗毀單位均為17。由于節(jié)點(diǎn)的大量增多，及運(yùn)算越來(lái)越復(fù)雜，甚至導(dǎo)致計(jì)算機(jī)出現(xiàn)數(shù)據(jù)溢出的現(xiàn)象，在此給出定性分析。兩種情況在抽取2節(jié)點(diǎn)時(shí)網(wǎng)絡(luò)毀滅概率的計(jì)算公式分別為和，幾乎近似等于零，遠(yuǎn)比第一種劃分方式要好。而當(dāng)抽取比例越來(lái)越大時(shí)，抗毀性不斷衰減，且開(kāi)始時(shí)衰減速度較慢，當(dāng)?shù)竭_(dá)某一臨界值時(shí)衰減速率急劇增加。4.4 問(wèn)題4的解決4.4.1 模型建立在上一問(wèn)的基礎(chǔ)上這里引入了十個(gè)以方向角服從0,2均勻分布，速度服從0,2均勻分布的隨機(jī)變量，其運(yùn)動(dòng)方式與物理學(xué)中的布朗運(yùn)動(dòng)性質(zhì)相似。因此借助布朗運(yùn)動(dòng)的結(jié)論，若 以節(jié)點(diǎn)在t=0時(shí)的位置為原點(diǎn)，則節(jié)點(diǎn)在時(shí)間 t 及位置 x 時(shí)的概率密度可表達(dá)為：其中D表示一正常數(shù)，在本題中D即為速度的期望值，即D1。由于原本此點(diǎn)在某一簇內(nèi)，故其最后距起始點(diǎn)不超過(guò)100則其聯(lián)通性不受影響。而當(dāng)t=400時(shí)，距離超過(guò)100的概率為：4.4.2 模型驗(yàn)證根據(jù)以上結(jié)論可認(rèn)為若節(jié)點(diǎn)作布朗運(yùn)動(dòng)則幾乎不影響網(wǎng)絡(luò)聯(lián)通性。當(dāng)然本題中節(jié)點(diǎn)運(yùn)動(dòng)所不同的是運(yùn)動(dòng)狀態(tài)不是時(shí)時(shí)改變，而是間隔30個(gè)單位，為了更好地驗(yàn)證這一隨機(jī)過(guò)程，可通過(guò)編寫(xiě)程序來(lái)模擬此過(guò)程，具體程序見(jiàn)附錄程序九。再將最終的狀態(tài)作出直觀圖，見(jiàn)圖18。圖18經(jīng)過(guò)程序仿真后所得的結(jié)果也可以直觀地看出此例中的Ad Hoc網(wǎng)絡(luò)在400單位時(shí)間后是連通的，4.5 問(wèn)題5的解決4.5.1 理論模型由于節(jié)點(diǎn)退出是因?yàn)槟芰亢谋M，可見(jiàn)本問(wèn)題的關(guān)鍵是找出節(jié)點(diǎn)能量消耗與起所處位置的關(guān)系。為了說(shuō)明方便，引入如下符號(hào)：由于能量E由發(fā)射能量、接收能量和備用能量三部分組成，若發(fā)射、接收、備用三種狀態(tài)所對(duì)應(yīng)的功率和時(shí)間分別為、和、，則：由于: : =11 : 10 : 1，上式可轉(zhuǎn)換為：其中為常量，顯然，要使工作時(shí)間盡可能的大，則的值要盡可能的大；反之，要使工作時(shí)間t盡可能的小，則的值要盡可能的小。由于兩節(jié)點(diǎn)之間原始（不是轉(zhuǎn)發(fā)）的平均通信次數(shù)大致與它們之間的距離的平方成反比，可將發(fā)射狀態(tài)和接收狀態(tài)歸結(jié)為通信狀態(tài)，則可認(rèn)為節(jié)點(diǎn)處于通信狀態(tài)時(shí)其發(fā)射和接收狀態(tài)為等概率事件。根據(jù)題目要求，問(wèn)題轉(zhuǎn)化為找出所有節(jié)點(diǎn)中處于備用狀態(tài)時(shí)間最短或處于通信狀態(tài)時(shí)間最長(zhǎng)的節(jié)點(diǎn)。根據(jù)題意，分下列兩類(lèi)情況討論：(1) 任取一節(jié)點(diǎn)，討論其發(fā)射一次所消耗的能量：在給出的所有數(shù)據(jù)點(diǎn)中任取一點(diǎn)，其坐標(biāo)為(,)，若此點(diǎn)對(duì)所有的點(diǎn)發(fā)射信息，則將其距離記為，持續(xù)時(shí)間記為。根據(jù)發(fā)射功率近似地與最大傳輸距離的三次方成正比以及兩節(jié)點(diǎn)之間原始（不是轉(zhuǎn)發(fā)）的平均通信次數(shù)大致與它們之間的距離的平方成反比的條件，可以得到如下等式：上式中、為常量，根據(jù)題意服從期望為4的指數(shù)分布，而所有點(diǎn)的坐標(biāo)已知，則，已知。由于樣本容量為926，足夠大，則根據(jù)獨(dú)立同分布的中心極限定理可以得到當(dāng)=0.05時(shí)，其置信區(qū)間上下限值約為0.25。由此可見(jiàn)，對(duì)的影響可近似看作與呈一次線形關(guān)系。(2) 任取一節(jié)點(diǎn)，討論其在某一段時(shí)間內(nèi)對(duì)所有點(diǎn)的發(fā)射次數(shù)：在給出的所有數(shù)據(jù)點(diǎn)中任取一點(diǎn)，其坐標(biāo)為(,)，若此點(diǎn)對(duì)所有的點(diǎn)發(fā)射信息，則將其距離記為。根據(jù)兩節(jié)點(diǎn)之間原始（不是轉(zhuǎn)發(fā)）的平均通信次數(shù)大致與它們之間的距離的平方成反比的條件，可以得到如下等式：為避免討論于分母的情況并簡(jiǎn)化計(jì)算，提出每一次發(fā)射的單位時(shí)間的概念，即每一次發(fā)射的起始時(shí)刻與下一次發(fā)射的起始時(shí)刻之間的時(shí)間間隔t。則可以得到下式：顯然，這里N的變化可看作受的影響，且越小，越大。綜合上面的兩種情況，在某一段時(shí)間內(nèi)因發(fā)射所消耗的能量即為，其改變趨勢(shì)主要受影響，即方向與相反，趨勢(shì)與相同。所以要得出處于發(fā)射狀態(tài)時(shí)間最長(zhǎng)的節(jié)點(diǎn)只要找出使有最大值的節(jié)點(diǎn)位置即可。而接收狀態(tài)與發(fā)射狀態(tài)一致，故整個(gè)問(wèn)題可轉(zhuǎn)換為找出使有最大值的節(jié)點(diǎn)位置。以下給出推導(dǎo)過(guò)程：由于與為常量，使與取得最大值的點(diǎn)坐標(biāo)為(,)，可以定義此點(diǎn)為能量中心點(diǎn)F。節(jié)點(diǎn)離F點(diǎn)越近，則用于通信的能量占總能量的比例越大，耗盡能量而退出網(wǎng)絡(luò)的時(shí)間越早；節(jié)點(diǎn)離F點(diǎn)越遠(yuǎn)，則用于通信的能量占總能量的比例越小，耗盡能量而退出網(wǎng)絡(luò)的時(shí)間越遲。因此，以F點(diǎn)為圓心作圓，其半徑越大，此區(qū)域內(nèi)節(jié)點(diǎn)能量耗盡而退出網(wǎng)絡(luò)的時(shí)間就越晚，即出現(xiàn)第一個(gè)退出網(wǎng)絡(luò)的節(jié)點(diǎn)的時(shí)間盡量長(zhǎng)。4.5.1 具體實(shí)現(xiàn)根據(jù)本題所提供的數(shù)據(jù)可以得到，F(xiàn)點(diǎn)坐標(biāo)為(493.913,499.031)，以F點(diǎn)為圓心，100為半徑，此區(qū)域內(nèi)的節(jié)點(diǎn)即為一簇，剩余的節(jié)點(diǎn)可按照第3問(wèn)中有湖的情況進(jìn)行劃分即可。具體的區(qū)域劃分的方案如圖19所示。圖19然后再調(diào)用程序七、程序八對(duì)一跳覆蓋區(qū)的覆蓋范圍進(jìn)行修正，使其滿(mǎn)足有轉(zhuǎn)發(fā)任務(wù)的相鄰一跳覆蓋區(qū)的公共面積不小于較大一跳覆蓋區(qū)面積5%的條件，并得出在此情況下全部一跳覆蓋區(qū)的半徑和為4549.70887。具體分布見(jiàn)圖20。圖20根據(jù)第3問(wèn)中區(qū)域連通的充分條件，以及本問(wèn)題中提出的能量中心理論，則在一段時(shí)間后，此正方形區(qū)域中央的一跳覆蓋區(qū)首先毀滅，隨之其周?chē)囊惶采w區(qū)相繼毀滅，直至最后。所以如果要對(duì)組網(wǎng)方式進(jìn)行改進(jìn)，可以考慮在能量中心附近多分布一些一跳覆蓋區(qū)以分擔(dān)其通信任務(wù)。4.6 問(wèn)題6的解決4.6.1 問(wèn)題分析本問(wèn)題要討論的是一個(gè)動(dòng)態(tài)過(guò)程，比前面的問(wèn)題要復(fù)雜的多。再加上Ad Hoc特殊的網(wǎng)絡(luò)拓補(bǔ)結(jié)構(gòu)，以及題目所提供的大量節(jié)點(diǎn)使得問(wèn)題更為復(fù)雜。解決復(fù)雜的問(wèn)題自然需要簡(jiǎn)化，一種方法是對(duì)Ad Hoc網(wǎng)絡(luò)復(fù)雜的路由進(jìn)行等效的分割，通過(guò)對(duì)部分節(jié)點(diǎn)的研究來(lái)推導(dǎo)出全局節(jié)點(diǎn)的總體特征；另一種方法是在眾多影響結(jié)果的條件中先著重考慮影響最顯著的條件，然后再逐步加入其它條件，使之接近于題設(shè)情況。如本題所要討論的通信質(zhì)量，可依照以上兩條途徑尋找解決方案。一條途徑是先找出節(jié)點(diǎn)與節(jié)點(diǎn)之間通信質(zhì)量的關(guān)系，再找到簇與簇之間通信質(zhì)量的關(guān)系，最后歸結(jié)到整個(gè)局域網(wǎng)的通信質(zhì)量。另一條途徑是首先考慮丟包（即重發(fā)或延時(shí)）的因素，再考慮因節(jié)點(diǎn)能量耗盡而退出的因素，最后歸納出所有的因素。當(dāng)然，將兩條途徑綜合考慮也許更正確，但是由于時(shí)間的限制，無(wú)法更深一步進(jìn)行探討，謹(jǐn)在此提出一些初步的想法。參考文獻(xiàn)1 蔣杰，方力，張鶴穎，竇文華 無(wú)線傳感器網(wǎng)絡(luò)最小連通覆蓋集問(wèn)題求解算法 Journal of Software Vol.17,No.2,February 2006,pp.175-184.2 潘麗君 戰(zhàn)場(chǎng)通信網(wǎng)戰(zhàn)時(shí)抗毀性初探 裝甲兵工程學(xué)院學(xué)報(bào) 2006，4，Vol.20 ,No.2,pp:21-25.3 陳建國(guó) 基于管理技術(shù)的ATM網(wǎng)絡(luò)抗毀性研究 信息系統(tǒng)網(wǎng)絡(luò) 2006，Vol.36,No.4,pp:8-11. 4 張宜華 精通SPSS 清華大學(xué)出版社，2002.5 郝黎仁，樊元 SPSS使用統(tǒng)計(jì)分析 中國(guó)水利水電出版社， 2003.6 張森 張正亮 MATLAB仿真技術(shù)與實(shí)例應(yīng)用教程 機(jī)械工業(yè)出版社， 2004.7 王紀(jì)林，賀才興等 概率論與數(shù)理統(tǒng)計(jì) 科學(xué)出版社， 2000.8 陳華生，張?jiān)佬?Visual C+程序設(shè)計(jì)基礎(chǔ) 蘇州大學(xué)出版社， 2000.9 壽紀(jì)麟 數(shù)學(xué)建模方法與范例 西安交通大學(xué)出版社， 1995.附錄程序一function h=circle(r,x0,y0,C,Nb) % r 圓的半徑。 % x0,y0 圓心座標(biāo)。% C圓的顏色，不說(shuō)明時(shí)，由指令依序指定。% Nb繪圓時(shí)所用點(diǎn)數(shù)，若不指定，則以300點(diǎn)為預(yù)設(shè)值。% the axes ColorOrder property. For several circles C may be a vector. switch nargin case 0 r=;x0=;y0=;C=;Nb=; case 1 x0=;y0=;C=;Nb=; case 2 y0=zeros(1,length(x0);C=;Nb=; case 3 C=;Nb=; case 4 Nb=; end if length(x0)=length(y0), if length(y0)=1, y0=ones(1,length(x0)*y0; elseif length(x0)=1, x0=ones(1,length(y0)*x0; else error(The lengths of x0 and y0 must be identical); end; end; if isempty(r),r=1;end; if isempty(x0),x0=0;end; if isempty(y0),y0=0;end; if isempty(Nb),Nb=300;end; if isempty(C),C=get(gca,colororder);end; if isstr(C),C=C(:);end; x0=x0(:); y0=y0(:); r=r(:); Nb=Nb(:); if length(r)=length(x0) maxk=length(r)*length(x0); else maxk=length(r); end; route=0; if length(x0)=1, route=1; end if length(r)=1, route=2; end if length(x0)=length(r), route=3; end for k=1:maxk switch route case 1 xpos=x0; ypos=y0; rad=r(k); case 2 xpos=x0(k); ypos=y0(k); rad=r; case 3 xpos=x0(k); ypos=y0(k); rad=r(k); otherwise rad=r(fix(k-1)/size(x0,1)+1); xpos=x0(rem(k-1,size(x0,1)+1); ypos=y0(rem(k-1,size(y0,1)+1); end; theta=linspace(0,2*pi,Nb(rem(k-1,size(Nb,1)+1,:)+1); h(k)=line(rad*cos(theta)+xpos,rad*sin(theta)+ypos); set(h(k),color,C(rem(k-1,size(C,1)+1,:); end;程序二x=67.83 243.49 419.15 594.81 770.47 946.13 -20 155.66 331.32 506.98 682.64 858.3 1033.96 67.83 243.49 419.15 594.81 770.47 946.13 -20 155.66 331.32 506.98 682.64 858.3 1033.96 67.83 243.49 419.15 594.81 770.47 946.13 -20 155.66 331.32 506.98 682.64 858.3 1033.96 67.83 243.49 419.15 594.81 770.47 946.13y=47.8100 47.8100 47.8100 47.8100 47.8100 47.8100 199.9360 199.9360 199.9360 199.9360 199.9360 199.9360 199.9360 352.0620 352.0620 352.0620 352.0620 352.0620 352.0620 504.1880 504.1880 504.1880 504.1880 504.1880 504.1880 504.1880 656.3140 656.3140 656.3140 656.3140 656.3140 656.3140 808.4400 808.4400 808.4400 808.4400 808.4400 808.4400 808.4400 960.5660 960.5660 960.5660 960.5660 960.5660 960.5660 circle(100,x,y)hold on;plot(0:0.1:1000,0)plot(0,0:0.1:1000)plot(0:0.1:1000,1000)plot(1000,0:0.1:1000)程序三x=70.8750 212.6250 354.3750 496.1250 637.8750 779.6250 921.3750 1063.0000 0 141.7500 283.5000 425.2500 567.0000 708.7500 850.5000 992.2500 70.8750 212.6250 354.3750 496.1250 637.8750 779.6250 921.3750 0 141.7500 283.5000 425.2500 567.0000 708.7500 850.5000 992.2500 70.8750 212.6250 354.3750 496.1250 637.8750 779.6250 921.3750 0 141.7500 283.5000 425.2500 567.0000 708.7500 850.5000 992.2500 70.8750 212.6250 354.3750 496.1250 637.8750 779.6250 921.3750 0 141.7500 283.5000 425.2500 567.0000 708.7500 850.5000 992.2500y=70.5400 70.5400 70.5400 70.5400 70.5400 70.5400 70.5400 70.5400 193.2990 193.2990 193.2990 193.2990 193.2990 193.2990 193.2990 193.2990 316.0580 316.0580 316.0580 316.0580 316.0580 316.0580 316.0580 438.8170 438.8170 438.8170 438.8170 438.8170 438.8170 438.8170 438.8170 561.5760 561.5760 561.5760 561.5760 561.5760 561.5760 561.5760 684.3350 684.3350 684.3350 684.3350 684.3350 684.3350 684.3350 684.3350 807.0940 807.0940 807.0940 807.0940 807.0940 807.0940 807.0940 929.8530 929.8530 929.8530 929.8530 929.8530 929.8530 929.8530 929.8530circle(100,x,y)hold on;plot(0:0.1:1000,0)plot(0,0:0.1:1000)plot(0:0.1:1000,1000)plot(1000,0:0.1:1000)程序四#define VN 45 / 13 /6 / 結(jié)點(diǎn)數(shù)#define QSIZE VN+1 / 隊(duì)列大?。鹤疃啻娣臯N個(gè)頂點(diǎn)的下標(biāo)struct Queue int baseQSIZE; int front,rear;void QueueInit(Queue &Q) Q.front =Q.rear =0; bool QueueEmpty(Queue &Q) if(Q.front=Q.rear) return(true); else return(false);void QueueEnter(Queue &Q, int e) Q.baseQ.rear=e; Q.rear=(Q.rear +1) % QSIZE; int QueueLeave(Queue &Q) int e=Q.baseQ.front; Q.front=(Q.front+1) % QSIZE; return(e);void Division(int MVN, int result) for(int i=0; iVN; i+) resulti=0; int group=1; int e; int workVN; for(i=0; iVN; i+) worki=0; Queue Q; QueueInit(Q); for(i=0; iVN; i+) QueueEnter(Q, i); while(QueueEmpty(Q)=false) while(QueueEmpty(Q)=false) e=QueueLeave(Q); if(worke=0) for(i=0; iVN; i+) if(Mei=1 & worki=0) worki=1; for(i=0; iVN; i+) if(worki=0) resulti=group; worki=-1; if(worki=1) worki=0; for(i=0; iVN; i+) if(resulti=0) QueueEnter(Q, i); group+; 程序五#include iostream.h#include Division.hvoid main() int MVNVN= 0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,