Secure Multi-Party Computation without Agreement

It has recently been shown that authenticated Byzantine agreement, in which more than a third of the parties are corrupted, cannot be securely realized under concurrent or parallel (stateless) composition. This result puts into question any usage of authenticated Byzantine agreement in a setting where many executions take place. In particular, this is true for the whole body of work of secure multi-party protocols in the case that a third or more of the parties are corrupted. This is because these protocols strongly rely on the extensive use of a broadcast channel, which is in turn realized using authenticated Byzantine agreement. We remark that it was accepted folklore that the use of a broadcast channel (or authenticated Byzantine agreement) is actually essential for achieving meaningful secure multi-party computation whenever a third or more of the parties are corrupted. In this paper we show that this folklore is false. We present a mild relaxation of the definition of secure computation allowing abort. Our new definition captures all the central security issues of secure computation, including privacy, correctness and independence of inputs. However, the novelty of the definition is in decoupling the issue of agreement from these issues. We then show that this relaxation suffices for achieving secure computation in a point-to-point network. That is, we show that secure multi-party computation for this definition can be achieved for any number of corrupted parties and without a broadcast channel (or trusted pre-processing phase as required for running authenticated Byzantine agreement). Furthermore, this is achieved by just replacing the broadcast channel in known protocols with a very simple and efficient echo-broadcast protocol. An important corollary of our result is the ability to obtain multi-party protocols that remain secure under composition, without assuming a broadcast channel.     

Location aided probabilistic broadcast algorithm for mobile Ad-hoc network routing

On-demand routing protocols are widely used in mobile Ad-hoc network (MANET). Flooding is an important dissemination scheme in routing discovering of on-demand routing protocol. However, in high-density MANET redundancy flooding packets lead to dramatic deterioration of the performance which calls broadcast storm problem (BSP). A location-aided probabilistic broadcast (LAPB) algorithm for routing in MANET is proposed to reduce the number of routing packets produced by flooding in this paper. In order to reduce the redundancy packets, only nodes in a specific area have the probability, computed by location information and neighbor knowledge, to propagate the routing packets. Simulation results demonstrate that the LAPB algorithm can reduce the packets and discovery delay (DD) in the routing discovery phase.     

一种新的三维FANETs跨层自适应广播协议

针对盲目广播带来的广播风暴问题,该文提出一种新的3维FANETs自适应广播协议NABP。NABP应用跨层设计的方法,在维持原有协议层间结构分离的基础上,允许路由层共享MAC层的接收信号强度信息,并根据转发分组时增加通信范围计算出转发概率,倾向于让增加通信范围大的节点以高概率转发分组,从而减少了分组在网络中的重复传输,降低了节点间的竞争和碰撞,提高广播效率。NS-2仿真结果表明：与flooding + 802.11和fp-flooding+802.11协议相比,NABP提高了转播节省率、减少了平均端对端延迟和平均丢包率。     

An adaptive transmission-scheduling protocol for mobile ad hoc networks

Transmission-scheduling protocols can support contention-free link-level broadcast transmissions and delay sensitive traffic in mobile, multiple-hop packet radio networks. Use of transmission-scheduling protocols, however, can be very inefficient in mobile environments due to the difficulty in adapting transmission schedules. The paper defines a new adaptive and distributed protocol that permits a terminal to adapt transmission assignments to changes in topology using information it collects from its local neighborhood only. Because global coordination among all the terminals is not required and changes to transmission assignments are distributed to nearby terminals only, the protocol can adapt quickly to changes in the network connectivity. The two key parameters that affect the ability of the protocol to adapt to changes in connectivity are the rate of connectivity changes and the number of terminals near the connectivity changes. Using simulation, we determine the ranges for these parameters for which our adaptive protocol can maintain collision-free schedules with an acceptable level of overhead. The stability of the protocol is also characterized by showing that the protocol can quickly return to a collision-free transmission schedule after a period of very rapid changes in connectivity. Our channel-access protocol does not require a contention-based random-access phase to adapt the transmission schedules, and thus its ability to adapt quickly does not deteriorate with an increase in the traffic load.     

Regional Gossip Routing for Wireless Ad Hoc Networks

Many routing protocols have been proposed for wireless ad hoc networks, and most of them are based on some variants of flooding. Thus many routing messages are propagated through the network unnecessarily despite various optimizations. Gossip based routing method has been used and re-investigated to reduce the number of messages in both wired networks and wireless ad hoc networks. However, the global gossiping still generates many unnecessary messages in the area that could be far away from the line between sender node and receiver node. We propose a regional gossip approach, where only the nodes within some region forward a message with some probability, to reduce the overhead of the route discovery in the network. We show how to set the forwarding probability based on the region and the network density both by theoretical analysis and by extensive simulations. Our simulations show that the number of messages generated using this approach is much less than the simple global gossiping method, which already saves many messages compared with global flooding. We expect that the improvement should be even more significant in larger networks.     

A Cross-Layer Routing Scheme Using Adaptive Retransmission Strategy for Wireless Mesh Networks

In this paper, we develop a link quality-based adaptive adjustment mechanism of the MAC maximum retransmission count to reduce collision probability of wireless Mesh networks. Based on statistics acquired in the link layer and the retransmission strategy, a multi-metric cross-layer on-demand routing scheme is proposed for wireless Mesh networks. The proposed scheme uses information such as available link bandwidth, node residual load rate and transmission efficiency of a path adequately to cross-layer routing. The network layer can adaptively select an optimal path to deliver packets based on the acquired statistics of the MAC layer. Extensive simulation results demonstrate that the proposed scheme can reduce link failure probability, improve network throughput, and decrease the end-to-end delay effectively.     

Border Node Retransmission Based Probabilistic Broadcast Protocols in Ad-Hoc Networks

We propose some improvements to the flooding protocols that aim to efficiently broadcast given information in ad-hoc networks. These improvements are based on probabilistic approach and decrease the number of emitted packets. Indeed, it is more interesting to privilege the retransmission by nodes that are located at the radio border of the sender. We observe that the distance between two nodes can be approximated by comparing neighbor lists. This leads to broadcasting schemes that do not require position or signal strength information. Moreover, proposed broadcast protocols require only knowledge of one hop neighborhood and thus need only short hello message and then support high mobility.     

Predictive models to rebroadcast in mobile ad hoc networks

Network wide broadcast is a fundamental operation in mobile ad hoc networks (MANETs). Several broadcast protocols have been proposed in the literature that improves on simple flooding by reducing the probability that a receiving node retransmits a packet. We propose analytical models to estimate these probabilities for three broadcast protocols. Our simulations show that these analytical models, which were derived under some simplifying assumptions, predict retransmission probabilities for static and mobile networks quite accurately when only the network layer is considered.     

Erasure coding for reliable adaptive retransmission in wireless broadcast/multicast systems

In this paper, we present new adaptive automatic repeat request (ARQ) schemes for wireless broadcast/multicast combining erasure coding (EC) and packet retransmission. Traditional approaches rely on retransmitting the lost packets in a point-to-point or point-to-multipoint mode. The main idea behind the presented protocols is to retransmit adaptive combinations of the lost packets using EC, which can help several receivers to recover the lost information with fewer retransmission attempts. We propose two versions of EC-based ARQ protocols, and investigate theoretically the corresponding transmission bandwidths in different contexts. We show through simulation results the efficiency of the proposed protocols with respect to conventional ARQ strategies and new published ARQ works for broadcast/multicast. Finally, a new sliding window NACK feedback policy is presented for the case of a high number of receivers to avoid the feedback implosion problem.     

Network coding and competitive approach for gradient based routing in wireless sensor networks

Energy efficiency is a key design criterion for routing protocols in wireless sensor networks since sensor nodes are strongly constrained in terms of energy supply. Gradient-Based Routing (GBR) is a well known energy efficient routing protocol that is used in WSNs. However, there exist shortcomings in the GBR scheme such as: (1) sinks make use of flooding to broadcast interest messages which leads to a lot of duplication packets which are transmitted. This leads to the waste of a lot of energy in the network and (2) nodes deliver messages in a point to point manner. As a result, the potential of data retransmissions in the network is high due to the unstable network environment in WSNs. In this study, network coding and a competitive approach are proposed to solve the above two problems. Firstly, an energy efficient broadcast algorithm using network coding for GBR (GBR-NC) is proposed. This algorithm aims to reduce network traffic, and furthermore, reduce the energy consumption and prolong the lifetime of the network. Secondly, two competing algorithms (GBR-C and auto-adaptable GBR-C) are proposed for GBR. The basic idea of the proposed competing algorithms is to reduce the retransmission attempts and save the energy by considering two forward candidates. Simulation results show that the proposed schemes give better results when compared to the traditional GBR in terms of energy efficiency.     

一种环境感知的无线Mesh网络自适应QoS路径选择算法

本文针对如何改善无线多跳Mesh网络的服务质量,满足无线多媒体业务对数据传输的带宽、时延、抖动的要求等问题,研究了一种基于无线信道状态和链路质量统计的MAC层最大重传次数的自适应调整算法。该算法通过对无线Mesh网络的无线信道环境的动态感知,利用分层判断法区分无线分组丢失的主要原因是无线差错还是网络拥塞导致,实时调整MAC层的最佳重传次数,降低无线网络中的分组冲突概率。基于链路状态信息的统计和最大重传策略,提出了一种启发式的基于环境感知的QoS路由优化机制HEAOR。该算法通过动态感知底层链路状态信息,利用灰色关联分析法自适应选择最优路径,在不增加系统复杂度的基础上,减少链路误判概率,提高传输效率。NS2仿真结果表明,HEAOR算法能有效减少重路由次数,降低链路失效概率,提高网络的平均吞吐率。本文提出的方法不仅能够优化MAC层的重传,而且通过发现跨层设计的优化参数实现对路径的优化选择。      

Gossip-based ad hoc routing

Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations of flooding, many routing messages are propagated unnecessarily. We propose a gossiping-based approach, where each node forwards a message with some probability, to reduce the overhead of the routing protocols. Gossiping exhibits bimodal behavior in sufficiently large networks: in some executions, the gossip dies out quickly and hardly any node gets the message; in the remaining executions, a substantial fraction of the nodes gets the message. The fraction of executions in which most nodes get the message depends on the gossiping probability and the topology of the network. In the networks we have considered, using gossiping probability between 0.6 and 0.8 suffices to ensure that almost every node gets the message in almost every execution. For large networks, this simple gossiping protocol uses up to 35% fewer messages than flooding, with improved performance. Gossiping can also be combined with various optimizations of flooding to yield further benefits. Simulations show that adding gossiping to AODV results in significant performance improvement, even in networks as small as 150 nodes. Our results suggest that the improvement should be even more significant in larger networks.     

ad hoc网络中一种基于信任模型的机会路由算法

由于ad hoc网络具有缺乏足够的物理保护、拓扑结构动态变化、采用分布式协作、节点的带宽和计算能力有限等特点,导致传统的路由安全机制不再适合ad hoc网络路由协议的设计。最近当前研究热点之一的机会路由能够在链路不可靠的情况下充分利用无线广播和空间多样性的特性提高网络的吞吐量。因此,考虑在机会路由中引入信任相似性概念设计信任机会路由,建立了基于节点信任度和最小成本的信任机会转发模型,提出了最小成本的机会路由算法MCOR,并对算法进行了理论上的分析和证明。最后采用仿真实验对该算法进行验证,又与经典机会路由协议ExOR以及其他经典的信任路由协议TAODV和Watchdog-DSR进行性能对比。仿真结果表明,MCOR算法能够防范恶意节点的攻击,在吞吐量、端到端时延、期望转发次数(ETX)和成本开销等方面都比其他3种协议表现出性能上的优势。     

反馈信道下基于LT码的空间网络广播传输策略设计

由于其特有的广域宽覆盖等特点,数据广播业务一直是空间网络的主要业务。然而空地间信道由于受到远距离、天气变化及遮挡等因素影响,数据传输时延长且丢包率较高。为进一步提高数据广播的性能,该文将反馈信息与LT码相结合,提出一种新的空间网络数据广播传输策略。与传统的数据广播策略相比较,新的传输策略利用反馈信息估计信道丢包率,并在此基础上引入信道状态矩阵和数据包选择权重向量,设计了数字喷泉新的编码方法,进而使得数据在重传阶段能够根据信道状态和重传概率实时调整。仿真结果表明,新的数据广播策略能够实现传输较少数据包的基础上实现原始数据的可靠接收。     

Broadcasting in Sensor Networks: The Role of Local Information

Flooding based querying and broadcasting schemes have low hop-delays of $Theta {( {{ 1}over { R(n)}})}$ to reach any node that is a unit distance away, where $R(n)$ is the transmission range of any sensor node. However, in sensor networks with large radio ranges, flooding based broadcasting schemes cause many redundant transmissions leading to a broadcast storm problem. In this paper, we study the role of geographic information and state information (i.e., memory of previous messages or transmissions) in reducing the redundant transmissions in the network.      

城市环境VANETS下的基于beacon控制的路由方案

车载网络(Vehicular ad hoc networks,VANETs)是一种特殊形式的网络,具有节点高速移动、拓扑频繁的变化的特性。这些特性为消息的传播带来挑战。路由机制是实现消息传递的关键因素。地理位置路由被广泛地应用于VANETS,要求节点周期广播beacon消息。然而,节点周期地广播beacon消息,降低了路由性能,特别是在城市区域,由于节点密集,每个节点均广播beacon消息,恶化了路由性能。为此,针对城市环境,提出基于beacon控制的路由协议RPBC(Routing protocol with beacon control)。在RPBC中,并非每个节点广播beacon消息,而设置有效的机制选择部分节点广播,从而降低了beacon冗余,同时,采用最短路径算法,减少数据传输跳数。仿真结果表明,提出的RBPC在分组投递率、端到端传输时延以及路由开销方面均有较好的性能。     

Secure group communication in wireless mesh networks

Wireless mesh networks (WMNs) have emerged as a promising technology that offers low-cost community wireless services. The community-oriented nature of WMNs facilitates group applications, such as webcast, distance learning, online gaming, video conferencing, and multimedia broadcasting. Security is critical for the deployment of these services. Previous work focused primarily on MAC and routing protocol security, while application-level security has received relatively little attention. In this paper we focus on providing data confidentiality for group communication in WMNs. Compared to other network environments, WMNs present new challenges and opportunities in designing such protocols. We propose a new protocol framework, Secure Group Overlay Multicast (SeGrOM), that employs decentralized group membership, promotes localized communication, and leverages the wireless broadcast nature to achieve efficient and secure group communication. We analyze the performance and discuss the security properties of our protocols. We demonstrate through simulations that our protocols provide good performance and incur a significantly smaller overhead than a baseline centralized protocol optimized for WMNs.     

Byzantine Agreement Given Partial Broadcast

This paper considers unconditionally secure protocols for reliable broadcast among a set of n players, where up to t of the players can be corrupted by a (Byzantine) adversary but the remaining h = n - t players remain honest. In the standard model with a complete, synchronous network of bilateral authenticated communication channels among the players, broadcast is achievable if and only if 2n/h < 3. We show that, by extending this model by the existence of partial broadcast channels among subsets of b players, global broadcast can be achieved if and only if the number h of honest players satisfies 2n/h < b + 1. Achievability is demonstrated by protocols with communication and computation complexities polynomial in the size of the network, i.e., in the number of partial broadcast channels. A respective characterization for the related consensus problem is also given.     

Secure routing in wireless sensor networks: attacks and countermeasures

We consider routing security in wireless sensor networks. Many sensor network routing protocols have been proposed, but none of them have been designed with security as a goal. We propose security goals for routing in sensor networks, show how attacks against ad-hoc and peer-to-peer networks can be adapted into powerful attacks against sensor networks, introduce two classes of novel attacks against sensor networks––sinkholes and HELLO floods, and analyze the security of all the major sensor network routing protocols. We describe crippling attacks against all of them and suggest countermeasures and design considerations. This is the first such analysis of secure routing in sensor networks.     

Performance Analysis of Adjusted Probabilistic Broadcasting in Mobile Ad Hoc Networks

Broadcasting in Mobile Ad Hoc Networks (MANETs) is a fundamental data dissemination mechanism with a number of important applications in, e.g., route discovery, address resolution. However, broadcasting induces what is known as the “broadcast storm problem” which causes severe degradation in network performance due to excessive redundant retransmission, collision, and contention. Broadcasting in MANETs has traditionally been based on flooding, which simply swamps the network with large number of rebroadcast messages in order to reach all network nodes. Although probabilistic flooding has been one of the earliest suggested schemes to broadcasting, there has not been so far any attempt to analyse its performance behaviour in a MANET environment. In an effort to fill this gap, this paper investigates using extensive ns-2 simulations the effects of a number of important system parameters in a typical MANET, including node speed, pause time, traffic load, and node density on the performance of probabilistic flooding. The results reveal that most of these parameters have a critical impact on the reachability and the number of saved rebroadcast messages achieved by probabilistic flooding.