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.     

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.     

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.     

Approximation Algorithms for the Mobile Piercing Set Problem with Applications to Clustering in Ad-Hoc Networks

The main contributions of this paper are two-fold. First, we present a simple, general framework for obtaining efficient constant-factor approximation algorithms for the mobile piercing set (MPS) problem on unit-disks for standard metrics in fixed dimension vector spaces. More specifically, we provide low constant approximations for L ₁ and L norms on a d-dimensional space, for any fixed d>0, and for the L ₂ norm on two- and three-dimensional spaces. Our framework provides a family of fully-distributed and decentralized algorithms, which adapt (asymptotically) optimally to the mobility of disks, at the expense of a low degradation on the best known approximation factors of the respective centralized algorithms: Our algorithms take O(1) time to update the piercing set maintained, per movement of a disk. We also present a family of fully-distributed algorithms for the MPS problem which either match or improve the best known approximation bounds of centralized algorithms for the respective norms and space dimensions.Second, we show how the proposed algorithms can be directly applied to provide theoretical performance analyses for two popular 1-hop clustering algorithms in ad-hoc networks: the lowest-id algorithm and the Least Cluster Change (LCC) algorithm. More specifically, we formally prove that the LCC algorithm adapts in constant time to the mobility of the network nodes, and minimizes (up to low constant factors) the number of 1-hop clusters maintained. While there is a vast literature on simulation results for the LCC and the lowest-id algorithms, these had not been formally analyzed prior to this work.We also present an O(logn)-approximation algorithm for the mobile piercing set problem for nonuniform disks (i.e., disks that may have different radii), with constant update time.     

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

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

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.     

无线传感器网络中基于树的能量高效分布式精确数据收集算法

在大规模节点密集的多跳传感器网络中,精确数据收集存在着\"热区\"问题:越靠近Sink节点的传感器节点,其承担的数据转发量就越多,能量消耗也越快,从而成为瓶颈节点,缩短整个网络的生命周期.最大生命周期数据收集树的构建已被证明是NP完全问题.已有算法大多是集中式算法,不适用于大规模节点密集的传感器网络.本文提出一种分布式精确数据收集算法EEDAT,在大规模节点密集的传感器网络中,不仅能够保证每个节点到Sink的路径是最短路径(最少跳数),而且能有效延长网络生命周期.EEDAT分为两个基本步骤,首先随机生成一棵数据收集树,然后根据各个传感器节点的孩子数和剩余能量,对已生成的数据收集树进行调整,使得各个节点的负载尽量均衡,从而达到延长网络生命周期的目的.实验结果表明,与已有分布式算法LMST相比,EEDAT所构造的数据收集树能延长网络生命周期平均20%.     

通信网中链路重要性的评价方法

本文提出了一种通信网链路重要性的评价方法,该方法可以评价全网范围内的链路重要性.最重要的链路是将其进行边收缩操作后,得到的图的生成树数目最多.通过比较生成树的数目,我们可以判断通信网中任意两条链路的相对重要性.基于生成树数目的边收缩方法反映了某条链路处于正常工作时,对整个通信网的贡献大小.实验结果和理论分析均证明了该方法的有效性和可行性.     

无线网络中节点重要性的研究

提出了一种判断无线网络中节点重要性的新方法——节点插入法,并给出了归一化表达式,认为最重要的节点是在 其相关链路上插入一个新节点后,使图的生成树增加最多.该方法可以判断全网范围内节点的重要性,并比较任意两个节点 的相对重要性,理论分析和仿真结果表明,该方法对新加入节点的位置评估要优于其它算法.     

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.     

Cooperative localization techniques for wireless sensor networks: free,signal and angle based techniques

This paper addresses the problem of localization in sensor networks where, initially, a certain number of sensors are aware of their positions (either by using GPS or by being hand‐placed) and are referred to as anchors. Our goal is to localize all sensors with high accuracy, while using a limited number of anchors. Sensors can be equipped with different technologies for signal and angle measurements. These measures can be altered by some errors because of the network environment that induces position inaccuracies. In this paper, we propose a family (AT‐Family) of three new distributed localization techniques in wireless sensor networks: free‐measurement (AT‐Free) where sensors have no capability of measure, signal‐measurement (AT‐Dist) where sensors can calculate distances, and angle‐measurement (AT‐Angle) where sensors can calculate angles. These methods determine the position of each sensor while indicating the accuracy of its position. They have two important properties: first, a sensor node can deduce if its estimated position is close to its real position and contribute to the positioning of others nodes; second, a sensor can eliminate wrong information received about its position. This last property allows to manage measure errors that are the main drawback of measure‐based methods such as AT‐Dist and AT‐Angle techniques. By varying the density and the error rate, simulations show that the three proposed techniques achieve good performances in term of high accuracy of localized nodes and less energy consuming while assuming presence of measure errors and considering low number of anchors. Copyright © 2012 John Wiley & Sons, Ltd.     

Load-balanced broadcast routing in wireless Ad-hoc networks

In wireless Ad-hoc networks, where mobile hosts are powered by batteries, the entire network may be partitioned because of the drainage of a small set of batteries.Therefore, the crucial issue is to improve the energy efficiency, with an objective of balancing energy consumption.A greedy algorithm called weighted minimum spanning tree (WMST) has been proposed, in which time complexity is O(n2).This algorithm takes into account the initial energy of each node and energy consumption of each communication.Simulation has demonstrated that the performance of the proposed algorithm improves the load balance and prolongs the lifetime.     

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.