【作者】 沈中；

【导师】 常义林；

【作者基本信息】 西安电子科技大学 ， 通信与信息系统， 2005， 博士

【摘要】 无线Ad Hoc网络是在没有固定基础设施的情况下,由具有无线通信功能的节点自组织形成的网络。网络拓扑结构对网络的性能有着重大的影响,而如何优化网络拓扑结构、提高网络的性能、增强网络的抗毁性、实现网络的快速部署和快速重新配置是拓扑管理研究的主要内容。本文从分层网络管理体系结构、拓扑控制、高效的广播技术这三个方面研究了拓扑管理问题,具体研究成果如下:1.为了减少节点的移动给分层网络管理结构带来的影响,提高节点的可控性,在分析Ad Hoc网络移动模型的基础上,提出了利用节点之间链路有效的概率来定量评估群首的稳定性,并且在群首稳定程度下降时迁移管理服务的群维护算法。该算法减少了网络节点移动带来的影响,增加了群的稳定性、改善了管理的连贯性和提高了节点的可控性,同时该算法显著降低了网络管理的开销。2.提出了一个基于最短路径树的拓扑维护算法,该算法在拓扑变化时首先触发失效节点的邻节点响应(即重新运行拓扑控制算法),在不增加额外通信开销的情况下,响应的节点根据相互发送的Hello分组来判断网络是否连通,如果不能确定网络是连通的,那么再触发失效节点的其它可达邻近节点响应以确保网络的连通性。该算法极大程度地减少了拓扑维护的开销,维护后的拓扑结构在功率有效性和功率扩展因子等方面也取得了好的性能。3.提出了一个分布式的拓扑控制算法,由算法产生的拓扑结构具有最小能量特性。更为重要的是,当网络的组成发生动态变化时,算法可以以响应的方式维护全网的连通性和全局的最小能量特性。也就是说,只有发现网络变化的节点才可能需要重新运行拓扑控制算法,而维护后的拓扑结构具有连通性和最小能量特性。该算法不仅适用于同质的无线Ad Hoc网络,而且也适用于异质的网络。4.提出了一个具有容错能力的拓扑控制算法,该算法建立的拓扑既具有最小能量特性,又具有两连通的性质,并且在网络的组成发生动态变化时,算法能够有效地维护网络的两连通性和最小能量特性。5.提出了广播功率效应的概念,广播功率效应反映了有用的产出和投入的关系。转发功率越小,收到广播的节点越多,则广播功率效应越高。在广播功率效应的基础上,提出了一个分布式广播算法,该算法根据动态的广播信息,不断地选择广播功率效应高的节点转发广播,最终建立一颗覆盖全网的广播树。提出的算法不仅远远优于其它分布式算法,而且其性能极为接近集中式的基于功率增量的广播算法。更多还原

【Abstract】 A wireless ad hoc network is a collection of wireless mobile nodes thatself-configure to form a network without the aid of any established infrastructure. Thetopology of a wireless ad hoc network, which is determined by positions andtransmission ranges of nodes, has a significant effect on the network performance.Topology management deals with how to optimize the network topology, improve thenetwork performance, enhance the network survivability and realize quick deploymentand self-configuration of the network. In this thesis, we discuss the problem of topologymanagement from three aspects: the hierarchical network management architecture,topology control and energy-efficient broadcast. The main contributions of this thesisare listed as follows:1. Forming and maintaining clusters are very important in a hierarchical networkmanagement system. By alalyzing the random ad hoc mobility model, we first introducethe notion of cluster availability which provides a quantitative measurement of clusterstability. Furthermore, a cluster maintenance algorithm based on cluster availability isproposed. In this algorithm, a node should continue to function as a cluster head as longas its degree of stability is maintained within a safe boundary. If a node running thecluster head service is on the verge of some degree of instability, then it should stepdown and make arrangements for management service migration, so a more stable nodewithin the cluster can take over as the cluster head. A unique feature of our algorithm isthat it can alleviate the influence caused by mobility, enhance the cluster stability,improve the continuity of management, and make the network management moreefficient.2. A topology maintenance algorithm based on the shortest path tree is proposed. Inthis algorithm, the neighbors of a faulty node are first triggered to respond (i.e., rerunthe topology control algorithm). Without extra communication overhead, eachresponding node determines the network connectivity by the contents of Hello messagessent by its neighbors. If the responding nodes couldn’t ensure that the network isconnected, the other reachable nodes from the fault node are further triggered. Theproposed scheme can efficiently maintain the network connectivity with low overheadand achieve acceptable performance in terms of both power efficiency and powerstretch factor.3. We propose a topology control algorithm for constructing a minimum-energypath-preserving spanning subgraph for a wireless ad hoc network. Not only does theconstructed topology preserve a minimum-energy path between every pair of nodes, butthe entire network connectivity and the global minimum-energy path property can beefficiently maintained in a responsive manner as the network changes dynamically. Thatis, only those nodes that detect network changes may need to rerun the topology controlalgorithm, and the maintained topology preserves the global minimum-energy pathproperty.4. A fault-tolerant topology control algorithm for constructing an energy-efficientspanning subgraph is proposed. The constructed topology has the following properties:(1) it preserves a minimum-energy path between every pair of nodes;(2) it isbiconnected, i.e., it can tolerate any one node failure and avoid network partition.Furthermore, the biconnectivity and the global minimum-energy path property can beefficiently maintained in a responsive manner as the network changes dynamically.5. Broadcast in wireless ad hoc networks is another challenging problem. We firstintroduce the notion of power efficiency which reflects the ratio of the effective oruseful output to the total input for a potential broadcasting node. More specifically, theless power a node use and the more uncovered neighbors it covers, the higher powerefficiency it has. Based on the power efficiency, a localized broadcast algorithm isproposed. Our algorithm uses the dynamic broadcasting information and always selectsthe node which has the highest power efficiency within its 2-hops neighbors to forwardthe broadcasting message, and finally construct a broadcast tree rooted at the source.The proposed algorithm has performances comparable to the centralized broadcastalgorithm based on incremental power and significantly outperforms other existingdistributed broadcast algorithms.更多还原