Improving route discovery in on-demand routing protocols using two-hop connected dominating sets

Many signaling or data forwarding operations involve the broadcasting of packets, which incurs considerable collisions in ad hoc networks based on a contention-based channel access protocol. We propose the Three-hop Horizon Pruning (THP) algorithm to compute two-hop connected dominating set (TCDS) using only local topology information (i.e., two-hop neighborhood). Because every node has the two-hop neighborhood information, it is possible to maintain fresh routes to all nodes within two hops. In this situation, a TCDS is ideal for the propagation of route request (RREQ) messages in the route discovery process of on-demand routing protocols. THP is shown to be more efficient than all prior distributed broadcasting mechanisms, when a TCDS is preferred over a connected dominating sets (CDS). Like all other algorithms that depend on local topology information, THP is not reliable when the topology changes frequently, and there is a clear trade-off between reliability and efficiency. We describe and analyze two enhancements to THP that address the lack of reliability of neighbor information. First we adopt a virtual radio range (VR), shorter than the physical radio range (RR), and consider as one-hop neighbors only those nodes within VR (we do not use two different radio ranges, as in prior work, because it can incur additional interference). The gap between VR and RR works as a buffer zone, in which nodes can move without loss of connectivity. Second, upon receiving a broadcast packet, the forwarder list in the packet header is analyzed together with the current information about the local neighborhood. Based on that, a node may decide to broadcast the packet even though it has not been selected as a forwarder. We conduct extensive simulations and show that AODV-THP with these two enhancements attains better performance than AODV in terms of delivery ratio, control overhead, packet collisions, and end-to-end delay.     

The Broadcast Storm Problem in a Mobile Ad Hoc Network

Broadcasting is a common operation in a network to resolve many issues. In a mobile ad hoc network (MANET) in particular, due to host mobility, such operations are expected to be executed more frequently (such as finding a route to a particular host, paging a particular host, and sending an alarm signal). Because radio signals are likely to overlap with others in a geographical area, a straightforward broadcasting by flooding is usually very costly and will result in serious redundancy, contention, and collision, to which we call the broadcast storm problem. In this paper, we identify this problem by showing how serious it is through analyses and simulations. We propose several schemes to reduce redundant rebroadcasts and differentiate timing of rebroadcasts to alleviate this problem. Simulation results are presented, which show different levels of improvement over the basic flooding approach.     

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.     

On broadcasting with cooperative diversity in multi-hop wireless networks

Cooperative diversity facilitates spatio-temporal communications without requiring the deployment of physical antenna arrays. While physical layer studies on cooperative diversity have been extensive, higher layer protocols which translate the achievable reduction in the SNR per bit for a given target BER, into system wide performance enhancements are yet to mature. The challenge is that appropriate higher layer functions are needed in order to enable cooperative diversity at the physical layer. We focus on network-wide broadcasting with the use of cooperative diversity in ad hoc networks. We design a novel distributed network-wide broadcasting protocol that takes into account the physical layer dependencies that arise with cooperative diversity. We perform extensive simulations that show that our protocol can outperform the best of the noncooperative broadcasting protocols by: (a) achieving up to a threefold increase in network coverage and, (b) by decreasing the latency incurred during the broadcast by about 50%. We also construct an analytical model that captures the behavior of our protocol. Furthermore, we show that computing the optimal solution to the cooperative broadcast problem is NP-complete and construct centralized approximation algorithms. Specifically, we construct an O(N ^epsi)-approximation algorithm with a computational complexity of O(N4/epsi); we also construct a simpler greedy algorithm.. The costs incurred with these algorithms serve as benchmarks with which one can compare that achieved by any distributed protocol     

Secure group communication in wireless mesh networks

Wireless mesh networks (WMNs) have emerged as a promising technology that offers low-cost community wireless services. The community-oriented nature of WMNs facilitates group applications, such as webcast, distance learning, online gaming, video conferencing, and multimedia broadcasting. Security is critical for the deployment of these services. Previous work focused primarily on MAC and routing protocol security, while application-level security has received relatively little attention. In this paper we focus on providing data confidentiality for group communication in WMNs. Compared to other network environments, WMNs present new challenges and opportunities in designing such protocols. We propose a new protocol framework, Secure Group Overlay Multicast (SeGrOM), that employs decentralized group membership, promotes localized communication, and leverages the wireless broadcast nature to achieve efficient and secure group communication. We analyze the performance and discuss the security properties of our protocols. We demonstrate through simulations that our protocols provide good performance and incur a significantly smaller overhead than a baseline centralized protocol optimized for WMNs.     

A secure broadcasting scheme to provide availability,reliability and authentication for wireless sensor networks

Reliability and security of broadcasting is critical in Wireless Sensor Networks (WSNs). Since reliability and security compete for the same resources, we are interested in jointly solving for error control coding (to achieve reliability) and integrity for a broadcast scenario. We assume Byzantine attacks in which the adversary can compromise nodes and then drop (or modify) the legitimate packets or inject its own packets. For reliable and efficient multihop broadcasting, it is critical to reduce the energy consumption and latency. To prevent the adversary from consuming the scarce network resources by injecting bogus packets, each receiver node should make sure that packets it receives are authentic and it filters out malicious packets immediately. We build our authentication scheme, on top of a reliable and energy efficient broadcasting protocol called Collaborative Rateless Broadcast (CRBcast) to improve efficiency and reliability. On contrary to the previous schemes, our scheme is resilient with respect to Byzantine adversary as well as routing and flooding attacks and protocol exploits. Moreover, we compared our scheme with the previously proposed broadcast authentication schemes and showed that our scheme outperforms them in terms of efficiency and data availability. This is a crucial improvement over the previous schemes that ensure availability by flooding, introducing very large communication overhead and latency.     

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.     

On Broadcasting in Radio Networks--Problem Analysis and Protocol Design

In this paper we develop a graph-oriented model for dealing with broadcasting in radio networks. Using this model, optimality in broadcasting protocols is defined, and it is shown that the problem of finding an optimal protocol is NP-hard. A polynomial time algorithm is proposed under which a channel is assigned to nodes from global, multiple-source broadcasting considerations. In particular, nodes participating in the broadcast do not interfere with each other's transmissions, but otherwise simultaneous channel reuse is permitted. Protocol implementations of this approach by frequency division and by time division are given. It is shown that, using these protocols, bounded delay for broadcasted messages can be guaranteed.     

Network condition and application‐based data adaptive intelligent message routing in vehicular network

Recent advances in intelligent transportation systems enable a broad range of potential applications that significantly improve the vehicle and road safety and facilitate the efficient dissemination of information among the vehicles. To assist the vehicle traffic, message broadcasting is a widely adopted technique for road safety. But efficient message broadcasting is a significant issue, especially in a high network density due to the broadcast storm problem. To solve this issue, several methods are proposed to eliminate the redundant transmission of safety packets. However, they lack in restricting the broadcasting region of safety messages, and the transmissions of safety packets outside the dangerous region, and force the vehicles to unnecessary detours. This paper proposes an adaptive multimode routing protocol, network condition, and application‐based data adaptive intelligent message routing in vehicular network (NetCLEVER) that supports 2 modes of operation such as message broadcasting and intelligent routing. In message broadcasting mode, the NetCLEVER decides the dangerous region of the network by considering the changes of neighbor vehicles velocity, instead of current vehicle velocity, because a vehicle decision in velocity is interdependent with the preceding vehicles. In intelligent routing mode, the NetCLEVER exploits the cuckoo search optimization in routing by taking into account multiple routing factors such as the road topology of intersections and traffic signals and their impact on link stability, which improves the reliability of routing packets significantly. The performance evaluation illustrates that the proposed NetCLEVER improves reliable wireless communication as well as road safety in vehicular ad hoc networks.     

Efficient Channel Allocation Tree Generation for Data Broadcasting in a Mobile Computing Environment

The research issue of broadcasting has attracted a considerable amount of attention in a mobile computing system. By utilizing broadcast channels, a server continuously and repeatedly broadcasts data to mobile users. These broadcast channels are also known as broadcast disks from which mobile users can retrieve data. Using broadcasting, mobile users can obtain the data of interest efficiently and only need to wait for the required data to present on the broadcast channel. The issue of designing proper data allocation in the broadcast disks is to reduce the average expected delay of all data items. We explore in this paper the problem of generating hierarchical broadcast programs with the data access frequencies and the number of broadcast disks in a broadcast disk array given. Specifically, we first transform the problem of generating hierarchical broadcast programs into the one of constructing a channel allocation tree with variant-fanout. By exploiting the feature of tree generation with variant-fanout, we develop a heuristic algorithm VF ^K to minimize the expected delay of data items in the broadcast program. In order to evaluate the solution quality obtained by algorithm VF ^K and compare its resulting broadcast program with the optimal one, we devise an algorithm OPT based on a guided search to obtain the optimal solution. Performance of these algorithms is comparatively analyzed. Sensitivity analysis on several parameters, including the number of data items and the number of broadcast disks, is conducted. It is shown by our simulation results that by exploiting the feature of variant-fanout in constructing the channel allocation tree, the solution obtained by algorithm VF ^K is of very high quality and is in fact very close to the optimal one resulted by algorithm OPT. Moreover, algorithm VF ^K is of very good scalability which is important for algorithm VF ^K to be of practical use to generate hierarchical broadcast programs dynamically in a mobile computing environment.     

Efficient broadcast for wireless ad hoc networks with a realistic physical layer

In this paper, we investigate the low coverage problem of efficient broadcast protocols in wireless ad hoc networks with realistic physical layer models. To minimize energy consumption, efficient protocols aim to select small set of forward nodes and minimum transmission radii. In ideal physical layer model, nodes within forward nodes’ transmission ranges can definitely receive packets; therefore energy efficient protocols can guarantee full coverage for broadcasting. However, in networks with a realistic physical layer, nodes can only receive packets with probability. We present an analytical model to show that the transmission radii used for nodes can be used to establish a tradeoff between minimizing energy consumption and ensuring network coverage. We then propose a mechanism called redundant radius, which involves using two transmission radii, to form a buffer zone that guarantees the availability of logical links in the physical network, one for broadcast tree calculation and the other for actual data transmission. With this mechanism, we extend well-known centralized protocols, BIP and DBIP, and corresponding localized protocols, LBIP and LDBIP. The effectiveness of the proposed scheme in improving network coverage is validated analytically and by simulation.     

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.     

Provision of continuous VCR functions in interactive broadcast VoD systems

Video broadcasting is one of the feasible solutions to implement a large-scale video-on-demand (VoD) system. Nevertheless, it is still an open issue for the provision of continuous VCR functions in a delay insensitive broadcast VoD system. In this paper, we propose to jointly optimize an active buffer management scheme with contingency channels to support the VCR functions in an efficient protocol called partitioned broadcasting. We develop a greedy channel management scheme by exploiting the property of the broadcasting protocol such that the system bandwidth capacity can be fully utilized. Incorporating the channel management scheme with the partitioned video broadcast, the VoD system not only provides delay insensitive services but also handles all the interactive requests. Extensive simulation results demonstrate that the partitioned broadcasting system outperforms the traditional system based on the staggered broadcasting protocols. It is found that 20 broadcasting channels and 10 contingency channels are sufficient to support on average 720 customers for a single video with less that one second start-up delay and all types of VCR functions.     

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.

     

Secure opportunistic routing protocols: methods,models, and classification

Addressing communication reliability and security has always been of significant importance in wireless networks. Opportunistic routing (OR) protocols comprise a promising area of research that aims to improve the reliability of communications, particularly in lossy networks. The main concept behind OR protocols is to utilize the broadcast nature of the wireless medium and determine a group of neighboring node candidates, known as candidate set, to collaboratively forward packets towards the destination using a candidate coordination approach. However, similar to traditional routing protocols, OR protocols operate poorly in the presence of malicious nodes and attackers. Therefore, researchers have designed and developed a number of security enhancements, considering the specific characteristics of such protocols. In this paper, following a brief overview on OR protocols, we examine, classify, and compare the different categories of security approaches proposed for OR protocols. More precisely, we divide security-related OR protocols into three categories, including trust-based approaches, game-theory-oriented solutions, and other related protocols. Furthermore, the most significant algorithms of each category are investigated as case studies. Finally, a comparison of different protocols is presented considering the main features, advantages, and shortcomings of each protocol.

     

Exploring the design space of reliable multicast protocols for wireless mesh networks

Many important applications in wireless mesh networks require reliable multicast communication, i.e., with 100% packet delivery ratio (PDR). Previously, numerous multicast protocols based on automatic repeat request (ARQ) have been proposed to improve the packet delivery ratio. However, these ARQ-based protocols can lead to excessive control overhead and drastically reduced throughput. In this paper, we present a comprehensive exploration of the design space for developing high-throughput, reliable multicast protocols that achieve 100% PDR.Motivated by the fact that 802.11 MAC layer broadcast, which is used by most wireless multicast protocols, offers no reliability, we first examine if better hop-by-hop reliability provided by unicasting the packets at the MAC layer can help to achieve end-to-end multicast reliability. We then turn to end-to-end solutions at the transport layer. Previously, forward error correction (FEC) techniques have been proved effective for providing reliable multicast in the Internet, by avoiding the control packet implosion and scalability problems of ARQ-based protocols. In this paper, we examine if FEC techniques can be equally effective to support reliable multicast in wireless mesh networks. We integrate four representative reliable schemes (one ARQ, one FEC, and two hybrid) originally developed for the Internet with a representative multicast protocol ODMRP and evaluate their performance.Our experimental results via extensive simulations offer an in-depth understanding of the various choices in the design space. First, compared to broadcast-based unreliable ODMRP, using unicast for per-hop transmission only offers a very small improvement in reliability under low load, but fails to improve the reliability under high load due to the significantly increased capacity requirement which leads to congestion and packet drop. Second, at the transport layer, the use of pure FEC can significantly improve the reliability, increasing PDR up to 100% in many cases, but can be inefficient in terms of the number of redundant packets transmitted. In contrast, a carefully designed ARQ–FEC hybrid protocol, such as RMDP, can also offer 100% reliability while improving the efficiency by up to 38% compared to a pure FEC scheme. To our best knowledge, this is the first in-depth study of high-throughput, reliable multicast protocols that provide 100% PDR for wireless mesh networks.     

Profit‐based exclusive‐or coding algorithm for data retransmission in DVB‐H with a recovery network

The digital video broadcasting‐handheld (DVB‐H) standard is developed by European Telecommunications Standards Institute to broadcast digital videos to handheld devices, but data loss is a critical issue due to the broadcast behavior. On the other hand, DVB‐Internet protocol datacasting (DVB‐IPDC) integrates DVB‐H with an Internet protocol‐based wireless network to provide bidirectional communication. We adopt this wireless network to deal with data retransmission and call it a recovery network. The paper argues that network coding can improve retransmission efficiency of the recovery network because DVB‐H packet loss often exhibits high correlation. In addition, DVB‐H packets may be heterogeneous in the sense that they have different importance. According to these two arguments, the paper considers that DVB‐H packets are associated with different profit depending on their importance and proposes an α‐maximum profit network coding problem. It asks the base station in the recovery network to use no more than α coded packets for handheld devices to retrieve the lost DVB‐H packets such that the overall profit is the maximum. An efficient exclusive‐or coding scheme, namely the profit‐based exclusive‐or network coding (PEN) algorithm, is proposed to solve this problem. Extensive simulation results also verify the effectiveness of the PEN algorithm. Copyright © 2014 John Wiley & Sons, Ltd.     

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.     

Minimum-Energy Broadcasting in Multi-hop Wireless Networks Using a Single Broadcast Tree

In this paper we address the minimum-energy broadcast problem in multi-hop wireless networks, so that all broadcast requests initiated by different source nodes take place on the same broadcast tree. Our approach differs from the most commonly used one where the determination of the broadcast tree depends on the source node, thus resulting in different tree construction processes for different source nodes. Using a single broadcast tree simplifies considerably the tree maintenance problem and allows scaling to larger networks. We first show that, using the same broadcast tree, the total power consumed for broadcasting from a given source node is at most twice the total power consumed for broadcasting from any other source node. We next develop a polynomial-time approximation algorithm for the construction of a single broadcast tree. The performance analysis of the algorithm indicates that the total power consumed for broadcasting from any source node is within 2H(n−1) from the optimal, where n is the number of nodes in the network and H(n) is the harmonic function. This approximation ratio is close to the best achievable bound in polynomial time. We also provide a useful relation between the minimum-energy broadcast problem and the minimum spanning tree, which shows that a minimum spanning tree may be a good candidate in sparsely connected networks. The performance of our algorithm is also evaluated numerically with simulations. A preliminary version of this work appeared in the Proceedings of WiOpt’04: Modeling and Optimization in Mobile, Ad hoc and Wireless Networks, University of Cambridge, UK, March 2004. Ioannis Papdimitriou was fully supported for this work by the Public Benefit Foundation “ALEXANDER S. ONASSIS”, Athens, Greece. Ioannis Papadimitriou was born in Veria, Greece, in 1976. He received his five year Diploma from the Department of Electronic and Computer Engineering, Technical University of Crete (Chania), Greece, in 1999 (graduating 2nd in class). He is currently a postgraduate student - Ph.D. candidate at the Telecommunications division, Department of Electrical and Computer Engineering, Aristotle University of Thessaloniki, Greece. His doctoral thesis deals with the design of wireless ad hoc networks. His research interests include broadcast and multicast communication, energy conservation, routing and topology control protocols, MAC layer and QoS issues. During his studies he has been honored with awards and scholarships by the Technical University of Crete, the Hellenic Telecommunications Organization S.A.(OTE S.A.) and Ericsson Hellas S.A. Mr. Papadimitriou has been a member of the Technical Chamber of Greece (TEE) since March 2000, and he has been supported by the Public Benefit Foundation ALEXANDER S. ONASSIS, Athens, Greece, with a scholarship for his doctoral studies from October 2001 to March 2005. Leonidas Georgiadis received the Diploma degree in electrical engineering from Aristotle University, Thessaloniki, Greece, in 1979, and his M.S. and Ph.D. degrees both in electrical engineering from the University of Connecticut, in 1981 and 1986, respectively. From 1981 to 1983 he was with the Greek army. From 1986 to 1987 he was Research Assistant Professor at the University of Virginia, Charlottesville. In 1987 he joined IBM T.J. Watson Research Center, Yorktown Heights, as a Research Staff Member. Since October 1995, he has been with the Telecommunications Department of Aristotle University, Thessaloniki, Greece. His interests are in the area of wireless networks, high speed networks, distributed systems, routing,scheduling, congestion control, modeling and performance analysis. Prof. Georgiadis is a senior member of IEEE Communications Society. In 1992 he received the IBM Outstanding Innovation Award for his work on goal-oriented workload management for multi-class systems.x