一种无线传感器网络分簇路由算法分析

郑州旅游职业学院　王桂凤　王小会

一种无线传感器网络分簇路由算法分析

郑州旅游职业学院王桂凤王小会

摘要：本文根据候选簇头到SINK的距离将网络划分成大小不等的簇,在每个簇内以节点的剩余能量作为重要参数最终选择出簇头；其次,在簇间采用多跳路由的方式,利用改进的Dijkstra算法求解每个簇头节点到SINK的最短路径,使得离基站较远的簇头节点沿着最短路径传输信息。

关键词：无线传感器；分簇

中图分类号：TP393

文献标识码：A

文章编号：1671-864X（2015）03-0198-01

作为一种新的信息处理模式和信息获取方式，WSN引起了全世界研究学者的广泛关注。路由技术是WSN比较重要的核心技术，对WSN的发展起着关键作用。由于分簇路由能够有效进行网内数据融合，减少冗余数据量，延长网络生命周期，己经成为WSN的热门研究领域。

一、算法的执行步骤

该算法的执行过程分为三个阶段：簇的形成阶段，簇间路由建立阶段和数据传输阶段。

(一)簇的形成阶段

WSN部署完成之后，初始化网络参数。SINK以给定的发送功率向网络内广播一个“HELLO”信号，每个传感器节点在收到此信号后，依据接收信号的强度计算出它到SINK的近似距离。然后，依据节点的剩余能量选择部分节点作为候选簇头(tentative_cluster_head)，tentative_cluster_head根据自身到SINK的距离计算它的竞争区域，区域的竞争半径记作Rc。每个tentative_cluster_head以Rc为半径建立大小不等的簇。每个tentative_cluster_head以Rc为半径广播竞争簇头的消息，假如si为tentative_cluster_head，那么以Rc为半径的圆内的候选簇头组成集合si.CH。在该面积内选择剩余能量Ecurrent最多的tentative_cluster_head作为最终簇头(final_cluster_head)。如果有多个最大能量相同的tentative_cluster_head，选择ID号最小的tentative_cluster_head作为final_cluster_head。然后删除此面积内的其他tentative_cluster_head，最后final_cluster_head以2Rc为半径广播成为簇头的消息。簇头选择过程结束。网络中的非簇头节点则根据自己到各个簇头的距离(选择距离最近的簇头)来选择它要加入的簇，并告知相应的簇头。簇划分完成。

(二)簇间路由建立阶段

簇建立完成之后，在每个簇头节点上运行改进的Dijkstra算法，寻找簇头到SINK的最短路径，运行完成后每个簇头节点都保存一张到达SINK的最短路径信息表。当簇头节点要与SINK进行通讯时，将沿着最短路径进行数据传输。

(三)数据传输阶段

簇成员节点将收集的数据在自己的时隙内发送给簇头节点，簇头将收到的所有数据进行融合处理，然后沿着最短路径将数据发送到SINK。每轮数据传输结束后，簇头节点检测自己的Ecurrent。当Ecurrent＜ECH，进入下一轮循环，重新进行网络划分。

二、算法分析

该算法以整个传感器网络为出发点，从多个角度考虑如何平衡节点的能量消耗问题。该算法是一个分布式动态算法，簇的建立阶段在采用大小不等的分簇思想的基础上，融入了节点的能量因素，即在邻居候选簇头集合中以节点的Ecurrent为主要依据来选择最终簇头。在簇间多跳路由中，用改进的Dijkstra算法寻找各簇头节点到SINK的最短路径，相当于给每个簇头节点创建了一条通往SINK的能量消耗最少的路径，当簇头节点要发送数据到SINK时，将沿着该路径进行传输。本算法具有以下特点：

(一)在最终簇头节点的选举过程中，尽可能的选择能量大的节点作为簇头，有效的延长网络的生存周期。

(二)在簇的建立过程中，采用大小不等的分簇思想，使得距离SINK较近的簇头覆盖的面积较小，从而减少簇头在管理簇内成员节点时的能量消耗，节省的能量用来中继转发，有效的解决路由中的“热区”问题，平衡簇头节点之间的能量消耗。

(三)该算法是分布式的，簇头的产生通过局部竞争，无需迭代，保证算法的快速收敛性和较好的伸缩性。

(四)簇间路由采用多跳通信方式，避免了远离SINK的簇头与SINK直接通信，并综合考虑中继簇头之间的距离，根据预先设置的权值进行路径选择，有效的平衡簇头节点的能量消耗。

三、算法的消息复杂度分析

(一)在监测区域内，DEUC算法的消息复杂度为O(N)。

首先，在算法开始时，SINK向全网广播一条“HELLO”消息给每个节点。其次，大概有N×T(n)个参与竞争的tentative_cluster_head节点，共广播N×T(n)条参与的消息com_head_msg，最终每个tentative_cluster_head广播一条成功竞选的消息final_head_msg，或者宣布退出竞选的消息quit_com_head _msg。假设共有X个tentative_cluster_head成为最终簇头final_head，每个簇头广播一条head_msg，共有X条消息，则有N-X条join_ cluster_ head_msg的消息。因此整个网络的消息总开销大概为：

1+N×T（n)+X+N-X=1+2N×T+N=2(T+1)N+1

所以消息复杂度为O(N)，说明本算法开销小，能量高效。

(二)阈值T(n)决定算法中参与竞争的tentative_cluster_head的个数，从而影响算法的消息开销。

阈值T(n)选择的合适与否，直接影响参与竞争的候选簇头的多少。如果T(n)的取值偏小的话，将直接导致参与竞争的tentative_cluster_head数量变少，使得很多能量较高的节点不能参与竞争，从而影响簇头的选举质量，最终导致整个网络的性能。相反，如果T(n)过大，将大大影响算法的消息开销，也会使得整个网络能量开销过大，影响网络生存时间。所以T (n)的取值对延长网络生存时间来说，也起到非常重要的作用。

四、结论

本算法之所以优于其它算法，其原因主要有以下几点：①因为传感器网络节点之间，即成员节点与簇头、簇头与簇头和簇头与SINK之间的距离不会太大，因此节点之间的通信只需要遵循自由空间(freespace)模型，避免采用多路衰减模型。②网络分成大小不等的簇，使得距离SINK越近的簇头节点拥有的成员节点越少，这样，可以减少靠近SINK的簇头节点的簇内通信能耗，以达到平衡整个网络中簇头节点能量消耗的目的。③簇间采用多跳通信方式，网络中以簇头节点为骨干网建立簇头到SINK的最短路径，簇头沿着最短路径将融合后的数据发送到SINK。④本协议具有很好的扩展性。

参考文献：

[1]刘琴，王福豹，马峻岩等.无线传感器网络中一种有效的分布式簇划分算法[J].计算机应用，2007，27（1）∶4-6.

[2]王桂凤.无线传感器网络智能分簇路由算法研究[D].桂林：桂林电子科技大学，2010.

[3]刘琴，王福豹，马峻岩等.无线传感器网络中一种有效的分布式簇划分算法[J].计算机应用，2007，27（1）∶4-6.