路成杰， 蔣海峰

(南京理工大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210094)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)由許多無線傳感器節(jié)點(diǎn)組成，應(yīng)用于大面積的監(jiān)控應(yīng)用中,這些應(yīng)用主要包括數(shù)據(jù)收集和事件驅(qū)動(dòng)兩類。傳感器節(jié)點(diǎn)多為一次性節(jié)點(diǎn)，電源更換困難，所以，能量問題成為了制約無線傳感器網(wǎng)絡(luò)發(fā)展的瓶頸。為此，提出了許多能量有效利用技術(shù)來延長(zhǎng)了網(wǎng)絡(luò)的壽命[1]。

因?yàn)榫W(wǎng)絡(luò)中的能量主要消耗在無線通信過程中，所以，選擇有效的路由協(xié)議能夠很好地降低通信過程中的能耗。路由協(xié)議通過選擇最優(yōu)信息傳遞路徑來降低能耗。在已提出的各類路由協(xié)議中，基于簇的路由協(xié)議對(duì)降低通信能耗，延長(zhǎng)網(wǎng)絡(luò)壽命具有良好的效果。

在已有的基于簇的路由協(xié)議中，簇頭需要承擔(dān)收集簇內(nèi)數(shù)據(jù)、與基站通信的任務(wù)。許多基于能量有效利用的路由協(xié)議均采用與簇相關(guān)的網(wǎng)絡(luò)構(gòu)架[2]。簇頭的選擇與成簇對(duì)于均衡整個(gè)網(wǎng)絡(luò)能量，延長(zhǎng)網(wǎng)絡(luò)壽命，降低網(wǎng)內(nèi)延遲與增強(qiáng)網(wǎng)絡(luò)可擴(kuò)展性起到了重要的作用。而成簇算法一般需要解決以下3個(gè)問題：應(yīng)用需求、網(wǎng)絡(luò)模型與其參數(shù)設(shè)置、選取適于評(píng)價(jià)算法的參數(shù)。

常見的分簇路由算法可以分為以下幾類：階層式成簇算法主要包括LEACH[3]協(xié)議，采用了分布式算法，這類算法很好地處理了簇內(nèi)信息收集，但缺點(diǎn)在于其網(wǎng)絡(luò)結(jié)構(gòu)不利于簇間的數(shù)據(jù)傳遞。分割式成簇算法也如典型的k-means method[4]以網(wǎng)絡(luò)參數(shù)與應(yīng)用需求為參照，以分割法求重心以獲得簇頭位置。

本文是在原有LEACH協(xié)議上提出的改進(jìn)算法SDD-LEACH(sensors density depended-LEACH)。與文獻(xiàn)[4]不同的是，該種算法不需要預(yù)知網(wǎng)內(nèi)狀況與運(yùn)用需求，具有較好的可移植性。在整個(gè)協(xié)議的運(yùn)行過程中，著重考慮候選簇頭區(qū)域的選擇降低簇間通信的能耗，平衡全網(wǎng)能耗。

1 模型建立

1.1 能量模型

本文選用了文獻(xiàn)[3]的無線通信能量消耗模型。在這里，一個(gè)無線傳感器節(jié)點(diǎn)發(fā)送lbit的數(shù)據(jù)到一個(gè)到其距離為d的傳感器節(jié)點(diǎn)的能耗為

(1)

1.2 網(wǎng)絡(luò)模型

假設(shè)在一面積為S的特定區(qū)域內(nèi)，一共分布了N個(gè)無線傳感器節(jié)點(diǎn)：1)所有網(wǎng)內(nèi)節(jié)點(diǎn)都是同構(gòu)節(jié)點(diǎn)；2)節(jié)點(diǎn)之間的鏈路是對(duì)稱的；3)節(jié)點(diǎn)具有發(fā)送/接收與數(shù)據(jù)融合的能力；4)基站位于傳感器網(wǎng)外部。

2 路由協(xié)議的改進(jìn)

2.1 簇頭個(gè)數(shù)的確定

在網(wǎng)內(nèi)，普通節(jié)點(diǎn)數(shù)遠(yuǎn)大于簇頭節(jié)點(diǎn)數(shù)，且普通節(jié)點(diǎn)只承擔(dān)接收監(jiān)測(cè)數(shù)據(jù)與發(fā)送數(shù)據(jù)至簇頭節(jié)點(diǎn)，所以，考慮網(wǎng)內(nèi)能耗時(shí)，只需單獨(dú)考慮功能較多的簇頭節(jié)點(diǎn)。對(duì)于一個(gè)簇頭節(jié)點(diǎn)來說，它的能耗主要源自3個(gè)方面：簇頭節(jié)點(diǎn)接收簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)消耗的能量Ech-rec，簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合消耗的能量Ech-df，簇頭節(jié)點(diǎn)將融合完畢的數(shù)據(jù)發(fā)送給基站時(shí)消耗的能量Ech-bs[5]，即

E∑=Ech-rec+Ech-df+Ech-bs.

(2)

在簇的建立階段，可以保證每個(gè)簇群內(nèi)普通節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的距離，使其通信模型符合自由空間信道模型。假設(shè)網(wǎng)內(nèi)簇頭節(jié)點(diǎn)的個(gè)數(shù)為n，則每個(gè)簇群內(nèi)傳感器節(jié)點(diǎn)的個(gè)數(shù)為N/n，普通節(jié)點(diǎn)發(fā)送數(shù)據(jù)大小為lbit。由公式(1)得

(3)

(4)

其中，εdf為簇頭節(jié)點(diǎn)每進(jìn)行1 bit數(shù)據(jù)融合而消耗的能量。

假設(shè)在該區(qū)域內(nèi)，傳感器節(jié)點(diǎn)的概率密度為ρ(x,y)，每個(gè)簇群覆蓋的面積為一半徑為r的正圓，S/n=πr2，則

(5)

令ρ(r,θ)為常數(shù)C， 將其帶入公式(3)得

(6)

設(shè)融合后每個(gè)簇頭節(jié)點(diǎn)需發(fā)送的數(shù)據(jù)大小為kbit。簇頭節(jié)點(diǎn)與基站的通信模型符合多徑衰落信道模型，即

(7)

(8)

可以得到一輪中單個(gè)簇頭的能耗為

(9)

(10)

(11)

因?yàn)樵诖笮投嗵亻g通信協(xié)議中，多跳路由協(xié)議能耗一定少于單跳路由協(xié)議[6]，所以，nsingle和nproper可以作為簇頭個(gè)數(shù)選擇的參考。

2.2 簇頭的選擇與生成

簇頭的選擇對(duì)于分簇路由協(xié)議至關(guān)重要，因?yàn)闊o論是簇內(nèi)通信還是簇間通信距離，都受簇頭分布的位置影響。

在LEACH協(xié)議中，所有節(jié)點(diǎn)都能參與簇頭節(jié)點(diǎn)的選舉，這是十分不合理的。在均勻分簇算法中，若是簇頭節(jié)點(diǎn)所在的區(qū)域節(jié)點(diǎn)過于稀疏，可能會(huì)造成整個(gè)簇群通信范圍變大，或是有普通節(jié)點(diǎn)加入簇頭失敗，如圖1中節(jié)點(diǎn)2的區(qū)域；相反，周圍節(jié)點(diǎn)比較密集的節(jié)點(diǎn)1就更適合成為簇頭。

圖1 簇頭的選擇區(qū)域示意圖

參數(shù)p的選取至關(guān)重要，如果p選取過高，會(huì)導(dǎo)致參與選舉的簇頭局限在某些區(qū)域內(nèi)，從而在網(wǎng)絡(luò)工作過程中，該區(qū)域能量急遽下降，不利于延長(zhǎng)網(wǎng)絡(luò)壽命。

3 算法仿真與分析

為了研究改進(jìn)算法與原有的算法的區(qū)別，本文在NS2網(wǎng)絡(luò)仿真軟件的環(huán)境下進(jìn)行仿真。環(huán)境參數(shù)設(shè)置為：仿真區(qū)域大小為100 m×100 m；節(jié)點(diǎn)個(gè)數(shù)為100；參數(shù)p為0.8；基站位置為(50,65)m；數(shù)據(jù)包長(zhǎng)度為4 000 bit。

圖2為在選擇不同的參數(shù)p情況下網(wǎng)絡(luò)節(jié)點(diǎn)生存的情況(p分別取1，0.5，0.8)。從圖中可以看出：當(dāng)參數(shù)p選擇為0.5時(shí)，曲線與原LEACH協(xié)議比較接近，說明參數(shù)p選擇較小，對(duì)改善網(wǎng)內(nèi)能耗分布基本沒有作用。當(dāng)參數(shù)p選擇為1時(shí)，雖然第一次出現(xiàn)死亡節(jié)點(diǎn)的輪數(shù)有所推遲，但是一段時(shí)間后節(jié)點(diǎn)迅速死亡，在符合條件的候選簇頭節(jié)點(diǎn)全部死亡的情況下，網(wǎng)絡(luò)通信失敗。最終選擇p=0.8為較合適參數(shù)。

圖2 不同參數(shù)p對(duì)網(wǎng)絡(luò)的影響

圖3從每輪存活節(jié)點(diǎn)個(gè)數(shù)這個(gè)方面，對(duì)LEACH,LEACH-C以及改進(jìn)后的SDD-LEACH協(xié)議進(jìn)行比較。從仿真中可以得出:SDD-LEACH的出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)的時(shí)間有了一定的延后，且整個(gè)網(wǎng)內(nèi)節(jié)點(diǎn)死亡速率較前2種算法減慢，在相同的輪數(shù)下，改進(jìn)算法具有更多的存活節(jié)點(diǎn)數(shù)。

表1為各協(xié)議下首次出現(xiàn)死亡節(jié)點(diǎn)的輪數(shù)。

表1 各協(xié)議死亡節(jié)點(diǎn)首次出現(xiàn)輪數(shù)

圖3 不同協(xié)議下節(jié)點(diǎn)存活數(shù)目對(duì)比

圖4為每輪節(jié)點(diǎn)能耗對(duì)比。由圖4知，改進(jìn)協(xié)議的能耗曲線更為緩和，說明改進(jìn)協(xié)議可以較好完成平衡網(wǎng)內(nèi)能量。

圖4 不同協(xié)議下每輪能耗對(duì)比

4 結(jié) 論

本文在總結(jié)已有的各類成簇算法的基礎(chǔ)上，總結(jié)了基于成簇的無線傳感器路由協(xié)議的主要思想，提出了一種改進(jìn)的成簇算法。將節(jié)點(diǎn)密度作為約束條件，減少了簇內(nèi)與簇間通信的距離，從而減少了通信能耗，延長(zhǎng)了網(wǎng)絡(luò)壽命,并且該改進(jìn)法對(duì)分布式成簇算法具有良好的可移植性和實(shí)用性。本算法改進(jìn)所考慮的約束條件比較少，在參數(shù)p的選取上，只給出幾個(gè)參考數(shù)據(jù),后期將擴(kuò)大研究范圍。

參考文獻(xiàn):

[1] Marin-Perianu R S,Scholten J,Havinga P J M,et al.Cluster-based service discovery for heterogeneous wireless sensor networks[J].International Journal of Parallel,Emergent and Distributed Systems,2008,23(4):325-346.

[2] Dimokas N,Katsaros D,Manolopoulos Y.Energy-efficient distri-buted clustering in wireless sensor networks[J].Journal of Parallel and Distributed Computing,2010,70(4):371-383.

[3] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor network-s[C]∥2000 Proceedings of the 33rd Annual Hawaii International Conference on System Sciences,IEEE,2000:10.

[4] Cleuziou G.An extended version of the k-means method for overlapping clustering[C]∥2008 19th International Conference on Pattern Recognition,ICPR 2008，IEEE,2008：1-4.

[5] 尚鳳軍,任東海.無線傳感器網(wǎng)絡(luò)中分布式多跳路由算法研究[J].傳感技術(shù)學(xué)報(bào),2012,25(4):529-535．

[6] 周新蓮,吳 敏,徐建波.BPEC:無線傳感器網(wǎng)絡(luò)中一種能量感知的分布式分簇算法[J].計(jì)算機(jī)研究與發(fā)展,2009(5):723-730.