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.This work was supported by the US Army Research Office under Contract No. DAAG29-84-K-0084.     

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.     

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     

Reduction of the broadcast redundancy by location awareness in mobile ad hoc networks

In this paper, a reachability-guaranteed approach for reducing broadcast storms in MANET is proposed. The approach is based on location awareness of each node, which means each node in the network needs to equip the positioning device like GPS and exchanges location information in the HELLO message with its neighbors. Three mechanisms are included in the proposed approach: Relay Set (RS), Neighbor Coverage (NC), and Transmission Order (TO). RS is a sender-based mechanism in which the sending node of the broadcast message determines the relay set of its neighbors for rebroadcast according to the radio coverage of the neighbors. The idea of the received-based NC is: a node receiving a broadcast message does not have to rebroadcast the message if all its neighbors have received the same message. TO mechanism requires a farther neighbor node away from the sending node to rebroadcast the message earlier than closer nodes so that a closer node may have more chances to save the rebroadcast. Simulation results have shown that the proposed approach ‘RS+NC+TO’ has a better performance than existing solutions like threshold-based schemes and angle-based scheme in terms of 100% reachability, more saved rebroadcast, and shorter average latency.     

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.     

短波地空网中一种动态TDMA协议设计与仿真*

针对传统TDMA网络节点间业务量不均匀时,会造成信道资源严重浪费的问题,设计了一种基于邻居时隙调动的短波地空网动态TDMA协议(TDMA protocol based on neighbour timeslot remove,NTR-TDMA),以可靠性较高的地面节点作为控制中心,实现时隙分配可控下的动态利用。提出了邻居时隙调动算法(neighbour timeslot remove algorithm,NTR-ALG),地面节点根据时隙估计过程后生成的节点时隙请求数,调动相邻业务时隙节点间的空闲时隙,重新划分节点业务时隙界限。利用OPNET平台进行性能仿真,并与HFTP协议和TDMA协议作了对比分析。仿真结果表明,NTR-TDMA相比HFTP协议和TDMA协议,在消息投递率、平均时延和吞吐量方面具有更优异的性能。     

一种基于网络分解的多播通讯路由方法

有效的消息通讯是提高分布存储器并行计算机性能的关键因素．点对点通讯和广播通讯是２种常用的消息通讯方法，而多播通讯（Ｍｕｌｔｉｃａｓｔｉｎｇ）是指从一个源节点同时给任意多个目标节点发送消息，这种通讯比点对点和广播２种方式更具一般性，适用于很多实际应用的需求．本文针对ＰＡＲ９５并行计算机的二维网格结构，提出一种基于网络分解的多播消息通讯方法，并比较了该方法与用多个点对点方法实现多播通讯的性能.     

移动传感网中基于虚拟货币的路由策略

移动无线传感器网络中,针对节点基于随机运动模型的路由问题,提出一种基于虚拟货币的低能耗路由策略——DTVC。根据节点的属性和数据消息的属性进行买方和卖方的定价并据此选择转发节点。为了提升网络性能,通过控制数据消息的副本数以及对节点的缓存队列中的数据消息排序,把网络中的节点分为源节点和中继节点,只有数据消息的源节点可以复制该数据消息,并依据数据消息的延迟容忍度对消息进行排序,延迟容忍度越小则优先级越高。为了减少网络中的能量消耗,根据sink节点广播的消息删除缓存队列中已经传输成功的数据消息。在Matlab上的仿真实验结果表明,与基于消息容错的自适应数据传输算法（FAD）、基于距离和能量感知模糊逻辑的路由算法（FLDAER）和基于能耗自选演进机制的路由算法相比,DTVC的数据消息投递率至少提高2.5%,平均副本数至少减少25%。     

一种IEEE 802.15.6 Two-Hop 拓扑扩展转发节点选择协议

IEEE 802.15.6标准提供了一种2-Hop的星形拓扑扩展结构用于节省单跳长距离通信带来的能量消耗,但该标准没有指明如何选择转发节点的机制.本文提出了一种IEEE 802.15.62-Hop的星形拓扑扩展结构转发节点选择协议ORR,通过请求转发的Relayed节点k广播包含自己的IDk、数据产生的频率FDatak和请求转发的持续时间TreqLenk的RelayNodeDiscovery消息,请求转发节点为自己转发数据;候选Relaying节点根据自己和已为转发的其他节点数据的能量消耗,在保留自己能量阈值EThreshi的情况下,单播发出响应RelayInfo消息;RelayInfo消息包含节点i自己的IDi,平均信噪比AvgSNRik和能提供转发的最长数据时间TmaxLenik;节点k根据这些参数选择最优或重新选择转发节点,提高了网络可靠性.性能分析与模拟实验表明:该协议在网络寿命和网络吞吐量方面优于传统的IEEE 802.15.6策略.     

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     

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).     

Multi-constraint multi-objective QoS aware routing heuristics for query driven sensor networks using fuzzy soft sets

In this paper, a fuzzy based distributed power aware routing scheme considering both energy and bandwidth constraints, especially for query driven applications in the asynchronous duty-cycled wireless sensor networks are devised. The proposed multi-constraint, multi-objective routing optimization approach under strict resource constraints guarantees reliability and fast data delivery along with efficient power management in spite of unreliable wireless links and limited power supply. In query driven applications, the request from the sink to the individual sensor node will be a broadcast message, whereas the individual sensor nodes replies back to sink as unicast messages. In the proposed work, the fuzzy approach and “A Star” algorithm are utilized for satisfying energy and bandwidth constraints to route the broadcast messages of the sink while querying all the sensor nodes in the network. Every node will be provided with a guidance list, which is used to decide the next best neighbor node with good route quality for forwarding the received multi-hop broadcast messages. The route quality of the every node is estimated with fuzzy rules based on the network parameters such as maximum remaining energy, minimum traffic load and better link quality to increase the network lifetime. The provision of overhearing the broadcast messages and acknowledgements within the transmission range minimizes the effort to search for the active time of nodes while routing the broadcast messages with asynchronous scheduling. Further, in the proposed work only the time slot of its nearest neighbor relay node (to which packets are to be forwarded) is learnt to reduce the number of message transmissions in the network. For the unicast message replies, the fuzzy membership function is modified and devised based on the routing metrics such as higher residual energy, minimum traffic loads and minimum hop count under energy and bandwidth constraints. Also, the multi-hop heuristic routing algorithm called Nearest Neighbor Tree is effectively used to reduce the number of neighbors in the guidance list that are elected for forwarding. This helps to increase the individual sensor node’s lifetime, thereby maximizes the network lifetime and guarantees increased network throughput. The simulation results show that the proposed technique reduces repeated transmissions, decreases the number of transmissions, shortens the active time of the sensor nodes and increases the network lifetime for query driven sensor network applications invariant to total the number of sensor nodes and sinks in the network. The proposed algorithm is tested in a small test bed of sensor network with ten nodes that monitors the room temperature.     

Efficient Broadcasting Using Network Coding and Directional Antennas in MANETs

In this paper, we consider the issue of efficient broadcasting in mobile ad hoc networks (MANETs) using network coding and directional antennas. Network coding-based broadcasting focuses on reducing the number of transmissions each forwarding node performs in the multiple source/multiple message broadcast application, where each forwarding node combines some of the received messages for transmission. With the help of network coding, the total number of transmissions can be reduced compared to broadcasting using the same forwarding nodes without coding. We exploit the usage of directional antennas to network coding-based broadcasting to further reduce energy consumption. A node equipped with directional antennas can divide the omnidirectional transmission range into several sectors and turn some of them on for transmission. In the proposed scheme using a directional antenna, forwarding nodes selected locally only need to transmit broadcast messages, original or coded, to restricted sectors. We also study two extensions. The first extension applies network coding to both dynamic and static forwarding node selection approaches. In the second extension, we design two approaches for the single source/single message issue in the network coding-based broadcast application. Performance analysis via simulations on the proposed algorithms using a custom simulator and ns2 is presented.     

快速响应的高效多值拜占庭共识方案

由于网络设备的增多和传输环境的不确定性,消息时延同样具有不确定性,异步共识协议发挥出更多优势.Miller等于2016年提出第一个异步共识协议HoneyBadgerBFT,但其在实现高吞吐量的同时传输效率依然可以再优化.针对HoneyBadgerBFT中的广播协议进行改进,减少广播过程中的消息复杂度,同时增加可选的消息...     

Ad Hoc网络位置辅助广播协议

提出了一种在位置信息辅助下的新的广播协议,称之为位置辅助广播协议（LABP）。它采用将转发节点周围的区域分成网格,再在网格的辅助下找到广播中转网关,将广播信息和广播中继网关信息一起发送给邻居节点的方法。仿真表明,该协议提供了非常好的广播性能。     

过程TPN模拟方法用于两种现场总线网络的性能比较研究

以具有过程说明的TPN为工具,对两种不同类型的Fieldbus网络性能进行了研究、分析 和比较.在轮询协议中,采用了P/C通信模型,由主节点管理轮询队列;在令牌协议中,分别 采用循环令牌和授权令牌来满足周期性和突发性通信需要,其中对网络响应时间、吞吐量和振 颤等性能进行了重点讨论,给出了它们的性能差异和响应界限.     

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

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

A total ordering multicast protocol using propagation trees

The paper discusses a multicast mechanism using propagation trees. It guarantees the total ordering (including causal ordering) of messages in multiple groups. The mechanism introduces a concept of meta-groups (a subset of a multicast group) and organizes meta-groups into propagation trees. Compared with the existing propagation tree mechanisms, this mechanism has the following advantages: 1) Greater parallelism. Messages can be sent to destinations by using broadcast networks. 2) Less message cost and less latency time. It takes less network communication to multicast a message and less time to have the message delivered to all the destinations. 3) More flexibility to dynamic membership changes and higher reliability for message propagation. It does not need to restructure propagation trees when there is a change in membership, and a site failure does not stop the message propagation to its descendants in the tree     

基于密度和距离的多跳广播转发节点选择方案

多数车联网VANET(Vehicular Ad Hoc Network)的安全应用均采用多跳广播方式分发安全消息。现已提出了许多的多跳广播转发节点选择方案,但它们以减少转发节点数为目的。为此,提出基于密度和距离的多跳广播转发节点选择方案DDBFS(Density-Distance based multi-hop Broadcast Forwarder Selection scheme),记为DDBFS。DDBFS方案主要解决两个问题：密集区域的冗余广播和稀疏区域的高的传输时延。在提出的DDBFS方案中,节点在决策是否转播接收的消息前,依据距离和网络密度设置定时器,一旦定时完毕,且在定时期间,没有其他节点转发该消息,该节点就成为下一跳转发节点。仿真结果表明,与现有的方案相比,提出的DDBFS协议在重播次数和传输时延性能得到显著提高。在密集区域,消息重播次数下降了约57%,在稀疏区域,传输时延缩短了约82%。     

Repetition-based cooperative broadcasting for vehicular ad-hoc networks

In vehicular ad hoc networks, most of critical applications involved with safety rely on reliable broadcast communications with low latency. Recently, repetition-based protocols have been proposed to meet the requirements of timeliness and reliability for broadcasting. In these protocols, a sender repeatedly retransmits the broadcast message during the lifetime of the message. However, existing protocols face serious problems such as deterioration of the signal quality caused by wireless fading. In particular, since excessive repetitions might cause network congestion and waste channel resources, reliability of broadcasting should be achieved with as small a number of repetitions as possible. In this paper, we therefore propose a novel repetition-based broadcast protocol which exploits a cooperative diversity technique (called RB-CD) making a small number of repetitions robust for wireless fading. To support this cooperative diversity, neighboring nodes transmit the same message almost simultaneously (that is, using the same repetition pattern for each other) in order to form a virtual antenna array. The virtual antenna array achieves a diversity gain at the receivers. In the RB-CD protocol, the virtual antenna array consists of the source and some of its neighbors (called relays) which participate in repeating the transmission of a broadcast message. In addition, a new distributed relay selection algorithm is introduced in the RB-CD protocol. From the ns-2 simulation results, we verified that RB-CD provides a more reliable broadcasting service due to its capability of exploiting cooperative diversity.