检索结果-内蒙古大学图书馆

Analyzing network coding (Gossip) Made Easy

JOURNAL OF THE ACM 2016年第3期63卷 26-26页

作者： Haeupler, Bernhard MIT Cambridge MA 02139 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

We introduce projection analysis-a new technique to analyze the stopping time of protocols that are based on random linear network coding (RLNC). Projection analysis drastically simplifies, extends, and strengthens previous results on RLNC gossip protocols. We analyze RLNC gossip in a general framework for network and communication models that encompasses and unifies the models used previously in this context. We show, in most settings for the first time, that the RLNC gossip converges with high probability in optimal time. Most stopping times are of the form O(k+T), where k is the number of messages to be distributed and T is the time it takes to disseminate one message. This means RLNC gossip achieves "perfect pipelining." Our analysis directly extends to highly dynamic networks in which the topology can change completely at any time. This remains true, even if the network dynamics are controlled by a fully adaptive adversary that knows the complete network state. Virtually nothing besides simple O(kT) sequential flooding protocols was previously known for such a setting. While RLNC gossip works in this wide variety of networks our analysis remains the same and extremely simple. This contrasts with more complex proofs that were put forward to give less strong results for various special cases.

关键词： Algorithms Performance Reliability Theory random linear network coding dynamic networks gossip multicast

来源：评论

学校读者我要写书评

暂无评论

An Improved Stochastic Modeling of Opportunistic Routing in Vehicular CPS

引用

IEEE TRANSACTIONS ON COMPUTERS 2015年第7期64卷 1819-1829页

作者： Zeng, Deze Guo, Song Barnawi, Ahmed Yu, Shui Stojmenovic, Ivan China Univ Geosci Sch Comp Sci Wuhan 430074 Peoples R China Univ Aizu Sch Comp Sci & Engn Fukushima Japan King Abdulaziz Univ Fac Comp & IT Jeddah 21413 Saudi Arabia Deakin Univ Sch Informat Technol Geelong Vic 3217 Australia Deakin Univ SIT Melbourne Vic Australia King Abdulaziz Univ Jeddah 21413 Saudi Arabia Univ Ottawa SEECS Ottawa ON K1N 6N5 Canada

Vehicular Cyber-Physical System (VCPS) provides CPS services via exploring the sensing, computing and communication capabilities on vehicles. VCPS is deeply influenced by the performance of the underlying vehicular network with intermittent connections, which make existing routing solutions hardly to be applied directly. Epidemic routing, especially the one using random linear network coding, has been studied and proved as an efficient way in the consideration of delivery performance. Much pioneering work has tried to figure out how epidemic routing using network coding (ERNC) performs in VCPS, either by simulation or by analysis. However, none of them has been able to expose the potential of ERNC accurately. In this paper, we present a stochastic analytical framework to study the performance of ERNC in VCPS with intermittent connections. By novelly modeling ERNC in VCPS using a token-bucket model, our framework can provide a much more accurate results than any existing work on the unicast delivery performance analysis of ERNC in VCPS. The correctness of our analytical results has also been confirmed by our extensive simulations.

关键词： Vehicular cyber-physical system epidemic routing random linear network coding stochastic analysis

来源：评论

学校读者我要写书评

暂无评论

randomized broadcast in radio networks with collision detection

引用

DISTRIBUTED COMPUTING 2015年第6期28卷 407-422页

作者： Ghaffari, Mohsen Haeupler, Bernhard Khabbazian, Majid MIT Cambridge MA 02139 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA Univ Alberta Edmonton AB Canada

We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in rounds, with high probability. This time complexity is most interesting because of its optimal additive dependence on the network diameter . It improves over the currently best known algorithms, due to Czumaj and Rytter (Broadcasting algorithms in radio networks with unknown topology. In: Proceedings of the symposium on foundations of computer science, pp 492-501, 2003), and Kowalski and Pelc (Broadcasting in undirected ad hoc radio networks. In: Proceedings of the ACM SIGACT-SIGOPS symposium on principles of distributed computing, pp 73-82, 2003). These algorithms where designed for the model without collision detection and are optimal in that model. However, as explicitly stated by Peleg in his 2007 survey on broadcast in radio networks, it had remained an open question whether the bound can be improved with collision detection. We also study distributed algorithms for broadcasting messages from a single source to all nodes. This problem is a natural and important generalization of the single-message broadcast problem, but is in fact considerably more challenging and less understood. We show the following results: If the network topology is known to all nodes, then a -message broadcast can be performed in rounds, with high probability. If the topology is not known, but collision detection is available, then a -message broadcast can be performed in rounds, with high probability. The first bound is optimal and the second is optimal modulo the additive term.

关键词： Wireless networks Radio networks Broadcast Collision detection random linear network coding

来源：评论

学校读者我要写书评

暂无评论

Expander chunked codes

引用

EURASIP JOURNAL ON ADVANCES IN SIGNAL PROCESSING 2015年第1期2015卷 1页

作者： Tang, Bin Yang, Shenghao Ye, Baoliu Yin, Yitong Lu, Sanglu Nanjing Univ Natl Key Lab Novel Software Technol Nanjing 210008 Jiangsu Peoples R China Chinese Univ Hong Kong Sch Sci & Engn Shenzhen Peoples R China

Chunked codes are efficient random linear network coding (RLNC) schemes with low computational cost, where the input packets are encoded into small chunks (i.e., subsets of the coded packets). During the network transmission, RLNC is performed within each chunk. In this paper, we first introduce a simple transfer matrix model to characterize the transmission of chunks and derive some basic properties of the model to facilitate the performance analysis. We then focus on the design of overlapped chunked codes, a class of chunked codes whose chunks are non-disjoint subsets of input packets, which are of special interest since they can be encoded with negligible computational cost and in a causal fashion. We propose expander chunked (EC) codes, the first class of overlapped chunked codes that have an analyzable performance, where the construction of the chunks makes use of regular graphs. Numerical and simulation results show that in some practical settings, EC codes can achieve rates within 91 to 97 % of the optimum and outperform the state-of-the-art overlapped chunked codes significantly.

关键词： random linear network coding Chunked codes Iterative decoding random regular graph

来源：评论

学校读者我要写书评

暂无评论

An Efficient Polynomial Time Algorithm for Robust Multicast network Code Construction

引用

IEEE COMMUNICATIONS LETTERS 2015年第2期19卷 143-146页

作者： Li, Fang Guo, Wangmei Xidian Univ State Key Lab Integrated Serv Networks ISN Xian 710071 Peoples R China

For a single source multicast network with failed edges, a robust network code is given to achieve the network capacity by coding only at a subset of edges. Our algorithm provides shaper bounds on the required field size when failure patterns are given. The more required coding edges involved in the linear coding operation, the more computation it takes. The number of required coding edges is minimal in minimal multicast networks employing our algorithm.

关键词： network coding random linear network coding efficient algorithm failure probability complexity

来源：评论

学校读者我要写书评

暂无评论

RLNC-Aided Cooperative Compressed Sensing for Energy Efficient Vital Signal Telemonitoring

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2015年第7期14卷 3685-3699页

作者： Lalos, Aris S. Antonopoulos, Angelos Kartsakli, Elli Di Renzo, Marco Tennina, Stefano Alonso, Luis Verikoukis, Christos Tech Univ Catalonia UPC Dept Signal Theory & Commun TSC Barcelona 08034 Spain CTTC Castelldefels 08860 Spain Univ Paris 11 Paris Saclay Univ Lab Signals & Syst CentraleSupelecCNRSUMR 8506 F-91192 Gif Sur Yvette France WEST Aquila Srl I-67100 Laquila Italy

Wireless body area networks (WBANs) are composed of sensors that either monitor and transmit vital signals or act as relays that forward the received data to a body node coordinator (BNC). In this paper, we introduce an energy efficient vital signal telemonitoring scheme, which exploits compressed sensing (CS) for low-complexity signal compression/reconstruction and distributed cooperation for reliable data transmission to the BNC. More specifically, we introduce a cooperative compressed sensing (CCS) approach, which increases the energy efficiency of WBANs by exploiting the benefits of random linear network coding (RLNC). We study the energy efficiency of RLNC and compare it with the store-and-forward (FW) protocol. Our mathematical analysis shows that the gain introduced by RLNC increases as the link failure rate increases, especially in practical scenarios with a limited number of relays. Furthermore, we propose a reconstruction algorithm that further enhances the benefits of RLNC by exploiting key characteristics of vital signals. With the aid of electrocardiographic (ECG) and electroencephalographic (EEG) data available in medical databases, extensive simulation results are illustrated, which validate our theoretical findings and show that the proposed recovery algorithm increases the energy efficiency of the body sensor nodes by 40% compared to conventional CS-based reconstruction methods.

关键词： random linear network coding compressed sensing WBANs cooperative communications

来源：评论

学校读者我要写书评

暂无评论

Wormhole Attack Detection Algorithms in Wireless network coding Systems

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2015年第3期14卷 660-674页

作者： Ji, Shiyu Chen, Tingting Zhong, Sheng Oklahoma State Univ Dept Comp Sci Stillwater OK 74078 USA Nanjing Univ Nanjing Peoples R China

network coding has been shown to be an effective approach to improve the wireless system performance. However, many security issues impede its wide deployment in practice. Besides the well-studied pollution attacks, there is another severe threat, that of wormhole attacks, which undermines the performance gain of network coding. Since the underlying characteristics of network coding systems are distinctly different from traditional wireless networks, the impact of wormhole attacks and countermeasures are generally unknown. In this paper, we quantify wormholes' devastating harmful impact on network coding system performance through experiments. We first propose a centralized algorithm to detect wormholes and show its correctness rigorously. For the distributed wireless network, we propose DAWN, a Distributed detection Algorithm against Wormhole in wireless network coding systems, by exploring the change of the flow directions of the innovative packets caused by wormholes. We rigorously prove that DAWN guarantees a good lower bound of successful detection rate. We perform analysis on the resistance of DAWN against collusion attacks. We find that the robustness depends on the node density in the network, and prove a necessary condition to achieve collusion-resistance. DAWN does not rely on any location information, global synchronization assumptions or special hardware/middleware. It is only based on the local information that can be obtained from regular network coding protocols, and thus the overhead of our algorithms is tolerable. Extensive experimental results have verified the effectiveness and the efficiency of DAWN.

关键词： Wireless networks random linear network coding wormhole attack expected transmission count

来源：评论

学校读者我要写书评

暂无评论

R²NC: robust inter-session network coding in lossy wireless networks

引用

IET COMMUNICATIONS 2015年第2期9卷 184-195页

作者： Hai, Long Wang, Hongyu Liu, Yong Wang, Jie Tang, Zhenzhou Dalian Univ Technol EE Dalian 116024 Peoples R China

The robustness of inter-session network coding is still an open issue in lossy wireless networks. The traditional XOR based network coding cannot work well if the overhearing is unperfect. Especially, the coding node cannot know the overheard information in time. In this paper, we consider a robust network coding method, namely (RNC)-N-2 which uses random linear network coding to encode packets together in the inter-session level, to resist the unperfect overhearing problem. With this method, coding node can always know the solvability of coded packets without the knowledge of overheard information. We analyse the performance of (RNC)-N-2 method with both lossy links of output and overhearing in the classic X-topology model, and give a necessary condition for the existence of coding gain. Finally, we design an optimal coding algorithm and a relay selection algorithm for (RNC)-N-2 to achieve its maximal transmission efficiency. Through ns-2 simulations, we demonstrate that (RNC)-N-2 plays a good performance in terms of throughput, delay and overhead, and is robust against losses on output and overhearing links.

关键词： network coding telecommunication network topology linear codes random codes relay networks (telecommunication) radio networks (RNC)-N-2 method robust intersession network coding lossy wireless networks random linear network coding packet encoding unperfect overhearing problem X-topology model coding gain relay selection algorithm maximal transmission efflciency overhearing links

来源：评论

学校读者我要写书评

暂无评论

On network coding for Funnel networks

引用

IEEE COMMUNICATIONS LETTERS 2015年第11期19卷 1897-1900页

作者： Karimian, Pourya Borujeny, Reza Rafie Ardakani, Masoud Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G 2V4 Canada

network coding for non-multicast problems has been the subject of many recent studies. In this letter, we consider networks in which the total capacity of the incoming links to each intermediate node is not less than the total capacity of its outgoing links. We call these networks funnel networks and prove that any feasible non-multicast problem on funnel networks is solvable by routing (hence, by linear network coding, too). The desirability of network coding in funnel networks may be justified by the other benefits that coding offers. However, we see that in funnel networks, the conventional random approach to linear coding fails with high probability. Hence, we provide a new random linear network coding solution for these non-multicast problems.

关键词： network information theory random linear network coding non-multicast problems

来源：评论

学校读者我要写书评

暂无评论

Decoding Failure Probability of random network coding Systems in Fading Channels 23

Decoding Failure Probability of Random Network Coding System...

引用

23nd Signal Processing and Communications Applications Conference (SIU)

作者： Khan, Rida Kurt, Gunes Karabulut Altunbas, Ibrahim Istanbul Tech Univ Dept Elect & Commun Wireless Commun Res Lab Istanbul Turkey

ISBN: (纸本)9781467373869

network coding allows a significant increase in throughput in multicast and broadcast scenarios;by letting intermediate nodes between data sources and destinations forward a coded version of incoming packets. random network coding is a type of network coding in which the coefficients used to encode the data packets are randomly extracted from a Galois field. Hence, it can be used in a network where the network topology is unknown. In a network coded system with practical wireless communication links, a decoding error at the destination may be observed due to linearly dependent coefficient vectors or due to missing packets at the intermediate relays because of fading channel characteristics. Taking these factors into account, in this paper we have analyzed the impact of Rayleigh and Rician fading channels on the performance of a random network coded systems.

关键词： random linear network coding decoding failure probability Rayleigh fading Rician fading

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：