|
|
论文:2023,Vol:41,Issue(1):73-80 |
|
|
引用本文： |
|
|
万柏麟, 杨奇, 闫中江, 杨懋, 李波. 一种基于动态规划的最小化最大加权响应时间的中心控制节点选举算法[J]. 西北工业大学学报 |
|
|
WAN Bailin, YANG Qi, YAN Zhongjiang, YANG Mao, LI Bo. Central node selection algorithm of minimizing maximum weighted response time based on dynamic programming[J]. Journal of Northwestern Polytechnical University |
|
|
|
|
|
|
|
| 一种基于动态规划的最小化最大加权响应时间的中心控制节点选举算法 |
|
| 万柏麟, 杨奇, 闫中江, 杨懋, 李波 |
|
| 西北工业大学 电子信息学院, 陕西 西安 710072 |
| 摘要: |
| 为了最小化网络中任意节点到达中心控制节点的最大加权响应时间,提出了一种基于动态规划的中心控制节点选举算法。无线网络中的节点和链路的响应时间被建模为网络拓扑图中的节点权值和边权值,进而最小化网络中任意节点到达中心控制节点的最大加权响应时间的中心控制节点选举问题被建模为K-中心问题,其中K表示中心控制节点的个数。采用基于动态规划的插点法可求出任意2个点之间的最小加权响应时间,所建模的K-中心问题被转化为若干个R-控制集问题。将若干个R-控制集问题转化为若干个0-1整数规划问题,采用分支定界的方法逐个求解每个整数规划问题。给出了K=1时上述算法的简化实现方法,证明了所提算法的最优性并分析了算法的复杂度。仿真结果表明,所提算法选举的中心控制算法可最小化网络最大加权响应时间。 |
| 关键词:
无线网络
中心节点选举
动态规划
|
|
| Central node selection algorithm of minimizing maximum weighted response time based on dynamic programming |
|
| WAN Bailin, YANG Qi, YAN Zhongjiang, YANG Mao, LI Bo |
|
| School of Electronics and Information, Northwestern Polytechnical University, Xi'an 710072, China |
| Abstract: |
| In order to minimize the maximum weighted response time for any node in the network to reach the central control node, a central control node election algorithm based on dynamic programming is proposed. Firstly, the response times of nodes and links in the wireless network are modeled as the node weights and edge weights in the network topology, and then the central control node election problem that minimizes the maximum weighted response time for any node in the network to reach the central control node is modeled as the central problem, where represents the number of central control nodes. Then, by using the interpolation method based on dynamic programming, the weighted response time between the two points can be obtained, and the K-central problem modeled is transformed into several R-control set problems. Then, several control R-set problems are transformed into several 0-1 integer programming problems, and each integer programming problem can be solved one by one by using the branch and bound method. Finally, a simplified implementation method based on the above algorithm is given when K=1, the optimality of the proposed algorithm is proved and the complexity of the algorithm is analyzed. Simulation results show that the proposed central control algorithm can minimize the maximum weighted response time of the network. |
| Key words:
wireless network
central node selection
dynamic programming
|
|
| 收稿日期: 2022-05-19
修回日期:
|
| DOI: 10.1051/jnwpu/20234110073 |
| 基金项目: 国家自然科学基金(61771392,61871322,61771390)与航空科学基金(201955053002,201855533035)资助 |
| 通讯作者: 闫中江(1983-),西北工业大学副教授,主要从事无线网络组网协议设计研究。e-mail:zhjyan@nwpu.edu.cn
Email：zhjyan@nwpu.edu.cn |
| 作者简介: 万柏麟(1998-),西北工业大学硕士研究生,主要从事无线自组织网络协议研究。
|
|
| 相关功能 |
|
|
|
|
| 作者相关文章 |
|
| 万柏麟 在本刊中的所有文章 |
| 杨奇 在本刊中的所有文章 |
| 闫中江 在本刊中的所有文章 |
| 杨懋 在本刊中的所有文章 |
| 李波 在本刊中的所有文章 |
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] 林华, 薛静宜. 软件定义网络(SDN)/网络功能虚拟化(NFV)技术研究及部署[J]. 广播电视网络, 2022, 29(1):106-108 LIN Hua, XUE Jingyi. Research and deployment of software definition network(SDN)/network function virtualization(NFV) technology[J]. Radio and Television Network, 2022, 29(1):106-108 (in Chinese)
[2] 杨坤, 吴昊, 刘松洁, 等. 网络中心节点的确定方法、装置及设备节点:中国, CN108075912A[P]. 2018-05-25
[3] 孙耀, 高孟杰, 秦爽, 等. 一种基于无线自组织网络的分布式簇头选举方法:中国, CN110943920B[P]. 2020-10-27
[4] ABIDI W, EZZEDINE T. Fuzzy cluster head election algorithm based on LEACH protocol for wireless sensor networks[C]//2017 13th International Wireless Communications and Mobile Computing Conference, 2017:993-997
[5] DJOUAMA A, ABDENNEBI M. Clusterhead selection algorithm based on energy and mobility in wireless mobile sensor networks[C]//2019 IEEE Symposium on Computers and Communications, 2019:982-986
[6] 李建平, 刘旭, 朱娟萍. 赋权树状网络中R-控制集问题和K-中心问题[J]. 运筹学学报,2009,13(2):111-118 LI Jianping, LIU Xu, ZHU Juanping. R-control set problem and K-center problem in weighted tree network[J]. Journal of Operations Research, 2009, 13(2):111-118 (in Chinese)
[7] 贾银亮, 张驰宇, 梁康武. 基于多重竞争的无线传感器网络簇头选择算法[J]. 传感器与微系统,2018, 37(2):140-142 JIA Yinliang, ZHANG Chiyu, LIANG Kangwu. Cluster head selection algorithm for wireless sensor networks based on multiple competition[J]. Sensors and Microsystems, 2018, 37(2):140-142 (in Chinese)
[8] 魏长宝, 陈中良, 姚汝贤. 车载网中基于模糊逻辑的簇头选择算法[J]. 测控技术, 2016, 35(9):83-86 WEI Changbao, CHEN Zhongliang, YAO Ruxian. Cluster head selection algorithm based on fuzzy logic in vehicle network[J]. Measurement and Control Technology, 2016, 35(9):83-86 (in Chinese)
[9] 刘晓理, 王出航, 王雪. 基于混沌粒子群的改进LEACH算法[J]. 长春工业大学学报, 2021, 42(5):451-454 LIU Xiaoli, WANG Chuhang, WANG Xue. Improved LEACH algorithm based on chaotic particle swarm optimization[J]. Journal of Changchun University of Technology, 2021, 42(5):451-454 (in Chinese)
[10] 刘涛, 庞博. 基于遗传算法的异构无线传感器网络分簇算法[J]. 现代电子技术, 2022, 45(5):25-30 LIU Tao, PANG Bo. Clustering algorithm for heterogeneous wireless sensor networks based on genetic algorithm[J]. Modern Electronic Technology, 2022, 45(5):25-30 (in Chinese)
[11] HAKIMI S. Optimal locations of switching centers and the absolute centers and medians of a graph[J]. Operations Research, 1964, 12(3):450-459
[12] 黄书强, 江秀美, 范人胜. 一种加权距离连续K-中心选址问题求解方法[J]. 小型微型计算机系统, 2020, 41(2):310-315 HUANG Shuqiang, JIANG Xiumei, FAN Rensheng. A weighted distance continuous K-center location problem solving method[J]. Minicomputer System, 2020, 41(2):310-315 (in Chinese)
[13] 刘旭. 赋权树状网络中R-控制集问题和K-中心问题[D]. 昆明:云南大学, 2007 LIU Xu. R-control set problem and K-center problem in weighted tree network[D]. Kunming:Yunnan University, 2007 (in Chinese)
[14] 郝自军, 何尚录. 最短路问题的Floyd算法的若干讨论[J]. 重庆工学院学报, 2008, 138(5):156-159 HAO Zijun, HE Shanglu. Some discussion on Floyd algorithm for the shortest problem[J]. Journal of Chongqing of Technology, 2008, 138(5):156-159 (in Chinese)
[15] 姚恩瑜, 何勇, 陈仕平. 数学规划与组合优化[M]. 杭州:浙江大学出版社, 2001 YAO Enyu, HE Yong, CHEN Shiping. Mathematical planning and combination optimization[M]. Hangzhou:Zhejiang University Press, 2001 (in Chinese) |
|
|
|
|
|
|
|
