Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2011年 第48卷 第3期    出版日期:2011-03-15
无线传感器网络定位理论和算法
王小平, 罗 军, 沈昌祥,
2011, 48(3):  353-363. 
摘要 ( 641 )   HTML ( 3)   PDF (1323KB) ( 1465 )  
相关文章 | 计量指标
定位技术作为网络协议和应用的基础,已经成为无线传感器网络重要的支撑技术,是传感器网络研究的核心问题之一.系统地总结了近年来定位理论和算法的最新研究进展.全面阐述了定位问题的形式化定义、定位问题复杂度分析、基于刚性理论的定位理论和定位问题可计算性研究的最新成果.通过对定位理论的研究可以更好地揭示定位技术的本质,回答很多定位技术相关的基本问题.此外,还深入分析了近年来典型的定位算法,介绍每种算法的设计思想,分析其适用范围和不足.最后给出定位理论和定位算法未来的研究方向.
论文
复杂区域节点定位算法研究
黄 河, 陈国良, 孙玉娥, 肖明军, 黄刘生,
2011, 48(3):  364-373. 
摘要 ( 477 )   HTML ( 0)   PDF (2540KB) ( 379 )  
相关文章 | 计量指标
传统的无线传感器网络节点定位算法假设节点间的最短路径长度与实际几何距离之间存在函数映射关系.然而对于布设在复杂区域的无线传感器网络而言,这种函数映射关系不再成立,直接应用传统定位算法将会带来较大的定位误差.针对复杂区域中各向异性的无线传感器网络节点定位问题,提出了一种基于参考节点凸包划分的测距无关定位算法CHP.首先,对参考节点进行凸包划分;然后,按照路径最短优先原则为待定位节点选择所属凸包;最后,依据待定位节点所属凸包内的参考节点对其进行定位,有效避免了复杂区域边界和障碍物对定位精度的影响.仿真实验结果表明:CHP算法与传统算法相比在定位精度以及误差抖动方面有了大幅改进;同时,CHP定位算法在执行过程中最大限度地降低了复杂区域边界和障碍物对定位的不利影响.
面向高效复杂查询的常数度P2P系统构建技术
王小海 彭宇行 李东升
2011, 48(3):  374-381. 
摘要 ( 465 )   HTML ( 0)   PDF (1973KB) ( 373 )  
相关文章 | 计量指标
常数度P2P系统成为P2P领域的关注热点,但其研究主要集中于拓扑构建与维护,复杂查询研究及其支持优化技术相对较少.P2P系统高层特性很大程度上由底层拓扑决定,常数度拓扑的特点使得经典技术构建的常数度P2P系统数据局部性不佳,从而不支持高效复杂查询.针对这一不足提出了通用的面向高效复杂查询的构建技术,通过在数据层与DHT overlay间添加嵌入变换逻辑层,将拓扑结构信息引入构建过程以改善数据局部性,并采用此技术重构FissionE.分析与实验结果表明,新构建技术在不改变底层DHT的前提下有效确保数据局部性,减少查询综合开销,提高系统应用效率.
P2P网络中搭便车行为分析与抑制机制建模
乐光学, 李仁发, 陈 志, 周 旭,
2011, 48(3):  382-397. 
摘要 ( 531 )   HTML ( 0)   PDF (4157KB) ( 445 )  
相关文章 | 计量指标
在现实网络中,节点日益严重的搭便车行为对P2P可信流媒体网络的健壮性、可用性、服务响应速度和生命周期等产生了重要的影响.设计合理且有效的搭便车行为抑制和鼓励自私节点为系统作贡献的策略已成为P2P可信流媒体系统应用研究的一个重要方向.在全面分析节点的搭便车行为机理和搭便车行为对网络性能影响的基础上,对节点在P2P可信流媒体网络中的行为建模,在保证网络性能的前提下引入“适度安全、容错不容罪”的思想以保持网络系统共享资源的丰富,以P2P可信流媒体网络中节点的信誉度、贡献度和收益等为评价指标,运用博弈论构建了一个具有纳什均衡的搭便车行为抑制和激励节点为系统作贡献的策略模型,给出了相应的规则和约束条件,并进行了较为详细的分析.仿真实验表明,该策略模型能很好地解决搭便车行为抑制和激励节点为系统作贡献的问题,提高了P2P可信流媒体网络的性能和服务质量,使P2P可信流媒体网络系统实现相对平衡.
Ad Hoc网络中基于惩罚机制的激励合作转发模型
王 博 黄传河 杨文忠 但 峰 徐利亚
2011, 48(3):  398-406. 
摘要 ( 479 )   HTML ( 0)   PDF (1497KB) ( 479 )  
相关文章 | 计量指标
由于Ad hoc网络中的节点受到自身处理能力、存储空间和电池能量等各种资源的限制,节点为了节省自身的宝贵资源经常会表现出自私性,因此激励自私节点之间合作转发成为Ad hoc网络重要的研究内容.为此,结合重复博弈理论的思想,首先建立邻居节点之间的单阶段博弈模型,得到对应的支付策略,并对该模型进行延伸,建立了无限重复博弈模型来增强自私节点的合作行为,提出了3种激励自私节点的惩罚策略,分析了各自激励合作转发的条件.对自私节点的通用惩罚机制进行重点分析.最后通过仿真实验对该机制进行验证,并给出了在激励合作博弈中自私节点效用值的演化过程.仿真结果表明:该机制能够有效地激励节点合作转发的积极性,提高网络的吞吐量,延长网络的生存时间,以及增加网络的总预期收益.
公交时延容忍网络中基于索引的多级分组路由算法
李 陟 查玄阅 刘凤玉 张 宏
2011, 48(3):  407-414. 
摘要 ( 366 )   HTML ( 0)   PDF (1535KB) ( 541 )  
相关文章 | 计量指标
在由以公共交通系统中的车辆为节点构成的无线网络中,由于其中节点的高速移动造成拓扑的快速变化,网络连接也多以瞬时的短暂连接为主.这构成了时延容忍网络(delay tolerant networks, DTN)的一个典型应用场景.公交节点的特性决定了其移动方式(时间、路线)带有一定的规律性.基于这一特性,构建了一种抽象的网络拓扑模型,并基于该模型提出了一种基于索引的多级分组路由算法.实验证明,基于预先的分组信息,该路由算法应用于高速移动的公交时延容忍网络中将比其他DTN路由更加的高效.
基于可信平台模块的虚拟单调计数器研究
李 昊 秦 宇 冯登国
2011, 48(3):  415-422. 
摘要 ( 622 )   HTML ( 1)   PDF (1091KB) ( 435 )  
相关文章 | 计量指标
分析了存储中常见的重放攻击问题,提出一种基于可信平台模块TPM构造虚拟单调计数器的方案以阻止重放攻击.该方案基于TPM提供的硬件计数器、传输会话与私钥保护3种机制建立起虚拟计数器管理器(virtual counter manager,VCM),再由VCM构造和管理虚拟单调计数器.同时提出了一种VCM恶意行为检测算法,用以确保VCM的可信性,使得该方案的安全性仅依赖于TPM的防篡改性.最后,通过实验分析,提出了2个性能改进方案,以确保方案的可行性.
一种基于Web的可靠网络隐蔽时间信道的研究
钱玉文 赵邦信 孔建寿 王执铨
2011, 48(3):  423-431. 
摘要 ( 393 )   HTML ( 2)   PDF (1320KB) ( 511 )  
相关文章 | 计量指标
针对隐蔽时间信道在广域网上无法稳定工作的问题,提出了一种可靠隐蔽时间信道的模型.这种信道利用HTTP协议的网络包的时间间隔作为载体传输隐蔽信息.通过抗干扰处理、接收方确认等方法,设计了可靠的通信协议.采用队列理论对这种可靠隐蔽时间信道进行建模,并推导出了该信道的容量.为了获取该信道的性能指标,在Internet网络中实现了这种可靠隐蔽时间信道,进行了隐蔽信息的数据传输实验.实验结果表明,这种可靠隐蔽时间信道的传输率约为传统隐蔽时间信道的传输率的11倍,在相同的干扰下,可靠隐蔽时间信道的稳定性远好于传统的隐蔽时间信道.
一种基于Q学习的LDoS攻击实时防御机制及其CPN实现
刘 陶, 何炎祥, 熊 琦,
2011, 48(3):  432-439. 
摘要 ( 528 )   HTML ( 0)   PDF (2444KB) ( 382 )  
相关文章 | 计量指标
针对低速率拒绝服务攻击具有隐蔽性高、难以检测和及时响应的特点,提出了一种基于Q学习的LDoS攻击实时防御机制.该机制以终端自适应控制系统为保护对象,周期性地提取网络攻击特征参数,将其作为Q学习模块的输入参数,由Q学习模块进行最优防御的选择,优选出来的防御措施交与系统端执行.防御措施基于动态服务资源分配,根据系统当前运行状态对服务资源进行动态调整,从而保障正常服务请求的响应率.最后使用着色Petri网结合BP神经网络对攻击和防御过程进行了建模和仿真,结果表明:该方法具有较好的实时性和较高的灵敏性,能够对LDoS攻击行为进行实时响应,显著提高了系统防御的自动化程度.
一种三维快速傅里叶变换并行算法
方 维 孙广中 吴 超 陈国良
2011, 48(3):  440-446. 
摘要 ( 1093 )   HTML ( 3)   PDF (1610KB) ( 551 )  
相关文章 | 计量指标
三维快速傅里叶变换在物理计算领域中被广泛地使用.传统并行算法所使用的面划分和块划分方法并不适合稀疏三维向量的傅里叶变换.提出了一种新三维快速傅里叶变换的并行算法,针对稀疏三维向量的傅里叶变换,新算法通过重新调整x,y,z三个方向的计算顺序,能最大限度地减少计算量以及进程间的通信量,从而减少计算时间,提高并行加速比.详尽的理论分析以及多个高性能计算平台上的实验结果证明:在对稀疏三维向量作傅里叶变换时,新算法优于传统算法.
一种求解Ramsey数的DNA计算机算法
李肯立 郭 里 唐 卓 江 勇 李仁发
2011, 48(3):  447-454. 
摘要 ( 566 )   HTML ( 0)   PDF (892KB) ( 386 )  
相关文章 | 计量指标
Ramsey理论是组合数学中一个庞大而又丰富的领域,在集合论、逻辑学、分析以及代数学上具有极重要的应用.Ramsey数的求解是非常困难的,迄今为止只求出9个Ramsey数的准确值.探讨了DNA生物分子超级计算在求解这一困难数学问题的可能性.将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展,在许进等人提出来的位序列编码方法的基础上,提出一种用于求解Ramsey数的DNA计算模型与算法.从下界开始,直到上界,每次产生问题的解空间,然后根据Ramsey数的定义,删除满足特定条件的解,最后检测最终的试管以确定当前值是否为所要求的Ramsey数,最终得到具体的Ramsey数值.算法性能理论分析和模拟实验结果表明了本算法在求解Ramsey数的理论可能性.
基于总空闲时间增量的无等待流水调度混合遗传算法
朱 夏 李小平 王 茜
2011, 48(3):  455-463. 
摘要 ( 410 )   HTML ( 2)   PDF (1561KB) ( 466 )  
相关文章 | 计量指标
将NP-难的最小化最大完工时间无等待流水调度问题等价转化为最小化总空闲时间的问题,改变传统求解调度序列目标函数的模式,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间.分析启发式算法基本操作和进化算子的总空闲时间增量性质,设计基本总空闲时间增量法以快速评估新产生解的质量.提出混合遗传算法IHGA(increment based hybrid genetic algorithm)求解该问题,构造相应初始种群生成方法和进化算子,提出进化概率动态更新策略和种群收敛判断与再生机制;算法混合了迭代改进局部搜索以进一步提高解的质量.基于120个经典Benchmark实例,将IHGA与目前求解该问题的有效算法RAJ,GR,SA2,TSM和FCH进行比较.实验结果表明:IHGA在性能方面优于其他,计算效率方面优于SA2和TSM,略逊于GR,RAJ和FCH.
多项式光滑的支持向量回归机一般模型的收敛性研究
熊金志 徐建敏 袁华强
2011, 48(3):  464-470. 
摘要 ( 496 )   HTML ( 0)   PDF (669KB) ( 451 )  
相关文章 | 计量指标
2005年Lee 等人提出光滑的支持向量回归机模型ε-SSVR(smooth ε-support vector regression),2008年熊金志等人提出一个多项式光滑的支持向量回归机模型ε-PSSVR(polynomial smooth ε-support vector regression),使回归性能及效率得到了一定改善.然而,这种支持向量回归机是否存在一个一般模型,以及一般模型的收敛性等问题没有解决.为此,将一类多项式函数作为新的光滑函数,使用光滑技术,把多项式光滑模型ε-PSSVR推广到一般情形,提出一个多项式光滑的支持向量回归机一般模型ε-dPSSVR(dth-order polynomial smooth ε-support vector regression).并用数学归纳法证明该一般模型的全局收敛性.研究表明:1) 多项式光滑的支持向量回归机存在无穷多个模型,可以用一个一般模型来表示;2) 该一般模型是全局收敛的,其收敛上界比ε-SSVR缩小半个数量级.成功解决了多项式光滑的支持向量回归机的一般形式及其收敛性问题,为进一步研究多项式光滑的支持向量回归机提供了基本的理论支持.
车载环境下基于样本熵的语音端点检测方法
赵 欢 王纲金 胡 炼 彭秀娟
2011, 48(3):  471-476. 
摘要 ( 501 )   HTML ( 1)   PDF (1527KB) ( 541 )  
相关文章 | 计量指标
在语音处理中一个关键性问题是如何准确找到语音的起止位置,目前提出许多的语音端点检测算法不能得到理想的检测结果.由于样本熵是近似熵的改进算法,提出车载环境下基于样本熵的语音端点检测方法,并采用模糊C均值聚类算法和贝叶斯信息判决算法进行样本熵特征门限估计,以及使用双门限法进行语音端点检测.在TIMIT连续语音库上的实验表明,车载噪声环境下,样本熵法和近似熵法的检测正确率均远高于谱熵法和能量谱熵法,而样本熵法相对于近似熵法具有更好的检测效果,特别是当信噪比小于等于0dB时,样本熵法的检测性能优于近似熵法近10%.因此,样本熵法在车载智能语音领域具有很好的应用前景,能够为车载导航提供准确的语音端点检测技术.
一种自适应的粒子水平集算法
张桂娟, 朱登明, 邱显杰, 王兆其,
2011, 48(3):  477-485. 
摘要 ( 439 )   HTML ( 1)   PDF (2960KB) ( 509 )  
相关文章 | 计量指标
在基于物理的流体动画中,准确而高效地跟踪流体运动界面是提高仿真效果的关键. 针对传统算法存在耗散大、效率低等问题,提出了一种自适应的粒子水平集算法.通过建立耗散函数估计的重要性采样模型,获取自适应优化规则;然后基于该优化规则,定义窄带上的局部特征尺寸函数和累积变形率,构建采样点分布的随机过程,在此基础上进行流体界面跟踪计算的优化.实验及应用结果表明:该方法能有效利用计算资源,在界面跟踪的精度与效率方面均优于原有方法,能够得到满足需求的仿真效果.
基于重要性采样的动态场景全频阴影实时绘制算法
李 帅 冉 蛟 郝爱民 王 振
2011, 48(3):  486-493. 
摘要 ( 467 )   HTML ( 0)   PDF (1899KB) ( 425 )  
相关文章 | 计量指标
由于环境光源下的柔和阴影绘制需要针对每像素对来自全景方向的上千个光源进行昂贵的可见性计算,这给实时绘制带来了巨大的挑战.在消除预计算的前提下,提出了一种环境光源下动态场景全频阴影实时绘制算法.通过基于光照强度的环境图重要性采样、场景几何信息近似采样、阴影图预滤波、BRDF重要性采样等方法,实现了环境光源下动态场景的全频阴影及其环境映射绘制.实验表明,算法可满足环境光源、场景物体及其材质动态变化的要求,并可在保证实时绘制效率的前提下,取得近似于预计算算法的绘制质量.
一种复杂度约束下基于宏块优先顺序的运动估计优化算法
陆寄远, 张培钊, 段晓华, 朝红阳,
2011, 48(3):  494-500. 
摘要 ( 424 )   HTML ( 0)   PDF (940KB) ( 403 )  
相关文章 | 计量指标
在实际应用中,视频编码算法不仅需要提供最好的编码效率,而且还需要自动地适应各种平台不同的计算能力约束.这是一个在复杂度约束下的率失真优化问题.针对视频编码消耗计算资源最多的运动估计过程,提出一种复杂度约束下的优化算法.该算法对运动估计的失真度和复杂度建模,并通过该模型决定每个宏块的预测失真度-复杂度斜率(distortion-complexity slope, DC-slope),以此决定各个宏块运动估计的优先顺序,然后通过一个常微分方程建立控制参数与计算复杂度之间的关系,准确地控制运动估计的计算复杂度.通过实验比较,本算法不仅可以自适应地调整运动估计的计算复杂度,而且能在不同的复杂度约束下提供优化的编码性能.
融合多种特征点信息的最小生成树医学图像配准
支力佳, 张少敏, 赵大哲, 赵 宏,
2011, 48(3):  501-507. 
摘要 ( 523 )   HTML ( 0)   PDF (1403KB) ( 785 )  
相关文章 | 计量指标
针对医学图像配准鲁棒性强、准确性高和速度快的要求,提出了一种基于融合多种特征点信息的最小生成树医学图像配准算法.该算法首先提取3种特征点,Harris-Laplace,Laplacian of Gaussian和网格点;然后使用遗传算法去除特征点集的冗余,并通过对位映射构建无向完全图顶点集合;进而使用改进的Kruskal算法来构造最小生成树;最后使用得到的最小生成树估计Rényi熵.该算法较好地解决了在噪声数据中使用最小生成树估计Rényi熵面临的特征点不稳定导致鲁棒性低和构造最小生成树遇到的速度瓶颈.实验结果表明:在图像含有噪声、灰度不均匀以及初始误配范围较大的情况下,该算法在达到良好配准精度的同时,具有较强的鲁棒性和较快的速度.
多尺度最稳定极限区域仿射不变特征
罗荣华, 闵华清, 陈 聪,
2011, 48(3):  508-515. 
摘要 ( 593 )   HTML ( 0)   PDF (1353KB) ( 479 )  
相关文章 | 计量指标
基于局部区域的仿射不变特征被广泛应用于目标识别、场景分类和图像检索.在已经提出的仿射不变局部特征中,最稳定极限区域特征MSER(maximally stable extremal region)在多个方面具有优越的性能.但是由于最稳定极限区域特征MSER是从单一尺度图像中提取的,当图像尺度发生较大变化时,图像的模糊会使最稳定极限区域特征的边界发生变化,从而影响特征的稳定性.针对这一问题,通过定义多尺度空间中极限区域的稳定性指标,提出一种在图像空间和尺度空间都最稳定的极限区域特征,并设计了在尺度空间进行极限区域提取的快速算法.同时,针对极限区域可以较好地描述特征轮廓的特点,将局部灰度梯度信息和形状信息相结合设计了一种新的特征描述器.这种特征被称为多尺度最稳定极限区域MMSER(multi-scale maximally stable extremal region)特征.实验结果表明,在不同仿射变化条件下,MMSER的稳定性和可识别性均优于MSER,而且其描述器的创建时间约为SIFT描述器的45%.
冗余多线程结构的重命名寄存器配对共享分配策略
印 杰 江建慧
2011, 48(3):  516-527. 
摘要 ( 475 )   HTML ( 0)   PDF (3405KB) ( 347 )  
相关文章 | 计量指标
同时多线程处理器允许多个线程同时执行,一方面提高了处理器的性能,另一方面也为通过线程冗余执行来容错提供了支持.冗余多线程结构将线程复制成两份,二者独立执行,并比较结果,从而实现检错或者容错.冗余多线程结构主要采用ICOUNT调度策略来解决线程间资源共享问题.然而这种策略有可能造成“饥饿”现象,并降低处理器吞吐率.提出一种重命名寄存器配对共享分配策略,在运行N个独立线程的结构中,将重命名寄存器分成N份,每个主动线程及其相应的冗余线程共享其中的一份,这样就可以比较有效地缓解竞争式共享所带来的负面影响.实验表明,配对共享策略使得处理器的吞吐率和单个线程的性能均有较大幅度的提高.
软件故障优化注入方案研究与分析
潘庆和 洪炳熔
2011, 48(3):  528-534. 
摘要 ( 350 )   HTML ( 0)   PDF (820KB) ( 511 )  
相关文章 | 计量指标
主要研究了基于空间注入技术的软件故障注入(software-implemented fault injection, SWIFI)实验与分析中存在的问题.提出了并设计了2种基于空间注入技术的注入方式:等待方式与冲击方式,分别设计了2种方式的注入算法,并利用它们分别进行了故障注入实验,通过实验着重分析了注入地址不同的空间分布对实验产生的影响.详细讨论并分析了基于不同空间地址概率分布的故障注入实验问题,根据实验结果得出并证明结论,针对空间注入技术实施的2种注入算法在执行软件故障注入实验时总存在一种相对较优的注入方案.
组合逻辑电路中软错误率的频域分析方法
雷韶华 韩银和 李晓维
2011, 48(3):  535-544. 
摘要 ( 536 )   HTML ( 0)   PDF (1466KB) ( 542 )  
相关文章 | 计量指标
基于频域的软错误率分析方法可实现快速而精确地分析组合逻辑中软错误的电气屏蔽特性和窗闩屏蔽特性.该方法利用信号和逻辑门的频域特性,计算瞬时错误信号在组合逻辑电路中传播过程.基于频域的分析方法主要分为2个处理步骤:线性系统处理和非线性系统处理.线性系统处理通过电路系统的频率响应来计算输出信号.非线性系统处理瞬时信号的幅度过高而导致晶体管工作在不同的线性系统的情况.基于频域的分析方法采用电路系统的输入输出特性来计算非线性系统的输出信号.数据拟合的方法可以求解粒子击中而导致的瞬时错误信号的信号宽度和通路输出信号的信号宽度之间的函数关系.二者结合可计算由粒子撞击而导致错误信号的概率.使用反相器链的实验结果表明,相对于HSPICE仿真,基于频域的软错误率分析方法是高效的,且可以取得平均96.96%的精确度.使用ISCAS85基准电路和乘法器阵列的实验结果表明,基于频域的软错误率分析方法取得95.82%的精确度.