能量有效的无线传感器网络分簇路由协议

刘伟， 杜佳鸿， 贾素玲， 蒲菊华，*

(1. 北京航空航天大学 经济管理学院, 北京 100083； 2. 深圳北航新兴产业技术研究院, 深圳 518057;3. 北京航空航天大学 计算机学院, 北京 100083)

微电子技术、无线通信技术的发展以及计算技术的提高，推动了多功能的低功耗传感器的进步，使其在自身微小体积内能够实现采集信息、处理数据和无线通信等多种功能。无线传感器网络(Wireless Sensor Networks,WSNs)是一种分布式传感器网络，其末梢是可以感知外部世界的廉价传感器，目的是共同感知、采集和处理网络覆盖区域中感知对象的信息。

WSNs作为当今信息领域新的研究热点，待发现和研究的关键技术有很多，主要包括：定位技术、路由协议、网络安全、时间同步以及数据融合等[1]。其中核心是路由技术，由于WSNs受环境以及自身约束的影响，不同实际情况中的路由协议差别可能很大，因此对于路由协议，没有一个通用的方法，而是根据具体的要求提出独有的设计标准[2]。

从路由结构要素出发，可以设计为2种路由协议：平面路由协议和层次路由协议，其中层次路由协议又叫做分簇路由协议。前者设计简单，健壮性良好，但建立、维护路由的开销大，适合小规模网络；后者扩展性好，适合大规模网络，且簇首节点是整个网络的关键，其失效将导致路由失败[3]。分簇式的拓扑结构有利于实际中的分布式算法，因此国内外有许多科研人员对WSNs中的分簇路由协议进行了研究，并提出了许多算法、协议[4]。

低功耗自适应集簇分层型(Low-Energy Adaptive Clustering Hierarchy,LEACH)协议是最典型的分簇算法，网络生命的时间被分为多个回合(rounds)，每个回合包括2个阶段：簇建立阶段、数据传输阶段。然而LEACH算法在很多方面还存在的不足，簇首选择只是随机选择，非簇首节点在选择加入簇时，仅依据接收信号的强度。国内外因此已经采取了很多策略进行改进，如对DCHS[5]、LEACH-improve[6]和LEACH-CH[1，7]都提出了一些改进。之后，固定簇半径的分簇协议(Hybrid Energy-Efficient Distributed clustering, HEED)[8]算法又被提出，HEED考虑节点剩余能量和通信代价2个指标来选举簇首节点。然而在实际情况中，由于基站一般离整个网络的距离很远，频繁多次地远距离传输会加大节点的消耗能量，为了解决这些问题，国内外的学者也提出了一些改进算法，如PEGASIS[9]、TEEN[10]、EEUC[11]、OHEED[1，12]和HEED-FT[1，13]，但这些协议的一个主要弊端都是簇首节点的能量消耗过大，导致网络生存周期变短。针对具体环境，Mini等[14]针对目标覆盖问题，使用人工蜂群算法和粒子群优化算法，解决了节点部署问题，以使满足覆盖要求的最少节点处于工作状态，延长了网络寿命。

通用设计的目标一般需要考虑以下的设计：算法简洁性、算法可靠性、网络自适应性、服务质量及优化能力[15]。目前的分簇路由协议在网络能耗均衡与降低能耗方面还有较大的提升空间，虽然部分协议能够得到分布均匀的簇首节点，但是其在簇建立阶段牺牲了较多的能耗与较大的时延，在节点通信开销方面仍存在改进的方法。因此，针对以上问题，本文提出了一种基于节点间相关性的能量有效分簇路由协议——BCCP协议。

1 BCCP协议整体设计

在LEACH、HEED路由协议的基础上，BCCP协议还考虑了以下相关因素：①节点间位置相关性，在WSNs中，节点间位置相距近，距离小，其通信能量消耗也小。②节点间数据相似性，传感器节点的感知数据、感知类型与其他邻近节点监测体现的价值相似。成簇时应获得更多的数据相似节点，数据融合效率才会更高，数据量才会降低。③节点间协同性，WSNs中的节点不是各自独立的，网络需要节点间合作才能产生具有价值的数据。具有协同性的节点应在同一簇内，以降低数据传输能耗。

当前的大多数分簇路由协议在进行簇首节点选择时一般的选举因素只是剩余能量，没有考虑节点与节点之间的其他相关性因素[16]。因此，本文提出了一种基于节点间相关性的能量有效分簇路由协议——BCCP协议，该协议主要分为2个部分：第1部分为能耗均衡分簇算法BCCP-EBA，该算法是BCCP协议的主要支撑，考虑了节点自身的剩余能量、节点能耗以及节点位置相关性来选择簇首节点和剩余节点入簇，使得簇首节点选举阶段时间短、开销小。第2部分为降低能耗分簇算法BCCP-ESA，该算法是对BCCP-EBA能耗均衡分簇算法的完善，考虑了节点间位置相关性，能耗协同性作为节点入簇的依据，以及数据相似性和节点能耗作为簇内通信的依据，以此降低簇内通信以及网络整体的能耗。图1展示了BCCP协议的整体设计。

与LEACH、HEED等路由协议相比，BCCP协议使用一种基于节点间相关性的新颖的簇建立方式与数据传输方式，可以达到降低网络能耗以及延长节点生存时间的目的。

图1 BCCP协议整体设计Fig.1 Integrated design for BCCP

2 能耗均衡分簇算法BCCP-EBA

为了实现能耗均衡的WSNs，本文提出了一种基于节点间位置相关性与节点剩余能量的WSNs能耗均衡分簇算法BCCP-EBA。基于该算法的分簇路由协议按照轮次进行工作，簇建立阶段分为多个迭代处理进行，一个迭代代表着一个节点接听全部邻居节点信息的过程。该分簇算法将节点间的位置相关性加入至分簇路由协议中，选取分布均匀的簇首节点，选取通信能耗低的簇内成员节点加入簇。

节点间的位置相关性体现于节点间的通信能耗之中，位置远的节点间通信能耗大。因此，可以将节点与周围邻居节点间的通信层次作为能耗判断参数。任意节点拥有多个通信能级，该节点通过变换通信能级与远近不一的邻居节点通信，即与该节点位置近的节点选择低通信能级，与该节点位置远的节点选择高通信能级。使用节点最小通信能耗关系式获得该节点与所有邻居节点进行通信的最小能量消耗为

(1)

式中：M为该节点的邻居节点数目；Mi为节点A与第i个邻居节点间进行通信时使用的通信能级。

协议同样采用节点自身剩余能量与节点间的位置相关性作为分簇参数选举簇首节点以及选择加入簇。参考节点自身剩余能量来选择随机选择节点当选为临时簇首节点的概率，这样会增大剩余能量大的节点临时簇首节点的概率。通过节点自身剩余能量与周围邻居节点的剩余能量共同决定节点成为临时簇首节点的概率，以此增加簇建立阶段初始时的临时簇首节点数目，加速簇首节点选举的过程。节点随机生成临时簇首节点的概率Cprob计算式为

(2)

式中：Cprob为初始成为临时簇首节点的百分比；Eresidual为节点的剩余能量；Emax-ner为该节点的邻居中剩余能量最大的节点的剩余能量值；Pmin为Cprob的最小值。节点以Cprob与随机数Ran进行比较，若大于或者等于Ran，则该节点成为临时簇首节点，反之则为普通节点。

在选择完最终簇首节点后，非簇首节点直接在邻居簇首节点中选择通信能耗最小的簇首节点作为自己加入的簇首节点。

3 降低能耗分簇算法BCCP-ESA

为了进一步降低簇首节点的能耗以及簇内通信能耗，本文对节点间的数值相似性、协同性进行了研究，提出了一种降低能耗分簇算法BCCP-ESA。

该算法在能耗均衡分簇算法BCCP-EBA的基础上改进分簇路由协议，将节点间数据相似性引入簇首节点选举阶段、节点入簇阶段，以此选择通信能耗小且数值相似的簇首节点；将节点间数据相似性引入网络数据传输阶段，以此降低簇内通信数据量；将节点间协同性引入网络数据传输阶段，以此降低簇内、簇间通信数据量。

在能耗均衡分簇算法BCCP-EBA的能量消耗计算中加入数值差异通信能耗，以此加入节点间数值相似性对簇首节点选举以及节点选择加入簇的影响。引入数值差异通信能耗后的节点通信能耗计算式为

(3)

式中：α为节点间位置相关性对通信能耗的影响因子；β为节点间数据相似性对通信能耗的影响因子，且α+β=1;Ai为第i个节点与计算节点间通信时传输的数值平均位数。

簇首节点选择完成后，对于任意协同的节点，若该节点与其他节点具有协同性，该节点的邻居节点中存在最终簇首节点且此簇首节点与该节点具有协同性，则该节点选择此簇首节点作为簇首节点；若该节点的邻居节点中存在多个最终簇首节点，则选择通信能耗小的簇首节点作为自己的簇首节点；若该节点的邻居节点中不存在与该节点具有协同性的簇首节点，则该节点在协同节点中选择与簇首节点通信能耗最小的节点作为协同中转节点，并将此中转节点的簇首节点作为自己加入的簇首节点。

将降低能耗分簇算法BCCP-ESA加入分簇路由协议中，可以降低簇内通信的数据量，降低簇间通信的数据量，以此保护节点能耗，延长网路偶的生命周期。

对于BCCP-ESA算法，在簇建立阶段，利用式(3)修改节点间的通信能耗，修改通信能耗计算后，利用能耗均衡分簇算法BCCP-EBA的分簇机制对网络中的簇首节点选择及节点选择入簇产生影响。在数据传输阶段，进行簇内通信时直接使用节点间数值差异传输即可。

簇首节点选举完成后，利用节点间协同性选择协同节点的簇首节点、中继节点，对于任意节点在选择加入通信能耗最小的簇首节点时，按照如下步骤进行：

步骤1该节点感知周围存在的簇首节点以及与该节点具有协同性的节点，转至步骤2。

步骤2判断该节点的邻居节点中是否存在与该节点协同的节点，若不存在，则转至步骤3，若存在，转至步骤4。

步骤3在邻居簇首节点中选择通信能耗最小的簇首节点作为该节点加入的簇首节点，若该节点被最终簇首节点覆盖，则结束。

步骤4判断该节点的邻居协同节点中是否存在簇首节点，若存在，转至步骤5，否则，转至步骤6。

步骤5该节点将邻居协同节点中的簇首节点作为该节点加入的簇首节点，若该节点被最终簇首节点覆盖，则结束。

步骤6该节点在协同节点中选择与簇首节点通信能耗最小的节点作为协同中转节点，并将此节点的簇首节点作为该节点加入的簇首节点，若该节点被最终簇首节点覆盖，则结束。

4 仿真实验

在WSNs中，由于其自身的特点，对于大规模部署的WSNs，在真实物理环境的测量中很难实现，只能利用计算机的模拟仿真实验对研究的协议、算法等进行测试，对其性能进行分析评价。本文提出的BCCP分簇路由协议采用MATLAB平台进行仿真实验。

4.1 仿真环境设置

本实验的仿真基于MATLAB 7.1平台上进行，仿真参数设计如表1所示。

仿真实验主要选择了LEACH、HEED分簇路由协议与BCCP协议进行比较，并且分别与BCCP协议中的能耗均衡分簇算法BCCP-EBA与降低能耗分簇算法BCCP-ESA进行比较，验证算法的有效性，主要的指标有簇建立消耗能量、网络存活节点、网络整体能耗。本文实验以50%的节点死亡作为网络失效的标志。

表1 仿真环境参数设置Table 1 Parameter setting of simulation environment

4.2 实验结果分析

为了分析BCCP-EBA与BCCP-ESA对BCCP协议的影响，将BCCP协议分为3个版本：①能耗均衡分簇算法BCCP-EBA；②BCCP-VALUE，在BCCP-EBA基础上加入节点间数据相似性后实现的分簇路由协议；③BCCP-COO，在BCCP-EBA基础上加入节点间协同性后实现的分簇路由协议。

为了对比节点间数据相似性与节点间协同性对网络能耗的影响，在LEACH协议基础上实现了如下2个协议：①LEACH-VALUE，在LEACH的基础上加入节点间数据相似性后实现的分簇路由协议；②LEACH-COO，在LEACH基础上加入节点间协同性后实现的分簇路由协议。

4.2.1 BCCP-EBA协议仿真结果

LEACH、HEED和BCCP-EBA分簇路由协议在每软次簇建立阶段消耗的能量随时间的变化曲线如图2所示。图中，横坐标为网络工作进行的轮数，用来代表网络工作的时间，纵坐标为协议在簇建立阶段消耗的能量。

图2 簇建立阶段消耗的能量对比Fig.2 Comparison of energy consumption for construction of clusters

由图2可知，BCCP-EBA分簇路由协议在簇建立阶段的能耗一直处于一个较低的水平；HEED分簇路由协议在存活节点较多时需要消耗较多的能量进行分簇，存活节点数目小时，簇建立阶段的能耗也较低；LEACH分簇路由协议中的分簇能耗较大，主要是因为其簇内部存在个别成员节点与簇首节点距离过大，导致能耗过大。

LEACH、LEACH-COO、BCCP-EBA和BCCP-COO分簇路由协议的存活节点数目随轮次的变化如图3所示。图中纵坐标为整个网络中的存活节点的数目。图4中LEACH-COO分簇路由协议相对于LEACH协议，其生存时间得到了微小的提升；图3中BCCP-COO分簇路由协议相对于BCCP-EDA协议，其生存时间得到了一定程度的提升，将网络的生存时间延长了5%左右。

LEACH、LEACH-COO、BCCP-EBA和BCCP-COO分簇路由协议的网络整体能耗随轮次的变化曲线如图4所示。图4中在LEACH引入节点间数据相似性要素后，其网络整体能耗有了一定的改善，但是效果很不明显；图4中在BCCP-EBA分簇路由协议中引入节点间数据相似性要素后，网络整体能耗降低了5%左右。所以，引入节点间数据相似性要素可以降低网络的能耗，但是效果不明显。

4.2.2 BCCP协议仿真结果

BCCP-EBA、BCCP-COO、BCCP-VALUE和BCCP分簇路由协议的存活节点数目随软次的变化曲线如图5所示。由图5可知，在将能耗均衡分簇算法BCCP-EBA与降低能耗分簇算法BCCP-ESA进行融合后，BCCP分簇路由协议能够更好地进行工作，存活节点数目、网络生存时间均有改善。

图4 网络整体能耗对比Fig.4 Comparison of complete network energy consumption

图5 BCCP-EBA、BCCP-COO、BCCP-VALUE和BCCP分簇路由协议的网络存活节点数目对比Fig.5 Comparison of number of live nodes in network of BCCP-EBA，BCCP-COO，BCCP-VALUE and BCCP clustering routing protocol

BCCP-VALUE协议中节点位置相关性α与节点数据相似性β在进行分簇时的权重比例对网络的影响如图6所示。由图6可知，节点位置相关性对于网络能耗的影响强于节点数据相似性，当节点数据相似性为0.7时，网络性能最优。这是因为在节点的通信模型中，能耗与kd2成正比，k为数据量，即节点数据相似性的影响因素；d为节点间距离，即为几点位置相关性的影响因素。因此，节点位置相关性对网络性能影响较大。

图6 不同α,β取值对网络性能的影响Fig.6 Influence of different α and β on network performance

5 结 论

1) 以节点间的位置相关性为依据计算节点能耗，以节点自身的剩余能量与邻居节点最大剩余能量计算随机生成簇首节点的概率，以节点能耗为依据得到分布均匀的簇首节点，以节点能耗作为节点入簇的依据，以此使得簇首节点选举阶段时间短、开销小，初始时随机生成的临时簇首节点数目稳定。

2) 以节点间的位置相关性和节点间数据相似性为依据共同计算节点能耗，以节点能耗和协同性作为节点入簇的依据，以节点间数据相似性和协同性作为簇内单跳通信的依据，以此降低簇内通信、簇间通信的数据量，降低节点自身、网络整体的能耗。