Ad Hoc網(wǎng)絡(luò)建立和分配問(wèn)題

1、vi本文討論了AdHoc網(wǎng)絡(luò)在一個(gè)假定區(qū)域中針對(duì)不同條件建立覆蓋區(qū)，以及信道分配的優(yōu)化方案，并討論了各個(gè)方案的抗毀性。其中選取覆蓋區(qū)方案的問(wèn)題都可以歸結(jié)為帶有約束的最優(yōu)化問(wèn)題。對(duì)于各題目中的不同的條件，分別建立了不同的最優(yōu)化模型，但是對(duì)這些問(wèn)題的直接求解方法都是NP完全問(wèn)題，因此針對(duì)各題的特點(diǎn)，本文分別采用了不同的近似方法，從而在較短的時(shí)間內(nèi)得到了較優(yōu)的解。之后根據(jù)覆蓋區(qū)選取方案，信道分配問(wèn)題可以轉(zhuǎn)化成平面圖著色問(wèn)題。利用圖論中經(jīng)典算法得到了具體的信道分配方案。最后，利用圖的連通性定義了抗毀性的度量，并用蒙特卡羅模擬法計(jì)算出了抗毀性的近似值。問(wèn)題1的最優(yōu)化模型為：目標(biāo)：所用圓的個(gè)數(shù)最少約束1：

2、正方形區(qū)域被完全覆蓋約束2：相鄰兩個(gè)圓的公共面積不小于一個(gè)圓面積的5%minnkxS(c),1i,jl這bx(G)個(gè)點(diǎn)在平面上分布的一種組合ka(f)所有可能存在的r的個(gè)數(shù)lis蒙特卡羅模擬中，某一次模擬隨機(jī)產(chǎn)生的點(diǎn)分布為蒙特卡羅模擬的模擬迭代次數(shù)平面的圓覆蓋問(wèn)題1.1圓個(gè)數(shù)的最小值最優(yōu)化模型本問(wèn)題可以歸結(jié)為一個(gè)最優(yōu)化問(wèn)題：目標(biāo)：所用圓的個(gè)數(shù)最少約束1：正方形區(qū)域被完全覆蓋約束2：相鄰兩個(gè)圓的公共面積不小于一個(gè)圓面積的5%設(shè)用一組半徑r二100圓Cc,c，,c來(lái)覆蓋這個(gè)1000 x1000的平面區(qū)域P，設(shè)p為12nP上任一點(diǎn)，用S來(lái)表示面積，則以上最優(yōu)化問(wèn)題可表述為：minnTOC o 1-5

3、 h zkxS(c),1i,jn且c與c相令Bijiij其中k表示相鄰兩個(gè)圓的公共面積占一個(gè)圓面積比例的下限，本問(wèn)題中k二0.05用(x,y)表示第i個(gè)圓的圓心坐標(biāo)(1in),則在平面區(qū)域P上一定存在一圓心的集ii合O(x,y),(x,y)，,(x,y)使得n最小。然而這個(gè)優(yōu)化問(wèn)題的求解是一個(gè)NP完全問(wèn)1122nn題，不存在多項(xiàng)式時(shí)間的解法。因此我們針對(duì)AdHoc網(wǎng)絡(luò)的特點(diǎn)，利用分析的方法得到一個(gè)較為滿意的解。覆蓋數(shù)的定義定義一：平面上一個(gè)圓c覆蓋點(diǎn)pop在c的內(nèi)部。且規(guī)定：處于圓周上的點(diǎn)不ii算覆蓋。定義二：用一組圓Cc,c，,c來(lái)覆蓋一個(gè)平面，在平面上任取一點(diǎn)p，覆蓋著p的12n圓的總個(gè)數(shù)

4、稱(chēng)為點(diǎn)p的圓覆蓋數(shù)。定義平面上所有點(diǎn)中最大的圓覆蓋數(shù)為C的覆蓋數(shù)，記為N。c定義三：用一組圓Cc,c，,c來(lái)覆蓋一個(gè)平面，定義這組圓所能覆蓋的總面積即12ncUcUUc為C的有效面積，記為S。12nv1.1.3平面鑲嵌連接圓的各個(gè)交點(diǎn)則在圓內(nèi)構(gòu)成內(nèi)接多邊形，如圖1所示。在N=2的情況下，相鄰c的圓的內(nèi)接多邊形之間沒(méi)有覆蓋關(guān)系。設(shè)圓c對(duì)應(yīng)的內(nèi)接多邊形為q，C的邊緣上的剩余ii的圓冠為d則qAq門(mén)門(mén)qAdAd門(mén)門(mén)d=0。則有效面積S為：i12n12kvS=S(q)+S(q)+S(q)+S(d)+S(d)+S(d)v12n12m其中m表示處于邊緣的圓的個(gè)數(shù)。因此平面的圓覆蓋問(wèn)題可以轉(zhuǎn)化為平面的多邊形

5、鑲嵌問(wèn)題。也就是說(shuō)，只要在平面區(qū)域P上得到一種平面鑲嵌方案，作出各個(gè)多邊形的外接圓，就可以得到一種圓覆蓋方案。圖1均衡性對(duì)AdHoc網(wǎng)絡(luò)的性能有著很大的影響。均衡性更好的網(wǎng)絡(luò)，網(wǎng)絡(luò)負(fù)荷分布更加均衡，并且由于其存在熱點(diǎn)節(jié)點(diǎn)的可能性更小，更不容易形成網(wǎng)絡(luò)中的流量瓶頸從而降低網(wǎng)絡(luò)的連通性，其業(yè)務(wù)性能也得到了提高204。而一跳覆蓋區(qū)在平面區(qū)域P上的分布情況則直接影響著AdHoc網(wǎng)絡(luò)的均衡性，因此為了使得形成的AdHoc網(wǎng)絡(luò)具有較好的均衡性，我們用全等的正多邊形來(lái)鑲嵌平面區(qū)域P。根據(jù)鑲嵌問(wèn)題的經(jīng)典結(jié)論，正三角形、正方形和正六邊形是僅有的三種自鑲嵌正多邊形。根據(jù)這三種圖形生成的圓覆蓋中，相鄰圓的公共面積占

6、圓面積的比例如表1所示。圖形相鄰圓的公共部分占圓面積的比例正三角形39.1%正方形18.16%正六邊形5.77%表1由于相鄰圓的覆蓋面積越大，有效面積越小，因此應(yīng)當(dāng)選擇盡量小的相交面積，而正六邊形剛好滿足約束且相鄰圓的公共面積最小。圖2根據(jù)圖2，可算得此時(shí)需要圓45個(gè)。1.2平面覆蓋的信道分配問(wèn)題根據(jù)1.1中的結(jié)論，平面區(qū)域P所在平面被半徑r100的正六邊形所鑲嵌，從另一個(gè)角度來(lái)說(shuō)，平面區(qū)域P被分割為一系列不重疊的區(qū)域。由于圓和正六邊形存在對(duì)應(yīng)的關(guān)系，只要使相鄰的正六邊形使用不同的信道便可以滿足題目中“有公共部分的圓使用不同的信道”這個(gè)要求。設(shè)為圓c分配信道頻率v，也即正六邊形q的信道頻率為v

7、。如果將平面區(qū)域P看作iiii地圖平面，q的邊界看作國(guó)境線，v看作要為q著上的顏色，則本問(wèn)中的信道分配問(wèn)題等iii價(jià)于一個(gè)平面地圖的著色問(wèn)題。利用圖論中經(jīng)典著色算法，可得本問(wèn)中的信道分配情況如圖3所示，最少需要3個(gè)信道。圖31.3k二0.18的情況1.3.1覆蓋方案根據(jù)表1,利用1.1中的結(jié)論，若將約束2中的公共面積調(diào)整為18%即k二0.18，則應(yīng)當(dāng)選擇正方形來(lái)完成平面的鑲嵌，得到兩種覆蓋方案，如圖2，圖3所示，其中圖2需要60個(gè)圓，圖3需要64個(gè)圓。圖4仔細(xì)觀察圖2和圖3，可以發(fā)現(xiàn)這兩幅圖中，各個(gè)圓之間的相對(duì)位置關(guān)系是一樣的，圖2以其中心為軸順時(shí)針（或逆時(shí)針）旋轉(zhuǎn)45。即得到圖3。在圖3中，

8、位于平面區(qū)域P的右邊緣和下邊緣的圓，大部分的面積都在平面區(qū)域P以外，有較大的面積損失，因此需要更多的圓來(lái)完成這個(gè)完全覆蓋。因此應(yīng)本問(wèn)題當(dāng)采用圖2的覆蓋方案，需要60個(gè)圓來(lái)完成覆蓋。1.3.2信道分配方案和1.2相似，本問(wèn)中的信道分配問(wèn)題也是一個(gè)平面的著色問(wèn)題，我們得到的結(jié)果如圖6所示，最少需要2個(gè)信道。圖61.4網(wǎng)絡(luò)的抗毀性1.4.1抗毀性度量對(duì)于某種覆蓋方案，根據(jù)題意，每個(gè)公共部分中心和相應(yīng)圓心各恰有一個(gè)節(jié)點(diǎn)。如果兩個(gè)節(jié)點(diǎn)d和d通信時(shí)，不需要借助第三個(gè)節(jié)點(diǎn)d對(duì)數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，則稱(chēng)d和d是一ijkij跳連通的。連接平面上所有一跳連通的節(jié)點(diǎn)，形成一個(gè)無(wú)向圖G。我們通過(guò)對(duì)G的連通kk性來(lái)討論AdH

9、oc網(wǎng)絡(luò)的抗毀性。設(shè)b為從節(jié)點(diǎn)集合中隨機(jī)抽掉的節(jié)點(diǎn)個(gè)數(shù)占節(jié)點(diǎn)總個(gè)數(shù)的比例。用y表示無(wú)向圖中點(diǎn)的個(gè)數(shù)，k表示無(wú)向圖中最大連通分支中包含的點(diǎn)的個(gè)數(shù)。用G表示從G中隨機(jī)抽掉kkbxy(G)個(gè)節(jié)點(diǎn)后的形成的無(wú)向圖。則AdHoc網(wǎng)絡(luò)的抗毀性D可定義為關(guān)于b的函數(shù)：kD(b)二K(Gk)(1-b)xy(G)k1.4.2蒙特卡羅模擬及結(jié)果對(duì)于某一種覆蓋方案，網(wǎng)絡(luò)的抗毀性D，除了b的取值之外，還和從G中隨機(jī)抽掉k的bxy(G)個(gè)點(diǎn)的位置有關(guān)。因此D(b)應(yīng)當(dāng)用這bxy(G)個(gè)點(diǎn)在平面上分布的所有可能kk情況的平均值來(lái)計(jì)算。用向量l表示這bxy(G)個(gè)點(diǎn)在平面上分布的一種組合，a(l)表示k所有可能存在的l的個(gè)

10、數(shù)。則:D(b)二工D(b,I)這種計(jì)算方法會(huì)產(chǎn)生組合爆炸的問(wèn)題，因此我們采用蒙特卡羅模擬方法近似的求解D(b)，設(shè)蒙特卡羅模擬中，某一次模擬隨機(jī)產(chǎn)生的點(diǎn)分布為I，模擬迭代次數(shù)為s，則iD(b)=工D(b,I.)is對(duì)1.1和1.3中求得的覆蓋方案進(jìn)行蒙特卡羅模擬，得到結(jié)果如表2、3所示圖7一個(gè)去掉15%點(diǎn)的例子k二5%，圖2分配方案的模擬結(jié)果:s二10s二100s二1000d=2%100%99.89%99.93%d=5%100%99.63%99.66%d二10%100%99.58%99.55%d二15%100%99.51%99.49%表2k二18%，圖4分配方案的模擬結(jié)果:s二10s二100

11、s二1000d=2%100%99.89%99.93%d=5%100%99.63%99.66%d二10%100%99.58%99.55%d二15%100%99.51%99.49%表3帶有湖區(qū)的平面覆蓋問(wèn)題和信道分配方案2.1最優(yōu)化模型將本問(wèn)題歸結(jié)為一個(gè)最優(yōu)化問(wèn)題，則：目標(biāo)：所有圓的半徑之和最小約束1：相鄰兩個(gè)圓的公共面積不小于大圓面積的5%約束2：地面被圓完全覆蓋約束3：節(jié)點(diǎn)不能存在于湖中設(shè)湖區(qū)所覆蓋的區(qū)域?yàn)镼,d為處于每個(gè)圓的圓心或相鄰圓公共部分中心的節(jié)點(diǎn)(也i可稱(chēng)終端或用戶)，m為節(jié)點(diǎn)個(gè)數(shù)，p為平面上任一點(diǎn)，則本問(wèn)題的最優(yōu)化模型的數(shù)學(xué)表述如下：minr1inii=1kxmaxS(c),S(c

12、)c與c有公共部分1i,jnTOC o 1-5 h zijijijVpe(P-Q)pecUcUUc12ndgQ1imi(2)其中k表示相鄰兩個(gè)圓的公共面積占一個(gè)圓面積比例的下限，本問(wèn)題中k=0.05用(x,y,r)這個(gè)三元組來(lái)表示圓c的圓心坐標(biāo)和半徑，根據(jù)題意，1x1000，iiiii1y1000，75r100，則在此范圍內(nèi)，一定存在一個(gè)集合iiO(x,y,z),(x,y,z)，,(x,y,z)使得所有圓的的半徑之和最短。與1.1.1中的問(wèn)題相1111222nnn似，這個(gè)問(wèn)題無(wú)法找到多項(xiàng)式時(shí)間的解法。用1.1中正六邊形鑲嵌方法得到的圓的分布作為初始值，利用遺傳算法可以搜索一個(gè)較優(yōu)的解。2.2遺

13、傳算法遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的高度并行、隨機(jī)、自適應(yīng)搜索算法。它模仿自然界生物進(jìn)化過(guò)程中“物競(jìng)天擇,適者生存”的原理而進(jìn)行的一種多參數(shù)、多群體同時(shí)優(yōu)化方法。遺傳算法由編碼方案，初始種群的選取，個(gè)體適應(yīng)度，選擇，繁殖，雜交，變異，約束處理，迭代終止條件這幾個(gè)部分構(gòu)成，下面分別闡述。2.2.1算法框架圖82.2.2編碼方案本問(wèn)題中，覆蓋在平面區(qū)域P-Q上的圓的個(gè)數(shù)在演化過(guò)程中不是一個(gè)固定的值，因此我們?nèi)∑渖辖鏝作為基因的長(zhǎng)度。則種群中一個(gè)個(gè)體的基因G是一個(gè)長(zhǎng)度為N的串,gg其中的每一個(gè)結(jié)點(diǎn)Gi是一個(gè)三元組(x,y,r)，其中1x10001y1000，iiiii75r100。

14、iN的求取辦法為：對(duì)平面區(qū)域P進(jìn)行邊長(zhǎng)為75的正六邊形鑲嵌，由這種鑲嵌得到的g圓覆蓋個(gè)數(shù)即為N的取值。g編碼時(shí)，從G0開(kāi)始順次將區(qū)域P-Q中的圓的信息編入G,設(shè)此時(shí)區(qū)域P-Q中的圓的個(gè)數(shù)為N,則G中只有G0GN-1范圍內(nèi)的節(jié)點(diǎn)表達(dá)有效信息，因此定義N為vvv基因G的有效長(zhǎng)度。2.2.3初始種群的選取在1.1的圓覆蓋方案的基礎(chǔ)上，在平面區(qū)域P上添加湖區(qū)Q之后的結(jié)果如圖5所示。顯然，圓心處與湖區(qū)中的圓是無(wú)效的，因此我們先除去這類(lèi)圓。將此種圓分布方案編碼，作為種群中的第一個(gè)個(gè)體V。0設(shè)種群規(guī)模為S，對(duì)種群中的個(gè)體交替應(yīng)用變異策略和繁殖策略，并對(duì)新個(gè)體應(yīng)用a相應(yīng)的約束處理，直道個(gè)體總數(shù)達(dá)到S。a個(gè)體的

15、適應(yīng)度個(gè)體的適應(yīng)度用表達(dá)式(2)中的目標(biāo)函數(shù)來(lái)定義，則適應(yīng)度函數(shù)為f=-tvr。特別ii=1的，在此過(guò)程中對(duì)于不可行個(gè)體，也就是適應(yīng)度為-8的個(gè)體，保持其適應(yīng)度f(wàn)=-8，不重新計(jì)算。選擇策略在一次迭代中，對(duì)種群中所有個(gè)體按照其適應(yīng)度排序，取位于前50%的個(gè)體作為下一次迭代的父代個(gè)體，從種群中去除后50%的個(gè)體。繁殖策略在一次繁殖中，一個(gè)個(gè)V體完全復(fù)制其自身，生成一個(gè)與其完全相同的個(gè)體V。全ij部個(gè)體繁殖完成之后，每個(gè)個(gè)體隨機(jī)選擇一個(gè)與其基因不相同的個(gè)體與其配對(duì)，也就是說(shuō)V不可以選擇V，進(jìn)而進(jìn)行雜交。ii雜交策略針對(duì)本題的特點(diǎn)，雜交后各個(gè)圓的位置不應(yīng)當(dāng)有太大的變化，因此采用交換雜交策略。個(gè)體V和

16、個(gè)體V進(jìn)行雜交時(shí)，從G中隨機(jī)選擇一些結(jié)點(diǎn)，則在G和G的有效長(zhǎng)度之內(nèi)，TOC o 1-5 h zijiij將這些結(jié)點(diǎn)與G中與其下標(biāo)相同的結(jié)點(diǎn)互換。例如，在G中隨機(jī)選擇的結(jié)果是：5，9，ji13，則將G5和G互換，G9和G9互換，G13和G13互換。其中，隨機(jī)選擇ijijij的概率為雜交概率，記為Pc變異策略在一次迭代中，對(duì)每一個(gè)個(gè)體，要在其基因中隨機(jī)選擇若干結(jié)點(diǎn)，改變?cè)擖c(diǎn)的取值，這個(gè)概率即為個(gè)體的變異概率，記為P。改變某結(jié)點(diǎn)(x,y,r)的取值的方法是：取一個(gè)miii1,1000上的隨機(jī)數(shù)x且x主x，取一個(gè)1,1000上的隨機(jī)數(shù)y且y主y，取一個(gè)75,100上iiiiii的隨機(jī)數(shù)r且r主r，用(

17、x,yr)替代(x,y,r)。iiiiiiiii2.2.9約束處理不滿足約束條件的個(gè)體稱(chēng)為不可行個(gè)體。對(duì)于不可行個(gè)體，對(duì)其在一定范圍內(nèi)進(jìn)行修補(bǔ)，如果修補(bǔ)后的個(gè)體滿足約束，則用修補(bǔ)后的個(gè)體替換原個(gè)體。如果修補(bǔ)失敗，將其適應(yīng)度調(diào)整為-a，則該個(gè)體將在選擇過(guò)程中被淘汰。2.2.10終止條件本算法采取如下兩條終止條件：迭代次數(shù)限制：迭代次數(shù)超過(guò)S，則算法終止。max適應(yīng)度飽和：如果最近S次的迭代的最優(yōu)適應(yīng)度梯度之和小于某一閾值h，則adpt算法終止。即丸f(t+1)-f(t)5%xmaxS(c),S(c)。ijij公共面積不足其中大圓面積的5%,即S(cnc)5%連通含有節(jié)點(diǎn)5%不連通不含節(jié)點(diǎn)無(wú)意義不

18、連通表5根據(jù)以上定義，約束3轉(zhuǎn)化為兩個(gè)一跳覆蓋區(qū)c和c是否能通過(guò)cnc連通的判據(jù),ijij不再作為本問(wèn)題的一個(gè)約束出現(xiàn)。則本問(wèn)題中的最優(yōu)化模型簡(jiǎn)化為：目標(biāo)：全部一跳覆蓋覆蓋區(qū)半徑之和最小約束1：所有節(jié)點(diǎn)都要被圓覆蓋。約束2：所有節(jié)點(diǎn)都連通。設(shè)Ww,w,w為附件1中給出的節(jié)點(diǎn)構(gòu)成的集合，一跳覆蓋區(qū)集合12mCc,c，,c為點(diǎn)集W上的一個(gè)覆蓋，則本問(wèn)題的最優(yōu)化問(wèn)題為:12nnmin乙rii=1s.t.VweW3ceC,使得wec1im,1j5%Xmax(S(c),S(c)kk+1kk+11i,jm1kh一13.2遺傳算法與問(wèn)題2相似，我們采用遺傳算法來(lái)求解這個(gè)最優(yōu)化問(wèn)題。本問(wèn)題所采用的遺傳算法的編

19、碼方案，個(gè)體適應(yīng)度，選擇策略，繁殖策略，雜交策略，變異策略，約束處理，迭代終止條件均與2.2相同，只有初始種群的選取與其不同。初始種群的選取對(duì)于VweW，連接w和以w為圓心半徑為100的圓范圍內(nèi)的所有節(jié)點(diǎn)，構(gòu)成一個(gè)iii無(wú)向圖。對(duì)這個(gè)無(wú)向圖中的所有點(diǎn)，按照其度（圖論中無(wú)向圖的度）的大小進(jìn)行排序，將度最大的點(diǎn)以及所有與其直接相連的點(diǎn)劃分為一簇，并從圖中去除這些點(diǎn)。在剩下的所有點(diǎn)中，選擇度最大的點(diǎn)，將它以及所有與其直接相連的點(diǎn)劃分為一簇，并從圖中除去，按此方法不斷迭代，直到圖中不再存在任何點(diǎn)。這樣，對(duì)集合W得到一個(gè)簇劃分方案。對(duì)每一個(gè)簇分配一個(gè)一跳覆蓋區(qū)，初始時(shí)使一跳覆蓋區(qū)的圓心和簇的圓形重合。在

20、一定范圍內(nèi)調(diào)整一跳覆蓋區(qū)圓心的位置，按照3.1中區(qū)域連通的判定方法，使得所有一條覆蓋區(qū)均連通。控制參數(shù)的選擇及結(jié)果分析本問(wèn)題中控制參數(shù)的選擇如表6所示SaPcPmSmaxh1000.60.00110000105表6在此組控制參數(shù)下，得到無(wú)湖情況下的覆蓋方案如圖11所示，此時(shí)所有圓的半徑之和為：4050Ei%=/DD=A/*113J/a%vaLJ3州aaI1訐=顯DphqdI1口廣；門(mén)*Vrj1Ja1卜aoJo/：iaCip-tA,rVl二彳aoc也=1。丿-嚴(yán)r1/a.-.)y._o/廠_xtJbL-丿J2&aI|aIu，!1o_Hfd/八口&npdr1|_|n|v&U=U120飛,卜嘰-72

21、.1卜,VX-&1raKQ7:_K-宀:pr卩也J-VX門(mén)fa3JJ嘆.、此./圖11在此組控制參數(shù)下，得到有湖情況下的覆蓋方案如圖12所示，此時(shí)所有圓的半徑之和為：3300圖123.3信道分配方案根據(jù)3.2中得到的結(jié)果，在有湖和無(wú)湖的情況下，信道分配方案如圖13、14所示兩種情況下，都最多需要4個(gè)信道即可滿足要求。圖13圖143.4區(qū)域連通的充分、必要條件定義四：按照3.1中區(qū)域連通的判定方法，對(duì)某一種一跳覆蓋區(qū)的分配方案，如果兩個(gè)相鄰的一跳覆蓋區(qū)可以連通，則將它們的圓心用線段連接，形成一個(gè)無(wú)向圖G，我們c稱(chēng)G為一跳覆蓋區(qū)的分配方案的生成圖。c充分必要條件：基于生成圖的概念，區(qū)域連通的充分必

22、要條件為：一跳覆蓋區(qū)的分配方案的生成圖為連通圖。必要不充分條件區(qū)域連通的必要不充分條件為：一個(gè)一跳覆蓋區(qū)至少和一個(gè)不同的一跳覆蓋區(qū)共享一個(gè)節(jié)點(diǎn)，且該節(jié)點(diǎn)所處的公共區(qū)域的面積不小于較大的一條覆蓋區(qū)面積的5%。對(duì)用戶移動(dòng)的模擬及結(jié)果根據(jù)附件1中給出的數(shù)據(jù)，3中得到的覆蓋方案和題目中的要求，我們進(jìn)行了10次模擬，模擬結(jié)果如圖15所示。圖15圖中藍(lán)色節(jié)點(diǎn)為前10個(gè)節(jié)點(diǎn)的初始位置，紅線表示10次模擬結(jié)果中節(jié)點(diǎn)最終位置的連線。從圖15可以看出，由于這10個(gè)節(jié)點(diǎn)中只有圓6和圓7之間的節(jié)點(diǎn)承擔(dān)轉(zhuǎn)發(fā)任務(wù)，只有這個(gè)節(jié)點(diǎn)的移動(dòng)可能對(duì)造成整個(gè)網(wǎng)絡(luò)不能完全連通。通過(guò)模擬，在這10次模擬中有6次造成網(wǎng)絡(luò)不連通，4次仍保持

23、連通。對(duì)功率有限制情況下的覆蓋區(qū)域劃分方案51電池功率的極限情況討論考慮最壞的情況，即所有的節(jié)點(diǎn)都在不停的進(jìn)行發(fā)送或者接受，根據(jù)題中給定的兩個(gè)條件：（1）電池在覆蓋半徑為100發(fā)送狀態(tài)下的工作總時(shí)間是400個(gè)時(shí)間單位（2）兩節(jié)點(diǎn)之間原始（不是轉(zhuǎn)發(fā)）的平均通信次數(shù)大致與它們之間的距離的平方成反比100_1200R400R_69.336可以得到每個(gè)節(jié)點(diǎn)的極限覆蓋半徑r，即當(dāng)每個(gè)節(jié)點(diǎn)運(yùn)行1200個(gè)時(shí)間單位并且始終處在發(fā)送狀態(tài)時(shí)能夠取得的最大覆蓋半徑。公式表示為解得5.2啟發(fā)式搜索算法根據(jù)問(wèn)題五給出的對(duì)于電池消耗問(wèn)題的約束，并且考慮到該問(wèn)題的為一個(gè)NP完全問(wèn)題，因此本文在這里設(shè)計(jì)了一種基于權(quán)值的啟發(fā)式

24、搜索算法。5.2.1搜索算法設(shè)圖中的點(diǎn)集為P（p,p，pp），并且每個(gè)點(diǎn)都有一個(gè)權(quán)值以及一個(gè)鄰居表與之對(duì)12iK應(yīng)，分別記為W(w,www),N(n,n，nn)，其中K為點(diǎn)的個(gè)數(shù)。12iK12iK對(duì)于任意一點(diǎn)p，將所有與p的距離小于100的點(diǎn)加入p的鄰居表n中，n中iiiii的元素按照其與p的距離升序排列i每個(gè)點(diǎn)p可以根據(jù)522中的啟發(fā)式權(quán)值衡量公式得到一個(gè)最小的權(quán)值wii在所有的點(diǎn)中選出一個(gè)權(quán)值最小的點(diǎn)，記錄它的下標(biāo)為index更新所有的節(jié)點(diǎn)的鄰居表，將已經(jīng)被以p為圓心的圓包括的節(jié)點(diǎn)從各節(jié)點(diǎn)的index鄰居表中刪除，并檢查是否還有節(jié)點(diǎn)未被包括：如果沒(méi)有，則搜索結(jié)束，否則，跳轉(zhuǎn)至(2)，繼續(xù)搜

25、索。啟發(fā)式策略基于該問(wèn)題中對(duì)于節(jié)點(diǎn)的電池持續(xù)時(shí)間的要求，啟發(fā)式策略被歸納成如下形式。使一個(gè)覆蓋區(qū)中的各節(jié)點(diǎn)距離圓心的距離之和盡可能小，這樣可以使得各節(jié)點(diǎn)之間的覆蓋半徑盡可能的小，從而降低了同一覆蓋區(qū)中的各節(jié)點(diǎn)通信時(shí)所使用的電量。限制一個(gè)覆蓋區(qū)中的節(jié)點(diǎn)個(gè)數(shù)，因?yàn)楫?dāng)節(jié)點(diǎn)個(gè)數(shù)過(guò)多時(shí)，可能會(huì)造成某些負(fù)責(zé)轉(zhuǎn)發(fā)的節(jié)點(diǎn)的電量迅速耗盡；而當(dāng)節(jié)點(diǎn)個(gè)數(shù)過(guò)少的時(shí)候，會(huì)增加覆蓋所有點(diǎn)的覆蓋區(qū)的半徑之和，并且會(huì)減弱網(wǎng)絡(luò)的連通性，導(dǎo)致網(wǎng)絡(luò)抗毀性的降低。根據(jù)上面的兩條策略，本文給出了一種權(quán)值計(jì)算公式。對(duì)于任意點(diǎn)p來(lái)說(shuō)，i定義d為p的連接度，即與p距離小于半徑radius的鄰居的個(gè)數(shù)viid=工(dist(v,v)radiu

26、s)iven,vHvi定義D為與p距離小于半徑radius的鄰居的距離之和iiD二工dist(v,v)iven.,vHv,idist(v,v)radius之后定義每個(gè)節(jié)點(diǎn)p在半徑為radius的情況下權(quán)值為iw=axd+axDidiDiri=radius之后在5.2.1的搜索過(guò)程中，這些通過(guò)啟發(fā)式策略得到的權(quán)值就影響覆蓋區(qū)的選擇，從而得到滿足題目要求的較優(yōu)解。5.3結(jié)果分析如下圖5.1所示，該結(jié)果為使用基于權(quán)值的啟發(fā)式搜索策略形成的覆蓋區(qū)，其中紅色點(diǎn)表示附件中給出的各點(diǎn)，圓表示覆蓋區(qū)，連線表示各覆蓋區(qū)之間的連同情況。根據(jù)5.1中給出的各節(jié)點(diǎn)的極限覆蓋半徑R二69.336的結(jié)論，通過(guò)分析可以得到

27、，只要保證在每一個(gè)覆蓋區(qū)內(nèi)的任意兩點(diǎn)之間的距離小于R，并且在每?jī)蓚€(gè)相鄰的覆蓋區(qū)之間通信時(shí)兩節(jié)點(diǎn)之間的距離小于R的話，就可以滿足所有的節(jié)點(diǎn)都最少運(yùn)行1200小時(shí)的限制。經(jīng)過(guò)計(jì)算，所有的節(jié)點(diǎn)都滿足上述條件，采用這種覆蓋方案，所有的覆蓋區(qū)的半徑之和R=6951.34。sum5.4算法評(píng)價(jià)該搜索算法將啟發(fā)式策略用在了如何求解較優(yōu)的權(quán)值，并根據(jù)這些權(quán)值來(lái)選取恰當(dāng)?shù)母采w區(qū)，從而將該問(wèn)題從NP完全問(wèn)題轉(zhuǎn)換成了一個(gè)有限時(shí)間內(nèi)可以得到較優(yōu)結(jié)果的搜索問(wèn)題。從實(shí)際的結(jié)果來(lái)看，得到的方案滿足了對(duì)于電量的約束要求，并且算法的復(fù)雜度控制在O(n2)，有較高的實(shí)時(shí)性。缺點(diǎn)在于設(shè)置的啟發(fā)式策略并不能使得圓的分布盡可能的均勻，

28、造成了一些覆蓋區(qū)上的面積的浪費(fèi)，使得R的值偏大。sum參考文獻(xiàn)：A.AmisandR.Prakash,Load-balancingclustersinwirelessadhocnetworks,in:ProceedingsofASSET2000,Richardson,TX,March2000,pp.2532.D.J.BakerandA.Ephremides,Adistributedalgorithmfororganizingmobileradiotelecommunicationnetworks,in:Proceedingsofthe2ndInternationalConferenceonDistributedComputerSystems,April1981,pp.476-483.D.J.BakerandA.Ephremides,Thearchitecturalorganizationofamobileradionetworkviaadistributedalgorithm,IEEETransactionsonCommunicationsCOM-2911(1981)16941701.S.Basagni,I