Tree Based Broadcast in Ad Hoc Networks

Although broadcasting using tree structure established in a network is a well known and widely used technique, it is typically claimed to be inappropriate for ad hoc networks, being the maintained tree very sensitive to network changes. On the contrary this paper presents an efficient tree based broadcasting scheme, which is reliable and stable even in case of the ever changing network structure of the ad hoc networks.To achieve this, first, a novel method is presented to maintain a spanning tree in an ad hoc network in a fully distributed, on-line and asynchronous way. Once the tree is established the broadcast itself is performed based on this tree. Some further improvements on the basic algorithm are also presented that reduce the resource requirements even more, increase the stability of the tree, enable the mobility of the nodes to be taken into account and make the method more configurable.As it is shown by simulation, the obtained broadcast scheme is stable, reliable and it uses small amount of resources: the acyclic structure of the broadcast tree ensures that the nodes get the broadcast messages only once, so the broadcast needs little bandwidth and the nodes need not store the recent broadcast messages, reducing the computational and memory requirements.As a byproduct a technique is proposed to measure the mobility of the nodes. This technique needs no additional GPS device or any geographical information but it is based on the stability of the links of the node.Alpár Jüttner received his M. Sc. degree in 1998 at the Eötvös Loránd University of Budapest, where he is currently working on his Ph. D. at Operational Research Departement. He also works as a research fellow at Ericsson Traffic Analysis and Network Performance Laboratory in Budapest, Hungary. His main interests are combinatorial optimization and its applications.Ádám Magi received his M. Sc. degree in 1996 at the Technical University of Budapest in Electrical Engineering. He is currently working on his Ph. D. there. He also works as a research fellow at Ericsson Traffic Analysis and Network Performance Laboratory in Budapest, Hungary. His main interests are mobile ad hoc networks and routing in telecommunication networks.     

Randomized Broadcast Channel Access Algorithms for Ad Hoc Networks

The problem of broadcast channel access in single-hop and multihop ad hoc networks is considered. Two novel randomized and distributed channel access algorithms are developed and analyzed for single-hop and multihop networks, respectively. These algorithms are designed based on maximizing the worst-case channel efficiency, by optimizing some key parameters, including the backoff probability distribution and the slot length. The proposed algorithm for single-hop networks offers significantly higher throughput than the CSMA methods when the traffic load is heavy, while still achieving good performance when the load is light or medium. The proposed algorithm for multihop networks can flexibly adapt to the traffic load, and offers much better throughput performance than the existing broadcast scheduling algorithms in light or medium load.     

Toward Broadcast Reliability in Mobile Ad Hoc Networks with Double Coverage

The broadcast operation, as a fundamental service in mobile ad hoc networks (MANETs), is prone to the broadcast storm problem if forwarding nodes are not carefully designated. The objective of reducing broadcast redundancy while still providing high delivery ratio under high transmission error rate is a major challenge in MANETs. In this paper, we propose a simple broadcast algorithm, called double-covered broadcast (DCB), which takes advantage of broadcast redundancy to improve the delivery ratio in an environment that has rather high transmission error rate. Among the 1-hop neighbors of the sender, only selected forwarding nodes retransmit the broadcast message. Forwarding nodes are selected in such a way that 1) the sender's 2-hop neighbors are covered and 2) the sender's 1-hop neighbors are either forwarding nodes or nonforwarding nodes covered by at least two forwarding neighbors. The retransmissions of the forwarding nodes are received by the sender as the confirmation of their reception of the packet. The nonforwarding 1-hop neighbors of the sender do not acknowledge the reception of the broadcast. If the sender does not detect all its forwarding nodes' retransmissions, it resends the packet until the maximum number of retries is reached. Simulation results show that the proposed broadcast algorithm provides good performance under a high transmission error rate environment     

Collision-Free and Low-Latency Scheduling Algorithm for Broadcast Operation in Wireless Ad Hoc Networks

It is desirable for broadcast operation in wireless ad hoc network to prevent collision and achieve low latency at the same time. In this letter, we propose a greedy broadcast scheduling algorithm based on the graph theory of Maximum Weight Independent Set (MWIS) problem. During each broadcast wave cycle, MWIS is able to find the optimal selection of forwarders so that maximum number of untouched nodes is covered without incurring collision. Numerical results show that this algorithm could produce better performance results than recent 2-step approach.     

无线特定网络--Ad Hoc网络

Ad Hoc网络是一种没有固定结构的无线移动网络。介绍了移动Ad Hoc网络（MANETs)的主特点和与传统有线分组交换网相比的特性,讨论了应用于Ad Hoc网络的路由机制和所需面临的问题。     

Minimizing Recovery State in Geographic Ad Hoc Routing

Geographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use of recovery algorithms when the greedy approach fails. We propose a novel idea based on virtual repositioning of nodes that allows to increase the efficiency of greedy routing and significantly increase the success of the recovery algorithm based on local information alone. We explain the problem of predicting dead ends which the greedy algorithm may reach and bypassing voids in the network, and introduce NEAR, node elevation ad-hoc routing, a solution that incorporates both virtual positioning and routing algorithms that improve performance in ad-hoc networks containing voids. We demonstrate by simulations the advantages of our algorithm over other geographic ad-hoc routing solutions.     

Ad Hoc网络中QoS技术研究

服务质量保障是Ad Hoc网络环境中的一个复杂的急需解决的问题。首先论述了Ad Hoc网络的网络协议模型、QoS服务模型、QoS路由以及QoS保障策略等方面的问题,然后对其进行了综合分析,在此基础上,给出了Ad Hoc网络中不同层次的QoS路由方案以及其未来的研究方向。     

自组网技术及其互连

自组网是由一些带有无线收发装置的移动节点组成的一个多跳的临时自治系统。这种新型的通信支撑环境具有动态变化的拓扑结构,独特的网络特征使得其路由问题、安全问题、QoS等问题成为研究的重点。本文针对自组网技术的这些方面作了简单的介绍。     

基于QoS的Ad Hoc路由协议综述

Ad Hoc网络是由一组带有无线收发装置的移动终端组成的一个多跳的临时性自治系统。随着人们对通信业务要求的不断提高，对带宽、时延、误码率等性能参数提出了不同程度的保障要求，因此要求Ad Hoc网络能够为某些业务提供服务质量（QoS）保障。但由于Ad Hoc网络无线链路的时变特性、网络拓扑结构的动态变化、移动终端设备电池容量受限等特点，使其相对于固定无线网络及有线网络提供有保证且稳定的QoS保障要困难得多，非常具有挑战性。本文对目前几种基于带宽和时延约束的QoS路由协议进行了介绍。     

移动Ad Hoc网络中的安全问题

移动自组网(Mobile Ad HoC Network)是一种无基础设施的无线网络由于它具有开放的媒质、分布式的合作、动态的拓扑结构和受限的网络能力等特点,所以特别容易受到攻击.为此文章结合移动Ad Hoc网络的特点分析了移动Ad Hoc网络面临的安全威胁,并对移动Ad Hoc网络的安全路由和安全报文传送问题进行了详细讨论.     

DV Based Positioning in Ad Hoc Networks

Many ad hoc network protocols and applications assume the knowledge of geographic location of nodes. The absolute position of each networked node is an assumed fact by most sensor networks which can then present the sensed information on a geographical map. Finding position without the aid of GPS in each node of an ad hoc network is important in cases where GPS is either not accessible, or not practical to use due to power, form factor or line of sight conditions. Position would also enable routing in sufficiently isotropic large networks, without the use of large routing tables. We are proposing APS – a localized, distributed, hop by hop positioning algorithm, that works as an extension of both distance vector routing and GPS positioning in order to provide approximate position for all nodes in a network where only a limited fraction of nodes have self positioning capability.     

Ad hoc网络中的路由技术

Ad hoc网络是一些移动节点组成一个多跳的临时性无线自治系统，这种新型的通信网络具有动态变化的拓扑结构和分布控制的网络机制。文中针对Ad hoc网络作了简单的介绍并重点介绍了针对Ad hoc网络特性而提出的路由协议。     

Ad Hoc网络的安全问题和安全策略

AdHoc网络作为一种无线移动网络正成为网络研究,特别是军事研究的一个热点。由于AdHoc网络的特点,其安全问题和安全策略正受到越来越广播的重视。文中介绍了AdHoc网络的特点,论述了AdHoc网络和路由协议的安全问题,最后讨论并提出了AdHoc网络的一些安全策略。     

Route Reservation in Ad Hoc Wireless Networks

This paper investigates whether and when route reservation-based (RB) communication can yield better delay performance than non-reservation-based (NRB) communication in ad hoc wireless networks. In addition to posing this fundamental question, the requirements (in terms of route discovery, medium access control (MAC) protocol, and pipelining, etc.) for making RB switching superior to NRB switching are also identified. A novel analytical framework is developed and the network performance under both RB and NRB schemes is quantified. It is shown that if the aforementioned requirements are met, then RB schemes can indeed yield better delay performance than NRB schemes. This advantage, however, comes at the expense of lower throughput and goodput compared to NRB schemes     

Priority Scheduling in Wireless Ad Hoc Networks

Ad hoc networks formed without the aid of any established infrastructure are typically multi-hop networks. Location dependent contention and hidden terminal problem make priority scheduling in multi-hop networks significantly different from that in wireless LANs. Most of the prior work related to priority scheduling addresses issues in wireless LANs. In this paper, priority scheduling in multi-hop networks is discussed. We propose a scheme using two narrow-band busy tone signals to ensure medium access for high priority source stations. The simulation results demonstrate the effectiveness of the proposed scheme. Xue Yang received the B.E. degree and the M.S. degree from University of Electronic Science and Technology of China. She is currently a Ph.D. candidate at University of Illinois at Urbana-Champaign (UIUC). She is awarded Vodafone-U.S. Foundation Graduate Fellowship from 2003 to 2005. Her current research is in the areas of wireless networking and mobile computing, with the focus on medium access control, quality of service and topology control. Her research advisor is Prof. Nitin Vaidya at UIUC. For more information, please visit Nitin H. Vaidya received the PhD degree from the University of Massachusetts at Amherst. He is presently an Associate Professor of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign (UIUC). He has held visiting positions at Microsoft Research, Sun Microsystems and the Indian Institute of Technology-Bombay. His current research is in the areas of wireless networking and mobile computing. His research has been funded by various agencies, including the National Science Foundation, DARPA, BBN Technologies, Microsoft Research, and Sun Microsystems. Nitin Vaidya is a recipient of a CAREER award from the National Science Foundation. Nitin has served on the program committees of several conferences and workshops, and served as program co-chair for the 2003 ACM MobiCom. He has served as editor for several journals, and presently serves as Editor-in-Chief for IEEE Transactions on Mobile Computing, and as editor-in-chief of ACM SIGMOBILE periodical MC2R. He is a senior member of IEEE and a member of the ACM. For more information, please visit     

Benefit-Based Data Caching in Ad Hoc Networks

Data caching can significantly improve the efficiency of information access in a wireless ad hoc network by reducing the access latency and bandwidth usage. However, designing efficient distributed caching algorithms is nontrivial when network nodes have limited memory. In this article, we consider the cache placement problem of minimizing total data access cost in ad hoc networks with multiple data items and nodes with limited memory capacity. The above optimization problem is known to be NP-hard. Defining benefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers a solution whose benefit is at least 1/4 (1/2 for uniform-size data items) of the optimal benefit. The approximation algorithm is amenable to localized distributed implementation, which is shown via simulations to perform close to the approximation algorithm. Our distributed algorithm naturally extends to networks with mobile nodes. We simulate our distributed algorithm using a network simulator (ns2) and demonstrate that it significantly outperforms another existing caching technique (by Yin and Cao [33]) in all important performance metrics. The performance differential is particularly large in more challenging scenarios such as higher access frequency and smaller memory.     

Efficient Broadcasting in Mobile Ad Hoc Networks

This paper presents two efficient flooding algorithms based on 1-hop neighbor information. In the first part of the paper, we consider sender-based flooding algorithms, specifically the algorithm proposed by Liu et al. In their paper, Liu et al. propose a sender-based flooding algorithm that can achieve local optimality by selecting the minimum number of forwarding nodes in the lowest computational time complexity O(n logn), where n is the number of neighbors. We show that this optimality only holds for a subclass of sender-based algorithms. We propose an efficient sender-based flooding algorithm based on 1-hop neighbor information that reduces the time complexity of computing forwarding nodes to O(n). In Liu's algorithm, n nodes are selected to forward the message in the worst case, whereas in our proposed algorithm, the number of forwarding nodes in the worst case is 11. In the second part of the paper we propose a simple and highly efficient receiver-based flooding algorithm. When nodes are uniformly distributed, we prove that the probability of two neighbor nodes broadcasting the same messageneighbor nodes broadcasting the same message exponentially decreases when the distance between them decreases or when the node density increases. The analytical results are confirmed using simulation.