Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks

A wireless sensor network usually consists of a large number of sensor nodes deployed in a field. One of the major communication operations is to broadcast a message from one node to the rest of the others. In this paper, we adopt the conflict-free communication model and study how to compute a transmission schedule that determines when and where a node should forward the message so that all nodes could receive the message in minimum time. We give two approximation algorithms for this NP-hard problem that have better theoretically guaranteed performances than the existing algorithms. The proposed approach could be applied to some other similar problems.     

Eigenvalue Bounds for the Orr–Sommerfeld Equation and Their Relevance to the Existence of Backward Wave Motion

Theoretical estimates of the phase velocity c_r of an arbitrary unstable, marginally stable or stable wave derived on the basis of the classical Orr–Sommerfeld eigenvalue problem governing the linear instability of plane Poiseuille flow or nearly parallel viscous shear flows in straight channels with velocity U(z) (=1?z², z∈[?1, +1] for plane Poiseuille flow), leave open the possibility that these phase velocities lie outside the range U_min<c_r<U_max but not a single experimental or numerical investigation, concerned with unstable waves in the context of flows with (d²U/dz²)_max≤0, has supported such a possibility as yet. U_min, U_max and (d²U/dz²)_max are, respectively, the minimum value of U(z), the maximum value of U(z), and the maximum value of (d²U/dz²) for z∈[?1, +1]. This gap between the theory on one hand and experiment and computation on the other has remained unexplained ever since Joseph [3] derived these estimates, first in 1968, and has even led to the speculation of a negative phase velocity in plane Poiseuille flow (i.e., c_r<U_min=0) and hence the possibility of a “backward” wave as in Jeffrey-Hamel flow in a diverging channel with backflow [1]. A simple mathematical proof of the nonexistence of such a possibility is given herein by showing that if (d²U/dz²)_max≤0 and (d⁴U/dz⁴)_min≥0 for z∈[?1, +1], then the phase velocity c_r of an arbitrary unstable wave must satisfy the inequality U_min<c_r<U_max, (d⁴U/dz⁴)_min is the minimum value of (d⁴U/dz⁴) for z∈[?1, +1], and therefore c_r cannot be negative when U_min=0. Another result that provides valuable insight into the general modal structure of the problem of instability of the above class of flows with U_min≥0 (e.g., plane Poiseuille flow) is that all standing waves, that is, modes for which c_r=0, are stable.     

Location-aided routing with uncertainty in mobile ad hoc networks: A stochastic semidefinite programming approach

We study location-aided routing under mobility in wireless ad hoc networks. Due to node mobility, the network topology changes continuously, and clearly there exists an intricate tradeoff between the message passing overhead and the latency in the route discovery process. Aiming to obtain a clear understanding of this tradeoff, we use stochastic semidefinite programming (SSDP), a newly developed optimization model, to deal with the location uncertainty associated with node mobility. In particular, we model both the speed and the direction of node movement by random variables and construct random ellipses accordingly to better capture the location uncertainty and the heterogeneity across different nodes. Based on SSDP, we propose a stochastic location-aided routing (SLAR) strategy to optimize the tradeoff between the message passing overhead and the latency. Our results reveal that in general SLAR can significantly reduce the overall overhead than existing deterministic algorithms, simply because the location uncertainty in the routing problem is better captured by the SSDP model.     

From fluid relaxations to practical algorithms for job shop scheduling: the makespan objective

We design an algorithm, called the fluid synchronization algorithm (FSA), for the job shop scheduling problem with the objective of minimizing the makespan. We round an optimal solution to a fluid relaxation, in which we replace discrete jobs with the flow of a continuous fluid, and use ideas from fair queueing in the area of communication networks in order to ensure that the discrete schedule is close to the one implied by the fluid relaxation. FSA produces a schedule with makespan at most C _max+(I+2)P _max J _max, where C _max is the lower bound provided by the fluid relaxation, I is the number of distinct job types, J _max is the maximum number of stages of any job-type, and P _max is the maximum processing time over all tasks. We report computational results based on all benchmark instances chosen from the OR library when N jobs from each job-type are present. The results suggest that FSA has a relative error of about 10% for N=10, 1% for N=100, 0.01% for N=1000. In comparison to eight different dispatch rules that have similar running times as FSA, FSA clearly dominates them. In comparison to the shifting bottleneck heuristic whose running time and memory requirements are several orders of magnitude larger than FSA, the shifting bottleneck heuristic produces better schedules for small N (up to 10), but fails to provide a solution for larger values of N. Received: September 1999 / Accepted: September 2001?Published online March 14, 2002     

An exact algorithm for minimum CDS with shortest path constraint in wireless networks

In this paper, we study a minimum connected dominating set problem (CDS) in wireless networks, which selects a minimum CDS with property that all intermediate nodes inside every pairwise shortest path should be included. Such a minimum CDS (we name this problem as SPCDS) is an important tache of some other algorithms for constructing a minimum CDS. We prove that finding such a minimum SPCDS can be achieved in polynomial time and design an exact algorithm with time complexity O(δ ² n), where δ is the maximum node degree in communication graph.     

Eigenvalue bounds for Orr-Sommerfeld equation ‘No backward wave’ theorem

Theoretical estimates of the phase velocityC _r of an arbitrary unstable, marginally stable or stable wave derived on the basis of the classical Orr-Sommerfeld eigenvalue problem governing the linear instability of plane Poiseuille flow (U(z)=1−z ²,−1≤z≤+1), leave open the possibility of these phase velocities lying outside the rangeU _min<C _r <U _max, but not a single experimental or numerical investigation in this regard, which are concerned with unstable or marginally stable waves has supported such a possibility as yet,U _min andU _max being respectively the minimum and the maximum value ofU(z) forz∈[−1, +1]. This gap between the theory on one side and the experiment and computation on the other has remained unexplained ever since Joseph derived these estimates, first, in 1968, and has even led to the speculation of a negative phase velocity (or rather,C _r <U _min=0) and hence the possibility of a ‘backward’ wave as in the case of the Jeffery-Hamel flow in a diverging channel with back flow ([1]). A simple mathematical proof of the non-existence of such a possibility is given herein by showing that the phase velocityC _r of an arbitrary unstable or marginally stable wave must satisfy the inequalityU _min<C _r <U _max. It follows as a consequence stated here in this explicit form for the first time to the best of our knowledge, that ‘overstability’ and not the ‘principle of exchange of stabilities’ is valid for the problem of plane Poiseuille flow.     

On the complexity of some arborescences finding problems on a multihop radio network

An arborescence of a multihop radio network is a directed spanning tree (with rootx) such that the edges are directed away from the root. Based upon an arborescence,x canbroadcast a message to other nodes according to the directed edges of the spanning tree. The minimum transmission power arborescence problem is to find an arborescence such that the message can be broadcasted to other nodes by using a minimal amount of transmission power. The minimum delay arborescence problem is to find an arborescence such that a message can be broadcasted to other nodes by using a minimal number of broadcast transmission. In this paper we show that both these problems areNP-complete. The reductions are from the maximum leaf spanning tree problem.Areverse arborescence is similar to an arborescence except that the edges are directed toward the root. Based upon a reverse arborescence, the root node cancollect information from other nodes. In this paper we also show that the reverse minimum transmission power arborescence problem can be solved with the same computational complexity as that of finding a minimum cost spanning tree, and the reverse minimum delay arborescence problem can be solved with the same computational complexity as that of finding a spanning tree.     

树网络上f模式最优广播问题的线性算法

网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点.所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数).假定每一次广播的执行时间为一单位.网络G的广播过程是广播的时间安排,使所有结点均获得消息.最优广播问题是求总时间最少的广播过程.在G是树网络情形,文献中已给出时间界为O(n2)的算法.本文给出线性时间的简捷算法.     

Approximating Scheduling Unrelated Parallel Machines in Parallel

We show how to approximate in NC the problem of scheduling unrelated parallel machines, for a fixed number of machines in which the makespan C _max is the objective function to minimize. We develop an approximate NC algorithm which finds a schedule whose length is at most (1+o(1))(C^* _max + 3 C^* _maxln(2n(n-1)/)), where C*_max denotes the optimal schedule, n the total number of jobs and a small positive constant. Our approach shows how to relate the linear program obtained by relaxing the integer programming formulation of the problem with a linear program formulation that is positive and in the packing/covering form. The established relationship enables us to transfer approximate fractional solutions from the later formulation that is known to be approximable in NC. Then, we show how to obtain an integer approximate solution, i.e. a schedule, from the fractional one, using the randomized rounding technique. We stress that our analysis assumes that the length of the schedule is (ln n) and that the min p _ij and max p _ij values are not too disparate (where p _ij is the time to run job j on machine i).Finally, we show that the same technique can be applied to the general assignment problem with a fixed number of machines and makespan T.     

Performance analysis of test scheduling schemes for a multi-access communications network

In this paper, we investigate the performance of two implementable test scheduling schemes for a multi-access communication channel whose components are subject to failure or malfunction. We relate the reliability of the system design, as reflected by system failure rate parameters, and the frequency at which the system (or nodal subsystem) is tested for failure detection, to the underlying key message delay and throughput performance. We derive queue-size distribution results for a discreteGeom ^(X)/D/1 system, representing the operation of the multi-access channel, or of a network node operating as a communications or queueing processor, which is maintained by a periodic or near periodic test scheduling scheme. Explicit formulas are presented for the system behavior as exhibited by the generating functions of the system queue-size distributions. The mean message delay is then calculated. The mean delay (or mean system size/workload performance index) can then be optimized by selecting the proper scheme parameters, under specified system (and component) failure conditions, noting that performing a test at too high a rate leads to inefficient system bandwidth utilization, while if tests are not carried out often enough, excessive message (or task) retransmissions and delays ensue.     

Connectivity threshold of Bluetooth graphs

We study the connectivity properties of random Bluetooth graphs that model certain “ad hoc” wireless networks. The graphs are obtained as “irrigation subgraphs” of the well‐known random geometric graph model. There are two parameters that control the model: the radius r that determines the “visible neighbors” of each vertex and the number of edges c that each vertex is allowed to send to these. The randomness comes from the underlying distribution of vertices in space and from the choices of each vertex. We prove that no connectivity can take place with high probability for a range of parameters r, c and completely characterize the connectivity threshold (in c) for values of r close the critical value for connectivity in the underlying random geometric graph.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 45–66, 2014     

Two new algorithms for the Min-Power Broadcast problem in static ad hoc networks

In this paper we address the Min-Power Broadcast problem in wireless ad hoc networks. Given a network with an identified source node w, the Min-Power Broadcast (MPB) problem is to assign transmission range to each node such that communication from w to other nodes is possible and the total energy consumption is minimized.

As the problem is NP-Hard we first propose a simulated annealing algorithm for the MPB problem. Utilizing a special node selection mechanism in its neighborhood structure the algorithm is designed in a way enabling an efficient power consumption evaluation and search for neighboring solutions. We then combine the algorithm with a decomposition approach to enhance its performance. This is achieved by decomposing the master problem and performing metropolis chain of the simulated annealing only on the much smaller subproblems resulting from decomposition. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed algorithms.     

Depth Properties of scaled attachment random recursive trees

We study depth properties of a general class of random recursive trees where each node i attaches to the random node \begin{align*}\left\lfloor iX_i\right\rfloor\end{align*} and X₀,…,X_n is a sequence of i.i.d. random variables taking values in [0,1). We call such trees scaled attachment random recursive trees (sarrt). We prove that the typical depth D_n, the maximum depth (or height) H_n and the minimum depth M_n of a sarrt are asymptotically given by D_n ～μ^‐1 log n, H_n ～ α_max log n and M_n ～ α_min log n where μ,α_max and α_min are constants depending only on the distribution of X₀ whenever X₀ has a density. In particular, this gives a new elementary proof for the height of uniform random recursive trees H_n ～ elog n that does not use branching random walks.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

A speculative transmission scheme for scheduling-latency reduction

Low latency is a critical requirement in some switching applications, specifically in parallel computer interconnection networks. The minimum latency in switches with centralized scheduling comprises two components, namely, the control-path latency and the data-path latency, which in a practical high-capacity, distributed switch implementation can be far greater than the cell duration. We introduce a speculative transmission scheme to significantly reduce the average control-path latency by allowing cells to proceed without waiting for a grant, under certain conditions. It operates in conjunction with any centralized matching algorithm to achieve a high maximum utilization and incorporates a reliable delivery mechanism to deal with failed speculations. The speculative transmission scheme is employed in a non-blocking N ×N R input-queued crossbar switch with R receivers per output. The control-path latency can be almost entirely eliminated for loads up to 50%. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Scheduling unit — time tasks on flow — shops under resource constraints

We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is proved that when the number of machines is arbitrary, the problem of minimizing schedule length is NP-hard, even when only one unit of the additional resource is available in the system. On the other hand, when the number of machines is fixed, then the problem is solvable in polynomial time, even for an arbitrary number of resource units available. For the two machine case anO(n log ₂ ² n) algorithm minimizing maximum lateness is also given. The presented results are also of importance in some message transmission systems.     

Probabilistic analysis of power assignments

A fundamental problem for wireless ad hoc networks is the assignment of suitable transmission powers to the wireless devices such that the resulting communication graph is connected. The goal is to minimize the total transmit power in order to maximize the life‐time of the network. Our aim is a probabilistic analysis of this power assignment problem. We prove complete convergence for arbitrary combinations of the dimension d and the distance‐power gradient p. Furthermore, we prove that the expected approximation ratio of the simple spanning tree heuristic is strictly less than its worst‐case ratio of 2. Our main technical novelties are two‐fold: First, we find a way to deal with the unbounded degree that the communication network induced by the optimal power assignment can have. Minimum spanning trees and traveling salesman tours, for which strong concentration results are known in Euclidean space, have bounded degree, which is heavily exploited in their analysis. Second, we apply a recent generalization of Azuma‐Hoeffding's inequality to prove complete convergence for the case for both power assignments and minimum spanning trees (MSTs). As far as we are aware, complete convergence for p > d has not been proved yet for any Euclidean functional. © 2017 The Authors Random Structures & Algorithms Published by Wiley Periodicals, Inc., 51, 483–505, 2017     

A combinatorial algorithm for the TDMA message scheduling problem

In this paper, we introduce a combinatorial algorithm for the message scheduling problem on Time Division Multiple Access (TDMA) networks. In TDMA networks, time is divided in to slots in which messages are scheduled. The frame length is defined as the total number of slots required for all stations to broadcast without message collisions. The objective is to provide a broadcast schedule of minimum frame length which also provides the maximum throughput. This problem is known to be -hard, thus efficient heuristics are needed to provide solutions to real-world instances. We present a two-phase algorithm which exploits the combinatorial structure of the problem in order to provide high quality solutions. The first phase finds a feasible frame length in which the throughput is maximized in phase two. Computational results are provided and compared with other heuristics in the literature as well as to the optimal solutions found using a commercial integer programming solver. Experiments on 63 benchmark instances show that the proposed method is able to provide optimal frame lengths for all cases with near optimal throughput.     

Computing bushy and thin triangulations

Shermer, T., Computing bushy and thin triangulations, Computational Geometry: Theory and Applications 1 (1991) 115–125. Given a triangulation of a simple polygon P, let t₂ be the number of leaves in the dual tree of the triangulation. Also, define t_max(P) and t_min(P) as the maximum and minimum values of t₂ over all triangulations of P. We present an O(n) time, O(n) space algorithm for finding a triangulation with t₂ = t_max(P), assuming that we are given any triangulation of P. We also show a triangulation with t₂ = t_min(P) can be found in O(n³) time, using O(n²) space.     

Rumor spreading on random regular graphs and expanders

Broadcasting algorithms are important building blocks of distributed systems. In this work we investigate the typical performance of the classical and well‐studied push model. Assume that initially one node in a given network holds some piece of information. In each round, every one of the informed nodes chooses independently a neighbor uniformly at random and transmits the message to it. In this paper we consider random networks where each vertex has degree d ≥ 3, i.e., the underlying graph is drawn uniformly at random from the set of all d ‐regular graphs with n vertices. We show that with probability 1 ‐ o(1) the push model broadcasts the message to all nodes within (1 + o(1))C_d lnn rounds, where Particularly, we can characterize precisely the effect of the node degree to the typical broadcast time of the push model. Moreover, we consider pseudo‐random regular networks, where we assume that the degree of each node is very large. There we show that the broadcast time is (1 + o(1))Clnn with probability 1 ‐ o(1), where \begin{align*}C = \lim_{d\to\infty}C_d = \frac{1}{\ln2} + 1\end{align*}. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Approximation for a scheduling problem with application in wireless networks

A network of many sensors and a base station that are deployed over a region is considered. Each sensor has a transmission range, an interference range and a carrier sensing range, which are r, αr and βr, respectively. In this paper, we study the minimum latency conflict-aware many-to-one data aggregation scheduling problem: Given locations of sensors along with a base station, a subset of all sensors, and parameters r, α and β, to find a schedule in which the data of each sensor in the subset can be transmitted to the base station with no conflicts, such that the latency is minimized. We designe an algorithm based on maximal independent sets, which has a latency bound of (a + 19b)R + Δb ? a + 5 time slots, where a and b are two constant integers relying on α and β, Δ is the maximum degree of network topology, and R is the trivial lower bound of latency. Here Δ contributes to an additive factor instead of a multiplicative one, thus our algorithm is nearly a constant (a + 19b)-ratio.