论文部分内容阅读
中图分类号：TP393 文献标识码：A摘要：本文根据候选簇头到SINK的距离将网络划分成大小不等的簇，在每个簇内以节点的剩余能量作为重要参数最终选择出簇头；其次，在簇间采用多跳路由的方式，利用改进的Dijkstra算法求解每个簇头节点到SINK的最短路径，使得离基站较远的簇头节点沿着最短路径传输信息。
关键词：无线传感器；分簇作为一种新的信息处理模式和信息获取方式，WSN引起了全世界研究学者的广泛关注。路由技术是WSN比较重要的核心技术，对WSN的发展起着关键作用。由于分簇路由能够有效进行网内数据融合，减少冗余数据量，延长网络生命周期，己经成为WSN的热门研究领域。
一、算法的基本思想
在采用分簇结构的WSN中，簇头是最重要的节点。它不仅要管理簇内成员节点，协调其成员节点按照一定的顺序进行数据传输，还要将收集到的成员节点数据进行融合，最后将融合后的数据发送给SINK。由于簇头节点的责任较大、负担较重，因此，本算法采用周期性轮换方法，在每一轮开始时，首先考虑所选簇头节点的状态，之后在成员节点加入某个簇时，考虑所加入簇的簇头节点剩余能量。
(一) 将网络划分成大小不等的簇。由于距离SINK节点越近的簇头节点所承担的数据转发任务越重，所消耗的能量就越大。因此，只有减少距离SINK节点较近的簇头节点的簇内能量消耗，才能使簇头节点有更多的能量来进行数据转发工作，从而解决平衡整个网络簇头节点能量消耗问题。
(二) 采用数据融合的思想，簇内成员节点仅与簇头节点通信，簇头节点将收集的数据进行融合处理后，以多跳的方式传输到SINK。
(三) 簇内通信采用TDMA方式。为了避免簇内数据传输时发生冲突，簇结构建立后，簇头节点创建TDMA时间表，为每个簇成员节点分配时隙，簇成员节点只有在自己的时隙内进行数据发送，而在其它时隙内节点关闭无线收发器，以节省能量。
(四) 在簇间路由过程中，当簇头节点将本簇内数据进行融合处理后，只需将数据传输到距离它最近的相邻簇头节点，并且该相邻簇头节点比自己距离SINK更近。
二、算法的执行步骤
该算法的执行过程分为三个阶段：簇的形成阶段，簇间路由建立阶段和数据传输阶段。
(一)簇的形成阶段
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 三、算法分析
该算法以整个传感器网络为出发点，从多个角度考虑如何平衡节点的能量消耗问题。该算法是一个分布式动态算法，簇的建立阶段在采用大小不等的分簇思想的基础上，融入了节点的能量因素，即在邻居候选簇头集合中以节点的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）+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.
关键词：无线传感器；分簇作为一种新的信息处理模式和信息获取方式，WSN引起了全世界研究学者的广泛关注。路由技术是WSN比较重要的核心技术，对WSN的发展起着关键作用。由于分簇路由能够有效进行网内数据融合，减少冗余数据量，延长网络生命周期，己经成为WSN的热门研究领域。
一、算法的基本思想
在采用分簇结构的WSN中，簇头是最重要的节点。它不仅要管理簇内成员节点，协调其成员节点按照一定的顺序进行数据传输，还要将收集到的成员节点数据进行融合，最后将融合后的数据发送给SINK。由于簇头节点的责任较大、负担较重，因此，本算法采用周期性轮换方法，在每一轮开始时，首先考虑所选簇头节点的状态，之后在成员节点加入某个簇时，考虑所加入簇的簇头节点剩余能量。
(一) 将网络划分成大小不等的簇。由于距离SINK节点越近的簇头节点所承担的数据转发任务越重，所消耗的能量就越大。因此，只有减少距离SINK节点较近的簇头节点的簇内能量消耗，才能使簇头节点有更多的能量来进行数据转发工作，从而解决平衡整个网络簇头节点能量消耗问题。
(二) 采用数据融合的思想，簇内成员节点仅与簇头节点通信，簇头节点将收集的数据进行融合处理后，以多跳的方式传输到SINK。
(三) 簇内通信采用TDMA方式。为了避免簇内数据传输时发生冲突，簇结构建立后，簇头节点创建TDMA时间表，为每个簇成员节点分配时隙，簇成员节点只有在自己的时隙内进行数据发送，而在其它时隙内节点关闭无线收发器，以节省能量。
(四) 在簇间路由过程中，当簇头节点将本簇内数据进行融合处理后，只需将数据传输到距离它最近的相邻簇头节点，并且该相邻簇头节点比自己距离SINK更近。
二、算法的执行步骤
该算法的执行过程分为三个阶段：簇的形成阶段，簇间路由建立阶段和数据传输阶段。
(一)簇的形成阶段
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
该算法以整个传感器网络为出发点，从多个角度考虑如何平衡节点的能量消耗问题。该算法是一个分布式动态算法，簇的建立阶段在采用大小不等的分簇思想的基础上，融入了节点的能量因素，即在邻居候选簇头集合中以节点的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）+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.