时延和能耗均衡的强连通支配集构造算法

针对无线传感器网络中链路的非对称性,提出时延约束的强连通支配树(SDTT,strongly connected dominating tree with bounded transmission delay)问题,给出在有向图上构建传输时延和能量消耗均衡的强连通支配集的强连通支配树(SCDT,distributed strongly connected dominating tree)算法。首先在单位圆图(UDG)模型的基础上构建极大独立集(MIS),然后在具有双向权值的有向图上基于最小支撑树和最短路径树实现分布式SCDT算法,同时满足时延和能耗均衡的约束条件要求。理论算例分析和仿真结果表明提出的算法能有效地解决SDTT问题,构造联合约束的强连通支配集,形成时延和能耗均衡的虚拟骨干。

无线传感器网络中基于有向图的强连通支配集的构造

提出一种基于有向图的分布式强连通支配集的构造方法(Ds CDS,Distributed constructing of strongly Connected Dominating Set)。该方法通过分布式的选取权值大的节点,构造性能较优的强连通支配集。实验研究显示:该算法通过构造合理的权值及每次选取最大权值的最好节点,使得最终产生一个性能较优的强连通支配集,可以较大程度的延长无线传感网络的生命周期。

图的支配集若干问题的研究

本文提出了两个图支配集问题的变形即C强支配集和完全支配集问题,这两个问题都有重要的实际应用背景。我们证明了它们的判定问题是NP完全的,并且给出了它们相应优化问题的近似算法以及算法的近似度分析。

基于知网的中文结构排歧工具——VXY

该文介绍了基于知网的中文结构排歧工具系列中的一种—VXY。VXY采取了一种独到的排歧技术,对于语言难点采取"定点清除"的策略。它用来解决"V+N+的+N"类型的结构性歧义。VXY是一个自足的、可以现场考核检验的并可以真正付诸实用的系统,而不是仅仅某种方法论的表演或举例性的"游戏"。该文简要地介绍了VXY的组成部分,说明了它的意义计算的原理。同时,该文就如何更有效地利用知网进行结构和语义排歧,如何开辟不同于当前语言信息处理中的"三部曲"(语料标注、现成的计算、应试性的评测)的语言技术等问题进行讨论。