An Algorithmic View on OVSF Code Assignment

Orthogonal Variable Spreading Factor (OVSF) codes are used in UMTS to share the radio spectrum among several connections of possibly different bandwidth requirements. The combinatorial core of the OVSF code assignment problem is to assign some nodes of a complete binary tree of height h (the code tree) to n simultaneous connections, such that no two assigned nodes (codes) are on the same root-to-leaf path. A connection that uses a 2^-d fraction of the total bandwidth requires some code at depth d in the tree, but this code assignment is allowed to change over time. Requests for connections that would exceed the total available bandwidth are rejected. We consider the one-step code assignment problem: Given an assignment, move the minimum number of codes to serve a new request. Minn and Siu propose the so-called DCA algorithm to solve the problem optimally. In contrast, we show that DCA does not always return an optimal solution, and that the problem is NP-hard. We give an exact n^O(h)-time algorithm, and a polynomial-time greedy algorithm that achieves approximation ratio Θ(h). A more practically relevant version is the online code assignment problem, where future requests are not known in advance. Our objective is to minimize the overall number of code reassignments. We present a Θ(h)-competitive online algorithm, and show that no deterministic online algorithm can achieve a competitive ratio better than 1.5. We show that the greedy strategy (minimizing the number of reassignments in every step) is not better than Ω(h) competitive. We give a 2-resource augmented online algorithm that achieves an amortized constant number of (re-)assignments. Finally, we show that the problem is fixed-parameter tractable.     

Evolutionary algorithms for orthogonal frequency division multiplexing-based dynamic spectrum access systems

This paper proposes two evolutionary algorithms (EAs) to perform dynamic spectrum assignment in distributed OFDM-based cognitive radio access networks. To achieve better radio resource utilization, the central spectrum manager (CSM) jointly considers the type of modulation level which can be used by each radio pair when deciding the number of subcarriers to be assigned. Using the piecewise convex transformations, we reformulate the nonlinear integer programming problem to an integer linear programming so that it is possible to obtain the optimal solution. While the solution to the integer linear programming problem is NP-hard, the proposed EAs provide useful suboptimal solutions especially when the number of radios and subcarriers are large. Our first proposed EA adopts the genetic algorithm. Although the reproduction process generates chromosomes which do not fulfill the constraints, our algorithm integrates the invisible walls technique used in particle swam optimization to retain the diversity while constructing chromosomes for the next generation. The second EA adopts the ant colony optimization approach using a directed multigraph. The vertices are used to represent the subcarriers and each edge corresponds to a possible chosen modulation index of a specific radio. We further obtain the performance of the two EAs through simulations and benchmark them against the optimal solution. Our studies show that ant colony algorithm gives better solutions most of the time, however, its computation time increases much faster compared to generic algorithm when the numbers of users and subcarriers increase.     

The on-line first-fit algorithm for radio frequency assignment problems

The radio frequency assignment problem is to minimize the number of frequencies used by transmitters with no interference in radio communication networks; it can be modeled as the minimum vertex coloring problem on unit disk graphs. In this paper, we consider the on-line first-fit algorithm for the problem and show that the competitive ratio of the algorithm for the unit disk graph G with χ(G)=2 is 3, where χ(G) is the chromatic number of G. Moreover, the competitive ratio of the algorithm for the unit disk graph G with χ(G)>2 is at least 4−3/χ(G). The average performance for the algorithm is also discussed in this paper.     

Deterministic Communication in Radio Networks with Large Labels

We study deterministic gossiping in ad hoc radio networks with large node labels. The labels (identifiers) of the nodes come from a domain of size N which may be much larger than the size n of the network (the number of nodes). Most of the work on deterministic communication has been done for the model with small labels which assumes N = O(n). A notable exception is Peleg's paper, where the problem of deterministic communication in ad hoc radio networks with large labels is raised and a deterministic broadcasting algorithm is proposed, which runs in O(n²log n) time for N polynomially large in n. The O(nlog²n)-time deterministic broadcasting algorithm for networks with small labels given by Chrobak et al. implies deterministic O(n log N log n)-time broadcasting and O(n²log²N log n)-time gossiping in networks with large labels. We propose two new deterministic gossiping algorithms for ad hoc radio networks with large labels, which are the first such algorithms with subquadratic time for polynomially large N. More specifically, we propose: a deterministic O(n^3/2log²N log n)-time gossiping algorithm for directed networks; and a deterministic O(n log²N log²n)-time gossiping algorithm for undirected networks.     

SONET ADMs Minimization with Divisible Paths

We consider an optical routing problem. SONET add-drop multiplexers (ADMs) are the dominant cost factor in SONET/WDM rings. The number of SONET ADMs required by a set of traffic streams is determined by the routing and wavelength assignment of the traffic streams. In this paper we consider the version where a traffic stream may be divided into several parts and assigned different wavelengths. A specific division may increase or decrease the number of ADMs needed for a given input. Following previous work, we consider two versions. In the arc version the route of each traffic stream is given as input, and we need to decide on divisions of streams, and then to assign wavelengths so as to minimize the total number of used SONET ADMs. In the chord version the route is not prespecified, but is assigned by the algorithm, and only after this step are the divisions done and wavelengths assigned. The previously best known approximation algorithm for the arc version has a performance guarantee of 5/4 = 1.25 whereas the previously best known approximation algorithm for the chord version has a performance guarantee of 3/2 = 1.5. We improve both these results. We present a 36/29 ≈ 1.24138-approximation algorithm for the arc version and a 7/5 = 1.4-approximation algorithm for the chord version.     

A gradual neural-network algorithm for jointly time-slot/code assignment problems in packet radio networks

A gradual neural network (GNN) algorithm is presented for the jointly time-slot/code assignment problem (JTCAP) in a packet radio network in this paper. The goal of this newly defined problem is to find a simultaneous assignment of a time-slot and a code to each communication link, whereas time-slots and codes have been independently assigned in existing algorithms. A time/code division multiple access protocol is adopted for conflict-free communications, where packets are transmitted in repetition of fixed-length time-slots with specific codes. GNN seeks the time-slot/code assignment with the minimum number of time-slots subject to two constraints: (1) the number of codes must not exceed its upper limit and (2) any couple of links within conflict distance must not be assigned to the same time-slot/code pair. The restricted problem for only one code is known to be NP-complete. The performance of GNN is verified through solving 3000 instances with 100-500 nodes and 100-1000 links. The comparison with the lower bound and a greedy algorithm shows the superiority of GNN in terms of the solution quality with the comparable computation time.     

DeepMTL Pro: Deep Learning Based Multiple Transmitter Localization and Power Estimation

In this paper, we address the problem of Multiple Transmitter Localization (MTL). MTL is to determine the locations of potential multiple transmitters in a field, based on readings from a distributed set of sensors. In contrast to the widely studied single transmitter localization problem, the MTL problem has only been studied recently in a few works. MTL is of great significance in many applications wherein intruders may be present. E.g., in shared spectrum systems, detection of unauthorized transmitters and estimating their power are imperative to efficient utilization of the shared spectrum.In this paper, we present DeepMTL, a novel deep learning approach to address the MTL problem. In particular, we frame MTL as a sequence of two steps, each of which is a computer vision problem: image-to-image translation and object detection. The first step of image-to-image translation essentially maps an input image representing sensor readings to an image representing the distribution of transmitter locations, and the second object detection step derives precise locations of transmitters from the image of transmitter distributions. For the first step, we design our learning model sen2peak, while for the second step, we customize a state-of-the-art object detection model YOLOv3-cust. Using DeepMTL as a building block, we also develop techniques to estimate transmit power of the localized transmitters. We demonstrate the effectiveness of our approach via extensive large-scale simulations and show that our approach outperforms the previous approaches significantly (by 50% or more) in performance metrics including localization error, miss rate, and false alarm rate. Our method also incurs a very small latency. We evaluate our techniques over a small-scale area with real testbed data and the testbed results align with the simulation results.     

An ANTS heuristic for the frequency assignment problem

The problem considered in this paper consists in assigning frequencies to radio links between base stations and mobile transmitters in order to minimize the global interference over a given region. This problem is NP-hard and few results have been reported on techniques for solving it to optimality. We have applied to this problem an ANTS metaheuristic, that is, an approach following the ant colony optimization paradigm. Computational results, obtained on a number of standard problem instances, testify the effectiveness of the proposed approach.     

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].     

Load balancing in large-scale RFID systems

A radio frequency identifier (RFID) system consists of inexpensive, uniquely-identifiable tags that are mounted on physical objects, and readers that track these tags (and hence these physical objects) through RF communication. For many performance measures in large-scale RFID systems, the set of tags to be monitored needs to be properly balanced among all readers. In this paper we, therefore, address this load balancing problem for readers — how should a given set of tags be assigned to readers such that the cost for monitoring tags across the different readers is balanced, while guaranteeing that each tag is monitored by at least one reader. We first present centralized solutions to two different variants of this load balancing problem: (i) min–max cost assignment (MCA), and (ii) min–max tag count assignment (MTA). We show that MCA, the generalized variant of the load balancing problem, is NP-hard and hence present a 2-approximation algorithm for it. We next present an optimal centralized solution for MTA, an important specialized variant of the problem. Subsequently, we present a localized distributed algorithm that is probabilistic in nature and closely matches the performance of the centralized algorithms. Finally we present detailed simulation results that illustrate the performance of the localized distributed approach, how it compares with the centralized optimal and near-optimal solutions, and how it adapts the solution with changes in tag distribution and reader topology. Our results demonstrate that our schemes achieve very good performance even in highly dynamic large-scale RFID systems.     

Multidimensional Cube Packing

We consider the d-dimensional cube packing problem (d-CPP): given a list L of d-dimensional cubes and (an unlimited quantity of) d-dimensional unit-capacity cubes, called bins, find a packing of L into the minimum number of bins. We present two approximation algorithms for d-CPP, for fixed d. The first algorithm has an asymptotic performance bound that can be made arbitrarily close to 2 – (1/2)^d . The second algorithm is an improvement of the first and has an asymptotic performance bound that can be made arbitrarily close to 2 – (2/3)^d . To our knowledge, these results improve the bounds known so far for d = 2 and d = 3, and are the first results with bounds that are not exponential in the dimension.     

Link scheduling in wireless sensor networks: Distributed edge-coloring revisited

We consider the problem of link scheduling in a sensor network employing a TDMA MAC protocol. Our algorithm consists of two phases. The first phase involves edge-coloring: an assignment of a color to each edge in the network such that no two edges incident on the same node are assigned the same color. Our main result for the first phase is a distributed edge-coloring algorithm that needs at most (Δ+1) colors, where Δ is the maximum degree of the network. To our knowledge, this is the first distributed algorithm that can edge-color a graph using at most (Δ+1) colors. The second phase uses the edge-coloring solution for link scheduling. We map each color to a unique timeslot and attempt to assign a direction of transmission along each edge such that the hidden terminal problem is avoided; an important result we obtain is a characterization of network topologies for which such an assignment exists. Next, we consider topologies for which a feasible transmission assignment does not exist for all edges, and obtain such an assignment using additional timeslots. Finally, we show that reversing the direction of transmission along every edge leads to another feasible direction of transmission. Using both the transmission assignments, we obtain a TDMA MAC schedule which enables two-way communication between every pair of adjacent sensor nodes. For acyclic topologies, we prove that at most 2(Δ+1) timeslots are required. Results for general topologies are demonstrated using simulations; for sparse graphs, we show that the number of timeslots required is around 2(Δ+1). We show that the message and time complexity of our algorithm is O(nΔ²+n²m), where n is the number of nodes and m is the number of edges in the network. Through simulations, we demonstrate that the energy consumption of our solution increases linearly with Δ. We also propose extensions to account for non-ideal radio characteristics.     

Wireless Heterogeneous Transmitter Placement Using Multiobjective Variable-Length Genetic Algorithm

The problem of placing wireless transmitters to meet particular objectives, such as coverage and cost, has proven to be NP-hard. Furthermore, the heterogeneity of wireless networks makes the problem more intractable to deal with. This paper presents a novel multiobjective variable-length genetic algorithm to solve this problem. One does not need to determine the number of transmitters beforehand; the proposed algorithm simultaneously searches for the optimal number, types, and positions of heterogeneous transmitters by considering coverage, cost, capacity, and overlap. The proposed algorithm can achieve the optimal number of transmitters with coverage exceeding 98% on average for six benchmarks. These preferable experimental results demonstrate the high capability of the proposed algorithm for the wireless heterogeneous transmitter placement problem.      

2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs

An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference. A cellular network is generally modeled as a subgraph of the infinite triangular lattice. The distributed frequency assignment problem can be abstracted as a multicoloring problem on a weighted hexagonal graph, where the weight vector represents the number of calls to be assigned at vertices. In this paper we present a 2-local distributed algorithm for multicoloring triangle-free hexagonal graphs using only the local clique numbers ω₁(v) and ω₂(v) at each vertex v of the given hexagonal graph, which can be computed from local information available at the vertex. We prove that the algorithm uses no more than colors for any triangle-free hexagonal graph G, without explicitly computing the global clique number ω(G). Hence the competitive ratio of the algorithm is 5/4.     

Algorithms for solving the symmetry number problem on trees

The symmetry number of a tree is defined as the number of nodes of the maximum subtree of the tree that exhibits axial symmetry. Chin and Yen have presented an algorithm for solving the problem of finding the symmetry number of unrooted unordered trees in time O(n⁴). In this paper we present an improved algorithm for solving the symmetry number problem on trees that runs in time O(n³). We also show that our algorithm needs O(n²logn) time for trees with bounded degrees.     

Bounded-Diameter Minimum-Cost Graph Problems

We present approximation algorithms for two closely related bicriteria problems. Given a graph with two weight functions on the edges, length and cost, we consider the Bounded-Diameter Minimum-Cost Steiner Tree (BDMST) problem and the Bounded-Diameter Minimum-Cardinality Edge Addition (BDMC) problem. We present a parameterized approximation algorithm for the BDMST problem with a bicriteria approximation ratio of (O(p log s/log p),O(log s/log p)) where the first factor gives the relaxation on the diameter bound, the second factor is the cost-approximation factor, s is the number of required nodes and p, 1 ≤ p < s, is an input parameter. The parameter p allows a trade-off between the two approximation factors. This is the first improvement of the cost-approximation factor since the scheme proposed by Marathe et al. [9]. For example, p can be set to s^α to obtain an (O(s^α),O(1)) approximation for a constant α. The algorithm is very simple and is suitable for distributed implementations. We also present the first algorithm for Bounded-Hops Minimum-Cost Steiner Tree for complete graphs with triangle inequality. This model includes graphs defined by points in a Euclidean space of any dimension. The algorithm guarantees an approximation ratio of (O(log_ds),O(log_ds)) where d is the bound on the diameter. This is an improvement over the general-case approximation when d is comparable with s. For example, the ratio is (O(1),O(1)) for any d = s^α where α is a constant between 0 and 1. For the case where the number of terminals is a constant and all edge lengths are unit, we have a polynomial-time algorithm. This can be extended to any length function providing a (1 + ε) in the approximation with ε showing up in the time complexity of the algorithm. For another special case, where the cost of any edge is either 1 or 0 and the length of each edge is positive, an algorithm with approximation ratio of (O(log(c log s)), O(log(c log s))) is presented, where c is the cost of the optimal solution. This approximation is a significant improvement over (O(log s),O(log s)) when the cost of the solution c is much smaller than the number of terminals s. This is useful when an existing multicast network is to be modified to accommodate new terminals with the addition of as few new edges as possible. We also propose an approximation algorithm for the Bounded-Diameter Minimum-Cardinality Edge Addition problem, which achieves an O(log n) approximation while relaxing the diameter bound by 2. While this ratio is the same as the one claimed in [3], this algorithm is simple and combinatorial rather than based on the Linear Program solution and can be readily modified for a distributed implementation.     

Heuristic manipulation,tabu search and frequency assignment

Heuristic manipulation attempts to modify the search space of an optimization problem, using information provided by an underlying heuristic method. In this paper it is applied in combination with tabu search to the fixed spectrum frequency assignment problem.The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimize interference and the spectrum required. In fixed spectrum frequency assignment the frequency spectrum available is given and the target is to minimize the interference in the network.Computational experiments confirm that the manipulation technique is able to drive the underlying tabu search algorithm towards improved solutions.     

Anchor-free的尺度自适应行人检测算法

Anchor作为行人检测算法中的初始框,可以解决行人平移问题和缓解行人尺度变化问题,目前的行人检测算法通常都基于anchor.然而,使用anchor就需要精心调整对检测性能影响非常大的anchor超参数,如anchor的尺度和高宽比等.为避免这一问题,提出一种基于anchor-free损失函数的行人检测算法,并通过融合...     

Finding the closed partition of a planar graph

In this paper we consider the problem of finding aclosed partition in a directed graph. This problem has applications in concurrent probabilistic program verification. The best sequential algorithm known for this problem runs inO(mn) time wherem is the number of directed edges andn is the number of vertices in the given digraph. In this paper we present a linear-time sequential algorithm to solve the closed partition problem for planar digraphs that arecompact. We then build on this algorithm to obtain an O(n^1.5)-time sequential algorithm to solve the closed partition problem for a general planar digraph.This work was supported in part by NSF Grant CCR 89-10707.     

Energy optimal schedules for jobs with multiple active intervals

In this paper, we study the scheduling problem of jobs with multiple active intervals. Each job in the problem instance has disjoint active time intervals where it can be executed and a workload characterized by the required number of CPU cycles. Previously, people studied multiple interval job scheduling problem where each job must be assigned enough CPU cycles in one of its active intervals. We study a different practical version where the partial work done by the end of an interval remains valid and each job is considered finished if total CPU cycles assigned to it in all its active intervals reach the requirement. The goal is to find a feasible schedule that minimizes energy consumption. By adapting the algorithm for single interval jobs proposed in Yao, Demers and Shenker (1995) [1], one can still obtain an optimal schedule. However, the two phases in that algorithm (critical interval finding and scheduling the critical interval) can no longer be carried out directly. We present polynomial time algorithms to solve the two phases for jobs with multiple active intervals and therefore can still compute the optimal schedule in polynomial time.