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.     

Neighborhood tracking for mobile ad hoc networks

In mobile ad hoc networks (MANETs), node mobility causes network topologies to change dynamically over time, which complicates such important tasks as broadcasting and routing. In a typical efficient localized approach, each node makes forwarding decisions based on a neighborhood local view constructed simply by collecting received “Hello” messages. That kind of neighborhood local view can become outdated and inconsistent, which induces a low-coverage problem for efficient broadcasting tasks and a low-delivery ratio problem for efficient routing tasks. In this paper, we propose a neighborhood tracking scheme to guarantee the accuracy of forwarding decisions. Based on historical location information, nodes predict the positions of neighbors when making a forwarding decision, and then construct an updated and consistent neighborhood local view to help derive more precise forwarding decisions. The inaccuracy factors of our scheme are also discussed and an accessory method is provided for possible usage. Simulation results illustrate the accuracy of our proposed tracking scheme. To verify the effectiveness of our scheme, we apply it to existing efficient broadcast algorithms. Simulation results indicate that our neighborhood tracking scheme can improve the protocols coverage ratio greatly.     

Deterministic broadcasting in ad hoc radio networks

We consider the problem of distributed deterministic broadcasting in radio networks of unknown topology and size. The network is synchronous. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. Such messages block each other and node u either hears the noise of interference of messages, enabling it to detect a collision, or does not hear anything at all, depending on the model. We assume that nodes know neither the topology nor the size of the network, nor even their immediate neighborhood. The initial knowledge of every node is limited to its own label. Such networks are called ad hoc multi-hop networks. We study the time of deterministic broadcasting under this scenario. For the model without collision detection, we develop a linear-time broadcasting algorithm for symmetric graphs, which is optimal, and an algorithm for arbitrary n-node graphs, working in time . Next we show that broadcasting with acknowledgement is not possible in this model at all. For the model with collision detection, we develop efficient algorithms for broadcasting and for acknowledged broadcasting in strongly connected graphs. Received: January 2000 / Accepted: June 2001     

Context-aware broadcasting approaches in mobile ad hoc networks

The aim of this paper is to compare different context-aware broadcasting approaches in mobile ad hoc networks (MANETs) and to evaluate their respective performances. Message broadcasting is one of the core challenges brought up by distributed systems and has therefore largely been studied in the context of traditional network structures, such as the Internet. With the emergence of MANETs, new broadcasting algorithms especially geared at these networks have been introduced. The goal of these broadcasting algorithms is to ensure that a maximum number of nodes deliver the broadcasted message (reliability), while ensuring that the minimum number of nodes retransmit the broadcasted message (efficiency), in order to save their resources, such as bandwidth or battery. In recent years, as more and more mobile devices have become context-aware, several broadcasting algorithms have been introduced that take advantage of contextual information in order to improve their performance. We distinguish four approaches with respect to context: (1) context-oblivious approaches, (2) network traffic-aware approaches, (3) power-aware approaches, and (4) location-aware approaches. This paper precisely aims at presenting these four different broadcasting approaches and at measuring the performance of algorithms built upon them.     

Deterministic broadcasting time with partial knowledge of the network

We consider the time of deterministic broadcasting in networks whose nodes have limited knowledge of network topology. Each node v knows only the part of the network within knowledge radius r from it, i.e., it knows the graph induced by all nodes at distance at most r from v. Apart from that, each node knows the maximum degree Δ of the network. One node of the network, called the source, has a message which has to reach all other nodes. We adopt the widely studied communication model called the one-way model in which, in every round, each node can communicate with at most one neighbor, and in each pair of nodes communicating in a given round, one can only send a message while the other can only receive it. This is the weakest of all store-and-forward models for point-to-point networks, and hence our algorithms work for other models as well, in at most the same time.

We show trade-offs between knowledge radius and time of deterministic broadcasting, when the knowledge radius is small, i.e., when nodes are only aware of their close vicinity. While for knowledge radius 0, minimum broadcasting time is Θ(e), where e is the number of edges in the network, broadcasting can be usually completed faster for positive knowledge radius. Our main results concern knowledge radius 1. We develop fast broadcasting algorithms and analyze their execution time. We also prove lower bounds on broadcasting time, showing that our algorithms are close to optimal.     

Visualization Techniques via MLBS for Personnel Management in Major Events

Mobile location-based services (MLBS) refer to services around geographic location data. Mobile terminals use wireless communication networks (or satellite positioning systems) to obtain users’ geographic location coordinate information based on spatial databases and integrate with other information to provide users with required location-related services. The development of systems based on MLBS has significance and practical value. In this paper a visualization management information system for personnel in major events based on microservices, namely MEPMIS, is designed and implemented by using MLBS. The system consists of a server and a client app, and it has some functions including map search and query, personnel positioning and scheduling, location management, messaging, and location service. Managers of the events can quickly search and locate the staff on the specific area of the map in real-time, and make broadcasting messages to the staff, and manage the staff. The client app is developed on the Android system, by which staff users can send the positions information to the server timely. The client users can search fuzzily near their peers and list their locations, and also call near peers through sending messages or query the history record of staff locations. In the design of the system, several new proposed techniques, including visual annotation method for overlapping locations, correcting trajectory drift algorithm, microservices-based overall system architecture methodology and other new techniques, which are applied to the implementation of the system. Also, HTML5, JQuery, MLBS APIs (Application Program Interfaces) related programming techniques have been used and combined with loading Ajax asynchronously and Json data encapsulation, map marker optimization techniques, that can improve the positioning accuracy and the performance of the system. The developed system with practical functions can enhance the efficiencies of the organization and management of major events.     

Optimal Communication Primitives on the Generalized Hypercube Network

Efficient interprocessor communication is crucial to increasing the performance of parallel computers. In this paper, a special framework is developed on thegeneralized hypercube, a network that is currently receiving considerable attention. Using this framework as the basic tool, a number of spanning subgraphs with special properties to fit various communication needs are constructed on the network. The importance of these spanning subgraphs is demonstrated with the development of optimal algorithms for four fundamental communication problems, namely, theone-to-allandall-to-all broadcastingand theone-to-allandall-to-all scattering. Broadcastingis the distribution of the same group of messages from a source processor to all other processors, andscatteringis the distribution of distinct groups of messages from a source processor to each other processor. We consider broadcasting and scattering from a single processor of the network (one-to-all broadcasting and scattering) and simultaneously from all processors of the network (all-to-all broadcasting and scattering). For the all-to-all broadcasting and scattering algorithms, a special technique is developed on the generalized hypercube so that messages originating at individual nodes are interleaved in such a manner that no two messages contend for the same edge at any given time. The communication problems are studied under thestore-and-forward, all-portcommunication model. Lower bounds are derived for the above problems under the stated assumptions, in terms of time and number of message transmissions, and optimal algorithms are designed.     

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.     

Efficient and accurate sensor network localization

Wireless sensor networks (WSN) have great potential in ubiquitous computing. However, the severe resource constraints of WSN rule out the use of many existing networking protocols and require careful design of systems that prioritizes energy conservation over performance optimization. A key infrastructural problem in WSN is localization—the problem of determining the geographical locations of nodes. WSN typically have some nodes called seeds that know their locations using global positioning systems or other means. Non-seed nodes compute their locations by exchanging messages with nodes within their radio range. Several algorithms have been proposed for localization in different scenarios. Algorithms have been designed for networks in which each node has ranging capabilities, i.e., can estimate distances to its neighbours. Other algorithms have been proposed for networks in which no node has such capabilities. Some algorithms only work when nodes are static. Some other algorithms are designed specifically for networks in which all nodes are mobile. We propose a very general, fully distributed localization algorithm called range-based Monte Carlo boxed (RMCB) for WSN. RMCB allows nodes to be static or mobile and that can work with nodes that can perform ranging as well as with nodes that lack ranging capabilities. RMCB uses a small fraction of seeds. It makes use of the received signal strength measurements that are available from the sensor hardware. We use RMCB to investigate the question: “When does range-based localization work better than range-free localization?” We demonstrate using empirical signal strength data from sensor hardware (Texas Instruments EZ430-RF2500) and simulations that RMCB outperforms a very good range-free algorithm called weighted Monte Carlo localization (WMCL) in terms of localization error in a number of scenarios and has a similar computational complexity to WMCL. We also implement WMCL and RMCB on sensor hardware and demonstrate that it outperforms WMCL. The performance of RMCB depends critically on the quality of range estimation. We describe the limitations of our range estimation approach and provide guidelines on when range-based localization is preferable.     

基于定向广播的AODV控制报文抑制研究

AODV路由协议是通过全向广播请求报文和定时广播Hello报文来建立Ad Hoc网络的路由,但在路由发现阶段需要广播发送大量的请求控制报文,导致了协议性能的下降。针对此问题,提出了一种新的基于定向广播的路由协议,该协议通过定向广播发送请求报文,并根据节点的移动性动态调整Hello报文的发送时间间隔来减少报文的发送。理论分析和仿真结果表明,该方法能有效地减少控制报文的数量,减少路由负载,也显著提高了端到端时延、平均投递率等性能参数。     

Graph-Based Parallel Query Processing and Optimization Strategies for Object-Oriented Databases

Much work has been accomplished in the past on the subject of parallel query processing and optimization in parallel relational database systems; however, little work on the same subject has been done in parallel object-oriented database systems. Since the object-oriented view of a database and its processing are quite different from those of a relational system, it can be expected that techniques of parallel query processing and optimization for the latter can be different from the former. In this paper, we present a general framework for parallel object-oriented database systems and several implemented query processing and optimization strategies together with some performance evaluation results. In this work, multiwavefront algorithms are used in query processing to allow a higher degree of parallelism than the traditional tree-based query processing. Four optimization strategies, which are designed specifically for the multiwavefront algorithms and for the optimization of single as well as multiple queries, are introduced. The query processing algorithms and optimization strategies have been implemented on a parallel computer, nCUBE2; and the results of a performance evaluation are presented in this paper. The main emphases and the intended contributions of this paper are (1) data partitioning, query processing and optimization strategies suitable for parallel OODBMSs, (2) the implementation of the multiwavefront algorithms and optimization strategies, and (3) the performance evaluation results.     

基于区域划分的连通支配集协议

针对规模较大、节点分布密集的无线传感器网络容易产生冗余数据包以及信号冲突,导致过多的节点能量消耗,加速死亡过程等问题,在深入研究现有的分布式连通支配集构造算法的基础上,提出基于区域划分的连通支配集协议——RPMPR协议.RPMPR协议中每个节点针对网络拓扑信息,对邻居节点进行区域划分,在各区域内选择中继转发节点集,并以节点的度作为选择支配节点的依据,构建覆盖全网的连通支配集.仿真实验结果表明,RPMPR协议充分考虑网络拓扑信息,显著减小连通支配集规模,同时支配节点分布更为均匀.     

HyCube: A distributed hash table based on a variable metric

Distributed Hash Tables (DHT) proved to be scalable decentralized systems providing efficient resource location. This paper concentrates on efficiency and resilience to node failures of DHT systems and presents a novel model of a distributed hash table based on a hierarchical hypercube geometry, called HyCube. The DHT geometry, the choice of the metric defining logical distances between nodes, and the routing algorithm have fundamental influence on routing efficiency and resilience. The use of the one-dimensional model (placing the nodes logically on a ring) allows the nodes to maintain sets of references called sequential neighbors - certain numbers of neighbors that are the closest existing nodes in both directions on the ring. Such a model yields a very high level of resilience to node failures. The new approach, presented in the paper, employs a variable multi-dimensional metric adopting the Steinhaus transform. Routing, lookup and search algorithms are discussed, as well as routing table nodes selection and self-organization techniques. It is shown that the new approach allows reaching a higher level of resilience to node failures, as well as a shorter average routing path length than with the use of the sequential neighbors sets.     

Twitter analysis algorithms for Intelligence Circulation System

The convergence of broadcasting and broadband communications network technologies has attracted increasing attention as a means to enrich the television viewing experience of viewers. Toward this end, this study proposes the ‘Intelligence Circulation System (ICS)’, which provides several services, by using newly developed algorithms for analysing Twitter messages. Twitter users often post messages about on-air TV programmes. ICS obtains viewer responses from tweets without requiring any new infrastructure or changes in users’ habits or behaviours, and it generates and provides several outputs to heterogeneous devices based on the analysis results. The algorithms—designed by considering the characteristics of Twitter messages about TV programmes—use auxiliary programme information, similarity between messages, and time series of messages. An evaluation of our algorithms using Twitter messages about all programme genres for a month showed that the accuracy of topic extraction was 85 % for an emphasis on quality (with 56 % of messages processed) and 65 % for an emphasis on quantity (with 95 % of messages processed). The accuracy of message sentimental classification was 66 %. We also describe social recommendation services using the analysis result. We have created a Social TV site for a large-scale field trial, and we have analysed users’ behaviours by comparing four types of social recommendation services on it. The experimental result shows that active and passive communication users had different needs with regard to the recommendations. ICS can generate recommendations for satisfying the needs of both user types by using the analysis result of Twitter messages.     

移动传感网中基于密度和距离的概率广播算法

广播是移动传感器网络(mobile wireless sensor networks)中最基本的信息传播方式,但现有的广播算法在广播时需要大量中间转发节点,造成大量消息冗余转发,从而导致能量浪费.因此提出一种基于节点密度和距离的概率(broadcasting algorithm named node density and distance-based probability, NDDP)广播算法.该算法平均转发率为5S/(Nπr2),这里S为网络区域面积,N为网络节点总数,r为通信半径.理论分析得出该算法的平均广播接收率超过95%.ns-2模拟结果表明平均广播接收率达到92%以上,并且网络节点密度越大算法的转发率越低,越节能.模拟实验结果表明NDDP算法无论在稳定性方面还是在节能性方面均优于Smite和Sidewinder中的广播算法.     

Design considerations in the real-time implementation of multiple expert image classifiers within a modular and flexible multiple-platform design environment

A modular multiple platform design environment is proposed for the real-time implementation of image analysis systems suited to tasks such as visual inspection and other similar applications involving the analysis of two-dimensional (2D) shapes. The design strategies proposed are particularly suited to the implementation of high performance image classifiers based on the multiple expert paradigm. The unified configuration includes an integrated environment incorporating different software and hardware platforms to maximize the overall efficiency of the complete image processing or recognition task. One of the major application areas of such systems is the recognition of handwritten characters. In recent years, a new generation of handwritten recognition systems has been explored which is based on a multiple expert paradigm. The decision combination required for these configurations is a specialized data fusion process. It has been found that these multiple expert decision combination configurations can easily outperform most of the individual experts working on their own, but successful integration of decisions taken by multiple experts depends not only on the access to different individual algorithms implemented and applied independently, but also on optimized implementations of these individual algorithms. It has been demonstrated that different image processing and recognition algorithms cannot be completely optimized on a single implementation platform. On the contrary, it has been found that different processes can be implemented with maximum efficiency on different platforms. In this paper, comparative performance analysis of the same algorithms on different platforms has been carried out to select the optimum implementation platform for different algorithms in terms of complexity and execution time constraints with the aim of implementing various multiple expert decision combination configurations, and very encouraging results have been achieved. This reasoning has been further explored to build a generalized, flexible and modular design environment to facilitate the incorporation of pipelined multiple platform implementations suitable for a range of image processing, image analysis and computer vision applications.     

WSN中有效的最小单位圆集覆盖算法*

针对具有不同传输半径的无线传感器网络覆盖与广播数据转发问题,提出了一种以最小单位圆覆盖集作为广播数据转发集的算法。该算法能有效计算出覆盖范围的轮廓集,具有最优的时间复杂度O(n log n)。对每个节点,该算法以其最少数量的邻居节点子集实现所有邻居节点的覆盖,并证明了该算法找到的最小单位圆覆盖集与其轮廓集是相等的。详细的仿真实验及与现有算法的比较表明,提出的覆盖算法不仅以最少数量的节点实现了网络覆盖与广播数据转发,同时延长了网络生命期。     

基于P-范式模型的P2P网络分组查询算法

P2P系统的可用性取决于查找数据的有效方法。利用节点兴趣和节点与中心节点的通信延迟建立链接,动态分组P2P网络的节点,查询节点通过中心节点转发搜索请求给其他中心节点,中心节点收到搜索请求后,若查找资源的主题排在本组关注的前K（K一般取1～3）位,则搜索本组内所有节点。在此基础上,提出了一种基于P-范式模型的P2P网络分组查询算法。算法分析和实验结果表明该算法的性能优于MSW查询算法。     

Sparse structures for searching and broadcasting algorithms over internet graphs and peer-to-peer computing systems

In a broadcasting problem, a message is sent from a source to all the other nodes in the network. Blind flooding is a classical mechanism for broadcasting, where each node retransmits received message to all its neighbors. Despite its important advantages, an increase in the number of requests or the network size or density produces communication overheads that limit the scalability of blind flooding, especially in networks with dynamic topologies. Theoretically optimal solution is based on minimal spanning trees (MST), but its construction is expensive. We discuss here protocols based on local knowledge and newly proposed sparse structures. In weighted RNG (Relative Neighborhood Graph), messages are forwarded only on links which are not the ‘longest’ in any triangle. In weighted RNGQ, messages are forwarded to links which are not the longest in any triangle or quadrangle. Each node constructs weighted MST based on its 2-hop knowledge. Weighted LMST (Localized LMST) preserves only edges that are selected by both endpoints, and messages are forwarded on these links. Any available metric, such as delay, reliability, reputation etc. can be used as weight. Analysis and simulation show that weighted RNG performs better than existing Flooding and Rumor Mongering (or Gossip) schemes. The parameterless weighted LMST, MST, RNG and RNGQ (RNG over Quadrangle) based broadcasting schemes are compared, showing overall advantage for LMST. We also hint that a number of existing protocols can be simplified by applying concept from this article.