应用于Ad Hoc网络中的密度自适应泛洪广播策略

针对Ad Hoc网络中泛洪广播机制可能带来的大量资源浪费问题,本文提出了一种新型的泛洪广播机制——密度自适应的泛洪广播策略.该策略根据发送节点的邻节点密度,以最密集节点的一次发送将覆盖较多节点为出发点,选取尽可能少的邻节点作为转发节点,减少了分组在网络中的重复传输,大大改善了网络的性能.仿真结果表明,密度自适应泛洪广播策略的性能明显优于普通的泛洪广播策略.     

一种在无线自组织网络中延长网络生存时间的累积广播算法

文章考虑一个无线自组织网络中的广播问题,分析研究了传统累积广播算法及其性能表现,提出了一种新颖的算法,延长生存时间累积广播算法(ELAB算法)。然后通过一个4节点网络模型详细阐述了这一算法,并将它扩展到N节点无线自组织网络中。理论分析和仿真结果证明,相比于传统累积广播算法,对于不同的网络结构和节点数量,ELAB算法可延长网络的生存时间至少50%。     

ADLE:一种Ad hoc网络分布式领导者选取算法

Ad hoc网络的动态拓扑结构和节点自组织给分布式算法的实现带来了诸多困难.Ad hoc网络分布式领导者选举算法:ADL.该算法基于广播机制,采用逻辑时戳保证消息的时序性,避免了节点饿死.同时,它通过缩小算法执行范围降低了消息复杂度,而且不需要节点了解系统中所有节点的信息,因而能够适应Ad hoc网络的动态拓扑结构和节点频繁出入.分析与仿真结果表明该算法具有较低的消息复杂度、小响应延迟和公平性.     

Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks

Network wide broadcasting is a fundamental operation in ad hoc networks. In broadcasting, a source node sends a message to all the other nodes in the network. In this paper, we consider the problem of collision-free broadcasting in ad hoc networks. Our objective is to minimize the latency and the number of transmissions in the broadcast. We show that minimum latency broadcasting is NP-complete for ad hoc networks. We also present a simple distributed collision-free broadcasting algorithm for broadcasting a message. For networks with bounded node transmission ranges, our algorithm simultaneously guarantees that the latency and the number of transmissions are within $O(1)$ times their respective optimal values. Our algorithm and analysis extend to the case when multiple messages are broadcast from multiple sources. Experimental studies indicate that our algorithms perform much better in practice than the analytical guarantees provided for the worst case.      

A Distributed Intelligent Broadcasting Protocol for Mobile Ad Hoc Networks

The control and routing performances of mobile ad hoc networks (MANETs) depend upon the efficiency of the network-wide broadcasting schemes that are in place. Ad hoc networks are often characterized by poor infrastructure quality, limited resources, dynamic variation and a need for mobility; therefore, ease of deployment, adaptability and potential for energy-savings are the primary drivers considered in the design of typical broadcasting schemes. This paper proposes a distributed intelligent broadcasting protocol (DIBP) that is capable of dynamically determining the broadcasting nodes in a MANET, based upon the distribution of network nodes. This eliminates the need for active network monitoring and periodical maintenance is not required. In addition, the distributed intelligent broadcasting protocol employs an adjustable parameter for determining the broadcasting node, broadcasting timing and the number of broadcasting nodes. This parameter can be changed dynamically based on different operational requirements; such as energy savings, hop count, network delay and other similar targets. Simulations of networks employing the protocol yield results showing that the DIBP performs better in terms of delivery delay, number of rebroadcast nodes, and delivery ratio.     

多跳无线网络中无需邻节点信息的空间覆盖广播算法

针对多跳无线网络中广播的转发冗余问题,该文提出了一种无需邻节点信息的空间覆盖广播(Space-Covered Broadcast,SCB)算法。SCB算法通过优化转发节点的空间分布达到利用最少数目的转发节点实现对网络空间的覆盖,从而在保证较高送达率的同时明显降低了广播的转发次数。由于无需邻节点信息和网络拓扑信息,SCB算法降低了带宽和存储计算等开销;并且,转发节点的选择由接收节点通过延时转发机制来完成,因而SCB算法能够自动适应信道状况,避免信道变化造成的传输错误。仿真结果表明：该算法在不同的节点密度和网络负载条件下能够明显提高广播的传输效率。     

Energy and Spatial Reuse Efficient Network-Wide Real-Time Data Broadcasting in Mobile Ad Hoc Networks

In this paper, we present NB-TRACE, which is an energy-efficient network-wide voice broadcasting architecture for mobile ad hoc networks. In the NB-TRACE architecture, the network is organized into overlapping clusters through a distributed algorithm, where the clusterheads create a nonconnected dominating set. Channel access is regulated through a distributed TDMA scheme maintained by the clusterheads. The first group of packets of a broadcast session is broadcast through flooding, where each data rebroadcast is preceded by an acknowledgment to the upstream node. Nodes that do not get an acknowledgment for a predetermined time, except the clusterheads, cease to rebroadcast, which prunes the redundant retransmissions. The connected dominating set formed through this basic algorithm is broken in time due to node mobility. The network responds to the broken links through multiple mechanisms to ensure the maintenance of the connected dominating set. We compare NB-TRACE with four network layer broadcast routing algorithms (Flooding, Gossiping, Counter-based broadcasting, and Distance-based broadcasting) and three medium access control protocols (IEEE 802.11, SMAC, and MH-TRACE) through extensive ns-2 simulations. Our results show that NB-TRACE outperforms other network/MAC layer combinations in minimizing energy dissipation and optimizing spatial reuse, while producing competitive QoS performance.     

Tree Based Broadcast in Ad Hoc Networks

Although broadcasting using tree structure established in a network is a well known and widely used technique, it is typically claimed to be inappropriate for ad hoc networks, being the maintained tree very sensitive to network changes. On the contrary this paper presents an efficient tree based broadcasting scheme, which is reliable and stable even in case of the ever changing network structure of the ad hoc networks.To achieve this, first, a novel method is presented to maintain a spanning tree in an ad hoc network in a fully distributed, on-line and asynchronous way. Once the tree is established the broadcast itself is performed based on this tree. Some further improvements on the basic algorithm are also presented that reduce the resource requirements even more, increase the stability of the tree, enable the mobility of the nodes to be taken into account and make the method more configurable.As it is shown by simulation, the obtained broadcast scheme is stable, reliable and it uses small amount of resources: the acyclic structure of the broadcast tree ensures that the nodes get the broadcast messages only once, so the broadcast needs little bandwidth and the nodes need not store the recent broadcast messages, reducing the computational and memory requirements.As a byproduct a technique is proposed to measure the mobility of the nodes. This technique needs no additional GPS device or any geographical information but it is based on the stability of the links of the node.Alpár Jüttner received his M. Sc. degree in 1998 at the Eötvös Loránd University of Budapest, where he is currently working on his Ph. D. at Operational Research Departement. He also works as a research fellow at Ericsson Traffic Analysis and Network Performance Laboratory in Budapest, Hungary. His main interests are combinatorial optimization and its applications.Ádám Magi received his M. Sc. degree in 1996 at the Technical University of Budapest in Electrical Engineering. He is currently working on his Ph. D. there. He also works as a research fellow at Ericsson Traffic Analysis and Network Performance Laboratory in Budapest, Hungary. His main interests are mobile ad hoc networks and routing in telecommunication networks.     

DBLAR：A DISTANCE-BASED LOCATION-AIDED ROUTING FOR MANET

In location-aided routing of Mobile Ad hoc NETworks (MANET), nodes mobility and the inaccuracy of location information may result in constant flooding, which will reduce the network performance. In this paper, a Distance-Based Location-Aided Routing (DBLAR) for MANET has been proposed. By tracing the location information of destination nodes and referring to distance change between nodes to adjust route discovery dynamically, the proposed routing algorithm can avoid flooding in the whole networks. Besides, Distance Update Threshold (DUT) is set up to reach the balance between real-time ability and update overhead of location information of nodes, meanwhile, the detection of relative distance vector can achieve the goal of adjusting forwarding condition. Simulation results reveal that DBLAR performs better than LAR1 in terms of packet successful delivery ratio, average end-to-end delay and routing-load, and the set of DUT and relative distance vector has a significant impact on this algorithm.     

Improving broadcast performance by traffic isolation in wireless ad hoc networks

In this paper we propose a new broadcasting algorithm. In the proposed method we significantly reduce the broadcast overhead and also improve the broadcast delivery ratio in mobile networks. A novel traffic isolation method has been used which reduces the control message exchange. The proposed broadcasting method is based on a clustering method called ‘stability‐based clustering algorithm’ which had been proposed before. The broadcasting traffic is divided into internal (flow inside a cluster) and external traffic (flow among the clusters). For internal flooding traffic, cluster‐heads and gateways are responsible for re‐broadcasting but for external type, border nodes may perform the forwarding function as well. This simplifies the gateway selection method through the local selection of gateway nodes by its cluster head. Therefore, a cluster head selects gateway in its own cluster without any knowledge of other clusters. Considering the effect of mobility and node density, simulations have been conducted in a number of wireless environments. Simulation results show the broadcast coverage is close to 100% at different node speeds. Moreover, we study the broadcast parameters in light and dense networks and show improvement of the overhead and the number of forward nodes in comparison to other broadcasting methods. Copyright © 2005 John Wiley & Sons, Ltd.     

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.

     

Broadcasting with Controlled Redundancy and Improved Localization in Wireless Sensor Networks

Wireless sensor networks （WSNs） consist of sensor nodes that broadcast a message within a network. Efficient broadcasting is a key requirement in sensor networks and has been a focal point of research over the last few years. There are many challenging tasks in the network, including redundancy control and sensor node localization that mainly depend on broadcasting. In this paper, we propose a broadcasting algorithm to control redundancy and improve localization （BACRIL） in WSNs. The proposed algorithm incorporates the benefits of the gossip protocol for optimizing message broadcasting within the network. Simulation results show a controlled level of redundancy, which is up to 57.6% if the number of sensor nodes deployed in a 500 m×500 m area are increased from 50 to 500.     

Ad hoc网络中基于能量的AODV双径路由算法研究

在Ad hoc网络中AODV路由的健壮性、路由开销、网络的生存时间以及分组报文传送率等都是评价该算法优良的指标。为了提高该路由算法的各项指标本文提出了改进的路由算法协议,在Ad hoc网络中避免使用的低于能量阈值的节点作为路由节点以提高整体网络的生存时间,提供主次路径使报文的到达率、网络的健壮性得以提高,同时也减少了链路的修复,减少了路由开销。     

Broadcast capacity of wireless networks

We present an upper bound on the broadcast capacity of arbitrary ad hoc wireless networks. The throughput obtainable by each node for broadcasting to-all-of the other nodes in a network consisting of n nodes with- fixed transmission ranges and C bits per second channel capacity is bounded by O(C/n), which is equivalent to the upper bound for per node capacity of a fully connected single-hop network.     

Minimum power multicast algorithms for wireless networks with a Lagrangian relaxation approach

Energy efficiency is crucial to the implementation of broadcast and multicast services in wireless ad hoc and sensor networks. This paper proposes a path-based power-efficient approach that minimizes energy consumption in the network by optimizing the transmission ranges of all nodes. Unlike existing link-based and node-based solutions, the proposed approach, which is applicable to both static and mobile wireless networks, constructs minimum-power broadcast trees. This study uses Lagrangian Relaxation (LR) to decompose the tree-construction problem, which is NP-complete, into multiple independently solvable sub-problems. The resulting Lagrange dual solution ensures a lower bound on the objective function value. The proposed approximation heuristic solves the primal problem by obtaining the upper bound of the objective value based on the information from the set of Lagrange multipliers. This study develops a decentralized, near-optimal algorithm to solve the problem. Simulation results show that in randomly generated networks, the proposed method outperforms the existing Minimum Shortest Path Tree (MSPT) algorithm, Prim’s Minimum Spanning Tree (PMST) algorithm, and the Broadcast Incremental Power (BIP) algorithm by 30, 10, and 5%, respectively.     

Cluster overlay broadcast (COB): MANET routing with complexity polynomial in source-destination distance

Routing algorithms with time and message complexities that are provably low and independent of the total number of nodes in the network are essential for the design and operation of very large scale wireless mobile ad hoc networks (MANETs). In this paper, we develop and analyze Cluster Overlay Broadcast (COB), a low-complexity routing algorithm for MANETs. COB runs on top of a one-hop cluster cover of the network, which can be created and maintained using, for instance, the Least Cluster Change (LCC) algorithm. We formally prove that the LCC algorithm maintains a cluster cover with a constant density of cluster leaders with minimal update cost. COB discovers routes by flooding (broadcasting) route requests through the network of cluster leaders with a doubling radius technique. Building on the constant density property of the network of cluster leaders, we formally prove that, if there exists a route from a source to a destination node with a minimum hop count of A, then COB discovers a route with at most O(/spl Delta/) hops from the source to the destination node in at most O(/spl Delta/) time and by sending at Most O(/spl Delta//sup 2/) messages. We prove this result for arbitrary node distributions and mobility patterns and also show that COB adapts asymptotically optimally to the mobility of the nodes. In our simulation experiments, we examine the network layer performance of COB, compare it with Dynamic Source Routing, and investigate the impact of the MAC layer on COB routing.     

基于极大权的最小连通支配集启发式算法

Ad hoc无线网络中基于最小连通支配集(MCDS)的路由是一个引人瞩目的方法,文中提出了一种基于极大权的MCDS的启发式算法,确保了性能强的主机担任网关节点的角色,能更好的协调管理网络中其他的节点,从而保持MCDS的相对稳固性并为全网中的广播和路由操作提供一个高效的通信基础.仿真结果表明,该算法能在保证生成权和极大的连通支配集的同时也确保它的极小性,因此能有效地用于基于MCDS的路由设计中.     

Cost Based Data Dissemination in Satellite Networks

We consider the problem of data dissemination in a broadcast network. In contrast to previously studied models, broadcasting is among peers, rather than client server. Such a model represents, for example, satellite communication among widely distributed nodes, sensor networks, and mobile ad hoc networks. We introduce a cost model for data dissemination in peer to peer broadcast networks. The model quantifies the tradeoff between the inconsistency of the data, and its transmission cost; the transmission cost may be given in terms of dollars, energy, or bandwidth. Using the model we first determine the parameters for which eager (i.e. consistent) replication has a lower cost than lazy (i.e. inconsistent) replication. Then we introduce a lazy broadcast policy and compare it with several naive or traditional approaches to solving the problem.     

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.     

一个基于层次结构的Ad hoc网络移动模式

采用连通图中极小支配集概念对平面分布的Ad hoc网络进行层次划分；提出移动节点之间的相关度概念，利用GM-BFS算法来实现Ad hoc网络的簇结构生成。结果显示提出的分簇模式能较好地适应网络的扩展、簇生成算法具有收敛快的特征。