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.     

一种改进的基于连通支配集的P2P搜索算法

为了避免由洪泛搜索方法引起的大量网络流量问题．基于连通支配集的广播算法BCDS通过减少转发节点来减少查询消息数。文章对BCDS算法进行改进，选择转发节点时考虑节点间的距离．简化选择转发节点的操作，且不用维持局部两跳拓扑信息。实验结果表明当搜索结果相同时，改进的BCDS算法的消息数量平均仅为洪泛搜索方法的35％。     

无线传感器网络中最小化能量广播算法

在无线传感器网络广播中,为保证所有节点都接收到广播的数据包并调节节点功率以最小化广播总能耗,在Cartigny等人提出的面向相对邻图的广播算法RBOP(relative neighborhood graph broadcast oriented protocol)的基础上,提出了更为节能的增强的面向相对邻图的广播算法ERBOP(enhanced relative neighborhood graph broadcast oriented protocol)。首先在相对邻图上删除较长边得到相对邻图的子图,该子图是连通稀疏图且包含了原图的最小生成树,然后在该子图上构造1-支配的连通支配集,只有支配点才参与数据包转发。仿真显示ERBOP有效节约了能量。     

Maximum lifetime broadcast communications in cooperative multihop wireless ad hoc networks: Centralized and distributed approaches

We investigate the problem of broadcast routing in energy constrained stationary wireless ad hoc networks with an aim to maximizing the network lifetime measured as the number of successive broadcast sessions that can be supported. We propose an energy-aware spanning tree construction scheme supporting a broadcast request, considering three different signal transmission schemes in the physical layer: (a) point-to-point, (b) point-to-multipoint, and (c) multipoint-to-point. First we present a centralized algorithm that requires global topology information. Next, we extend this to design an approximate distributed algorithm, assuming the availability of k-hop neighborhood information at each node, with k as a parameter. We prove that the centralized scheme has time complexity polynomial in the number of nodes and the distributed scheme has a message complexity that is linear in the number of nodes. Results of numerical experiments demonstrate significant improvement in network lifetime following our centralized scheme compared to existing prominent non-cooperative broadcasting schemes proposed to solve the same lifetime maximization problem in wireless ad hoc networks. Due to lack of global topology information, the distributed solution does not produce as much advantage as the centralized solution. However, we demonstrate that with increasing value of k, the performance of the distributed scheme also improves significantly.     

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.     

Models and Approximation Algorithms for Channel Assignment in Radio Networks

We consider the frequency assignment (broadcast scheduling) problem for packet radio networks. Such networks are naturally modeled by graphs with a certain geometric structure. The problem of broadcast scheduling can be cast as a variant of the vertex coloring problem (called the distance-2 coloring problem) on the graph that models a given packet radio network. We present efficient approximation algorithms for the distance-2 coloring problem for various geometric graphs including those that naturally model a large class of packet radio networks. The class of graphs considered include (r,s)-civilized graphs, planar graphs, graphs with bounded genus, etc.     

Performance analysis of geography‐limited broadcasting in multihop wireless networks

In multihop wireless networks, delivering a packet to all nodes within a specified geographic distance from the source is a packet forwarding primitive (geography‐limited broadcasting), which has a wide range of applications including disaster recovery, environment monitoring, intelligent transportation, battlefield communications, and location‐based services. Geography‐limited broadcasting, however, relies on all nodes having continuous access to precise location information, which may not be always achievable. In this paper, we consider achieving geography‐limited broadcasting by means of the time‐to‐live (TTL) forwarding, which limits the propagation of a packet within a specified number of hops from the source. Because TTL operation does not require location information, it can be used universally under all conditions. Our analytical results, which are validated by simulations, confirm that TTL‐based forwarding can match the performance of the traditional location‐based geography‐limited broadcasting in terms of the area coverage as well as the broadcasting overhead. It is shown that the TTL‐based approach provides a practical trade‐off between geographic coverage and broadcast overhead. By not delivering the packet to a tiny fraction of the total node population, all of which are located near the boundary of the target area, TTL‐based approach reduces the broadcast overhead significantly. This coverage‐overhead trade‐off is useful if the significance of packet delivery reduces proportionally to the distance from the source. Copyright © 2011 John Wiley & Sons, Ltd.     

SOBP: a sender-designated opportunistic broadcast protocol for VANET

Two problems existing in highway vehicular ad hoc networks (VANET), i.e., the slow reaction problem (SRP) and the local broadcast storm problem (LBSP), are investigated. In SRP, a candidate forwarder (CF) close to a sender always rebroadcasts a packet with a low probability or rebroadcasts a packet after a long delay in sparse network, while LBSP occurs when vehicles contending for accessing channel in a local dense network. To solve these problems, a Sender-designated Opportunistic Broadcast Protocol (SOBP) is proposed, which has multiple CFs to broadcast packets and is irrelevant to node density. A sender designates a fixed number of CFs and assigns priorities to them before broadcasting a packet so that possible collisions in the receivers are avoided. To enhance the efficiency of a single transmission, the sender chooses the CFs separated with a certain distance to alleviate the effect of hidden node. The average number of transmissions in a successful broadcast is analyzed and the retransmission strategy to enhance the reliability is presented. One of the main features of SOBP is that it is able to keep broadcasting overhead at a low level. Simulations show that SOBP is able to effectively solve the SRP and the LBSP.     

Performance evaluation of broadcasting strategies in cognitive radio networks

Broadcasting is an important phenomenon, because it serves as simplest mode of communication in a network, via which each node disseminates information to their neighboring nodes simultaneously. Broadcasting is widely used in various kind of networks, such as wireless sensor networks, wireless networks, and ad-hoc networks. Similarly, in cognitive radio networks (CRNs), broadcasting is also used to perform many tasks including neighbor discovery, spectrum mobility, spectrum sharing, and dissemination of message throughout the network. The traditional approach that has been used as broadcasting in CRNs is simple flooding in which a message is disseminated in the network without any strategy check. Simple flooding can cause major setbacks in the network, such as excessive redundant rebroadcasts, and collision drops which collectively are termed as broadcast storm problem. To reduce the effects of broadcast storm problem in wireless networks, we propose and compare four broadcasting strategies for cognitive radio networks in this paper. These four strategies are: (1) probability based, (2) counter based, (3) distance based, and (4) area based. Extensive NS-2 based simulations are carried out on different threshold values for each broadcasting strategy. After experimental evaluation, it is demonstrated that counter based broadcasting surpasses other broadcasting strategies by achieving maximum delivery ratio of 60% and by decreasing redundant rebroadcasts and collision drops up to 44 and 37% respectively.

     

Analysis and simulation of a message dissemination algorithm for VANET

This paper addresses the analytical evaluation of broadcast protocols in VANET. We focus on the most popular broadcast algorithm, which consists in the current emitter selecting the furthest receiver as the next forwarder. We propose a general framework based on point process to evaluate this protocol. The radio environment is modelled by a generic Frame Error Rate function. It enables us, through the same model, to assess the performances for different radio environments or radio technologies. We derive simple formulae for different quantities relative to the performance of the broadcast protocol: time to propagate the message, emitters' intensity, mean number of receptions for the same message, etc. Results based on the analytical model are compared with simulations using realistic vehicle traffic in order to determine the contexts for which the analytical model is relevant. Copyright © 2011 John Wiley & Sons, Ltd.     

Mobile ad hoc network broadcasting: A multi‐criteria approach

Nodes in a computer network often require a copy of a message to be delivered to every node in the network. The network layer can provide such a service, referred to as network‐wide broadcast routing or simply ‘broadcasting’. Broadcasting has many applications, including its role as a service to many routing protocols. In a mobile ad hoc network (MANET), simplistic broadcast schemes (such as flooding) inundate the network with redundancy, contention, collision, and unnecessary use of energy resources. This can prevent broadcasts from achieving their primary objective of maximizing delivery ratio, while also considering secondary objectives, such as balancing energy resources or reducing the network's burden on congested or busy nodes. As a solution, we propose multiple‐criteria broadcasting (MCB). In MCB, the source of each broadcast specifies the importance assigned to broadcast objectives. Network nodes use these priorities, along with local and neighbor knowledge of distributed factors, to broadcast in accordance with the objective priorities attributed to the message. Using ns2, the performance of MCB is evaluated and compared to that of other broadcast protocols. To present knowledge, MCB constitutes the first reconfigurable, multi‐objective approach to broadcasting. Copyright © 2010 John Wiley & Sons, Ltd.     

An opportunistic routing mechanism for real‐time voice service in mobile ad hoc networks

The opportunistic routing mechanism can use several lossy broadcast links to support reliable transmission. In this paper, a simple opportunistic routing mechanism for real‐time multimedia services is proposed. This mechanism is based on the dynamic source routing protocol with some modifications, multiple route request, and route reply messages are used to construct the forwarder list, and the nodes within the forwarder list forward the packets which they overhear. The forwarder list is placed on the packet header in the form of a Bloom filter, which will restrict the size of the forwarder list to a constant value. There are no strict scheduling mechanisms for the forwarding order of the forwarder nodes, thus our opportunistic routing mechanism can be scalable for multiple simultaneous flows. Simulations show that our mechanism can effectively decrease the transmission times and the amount of the control messages for each packet and reduce the end‐to‐end delay for real‐time voice service, the quality of service for these services can be supported well over the unstable wireless channel. Copyright © 2009 John Wiley & Sons, Ltd.     

Channel-quality-aware multihop broadcast for asynchronous multi-channel wireless sensor networks

In this paper, we propose Multi-channel EMBA (M-EMBA), efficient multihop broadcast for asynchronous multi-channel wireless sensor networks. Our scheme employs two channel-quality-aware forwarding policies of improved forwarder’s guidance and fast forwarding to improve multihop broadcast performance. The improved forwarder’s guidance allows forwarders to transmit broadcast messages with guidance to their receivers through channels with good quality. The guidance indicates how each receiver should forward the broadcast message to its neighbor nodes. The improved forwarder’s guidance tremendously reduces redundant transmissions and collisions. Fast forwarding allows adjacent forwarders to send their broadcast messages simultaneously through different channels that have good quality, which helps to reduce multihop broadcast latency and improve multi-channel broadcast utility. In this work, we evaluate the multihop broadcast performance of M-EMBA through theoretical analysis of the system design and empirical simulation-based analysis. We implement M-EMBA in ns-2 and compare it with the broadcast schemes of ARM, EM-MAC, and MuchMAC. The performance results show that M-EMBA outperforms these protocols in both light and heavy network traffic. M-EMBA reduces message cost in terms of goodput, total bytes transmitted, as well as broadcast redundancy and collision. M-EMBA also achieves a high broadcast success ratio and low multihop broadcast latency. Finally, M-EMBA significantly improves energy efficiency by reducing average duty cycle.     

Relative degree adaptive flooding broadcast algorithm for ad hoc networks

Broadcasting has been widely used in mobile Ad hoc networks as a communication means to disseminate information to all reachable nodes. Because radio signals are likely to overlap with others in a geographical area, straightforward broadcasting by flooding becomes very costly and results in serious redundancy, contention and collision, to which we refer as the broadcast storm problem. In this paper we propose the Relative Degree Adaptive flooding Broadcast (RDAB) algorithm for Ad hoc networks to efficiently reduce the broadcast overhead in the network. Based on the current situation of the network and the degree of the nodes, RDAB calculates the relative degree of the nodes, decides which nodes need to re-transmit and which nodes only need to receive. The higher the neighbor node's relative degree, the more uncovered nodes it can cover, hence these nodes can be selected to re-transmit broadcasting packets in the networks. We analyze the reliability and the validity of the RDAB algorithm to prove that the RDAB algorithm is a valid flooding broadcast algorithm. Simulation results show that the RDAB strategy outperforms the Ordinary Flooding Broadcast Method (OBM) and the Multipoint Relaying (MPR) protocol for Ad hoc networks.     

Smart antenna based broadcasting in wireless ad hoc networks

Smart antennas have the advantage over traditional omnidirectional antennas of being able to orientate radio signals into the concerned directions in either transmission mode or in reception mode. Since the omnidirectional antenna use in broadcasting over the whole network is the source of an excessive redundancy of broadcast packet receptions within each node, we suggest using smart antennas to improve the medium usage in the case of broadcasting. We propose to adapt a current broadcast protocol to smart antenna applications and present two smart antenna broadcast approaches. We also present a comparative performance study between omnidirectional and smart antennas when broadcasting. We show that we can improve battery power utilisation and bandwidth usage with smart antennas.     

Collaborative techniques for intrusion detection in mobile ad-hoc networks

In this paper, we present two intrusion detection techniques for mobile ad-hoc networks, which use collaborative efforts of nodes in a neighborhood to detect a malicious node in that neighborhood. The first technique is designed for detection of malicious nodes in a neighborhood of nodes in which each pair of nodes in the neighborhood are within radio range of each other. Such a neighborhood of nodes is known as a clique [12]. The second technique is designed for detection of malicious nodes in a neighborhood of nodes, in which each pair of nodes may not be in radio range of each other but where there is a node among them which has all the other nodes in its one-hop vicinity. This neighborhood is identical to a cluster as mentioned in [12]. Both techniques use message passing between the nodes. A node called the monitor node initiates the detection process. Based on the messages that it receives during the detection process, each node determines the nodes it suspects to be malicious and send votes to the monitor node. The monitor node upon inspecting the votes determines the malicious nodes from among the suspected nodes. Our intrusion detection system is independent of any routing protocol. We give the proof of correctness of the first algorithm, which shows that it correctly detects the malicious nodes always when there is no message loss. We also show with the help of simulations that both the algorithms give good performance even when there are message losses arising due to unreliable channel.     

Analysis of broadcasting delays in vehicular ad hoc networks

High mobility of nodes in vehicular ad hoc networks (VANETs) may lead to frequent breakdowns of established routes in conventional routing algorithms commonly used in mobile ad hoc networks. To satisfy the high reliability and low delivery‐latency requirements for safety applications in VANETs, broadcasting becomes an essential operation for route establishment and repair. However, high node mobility causes constantly changing traffic and topology, which creates great challenges for broadcasting. Therefore, there is much interest in better understanding the properties of broadcasting in VANETs. In this paper we perform stochastic analysis of broadcasting delays in VANETs under three typical scenarios: freeway, sparse traffic and dense traffic, and utilize them to analyze the broadcasting delays in these scenarios. In the freeway scenario, the analytical equation of the expected delay in one connected group is given based on statistical analysis of real traffic data collected on freeways. In the sparse traffic scenario, the broadcasting delay in an n‐vehicle network is calculated by a finite Markov chain. In the dense traffic scenario, the collision problem is analyzed by different radio propagation models. The correctness of these theoretical analyses is confirmed by simulations. These results are useful to provide theoretical insights into the broadcasting delays in VANETs. Copyright © 2010 John Wiley & Sons, Ltd.     

Tree-Based Data Broadcast in IEEE 802.15.4 and ZigBee Networks

This paper studies efficient and simple data broadcast in IEEE 802.15.4-based ad hoc networks (e.g., ZigBee). Since finding the minimum number of rebroadcast nodes in general ad hoc networks is NP-hard, current broadcast protocols either employ heuristic algorithms or assume extra knowledge such as position or two-hop neighbor table. However, the ZigBee network is characterized as low data rate and low cost. It cannot provide position or two-hop neighbor information, but it still requires an efficient broadcast algorithm that can reduce the number of rebroadcast nodes with limited computation complexity and storage space. To this end, this paper proposes self-pruning and forward node selection algorithms that exploit the hierarchical address space in ZigBee networks. Only one-hop neighbor information is needed; a partial list of two-hop neighbors is derived without exchanging messages between neighboring nodes. The ZigBee forward node selection algorithm finds the minimum rebroadcast nodes set with polynomial computation time and memory space. Using the proposed localized algorithms, it is proven that the entire network is covered. Simulations are conducted to evaluate the performance improvement in terms of the number of rebroadcast nodes, number of duplicated receivings, coverage time, and communication overhead     

MH-TRACE: multihop time reservation using adaptive control for energy efficiency

In this paper, we propose multihop time reservation using adaptive control for energy efficiency (MH-TRACE), which is a medium access control (MAC) protocol that combines advantageous features of fully centralized and fully distributed networks for energy-efficient real-time packet broadcasting in a multihop radio network. We introduce a novel clustering algorithm that dynamically organizes the network into two-hop clusters. MH-TRACE clusters are just for coordinating channel access and minimizing interference; thus, ordinary nodes are not static members of any cluster. Time is organized into cyclic superframes, which consist of several time frames, to support reservation-based periodic channel access for real-time traffic. Each clusterhead chooses the frame with least interference based on its own measurements for the operation of its cluster. Energy dissipation for receiving unwanted or collided data packets or for waiting in idle mode is avoided through the use of information summarization packets sent prior to the data transmissions by the source nodes. Through the use of transmission schedules within each cluster, managed by the clusterheads, intracluster data collisions are completely eliminated and intercluster collisions are minimized. We investigated MH-TRACE through extensive simulations and theoretical analysis. Our results show that MH-TRACE outperforms existing distributed MAC protocols like IEEE 802.11 and sensor MAC, in terms of energy efficiency and throughput, approaching the theoretical maximum throughput and theoretical minimum energy dissipation.     

Extended bridge algorithms for large networks

A network bridge is a device that operates at the ISO data link level and routes packets across extended networks, commonly composed of multiple local area networks (LANs) and bridges. A set of algorithms that greatly extends the application of the network bridge is presented. This multitree bridge algorithm allows networks of arbitrary topology and capacity to use bridge routing. The reduced broadcast bridge algorithm alleviates the problem of extraneous broadcasting in large networks built from bridges and packet switches. A method for routing to network users who change their location rapidly, as in mobile cellular radio systems, is presented. An algorithm for efficient multicasting in bridges is given. Application of this technology to the broadband integrated services digital network (BISDN) is proposed