A Routing Algorithm for Wireless Ad Hoc Networks with Unidirectional Links

Most of the routing algorithms for ad hoc networks assume that all wireless links are bidirectional. In reality, some links may be unidirectional. In this paper we show that the presence of such links can jeopardize the performance of the existing distance vector routing algorithms. We also present modifications to distance vector based routing algorithms to make them work in ad hoc networks with unidirectional links. For a network of n nodes, neighbors exchange n×n matrices to propagate routing information. This results in loop-free routes.     

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

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

TCP Performance in IEEE 802.11-Based Ad Hoc Networks with Multiple Wireless Lossy Links

We propose a packet-level model to investigate the impact of channel error on the transmission control protocol (TCP) performance over IEEE-802.11-based multihop wireless networks. A Markov renewal approach is used to analyze the behavior of TCP Reno and TCP Impatient NewReno. Compared to previous work, our main contributions are listed as follows: 1) modeling multiple lossy links, 2) investigating the interactions among TCP, Internet Protocol (IP), and media access control (MAC) protocol layers, specifically the impact of 802.11 MAC protocol and dynamic source routing (DSR) protocol on TCP throughput performance, 3) considering the spatial reuse property of the wireless channel, the model takes into account the different proportions between the interference range and transmission range, and 4) adopting more accurate and realistic analysis to the fast recovery process and showing the dependency of throughput and the risk of experiencing successive fast retransmits and timeouts on the packet error probability. The analytical results are validated against simulation results by using GloMoSim. The results show that the impact of the channel error is reduced significantly due to the packet retransmissions on a per-hop basis and a small bandwidth delay product of ad hoc networks. The TCP throughput always deteriorates less than ~ 10 percent, with a packet error rate ranging from 0 to 0.1. Our model also provides a theoretical basis for designing an optimum long retry limit for IEEE 802.11 in ad hoc networks.     

一维Ad Hoc网络二连通性研究

无线Ad Hoc网络拓扑结构的连通性是成功实现网络端到端数据通信的基本前提,而二连通性是网络在有节点失效的情况下保持拓扑连通的基本条件.为了有效构建具有容错能力的网络拓扑结构,本文针对节点随机均匀分布的一维Ad Hoc网络模型,基于割点概率,分析了一维Ad Hoc网络的二连通性,给出了网络的二连通性与网络分布区域大小、节点数目、通信半径间的解析关系.利用该结论,合理配置网络参数,能够有效优化网络的拓扑结构.仿真实验结果表明,理论值与仿真值吻合良好,验证了所得结论的正确性.     

一种基于TDMA的Ad Hoc网络的虚电路建立协议

为了实现网络中端到端的可靠传输,在基于TDMA的Ad Hoc网络里引入一种虚电路建立协议.该协议采用分布式的资源预约方式建立虚电路,对于网络拓扑变化所引起的链路故障,能够及时发现和处理,且具有相对较小的开销和较高的可靠性,比较适合Ad Hoc网络.     

Virtual Surrounding Face Geocasting in Wireless Ad Hoc and Sensor Networks

Geocasting in wireless sensor and ad hoc networks means delivering a message from a source node to all the nodes in a given geographical region. The objectives of a geocasting protocol are two-fold: guaranteed message delivery and low transmission cost. Most of the existing protocols do not guarantee message delivery, and those that do, incur high transmission costs.      

A Cross-Layer Framework for Exploiting Virtual MISO Links in Mobile Ad Hoc Networks

Space-time communications can help combat fading and, hence, can significantly increase the capacity of ad hoc networks. Cooperative diversity or virtual antenna arrays facilitate spatio-temporal communications without actually requiring the deployment of physical antenna arrays. Virtual MISO entails the simultaneous transmission of appropriately encoded information by multiple nodes to effectively emulate a transmission on an antenna array. We present a novel multilayer approach for exploiting virtual MISO links in ad hoc networks. The approach spans the physical, medium access control and routing layers, and provides 1) a significant improvement in the end-to-end performance in terms of throughput and delay and 2) robustness to mobility and interference-induced link failures. The key physical layer property that we exploit is an increased transmission range due to achieved diversity gain. Except for space-time signal processing capabilities, our design does not require any additional hardware. We perform extensive simulations to quantify the benefits of our approach using virtual MISO links. As compared to using only SISO links, we achieve an increase of up to 150 percent in terms of the end-to-end throughput and a decrease of up to 75 percent in the incurred end-to-end delay. Our results also demonstrate a reduction in the route discovery attempts due to link failures by up to 60 percent, a direct consequence of the robustness that our approach provides to link failures     

无线自组网技术应用

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

无线自组网技术应用

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

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     

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     

Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks

Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms cannot guarantee to generate a CDS of small size. Their message complexities can be as high as O(n ²), and their time complexities may also be as large as O(n ²) and O(n ³). We then present our own distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 8, O(n) time complexity and O(nlogn) message complexity. By establishing the (nlogn) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.     

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.     

Routing with Guaranteed Delivery in Ad Hoc Wireless Networks

We consider routing problems in ad hoc wireless networks modeled as unit graphs in which nodes are points in the plane and two nodes can communicate if the distance between them is less than some fixed unit. We describe the first distributed algorithms for routing that do not require duplication of packets or memory at the nodes and yet guarantee that a packet is delivered to its destination. These algorithms can be extended to yield algorithms for broadcasting and geocasting that do not require packet duplication. A byproduct of our results is a simple distributed protocol for extracting a planar subgraph of a unit graph. We also present simulation results on the performance of our algorithms.     

Multicasting with Localized Control in Wireless Ad Hoc Networks

This paper investigates how to support multicasting in wireless ad hoc networks without throttling the dominant unicast flows. Unicast flows are usually congestion-controlled with protocols like TCP. However, there are no such protocols for multicast flows in wireless ad hoc networks and multicast flows can therefore cause severe congestion and throttle TCP-like flows in these environments. Based on a cross-layer approach, this paper proposes a completely-localized scheme to prevent multicast flows from causing severe congestion and the associated deleterious effects on other flows in wireless ad hoc networks. The proposed scheme combines the layered multicast concept with the routing-based congestion avoidance idea to reduce the aggregated rate of multicast flows when they use excessive bandwidth on a wireless link. Our analysis and extensive simulations show that the fully-localized scheme proposed in this paper is effective in ensuring the fairness of bandwidth sharing between multicast and unicast flows in wireless ad hoc networks.     

构造自组网的容错骨干集

为简化网络结构和提高网络性能所使用的骨干网技术若未考虑容错易造成自组网无法面对节点和无线信道失效.本文研究了如何利用容错骨干来提高网络可靠性,设计了一种分布式容错骨干集构造算法LKFB,满足网络内任意两点之间仅通过容错骨干集保持最大限度K连通容错能力.仿真结果表明,LKFB能够通过改变K值来调整网络的容错能力,通过增加较少的骨干节点换得较高的容错性能.最后通过修改权值函数能够保证按照全网能耗均衡的方式选择容错骨干.     

无线自组织应急通信网络的入网管理

文章着重分析入网控制流程,对普通的和广域的格状网（Mesh）模式分析了自组织网络的入网冲突问题;进一步文章提出了一种分布式入网管理方法,阐述了该方法中的退避机制和算法,描述了算法的流程,并且分析了算法性能;文章还指出了入网管理的一些关键问题和发展趋势。     

Multicast Capacity of Wireless Ad Hoc Networks

Assume that n wireless nodes are uniformly randomly deployed in a square region with side-length a and all nodes have the uniform transmission range r and uniform interference range R > r. We further assume that each wireless node can transmit (or receive) at W bits/second over a common wireless channel. For each node vi , we randomly and independently pick k-1 points pi,j (1 les j les k-1) from the square, and then multicast data to the nearest node for each pi,j. We derive matching asymptotic upper bounds and lower bounds on multicast capacity of random wireless networks. Under protocol interference model, when a ²/r ²=O(n/log(n)), we show that the total multicast capacity is Theta(radic{n/log n}middot(W/radick)) when k=O(n/log n); the total multicast capacity is Theta(W) when k=Omega(n/log n). We also study the capacity of group-multicast for wireless networks where for each source node, we randomly select k-1 groups of nodes as receivers and the nodes in each group are within a constant hops from the group leader. The same asymptotic upper bounds and lower bounds still hold. We also extend our capacity bounds to d -dimensional networks.     

Ad Hoc网络路由技术

无线自组织网络(Adhoc)是一个复杂的系统,其中路由协议是该领域中的研究热点。通过采用合理的路由技术,可使无线自组网具有更为灵活的组网方式,从而达到提升网络性能、减少网络开销等目的。通过与认知无线电(CR)技术、协同通信(CC)技术以及多输入多输出(MIMO)天线技术等物理层新技术的有效结合,可以大大改善Adhoc路由协议的性能。     

自组网环境下利用单向链路的能源节省路由研究

针对自组网中节点电源的容量限制，本文提出了一种利用单向链路的能源节省路由算法。该算法充分利用网络中存在的单向链路，通过让能源较多的节点承担较多的传输任务的方式为数据流选择最佳路由，以延长网络的生存时间。仿真结果证明了该算法的有效性，以及单向链路对于能源节省具有较高的价值。