蘭恒武，彭 艦，劉 唐，2

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

0 引 言

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

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

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

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

1 網絡模型

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

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

圖1 網絡模型Fig 1 Network model

2 CMA 設計

2.1 Sink 移動半徑選擇

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

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

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

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

綜上，網絡總的能量消耗為

對公式(6)求導，可得

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

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

2.2 簇的形成

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

2.3 RP 選取

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

2.4 數據采集

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

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

3 CMA 仿真實驗

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

表1 模擬參數Tab 1 Simulation parameters

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

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

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

3.2 簇半徑對性能的影響

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

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

3.3 幾種算法性能對比

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

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

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

4 結 論

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

［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］ 蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網絡非均勻分簇路由協議［J］.軟件學報，2012，23(5):1222-1232.

［6］ 張希偉，戴海鵬，徐力杰，等.無線傳感器網絡中移動協助的數據收集策略研究［J］.軟件學報，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.