Efficient broadcasting in ad hoc wireless networks using directional antennas

Using directional antennas to conserve bandwidth and energy consumption in ad hoc wireless networks (or simply ad hoc networks) is becoming popular. However, applications of directional antennas for broadcasting have been limited. We propose a novel broadcast protocol called directional self-pruning (DSP) for ad hoc wireless networks using directional antennas. DSP is a nontrivial generalization of an existing localized deterministic broadcast protocol using omnidirectional antennas. Compared with its omnidirectional predecessor, DSP uses about the same number of forward nodes to relay the broadcast packet, while the number of forward directions that each forward node uses in transmission is significantly reduced. With the lower broadcast redundancy, DSP is more bandwidth and energy-efficient. DSP is based on 2-hop neighborhood information and does not rely on location or angle-of-arrival (AoA) information. Two special cases of DSP are discussed: the first one preserves shortest paths in reactive routing discoveries; the second one uses the directional reception mode to minimize broadcast redundancy. DSP is a localized protocol. Its expected number of forward nodes is O(1) times the optimal value. An extensive simulation study using both custom and ns2 simulators show that DSP significantly outperforms both omnidirectional broadcast protocols and existing directional broadcast protocols.     

Acknowledged broadcasting in ad hoc radio networks

We consider ad hoc radio networks in which each node knows only its own identity but is unaware of the topology of the network, or of any bound on its size or diameter. Acknowledged broadcasting (AB) is a communication task consisting in transmitting a message from a distinguished source to all other nodes of the network and making this fact common knowledge among all nodes. To do this, the underlying directed graph must be strongly connected. Working in a model allowing all nodes to transmit spontaneously even before getting the source message, Chlebus et al. [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] proved that AB is impossible, if collision detection is not available, and gave an AB algorithm using collision detection that works in time O(nD) where n is the number of nodes and D is the eccentricity of the source. Uchida et al. [J. Uchida, W. Chen, K. Wada, Acknowledged broadcasting and gossiping in ad hoc radio networks, Theoret. Comput. Sci. 377 (2007) 43-54] showed an AB algorithm without collision detection working in time O(n4/3log10/3n) for all strongly connected networks of size at least 2. In particular, it follows that the impossibility result from [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] is really caused by the singleton network for which AB amounts to realize that the source is alone. We improve those two results by presenting two generic AB algorithms using a broadcasting algorithm without acknowledgement, as a procedure. For a large class of broadcasting algorithms the resulting AB algorithm has the same time complexity. Using the currently best known broadcasting algorithms, we obtain an AB algorithm with collision detection working in time O(min{nlog²D,nlognloglogn}), for arbitrary strongly connected networks, and an AB algorithm without collision detection working in time O(nlognloglogn) for all strongly connected networks of size n?2. Moreover, we show that in the model in which only nodes that already got the source message can transmit, AB is infeasible in a strong sense: for any AB algorithm there exists an infinite family of networks for which this algorithm is incorrect.     

Applications of k-local MST for topology control and broadcasting in wireless ad hoc networks

We propose a family of structures, namely, k-localized minimum spanning tree (LMST/sub k/) for topology control and broadcasting in wireless ad hoc networks. We give an efficient localized method to construct LMST/sub k/ using only O(n) messages under the local-broadcast communication model, i.e., the signal sent by each node would be received by all nodes within the node's transmission range. We also analytically prove that the node degree of the structure LMST/sub k/ is at most 6, LMST/sub k/ is connected and planar and, more importantly, the total edge length of the LMST/sub k/ is within a constant factor of that of the minimum spanning tree when k/spl ges/2 (called low weighted hereafter). We then propose another low weighted structure, called Incident MST and RNG Graph (IMRG), that can be locally constructed using at most 13n messages under the local broadcast communication model. Test results are corroborated in the simulation study. We study the performance of our structures in terms of the total power consumption for broadcasting, the maximum node power needed to maintain the network connectivity. We theoretically prove that our structures are asymptotically the best possible for broadcasting among all locally constructed structures. Our simulations show that our new structures outperform previous locally constructed structures in terms of broadcasting and power assignment for connectivity.     

Deterministic broadcasting in ad hoc radio networks

We consider the problem of distributed deterministic broadcasting in radio networks of unknown topology and size. The network is synchronous. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. Such messages block each other and node u either hears the noise of interference of messages, enabling it to detect a collision, or does not hear anything at all, depending on the model. We assume that nodes know neither the topology nor the size of the network, nor even their immediate neighborhood. The initial knowledge of every node is limited to its own label. Such networks are called ad hoc multi-hop networks. We study the time of deterministic broadcasting under this scenario. For the model without collision detection, we develop a linear-time broadcasting algorithm for symmetric graphs, which is optimal, and an algorithm for arbitrary n-node graphs, working in time . Next we show that broadcasting with acknowledgement is not possible in this model at all. For the model with collision detection, we develop efficient algorithms for broadcasting and for acknowledged broadcasting in strongly connected graphs. Received: January 2000 / Accepted: June 2001     

Intelligent QoS management for multimedia services support in wireless mobile ad hoc networks

In this paper, we propose a new intelligent cross-layer QoS support for wireless mobile ad hoc networks. The solution, named FuzzyQoS, exploits fuzzy logic for improving traffic regulation and the control of congestion to support both real-time multimedia (audio/video) services and non-real-time traffic services. FuzzyQoS includes three contributions: (1) a fuzzy logic approach for best-effort traffic regulation (FuzzyQoS-1), (2) a new fuzzy Petri nets technique (FuzzyQoS-2) for modeling and analyzing the QoS decision making for traffic regulation control, and (3) a fuzzy logic approach for threshold buffer management (FuzzyQoS-3). In FuzzyQoS-1, the feedback delay information received from the network is used to perform a fuzzy regulation for best-effort traffic. Using fuzzy logic, FuzzyQoS-3 uses fuzzy thresholds to adapt to the dynamic conditions. The evaluation of FuzzyQoS performances was studied under different mobility, channel, and traffic conditions. The results of simulations confirm that a cross layer design using fuzzy logic at different levels can achieve low and stable end-to-end delay, and high throughput under different network conditions. These results will benefit delay- and jitter-sensitive real-time services.     

Geometric spanners for wireless ad hoc networks

We propose a new geometric spanner for static wireless ad hoc networks, which can be constructed efficiently in a localized manner. It integrates the connected dominating set and the local Delaunay graph to form a backbone of the wireless network. Priori arts showed that both structures can be constructed locally with bounded communication costs. This new spanner has these following attractive properties: 1) the backbone is a planar graph, 2) the node degree of the backbone is bounded from above by a positive constant, 3) it is a spanner for both hops and length, 4) it can be constructed locally and is easy to maintain when the nodes move around, and 5) moreover, the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance.     

Context-aware broadcasting approaches in mobile ad hoc networks

The aim of this paper is to compare different context-aware broadcasting approaches in mobile ad hoc networks (MANETs) and to evaluate their respective performances. Message broadcasting is one of the core challenges brought up by distributed systems and has therefore largely been studied in the context of traditional network structures, such as the Internet. With the emergence of MANETs, new broadcasting algorithms especially geared at these networks have been introduced. The goal of these broadcasting algorithms is to ensure that a maximum number of nodes deliver the broadcasted message (reliability), while ensuring that the minimum number of nodes retransmit the broadcasted message (efficiency), in order to save their resources, such as bandwidth or battery. In recent years, as more and more mobile devices have become context-aware, several broadcasting algorithms have been introduced that take advantage of contextual information in order to improve their performance. We distinguish four approaches with respect to context: (1) context-oblivious approaches, (2) network traffic-aware approaches, (3) power-aware approaches, and (4) location-aware approaches. This paper precisely aims at presenting these four different broadcasting approaches and at measuring the performance of algorithms built upon them.     

Flooding in wireless ad hoc networks

In an ad hoc network, each host assumes the role of a router and relays packets toward final destinations. This paper studies efficient routing mechanisms for packet flooding in ad hoc wireless networks. Because a packet is broadcast to all neighboring nodes, the optimality criteria of wireless network routing are different from that of the wired network routing. We show that the minimum cost flooding tree problem is similar to MCDS (Minimum Connected Dominating Set) problem and prove the NP-completeness of the minimum cost flooding tree problem. Then, we propose two flooding methods: self-pruning and dominant pruning. Both methods utilize the neighbor information to reduce redundant transmissions. Performance analysis shows that both methods perform significantly better than the blind flooding. Especially, dominant pruning performs close to the practically achievable best performance limit.     

一种能量高效的Ad hoc无线网络广播算法

广播在Ad hoc无线网络中有着广泛的应用,而Ad hoc网络节点资源、网络资源严重受限,广播引起的广播风暴问题加剧了资源的消耗。提出了一种能量高效的无冲突的广播策略,该策略利用所有两跳邻节点的剩余能量和度等信息选择前向转播节点,并将前向转播节点分为相互不干扰的独立子集,统一为独立子集设置退避时间,避免冲突的发生。该策略平衡了网络中节点的能量消费、延长了网络寿命,同时减少了广播延迟和转播冗余,确保了广播的可达性。仿真结果也表明提高了广播的效率。     

Secure mutual authentication for ad hoc wireless networks

As wireless LANs and wireless terminals deployed, security and authentication, among other things, became important. We propose a mutual authentication scheme for access security among wireless terminals. We use user identification together with hardware identification in creating a certificate for the wireless access. And authentication is performed based on the certificate. It enables reliable user authentication, establishment and check of access rights (when a terminal is managed in connection with a network gateway), Peer-to-Peer access with authentication, and international roaming of terminals. This work was supported by the Korea Research Foundation Grant (KRF-2004-005-D00198).     

A scalable multimedia QoS architecture for ad hoc networks

Communication demands have grown from separate data and voice to integrated multimedia, paving the way to converging fixed, mobile and IP networks. Supporting Multimedia is a challenging task for wireless ad hoc network designers. Multimedia forms high data rate traffic with stringent Quality of Service (QoS) requirements. Wireless ad hoc networks are characterized by frequent topology changes, unreliable wireless channel, network congestion and resource contention. Providing scalable QoS is the most important challenge for multimedia delivery over ad hoc networks. We introduce here a provisioning and routing architecture for ad hoc networks which scales well while provisioning QoS. The proposed architecture is analysed using a mix of HTTP, voice and video streaming applications over 54 Mbps 802.11 g-based ad hoc networks. The architecture is simulated and compared to well-known routing protocols using the OPNET Modeller. The results show that our architecture scales well with increase in the network size, and outperforms well-known routing protocols.     

Providing MAC QoS for multimedia traffic in 802.11e based multi-hop ad hoc wireless networks

Ad hoc wireless networks with their widespread deployment, now need to support applications that generate multimedia and real-time traffic. Video, audio, real-time voice over IP, and other multimedia applications require the network to provide guarantees on the Quality of Service (QoS) of the connection. The 802.11e Medium Access Control (MAC) protocol was proposed with the aim of providing QoS support at the MAC layer. The 802.11e performs well in wireless LANs due to the presence of Access Points (APs), but in ad hoc networks, especially multi-hop ones, it is still incapable of supporting multimedia traffic.One of the most important QoS parameters for multimedia and real-time traffic is delay. Our primary goal is to reduce the end-to-end delay, thereby improving the Packet Delivery Ratio of multimedia traffic, that is, the proportion of packets that reach the destination within the deadline, in 802.11e based multi-hop ad hoc wireless networks.Our contribution is threefold: first we propose dynamic ReAllocative Priority (ReAP) scheme, wherein the priorities of packets in the MAC queues are not fixed, but keep changing dynamically. We use the laxity and the hop length information to decide the priority of the packet. ReAP improves the PDR by over 28% in comparison with 802.11e, especially under heavy loads. Second, we introduce Adaptive-TXOP (A-TXOP), where transmission opportunity (TXOP) is the time interval during which a node has the right to initiate transmissions. This scheme reduces the delay of video traffic by reducing the number of channel accesses required to transmit large video frames. It involves modifying the TXOP interval dynamically based on the packets in the queue, so that fragments of the same packet are sent in the same TXOP interval. A-TXOP is implemented over ReAP to further improve the performance of video traffic. ReAP with A-TXOP helps in reducing the delay of video traffic by over 27% and further improves the quality of video in comparison with ReAP without A-TXOP. Finally, we have TXOP-sharing, which is aimed at reducing the delay of voice traffic. It involves using the TXOP to transmit to multiple receivers, in order to utilize the TXOP interval fully. It reduces the number of contentions to the channel and thereby reduces the delay of voice traffic by over 14%. A-TXOP is implemented over ReAP to further improve the performance of voice traffic. The three schemes (ReAP, A-TXOP, and TXOP-sharing) work together to improve the performance of multimedia traffic in 802.11e based multi-hop ad hoc wireless networks.     

A novel range-free localization based on regulated neighborhood distance for wireless ad hoc and sensor networks

Range-free localization methods are suitable for large scale wireless ad hoc and sensor networks due to their less-demanding hardware requirements. Many existing connectivity- or hop-count-based range-free localization methods suffer from the hop-distance ambiguity problem where a node has a same distance estimation to all of its one-hop neighbors. In this paper, we define a new measure, called regulated neighborhood distance (RND), to address this problem by relating the proximity of two neighbors to their neighbor partitions. Furthermore, we propose a new RND-based range-free localization method, and compare our localization algorithm with peer classical algorithms in different network scenarios, which include grid deployment, random uniform deployment, non-uniform deployment and uniform deployment with a coverage hole. Simulation results show that ours can achieve better and reliable localization accuracy in these network scenarios.     

A multi-timescale cross-layer approach for wireless ad hoc networks

Conventionally, cross-layer designs with same timescale updates can work well; however, there is a difference in layers’ timescales and each layer normally operates at its corresponding timescale when implemented in real systems. To respect this issue, in this article, we introduce a multi-timescale cross-layer design along with three sets of constraints: congestion control, link delay, and power control and with the objective of maximizing the overall utility and minimizing the total link delay and power consumption. The proposed procedure can be implemented in a distributed fashion, which not only guarantees truly optimal solutions to the underlying problem, but also adheres to the natural timescale difference among layers. Finally, the numerical results further solidify the efficacies of our proposal compared to the current frameworks.     

Double sense multiple access for wireless ad hoc networks

In wireless ad hoc networks, the major quality of service (QoS) concern and challenge in the design and analysis of contention-based medium access control (MAC) protocols is to achieve good throughput and access delay performance in the presence of hidden terminals, which are defined as the terminals out of the radio coverage area of an intended transmitter but within that of the receiver. We propose and analyze in this paper a new dual-channel random access protocol, called “Double Sense Multiple Access” (DSMA), for improving QoS support in wireless ad hoc networks. By separating the transmissions of ready-to-send (RTS) and data packets into two time-slotted channels and by introducing a novel double sense mechanism, DSMA completely solves the hidden terminal problem and can guarantee the success transmission of data packets. By taking into account the most complex network scenario in which all transmitters are hidden terminals with respect to each other, key QoS metrics such as throughput, blocking probability and access delay are derived mathematically for the proposed DSMA protocol. These analytical results are verified by extensive computer simulations.     

一种基于分布式ad hoc无线传感器网络的辅助认证机制

介绍了无线网络中一个基于对称加密算法的物理层辅助消息认证机制,在此基础上提出了一个基于广播信道的新型消息认证机制.提出的机制通过利用物理层信道响应的时间和空间的独立性将传统的消息认证机制和物理层认证机制相结合,达到快速认证的目标而且传输负载最小.并与公钥基础的物理层辅助认证机制和传统的上层认证机制进行了比较,也进行了扩展分析和仿真测试,验证了所提出认证机制的性能.     

Trust-based security for wireless ad hoc and sensor networks

Wireless sensors networks are susceptible to a large number of security threats, and because of the communication, computation and delay constraints of most applications that run on top of these networks, traditional security mechanisms cannot be used. Trust and reputation have been recently suggested as an effective security mechanism for open environments such as the Internet, and considerable research has been done on modeling and managing trust and reputation. Using the trust and reputation management scheme to secure wireless sensor networks (WSNs) requires paying close attention to the incurred bandwidth and delay overhead, which have thus far been overlooked by most research work. In this paper, we propose a novel agent-based trust and reputation management scheme (ATRM) for wireless sensor networks. The objective of the scheme is to manage trust and reputation locally with minimal overhead in terms of extra messages and time delay. Throughout the entirety of this paper, we describe our scheme and prove its correctness. We will also present our extensive performance evaluation results, which clearly show that trust and reputation can be computed in wireless sensor networks with minimal overhead.     

Efficient implementations of all-to-all broadcasting in mobile ad hoc networks

In order to ease the challenging task of information dissemination in a MANET, we employ a legend: a data structure passed around a network to share information with all the mobile nodes. Our motivating application of the legend is sharing location information. Previous research shows that a simplistic legend performs better than other location services in the literature. To realize the full potential of legend-based location services, we propose three methods for the legend to traverse a network and compare their performance in simulation. Two of our proposed methods are novel, and the third is an improvement on an existing method. We also evaluate several general improvements to the traversal methods, and describe our way of making the legend transmission reliable. The result is a simple, lightweight location service that makes efficient use of network resources. Beyond using the legend as a location service, we discuss several implementation aspects of providing an efficient all-to-all broadcast operation, including legend reliability, preventing duplicate legends, using a legend in dynamic networks, and working with non-synchronized clocks. We also provide pseudocode for our legend traversal methods to aid implementation.