一種基于分簇的無線傳感器網絡GPSR 協議*

沈丹丹，王立華，王 宇，王振洲

(1.上海海洋大學 信息學院，上海201306;2.中國水產科學研究院 漁業工程研究所，北京100141)

0 引 言

無線傳感器網絡(wireless sensor networks，WSNs)［1］是由大量微小的傳感器節點組成的一種多跳無線網絡，通過無線方式通信，網絡設置靈活，設備位置可以隨時更改，還可以跟互聯網進行有線或無線方式的連接。WSNs 廣泛應用于軍事、智能交通、環境監控、醫療衛生等多個領域。由于WSNs 節點本身電池能量有限，在惡劣環境下，電池不易更換，當電池能量耗盡時，節點就會死亡，當網絡中死亡節點過多就會導致網絡癱瘓，因此，控制節點能量損耗成為延長網絡的生存周期主要難題［2］。

GPSR［3］(greedy perimeter stateless routing)協議建立在傳統貪婪轉發算法之上，其優點是只依賴直接鄰節點進行路由選擇，避免在節點中建立、維護、存儲路由表，幾乎處于無狀態;數據傳輸時延小;健壯性好。在一定程度上GPSR協議可節省節點的能量。而缺點是當網絡中Sink 點和源節點在兩個區域時，由于通信量不平衡導致部分節點失效，嚴重影響WSNs 生存時間。

為了延長網絡生存周期，提出了一種基于分簇的WSNs GPSR 協議。通過仿真結果表明:該協議不僅能延長網絡生存周期，還能提高數據傳輸成功率。

1 GPSR 協議簡介

GPSR 是一種基于傳統貪婪轉發方案的路由協議。為了避免傳統貪婪轉發方案中通信空洞造成的路由尋徑失敗和由此產生的重復路由請求帶來的額外開銷，GPSR 利用傳感節點對位置信息的可知性，在路由過程遭遇通信空洞而失效時，根據網絡原始拓撲生成一個平面子圖并沿子圖中空洞的周界進行分組轉發［4］。

2 WSNs 模型與算法改進

2.1 基于位置的WSNs 模型

針對本文提出的改進算法，提出以下假設條件:

1)每個節點初始能量相同ei(0);

2)每個節點擔任簇頭期間耗費的能量均等;

3)所有節點隨機分布，并且傳感器射頻發射功率恒定。

本文節點的地理信息位置由GPS 獲得，設節點Li={Li=(xi，yi)}，設Li表示節點i 的生存時間，ei(0)為傳感器初始能量，T 表示整個網絡從起始狀態的能量到第一個節點是失效的時間，則有T=min(T1，T2，….TN)。

根據能量模型［5］

式中 Eelec為發送電路和接收電路每發送或接收單位比特所消耗的能量;εfs為自由空間傳播模型下功率放大所需要的耗能系數;εmp為多路徑衰減傳播模型下功率放大所需要的耗能系數;d0為門限距離。

由式(1)可看出，傳感器節點數據傳輸時，盡可能選擇距離較短的路由，減少節點耗能，延長整個WSNs 的生存周期。

2.2 改進GPSR 協議算法

2.2.1 簇的建立階段

WSNs 會被分成多個大小不同的簇，每個簇中包括一個簇頭節點和多個普通節點，根據文獻［6］可知，最優簇頭數為

式中 εfs為自由空間傳播模型下功率放大所需耗能系數;εmp為多路徑衰減傳播模型下功率放大所需要的耗能系數;dtoBs為簇頭到基站的距離。

簇頭節點不僅要負責接收、融合、傳輸簇內節點的數據而且還要負責轉發其他簇頭節點傳輸的數據，所以，選擇剩余能量較少的傳感器節點作為簇頭節點，那么，該傳感器節點會因為耗能過快而失效，這樣，這個WSNs 的數據傳輸將會遭到破壞而失效［7～9］。因此，簇頭節點的選擇應該考慮傳感器節點的剩余能量。

2.2.2 簇頭的選舉優化

節點隨機產生一個［0，1］間的隨機數，如果這個數小于閾值T(n)，則廣播自己是簇頭的消息。在每輪循環中，如果節點已經被當選為簇頭，則設置T(n)為0，這樣，該節點不會被再次被選為簇頭。未被當選為簇頭的節點被選中的概率T(n)

T(n)=0，其他情況下

式中 p 為簇頭占所有節點的百分比，即節點當選簇頭的概率;R 為目前循環進行的輪數;G 為最近1/p 輪中還未當選過簇頭的節點集合。

WSNs 中所有節點等概率地擔任簇首，保持網絡內節點能量的均衡消耗，延長了整個網絡生命周期。考慮到能量問題，將T(n)優化為

式中 En_current為節點的當前能量;En為節點的初始能量。

2.2.3 改進貪婪算法建立路由

在傳統GPSR 協議中，源節點S 向目的節點D 發送數據包，數據包中標示了源節點和目的節點的位置信息。當目的節點D 不在源節點S 鄰節點列表中時，則需要轉發節點進行數據轉發。在GPSR 協議中使用貪婪轉發來獲取下一跳［10］。

源節點S 向目的節點D 發送數據包，具體改進步驟如下:

1)源節點S 首先選擇其通信半徑內與簇頭節點距離最近的一跳鄰節點A，若該節點是簇頭節點，則路由過程結束，簇頭節點直接將數據包發送至下一個簇的簇頭。

2)若A 不是簇頭節點，那么，源節點選擇覆蓋半徑內與簇頭節點距離最近的節點A'傳輸數據。

3)A'同樣選擇其通信覆蓋半徑范圍內與簇頭節點距離最近的節點傳輸數據。

4)重復步驟(2)，(3)，直到數據傳送至簇頭節點。

5)重復步驟(2)，(3)，(4)，直到數據傳送至目的節點D。

改進的路由協議執行的流程圖如圖1。

圖1 改進路由協議算法流程圖Fig 1 Algorithm flow chart of improved routing protocol

3 仿真與結果分析

3.1 仿真環境

在100 m×100 m 的正方形區域內，隨機分布100 個傳感器節點，這些節點初始能量相同且為0.5 J。本次仿真采用Matlab 2010b 進行模擬仿真，仿真環境參數設置如表1所示。

其中，Eelec為發送電路和接收電路每發送或接收單位比特所消耗的能量;εfs為自由空間傳播模型下功率放大所需耗能系數;εmp為多路徑衰減傳播模型下功率放大所需要的耗能系數。

表1 仿真參數設置Tab 1 Simulation parameters settings

3.2 仿真結果分析

1)網絡生存節點數

如圖2 所示，由于GPSR 協議存在局部最小化問題，當局部最小化問題突出時，節點能量損耗嚴重，導致節點失效，網絡生存下的節點數越來越少。而本文算法采用分簇算法避免了局部最小化問題，因此，節約了節點能量，延長了節點生存時間，使得生存的節點數增加。

圖2 網絡生存節點數對比圖Fig 2 Comparison diagram of number of network alive nodes

2)網絡節點能量消耗

如圖3 所示，GPSR 協議存在局部最小化問題，當局部最小化問題不突出時，節點之間的數據傳遞不會有太多影響，不會出現大量的能量損失。但當出現局部最小化問題時，能量損耗速度快，節點消失較多。而本文算法不存在局部最小化問題，因此，能較好節省節點能量，延長節點生存時間，即延長網絡的周期。

3)數據包轉發成功數

如圖4 所示，GPSR 協議數據傳輸成功率低，本文算法不存在局部最小化問題，在簇形成以后，就不必再消耗能量分簇。因此，網絡節點能量穩定，均衡消耗，數據傳輸率高。

圖3 網絡節點能量消耗對比圖Fig 3 Energy consumption comparison of network nodes

圖4 數據包轉發成功數對比圖Fig 4 Comparison diagram of number of packets successful transmission

4 結束語

為了延長網絡生存周期，本文提出一種基于分簇的WSNs GPSR 協議。該算法基于分簇思想提出基于每個鄰節點與簇頭節點距離的比較來建立路由，因此，不存在局部最小化問題，大大減少了算法的復雜度。由于WSNs 節點能源有限，考慮到節省能量來延長網絡生存周期，但卻是以增加數據傳輸時延為代價的。仿真對比結果表明:本文改進協議能有效均衡能耗，延長網絡生存周期。

［1］ 任豐原，黃海寧，林 闖.無線傳感器網絡［J］.軟件學報，2003，14(7):1282－1291.

［2］ Kail A，Kanatas A G，Efthymoglou G P.A cooperative beam forming solution for eliminating multi－hop communications in wireless sensor［J］.IEEE Journal on Selected Areas in Communications，2010，28(7):1055－1062.

［3］ 唐國明，謝 羿，唐九陽，等.一種基于左、右手法則的GPSR分區邊界轉發路由協議［J］.計算機應用研究，2011，28(3):1099－1101.

［4］ 張 威，施偉斌.無線傳感器網絡GPSR 路由協議研究［J］.電子測量技術，2010(9):118－121.

［5］ 李成法，陳貴海，葉 懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007(1):27－36.

［6］ 趙菊敏，張子辰，李燈熬，等.一種無線傳感器網絡鏈式傳輸分簇路由協議［J］.傳感器與微系統，2014，33(3):135－138，142.

［7］ 鐘 智，樊曉平，羅大庸，等.一種基于網格的無線傳感器網絡分簇路由協議［J］.傳感器與微系統，2011，30(12):18－20，24.

［8］ 侯貴升，吳曉蓓，黃 成，等.無線傳感器網絡中一種基于標號的貪婪轉發算法［J］.傳感器與微系統，2012，31(9):123－125，128.

［9］ 楊海迎.基于非均勻分簇的無線傳感器網絡路由協議設計與研究［J］.現代計算機:專業版，2014(7):3－6.

［10］徐躍州，張 欣，張 濤，等.基于貪婪－改進果蠅算法的無線傳感器網絡路由協議［J］.傳感器與微系統，2015，34(5):134－136，139.