Ad Hoc网络基于权重的AOW分簇算法研究与仿真

摘要：该文首先介绍了ad hoc网络中常见的几种分簇算法以及各自的优缺点，这些分簇算法考虑的因素较为单一。而自适应按需加权（AOW）分簇算法利用加权的思想综合考虑多种因素，在实际应用中可以对影响因素进行取舍，也可以调整各因素的重要性，具有较强的通用性和灵活性。最后通过NS2仿真实验对几种分簇算法进行了比较分析，得出AOW分簇算法根据网络环境的变化动态的调整权值更能适应复杂的网络环境。

关键词：Ad Hoc网络；AOW；分簇

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)36-2602-03

Ad Hoc Network Based on the Weight of the AOW Clustering Algorithm and Simulation

LU Xin-rong1, HUANG Xiao-ling2

(1.Wuhan University,Wuhan 430000,China;2.Jiangxi University of Science and Technology,Ganzhou 341000,China)

Abstract: This article first introduced the Ad Hoc network of several common clustering algorithms, as well as their respective advantages and disadvantages，these algorithm consider to more single，Adaptive On-demand Weighting clustering algorithm (AOW) using weighting thought overall evaluation many kinds of factors, may carry on the choices in the practical application to the influence factor, also may adjust various factors the importance, has the strong versatility and the flexibility. Finally, through NS2 simulation of several sub-cluster algorithm for a comparative analysis，AOW clustering algorithm based on the network environment changes the dynamic of the right to adjust the value in a better position to complex network environment.

Key words: Ad Hoc network;AOW;cluster

1 引言

移动Ad hoc网络是一组带有无线收发装置的移动终端(节点)组成的一个多跳临时性自治系统。Ad hoc网络中所有节点的地位平等，无需设置任何中心控制节点，具有很强的抗毁性。

Ad hoc网络的体系结构可分为平面结构和分级结构[1]，如图1所示。平面结构中，网络中的所有节点的地位平等，理论上不存在瓶颈节点，网络比较健壮。但在网络规模较大，特别是在网络拓扑变化较频繁的情况下，平面结构具有控制开销大，路由经常中断等缺点，并且很难实施集中式的网络管理和控制。在分级结构中，通常将整个Ad hoc网络进行分簇，一个簇（Cluster）通常包括一个簇头和若干个簇成员。簇头负责协调和管理簇内节点，并用于相邻簇之间的通信，而簇成员的功能则较为单一。

分级结构的网络可扩充性好，网络的规模受限制较小。在移动环境中，需要交换的路由和控制信息相对较少，信道的空间重用率高，从而提高了系统容量。当网络拓扑结构发生改变时，可以将这种变化的影响限制在一定的区域内而不会扩散到整个网络中。但是建立和维护簇结构会引入一定的开销，可以通过设计合理的分簇算法来减少这种开销。总之，在Ad Hoc网络中分级结构可以对移动节点进行有效的组织并合理分配网络资源。

2 典型的分簇算法

1) 链路分簇算法（LCA）

链路分簇算法(LCA)[2]是较早提出的一种分簇算法。LCA算法中，邻居节点中具有最高ID的节点成为簇头，并且如果一个节点是其某个邻居节点的ID最高的邻居节点，此节点也成为簇头。该分簇算法的一种实现方法是首先选择ID最高的节点作为簇头。如果次高ID的节点覆盖的范围内存在没有被ID最高的簇头覆盖的节点，那么次高ID节点也成为簇头，否则继续检查下一个ID较高的节点，直到所有节点都属于某个簇。

LCA算法最大的优点就是实现简单，分簇过程中节点的计算量较小。但是，使用LCA算法会产生过多的簇头，特别是当节点按ID递增的顺序线性排列时，此时除第一个节点外，其他节点都是簇头。为了解决上述问题，可以引入簇头消减机制来消除多余的簇头，例如规定如果一个簇的节点都在其他簇头的覆盖范围之内，则取消此簇头的资格。LCA算法的另一个缺点是，没有考虑公平性因素和负载平衡因素。

2) 最小ID分簇算法(LID)

最小ID分簇算法[3]也是基于节点ID的分簇算法之一。最小ID算法对LCA算法作了改进，进一步减少了簇头的个数。算法规定，相邻节点中具有最小ID的节点作为簇头，其一跳邻居节点成为该簇头所在簇的成员节点，并不再参与簇头选举过程。此外，在某些特殊情况下，簇头可以将其职责交付给簇内具有最小ID的成员节点。

最小ID分簇算法计算简单，实现方便，算法收敛较快。在移动环境下，最小ID算法中簇头更新的频率较慢，维护簇花费的开销较小。最小ID算法同样没有考虑公平性因素，也没有考虑负载平衡等因素。因为，该算法倾向于选择ID较小的节点作为簇头，这部分节点由于充当簇头而耗费过多的资源（如能量，处理能力等），不利于延长网络的整体寿命。

3) 最高节点度分簇算法(HID)

最高节点度分簇算法[4]（也称最高连接度算法）借鉴了Internet中选择路由节点的方法，原则是尽量减少路由节点的数目，其目标是提高网络的控制能力和减少簇的数目。每个节点通过交互控制消息来获得邻居节点的数目，然后它将自己的节点度向邻居节点广播。该节点和其相邻节点中具有最大节点度的节点被选为簇头；当节点度相同时，则选择ID较小的节点作为簇头。簇头的一跳邻居节点则成为该簇的成员节点，并不再参与簇生成过程，重复以上过程直到所有节点都加入到某个簇。

最高节点度算法的优点在于网络中簇的数目较少，源目的节点对之间的平均跳数较少，从而减少了分组投递时延。最高节点度算法的缺点是没有对簇中簇成员的个数进行限制。当一个簇中的簇成员过多时，簇头的负担过重，可能会成为网络的瓶颈。而且，当网络中节点的移动性较低时，网络拓扑较稳定，某些节点可能一直充当簇头，直至其能量耗尽，同样不利于延长整个网络的寿命。

4) 最低移动性分簇算法(WM)

节点的移动会造成网络拓扑的变化，为适应节点的移动特性，提高簇结构的稳定性，可以根据节点的移动性为节点分配权重，并依据节点的权重来选举簇头。最低节点移动性分簇算法[5]规定：节点的移动性越高，其权重越低，选择邻居节点中具有最高权重的节点作为簇头，即选择移动性最低的节点作为簇头。在算法的实现中，可采用一种相对移动性指标来表示节点的移动性，节点通过比较收到的来自某一邻居节点的连续两次的信号强度来估计它们之间的相对移动性。下面介绍这种相对移动性指标的计算方法。

[3] Lin C R, Gerla M. A distributed architecture for multimedia in dynamic wireless networks．Global Telecommunications Conference, 1995. GLOBECOM '95, IEEEVolume 2, 13-17 Nov, 1995 Page(s):1468-1472 vol.2 Digital Object Identifier 10.1109.1995,502646 1468-1472.

[4] Gerla M, Tsai J T C．Multicluster, Mobile, Multimedia Radio Network [J]. Wireless Networks,1995,1(3):255-265.

[5] S Basagni. Distributed Clustering for Ad Hoc Networks. International Symposiun on Parallel Architectures, Algorithms and Networks, June 1999. 310-315.

[6] Amis A D, Prakash R. Load-balancing clusters in wireless ad hoc networks. Application-Specific Systems and Software Engineering Technology, 2000 Proceedings 3rd IEEE Symposium on 24-25 March 2000 Page(s):25-32.

[7] Daniel Lihui Gu, Guangyu Pei, Henry Ly, et al. Hierarchical Routing for Multi-Layer Ad-Hoc Wireless Networks with UAVs [A]. in Proceedings of IEEE Milcom 2000[C]. Los Angeles, USA, 2000(10).

[8] 王海涛.Ad Hoc网络的体系结构和分簇算法研究[D].理工大学通信工程学院博士论文,2003(6).

[9] 英春,史美林.自组网体系结构研究[J].通信学报,1999, 20(9).

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”