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

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

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

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

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

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

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

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

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

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

10、數(shù)。則:D(b)二工D(b,I)這種計算方法會產生組合爆炸的問題，因此我們采用蒙特卡羅模擬方法近似的求解D(b)，設蒙特卡羅模擬中，某一次模擬隨機產生的點分布為I，模擬迭代次數(shù)為s，則iD(b)=工D(b,I.)is對1.1和1.3中求得的覆蓋方案進行蒙特卡羅模擬，得到結果如表2、3所示圖7一個去掉15%點的例子k二5%，圖2分配方案的模擬結果: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分配方案的模擬結果: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ū)的平面覆蓋問題和信道分配方案2.1最優(yōu)化模型將本問題歸結為一個最優(yōu)化問題，則：目標：所有圓的半徑之和最小約束1：相鄰兩個圓的公共面積不小于大圓面積的5%約束2：地面被圓完全覆蓋約束3：節(jié)點不能存在于湖中設湖區(qū)所覆蓋的區(qū)域為Q,d為處于每個圓的圓心或相鄰圓公共部分中心的節(jié)點(也i可稱終端或用戶)，m為節(jié)點個數(shù)，p為平面上任一點，則本問題的最優(yōu)化模型的數(shù)學表述如下：minr1inii=1kxmaxS(c),S(c

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、造成了一些覆蓋區(qū)上的面積的浪費，使得R的值偏大。sum參考文獻：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