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

Ad Hoc網(wǎng)絡(luò)中的區(qū)域劃分和資源分配問題1 問題重述隨著人們對擺脫有線網(wǎng)絡(luò)束縛、隨時隨地進(jìn)行自由通信的渴望，近幾年來無線網(wǎng)絡(luò)通信得到了迅速的發(fā)展。為了能夠在沒有固定基站的地方進(jìn)行通信， Ad Hoc網(wǎng)絡(luò)技術(shù)應(yīng)運而生。Ad Hoc網(wǎng)絡(luò)不需要有線基礎(chǔ)設(shè)備的支持，通過移動主機(jī)自由的組網(wǎng)實現(xiàn)通信。就其特點，在給定一些限制條件下，本文提出了關(guān)于如何合理劃分 Ad Hoc網(wǎng)絡(luò)中的區(qū)域和分配資源問題。具體內(nèi)容如下：對一個指定10001000(面積單位)的正方形區(qū)域內(nèi)構(gòu)建一個Ad Hoc網(wǎng)絡(luò)，需解決以下問題：(1) 以圓的形式對正方形區(qū)域進(jìn)行覆蓋，在滿足所給定的限制條件下，通過建立最小半徑和模型，求得圓的最少個數(shù)。若給每個圓分配一個信道，使得有公共部分的圓擁有不同的信道，在此條件下合理分配信道。改變公共面積部分的限制條件，重復(fù)上述問題。再根據(jù)條件，提出合理假設(shè)，討論網(wǎng)絡(luò)的抗毀性問題。(2) 設(shè)正方形區(qū)域中有一滿足給定條件的橢圓形湖泊。由限制條件：節(jié)點僅能設(shè)置在地面上，以及假設(shè)條件：一跳覆蓋區(qū)圓的半徑可以在75100間隨意選擇，兩個面積不等的圓相交，它們之間的公共面積應(yīng)不小于大圓面積的5%，建立最小半徑和模型，研究合理的區(qū)域分劃和信道分配方案。(3) 在假設(shè)一個較短的時間間隔內(nèi)，網(wǎng)絡(luò)的連通性可能并未變化的情況下，采用基于節(jié)點的劃分方式，在某一時刻將正方形區(qū)域內(nèi)的節(jié)點（用戶）分成若干個簇。給出簇與一跳覆蓋區(qū)的定義，并根據(jù)給定條件結(jié)合數(shù)據(jù)，建立半徑最小和模型，研究一跳覆蓋區(qū)劃分和信道分配方案，找出區(qū)域連通的充分、必要條件，并討論網(wǎng)絡(luò)抗毀性。(4) 在問題3的基礎(chǔ)上作進(jìn)一步假設(shè)，根據(jù)所給的條件，考慮在動態(tài)情況下，通過建立模型，考慮網(wǎng)絡(luò)連通性問題。(5) 基于前面（3）中所給辦法，從節(jié)能角度出發(fā)，根據(jù)所給條件，建立能量消耗與其所處位置關(guān)聯(lián)的求極值模型，找到比較節(jié)能的區(qū)域分劃方式，使出現(xiàn)第一個退出網(wǎng)絡(luò)的節(jié)點的時間盡量長。并通過對該網(wǎng)絡(luò)的運行狀況進(jìn)行分析，對組網(wǎng)方式提出改進(jìn)意見。(6) Ad Hoc網(wǎng)絡(luò)中針對如何保證通信的質(zhì)量問題，根據(jù)所給條件，建立相關(guān)模型，對上一題中的通信質(zhì)量進(jìn)行定量評價。2 模型假設(shè)(1) 節(jié)點可看作質(zhì)點，其所占的面積可忽略不計；(2) 節(jié)點與其自身通信所消耗的能量為0；3 符號說明：鄰接矩陣；：抗毀性的量化值；：網(wǎng)絡(luò)損毀概率；、：分別表示為總能量、發(fā)射能量、接收能量、備用能量；、：分別表示為發(fā)送、接收、備用功率；、：分別表示為發(fā)送、接收、備用時間；：第個節(jié)點對所有的點發(fā)射信息的距離；、：第個節(jié)點的坐標(biāo)；：第個節(jié)點對所有的點發(fā)射信息所持續(xù)的時間；、：分別表示為一斷時間內(nèi)總的發(fā)射次數(shù)、總的時間；：發(fā)射時所消耗的能量；：在某一段時間內(nèi)因發(fā)射所消耗的能量；：節(jié)點與個節(jié)點的距離之和；F： 能量中心點；：置信區(qū)間；：表示每一次發(fā)射的起始時刻與下一次發(fā)射的起始時刻之間的時間間隔；：節(jié)點在時間 及位置 時的概率密度；D：速度的期望值；P：簇內(nèi)某點最后距起始點距離超過100的概率；4 模型建立與求解4.1 問題1的解決4.1.1 相鄰圓的距離相鄰圓的半徑均為100，根據(jù)平面幾何的相關(guān)知識可以算出當(dāng)相鄰圓的公共面積不小于圓面積的5%時，兩圓間距為175.66；當(dāng)相鄰圓的公共面積不小于圓面積的18%時，兩圓間距為141.75。4.1.2 相鄰圓的連接關(guān)系及區(qū)域劃分顯然，當(dāng)圓以蜂窩狀分布時，有最小覆蓋，以下的圖1給出最簡構(gòu)造。圖1以上給出的是臨界情況，則連接三個圓心的封閉折線為正三角形，根據(jù)本題給出的條件100，易得此正三角形的邊長為。當(dāng)然，在實際情況中圓心間距是不固定的，因此分以下兩種情況進(jìn)行討論：(1) 圓心間距：此時，若以為邊長構(gòu)成正三角形結(jié)構(gòu)，則在正三角形中心位置會出現(xiàn)小的空隙（見圖2中的陰影部分），這對于最小覆蓋來說是極其不利的。圖2因此，必須將最上方的圓心位置下移，使得此圓的最低點恰好通過下方兩圓交點中y方向數(shù)值較大的點(如圖2中y點所示)，顯然連接此三個圓圓心構(gòu)成的封閉折線為頂角大于60的等腰三角形。就本題來說，當(dāng)相鄰圓的公共面積不小于圓面積的5%時，兩圓間距s為175.66，滿足此條件。由于等腰三角形頂角大于60，則兩腰長度小于底邊長度，即上下兩層相鄰的圓的圓心間距小于175.66，顯然此時兩圓之間的公共部分更大，符合題目要求。按照此方案，則如圖3所示，MATLAB程序見附錄程序二（注：其中調(diào)用circle函數(shù)見附錄程序一）。圖3通過計算可知，長度 為1000的邊至少需要6個圓才能完整覆蓋。最下面一層中相鄰圓交點中 軸方向數(shù)值較小的點與 軸相交，則最有利于最小覆蓋。由基礎(chǔ)的平面幾何知識可求出最下面一層圓的圓心 坐標(biāo)為47.81，再根據(jù)上述“等腰三角形”的理論可得各層間圓的圓心 坐標(biāo)間距Sy為152.126，這樣按層級6、7、6、7間雜排列，就可以得到結(jié)果。而 軸方向有空間富余，若發(fā)現(xiàn)在邊界區(qū)域有部分空隙未能覆蓋，則可通過在 軸方向的坐標(biāo)平移來修正。最后檢驗四條邊界及四個頂點，均可落在所有圓覆蓋的區(qū)域里，則如圖3，當(dāng)相鄰圓的公共面積不小于圓面積的5%時可用45個半徑 為100的圓覆蓋此區(qū)域。 (2) 圓心間距 ：此時，若以s為邊長構(gòu)成正三角形結(jié)構(gòu)，則在正三角形中心位置會出現(xiàn)重疊部分（見圖4陰影部分）。.圖4就直觀而言似乎可以將上層圓的位置上移，但結(jié)合本題來說是不符合要求的。如：當(dāng)相鄰圓的公共面積不小于圓面積的18%時，兩圓間距為141.75，符合此情況。如果上移圓的位置，則連接此三圓圓心構(gòu)成的封閉折線為頂角小于60的等腰三角形，兩腰長度就大于底邊長度，即上下兩層相鄰的圓的圓心間距大于141.75，同時當(dāng)相鄰圓的公共面積就會小于圓面積的18%。因此，本情況只能以邊長為圓心間距的正三角形為基礎(chǔ)架構(gòu)可得出區(qū)域劃分方案（如圖5）。MATLAB程序見附錄程序三（注：其中調(diào)用circle函數(shù)見附錄程序一）。圖5與上面類似，通過計算可知，長度 為1000的邊至少需要7個圓才能完整覆蓋，則以邊長 為141.75的正三角形為基本構(gòu)架，即各層間圓心在y軸方向間距 為122.759，按層級7、8、7、8間雜排列，可得到結(jié)果。最后檢驗四條邊界及四個頂點，最下層的7個圓為了使交點與 軸重合，所能覆蓋的 方向長度不到994，而在此情況中最上層與最下層中相鄰圓交點在 軸方向上間距 為1000.3，幾乎沒有在 軸方向上做坐標(biāo)平移的可能，所以只好再補(bǔ)一個圓，即圖5中右下角的圓。則當(dāng)相鄰圓的公共面積不小于圓面積的18%時可以用61個半徑為100的圓覆蓋此區(qū)域。4.1.3 信道分配可將圖3中圓按序編號進(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鄰接時：Mij=1；當(dāng)i和j不鄰接時：Mij=0。具體的矩陣形式參見附錄程序五中的MVNVN定義。此后的問題就轉(zhuǎ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)，使任何子集中的元素均無關(guān)系，同時要求子集個數(shù)盡可能少。在此可通過編寫子集劃分程序來實現(xiàn)，簡要的算法描述如下： 集合A進(jìn)Q；result和work全部置0；當(dāng)前組號group=1； 依次出隊列得e，若worke=0（只考查關(guān)系未定的元素），則在work中，標(biāo)記e的沖突關(guān)系。即： 若Mei=1 & worki=0，則worki=1； （避免改寫worki為-1的單元） 若worki=0，則resulti=group; worki=-1; 若worki=1，則worki=0; 將所有worki=0的元素，再進(jìn)隊列； group+； 轉(zhuǎn)，直至Q為空。具體的程序見附錄程序五(注：程序所需Division.h文件見附錄程序四)。由此可得出滿足相鄰圓的公共面積不小于圓面積的5%條件信道劃分結(jié)果，見表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個信道，示意圖見圖6。同理，將圖5中圓按序編號進(jìn)行改造，也可以得到滿足相鄰圓的公共面積不小于圓面積的18%條件的信道劃分結(jié)果也為4個，其示意圖見圖7。圖6圖74.1.4 抗毀性討論在通信中，抗毀性的定義是在網(wǎng)絡(luò)有故障時的通信能力，在本題中可以理解為位于圓心的節(jié)點在有與外界進(jìn)行通信的需求時，即使在此圓所覆蓋的區(qū)域內(nèi)有部分節(jié)點不能正常工作，依然有與外界進(jìn)行通信的能力；而處于兩圓公共部分的節(jié)點在這兩個圓的圓心節(jié)點被抽取時就不具備通信能力了。根據(jù)以上的理解可以認(rèn)為，當(dāng)相臨圓心的節(jié)點被抽掉以及一個圓周圍的所有與其它圓聯(lián)通的節(jié)點都被抽掉的時候，就會影響整個網(wǎng)絡(luò)的連通性。針對以上的分析，分以下兩種情況進(jìn)行討論：(1) 當(dāng)抽取圓公共部分節(jié)點時情況比較復(fù)雜，于是考慮將問題簡化為抽出特定的一組不在圓心的節(jié)點后，網(wǎng)絡(luò)可能被毀。表3表示這種特定點的分組情況抽取特定點數(shù)5的情況18的情況2033106481354662333表3由古典概型的定義可以得出抗毀性的量化標(biāo)準(zhǔn)，但由于計算繁瑣，可近一步簡化。將以上兩組數(shù)據(jù)加權(quán)平均后可得其值都近似等于5，故可以認(rèn)為特定的5個不位于圓心的節(jié)點為抗毀性的基本單位，只要此特定的5點不同時被抽取則可認(rèn)為網(wǎng)絡(luò)正常。(2) 當(dāng)抽取圓中心節(jié)點時，若節(jié)點數(shù)小于2則不影響網(wǎng)絡(luò)連通；若節(jié)點數(shù)等于2時，則根據(jù)上面的結(jié)構(gòu)可得出公共面積為5%時網(wǎng)絡(luò)損毀概率為，公共面積為18%時網(wǎng)絡(luò)損毀概率為；而若節(jié)點數(shù)大于2時，因為根據(jù)題意，在三圓公共部分沒有節(jié)點，故可近似看作先取兩相鄰圓在任意取其它圓，則損毀概率與等于2時相同。綜合兩種情況，再利用古典概型的定義，可近似得出抗毀性的量化值k，羅列如下：公共面積5%的情況抽掉2%（3點）： 抽掉5%（8點）： 抽掉10%（15點）： 抽掉15%（23點）： 公共面積18%的情況抽掉2%（4點）： 抽掉5%（11點）： 抽掉10%（21點）： 抽掉15%（32點）： 4.1.5 問題1總結(jié)經(jīng)過上述四個步驟的計算、編程、求解，我們可以得出，將此正方形區(qū)域用若干個半徑都是100的圓完全覆蓋，在相鄰兩個圓的公共面積不小于一個圓面積的5%的情況下，最少需要45個圓；相鄰兩個圓的公共面積不小于一個圓面積的18%的情況下，則最少需要61個圓。分別考慮在公共面積不小于一個圓面積的5%和18%兩種情況下，若給每個圓分配一個信道使得有公共部分的圓擁有不同的信道，最少需要的信道數(shù)都為4個。若每個公共部分中心和相應(yīng)圓心各恰有一個節(jié)點，在節(jié)點集合中，隨機(jī)地抽掉2%、5%、10%、15%等數(shù)量的節(jié)點，在公共面積不小于5%和18%的兩種情況下，網(wǎng)絡(luò)的抗毀性可以定量分析得出。對于問題1各問的結(jié)果，我們匯總?cè)绫?。公共面積5情況公共面積18情況覆蓋圓的個數(shù)4561所需信道個數(shù)44抗毀性抽掉288.8991.69%抽掉588.87%91.6%抽掉1088.8%91.51%抽掉1587.02%88.57%表44.2 問題2的解決4.2.1 替代圓規(guī)則為了更好的表述改進(jìn)后的情況，首先作出相應(yīng)的圖形（見圖8）。圖8又由于最關(guān)心的數(shù)據(jù)為所有圓的半徑和，表5給出部分半徑分別為100和75的圓的各自的半徑和。圓的個數(shù)半徑75圓的半徑和半徑100圓的半徑和1751002150200322530043004005375500表5由上表可以直觀的看出我們可以接受的替換：1個小圓替換1個大圓，2個小圓替換2個大圓，4個小圓替換3個大圓，6個小圓替換5個大圓而4個小圓可覆蓋面積為22500，3個大圓可覆蓋面積為30000；6個小圓可覆蓋面積為33750，5個大圓可覆蓋面積為50000。顯然，由于面積與半徑為平方關(guān)系，需要覆蓋多個大圓面積就需要更多的小圓，因此除去大圓覆蓋大面積無效的情況，最實惠的做法是用1個小圓去替換1個大圓。顯然，在圖8中間位置與湖面相交的圓可以用半徑為75的小圓代替，左右兩邊界各有3個大圓可用小一些的圓替代。根據(jù)相鄰圓之間的公共面積不小于大圓面積的5%，及以我們的方案進(jìn)行區(qū)域劃分時相鄰兩層圓的圓心距不得小于152.126的條件，可以得出這6個圓最小半徑約為80。改動后的區(qū)域劃分如圖9所示，其半徑和為4355。圖94.2.2 信道分配這里的原理與1.3相同，因此直接給出結(jié)果示意圖，見圖10。圖104.3 問題3的解決4.3.1 區(qū)域的劃分首先根據(jù)所給的數(shù)據(jù)畫出這些點在正方形區(qū)域內(nèi)的分布散點圖，如圖11所示。圖11顯而易見，這些大量的點的分布是雜亂無章的，可由如下思想對此進(jìn)行分簇：(1) 通過定義一組起始簇中心進(jìn)行分簇，初始簇中心可隨機(jī)產(chǎn)生。(2) 根據(jù)輸入數(shù)據(jù)把每個數(shù)據(jù)分到與其最相似的簇。(3) 在分完所有的數(shù)據(jù)后，更新簇中心以反映分到每一個簇的新的數(shù)據(jù)情況。(4) 再次檢查記錄，以確定是否將其重新分到別的簇。(5) 進(jìn)行遞歸，直到達(dá)到最大遞歸次數(shù)或者前后兩次遞歸之間的差異不超過指定閥值?？梢苑奖愕乩媒y(tǒng)計軟件SPSS對這些數(shù)據(jù)進(jìn)行分簇，只需滿足條件：每個簇中的所有節(jié)點到簇中心的最大距離小于等于100即可。其結(jié)果見附錄表一，示意圖見圖12。圖12此圖所示各圓所包含的節(jié)點使用相同的信道，由于Ad Hoc網(wǎng)絡(luò)一跳覆蓋區(qū)的圓心、半徑在不斷變化，以上僅是區(qū)域劃分示意圖。當(dāng)區(qū)域中有湖時，編寫程序先剔除位于湖中的節(jié)點，具體程序見附錄程序六。再利用SPSS進(jìn)行分簇，具體圖示見圖13。圖13圖14圖15但僅僅以上的結(jié)論并不一定能夠滿足有轉(zhuǎn)發(fā)任務(wù)的公共面積不小于較大一跳覆蓋區(qū)面積的5%，因此需要對得到的數(shù)據(jù)進(jìn)行修正。為此我們設(shè)計了“自適應(yīng)修正算法”，此算法由兩個子程序組成，分別附于附錄程序七和程序八。通過程序七可初步檢驗出所有不滿足公共面積5%條件的圓心對，但根據(jù)題意，沒有轉(zhuǎn)發(fā)任務(wù)的公共區(qū)域并沒有5%的要求，顯然當(dāng)公共區(qū)域中沒有節(jié)點時就可以認(rèn)為沒有轉(zhuǎn)發(fā)任務(wù)。將程序七得出的數(shù)據(jù)再傳入程序八，可進(jìn)一步判斷出有轉(zhuǎn)發(fā)任務(wù)且不滿足5%條件的公共區(qū)域。將與這些公共區(qū)域相關(guān)的圓的半徑稍作放大（始終讓其不大于100）后得到新的數(shù)據(jù)重新傳入程序七進(jìn)行迭代，并在此過程中記錄下不滿足條件的節(jié)點數(shù)最少時的狀態(tài)。經(jīng)過一定次數(shù)的迭代后，若仍然存在不滿足條件的節(jié)點，則調(diào)出先前的最佳記錄，通過微調(diào)圓心位置使所有節(jié)點滿足要求。修正后的示意圖分別見圖14和圖15。此時，得到的在無湖和有湖狀態(tài)下全部一跳覆蓋區(qū)的半徑和分別為4670.42672與4361.02504。4.3.2 信道分配方案信道劃分的方法如前所述，這里不再贅述，僅給出示意圖：圖16、圖17。圖16圖174.3.3 區(qū)域連通的充分、必要條件由于這里的組網(wǎng)方式是基于簇的，所以在同一簇里的節(jié)點既可以作為一跳覆蓋區(qū)的中心節(jié)點，也可以作為公共部分的節(jié)點。當(dāng)一個簇里有節(jié)點處在工作狀態(tài)下，則所處區(qū)域也出于連通狀態(tài)，這就是區(qū)域連通的充分條件；反之，當(dāng)區(qū)域連通時，所在簇中至少有一個節(jié)點出于工作狀態(tài)，這即為必要條件。4.3.4 網(wǎng)絡(luò)的抗毀性對于網(wǎng)絡(luò)的抗毀性，可借鑒問題1的思路，并根據(jù)以上充分、必要條件加以討論。無湖時的分簇情況有湖時的分簇情況組號 包含點個數(shù)組號 包含點個數(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)為在無湖與有湖狀態(tài)下的最小抗毀單位均為17。由于節(jié)點的大量增多，及運算越來越復(fù)雜，甚至導(dǎo)致計算機(jī)出現(xiàn)數(shù)據(jù)溢出的現(xiàn)象，在此給出定性分析。兩種情況在抽取2節(jié)點時網(wǎng)絡(luò)毀滅概率的計算公式分別為和，幾乎近似等于零，遠(yuǎn)比第一種劃分方式要好。而當(dāng)抽取比例越來越大時，抗毀性不斷衰減，且開始時衰減速度較慢，當(dāng)?shù)竭_(dá)某一臨界值時衰減速率急劇增加。4.4 問題4的解決4.4.1 模型建立在上一問的基礎(chǔ)上這里引入了十個以方向角服從0,2均勻分布，速度服從0,2均勻分布的隨機(jī)變量，其運動方式與物理學(xué)中的布朗運動性質(zhì)相似。因此借助布朗運動的結(jié)論，若 以節(jié)點在t=0時的位置為原點，則節(jié)點在時間 t 及位置 x 時的概率密度可表達(dá)為：其中D表示一正常數(shù)，在本題中D即為速度的期望值，即D1。由于原本此點在某一簇內(nèi)，故其最后距起始點不超過100則其聯(lián)通性不受影響。而當(dāng)t=400時，距離超過100的概率為：4.4.2 模型驗證根據(jù)以上結(jié)論可認(rèn)為若節(jié)點作布朗運動則幾乎不影響網(wǎng)絡(luò)聯(lián)通性。當(dāng)然本題中節(jié)點運動所不同的是運動狀態(tài)不是時時改變，而是間隔30個單位，為了更好地驗證這一隨機(jī)過程，可通過編寫程序來模擬此過程，具體程序見附錄程序九。再將最終的狀態(tài)作出直觀圖，見圖18。圖18經(jīng)過程序仿真后所得的結(jié)果也可以直觀地看出此例中的Ad Hoc網(wǎng)絡(luò)在400單位時間后是連通的，4.5 問題5的解決4.5.1 理論模型由于節(jié)點退出是因為能量耗盡，可見本問題的關(guān)鍵是找出節(jié)點能量消耗與起所處位置的關(guān)系。為了說明方便，引入如下符號：由于能量E由發(fā)射能量、接收能量和備用能量三部分組成，若發(fā)射、接收、備用三種狀態(tài)所對應(yīng)的功率和時間分別為、和、，則：由于: : =11 : 10 : 1，上式可轉(zhuǎn)換為：其中為常量，顯然，要使工作時間盡可能的大，則的值要盡可能的大；反之，要使工作時間t盡可能的小，則的值要盡可能的小。由于兩節(jié)點之間原始（不是轉(zhuǎn)發(fā)）的平均通信次數(shù)大致與它們之間的距離的平方成反比，可將發(fā)射狀態(tài)和接收狀態(tài)歸結(jié)為通信狀態(tài)，則可認(rèn)為節(jié)點處于通信狀態(tài)時其發(fā)射和接收狀態(tài)為等概率事件。根據(jù)題目要求，問題轉(zhuǎn)化為找出所有節(jié)點中處于備用狀態(tài)時間最短或處于通信狀態(tài)時間最長的節(jié)點。根據(jù)題意，分下列兩類情況討論：(1) 任取一節(jié)點，討論其發(fā)射一次所消耗的能量：在給出的所有數(shù)據(jù)點中任取一點，其坐標(biāo)為(,)，若此點對所有的點發(fā)射信息，則將其距離記為，持續(xù)時間記為。根據(jù)發(fā)射功率近似地與最大傳輸距離的三次方成正比以及兩節(jié)點之間原始（不是轉(zhuǎn)發(fā)）的平均通信次數(shù)大致與它們之間的距離的平方成反比的條件，可以得到如下等式：上式中、為常量，根據(jù)題意服從期望為4的指數(shù)分布，而所有點的坐標(biāo)已知，則，已知。由于樣本容量為926，足夠大，則根據(jù)獨立同分布的中心極限定理可以得到當(dāng)=0.05時，其置信區(qū)間上下限值約為0.25。由此可見，對的影響可近似看作與呈一次線形關(guān)系。(2) 任取一節(jié)點，討論其在某一段時間內(nèi)對所有點的發(fā)射次數(shù)：在給出的所有數(shù)據(jù)點中任取一點，其坐標(biāo)為(,)，若此點對所有的點發(fā)射信息，則將其距離記為。根據(jù)兩節(jié)點之間原始（不是轉(zhuǎn)發(fā)）的平均通信次數(shù)大致與它們之間的距離的平方成反比的條件，可以得到如下等式：為避免討論于分母的情況并簡化計算，提出每一次發(fā)射的單位時間的概念，即每一次發(fā)射的起始時刻與下一次發(fā)射的起始時刻之間的時間間隔t。則可以得到下式：顯然，這里N的變化可看作受的影響，且越小，越大。綜合上面的兩種情況，在某一段時間內(nèi)因發(fā)射所消耗的能量即為，其改變趨勢主要受影響，即方向與相反，趨勢與相同。所以要得出處于發(fā)射狀態(tài)時間最長的節(jié)點只要找出使有最大值的節(jié)點位置即可。而接收狀態(tài)與發(fā)射狀態(tài)一致，故整個問題可轉(zhuǎn)換為找出使有最大值的節(jié)點位置。以下給出推導(dǎo)過程：由于與為常量，使與取得最大值的點坐標(biāo)為(,)，可以定義此點為能量中心點F。節(jié)點離F點越近，則用于通信的能量占總能量的比例越大，耗盡能量而退出網(wǎng)絡(luò)的時間越早；節(jié)點離F點越遠(yuǎn)，則用于通信的能量占總能量的比例越小，耗盡能量而退出網(wǎng)絡(luò)的時間越遲。因此，以F點為圓心作圓，其半徑越大，此區(qū)域內(nèi)節(jié)點能量耗盡而退出網(wǎng)絡(luò)的時間就越晚，即出現(xiàn)第一個退出網(wǎng)絡(luò)的節(jié)點的時間盡量長。4.5.1 具體實現(xiàn)根據(jù)本題所提供的數(shù)據(jù)可以得到，F(xiàn)點坐標(biāo)為(493.913,499.031)，以F點為圓心，100為半徑，此區(qū)域內(nèi)的節(jié)點即為一簇，剩余的節(jié)點可按照第3問中有湖的情況進(jìn)行劃分即可。具體的區(qū)域劃分的方案如圖19所示。圖19然后再調(diào)用程序七、程序八對一跳覆蓋區(qū)的覆蓋范圍進(jìn)行修正，使其滿足有轉(zhuǎn)發(fā)任務(wù)的相鄰一跳覆蓋區(qū)的公共面積不小于較大一跳覆蓋區(qū)面積5%的條件，并得出在此情況下全部一跳覆蓋區(qū)的半徑和為4549.70887。具體分布見圖20。圖20根據(jù)第3問中區(qū)域連通的充分條件，以及本問題中提出的能量中心理論，則在一段時間后，此正方形區(qū)域中央的一跳覆蓋區(qū)首先毀滅，隨之其周圍的一跳覆蓋區(qū)相繼毀滅，直至最后。所以如果要對組網(wǎng)方式進(jìn)行改進(jìn)，可以考慮在能量中心附近多分布一些一跳覆蓋區(qū)以分擔(dān)其通信任務(wù)。4.6 問題6的解決4.6.1 問題分析本問題要討論的是一個動態(tài)過程，比前面的問題要復(fù)雜的多。再加上Ad Hoc特殊的網(wǎng)絡(luò)拓補(bǔ)結(jié)構(gòu)，以及題目所提供的大量節(jié)點使得問題更為復(fù)雜。解決復(fù)雜的問題自然需要簡化，一種方法是對Ad Hoc網(wǎng)絡(luò)復(fù)雜的路由進(jìn)行等效的分割，通過對部分節(jié)點的研究來推導(dǎo)出全局節(jié)點的總體特征；另一種方法是在眾多影響結(jié)果的條件中先著重考慮影響最顯著的條件，然后再逐步加入其它條件，使之接近于題設(shè)情況。如本題所要討論的通信質(zhì)量，可依照以上兩條途徑尋找解決方案。一條途徑是先找出節(jié)點與節(jié)點之間通信質(zhì)量的關(guān)系，再找到簇與簇之間通信質(zhì)量的關(guān)系，最后歸結(jié)到整個局域網(wǎng)的通信質(zhì)量。另一條途徑是首先考慮丟包（即重發(fā)或延時）的因素，再考慮因節(jié)點能量耗盡而退出的因素，最后歸納出所有的因素。當(dāng)然，將兩條途徑綜合考慮也許更正確，但是由于時間的限制，無法更深一步進(jìn)行探討，謹(jǐn)在此提出一些初步的想法。參考文獻(xiàn)1 蔣杰，方力，張鶴穎，竇文華 無線傳感器網(wǎng)絡(luò)最小連通覆蓋集問題求解算法 Journal of Software Vol.17,No.2,February 2006,pp.175-184.2 潘麗君 戰(zhàn)場通信網(wǎng)戰(zhàn)時抗毀性初探 裝甲兵工程學(xué)院學(xué)報 2006，4，Vol.20 ,No.2,pp:21-25.3 陳建國 基于管理技術(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)計分析 中國水利水電出版社， 2003.6 張森 張正亮 MATLAB仿真技術(shù)與實例應(yīng)用教程 機(jī)械工業(yè)出版社， 2004.7 王紀(jì)林，賀才興等 概率論與數(shù)理統(tǒng)計 科學(xué)出版社， 2000.8 陳華生，張岳新 Visual C+程序設(shè)計基礎(chǔ) 蘇州大學(xué)出版社， 2000.9 壽紀(jì)麟 數(shù)學(xué)建模方法與范例 西安交通大學(xué)出版社， 1995.附錄程序一function h=circle(r,x0,y0,C,Nb) % r 圓的半徑。 % x0,y0 圓心座標(biāo)。% C圓的顏色，不說明時，由指令依序指定。% Nb繪圓時所用點數(shù)，若不指定，則以300點為預(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é)點數(shù)#define QSIZE VN+1 / 隊列大?。鹤疃啻娣臯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,