無線傳感器網(wǎng)絡(luò)分簇算法研究

無線傳感器網(wǎng)絡(luò)分簇算法研究

目前，基于微電池傳感器技術(shù)的創(chuàng)新和低效率r的設(shè)計成功，我們可以開發(fā)出經(jīng)濟、低效率的無線傳感器。大量傳感器使用聯(lián)合通信來完成大規(guī)模的傳感器通信任務(wù)。然而，眾所周知，傳感器網(wǎng)絡(luò)的邊界是資源有限的，包括內(nèi)存、算術(shù)算法、通信帶寬和功率。分層結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)目前大多采用2層結(jié)構(gòu),利用簇的概念來對網(wǎng)絡(luò)進行分層.對無線傳感器網(wǎng)絡(luò)分簇,一個重要的作用是可以將網(wǎng)絡(luò)的感知的數(shù)據(jù)進行融合后再進行傳輸,減少由于傳輸產(chǎn)生的能量開銷,便于對簇內(nèi)節(jié)點統(tǒng)一管理,有利于對網(wǎng)絡(luò)進行擴展.在分簇的無線傳感器網(wǎng)絡(luò)中,存在簇頭和簇內(nèi)成員.簇頭作為簇的中心點負(fù)責(zé)簇結(jié)構(gòu)的穩(wěn)定和重組,通過簇頭組成骨干網(wǎng),可以實現(xiàn)跨簇通信.本文在通過引入Adhoc網(wǎng)絡(luò)中節(jié)點度的概念,結(jié)合節(jié)點剩余能量,最后建立簇頭選擇模型,實現(xiàn)無線傳感器網(wǎng)絡(luò)的分簇.本文組織結(jié)構(gòu)如下:第一節(jié)建立簇頭選擇模型;第二節(jié)理論分析和性能仿真;第三節(jié)總結(jié).1規(guī)模過大的情況下多時要注意聚合群數(shù)的約束簇頭選擇模型根據(jù)每個節(jié)點的權(quán)值來選擇簇頭,權(quán)值較小的節(jié)點優(yōu)先成為簇頭.節(jié)點的權(quán)值綜合考慮了節(jié)點度和節(jié)點剩余能量.為了平衡整個網(wǎng)絡(luò)的能量消耗,減少簇頭的持續(xù)能量消耗,還為原有簇頭引入了一定的增量增大其權(quán)值,使其再次被選舉為簇頭的可能性減小.節(jié)點權(quán)值的計算公式為:W(n)={a×|d(n)-m|+b×lg[(Τ(n)+0.01)(Τthr+0.01)〗+c×Δ}×(E0-ErE0)(1)W(n)={a×|d(n)?m|+b×lg[(T(n)+0.01)(Tthr+0.01)〗+c×Δ}×(E0?ErE0)(1)式中:d(n)表示節(jié)點n的節(jié)點度,節(jié)點度定義為一個節(jié)點的相鄰節(jié)點數(shù),擁有最高節(jié)點度的節(jié)點被選擇為簇頭,可以將網(wǎng)絡(luò)劃分為較小的簇,從而減少數(shù)據(jù)分組的延遲;m表示每個簇內(nèi)理想的簇成員數(shù).一方面,由于能力的限制,簇頭無法負(fù)擔(dān)過多的簇成員,即使這些簇成員都在它的傳輸范圍內(nèi).簇的尺寸太大會使簇頭的開銷過大,并降低信道的空間重用率;另一方面,簇的尺寸太小又會在網(wǎng)絡(luò)中形成過多的簇從而使建立和維護有效的簇結(jié)構(gòu)變得很困難,并增加分組的延遲.因此應(yīng)選擇簇的尺寸是否合理,是一個分簇算法必須考慮到的因素.在其他文獻中還有關(guān)于簇規(guī)模過大過小的情況下如何對簇進行約束.簇規(guī)模的大小可以用簇頭的節(jié)點數(shù)來衡量,即簇頭數(shù)越多,簇規(guī)模越小;簇頭數(shù)越少,簇規(guī)模越大.理想的簇頭數(shù)情況如下:設(shè)整個網(wǎng)絡(luò)可以被分為h個簇,為保證全網(wǎng)中流量平衡,將骨干網(wǎng)流量帶寬B2平均分配給每個簇,使得B2=B1×h,所有子網(wǎng)共享骨干網(wǎng)中的流量,以適應(yīng)每個子網(wǎng)能同時進行通信的情況.在無線網(wǎng)絡(luò)中,對于隨機分布的n個相同的節(jié)點,每個節(jié)點在一個固定的范圍內(nèi)其傳輸能力為Wbit/s,則每個節(jié)點到隨機選取的目的節(jié)點的傳輸流量λ(n)=Θ(W√nlgn)bit/sλ(n)=Θ(Wnlgn√)bit/s.進一步指出如果節(jié)點所處區(qū)域為單位圓,傳輸模式、傳輸范圍最優(yōu)的情況下傳輸流量可以用下式表示:λ=Θ(W√n)(2)λ=Θ(Wn√)(2)根據(jù)式(2),簇內(nèi)節(jié)點的傳輸流量總和λc由下式表示:λc=Θ[B1√n/hλc=Θ[B1n/h√bit/s(3)簇頭節(jié)點的流量λb由下式表示:λb=Θ[B2√hλb=Θ[B2h√bit/s(4)理想的情況下有λc=λbhλc=λbh,則根據(jù)式(2)和式(3)得到[B1√n/h=1h[B2h〗(5)由此得到分簇數(shù)h:h=√B2B1√n(6)因此,理想情況下簇內(nèi)的簇成員數(shù):m=nh=n√B2B1√n=√B1B2n3/4(7)T(n)表示節(jié)點n擔(dān)當(dāng)簇頭的時間.簇頭會比簇成員消耗更多的能量,節(jié)點擔(dān)當(dāng)簇頭的時間越長,消耗的電池能量也就越多.為了避免已經(jīng)消耗了過多能量的節(jié)點再次被選為簇頭,從而導(dǎo)致其過早地耗盡能量,規(guī)定一個時間門限值Tthr,當(dāng)某節(jié)點擔(dān)當(dāng)簇頭的時間超過了Tthr時,該節(jié)點被選為簇頭的可能性就迅速下降,這里用對數(shù)函數(shù)來實現(xiàn).其中加0.01是為了避免對數(shù)函數(shù)的自變量為0;Δ表示一個增量.如果在上一次選舉時,節(jié)點n被選為簇頭,則在本次選舉時,為其權(quán)值附加這個增量.若在上次選舉中節(jié)點n為簇成員,則權(quán)值的計算公式中不包含這個增量.a,b,c表示權(quán)重系數(shù),其值都為正數(shù),且滿足a+b+c=1.根據(jù)不同系統(tǒng)的特殊需要,可以為這幾個變量選擇不同的值,從而改變不同因素在簇頭選取中的作用大小,使該分簇算法適用于不同類型的網(wǎng)絡(luò).假設(shè)E0為節(jié)點的初始能量,Er為節(jié)點的剩余能量.從式(1)中,我們可以看出當(dāng)節(jié)點的能量耗盡時,節(jié)點的剩余能量接近于0,即ErE0≈0,這將導(dǎo)致節(jié)點被選為簇頭的概率幾乎為0.權(quán)值小于所有鄰節(jié)點的節(jié)點被選為簇頭,當(dāng)權(quán)值相等時,選擇ID較小的節(jié)點成為簇頭.簇頭的鄰節(jié)點成為其簇成員,并不再參與簇頭的選舉過程.若一個節(jié)點的所有鄰節(jié)點中比它權(quán)值小的節(jié)點都已經(jīng)成為了其他簇頭的簇成員,則該節(jié)點也成為簇頭;因此擁有權(quán)值W(n)小的節(jié)點被選為簇頭,從而可以構(gòu)成簇頭集,以表示{Ci},i=1,2,…,h.{Ci}中的每一個點代表一個簇頭.簇生成的過程是使用簇頭集{Ci}中的每一個點為簇頭,且簇頭節(jié)點Ci作為根節(jié)點廣播“Cluster-Init”信息,其信息采用廣播方式傳播.算法通過建立簇成員數(shù)據(jù)庫,從而生成簇.以簇的生成為例,描述如下:(1)參數(shù)和變量的初始化intv,u,w,n;BooleanVisited[];//節(jié)點被訪問標(biāo)志數(shù)組intClusterSet[Q];//簇選擇模型for(u=0;u<Gvexnum;++u)Visited[u]=FALSE;//訪問標(biāo)志初始化;InitClusterSet(ClusterSet[Q]);//簇選擇模型數(shù)據(jù)庫初始化;(2)i簇生成(圖1)以上為簇生成算法對于簇中的任意節(jié)點vij,i為簇標(biāo),其取值范圍是從1到h,j為第i簇中節(jié)點標(biāo)號,取值范圍是從1到x,并且每個簇中節(jié)點的數(shù)目不同.最終有:h∑i=1x∑j=1vij=n(8)2性能分析2.1層次樹生成的復(fù)雜度信息復(fù)雜度是為了生成簇,在節(jié)點之間傳輸和存儲的信息量.該分簇算法的信息復(fù)雜度為O(n5/4).證明如下:m=nh=√B1B2n3/4(9)由于算法在本質(zhì)上是發(fā)現(xiàn)和生成L層的D-維層次樹(樹深L<∞),所以最終生成的是深度為L且與隨機標(biāo)記相關(guān)的D-維平衡樹的鏈路集合.根據(jù)文獻的計算結(jié)果,為生成層次樹,每個節(jié)點產(chǎn)生的數(shù)據(jù)量與L×n1/L相關(guān),用ω′=λL×n1/L表示,其中n為網(wǎng)絡(luò)節(jié)點數(shù),λ為系數(shù).一個簇中交換的信息量為簇平均節(jié)點數(shù)m與每個節(jié)點數(shù)據(jù)量ω′的乘積.由下式表示:m×ω′=√B1B2n3/4×λL×n1/L×ρ(10)式(10)中ρ為常量數(shù)據(jù)單位,在本文中L=2,所以可得到:2ρλ√B1B2n5/4(11)由此,我們得出其復(fù)雜度為O(n5/4).證畢2.2節(jié)點傳輸范圍不同下面我們利用仿真工具NS2來對該分簇算法進行分析.對于無線傳感器網(wǎng)絡(luò)而言,目前并沒有統(tǒng)一的評測標(biāo)準(zhǔn).為了更好的分析出該分簇算法的性能,我們選擇使用以下參數(shù):①簇數(shù)和簇中平均節(jié)點數(shù).②簇頭轉(zhuǎn)移次數(shù):簇頭轉(zhuǎn)移次數(shù)可以衡量簇頭更換頻率的快慢.仿真中所用的網(wǎng)絡(luò)參數(shù)如表1所示:圖1給出了網(wǎng)絡(luò)中節(jié)點數(shù)分別為50,100和150這三種情況下的仿真場景圖.其中節(jié)點是隨機撒播在固定區(qū)域中的.圖2給出了兩種不同簇算法平均簇數(shù)隨節(jié)點傳輸范圍的變化情況.假設(shè)B2B1=10,在網(wǎng)絡(luò)節(jié)點數(shù)n為50的時候,由式(6)得出理想的簇數(shù)為8,從圖2中可以看出,相應(yīng)的節(jié)點傳輸距離為35m.同理,網(wǎng)絡(luò)節(jié)點數(shù)n為100的時候,理想的簇數(shù)為10;網(wǎng)絡(luò)節(jié)點數(shù)n為150的時候,理想的簇數(shù)為11.單個簇內(nèi)所包含的節(jié)點數(shù)較多,可以產(chǎn)生較少的簇,從而降低分組投遞的延遲,還可以簡化簇結(jié)構(gòu)的管理.但是較少的簇數(shù)也會降低信道的空間重用率,同時單個簇內(nèi)的節(jié)點數(shù)過多也會使簇頭負(fù)擔(dān)加重.根據(jù)以上模擬計算的結(jié)果顯示,網(wǎng)絡(luò)參數(shù)節(jié)點數(shù)n、無線傳輸帶寬B2B1和節(jié)點傳輸范圍之間的關(guān)系決定了網(wǎng)絡(luò)性能,需要在它們之間進行平衡,以得到最佳的網(wǎng)絡(luò)的性能.當(dāng)節(jié)點的傳輸范圍較小時,簇成員與簇頭的距離很近,不容易離開原簇,因此單位時間內(nèi)簇頭更新次數(shù)較低.從圖3中可以看出,隨著節(jié)點傳輸范圍的增大,單位時間內(nèi)簇頭更新次數(shù)逐漸增加達到峰值.傳輸范圍的進一步增大反而使單位時間內(nèi)的簇頭更新次數(shù)降低,這是因為簇頭的傳輸范圍較大,節(jié)點不容易移出原來簇頭的覆蓋