Energy-Efficient Broadcasting in All-Wireless Networks

In all-wireless networks, minimizing energy consumption is crucial as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of radio transmissions can be exploited to optimize energy consumption. This problem appears to be difficult to solve [30]. We provide a formal proof of NP-completeness for the general case and give an NP-completeness result for the geometric case; in the former, the network topology is represented by a generic graph with arbitrary weights, whereas in the latter a Euclidean distance is considered. For the general case, we show that it cannot be approximated better than O(logN), where N is the total number of nodes. We then describe an approximation algorithm that achieves the O(logN) approximation ratio. We also describe a new heuristic, Embedded Wireless Multicast Advantage. We show that it compares well with other proposals and we explain how it can be distributed.     

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.     

采用喷泉码的无线协同多眺信息累积广播协议

为提高无线多跳广播的能量效率,提出了采用喷泉码的协同多跳信息累积广播胁议:令注水速率最大的节点进行发送,其发送功率由传输速率和注水速率决定.当有接收节点成功接收时,再由更新后注水速率最大的节点发送.各发送节点采用不同的喷泉码进行编码,使接收节点获得复用增益,并且节点可以接收可靠传输范围以外的信息并进行累积直至成功译码....     

Tree Based Broadcast in Ad Hoc Networks

Although broadcasting using tree structure established in a network is a well known and widely used technique, it is typically claimed to be inappropriate for ad hoc networks, being the maintained tree very sensitive to network changes. On the contrary this paper presents an efficient tree based broadcasting scheme, which is reliable and stable even in case of the ever changing network structure of the ad hoc networks.To achieve this, first, a novel method is presented to maintain a spanning tree in an ad hoc network in a fully distributed, on-line and asynchronous way. Once the tree is established the broadcast itself is performed based on this tree. Some further improvements on the basic algorithm are also presented that reduce the resource requirements even more, increase the stability of the tree, enable the mobility of the nodes to be taken into account and make the method more configurable.As it is shown by simulation, the obtained broadcast scheme is stable, reliable and it uses small amount of resources: the acyclic structure of the broadcast tree ensures that the nodes get the broadcast messages only once, so the broadcast needs little bandwidth and the nodes need not store the recent broadcast messages, reducing the computational and memory requirements.As a byproduct a technique is proposed to measure the mobility of the nodes. This technique needs no additional GPS device or any geographical information but it is based on the stability of the links of the node.Alpár Jüttner received his M. Sc. degree in 1998 at the Eötvös Loránd University of Budapest, where he is currently working on his Ph. D. at Operational Research Departement. He also works as a research fellow at Ericsson Traffic Analysis and Network Performance Laboratory in Budapest, Hungary. His main interests are combinatorial optimization and its applications.Ádám Magi received his M. Sc. degree in 1996 at the Technical University of Budapest in Electrical Engineering. He is currently working on his Ph. D. there. He also works as a research fellow at Ericsson Traffic Analysis and Network Performance Laboratory in Budapest, Hungary. His main interests are mobile ad hoc networks and routing in telecommunication networks.     

Energy Efficient Broadcast in Wireless Ad hoc Networks with Hitch-hiking

In this paper, we propose a novel concept called Hitch-hiking in order to reduce the energy consumption of broadcast application for wireless networks. Hitch-hiking takes advantage of the physical layer design that facilitates the combining of partial signals to obtain the complete information. The concept of combining partial signals using maximal ratio combiner [15] has been used to improve the reliability of the communication link but has never been exploited to reduce energy consumption in broadcasting over wireless ad hoc networks. We study the advantage of Hitch-hiking for the scenario when the transmission power level of nodes is fixed as well as the scenario when the nodes can adjust their power level. For both scenarios, we show that Hitch-hiking is advantageous and have proposed algorithms to construct broadcast tree with Hitch-hiking taken into consideration. For fixed transmission power case, we propose and analyze a centralized heuristic algorithm called SPWMH (Single Power Wireless Multicast with Hitch-hiking) to construct a broadcast tree with minimum forwarding nodes. For the latter case, we propose a centralized heuristic algorithm called Wireless Multicast with Hitch-hiking (WMH) to construct an energy efficient tree using Hitch-hiking and also present a distributed version of the heuristic. We also evaluate the proposed heuristics through simulation. Simulation results show that Hitch-hiking can reduce the transmission cost of broadcast by as much as 50%. Further, we propose and evaluate a protocol called Power Saving with Broadcast Tree (PSBT) that reduces energy consumption of broadcast by eliminating redundancy in receive operation. Finally, we propose an algorithm that takes advantage of both Hitch-hiking and PSBT in conserving energy. Manish Agarwal is an engineer at Microsoft, Redmond. He received his Masters degree in Electrical and Computer Engineering from University of Massachusetts, Amherst in 2004. He received his undergraduate degree from Indian Institute of Technology, Guwahati. His research interest lies in the field of mobile ad hoc networks. Lixin Gao is an associate professor of Electrical and Computer Engineering at the University of Masschusetts, Amherst. She received her Ph.D. degree in computer science from the University of Massachusettes at Amherst in 1996. Her research interests include multimedia networking and Internet routing. Between May 1999 and January 2000, she was a visiting researcher at AT&T Research Labs and DIMACS. She is an Alfred P. Sloan Fellow and received an NSF CAREER Award in 1999. She is a member of IEEE, ACM, and Sigma Xi. Joon Ho Cho received the B.S. degree (summa cum laude) in electrical engineering from Seoul National University, Seoul, Korea, in 1995 and the M.S.E.E. and Ph.D. degrees in electrical and computer engineering from Purdue University, West Lafayette, IN, in 1997 and 2001, respectively. From 2001 to 2004, he was with the University of Massachusetts at Amherst as an Assistant Professor. Since July 2004, he has been with Pohang University of Science and Technology (POSTECH), Pohang, Korea, where he is presently an Assistant Professor in the Department of Electronic and Electrical Engineering. His research interests include wideband systems, multiuser communications, adaptive signal processing, packet radio networks, and information theory. Dr. Cho is currently an Associate Editor for the IEEE Transactions on Vehicular Technology. Jie Wu is a Professor at Department of Computer Science and Engineering, Florida Atlantic University. He has published over 300 papers in various journal and conference proceedings. His research interests are in the area of mobile computing, routing protocols, fault-tolerant computing, and interconnection networks. Dr. Wu served as a program vice chair for 2000 International Conference on Parallel Processing (ICPP) and a program vice chair for 2001 IEEE International Conference on Distributed Computing Systems (ICDCS). He is a program co-chair for the IEEE 1st International Conference on Mobile Ad-hoc and Sensor Systems (MASS'04). He was a co-guest-editor of a special issue in IEEE Computer on “Ad Hoc Networks”. He also editored several special issues in Journal of Parallel and Distributing Computing (JPDC) and IEEE Transactions on Parallel and Distributed Systems (TPDS). He is the author of the text “Distributed System Design” published by the CRC press. Currently, Dr. Wu serves as an Associate Editor in IEEE Transactions on Parallel and Distributed Systems and three other international journals. Dr. Wu is a recipient of the 1996–97 and 2001–2002 Researcher of the Year Award at Florida Atlantic University. He served as an IEEE Computer Society Distinguished Visitor. Dr. Wu is a Member of ACM and a Senior Member of IEEE.     

一种适合于无线网络的竞争广播算法

广播是无线网络中基本且重要的操作.竞争广播算法是一种基于竞争机制的广播协议算法,适合于移动自组网络.分析和仿真结果表明,与泛洪方案相比,竞争广播算法去除了大量冗余转播,改善了网络的广播性能,提高了网络的吞吐量.另外,竞争广播算法思想还能应用于其他网络协议,如应用于路由协议的路由发现过程,提高路由算法的性能等.     

多跳无线网络中无需邻节点信息的空间覆盖广播算法

针对多跳无线网络中广播的转发冗余问题,该文提出了一种无需邻节点信息的空间覆盖广播(Space-Covered Broadcast,SCB)算法。SCB算法通过优化转发节点的空间分布达到利用最少数目的转发节点实现对网络空间的覆盖,从而在保证较高送达率的同时明显降低了广播的转发次数。由于无需邻节点信息和网络拓扑信息,SCB算法降低了带宽和存储计算等开销;并且,转发节点的选择由接收节点通过延时转发机制来完成,因而SCB算法能够自动适应信道状况,避免信道变化造成的传输错误。仿真结果表明：该算法在不同的节点密度和网络负载条件下能够明显提高广播的传输效率。     

Energy-Aware Broadcast Trees in Wireless Networks

In this paper we address the problem of broadcasting in wireless networks, so that the power consumed by any node is as small as possible. This approach is motivated by the fact that nodes in such networks often use batteries and, hence, it is important to conserve energy individually, so that they remain operational for a long time. We formulate the problem as a lexicographic node power optimization one. The problem is in general NP-complete. We provide an optimal algorithm which runs in polynomial time in certain cases. We also provide a heuristic algorithm whose performance relative to the optimal one is fairly satisfactory. We next show that these algorithms can also be used to solve the problem of broadcasting so that the residual energy of any node after the broadcast process is as large as possible. Finally, we discuss the issues of implementing the above algorithms distributively, as well as their multicast extensions.     

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.     

一种多跳无线网络中的高效广播算法

广播是多跳无线网络中的一种基本操作。现有的广播算法中普遍存在转发冗余过多的问题。该文首先分析了覆盖网络所需的最少转发节点数目,然后以此为基础,提出了一种简单高效的广播算法。该算法中,每个节点最多只需选择3个转发节点,从而明显地减少了广播的转发次数,提高了节点能量和网络资源的利用率;同时,所有转发节点实现了对整个网络接近双重的覆盖,能够保证较高的传输可靠性;此外,对不同的网络规模和拓扑的动态变化,该算法具有较好的可扩展性。仿真结果显示,该算法在多种常见的网络环境下具有比现有方法更优越的性能。     

A Constraint Formulation for Minimum-Energy Multicast Routing in Wireless Multihop Ad-hoc Networks

Energy conservation is a critical issue in wireless multihop ad-hoc networks, which have nodes powered by batteries only. One major metric for energy conservation is to route a communication session along the routes that require the lowest total energy consumption. To do this, we introduce in this paper a new concept called Virtual Relay. Based on this new concept, we present a constraint formulation for the minimum-energy multicast routing problem in terms of mixed integer linear programming. Experiment results show that in a typical multihop ad-hoc network with 50 nodes, the optimal solutions can always be solved in a timely manner, and it also provides a way to evaluate the realistic performance of different heuristic algorithms. Song Guo received the B.S. degree in computer science from Huazhong University of Science and Technology, Wuhan, China, in 1995 and the M.S. degree in electrical and computer engineering from Beijing University of Posts and Telecommunications, Beijing, China, in 1998. Since 2001 he has been a Ph.D. student in the School of Information Technology and Engineering at University of Ottawa, Canada. His main research interests lie in mobile ad-hoc routing protocols and algorithms, power-aware design and optimization for ad-hoc wireless networks, and performance evaluation. Oliver Yang is a Professor in the School of Information Technology and Engineering at University of Ottawa, Ontario, Canada. Dr. Yang received his Ph.D. degree in Electrical Engineering from the University of Waterloo, Ont., Canada in 1988. He has worked for Northern Telecom Canada Ltd. and has done various consulting. His research interests are in modeling, analysis and performance evaluation of computer communication networks, their protocols, services and interconnection architectures. The CCNR Lab under his leadership has been working on various projects in the traffic control, traffic characterization, switch architecture and traffic engineering issues in both wireless and photonic networks. This has been reported in more than 200 technical papers. Dr. Yang is also interested in queuing theory, simulations, computational algorithms and their applications such as reliability and traffic analysis. Dr. Yang is currently the editor of IEEE Communication Magazine.     

无线网络中基于网络编码的可靠广播传输

Recently, network coding has been applied to the loss recovery of reliable broadcast transmission in wireless networks. Since it was proved that fi nding the optimal set of lost packets for XOR-ing is a complex NP-complete problem, the available time-based retransmission scheme and its enhanced retransmission scheme have exponential computational complexity and thus are not scalable to large networks. In this paper, we present an efficient heuristic scheme based on hypergraph coloring and also its enhanced ...     

Fault-Tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks

The topology of a multi-hop wireless network can be controlled by varying the transmission power at each node. The life-time of such networks depends on battery power at each node. This paper presents a distributed fault-tolerant topology control algorithm for minimum energy consumption in multi-hop wireless networks. This algorithm is an extension of cone-based topology control algorithm [19, 12]. The main advantage of this algorithm is that each node decides on its power based on local information about the relative angle of its neighbors and as a result of these local decisions, a fault-tolerant connected network is formed on the nodes. It is done by preserving the connectivity of a network upon failing of, at most, k nodes (k is a constant) and simultaneously minimize the transmission power at each node to some extent. In addition, simulations are studied to support the effectiveness of this algorithm. Finally, it is shown how to extend this algorithm to 3-dimensions. An extended abstract version of this paper appeared in the 11th IEEE International Conference on Computer Communications and Networks(ICCCN02). Mohsen Bahramgiri born in 1979, recieved the Bachelor's degree in Mathematical Sciences from Sharif University of Technology, Tehran, Iran in 2000. He is now a PhD candidate in Mathematics Department at Massachusetts Institute of Technology. His research interests include Symplectic Hodge Theory on Higher dimentional Geometry, Kahler Geometry, Mathematical Physics and Geometric Analysis on one hand, and algorithmic Graph Theory and Combinatorics on the other hand. MohammadTaghi Hajiaghayi received the Bachelor's degree in computer engineering from Sharif University of Technology in 2000. He received the Master's degree in Computer Science from the University of Waterloo in 2001. Since 2001, he is a Ph.D. candidate in Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology. During his Ph.D. studies, he also worked at the IBM T.J. Watson Research Center (Department of Mathematical Sciences) and at the Microsoft Research (Theory group). His research interests are algorithmic graph theory, combinatorial optimizations, distributed and mobile computing, computational geometry and embeddings, game theory and combinatorial auctions, and random structures and algorithms. Vahab S. Mirrokni received the Bachelor's degree in computer engineering from Sharif University of Technology, Tehran, Iran in 2001. Since 2001, he is a Ph.D. candidate in Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology. During his Ph.D. studies, he also worked at the Bell-Laboratories (Networking Center and Department of Fundamental Mathematics). His research interests include approximation algorithms, combinatorial optimization, computational game theory, mobile computing, network mannagement, and algorithmic graph theory.     

Energy-Efficient Broadcast and Multicast Trees in Wireless Networks

The wireless networking environment presents formidable challenges to the study of broadcasting and multicasting problems. In this paper we focus on the problem of multicast tree construction, and we introduce and evaluate algorithms for tree construction in infrastructureless, all-wireless applications. The performance metric used to evaluate broadcast and multicast trees is energy-efficiency. We develop the Broadcast Incremental Power (BIP) algorithm, and adapt it to multicast operation by introducing the Multicast Incremental Power (MIP) algorithm. These algorithms exploit the broadcast nature of the wireless communication environment, and address the need for energy-efficient operation. We demonstrate that our algorithms provide better performance than algorithms that have been developed for the link-based, wired environment.     

一种适用于无线传感器网络的 高效节能广播机制

 针对无线传感器网络结点体积小、内存与计算能力小、靠电池供电、结点密度高以及网络规模大的特点,提出了高效广播协议(EBP,Effective Broadcast Protocol).通过对广播过程中一个结点转播之后其邻域内其它结点的转播,即引发新转播的讨论,完成了对最佳引发新转播的分析.EBP广播协议以此为依据选择转播结点,不需要任何邻结点信息就可以高效完成广播,算法的控制开销和存储开销大大降低.EBP广播机制简单有效,在无线传感器网络中具有良好的扩展性.     

在传感器网络中构造延迟限定的最大化生命周期树

在一些对延迟敏感的持续性监视应用中,无线传感器网络中的数据收集需要构造延迟限定的最大化生命周期树,这属于NP完全问题。提出一个新的算法MILD,通过限定树的高度来满足延迟限定,然后通过使树上“瓶颈节点”的度最小化来延长树的生命周期。实验表明,与目前已有的协议相比,MILD能有效地限定延迟并延长树的生命周期。     

Border Node Retransmission Based Probabilistic Broadcast Protocols in Ad-Hoc Networks

We propose some improvements to the flooding protocols that aim to efficiently broadcast given information in ad-hoc networks. These improvements are based on probabilistic approach and decrease the number of emitted packets. Indeed, it is more interesting to privilege the retransmission by nodes that are located at the radio border of the sender. We observe that the distance between two nodes can be approximated by comparing neighbor lists. This leads to broadcasting schemes that do not require position or signal strength information. Moreover, proposed broadcast protocols require only knowledge of one hop neighborhood and thus need only short hello message and then support high mobility.     

多跳无线网络MAC协议的研究进展

该文简要介绍了多跳无线网络的结构及其MAC协议的分类,简述了近几年来国内外对多跳无线网络MAC协议研究的几个新进展。这些协议均有各自的特点,适用于不同种类的无线网络。最后展望了多跳无线网络MAC协议的发展前景。     

分层多跳无线网中结合负载均衡的切换管理

该文主要研究分层多跳无线网络中的切换管理,提出一种新的用户切换管理算法和移动基站路由切换策略.在网络动态变化时,用户切换管理算法可以减少用户的切换次数,使用户负载分布均匀.移动基站路由切换策略则尽可能地从基站本地找出替代路由,可以在较小的开销下达到快速和无缝切换的目的.     

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

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