路成杰， 蔣海峰

(南京理工大學 自動化學院，江蘇 南京 210094)

0 引 言

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

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

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

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

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

1 模型建立

1.1 能量模型

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

(1)

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

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

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

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

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

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

(2)

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

(3)

(4)

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

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

(5)

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

(6)

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

(7)

(8)

可以得到一輪中單個簇頭的能耗為

(9)

(10)

(11)

因為在大型多跳簇間通信協(xié)議中，多跳路由協(xié)議能耗一定少于單跳路由協(xié)議[6]，所以，nsingle和nproper可以作為簇頭個數(shù)選擇的參考。

2.2 簇頭的選擇與生成

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

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

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

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

3 算法仿真與分析

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

參考文獻:

[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ù)學報,2012,25(4):529-535．

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