【作者】 赵瑞琴；

【导师】 刘增基；

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

【摘要】 无线多跳网络中,源结点到目的结点之间由多跳的无线链路组成,任意结点既可充当端结点产生或接收数据分组,又可充当中间结点(路由器)对来自其他结点的数据分组进行转发。无线Ad Hoc网络、无线传感器网络以及无线Mesh网络均属于无线多跳网络。无线多跳网络是自组织、自生成和自管理的,容许结点发生故障以及结点随意的加入或离去。无线多跳网络的这些优势引起了人们越来越多的关注。本文从无线多跳网络的各种研究热点出发,分别研究了无线多跳网络的广播机制和无线多跳网络的网络容量提升问题,本文的主要工作与贡献如下:为无线Ad Hoc网络提出了有效延长网络寿命的分布式广播机制(MLDB)。该广播机制中结点不需为有效广播维持过多的拓扑信息,网络中每个结点仅需获取本地一跳邻结点信息就可以完成广播任务。在确定转播结点时,MLDB让那些拥有较多未覆盖邻结点和较大新增覆盖面积的结点进行转播,选取尽可能少的邻结点为转播结点,以减小广播分组在网络中的重复。MLDB的优化设计解决了其他节能广播算法中存在的开销太大的问题,使其更加适用于无线Ad Hoc网络的特殊环境。与其他算法相比,MLDB能够大幅降低转播冗余、有效增加网络寿命。针对无线传感器网络结点体积小、内存与计算能力小、靠电池供电、结点密度高等特点,提出了有效广播协议(EBP)。通过对广播过程中一个结点转播之后引发新转播的讨论,对最佳引发新转播次数和最佳引发新转播位置进行分析。EBP广播协议基于上述分析的结论选择转播结点,它不需要任何邻结点信息就可以高效完成广播,因此算法的控制开销和存储开销大大降低。EBP广播协议简单有效,在无线传感器网络中具有良好的扩展性。提出了适用于大规模高密度无线多跳网络的最少冗余广播算法LRBA。该算法采用一种行之有效的将顶点转播策略与结点的度相结合的机制,最大程度地减小转播冗余。通过对广播算法转播率进行理论分析,得出了理论的最大转播率和最小转播率。基于不同的自延时计算方法,分别给出了LRBA广播算法的两种实现方式LRBA1和LRBA2,通过仿真分析比较研究了这两种广播机制的广播覆盖率、转播率、时延以及能耗等性能,并指出其中综合性能较好的方法。仿真结果表明LRBA广播算法对于网络结点密度和网络规模有很好的扩展性。尽管LRBA广播算法的存储和计算开销要稍大于EBP算法,但它能获得比EBP及其他算法更低的转播率,特别适用于大规模、高密度且结点具有较好处理能力的无线多跳网络,例如无线mesh网。最后,研究并分析了基于扫描的定向邻居发现算法,提出了一种非辅助定向邻居发现算法(UADND),该算法能够充分利用智能天线给无线多跳网络带来的各种优势。UADND可以在不依赖GPS、时间同步等措施的条件下为无线多跳网络发现那些只有通过定向收发才能到达的邻结点,使通过采用智能天线提升网络容量成为可能。UADND利用跨层设计思想,将邻居发现与无线多跳网络路由机制结合起来。仿真表明,与其他定向邻居发现算法相比,UADND能够以较小的控制开销和较低的能耗完成无线多跳网络的定向邻居发现。更多还原

【Abstract】 Wireless multi-hop networks (WMHN) consist of nodes that freely and dynamically self-organize into arbitrary and temporary network topology, where source nodes and destination nodes are connected by multiple wireless links. Each node in WMHN is both a host that is the source or sink of packets and a router that relays packets for other nodes. Wireless ad hoc network, wireless sensor network and wireless mesh network are three typical wireless multi-hop networks. Wireless multi-hop networks are self-forming, self-managing and self-healing networks, allowing the random entrance and exit of nodes, and automatically rerouting communications around points of failure. These features and benefits of WMHN have been attracting attentions of many researchers in last several years. Starting from the intense active areas of research in wireless multi-hop networks, network wide broadcasting mechanisms and the improvement of network capacity for wireless multi-hop networks are studied in this paper. The main research works and results are listed as follows:An efficient broadcast mechanism——maximum life-time distributed broadcast (MLDB) method is proposed in this paper. To complete a broadcast across the network, all nodes need only maintain relevant information of their one-hop neighbors in MLDB. With the aim of selecting as less rebroadcast nodes as possible, MLDB chooses nodes with more uncovered neighbors and with larger new coverage area to do rebroadcast, thus reducing the redundant rebroadcasted packets in the network. The optimized design determines the little overhead of MLDB, which is applicable in the special wireless environment of wireless ad hoc networks. Compared with other algorithms, MLDB is capable of saving more rebroadcasts and obtaining longer useful network life-time under all circumstances.Wireless sensor network is featured by small node size and memory, low computing capability, battery supplied constrained energy and high node density. In view of the above features of wireless sensor network, an effective broadcast protocol (EBP) is presented in this paper. Through the discussion on the induced rebroadcast of a node’s rebroadcast, the times and locations of the optimized induced rebroadcast are analyzed. In EBP, optimized rebroadcast nodes are selected based on the above analysis results and each node needs not any neighbor information to complete a broadcast efficiently. Thus, the control and memory overheads are decreased greatly. The simple and effective EBP algorithm performs well in wireless sensor network.A new broadcast algorithm called least redundancy broadcast algorithm (LRBA) is presented for large scale wireless multi-hop networks with dense nodes deployment. To decrease redundant rebroadcast, the vertex rebroadcast mechanism and node degree are combined by LRBA. The theoretical analysis on the rebroadcast ratio is completed, and the theoretical maximum and minimum rebroadcast ratio of LRBA is obtained. Based on different self-delay mechanisms, two implementing methods of LRBA are proposed. They are LRBA1 and LRBA2. Though simulations and comparisons of the reachability, rebroadcast ratio, delay and energy consumption performances of the two methods, the better one in overall performance is pointed out. Simulation results show that LRBA is scalable in large scale wireless multi-hop networks with dense nodes deployment. Though it has more memory and computation overheads than EBP, LRBA obtains lower rebroadcast ratio than other algorithms. LRBA is especially applicable to dense, large scale wireless multi-hop networks with a certain node processing power, such as wireless mesh network.The sweeping based directional neighbor discovery algorithm is studied and analyzed. To obtain the potentials offered by smart antennas, an unaided directional neighbor discovery (UADND) algorithm is proposed for wireless multi-hop networks. With UADND, network nodes could independently discover neighbors that can be reached only when both of transmission and reception are directional, thus the capacity of the networks could be expanded. Additional information provided by GPS or other methods, such as node position or synchronization information utilized by other neighbor discovery algorithms is not necessitated in UADND. Cross layer design is used in UADND to integrate directional neighbor discovery with routing. Simulation results show that compared with other algorithms UADND completes directional neighbor discovery with less control overhead and energy consumption.更多还原