一種基于節點密度的無線傳感器網絡路由協議*

路成杰， 蔣海峰

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

0 引 言

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

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

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

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

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

1 模型建立

1.1 能量模型

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

(1)

1.2 網絡模型

假設在一面積為S的特定區域內，一共分布了N個無線傳感器節點：1)所有網內節點都是同構節點；2)節點之間的鏈路是對稱的；3)節點具有發送/接收與數據融合的能力；4)基站位于傳感器網外部。

2 路由協議的改進

2.1 簇頭個數的確定

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

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

(2)

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

(3)

(4)

其中，εdf為簇頭節點每進行1 bit數據融合而消耗的能量。

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

(5)

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

(6)

設融合后每個簇頭節點需發送的數據大小為kbit。簇頭節點與基站的通信模型符合多徑衰落信道模型，即

(7)

(8)

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

(9)

(10)

(11)

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

2.2 簇頭的選擇與生成

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

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

圖1 簇頭的選擇區域示意圖

參數p的選取至關重要，如果p選取過高，會導致參與選舉的簇頭局限在某些區域內，從而在網絡工作過程中，該區域能量急遽下降，不利于延長網絡壽命。

3 算法仿真與分析

為了研究改進算法與原有的算法的區別，本文在NS2網絡仿真軟件的環境下進行仿真。環境參數設置為：仿真區域大小為100 m×100 m；節點個數為100；參數p為0.8；基站位置為(50,65)m；數據包長度為4 000 bit。

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

圖2 不同參數p對網絡的影響

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

表1為各協議下首次出現死亡節點的輪數。

表1 各協議死亡節點首次出現輪數

圖3 不同協議下節點存活數目對比

圖4為每輪節點能耗對比。由圖4知，改進協議的能耗曲線更為緩和，說明改進協議可以較好完成平衡網內能量。

圖4 不同協議下每輪能耗對比

4 結 論

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

參考文獻:

[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] 尚鳳軍,任東海.無線傳感器網絡中分布式多跳路由算法研究[J].傳感技術學報,2012,25(4):529-535．

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