[基于聚合度的WSN分簇优化算法研究]组合优化算法研究综述

　　摘 要 针对无线传感器网络分簇问题，引入节点聚合度概念，以节点能量的均衡消耗为目标，提出一种有效簇头数优化方法，并设计出均衡网络负载的簇首动态更新和簇重组机制，进一步地优化分簇。算法包括基于能量消耗的有效簇头数计算，聚合度最大的簇首选举和簇建立，以及均衡网络负载的簇首动态更新和簇重组。仿真结果表明，算法能有效延长网络寿命，均衡网络消耗。
　　关键词 无线传感器网络; 分簇;节点聚合度;有效簇头数；优化分簇
　　中图分类号 TP393 文献标识码 A
　　
　　Research on Convergence Degree-based Cluster Optimized Algorithm of Wireless Sensor Network
　　HAN Gang1 YANG Hua2 YANG Liang2 ZHOU Rui2
　　 1(School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China)
　　 2(School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China)
　　【Abstract 】 As for the problem of wireless sensor network clustering, based on the balanced energy consumption, a optimized method of effective number cluster was proposed, which uses convergence degree concept during the foundation of cluster head. The mechanism of dynamic updating cluster head and cluster rebuilding was designed, which balances network load and optimizes cluster much better. It mainly contains the calculation of effective number cluster, the election of cluster head, cluster building, cluster head dynamic updating and cluster rebuilding. The simulation shows that new algorithm can prolong the lifetime of network and balance energy consumption.
　　【Key words】wireless sensor network; clustered; convergence degree; effective clusters; optimized cluster
　　
　　0 引 言
　　无线传感器网络具有可靠、低廉、易于部署等特性,因而具有非常广阔的应用前景,能够广泛应用于军事国防、环境监测、智能家居、城市管理等的安全监测等领域[1,2,3]。由于有限的计算、存储和通信能力，尤其是严重受限的能量使其应用前景面临巨大的挑战[4]。而数据路由是无线传感器网络在各种应用的基础，其能耗也是网络总能量消耗的主要部分，因此设计一种有效的数据路由协议是关键[5]。
　　同一感知区域内不同节点感知的数据有一定冗余性，若将每个节点感知到的数据直接发送到Sink节点, 不仅毫无必要, 而且会产生大量的通信数据包, 浪费网络资源。基于分簇的逻辑网络结构将网络分成不同的逻辑簇, 每个簇有一个簇头, 由簇头对簇内成员节点的感知数据进行融合[6], 并由簇头作为Sink节点的代理, 对簇的成员进行管理。将网络有效的分簇是无线传感器网络的一个重要研究内容。本文在基于聚合度成簇算法的基础上[7]，以节点能量的均衡消耗为目标，提出一种有效簇头数优化理论，并计簇首动态更新和簇重组机制，更进一步地优化分簇。
　　1 网络模型
　　本文假设无线传感器节点随机、均匀地分布在一个二维方形区域，该传感器网络具有以下性质：
　　(1)网络里所有节点完全相同并且能量非常有限；
　　(2)无线传感器网络是静态网络，节点部署后不再移动；
　　(3)Sink节点是固定的，并且离整个无线传感器网络较远；
　　(4) 无线电信号在各个方向上能量消耗相同。
　　定义1(无向连通图) 无线传感器网络可用无向连通图表示。设图 , 称为无向连通图当且仅当 中任意两个节点之间最多有1条边。
　　定义2(相邻节点) 无线传感器网络中每个节点具有相同的通信半径，即具有相等的通信距离，如果两个节点处于彼此的通信半径之内，同时彼此之间存在一条通信链路，则称这两个节点是相邻节点。
　　定义3(状态集) 在任意时刻， ， 处于下列状态：status = {idle, c_head, c_member}其中，idle表示节点处于独立状态；c_head 表示节点处于某个簇中，且作为簇首；c_memeber 表示节点处于某个簇中，且作为簇成员。
　　2 基于节点聚合度的路由算法设计
　　用无向连通图 表示传感器网络，在网络中选出某些节点作为簇首，相当于在网络图中选取该节点所构成逻辑图的最大覆盖。目前提出的有最小ID算法(LID)和最大连通度算法(MAXD)。LID算法是有ID最小的节点为簇首，MAXD算法是选择连通度最大的节点为簇首，但这两种算法都不能保证合理、最佳的簇头数目。本文提出基于聚合度算法是根据节点和其邻居节点组成子网的密切联系程度，以最佳簇头数为优化，并结合簇首动态更新和簇重组机制，更进一步地均衡网络消耗，延长网络寿命。
　　2.1聚合度最大的簇首选举
　　在网络图 中，假设 属于 ，用 表示节点 的一跳邻节点集。如果 属于 当且仅当 属于 ，则节点 聚合度为节点 和其一跳邻节点组成子图 , 是子图 的度与节点总数的比值，即节点 的聚合度。该值表示子图 中节点间联系的密切程度, 越大，子图 中节点之间联系越紧密，按照子图 建立的簇结构越稳定。
　　算法选取节点中聚合度较大且能量充足的节点作为簇首节点。节点之间通过交互消息获知邻节点信息，反复进行直到获得所有 节点的 和其聚合度。设定能量阈值 ，目的是保证簇首总是有充足的能量，同时确保簇内节点能量均衡消耗。聚合度最大的节点查看自身能量，如果自身能量 超过阈值 ，则宣布成为簇首，否则聚合度次大且能量超过阈值的节点宣布成为簇首，依此类推。簇首节点将自身状态设为c_head且发布消息，其邻节点收到建簇消息后加入该簇。
　　2.1.1获取邻节点信息过程
　　在该阶段，节点主动广播其 和当前所知邻节点 ，根据本文的网络模型，所有的一跳邻节点都会收到该信息。其邻节点收到该信息后，更新自己的邻节点表，标记互相连接的一跳邻节点，并准备将自己 和当前所知邻节点 发送出去。当子图 所有节点都发送一遍信息后，则每个节点可以知道所有处于idle状态的一跳邻节点和它们之间的互相连接情况。
　　While (channel is free&&no out of time)
　　{ if (receive the node of q’s broadcasting message)
　　 {Neighbor_Table: update, ;
　　While( v == Neighbor_Table: )
　　{ if ( v== Neighbor_Table: )
　　{ Neighbor_Table record}
　　else{ do nothing；}
　　}
　　}
　　if (channel is free &&no the nodes’ broadcasting message)
　　{ broadcast(my_id, Neighbor_Table)}
　　}
　　2.1.2基于能量消耗的簇头数计算
　　由一阶无线电模式（first order radio model)[12]能量消耗公式知，传感器节点发送 bit数据所消耗的能量为:
　　其中， 是信号放大器的放大倍数。 是发送电路和接收电路消耗的能量，由于实际相差不大，在这个模式里面简化为两者相等。而 是由无线电通道决定的常量,在发送距离较近时，适用自由空间信道模型，取 。 是信号传输的距离。
　　由文献[10]可知， 最小的 值即为有效簇头数。
　　2.1.3节点聚合度的计算
　　根据第3.1.1阶段获得的邻居节点连接信息并结合第3.1.2阶段获得的有效簇头数目，节点获得其所有一跳邻节点 和它们之间的互连情况。按照聚合度计算公式计算出任意节点 的聚合度 ，开始广播其聚合度值，告知所有邻节点。
　　以图1的网络拓扑结构为例，由聚合度计算公式计算出图中的节点聚合度。节点A和邻居节点{B,C,D,E}构成的子图 中有5个节点{A,B,C,D,E}和六条边{(A,B),(A,C),(A,D),(A,E),(B,C),(D,E)},则其聚合度为 。依次算出网络拓扑图中各节点的聚合度，按照聚合度成簇后的拓扑图如图2
　　各节点的聚合度值如表1所示:
　　2.2簇建立算法
　　节点获得所有邻节点的聚合度，若本节点聚合度最大，查看本节点的能量状况，如果本身能量 高于能量阈值 ，则广播Head_Msg消息，宣布自己为头节点，建立簇，同时自身状态设为c_head；收到该消息的节点，如果还未加入任何簇，则发布Join_Msg消息宣布加入该簇，自身状态设为c_member。如果聚合度最大节点的能量低于阈值，则将聚簇权力让给聚合度次大的节点来执行，自身监听信道置于监听状态，准备接收Head_Msg消息，成为簇成员。
　　2.3均衡网络负载的簇首动态更新与簇重组
　　成簇过程结束后，所有节点处于c_head或c_member状态，即节点成为簇首或簇成员状态。成为簇首的节点接收簇成员感知数据，并同自身感知的数据一起分析比较，在数据融合的基础上，将信息进一步发送给 Sink节点或其他簇首。
　　由于簇首不仅像其他节点一样具有数据转发(簇间转发或转发给Sink节点)功能，还肩负着簇内数据融合功能，因此其能量消耗必然比其他普通节点高，即簇首会早于其他节点死亡。簇首的死亡意味着簇的死亡，将会导致整个簇内的簇组织关系同时失效，即簇解散。所以为了延长簇的生存周期，本文采用簇首动态更新方式，以均衡网络负载，达到提高网络整体寿命。簇首动态更新从簇首能量降低到一定程度时开始，其基本过程如下：
　　while(c_head)
　　{ broadcast(Msg_heart);
　　if(c_head_energy= )
　　 {broadcast(Head_Msg); }
　　}
　　}
　　3 算法分析与仿真
　　3.1 算法分析
　　基于聚合度的成簇算法选择聚合度最大并能量充足的节点作为簇节点，簇的稳定性比较高，在簇头节点出现故障时，不会引起大规模的簇重组，从而降低网络管理费用。算法属于分布式算法，时间复杂度为 .
　　证明：在节点信息获取阶段， 个节点广播其 和当前所知邻居节点。然后在簇建立阶段，假设由最佳簇头数计算出的簇头数为 ，则他们广播 条Head_Msg消息，而 个簇成员广播 条Join_Msg消息。因此网络中总的开销为： .所以时间复杂度为 。
　　3.2 算法仿真
　　模拟实验环境是监测区域范围为 ，随机部署节点总数为 ，Sink点的坐标位置为 ,由2.1.2的有效簇头数理论计算公式 计算出有效簇头数 。模拟实验参数见表2.
　　根据以上实验参数对其进行1500轮仿真，对网络能耗进行评估，图4中横坐标表示网络工作轮数，纵坐标表示剩余节点数目，分簇优化算法与Leach协议的节点存活个数做比较。
　　根据仿真结果，Leach算法在350轮的时候出现节点死亡，而分簇优化算法在720轮才开始出现死亡节点，网络寿命比Leach算法延长了约50%。仿真图显示，Leach算法在970轮时存活节点数已经为0，而此时分簇优化算法的网络中尚有75个节点存活。更直观地显示Leach算法的整个网络死亡速度比分簇优化算法要快，因此，本文提出的基于聚合度的分簇优化算法更好地均衡网络能耗，延长网络寿命。
　　4 结论
　　针对无线传感器网络分簇问题，本文引入节点聚合度概念，根据节点和其邻居节点组成子网的密切联系程度，以节点能量的均衡消耗为目标，优化簇头选举的数目，并设计簇首动态更新和簇重组机制，更进一步地优化分簇。仿真结果表明，该算法有效延长网络寿命，均衡网络消耗。
　　参考文献
　　[1] Akyildiz LF,Su WL,Sankarasubramaniam Y, et al. A Survey on Sensor Networks[ J ]. IEEE Communications Magazine, 2002, 40 (8) : 102-114.
　　[2] Chee-Yee Chong, Spikanta P Kumar. Sensor Networks: Evolution, Opportunities, and Challenges [ J ]. Proceedings of the IEEE, 2003, 19 (8) : 1247-1256.
　　[3] 孙利民,李波,周新运.无线传感器网络的拥塞控制技术[J].计算机研究与发展,2008,41(5):63-72.
　　[4] 王换招,孟凡志,李增智.高效节能的无线传感器网络覆盖保持协议[J].软件学报,2010,21(12):3124-3137.
　　[5] Sokwoo Rhee, Deva Seetharam, Sheng Liu, Ningya Wang,JasonXiao.I-Benas: An Ultra-low Power Wireless Sensor Network.
　　[6] XU Y，BIEN S. Topology Control Protocols to Conserve Energy in Wireless Ad hoc Networks[ R]. T echnical Report 6, Univers ity of California, Los Angeles, Center for Embedded Networked Computing, 2003
　　[7] 孙亭,芦东昕,杨永田.基于图论聚合度的动态分层路由算法[J].计算机工程,2008,34(7):23-25.
　　[8] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy Efficient Communication Protocol for Wireless Microsensor Networks [ C ]. Maui: IEEE Computer Society, Proceedings of the 33rd Hawaii International Conference on System Sciences, 2000. 3005-3014.
　　[9] Seema Bandyopadyay,Coyle E J.An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks[C].Infocom 2003,the 22nd Annual Joint Conference of the IEEE Computer and Communication Societies,IEEE,2003,1713-1723.
　　[10] Demirbas M,Arora A,Mittal V,et al.Design and Analysis of a Fast Local Clustering Service for Wireless Sensor Networks[C].Broadband Networks, the 1st International Conference,2004.700-709
　　[11] Yingyue Xu,Hairong Qi.Decentralized Reactive Clustering for Collaborative Processing in Sensor Networks[C].Parallel and D istributed Systems,ICPADS 2004.Proceedings of the 10th International Conference,2004.54-61
　　[12] Heinzelman W,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks.In:IEEE Transaction on Wireless Communications,2002,(10):660-670.
　　5 作者简介
　　作者简介: 韩刚(1989－),男,本科在读,主要研究领域为无线传感器网络;杨华(1989－),男,本科在读,主要研究领域为无线传感网;杨亮(1989－),男,本科在读,主要研究领域为无线传感网.
　　基金项目：国家大学生科研创新计划资助项目(CUMT101029023)

推荐访问:算法 聚合 优化 基于聚合度的WSN分簇优化算法研究 基于蚁群算法的车辆调度研究优化 车辆调度多目标优化