无线传感网络中基于Dijkstra 算法的分簇路由

张慧娟

（驻马店职业技术学院信息工程系，河南 驻马店 463000）

0 引言

无线传感网络（wireless sensor networks，WSNs）是由大量传感节点以自组织方式分布，且节点间能相互通信的无线网络。目前，WSNs 已在多个领域内广泛使用，如健康医疗，野外环境监测。传感节点通过连续地监测环境，并感测环境数据，再将数据传输至汇聚节点，进而实现对环境的监测。

节点的通信带宽有限，若信宿在节点通信范围内，节点就直接将数据传输至汇聚节点，否则节点只能以多跳方式向汇聚节点传输数据。在部分应用中，如目标跟踪，战场侦察，WSNs 将产生了大量的数据，这增加了网络流量。

由于节点能耗是WSNs 的有限资源，基于WSNs 的网络应用必须关注节点能耗问题。节点的能量有限，即便节点能量消耗完毕，也不便于补给能量。因此，必须通过算法或者策略缓解节点能耗速度，延长节点的工作时间。

簇结构是降低节点能耗，提高数据传输效率的有效策略。在簇结构中，将WSNs 内节点划分多个簇，每个簇由一个簇头（cluster head，CH）和多个簇成员构成。CH 负责收集、融合本簇内的簇成员数据，再传输至汇聚节点，图1 给出典型的基于簇的WSNs 拓扑结构。

图1 基于簇的网络拓扑结构

然而，由于CHs 承担了更多数据收集和转发的任务，它们能耗速度高于簇成员节点的能耗速度。并且，各个CH 间的能耗速度可能也不尽相同。因此，如何选择最优的簇头数，并且平衡CHs 间的能耗是构建簇算法必须考虑的问题。

文献［6］讨论了基于能量消耗的簇头选择问题，并提出间歇性簇头选择策略。文献［7］提出基于鸡群优化算法的簇头选举策略，利用鸡群优化算法产生簇头，稳定簇结构，进而减少网络能耗。

尽管分簇路由能够减少网络能耗，并且研究人员也提出不同的分簇路由策略，但是这些策略并没有考虑节点的拥塞情况。实质上，若节点拥塞，会导致节点无法按时传输数据包，增加数据包传输时延，并且也增加了节点能耗。

为此，基于Dijkstra 算法的分簇路由（clustering routing-based dijkstra，CRBD）。CRBD 路由依据节点的剩余能量以及离汇聚节点的距离信息，产生簇头，并且避免拥塞节点担任簇头。再利用贪婪启发式算法构建簇。为了缩短簇间的数据传输路径，采用Dijkstra 算法构建簇间最短路径，优化传输路径，减少簇头的能量消耗。仿真结果表明，CRBD 路由降低节点能耗，延长了网络寿命。

1 系统模型及相关概念

式中，表示节点的通信半径。

1.1 能量消耗模型

节点s接收比特数据所消耗的能量：

式中，α表示接收单比特数据所消耗的能量。

节点s在传输数据和接收数据两个阶段共消耗的能量E：

1.2 相关概念

数据包传递率（packet delivery rate，PDR）等于汇聚节点所接收的数据包数与所有节点传输的数据包数之比，如式（7）所示：

式中，N表示汇聚节点所接收的数据包数，N表示所有节点传输的数据包数，其定义如式（8）所示：

将时间内信宿所接收的数据包数定义为网络吞吐量：

2 CRBD 路由

CRBD 路由主要由拥塞节点的识别、最初CHs数、产生最优CHs、簇形成和数据传输4 个阶段构成。

2.1 拥塞节点的识别

2.2 初始的簇头数

式中，表示节点通信半径。

2.3 产生最优簇头

为了避免拥塞节点担任簇头，CRBD 路由禁止拥塞节点担任簇头。即拥塞节点不参与簇头竞争。

2.4 基于贪婪启发式算法的簇形成

节点s依据式（16）计算与个簇头间的权重值，再从中选择具有最大权重的簇头作为自己的簇头，并向发送加入消息Join_CH。

2.5 最短路径的簇头间多跳路由

2.6 构建最短路径示例

图2 构建最短路径的多跳路由示例

表1 最短路径的迭代过程

3 性能仿真

3.1 仿真参数

利用MATLAB 软件建立仿真平台，分析CRBD路由的性能。在100×100方形区域内随机部署100～200 个节点。汇聚节点位于区域中心。图3 显示了在100×100方形区域内随机部署100 个节点的拓扑结构，其中，红色的空心圆表示汇聚节点，黑色实心点表示传感节点。具体的仿真参数如下页表2 所示。

表2 仿真参数

图3 100 个节点100×100 m2 在区域内的分布

为了更好地分析CRBD 路由性能，选择文献［13］提出的基于改进萤火虫聚类的能效路由（energy efficient routing based on improved firefly clustering，EIFC）和文献［14］提出拥塞感知的数据收集（congestion-aware data collection，CADC）路由。EIFC 路由利用改进萤火虫聚类算法分簇，使簇头分布更均匀，但是EIFC 路由并没有优化数据传输路径。CADC 路由旨在提高数据收集效率，其利用kmeans 聚类优化数据传输率，控制拥塞。

接下来，数据包传递率、能量消耗和网络寿命以及数据包传输时延4 个方面分析CRBD 路由、EIFC 路由和CADC 路由的性能。

3.2 数据包传递率

首先分析CRBD 路由，EIFC 路由和CADC 路由的数据包传递率性能，如图4 所示。

图4 数据包传递率

从图4 可知，相比于CADC 路由和EIFC 路由，CRBD 路由的数据包传递率具有明显的优势。在100 轮（=100）内，CRBD 路由的数据包传递率均保持在85%以上。相比之下，CADC 路由和EIFC 路由的数据包传递率随运行轮的增加而下降速度更快，其中CADC 算法的下降速度最快。原因在于：CADC路由旨在通过控制拥塞，提高数据传输率。因此，在前60 轮内，CADC 路由的数据包传递率优于EIFC路由，但是随着轮数的增加，其数据包传递率迅速下降。这主要是因为：CADC 路由并没有考虑到节点能耗问题，当运行至一定轮数，网络内部分节点的能耗可能消耗殆尽，无法转发数据包，导致数据包传递率快速下降。

与CADC 路由相比，CRBD 路由和EIFC 路由的数据包传递率下降速度较缓慢。这归功于：它们优化了簇头的选择，缓解了节点的能耗速度。

3.3 节点的平均能耗率

下页图5 给出CRBD 路由，EIFC 路由和CADC路由的平均能耗性能。从图可知，相比于CADC 路由，CRBD 路由的平均能耗最低，并且随运行轮的增加，能耗增加速度也较缓慢。但是，在前40 轮阶段，CRBD 路由的平均能耗略高于EIFC 路由。这主要是因为：CRBD 路由中节点需要执行基于贪婪启发式算法，增加了节点能耗。但是随着轮数的增加，CRBD 路由在降低能耗方面的优势突显出来。

图5 节点的平均能耗

3.4 网络寿命

网络寿命是衡量WSNs 性能的重要指标。引用式（20）计算网络寿命（Network Lifetime，NL）。

式中，表示节点的初始能量。从式（20）可知，等于节点的初始能量与网络内能耗最多节点所消耗的能量的比值。

在100×100区域部署100～200 个节点。在每个拓扑环境下，运行100 轮，再利用式（20）计算网络寿命。图6 给出CRBD 路由，EIFC 路由和CADC算法的情况。

图6 网络寿命

从图6 可知，CRBD 路由的网络寿命性能优于EIFC 路由和CADC 路由。这符合预期，也与图5 的数据相符合。此外，节点数的增加，使网络寿命呈下降趋势。原因在于：节点数越多，算法的复杂度越高，加大了节点运行开销。但是从图6 可知，网络寿命随节点数增加而下降的速度较缓慢。

3.5 数据包传输时延

最后，分析数据包的传输时延，其反映了将一个数据包从节点传输至汇聚节点所需的平均时间。在100×100区域部署100～200 个节点。在每个拓扑环境下，运行100 轮。依据式（11）计算一个数据包的平均传输时延。

图7 给出CRBD 路由，EIFC 路由和CADC 路由的平均传输时延随节点数的变化情况。从图可知，节点数的增加提升了平均传输时延。这主要原因在于：节点数越多，产生的数据包数越多，队列时延随之增加。

图7 数据包的平均传输时延

此外，从图6 可知，节点数的增加，加大了节点的能耗，提升了节点能量消耗速度。而能耗速度的加大，可能导致部分节点的剩余能量过低，无法转发数据或者传输数据，最终，降低了数据包传输成功率，需要多次重传，甚至传输失败。这就增加了数据包的传输时延。

相比于EIFC和CADC 路由，CRBD 路由的平均传输时延性能存在优势。这归功于：1）CRBD 路由引用了拥塞控制机制，避免了拥塞节点担任簇头，降低了队列时延；2）CRBD 路由引用了Dijkstra 算法构建最短簇间路径，缩短了数据传输路径。

4 结论

为了缓解节点的能耗，本文提出Dijkstra 算法的分簇路由CRBD。CRBD 路由从优化簇和构建簇间多路由两个阶段减少节点能耗。利用节点的剩余能量以及离汇聚节点间距离信息计算节点权重，再依据权重，择优部分节点作为簇头。并利用贪婪启发式算法，构建簇，优化簇内数据传输路径。同时，利用Dijkstra 算法构建簇间路径，减少簇头的能量消耗。仿真结果表明，提出的CRBD 路由减少了节点能耗，延长了网络寿命，并提升了数据包传递率。