基于簇结构稳定的分环多跳路由算法＊

周建钦，石志远，赵泽茂

（杭州电子科技大学通信工程学院，浙江杭州 310018）

基于簇结构稳定的分环多跳路由算法＊

周建钦，石志远，赵泽茂

（杭州电子科技大学通信工程学院，浙江杭州 310018）

为了提高大型无线传感器网络的稳定性，延长网络出现首个节点的死亡时间，提出一种基于簇结构稳定的分环多跳路由算法CBSM（Cluster structure stability based Sub－ring algorithm over multi－hop routing）.CBSM算法将监测区域划分为许多固定小区，采用基于节点剩余能量和节点位置的代价函数选择簇头.仿真结果表明，基于簇结构稳定的多跳路由算法，能有效延长网络出现首个节点死亡的时间，提高整个网络的稳定性.

固定分区；分簇路由；最优簇头数目；簇心；相对距离

1 网络模型

文中假设N个传感器节点随机、均匀的分布在半径为R的圆形区域内，同时有以下假设：

（1）所有节点初始能量相同，节点部署完毕后不再移动.

（2）节点装备有定位装置，可以感知自身地理位置.

（3）基站（BS）位于圆形区域的中心且位置固定，基站能量不受限制.

（4）节点能确保与所在分区内的任意一个节点保持通信.

为了方便不同簇间多跳路由路径的建立，按照实际需要将整个感知区域均匀等分为h个圆环，宽度为a＝R／h.从以基站为圆心的圆向外，依次标注为第1环、第2环、……、第h环.节点部署完成后向基站发送NODE＿M消息，其中包含节点的位置信息（posi，x，posi，y）和节点当前能量信息Ei－current.基站收到节点发送来的信息后，根据实际需求计算感知区域最佳分环数h.

2 算法描述

2.1 最优分区数目

无线传感器网络中，靠近基站的簇头节点因为要转发数据，其能量消耗要大于外环簇头的能量消耗，很容易因为能耗问题而过早“死亡”.为了避免出现数据传输过程中的“热点”问题，均衡不同环内簇头的能量消耗，笔者在不同环内划分规模不同的簇来解决簇头能耗不均的弊病［5］.具体来说就是：基站根据全网总体信息利用文献［4］中方法计算出各环最优簇头数目后，按照各环最优簇头数目mk（k＝1，2，...，h）将网络区域进行分区.分区模型建立完毕后，基站将区域总体信息和各环分区信息hzone、分区平均能量Eave以及基站位置posBS打包DATA＝｛N，R，h，hzone，Eave，posBS｝，并将其标注为BS＿TOTAL＿MEG向整个网络区域广播.网络区域中的任一节点在接收到BS＿TOTAL＿MEG消息后，将其自身位置信息与基站（BS）位置信息进行比较，以此来确定自己所在的环数和分区位置，方法为

则节点i位于第k环内.其中D（·）为距离运算，

图1 网络分区模型

利用以上方法，节点可以从集合DATA中找到自身所在的环数以及所在环的分区信息，各环按照分区信息进行分区，每个小分区即为一个簇.分区模型如图1所示.

文中采用文献［6］中提出的无线能量消耗模型.节点发送数据的能量消耗为

接收端消耗的能量为

其中：Eelec表示无线收发电路发送或接受1bit数据时的能耗；εfs和εmp分别表示自由空间模型和多路衰减模型的损耗系数；d0为常数；L是要发送或接收的数据比特数.

2.2 簇头选举

整个感知区域分区完毕后，基站计算各分区的平均能量Eave，并向全网广播.网路中任意节点i将接收到的自己分区的平均能量值与自身剩余能量比较，能量小于分区平均能量的节点放入集合Emin中.由于平均能量的计算需要全网节点的剩余能量信息，对于大型传感器网络来说能量消耗十分巨大，因此文中采用估计方法来预测每一轮各个分区的平均能量［7］.假设传感器节点每轮消耗相同的能量，这种假设是合理的，因为采用固定分区策略每轮的簇头数量相同，通信开销相近.

由文献［6］所示无线通信能耗模型可得第k环中任一簇头的能耗为

由文献［4］得第1环内某个成员节点的能耗为

由假设条件可以预测经过r轮后第k环内某个分区的平均能量为E＝Etotal－r·（Echk＋Enon－ch1）k＝1，2，...，h，

经过r轮后第k环内任意节点剩余能量为：

（1）节点上一轮为成员节点时，Ere＝E0－r·Enon－ch1；

（2）节点上一轮为簇头结点时，Ere＝E0－r·Echk，k＝1，2，...，h.

定义1 一个簇内所有节点位置坐标的平均值称为一个簇的主簇心，即节点的坐标质心［8］.其数学表达式为：设第k环某个簇内的任一节点i（i＝1，2，...，（Nk／mk）），节点的位置用posi，x和posi，y表示，则簇心坐标（主簇心坐标包含在分区信息hzone中向全网广播）表示为

分区中任意节点i到簇心的距离为

同理，将一个簇内所有剩余能量小于簇平均能量的节点位置坐标的平均值定义为副簇心.设第k环某个簇内集合Emin中有m个节点，集合中的任一节点j（j＝1，2，...，m）节点的位置用posj，x和posj，y表示，则副簇心坐标（副簇心坐标包含在分区信息hzone中向全网广播）表示为

集合Emin中任意节点j到副簇心的距离为

从而，主簇心与副簇心之间的相对距离为D＝｜D（i）－D（j）｜.

为了使簇内节点保留更多的能量用来传递簇间数据，同时尽量延长第1个节点的死亡时间，采用基于节点剩余能量和节点位置的代价函数的方法选举簇头，使当选的簇头剩余能量尽可能大并且使当选簇头节点到主、副簇心的相对距离尽量小.（当选簇头剩余能量足够大才会在传递簇间数据时不至于过早死亡而使得网络瘫痪，相对距离尽可能小可以减少大部分节点向簇头传输数据时的能耗，延长其生存时间.）

由节点到主、副簇心的相对距离和节剩余能量设定权值

簇头选举时，在第k环的某个分区内的节点i首先从基站发送来的DATA信息中查找到自己所在分区的平均能量Eave和主、副簇心坐标判定自己所属的集合，并利用（1）和（2）式计算出节点到主、副簇心的距离D（i）和D（j）.然后，节点i利用（3）式求出代价权值W，权值W设定完毕后，节点将自身权值向所在分区内广播.节点i将接收到其他节点的权值信息与自身权值进行比较，若存在权值比自身大的节点，则该节点i退出簇头竞争成为成员节点，否则宣布自己当选为簇头.

当选为簇头的节点以固定功率f向外发送CH＿ELECTED＿MSG消息，消息中包含当选簇头节点的地理位置以及能量信息.分区内其他节点接收到此消息后检查发送此消息的节点是否与自己在同一分区，若是则退出簇头竞争，并向当选的簇头节点发送NODE＿JOIN＿MSG消息，加入该簇.簇头接收到NODE＿JOIN＿MSG消息后返回一个ACP＿MSG消息将节点加入到本簇.第（k＋1）环中的簇头节点接收到来自第k环的簇头消息后，在第k环当选簇头中选择下一跳路由节点.

2.3 下一跳路由节点

传输1bit的数据消耗的能量远大于处理1bit数据所消耗的能量，位于内环的簇头在数据传输过程中要转发外环数据，若是外环簇头选择下一跳路由节点算法不合理，则会造成内环某些簇头成为多个外环簇头的中继节点，或某些内环簇头节点处于相对空闲状态.这种情况会造成节点的能量消耗不均匀，导致内环某些簇头节点因转发数据量过大而过早“死亡”，从而影响整个网络的稳定性.

为了解决这个问题，笔者提出依据能耗均衡原则选择下一跳路由节点.所谓能耗均衡原则，就是能量低的簇头在选择下一跳路由节点时选择距离近的簇头节点，能量高的节点选择距离远的簇头节点作为下一跳路由节点.具体算法描述为：第（k＋1）环中的簇头节点接收到第k环簇头节点发送来的CH＿ELECTED＿MSG消息后，根据自身位置计算与第k环内簇头之间的距离d.第（k＋1）环中的簇头首先选择距离d最小的第k环内簇头作为下一跳路由节点，第k环中的簇头节点将选择自己作为下一跳路由的第（k＋1）环中的簇头节点放入集合R－NODE中，然后集合中的节点数大于2个时，集合中的节点比较彼此的能量大小，能量最大的节点退出该集合，选择距离自己次近的第k环中簇头作为下一跳.以此类推，直到所有簇头节点选择到合适的下一跳路由节点.

2.4 算法流程

CBSM算法的运行过程主要分为3个阶段：分区、簇头选择和数据传输.其中数据传输阶段按照TDMA方式，簇内不同节点按照事先划分的时隙向簇头传输数据，TDMA信息包含在簇头建立阶段发送的广播消息CH＿ELECTED＿MSG中.具体流程如图2所示.

图2 CBSM算法流程

3 仿真结果

表1 仿真主要参数

仿真环境采用Matlab2008a，仿真算法包括LEACH，RBMC和CBSM.笔者对节点总数N＝1 000、区域半径为R＝240的场景进行了仿真，整个感知区域分为4个等宽的环，从最内层第1环到最外层第4环最优簇头数目分别为m1＝8，m2＝13，m3＝17，m4＝21.仿真主要参数见表1.

当网络中出现节点死亡时，网络性能就会下降，网络的拓扑结构、数据检测率等都会变差，网络开始变得不稳定.因此，文中区别于传统算法中以所有节点死亡时间作为网络的生命周期，而采用首节点和一半节点死亡时间来衡量网络的生命周期.

图3分别是CBSM算法与LEACH算法、RBMC算法存活节点数随网络运行轮数的变化曲线.表2是3种算法首节点和一半节点死亡时的对应轮数.从表2可以看出，以一半节点死亡时间来衡量网络生命周期时，CBSM算法的网络生存周期比LEACH算法提高了约414%，比RBMC算法提高了约97%；若以首节点死亡时间来衡量网络生命周期，则CBSM算法分别比LEACH算法和RBMC算法提高了约177%和123%，显著地延长了网络的生命周期.

图3 节点存活数目n＝1 000时剩余节点数与轮数关系

表2 节点死亡轮数对照

图4显示了CBSM算法和LEACH算法簇头数目变化曲线，SBMC算法的簇头数目变化规律与LEACH算法相同.由图4可知，CBSM算法簇头数目与LEACH算法相比相对较稳定.簇头数目稳定才能保证将区域内节点采集的信息转发到基站，保持簇头数目的稳定在一定程度上提高了整个网络的稳定性.

图4 簇头数目变化曲线

4 结语

通过对典型分簇算法LEACH及其改进算法RBMC的分析，提出了CBSM算法.CBSM算法将整个网络区域划分为规模大小不同的固定小区，每个小区作为一个簇，有效地控制了网络的拓扑结构；同时采用基于节点剩余能量和节点位置的代价函数选举簇头，延长了网络的生命周期，提高了网络的稳定性.

［1］ SOHRABI K.Protocols for Self－Organization of a Wireless Sensor Network［J］.IEEE Personal Communications，2000，7（5）：16－27.

［2］ HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy－Efficient Communication Protocol for Wireless Micro－Sensor Networks［C］／／Proceedings of IEEE HICSS.Hawaii，USA，2000：223－232.

［3］ SMARAGDAKIS G，MATTA I，BESTAVROS A.SEP：A Stable Election Protocol for Clustered Heterogeneous Wireless Sensor Networks［C］／／Proceedings of SANPA.Boston，Massachusetts，USA，2004：251－261.

［4］ 刘 志，裘正定.基于分环多跳的无线传感网分簇路由算法［J］.通信学报，2008，28（3）：104－113.

［5］ SORO S，HEINZELMAN W R.Prolonging the Lifetime of Wireless Sensor Networks via Unequal Clustering［C］／／Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium（IPDPS’05）.Denver，Colorado，USA，2005：1－8.

［6］ HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.An Application－Specific Protocol Architecture for Wireless Micro－Sensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660－670.

［7］ 卿 利，朱清新，王明文.异构传感器网络的分布式能量有效成簇算法［J］.软件学报，2006，17（3）：481－489.

［8］ BULUSU N，HEIDEMANN J，ESTRIN D.GPS－Less Low－Cost Outdoor Localization for Very Small Devices［J］.Personal Communications，IEEE，2000，7（5）：28－34.

（责任编辑 向阳洁）

Cluster Structure Stability Based Sub－Ring Algorithm over Multi－Hop Routing

ZHOU Jian－qin，SHI Zhi－yuan，ZHAO Ze－mao
（School of Communication Engineering，Hangzhou Dianzi University，Hangzhou 310018，China）

The cluster structure stability based sub－ring algorithm over multi－hop routing（CBSM）is proposed to improve the stability of the wireless sensor network（WSN）and to prolong the lifetime of the network.The main idea of the CBSM is to divide the monitoring area into a number of fixed cells.Then select the cluster head with the residual energy and the nod location in the fixed cell.The simulation results showed that CBSM has a good performance in prolonging the network lifetime and increasing the network stabilization.

fixed partition；clustering routing algorithm；optimal cluster head size；clusters heart；relative distance

TP393

A

10.3969／j.issn.1007－2985.2013.03.004

1007－2985（2013）03－0015－06

无线传感器网络是一种自组织网络，随机、高密度分布的节点具有能量有限、片上运算能力不足、存储空间小等特点［1］.其中，节点的能量对网络生命周期的影响最为显著，这是因为传感器节点一般由电池供电，能量有限且不可补充.另外，当网络中出现节点死亡时，网络性能就会下降，网络的拓扑结构、数据检测率等都会变差，网络开始变得不稳定.因此，在确保能量有效性的同时，还要尽量延长网络中第1个节点的死亡时间，以提高整个网络的稳定性.

传统路由算法中，分簇路由算法相比于平面路由算法具有更好的能量有效性和可扩展性.LEACH（low energy adaptive clustering hierarchy）算法［2］是人们最早提出的分簇算法，其核心思想是让每个节点轮流担当簇头，将整个网络的负载均匀的分配到每个节点上.然而LEACH算法只考虑了单跳模型，因此只适合小型WSN（无线传感器网络）.SEP（stable election protocol for clustered heterogeneous wireless sensor networks）算法［3］根据节点初始能量的不同，为节点设置不同的簇头选举概率来均匀能耗，但是SEP算法仍采用类似LEACH的簇头随机选举策略，从本质上说仍然是一个单跳网络.文献［4］提出了RBMC（ring based multi－hop clustering routing algorithm）算法，将检测区域分成多个同心圆环，根据第1环能耗最小目标和各环能耗相同原则推导出各环的最优簇头数目，外环簇头通过内环的簇头转发数据.RBMC算法选择方法与LEACH算法相同，随机动态地选择簇头会造成簇头数目高度动态变化，网络的拓扑结构不稳定，若某轮没有选出簇头，则整个网络会处于暂时失效的状态.

为了提高大型网络的稳定传输时间，有效控制网络的拓扑结构，笔者提出基于簇结构稳定的路由算法CBSM.首先将感知区域划分为等宽圆环，其次按照每环最优簇头数目将圆环分为多个规模不同的小区，每个小区作为一个簇，外环簇头通过内环簇头转发数据，最终建立一个拓扑结构稳定、能耗均匀的无线传感网络.

2012－12－03

浙江省自然科学基金资助项目（Y1100318；Y1100818）

周建钦（1963－），男，山东巨野人，安徽工业大学计算机学院教授，硕士，主要从事通信、密码学与理论计算机科学研究.