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

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

0 引 言

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

GPSR［3］(greedy perimeter stateless routing)協(xié)議建立在傳統(tǒng)貪婪轉(zhuǎn)發(fā)算法之上，其優(yōu)點(diǎn)是只依賴直接鄰節(jié)點(diǎn)進(jìn)行路由選擇，避免在節(jié)點(diǎn)中建立、維護(hù)、存儲路由表，幾乎處于無狀態(tài);數(shù)據(jù)傳輸時延小;健壯性好。在一定程度上GPSR協(xié)議可節(jié)省節(jié)點(diǎn)的能量。而缺點(diǎn)是當(dāng)網(wǎng)絡(luò)中Sink 點(diǎn)和源節(jié)點(diǎn)在兩個區(qū)域時，由于通信量不平衡導(dǎo)致部分節(jié)點(diǎn)失效，嚴(yán)重影響WSNs 生存時間。

為了延長網(wǎng)絡(luò)生存周期，提出了一種基于分簇的WSNs GPSR 協(xié)議。通過仿真結(jié)果表明:該協(xié)議不僅能延長網(wǎng)絡(luò)生存周期，還能提高數(shù)據(jù)傳輸成功率。

1 GPSR 協(xié)議簡介

GPSR 是一種基于傳統(tǒng)貪婪轉(zhuǎn)發(fā)方案的路由協(xié)議。為了避免傳統(tǒng)貪婪轉(zhuǎn)發(fā)方案中通信空洞造成的路由尋徑失敗和由此產(chǎn)生的重復(fù)路由請求帶來的額外開銷，GPSR 利用傳感節(jié)點(diǎn)對位置信息的可知性，在路由過程遭遇通信空洞而失效時，根據(jù)網(wǎng)絡(luò)原始拓?fù)渖梢粋€平面子圖并沿子圖中空洞的周界進(jìn)行分組轉(zhuǎn)發(fā)［4］。

2 WSNs 模型與算法改進(jìn)

2.1 基于位置的WSNs 模型

針對本文提出的改進(jìn)算法，提出以下假設(shè)條件:

1)每個節(jié)點(diǎn)初始能量相同ei(0);

2)每個節(jié)點(diǎn)擔(dān)任簇頭期間耗費(fèi)的能量均等;

3)所有節(jié)點(diǎn)隨機(jī)分布，并且傳感器射頻發(fā)射功率恒定。

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

根據(jù)能量模型［5］

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

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

2.2 改進(jìn)GPSR 協(xié)議算法

2.2.1 簇的建立階段

WSNs 會被分成多個大小不同的簇，每個簇中包括一個簇頭節(jié)點(diǎn)和多個普通節(jié)點(diǎn)，根據(jù)文獻(xiàn)［6］可知，最優(yōu)簇頭數(shù)為

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

簇頭節(jié)點(diǎn)不僅要負(fù)責(zé)接收、融合、傳輸簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)而且還要負(fù)責(zé)轉(zhuǎn)發(fā)其他簇頭節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)，所以，選擇剩余能量較少的傳感器節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)，那么，該傳感器節(jié)點(diǎn)會因?yàn)楹哪苓^快而失效，這樣，這個WSNs 的數(shù)據(jù)傳輸將會遭到破壞而失效［7～9］。因此，簇頭節(jié)點(diǎn)的選擇應(yīng)該考慮傳感器節(jié)點(diǎn)的剩余能量。

2.2.2 簇頭的選舉優(yōu)化

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

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

式中 p 為簇頭占所有節(jié)點(diǎn)的百分比，即節(jié)點(diǎn)當(dāng)選簇頭的概率;R 為目前循環(huán)進(jìn)行的輪數(shù);G 為最近1/p 輪中還未當(dāng)選過簇頭的節(jié)點(diǎn)集合。

WSNs 中所有節(jié)點(diǎn)等概率地?fù)?dān)任簇首，保持網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)能量的均衡消耗，延長了整個網(wǎng)絡(luò)生命周期?？紤]到能量問題，將T(n)優(yōu)化為

式中 En_current為節(jié)點(diǎn)的當(dāng)前能量;En為節(jié)點(diǎn)的初始能量。

2.2.3 改進(jìn)貪婪算法建立路由

在傳統(tǒng)GPSR 協(xié)議中，源節(jié)點(diǎn)S 向目的節(jié)點(diǎn)D 發(fā)送數(shù)據(jù)包，數(shù)據(jù)包中標(biāo)示了源節(jié)點(diǎn)和目的節(jié)點(diǎn)的位置信息。當(dāng)目的節(jié)點(diǎn)D 不在源節(jié)點(diǎn)S 鄰節(jié)點(diǎn)列表中時，則需要轉(zhuǎn)發(fā)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。在GPSR 協(xié)議中使用貪婪轉(zhuǎn)發(fā)來獲取下一跳［10］。

源節(jié)點(diǎn)S 向目的節(jié)點(diǎn)D 發(fā)送數(shù)據(jù)包，具體改進(jìn)步驟如下:

1)源節(jié)點(diǎn)S 首先選擇其通信半徑內(nèi)與簇頭節(jié)點(diǎn)距離最近的一跳鄰節(jié)點(diǎn)A，若該節(jié)點(diǎn)是簇頭節(jié)點(diǎn)，則路由過程結(jié)束，簇頭節(jié)點(diǎn)直接將數(shù)據(jù)包發(fā)送至下一個簇的簇頭。

2)若A 不是簇頭節(jié)點(diǎn)，那么，源節(jié)點(diǎn)選擇覆蓋半徑內(nèi)與簇頭節(jié)點(diǎn)距離最近的節(jié)點(diǎn)A'傳輸數(shù)據(jù)。

3)A'同樣選擇其通信覆蓋半徑范圍內(nèi)與簇頭節(jié)點(diǎn)距離最近的節(jié)點(diǎn)傳輸數(shù)據(jù)。

4)重復(fù)步驟(2)，(3)，直到數(shù)據(jù)傳送至簇頭節(jié)點(diǎn)。

5)重復(fù)步驟(2)，(3)，(4)，直到數(shù)據(jù)傳送至目的節(jié)點(diǎn)D。

改進(jìn)的路由協(xié)議執(zhí)行的流程圖如圖1。

圖1 改進(jìn)路由協(xié)議算法流程圖Fig 1 Algorithm flow chart of improved routing protocol

3 仿真與結(jié)果分析

3.1 仿真環(huán)境

在100 m×100 m 的正方形區(qū)域內(nèi)，隨機(jī)分布100 個傳感器節(jié)點(diǎn)，這些節(jié)點(diǎn)初始能量相同且為0.5 J。本次仿真采用Matlab 2010b 進(jìn)行模擬仿真，仿真環(huán)境參數(shù)設(shè)置如表1所示。

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

表1 仿真參數(shù)設(shè)置Tab 1 Simulation parameters settings

3.2 仿真結(jié)果分析

1)網(wǎng)絡(luò)生存節(jié)點(diǎn)數(shù)

如圖2 所示，由于GPSR 協(xié)議存在局部最小化問題，當(dāng)局部最小化問題突出時，節(jié)點(diǎn)能量損耗嚴(yán)重，導(dǎo)致節(jié)點(diǎn)失效，網(wǎng)絡(luò)生存下的節(jié)點(diǎn)數(shù)越來越少。而本文算法采用分簇算法避免了局部最小化問題，因此，節(jié)約了節(jié)點(diǎn)能量，延長了節(jié)點(diǎn)生存時間，使得生存的節(jié)點(diǎn)數(shù)增加。

圖2 網(wǎng)絡(luò)生存節(jié)點(diǎn)數(shù)對比圖Fig 2 Comparison diagram of number of network alive nodes

2)網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗

如圖3 所示，GPSR 協(xié)議存在局部最小化問題，當(dāng)局部最小化問題不突出時，節(jié)點(diǎn)之間的數(shù)據(jù)傳遞不會有太多影響，不會出現(xiàn)大量的能量損失。但當(dāng)出現(xiàn)局部最小化問題時，能量損耗速度快，節(jié)點(diǎn)消失較多。而本文算法不存在局部最小化問題，因此，能較好節(jié)省節(jié)點(diǎn)能量，延長節(jié)點(diǎn)生存時間，即延長網(wǎng)絡(luò)的周期。

3)數(shù)據(jù)包轉(zhuǎn)發(fā)成功數(shù)

如圖4 所示，GPSR 協(xié)議數(shù)據(jù)傳輸成功率低，本文算法不存在局部最小化問題，在簇形成以后，就不必再消耗能量分簇。因此，網(wǎng)絡(luò)節(jié)點(diǎn)能量穩(wěn)定，均衡消耗，數(shù)據(jù)傳輸率高。

圖3 網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗對比圖Fig 3 Energy consumption comparison of network nodes

圖4 數(shù)據(jù)包轉(zhuǎn)發(fā)成功數(shù)對比圖Fig 4 Comparison diagram of number of packets successful transmission

4 結(jié)束語

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

［1］ 任豐原，黃海寧，林 闖.無線傳感器網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，2003，14(7):1282－1291.

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

［3］ 唐國明，謝 羿，唐九陽，等.一種基于左、右手法則的GPSR分區(qū)邊界轉(zhuǎn)發(fā)路由協(xié)議［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(3):1099－1101.

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

［5］ 李成法，陳貴海，葉 懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2007(1):27－36.

［6］ 趙菊敏，張子辰，李燈熬，等.一種無線傳感器網(wǎng)絡(luò)鏈?zhǔn)絺鬏敺执芈酚蓞f(xié)議［J］.傳感器與微系統(tǒng)，2014，33(3):135－138，142.

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

［8］ 侯貴升，吳曉蓓，黃 成，等.無線傳感器網(wǎng)絡(luò)中一種基于標(biāo)號的貪婪轉(zhuǎn)發(fā)算法［J］.傳感器與微系統(tǒng)，2012，31(9):123－125，128.

［9］ 楊海迎.基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)與研究［J］.現(xiàn)代計(jì)算機(jī):專業(yè)版，2014(7):3－6.

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