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

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

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

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.