摘要
本文针对新兴无线传感器网络中的三维空间随机最佳覆盖NP难问题进行了研究.采用计算几何与图论着色方法建立了三维空间的随机最佳覆盖数学模型,给出了一种分布式启发算法,得到了完成最佳覆盖的低能量消耗路径.并在此基础上设计了一种可以实现无线传感器网络三维空间最佳覆盖的优化路由协议.最后进行了协议算法的性能评价以及最佳覆盖和网络生存时间的实验仿真,结果表明协议算法时间复杂度低,并具有可扩展性、有效性和鲁棒性.
This paper analyzed optimal coverage for routing in three-dimensional wireless sensor networks. For this NP-hard combinatorial optimization problem, we proposed a new solution used techniques from Computational Geometry, Graph Coloring and established a new model for optimal coverage. We also proposed an energy-efficient distributed heuristic algorithm to find the optimal coverage routing path. Based on the model and algorithm, we presented a three-dimensional optimal coverage routing protocol in a distributed manner. To evaluate the performance of the algorithm, a time complexity analysis was given for each operation. In the end, we analyzed the coverage quality and compared the network lifetime with several typical protocols. Simulation results show that proposed routing protocol has low time complexity and it is considerably effective, scalable and robust.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2006年第2期306-311,共6页
Acta Electronica Sinica
基金
国家自然科学基金(No.60473001
No.60572037)
北京交通大学优秀博士生科技创新基金(No.48013)
关键词
无线传感器网络
最佳覆盖
路由协议
分布式启发算法
三维空间
wireless sensor networks
optimal coverage
routing protocol
distributed heuristic algorithm
threedimensional
