Performance evaluation of dynamic probabilistic broadcasting for flooding in mobile ad hoc networks

In mobile ad hoc networks (MANETs), flooding is a required message dissemination technique for network-wide broadcast. The conventional blind flooding algorithm causes broadcast storm problem, a high number of unnecessary packet rebroadcasts thus resulting in high contention and packet collisions. This paper proposes a new probabilistic approach that dynamically fine-tunes the rebroadcasting probability of a node for routing request packets (RREQs) according to the number of neighbour nodes. We evaluate the performance of the proposed approach for the ad hoc on demand distance vector (AODV) routing protocol and compared against the blind flooding, fixed probabilistic and adjusted probabilistic flooding [L.M.M.M. Bani-Yassein, M. Ould-Khaoua et al., Performance analysis of adjusted probabilistic broadcasting in mobile ad hoc networks, International Journal of Wireless Information Networks 13(2) (2006) 127–140; M.B. Yassein, M.O. Khaoua et al., Improving route discovery in on-demand routing protocols using local topology information in MANETs, Proceedings of the ACM international workshop on Performance Monitoring, Measurement, and Evaluation of Heterogeneous Wireless and Wired Networks, Terromolinos, Spain, ACM Press, 2006, pp. 95–99.] approaches. The simulation results show that our proposed approach demonstrates better performance than blind flooding, fixed probabilistic and adjusted flooding approaches.     

Adjusted probabilistic route discovery in mobile ad hoc networks

Conventional on-demand route discovery methods in mobile ad hoc networks (MANET) employ simple flooding method, where a mobile node blindly rebroadcasts received route request (RREQ) packets until a route to a particular destination is established. This can potentially lead to high channel contention, causing redundant retransmissions and thus excessive packet collisions in the network. This paper proposed two new probabilistic methods that can significantly reduce the number of RREQ packets transmitted during route discovery operation. Our simulation analysis reveals that equipping AODV with an appropriate probabilistic route discovery method can result in significant performance improvements in terms of routing overhead, MAC collisions and end-to-end delay while still achieving a good throughput when compared with the traditional AODV.     

A new probabilistic broadcasting scheme for mobile ad hoc on-demand distance vector (AODV) routed networks

Broadcast is a fundamental operation used in Mobile Ad hoc NETworks (MANETs) for many services, such as route discovery and sending information messages. The direct method to perform broadcast is a simple flooding, which can decrease the performance of MANET. Recently, a probabilistic approach to flooding has been proposed as one of most important suggested solutions to solve the broadcast storm problem, which leads to the collision, contention and duplicated messages. This paper presents the Smart Probabilistic Broadcasting (SPB) as a new probabilistic method to improve the performance of existing on-demand routing protocols by reducing the RREQ overhead during the rout discovery operation. The simulation results show that the combination of AODV and a suitable probabilistic rout discovery can reduce the average end-to-end delay as well as overhead, while achieving low normalized routing load, compared to AODV that uses fixed probability and blind flooding. Simulation experiments have been conducted to examine our proposed scheme. The results show that SPB outperforms its counterparts and opens up a promising framework towards optimal probabilistic broadcasting.     

Triangle-based routing for mobile ad hoc networks

Routing protocols for Mobile ad hoc networks (MANETs) have been studied extensively in the past decade. Routing protocols for MANETs can be broadly classified as reactive (on-demand), proactive, hybrid and position-based. Reactive routing protocols are attractive because a route between a source and a destination is established only when it is needed. Such protocols, unlike proactive protocols, do not have high overhead for route maintenance and are especially suitable for networks in which not all nodes communicate frequently. One problem with existing reactive routing protocols is the propagation of redundant route request messages during route discovery. In this paper, we present a low-overhead reactive routing protocol which reduces propagation of redundant route request messages. We also compare its performance with the well-known reactive routing protocol AODV.     

A stable weight-based on-demand routing protocol for mobile ad hoc networks

A mobile ad hoc network (MANET) consists of a set of mobile hosts that can communicate with each other without the assistance of base stations. In MANETs, the high mobility of mobile nodes is a major reason for link failures. In this paper, we propose a stable weight-based on-demand routing protocol (SWORP) for MANETs. The proposed scheme uses the weight-based route strategy to select a stable route in order to enhance system performance. The weight of a route is decided by three factors: the route expiration time, the error count, and the hop count. Route discovery usually first finds multiple routes from the source node to the destination node. Then the path with the largest weight value for routing is selected. Simulation results show that the proposed SWORP outperforms DSR, AODV, and AODV-RFC, especially in a high mobility environment.     

节点度估计和静态博弈转发策略的Ad Hoc网络路由协议

针对Ad Hoc网络路由发现过程中广播路由请求分组导致的广播风暴问题，提出了一种基于节点度估计和静态博弈转发策略的Ad Hoc网络路由协议NGRP.NGRP考虑边界影响，采用分段函数的思想将网络场景分为中心、边和角区域，分别估算网络中节点在不同区域的节点度，避免了周期性广播Hello消息获取节点度导致的开销；NGRP路由请求分组的转发采用静态博弈转发策略，利用节点度估算参与转发路由请求分组的节点数量，将转发和不转发作为策略集合，设计效益函数，通过纳什均衡获得节点转发路由请求分组的转发概率，从而减少了路由请求分组广播过程中产生的大量的冗余、竞争和冲突，提高了路由发现过程中路由请求分组的广播效率.运用NS-2对协议的性能进行大量的仿真，结果表明：NGRP的分组投递率、路由开销、MAC层路由开销和吞吐率这4项指标明显优于AODV+FDG，AODV with Hello和AODV without Hello协议.     

Dynamic probabilistic broadcasting in MANETs

In mobile ad hoc networks (MANETs), the efficiency of broadcasting protocol can dramatically affect the performance of the entire network. Appropriate use of a probabilistic method can reduce the number of rebroadcasting, therefore reduce the chance of contention and collision among neighboring nodes. A good probabilistic broadcast protocol can achieve higher throughput and lower energy consumption, without sacrificing the reachability or having any significant degradation. In this paper, we propose a probabilistic approach that dynamically adjusts the rebroadcasting probability as per the node distribution and node movement. This is done based on locally available information and without requiring any assistance of distance measurements or exact location determination devices. We evaluate the performance of our approach by comparing it with the AODV protocol (which is based on simple flooding) as well as a fixed probabilistic approach. Simulation results show our approach performs better than both simple flooding and fixed probabilistic schemes.     

Link stability based multicast routing scheme in MANET

The group-oriented services are one of the primary application classes that are addressed by Mobile Ad hoc Networks (MANETs) in recent years. To support such services, multicast routing is used. Thus, there is a need to design stable and reliable multicast routing protocols for MANETs to ensure better packet delivery ratio, lower delays and reduced overheads. In this paper, we propose a mesh based multicast routing scheme that finds stable multicast path from source to receivers. The multicast mesh is constructed by using route request and route reply packets with the help of multicast routing information cache and link stability database maintained at every node. The stable paths are found based on selection of stable forwarding nodes that have high stability of link connectivity. The link stability is computed by using the parameters such as received power, distance between neighboring nodes and the link quality that is assessed using bit errors in a packet. The proposed scheme is simulated over a large number of MANET nodes with wide range of mobility and the performance is evaluated. Performance of the proposed scheme is compared with two well known mesh-based multicast routing protocols, i.e., on-demand multicast routing protocol (ODMRP) and enhanced on-demand multicast routing protocol (EODMRP). It is observed that the proposed scheme produces better packet delivery ratio, reduced packet delay and reduced overheads (such as control, memory, computation, and message overheads).     

Improving discovery phase of reactive ad hoc routing protocols using Jaccard distance

Recently, more and more research focus has been directed towards optimum designs for Mobile Ad Hoc Networks (MANETs). In this paper, the authors explore novel broadcasting schemes to improve the discovery phase of reactive routing protocols in MANETs. The objective is to reduce the redundancy of routing packets during the discovery phase of the reactive routing protocols for MANETs. For this purpose, the Jaccard distance is used to select dissimilar nodes during the discovery phase in order to reduce redundancy. Furthermore, it is shown that the Jaccard distance is correlated to the Euclidean distance. The simulation results obtained indicate that the Jaccard distance is a suitable metric for improving the discovery phase of the reactive routing protocols in MANETs.     

移动ad hoc网络中DOS攻击及其防御机制

移动ad hoc网络由于其动态拓扑、无线信道以及各种资源有限的特点,特别容易遭受拒绝服务(DOS)攻击．提出了移动ad hoc网络中一种新的DOS攻击模型——ad hoc flooding攻击及其防御策略．该攻击主要针对移动ad hoc网络中的按需路由协议,如AODV,DSR等．ad hoc flooding攻击是通过在网络中泛洪发送超量路由查询报文及数据报文,大量地占用网络通信及节点资源,以至于阻塞节点正常的通信．分析ad hoc flooding攻击之后,提出了两种防御策略：其一是邻居阻止,即当入侵者发送大量路由查询报文时,邻居节点降低对其报文的处理优先级,直至不再接收其报文．其二是路径删除,即目标节点将入侵者发送攻击报文的路径删除,以阻止其继续发送攻击报文．模拟实验证实,通过这两种方法的结合．能够有效地阻止网络中的ad hoc flooding攻击行为．     

MANET与Internet互联时的增强型机制研究

已有的移动自组网与Internet的互联协议由于无法克服网关发现过程中的单向链路并且因盲目转播网关发现报文形成广播风暴等原因而致使性能严重恶化。该文提出了一种增强型的综合互联协议，该协议一方面采用效率较高的综合方式进行网关发现，另一方面则通过交换携带有对称邻居列表和非对称邻居列表的HELLO分组而有效克服了网关发现过程中的单向链路，同时抑制了广播风暴的形成。基于NS2的仿真结果显示该增强型的综合互联协议在不引入新控制分组的前提下能显著提升互联性能，降低互联开销。     

The role of congestion in probabilistic broadcasting for ubiquitous wireless multi-hop networks through mediation analysis

Broadcast schemes play an important role in the performance of mobile ad hoc networks, which are a clear example of ubiquitous wireless multi-hop networks where nodes collaborate in a distributed way. They are widely used as a dissemination mechanism and as a part of the discovery phase of routing protocols. The simple flooding algorithm is the usual mechanism employed in mobile ad hoc networks, but its inefficiency has been demonstrated in congested scenarios due to the high number of collisions and contentions. However, these problems can be partially alleviated by using a probabilistic broadcast approach in which every node forwards the incoming packets according to a certain forwarding probability. In this paper, we use a simple probabilistic broadcast protocol to evaluate the effects of congestion on the performance of broadcasting in ad hoc networks through a mediation analysis. We hypothesize that the congestion mediates in the relationship between the forwarding probability (independent variable) and the output metric (dependent variable). We consider several output metrics according to the application of the broadcasting protocol such as reachability, broadcasting delay, packet delivery fraction and end to end delay. The simulation results show the existence of the mediating effects and how such effects may be counterbalanced depending on the target use of the probabilistic broadcast scheme.     

按需式ad hoc移动网络路由协议的研究进展

Ad hoc移动网络是一种完全由移动主机构成的网络，网络拓扑易变，带宽，能源有限是ad hoc移动网络的主要特点，针对这些特点，目前设计的ad hoc路由协议大多采用按需查找方式，该文介绍了这方面研究的最新进展，对几种典型的按需路由协议进行了说明，分析和综合比较，文中分析了目前协议存在的一些问题并提出了相应的改进方法，最后指出了下一步研究方向。     

Improving source routing reliability in mobile ad hoc networks

In this paper, we propose a novel on-demand routing protocol called backup source routing (BSR) to establish and maintain backup routes that can be utilized after the primary path breaks. The key advantage of BSR is the reduction of the frequency of route discovery flooding, which is recognized as a major overhead in on-demand protocols. We define a new routing metric, called the route reliability, and use it to provide the basis for the backup path selection. We use a heuristic cost function to develop an analytical model and an approximation method to measure this metric. Various algorithms for our BSR protocol in the route discovery phase and route maintenance phase have been designed based on this cost function. Extensive simulations demonstrated that our routing strategy has two interesting features: 1) in less stressful situations of lower mobility, BSR has similar performance to DSR, 2) in more challenging situations of high mobility, BSR can improve the performance significantly.     

A probabilistic and opportunistic flooding algorithm in wireless sensor networks

In wireless sensor networks, many communication protocols and applications rely on flooding for various networking purposes. Prior efforts focus on how to design efficient flooding algorithms; that is, they seek to achieve full reliability while reducing the number of redundant broadcasting across the network. To achieve efficient flooding, most of the existing protocols try to reduce the number of transmissions, which is decided without considering any online transmission result. In this paper, we propose a probabilistic and opportunistic flooding algorithm that controls rebroadcasts and retransmissions opportunistically. It seeks to achieve a target reliability required by an application. For this purpose, it makes a given node select only the subset of its one-hop neighbors to rebroadcast the same message. It considers node relations such as link error rates among nodes in selecting eligible neighbors to rebroadcast. The sender controls the number of retransmissions opportunistically by tracking the current status of message reception at its neighbors. Simulation is carried out to reveal that our proposed scheme achieves the given target reliability with less overhead than other flooding algorithms in most cases, thus prolonging the network lifetime.     

PCBA: A priority-based competitive broadcasting algorithm in Mobile Ad Hoc Networks

Broadcasting operations are of great importance in Mobile Ad Hoc Networks (MANETs) since they are frequently executed. A straightforward broadcasting by flooding will produce serious redundancy, contention and collision, and furthermore it will result in the perfor-mance degradation of the networks. PCBA, a Priority-based Competitive Broadcasting Algorithm,is proposed in this paper to solve the above problem. In this algorithm, hosts with larger Priority Index (PD have higher probability to rebroadcast relevant messages while some other hosts will be prevented from rebroadcasting according to the competing policy. PCBA is a distributed algorithm and will not increase communication overhead. Through the analyses and extensive simulations,the authors demonstrate that PCBA has advantages in availability and scalability. It can signif-icantly reduce the rebroadcast redundancy. In addition, PCBA can also be further used in other applications such as routing discovery schemes, enhancing the performance.     

A Distributed and Efficient Flooding Scheme Using 1-Hop Information in Mobile Ad Hoc Networks

Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference with the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100 percent deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is minimal and 2) the time complexity for computing forwarding nodes is the lowest, which is O(nlogn), where n is the number of neighbors of a node. Extensive simulations have been conducted and simulation results have shown the excellent performance of our algorithm     

A new dynamic counter-based broadcasting scheme for Mobile Ad hoc Networks

Broadcasting is an essential operation in Mobile Ad hoc Networks (MANETs) to transmit a message (data packet) from the sender to the rest of the network nodes. Although flooding is the simplest mechanism for broadcasting, where each node retransmits every uniquely received message exactly once, it is usually costly and results in serious redundancy, contention and collisions in the network. These problems are widely referred to as the broadcast storm problem. In the light of this, this study introduces a new counter-based broadcasting scheme to achieve efficient broadcasting in MANETs. This is achieved by using a counter-based scheme with a dynamic threshold to increase the successful delivery rate of packets and enhance the throughput of the network. Extensive simulation experiments have been conducted. Our results show that the new scheme outperforms the well known exiting schemes, namely the two counter-based broadcasting scheme and blind flooding.     

ZigBee网络路由发现广播策略

在ZigBee网络中,具有路由能力的网络节点通过预先设定广播半径的广播路由请求命令帧实现路由发现,不受限制的数据广播会影响网络性能。结合网络节点的地址信息和邻居表信息,减小路由请求命令帧广播深度,提出一种改进的路由发现广播策略。仿真结果表明,使用该策略能实现最优路由发现,减少路由请求命令帧转发次数,改善网络性能。     

一种UC匿名的移动自组网概率组播策略

鉴于现有移动自组网匿名路由协议不能为组播提供匿名通信支持,而只能提供特定非形式化的匿名性分析,提出了一种UC(universally composable)匿名的移动自组网概率组播策略.在路由发现阶段,采用一次性密钥对保持路径记录私密.在数据分组传输阶段,采用Gossip机制、DH秘密路径及Bloom Filter编码实现匿名源路由组播.最后,采用UC框架分析了协议的匿名性,并对协议的性能进行了仿真.分析与仿真结果表明,该策略在实现匿名性的同时还提供了较好的可靠性.