在任意有线和无线网络中,连通性是保障网络通信最基本的要求.与有线网络相比,由于无线用户移动、节点电量耗尽、网络受到恶意攻击等因素,使得网络连通具有动态性,因此,与有线网络相比研究无线移动网络中的连通性具有更大挑战.作为无线移动网络独有的特点之一,移动性在给无线用户带来诸多便利的同时,也给增强网络连通带来了极大的机遇.比如在不连通的车辆网络中,过往的车辆可作为信息传递的载体；在连通的蜂窝网络中,可移动的通信车可用于改善局部网络的无线通信质量.本文主要研究了如何利用无线用户的移动性增强现有网络的连通性,研究了无线定位问题、网络拓扑修复问题、网络抗毁性问题、和网络k-连通分析等,即论文从研究前提、被动修复、主动预防、和扩展分析等方面,系统的对无线移动网络中的网络连通性进行了研究.论文的主要研究成果和内容如下：1)定位准确的实现节点定位是研究网络连通的先提条件之一.提出了一种基于网格扫描的无线传感器网络定位算法,该算法在每一个未知节点处(已知位置的节点称为锚节点)分布式运行.利用1跳和2跳邻锚节点的位置信息,所提出的算法通过网格扫描的方式确定自己位于每一个网格的概率.最后,将所有概率不为0的网格的平均位置作为自己的估计位置.仿真结果表明,与现有的DLE算法相比,所提出的算法具有更高的定位精度.2)网络分区修复针对不连通的网络分区,为修复网络连通提出了两种基于Steiner树和最小连通支配集(MCDS)的移动控制算法,分别称为SMC和SteinerMcds.SMC首先调用3近似最少Steiner点算法建立一棵包含所有网络节点和Steiner点的Steiner树,然后将引入的Steiner点作为节点移动的目的点,选择并调度一些节点移动到引入的Steiner点上,SMC算法迭代执行直到网络拓扑恢复连通.与SMC算法不同,SteienrMcds算法则首先计算当前各个网络分区的MCDS,然后建立一棵连接所有MCDS节点集合的Steiner树.最后,将所有不在MCDS集合中的节点与引入的Steiner点进行匹配,并将被匹配的节点移动到相应的Steiner点处. SteinerMcds算法迭代执行直到网络连通.仿真结果表明,所提出的SMC和SteinerMcds算法,在算法迭代次数、节点总移动距离、节点平均和最大移动距离等方面,均优于基于分区最小生成树的PMST-UV算法；此外,两种算法中,SMC算法具有较高的算法成功率和较少的移动节点总个数；而SteinerMcds算法则具有较少的迭代次数和较小的节点最大移动距离.3)网络抗毁性研究为增强1-连通网络的抗毁性,提出了一种基于可删除节点的移动控制算法,通过调度节点移动使得1-连通的网络变为2-连通.该研究的主要内容和成果有：在图论中,第一次提出可删除节点的概念.可删除节点有下述优点：当可删除节点u被从连通图G中移除之后,图G既不会分割(不连通),也不会有新的割点出现.进一步的,提出了一种分布式的可删除节点判定算法.提出独立可删除节点集的概念,当所有独立可删除节点集中的节点同时移动时,图G既不会分割(不连通),也不会有新的割点出现；并找到了一种判定独立可删除节点集的充分条件.基于独立可删除节点集及其判定条件,提出了一种分布式的移动控制算法,调度可删除节点向割点移动,从而使得最终的网络拓扑2-连通,并同时最小化移动节点总个数和节点移动总距离.为最小化每个被移动的可删除节点的移动距离,将可删除节点移动到指定割点的问题,建模为最小化可删除节点移动开销的凸优化问题.通过求解该凸问题,可以得到可删除节点最终的移动位置.仿真结果表明,1-连通网络中平均至少有40%的节点为可删除节点,且所提出的可删除节点判定算法能够判定出大部分可删除节点(87%~100%).所提出的上述移动控制算法有下述优点：高成功率(通过调度节点移动可达到最终的网络2-连通)、被移动的节点个数少、总的节点移动距离短等.此外,仿真结果还表明,在同时含有移动节点和不可移动节点的混合网络中,所提出的算法同样有效.4)网络k-连通分析从网络连通角度,研究了车辆网络的特有性质：车辆的离开将导致车辆网络的不连通.由于在k-连通网络中任意(k-1)个节点失效均不会导致网络分割,因此本文将主要分析计算网络k-连通的概率.论文提出了一种新的准确计算网络k-连通概率的方法；由所得的网络k-连通概率,可计算出给定车辆网络所能接受的最多离开车辆的期望值.主要研究结果包括以下几个方面：推导出一维车辆网络k-连通的充分必要条件：当且仅当任意k个连续的车辆间距之和不大于车辆的无线传输半径时,该车辆网络达到k-连通.基于所得到的充分必要条件,推导出了网络k-连通概率的表达式.为准确计算所得的网络k-连通概率的表达式,引入了排序统计学(orderstatistics)中的标记算法(Marking Algorithm),准确计算出网络k-连通概率,并举例说明了表达式的计算过程.特别的,当k=1时,所得概率公式的计算结果与现有文献吻合；当k>1时,通过仿真验证了算法的准确性.仿真结果验证了概率计算结果的准确性,并表明在给定网络范围、无线传输距离的情况下,车辆网络所能接受的最多离开车辆的期望值与车辆的总数具有近似线性关系.