Abstract: The problem in localization of wireless sensor network has been noticed widely and emphatically at home and abroad all the time, thus researchers has proposed many localization algorithms, and they obtain a large number of achievements. Based on results and conclusions that given, inspired by graph theory, wireless sensor network is regarded as a connected undirected graph. An improved greedy algorithm is proposed and enhances the capability of jumping out the local optimum. This method uses a mobile anchor traversing the whole graph, and then obtains all localizations. This method has better properties in localization precision and system energy expenditure from the complexity analysis and experiment.

Key words: wireless sensor networks, localization, improved greedy algorithm, mobile anchor, graph theory

摘要： 无线传感器网络中的节点定位问题一直是一个倍受国内外关注的问题，由此已经提出了很多定位算法，并取得了很好的成果。在总结已有成果的基础上，受到图论的启发，将无线传感器网络当成是一个连通的节点无向图，提出了一种改进的贪婪算法，提高了算法跳出局部最优的能力。该算法采用单个移动锚节点遍历整个图，从而实现了对所有节点的定位。分析与实验表明该方法在定位精度和系统能量消耗方面都具有很好的性能。

关键词: 无线传感器网络, 定位, 改进贪婪算法, 移动锚节点, 图论