|
|||||
|
|
| 基于模拟植物生长算法的求解MCCS问题的研究 | |
| 引用本文： | 丁雪枫,马良,丁雪松. 基于模拟植物生长算法的求解MCCS问题的研究[J]. 计算机工程与设计, 2010, 31(7) |
| 作者姓名： | 丁雪枫 马良 丁雪松 |
| 作者单位： | 1. 上海理工大学管理学院,上海,200093;长春理工大学计算机学院,吉林,长春,130022 2. 上海理工大学管理学院,上海,200093 3. 吉林大学商学院,吉林,长春,130000 |
| 基金项目： | 国家自然科学基金，上海市重点学科建设基金，上海市研究生创新基金 |
| 摘 要： | 为了降低耗能和减少花费,提出了对无线传感网络设计中的最小连通集合划分的方法.采用对网络进行Voronoi划分成近似覆盖集合,对不满足连通的情况采用一种基于模拟植物生长算法生成Steiner最优树的连通算法来实现网络连通的方法.通过对算法的时间复杂度分析及算例实验,验证了该算法不但可获得最优解,同时精度和性能也有提高,明显优于其它方法. |
| 关 键 词： | 无线传感网络 最小连通覆盖集合 Steiner最优树 形态素浓度 模拟植物生长算法 |
Study on minimal connected cover set problem based on plant growth simulation algorithm |
|
| DING Xue-feng,,MA Liang,DING Xue-song. Study on minimal connected cover set problem based on plant growth simulation algorithm[J]. Computer Engineering and Design, 2010, 31(7) | |
| Authors: | DING Xue-feng MA Liang DING Xue-song |
| Affiliation: | DING Xue-feng1,2,MA Liang1,DING Xue-song3(1.Management Institute,University of Shanghai for Science , Technology,Shanghai 200093,China,2.Computer Institute,Changchun University of Science , Technology,Changchun 130022,3.Business Institute,Jilin University,Changchun 130000,China) |
| Abstract: | To reduce the power consumption and extend the network lifetime, a solution method of dividing the sensor nodes into several minimal connected cover sets is presented. Firstly, a Voronoi tessellation based on approximate algorithm is proposed to construct a near optimal cover set. Then, if the cover set connected condition is not satisfied, a Steiner minimal tree would be constructed based on plant growth simulation algorithm to realise the net' s connectivity. Finally, by analyzing the time complexity of the algorithm and the experimental tests of real instances, the minimal result can be got, while the precision and performance of the presented algorithm is demonstrated better than other methods. |
| Keywords: | wireless sensor network minimal connected cover set Steiner minimal tree morphactin concerntration plant growth simulation algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |