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.     

自组网技术及其互连

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

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

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

Ad Hoc网络中的节能机制

Ad Hoc网络终端的连续工作时间是影响Ad Hoc网络实用化的关键因素,产业界也一直在寻求通过采用节能机制来延长终端工作时间的方法。本文对Ad Hoc网络中典型的节能机制进行了分类介绍和比较,对运用节能机制所面临的困难给予了阐述,最后给出了节能研究的发展方向。     

Ad Hoc网络中QoS技术研究

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

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

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

基于双变量泊松点过程的无线Ad Hoc网络的保密广播传输容量分析

本论文利用双变量泊松点过程对无线ad hoc广播网络和非法窃听网络共存的网络场景进行建模,运用随机几何工具,研究了无线ad hoc网络的保密广播传输容量,其定义为未发生窃听中断的广播发送节点密度、广播发送节点的相邻接收节点数量的平均值与保密速率的乘积.针对一般衰落和瑞利衰落信道条件,论文推导了造成保密中断的相邻窃听节点数量的平均值和保密广播传输容量的表达式.分析结果表明,与不存在相关性的网络场景相比,广播网络和窃听网络间的相关性会带来的保密广播传输容量的损失.     

无线自组网技术应用

针对Ad Hoc网络良好的灵活性和健壮性在介绍其基本结构和特点的基础上,说明了Ad Hoc网络的技术难点、解决方法并展望了发展前景。     

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.     

Cross-Layering Approaches in Wireless Ad Hoc Networks

Wireless ad hoc networks are temporary formed, infrastructureless networks. Due to the unstable channel conditions and network connectivity, their characteristics impose serious challenges in front of network designers. The layering approach to network design does not fit the ad hoc environment well. Therefore, various cross-layering approaches, where protocol layers actively interact, exchange inherent layer information and fine tune their parameters according to the network status are becoming increasingly popular. This paper presents an in-depth analysis of the latest cross-layering approaches for wireless ad hoc networks supported by several examples. A special emphasis is put on the link and network layer related cross-layer designs. Several link adaptation and efficient service discovery schemes are elaborated through analytical and simulation studies. Their performance shows the potentials of the cross-layering for boosting system characteristics in wireless ad hoc networks. Liljana Gavrilovska currently holds a position of full professor at Faculty of Electrical Engineering, University “St. Cyril and Metodij” – Skopje, Macedonia. She is chief of Telecommunications Laboratory and teaches undergraduate courses in telecommunication networks, data transmission and switching and traffic theory, and graduate courses in wireless, mobile and personal networks, teletraffic engineering and planning, and broadband multiservices networks. In 2000 she joined the Center for PersonKommunikation, Aalborg University, Denmark, as a visiting professor and during 2001--2002 she held a position of associate research professor at the same university. Currently she holds a part-time position of associated research professor with Center for Teleinfrastructur (CTIF). Prof. Gavrilovska was involved in several EU (ACTS ASAP, IST PACWOMAN, MAGNET, TEMPUS) and national/international projects. She published numerous conference and journal papers and participated in several workshops. At the moment she is working on the book “Ad Hoc Networking Towards Seamless Communications” together with prof. R. Prasad. Her research interests include wireless and personal area networks, ad hoc networking, networking protocols, traffic analysis, QoS, and optimization techniques. She is a senior member of IEEE and serves as a Chair of Macedonian Communication Chapter.     

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.     

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