华中科技大学硕士学位论文移动约束群组Ad Hoc网络研究姓名：戴维斯申请学位级别：硕士专业：信息与通信工程指导教师：王芙蓉20090525华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 IAbstract Dynamic routing is a crucial, yet very challenging issue in MANETs. A flat structure, imposed on networks by default, fails to yield in large scale dynamic MANETs due to communication overhead 2()O nand scalability. This implies a hierarchical architecture clustering, which is vital for efficient resource utilization and load balancing in large scale dynamic networks such as Ad Hoc and sensor networks. The clustering process entails diffusion of node identities along wireless links to yield virtual homogenous sets, whose members subscribe to some rules, with the net effect of entire network decomposition into overlapping or disjoint clusters. Nodes are assigned to clusters based on geographical adjacency. Frequency re-use, reduced overhead and compact clusters are some of the benefits of clustering. Yet, clustering has some cost implications that result from cluster construction and maintenance. The cost functions include explicit message exchange, ripple effect, frozen period and computation round. Over twenty clustering schemes have been proposed. Empirical evidence indicates that linear clusters often generate multiple gateways and confirms circular/roundish clusters as most stable. Besides, research shows that only three geometric shapes: hexagon, triangle and square, can tessellate an infinite, two dimensional spaces (networks). Mobility-aware circular clusters have not only been contemplated, but also formed. Yet, little attention is afforded to the mobility behavior of the nodes during cluster maintenance phase, a fact that could compromise the circular cluster shape. I propose CAN-MR, a mobility-conscious and situation-specific scheme for maintaining circular clusters. My research extends the work of Basu, P. et al, who proposed formation of a circular cluster, but failed to consistently consider the mobility behavior of nodes in cluster maintenance. I dwell on uniform periodic time for all cluster nodes, which confers to them relative stationary state and consigns them to circular motion. For an arbitrary node n, the propagation path defines a locus of pointsR (radius) distance from the CH, designated as the least mobile of the cluster nodes. The location coordinates are determined using the sine and cosine trigonometric ratios. Yet a node-executable program could also be used in guiding node 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 IIpositioning and movement. Instantaneous node locations are defined by equation of a circle. For sufficiently close consecutive locations, a circle is defined, yet with adequate spacing, the shape can be manipulated to a hexagon or other convenient polygons. This allows clustering to subscribe to frequency re-use equation in cellular networks. Key Words：MANETs, clustering, mobility, mobility metrics, angular velocity 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 VIList of Tables TABLE 1: SUMMERY OF COST FUNCTIONS IN CLUSTERHEAD-BASED MANETS.14 TABLE 2: SUMMERY OF THE EXISTING CLUSTERING SCHEMES.16 TABLE 3 SUMMERY OF ENERGY-EFFICIENT CLUSTERING SCHEMES.31 TABLE 4: SUMMERY OF MOBILITY-AWARE CLUSTERING SCHEMES.44 TABLE 5: LIST OF SIMULATION PARAMETERS.62 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 VIIList of Figures CLASSIFICATION OF WIRELESS NETWORKS.2 ROUTE INVALIDATION IN AD HOC NETWORKS.5 SCHEMATIC PRESENTATION OF CLUSTER STRUCTURE.11 LOWEST ID CLUSTERING ALGORITHM.18 ILLUSTRATION OF 3HBC CLUSTERING ALGORITHM.21 MEMBERSHIP UPDATE IN 3HBC CLUSTERING ALGORITHM.22 OPTIMIZING POWER CONSUMPTION THROUGH NODE PROXIMITY.26 ILLUSTRATION OF CLUSTER MERGE PROCESS IN LOAD BALANCING SCHEMES.32 A GRAPHIC PRESENTATION OF A DOMINATING SET.35 AN ILLUSTRATION OF A CONNECTED DOMINATING SET.37 A WEAKLY CONNECTED DOMINATING SET.39 AN ILLUSTRATION ON MOBILITY-BASED CLUSTERING.40 AGGREGATE RELATIVE MOBILITY CALCULATION.52 ILLUSTRATION OF THE STAGGER ZONE FOR A NODE IN MOTION.56 CAN-MR 1-HOP C