能量均衡的多根多树型协议研究

何杏宇++杨桂松++周亦敏

摘要：现有的无线传感器网络簇树型算法一般基于单一的根节点或Sink节点构成网络，因此，网络中的数据流向单一且能耗分布不均衡。为此，本文提出了能量均衡的多根多树型（Multi-roots Multi-trees，MRMT）协议，该协议采用基于位置和链接关系的父节点选择算法，建立多根多树结构（MRMT结构），为每个节点提供多个数据流向，解决了因数据流向单一带来的能量消耗不均的问题。另外，该协议生成能量相关的MRMT链接矩阵和MRMT父节点矩阵，并提出基于这两个矩阵的最短路径获取方法，降低了网络总体能耗。实验结果证明本文提出的MRMT协议均衡了网络能耗，提高了网络稳定性，延长了网络寿命。

关键词：多根多树型协议；父节点选择算法；最短路径获取方法；MRMT链接矩阵；MRMT父节点矩阵

中图分类号：TP393.04 文献标识码：A DOI： 10.3969/j.issn.1003-6970.2015.10.007

引言

无线传感器网络（Wireless Sensor Networks，WSN）是一种由传感器节点通过相互合作来感知或监测物理环境的新型网络。树型路由（Tree Routing，TR）是无线传感器网络中一种较为基础的路由策略。为了改进树型路由以降低能耗，文献提出了增强树型路由（Enhanced Tree Routing，ETR）协议。但树型路由仍然存在因节点能耗不均而节点过早死亡的问题。为了避免低剩余能量的节点被选为转发节点，一些文献基于剩余能量对树型路由进行了改进，另一文献则进一步提出基于动态能量阈值模型的能量有效增强树型路由（Energy-aware Enhanced TreeRouting，EETR）。为实现网络的能耗均衡，一些层次型簇树协议也相继提出。LEACH算法是较早提出的一种层次型簇树算法，该算法以循环的方式随机选择簇头节点，使得网络中节点的能量均衡。随后，HEED算法要求在节点选取簇头时考虑其剩余能量，进一步提高了网络的稳定性。另一些文献也基于节点剩余能量对LEACH算法提出了改进。然而上述算法都是基于单一的根节点或Sink节点构成网络，且网络中的数据流向单一，虽然考虑了剩余能量，也采用了轮换机制，但仍然解决不了能耗分布不均的问题：靠近根节点或Sink节点的传感器节点的能耗仍然是相对较大。

为此，本文提出了一种能量均衡的多根多树型（Multi-roots Multi-trees，MRMT）网络结构，该结构选取网络中分散的多个根节点为起始点建立多个覆盖同一个网络的多个树结构，为每个节点提供的了多个数据流向，从而解决因数据流向单一带来的能量消耗不均的问题。

1 系统模型

本文的网络模型定义如下：（1）根节点和传感器节点都随机分布在正方形检测区域内，传感器节点在部署后位置固定且具有获知其位置信息的能力；（2）网络中的所有传感器节点结构相同且具有相同的初始能量、数据处理能力和通信能力和数据融合能力，且能量不可补给；（3）每个传感器节点具有一个全网唯一的ID号；（4）本文采用文献中的节点无线通信能量模型。

2 能量均衡的多根多树组网方式

在MRMT结构组网过程中，一方面，为了后续计算数据传输的最短路径，将生成能量相关的MRMT链接矩阵和MRMT父节点矩阵；另一方面，为了让节点拥有更多的新的链接关系，将采用基于位置和链接关系的父节点选择算法来建立网络连接。

2.1 MRMT父节点矩阵

在MRMT协议中，第一个树结构按照Zigbee协议给每个节点分配一个地址，该地址将作为每个节点固定的ID号，后续的树结构将不再对节点进行地址分配，而是利用每个节点的固定ID号进行数据传输。在MRMT结构的形成过程前，第一个根节点初始化一个MRMT父节点矩阵F[P][q]，其中，p表示节点的ID号码，g表示树结构的序号（第一个树结构q=l），F[p][q]表示节点p在第q个树结构中的父节点ID号。在每个树结构形成后，第一个根节点会通过第一个树按照ZigBee路由协议收集每个节点在新的树结构中的父节点ID，以更新MRMT父节点矩阵F[p][q]。当有节点移动或死亡，该节点或其邻居节点将该节点的新ID和移动后的父节点ID广播给所有节点以方便所有节点更新MRMT父节点矩阵F[p][q]。

2.2 能量相关的MRMT链接矩阵

为了方便后续计算数据传输的最短路径，在MRMT结构的形成过程前，第一个根节点还初始化一个MRMT链接矩阵结构A[i][j]，i和j表示节点的ID号。在每一个树结构形成后，每个节点将自身的ID号、位置信息和父节点ID号一同沿着第一个树结构按照Zigbee树型路由协议发送给第一个根节点。然后第一个根节点根据收集到的信息更新所述MRMT连接矩阵结构A[i][j]。当节点i和j之间有链接关系且节点i和j的剩余能量等级Ri和Rj均大于等于预设能量等级Rthreshold，则A[i][j]=D[i][j]，D[i][j]表示节点i和j之间的距离，否则A[i][j]=∞。

在MRMT结构形成之后，第一个树节点将周期性地收集所有节点的剩余能量信息，并对所有节点的剩余能量进行排序，选出剩余能量等级低于预设能量等级的节点，并将该节点ID信息广播出去提醒所有节点更新该节点对应的A[i][j]值为无穷大，从而使得这些剩余能量低的节点将暂时性不参与后续的最短路径计算，以保持整个网络的能耗均衡。

2.3 基于位置和链接关系的父节点选择算法

为了在树结构的形成过程中开辟出更多的新路径，本文设计了基于位置和链接关系的父节点选择算法。首先，第一个树是按照传统的树型组网方式形成的，而在后续第n（n≥2）个树结构形成过程中，节点优先选择在之前的n-1个树结构都与本节点没有链接关系的邻居节点作为父节点，如果存在多个这样的邻居节点，则选择其中距离第n个根节点最近的邻居节点为父节点，如果不存在这样的邻居节点，也选择距离第n个根节点最近的邻居节点为父节点。我们以图1为例对上述父节点选择算法进行说明，例如，在图1的第三个树的组网过程中，n2的邻居节点中只有n3在之前的树结构中未与n2建立了链接关系，节点n2选择n3作为父节点发起链接请求；虽然n7的所有邻居节点都在前面的树结构中与n7建立链接关系，但n8距离根节点n15的距离最近，节点n7选择节点n8作为父节点。

3 多根多树最短路径路由

利用MRMT结构传递数据时，MRMT结构的多个树为源节点和目的节点之间提供了多条路径，如图2所示，图中的MRMT结构分别为源节点n7和目的节点n13之间提供了三条树路径（分别用细实线、粗实线和虚线表示），然而这三条树路径并不是n7和n13之间的最短路径。n7和n13之间的最短路径为n7-n8-n12-n13，由三条树路径的不同分段拼接而成。我们可以利用源节点到目的节点的多条树路径的MRMT父节点矩阵和能量相关的MRMT连接矩阵结构计算当前节点到目的节点的最短路径：首先，根据MRMT父节点矩阵获取多个树结构为源节点和目的节点之间提供的多个树路径；然后根据多个树路径上节点对应的MRMT链接值A[i][j]，利用Dijkstra算法计算出当前节点到目的节点的最短路径。

3.1 树路径获取算法

如图3所示（R表示根节点，C表示当前节点，D表示目的节点，虚线表示两节点之间的路径），在一个树结构中，如果当前节点不为目的节点，则当前节点和目的节点的关系只有三种情况：当前节点和目的节点位于某一个共同前辈节点X的两个不同分支上；当前节点为目的节点的前辈；目的节点为当前节点的前辈。

Fig.3

Illustration of method to calculate tree path

那么，我们根据MRMT父节点矩阵设计树路径获取算法的伪代码为：同时搜寻当前节点C（节点ID号为c）和目的节点D（节点ID号为d）通往第q个根节点R的父节点序列，如果D节点到根节点的跳数少于C节点到根节点的跳数，若在C节点通往根节点的序列中发现节点X（ID号为C[m]，该节点X也在D节点到根节点的路上，为图3中情况l，C[m]=D[k]，那么在第q个树中C点到D点的树路径为节点C到X（ID号为C[州]）和X节点到D节点的两条路径的拼接；若X节点为D节点时，为图3中情况3，那么在第q个树中C点到D点的树路径为节点C到X（ID号为C[m]，m=0）；如果C节点到根节点的跳数少于D节点到根节点的跳数，若在D节点通往根节点的序列中发现节点X（ID号为D[m]），且该节点X也在C节点到根节点的路上，为图3中情况1，D[m]_C嘲，那么在第q个树中C点到D点的树路径为节点D到X（ID号为D[m]）和X节点到C节点的两条路径的拼接，若X节点为C节点时，为图3中情况2，那么在第q个树中C点到D点的树路径为节点D到X（序号为D[m]，m=0）。

3.2 Dijkstra算法求最短路径

当前节点根据目的节点的ID号并采用上述树路径获取算法计算出MRMT结构提供的多条树路径，根据多条树路径产生图G=（v，E），V表不多条树路径的所有节点的集合，E表示多条树路径上链接的集合。G中i节点和j节点之间的边的权重等于为对应MRMT链接值A[i][j]。然后，当前节点根据G利用Dzjkstra算法计算出当前节点到目的节点的最短路径。当前节点将数据包发送给最短路径中的下一跳节点，然后下一跳节点继续采用上述路由算法进行数据转发直至数据包到达目的节点。

4 仿真与实验

本文使用NS2平台对文献所提出的能量有效增强树型路由（Energy-aware Enhanced Tree Routing，EETR）、文献提出的能量相关的LEACH协议（LEACH-E）以及本文提出的MRMT协议分别进行了仿真，并对三种协议的仿真结果进行了对比分析。

4.1 实验参数设置

本文的仿真场景为200个传感器节点和10个根节点随机部署在一个长200m宽200m的正方形区域内。其中，数据包的长度为2000bits，自由空间能耗模型中功率放大器所需的能量参数εfs取0.0013，多路衰减能耗模型中功率放大器所需的能量参数εmp取10。根节点的初始能量为1J，传感器节点的初始能0.05J。

4.2 实验结果分析

为了比较上述三种协议中能量消耗的均衡性，本文分别对这三种协议的运行时节点能耗进行了随机抽样，并进行了节点能耗方差计算。由图4可知，EETR协议和LEACH-E协议均具有较高的能耗方差且波动较大，从而反映出较大的网络能耗不均衡性。经分析也不难发现，虽然EETR协议和LEACH-E协议都考虑到了节点的剩余能量，但由于根节点（或Sink节点）唯一，数据的传输流向也单一，从而使得网络中能量消耗不均衡。相较之下，本文提出的MRMT协议有效地降低了方差，呈现出较好的能耗均衡状况。

由图5可知，由于LEACH-E协议考不仅考虑了虑节点的剩余能量，而且具有簇头轮换机制，因此节点开始死亡的时间点比EETR协议晚，但由于LEACH-E协议将因节点轮换机制增加网络总体能耗，因此网络运行持续时间比EETR协议短（所有节点死亡视为网络运行时间结束）；而MRMT协议具有多个根节点，数据流向多样化，且在考虑节点剩余能量的情况下进行最短路径计算，既均衡了网络能耗又减少了网络的整体能耗开支，节点开始死亡的时间点最迟，且网络运行持续时间最长。

5 结论

本文提出了一种能量均衡的多根多树型协议，该协议采用基于位置和链接数量的父节点选择算法，选取网络中分散的多个根节点为起始点，建立覆盖同一个网络多根多树结构（MRMT结构）。MRMT结构不仅为节点开辟出更多的链接关系，而且为每个节点提供的了多个数据流向，解决了因数据流向单一带来的能量消耗不均的问题。另外，该协议在建立MRMT结构的过程中，生成了能量相关的MRMT链接矩阵和MRMT父节点矩阵，并根据能量相关的MRMT链接矩阵和MRMT父节点矩阵建立最短传输路径。实验结果证明本文提出的MRMT协议节省了网络能耗，提高了网络稳定性，延长了网络寿命。但本文利用固定ID进行数据传输的方法不够灵活，可在之后的研究中为MRMT结构提出更为灵活的地址分配方式。