基于最小连通支配集的无线传感网拓扑构建研究-电子与信息学报.PDFVIP

第 34 卷第 8 期 电 子 与 信 息 学 报 Vol.34No.8 2012 年 8 月 Journal of Electronics Information Technology Aug. 2012 基于最小连通支配集的无线传感网拓扑构建研究 洪 榛 俞 立* 张贵军 陈友荣 (浙江工业大学信息工程学院 杭州 310023) 摘 要：基于通信虚拟主干网的拓扑构建是关闭冗余节点，节省全网能耗的有效方法。该文将全连通网络环境下寻 找最优虚拟主干网问题抽象转化成最小连通支配集求解问题(MCDS)，并建立了基于混合整数规划的数学模型 (NMIP-MCDS)。NMIP-MCDS 在分析 MCDS 解的基础上，确定以令牌分发数与节点能耗乘积为目标的优化函数， 通过令牌分发同时辅以全网能量负载均衡的方式，构建最优 MCDS。仿真实验结果验证了 NMIP-MCDS 的有效性， 并可进一步实际应用在中等规模的无线传感网中。 关键词：无线传感器网络；拓扑构建；最小连通支配集；混合整数规划 中图分类号：TP393 文献标识码： A 文章编号：1009-5896(2012)08-2000-07 DOI: 10.3724/SP.J.1146.2011.01029 Topology Construction Based on Minimum Connected Dominating Set for Wireless Sensor Networks Hong Zhen Yu Li Zhang Gui-jun Chen You-rong (College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China) Abstract: Topology construction based on virtual backbone communication is an effective way to shut down redundant nodes and save energy of whole network. In this paper, an issue of finding optimal virtual backbone through fully connected network is abstracted and converted into Minimum Connected Dominating Set (MCDS) issue while a new mathematical modeling approach which is called (NMIP)-MCDS based on Mixed Integer Programming is proposed. Furthermore, with the help of analyzing MCDS solution, the product of token distribution number and energy consumption from nodes are built as the goal of optimization function. Simultaneously, the optimal MCDS is constructed via manner of token distribution and network energy load balancing. Finally, simulation