Broadcasting in UDG radio networks with unknown topology

The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time. In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning. It turns out that broadcasting time depends on two parameters of the UDG network, namely, its diameter D and its granularity g, which is the inverse of the minimum distance between any two stations. We present a deterministic broadcasting algorithm which works in time O (D g) under the conditional wake up model and prove that broadcasting in this model cannot be accomplished by any deterministic algorithm in time better than ${\Omega (D \sqrt{g})}The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time. In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning. It turns out that broadcasting time depends on two parameters of the UDG network, namely, its diameter D and its granularity g, which is the inverse of the minimum distance between any two stations. We present a deterministic broadcasting algorithm which works in time O (D g) under the conditional wake up model and prove that broadcasting in this model cannot be accomplished by any deterministic algorithm in time better than W(D ?g){\Omega (D \sqrt{g})} . For the spontaneous wake up model, we design two deterministic broadcasting algorithms: the first works in time O (D + g ²) and the second in time O (D log g). While neither of these algorithms alone is optimal for all parameter values, we prove that the algorithm obtained by interleaving their steps, and thus working in time O ( min{ D + g², D logg}){ O \left( \min\left\{ D + g^2, D \log{g}\right\}\right) }, turns out to be optimal by establishing a matching lower bound.     

Broadcasting in dynamic radio networks

It is reasonable to claim that almost all major questions related to radio broadcasting can be considered closed as far as static networks are considered: the network never changes during the entire protocol's execution. On the other hand, theoretical results on communication protocols in any scenario where the network topology may change during protocol's execution (i.e. a dynamic radio network) are very few.In this paper, we present a theoretical study of broadcasting in radio networks having dynamic unknown topology. The dynamic network is modeled by means of adversaries: we consider two of them. We first analyze an oblivious, memoryless random adversary that can be seen as the dynamic version of the average-case study presented by Elsässer and Gasieniec in JCSS, 2006. We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). This is the dynamic version of the worst-case study provided by Bar-Yehuda, Goldreich and Itai in JCSS, 1992.In both cases we provide tight bounds on the completion time of randomized broadcast protocols.     

Broadcasting in undirected ad hoc radio networks

We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working in expected time in n-node radio networks of diameter D, which is optimal, as it matches the lower bounds of Alon et al. [1] and Kushilevitz and Mansour [16]. Our algorithm improves the best previously known randomized broadcasting algorithm of Bar-Yehuda, Goldreich and Itai [3], running in expected time . (In fact, our result holds also in the setting of n-node directed radio networks of radius D.) For deterministic broadcasting, we show the lower bound on broadcasting time in n-node radio networks of diameter D. This implies previously known lower bounds of Bar-Yehuda, Goldreich and Itai [3] and Bruschi and Del Pinto [5], and is sharper than any of them in many cases. We also give an algorithm working in time , thus shrinking - for the first time - the gap between the upper and the lower bound on deterministic broadcasting time to a logarithmic factor. Received: 1 August 2003, Accepted: 18 March 2005, Published online: 15 June 2005 Dariusz R. Kowalski: This work was done during the stay of Dariusz Kowalski at the Research Chair in Distributed Computing of the Université du Québec en Outaouais, as a postdoctoral fellow. Research supported in part by KBN grant 4T11C04425. Andrzej Pelc: Research of Andrzej Pelc was supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais.     

Dynamic routing with inaccurate link state information in integrated IP-over-WDM networks

In this paper, we investigate the problem of dynamically routing bandwidth-guaranteed label switched paths (LSPs) in integrated IP-over-wavelength division multiplexed (WDM) networks with inaccurate link state information. To select a good path, a routing algorithm needs up-to-date link state information. This leads to excessive update overhead and scalability problems. In real networks, from the practical point of view, in order to avoid extensive overhead of advertising and processing link state information, updates need to be made periodically or based on a threshold trigger. This leads to inaccuracies in the link state information. Our contribution is that we consider the routing problem taking into consideration the uncertainty of link state parameters due to wavelength inaccuracy in addition to bandwidth inaccuracy. Based on the threshold-triggered update scheme, we present a probabilistic method to model the uncertainty of link state parameters. We then define a cost function reflecting the uncertainty. Depending on different cost metrics chosen to be optimized, we propose two routing algorithms considering the uncertainty of link state parameters. The objective is to minimize the impact of inaccurate information so that the blocking probability as well as setup failures are reduced. We use various performance metrics such as total blocking probability, blocking probability due to setup failures, blocking probability due to routing failures, bandwidth update frequency, and wavelength update frequency to evaluate the effectiveness of the proposed algorithms. Through extensive simulation experiments, we show that our algorithms can significantly reduce the impact of inaccurate link state information and perform very well.     

Resource allocation robustness in multi-core embedded systems with inaccurate information

Multi-core technologies are widely used in embedded systems and the resource allocation is vita to guarantee Quality of Service (QoS) requirements for applications on multi-core platforms. For heterogeneous multi-core systems, the statistical characteristics of execution times on different cores play a critical role in the resource allocation, and the differences between the actual execution time and the estimated execution time may significantly affect the performance of resource allocation and cause system to be less robust. In this paper, we present an evaluation method to study the impacts of inaccurate execution time information to the performance of resource allocation. We propose a systematic way to measure the robustness degradation of the system and evaluate how inaccurate probability parameters may affect the performance of resource allocations. Furthermore, we compare the performance of three widely used greedy heuristics when using the inaccurate information with simulations.     

Broadcasting cryptosystem in computer networks

A cryptosystem which can securely broadcast secret messages in a public access distributed system is proposed. Comparing with the existing broadcasting schemes, this scheme always requires fewer broadcasting messages. Furthermore, when a new user is inserted into the distributed system, the corresponding secret and public keys can be determined without changing any existing keys.     

An Effective Randomized QoS Routing Algorithm on Networks with Inaccurate Parameters

This paper develops an effective randomized on-demand QoS routing algorithm on networks with inaccurate link-state information.Several new techniques are proposed in the algorithm.First,the maximum safety rate and the minimum delay for each node in the network are pre-computed,which simplicfy the network complexity and provide the routing process with useful information .The routing process is dynamically directed by the safety rate and the minimum delay of the next node.Randomness in used at the link level and depends dynamically on the routing configurationl.This provides great flexibility for the routing process,prevents the routing process from overusing certain fixed routing paths,and adequately balances the safety rate and delay of the routing path.A network testing environment has been established and five parameters are introduced to measure the performance of QoS routing algorithms.Experimental results demonstrate that in terms of the proposed parameters,the algorithm outperforms existing Qos algorithms appearing in the literature.     

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.     

基于遗传算法的非精确信息组播约束路由研究

为求解基于非精确网络状态信息和弹性QoS需求约束的组播约束路由问题,提出了一种自适应的组播遗传算法.通过分析具有非精确度量参数的组播路径满足弹性QoS需求的概率,建立了基于概率法的组播约束路由模型.以种群多样性作为种群进化的度量指标,对进化过程中最大交叉率和最大变异率进行宏观调整;采用优势交叉变异法,在每次进化时,微调各个体的交叉率和变异率.仿真实验结果表明,该算法简单易操作,具有较高的收敛速度,能在一定程度上提高路由请求成功率.     

Probabilistic planning with clear preferences on missing information

For many real-world problems, environments at the time of planning are only partially-known. For example, robots often have to navigate partially-known terrains, planes often have to be scheduled under changing weather conditions, and car route-finders often have to figure out paths with only partial knowledge of traffic congestions. While general decision-theoretic planning that takes into account the uncertainty about the environment is hard to scale to large problems, many such problems exhibit a special property: one can clearly identify beforehand the best (called clearly preferred) values for the variables that represent the unknowns in the environment. For example, in the robot navigation problem, it is always preferred to find out that an initially unknown location is traversable rather than not, in the plane scheduling problem, it is always preferred for the weather to remain a good flying weather, and in route-finding problem, it is always preferred for the road of interest to be clear of traffic. It turns out that the existence of the clear preferences can be used to construct an efficient planner, called PPCP (Probabilistic Planning with Clear Preferences), that solves these planning problems by running a series of deterministic low-dimensional A*-like searches.In this paper, we formally define the notion of clear preferences on missing information, present the PPCP algorithm together with its extensive theoretical analysis, describe several useful extensions and optimizations of the algorithm and demonstrate the usefulness of PPCP on several applications in robotics. The theoretical analysis shows that once converged, the plan returned by PPCP is guaranteed to be optimal under certain conditions. The experimental analysis shows that running a series of fast low-dimensional searches turns out to be much faster than solving the full problem at once since memory requirements are much lower and deterministic searches are orders of magnitude faster than probabilistic planning.     

Consensus and collision detectors in radio networks

We consider the fault-tolerant consensus problem in radio networks with crash-prone nodes. Specifically, we develop lower bounds and matching upper bounds for this problem in single-hop radios networks, where all nodes are located within broadcast range of each other. In a novel break from existing work, we introduce a collision-prone communication model in which each node may lose an arbitrary subset of the messages sent by its neighbors during each round. This model is motivated by behavior observed in empirical studies of these networks. To cope with this communication unreliability we augment nodes with receiver-side collision detectors and present a new classification of these detectors in terms of accuracy and completeness. This classification is motivated by practical realities and allows us to determine, roughly speaking, how much collision detection capability is enough to solve the consensus problem efficiently in this setting. We consider nine different combinations of completeness and accuracy properties in total, determining for each whether consensus is solvable, and, if it is, a lower bound on the number of rounds required. Furthermore, we distinguish anonymous and non-anonymous protocols—where “anonymous” implies that devices do not have unique identifiers—determining what effect (if any) this extra information has on the complexity of the problem. In all relevant cases, we provide matching upper bounds. This work is supported by MURI–AFOSR SA2796PO 1-0000243658, USAF–AFRL #FA9550-04-1-0121, NSF Grant CCR-0121277, NSF-Texas Engineering Experiment Station Grant XS64961-CS, and DARPA F33615-01-C-1896.     

Predicting missing contacts in mobile social networks

Experimentally measured contact traces, such as those obtained in a conference setting by using short range wireless sensors, are usually limited with respect to the practical number of sensors that can be deployed as well as the number of available human volunteers. Moreover, most previous experiments in this field can report only partial contact information since not everyone participating in the experiment carries a sensor device. Previously collected contact traces have significantly contributed to the development of more realistic human mobility models. This in turn has influenced proposed routing algorithms for Delay Tolerant Networks where human contacts play a vital role in message delivery. By exploiting time-spatial properties of contact graphs as well as the popularity and social information of mobile nodes, we propose a novel method to reconstruct the missing parts of contact graphs where only a subset of nodes are able to sense contacts.     

Energy-efficient permutation routing in radio networks

A radio network (RN, for short) is a distributed system populated by small, hand-held commodity devices running on batteries. Since recharging batteries may not be possible while on mission, we are interested in designing protocols that are highly energy efficient. One of the most effective energy-saving strategies is to mandate that the stations go to sleep whenever they do not transmit or receive messages. It is well known that a station is expending power while its transceiver is active, that is, while transmitting or receiving a packet. It is perhaps surprising at first that a station is expending power even if it receives a packet that is not destined for it. Since, in single-hop radio networks, every station is within transmission range from every other station, the design of energy-efficient protocols is highly nontrivial. An instance of the permutation routing problem involves p stations of an RN, each storing n/p items. Each item has a unique destination which is the identity of the station to which the item must be routed. The goal is to route all the items to their destinations while expending as little energy as possible. Since, in the worst case, each item must be transmitted at least once, every permutation routing protocol must take n/k time slots. Similarly, each station must be awake for at least n/p time slots to transmit and/or receive packets. Our main contribution is to present an almost optimal energy-efficient permutation routing protocol for a k-channel, a p-station RN that routes n packets in at most (2d+2b+1)n/k+k time slots with no station being awake for more than (4d+7b-1)n/p time slots, where d=[(logp/k)/(logn/p)], b=[(log k)/(logn/p)] and k⩽√(p/2). Since, in most real-life situations, the number n of packets to route, the number p of stations in the RN, and the number k of channels available satisfy the relation k≪p≪n, it follows that d and b are very small     

Reduced-order filtering for networks with Markovian jumping parameters and missing measurements

The problem of reduced-order H _∞ filters design for Markovian jumping complex networks with polytopic time-varying transition probability matrices is first addressed in this paper, where the dynamic of each node is described by the sector-bounded nonlinearity. For the measurements, both quantisation and packet dropouts are considered, where each node has its own packet dropout rate. By using the mode- and transition probability-dependent Lyapunov function approach, two sufficient conditions are provided to ensure the stochastic stability and the disturbance attenuation performance of the resulting filtering error system. Then, the mode-independent reduced-order filters design method is proposed, and the filter parameters are given explicitly by linear matrix inequality method. Finally, the effectiveness of the theoretic results presented is illustrated via a numerical example which contains performance comparison of different mode-independent reduced-order filters.     

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.     

Weighted broadcast in linear radio networks

The weighted version of the broadcast range assignment problem in ad hoc wireless network is studied. Efficient algorithms are presented for the unbounded and bounded-hop broadcast problems for the linear radio network, where radio stations are placed on a straight line. For the unbounded case of the problem, the proposed algorithm runs in O(n²) time and using O(n) space, where n is the number of radio stations in the network. For the h-hop broadcast problem, the time and space complexities of our algorithm are O(hn²logn) and O(hn), respectively. This improves time complexity of the existing results for the same two problems by a factor of n and , respectively [C. Ambuhl, A.E.F. Clementi, M.D. Ianni, G. Rossi, A. Monti, R. Silvestri, The range assignment problem in non-homogeneous static ad hoc networks, in: Proc. 18th Int. Parallel and Distributed Precessing Symposium, 2004].