一種adhoc網(wǎng)絡(luò)分簇方法的研究

一種adhoc網(wǎng)絡(luò)分簇方法的研究

1基于連通支配集的adhoc網(wǎng)絡(luò)分簇算法無線傳感器網(wǎng)絡(luò)是一組無線節(jié)點組成的移動網(wǎng)絡(luò)。在sdhoc網(wǎng)絡(luò)中，一個重要的角色是將網(wǎng)絡(luò)重建限制到特定區(qū)域，這有助于促進(jìn)網(wǎng)絡(luò)擴展。在共享網(wǎng)絡(luò)的adhoc網(wǎng)絡(luò)中，有簇頭和簇尾的成員。簇頭作為簇的中心，負(fù)責(zé)簇結(jié)構(gòu)的穩(wěn)定和重組，通過簇頭形成骨干網(wǎng)，可以傳輸?shù)郊?。近幾?國外的研究工作者對adhoc網(wǎng)絡(luò)提出比較多的分簇算法.文獻(xiàn)采用探測法對網(wǎng)絡(luò)分簇,每個節(jié)點計算它自己在網(wǎng)絡(luò)中的連通度,在一群相鄰節(jié)點之間,選擇連通度高的節(jié)點作為簇頭.這種算法具有快的收斂性.但每個節(jié)點要維持與其它節(jié)點的連通度信息,所以在網(wǎng)絡(luò)拓?fù)渥兓瘯r,更新數(shù)據(jù)信息量大,網(wǎng)絡(luò)資源開銷也大.文獻(xiàn)是依據(jù)節(jié)點的權(quán)重因子進(jìn)行分簇,節(jié)點的權(quán)重因子被定義為在給定時間t內(nèi),節(jié)點與相鄰節(jié)點之間的一個有效路徑概率a,表示為(a,t).節(jié)點根據(jù)鄰節(jié)點的權(quán)重值是否滿足需要來決定是否加入相關(guān)的簇,權(quán)重的閾值是可以調(diào)整的.但當(dāng)節(jié)點的運動自由度變大時,有效的路徑預(yù)測概率變低,降低算法的可靠度.文獻(xiàn)利用節(jié)點的地理位置信息來進(jìn)行分簇,根據(jù)節(jié)點的物理坐標(biāo)計算出節(jié)點之間的距離,以距離值作為分簇的依據(jù).算法不需要節(jié)點保持網(wǎng)絡(luò)的拓?fù)錁?gòu)造信息,所以網(wǎng)絡(luò)開銷比較小,并且能夠快速適應(yīng)網(wǎng)絡(luò)的拓?fù)渥兓?但采用GPS來獲取節(jié)點的位置信息,應(yīng)用時具有局限性.文獻(xiàn)提出利用連通支配集的概念進(jìn)行分簇,但尋求最小支配集是NP-完全問題,所以文中提出采用分布式的算法來求得近似解,算法的時間復(fù)雜度和信息復(fù)雜度都比較大,并且對鄰接跳數(shù)有限制.本文在移動節(jié)點之間引進(jìn)相關(guān)性的概念,通過相關(guān)性來計算節(jié)點的相關(guān)度值,再采用D-tree算法實現(xiàn)adhoc網(wǎng)絡(luò)的分簇.本文第2節(jié)介紹分簇方法;第3節(jié)是算法的性能評估;第4節(jié)是模擬計算結(jié)果;最后一節(jié)是相關(guān)的結(jié)論和進(jìn)一步的工作.2集群生產(chǎn)2.1鄰節(jié)點集合vvi我們將由n個自由運動節(jié)點組成的平面adhoc網(wǎng)絡(luò)抽象為一個連通圖G=(V,E),|V|表示網(wǎng)絡(luò)節(jié)點集合,|E|表示節(jié)點之間的雙向鏈路集合.網(wǎng)絡(luò)節(jié)點分布具有隨機的特征,同一小區(qū)域中節(jié)點由于距離近,具有物理位置的相關(guān)性.利用節(jié)點所處的物理位置來構(gòu)建子網(wǎng),能提高網(wǎng)絡(luò)的穩(wěn)定度.定義1.在G=(V,E)中,對于節(jié)點u,v∈G(V),D(v,u)或D(u,v)表示節(jié)點u,v之間的無線傳輸鏈路.設(shè)r是網(wǎng)絡(luò)中節(jié)點的無線傳輸距離,當(dāng)節(jié)點u,v是鄰居時,|D(v,u)|≤1成立;否則|D(u,v)|>r.定義2.對于給定節(jié)點u,v∈G(V),符號R(v,u)表示節(jié)點u,v之間的傳輸對應(yīng)關(guān)系,稱為節(jié)點u,v之間的相關(guān)度.相關(guān)度R(v,u)的取值為正整數(shù).當(dāng)節(jié)點u,v滿足條件|D(v,u)|≤1時,表示u,v為鄰節(jié)點,其相關(guān)度值|R(v,u)|=1.當(dāng)節(jié)點u,v滿足條件|D(u,v)|>r時,u,v之間需要通過d-1個中間節(jié)點的轉(zhuǎn)發(fā)才可以相互到達(dá),其相關(guān)度值|R(v,u)|=d.圖G=(V,E)中的每一個節(jié)點vi∈G(V),節(jié)點vi(i=1,2,…,n)的鄰節(jié)點集合V′vi可表示為V′vi={vj|R(vj,vi)≥d,vj≠vi,j≤|V|,i=1,2,…,n},d=1時,V′vi表示是節(jié)點vi所有一跳鄰節(jié)點的集合;當(dāng)d>1時,V′vi表示為節(jié)點vi的所有d-1跳鄰節(jié)點集合.節(jié)點vi在不同的相關(guān)度值d下,其V′vi值是不同的.定義3.節(jié)點vi的鄰節(jié)點集合V′vi可以用一個鄰接矩陣Ai=(aij)1×j來表示,這是一個1×j矩陣,它的矩陣元素aij可以由式(1)表示:aij={|R(vi,vj)|,vi≠vj0,vi=vj(1)aij={|R(vi,vj)|,0,vi≠vjvi=vj(1)任意節(jié)點vi鄰接矩陣Ai的值N(vi),可以由下式計算得到,其值的物理意義表示節(jié)點vi與它鄰節(jié)點vj相關(guān)度值的和:Ν(vi)=m∑j=1aij(2)N(vi)=∑j=1maij(2)式(2)中變量i的取值范圍是i=1,2…,n.變量j是節(jié)點vi的鄰節(jié)點數(shù),其取值范圍是j=1,2,…,m,不同的節(jié)點在取不同的相關(guān)度值時,其m取值是不同的,表示節(jié)點vi具有不同的鄰節(jié)點數(shù).定義4.符號deg(vi)=|N(vi)|表示節(jié)點vi的度,|N(vi)|是大于零的正整數(shù).節(jié)點vi與鄰節(jié)點vj之間可以取不同的相關(guān)度值d,當(dāng)選取一個確定的相關(guān)度值d,根據(jù)上述的計算方法,可以得到圖G=(V,E)中節(jié)點vi的度,節(jié)點vi的度值越高表示它周圍的鄰節(jié)點數(shù)越多,所以度值最高的節(jié)點具有作為簇頭的優(yōu)先條件.2.2子網(wǎng)流量帶及實施方法本文中所考慮的是由子網(wǎng)和骨干網(wǎng)組成的兩層網(wǎng)絡(luò)模型,如圖1所示.若干個節(jié)點組成子網(wǎng),每個子網(wǎng)中的節(jié)點數(shù)不同.子網(wǎng)中的節(jié)點通過簇頭進(jìn)入骨干網(wǎng),網(wǎng)關(guān)是一個軟件實體,運行在簇頭節(jié)點上.在圖1所示的分層網(wǎng)絡(luò)結(jié)構(gòu)中,子網(wǎng)內(nèi)部的流量B1和子網(wǎng)間流量B2(骨干鏈路上的流量)是不同的,為了保持網(wǎng)絡(luò)工作穩(wěn)定,希望各子網(wǎng)間的網(wǎng)際流量盡量均衡.網(wǎng)間流量均衡意味可以降低骨干鏈路的設(shè)計容量,減少網(wǎng)絡(luò)發(fā)生擁塞的可能.設(shè)整個網(wǎng)絡(luò)可以被分為h個子網(wǎng)即h簇,為保證全網(wǎng)中流量平衡,將骨干網(wǎng)流量帶寬B2平均分配給每個子網(wǎng),使得B2=hB1,所有子網(wǎng)共享骨干網(wǎng)中的流量,以適應(yīng)每個子網(wǎng)能同時通信的情況.根據(jù)文獻(xiàn),具有n個移動節(jié)點的adhoc網(wǎng)絡(luò)中,每個節(jié)點的傳輸流量由下式表示S=Θ(B√n)(bit/s)(3)S=Θ(Bn√)(bit/s)(3)式(3)中B表示是通道帶寬,Θ是系數(shù)因子.根據(jù)式(3),子網(wǎng)內(nèi)節(jié)點的傳輸流量總和Ssubnet由下式表示Ssubnet=Θ(B1√n/h)(bit/s)(4)Ssubnet=Θ(B1n/h√)(bit/s)(4)簇頭節(jié)點的流量Sbackbone由下式表示Sbackbone=Θ(B2√h)(bit/s)(5)Sbackbone=Θ(B2h√)(bit/s)(5)理想的情況下有Ssubnet=SbackbonehSsubnet=Sbackboneh,則根據(jù)式(3)和式(4)得到(B1√n/h)=1h(B2√h)(6)(B1n/h√)=1h(B2h√)(6)由此得到分簇數(shù)hh=√B2B1√n(7)h=B2B1n√?????√(7)從圖1所示的網(wǎng)絡(luò)結(jié)構(gòu)中可以看出,簇頭的決定是至關(guān)重要的.由2.1節(jié)的結(jié)果可知,度值|deg(vi)|高的點周圍有比較多的鄰節(jié)點,具有作為簇頭的優(yōu)先條件.所以我們根據(jù)式(7)中所求的簇數(shù)值h,選擇h個度值高的點作為簇頭節(jié)點,以{Dh}表示.{Dh}中的每一個點代表一個簇頭(clusterhead),以每個簇頭節(jié)點為中心組成簇,這樣n個節(jié)點平面adhoc網(wǎng)絡(luò)可以分為h簇.2.3打造d-to-u-dh-ci0光團見表3定義5.符號Cxy為分簇前的節(jié)點標(biāo)記;符號Cij(i=1,2,…,h)標(biāo)記為分簇后第i簇中的節(jié)點,其中Ci0(i=1,2,…,h)為第i簇中的簇頭節(jié)點;符號{Cij}是一個簇中節(jié)點的集合標(biāo)記.規(guī)則1.i簇組成的必要條件是1≤|R(Ci0,Cij)|≤4.規(guī)則2.min|R(Ci0,Cxy)|(i=1,2,…)值.規(guī)則1表明,簇頭與簇內(nèi)節(jié)點之間的傳輸距離一般不超過4跳.規(guī)則2表示,某個節(jié)點Cxy在它所在區(qū)域內(nèi)有超過兩個以上簇頭時,選擇距它傳輸跳數(shù)最小的簇頭.簇生成的過程是使用上一節(jié)所選定的簇頭集{Dh}中的每一個點為簇頭Ci0(i=1,2,…,h),且簇頭節(jié)點Ci0作為根節(jié)點廣播“Cluter-Init”信息開始,其信息采用廣播方式傳播,采用D-tree算法來建立|R(Ci0,Cij)|的相關(guān)性數(shù)據(jù)庫,從而生成簇.以i簇的生成為例,描述算法如下.以簇頭Ci0為中心,使用D-tree搜索來生成i簇集合.由于算法的窮盡性,網(wǎng)絡(luò)中的每一個節(jié)點都與相應(yīng)簇頭節(jié)點建立唯一的相關(guān)值|R(Ci0,Cij)|≤d,生成{Cij}集,其中d為相關(guān)度閾值.{Cij}集中的每一個節(jié)點通過一次加入操作完成登記.不同簇中的節(jié)點數(shù)與算法無關(guān),與節(jié)點的物理位置相關(guān).對于簇中的任意節(jié)點Cij,i為簇標(biāo),其取值范圍是從1到h,j為第i簇中節(jié)點標(biāo)號,取值范圍是從1到x,并且每個簇中節(jié)點的數(shù)目不同.最終有h∑ix∑jvij=n(8)∑ih∑jxvij=n(8)3性能評價3.1算法的信息復(fù)雜度定義6.信息復(fù)雜度是為了生成簇,在節(jié)點之間所傳輸和存儲的信息量.定理1.D-tree算法的信息復(fù)雜度為O(n5/4).證明.根據(jù)2.2節(jié)式(7)中得到的簇頭數(shù)h=√B2B1√nh=B2B1n√?????√,一個簇的平均節(jié)點數(shù)ˉΝ=nh=√B1B2n3/4(9)Nˉˉˉ=nh=B1B2???√n3/4(9)由于算法在本質(zhì)上是發(fā)現(xiàn)和生成L層的D-維層次樹(樹深L<∞),所以最終生成的是深度為L且與隨機標(biāo)記相關(guān)的D-維平衡樹的鏈路集合.根據(jù)文獻(xiàn)的計算結(jié)果,為生成層次樹,每個節(jié)點產(chǎn)生的數(shù)據(jù)量與L×n1/L相關(guān),用ω′=λL×n1/L表示,其中n為網(wǎng)絡(luò)節(jié)點數(shù),λ為系數(shù).一個簇中交換的信息量為ue8480-GKvAp,則ue8480-GKvAp是簇平均節(jié)點數(shù)ˉΝNˉˉˉ與每個節(jié)點數(shù)據(jù)量ω′的乘積.ue8480-GKvAp由下式表示:■0-GΚvAp=ˉΝ×ω′=√B1B2n3/4×λL×n1/L×ρ(10)式(10)中ρ為常量數(shù)據(jù)單位,在本文中L=2,所以可得到■0-GΚvAp=2ρλ√B1B2n5/4(11)算法的信息復(fù)雜度為O(n5/4).證畢.3.2節(jié)點數(shù)量的變化設(shè)網(wǎng)絡(luò)節(jié)點作隨機運動,從原先的簇移動進(jìn)入一個新的簇,它需要交換信息達(dá)到新的穩(wěn)定,也是節(jié)點移動所帶來的信息開銷.假設(shè)在i簇中節(jié)點Cij到簇頭Ci0的平均跳數(shù)為k,每個節(jié)點的無線傳輸距離為r,所以簇的平均覆蓋范圍是以簇頭為中心,以R=k×r作為半徑的區(qū)域S=πk2r2.設(shè)簇中節(jié)點的平均密度是σ,則σ=ˉΝS=√B1B2n3/4πk2r2(12)節(jié)點作隨機運動,設(shè)平均速度是ˉv,在單位時間Δt內(nèi)節(jié)點的運動距離是l=ˉv×Δt,在單位時間內(nèi),分布在環(huán)形區(qū)域S′中的節(jié)點可能移出本簇,用W′表示這些節(jié)點的數(shù)量,如圖2所示.S′=πk2r2-π(kr-l)2=2πkrˉvΔt-π(ˉvΔt)2(13)W′=S′×σ=√B1B2n3/4×2krˉvΔt-(ˉvΔt)2k2r2(14)S′區(qū)域中的節(jié)點作隨機運動,所以一個節(jié)點移出本簇的概率是:ρ=1l∫l12cos-1(x/l)2πdx?ρ=1π∫10cos-1(y)dy=1π(15)所以移出本簇的節(jié)點數(shù)是W=w′×ρ=√B1B2n3/4×2krˉvΔt-(ˉvΔt)2πk2r2(16)根據(jù)3.1節(jié)中對信息復(fù)雜度的分析,每個節(jié)點產(chǎn)生的數(shù)據(jù)量與L×n1/L相關(guān),這也是每個節(jié)點在穩(wěn)態(tài)時保持的數(shù)據(jù)量.所以移出節(jié)點所引起的數(shù)據(jù)更新量總數(shù)為UU=W×ω′=2λ√B1B2n5/4(2ˉvΔtπkr-(ˉvΔt)2πk2r2)(17)在動態(tài)平衡狀態(tài)下,可以認(rèn)為移入和移出的節(jié)點數(shù)相同,所以一個簇中,移動節(jié)點所引起的數(shù)據(jù)更新量為2U數(shù)據(jù)單位.4網(wǎng)絡(luò)參數(shù)對算法的影響我們采用GloMoSim(GlobalMobilesystemSimulator),系統(tǒng)作為網(wǎng)絡(luò)環(huán)境來模擬算法的性能指標(biāo)和各參數(shù)之間的關(guān)系,試驗所用的網(wǎng)絡(luò)參數(shù)如表1所示.通過模擬計算分析,我們得到如下結(jié)果.4.1網(wǎng)絡(luò)節(jié)點數(shù)對網(wǎng)絡(luò)分簇的影響根據(jù)式(7)所建立簇的數(shù)目與簇中平均節(jié)點數(shù)之間的對應(yīng)關(guān)系如圖3所示.從圖中可以看出,無線傳輸信道帶寬比的不同,生成的簇的數(shù)目也不同.當(dāng)B2/B1=8,網(wǎng)絡(luò)節(jié)點數(shù)為40時,分簇數(shù)為7個,每個簇中的平均節(jié)點數(shù)約為6個.當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)增加到200個點時,分簇數(shù)為10個,每個簇中的平均節(jié)點數(shù)為20個.它們之間的關(guān)系不是一種簡單的線性關(guān)系.4.2節(jié)點運動速度的數(shù)值模擬節(jié)點在單位時間內(nèi)從一個簇中移動的特性如圖4所示.本模擬中將自組網(wǎng)分為8個簇,每個簇中的平均節(jié)點數(shù)最大為25個,模擬時間T=120s,節(jié)點的無線傳輸范圍r=100m.從圖中可以看出,移動的節(jié)點數(shù)目與節(jié)點運動速度相關(guān).當(dāng)節(jié)點的平均運動速度為10m/s時,在120s的時間內(nèi),一個簇中的平均移動節(jié)點數(shù)最大是9個,占簇節(jié)點數(shù)的45%.圖中列出的是節(jié)點離開的情況,也有進(jìn)入簇的移動節(jié)點,所以進(jìn)出簇的運動節(jié)點應(yīng)該是圖示節(jié)點數(shù)的兩倍.4.3節(jié)點系統(tǒng)更新量由于節(jié)點移動,需要重新加入新的簇,需要進(jìn)行節(jié)點中的信息更新.本模擬中將自組網(wǎng)分為8個簇,每個簇中的平均節(jié)點最大數(shù)為25個,模擬時間T=120s,節(jié)點的無線傳輸范圍r=100m.在單位時間內(nèi),移動節(jié)點引起的數(shù)據(jù)更新量如圖5所示.4.4節(jié)點的網(wǎng)絡(luò)更新根據(jù)以上模擬計算的結(jié)果顯示,網(wǎng)絡(luò)參數(shù)節(jié)點數(shù)n、無線傳輸帶寬B1/B2和節(jié)點移動速度v之間的關(guān)系決定網(wǎng)絡(luò)性能,需要在它們之間進(jìn)行平衡,以得到最佳的網(wǎng)絡(luò)的性能.對于具有200個運動節(jié)點的