蘭恒武，彭 艦，劉 唐，2

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

0 引 言

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

文獻(xiàn)［2］提出的低功耗自適應(yīng)集簇分層型(low energy adaptive clustering hierarchy，LEACH)協(xié)議是典型的采用均勻分簇來提高網(wǎng)絡(luò)生命周期的算法，在該協(xié)議中，簇和Sink之間以單跳方式傳輸，造成遠(yuǎn)離Sink 的節(jié)點由于發(fā)送數(shù)據(jù)能量消耗過大而迅速死亡。而在使用多跳分簇傳感器網(wǎng)中，距離Sink 點越近的簇頭因轉(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］相同方法，在多跳非均勻分簇時考慮了距離和能耗因素，但仍然無法完全解決能量空洞的問題。

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

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

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

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

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

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

2 CMA 設(shè)計

2.1 Sink 移動半徑選擇

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

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

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

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

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

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

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

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

2.2 簇的形成

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

2.3 RP 選取

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

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

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

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

3 CMA 仿真實驗

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

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

3.1 Sink 運動速率對性能的影響

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

圖3 Sink 運動速度的影響Fig 3 Influence of sink moving speed

3.2 簇半徑對性能的影響

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

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

3.3 幾種算法性能對比

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

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

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

4 結(jié) 論

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

［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é)報，2012，23(5):1222-1232.

［6］ 張希偉，戴海鵬，徐力杰，等.無線傳感器網(wǎng)絡(luò)中移動協(xié)助的數(shù)據(jù)收集策略研究［J］.軟件學(xué)報，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.