无线传感器网络增配节点实现双连通并优化中继路径

时所有节点有统一通信功率和传输半径的无线传感器网络,用平面无向图建模.提出一个基于广度优先的O(n3)多项式时间搜索算法来发现无线传感器网络中的双连通分量,继而确定网络中所有关节点,然后提出一个最坏情况有O(n2log(n/3))多项式计算时间的贪心算法来增加尽量少的节点以实现网络双连通,同时,增配节点形成的新路径有助于减少部分节点到汇聚节点的中继跳数.实验结果也验证了以上算法的效果.     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.     

无线传感器网络覆盖优化策略

针对无线传感器网络节点覆盖容易出现空洞和盲区的问题,提出一种基于改进人工鱼群算法的无线传感器网络覆盖优化算法.首先构建网络节点的信任度模型,进行节点轮换调度修复路由,然后采用改进人工鱼群算法进行无线传感器网络节点的自适应定位寻优,以人工鱼群优化的节点分布模型重构无线传感器网络(WSN)节点覆盖连通图,实现优化网络覆盖.仿真实验结果表明,利用覆盖优化算法进行WSN网络节点设计,明显地改善了网络节点的覆盖质量,提高了无线传感器网络的安全性能.     

监测奶牛无线传感器网络的连通支配集构造

基于一个对奶牛行为特征监测的自组织无线传感器网络,构造骨干网以解决节点多跳通信问题,并采用图的连通支配集来实现。提出了一个基于极大独立集的最小连通支配集的分布式构造算法,并证明了该算法的正确性。采用计算机程序仿真的实验结果表明,此算法简单有效、适应于节点移动和网络拓扑变化的环境、且构造的连通支配集占节点的比例为30%左右,有效减少冗余的转发节点,可节省宝贵的网络资源。     

无线传感器网络DV-Hop定位算法研究

针对无线传感器网络无需测距定位算法中典型的DV-Hop算法在不同参数设置时存在定位误差及定位时间差异较大的问题，分别分析并仿真了对定位误差和定位时间有较大影响的节点个数、网络平均连通度及监测区域等几个重要参数，考虑到无线传感器网络能量及成本的限制，通过仿真结果分析得出，网络平均连通度和节点个数分别对DV-Hop算法的定位精度及定位时间起主导作用。理论分析与仿真结果表明，在不同监测区域内，在确保DV-Hop算法低能量消耗的基础上，参数优化后的算法有效地降低了节点的定位误差。     

基于概率图理论的无线传感器网络覆盖性与选路策略研究

针对无线传感器网络中节点传感半径、节点传输半径与连通覆盖性之间的内在联系问题,基于几何概率理论,提出并证明了一个传感半径尺度刻画,若节点传感半径满足该尺度刻画,则监测区域内的每一个目标点,在任何时刻都能以渐近于1的概率落在至少一个传感器节点的感应范围内.另外,分析了无线传感器的连通覆盖问题,提出并证明了一个节点苏醒概率不等式,其可作为网络连通性不受到破坏的判断尺度和临界门限.最后文章在满足无线传感器网络连通必要性的前提下,基于图论模型,提出了一个无线传感器网络的选路策略并作了比较分析,得出简要结论.     

一种网络生长的无线传感器网络定位算法

提出了一种利用完全图进行无线传感器网络定位的分布式定位算法.仿真表明,该算法在噪声功率较小或者网络连通程度较高时,节点的定位精度更高,并且在网络的连通程度较低或者传感器节点分布不均匀时,仍然保持较好的定位精度.     

一种大概率强连通鲁棒性的无线传感器网络构造算法

针对无线传感器网络的软硬件必须具备鲁棒性、抗毁性和容错性的特点提出了一个具有大概率强连通鲁棒性的无线传感器网络构造算法并进行了仿真分析.该构造算法不仅具备WSN所要求的鲁棒性、抗毁性,而且也兼顾到传感器节点能量保护和网络功率控制.     

面向WSN的移动锚节点路径规划算法

针对无线传感器网络中使用移动锚节点辅助未知节点定位问题,提出了一种动态路径规划算法.该算法首先引用相关图论知识,把无线传感器网络看成一个连通的无向图,将传感器节点转化为图的顶点选取虚拟信标节点,通过蚁群算法遍历所选取的节点获得移动路径.并对传统宽度优先搜索算法中节点选取冗余和经典蚁群算法中存在的收敛速度慢等问题提出改进.仿真实验结果表明,改进算法能在保证一定通信覆盖率的情况下减少节点重复遍历以及锚节点的移动距离.     

基于遗传算法的无线传感器网络最小覆盖集算法

降低能耗以延长网络生存时间是无线传感器网络设计中的一个研究热点.提出一种利用遗传算法实现的"密度控制"策略.该策略利用无线传感器工作节点的最小节点子集(最小覆盖集),达到覆盖整个传感器网络区域的目的.所提出的算法能够较好地调和无线传感器网络寿命和网络覆盖率之间的矛盾,仿真实验证明了算法的有效性.     

Fp上不可约与本原多项式的高效确定算法

对于一大类整数n(n为素数乘于素数或1的积),分别给出有限域Fp上n次多项式是不可约多项式与本原多项式的一个充要条件,该条件可通过O(n3)次Fp上乘法加以验证,易于硬件实现.提出可约多项式一个充分条件,借此减少验证时间,并得到用O(n4)次Fp上乘法确定一个n次不可约多项式及一个n次本原多项式的高效算法.对于ECC中构造Fnp上椭圆曲线、序列密码中构造LFSR,有重要的应用价值.     

找K个最小生成树的并行算法

基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log~2n+Klogn~*)时间及O(n~2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n~2)处理器,这里n 是图的顶点数.     

单车独占性带时间窗口装卸货问题的分析与算法

提出了一类广泛存在于运输领域的NP-hard组合优化问题——独占性带时间窗口装卸货(E-PDPTW)问题,给出了它的数学描述,分析了其性质并把问题简化为不对称带时间窗口旅行商问题(TSP),提出了求解单车E-PDPTW问题的两阶段快速算法,其时间复杂度只有O(n^3),测试结果表明了该算法的有效性和快速性。     

平面多轮廓加工路径优化模型及其近似算法

应用一种节点可变的广义旅行商问题，为平面多轮廓加工路径优化问题建模．针对在分层实体制造中，轮廓加工路径的优化必须实时进行、优化计算时间必须小于因路径缩短而节省的加工时间的要求，以及每层加工的轮廓数量通常少于10^2、每条轮廓的节点数可能为10^3的特点，提出一种先用时间复杂度为O(n^2)的最近邻算法，求轮廓原始起点集合的旅行商问题解，然后在O(n)时间内改变每条轮廓的起点，进一步缩短路径长度的2步优化近似算法，从而兼顾了轮廓加工特点和算法实时性的要求．实验统计表明，该算法对路径的优化程度比仅按传统旅行商问题处理时提高了10％以上，且运行时间不超过0．1s。     

无线传感器网络关键区域覆盖优化算法

针对无线传感器网络中的关键区域覆盖NP完全问题,提出了一种启发式的关键区域覆盖优化算法CACOA.该算法对关键区域格点与一般区域格点,分配不同的权值创建感知区域图和终端集合,并以迭代合并方式创建加权节点Steiner树,进而形成具有最少数量的格点集合,并以格点集合中优化的格点位置来构建覆盖关键区域的传感器放置方法.理论分析证明了提出的CACOA算法一定能完全覆盖关键区域并形成一个有效的无线传感器网络,且算法的复杂度为O(n4).详细的仿真实验及与现有覆盖机制NPCC的比较表明,提出的覆盖优化算法CACOA在关键区域格点数、感知范围、发送范围和关键区域格点选择分布概率变化时放置的传感器数量明显少于NPCC覆盖机制.     

基于散列技术的快速子串归并算法

用统计方法研究东西方语言的多词单元问题和东方语言的未登录词问题时需要删除同频子串(子串归并)．传统的子串归并算法时间复杂度为O(n^2),在大规模语料库的处理中效率低下．提出一种基于散列技术的时间复杂度为O(n^2)的子串归并算法,并用数学方法证明其与O(n^2)复杂度的算法等价,即输入相同时输出也相同．不同规模语料上的实验结果表明新算法能够大大缩短子串归并所需时间,适用于大规模语料库的处理．     

方案集团序及其应用

提出了集团序的概念和方法,建立方案之间的3种关系.基于这3种关系,对每个方案定义了3个集合.定义了方案集的集团序,给出了集团序的构造算法.对算法进行了时间复杂度分析,该算法的时间复杂度为O(n3).定义了方案的集团序指标和方案的集团优先关系.对方案集团序进行了稳定性分析,给出了方案集团序稳定的充分条件.最后给出一个应用实例.     

Hankel矩阵和Vandermonde矩阵之逆的新矩阵表示式及快速算法

利用线性方程组是否有解给出Hankel矩阵、Vandermonde矩阵可逆的条件及求逆的递推公式，并给出了逆矩阵新的表示式．表明Hankel矩阵、Vandermonde矩阵的逆矩阵可以表示为一些特殊矩阵的乘积之和，并以Hankel矩阵为例，得到了求逆的快速算法，所需计算量为O(n^2)，一般n阶矩阵求逆的计算量为O(n^2)．     

带有可控性维护的单机调度问题研究

为在附加费用不大的条件下,通过最小化工件完成时间之和来减小work-in-process中的库存,尽可能使工件按期交付,在将工件调度与机器维护统一进行考虑的模型基础上,提出了带有预防性维护的单机调度问题,并对其进行了建模.将机器的维护周期适当放宽,以便在保证总的附加费用不超出预先给定的一个常数的前提下,实现工件的完成时间和的最小化.对工件加工允许中断的情况给出时间复杂度为O(n*ln(n));对工件加工不允许中断的情况给出一个启发式算法,其时间复杂度为O(n2).由该启发式算法很容易得到问题的可行解,从而为问题的进一步研究打下了基础.