无线传感器网络中基于MDS-MCC问题的启发式算法研究

J4 ›› 2013, Vol. 35 ›› Issue (4): 53-58.

无线传感器网络中基于MDS-MCC问题的启发式算法研究

夏韵，陈志刚，曾锋

（中南大学信息科学与工程学院，湖南长沙 410083）

收稿日期:2012-02-23 修回日期:2012-05-16 出版日期:2013-04-25 发布日期:2013-04-25
基金资助:
国家自然科学基金资助项目(61073186，61103202)；中南大学中央高校基本科研业务费专项资金资助(2011QNZT023)

Research of heuristic algorithm based on
MDSMCC problem in wireless sensor networks

XIA Yun,CHEN Zhigang，ZENG Feng

(School of Information Science and Engineering,Central South University,Changsha 410083,China)

Received:2012-02-23 Revised:2012-05-16 Online:2013-04-25 Published:2013-04-25

摘要/Abstract

摘要：

在保证覆盖和连通性的情况下，通过节能技术延长网络寿命是无线传感器网络的核心研究之一。基于MDSMCC问题的启发式算法利用睡眠机制实现节能，该算法使用以路径长度为优先考虑因子的greedy策略选择最大不相交集合，但是使用该策略不能得到最大不相交集合个数，因此本文针对该策略提出了以覆盖为主要考虑因子的基于DFS和BFS结合的搜索算法（DBFS）。本文建立的模型是以不相交集合个数为网络寿命的衡量标准的，不相交集合个数越多表明网络寿命越长，仿真实验结果证明，从不相交集合的个数（也就是网络寿命）以及实验结果的稳定性来看，DBFS算法要优于greedy策略。

关键词: 网络寿命, greedy策略, DBFS, 不相交集合

Abstract:

Under the circumstance of maintaining coverage and connectivity of wireless sensor networks, to extend the lifetime of networks through energy conservation technique is a critical issue. A heuristic algorithm based on the MDSMCC problem takes advantages of power aware organization to acquire long lifetime, and it uses greedy strategy to select maximum disjoint sets, the strategy selects the nodes which has the shortest path. Combining DFS and BFS, the paper proposed a new method called DBFS. The DBFS method takes the coverage as the first consideration to select disjoint sets. The simulation results prove that the performance of DBFS is better than greedy strategy in terms of the number of disjoint sets and the stability in different networks respectively.

Key words: lifetime of networks;greedy strategy;DBFS;disjoint sets

夏韵，陈志刚，曾锋. 无线传感器网络中基于MDS-MCC问题的启发式算法研究[J]. J4, 2013, 35(4): 53-58.

XIA Yun,CHEN Zhigang，ZENG Feng. Research of heuristic algorithm based on
MDSMCC problem in wireless sensor networks [J]. J4, 2013, 35(4): 53-58.