Optimizing responses to broadcast messages in radio networks

Algorithms to optimize the performance of response traffic for broadcast messages in a packet-switched radio network are studied. The situation considered here involves a source node sending a broadcast message to all destinations and collecting positive response packets from these destinations in a fully connected packet radio network. The exact value of the number of destination nodes is unknown. A contention-based two-level protocol is described. Based on the protocol, an optimization problem is formulated in order to minimize the time for the source node to receive all the responses. Several algorithms are presented and numerical results of the corresponding optimization problems are obtained. These optimization problems are treated by the methods of dynamic programming. An extension of the basic scheme—multicast instead of full broadcast message—is also studied.     

Centralized asynchronous broadcast in radio networks

We study asynchronous broadcasting in packet radio networks. A radio network is represented by a directed graph, in which one distinguished source node stores a message that needs to be disseminated among all the remaining nodes. An asynchronous execution of a protocol is a sequence of events, each consisting of simultaneous deliveries of messages. The correctness of protocols is considered for specific adversarial models defined by restrictions on events the adversary may schedule. A protocol specifies how many times the source message is to be retransmitted by each node. The total number of transmissions over all the nodes is called the work of the broadcast protocol; it is used as complexity measure. We study computational problems, to be solved by deterministic centralized algorithms, either to find a broadcast protocol or to verify the correctness of a protocol, for a given network. The amount of work necessary to make a protocol correct may have to be exponential in the size of network. There is a polynomial-time algorithm to find a broadcast protocol for a given network. We show that certain problems about broadcasting protocols for given networks are complete in NP and co-NP complexity classes.     

分组无线网缠绕多路径数据路由协议仿真

在分组无线网的路由协议中,传统路由协议在恶意节点数目较多时网络吞吐量较低,因此提出一种分组无线网缠绕多路径数据路由协议,利用获取的源节点数量信息与位置信息进行路由发现;根据路由发现结果建立从汇聚节点至源节点之间的路径,从而建立缠绕多径路由;对缠绕多径路由进行建簇与重构;进行支路径数优化,从而实现分组无线网缠绕多路径数据路由协议的构建。为了验证上述路由协议的网络吞吐量,将路由协议与基于链路状态的主动式多路径路由协议、基于动态源的按需式多路径路由协议、基于距离矢量的混合式多路径路由协议进行对比,上述四种路由协议在恶意节点数目为30时的网络吞吐量分别为69.5%、33.5%、23.6%、4.2%,通过比较可知,新提出的路由协议的网络吞吐量最高,证明了新路由协议的性能。     

Deadlock-free multicast wormhole routing in 2-D mesh multicomputers

Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms     

无线传感器网络机会路由协议—MORE的优化

无线传感器网络中的机会路由协议—MORE协议,即独立于MAC层的机会路由和编码协议,从对MORE协议的学习中,得知MORE协议在源节点准备发送数据包时,首先将K个数据包随机地分成批(batch)进行流内随机网络编码,再以广播的形式发送出去,这种提前设定好批的大小的方法不能满足实时的要求,对信道利用率和时延造成影响。针对MORE协议的这种弊端引入一种根据块时延的大小自主适应选择数据块大小的算法对MORE协议进行优化。     

Optimized broadcasting and multicasting protocols in cut-throughrouted networks

This paper addresses the one-to-all broadcasting problem and the one-to-many broadcasting problem, usually simply called broadcasting and multicasting, respectively. Broadcasting is the information dissemination problem in which a node of a network sends the same piece of information to all the other nodes. Multicasting is a partial broadcasting in the sense that only a subset of nodes forms the destination set. Both operations have many applications in parallel and distributed computing. In this paper, we study these problems in both line model, and cut-through model. The former assumes long distance calls between nonneighboring processors. The latter strengthens the line model by taking into account the use of a routing function. Long distance calls are possible in circuit-switched and wormhole-routed networks, and also in many networks supporting optical facilities. In the line model, it is well known that one can compute in polynomial time a [log₂n]-round broadcast or multicast protocol for any arbitrary network. Unfortunately such a protocol is often inefficient from a practical point of view because it does not use the resources of the network in a balanced way. In this paper, we present a new algorithm to compute broadcast or multicast protocols. This algorithm applies under both line and cut-through models. Moreover, it returns protocols that efficiently use the bandwidth of the network. From a complexity point of view, we also show that most of the optimization problems relative to the maximization of the efficiency of broadcast or multicast protocols in terms of switching time or vertex load are NP-complete. We have, however, derived polynomial efficient solutions for tree-networks     

基于分层结构的Ad Hoc网络应用层组播路由研究

提出了一种基于分层结构的Ad Hoc网络应用层组播路由协议HALMP,将网络划分为多个子网,利用虚拟成员节点和延迟响应机制优化子网内共享组播树,以最小生成树方式构建子网间的源-群首组播树,数据分组转发时对组成员节点分布密集的区域引入本地广播机制。仿真结果表明,这些策略的采用优化了组播树,提高了分组转发效率,协议具有较好的可扩展性。     

Time-Step Optimal Broadcasting in 3-D Meshes with Minimum Total Communication Distance

In this paper we propose a new minimum total communication distance (TCD) algorithm and an optimal TCD algorithm for broadcast in a 3-dimensional mesh (3-D mesh). The former generates a minimum TCD from a given source node, and the latter guarantees a minimum TCD among all the possible source nodes. These algorithms are based on a divide-and-conquer approach where a 3-D mesh is partitioned into eight submeshes of equal size. The source node sends the broadcast message to a special node called an eye in each submesh. The above procedure is then recursively applied in each submesh. The proposed approach can be generalized to a d-dimensional mesh or torus. In addition, the proposed approach can potentially be used to solve optimization problems in other collective communication operations.     

HM-MAC:一种支持广播的多信道传感器网络MAC协议

针对单Radio多信道MAC协议需要全网时间同步、占用大量正交信道、多信道隐终端较多以及单跳多信道广播数据大量丢失等问题,提出了一种基于竞争的多信道MAC协议--HM-MAC.该协议无需全网时间同步,通过动态预约技术降低了正交信道占用量,利用握手机制减少了多信道隐终端数目,同时,HM-MAC采用基于概率的广播发送者协调机制,减少了广播数据丢失,提高了广播效率.在理论上分析了所用信道数目、多信道隐终端数目以及广播效率等性能参数.实验结果表明:HM-MAC可以有效地解决多信道隐终端数目较多的问题,显著地提高了广播效率和网络吞吐量.     

一种多信道Ad hoc认知无线电网络密钥交互协议*

针对现有密钥协商协议没有考虑Ad hoc认知无线电网络多信道这一缺陷,提出一种多信道密钥协商协议（multi channels key agreement protocol,MCKAP）,通过建立多重图和替换广播操作减少信道冲突,优化协商路径提高共享密钥协商效率,利用信道属性为节点间选择合理位置,避免主用户干扰。该方案能有效地利用多信道提高共享密钥协商效率。最后通过理论分析和仿真实验证明该协议适用于Ad hoc认知无线电网络,具有较好的执行效率。     

A distributed multicast routing protocol for real-time multicast applications

Multicast routing is establishing a tree which is rooted from the source node and contains all the multicast destinations. A delay bounded routing tree is a tree in which the accumulated delay from the source node to any destination along the tree does not exceed a pre-specified bound. This paper presents a distributed routing protocol which constructs delay bounded routing trees for real-time multicast connections. A constructed routing tree has a near optimal network cost under the delay bound constraint. The proposed algorithm is fully distributed, efficient in terms of the number of messages required, and flexible in multicast membership changes. A large number of simulations have been done to show the network cost of the routing trees generated by our method is better than the other major existing algorithms.     

Weighted broadcast in linear radio networks

The weighted version of the broadcast range assignment problem in ad hoc wireless network is studied. Efficient algorithms are presented for the unbounded and bounded-hop broadcast problems for the linear radio network, where radio stations are placed on a straight line. For the unbounded case of the problem, the proposed algorithm runs in O(n²) time and using O(n) space, where n is the number of radio stations in the network. For the h-hop broadcast problem, the time and space complexities of our algorithm are O(hn²logn) and O(hn), respectively. This improves time complexity of the existing results for the same two problems by a factor of n and , respectively [C. Ambuhl, A.E.F. Clementi, M.D. Ianni, G. Rossi, A. Monti, R. Silvestri, The range assignment problem in non-homogeneous static ad hoc networks, in: Proc. 18th Int. Parallel and Distributed Precessing Symposium, 2004].     

一种基于局部连通性的增强型车载网多跳广播协议

在车载网中,许多应用都依赖于可靠高效的消息广播。由于无线信道共享介质的特性,消息广播不得不面临广播风暴问题。概率广播是一类能抑制广播风暴的简单有效的方法,然而车载网中除DV-CAST以外的概率广播协议均未考虑稀疏节点场景下的网络分割问题。在分析和验证DV-CAST协议固有缺点的基础上,借鉴其利用局部连通性进行转发决策的思想,提出了一种基于局部连通性的增强型多跳广播协议。实验表明,提出的协议能在稠密节点及稀疏节点场景中均取得较好的可靠性并具有较低开销。     

Ad hoc网络MAC协议的关键问题研究

Ad hoc网络综合了分组交换网和无线通信网两者的优点，是一种极有前途的无玑通信组网技术。在Ad hoc网络中，设计一个合适的MAC协议不仅可以确保在发生分组冲突时在移动台之间成功地交换信息，而且还可以提高系统吞吐量、减小分组传输时延。本文讨论了影响Ad hoc网络MAC协议性能的一些关键因素及其解决方案，并给出了对MAC技术进行建模分析时常用的一些基本假设和方法。     

动态源路由协议(DSR)在Linux下的实现

动态源路由协议(DynamicSourceRoutingProtocol,DSR)是由移动节点组成的多跳无线AdHoc网络犤3,4犦中一种简单和行之有效的路由协议犤1犦。协议允许任一结点动态发现到达AdHoc网络中其它任意节点的路由,所有的路由信息由DSR自动地进行维护。每个DSR头部都携带了到达目的节点的完整的路由跃点列表(hoplist),中间节点只需简单地对分组进行转发即可。同时DSR协议完全按需(on-demand)的特性可以显著减少路由协议的开销,节省了电池能量,减少了分组冲突的概率并减少了潜在的大规模的路径更新信息的传播。使用DSR协议可以实现AdHoc网络的完全的自组织和自配置而无需任何已经存在的网络基础设施。论文详细论述了DSR路由协议在Linux操作系统下借助Netfilter的实现。     

Multicast communication in multicomputer networks

Efficient routing of messages is a key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. While multicast communication is highly demanded in many applications, most of the existing multicomputers do not directly support this service; rather it is indirectly supported by multiple one-to-one or broadcast communications, which result in more network traffic and a waste of system resources. The authors study routing evaluation criteria for multicast communication under different switching technologies. Multicast communication in multicomputers is formulated as a graph theoretical problem. Depending on the evaluation criteria and switching technologies, they study three optimal multicast communication problems, which are equivalent to the finding of the following three subgraphs: optimal multicast path, optimal multicast cycle, and minimal Steiner tree, where the interconnection of a multicomputer defines a host graph. They show that all these optimization problems are NP-complete for the popular 2D-mesh and hypercube host graphs. Heuristic multicast algorithms for these routing problems are proposed     

A novel adaptive protocol for lightweight efficient multicasting in ad hoc networks

In group communications, we find that current multicast protocols are far from “one size fits all”: they are typically geared towards and optimized for particular scenarios. As a result, when deployed in different scenarios, their performance and overhead often degrades significantly. A common problem is that most of these protocols incur high overheads with a high density of group members and in high mobility. Our objective is to design a protocol that adapts in response to the dynamics of the network. In particular, our objective is to provide efficient and lightweight multicast data dissemination irrespective of the density of group members and node density. Our work is motivated by two observations. First, broadcasting in some cases is more efficient than multicasting. Second, member and node layout distributions are not necessarily homogeneous. For example, many MANET applications result in a topological clustering of group members that move together. Thus, we develop Fireworks, an adaptive approach for group communications in mobile ad hoc networks. Fireworks is a hybrid 2-tier multicast/broadcast protocol that adapts to maintain performance given the dynamics of the network topology and group density. In a nutshell, our protocol creates pockets of broadcast distribution in areas with many members, while it develops a multicast backbone to interconnect these dense pockets. Fireworks offers packet delivery statistics comparable to that of a pure multicast scheme but with significantly lower overheads.     

WSN中能支持广播优化的多项式广播认证机制*

针对无线传感器网络中已有的广播认证机制难以支持广播优化、存在延迟等不足,基于虚拟骨干网的思想,构建一个动态阶梯型网络,采用多项式技术,提出了一种能够识别转发节点身份的广播认证机制及其改进方案.该机制计算简单、认证延迟低,而且能够容忍大量的俘获节点;与已有广播认证机制相比,该机制能够支持层次广播优化策略,更适用于大规模网...     

An energy-efficient permutation routing protocol for single-hop radio networks

A radio network (RN) is a distributed system where each station or node is a small hand-held commodity device called a station. Typically, each station has access to a few channels for transmitting and receiving messages. By RN(p, k), we denote a radio network with p stations, where each station has access to k channels. In a single-hop RN, every station is within the transmission range of every other station. Each station consumes power while transmitting or receiving a message, even when it receives a message that is not destined for it. It is extremely important that the stations consume power only when it is necessary since it is not possible to recharge batteries when the stations are on a mission. We are interested in designing an energy-efficient protocol for permutation routing, which is one of the most fundamental problems in any distributed system. An instance of the permutation routing problem involves p stations of an RN, each storing n/p items. Each item has a unique destination address which is the identity of the destination station to which the item should be sent. The goal is to route all the items to their destinations while consuming as little energy as possible. We show that the permutation routing problem of n packets on an RN(p, k) can be solved in 2n/k+(p/k)/sup 2/+p+2k/sup 2/ slots and each station needs to be awake for at most 6n/p+2p/k+8k slots. When k/spl Lt/p/spl Lt/n, our protocol is more efficient, both in terms of total number of slots and the number of slots each station is awake compared to a previously published protocol by Nakano et al. (2001).     

An adaptive and opportunistic broadcast protocol for vehicular ad hoc networks

A primary goal of broadcasting in vehicular ad hoc network (VANET) is to improve the road safety by transmitting alert messages to all surrounding vehicles as soon as possible. In this paper, we adopt the concept of opportunistic routing and propose a multiple candidate relays opportunistic broadcast (MCROB) protocol for VANET. The MCROB protocol is a sender-driven broadcast scheme independent of node density. The packet delivery ratio (PDR) is derived and an expected transmission speed (ETS) for the MCROB is proposed. A priority rule for selecting a proper candidate relay and an adaptive algorithm for forwarding timers of candidate relays are also presented in this paper. Simulations show that MCROB is adaptive to the rapid changing of network conditions. It keeps a low communication overhead introduced by the broadcast and increases the average transmission speed by around 40%.