基于双重选举机制的无线传感器网络分簇算法*

孙中皋 郑紫微 许少娟

(1.大连海事大学信息科学技术学院，辽宁大连116026;2.辽宁师范大学物理与电子技术学院，辽宁大连116029;3.宁波大学信息科学与工程学院，浙江宁波315211;4.大连理工大学城市学院，辽宁大连116600)

在无线传感器网络中，传感器节点部署比较密集，邻近节点采集到的数据具有较大的相关性，节点可以通过收集邻近节点的数据并进行融合［1］来减少冗余数据，从而降低数据采集的能耗.利用这一特性，人们提出了大量的分簇算法以提高网络的能量效率.分簇的基本思想是将网络中的节点划分为簇头节点和簇成员节点，簇头节点负责收集簇内成员节点的数据并进行融合处理后发送至远方的基站.分簇算法的有效性很大程度上取决于簇头节点的选取策略:(1)因簇头节点的能耗远大于簇成员节点的能耗，若簇头节点选取不当，则容易导致其电池能量过早耗尽而使网络失效，故选取簇头节点时要考虑节点的能量和能耗;(2)传感器节点的无线通信能耗远大于传感和数据处理时消耗的能量［2］，所以簇头节点的选取过程要减少消息通信的数量.

LEACH算法［3］是具有代表性的分簇算法，其簇头节点的选取方法具有随机性且没有考虑节点的剩余能量.在其它众多分簇算法中［4-11］，簇头节点的选取方法不仅考虑了节点的剩余能量，还将网络局部范围内节点的其它属性信息作为簇头节点选举的依据，如节点度［4，6］、节点聚合度［5］、通信代价［6］和两跳范围内节点的拓扑信息［7］等.文献［6］中提出的HEED算法，在选举簇头节点时首先以节点剩余能量作为主参数选取出候选簇头节点，然后以簇内通信代价或度作为次参数，通过多次迭代来选取簇头节点.文献［8］中提出的基于投票机制的分簇算法(VCA)，节点依据剩余能量信息给邻居节点及自身投票，通过迭代选取票数高的节点为簇头节点.HEED算法和VCA在迭代过程中节点与邻居节点的消息交换消耗了额外的能量.基于定时驱动机制的分簇算法［9-11］则避免了迭代过程，减少了消息开销.文献［10］中提出的基于定时驱动的分簇算法，节点按照负指数分布生成一个定时长度用于竞争簇头节点，剩余能量较多的节点成为簇头节点的机会更大.文献［11］中提出的SWEET算法在簇头节点选举的两个阶段都采用了定时的方式.

结合投票机制考虑邻居节点信息的思想和定时驱动机制消息开销小的特点，文中提出了一种基于双重选举机制的分簇算法(DSMCA).投票选举机制中考虑了节点的剩余能量、节点间及节点与基站间的通信代价3个属性，节点所投票数取决于这3个属性的综合评价值，各属性的权重系数采用信息熵的方法求得.投票结束后，节点依据所得的总票数生成一个定时长度参与簇头节点的选举.

1 VCA

VCA认为在簇头节点选举中，节点除考虑自身的能量状态外还应考虑邻居节点的能量信息.节点si投给节点sj的票数为［8］

式中，ej为节点sj的剩余能量，dij为节点si到节点sj的距离，R为节点的通信半径.

VCA以节点的剩余能量为参数，而忽略了节点的相对位置信息，在选取高能量节点的同时可能会付出高的能耗代价.如图1所示，sj和sk为si的两个邻居节点，采用VCA投票，当sj和sk的剩余能量相等或较为接近时，si投给这两个节点的票数相当.因sk与si之间的距离以及sk与基站之间的距离都比sj近，si选取sk当选簇头节点的通信代价更小，故sk应比sj得到更多的票数.

图1 节点投票示例Fig.1 An example of node voting

2 DSMCA的双重选举机制

2.1 DSMCA的投票机制

DSMCA除考虑节点的剩余能量属性外，还引入了节点间的通信代价以及节点与基站间的通信代价两个属性，节点按照以下规则投票:(1)节点只给比自己剩余能量大的邻居节点投票;(2)节点所投出的总票数为1，投给某个节点的票数与该节点的综合属性评价值有关.

由规则(1)可知，节点的剩余能量越大，得到的票数越多而投出的票数越少;相反，节点的剩余能量越小，投出的票数越多而得到的票数越少.规则(1)减少了剩余能量小的节点当选簇头节点的机会，让剩余能量大的节点处于被选举状态而少投票，与VCA中节点给每个邻居节点投票相比，减少了消息开销.由规则(2)可知，一个具有较高剩余能量的节点，其邻居节点数越多，得到的票数越多，并且票数均衡了节点的能量和能耗因素.

基于投票规则，DSMCA的多属性投票模型为

式中，zj为节点sj的综合属性评价值，

m为属性个数，rjk为节点sj的第k个属性的规范化值，ωk为第k个属性的权重，满足

由式(2)、(3)可知，要计算票数，需先确定属性的规范化值，并为每个属性选择合适的权重.

2.1.1 属性规范化

设节点si拥有比自己剩余能量高的邻居节点集为S={s1，s2，…，sn}，每个节点的属性集为U={u1，u2，…，um}，用xk'l(1≤k'≤n，1≤l≤m)表示节点sk'关于属性ul的评价值，则节点si可建立集合S的多属性矩阵X:

由于不同属性的物理量纲互不相同，为了使各属性之间具有可比性，需要对属性矩阵进行规范化处理［12］.DSMCA采用比例转换法对各属性进行转换.对于效益型属性(如剩余能量)，采用式(6)进行规范化:

规范化后的属性矩阵R为

将R中的属性评价值代入式(3)，求得节点的综合属性评价值，就消除了属性量纲的差异性.

2.1.2 属性权重

熵在信息论中是不确定性和信息量的一个量度，其定义为［13］

式中，h为正常数，pi为一个离散的概率分布.熵值具有极值性，当所有的pi都相等，即等概率pi=1/n时，熵值E取得最大值.

多属性矩阵表述了节点的不同属性值，可以看作是信息的载体.而熵法是评价属性相对重要程度的一种有力工具［13］，其基本原理为:所有方案在某属性上的取值差异越大，则该属性向量提供的信息越多，该属性被赋予的权重也越大;与之相反，所有方案在某一属性上的取值越接近，则该属性对各方案所起的作用越小，所赋予的权重也越小.

DSMCA采用熵法求解权重，节点在投票时通过所有可投票节点的多属性矩阵衡量各属性的重要程度，从而决定各属性的权重.确定权重的步骤如下:

1)对于规范化后的属性矩阵R，计算属性ul的几何影射pk'l为

2)计算属性ul的熵El为

当pk'l=0时，令pk'llnpk'l=0.

3)计算属性ul的权重为

式(12)通过归一化处理，使权重满足式(4)的条件.

2.2 DSMCA的定时驱动机制

设节点完成投票后统计所得票数为vtotal，首先将票数转换为参与簇头节点竞争的初始定时长度:

式中:ε为一足够小的常数，当vtotal=0时，节点依据ε生成定时长度;x为在［0，1］上均匀分布的随机变量;vmax为一常数，表示节点可能得到的最大票数，若节点收到每个邻居节点的票数都为最大值1，则vmax等于节点所拥有的最大邻居节点数，vmax由节点的通信半径及网络中节点的分布密度决定.

接着节点设置定时器时间为

式(13)中，当vtotal≠0 时，令v=vtotal/vmax，则0 ＜v＜1，保证了tinitial＞0且tinitial关于v的一阶偏导数∂tinitial/∂v=-v-1＜ 0，即随着v的增大，tinitial单调递减，也就是说，节点所得的选票数越多，其生成的定时长度越短.

另外，由式(13)可知，节点的初始定时长度取决于节点得到的票数vtotal和随机变量x的取值，其中vtotal取决于邻居节点对节点多个属性的综合评价值，这使得在节点通信半径内存在与该节点具有相同票数的其它节点的概率很小，而且随机变量x进一步降低了相邻节点生成相同定时长度的可能性.所以，DSMCA降低了节点在竞争簇头节点时发生冲突的概率，在簇头节点的通信半径内只存在一个簇头节点，即簇头节点在网络中的分布相对均匀.

3DSMCA描述

3.1 网络初始化

网络初始化的主要任务是节点根据信号接收强度估算与发送方的距离，以便获取通信代价属性值及在数据传输时选取合适的发射功率.其中节点的通信代价属性定义为节点向接收方发送一个数据包所需要的能量.

为此，在网络部署完成后，首先由基站以一定功率向全网广播一个消息，每个节点根据该消息估算至基站的距离并计算自身至基站的通信代价.然后每个节点以一定的功率发送一个邻居发现消息与邻居节点进行消息交换，在这个过程中，节点计算与每个邻居节点间的通信代价，并获得邻居节点的剩余能量和至基站的通信代价属性值.网络初始化完成后，节点建立邻居节点信息表，保存各节点的属性值.

3.2 网络运行

在网络初始化之后，同大多数分簇算法一样，DSMCA采用轮方式运行的方案，每轮包括簇头节点选举、簇形成和数据传输3个阶段.

3.2.1 簇头节点选举阶段

簇头节点选举开始后，节点执行如下步骤:

1)查看邻居节点信息表，查找比自己剩余能量高的节点组成集合S，并建立多属性矩阵X.如果S=∅，说明该节点在所有邻居节点中剩余能量最大，节点直接进入接收投票的状态，并在投票过程结束后转步骤6).

2)由式(6)和(7)对X进行规范化处理，得到规范化属性矩阵R.

3)由式(12)计算各属性的权重系数.

4)由式(3)计算S中每个节点的综合属性评价值.

5)由式(2)计算S中每个节点的票数，然后节点随机生成一个退避时间，到时后首先竞争信道，若成功则发送一个投票消息完成给其它节点的投票，在此过程中接收其它节点给自己的投票.

6)节点统计最终所得票数，由式(13)生成初始定时长度，由式(14)设置定时器时间.

7)如果在ttimer时刻到达之前，节点没有收到任何邻居节点发出的簇头节点当选消息，则节点向所有邻居节点广播簇头节点当选消息，声明自己当选为簇头节点.所有收到当选消息的节点停止计时成为普通节点并记录相应簇头节点的ID.

3.2.2 簇形成阶段

簇头节点选举结束后，网络进入簇形成阶段.在该阶段，每个普通节点向簇头节点发送加入消息成为簇成员.普通节点在簇头节点选举阶段可能会收到多个簇头节点发送的当选消息，此时，节点比较自己给每个簇头节点所投的票数，向票数最高的簇头节点发送加入消息.综合属性值大的簇头节点形成的簇规模大于综合属性值小的簇头节点，从而降低综合属性值小的簇头节点的负担，避免其过早失效.

在成簇过程中，如果一个簇头节点存在邻居节点，但其所有邻居节点都选择加入了其它簇，则该簇没有簇成员加入，形成单节点簇，文献［10］中将其称为被动型簇头节点.VCA和文献［10］中的算法让被动型簇头节点直接向基站发送自身数据，显然浪费了节点的能量.DSMCA采取多跳中继方式，当节点成为被动型簇头节点后，在邻居节点中选取剩余能量最大的节点作为中继节点并发送中继消息通知被选节点.

3.2.3 数据传输阶段

由于网络中可能存在被动型簇头节点，所以在数据传输阶段，首先由被动型簇头节点将数据发送给中继节点，然后各成员节点在簇头节点分配的时分多址(TDMA)时隙内将数据发送给簇头节点，簇头节点执行数据融合后向基站发送一个数据包，即网络完成一个数据采集周期.为避免频繁的簇重组带来的能量开销，网络在多个数据采集周期后进行重新分簇［14］.

3.3 属性更新

节点在投票时需要邻居节点的剩余能量、节点与邻居节点间的通信代价以及邻居节点与基站间的通信代价3个属性值.在网络初始化阶段，节点通过信息交换建立了邻居节点属性信息表.假设网络部署后，节点和基站的位置不再发生改变，故通信代价属性在网络运行过程中不发生变化，无需进行更新.但随着时间的推移，节点的剩余能量会发生改变，这时需要节点之间定期交换剩余能量信息.DSMCA采取和VCA相同的方法:节点在每次簇重组开始前向邻居节点广播心跳信号，在确认邻居节点存活状态的同时，更新剩余能量属性信息［8］.

4 仿真实验和结果分析

文中通过仿真实验来评价DSMCA的性能，采用网络生命期(第一个节点失效的时间［15-16］)和数据传输效率来比较DSMCA、LEACH、HEED及VCA的性能，以验证DSMCA的有效性.实验中所用的参数设置如表1所示，采用和文献［3］中相同的无线通信能耗模型及参数.所有仿真均重复100次，取平均值作为最终结果.

表1 实验参数值Table 1 Values of simulation parameters

图2为采用4种算法的网络中存活节点数随时间变化的情况.从图2中可以看出，DSMCA的网络生命期比LEACH、HEED、VCA分别提高了260%、50%和37%.其原因主要有:(1)DSMCA的投票机制采用了邻居节点的多属性信息，均衡考虑了能量和能耗因素，节点综合属性评价值越大，所得票数越多，越有机会当选为簇头节点，而LEACH没有考虑节点的剩余能量信息，VCA只以节点的剩余能量信息为主参数;(2)DSMCA簇头节点选举采用了定时驱动方式，且节点只给剩余能量比自己大的节点投票，比采用迭代方式的HEED和VCA节省了大量消息开销;(3)DSMCA中的被动型簇头节点采取多跳的方式向基站传输数据，减少了节点能耗.由图2还可以看出，DSMCA从第一个节点失效到最后一个节点失效的时间跨度比其它3种算法更短，而时间跨度可反映出网络中节点的能量均衡情况［5］，所以DSMCA的能量使用效率最高，更好地均衡了网络中节点的能耗.

图2 存活节点数随时间的变化Fig.2 Changes of number of surviving nodes with time

图3给出了基站收到的数据包数和存活节点数的关系.从图3可见，与其它3种算法相比，DSMCA能够使基站接收到更多的数据信息.这是因为DSMCA的节点失效更为缓慢，能够采集并传送更多的数据.

图3 基站收到的数据包数与存活节点数的关系Fig.3 Relationship between number of data packets received at base station and number of surviving nodes

图4给出了基站收到的数据包数与网络能耗的关系.从图4可以看出，在能耗相同的情况下，采用DSMCA的基站可以收到更多的数据包，整个网络的能量使用效率更高.

图4 基站收到的数据包数与网络能耗的关系Fig.4 Relationship between number of data packets received at base station and energy consumption of network

5 结语

为了高效地利用无线传感器网络的能量，文中提出了一种基于双重选举机制的无线传感器网络分簇算法，该算法结合了投票选举和定时驱动两种分簇机制.票数的计算均衡考虑了能量和能耗因素，借鉴了多属性决策中求解多属性综合值的方法，采用熵法来计算属性的权重系数.节点将所得票数转换为一个定时长度参与簇头节点竞争，减少了消息开销.在数据传输阶段，被动型簇头节点采取多跳转发数据的方式，节省了节点的能量.实验表明，和已有的几种分簇算法相比，文中算法能更好地均衡节点能耗，延长了网络生存时间.今后将改进簇形成阶段的算法，使得簇头节点之间的负载更加均衡，进一步提高文中算法的性能.

［1］Fasolo E，Rossi M，Widmer J，et al.In-network aggregation techniques for wireless sensor networks:a survey［J］.IEEE Wireless Communications，2007，14(2):70-87.

［2］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks［J］.IEEE Communications Magazine，2002，40(8):102-114.

［3］Heinzelman W B，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［4］Chamam A，Pierre S.A distributed energy-efficient clustering protocol for wireless sensor networks［J］.Computers ＆Electrical Engineering，2010，36(2):303-312.

［5］孙亭，杨永田，芦东昕，等.一种基于聚合度的动态分层路由协议［J］.电子学报，2008，36(4):794-799.Sun Ting，Yang Yong-tian，Lu Dong-xin，et al.Convergence degree-based dynamic hierarchical routing protocol［J］.Acta Electronica Sinica，2008，36(4):794-799.

［6］Younis O，Fahmy S.HEED:a hybrid，energy-efficient，distributed clustering approach for ad hoc sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3(4):366-379.

［7］Dimokas N，Katsaros D，Manolopoulos Y.Energy-efficient distributed clustering in wireless sensor networks［J］.Journal of Parallel and Distributed Computing，2010，70(4):371-383.

［8］Qin M，Zimmermann R.An energy-efficient voting-based clustering algorithm for sensor networks［C］∥Proceedings of the Sixth International Conference on Software Engineering，Artificial Intelligence，Networking and Parallel/Distributed Computing and the First ACIS International Workshop on Self-Assembling Wireless Networks.Towson MD:IEEE，2005:444-451.

［9］Wen C Y，Sethares W A.Automatic decentralized clustering for wireless sensor networks ［J］.EURASIP Journal on Wireless Communications and Networking，2005，2005(5):686-697.

［10］曹涌涛，何晨，蒋铃鸽.无线传感器网络中基于自适应定时器策略的分簇算法［J］.电子学报，2007，35(9):1719-1723.Cao Yong-tao，He Chen，Jiang Ling-ge.A distributed timer-based clustering algorithm for wireless sensor networks［J］.Acta Electronica Sinica，2007，35(9):1719-1723.

［11］Fang S，Berber S M，Swain A K.An overhead-free clustering algorithm for wireless sensor networks［C］∥Proceedings of IEEE Global Telecommunications Conference.Washington DC:IEEE，2007:1144-1148.

［12］黄河，石为人，许磊，等.一种基于自适应加权的无线传感器网络室内能量均衡路由［J］.电子学报，2010，38(11):2493-2498.Huang He，Shi Wei-ren，Xu Lei，et al.Weight coefficient adaptive based indoor energy load-balance wireless sensor networks routing［J］.Acta Electronica Sinica，2010，38(11):2493-2498.

［13］徐玖平，吴巍.多属性决策的理论与方法［M］.北京:清华大学出版社，2006:12-52.

［14］Heinzelman W B.Application-specific protocols architectures for wireless networks［D］.Cambridge:Department of Eleetrical Engineering and Computer Science，Massachusetts Institute of Technology，2000.

［15］岳林，易本顺，肖进胜，等.优化生存时间的传感器网络地理机会路由［J］.华南理工大学学报:自然科学版，2010，38(12):67-72.Yue Lin，Yi Ben-shun，Xiao Jin-sheng，et al.Geographic opportunistic routing with optimized lifetime for sensor networks［J］.Journal of South China University of Technology:Natural Science Edition，2010，38(12):67-72.

［16］Wu Y，Mao Z，Fahmy S，et al.Constructing maximumlifetime data-gathering forests in sensor networks［J］.IEEE/ACM Transactions on Networking，2010，18(5):1571-1584.