Acknowledged broadcasting in ad hoc radio networks

We consider ad hoc radio networks in which each node knows only its own identity but is unaware of the topology of the network, or of any bound on its size or diameter. Acknowledged broadcasting (AB) is a communication task consisting in transmitting a message from a distinguished source to all other nodes of the network and making this fact common knowledge among all nodes. To do this, the underlying directed graph must be strongly connected. Working in a model allowing all nodes to transmit spontaneously even before getting the source message, Chlebus et al. [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] proved that AB is impossible, if collision detection is not available, and gave an AB algorithm using collision detection that works in time O(nD) where n is the number of nodes and D is the eccentricity of the source. Uchida et al. [J. Uchida, W. Chen, K. Wada, Acknowledged broadcasting and gossiping in ad hoc radio networks, Theoret. Comput. Sci. 377 (2007) 43-54] showed an AB algorithm without collision detection working in time O(n4/3log10/3n) for all strongly connected networks of size at least 2. In particular, it follows that the impossibility result from [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] is really caused by the singleton network for which AB amounts to realize that the source is alone. We improve those two results by presenting two generic AB algorithms using a broadcasting algorithm without acknowledgement, as a procedure. For a large class of broadcasting algorithms the resulting AB algorithm has the same time complexity. Using the currently best known broadcasting algorithms, we obtain an AB algorithm with collision detection working in time O(min{nlog²D,nlognloglogn}), for arbitrary strongly connected networks, and an AB algorithm without collision detection working in time O(nlognloglogn) for all strongly connected networks of size n?2. Moreover, we show that in the model in which only nodes that already got the source message can transmit, AB is infeasible in a strong sense: for any AB algorithm there exists an infinite family of networks for which this algorithm is incorrect.     

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     

Efficient broadcasting in radio networks with long-range interference

We study broadcasting, also known as one-to-all communication, in synchronous radio networks with known topology modeled by undirected (symmetric) graphs, where the interference range of a node is likely exceeding its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge they cannot communicate directly and transmission of one node disables recipience of any message at the other node. For a network $G,$ we term the smallest integer $d$ , s.t., for any interference edge $e$ there exists a simple path formed of at most $d$ transmission edges connecting the endpoints of $e$ as its interference distance $d_I$ . In this model the schedule of transmissions is precomputed in advance. It is based on the full knowledge of the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on a bounded number of transmissions executed at each node. We adopt $n$ as the number of nodes, $D_T$ is the diameter of the subnetwork induced by the transmission edges, and $\varDelta $ refers to the maximum combined degree (formed of transmission and interference edges) of the network. We contribute the following new results: (1) We prove that for networks with the interference distance $d_I\ge 2$ any broadcasting schedule requires at least $D_T+\varOmega (\varDelta \cdot \frac{\log {n}}{\log {\varDelta }})$ rounds. (2) We provide for networks modeled by bipartite graphs an algorithm that computes $1$ -shot (each node transmits at most once) broadcasting schedules of length $O(\varDelta \cdot \log {n})$ . (3) The main result of the paper is an algorithm that computes a $1$ -shot broadcasting schedule of length at most $4 \cdot D_T + O(\varDelta \cdot d_I \cdot \log ^4{n})$ for networks with arbitrary topology. Note that in view of the lower bound from (1) if $d_I$ is poly-logarithmic in $n$ this broadcast schedule is a poly-logarithmic factor away from the optimal solution.     

Time efficient k-shot broadcasting in known topology radio networks

The paper considers broadcasting protocols in radio networks with known topology that are efficient in both time and energy. The radio network is modelled as an undirected graph G = (V, E) where |V| = n. It is assumed that during execution of the communication task every node in V is allowed to transmit at most once. Under this assumption it is shown that any radio broadcast protocol requires transmission rounds, where D is the diameter of G. This lower bound is complemented with an efficient construction of a deterministic protocol that accomplishes broadcasting in rounds. Moreover, if we allow each node to transmit at most k times, the lower bound on the number of transmission rounds holds. We also provide a randomised protocol that accomplishes broadcasting in rounds. The paper concludes with a number of open problems in the area. The research of L. Gąsieniec, D.R. Kowalski and C. Su supported in part by the Royal Society grant Algorithmic and Combinatorial Aspects of Radio Communication, IJP - 2006/R2. The research of E. Kantor and D. Peleg supported in part by grants from the Minerva Foundation and the Israel Ministry of Science.     

On the complexity of bandwidth allocation in radio networks

We define and study an optimization problem that is motivated by bandwidth allocation in radio networks. Because radio transmissions are subject to interference constraints in radio networks, physical space is a common resource that the nodes have to share in such a way, that concurrent transmissions do not interfere. The bandwidth allocation problem we study under these constraints is the following. Given bandwidth (traffic) demands between the nodes of the network, the objective is to schedule the radio transmissions in such a way that the traffic demands are satisfied. The problem is similar to a multicommodity flow problem, where the capacity constraints are replaced by the more complex notion of non-interfering transmissions. We provide a formal specification of the problem that we call round weighting  . By modeling non-interfering radio transmissions as independent sets, we relate the complexity of round weighting to the complexity of various independent set problems (e.g. maximum weight independent set, vertex coloring, fractional coloring). From this relation, we deduce that in general, round weighting is hard to approximate within n^1−ε$n^{1-\epsilon }$ (n$n$ being the size of the radio network). We also provide polynomial (exact or approximation) algorithms e.g. in the following two cases: (a) when the interference constraints are specific (for instance for a network whose vertices belong to the Euclidean space), or (b) when the traffic demands are directed towards a unique node in the network (also called gathering, analogous to single commodity flow).     

Circuit-switched broadcasting in torus networks

In this paper we present three broadcast algorithms and lower bounds on the three main components of the broadcast time for 2-dimensional torus networks (wrap-around meshes) that use synchronous circuit-switched routing. The first algorithm is based on a recursive tiling of a torus and is optimal in terms of both phases and intermediate switch settings when the start-up time to initiate message transmissions is the dominant cost. It is the first broadcast algorithm to match the lower bound of log₅ N on number of phases (where N is the number of nodes). The second and third algorithms are hybrids which combine circuit-switching with the pipelining and arc-disjoint spanning trees techniques that are commonly used to speed up store-and-forward routing. When the propagation time of messages through the network is significant, our hybrid algorithms achieve close to optimal performance in terms of phases, intermediate switch settings, and total transmission time. They are the first algorithms to achieve this performance in terms of all three parameters simultaneously     

On neighbor discovery in cognitive radio networks

A cognitive radio node is a radio device capable of operating over multiple channels. As a result, a network consisting of one or more cognitive radio nodes can adapt to varying channel availability in its geographical region by dynamically changing the channel (or channels) nodes are using for communication.     

无线传感器网络节点部署问题研究

节点部署是无线传感器网络(W SNs)研究的一个基本问题。合理的节点部署方式有助于提高网络工作效率,优化利用网络资源。针对与节点部署相关的覆盖、连通、能耗三方面基本问题,对现有主要研究成果进行了分类和比较,讨论了三者之间的关系,总结性地提出并分析了网络覆盖和连通性能的评价标准。     

Rapid almost-complete broadcasting in faulty networks

This paper studies the problem of broadcasting in synchronous point-to-point networks, where one initiator owns a piece of information that has to be transmitted to all other vertices as fast as possible. The model of fractional dynamic faults with threshold is considered: in every step either a fixed number c(G)−1$c\left(G\right)-1$, where c(G)$c\left(G\right)$ is the edge connectivity of the communication graph, or a fraction α$\alpha$ of sent messages can be lost depending on which quantity is larger.     

Neural networks in quality function deployment

Quality Function Deployment (QFD) is a method of product planning in the early phases of the development of new products (pre-CAD phase). A major drawback of its application is the need to input a large amount of data and the necessity to estimate values on a rather subjective basis in order to complete the House of Quality. This data is plentiful and often designers lack the knowledge with satisfying accuracy. This paper suggests a machine learning approach in which a neural network automatically determines the data by learning from examples. Unlike conventional neural networks which are treated as black boxes, the topology and the weight values are not random but represent real circumstances and can directly be interpreted in the terms of the application. A final section discusses problems arising from the small number of training sets which is usually available in the field of product design.     

Circuit-switched broadcasting in torus and mesh networks

We consider the problem of broadcasting on torus and mesh networks using circuit-switched, half-duplex, and link-bound communication. In this paper, we obtain an optimal broadcasting algorithm that uses pd time steps for a d-dimensional torus with (2d+1)^p nodes in each side of the torus. Using this algorithm, we show that a broadcasting on a d-dimensional mesh with the same size can be done in pd+p+d-1 time steps     

事件驱动的水下传感器网络部署研究

考虑到水下传感器能力受限的特点,提出了一种针对不确定事件监测的水下传感器网络部署方法。初始部署阶段采用随机深度调节的方法让节点均匀分布,以捕捉到更多的事件。重部署阶段节点则根据探测到的事件信息,基于虚拟力的方法进行移动,并且通过引入分簇控制的思想,将节点移动范围限制在各个簇内,从而降低了重构的规模,保证了网络的连通性。仿真结果表明:该算法可以在满足覆盖性能的同时,有效缩短节点的移动距离。     

Dynamic IP configuration of terminals in broadcasting networks

The concept of synergy between broadcasting and telecommunication networks has been strengthened by the emergence of multi-modal terminals, which are used in a broadcast environment (mainly in DTV-Digital Television networks) to provide IP-based multimedia services. The migration of IPv4/IPv6 applications, either interactive or not, in a broadcasting network, requires that certain parameters, such as Host, Gateway and DNS IP addresses are configured in the terminals, either statically or dynamically. This paper discusses issues of dynamic configuration of IP parameters for DTV terminals, based on an overview of relevant mechanisms usually used in access networks. It proposes an IP-based auto-configuration protocol tailored to the needs of an IP/DTV access platform, describes its implementation and evaluates its behaviour in a laboratory-based DVB-T network.     

无线传感器网络的节点部署方法的研究进展

无线传感器网络正成为全球关注的热点领域,节点部署是无线传感器网络工作的基础,它直接关系到网络监测信息的准确性、完整性和时效性,但目前对这一方面的研究还比较少,研究工作远落后于其它方面.对节点部署的相关问题进行了阐述.在分类与比较的基础上系统的综述了近几年来节点部署方法的研究进展,讨论了目前存在的问题和需要进一步研究的方向,旨在对以后的研究提供参考.     

On game theoretic DSA-driven MAC for cognitive radio networks

The game theoretic dynamic spectrum allocation (DSA) technique is an efficient approach to coordinate cognitive radios sharing the spectrum. However, existing game based DSA algorithms lack a platform to support the game process. On the other hand, existing medium access control (MAC) protocols for cognitive radio networks do not fully utilize the adaptability and intelligence of the cognitive radio (CR) to achieve efficient spectrum utilization, let alone fairness and QoS support. Therefore it is necessary to develop DSA-driven MAC protocols with the game theoretic DSA embedded into the MAC layer. In this paper, based on the analysis of challenges for the game theoretic DSA in realistic applications, we conclude that a unified game theoretic DSA-driven MAC framework should constitute of four integral components: (1) DSA algorithm, deriving the spectrum access strategy for data communication; (2) negotiation mechanism, coordinating players to follow the right game policy; (3) clustering algorithm, limiting the negotiation within one cluster for scalability; (4) collision avoidance mechanism, eliminating collisions among clusters. With our MAC framework, DSA-driven MAC protocols can be conveniently developed, as illustrated in the design process of a concrete QoSe-DSA-driven MAC protocol. The game theoretic DSA-driven MAC framework can fulfill merits of game theoretic DSA algorithms including high spectrum utilization, collision-free channel access for data communication, QoS and fairness support. Through simulations, the merits of the DSA-driven MAC framework are demonstrated.     

Optimized broadcasting and multicasting protocols in cut-throughrouted networks

This paper addresses the one-to-all broadcasting problem and the one-to-many broadcasting problem, usually simply called broadcasting and multicasting, respectively. Broadcasting is the information dissemination problem in which a node of a network sends the same piece of information to all the other nodes. Multicasting is a partial broadcasting in the sense that only a subset of nodes forms the destination set. Both operations have many applications in parallel and distributed computing. In this paper, we study these problems in both line model, and cut-through model. The former assumes long distance calls between nonneighboring processors. The latter strengthens the line model by taking into account the use of a routing function. Long distance calls are possible in circuit-switched and wormhole-routed networks, and also in many networks supporting optical facilities. In the line model, it is well known that one can compute in polynomial time a [log₂n]-round broadcast or multicast protocol for any arbitrary network. Unfortunately such a protocol is often inefficient from a practical point of view because it does not use the resources of the network in a balanced way. In this paper, we present a new algorithm to compute broadcast or multicast protocols. This algorithm applies under both line and cut-through models. Moreover, it returns protocols that efficiently use the bandwidth of the network. From a complexity point of view, we also show that most of the optimization problems relative to the maximization of the efficiency of broadcast or multicast protocols in terms of switching time or vertex load are NP-complete. We have, however, derived polynomial efficient solutions for tree-networks