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.     

The Minimum Range Assignment Problem on Linear Radio Networks

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 3 ) 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 3 ) time.     

Radio Link Frequency Assignment

The problem of radio frequency assignment is to provide communication channels from limited spectral resources whilst keeping to a minimum the interference suffered by those whishing to communicate in a given radio communication network. This problem is a combinatorial (NP-hard) optimization problem. In 1993, the CELAR (the French Centre d'Electronique de l'Armement) built a suite of simplified versions of Radio Link Frequency Assignment Problems (RLFAP) starting from data on a real network Roisnel93. Initially designed for assessing the performances of several Constraint Logic Programming languages, these benchmarks have been made available to the public in the framework of the European EUCLID project CALMA (Combinatorial Algorithms for Military Applications). These problems should look very attractive to the CSP community: the problem is simple to represent, all constraints are binary and involve finite domain variables. They nevertheless have some of the flavors of real problems (including large size and several optimization criteria). This paper gives essential facts about the CELAR instances and also introduces the GRAPH instances which were generated during the CALMA project.     

认知无线电中基于改进脉冲耦合神经网络的频谱分配算法

本文研究认知无线电中的频谱分配问题,分析了脉冲耦合神经网络(PCNN)模型的脉冲传递和数据耦合特性在频谱分配中的作用,研究了授权用户可占用时间对认知无线电通信系统的影响,改进了PCNN模型,提出了一种基于PCNN的频谱算法,在避免频谱干扰的前提下缩短了频谱跨度,减少了频率的使用个数;将授权用户的可占用时间作为分配频谱的依据之一,在保证授权用户通信的基础上提高了系统中非授权用户的吞吐量。最后通过实验证明了算法的有效性。     

LID Assignment in InfiniBand Networks

To realize a path in an InfiniBand network, an address, known as local identifier (LID) in the InfiniBand specification, must be assigned to the destination of the path and used in the forwarding tables of intermediate switches to direct the traffic following the path. Hence, routing in InfiniBand has two components: (1) computing all paths, and (2) assigning LIDs to destinations and using them in intermediate switches to realize the paths. We refer to the task of computing paths as path computation and the task of assigning LIDs as LID assignment. This paper focuses on the LID assignment component, whose major issue is to minimize the number of LIDs required to support a given set of paths. We prove that the problem of realizing a given set of paths with a minimum number of LIDs is NP-complete, develop an integer linear programming formulation for this problem, design a number of heuristics that are effective and efficient in practical cases, and evaluate the performance of the heuristics through simulation. The experimental results indicate that the performance of our best performing heuristic is very close to optimal.     

认知无线Mesh网络中联合功率控制与信道分配的拥塞避免

受制于频谱资源有限性及链路负载差异性,网络拥塞成为认知无线Mesh网络研究中亟待解决的关键性问题.针对该问题,通过量化节点通信功率等级,并综合考虑网络干扰、链路有效容量及流量守恒等因素,建模了联合功率控制与信道分配的拥塞避免模型.进一步,提出了基于嵌套优化的拥塞避免机制,包括基于遗传算法的功率控制与信道分配、基于遗传算法的路由调度以及基于链路需求的最优路由算法.分别设计了组合编码和序列编码规则及流量守恒的约束控制机制,以保证个体进化的有效性及算法的快速收敛.一系列仿真实验表明该算法能够有效提高网络吞吐量,满足数据传输的实时性需求.     

网络效益最大化的认知无线电频谱分配算法

首先介绍了认知无线电系统中频谱分配的图论着色模型。针对该模型以网络效益最大化为目标,设计了自适应的交叉和变异算子,并在此基础上引入小生境技术,提出了基于自适应小生境遗传算法的认知无线电频谱分配算法。通过仿真实验比较了本算法、颜色敏感图论算法与经典遗传算法的性能。结果表明基于自适应小生境的遗传算法不易陷入局部最优,在较少的代数内就可以找到理想最优解,能更好地实现网络频谱效益最大化,其性能优于颜色敏感图论算法和经典遗传算法。     

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.     

Many-to-Many Communication in Radio Networks

Radio networks model wireless data communication when the bandwidth is limited to one wave frequency. The key restriction of such networks is mutual interference of packets arriving simultaneously at a node. The many-to-many (m2m) communication primitive involves p participant nodes from among n nodes in the network, where the distance between any pair of participants is at most d. The task is to have all the participants get to know all the input messages. We consider three cases of the m2m communication problem. In the ad-hoc case, each participant knows only its name and the values of n, p and d. In the partially centralized case, each participant knows the topology of the network and the values of p and d, but does not know the names of the other participants. In the centralized case, each participant knows the topology of the network and the names of all the participants. For the centralized m2m problem, we give deterministic protocols, for both undirected and directed networks, working in time, which is provably optimal. For the partially centralized m2m problem, we give a randomized protocol for undirected networks working in time with high probability (whp), and we show that any deterministic protocol requires time. For the ad-hoc m2m problem, we develop a randomized protocol for undirected networks that works in time whp. We show two lower bounds for the ad-hoc m2m problem. One lower bound states that any randomized protocol for the m2m ad hoc problem requires expected time. Another lower bound states that for any deterministic protocol for the m2m ad hoc problem, there is a network on which the protocol requires time when n−p(n)=Ω(n) and d>1, and that it requires Ω(n) time when n−p(n)=o(n). The results of this paper appeared in a preliminary form in “On many-to-many communication in packet radio networks” in Proceedings of the 10th Conference on Principles of Distributed Systems (OPODIS), Bordeaux, France, 2006, Lecture Notes in Computer Science 4305, Springer, Heidelberg, pp. 258–272. The work of B.S. Chlebus was supported by NSF Grant 0310503.     

Energy-Efficient Paths in Radio Networks

We consider a radio network consisting of n stations represented as the complete graph on a set of n points in the Euclidean plane with edge weights ω(p,q)=|pq| ^δ +C _p , for some constant δ>1 and nonnegative offset costs C _p . Our goal is to find paths of minimal energy cost between any pair of points that do not use more than some given number k of hops.     

Static Frequency Assignment in Cellular Networks

A cellular network is generally modeled as a subgraph of the triangular lattice. In the static frequency assignment problem, each vertex of the graph is a base station in the network, and has associated with it an integer weight that represents the number of calls that must be served at the vertex by assigning distinct frequencies per call. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. The static frequency assignment problem can be abstracted as a graph multicoloring problem. We describe an efficient algorithm to multicolor optimally any weighted even or odd length cycle representing a cellular network. This result is further extended to any outerplanar graph. For the problem of multicoloring an arbitrary connected subgraph of the triangular lattice, we demonstrate an approximation algorithm which guarantees that no more than 4/3 times the minimum number of required colors are used. Further, we show that this algorithm can be implemented in a distributed manner, where each station needs to have knowledge only of the weights at a small neighborhood. Received May 13, 1997; revised August 24, 1998.     

Corrigendum Static Frequency Assignment in Cellular Networks

Abstract. No abstract.     

无线ATM网络的CDMA传输技术

这篇论文在提出了一种采用CDMA传输技术的ATM网络结构的基础上,对CDMA体制应用于ATM网络无线接口的关键技术进行了详细的描述,并对其中某些问题给出了探讨性的结论。     

Faster Deterministic Communication in Radio Networks

We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. We show that gossiping can be completed in time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than units of time. Moreover, we show a schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log ³ n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log ² n) time broadcasting schedule by Kowalski and Pelc. A preliminary version of this paper appeared in the proceedings of ISAAC’06. F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported by the Research Council of Norway through the SPECTRUM project.     

Matching Networks with Different Levels of Detail

This paper deals with the issue of automatically matching networks with different levels of details. We first present why this issue is complex through an analysis of the differences that can be encountered between networks. We also present different criteria, tools and approaches used for network matching. We then propose a matching process, named NetMatcher. This process is a several steps process looking for potential candidates and then analysing them in order to determine the final results. It relies on the comparison of geometrical, attributive, and topological properties of objects. It determines one-to-many links between networks: in particular a node of the less detailed network can be matched to several arcs and nodes forming a complex junction in the most detailed network. An important strength of the process is to self-evaluate its results through the comparison of topological organisation of networks. This paves the way to an interactive editing of the results. The NetMatcher process has been intensively tested on a wide range of actual datasets, thus highlighting its effectiveness as well as its limits.

认知无线电中的功率控制

文章对认知无线电中的关键技术功率控制进行了研究,并在新的干扰模型一协议模型的基础上,研究了功率控制对调度可行性,带宽有效性的影响,且阐述了衡量网络性能的新的性能指标频率空间容量积BFP（Bandwidth Footprint Product）,并通过化简其数学公式可更加明显的发现它与功率控制的关系。     

MAC Protocols for Cognitive Radio Networks

由于认知无线网络(cognitive radio network,简称CRN)固有“二次利用”的特性,使其日益得到重视.而作为CRN核心构成的MAC(medium access control)协议,业已成为当前各研究机构的一个热点.主要对频谱感测技术、信道接入技术等MAC层核心设计问题进行了探讨,并针对认知无线网络MAC的特性及需求进行了分析,然后对设计MAC频谱感知技术、信道接入技术、频谱共享技术等相关研究进展进行了归类总结.最后指出了当前面临的主要研究难点及挑战,并提出了一些方向性建议.     

一种稀疏波长转换光网络中的波长分配算法

研究了具有波长转换功能的WDM光网络的分类以及已有的几种波长分配算法,分析了波长分配算法的一般流程。文中以波长变换次数最少做为所提出的波长分配算法的主要优化目标,根据WDM光网络中的节点是否具有波长转换的功能,结合等价光路由替换的思想,提出了在稀疏有限波长转换光网络中的一种启发式的波长分配算法。仿真实验表明,当光网络中的连接请求量较大时,该算法的阻塞率低于已有的一些波长分配算法,连接能力有了较大提高。     

一种稀疏波长转换光网络中的波长分配算法

研究了具有波长转换功能的WDM光网络的分类以及已有的几种波长分配算法，分析了波长分配算法的一般流程。文中以波长变换次数最少做为所提出的波长分配算法的主要优化目标，根据WDM光网络中的节点是否具有波长转换的功能，结合等价光路由替换的思想，提出了在稀疏有限波长转换光网络中的一种启发式的波长分配算法。仿真实验表明，当光网络中的连接请求量较大时，该算法的阻塞率低于已有的一些波长分配算法，连接能力有了较大提高。