Performance Evaluation of Routing Protocols for Ad Hoc Wireless Networks

A mobile ad hoc network is a collection of autonomous mobile nodes that communicate with each other over wireless links. Such networks are expected to play an increasingly important role in future civilian and military settings, being useful for providing communication support where no fixed infrastructure exists or the deployment of a fixed infrastructure is not economically profitable and movement of communicating parties is possible. However, since there is no stationary infrastructure such as base stations, mobile hosts need to operate as routers in order to maintain the information about the network connectivity. Therefore, a number of routing protocols have been proposed for ad hoc wireless networks. In this paper, we study and compare the performance of the following routing protocols AODV, PAODV (preemptive AODV), CBRP, DSR, and DSDV. A variety of workload and scenarios, as characterized by mobility, load and size of the ad hoc network were simulated. Our results indicate that despite its improvement in reducing route request packets, CBRP has a higher overhead than DSR because of its periodic hello messages while AODV's end-to-end packet delay is the shortest when compared to DSR and CBRP. PAODV has shown little improvements over AODV.     

依据用户妥善安排的多址接入协议在分布式无线网络中的性能研究

本文基于有效竞争预约接入、无冲突轮询传输的思想提出了在多跳分布式无线网络中支持节点移动性和多跳网络结构的依据用户妥善安排的多址接入(UPMA)协议.该协议能够保证发送节点快速接入信道,从而大大提高信道的使用效率.用仿真方法研究了多跳分布式无线网络中采用该协议时的网络性能.结果表明,UPMA协议可以提供较高的通过量、较低的平均分组时延和较小的平均分组丢失率.     

Design and Performance Analysis of a Proxy-Based Indirect Routing Scheme in Ad Hoc Wireless Networks

The majority of existing ad hoc network routing protocols has a tendency to use the shortest single path from a source to a destination. However, in constantly changing topologies such as those in mobile ad hoc wireless networks, the shortest single path is not only unreliable for reachability but also unsuitable for traffic load equilibrium. In order to improve routing performance and make optimum use of the limited resources, the congestion must first be relieved as much as possible and the routing path be made available at all times. In this paper, we propose a novel scheme, called the Applicative Indirect Routing (AIR), to control network traffic congestion and refine route availability by coping with unreliable links quickly. The proposed scheme, acting as a proactive routing protocol, utilizes additional information about the neighbors shared by the sender and the receiver to find an alternative for the original path with unreliable links. The additional bandwidth usage in AIR to obtain the information about shared neighbors (defined as proxy candidates) is so minimal that the bandwidth availability for user data traffic is not significantly affected. Extensive simulation experiments show that compared with a conventional proactive protocol, namely Destination-Sequenced Distance Vector (DSDV), the AIR scheme leads to a much improved system performance in terms of packet delivery ratio, average end-to-end packet delay, and network reliability. We further show that, in terms of packet delivery ratio, AIR is also a competitive protocol compared with such reactive protocols as Ad hoc On Demand Distance Vector (AODV) and Dynamic Source Routing (DSR).     

A Clock Synchronization Algorithm for Multihop Wireless Ad Hoc Networks

In multihop wireless ad hoc networks, it is important that all mobile hosts are synchronized. Synchronization is necessary for power management and for frequency hopping spread spectrum (FHSS) operations. IEEE 802.11 standards specify a clock synchronization protocol but this protocol suffers from the scalability problem due to its inefficiency contention mechanism. In this paper, we propose an automatic self-time-correcting procedure (ASP) to achieve clock synchronization in a multihop environment. Our ASP has two features. First, a faster host has higher priority to send its timing information out than a slower one. Second, after collecting enough timing information, a slower host can synchronize to the faster one by self-correcting its timer periodically (which makes it becoming a faster host). Simulation results show that our ASP decreases 60% the average maximum clock drift as compared to the IEEE 802.11 and reduces 99% the number of asynchronism in a large-scale multihop wireless ad hoc networks.     

Checkerboard-Like Routing Protocol for Ad Hoc Mobile Wireless Networks

The main purposes of this article are to relieve broadcast problem, to immunize to some prerequisites, and to reduce the number of transmitted control packets. Broadcasting control packets network-wide is the most direct and common method for finding the required destination node in ad hoc mobile wireless networks; however, this causes a lot of waste of wireless bandwidth. To remedy the problem, routing protocols demanding some prerequisites are proposed; nonetheless, hardly can they be used if these prerequisites are missed or become stale. To efficiently reduce the number of transmitted control packets, our routing protocol partitions the network into interlaced gray districts and white districts by the aid of GPS and inhibits an intermediate node residing in a white district from re-transmitting the received control packets. However, a mobile node residing in a gray district is responsible for re-transmitting them till they reach the destination node. Our routing protocol does not demand any prerequisite except the use of GPS. Each mobile node can always obtain its own location information; furthermore, the information may neither be missed nor become stale. Our routing protocol is easy to be implemented, saves precious wireless bandwidth, and reduces almost half a number of control packets as compared with pure flooding routing protocols.Ying-Kwei Ho received the B.S. degree and M.S. degree in applied mathematics and in electrical engineering from the Chung-Cheng Institute of Technology in 1987 and 1993 respectively and the Ph.D. degree in computer engineering and science from the Yuan-Ze University, Taiwan, R.O.C. He joined the Army of Taiwan, R.O.C. in 1987 and worked as a software engineer. From 1993 to 1997, he was an instructor in the War Game Center of Armed Forces University, Taiwan, R.O.C. He is currently an assistant professor of the Department of Computer Science at Chung-Cheng Institute of Technology. His research interests include mobile computing, wireless network performance simulation and evaluation, and modeling and simulation.Ru-Sheng Liu received the B.S. degree in electrical engineering from the National Cheng-Kung University, Taiwan, in 1972 and the M.S. and Ph.D. degrees in computer science from the University of Texas at Dallas, Richardson, Texas, in 1981 and1985, respectively. He is currently an associate professor in the Department of Computer Engineering and Science at Yuan-Ze University, Chungli, Taiwan. His research interests are in the areas of mobile computing, internet technology, and computer algorithms.     

适于多跳移动Ad Hoc网络的非对称双信道媒质接入控制协议

In order to resolve the hidden and exposed terminal problems and improve the probability of concurrent packet transmissions for multihop Mobile Ad Hoc Networks (MANETs), a novel slotted Asymmetric Dual-Channel Medium Access Control (ADC-MAC) protocol is proposed. It exploits simultaneous reservation with less collisions and collision-free data packet transmissions, and achieves optimal transmission balance on the Control Channel (CCH) and Data Channel (DCH) by adjusting the relationship between Reservation Slot (RS) on the CCH and the data packet Transmission Slot (TS) on the DCH. Transmission interferences can be avoided by only observing CCH for the transmission time of a data packet. The proposed RS and contention micro-slot backoff mechanisms also greatly improve channel access efficiency. Simulation results show that compared to IEEE 802.11 DCF and p-Mc protocols, the proposed protocol can achieve a throughput gain of 88% in single-hop networks and 151% in multihop networks at the same total data rate.     

Minimum-Energy Broadcasting in Static Ad Hoc Wireless Networks

Energy conservation is a critical issue in ad hoc wireless networks for node and network life, as the nodes are powered by batteries only. One major approach for energy conservation is to route a communication session along the route which requires the lowest total energy consumption. This optimization problem is referred to as Minimum-Energy Routing. While the minimum-energy unicast routing problem can be solved in polynomial time by shortest-path algorithms, it remains open whether the minimum-energy broadcast routing problem can be solved in polynomial time, despite the NP-hardness of its general graph version. Recently three greedy heuristics were proposed in [11]: MST (minimum spanning tree), SPT (shortest-path tree), and BIP (broadcasting incremental power). They have been evaluated through simulations in [11], but little is known about their analytical performances. The main contribution of this paper is a quantitative characterization of their performances in terms of approximation ratios. By exploring geometric structures of Euclidean MSTs, we have been able to prove that the approximation ratio of MST is between 6 and 12, and the approximation ratio of BIP is between 13/3 and 12. On the other hand, we show that the approximation ratio of SPT is at least n/2, where n is the number of receiving nodes. To the best of our knowledge, these are the first analytical results for the minimum-energy broadcasting problem.     

无线Ad Hoc网中的TCP SACK与TCP Vegas

本文用仿真方法分析了TCP SACK和Vegas在无线ab hoc网络中的性能，提出了一种改进的SACK选项格式（ASACK）和一种称为环回时间通知（RN）的新技术以分别用于提高TCP SACK和TCP Vegas在无线ab hoc网中的性能。为了研究路由稳定性TCP Vegas性能的影响，我们实现了一种基于相关性的选路协议（ABR）。     

On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks

An ad hoc network is a dynamically reconfigurable wireless network with no fixed infrastructure or central administration. Each host is mobile and must act as a router. Routing and multicasting protocols in ad hoc networks are faced with the challenge of delivering data to destinations through multihop routes in the presence of node movements and topology changes. This paper presents the On-Demand Multicast Routing Protocol (ODMRP) for wireless mobile ad hoc networks. ODMRP is a mesh-based, rather than a conventional tree-based, multicast scheme and uses a forwarding group concept; only a subset of nodes forwards the multicast packets via scoped flooding. It applies on-demand procedures to dynamically build routes and maintain multicast group membership. ODMRP is well suited for ad hoc wireless networks with mobile hosts where bandwidth is limited, topology changes frequently, and power is constrained. We evaluate ODMRP performance with other multicast protocols proposed for ad hoc networks via extensive and detailed simulation.     

A Power Control MAC Protocol for Ad Hoc Networks

This paper presents a power control MAC protocol that allows nodes to vary transmit power level on a per-packet basis. Several researchers have proposed simple modifications of IEEE 802.11 to incorporate power control. The main idea of these power control schemes is to use different power levels for RTS–CTS and DATA–ACK. Specifically, maximum transmit power is used for RTS–CTS, and the minimum required transmit power is used for DATA–ACK transmissions in order to save energy. However, we show that these schemes can degrade network throughput and can result in higher energy consumption than when using IEEE 802.11 without power control. We propose a power control protocol which does not degrade throughput and yields energy saving.     

Distributed Power Control for Energy Efficient Routing in Ad Hoc Networks

In this paper, distributed power control is proposed as a means to improve the energy efficiency of routing algorithms in ad hoc networks. Each node in the network estimates the power necessary to reach its own neighbors, and this power estimate is used both for tuning the transmit power (thereby reducing interference and energy consumption) and as the link cost for minimum energy routing. With reference to classic routing algorithms, such as Dijkstra and Link State, as well as more recently proposed ad hoc routing schemes, such as AODV, we demonstrate by extensive simulations that in many cases of interest our scheme provides substantial transmit energy savings while introducing limited degradation in terms of throughput and delay.     

Probabilistic Power Management for Wireless Ad Hoc Networks

Extending system lifetime by effectively managing power on participating nodes is critical in wireless ad hoc networks. Recent work has shown that, by appropriately powering off nodes, energy may be significantly saved up to a factor of two, especially when node density is high. Such approaches rely on the selection of a virtual backbone (i.e., a connected dominating set) of the topology to forward ongoing traffic, coupled with algorithms to manually and periodically recompute such a backbone for load balancing purposes. The common drawback of such schemes is the need to involve periodic message exchanges and to make additional restrictive assumptions. This paper presents Odds¹, an integrated set of energy-efficient and fully distributed algorithms for power management in wireless ad hoc networks. Odds build on the observation that explicit and periodic re-computation of the backbone topology is costly with respect to its additional bandwidth overhead, especially when nodes are densely populated or highly mobile. Building on a fully probabilistic approach, Odds seek to make a minimum overhead, perfectly balanced, and fully localized decision on each node with respect to when and how long it needs to enter standby mode to conserve energy. Such a decision does not rely on periodic message broadcasts in the local neighborhood, so that Odds are scalable as node density increases. Detailed mathematical analysis, discussions and simulation results have shown that Odds are indeed able to achieve our objectives while operating in a wide range of density and traffic loads.Zongpeng Li received his B.Engr. in 1999, from Department of Computer Science and Technology, Tsinghua University, China, and his M.S. degree in 2001 from the Department of Computer Science, University of Toronto. He is currently working towards his Ph.D. degree in the Department of Electrical and Computer Engineering, University of Toronto. His research interests include algorithm design and analysis for both wireless and wireline networks.Baochun Li received his B.Engr. degree in 1995 from Department of Computer Science and Technology, Tsinghua University, China, and his M.S. and Ph.D. degrees in 1997 and 2000 from the Department of Computer Science, University of Illinois at Urbana-Champaign. Since 2000, he has been with the Department of Electrical and Computer Engineering at the University of Toronto, where he is an Assistant Professor. In 2000, he was the recipient of the IEEE Communications Society Leonard G. Abraham Award in the Field of Communications Systems. His research interests include network-level and application-level Quality of Service provisioning, application-layer overlay networks, wireless ad hoc networks, and mobile computing.     

无线Ad Hoc网络中基于业务感知的多信道MAC协议(英文)

Existing multi-channel Medium Access Control (MAC) protocols have been demonstrated to significantly increase wireless network performance compared to single channel MAC protocols. Traditionally, the channelization structure in IEEE 802.11 based wireless networks is pre-configured, and the entire available spectrum is divided into subchannels and equal channel widths. In contrast, this paper presents a Traffic-Aware Channelization MAC (TAC-MAC) protocol for wireless ad hoc networks, where each node is equipped with a single half duplex transceiver. TAC-MAC works in a distributed, fine-grai-ned manner, which dynamically divides variable-width subchannels and allocates subchannel width based on the Orthogonal Frequency Division Multiplexing (OFDM) technique according to the traffic demands of nodes. Simulations show that the TAC-MAC can significantly improve network throughput and reduce packet delay compared with both fixed-width multi-channel MAC and single channel 802.11 protocols, which illustrates a new paradigm for high-efficient multi-channel MAC design in wireless ad hoc networks.     

A Cross-layer Approach to Channel Assignment in Wireless Ad Hoc Networks

To improve the capacity of wireless ad hoc networks by exploiting multiple available channels, we propose a distributed channel assignment protocol that is based on a cross-layer approach. By combining channel assignment with routing protocols, the proposed channel assignment protocol is shown to require fewer channels and exhibit lower communication, computation, and storage complexity than existing channel assignment schemes. A multi-channel MAC (MC-MAC) protocol that works with the proposed channel assignment protocol is also presented. We prove the correctness of the proposed channel assignment protocol. In addition, through a performance study, we show that the proposed protocol can substantially increase throughput and reduce delay in wireless ad hoc networks, compared to the IEEE 802.11 MAC protocol and an existing multi-channel scheme.

移动无线ad hoc网络吞吐量的计算

在网络拓扑满足网络各种不同性能指标下,本文提出了一种新的转发策略和功率控制策略来估计ad hoc网络的吞吐量.实验结果证明:该方法能够有效的估算和提高ad hoc网络的吞吐量.     

ABRP: Anchor-based Routing Protocol for Mobile Ad Hoc Networks

Ad hoc networks, which do not rely on any infrastructure such as access points or base stations, can be deployed rapidly and inexpensively even in situations with geographical or time constraints. Ad hoc networks are attractive in both military and disaster situations and also in commercial uses like sensor networks or conferencing. In ad hoc networks, each node acts both as a router and as a host. The topology of an ad hoc network may change dynamically, which makes it difficult to design an efficient routing protocol. As more and more wireless devices connect to the network, it is important to design a scalable routing protocol for ad hoc networks. In this paper, we present Anchor-based Routing Protocol (ABRP), a scalable routing protocol for ad hoc networks. It is a hybrid routing protocol, which combines the table-based routing strategy with the geographic routing strategy. However, GPS (Global Positioning System) (Kaplan, Understanding GPS principles and Applications, Boston: Artech House publishers, 1996) support is not needed. ABRP consists of a location-based clustering protocol, an intra-cell routing protocol and an inter-cell routing protocol. The location-based clustering protocol divides the network region into different cells. The intra-cell routing protocol routes packets within one cell. The inter-cell routing protocol is used to route packets between nodes in different cells. The combination of intra-cell and inter-cell routing protocol makes ABRP highly scalable, since each node needs to only maintain routes within a cell. The inter-cell routing protocol establishes multiple routes between different cells, which makes ABRP reliable and efficient. We evaluate the performance of ABRP using ns2 simulator. We simulated different size of networks from 200 nodes to 1600 nodes. Simulation results show that ABRP is efficient and scales well to large networks. ABRP combines the advantages of multi-path routing strategy and geographic routing strategy—efficiency and scalability, and avoids the burden—GPS support.     

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.     

PARO: Supporting Dynamic Power Controlled Routing in Wireless Ad Hoc Networks

This paper introduces PARO, a dynamic power controlled routing scheme that helps to minimize the transmission power needed to forward packets between wireless devices in ad hoc networks. Using PARO, one or more intermediate nodes called redirectors elects to forward packets on behalf of source–destination pairs thus reducing the aggregate transmission power consumed by wireless devices. PARO is applicable to a number of networking environments including wireless sensor networks, home networks and mobile ad hoc networks. In this paper, we present the detailed design of PARO and evaluate the protocol using simulation and experimentation. We show through simulation that PARO is capable of outperforming traditional broadcast-based routing protocols (e.g., MANET routing protocols) due to its energy conserving point-to-point on-demand design. We discuss our experiences from an implementation of the protocol in an experimental wireless testbed using off-the-shelf radio technology. We also evaluate the impact of dynamic power controlled routing on traditional network performance metrics such as end-to-end delay and throughput.     

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