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网络的吞吐量.     

Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks

In military and rescue applications of mobile ad hoc networks, all the nodes belong to the same authority; therefore, they are motivated to cooperate in order to support the basic functions of the network. In this paper, we consider the case when each node is its own authority and tries to maximize the benefits it gets from the network. More precisely, we assume that the nodes are not willing to forward packets for the benefit of other nodes. This problem may arise in civilian applications of mobile ad hoc networks. In order to stimulate the nodes for packet forwarding, we propose a simple mechanism based on a counter in each node. We study the behavior of the proposed mechanism analytically and by means of simulations, and detail the way in which it could be protected against misuse.     

Internet Connectivity for Ad Hoc Mobile Networks

The growing deployment rate of wireless LANs indicates that wireless networking is rapidly becoming a prevalent form of communication. As users become more accustomed to the use of mobile devices, they increasingly want the additional benefit of roaming. The Mobile IP protocol has been developed as a solution for allowing users to roam outside of their home networks while still retaining network connectivity. The problem with this solution, however, is that the deployment of foreign agents is expensive because their coverage areas are limited due to fading and interference. To reduce the number of foreign agents needed while still maintaining the same coverage, ad hoc network functionality can cooperate with Mobile IP such that multihop routes between mobile nodes and foreign agents can be utilized. In this work, we present a method for enabling the cooperation of Mobile IP and the Ad hoc On-Demand Distance Vector (AODV) routing protocol, such that mobile nodes that are not within direct transmission range of a foreign agent can still obtain Internet connectivity. In addition, we describe how duplicate address detection can be used in these networks to obtain a unique co-located care-of address when a foreign agent is not available.     

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.     

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     

无线adhoc网络中的多径源路由

本文针对无线ad hoc网络提出了一种基于DSR(动态源路由)的路由算法,多径源路由(MSR).MSR对DSR中的路由搜索和路由维护机制进行了扩展,用来解决多径路由问题.本文还提出,在多条路径之间基于测量的RTT进行负载分配.仿真结果表明,MSR在只增加少量网络开销的情况下,提高了TCP和UDP的投递率,降低了丢包率,并减少了端到端之间的延迟以及队列长度,从而有效地减少了网络拥塞.     

Algorithms for Energy-Efficient Multicasting in Static Ad Hoc Wireless Networks

In this paper we address the problem of multicasting in ad hoc wireless networks from the viewpoint of energy efficiency. We discuss the impact of the wireless medium on the multicasting problem and the fundamental trade-offs that arise. We propose and evaluate several algorithms for defining multicast trees for session (or connection-oriented) traffic when transceiver resources are limited. The algorithms select the relay nodes and the corresponding transmission power levels, and achieve different degrees of scalability and performance. We demonstrate that the incorporation of energy considerations into multicast algorithms can, indeed, result in improved energy efficiency.     

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.     

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.     

Performance Evaluation of Directional Adaptive Range Control in Mobile Ad Hoc Networks

This paper presents DARC (Directional Adaptive Range Control), a range control mechanism using directional antennas to be implemented across multiple layers. DARC uses directional reception for range control rather than directional transmission in order to achieve both range extension and high spatial reuse. It adaptively controls the communication range by estimating dynamically changing local network density based on the transmission activities around each network node. The experimental results using simulation with detailed physical layer, IEEE 802.11 DCF MAC, and AODV protocol models have shown the successful adaptation of communication range with DARC for varied network densities and traffic loads. DARC improves the packet delivery ratio by a factor of 9 at the maximum for sparse networks while it maintains the increased network capacity for dense networks. Further, as each node adaptively changes the communication range, the network delivers up to 20% more packets with DARC compared to any fixed range configurations.Mineo Takai is a Principal Development Engineer in the Computer Science Department at University of California, Los Angeles. He received his B.S., M.S. and Ph.D. degrees, all in electrical engineering, from Waseda University, Tokyo, Japan, in 1992, 1994 and 1997 respectively.Dr. Takai’s research interests include parallel and distributed computing, mobile computing and networking, and modeling and simulation of networked systems. He is a member of the ACM, the IEEE and the IEICE.Junlan Zhou received her B.S in Computer Science from Huazhong University of Science and Technology in 1998, her M.Eng in Computer Engineering from Nanyang Technological University in 2001 and her M.S in Computer Science from University of California, Los Angeles in 2003. She is currently a Ph.D candidate in the Computer Science Department at University of California, Los Angeles. Her research interests include modeling and simulation of wireless networks, protocol design and analysis of wireless networks, and broad areas of distributed computing.Rajive Bagrodia is a Professor of Computer Science at UCLA. He obtained a Bachelor of Technology in electrical engineering from the Indian Institute of Technology, Bombay and a Ph.D. in Computer Science from the University of Texas at Austin. Professor Bagrodia’s research interests include~wireless networks, performance modeling and~simulation, and nomadic computing. He has published over a hundred research papers on the preceding topics. The research has been funded by a variety of government and industrial sponsors including the National Science Foundation, Office of Naval Research, and the Defense Advanced Research Projects Agency. He is an associate editor of the ACM Transactions on Modeling and Computer Systems (TOMACS).     

分布式无线网络中的自适应控制协议

本文提出了一种新颖的移动分群算法和分群保持策略,它可以用较少的控制开销快速获得网络的分群控制结构并能适应拓扑结构的变化.采用重叠群方案简单可靠地实现了分群大小的优化,将节点密度高的区域灵活地划分成多个节点数较少的群,增大了每个节点的通信容量.提出了网关智能控制协议,该协议缓解了网关成为多信道分群间通信的瓶颈.     

无线自组织网络极限信道容量增长规律研究

 为了分析和提高无线自组织网络的吞吐能力,提出了无线自组织网络的极限信道容量增长规律(capacity scaling laws)的一般表达式,研究发现单个节点的策略决定了整个无线自组织网络的吞吐能力,证明了使得整个网络吞吐能力最大化的最优策略的存在性。进一步通过应用博弈论,推导得出最优策略,并验证其满足纳什均衡且是演化稳定策略。     

Selecting Forwarding Neighbors in Wireless Ad Hoc Networks

Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as flooding, is to let every node retransmit the message to all its 1-hop neighbors when receiving the first copy of the message. Despite its simplicity, flooding is very inefficient and can result in high redundancy, contention, and collision. One approach to reducing the redundancy is to let each node forward the message only to a small subset of 1-hop neighbors that cover all of the node's 2-hop neighbors. In this paper we propose two practical heuristics for selecting the minimum number of forwarding neighbors: an O(nlogn) time algorithm that selects at most 6 times more forwarding neighbors than the optimum, and an O(nlog² n) time algorithm with an improved approximation ratio of 3, where n is the number of 1- and 2-hop neighbors. The best previously known algorithm, due to Bronnimann and Goodrich [2], guarantees O(1) approximation in O(n ³ logn) time.     

An Extended Dynamic Source Routing Scheme in Ad Hoc Wireless Networks

In this paper we consider a multipath extension to the dynamic source routing (DSR) protocol proposed by Johnson and Maltz, an on-demand routing protocol for ad hoc wireless networks. This extension keeps two node-disjoint paths between the source and destination of a routing process without introducing extra overhead. Unlike other multipath extensions where node-disjoint paths are selected at the destination or at the reply phase, our approach generates two node-disjoint paths during the query phase of the route discovery process by restricting the way the query packet is flooded. Several optimization options are also considered. Simulation is conducted to determine the success rate of finding node-disjoint paths.     

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

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

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.     

移动Ad Hoc网络的一种跨层功率控制路由协议

移动ad hoe网络中通信终端能量有限,但在许多应用场景,尤其是战场环境下,节点能量消耗较大,因此采用有效的功率控制策略非常重要.利用信道增益的对称性,在AODV协议的基础上提出了一种不依赖于地理位置信息的跨层功率控制路由协议PBAODV,仿真表明该协议在不影响其他网络性能指标的前提下,有效的降低了系统整体功耗.     

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.