傅霞玲陳江勇許力殷知越
(1.福建師范大學數(shù)學與計算機科學學院,福建福州350007;2.福建省德化陶瓷職業(yè)技術學院,福建泉州362500)
隨著通信技術、嵌入式技術、傳感器技術、無線技術的迅速發(fā)展和日趨成熟,具有通信能力、計算能力和感知能力的微型傳感器節(jié)點開始在世界范圍內(nèi)涌現(xiàn)。數(shù)目眾多的傳感器節(jié)點,以Ad Hoc方式構成無線傳感器網(wǎng)絡[1]。無線傳感器網(wǎng)絡的傳感器節(jié)點,隨機撒播或均勻有規(guī)則地分布在監(jiān)測區(qū)域,協(xié)同感知、采集和處理網(wǎng)絡覆蓋范圍內(nèi)的感知對象的信息,并把收集的信息,以多跳的方式發(fā)送給匯集節(jié)點(Sink節(jié)點)。但由于傳感器節(jié)點由電池供電,電池的容量一般不大,而且其特別的應用領域也決定傳感器在使用過程中,很難再充電或更換。因此,節(jié)能以延長網(wǎng)絡的生命周期是無線傳感器網(wǎng)絡設計的首要任務[2-3]。
l929年,匈牙利作家F.Karinthy最早提出了“小世界現(xiàn)象”的論斷[4]。1998年,Watts和Strogatz對規(guī)則網(wǎng)絡進行斷鏈重連得到了既具有小世界效應(L~lnN),又具有集團化特征的網(wǎng)絡,提出了著名的W-S小世界網(wǎng)絡(Small World Network SWN)這一概念,并建立了模型[5]。2004年,Helmy等學者通過在Ad Hoc網(wǎng)絡中引入邏輯鏈路形成具有小世界效應的無線網(wǎng)絡,驗證了小世界網(wǎng)絡同樣適用于具有空間屬性的無線網(wǎng)絡[6]。Helmy等人還研究了在磁盤網(wǎng)絡模型中以靜態(tài)匯聚節(jié)點為中心的無線傳感器網(wǎng)絡中設置有線鏈路產(chǎn)生捷徑的能量效率問題[7]。
但是,Helmy等人只是分析了有線的最優(yōu)長度、加入多少的有線后能量效率達到最高,以及最大可以達到的能量節(jié)省率,而沒有分析這些有線放置的最優(yōu)位置。因此,本文采用遺傳算法,研究在磁盤網(wǎng)絡模型中,傳感器節(jié)點均勻分布的單個Sink節(jié)點的靜態(tài)異構傳感器網(wǎng)絡中有線捷徑的優(yōu)化部署問題。通過有線捷徑的引入,最大幅度地降低平均路徑長度,達到提高網(wǎng)絡能量效率、延長網(wǎng)絡生命周期的目的。
本文采用磁盤網(wǎng)絡模型,傳感器節(jié)點以圖1所示的方式均勻分布于網(wǎng)絡拓撲中,節(jié)點之間信息傳輸采用曼哈頓距離(Manhattan Distance),每個節(jié)點到鄰居節(jié)點的距離均為一跳。網(wǎng)絡中只有一個Sink節(jié)點,所有的普通節(jié)點都把采集的信息發(fā)送到Sink節(jié)點。網(wǎng)絡為靜態(tài)及位置相關,即當網(wǎng)絡布設完成后,節(jié)點將保持位置不變。
在網(wǎng)絡中加入有線捷徑(wired shortcuts)或中繼節(jié)點,構造具有“小世界效應”的異構傳感器網(wǎng)絡。有線捷徑一端放置在遠離Sink節(jié)點的地方,另一端與Sink節(jié)點只有一跳的距離、與Sink節(jié)點可以直接通信?;蛘咭部梢圆捎镁哂凶銐虻哪芰抗⒋鎯吞幚砟芰Ω鼜姷闹欣^節(jié)點,這些中繼節(jié)點也是與Sink節(jié)點只有一跳的距離。兩種情況下,都只要確定遠離Sink節(jié)點的那一端的位置,分析的情況是一樣的,因此,在本文的論述中,捷徑與中繼節(jié)點為同義詞。
在圖1的磁盤網(wǎng)絡模型中,從拓撲的中心往外看,共有5個圓,表示一個具有5層的磁盤網(wǎng)絡。中心的第一個圓為第1層,從中心往外看,每個圓環(huán)分別為第2、3、4、5層。若Sink節(jié)點在拓撲中心上,則每一層上的節(jié)點,不管是在圓上,還是在該層的圓環(huán)內(nèi),到Sink節(jié)點的跳數(shù)是一樣的(采用貪婪路由策略)。
圖1 節(jié)點均勻分布的5層磁盤網(wǎng)絡模型(用θ=60o的斜坐標系表示)
本文采用貪婪路由策略,即某個節(jié)點N要發(fā)送數(shù)據(jù)到Sink節(jié)點時,它把數(shù)據(jù)包發(fā)送給距離Sink最近的鄰居節(jié)點,鄰居節(jié)點再重復這種過程,直到數(shù)據(jù)包發(fā)送到Sink節(jié)點。采用貪婪路由算法,數(shù)據(jù)包以最小的跳數(shù),就可以到達Sink節(jié)點。當網(wǎng)絡中加入有線捷徑時,顯然,對于有些節(jié)點,通過有線捷徑構成的有線鏈路,可以更快地到達Sink節(jié)點,因此,信息通過有線鏈路,傳輸?shù)絊ink節(jié)點;而對于另一些節(jié)點,直接通過無線鏈路,傳輸距離更近,就不必要通過有線鏈路了。數(shù)據(jù)包到底如何傳輸,需要進行比較判斷:
設:用NS(xs,ys)表示Sink節(jié)點坐標,Ni(i,j)表示普通節(jié)點坐標,Nn(xn,yn)為中繼節(jié)點坐標。
令:dWSN=|i-xs|+|j-ys|,dHSN=|i-xn|+|j-yn|+1
其中,dWSN表示普通節(jié)點通過無線鏈路到達Sink節(jié)點的距離(跳數(shù));dHSN表示通過有線鏈路到達Sink節(jié)點的距離(跳數(shù))。
若:dWSN<dHSN,則數(shù)據(jù)包通過無線鏈路到達匯集節(jié)點;否則,數(shù)據(jù)包通過有線鏈路到匯集節(jié)點。
傳感器網(wǎng)絡中節(jié)點的能量消耗主要在于數(shù)據(jù)包的傳送和接收過程,整個網(wǎng)絡的能耗與網(wǎng)絡中所有節(jié)點達到Sink節(jié)點的總跳數(shù)成正比。因此,我們可以在網(wǎng)絡的平均路徑長度和網(wǎng)絡的能耗之間建立對應關系。網(wǎng)絡的平均路徑長度最小,也即能耗最小。
用L(N)表示在m層磁盤網(wǎng)絡模型中,放置n個中繼節(jié)點后異構傳感器網(wǎng)絡的平均路徑長度。則L(N)為:
其中:
(i,j)為網(wǎng)絡中任一普通節(jié)點的坐標
(x1…n,y1…n)為中繼節(jié)點的坐標
(xs,ys)為sink節(jié)點的坐標
由于網(wǎng)絡中第一層為6個節(jié)點,其余各層的節(jié)點數(shù)構成公差為6的等差數(shù)列,因此,m層磁盤網(wǎng)絡的總節(jié)點數(shù)為:Sm=a1*m+m(m-1)d/2=6m+m(m-1)*6/2=3m2+3m
用L(O)表示未加線時無線傳感網(wǎng)絡的平均路徑長度,用ESR(Energy Saving Raito)表示加線后網(wǎng)絡的能量節(jié)省率,則:
由式(3)可知,在網(wǎng)絡規(guī)模及有線條數(shù)確定的情況下,L(O)為一固定值,因此,若要提高網(wǎng)絡的能量效率,獲得最大的能量節(jié)省率ESR,必須是有線得到優(yōu)化放置,使得L(N)為最小值??梢姡肊SR可以很方便地評價網(wǎng)絡的性能指標。
遺傳算法是一種模擬自然進化過程發(fā)展起來的高度并行、隨機、自適應的搜索算法。它從代表問題可能的解集的一個種群開始,而一個種群則由經(jīng)過基因編碼的一定數(shù)目的個體組成。初代種群產(chǎn)生之后,按照適者生存和優(yōu)勝劣汰的原理,逐代演化產(chǎn)生出越來越好的近似解。在每一代,根據(jù)問題域中個體的適應度大小選擇個體,并借助于自然遺傳學的遺傳算子進行組合交叉和變異,產(chǎn)生出代表新的解集的種群[8,9]。
本文采用輪盤賭選擇方案,即每個個體串按照它們的適應值進行選擇,選擇操作通過隨機方法來實現(xiàn)。變異也是產(chǎn)生新個體的一種方法,但一般變異概率都非常小,故不是產(chǎn)生新個體的主要方法。通過變異操作可以改變遺傳算法的局部搜索能力。
本文采用了一種編碼映射方法:把所有的節(jié)點按坐標從0開始進行編號。對于半徑為5的磁盤網(wǎng)絡,坐標為(5,0)的節(jié)點對應編號0,(5,1)對應編號1,依次類推。所以,半徑為m的磁盤網(wǎng)絡的所有節(jié)點對應一個整數(shù)集合Zn={0,1,2,3……,3m2+3m},這樣部署n個中繼節(jié)點的一個方案就唯一對應Zn的一個包含n個元素的子集,即每個染色體對應Zn的一個包含n個元素的子集。并且,我們在開始的時候隨機產(chǎn)生一定數(shù)目的Zn的n元子集作為初始種群。
對生存環(huán)境較高的物種將獲得更多的繁殖機會,因此適應度值和目標函數(shù)值成反比關系,目標函數(shù)值越小的個體,其適應度函數(shù)值越大,保證以較大的概率被選擇交叉產(chǎn)生下一代,適應度函數(shù)定義如(4)式所示。
公式中,考慮到取倒數(shù)后,值太小,所以用1/L(N)乘以一個系數(shù)(3m2+3m),并且再取平方值以拉大各數(shù)值間的差距。
實驗考慮Sink節(jié)點位于最外層第5層圓環(huán)上這種較特殊的情況,坐標為S(5,0)。用Visual C++6.0實現(xiàn)仿真,仿真實驗數(shù)據(jù)如下所示。
網(wǎng)絡層數(shù)M取值:5-20
中繼節(jié)點個數(shù)N取值:0,1,2…10,15,…50
種群大?。?0
交叉概率:0.80
變異概率:0.05
遺傳總代數(shù):1000
隨機數(shù)種子:88
算法重復執(zhí)行次數(shù):5
5.2.1 中繼節(jié)點的位置確定且不是唯一解
表1 兩種網(wǎng)絡規(guī)模下中繼節(jié)點優(yōu)化部署方案
由表1可知,中繼節(jié)點的坐標可以獲得,因此,采用本方案可以直接確定中繼節(jié)點的位置,對中繼節(jié)點可以直接進行部署,并且由于對稱性等原因,優(yōu)化部署方案不是唯一解。
5.2.2 平均路徑長度與中繼節(jié)點的關系
圖2 不同網(wǎng)絡規(guī)模下平均路徑長度與中繼節(jié)點的關系
在圖2中,網(wǎng)絡規(guī)模m增大時,若不加捷徑,平均路徑長度急劇增大,如圖所示,m=5,L(0)=7.7;m=20,L(0)=35.5。但當加入少量的有線后(1-4),平均路徑長度急劇下降,當捷徑增加到10時,各種網(wǎng)絡規(guī)模下的平均路徑長度相差不大,說明隨著捷徑的加入使得平均路徑長度大大減小,網(wǎng)絡的能耗大大降低。隨著有線數(shù)量的增加,平均路徑長度減小緩慢。這也從另一方面說明,并不是增加越多的有線越好。到底要加多少的有線,既可以較大幅度的降低能耗,又可以兼顧經(jīng)濟效益,這需要在兩者之間進行權衡。
5.2.3 能量節(jié)省率與中繼節(jié)點個數(shù)的關系
由圖3得,當中繼節(jié)點個數(shù)增加到10個時,網(wǎng)絡的能量節(jié)省率可以達到70-80%;繼續(xù)增加中繼節(jié)點個數(shù)到25,能量節(jié)省率達到77-87%。這與Helmy等人在論文[7]中的結論“加線5-24,路徑長度減少60-70%”相比,采用此方案可以獲得更高的能量節(jié)省率。
圖3 不同網(wǎng)絡規(guī)模下能量節(jié)省率與中繼節(jié)點個數(shù)之間的關系
本文研究磁盤網(wǎng)絡模型的節(jié)點均勻分布的異構傳感器網(wǎng)絡的捷徑優(yōu)化部署問題。理論分析與仿真實驗表明,采用遺傳算法可以得到優(yōu)化部署方案,通過最大限度減少網(wǎng)絡的平均路徑長度,獲得最大的能量節(jié)省率,從而達到延長網(wǎng)絡的生命周期的目的。并且有線的條數(shù)和位置確定后,線的長度也即確定,因此,便于網(wǎng)絡的布設與管理。
[1]Estrin D,Govindan R,Heidemann J,et a1.Next centurychal1enges:scalable coordinate in sensor network[A].In:Proc.of 5th ACM/IEEEInt’1Confon Mobile Computing and Networking[C].Washington,USA:ACM Press,1999.263~270.
[2]孫利民,李建中,陳渝,無線傳感器網(wǎng)絡[M].北京:清華大學出版社,2005.
[3]周賢偉,覃伯平,徐福華,無線傳感器網(wǎng)絡與安全[M].國防工業(yè)出版社,2007.
[4]Braun T.Hungarian priority in network theoty[M].Science,2004.
[5]WATTS D,STROGATZ S.Collective dynamics of‘small-world’networks[J].Nature,1998,393:440—442.
[6]HELMY A.Contact based architecture for resourcediscovery(CARD)in large scale MANets[J].IEEE/ACM IPDPS WMAN,2003,(4):219—227.
[7]HELMY A,CHITRADURGA R.Analysis of short cuts in wireless sensor networks[C].Proceedings of the The IEEE/ACS International Conference on Pervasive Services(ICPS'04),July 19-23,2004:167-176.
[8]王小平,曹立明,遺傳算法---理論、應用與軟件開發(fā)[M].西安交通大學出版社,2002.
[9]Zhao Chunhua,Yu Zhiqiang,Chen Peng.Optimal deployment of nodes based on genetic algorithm in heterogeneous sensor networks[C].2007 International Conference on Wireless Communications,Networking and Mobile Computing,WiCOM,2007:2743-2746.