Faster communication in known topology radio networks

This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology of the network. The first part of the paper examines the two communication primitives in arbitrary graphs. In particular, for the broadcast task we deliver two new results: a deterministic efficient algorithm for computing a radio schedule of length D + O(log³ n), and a randomized algorithm for computing a radio schedule of length D + O(log² n). These results improve on the best currently known D + O(log⁴ n) time schedule due to Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 2005). Later we propose a new (efficiently computable) deterministic schedule that uses 2D + Δlog n + O(log³ n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree Δ. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time , for any network with the diameter D = Ω(log ⁱ⁺⁴ n), where i is an arbitrary integer constant i ≥ 0, see Gąsieniec et al. (Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity, vol. 3104, pp. 173–184, 2004). The second part of the paper focuses on radio communication in planar graphs, devising a new broadcasting schedule using fewer than 3D time slots. This result improves, for small values of D, on the currently best known D + O(log³ n) time schedule proposed by Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 2005). Our new algorithm should be also seen as a separation result between planar and general graphs with small diameter due to the polylogarithmic inapproximability result for general graphs by Elkin and Kortsarz (Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, vol. 3122, pp. 105–116, 2004; J. Algorithms 52(1), 8–25, 2004). The second author is supported in part by a grant from the Israel Science Foundation and by the Royal Academy of Engineering. Part of this research was performed while this author (Q. Xin) was a PhD student at The University of Liverpool.     

Localized Techniques for Broadcasting in Wireless Sensor Networks

In this paper we tackle the problem of designing simple, localized, low energy consuming, reliable protocols for one-to-all communication in large scale wireless sensor networks. Our first proposed technique, called the Irrigator protocol, relies on the idea to first build a sparse overlay network, and then flood over it. The overlay network is set up by means of a simple, distributed, localized probabilistic protocol and spans all the sensor nodes with high probability. Based on the algorithmic ideas of the Irrigator protocol we then develop a second protocol, dubbed Fireworks, with similar performance that does not require any overlay network to be set up in advance. Asymptotic analytical results are provided which assess the reliability of the Irrigator and Fireworks techniques. The theoretical analysis of the proposed protocols is complemented and validated by a (simulation based) comparative performance evaluation that assesses several advantages of our new protocols with respect to gossiping and simple flooding. Differently from previous studies, we analyze and demonstrate the performance of our protocols for two different node distributions: The typical uniform distribution and a newly defined “hill” distribution, here introduced to capture some of the important and more realistic aspects of node deployment in heterogeneous terrain. Simulation results show that the proposed schemes achieve very good trade-offs between low overhead, low energy consumption and high reliability. In particular, the Irrigator and Fireworks protocols are more reliable than gossiping, and significantly reduce the number of links along which a message is sent over both flooding and gossiping.     

Faster Deterministic Communication in Radio Networks

We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. We show that gossiping can be completed in time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than units of time. Moreover, we show a schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log ³ n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log ² n) time broadcasting schedule by Kowalski and Pelc. A preliminary version of this paper appeared in the proceedings of ISAAC’06. F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported by the Research Council of Norway through the SPECTRUM project.     

Parallel routing algorithms for incomplete hypercube interconnection networks

Hypercube interconnection networks have been receiving considerable attention in the supercomputing environment. However, the number of processors must be exactly 2^r for an r-cube complete hypercube. This restriction severely limits its applicability. In this paper, we address three variant hypercube topologies with more flexibility in system sizes, the labelled hypercubes I_m^r, I_M^r, and I_A^r. Incomplete hypercube I_m^r consists of an r-cube and an m-cube complete hypercubes; I_m^r is composed of 2^r and Σ_{m ε M} 2^m nodes; I_Ar comes from an r-cube complete hypercube which operates in a degraded manner and allows that the missing nodes to be arbitrarily distributed. Specifically, we focus on the parallel paths routing algorithms for these three classes of incomplete hypercubes. Parallel paths between any given two nodes mean that these paths have the same source and destination nodes but with different intermediate nodes. Parallel communication is important as it will allow us to use the full bandwidth of the multiprocessors for the data transfer operation between any two nodes, and3these redundant paths can increase system fault-tolerance and communication reliability. With these parallel routing algorithms, one can use them as a criterion to design multiprocessor systems.     

Comparator networks for binary heap construction

Comparator networks for constructing binary heaps of size n are presented which have size and depth . A lower bound of for the size of any heap construction network is also proven, implying that the networks presented are within a constant factor of optimal. We give a tight relation between the leading constants in the size of selection networks and in the size of heap construction networks.     

Performance analysis of banyan-type multistage interconnection networks under nonuniform traffic pattern

Multistage Interconnection Networks(MINs) have a number of applications in the areas of computer and communications. The most widely researched structure among MIN’s is the (l)banyan type network. It has several variations such as buffered banyan, batcher-banyan, tandem banyan, recirculating banyan and banyan with contention resolution phase. Analytical performance evaluation is crucial for justifying the merit of the design in different operational conditions. While several analytical models have been proposed for the performance evaluation of MINs, they are mainly for uniform traffics. Even the models for nonuniform traffics have several shortcomings such as they only consider output buffered structure or do not consider blocking conditions. In this paper, the more accurate models than any other ones so far have been proposed for the performance evaluation of multibuffered banyan-type MIN’s under nonuniform traffic condition is obtained. The accuracy of proposed models are conformed by comparing with the results from simulation. Firstly, single buffer model is developed. Markov chain is used for the analysis. Multibuffer model is obtained from single buffer model. Simulation is performed using Discrete Evenet Simulaton(DES) method. As a results, proposed model proves to be very accurate.     

Fast deterministic broadcast and gossiping algorithms for mobile ad hoc networks

We present a mobility resilient deterministic broadcast algorithm with worst-case time complexity of O(nlogn)$O(nlogn)$ for ad hoc networks where the nodes possess collision detection capabilities; n$n$ is the total number of nodes in the network. The algorithm is based on a breadth-first traversal of the network and allows multiple simultaneous transmissions by the nodes. The idea of this broadcast algorithm is then extended to develop a mobility resilient deterministic gossiping algorithm having O(Dnlogn)$O(Dnlogn)$ worst-case run time (D$D$ is the diameter of the network graph), which is an improvement over the existing algorithms. Simulation results show that on an average, the time for completing the broadcast or gossiping is significantly lower than the theoretical worst-case time requirement.     

Optimal information dissemination in star and pancake networks

This paper presents a new decomposition technique for hierarchical Cayley graphs. This technique yields a very easy implementation of the divide and conquer paradigm for some problems on very complex architectures as the star graph or the pancake. As applications, we introduce algorithms for broadcasting and prefix-like operations that improve the best known bounds for these problems. We also give the first nontrivial optimal gossiping algorithms for these networks. In star-graphs and pancakes with N=n! processors, our algorithms take less than [log N]+1.5n steps     

Efficient techniques for time-constrained information dissemination using location-based social networks

Social networks have undergone an explosive growth in recent years. They constitute a central part of users׳ everyday lives as they are used as major tools for the spread of information, ideas and notifications among the members of the network. In this work we investigate the use of location-based social networks as a medium of emergency notification, for efficient dissemination of emergency information among members of the social network under time constraints. Our objective is the following: given a location-based social network comprising a number of mobile users, the social relationships among the users, the set of recipients, and the corresponding timeliness requirements, our goal is to select an appropriate subset of users so that the spread of information is maximized, time constraints are satisfied and costs are considered. We propose LATITuDE, our system that investigates the interactions among the members of the social network to infer their social relationships, and develop scalable dissemination mechanisms that select the most efficient set of users to initiate the dissemination process in order to maximize the information reach among the appropriate receivers within a time window. Our detailed experimental results illustrate that our approach is practical, effectively addresses the problem of informing the appropriate set of users within a deadline when an emergency event occurs, uses a small number of messages, and consistently outperforms its competitors.     

An application-level framework for information dissemination and collection in vehicular networks

Mobility of wireless network nodes is increasingly regarded as a fundamental resource for future pervasive communication systems. In this paper, we leverage the movement of communication-enabled vehicles to implement an original Application-level Role Mobility (ARM) framework. ARM allows nodes to share a generic assignment, by handing each other the associated application-level role. The handover of the role is performed according to the mobility patterns of the vehicles, following rules that are specific to the objective of the application. We employ the ARM framework for two different tasks: dissemination of information to traveling cars, and data collection from road-side sensors. For each application, we provide dedicated role handover rules and show, via simulation, that ARM can successfully perform the required operations in a lightweight, fully distributed way.     

Performance modeling and analysis of heterogeneous meta-computing systems interconnection networks

The overall performance of a distributed system often depends on the effectiveness of its interconnection network. Thus, the study of the communication networks for distributed systems is very important, which is the focus of this paper. In particular, we address the problem of interconnection networks performance modeling for heterogeneous meta-computing systems. We consider the meta-computing system as a typical multi-cluster system. Since the heterogeneity is becoming common in such systems, we take into account network as well as cluster size heterogeneity to propose the model. To this end, we present an analytical network model and validate the model through comprehensive simulation. The results of the simulation demonstrated that the proposed model exhibits a good degree of accuracy for various system organizations and under different working conditions.     

Interval routing in some planar networks

In this article, we design optimal or near optimal interval routing schemes (IRS, for short) with small compactness for several classes of plane quadrangulations and triangulations (by optimality or near optimality we mean that messages are routed via shortest or almost shortest paths). We show that the subgraphs of the rectilinear grid bounded by simple circuits allow optimal IRS with at most two circular intervals per edge (2-IRS). We extend this result to all plane quadrangulations in which all inner vertices have degrees4. Namely, we establish that every such graph has an optimal IRS with at most seven linear intervals per edge (7-LIRS). This leads to a 7-LIRS with the stretch factor 2 for all plane triangulations in which all inner vertices have degrees6. All routing schemes can be implemented in linear time.     

Study of General Icomplete Star Interconnection Networks

The star networks,which were originally proposed by Akers and Harel,have suffered from a rigorous restriction on the number of nodes.The general incomplete star networks(GISN) are proposed in this paper to relieve this restriction.An efficient labeling scheme for GISN is given,and routing and broadcasting algorithms are also presented for GIS.The communication diameter of GISN is shown to be bounded by 4n-7.The proposed single node broadcasting algorithm is optimal with respect to time complexity O(nlog2n).     

互联互通视阈下医院信息化建设路径探索

医疗服务一直都是人们所关注的热点。当前,由于人们对医疗服务提出了更高要求,所以很多医院开始将信息化技术融合到工作中,希望能有所突破。文章主要阐述了互联互通视阈下医院信息化建设现状,面临的问题和建设路径。     

互联互通视阈下医院信息化建设路径探索

医疗服务一直都是人们所关注的热点。当前,由于人们对医疗服务提出了更高要求,所以很多医院开始将信息化技术融合到工作中,希望能有所突破。文章主要阐述了互联互通视阈下医院信息化建设现状,面临的问题和建设路径。     

Compiler-directed power optimization of high-performance interconnection networks for load-balancing MPI applications

Energy consumption of parallel computers has been becoming the obstruction to higher-performance systems. In this paper, we focus on power optimization of high-performance interconnection networks for MPI applications in high-performance parallel computers. Compared with the past history-based work, we propose the idea of compiler-directed power-aware on/off network links. There are some idle intervals for network links during the execution of parallel applications, at which the links still consume large amounts of energy. Using on/off network links, compiler first divides load-balancing MPI applications into the communication intervals and the computation intervals, and then inserts the on/off instruction into the applications to switch the link state. To avoid the time overhead of state switching, we use a time estimation technique to analyze the computation time, and insert the on instruction before reaching the communication intervals. Results from simulations and experiments show that the proposed compiler-directed method can reduce energy consumption of interconnection networks by 20∼70%, at a loss of less than 1% network latency and performance degradation.     

基于网关的ZigBee网络与Internet互联框架

针对如何将ZigBee网络与Internet紧密融合的问题,提出一种网关设计方案.介绍了工作在传输层的互联网关,在分析此网关不足的基础上,根据面向服务的网络中间件思想,提议网关的体系结构.包括服务注册、服务绑定、服务调用和取消服务4个模块,以实现为用户提供服务的透明性;同时,为了减少ZigBee网络节点占用的IP地址数目,服务调用模块中使用传输层网关的协议转换方式.该网关从网络协议和服务两个角度实现ZigBee网络和Internet网络的互联,通过分析和比较证明具有用户透明性、业务提供方便等特点.     

Finding a robust configuration for the AEDB information dissemination protocol for mobile ad hoc networks

The Adaptive Enhanced Distance Based Broadcasting Protocol, AEDB hereinafter, is an advanced adaptive protocol for information dissemination in mobile ad hoc networks (MANETs). It is based on the Distance Based broadcasting protocol, and it acts differently according to local information to minimize the energy and network use, while maximizing the coverage of the broadcasting process. As most of the existing communication protocols, AEDB relies on different thresholds for adapting its behavior to the environment. We propose in this work to look for configurations that induce a stable performance of the protocol in different networks by automatically fine tuning these thresholds thanks to the use of cooperative coevolutionary multi-objective evolutionary algorithms. Finding robust solutions for this problem is important because MANETs have a highly unpredictable and dynamic topology, features that have a strong influence on the performance of the protocol. Consequently, robust solutions that show a good performance under any circumstances are required. In this work, we define different fitness functions that measure robustness of solutions for better guiding the algorithm towards more robust solutions. They are: median, constrained, worst coverage, and worst hypervolume. Results show, that the two worst-case approaches perform better, not only in case of robustness but also in terms of accuracy of the reported AEDB configurations on a large set of networks.     

Low-power high-speed interconnection networks in NOC using multi-valued current-mode techniques

With the fast developments and growth of electronic applications and a great demand for increasing the speed of processors, VLSI circuits and on-chip interconnections the ＂Networks-On-Chip＂ （NOC） is the best solution for ＂System-On-Chip＂ （SOC）. The most fundamental part of networks On-Chip is the On-Chip interconnection. The model presented in this article describes the method of sending data on On-Chip interconnection by using a current-mode multi-valued logic instead of voltage-mode in order to increase speed and reduce the number of interconnection wires.     

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.