Ad-Hoc网络中基于位置信息的分簇算法研究.doc

  Ad-Hoc 网络中基于位置信息的分簇算法 研究# 冯延钊，王玉龙** 5 10 15 20 25 30 35 40 （北京邮电大学信息与通信工程学院，北京 100876） 摘要：本文研究了 Ad-Hoc 网络中的节点分簇算法,针对各个算法的实现过程进行了详细介绍, 并着重分析和比较了各个分簇算法的优点和缺点,并在此基础上,研究了一种基于位置信息 的网络分簇算法。此分簇算法的主要思想是根据节点的位置信息进行分簇。基于位置信息的 分簇算法复杂度较低，并且簇头分布均匀，个数适当。仿真结果表明，基于位置信息的分簇 算法簇头个数适中，在网络中分布均匀，从而减少了网络的能量开销，延长了网络的运行时 间，降低了死亡节点的个数，使网络的分层结构更加稳定。 关键词：Ad-Hoc 网络；分簇算法；位置信息；簇头 中图分类号：TN929.5 Research on Location-based Cluster Algorithm in Ad-Hoc Network Feng Yanzhao, WANG Yulong (School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876) Abstract: In this paper, we research on the existing cluster algorithm in Ad-Hoc. We introduct the main idea of the algorithms and compare the algorithms advantage and disadvantage. Based on these, we propose an location-based cluster algorithm. In this algorithm, we use location information to choose the cluster head. The simulation results show that this algorithm reduces the network’s energy consummation, decrease the number of dead nodes, prolong the network’s lifetime and make the layer structure more stable. Keywords: Ad-Hoc; Cluster Algorithm; Location Information; Cluster Head 0 引言 在 Ad Hoc 网络[1]中，基于分簇的层次化体系结构有着非常重要的作用，它能有效降低 系统成本，提供灵活可靠的通信并提高 Ad Hoc 网络的可扩展性。构建这种类型体系结构的 核心在于提供灵活高效的分簇算法，因此，分簇算法设计与开发成为了 Ad Hoc 网络中的一 种核心关键技术，受到了研究人员的广泛重视[2][3]。 分簇算法分类示意图如图 2-1 所示。从不同的角度出发，Ad-Hoc 网络中的分簇算法可 以被划分为不同的类型。比如从传输过程中是否需要依赖于特定的簇头节点，分簇算法可以 被分成基于簇头的分簇算法和非基于簇头的分簇算法。根据选择簇头节点的参数，可以将分 簇算法分为基于 ID 的、基于连接度的、基于地理位置信息的和基于节点权重的。根据簇内 节点到簇头节点的跳数，可以将分簇算法分为一跳成簇和多跳成簇算法[4]。根据分簇算法不 同的执行方式，可以将分簇算法分为集中式的和分布式的[5]。根据算法的优化目标，可以将 分簇算法分为面向维护开销的分簇算法、面向能量优化的分簇算法、面向移动性优化的分簇 算法和面向负载均衡优化的分簇算法[6]。根据分簇算法的应用场景，可以将分簇算法分为静 基金项目：工信部重大专项项目，(项目编号：2010ZX03003-004-03) 作者简介：冯延钊，（1987-），男，硕士研究生主要研究方向：多播传输、分簇算法。 通信联系人：王玉龙，（1969-），男，副教授，硕士研究生导师，主要研究方向：信息与通信理论，下一 代网络技术，移动通信与定位. E-mail: bupt608@ -1-   态分簇算法和动态分簇算法。相对于前面几种分簇算法的分类机制，后面两种分类机制能够 更好的描述分簇算法的特定目标，明确分簇算法的设计目的，也更能方便的对分簇算法进行 比较和评估，因此我们在本文中采用后两种分类机制，着重研究了静态分簇算法和面向能量 优化的分簇算法。 分簇算法分类  传