基于分簇的移動(dòng)協(xié)助無線傳感器網(wǎng)絡(luò)路由協(xié)議*

蘭恒武，彭 艦，劉 唐，2

(1.四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都610065;2.四川師范大學(xué) 基礎(chǔ)教學(xué)學(xué)院，四川 成都610068)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)近年來作為一種新的數(shù)據(jù)收集模式廣泛用于戰(zhàn)場(chǎng)搜救、環(huán)境監(jiān)測(cè)、火災(zāi)應(yīng)急、醫(yī)療監(jiān)護(hù)等領(lǐng)域.典型的WSNs 是由低能耗、低成本、密集隨機(jī)部署的傳感器節(jié)點(diǎn)組成［1］。由于傳感器節(jié)點(diǎn)部署后難再次充電，而且其通信能力和資源有限，如何有效地提高節(jié)點(diǎn)的網(wǎng)絡(luò)生命周期是一個(gè)值得深入研究的課題。

文獻(xiàn)［2］提出的低功耗自適應(yīng)集簇分層型(low energy adaptive clustering hierarchy，LEACH)協(xié)議是典型的采用均勻分簇來提高網(wǎng)絡(luò)生命周期的算法，在該協(xié)議中，簇和Sink之間以單跳方式傳輸，造成遠(yuǎn)離Sink 的節(jié)點(diǎn)由于發(fā)送數(shù)據(jù)能量消耗過大而迅速死亡。而在使用多跳分簇傳感器網(wǎng)中，距離Sink 點(diǎn)越近的簇頭因轉(zhuǎn)發(fā)大量數(shù)據(jù)，造成簇頭能量消耗增加而失效，這些現(xiàn)象被稱為能量空洞［3］。文獻(xiàn)［4］提出的非均勻分簇(unequal clustering，UC)算法，采用多跳非均勻分簇的路由算法來解決能量空洞，它的主要思想是通過平衡簇頭之間的能量消耗來均衡網(wǎng)絡(luò)總能量消耗。文獻(xiàn)［5］提出的分布式能量均衡非均勻分簇(distributed energy-balanced unequal clustering，DEBUC)路由協(xié)議采用與文獻(xiàn)［4］相同方法，在多跳非均勻分簇時(shí)考慮了距離和能耗因素，但仍然無法完全解決能量空洞的問題。

解決能量空洞的另一種方法是采用移動(dòng)協(xié)助數(shù)據(jù)收集器直接訪問傳感器節(jié)點(diǎn)的數(shù)據(jù)策略［6］。在文獻(xiàn)［7～9］中，移動(dòng)數(shù)據(jù)收集器(mobile data collector，MDC)直接與傳感器節(jié)點(diǎn)進(jìn)行通信。文獻(xiàn)［7］研究Sink 的路徑規(guī)劃問題，將遍歷更多的傳感器節(jié)點(diǎn)(更長(zhǎng)的路徑)問題轉(zhuǎn)化為旅行商問題進(jìn)行求解.文獻(xiàn)［8］引入數(shù)據(jù)協(xié)助策略DMS，該策略主要包括路徑選擇、速度控制以及數(shù)據(jù)收集。文獻(xiàn)［9，10］在方形網(wǎng)絡(luò)中，Sink 直接移動(dòng)到簇頭通信范圍，單跳收集簇頭數(shù)據(jù)，利用混合整數(shù)規(guī)劃來最大化網(wǎng)絡(luò)壽命。顯然，上述幾種算法中利用單跳直接傳遞消息數(shù)據(jù)，能大大減少網(wǎng)絡(luò)總的能量消耗，但在移動(dòng)Sink 速度受限情況下，移動(dòng)Sink 路徑越長(zhǎng)，網(wǎng)絡(luò)的時(shí)延越大。

本文提出了一種基于分簇的移動(dòng)協(xié)助(CMA)傳感器網(wǎng)絡(luò)中的路由協(xié)議，無線Sink 以恒定速率在圓形網(wǎng)絡(luò)中做圓周運(yùn)動(dòng)，針對(duì)能量空洞現(xiàn)象，提出移動(dòng)Sink 與多跳相結(jié)合來延長(zhǎng)網(wǎng)絡(luò)的生命周期的思想。本文在網(wǎng)絡(luò)初始階段，先確定移動(dòng)Sink 的運(yùn)動(dòng)半徑，將網(wǎng)絡(luò)進(jìn)行均勻分簇。在Sink 通信范圍內(nèi)確定一批普通節(jié)點(diǎn)作為匯聚節(jié)點(diǎn)，Sink 進(jìn)行數(shù)據(jù)采集，仿真實(shí)驗(yàn)驗(yàn)證了CMA 路由協(xié)議的有效性。

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

設(shè)定在一個(gè)半徑為R 的圓形網(wǎng)絡(luò)區(qū)域A 內(nèi)［8］，存在N 個(gè)固定部署的普通傳感器節(jié)點(diǎn)和移動(dòng)Sink.各普通傳感器節(jié)點(diǎn)均勻分布在A 內(nèi)。如圖1，假定該網(wǎng)絡(luò)具有如下性質(zhì):

網(wǎng)絡(luò)內(nèi)的Sink 以移動(dòng)基站形式部署，部署后沿固定軌跡做圓周運(yùn)動(dòng)，速度大小不變。Sink 節(jié)點(diǎn)的能量不受限制，發(fā)射功率可調(diào)。各個(gè)普通傳感器節(jié)點(diǎn)類型相同，且所有節(jié)點(diǎn)和移動(dòng)Sink 通信半徑均為r，存儲(chǔ)容量均為C，消息產(chǎn)生率λ。所有普通傳感器節(jié)點(diǎn)通過GPS 或其他輔助設(shè)備知道自身位置，節(jié)點(diǎn)已知網(wǎng)絡(luò)中心位置。

圖1 網(wǎng)絡(luò)模型Fig 1 Network model

2 CMA 設(shè)計(jì)

2.1 Sink 移動(dòng)半徑選擇

本小節(jié)討論移動(dòng)Sink 做圓周運(yùn)動(dòng)的半徑Rs，應(yīng)用程序要求時(shí)延為Dr，滿足:Tmin≤Dr≤Tmax，v 表示Sink 的運(yùn)動(dòng)速度，節(jié)點(diǎn)的密度為ρ。

定理1 網(wǎng)絡(luò)的總能量消耗最小，Sink 的最優(yōu)半徑須滿足

證明:如圖1 所示，設(shè)接收1 跳距離的l bit 消息需消耗E0J。移動(dòng)Sink 把整個(gè)網(wǎng)絡(luò)區(qū)域劃分成大于Rs的區(qū)域2 和小于Rs的區(qū)域1，對(duì)于區(qū)域2，在距O 為x、寬為dx 的圓環(huán)上，取夾角dθ 的一小段扇環(huán)，這一區(qū)域的節(jié)點(diǎn)個(gè)數(shù)期望為xdθ·dx·r。為使總能量最小，節(jié)點(diǎn)傳送數(shù)據(jù)將沿最短路徑傳送消息給Sink，節(jié)點(diǎn)到Sink 的跳數(shù)近似為(x-L)/r，那么上述區(qū)域節(jié)點(diǎn)傳輸?shù)絊ink 的能耗為。綜上，區(qū)域2 的總能量為

同理，當(dāng)x ＜Rs時(shí)，區(qū)域1 的總能量為

綜上，網(wǎng)絡(luò)總的能量消耗為

對(duì)公式(6)求導(dǎo)，可得

公式(7)得出網(wǎng)絡(luò)總消耗的最小能量，且還需滿足

若應(yīng)用要求時(shí)延滿足定理1，則以上述半徑作為移動(dòng)Sink 的運(yùn)動(dòng)半徑;否則，Rs應(yīng)為

2.2 簇的形成

Sink 隨機(jī)選取候選簇頭，并以相同的競(jìng)爭(zhēng)半徑參加競(jìng)選，在候選簇頭交疊區(qū)域，選取剩余能量最大的候選簇頭作為簇頭，其他節(jié)點(diǎn)根據(jù)接收到信號(hào)強(qiáng)弱選擇加入最近的簇。

2.3 RP 選取

RP 節(jié)點(diǎn)的選取由移動(dòng)Sink 統(tǒng)一選取。RP 的選取策略，是移動(dòng)Sink 從通信范圍內(nèi)選取任意普通節(jié)點(diǎn)作為候選RP 節(jié)點(diǎn)j(j=1，2，…，ncp)，不在Sink 單跳通信范圍內(nèi)的簇頭節(jié)點(diǎn)i(i=1，2，…，nm)作為子RP 路由節(jié)點(diǎn)，設(shè)k 為RP 節(jié)點(diǎn)的個(gè)數(shù)，顯然，有

2.4 數(shù)據(jù)采集

簇形成時(shí)，普通成員節(jié)點(diǎn)將消息數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn)，簇頭接收并融合處理消息數(shù)據(jù)，然后進(jìn)行簇間路由。簇間路由時(shí)，對(duì)任意簇頭i，若在Sink 單跳范圍內(nèi)，則等待Sink 運(yùn)動(dòng)到其通信范圍內(nèi)直接與移動(dòng)Sink 通信;否則，需要轉(zhuǎn)發(fā)。簇頭i 沿最短路徑傳遞消息給與其對(duì)應(yīng)RP 節(jié)點(diǎn)，如圖2 所示。

圖2 CMA 算法示意圖Fig 2 Illustration of CMA algorithm

3 CMA 仿真實(shí)驗(yàn)

本文在Matlab 環(huán)境下進(jìn)行仿真，討論了不同參數(shù)變化(Sink 的運(yùn)動(dòng)速率、簇半徑)，對(duì)CMA 算法的性能影響，最后仿真實(shí)現(xiàn)了CMA，LEACH，DEBUC 3 種算法性能對(duì)比。如表1，所有參數(shù)值均勻分布在表中對(duì)應(yīng)參數(shù)取值范圍內(nèi)。

表1 模擬參數(shù)Tab 1 Simulation parameters

3.1 Sink 運(yùn)動(dòng)速率對(duì)性能的影響

本節(jié)實(shí)驗(yàn)研究其他參數(shù)不變情況下Sink 運(yùn)動(dòng)速率對(duì)CMA 算法性能的影響。由于所有節(jié)點(diǎn)剩余能量均較低，故統(tǒng)計(jì)總剩余能量.仿真結(jié)果如圖3 所示。當(dāng)Sink 運(yùn)動(dòng)速率增大，網(wǎng)絡(luò)時(shí)延不變時(shí)，可由公式(9)推導(dǎo)出移動(dòng)Sink 的運(yùn)動(dòng)半徑增加。圖3(a)可以看出:CMA 算法平均簇頭數(shù)目變化相對(duì)較小，這是由于均勻分簇且簇半徑保持不變;圖3(b)，(c)表明，隨速率增加Sink 的運(yùn)動(dòng)半徑逐漸到達(dá)最優(yōu)取值160m，CMA 算法的生命周期有一定的增加，總剩余能量逐漸減少，反映出CMA 有較高的能量利用率。

圖3 Sink 運(yùn)動(dòng)速度的影響Fig 3 Influence of sink moving speed

3.2 簇半徑對(duì)性能的影響

本組實(shí)驗(yàn)研究CMA 分簇時(shí)不同簇半徑情況下，CMA算法的性能變化，結(jié)果如圖4 所示。圖4(a)表明:CMA 算法由于簇半徑增加平均簇頭數(shù)目有所減少，圖4(b)顯示，隨簇半徑增加，簇內(nèi)能量消耗增加，網(wǎng)絡(luò)的生命周期減小，因此，網(wǎng)絡(luò)最優(yōu)簇半徑在20 m 左右。圖4(c)隨節(jié)點(diǎn)簇半徑改變，總剩余能量變化，由圖4(c)，(b)得出節(jié)點(diǎn)的能量得到較優(yōu)利用，總剩余能量有一定增加，由于簇半徑增加，簇內(nèi)能量消耗增大，總剩余能量減少，網(wǎng)絡(luò)生命周期也減少。

圖4 簇半徑對(duì)CMA 算法的影響Fig 4 Influence of cluster radius on CMA algorithm

3.3 幾種算法性能對(duì)比

在各參數(shù)取表1，速率3 m/s，簇半徑60 m，應(yīng)用程序時(shí)延要求為400 ～800 s。普通傳感器節(jié)點(diǎn)總數(shù)1 600 個(gè)情況下，CMA，LEACH，DEBUC 3 種算法性能對(duì)比仿真結(jié)果如圖5所示。

圖5 CMA 算法與其他算法對(duì)比Fig 5 Comparison of CMA and other algorithms

圖5 (a)是統(tǒng)計(jì)簇頭數(shù)目出現(xiàn)次數(shù).DEBUC 與CMA 簇頭數(shù)目更加穩(wěn)定，是由于LEACH 隨機(jī)選擇簇頭。圖5(b)顯示了幾種算法生命周期(存活節(jié)點(diǎn)數(shù)目)隨輪數(shù)變化曲線。由于DEBUC 算法使用非均勻分簇有效平衡了能量消耗，比LEACH 算法更優(yōu)，故結(jié)果與DEBUC 算法相當(dāng)，低于CMA 的生命周期。圖5(c)比較了3 種算法網(wǎng)絡(luò)總能耗，DEBUC 分簇比LEACH 能量消耗較少，由于DEBUC 算法更多的考慮能量和距離因素。CMA 算法由于采用移動(dòng)Sink和RP 節(jié)點(diǎn)作為數(shù)據(jù)緩存因而生命周期更長(zhǎng)和最低的能量消耗。

4 結(jié) 論

本文提出了一種CMA 算法，Sink 以恒定速率在圓形網(wǎng)絡(luò)中做圓周運(yùn)動(dòng)，在網(wǎng)絡(luò)初始階段，先確定移動(dòng)Sink 的運(yùn)動(dòng)半徑，將網(wǎng)絡(luò)進(jìn)行均勻分簇。在Sink 通信范圍內(nèi)確定一批普通節(jié)點(diǎn)作為Rp，Sink 進(jìn)行數(shù)據(jù)采集。計(jì)算了在圓形網(wǎng)絡(luò)中受到應(yīng)用時(shí)延和能量最優(yōu)限制的Sink 運(yùn)動(dòng)半徑，并結(jié)合分簇和移動(dòng)Sink 來優(yōu)化網(wǎng)絡(luò)壽命。仿真實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

［1］ Akyildiz I F，Su W J，Sankarasubramaniam Y，et al.Wireless sensor networks:A survey［J］.Computer Networks，2002，38(4):393-422.

［2］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks［C］∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，Hawaii，USA，2000:3005-3014.

［3］ Tang L，Jian P，Xiao F W et al.Research on the energy hole problem based on non-uniform node distribution for wireless sensor networks［J］.Transactions on Internet and Information Systems，2012，6(9):2017-2036.

［4］ Soro S，Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］∥Proc of the 19th IEEE Int’l Parallel and Distributed Processing Symp:IEEE Computer Society，Denver，USA，2005:236-244.

［5］ 蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.軟件學(xué)報(bào)，2012，23(5):1222-1232.

［6］ 張希偉，戴海鵬，徐力杰，等.無線傳感器網(wǎng)絡(luò)中移動(dòng)協(xié)助的數(shù)據(jù)收集策略研究［J］.軟件學(xué)報(bào)，2013，24(2):198-214.

［7］ Nesamony S，Vairamuthu M K，Orlowska M E.On optimal route of a calibrating mobile sink in a wireless sensor networks［C］∥Proc of the IEEE INSS，Braunschweig，Germany，2007:61-64.

［8］ Ryo S，Rajesh K G.Optimizing energy-latency trade-off in sensor networks with controlled mobility［C］∥Proc of the IEEE INFOCOM，Rio de Janeiro，Brazil，2009:1398-1408.

［9］ Tashtarian F，Moghaddam M H Y，Effati S.Energy efficient data gathering algorithm in hierarchical wireless sensor networks with mobile sink［C］∥2012 2nd IEEE International Conference，Mashhad，Iran，2012:232-237.