【作者】 田野；

【导师】 李建东；

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

【摘要】 无线Ad Hoc网络是一种充满发展潜力的无线网络通信系统,该网络具有的自组织、自配置、自适应以及自愈能力使之能够灵活地用于各种无任何固定通信基础设施支撑的环境。在影响无线Ad Hoc网络性能的众多因素之中,网络的拓扑结构是不可忽视的一个重要方面,因此如何优化Ad Hoc网络的拓扑结构、增强网络拓扑的容错能力并为上层通信协议提供良好的底层拓扑支撑是拓扑控制技术研究的重点。本文从基于能量平衡的分布式拓扑控制技术、关键传输半径问题以及高效的拓扑探测技术三个方面对Ad Hoc网络拓扑控制技术进行研究,并讨论了无线传感器网络MAC地址的分配问题,具体研究成果如下:1.针对现有大多数拓扑控制机制不能有效平衡网络节点能量消耗的问题,本文提出了一种基于能量感知的分布式拓扑控制算法EDTC(Energy-aware Dynamic Topology Control)。通过引入综合反映能量消耗及剩余能量两方面因素的链路代价函数,EDTC能够根据节点能量的实时变化动态优化网络的拓扑结构。同时,无需获取精确的地理位置信息,节点仅根据网络局部区域内的拓扑信息即可确定所需的传输功率,从而完成对全局拓扑结构的优化,极大地降低了算法实现时的复杂度及开销。该算法是一种局部化,轻量级的拓扑控制机制。2.在EDTC算法的基础之上,本文将动态进行拓扑优化的设计思想推广到异质无线Ad Hoc网络,提出了ESATC(Energy-aware Self-Adjust Topology Control)算法。该算法更具一般性,能够用于由多种节点混合组成的无线Ad Hoc网络。理论分析及仿真结果表明,与EDTC算法相同,ESATC算法能够构建具有连通性以及最小代价特性的网络拓扑结构,能够显著地延长网络的“寿命”。3.关键传输半径不仅能够保持网络的连通性,而且能够减小节点的能量消耗和多址干扰,最大化网络容量。为了有效构建具有容错能力的网络拓扑结构,本文主要针对有较广应用范围的一维无线Ad Hoc网络,研究了以一定概率保障其拓扑二连通性的关键传输半径问题。从对网络割点出现概率的分析入手,基于独立性假设,给出了网络二连通概率与网络分布区域大小、节点数目、通信半径间的解析关系。仿真实验表明理论值与仿真值吻合良好,验证了所得结果的正确性。在实际工程中利用所得结论可以合理配置网络参数,从而改善网络拓扑结构在连通性方面的容错能力。4.通过拓扑分割探测的方法预先发现网络连通关系中的薄弱环节,对保障多跳Ad Hoc网络端到端通信具有十分重要的意义。针对网络中极易导致网络拓扑分割的关键节点,本文首先证明了关键节点的判定准则,它从本质上揭示了关键节点i的产生与两个决定性因素(邻节点度Ni以及基本回路度Mi)间的关系,指出Ni-Mi≥2是关键节点i存在的充要条件,极大地方便了关键节点的判定。在此基础之上,结合Ad Hoc网络具体应用背景,提出了一种分布式拓扑分割探测算法DPDP(Distributed Partition Detection Protocol)。通过在局部范围内进行关键节点的探测,该算法能够有效达到网络拓扑分割探测目的。理论分析及实验结果表明:DPDP算法具有复杂度低、准确度高、开销小、扩展性好的特点,与其它算法相比具有较优的性能。5.针对无线传感器网络MAC地址开销较大的问题,本文提出了一种适用于传感器网络的分布式MAC地址分配算法VGSR(Virtual Grid Spatial Reusing)。该算法将网络分布区域划分为一系列虚拟小区,并建立节点地理位置坐标与虚拟小区间的映射关系,通过MAC地址在不同虚拟小区处的空间复用达到减小节点MAC地址长度的目的。通过调整传感器节点的通信半径,VGSR算法能够在不失网络连通性的同时最大限度地降低MAC地址域的大小。理论分析和实验结果表明,该算法能够很好地适应网络规模的变化,具有消耗能量低和效率改善明显的特点,其性能优于现有的其他算法。更多还原

【Abstract】 Wireless Ad Hoc network is formed by a collection of mobile, wireless devices that cooperatively route packets for each other without any aid of fixed infrastructure or centralized administration, and is a self-organizing and self-configuring multi-hop wireless communication system. In such a type of network, topology structure which is determined by the node position and transmission range has significant effect on network performance. Therefore, how to optimize network structure and enhance network survivability so as to provide underlying topology with desired property for upper layer communication protocol is major concern of topology control technology. In this dissertation, the topology control technology for wireless Ad Hoc networks is studied in three aspects: energy-based distributed topology control, critical transmitting range and topology partition detection. Meanwhile, MAC address assignment problem for wireless sensor networks is also discussed. The main achievements and results of this dissertation are listed as follows:1. To address the problem that most of existing algorithms can not balance energy consumption and extend network lifetime efficiently, a lightweight dynamic topology control algorithm EDTC (Energy-aware Dynamic Topology Control) is proposed. Based on the link metric reflecting both the energy consumption rates and residual energy levels at the two end nodes, EDTC generates a dynamic network topology that changes with the variation of node energy. In addition, without the aid of location information, each node determines its transmission power according to local network information, which reduces the complexity and overhead greatly.2. Based on EDTC, a localized distributed topology control algorithm called ESATC (Energy-aware Self-Adjusted Topology Control) is proposed for heterogeneous wireless Ad Hoc networks. It extends the idea of dynamic optimization into hybrid wireless networks and becomes more generalized. Theoretic analysis and experiment results show that just like EDTC, ESATC algorithm preserves network connectivity and minimum-cost property and it can extend network lifetime remarkably. 3. Biconnectivity is the baseline graph theoretic metric of fault tolerance to node failures which can keep network connectivity while allowing unexpected node failures. In this dissertation this property for one-dimensional wireless Ad Hoc networks with finite nodes is analyzed. With common adopted assumption of uniform node distribution for static networks, the formula for the critical transmitting range that realizes network biconnectivity with certain probability is derived via proposed independency approximation assumptions. Simulation results validate the accuracy of our conclusion and confirm its efficiency in practical network design.4. As the failure of a critical node will directly partition a network, a theorem for critical node identification is proved, which indicates that node degree Ni and elementary loop degree Mi of node i are two decisive factors for the existence of a critical node and shows that Ni-Mi≥2 is the necessary and sufficient condition for node i being critical. Based on the theorem, a distributed topology partition detection algorithm called DPDP (Distributed Partition Detection Protocol) is presented for large scale networks, which achieves the goal of partition detection efficiently by detecting critical nodes in a local area. Theoretic analysis and experiment results show that DPDP has the advantages of low complexity, high accuracy, low cost as well as good scalability, and is superior to other algorithms.5. Compared with the small overhead of data payload in wireless sensor network, the overhead of MAC address is significant in terms of energy-saving. In this dissertation, a novel distributed MAC address assignment algorithm named VGSR (Virtual Grid Spatial Reusing) is proposed, which reduces the size of the MAC address efficiently based on both the spatial reuse of MAC addresses and the mapping of geographical position. By adjusting the communication range of sensor nodes, VGSR can minimize the size of MAC address and meanwhile guarantee the connectivity of sensor network. The theoretic analysis and experiment result show that VGSR is low energy cost, but also it scales well with the network size. Its performance is superior to other existing algorithm.更多还原