同址干扰限制下跳频异步组网的频率分配方法

针对跳频电台多台同址时相互间同址干扰严重和采用分频段跳频方式导致跳频增益小的不足,从子网内、子网间和跳频同步信号无干扰3个层次分析跳频异步组网中的全频段宽间隔频率分配约束条件,并建立代价函数;根据约束条件的特点对模拟退火算法的实际应用进行改进,提出同址干扰限制下的全频段宽间隔跳频异步组网频率分配方法。计算机求解结果表明新方法可以很好地解决同址干扰限制下的跳频频率分配问题,提高跳频通信抗干扰性能,对跳频电台发挥性能优势具有重要意义。     

Corrigendum Static Frequency Assignment in Cellular Networks

Abstract. No abstract.     

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.     

The Minimum Range Assignment Problem on Linear Radio Networks

Abstract. Given a set S of radio stations located on a line and an integer h ≥ 1 , the MIN ASSIGNMENT problem consists in finding a range assignment of minimum power consumption provided that any pair of stations can communicate in at most h hops. Previous positive results for this problem are only known when h=|S|-1 or in the uniform chain case (i.e., when the stations are equally spaced). As for the first case, Kirousis et al. [7] provided a polynomial-time algorithm while, for the second case, they derive a polynomial-time approximation algorithm. This paper presents the first polynomial-time, approximation algorithm for the MIN ASSIGNMENT problem. The algorithm guarantees a 2-approximation ratio and runs in O(hn ³ ) time. We also prove that, for fixed h and for ``well spaced' instances (a broad generalization of the uniform chain case), the problem admits a polynomial-time approximation scheme . This result significantly improves over the approximability result given by Kirousis {et al}. Both our approximation results are obtained via new algorithms that exactly solve two natural variants of the MIN ASSIGNMENT problem: the problem in which every station must reach a fixed one in at most h hops and the problem in which the goal is to select a subset of bases such that all the other stations must reach one base in at most h-1 hops. Finally, we show that for h=2 the MIN ASSIGNMENT problem can be exactly solved in O(n ³ ) time.     

OVSF-CDMA Code Assignment in Wireless Ad Hoc Networks

Orthogonal Variable Spreading Factor (OVSF) CDMA code consists of an infinite number of codewords with variable rates, in contrast to the conventional orthogonal fixed-spreading-factor CDMA code. Thus, it provides a means of supporting of variable rate data service at low hardware cost. However, assigning OVSF-CDMA codes to wireless ad hoc nodes posts a new challenge since not every pair of OVSF-CDMA codewords are orthogonal to each other. In an OVSF-CDMA wireless ad hoc network, a code assignment has to be conflict-free, i.e., two nodes can be assigned the same codeword or two non-orthogonal codewords if and only if their transmission will not interfere with each other. The throughput (resp., bottleneck) of a code assignment is the sum (resp., minimum) of the rates of the assigned codewords. The max-throughput (resp., max-bottleneck) conflict-free code assignment problem seeks a conflict-free code assignment which achieves the maximum throughput (resp., bottleneck). In this paper, we present several efficient methods for conflict-free code assignment in OVSF-CDMA wireless ad hoc networks. Each method is proved to be either a constant-approximation for max-throughput conflict-free code assignment problem, or a constant-approximation for max-bottleneck conflict-free code assignment problem, or constant-approximations for both problems simultaneously. The work of Peng-Jun Wan and Xiang-Yang Li is partially supported by NSF CCR-0311174. The preliminary version of the paper first appeared in ACM DIAL M-POMC 2004, workshop of ACM MobiCom 2004.     

A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem

Motivated by the problem of supporting energy-efficient broadcasting in ad hoc wireless networks, we study the Minimum Energy Consumption Broadcast Subgraph (MECBS) problem. We present the first logarithmic approximation algorithm for the problem which uses an interesting reduction to Node-Weighted Connected Dominating Set.     

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required.     

A Hybrid Neural-Genetic Algorithm for the Frequency Assignment Problem in Satellite Communications

A hybrid Neural-Genetic algorithm (NG) is presented for the frequency assignment problem in satellite communications (FAPSC). The goal of this problem is minimizing the cochannel interference between satellite communication systems by rearranging the frequency assignments. Previous approaches to FAPSC show lack of scalability, which leads to poor results when the size of the problem grows. The NG algorithm consists of a Hopfield neural network which manages the problem constraints hybridized with a genetic algorithm for improving the solutions obtained. This separate management of constraints and optimization of objective function gives the NG algorithm the properties of scalability required.We analyze the FAPSC and its formulation, describe and discuss the NG algorithm and solve a set of benchmark problems. The results obtained are compared with other existing approaches in order to show that the NG algorithm is more scalable and performs better than previous algorithms in the FAPSC.This work was supported in part by CICYT under grant TIC 1999-0216     

Property Testing in Bounded Degree Graphs

Abstract. We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Loosely speaking, given an oracle access to a graph, we wish to distinguish the case when the graph has a pre-determined property from the case when it is ``far' from having this property. Whereas they view graphs as represented by their adjacency matrix and measure the distance between graphs as a fraction of all possible vertex pairs, we view graphs as represented by bounded-length incidence lists and measure the distance between graphs as a fraction of the maximum possible number of edges. Thus, while the previous model is most appropriate for the study of dense graphs, our model is most appropriate for the study of bounded-degree graphs. In particular, we present randomized algorithms for testing whether an unknown bounded-degree graph is connected, k -connected (for k>1 ), cycle-free and Eulerian. Our algorithms work in time polynomial in 1/ɛ , always accept the graph when it has the tested property, and reject with high probability if the graph is ɛ -far from having the property. For example, the 2-connectivity algorithm rejects (with high probability) any N -vertex d -degree graph for which more than ɛ dN edges need to be added in order to make the graph 2-edge-connected. In addition we prove lower bounds of Ω(\sqrt N ) on the query complexity of testing algorithms for the bipartite and expander properties.     

An efficient distributed algorithm for finding all hinge vertices in networks

Let G=(V, E) be a graph with vertex set V of size n and edge set E of size m. A vertex v∈V is called a hinge vertex if there exist two vertices in V\{v} such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O(n ²) time complexity and O(m) message complexity. In particular, the total messages exchanged during the algorithm are at most 2m(log n+nlog n+1) bits.     

Distributed approximation of cellular coverage

We consider the following model of cellular networks. Each base station has a given finite capacity, and each client has some demand and profit. A client can be covered by a specific subset of the base stations, and its profit is obtained only if its demand is provided in full. The goal is to assign clients to base stations, so that the overall profit is maximized subject to base station capacity constraints.     

计算机网络中容量与流量分配优化研究

计算机通信网络中的链路容量与流量分配（CFA）问题是一个极其复杂的网络优化问题。本文采用正交多主体遗传算法求解CFA问题，得到了满意的结果。大量的计算机仿真实验结果表明，与传统方法相比，本文的算法能迅速地求出全局近似最优解，解的质量也有大幅度的提高。     

计算机网络中容量与流量分配优化研究

计算机通信网络中的链路容量与流量分配(CFA)问题是一个极其复杂的网络优化问题。本文采用正交多主体遗传算法求解CFA问题,得到了满意的结果。大量的计算机仿真实验结果表明,与传统方法相比,本文的算法能迅速地求出全局近似最优解,解的质量也有大幅度的提高。     

Finding optimal paths in MREP routing

Maximum Residual Energy Path (MREP) routing has been shown an effective routing scheme for energy conservation in battery powered wireless networks. Past studies on MREP routing are based on the assumption that the transmitting node consumes power, but the receiving node does not. This assumption is false if acknowledgment is required as occurs, for example, in some Bluetooth applications.If the receiving node does not consume power then the MREP routing problem for a single message is easily solvable in polynomial time using a simple Dijkstra-like algorithm. We further show in that when the receiving node does consume power the problem becomes NP-complete and is even impossible to approximate with an exponential approximation factor in polynomial time unless P=NP.     

蜂窝移动通信系统中基于免疫遗传算法的固定频率分配

频率分配的问题是一个典型的NP-Complete问题。本文介绍了一种基于免疫遗传算法的蜂窝移动通信固定频率分配方法。通过仿真与标准遗传算法对比分析,说明了免疫遗传算法在解决固定频率分配问题方面具有较好的效果。     

蜂窝移动通信系统中基于免疫遗传算法的固定频率分配

频率分配的问题是一个典型的NP—Complete问题。本文介绍了一种基于免疫遗传算法的蜂窝移动通信固定频率分配方法。通过仿真与标准遗传算法对比分析，说明了免疫遗传算法在解决固定频率分配问题方面具有较好的效果。     

蜂窝中继网络中协作切换策略研究

传统蜂窝网络架构存在着不少缺陷,小区边缘用户的服务质量远差于靠近基站中心的用户。通过部署中继,并完善其切换算法,提出了在该蜂窝中继网络中基于中继协作的切换策略,且对小区内及小区间切换策略进行细化,这样可以更精确的选择接入站点。比较了传统切换与协作切换中的切换阻塞率以及切换次数,通过仿真证明基于中继协作的协作切换的切换阻塞率小于传统切换,且基站间切换次数也得到降低,减轻了基站的负担,使系统性能得到提升。     

最大最小蚁群算法在实际GSM系统中频率规划的应用

探讨了应用最大最小蚁群算法（MMAS）来解决移动通讯系统（GSM）的频率规划问题。基于MMAS提出了一个可方便地控制算法的探索和开发能力并使之平衡的参数。实验结果表明,通过优化该参数,显著提高了算法的性能。