Localized Algorithms for Energy Efficient Topology in Wireless Ad Hoc Networks

Topology control in wireless ad hoc networks is to select a subgraph of the communication graph (when all nodes use their maximum transmission range) with some properties for energy conservation. In this paper, we propose two novel localized topology control methods for homogeneous wireless ad hoc networks. Our first method constructs a structure with the following attractive properties: power efficient, bounded node degree, and planar. Its power stretch factor is at most , and each node only has to maintain at most neighbors where the integer is an adjustable parameter, and β is a real constant between 2 and 5 depending on the wireless transmission environment. It can be constructed and maintained locally and dynamically. Moreover, by assuming that the node ID and its position can be represented in bits each for a wireless network of n nodes, we show that the structure can be constructed using at most 24n messages, where each message is bits. Our second method improves the degree bound to k, relaxes the theoretical power spanning ratio to , where is an adjustable parameter, and keeps all other properties. We show that the second structure can be constructed using at most 3n messages, where each message has size of bits. We also experimentally evaluate the performance of these new energy efficient network topologies. The theoretical results are corroborated by the simulations: these structures are more efficient in practice, compared with other known structures used in wireless ad hoc networks and are easier to construct. In addition, the power assignment based on our new structures shows low energy cost and small interference at each wireless node. The work of Xiang-Yang Li is partially supported by NSFCCR-0311174. Wen-Zhan Song received Ph.D. from Illinois Institute of Technology in 2005, BS and MS from Nanjing University of Science and Technology in 1997 and 2000. He is currently an assistant professor in Washington State University. His current research interest is mainly focus on network protocol and algorithm design, especially in wireless networks, sensor networks and Peer-to-Peer networks. He is a member of the IEEE. Yu Wang received the Ph.D. degree in computer science from Illinois Institute of Technology in 2004, the BEng degree and the MEng degree in computer science from Tsinghua University, China, in 1998 and 2000. He has been an assistant professor of computer science at the Univeristy of North Carolina at Charlotte since 2004. His current research interests include wireless networks, mobile computing, algorithm design, and artificial intelligence. He is a member of the ACM, IEEE, and IEEE Communication Society. Xiang-Yang Li has been an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He hold MS (2000) and PhD (2001) degree at Computer Science from University of Illinois at Urbana-Champaign. He received his Bachelor degree at Computer Science and Bachelor degree at Business Management from Tsinghua University, P.R. China in 1995. His research interests span the computational geometry, wireless ad hoc networks, game theory, cryptography and network security. He is a Member of the ACM, IEEE, and IEEE Communication Society. Ophir Frieder is the IITRI Professor of Computer Science at the Illinois Institute of Technology. His research interests span the general area of distributed information systems. He is a Member of ACM and a Fellow of the IEEE.     

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

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

Localized Construction of Low Weighted Structure and Its Applications in Wireless Ad Hoc Networks

We consider a wireless network composed of a set of n wireless nodes distributed in a two dimensional plane. The signal sent by every node can be received by all nodes within its transmission range, which is uniform and normalized to one unit. We present the first distributed method to construct a bounded degree planar connected structure LRNG, whose total link length is within a constant factor of the minimum spanning tree using total O(n) messages under the broadcast communication model. Moreover, in our method, every node only uses its two-hop information to construct such structure, i.e., it is localized method. We show that some two-hop information is necessary to construct any low-weighted structure. We also study the application of this structure in efficient broadcasting in wireless ad hoc networks. We prove that, for broadcasting, the relative neighborhood graph (RNG), which is the previously best-known sparse structure that can be constructed locally, could use energy O(n) times the total energy used by our structure LRNG. Our simulations show that the broadcasting based on LRNG consumes energy about 36% more than that by MST, and broadcasting based on RNG consumes energy about 64% more than that by MST. We also show that no localized method can construct a structure for broadcasting with total power consumption asymptotically better than LRNG. Xiang-Yang Li has been an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He hold MS (2000) and PhD (2001) degree at Computer Science from University of Illinois at Urbana-Champaign. He received his Bachelor degree at Computer Science and Bachelor degree at Business Management respectively from Tsinghua University, P.R. China in 1995. His research interests span the computational geometry, wireless ad hoc networks, game theory, optical networks, and cryptography. He is a Member of the ACM and IEEE.     

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.     

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 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.     

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.     

Equilibria in Topology Control Games for Ad Hoc Networks

We study topology control problems in ad hoc networks where network nodes get to choose their power levels in order to ensure desired connectivity properties. Unlike most other work on this topic, we assume that the network nodes are owned by different entities, whose only goal is to maximize their own utility that they get out of the network without considering the overall performance of the network. Game theory is the appropriate tool to study such selfish nodes: we define several topology control games in which the nodes need to choose power levels in order to connect to other nodes in the network to reach their communication partners while at the same time minimizing their costs. We study Nash equilibria and show that—among the games we define—these can only be guaranteed to exist if each network node is required to be connected to all other nodes (we call this the Strong Connectivity Game). For a variation called Connectivity Game, where each node is only required to be connected (possibly via intermediate nodes) to a given set of nodes, we show that Nash equilibria do not necessarily exist. We further study how to find Nash equilibria with incentive-compatible algorithms and compare the cost of Nash equilibria to the cost of a social optimum, which is a radius assignment that minimizes the total cost in a network where nodes cooperate. We also study variations of the games; one where nodes not only have to be connected, but k-connected, and one that we call the Reachability Game, where nodes have to reach as many other nodes as possible, while keeping costs low. We extend our study of the Strong Connectivity Game and the Connectivity Game to wireless networks with directional antennas and wireline networks, where nodes need to choose neighbors to which they will pay a link. Our work is a first step towards game-theoretic analyses of topology control in wireless and wireline networks. A preliminary version of this paper appeared in DIALM-POMC ’03 [8]. Stephan Eidenbenz is a technical staff member in Discrete Simulation Sciences (CCS-5) at Los Alamos National Laboraotry. He received his Ph.D. in Computer Science from the Swiss Federal Institute of Technology, Zurich, Switzerland in 2000. Stephan’s research covers areas in approximability, algorithms, computational geometry, computational biology, large-scale discrete simulation, selfish networking, efficient networking, protocol design and optimization. V. S. Anil Kumar is currently an Assistant Professor in the Dept. of Computer Science and a Senior Research Associate at Virginia Bioinformatics Institute, Virginia Tech. Prior to this, he was a technical staff member in Los Alamos National Laboratory. He received a Ph.D. in Computer Science from the Indian Institute of Science in 1999. His research interests include approximation algorithms, mobile computing, combinatorial optimization and simulation of large socio-technical systems. Sibylle Zust received her Masters degree in mathematics from ETH Zurich in Switzerland in 2002. She wrote her diploma thesis at the University of Copenhagen in Denmark. Sibylle Zust spent two and a half years (2002–2005) as a graduate research assistant at the Los Alamos National Laboratory in New Mexico, USA, where she worked on algorithmic aspects of game theory and scheduling problems. She now works for an insurance company in Zurich, Switzerland.     

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

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

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.     

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.

Congestion Control Performance of R-DSDV Protocol in Multihop Wireless Ad Hoc Networks

Ad hoc wireless networks are composed of mobile nodes communicating through wireless links, without any fixed backbone infrastructure. Frequent topology changes due to node mobility make routing in such dynamic networks a challenging problem. Moreover, successful message routing implies every mobile node is potentially capable of acting as a router, thus supporting store-and-forward mechanisms. However, resource limitations on these nodes also require a control on congestion due to message forwarding. In this paper, we consider our recently proposed randomized version of the well-known Destination-Sequenced Distance Vector (DSDV) routing protocol, referred to as R-DSDV, and validate its performance through extensive simulation experiments. Our results demonstrate that a probabilistic control on message traffic based on local tuning of protocol parameters is feasible, and that R-DSDV outperforms the basic DSDV protocol by significantly reducing the average queue size associated with each mobile node and hence the average packet delay.     

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     

Channel Adaptive Shortest Path Routing for Ad Hoc Networks

1　IntroductionAdhocnetworksareformedwithoutrequiringthepreexistinginfrastructureorcentralizedadminis tration ,incontrasttocellularnetworks.Asidefromtheoriginalmilitaryapplication ,ithasapplicationinpublicsafetyandcommercialareas,butadaptiveprotocolsarerequiredinorderforthemtodoso .Twoimportantcharacteristicsofacommunicationlinkinadhocnetworksareitsunreliabilityanditsvariability .Thelinksinsuchanetworkareunreli ablebecauseoffading ,interference,noise,andper hapsthefailureofthetransmittingorrec…     

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.     

Maximizing Network Lifetime of Broadcasting Over Wireless Stationary Ad Hoc Networks

We investigate the problem of extending the network lifetime of a single broadcast session over wireless stationary ad hoc networks where the hosts are not mobile. We define the network lifetime as the time from network initialization to the first node failure due to battery depletion. We provide through graph theoretic approaches a polynomial-time globally optimal solution, a variant of the minimum spanning tree (MST), to the problem of maximizing the static network lifetime. We make use of this solution to develop a periodic tree update strategy for effective load balancing and show that a significant gain in network lifetime over the optimal static network lifetime can be achieved. We provide extensive comparative simulation studies on parameters such as update interval and control overhead and investigate their impact on the network lifetime. The simulation results are also compared with an upper bound to the network lifetime. A preliminary version of this paper appeared in IEEE ICC 2003 [35]. This research was funded in part by NSF grant ANI-0093187, ONR award #: N00014-04-1-0479 and Collaborative Technology Alliance (CTA) from ARL under DAAD19-01-2-0011. All statements and opinions are that of the authors and do not represent any position of the U.S government Intae Kang received his B.S. degree in physics from Seoul National University, Seoul, Korea and M.S. degree in electrical engineering from the Johns Hopkins University, Baltimore, MD. He is currently working toward the Ph.D. degree in the Department of Electrical Engineering at the University of Washington, Seattle, WA. His current research interests are in the area of ad hoc and sensor networks. In particular, he is interested in energy efficient routing, topology control, medium access control, mobility management, and modeling and performance analysis of network protocols using directional/smart antennas. Radha Poovendran has been an assistant professor at the Electrical Engineering Department of the University of Washington at Seattle since September 2000. He received his Ph.D. in Electrical Engineering from the University of Maryland, College Park in 1999. His research interests are in the areas of applied cryptography for multiuser environment, wireless networking, and applications of Information Theory to security. He is a recipient of Faculty Early Career Award from the National Science Foundation (2001), Young Investigator Award from the Army Research Office (2002), Young Investigator Award from the Office of Naval Research (2004), and the 2004 Presidential Early Career Award for Scientists and Engineers, for his research contributions in the areas of wired and wireless multiuser security. He is also a co-recipient of the 2002 Outstanding Teaching as well as the Outstanding Advisor Awards from the Department of Electrical Engineering of the University of Washington.     

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.     

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.