一种基于协同演化算法的无线传感器网络拓扑设计方法

0 引言

如今，无线传感器网络（WSN）因其高度认可的实用价值而迅速发展。为了不断提高WSN 的相关技术和应用潜力，进行了各种研究和开发。例如，WSN 可用于连续传感，事件检测，位置传感等^[1]。WSN 由低成本，低功耗的多功能传感器组成，其中每个传感器的尺寸都很小，并且在短距离内不受限制地通信。传感器能够检测特定的环境参数、信息处理和无线通信。但是，每个传感器节点只能进行有限数据量的处理。

以前，传感器网络由连接到中央处理站的少量传感器节点组成。在大多数情况下，要监测的环境没有现有的基础设施来提供能源或通信渠道。因此，如何在小而有限的能源上生存并通过无线通信信道进行通信成为WSN 设计的必要条件^[2]。换句话说，WSN 的能耗、覆盖范围和最短路由路径是WSN 设计过程中的关键问题。

如果每个传感器将消息直接传输到中心节点，由于传感器和中心节点之间的距离较长，可能会非常耗电^[3]。然而，由于传感器体积小且储能容量有限，传感器很难将收集信息有效地直接中继到中心节点。在这种情况下，所有传感器都需要直接或间接地将其数据传输到中心节点，通信信号在传感器通信半径范围内与其他传感器节点进行通信^[4]。最小化通信距离且平衡每个节点工作负载的设计可以延长整体网络生命周期^[3]。

如图1 所示，WSN 已解决节能问题，还满足了其他条件，如负载平衡、容错等。在 WSN 中，节点使用集中或分布式方法成为多个集群。传感器检测到和收集的数据通过所选集群的中心节点路由的最优路径传输到网络中心节点^[5]。

与直接与中心节点进行通信相比，集群的形成可以大大降低通信成本。因为功耗与传输距离成正比，并且在集群形成中，传感器节点将数据发送到最近的集群中心节点（主节点），而不是直接发送到可能更远的网络中心节点^[6]。对于那些远离中心节点的主节点，直接通信是不合适的。我们必须找到最短路由路径，必须考虑每个节点的路径距离和工作负载。

最优路由路径是对WSN 性能有重大影响的最重要的设计问题之一^[7-8]。最短路径问题（SPP）是一个经典的网络优化问题。最短路由路径问题的搜索算法有很多，如Dijkstra 算法、Bellman-Ford 算法等。这些算法专为单目标 SPP 设计。然而，多目标SPP（MSPP）是一个NP 难题。MSPP 可以表述为一个用于查找包含指定源节点和目标节点的最小成本路径，MSPP 是许多设计和规划中出现的经典组合优化问题^[9]。

遗传算法（GA）具有很强的并行搜索能力，是多目标优化问题中最有前途的算法之一。GA 和其他相关的进化算法可以解决MSPP 问题，并且它们已成功用于各种实际应用。在本文中，我们使用扩展的GA 方法来解决WSN 拓扑设计问题。与其他方法相比，本文提出的方法可以在更短的时间内获得一组近似最优解。

1 背景与实际工作

目前，已经有不少专家进行了研究来改进WSN 设计。Kumar 等人^[10]旨在提取具有最小能耗的WSN 的最佳集群数。尽管他们采用的分析方法与预测结果一致^[11]，但他们对集群头节点到中心节点的平均距离做出了过于严格的假设。

Si ^[12] 提出了一种用于不同数据传输路径排列的梯度扩散算法，该算法侧重于平衡传输路径上传感器节点的工作量，并提高所有传感器节点的预期寿命。该算法记录可用于构建整个传输路径每个路径段的节点数。通过计算找到最优路径，而且可以降低整体能耗。仿真结果表明，与其他传统算法相比，所提算法节能13.61%。此外，该算法平衡了各传感器节点的负载，降低了能耗，使数据包能够快速发送到最终目的节点。

Chang 和Ramakrishna^[13]提出了一种遗传算法方法来解决最短路径路由问题。他们使用可变长度的染色体及其基因来编码。在位置无关的交叉位点交换部分染色体，突变操作保持了种群的遗传多样性。这个算法可以通过简单的修复功能治愈所有不可行的染色体。

如上所述的WSN 工作很少关注多重目标方面的问题。本文的方法使用 EA 来确定集群头和路由路径的数量和位置，从而最大限度地减少WSN 中的通信距离。

2 建模

通过将WSN 组织成集群形式，可以大大缩短总通信距离，从而节省能源并延长每个节点的预期寿命，均衡主节点的负载。

2.1 定义参数

在本文中，我们假设WSN 要监测的区域是一个平坦的方形表面，并且每个传感器节点都可以检测由传感器半径确定的圆形区域内的所有数据。所有传感器节点都是相同的，并且在部署在唯一的坐标上后，坐标是固定不变的。WSN 模型的参数和变量定义如下：

2.2 数学模型

为了模拟WSN设计问题，我们定义了一个有向图，其中V 是一组M 个主节点，E 是一组边。每个节点的负载对应一个非负，并表示节点k 和节点m 之间的距离。如果节点k 和节点m 之间的距离小于通信半径，则节点k 和节点m 之间存在边。主节点最大覆盖、最小总距离和最佳路由路径的数学模型表述如下：

等式（6）是两个节点之间的距离，它必须小于通信距离，约束（7）确保每个主节点与中心节点之间的距离在通信距离限制范围内，式（8）是集群中节点之间的总距离，式（9）是整个网络的总距离，约束（10）保证主节点数和传感器节点数等于节点总数。式（11）是两个主节点之间的距离。式（14）和式（15）确保除源节点和目标节点外，每个节点不存在或只有两条相邻边。约束（16）和式（17）确保结果是源节点和目标节点之间没有环路的路径。

图2 生态系统中的可协商进化算法

3 协同演化算法

EA 是一种启发式优化方法，灵感来自生物物种遗传特征的自然进化过程^[11]。EA 在为多目标问题找到最佳解决方案方面无效，但它可以快速收敛，找到最优的解决方案。在本文中，我们使用可协商进化算法[14] 来解决多目标WSN 布局问题。NEA 过程如图2 所示，生态系统可用于表示WSN 的整体性能，并且生态系统中物种的进化可用于对相应子问题的进行求解，优化算法进行建模。

首先将WSN 问题划分为N 个子问题，每个问题都可以通过EA 更有效地解决。进行进化过程后，选择一些解决方案作为跨物种进化候选者，然后评估每个子解决方案对系统目标的贡献。从本质上讲，可以识别显著能提高系统目标适应性的基因模式，并在合作伙伴之间共享信息。最优的基因模式可能会在EA 模型之间迁移，以促进对整体解决方案的合理探索，从而避免重复收敛到局部目标，然后重新启动每个EA 模型的演变并迭代该过程，直到满足终止标准。^[14]

图3 NEA优化结果

本文采用合作贝叶斯优化算法（COBOA）实现协商促进。图3 描述了每个物种的每个迭代器使用任何标准的进化算法，从原始种群中选择有较优的解决方案。首先，构建一个用于对子问题进行建模的贝叶斯网络，获得最优的解决方案。然后，使用构建的网络对一些新的候选个体进行采样，新的候选个体与其他种群的代表合作。最后，将评估的新候选个体纳入原始种群。该过程将迭代，直到满足预定义的终止条件。^[16]

4 实验与分析

在本文中，NEA 和CEA（交叉EA-baesd）[15] 都是在Eclipse 环境下使用JAVA 语言编程的。该程序在配置有2.33 GHz CPU 和2.00 GB RAM 的PC 上运行。

图4 显示了当中心节点位于（0，0）时NEA 的优化结果。

图4 NEA优化结果

从图5 和图6 中，我们可以看到NEA 方法取得了更好的结果。图5 显示了与CEA 相比，NEA 发现更短的总通信距离值，图6 分别显示了NEA 和CEA 实现的覆盖值曲线。

图5 距离值曲线

图6 覆盖值曲线

5 结束语

本文提出了一种NEA方法来解决多目标优化问题，例如确定WSN 的布局和路由策略。实验表明，NEA 在复杂环境下提供的决策是有效的。在我们未来的工作中，作者希望改进谈判促进者，以解决建模和解决复杂多目标问题。基于所提出的方法，作者还希望及时实现一个功能齐全的软件应用程序，用于设计真实案例场景的WSN。

参考文献：

[1] 汪清清,王茜,李小平.网络环境下数据交换方案的设计与实现[J].东南大学学报(自然科学版).2007(4):59-66.

[2] ARCHANA B, VIJAY A S P. Sensor networks: an overview[J].University of California, Davis, CA 95616.

[3] 杨平,郑金华.遗传选择算子的比较与研究[J].计算机工程与应用,2007(15)：37-46.

[4] NAVID A, ALIREZA V, XU W Y, et al. Cluster size optimization in sensor networks with decentralized clusterbased protocols [J]. Computer Communications, 2012(35):207-220.

[5] NAVID A, ALIREZA V, XU W Y, et al. Cluster size optimization in sensor networks with decentralized clusterbased protocols [J]. Computer Communications, 2012(35): 207-220.

[6] W. STALLING. High-Speed Networks: TCP/IP and ATM Design Principles[J]. Englewood Cliffs, NJ: Prentice- Hall,1998.

[7] M. K. ALI, F. KAMOUN. Neural networks for shortest path computation and routing in computer networks[J]. IEEE Trans. Neural Networks, 1993,4(11):941–954.

[8] 董红斌,丁蕊.协同演化算法及其应用[M].哈尔滨:哈尔滨工程大学出版社,2021.

[9] D. KUMAR, C.A. TRILOK, R.B. Patel. EEHC: energy efficient heterogeneous clustered scheme for wireless sensor networks[J]. Computer Communication, 2009,32 (4) :662-667.

[10] W.B. HEINZELMAN, A.P. CHANDRAKASAN, H. BALAKRISHNAN, An application-specific protocol architecture for wireless micro-sensor networks[J]. IEEE Transactions on Wireless Communications, 2002 (4) : 660-670.

[11] 何俊辉, 潘正祥.“梯度扩散算法”2011年信息技术与应用学术会议[C],2011.

[12] CHANG W A, R. S. RAMAKRISHNA. A genetic algorithm for shortest path routing”, IEEE transactions on evolutionary computation[J]. 2002,6(12):566-578.

[13] HAO X, LIN H W, T MURATA. Application of negotiable evolutionary algorithm in flexible manufacturing planning and scheduling[C]. Proceedings of 17th International Conference on Industrial Engineering and Engineering Management (IE&EM 2010)

[14] 张丽,林文浩. 基于种群交叉策略遗传算法的无线传感器网络结构设计[D].哈尔滨:哈尔滨工业大学,2012.

[15] HAO X, CHEN X, LIN H W, et al. Cooperative bayesian optimization algorithm: a novel approach to simultaneous multiple resources scheduling problem[C]. Second International Conference on Innovations in Bio-inspired Computing and Applications, 2011.

（本文来源于《电子产品世界》杂志2023年4月期）