On the L(2, 1)-labelling of block graphs

The distance-two labelling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and non-consecutive integers. The L(2, 1)-labelling number of G, denoted by λ(G), is the smallest integer k such that G has a L(2, 1)-labelling in which no label is greater than k.

In this work, we study the L(2, 1)-labelling problem on block graphs. We find upper bounds for λ(G) in the general case and reduce those bounds for some particular cases of block graphs with maximum clique size equal to 3.     

Distance three labellings for K n ×K 2

In a wireless communication network, the channel assignment problem addresses the correct assignment of a frequency to each transmitter in the network. To avoid interference between two nearby transmitters, the assigned frequencies must satisfy certain conditions related to the distance between transmitters. We can use only a limited number of channels; hence, we have to minimize the range of frequencies used. The distance labelling of a graph is a mathematical model of the channel assignment problem derived from the work of Hale [Frequency assignment: Theory and application, Proc. IEEE 68 (1980), pp. 1497–1514]. Lam et al. [L(j, k)-labelings for the products of complete graphs, J. Comb. Optim. 14 (2007), pp. 219–227] addressed distance two labelling for the direct product K _n ×K _m of complete graphs K _n and K _m . In this paper, we solve the distance three labelling problem for K _n ×K ₂.     

On the locatic number of graphs

A vertex v of a connected graph G distinguishes a pair u, w of vertices of G if d(v, u)≠d(v, w), where d(·,·) denotes the length of a shortest path between two vertices in G. A k-partition Π={S ₁, S ₂, …, S _k } of the vertex set of G is said to be a locatic partition if for every pair of distinct vertices v and w of G, there exists a vertex s∈S _i for all 1≤i≤k that distinguishes v and w. The cardinality of a largest locatic partition is called the locatic number of G. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of order n having locatic number n, n?1 and n?2. Some realizable results are also given in this paper.     

基于遗传算法的全双工认知无线电网络信道分配策略研究

随着无线通信业务的不断增长和智能终端的日益多样化,无线频谱资源变得愈加紧缺,认知无线电作为一项能够有效解决频谱利用率过低的技术,近年来引起了学术界和工程界的广泛关注。在认知无线电网络中,次用户以合作频谱感知的方式智能判断主用户的工作状态,以便在授权频谱的空闲时段内接入并加以使用。将全双工通信技术引入到传统的认知无线电网络中,实现了频谱感知和数据传输的同步,既能确保数据传输的连续性,又能减少对主用户的干扰,对提升无线频谱利用率具有重要作用。对于多信道全双工认知无线电网络的信道分配,建立了次级网络吞吐量最大化模型,并通过惩罚函数法,将混合整数非线性规划问题转换成不带约束条件的非线性规划问题,提出了基于遗传算法的全双工认知无线电网络信道分配策略。仿真实验结果表明,该算法能在综合考虑算法复杂度和性能的情况下,完成信道分配并保证次级网络吞吐量的最大化。     

Game chromatic number of graphs with locally bounded number of cycles

We consider the coloring game and the marking game on graphs with bounded number of cycles passing through any edge. We prove that the game coloring number of a graph G is at most c+4, if every edge of G belongs to at most c different cycles. This result covers two earlier bounds on the game coloring number: for trees (c=0) and for cactuses (c=1).     

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.     

NC-OFDM在认知无线电中应用的仿真研究

认知无线电环境中,可用频谱具有分布宽、非连续和动态变化的特性。为了解决环境中数据传输的问题,研究设计能够适应频谱特性的通信系统。首先对系统所处的电磁环境进行动态频谱感知,估计出当前时刻的频谱信息,然后根据频谱信息对系统子载波进行裁剪,只利用未被授权用户使用的子载波以NC-OFDM作为传输技术进行数据传送。当通信环境动态变化时,验证系统是否能够准确的估计出当前的频谱信息,然后仿真比较NC-OFDM和NC-MC-CDMA系统的误码性能,并对其结果进行讨论分析。仿真结果表明:NC-OFDM技术能够适应认知环境中可用频谱的特性,且NC-OFDM系统比NC-MC-CDMA系统具有更好的误码性能。     

On the stability number of the edge intersection of two graphs

Let G be the graph obtained as the edge intersection of two graphs G₁, G₂ on the same vertex set V. We show that if at least one of G₁, G₂ is perfect, then α(G)?α(G₁)·α(G₂), where α() is the cardinality of the largest stable set. Moreover, for general G₁ and G₂, we show that α(G)?R(α(G₁)+1,α(G₂)+1)−1, where R(k,?) is the Ramsey number.     

The oriented chromatic number of Halin graphs

The oriented chromatic number of an oriented graph G is the minimum order of an oriented graph H such that G admits a homomorphism to H. The oriented chromatic number of an unoriented graph G is the maximal chromatic number over all possible orientations of G. In this paper, we prove that every Halin graph has oriented chromatic number at most 8, improving a previous bound by Hosseini Dolama and Sopena, and confirming the conjecture given by Vignal.     

基于区间数型多因素指派模型的多传感器优化分配方法

如何在不确定的复杂环境下优化分配有限的传感器资源是传感器管理系统中的一个关键问题.在用区间数来描述这种不确定性研究思路的基础上, 提出了一种新的区间数型多因素指派模型的求解方法. 首先, 给出了拓展的区间数型多因素指派模型. 然后, 采用不确定有序加权平均 (Uncertain ordered weighted average, UOWA) 算子集结规范化后的区间数型效率矩阵, 通过逼近理想解的排序法 (Technique for order preference by similarity to ideal solution, TOPSIS) 确定综合效率矩阵. 进一步将其转化为标准型指派问题, 最后通过匈牙利法得到最优解. 通过算例说明了该方法解决多传感器优化分配问题的有效性.     

基于混合蛙跳算法的认知无线电频谱分配

提出一种二进制混合蛙跳算法和基于该算法的认知无线电频谱分配方法。对该方法与颜色敏感图论着色算法进行仿真比较,结果表明在最大化网络总效益和最大化公平效益准则下,基于二进制混合蛙跳算法的频谱分配方法的性能较高。二进制混合蛙跳算法能找到理想最优解,颜色敏感图论着色算法得到的解与理想最优解偏差较大。     

梯图的点可区别全染色（n=7（mod8））

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法——三角排序,利用该排序的结果证明了当n=7（mod8）且Cn-1^4/2＋2〈m≤Cn ^4/2＋2时,梯图Lm≌Pm×P2的点可区别全色数为n。     

TFRC在认知无线电环境中的性能分析及改进

TCP友好速率控制协议(TCP Friendly Rate Control,TFRC)能够有效支持多媒体传输,而其在认知无线电环境中少有研究.本文通过在认知无线电环境中对TFRC进行仿真,考察了①感知周期,②主用户干扰,③信道异构性三个因素对TFRC性能的影响,进而提出了一种反馈机制改善TFRC对频谱切换前后信道容量变化适应的能力.实验结果表明TFRC性能与信道检测时长和主用户行为有着密切关系,提出的改进方法可以有效的提高TFRC在认知无线电环境中的性能.     

认知无线电网络信道选择机制

认知无线电网络通过动态频谱接入来提高无线频谱资源利用率,而节点目标信道选择的优劣直接决定了频谱接入性能的好坏. 本文首先综合考虑信道增益和空闲时间两种因素,设计以实现最大化系统容量的目标信道选择机制,然后引入信道热度概念,提出一种多属性决策信道选择机制. 仿真结果表明,多属性决策信道选择机制在系统吞吐量和频谱利用率性能上都有明显的提高.     

大射电望远镜馈源轨迹跟踪自适应控制

针对大射电望远镜悬索馈源为一非线性慢时变多变量耦合的系统特点, 提出用多变量极点配置自校正预测控制器 (MPSTPC)来实现馈源轨迹的跟踪控制. 建立了悬索 馈源系统的数学模型, 在有随机风扰动和无随机风扰动的情况下, 进行了数字仿真. 结果表明, 该控制算法可以很好地满足馈源系统轨迹跟踪高精度要求.     

On the modular inversion hidden number problem

We give a rigorous deterministic polynomial time algorithm for the modular inversion hidden number problem introduced by D. Boneh, S. Halevi and N.A. Howgrave-Graham in 2001. For our algorithm, we need to be given about 2/3 of the bits of the output, which matches one of the heuristic algorithms of D. Boneh, S. Halevi and N.A. Howgrave-Graham and answers one of their open questions. However their more efficient algorithm that requires only 1/3 of the bits of the output still remains heuristic.     

认知Ad-hoc网络中的快速邻居发现

在认知Ad-hoc网络中,邻居发现是MAC协议、拓扑管理、路由协议运行的前提,对网络性能有重要影响。针对认知Ad-hoc网络中节点的可用信道集异构和缺乏全网公共控制信道的特点,提出了基于可用频谱相似性的快速邻居发现算法。与现有同步邻居算法要求节点在全网可用信道集上切换以进行邻居发现的机制不同,所提算法要求节点在各自的可用信道集上切换,以一定的概率λ发送包含节点信息的分组。由于认知Ad-hoc网络全网可用信道集一般很大,而对于每个节点来说可能仅有几个可用信道,因此所提算法大大减小了邻居发现的时间开销。仿真分析表明,与现有算法相比,所提算法的时间开销至少降低了47%。