基于分簇的移动协助无线传感器网络路由协议*

兰恒武，彭 舰，刘 唐，2

(1.四川大学 计算机学院，四川 成都610065;2.四川师范大学 基础教学学院，四川 成都610068)

0 引 言

无线传感器网络(wireless sensor networks，WSNs)近年来作为一种新的数据收集模式广泛用于战场搜救、环境监测、火灾应急、医疗监护等领域.典型的WSNs 是由低能耗、低成本、密集随机部署的传感器节点组成［1］。由于传感器节点部署后难再次充电，而且其通信能力和资源有限，如何有效地提高节点的网络生命周期是一个值得深入研究的课题。

文献［2］提出的低功耗自适应集簇分层型(low energy adaptive clustering hierarchy，LEACH)协议是典型的采用均匀分簇来提高网络生命周期的算法，在该协议中，簇和Sink之间以单跳方式传输，造成远离Sink 的节点由于发送数据能量消耗过大而迅速死亡。而在使用多跳分簇传感器网中，距离Sink 点越近的簇头因转发大量数据，造成簇头能量消耗增加而失效，这些现象被称为能量空洞［3］。文献［4］提出的非均匀分簇(unequal clustering，UC)算法，采用多跳非均匀分簇的路由算法来解决能量空洞，它的主要思想是通过平衡簇头之间的能量消耗来均衡网络总能量消耗。文献［5］提出的分布式能量均衡非均匀分簇(distributed energy-balanced unequal clustering，DEBUC)路由协议采用与文献［4］相同方法，在多跳非均匀分簇时考虑了距离和能耗因素，但仍然无法完全解决能量空洞的问题。

解决能量空洞的另一种方法是采用移动协助数据收集器直接访问传感器节点的数据策略［6］。在文献［7～9］中，移动数据收集器(mobile data collector，MDC)直接与传感器节点进行通信。文献［7］研究Sink 的路径规划问题，将遍历更多的传感器节点(更长的路径)问题转化为旅行商问题进行求解.文献［8］引入数据协助策略DMS，该策略主要包括路径选择、速度控制以及数据收集。文献［9，10］在方形网络中，Sink 直接移动到簇头通信范围，单跳收集簇头数据，利用混合整数规划来最大化网络寿命。显然，上述几种算法中利用单跳直接传递消息数据，能大大减少网络总的能量消耗，但在移动Sink 速度受限情况下，移动Sink 路径越长，网络的时延越大。

本文提出了一种基于分簇的移动协助(CMA)传感器网络中的路由协议，无线Sink 以恒定速率在圆形网络中做圆周运动，针对能量空洞现象，提出移动Sink 与多跳相结合来延长网络的生命周期的思想。本文在网络初始阶段，先确定移动Sink 的运动半径，将网络进行均匀分簇。在Sink 通信范围内确定一批普通节点作为汇聚节点，Sink 进行数据采集，仿真实验验证了CMA 路由协议的有效性。

1 网络模型

设定在一个半径为R 的圆形网络区域A 内［8］，存在N 个固定部署的普通传感器节点和移动Sink.各普通传感器节点均匀分布在A 内。如图1，假定该网络具有如下性质:

网络内的Sink 以移动基站形式部署，部署后沿固定轨迹做圆周运动，速度大小不变。Sink 节点的能量不受限制，发射功率可调。各个普通传感器节点类型相同，且所有节点和移动Sink 通信半径均为r，存储容量均为C，消息产生率λ。所有普通传感器节点通过GPS 或其他辅助设备知道自身位置，节点已知网络中心位置。

图1 网络模型Fig 1 Network model

2 CMA 设计

2.1 Sink 移动半径选择

本小节讨论移动Sink 做圆周运动的半径Rs，应用程序要求时延为Dr，满足:Tmin≤Dr≤Tmax，v 表示Sink 的运动速度，节点的密度为ρ。

定理1 网络的总能量消耗最小，Sink 的最优半径须满足

证明:如图1 所示，设接收1 跳距离的l bit 消息需消耗E0J。移动Sink 把整个网络区域划分成大于Rs的区域2 和小于Rs的区域1，对于区域2，在距O 为x、宽为dx 的圆环上，取夹角dθ 的一小段扇环，这一区域的节点个数期望为xdθ·dx·r。为使总能量最小，节点传送数据将沿最短路径传送消息给Sink，节点到Sink 的跳数近似为(x-L)/r，那么上述区域节点传输到Sink 的能耗为。综上，区域2 的总能量为

同理，当x ＜Rs时，区域1 的总能量为

综上，网络总的能量消耗为

对公式(6)求导，可得

公式(7)得出网络总消耗的最小能量，且还需满足

若应用要求时延满足定理1，则以上述半径作为移动Sink 的运动半径;否则，Rs应为

2.2 簇的形成

Sink 随机选取候选簇头，并以相同的竞争半径参加竞选，在候选簇头交叠区域，选取剩余能量最大的候选簇头作为簇头，其他节点根据接收到信号强弱选择加入最近的簇。

2.3 RP 选取

RP 节点的选取由移动Sink 统一选取。RP 的选取策略，是移动Sink 从通信范围内选取任意普通节点作为候选RP 节点j(j=1，2，…，ncp)，不在Sink 单跳通信范围内的簇头节点i(i=1，2，…，nm)作为子RP 路由节点，设k 为RP 节点的个数，显然，有

2.4 数据采集

簇形成时，普通成员节点将消息数据发送给簇头节点，簇头接收并融合处理消息数据，然后进行簇间路由。簇间路由时，对任意簇头i，若在Sink 单跳范围内，则等待Sink 运动到其通信范围内直接与移动Sink 通信;否则，需要转发。簇头i 沿最短路径传递消息给与其对应RP 节点，如图2 所示。

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

3 CMA 仿真实验

本文在Matlab 环境下进行仿真，讨论了不同参数变化(Sink 的运动速率、簇半径)，对CMA 算法的性能影响，最后仿真实现了CMA，LEACH，DEBUC 3 种算法性能对比。如表1，所有参数值均匀分布在表中对应参数取值范围内。

表1 模拟参数Tab 1 Simulation parameters

3.1 Sink 运动速率对性能的影响

本节实验研究其他参数不变情况下Sink 运动速率对CMA 算法性能的影响。由于所有节点剩余能量均较低，故统计总剩余能量.仿真结果如图3 所示。当Sink 运动速率增大，网络时延不变时，可由公式(9)推导出移动Sink 的运动半径增加。图3(a)可以看出:CMA 算法平均簇头数目变化相对较小，这是由于均匀分簇且簇半径保持不变;图3(b)，(c)表明，随速率增加Sink 的运动半径逐渐到达最优取值160m，CMA 算法的生命周期有一定的增加，总剩余能量逐渐减少，反映出CMA 有较高的能量利用率。

图3 Sink 运动速度的影响Fig 3 Influence of sink moving speed

3.2 簇半径对性能的影响

本组实验研究CMA 分簇时不同簇半径情况下，CMA算法的性能变化，结果如图4 所示。图4(a)表明:CMA 算法由于簇半径增加平均簇头数目有所减少，图4(b)显示，随簇半径增加，簇内能量消耗增加，网络的生命周期减小，因此，网络最优簇半径在20 m 左右。图4(c)随节点簇半径改变，总剩余能量变化，由图4(c)，(b)得出节点的能量得到较优利用，总剩余能量有一定增加，由于簇半径增加，簇内能量消耗增大，总剩余能量减少，网络生命周期也减少。

图4 簇半径对CMA 算法的影响Fig 4 Influence of cluster radius on CMA algorithm

3.3 几种算法性能对比

在各参数取表1，速率3 m/s，簇半径60 m，应用程序时延要求为400 ～800 s。普通传感器节点总数1 600 个情况下，CMA，LEACH，DEBUC 3 种算法性能对比仿真结果如图5所示。

图5 CMA 算法与其他算法对比Fig 5 Comparison of CMA and other algorithms

图5 (a)是统计簇头数目出现次数.DEBUC 与CMA 簇头数目更加稳定，是由于LEACH 随机选择簇头。图5(b)显示了几种算法生命周期(存活节点数目)随轮数变化曲线。由于DEBUC 算法使用非均匀分簇有效平衡了能量消耗，比LEACH 算法更优，故结果与DEBUC 算法相当，低于CMA 的生命周期。图5(c)比较了3 种算法网络总能耗，DEBUC 分簇比LEACH 能量消耗较少，由于DEBUC 算法更多的考虑能量和距离因素。CMA 算法由于采用移动Sink和RP 节点作为数据缓存因而生命周期更长和最低的能量消耗。

4 结 论

本文提出了一种CMA 算法，Sink 以恒定速率在圆形网络中做圆周运动，在网络初始阶段，先确定移动Sink 的运动半径，将网络进行均匀分簇。在Sink 通信范围内确定一批普通节点作为Rp，Sink 进行数据采集。计算了在圆形网络中受到应用时延和能量最优限制的Sink 运动半径，并结合分簇和移动Sink 来优化网络寿命。仿真实验验证了该方法的有效性。

［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.